并行Hough變換航跡起始

鹿傳國*① 馮新喜① 孔云波① 曾 蓉② 李紅英①③

?

并行Hough變換航跡起始

鹿傳國馮新喜孔云波曾 蓉李紅英

(空軍工程大學信息與導航學院 西安 710077)(94936部隊 杭州 310021)(93861部隊 西安 710038)

Hough變換作為一種批處理航跡起始方法，混淆了傳感器量測數據的時序信息，難以克服單次掃描數據的累積效應。該文通過改變Hough變換處理結構和計數器累加方式，提出了一種并行處理結構的Hough變換航跡起始算法。該算法利用Hough變換將不同時刻的量測集合分別映射到參數空間，繼而將空間中具有相同索引的各次累加結果構成累加向量；再根據建立的參數空間累加規則，利用滑窗法來確定累積矩陣的輸出，最后通過門限檢測實現航跡起始判決。對密集雜波環境下不同掃描周期下的航跡起始問題進行了仿真驗證，結果表明了并行Hough變換起始算法的有效性。

航跡起始；Hough變換；并行

1 引言

航跡起始是多目標航跡處理的首要問題。強烈的軍事需求使其得到了極大的發展，各種起始算法層出不窮。當前航跡起始算法主要包括順序處理和批處理兩類，批處理技術主要是指基于Hough變換的起始方法， Smith等人最先把Hough變換引入到航跡起始領域，將航跡起始問題轉化為特征曲線檢測問題，其后Hough變換便因其良好的雜波抑制能力和優異的起始效果得到了廣泛的關注和極大的發展。提高Hough變換起始性能的研究多集中在下述方面：

(1) 提高Hough變換的時效性。標準Hough變換的計算量極大，低信噪比情況下尤甚，無法實現快速起始。提高時效性多采用如下方式：一是盡可能地簡化輸入數據，如修正Hough變換，利用目標運動學參數等通過設定限制規則來嚴格起始判決，隨機Hough變換方法又進一步采用隨機采樣代替遍歷式投票，犧牲航跡起始性能換取時效性；二是調整參量空間的分割情況，如快速Hough變換，迭代細分參數空間，在減少計算量的同時，降低了存儲空間；三是基于Hough變換分解定理，利用多個非相干完全子集的Hough變換之和作為目的數據集合的Hough變換，利用分布式并行計算結構來提高運算速度；四是改進計數器的投票方式，如文獻[7]給出了基于觀測空間參考點參數的投票方法，大大降低了投票所需的計算量。

(2) 提高Hough變換的雜波抑制能力。電子干擾和環境噪聲等所造成的雜波容易形成虛假航跡，同時可能惡化真實航跡質量，引起航跡的分叉、分段等。Hough變換本身可以通過利用“真實航跡成直線”這一幾何特性來抑制雜波，但往往需要多次掃描才能獲得較好的效果。文獻[8]討論了多傳感系統的航跡起始問題，該體制可充分利用多傳感器的冗余量測信息相互驗證來消除雜波影響；文獻[9]則直接將Hough變換應用于預處理階段，再采用邏輯法來完成航跡起始判決。

(3) 克服傳感器量測誤差影響。量測誤差帶來的直接后果是破壞了真實航跡成直線的幾何特性，在利用Hough變換時使得本位于同一直線的點難以準確在參數空間某一點上累積，導致峰值簇擁。克服量測誤差影響通常采用以下方法：一是改變Hough變換計數器的累加尺度，如模糊Hough變換、概率網格Hough變換等，用[0,1]區間上表征量測數據概率的模糊數來代替“非0即1”的累加步長，可有效緩解峰值簇擁現象，文獻[13]則利用觀測數據鄰域內的多個點跡代替單一的量測數據進行投票；二是采用序列Hough變換方法，每次只檢測最大值，同時將對該單元投票的量測予以刪除，直到最大值到達預先設定值。

(4) 降低Hough變換結果對參數的敏感性。利用Hough變換實現航跡起始，往往需設定門限、參數空間分割尺度等諸多參數，然而目前并無嚴格的數學理論支持此類參數的選擇。文獻[5]可智能化調整參數空間的分割尺度；文獻[14,15]分別提出利用多尺度Mean-shift聚類和減法聚類來起始航跡，這種無監督聚類方法可以自適應地確定聚類中心，無需門限設定即可實現航跡起始判決。

