Estimation of time delay of arrival
Accurate and computationally efficient estimation of time delay of arrival data for localization of a sound source is described herein. A number of independent time delays are retained and validated through comparison with a set of dependent time delays. The method is robust against detrimental effects in the environment such as noise and reverberation. The resulting delays may then be used in sound source localization or other signal processing applications.
1. One or more non-transitory computer-readable media storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:
receiving signals s from N sensors s i [n], i=0 to N−1 where i is an index of a sensor and n is a time index;
calculating, using a first type of correlation, N−1 correlation sequences E{s i [n]s 0 [n−m]} for i=1 to N−1 where m is a time lag;
calculating an independent data set by finding a total of (N−1)×M independent delays (l) with associated correlation values (R) where l i,0 (k) , R i,0 (k) , i=1 to N−1, k=0 to M−1;
confirming, using a second type of correlation, Mi largest peaks found using the first type of correlation, the second type of correlation being direct correlation;
retaining M largest peaks of the correlation sequences confirmed using the second type of correlation, where M is a parameter and Mi>M;
determining a valid solution from a set of tentative solutions comprising N−1 delay values with an ith delay value (i=1 to N−1) drawn from one of the M N-1 possibilities and M available choices (k=0 to M−1) by:
calculating correlation sequences
E{s i [n]s j [n−m]},j= 1 to N− 2, i=j+ 1 to N− 1;
extracting a dependent data set comprising
l i,j (k) ,R i,j (k) ,j= 1 to N− 2, i=j+ 1 to N− 1, k= 0 to M− 1; and
selecting a solution.
2. The one or more non-transitory computer-readable storage media of claim 1 , wherein the selecting the solution comprises:
for p←0 to M N1 where available independent delays are
l i,0 , i=1 to N−1, deriving dependent delays
l i,j ←l i,0 −l j,0 , j=1 to N−2, i=j+1 to N−1 for each l i,j , find k i,j so that;
k
i
,
j
=
arg
min
k
l
i
,
j
-
l
i
,
j
(
k
)
;
determining a first metric for a pth solution, the first metric comprising
Δ
l
min
p
=
∑
j
=
1
N
-
2
∑
i
=
j
+
1
N
-
1
l
i
,
j
-
l
i
,
j
(
k
i
,
j
)
;
determining a second metric for a pth solution, the second metric comprising
R
p
=
∑
i
=
1
N
-
1
R
i
,
0
+
∑
j
=
1
N
-
2
∑
i
=
j
+
1
N
-
1
R
i
,
j
(
k
i
,
j
)
;
based at least in part upon the first metric and second metric, locating K solutions having the lowest Δlmin; and
selecting from among the K solutions the one having the highest R as a solution.
3. The one or more non-transitory computer-readable storage media of claim 1 , wherein the direct correlation Rd is calculated from the signals resulting in the arrays
l i,j (k) ,R i,j (k) ,Rd i,j (k) ,j= 0 to N− 2, i=j+ 1 to N− 1, k= 0 to Mi− 1.
4. The one or more non-transitory computer-readable storage media of claim 3 , wherein correlation values R are found with peak-picking over the correlation sequences obtained through the first type of correlation, the first type of correlation being phase transform.
5. The one or more non-transitory computer-readable storage media of claim 3 , wherein direct correlation values Rd are found from known lag values and where the signals are correlated directly in a time domain.
6. The one or more non-transitory computer-readable storage media of claim 3 , wherein only Mi direct correlation calculations are executed per index pair.
7. The one or more non-transitory computer-readable storage media of claim 3 , wherein for each index pair three arrays indexed by k are re-ordered, where direct correlation values Rd is sorted, and with l and R re-ordered according to a resultant order of Rd.
8. The one or more non-transitory computer-readable storage media of claim 1 , wherein the selecting the solution is based at least in part on:
a first metric indicative of closeness between dependent delays derived based at least in part on the independent delays for an individual tentative solution and dependent delays found from the correlation sequences of the individual tentative solution; and
a second metric that is based at least in part on a total correlation value of the independent data set and the dependent data set of the individual tentative solution.
9. One or more non-transitory computer-readable media storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:
receiving signals at a plurality of sensors;
calculating one or more correlation sequences from the received signals using a phase transformation correlation;
calculating an independent data set by finding independent delays (l) with associated phase transformation correlation values (R) from the one or more correlation sequences;
confirming Mi largest peaks found during phase transformation correlation using direct correlation;
retaining M largest peaks of the one or more correlation sequences confirmed using direct correlation, where M is a parameter and Mi>M;
extracting a dependent data set from the independent data set; and
selecting a solution from the dependent data set.
10. The one or more non-transitory computer-readable storage media of claim 9 , the acts further comprising selecting a set of tentative solutions comprising N−1 delay values with an ith delay value (i=1 to N−1) drawn from one of the M N-1 possibilities and M available choices (k=0 to M−1) by calculating correlation sequences
E{s i [n]s j [n−m]},j= 1 to N− 2, i=j+ 1 to N− 1.
11. The one or more non-transitory computer-readable storage media of claim 9 , wherein the dependent data set comprises
l i,j (k) ,R i,j (k) ,j= 1 to N− 2, i=j+ 1 to N− 1, k= 0 to M− 1.
12. The one or more non-transitory computer-readable storage media of claim 9 , wherein selecting the solution comprises:
for p←0 to M N-1 where the available independent delays are
l i,0 , i=1 to N−1, deriving dependent delays
l i,j ←l i,0 −l j,0 , j=1 to N−2, i=j+1 to N−1 for each l i,j , find k i,j so that;
k
i
,
j
=
arg
min
k
l
i
,
j
-
l
i
,
j
(
k
)
;
determining a first metric for a pth solution, the first metric comprising
Δ
l
min
p
=
∑
j
=
1
N
-
2
∑
i
=
j
+
1
N
-
1
l
i
,
j
-
l
i
,
j
(
k
i
,
j
)
;
determining a second metric for the pth solution, the second metric comprising
R
p
=
∑
i
=
1
N
-
1
R
i
,
0
+
∑
j
=
1
N
-
2
∑
i
=
j
+
1
N
-
1
R
i
,
j
(
k
i
,
j
)
;
based at least in part upon the first metric and second metric, locating the K solutions having the lowest Δlmin; and
selecting from among the K solutions the one having the highest R as a solution.
13. The one or more non-transitory computer-readable storage media of claim 9 , wherein the direct correlation Rd is calculated from the signals resulting in the arrays
l i,j (k) ,R i,j (k) ,Rd i,j (k) ,j= 0 to N− 2, i=j+ 1 to N− 1, k= 0 to Mi− 1.
14. The one or more non-transitory computer-readable storage media of claim 13 , wherein correlation values R are found with peak-picking over the correlation sequence obtained through phase transform.
15. The one or more non-transitory computer-readable storage media of claim 13 , wherein direct correlation values Rd are found from known lag values and where the signals are correlated directly in a time domain.
16. The one or more non-transitory computer-readable storage media of claim 13 , wherein for each index pair, three arrays indexed by k are re-ordered, where direct correlation values Rd are sorted, with l and R re-ordered according to a resultant order of Rd.
17. The one or more non-transitory computer-readable storage media of claim 9 , wherein the selecting the solution is based at least in part on:
a first metric indicative of closeness between dependent delays derived based at least in part on the independent delays for an individual tentative solution and dependent delays found from the correlation sequences of the individual tentative solution; and
a second metric that is based at least in part on a total correlation value of the independent data set and the dependent data set of the individual tentative solution.
18. A system comprising:
a plurality of sensors; and
a time-difference-of-arrival estimation module coupled to the sensors and configured to:
receive signals from the plurality of sensors;
calculate a correlation sequence from the received signals;
calculate an independent data set by finding independent delays (l) with associated correlation values (R) from the correlation sequence;
extract a dependent data set from the independent data set; and
select a solution from the dependent data set comprising:
for p←0 to M N-1 where available independent delays are
l i,0 , i=1 to N−1, derive, for M available choices (k=0 to M−1), dependent delays
l i,j ←l i,0 −l j,0 , j=1 to N−2, i=j+1 to N−1 for each l i,j , find k i,j so that;
k
i
,
j
=
arg
min
k
l
i
,
j
-
l
i
,
j
(
k
)
;
determine a first metric for a pth solution, the first metric comprising
Δ
l
min
p
=
∑
j
=
1
N
-
2
∑
i
=
j
+
1
N
-
1
l
i
,
j
-
l
i
,
j
(
k
i
,
j
)
;
determine a second metric for the pth solution, the second metric comprising
R
p
=
∑
i
=
1
N
-
1
R
i
,
0
+
∑
j
=
1
N
-
2
∑
i
=
j
+
1
N
-
1
R
i
,
j
(
k
i
,
j
)
;
and
based at least in part upon the first metric and second metric, locate the K solutions having the lowest Δlmin, then among these selected solutions selecting the one having the highest R as a solution.
19. The system of claim 18 , wherein the sensors comprise microphones.
20. The system of claim 18 , wherein the difference-of-arrival estimation module is further configured to confirm one or more peaks found during the phase transformation correlation using direct correlation.