NEW ANALYTICAL UPDATE RULE FOR TDOA INFERENCEFOR UNDERDETERMINED BSS IN NOISY ENVIRONMENTS
Takuro Maruyama† , Shoko Araki† , Tomohiro Nakatani† , Shigeki Miyabe , Takeshi Yamada ,Shoji Makino and Atsushi Nakamura†Graduate School of Systems and Information Engineering, University of Tsukuba
1-1-1 Tennoudai, Tsukuba-shi, Ibaraki 305-8573, Japan†NTT Communication Science Laboratories, NTT Corporation
2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237, Japan
Email: maruyama@mmlab.cs.tsukuba.ac.jp
ABSTRACTIn this paper, we propose a new technique for sparsenessbased underdetermined BSS that is based on the clustering of
the frequency-dependent time difference of arrival (TDOA)
information and that can cope with diffused noise environments. Such a method with an EM algorithm has alreadybeen proposed, however, it required a time-consuming exhaust search for TDOA inference. To remove the need forsuch an exhaust search, we propose a new technique by focusing on a stereo case. We derive an update rule for analytical TDOA estimation. This update rule eliminates the needfor the exhaustive TDOA search, and therefore reduces thecomputational load. We show experimental results for separation performance and calculation time in comparison withthose obtained with the conventional approach. Our reported
results validate our proposed method, that is, our proposed
method achieves high performance without a high computational cost.
Index Terms— Underdetermined blind source separation, EM algorithm, speech sparseness, time-frequency
masking
1. INTRODUCTION
Blind Source Separation (BSS) has been intensively investigated since this problem setting matches a real environment
very well. With overdetermined BSS, the source separation
can be performed satisfactorily, especially in a clean environment, for example by using Independent Component Analysis (ICA). To be able to handle a more realistic situation,
however, we must consider the underdetermined case, where
there are fewer sensors than sources.
Many methods have been proposed for underdetermined
BSS [1, 2, 3, 4, 5]. Most of there methods employ thesparseness characteristics of the source signals. The energyof the target signal concentrates on certain time-frequency

978-1-4673-0046-9/12/$26.00 ©2012 IEEE

269

points, which deﬁnes sparseness. In particular with speechin the time-frequency domain, it is approximately true owing to such factors as formants, harmonic structures, andnon-stationarity. If the time-frequency components of eachsource signal are sparse, then these components rarely overlap even when many sources are mixed together [6], andit can be assumed that at most one source is active at eachtime-frequency slot. Time-frequency masking utilizes thissparseness assumption, and aims at extracting the timefrequency components dominated by each source. Such atime-frequency mask can be built by performing a clustering operation on the source location information, such as
the TDOA, at all the time-frequency slots [1, 7]. However,most of the separation methods based on the clustering of thesource location information tend to be weak with respect toreverberation and background noises.
Recently, Izumi et al. [8] proposed a BSS method to
overcome this issue. They also relied on the TDOA for theclustering, however, their method achieved high performanceeven under noisy and reverberant conditions because they
considered the noise and reverberation in their microphoneobservation model. The clustering was performed by using
the EM algorithm, however, there is a serious problem withthis approach, that is, it cannot analytically update the TDOA
parameter. In other words, their method required a timeconsuming exhaust search for the TDOA inference. This
problem has precluded wide use of this approach.
To remove the need for such an exhaust search, we propose a new efﬁcient BSS algorithm. We derive an update rulefor TDOA parameter estimation in Izumi’s algorithm in ananalytical way. The new update rule eliminates the need forthe exhaust search of TDOA, and is therefore expected to reduce the computational load. Our experimental results showthat the proposed method can achieve the comparable performance by greatly reducing the computational time undernoisy and reverberant conditions.

ICASSP 2012

2. CONVENTIONAL METHODThis section outlines the method proposed by Izumi et al. [8]and its problem.
T
Let xf,t = [xf,t,L , xf,t,R ] be signals observed by two microphones represented in the time-frequency domain. If weassume that source signals are sufﬁciently sparse such that
only one source signal is active at each time-frequency point,
and each source signal is transferred as a plane wave, xf,t canbe written as

xf,t,L
xf,t,R=1ej2πf δk

xf,t

=


Sf,t,k +Nf,t,L
Nf,t,Rsinc(2πf D/c)
1p(xf,t |k, θ) =



