结合FAST-SURF和改进k-d树最近邻查找的图像配准

陈剑虹， 韩小珍

(西安理工大学 机械与精密仪器工程学院，陕西 西安 710048)



结合FAST-SURF和改进k-d树最近邻查找的图像配准

陈剑虹， 韩小珍

(西安理工大学 机械与精密仪器工程学院，陕西 西安 710048)

针对两图像之间存在平移和旋转变化的图像匹配，提出了一种结合FAST-SURF和改进k-d树最近邻查找的图像配准算法。该算法首先用FAST(加速分割检测特征)检测器进行特征点提取，然后根据特征点周围邻域的信息生成SURF(快速鲁棒特征)描述子，采用一种改进的k-d树最近邻查找算法BBF(最优节点优先)寻找特征点的最近邻点及次近邻点，接着进行双向匹配得到初匹配点对，最后利用RANSAC(随机抽样一致性)算法消除误匹配点，findHomography函数寻找单应性变化矩阵，从而计算出图像间的相对平移量和旋转量。实验结果表明，该算法平移参数的最大误差为0.022个像素，旋转参数的最大误差为0.045度，优于传统的SURF图像匹配算法，实现了图像的快速、高精度配准。

图像匹配； FAST-SURF算法； BBF； 双向匹配； RANSAC

图像匹配是常见的一种图像处理技术，它是将处于不同传感器、不同时刻、或者不同条件下的两幅图像进行对准的过程，用以找到两幅图像间的平移及旋转关系，广泛用于遥感图像分析、工业检测、图像融合等领域[1]。在很多应用场景中，例如遥感图像配准、图像测量等领域，对图像配准精度有较高要求。

图像匹配算法一般有基于灰度值的匹配和基于特征的匹配[2]两大类。前者是根据图像间像素点的灰度值来进行相似性比较的一种算法，该算法计算量相对较大，需要逐像素进行比较，匹配精度高，适用于图像间存在平移变换的图像匹配。后者是先提取特征点，然后采用一定的方法生成描述向量，最后实现特征配准的一种算法。该算法优点是匹配速度快，抗噪声能力强，而且对仿射变换、光照等都有比较强的鲁棒性。典型的特征点提取算法主要有Moravec、SUSAN[3]、Harris[4]、SIFT[5-6](Scale-invariant Feature Transform) 以及SURF (Speeded Up Robust Feature) 算子等。其中，使用较多的有Harris、SIFT和SURF算子。Lowe[7]等人提出的SIFT算法在噪声、仿射变换等方面都具备非常好的匹配能力，尤其是在抗旋转方面，但SIFT算法在计算的过程中会产生大量的描述符，从而引起计算量大、运行时间长的问题。Bay等人在2006年提出了SURF算法[8]，该算法在匹配的过程中引入了积分图像，从而使其匹配速度远远超过了SIFT算法，然而此类关键点特征运算量还是过于庞大，检测的特征点数目过少，导致获得的匹配点数量少，降低了匹配的效率。Rosten等人提出了一种快速、有效的FAST特征点检测算法[9]，该算法既减少了检测时间，又进一步提取了图像细节处的特征点，提高了匹配精度。

因此，笔者提出了一种结合FAST-SURF和改进的k-d树最近邻查找的图像配准算法，该算法用FAST检测器对特征点进行提取，同时结合了SURF特征描述子，并用BBF算法进行查找，然后利用双向匹配算法获取初匹配点对，实现了对传统单向匹配算法的改进，最后使用RANSAC实现精确匹配，计算得出变化参数。实验仿真结果表明，本文算法对于图像间存在平移、旋转变化有非常好的配准效果。

1　算法介绍

由于FAST算法在检测特征点方面具有快速和稳定的特性，可用它来进行角点的检测。本文基于FAST的特征检测来取代基于SURF特征检测，提高了提取速度，同时与SURF描述子相结合，使特征点具有抗旋转特性。

在特征匹配过程中，采用BBF算法实现最近邻查找，然后用双向匹配算法得到初匹配点对，最后使用RANSAC算法实现精确匹配，该算法的流程如图1所示。

图1　算法流程图Fig.1　Algorithm flowchart

算法的具体步骤如下: ①采用FAST算法检测特征点; ②根据特征点周围的邻域信息生成SURF描述子: ③利用改进的k-d树BBF算法对特征点进行查找，使用双向匹配算法进行粗匹配; ④使用RANSAC实现精确匹配，并计算得出变化参数。

1.1FAST特征点检测

