A geometric approach to localization of acoustic sources and reflectors

V Fa oltà di Ingegneria

Corso di laurea in Ingegneria delle Tele omuni azioni

Dipartimento di Elettroni a e Informazione

A Geometri Approa h to Lo alization of

A ousti Sour es and Ree tors

Relatore: Prof. Augusto SARTI

Correlatore: Dr. Fabio ANTONACCI

Tesi di Laurea di:

Paolo BESTAGINI Matr. 733451

Spa e-time audio pro essing has assumed great signi an e and importan e for

manyappli ationssu hassour elo alization,tra king,beam-shaping,andmany

more. In this thesis we want to propose a dierent approa h to a ousti sour e

lo alizationonaplanebymeasuringtimedieren esofarrival(TDOA).Webase

our approa h on a frame whi h uses three oordinates instead of only two, also

for 2D lo alization. We ould say that the third oordinateis tobe interpreted

astime or,vi e-versa, thatthethree- oordinatesystemhas asimilarstru ture to

proje tive geometry oordinates, where s aling fa tor now matters. In pra ti e

ea h point of this spa e identies a point on the plane where sour e lies, in a

spe i time instant. In this framework we represent the signal emitted by the

sour e as a one the vertex oin iding with the sour e position, or a ir le

pro-je ted in the third dimension in reasing its radius as third oordinate in reases.

Inthe 3D spa e, ea h pair ofTDOAmeasurementand mi rophoneposition

rep-resentsapointthroughwhi hthe oneissupposedtopass. Lo alizationproblem

is thus turned into a one tting problem. The above one tting method an

alsobe applied tomulti-sour e ase. In regardto this, a parti ular ase is given

whenimage sour es are reated by ree tions on walls. Therefore, we showhow

toapply our lo alizationmethodalsoto imagesour es. In doingso we an infer

aree tor position based on real and image sour es lo ations. Forall the above

problems,weprovidesimulationsandexperimentalresultsaswellas omparisons

with other te hniques proposed in the literature. These omparisons show that

theproposedalgorithmsperformatleastaswellasthe bestoneswesele ted, but

usingthe proje tive spa e and dealing with oni s allows usto write onstraints

in a ompa t notation, more suitable when handling many onstraints. One of

Lospa e-time audiopro essing haassuntonotevoleimportanzapermolte

appli- azioni omelalo alizzazionedisorgente, iltra king,ilbeam-shaping,ealtre. In

questatesivogliamomostrareunappro iodierenteperlalo alizzazionediuna

sorgentea usti asu un pianodamisure didierenzedi tempid'arrivo(TDOA).

Basiamoilnostroappro iosuunsistemadi oordinate he neusa trealposto di

due,nonostantelo alizzinel2D.Di iamo he laterza oordinatavainterpretata

ometempoo,vi eversa, he il sistemaditre oordinatehauna struttura simile

aquelle della geometria proiettiva,in uiilfattore di s ala ora onta. In prati a

ognipuntodiquesto spazioidenti a unpuntodelpiano su uigia elasorgente

in uno spe i o istante di tempo. In questo s enario rappresentiamo il segnale

emesso omeun ono olverti enella posizionedellasorgente, oun er hio

proi-ettato nella terza dimensione ol raggio he aumenta all'aumentare della terza

oordinata. Nello spazio 3D, ogni oppia di misure di TDOA e di posizione di

un mi rofono rappresenta un punto attraverso il qualeil ono dovrebbe passare.

Il problema della lo alizzazione si trasforma dunque nel problema di ri er a di

un ono passante per dei punti. Questo metodo di ri er a del ono può essere

utilizzatoan he nel aso di sorgenti multiple. Un aso parti olare si ha quando

delle sorgenti immagine sono reate dalla presenza di riettori. In questo aso,

lo alizzando le sorgenti reali e immaginepossiamo inferire an he laposizione di

un riettore. Per i problemi itati forniamo simulazioni e risultati sperimentali

oltre ad un onfronto on te ni he trovate in letteratura. Il onfronto mostra

he glialgoritmipropostisi omportano bene almenoquantoi miglioritraquelli

testati,mal'uso dello spazio proiettivoel'avere a he fare on oni he permette

di s rivere i vin oli in maniera ompatta, preferibile quando si utilizzano molti

vin oli. Uno dei nostri algoritmi è an he più robusto degli altri in presenza di

List of Figures 12

List of Tables 13

1 Introdu tion 15

2 Problem Formulation 19

2.1 A ousti Measurements: Timeof Arrival,TimeDieren e ofArrival 19

2.2 A ousti Sour eLo alization . . . 21

2.2.1 Stateof the Art . . . 23

2.2.1.1 Lo alizationBasedon Timeof Arrival . . . 23

2.2.1.2 Lo alizationBasedon TimeDieren e of Arrival 24 2.3 Multi-Sour e Lo alization . . . 32

2.3.1 Stateof the Art . . . 33

2.4 Ree tor Lo alization. . . 35

2.4.1 Stateof the Art . . . 36

2.5 Con lusions . . . 43

3 From Measurements to Constraints 45 3.1 State of the Art . . . 45

3.1.1 Dire tTime of ArrivalConstraints . . . 46

3.1.2 Indire tTime of Arrival Constraints . . . 47

3.1.3 Dire tTime Dieren e of ArrivalConstraints . . . 49

3.1.4 Indire tTime Dieren e of ArrivalConstraints . . . 50

3.2 Problem Reformulation . . . 51

3.2.3 Dire tTime Dieren e of ArrivalConstraints . . . 54

3.2.4 Indire t Time Dieren e of ArrivalConstraints . . . 55

3.3 Con lusions . . . 55

4 From Constraints to Lo alization 57 4.1 Algorithms. . . 57

4.1.1 Cost Fun tionBased onthe ConeEquation . . . 58

4.1.2 Cost Fun tionBased onthe ConeAperture . . . 59

4.1.3 Dis ussion . . . 61

4.2 Degenerate Geometry Chara terization . . . 62

4.2.1 Mathemati al Approa h . . . 62

4.2.2 Case Studies. . . 63

4.3 Con lusions . . . 66

5 Extension to Multi-Sour e Lo alization 67 5.1 Data Model . . . 67

5.2 TDOA Disambiguation . . . 68

5.3 Algorithms. . . 69

5.4 Con lusions . . . 74

6 Appli ation to Ree tor Lo alization 75 6.1 Dire tand Indire t Paths . . . 75

6.2 Algorithms. . . 78 6.3 Con lusions . . . 80 7 Experimental Results 81 7.1 ExperimentalHardware . . . 81 7.2 EvaluationMethodology . . . 87 7.3 Lo alization . . . 88 7.3.1 Simulations . . . 88 7.3.2 Experiment . . . 90 7.4 Multi-Sour e Lo alization . . . 100 7.4.1 Simulations . . . 100 7.4.2 Experiment . . . 103

8 Con lusions and Future Works 111

2.1 Lo alizationSetup . . . 21

2.2 Spheri al LS Error Fun tion . . . 27

2.3 Inferen e Setup . . . 36

2.4 Ree tor TopView forContinuous Signals Method . . . 39

2.5 TDOA Disambiguation . . . 42

3.1 TOA, Ree tion on aWall . . . 47

3.2 TDOA, Ree tion ona Wall . . . 51

3.3 New Set of Coordinates. . . 52

3.4 TOA Cone . . . 53

4.1 Cone ApertureConstraint . . . 60

4.2 Tested Arrays . . . 64

4.3 Cost Fun tions . . . 65

4.4 Sour e OutsideArray Area . . . 66

