ABSTRACT

The background of the rocket launch is very complex, and a lot of smoke will affect the tracking results, so this paper proposes a tracking algorithm based on edge feature and improves Hausdorff distance. Firstly, we separate the edge feature of the rocket from the mountain background, and then use the improved Hausdorff distance to carry out template matching. In the target tracking process, in order to speed up the template matching speed, the 3-step search method is applied. Experimental results show that this algorithm has good tracking performance and fast com- putation speed.

Keywords:Edge Feature, Hausdorff Distance, Target Tracking, Image Matching

一种基于边缘特征和改进Hausdorff距离的 火箭目标跟踪算法

阳小燕，李琳琳

成都理工大学核技术与自动化学院，四川 成都

收稿日期：2016年6月9日；录用日期：2016年6月27日；发布日期：2016年6月30日

摘 要

火箭发射时背景十分复杂，产生的大量烟雾也会影响跟踪效果，本文针对这一问题提出了一种基于边缘特征和改进Hausdorff距离的跟踪算法。首先将火箭的边缘特征与山体背景分离出来，再用改进的Hausdorff距离进行模板匹配。在目标跟踪过程当中，为了加快模板匹配速度，使用了3步搜索法。实验结果证明，该算法适时跟踪效果好，运算速度快。

关键词 :边缘特征，Hausdorff距离，目标跟踪，图像匹配

1. 引言

作为衡量一个国家科技、国防综合实力的重要标志，航天技术已成为当今世界最具代表性的高科技技术。我国一直以来十分重视研发各类应用卫星以及卫星发射技术，在卫星通信、遥感、导航定位等方面取得了巨大发展，火箭安全发射对航天事业的快速发展超着致关重要的作用。对火箭飞行的轨迹数据的鉴定和分析有利于对运载火箭的制导系统、动力系统以及其他分系统进行安全评估。因此，航天发射的十分重要任务之一就是火箭飞行的轨迹跟踪与记录。

目前对火箭的跟踪，多采用高速摄像机通过视频图像的方式进行跟踪，但这种方式仍是操作人员手动控制摄像机进行跟踪，安全性和可靠性不能保证，并且也无法实现多台摄像机在多个角度多个方位进行实时跟踪。因此，基于计算机视觉的火箭目标跟踪成为当今航天领域研究的热门技术 [1] [2] 。

近年来，国内外许多学者在基于计算机视觉的目标跟踪方面做了大量的研究，图像匹配是目标跟踪中的核心问题，图像匹配是指将模板图像与待匹配图像进行配准，来确定二者之间相对位置的过程。传统的匹配方法，在遇到物体遮挡、光照变化以及噪声影响时，无法实现对快速目标的跟踪。因此，在大多数跟踪场景中，如何选择尺度不变的关键点又是一个新的问题。目前针对传统匹配存在的缺点，许多学者提出了不同的解决方案，如基于光流法的快速目标跟踪、基于多特征融合的目标跟踪等，这些算法在一定程度上提高了跟踪的准确度，但是这些方法首先要建立模板与图像间的对应关系，计算量大，不能满足实时性要求 [3] - [12] 。

本文针对火箭发射时特有的复杂环境，提出了将边缘特征提取与Hausdorff距离匹配相结合的改进算法，该算法不需要计算光流特征值，也不需要对待匹配图像进行分割。实验证明，改进的Hausdorff距离的跟踪方法明显提高了目标匹配准确性，三步搜索法大大加快了匹配过程，具有较强的稳定性。

2. 基于Hausdorff距离的目标跟踪

本模板Hausdorff (简写成HD)距离是通过比较点集合的最大最小距离，计算模板图像与待匹配图像边缘点的Hausdorff距离来进行模板匹配，实现跟踪目标的目的。

Hausdorff距离描述两组点集合之间相似度的一种量度，一般定义两组点集：假设有两组集合，则这两个点集合的Hausdorff距离可用下式定义：

(1)

(2)

(3)

这里，是点集到的有向Hausdorff距离，是点集到的有向Hausdorff距离；Hausdorff距离取和中较大的那一个；是欧氏距离。

令集合中的一个点到集合的距离为，取点为到集合中的每一点距离的最小值：

(4)

此时表示集合中所有点到集合的距离的最大值。

Hausdorff距离取和中的最大值，由此可获得两个点集A和点集B之间的匹配程度。函数对于两个点数分别为p和q的点集，其计算复杂度为，可以改进到。

