基于改進(jìn)擬牛頓-K近鄰的TDOA定位算法

徐耀松,譚 亮

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

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

1 擬牛頓方法及其改進(jìn)

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

F(α)=0,α∈Rn

(1)

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

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

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

(2)

式中,Jk是非線性定位方程F(αk)的雅可比矩陣。利用定位估計(jì)非線性方程F與其一階導(dǎo)數(shù)g包含的信息,得到目標(biāo)函數(shù)的曲率近似,具有易實(shí)現(xiàn)的特點(diǎn)。但是當(dāng)計(jì)算維數(shù)較高時(shí),求解雅可比矩陣的花銷就變大,為解決雅可比陣運(yùn)算花銷大的問題,利用下式替換擬牛頓算法的雅可比矩陣[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),求導(dǎo):

(7)

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

R(i)=ai2+bi+c

(8)

式中,a,b,c為各項(xiàng)系數(shù)。為逼近時(shí)延估計(jì)的定位方程,式(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)并求導(dǎo)得到:

(12)

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

(13)

簡(jiǎn)化上式,令:

(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三項(xiàng)的取值有關(guān),因此在解方程時(shí),首次迭代使用構(gòu)造雅可比矩陣的擬牛頓方法;第2次迭代使用BBM方法;之后便可利用式(18)的近似矩陣更新迭代公式,直至滿足停止條件,迭代結(jié)束。具體運(yùn)算步驟為:①設(shè)置迭代起始點(diǎn)α0,求取雅可比矩陣J0,令U0=J0。②通過U0v0=-F(α0),求取v0進(jìn)而求取α1,f0。③通過式(3)求得U1,使用U1v1=-F(α1)求取v1,α2,f1。④通過式(14)、式(15)求得χ1,γ1。⑤通過式(18)求得Uk,并通過Ukvk=-F(αk)求取vk,αk,fk。觀察αk是否滿足停止條件。滿足則結(jié)束迭代;不滿足則k=k+1并返回步驟④。

2 基于改進(jìn)K近鄰算法的定位估計(jì)

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

2.1 K近鄰學(xué)習(xí)方法

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

例如對(duì)同一個(gè)點(diǎn)估計(jì)20次,把20次定位的平均值作為學(xué)習(xí)樣本輸入,將20次估計(jì)點(diǎn)作為待學(xué)習(xí)的樣本。通過計(jì)算學(xué)習(xí)樣本和待學(xué)習(xí)樣本之間的距離,一般采用歐式距離:

(19)

式中,x*是學(xué)習(xí)例子,xi是待學(xué)習(xí)例子,將計(jì)算的結(jié)果進(jìn)行排序,選擇距離最近的K個(gè)值,達(dá)到抑制噪聲的目的。

2.2 K近鄰的改進(jìn)方法

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

rij=|xixj|

(20)

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

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

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

(21)

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

3 實(shí)驗(yàn)分析

3.1 二維空間定位實(shí)驗(yàn)

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

圖1 實(shí)驗(yàn)布局圖

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

表1 不同聲源的迭代計(jì)算結(jié)果

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

圖2 定位結(jié)果誤差對(duì)比

可見改進(jìn)擬牛頓的算法相對(duì)于擬牛頓每次迭代的速度更快,同一迭代周期內(nèi)的誤差更小。

3.2 三維空間定位實(shí)驗(yàn)

實(shí)驗(yàn)場(chǎng)所設(shè)置為長(zhǎng)5 m,寬3 m,高2 m的三維空間,同樣建立三維笛卡爾坐標(biāo)系。將聲音傳感器設(shè)置在x,y,z軸的距離原點(diǎn)10cm的位置。如圖3所示。

圖3 室內(nèi)布局圖

圖4 含噪定位點(diǎn)與定位點(diǎn)

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

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

表2 不同聲源位置的迭代計(jì)算結(jié)果

3.4 含噪聲情況的聲源定位估計(jì)

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

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

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

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

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

選擇一處高3.5 m,長(zhǎng)6 m,寬4 m的空間。在室內(nèi)的角落搭建實(shí)驗(yàn)設(shè)備。選擇的聲源是一個(gè)5 V的有源蜂鳴器,其頻率在語(yǔ)音頻率內(nèi)為(2 300±500)Hz。隨機(jī)選擇位置進(jìn)行定位估計(jì)。實(shí)驗(yàn)結(jié)果如表7所示。

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

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

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

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

表7 三維空間含噪聲定位結(jié)果

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

4 結(jié)論

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