基于Harris和最佳缝合线的图像拼接算法

万俊1李志永1施沛妍2黄玉春2闫忠凯3

摘要：图像拼接是图像处理技术的一个重要内容，是一种将多张有衔接重叠的图像拼成一张高分辨率图像的技术。该技术广泛应用于显微图像分析、数字视频、运动分析、医学图像处理、虚拟现实技术和遥感图像处理等领域[1]。本次方法探究是为满足不同形态的工件图像拼接要求，得到拼接影像量测工件尺寸，从而对图像拼接技术做深入探究，提出基于棋盘格标定板角点检测图像拼接的处理方法。探究基于棋盘格标定板角点特征的图像拼接技术，利用RANSAC算法提高关键点匹配度，然后为消除拍摄角度产生的尺寸误差，对拍摄的图像进行透视变换，最后基于C++编程实验实现透视变换后两张图像拼接过程，实验结果证明了拼接方法的可行性及有效性。

关键词：特征检测匹配；RANSAC；最佳缝合线图像拼接；透视变换；

0引言

图像拼接是一个日益流行的研究领域，它已经成为照相绘图学、计算机视觉、图像处理和计算机图形学研究中的热点话题。图像拼接所要解决的问题一般表现为通过对齐一系列的空间重叠图像构造一个无缝的高清晰度的图像，它具有比单个图像更高的分辨率和更大的视野[2]。对于这些有重叠部分的图像，一边通过两种方法获得：一种是固定照相机的转轴，然后绕轴旋转所拍摄的照片；另一种是固定照相机的光心，水平摇动镜头所拍摄的照片[3]。其中前者主要是用于远景或遥感图像的获取，后者主要用于显微图像的获取还有一种方法是针对于工件测量的拍摄方式，将相机放于工件上方水平移动拍摄，将拍摄的照片拼接起来。它们共同的特点都是获得二维图像，但通常由于机械或者场景的不理想导致各衔接图像不能完全匹配，因此这给拼接图像环节带来了严重问题。

为此，本文就图像拼接出现的严重问题，为了满足不同形态的工件图像拼接要求，提高拼接的精度，提出一种基于棋盘格标定板角点检测特征匹配的拼接方法。

1工件图像特征点检测

完成高分辨率图像拼接的第一步是选择准确度较高的图片配准方法，这样才能找出图片中的关键点(即特征点)[4]。本算法目的在于，利用工件图片，计算出工件的实际尺寸。在计算过程中，存在由图片像素尺寸到实际尺寸的转换过程，因此在工件图片中要有一个实际长度已知的标定板来求得像素尺寸与实际尺寸的转换关系，所以选择尺寸已知的棋盘格标定板作为参考。另外，由于单纯工件图片缺少特征点以及工件表面粗糙，本文选择以棋盘格标定板上的角点作为图像变换以及拼接的特征点。准确无误的找到棋盘格内部角点的位置是本文研究的第一个重要的问题。当今的角点检测算法有好多种，而Harris角点检测算法是最简单易行的方法。

1.1角点检测

角点是图像很重要的特征，对图像图形的理解和分析有很重要的作用。目前的角点检测算法可归纳为3类：基于灰度图像的角点检测、基于二值图像的角点检测、基于轮廓曲线的角点检测。基于灰度图像的角点检测又可分为基于梯度、基于模板和基于模板梯度组合3类方法，其中基于模板的方法主要考虑像素领域点的灰度变化，即图像亮度的变化，将与邻点亮度对比足够大的点定义为角点。常见的基于模板的角点检测算法有Kitchen-Rosenfeld角点检测算法，Harris角点检测算法、KLT角点检测算法及SUSAN角点检测算法。和其他角点检测算法相比，SUSAN角点检测算法具有算法简单、位置准确、抗噪声能力强等特点。而黑白棋盘格模板角点检测算法又可以分为两大类：第一类是基于图像边缘的角点提取算法；第二类是基于图像灰度的角点检测算法。基于边缘的角点检测算法的基本思想是：角点首先是一种边缘上的点，是一种特殊的边界点。该算法的主要缺点就是对边缘提取算法依赖性较大，如果提取的边缘发生错误或是边缘线发生中断，将会对角点的提取结果会造成很大的影响。基于图像灰度的角点检测算法所提取的角点是图像上某点的局部范围内灰度和梯度变化剧烈的点。该算法简单易行，在实际工作中得到了广泛的应用。

