一种抗视角变换的改进SIFT景象匹配算法

苏可心 ，韩广良 ，孙海江

1.中国科学院大学，北京 100039

2.中国科学院 长春光学精密机械与物理研究所 图像室，长春 130033

1 引言

近年来，精度高、突防能力强、杀伤力大的精确制导武器在现代化战争中起着主导作用[1]。而景象匹配作为高精度末制导技术已广泛应用于精确制导系统中：利用电视导引头实时获取的前视图像（实时图）与存储在弹体导引头中的目标区域图像（基准图）进行匹配，依据匹配结果判定当前是否到达目标区域，从而对目标进行精确定位，为末制导跟踪过程提供必要的目标初始信息[2]。可见，景象匹配算法的性能将直接影响末制导定位精度。

目前，基于局部特征的景象匹配成为国内外研究的热点。其中，David Lowe[3]于2004年提出的SIFT算法因其对旋转、尺度变换、光照变化等都具有良好的鲁棒性而得到广泛研究。如SURF[4]算法旨在改善SIFT的计算复杂度；针对SIFT无法适应大视角变换的缺点，Morel[5]于2009年提出ASIFT算法，通过模拟相机拍摄视角的变化，实现了全仿射不变性，但其匹配效率相对较低。

本文针对末制导导弹目标匹配阶段，弹载相机拍摄的实时图与预存的基准图之间存在大视角差异的情形，提出了一种抗视角变换的改进SIFT景象匹配算法。该算法较原始SIFT算法得到更多匹配点对并且明显提高了匹配准确率，满足工程应用需求。

2 SIFT算法原理

SIFT特征点提取与匹配过程一般包括如下4个步骤[6-9]：

（1）尺度空间极值点检测，即在图像二维平面空间和尺度空间中同时检测局部极值点。并通过拟合三维二次函数来精确特征点的位置和尺度。

（2）特征点方向分配，采用基于梯度方向直方图统计的方法来确定特征点的方向。

（3）建立特征点的描述符，SIFT描述子是对特征点邻域高斯图像梯度统计结果的一种表示。

（4）SIFT特征点集的匹配。以欧氏距离作为相似度量准则来完成特征向量集的匹配，并采用RANSAC[10]算法对匹配点对进行筛选，从而提高变换模型参数估计的准确性。

3 SIFT算法改进

通过实验发现，当实时图和基准图之间存在较大视角差异时，SIFT算法得到的匹配对数明显减少且误匹配增多。针对此问题，本文受到Matas等人[11]的启发后在提取SIFT特征点环节即步骤（1）对其进行改进：首先，在高斯尺度空间中提取抗仿射变换区域；第二，用逐层筛选的方法去除近似重复的冗余区域，得到最终尺度不变的抗仿射变换区域集；第三，采用合理的变换矩阵对不规则形状的区域集进行归一化处理；最后，由各归一化区域的圆心构成抗视角变换特征点集。下面将具体介绍其实现方法。

3.1 提取抗仿射变换区域

在SIFT算法中，特征点邻域的梯度分布直接影响特征点方向的分配以及描述符的生成。而工程实际中经常出现的视角差异过大，会导致图像发生不规则的几何形变，同时特征点邻域梯度分布也会随之发生畸变，使得SIFT算法性能明显下降。针对此问题，本文首先在SIFT的高斯尺度空间中检测抗仿射变换区域来改善算法对视角变换的适应性。将提取的区域做如下数学描述：

对于灰度图像I，满足I:D⊂Z2→S映射关系，如果S具有全序结构，并且定义了像素间的邻接关系A⊂D×D（这里采用4-邻域），那么可将图像中的区域R定义为在D上满足邻接关系A的连通子集，即对于任意的p，q∈R均有：

其中ai∈Q，i=1，2，…，n。

区域Q的边界∂Q是由不属于Q，但至少与Q中一个像素满足邻接关系的点集，即

对于区域Q⊂D及其边界∂Q，如果满足∀p∈Q和∀q∈∂Q，并且I(p)＞I(q)恒成立，则称Q为极大值区域；反之如果I(p)＜I(q)恒成立，则称Q为极小值区域。

令序列Q1，Q2，…，Qi-1，Qi，… 表示一组相互嵌套的极值区域，即Qi⊂Qi+1。如果Qi的面积变化率：

