摘  要： 提出了一种基于视频序列拼接的新方法。首先，利用KLT算法对视频序列中特征点进行提取和跟踪，实现关键帧粗略选取；其次，在选取的关键帧中利用SURF算法进行特征提取，利用最近邻距离比进行特征点匹配，通过RANSAC估计算法求精单映矩阵，并结合关键帧选取判定寻找最佳关键帧；最后，利用级联单映矩阵和加权融合算法实现视频序列拼接。实验验证了该方法的有效性。
关键词： KLT算法；关键帧；SURF算法；单映矩阵

　图像拼接是构建高分辨率大场景的关键技术，在虚拟现实场景表达、计算机视觉、全景图绘制中有着重要应用，也是计算机图形学领域中研究热点[1]。视频序列拼接是由多帧视频序列拼接而成的完整全景图像，在视频监控、医学图像处理、遥感图像处理等方面得到广泛应用[2]。
　在视频序列的拼接中，相邻帧间重叠部分较大，若每相邻帧都做一次拼接，不仅耗费大量时间，而且随着所需拼接帧数量增多，匹配误差会增大，造成拼接效果不佳。利用关键帧拼接表示整个视频序列拼接成为有效的方法。参考文献[3]提出SIFT结合Kalman跟踪算法进行关键帧的提取及拼接的实现，由于视频序列帧数量较大，而SIFT算法本身复杂，SIFT对每一帧都进行处理，累积造成运算时间比较长。参考文献[4]提出利用分层式自适应帧采样的视频拼接，但这种方法的计算量大，算法限制条件较多，容易导致拼接失败。参考文献[5]提出采用四叉树方式来解决重叠区域大小确定问题，但是没有从根本上解决大量视频序列拼接时匹配误差增大的问题。针对以上问题，提出了一种新的视频序列拼接算法，可以有效提取关键帧，利用关键帧拼接表示整个视频序列拼接，从而节省视频拼接时间。首先，利用KLT算法对视频序列中每帧特征点进行提取，并通过特征点的跟踪实现进行关键帧粗略选取。其次，在选取的关键帧中利用SURF算法进行纹理特征提取，并利用最近邻距离比进行特征点匹配[6]，通过估计算法求精单映矩阵，结合关键帧选取判定寻找最佳关键帧。最后，通过RANSAC级联单映矩阵和加权融合算法实现拼接，取得较好效果。

　在关键帧选取效果不好的情况下，非相邻关键帧数量比较多，容易造成匹配误差增大。为了进一步减少关键帧的数量，减小单映矩阵级联时造成的误差，通过如下比较进行运算，进一步提取关键帧，从而完成关键帧的选取判定。具体步骤为：
　(1)设定第k帧、第h帧为非相邻的关键帧，直接计算两关键帧单映矩阵Hk，h；
　(2)将单映矩阵级联方法和直接计算单映矩阵方法计算出来的结果进行比较，比较h0、h1、h2、h3、h4、h5、h6、h7值的误差大小，只要有一项数值超过预定的阈值，则认为第h帧的前一项关键帧是须保留的，第k帧和第h帧前一项关键帧作为保留关键帧，两者之间的其他关键帧可以省略。
2 关键帧的提取方法
2.1 KLT特征点跟踪算法
　由于视频序列帧与帧之间的冗余较大，考虑采用KLT特征点跟踪算法来实现关键帧的粗略选取。KLT算法是以待跟踪窗口在视频图像帧间的灰度差平方和作为度量的跟踪算法[8]。对于相邻视频帧I和视频帧J中的两个窗口，直接的SSD为：

　利用计算Z的特征值，选取两个特征值比较大的点作为跟踪的特征点，在选定的特征点基础上再利用Zd=e可以计算出特征点的漂移。跟踪停止条件是特征值小于规定的最小特征值以及迭代次数超过设定次数。
2.2 SURF特征提取算法
　KLT特征点跟踪算法有较高的求解效率，但是对纹理变化复杂的情况，常由于误匹配而造成被跟踪点的丢失。因此，利用上述KLT特征点跟踪算法提取关键帧后，对关键帧再利用SURF算法进行特征点的提取，为后续提取最佳关键帧提供有效方法。
　SURF算法利用快速Hessian检测算法提取特征点[9]，Hessian矩阵具有良好的计算时间和精度表现。
　SURF特征描述子的提取可以分为两步：(1)根据特征点周围的一个圆形区域找到特征点的主方向；(2)在选定的主方向上构建一个矩形区域，并提取所有的特征描述点信息。在主方向上构建一个大小为20δ的窗口(δ表示尺度)，并将该窗口区域分为4×4的子区域，对于每一个子区域，分别计算相对于主方向的水平和垂直方向Haar小波响应，每个子区域得到4维向量，因此4×4的子区域得到64维特征点描述子，它可以扩展到128维的特征点描述子，一般采用128维特征点描述子。
3 拼接算法的实现及实验结果
3.1 拼接方法的实现

