基于零系数块和快速MPPM的AVS帧内预测算法

张永强，王双龙

(河北工程大学信息与电气工程学院，河北邯郸056038)

AVS是国内第一个针对音视频产业需求而制定的标准，全称为《信息技术先进音视频编码》［1］。相比于MPEG－2标准，AVS编码效率提高了2～3倍，在编码高清视频信号时，获得与先进视频编码标准AVC/H.264主要档次(MP)相当的编码效率，但解码器的实现复杂度只有60%～70%，实现了算法复杂度和编码效率的折中。

AVS采用基于时间和空间的预测编码、变换编码和熵编码的混合编码结构。关于预测编码中的帧内预测编码部分，相比H.264帧内编码，AVS帧内预测不但流程简洁，实现复杂度低，而且采用的预测模式更少。但其参考软件在PC平台广播档次下，编码I帧平均要用1.5 s，编码P帧要3.5 s，编码B帧所用时间更多，这样很难在DSP上实现，而帧内编码效率存在很大的提升空间。通过分析AVS帧内预测编码的工作原理及流程，改进帧内预测编码，提出一种结合零系数块和快速MPPM的优化算法来提高帧内编码效率。经实验验证，在PSNR降低较小的情况下，改进后的算法明显提高了编码效率。

1 零系数块的提出及阈值判定

1.1 零系数块的提出

AVS帧内编码以宏块为单元，在4∶2∶0格式下，宏块包括4个8×8亮度子块和2个色度子块，其中子块的分隔及序号如图1所示，0～3为亮度子块，4～5为色度子块，编码的比特流中若包含语法元素cbp，表示当前宏块中序号从0～5的4个8×8亮度块和2个色度块是否包含非零变换系数，cbp的第n位为0表明序号为n的8×8子块中没有非零系数，即该8×8子块中的任一像素值都为0，这样的子块称为零系数块［2］。

图1 4∶2∶0下AVS宏块分隔子块

在AVS参考软件GDM2.1中，元素cbp的编码是在帧内预测编码的最后阶段进行的，前面进行了一系列复杂操作，如利用率失真代价值选取当前宏块最优预测模式(Best Prediction Mode，BPM)，这部分操作极大地降低了系统效率(在后文详细阐述)。很明显，如果当前块是零系数块，把当前块cbp元素的编码放在帧内编码的最后是不合适的，基于此，通过推导出子块为零系数块的充分条件，提前判定当前块是否为零系数块，进而决定是直接编码宏块cbp元素还是进行后续编码操作。

1.2 零系数块阈值推导

AVS为减少相邻像素间空间相关性，采用8×8预缩放整数变换(Pre－scaled Integer Cosine Transform，ICT)，该变换源于离散余弦变换，是定点余弦变换的扩展，旨在保持相当压缩性能的同时降低计算复杂度以及避免离散余弦变换(Discrete Cosine Transform，DCT)导致的编解码失配问题。AVS中整数变换过程为

式中:A为AVS变换矩阵;X为待变换矩阵，在帧内编码中即为当前8×8子块实际值与预测值之差，以下简称残差。如图2所示，残差数据经过ICT变换、尺度变换、量化，得到量化后的变换系数，量化后的变换系数经过反量化、ICT逆变换，得到重建数据。参考软件中尺度变换过程与量化过程是一体的，见图2中的虚线部分。

图2 AVS变换量化及数据重建

参考软件中，残差数据Xij经过ICT变换及尺度缩放为

式中:Aui，Ajv为变换矩阵A中的元素。残差变换系数X量化过程如下

式中:Fq为残差X变换、量化后的结果;ScaleM是一个以位置参数i，j为索引的二维数组表，值可由式(5)获得;qp_cost为帧内或帧间编码常数，对于帧内编码等于(1＜＜15)×10/31，对于帧间编码等于(1＜＜15)×10/62。将式(2)代入式(3)，得到

为方便式子的推导，对式(6)中部分表达式做如下简化

式中:Bmax=43 969;C1=，由绝对值不等式的性质对式(8)作进一步推导，即

由函数极限可知，当表达式B、D取最大值时，如果Fq小于1，即量化的变换系数为0，此时得到的SAD阈值可以作为判定零系数块的充分条件。将表达式C1，Bmax，Dmax代入式(6)，得到判定当前子块是零系数块的SAD阈值，即

