基于改進擬牛頓-K近鄰的TDOA定位算法

徐耀松,譚 亮

(遼寧工程技術大學電氣與控制工程學院,遼寧 葫蘆島 125105)

TDOA(Time Difference Of Arrival)方法在室內聲源定位是進行聲源定位的一種有效的方法[1]。主要分為兩個步驟:首先麥克風陣列獲取聲音信號到達麥克風陣列之間的時間差,獲得時間延遲;然后基于時間延遲求解非線性定位方程,求出聲源位置。對于非線性定位方程的求解方法主要分為兩類[2]:第1類為目標函數(shù)搜索的定位算法,這種方法需要對定位空間搜索遍歷,運算量大,常用的方法有最大似然估計法[3]、球型插值法[4];第2類方法根據(jù)傳感器的布設情況,直接解非線性方程得到所要求的坐標。解非線性方程常見的無約束一維極值的方法主要包括:黃金分隔法[5],進退法[6],牛頓法[7]等等;無約束多維極值的方法主要包括:模式搜索法[8],最速下降法[9],擬牛頓法[10]等等。因定位方程維度較高,所以在解定位方程時更加適用于使用無約束多維極值的方法。模式搜索法不用計算目標函數(shù)導數(shù),只需要計算函數(shù)值,但其不適用于目標函數(shù)復雜的情況下。最速下降法又稱為梯度下降法,易于編程,但其收斂速度并不快,在高維的優(yōu)化問題和精度要求較高的情況下,缺點更為明顯。一般情況下,該方法一般與其他算法配合使用。而擬牛頓方法在維度較高情況下可以較準確的得出非線性方程解,計算效率較高。因此選擇擬牛頓方法解定位方程。然而擬牛頓方法計算速度較慢,在時延估計存在噪聲的情況下,擬牛頓定位的準確度也有所下降,本文提出一種改進擬牛頓-K均值定位方法對聲源進行定位。提出一種近似矩陣替換雅可比矩陣,提高非線性定位方程擬牛頓算法求解的速度,根據(jù)噪聲性質改變K近鄰算法的距離,提高系統(tǒng)定位結果的準確性。

1 擬牛頓方法及其改進

定位估計系統(tǒng)可以看成解決非線性等式問題:

F(α)=0,α∈Rn

(1)

式中,α為聲源坐標向量,若為三維空間定位,α則為三維坐標。

傳統(tǒng)的擬牛頓的方法的迭代公式為:

Jk(αk+1-αk)=F(αk)

(2)

式中,Jk是非線性定位方程F(αk)的雅可比矩陣。利用定位估計非線性方程F與其一階導數(shù)g包含的信息,得到目標函數(shù)的曲率近似,具有易實現(xiàn)的特點。但是當計算維數(shù)較高時,求解雅可比矩陣的花銷就變大,為解決雅可比陣運算花銷大的問題,利用下式替換擬牛頓算法的雅可比矩陣[11]

(3)

式中,Uk為雅可比矩陣的近似陣,vk=αk+1-αk,fk=F(αk+1)-F(αk),利用近似矩陣Uk代替雅可比矩陣Jk。如式(4)和式(5)所示:

Uk(αk+1-αk)=F(αk)

(4)

Uk+1(αk+1-αi)=F(αk+1)-F(αi),i∈[0,k]

(5)

令vk=αk+1-αk,Jk=J(αk),得到新的擬牛頓等式:

(6)

將式(6)代入式(2),求導:

(7)

由于時延估計結果的定位方程為二次的,可以用如下二次方程R(i)逼近定位系統(tǒng):

R(i)=ai2+bi+c

(8)

式中,a,b,c為各項系數(shù)。為逼近時延估計的定位方程,式(8)需要滿足以下條件:

R(0)=F[α(0)]=F(αk)=Fk

R(‖vk‖)=F[α(‖vk‖)]=F(vk+1)=Fk+1

R(-‖vk-1‖)=F[α(-‖vk-1‖)]=F(vk-1)=Fk-1

則可得到:

(9)

(10)

c=Fk

(11)

同樣地,將式(9)～式(11)代入式(8)并求導得到:

(12)

