Minimum-Spanning-Tree-Based Time Delay Estimation Robust to Outliers

Abstract

In this paper, we present a novel approach to estimating multiple time delays (TDs) in sensor arrays that is robust to outliers of TD measurements. These measurements are typically obtained from the peak of the cross correlation of two sensor signals but may contain outliers due to noise, significantly degrading the performance of downstream applications. To address this issue, we propose an approach to leverage only the best minimum-necessary TD measurements. First, we describe the general properties of TDs and show that the degree of freedom of TDs is the number of sensors minus one for a signal source, which indicates that the full set of TDs is redundant in this case. We then consider selecting nonredundant TDs from all measurements given the necessary and sufficient condition to reconstruct all TDs uniquely. We represent this condition by utilizing the graph theory, and then, formulate an optimization problem to select the optimal nonredundant TDs while satisfying the condition above. We reduce this problem to the problem of finding a minimum spanning tree and propose an efficient algorithm for TD estimation. Experimental evaluation shows that our method successfully eliminates outliers while ensuring that all TDs can be restored.

Keywords

• Time delay estimation
• generalized cross correlation
• graph theory
• microphone array
• minimum spanning tree