sift特征匹配算法研究

《sift特征匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

SIFT特征匹配算法研究第20卷第2期2007年06月盐城工学院(自然科学版)JournalofYanchengInstituteofTechnologyNaturalScienceEditionVo1.20No.2Jun.2007SIFT特征匹配算法研究王国美,陈孝威(贵州大学计算机科学与技术学院,贵州贵阳550025)摘要:SIFT特征匹配算法是目前特征匹配研究领域的热点,其匹配能力较强,可以处理图像间发生平移,旋转,仿射变换的匹配,对任意角度拍摄的图像也具备较稳定的特征匹配能力.实验结果表明,该算法具有较强的匹配能力和鲁棒性,是一种较好的特征匹配算法.关键词:虚拟现实;特征匹配;图像拼接;全景图中图分类号:TP37文献标识码:A文章编号:1671—5322(2007)02—0001—05图像匹配是虚拟现实,计算机视觉等领域的一个研究热点.目前,有关研究人员对图像匹配技术进行了大量的研究,提出了很多匹配算法:有基于面积的方法…,有基于比值的方法-2J,有相位相关算法-3等等,但是这些匹配算法都有一个共同点:图像间的焦距要一致,不能有尺度缩放,旋转不能太大,变形不能太明显,还有光照变化,仿射变换等等方面受到限制.随着图像技术和计算机技术的发展,出现了基于特征的图像匹配技 术.这种技术的优点是能处理具有不同特性的图像和图像间变形复杂的情况.缺点是特征的检测困难,算法稳定性较差.针对特征匹配算法存在的不足,经过计算机视觉多年的发展,特征提取技术越来越稳定,特别是尺度空间的特征检测器甚至可以稳定地对两幅位移很大的图像进行准确的特征检测和匹配.在基于特征的匹配技术中,其首要任务是提取稳定的特征,并进行描述.常用的方法有基于空间关系的匹配算法,基于不变量描述子的匹配算法,金字塔,和小波算法等等.其中文献[5]提出的SIFr(ScaleInvariantFeatureTransfo1TI1即尺度不变特征变换)特征匹配算法是目前国内外特征匹配研究领域取得比较成功的一种算法,该算法匹配能力较强,能提取稳定的特征,可以处理两幅图像之间发生平移,旋转,仿射变换,视角变换,光照变换情况下的匹配问题,甚至在某种程度上对任意角度拍摄的图像也具备较为稳定的特征匹配能力,从而可以实现差异较大的两幅图像之间的特征的匹配.本文在研究以上各种匹配算法的基础上,对匹配能力较强,适用范围较大的sIFr特征变换匹配算法进行比较详细和深入的介绍,并用Mat—lab7.0实现了该算法.1SIFT特征匹配算法siFr特征匹配算法是DavidG.1_~we在2004年总结了现有的基于不变量技术的特征检测方法的基础上,提出的一种基于尺度空间的,对图像缩放,旋转甚至仿射变换保持不变性的特征匹配算 法.siFr特征是图像的局部特征,该特征对旋转,尺度缩放,亮度变化保持不变性,对视角变化,仿射变换,噪声也保持一定程度的稳定性.siFr特征匹配算法分两个阶段来实现:第1阶段是siFr特征的生成,即从多幅待匹配图像中提取出对尺度缩放,旋转,亮度变化无关的特征向量;第2阶段是siFr特征向量的匹配.1.1SIFT特征向量的生成在生成SIFT特征向量之前,先对图像进行规收稿日期:2006—12—21基金项目:国家教育部春晖计划基金(200203)作者简介:王国美(1975一),女,贵州遵义市人,博士研究生,主要研究方向为虚拟现实技术,多媒体技术.盐城工学院(自然科学版)第20卷一化处理,然后扩大图像为原来的两倍,预滤波剔除噪声,得到高斯金字塔的最底层即第1阶的第1层.一幅图像SIFT特征向量的生成算法总共包括4步.1.1.1尺度空间极值检测尺度空间理论最早出现于计算机视觉领域,当时其目的是模拟图像数据的多尺度特征.随后Koendetink利用扩散方程来描述尺度空间滤波过程,并由此证明高斯核是实现尺度变换的唯一变换核引.Lindeberg[,Babaud[.等人通过不同的推导进一步证明高斯核是唯一的线性核.因此,尺度空间理论的主要思想是利用高斯核对原 始图像进行尺度变换,获得图像多尺度下的尺度空间表示序列,对这些序列进行尺度空间特征提取.二维高斯核的定义如公式(1)所示,其中代表了高斯正态分布的方差:G(,,)=e舻)/(1)1T对于二维图像,(,Y),在不同尺度下的尺度空间表示(,y,)可由图像,(,Y)与高斯核G(,Y,)的卷积得到,如公式(2)所示:L(,Y,)=G(,Y,)×,(,Y)(2)在公式(2)中,￡表示尺度空间.(,Y)代表图像,上的点.是尺度因子,其值越小则表征该图像被平滑得越小;其值越大则表征该图像被平滑得越大.大尺度对应于图像的概貌特征,小尺度对应于图像的细节特征.因此,选择合适的尺度因子平滑是建立尺度空间的关键.在这一步里面,主要是建立高斯金字塔和DOG(DifferenceofGaussian)金字塔,然后在DOG金字塔里面进行极值检测,以初步确定特征点的位置和所在尺度.(1)建立高斯金字塔为了得到在不同尺度空间下的稳定特征点,将图像(,Y)与不同尺度因子下的高斯核G(,y,17")进行卷积操作,构成高斯金字塔.高斯金字塔有O阶,一般选择4阶,每一阶有s层尺度图像,s一般选择5层.高斯金字塔的构成如图1所示.在高斯金字塔的构成中要注意,第1阶的第 1层是放大2倍的原始图像,其目的是为了得到更多的特征点;在同一阶中相邻两层的尺度因子比例系数是k,则第1阶第2层的尺度因子是ko",k6口皇薯r第5珐第矿d昌墨第4层k40-冒-m-----第3g-F第2层第J}3然后其它层以此类推则可;第2阶的第1层由第一阶的中间层尺度图像进行子抽样获得,其尺度因子是,然后第2阶的第2层的尺度因子是第1层的k倍即k3.第3阶的第1层由第2阶的中间层尺度图像进行子抽样获得.其它阶的构成以此类推.(2)建立DOG金字塔DOG即相邻两尺度空间函数之差,用D(,Y,)来表示,如公式(3)所示:D(,Y,)=(G(,Y,)一G(,Y,))×,(,Y)=(,Y,j})一(,Y,)(3)DOG金字塔通过高斯金字塔中相邻尺度空间函数相减即可,如图2所示.在图中,DOG金字塔的第1层的尺度因子与高斯金字塔的第1层是一致的,其它阶也一样.J}3高斯DOG图2DOG金字塔Fig.2DOGpyramidJ}3 (3)DOG空间的极值检i贝0在上面建立的DOG尺度空间金字塔中,为了检测到DOG空间的最大值和最小值,DOG尺度第2期王国美等:SIFt特征匹配算法简介?3?空间中中间层(最底层和最顶层除外)的每个像素点需要跟同一层的相邻8个像素点以及它上一层和下一层的9个相邻像素点总共26个相邻像素点进行比较,以确保在尺度空间和二维图像空间都检测到局部极值,如图3所示.尺度图3尺度空间极值检测Fig.3Detectionofscale—spacee~rema在图3中,标记为叉号的像素若比相邻26个像素的DOG值都大或都小,则该点将作为一个局部极值点,记下它的位置和对应尺度.1.1.2精确定位特征点位置由于DOG值对噪声和边缘较敏感,因此,在上面DOG尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点.下面对局部极值点进行三维二次函数拟和以精确确定特征点的位置和尺度,尺度空间函数D(,Y,)在局部极值点(.,Y.,or)处的泰勒展开式如公式(4)所示.)Xo,Yo,o.o)+簪+(4)其中,y,,=aD OX2——aD缸aDOyxaDOo.xOD'aODOyODOo.一aDOxyaDOy2aDOo.yaOxo.aDOyo.aD0o.202D(Dx+,y.一D)一(D一D)a一4(k一当前层,k一1一下层,k+1一上一层)azD(一D"X+.l¨一::)一(一DX一+.l¨～D::) ——————广————一i公式(4)中的一阶和二阶导数是通过附近区域的差分来近似求出的,列出其中的几个,其它的二阶导数以此类推.通过对公式(4)求导,并令其为O,得出精确的极值位置,如公式(5)所示:=一()(5在上面精确确定的特征点中,同时要去除低对比度的特征点和不稳定的边缘响应点,以增强匹配稳定性,提高抗噪声能力.去除低对比度的特征点:把公式(5)代到公式(4)中,只要前两项,得到公式(6):D(X一)=D+(6)通过式(6)计算出D(),若ID()I≥O.O3,则该特征点就保留下来,否则就丢弃.去除不稳定的边缘响应点:海森矩阵如公式(7)所示,其中的偏导数是上面确定的特征点处的偏导数,它也是通过附近区域的差分来近似估计的.日=DxyDyyy1I(7)L通过2×2的海森矩阵日来计算主曲率,由 于D的主曲率与日矩阵的特征值成比例,根据文献[5],不具体求特征值,求其比例ratio.设a是最大幅值特征,卢是次小的,r=百Ot,则rati.如公式(8)所示.Tr(H)=D+D,=+卢Det(H)=DD一(D):qprat:=㈣通过公式(8)求出ratio,常取r=10,若mtio≤,则保留该特征点,否则就丢弃.1.1.3确定特征点主方向利用特征点邻域像素的梯度方向分布特性为每个特征点指定方向参数,使算子具备旋转不变性.m(,Y)=+1,Y)～一1,y)+,Y+1)一,Y-1)盐城工学院(自然科学版)第2O卷(,Y)=tan(((,Y+1)一(,Y一1))/((+1,Y)一(一1,y))(9)公式(9)为(,Y)处的梯度值和方向.为所用的尺度为每个特征点各自所在的尺度,(,y)要确定是哪一阶的哪一层.在实际计算过程中,在以特征点为中心的邻域窗口内采样,并用梯度方向直方图统计邻域像素的梯度方向.梯度直方图的范围是0.一360.,其中每1O.一个柱,总共36个柱.梯度方向直方图的峰值则代表了该特征点处邻域梯度的主方向,即作为该特征点的方向.在梯度方向直方图中,当存在另一个相当于 主峰值80%能量的峰值时,则将这个方向认为是该特征点的辅方向.一个特征点可能会被指定具有多个方向(一个主方向,一个以上辅方向),这可以增强匹配的鲁棒性.通过上面的3步,图像的特征点已检测完毕,每个特征点有3个信息:位置,对应尺度,方向.1.1.4生成SIFT特征向量首先将坐标轴旋转为特征点的方向,以确保旋转不变性.接下来以特征点为中心取8×8的窗口(特征点所在的行和列不取).在图4(a)中,中央黑点为当前特征点的位置,每个小格代表特征点邻域所在尺度空间的一个像素,箭头方向代表该像素的梯度方向,箭头长度代表梯度模值,图中圈内代表高斯加权的范围(越靠近特征点的像素,梯度方向信息贡献越大).然后在每4×4的图像小块上计算8个方向的梯度方向直方图,绘制每个梯度方向的累加值,形成一个种子点,如图4(b)所示.此图中一个特征点由2×2共4个种子点组成,每个种子点有8个方向向量信息,可产生2×2×8共32个数据,形成32维的SIFT特征向量即特征点描述器,所需的图像数据块为8×8.这种邻域方向性信息联合的思想增强了算法抗噪声的能力,同时对于含有定位误差的特征匹配也提供了较好的容错性.实际计算过程中,为了增强匹配的稳健性,文献[5]建议对每个特征点使用4x4共16个种子点来描述,每个种子点有8个方向向量信息,这样对于一个特征点就可以产生4x4×8共128个数 据,最终形成128维的SIFT特征向量,所需的图像数据块为16×16.此时SIFT特征向量已经去除了尺度变化,旋转等几何变形因素的影响,再继T一./ItT≯,,,t?▲一t●J/'-.●/,',P0,●,●a图像梯度r犬一b特征点描述器图4图像梯度及特征点描述器Fig.4Theimagegradientsandkeypointdescriptor续将特征向量的长度归一化,则可以进一步去除光照变化的影响.当两幅图像的SIFT特征向量即特征描述器生成后,下一步就是进行特征向量的匹配.1.2SIFT特征向量的匹配首先,进行相似性度量.一般采用各种距离函数作为特征的相似性度量,如欧氏距离,马氏距离等. 通过相似性度量得到图像间的潜在匹配.本文中采用欧氏距离作为两幅图像间的相似性度量.获取SIFT特征向量后,采用优先k—d树进行优先搜索来查找每个特征点的2近似最近邻特征点.在这两个特征点中,如果最近的距离除以次近的距离少于某个比例阈值,则接受这一对匹配点.降低这个比例阈值,SIFT匹配点数目会减少,但更加稳定.其次,消除错配.通过相似性度量得到潜在匹配对,其中不可避免会产生一些错误匹配,因此需要根据几何限制和其它附加约束消除错误匹配,提高鲁棒性.常用的去外点方法是RANSAC随机抽样一致性算法,常用的几何约束是极线约束关系.第2期王国美等:sIFT特征匹配算法简介?5?2实验结果及分析本文采用Matlab7.0实现上述算法.首先提取SIFT特征,然后再进行特征匹配.在图5中,a和b为原始图像,在拍摄时进行了相机平移,转动和变焦操作;c,d分别为第1,第2幅图像中检测出的SIFT特征,用箭头来表示,箭头的起点代表(a)originalimage1(原始像l1特征点的位置,箭头的长度代表该特征点所在的尺度,箭头的方向代表该尺度下特征点所处领域的主梯度方向;e是特征匹配的结果.从图中可看出,尽管两幅图像有旋转,缩放及亮度等变换,但两幅图像中找到的SIFT特征匹配对,其位置信息,方向性和尺度信息是准确的. (b)originalimage2(原始图像2)(c)SIFTkeypointsinimagel(图像1中的sIFT特征)(d)SIFTkeypointsinimage2(图像2中的sIFT特征)fe)resultsoffeaturematching(特征配结果)图5实验结果Fig.5experiments.,后的研究中,希望在算法的实时性方面能够做出儿改进;在特征匹配方面,算法的实时性和特征匹配本文对基于特征的匹配算法做了较深入的研的准确度都有待于改进,在图像处理中,这仍然是究.在特征提取过程中,由于SIFT算法需要在各一个没有完全解决的问题,这将促使新的匹配方个尺度上进行计算,其时问复杂度相对较高,在今法不断出现,也是今后需要进一步研究的方面.参考文献:[1]汪成为.灵境(虚拟现实)技术的理论,实践及应用[M].南宁:广西科学技术出版社,1996.[2]钟力,胡小锋.重叠图像拼接算法[J].中国图像图形,1998(3):365—369.[3]KuglinCD,HinesDC.ThePhaseCorrelationImagealignmentmethod[C].IEEEConferenceonCyberneticsandSociety,NewYork,1975:163—165.[4]DavidGLowe.ObjectRecognitionfromLocalScale—InvariantFeatures[C].7thInternationalConferenceonComputerVi-sion,1999:1150—1157.(下转第l0页)?1O?盐城工学院(自然科学版)第20卷 参考文献:[1]吴茂念.广义Fibonacci数列几个前n项和式[J].贵州大学:自然科学版,2005(增刊):6—8.[2]吴茂念.广义Fibonacci数列一些前n项和式[J].贵州大学:自然科学版,2005(4):343—347.[3]宋卫星,杨巧梅."魔(n,k)方"与广义Fibonacci数列[J].数学通报,2001(4):41-43.[4]康士凯.斐波那契数列[M].上海:上海科技教育出版社,1992:41—49.[5]高山珍.Lucas数列的几个性质[J].贵州大学:自然科学版,2002(4):291—296.SomeFormalsofSumaboutGeneralFibonacciSequenceWUMao—nian(SchoolofScience,GuizhouUniversity,GuizhouGuiyang550025,China)Abstract:Thearticlehasdemonstratedanelementaryproofaboutthesumofthefirstnitemdifferencelessthan6ofthegeneral—izedFibonaeeisequence.Thus,thesulnofthefirstnitemdifferencelessthan6ofFibonaccisequence,Lucassequencecouldbeobtainedanditsnumericalvaluecouldbecalculatedbythegeneralformalsofthesesequences.Keywords:Fibonaeeisequence;Lucassequence;GeneralizedFibonacciSequence;thesumofthefirstnitem(上接第5页)[5]DavidGLowe.DistinctiveImageFeaturesfromScale—InvariantInterestPoints[J].InternationalJournalofComputerVi—sion,2004,60(2):91—110.[6]HarrisCStephens.ACombinedComerandEdgeDetector[J].4thAlveyVisionConference.1988,60(2):147—151.[7]FaugerasO,RobertL.WhatCantwoimagestellUSaboutthethirdone[C].ProceedingsoftheEuropeConferenceonGem?puterVision,Sweden,1994.[8]KoenderinkJ.Thestructureofimages[J].BiologicalCybernetics,1984,50:363—396. [9]LindebergT.scale—SpacefordiscreteSignals[J].IEEETransactionsPAMI,1980,207:187-217.[10]BabaudJ,WitkinAP,BaudinMeta1.UniquenessoftheGaussiankernelforscale—spacefiltering[J].IEEETransactionsonPaRemAnalysisandMaehineIntelligence,1996,8(1):26—33.StudyonaNawAlgorithmofFeatureMatching——SIFTWANGGuo—mei,CHENXiao—wel'(CollegeofComputerScienceandTechnology,GuizhouUniversity,GuizhouGuiyang550025,China)Abstract:Anewalgorithmoffeaturematching—SIFT(ScaleInvariantFeatureTransform)whichhasbecomeahottopicanddifficultresearchareaisintroduced.Atpresentthealgorithm,whosematchingabilityismorestrongandCandisposeofmatchingproblemwithtranslation,rotationandaffinedistortionbetweenimagesandtoacertainextentiswithmorestablefeaturematchingabilityforimageswhichaleshotfromrandomdifferentangles.Theexperimentsshowthatthealgorithmisofstrongermatchinga—bilityandrobustness,whichisabetterfeaturematchingalgorithm.Keywords:virtualreality;featurematching;imagemosaicing;panorama