Time Delay Estimation Based on Entropy Estimation

Fei Wen and Qun Wan

Time Delay Estimation Based on Entropy Estimation

Fei Wen and Qun Wan

—This paper presents a novel time delay estimation (TDE) method using the concept of entropy. The relative delay is estimated by minimizing the estimated joint entropy of multiple sensor output signals. When estimating the entropy, the information about the prior distribution of the source signal is not required. Instead, the Parzen window estimator is employed to estimate the density function of the source signal from multiple sensor output signals. Meanwhile, based on the Parzen window estimator, the Renyi’s quadratic entropy (RQE) is incorporated to effectively and efficiently estimate the high-dimensional joint entropy of the multichannel outputs. Furthermore, a modified form ofthe joint entropyfor embedding information about reverberation (multipath reflections) for speech signals is introduced to enhance the estimator’s robustness against reverberation.

Index Terms—Acoustic source localization, joint entropy, Parzen window estimator, Renyi’s quadratic entropy, time delay estimation.

1. Introduction

Time delay estimation (TDE) is a fundamental problem in modern signal processing and it is widely used in radiating sources localization and tracking systems. Early study on TDE mostly focused on applications in radar and sonar. Nowadays, the same technique is used for localizing and tracking acoustic sources in a room environment[1]?[3].

Among the traditional techniques for TDE, the most popular algorithms in practice are based on the generalized cross-correlation (GCC) method[4]. The GCC method performs fairly well in moderately noisy and lightly reverberant environments[5],[6]. However, its performance degrades dramatically when reverberation or noise is high. To deal better with noise and reverberation, an effective approach based on the multichannel cross-correlation coefficient (MCCC) was proposed in [7]. It was found that the algorithm’s robustness gets better as the number of sensors increases. As a second-order-statistics (SOS) measure of the dependence among multiple random variables, the MCCC is ideal for Gaussian source signals. But for non-Gaussian source signals, higher order statistics (HOS) imply more information about their dependence. In [8], an information theory based TDE approach for the speech signal was introduced by pre-specifying the source signal as the Laplacian distribution (LD) and minimizing the joint entropy, which can be viewed as a higher order statistic[9].

In order to combat noise and reverberation more effectively for TDE in acoustic environments, it makes more sense to take into account of the statistical model of the received noisy speech signals. In [10], it was proved that the LD was the best model for speech samples during voice activity intervals compared with the Gaussian distribution (GD), generalized Gaussian distribution (GGD), and gamma distribution. However, as mentioned in [8], since the additive noise in the signal model was assumed to be Gaussian, the signal cannot be exactly modeled by LD. Thus, the performance of the Laplacian entropy (LE) based method is limited in real adverse acoustic environment[11], where the noise is usually known to be Gaussian. Additionally, in many other applications, it may not be feasible to find a certain density to characterize the distribution of the source signal.

With no prior distribution given about the source signal, the joint entropy of multichannel outputs can be estimated by estimating the joint probability density function (PDF) firstly. One of the most effective ways of PDF estimation is to use a continuous kernel-based density estimator, which is more accurate than the popular histogram estimator[12]. In this paper, we use the Parzen window density estimator[13]with a Gaussian kernel to estimate the joint density of the multichannel outputs. Based on the Parzen window estimator, Renyi’s quadratic entropy (RQE)[14]is incorporated to reduce the computational complexity of entropy estimation. Furthermore, a modified form of the joint entropy is utilized to embed information about reverberation, which enhances the estimator’s robustness against reverberation.

The paper is organized as follows. Section 2 presentsthe basic concept of TDE by minimizing entropy. Section 3 details the proposed entropy estimation methodology for TDE. Section 4 describes how to modify the TDE algorithm to be more robust against reverberation. Simulations are presented in Section 5. Section 6 summarizes the conclusions of the paper.

2. TDE via Minimizing Entropy

2.1 Shannon’s Entropy