令式(12)和式(7)相等,并令fk=Fk+1-Fk得出:

(13)

簡化上式,令:

(14)

(15)

從而:

Jk+1χk=γk

(16)

如果用Uk逼近Jk,則:

Uk+1χk=γk

(17)

最后,由式(3),(14)和(15)得到的更新Uk的公式如下:

(18)

由于式(18)中的近似矩陣Uk與αk-1、αk、αk+1三項的取值有關,因此在解方程時,首次迭代使用構造雅可比矩陣的擬牛頓方法;第2次迭代使用BBM方法;之后便可利用式(18)的近似矩陣更新迭代公式,直至滿足停止條件,迭代結束。具體運算步驟為:①設置迭代起始點α0,求取雅可比矩陣J0,令U0=J0。②通過U0v0=-F(α0),求取v0進而求取α1,f0。③通過式(3)求得U1,使用U1v1=-F(α1)求取v1,α2,f1。④通過式(14)、式(15)求得χ1,γ1。⑤通過式(18)求得Uk,并通過Ukvk=-F(αk)求取vk,αk,fk。觀察αk是否滿足停止條件。滿足則結束迭代;不滿足則k=k+1并返回步驟④。

2 基于改進K近鄰算法的定位估計

在室內聲源定位過程中時延估計結果容易受到環(huán)境噪聲的影響,在觀測次數(shù)有限的情況下,尤其是實時性要求較高的場合,采用改進擬牛頓定位方法會產生較大的誤差。為了提高定位的準確性,降低時延估計噪聲對結果的影響,提高算法的魯棒性,提出采用改進的K近鄰方法進行定位結果的最優(yōu)估計。

2.1 K近鄰學習方法

K近鄰學習算法根據(jù)提供測試的樣本,通過比較待測樣本和提供樣本之間的距離度量,選擇最靠近的K個樣本點,使用這K個樣本點對結果進行估計[12]。

例如對同一個點估計20次,把20次定位的平均值作為學習樣本輸入,將20次估計點作為待學習的樣本。通過計算學習樣本和待學習樣本之間的距離,一般采用歐式距離:

(19)

式中,x*是學習例子,xi是待學習例子,將計算的結果進行排序,選擇距離最近的K個值,達到抑制噪聲的目的。

2.2 K近鄰的改進方法

實際中由于提供的估計點數(shù)有限,使用傳統(tǒng)的均值方法選擇學習樣本的效果并不理想,K近鄰算法中單純基于歐式距離的求解精確程度不高。本文提出采用密集距離法估計定位點,即計算有限含噪估計點的相互距離,而非估計點到均值點的距離,如下

rij=|xixj|

(20)

式中,i,j=1,2,…,n且i≠j。通過距離rij,尋找距離之和最短且成群的點集,將均值點作為學習樣本,使用K近鄰算法選出K個點,采用打分方法選擇合適的權值。

該方法實施時,可根據(jù)最大距離與估計點比值設置多個距離閾值?1,?2,…,?t,在閾值內的距離值可以獲得相應的分值βi,i∈t,距離越近分值越高;多個點距離在最小距離閾值內且聚集在一起也會得到分數(shù)的加成βt(n-1),i∈t,n是聚集點數(shù)。

然后,根據(jù)下式求出聲源位置:

(21)

綜上所述,基于IQN-IKN方法的TDOA定位過程可概括如下:①通過麥克風陣列得到時延估計結果,得到定位方程。②通過改進的擬牛頓方法求出方程組的解。③采用改進K近鄰的方法對估計誤差進行抑制,優(yōu)化定位的準確度。

3 實驗分析

3.1 二維空間定位實驗

為驗證方法的快速和準確性,分別采用改進擬牛頓方法和傳統(tǒng)擬牛頓方法在二維空間進行比較。定位區(qū)域是150 cm×150 cm的平面,麥克風傳感器設置在一角并建立笛卡爾坐標系,設置在坐標(0,10),(10,0),(-10,0)和(0,-10)的位置(單位:cm),如圖1所示。

圖1 實驗布局圖