1.2Harris角点检测原理

角点不仅可以说成灰度和梯度变化剧烈的点，也可以说成是信息含量很高的点。检测出来的这些点对以后的相机标定和图像匹配尤为重要。在一幅图像当中，Harris角点检测算法认为角点与自相关函数的曲率特性有关。

本文所使用的角点检测算法是Harris角点检测算法，该算法的基本原理是选择一个目标像素点，并选取一个以该目标像素点为中心的小窗口，计算出窗口沿任何方向移动后的灰度变化，并用解析形式表达。假设以像素点(x,y)为中心的小窗口在x方向上移动u，y方向上移动v，Harris给出了灰度变化度量的解析表达式为：

来判断这个点是不是角点。其中det(M)是求M方阵的行列式的值，trace(M)是求M方阵对角线上元素之和，K就是Harris角点检测算法的一个经验值，一般取0.04，本实验中K=0.04。确定阈值大小，并进行非极大抑制，非极大抑制窗口的大小可以多试验几次进行确定，本文选取的非极大抑制窗口大小为3*3。利用find(result==1);语句来确定角点的位置，进而统计出角点的个数。利用plot(posc,posr,'r*')来标注显示出来的角点。利用disp(c)函数将获得的角点坐标c显示在屏幕上，并将坐标c保存为一个txt文档中。

2影像平面恢复

为了保证后面尺寸量测的准确性，需要确保电力线夹影像垂直于主光轴。而一般来说，由于线夹固定位置不准，相机固定不准等原因，线夹影像很难保证一定垂直于主光轴，从而变成一个斜视影像，导致后面尺寸检测出现较大误差。所以将线夹影像平面恢复成垂直相机主光轴的状态，变得十分重要。

本研究对其恢复的方法是，通过对检测到的特征点进行筛选，得到棋盘格的所有角点（如图1所示，棋盘格内有7*4共28个角点），并且已知实际棋盘格角点之间的物理尺寸，建立影像中棋盘格角点和实际棋盘格角点的之间的单应性，就可以将棋盘格恢复成垂直相机主光轴的状态。

斜视棋盘格正视棋盘格

图2棋盘格平面恢复示意图

图3影像平面恢复实验结果

3RANSAC算法

3.1RANSAC算法简介

由于噪声等诸多误差不能保证关键点匹配的准确性，所以要对匹配结果继续筛选。这里，需要一种能分辨错误配对的数据处理算法，这里，我们选用随机抽样一致性(RANSAC)[8][9]，一种对包含错误信息数据集进行重复提取并计算出最适用数据转换的数学处理方法来完成精匹配，在本图像处理中，合乎RANSAC的数据点是内点，不符合模型的数据点是外点，RANSAC在排除外点得到具有高准确度的内点之后，再计算出体现源图像和带配准图像匹配关键点的坐标变换矩阵。

把RANSAC利用在关键点精匹配中，对应的数学流程为：在源图片与待配准图片中存在N对正确配对的关键点对，同时也存在不正确的匹配对，不妨设所扫描到的全部关键点集合是P，此集合P中包括正确匹配和偏差匹配对。要实现关键点在两幅图像中的转化，对应像素点应该通过包括m=8个数值的转换矩阵H来实现，即源图片的像素点乘以矩阵H得到配准图像像素点坐标。由于图像发生的改变会比较复杂，计算一次转换矩阵H至少需要n=4对匹配点进行计算。这样每次随机选择4对匹配点以计算矩阵H。

详细就算过程如下：1、开始从全部匹配集合P中选择n组匹配点。2、通过随机抽取的n组匹配点得到初始转换矩阵H。3、对于P中剩下的N-n对匹配点计算出与转换矩阵的位置关系，若距离大于某一临界值T，则纳入到外点集合，剩余的其他匹配点均纳入到内点的集合u，得到内点总数C。4、对上述步骤123进行重复计算K次。5、把k次计算集合u中内点最多的一次(即c最大)计算结果定义为正确匹配对组q。6、利用上一步得到的集合q计算出最终转换矩阵H。

