第19卷第11期 2008年11月 JournalofOptoelectronics・Vol.19No.11 Nov.2008Laser
基于SIFT算法的圆心快速精确定位技术研究
吴慧兰33,刘国栋,刘炳国,浦昭邦
(哈尔滨工业大学自动化测试与控制系,哈尔滨150001)
3
3
摘要:针对SIFT算法在圆心检测应用中的特点,分析了SIFT算法中存在的冗余步骤,提出对其进行简化改进:
估计圆心所在的金字塔层,删减金字塔中多余的层数建立,并且通过提高滤除低对比度特征点阈值的办法减少背景特征点的生成,去掉了特征点辅方向分配和建立辅方向特征点这一步骤。分别对计算机模拟生成的标准圆和实际的PCB定位标志图像做了圆心检测实验,实验表明,SIFT算法改进后在没有降低其定位精度及对图像的模糊、光照、仿射等变换适应性的情况下,大大缩短了检测时间,提高了检测效率。关键词:圆心定位;尺度不变特征变换(SIFT)算法;特征匹配;冗余中图分类号:TP391 文献标识码:A 文章编号:100520086(2008)1121512204
Studyonthecirclecenterfastaccurate2locatingtechniquebasedontheSIFTWUHui2lan33,LIUGuo2dong,LIUBing2guo,PUZhao2bang(DepartmentofAutomaticMeasurementandControl,HarbinInstituteofTechnology,Harbin,150001,China)Abstract:InallusiontothecharacteristicsoftheSIFTalgorithmintheapplicationofcirclecenterlocation,redundantproce2dureisanalyzedandanovelpredigestedandimprovedmethodisproposed.Byestimatingwhichpyramidoctavethecirclecenterisin,eliminatingtheredundancypyramidoctaves,andreducingthekeypointsgeneratedfromthebackgroundbyin2creasingthethresholdforfilteringoutthekeypointswithlowcontrast,thestepsofassigningassistantorientationsofthekeypointsandgeneratingkeypointswithassistantorientationhasbeenleavedout.CirclecenterdetectionexperimentshavebeencarriedoutforbothstandardcirclesgeneratedbythecomputerandtherealPCBlocationmarkimages.Theexperimentresultsshowthat,withoutanypenaltyofthelocationaccuracy,orrobustnesstoblur,illumination,affinetransformation,thedetectionefficiencyhasbeenimproveddramaticallywiththeproposedimprovedmethod.Keywords:circlecenterlocation;scaleinvarintfeaturetransform(SIFT);featurematching;redundancy
1 引 言
视觉检测中,圆形定位标志是较为常用的。传统的圆心检
测方法以圆Hough变换最为常用[1,2],但该方法在三维空间运算时资源需求大,检测速度慢。后来出现的各种改进的Hough变换大多在边缘检测的基础上进行,虽然提高了运算速度,但对图像的变形适应性差。因此研究圆形定位标志圆心的检测方法,在保证其检测精确度和效率的同时,保证其对图像变形的适应性是极为重要的。2004年David.G.Lowe[3,4]在总结了现有的不变量特征检测方法基础上提出了SIFT(scaleinvariantfeaturetransform)算法,它是一种基于尺度空间的对图像缩放、旋转甚至仿射变换均保持不变性的局部特征点匹配算法。SIFT算法提出后,很快成为国内外特征点匹配领域研究的热点,在图像的识别、目标跟踪定位中[5～7]得到了广泛的应用,并随着更多学者的深入研究,SIFT算法的应用领域亦不断拓宽。 SIFT算法的特征检测器在圆心处具有极值响应,利用该特性对圆形标志进行定位,其原理不同于基于参数空间变换原理的Hough变换,对图像的各种变换,尤其是仿射变换,更有适应性。但SIFT算法本身运算复杂,提取的特征点有很多冗
余[8],这些冗余在图像识别中可以增加目标正确识别的概率,在圆心定位中却是不必要的。本文针对其在圆心定位中的特点,在保证不改变其定位精确度及对图像模糊、光照和映射仍保持鲁棒性的前提下,提出减少不必要的冗余步骤的改进算法,以达到提高运算速度的目的。
2 SIFT算法在圆心定位中的应用
2.1 常规SIFT特征提取算法及圆心定位原理
SIFT算法在高斯差分尺度空间,DoG空间(Differenceof
GaussianScale2space)提取极值点作为特征点,主要有以下4个
步骤[4]。
1)建立高斯差分尺度空间并寻找极值点
输入图像经过与系列尺度等间隔的高斯核函数卷积及2×2降采样生成N层高斯尺度空间金字塔,其中每层金字塔又分为若干层,同层金字塔中高斯图像大小相等,然后同层金字塔中相邻尺度图像相减得到DoG空间金字塔。DoG空间函数σ)定义如下:D(x,y,
3收稿日期:2008201208 修订日期:2008203228
3 基金项目:中国博士后基金资助项目(20060400820)哈工大2006优秀青年教师基金资助项目 33E2mail:whl3003@163.com
第11期 吴慧兰等:基于SIFT算法的圆心快速精确定位技术研究 ・1513・
σ)=(G(x,y,kσ)-G(x,y,σ))3I(x,y)= D(x,y,
σ)-L(x,y,σ)(1)L(x,y,kσ)=式中G(x,y,
1πσ2
2
e
-(x+y)
22
σ是尺度可变高斯函数,L(x,/2
2
分配增加了图像匹配的鲁棒性,但是在对圆心定位时却是
不必要的冗余。减少上述冗余,加快算法运算速度是本文的主要目的。
σ)是高斯图像,k是数值恒定的尺度比例因子,σy,为高斯尺度。 在建立了DoG空间以后,对DoG空间的每一个像素点都
σ)中的8邻域像素点及上下相与其所在尺度DoG图像D(x,y,
邻尺度DoG图像中对应的9像素点比较,如果此像素点是局部极值点,则列入特征点候选对象。 2)特征点精确定位 通过拟合三维二次函数将特征点的位置和尺度精确到亚像素。计算特征点对应DoG图像三维二次函数拟合值的绝对值,并将绝对值小于阈值的特征点去掉以滤除低对比度的特征点;计算特征点的曲率,将曲率大于设定阈值的特征点去掉以滤除不稳定的边缘响应点。 3)特征点方向分配 计算特征点所在高斯尺度空间图像的梯度,梯度的幅值与方向角计算公式如下: m(x,y)=
(L(x+1,y)-L(x-1,y))2
2
+(L(x,y+1)-L(x,y-1))
1/2
2.2 改进后的基于SIFT算法检测圆心步骤
1)估计待检测圆大小,初步确定可以在哪层DoG金字塔中检测到圆心。 2)以第1)步确定的金字塔层为中间层,构建3层金字塔。这样做的好处是允许有一定的估计失误,在估计不是很准确的情况下也能找到圆心。 3)在构建的3层金字塔中搜索DoG空间极值点作为图像特征点,精确定位特征点,并在精确定位特征点时提高滤除低对比度特征点所采用的阈值,滤除更多的背景特征点。 4)为检测到的特征点分配主方向,方法与SIFT算法相同,但是省略为特征点分配辅方向这一步骤。 5)计算SIFT特征点描述符,与原SIFT算法相同。 6)特征点匹配。对于一个纯色背景下的没有噪声污染的标准圆,在相应的DoG空间只在圆心处存在一个特征点。但实际上,1幅真实的图像是不可能没有噪声干扰的,因此,其构建的DoG空间中的极值点除圆心点外,还有很多其它的极值点,这些极值点生成的特征点干扰了圆心的检测。本文通过与标准图像数据库的特征点匹配滤除这些干扰点;数据库中存储着每一种待检测圆的标准图像的圆心点特征。 由于在第3)步中提高了滤除低对比度特征点阈值,使得背景特征点数量大大减少,降低了背景特征点带来的误匹配,因此采用直接比较特征欧式距离的方法进行特征点匹配,即离标准图像圆心距离最近的点即是待检测的特征点。
L(x,y+1)-L(x,y-1)θ(x,y)=atan2
L(x+1,y)-L(x-1,y)
(2)
将梯度的方向角从0～360°分为36个方向,在以特征点为
中心的邻域窗口内采样,并统计窗口内梯度的幅值在36个方向上的投影累加值,累加值最大的方向即为特征点的主方向。并将其它累加值大于主方向累加值80%的方向设为辅方向。一个特征点可能会被指定具有多个方向(1个主方向,1个以上辅方向)。 4)计算特征点描述子
)坐标轴旋转到 首先将特征点所在高斯图像L(x,y,σ
特征点主方向;然后以特征点为中心,将其周围16×16像素的窗口分为4×4个子窗口,在每个子窗口内计算高斯图像梯度在8方向上的投影累加值,得到1个4×4×8=128维的特征向量,最后将特征向量规范化到单位长度。 SIFT算法可以检测到圆心主要有以下两点原因。(1)图像的卷积值是由卷积模板与图像中和模板对应的点逐像素相乘相加得到的。当高斯窗口的大小能覆盖待检测圆时,由于SIFT算法中高斯函数的圆对称性,圆心点被周围像素值加权平均后,是DoG空间的一个极值点。(2)SIFT算法中的DoG空间金字塔是通过图像降采样后与不同尺度的高斯差分核卷积得到。图像降采样可以使待检测圆缩小到能被高斯卷积模板所覆盖。 根据以上分析,SIFT算法在对圆心检测的过程中,有以下两点是冗余的。 1)金字塔层冗余。原SIFT算法为了得到尽可能多的有效特征点,金字塔层的构建一般是6～7层。但圆心只存在于其中一层金字塔中,在高斯卷积模板能覆盖待检测圆之前及之后金字塔层的构建对圆心检测是没有贡献的,增加了算法的运算时间,而且由此多检测出的极值点及其滤除也增加了算法的运算时间。
[7]
2)特征点的辅方向分配。在图像识别中,辅方向的
3 实验结果
3.1 标准圆定位比较
本文实验是在主频2.8G、内存512M的PC机上利用
matlab7.1和C语言混合编程实现的。图1(a)和图1(b)分别是半径为140像素的标准圆添加密度为0.02的椒盐噪声和σ=0.005的高斯加性噪声后,用改进前和改进后的SIFT算法检测到的特征点,较大十字线是通过与没有噪声污染的标准圆圆心匹配检测到的圆心点,较小十字线是SIFT算法检测到的其它不相关的特征点。
图1 SIFT算法改进前(a)后(b)检测的
标准圆图像特征点及圆心
Fig.1 ThekeypointsandthecirclecenterdetectedbythebasicSIFTalgorithm(a)
andtheimprovedSIFT(b)onthestandardcircleimage
表1列出了添加不同程度的噪声后SIFT算法改进前后检
・1514・
光电子
2008年 第19卷 ・激光 测到的圆心位置准确度对比。
表2列出了检测的特征点数和所用时间的对比。 从图表中可以看出,在没有影响算法的定位精度的同时,SIFT算法改进后耗时由20s减少到0.6s,使检测效率大大提高。
表1 SIFT改进前后及Hough变换圆心定位精确度对比
Tab.1 ComparisonofthelocationaccuracyofthebasicSIFT,
theimprovedSIFTandtheHoughtransform(theidealvalueofthestandardcirclecenter
is(300,300)pixel) (Unit/pixel)
BasicSIFT
Noisetype12345Mean12345Mean123345Mean
coordinates
x
y
x
金字塔层节约了时间,而且在少构建的金字塔层上少了相应的特征点的搜索、精确定位、描述这些步骤,节约了大量的时间。 2)提高了滤除低对比度特征点阈值,使得更多的背景点被滤除,较少的特征点更利于后面的匹配定位。 3)去掉了辅方向分配这一步,每个极值点只产生一个特征点,少生成的特征点为后面的匹配定位节省了时间。 4)特征点匹配法采用直接比较特征向量最近欧式距离,计算量小于原SIFT算法中比较特征向量欧氏距离最近距离与次最近距离之比。
3.2在视觉检测中的应用
与模拟实验相比,实际图像会更复杂,噪声也更复杂,在本节中主要将该算法应用在PCB(印刷电路板)圆形定位标志检测上。 图2(a)是PCB圆形定位标志图像利用改进前SIFT算法提取的特征点,2(b)是利用改进后的SIFT算法提取的特征点。图中较大白色十字线标示圆形定位标志的圆心,较小白色十字线是其它不相关的特征点。从图中可以看出改进后检测到的干扰性特征点少了很多。error
y
301.20301.30301.30301.20301.30
301.40301.50301.40301.30301.40
1.201.301.301.201.301.260.100.400.400.200.200.38-1.0-1.0-1.0-1.0-1.0-1.0-1.0
1.401.501.401.301.401.420.100.200.500.500.400.34-1.0-1.0-1.0-1.0-1.0-1.1-1.0
—300.20300.40300.40300.20300.20
—ImprovedSIFT
300.10300.20300.50300.5030.40
图2 改进前(a)后(b)SIFT算法提取的
PCB定位标志图像特征点
Fig.2 ThekeypointsdetectedbythebasicSIFT(a)andtheimprovedSIFT(b)onthePCBlocationmarkimages
—
299.0299.0299.0299.0299.0299.0
—
Houghtransform
299.0299.0299.0299.0299.0298.9
表3列出了算法改进前后提取的特征点所用时间的对比,
表4列出了检测精度对比,可以看出算法改进后在保证了定位精度的同时,大大提高了其运算速度。
表3 SIFT改进前后PCB定位标志圆心检测耗时对比
Tab.3 ComparisonofthebasicSIFTandtheimprovedSIFT
intermsofthedetectiontimesforthePCBlocationmarkcirclecenter
ThemethodKeypointsqantityDetectiontime/sMatchtime/sTotaltime/s
BasicSIFT
16117.490.1917.68
ImprovedSIFT
20.860.020.88
——
Note:noisetype12nonoise;2-0.02peppernoise
σ=100Gaussianblur3-0.005Gaussiannoise,42
5-0.005Gaussiannoise+0.02peppernoise
InitalvaluesofthevariablesσandkintheSIFTaresettobe1.6and21/srespectively,sdenotestheintervalsofeveryoctaveandissettobe3and,thethresholdforfilteringoutkeypointswithlowcontrastis0.08.
表2 特征点数和耗时对比
Tab.2 Comparisonoftheamountofthekeypoints
andthedetectiontime
ThemethodKeypointsquantityDetectiontime/sMatchtime/sTotaltime/s
BasicSIFT
63720.020.1920.21
ImprovedSIFT
30.610.050.66
表4 SIFT改进前后PCB定位标志圆心检测精确度对比(像素)
Tab.4 ComparisonofthebasicSIFTandtheimprovedSIFT
intermsofthedetectionforthePCBlocationmarkcirclecenter(pixel)
Truevalue
x
y
BasicSIFT
x
y
ImprovedSIFT
x
y
改进的SIFT算法比原SIFT算法耗时少主要有下面的
原因: 1)金字塔层构建少。原SIFT算法金字塔一般构建6～7层,而改进后的SIFT算法只构建3层金字塔。不但少构建的
159.6139.3159.0141.5159.9140.3
另外本文还对图像的光照变化、离焦模糊及仿射变换做了一系列实验。图3(a)是改变照明条件后的检测图像,图3(b)
第11期 吴慧兰等:基于SIFT算法的圆心快速精确定位技术研究 ・1515・
是离焦状态下的检测图像,图3(c)是图3(a)添加仿射变换后的图像,较大白色十字线标示定位标志的圆心,较小白色十字线标示背景特征点。
SIFT算法对圆心检测的步骤,提高了检测效率。SIFT算法对图像的多种变换具有不变性,是其胜于其他圆心检测方法的主要优点,改进的SIFT算法在提高工作效率的同时,并没有降低算法对图像各种变换的适应性,使得利用SIFT算法检测圆心
更有实用性。
参考文献:
[1] LIUKe,ZHUOFu2qiang,HZANGGuang2jun.Radiusconstraintleast2
squarecirclefittingmethodanderroranalysis[J].JournalofOptoe2lectronics・Laser(光电子・激光),2006,17(5):6042607.(inChi2nese)[2] YUANWei2qi,XULu,LINZhong2hua.Irislocalizationalgorithmbased
ongraydistributionfeaturesofeyeimages[J].JournalofOptoelec2tronics・Laser(光电子・激光),2006,17(2):2262130.(inChinese)[3] DavidG.Lowe.Objectrecognitionfromlocalscale2invariantfeatures
[A].Proceedingsofinternationalconferenceoncomputervision[C].Corfu,Greece,1999,115021157.[4] DavidG.Lowe.Distinctiveimagefeaturesfromscale2invariantkey2
points[J].IntJournalofComputerVision,2004,60(2):912110.[5] KrystianMikolajczyk,CordeliaSchmidA.Performanceevaluationof
localdescriptors[J].IEEETransactionsonPatternAnalysisandMa2chineIntelligence,2005,27(10):161521630.
[6] KeY,SukthankarR.Pca2sift:amoredistinctiverepresentationforlo2
calimagedescriptors[A].IEEEConferenceonComputerVisionandPatternRecognition(CVPR04)[C].2004,5062513.[7] ManueleBicego,AndreaLagorio,EnricoGrosso,etc.Ontheuseof
SIFTfeaturesforfaceauthentication[J].Proceedingofthe2006Con2ferenceonComputerVisionandPatternRecognitionWorkshop(CVR2PW′06)[C].2006.[8] LukeLedwich,StefanWilliams.ReducedSIFTfeaturesforimage
retrievalandindoorlocalisation[J].AustralasianConferenceonobot2icsandAutomation(ACRA′04)[C].Canberra,Australia,2004.
图3 改变光照条件(a),图像模糊(b)
及添加仿射变换(c)定位图
Fig.3 Thelocationimageswithillumination
conditionchanging(a)ou2offocusblur(b)andaffinetransform(c)
表5列出了检测结果,并给了其它状态相对于聚焦状态下
的检测误差。可以看出除了图像的模糊对检测的影响较大,检测结果与聚焦状态相比相差了1个多像素,其它的图像变换检测结果与聚焦状态相比均在0.5个像素以内。该算法对图像变换的适应性,是胜于其它圆心检测算法的最大优点。表5 PCB定位圆心检测结果(pixel)
Tab.5 ThelocationmarkcirclecenterdetectionresultofPCB(pixel)
Imagemorphology
blur
illuminationtransform
afinetransform
coordinates
x
error
y
161.7141.1160.5140.1
1.80.6
0.8-0.2
160.0140.1-0.1-0.2
除此之外本文亦对其它的定位标志诸如ICF实验靶的定
位标志等做了圆心检测实验,结果良好,限于篇幅限制,不再赘述。
4 结 论
本文针对SIFT算法在圆心定位过程中的特点,简化了
作者简介:
吴慧兰 (1982-)博士研究生,主要从事模式识别、图像处理研究1
因篇幅问题不能全部显示，请点此查看更多更全内容