基于Hough變換的目標交叉跟蹤算法*

樓萬翔　黃　迪

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

?

基于Hough變換的目標交叉跟蹤算法*

樓萬翔黃迪

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

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

Hough變換;被動跟蹤;交叉目標

Class NumberTP391.41

1　引言

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

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

2　Hough變換的基本原理

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

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

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

(1)

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

圖1　笛卡爾坐標系中的一條直線

圖2　Hough變換示意圖

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

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

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

(2)

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

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

(3)

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

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

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

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

3　基于Hough變換的目標交叉跟蹤

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

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

圖3基于Hough變換的目標跟蹤流程

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

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

(4)

該矩陣橫坐標表示波束號，縱坐標表示時間，矩陣中1表示目標在該時刻所在的波束號。

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

圖4　未達到處理門限前兩目標跟蹤軌跡

圖5　兩目標跟蹤軌跡對應(yīng)的Hough域峰值點

(5)

(6)

以兩目標位例，Hough域峰值點如圖6所示。

圖6　Hough域峰值點

(7)

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

(8)

在Hough域中得到最近的峰值點后，根據(jù)該峰值點確定目標的正確量測。

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

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

4　仿真分析

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

圖7　目標真實軌跡

圖8　目標跟蹤軌跡

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

5　結(jié)語

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

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

[2]李啟虎.數(shù)字式聲納設(shè)計原理[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]王國宏,孔敏,何友.Hough變換及其在信息處理中的應(yīng)用[M].北京：兵器工業(yè)出版社,2005.

[7]陶劍鋒,陶秀.基于Hough變換的被動聲納航跡起始[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]王國宏,蘇峰.雜波環(huán)境下基于Hough變換和邏輯的快速航跡起始算法[J].系統(tǒng)仿真學報,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)欣等.雷達數(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日

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

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