基于分割模板加权Hausdorff 距离矩阵的特征匹配算法

徐一鸣，刘晓利，刘怡昕，3

(1.南京理工大学 瞬态物理国家重点实验室，江苏 南京210094;2.南通大学 电气工程学院，江苏 南通226000;3.南京炮兵学院，江苏 南京211132)

基于Hausdorff 距离(HD)的特征匹配算法因其较小的运算量以及对目标一定程度几何失真的适应性而得到了较为广泛的应用。然而由于HD 本身对于噪声和孤立点较为敏感，在实际运用时，常会因目标被遮挡或存在背景噪声，导致无法实现图像配准。针对这种情况，近年来已经提出了多种改进Hausdorff 算法，如部分HD(PHD)、平均HD(MHD)、去出格点HD(M-HD、LST-HD)等。上述算法可以克服一定程度多点、少点或出格点的影响，但在目标存在大比例遮挡或较严重非高斯噪声干扰下的效果仍然欠佳［1］，因此要在电视制导武器系统上应用基于HD 的特征匹配算法，势必需要对算法的抗干扰性能进行增强。

为了增强特征匹配算法的鲁棒性，本文通过构造合适的角点响应函数(CRF)对部分平均HD 进行加权修正;同时采用模板分割的方法，根据子模板信息量来评价其对全局匹配的贡献程度，构造加权修正的相似性度量矩阵。实验证明，通过对相似性度量与特征空间分别进行加权修正，可以有效抑制出格点的干扰，从而弱化局部区域错误特征对全局匹配产生的影响。

1 基于加权HD 的角点匹配

1.1 角点检测

角点作为图像兴趣点的一种特例，可以描述为图像上灰度变换剧烈且和周围的邻点有着显著差异的像素点，通常定义为一阶导数为局部最大时所对应的像素点。角点包含了图像至关重要的信息，且数量相对较少，比较适合用于实时匹配计算。

目前常用的角点检测算子有多种，如Movarac算子、Harris 算子、Förstner 算子、Plessey 算子、Susan算子等。本文采用了最小核相似区检测角点(SUSAN)算法，该算法由Smith 首先提出，通常采用一个包含37 个像元的近似圆形模板，并基于该模板领域的图像灰度计算角点响应函数的数值，如果大于某阈值且为局部极大值，则认为该点为角点。SUSAN 检测算法具有方法简单、特征定位比较准确、抗噪能力强等特点［2-3］。

1.2 HD 定义

给定2 个点集A={a1，a2，…，ap}和B={b1，b2，…，bq}，h(A，B)和h(B，A)称为集合A 与B 之间的有向距离，定义为:

则A 和B 之间的HD 定义为:

HD 表征了2 点集间的最不相似程度［4］，由于无须知道点与点之间的一一对应关系，可以容忍一定程度下点位置的不准确以及多点、少点的误差，因此非常适合应用于图像配准。

1.3 基于角点响应函数的加权HD

为增强算法的鲁棒性，结合部分平均HD 与CRF，提出了一种基于CRF 的加权部分平均HD.

首先去除零均值高斯噪声的影响，采用部分平均HD，如下式［5-9］:

式中:th 表示按由小到大的顺序排序，即把点集A中所有点到点集B 的距离按由小到大的顺序排序，再对1 到k 的k 个距离求均值。

进一步考虑因非零均值噪声和目标遮挡造成的影响。由此类干扰产生的角点，即使距离匹配中心的角点距离较近，但是通过构造合适的CRF，可以得到不同的CRF 数值。因此可以由二者CRF 的差值来构造加权函数，对部分平均HD 公式进行修正，从而抑制噪声或遮挡产生的影响。

定义

称为A 到B 的有向加权HD，Na为点集A 中选取的特征点的总数，d(a，B)为点集中特征点a 到点集B 的距离，w(a)为该距离上的权值。

模板图像与搜索图像的角点集分别定义为A{a［i］}，i∈［1，2，…，p］和B{b［j］}，j∈［1，2，…，q］，其中a［i］和b［j］包括了角点的位置以及该角点的CRF 值，定义为a［i］.POS，a［i］.CRF 以及b［j］.POS，b［j］.CRF.

角点检测算法中的CRF 通常采用可以反映角点突出性，即角点处各方向灰度差变化趋势的响应函数。而构造加权函数的目的为衡量该角点包含信息量的多少，通过估算该角点的不等“价值”来增强对于出格点的区分能力。由对特征点的分析可知，角点是在微小邻域中灰度急剧变化的点，即在该局部区域中含有较大的信息量，因此将CRF 定义为角点像元与平均信息量之差的平方和。根据SUSAN算法中的37 像元模板，可得如下公式:

对于模板角点集A 中任一点a［i］，计算d(a［i］.POS，B{b［j］.POS})，a［i］必然对应于a［i］.POS-b［j］.POS|的点集B 中的m 个点b［jm］(通常情况下m=1，只有个别情况下才会存在多个对应点)，有权重公式如下:

经过加权的模板图像到搜索图像的有向HD 公式如下:

式中:Na=f1p，f1∈(0，1).

同理可得搜索图像到模板图像的有向HD 公式

式中:Nb=f2q，f2∈(0，1).

2 基于加权HD 矩阵的图像匹配算法

2.1 分割模板图像HD 矩阵

基于局部熵差的图像匹配思想，可以将模板分割引入匹配过程，从而进一步抑制大比例目标遮挡或严重噪声的影响。

将模板图像分割成M ×N 个子模板，对各子模板与搜索图像进行HD 计算，得到一个M ×N 维的HD 矩阵:

这个距离矩阵中每个元素的数值即该子模板与对应区域的相似程度;距离矩阵的范数则反映了整个模板与对应区域的相似程度。利用这个特性，可以根据各子模板对于整个匹配过程贡献度的大小进行加权，从而较好地抑制受遮挡或噪声等不利因素影响严重的局部区域对全图像匹配造成的干扰。

2.2 HD 矩阵的加权修正

为了增加匹配的可靠性，对各子模板的重要性进行分析。由于角点在局部区域中含有较大的信息量，因此对于子模板来说，含有的角点越多，说明该子模板含有的信息量越大，对于图像匹配的重要性就越高;反之，则说明该子模板的重要性越低。

由此采用了信息融合的方法来增强算法的可靠性，引入了角点密度矩阵对HD 矩阵进行修正，将经过加权修正的HD 矩阵作为相似性度量。

定义Ci，j=1-pij/NT，pij表示第i 行第j 列的子模板含有的角点数目，NT表示整个模板含有的角点总数。有角点密度矩阵

经过修正的加权HD 矩阵为

(11)式的意义在于，在子模板角点密度很小的情况下，即使该子块与对应区域HD 很小，亦不足以说明两者相似性高的可信度高;反之，当子模板角点密度很高，如果该子块与对应区域的HD 很小，可以相信这二者相似性较高。

该加权HD 矩阵可以有效调整重要性不等的子模板对整体匹配产生的影响，从而将图像匹配最后转化为矩阵之间的比较。

2.3 HD 矩阵的比较

对于2 个含有大小各异元素的HD 矩阵，其大小的比较通常可以通过矩阵范数的计算来实现。

Frobenius 范数(F 范数)在工程上应用较为广泛，其计算公式为

对于所求得的HD 矩阵，分别求出其F 范数，其中最小的F 范数对应的矩阵测度即对应搜索图像上与模板图像整体相似度最高的区域。

2.4 算法具体实现步骤

1)采用SUSAN 算子分别提取模板图和搜索图的角点，得到子模板特征二值图Ti和搜索特征二值图S，i∈［1，N］.

2)根据(10)式求解子模板角点密度矩阵CHD.

3)根据(5)式计算子模板Ti与搜索图像S 各角点的CRF 值，得到T_CRFi［x，y］及S_CRF［x，y］.

4)采用3-4DT 算法在二维空间中对特征点集进行距离转换［10］，得到图像距离转换矩阵JTi和JS.

5)根据(7)式、(8)式，结合JTi、JS、T_CRFi［x，y］及S_CRF［x，y］来求取每个子模板与搜索图像之间的加权HD，得到距离矩阵JHD.

6)根据(11)式，结合CHD、JHD求取修正后的加权HD 矩阵JWHD.

7)根据(12)式，求取JWHD的Frobenius 范数D=‖JWHD‖F，以具有最小范数度量值的匹配点作为最终匹配点。

算法流程图如图1所示。

图1 算法流程图Fig.1 Algorithm flowchart

3 实验结果及分析

为证明本文算法的有效性，进行了大比例目标遮挡及斑点噪声干扰下的目标跟踪实验，测试匹配效果及实时性能。计算机配置为INTEL P-IV 1.8 G处理器，512 M DDR 内存。在进行图像匹配时，部分HD 中的参数f1，f2均设为0.8，模板图像大小为64×64，搜索图像大小为320 ×240.

