基于支撑描述的SIFT匹配方法

郑 红 刘振强 温天骁

(北京航空航天大学 自动化科学与电气工程学院，北京100191)

图像匹配从场景的两幅或多幅图像中确定点对应关系，是计算机视觉的重要内容，在图像配准三维重构、目标识别以及目标跟踪等领域有着广泛应用[1－5].

由于局部不变特征对图像平移、旋转、尺度、光照以及一定程度的视点变化具有不变性，基于局部不变特征的匹配方法可以获得较为精确稳定的图像匹配效果.文献[6]对多种局部不变特征算法进行评估比较，发现尺度不变特征变换(SIFT，Scale Invariant Feature Transform)算法[7]在大多数测试中表现出优秀的鲁棒性和准确性，可得到正确率较高的匹配结果.

但是由于SIFT只利用了特征点的局部邻域梯度信息，对整体图像中的局部相似结构无法有效区分，当图像中出现重复的局部结构时，极易发生误匹配现象.针对这种情况，通过极几何约束估计的方法来去除误匹配，如 M-Estimators[8]，RANSAC(RANdom SAmple Consensus)等方法.但这些方法需要用全体匹配点对进行迭代训练，其精度受错误匹配率的影响较大[9].文献[10]将全局上下文描述符与SIFT描述符通过加权方式组合在一起形成新的描述符，并通过PCA(Principal Component Analysis)降维后进行匹配.由于需要为每个特征点计算新的高维特征描述符，其过程繁琐，且PCA降维后描述符性能会有所下降.

为克服局部相似结构等因素导致的错误匹配，本文提出一种基于支持描述的SIFT匹配方法，利用SIFT初始匹配结果中具有较高稳定性的匹配特征的分布信息建立支撑特征集，对稳定性较低的匹配特征进行支撑描述，进而根据支撑描述符的匹配程度进行误匹配的剔除.算法利用了图像中关键点分布的全局信息，能够较好地区别局部相似结构中的特征点.

1 建立支撑特征集

1.1 SIFT 特征匹配

SIFT算法[7]包含了特征检测、描述和匹配的过程，主要可分为5个步骤:尺度空间极值点检测、特征点定位筛选、特征点主方向分配、特征描述向量生成及特征向量匹配.本文研究致力于SIFT特征向量的匹配过程以及误匹配的去除，特征描述向量的生成仍采用文献[7]所提出的方法.

图像的SIFT特征描述向量生成后，文献[7]采用描述向量的欧式距离作为图像之间特征点的相似性判定度量.为排除因图像遮挡和背景混乱而产生的无匹配关系的特征点，其使用最近邻与次近邻距离比值法进行匹配.取图像中的某个关键点，并找出待匹配图像中与其欧式距离最近的前两个关键点，如果最近邻距离与次近邻欧式距离的比值(r)小于阈值，则接受最近邻点为匹配点，否则不匹配.阈值较高时，能够得到大量匹配点，但错误匹配率较高，取较低阈值能够得到较高的正确匹配率，但是匹配点数大为减少.本文算法的目的就在于降低错误匹配率的同时保留尽量多的正确匹配.

1.2 支撑特征集建立

根据文献[7]针对SIFT匹配正误在不同r值下的概率密度分布统计结果[7]，可知:当 r较低(小于0.35)时，匹配正确率较高，错误匹配几乎为零;r较高时，错误匹配数量增多，匹配正确率下降，当r＞0.8时，错误匹配急剧增加.本文采用匹配特征最近邻与次近邻距离比值r作为匹配稳定性的衡量，r值越高，匹配稳定性越低.为建立支撑特征集，首先取较高 r阈值 Tr=0.8进行SIFT匹配，获得初始匹配集UI.然后对初始匹配集按r值由小到大排序，提取其中r较小的匹配点对组成支撑特征集US，初始匹配集中的剩余匹配点对构成待判别匹配集UR=UI－US.

由于从实际图像中获取到的匹配r范围不定，直接使用固定阈值不利于获取密度稳定的支撑特征集.故对初始匹配集排序后，取其中r较小的前20%作为支撑特征集.支撑特征集中的匹配点对具有较高稳定性，以其分布信息为依据，可对待判别匹配集进行误匹配的剔除.

2 支撑描述

2.1 支撑描述符

获得支撑特征集后，在每幅图像中根据待判别特征点周围支撑特征点的分布情况，分别构建对应的支撑描述符.当特征点对的支撑描述相符程度较低时，认为此特征点对为误匹配.

支撑描述符是对待判别特征点周围支撑特征点分布情况的描述.构建支撑描述符前首先对支撑特征集中的每个特征点对赋予标识编号，以使两图像中相互匹配的支撑特征点标识编号相同，且每幅图像中各支撑特征点标识编号无重复.算法中使用支撑特征点按r值排序后的排序编号作为标识编号.

每幅图像中支撑描述符的建立:以待判别特征点p为中心，以×形划分图像区域，形成ABCD 4个象限，如图1所示;在每个象限中寻找n个距中心最近的支撑特征点作为p的支撑描述点，取4个象限共4n个支撑特征点的标识编号集合作为该特征点的支撑描述符.若象限中支撑特征点不足n个，所欠缺描述点补零.

