一种基于二维离散余弦模型的运动估计算法研究

赵臣臣（厦门大学信息科学与技术学院，厦门 361001）

一种基于二维离散余弦模型的运动估计算法研究

赵臣臣
（厦门大学信息科学与技术学院，厦门 361001）

0　引言

随着技术的进步，互联网以及移动互联网的快速发展，视频信息流在互联网传播中日益占有越来越重要的信息体现价值。视频因其直观、高效、易于接受等特点，已经从单纯的视频流转变为监控、视频会议、无线流媒体等方向转变，因此对于视频压缩的要求提出更高的要求。近几十年来，通过近几代人的努力，视频编码技术已经取得了长足的进度，从第一代的视频标准 H.261到后来的历代标准如 H.263、MPEG-1、MPEG-2、H.264、MPEG-4［3］等。对视频的压缩率已经提高了几十上百倍，高效的视频压缩技术不仅降低信息的冗余，同时了通过压缩提高了码流的利用率，缓解网络频宽的压力。

在视频编解码中，帧间运动估计是其耗费时间较大的一个环节，同时也是影响视频压缩质量的重要一环。因此，运动估计算法常常影响视频编码算法的最终效果。运动估计与补偿的目标是减小帧间冗余信息，运动估计不是以估计物体的真实位移为目标，而是追求最优化率失真。自第一代视频压缩框架，基于平移运动模型的块匹配算法BMA已经被证实为有效的运动估计算法。在块匹配算法中，每一帧被分割成固定大小的块，并采用参考帧中最佳匹配块去预测，这种方案假设每一块相对于参考帧都具有相对独立的运动适量。对于大部分连续性视频序列来说，当前帧与前后帧之间存在很强的相关性，它们之间的差异性也可能很小，这些差别主要来自于帧内局部变化或者全局变化量。传统的运动估计算法是基于块的方式进行帧间预测。首先，当前帧被划分成若干个互不重叠的宏块，并假定宏块内部具有相同的运动矢量，然后选定当前帧的前一帧或者后一帧作为参考帧，并在参考帧中规定搜索的范围搜索，因此，搜索范围和搜索的算法直接决定了搜索的精度和效率。

在H.261中，16×16块大小被采用，最近，更大块的64×64被采用，一些学者对块的划分合并提出了一些改进算法等，基于块的算法因其分割简单，易于实现，算法变化量化的方便，被认为是最合适的选择，但是近年来，国内外学者在改进运动模型方面做了大量的研究和改进，大部分研究都是基于块匹配框架的基础进行，例如Seferidis和Ghanbari两位学者提出了普遍适用的基于块匹配框架去估计运动矢量，他们采用了基于仿射、透视和双线性变换等运动模型对四边形块进行变换。Wen-Hsiao等为了进一步优化新一代视频压缩标准HEVC的帧间预测技术，他们提出了基于模板匹配和块匹配的联合运动补偿技术去近似真实运动矢量场。本文将在后续章着重介绍基于弹性运动模型的算法理论研究和主客观实验分析，包括了二维离散余弦基函数弹性模型、迭代求解弹性模型参数算法、整体的求解流程以及实验仿真对比。

1　运动估计算法

在视频编解码算法中，运动估计通常采用基于块的匹配算法。基于块运动估计算法通常是一个确定的搜索块，这类算法使用固定搜索的方式在搜索区域内搜索运动矢量，传统的搜索算法有全搜索算法（FS）、3步搜索算法（3SS）、新三步搜索（N3SS）、4步搜索（4SS）、梯度下降搜索（BBGHD），菱形搜索（DS）等。此类算法中，主要以一个固定的模式，进行一个范围内搜索，此类算法一般是基于一个最小点进行步长的缩短等，但是很多算法会陷入局部最小。当搜索模式的大小与实际运动程度不符合的时候，很容易造成搜索的不精度，影响寻找的匹配结果精度。

在块运动估计算法中一般是基于平移模型，适用于匹配块的垂直或者水平运动。该模型对于旋转、缩放和形变等不能很好地描述，近年来，为了有效对非平移运动矢量进行预测以提高视频压缩效果，一些基于非平移模型的算法被学者关注和提出。比较典型的有仿射运动模型，透视运动模型，双线性运动模型，基于光流模型的运动估计，基于网格模型的运动估计等算法。

图1　运动估计原理示意图

2　基于弹性模型的运动估计算法研究

基于平移的运动模型因其简单性，几乎主流的标准都采用了该平移模型的块运动估计，但是由于对形变模型估计的需求，我们一改以往的刚性运动模型，提出了基于二维离线余弦基函数的弹性运动模型的运动估计算法。在常见的视频序列中，主要有以下几种运动方式：第一基于全局运动，第二局部块运动。在传统的运动模型中，对这两种模型都有较好的表现，但是综合这两种运动形式会形成较复杂的运动矢量场，因此传统块运动模型赋予同一匹配所有像素点相同的运动矢量并不能很好地描述复杂矢量场的情况，块运动估计模型处理复杂运动场的通常做法是采用较小的分块，但是这样必然会带来比特信息流的开销。本文介绍了一种基于二维离线余弦函数的弹性运动模型将有效的改善块运动模型对运动矢量复杂的表现。

图像匹配准则技术的关键在于得到参考帧和测试帧之间相似点坐标的映射函数。经典的图像配准技术都能够快速适用于视频压缩中。在视频中假定两个匹配块为I（xi+yi）和 I'（xi'+yi'）

其中，P是运动参数的总数，mk为运动参数，φk（*）为任意的基函数，它能描述I与I'之间坐标的复杂对应关系。基函数φk（*）可以为B样条插值、多项式、谐波函数、仿射基函数以及小波变换等。

