一种适用于移动视频编码标准(AVS-M)的快速搜索算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种适用于移动视频编码标准(AVS-M)的快速搜索算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

AVS工作组在2004年了移动视频编码标准(AVS for Mobile),它作为AVS标准的第七部分 (AVS1-P7)主要是适用于低码率的移动多媒体通信。AVS-M中,由于使用了多模式运动矢量、子像素估算及多参考帧,使编码的图像质量大大提高,但代价是高精度、大耗时的运动估算。其中,运动估算部分是最耗时的。对AVS-M编码器各个模块进行分析可以看出,运动估算模块的计算量占整个编码器运算量的85% 以上。要想提高编码速度,提高运动估算部分的速率是关键,因此本文提出一种适用于AVS-M的快速运动估算的搜索算法。

运动矢量场自适应搜索技术简介

运动矢量场自适应搜索技术MVFAST [1] (Motion Vector Field Adaptive Search Technique)是在区域搜索技术的基础上引入了自适应技术。MVFAST技术在质量、计算速度方面均有较大的提高,且不需特别的存储空间以存储搜索点和运动矢量。该技术考虑相邻块的运动特性,同时使用阈值以使搜索在小运动情况下能早期终止,集可行的预测技术和早期终止准则于一体,改善了算法性能。

MVFAST的派生技术称为PMVFAST[2] (Predictive MVFST), 谓之预测运动场自适应搜索技术。PMVFAST在MVFAST的基础上融入一系列预处理技术以获得较高的搜索速度,但增加了存储空间及算法复杂度。和MVFAST一样,PMVFAST在算法开始很重视那些可选的预测矢量集,并对阈值的计算也考虑自适应准则。PMVFAST的改进结果是使其适应性更广。PMVFAST算法是以MVFAST算法为基础,加入自适应的预测技术更进一步地动态调整搜索策略,达到更好的搜索效果。

首先为了更进一步地利用周围相邻宏块的相关性,PMVFAST定义了两组新的相关运动矢量的集合:

集合A,它包括6个候选宏块的运动矢量:左宏块、上宏块、右上宏块、前三者运动矢量中值、(0,0) 宏块的运动矢量和前一帧对应位置宏块的运动矢量。

集合B,包括集合A中的所有元素,同时还可以加入各种时间上、空间上相邻宏块的运动矢量组合, 例如可以定义一个集合A中多个候选运动矢量的线性组合。

使用两个集合中任意一个或者两个,从中寻找一个可以使得当前宏块的失真度为最小的运动矢量为最初的运动矢量,并且设定这个运动矢量指向的位置为搜索的初始中心。这样两组新的候选运动矢量的集合比单纯使用(0,0)或者相邻宏块的运动矢量可以取得更好的预测效果,使得搜索的初始中心比较准确地定位在最优点的附近。

其次,为了加速搜索匹配过程,PMVFAST使用了一套自适应阈值的方法提前结束当前宏块的搜索过程,这两个阈值如下:

Threshold-a:如果当前搜索到的位置的失真度小于threshold-a,则提前结束当前宏块的搜索过程。这个阈值是由大量的试验后得到的经验数据,可以根据实际情况调整这个参数,使计算复杂度和搜索的准确程度达到较好的平衡。

Threshold-b:如果当前搜索到的位置的失真度小于threshold-b,说明当前宏块的运动不是很剧烈。所以使用小钻石模型进行搜索。

此外PMVFAST还引入了一个失真度准则,如果当前的搜索状态满足这个准则,就提前结束当前宏块的搜索过程。所谓失真度准则是指:如果当前宏块的左边、上边和右上宏块的运动矢量和前一帧对应位置的运动矢量相同的话,则说明当前宏块和周围的宏块处于同一个运动区域内,周围宏块的运动程度基本说明了当前宏块的情况,所以至多再进行两次钻石模型的搜索就结束当前宏块的搜索过程。