FAST特征检测算法是利用特征点周围的图像灰度值来定义的，是非常简单又快速的特征检测算子。如图2所示，该算法通过选定图像中的任意一个像素点作为候选特征点，并以该候选特征点为圆心构造一个圆形区域，检测圆周上的像素灰度值，并与该候选点的灰度值进行比较，假如两者的灰度值差别很大，并且圆周上满足这一条件的点数足够多，则选定该候选点为特征点。

图2　FAST特征点提取Fig.2　Detection of FAST feature

特征点的判断过程为：设I(p)为候选特征点p的灰度值，I(x)为圆周上点x的像素灰度值，εd为给定阈值。以N表示满足下述公式的圆周上像素点x的个数：

|I(x)-I(p)|>εd

(1)

如果满足判定条件的像素点数N大于设定值，一般为周围圆周点的四分之三，即认为p是特征点。

本文采用FAST角点提取改进算法，使其可以快速的排除一些非特征点，从而加快了算法的提取速度。首先检测候选点p圆周上每隔90°角的4个点(点1、5、9、13)，如果这4个像素点至少有3个满足公式(1)，则再计算其他点；假如不满足，则认为此候选点不是特征点。

1.2SURF特征点描述

1.2.1特征点主方向的选取

完成特征点的检测后，必须对其进行主方向的选取。首先，构建一个圆形区域，该区域将特征点设为中心，半径设为6s(s即特征点的尺度值)，然后计算区域内像素点的Haar小波响应值。

如图3所示，左侧为Haar小波在x方向上的响应，右侧为Haar小波在y方向上的响应，将高斯权重系数赋予响应值，使离特征点近的Haar响应贡献比较大，而离特征点远的贡献比较小，把60度区域内的所有响应相加，获得新的矢量，接着遍历整个区域，特征点主方向即为矢量最长的方向。

最后计算每个特征点，获得所有特征点的主方向[10]。

图3　Haar小波响应Fig.3　Response of Haar wavelet

1.2.2特征点描述符的生成

生成SURF描述符的第一步是构造一个正方形区域，将特征点设为该区域的中心，边长设为20s，区域方向设置为与特征点方向一致。

如图4所示，然后对该区域实现等间隔采样(采样间隔为s)，并将其划分成4×4=16个子区域，计算这些子区域Haar小波响应。

图4　描述符表示Fig.4　Representation of a descriptor

(2)

将16个子区域的V组合在一起，获得16×4=64维特征描述向量，即生成了SURF描述符。

1.3FAST-SURF算法

FAST特征检测的优点主要有以下几点。

1) 计算简单、快速。FAST检测算子是通过特征点周围的灰度值来判断是否为特征点，操作方便。

2)FAST特征检测子可以提取大量的有用的特征点，即提取的特征点大多位于图像的细节区域，避免了边缘区域提取太多的特征点的问题。

3) 如果图像存在平移、旋转变换，FAST角点检测子依然很稳定。

SURF特征检测算法的优点是具有尺度不变性，当图像发生仿射、光照、噪声等变换时，该算法也具有很好的稳定性。尽管SURF算法在特征检测方面具有很多优点，但由于其特征检测数量相对较少，速度较慢，降低了图像的匹配速度和精确度。

针对此问题，本文用FAST角点检测器来替代传统的SURF特征检测器，克服了传统的SURF检测子提取特征点少，计算量大的问题，同时又保留了SURF描述子的抗旋转特性，实现了对SURF算法较好的改进。

1.4改进的k-d树最近邻查找算法的特征点匹配

利用FAST角点检测器和SURF特征描述子得到特征点后，要实现图像匹配。

针对普通的k-d树最近邻查找算法对于高维数据的查找时间较长，速度慢的缺点，本文采用了一种改进的k-d树BBF查找算法来替代传统的k-d树查找方法。BBF算法由于在k-d树算法的基础上加入了优先队列，即在形成搜索路径的同时也形成了优先队列，在回溯查找的过程主要按照优先队列来进行查找，从而避免了重复路径的搜索过程，进一步提高了搜索效率。

本文首先利用归一化的欧氏距离准则[11]，得到两幅图像特征点之间的相似性距离，然后建立64维的k-d树，采用改进的k-d树算法在待匹配图像中查找与原图像欧氏距离最近的特征点和次近的特征点，利用比率法判断是否匹配，即最近距离与次近距离相除，假如比值结果小于某个阈值(本文取0.6)，则确定该点为匹配点。