In general, the entropy is an information-theoretic measure of uncertainty of a random variable. Shannon, using an axiomatic approach[15], defined the entropy of a random variablexwith a PDFf(x) as

Let us now considerMrandom variables

with the joint densityf(x), wheredenotes a vector/matrix transpose. The corresponding joint entropy of theMrandom variables can be considered to be the entropy of the single vector-valued random variableX:

2.2 TDE via Minimum Shannon’s Entropy

In an attempt to estimate only one time delay, two sensors are enough. However, it has been shown in [7] and [8] that using more than two sensors can help to significantly improve the estimator by taking advantage of the redundant information.

Suppose that we have anM-element linear microphone array positioned arbitrarily in an acoustical enclosure. When the reverberation is ignored, the received signals from a single far-field source can be denoted as

In other scenarios with linear but non-equispaced or nonlinear arrays, the mathematical formulation ofcan be determined depending on the array geometry. Moreover, we assume that the sampling rate was sufficiently high such that the values ofcan be treated as integers.

However, the model described by (4) fails to include the effect of reverberation in real room acoustic environments. To describe the TDE problem in a room environment where each microphone often receives a large number of echoes due to reflections of the wavefront from objects and room boundaries, we can use a more realistic reverberation model[16]which models the received signals as

wherehmdenotes the reverberant impulse response between the source and themth microphone and the symbol ?denotes convolution. In this model,hmcontains not only the effect of the direct path delay but also that of other reflected path delays.

According to the signal model (4), we consider the following vector:

Intuitively, when we determine the delay, the signal components at different microphones will be synchronized, and the entropy ofwill be minimum. This observation is the basis of the entropy based TDE algorithm. In [8], the LE-based method was proposed by modeling the speech signal as LD and minimizing the Shannon’s entropy of

3. TDE via Entropy Estimation

Although assuming a certain distribution density of the source signal may simplify the derivation of signal processing algorithms in many applications, it is more advisable to recognize that a specific density may not be found for the source signal in some applications. In this section, we present a new TDE algorithm based on a combination of a nonparametric PDF estimator and a procedure to compute entropy, which does not require any information about the prior distribution of the source signal.

The PDF is required to estimate the entropy. One of the most popular ways is to use a histogram as a PDF estimator, which is feasible in a 2-dimensional data space. However, there are problems in a high-dimensional data space because of its degraded estimation accuracy and the exponentially increased requirement of calculation with the number of dimensions.

Continuous kernel-based density estimators can avoid the above problems. Given a set ofKdata samplesof theM-dimensional variablewhere, the data PDF ofxkcan be estimated by the Parzen window method[13]using a Gaussian kernel:

where

is the Gaussian kernel in theM-dimensional space;Γdenotes the covariance matrix of the sample data andhis the kernel bandwidth. In this paper, we use the fixed-width kernel density estimator and determinehusing the Silverman’s method[17], i.e.,

However, with continuous kernel based PDF estimators, the integral operation in Shannon’s entropy (3) poses a major computational difficulty. In [14] the RQE (11) was developed

It has been shown that, the integration in (11) can be simplified to summation by using the property of Gaussian function[14]:

In this way, by substituting (9) into (11), the RQE ofxcan be computed efficiently as

The RQE is just one example of the generalized entropy measures and it is equivalent to Shannon’s entropy for the goal of entropy minimization[18]. When the signal components at different microphones are synchronized, the RQE of thewill be minimization. Thus, the relative delay can be estimated by minimizing the RQE

In practice, suppose that we haveLobservations ofx(k), of which onlyK-point subframes are used for each searched value in the searching range of the relative delay. Here,, we can, thus, shift or delaysamples via using the redundant samples. Firstly, we estimate the covariance matrixSecondly, with the estimated covariance matrix, the observed dataare transformed to be. In the data transformation, we can utilize that, whereUandDare the eigenvector matrix and the diagonal eigenvalue matrix of the covariance matrix, respectively. Then, we compute the RQE with (13) for differentand choose the one that minimizesto be the optimal estimate of the relative delay.