2π


exp
σf2 |Vf |(3)1− 2 NHV−1 Nf,t,k
2σf f,t,k fLet θ = {σf2 , δk , Sf,t,k } be the parameter set. The log
likelihood function is:


L=
log
p(xf,t |k, θ)p(k|θ)
(5)
f

k


where p(k|θ) is the mixing weight ( k p(k|θ) = 1).
In [8], this log likelihood is maximized with the EM algorithm. The parameters to be estimated are θ = {σf2 , δk , Sf,t,k }where k is the hidden variable and the auxiliary function inthis problem is
Q(θ|θ )==E [log p(xf,t ; θ)|θ ]mk,f,t log p(xf,t |k, θ)p(k|θ)(6)
t

f

1 
−1
mf,t,k NH
f,t,k Vf Nf,t,k
T t

(8)

(2)

(4)

t

The parameters σf2 and Sf,t,k are estimated by differentiating the auxiliary function with respect to each parameter,and setting them at zero,
σf2 =where c is the velocity of sound, and D represents the distance between the two microphones. The purpose of the conventional method [8] and this paper is to estimate the source
signals Sf,t,k solely from the mixed observation xf,t .
The likelihood function for the observation xf,t is
1

(7)

k

bf,k Sf,t,k + Nf,t1sinc(2πf D/c)p(k|θ )p(xf,t |k, θ )mf,t,k = p(k|xf,t,k , θ ) = k p(k|θ )p(xf,t |k, θ )(1)where k is the index of the source, Sf,t,k is the spectrum of
the source signal that is active at a time-frequency slot, bf,k isthe transfer function from the source to the microphones (δkis the TDOA between two microphones), and Nf,t is the observation error, which includes reverberation and backgroundnoise and is assumed to be independent of the source signals.
We assume that N is time-invariant and follows a Gaussian distribution with a zero mean and a covariance matrix
σf2 Vf . Where σ 2 is the noise power, and V is given as follows for the diffused noiseV(f ) =

where time-frequency mask mk,f,t is the posterior probability
that source k is active at a t-f slot, and θ is the parameter set
obtained by the previous iteration. mk,f,t is updated by:k

270

Sf,t,k =−1bH
f,k Vf xf,t−1
bH
f,k Vf bf,kand the mixing weight p(k|θ) (whereculated byp(k|θ) =,(9)k p(k|θ) = 1) is cal-

1 
mf,t,k
TF t

(10)

f

where T and F are the number of time frames and frequency
bins, respectively.
In [8], as δk cannot be solved analytically, the update is
performed by calculating Q(θ|θ ) for all the discretized δkand selecting δk that gives the maximum Q:
δk = argmaxδk Q(θ|θ )(11)This update rule has two problems. One is that the inference of δk should always be discretized. Therefore, theoptimum value tends not to be obtained when using these discretized values. The other problem is that this exhaust searchrequires a large computational cost. To overcome these problems, we derive an analytical update rule for estimating the
TDOA parameter δk .
3. PROPOSED METHOD
In this section, we provide an analytical update rule for the
TDOA parameter δk . By using the components of the vectors
x, b and the matrix V, the likelihood function (4) can be
rewritten as:p(xf,t |k, θ) =
· exp

1

exp C
2π σf2 |Vf ||ξf,t,k ||Sf,t,k |cos(ψs − ψξ − 2πf δf,k )σf2 (1 − φ2 )(12)where φf = sinc(2πf D/c), ξf,t,k = [xf,t,R − φf (xf,t,L −Sf,t,k )], C is independent of δf,k . ψSk and ψξk represent thephases of Sf,t,k and ξf,t,k , respectively.
The last term,
exp|ξf,t,k ||Sf,t,k |cos(ψs − ψξ − 2πf δf,k ) ,σf2 (1 − φ2 )(13)

has the shape of the von Mises distribution [9]:g(x|κ, μ)=1eκ cos (x−μ)
2πI0 (κ)(14)

