基于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