Signal Processing - July 2016 - 21

r and Er is P, the rank of the matrix
Since the rank of both M
on the left-hand side of (9) is equal to P, which is usually much
smaller than both M and K. The matrix C(i) can be viewed as
u + C(i) also has rank P. This obseru , such that T
correcting T
vation opens the way to determining the timing parameters
i [11]: first, determine the best rank-P approximation of the
right-hand side of (9). This can be achieved via SVD. Then
determine the parameters i such that the distance between
u + C(i) is as small as possithe rank-P approximation and T
ble. These two steps are alternated until convergence. In a subsequent work, the authors employed an alternative low-rank
approximation method, the structured total LS algorithm,
which was much faster [15]. However, this was achieved by
playing back a sequence of chips with known timing.
Once the timing parameters i are estimated, the location
r and Er are determined, again exploiting their rank-P
matrices M
property. An SVD gives
r T Er = URW T,
M

(10)

r T and Er can be recovered as
from which M
r T = U P C and E
r = C -1 R P W TP,
M

(11)

where R P = R, all except for the P largest eigenvalues are
truncated, and U P and W P consist of the corresponding left
and right singular vectors, respectively.
The remaining problem is the estimation of the P # P
r
matrix C, which is much easier than the estimation of M
and Er , because it is of much lower dimension. In [11], it was
formulated as a nonlinear LS problem, while [8] showed that
a closed-form solution can be found if one sensor is colocated with a source. If the timing parameters are known, only
the second part of the algorithm needs to be carried out, as
described in [8].
Using microphones randomly distributed on a table, an
accuracy of 2 cm was achieved with this method [11]. The ToA
measurements were obtained from recordings of handclaps.
However, the authors needed to label the largest peak in each
handclap signal manually to obtain precise estimates.

Synchronized microphones
In reverberant environments, the steered response power
with phase transform is often employed for TDoA-based
localization. This is equivalent to a filter-and-sum beamformer, when steering the beamformer to all possible locations and selecting the position where the output energy is
maximized [5]. The individual source positions obtained
from several distributed microphone arrays located at the
ceiling of a highly reverberant conference room were used
by Hennencke et al. to perform a coordinate mapping [14].
In their experiments, speech and noise emitted from random
positions was used together with a RANSAC scheme. They
achieved an accuracy of 10 cm with speech and white noise
in most cases.
If a sensor node consists of a microphone array, an acoustic camera can be formed by a delay-and-sum beamformer
applied to the received signals of each array. Redondi et al.
[37] used pure sinusoids as source signals to obtain acoustic images. This enables the application of computer vision
techniques. They used camera models to extract positions in
Cartesian coordinates, which were used as input for a subsequent coordinate mapping approach. The coordinate mapping
approach recovered the rotation and translation for each microphone array to a selected reference array.
Thrun [43] showed that the localization problem can be
significantly simplified if the sources are in the far field of
the microphones. Then a source signal impinges on all sensors from the same angle, and the actual position of the source
is immaterial. Thus, we can write m m - e k = u kT (m m - e k),
where the unit-length direction vector u k only depends on the
source and is independent of which microphone is considered.
Then the right-hand side of (12) simplifies to u Tk (m m - m 1) /c,
which has to be compared to the measured TDoA xu k,(m, 1), leading to the overdetermined system of equations
r /c = x,
UT M

TDoA (M3)
The TDoA is proportional to the distance difference of a pair
of microphones to the source, when the direct path from the
source to the microphones exists. The TDoA itself may be
measured by the maximum in the correlation of the two microphone signals, or by onset detection. To derive the geometry,
this measurement is related to the positioning as follows: The
TDoA from the kth source to the mth and nth sensor is given by

x k,(m, n) = t k, m - t k, n =

Relevant work is discussed first, which assumes time synchronization and thus absence or, equivalently, knowledge of
the delays, before we turn to the case where the delays have to
be estimated as ancillary parameters.

mm - ek - mn - ek
- d m + d n . (12)
c

(13)

where U is the P × K matrix, with u k on the kth column, and
x is the K # (M - 1) matrix of measured TDoAs. Note that
Thrun assumes that the d terms are known and thus can be
set to zero.
Again, the rank argument can be invoked. The rank of the
left-hand side of (13) is P, and so must be the rank of the righthand side. Thus, we can apply the same rank approximation by
SVD as explained in (10) and (11) to infer the microphone positions. This approach of Thrun and others has become known
as affine structure from sound (ASfS).

Unsynchronized microphones
Note that the onset time tk cancels out. Here, - d m + d n is
the time offset between the recording devices.

In the general case of unsynchronized microphones, the
recording delays d m, m = 1, f, M are different and unknown.

IEEE Signal Processing Magazine

July 2016

Table of Contents for the Digital Edition of Signal Processing - July 2016