基于SURF和改进RANSAC的视频拼接算法

陈雪涛，穆春阳，马　行（北方民族大学信息与通信研究所，宁夏银川　750021）



基于SURF和改进RANSAC的视频拼接算法

陈雪涛，穆春阳，马行
（北方民族大学信息与通信研究所，宁夏银川750021）

摘要：在传统的视频拼接算法中，配准的误差和运动的物体都会使拼接结果产生鬼影，而复杂的融合算法又难以满足实时性要求。针对上述问题，以平行光轴且光心位于同一水平基线位置的双目相机采集的视频图像为研究对象，提出一种基于限定区域和SURF算法的视频拼接方法。针对采集到的具有20%～30%重叠感兴趣区域（ROI）的视频图像，每24帧设置一个关键帧，仅对关键帧的ROI区域采用SURF算法寻找特征匹配点对。然后采用改进的RANSAC算法筛选单应性变换矩阵H，对非关键帧直接采用此单应性变换矩阵H进行图像融合。实验结果表明，采用关键帧计算特征点的方式得到的视频拼接效果能够很好地消除鬼影，同时也能够保证视频融合的实时性。

关键词：视频拼接；ROI；关键帧；RANSAC

0　引　言

人们获取信息的方式多种多样，例如通过触觉、视觉、嗅觉和听力等，其中视觉是最直接也是最广泛的获取信息的方式之一。在现代社会中，人们通过视觉获取大量有用信息。由于人的视角或者机器的视角范围有限，因此，对多个视频进行拼接并形成大视角范围的图[1]，这有着非常重大的研究意义。视频拼接技术在许多方面有着重要的应用，例如环境监测[2]、监控系统[3]和生物工程[4]等。

当前视频拼接的方法多种多样，文献[5]采用一种改进的快速检测Harris算子，结合捆绑调整进行全局调整方法，能够得到很好的拼接效果。文献[6]提出了基于图像分块和邻近角点剔除策略的自适应Harris角点检测算法，该算法能很好地适应图像拼接。文献[7]对图像进行SIFT特征提取并进行粗匹配，再用RANSAC方法剔除误匹配点获得变换单应阵，最后用查表法投影图像，最终实现融合拼接。文献[8]在SIFT提取不变特征向量过程中加入Harris算子，运用KLT跟踪算法，精确特征点的位置，提高了图像拼接的稳健性和快速性。文献[9]提出基于SURF和动态ROI方法的视频图像快速拼接方法，获得较清晰的宽敞景视频。基于以上所有视频拼接方法，有的算法比较复杂，运算量巨大，会消耗大量时间，不利于实时视频拼接；有的算法拼接效果不是很理想，会产生明显的鬼影，影响了拼接效果。针对上述2个问题，在SURF算法的基础上，提出了改进的拼接算法，最终效果比较理想。

1　视频拼接算法分析

在这里，首先设定平行光轴且光心位于同一水平基线位置的双目相机采集到图像的重叠部分在20%～30%之间。由于人眼的视觉暂留现象这里引入关键帧，既每24帧视频设置一个关键帧，关键帧和非关键帧采取不同的算法步骤。整个算法流程可分为A、B、C和D四个部分，如图1所示。

图1　视频拼接算法流程框图

图1中：A部分主要是获取视频文件并且设置一些参数；B部分是对关键帧在重叠区域的ROI中用SURF算法生成特征描述算子，从而生成匹配点对；C部分是用改进的RANSAC算法筛选匹配点对并生成最终的变换矩阵H；D部分是图像帧的融合形成拼接图像。

当获取双目相机采集到的视频数据之后，对于第一帧视频，在前面限定的ROI区域内，利用SURF算法找出两帧的特征匹配点对，再利用改进的RANSAC算法筛选出单应性变换矩阵H，之后在变换矩阵H基础上利用融合算法拼接两帧图像形成拼接图，而对于非关键帧，在此直接采用前面利用SURF算法对关键帧处理后生成的变换矩阵H来融合。

1.1SURF算法分析

SURF算法由Herbert Bay等提出的具有尺度和旋转不变性的算法[10]，其具体步骤如下：

（1）Hessian矩阵（SURF算法的核心），设图像像素为I(x，y)，则H矩阵可表示为：

