A NOVEL BLIND SOURCE SEPARATION METHODWITH OBSERVATION VECTOR CLUSTERING
Shoko Araki, Hiroshi Sawada, Ryo Mukai, and Shoji Makino
NTT Communication Science Laboratories, NTT Corporation
2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237, Japan{shoko,sawada,ryo,maki}@cslab.kecl.ntt.co.jp
In this paper, we propose a new method for separating
sparse signals from their mixtures. First we normalize
all the observations and cluster the normalized observation vectors (see Eq. (5)). Then, we design time-frequency
binary masks using the clustering result and estimate theseparated signals with the masks. With this approach, we
can exploit the information obtained from all the sensors.
Moreover, we do not need to know the exact sensor locations, simply the maximum distance between a given sensor and any other sensor. This relaxation makes it easy to
use a non-uniform arrangement of sensors, and also eliminates the need for sensor calibration. We show the experimental results obtained in a room (reverberation timeof 130 ms) with non-linear sensor arrays in both a determined and an underdetermined scenarios.
Previously, we have applied the normalization and clustering techniques to the basis vectors produced by ICA [6] inorder to overcome the permutation problem that we facein frequency domain ICA. In contrast, in this paper, wenormalize and cluster the observation vectors themselves
and separate the signals directly.
We also consider the musical noise problem, which usually occurs when we use a time-frequency binary mask.
We confirm that our reported fine-shift and overlap-add
method [7] is also applicable to our observation vector
clustering method to reduce musical noise.

ABSTRACT
We propose a new method for separating sparse signals fromtheir mixtures. Separation is achieved by clustering the normalized observation vectors and extracting each cluster as each separated signal. We show the practical result of speech separation
with non-linear sensor arrangements in both a determined and anunderdetermined scenarios. We also consider the musical noiseproblem and show the listening test results.

1. INTRODUCTION
In this paper, we consider the blind source separation (BSS)of speech signals observed in a real environment, i.e., the
BSS of convolutive mixtures of speech. Recently, independent component analysis (ICA) [1] has been widely
studied for such a BSS problem. However, ICA cannot beapplied when N > M . In contrast, we propose a methodthat can handle both a (over-)determined (N ≤ M ) andan underdetermined (N > M ) cases.
Let us formulate the task. Suppose that sources s 1 , . . . , sN
are convolutively mixed and observed at M sensors
PN P
xj (t) = k=1 l hjk (l) sk (t − l), j = 1, . . . , M, (1)where hjk (l) represents the impulse response from source
k to sensor j. Here we assume that sources s k are sparse
signals, i.e., they have super-Gaussian distributions. For
instance this is true for speech signals. The goal is to obtain the separated signals y k (t) that are estimations of s k
only from the M observations.
There are several approaches [2, 3, 4] that rely on thesparseness of the source signals. If the signals are sufficiently sparse, we can assume that the sources rarely exist
simultaneously. Therefore, we can estimate each sourceby gathering the observation samples that appear to belong to one of the sources. Previously, this was doneby using geometric information (e.g., direction of arrival(DOA) and/or distance) about the sources, which is estimated by the phase and/or level difference between two
observations of a linear sensor array [2, 5]. However, it isdifficult to expand those methods for M ≥ 3. That is, evenif we have M ≥ 3 microphones, the previous methods
cannot utilize all the observation information effectively
and straightforwardly. In addition, the previous methods
needed an exact sensor arrangement and sensor calibration to estimate the geometric features of the sources accurately.

2. PROPOSED APPROACH
2.1. Frequency domain operation
Figure 1 shows the flow of our method. First, time-domain
signals xj (t) sampled at frequency f s are converted intofrequency-domain time-series signals x j (f, τ ) with an Lpoint short-time Fourier transform (STFT):
PL/2−1xj (f, τ ) ← r=−L/2 xj (τ + r) win(r) e−2πf r , (2)where f ∈ {0, L1 fs , . . . , L−1
L fs } is a frequency, win(r)is a window that tapers smoothly to zero at each end, suchas a Hanning window 21 (1+cos 2πr
L ), and τ is a new index
representing time.
The remaining operations are performed in the frequency
domain. There are two advantages to this. First, convolutive mixtures (1) can be approximated as instantaneous
mixtures at each frequency:
PN(3)
xj (f, τ ) ≈ k=1 hjk (f )sk (f, τ ),

117

]

...

x1(t)

x(f,τ)
STFT

x(f,τ)
Normalize

Clustering

Ck

Maskingyk(f,τ)

