基于相关系数的适用于视频拼接的帧对齐方法

殷兴华

（北京化工大学 信息科学与技术学院，北京100029）

0 引 言

传统的视频拼接在采集视频时需要使用同步触发器来同步两台摄像机启动，本实验中考虑到通用性，未使用同步触发器，而由采集者进行人工的控制。这造成了所获得的两段视频在时间上不是同步的，所以在拼接之前需要进行对帧工作。同时，为了拓展视场，两台摄像机拍摄所获得视频通常具有相对较小的重叠区域 （约1/3左右），这造成了使用传统的视频帧对齐方法［1－3］容易产生严重错误，导致对帧的失败。矩阵间的相关系数能够反映两数字矩阵的相似性，而且计算方法简洁，便于计算机实现，是一种常用的图像匹配方法［4］。相位相关法能够快速的确定两图像间的位移量，适用于拼接图像间交叠区域的界定。本文结合两者特性，并综合运用运动量检测及变步长搜索算法，提出了应用于视频拼接的帧对齐方法，有效的解决了源视频帧序列在时间上不同步的问题，具有很重要的实际意义。

1 方法概述

如图1所示，An和Bn是经由两台摄像机获取的视频帧序列，且具有一定的交叠区域 （阴影区域）。由于采集者不可能十分精确的同时开始采集，所以即使两源视频A和B的帧率相同，视频中第n帧图像也不是同一时刻采集得到的。由于两视频的帧率是已知的，现假设A视频中的第n帧与B视频中的第n＋m帧是同一时刻采集的，所以只要先找到An与Bn＋m的这种对应关系，就可以确定两视频启动时间差，从而得知A，B间帧的对应关系。

图1中虚线所示为两具有交叠区域的两视频，为了找到An与Bn＋m的对应关系，我们需要解决两个问题：①交叠区域的界定。②利用交叠区域图像在相同时间点上的一致性确定对应帧。

图1 帧序列对应

1.1 交叠区域界定

本实验使用相位相关法界定交叠区域，相位相关法利用两次快速傅立叶变换以及一次反变换即可得出冲击函数，确定帧图像间的位移量，具有较好的时效性。但传统相位相关法确定位移量一般是使用在采集时间相同的拼接图片间。本实验中，先使用帧差法寻找视频中运动量最小的时间点［5］。此点附近的帧中含有较少的运动物体，各帧图像之间的变化较小，有利于相位相关法确定两源视频帧图像间的位移。实验证明，使用低运动量点附近的帧图像来进行相位相关法计算所得的位移量能够满足后续算法的要求。

1.1.1 帧差法确定低运动量点

设视频A分辨率为M＊N，时长为n秒，视频帧率μ，则可知第i秒中第二幅帧图像在视频帧序列中的编号为ki＝μ＊ （i－1）＋1。对Aki－1，Aki＋1，计算i时刻的帧差如式（1）［6］所示

从而得到帧差序列Z1，Z2，Z3，…，Zn，取

按照式 （2）定义的规则，得到帧差最小的整点时刻为第i秒。之后再将第i－1秒至第i＋1秒之间的帧图像序列如上计算帧差，得到帧差序列并比较，从而找到帧差最小的帧图像。

本实验中不同运动量时刻所的帧差结果如图2、图3所示。

1.1.2 相位相关法

相位相关法是一种频率域的配准方法，它先利用傅立叶正变换，计算两幅带拼接图像的互功率谱［7］。然后对互功率谱进行傅立叶逆变换，通过互功率谱与冲击函数的关系，求得冲击函数。由冲击函数的峰值便可以得到两幅图像间的位移量［8－9］。如果一幅数字图像分辨率为M＊N，则其像素值可以表示为式 （3）所示二维离散矩阵

现假设帧图像f1和图像f2具备如下平移关系

式 （5）对上述等式进行傅立叶变换

变换可得互功率谱为

式中：F＊——F的复共轭。对其进行傅立叶逆变换得