式中:Q_TAB是一个以量化步长QP为索引的一维常数数组表，其值随QP增大而递减，例如当QP为24时，Q_TAB=4 467，Th=27。阈值Th只与量化步长QP有关，在程序算法的设计中，将其做成一个以量化步长QP为索引的一维常量阈值数组表，判定零系数块时只需查表即可查到阈值，降低系统开销。

2 快速帧内预测算法

2.1 AVS 帧内预测

AVS帧内预测编码基本思路同H.264，但在保证编码质量相当的前提下，AVS采用预测模式更少，帧内编码以8×8子块为基本单元，亮度预测有5种预测模式，色度预测有4种。下面介绍帧内预测都以亮度子块预测模式为例假以说明，色度子块帧内预测与亮度子块类似，亮度预测模式如表1所示。

表1 AVS帧内预测编码模式

由文献［3］知，AVS通过计算率失真代价值(Rate Distortion Optimization，RDO)选择帧内最优预测模式BPM能保证帧内编码的效率与质量。在AVS标准中，计算帧内预测编码模式时，采用全搜索算法遍历计算比较率失真代价函数值，全搜索算法流程如下:

1)判断是否使能率失真代价函数，若没有使能则直接跳到3)。

2)计算当前8×8子块残差数据，当前模式下的率失真代价值RDCost，若其值小于min_cost，把当前模式的率失真代价值赋给min_cost。

3)若没有使能率失真代价函数，则计算在当前模式下8×8子块的残差数据，经Hadamard变换，若其值小于min_cost，则把当前模式的代价值赋给min_cost。

4)重复1)、2)或3)步骤，遍历其他的帧内预测模式，选取min_cost对应的预测模式为当前块最佳预测模式。

率失真代价值计算函数为

式中:Sij为实际像素值;Qij为重建像素值;i，j为子块中像素所在的相对行、列序号(0≤i，j≤7);SSD(Sum of Squared Difference)为当前8×8子块在某种预测模式下实际值与重建值之差的平方和，微观上反映帧内预测的准确度;Rate为编码比特流数，包括编码最佳预测模式、当前子块的位置参数、类型以及亮度系数所用的比特数;λ为拉格朗日因子，可从式(14)得到。

2.2 快速算法的提出

由AVS中帧内预测的流程可知，全搜索算法花费不少时间，计算编码比特数(Rate)过程中涉及到变换、量化、反量化、反变换的重建操作以及浮点数操作等。由文献［4－7］可知目前关于降低最佳帧内预测模式计算复杂度的研究可分为两个方向，一是减少遍历预测模式次数;二是简化求率失真代价值RDcost的操作。权衡之下，本文偏向第一种，优化计算搜索帧内预测模式的过程，提出快速MPPM(Most Possible Prediction Mode)算法，也就是快速筛选出最佳帧内预测模式MPPM，算法基于当前子块纹理方向，通过快速简易筛选减少帧内预测候选模式，进而快速确定最优候选模式，提高AVS的编码效率。

快速MPPM算法阐述如下:定义各纹理方向的SAD分别为垂直方向SADV、水平方向SADH、135°方向SADDL和45°方向SADDR，8×8子块及其各预测方向如图3所示，其中Sij为子块像素值。分别计算当前8×8子块的水平、垂直、垂直向左、垂直向右4个方向残差值的加权绝对值之和，为减少计算量，本文求取SAD值时只取其部分，在不影响编码质量的前提下降低复杂度，各方向预测模式的SAD值求取范围如图4所示，水平和垂直方向取奇数行(列)的SAD值，垂直向左和垂直向右取对角线各向其两侧水平位置平移两像素值，具体定义的各SAD值求取方法见式(15)～式(18)，其中Pij为某种预测模式下的像素值，i，j及Sij同式(11)。

图3 AVS 8×8子块及各预测方向

图4 帧内预测方向及SAD值范围

