SIFT算法研究和应用

黄超，齐英剑

(中国传媒大学理学院，北京， 100024)

SIFT算法研究和应用

黄超，齐英剑

(中国传媒大学理学院，北京， 100024)

图像匹配是计算机视觉中众多问题的一个基本方面，包括目标和场景识别，从多图片里解决三维结构，立体相关性和动作追踪。本论文主要对SIFT算法的基本步骤进行了简单阐述，并且阐述了其在场景分类上的独特应用，以及一些重要改进。实验结果表明该算法具有在场景识别和分类上有较显著的优势，可以进行良好应用。

特征描述符;尺度空间;词包分类算法;独立成分分析;背影检测

1 SIFT算法介绍

1.1 引言

1999年哥伦比亚大学的David G..Lowe教授提出了SIFT算法，一种基于提取局部特征的算法在尺度空间寻找极值点，提取位置，尺度，旋转不变量。其具有局部性、特殊性、多量性和高效性等特性。他在2004年又把算法进行了完善总结，后来Y.Ke将其描述子部分用PCA代替直方图的方式，对其进行改进。该算法较好的解决了物体在发生旋转缩放、视角、光度变化引起的图像变形等问题。

1.2 SIFT 算法原理

David G..Lowe在2004年总结了现有的基于不变量技术的特征检测方法，提出了一种基于尺度空间的、对图像缩放、旋转和仿射变换具有不变性的图像局部特征描述子——SIFT算子。该算法首先在特征空间进行特征检测，并确定关键点的位置和所处的尺度，然后使用关键点邻域的梯度方向作为该点的方向，以实现算子对尺度和方向的无关性，从而得到了一种对尺度和方向无关的算子。

1.2.1 尺度空间极值点检测

尺度空间理论最早出现于计算机视觉领域时其目的是模拟图像数据的多尺度特征。Koendetink证明了高斯卷积核是实现尺度变换的唯一变换核，而Lindeburg等人则进一步证明高斯核是唯一的线性核。一幅二维图像在不同尺度下的尺度空间表示可由图像与高斯卷积核得到:

因此，要提取稳定的具有尺度无关性的特征点，就必须在图像二维空间和DOG(Difference of Gaussian)尺度空间中同时检测局部极值点。

在DOG空间检测极值时，需要把关键点与同一尺度的周围邻域8个像素和相邻2 6个像素进行比较，以确保同时在尺度空间和二维图像空间检测局部极值。

DOG算子计算比较简单，是尺度归一化的LOG算子的近似。

1.2.2 特征点过滤并进行准确定位

准确确定关键点的位置和尺度，在该过程中，要同时去除低对比度的特征点和不稳定的边缘相应点，以增强提取出来的描述符的有效性和实用性，提高抗噪能力。

DOG算子会产生较强的边缘响应，因此要通过拟合三维二次函数以准确确定关键点的位置和尺度。

1.2.3 关键点方向分配

利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具有旋转不变性。

至此，图像的关键点已检测完毕，每个关键点有三个信息:位置、所处尺度、方向。这样就可以一个SIFT特征区域。

1.2.4 生成描述特征点的特征向量

首区域计算8个方向的梯度直方图，绘制每个梯度方向的累计值，即可形成一个种子点，这样对于每个关键点就可以形成一个128维的SIFT特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，然后将特征向量的长度归一化，就可以进一步去除光照条件的影响。这种邻域方向性信息联合的思想增强了算法的抗噪声能力，同时对于含有定位误差的特征匹配也提供了较好的容错能力。特征向量生成示意图如下(图1):

图1 特征向量生成示意图

1.2.5 SIFT描述符在图像匹配方面的表现

当两幅图像的SIFT特征向量生成以后，采用关键点特征向量的欧氏距离作为两幅图中关键点相似性的判定度量。取其中一幅图片的某个关键点，并找出另一幅图片中欧式距离最近的的前两个关键点，在这两个关键点中，如果最近的距离除以次近邻的距离小于某一个预先设定的比例阈值，则接受这一匹配点。

2 SIFT描述符的应用

SIFT描述符最早用于图像匹配，在随后的研究中，不断有新的算法提出并应用到不同领域。比如使用SIFT特征完成目标识别，包括最近邻搜索，对象位姿的霍夫聚类，最小二乘位姿计算，最后完成验证，其它应用还有3D重建，运动跟踪、分割、机器定位、摄影机标定等。未来的研究还包括建立光照不变的颜色描述符(目前是单色的灰度图像)局部纹理的测量，这方面的研究已经在人类视觉中扮演了越来越重要的角色，可以整合到特征描述符中，可以多特征结合进行对象识别;另一个方向是特定对象类别的识别。

2.1 SIFT描述符应用于图像匹配中