ISTFT

yk(t)

xM(t)

]

Figure 1: Flow of proposed method
where hjk (f ) is the frequency response from source k tosensor j, and sk (f, τ ) is a frequency-domain time-series
signal of sk (t) obtained by the same operation as (2). The
second advantage is that the sparseness of a source signal becomes prominent in the time-frequency domain if
the source is colored and non-stationary such as speech.
The possibility of s k (f, τ ) being close to zero is muchhigher than that of s k (t). When the signals are sufficiently
sparse in the time-frequency domain, we can assume thatthe sources rarely overlap and (3) can be approximated as
xj (f, τ ) ≈ hjk (f )sk (f, τ ), k ∈ {1, · · · , N },2.2.2. Clustering
The next step is to find clusters C 1 , . . . , CM formed bynormalized vectors x̄(f, τ ). The centroid ck of a cluster
Ck is calculated byP
ck ← x̄∈Ck x̄/|Ck |, ck ← ck /||ck ||,where |Ck | is the number of vectors in C k . Each cluster corresponds to an individual source. The clustering
criterion is to minimize the total sum J of the squared
distances between cluster members and their centroid
P
P
2
J = M
(8)
k=1 Jk , Jk =x̄∈Ck ||x̄ − ck || .

(4)

where sk (f, τ ) is a dominant source at the time-frequency
point (f, τ ). We estimate which source is dominant at
each time-frequency point (f, τ ) by using the procedures
described in the following subsection.

This minimization can be performed efficiently with the
k-means clustering algorithm [8].

2.2. Separation procedures

2.2.3. Reconstruction of each separated signal

Let us have a vector notation of the mixing model (3) :PNx(f, τ ) ≈ k=1 hk (f )sk (f, τ ),(5)

Finally, we design a time-frequency binary mask that extracts the time-frequency points in one of the clusters
1 x̄(f, τ ) ∈ Ck
Mk (f, τ ) =(9)0 otherwise

where x = [x1 , . . . , xM ]T is an observation vector andhk = [h1k , . . . , hM k ]T is the vector of the frequency responses from source s k to all sensors.

and obtain the separated signals y k (f, τ ) by
2.2.1. Normalizationyk (f, τ ) = Mk (f, τ )xJ 0 (f, τ )The new method involves normalizing all observation vectors x(f, τ ), j = 1, . . . , M , for all frequency bins f =0, L1 fs , . . . , L−1
L fs such that they form clusters, each ofwhich corresponds to an individual source. The normalization is performed by selecting a reference sensor J andcalculating
arg[xj (f, τ )/xJ (f, τ )]x̄j (f, τ ) ← |xj (f, τ )| exp 
4f c−1 dmax
(6)

where J 0 ∈ {1, · · · , M } is a selected sensor index.
At the end of the flow, we have outputs y k (t) by an inverse
STFT (ISTFT):
yk (τ + r) ←X

yk (f, τ ) e 2πf r .

1
f ∈{0, L
fs , ..., L−1
L fs }(10)
3. EXPERIMENTS

where c is the propagation velocity and d max is the maximum distance between the reference sensor J and a sensor∀j ∈ {1, . . . , M }. Then, we apply unit-norm normalizationx̄(f, τ ) ← x̄(f, τ ) / ||x̄(f, τ )||1
L·win(r)3.1. Experimental conditions
We performed experiments to verify that our method canseparate signals mixed in a reverberant condition. We
measured impulse responses h jk (l) under the conditions
shown in Figs. 2 and 4. Mixtures were made by convolving the impulse responses and 5-second English speeches.
The reverberation time of the room was RT 60 =130 ms.
The sampling rate was 8 kHz. The frame size L for STFT
was 512, and we changed the frame shift from 64(= L/8)
to 256(= L/2) to observe its effect on musical noise.

(7)

for x̄(f, τ ) = [x̄1 (f, τ ), . . . , x̄M (f, τ )]T . By this normalization, x̄(f, τ ) becomes independent of frequency, anddependent only on the positions of the sources and sensors. That is, the observation vectors are clustered basedon the source geometry. The rationale for this is explainedin the Appendix.

118

Loudspeakers(height : 1.35 m)

3

Squared distance from C1

S3

1.80 m1.1 mo

3.55 m150
2.25 m

S2

o

90

4 cm

o

30

1.75 m3.5

3.5

4.45 mS1

3@330Hz

2.5

2.5

2

2
C3

1.5

@516Hz

C3

1.5

1

1
C2