將聲源(頻率為100 Hz～5 000 Hz,主要為語音信號)設定在第一象限中,設定固定的迭代起始點(2,2)(單位:cm),停止條件為誤差0.000 1(單位:cm)。隨機放置聲源,分別采用擬牛頓算法和改進擬牛頓算法進行多次聲源定位對結果求取平均值,測試結果如表1所示。

表1 不同聲源的迭代計算結果

表1結果表明改進擬牛頓算法相對于傳統(tǒng)擬牛頓算法進行聲源定位的速度更快。以聲源位置為(8,10)(單位:cm)為例,比較兩種算法每一次迭代的誤差和時間。如圖2所示。

圖2 定位結果誤差對比

可見改進擬牛頓的算法相對于擬牛頓每次迭代的速度更快,同一迭代周期內的誤差更小。

3.2 三維空間定位實驗

實驗場所設置為長5 m,寬3 m,高2 m的三維空間,同樣建立三維笛卡爾坐標系。將聲音傳感器設置在x,y,z軸的距離原點10cm的位置。如圖3所示。

圖3 室內布局圖

圖4 含噪定位點與定位點

選擇迭代的起始點是(50,50,50)(單位:cm),設置迭代停止條件為最小均方差為1cm,隨機選擇空間點進行多次定位并計算均值。記錄擬牛頓方法和改進擬牛頓方法的迭代次數(shù)和運算時間。

三維空間定位實驗結果證明,改進擬牛頓比傳統(tǒng)擬牛頓方法在三維空間定位的速度明顯更快。相對于二維空間定位實驗結果,定位的維度越高,采用改進擬牛頓算法比傳統(tǒng)擬牛頓的收斂速度更快。

表2 不同聲源位置的迭代計算結果

3.4 含噪聲情況的聲源定位估計

為了驗證含噪聲情況下改進擬牛頓方法的聲源定位效果,對二維空間點(75,75)(單位:cm)定位并在時延估計結果中分別加入信噪比為0 dB,10 dB,20 dB,30 dB的高斯白噪聲,采用擬牛頓方法的定位結果如圖4所示。

可見,在噪聲影響下改進擬牛頓方法的定位結果產生誤差,甚至會產生偏離較大的異常定位結果,針對這一問題,采用本文提出的改進K近鄰方法優(yōu)化定位估計結果。

為驗證本文方法的性能,分別使用均值、K近鄰和改進K近鄰方法進行定位求解。

選擇10組估計點并對每一組數(shù)據(jù)分別加入信噪比0 dB、10 dB、20 dB和30 dB噪聲后進行估計20次,分別用均值方法、K均值方法以及改進K均值方法估計定位點。得出定位結果均值如表3～表6 所示。

從表3～表6可以看出改進K近鄰方法能夠獲得更準確的二維空間定位估計。

選擇一處高3.5 m,長6 m,寬4 m的空間。在室內的角落搭建實驗設備。選擇的聲源是一個5 V的有源蜂鳴器,其頻率在語音頻率內為(2 300±500)Hz。隨機選擇位置進行定位估計。實驗結果如表7所示。

表3 二維空間信噪比為0 dB定位結果

表4 二維空間信噪比為10 dB定位結果

表5 二維空間信噪比為20 dB定位結果

表6 二維空間信噪比為30 dB定位結果

表7 三維空間含噪聲定位結果

從表7可以看出,改進K近鄰方法具有很好的魯棒性,并且定位誤差小。改進K近鄰算法優(yōu)化室內定位效果明顯。

4 結論

對于TDOA聲源定位系統(tǒng)定位估計階段,定位方程求解速度和環(huán)境噪聲是影響定位系統(tǒng)主要問題。本文提出IQN-IKN算法,構造二次方程逼近定位估計的定位方程,得到近似雅可比矩陣并用其代替?zhèn)鹘y(tǒng)擬牛頓中的雅可比矩陣,減少了系統(tǒng)定位的時間,提高定位求解速度;在含噪聲環(huán)境下,采用基于密集距離和打分策略的改進K近鄰方法估計定位點,在不減少定位時間的前提下,同樣能夠提高定位方法的準確性和魯棒性。本方法可以用于室內和信噪比較大的戶外聲源定位場合。