一种简化的SIFT图像特征点提取算法

第25卷第7期2008年7月　

计算机应用研究

ApplicationResearchofComputersVol.25No.7Jul.

2008

一种简化的SIFT图像特征点提取算法

高　健,黄心汉,彭　刚,王　敏,吴祖玉

(华中科技大学控制科学与工程系,武汉430074)

3

摘　要:针对目前尺度不变的图像特征点提取算法计算量较大,算法较复杂的问题,提出一种简化的SIFT图像特征点提取算法。此算法通过改变金字塔尺度空间的结构实现对SIFT特征点提取过程的简化,通过改变特征点描述子的结构实现对特征向量计算的简化,验证明了该算法的有效性。

关键词:特征点提取;图像匹配;中图分类号:TP391　　　文献标志码::2203

pointdetectingmethod

GAOJian,HUANGXin2han,PENGGang,WANGMin,WUZu2yu

(Dept.ofControlScience&Engineering,HuazhongUniversityofScience&Technology,Wuhan430074,China)

Abstract:Thescale2invariantimagefeaturepointdetectingmethodsarealwayscomplexandneedlargecomputation.Inorder

tosolvetheproblem,thispaperproposedafeaturepointdetectingmethodwhichwasasimplificationoftheSIFTmethod.ThemethodchangedthepyramidframeinimagescalespacetosimplifytheSIFTfeaturepointdetectingprocessandchangedthedescriptorconfigurationtosimplifytheeigenvectorcomputation.Itcouldensuretheperformanceanddecreasethecomputationatthesametime.Theexperimentalresultshaveproveditsvalidity.Keywords:featurepointdetection;imagematching;SIFT(scaleinvariantfeaturetransform)method

　　图像特征在图像处理中具有非常重要的意义。目前,几何特征、彩色特征、纹理特征和特征点在目标识别、运动估计和立体匹配等领域中均已得到了一定程度的应用。在实际应用中,图像经常会发生变化,提取具有较强鲁棒性的图像特征就显得尤为重要。尺度不变的特征点对移动、旋转、噪声、缩放、遮挡等图像变换均具有较强的适应能力。因而近年来,尺度不变的特征点提取算法及其应用成为了图像处理领域中的一个研究热点。

Harris角点检测算法

[1]

维的特征向量空间,使用了BBF算法加快搜索过程,取得了较好的效果。SIFT算法已经在图像匹配[5]、全景拼接[6]和视觉导航[7]等领域得到成功应用。为了更好地适应实时性要求较高的场合,本文提出一种简化的SIFT算法,它可以在一定程度上减少计算量、缩短计算时间。

　特征点的提取

整个图像特征点提取算法可以分为特征点的提取和特征点描述与匹配。其中,如何提取鲁棒性较强的特征点是整个算法的基础。

1　特征点的鲁棒性

在实际的特征点提取算法中,微分算子可以实现对图像的位移不变;数字图像处理中微分的差分表示可以在一定程度上适应图像的亮度改变;具有各向同性的微分算子可以适应图像的旋转变化;对图像进行高斯卷积则可以增强抵抗噪声干扰的能力;要适应图像尺度的变化就需要在图像的尺度空间中计算规格化导数。

如图1所示,图像的尺度空间是这幅图像在不同解析度下的表示。一幅图像I(X)在不同解析度下的表示可以利用高斯核G(t)的卷积来实现:L(X;t)=G(t)3I(X)(t为高斯方差)。图像的尺度大小一般用高斯标准差σ(σ=t1/2)来表示。

Lindeberg在文献[8]中对图像尺度空间理论进行了详细的论

是一种经典的图像特征点提取算

法。虽然Harris角点对图像平移、图像旋转和图像噪声均具有较强的鲁棒性,但是它却无法适应图像的尺度变化,这也在一定程度上限制了它的应用。随着图像尺度空间理论的发展,近年来一些具有尺度不变特性的特征点提取算法被提了出来。

