基于Harris角点和改进SURF描述子的图像快速拼接

杨超　余厚云　刘斌

摘 要： 针对SURF算法计算量大、对应点匹配时间长的不足，以Harris角点取代SURF斑点作为特征点，改进了描述子生成区域的子块划分方式，使区域面积减小40%。同时，引入尺度因子[s]以弥补采样区域减小的影响，形成一种计算量小、独特性好的描述子。以该方法构造的角点特征矢量参与同名点匹配，可实现较好的匹配快速性和准确性。匹配完成后，分别使用RANSAC方法和L?M方法获取变换矩阵并进行非线性优化，最后根据图像的不同区域采用不同方法完成图像融合。实验结果表明，该图像拼接方法与传统SURF法相比，图像匹配时间可节约35%以上，整体图像的拼接时间可节约30%左右，大幅提高了图像拼接的效率。

关键词： Harris角点； SURF描述子； L?M非线性优化； 图像匹配； 图像拼接

中图分类号： TN957.52?34； TP391 文献标识码： A 文章编号： 1004?373X（2015）11?0087?04

Image fast mosaic based on Harris corner points and improved SURF descriptor

YANG Chao， YU Hou?yun， LIU Bin

（College of Mechanical and Electrical Engineering， Nanjing University of Aeronautics and Astronautics， Nanjing 210016， China）

Abstract： Since the shortages of SURF algorithm are the large amount of calculations and long matching time of corresponding points， the Harris corner points are taken as the feature points instead of the SURF spots. The sub?block dividing mode of descriptor generated region is improved， and the region areas are reduced by 40%. The descriptor with little calculated quantity and good peculiarity is shaped by the introduced scale factor s to eliminate the influence of sample region decrease. The corner point characteristic vector parameter structured by the proposed method is matched with the same name point， so rapidity and accuracy of matching are well realized. After matching， RANSAC method and L?M method are respectively adopted to obtain the transformation matrix， and execute nonlinear optimization. Image fusion is accomplished with different methods according to different image regions. The experimental results show that the image mosaic method， compared with the traditional SURF method， can save more than 35% image matching time and about 30% mosaic time of the whole image. The efficiency of image mosaic is greatly improved.

Keywords： Harris corner point； SURF descriptor； L?M nonlinear optimization； image matching； image mosaic

0 引 言

图像拼接是一种将多幅有重叠部分的图像拼成一幅大型无缝高分辨率图像的技术，它广泛应用于照相绘图、医学影像以及视觉测量等领域。图像拼接主要由特征提取、特征描述及匹配、变换矩阵计算和图像融合四个部分组成。特征提取以对特征点的提取为主，提取算法包括以斑点检测与匹配相结合的稳健的SIFT算法[1]、利用积分图像和DoH近似实现快速斑点检测匹配的SURF算法[2]和以角点为特征点的鲁棒Harris角点提取法[3]等。特征匹配是将不同图像中的对应点匹配起来，并尽可能剔除错误匹配点对，它为变换矩阵的计算提供原始数据。变换矩阵是利用若干匹配点计算后经优化得到，图像融合则是指运用线性插值等方法使图像过渡自然、色彩均匀。图像拼接的精度很大程度上取决于特征描述和匹配环节，相应的算法有Lowe提出的SIFT算法、Bay提出的SURF算法以及Mikolajczyk提出的GLOH[4]算法等。然而这些算法均需要对图像进行复杂的预处理以建立图像金字塔等，再通过计算确定特征点，进而建立特征描述子参与匹配。它们虽然匹配效果较好，但运算复杂、耗时长，且特征点不可预测。国内也有研究人员提出基于不变矩结合区域灰度相关性的方法[5]进行特征匹配，然而在缺少更多约束条件的情况下，这些方法匹配效率不高。

事实上，角点作为图像中的重要特征已被人们深入研究，以角点为特征点的特征匹配在图像识别和测量等应用领域逐渐发挥越来越重要的作用。因此，本文提出一种以Harris角点为特征点，以改进的SURF描述子构造角点特征矢量，实现角点快速匹配并最终完成图像拼接的方法。实验结果表明，该方法与传统SURF方法相比，图像匹配效果达到同等水平，而匹配时间可节约35%，整幅图像拼接时间可节约30%以上，大幅度提高了图像拼接的效率。

