基于边缘梯度特征的目标定位算法

南京邮电大学电子与光学工程学院 陈志彭

1 引言

目标定位广泛应用于计算机视觉和图像处理的相关领域，例如目标跟踪、目标检测等。针对目标识别和定位这一问题，已经形成了一系列的相关理论和技术，现在流行的目标定位的方法主要有两种，一种是基于区域的目标匹配，另一种时基于局部几何特征的目标匹配[1]。

典型的模板匹配就是计算模板和搜索图像滑动窗口内的子图像在每一个像素点上的像素值相似度，并将相似度高于阈值的区域作为目标在图像上的位置，这种方法对于模板或被搜索图像的尺度变化以及图像旋转等问题的适用性不够好。

针对传统上基于灰度相似性度量的模板匹配算法在图像旋转情况下适用性不高以及容易受到环境光照影响的局限性，本文采用一种基于边界梯度特征的目标定位方法。该算法主要思想是在图像金字塔逐步求精的基础上采用边界梯度而非像素点处的像素值进行相似性度量，使得算法能够针对图像旋转情况具有其匹配准确性和适用性。另外，针对目标定位的多目标问题，本文算法在遍历整个搜索图像的同时，将所有高于设定阈值的匹配得分以及对应的坐标和旋转角都保存在一个链表里，在遍历结束之后根据匹配得分对整个链表进行排序，得到所要确定的多个目标位置以及相对旋转角。

2 基于边界梯度特征的匹配方法

2.1 基于构建图像金字塔的匹配方法

传统的模板匹配是计算搜索图像每幅子图像在各种旋转角度下的灰度值相似度量值，这是一个十分耗时的过程，虽然通过使用终止条件可以加快算法处理的速度，但是并不能降低算法的复杂度[5]。

为了能够更加满足实时性的要求，就要采用更加快速有效的搜索策略。考虑到计算灰度相似度量的运行时间取决于搜索图像的大小、模板像素点个数以及模板旋转的次数，那么由粗到精的搜索策略就可以有效的降低算法的复杂度[2]。

实现这一过程的比较有效的办法是构建图像金字塔，构建图像金字塔时，对图像隔i行i列进行重采样。对搜索图像和模板进行降采样操作，得到低分辨率的图像后，通过计算模板和搜索图像子图像的相似度量值来获取与模板相似图像的大概位置。接着，使用间隔小一点，如i/2的重采样图像，在上一分辨率得到的大致位置的领域内进行相似度量计算并判断，获得精确一点的匹配位置。以此类推，逐步求精，直到得到原分辨率下精确的匹配位置[3]。

2.2 基于梯度信息的相似性度量函数

上一节介绍图像金字塔逐步求精的过程中，通过降采样的方式分别在不同的金字塔层级计算模板图像与搜索图像子图的灰度值相似性度量值，从而逐步确定目标图像在搜索图像中的目标位置。但是通过计算灰度值的相似性度量值对环境变化、图像旋转等情况鲁棒性不高，所以本文采用用图像边界特征的梯度信息作为相似性度量因素，在图像金字塔分层搜索过程中计算模板图像与搜索图像在边界特征点处的梯度信息相似性来确定是否为目标位置。

针对图像会发生的旋转情况，同样可以采用图像金字塔的思想：首先，通过使模板以一定角度步长旋转遍历一次金字塔最顶层的图像。在计算相似度量值的时候，可以适当加入合理的停止标准，加快判断效率。然后，将在最顶层找到的大致位置映射到下一层，在该位置的一定领域内进行更加角度步长更精细的匹配，依次直到图像金字塔的最底层，这样就能得到图像旋转时最高分辨率匹配精度[4]。

采用基于边界特征点的匹配算法，需要对模板图像边界特征点进行筛选提取得到边界特征点坐标及其对应的梯度向量，i=1，2……,n（n表示特征点个数）。还有搜索图像的边缘特征点坐标以及每个子图像中的梯度向量，这里的分别是特征点（a,b）处的横向梯度方向分量和纵向梯度方向分量。在得到边界特征点坐标以及特征点处的梯度向量信息之后，通过计算模板图像中所有特征点与搜索图像的所有特征点的梯度相关性的总和作为相似度，表示梯度相关性的相似度量函数为：

这里的搜索图中与模板特征点梯度相对应的梯度向量。公式(1)[2]容易受到非线性噪声的影响，因此对其进行归一化处理：

归一化后的梯度相似性度量表示的是归一化后模板与搜索图像的所有特征点处梯度信息相似性度量均值，通过该公式计算相似性可以得到一个小于等于1的匹配得分。当该匹配得分越高，表示搜索图像该子图区域与模板图像越匹配。当该式等于1时，为该子图区域与模板图像完全匹配。

根据上述关于边界特征点的梯度相似性度量函数的介绍，接着详细介绍算法设计实现的过程，包括模板和搜索图像特征点提取及筛选、金字塔模型创建、匹配过程的梯度信息相似性度量计算和多目标定位等。

2.3 算法设计与实现

2.3.1 特征点提取及筛选

首先，需要通过边缘检测提取模板图像特征点x方向和y方向的梯度信息和，并通过公式(3)和公式(4)计算得到梯度幅值和梯度方向：

为了减少边缘特征点提取到的伪特征点对梯度信息相似性度量的影响，减少伪特征点处不必要的计算量。在进行伪特征点剔除之前，为了方便非最大值抑制过程的实现，需要将梯度方向修正到0度、45度、90度、135度方向。通过非最大值抑制以及双阈值筛选剔除伪特征点，将低于低阈值的特征点以及介于低阈值和高阈值之间但与高于高阈值的特征点不连通的特征点确定为伪特征点，给与剔除，不参与匹配过程中的相似性度量计算。