设定B为模板，A为图像，可以用来度量B和A的匹配程度。当模板只需匹配图像的某个部分时，也可以推广到部分Hausdorff距离，满足匹配需要。其定义为

，其中

的值可以这样求取：计算出点集B中所有的点到点集A的距离，并将计算所得到的所有距离由小到大排序，序号为的距离即为。

对于两个有限集A和B，还可以定义双向Hausdorff距离

,

式中与的定义类似，其中。也可以作为模板与图像匹配的度量。

在匹配过程中遇到突发噪声时，Hausdorff距离计算值将会产生较大的误差，影响匹配结果。针对这一问题，许多学者提出了改进的HD计算公式，如PHD、MHD、RHD等。参照RHD方法，并对其进行了改进，定义Hausdorff距离如下：

其中，

是值很大的常数，，是常数。，值选择合适可消除出格点，值则可有效解决遮挡问题。

3. 基于边缘特征和改进Hausdorff的火箭目标跟踪算法

3.1. 算法流程

Hausdorff距离在二值图像模板匹配中效果较好，因此常将图像的边缘特征作为匹配的依据。分别提取待匹配图像和模板边缘值，用Hausdorff距离在这两个二值图像之间确定匹配位置，设定待匹配边缘图像的像素点集合为A，模板边缘图像的像素点集合为B，可得到图像与模板之间的双向距离，其中，前向Hausdorff距离为，即图像到模板的距离；后向Hausdorff距离为，即模板到图像的距离。通常所说的匹配，就是指：通过一定的变换空间，将模板按一定规则变换搜寻得到其在图像上的匹配位置。

基于Hausdorff距离的目标跟踪算法通常包含3部分内容：首先将图像进行预处理，然后将模板与待匹配图像进行匹配，最后将模板更新代替原有模板。确定初始模板后，在第一帧图像中按设定规则搜寻到最佳匹配位置，将已获取的图像目标信息作为新匹配的模板进行下一帧的匹配。模板匹配和模板更新交替循环进行，直到整个图像序列目标跟踪工作的完成。

传统的Hausdorff距离在一般情况下能较好的完成目标的跟踪，但是当图像间亮度变化较大，或者遇到突发噪声时，跟踪效果不佳，并且在模板匹配的过程当中，需要将待匹配图像的所有区域进行依次匹配，计算量大，十分耗时，不能很好的运用到实时跟踪。火箭发射时的有自身的一些特点，比如发射场背景复杂，火箭升空时会产生大量白烟，使前后帧光照变化很大，发射背景变化快，包括山体背景、天空背景，这些自身的特点都导致传统的Hausdorff距离不能很好的跟踪火箭目标。针对这些问题，本文提出了将边缘特征与改进Hausdorff距离相结合的火箭目标跟踪算法。具体的基跟踪算法如下图1所示。

首先将火箭的边缘特征与山体背景分离出来，再用改进的Hausdorff距离进行模板匹配。从上述跟踪算法可知，要实现对火箭目标的跟踪，首先要对图像进行边缘提取，图像边缘包含着重要的特征，对目标跟踪的效果起着关键作用。

3.2. 边缘特征提取

在图像处理和计算机视觉中，特别是在特征提取中，边缘检测是一个重要的研究领域。边缘检测是将边缘精确定位并且同时对噪声进行抑制。边缘点一般认为是极值点或灰度发生急剧变化的点，当灰度不连续性变化时即为物体的边缘，其特性是垂直于边缘方向的像素剧烈变化，而沿边缘走向的像素变化平缓 [13] - [16] 。

图像函数f(x, y)在点(x, y)的梯度是一个矢量，具有方向和大小，即

(5)

在方向的变化率可由下式给出

(6)

图1. 基于Hausdorff距离的火箭目标跟踪算法

变化率最大方向为

(7)

梯度值的大小为

(8)

算子应用的方向，以及在这些方向上形成图像一维导数的方式和把获得的这些近似值合成为梯度幅度的方式是所有基于梯度的边缘检测器之间的根本区别。在数字图像中，图像函数的偏导数可用图像的一阶差分替代。近年来许多学者对边缘检测提出了不同的模板算子及其相应的算法。一般常用的边缘检测算子包括Sobel算子、Roberts交叉算子、Prewitt算子等等。其检测的效果如下图2、图3。