where −π < x ≤ π, μ is the mean of the distribution (−π <μ ≤ π), κ > 0 is a concentration parameter, and I0 (x) isa modiﬁed Bessel function of the ﬁrst kind and order zero.
That is, (13) means that the phase difference ψs − ψξ ≈arg (xf,t,R )−arg (xf,t,L ) has a von Mises distribution whosemean value corresponds to the frequency-dependent TDOA
μ = 2πf δf,k , and the concentration parameter is the SNR|ξ||Sf,t,k |.
related 1 value κ = f,t,k
σ 2 (1−φ2 )fTherefore, we can derive the update rule for δk using asimilar method with the mixture model of the von Mises distribution. However, because the cosine-part of (13) depends
on the frequency f , we have to derive the update rule for δf,k
at each frequency, which is different from the previous frequency independent update rule (11). By substituting (13)into (6), and by setting ∂δ∂Q
= 0, the update rule becomes:f,k
mf,t,k |ξf,t,k ||Sf,t,k | sin(ψξk − ψSk )2πf δf,k = arctan  tt mf,t,k |ξf,t,k ||Sf,t,k | cos(ψξk − ψSk )(15)
It should be noted that the function arctan(x) is uniqueonly if −π/2 < x < π/2. However, 2πf δf,k can fall inthe −π to π range. Therefore, when |x| ≥ π/2, we have tomodify the estimated value by checking the inﬂection pointof the auxiliary function. To accomplish this, we calculate thesecond order differential of the auxiliary function, and modify
the values as follows:
f,k

2

∂ Q
• If δf,k > 0, ∂(δ2 ) ≥ 0, then 2πf δf,k ← 2πf δf,k − πf,k• Otherwise, we do not modify 2πf δf,kIn summary, the proposed method estimates the parameters σf2 , Sf,t,k and mf,t,k in the same ways as described in
Section 2, and the TDOA parameter δf,k is calculated withthe update rule (15).

the SNR.

f= 0,|ξf,t,k ||Sf,t,k |2 (1−φ2 )σf=4.1. Experimental conditions
We performed experiments with measured impulse responses
in a room (Fig. 1) with a reverberation time of 130 ms. We
used two microphones, whose spacing was 4 cm. The number of sources K was K = 2 (70◦ and 150◦ ), or K = 3(30◦ , 70◦ and 150◦ ). Mixtures were formed by convolving
the measured room impulse responses and 5-second English
speech signals sampled at 8 kHz. The frame size and frame
shift for STFT were 64 ms and 16 ms, respectively.
The noise we used in our experiments was the Gaussian
noise of the zero mean and the covariance matrix of σf2 Vf ,where Vf was given by (3), and σf was determined so thatthe signal to noise ratio (SNR) with respect to source 1 has apreset value.
The performance was evaluated in terms of the signal
to interference-plus-noise ratio (SINR) and the signal-todistortion ratio (SDR) [2]. For each K, 10 speaker combinations were tested and the results were averaged.
We compared the performance and computational timesof the conventional and proposed methods. For the parametersearch with the conventional method, we changed the DOAsof the sources from 0◦ to 180◦ in increments of 1◦ and provided the corresponding TDOA δk . We then performed an
exhaust search according to (11).
4.2. Results
Table 1 shows the experimental results, SINR, SDR and therequired computational time (Intel Xeon X5650 2.67 GHz (6Core), dual).
We can see from Table 1 that our proposed method
achieves a comparable performance to the conventional approach and reduces the computational time by 1/10. This result shows that our proposed method can estimate the TDOA
parameter δk without using an exhaust search as with theconventional method.
4.3. Inﬂuence of noise and reverberation

2∂ Q• If δf,k < 0, ∂(δ2 ) ≥ 0, then 2πf δf,k ← 2πf δf,k + π

1 When we assume that φ

4. EXPERIMENTS|Sf,t,k |2, which is
2
σf

271

To investigate the inﬂuence of noise power and reverberation on separation performance, we also compared the performance and computational times of the conventional andthe proposed methods by changing the SNR and reverberation time.
Table 2 shows the inﬂuence of the SNR on separation performance. The number of sources K was 3 (30◦ , 70◦ and150◦ ), and the other conditions were the same as those in Section 4.1. By adjusting the power of the noise σf2 , the SNR was
set at 27.5 dB (= Table 1. (b)), 20 dB (Table 2. (a)), and 10
dB (Table 2. (b)).
Table 3 shows the inﬂuence of the reverberation time on
separation performance. The number of sources K was 3150o