4. Modified Entropy of Multichannel Outputs

For TDE techniques using two sensors, it has been shown in [19] that the estimator searching the relative delay by directly maximizing the mutual information suffers from the same limitations as GCC and its phase transform (PHAT) variant, and it would not be robust enough in multipath environments. The authors proposed a way of embedding information about reverberation to get more robust and consistent estimations.

Suppose that the relative delay between the two signalsx1(k) andx2(k) is τ. In the absence of reverberation, only a single delay is present between the two signals. Thus, the information contained in a sampleiofx1(k) is only dependent on the information contained in the samplei?τ ofx2(k). When reverberation is present, then, the information contained in a sampleiofx1(k) is also contained in neighboring samples of the samplei?τ ofx2(k). Therefore, the entropy (13) is not representative enough in the presence of reverberation. The same logical argument applies to the samples ofx2(k). Thus, in order to better estimate the information conveyed by the two signals, the modified joint entropy that considers jointlyQneighboring samples can be formulated as[19]

When the condition of using multiple sensors is considered, accordingly, the modified RQE ofcan be formulated as

with

The computational burden of the proposed algorithm is compared with its LE-based and MCCC counterparts as following. We investigate the computational complexity in terms of the required number of arithmetic operations (multiplications, divisions, additions, and subtractions) for each searched delay by estimating the cost function of each algorithm. For each searched delay, the LE-based, MCCC, and the proposed algorithms require approximately, andoperations, respectively, whereObviously, the proposed algorithm has a much higher computational burden than its two counterparts and it is not suitable for the implementation with large data sample sizeK. In the comparison, the exponential function exp(?), natural logarithm ln(?), and Bessel function are ignored, for these functions can be implemented using simple and fast look-up table methods.

5. Simulations

The image model technique[20]and its improved version[21]are used to simulate real reverberant acoustic environments of a rectangular room with the following parameters: the simulated room dimensions are (7 m, 6 m, 3 m); a linear microphone array which consists of six ideal point receivers is simulated, the first microphone is located at (6 m, 5.8 m, 1.5 m), and the sixth at (6.5 m, 5.8 m, 1.5 m); the source is located at (1.6 m, 2 m, 1.6 m). Two reverberation conditions are simulated for different reverberationT60time, which is defined as the time period for the sound to decay to a level 60 dB below its original level[22]. The two reverberation time period are approximately 180 ms and 360 ms, respectively.

Fig. 1. RMSE versus orderQfor the two reverberation conditions, SNR=20 dB.

A real female speech signal sampled atf=22 kHz is convolved with the low-pass sampled room impulse responses to generate microphone signals. The microphone signals are partitioned into non-overlapping frames with a frame size of 40 ms (L=880 samples). The true relative delay between the first two microphone signals is approximately five samples. Mutually independent zero-mean white Gaussian noise is added to each signal to control the signal to noise ratio (SNR).

For each set of noise and reverberation conditions, 100 frames are processed to generate 100 estimates. The used signal block size is 20 ms ( 440K= samples). The TDE performance is investigated in terms of the average root mean-squared error (RMSE) of the estimates. The RMSE is defined as

We first examine the effect of the system orderQon the performance of the RQE-based estimator. Fig. 1 presents the RMSE for varyingQin the two reverberant environments. The noise level is SNR=20 dB. As clearly shown in Fig. 1, the RMSE decreases asQincreases, which can be explained as that the entropy estimation becomes more accurate.