1 角点特征提取

角点是图像灰度发生剧烈变化或图像边缘曲线上曲率为极大值的点。Harris角点提取算法简单，具有旋转和尺度不变性以及对图像亮度和对比度的部分不变性等优点，使其在图像角点检测方面应用广泛。本文首先将两幅原始图像预处理后以相同参数进行Harris角点提取，并将角点存于两个不同序列中。再用这些角点代替SURF算法中矩阵运算得到的斑点作为图像特征点，使图像匹配的运算量小、速度快。

Harris角点检测[6]过程可归纳为如下步骤：

（1） 计算图像[I（x，y）]的水平和垂直方向的梯度[Ix，][Iy。]

（2） 计算[x，][y]方向梯度乘积[I2x，][I2y，][Ixy。]

（3） 对[I2x，][I2y，][Ixy]使用高斯函数加权生成[M]矩阵元素[A，][B，][C。]

（4） 按下式计算每个像元的Harris响应值[R，]小于阈值[T]的置0。

[R={R：detM-α（traceM）2

式中：det[M=AC-B2，]trace[M]为矩阵[M]的迹；α为经验常数，一般取0.04～0.06。[α]增大则角点检测的灵敏度降低，检出的角点数量减少。[α]减小则角点检测的灵敏度提高，检出的角点数量增多。

（5） 进行邻域非极大值抑制，局部极大值即认为是角点。

2 特征描述与匹配

特征描述子又称特征矢量，它对特征点进行独特性描述。为实现图像旋转不变性，首先根据特征点的局部图像结构求得一个方向基准即主方向，再确定描述子。

2.1 主方向的确定

以Harris角点作为特征点，并以其为中心，对给定半径（文中取12 pixel）的圆形区域内的采样点计算Haar小波响应。然后对小波响应结果进行高斯加权，使角点附近采样点的小波响应值权重大，以弥补仿射不变性的不足。最后依照SURF方法求得特征点的主方向角[θ。]

2.2 特征矢量生成

在积分图像中以特征点为中心取大小为[L×L]的正方形区域[P，]正方形的两条边分别平行和垂直于主方向，[L]为正方形边长，区域[P]即为计算特征矢量的区域。考虑到编程方便，实际计算时先取两边平行于积分图像坐标轴且与[P]等大小的正方形区域[Q，]再按公式（1）对区域[Q]中包含的点做旋转运算，得到其在对应区域[P]附近的坐标。

[xP=x0-Δx?s?sinθ+Δy?s?cosθyP=y0+Δx?s?cosθ+Δy?s?sinθ] （1）

式中：[Δx=xQ-x0，][Δy=yQ-y0；][（x0，y0），][（xQ，yQ）]和[（xP，yP）] 分别为特征点坐标和正方形[Q，][P]内的像元坐标。

同时，为了取得特征点附近尽可能大的区域，在公式（1）中引入了尺度因子[s。][s=1]表示采集区域[P]中所有的像元；[s>1]表示间隔采样，采样区域将大于[P，]系数[s]表征了采样的疏密程度。[s]不宜过大，否则采样点距离远，对特征保持不利。如图1和图2所示，随着[s]的增大，正确角点匹配对数先增后减，而错误匹配点对数有上升趋势。本文中取[s=2.5。]

与SURF法类似，在求沿主方向和垂直于主方向的Haar小波响应时，先求像元水平、垂直方向的Haar响应值，经高斯加权后，再根据公式（2）按主方向对其进行旋转变换。

[dx=ω（-dxPsinθ+dyPcosθ）dy=ω（dxPcosθ+dyPsinθ）] （2）

式中：[（dxP，dyP），][（dx，dy）]分别为区域[P]附近像元旋转前、后的Haar响应。

特征矢量包含信息量的多少和运算量大小，均取决于区域[P]边长的大小。设SURF法所取的正方形区域边长为[L，]本文为降低计算量，取边长[L=3L4。]SURF法在形成特征矢量中的元素时，将[L×L]的正方形划分成均匀的4×4个边长为[L4]的无重叠子块。本文将正方形区域均分成4×4个子块，子块面积与SURF法等大，但由于[L

为避免重复计算，本文先求出[L×L]中所有像元对应的响应[dx，][dy，]再按照子块的划分，分别求出每个子块的4维子块矢量[[Σdx，Σdx，Σdy，Σdy]，]由16个子块得到64维特征矢量，并进行归一化处理。

2.3 对应点匹配

2.3.1 角点初始匹配

图3和图4分别为原始待拼接图像的左、右两图，利用相似性准则依次计算左图角点的特征矢量与右图中全部特征矢量的欧式距离，记录这些欧式距离中最小值所对应的右图中的角点。若欧氏距离最小值与次小值的商小于给定阈值[μ，]则认为该最小值所对应的右图中的角点与左图中当前角点初始匹配成功；否则，认为右图中不存在左图角点的匹配点，舍去左图中当前角点。根据以上算法，从而得到两幅图像角点的初始匹配集合。

2.3.2 匹配点集的提纯

初始匹配集合中必然有误匹配点对，这对求取变换矩阵危害很大。为此，本文采用RANSAC法[7]分两步进行提纯：

（1） 从初始匹配集合中随机抽取4对点，计算出变换矩阵。利用该矩阵将初始匹配集合中图4角点映射到图3，计算映射点与图3匹配点之间的欧氏距离[D，]设置距离阈值[d。]若[D

（2） 以[N]个内点对集合中内点对数最多的集合作为初始内点对集合，重复步骤（1）。此时提纯所用的阈值应小于第一次，以提高精度，完成第二次提纯。以本次提纯后所得内点对数最多的集合所对应的矩阵作为初始变换矩阵。

应该注意的是，由于初始匹配集合中存在一定的误配点对，且抽样次数[N]远小于集合中任意4点对的组合数，因此首次提纯的阈值[d]不应设置得过小，否则会导致首次提纯后的内点对数过小或不稳定。经首次提纯去除大量误配点后，再减小阈值[d]做二次提纯，所得结果较好。

2.3.3 变换矩阵的优化

以上述步骤（2）提纯所得变换矩阵为初始矩阵，利用Levenberg?Marquardt法[8]对其进行非线性优化。图4中的角点[（xri，yri）]与它在图3中的映射点[（x′i，y′i）]之间的对应关系为：

[x′iy′i1=m0m1m2m3m4m5m6m71?xriyri1] （3）

实际情况中，映射点与图3中的匹配点[（xli，yli）]不完全重合。优化目标是求变换矩阵中[m0～m7]组成的向量[m]的最优解，即最优解满足所有图4角点的映射点与图3匹配点之间的欧氏距离和[F（m）]取得最小值。

[F（mk）=in[（xli-xri）2+（yli-yri）2]12] （4）

令[fi（mk）=[（xli-xri）2+（yli-yri）2]14，]则[F（mk）=infi（mk）2=]

[f（mk）Tf（mk）。]公式（4）中，[n]为匹配点对数，[f（mk）=][[f1（mk）， f2（mk），…， fk（mk）]T]为[n]维列向量，[mk]为迭代[k]次后向量[m]的值。Levenberg?Marquardt迭代公式为：

[mk+1=mk+ΔmΔm=-[J（mk）TJ（mk）+uI]-1J（mk）Tf（mk）] （5）

式中：[J（mk）]为[fi]对[m]的[n×8]阶雅可比矩阵；[I]为单位矩阵；[u>0]为比例系数。[uI]的存在可保证[J（mk）TJ（mk）+uI]正定。设置迭代次数[k，]通过调节比例系数[u]使[F（m）]逐步逼近最小值，从而得到最优变换矩阵。

3 图像融合

利用提纯优化后的变换矩阵计算出图4四个顶点映射到图3中的坐标，以确定融合后图像的大小，开辟空白图。先将图3复制到空白图上，再将图4映射到空白图中，两图经融合形成图5。融合过程划分为以下四部分：

（1） 图5中仅属于图3的区域，不进行处理。

（2） 图5中仅属于图4的区域，为避免空像素，采用后向映射的方法处理。即由该区域像素点反求该点映射到图4的坐标，该坐标一般为非整数，采用双线性插值法计算该坐标处的像素值，以该像素值作为图4中对应坐标点的像素值。

（3） 图5中图3、图4都映射不到的区域赋0。

（4） 图5中属于图3和图4映射重合的区域，首先按步骤（2）获得当前位置映射到图4的像素值，将该像素值与对应的图3像素值按该位置离两侧重合区边界的远近进行加权融合，使图像过渡自然。

4 实验结果与分析

本文采用VC++6.0，OpenCV1.1实现变换矩阵的计算和图像拼接融合，采用的原始图像大小为360×480像素，图像拼接的结果如图5和图6所示。从拼接结果看，图6未对变换矩阵进行优化，图像中建筑物右侧有明显放大趋势。而在图5中，变换矩阵经L?M优化后，图像右侧的放大趋势得到很好地抑制。

表1中列出了分别采用本文方法与SURF法进行特征点匹配的效果对比，结果表明两种方法的最终精确匹配点数相差较小，但本文方法匹配时间减少了35%左右，大幅提高了匹配效率。表2中列出了以不同方法完成特征匹配并获得最终变换矩阵的结果以及整体拼接时间。结果表明，本文方法与SURF方法最终得到的变换矩阵十分相近，说明本文方法稳定可靠。整体拼接时间上，本文方法比SURF方法节约30%左右，在拼接速度上有较大优势。

5 结 论

本文以Harris角点为特征点，以改进的SURF描述子构造角点特征矢量，提出了基于Harris角点快速匹配的图像拼接方法，并利用RANSAC法进行二次内点对提纯后，再通过L?M法实现了变换矩阵的非线性优化。该方法在保证匹配快速性和准确性的前提下，弥补了传统方法特征点不可预测的不足。通过特征点匹配和图像拼接实验的结果表明，本文方法对存在尺度变化及拍摄角度差的两幅图像进行拼接，能达到良好的拼接水平。同时，图像匹配时间可节约35%以上，整个图像拼接时间可节约30%以上，大幅提高了图像拼接的效率。

参考文献

[1] LOWE D G. Object recognition from local scale?invariant feature [C]// International Conference on Computer Vision. Greece：IEEE， 1999： 1150?1157.

[2] BAY H， ESS A， TUYTELAARS T， et al. Speeded?up robust features （SURF） [J]. Computer Vision and Image Understanding， 2008， 110（3）： 346?359.

[3] HARRIS C， STENHENS M. A combined corner and edge detector [C]// Proceedings of Fourth Alvey Vision Conference. Manchester： ICASSP， 1988： 147?152.

[4] MIKOLAJCZYK K， SCHMID C. A performance evaluation of local descriptors [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（10）： 1615?1630.

[5] 徐春萍，柴亚辉，李广丽，等.一种基于Harris角点特征精确匹配的图像拼接方法[J].实验室研究与探索，2011（10）：40?43.

[6] 王永明，王贵锦.图像局部不变性特征与描述[M].北京：国防工业出版社，2010.

[7] FISHER M， BOLLES R C. Random sample consensus： a paradigm for model fitting with application to image analysis and automated cartography [J]. Communications of ACM， 1981， 24（6）： 381?396.

[8] 伏燕军，杨坤涛，邹文栋，等.基于Levenberg?Marquardt算法的图像拼接[J].激光杂志，2007，28（5）：46?48.

[9] GUI Yang， SU Ang， DU Jing. Point?pattern matching method using SURF and shape context [J]. Optik? International Journal for Light and Electron Optics， 2013， 124（14）： 1869?1873.

[10] TUYTELAARS T， MIKOLAJCZYK K. Local invariant feature detectors： a survey [J]. Foundations and Trends in Computer Graphics and Vision， 2008， 3（3）： 177?210.