基于FAST特征点提取的图像拼接算法

高　晶，陈　莉，兰小艳，靳立燕，杨　洲

(西北大学 信息科学与技术学院，陕西 西安　710127)



·信息科学·

基于FAST特征点提取的图像拼接算法

高晶，陈莉，兰小艳，靳立燕，杨洲

(西北大学 信息科学与技术学院，陕西 西安710127)

针对SIFT图像拼接算法在特征点提取阶段，采用基于差分高斯金字塔的方式导致的算法运行时间较长，且易造成特征点漏检、位置偏移的问题,提出一种基于FAST特征点提取的图像拼接算法。该算法首先对拼接图像进行基于FAST算法的特征点提取，取代原有SIFT算法中特征点提取方式,然后对提取特征点进行描述和向量匹配,利用欧氏距离和RANSAC算法实现配准,最后通过加权平均融合算法完成图像拼接。仿真实验表明,该算法加快了特征点的提取速度，提高了定位准确性,更有利于得到灰度整体和谐的拼接图像。

FAST；特征点；SIFT；图像拼接

图像拼接是指通过图像间的重叠部分找出图像间对应的几何坐标变换模型,将多幅图像无缝拼接成一幅具有高分辨率、宽视角的大图。特征点具有可以较好表征原有图像且不随图像变换而改变的优势，因而基于特征点的图像拼接算法得到了广泛应用[1]。

常见的基于特征点的图像拼接算法主要包括：基于SUSAN的图像拼接算法[2]、基于Harris的图像拼接算法[3]、基于尺度变换不变特征提取(Scale invariant feature transform,SIFT)算法[4]等。SIFT算法作为经典的图像拼接算法,是目前使用比较广泛的图像拼接算法之一,但该算法过于依赖局部像素的梯度方向，且图像层层金字塔差分构造易造成特征点定位偏差的问题,同时耗时较长[5],无法高效完成图像拼接任务。对此,很多学者对SIFT算法做了相应的改进,文献[6]将PCA和SIFT算法相结合来减少运行时间,但当图像出现尺度变换或旋转变化时,拼接效果不甚理想;文献[7]提出的SUFT算法，通过使用积分图像求导的方法加快拼接速度,但该算法抗噪能力较差，且在图像发生尺度变换情况下拼接效果并不理想。现有改进算法无法在较好保证图像拼接效果的前提下加快算法的运行速率[8]。

基于SIFT的图像拼接算法在特征点提取阶段采用高斯金字塔差分取极值的方式，运行时间较长，本文为兼顾拼接效果与效率,采用FAST角点算法对其进行改进。FAST角点提取算法[9]作为SUSAN角点提取算法的改进,保留了SUSAN算法可以检测出各类特征点的特性[10]，而且快速准确[11]。本文利用FAST算法在特征提取时具有的独特优势,将该算法用于SIFT算法的特征提取阶段，提出了一种新的基于FAST特征点提取的图像拼接算法。该算法不仅能得到良好的图像拼接效果,而且能加快图像拼接速度。

1　SIFT图像拼接算法

SIFT图像拼接算法主要分为4个阶段:特征点提取、特征点描述、特征点匹配和图像融合。特征点提取采用基于高斯差分金字塔的方法获取。

1.1尺度空间极值检测

一幅二维图像在不同尺度下的尺度空间表示可以由图像和高斯核卷积得到

L(x,y,δ)=G(x,y,δ)*I(x,y)。

(1)

其中,(x,y)是图像点的像素坐标,δ是尺度空间因子,I(x,y)为原图像，G(x,y,δ)为高斯核函数,

(2)

SIFT算法在实际应用中使用差分高斯(DifferenceofGaussian,DoG)算子来建立尺度空间。它是归一化LoG(LaplacianofGaussian,LoG)算子的近似。DoG定义如下

D(x,y,δ)=

(G(x,y,kδ)-G(x,y,δ))*I(x,y)。

(3)

其中,D(x,y,δ)的构造需要建立高斯金字塔与DoG两个金字塔,而高斯金字塔分为多组,每组间又分为多层。尺度因子因组和层的不同而不同,同时为了获取DoG极值,需要生成δ·(S+3)的平滑图像(S代表尺度数)。

1.2尺度空间极值点判定