取MPPM集合α，DC模式固定为MPPM集合固定元素之一，初始化将DC预测模式加入集合，即α={ModeDC}。如式(15)～式(18)所示方法，计算各个方向下的SAD并作比较，将计算得到的两种最佳预测模式M1和M2加入集合α中;通过对多个测试序列的实验统计可知，若两种预测模式的SAD值相差多于1.48倍，则可把两者中较大者对应的预测模式筛除，即MPPM集合中余下较小者对应的预测模式和DC预测模式;最后计算MPPM集合中余下模式对应的率失真代价值，选择值最小的所对应的模式为当前子块的最佳预测模式，并编入比特流。

通过上面算法，剔除了至少两种预测模式，理论上排除了40%以上的不可能的预测模式，改进后的算法不但能快速筛选出当前子块的预测模式，而且可以很大程度上提高帧内编码效率。

2.3 快速算法流程

提出的快速算法结合上面提出的零系数块和快速MPPM两部分，具体算法流程如下:

1)以当前片(宏块)的量化步长QP为索引，查找前面设计的阈值表得到判定当前8×8子块为零系数块的阈值Th，计算当前8×8子块的残差SAD值，若SAD＜Th，即SAD在阈值之内，则直接编码当前8×8子块cbp元素，跳过下面的步骤，否则进行下面操作。

2)计算当前8×8子块SADV，SADH，SADDL和SADDR值，挑选其中SAD值较小的两个相应的预测模式，设为M1 和M2，则 MPPM 集合 α ={ModeDC，ModeM1，ModeM2}，并做进一步筛选，若SADM1/SADM2＞1.48，则把预测模式M1从MPPM集合中剔除，即α ={ModeDC，ModeM2}。

3)计算MPPM集合中余下模式的率失真代价函数值，选取其中值最小的相应的预测模式为当前子块最佳预测模式BPM=MPPMmax。

4)遍历当前宏块余下的8×8子块，重复1)～3)步骤，计算它们的最佳预测模式，并编入视频比特流。

3 测试结果

为验证本文提出的算法，选取种不同的CIF测试序列，分别比较采用本改进算法前后AVS的编码效率。测试条件如下:

GDM2.1参考软件，测试机Pentium4200，2 Gbyte内存，Enable Hadamard，Enable RD optimization，Off Rate Control，Enable FME，30 Frames，Frame Style IPPP，GoP=8。分别选取量化步长QP=20，24，28，32，36，Bitrate=768 000 bit/s，相应测试序列的PSNR，Time，Bitrate如表2所示。

表2列出了用本算法前后的不同序列的测试结果，可以看出平均PSNR下降控制在1%之内，平均比特数增加控制在2%，平均编码时间减少了31%以上。算法改进前后各测试序列在不同QP下平均编码时间如图5所示，从图可以看出改进后的算法大幅度提高了编码效率。

表2 本算法的测试结果

图5 改进算法前后编码效率

4 结语

本文提出了AVS帧内预测编码的改进算法，将零系数块和快速MPPM算法结合一起，把零系数的判定阈值做成数组表格，并且简化求各预测模式的SAD方法。改进后的快速AVS帧内预测算法，使帧内预测编码流程简化，算法复杂度下降，与AVS全搜索算法相比，在编码质量和码率变化极小情况下，平均编码时间减少31%以上，大大提高了编码效率。

［1］数字音视频编解码技术标准工作组.AVS技术创新报告(2002—2010)［M］.北京:人民邮电出版社，2011.

［2］ LEE Y，LIN Y.Zero－block mode decision algorithm for H.264/AVC［J］.IEEE Trans.Image Process，2009，18(3):524－533.

［3］ GB/T20090.2—2006，信息技术先进音视频编码第 2部分:视频［S］.2011.

［4］ KIM D，LEE Y.A fast intra prediction mode decision using DCT and quantization for H.264/AVC［J］.Signal Processing:Image Communication，2011(26):455－465.

［5］ KIM C，SHIH H，KUOC.Fast H.264 Intra－predictionmode selection using joint spatial and transform domain features［J］.J.Vis.Commun.Image R.，2006(17):291－310.

［6］刘代如，宋昊，李晓，等.H.264中的一种快速帧内预测判决算法［J］.电视技术，2007，31(4):10－11.

［7］靳栀艳，高志勇，张小云，等.H.264 High Profile的帧内预测模式快速判决算法研究［J］.电视技术，2012，36(21):8－11.