基于FAST角点检测的图像配准算法

吴金津，王鹏程，龙永新，廖飞

（湖南工业大学计算机与通信学院，湖南株洲412007）

基于FAST角点检测的图像配准算法

吴金津，王鹏程，龙永新，廖飞

（湖南工业大学计算机与通信学院，湖南株洲412007）

提出了一种具有类SIFT描述特征的FAST角点检测的图像配准算法。先利用FAST对图像进行特征点提取；然后，采用圆环结构算子对提取出的特征点进行类SIFT的特征描述；最后，通过K-D算法将提取出来的特征点进行粗匹配，并使用视差梯度进行预筛选，使用RANSAC算法提纯，从而实现特征点匹配。试验结果表明，与SIFT算法和改进的SIFT算法相比，本算法减少了误匹配的数目，提高了匹配的精确性和稳定性。

FAST角点；K-D算法；RANSAC算法

0 引言

图像拼接主要包括图像配准与融合，其中最关键的是图像配准。目前图像配准的方法有很多，常见的是基于特征提取的图像配准方法[1]。角点是图像中一个重要的局部特征。在图像的各种特征中，角点具有旋转不变性和不随光照条件变化而变化的特点，还能减少参与计算的数据量的同时，又不损失图像的重要灰度信息。因此， 角点特征能用于图像匹配、目标跟踪以及运动估计、目标描述和识别等领域。

E. Rosten和T. Drummond提出了一种既简单又快速的FAST角点探测算法[2]，对待匹配的2幅图像进行FAST角点的提取。该算法不仅能降低特征点检测的时间，还可迅速地排除大量的非特征点。2004年David G. Lowe提出的尺度不变特征变换（scale invari-ant feature transform，SIFT）算法[3]具有尺度旋转、亮度变化、缩放的不变性，且SIFT角点能适应图像的尺度变化，但其不足在于对特征点的要求过于苛刻，在信息较少的图像中，特征点的数量较少，参数拟合的误差非常大。张春美等人[4]提出改进的SIFT算法，用基于同心圆形窗口的64维向量代替传统SIFT算法的128维。该算法的思想是通过增强特征描述符本身的抗旋转能力和减少特征描述符的维数来降低计算的复杂度，加快了匹配速度。2012年，芮挺等人[5]改进SIFT对特征点的描述方法，用8个同心圆，在每个圆形的区域内选取10个方向，生成70维向量代替原始SIFT算法中的128维。

针对传统的SIFT特征匹配算法将时间耗费在特征点检测以及特征点描述上的缺点，本文提出了具有类SIFT描述特征的FAST角点检测的图像配准算法。特征点描述阶段，利用圆环算子进行特征点的描述，由于圆具有旋转性不变性，增强了特征描述符的抗旋转能力，降低了其维数，最终降低了计算复杂度；特征点匹配阶段，先利用K-D树进行粗匹配，再用视差梯度进行精确配准，消除了大量的误匹配，最后使用RANSAC提纯[6]。本文采用具有类SIFT 描述方式的FAST角点检测算法进行图像配准，融合了FAST与SIFT算法各自的优点，试验证明了本算法具有良好的配准效果。

1 算法介绍

图像匹配的核心问题是将同一目标在不同时间、不同分辨率、不同光照、不同位置情况下所成的像相对应[7]。传统的匹配算法往往首先直接提取角点或边缘，对环境的适应能力较差。针对以上问题，本文提出了一种鲁棒性强，能适应不同光照、不同位置等情况的图像配准方法，即基于FAST角点检测的图像配准方法。

1.1 特征提取

图像配准包括特征提取、特征匹配、转换模型参数估计、图像重采样4个步骤。其中，特征提取是图像配准中最基础的一个环节。图像的特征点是指那些十分突出并且不会受光照条件的改变而消失的点，比如角点、边缘点、暗区域的亮点以及亮区域的暗点[8]。FAST角点检测算法不仅简单，而且速度快。该算法是指在图像中选定一个像素点，并以此像素点为中心构建一个圆形区域，将中心像素点的灰度值与圆周中每个像素点的灰度值进行比较，若有足够多的灰度差值的绝对值小于阈值，则可认为此中心像素点是角点。图1是以像素点p为中心的圆形区域的模板情况，圆形区域是一个以3像素为半径的离散化区域。

图1 圆形模板示意图Fig.1Schematic diagram of circular template

首先定义一个角点响应函数来判断像素点是否为角点，角点响应函数（corner response function，CRF）[6]为