Omni-directional microphones(height : 1.39 m)

Room height : 2.50 m

0
0

C2

0.5

0.5

50

150
100
Frame index

C1
200

0
0

50

150
100
Frame index

C1
200

Figure 2: Room setup for primary experiment
Figure 3: Example clustering result (N = 3, M = 2). o,+, * show the cluster members C 1 , C2 and C3 , respectively.

3.2. Performance measures
The separation performance was evaluated in terms of the
improvement in the signal-to-interference ratio (SIR) for
each output i. This improvement was calculated by
OutputSIRi − InputSIRi , where
InputSIRi = 10 log10

h|x 0 (t)|2 it
P Ji
h| k6=i xJ 0 k (t)|2 it

OutputSIRi = 10 log10h|y (t)|2 it
P ii
h| k6=i yik (t)|2 it

Table 1 shows the separation result for four sources withthree sensors (N = 4, M = 3, underdetermined), thatwere arranged non-linearly (Fig. 4 [Setup 1]). We investigated four combinations of speakers and averaged the results. From Table 1, we can see that our proposed method
achieved good separation performance even if we utilized
the non-linear sensor arrangement. In such a non-linear
case, the conventional DOA-based method cannot be applied straightforwardly. The applicability to a non-linear
sensor array is one of the advantages of our method.

(dB), (11)(dB), (12)P
where xJ 0 k (t) =l hJ 0 k (l) sk (t − l) and yik (t) is thecomponent of s k that appears at output y i (t): yi (t) =PN
k=1 yik (t). Moreover, we used the signal to distortion
ratio (SDR) as a measure of sound quality:
SDRi = 10 log10h|xJ 0 i (t)|2 it
h|xJ 0 i (t) − αyii (t − D)|2 it

Table 1 also shows the SIR, SDR and MOS values when
we changed the frame shift from 256(= L/2) to 64(=L/8). By using the fine-shift (L/4 and L/8), the SDR
and MOS values increase without any reduction in the SIR
values. The MOS was significantly different for each shift
rate (the significant level was .01). Our subjective test
confirmed that the fine-shift reduced the audible musicalnoise. This is because the fine-shift in (2) and the overlapadd in (10) realize a gradual change in the spectrogram ofthe separated signal [7]. We can say that the fine-shift effectively reduces the signal distortion when we employ it
for our new method.

(dB), (13)where α and D are parameters used to compensate for theamplitude and phase difference between x J 0 i and yii .
To evaluate the musical noise, we also conducted a subjective test and obtained the mean opinion score (MOS).
The listening tests were undertaken by 10 listeners. Eachlistener awarded a score from one (musical noise is clearly
audible) to five (not audible) for each output signal.
3.3. Results

We also applied our method to a 3-dimensional sensor arrangement (Fig. 4 [Setup 2]). Table 2 shows the example
separation result for four sources (two male and two female speakers) with four sensors (N = M = 4). Here, thesystem knew just the maximum distance (5.0 cm) between
the reference microphone (Mic. 3) and the others. We cansee from Table 2 that our proposed method can be applied
to such a 3-dimensional microphone array system. Here,although there was no significant difference between the
MOS results for shift=L/4 and shift=L/8, the fine-shift(shift=L/4 or L/8) reduced the musical noise.

Figure 3 shows an example clustering result for normalized observation vectors when N = 3 and M = 2 (Fig. 2)
at two frequencies. Each point shows the squared distance||x̄ − c1 ||2 between normalized vectors x̄ and one of thecentroids c1 . We can see that the clustering was accomplished successfully using our clustering method. Moreover, it can be seen that the clustering is independent of
frequency. As expected, the SIR improvement was almost
the same (around 12 dB on average) with both our proposed method and the previous DOAs-based method, because we have only two elements and all sources were atequal distances from the microphones.

Some sound examples can be found at [9].

119445 cm

Microphone (120cm height, omni-directional)
Loudspeaker (120cm height)

Mic.4 Mic.1
5.7cm
5cm
Mic.2
4cm
4.2cm
Mic.3
5cm

[Setup 1]
Mic.1

Mic.2

355 cm

4cm
4cm

S4

4cm
Mic.3

Table 1: Average SIR improvement [dB], average SDR[dB] and average MOS (N = 4, M = 3),[Setup 2]

30o

S3

InputSIRi
Shift L/2

180cm

45o
30o 45o

Shift L/4

160cm

50cm

S1

Shift L/8

S2

80cm

175cm

SIRi
SDRi
SIRi
SDRi
SIRi
SDRi