DoG局部极值的检测依据构造的金字塔。金字塔每层的每个像素需要和同一尺度的周围邻域8个像素和上下相邻尺度对应位置的邻域9个像素，一共26个像素进行比较,如果当前像素比周围26个像素都大或者都小时就认为该点属于极值点。

经上述两步所得极值点即为特征点。由此可见,SIFT图像拼接算法在特征点提取时,采用分组分层并遍历的方式提取特征点,造成被描述的特征点数成倍增多,特征点提取时间增加的同时加大了拼接算法的耗时。同时SIFT方法虽然能够从尺度空间寻找出具有结构化特性的特征点，但忽略了实际图像中很多具有视觉意义的特征位置,造成特征点漏检的情况。对图像进行高阶导数运算,也会出现噪声放大、像素位置偏移的问题[12]。因此,本文用FAST特征提取算法取代基于高斯差分金字塔的特征提取方法,实现SIFT图像拼接算法的改进，提高算法运行效率。

2　基于FAST的图像拼接算法

2.1FAST特征点检测算法

FAST 算法是一种对待检测点邻域范围内角点分布进行分段检测的特征检测方法[13]，其周围邻域如图1所示。

图1　FAST检测领域示意图Fig.1　Schematic diagram of FAST detection field

图中的每个小方格代表一个像素,中心的m点是待检测的点,检测点的邻域半径是3个像素值,圆周的像素用1～16顺时针标注。以图中检测m点是否为特征点为例说明该算法思想。首先将圆周上的1～16个像素点分为如下3类:

(4)

式中Im代表m点的像素值,Im→i代表圆周上第i个像素点,n是一个参数。得到的结果Sm→i有3种取值:d代表比检测点暗,s代表与检测点相似,b代表比检测点亮。实际检测时,为了提高速度,一般先检测圆周上的第1和9两个像素点,如果Sm→1=s和Sm→9=s同时发生,则不把该点选择为候选点。否则继续检测Sm→5和Sm→13,若以上4个值中有3个值都是d或者b,则该点将作为候选点,继续计算其余点的Sm→i值，如果检测的16个点的Sm→i值中有p个连续的值为d或者b,则该点被确定为特征点。

其中,参数n的选择会影响检测到的特征点的数量,通过文献及已有实验[14]可知，n取值为30，p取值为9时，可以较好地保留特征点，剔除伪特征点。

图2是SIFT特征检测算法和FAST算法针对某一几何图形的特征检测结果。由图2可以看到，SIFT算法提取出的特征点位置发生了一定程度的偏移,同时出现漏检的情况,这是由于高斯平滑的过程中极值点会随着像素扩散引起的,图像上曲率变化大的点以及角点往往是进行图像匹配比较理想的特征点,但该方法遗漏了某些重要的特征信息,不利于后续特征点匹配以及拼接图像的形成。而FAST算法检测的特征点,误检测点数少,且数量稳定,可一次性检测出角点、交点、边缘点等各类特征点。

图2　SIFT算法与FAST算法特征点提取对比图Fig.2　Feature points extraction comparison chart of SIFT and FAST algorithm

经实验测试，对同一幅图像使用基于SIFT的特征检测算法耗时2.021s,而使用FAST算法检测特征点耗时0.453s,可知FAST算法提取特征点所用时间远小于基于SIFT的特征检测算法。其原因在于,SIFT算法需遍历考察一幅图像经高斯算法处理后的不同组不同层间的像素对比值,且其运行时间复杂度会随着图像像素的增加而增加,而FAST算法只需比较该幅图像自身像素间的对比值,因而其时间复杂度远小于SIFT算法。

综上可知,FAST算法提取特征点具有快速且准确的特性,本文充分利用这一优势,提出一种新的基于FAST特征点检测的图像拼接算法,在保证图像拼接效果的同时加快拼接速度。

2.2算法

SIFT图像拼接算法在特征点提取阶段耗时长，且易出现特征点漏检的问题,本文采用FAST算法进行特征点检测,再将提取出的特征点进行描述,最终完成图像拼接。算法流程图如图3所示。

算法主要步骤如下:

1)图像获取。采用定点旋转或沿垂直于照相机光轴的方向移动拍摄，获取源图像I1和I2。