从以上边缘检测效果可以看出，Roberts边缘检测算子对于火箭目标的各种背景都有很好的边缘提取效果。因此在火箭目标跟踪过程中，用Roberts边缘检测算子提取火箭图像序列的边缘特征。

3.3. 火箭目标跟踪算法

在传统的模板匹配过程中，需要将模板在待匹配图像上由左至右、由上向下顺序滑动来获取最佳匹配位置，它的匹配精度高，但运算过程复杂，计算量很大，实时目标跟踪中效果欠佳。

火箭在发射过程中，背景和火箭目标在两个相邻帧之间变化较小。因此，为加快匹配过程，缩短匹配时间，在跟踪过程中加入了一种快速的搜索算法——3步搜索法(Three Step Search, TSS) (图4所示)。3步搜索法搜索过程如图4中所示，具体描述如下：首先在中心(0,0)周围，选取8个样本点并计算每点到中心点的距离，将第一次计算的这8个点标记为序列1；第二步，在计算的8个距离中选取数值最小的点，并将搜索距离缩短一半，以该点为原心，继续选取周围8个样本点(记为序列2)，计算样本点到原心的距离；第三步，重复前两步搜索过程，直到步长小于或等于1个像索。

图2. 天空背景下边缘检测效果

图3. 出山时边缘检测效果

在使用三步搜索法搜索最佳匹配位置的过程中，采用的Hausdorff距离计算方法就是本文所提出的改进方法，提高了模板匹配的精度。

4. 仿真结果及分析

为了验证算法的可行性和有效性，本文选取某基地提供的公开火箭发射录像为实例,该段录像长300帧。使用matlab7.0为仿真工具，在Semprorr-1.81 MGHZ，512内存的PC平台上进行了仿真实验。采用基于边缘检测和改进Hausdorff距离的目标跟踪算法。图5为采用传统Hausdorff距离匹配算法和本文跟踪算法分别在第50、100、150、200帧图像的匹配跟踪效果。从图5中可以看出，传统算法从第150帧的时候模板开始漂移，在第200帧开始已经完全丢失了跟踪目标。因此从图5的仿真图可以看出采用本文所提方法，在火箭目标运行的各个阶段都能有很好的跟踪效果。

图4. 三步搜索法示意图

图5. 传统Hausdorff距离匹配算法与本文跟踪算法结果比较

表1. 使用不同匹配策略的平均每帧时耗

通过对比实验，可以明显的看出本文所提的火箭目标跟踪算法，明显优于传统Hausdorff距离匹配法对火箭目标的跟踪。采用Robert边缘检测算子提取火箭边缘，Hausdorff距离法进行模板匹配，三步搜索法快速收搜下帧火箭位置，有效地消除了传统模板匹配存在的跟踪误差累积的问题。

为了有效的验证算法实时性，采用传统的算法和本文所提算法，对火箭发射序列图像中的230帧图像处理的平均每帧时耗进行比较，其结果如表1。其中模板初始大小为8 × 72个像素单位，待配图像大小为200 × 200个像素单位。具体对比如表1。

图像采集速度一般为每秒24帧至30帧，即每两帧间的时间间隔约为0.05秒至0.03秒。从表1中可以看到，本文所提的基于边缘特征与改进Hausdorff距离的跟踪算法耗时大幅下降。

5. 结束语

传统的Hausdorff距离匹配算法存在运算量大，目标匹配精度低，不能很好的满足实时跟踪要求等缺点，针对这些缺点，本文提出一种改进算法。该算法将边缘特征提取与Hausdorff距离匹配相结合，首先利用Roberts算子进行图像预处理，提取火箭在各种背景下的边缘特征；然后对Hausdorff距离的形式进行了改进，增强了抗噪性能；在搜索过程中，为加快匹配搜索速度，使用了3步搜索法。为验证算法的有效性，对火箭在不同背景运行进行了实时跟踪，实验结果表明该算法在具有较好的跟踪效果，可以实现实时跟踪，并具有较强的稳健性。

文章引用

阳小燕,李琳琳. 一种基于边缘特征和改进Hausdorff距离的火箭目标跟踪算法
A Rocket Object Tracking Algorithm Based on Edge Features and Improved Hausdorff Distance[J]. 国际航空航天科学, 2016, 04(02): 34-40. http://dx.doi.org/10.12677/JAST.2016.42005

参考文献 (References)