在i处取得局部最小值，则称Qi为抗仿射变换区域。式（3）中Δ表示阈值变化情况， ||•为区域面积（即区域覆盖的像素个数）。

经分析可知，提取抗仿射变换区域主要包括获取极值区域和判定抗仿射变换区域两部分。具体实现过程为：

（1）采用高效的箱排序（Bin Sort）法对输入图像像素按灰度值进行快速排序。

（2）引入分离集合森林数据结构中的并查集，即合并-查找（Union-Find）算法，维护相连区域的列表和面积；并运用按秩合并与路径压缩策略分别优化其合并与查找的过程，以快速获取极值区域。

（3）构建用于保存数据结构中相邻极值区域的成分树，当像素点全部植入森林后，即得到该图像所对应的全部极值区域。成分树的每层对应一个阈值图像，并且每层上的每个节点代表相应阈值图像上的一个极值区域。所求取的抗仿射变换区域即为成分树上当阈值在2Δ范围内变化时具有极小面积变化率的区域。

（4）最后要依据面积变化率进行区域的清除：面积变化率过大的区域稳定性差；面积变化率过小的区域多由噪声引起，本文经实验证实，保留面积变化率为0.5～1的区域，其稳定性最佳。

为更稳定地获取图像中对应目标的关联特征，本文从正、反两个方向完成区域提取过程。其中，反向过程即为提取原始图像的灰度反转图像中的区域。所提取的抗仿射变换区域如图1所示。其中，正向区域标识为绿色，反向区域标识为红色。

图1 抗仿射变换区域

由于在提取抗仿射变换区域的过程中，整个区域的信息随着融合过程的不断进行而被覆盖，结果仅剩最后一个抗仿射变换区域的空间位置及其对应阈值。因此要得到全部抗仿射变换区域，需对该区域重新做阈值化处理，导致算法的时间复杂度过高，针对此问题，本文参考文献[12]的方法，采用邻域四叉树的数据结构将双向链表和分离集合森林结合在一起，以便恢复那些存在于任意一棵树上的节点信息，从而实现对该过程的加速。对于提取抗仿射变换区域来说，即意味着给出任意一个像素点及灰度阈值，就可以根据邻域四叉树算法求出区域的全部像素信息，从而有效降低该过程的时间复杂度。

3.2 获得抗视角变换特征点集

针对高斯尺度空间中检测图像的抗仿射变换区域时存在区域重复提取的问题，本文采用逐层筛选的方法对冗余的区域进行处理：

（1）将高斯尺度空间第i层的区域ai变换至第i+1层的尺度上，并表示为区域a′i+1。

（2）设ai+1为第i+1层中与之对应的区域，若同时满足关系：

则消除第i+1层的相应区域ai+1。其中，C表示对应区域的质心，S表示区域的面积。经实验验证，Δ1=3，Δ2=0.2时所得到的区域最稳定。

（3）逐层进行相同的处理，直至遍历整个高斯尺度空间后即得到尺度不变的抗仿射变换区域集。

由于得到的抗仿射变换区域的形状是不规则的，不利于特征描述的操作，因此需对这些特征区域进行合理的数学拟合及规则化处理[13]。由于特征区域协方差矩阵的特征值和特征向量唯一确定一个椭圆，因此本文采用椭圆拟合方法。即通过变换矩阵A将圆映射为椭圆的方式进行特征区域拟合。

设灰度图像I(x，y)中抗仿射变换区域Φ的质心为Xc=(xc，yc)T，则以 Xc为圆心单位圆上的 X满足：

矩阵A将圆上的点X映射到椭圆上，故有：

比较式（6）、式（7）可知：

式（7）、式（8）中，Κ为抗仿射变换区域Φ的协方差矩阵，I为二阶单位矩阵，设：

其中m20、m11、m02为Φ的二阶中心矩，分别定义为：该式中m00为Φ的面积，(xc，yc)为Φ的质心坐标，计算公式分别为：

联立式（8）、式（9），可推导出变换矩阵 A为：

通过式（13）中的矩阵A可将不规则形状的抗仿射变换区域Φ映射为一个椭圆。其中，椭圆的形状和主轴倾角由Φ的二阶中心矩构成的协方差矩阵唯一确定，中心与Φ的质心重合。图2为对抗仿射变换区域进行椭圆拟合的结果。

图2 抗仿射变换区域的椭圆拟合结果