2.1基于二维离散余弦运动基函数的弹性运动模型

基于二维离线余弦基函数能够用较少的系数有效表述弹性运动矢量场。离散余弦基函数的坐标变换可以表示为：

2.2迭代高斯-牛顿梯度非线性最优算法

在运动模型中，我们采用高斯牛顿梯度法来计算运动模型的参数，以使其从参考帧中得到最佳预测块。我们采用的是迭代高斯-牛顿梯度非线性最优化算法。在这种算法中，我们采用一阶泰勒近似平方差和去线性化非线性表达式：

其中，把I与I'表示为I（xi+yi）和I'（xi'+yi'）。

2.3弹性运动模型参数求解流程

基于迭代高斯-牛顿梯度非线性最优算法求解流程可以总结为以下9步：

（1）获得当前运动参数所对应的映射模型，也就是把参数代入弹性运动模型并且计算对应匹配点的像素位置。

（2）计算出当前块与参考块的残差。

（3）计算图像水平和垂直的梯度。

（4）计算弹性运动模型对参数的导数。

（5）计算（3）和（4）的积。

（6）计算Hessian矩阵。

（7）计算（5）和（2）的值。

（8）计算弹性运动模型参数增量。

（9）更新弹性运动模型的参数值，本次迭代求解结束。

3　实验结果分析

为了验证本文研究的弹性运动模型运动估计算法对非平移运动矢量场的预测效果，本次实验选取了A、B和C三类国际视频标准测试序列，对各个测试序列的前50帧分别进行基于两种不同运动模型的主客观性能验证，也就是弹性运动模型和BMA运动模型的算法比较，测试序列如表1所示。

表1　实验所用测试序列

表2为本文采用的弹性运动模型与全搜索块匹配算法BMA的实验对比表，分割大小为64×64（表中1、4、7列）、32×32（表中2、5、8列）和16×16（表中3、6、9列），它们的匹配精度均为1/4像素，所有实验数据均在单一分割层得到。

表2　64×64、32×32和16×16块分割实验对比表

从表中可以看出，对于块分割大小为64×64，，相比于BMA算法，采用本文研究的弹性运动模型其平均PSNR都有提高。对于A类视频序列，分辨率为352× 288，对其进行64×64块分割后，由于分辨率低而分割块大造成每个64×64编码块都包含了丰富的纹理信息，在编码块相对于参考帧运动并具有复杂矢量场情况下，采用传统的BMA算法则无法有效地对运动矢量场进行预测而造成较大的残差，相反，采用弹性运动模型则能有效地对非刚性运动矢量场进行表述，一定程度地减少了预测残差能量。

图2　32×32块分割快匹配算法与弹性模型主观图对比

4　结语

基于弹性模型算法与常用的块匹配算法是两个完全不一样的理论体系，我们根据实验仿真数据从主客观两方面论证了本文研究的弹性运动模型的有效性，特别在预测复杂矢量场时，由于BMA算法的局限性，本文研究的弹性运动模型有更好的预测效果。

［1］X.Jing，L.P.Cha.An Effieient Three-step Search Algorithm for Block Motion Estimation.IEEE Transactions on Multimedia，2004

［2］W.Li，E.Salari.Suceessive Elimination Algorithm for Motion Estimation.IEEE Transactions on Image Processing

［3］Video Codec for Audiovisual Services at px64 Kbit/s，ITU-T Rec．H.261［S］，1993

［4］Sullivan G J，Ohm J，Woo-Jin H，et al.Overview of the High Efficiency Video Coding（HEVC）Standard［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22（12）：1649～1668

［5］Video Coding for Low Bitrate Communication，Version 1.ITU-T Rec.H.263［S］.ITU-T Rec.H.263，1995

［6］Iu S L.Comparison of Motion Compensation Using Different Degrees of Sub-pixel Accuracy for Interfield/Interframe Hybrid Coding of HDTV Image Sequences［C］.IEEE International Conference on Acoustics，Speech，and Signal Processing，1992

［7］Muhit A A，Pickering M R，Frater M R，et al.Video Coding Using Elastic Motion Model and Larger Blocks［J］.IEEE Transactions on Circuits and Systems for Video Technology，2010，20（5）：661～672

Two-Dimensional Discrete Cosine；HEVC；Motion Estimation

Research on a Motion Estimation Algorithm Based on the Two-Dimensional Discrete Cosine Model

ZHAO Chen-chen
（College of Information Science and Technology，Xiamen University，Xiamen 361001）

1007-1423（2015）10-0017-04

10.3969/j.issn.1007-1423.2015.10.005

赵臣臣（1989-），男，山东临沂人，硕士研究生，研究方向为视频编解码

2015-02-05

2015-03-18

随着视频需求变大，视频编解码的要求越来越高，传统的视频编解码技术基于块匹配算法，其在同一个运动矢量场内使用相同的运动矢量，并不能很好表现像素点的细节，同时对于采用较小块划分的结构带来大量的比特信息量，介绍一种基于二维离散余弦模型的方式实现更加精确描述复杂矢量场模型，能有效表现视频序列的细节及节省比特开销。

二维离散余弦；HEVC；运动估计

With the development of video demand，higher and higher requirements of video code，the conventional video coding technology based on the block matching algorithm，which uses the same motion vectors in the same motion vector field，it doesn't has a very good performance of pixel details，also for using relatively small partition structure brought a large number of bits，introduces a two-dimensional discrete cosine model based on the way to achieve a more accurate description of complex vector field model，which can effectively describe video sequence in details and save the bits.