式 （7）左侧即为所求冲击函数，由其峰值位置可确定两图像平移参数。本实验中，使用帧差法确定的运动量最低点帧图片对进行相位相关计算，所得冲击函数峰值如图4所示。

经实验证明，此方法所求得的位移量能够满足后续计算的要求。取10对交叠区域不同的源视频，通过此方法可得到各对视频的位移量。计算此值与实际位移量的差值，不同交叠区域导致的误差如图5所示。随着交叠区域的增大，位移量的差值减小，当交叠区域大于视频拼接所一般要求的30%时，误差降至30个像素以下，这完全可以满足相关系数计算的要求。

1.2 确定帧对应关系

1.2.1 相关函数

设图像A，B为两幅图像，分辨率均为M＊N。则A，B的像素值二维矩阵可分别表示为f（x，y），g（x，y），其中x＝0，1，2，…，M－1；y＝0，1，2，…，N－1。A，B像素值矩阵的相关系数［10－11］可以定义如下

式中：cov（A，B）——两二维矩阵的协方差，DA，DB——矩阵各自的方差。计算公式为

式 （9）、式 （10）和式 （11）中和分别为A和B像素值矩阵的均值，即两幅源图像的亮度均值。相关系数ρ的取值范围为 ［－1，1］，其值越接近1，说明两幅源图像的相关程度越高，也就说明这两幅帧图像越可能是同一时间点采集到的。

1.2.2 搜索算法

设视频A和B为待拼接的源视频，交叠区域数字矩阵大小为K＊L，视频A由NA幅帧图片组成，帧率为fpsA，B由NB幅帧图片组成，帧率为fpsB。如果直接取视频A中的一帧作为基准帧，在视频B的帧序列中逐一计算相关系数并求取相关度最大的帧，这种方法会产生两个问题。①由于两视频启动与停止时间差的存在，视频A中的某些帧与B中的任何一帧在时间上均不存在对应关系。②对帧图像Ai和Bi进行的相关系数的计算为二维运算，如果对视频B中的每一幅帧图像都与基准帧计算相关系数，这将是一个十分巨大的运算量。所以，为了解决这两个问题，本实验中使用了变步长的搜索查找算法［12－13］。

本文所针对的问题中，在采集视频时，采集者在主观上应尽量减小时间差，即采集者应尽量做到同时启动摄像机。经过多次试验，在此前提下，无论是采用口令由两人启动两台摄像机，还是由一人使用两手启动两台摄像机，摄像机的启动时间差绝对值是存在一个范围的，设此绝对值的最大值为tmax。假设基准帧为A中第i帧，则其对应帧为视频B中的第（i/fpsA－tmax）＊fpsB帧至第 （i/fpsA＋tmax）＊fpsB帧之间一帧。由以上推论可知，视频序列Ai（i＝tmax＊fpsA，…，NA－ （tmax＊fpsA））中任何一帧在视频B中必然存在对应帧，所以在Ai中选择基准帧可以避免第一个问题的出现。

设定初始步长为t0，对 ［tmax＊fpsA，NA－ （tmax＊fpsA）］区间之内的视频A帧图像序列抽样得帧序列Ai（i＝tmax＊fpsA，…，k－t0，k，k＋t0，…，NA－ （tmax＊fpsA））。以相同步长t0对视频B进行采样得视频序列Bi（i＝0，…，k－t0，k，k＋t0，…，NB）。为了更精准的确定对应帧，我们希望选取的基准帧附近的帧序列图片间差距越大越好。因为两相邻帧之间差距的大小决定了两者是否易于区分，在数学上，即各自与基准帧计算所得的相关系数之间差值越大［14］。由第一部分的分析可知，运动量的高低决定了相邻帧之间的差距，所以我们在Ai视频帧序列中取运动量最高的帧 （由1.1.1节中计算所得），设在Ai序列中运动量最大的为第Ak帧。以第Ak帧为中心，缩短步长，取新步长t1（t1＝｜t0/2｜）。对帧图片序列Ai（i＝k－t0，…，k0－t1，k0，k0＋t1，…，k＋t0）如上计算帧差求取运动量最高的帧，设其中运动量最大的帧为As。然后继续如上缩短步长，以第As帧为中心，求取运动量最高的帧……，直至步长为1。假设此时求得的基准帧为Ax。