通过以上多种策略的使用,PMVFAST算法在保证基本不降质的情况下,使得搜索速度比全局搜索快了几十甚至上百倍,所以它成为现有针对中低图像分辨率的快速搜索算法中最快的一种。同时由于它使用了临近宏块作为参考,更加准确地将初始搜索中心定位在全局最优点的附近,所以有效避免了陷入局部最优状态,在某些情况下使得视频整体PSNR的值比全局搜索法更高。

一种适用于

AVS-M的新型运动估计搜索算法

通过对多种运动估计搜索算法的分析与总结,结合AVS-M标准的实际应用,它适用于低分辨率,低码率视频序列,相邻帧之间的相对运动较之高分辨率视频序列来说,一般都较小。所以我们从PMVFAST算法出发,提出了一种新的适用于AVS-M的运动估计搜索算法。

1.算法特点

(1)搜索模板的改进

分析PMVFAST算法的9点大菱形模板(LDSP)可以发现,LDSP四周的8个匹配点到中心点(0,0)位置距离是不同的:水平和垂直方向的相邻搜索点间距为2像素,而中心点和对角方向的相邻搜索点间距为 像素。因此使用LDSP进行粗定位时,沿不同方向移动的匹配速度也是不同的,当LDSP的顶点为本次匹配的MBD点时模板沿水平或垂直方向移动,此时的搜索速度为2像素/步;当模板沿对角方向移动时其速度为 像素/步。另一方面,在大模板移动的每一步中,不同的搜索方向需要检测的搜索点数也不同。在水平和垂直方向上需要检测5个新搜索点,而在对角方向上只需检测3个新的搜索点。对于保持静止的图像序列,即运动矢量为零的情况,DS算法要经历由大模板到小模板的变化过程,要对13个搜索点进行搜索,而理想情况是只需搜索1个点。从以上几点可以看出大菱形模板并不是最优的搜索模板。事实上,造成该问题的根源在于块匹配误差实际上是在搜索范围内建立的误差表面函数,全局最小点即对应着最佳运动矢量,而LDSP实际上只是一个旋转了45度的正方形模板,在对角方向上的梯度下降方向不够快,需要较多步数才能够搜索到最优点。

考虑圆周的任意点到圆心的距离都相等,如果能利用圆形作为匹配模板,则该模板在各个搜索方向都具有相同的梯度下降速度,搜索速度能够达到最优。考虑到计算复杂度和图像序列的实际情况,我们使用了如图1(a)中所示的六边形模板(Hexagon Search Pattern, HSP)代替大菱形模板(LDSP),小菱形模板(SDSP)保持不变(图1(b))。搜索时先用HSP进行计算,当最佳匹配点出现在中心处时,可以认为最优点位于HSP所包围的六边形区域内,此时再将HSP换为SDSP,这5个点中的MBD就是最优匹配点。

(2)细分运动类型

从PMVFAST算法中,每次搜索执行过程中,算法都会利用中值预测运动矢量(必然环节)和相邻左块,上块,右上块,参考帧同位置块的运动矢量(可选环节),通过计算SAD来预测起始点位置,这在很大程度上提高了搜索的精度和速度,但是,考虑到运动矢量的中心偏置特性以及AVS-M应用于中低分辨率视频序列的特点,我们在这里引入了对图像运动类型(剧烈程度)的细分,主要目的是通过设计判断准则,在进行运动矢量预测之前,对待处理图像块的运动类型进行细分,根据不同的细分结果,采用不同的处理方式,避免了对每个块都使用起始点预测,这样可以大大节省起始点预测所消耗的时间。

