基于空间约束的快速鲁棒特征匹配优化

赵 烨蒋建国 洪日昌

(合肥工业大学计算机与信息学院 合肥 230009)

1 引言

基于特征的配准方法以其计算量较少、速度快等特点广泛应用于机器视觉、图像拼接、目标识别、3维重建、图片旅游、视频摘要等诸多领域[14]-。尤其以基于 Lowe[5,6]提出的尺度不变特征转换 (Scale Invariant Feature Transform, SIFT)算法应用较为广泛。SIFT算法将尺度不变特征子与梯度方向描述子相结合，具有图像缩放、旋转、光照和仿射不变性等优点。然而由于 SIFT描述子的维度较高导致计算过于复杂，难以满足在对速度要求高的场景。为了降低计算复杂度，缩短匹配时间，随后有很多研究人员提出了各种基于 SIFT 的改进算法。文献[7]提出了采用主成分分析(Principal Component Analysis, PCA)的方法对 SIFT描述子进行降维的PCA-SIFT算法，其算法中PCA-SIFT描述子的维度可以降低到 20维，但是该描述子的通用性不如SIFT描述子，需要通过有代表性的图像计算投影矩阵，并且在执行快速匹配时的精度也不如SIFT，不太满足实际应用[8]。文献[9]提出梯度位置方向直方图 (Gradient Location Orientation Histogram,GLOH)算法，把SIFT中棋盘格状的块状分区变成同心圆形的放射状分区，再使用PCA降低维度。该算子的独特性比 SIFT要好，但是计算更复杂。文献[10]提出的快速鲁棒特征(Speeded Up Robust Features, SURF)算法是一种快速的特征检测和描述算法。该算法在特征点检测和向量描述中巧妙地利用快速积分和箱式滤波，在继承 SIFT算法对图像缩放与亮度变化不敏感、抗干扰以及鲁棒性强的同时，大幅加快了特征的提取速度，基于SURF特征配准已成为模式识别领域中的一个新的研究热点。

但是SURF的匹配精度还不够优良，得到的特征匹配点还存在一定数量的误匹配。而SURF主要应用在图像处理的前端，其配准精度直接影响到整个系统性能。为了进一步提高SURF匹配精度，文献[11]提出了结合颜色和全局特征的 SURF特征算法，文献[12]通过加权的方式把 SURF特征与局部颜色直方图结合起来。鉴于视觉词之间的几何关系在图像识别中起到重要作用，近来文献[13]采用最佳尺度空间的选择来提高匹配性能，虽然以上的改进算法在一定程度上提高了匹配精度，但由于计算过于复杂，时间消耗非常大。因此，在保证计算复杂度基本不变的要求下，如何提高SURF匹配精度仍然是尚待解决的问题。

在以往算法中，特征点之间的空间关系往往被忽略，这使得计算成本高昂。特征点间的空间关系很容易获得，而且计算简便易行，为此本文提出一种基于空间约束的 SURF特征匹配优化算法(SC-SURF)，通过选择最优匹配点计算投影矩阵，同时利用最优匹配点构造参考坐标系产生空间信息表，二者结合起来对按匹配度加权的匹配点进行几何核查，以提高匹配的高效性和有效性。

2 SURF特征点匹配

SURF算法利用最近邻比率方法判断匹配度，最近邻比率算法就是使用最近邻距离与次近邻距离的比值作为两幅图像的相似性判定度量，当该比值在一定的阈值范围内时则认定该特征点是匹配特征点。

距离比阈值是特征点之间建立匹配关系的纽带。Lowe的实验给出了距离比与概率密度分布曲线，如图1所示。阈值越小，匹配点的正确概率越大，然而匹配点数越少；阈值越大，匹配点数越多，但匹配准确率越小。Lowe将距离比阈值设为0.8。本文在SURF特征点匹配中按照最近邻比率对匹配点进行优先队列实现。

通过上面方法对SURF特征点进行匹配，得到的匹配点仍然存在一定数量的误匹配，为了提高匹配精度，需要对特征点进行二次匹配。

3 SURF特征点的二次匹配

3.1 几何校验方法

为了进一步提纯和滤除误匹配，一般采用几何校验来实现SURF特征点的二次匹配。应用最广泛的几何校验方法是随机抽样一致性(RANSAC)算法[14]。它是一种在一组观测数据集中估计模型参数的迭代方法，可以从数据样本中准确拟合数学模型，然后采用随机抽样验证去除噪声点。但该方法的性能在外点较多的情况下将受到很大影响，而且计算复杂度高，得到的结果并不理想。所以SURF的几何校验策略需要一种更简便有效的方法。为此本文提出利用简化的 RANSAC算法结合空间约束策略来实现几何校验。

3.2 二次匹配优化策略

特征点间的空间关系很容易获得，而且计算简便易行，本文从SURF特征点之间的相对空间关系出发，以最优匹配点构造参考坐标生成空间约束矩阵，可以大大地简化计算复杂度。同时选择最优匹配点做为初始数据集进而简化 RANSAC算法，最后二者结合起来通过正误率分析实现几何校验。