则最终选定其作为基准帧，对视频序列Bi（i＝0，…，k－t0，k，k＋t0，…，NB）依次计算相关系数，得到以Ax为基准帧的相关系数数列为ρi（i＝0，…，k－t0，k，k＋t0，…，NB），求取

假设取得此最大值的帧在视频B中为第k0帧。然后保持视频A中基准帧不变，缩短步长，取新步长为t1（t1＝｜t0/2｜），以视频B中第k0帧为中心，对帧图片序列Bi（i＝k－t0，…，k0－t1，k0，k0＋t1，…，k＋t0）中每幅图片计算相关系数，求得取到最大值的帧图片为视频B中的第k1帧。然后，继续如上缩短步长，以第k1帧为中心，求取相关系数最大的帧……，直至步长为1，假设此时求得的帧数为kn。

为了提高配准的准确度与可信度，实验中取视频A中运动量最大的三帧Ax1，Ax2，Ax3分别如上计算对应帧数kn。设3次求得的对应帧数分别为kn1，kn2，kn3［15］，则按照式 （13）分别求得的视频对应帧时间差

设如上求得时间差为δt1，δt2，δt3，则最终求的视频A，B时间差为

2 实验结果

为了测试本方法能否实现所需要的对帧功能，实验中采用两台CANON A495相机采集视频。两相机之间距离可调整以改变交叠区域的大小，摄像机的启动与停止由两人手工操作，采取口令的方式人工同步，启动与停止的时间差一般不大于3S。软件运行环境：操作系统：Windows XP 32，内存：2G，CPU主频：2.0GHz。共采集不同类型视频10组，交叠区域所占视频分辨率百分比最低为13%，最高为57%。视频中不同时间段要求具有不同的运动量及场景，以涵盖不同的情况。

下文中，取参数tmax＝3，t0＝10。以交叠区域40%，fpsA＝20，fpsB＝30的源视频对为例。此视频对具有明显不同的光照，远、近境的运动物体，以及树叶的摆动等多种不同特征，具有较好的代表性。运用本方法选取视频A中第80帧、第90帧和第40帧为基准帧，分别求得视频B中于视频A中基准帧对应的3个帧分别为：kn1＝130，kn2＝145，kn3＝69，依式 （13）求得

δt1＝0.333，δt2＝0.333，δt3＝0.300

按照式 （14）可求的视频A与视频B对应帧时间差为δt＝ （0.333＋0.333＋0.300）/3＝0.32 （s）

以10帧为间隔，视频A，B第40～80帧图片序列如图6、图7所示。观察图片可知，视频A中第40帧图片与视频B中第70帧图片为对应帧图片，则两视频时间差为70/30－40/20＝0.33 （s），误差为0.01，小于视频A或B中单帧的时间长度 （0.03）。所以误差在可接受范围内，实现了对帧功能。

同样以初始步长10帧为间隔，视频A，B帧序列中各帧处的帧差运动量及计算所得时间差与实际时间差的差值如表1所示，表2为不同交叠百分比视频最终计算所得时间差与实际时间差的差值对比表。

表1 运动量与时间差对比

表2 交叠区域与时间差对比

经过分析，第0帧处出现此种情况的原因是，采集视频是由人手工启动的，而且未使用严格的支架，所以在按下摄像机时摄像机会出现一次抖动，造成用帧差法检测是会出现很大的灰度差，但此时刻往往并不具有可以接受的运动量。在本实验中，选取基准帧时，tmax估计量的引入恰好可以将视频开头处的抖动帧丢弃。

