![](https://csdnimg.cn/release/download_crawler_static/18921997/bg1.jpg)
第 40 卷 第 1 期
2013 年
北京化工大学学报(自然科学版)
Journal of Beijing University of Chemical Technology (Natural Science)
Vol. 40, No. 1
2013
尺度不变特征转换特征提取优化算法研究
易军凯摇 边锆辉摇 姜大光
*
(北京化工大学 信息科学与技术学院, 北京摇 100029)
摘摇 要: 针对尺度不变特征转换(SIFT)算法时间复杂度高的缺点,提出了 SIFT 特征提取优化算法。 分析了 SIFT
特征提取算法各个计算步骤的时间复杂性。 对 SIFT 特征提取过程进行了优化,包括耗时最多的高斯金字塔的创
建和计算特征描述符过程。 优化算法降低了特征点提取时间,减少了特征点的重复匹配,同时保证了匹配结果的
准确性。 最后,实验证明了优化后的算法能有效降低时间复杂度。
关键词: 针对尺度不变特征转换算法; 高斯金字塔; 高斯核; 特征描述符; 特征点提取; 物体识别
中图分类号: TP301郾 6
收稿日期: 2012-04-16
基金项目: 国家“863冶计划重点项目(2009AA01Z433)
第一作者: 男,1972 年生,教授
*通讯联系人
E鄄mail: jiangdg@ mail. buct. edu. cn
引摇 言
尺度不变特征转换( SIFT) 算法
[1]
是一种对于
尺度、方向、仿射变换、光照变化等具有不变性的局
部特征提取算法,在空间尺度中寻找极值点,并计算
特征描述的方向、尺度和旋转量,可用来检测和描述
图像中的局部特征。 SIFT 算法在场景匹配、目标识
别、图像检索、图像拼接、人脸识别等领域已经有成
功的应用
[2 - 5]
,并且在计算机视觉,模式识别领域有
广阔的发展前景。
Mikolajczyk 等
[6]
针对不同场景下,对光照变化、
图像几何变形、旋转、模糊和图像缩放等几种情况,
就最具代表性的 10 种局部描述子进行了对比试验,
结果表明 SIFT 算法在同类描述子中具有最强的健
壮性,但就算法效率来讲 SIFT 算法并不最优
[7]
。 针
对 SIFT 算法在计算时间上的不足,研究者提出了能
够快速提取特征点的算法,具有代表性的有 PCA鄄
SIFT,SURF,GLOH 和 ASIFT 等算法。 PCA鄄SIFT 采
用降维技术,降低了计算时间,但是它是不完全的仿
射不变。 SURF 简化了高斯二阶微分模板,运算速
度比 SIFT 算法快 3 倍左右,但是主方向的计算不准
确
[8]
。 GLOH 进一步增强了算子 的独特性和鲁棒
性,在实现中也用到了 PCA
[9]
降维方法。 Abdel鄄Ha鄄
kim 等
[10]
提出的 CSIFT 算法把 SIFT 算法的应用范
围从灰度图像推广到了彩色图像。 Liu 等
[11]
提出
SIFT Flow 的概念,并证实了该方法在复杂场景中的
图像对齐的有效性。 Morel 等
[12]
提出了 ASIFT 算
法,可 以 抵 抗 强 仿 射 情 况, 提 取 的 特 征 点 远 多 于
SIFT 算法。
本文对 SIFT 算法的高斯图像金字塔构造及计
算特征描述符过程进行了优化,在保持特征匹配准
确性的前提下,降低了 SIFT 算法的时间复杂度。
1摇 创建高斯金字塔优化
1郾 1摇 SIFT 算法各步骤耗时统计
SIFT 算法本身参数多、算法复杂度高,直接应
用无法满足物体匹配速率要求。 表 1 统计了算法各
个阶段所需时间分数。
表 1摇 SIFT 算法各阶段需时间分数
Table 1摇 Time consumption of each step of SIFT
算法阶段 时间分数 / %
创建高斯金字塔 24郾 088
创建高斯差分金字塔 5郾 1998
关键点检测 22郾 372
算法阶段 时间分数 / %
计算关键点尺度 0郾 0182
计算关键点方向 9郾 4938
计算特征描述符 38郾 9074
摇 摇 由表 1 可知,创建高斯金字塔和计算特征描述
符比较耗时,具有较大的优化空间。
1郾 2摇 高斯金字塔构建与高斯核
在 SIFT 算 法 中, 构 建 高 斯 金 字 塔 分 为 两 步:
(1)对图像做高斯平滑;(2)对图像做降采样。 一幅
图像可以产生几组图像,一组图像包括几层。 为了
让尺度体现连续性,相邻两层图像间的尺度为 k 倍