支撑描述符的维数决定于每个象限所选取点数n，由于支撑特征点本身的稳定性，较少的点数即可实现稳定的支撑描述，从而降低了计算复杂度.象限划分选取支撑描述点的方法使支撑描述点能在待判别特征点周围均匀分布，不会因某个方向支撑特征点密集而使描述点分布集中.

图2为具有尺度变化的两幅图像中一对待判别特征点的支撑描述结果，十字标示出待判别特征点位置，其支撑描述点由周围圆圈标出，每个象限选取点数n=3.

图2 特征点对的支撑描述

由图2可见对于两幅含有尺度及视角变化图像中的这一对待匹配特征点，其周围支持描述点的分布基本一致，所对应的支撑描述符可表示为

式中D(1pnew)与D(2pnew)分别为图2所示左右图中支撑描述点(圆圈标出)的标识编号的集合，标识编号由支撑特征集按r值升序排序后相应支撑特征点的序位得出.

2.2 支撑描述符的匹配

获得待判别特征点对 pl，pr的支持描述符D(pl)，D(pr)后，通过衡量支持描述符的相似程度F(D(pl)，D(pr))，来判断该特征点对是否匹配正确.两支撑描述符的相似程度由其相同支撑描述点的比例决定，可通过式(1)获得.

式中Num()表示集合中不为0元素个数的统计.

通过式(2)判断待判别特征点对是否匹配正确，如果满足式(2)，认为匹配正确，否则为误匹配.

式中，r(pl，pr)表示SIFT匹配确定该特征点对时的最近邻与次近邻距离比值;λ为正比例常数，一般取λ=1.

由式(2)可见，匹配所需支撑描述的相似度与其所对应r值成正比，r值越大，即特征点对匹配稳定性越低时，需要支撑描述符的相似度越大，而对于r值较低的相对稳定特征点对，支撑描述符的相似度要求较低.λ值是对支撑描述符相似度的整体调整，当λ增大意味着需要更强的支撑描述.经支撑描述符匹配判定正确的特征点对与支撑特征集中的特征点对合并，即获得全部的正确匹配结果.

2.3 支撑特征集的动态扩展

支撑特征集中特征点的数量及分布状况直接影响支撑描述符的生成.当初始匹配集中匹配点数目较多时，取稳定性较高的前20%即可作为有效的支撑特征集.但是当初始匹配点数目较少时，只取20%匹配点得到的支撑特征集可能存在特征点过少的问题，若任意提高从初始匹配集中取特征点的百分比，又会降低支撑特征集中支撑特征的稳定性，导致生成支撑描述符的有效性降低.

针对上述情况，提出基于动态扩展支撑特征集的支撑描述判别方法.

1)按1.2节方法获得支撑特征集;

2)从待判别匹配集取出r值最小的匹配特征点对，使用当前支撑特征集，按2.1节方法进行支撑描述符的生成.

3)按2.2节方法进行支撑描述符匹配，若经支撑描述匹配判定为正确匹配，则将此特征点对加入支撑特征集中，否则舍弃;

4)重复步骤2)和3)，直至待判别匹配集为空，最终得到的支撑特征集即全部特征匹配结果.

支撑特征集的动态扩展随匹配的进行不断扩展支撑特征集的规模，有利于提高支撑描述精确度.对于支撑特征集中可能存在的错误匹配点对(无论来自初始支撑特征集还是动态扩展中加入)，由于支撑描述符由多个描述点共同组成，少量支撑描述点的匹配错误对于支撑描述符的匹配不会产生显著影响，并且其影响只局限于错误点所在的局部区域，不会导致全局匹配判定效果的累积恶化.因此支撑特征集动态扩展能够得到稳定的匹配结果.

3 实验分析

实验图像采用富含相似结构的4种场景图像(图3)，图像场景中包含平移、尺度、旋转及视角变化.算法运行软硬件环境为:CPU 2.60 GHz，内存 2 GB，Windows XP 系统，Matlab 7.11.

图3 富含相似结构的场景图像对

为了比较算法的性能，对各图像对分别采用SIFT算法、SIFT结合RANSAC去除误匹配算法(简称SIFT+RANSAC)以及本文所提出的使用固定支撑集/扩展支撑集的基于支撑描述的SIFT匹配算法(简称SIFT+SD/SIFT+ESD)进行匹配性能对比.其中SIFT算法分别选择Tr为0.8和0.6以比较不同阈值下的匹配效果;SIFT+RANSAC算法通过RANSAC方法拟合图像间的基本矩阵去除误匹配，归一化后的距离阈值取为0.001;SIFT+SD算法取 SIFT初始匹配(Tr=0.8)r值较小的前20%为作为固定支撑特征集，每个象限支撑描述点数n=3，比例常数λ=1;SIFT+ESD算法采用动态扩展的支撑特征集，取SIFT初始匹配(Tr=0.8)r值较小的前20%为作为初始支撑集，每个象限支撑描述点数n=3，比例常数λ=1.