将实验中所用到的10组视频对按照交叠区域百分比排序，与计算所得时间差与实际时间差的差值的绝对值可见表2。由此表中数据可知，当交叠区域大于1/4时，此方法计算值与实际值差值接近0，当交叠区域达到1/3以上时，经过计算，一般都可准确得到两视频启动时间差。而对于视频拼接，为了能够为后续拼接提供较丰富的特征点，一般要求源视频具有1/3以上的交叠区域。所以此方法可以满足基于双摄像机视频拼接的对帧要求。

3 结束语

本文阐述了一种用于双摄像机视频拼接的对帧方法。该方法利用帧差法对视频进行分析，获得视频中不同时间点的运动量状况，在运动量最低点利用相位相关法计算视频位移，在运动量最高点计算基准帧与另一视频帧序列交叠区域间的相关系数，以此确定对应帧。此方法具有运算量较小，受树叶摆动等不规则运动干扰小的特点。经实验证明，该方法能够在人手工操作摄像机，具有要求交叠区域的情况下，准确的定位到对应帧，完成视频对帧操作。

［1］BEN Yueyang，YIN Guisheng，GAO Wei，et al.Inertial frame coarse alignment for strap down inertial navigation system ［C］.IEEE International Forum on Information Technology and Applications，2009：647－651.

［2］Flavio Padua，Rodrigo Carceroni，Geraldo Santos，et al.Linear sequence－to－sequence alignment ［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，2010，32 （2）：304－320.

［3］Philip A Tresadern，Ian D Reid.Video synchronization from human motion using rank constraints ［J］.Computer Vision and Image Understanding，2009，113 （8）：891－906.

［4］CHEN Weibing.Comparision of matching capabilities in similarity measurements［J］.Journal of Computer Applications，2010，30（1）：98－110 （in Chinese）.［陈卫兵.几种图像相似性度量的匹配性能比较 ［J］.计算机应用，2010，30 （1）：98－110.］

［5］Josue Hernandez，Hiroshi Morita，Mariko Nakano－Miytake，et al.Movement detection and tracking using video frames［C］.14th Iberoamerican Conferences，2009：1054－1061.

［6］Darlan N Brito，Flavio L C Padua，Guilherme A S PereiraL，et al.Temporal synchronization of non－overlapping videos using known object motion ［J］.Pattern Recognition Letters，2011，32 （1）：38－46.

［7］Yaron Caspi，Denis Simakov，Michal Irani.Feature－based sequence－to－sequence matching ［J］.International Journal of Computer Vision，2006，68 （1）：53－64.

［8］ZHANG Jing，WANG Changshun，LIAO Wuling.An image mosaic algorithm based on improved phase correlation ［C］.International Conference on Environmental Science and Information Application Technology，2009：383－386.

［9］Javed Ahmed，Noman Jafri M.Improved phase correlation matching ［C］.3rd International Conference on Image and Signal Processing，2008：128－135.

［10］SHEN Hengtao，SHAO Jie，HUANG Zi，et al.Effective and efficient query processing for video subsequence identification ［J］.IEEE Transactions on Knowledge and Data Engineering，2009，21 （3）：321－334.

［11］ WANG Xiangqing， WANG Jun，PENG Hong.A semifragile image watermarking resisting to JPEG compression［C］.International Conference on Management of E－Commerce and E－Government，2009：498－502.

［12］Miroslaw Kordos，Wlodzislaw Duch.Variable step search algorithm for feedforward networks ［J］.Neurocomputing，2008，71 （13－15）：2470－2480.

［13］GAO Jian，LU Jining，HUANG Keyuan，et al.A novel variable step hill－climb search algorithm used for direct driven PMSG ［C］.International Conference on Energy and Environment Technology，2009：511－514.

［14］CAI Z H，WANG Y Y，WANG W Q.Improved image mosaic algorithm based on morphological method ［J］.Chinese Journal of Scientific Instrument，2006，27 （6）：721－723.

［15］Zirova B，Flusser J.Image registration methods：A survey ［J］.Image and Vision Computing，2007，21 （11）：977－1000.