基于投票分布积累的Hough变换航迹起始法*

陈　伟,赵毅寰,孙洪忠

(1.中国空空导弹研究院,河南洛阳　471000；

2.航空制导武器航空科技重点实验室,河南洛阳　471000)



基于投票分布积累的Hough变换航迹起始法*

陈伟1,2,赵毅寰1,2,孙洪忠1,2

(1.中国空空导弹研究院,河南洛阳471000；

2.航空制导武器航空科技重点实验室,河南洛阳471000)

摘要:针对密集杂波下匀加速运动的低可观测目标的航迹起始问题,提出了一种基于投票分布积累的Hough变换航迹起始法。该方法利用单元投票数以及该单元附近投票数的密集程度定义了投票密度和投票均值,构造了两级门限来滤除部分杂波,快速给出目标航迹参数在参数空间的大概位置,最后由直观法给出起始航迹的数目以及参数。仿真结果表明,该方法不仅能提高正确航迹起始概率、降低错误起始概率，而且所用时间短,尤其适用于复杂环境中的目标检测。

关键词:Hough变换;航迹起始;积累方式;低可观测目标

修回日期： 2015-11-19

赵毅寰(1982-),博士,高级工程师。

孙洪忠(1968-)，男，研究员。

自从Smith和Winter[1]将Hough变换作为一种有效的航迹起始方法提出以来,很多学者将Hough变换及其改进的方法应用到航迹起始中[2-3]。与传统的航迹起始算法相比,Hough变换解决了复杂环境下航迹起始研究的瓶颈问题,大大推动了航迹起始研究的发展。

目前Hough变换的积累矩阵的积累方式主要有:1)像素梯度幅值积累方法[4-6];2)概率积累方式[7-8];3)影响函数积累方法[9];4)二值积累方法[10];5)加权积累方法[11-12]。方法1)和2)需要利用特征点的梯度信息,对梯度信息比较敏感,因而对梯度信息的准确度要求很高,从而使其适用范围比较有限,方法3)和4)适用于任何各类图像,但是方法3)需要计算每个特征点对所有积累单元的贡献值,计算量庞大。方法4)的应用最为普遍,但由于参数空间划分无法保证理论特征参数对应的积累单元与其相邻的积累单元相比在票数上具有明显的优势,导致积累矩阵存在严重的局部积累峰值单元与其附近单元积累值不易区分的峰值簇拥现象,因此不利于峰值的提取。方法5)是方法4)的进一步发展,但是该方法在航迹起始方面,需要较长的扫描时间才能获得较低的虚假航迹起始概率,这也限制了该方法的适用范围。

二值积累方法以及相应的改进的积累方法都是利用投票分布特征作为判断标准的基本方法,但是这些方法只用到了投票分布特征中的少量信息,如单元投票数、投票取值。实际上,投票分布特征还有很多可以利用的信息,如投票密度、投票均值、投票数的中位数等。本文分析了在不同情况下积累矩阵的积累值的分布情况,引入了一些更能反映投票分布特征的信息-投票密度和投票均值。基本思想为利用单元投票数以及该单元附近投票数的密集程度定义了投票密度和投票均值,并根据这两个定义构造两级门限来判断该积累单元对应的参数是否为待测曲线特征参数。对投票数大,投票取值密集的单元作为候选目标航迹参数单元进行保留,对投票数小,投票取值稀疏的单元作为虚假目标航迹的单元进行删除,从而提出了一种基于投票分布积累的Hough变换航迹起始法。

1基于投票分布积累的Hough变换法

Hough变换的本质是从图像空间到参数空间的映射[11-12],其基本思想是把解析曲线从图像空间映射到以参数为坐标的参数空间中,根据参数空间的一些标识反过来确定曲线的参数值,进而得出图像空间中各种边界的确定性描述。其不仅可以用来检测直线,还可用来检测圆、抛物线、椭圆等任意形状的曲线。在直线检测中,应用最广泛是标准Hough变换,其原理图如图1,其变换函数为:

ρ=x·cosθ+y·sinθ

(1)

图1　Hough变换原理图

ρ为从图像空间的原点到直线的距离,0≤θ≤π为由原点向直线所引的垂线与x轴的夹角。首先以合适的间隔对参数空间进行等间隔划分,建立与之相应的积累矩阵,对积累矩阵内的每个小方格进行初始化;其次,对每一个边缘点根据式(1)使其对所有可能通过该点的曲线参数所属的区域进行二值积累;最后,根据给定的阈值,选出大于阈值的积累单元,这些单元对应的参数即为真实目标对应的参数值。

