樓萬(wàn)翔　黃　迪

(中國(guó)船舶重工集團(tuán)公司第七一五研究所　杭州　310023)

?

基于Hough變換的目標(biāo)交叉跟蹤算法*

樓萬(wàn)翔黃迪

(中國(guó)船舶重工集團(tuán)公司第七一五研究所杭州310023)

被動(dòng)聲納目標(biāo)跟蹤中，常規(guī)跟蹤算法在目標(biāo)軌跡交叉時(shí)因目標(biāo)軌跡與量測(cè)關(guān)聯(lián)錯(cuò)誤會(huì)出現(xiàn)失跟或誤跟的現(xiàn)象。針對(duì)這一問(wèn)題，可通過(guò)Hough變換轉(zhuǎn)換域的方法對(duì)每個(gè)交叉目標(biāo)進(jìn)行分離關(guān)聯(lián)跟蹤。仿真結(jié)果表明，基于Hough變換的目標(biāo)交叉跟蹤算法能夠穩(wěn)定跟蹤兩個(gè)軌跡交叉的目標(biāo)。

Hough變換;被動(dòng)跟蹤;交叉目標(biāo)

Class NumberTP391.41

1　引言

在被動(dòng)聲納跟蹤中，常規(guī)算法通常利用方位信息進(jìn)行目標(biāo)軌跡和量測(cè)的關(guān)聯(lián)。在進(jìn)行單目標(biāo)跟蹤時(shí)，常規(guī)算法能夠順利跟蹤目標(biāo)；但當(dāng)同一時(shí)刻出現(xiàn)多目標(biāo)交叉時(shí)，常規(guī)算法往往會(huì)出現(xiàn)軌跡與量測(cè)錯(cuò)誤關(guān)聯(lián)，從而導(dǎo)致目標(biāo)失跟或誤跟[1～3]。如果能將上述目標(biāo)方位關(guān)聯(lián)通過(guò)轉(zhuǎn)換域的方法進(jìn)行分離關(guān)聯(lián)，應(yīng)該能夠避免此類(lèi)問(wèn)題的發(fā)生。

而轉(zhuǎn)換域的實(shí)現(xiàn)，可通過(guò)Hough變換實(shí)現(xiàn)。Hough變換是一種圖像處理方法，用于檢測(cè)圖像中的直線(xiàn)，同樣它可應(yīng)用于被動(dòng)聲納目標(biāo)跟蹤，解決多目標(biāo)軌跡交叉時(shí)軌跡與量測(cè)的關(guān)聯(lián)問(wèn)題。該方法是基于假設(shè)多目標(biāo)在交叉期間軌跡呈直線(xiàn)分布，利用Hough變換把軌跡和量測(cè)的方位關(guān)聯(lián)轉(zhuǎn)換為Hough域中峰值點(diǎn)的關(guān)聯(lián)，避免交叉判決混亂。

2　Hough變換的基本原理

Hough變換最早應(yīng)用于圖像處理中，是檢測(cè)圖像空間中圖像特征的一種基本方法，主要適用于檢測(cè)圖像空間中的直線(xiàn)[4～6]。由于可以將聲納經(jīng)過(guò)多次掃描得到的數(shù)據(jù)看作一幅圖像，因此可以使用Hough變換檢測(cè)目標(biāo)的軌跡?，F(xiàn)在Hough變換法已被廣泛地應(yīng)用于雷達(dá)數(shù)據(jù)處理中，并以成為多傳感器航跡起始和檢測(cè)低可觀(guān)測(cè)目標(biāo)的重要方法[7～11]，但是在被動(dòng)聲納中，使用Hough變換法進(jìn)行目標(biāo)跟蹤還是比較少見(jiàn)。Hough變換的基本思想是通過(guò)Hough變換方程建立起圖像空間到參數(shù)空間的映射，圖像空間中一點(diǎn)變換到參數(shù)空間中將對(duì)應(yīng)一條曲線(xiàn)或曲面，而具有相同參數(shù)特征的點(diǎn)在參數(shù)空間中將交于一點(diǎn)，通過(guò)峰值提取對(duì)交點(diǎn)進(jìn)行定位再對(duì)交點(diǎn)進(jìn)行反變換從而完成圖像空間中圖形的檢測(cè)。