3.2.1空间约束矩阵 SURF匹配点之间的空间位置信息可以用一个矩阵表示[15]，对于任意N个匹配点，第i个和第j个匹配点满足关系，从而使得空间信息表M中元素取值如式(1)，式(2)所示。

匹配点在新坐标系下的坐标为

那么形成了3维空间约束矩阵M：

图1 Lowe实验的概率密度分布曲线

3.2.2简化的RANSAC算法 RANSAC算法模型的参数估计是不断通过内外点进行迭代计算和反复测试来完成的，初始模型参数是由随机抽取样本数据计算得到的，所以具有很大的不确定性，而初始参数的优劣直接决定着迭代次数和计算成本。本文简化 RANSAC的方法是选择少数最优匹配点作为初始样本数据，这样得到初始模型参数很接近真实值，可以通过设置尽量少的迭代次数来得到尽量真实的单应性矩阵参数，提高了计算效率。

本文选择投影变换矩阵作为图像变换模型，变换关系为

这是8个参数的投影变换，至少需要4个匹配对来生成，利用最小二乘法求解这8个参数。

初始样本数据数目n可按照式(9)确定：

这里0N是一次匹配的匹配点数目，并且为样本数目步长, μ为比例因数。

3.2.3空间几何校验 待配准的两幅图像根据相应的匹配对分别产生空间约束矩阵和，对和矩阵中的异值点进行统计，生成异值矩阵W：

为了确保匹配精度，K值选择应大于 2，但考虑到运算速度，K取值又不能过大，一般选择K=3。最后得到特征点在空间约束矩阵下的错误率为id。

图2 最优匹配点构成参考坐标系

设模型参数变换得到匹配点坐标值与实际坐标的距离值为jd，匹配点判别按照式(12)进行，由于透视变换矩阵仅为少数数据得出，不能保证求得最精确的结果，所以采用两个约束条件相互补充。

式中α为比例因子, γ均为距离阈值。

4 实验结果与分析

实验的运行环境为 Genuine Intel(R) T2400(CPU), 1.83 GHz主频，2 G内存的PC机。采用牛津大学的局部仿射变换数据集[16]，分别对SC-SURF算法与SIFT算法、SURF算法和带有RANSAC校验的SURF算法进行了对比实验，匹配性能主要从匹配准确率(Precision)-召回率(Recall)和匹配速度两个方面进行分析。鉴于准确率与召回率往往是矛盾的，因此本文又采用一个综合指标加权调和平均(F-Measure)来帮助分析，加权调和平均是准确率和召回率加权调和平均：

4.1 匹配性能测试实验

对测试图像在旋转和尺度变化、视角变化、模糊变化、光照变化和JPEG压缩等典型变换下进行了匹配实验。其中SIFT的对比度阈值为0.02, S为3, O为7, SURF的描述子为64维，SC-SURF中的比例因子α根据多次测试实验效果最佳时的取值为0.1，距离阈值。利用已知的单向性矩阵判断匹配效果，最后将大量的实验数据平均后，得到各种典型变换下各算法的查准率-召回率曲线和加权调和平均曲线，如图 3～图 7所示。在旋转和尺度变换情况下，测试图像角度旋转3045°°～，尺度因子变化1～4倍。视角变化的测试图片不仅有60°的旋转视角，还有尺度和照度上的变化。从图3，图4的曲线中可以看出SC-SURF算法不论在尺度、旋转变化还是视角变化下的匹配效果均好于其他算法。这是因为加入了空间约束和旋转坐标，所以 SC-SURF具有更好的旋转不变性和尺度不变性。

JPEG序列是利用标准的xv图像浏览器通过改变图像质量参数从40\%到2\%产生的，在抗JPEG压缩方面，如图7所示，SURF算法与RANSACSURF和 SC-SURF效果差异不大，都能很有效地抗压缩变化。在以上各种图像变换的情况下，SIFT的准确率指标较好，但其召回率较差，所以综合指标加权调和平均性能较低，然而 DoG检测子比Hessian检测子可以提取更多的特征点数，一般SIFT检测到的特征点数目是SURF检测到的2～5倍。因此在对匹配速度要求不高的情况下，SIFT算法还是比SURF得到更广泛的应用。

图3 视角变化时各算法的性能比较

图4 缩放旋转变化时各算法的性能比较

图5 光照变化时各算法的性能比较

图6 图像模糊时各算法的性能比较

图7 JPEG压缩时各算法的性能比较

图8给出了在视角变化下的匹配示例。测试图像为Graf中img1与img2，距离比阈值为0.7，匹配结果为：SIFT的匹配点对是1230对，其中正确匹配对是1179对，配准率为0.95854。SURF的匹配点对是734对，其中正确匹配对是611对，配准率为0.8324。RANSAC-SURF的匹配点对是695对，其中正确匹配对是 611对，配准率为 0.8791。SCSURF的匹配点对是691对，其中正确匹配对是611对，配准率为 0.8842。绿色空心圆为正确匹配点，红色十字形表示错误匹配点，可见 SIFT的配准率是最高的。

