基于SIFT图像特征提取与FLANN匹配算法的研究

王金龙, 周志峰

(上海工程技术大学，上海 201600)

0 引言

特征点的检测和匹配是计算机视觉中非常重要的技术之一，在物体检测、视觉跟踪、三维重建等领域都有非常广泛的应用。

目前特征提取方法可以分为3种：一是基于所制定模板的特征检测，二是基于图形边缘的特征检测，三是基于亮度变化特征检测[1]。第一种由于设计的模板会随着检测图像的变化而变化，所以遇到复杂的图像时就显得不适用，第二种必须先进行边缘化处理之后才可以进行特征检测，第三种就是目前的研究热点，Harris[2]、SIFT、SURF均属于这种类型。目前国内外学者已经在这方面做了大量的研究。图像的特征匹配技术主要分为两类，一是基于灰度值的图像匹配，二是基于特征的图像匹配方法，其中基于灰度值的匹配方法，主要是利用空间中一维或者二维的滑动模板实现图像的匹配，这样做的优点在于匹配率高，然后计算量太大，所以匹配时间会比较长。而基于特征的图像匹配的这种方法，主要是通过提取出图像的一些显而易见的稳定的特征，将不同图像中的一些相同性质关联起来，由于不需要穷举匹配，所以匹配速度较快。本文将SIFT特征提取与FLANN匹配算法结合在一起，实现了对两幅图像的特征匹配，并通过VS2015与Opencv库结合，用C++语言进行特征提取与匹配算法的实现，并验证了在旋转，亮度变化的情况下仍然能实现较精确的匹配结果。

1 特征点提取算法(SIFT)

SIFT(Scale-invariant feature transform)是一种检测局部特征的算法，该算法通过求一幅图中的特征点及其有关的scale和orientation的描述子得到特征并进行图像特征点匹配，SIFT特征不仅仅具有尺度不变性，即使改变旋转角度，图像的亮度等条件，也能实现很好的检测效果。文章会针对SIFT特征做相应的理论分析，并验证这一结论，并与FLANN匹配算法结合，实现快速准确的匹配。大致分为以下几个步骤：构建尺度空间，LOG近似DOG找到关键点及检测DOG尺度空间的极值点，精确定位特征点，确定特征点的方向，最后生成SIFT特征描述子。

1.1 构建尺度空间

尺度空间理论就是利用高斯核函数对图像进行尺度变换来模拟图像数据的多尺度特征。获得图像在尺度空间下的多尺度序列表示。高斯卷积核是实现尺度变换的唯一线性核，如式1所示，一幅二维图像的尺度空间可以表示为[3]：

L(x,y,σ)=G(x,y,σ)*I(x,y)

(1)

其中：G(x,y,σ)是尺度可变高斯函数，随着尺度因子σ不同，将会产生不同尺度下的一组图像L(x,y,σ)，称为高斯尺度空间，σ大小决定图像的平滑程度，大尺度主要展示了图像的大致的外貌特征，小尺度主要展示图像的细节部分[4]。大的σ值表示是图像比较粗糙的尺度(低分辨率)，反之，对应精细的尺度(高分辨率)，图1显示了Gaussian尺度空间中随着的值的变化图像变的越来越模糊。为了有效地在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间(DOGscale-space)。如式2所示，采用了不同尺度的高斯差分核与图像卷积生成，如图1所示。

图1 DOG产生的原理图

(2)

对于尺度空间而言，在Lowe的论文中，他将第0层的初始尺度定义为1.6，也就是说最模糊的，图片的初始尺度定义为0.5(最清晰)，在检验极值点之前，Lowe建议在建立尺度空间之前，需要对原图进行长宽的扩展，以保留更多的图片信息，增加特征点的数量。

对于图像金字塔的建立问题，对于一幅图像，建立其在不同尺度(scale)的图像，也成为子八度，这是为了保证其尺度不变性(scale-invariant)，也就是在任何尺度都能够有对应的特征点，第一个子八度的scale为原图大小(金字塔的最底端)，后面每个octave为上一个octave降采样的结果，即原图的1/4(长宽分别减半)，构成下一个子八度(高一层金字塔)。每上一层是对下一层做Laplacian变换。