設(shè)已知灰度圖像上一條直線(xiàn)，圖像空間笛卡爾坐標(biāo)系x-y中的直線(xiàn)用法線(xiàn)式表達(dá)式為

xcosθ+ysinθ=ρρ≥0,0≤θ≤π

(1)

其中，ρ為直線(xiàn)l到原點(diǎn)的距離，θ為直線(xiàn)l與x軸正方向的夾角，通常將以ρ-θ為參數(shù)的平面稱(chēng)為Hough空間。根據(jù)方程式，直線(xiàn)l上不同的點(diǎn)在參數(shù)平面ρ-θ中被變換為一簇相交于p點(diǎn)的正弦曲線(xiàn)，即在參數(shù)空間中交于公共點(diǎn)的曲線(xiàn)所對(duì)應(yīng)的笛卡爾坐標(biāo)系中的坐標(biāo)點(diǎn)一定在一條直線(xiàn)上。顯然，若能確定參數(shù)平面中的p點(diǎn)就實(shí)現(xiàn)了直線(xiàn)檢測(cè)，也就是說(shuō)圖像平面中的直線(xiàn)與參數(shù)平面中的點(diǎn)一一對(duì)應(yīng)，其原理如圖1、圖2所示。

圖1　笛卡爾坐標(biāo)系中的一條直線(xiàn)

圖2　Hough變換示意圖

Hough變換的具體實(shí)現(xiàn)時(shí)利用表決 ，即曲線(xiàn)上的每一點(diǎn)可以表決若干參數(shù)組合，贏得多數(shù)表決的參數(shù)就是勝者。在這種方法中，常把參數(shù)平面設(shè)計(jì)成一個(gè)累加器陣列，表示離散參數(shù)。依照變換方程，由圖像平面中的邊緣點(diǎn)數(shù)據(jù)區(qū)計(jì)算Hough空間中的參考點(diǎn)的可能軌跡，在一個(gè)累加器中統(tǒng)計(jì)處的參考點(diǎn)，最后選出峰值圖像中的每一個(gè)點(diǎn)可以表決幾個(gè)參數(shù)，而參數(shù)平面(或累加器陣列)的峰值就是表征一條直線(xiàn)的參數(shù)。具體實(shí)現(xiàn)步驟如下：

1)將ρ-θ平面中θ軸以一定的量化間隔Δθ離散地分割成若干小段，每小段的中心點(diǎn)為

θk=(k-1/2)Δθk=1,2,…,Nθ

(2)

其中，Δθ=π/Nθ，Nθ為參數(shù)θ的分割段數(shù)。

2)根據(jù)笛卡爾空間中的每個(gè)數(shù)據(jù)點(diǎn)(xi,yi)(i=1,2,…,n)和自變參數(shù)的每個(gè)離散值θn，計(jì)算ρi,θk，即ρik=xicosθk+yisinθk，將所有ρik保存到矩陣R中，得

(3)

3)給定因變量量化間隔Δρ，對(duì)所有ρi,θk進(jìn)行量化分區(qū)，得到矩陣R′；

4)根據(jù)矩陣R，通過(guò)一定的轉(zhuǎn)換關(guān)系定義參數(shù)空間積累矩陣A；對(duì)于矩陣R′中的所有元素ρ(i,j)考察是否對(duì)積累單元A(m,j)投票；若投票，則執(zhí)行A(m,j)=A(m,j)+1；

5)在積累矩陣中尋找局部峰值A(chǔ)(ρmax,θmax)；

6)根據(jù)峰值參數(shù)(ρmax,θmax)確定直線(xiàn)。

3　基于Hough變換的目標(biāo)交叉跟蹤

當(dāng)目標(biāo)軌跡未發(fā)生交叉時(shí)，常規(guī)的跟蹤算法能夠順利實(shí)現(xiàn)目標(biāo)跟蹤。當(dāng)目標(biāo)相互靠近，常規(guī)的方位關(guān)聯(lián)將失去作用。為了解決這個(gè)問(wèn)題，可通過(guò)Hough變換將目標(biāo)的方位跟蹤轉(zhuǎn)換到Hough域上進(jìn)行跟蹤。

假設(shè)在目標(biāo)交叉期間內(nèi)，目標(biāo)的運(yùn)動(dòng)軌跡為近似為一條直線(xiàn)?；贖ough變換的目標(biāo)交叉跟蹤算法就是基于以上假設(shè)而實(shí)現(xiàn)的。基于Hough變換的目標(biāo)交叉跟蹤流程如圖3所示。