本算法利用 (0,0) 点SAD来判断块的运动类型,通过比较SAD值与相关阈值的大小,来确定待处理块属于静止块,小运动块,中运动块,或者大运动块。首先判断当前块是否为静止块,如为静止块则直接中止搜索;对于非静止块则根据运动矢量的时空相关性进行运动类型判定和起始点预测,自适应的选择搜索模板和搜索策略。对于小运动块,最优运动矢量位于中心点附近的位置,使用SDSP法精度高、速度快;对于中运动块,最优运动矢量位于比较靠近中心点附近的位置,所以比较适合利用HSP进行搜索;而对于大运动块则类似PMVFAST算法,先进行起始点预测,使搜索起始点更接近全局最优点,再使用HSP或SDSP进行搜索,具有良好的搜索性能。图2是运动类型细分的流程图。

(3)自适应的搜索范围

在AVS-M中,为适应不同运动程度的视频图像序列、提高运动估计的性能,一般采用了±16或±32点的搜索窗。这使得单块的全搜索点数上升到1089和4225个点。扩大的搜索窗对于大运动序列,无疑可以进一步提高运动估计的精度,但对于分辨率较小运动序列,却是不必要的浪费。显然,如果能够根据序列本身的运动特性,自适应地确定一个搜索范围,使绝大部分最佳匹配点都落于该范围内,则可在保证PSNR方面性能的同时,降低运算量,提高效率。实际上,考虑到运动矢量的中心偏置特性,一般情况下,运动矢量主要集中在(0,0)点周围,在各种运动剧烈程度不同的视频序列中,运动矢量小于5像素的块的概率普遍最大。如表1的统计结果。

考虑到运动矢量可以认为是当前块从当前帧到参考帧的偏移量,则可以用运动矢量的二阶矩来评价当前帧相对参考帧的运动程度。同时,研究表明视频序列是一个相对缓变的过程,从整体上看,其各帧运动向量的二阶矩变化也较为缓慢。基于此项观察,本文提出建立在视频图像序列统计特性之上的自适应范围搜索,即根据前一帧运动向量的二阶矩来为后一帧确定一个较为合适的搜索区,然后在该区内进行搜索。定义

--------------- (1)

搜索区SR=1.5×D----------- (2)

其中,NMV是前一帧运动向量的个数,D为运动向量的二阶矩,而SR则为用于当前帧的自适应搜索区。求得SR后,进行自适应范围搜索。通过使用自适应范围搜索,可以在六边形与小菱形搜索的过程中,在保证搜索准确性的基础上,有效的缩小搜索的区域,从而降低搜索复杂度,提高搜索速度。

2、算法流程

新算法主要分为以下几个主要阶段:

初始化阶段; 运动类型判定阶段; 起始点预测阶段;

六边形与小菱形模板搜索阶段; 终止步骤

算法的具体步骤如下(以16×16宏块为例):

(1)初始化阶段 Step1:

利用上一帧运动矢量,计算当前帧的自适应搜索范围,调整搜索窗的大小;

设置阈值 threshold-a和threshold-b值。具体如下:

如果搜索点位于第一行第一列,则threshold-a = 512, threshold-b = 1024;

否则threshold-a取左、上、右上相邻块中的最小SAD值,

Threshold-b = threshold-a + 256;

置标志:Found = 0, PredEq = 0;

判置阈值

Ifthreshold-a < 512, threshold-a = 512;

If threshold-a > 1024, threshold-a = 1024;

If threshold-b > 1792, threshold-b = 1792;

(2)运动类型判定阶段(判定运动类型)

Step2:计算搜索窗中心(0,0)点的SAD值,如果SAD

Step3:重复进行小菱形模式搜索,直至最小SAD点为小菱形模板中心点,随后转至Step14;

Step4:重复进行六边形模式搜索,直至最小SAD点为六边形中心点,则转而使用小菱形模板再搜索一次,随后转至Step14;

(3)起始点预测阶段

Step5:按中值法则计算预测运动矢量(PMV):选择相邻左块运动矢量、上块运动矢量,右上块运动矢量并计算与之相关的模值的中间值。

块处理(若宏块为边界块,依据块位置作如下操作):