綜上所述不難發現，Hough變換的改進算法幾乎涉及其處理過程的方方面面。Hough變換作為一種批處理算法，不同時刻的量測數據對處理中心來說是無差別的，這種時序上的模糊使得單次掃描數據易形成虛假航跡，究其原因在于Hough變換無法充分利用量測數據的時序信息。Hough變換最初是針對圖像處理領域提出的，所處理的數據均是沒有時序性的圖元數據，即像素點，并不存在時間相關性，而航跡起始所處理的數據是具有明顯的時間相關性的廣義時間序列，Hough變換起始易因單次掃描數據的累積形成虛假航跡。

針對上述問題，本文設計了一種并行結構的Hough變換起始算法，同時改變了Hough變換的計數器累加模式。具體說來，就是對不同時刻的雷達量測數據并行地進行Hough變換，得到參數空間里的多個累加矩陣，繼而將具有相同-索引的累加結果構成“累加向量”，而非簡單的求和，通過統計“累加向量”非零元素的個數來確定參數空間最終的累積結果的取值，繼而借鑒修正邏輯法設定累加結果輸出的規則。最后對所提算法進行了實驗仿真，驗證了其有效性。

2 Hough變換航跡起始

2.1 Hough變換原理

Hough變換能夠將笛卡爾空間中的點映射為參數空間中的曲線或曲面，則笛卡爾空間中滿足某特性的點集將在變換后交于參量空間一點，統計交點處的累加程度來檢測特征曲線或曲面。

(2)

2.2 Hough變換起始算法

Hough變換航跡起始算法步驟如下：

Step 1確定方格容量，劃分參數區間，確定方格坐標。參數區間的劃分直接影響航跡起始的質量，容量參數取值愈小，則參數空間劃分愈加精細，起始航跡的質量越高，但容易造成漏檢，而容量參數取值過大則不至于產生漏警。

Step 2 Hough變換，采用Carlson提出的多維矩陣變換法。記笛卡爾空間中點的坐標為，其中為集合的勢，則量測數據集合可表示為

定義轉換矩陣

:(4)

Hough變換即可轉化為如下的矩陣乘積問題：

(6)

2.3 Hough變換問題分析

利用Hough變換檢測航跡時，同一掃描時刻量測集合中的雜波和真實目標點跡形成的直線往往易被判別為真實航跡，而這顯然是虛假航跡。如圖1所示，圖1中左圖的點分別代表了不同時刻同一目標的量測點跡，是與同一時刻的雜波。Hough變換后可得參數空間中3條曲線和，如圖1中右圖所示，3條曲線的交點分別記為,,，則對應的計數器值均為2。都是因雜波的影響而形成的虛假航跡，但又有所不同，點所對應的量測和雜波來源于不同的時刻，點所對應的量測和雜波來自同一時刻，而同一時刻的點跡顯然是無法形成航跡的。Hough變換無法處理此類情況，特別是在密集雜波環境下，往往單次數據的累加即可達到很高的峰值，形成大量的虛假航跡，這將大大提高虛假航跡起始的風險。

3 并行Hough變換

3.1 并行Hough變換處理結構

需指出的一點是，這里的并行實際上指的是多次掃描數據分別進行Hough變換，而由于掃描數據具有時序性，因此只要Hough變換處理時間小于傳感器掃描周期，即可序貫地使用同一Hough處理單元完成參數空間的映射工作，而無需增加新的計算單元。

圖1 雜波影響示意圖

圖2 并行Hough變換結構圖

3.2 參數空間累加方式

完成并行Hough變換后，需要對航跡所得的參數空間數值進行處理。為充分利用和區分多次掃描數據的時序信息，抑制單次掃描數據的累加效應而引起的虛假航跡，采用一個累加向量來存儲相應索引的多次掃描的累加結果。如將該向量求和，則與經典的Hough變換結果一致。

考察一條真實的航跡，在理想情況下，按照并行Hough變換而得的累加向量應該具有一個明顯的特點：各分量均大于零。然而量測誤差不可避免，可能導致某些分量為零，鑒于量測誤差的隨機性，可認為那些大多數分量非零的累加向量可進行航跡起始，即用累加向量非零元素的個數作為航跡起始的依據之一。

記基于前時刻所有量測數據并行Hough變換所得參數累加矩陣為，對第次掃描數據集合進行Hough變換得到的參數空間累加矩陣為，其中。

3.3 參數空間累加規則

圖3 參數空間累加規則

設定的參數累加規則如下：

If, then(9)

If, then(10)

3.4 航跡起始算法

至此，并行Hough變換航跡起始算法可歸結如下：