图2为模板图像及其角点检测结果，模板被分割为4 ×4 共16 个子模板。图3为搜索图像角点检测结果。表1记录了实时跟踪图像序列中的一些中间状态帧。整个图像序列共125 帧图像，其中约90帧图像存在不同程度的目标遮挡。为了验证大比例遮挡情况下的匹配性能，未对模板进行更新。整个跟踪过程中，模板对应区域角点数量因遮挡导致的少点比率最高达到43.75%.将目标实时跟踪轨迹分解为x 轴方向与y 轴方向进行轨迹连续性分析，如图4所示。目标在第25 帧～115 帧之间处于不同程度的局部遮挡状态，轨迹分布连续而稳定，没有出现明显的误匹配点。

图2 模板图像及分割模板角点检测图像Fig.2 Template image and corners of template partition image

图3 搜索图像角点检测结果Fig.3 Searched corners in image

当改用部分平均Hausdorff 算法时，当目标进入遮挡区域，便无法进行正确的匹配。

为了验证算法在严重非高斯噪声干扰下的性能，对搜索图像加入了较严重的斑点噪声(n=10)，并进行匹配分析。图5、图6分别为加入噪声前后的角点检测结果，可见加入斑点噪声后，搜索图像中增加了大量因噪声引起的角点。图7为噪声干扰下的匹配结果示意图，图7(b)与图7(c)为搜索图像角点与模板匹配情况，可以看到存在一个错配点。图7(a)为匹配区域扣除正确匹配点外的出格点，共计12 个。对于仅有16 个角点的模板，出格点比例高达42.9%，错配率为3.57%.

图4 目标跟踪轨迹Fig.4 Tracking trajectory of target

当改用部分平均HD 算法时，无法实现正确匹配。

将基于分割模板加权HD 矩阵算法(TPWHDM)与部分平均HD 算法(PMHD)进行比较，测试最大、最小以及平均匹配时间(tmax，tmix，)和目标匹配效果，如表2所示。

表1 实时跟踪图像序列Tab.1 Real-time tracking image sequence

图5 加入斑点噪声前的角点检测图像Fig.5 Corner detection without noise

图6 加入斑点噪声后的角点检测图像Fig.6 Corner detection with noise

4 结论

由于HD 对出格点比较敏感，导致基于HD 的特征匹配算法较区域相关匹配算法更易受目标遮挡及噪声干扰的影响。本文利用特征点信息量的不等性，通过构造角点响应函数，提出了一种基于CRF的加权部分平均HD;同时通过模板分割后子模板对于全局匹配贡献度的不等性进行相似性度量矩阵加权修正，从而在相似性度量与特征空间上对因遮挡或噪声引起的局部错误特征进行了双重抑制。目标跟踪实验证明该算法具有较强的鲁棒性，对于可靠性要求较高的电视制导武器系统具有一定的可行性。

图7 加入严重噪声干扰后的匹配结果Fig.7 Tracking result with heavy spot noise

表2 2 种算法的性能比较Tab.2 Performance comparison of two algorithms

References)

［1］ 赵峰伟.景象匹配算法性能评估及其应用［D］.北京:国防科学技术大学，2002.ZHAO Feng-wei.Performance evaluation and application of image matching algorithms［D］.Beijing:National University of Defense Technology，2002.(in Chinese)

［2］ Smith S M，Brad Y M.SUSAN-a new approach to low level image processing［J］.International Journal of Computer Vision，1997，231，23(1):4578.

［3］ 刘博，仲思东.一种基于自适应阈值的SUSAN 角点提取方法［J］.红外技术，2006，28(6):331-333.LIU Bo，ZHONG Si-dong.A SUSAN corner detector based on adaptive threshold［J］.Infrared Technology，2006，28(6):331-333.(in Chinese)

［4］ Huttenlocher D P，Klanderman G A，Rucklidge W J.Comparing images using the Hausdorff distance［J］.IEEE Trans Pattern Analysis and Machine Intelligence，1993，15(10):850-863.

［5］ Dubuisson M P，Jain A K.A modified Hausdorff distance for object matching［C］∥Proceedings of 12th International Conference on Pattern Recognition.Jerusalem:IEEE Computer Society，1994:566-568.

［6］ William J，Rucklidge.Efficiently location objects using the Hausdorff distance［J］.International Journal of Computer Vision，1997，24(3):251-270.

［7］ Shen F，Wang H.Real time gray level corner detector［J］.Pattern Recognition Letters，2002，23(8):1-6.

［8］ Sim D G，Kwon O K，Park R H.Object matching algorithm using robust Hausdorff distance measures［J］.IEEE Trans Image Process，1999，8(2):425-429.

［9］ Arturo P，Victor A R，Raul Enrique S Y，et al.Monte Carlo evaluation of the Hausdorff distance for shape matching［J］.LNCS，2006，4225:686-695.

［10］ Borgrfore G.Distance transformations in digital images ［J］.Computer Vision Graphics and Image Processing，1986，34:344-371.