图1 视频拼接算法流程
Fig.1 Video mosaic algorithm flow
程德强1， 厉航1， 黄晓丽1， 屠屹磊1， 游大磊2
(1.中国矿业大学 信息与控制工程学院， 江苏 徐州 221116； 2.河南应用技术职业学院 信息工程学院， 河南 开封 475001)
摘要：为了解决实时视频拼接中的鬼影和拼接缝问题，提出了一种基于改进随机抽样一致算法的实时视频拼接算法。首先，针对双目摄像头的重叠区域，采用加速鲁棒特征算法提取特征点，寻找特征匹配点对；然后利用改进的随机抽样一致算法去除误匹配点对，获得最优单应性矩阵；最后，对重叠区域像素进行动态融合处理。实验结果表明，采用本文算法可以有效地消除视频重叠区域的拼接缝和鬼影，同时可保证视频拼接系统的实时性。
关键词：全景图像； 视频拼接； 随机抽样一致算法； 加速鲁棒特征算法； 最优单应性矩阵； 动态融合
全景图像被广泛应用于视频监控、虚拟现实、环境监测等领域[1]。随着数字监控系统的发展，对全景动态图像的实时视频拼接技术提出了更高的要求[2]。全景图像生成以后，在重叠区域会有明显的拼接缝、模糊和鬼影[3]。针对拼接缝和鬼影问题，已有相关学者进行了研究，并取得了一定成果[4]。文献[5]提出了一种基于RANSAC(Random Sample Consensus，随机抽样一致)算法的柱面全景图拼接方法，该方法计算简单，运行速度快，但是求取的参数误差很大，导致拼接出的全景图质量不佳。文献[6]提出了一种基于SURF(Speeded-Up Robust Features，加速鲁棒特征)和改进RANSAC 的视频拼接算法，该算法结合传统融合算法，在一定程度上改善了拼接图的质量，但容易受运动物体的影响，不能准确实现全景图拼接。文献[7]对含有运动目标的视频进行研究，提出了动态视频拼接技术，但该技术要求场景中的运动目标很小，否则不能处理视频序列图像。文献[8-9]提出了基于泊松融合和寻找最佳缝合线的图像融合算法，该算法虽然抑制了鬼影的生成，但是计算量大，实时性不佳。
针对上述问题，本文提出了基于改进随机抽样一致算法的视频拼接算法。通过迭代的方法检测和剔除外点数据，对RANSAC算法进行改进，获得了更为可靠的最优单应性矩阵，提高了算法精确度。通过动态融合算法对重叠区域像素进行融合处理，解决了运动目标穿过重叠区域时产生的鬼影问题。
1.1 算法流程
基于改进随机抽样一致算法的视频拼接算法流程如图1所示。
图1 视频拼接算法流程
Fig.1 Video mosaic algorithm flow
视频拼接具体步骤：
(1) 提取双目摄像头视频帧，并判断其是否为关键帧。
(2) 对关键帧进行SURF特征提取[10]，生成特征描述算子，从而生成匹配点对。
(3) 利用改进的RANSAC算法筛选匹配点对，剔除误匹配点，从而获得最优单应性矩阵。
(4) 在最优单应性矩阵基础上，利用动态融合方法对视频帧进行融合，并获取最终的拼接图像。
设定双目摄像头位于同一水平面，且重叠区域约为30%。考虑到特征检测阶段耗时较长，若对每帧图像都应用特征检测后再进行融合拼接，则不能实现实时拼接。因此，引入时间间隔，即先对首帧图像进行SURF 特征检测和匹配，计算出比较稳定和准确的投影变换矩阵[11-12]，然后将该投影变换关系应用到后续的帧图像的拼接中。为了克服拍摄过程中的不确定因素和对首帧图像计算不精确带来的累积误差，以一定的时间间隔再进行特征提取、匹配和求取投影变换矩阵，然后再应用到后续一段时间的帧图像拼接中，最后可获得准确性较高的实时动态拼接视频。
1.2 SURF算法
构建全景图像的第1步是图像配准。目前的配准方法主要包括基于像素法、变换域法和基于特征的配准方法。基于特征的配准方法鲁棒性高，适应性强，因此，被广泛应用于拼接实现中。基于特征的配准方法主要包括特征提取和特征匹配。目前主流的特征提取算法有SIFT算法和SURF算法等。研究结果表明，SURF算法至少比SIFT算法快3倍以上，综合性能优于SIFT 算法，因此，本文采用SURF算法提取匹配点对。
SURF算法步骤：
(1) 构建积分图像。积分图像定义:点x的积分图像为该点与原点形成的对角点构成的矩形域方框内全部像素值灰度值总和。积分图像I∑(x,y)公式为
(1)
式中：I(x,y)为原图像；x,y分别代表像素点横坐标、纵坐标。
(2) 建立图像金字塔。SURF算法利用盒子滤波器与图像进行卷积来建立尺度空间，通过改变盒子滤波器的尺寸来获得不同尺度的图像，从而建立图像金字塔。
(3) 用Hessian矩阵检测极值点。利用Hessian矩阵计算出重叠区域内所有点的特征值；然后在3×3立方体内将检测的特征点与自身尺度层中其余8个点和在其之上及之下的2个尺度层的18个点，共26个点进行比较，将极值点保留下来作为特征点。 Hessian矩阵公式为
Det(Hs)=DxxDyy-(0.9Dxy)2
(2)
式中：Det(Hs)代表Hessian矩阵行列式；Dxx，Dyy，Dxy分别代表高斯滤波后图像在各个方向的二阶导数近似值。
(4) 确定特征点主方向。在以特征点为中央的圆周内，按一定行进步长，每次计算60°扇形范围里的各点在x，y方向上的Haar小波响应，Haar小波响应的尺寸为4s(s为该特征点所属空间尺度)。遍历整个圆形区域，选择最长向量的方向为该特征点的主方向。
(5) 生成特征描述子。以主方向为指导旋转图像系，取特征点作为正中央，开设边长为20s的正方形区域，并将该空间切割成4×4的子块；再计算各子块中的每点经重定义图像系后，据中央特征点发散的高斯加权的Haar小波响应；最后统计出每个子块的x，y方向上的Haar小波响应和∑dx，∑dy，∑|dx|，∑|dy|，得到一个包含4个数据的4维向量。依次对每一小块进行处理，最后获得一个64维的向量，将该向量作为特征点的唯一描述子。
1.3 改进RANSAC算法
提取SURF特征点后，利用改进的RANSAC算法进行特征点提纯[13]，并计算最优单应性矩阵H。对于传统的RANSAC算法，当数据集中存在较多的误匹配点即外点时，算法的迭代次数会增加，很大程度上降低了算法执行效率，导致单应性矩阵精度不高。因此，本文从检测和剔除外点方面对RANSAC算法进行改进。
改进的RANSAC算法在粗匹配点对中顺序选取匹配点对，并计算其空间相似度，当相似度高于设定阈值时保留该匹配点对，反之，则舍弃，直至检测完所有匹配点对。
根据相机的成像原理，相关的2幅图像中，任意正确匹配的匹配点对应存在相似的空间关系。在平面图形中，为确定某一点的唯一位置，至少需要其他不共线的3个点。假设(P1,Q1)，(P2,Q2)，(P3,Q3)，(P4,Q4)为4对匹配点对，Pt和Qt (t=1,2,3,4)分别表示2帧图中的对应特征点；Pt，Qt中任意3点不共线；d(P1,P2)，d(P1，P3)，d(P1，P4)分别表示P1与P2，P3，P4之间的距离；d(Q1,Q2)，d(Q1，Q3)，d(Q1，Q4)分别为Q1与Q2，Q3，Q4之间的距离。现引入空间相似度λ=min
，当λ小于某一设定阈值时，认为(P1,Q1)匹配度过低，将其判定为误匹配点并剔除，反之，则认为(P1,Q1)为正确匹配点。以此方法遍历两视频帧中的各匹配点对。
考虑到双目视频拼接，2幅图像之间的变换情况可用如下矩阵来表示：
(3)
式中：(x′，y′)和(x，y)分别代表2个视频帧中的点；m0，m1，m3，m4代表尺度和旋转量；m2代表水平方向位移；m5代表垂直方向位移；m6和m7代表水平与垂直方向的变形量。
式(3)所示的单应性矩阵有8个自由度，要确定其参数至少需4对匹配点，即要获取4对匹配点才可得到投影变换矩阵。
从筛选出的匹配点对中随机选取4对，代入变换模型计算得出单应性矩阵H，然后用得到的模型去测试所有的其他数据。如果某个点适用于估计的模型，认为它也是局内点，并将其标记。
重复上述步骤N次，提取被标记次数最多的内点，并将其作为最终的匹配点集，用所选取点集中的匹配对重新计算单应性矩阵，从而得到最终的参数估计值及最优单应性矩阵。
1.4 动态融合算法
传统的图像融合算法中，在执行图像融合之前，通常会先进行寻找最佳缝合线的处理，以获得最优或局部最优缝合线[14]。但是在本文工作中，该步骤会与接下来进行的融合过程冲突，因此，本文略过了最佳缝合线寻找处理，直接进行图像融合。
常用的图像融合方法有最大值法、简单平均法、加权平均法、多分辨率法、渐入渐出法[15]。渐入渐出法公式为
(4)
式中：f(x,y)为融合后图像中各像素点信息；I1(x,y)为第1幅图中各像素点信息；I2(x,y)为第2幅图中各像素点信息； b为当前像素点与重叠区域右边缘的距离与重叠区域宽度的比值。
在一般情况下，利用式(4)可以取得很好的融合效果，但当有运动目标穿过重叠区域时，仍会产生鬼影。为解决该问题，本文提出了一种动态融合算法。首先利用背景消除算法提取运动目标并记录其位置；其次，重叠区域的2幅图像中，某一图像的像素当优于另一图像，以减少鬼影的生成；同时，在图像左右边缘处应设定一缓冲区，以避免明度突变。
含运动目标的图像融合如图2所示。
图2 含运动目标的图像融合
Fig.2 Image fusion with moving objects
改进后的图像融合公式为
(5)
式中：w为重叠区域左边缘至目标左边缘的距离；i1为重叠区域内当前像素点所在列，0～w-1。
由于a1和a2区域的颜色与运动目标不同，所以需对a1和a2区域进行进一步融合，融合公式为
(6)
式中j1为重叠区域当前像素所在行；n=1,2;n=1时，hn为物体上边缘到重叠区域上边缘的距离，n=2时，hn为物体下边缘到重叠区域下边缘的距离。
当对a1区域融合时，j1取值范围为0～h1-1；当对a2区域融合时，j1取值范围为h2-1～0。
硬件平台主要包括1台计算机、2个普通USB 摄像头(感光元件为CMOS，500万像素，最大分辨率为800×600，最高视频采集帧率达30 帧/s)，软件平台为Microsoft Visual Studio 2010和开源的计算机视觉库OpenCV。
2.1 改进的RANSAC算法实验
针对双目摄像头视频1分别用原始RANSAC算法和改进RANSAC算法提纯，统计提纯后内点对数目和提纯耗时。在提取首帧最优单应性矩阵后，以1 min的间隔对后续视频帧进行处理。表1为用2种算法对视频1前3 min进行处理的效果比较。
表1 2种算法效果比较
Table 1 Effects comparison of two algorithm
分析表1可知，对于相同的初始点集，采用改进RANSAC算法能够剔除更多的误匹配点，获取准确率更高的内点，比原始RANSAC算法有更高的去误率，这有利于获取更高精度的单应性矩阵。同时，改进RANSAC算法提纯耗时更少，其效率比原始RANSAC算法提高了约15%，这有利于保证视频拼接系统的实时性。
2.2 摄像头视频拼接结果实验
随机提取双目摄像头同一时刻视频1和视频2中的1帧图像，如图3所示，分别对其进行原始RANSAC算法提纯普通融合、改进RANSAC算法提纯普通融合、改进RANSAC算法提纯动态融合，实验结果如图4所示。
(a) 待拼接视频帧1
(b) 待拼接视频帧2
图3 待拼接视频帧
Fig.3 Video frame to be spliced
(a) 原始RANSAC算法结合普通融合算法拼接效果
(b) 改进RANSAC算法结合普通融合算法拼接效果
(c) 改进RANSAC算法结合动态融合算法拼接效果
图4 视频拼接效果
Fig.4 Video mosaic effect
图4(a)中，运动目标区域存在明显的鬼影，黑色框内存在可见的拼接缝，拼接效果很差；图4(b)中，鬼影现象有所抑制，黑色框内的拼接缝得到了消除；图4(c)中，鬼影和拼接缝均得到了消除，同时镜头畸变也得到了校正，视觉效果明显优于前2种算法，拼接效果较为理想。
提出了一种基于改进随机抽样一致算法的视频拼接算法，在重叠区域用SURF算法提取特征点后，利用改进RANSAC算法剔除误匹配对，获得了更为可靠的变换模型，即最优单应性矩阵，同时减少了计算变换模型所消耗的时间；对运动目标区域采用动态融合算法进行处理，解决了有运动目标穿过重叠区域时产生的鬼影问题。实验结果表明，运用本文算法可以有效消除图像融合过程中产生的拼接缝和鬼影。
参考文献(References)：
[1] 王小强,陈临强,梁旭.实时全自动视频拼接方法[J].计算机工程,2011,37(5):291-292.
WANG Xiaoqiang,CHEN Linqiang,LIANG Xu.Method of real time automatic video stitching[J].Computer Engineering,2011,37(5):291-292.
[2] 张欣.全景拼接的关键技术研究[D].哈尔滨:哈尔滨工业大学,2009.
[3] 刘畅，金立左，费树岷，等.固定多摄像头的视频拼接技术[J].数据采集与处理，2014,29(1):126-133.
LIU Chang,JIN Lizuo,FEI Shumin,et al.Fixed multi-camera video stitching technology [J].Data Acquisition and Processing,2014，29(1)：126-133.
[4] 郝飞,陈文艺.基于特征点匹配的图像拼接方法[J].西安邮电学院学报,2012,17(1):87-91.
HAO Fei,CHEN Wenyi.Panorama mosaicking on scale-invariant feature transform[J].Journal of Xi'an Institute of Posts and Telecommunications,2012,17(1):87-91.
[5] 黄有群,付裕,马广焜.基于RANSAC 算法的柱面全景图拼接方法[J].沈阳工业大学学报,2008,30(4):461-465.
HUANG Youqun,FU Yu,MA Guangkun.Cylindrical panoramic map mosaic method based on RANSAC algorithm[J].Journal of Shenyang University of Technology,2008,30(4):461-465.
[6] 陈雪涛,穆春阳,马行.基于SURF 和改进RANSAC 的视频拼接算法[J].现代电子技术,2016,39(10):44-48.
CHEN Xuetao,MU Chunyang,MA Xing.Video mosaic algorithm based on SURF and improved RANSAC[J].Modern Electronic Technology,2016,39(10):44-48.
[7] ZHAO Xinbo,ZOU Xiaochun,MA Zhong,et al.An efficient video mosaic panorama algorithm[C]∥International Conference on Information Science & Applications Seoul,2010.
[8] 潘恒辉.图像拼接中鬼影消除算法研究[J].舰船电子工程,2010,30(3):125-128.
PAN Henghui.Research on eliminating ghosting in image mosaic[J].Ship Electronic Engineering,2010,30(3):125-128.
[9] 方贤勇,潘志庚,徐丹.图像拼接的改进算法[J].计算机辅助设计与图形学学报,2003,15(11):1362-1365.
FANG Xianyong,PAN Zhigeng,XU Dan.An improved algorithm for image mosaics[J].Journal of Computer-Aided Design & Computer Graphics,2003,15(11):1362-1365.
[10] BAY H,ESS A,TUYTELAARS T,et al.Speeded-up robust features[J].Computer Vision and Image Understanding,2008,110(3):346-359.
[11] YUAN C H,PAN J S,SHEU M H,et al.Fast image blending and deghosting for panoramic video[C]//Ninth International Conference on Intelligent Information Hiding and Multimedia Signal Processing,Beijing,2013.
[12] GUO K Y,YE S,JIANG H M,et al.An algorithm based on SURF for surveillance video mosaicing [J].Advanced materials research,2011,267:746-751.
[13] 张春雨,王文,邱亚特,等.视频拼接中最优自适应单应性矩阵求解算法[J].吉林大学学报(工学版),2013,43(4):1116-1120.
ZHANG Chunyu,WANG Wen,QIU Yate,et al.Algorithm for optimal homography matrix in video mosaic[J].Journal of Jilin University(Engineering and Technology Edition),2013,43(4):1116-1120.
[14] 邵向鑫.数字图像拼接核心算法研究[D].长春:吉林大学,2010.
[15] 阮芹,彭刚,李瑞.基于特征点的图像配准与拼接技术研究[J].计算机与数字工程,2011,39(2):141-144.
RUAN Qin,PENG Gang,LI Rui.Study on image registration and mosaic technologhy based on surf feature[J].Computer and Digital Engineering,2011,39(2):141-144.
Video mosaic algorithm based on improved random sample consensus algorithm
CHENG Deqiang1, LI Hang1, HUANG Xiaoli1, TU Yilei1， YOU Dalei2
(1.School of Information and Control Engineering, China University of Mining and Technology, Xuzhou 221116, China; 2.College of Information Engineering，Henan Vocational College of Applied Technology, Kaifeng 475001, China)
Abstract：In order to solve problems of seam and ghosting in real-time video mosaics, a video mosaic algorithm based on improved random sample consenus (RANSAC) algorithm was proposed. Firstly, speed-up robust features algorithm is used to extract feature points and find matching feature points in the overlapping area of binocular camera. Then, the improved RANSAC algorithm is adopted to remove the mismatched point pairs and obtain the optimal homography matrix. Finally, the pixels in overlapping areas are processed by dynamic fusion. The experiment results show that using the proposed algorithm can effectively eliminate the seam and ghosting in the video overlapping area, and also ensure real-time performance of the video mosaic system.
Key words：panoramic image; video mosaic; ramdom sample consenus algorithm; speed-up robust features algorithm; optimal homography matrix; dynamic fusion
收稿日期：2017-03-03；
修回日期：2017-06-01；责任编辑：胡娴。
基金项目：江苏省“六大人才高峰”高层次人才培养项目(2015-ZBZZ-009)。
作者简介：程德强(1979-)，男，河南洛阳人，教授，博士研究生导师，研究方向为图像智能检测与模式识别、图像处理与视频编码、多媒体专用集成电路设计，E-mail：chengdq@cumt.edu.cn。
引用格式：程德强，厉航，黄晓丽，等.基于改进随机抽样一致算法的视频拼接算法[J].工矿自动化，2017,43(8)：50-55. CHENG Deqiang, LI Hang, HUANG Xiaoli, et al. Video mosaic algorithm based on improved random sample consensus algorithm[J].Industry and Mine Automation，2017,43(8)：50-55.
文章编号：1671-251X(2017)08-0050-06
DOI：10.13272/j.issn.1671-251x.2017.08.010
中图分类号：TD67
文献标志码：A 网络出版时间：2017-07-27 10:04
网络出版地址：http://kns.cnki.net/kcms/detail/32.1627.TP.20170727.1004.010.html