Step 1將多次掃描數據集合按圖2所示方式并行地進行Hough變換，Hough變換具體方法見2.2節；

Step 2按3.2節所述構造累加向量，基于3.3節設定的規則對累加向量進行處理，得到最終的累加矩陣；

4 實驗仿真

為驗證所提航跡起始的有效性，研究了雜波下快速起始問題和一般起始問題，分別從參數空間累積情況、航跡起始結果和預處理能力3方面對標準Hough變換、文獻[17]所提Hough變換和本文所提并行Hough變換的性能進行了分析和比較。

4.1 實驗場景設置

假設傳感器探測范圍為一正方形區域，其4個頂點的坐標分別為(0,0),(0,100),(100,0),(100,100)，單位：km。雷達的探測周期為=6 s，雷達的徑向距離量測誤差和方位角量測誤差為高斯白噪聲，其標準差分別為。

假設5個目標均作勻速直線運動，5個目標的初始位置為(55,55),(45,55),(35,35),(25,45), (15,55)，速度相同，均為。圖4給出了持續6次掃描各目標的真實運動狀態。

4.2 實驗數據分析

4.2.1參數空間累積情況對比 圖7和圖8分別給出了4次和6次掃描周期下上文所述3種不同算法的參數空間累加情況，包括直方圖和峰值俯視圖。

將圖7和圖8(b), 8(c), 8(d)分別與圖8(a)進行對比，圖8(b)和圖8(d)中的參數空間累積峰值與真實航跡的參數空間累積峰值較為接近，而圖8(c)中的參數空間累積峰值與掃描次數相同，已與真實航跡產生了較大偏差，且過小的峰值使得參數空間的分辨率大大降低；對比圖8(b), 8(c), 8(d)，圖8(b)和圖8(c)的峰值簇擁程度要顯著高于圖8(d)，在多次掃描時更加明顯；從參數空間俯視圖可以看出，并行Hough變換獲得的參數累積直方圖較為稀疏，這是參數空間累積規則的約束所引起的，它可直接剔除單次掃描數據所引起的疊加效應。此外，這一參數空間中的稀疏化可以明顯降低參數空間中的數據量，對簡化聚類起始算法計算量具有重要意義。

圖4真實目標航跡

圖5 4次掃描雜波分布圖

圖6 6次掃描雜波分布圖

4.2.2 起始結果對比 單次蒙特卡羅仿真的實驗結果如圖9和圖10所示，兩圖分別給出了4次和6次掃描周期下經Hough變換、文獻[17]算法和并行Hough變換經門限判決后回溯至參數空間所得的航跡起始結果。

圖9 4次掃描航跡起始結果圖

圖10 6次掃描航跡起始結果圖

對比圖9和圖10中的各圖不難發現，Hough變換在密集雜波下雖可以檢測出真實航跡，但仍保留了大量的雜波，仍需要借助于進一步改進才能保證有效的航跡起始；文獻[16]所提算法在對雜波的消除方面與標準Hough變換相比改進較小；與前兩種算法相比，并行Hough變換起始結果所包含的雜波數據最少，這證明該算法可以有效抑制雜波的影響，與此同時，該算法能夠較好地保留真實目標的航跡數據。

4.2.3 預處理能力分析 Hough變換本身可以作為一種剔除雜波的預處理方式，通常做法是將門限值設定為一個較小的數值，將低于該門限的參數空間置零(實驗中門限被設定為參數空間累積最大值的二分之一)。在完成預處理之后，便可采用邏輯法、聚類法等來起始航跡。對不同雜波密度下3種不同Hough變換的預處理結果進行了量化，主要從保持真實航跡和剔除雜波能力兩方面進行分析。

航跡保持度：

雜波抑制度：

(12)

表1 預處理能力對比()

Tab. 1 Preprocessing ability comparison ()

Tab. 1 Preprocessing ability comparison ()

起始算法試驗結果 4次掃描6次掃描 Hough0.97200.18810.99730.0702 文獻[17]1.00000.21290.93130.3547 本文算法0.96800.21720.96070.3572

表2 預處理能力對比()

Tab. 2 Preprocessing ability comparison ()

Tab. 2 Preprocessing ability comparison ()

起始算法試驗結果 4次掃描6次掃描 Hough0.96600.13730.99600.0877 文獻[17]1.00000.14580.93800.3878 本文算法0.96700.14870.95800.3902

表3 預處理能力對比()

Tab. 3 Preprocessing ability comparison ()