为便于关联特征间比较，需进一步对得到的椭圆区域进行归一化处理，即将不同尺寸的椭圆拟合区域映射为某个固定大小的圆形区域。假设待规则化的椭圆中心在点 X′c处，区域规则化的数学描述为：对于椭圆上的点 X=(x，y)T，寻找一个2×2的变换矩阵 A，使得式（14）成立。

其中r为规则化后的圆半径。因为点X在椭圆上，故有：

其中 Κ 为协方差矩阵（见式（9））。由式（14）、式（15）可以推导出：

联立式（9）、式（16）可求得：

至此，通过变换矩阵A可将椭圆区域映射至一个固定大小的圆域。对于各圆域，本文取圆心处为特征点位置，即构成抗视角变换特征点集。图3为分别取自待匹配图像中某椭圆拟合区域的归一化结果及特征点位置。

图3 分别取自待匹配图像中某椭圆拟合区域的归一化结果及特征点位置

可见，本文采用的椭圆拟合、归一化抗仿射变换区域、选取特征点的方法能够有效消除形变干扰，使特征区域在形态上表现出较强的视觉一致性，有效提取出便于描述和匹配的抗视角变换特征点集。图4为提取的抗视角变换特征点集。

图4 抗视角变换特征点集

3.3 抗视角变换特征点集匹配

对上述提取的抗视角变换特征点集运用SIFT算法的步骤（2）～（4）进行描述和匹配，本文采用最小欧氏距离作为匹配准则，即以k-d树搜索策略在欧氏空间中搜索各特征向量的最近邻和次近邻，当两者之比小于某个阈值（实验中设定为0.7），则认为两特征向量匹配。并引入RANSAC算法对特征匹配结果进行误匹配剔除，完成匹配。

4 仿真结果及实验分析

实验仿真平台的硬件环境为：Intel®CoreTMi3-2120 CPU，主频3.29 GHz，内存2 GB的PC机；软件开发工具为：Windows XP 操作系统、VC++6.0、MatlabR2010b。实验所采用的图像分别来自Mikolajczyk数据集[14]和实拍图片。

首先采用 640×800、视角分别为 70°和 20°（视角差为50°）的Graf图片进行实验。实验结果如图5所示，其中（a）为SIFT的匹配结果；（b）和（c）分别为本文算法的粗匹配及去除误匹配后的结果；（d）和（e）分别为SURF、ASIFT的匹配结果；实验数据见表1。

表1 视角差为50°的Graf图片匹配实验数据

图5 视角差为50°的Graf图片匹配实验结果

实验中设定SIFT和本文算法的阈值均为0.6。从图5及表1中可以看出：在视角差为50°时，SIFT、SURF算法虽耗时较少，但是误匹配点对增多、匹配可信度明显下降。ASIFT算法由于实现了全仿射不变性，其匹配效果最佳，对视角变换的鲁棒性最好，但由于其算法复杂度高，匹配效率低的缺点，很难满足工程实际要求。本文算法较SIFT算法增加19组准确匹配点对，准确率提高约4.55倍；较SURF算法增加17组准确匹配点对；相比ASIFT算法，本文算法在耗时方面亦有明显优势。

进一步加大待匹配图像的视角差异：采用640×800、视角分别为60°和0°（视角差为60°）的Graf图片进行实验，限于篇幅，图6仅给出SIFT算法、本文算法及其去除误匹配的实验结果，实验数据见表2。

表2 视角差为60°的Graf图片匹配实验数据

从图6及表2中可以看出：在视角差为60°时，本文算法较SIFT算法增加18组准确匹配点对，匹配准确率提高近5倍；较SURF算法增加17组准确匹配点对；对大视角差异表现出良好的适应性。ASIFT算法的匹配效果最佳，但耗时仍最多。

将本文算法用于实际光电成像制导过程：模拟弹载相机在俯仰角为－63°、飞行高度为1 000 m时拍摄的实时图与弹体预存的卫星航拍目标区域基准图（均为315×315）的匹配。图7中（a）为SIFT算法的匹配结果；（b）为本文算法的匹配结果，实验数据见表3。

从图7及表3中可以看出：存在尺度、视角变换情形的光电成像制导过程中，本文算法较SIFT、SURF算法得到更多匹配点对，且匹配点对相对均匀地分布在目标场景内，明显提高了匹配可信度；较ASIFT算法耗时更少、具备更高的工程实用价值。

图7 存在尺度、视角变换情形的匹配实验结果

