 Computer Science and Application 计算机科学与应用, 2012, 2, 204-208 http://dx.doi.org/10.12677/csa.2012.24036 Published Online October 2012 (http://www.hanspub.org/journal/csa.html) Improved SIFT Matching Algorithm* Can Ding1, Changwen Qu1, Yangyang Zhao2 1Department of Electronic and Information Engineering, Naval Aeronautical & Astronautical University, Yantai 2Simulator Training Center, Naval Submarine Academe, Dalian Email: dican011@126.com Receiv ed: Aug . 16th, 2012; revised: Aug. 29th, 2012; accepted: Sep. 9th, 2012 Abstract: The high dimension and complexity of feature descriptor of SIFT, not only occupy the memory space, but also influence the speed of feature matching. We adopt the statistic feature point’s neighbor gradient method, the local statistic area is constructed by 8 concentric square ring feature of points-centered, compute gradient of these pixels, and statistic gradient accumulated value of 8 direction, then descending sort them, at last normalize them. The new feature descriptor descend dimension of feature from 128 to 64, the proposed method can improve matching speed and keep matching precision at the same time. Keywords: SIFT Algorithm; Image Matching; Feature Descriptor; DoG 改进的 SIFT 匹配算法* 丁 灿1，曲长文 1，赵阳扬 2 1海军航空工程学院电子信息工程系，烟台 2海军潜艇学院模拟器训练中心，大连 Email: dican011@126.com 收稿日期：2012 年8月16 日；修回日期：2012 年8月29 日；录用日期：2012 年9月9日 摘 要：SIFT 特征描述子的高维性和复杂性，不但占用较大的内存空间，而且影响特征匹配的速度。文章采用 基于特征点邻域梯度统计的思想，局部统计区域由以特征点为中心的 8个同心方环分割出来的环形组成，并计 算出其相应像素的梯度(模值和方向)，统计出 8个方向的梯度累加值，然后进行从大到小的排序，最后再进行规 一化处理。建立新的描述子将原来的 128 维向量降低到 64 维，实验证明此方法在保持匹配精度的情况下提高了 匹配速度。 关键词：SIFT 算法；图像匹配；特征描述子；差分高斯金字塔 1. 引言 图像匹配是计算机视觉和数字图像处理的重要 组成部分，广泛应用于摄影测量与遥感、资源分析、 三维重建、目标识别等众多领域，一直视研究者关注 的焦点，但由于它受到天气、阳光、遮挡等外界因素 的严重影响，并且存在因不同成像时间、角度、距离 等因素而导致的图像平移、旋转、缩放等问题，这都 给图像匹配工作带来很大的难度。 长期以来，国内外许多学者都致力于能够解决上 述问题的图像匹配技术研究。近年来，在计算机视觉 领域，基于局部不变量描述符(local inv a r i ant descriptor ) 的方法在目标识别和图像匹配方面取得了显著进展。 1999 年D. G. Lowe提出尺度不变特征变换算法(scale invariant feature transformation, SIFT)，并 与2004 年总 结了现有的基于不变量技术的特征检测方法，并正式 提出了一种基于尺度空间的、对图像缩放、旋转甚至 *基金项目：“泰山学者”建设工程专项经费资助。 Copyright © 2012 Hanspub 204  改进的 SIFT 匹配算法 仿射变换保持不变性的图像局部特征描述算子即 SIFT 算子[1]。该算法较好的解决了场景部分遮挡、旋 转缩放、视点变化引起的图像变形的等问题，但是算 法仍存在问题，即特征描述符维数过高导致计算过于 复杂进而导致匹配时间过长。Yanke 等人[2]提出用 PCA-SIFT 方法对特征描述进行数据降维，但在没有 任何先验知识 的情况下，反而增加了计算量；Grabner[3] 等人用积分图像虽提高了 SIFT 的计算速度，但却降 低了 SIFT 方法的优越性。Delponte 等人[4]提出用SVD 方法进行特征匹配，但匹配过程计算复杂，且不能用 于宽基线匹配；这些方法只是在特征描述或者匹配阶 段进行改进，而没有改变算法本身。Mikolajczyk[5]等 人还通过实验证实了 SIFT 描述子在大多数情况下受 图像间的各种变换影响最小，具有最稳定的匹配性 能。同时他们还提出了一种叫做梯度的位置和方向直 方图(gradient location orientation histogram, GLOH)的 局部描述子，无论 PCA-SIFT还是 GLOH都利用 PCA 技术，这要求必须要选取一系列有代表性的图像来训 练投影矩阵，这不但需要额外的离线计算时间代价， 而且训练出来的矩阵也只对这类图像起作用，并不具 有广泛的适用性。秦晅在其改进 SIFT 算法中为每个 特征点定义了一个更精确的主方向，在生成特征点描 述子时去掉了对特征点周围像 素的高斯加权，从而降低了算法的计算成本，提 高了特征描述子对特征点的描述能力[6]。又有学者提 出利用圆环的特性同时对特征向量进行序列化，以保 证物体的旋转不变，当图像存在不同程度的几何变 形、副射畸变和噪声影响时，保持了很好的速度及精 度，但该算法在进行实际计算时较为复杂[7]。于丽莉 提出一种基于图像 Radon 变换的改进 SIFT 特征匹配 算法，降低了 SIFT 特征向量的维数，进而提高特征 匹配效率[8]。甘玲等在 SIFT 特征的描述符向量构造和 采样区域等方面进行改进，并通过对比特征描述符的 相似性建立特征点间的匹配关系，该算法能够适应图 像的尺度变化，增加了算法的鲁棒性，提高了图像配 准精度[9]。 文章针对 SIFT 特征描述符的高维数和高复杂度 问题对 SIFT 算法进行改进，采用基于特征点邻域梯 度统计的思想，局部统计区域由以特征点为中心的 8 个同心方环分割出来的环形组成，并计算出其相应像 素的梯度(模值和方向)，统计出每个方环的 8个方向 的梯度累加值，然后按照从大到小的顺序进行排序， 最后再进行规一化处理。建立新的描述子将原来的 128维向量降低到 64 维，以此通过减少特征描述符的 维数来降低计算的复杂度，进而缩短匹配的时间。 2. SIFT算法原理 SIFT 算法是一种提取局部特征的算法，在尺度空 间寻找极值点，提取位置、尺度、旋转不变量。SIFT 特征点源自差分高斯尺度空间的极值点，在差分高斯 图像中通过比较每一像素与当前尺度、上层尺度和下 层尺度的 26 个邻域得到极大值和极小值。SIFT 算法 然后使用泰勒展开式和 Hessian 矩阵过滤不稳定极值 点并计算其亚像素精度位置，并在高斯图像上，统计 特征点邻域各像素的梯度值和梯度方向得到特征点 主方向，以实现算子对尺度和方向的无关性。SIFT特 征的提取主要包含 4个步骤[10]： 1) 图像尺度空间，检测尺度空间极值点；2) 精 确确定关键点，剔除不稳定点；3) 确定关键点的方向； 4) SIFT特征向量的生成。 SIFT 特征的构造方法包括关键点的检测和描述 子的构造两部分。 2.1. 关键点(或兴趣点)检测 为了使特征具有尺度不变性，关键点检测是在多 尺度空间完成的。主要原理为：将输入图像通过不同 尺度 的高斯核函数连续滤波和下采样(sub-sam- pled)，形成高斯金字塔图像，然后再对相邻尺度的两 个高斯图像相减得到 DoG(difference-of-Gaussians)金 字塔多尺度空间表示。对DoG 尺度空间每个点与相 邻尺度和相邻位置的点逐个进行比较，得到的局部极 值位置即为关键点所处的位置和对应的尺度。再通过 拟合三维二次函数进行位置和尺度的精确定位，同时 去除低对比度的特征点和不稳定的边缘响应点，以提 高抗噪声能力。DoG 算子定义为两个不同尺度的高斯 核的差分，其具有计算简单的特点，是归一化 LoG (Laplacian-Gaussian)算子。高 斯卷积核是实 现尺度变 换的唯一变换核[1]。因此一幅图像(x,y)的尺度空间定 义为 ,,yLx ，是由不同尺度的高斯函数 ,,Gxy 与原图像卷积运算生成。图像金字塔的构建：图像金 Copyright © 2012 Hanspub 205  改进的 SIFT 匹配算法 Copyright © 2012 Hanspub 206 字塔共 O组，每组有S层，下一组的图像由上一组图 像降采样得到，如图 1所示。 DoG 算子如下式所示： ,,,,,, , ,,,, DxyGxyGxyI xy Lxyk Lxy (1) k 第 二 组 k 第 一 组 2.2. SIFT描述子的构造 在构造 SIFT 描述子之前首先为每个关键点赋予 一个主方向。主方向是指关键点邻域内各点梯度方向的 直方图中最大值所对应的方向。后续的描述子构造均以 该方向为参照，这样所构造 的描述子具有旋转不变性。 各像素梯度的模和方向的计算公式为式(2)、式(3)： Figure 1. Gaussian and difference of Gaussian 图1. 高斯金字塔和 DOG 算子的效果图 1,1 ,1 ,tan 1, 1, Lxy Lxy xy Lxy Lxy (3) 其中，L所用的尺度为每个关键点各自所在的尺度， 在实际计算中，在关键点为中心的邻域内进行采样， 用直方图统计邻域像素的梯度方向。 描述子的构造过程为：对任意一个关键点，在其 所在的尺度空间(高斯金字塔某一层)，取以关键点为 中心的 16 × 16像素大小的邻域，再将此邻域均匀地 分为 4 × 4个子区域(每个子区域大小为 4 × 4像素)， 如图 2所示。对每个子区域计算梯度方向直方图(直方 图均匀分为 8个方向)。然后，对 4 × 4个子区域的 8 方向梯度直方图根据位置依次排序，这样就构成了一 个4 × 4 × 8 = 128维的向量，该向量就是 SIFT描述子。 其中，第1维对应于第一个子区域的第一个梯度方向， 第2维对应于第一个子区域的第 2个梯度方向，第9 维对应于第二个子区域的第一个梯度方向，依次类推 [1]。随 后 将SIFT 特征进行归一化，进一步减少了光照 变化的影响。 Figure 2. SIFT descriptor 图2. SIFT描述符 时运算速度比较快，定位精度比较高： 1) 在多尺度空间采用 DOG 算子检测关键点，相 比传统的 LoG 算子的检测方法，运算速度大大加快； 2) 关键点的精确定位不仅提高了精度，而且大大 提高了关键点的稳定性； 3) 在构造描述子时，以子区域的统计特性，而不 是以单个像素作为研究对象，提高了对图像局部变形 的适应能力； 4) 对于 16 × 16的关键点邻域和 4 × 4的子区域， 在处理梯度幅度时都进行了类似于高斯函数的加权 处理，强化了中心区域，淡化了边缘区域的影响，从 而提高了算法对几何变形的适应性； 2.3. SIFT特征的主要特点 从理论上说，SIFT 是一种相似不变量，即对图像 尺度变化和旋转是不变量。然而，由于构造 SIFT特 征时，在很多细节上进行了特殊处理，使得 SIFT对 图像的复杂变形和光照变化具有了较强的适应性，同 5) 该方法不仅对通用的线性光照模型具有不变 性，而且对复杂的光照变化亦具有一定的适应性。 2 ,1,1,,1,mxyLxy LxyLxyLxy 2 1 (2)  改进的 SIFT 匹配算法 3. 改进的 SIFT 算法 SIFT 的高维特征向量，不但占用较大的内存空 间，而且影响特征匹配的速度。因此本文在特征点检 测阶段，本文采用文献[1]中的方法，检测出每个关键 点的位置，特征尺度以及主方向。在计算特征描述子 阶段，本文采用基于特征点邻域梯度统计的思想，局 部统计区域由 8个同心方环分割出来的环形组成，如 图所示(图3中仅给出 4个同心方环，图中符号﹡△◇ 及实线分别表示关键点的邻域)。同一方环的象素在图 像发生改变后，相对位置并为发生改变，同时像素其 它的相对信息基本保持不变。所以方环内 8个方向梯 度累加值排序后会对图像旋转保持一定程度的稳定 性。因此，设定第一个方环内排序后的 8个梯度累加 值作为描述符的第 1到第8的特征向量，以此类推。 本文方法在实际计算中，靠近特征点的像素的梯度信 息可以得到重复应用，越靠近特征点的像素的梯度信 息对形成特征描述符的贡献越大，起到近似高斯加权 的效果，减少远距离关键点的像素对关键点梯度信息 的影响。这样 8个方环的梯度累加值分别排序后组成 了8 × 8 = 64个特征向量，定义为关键点的特征描述 子，最后将此向量进行规一化处理，以减少光照变化 的影响。建立新的描述子将原来的 128 维向量降低到 64 维，得到更加紧凑的描述子表达，而且关键点邻域 的梯度更能表达出关键点的特征，进而能在保持匹配 精度不变的情况下提高匹配速度。如图 4为改进算法 的计算流程图。 4. 实验结果及分析 为检验本改进算法的有效性，本文先后进行如下 实验：一、将实验图像进行缩变、平移、旋转等来评 价两种算法的匹配结果。二、将从不同视点拍摄的图 像进行匹配，该组图像存在一定的辐射畸变和几何变 形。 特征点匹配需要计算待测图像中每一特征点描 述符与所有目标图像中全部特征点描述符的欧式距 离，如果最小欧式距离小于次最小欧式距离的 0.8 倍 即ratio = 0.8，则认为两特征点匹配。经反复实验当 ratio = 0.6时有可能损失部分匹配点但也去除了部分 误匹配点并且匹配率最高，如果某目标在待测图像上 多于 7对匹配点，则认为该目标可被可靠识别，7对 Figure 3. Improved SIFT descriptor 图3. 改进的 SIFT 描述符 确定 关键点 归一化 向量 最终 结果 尺度空 间检测 分别计算关键点 八邻域像素梯度 按梯 度大 小排序 生成 64 维向量 Figure 4. Flow chart of improved SIFT algorithm 图4. 改进SIFT 算法流程图 匹配点也能保证较高的仿射变换参数的计算精度。理 论上匹配点越多，解析的仿射参数精度越高，但得到 的匹配点越多越多耗费的计算时间也越多，实际上过 多的匹配点无助于进一部提高匹配精度，一般有 20~50对匹配点比较适中。使用 Intel Core 2 Duo主频 为2.2 GHz，内存为 504 MB 的计算机，Matalab7.04 环境进行编程实验。 从实验结果图 5、图 6及表1、表 2来看，改进 算法在保持匹配精度的情况下，提高了匹配速度进而 缩短了匹配时间。究其原因是原算法在对特征点进行 描述时消耗的时间较长。 5. 结论 本文针对 SIFT 特征描述符的高维数、高复杂度 Figure 5. Feature matching of Lena image 图5. Lena图像的特征点匹配 Copyright © 2012 Hanspub 207  改进的 SIFT 匹配算法 Figure 6. Feature matching of different visual angle image 图6. 不同视点拍摄图像的特征点匹配 Table 1. Compare of two methods about test one 表1. 实验一的两种算法的比较 Ratio = 0.6 原算法 改进后算法 初测特征点 215 333 215 333 匹配点数 80 80 误匹配点数 2 2 匹配率 97.5% 97.5% 匹配时间(s) 7.12 3.93 Table 2. Compare of two methods about test two 表2. 实验二的两种算法的比较 Ratio = 0.6 原算法 改进后算法 初测特征点 1496 1541 1496 1541 匹配点数 59 59 误匹配点数 2 2 匹配率 96.6% 96.6% 匹配时间(s) 15.1 7.06 问题改进了 SIFT 算法的特征描述子，在计算特征描 述子阶段，本文采用基于特征点邻域梯度统计的思 想，局部统计区域由 8个同心方环分割出来的环形组 成，将描述符的维数由 128 维降至 64 维，实验表明 改进的算法在保持了匹配率的同时缩短了匹配时间。 参考文献 (References) [1] D. G. Lowe. Distinctive image features from scale invariant keypoints. International Journal of Computer Vision, 2004, 60(2): 91-110. [2] Y. Ke, R. Sukthankar. PCA-SIFT: A more distinctive representa- tion for local image descriptors. Proceeding Conference Com- puter Vision and Pattern Recognition, 2004: 511-517. [3] M. Grabner, H. Grabner and H. Bischof. Fast approximated SIFT. Proceedings Asian Conference on Computer Vision, 2006, 1: 918-927. [4] E. Delponte, F. Isgrò, F. Odone, et al. SVD-matching using SIFT features. Graphical Models, 2006, 68(5-6): 415-531. [5] K. Mikolajczyk, C. Schmid. A performance evaluation of local descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615-1630. [6] 秦晅, 罗丽莉. 改进的 SIFT算法在图像匹配中应用研究[J]. 现代电子工程, 2009, 5: 49-52. [7] 赵垒, 侯振杰. 一种改进的 SIFT图像配准方法[J]. 计算机工 程, 2010, 36(12): 226-228. [8] 甘玲, 马艳春. 基于 SIFT 特征描述符的多尺度图像配准方法 [J]. 计算机仿真, 2010, 27(10): 207-210. [9] 于丽莉, 戴青. 一种改进的 SIFT 特征匹配算法[J]. 计算机工 程, 2011, 37(2): 210-212. [10] 武克南, 王丽萍. 一种基于不变特征的图像识别算法研究[J]. 甘肃科技, 2009, 25(9): 52-55. Copyright © 2012 Hanspub 208 |