2.3.2 构建模板图像和搜索图像金字塔模型

在搜索图像上直接进行匹配运算是一个十分耗时的过程，本文通过构建图像金字塔的方式以实现逐步求精的匹配过程，可以适当提高算法的速度。首先根据设定的金字塔层数，本文设置为3层，对模板进行降采样构建金字塔。在构建好图像金字塔之后，需要按照3.2.1小节的方法在每一层提取模板梯度信息，并保存模板在同一角度下不同金字塔层级的梯度信息，方便匹配过程中的相似性计算。针对搜索图像可能出现的旋转情况，按照ΔƟ的步长旋转模板图像，该步长也要依据图像金字塔逐步求精的思想，设置为依据金字塔层数的递进逐步细分，并采用与上述相同的过程保存不同角度下的模板梯度信息。

为了给图像匹配过程做好准备，对搜索图像也要采用与模板图像相同的处理方法，构建与模板图像金字塔相同层数的搜索图像金字塔。不同地方在于，已经对模板图像进行旋转处理得到不同角度下的模板梯度信息，就不需要去搜索图像再做重复处理。

2.3.3 匹配过程的实现

构建好搜索图像金字塔之后，就是匹配过程的实现。从图像金字塔顶层开始，在图像金字塔每一层都对模板和搜索图像子图像中所有特征点进行梯度信息相似性计算并归一化得到的就是每个子图像与模板图像的匹配得分。当梯度信息相似度量值高于设置阈值时就认为是目标位置，随即也就可以确定出最佳匹配位置坐标和相对旋转角。

在程序设计时，在金字塔每一层中，从图像金字塔顶层开始计算公式(2)的梯度信息相似度量值，该公式得到的计算结果就是每个搜索图像的每个子图与模板图像的匹配得分。得到匹配得分之后，将该得分与事先设置的阈值做比较，若该得分高于阈值，将目前的得分作为搜索图像下一个子图像与模板图像匹配的阈值，并保存其坐标以及旋转角。若低于阈值则认为该子图像不匹配并舍弃。以此类推，当整个搜索图像金字塔模型被遍历完成之后，保存下来的阈值就是当前搜索图像的子图像（匹配得到的目标位置）与模板图像的匹配得分打分，而该匹配得分对应的信息就是匹配的目标位置和相对旋转角。

2.3.4 多目标匹配的实现

采用计算梯度信息相似度的全局最大值只能实现单目标匹配，而通常在进行目标定位时，搜索图像中可能存在多个与模板相匹配的目标位置，这个时候通过查找全局最大值来确定目标位置就不适用了。这时可以在遍历整个搜索图像的同时，将所有高于设定阈值的匹配得分以及对应的坐标和旋转角信息都保存在一个链表里，这里保存的信息也包含了最佳匹配位置附近的匹配得分。在遍历结束之后，依据匹配得分对整个链表进行排序，再根据设定的目标个数就可以确定相应的排序在前的那几个得分就是目标点匹配得分，从而就可以确定多个匹配位置的坐标和旋转角度。

3 算法实验设计与结果分析

3.1 实验设计

康耐视的PatMax目标定位算法是机器视觉领域中成熟稳定的算法，并且有相应的InSight图片处理软件。为了验证本文目标定位算法针对图像旋转情况是否能够正确进行目标定位，在PC端进行软件算法设计，工具是Visual Studio 2013，编程实现本文采用的基于边界特征梯度相似性度量的目标定位算法，并将两者的匹配结果与康耐视InSight处理软件上的匹配结果做比较。如图1(a)、(b)分别是本文验证算法采用的搜索图像和模板图像：

图1 实验采用的搜索图像和模板图像

3.2 实验结果及分析

通过上面的实验设计，并在PC端进行编程实现的结果记录如图2和表1所示：

图2 本文算法的匹配结果图

表1 两种算法的匹配输出坐标对比表

根据图2(a)，我们可以看出，即使在图像发生旋转的情况下，本文算法也能正确定位到目标图像。从图2(b)可以看出，在角度搜索范围内，本文的算法都能正确进行目标定位，并且能够给出搜索图像中的目标区域与模板图像的匹配得分以及相对应的目标位置坐标。另外，本算法还给出搜索图像中目标相对于模板的旋转角度，分别为-69°、-26°和13°（规定顺时针旋转角度为正角度，逆时针旋转为负角度），即代表其能够在误差接受范围内确定出搜索图像相对于模板图像的旋转角度。最后，搜索图像中存在三个目标位置，采用本文的目标定位算法能够定位处多个目标位置，从而也验证了针对多目标场景的可行性。

通过表1可以看出，采用本文算法进行PC端进行代码实现得到的匹配结果与康耐视相机处理结果相当，说明本文算法进行目标定位具有其准确性。针对不同旋转角度下的多个目标位置，本文算法也能够给出目标位置，说明该算法在图像旋转情况下具有其实用性，并且能够实现多目标定位。

4 结束语

本文在金字塔逐步求精的基础上，用边界特征点处的梯度信息代替传统上以像素点的灰度值来计算相似性度量。另外，考虑到搜索图像中可能存在的多目标位置的情况，采用针对匹配得分为标准进行排序筛选从而能够实现多目标定位。经过理论的分析以及实验结果的验证，可以本文基于边界特征点梯度信息的目标定位算法能够在图像旋转情况下具有其适用性和准确性，并且能够在多目标的场景下也是可行的。