[2]

这其中包括Harris2Laplacian算法、基于相位的局部特征点[4]提取算法[3]、Patch2Duplets算法、Laplacian算法和SIFT算

法[5]。前三种都是基于Harris角点并且扩展到了尺度空间以适应图像的尺度变化。这类算法鲁棒性较强,但是计算较复杂,实时性较差。与之相比,后两种算法对大噪声情况适应能力较差,但是算法相对简单,实时性较好。

SIFT算法

[5]

是Lowe提出的一种比较奇特的特征点提取

算法。它选择高斯残差在尺度空间上的极值点为特征点,并计算特征点局部邻域内的梯度方向直方图为描述子。这种算法将图像金字塔结构引入尺度空间以减少计算量,同时针对128

　　收稿日期:2007206226;修回日期:2007209207　　基金项目:国家自然科学基金资助项目(60675028)

　　作者简介:高健(19772),男,江苏南京人,博士研究生,主要研究方向为计算机视觉、机器人视觉导航([email protected]);黄心汉

(19462),男,湖北武汉人,教授,博导,主要研究方向为智能控制、信息融合;彭刚(19732),男,湖北武汉人,副教授,博士后,主要研究方向为嵌入式

系统;王敏(19542),女,湖北武汉人,教授,主要研究方向为模式识别;吴祖玉(19802),男,湖北天门人,博士研究生,主要研究方向为机器人定位与地图构建.

・2214・计算机应用研究　第25

卷

述,并将γ规格化导数操作引入尺度空间。他指出当γ=1时,规格化后的导数具有尺度不变性。也就是图像中某一点的σd9xL(X;t)的值不会因尺度的改变而变化。在实际的尺度不变特征点提取中,先通过图像与一系列按指数分布的σ值(σ=

n

kσ0,σ0为起始尺度)的高斯核卷积生成尺度空间,再对各层d

性的影响。从连续图像的角度来看,金字塔结构并没有改变规格化导数函数原有的位移不变性、各向同性和尺度不变性。但数字图像中采样过程不可避免地要发生混叠现象。金字塔结构中的抽样操作和一些近似处理也会对特征点的鲁棒性产生进一步的影响。在同样标准差和同样分层的情况下,采用金字塔结构所提取的特征点的鲁棒性会差于采用原尺度空间结构,采用简化后的结构会差于简化前的结构,但是却可以通过增加非完整金字塔结构的级数和层数来缩小这个差距。1　特征点提取

:a)利用高斯卷;);c)在高(包括同层的八邻域点、上层对)内取得极值并大于阈值的像素点为特征点;d)确定特征点的位置、尺度和方向。其中特征点的尺度为对应尺度空间图像层的尺度大小,特征点方向角度的计算依照SIFT的计算方法进行。

图像各个像素求得相应规格化的各向同性的导数的函数值。在尺度空间局部邻域中取得极值的像素点被选为特征点。这样就保证了所提取特征点对图像变化的鲁棒性。1　尺度空间结构分析

对于数字图像而言,其在xy空间上的采样已经确定。特征点提取算法所能改变的是尺度空间中在尺度方向上的采样。具有较大影响。采样间隔越短,,增加。

如前所述,,并且尺度系数越大,高斯卷积模板就越大,所需要的计算时间也就越长。在实际计算中,每层尺度图像并不是直接通过原始图像的高斯卷积生成,而是由下一层图像的高斯卷积获得,也就是

L(X;t2)=G(t2-t1)3L(X;t1)。另一方面,也可以根据高斯

　特征向量的计算与匹配

在提取特征点并确定其位置、尺度和方向后,需要利用描述子计算特征点的特征向量,以进行特征点的匹配。对于遮挡等现象,局部特征比全局特征具有更强的适应能力。因而,对特征点的描述主要采用局部特性。在文献[10]对多种描述子进行了实验对比,得出基于SIFT的一类描述子具有最佳性能的结论。