2)提取特征点。对源图像I1和I2经向量变化得到相应的向量矩阵,对图像矩阵采用FAST算法提取特征点,得到对应特征点坐标,其中参数n取值为30,p取值9,通过使用角点提取的方式提高特征点定位精度，并加快特征点的提取速度。

3)选取特征点主方向。计算检测出的每个特征点的梯度模值和方向。以关键点所在位置为中心，在半径为4的邻域窗口内采样,以此增加邻域点对关键点的影响,然后用直方图统计邻域像素的梯度方向,选取直方图的主峰值作为关键点的主方向,80%主峰值的局部峰值作为该点的辅助方向。

4)生成特征向量。利用直方图统计8×8小块上8个方向的梯度方向直方图,绘制每个方向的累加值,形成4个种子点,每个关键点就形成2×2×8=32维的描述子。对向量进行归一化处理,进一步去除光照影响,增加匹配的稳健性。

5)特征匹配。本文采用两个向量的欧氏距离作为相似性的判断度量。为了提高图像匹配精度，采用RANSAC算法对变换矩阵进行求解与精炼。

6)图像融合。本文采用简单快速的加权平滑算法[15]处理拼缝问题。

7)输出拼接图像。即输出经过特征提取、特征匹配和融合的拼接图像。

图3　本文算法流程图Fig.3　The flow chart of this algorithm

3　实验结果及分析

本算法在Core 2,2.66 GHz CPU,2.0 GB RAM的PC机上,Matlab R2010a 环境下实现。为了验证本文算法的有效性,将本文算法与基于SIFT的拼接算法以及SIFT算法的改进算法——PCA-SIFT算法及SUFT算法进行比较。使用两组图像对算法进行检验,其中图像组1为标准灰度Lena图像，图像组2为景物灰度图像,如图4所示。

图4　原始图像组Fig.4　The original image groups

对两组图像分别进行特征点的提取和匹配,以图像组2为例,特征点提取如图5所示,特征点匹配如图6所示。

图5　图像组2特征点提取对比图Fig.5　Image feature point extraction contrast figure of group 2

图6　图像组2特征点匹配对比图Fig.6　Image feature point matching contrast figure of group 2

对两组图像使用4种拼接算法实验结果如图7,图8所示。

图7　图像组1拼接结果对比图Fig.7　Mosaic results contrast figure of group 1

图8　图像组2拼接结果对比图Fig.8　Mosaic results contrast figure of group 2

图9　图像组1右侧图像旋转后待拼接图像组Fig.9　Mosaic image group after rotation for the image on the right side of group 1

为了进一步验证本文算法的有效性,对图像组1右侧图像进行任意角度的旋转，如图9所示，然后进行拼接实验，拼接结果如图10所示。

为了验证算法的鲁棒性,给两组图像添加密度为0.02的椒盐噪声,并与其他3种拼接算法比较,图像组1拼接结果如图11所示,图像组2拼接结果如图12所示。

图10　图像组1右侧图像旋转后拼接结果对比图Fig.10　Contrast figure of mosaic results after rotation for the image on the right side of group 1

图11　图像组1添加椒盐噪声后拼接结果对比图Fig.11　Contrast figure of mosaic results after add salt and pepper noise to group 1

图12　图像组2添加椒盐噪声后拼接结果对比图Fig.12　Contrast figure of mosaic results after add salt and pepper noise to group 2

分别统计原始图像组采用SIFT拼接算法、PCA-SIFT算法、SUFT拼接算法以及本文算法进行拼接所对应的特征点数、匹配点对数和算法运行时间,结果分别如表1(“/”符号前为左侧图像提取特征点数,符号后为右侧图像提取特征点数)、表2和表3所示。

表1　4种算法特征点提取个数对比结果

表2　4种算法特征点匹配个数对比结果

表3　4种算法运行时间对比结果

从直观效果来看,由图5圈内标注的特征点提取情况可知,SIFT算法提取特征点位置存在一定偏移，但本文算法提取特征点定位准确且数目较多。由图6匹配对比图可以看出,本文算法的匹配情况优于原有SIFT算法,误匹配对数较少。由图7和图8两组图像的拼接结果对比图可以得出,本文算法拼接结果与SIFT算法相近,PCA-SIFT拼接算法拼缝处过渡不光滑,SUFT拼接算法拼缝处有细微裂痕。由图10旋转后的拼接结果可知,其他3种算法出现不同程度的拼缝，但本文算法拼接效果良好,可以完整显示拼接图像。由图11和12噪声影响下的拼接结果可以看出，SUFT算法拼接图像受噪声干扰明显,PCA-SIFT算法拼接图出现一定拼缝,而本文算法仍可以较好地实现拼接,证明其对噪声具有一定鲁棒性。

