PROCEEDINGS of the23rd International Congress on Acoustics
9 to 13 September 2019 in Aachen, Germany

A target direction search algorithm based on microphone array
Xubin LIANG1; Difeng SUN1; Tianqing ZHAO1; Liangyong ZHANG1; Houlin FANG1; Fang ZHANG1
1

Northwest Institute of Nuclear Technology, China

ABSTRACTThe use of a microphone array to obtain the direction of a far-field target is an important means ofimpacting-point detection. In this paper, a new search algorithm based on time-delay orientation is proposed,
which USES the time-delay and position vector of the microphone pair in the array to estimate the unit vectorof the target direction by using the least square method, and then calculates the azimuth and pitch Angle ofthe target through this vector. On this basis, calculate the Euclidean distance between the projection of theposition vector in the target direction and the difference of the sound path between the microphones. By
setting the distance threshold, use a certain search rule to eliminate the time delay when the participation
calculation results in a relatively large distance. Extend, thereby finalizing the azimuth and elevation of thetarget. The simulation analysis of the proposed algorithm is carried out. Compared with the orientation
results of the unused search algorithm, the proposed algorithm not only has high orientation accuracy, butalso has strong stability and high reliability. It can avoid the problem of angle calculation error caused by thedamage of the microphone or individual time delay calculation errors. It has important reference significancefor the practical engineering application of using time-delay orientation such as the target impacting-point
measurement.
Keywords: Microphone array, Time-delay orientation, Search algorithm

1. INTRODUCTION
Orienting the target with the microphone array is the basis for the target detection and positioning.
Accurately obtaining the direction information of the target is the key and basis for obtaining the target
position information. At present, there are two methods for obtaining the target direction by using themicrophone array. One is to obtain the time delay between the microphone array and the reference
microphone (1-3), and use the geometric relationship of each microphone in the array to solve thetarget direction (4-6); The other is to use the multiple signal subspace method (MUSIC) (7) to solve thedirection of multiple targets, but the signal must be continuous and stable. For the first orientation
method, the time delay of the microphone pair must be obtained. If the desired time delay is wrong due
to poor performance or damage of a certain microphone, or individual delay calculation errors causedby other circumstances, the orientation result will be inaccurate or even wrong. But this kind ofsituation are often found in engineering applications. If you can find a directional method that canavoid such situations, and does not affect the directional performance, it will be of great significance toengineering applications.
In this paper, a target direction search algorithm based on microphone array is proposed, and theorientation model of arbitrary array is introduced. On this basis, certain search rules are used toeliminate some wrong time delay, and the target direction is finally determined. Finally, the algorithm
is simulated and compared.

2. ARBITRARY ARRAY ORIENTATION MODEL
Figure 1 shows the arbitrarily distributed N-element microphone array and sound source geometry
in three-dimensional space, where N microphones are isotropic, the target sound source is located at
the far field P point, and the azimuth and elevation angles are represented by φ and θ, respectively. The
position vector of the m-th element is represented by r m = [x m, y m, z m] T, and the direction vector of thej-th microphone to the i-th is represented as r ij=rj - r i, where {ię[1, N-1], ję[1, N], j > i }, a total of
Q direction vectors can be formed, where Q is12730

liangxubin@nint.ac.cn

N u N 1 / 2Q CN2(1)
PZ

Sensor m(xm, ym, zm)θSensor3

Sensor2

rm
Sensor NYOr1m

φr1
Sensor1

X

Figure 1 – Spatial N-element microphone array and sound source geometry
Each pair of N microphones obtains a time delay τij , which represents the time delay of themicrophone of the j-th with respect to the microphone of the i-th, and can obtain Q delays, which areexpressed as vectors:
τ [W12 ,W13 , ,W ( N 1) N ]T(2)Then the sound path difference vector d c  τ , where c is the speed of sound. The unit vector
from the sound source to the origin O is defined as kkª kx º«k »« y»«¬ k z »¼