y1
−7.4
16.4
4.7
17.4
5.5
17.9
5.6

y2
−6.2
10.5
3.9
11.6
4.7
11.8
4.8

y3
−6.0
14.2
4.8
15.5
5.6
15.9
5.8

y4
−1.0
11.1
7.9
12.0
8.7
12.3
8.8

MOS

1.9
2.6
2.9

120cm

Table 2: Example SIR improvement [dB], SDR [dB] andaverage MOS (N = 4, M = 4),• Reverberation time: 130 ms• Room height: 250cm

Figure 4: Experimental setups with non-linear arrays
InputSIRi
Shift L/2
4. CONCLUSION

Shift L/4

We proposed a new method for separating sparse signals
by clustering the normalized observation vectors. Our
proposed technique 1) provides a novel BSS method thatcan be applied to both (over-)determined and underdetermined cases, 2) provides a new feature vector for clustering the observation vectors, 3) makes it easy to use a nonlinear/non-uniform sensor arrangement, and 4) makes it
possible to exploit the information obtained from all the
sensors for separation.

Shift L/8

y3
−6.6
9.6
3.6
9.9
4.1
10.1
4.2

y4
−0.6
15.7
11.5
17.0
12.1
17.4
12.2

MOS

1.9
2.7
2.7

sensorFigure 5: Direct-path (nearfield) modelThis appendix explains why normalized observation vectors x̄(f, τ )form a cluster for a source. Let us approximate the multi-path
mixing model (1) by using a direct-path (nearfield) model (Fig. 5)q(f )exp  2πf c−1 (djk − dJ k ) ,
djk

(14)



where djk > 0 is the distance between source k and sensor j.
We assume that the phase 2πf c−1 (djk − dJ k ) depends on the
distance normalized with the distance to the reference sensor J.
We also assume that the attenuation q(f )/djk depends on both
the distance and a frequency-dependent constant q(f ) > 0.
Substituting (14) and (4) into (6) and (7) yieldsx̄j (f, τ ) ≈

y2
−5.3
15.6
5.7
16.5
6.1
17.3
6.6

sourceAppendixhjk (f ) ≈

SIRi
SDRi
SIRi
SDRi
SIRi
SDRi

y1
−8.1
17.8
4.2
19.0
4.7
19.3
4.9

1
π (djk − dJ k )
, D=
exp 
djk D
2
dmax








M
j=1

1
,
djk 2

which is independent of frequency, and dependent only on thepositions of the sources and sensors. That is, the observation
vectors are clustered based on the source geometry. From thefact that maxj,k |djk − dJ k | ≤ dmax , an inequality−π/2 ≤ arg[x̄j (f, τ )] ≤ π/2
holds. This property is important for the distance measure (8),since |x̄ − x̄0 | increases monotonically as | arg(x̄) − arg(x̄0 )|increases.

120

5. REFERENCES[1] A. Hyvärinen, J. Karhunen, and E. Oja, Independent Component Analysis, John Wiley & Sons, 2001.
[2] Ö. Yılmaz and S. Rickard, “Blind separation of speech mixtures via time-frequency masking,” IEEE Trans. on SP, vol.
52, no. 7, pp. 1830–1847, 2004.
[3] F. J. Theis, C. G. Puntonet, and E. W. Lang, “A histogrambased overcomplete ICA algorithm,” in Proc. ICA2003,
2003, pp. 1071–1076.
[4] P. Bofill and M. Zibulevsky, “Blind separation of more
sources than mixtures using sparsity of their short-time
Fourier transform,” in Proc. ICA2000, 2000, pp. 87–92.
[5] S. Araki, S. Makino, A. Blin, R. Mukai, and H. Sawada,“Underdetermined blind separation for speech in real environments with sparseness and ICA,” in Proc. ICASSP2004,
May 2004, vol. III, pp. 881–884.
[6] H. Sawada, S. Araki, R. Mukai, and S. Makino, “Blind extraction of a dominant source signal from mixtures of manysources,” in Proc. ICASSP2005, Mar. 2005, vol. III, pp. 61–
64.
[7] S. Araki, S. Makino, H. Sawada, and R. Mukai, “Reducing
musical noise by a fine-shift overlap-add method applied tosource separation using a time-frequency mask,” in Proc.
ICASSP2005, Mar. 2005, vol. III, pp. 81–84.
[8] R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, Wiley Interscience, 2nd edition, 2000.
[9] http://www.kecl.ntt.co.jp/icl/signal/araki/xcluster.html