Measuring Dependence of Bin-wise Separated Signals for
Permutation Alignment in Frequency-domain BSS
Hiroshi Sawada

Shoko Araki

Shoji Makino

NTT Communication Science Laboratories, NTT Corporation
2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237, Japan
Email: {sawada,shoko,maki}@cslab.kecl.ntt.co.jp

Abstract— This paper presents a new method for grouping bin-wise
separated signals for individual sources, i.e., solving the permutation
problem, in the process of frequency-domain blind source separation.
Conventionally, the correlation coefficient of separated signal envelopes
is calculated to judge whether or not the separated signals originate
from the same source. In this paper, we propose a new measure that
represents the dominance of the separated signal in the mixtures, and use
it for calculating the correlation coefficient, instead of a signal envelope.
Such dominance measures exhibit dependence/independence more clearly
than traditionally used signal envelopes. Consequently, a simple clustering
algorithm with centroids works well for grouping separated signals.
Experimental results were very appealing, as three sources including
two coming from the same direction were separated properly with the
new method.

I. I NTRODUCTION
For acoustic applications of blind source separation (BSS) or
independent component analysis (ICA) [1]–[3], such as solving a
cocktail party problem, signals are generally mixed in a convolutive
manner with reverberations. Let s1 , . . . , sN be source signals andx1 , . . . , xM be sensor observations. The convolutive mixture model
is formulated asxj (t) =

N


k=1

hjk (l) sk (t − l), j = 1, . . . , M ,(1)lwhere t represents time and hjk (l) represents the impulse response
from source k to sensor j. In a practical room situation, impulse
responses hjk (l) can have thousands of taps even with an 8 kHz
sampling rate. This makes the convolutive BSS problem harder tosolve compared with that of simple instantaneous mixtures.
Many methods have been proposed [4]–[14] for solving the convolutive BSS problem. Among them, we consider the frequency-domain
approach [6]–[14], where we apply a short-time Fourier transform(STFT) to the sensor observations xj (t). In the frequency domain,
the convolutive mixture (1) can be approximated as an instantaneous
mixture at each frequency:
xj (n, f ) =N

hjk (f )sk (n, f ), j = 1, . . . , M,

(2)

k=1

where n represents the time frame index, f represents frequency,
hjk is the frequency response from source k to sensor j, andsk (n, f ) is the time-frequency representation of a source signal sk .
A filtering operation for generating separated signals is performed ineach frequency bin f , and then an inverse STFT is applied to the binwise separated signals to construct time-domain separated signals.
In order to construct proper separated signals in the time domain, frequency-domain separated signals originating from the same
source should be grouped together. This problem is known as the
permutation problem of frequency-domain BSS, and various methods
have been proposed for its solution. Early work [6], [7] considered

1-4244-0921-7/07 $25.00 © 2007 IEEE.

STFT

ISTFT

Separation

Fig. 1.

Permutation

Scaling

System structure for frequency-domain BSS

the smoothness of the frequency responses of the separation filters.
Spatial information, such as the direction-of-arrivals of sources, canalso be estimated and used [10]–[12]. For non-stationary sources
such as speech, many methods [8]–[10], [13], [14] exploit thedependence of separated signals across frequencies. Of these, thispaper considers the methods that employ two-stage processing [9],[10] where separation is first completed in each frequency bin by
any BSS or ICA algorithm and then bin-wise separated signals aregrouped together by measuring their dependence. This contrasts withthe other methods [8], [13], [14] where the separation matrix in eachfrequency bin is adaptively updated according to the dependence ofbin-wise signals across frequencies.
This paper discusses how to evaluate the dependence of frequencydomain separated signals. Conventionally, the correlation coefficientof separated signal envelopes has been utilized [8]–[10]. Section III
reviews the conventional method, and points out the drawbackof using signal envelopes. Then, we propose a new measure inSec. IV, which has good characteristics that help to represent dependence/independence more clearly. Section V presents two optimization methods for grouping bin-wise separated signals based on
the above measure. The experimental results shown in Sec. VI arevery encouraging. Section VII concludes this paper.
II. F REQUENCY- DOMAIN BSS
This section presents an overview of frequency-domain BSS, which
we consider in this paper. Figure 1 shows the system structure.
First, sensor observations (1) sampled at frequency fs are converted
into frequency-domain time-series signals (2) by a short-time Fouriertransform (STFT) with an L-sample frame and its S-sample shift:xj (n, f ) ←t