ªsin(T )cos(M ) º« sin(T )sin(M ) »«»«¬ cos(T ) »¼

(3)

It is assumed that the target sound source P is located in the far field and the sound wave
propagates as a spherical wave. When the array radius is small, it is considered that the sound wave
propagates as a plane wave when passing through the array. The direction vector of Q microphonepairs is expressed as a matrix as follows:

Rª¬r12r13r( N 1) N º¼

T(4)Then there isRk c  τ(5)As shown in equation (3), c and R are known quantities, τ can be obtained by time delay
estimation, and the problem of solving the target azimuths φ and θ is converted into the solution
direction vector k. Here, N must be greater than or equal to 3, that is, at least a 3-element array.
When N=3, the matrix R is a non-singular square matrix. The inverse matrix R -1 of R can be directly
obtained to obtain k=c·R -1τ=c·(R TR) -1RTτ; when N > 3, equation (5) is an overdetermined equation,
there is no solution that strictly satisfies the equation, only the least square solution with the lowest
norm (8).
kˆmin arg( Rk  c  τ ) c  (R T R ) 1 R T τk(6)Therefore, when Nı3, kˆ c  (RT R)1 RT τ . Thus, the sound source azimuth angle φ and thepitch angle θ can be calculated by the direction vector k.

Mˆ arctan(kˆy / kˆx )Tˆ arctankˆx2  kˆy2 kˆz

 S  Mˆ d S
0 d Tˆ d S 2(7)
(8)

2731

