利用三分法進行多圓聯動搜索的聲源定位算法

覃泓銘 王 玫，2 羅麗燕* 韋金泉

1(桂林電子科技大學認知無線電與信息處理教育部重點實驗室 廣西 桂林 541004) 2(桂林理工大學信息科學與工程學院 廣西 桂林 541007)

0 引 言

聲源定位技術由于廣泛應用于智能交通[1]、安防監控[2]、電話會議[3]、人機交互[4]、導航[5]等而備受關注。傳統的聲源定位方法可分為三類：基于可控波束形成的方法、基于高分辨率譜估計的方法和基于到達時間差的方法。其中,基于可控波束形成的定位方法[6-7]需要做全局搜索,計算量大,并且依賴于聲源信號和噪聲信號的先驗知識。基于高分辨率譜估計的定位方法[8-9]需要在空間中搜索目標聲源位置,這種方法的定位精度高但計算復雜度非常高。相比前兩種定位技術,基于到達時間差(TDOA)的定位方法[10-11]計算復雜度較低、定位速度較快性好且硬件成本低,因此成為聲源定位領域中的研究熱點。

基于TDOA的定位方法的中心思想是求解由幾何關系構成的方程組,求解方程組的復雜度會隨著接收節點/基站數量的增加而加大,并且設備誤差與時延估計誤差可能會導致方程組無解,因此基于該方法的聲源定位問題往往被表述為一個非線性優化問題。已經存在很多方法用于解決優化問題,例如最大似然法、非線性最小二乘法和加權最小二乘法,但這些方法具有計算復雜度高、需要估計初始位置的缺點。Chan算法、Fang算法、Taylor級數展開法與最小二乘法的結合[12-14]解決了確定初始位置與聲源位置最優估計的問題,但仍存在計算復雜度高、對初始位置敏感的問題。為了解決這一問題,相關研究者從幾何分析的角度出發,提出了利用圓的幾何關系搜索聲源位置的定位算法[15-17]。文獻[15]提出了基于收縮圓的定位方法，其思想是以恒定的步長收縮所有圓的半徑,直到相交區域的面積達到較小的閾值。文獻[16]中提出一種基于GCC-PHAT與收縮圓的優化方法,相比于收縮圓方法,定位精度與速度得到了改善。文獻[17]中提出了多圓聯動搜索目標的定位算法,其思想是：首先計算初始搜索半徑,根據TDOA的測量值計算每個接收節點相對于搜索半徑的聯動半徑,并根據搜索步長改變搜索半徑進行搜索,找到具有最大步長的最佳半徑,然后減小步長進行搜索以獲得更準確的估計位置。該方法將傳統的多維搜索轉換為一維搜索,并且初始值的計算簡單,降低了計算復雜度。相比于傳統的搜索算法,該方法有效提高了搜索速度和定位精度,但該方法通過逐步提高步長的精度來提升定位精度,在搜索過程中存在重復搜索的問題。本文提出一種利用三分法進行多圓聯動搜索的聲源定位算法，優化了文獻[17]中減小搜索步長進行重復搜索的問題。此外,本文對于初始值的設定進行了改進,減少了搜索迭代次數。較于文獻[17],本文算法不僅減少了迭代次數,還降低了每次迭代搜索時的計算復雜度。實驗結果表明,本文方法在提高定位速度的同時,有效提升了定位精度。

1 基于TDOA的聲源定位方法

基于TDOA的聲源定位基本思想[18]是：通過測量聲源到各個接收節點的到達時間差，得到至少兩個距離差，通過距離差可以獲得雙曲線方程，求解雙曲線的交點即可得到聲源的位置。考慮如圖1所示的二維聲源定位系統，假設聲源位置為S(x,y)，接收節點位置為Ni(xi,yi)，聲源到各個接收節點的距離為ri，到各接收節點之間的距離差為dij，以節點0為參考節點，聲源到各傳感節點與參考節點的時間差為τi0，c為聲速，則有：

(1)

di0=r0-ri=cτi0

(2)

(i=0,1,2,…,n-1)

(3)

圖1 聲源定位系統示意圖

聲源位置就是由式(4)構成的方程組的解,該方程組是基于雙曲線的非線性方程組,在理想條件下,通過聯立方程組即可求出解,即雙曲線的交點。但由于設備誤差、時延估計誤差的存在,這個交集往往是空集,因此求解該方程組的重點是如何采用搜索算法估計聲源位置。聲源定位中,兩種廣泛使用的聲源定位算法是Chan算法和Taylor算法。Chan算法將如上所述的非線性方程組轉化為線性方程組,然后采用最小二乘法(LS)獲得最佳解。Taylor算法將非線性方程組通過Taylor級數展開的方法整理成線性方程組,選擇一個初始值后進行迭代搜索,直到坐標精度滿足搜索的終止條件，即可獲得最佳解。

1.1 Chan算法