3.2RANSAC算法效率

在描述了RANSAC计算原理之后，由RANSAC所确定的最终转换矩阵H无疑会增加总体计算复杂度。计算过程主要集中在三个变量上：划分关键点属于内外点的临界值T，重复计算内点集合次数k和正确匹配点对N的大小。

3.2.1划分关键点属于内外点的临界值T

RANSAC计算过程中每次取n对匹配点计算出转换矩阵H，在验证转换矩阵是否适合所有关键点时定义的临界值T是重要的参数，若大于临界值则判定匹配点有误差，若在临界值之内则判定属于内点并纳入到内点集合进入下一步运算，因此临界值T的选择极为重要，临界值的选择很大程度上决定了最终转换矩阵的参数。在本匹配点提纯过程中用RANSAC计算不同情况，临界值T的大小要进行实际分析，不同的要求下定义不同的临界值能够解决不同的问题。

3.2.2重复计算内点集合次数k

最好的采样是选择的所有关键点都是内点，这样我们得到的转换矩阵H是最准确的。但实际情况下，在不清楚内点集合的情况下我们不得不对所有点都进行验算。若W定义某一次随机抽取到内点的概率，那么1-Wn表示n个关键点中至少有一个是外点的概率，(1-Wn)k是k次采样中每次是外点概率的乘积。并且1-p表示七次采样中都最多有一个内点的概率(理论上的)。若要(1-Wn)k<1-p成立。即：

3.2.3正确匹配点对N

在重复扫描得到不同的转换模型中，能够找到完全匹配内点集合的矩阵是最优的选择。如果某次扫描中得到了一个转换矩阵，使用关键点匹配点数目是t，定义全部集合

里出现误差关键点匹配对的概率是y，若要计算错误矩阵的内点越少越可靠，即：

式中，y0的值一般取0.05，y0取值的变化对结果的可靠性有很大干扰，虽然越小准确度越高，但也会有适配的数据点太少的情况。

4最佳缝合线

4.1最佳缝合线算法

两幅图像完成配准后下一步就是拼接。传统的像素加权拼接方法虽然快捷方便，但拼接域容易出现重合鬼影等问题，毕竟在拼接域边缘没有平滑处理。为消除传统图像融合产生的鬼影问题，本系统采用最佳缝合线算法以解决这一现象。

最佳缝合线的原理是在两幅图像的重叠区域，计算出一条拼接线，使拼接线两侧像素点分别来自同一幅图像，属于动态规划处理的数学模型[10][11]。我们要搜寻的最佳缝合线所处的像素点应该是两幅图片最接近的位置，这种接近可以用几个因子来量化，一个是拼接线附近像素点色彩差值最小，另一个是拼接线附近描述物体几何构造最相通。遵循这两条要求，学者们提出了很多计算最佳缝合线的算法并取得了不错的效果。

Duplaquet于1998年在吸收了多种缝合线算法特点之后，提出了同时考虑到图像色彩区别和构造不同的缝合线的算法：

式中I1和I2分别表示待拼接的两幅图像，E(x,y)dif代表两幅图像中拼接域的色彩区别，Eedge(x,y)表示两幅图像中拼接域的结构差异。

这种最佳缝合线的算法原理考虑到了图像的色彩区别和构造不同，但渐变因子γ很难确定，并且还存在着诸多的随机因素导致最佳缝合线的最终求解相当复杂。

方贤勇于2005年得到了一种完善的拼接线搜索算法，此方法类似于Duplaquet综合考虑了图像色彩区别和构造不同：

式中Edif(x,y)2和Egeometry(x,y)分别表示待拼接图片的重合部分的色彩区别和构造不同。两者的构造不同Egeometry(x,y)由两幅图像拼接域的梯度乘积来计算得出。上式在得到像素点的梯度值时一般使用的Sobel算子为：