In the second experiment, the LE-based, MCCC, and RQE-based approaches are compared in various noisy and reverberant environments. Fig. 2 depicts the relationship between the RMSE and SNR for all the three approaches with different numbers of microphones (M=2, 4, and 6) in the two simulated reverberation conditions. The SNR varies from ?5 dB to 25 dB. The system order of the RQE-based method is chosen to beQ=4. It can be clearly seen that, the performance of all the three methods degrades as either the SNR decreases or the reverberation time increases. For example, for each of the estimators with a fixed number ofmicrophones in the same SNR condition, the RMSE for the reverberation timeT60=360 ms are more than three times that forT60=180 ms in most cases. But the robustness against noise and reverberation can be improved for each algorithm by employing more microphones.

Fig. 2. RMSE of the LE-based, MCCC, and RQE-based algorithms for varying SNR in the two reverberation conditions with different numbers of microphones: (a)M=2, (b)M=4, and (c)M=6.

In general, for the same number of microphones, and the same noise and reverberation conditions, the proposed RQE-based algorithm with an order ofQ=4 shows better performance compared with its LE-based and MCCC counterparts when the SNR is relatively high (more than 15 dB), which is demonstrated by its distinct lower RMSE. When the SNR is relatively low, it performs comparably to MCCC but better than the LE-based algorithm. One would wonder, why the LE-based method deteriorates dramatically at low SNR (e.g., below 0 dB in the experiment). This can be explained as follows. As mentioned in [8], since the additive noise was typically Gaussian, the noisy microphone output, which was a mixture of Laplacian and Gaussian random variables, could not be well modeled by LD, particularly when the noise was high, which leaded to a rapid increase of error in the LE estimation.

6. Conclusions

In this paper, we have introduced a multichannel time delay estimator which searches the relative delay by minimizing the estimated joint entropy of multichannel output signals. The Parzen window density estimator is combined with the RQE to effectively and efficiently estimate the high-dimensional entropy. Moreover, a modified form of the entropy is utilized to enhance the estimator’s robustness against reverberation. The performance of the proposed approach is demonstrated by TDE experiments for speech signals compared with the LE-based and MCCC approaches in various noise and reverberation conditions. Although the proposed algorithm has high computational complexity compared with its two counterparts, it would be preferable in some applications since it does not require any information about the prior distribution of the source signal.

[1] H. Wang and P. Chu, “Voice source localization for automatic camera pointing system in videoconferencing,” inProc. of IEEE ASSP Workshop on Applications of Signal ProcessingAudioAcoustics, New Paltz, doi: 10.1109/ASPAA.1997.625639

[2] Y. Huang, J. Benesty, and G. W. Elko, “Microphone arrays for video camera steering,” inAcoustic Signal Processing for Telecommunication, S. L. Gay and J. Benesty, Eds. Norwell: Kluwer, 2000, ch. 11, pp. 239–259.

[3] M. Brandstein and D. Ward,Microphone Arrays, Berlin: Springer, 2001.

[4] C. H. Knapp and G. C. Carter, “The generalized correlation method for estimation of time delay,”IEEE Trans. on Acoustics,Speech,and Signal Processing, vol. 24, no. 4, pp. 320–327, Aug. 1976.

[5] J. P. Ianniello, “Time delay estimation via cross-correlation in the presence of large estimation errors,”IEEE Trans. onAcoustics,Speech,and Signal Processing, vol. 30, no. 6, pp. 998–1003, Dec. 1982.

[6] B. Champagne, S. Bédard, and A. Stéphenne, “Performance of time-delay estimation in presence of room reverberation,”IEEE Trans. on Speech and Audio Processing, vol. 4, no. 2, pp. 148–152, Mar. 1996.

[7] J. Chen, J. Benesty, and Y. Huang, “Robust time delay estimation exploiting redundancy among multiple microphoens,”IEEE Trans. on Speech and Audio Processing, vol. 11, no. 6, pp. 549–557, 2003.

[8] J. Benesty, J. Chen, and Y. Huang, “Time delay estimation via minimum entropy,”IEEE Signal Processing Letters, vol. 14, no. 3, pp. 157–160, Mar. 2007.

