SIFT算法的介绍和应用

SIFT算法的介绍和应用

SIFT算法的介绍和应用﹡

The Introduction and Application of SIFT

陈志华1,吴彩荣1,赵建锋2,曾锻成2

CHEN Zhi-hua1, WU Cai-rong1, ZHAO Jian-feng2, ZENG Duan-cheng2

（1.南宁海蓝数据有限公司，广西南宁 530022 2.广西计算中心，广西南宁 530022）

（1.Highland Dightal Technology INC.,Nanning,Guangxi,530022,China http://www.77cn.com.cnputing

Center of Guangxi,Nanning,Guangxi,530022,China）

摘 要：在图像匹配中，有很多种算法。在这众多的算法中，SIFT算法具有良好的尺度、光照和空间旋转的不变性，所以被广泛的应用于图像匹配当中。本文对SIFT算法的四个主要步骤进行了简单的介绍，并将该算法应用到多色二值压缩的压缩算法当中，提高了压缩效率并且缩小了压缩后的存储空间。

关键词：SIFT 特征描述符 尺度空间 高斯差分 关键点 图像压缩

Abstract：There are a lot of algorithms in image matching. With the algorithm named SIFT we can extract features invariant to scale and rotation from images. The algorithm is widely used in image matching because of its excellent property. This paper presents the main steps of SIFT algorithm. We applied it to the patent about image compression. As a result, the effect of the patent is improved and the storage of the compression is reduced.

Key words：SIFT，feature descriptor，scale space，difference of Gaussian，key points，image compression

引言

图像匹配是计算机视觉的一个重要方面，在众多的视觉应用中是个关键技术，广泛的应用于地理信息系统、物体识别领域。近年来，在计算机视觉领域，基于局部不变量描述符的方法在目标识别和图像匹配方面取得显著进展。2004年，哥伦比亚大学的David Lowe提出了一种新的提取点特征的算法—SIFT算法。较好的解决了物体遮挡、旋转缩放、视角变换引起的图像变形等问题[2]。

1 算法思想

SIFT算法可以在不同的空间和图像区域中检测到大量的特征点，用于图像的匹配。Lowe曾做过实验，一幅500*500像素的图像中大约检测到了2000个特征点，当然特征点的数目也受到图像中景物的影响[1]。这些特征具有尺度和旋转不变性，而且能够克服光照和视角的变换。以下是获取图像的特征点的主要思想：

(1)尺度空间极值点的检测：该算法的第一步是通过对原始图像进行高斯滤波，建立高﹡应用基础研究专项项目（桂科基0342016）资助

SIFT算法的介绍和应用

斯金字塔，获得高斯差分来找到那感兴趣的关键点，也就是在以后的图像匹配中可能发挥作用的特征点。

(2)关键点的定位：在第1步中找到的点，需要经过稳定性的筛选才能成为真正的关键点。

(3)关键点方向的分配：根据每一个关键点邻域内点的梯度方向，为关键点分配梯度方向和梯度的模。

(4)关键点描述符：将特征点以多维向量的形式描述出来。

2 算法主要步骤

(1)建立图像尺度空间并检测极值点

首先建立尺度空间，要使得图像具有尺度空间不变性，就要建立尺度空间，SIFT算法采用了高斯函数来建立尺度空间，高斯函数公式：

1 (x2+y2)G(x,y,σ)=e/2σ2, (公式1) 22尺度空间定义为：L(x,y,σ)=G(x,yσ) I(x,y)，(公式2)

其中(x,y)表示点的坐标，σ表示尺度空间参数，随着

σ的变化，不同的尺度空间就建立起来，我们也称之为图像的高斯金字塔。*代表卷积操作。在进行高斯卷积时，整个图像要遍历所有的像素进行卷积(边界点除外)，这就造成了很大的时间和空间的复杂度，为了缩小时空复杂度可以对SIFT算法进行一个改进：在进行高斯卷积时可以将高斯公式在x方向上分解为：，同理在y方向上也可以分解。这样先在x方向上进行卷积，然后在y方向上卷积带来的空间和时间复杂度都会减小。选择=0.5进行高斯卷积作为第一组尺度空间的第一幅图像。在建立一组尺度空间后，再组建下一组尺度空间，对上一组尺度空间的最后一幅图像进行二分之一采样，得到下一组尺度空间的第一幅图像，然后进行像建立第一组尺度空间那样的操作，得到第二组尺度空间。如图1：

图1 高斯金字塔的建立，左为上一组，右为下一组

在尺度空间建立完毕后，为了能够找到稳定的关键点，采用高斯差分的方法来检测那些在局部位置的极值点，即采用两个相邻的尺度中的图像相减。公式定义为：

D(x,y,σ)=(G(x,y,kσ) G(x,y,σ)) I(x,y)=L(x,y,kσ) L(x,y,σ)，(公式3)

SIFT算法的介绍和应用

如图2：

图2

(2)检测关键点

要获得某个尺度空间中的极值点，除了将该点和它周围的8个点比较外，还要将它与相邻尺度的对应位置的点比较。如图

3：

图3

从图3可以看到，标记的点需要与它相邻的9*2+8=26个点进行比较，看它是否具有极大值或者极小值。Lowe在他的实验中在每组的3个不同的尺度中检测每个尺度中图像的极值点，为了能够检测3个不同的尺度中的极值点，就需要有5个高斯差分图像来比较，所以每组高斯卷积要产生6幅图像才满足要求。在找到极值点后，需要去除那些低对比度的点，这些点会降低匹配的准确性和抗噪声能力。单消除低对比度还不够，还要去除边缘响应点。一个不恰当的高斯差分函数会在边缘地方造成主曲率。主曲率通过一个2x2 的Hessian矩阵求出：

DxxH= DxyDxy Dyy （4）

D的主曲率和H的特征值成正比，令α为最大特征值，β为最小的特征值，则

令α=γβ，则：

SIFT算法的介绍和应用

2

(r + 1)/r的值在两个特征值相等的时候最小，随着r的增大而增大，因此，为了检测

主曲率是否在域值r下，只需检测

在Lowe的文章中，取r＝10。[4]

在实际计算中，导数由采样点相邻差得到。

Dyy=p[x][y-1]+p[x][y+1]-2*p[x][y];

Dxx=p[x-1][y]+p[x+1][y]-2*p[x][y];

Dxy=(p[x-1][y-1]+p[x+1][y+1]-p[x+1][y-1]-p[x-1][y+1])/4

把获得的局部极值点同它的相邻尺度空间的对应位置的点进行比较，检测它是否是尺度空间中的极值点。

(3)关键点方向的分配

利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。梯度的方向和模的计算公式分别如下：

其中L所用的尺度为每个关键点各自所在的尺度。 在实际计算时，我们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。首先在关键点的邻域内进行采样，建议采用邻域选择16*16的大小。但是如果选择以关键点为圆心，半径为8的圆作为邻域，可以减少计算数量，提高算法的效率，并且对寻找关键点主方向影响不大。

在邻域内，采用直方图统计的方式来统计该邻阈内的各个像素的梯度方向。这里n代表直方图的区间数。可以选择n=36，每10度为一个区间。从这36个区间中选择出该像素点的主方向。也就是直方图中峰值最大的方向。

(4)特征点描述符

在得到邻域内点的主方向后，将关键点描述成特征向量使关键点数值化。在关键点的邻域内，以4*4大小为单位作为一个种子点，采用直方图统计的方法后种子点将描述为8维的向 …… 此处隐藏：3223字，全部文档内容请下载后查看。喜欢就下载吧 ……