式中：circle(p)为以p为中心的圆周上的点集合；

I(x)为圆周上任意一点的图像灰度值；

I(p)为中心像素点p（候选点）的图像灰度值；

像素点p是否为角点取决于圆周上的16个像素点满足式（1）的像素点个数N，如果N大于给定的一个阈值，就可以确定该候选点为角点。通常FAST角点阈值设置为12。

本文对传统FAST算法进行优化。该算法可以迅速排除大量的非特征点，其具体步骤如下：

Step1选择图像上的任意一点p，并以此为中心构建一个半径为3的圆形区域，将圆周上的像素点按顺时针顺序依次编号1～16。

Step2分别计算中心像素点p与圆周上的像素1和像素9的图像灰度差值。若它们的绝对值都大于阈值d，则p为非特征点；若它们的绝对值至少有一个小于阈值d，则执行Step3。

Step3分别计算中心像素点p与圆周上的像素3和像素11的图像灰度差值。若它们的绝对值至少有一个大于阈值d，则p为非特征点；若它们的绝对值都小于阈值d，则像素点p为候选特征点，执行Step4。

Step4分别计算中心像素点p与圆周上其余的12个像素点的图像灰度差值。若至少有4个像素点不满足公式（1），则像素点p为非特征点；若至少有8个像素点满足公式（1），则像素点p为特征点。经过优化之后，该算法只需要平均检测候选特征点周围的8个点就能判断是否为角点。

Step5判断图像的其他像素点是否为角点，重复Step1～Step4。

该算法可以快速地排除整幅图像中的很多像素点，提高了特征点检测的时间。

1.2 类SIFT特征点描述

对检测到的FAST角点采用圆环结构算子进行类SIFT特征描述。为了保证特征向量的旋转不变性，传统的SIFT算法会对SIFT特征描述进行主方向的分配，而本算法采用圆环结构算子进行类SIFT特征描述，因此其不需要进行主方向的分配。由于圆本身具有旋转不变性，因此，在图像旋转之后，特征点周围的部分都不会发生任何改变。

SIFT特征描述符是一种以特征点周围像素的方向信息和梯度为特征的描述符。具有类SIFT描述特征的算法对描述符的复杂度、维数和抗旋转能力进行了改进，以特征点为中心，采用圆环算子对特征点进行描述。对于图像在每一尺度空间下的像素点(x, y)，其方向信息H和梯度M如式（2）～（3）所示。

构建特征点描述的具体步骤如下：

Step1以特征点为中心、半径为1，生成第1个圆形区域，半径依次增大1，总共生成8个同心圆，如图2所示。

图2 关键点邻域梯度信息生成特征向量的过程Fig.2The process of the key point neighborhood gradient information to generate a feature vector

Stpe2利用式（2）和（3）计算每个圆环内各个像素10 个方向的方向信息和梯度模。

Step3分别统计第1个圆环和第2个圆环区域内10 个方向的梯度累加值，按角度排序后作为第 1 到第 10 个元素；然后在第2个圆环和第3个圆环区域内统计 10 个方向的梯度累加值，按角度排序后作为第 11 到第 20 个元素。在第3个圆环和第4个圆环区域内统计 10 个方向的梯度累加值，按角度排序后作为第 21 到第 30 个元素。依次下去直到在第7个圆环和第8个圆环区域内统计 10 个方向的梯度累加值，按角度排序作为第 61 到第 70 个元素，共生成7×10个元素。该一维向量就定义为关键点的特征描述符。

Step4将特征描述符向量进行归一化处理，减少光照变化对特征点的影响。

1.3 特征匹配

由于传统的RANSAC算法存在效率不高的问题，当需要匹配的两幅图像误匹配点的数目比较大时，其算法的效率也非常低。为了降低误匹配的概率和提高RANSAC算法的效率，本文先利用K-D树粗匹配特征点对，再采用视差梯度初选匹配特征点对，然后使用RANSAC算法对预筛选出的特征点对进行精确提纯，进而得到匹配的特征点对。

1.3.1 K-D树粗匹配特征点对

为了能够快速地提取匹配特征点，本文采用K维二叉搜索树（K-dimensional binary search trees， K-D树）算法[9]获取匹配点，对状态空间中的所有特征描述符向量进行分类整理，为图像中所有特征点建立了一个索引树。定义目标图像的特征点与待匹配的特征点之间距离最小与次最小之间的比值作为特征点匹配的相似性度量。假定NN表示目标图像的特征点与待匹配的特征点之间距离最小值，SCN表示2个匹配点之间的距离为次最小值。通过式（4）和式（5）来判断关键点是否为匹配的特征点对，