[9] T. M. Cover and J. A. Thomas,Elements of Information Theory, New York: Wiley, 1991.

[10] S. Gazor and W. Zhang, “Speech probability distribution,”IEEE Signal Processing Letters, vol. 10, no. 7, pp. 204–207, Jul. 2003.

[11] F. Wen and Q. Wan, “Robust time delay estimation for speech signals using information theory: A comparison study,”EURASIP Journal on Audio,Speech,and Music Processing, doi:10.1186/1687-4722-2011-3.

[12] M. Young, B. Rajagopalan, and U. Lall, “Estimation of mutual information using kernel density estimators,”Physical Review E, vol. 52, no. 3, pp. 2318–2321, 1995.

[13] E. Parzen, “On estimation of a probability density function and mode,”The Annals of Mathematical Statistics, vol. 33, no. 3, pp. 1064–1076, 1962.

[14] J. C. Principe, D. Xu, and J. Fisher III, “Information theoretic learning,” inUnsupervised Adaptive Filtering, S. Haykin, Ed. New York: Wiley, 2000, pp. 265–320.

[15] C. E. Shannon, “A mathematical theory of communication,”The Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, 623–656, 1948.

[16] J. Chen, Y. Huang, and J. Benesty, “Time delay estimation in room acoustic environments: An overview,”EURASIP JournalonAppliedSignalProcessing, doi: 10.1155/ASP/2006/26503.

[17] B. W. Silverman,Density Estimation for Statistics and Data Analysis, London: Chapman & Hall, 1986.

[18] J. N. Kapur,Measures of Information and TheirApplications, New York: Wiley, 1994.

[19] F. Talantzis, A. G. Constantinides, and L. C. Polymenakos,“Estimation of direction of arrival using information theory,”IEEE Signal Processing Letters, vol. 12, no. 8, pp. 561–564, Aug. 2005.

[20] J. B. Allen and D. A. Berkley, “Image method for efficiently simulating small-room acoustics,”Journal of the Acoustical Society of America, vol. 65, no. 4, pp. 943–950, 1979.

[21] P. M. Peterson, “Simulating the response of multiple microphones to a single acoustic source in a reverberant room,”Journal of the Acoustical Society of America, vol. 80, no. 5, pp. 1527–1529, 1986.

[22] M. R. Schroeder, “New method for measuring reverberation time,”Journal of the Acoustical Society of America, vol. 37, no. 3, pp. 409–412, 1965.

Fei Wen was born in Sichuan, China in 1983. He received the B.S. and M.S. degrees in communications and information engineering from University of Electronic Science and Technology of China (UESTC) in 2006 and 2010, respectively. He is currently pursuing the Ph.D. degree in communications and information engineering with UESTC, Chengdu, China. His main research interests include statistical signal processing, communications, and estimation theory.

ceived the B.S. degree from Nanjing University in 1993, and the M.S. and Ph.D degrees from UESTC in 1996 and 2001, respectively. During 2001 to 2002, he worked as a post-doctor at Tsinghua University, where he participated in the cellular localization program. Since 2004, he has been a professor with the Department of Electronic Engineering, UESTC. His research interests include sparse and array signal processing and mobile and indoor localization. He is a Senior Member of CIE.

Manuscript

July 4, 2012; revised August 6, 2012. This research was supported by the National Natural Science Foundation of China under Grant No. 61172140, and ‘985’ Key Projects for Excellent Teaching Team Supporting (postgraduate) under Grant No. A1098522-02.

F. Wen is with School of Electronic Engineering, University of Electronic Science and Technology, Chengdu 611731, China (e-mail: wenfee@126.com).

Q. Wan is with School of Electronic Engineering, University of Electronic Science and Technology, Chengdu 611731, China (Corresponding author e-mail: wanqun@uestc.edu.cn).

Digital Object Identifier: 10.3969/j.issn.1674-862X.2013.03.003