Tab. 3 Preprocessing ability comparison ()

起始算法試驗結果 4次掃描6次掃描 Hough0.98600.06701.00000.0111 文獻[17]0.98900.06890.99670.0686 本文算法0.98600.07020.99730.0710

表4 預處理能力對比()

Tab. 3 Preprocessing ability comparison ()

Tab. 3 Preprocessing ability comparison ()

起始算法試驗結果 4次掃描6次掃描 Hough0.99800.06211.00000.0115 文獻[17]1.00000.06201.00000.0468 本文算法0.99700.06321.00000.0474

綜合表1-表4的數據，不難看出：

(1) 在航跡保持度方面，3種算法均位于一個十分理想的水平，降低了真實目標量測數據被誤剔除的風險，可很好地保持目標航跡的完整性；

(2) 在雜波抑制度方面，并行Hough變換表現最優，與標準Hough變換相比有很大提高(達到標準Hough變換的4～8倍)，較之文獻[17]所提算法亦有一定程度的提升，可有效地降低雜波數量，在減少計算量的同時，還可顯著提高航跡起始的性能。

5 總結

Hough變換是一種有效的航跡起始方法，然而作為一種批處理技術，無法區分不同時刻航跡數據對參數空間累加值的貢獻程度。而并行Hough變換算法，改變了求和式的參數空間累加方式，同時引入“累加向量”分析各時刻量測集合的參數空間累加情況，通過設定邏輯規則處理累加向量來確定參數空間最終的累加結果。與Hough變換直接求和的累加方式相比，有效克服了單次量測數據的累加效應，大大降低了虛假航跡的起始風險。

從并行Hough變換的數據處理結構來看，主要是將各次掃描的量測數據分別進行Hough變換，因此可以采取增加Hough變換處理單元的方法實現分布式并行計算方式以縮短Hough變換的處理時間，或者在特定條件下利用同一Hough變換處理單元對各次掃描數據序貫處理。從雜波抑制能力上看，在密集雜波環境下，并行Hough變換可有效地克服雜波影響，同時較好地保持真實的航跡信息。綜上分析，不難發現，該算法具有一定的優勢來快速起始航跡。

需指出的一點是，所提算法重在改變Hough變換的處理結構，在下一步的工作中也可引入模糊、概率網格、修正邏輯思想，還可與自適應聚類等算法相結合，以進一步提高航跡起始算法的魯棒性。

[1] 何友, 修建娟, 張晶煒, 等. 雷達數據處理及應用[M]. 北京:電子工業出版社.

He You, Xiu Jian-juan, Zhang Jing-wei,.. Radar Data Processing with Applications[M]. Beijing: Publishing House of Electronics Industry.

[2] Smith M C and Winter E M. Feature space transform for multi-target detection[C]. IEEE Confon Decision and Control Albuqureque, NM, 1980: 835-836.

[3] Chen J, Leung H, Lo T,.. A modified probabilistic data association filter in real clutter environment[J]., 1996, 32(1): 300-314.

[4] Xu L and Oja E. Randomized Hough Transform(RHT): basic mechanism, algorithms, and computer complexities[J].:, 1993, 57(2): 131-154.

[5] Li H, Lavin M A, and Le Maste. Fast Hough transform: a hierachical approach[J].&, 1986, 36: 112-117.

[6] Duquenoy E and Taleb-Ahmed A. Applying the Hough transform pseudo-linearity property to improve computing speed[J]., 2006, 27: 1893-1904.

[7] Xia Dong, Cha Hao, and Xiao Chunsheng. A new Hough transform applied in track initiation[C]. 2011 International Conference on Consumer Electronics, Communications and Networks (CECNet), April 2011: 16-18.

[8] Yankowich S W and Farooq M. Hough transform based multisensor, multitarget, track initiation technique[J]., 1998, 37(7): 2064-2077.

[9] 王國宏, 蘇峰, 毛士藝, 等. 雜波環境下基于Hough變換和邏輯的快速航跡起始[J]. 系統仿真學報, 2002, 14(7): 873-875.

Wang Guo-hong, Su Feng, Mao Shi-yi,.. Fast track initiation algorithm in clutter environments based on Hough transform and logic[J]., 2002, 14(7): 873-875.

[10] 康莉, 謝維信, 黃敬雄. 基于模糊Hough變換的被動傳感器系統航跡起始方法[J]. 系統工程與電子技術, 2007, 29(11): 1803-1805.