Mills于2009年提出了一类考虑到有曝光区分算子的拼接线搜索算法：

式中Ecolor(x,y)和Egeometry(x,y)分别是色彩区别和构造不同，I1和I2分别是对应像素点的色彩程度，g1和g2是待拼接图像重合部分点(x,y)处的梯度值，α和β是曝光区分因子。

这种最佳缝合线计算方法虽然解决了曝光不同带来的拼接线结果不同的问题，却忽略了拼接域中图像的平滑性，这样式中的α和β很难得到，同时也有计算效率偏低的问题。

本系统利用这样的缝合线搜索算法：

式中Egray(x,y)2和Egeometry(x,y)分别表示待拼接图片相同部分的灰度区别(因为处理的是灰度图像，这样可以避免在三个通道上计算色彩的问题，降低计算复杂度)和构造不同，a,b为灰度区别和构造不同的权重值。

如果待拼接图像的曝光度相差很大，渐变因子的值会很大，此时做曝光还原的精确度会有所下降，这样也会导致两幅图像梯度信息更准确，所以不妨把梯度的因子b取值增大。为降低误差，可以先把曝光明显的图像进行处理完成简单的还原在一定程度上减小曝光影像，为降低时间成本选用较快速的数学模型便可完成还原，暂不使用计算更复杂的RANSAC数学模型。得到曝光系数比例K后完成灰度区别和构造不同的计算因子。如果曝光程度相同，可以简单地令灰度信息和结构区分系数相同，数学上表示为若K=1则a=b，此时式35中a,b的取值是：

式中K为待拼接图像曝光系数值，因子a,b变化曲线如图3.1所示。当亮度比值是1时a,b曲取值均为0.5。

上式g1x和g2x为待拼接图像重合部分中每个点在水平上的梯度值，g1y和g2y为待拼接图像重合部分中每个坐标点则是竖直方向梯度。

图4亮度比值和a、b变化曲线

本文提出的最佳缝合线计算方法通过变化的系数因子来使灰度信息和构造差异得以最大程度的体现，并且考虑到了曝光不同给缝合线搜索带来的影像，将灰度、构造、曝光三方面的综合考量，使计算得到的拼接线更加准确和可靠。

4.2最佳缝合线搜索准则

计算最佳缝合线时要根据式19得到拼接域内每个点的色彩差异和构造差异值，这样会得到差分点像素图片。图5是搜索算法图，在计算最佳缝合线的时候，搜寻的方式是每一行进行计算从上到下。在第一行得到缝合线的起始点后，分别比较下一行的距离上一个点最近的三个点，哪个点差值最小则作为下一个延伸点，然后用相同方法计算下一行的拼接点直到最后一行，此时便完成了整个缝合线的搜索过程。

图5最佳缝合线搜索图

利用最佳缝合线最终能把待拼接图像的拼接域分成两块，两块的像素点各属于一张图片。这样可以很大概率的把运动图形保留在拼接线一侧，避免了拼接过程出现的重影问题。当然最佳缝合线也不是完全解决此类问题的最佳算法，如果某一点的选择并不准确，由于向下延伸的算法，不可避免的给延伸点带来误差并持续到最终的拼接点。如果经过图像配准得到的关键点准确性足够高，也就是说关键点是实际中的同一个点，那么也就是差异最小的点，一条拼接线如果由更多的关键点组成我们可以认为这条拼接线可靠性足够高，反之则准确性不足，所以我们可以通过拼接线途径的关键点或者拼接线附近的关键点个数作为拼接线可靠性的量度。RANSAC关键点二次精匹配的办法，可以保证关键点的精确度。那么给关键点附近的拼接线搜索算法值定义一个大于0小于1的系数(本系统设为0.5)来使拼接线纳入或者附近有最多的关键点。并且在拼接线延伸的过程中不妨把3个相邻点变成5个相邻点以更大可能靠近关键点，所以本系统最终采用的拼接线搜索算法总结如下，图6为拼接效果图：

1.差分图像：得到待拼接图像重合部分的差分值，从第一行的每一个点(最好是关键点)作为所有可能拼接线的起点，计算出其差异值，并选取最小差异值的点定义为要搜索缝合线的起始点；