Chan算法[19]是非遞歸雙曲線方程組解法,具有解析表達式解。其主要的特點為在測量誤差服從理想高斯分布時定位精度高,并且可以通過增加基站數量來提高算法精度。該算法的核心思想如下：

將式(1)展開并將其線性化得：

(x0-xi)x+(y0-yi)y=ki+r0di0

(4)

(5)

由此可得到矩陣表達式：

AX=F

(6)

(7)

由此可求出聲源的估計位置：

X=(ATA)-1ATF

(8)

1.2 Taylor算法

Taylor級數展開法[20]是一種需要初始估計位置的遞歸算法,在每一次遞歸中通過求解TDOA測量誤差的局部線性最小二乘(LS)解來改進估計位置。該算法的核心思想如下：

將式(3)根據Taylor級數展開得：

ht=Gtδ+ε

(9)

(10)

式中：Rm，1表示由聲源到傳感節點m與傳感節點1的時延差計算出來的距離差；Rm-R1為聲源到傳感節點m與到傳感節點1的真實距離差。

(11)

其加權最小二乘解為：

(12)

式中：Q為TDOA測量值的協方差矩陣。初始迭代時,令x=x0，y=y0,在下一次迭代中，則有：

x(1)=x0+Δxy(1)=y0+Δy

(13)

重復以上過程,直到Δx、Δy足夠小,并滿足一定的閾值ε,使得：

|Δx|+|Δy|<ε

(14)

經過k次迭代,得到的解(xk,yk)即為聲源的估計位置。

2 算法簡介

2.1 算法的基本原理

算法基于TDOA測量值,通過構建幾何關系將非線性問題轉化為線性問題,將多維搜索轉化為一維搜索。算法的基本原理可由下描述：

假設聲源位置為S(x,y),參考節點位置為N0(x0,y0),其他參考節點位置為Ni(xi,yi),聲源到各個接收節點的距離為ri,聲源到各接收節點與到參考節點的時間差為τi0,則有：

(15)

(16)

易知,式(3)可由式(15)、式(16)聯立得到。對于式(15)、式(16)的求解,考慮如圖2所示的定位系統,假設估計的聲源到參考節點的距離為Rk,到其他接收節點的距離為Ri,則有：

(17)

(18)

聯立式(17)、式(18)可得：

(19)

令：

(20)

則式(19)的解為：

(21)

(22)

圖2 接收節點部署示意圖

由方程可知,若改變參考圓半徑Rk,其他圓的半徑Ri也會隨著改變,即不同的Rk對應不同的解(估計聲源位置)。如圖3所示(★：聲源位置；●：接收節點；-‥-：Rk為初始值時的幾何關系；---：Rk改變一次時的幾何關系；—：Rk改變N次時的幾何關系)，不斷地搜索Rk,直到Rk=r0,此時的估計聲源位置即為真實聲源位置。

圖3 多圓聯動搜索的基本思想

在搜索Rk的過程中,初始值的設定以及搜索算法直接影響到算法收斂速度,即聲源搜索速度。文獻[17]根據參考圓B0與各個參考圓Bi相交時,方程具有解的條件設定了Rk的初始搜索半徑,并以初始搜索半徑為最小值,通過改變搜索步長來尋找最優半徑,最后根據最優半徑估計出聲源位置。由于只設定了初始搜索半徑的最小值,該搜索過程為由小往大的單向搜索。為了進一步加快搜索速度,本文根據接收節點位置的幾何關系設定了Rk的初始搜索半徑的最小值與最大值,即搜索半徑區間,并同時改變最小值與最大值進行雙向搜索,不斷地縮小Rk的搜索區間。此外,文獻[17]首先采用較大的搜索步長來估計聲源的粗略位置,然后通過減小步長進行精確搜索。當搜索步長較大時,算法收斂速度較快,但定位精度相應較低,當搜索步長較小時,定位精度得到有效的提高,但重復搜索加長了搜索時間,整個搜索過程速度較慢。本文將三分法運用到雙向搜索過程中,改善了文獻[17]中重復搜索的問題,進一步加快了搜索速度。同時,利用三分法進行搜索,最終搜索區間的下限值無限逼近于上限值,有效提高了定位精度。

2.2 搜索半徑的初始值

設Lij為接收節點i到參考節點j之間的距離,則：

(23)

由聲源、節點Ni、節點Nj構成的三角形滿足三角形三邊關系：

Rk+Rk-cτij≥Lij

(24)

即：

(25)

聲源應該位于由4個節點形成的矩形區域中，則Rk應滿足：

Rk≤max{Lij}

(26)

所以Rk應滿足：

min{(L1j-d1j)/2}≤Rk≤max{Lij}

(27)

以式(27)確定的搜索區間進行搜索,在搜索過程中,每改變一次搜索區間,誤差函數的值都會隨著改變。當誤差函數為最小值時即停止搜索,此時的Rk為全局最優解,即最佳半徑。

2.3 搜索的停止條件

根據式(7)，可定義誤差函數：

(28)