式中：Lxx，Lyy和Lxy分别是图像在x方向、y方向和xy方向的二阶高斯滤波。通常Hessian矩阵的特征值用H矩阵的近似判别式表示为：

式中，α为权系数，这里根据计算取α=0.9，可以根据此特征值的符号将所有点分类。

（2）利用Hessian矩阵公式计算两帧图像中的限定区域ROI中所有点的特征值。在不同尺度空间下的高斯滤波图像中，将像素点I(x，y)的特征值与三维空间下该点周围及上下两层共26个点的特征值进行比较，把其中最大值或者最小值保留下来，作为一个特征点。

（3）根据特征点的Harr小波特性，统计出每一个特征点的主方向。以特征点I(x，y)为中心，以6s（s为特征点所在的尺度）为半径，统计出圆中60°扇形区域的所有特征点的Harr小波特征总和，然后以一定角度旋转，遍历整个圆形区域，把最后得到的Harr小波特征总和最大值的扇形区域的方向作为特征点I(x，y)的主方向。

（4）在前述基础上构建特征描述算子。以特征点I(x，y)为中心，以上一步求出的主方向为方向，构建一个边长为20s（s为特征点所在的尺度）的正方形区域，并把该正方形均分成16个小区域，并统计每一个小区域中25个像素点的Harr小波特征，分别求出水平方向、垂直方向、水平方向绝对值、垂直方向绝对值之和，由此可以生成一个64维的特征向量描述子。

（5）最后，生成了每帧图像ROI区域的所有特征点描述算子的两个集合，A和B，可以寻找出特征匹配对。这里采用欧式距离法，即选取集合A中的一个特征向量，采用遍历法，利用式（3）计算其与集合B中距离最近的两个点，如果次近距离除以最近距离小于一定阈值，则判定为匹配点对：

式中：n=64；xi1表示第一个点的第i维坐标；xi2表示第二个点的第i维坐标。

1.2改进的RANSAC算法介绍

计算出所有匹配点对后，采用改进的RANSAC算法计算仿射变换矩阵H，详细步骤如流程图2所示。

改进的RANSAC算法流程可分为A，B两部分，A部分是在上面SURF算子粗匹配的点对中依顺序选取一匹配点对，把匹配对中特征点主方向和长度都匹配的点保留下来，而不符合的匹配点对都舍弃，直到检测完所有特征点匹配对。假设(Pi，Qi)是一对匹配对，Pi和Qi分别表示两帧图中的对应特征点，Pdx和Pdy分别表示Pi点Harr小波响应在水平和垂直方向上的矢量分量，Pθ表示Pi点的方向角，则Pθ表示为：

特征点Pi方向矢量的长度Plength表示为公式（5）：

同理，Qdx和Qdy分别表示Qi点Harr小波响应在水平和垂直方向上的矢量分量，Qθ表示Qi点的方向角，则有Qθ表示为公式（6）：

特征点Qi方向矢量的长度Qlength表示为：

当两个特征点的方向角之差的绝对值|Pθ- Qθ|小于某一设定阈值ε，且特征点方向矢量长度之差的绝对值|Plength- Qlength|小于某一设定阈值δ时，保留这对匹配对，否则舍弃匹配对。

图2　改进的RANSAC算法流程图

接下来在B部分中，从筛选后留下的匹配点对中随机抽取4个匹配点对，把这些特征匹配点对代入变换模型计算出仿射变换矩阵H，这里在齐次坐标系下两幅图像之间的变换模型可以用下式来表示：

式中：（x′，y′）∈I1和(x，y)∈I2（I1，I2分别表示图像1和图像2）；h1，h2，h4和h5是旋转和尺度变换因子；h3是水平位移因子；h6是垂直位移因子；h7，h8是水平和垂直方向的变形量。重复此步中的B部分N次，找出满足迭代计算矩阵最多的特征匹配对，利用这些特征匹配对计算出最终的仿射变换矩阵H。此改进的RANSAC算法能够去除大部分外点，保留下来的内点比例进一步提高，最终计算出稳定的H矩阵，很好地消除了拼接鬼影。

1.3图像的融合

当计算出正确的仿射变换矩阵H后，参考图像帧位置不变，对待匹配图像用矩阵H进行相应的变换。通常，融合方法有平均值法、加权均值法和最大值法等，此文采用渐入渐出加权均值法，具体融合方法用公式（9）表示：