通常阈值选取值越小越好。通过对大量任意存在尺度、旋转和亮度变化的两幅图片进行匹配，结果表明ratio取值在0.4～0.6之间最佳，小于0.4的很少有匹配点，大于0.6的则存在大量错误匹配点，因此本文选择0.6作为阈值。

上述算法实现了两幅图像之间的单向匹配，为了提高匹配精度，本文将单向匹配进行改进，实现图像间的双向匹配。首先将原图像和待匹配图像实现匹配，获取第一组匹配点对，接着反过来将待匹配图像与原图像实现匹配，获取第二组匹配点对，将这两组中相同的匹配点对提取出来作为最终的匹配结果。

1.5变换参数的计算

本文研究图像间发生平移与旋转的仿射变化关系，图像进行特征点匹配后，根据匹配的特征点对可以得出单应性变换矩阵，从而进一步获得图像间的相对变化参数。

设(X,Y)和(x,y)为两幅图像的任意一对匹配点对，则有：

(3)

根据其变化关系，H矩阵可表示为：

(4)

其中，θ为旋转角度，Δx、Δy分别为x方向和y方向的像素平移量。

为了提高H的计算精度，本文采用RANSAC[12]算法来消除误匹配点对，从而获得更准确的变换参数。RANSAC算法的基本内容是：

1) 任意选取两幅图像的3组匹配点对，可估算出H矩阵的6个参数值；

2) 使用H矩阵对剩余的匹配点对来进行判别，对匹配的内点和外点进行区分，并且记录内点的总体数量，用得到的新内点再次计算H的各个参数；

3) 当内点数量达到最多时，采用该组内点计算H的最佳参数。

在程序中，使用cv::findHomography函数计算单应性变换，利用RANSAC算法求取最佳H矩阵。

2　实验结果及分析

实验仿真平台的硬件环境为：Intel(R)Core(TM)i3-2330MCPU，主频2.20GHz，内存2.00GB的PC机；软件开发工具为：Windows7操作系统、VS2010+OpenCV2.4.9[13]。

为了验证本文算法的快速性和正确性，对图5所示大小为512×512的Lena图像先进行特征点提取，然后分别进行平移和旋转变化，采用本文算法和传统的SURF算法进行特征匹配，计算出实际的平移量和旋转量，并与理论值相比较。

图5　Lena图Fig.5　Lena figure

1) 分别用FAST角点检测算法和SURF特征检测算法对图5进行特征点提取，如图6所示，并统计出特征点的个数和检测时间，如表1所示。对比可知，FAST算法相对于SURF算法检测出的特征点数量多，而且运行时间较短，该算法提取的特征点进一步突出了图像的细节，从而使匹配准确率得到了提高。

图6　特征点检测结果Fig.6　Results of feature point detection

表1　特征点检测时间比较

2) 将图5所示的图像作为参考图像，分别对其进行平移和旋转变化，得到待配准图像，然后采用本文提出的算法进行特征点匹配，如图7和图8所示，计算其平移量和旋转量，并与理论值做比较，结果如表2所示。

图7　平移变换匹配结果Fig.7　Translational transformation matching results

图8　旋转变换匹配结果Fig.8　Rotation transformation matching results

表2　图像配准试验数据

由图7和图8的匹配效果可以看出，本文算法对平移、旋转变换具有良好的匹配效果。由表2可知，平移参数的最大误差为0.022个像素，旋转参数的最大误差为0.045°。

为了进一步评价匹配结果，将本文的算法与传统的SURF算法在匹配正确率和所用时间上进行比较，结果如表3所示。

由表3可看出，本文算法相比SURF算法在精确度和速度方面得到了很好的提升。这主要是由于FAST角点检测器的优良特性和SURF特征描述符的抗旋转性，不仅使计算复杂度降低，速度加快，而且对旋转变化具有一定不变性。

3　结　语

本文根据图像匹配技术精度高、速度快的要求，提出了结合FAST-SURF和改进k-d树最近邻查找的图像配准算法。该算法利用了FAST角点的快速性、稳定性以及SURF描述子的抗旋转性的优点，采用改进的k-d树BBF算法查找特征点，并对得到的特征点对进一步实现双向匹配，得到初匹配点对，为了实现更精确的匹配，使用RANSAC算法消除误匹配点。实验结果表明，平移参数的最大误差为0.022个像素，旋转参数的最大误差为0.045°，本算法实现了较高的匹配速度和精度。

[1]朱琳，王莹，刘淑云，等. 基于改进快速鲁棒特征的图像快速拼接算法[J]. 计算机应用，2014，34(10)：2944-2947.