就一条直线而言,无论是在不考虑各种干扰[13],还是在考虑各种干扰的情况下,只要图像空间的数据点隐含直线关系,那么对应参数空间中的变换曲线就在某一区域内较为集中,而这个集中区域又恰恰是直线参数所在的区域。如图2-图7所示,图中给出了总扫描次数为60的情况下,曲线交点对应的参数值附近的积累图。从下图中可以明显看出,在目标参数对应的积累峰值附近的小区域内的投票值都比较大(特别是以峰值为中心,长5个单元格、宽3个单元格的小区域内,投票值一般都大于峰值的三分之一)。这说明了积累单元投票取值的密集程度也是衡量该积累单元对应参数是否为待测曲线特征参数的一个重要指标。

图2　不加量测噪声和杂波时的参数空间映射图

图3　不加量测噪声和杂波时的积累矩阵局部积累图

图4　加量测噪声不加杂波时的参数空间映射图

图5　加量测噪声不加杂波时的积累矩阵局部积累图

图6　加量测噪声和加杂波时的参数空间映射图

图7　加量测噪声和加杂波时的积累矩阵局部积累图

针对这一现象,本文根据单元投票数以及该单元附近投票数的密集程度定义了投票密度和投票均值,并根据这两个定义给出了两个门限来判断该积累单元对应参数是否为待测曲线特征参数。

利用初选阈值T1对经过二值积累的积累矩阵进行筛选,将大于T1的积累值保持原值,小于T1的积累值置0,获得新的积累值C。

定义一:投票密度φ是指C中的某一积累值为中心,划分出一个小矩形区域,并在该矩形区域内非零积累值的个数。

第一级门限为

(2)

其中，α为折扣因子,多次仿真实验表明,其取值范围为(1/6,1/3),并且α随杂波的增多而变大;N为该矩形区域内单元格总数。

定义二:投票均值:

(3)

其定义为目标矩形区域内非零积累值的平均值,即以C中的某一积累值为中心的目标矩形区域内的非零积累值相加,然后除以非零积累值的个数。其中(i,j)代表该目标矩形区域的中心值的行和列值;n为该小矩形区域非零积累值的个数。

第二级门限为

T2=κ·T1

(4)

其中，T1=β·Ts·total·Pd(0.3≤β≤3),β的值随杂波增多选取得越大(具体选取标准见文献[14])。Ts为扫描间隔,total为总的扫描次数。κ为折扣因子,经多次试验,κ取值范围一般为(1,1.4),在杂波比较多时,κ取较大的值,在杂波比较少时,κ取较小的值。

本文提出的基于投票分布积累的Hough变换法的基本步骤如下:

步骤1:在合适的范围内将参数空间分割为众多大小相等的小区域(积累单元),并建立相应的积累矩阵H,其每个元素都与一个相应的积累单元Ψ对应,置每个元素值为零;

步骤2:对图像空间中的每个边缘点zi(k),根据式(1)使其对所有可能通过该点的曲线参数所属的区域进行投票,并对相应的投票标志位p赋值;

步骤3:根据初选阈值T1对各个积累单元进行筛选,将大于等于T1的积累值保留原值,同时将小于T1的值全部置0,获得新的积累矩阵C。同时得到第一批临时航迹s1,s2,…sm;

本文应用基于投票分布积累的Hough变换方法有效地去除杂波,获得目标航迹参数在参数空间的大概位置;然后再用速度以及加速度限制对候选航迹进行进一步地筛选,快速获得目标航迹的数目以及参数。

假定强杂波下原图像是R1,基于投票分布积累的Hough变换法滤除大部分杂波后的图像是R2,基于投票分布积累Hough变换航迹起始算法的大概步骤及流程图(图8)如下:

步骤1:利用基于投票分布积累Hough变换法滤除杂波,得到候选航迹的数目以及参数。

利用基于投票分布积累的Hough变换法得到候选航迹l1,l2,…,lk(k是由基于投票分布积累的Hough变换初选出的临时航迹的数目)。在R2内的杂波点比在R1内的杂波点减少了很多,这样可以大大减少进入第二步筛选的点的个数,减轻运算负担。

步骤2:用直观法确定目标航迹的数目以及参数;

根据直观法[15]对步骤1筛选出的候选航迹li中的量测点进行进一步地确认,若候选航迹li中的量测点不满足速度、加速度限制,则删除该候选航迹。当循环完所有候选航迹l1,l2,…,lk时,就可以得到目标航迹的数目以及参数。

图8　算法流程图

2仿真分析

本文以多目标航迹起始为例,分别在1)只考虑量测噪声,2)给定检测概率和量测噪声而杂波密度不同的两种情况下,将采用本文提出的基于投票分布积累的Hough变换航迹起始法(简称为VA-HT)与文献[13]提出的方法(简称为WB-HT)进行了比较。

假设目标监视区域有三个目标作匀加速直线运动,其量测方程如下:

(5)

其中，W(k)代表零均值高斯白噪声,协方差R=[σ20;0σ2],σ=0.1km。

三个目标的初始运动状态定义如下:X(1,0)=[2km100m/s10m/s22km100m/s10m/s2];

X(2,0)=[20km-180m/s-10m/s296km100m/s10m/s2];X(3,0)=[106km-200m/s-10m/s26km200m/s10m/s2];在仿真中设起始窗长为20Ts,采样间隔为Ts=2s。Nθ=90,为使位于同一直线上的含噪边缘点以大概率共同对相应积累单元投票,仿真中取Δρ=6σ,(σ=max(σx,σy))。

场景1:为了检验基于投票分布积累的Hough变换方法对量测噪声的鲁棒性,该仿真中假定检测概率为(Pd=0.8)和杂波密度为λ=0.04个/km2时,分别在量测噪声σx=σy且取值分别为0.1km和0.2km的情况下,将基于VA-HT与基于WB-HT滤波结果进行了比较。仿真结果如图9-16所示。其中红色*号代表源于目标的真实量测,蓝色·号代表起始的航迹。

图9　σ=0.1时WB_HT的滤波

图10　σ=0.1时WB_HT航迹起始图

图11　σ=0.1时VA_HT的滤波

图12　σ=0.1时VA_HT航迹起始图

图13　σ=0.2时WB_HT的滤波

图14　σ=0.2时WB_HT航迹起始图

图15　σ=0.2时VA_HT的滤波

图16　σ=0.2时VA_HT航迹起始图

从上述仿真结果中可以看出,无论量测噪声是0.1km,还是0.2km,基于VA-HT的滤除杂波的效果明显优于基于WB-HT的滤波效果。从起始结果还可以看出,基于VA-HT的方法对量测噪声具有更好的鲁棒性。如当量测噪声为0.1km和0.2km时,基于VA-HT的虚假航迹数分别为35和29,而基于WB-HT的虚假航迹数分别为74和70。

场景2:为了检验基于投票分布积累的Hough变换方法的抗干扰能力,该仿真中给定检测概率Pd=0.8、量测噪声σx=σy=0.1km,分别比较了两种积累方法在杂波密度从1×10-2个/km2增加到5×10-2个/km2,每次增加1×10-2个/km2时的起始结果,如图17-21所示。其中,杂波在整个监视区域内服从均匀分布,杂波个数服从泊松分布。其中航迹起始概率用Pd表示,虚假航迹占有率用Pc表示,总的运行时间用Tall表示,积累时间用Tacc表示,起始航迹的条数用linenumber表示。

图17　不同杂波密度下的航迹起始概率图

图18　不同杂波密度下的虚假航迹占有率图

图19　不同杂波密度下的积累时间

图20　不同杂波密度下的总的运行时间

图21　不同杂波密度下的起始航迹的条数

从图17、18可以看出,基于VA-HT的航迹起始性能明显优于WB-HT航迹起始性能。虽然在杂波密度较小(λ<0.025个/km2)时,基于VA-HT的航迹起始性能与基于WB-HT的航迹起始性能相近,但基于VA-HT的方法明显具有更强的抗杂波干扰能力,随着杂波密度的增大(λ>=0.025个/km2),基于VA-HT的航迹起始概率明显高于基于WB-HT的航迹起始概率。同时,由于基于VA-HT方法能大量滤除杂波,使得基于VA-HT的虚假航迹占有率明显低于基于WB-HT的虚假航迹占有率,如在λ=0.05个/km2时,基于VA-HT的虚假航迹占有率比基于WB-HT的虚假航迹占有率低了近二十个百分点。

从图19、20可以看出,由于基于投票分布积累Hough变换法能够快速有效地找到目标航迹参数的大概位置,并且能够滤除大部分杂波,减轻了运算负担,使得基于VA-HT的积累时间以及总的运行时间均小基于WB-HT的时间。由图19可以明显看出,基于VA-HT的积累时间是基于WB-HT的积累时间的三分之一,并且基于VA-HT的总的运行时间也近似是基于WB-HT的总运行时间的三分之一。

从图21可以看出,在不同的杂波密度下,基于VA-HT的起始航迹的条数均小于基于WB-HT起始航迹的条数,并且随着杂波密度的不断增加,两种算法起始航迹的条数的差距也是不断增加。在λ=0.03个/km2,基于WB-HT起始航迹的条数近似是基于VA-HT的起始航迹的条数的两倍,在λ=0.05个/km2,基于WB-HT起始航迹的条数近似是基于VA-HT的起始航迹条数的三倍。

3结束语