式中，t为设定的阈值，依据经验，本文取[0.6, 0.7]，如果d小于等于t，则匹配点对是较好的匹配。

1.3.2 视差梯度预筛选特征点对

根据视差梯度的定义[10]，用m，n分别表示原始图像中的2个相邻的特征点，m′，n′表示目标图像中相应的匹配特征点。若原始图像相邻的特征点与目标图像的特征点匹配，则视差梯度Gd应小于2；如果视差梯度大于2，则表示原始图像的特征点和目标图像的特征点不匹配。视差梯度的公式为

式中：（m′, m）和（n′, n）是对应特征点的图像坐标向量；

运用RANSAC算法对这些预筛选出的特征点匹配对提纯，以得到误匹配率几乎为0的特征点匹配对；利用特征点匹配对计算变换矩阵，最后利用LM（levenberg-marquardt）[11]算法进行优化，完成特征匹配。

2 算法流程

本文的算法流程如图3所示。算法主要由FAST角点检测、类SIFT特征点描述、特征匹配、变换参数估计和图像配准几个部分组成。

图3 算法流程图Fig.3Flow chart of the algorithm

算法实现步骤如下：

1）检测2幅待匹配图像的FAST角点。在图像中，选定任意一个像素点并且以此像素点为中心构建圆区域，将中心像素点的灰度值与圆周中任意像素点的灰度值相比较，若圆周中有足够多的像素点的灰度值大于或者小于中心像素点的灰度值，则被选为角点。

2）特征点的描述。采用圆环算子对FAST角点进行类SIFT描述，以特征点为中心，统计10个方向的梯度值累加，按照角度排序之后作为第1到第10个元素，总共有8个同心圆，则圆环之间的区域有7个，则可生成70维的特征描述符，2幅图像根据特征点的数量生成相应的特征向量。

3）匹配点对提纯。采用K-D算法粗略得到图像匹配对，然后利用视差梯度初次提纯，消除大量的误匹配点对，最后使用RANSAC算法精确提纯。

4）根据匹配结果，采用LM算法进行优化，求出变换参数，完成图像配准。

3 试验结果及分析

本文试验图像大小为320×240像素。试验平台的操作系统为WIN 7， CPU为AMD Athlon(tm) Dual-Core CPU T4400 @ 2.20 GHz，内存为2 G。编程环境为Microsoft Visual C++ 6.0和Open CV。本文比较了SIFT算法、改进的SIFT算法和本文算法3种算法的图像配准效果。

2幅待匹配的原始图像如图4所示。

图4 原始图像Fig.4Original image

1）分别利用SIFT算法、改进的SIFT算法和本算法对2幅待匹配图像进行提取特征点，如图5所示。

由图5可知，本文算法提取的特征点比改进的SIFT算法的特征点数量少，从而减少了待匹配特征点的数目，缩短了特征描述的时间，并且减少了特征匹配的时间。

2）特征匹配。SIFT算法和改进的SIFT算法需建立高斯金字塔，并对高斯差分图像进行泰勒展开，浪费了大量的时间。而本文算法用FAST对图像进行角点提取，计算简单，算法时间效率更高，且生成的特征点显著。SIFT算法、改进的SIFT算法和本文算法（通过视差梯度进行初次筛选）3种算法的图像匹配效果如图6所示。

图6 特征匹配Fig.6Feature matching

由图6可知，平行的连线为正确的匹配对，交叉的连线为误匹配对，SIFT算法得到的误匹配对较多，改进的SIFT算法得到的误匹配对明显减少，而本文算法得到的误匹配点很少。

将SIFT算法、改进的SIFT算法和本文算法在特征点提取和特征点匹配的性能上进行对比和分析。部分试验结果（5幅图像的结果）如表1所示。

表1 部分试验结果Table 1Some expreimental results

由表1可知，与SIFT算法和改进的SIFT算法相比，本文算法一方面在特征点检测阶段所用的时间有所减少；另一方面，在特征点匹配阶段的误匹配点数更少，且算法的复杂度也有所降低。

4 结语

本文利用FAST角点检测的优势和圆的旋转不变性特点，在特征点提取阶段，使用FAST进行特征点提取，在SIFT特征描述符阶段，通过圆的旋转不变性来构造特征描述符，使其自身具有旋转不变性，降低了算法的复杂度，并减少了匹配时间。算法的不足之处是匹配点对的数目较少，不能用于实时的图像拼接。