当两幅图像的SIFT特征向量生成以后，采用关键点特征向量的欧氏距离作为两幅图中关键点相似性的判定定量。取其中一幅图片的某个关键点，并找到另一幅图片中的欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近邻的距离小于某一个预先设定的比例阈值，则接受这一匹配点。

结果(对lena图像提取特征点图2)如下:

结果如下:

以上看出提取出来的SIFT描述符在图像匹配上有很好的应用。因为该图像是对原图像进行顺时针90°然后在另一幅图片上进行了一个小贴图，结果比较理想。证明了SIFT描述符的旋转不变性。

2.2 SIFT描述符在场景分类中的应用

图像目标的分类、识别是计算机视觉和模式识别领域的一个重要的研究问题。由于图像目标存在视角变化、亮度变化、尺度、目标变形、遮挡、复杂背景以及目标类内差别等影响，使得图片目标的分类非常困难。针对这些问题，lowe提出的SIFT描述算子，这种具有尺度不变、旋转不变的局部特征为了使用这些局部特征提出了许多基于特征包(Bags of Features)的方法对图像进行分类，并取得了良好的性能，但是这些方法没有利用局部特征在图像空间的位置关系，只利用了局部特征在特征空间的关系，最近Lazebnik借鉴Grauman的金字塔匹配思想，在Discriminative Classification with Sets of Image Features中提出空间金字塔匹配核(Spacial Pyramid Matching Kernel)，首先对局部特征量化，并在二维图像空间建立金字塔，然后计算两幅图像的子图像区域局部特征直方图交叉，该方法要求图像中的目标比较规范，且要求目标在图像中的位置比较一致，这也是其缺陷，时间效率不会很高。

2.3 结合金字塔匹配方法对图片库分类

金字塔匹配是一种以特征为基础的匹配，即指通过分别提取两个或多个图像的特征(点、线、面等特征)，对特征进行参数描述，然后运用所描述的参数来进行匹配的一种算法。基于特征的匹配所处理的图像一般包含的特征有颜色特征、纹理特征、形状特征、空间位置特征等。要进行图像匹配首先要进行特征提取与描述，通常我们将此类问题看做是识别图像的语义种类。

建立金字塔首先要用一个规则的晶格在每一幅图片上提取SIFT描述符，然后通过K-均值建立词典，每一个SIFT描述符给定了一个纹理标签，该标签是与最近的词典码字相对应的。最后，金字塔从这些标签中产生出来。所以该算法主要分以下步骤:

1)生成SIFT描述符(GenerateSiftDescriptors)

2)计算词典(CalculateDictionary)

3)建立直方图(BuildHistograms)

4)构建金字塔(CompilePyramid)(该步较重要现将流程表达如下)

基本流程如下:

2.4 结合SIFT描述符的性别识别

性别识别(gender recognition)结合面部表情的密集SIFT描述符和形状内容，性别分类很重要，因为它可以提升其它一些应用，比如人体识别和人机交互。

应用SIFT描述符对面部的的性别识别有四个问题:

(1)由于丢失的纹理信息或者因为光照原因的图片只能提取一部分的关键点。

(2)在关键点上的SIFT描述符是独特的，但是在非关键点(如晶格)可能对准确性有负面影响。

(3)对于相对较大尺寸的的图片则需要获取足够的关键点来支持图像匹配。

(4)匹配算法假设人脸是被合适的记录下来。

处理以上问题主要是通过将SIFT描述符和形状特征，而不是仅仅提取兴趣点周围的描述符，在规则图片晶格点上提取局部特征描述符，这就需要对面部图片进行密集特征提取。另外面部图片的全局形状融合在这些密集特征中来提高准确性。

2.5 结合SIFT特征匹配的的阴影检测

阴影检测(shadow detection)对视觉监督系统的健壮性和可靠性是至关重要的，当目标部分和真正的阴影部分比例相似的时候，基于灰度水平和颜色信息的阴影检测就会失效，但是当利用SIFT特征检测时就可以解决这一问题。在2010年国际信息工程大会上 ZhangLiang和 HeXiaomei的Fake Shodow Detection Based on SIFT Features Matching提出的利用RGB颜色模型候选阴影检测出来之后，然后利用SIFT算法将局部特征描述出来(在两个连续的框架内)对于移动目标和阴影的SIFT特征的位置信息就会得到，从而将阴影检测出来。

2.6 结合SIFT描述符和自适应颜色独立成分分析对图像的分类

一般对图像分类或者匹配都是在灰度图像上，对于在颜色图像上进行分类就显得比较难。所以如何能找到一种自适应强且效果好的颜色空间来提取SIFT特征就成了一个重要的课题。在2010年国际模式识别大会上Danni Ai等在Adaptive Color Independent Components based SIFT Descriptors for Image Classification中提出的，此方法不仅可以加强目标和背景之间的对比度，和传统的目标和场景分类相比效果也是很好的。主要从以下两方面进行处理:

(1)基于独立成分分析，一种自适应能力好且效果好的颜色空间用来表示颜色图像。

(2)在此基于颜色空间中的独立成分分析中，一种有区别性的CIC-SIFT描述符计算了出来用于图片分类。

3 SIFT算法的改进

3.1 提高旋转不变性

不同图像之间的匹配在一算计视觉中一直是一个很有挑战性的课题。图像匹配也是中国计算机视觉应用中的几个必须步骤，如三维重建，镶嵌和目标识别。图像点需要通过特征向量提取出来，或者整幅图片应用密集匹配(算法效率不高，硬件要求较高)。提取的图像点然后通过一个特征描述符的算法转化成一个特征向量，这个向量最终来对比建立匹配。

由于不能保证每幅图像都能很规则的表示，所以难免会有图片有旋转，那么在遇到这种情况下，SIFT描述符就显示了其优势。图像描述符在匹配图像特征中已广泛得到一种应用结构。基于SIFT方法的描述符是通过计算不同特征区域的梯度方向直方图，一般都是通过一种规则的笛卡尔晶格或者log-polar晶格来划分区域。为了得到旋转不变性，特征点一般需要在主梯度方向上进行旋转。在Fabio Bellavia等的Improving SIFT-based descriptors stability to rotations中提到了一种改进是基于某种晶格进行的SIFT特征提取，这样可能就会避免在计算描述符之前旋转特征点，因为提前定义的离散方向可以很容易的通过改变描述符向量来得到。

3.2 利用灰关联提高计算率

在上面应用中介绍了在性别识别中用到是密集SIFT描述符，通常这需要很大的计算量和较高配置的硬件，这样要求怎样能更好的准确定位关键点可以加快计算的速度从而提高效率。因为淡出的特征点提取容易不够用，而稠密采样又计算量大，可以使用灰关联的方法较合理的获得特征点，也兼顾平滑特点。灰色关联分析的基本思想是根据序列曲线几个形状的相似程度来判断其联系是否紧密。曲线越接近，相应序列之间关联度越大，反之就越小。就是利用灰关联的这种性质，在进行SIFT描述符提取的过程中可以利用该理论进行关联度判断，从而判断其关联度的大小来决定是否是其达到要求的兴趣点。这种方法就可以更好更快的解决效率问题。

在以后的工作中，如何更快更好的算法找到特征点，是研究的重点。

4 结束语

本文主要研究了SIFT算法，介绍了SIFT算法的原理和将算法应用到图像匹配和图片分类和算法的改进，并结合其他算法应用到图像分类中的应用，说明SIFT描述符和算法确实具有很强的应用价值，具有较强的健壮性，而且结合其他算法可以实现更多的重要功能，这些都需要有待进一步的研究。

［1］David G Love.Distinctive Image Featurea from Scale-Invarient Keypoints.International Journal of Computer Vision，2004.

［2］Sv etlana Lazebnik，Cordelia Schmid，Jean Ponce.Beyond Bags of Features:Spatial Pyramid Matching for Recognizing Natural Scene Categories.IEEE，2006.

［3］Kristen Grauman，Trevor Darrell.The Pyramid Match Kernel:Discriminative Classification with Sets of Image Features.IEEE，2005.

［4］K Mikolajczyk and C Schmid.A performance evaluation of local descriptors.IEEE Transaction on PAMI 2005

［5］Jian-Gang，Jun Li，Wei-Yun Yau.Boosting Dense SIFT Descriptors and Shape Contents of Face Images for Gender Recognition.IEEE，2010.

［6］Liang Zhang，Xiaomei He.Fake Shadow Detection Based on SIFT Features Matching.IEEE，2010.

［7］Danni Ai，Xianhua Han，Xiang Ruan，Yen-Wei Chen.Adaptive Color Independent Components based SIFT Descriptors for Image Classification.IEEE，2010.

［8］杨淑莹.模式识别与智能计算——Matlab技术实现［M］.电子工业出版社，2009.

［9］于成波.数字图像处理及MATLAB实现.重庆大学出版社，2003.

［10］刘思峰，谢乃明等.灰色系统理论及其应用［M］.科学出版社，2008.

SIFT Algorithm Research and Application

HUANG Chao，Qi Ying-jian
(School of Science Communication University of China Beijing 100024)

Image matching is a fundamental aspect of many problems in Compter Vision，including object and scene recognition，solving 3D structure in more images，3D correlation and motion tracking.The paper is mainly about SIFT alorithm and the its application in scenes classification and some of its improvement.The experiments results shows that it has significant advantages in scene recognition and classification，it also can be improved and adopted in other computer vision.

feature descriptor;scale space;BOF，ICA-SIFT;shadow detection

TP391

A

1673-4793(2012)01-0068-05

2011-1-5

黄超(1987-)，男，山东临沂市人，中国传媒大学研究生。

(责任编辑

:龙学锋)