假如块包含首列,则设相邻左块运动矢量为(0,0);

假如块包含首行,取相邻左块运动矢量作PMV;

假如块包含最后一列,则设右上块MV为(0,0);

假如left MV = top MV = top-right MV,则置PredEq = 1;

Step6:计算Distance值:Distance = |medianMVx| + |medianMVy|, 如果PredEq = 1且PMV = Previous Frame MV(参考帧同位置块的运动矢量),则置Found = 2;

Step7:如果Distance > 0或者thresholdb < 1536或者PredEq = 1,选择小菱形搜索模式,否则选择六边形搜索模式;

Step8:计算中值预测点的SAD值,并令MinSAD = SAD。如果SAD

Step9:计算相邻左块,上块,右上块,前一帧的同位置块的SAD块;并置MinSAD为此步计算得到的四个SAD值与中值预测点SAD值中的最小值;

Step10:如果MinSAD

Step11:执行搜索(小菱形搜索或者六边形搜索,根据Step7决定),如果Found = 2,则只进行一次搜索,随后转至Step14;

Step12:如果执行小菱形搜索,则重复执行,直至最小SAD点位于中心点,然后转至Step14;

Step13:如果执行六边形搜索,则重复执行,直至最小SAD点位于中心点,再执行一次小菱形搜索以精确计算,然后转至Step14;

(4)终止步骤

Step14: 运动矢量由与之相关的有MinSAD值的块决定。

实验结果验证

为了验证算法的有效性,我们选取了几种最具代表性的块匹配算法:FS,UMHexagonS,PMVFAST,在相同的条件下与本文算法进行对比实验。使用的匹配块大小为16×16像素,匹配准则使用SAD。实验中选取2个CIF格式图像序列:Football,Mobile和2个QCIF格式的图像序列:Claire,Glasgow。Claire是典型的头肩序列,图像运动微小平缓;Football属于大运动序列;Glasgow序列中包含物体的快速运动和场景切换;Mobile序列中既含有镜头的平移也包括物体的移动,且背景复杂。对这些序列中的前50帧逐帧进行运动估计,计算其PSNR和编码时间的平均值。软硬件平台为:Pentium-M 1.4GHz,512M内存的PC上进行,操作系统使用Windows XP Professional,编译器使用Intel Complier 8.0。编码器的设置:第一帧为I帧,其余均为P帧,所有帧的QP = 32,rate control off,RDO on,CIF搜索范围为32,QCIF搜索范围为16(本文算法采用自适应搜索范围),采用两个参考帧。结果如表2和表3所示。

从实验结果可以看出,本文算法在编码速度上,与FS、UMHexagonS、PMVFAST比较有明显提高,主要原因是本文算法充分利用了低分辩率,低码率视频序列的运动特点,对算法的搜索模板,搜索范围的设定,搜索起始点的预测以及搜索策略等都做了相应的改进,简化了运动估计算法的复杂度,因此在速度上得到了很大的提高,编码时间约为PMVFAST所用时间的90%左右;相对于UMHexagonS和FS,速度的提高则更为明显。图3和4显示了以上四种算法在QCIF格式Claire序列与QIF格式Mobile序列编码50帧的时间统计,我们可以很清楚的观察到编码速度的提升。

在性能方面,相比PMVFAST,由于本文采用了一些简化手段,如自适应的搜索窗大小,提前终止的判断准则等,因此,在PSNR上有了一定的降低。与PMVFAST算法相比,差距均在0.1dB范围以内(某些情况下,已经相当接近PMVFAST的性能),不会对主观评价造成过大影响,基本可以忽略,且明显要好于UMHexagonS,因此较为适合实际的应用。

小 结

本文从介绍现有的新型快速运动估计算法的步骤及特点出发。在此基础上,对运动估计算法的设计思路进行了总结,提出了一种适用于AVS-M视频标准的新型运动估计算法,并通过实验,验证了该算法的有效性。■