图9所示是4种算法在近重复图像下的匹配示例。

综合上面的实验结果，SC-SURF的匹配性能明显优于其他算法，在匹配的有效性上相比于原始SURF有很大的改进。

4.2 匹配速度测试实验

为了评估SC-SURF算法的计算复杂度，对这4种算法进行匹配速度测试。为了统一参数，SC-SURF算法与其余3种算法的距离比阈值均设为0.7，其余参数设置与上面实验相同。在前面所述的运行环境下，样本数目取100对，图10给出了SIFT和SURF匹配时间的比较，图11比较了RANSACSURF和SC-SURF的二次匹配时间。

由以上图表可知，RANSAC-SURF在个别情况下的计算复杂度很高，这是由于样本点中的外点过多，而 RANSAC要拟合的仿射矩阵总是受污点感染而达不到最优矩阵造成的。SIFT和 SURF的运行时间主要取决于检测到特征点的数目。SIFT的运行时间远远大于SURF，大约是SURF的10～30倍。同时 SC-SURF的二次匹配运行速度相对RANSAC-SURF快3～100倍，在个别情况时能高达几千倍，它的运行时间大约是SURF的2%左右，所以本文算法相对于原始SURF运行时间基本保持一致，但匹配精度大大提高。本文算法相对于RANSAC-SURF运行速度大幅度提高，同时匹配精度也比后者略好。

5 结束语

本文以SURF作为图像的局部特征，构建了一种基于空间约束的 SURF特征点匹配的优化算法SC-SURF。为提高算法对各类变化图像的适应性，在 BBF匹配搜索中按照最近邻比率进行优先级排序，把匹配点间的空间约束关系和简化的RANSAC算法结合起来进行几何校验，从而提高匹配精度和速度。通过对在图像缩放和旋转、光照、视角、模糊和压缩等图像典型变化下的实验数据进行分析，SC-SURF算法在匹配准确率上明显超过 SURF和SIFT算法，在匹配时间上控制在毫秒级，在保持与SURF运行时间几乎不变情况下，大幅提高了匹配精度。同时在比 RANSAC-SURF的匹配精度略好的情况下，减少了计算复杂度。该算法在实际应用中仍存在很多待改进之处，由于对最优匹配点依赖性较强，因此如何进一步完善最优匹配的选择条件，是下一步待研究的问题。

图8 视角变化的匹配结果(绿色圆形符号表示正确匹配点，红色十字形符号表示错误匹配点)

图9 匹配实例(由上到下依次是SIFT, SURF, RANSAC-SURF和SC-SURF)

图10 SURF与SIFT运行时间对比

图11 SC-SURF与RANSAC-SURF二次匹配运行时间对比

[1] Rudinac S, Larson M, and Hanjalic A. Learning crowdsourced user preferences for visual summarization of image collections[J]. IEEE Transactions on Multimedia, 2013,15(6): 1231-1243.

[2] Wang M, Ni B, Hua X, et al.. Assistive tagging: a survey of multimedia tagging with human-computer joint exploration[J]. ACM Computing Surveys, 2012, 44(4): 1-25.Conference on Computer Vision, Los Alamitos, 1999:1150-1157.

[6] Lowe D. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision, 2004,60(2): 91-110

[7] Ke Y and Sukthankar R. PCA-SIFT: a more distinctive representation for local image descriptors[C]. Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Washington D. C., 2004: 506-513.

[8] Juan L and Gwun O. A comparison of SIFT, PCA-SIFT and SURF [J]. International Journal of Image Processing, 2009,3(4): 143-152.

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

[10] Bay H, Ess A, Tuytelaars T, et al.. Speeded-Up Robust Features (SURF)[J]. International Journal on Computer Vision and Image Understanding, 2008, 110(3): 346-359.

[11] Yoon H, Chung H, and Hahn H. SURF Algorithm with color and global characteristics[C]. Proceedings of ICCAS-SICE International Joint Conference, Fukuoka, 2009: 183-187.

[12] Fan P, Men A, Chen M, et al.. Color-SURF: a SURF descriptor with local kernel color histograms [C]. Proceedings of IEEE International Conference on Network Infrastructure and Digit Content Proceedings, Beijing, 2009: 726-730.

[13] Ehsan S, Kanwal N, Clark A, et al.. An algorithm for the contextual adaption of SURF octave selection with good matching performance: best octaves [J]. IEEE Transactions on Image Processing, 2012, 21(1): 297-304.

[14] Fischler M and Bolles R. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the Association for Computing Machinery, 1981, 24(6):381-395.

[15] Zhou W, Lu Y, Li H, et al.. Spatial coding for large scale partial-duplicate web image search[C]. Proceedings of the 18th ACM the International Conference on Multimedia, New York, 2010: 25-29.

[16] The Oxford University: Affine Covariant Features Database of Oxford University[OL]. http://www.robots.ox.ac.uk,2012.4.