1.2 检测DOG空间的极值点

为了检测出高斯差分尺度空间中的存在的极值点，所选中的每一个采样点均要和周围的26个邻域点比较，即同尺度中相邻的8个像素点和上下相邻尺度的各9个像素点，总共26个像素点相比较，当采样点比这26个邻域点大或者小时，则将此点看作是候选的关键点[5]，如图2所示。

图2 极值点查找 图3 离散空间极值与连续极值

在进行极值比较的过程中，每一组图像中的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，对每组图像的顶层使用高斯模糊生成3幅图像，高斯金字塔每一组有S+3层图像，DOG金字塔有S+2层。

1.3 精确定位特征点

如图3所示，展示了二维函数在离散空间里面所求出来的极值点与连续空间中的极值点区别。

通过拟合三维二次函数以准确的确定关键点的位置和尺度(达到亚像素要求)，同时去除一些不稳定的边缘特征点，提高匹配的准确度和稳定性，主要分为以下几个步骤：

1)使用子像素插值的方法，通过对离散的空间点不断的插值可以求出连续的空间中的极值点，对尺度空间DOG函数进行子像素插值也就是数学上的曲线拟合[6]，运用DOG函数在尺度空间里面的泰勒级数展开式，如式(3)所示：

(3)

对式(3)求导，然后让这个导数等于0，即可解出相对极值的偏移量，这样可以得到相应极值点:

(4)

所得到极值点xmax的亚像素的位置。如果偏移值大于0.5这个条件成立，这就说明靠近另一侧的像素点，这时候让另一侧的像素选为候选的特征点，循环重复上面的计算，这样就可以获得新的亚像素的位置，之后在用该亚像素精度的位置取代所有尺度之前的候选的特征点位置[7]。

2)在已经检测出的所有的特征点中，需要去去除一些无关的响应点，比如一些低对比度的特征点和一些不稳定的边缘响应点。把公式(4)代入公式(3)，即在DOG Space的极值点处取值，只取前两项可得，如式(5)所示：

(5)

1.4 确定特征点的方向

关键点领域像素的梯度方向是不同的，根据他们分布特性的不同为每一个关键点指定一个确定的方向，使其可以具备旋转不变性。这也是判断特征子优越性的一个重要因素。

针对于窗口的每一个采样点L(x,y)，其梯度方向的幅值和方向分别可以用m(x,y)和θ(x,y)公式表示，分别如式(6)和式(7)：

(L(x,y+1)-L(x,y-1))2

(6)

(7)

每一个关键点需要3个信息：位置，尺度，方向，这样可以确定一个SIFT特征区域。

做一个包含所有梯度方向的分布直方图，取值范围是一个圆周0～360°，划分每10°为一个bin，这样可以分为36个bin。每个采样点根据其梯度方向θ(x,y)加权统计到分布直方图中，取幅度m(x,y)与贡献因子的乘积为规定的权值。贡献因子定义为采样点到关键点即窗口中心的距离长度，距离的量度遵循以下原则：如果距离越大，那么贡献因子就会越小反之则会越大，选择分布直方图的最大值为所选关键点在此邻域梯度方向中的主要方向[8]，如图4所示。

图4 特征点方向的确定示意图

1.5 生成SIFT特征描述子

SIFT描述子是关键点领域高斯图像统计结果的一种表示，特征描述子意味着特征点的一切信息包括梯度方向、幅值等等，为了能够提高稳定性，优秀的特征描述子应当包括此特征点的位置和灰度信息，除此之外，还需要反映这个特征点的一些局部的灰度变化信息。SIFT特征描述子就是一个高维向量，它包含着特征点的领域的所有信息，生成特征描述子之前，首先应该确定特征点邻域内像素的主方向，我们可以选择0度作为主方向，这样就可以消除旋转变换所带来的影响，其次在每个4×4的16个区域中统计每个领域中的8个方向的梯度方向分布直方图。图5中，选取了16×16的邻域，要统计16个分布直方图，所选择的每个直方图均代表了该领域内8个方向的信息，这样就构成了128维的特征点描述子。