如图4所示,SIFT描述子由多个子区域组成,每个子区域分为16个采样区。描述子在与特征点对应的尺度层图像上计算特征向量,以特征点为中心,并旋转其方向与特征点的方向一致。在划分好各个子区域和采样区之后,需要计算各采样区的梯度幅值和梯度方向,从而形成每个子区域的八梯度方向的直方图。直方图中各向量的大小由对应梯度方向的采样区的梯度幅值累加而成。为了消除直方图中的边界效应,首先确定与采样区梯度方向相邻的直方图中的两个方向向量,再根据梯度方向与这两个方向向量中心值的偏离距离将采样区的梯度幅值分散累加到这两个方向向量中。这样,每个子区域就形成了一个8维的特征向量。为了减少描述子偏移带来的影响,各个采样区的梯度幅值还需要进行方差为描述子一半宽度的高斯平滑,以突出靠近特征点采样区所占的比重而减少远离特征点采样区所占的比重。同时,为了减少光照变化对梯度幅值的影响,特征向量还需要进行归一化处理。图4为2×2的结构形式。Lowe在文献[5]中推荐使用4×4的结构形式,而对于

4×4结构的描述子,就会形成一个128维的特征向量

。

卷积的性质,将二维卷积化为一维卷积来计算。但是尺度空间的生成依然需要大量的计算时间和存储量。因而,尺度上的采样间隔和采样深度均会受到实时性要求的限制。

为了减少计算量和存储量,SIFT算法将图像金字塔引入尺度空间,采用了一种如图2所示的金字塔结构

[5]

:整个结构

分为高斯金字塔和高斯残差金字塔两个部分。由高斯金字塔求高斯残差,由高斯残差金字塔提取特征点。金字塔分为多

级,一级分为多层,每层之间的σ值相差k倍。如果每级有r层图像需要提取特征点,则高斯残差金字塔各级需要计算r+

2层。由于高斯残差金字塔由对应相邻的高斯金字塔中的两