式中：I(x，y)表示融合后的帧图像像素点；I1(x，y)和I2(x，y)分别表示待拼接的帧图像像素点；w1和w2表示重叠区域对应像素点的权值，且有w1+ w2=1，0≤w1≤1，0≤w2≤1。假设两帧图像重叠区域的宽度为L，重叠区域左边界起始位置为Xstart，则w1可表示为：

即待拼接图像I1(x，y)中的像素点的权重与当前处理点距重叠区域左边界的距离成反比。

2　实验结果及分析

实验的测试平台为CPU IntelⓇCore（TM）4 i5⁃3470 CPU@ 3.20 GHz，内存8 GB，软件开发环境为Qt+OpenCV 2.4，采用的源视频分辨率为480×360。经过实验，把一般的SURF+传统RANSAC算法（以下称为算法一）和本文所采取的SURF+改进RANSAC算法（以下称为算法二）进行了比较，结果如下所述。

本实验选取两段视频作为分析对象，统计了视频一和视频二采用传统算法一和本文算法二所找到的匹配点对数（如图3所示）和拼接一帧关键帧图像所耗费时间总和（如图4所示）。图3（a）、（b）两图分别是视频序列一和视频序列二的前400帧中关键帧的配对数统计结果图。由图3可知采用本文算法二找到的匹配对数比采用传统算法一找到的匹配对数有所减少，说明本文算法能够剔除部分传统算法中的误匹配点对数，有助于提高计算H矩阵的精度，同时也能够减少改进RANSAC筛选H矩阵所消耗的时间。

图3　视频序列关键帧配对数目统计图

图4（a）、（b）中两图分别表示视频序列一和视频序列二的前400帧中关键帧的拼接耗时统计图，从图4中可以看出拼接一帧关键帧，算法二耗时更少，经计算，算法二的平均效率为算法一的1.5～2倍，本文算法在耗时性能上相比算法一来说有所提高，这有助于提高实时视频拼接的性能。一融合的效果，可以看到明显的模糊重影；而图7（b）中黑色方框圈出的重叠区域部分是使用本文算法二融合的效果图，对比来看，其中黑色圈出的部分算法二的融合效果明显好于算法一。

图7　视频序列一拼接效果图

图4　视频序列关键帧耗时统计

本文只对关键帧进行特征点匹配，随机选择了视频一中的2个关键帧和视频二中的2个关键帧进行分析，根据本文改进后的RANSAC算法处理之后找到的精确匹配点对，如图5（a）、图5（b）所示，两图分别是视频序列一第1帧和第264帧的匹配对图，图6（a）、图6（b）两图分别是第1帧和第432帧的匹配对图，从图6中可以看出在设定的ROI区域内，即图6中黑色方框区域内，经筛选后的匹配对效果不错；同时经过大量实验证明，本文算法找到的特征点匹配对效果优于一般算法。

图5　视频序列一第1帧和264帧匹配图

图6　视频序列二第1帧和432帧匹配图

下面分别随机选取两个视频序列中的一帧图像进行分析，图7（a）、（b）分别是使用传统算法一和本文算法二对视频序列一中第72帧拼接后的效果图，其中图7（a）中黑色方框圈出的重叠区域部分为使用算法

图8（a）、（b）分别是使用传统算法一和本文算法二对视频序列二的第1帧拼接后的效果图，可以明显看出图8（a）中黑色方框圈出的大树部分比较模糊，这是拼接重影；而图8（b）是使用本文算法二对视频序列二拼接后的效果图，其中黑色方框圈出的部分比图8（a）中对应的部分效果要好，因此可以断定本文算法在消除重影方面要优于一般的算法。

图8　视频序列二拼接效果图

同时，本文统计了使用算法二时视频序列一中前144帧中关键帧和非关键帧的耗时，具体如表1所示。

表1　关键帧和非关键帧的拼接耗时统计　s

由表1可知，共统计了N=144帧的耗时情况，其中6个关键帧的总耗时T0=1.917 2 s；138个非关键帧的总耗时T1=4.169 2 s，所以总耗时T= T0+ T1=6.086 4 s，平均每一帧约耗时Tm=T/ N =0.042 26 s，而一般视频播放速率在24帧以上，也即每一帧需要用时在0.041 667 s左右，所以根据本文统计的视频帧耗时时间，基本吻合，满足实时性要求。

3　结　论