圖3基于Hough變換的目標(biāo)跟蹤流程

基于Hough變換的目標(biāo)交叉跟蹤算法具體步驟如下：

2)Hough域轉(zhuǎn)換。假設(shè)在T1時(shí)刻交叉判定完成，且有L(2≤N≤M)個(gè)目標(biāo)落入交叉判決門(mén)限內(nèi)，提取L個(gè)目標(biāo)在T1-T0+1～T1-1時(shí)刻的跟蹤軌跡，T0的取值不能取得過(guò)大，因?yàn)槿绻麜r(shí)間過(guò)長(zhǎng)，目標(biāo)的跟蹤軌跡不能近似為一條直線(xiàn)，將會(huì)影響后續(xù)Hough域上的關(guān)聯(lián)。第l個(gè)目標(biāo)T1-T0+1～T1-1時(shí)刻的跟蹤軌跡用一(T0×波束數(shù))的矩陣Mal表示如下：

(4)

該矩陣橫坐標(biāo)表示波束號(hào)，縱坐標(biāo)表示時(shí)間，矩陣中1表示目標(biāo)在該時(shí)刻所在的波束號(hào)。

得到跟蹤軌跡矩陣后，利用Hough變換可得到第l個(gè)目標(biāo)在Hough域中的參數(shù)(ρl,θl)。以?xún)赡繕?biāo)為例，目標(biāo)跟蹤軌跡如圖4所示，跟蹤軌跡Hough域?qū)?yīng)的峰值點(diǎn)如圖5所示，其中T1=48,T0=5。

圖4　未達(dá)到處理門(mén)限前兩目標(biāo)跟蹤軌跡

圖5　兩目標(biāo)跟蹤軌跡對(duì)應(yīng)的Hough域峰值點(diǎn)

(5)

(6)

以?xún)赡繕?biāo)位例，Hough域峰值點(diǎn)如圖6所示。

圖6　Hough域峰值點(diǎn)

(7)

在Hough域上進(jìn)行最近鄰關(guān)聯(lián)，即在集合HoughPks′(T1)中尋找離(ρl,θl)最近的點(diǎn)，可得

(8)

在Hough域中得到最近的峰值點(diǎn)后，根據(jù)該峰值點(diǎn)確定目標(biāo)的正確量測(cè)。

4)交叉結(jié)束。Hough域關(guān)聯(lián)成功后，確定目標(biāo)所對(duì)應(yīng)的量測(cè)，更新目標(biāo)跟蹤軌跡。依次循環(huán)上述步驟，直至目標(biāo)運(yùn)動(dòng)至交叉判決門(mén)限外。

由以上分析可知，基于Hough變換的目標(biāo)交叉跟蹤算法把方位關(guān)聯(lián)轉(zhuǎn)換為Hough域關(guān)聯(lián)，避免了軌跡交叉時(shí)的判決混亂，在一定程度上能夠解決目標(biāo)因軌跡交叉發(fā)生失跟或誤跟的現(xiàn)象。但是如果目標(biāo)交叉時(shí)間過(guò)長(zhǎng)，遠(yuǎn)遠(yuǎn)超過(guò)時(shí)間T0，那么在Hough域上的峰值點(diǎn)將會(huì)出現(xiàn)交疊現(xiàn)象，從而導(dǎo)致關(guān)聯(lián)失效，因此該方法不適用目標(biāo)交叉時(shí)間過(guò)長(zhǎng)的情況。

4　仿真分析

為了驗(yàn)證算法的正確性，對(duì)其進(jìn)行仿真分析。仿真條件如下：96元線(xiàn)列陣按半波長(zhǎng)均勻布陣，基陣起始坐標(biāo)為(0,0)，跟蹤結(jié)束后的坐標(biāo)為(500,500)，期間為勻速直線(xiàn)運(yùn)動(dòng)，基陣工作頻率為500Hz～5000Hz，采樣頻率為12000Hz，采樣點(diǎn)數(shù)為1024?；嚤O(jiān)測(cè)范圍內(nèi)存在兩個(gè)目標(biāo)，目標(biāo)1的起始坐標(biāo)為(3000,3000)，跟蹤結(jié)束后的坐標(biāo)為(0,3000)；目標(biāo)2的起始坐標(biāo)為(500,5000)，跟蹤結(jié)束后的坐標(biāo)為(4000,3800)。交叉判定門(mén)限為4°，T0=15，目標(biāo)真實(shí)軌跡以及基于Hough變換的目標(biāo)交叉跟蹤算法的跟蹤軌跡如圖7、圖8所示。