式中：第一項為真實聲源到各接收節點的距離差，第二項為根據Rk估計的聲源到各接收節點的距離差。

(29)

在理想情況下，εi(x,y)=0，但由于設備誤差、時延估計誤差的存在，εi(x,y)≠0，所以當誤差滿足式(29)時，即停止搜索。

圖4 三分法的基本思想

文獻[17]中,改變步長進行迭代搜索的算法計算復雜度為O(mn),其中m為改變步長精度的次數。由三分法的基本思想可知,利用三分法進行搜索算法的計算復雜度為O(2log3n),易知O(2log3n)

利用三分法搜索Rk從而搜索誤差的最小值,即可獲得估計聲源的最佳位置,該過程由以下步驟完成：

步驟1計算搜索半徑Rk的初始值：

(30)

(31)

步驟2進行第i次迭代搜索(可見算法1)：

(32)

則

(33)

反之

(34)

算法1基于三分法的半徑搜索算法

3) fori=1;i<100;i++

9) else

12) end

14) break

15) end

16) end

3 實驗及分析

為了驗證本文方法的定位性能,采用文獻[17]提出的多圓聯動搜索目標定位算法與本文算法進行比較。實驗選用Behringer ECM 8000全向型麥克風4個、哈曼卡頓aura studio音響1個、M-AUDIO M-TRACK QUAD 4通道外置聲卡1個,另外使用1臺聯想筆記本控制收發信號及數據處理。如圖5所示,實驗場景較為空曠,其中一面為墻面。受麥克風信號線長限制,麥克風以矩形(6.5 m×6.5 m)陣型進行擺放,坐標分別為N0(0,0)、N1(6.5,0)、N2(6.5,6.5)、N3(0,6.5)。麥克風與音響高度均為1.3 m,聲源信號為0至16 k chirp信號,采樣頻率為32 kHz。選取3個聲源位置S1(2,2)、S2(3,4)、S3(5.5,3),在每個聲源位置分別采集20組獨立數據。每組定位結果如圖6-圖8所示,平均誤差如表1所示。

圖5 實驗場景

圖6 聲源位于(2,2)處的誤差對比結果

圖7 聲源位于(3,4)處的誤差對比結果

圖8 聲源位于(5.5,3)處的誤差對比結果

表1 兩種方法的聲源定位平均誤差

從表1可以看出,從位置1到位置3的平均誤差在增大,原因在于聲源越靠近墻面(見圖5),麥克風接收到的反射波干擾越大,時延估計的誤差則越大,導致定位誤差增大,本文暫不討論時延估計誤差對定位的影響。在定位精度方面,本文方法的定位精度與文獻[17]方法的定位精度相差不大,但略微優于文獻[17]方法。為證明本文方法在計算復雜度方面的優越性,取聲源位置為(3,4)時的數據進行計算復雜度的對比,結果如表2、表3所示。

表2 文獻[17]方法的Rk搜索過程 單位：m

表3 本文方法的Rk搜索過程 單位：m

從表2可以看出,文獻[17]的方法首先以3.08 m為初始半徑、1 m為步長進行搜索,找到最佳半徑位于[5.80,6.08]區間。然后將步長減小為0.1 m進行搜索,找到最佳半徑位于[5.18,5.28]區間。最后將步長減小為0.01 m進行搜索,直到誤差滿足搜索結束條件。搜索結束時,Rk為5.21 m,對應的估計聲源坐標為(3.135,4.170),經過10次迭代搜索找到聲源最佳估計位置。而從表3可以看出,本文方法首先確定最佳半徑位于[3.080,9.192]區間,然后通過三分法不斷改變區間的左右界限,并結合誤差判斷是否結束搜索。搜索結束時,Rk為5.17 m,對應的估計聲源坐標為(3.105,4.146),僅經過5次迭代搜索便可找到聲源最佳估計位置。對于文獻[17]的方法,通過改變三次步長進行迭代搜索,易知其計算復雜度為O(3n),而對于本文方法,通過將n/3處的元素與2n/3處的元素比較,將搜索范圍縮小為原來的n/3,其計算復雜度為O(2log3n)。

綜上所述,相比于文獻[17]提出的多圓聯動搜索聲源定位算法,本文算法不僅減小了迭代搜索的次數,并且減小了每次搜索時的計算復雜度。在加快定位速度的同時,有效提升了定位精度。

4 結 語

對于TDOA聲源定位系統中的定位估計階段,定位方程求解速度與定位精度是關鍵問題。較傳統的迭代搜索定位算法,多圓聯動搜索聲源定位算法有效提高了搜索速度和定位精度。本文提出利用三分法進行多圓聯動搜索的聲源定位算法,將非線性方程組轉化為線性方程組,并在迭代搜索的過程中引入三分法進行搜索,進一步提高了定位求解速度與定位精度。理論分析和實驗結果均證明了本文算法的優越性。未來的工作將研究減小時延估計誤差的方法并與本文算法相結合,進一步提高該算法的定位精度。