3. ANGLE SEARCH ALGORITHM
3.1 Search RuleIn the case where all microphones have good performance and all the Q time delays are calculated
correctly, the direction of the target can be correctly calculated using equations (6) -(7). However, inthe case of one or more time delay errors, using equations (6)-(7) to calculate the orientation will
result in large errors or even errors, and certain rules are needed to eliminate the erroneous delay andthus estimate the correct k. Let ∆d beªsin(Tˆ)cos(Mˆ ) º«»kˆ a  kˆ « sin(Tˆ)sin(Mˆ ) »'d Rkˆ  c  τ,(9)«»ˆ«¬ cos(T ) »¼
∆d is the difference between the projection of the position vector of microphone pair on the target
direction and the sound path difference, where kˆ is the target direction unit vector, which iscomposed of the angle estimation value, a is the coefficient, generally aĮ1, and kˆ T kˆ { 1 . Thethreshold T0 is set. When ||Δd|| < T 0, the value of k obtained by equation (5) is considered to be valid;
when ||Δd||ıT 0, it is necessary to re-estimate k with the new matrix R nm, where R nm is a sub-matrix
formed by deleting n rows from R, m represents a different selection mode of n rows, and τnm is aR kˆ  c  τ indicating that
sub-vector formed by deleting a corresponding rows from τ, 'dnmnmnmnm

the difference between the projection of the position vector and the sound path difference that n
microphone pairs are removed.
First remove 1 row to search. When min{||∆d 1m||, mę[1, C Q1 ]} is less than the threshold T1 , stopsearching, and the k corresponding to the minimum value is the best estimate. Otherwise, continuesearching; remove 2 rows. When min{||∆d 2m||, mę[1, C Q2 ]} is less than the threshold T 2, the searchis stopped, otherwise the search is continued; and so on, until the Q-3 rows is removed, where Q isshown int equation (3). In the worst case, you need to search CQ0  CQ1  CQ2   CQQ 3 times. WhenN is large, you need to search too many times. Under normal circumstances, a time delay error orpoor performance of a certain microphone is more likely. Therefore, generally only consider
removing a row from R or a few rows related to a certain microphone, so that the number of searches
CQ0  CQ1  N will be greatly reduced.
3.2 Threshold Determination
In the search algorithm, the accurate selection of the threshold T can effectively delete the error
delay, and the selection of the threshold T is the key of the algorithm. According to the microphonearray orientation error analysis in (4, 6), the error of the orientation angle is proportional to the delayerror. When the position of the microphone array is relatively accurate, the main source of error is thetime delay error, so r T kˆ  c W  c  V , where σ is the time delay the estimation error. Therefore, theij

ij

τ

W

formula of the threshold value T n can be given asTnrow(R nm )c  V t(10)In the equations (10), row(R nm) represents the number of rows of the matrix R nm, and the rule for
judging whether to continue searching is(R nmkˆ  c  τ(R nmkˆ  c  τ)T (R nmkˆ  c  τ)  Tn(11)4. SIMULATION AND ANALYSIS
4.1 Simulation Parameter Determination
In this paper, the 2D model is selected for simulation. Only the azimuth angle is calculated. The
4-element cross-plane array is used, with an array radius of 1.5m. The sampling rate is 8000kSa, thecorresponding time is 0.125ms, and there are 6 time delays for the microphone pair. The time delay2732

used in the simulation is generated by the simulation method, as shown in equation (12).

W ij

rijTk / c  noise(12)The noise satisfies the average distribution, and the maximum amplitude is 0.125ms corresponding
to 1 sampling point. Considering the symmetry of the 4-element cross-plane array, only the azimuth
angle of 0~90° is selected. During the simulation, a certain time delay is randomly selected to set it toa random value, or a microphone is randomly selected, and the corresponding time delays are set torandom values, wherein the random values satisfy the average distribution. The Monte Carlo method isused to simulate in these two ways. The preset angle interval is 1°. The azimuth algorithm uses thealgorithms of equations (5)-(7) (hereinafter referred to as general algorithms) and angle searchalgorithms.
4.2 The Case of A Time Delay Error
The first method described in 4.1 is used for 1000 simulations. The angle error is defined as thedifference between the calculated angle and the preset value. The error statistics of each angle areshown in Figure 2. The curves of mean and standard deviation of the angle error in the case of twoalgorithms are shown in Figure 3-4. The maximum mean and maximum standard deviations of the twoalgorithms are shown in Table 1. It can be seen from Fig. 2-4 that the angle error of the generalalgorithm is very large, and the worst case is greater than 30°, which far exceeds the cross-plane arrayerror analyzed in the literature (5, 6). The maximum standard deviation of the angle error after using
the search algorithm is 0.4713 < σφ, and the mean is randomly distributed around 0.

(a) General algorithm(b) Search algorithm
Figure 2 – Angle error statistics figure(a) General algorithm(b) Search algorithm
Figure 3 – The mean curve of angle error at each angle

2733

(a) General algorithm(b) Search algorithm
Figure 4 – The standard deviation curve of angle error at each angle
4.3 The Case of Several Time Delay Errors Related to A Microphone
The second method described in 4.1 was used for 1000 times of simulation to obtain the angle
error. The error statistics of each angle are shown in Figure 5. The curves of the mean and standard
deviation of the angle error in the two algorithms were shown in figure 6 -7. The maximum mean andmaximum standard deviations of the two algorithms are shown in Table 1. It can be seen from Fig.
5-7 that the angle error obtained by the general algorithm is very large, and in the worst case, it islarger than 60°, and it is impossible to use it for angle calculation; the maximum standard deviationof the angle error after using the search algorithm is 0.5764.< σφ, there is no significant change in theangle error mean value of 0.0276 and the standard deviation of 0.3499 when the time delay is normal,
and the mean value is also randomly distributed around 0.

(a) General algorithm(b) Search algorithm
Figure 5 – Angle error statistics figure(a) General algorithm(b) Search algorithm
Figure 6 – The mean curve of angle error at each angle

2734

(a) General algorithm(b) Search algorithm
Figure 7 – The standard deviation curve of angle error at each angle
4.4 Analysis of Simulation Results
According to the analysis of 3.1, the general algorithm is a special case of the proposed algorithm
in this paper. The simulation was also carried out for such cases. The simulation results are shown in
Table 1. The results are consistent with the analysis. The simulation results of the search algorithm
used in 4.2 and 4.3 are subjected to probability density analysis, and then compared with the normal
distribution probability density function, wherein the mean μ of the normal distribution is theaverage of the error mean, and the standard deviation σ is the average of the error standard deviation.
As can be seen in Figure 8-9, it is consistent with the normal distribution function

Figure 8 – Probability density curve with a delay error

Figure 9 – Probability density curve for several delay errors
In this paper, the simulation results of the general algorithm and the search algorithm in three cases
are listed, as shown in Table 1.

2735

Table 1 – Simulation resultsCondition

General algorithm, deg

Search algorithm, deg

Max of mean

Max of stddev

Max of mean

Max of stddev

Normal0.0294

0.34930.0276

0.3499One time-delay error

1.2203

11.54310.04130.4713

Mult time-delay errors

9.130928.2536

0.04630.5764

From the above simulation results, we can conclude:
1) In the case that all time delays are normal, both the general algorithm and the search algorithm inthis paper can obtain correct orientation results and there is no difference between the two. The searchalgorithm in this paper is degraded to the general algorithm, which verifies the analysis of 3.1;
2) A time delay error, or several time delay errors caused by poor performance of individualmicrophones, will directly lead to the failure of the general algorithm, unable to obtain the correctorientation results. However, the search algorithm of this paper is not affected and can still obtain thecorrect orientation result;3) Using the search algorithm of this paper, the positioning accuracy is high, the angle error
conforms to the normal distribution, and the algorithm has strong stability and high reliability.