2.延伸：从步骤1里找到的起始点开始向下一行延伸，考虑下一行相邻最近的5个点，如果某一点是关键点可以乘以0.5的因子系数，比较这五个点差异值，选择最小值的点作为下一行的延伸点，重复此方法直到得到最后一行像素点的拼接点；

3.最佳缝合线：把在每一行确定的拼接点连起来就可以得到最佳缝合线。

图6拼接效果图

5总结

继续深入探究了基于Harris角点检测算法的图像拼接技术，利用RANSAC算法提高关键点匹配度，然后为消除传统融合出现的重影问题提出缝合线的拼接方法，最后基于Opencv编程实验实现整个拼接过程，证明了拼接方法的可行性及有效性。

参考文献：

[1]蔡丽欢,廖英豪,郭东辉.图像拼接方法及其关键技术研究[J].计算机技术与发展，2008，18（3）：1-4，20.

[2]王俊杰,刘家茂,胡运发,于玉.图像拼接技术[J].计算机科学,2003(06):141-144+150.

[3]MoitraaD,GaneshbJ.Webservicesandflexiblebusinesspro-cesses:towardstheadaptiveenterprise[J].Information&Management,2005,42:921-933.

[4]温江涛，王伯雄，秦矗．基于局部灰度梯度特征的图像快速配准方法[J]．清华大学学报(自然科学版)，2009,49(5)：673-675.

[5]陈贤巧．基于特征的图像配准算法研究[D]．中国科学技术大学，2009．

[6]何敬，李永树，李歆，唐敏．基于点特征和边缘特征的无人机影像配准方法[J]．西南交通大学学报，2012，47(6)：955-961.

[7]LoweD．DistinctiveImageFeaturesfromScale-InvariantKeypoints[J]．Inte-rnationalJournalofComputerVision,2004，60(2)：91-110．

[8]陈付幸，王润生．基于预检验的快速随机抽样一致性算法[J]．软件学报，2005，16(8)：1431-1437．

[9]单欣，王耀明，董建萍．基于RANSAC算法的基本矩阵估计的匹配方法[J]．上海电机学院学报，2006(8)：66-69．

[10]葛仕明，程义民，李杰．基于梯度场的拼接缝消除方法[J]．计算机辅助设计与图形学报，2007，19(2)：232-239．

[11]宋利，周源华，周军．基于复小波变换的图像镶嵌[J]．上海交通大学学报2005，39：178—181+186．

Imagestitchingmethodforworkpiecesizemeasurement

(WanJunLiZhiYongShiPeiYanHuangChunYuYanZhongKai)

Abstract:Imagesplicingisanimportantcontentofimageprocessingtechnology,anditisatechniqueofmergingmultipleoverlappingimagesintoonehigh-resolutionimage.Thistechniqueiswidelyusedinmicroscopicimageanalysis,digitalvideo,motionanalysis,medicalimageprocessing,virtualrealitytechnology,andremotesensingimageprocessing[1].Thismethodistomeetthedifferentrequirementsofthestitchingoftheworkpieceimage,toobtainthemeasuredimagesizeofthestitchedimage,soastomakeanin-depthexplorationoftheimagestitchingtechnology,andtoproposeaprocessingmethodbasedoncheckerboardcalibrationboardcornerdetectionimagestitching.Exploretheimagemosaictechnologybasedoncheckerboardcalibrationplatecornerfeatures,useRANSACalgorithmtoimprovethematchingofkeypoints,andthenusetheRANSACalgorithmtoeliminatethesizeerrorcausedbytheshootingangle,performperspectivetransformationonthecapturedimage,andfinallyimplementtheperspectivetransformationbasedontheC++programmingexperiment.Twoimagesstitchingprocess,theexperimentalresultsprovethefeasibilityandeffectivenessofthestitchingmethod.

Keywords:featuredetectionmatch;RANSAC;beststitchimagestitching;perspectivetransformation;

作者简介：万俊，1989年出生，男，工程师，学士学位，现就职于广西电网有限责任公司北海供电局，从事变电检修专业的研究。