帧间预测运动估计算法研究
帧间预测编码法是视频编码过程中消除冗余的重要方法。
运动估计和运动补偿技术是视频帧间预测编码中的核心技术。
详细研究了块匹配运动估计的基本原理，重点介绍了几种经典的块匹配运动估计算法，通过实验定性地评价了各算法的性能特点，分析了各算法的优缺点，总结出了运动估计算法优化的方向，对目前运动估计技术的研究和设计具有重要意义。
标签：帧间预测编码；时间冗余；块匹配；运动估计；运动矢量
Abstract：Motion estimation and motion compensation are the core technologies in video inter-frame prediction coding. The basic principle of block matching motion estimation is studied in detail，and several classical block matching motion estimation algorithms are introduced in detail. The performance characteristics of each algorithm are evaluated qualitatively through experiments，and the advantages and disadvantages of each algorithm are analyzed.
Keywords：interframe prediction coding；time redundancy；block matching；motion estimation；motion vector
引言
幀间预测是视频编码的关键内容，而运动估计是其核心。
据统计在H.264/A VC编码中运动估计约占全部计算量的60%到80%，所以运动估计算法的性能至关重要。
块匹配算法广泛应用标准视频编码。
在基于块匹配的运动估计算法中，对每一帧图像都被分成大小相同的宏块，然后以宏块为基本处理单元。
最后对预测差值、运动矢量和相应的参考索引进行编码。
1 帧间预测原理
1.1 运动估计
在序列图像中，邻近帧存在着一定的相关性。
因此，可将活动图像分成若干块或宏块，在参考帧中定义的搜索区域，按照一定的匹配准则，搜索出每个块或宏块在参考帧图像中的匹配块，并得出两者之间的空间位置的相对偏移量，即运动矢量。
当前块从参考帧中求取最佳匹配块得到运动矢量的过程被称为运动估计[2]。
运动估计的原理如图1。
假设当前帧为P，参考帧为Pr，当前编码块为B，B*与B在图像中坐标位置相同。
在Pr中，按照搜索准则，寻找与B块相减残差最小的匹配块Br。
这个过程就是运动估计，Br左上角坐标（xr，yr）与B*左上角坐标（x，y）之差，
即为运动矢量（Motion Vector，MV）。
1.2 运动补偿
运动估计得到的运动矢量同参考帧补偿出当前帧的预测帧的过程叫做运动补偿（Motion Compensation，MC），预测帧与当前帧相减得到预测误差[3]。
再对预测误差进行进一步处理。
2 运动估计算法
全搜索算法[4]（Exhaustive Search method，ES）能够得到全局最优的运动矢量，但该算法的运算量巨大无法实时应用。
快速搜索算法[5]简单，计算量小，加速比较大，但有时会陷入局部最优值，搜索的准确度不高。
经典的快速搜索算法[6]有：三步法（Three Step Search method，TSS），二维对数法，交叉搜索法，新三步法（New Three Step Search method，NTSS），四步法（Four Step Search method，FSS），菱形法[7]（Diamond Search method，DS），十字菱形搜索法，自适应十字搜索法（Adaptive Rood Pattern Search method，ARPS），六边形搜索法。
2.1 全局搜索算法
全局搜索算法是以每个像素为单位，在搜索区域内，按照一定的搜索规则，寻找匹配误差最小的块，计算出运动矢量，这样在每个像素的位置都会找到一个运动矢量，形成运动矢量集合。
2.2 三步搜索法
三步法是首先将图像分成不重叠的的块，在搜索区域内，按照一定的搜索准则分三步搜索。
第一步，从块中心开始以4步为步长的9个点的区域内计算最小误差值。
第二步，以第一步的最小值的点为中心，步长为2步的9个点的区域内计算最小的误差值。
第三步：以第二步的最小SAD值的点为中心，步长为1步的9个点的区域内计算最小误差值，这个最小点即为最佳匹配点。
三步法一共计算点数为：25个点。
它的优点是搜索步骤固定简单，只有三步，易于硬件实现新三步法、简单快速三步法（Simple and Efficient Three Step Search method，SESTSS）、四步法等都是在三步法的基础上进行改进的运动估计算法。
2.3 菱形法
菱形法不同于三步法及其改进的算法，它利用运动矢量的中心偏置特性，对搜索模式进行了改进，采用大小菱形模板。
大菱形由9个点组成，围绕中心点的8个点形成一个大菱形的形状。
小菱形是由5个点组成的菱形。
菱形法的第一步：在大菱形中搜索计算9个点（大菱形）的SAD，找到最小值点，如果在中心，则转至第三步；如果不在中心，转至第二步。
第二步：以第一步的最小值点为中心继续构建大菱形搜索，直至最小值位于中心。
第三步：以上一步的最小值点为中心构建5个小菱形搜索，计算结束。
菱形法的优点：计算量少，搜索速度快，
可以尽可能避免找到局部最优的位置，得到的性能更好。
六边形搜索法、十字形搜索等算法是在菱形法的基础上进行改进的运动估计算法。
3 实验结果与分析
3.1 实验平台和实验条件设置
仿真实验在配置为Intel（R）Core（TM）CPU i7-8550@1.80GHz 1.99Hz，8.00GB内存，Windows10的PC平台下，使用Matlab2014b作为仿真平台，对ES、TSS、NTSS、SESTSS、FSS、DS、ARPS算法进行实验，测试视频为caltrain 的前31帧。
运动估计块采用边长为16个像素的正方形，搜索范围为距当前块的上下左右各15个像素。
最佳搜索点采用最小绝对误差匹配准则。
测试指标采用搜索点数和峰值信噪比（Peak Signal to Noise Ratio，PSNR）。
3.2 實验结果和分析
每帧图像在所采用算法下的峰值信噪比PSNR如图2所示。
实验所用31帧图像的平均搜索点数和平均峰值信噪比PSNR值如表1所示。
图2表明，出全局ES算法的PSNR值最高，搜索的精确性最好，得到的运动矢量最佳。
四步法FSS和菱形法DS与全局搜索ES算法的PSNR性能上相近，帧PSNR值相差不到0.3dB。
从表1可以看出ES算法虽然PSNR最高，但是搜索点数是快速搜索算法的10～20倍，搜索速度很慢。
三步法相比ES算法在PSNR上有一定的下降，但是搜索速度快约10倍。
新三步法是在三步法基础改进的，与三步法在搜索速度上相当，但是PSNR上有明显的提高。
菱形法采用大小菱形模板，在搜索速度和PSNR上均有明显的提升。
自适应十字形搜索法在PSNR上和菱形法一致，搜索速度上却提升近一倍。
4 结束语
本文在分析块匹配运动估计原理的基础上，实现了几种经典的块匹配运动估计算法，通过实验结果和数据证明了不同运动估计算法的优劣，进而从理论上分析了这些经典算法优劣的原因，为更加鲁棒和快速的运动估计算法的研究设计提供了思路，有利于视频帧间预测编码的进一步研究。
参考文献：
[1]朱秀昌，刘峰，胡栋.视频编码和传输新技术[M].北京：电子工业出版社，2014：7.
[2]陈靖，刘京，曹喜信.深入理解视频编解码技术：基于H.264标准及参考模型[M].北京：北京航空航天大学出版社，2012：20-29.
[3]张晓星.基于块匹配的运动估计算法研究与实现[D].北京交通大学，2008.
[4]蒋晓悦，赵荣椿.几种块匹配运动估计算法的比较[J].计算机应用研究，2004，21（7）：1-3.
[5]刘书平.H.264运动估计算法比较与分析[J].现代计算机，2017（9）：41-46.
[6]吴晓军，白世军，卢文涛.基于H.264视频编码的运动估计算法优化[J].电子学报，2009，37（11）：2541-2545.
[7]刘海峰，郭宝龙，冯宗哲.用于块匹配运动估值的正方形-菱形搜索算法[J].计算机学报，2002，25（7）：747-752.。