5.1 Multi-Sour e Cross-Correlation . . . 68

5.2 Multi-Sour e TDOAs . . . 69

5.3 Multi-Sour e DATEMM . . . 71

6.1 Dire t and Indire t Path . . . 76

6.2 Raster Condition . . . 78

6.3 Ree tor Geometry . . . 79

7.1 Used Hardware . . . 82

7.2 Simulation Setup . . . 89

7.5 Time Comparison . . . 93

7.6 SimulationsResults . . . 95

7.7 ExperimentalResults (gaussian noise). . . 97

7.8 ExperimentalResults (spee h) . . . 99

7.9 Multi-Sour e Cost Fun tion . . . 101

7.10 Multi-Sour e SimulationSetup. . . 102

7.11 Multi-Sour e Experimental Setup . . . 103

7.12 Multi-Sour e Results . . . 106

7.13 Ree tor Bias . . . 109

5.1 Zero-Sum Restoration . . . 73

7.1 Experimentalsetup: mi rophone spe i ations . . . 83

7.2 Experimentalsetup: A/D and D/A spe i ations(Analog I/O) . 84

7.3 Experimentalsetup: A/Dand D/A spe i ations(Analog In

Per-forman e) . . . 84

7.4 Experimental setup: A/D and D/A spe i ations (Analog Out

Performan e) . . . 85

7.5 Experimentalsetup: A/D and D/A spe i ations(Digital I/O). . 85

7.6 Experimentalsetup: A/D and D/A spe i ations(On-board

Dig-ital Mixer) . . . 85

Introdu tion

Spa e-time audio pro essing has assumed great signi an e and importan e for

many appli ations su h as lo alization, automati amera tra king for

video- onferen ing,separationofa ousti sour es, beamformersteeringforsuppressing

noise and reverberation, beam-shaping, and many more. Many of these

appli- ations are based on the exploitation of dierent kind of measurements su h as

dire tion of arrival (DOA), time of arrival (TOA), or time dieren e of arrival

(TDOA).

Inparti ular,tolo ateradiativepointsour esusingpassivestationarysensor

arrays is of onsiderable interest and has been a repeated theme of resear h

in radar, underwater sonar, and seismology. A ommon method is to have the

estimateofsour elo ationbasedonTDOAmeasurementsbetweendistin tsensor

pairs,or onTOA measurements when sour es and sensorsare syn hronized.

The aim of this thesis is to show an approa h to 2D a ousti sour e

lo al-ization based on the idea of working in a three oordinates spa e with TDOAs

measurements. In this framework we use the two spatial oordinates used for

lo ating obje ts on the plane, aswellas a third oordinaterelated to the signal

propagation time. We also fo us on how to extend this method to the

multi-sour e ase. This allows usto perform real and image sour es lo alizationwhen

aree tor is present, thereforewe an alsoinferthe ree tor position. Proposed

methodsmakeuseof TDOAs,even thoughshown algorithms an bealsoapplied

toTOAs measurements.