从定量角度分析,由表1、表2和表3可得,本文算法提取的特征点数及匹配对数多于其他3种拼接算法,但运行时间均小于其他3种算法,即本文算法在更短的时间内取得了较好的拼接效果。

4　结　论

本文算法采用FAST特征点提取融合SIFT特征点描述的方式,改进原有SIFT图像拼接算法。仿真实验表明，该算法相较原有算法减少了拼接运行时间,增加了准确定位特征点数,提高了匹配准确率，有利于拼接图像的快速生成，适应于实时性要求较高的场景。

[1]袁杰. 基于 SIFT 的图像配准与拼接技术研究[D]. 南京: 南京理工大学, 2013.

[3]HARRIS C, STEPHENS M. A combined corner and edge detector [C]∥Alvey vision conference, The University of Manchester,1988,15:147-151.

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

[5]苏丽颖, 李小鹏, 么立双. 一种改进的SIFT特征提取新算法[J]. 华中科技大学学报(自然科学版), 2013, 41(1):396-398.

[6]KE Y, SUKTHANKAR R. PCA-SIFT: A more distinctive representation for local image descriptors[J]. Computer Vision and Pattern Recognition, 2004, 2:506-513.

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

[8]杨恒, 王庆. 一种新的局部不变特征检测和描述算法[J]. 计算机学报, 2010, 33(5): 935-944.

[9]ROSTEN E, DRUMMOND T. Fusing points and lines for high performance tracking[C]∥Tenth IEEE International Conference on Computer Vision. IEEE, 2005, 2: 1508-1515.

[10] 孙波. 数字图像角点检测算法的研究[D]. 合肥:合肥工业大学, 2013.

[11] 梁艳菊,李庆,陈大鹏,等.一种快速鲁棒的LOG-FAST角点算法[J].计算机科学，2012，39(6)：251-254.

[12] MA Y, REN Z. Image mosaic method based on improved SIFT feature detection algorithm[C]∥Proceedings of the 9th International Symposium on Linear Drives for Industry Applications, Springer Berlin Heidelberg, 2014: 771-779.

[13] ALDANA-MURILLO N G, HAYET J B, BECERRA H M. Evaluation of Local Descriptors for Vision-Based Localization of Humanoid Robots[M]//Pattern Recognition.Berlin:Springer International Publishing, 2015: 179-189.

[14] ROSTEN E,DRUMMOND T. Faster and better: a machine learning approach to corner detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(1):105-119.

[15] ZHANG Y, CHEN L,ZHAO Z,et al.Multi-focus image fusion with sparse feature based pulse coupled neural network[J].TELKOMNIKA (Telecommunication Computing Electronics and Control),2014,12(2):357-366.

(编辑李静)

Image mosaic algorithm based on the FAST feature points extraction

GAO Jing, CHEN Li, LAN Xiao-yan, JIN Li-yan, YANG Zhou

(School of Information Science and Technology, Northwest University, Xi′an 710127， China)

Aiming at the feature invariants and position deviation caused by a long run time in feature points extraction when adopting difference of Gaussian pyramid method based on SIFT image mosaic algorithm, an image mosaic algorithm based on the FAST feature points extraction was proposed. In this algorithm, the first step is replacing original SIFT algorithm with feature extraction method based on FAST. The step followed by is describing and vector-matching the feature points, then registering image by Euclidean distance and RANSAC algorithm.The final mosaic image is accomplished by using weighted average fusion algorithm.Simulation results show that the new algorithm is more suitable to get seamless image in that it not only accelerates the extraction rate of the feature points, but also improves the accuracy of positioning.

FAST; feature points; SIFT; image mosaic

2015-11-03

国家科技支撑基金资助项目(2013BAH49F02，2013BAH49F03)

高晶，女，山西吕梁人，从事数字图像处理、智能信息处理研究。

TP751.1

A

10.16152/j.cnki.xdxbzr.2016-03-009