基于AVS的多参考帧快速运动搜索算法

李媛媛

（太原理工大学 电气与动力工程学院，山西 太原 030024）

0 引言

AVS（Advanced Audio－Video Coding－Decoding Standard）标准，是我国“数字音视频编解码技术标准工作组”自主研发的，拥有自主知识产权的第二代视频压缩标准［1－3］，它也是目前最先进的音视频压缩编解码标准之一。AVS技术标准主要包括系统、视频、音频和数字版权管理等4个方面。AVS视频编码部分具有计算复杂度低、压缩比高、图像质量高、专利授权费用低等优点，对于我国实施自主发展的多媒体产业具有非常重要的经济意义和社会意义。

视频编码算法主要包括运动估计、运动补偿、DCT 变换、量化、熵编码、滤波等模块［4－6］。其中运动估计主要包括运动搜索和模式选择两部分。运动搜索是通过一定的匹配准则在参考帧中搜索得到当前块的最佳匹配块，尽可能地消除帧间冗余，减少编码信息量，从而提高编码效率。为了寻找到最优匹配块，AVS视频编码标准从已编码的两帧中搜索最佳匹配块，使得运动搜索的计算复杂度大大增加。模式选择是对编码模式通过代价值的比较选取代价值最小的模式为当前块的最佳编码模式。因此，降低运动搜索运算量是提高AVS视频编码器编码性能的重要内容。本文提出了一种新的菱形搜索形式，该方法主要是根据参考帧的位置不同而选用不同形状的菱形搜索模式，在保证视频质量不变的情况下使搜索点数大大减少。

1 AVS运动估计过程

在AVS视频编码中，帧间预测编码就是找出当前块在参考帧中的位置，两者空间位置的相对偏移量就是运动矢量。运动估计就是得到运动矢量的过程，运动估计又包括运动搜索和模式选择两个步骤。传统的运动搜索算法有全搜索法和快速搜索法。快速搜索法主要包括菱形搜索（DIA）、六边形搜索（HEX）、非对称十字六边形搜索（UMH）等。

AVS帧间预测模式有4 种：16＊16 模式、16＊8模式、8＊16模式和8＊8模式。由运动搜索得到当前块在参考帧中的最佳匹配块，计算匹配块和当前块的代价值，通过代价值的比较选出以上4种预测模式中代价值最小的模式做为最佳预测模式。

1.1 DIA 搜索和模式选择介绍

1.1.1 运动搜索

AVS的运动搜索是基于块的搜索，最佳匹配块由运动搜索的率失真函数Bcost（x，y）进行选择：

其中：SA（T）D（x，y）为当前块x 和匹配块y 的像素差经过哈达玛变换后所得到的系数之和；IMOTION为运动估计的拉格朗日乘子；△mv为预测运动矢量与实际运动矢量的差值，b（△mv）为编码△mv 所需比特数［7］。Bcost（x，y）值最小的候选块就是当前块的最佳匹配块。

在运动搜索算法中，根据运动矢量分布的中心偏移特性而得到的菱形搜索算法（DIA）搜索模型较简单，并且运算量也较小。DIA 搜索算法流程如图1所示。

图1 DIA 搜索算法流程图

DIA 算法中，候选搜索起始点是利用当前块与邻近块的空间相关性和与参考帧中对应位置的时间相关性预测得到；通过将每次菱形搜索得到的最优点和上次得到的最优点比较看其是否相同确定搜索是否结束，最优点对应的块就是当前块的最佳匹配块。

1.1.2 模式选择

4种预测模式通过运动搜索得到最佳匹配块后，由公式（2）根据已有的最佳匹配块确定4种预测模式中的最佳预测模式。模式选择的率失真函数J（s，c，MODE／QP）表示如下：

其中：D（s，c，MODE／QP）为待编码块c和重建块s 的差值平方和，MODE 为预测模式，QP 为量化参数；λMODE为预测模式的拉格朗日乘子；R（s，c，MODE／QP）为编码残差所用的比特数。J（s，c，MODE／QP）取值最小的预测模式即为当前块的最佳预测模式。

1.2 最佳参考帧选择的概率分析

AVS视频编码标准中P 帧和B 帧最多可有两帧参考图像。P帧可参考前向的两帧，B 帧可参考一前一后的两帧。根据时间相关性可推测时间相差越小的两帧相关性越强。

非对称十字形多层次六边形格点搜索是一种优秀的搜索算法，该算法能够保证较高的视频质量、较低的码率。本文采用UMHexagonS 搜索方法，为了验证当前帧的前一帧和当前帧的相关性最强、被选为最佳参考帧的几率较大，分别对分辨率为352×288的CIF格式和分辨率为176×144的QCIF 格式的测试序列进行了实验统计，实验中所用测试序列均为标准序列（如news、mobile、foreman等）。统计结果见表1和表2。

