基于SIFT特征描述子的立体匹配算法_宰小涛
您的论文得到两院院士关注
文章编号:1008-0570(2007)08-3-0285-03
图像处理
基于SIFT特征描述子的立体匹配算法
AStereoMatchingAlgorithmbasedonSIFTFeatureDescriptor
(上海交通大学)宰小涛
赵宇明
ZAIXIAOTAOZHAOYUMING
摘要:目前,立体匹配是计算机视觉领域最活跃的研究课题之一。为了克服传统的局部特征匹配算法对噪声和图像灰度的非线性变换敏感的缺点,本文提出了一种新的基于SIFT(ScaleInvariantFeatureTransform)特征描述子的立体匹配算法。该算法利用图像梯度信息,构造基于三维梯度方向直方图的SIFT特征描述子作为区域特征描述符,通过立体视觉理论中的极线约束将匹配特征的搜索空间从二维降到一维,最后以基于特征描述子欧氏距离的最近邻匹配得到匹配结果。实验结果表明,该方法匹配精度高,对图像灰度的非线性变换比较鲁棒,可以应用于对匹配算法鲁棒性要求比较高的立体视觉系统中。关键词:立体匹配;SIFT;极线约束;图像变换中图分类号:TP391.41文献标识码:A
Abstract:Stereomatchingisoneofthemostactiveresearchsubjectsinthefieldofcomputervisionatpresent.Anewstereomatch-ingalgorithmbasedonSIFTfeaturedescriptorisproposedinthispaper,inordertorestrainthehighsensitivitytoimagenoiseandnon-linearintensitytransformationasforconventionallocalmatchingalgorithms.ThisalgorithmfirstconstructsSIFTlocalfeaturede-scriptorbasedon3Dhistogramofgradientlocationandorientationbyexploitingimagegradientsinformation,andthenreducesthesearchspaceofmatchingfeaturesfrom2Dto1Dinthelightofepipolarconstraintsinstereovisiontheory,thematchingresultisfi-nallyobtainedaccordingtothenearestneighbormatchingbasedonEuclideandistanceofSIFTdescriptors.Theexperimentalresultsprovethatthisalgorithmwinshighmatchingaccuracyandrobustnessagainstnon-linearimageintensitytransformation.Soitcanbeusedinstereovisionsystemwhichisindemandofhighrobustnessforstereomatchingalgorithm.Keywords:Stereomatching,SIFT,Epipolarconstraints,non-linearintensitytransformation.
技术创新
1引言
立体匹配是立体视觉系统的重要组成部分,是近年来数字图像处理和计算机视觉领域备受关注的前沿方向和研究热点。立体匹配是在变换空间中寻找一种或多种变换,使来自不同时间、不同传感器或者不同视角的同一场景的两幅图像在空间上航空测绘、军事应用、医学诊断及工业一致,它在机器人视觉、
检测中有着广泛的应用前景和潜在的经济价值。
近些年来,各种立体匹配算法相继出现,并且结合许多数学理论和方法,不断有新的匹配算法被提出。本文提出了一种新的基于SIFT(ScaleInvariantFeatureTransform)特征描述子的立体匹配算法,本质上它属于是基于特征点的稀疏匹配。该算法利用图像梯度信息,构造基于三维梯度方向直方图的SIFT特征描述子作为区域特征描述符,通过立体视觉理论中的极线约束将匹配特征的搜索空间从二维降到一维,最后以基于特征描述子欧氏距离的最近邻匹配得到匹配结果。实验结果表明,该方法匹配精度高,对图像灰度的非线性变换比较鲁棒,可以应用于对匹配算法鲁棒性要求比较高的立体视觉系统中。
图1算法框架图
图1中左图和右图是经过校正的同一场景的左视图和右
视图。本文算法首先对左图进行
特征点提取,且分别采用了Harris和SUSAN两种不同的特征提取算法。相对于其它特征提取算法,这两种算法检测性能更好,时间复杂度更低,同时对图像中的噪声信息也不敏感,是特征提取领域应用比较广泛的算法。接下来对于左图中的每一个特征点,根据计算机视觉中的极线几何(Epipolargeometry)理论,在右图中可以计算得到一条对应于该特征点的极线(Epipolarline),这样匹配点的搜索空间就从整幅图像2D空间的盲目搜索降为沿着极线的1D搜索,匹配时间大大提高,最后根据相应的SIFT特征描述子完成立体匹配过程。
2.2极线约束(Epipolarconstraints)
立体匹配中常利用一些约束来减少搜索的范围和确定正确的对应点,如唯一性约束、相容性约束、极线约束等。本文算法为了降低搜索空间采用了极线约束,如图2所示。
图中是真实物理空间的一个三维坐标点,p1和p2分别是其在两个像平面上的投影点,C1和C2分别对应两个摄像机的光学中心,由点P、C1和C2组成的平面PC1C2被称为极线平面就是极(Epipolarplane),此极线平面与两个像平面的交线l、l′线(Epipolarline)。
:360元/年-
2算法原理
2.1算法框架
基于SIFT特征描述子的立体匹配算法整体框架如图1所示。宰小涛:硕士生
PLC技术应用200例》
285-
图像处理
中文核心期刊《微计算机信息》(管控一体化)2007年第23卷第8-3期
头长度和箭头方向表示,梯度的计算公式如下:
(1)(2)
其中,
四个像素点的灰度值。
然后对窗口内每个像素点梯度的幅值利用高斯函数进行加权,如图3(a)中圆形窗口所示,高斯函数表达式如下所示:
图2极线约束示意图
显然,对空间点P来说,给定其在一个像平面的投影点P1,则另一个像平面的投影点P2一定落在极线l上;同理,给定P2,上。也就是说立体匹配过程存在这样一个P1也一定位于极线l′
依据:任一空间点在两个像平面上的投影点,一定落在一对极线上,这就是极线约束(Epipolarconstraints)。从此约束中可以看出,对于立体匹配问题,当提取得到一幅图像中的特征点后,对另一幅图像中匹配点的搜索并不需要在整幅图像中盲目地进行,事实上,这样的匹配点必然落在对应的极线上,沿着此极线进行搜索也一定能够找到对应的匹配点。这样利用极线约束就可以将匹配过程的搜索空间从2D图像降为1D的线性搜索,大大提高了匹配时间和匹配精度。
分别代表点(x,y)处梯度的幅值和方
向,L(x,y+1),L(x,y-1),L(x-1,y),L(x+1,y)分别表示点(x,y)上下左右
(3)
其中,σ为特征描述子窗口大小的一半。引入高斯加权后,避免了当窗口位置发生微小改变时引起的特征描述子的突变,并且越靠近特征点的像素点,其梯度对最终的特征描述向量贡献越大,那些远离中心特征点的像素点梯度对特征描述向量影响因子则较小,因为这些点最容易受图像对准错误干扰。
接下来如图3(b)所示,在窗口内每个4×4的小块上统计计算8个方向的图像梯度方向直方图,具体统计过程为若某个像素点梯度方向落在某一个方向(图3b箭头方向所示)的附近,则其相应的梯度高斯加权幅值就累加在这个方向上,图3(b)中箭头长度代表这个方向上的梯度加权幅值的累加和。
实验证明,当窗口大小取16×16时,此时对每个特征点就可以产生4×4×8=128个数据,即最终生成128维的SIFT特征描述子时,匹配算法的性能最好。但是为了降低算法的时间复杂度,本文中算法采用8×8大小窗口,即每个特征点用一个2×
技
术创新
2.3SIFT特征描述子匹配
常见的立体匹配算法的特征描述函数有SSD,SAD,NCC等。NCC算法易于实现,在模板匹配领域应用非常广泛。但是,在计算过程中NCC算法直接利用图像的灰度信息作为匹配基元,因而导致它对图像中的噪声信息以及图像的各种变换比较敏感,算法鲁棒性不高。
为了有效抑制图像噪声、图像畸变以及图像变换对匹配结果的影响,进一步提高匹配算法的鲁棒性,本文引入SIFT特征描述子作为特征描述函数。SIFT特征描述子是基于生物视觉理论模型提出来的一种新的图像局部特征描述子,该理论认为:生物大脑视觉皮层中的复杂神经元细胞对图像梯度的方向和空域频率信息响应非常强烈,相反地,对梯度的位置信息敏感度没有那么高,即梯度在视网膜上并不需要精确定位,一点点可承受范围内的位移都不会对这些神经元产生视觉刺激。受此理论影响,SIFT特征描述子利用特征点邻域图像窗口内梯度的方向统计直方图来构造特征描述向量,有效解决了NCC算法所存在的缺陷,提高了特征描述子对图像仿射变换,3D视点变换和非刚性变形的鲁棒性,进而提升了整个匹配算法的稳健性。
2×8=32维的特征向量来描述。
最后,将SIFT特征描述子的长度归一化以进一步消除光
照变化的影响,并且为了提高算法对非线性光照变化的鲁棒性,可以限制归一化的特征向量的每一维元素不超过0.2(经验数据),即如果某一维数据元素大于0.2,则令其等于0.2然后再次进行向量归一化。
本文中算法采用沿着极线的一维搜索,搜索宽度定为40
(即最大视差为40),通过计算得到特征点所在模板图和40个搜索子图各自的SIFT特征向量后,下一步采用特征向量的欧氏
距离作为特征点和匹配点的相似性度量。取右图中某个特征点,分别计算此特征点的特征向量与左图中40个相应的搜索子图的特征向量之间的欧氏距离,最后取最小欧氏距离搜索子图的中心点作为匹配点。
SIFT特征描述子的具体生成过程如下。
3实验及其结果分析
为了验证新的匹配算法的性能,50对立体图像样本库被用来进行测试实验,样本库均
由加拿大PointGrey公司生产的Bumblebee双目立体视觉摄像机拍摄而来,所有拍摄图像均为1024×768大小的灰度图像,并且为了更好的测试新算法的鲁棒性,样本库的采集是在光照条件较暗且存在大量遮挡(overlap)场景的条件下进行的。具体实验过程如下所述。
首先测试新匹配算法的匹配精度。将50对样本图依次输入新算法进行立体匹配,图4(a)和图4(b)演示了算法测试程序的运行过程,左、右图为校正后的立体图像对,图4(a)中的红色标记点为特征提取的结果,用鼠标选中某个特征点(图4a中浅绿色点所示),新算法的匹配结果就会在图4(b)中标记出来(图
现场总线技术应用200例》
(a)图像梯度(b)SIFT特征描述子
图3SIFT特征描述子的生成过程
图3说明了SIFT特征描述子的计算过程。首先以特征点为中心取8×8的窗口(图3a中方框所圈),计算窗口内每个像素点的梯度的幅值和方向,在图3(a)中分别以每个方格内的箭
-
-/:
您的论文得到两院院士关注图像处理
(ShanghaiJiaoTongUniversity)ZaiXiao-taoZhaoYu-ming通讯地址:(200240上海上海市闵行区东川路800号上海交通大学B0403291班)宰小涛
(收稿日期:2007.6.03)(修稿日期:2007.7.05)
4b中红色点所示),图4(b)中黄线表示对应的极线。匹配点与精确位置相差超过3个像素即认为是误匹配点,误匹配率为误匹
配点个数除以总特征点个数,最终统计结果本文中算法的平均误匹配率为4.7%,这说明新的算法具有非常高的匹配精度。
(a)右图(b)左图
图4测试样本图像
(c)增强后左图
接下来测试新算法的鲁棒性。将50对样本图中的左图通通采用Aptic算法增强(一种图像灰度非线性变换),右图不变,然后用变换后的图像对进行匹配实验,测试运行过程如图4(a)和图4(c)所示,图中所有标记的物理意义同上,仍然采用和上面相同的误匹配率指标,最终统计结果本文算法的平均误匹配率为8.2%,这说明了新的算法在图像灰度发生剧烈变化时,仍然能够保持非常高的匹配精度,充分验证了新的算法对图像仿射变换、3D视角变换和图像灰度的非线性变换都具有非常好的鲁棒性。
(上接第292页)
[4]TChang,eta1TextureAnalysisandClassificationwithTree.stme.turedWaveletTransform[J]IEEETransonImageProc,1993,2(4):429-441
[5]J.Z.Wang,J.LiandG.Wiederhold,“SIMPLIcity:Semantics-sensitiveIntegratedMatchingforPictureLibraries”,IEEETrans-actionsOnPatternAnalysisAndMachineIntelligence,Vol.23,No.9,September2001.
曹元大等,图像检索中基于记忆与半监督的主动相[6]周艺华,
北京理工大学报,关反馈算法[J],2006,26-1:45-48.任建锋等,支持语义的图像检索[J],南京航空航天大[7]鲍永生,
学学报,2005,37-1:75-78.
[8]邢慧强,SVM用于基于块划分特征提取的图像分类[J]微计算机信息,2006,22:210-212。
作者简介:赵正利(1978—),女(汉族),山东青岛人,中国海洋大学在读硕士研究生,研究方向信号与信息处理;王国宇(1962—),男(汉族),山东青岛人,中国海洋大学博士生导师,电子系主任,主要从事图像处理,模式识别,三维图像分析
4结束语
本文作者创新点:
在基于特征点的立体匹配框架中,利用图像梯度信息,引入基于三维梯度方向直方图的SIFT特征描述子作为区域特征描述符,这种邻域方向性信息联合的思想增强了算法抗噪声的能力和对图像变换的鲁棒性,同时对于含有定位误差的特征匹配也提供了较好的容错性。实验结果表明,该算法匹配精度高,对图像灰度非线性变换的鲁棒性较好,可以应用于对匹配算法鲁棒性要求比较高的立体视觉系统中。
Biography:ZhaoZhengliwasbornin1978.Nowsheisapost-graduatestudentinDepartmentofElectronicEngineering,OceanUniversityofChina.Hercurrentresearchinterestissignalandinformationprocessing;WangGuoyuwasbornin1962.Heisaprofessor,doctorsupervisor,departmenthead,Hiscurrentre-searchfield:ImageProcessing,PatternRecognition,Three-di-mensionalImageAnalysis.
(266100山东青岛中国海洋大学电子工程系)赵正利王国
宇籍芳
通讯地址:(266100青岛青岛市崂山区松岭路238号中国海洋大学信息学院电子系2004级研究生)赵正利
(收稿日期:2007.6.03)(修稿日期:2007.7.05)
技术创新
参考文献
[1]HarrisC.G.,StephensM.Acombinedcornerandedgedetector.In4thAlveyVisionConference,1988,147-151.
[2]SmithS.M.,BradyJ.M.SUSAN-Anewapproachtolowlevelimageprocessing[J].InternationalJournalofComputerVision,1997,23(1):45-78.
[3]EdelmanS.,IntratorN.andPoggioT.Complexcellsandobjectrecognition,1997.Unpublishedmanuscript:http://kybele.psych.cornell.edu/ ̄edelman/archive.html
[4]LoweD.G.Distinctiveimagefeaturesfromscale-invariantkey-points[J].InternationalJournalofComputerVision,2004,60(2):91-110.
[5]马颂德,张正友.计算机视觉-计算理论与算法基础[M].北京:科学出版社,1998.
[6]牛刚,梁伟.基于特征像素统计的图像相关匹配算法[J]微计算机信息,2005,33:103-105.
作者简介:宰小涛(1982-)男,硕士生,主要研究方向:图像增强,立体匹配等;赵宇明(1968-)女,博士生,副教授,主要研究方向:图像增强,立体匹配,模式识别等。
Biography:ZaiXiaotao(1982-)Male,Master,Mainresearchfield:Imageenhancement,stereomatchingetc;ZhaoYuming(1968-)Female,AssociateProf.,Doctor,Mainresearchfield:Imageenhancement,stereomatching,patternrecognitionetc.(200240上海上海交通大学)宰小涛赵宇明
PLC技术应用200例》
(上接第301页)
Biography:QuXun-zhengwasbornin1981.Nowheisapost-graduatestudentinDepartmentofElectronicEngineering,OceanUniversityofChina.
Hiscurrentresearchinterestissignaland
informationprocessing;WangGuo-yuwasbornin1962.Heisaprofessor,doctorsupervisor,departmenthead,Hiscurrentre-searchfield:ImageProcessing,PatternRecognition,Three-di-mensionalImageAnalysis.
(266100青岛中国海洋大学信息科学与工程学院)曲训正
王国宇许静
(DepartmentofElectronic&Engineering,,OceanUniversityofChina,Shandong,Qingdao,266100)QuXun-zhengWangGuo-yuXuJing
通讯地址:(266100青岛青岛市崂山区松岭路238号中国海洋大学信息学院电子系2004级研究生)曲训正
(收稿日期:2007.6.03)(修稿日期:2007.7.05)
:360元/年-
287-