图5 16X16的特征点描述子

特征描述子需要具有光照不变性，我们可以将特征向量通过式(8)归一化为单位长度，下文的实验表现出很好的匹配效果。

(8)

2 特征匹配最近邻算法FLANN

在现代化的机器学习中，训练一个高维特征数据，然后找到训练数据中的最近邻计算是需要花费很高的代价的。对于一个高维特征，目前来说最有效的方法是The randomized k-d forest和The priority search k-means tree，而对于二值特征的匹配multiple hierarchical clustering trees则比LSH方法更加有效[9]。图6显示了特征匹配的一般步骤，目前来说，fast library for approximate nearest neighbors(FLANN)可以很好地解决这些问题，Muja和Lowe于2009年提出FLANN算法，FLANN算法模型的特征空间一般是n维实数向量空间，该算法的核心是通过使用欧式距离来寻找与实例点的最邻近的点，欧式距离的定义如式(9)所示。

图6 特征匹配的一般步骤

(9)

如果D值越小，这就表明了这些特征点对之间的距离越”近”，也就是说它们相似程度越高。

2.1 快速近似NN匹配

2.1.1 随机K-d树算法

1)Classic k-d tree求取出数据中方差最高的那个维度，然后利用这个维度的数值将数据划分成2个部分，接着对每个子集重复上述的相同的计算步骤。

2)Randomized k-d tree通过创建许多颗随机树，然后从那些具有最高方差的N-d维中随机选取一些维度，并用这些维度来对数据进行划分。另外在对随机K-d森林进行搜索时，所有K-d均属于同一个优先级。从理论上说，如果增加树的数量，就能提高搜索速度[10]，提高效率，但由于硬件方面的种种限制，树的数量需要控制在一定的范围内，如果超出了速度不会增加甚至会变慢，实现原理如图7所示。

图7 随机K-d森林的实现原理

2.1.2 层次聚类树

层次聚类树采用的是K-medoids的聚类方法，而不是K-means，在本算法中，并没有像在K-medoids聚类算法中直接求最小化方差求聚类中心，而是在输入数据中随机选取聚类中心，这种建立方式显得更加简单，也可以保持各个树之间的独立性，在建立多棵树的同时，这个方法的搜索性能就提高了很多，这主要是因为随机选取的聚类中心，而不需要多次迭代计算聚类中心。建立多颗随机数的方法在K-d tree中比较有效，在K-means tree中却不适用。

2.1.3 优先搜索K-means树算法

随机k-d森林适用范围比较广，在很多情况下均有不错的搜索效果，然后如果对精度要求比较高，这样k-means树效果会更加好一点。K-means tree充分挖掘了数据本身所固有的一些机构特征，原理则是将数据的所有维度进行聚类处理，与之前的随机k-d tree只使用了一次维度划分[11]。本文采用的是K-means树的搜索原理，算法描述如下：

1)建立层次化的K-means树;

2)树的节点就选层次化的聚类中心;

3)如果某个duster内的点的数量小于K时，在这样的前提下就选择这些数据节点为叶子节点;

4)从根节点N开始检索;

5)如果N是叶子节点，则将处于相同层次的叶子节点添加到搜索结果中去，此时count + = |N|;

6)相反，如果N不是叶子节点，则将它的子节点与queryQ比较，找出最近的那个节点Cq，并将同层次的其他节点加入到我们所考虑的优先队列中;

7)对Cq节点进行递归搜索;

8)如果优先队列不为空和count

在匹配的过程中难免会出现错误的匹配对，通过K-mean算法处理之后，匹配的精度达到很高，速度也比较快。

3 实验结果及分析

本次实验中，通过对两幅图像分别进行旋转，缩放以及改变光照条件，检测该组合算法的抗干扰性以及匹配的成功率，检查匹配的准确率和速度。

3.1 光照变化

通过改变匹配时某个图片的光照情况(图片的亮度)，检测特征描述子对光照变化的适应情况，实验结果如图8所示。