圖7　目標(biāo)真實(shí)軌跡

圖8　目標(biāo)跟蹤軌跡

從仿真結(jié)果中可以看出，基于Hough變換的目標(biāo)交叉跟蹤算法能夠順利跟蹤兩個(gè)軌跡交叉的目標(biāo)。由此可得，該算法能夠解決因目標(biāo)軌跡交叉引起的失跟或誤跟問(wèn)題。

5　結(jié)語(yǔ)

基于Hough變換的目標(biāo)交叉跟蹤算法把方位量測(cè)關(guān)聯(lián)轉(zhuǎn)換為Hough域峰值點(diǎn)的關(guān)聯(lián)，避免了因軌跡交叉引起的量測(cè)判決混亂，一定程度上解決了目標(biāo)軌跡交叉失跟或誤跟目標(biāo)的問(wèn)題。但是，該方法的跟蹤性能的優(yōu)劣在很大程度上受T0取值的影響，而T0的取值沒(méi)有確定的規(guī)律，因此在后續(xù)的研究中如何選取T0顯得尤為關(guān)鍵。

[1]李啟虎.聲吶信號(hào)處理引論[M].北京：北京海洋出版社,1985:235-252.

[2]李啟虎.數(shù)字式聲納設(shè)計(jì)原理[M].合肥：安徽教育出版社,2003:321-342.

[3]C.R.Rao,L.Zhang,L.C.Zhao.Multiple Target angle tracking using sensor array outputs[J].IEEE Transactions on Aerospace and Electronic Systems,1993,29:268-271.

[4]Duda R.O,Hart P.E.Use of the Hough transform to detect lines and curves in pictures[J].Communication of the ACM,1972,15(1):11-15.

[5]J.Sklansky.On the Hough Technique for Curve Detection[J].IEEE Trans.On Comput,27(10):923-926.

[6]王國(guó)宏,孔敏,何友.Hough變換及其在信息處理中的應(yīng)用[M].北京：兵器工業(yè)出版社,2005.

[7]陶劍鋒,陶秀.基于Hough變換的被動(dòng)聲納航跡起始[J].船舶電子工程,2008,28(1):141-142.

[8]Kiril M,Alexiev.Implementation of Hough Transform as Track Detector.Proc.of the International Conf.on Multisource-Multisensor Information Fusion[C]//FUSION’,2000:ThC4-11-ThC4-16.

[9]王國(guó)宏,蘇峰.雜波環(huán)境下基于Hough變換和邏輯的快速航跡起始算法[J].系統(tǒng)仿真學(xué)報(bào),2002,14(7):37-42.

[10]Kiril M.Alexiew,Ljudmil V.Bojilov.A Hough Transform Track Inition Algorithm for Multiple Passive Sensors.Proc.of the International Conf.on Multisource-Mutisensor Information Fusion[C]//FUSION’,2000:TuB2-11-TuB2-16.

[11]何友,修建娟,關(guān)欣等.雷達(dá)數(shù)據(jù)處理及應(yīng)用[M].北京：電子工業(yè)出版社,2013:112-126.

Trace Intersecting Targets Tracking Based on Hough Transform

LOU WanxiangHUANG Di

(No.715 Research Institute,CSIC,Hangzhou310023)

Conventional algorithms will track the inaccurate target when the traces intersect because of failure in associating traces with measurements correctly in passive sonar tracking.An algorithm based on Hough Transform is presented to solve the problem.Target tracking is transformed into Hough field by Hough Transform to track trace intersecting targets separately.Computer simulation results indicate that the algorithm presented is able to track trace intersecting targets stably.

Hough transform,passive tracking,intersecting trace

2016年3月19日,

2016年5月3日

樓萬(wàn)翔，男，碩士研究生，助理工程師，研究方向：被動(dòng)聲納檢測(cè)跟蹤。黃迪，男，碩士研究生，工程師，研究方向：被動(dòng)聲納跟蹤和數(shù)據(jù)融合。

TP391.41DOI：10.3969/j.issn.1672-9730.2016.09.009