on TDOAs an befound in [1℄, but there are alsoother papers fa ingthe sour e

lo alizationproblemin losed-formsolution[2℄,orwithaniterativemethodbased

onTaylorseries[3℄,orexpli itlygivingasolutionbasedonhyperbolainterse tion

[4℄. The ommonapproa hsharedbythesemethods onsistsinworkingwithonly

the two spatial oordinates in order tolo atingthe sour e in 2D.

However, overthelastfewyears, thete hnologi alprogress allowedtoredu e

the size and the ost of the omponents. Mi rophones and loudspeakers are now

moreaordable,andwethinkthatinthenearfuturetheywillbemoreextensively

used in ommer ial produ ts. For example, we imagine entertainment systems

liketelevisionsetsorhi-systemsequippedwithsetsofminiaturizedmi rophones

or speakers orother sensors in order totake advantage of audio te hniques su h

as those basedon roomawarenessto improve auditoryexperien e.

In order to jointly make use of all the onstraints given by the in reasing

number of sensors and managing all of them with a ompa t notation, a novel

approa h to lo alizationproblemis needed. In this dire tion, some really

inter-esting solutionsare those proposed in [5,6,7℄,as they add athird oordinateto

the referen eframe. Inparti ular [5,6℄showalgorithmswhi hmake useof three

homogeneous oordinates, extensively used in omputer vision. These methods

enableustotreat onstraintsgivenbymeasurementsas oni sandquadri s,

lead-ing usto a ompa t notationwhi h is ompatible with onstraints from TDOA,

TOA and DOA. The interesting aspe t of [7℄ is that it works taking into

a - ountspatial oordinates together with propagationtime, givingthus aphysi al

meaningto the third oordinate.

Ourgoalistoproposeasolutionthattakesadvantageofbothsu hte hniques.

Weworkina3Dframeworkaswethinkthatin reasingthedimensionalityofthe

referen eframeallowsustotreatsomeproblemeasily,forexampleturningmany

nonlinear problems intolinear ones. Howeverwe alsogive a physi al

interpreta-tion tothe third oordinateassignal propagationtime, whi h makes onstraints

moreunderstandable. Inthis3Ds enario, ea hpointrepresentsalo ationonthe

2Dsurfa e wheresour elies,inaspe i timeinstant. Thesignalemittedby the

sour e is represented by a one, the vertex oin iding with the sour e position.

As time goes by, the radius of ir le in reases. In this 3D spa e, TDOAs

problemwhere nding the vertex of the one means nding the sour elo ation.

Workingwith a oneina3Dspa e allowsustoeasilytakedegenerategeometries

intoa ount. In fa twe an study mi rophonesdispla ementinorder toprovide

agood one sampling,whi hensures better lo alizationperforman e.

As far as multi-sour e lo alizationproblem is on erned, various approa hes

are proposed in the literature. For example in [8℄ and [9℄ an algorithm based

on blind sour e separation is proposed, in [10℄ blind hannel identi ation is

used,while in[11℄authors makeuse of lustering te hniques. Amore interesting

approa h for our purpose, is that based on orre tly assigning TDOAs to ea h

sour e in order to treat the multi-sour e lo alization problem one sour e at a

time [12, 13, 14℄. These methods pra ti ally onsist in exploiting some TDOA

propertiessoastounderstandwhi hTDOAbelongstowhi hsour e. Thisallows

usto split the multi-sour e lo alizationproblem into several single-sour e

lo al-ization ones. In doing so we an apply our one-based single-sour e lo alization

algorithmsalsotothe multi-sour e ase.

A parti ular multi-sour e s enario is given when image sour es are reated

by signal ree tion on walls. In fa t, when a ree tor is present in the s ene,

mi rophones re eive a signal as if it was emitted by the real sour e and an

im-age sour e reated by the ree tive path. Inthis parti ular ase we an perform

real and image sour e lo alizationassigning TDOAs to ea h of them using on e

more the algorithms for TDOAs assignment as [12, 13, 14℄. After the real and

imagesour esare lo ated,we analsoinferthe ree tor positionwithsome

sim-ple onsiderations onsour es lo ations. Nonetheless other solutions for ree tor

lo alizationproblem an be found in[15℄and [16℄. In thesepapers authorsfo us

onmethodsusingallthe TDOAstogether, inordertolo alizeree tors, without

addressing sour elo alizationproblem.

In briefwe sum up the three problems treated inthis thesis as: single-sour e

lo alization in 2D; multi-sour e lo alization always in 2D; and ree tor

lo al-ization in the same framework. All the methods we propose for solving this

problems are based on the one idea in order to work in the 3D spa e, and are

provided with simulations or experimental results. We have also made a

om-parison between some of the above ited te hniques found in the literature and

In Chapter 2, we fo us our attention on givingthe problemformulation and

presenting the notationused. Givingthe problemformulation wealso introdu e

the state of the artforall the three problems, ex ept for thosete hniques whi h

are basedon homogeneous oordinates.

The methods employed so as to lo alize sour es and ree tors making use

of homogeneous oordinateare dis ussed in Chapter 3. In this Chapter we also

present ina omprehensive way our novel 3D oordinatesystem, and show how

TOAsand TDOAs measurements anbeturnedinto onstraints inthe extended

geometryspa e,usinghomogeneous oordinates asdes ribedinthe literature,as

well aswith our novel approa h.

Afterpresenting the urrentstateoftheartandournewframework,in

Chap-ter4weshowhowproposedalgorithms,makinguseoftwosimilar ostfun tions,

work for sour e lo alization. In this Chapter we fo us on how to use previously

shown onstraints in order to perform sour e lo alization, emphasizing also the

study of favorable mi rophonesdispla ementsand degenerate geometries.

In Chapter 5 we then explain how to use the above proposed lo alization

methodsforthemulti-sour e ase. Indoingso,wedeeplyexplainhowto orre tly

assign TDOAs to ea hsour e before applyinga one-based algorithm.

After the multi-sour egeneral ase isintrodu ed, inChapter6we extend the

algorithm in order to lo alize an image sour e generated by a ree tive path.

Weshow how tond real and image sour es positions and howto inferree tor

positionfromthe sour esones,afterwhi h(Chapter7)wegatherallsimulations

and experimental results in order to prove the ee tiveness of our algorithmsin

ontrast tothe othersfound inthe literature.

Finally,inChapter 8we draw on lusionsabout the study andshow possible

Problem Formulation

InthisChapterweintrodu ethemathemati alformulationofsour eandree tor

lo alization problems. We also show the urrent state of the art in order to

understand some possible approa hes to these problems. The notation used in

the rest of the thesis is alsogiven.

Sour e lo alization problem is approa hed when no obsta les are present

within the s ene, and only informationfrom the dire t signal is available. First

we dis uss single sour e ase, then we introdu e also the multi-sour e ase.

Fi-nallywehandle ree tor lo alizationproblemwhenonly one ree tor ispresent,

and informationabout dire t and indire tsignal are available.

2.1 A ousti Measurements: Time of Arrival, Time

Dieren e of Arrival

In this Se tion we willrefer about the methodology we use to ondu t a ousti

measurementsinadryroom. Inparti ular,wewillrelateaboutthemeasurement

of times of arrival (TOAs) and time dieren es of arrival (TDOAs) from

ross- orrelation.

In regard to TOAs, the goalis to measure the time of arrivalof the a ousti

paths that link the sour e to the

i

-th mi rophone. In order to do so, the loud-speakerprodu esaknown sequen e

s(t)

(time- ontinuous). Thetime- ontinuous signal

x

i

(t)

a quired by sensor

i

syn hronized with sour e is the delayed repli a

of the signal

s(t)

:

x

i

(t) = hs(t − τ

i

) + v

i

(t).

(2.1)

The oe ient

h

is the attenuation of the dire t path from sour e to re eiver;

τ

i

is the orresponding delay; nally

v

i

(t)

is an additive noise that alters our measurement. After sampling by the A/D onverter we write the time-dis rete

signal as

x

i

(k) = x

i

(kT ) = hs(k − i

i

) + v

i

(k),

(2.2)

where

T

is the sampling period;

k

is the time-dis rete index;

i

i

is the dis rete version of

τ

i

. Forthe sake of simpli ity TOAs are estimated by pi kingpeaksin the ross- orrelations of

x

i

(k)

and

s

(

k)

. In parti ular the lag

i

i

is the lo ation of the rst relevant peak inthe ross- orrelation.

When measuringTDOAs weremove thehypothesisthat sour esare

syn hro-nized with re eivers, while syn hronism among mi rophones still holds. This

s enario a ounts for situations in whi h an arbitrary sour e (e.g. a person

ut-tering a senten e, a ring of a mobile phone, et .) is a tive in the environment.

Obviously this is a more interesting ase be ause it is more realisti to have a

sour e not syn hronized with sensors. Even if we annot measure the time of

arrival,many ues about thesour e position an stillbeextra ted fromthe joint

knowledge of the syn hronized signalsavailable atsensors. After time sampling,

the signal a quired by sensor

i

inthe array is

x

i

(k) = hs(k − i

i

) + v

i

(k).

(2.3)

Themodelintheaboveequationisequivalenttothemodelinequation2.2. Under

the assumptionthatthe attenuation

h

doesnot dependonthemi rophoneindex and that additive noises at dierent mi rophones are un orrelated, the

ross- orrelation of

x

i

(k)

and

x

j

(k)

gives

r

ij

(k) = h

2

s(k − i

i

) ⊗ s(k − i

j

),

(2.4)

where

⊗

denotes the ross- orrelation operator. If the sour e signal is a white noise, we obtain

r

ij

(k) = h

2

δ[k − (i

i

− i

j

)],

(2.5)

TDOAs from ross- orrelations sear hing for the globalmaximum lo ations.

2.2 A ousti Sour e Lo alization

Twodimensionallo alizationproblem onsistsinndingana ousti sour e

lo a-tionona plane,havinginformationabout the array geometry, timeof arrival,or

time dieren eof arrivalfrom sour eto the array.

We onsider anarray of

N + 1

mi rophoneslo atedon a planeat positions

r

_i

_{, [x}

_i

, y

i

]

T

, i = 0, ..., N

(2.6)

in Cartesian oordinate, where

[.]

T

denotes transpose of a ve tor. The rst

mi- rophone (

i = 0

) is regarded as the referen e and is pla ed at the origin of the oordinatesystem (

r

0

= [0, 0]

T

). The a ousti sour eis lo atedat

r

s

, [x

s

, y

s

]

T

.

Figure2.1: Lo alizationSetup: mi rophonesare lo ated at

r

i

, sour e is lo ated at

r

s

,and

D

i

represents the distan e from the

i

-th mi rophone tothe sour e. The distan e from the origin tothe

i

-thmi rophone and the sour eare denoted by

R

i

e

R

s

, respe tively, where

R

s

, kr

s

k =

px

2

s

+ y

s

2

.

(2.8)

The distan e between the sour eand the

i

-thmi rophone isdenoted by

D

i

, kr

i

− r

s

k =

q

(x

i

− x

s

)

2

+ (y

i

− y

s

)

2

.

(2.9)

The dieren e in the distan es of mi rophones

i

and

j

from the sour e is given by

d

ij

, D

i

− D

j

, i, j = 0, ..., N .

(2.10)

The distan e

D

i

and the range dieren e

d

ij

are proportional to time of arrival (TOA)

τ

i

and time dieren e of arrival(TDOA)

τ

ij

, respe tively.

If the sound speed is

c

,then

D

i

= c · τ

i

,

(2.11)

d

ij

= c · τ

ij

.

(2.12)

The speed of sound (inm/s) an be estimated fromthe air temperature

t

air

(in degrees Celsius)a ording to the following approximate (rst-order)formula

c ≈ 331 + 0.610 · t

air

.

(2.13)

The lo alizationproblemis then to estimate

r

s

given the set of

r

i

and

τ

i

, or morerealisti ally

τ

ij

,asshowninpreviousse tion. Notethathaving

N +1

mi ro-phones givesus

N + 1

distin tTOA measurements

τ

i

and

(N + 1) · N/2

distin t TDOA estimates

τ

ij

, whi h ex lude the ase

i = j

and ount the

τ

ij

= −τ

ji

pair only on e. However, in the absen e of noise, the spa e spanned by these TDOA

estimates is

N

-dimensional. Any

N

linearly independent TDOAs determine all of the others. In a noisy environment, the TDOA redundan y an be used to

improve the a ura y of the sour e lo alization algorithms, but this would

in- rease their omputational omplexity. For simpli ity and also without loss of

generality, we an hoose

τ

i0

, i = 1, ..., N

asthe basis forthis

R

N

2.2.1 State of the Art

In this Se tion we present the state of the art for TDOA and TOA lo alization

problem. However, TOA lo alization problem is mu h easier to be solved than

TDOA one be ause TOA knowledge brings more information. For this reason

less TOA based lo alization methods are proposed while it will be given more

importan etoTDOA lo alizationproblemand its state of the artwillbe better

treated. We willshowhowthis problem an besolved withmaximum likelihood

(ML)orleast-squares (LS) riteria,dependingontheerror probabilisti

assump-tions, and whi h are the similarities among the proposed solutions. It will be

emphasized how many LS riteria start with the denition of a ost fun tion

from a shared equation based on TDOA denition and how these algorithms

dier only in the way they treat this equation. In fa t some solutions propose

dierent ost fun tions, whileothers dier forits minimizationmethod.

2.2.1.1 Lo alization Based on Time of Arrival

When sour e lo alizationproblem based onTOAs is examined using estimation

theory[17℄,the measurementsofdistan e between thesour eandthe

i

-th mi ro-phoneare modeledby

D

i

= l

i

(r

s

) + ε

i

, i = 1, ..., N

(2.14)

where

l

i

(r

s

) =

q

(x

i

− x

s

)

2

+ (y

i

− y

s

)

2

(2.15)

and the

ε

i

's are measurement errors. The squared distan e from the sour e to

i

-thmi rophoneis given by

l

i

(r

s

)

2

=

(x

i

− x

s

)

2

+ (y

i

− y

s

)

2

= K

i

− 2x

i

x

s

− 2y

i

y

s

+ x

2

s

+ y

2

s

(2.16) where

K

i

= x

2

i

+ y

2

i

and

x

2

s

+ y

s

2

= D

0

2

if we hoose the rst mi rophone as the origin. We an then denethe error

and putting the

N

error together we obtain

e

_{= Aθ − b}

(2.18) where

e

=













e

1

e

2

. . .

e

N













A

=













x

1

y

1

x

2

y

2

. . . . . .

x

N

y

N













θ

=

"

x

s

y

s

#

b

=

1

2













K

1

− D

1

2

− D

0

2

K

2

− D

2

2

− D

0

2

. . .

K

N

− D

N

2

− D

2

0













.

Ifweusealeast-squaresapproa hfortheerrorminimization,theLS ostfun tion

to be minimizedis given by

J = e

T

e

_{= (Aθ − b)}

T

_{(Aθ − b)}

(2.19)

and a losed-formsolution isgiven by

ˆ

θ

= A

T

A

−1

A

T

b.

(2.20)

2.2.1.2 Lo alization Based on Time Dieren e of Arrival

Whensour elo alizationproblembasedonTDOAsisexaminedusingestimation

theory [1℄, the measurements of rangedieren es are modeled by

d

i0

= g

i

(r

s

) + ε

i

, i = 1, ..., N

(2.21)

where

g

i

(r

s

) = kr

i

− r

s

k − kr

s

k

(2.22)

and the

ε

i

'saremeasurementerrors. In ave tor form,the additivemeasurement error model be omes

where

d

=

[ d

10

d

20

... d

N 0

]

T

,

g

(r

s

) = [ g

1

(r

s

) g

2

(r

s

) ... g

3

(r

s

) ]

T

,

ǫ

=

[ ε

1

ε

2

... ε

N

]

T

.

Sin e the measurementmodelis highlynonlinear, an e ient estimatorthat

attains the CRLB may not exist or might be impossible to nd even if it does

exist. Forthisreasonseveralsolutionsusingdierent riteriahavebeenproposed.

Maximum Likelihood The maximum likelihood estimator (MLE) [1℄ is the

most popular approa h be ause of the well-proven advantage of asymptoti

ef- ien y for a large sample spa e. However to apply the maximum likelihood

prin iple the statisti al hara teristi s of the measurements need to be known

or properly assumed prior to any pro essing. From the entral limit theorem

and also for mathemati alsimpli ity, the measurement error is usually modeled

as Gaussian with zero mean and ovarian e matrix

C

ε

. Sin e the exponential fun tionismonotoni allyin reasing,the MLEisequivalenttominimizinga

(log-likelihood) ost fun tiondened as

ε

M L

(r

s

)

, [d − g (r

s

)]

T

C

−1

ε

[d − g (r

s

)] .

(2.24)

Forthisminimizationaniterativealgorithmsu hassteepestdes ent anbeused

inorder toavoid the ost fun tion exhaustive sear h. However, MLEsuers the

limitation given by the probabilisti assumptions to be made about the

mea-sured range dieren es. In order to over ome this problem, many least squares

estimators (LSEs) have been proposed in the literature.

Least Squares The LSEs make no probabilisti assumptions about the data

and hen e an be applied to the sour e lo alizationproblem in whi h a pre ise

statisti al hara terizationof thedata ishard todetermine. In theLS approa h,

we attempt to minimize a squared error fun tion that is zero in the absen e

of noise and model ina ura ies. Dierent error fun tions an be dened for

losenessfromtheassumed(noiseless)signalbasedonhypothesizedparametersto

theobserveddata,andanydierenterrorfun tionleadstoadierentLSE.Inthe

of

D

i

(equation2.9) other solutionsto lo alizationproblemare proposed.

Hyperboli LS Error Fun tion In the sour e lo alization problem, an

observed range dieren e

d

i0

denes a hyperbola, whi h is the lo us of points where the dieren e of the distan es to the

i

-th mi rophone and the referen e one is a onstant. All points lying on su h a hyperbola are potential sour e

lo ations and all have the same range dieren e

d

i0

to the two mi rophones

i

and

0

. The hyperboli LSerror fun tion isdened asthe dieren e between the observed range dieren e (

d

i0

) and that generated by a signal modeldepending upon the unknown parameters (

g

i

(r

s

)

). Therefore, a sound sour e that is lo- ated by minimizingthe hyperboli LS error riterion has the shortest distan e

toallhyperbolasasso iatedwith dierentmi rophonepairs and spe iedby the

estimated range dieren es.

The denition of this error fun tion isbased onthe assumptionthat if the

measurements are noiseless, the measured range dieren es are equal to

those generated by a model

d

i0

=

q

(x

i

− x

s

)

2

+ (y

i

− y

s

)

2

−

q

(x

0

− x

s

)

2

+ (y

0

− y

s

)

2

= g

i

(r

s

) .

(2.25)

For ea h mi rophone we an then denethe error

e

h,i

(r

s

)

, d

i0

− g

i

(r

s

) .

(2.26)

The error fun tion an be expressed inve tor formas

e

h

(r

s

) = d − g (r

s

)

(2.27)

and the orresponding LS riterionis given by

J

h

= e

T

h

e

h

= [d − g (r

s

)]

T

[d − g (r

s

)] .

(2.28)

Sin e

J

h

isnonlinear,minimizingitleadstoamathemati allyintra tablesolution as

N

gets large. As a result, it is rarely used in pra ti e as is. Methods taking

Spheri al LS Error Fun tion The se ond LS riterion is based on the

errors found in the distan es from a hypothesized sour e lo ation to the

mi ro-phones. Referring to Figure 2.2, if we draw ir les with radius

D

i

entered at the mi rophones, they all interse t in one point in the absen e of measurement

errors. The orre t sour elo ationis preferablyat the interse tion of this group

Figure2.2: Spheri al LSErrorFun tion:

r

s

representsthe sour eposition,while

r

0

,

r

1

, and

r

2

represent mi rophones.

D

0

,

D

1

and

D

2

are the distan es from sour etomi rophones. Allthe ir les enteredatmi rophoneswithradius equal

to the distan es to the sour e, interse ts in one point. The sour e is lo ated at

this point.

of ir les(orspheresin3D).When measurementerrorsare present, ir lesdonot

interse t in only one point. Therefore the best estimate of the sour e lo ation

would be the point that yieldsthe shortest distan e to those ir les.

From the denition of the range dieren e and the fa t that

D

0

= R

s

, we have

ˆ

D

i

= R

s

+ d

i0

(2.29)

where

D

ˆ

i

denotesthedistan efromthesour etothe

i

-thmi rophonebased onthe measuredrange dieren e

d

i0

. From thedenition of

D

i

we an also

write

D

2

_i

_{= kr}

i

− r

s

k

2

= R

i

2

− 2r

T

i

r

s

+ R

s

2

.

(2.30)

The spheri al LS error fun tion is then dened as the dieren e between

the measured and hypothesized values

e

sp,i

(r

s

) =

1

2

 ˆ

D

2

i

− D

i

2



(2.31)

= r

i

r

s

+ d

i0

R

s

−

1

2

R

2

i

− d

2

i0

, i = 1, ..., N

Putting the N errors together and writing them ina ve tor form gives

e

sp

(r

s

) = Aθ − b

(2.32) where

e

sp

(r

s

) =













e

sp,1

(r

s

)

e

sp,2

(r

s

)

. . .

e

sp,N

(r

s

)













A

=













x

1

y

1

d

1,0

x

2

y

2

d

2,0

. . . . . . . . .

x

N

y

N

d

N,0













θ

=







x

s

y

s

R

s







b

=

1

2













R

2

1

− d

2

1,0

R

2

2

− d

2

2,0

. . .

R

2

N

− d

2

N,0













.

The orresponding LS riterion isthen given by

J

sp

= e

sp

(r

s

)

T

e

sp

(r

s

) = (Aθ − b)

T

(Aθ − b) .

(2.33)

A losed-formsolution is thengiven by

ˆ

θ

= A

T

A

−1

A

T

b.

(2.34)

Thespheri al errorfun tionislinearin

r

s

,thereforethe omputational omplex-ity to nd a solution will not dramati ally in rease as

N

gets large. For this reasonthespheri alLSerrorfun tion anbeusedwhenafastsolutionisneeded.

thesour e andthe referen emi rophone(

R

s

)was orre tforthe omputationof

ˆ

D

i

. As shown in [18℄, abettersolution an be found.

Linear-Corre tion Least-Squares In the previous solution we assumed

that the distan e between the sour e and the referen e mi rophone (

R

s

) was orre t for the omputation of

D

ˆ

i

. The whole error of the term

d

i0

was then "loaded" on the

i

-th mi rophone lo ation. In order to avoid this problem, the linear- orre tionleast-squaresmethod[18℄wasproposed. Thisalgorithmsear hes

forthe minimumof the Spheri al LS Error Fun tion(

J

sp

) taking a ount of the onstraint

x

2

s

+ y

s

2

− R

2

s

= 0

whi hfor es the distan ebetween thesour eand the referen emi rophone tobe

R

s

.

Usingthis method, the solutionis given by

min

θ

(Aθ − b)

T

(Aθ − b) s.t. θ

T

Σ

θ

= 0

(2.35) where

Σ

_{= diag( 1 1 −1 ).}

(2.36)

Usingthis orre tion is equalto onstrain the distan e between the sour e

and the referen e mi rophone to be

R

s

. In order to solve this onstrained minimizationproblemthete hniqueofLagrangemultipliersisusedandthe

sour elo ationis determinedby minimizingthe Lagrangian

L(θ, λ) = J

sp

+ λθ

T

Σ

θ

(2.37)

where

λ

isthe Lagrangemultiplier. In[18℄ itis shown thatinorder tond

λ

, a polynomial of degree six must be solved. Be ause of its omplexity, numeri almethodsneed tobe usedfor rootsear hing. In order toperform

this rootsear hing, amulti-steppro edureis proposed.

ThisalgorithmispresentedasanimprovementoftheSpheri alLSErrorFun tion

one. The negative aspe t is given by the omplexity of root sear hing used to

nd the orre t value of

λ

. This aspe t makes this algorithm not suitable for real-time problems or when a fast solution is needed, be ause of time spent in

Gillette-Silverman Gillette and Silverman propose another losed-form

method based on squared range dieren e between a referen e mi rophone and

the others [2℄. Their goal is to nd a simple solution to the sour e lo alization

problem, giving it in losed-form. In order to pro eed with this algorithm, we

need todeneareferen emi rophone,andwithoutlossofgeneralitywe an take

the mi rophone pla edat the origin asreferen eone. Asan extensionof this

al-gorithm,alsoamethodwheredierentreferen emi rophonesaresimultaneously

used is proposed in[2℄.

Thesquareddistan e fromthe sour etothe

i

-thmi rophoneis(from equa-tion 2.9)

D

_i

2

= (x

i

− x

s

)

2

+ (y

i

− y

s

)

2

.

(2.38)

The squared range dieren e between the referen e mi rophone and the

i

-thone isthen

D

2

_i

_{− D}

2

₀

= (x

i

− x

s

)

2

+ (y

i

− y

s

)

2

− (x

0

− x

s

)

2

− (y

0

− y

s

)

2

.

(2.39)

Startingfromthis equation,GilletteandSilvermanshowhowtoobtainthe

followinglinear system













x

0

− x

1

y

0

− y

1

d

1,0

x

0

− x

2

y

0

− y

2

d

2,0

. . . . . . . . .

x

0

− x

N

y

0

− y

N

d

N,0



















x

s

y

s

D

0







=













w

1,0

w

2,0

. . .

w

N,0













(2.40) where

w

i,j

≡

1

2

d

2

ij

− x

2

i

+ x

2

j

− y

2

i

+ y

j

2

.

(2.41) The solution an then be obtained with aleast-squares inversion.

As mentioned above the algorithm an then be easily extended to a more

generalone, using

M

referen e-mi rophones atthe sametime. The follow-ing example shows how to extend the algorithm for

M = 2

and

M = 5

mi rophones. The system to be solved be omes

































x

0

− x

1

y

0

− y

1

d

1,0

0

x

0

− x

2

y

0

− y

2

d

2,0

0

x

0

− x

3

y

0

− y

3

d

3,0

0

x

0

− x

4

y

0

− y

4

d

4,0

0

x

1

− x

0

y

1

− y

0

0

d

0,1

x

1

− x

2

y

1

− y

2

0

d

2,1

x

1

− x

3

y

1

− y

3

0

d

3,1

x

1

− x

4

y

1

− y

4

0

d

4,1













































x

s

y

s

D

0

D

1













=

































w

1,0

w

2,0

w

3,0

w

4,0

w

0,1

w

2,1

w

3,1

w

4,1

































.

(2.42)

The solution an be on e more obtained with a least-squares inversion.

As mentionedabove, this method ensures a simple and losed-form solution. In

order to use this te hnique a greater number of mi rophones should be used, if

ompared to other methods. By the way it is a andidate solution when only a

fewtime is given inorder to nd the solution.

Taylor Series Another interesting solution is given by the Taylor series

expansion of equation 2.22 about a referen e point and a su essive iterative

gradient sear h ([3℄ ,[19℄). This algorithm an also be viewed as a method for

iteratively minimizethe Hyperboli LS Error Fun tion.

To determine a reasonably simple estimator, the equation 2.22 an be

lin-earizedby retainingonly the rst two terms ofthe Taylor series expansion

about the referen e point

r

s,0

= [x

s,0

, y

s,0

]

T

g(r

s

)

⋍ g(r

s,0

) + G · (r

s

− r

s,0

).

(2.43)

Here

G

isthe gradientmatrix

G

=









∂g

1

∂xs

∂g

1

∂ys

. . . . . .

∂gN

∂xs

∂gN

∂ys

























rs=rs,0

=









x

0

_−xs

D0

−

x

1

_−xs

D1

y0

−ys

D0

−

y1

−ys

D1

. . . . . .

x0

−xs

D

0

−

xN

−xs

DN

y

0

_−ys

D

0

−

yN−ys

DN

























rs=rs,0

where

∂g

i

∂x

s

=

x

0

− x

s

D

0

−

x

i

− x

s

D

i

,

(2.45)

∂g

i

∂y

s

=

y

0

− y

s

D

0

−

y

i

− y

s

D

i

,

(2.46)

and the ve tor

r

s,0

ould be anestimate of

r

s

determined from a previous iteration or based upon a priori information. The sour e lo alization an

beperformedwith agradientsear h, asprogressiveapproximationstarting

from an initial point

r

s,0

and applying the following update at the

v

-th iteration

r

s,v+1

= r

s,v

+ G

T

v

G

v

−1

G

T

_v

e

h

(r

s,v

)

(2.47)

where

e

h

isthehyperboli LSerrorfun tiontakenfromequation2.27. This method is in fa t an algorithm to iteratively minimize the Hyperboli LS

Error Fun tion.

This algorithmpresent asimpleway todealwith the Hyperboli LSError F

un -tion. Anegativeaspe t isgivenbyitsiterativeway of onvergingtothesolution.

Inordertouse thismethod,thenumberofiterationshouldbe ontrolledinorder

to give areasonable time of onvergen e as wellas ana urate solution.

Exa t Noniterative Linear Method In[7℄ anoniterativelinear method

is proposed. This method is alledan exa t methodbe ausenolinearizationare

made. This algorithm is based on an inverse approa h very similar to the idea

atthe basis ofSpheri al LSErrorFun tion. In parti ularre eivers are presented

as if they a t as sour es emitting ir ular wave fronts, so that at a given time

all the wave fronts interse t at the sour e position. This method needs at least

four mi rophones for 2D lo alization in order to write three equation (one for

ea h independent ouple of mi rophones)linear in the unknowns

x

s

,

y

s

,and the propagationtime

t

. Takinga ountof propagationtime aswellasthe two spa e oordinate isone of the most interesting aspe ts of this method.

2.3 Multi-Sour e Lo alization

TDOAs.

Ifwehave

M

whiteandun orrelatedsour es

r

sa

, a = 1, ..., M

emitting

s

a

(t)

inanane hoi roomwith

N + 1

sensorsat

r

i

, i = 0, ..., N

,whereonlythedire t pathsfrom sour e

a

tosensor

i

with delay

τ

a,i

andattenuation

h

a,i

ontribute to the sensor signals

x

i

(t) =

M

X

a=1

h

a,i

s

a

(t − τ

a,i

) , i = 0, ..., N,

(2.48)

the ross- orrelation

r

ij

(τ )

willshowatmaximum

M

lo alextrema. Aspreviously shown inthis Chapter, when onlyone sour eis onsidered, the ross- orrelation

exhibits only one peak, and TDOA an be extra ted from the lo ation of this

peak.

Inthemulti-sour e ase,ea hoftheMpeakslo ation orrespondstoaTDOA

for a parti ular sour e. Unfortunately we an not orre tly assign peaks to

sour es. Resolving this multiple-sour e ambiguity is important for lo alization,

be ause wehave toassign ea h TDOA toone sour e and onsider allTDOAs of

that parti ular sour e together toestimate its geometri position. This problem

isknown asTDOA disambiguation.

Afterthisproblemissolved, andea hTDOAextra ted from ross- orrelation

isassignedtothe orre tsour e,multi-sour elo alizationproblem anbetreated

asseparate singlesour e lo alizationproblems.

2.3.1 State of the Art

In order to solve TDOA disambiguationproblem we an found several dierent

approa hes in the literature. Anyway some authors propose methods for

simul-taneouslylo ateall the sour es. Now wesum up some of this methods.

ClusteringTe hnique Onepossiblesolution onsistinndingsour elo ation

andidates testing several TDOAs ombinations [11℄, and then perform a he k

inorder tond real sour eslo ations.

In order to use this method array mi rophones are paired in doublets.

ltered by the same a ousti transfer fun tion.

Signals oming from ea h pair of mi rophones are pre-pro essed by a

stan-dard LPC algorithminorder toremove the ommonspe tral featurespresent in

doublet signals(in luding the pit h) and minimizespe trum u tuations.

If the number of sour es is not known, it an be estimated, and TDOAs are

extra ted fromthere eivedsignals. FromTDOAsgeneratedforea hpairof

dou-blets, a andidate sour e position is omputed by e ient geometri algorithms

availablein the literature.

Whilewrongestimatesusuallygeneratedisperse lusters ontainingfewpoints,

dense lusters having an approximately ellipti al shape are formed around the

speakers. Centroids of lustersare nally sele ted as speaker lo ations.

DATEMM (Zero-Sum) Disambiguation of TDOA Estimates in Multi-path

Multi-Sour eEnvironments(DATEMM) algorithm[14℄isanothersolutiontothe

problem. Thisalgorithmisuseful forassigningea h peakofthe ross- orrelation

to a sour e. This allowus to separate TDOAs for ea h sour e as well as

re og-nizing whi h TDOA belongsto ree tive paths.

Thealgorithmis omposedbytwosteps. Initsrststep,DATEMMalgorithm

establisheswhi hpeaksof ross- orrelationsbelongtothedire tsignal,andwhi h

tothe ree ted signal. If we onsider anon reverberantroom, we an go further

this step.

On e ross- orrelation peaks related to ree tive paths are removed, a step

is performed in order to assign TDOAs tosour es. This assignment is based on

onsideration on TDOAs between mi rophones ouples. A parti ular he k is

performedbetweenTDOAs inordertond thosewhi hmat ha ondition alled

Zero-Sum ondition. However this step is better explained in Chapter 5, when

our algorithmfor multi-sour e lo alizationis explained.

Gaussian Likelihood Criterion Another possible solution onsists in using

ablind sour eseparation (BSS)method ombinedwith alikelihood riterion. In

[8℄, authors propose a BSS method involving a multiple-input-multiple-output

(MIMO) model in order to estimate TDOAs for ea h mi rophone pairs. This

MIMOsystem isalsoshownin[9℄asanalternativetotheuse of ross- orrelation

inherently based on the real reverberant propagation model. While performing

the separationof sour es, the BSS method behaves similarlytoa set of adaptive

nullbeamformers, whi h steer nullsin the dire tions of the sour es.

Afterthisestimation step,aspatialambiguityforsour eslo ationstillexists.

TheTDOAsextra tedforea hmi rophonespair annotstillbeusedtolo alizea

singlesour eposition. Inordertoover omethisproblem,alikelihoodfun tionis

proposed, andallthe possiblesour epositionsare tested. A omparisonbetween

thelikelihoodof allpossible sour e ongurations isperformed,and the

ongu-rationgivingthe highestlikelihoodvalue is onsidered the orre t onguration.

This step is shown to sometime fail in simultaneously lo alize many sour es for

some ongurations. However, it an lo alize at least one of them su essfully

most of the time.

Thisalgorithmalsotakesa ountofthepossibilityoftra kingmovingsour es.

In this ase a parti lelter is implemented.

2.4 Ree tor Lo alization

Inferen e problem onsidered in this se tion onsists in ndingthe position of a

singleree tor present intoa s ene, dealingwith TDOAs measurements.

We onsider the same array and sour e setup used for sour e lo alization

problem,but we add a ree tor. This ree tor an be modeled onthe plane

xy

asalineofequation

y = mx + q

. UsingtheCartesian oordinatesystem entered in

r

0

= [0, 0]

T

the ree tor an be dened as all the points

x

= [x, y, 1]

T

whi h

satisfythe ondition

x

T

l

= 0,

(2.49)

where

l

= [−m, 1, −q]

T

.

Dealingwithoneree tor,ea hmi rophonere eivesthesignalfromthedire t

path as well as from the indire t path reated from the ree tion of the signal

frompoint

r

p

. Amethodtotreatthemulti-pathpropagation onsistsinmodeling the signal omingfromthe indire t path asit omes from anothersour e, alled

the image sour e. The image sour e position is found mirroring the real sour e

through the ree tor. As we work with real and image sour es we dene

r

s

′

as the image sour erelated toreal sour e

r

s

.

Figure2.3: Inferen e Setup: real sour eisin

r

s

,image sour ein

r

s

′

,mi rophone in

r

r

,and

r

p

represents the ree tion point.

l

represents a ree tor.

morethe TDOAdisambiguationproblem. Inthe multi-sour e asewehad

dier-ent sour esemittingdierentsignals, whi h leads toanumberof peaksin

ross- orrelations equal tothe numberof sour es. With aree tor and one sour e, we

an onsider having two sour es, the real and the image one, syn hronized and

emitting the same signal. This leads to four peaks in ea h ross- orrelation

be-tween mi rophonesinstead of only two. Forthis reason we deal with asituation

worse thanthe multi-sour e one previously shown.

However, aswewillseeinChapter6,thisTDOAambiguity anbesolvedwith

some onsiderations based on the analysis of the auto- orrelations of the signal

re eived by ea h mi rophone. Then,on e we are able to assign ross- orrelation

peaks to real and image sour es, we an estimatetheir position

r

s

′

and

r

s

from theseTDOAs andderive

l

asshowninChapter6. Howeverothersolutionsfound in the literature are proposed.

2.4.1 State of the Art

The problem of room geometry estimation using mi rophones and loudspeakers

has been addressed by several authors with various approa hes. We rst show

tion methods, whi h diers from our approa h, in order to show that problem

formulation an be dierent fromours. Finally we also show a possible solution

found inthe literature forsolving TDOA ambiguity aused by multipath.

BlindChannelIdenti ation Using ross- orrelationforestimatingTDOAs,

we approximate the a ousti room impulse response as a simple delta fun tion,

and the TDOA estimation is a hieved by maximizingthe ross- orrelation

fun -tion. However in [1℄ and [10℄ dierent approa hes are proposed based on blind

hannel identi ation. Blind hannel identi ation approa hes modelan

a ous-ti roomimpulse response as an FIRlter that in ludes both a dire t path and

multipath ree tions. In these approa hes, after the modeling lters have been

identied, the TDOA an be easily omputed by examining the dire t paths in

the lters.

Ina roomwitha sour eand two mi rophones,the

i

-thmi rophone output attime

k

an be writtenas:

x

i

(k) = s(k) ∗ h

i

+ n

i

(k),

(2.50)

where

∗

denotes linear onvolution,

s(k)

is the sour e signal,

h

i

represents the hannelimpulse response between the sour eand the

i

-th mi rophone, and

n

i

(k)

isanoisesignal. Theblind hannelidenti ationvia rossrelation is based on a lever observation,

x

2

(k) ∗ h

1

= x

1

(k) ∗ h

2

= s(k) ∗ h

1

∗ h

2

, if the mi rophone signals are noiseless [20℄. Then, without requiring any

knowledge from the sour e signal, the hannel lters an be identied by

minimizingthe squared ross- orrelation error. In matrix-ve tor form, the

optimizationbe omes

h

∗

1

, h

∗

2

= arg min

_h1

,h

2

1

2

kX

2

h

1

− X

1

h

2

k

2

s.t.kh

1

k

2

+ kh

2

k

2

= 1,

(2.51)

where

X

i

is the

(N + L − 1) × L

onvolution Toeplitz matrix whose rst rowandrst olumnare

[x

i

(k −N +1), x

i

(k −N), ..., x

i

(k −N −L+2)]

and

[x

i

(k − N + 1), x

i

(k − N + 2), ..., x

i

(k), 0, ..., 0]

T

respe tively,

N

is the mi- rophonesignallength,

L

isthe lterlength,and

k.k

denotes

l

2

-norm. This

minimization problem an be solved by eigenvalue de omposition. When

the lters are estimated, the TDOAs an be omputed by examining the

dire t paths inthe lters.

Byusingamorerealisti model,the blind hannelidenti ationapproa heshave

been shown to be more ee tive than ross- orrelation approa hes to

reverbera-tion. Howeverweareworking inasimple ase whereonlyoneree torispresent,

and we do not need all the information that the room impulse response brings.

For this reason, the omputational omplexity of this algorithm is not justied

for our purpose, and prevents usfrom using it.

Continuous Signals Method In [15℄, authorspropose amethod for

estimat-ing ree tive surfa es using ontinuous signals withoutany prior informationon

the sour e signal. For this method, some sour es and sensors are pla ed into

a room whose walls positions need to be estimated. TDOAs from mi rophones

pairsare omputedbyexponentialttingof ross- orrelationfun tions. Thenthe

approa hisbasedontheinversemappingofthemulti-pathpropagationproblem.

Ree tive surfa e an be dened as a plane with points fullling

perpen-di ularity to anormal ve tor

n

:

P

2

_{(n, a) = {x ∈ R}

3

: n

T

_{(a − x) = 0),}

(2.52)

where

a

denes anarbitrarypointwithintheplane

P

2

. Repla ingthepoint

a

with

b

+ n

plane parameterizationthen be omes

P

b

2

= P

2

(n, b + n) = {x ∈ R

3

: n

T

((b + n) − x) = 0},

(2.53)

whi h has only 3degrees of freedom but asa trade-o loses ability to

rep-resent planes ontainingthe referen epoint

b

. To identifya ree tive surfa e

P

2

,we onsider a system ofthree points

r

i

,

r

s

and

o

i

∈ P

2

,namely the positionsof

i

-thre eivingsensor, soundsour e and the point ofree tion (Figure2.4). The formertwoare assumed tobe

known and the point of ree tion has to be estimated.

Dire t path time delay is determined as

τ

d

(r

s

, r

i

) = c

−1

_{k r}

Figure2.4: Ree tor Top Viewfor Continuous Signals Method:

P

2

isthe

ree -tor,

n

is the normal ve tor,

a

an arbitrary point on the ree tor.

r

i

and

r

j

are twore eivers,

r

s

isthesour e,and

o

i

,

o

j

are twopointofree tion. The indire t signalpath is shown from sour eto mi rophones

i

and

j

.

time delay for a ree tive propagation path is twofold and an be dened

usingthe threepointsdened earlierwith

τ (r

s

, o

i

, r

i

) = τ (r

s

, o

i

) + τ (o

i

, r

i

).

(2.54)

Furthermore, the law of ree tion states that the pie ewise propagation

path has equalangles of in iden e and ree tion. As it happens, ellipsoids

E

2

_(r

s

, r

i

)

with sensor and sour e a ting asits fo i fulllthis requirement. Thisdoesnot, however, givesthe expli it pointof ree tion, rather thana

set of points fullling(2.54).

Given a plane

P

2

the point of ree tion an be realizedas

o

i

=

k proj

P

2

r

_s

k proj

_P

2

r

_i

+ k proj

_P

2

r

_i

k proj

_P

2

r

_s

k proj

P

2

r

_s

k + k proj

P

2

r

_i

k

(2.55)

where

proj

P

2

isa point proje tion onthe plane

P

2

.

Fora plane

p

∈ P

2

b

parameterized as 2.53, the delay be omes independent ofthe ree tion point:

τ (r

s

, o

i

, r

i

) = τ (r

s

, r

i

, p)

spa e dened by 2.53 where delay dieren es from separate sour e-sensor

ombinationsinterse t inthe sear h spa e.

The surfa e is estimated asthe maximum argument of apseudo-likelihood

fun tion as

ˆ

p

= arg max

p

M

Y

i,j=1

R

xi,xj

(τ

i,j

(r

s

, p)),

(2.56)

where

R

xi,xj

(τ )

is the generalized ross orrelation between two re eived signals

x

i

and

x

j

, and time delay dieren es an be al ulated as

τ

ij

(r

s

, p) = τ (r

s

, r

i

, p) − τ

d

(r

s

, r

j

).

(2.57)

Thissolutiontoree torlo alizationisanadvan edsolutionanditmakespossible

tolo atemanyree tors. Howeverwiththeaboveformulationthesour eposition

has tobe known.

L1 Regularized Room Modeling An algorithmfor obtaininga roommodel

based on studying the room impulse response an be found in [16℄. This

algo-rithm uses a onstrained roommodeland

l

1

-regularized least-squares to a hieve good estimation of room geometry. The main idea onsists in syntheti ally or

experimentallyobtainingasetofimpulseresponsesforasetofhypothesizedwalls

positions, and performing a smart sear h between this set of impulse responses

in orderto nd walls positions ompatibles with the re eived signal.

Authorsdenethesinglewallimpulseresponse(SWIR)

h

(r,θ,φ)

m

(n)

asthe dis- rete timeimpulseresponse fromthe loudspeakertothe

m

-thmi rophone, onsidering that: the dire t path from loudspeaker to the mi rophone has

been removed and the array is mounted on freespa e, ex ept for the

pres-en e of a lossless, innite wall with normal ve tor

n

= (r, θ, φ)

and whi h ontainsthe point

(r, θ, φ)

. Forreasonablysmallarraysthe soundwilltake approximately the same path from the sour e toea h of the mi rophones,

whi himpliesthatitshouldwithhigh probabilityree tothe samewalls

beforerea hingea hmi rophone,su hthattheree tion oe ientswillbe

the same for every mi rophone. We an then rewritethe SWIR

h

(r,θ,φ)

related to a generi mi rophone as a ve tor

h

(r,θ,φ)

of length

N

just large enoughto ontain the rst order ree tions.

The rst algorithm step onsists in obtaining syntheti ally or

experimen-tallyforthe array ofinterest aset of SWIRs,ea hmeasured atxed range

over agrid

A

of azimuth angles,and theSWIRs ontaining onlythe ree -tion from a eiling at the same xed range. In essen e this set of SWIRs

arriesatime-domain des riptionof the array manifoldve tor formultiple

dire tions of arrival.

If

A

is su iently ne, for a set of

W

walls, there are oe ients

c

i

,

i = 1, ..., W

su h that we an represent an impulse response

h

room

, whi h hasthedire tpathremovedandtrun atedtoonly ontainearlyree tions,

h

_room

_≈

W

X

i=1

c

i

h

(r0,θi,φi)

.

(2.58)

Theproblemisthen totsome

h

(r0,θi,φi)

forsome valueof

(r

0

, θ

i

, φ

i

)

tothe measured impulse response, adjusting for attenuation. In order to

a om-plish this goal, the SWIRs are ordered into a matrix

H

and attenuation oe ients

c

i

are ordered into a ve tor

a

. The solution to the problem is then given when the orre t

a

is found. In order to nd

a

the following

l

1

-regularizedleast-squares problemshould besolved

min

a

k h

room

− Ha k

2

2

+λ k a k

1

.

(2.59)

Ifwe onsider onlySWIRs with oe ients

[a]

i

largerthan agiven thresh-old, then we have a set of andidate walls. With a post-pro essing stage,

impossiblesolutionsare dis arded inorder to nd the orre tone.

This algorithm aim is to nd the omplete room geometry. For this reason its

omputational omplexity is high. When sear hing for asingle ree tor, using a

method so omplex is not ne essary.

DATEMM (Raster Condition) In[13℄ authorsshowthat by exploitingthe

ross-distan es between them. Fig. 2.5 shows a simple example with one sour e, two

sensors, and two paths persensor. The raster inthe ross- orrelation onsists of

Figure 2.5: TDOA Disambiguation: raster for one sour e asshown in [13℄.

Dis-tan es between peaks in ross- orrelations an be found as peaks positions in

auto- orrelations.

four timemarks whose distan es are known from the peakpositionsof the

auto- orrelations. By nding this raster in the ross- orrelation,its absolute position

determines the desired TDOA of dire t and indire tpaths.

For this purpose, we rst extra t the relevant peaks from both ross- and

auto- orrelations. Wenow onsidertwoTDOAs

τ

ij,µ1

ν1

and

τ

ij,µ2

ν2

resulting fromthesamesour ewherethepathstosensor

i

are ommon(

µ

1

= µ

2

= µ

) and one of the paths to sensor

j

is a dire t path (

ν

1

= 0

or

ν

2

= 0

). The distan e

|τ

ij,µν

1

− τ

ij,µν

2

|

an be found as the position of a peak in the auto- orrelation of sensor

j

, see Fig. 2.5. As the dire t path is always the shortest, we an also determine the sign of the above dieren eand hen e

identify whether

ν

1

or

ν

2

is the dire t path.

Continuing this raster mat h for all TDOA pairs,

τ

ij,00

willbe most likely identiedseveraltimesasthedire tpath(TDOAasso iatedtorealsour e)

while allother path ombinations

(µ, ν) 6= (0, 0)

willat least on e be iden-tied as non-dire t. The TDOA

τ

ij,µν

identied as non-dire t more times than others, isthe TDOA asso iatedto image sour e.

This algorithm allows us to assign TDOAs extra ted from ross- orrelation to

2.5 Con lusions

Wehave introdu edthe threeproblems treatedinthe thesis: singlesour e

lo al-ization, multi-sour e lo alization, and ree tor position inferen e. We have also

shown thenotationusedinnextChaptersand wehavegiven anoverviewofsome

lassi almethodsfound in the literature todeal with the proposed problems.

Inthenext Chapterweoutlineadierentapproa htosour elo alizationand

inferen eusing geometries onsiderationsand a new oordinatesystem. We also