杨幸芳 黄玉美 韩旭炤 杨新刚

1.西安理工大学，西安，710048 2.西安工程大学，西安，710048

0 引言

尺 度 不 变 特 征 变 换 （scale invariant feature transform，SIFT）是 Lowe［1－2］于1999年提出，并于2004年完善总结的一种特征点检测与匹配算法，该算法提取的图像特征（SIFT特征）不但对图像的旋转、尺度缩放和亮度变化保持不变性，而且对视角变化、仿射变换以及噪声也能保持一定程度的稳定性，故SIFT算法可用于处理两幅图像之间发生平移、旋转、仿射变换、视角变换、光照变换等情况下的识别与匹配问题。基于SIFT特征的识别与匹配被用于很多领域，如目标识别［3－4］、图像拼接［5］、移动机器人定位及地图创建［6－7］等。

虽然SIFT算法被成功应用于许多领域，但由于SIFT特征点数量庞大，且SIFT特征描述符维数过高，这使得SIFT特征匹配计算量大、效率不高。针对这些问题，许多学者进行了研究［8－12］。文献［8］提出的PCA－SIFT通过采用主成分分析法降低特征描述符的维数，以此减小算法的计算量及降低算法的复杂度，但由于PCA要求样本数据呈椭圆分布，且建立的模型是线性的，所以对于非线性的高维数据，效果不好，准确性较SIFT差。文献［9］通过修改原SIFT算法的采样规则，同时针对简单和复杂两种环境下的图像采用不同的采样方式，减少了SIFT特征的数据量，使系统基本达到了实时的效果。但该算法在不同尺度间循环采样，还需要分不同情况设定采样数或待检测的特征点数目，使得算法复杂。文献［10－11］以基于圆形窗口的12维向量代替128维向量，该方法提高了算法的实时性，但同时削弱了原算法邻域方向性信息联合的思想，使得算法抗噪能力变弱。文献［12］以街区距离和棋盘距离的线性组合代替欧氏距离作为特征描述符之间的相似性度量，并根据部分特征的计算结果逐步减少参与计算的特征点数，从而降低算法时间复杂度。线性组合系数和特征权重的选取均依赖于大量的实验数据，且针对不同的图像系数其取值范围是变化的，因此，应用起来并不方便。本文以街区距离［13］代替欧氏距离作为特征描述符之间的相似性度量，提出了最近邻、次近邻假设算法，通过降低相似性度量公式的时间复杂度，以及减少相似性计算过程中特征点比较的次数来缩减算法的计算量。实验结果表明，新算法在保持原SIFT算法鲁棒性的同时，提高了算法的效率。

1 SIFT特征检测与匹配算法

SIFT特征检测与匹配算法主要包括以下步骤［1－2］：尺度空间极值检测、特征点位置的确定、特征点方向的分配、特征描述符的生成以及特征匹配。

1.1 尺度空间极值检测

尺度空间极值检测的目的是确定局部极值点的位置及其所在的尺度。文献［14］指出高斯卷积核是实现尺度变换的唯一线性核，于是一幅图像I（x，y）的尺度空间定义为

式中，G（x，y，σ）为尺度可变的高斯函数；σ为尺度空间因子，其大小决定着图像的平滑程度。σ越小表征图像被平滑的越少，相应的尺度也就越小，因此大尺度对应图像的概貌特征，小尺度对应图像的细节特征。为了有效地在尺度空间检测到稳定的特征点，提出了高斯差分尺度空间DOG（difference of Gaussian），它由2个相邻尺度空间函数之差计算得到，即

为了寻找某个尺度空间中的极值点，D OG尺度空间中间层（最底层和最顶层除外）的每个像素，除需要跟其同尺度的周围相邻的8个像素进行比较外，还需要跟其上下2个相邻尺度的18个相邻像素（上下两个相邻尺度各9个像素）进行比较，若该像素是该26个邻域像素中的极值点（最大值或最小值），则认为该点是图像在该尺度下的一个特征点，如图1所示。

图1 尺度空间极值检测

1.2 特征点位置的确定

对极值检测得到的所有候选特征点，还需要经过两步检验才能得到精确定位的特征点：一是利用尺度空间函数D（x，y，σ）的二阶Taylor展开式进行最小二乘拟合，通过计算拟合曲面的极值来精确定位特征点，同时通过设置阈值剔除对比度低的点；二是通过Hessian矩阵剔除不稳定的边缘响应点［2］。二阶Taylor展开式和Hessian矩阵的表达式分别为

1.3 特征点方向的分配

利用特征点邻域像素梯度方向的分布特性，为每个特征点指定主方向，即邻域内各点梯度方向的直方图中最大值所对应的方向。

点（x，y）处梯度的模以及方向的计算式为

1.4 特征描述符的生成

