并行Hough变换航迹起始

2013-07-25鹿传国冯新喜孔云波李红英

雷达学报 2013年3期

鹿传国*① 冯新喜① 孔云波① 曾蓉② 李红英①③

并行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 ()

起始算法试验结果 4次扫描6次扫描 Hough0.97200.18810.99730.0702 文献[17]1.00000.21290.93130.3547 本文算法0.96800.21720.96070.3572

表2 预处理能力对比()

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 ()

起始算法试验结果 4次扫描6次扫描 Hough0.98600.06701.00000.0111 文献[17]0.98900.06890.99670.0686 本文算法0.98600.07020.99730.0710

表4 预处理能力对比()

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

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部队高级工程师。主要研究方向为通信与航空管制。