xj (t) win(t−n fSs ) e−ı2πf t ,(3)1
f , . . . , L−1fs } and for frame
L s
Lfor all discrete frequencies f ∈ {0,indexes n. The window win(t) is defined as non-zero only in the Lsample interval [− L2 f1s , ( L2 −1) f1s ] and preferably tapers smoothly
to zero at each end of the interval.
Next, separation is performed in each frequency bin f ∈ F:
y(n, f ) = W(f ) x(n, f ),(4)

where x = [x1 , . . . , xM ]T is the vector of observations, y =[y1 , . . . , yN ]T is the vector of separated signals, and W is an N ×M

3247

separation matrix. The set of frequencies F where the separation
operation is performed can be limited toxj (n, mf ) = x∗j (n, L−mfs ) ,L s
L

m = 1, . . . , L2 −1 .

Frequency (kHz)1
F = {0, . . . , fs }2
due to the relationship of the complex conjugate:

|y |

(5)

(6)

x(n, f ) = A(f ) y(n, f ) =

6

2

4
2

1

0
0.5

Frequency (kHz)(7)

If W has the inverse, the matrix is given simply by A = W−1 .
Otherwise it is calculated as a least-mean-square estimator

2

2.5

8

3

6

2

4
2

1

0
0.5

1

(8)

i=1

1.5
|y2|

0

ai (f )yi (n, f ) .

1

4

in order to represent the vector x by a linear combination of the basis
vectors:
N


8
3

0

We can apply any instantaneous BSS/ICA algorithm [1]–[3] for the
calculation of W. Then, we calculate a matrix A whose columns arebasis vectors ai ,A = [a1 , · · · , aN ], ai = [a1i , . . . , aM i ]T ,

1

4

1.5
Time (sec)2

2.5

Fig. 2.
Separated signal envelopes, normalized to zero mean and unit
variance.

A = E{xyH }(E{yyH })−1 ,|y | and |y |1

|y | and |y |

1

1

2

1

4

3

0.5

3

0.5

2

0

2

0

1

−0.5

1

−0.5

−1

0
0

1

4

3

0.5

3

0.5

2

0

2

0

1

−0.5

1

−0.5

−1

0
0

4

1

2

i = Πf (k)Frequency (kHz)which minimizes E{||x − Ay|| }.
If the separation works well, we can expect the bin-wise separated
signals y1 (n, f ), . . . , yN (n, f ) to be close to the original source signals s1 (n, f ), . . . , sN (n, f ) up to permutation and scaling ambiguity.
The use of different subscripts in (2) and (8), i and k, indicatesthe permutation ambiguity. They should be related by a permutation
Πf : {1, . . . , N } → {1, . . . , N } for each frequency bin f as

0
0

(9)

4
Frequency (kHz)so that the separated components yi originating from the same source
sk are grouped together. The following sections will describe aprocedure for deciding permutations Πf . After Πf are decided, theseparated signals and the basis vectors are updated byyk (n, f ) ← yΠf (k) (n, f ), ak (f ) ← aΠf (k) (f ), ∀ k, n, f. (10)Next, the scaling ambiguity is aligned by adjusting yk (n, f ) to theobservation xJ (n, f ) of a selected reference sensor J ∈ {1, . . . , M }:yk (n, f ) ← aJ k (f )yk (n, f ), ∀ k, n, f.

(11)

We see in (8) that aJ k (f )yk (n, f ) is a part of xJ (n, f ) that originatesfrom source sk .
Finally, time-domain output signals yk (t) are calculated with aninverse STFT (ISTFT) of the separated signals yk (n, f ).
III. C ONVENTIONAL MEASURE FOR DEPENDENCE
The correlation coefficient of bin-wise separated signal envelopes
has been used [8]–[10] for measuring their dependence, and solving
the permutation problem. The envelope of a bin-wise separated signal
yi is calculated byvif (n) = |yi (n, f )| .
(12)
It is real-valued and represents the signal activity. The correlation
coefficient ρ between two real-valued sequences vi (n) and vj (n) is
defined as
rij − µi µj(13)
ρ(vi , vj ) =
σi σj
where
rij = E{vi vj }, µi = E{vi }, σi =E{vi2 } − µ2i

0
0

2

4

|y2| and |y1|2
Frequency (kHz)

4

2

4

|y2| and |y2|2Frequency (kHz)

−1

1

4

−1

Fig. 3. Correlation coefficients between the separated signal envelopes shownin Fig. 2.

are the correlation, the mean, and the standard deviation, respectively.
For any two sequences vi and vj , the correlation coefficient isbounded by −1 ≤ ρ(vi , vj ) ≤ 1 , and becomes 1 if the two sequences
are identical.
We expect the correlation coefficient ρ(vif , vkg ) of bin-wise separated signal envelopes to be high if they come from the same
source. However, such a tendency is not always the case, andmostly can be seen only when the frequencies f and g are close
together, or in a harmonic relationship such as f ≈ 2g. Here isan example. Figure 2 shows the envelopes of successfully separated
speech signals. Figure 3 shows the correlation coefficients between
these envelopes. We observe that there are many frequency pairs f
and g such that the envelopes are almost uncorrelated even if they
belong to the same source: ρ(v1f , v1g ) ≈ ρ(v2f , v2g ) ≈ 0. This is due tothe wide dynamic range of speech signals even if they are normalized
to zero mean and unit variance, and active signals are represented withvarious values. This indicates the drawback of using signal envelopes.

3248

powRatio

IV. P ROPOSED NEW MEASURE
Frequency (kHz)Instead of using envelopes (12) for calculating correlation coefficients (13), we propose using another type of measure that represents
the dominance of the i-th separated signal in the observations. An
example of such a measure is the power ratio between the i-th
separated signal and the total power sum of the all separated signals:.

vif (n) = powRatioi (n, f )ρ(vif , ck ) i=Π (k) .
f(16)

The centroid ck is calculated for each source as the average value ofthe measure (15) with the current permutation Πf :ck (n) ←|F|vi (n) f ∈F

i=Πf (k), ∀ k, n ,(17)where |F| is the number of elements in the set F. The permutations
Πf are optimized to maximize the correlation coefficients ρ between
the measures (14) and the current centroid:Πf ← argmaxΠ

N




1

1.5

2

0

2.5

2

1

3
2

0.5

1
0.5

1

1.5
Time (sec)

2

0

2.5

Fig. 4. The powRatioi values for the same separated signals whose envelopes
are shown in Fig. 2.
powRatio and powRatio
1

powRatio and powRatio
1

2

4

3

0.5

3

0.5

2

0

2

0

1

−0.5

1

−0.5

−1

0
0

1

4

3

0.5

3

0.5

2

0

2

0

1

−0.5

1

−0.5

−1

0
0

0
0
4
Frequency (kHz)

1

1

4

2

4

powRatio2 and powRatio1002Frequency (kHz)

4

2

4

powRatio2 and powRatio2

2
Frequency (kHz)

4

1

−1

1

−1

Fig. 5. Correlation coefficients between the powRatioi values shown in Fig. 4.

This section presents two optimization techniques for permutationalignment. The first technique is rough global optimization, which
maximizes the cost function

1  f

0.5

0

(15)

V. O PTIMIZATION

f ∈F k=1

1

powRatio

instead of envelopes (12) for calculating correlation coefficients (13).
Figure 5 shows the correlation coefficients between such values. We
see that the correlation coefficients are high for the same source more
often than those in Fig. 3. Moreover, the correlation coefficients tend
to be negative for different sources, due to the exclusive property
mentioned above.
In summary, we can measure the dependence of bin-wise separated
signals yi more clearly by calculating correlation coefficients ρ with
powRatioi values (14) rather than with envelopes |yi | (12).

N


0.5

4

It is in the range 0 ≤ powRatioi ≤ 1 by definition. It is close to 1 if
the i-th signal term ai (f )yi (n, f ) is dominant in the decomposition(8) of the mixtures x(n, f ). In contrast, it is close to 0 if othersignals ai (f )yi (n, f ) are dominant. For speech signals, there aremany cases where one signal is dominant due to their sparsenessproperty.
Figure 4 shows the powRatioi values for the same separated signals
as those shown in Fig. 2. Two characteristics should be stressed
here. First, the dynamic range of the value is bounded, and active
signals are uniformly represented with values close to 1. Second,the values of different sources are exclusive to each other, i.e., if
powRatio1 (n, f ) is close to 1, then powRatio2 (n, f ) is close to 0.
These two characteristics help us to measure the dependence clearly,
as demonstrated below.
Let us here employ

J ({ck }, {Πf }) =2

(14)
Frequency (kHz)||ak (f ) yk (n, f )||2

Frequency (kHz)

k=1

1

3

0

||ai (f ) yi (n, f )||2

powRatioi (n, f ) = N

1

4

ρ(vif , ck ) i=Π(k) , ∀ f ∈ F .

(18)

The second technique is for fine local optimization. It maximizes
the sum of the correlation coefficients over a set of selected frequencies R(f ) for a frequency f :Πf ← argmaxΠg∈R(f ) k=1

ρ(vif , vig ) i=Π(k),i =Π (k) .
g(19)

The set R(f ) preferably consists of frequencies g where a highcorrelation coefficient ρ(vif , vkg ) would be attained for vif and vig
corresponding to the same source. We typically select adjacentfrequencies A(f ) and harmonic frequencies H(f ) so that R(f ) =A(f ) ∪ H(f ). For example, A is given byA(f ) = {f −3∆f, f −2∆f, f −∆f, f +∆f, f +2∆f, f +3∆f }where ∆f = L1 fs , and H is given byH(f ) =

{round (f /2)−∆f, round (f /2), round (f /2)+∆f,
2f −∆f, 2f, 2f +∆f }k=1

These two operations (17) and (18) are iterated until convergence.

N 

where round (·) selects the nearest frequency to · from the set F.

3249

1.1 m120°

Microphones
On edges of 4cm triangle

45°

14

Source signals:
speeches of 3 s
Sampling rate:
8 kHz
Frame size of STFT:
1024 points (128 ms)
Frame shift of STFT:
256 points (32 ms)
Room size:
4.45 × 3.55 × 2.5 m
Reverberation time:
RT60 = 200 ms

SIR improvement (dB)

Loudspeaker

1.7 m

12
10
8
6
4
Average of 8 cases
Each case2
Env(Lo)Fig. 6.

Fig. 7.

Experimental conditions

The fine local optimization (19) is performed for a selected
frequency f at a time, and repeated until no improvement is foundfor any frequency f .
VI. E XPERIMENTS
We performed experiments to separate three speech sources withthree microphones. We measured impulse responses hjk (l) under
the conditions shown in Fig. 6. Under this condition, two sources
came from the same direction, and the sensor spacings were small.
Thus, it was hard to exploit the spatial information of sources for
permutation alignment as considered in [10]–[12]. Mixtures at the
microphones were made by convolving the impulse responses and3-second English speeches. The computational time was around 3
seconds for 3-second speech mixtures. The program was coded in
Matlab and run on Athlon 64 FX-53. The separation performance was
evaluated in terms of signal-to-interference ratio (SIR) improvement.
The improvement was calculated by OutputSIRi − InputSIRi foreach output i, and we took the average over all outputs. These two
types of SIRs are defined by | l hJ i (l)si (t − l)|2t
InputSIRi = 10 log10  | k=i l hJ k (l)sk (t − l)|2t
OutputSIRi = 10 log10 |yii (t)|2
t


t

|

k=i

yik (t)|2

Env(Gl)Env(Gl+Lo) PoR(Lo)PoR(Gl) PoR(Gl+Lo) Optimal

Permutation alignment method

Height of microphones and loudspeakers: 1.2 m

(dB),

(dB),

where J ∈ {1, . . . , M } is the index of one selected reference sensor,
and yik (t)Nis the component of sk that appears at output yi (t), i.e.
yi (t) = k=1 yik (t).
Experiments were conducted with 8 combinations of 3 speeches.
Figure 7 shows the average SIR improvements obtained with several
permutation alignment methods. The abbreviations “Env” and “PoR”
indicate the methods using conventional [8]–[10] envelopes |yi |in (12) and the proposed dominance measure powRatioi in (14),respectively. The abbreviations “Gl” and “Lo” correspond to therough global optimization and the fine local optimization presented
in Sec. V, respectively. The entry “Optimal” represents the resultswith the optimal permutations calculated with a knowledge of theoriginal source signals.
We observe the following. The rough global optimization “Gl”
works well with the new measure “PoR”, but not with the conventional measure of envelopes “Env”. The fine local optimization “Lo”
alone does not provide good results for either “Env” and “PoR”. Its
effectiveness can be seen in improving the moderately good solutions
obtained by the global optimization “Gl”. The proposed method“PoR(Gl+Lo)” achieved almost optimal results.

SIR improvements with several permutation alignment methods.

VII. C ONCLUSION
This paper presented a novel method for solving the permutation
problem of frequency-domain BSS. The newly proposed dominancemeasure (14) represents the activity of a separated signal yi with thefavorable characteristics described in Sec. IV. Thanks to these characteristics, the dependency of separated signals is clearly measured
by using correlation coefficients (13). This allows the effective use of
the global optimization technique proposed in Sec. V. The proposed
method worked surprisingly well in the experiments, as two sources
coming from the same direction were separated in a real room.
R EFERENCES[1] T.-W. Lee, Independent Component Analysis - Theory and Applications.
Kluwer Academic Publishers, 1998.
[2] A. Hyvärinen, J. Karhunen, and E. Oja, Independent Component Analysis. John Wiley & Sons, 2001.
[3] A. Cichocki and S. Amari, Adaptive Blind Signal and Image Processing.
John Wiley & Sons, 2002.
[4] S. C. Douglas, H. Sawada, and S. Makino, “A spatio-temporal FastICAalgorithm for separating convolutive mixtures,” in Proc. ICASSP 2005,
vol. V, Mar. 2005, pp. 165–168.
[5] W. Kellermann, H. Buchner, and R. Aichner, “Separating convolutive
mixtures with TRINICON,” in Proc. ICASSP 2006, vol. V, May 2006,
pp. 961–964.
[6] P. Smaragdis, “Blind separation of convolved mixtures in the frequency
domain,” Neurocomputing, vol. 22, pp. 21–34, 1998.
[7] L. Parra and C. Spence, “Convolutive blind separation of non-stationary
sources,” IEEE Trans. Speech Audio Processing, vol. 8, no. 3, pp. 320–
327, May 2000.
[8] J. Anemüller and B. Kollmeier, “Amplitude modulation decorrelation forconvolutive blind source separation,” in Proc. ICA 2000, June 2000, pp.
215–220.
[9] N. Murata, S. Ikeda, and A. Ziehe, “An approach to blind source separation based on temporal structure of speech signals,” Neurocomputing,vol. 41, pp. 1–24, Oct. 2001.
[10] H. Sawada, R. Mukai, S. Araki, and S. Makino, “A robust and precise
method for solving the permutation problem of frequency-domain blindsource separation,” IEEE Trans. Speech Audio Processing, vol. 12, no. 5,
pp. 530–538, Sept. 2004.
[11] H. Saruwatari, S. Kurita, K. Takeda, F. Itakura, T. Nishikawa, andK. Shikano, “Blind source separation combining independent component analysis and beamforming,” EURASIP Journal on Applied Signal
Processing, vol. 2003, no. 11, pp. 1135–1146, Nov. 2003.
[12] R. Mukai, H. Sawada, S. Araki, and S. Makino, “Frequency domain
blind source separation using small and large spacing sensor pairs,” inProc. ISCAS 2004, vol. V, May 2004, pp. 1–4.
[13] A. Hiroe, “Solution of permutation problem in frequency domain ICA
using multivariate probability density functions,” in Proc. ICA 2006
(LNCS 3889). Springer, Mar. 2006, pp. 601–608.
[14] T. Kim, H. T. Attias, S.-Y. Lee, and T.-W. Lee, “Blind source separation
exploiting higher-order frequency dependencies,” IEEE Trans. Audio,
Speech and Language Processing, pp. 70–79, Jan. 2007.

3250