表3 存在尺度、视角变换情形的匹配实验数据

图8为一组模拟弹载相机在航向角为20°、俯仰角为－65°、飞行高度为1 100 m时拍摄的实时图与预存基准图的匹配实验结果。其中，（a）、（b）分别为SIFT和本文算法的匹配结果，实验数据见表4。

图8 存在旋转、尺度和视角变换情形的匹配实验结果

从图8及表4中可以看出：本文算法在光电成像制导过程中当基准图和实时图之间存在旋转、尺度和较大视角差异时，也能快速准确地捕获目标区域，从而尽早为末制导跟踪系统提供精准的目标初始态信息。具备较高的工程应用价值。

表4 存在旋转、尺度和视角变换情形的匹配实验数据

从上述各组实验中均可以看出，与SIFT、SURF算法相比，本文算法对大视角变换具有良好的鲁棒性。但在明显增加正确匹配点对数的同时，算法耗时增多，这是由于：虽然本文算法相当于只对部分图像计算SIFT描述子并进行匹配，且引入邻域四叉树策略在一定程度上降低了算法的时间复杂度，但在高斯尺度空间中提取抗仿射变换区域，进而得到抗视角变换特征点集是算法中最耗时的环节，这一点仍有待进一步优化。同时，本文算法较ASIFT算法时间复杂度更低、实时性更强。可见，本文算法在匹配准确度和算法耗时两方面实现了良好的折衷。

5 结束语

本文针对光电成像制导过程中，导引头目标场景自动识别的实时图和基准图之间存在较大视角差异时，SIFT算法的正确匹配点对数减少从而影响对变换模型参数估计的情况，提出了一种抗视角变换的改进SIFT景象匹配算法。仿真结果表明，该算法相比SIFT、SURF算法，在视角差高达50°～60°以上的情况下得到的正确匹配点对数明显增加，有效提高了匹配算法的可信度。并且较ASIFT具有更低的时间复杂度，利于实时性的实现。后续将针对本文算法的优化和加速开展工作。

[1]陈冰，赵亦工，李欣.基于快速鲁棒性特征的景象匹配[J].系统工程与电子技术，2009，31（11）：2714-2718.

[2]邸男，李桂菊，魏雅娟.采用SIFT的末制导图像匹配技术[J].红外与激光工程，2011，40（8）：1549-1593.

[3]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vsion，2004，60（2）：91-110.

[4]Herbert B，Tinne T，Luc V G.SURF：speeded up robust features[J].ComputerVision and ImageUnderstanding，2008，110（3）：346-359.

[5]Morel J M，Yu G.ASIFT：a new framework for fully affine invariant imagecomparison[J].SIAM Journal onImaging Science，2009，2（2）：438-468.

[6]丘文涛，赵建，刘杰.结合区域分割的SIFT图像匹配方法[J].液晶与显示，2012，27（6）：827-831.

[7]吕倩利，邵永社.基于SIFT特征的异源遥感影像匹配方法研究[J].计算机工程与应用，2012，48（36）：171-176.

[8]王民，刘伟光.基于改进SIFT特征的双目图像匹配算法[J].计算机工程与应用，2013，49（2）：203-206.

[9]孔军，汤心溢，蒋敏.多尺度特征提取的双目视觉匹配[J].计算机工程与应用，2010，46（33）：1-5.

[10]Fischler M A，Bolles R C.Random sample consensus：a paradigm for model fitting with applications to image analysisand automated cartography[J].Communications of the ACM，1981，24（6）：381-395.

[11]Matas J，Chum O，Urban M，et al.Robust wide-baseline stereo from maximally stable extremal regions[J].Image Vision Computing，2004，22（10）：761-767.

[12]孙晶.图像局部不变特征提取技术研究及其应用[D].辽宁大连：大连理工大学，2009.

[13]廉蔺，李国辉，王海涛，等.基于MSER的红外与可见光图像关联特征提取算法[J].电子与信息学报，2011，37（7）：1625-1631.

[14]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

[15]严磊，汪增福.基于多局部特征匹配的全自动图像拼接[J].计算机应用与软件，2010，27（10）：5-7.

[16]Mikolajczyk K，Schmid C.Scale&affine invariant interest point detectors[J].International Journal of Computer Vision，2004，60（1）：63-86.

[17]王永明，王贵锦.图像局部不变性特征与描述[M].北京：国防工业出版社，2010：150-163.