[1]廖飞，叶玮琼，王鹏程，等. 基于SIFT特征匹配的图像拼接算法[J]. 湖南工业大学学报，2014，28(2)：71-75. Liao Fei，Ye Weiqiong，Wang Pengcheng，et al. Image Mosaic Algorithm Based on SIFT Feature Matching[J]. Journal of Hunan University of Technology，2014，28(2)：71-75.

[2]燕鹏，安如. 基于FAST改进的快速角点探测算法[J]. 红外与激光工程，2009，38(6)：1104-1108. Yan Peng，An Ru. Improved Fast Corner Detection Algorithm Based on FAST[J]. Infrared and Laser Engineering，2009，38 (6)：1104-1108.

[3]Deng Rongfeng，Li Xiying. Robust Image Mosaic Algorithm Based on SIFT Feature Matching[J]. Journal of Computer Applications，2009 (S1)：219-221.

[4]张春美，龚志辉，孙雷. 改进SIFT特征在图像匹配中的应用[J]. 计算机工程与应用，2008，44(2)：95-97. Zhang Chunmei，Gong Zhihui，Sun Lei. Improved SIFT Feature in Image Matching[J]. Computer Engineering and Applications，2008，44 (2) ：95-97.

[5]芮挺，奡张升，周游，等. 具有SIFT描述的Harris角点多源图像配准[J]. 光电工程，2012，39(8)：26-31. Rui Ting，Zhang Sheng’ao，Zhou You，et al. Registration of Multi-Sensor Image Based on Harris Corner with SIFT Description[J]. Opto-Electronic Engineering，2012，39 (8)：26-31.

[6]Chen Fuxing，Wang Runsheng. Fast RANSAC with Preview Model Parameters Evaluation[J].Journal of Software，2005，16(8)：1431-1437.

[7]周军太，龙永红. 一种改进SURF算法的图像配准[J]. 湖南工业大学学报，2011，25(2)：95-99. Zhou Juntai，Long Yonghong. Image Matching Based on Improved Speed-Up Robust Features[J]. Journal of Hunan University of Technology，2011，25(2)：95-99.

[8]武岫缘，龙永新，高总总. 基于SIFT-ACO的图像拼接算法[J]. 湖南工业大学学报，2014，28(1)：76-80. Wu Xiuyuan，Long Yongxin，Gao Zongzong. Image Mosaic Optimization Algorithm Based on SIFT-ACO[J]. Journal of Hunan University of Technology，2014，28(1)：76-80.

[9]Bentley J L. Multidimensional Binary Search Trees Used for Associative Searching[J]. Communications of the ACM，1975，18(9)：509-517.

[10]马颂德，张正友. 计算机视觉[M]. 北京：北京科学出版社，1988：82-83. Ma Songde，Zhang Zhengyou. Computer Vision[M]. Beijing：Beijing Science and Technology Press，1988：82-83.

[11]Szeliski R，Shun Heungyeung. Creating Full View Panoramic Image Mosaics and Environment Maps[C]//SIGGRAPH′97 Proceedings of Computer Graphics. Los Angeles：ACM Press，1997：251-258.

（责任编辑：邓彬）

Image Registration Algorithm Based on Fast Corner Detection

Wu Jinjin，Wang Pengcheng，Long Yongxin，Liao Fei
（School of Computer and Communication，Hunan University of Technology，Zhuzhou Hunan 412007，China）

Proposes an image registration algorithm of FAST corner detection with the description of the characteristics of SIFT. First applies FAST to extract image feature points, then uses the ring structure operator for SIFT description of the feature points, finally conducts coarse matching of the points by means of K-D algorithm, and pre screening through disparity gradient and purification with RANSAC algorithm achieves feature points matching. The experimental results show that compared with SIFT algorithm, the improved SIFT algorithm reduces the number of false matches and improves the accuracy and stability of matching.

FAST corner； K-D algorithm； RANSAC algorithm

TP751

A

1673-9833(2014)04-0071-05

10.3969/j.issn.1673-9833.2014.04.016

2014-03-28

国家自然科学基金资助项目（61170102），湖南省教育厅科学研究基金资助项目（12A039），湖南省自然科学基金资助项目（11JJ3070），湖南省科技发展基金资助项目（2011GK3145）

吴金津（1988-），女，湖南益阳人，湖南工业大学硕士生，主要研究方向为数字图像处理，E-mail ：514959975@qq.com