采用SURF特征的图像拼接融合算法

基金项目：中国科学院知识创新工程重要方向项目（KGCX2-YW-148）作者简介：梁艳菊（1985-），女，博士研究生，主要从事图像拼接、目标识别方面的研究工作。采用SURF特征的图像拼接融合算法梁艳菊1苏君2陈大鹏1(1中国科学院微电子研究所，北京,100029；2电子科技大学光电信息学院，成都，610054)【摘要】提出了一种采用SURF(SpeededUpRobustFeatures)特征的快速图像拼接融合算法。该方法利用SURF算子提取特定区域的图像特征；采用K-dimensional树最近邻搜索算法实现图像特征的精确高效匹配；利用RANSAC(随机抽样一致性)算法消除误匹配，优化图像空间透视变化参数；最后根据变换参数对齐图像，采用渐入渐出的图像融合方法实现图像的拼接。实验结果表明，图像拼接效果良好，鲁棒性强,在时间效率上优于其他算法。关键词图像拼接；SURF特征；K-dimensional树；图像融合中图分类号TP391文献标识码:AImageMosaicAlgorithmUsingSURFFeatureLIANGYan-ju1,SuJun2andCHENDa-peng1(1InstituteofMicroelectronics,ChinaAcademyofSciences(IMECAS),Beijing100029;2UniversityofElectricScienceandTechnologyofChina,SchoolofOptoelectronicInformation,Chengdu610054)AbstractAnfastimagemosaicschemebasedonSURFfeatureisproposed.Inthisscheme，SURF(SpeededUpRobustFeatures)isappliedtoextractfeaturesfromtheimages;K-dimensionaltreenearestneighborsearchingmethodisadoptedtomatchtheinterestpointsfastandprecisely;RANSAC(RANdomSAmpleConsensus)isexploitedtoeliminatethemismatchedfeaturepointsandoptimizetheperspectivetransformationparameterbetweentheimages;Gradatingin-and-outamalgamationalgorithmisusedtofusedtheimagetogetheratlast。Experimentalresultsshownotonlytherobustnessandvalidityoftheproposedschemebutalsobettertimeefficientperformance.Keywordsimagemosaic;SURFfeature；K-dimensionaltree;imagefusion图像拼接技术可在不降低图像分辨率的条件下获取大视野场景图片，克服鱼眼镜头等设备的不足，能应用于多种场景，已成为图像处理、计算机视觉等领域的重要研究课题[1]。其中，基于特征的图像拼接技术具有时间效率高，匹配精度高，鲁棒性好等优点，研究和应用较广泛[2,3]。常用于图像拼接的特征点提取方法有：Harris[4]、SIFT[5,6]、SURF[7]等。其中，SIFT算法是一种鲁棒性好，具有尺度不变性的角点检测方法，但SIFT计算数据量大、时间复杂度高。SURF算法较之SIFT在计算速度和鲁棒性上有较大改进。基于SIFT算法的图像拼接[8]系统拼接效果好，但计算量大，时间复杂度高。基于SURF特征的图像拼接算法在时间复杂度上有所降低，但仍然无法满足对图像拼接的实时性要求较高的应用场合。为提高图像拼接系统的时间效率，文中提出了一种基于SURF特征的具有较高时间效率的图像拼接融合方法。利用SURF算子提取图像特定区域的特征点，并引入K-D（K-dimensional）树最近邻搜索算法进行特征点匹配，提高了图像拼接的时间效率。1SURF特征提取SURF是一种特征点提取算法，性能接近SIFT，计算速度提高了近3倍。SURF算法可分为两部，特征点检测与特征点描述符表示。1.1SURF特征点检测SURF特征点检测在积分图像[9]上进行。积分图像用符号()Ix表示。积分图像上点(,)Xxy处的值代表以图像原点(0,0)和点X为对角顶点组成的长方形中的像素总和：()(,)00jyixIxIijij(1)Fast-Hessian[7][10]矩阵的定义为：(,)(,)(,)(,)(,)xxxyxyyyLxLxHxLxLxsssss=轾犏犏臌(2)式2中(,)xxLx是图像在点X处灰度值与二阶高斯微分函数的卷积。(,)xyLx，(,)yyLx含义与之类似。采用框状滤波器近似高斯微分函数，得到Fast-Hessian矩阵：(,)(,)(,)(,)(,)xxxyapproxxyyyDxDxHxDxDx(3)其中approxH的行列式为：2det()(0.9)approxxxyyxyHDDD(4)为使SURF特征点具有尺度不变性，用不同尺寸的框状滤波器对原始图像进行滤波处理，组成滤波金字塔，如图1a所示。图1b是SIFT滤波金字塔的生成方式。二者对比可以看出SURF对同一尺寸图像进行处理，可以并行计算,提高了时间效率。(a)SURF算法滤波金字塔(b)SIFT算法滤波金字塔图1SURF算法和SIFT算法滤波金字塔[9]初始尺度框状滤波器与图像卷积得到尺度空间的第一层，尺寸逐渐增大的滤波器与原始图像卷积生成下面的图像层，四个图像层构成一阶（Octave），一般取四阶。根据Fast-Hessian矩阵行列式的阈值，检测图像满足阈值要求的点，然后在该点周围的26个点范围内进行非最大化抑制，得到特征点集，最后进行三维二次插值，对特征点实现亚像素级定位。图像拼接融合一般在存在重叠区域的图像间进行。为提高时间效率，根据摄像头摆放位置，文中算法对特征点提取的区域进行了限制，均对包含重叠区域的半边图像进行了特征提取。1.2SURF特征点描述符的表示兴趣点描述符的提取分为两步，首先给特征点分配一个方向，然后生成描述符向量。在以特征点为圆心，半径为6（为尺度）的圆内，计算尺寸为4的Harr小波响应,xydd，对,xydd进行高斯加权（2）。用角度为/3的扇形区域绕特征点旋转一周，计算扇形在每个角度时的xydd。xydd最大时的方向为特征点的方向，如图2所示。图2特征点方向指定选定方向，以特征点为核心，构建一个大小为20的正方形窗，与特征点对齐。将这个正方形窗划分为4*4个小正方向区域，计算每个小区域内的,xydd，并用高斯函数（3）进行加权。每个小区域内的描述符如式5所示：Desc_squrexyxydddd=V（、、、）(5)Desc_squre是四维向量，4*4个小区域就组成了特征点的64维描述符向量。2特征点匹配特征点匹配目的是找到两幅图像中表示相同物理位置的特征点，形成特征点匹配对。文中采用K-D树[10]算法对两幅图像提取的特征点进行快速最近邻搜索，进行最近邻次近邻比值判别，实现特征点的匹配,计算仿射变换矩阵。K-D最近邻搜索算法充分利用K-D树的特点，大幅度提高了搜索效率。最近邻的判别标准是欧式距离最短，特征欧式距离定义为：6421(1,2)1()2()iddescdescdescidesci(6)desc1(i),desc2(i)分别表示两幅图像Image1，Image2中特征点描述符desc1,desc2的分量。2.1K-D树最近邻搜索64-D最近邻搜索算法是一个递归的算法，在64-D树上进行。用64维的特征点描述符组成64-D搜索树。SURF特征点的64-D树的每一个节点都是64维的数据，组成一个64维超空间。每个节点都可以看作一个分裂超平面，将64维超空间分为两个子超空间。分裂超平面轴的选择从第1维轴到第64维轴为一个循环，最后所有的特征点都被插入到64-D树中。为提高计算效率，避免开方计算，欧式距离直接用其平方代替。算法的执行如下：1.从根节点开始往下搜索子树。2.如果搜索到叶子节点，存储该叶子节点为当前最近邻点currentbest。3.在每个节点上首先判断计算当前节点与目标节点的距离，如果当前节点与给定的目标点的距离更小，则更新currentbest。然后判断以目标节点为中心，以当前最佳距离为半径的子超空间是否与分裂超平面相交。若相交则搜索右子树，否则忽略右子树，继续搜索。4.最后算法在根节点上完成上述步骤。2.2最近邻次近邻比值判别在匹配过程中，图像的视角不同，景物范围也不同，或是两幅图像之间存在缩放关系，这些情况都有可能导致图像Image1中的特征点在Image2中没有匹配点。当Image1和Image2中存在邻域灰度信息分布比较相似的点时，也会产生匹配错误。为避免上述错误的发生，检测最近邻与次近邻的比值，检测方法可表示为：ThresholdmatchsuccessThresholdmatchfailedFNDSNDFNDSND(7)其中最近邻距离表示为FND(FirstNearestDistance)，次近邻距离表示为SND(SecondNeighborDistance）。经过上述步骤，两幅图像SURF特征点匹配完成。3变换矩阵参数计算假设两幅图像间存在仿射变换关系，则图像Image1和Image2中的一对匹配点111(,)pxy222(,)pxy间变换关系为式8，9。111121322121222322100111xhhhxxyhhhyHy(8)111212213121222223xhxhyhyhxhyh(9)为了提高H矩阵中参数估计的精度，排除可能存在的误匹配点影响，文中采用RANSAC随机采样一致算法来估计H。RANSAC[11]分为三步进行：第一步随机选取3组匹配点，估计H的六个参数；第二步利用估计的参数对余下的匹配点进行判断，区分出内点和外点集，记录内点集的数量，用新内点集重新估计参数；第三步，当内点数目最大时，在该内点集上给出H的最佳估计。4图像对齐得到图像的变换参数后，需要将图像对齐，变换到同一坐标系下。选择一副图像作为基准图像，将另外一幅图像根据其变换参数进行仿射变换。为保证图像变换后清晰度，对变换的图像进行插值。常用的插值方法有最近邻插值、双线性插值、立方卷积插值[12]，其中双线性插值折衷性能和时间效率最为常用，文中也采用该方法。5图像拼接融合图像的拼接融合时将配准后的图像根据其对应关系合并为一幅图像。一般情况下，由于采样时间、采样角度、光照强度等因素影响，直接拼接会使两幅图像重叠区域出现明暗强度差异，拼接处出现明显的拼缝，因此采用渐入渐出的方法对图像进行融合。假设待拼接的两幅图像用12,II表示，融合后的图像用I表示，融合公式为：11121222,,,,(1),,,,,IxyxyIIxyIxyaIxyxyIIIxyxyI(10),0,1iwW，其中iw为当前像素点与两幅图像重合区域左边缘的横向距离，W是两幅图像重合区域的总宽度。从0均匀变化到1，1-从1均匀变化到0，实现了拼接图像的平滑过渡。6性能测试测试在MicrosoftVisualC++2010，MATLAB2010R2010a环境,PentiumDual-coreE5500CPU,主频2.79GHz，内存2GB的主机上进行。测试图片来自于多幅用摄像机拍摄的中国科学院微电子研究所图片，尺寸统一为400*256。测试首先验