构造特征描述符时，首先将特征点周围局部区域相对于特征点主方向旋转θ°（调整至0°），以确保其旋转不变性；然后以特征点为中心，选取16×16大小的邻域（图2仅显示了8×8大小的邻域），将此邻域均匀地分成16个4×4的子区域，并在每个子区域计算8个方向（0°、45°、90°、135°、180°、225°、270°、315°、360°）的梯度累加值，绘制梯度方向直方图，这样16个子区域共生成16×8＝128个数据，1×128的向量被定义为一个特征点的描述符。

图2 特征描述符的生成

1.5 特征匹配

为了各种应用的目的，需要对当前图像和目标图像进行特征匹配。这就需要首先存储目标图像（待匹配图像）的SIFT特征点，然后从当前图像中查找与之匹配的关键点。具体用欧氏距离度量两幅图像特征点间的相似性，即在待匹配图像中找到与当前图像中某个特征点m1欧氏距离最近的特征点m2和次近的特征点m3，设dist（mi，mj）表示2个特征点mi和mj之间的距离，若距离之比dist（m1，m2）/dist（m1，m3）小于某个阈值T（称T为距离比阈值），则认为m1与m2相匹配，否则认为m1在待匹配图像中没有匹配点。

2 提高SIFT特征匹配效率的方法

SIFT特征具有良好的光照、旋转和尺度不变性，其在许多基于图像匹配的应用领域［15－16］获得了成功的应用。SIFT特征匹配是通过计算一幅图像中所有特征点与另外一幅图像中所有特征点之间的欧氏距离来实现。由于每幅图像的SIFT特征数目庞大，且每个SIFT特征是128维向量，故SIFT特征匹配的计算效率非常低。本文通过减小算法的计算量，从2个方面提高了SIFT特征匹配的效率：

（1）改造了特征描述符相似性度量的形式，用街区距离代替欧氏距离，降低了相似性度量公式的时间复杂度。

（2）提出了最近邻－次近邻假设算法，通过减少相似性计算过程中特征点比较的次数，缩减算法的计算量。

2.1 用街区距离代替欧氏距离

2个n维点x＝（x1，x2，…，xn）与y＝｛y1，y2，…，yn｝之间的欧氏距离定义为

这2个n维点之间的街区距离定义为

不难验证，DJ（x，y）≥DO（x，y），且由定义可知，DJ（x，y）的计算比DO（x，y）的计算简单。对每个SIFT特征点，计算欧氏距离需要128次减法运算，128次平方运算、127次加法运算和1次开平方运算；计算街区距离需要128次减法运算，128次绝对值运算和127次加法运算。显然，就运算量而言，街区距离比欧氏距离少了开平方运算，对数目庞大的SIFT特征点，这样减少的计算量也是相当可观的。

为了排除因为图像遮挡和背景混乱而产生的无匹配关系的特征点，SIFT特征匹配没有利用最近邻匹配（最近邻定义为特征描述符之间的最小欧氏距离）作为最佳匹配，而是利用最近邻与次近邻的比来判定最佳匹配。若最近邻与次近邻的比小于某个阈值（称为匹配阈值），则认为当前点与其最近邻点是一对正确匹配，否则是错误匹配。由于正确匹配取决于距离的比，故距离的变化（DJ（x，y）≥DO（x，y））对匹配阈值的选取影响不大。

2.2 最近邻－次近邻假设算法

假设待匹配图像中任意2个特征点分别为当前图像中某个特征点的最近邻点和次近邻点。为方便起见，假设按在计算机中存储的顺序排列的前2个特征点分别为最近邻点和次近邻点。设待匹配图像中按在计算机中存储的顺序排列的SIFT特征点用y1，y2，…，yn表示，当前图像中按在计算机中存储的顺序排列的SIFT特征点用x1，x2，…，xn表示。根据式（8）计算当前图像中第一个特征点x1分别与待匹配图像中前2个特征点y1和y2之间的距离，根据这2个距离对y1和y2按距离大小排序，并将它们存入集合C中，集合C中的元素按位置编号分别称为c1、c2。设

假设C中的元素是按距离大小升序排列的，则c1和c2分别是待匹配图像2个特征点中相对于x1的最近邻点和次近邻点，即c1是dmin对应的点，c2是ds，min对应的点。

求x1与待匹配图像中第3个特征点y3之间的距离DJ（x1，y3），若DJ（x1，y3）≥ds，min，放弃y3，直接进行待匹配图像中下一个特征点的计算，即计算x1与y4之间的距离；否则，比较DJ（x1，y3）与dmin的大小，若DJ（x1，y3）≥dmin，用y3替换c2（y3成为新的c2），即y3成为待匹配图像3个特征点中相对于x1的次近邻点，此时ds，min＝DJ（x1，y3），若DJ（x1，y3）＜dmin，用y3替换c1（y3成为新的c1），即y3成为待匹配图像3个特征点中相对于x1的最近邻点，此时dmin＝DJ（x1，y3），然后进行待匹配图像中下一个特征点的计算，即计算x1与y4之间的距离。重复上述x1与y3之间的匹配过程，直到考察完待匹配图像中所有特征点为止，最终集合C中的2个元素分别是x1的最近邻和次近邻点。