3.2 缩放变化

通过对匹配的物体进行缩放，检测缩放前后特征点匹配情况，实验结果如图9所示。

图8 不同光照情况的结果图

图9 物体缩放前后匹配对比图

3.3 旋转变化

同一场景下，对物体进行不同角度的旋转，通过对比，得出文章中组合算法对旋转变化的适应能力，结果如图10所示。

3.4 SIFT与SURF对比

本文采用SIFT特征提取与FLANN匹配算法结合的方法，对匹配图像进行了综合性的实验，并与SURF特征提取与匹配进行了对比，对比结果图11所示。

图10 不同旋转角度图像间匹配图

图11 SIFT与SURF提取匹配对比

特征提取的方法特征点个数匹配点运行时间/s成功率/%SIFT120901.375SURF115890.977

从实验结果中可以看出SIFT算法的匹配准确度比SURF高很多，但是由于SIFT算法的复杂性，在特征点提取的过程中，时间较长。通过实验SIFT和SURF特征匹配的数据如表1所示。

4 结论

特征点提取是图像处理领域重要的一个环节，是接下来的图像匹配的前提，本文采用SIFT算法提取的图像的特征点，并与SURF特征点进行了简单的对比，SURF算法的准确性较SIFT高很多，SIFT对特征细节的表达也比SURF高很多，通过本次实验分析，可以得出SIFT特征算子对缩放、旋转、亮度变化的适应能力较强。虽然存在一些误差，但整体准确度比较高，满足一定的匹配要求。本文所采用的FLANN匹配算法的K-means tree匹配的准确率高，应用场景较广。本文的算法组合缺点也很明显，问题主要是在SIFT特征提取的时间比较长不能很好的应用到实时性处理中，但可以将SIFT与LBP特征结合[12]，可以提高效率，改善算法。实验结果表明，本文的组合算法对图像的亮度，旋转，缩放等各个方面都有较强的适应性。可以应用与图像识别，三维重建等热门领域，在后续的研究中，提高SIFT算法的效率是关键，可以通过改进SIFT特征提取的步骤来提高提取速度。

[1] 谭博怡. 图像特征提取与匹配[D]. 北京: 中国科学院研究生院, 2008.

[2] Harris C, Stephens M. A combined corner and edge detector [A].Manchester: Proceedings of the 4thAlvey Vision Conference[C]. Manchester, UK, 1988: 147-151.

[3] Lowe D G. Object Recongnition from Local Scale-Invariant Keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[4] Schmid C, Mohr R, Bouckhage C. Evaluation of interest point detectors[J]. International Journal of Computer Vision, 2000, 37(2): 151-172.

[5] Bay H, Tuytelaars T, Van Gool L. SURF: speeded up roubst features [A].Proceedings of European Conference on Computer Vision[C]. Graze, Austria, 2006: 404-407.

[6] Marius Muja, Lowe D G. Scalable Nearest Neighbor Algorithms for High Dimensional Data[J].

[7] Brown M, Lowe D. Invariant features from interest point groups[A].British Machine Vision Conference[C]. Cardiff, Wales, 2002: 656-665.

[8] Moller T, Haines E, Akenine-Moller T. 实时极端及图形学[M]. 普建涛,译. 北京:北京大学出版社.

[9] Muja M, Lowe D G. Fast approximate nearest neighbors with automatic algorithm configuration [A].Proceedings of IEEE Conference on Computer Vision Theory and Applications[C]. Lisbon, Portugal: IEEE Computer Society, 2009: 331-340

[10] 刘树勇, 杨超庆, 位秀雷，等, 邻近点快速搜索方法在混沌识别中的应用[J]. 华中科技大学学报, 2012, 40(11): 89-92.

[11] 崔江涛, 刘卫光. 一种多分辨率高维图像特征匹配算法[J]. 光子学报, 2005, 34(1):138-141.

[12] Zhao G, Pietikainen M. Dynamic texture recognition using local binary patterns with an application for facial expressions[A]. Asia Conference on Computer Vison(ACCV)[C]. 2011(3):281-292.