Vol.37No.1
红外与激光工程InfraredandLaserEngineering
2008年2月Feb.2008
采用简化SIFT算法实现快速图像匹配
刘立
1,2
,彭复员1,赵坤1,万亚平
2
(1.华中科技大学电信系,湖北武汉430076;2.南华大学计算机科学与技术学院,湖南衡阳421001)
摘
要:SIFT(ScaleInvariantFeatureTransform)算子因其良好的尺度、旋转、光照等不变特性而广
泛应用于图像匹配中,但用128维向量来表征每个特征点降低了算法的实时性。为了提高匹配速度,介绍了一种基于SIFT的简化算法(SSIFT),采用基于圆形窗口的12维向量有效地表示一个特征点。实验结果显示,算法在保持较好匹配率的同时能降低时间复杂度,适合运用在对实时性要求较高的场合。
关键词:SIFT;
高斯差尺度空间;
尺度不变;
图像匹配
中图分类号:TP391.41
文献标识码:A
文章编号:1007-2276(2008)01-0181-04
SimplifiedSIFTalgorithmforfastimagematching
LIULi1,2,PENGFu!yuan1,ZHAOKun2,WANYa!ping2
(1.DepartmentofTelecommunication,HuazhongScienceandTechnologyUniversity,Wuhan430076,China;
2.DepartmentofComputerScienceandTechnology,NanhuaUniversity,Hengyang421001,China)
Abstract:Duetotheinvarianceofscale,rotation,illumination,SIFT(ScaleInvariantFeature
Transform)descriptoriscommonlyusedinimagematching.However,thefactthatthepresentationofonefeaturepointneeds128dimensionswillreducereal!timeefficiencyofthealgorithm.AsimplifiedalgorithmbasedonSIFT(SSIFT)isdevelopedtoexpressafeaturepointwithonly12dimensionsbasedonacircularwindowtoimprovetheefficiencyofmatching.Theexperimentalresultsshowthatthealgorithmcanreducetherateoftimecomplexityandmaintainarelativelygoodmatchingrateatthesametime,whichisfitforreal!timeprocessing.
Keywords:SIFT;
Gaussiandifferencescale!space;
Scaleinvariant;
Imagematching
0引言
图像匹配在众多视觉应用中是一个关键技术,匹
取和最小距离计算。Moravec等人采用角点算子来实现立体视觉匹配[2],在此基础上Harris等人对Moravec算子进行改进[3],Harris角点检测算子具有旋转不变以及缩放不变等许多优良性能,因此广泛应用在各种图像匹配算法中。如Schmid和Mohr采用Harris角点检测实现通用目标识别[4]等,但它对尺度、视角、照明变化比较敏感,而且抗噪声能力差[5]。1999年Lowe等人提出一种更加稳定的SIFT(ScaleInvariantFeature旋转、仿Transform)特征算子[6],该算子不仅具有尺度、
配算法直接影响后续视觉处理的效果。对于运动目标常采用光流等方法提取特征进行匹配,如王兆仲等人提出了一种利用光流确定图像运动场的高精度图像匹配算法[1]。对于静态目标主要采用点匹配方法,即给定同一场景的两幅图像,寻找同一场景点投影到图像中的像素之间的对应关系,主要步骤为图像特征点提
收稿日期:2007-04-10;修订日期:2007-06-01
基金项目:国家自然科学基金资助项目(60475024);航天技术创新基金资助项目(20060118)
作者简介:刘立(1971-),男,湖南衡阳人,博士,主要从事计算机视觉等方面的研究。Email:liulee@smail.hust.edu.cn
导师简介:彭复员(1945-),女,湖北武汉人,教授,博士生导师,主要从事水下图像与信号处理等方面研究。Email:pfuyuan@163.com
182
红外与激光工程第37卷
射、视角、光照不变性,对目标的运动、遮挡、噪声等因素也保持较好的匹配性。该算子目前已广泛应用于机器人定位和导航、地图生成[7]以及三维目标识别中[8]。
SIFT算子一个重要的特点是匹配点多而且稳定,这对于三维目标重建以及复杂目标识别比较有利,但它使用了128维向量来表示每个特征点,要处理的数据量大大增加,对于无需太多匹配点且实时性要求比较高的情况,存在一定的局限性,如目标初定位、机器人单目视觉测深等场合。文中在SIFT算法的基础上进行简化,对每个特征点只采用12维特征向量来表示,在降低部分匹配数量的同时,较大提高了计算机处理的实时性,实验还表明,文中介绍的算法在旋转不变性上优于原算法。
图1DoG尺度空间特征点检测
Fig.1DetectionoffeaturepointinGaussianspace
$(x,y)=arctan{[L(x,y+1)-L(x,y-1)]/[L(x+1,y)-L(x-1,y)]}(5)公式(4)、(5)为(x,y)处梯度的模值和方向公式。其中L所用的尺度为每个关键点各自所在的尺度。
实际计算时,在关键点为中心的邻域窗口内采样,并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0~,每10°代表一个方向,总共36个360°方向。直方图的峰值代表该特征点处邻域梯度的主方向,作为该关键点的方向。图2是采用7个方向时使用梯度直方图为特征点确定主方向的示例。
1SIFT算法
1.1图像的高斯尺度空间
尺度空间理论最早出现在计算机视觉中是为了模拟图像数据的多尺度特征,“尺度空间”概念是著名的“图像金字塔”概念的补充,Koenderink与Lindeberg的研究表明唯一可能的线型尺度核就是高斯核[9]。
一幅图像的尺度空间被定义为函数L(x,y,σ),它是尺度变化的高斯函数G与图像I的卷积:
图2建立特征点方向
L(x,y,σ)=G(x,y,σ)*I(x,y)
-(x+y)/2!
G(x,y,σ)=12e
2\"!
2
2
2
(1)(2)
Fig.2Toestablishtheorientationoffeaturepoint
(3)生成SIFT特征向量,将坐标轴旋转到特征点方向,以保证旋转不变性。然后,以关键点为中心取8×
式中:(x,y)为像素坐标;σ为尺度空间因子;L为尺度空间。σ大小决定图像的平滑程度,大尺度对应图像的概貌特征,小尺度对应图像的细节特征。
8的窗口。图3(a)的中央黑点为当前关键点的位置,
1.2SIFT特征匹配算法
Lowe提出的SIFT算法主要包括4个步骤:(1)尺度空间极值检测。首先建立图像的DOG(Difference#of#Gaussian)金字塔,在DOG尺度空间中的26个领域中检测极值,D(x,y,σ)是两个相邻尺度图像之差,即:
(a)
(b)
图3由特征点邻域梯度信息生成特征向量
Fig.3CreatingSIFTdescriptorfromthegradient
D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*I(x,y)=
L(x,y,k!)-L(x,y,!)
(3)
informationofneighbourhood
每个小格代表关键点邻域所在尺度空间的一个像素,利用公式(4)、(5)求得每个像素(i,j)的梯度幅值mi,j与梯度方向θi,j,箭头方向代表该像素的梯度方向,箭头长度代表梯度模值,然后用高斯窗口对其进行加权运算,每个像素对应一个向量,长度为G(σ′,i,j)*mi,j,
一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时,就认为该点是图像在该尺度下的一个特征点,如图1所示。
(2)利用关键点邻域像素的梯度方向分布特性,为每个关键点指定方向参数,使算子具备旋转不变性。
G(σ′,i,j)为该像素点的高斯权值,方向为θi,j,图中圆圈代表高斯加权的范围,根据参考文献[5]高斯参数
m(x,y)=!(L(x+1,y)-L(x-1,y))+(L(x,y+1)-L(x,y-1))(4)
22第1期
刘立等:采用简化SIFT算法实现快速图像匹配183
取3倍特征点所在的尺度,即3σ。每个向量在2×σ′2的子窗口范围内投影到8个梯度方向上,绘制每个梯度方向的累加值,即可形成一个8维向量,如图3(b)所示。Lowe在实际应用中采用4×4个小窗口,这样每个特征点就用128维向量来表征。最后对特征向量规一化,去除光照影响。
当两幅图像的SIFT特征向量生成(4)特征匹配。
后,就采用欧式距离来作为两幅图像中关键点的相似性判定度量,当此距离小于某个阈值时就认为这两个点已匹配上。
d6,d7,d8,d9,d10,d11,d12),否则转4)。
4)向左循环移动整个向量序列,直到最大的梯度方向统计量移动到向量的第一个元素,以保证旋转不变性。假设d5是向量的最大元素,则最终特征向量为:
!D=(d5,d6,d7,d8,d9,d10,d11,d12,d1,d2,d3,d4)(3)特征匹配
为了保证稳定的匹配效果,在原算法上增加一次匹配,第一次匹配时记录下匹配的坐标对,然后交换匹配的图像顺序,再匹配一次,当两次匹配的坐标相同时完成匹配,实验表明两次匹配能较大地提高匹配的稳定性。
2简化算法
2.1算法描述
实验表明,步骤(3)在整个算法中占用80%以上的计算时间,严重影响算法的实时性。同时在步骤(2)和步骤(3)中做了类似的方向直方图统计工作,为了提高算法的实时性,将这两个步骤合并,并只采用12维向量表征特征点。具体改动如下:
2.2维数设定
本算法中最关键的参数就是圆形统计窗口中向量对50幅不同类型的图像进行统计,发现随着的维数n。
n的增大匹配率增加,但运算时间也大大增加,同时,当n>12时匹配率并无明显提高,如图5所示,其中(a)为正确匹配率,(b)为计算时间,(c)为匹配效率,通过选取最大匹配效率来决定维数。匹配效率定义为:
匹配效率=正确匹配率
计算时间(1)尺度空间极值检测(同原算法)(2)形成特征向量
1)在多尺度空间特征点形成之后,以特征点为中心采用圆形窗体来确定需要统计的邻域范围(见图,因此圆形窗口4),窗口尺寸采用Lowe推荐的9σ×9σ半径取4.5σ,在该圆形窗体内统计12个梯度方向。
(7)
图4圆形统计窗口
Fig.4Circularstatisticswindow
2)将这12个梯度方向规一化,保证光照不变性。假设D是特征点的特征向量,即D=(d1,d2…,d12),归一化后得到:
!D=
D
#\"d
i=1
12=(d1,d2…,d12)
2i
(6)
3)查找最大的梯度方向统计量,如果该统计量元素位于12维向量的头部则向量最终形成,即若d1=
图5维数设定
Fig.5Dimensionassignmentonmatchingtask
D},最终特征向量为!D=(d1,d2,d3,d4,d5,max{di,di∈!
从图中看出,当n=12时获得最大匹配效率。
184
红外与激光工程第37卷
3实验结果
本实验环境参数如下:
4结论
简化算法在复杂环境下匹配效率不如原算法,但匹配时间大大缩短,有利于视觉处理的实时性,同时在目标旋转不变性上具有一定的优势。对于视角变化不大、匹配数量要求不高的场合,如单目视觉测距、机器人目标抓取初定位等情况下,文中算法的实时性特点比较突出。但本算法与原算法存在同样缺陷,即在相似环境或对称环境下匹配正确率明显下降[10],如何在向量中加入全局元素提高匹配正确率是下一步工作的重点。参考文献:
[1]
WANGZhao!zhong,ZHOUFu!gen,LIUZhi!fang,etal.Imagematchingalgorithmwithhighprecision[J].InfraredandLaserEngineering(王兆仲,周付根,刘志芳,等.一种高精度的图像匹配算法.红外与激光工程),2006,35(6):751-755.
CPU为Pentium41.6Ghz,内存256M,显存32M,操作系统为Windows2000,仿真平台为Matlab6.1。
选取了50幅不同的图像,针对不同的情况进行实验,部分效果以及运算时间如图6和表1所示。其中图6(a)为SIFT方法,图6(b)为SSIFT方法。
[2][3][4]
MORAVECH.Rovervisualobstacleavoidance[C]//InternationalJointConferenceonArtificialIntelligence,1981:785-790.HARRISC,STEPHENSM.Acombinedcornerandedgedetector[C]//FourthAlveyVisionConference,1988:147-151.
SCHMIDC,MOHRR.Localgrayvalueinvariantsforimageretrieval[J].IEEETransonPatternAnalysisandMachineIntelligence,1997,19(5):530-534.
[5]LOWEDG.Distinctiveimagefeaturesfromscale!invariantkeypoints[J].InternationalJournalofComputerVision,2004,60(2):91-110
(a)
图6SIFT与SSIFT匹配效果比较
(b)
[6]LOWEDG.Objectrecognitionfromlocalscale!invariantfeatures[C]//InternationalConferenceonComputerVision,1999:1150-1157
Fig.6ComparisonbetweenSIFTandSSIFT
[7]STEPHENS,LOWEDG,LITTLEJJ.Vision!basedgloballocalizationandmappingformobilerobots[J].IEEETransactionsonRobotics,2005,21(3):364-375.
表1图像匹配比较数据
Tab.1Comparisondatainimagematching
PointMatching
amountratematched(SIFT)
RotationIlluminationZoomComplex
3568553233
45.5%32.7%84.9%36.5%
Matching
rate(SSIFT)93.5%56.5%90.6%10.7%
SIFTcomputertime/s123.135.754.3109.7
SSIFTcomputertime/s11.24.25.58.1
[8]
HELMERS,LOWEDG.Objectrecognitionwithmanylocalfeatures[C]//WorkshoponGenerativeModelBasedVision2004(GMBV),2004.
[9]LINDEBERGT.Scale!spacetheory:Abasictoolforanalyzingstructuresatdifferentscales[J].JournalofAppliedStatistics,1994,21:224-270.
[10]MORTENSENEN,REESELJ,BARRETTWA..Computer
visionandpatternrecognition[J].IEEEComputerSocietyConference,2005,1:184-190.
因篇幅问题不能全部显示,请点此查看更多更全内容