求C中第一个特征点c1（最近邻点）与第二个特征点c2（次近邻点）对应的距离之比，即dmin/ds，min，若该值小于给定的匹配阈值，则认为x1与c1是一对正确匹配，否则认为x1在待匹配图像中没有匹配点。对当前图像中的其他特征点x2，x3，…，xn重复上述x1寻找匹配点的过程，直到完成当前图像中所有特征点寻找匹配点的过程为止，至此，匹配结束。

最近邻－次近邻假设算法通过假设待匹配图像中任意2个特征点为最近邻点和次近邻点，避免了特征点之间许多不必要的比较，加快了特征点匹配的速度。

3 实验结果与分析

为了验证本文算法的有效性，分别用原SIFT算法和本文算法对2对图像进行了SIFT特征匹配，结果分别如图3和图4所示。

图3 零件匹配图一（距离比阈值T＝0.6）

从图3、图4可以看到，与原SIFT特征匹配相比，本文算法对SIFT特征匹配的数量影响不大，原因在于本文算法虽然改变了特征点相似性度量的形式，但由于特征点匹配关系的确定最终取决于特征点与最近邻以及次近邻相似性度量值之比，故本文算法并未明显改变特征点匹配的数量。实验数据表明，在相同的匹配阈值下，本文算法所匹配的特征点数量比原SIFT算法所匹配的特征点数量略大。实验数据同时表明，本文算法缩短了算法的运行时间，提高了算法的运算效率。

图4 零件匹配图二（距离比阈值T＝0.36）

在（AMD Athlon）CPU 为2.01GHz、内存为512MB的微机平台上，用MATLAB语言编写的算法程序的运行结果如表1和表2所示。

表1 图3实验数据

表2 图4实验数据

4 结语

在分析SIFT特征匹配算法的基础上，本文提出了一种提高SIFT特征匹配效率的方法。该方法通过降低特征点相似性度量公式的时间复杂度，以及减少相似性计算过程中特征点比较的次数来缩减算法的计算量，从而提高了算法的效率。由于该算法并没有改变SIFT特征描述符的维数，所以该算法保持了原SIFT算法的鲁棒性。与原SIFT算法相比，本文算法能够为实时性要求较高的应用场合提供保障，具有广阔的工业应用前景。

［1］Lowe D G.Object Recognition from Local Scaleinvariant Features［C］//Proceedings of the Seventh IEEE International Conference on Computer Vision.Kerkyra，Greece，1999：1150－1157.

［2］Lowe D G.Distinctive Image Features from Scaleinvariant Keypoints［J］.International Journal of Computer Vision，2004，60（2）：91－110.

［3］夏庆观，盛党红，路红，等.零件图像特征提取和识别的研究［J］.中国机械工程，2005，16（22）：2031－2033.

［4］熊英，马惠敏.三维物体SIFT特征的提取与应用［J］.中国图像图形学报，2010，15（5）：814－819.

［5］张朝伟，周焰，吴思励，等.基于SIFT特征匹配的监控图像自动拼接［J］.计算机应用，2008，28（1）：191－194.

［6］Stephen S，Lowe D G，Little J J.Vision－based Global Localization and Mapping for Mobile Robots［J］.IEEE Transactions on Robotics，2005，21（3）：364－375.

［7］王彭林，石守东，洪小伟.基于SIFT算法的移动机器人同时定位与地图创建［J］.宁波大学学报（理工版），2008，21（1）：68－71.

［8］Ke Y，Sukthankar R.PCA－SIFT：a More Distinctive Representation for Local Image Descriptors［C］//Proceedings of the Conference on Computer Vision and Pattern Recognition. Washington，USA，2004：511－517.

［9］夏桂华，王博，朱齐丹.改进SIFT用于全景视觉移动机器人定位［J］.计算机工程与应用，2010，46（18）：196－198.

［10］刘立，彭复员，赵坤.采用简化SIFT算法实现快速图像匹配［J］.红外与激光工程，2008，37（1）：181－184.

［11］裴聪，戴立玲，卢章平.基于SIFT的简化算法下图像快速匹配［J］.制造业自动化，2010，32（1）：132－135.

［12］王晓华，傅卫平，梁元月.提高SIFT特征匹配效率的方法研究［J］.机械科学与技术，2009，28（9）：1252－1260.

［13］贾云得.机器视觉［M］.北京：科学出版社，2000.

［14］Lindeberg T.Scale－space Theory：a Basic Tool for Analyzing Structures at Different Scales［J］.Journal of Applied Statistics，1994，21（2）：225－270.

［15］刘小军，杨杰，孙坚伟，等.基于SIFT的图像配准方法［J］.红外与激光工程，2008，37（1）：156－160.

［16］王彦，傅卫平，朱虹，等.结合小波变换与SIFT特征的工件图像匹配［J］.机械科学与技术，2009，28（5）：638－642.