本文基于限定重叠ROI区域，提出了基于SURF算法的改进方法，利用改进的RANSAC算法，快速地找到了ROI区域中的匹配点对，节省了大量的匹配时间，同时和传统的方法相比较，本文算法在消除鬼影方面有了较大进步，能够很好地去除鬼影。再者，采用了关键帧技术，对关键帧和非关键帧采取了不同的算法步骤，避免了每一帧都进行特征点匹配而产生的时间冗余，大大的提高了实时性，所以本文采取的方法对视频拼接技术的研究及应用有一定的参考价值。

参考文献

[1]ZENG Lin，DENG Dexiang，CHEN Xi，et al. A self⁃adaptive and real⁃time panoramic video mosaicing system [J]. Journal of computers，2012，7（1）：218⁃225.

[2]ZHU Zhigang，RISEMAN E M. HANSON A R，et al. An effi⁃cient method for geo⁃referenced video mosaicking for environ⁃mental monitoring [J]. Machine vision and applications，2005，16（4）：203⁃216.

[3]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.

[4]VAN REIN H，SCHOEMAN D S，BROWN C J，et al. Develop⁃ment of low⁃cost image mosaics of hard⁃bottom sessile commu⁃nities using SCUBA：comparisons of optical media and of proxy measures of community structure [J]. Journal of Marine Biological Association of United Kingdom，2012，92（01）：49⁃62.

[5]王小强，陈临强，梁旭.实时全自动视频拼接方法[J].计算机工程，2011，37（5）：291⁃292.

[6]赵万金，龚声蓉，刘纯平，等.一种自适应的Harris角点检测算法[J].计算机工程，2008，34（10）：212⁃214.

[7]刘畅，金立左，费树岷，等.固定多摄像头的视频拼接技术[J].数据采集与处理，2014，29（1）：126⁃133.

[8]尚明姝.基于改进SIFT特征匹配的快速图像拼接算法[J].微电子学与计算机，2014，31（1）：64⁃67.

[9]首照宇，欧阳宁，张华俊，等.基于SURF和动态ROI的实时视频拼接[J].计算机工程与设计，2013，34（3）：998⁃1003.

[10]BAY Herbert. Speeded⁃up robust features（SURF）[J]. Com⁃puter vision and image understanding，2008，110（3）：346⁃359.

[11]宋翔.基于Director的动画创作技术研究[J].现代电子技术， 2011，34（8）:108⁃110.

Video stitching algorithm based on SURF and improved RANSAC

CHEN Xuetao，MU Chunyang，MA Xing
（Institute of Information and Communication Technology，Beifang University of Nationalities，Yinchuan 750021，China）

Abstract：In the traditional video stitching，the calibration error and the motion of an object may cause the ghost shadows in stitching results. In addition，the complex fusion algorithm can’t meet the real⁃time requirement. In order to solve the above problems，the video images acquired by binocular camera that has a parallel optical axis and its optic center is at the same hori⁃zontal baseline are studied，and a new method of real⁃time video stitching based on limited region and SURF algorithm is put for⁃ward in this paper. A key frame is set per 24 frames for the video images with 20%～30% overlap area in ROI area. the SURF al⁃gorithm is used to look for the feature matching point pairs in the ROI overlap area of key frame only. The homography transfor⁃mation matrix H is selected with the improved RANSAC algorithm，and then the image fusion is executed for non⁃key frames by using the transformation matrix H directly. The experiment results show that the video stitching algorithm proposed in this paper can eliminate the ghost shadows well，also can ensure the real⁃time performance of video.

Keywords：video stitching；ROI；key⁃frame；RANSAC

中图分类号：TN911.72⁃34

文献标识码：A

文章编号：1004⁃373X（2016）10⁃0044⁃05

doi：10.16652/j.issn.1004⁃373x.2016.10.012

收稿日期：2015⁃09⁃19

基金项目：国家自然科学基金项目（61162005，61163002）；机器人技术与系统国家重点实验室开放研究基金课题（SKLRS⁃2013⁃MS⁃05）

作者简介：陈雪涛（1987—），男，河南信阳人，硕士。研究方向为信号检测与信息处理。穆春阳（1975—），男，黑龙江人，副教授，博士。研究方向为嵌入式系统与智能控制。马行（1980—），女，宁夏银川人，副教授，博士。研究方向为视频图像处理。