SURF特征匹配中的分块加速方法研究

SURF特征匹配中的分块加速方法研究 SURF特征匹配中的分块加速方法研究 第4l卷第6期 2011年6月 激光与红外 【ASER&INFRARED Vo1.41,No.6 June.2O11 文章编号:1001-5078(2011)06-0691-06?图像与信号处理? SURF特征匹配中的分块加速方法研究 乔勇军,谢晓方,李德栋,孙涛 (海军航空工程学院兵器科学与技术系,山东烟台264001) 摘要:针对高实时性要求中SURF(speededuprobustfeatures)特征匹配算法速度偏慢的缺 点,提出一种基于分块的加速方法,根据匹配中 模板 个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载 图像与搜索图像的大小对比关系,分别采 用只对搜索图像分块的单分块方法与对模板图像与搜索图像都进行分块的双分块方法,其中 单分块方法包括简单分块,简单+1分块,尺度+1分块及模板尺寸与尺度自适应的分 块方法;双分块方法包括单块匹配与多块匹配.针对不同的分块方法分析了其理论上的平均 匹配时间,并通过实验进行了对比,结果证明分块方法能够在保证正确匹配的同时大幅提高匹 配速度. 关键词:SURF;特征匹配;分块;加速 中图分类号:TP391文献标识码:ADOI:10.3969/j.issn.1001.5078.2011.06.021 Researchonthespeed-upmethodofSURFfeature matchingbyblocking QIAOYong-jun,XIEXiao?fang,LIDe-dong,SUNTao (DepartmentofOrdnanceScienceandTechnology,NavalAeronauticalandAstronauticalUniversity,Yantai264001,China) Abstract:ToovercometheshortcomingofSURF(speededuprobustfeatures)featurematchingalgorithm.aspeed—up methodbasedonblockingisproposed.Accordingtothesizesoftenlplateimagesandsearchingimages , itisproposed toadoptthesingleblockingmethodthatonlysplitsthesearchingimagesandthedoubleblockingmethodthatsplits boththetemplateimagesandthesearchingimagesrespectively. TheformerincludesthemethodofsimpleKbl0cking, simpleK+1blocking,scaleK+1blockingaswellassizeandscaleself-adaptiveblocking, 【hedoubleblockingmeth— odincludessingleblockmatchingandmultipleblocksmatching.Fordifferentblockingmethod,tl1etheoreticaverage matchingtimesareanalyzedandexperimented,theresultsshowsthattheblockingmethodcarlsDeedupfeaturematc— hingremarkablywhilekeepingcorrectmatching. Keywords:SURF;featurematching;blocking;speed.up 1引言 在数字图像处理中,图像匹配是根据一幅已知 图像(模板图像)在待匹配图像(搜索图像)中寻找 对应子图的过程,它在计算机视觉,医学图像,资源 分析,航空导航,目标识别与跟踪等领域具有广泛的 应用.目前的图像匹配算法主要分为基于灰度与基 于特征两类,而后者为近年来国内外研究与应用最 多一. 在图像特征匹配算法中,目前研究及应用最多 的算法有两种,分别是2004年DavidG.Lowe所提 出的sI不和2006年苏黎世理工学院计算机视觉 实验室提出的SURF,二者都是基于尺度,旋转, 光照与仿射不变性特征的算法.这两种算法不仅包 含感兴趣点检测,也包含对感兴趣点进行独特 基金项目:装备维修改革专项基金资助. 作者简介:乔勇军(1973一),男.博士,研究方向为武器系统建 模与仿真.E—mail:qyjdatabase@163.corn 收稿日期:2010-07-25;修订日期:2011-02.24 692激光与红外第41卷 识别与匹配的不变特征描述符的生成.2007年, J.Bauer对三种版本的SIFT(DavidLoweSIFT, sI++,LTI—libSIFT),两种版本的SURF(SURF, 旋转, SURF.d)及Harris角点检测器等算法以尺度,噪声,亮度及视点变化为指标通过实验进行了比较 与评估,结论是SURF无论在速度上还是在精度上 il设定sURF检爰I参数l ? I计算积分图像l ? l尺度空间分析I ? l计算Hessiall矩阵I ? l检测并定位感兴趣点l 都比其他算法更为优异J. 2SURF特征匹配算法 SURF算法主要包括三个步骤:感兴趣点检 测,感兴趣点描述及感兴趣点匹配,其算法流程 如图1所示,其中三个虚线框分别对应了这三个 步骤. 图1SURF算法流程图 2.1感兴趣点检测 SURF对感兴趣点(也称特征点)的定义是指图 像中具有独特位置的点,例如角点,斑点及T形连 接.感兴趣点检测器最有价值的属性是可重复性, 可重复性代表了检测器在不同视觉条件下搜索感兴 趣点的可靠性. 对尺度具有不变性的检测器中最具代表性的是 SIFT,其原理是首先利用高斯与图像的卷积生成高 斯金字塔,利用高斯差分(DOG)与图像的卷积生成 高斯差分金字塔,进而构建尺度空间,然后在尺度空 间内计算3X3Y3立体邻域内的极值点,并以此点 为感兴趣点.SIF]r感兴趣点检测的缺点在于计算 时间太长.为了加快速度,SURF通过在尺度空间 内计算Hessian矩阵行列式的值来获得极值点.对 于图像I中的一个点X=(,Y),在尺度or下的Hes— sian矩阵H(,or)定义为: Lxx (X,or】? 其中,,J(,or)是二维高斯函数g(,y,or)的二阶偏 导数L(,or)=g()与图像,在点X的卷积; L(,or)与L(,or)亦然. 为进一步加快速度,SURF在计算过程中采用 图2所示的箱式滤波器与积分图像来简化计算. nn 图2箱式滤波器取代高斯二次偏导 2.2感兴趣点描述 SURF的感兴趣点描述符描述的是感兴趣点邻 域内的分布密度,与sIFTr中描述符用于对梯度信息 进行描述类似.SIFT的描述方法是将20Y20的区 域划分成小的4X4子区域,在每个子区域中计算8 个方向的梯度直方图,从而得到4Y4×8:128维的 描述符矢量.经学者证明,SIH'描述符的生成方法 非常耗时. 与SIFT不同,SURF通过计算Haar小波响应来 提取描述符.第一步是确定感兴趣点的主方向:首 先在感兴趣点6s圆形邻域内计算与Y方向的小 波响应(S为检测感兴趣点时所使用的尺度,小波边 长为4S),然后对小波响应运用or=2s的高斯进行 加权,再使用60.的滑窗来计算窗口内与y方向的 总响应从而得到新矢量,最后选择最长矢量的方向 为主方向.第二步是提取描述符:首先将坐标轴旋 转到感兴趣点的主方向,然后以此点为中心,沿主方 向上选择一个20SX20S的正方形区域,并将其划 分成4Y4的子区域,再在每个子区域内按5×5采 样点计算Haar小波响应,于是每个子区域可以得到 一 个四维的矢量: b=(?d,?ldl,?d,?ld,I)(1) 所以SURF的描述符维数是4Y4Y4=64.因 为小波响应对光照具有不变性,所以SURF描述符 1II 0'????I l??- _一一曩一 一曩一一 一一一一一_一.,一_一一曩一 一一" 激光与红外No.62011乔勇军等SURF特征匹配中的分块加速方法研究693 也是对光照不变的.进一步对描述符进行单位化或 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 化,即可实现对对比度的不变性. 2.3感兴趣点匹配 SURF感兴趣点匹配是基于矢量间距离的,即 通过计算模板图像与搜索图像感兴趣点的描述符矢 量间的距离(如Mahalanobis,Euclidean,Hausdorff 等)来确定两个感兴趣点是否匹配. 3单分块方法 从SURF特征匹配算法可以看出,整个匹配过 程所消耗的时间主要分为感兴趣点检测与描述和感 其中第一项与图像尺寸及感 兴趣点匹配两个部分, 兴趣点的数目直接相关,而第二项与模板图像与搜 索图像中感兴趣点的数目之积相关.一般来说,图 像尺寸越大,感兴趣点数目也越多,相应地感兴趣点 检测与匹配的时间也越长.当模板图像尺寸远小于 搜索图像时,模板图像中感兴趣点的数目相对较少, 整个特征匹配过程所消耗的时间主要是搜索图像中 感兴趣点的检测,而当模板图像与搜索图像都比较 大且感兴趣点都比较多时,感兴趣点匹配的时间会 急剧增加,这一点从表1可以看出.另外,从表1还 可以看到,尽管SURF较以前的算法在速度上有了 很大的提高,但耗时仍然很大,这一点制约了其在高 实时性要求的系统中的应用.实际上,在很多应用 中一般并不需要对两幅图像中所有的感兴趣点都进 行检测与匹配,所以如果采用分块操作,匹配时间必 将大大减少 表1标准SURF特征匹配时间分布 模板图像搜索图像模板图像中模板图像中搜索图像中搜索图像中感兴趣点匹配 尺寸尺寸感兴趣点数目感兴趣点检测时间/ins感兴趣点数目感兴趣点检测时间 /ms时间/ms 420×400720×4001458136.7522822l8.141363 66×66512×384635.922l25162.7456.65 单分块方法是只对搜索图像进行分块检测,描 述与匹配的方法,主要适用于模板图像尺寸远小于 搜索图像的情况. 3.1标准分块 标准分块是指对搜索图像按照常规的2×2, 3x3,3X2等进行等大小分块,如图3所示. 图3单分块中的标准分块方法 3.1.1简单分块 记模板图像为(m,n),尺寸为mXn,记搜索 图像为S(M,N),尺寸为M×N.假设均匀分块的 数目为k,标准SURF匹配时间为t,另假定感兴趣 点均匀分布,则对单个图像子块进行匹配的时间为 , t=_vS ,匹配过程中按照图像块从上到下,从左至右 ,c 的顺序进行匹配,相应的子块依次标记为1,2,…, k,如果某个子块匹配成功则终止退出,那么匹配到 , 第i块所需时间为,=it=i芋,那么按照分块策略 对搜索图像完成匹配所需的平均时间为: ? ravel=一 tS bavelk2?2=2kf(2)一一一, 从公式(2)知当后大于1时,t…<t,所以通过 分块方法是可以降低特征匹配时间的.另外公式 (1)显示当k增大时,,…减小,但事实上k并非是可 以无限增大的,因为当增大时运算中会需要更多 的变量与图像分割,相应会增大时间消耗,另外分块 太多则单个子块中的感兴趣点数目相应减少,结果 可能造成匹配失败或错误匹配. 简单分块策略中最简单的分块是2×2分块,即 将搜索图像均匀划分为4块,根据公式(2)可知平 均匹配时间约为0.63t. 3.1.2简单K+1分块 如果要对 简单分块可适用于任意图像的匹配, 视频图像或者序列图像进行匹配,考虑到图像序列 中相邻的图像变动幅不大,可以采用+1分块方 法,如图1中右图所示.简单K+1分块是在简单 分块的基础上增加一个中心分块,其尺寸等同于 分块的大小,匹配时该块优先处理.假设模板图像 出现在中心块内的概率为P,那么采用此方法匹配 的平均时间为: tare2=p tS +(1(?+)t = ,'L (3) 激光与红外第41卷 对比式(2)与式(3),要使t.以<t.,即: 只需: 2 p> 不足分块部分的宽度与子块宽度的比值;【】表 (4)示水平分块中整块的数目 .垂直分块与水平分块方 法相同,所以搜索图像的分块数目为: (5) 3:,s+ 4o"zmn ,5(6)…3s+o 100,M=640,N=480时t…3O.81t5.和简单K分 ? : (M)(8) 分块数目确定后,后期匹配方法与平均时间的 计算与第3.1节相同. 4双分块方法 单分块方法在模板图像尺寸远小于搜索图像的 条件下适应性较好,当二者尺寸比较接近时,模板图 像与搜索图像中的子块相比相对较大,此时应该采 用对模板图像与搜索图像都进行分块的双分块 方法. 4.1单块匹配 双分块后,最简单的匹配方法是取模板图像中 的一个子块进行匹配,如果匹配不成功则用另一子 块继续匹配,直到匹配成功或者所有的子块全部 用完. 假设模板图像按照简单分块方法被等分成 块,搜索图像亦按照此法等分成k块,另假设模板图 像中子块匹配成功的概率相等,则由公式(2)得到 单块匹配的平均时问: tare4=了l&了i(9) 假设k=f=4,则te4一O.39ts. 4.2多块匹配 双分块中单块匹配的缺点是模板图像与搜索图 像都进行了分块,这样两个子块匹配的成功率大为 降低,另外即使两个子块匹配成功也难以保证整个 模板图像与搜索图像匹配的正确性,解决办法是采 取多块匹配. 多块匹配时子块的选择非常重要,保持整体性 最好的是沿对角线选择子块,如图4中.所示,因 为模板图像在搜索图像中所处的位置不同而有三种 不同的选择方向.匹配时先选取模板图像中的左上 角子块按照简单分块方法进行匹配,成功匹配后 再根据该块在搜索图像中所处的位置按照图4所示 的选择方向选择水平/垂直/对角线上相邻的另一块 进一步匹配,直到该方向上的块都被完全匹配或者 模板越界.多个子块匹配后,整体性的衡量是运用 RANSAC算法计算多个子块位置关系的一致性,这 样才能确保在缩小匹配范围即减少感兴趣点数目的 情况下保证匹配的正确性. 激光与红外No.6201l乔勇军等SURF特征匹配中的分块加速方法研究695 图4双分块多块匹配中模板图像子块的 三种子块选择方向 仍然将标准SURF匹配时间记为t,假设模板 图像划分的行和列块数相等,如果不计一致性检验 的时间消耗,则按照双分块方法进行匹配所需要的 平均时间约为: tare5=×s于×ss(o) 假女口Z=k=4,贝0t0.31ts. 5实验评估 实验中采用AMDAthlon64×2Dual4000+ 2.11GHz,1GB为平台,基于OpenCV(intelopen soureecomputervisionlibrary)实现SURF算法. 对于单分块方法,对图5中的T.(66,66)与 S(340,460)进行特征匹配,各种分块方法所对应的 匹配时间分布如表2所示.对于双分块方法,对图 3所示的(280,280)与.s:(420,400)进行特征匹 配,各种分块方法所对应的匹配时间分布如表3 所示 图5匹配实验中的模板图像l'与搜索图像S 通过实验可以看到:采用分块匹配方法后匹配与整体另外从实验均值之间的差异.也看到,采用 时间明显缩短,最快仅为标准SURF匹配时间的分块方法后参与匹配的感兴趣点数目显着减少,这 7.15%;单分块方法中的尺度+1分块与双分块在一定程度上会增大匹配误差,但在宽基线条件下 中的多块匹配方法的匹配点对数目较多,总体匹配图像感兴趣点数目相对较多,此外分块匹配的终止 效果较好.实验中分块匹配与标准匹配相比,坐标条件即阈值本身就是匹配点对的数目,所以能够保 误差不超过3个像素点,角度误差不超过5.,证明证匹配的正确性. 了分块加速方法的有效性.实验中的数据是以测试对象中的一个样本来给 实验中各种分块方法所对应的匹配时间与分析出的,事实上我们以多幅图像及用 基于视频图像的座 中的平均时间存在差异,这是因为匹配时间与模板舱智能辅助训练系统采集到的视频图像序列为对 图像在搜索图像中所处的位置有关,亦即单个样本象进行测试,得到的也是与表中数据相近的结果. 表2单分块中各种分块方法时间消耗分布 模板图像中搜索图像中搜索图像中感兴趣感兴趣点匹配k匹配点对数目总时间 /ms 感兴趣点数目感兴趣点数目点检测时间/ms时间/ms 不分块l632l25l62.9356.0376222.43 简单K分块4633"/498.4736.8244141.65 简单K+1分块46349239.3913.588659.86 尺度+1分块463l9O46.7716.95927O.1O 尺寸与尺度自适应分块 24633832.6514.971859.02 (=1.2,:0.5) 696激光与红外第41卷 表3双分块中各种分块方法时间消耗分布 模板图像中搜索图像中搜索图像中感兴趣感兴趣点匹配f匹配点对数目总时间/ ms 感兴趣点数目感兴趣点数目点检测时间/ms时间/ms 不分块11l027l49l216.70603.67782831.65 单块匹配4429035847.8944.23601O2.33 多块匹配946349239.3913.588659.47 5结论 基于分块的SURF特征匹配方法能够在保证正 确匹配的基础上大幅提高匹配速度,满足了高实时 性图像匹配的要求,但分块并非唯一的加速方法,例 如文献[8]中采用决策树来实现对SURF匹配中的 感兴趣点匹配进行加速,但这种方法需要对分类 器进行训练,并且因其只对SURF中的一个环节进 行加速,只适用于模板图像与搜索图像尺寸都比 较大,感兴趣点数目都很多的情况,所以适用范围 非常有限.另外,通过改变金字塔尺度空间的结 构与描述符的结构来实现加速也是一种值得研 究的方法. 参考文献: [2] [3] KrystianMikolajczyk.CordeliaSchmid.Scale&affinein- variantinterestpointdetectors[J].InternationalJournalof ComputerVision,2004,60:63—86. JimMutch,DavidG,Lowe.Objectclassrecognitionand localizationusingsparsefeatureswithlimitedreceptive fields[J].InternationalJournalofComputerVision, 20o8,80(1):45—57. LengXuefei,LiuJianye,XiongZhi.Areal—timeimage matchingalgorithmfornavigationsystembasedonbifur— cationextraction[J].ActaautomaticaSinica,2007, 33(7):678—682. 冷雪飞,刘建业,熊智.基于分支特征点的导航用实时 图像匹配算法[J].自动化,2007,33(7): 678—682. [4] [5] [6] [7] [8] [9] DavidG,Lowe.Distinctiveimagefeaturesfromscale—in— variantkeypoints,cascadefilteringapproach[J].Interna— tionalJournalofComputerVision,2004,60(2): 91一l1O. HBay,AEss,TTuytelaars,eta1.SURF:Speeded—upro? bustfeatures[J].ComputerVisionandImageUnder? standing,2008,110:346—359. JBauer,NSunderhauf,PeterProtze1.Comparingseveral implementationsoftworecentlypublishedfeaturedetec— tors[C]//ProceedingoftheInternationalConferenceon IntelligentandAutonomousSystems,Toulouse,France, 2OH07. QiaoYongjun,XieXiaofang,ShiLei,eta1.Designofthe intelligentaidedtrainingsystemforcockpitbasedonvide— Oimage[J].Laser&Infrared,2010,40(3):277—281. (inChinese) 乔勇军,谢晓方,时磊,等.基于视频图像的座舱智能 辅助训练系统 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 [J].激光与红外,2010,40(3): 277—281. MLanger,KD,Kuhnert.Anewhierarchicalapproachi'n robustreal—timeimagefeaturedetectionandmatching [C]//PatternRecognition,the19InternationalCon~r- encePatternRecognition,Florida,USA,2008:1—4. GaoJian,HuangXinhan,PengGang,eta1.Simplified SIFtfeaturepointdetectingmethod[J].ApplicationRe— searchofComputers,2008,25(7):2213—221. 高健,黄心汉,彭刚,等.一种简化的SIFY图像特征点 提取算法[J].计算机应用研究,2008,25(7): 22】3—221.