表1～表4分别给出了各算法针对图3所示4对场景图像匹配正误的具体数值比较.综合对比可以看出，SIFT算法(Tr=0.8)匹配正确率最低，调低r阈值(Tr=0.6)虽然提高了匹配正确率，但是也消除了较多正确匹配.SIFT+RANSAC算法与所提SIFT+ESD算法都能够保留原SIFT算法中的大部分正确匹配，但相比 SIFT+RANSAC算法，SIFT+ESD算法错误匹配数量更少，匹配正确率维持在96%以上，表现出最好的效果.特别是当原SIFT算法匹配错误比例较高的情况下(表2、表3)，SIFT+RANSAC算法匹配结果不稳定，错误匹配明显增多，而SIFT+ESD算法匹配效果则保持稳定.同时，相对于动态扩展支撑特征集的SIFT+ESD算法，使用固定支撑特征集的SIFT+SD算法效果略差.

表1 场景1图像各算法匹配结果比较

表2 场景2图像各算法匹配结果比较

表3 场景3图像各算法匹配结果比较

表4 场景4图像各算法匹配结果比较

为进一步评估所提出算法的匹配效果，将各算法对正确匹配的保留效果和错误匹配的消除效果进行比较.以SIFT算法(Tr=0.8)获得的正确和错误匹配为基准，根据表1～表4中数据得到低阈值SIFT算法(Tr=0.6)、SIFT+RANSAC算法、SIFT+SD算法以及SIFT+ESD算法的正确匹配保留率和错误匹配消除率，如表5和表6所示.其中正确匹配保留率及错误匹配消除率的计算如式(3)、式(4)所示.

表5 各算法正确匹配保留率比较 %

表6 各算法错误匹配消除率比较 %

由表5及表6可见，调低Tr的SIFT算法能够实现较高的错误匹配消除率，但是其正确匹配保留率明显下降.SIFT+RANSAC算法能保证一定的正确匹配保留率，但其正确匹配保留率较高时，相应错误匹配消除率会明显降低.本文提出的使用动态扩展支撑特征集的基于支撑描述的SIFT匹配方法(SIFT+ESD)在不同场景图像中都实现了较高的正确匹配保留率(90%以上)和错误匹配消除率(90%以上)，在保留正确匹配的同时，能够剔除更多错误匹配.使用固定支撑特征集的SIFT+SD算法相对于动态扩展支撑特征集的SIFT+ESD方法匹配效果略有不足，但与SIFT+RANSAC算法相当.

4 结论

本文提出了基于支持描述的SIFT匹配方法.通过针对不同场景图像的匹配实验，得到以下结论:

1)支撑描述符能够较好地区别局部相似结构中的特征点，所提出方法能够实现较高的正确匹配保留率和错误匹配消除率;

2)在初始误匹配比例较大的情况下，所提出方法相比RANSAC方法有着更好的稳定性;

3)根据不同特性建立支撑特征集，所提出支撑描述方法的思想可以较容易地扩展到其他特征匹配方法中.

References)

[1]蔡晓东，叶培建.基于特征点集的匹配算法应用于卫星姿态确定[J].北京航空航天大学学报，2006，32(2):171 －175

Cai Xiaodong，Ye Peijian.Image matching algorithm based on feature point set for satellite attitude calculation[J].Journal of Beijing University of Aeronauticsand Astronautics，2006，32(2):171－175(in Chinese)

[2]Piccinini P，Prati A，Cucchiara R.Real-time object detection and localization with SIFT-based clustering[J].Image and Vision Computing，2012，30(8):573 －587

[3]Ha S W，Moon Y H.Multiple object tracking using sift features and location matching[J].International Journal of Smart Home，2011，5(4):17 －26

[4]赵龙，肖军波.一种改进的运动目标抗遮挡跟踪算法[J].北京航空航天大学学报，2013，39(4):517－520

Zhao Long，Xiao Junbo.Improved algorithm of tracking moving objects under occlusions[J].Journal of Beijing University of Aeronautics and Astronautics，2013，39(4):517 － 520(in Chinese)

[5]田越，张永梅，李波.遥感图像的快速配准方法[J].北京航空航天大学学报，2008，34(11):1356－1359

Tian Yue，Zhang Yongmei，Li Bo.Fast remote sensing image registration algorithm[J].Journal of Beijing University of Aeronautics and Astronautics，2008，34(11):1356 －1359(in Chinese)

[6]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1615 －1630

[7]Lowe D G.Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision，2004，60(2):91－110

[8]Chen J H，Chen C S，Chen Y S.Fast algorithm for robust template matching with M-estimators[J].IEEE Transactions on Signal Processing，2003，51(1):230 －243

[9]Sidibe D，Montesinos P，Janaqi S.Fast and robust image matching using contextual information and relaxation[C]//Avenida D.Proceedings of 2nd International Conference on Computer Vision Theory and Applications.Esquerdo，Setubal，Portugal:INSTICC Press，2007:68 －75

[10]Mortensen E N，Deng H，Shapiro L.A sift descriptor with global context[C]//Cordelia Schmid.IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Los Alamitos，CA:IEEE Computer Society，2005，1:184 －190