层相减获得,高斯金字塔需要计算r+3层。此外,高斯金字塔σ0)通过抽样获得上一级的第每级取第r+1层(标准差对应kr

一层,再由高斯卷积获得各层图像。采用这种结构时,特征点只是在每级的中间r层中产生。每级的底层和顶层并不提取特征点,只是分别用于尺度方向上下层的极值比较中

。

为了进一步减少计算量,本文采用了一种简化的SIFT金字塔结构。如图3所示,与简化前相比,简化后的SIFT金字塔每级的顶层被删除。在这种结构中,每级的底层依然不提取特征点,只是用于与第二层规格化导数的极值比较中。由于缺少了原SIFT金字塔的顶层,简化前的每级的最顶上两层的极值比较就无法直接进行。考虑到上一级第一层是由本级第r+1层抽样获得,简化后的结构用上一级的第一、第二层的对应像素的比较代替简化前的结构中最顶上两层间的对应像素比较,从而在每一级上减少了一次高斯卷积过程。

笔者在文献[9]中已经分析了金字塔结构对特征点鲁棒

文献[5]并没有对采样区的选取进行详细的说明。如果

第7期高　健,等:一种简化的SIFT图像特征点提取算法・22　　　15・

选取单个像素点作为采样区,那么采样区和子区域的大小对于各层尺度层图像都是固定的。这样的描述子就不具有尺度不变的特性。要使描述子具有尺度不变性,其尺寸大小必须要与对应尺度成比例。所以采样区的宽度也要与对应尺度成比例,并且对应不同尺度层图像的描述子所包含的像素点的个数也不一样。这样,如何计算各采样区的梯度幅值和梯度方向是需要解决的问题。

由以上分析可以看出,SIFT描述子中设置采样区的方法显得有点多余。本文简化了计算过程,取消了采样区的设置,而直接由子区域所包含像素点的梯度方向和梯度幅值来计算特征向量。为了保证尺度不变性,简化后的SIFT描述子的宽度依然与对应尺度成比例。为了增加描述子的鲁棒性,;,简化后的SIFT描述子计算上更简单,计算量也有所减少,但是性能却没有下降。第3章的实验结果将给出详细的比较。

分别对两幅图像提取特征点并计算了各个特征点的特征向量之后,就可以进行特征点的匹配。两幅图像中两个最相近的特征向量所对应的特征点组成一个匹配点对。SIFT特征向量的匹配采用的是欧式距离,并且通过计算与最相近的两个特征向量的距离的比值来判断是否匹配。这种方法可以取得比直接设置距离阈值更好的效果。匹配后的点对还是可能存在错误的匹配,这可以通过RANSAC算法作进一步的筛查。

对SIFT金字塔结构的简化对照明改变和图像噪声条件下的重复率影响较小,对图像旋转条件下的重复率有所影响,而对尺度变化后的重复率影响比较明显。但是可以通过增加金字塔的采样频率和采样深度来缩小这个差距。

SDet2就是在SDet1的基础上增加了一级、每级增加了两层。它在某些方面上的性能已经超越了SIFT。表2给出了三种特征点检测器在IntelP4

310GHzCPU的条件下计算一幅

320×240像素图像所需时间

的平均值。从表中可以看出,简化后的SIFT金字塔结构减少了计算量和计算时间,。

表1　3倍°方差为4的高斯噪声图像放大113倍以上四种变化综合

[**************]SDet[***********]184SDet[***********]146ms

SDet98

%

表2　特征点检测器的检测时间

SIFT297

SDet175

　　表2给出了SIFT描述子和简化的SIFT描述子所计算的特征向量在多种图像变化条件下的匹配鲁棒性比较。其中,第一列显示了五种图像变化条件;第二三列分别显示了SIFT描述子在这五种变化条件下的匹配率和错误匹配率;第四五列分别显示了简化的SIFT描述子在这五种变化条件下的匹配率和错误匹配率。从中可以看出简化后的SIFT描述子与简化前相比,在性能上并没有明显的差异。本文用计算1000个特征点的特征向量所需要的计算时间来比较SIFT描述子在简化前后的实时性能。SIFT描述子在简化前计算1000个特征点所需

　实验结果与分析

本文使用重复率

[5]

来评价特征点检测器的鲁棒性。也就

时间为339ms,简化后为267ms。这也是在IntelP43.0GHz

CPU的条件下统计获得。可以看出简化后的SIFT描述子在实

是先对原始图像和其变形图像分别计算特征点,求两幅图像中重复特征点的数量与这两幅图像分别提取的特征点数量的最小值的比值作为重复率。笔者预先知道图像变形的相关系数,这样就可以得到原始图像中的像素点在变形图像中的对应像素点。实际计算中,两幅图像提取的特征点是很难准确对应的。因此,当两幅图像中位置误差小于115×2(l为特征点所

在的级数,最低级为0)个像素,尺度误差小于21/2σ,方向角误差小于15°的两个特征点就被认为是对应重复特征点。对于描述子性能的评价,本文采用的是文献[10]中所定义的匹配率和错误匹配率。匹配率是指通过描述子计算匹配成功的特征点对数量与前面所求得的重复特征点对数量的比值。错误匹配率则是错误匹配的点对数量与描述子计算匹配的总点对数量的比值。错误匹配的判断依然采用以上计算重复率时确定的重复点对的标准。同时为了增加数据的可靠性,笔者选取了100幅实际场景图像分别计算,再作统计求平均值作为最终实验结果进行比较。

表1给出了几种算法所提取特征点的在多种图像变化条件下的鲁棒性比较。SIFT表示σ0=21/2,k=21/2,m=2,高斯金字塔每级的层数p取0～4,j取0～3的SIFT特征点检测器。SDet1表示简化后的SIFT特征点检测器,其σ0、k、m和j与

SIFT相同,只是p取0～3。SDet2的算法与SDet1相同,只是k=2

1/4

l

时性上有所改善。

表3　描述子的匹配率和错误匹配率

图像变化照明增加113倍图像旋转15°方差为4的高斯噪声图像放大113倍以上四种变化综合

SIFT(r)[**************]79.06SIFT(e)[**************]3SDes(r)[***********][***********]%

SDes(e)

　　图5显示了三种算法对两幅图像的特征点匹配结果。其

中:(a)为SIFT算法匹配了101个点对,并由RANSAC算法剔除了9个错误匹配;(b)为SDet1+SDes算法匹配了91个点对。其中85个匹配正确,这个算法虽然匹配成功的特征点对比SIFT少,但是其在实时性上有所增强;(c)为SDet2+SDes算法匹配了124个点对,其中123个匹配正确,与前两种算法相比,该算法检测出的正确匹配点对最多。

,p取0～5,j取0～4。表1中的第一列显示了五种图像

(下转第2222页)

变化条件;第二～四列分别显示了在这五种变化条件下的

SIFT、SDet1和SDet2提取特征点的重复率。从表中可以看出,

・2222・计算机应用研究　

　　Springer2Verlag,2005:124521254.

第25

卷

习对和一个距离判据单元,然后通过类内期望输出和类间期望

距离来修正该网络,最后给出一组实例样本进行表情分类识别。实验结果表明,该算法使识别率有了显著提高,平均正确识别率达到93%,虽然这一结果离现实应用还有一定的距离,但对问题的最终解决应有较好的促进作用

。

[8]KRUEGERV,SOMMERG.Gaborwaveletnetworksforobjectrepre2

sentation[J].JournaloftheOpticalSocietyofAmerica,2002,19(6):111221119.[9]LIUC,WECHSLERH.

2003,14(4):9192928.

[10]GHIJSENM,HEYLEND,NIJHOLTA,etalFacialaffectdisplays

duringtutoringsessions[C]//ProcofInternationalConferenceonIn2telligentUserInterfaces.SanDiego,CA:[s.n.],2005.

[11]RUMELHARTDE,HINTONGILLIAMSRJ.Learningrepresen2

tationsback2Nature,1986,323:5332536.[books[M].NewYork:Henry

andIndependentcomponentanalysisofGabor

featuresforfacerecognition[J].IEEETransonNeuralNetworks,

未来工作中,,问题有待进一步研究,工作者关注的问题,,表情识别的研究与应用会得到不断扩展。参考文献:

[1]EKMANP,FRIESENWV.Facialactioncodingsystem[M].PaloAl2

to:ConsultingPsychologistsPress,1978.

[2]高文,金辉.面部表情图像的分析与识别[J].计算机学报,

1997,20(9):7822789.

[3]TURKM,PENTLANDA.Eigenfacesforrecognition[J].Cognitive

Neuroscience,1991,3(1):71286.

[4]PADGETTC,COTTRELLG.Identifyingemotioninstaticfaceima2

ges[C]//Procofthe2ndJointSymposiumonNeuralComputation:SanDiego:UniversityofCalifornia,1995:912101.

[5]LANITISA,TAYLORC,COOTEST.Aunifiedapproachtocoding

andinterpretingfaceimages[C]//Procofthe5thInternationalCon2ferenceonComputerVision(ICCV’95).1995:3682373.

[6]WONGJia2jun,CHOSY.Facialemotionrecognitionbyadaptive

processingoftreestructures[C]//ProcofACMSymposiumonAp2pliedcomputing.2006:23230.

[7]CHOSY,WONGJia2jun.Probabilisticbasedrecursivemodelforface

recognition[R]//LectureNotesinComputerScience3641.[S.l.]:(上接第2215页)

[]R.Statisticalnon2uniformsamplingofGaborwavelet

coefficientsforfacerecognition[C]//IEEEIntConfonAcoustics,Speech,andSignalProcessing.Philadelphia:[s.n.],2005.[14]DUCHW,Neuralminimaldistancemethods[C]//Procofthe3rd

ConferenceonNeuralNetworksandTheirApplications.Kule:[s.n.],1997:1832188.

[15]RUMELHARTDE.Learninginternalrepresentationbyerrorpropa2

gation[M].[S.L.]:MITPress,1986:3182362.

[16]MICHAELJL,BUDYNEKJ,KAMATSUS.Automaticclassification

ofsinglefacialImages[J].IEEETransonPatternAnalysisandMachineintelligence,1999,21(12):135721362.

[17]BELHUMEURPN,HESPABNHAJP,KRIENGMANDJ.Eigen2

facesvs.fisherfaces:recognitionusingclassspecificlinearprojection[J].IEEETransonPatternAnalysisandMachineIntelligence,1997,19(7):7112720.

[18]COHENI,GARGA,HUANGT.Emotionrecognitionfromfacialex2

pressionsusingmultilevelHMM[C]//ProcofNeuralInformationPro2cessingSystems,Workshop.2000.

[19]KAPOORA,PICARDR.Multimodalaffectrecognitioninlearning

environments[C]//ProcofMultimedia.Singapore:[s.n.],2005.[20]PADGETTC,COTTRELLG,ADOLPHSR.Categoricalperception

infacialemotionclassification[C]//Procofthe18thAnnualConfer2enceoftheCognitiveScienceSociety.Hillsdale,NJ:LawrenceErl2baumAssociates,1996.

sionandPatternRecognition.2003:7362743.[4]

JOHANSSONB,MOEA.Patch2dupletsforobjectrecognitionandposeestimation[C]//Procofthe2ndCanadianConferenceonCom2puterandRobotVision.2005:9216.

[5]LOWEDG.Distinctiveimagefeaturesfromscaleinvariantkeypoints[J].

InternationalJournalofComputerVision,2004,60(2):912110.[6]BROWNM,LOWEDG.Recognisingpanoramas[C]//Procofthe

9thInternationalConferenceonComputerVision.Nice:[s.n.],2003:121821225.

[7]SES,LOWEDG,LITTLEJJ.

andmappingformobilerobots[J].2005,21(3):3642375.

[8]LINDEBERGT.Featuredetectionwithautomaticscaleselection[J].

InternationalJournalofComputerVision,1998,30(2):792116.[9]

GAOJian,HUANGXin2han,PENGGang,etal.Aquickfeaturedetectingmethodappliedinrobotvision[C]//ProcofIEEEInterna2

Indexingbasedonscaleinvariant

tionalConferenceonMechatronicsandAutomation.[s.n.],2007:7362743.

[10]SCHMIDC,MOHRR,BAUCKHAGEC.Comparingandevaluating

interestpoints[C]//Procofthe6thInternationalConferenceonComputerVision.1998:2302235.

Haerbin:

Vision2basedgloballocalizationIEEETransonRobotics,

　结束语

理论分析和实验结果表明,本文所提出简化的SIFT特征点提取算法可以在保证性能的同时提高算法的实时性。虽然改变SIFT金字塔结构带来的误差会影响所提取特征点的鲁棒性,但是可以通过减少采样间隔和增加采样深度在一定程度上提高算法的性能。而对描述子结构的修改不仅没有影响原有的性能,还简化了计算过程。因而,这种简化算法比较适合于立体视觉匹配等对算法实时性要求较高的图像处理领域中。参考文献:

[1]HARRISC,STEPHENSM.Acombinedcornerandedgedetector

[C]//Procofthe4thAlveyVisionConference.Manchester:[s.n.],1988:1472151.

[2]MIKOLAJCZYKK,SCHMIDC.

interestpoints[C]//Procofthe8thInternationalConferenceonComputerVision.Vancouver:[s.n.],2001:5252531.

[3]CARNEIROG,JEPSONAD.Multi2scalephase2basedlocalfeatures

[C]//ProcofIEEEComputerSocietyConferenceonComputerVi2