从表1和表2可以看出，第1帧i＿ref0被选为当前帧参考帧的概率最大，平均可达92.33%，而第2帧i＿ref1被选为当前帧参考帧的概率仅为7.67%。也就是说，距离当前帧越近的参考帧被选为当前帧优秀参考帧的概率越大。

表1 CIF格式参考帧被选用的概率统计结果

表2 QCIF格式参考帧被选用的概率统计结果

2 变换菱形搜索算法

2.1 两种菱形搜索模板

运动搜索算法中的UMHexagonS搜索是一种多种搜索模型混合使用的搜索算法，它能够有效地避免运动搜索过早陷入局部最优，并且保持了良好的率失真性能，但是由于搜索模型较复杂，搜索点数较多，使得运算量大大增加。传统的菱形搜索法搜索模型较简单、计算量较小，视频质量和UMHexagonS搜索算法相比有明显下降。本文提出了一种新的菱形搜索方法，对不同参考帧采用不同的菱形搜索模板。

具体搜索模板如图2所示，模板0中心点周围有8个搜索点，模板1中心点周围有4个搜索点，模板1是在模板0的基础上减少外围的4个搜索点形成的。模板0用于对参考帧i＿ref0进行匹配块搜索，较大范围的搜索可以得到较好的运动矢量。模板1用于对参考帧i＿ref1进行搜索，在前面运动矢量的基础上参考帧i＿ref1使用缩小的菱形模板进行搜索。

图2 变换的菱形模板

2.2 算法实现

针对已编码的两帧参考帧采用上述模板0和模板1进行菱形搜索，搜索流程如图3所示。

变形菱形搜索中，候选搜索点是根据当前块与邻近块的空间相关性和当前块与参考帧的时间相关性预测而得到的。对于和当前帧相关性更强的参考帧i＿ref0采用模板0进行搜索，参考帧i＿ref1采用较简单的模板1进行搜索。如果搜索到的新的最优点和上一搜索中心点相同则结束搜索，否则继续使用该搜索模板进行搜索。

图3 变换菱形搜索流程图

3 实验结果与分析

本文分别从峰值信噪比（PSNR）和搜索点数两个方面对上述优化算法和UMHexagonS搜索算法进行了比较。主要参数设置如下：参考帧为2 帧；I帧（只采用帧内预测模式）的量化参数设为30，P 帧（采用帧内和帧间预测模式，帧间预测时用前向参考）的量化参数设为32，B帧（采用帧内和帧间预测模式，帧间预测时用双向参考）的量化参数设为34；编码序列为IPBBPBB格式。测试了不同格式和不同运动剧烈程度的测试序列的峰值信噪比和搜索点数的变化，实验数据见表3和表4。

表3 QCIF格式的实验结果

在表3和表4中，“－”号表示降低。由测试结果可以看出，在所有测试序列信噪比降低不超出0.12dB的情况下，搜索点数明显减少，最多可以减少92.12%。总体来看，在峰值信噪比变化不明显的情况下，优化算法的搜索点数大幅度减少，进而运动搜索计算量和搜索时间也都大大降低，提高了编码器的性能，更好地满足了视频压缩编码的实时性要求。

表4 CIF格式的实验结果

4 结束语

本文通过对AVS编码器中两帧参考帧被选为优秀参考帧概率的深入分析和研究，提出了一种低复杂度的变换菱形搜索算法。对距离当前帧不同的参考帧采用不同的搜索模板，从而在保证视频质量的条件下，运动搜索的计算量大大降低，大幅度提高了AVS 视频编码速度，更有利于AVS编码器的硬件实现和实时性要求。

［1］ 周波，王力波，刘东华，等.用于AVS视频编码的快速子像素运动搜索算法［J］.计算机应用研究，2008，25（7）：2238－2240.

［2］ 绍娟，张卫宁，陈栋，等.AVS中B 帧宏块模式选择快速方法［J］.计算机工程与应用，2011，47（5）：179－181，245.

［3］ 毕厚杰.视频压缩编码标准——H.264／AVC［M］.北京：人民邮电出版社，2005.

［4］ 张新安，宫彦军，陈爱武，等.一种AVS－M 运动搜索快速算法［J］.计算机工程，2011，37（9）：260－262.

［5］ 康慧斌.AVS视频编码中子像素运动估计算法的优化研究［J］.控制工程，2010（7）：14－17.

［6］ 叶文龙，袁友伟，汪世瑜，等.H.264 块匹配运动估计中UMHexagonS算法的优化［J］.计算机工程与应用，2011，47（25）：133－136.

［7］ 杨春玲，王华兴.基于结构相似度的H.264 快速运动估计算法［J］.华南理工大学学报（自然科学版），2008，36（8）：28－32.