Reverberation time:
130 msTable 2. Performance under several SNR conditions

Sampling rate:
8000 Hz
4 cm

70 o

SDR
5.4[dB]
5.9[dB]

Calculation Time214.9[s]26.0[s](b) SN R = 10 [dB]
MethodSINR
Conventional 5.3[dB]
Proposed
6.1[dB]SDR
5.4[dB]
5.9[dB]

Calculation Time
231.0[s]29.6[s]o

30

Room size:
4.45 m × 3.55 m × 2.50 m(a) SN R = 20 [dB]
MethodSINR
Conventional 7.6[dB]
Proposed
6.7[dB]

Door

Table 3. Performance under several reverberation conditions

Fig. 1. Experimental setup
Table 1. Source separation results(a) K = 2 (70◦ and 150◦ )SINR
MethodConventional 15.3[dB]
Proposed
14.8[dB]

SDR
6.7[dB]
7.7[dB]

Calculation Time
184.1[s]16.3[s](b) K = 3 (30◦ , 70◦ and 150◦ )SINR
SDR
MethodConventional 7.8[dB] 5.4[dB]
Proposed
6.7[dB] 5.9[dB]

Calculation Time
201.8[s]24.7[s](a) reverberation time = 130 [ms]MethodSINR
SDR
Conventional 13.0[dB] 6.7[dB]
Proposed
11.4[dB] 5.9[dB]

Calculation Time
321.3[s]30.3[s](b) reverberation time = 300 [ms]MethodSINR
SDR
Conventional 7.0[dB] 2.9[dB]
Proposed
6.3[dB] 2.8[dB]

Calculation Time
422.9[s]42.1[s][2] S. Araki and H. Sawada and R. Mukai and S. Makino, “Underdetermined Blind Sparse Source Separation for Arbitrarily
Arranged Multiple Sensors,” Signal Processing, Vol 77, No. 8,
pp 1833-1847, 2007.

(30◦ , 100◦ and 135◦ ), and the other conditions were the sameas those in Section 4.1. The reverberation time was set at 130
and 300 ms.
We can see from Tables 2 and 3 that our proposed method
achieves comparable performance, reducing the computational time, regardless of the SNR and reverberation time.

[3] M. Mandel and D. Ellis and T. Jebara, “An EM algorithm for
Localizing Multiple Sound Sources in Reverberant Environments,” Proc. Neural Info. Proc. Sys. , 2006.
[4] C. Fevotte and S. J. Godsill, “A Bayesian Approach for Blind
Separation of Sparse Sources,” IEEE Transactions on Speech
and Audio Processing, Vol. 14, No. 6, pp 2174-2188, 2006.
[5] H. Sawada and S. Araki and S. Makino, “A Two-stage
Frequency-domain Blind Source Separation Method for Underdetermined Convolutive Mixtures,” Proc. WASPAA2007. ,pp 139-142, 2007.

5. CONCLUSION
This paper proposed a new method for sparse source separation in noisy and reverberant conditions. We provided ananalytical update rule for estimating the TDOA parameter,
which is estimated by using an exhaust search in the conventional approach. We conﬁrmed that our proposed method canachieve comparable performance by reducing the computational time drastically, regardless of the power of noise. We
plan to evaluate our method in a real environment, and to introduce a noise model appropriate for reverberation.

[6] S. Rickard and O. Yilmaz, “On the Approximate W-disjoint
Orthogonality of Speech,” Proc. ICASSP, Vol. I, pp. 529-532,
2002,[7] S. Winter, H. Sawada, S. Araki, and S. Makino, “Overcomplete BSS for Convolutive Mixtures Based on Hierarchical
Clustering,” Proc. SAPA2004, S13, 2004.
[8] Y. Izumi, N. Ono, and S. Sagayama, “Sparseness-based 2ch
BSS using the EM Algorithm in Reverberant Environment,” inProc. WASPAA2007, pp. 147-150, 2007.

6. REFERENCES[1] O. Yilmaz and S. Rickard, “Blind Separation of Speech Mixtures via Time-Frequency Masking,” IEEE Transactions on
Signal Processing, Vol. 52, No. 7, pp 1830-1847, 2004.

[9] C. M. Bishop, “Pattern Recognition and Machine Learning,”
Springer, 2008272