Kang Li, Xie Wei-xin, and Huang Jing-xiong. Track initialization algorithm based on fuzzy Hough transform for passive sensor systems[J]., 2007, 29(11): 1803-1805.

[11] 吳澤民, 任姝婕, 倪明放. 基于模糊累積函數的航跡起始問題研究[J]. 系統工程與電子技術, 2009, 31(5): 1213-1216.

Wu Ze-min, Ren Shu-jie, and Ni Ming-fang. Track initialization based on fuzzy accumulation function[J]., 2009, 31(5): 1213-1216.

[12] 趙志超, 饒彬, 王雪松, 等. 基于概率網格Hough變換的多雷達航跡起始算法[J]. 航空學報, 2010, 31(11): 2209-2215.

Zhao Zhi-chao, Rao Bin, Wang Xue-song,.. Multi-radar track Initiation algorithm based on probabilistic grid Hough transform[J].&, 2010, 31(11): 2209-2215.

[13] Shu Lingjin, Yan Liang, Peng He,.. An efficient Hough transform based track initiation[C]. Proceedings of the Fifth International Conference on Machine Learning and Cybernetics, Dalian, 2006: 3196-3200.

[14] 金術玲, 梁彥, 潘泉, 等. 基于Hough變換和聚類的航跡起始算法[J]. 系統仿真學報, 2009, 21(8): 2382-2385.

Jin Shu-ling, Liang Yan, Pan Quan,.. Track initiation algorithm based on Hough transform and clustering[J]., 2009, 21(8): 2382-2385.

[15] Zhang Yanhang, Su Xiaohong, and Ma Peijun. Multi-Hough transform track initiation for detecting target with constant acceleration[C]. International Symposium on Information Science and Engineering, 2008.

[16] 劉航, 竇麗華, 董領遜. 基于改進積累方式的Hough變換和最小方差航跡起始方法[J]. 火力與指揮控制, 2009, 34(2): 114-117.

Liu Hang, Dou Li-hua, and Dong Ling-xun. The track initiation approach based on improved accumulation method of Hough transform and least-square[J]., 2009, 34(2): 114-117.

[17] Matteo S, Pierfrancecesco L, and Alfonso F. A modified M/N logic for track initiation of low observable targets using amplitude information[C]. International Radar Symposium, 2006: 1-4.

[18] Charlson B D, Evans E D, and Wilson S L. Search radar detection and track with the hough transform, Part I: system concept[J]., 1995, 30(1): 102-108.

Track Initiation Based on Parallel Hough Transform

Lu Chuan-guoFeng Xin-xiKong Yun-boZeng RongLi Hong-ying

(School of Information and Navigation, Air-force University, Xi’an 710077, China)(Army Unite 94936, Hangzhou 310021, China)(Army Unite 93861, Xi’an 710038, China)

As a batch processing method, the Hough transform hardly overcomes the accumulation phenomenon of single-scan data sets for it gets confused with the time sequence information of measurements. To solve this nonlinear problem, a track initiation method based on the parallel Hough transform that changes the processing structure of the Hough transform and the accumulating manner of the counter is proposed. After mapping sets of different time measurements to the parameter space separately, the accumulated result of the measurement sets with the same index constitute an accumulated vector. According to the rules, the value of the accumulator can be obtained using the sliding window method. Finally, we make a decision on whether to initiate a track or not through threshold detection. Simulation experiment results of track initiation problems with different scan times under heavy clutters show the efficiency of the parallel Hough transform.

Track initiation; Hough transform; Parallel

TN953

A

2095-283X(2013)03-0292-08

10.3724/SP.J.1300.2013.13036

2013-04-01收到，2013-07-11改回；2013-09-03網絡優先出版

陜西省自然科學基金(2011JM8023)資助課題

鹿傳國 luyujie22@126.com

鹿傳國(1986-)，男，空軍工程大學信息與導航學院博士研究生。主要研究方向為多傳感器信息融合、數據關聯。

馮新喜(1962-)，男，空軍工程大學信息與導航學院教授。主要研究方向為多元信息融合、指揮自動化信息處理。

孔云波(1987-)，男，空軍工程大學信息與導航學院博士研究生。主要研究方向為異質傳感器信息融合。

E-mail: kongyunbo123@163.com

曾 蓉(1963-)，女，94936部隊高級工程師。主要研究方向為通信與航空管制。

李紅英(1976-)，女，空軍工程大學信息與導航學院博士研究生，93861部隊工程師，主要研究方向為信息融合。