基于SITF特征提取的加速匹配方法
- 格式：doc
- 大小：194.50 KB
- 文档页数：9
基于SITF特征提取的加速匹配方法
摘要：SIFT算法是目前应用最广泛的特征点提取匹配算法，该算法具有尺度不变性，旋转不变性和一定的光照不变性。
但SIFT算法复杂度较高，而且图像匹配时间较慢，在较大形变和光照变化下易出现匹配不准确。
针对上述问题，提出极值分类匹配算法，将特征点分为极大特征点和极小特征点两类，进行分类匹配，并利用扩散过程来代替欧式距离计算特征点之间的距离。
本文方法不仅降低了时间复杂度，提高匹配速度，而且对图像形变和光照变化更具鲁棒性。
关键字：SIFT算法；图像匹配；特征分类；扩散距离
0 引言
图像匹配是图像预处理的基本任务，是图像拼接校正和图像融合最基本的步骤之一。
现已广泛应用于计算机视觉，包括目标识别与检测，遥感信息处理，医学图像处理以及三维场景重建等领域[1-3]。
近年来围绕图像匹配提出很多方法，主要可以分为三类，基于灰度的图像匹配方法、基于变换域的图像匹配方法和基于特征的图像匹配算法。
基于特征的匹配算法较其他两种方法而言计算量小，可靠性高，适应性强。
目前最流行的特征提取算法是2004年，David G.Lowe提出的SIFT（Scale-Invariant Feature Transform）算法，该算法实现了图像在模糊，旋转，缩放，光照变化等情况下的配准[4]。
与其他算法相比，SIFT在特征点提取和配准方面具有最优的鲁棒性，但其算法
效率并不最优。
许多研究者对SIFT做了优化和改进，包括Yanke等人提出PCA-SIFT算法[5]，Bay等人提出的SURF算法[6]，Morel等提出了Affine-SIFT(ASIFT)算法[7]，这些改进算法在运算速度方面优于原算法，但匹配精度不高。
本文在SIFT算法基础上提出一种极值分类匹配算法。
用SIFT 算法提取两幅图像的特征点，把特征点分为极大特征点和极小特征点两类，再使用扩散距离[8]代替欧氏距离确定候选匹配点。
1 SIFT特征提取与匹配
1.1特征点提取
一个图像的尺度空间定义为变化尺度的高斯函数与原图像的卷积，形成高斯金字塔，通过对两个相邻高斯尺度空间的图像相减，得到DoG(高斯差分金字塔)的响应值图像
其中，（表示高斯卷积核，表示两相邻尺度空间倍数的常数）。
在差分金字塔中采样点要和它同尺度的8个临近点和上下相邻尺度对应的9*2个点共26个点比较，找出在其邻域中的极大或极小值点。
通过对DoG函数拟合，精确特征点的位置和尺度，同时去除低对比
度点和边缘响应点。
1.2特征点描述
在描述阶段，根据特征点邻域内的梯度方向为每个特征点选定一个主方向。
将特征点周围邻域均匀划分为4*4个小块，计算每个小块中像素的梯度幅值和方向，对每个特征点形成4*4*8的128维描述子向量，最后对每一个点的128维向量进行归一化，去除光照的影响。
1.3特征点匹配
SIFT算法使用欧氏距离度量两幅图像特征点之间的相似性，在待配准图像中找到与当前图像某个特征点欧氏距离最近的特征点和次近的特征点。
用表示两点之间的距离，若距离之比小于某个阈值T，则接受为一对匹配点。
在得到了初始的匹配点对之后，采用随机抽样一致（RANSAC）算法来剔除误配点，获得更精准的匹配和图像转换模型。
2匹配算法的改进
2.1极值分类匹配法
由1.1可知，图像的特征点都是不同尺度的差分金字塔中的极大值和极小值经过拟合形成的，因此我们分别将两幅图像的特征点分为极大特征点和极小特征点，在匹配时将相同类别的特征点进行匹配。
（1）改进的极值分类匹配算法步骤：
①分别将两幅图像的极值点分类，原图像极大值点组成集合，极小值点组成集合，待配准图像极大值点组成集合，极小值点组成集合；
②建立待配准图像的K-D树，将生成（极大值树），生成（极小值树）；
③分别取原图像两个集合中的点，用BBF有序搜索算法[3]在和中使用下文介绍的扩散距离比较最近邻距离与次近邻距离的比值，确定候选匹配点。
（2）算法性能分析
使用改进的算法步骤进行匹配加快了特征点匹配速度，其主要表现在两个方面：构建K-D树和搜索近邻点。
①构造K-D树的时间复杂度为,设待匹配图像中集中特征点个数为, 集中特征点个数为，。
则建立的复杂度为，建立的复杂度为。
②个最小临近点的查找需要的时间。
若使用原算法，设是极大值匹配次数为，极小值匹配次数为。
现使用极值分类法，搜索次数为，搜索次数为，则，算法复杂度的证明同①。
2.2扩散距离度量相似性
SIFT算法是采用特征点间的欧氏距离作为相似性度量。
由于每幅图像的特征点数目很多，且每个点都是128维向量，所以欧氏距离的计算效率很低。
本文使用扩散距离进行特征点之间的相似性度量。
扩散距离（Diffusion Distance）是Haibin Ling和Kazunori Okada 在2006年提出的基于局部描述子的直方图比较的测量方法，该方法模拟温度场热量扩散来计算距离[8]。
假设一维分布和，它们之间的差值为,现定义一个孤立的温度场,在时，= 温度场热量扩散方程式为
是金字塔层数, 是高斯滤波函数标准差，“ ”符号的意义代表着对上层图像的降采样。
我们用范式来计算因此式(10)可以近似为
采用扩散距离的方法可以降低相似性度量的复杂度。
首先，降采样操作的计算量呈指数减少。
其次，高斯滤波的卷积操作是线性计算。
而使用欧氏距离，每对特征点的比较都要进行128次的平方运算，
所以对于大量的特征点匹配，扩散距离的计算效率明显提高。
3实验结果与分析
本文的编程平台为Visual Studio 2010下的Opencv2.4.5开源计算机视觉库。
使用C/C++语言编程，实现了极值分类法和使用扩散距离进行相似性度量的特征点快速匹配方法。
由以上图片和图表可以看出，利用本文提出的极值分类算法和扩散距离方法在匹配速度上比SIFT算法大大加快，而且在图像形变和光照变化下具有更高的精确度。
4结论
本文简单介绍了SIFT算法，提出了一种基于SIFT的特征匹配加速算法，首先将特征点分成极大值类和极小值类，匹配时生成两棵K-D树分别搜索近邻特征点，然后用扩散距离代替欧氏距离计算特征点之间的相似性，生成初始匹配点，最后用RANSAC算法去除误配，通过变换矩阵得到配准后的图像。
实验结果表明，改进算法不仅在时间上节省开销，提高匹配效率，而且在形变和光照变化方面有很强的鲁棒性。
参考文献
[1].张谦，贾永红，胡忠文.多源遥感影像配准中SIFT特征匹配改进[J].武汉大学学报,2013, 38（4），40（1），455-459.
[2].易军凯，边锆辉，姜大光.尺度不变特征转换特征提取优化算法研究[J].北京化工大学学报,2013,38（4），115-119.
[3].刘金侠.基于特征的图像匹配和图像融合研究[D].北京：中国科学院研究生院硕士学位论文,2013.
[4].Lowe D G. Distinctive Image Features from Scale invariant Keypoints [J].International Journal of Computer Vision，2004，60(2):91-110.
[5].AbdiH，Williams L J．Principal component analysis[J]．Wiley
Interdisciplinary Reviews：Computational Statistics，2010，2：433-459．
[6].Bay H. Tuytelaares T. Van Gool L.Surf: Speeded up robust features[C]//European Conference on Computer Vision.2006:404-417.
[7].Morel J M, Yu G S.ASIFT: A new framework for fully affine invariant image comparison[J].SIAM Journal on Image Sciences,2009,2（2）:438-469.
[8].Ling H, Okada K. Diffusion Distance for Histogram Comparison.IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE Computer Society,2006.246-253.。