本文分析了在不同情况下积累矩阵的积累值的分布情况,引入了一些更能反映投票分布特征的信息-投票密度和投票均值,提出了一种基于投票分布积累的Hough变换航迹起始法。该方法利用单元投票数以及该单元附近投票数的密集程度定义了投票密度和投票均值,构造了两级门限来滤除部分杂波,快速给出目标航迹参数在参数空间的大概位置,最后由直观法给出起始的航迹数目以及参数。它明显地改善了二值积累方式下峰值簇拥现象;同时该方法具有更强的抗干扰能力,对复杂环境下的直线检测具有优越性。在低杂噪比环境下的多目标航迹起始和海面低可观运动目标检测中有广泛的应用前景。

参考文献:

[1]Smith M C,Winter E M.Feature Space Transform for Multi-target Detection[C].IEEE Conf on Decision and Contro1.Albuquerque, NM, l980: 835-836.

[2]YanHang Zhang, XiaoHong Su, PeiJun Ma, Multi-Hough Transform Track Initiation for Detecting Target with Constant Acceleration[C].International Symposium on Information Science and Engieering,2008,p581-584

[3]刘航,窦丽华,董领逊. 基于改进积累方式的Hough变换和最小方差航迹起始方法[J].火力与指挥控制,2009,34(02):114-116.

[4]Ballard D H. Generalizing the Hough transform to detect arbitraryshapes[J]. Pattern Recognition (S0031-3203), 1981, 13(2):111-122.

[5]Van Veen T M, Groen F C A. Discretization errors in Hough transform[J]. Pattern Recognition (S0031-3203), 1981, 14: 137-145.

[6]Ibrahim M K, Nqau E C L, Daemi M F. Weighted Hough Transform[C].SPIE Intelligent Robots and Compter Vision X:Algorithms and Techniques. 1992. 1607:237-241.

[7]Stephens R S. Probabilistic approach to the Hough transform[J]. Image & Vision Comput. (S0262-8856), 1991, 9(1): 66-71.

[8]Ji Q, Haralick R M. Error propagation for the Hough transforms[J]. Pattern Recognition Letters (S0167-8655), 2001, 22(6): 813-823.

[9]L. Fan, X. Zhang, and L. Wei. Tbd algorithm based on improved randomized hough transform for dim target detection,Progress In Electromagnetics Research C[J]. 2012,31: 271-285.

[10]Siyu Guo, Tony Pridmore, Yaguang Kong, Xufang Zhang, An improved Hough transform voting scheme utilizing surround suppression[J].Pattern Recognition Letters, 2009, 30(13):1241-1252.

[11]鹿传国,冯新喜,孔云波,等.基于形态学和Hough变换的航迹起始研究[J].兵工学报,2013,34(6):704-710.

[12]Pang Cun-suo, Hou Hui-ling, Han Yan, High-speed Weak Target Detection Based on Hough Transform[J]. Journal of Electronics & Information Technology, 2012,34(3): 754-757.

[13]金术玲,梁彦,潘泉,等.一种有效的Hough 变换航迹起始积累方法[J].系统仿真学报,2007，19(4):811-814.

[14]金术玲.弱小目标跟踪航迹起始与数据关联研究[D].博士论文,2007.

[15]何友,修建娟,张晶纬,等.雷达数据处理及应用[M].北京：电子工业出版社,2006.

Hough Transform Track Initiation Based on Vote Distribution Accumulation Method

CHEN Wei1,2, ZHAO Yi-huan1,2, SUN Hong-zhong1,2

(1.China Airborne Missile Academy, Luoyang 471000；

2.Aviation Key Laboratory of Science and Technology on Airborne Guided Weapons, Luoyang 471000， China)

Abstract:In order to solve the problem of the Track Initiation of dim target with constant acceleration under the condition of heavy clutter, a Hough Transform track initiation algorithm based on vote distribution accumulation method was proposed in this paper. In this algorithm, the vote density and the mean-vote are defined first using the vote number of the cell and the transformed values of the cell votes and its neighbor votes simultaneously; then two-hierarchical thresholds were constructed according to the two definitions which are used to filter clutter, and the probable locations of the true parameters in the parameter space were obtained. Finally, the track number and parameters were given by object method. Simulation results show that this algorithm can keep higher true track initiation probability but lower false track initiation probability, moreover, the time is shorter, especially in complex environment.

Key words:Hough Transform; track initiation; accumulation method; dim target

作者简介：陈伟(1984-),男,湖北英山人，博士,工程师,研究方向为目标检测与跟踪、雷达信号处理、模式识别。

*基金项目：航空科学基金重点项目(20130112002)

收稿日期：2015-10-18

中图分类号:TN953

文献标志码:A

DOI:10.3969/j.issn.1673-3819.2016.01.011

文章编号：1673-3819(2016)01-0046-07