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

樓萬翔　黃　迪

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

?

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

樓萬翔黃迪

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

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

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

Class NumberTP391.41

1　引言

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

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

2　Hough變換的基本原理

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

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

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

(1)

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

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

圖2　Hough變換示意圖

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

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

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

(2)

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

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

(3)

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

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

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

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

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

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

假設在目標交叉期間內，目標的運動軌跡為近似為一條直線。基于Hough變換的目標交叉跟蹤算法就是基于以上假設而實現的。基于Hough變換的目標交叉跟蹤流程如圖3所示。

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

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

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

(4)

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

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

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

圖5　兩目標跟蹤軌跡對應的Hough域峰值點

(5)

(6)

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

圖6　Hough域峰值點

(7)

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

(8)

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

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

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

4　仿真分析

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

圖7　目標真實軌跡

圖8　目標跟蹤軌跡

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

5　結語

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

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

[2]李啟虎.數字式聲納設計原理[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變換及其在信息處理中的應用[M].北京：兵器工業出版社,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]王國宏,蘇峰.雜波環境下基于Hough變換和邏輯的快速航跡起始算法[J].系統仿真學報,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]何友,修建娟,關欣等.雷達數據處理及應用[M].北京：電子工業出版社,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日

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

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