　按照上述所述，拼接的具体实现步骤如下：
　(1)为了选取关键帧子序列，使全景图内容丰富，第一帧和最后一帧为必选关键帧，选取第一帧视频序列关键帧为基准帧，提取基准帧的特征点。
　(2)利用KLT算法进行特征点的提取并跟踪，从而确定粗略的关键帧，具体如下：
　①假设选取的特征点个数为N，比例因子为α，对视频序列经过特征点跟踪，当特征点个数减至αN时，停止跟踪，选取当前帧为关键帧，并作为后续跟踪的基准帧；
　②重复上述过程，直至视频序列跟踪完毕，最后获取粗略视频关键帧，对原始视频帧图像进行跟踪，计算量较大，为减少计算量，利用高斯图像金字塔，并通过插值获取原始视频帧中特征点[10]。
　(3)利用SURF算法对关键帧提取特征点，采用最近邻距离比进行特征点匹配，并利用帧间单映矩阵模型和关键帧选取判定方法进行优化的关键帧选择。具体如下：
　①利用SURF特征点提取算法对步骤(2)选定的关键帧进行特征提取；
　②对相邻关键帧利用帧间单映矩阵模型进行匹配计算。为了使单映矩阵H的估计准确，利用RANSAC鲁棒估计方法得到相邻关键帧之间单映矩阵H的估计，具体步骤为：
　(a)随机抽取n≥4对匹配特征点来估计矩阵H的参数；
　(b)对于步骤(2)中的每一对匹配点，计算对单映矩阵H的拟合误差；
　(c)设定一个门限值，若拟合误差小于此门限值，表示匹配点对是一致点，并统计一致点的数目；
　(d)重复步骤(a)~(c)，直到所有的一致点集中至少有一个有效表征集的概率大于一定的数值为止；
　(e)选择具有最大一致点集的单映矩阵H。
　③对非相邻关键帧利用单映矩阵的级联性进行计算，利用关键帧选取判定方法进一步得到选定关键帧。
　(4)将步骤(3)选定的关键帧作为最终拼接的关键帧，利用单映矩阵级联和加权融合算法完成视频序列的拼接。
3.2 实现结果
　实验采用自拍的两段视频，利用上述方法完成了视频序列的拼接，效果比较好。
　图2所示是将拍摄的一段200帧的视频利用上述方法获取的最终关键帧，其拼接效果图如图3所示，剪切处理后的视频序列拼接最终效果图如图4所示。
　图5是自拍的一段350帧的视频，利用上述算法获取的关键帧，视频拼接效果图如图6所示，剪切处理后视频序列最终拼接效果图如图7所示。

　本文采用了一种新的视频序列拼接方法，利用KLT特征点跟踪算法实现粗略关键帧的选取，再次利用SURF特征点提取算法结合最近邻距离比匹配方法、关键帧判定准则，对关键帧进行进一步提取，并利用RANSAC估计算法对单映矩阵进行求精，通过级联单映矩阵和加权融合算法实现视频序列拼接，取得了较好效果。
参考文献
[1] KIM D H， YOON Y I， CHOI J S. An efficient method to build panoramic image mosaics[J]. Pattern Recognition Letters，2003，24 (1)： 2421–2429.
[2] SHUM H Y， SZELISKI R. Panoramic image mosaics[R].TechnicalReport， MSR-TR-97-23， Microsoft Research， Redmong， WA， USA， 1997：1-3.
[3] FADAEIESLAM M J， FATHY M， SORYANI M. Key frames selections into panoramic mosaics[C]. Proceedings of the 7th International Joint Conference on Information，  Communication and signal， Macau， 2009.
[4] 刘永，王贵锦，姚安邦，等.基于自适应帧采样的视频拼接[J].清华大学学报(自然科学版)，2010，50(1)：108-112.
[5] BABU D R R， RAVISHANKAR M. Automatic seamless image mosaicing： an approach based on quad-tree technique[C]. Proceedings of the World Congress on Engineering， University of Oxford， UK， 2010，London，UK.
[6] LOWE D G. Distinctive image features from scale-invariant key points[J]. International Journal of Computer Vision， 2004，60(2)：91-110.
[7] HARTLEY R， AISSENRMAN A. Multiple view geometry in computer version[M]. Cambridge， UK： Cambridge University Press， 2000.
[8] TOMASI J S C. Good features to track[C]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition，  Seattle， WA， USA，1994：593-600.
[9] BAY H， TUYTELAARS T， GOOL L V. SURF：speed up robust features[J]. Computer Science， 2006，3951(1)：404-417.
[10] SINHA S N， FRAHM J M， POLLEFEYS M， et al. Feature tracking and matching in video using programmable graphics hardware[J]. Machine Vision and Applications， 2007， 22(1)： 207-217.