ZHU Lin, WANG Ying, LIU Shuyun, et al. Fast image stitching algorithm based on improved speed up robust feature[J]. Journal of Computer Applications, 2014, 34(10):2944-2947.

[2]SCHMID C, MOHR R, BAUCKHAGE C. Evaluation of interest point detector[J]. International Journal of Computer Vision, 2000, 37(2):151-172.

[3]SMITH S M, BRADY J M. SUSAN -A new approach to low level image processing[J]. International Journal of Computer Vision, 1997, 23(1):45-78.

[4]HARRIS C G, STEPHENS M J. A combined corner and edge detector[C]//Proceeding of 4th Alvey Vision Conference, 1988:147-151.

[5]张静，桑红石. 基于初始尺度变换的SIFT匹配算法[J].红外与毫米波学报，2014，33(2)：177-182.

ZHANG Jing, SANG Hongshi. SIFT matching method based on base scale transformation[J]. Journal of Infrared and Millimeter Waves,2014,33(2):177-182.

[6]刘志文，刘定生，刘鹏. 应用尺度不变特征变换的多源遥感影像特征点匹配[J]. 光学精密工程，2013，21(8)：2146-2153.

LIU Zhiwen, LIU Dingsheng, LIU Peng. SIFT feature matching algorithm of multi-source remote image[J]. Optics and Precision Engineering, 2013, 21(8): 2146-2153.

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

[8]BAY H, TUYTELAARS T, VAN GOOL L. SURF: Speeded up robust features[C]//9th European Conference on Computer Vision, Graz, Austria, 2006: 404-417.

[9]ROSTEN E, DRUMMOND T. Machine learning for high-speed corner detection[C]//9th European Conference on Computer Vision, Graz, Austria, 2006: 430-443.

[10] 杜杰，刘亚秋，孙垚. 基于仿射不变闭合区域和SURF的图像匹配算法[J]. 计算机应用研究，2014，31(1)：295-298.

DU Jie, LIU Yaqiu, SUN Yao. Image matching algorithm based on affine-invariant closed region and SURF[J]. Application Research of Computers,2014,31(1):295-298.

[11]尧思远，王晓明，左帅. 基于SURF的特征点快速匹配算法[J]. 激光与红外,2014,44(3):347-350.

YAO Siyuan, WANG Xiaoming, ZUO Shuai. Fast feature point matching algorithm based on SURF[J]. Laser & Infrared, 2014, 44(3):347-350.

[12]罗天健，刘秉瀚. 融合特征的快速SURF配准算法[J].中国图象图形学报，2015，20(1)：95-103.

LUO Tianjian, LIU Binghan. Fast SURF key-points image registration algorithm by fusion feature[J]. Journal of Image and Graphics,2015,20(1):95-103.

[13]BRADSKI G.Learning OpenCV[M].南京：东南大学出版社，2009：20.

(责任编辑王绪迪,王卫勋)

Image matching algorithm combining FAST-SURF and improved k-d tree nearest neighbor search

CHEN Jianhong， HAN Xiaozhen

(School of Mechanical and Precision Instrument Engineering，Xi’an University of Technology，Xi’an 710048,China)

An algorithm combining FAST-SURF and improved k-d tree nearest neighbor search is proposed to solve the matching problem of translation and rotation changes between two images. Feature points are first extracted using FAST (Features from Accelerated Segment Test) corner detector, and then SURF (Speeded Up Robust Feature) descriptors are generated based on the feature points around the neighborhood information. And an improved k-d tree nearest neighbor search algorithm BBF (Best Bin First) is adopted to find out the feature highlights of two nearest neighbor points. The preliminary match point is obtained by bidirectional matching, and finally RANSAC (Random Sample Consensus) algorithm is adopted to eliminate false matching points, with findHomography function used to find transformation matrix to calculate the relative amount of translation and rotation of the two images. Experimental results are superior to traditional SURF image matching algorithm with the maximum error of the algorithmic translation parameter being 0.022 pixels, and the maximum error of rotation parameters is 0.045 degree, thus achieving a fast and accurate precision of the image registration.

images matching; FAST-SURF algorithm; BBF; bidirectional matching; RANSAC

1006-4710(2016)02-0213-05

10.19322/j.cnki.issn.1006-4710.2016.02.014

2015-08-14

陕西省自然科学基础研究计划资助项目(2012JM8006)；陕西省教育厅科研计划资助项目(2013JK1049)

陈剑虹，男，副教授，博士，研究方向为光电检测与光谱分析。E-mail: chenjianhong@xaut.edu.cn

TP391.4

A