5. CONCLUSIONSIn this paper, the method of time delay orientation for arbitrary arrays is analyzed. Based on this, asearch algorithm is proposed, which can eliminate the incorrect time delay and retain the correct delay
participation angle calculation, avoiding the error of angle estimation caused by individual incorrecttime delay. Through the simulation comparison of approximate real environment, it is proved that theproposed algorithm not only has high precision, but also has strong stability and high reliability. It has
important reference significance for the practical engineering application of using time-delayorientation such as the target impacting-point measurement.

ACKNOWLEDGEMENTS
The authors would like to thank the Acoustics Engineering Innovation Group Fund for funding thisproject, and also would like to thank every member of the project team for their contribution to thework of this paper. This work would not have been possible without your help.

REFERENCES
1. Piersol A G. Time delay estimation using phase data. IEEE Transfer Acoustic, Speech, Signal
Processing. 1981; ASSP-29(3):471㨪477.
2. Brian G.Ferguson, Kam W.Lo. Time delay estimation in the presence of source or receiver motion. The
Journal of Acoustical Society of America. 2016;140(4):3007-3007.
3. PETR DOSTALEK, VLADIMIR VASEK, JAN DOLINAY. Direction of sound wave arrival
determination using time-delay estimation and beamforming methods. WSEAS Transactions on Circuitsand Systems. 2009; (12):893-904.
4. Tang JS, Sun C; Li B. A new model for arbitrary array in air to ensure accurate acoustic-passive
direction estimation. Journal of Northwestern Polytechnical University. 2004;22(4):496-499.
5. Jia YD, Leng SL, Liu WC, Pei HA. Modeling of passive acoustic sensing with four-sensor array fortarget localization, Acta Armamentarii. 2001;22(2):206-209.
6. Wang Z, Li H, Zhao JW, et al. Error analysis of acoustic passive localization in the air. AppliedAcoustics. 2000;19(2):39-43.
7. M Wax, T Shan, T Kailath. Spatio-temporal spectral analysis by eigen-structure methods. IEEE Trans.
1984;ASSP-32(4):817- 827.
8. Rao C R, Mitra S K. Generalized inverse of matrices. New York, USA: John Wiley&Sons; 1971.p.
51~55.

2736