VPx帧内压缩的快速算法

目前主流的视频编码标准包括3个体系：国际联合视频工作组(Joint Video Team，JVT)的H.26x、国内数字音视频编解码技术标准工作组(Audio Video Coding Standard，AVS)的AVSx和Google公司的VPx[1-4]。其中，VPx编解码器(COder/DECoder，CODEC)凭借开源和免专利费的优势，在全球范围内各种网络浏览器的支持率已经超过92%[5]。

视频编码标准中的是决定最终编码效率的关键，但由于该过程的算法复杂度高而导致非常耗时，因此对帧内压缩快速算法的研究显得尤为必要。近年来这方面的研究主要集中在H.264和H.265/高性能视频编码(High Efficiency Video Coding，HEVC)[6-9]。文献[6]通过统计方法与阈值法，文献[7]基于纹理方向检测，文献[8]利用时间与时空相关性，分别对HEVC帧内预测进行加速，实现将编码时间减少24~30%。文献[9]提出梯度法加快确定帧内模式，将编码时间减少15%，再结合支持向量机(Support Vector Machine，SVM)加快确定HEVC编码单元划分，使编码时间进一步减少到50%以上。文献[10]对HEVC和VP9两种标准的帧内压缩算法及其对编码效率的影响进行了比较。本文针对VPx的帧内压缩提出了加速算法，并通过实验验证了算法的效果。

1 VPx帧内压缩

帧内压缩是基于相邻像素之间的相关性，通过当前块的相邻块对其进行预测，并对预测值与实际值之间的残差进行一系列变换、量化和熵编码，以消除空间冗余达到压缩的目的。图1所示为VPx帧内压缩框图。VPx帧内压缩以宏块/超级块为单位，其中VP8标准的宏块大小为16×16，VP9标准的超级块大小为64×64。VP8采用4×4的子块划分方式将宏块划分为4×4大小的子块，其变换包括离散余弦变换(Discrete Cosine Transform，DCT)和沃尔什-哈达玛变换(Walsh-Hadmard Transform，WHT)。VP9采用四叉树子块划分方式将超级块划分为4×4~64×64大小的子块，其变换包括非对称离散正弦变换(Asymmetric Discrete Sine Transform，ADST)和DCT。

VPx帧内预测分为亮度块预测和色度块预测。亮度块预测包括以下10种预测模式：

其中，DC和TM分别为直流和真运动预测模式，另外8种为角度预测模式，图2中以4×4的亮度块预测为例说明。HE和VE分别为水平和垂直预测模式，LD和RD分别为45°和135°预测模式，VL和VR分别为63°和117°预测模式，HD和HU分别为153°和207°预测模式。

在帧内压缩过程中，要从上述10种预测模式中选择一种，使码率在不超过某最大码率的情况下失真最小。VPx采用率失真优化(Rate Distortion Optimization，RDO)方法来寻找码率和失真之间的平衡，其率失真代价函数表示为：

其中，Jmode为预测模式对应的率失真代价，Dmode为失真，λmode为拉格朗日系数，Bmode为所需比特数。通过计算预测残差的平方和(Sum Squared Error，SSE)得到失真Dmode。对于每个亮度子块，要进行10次变换、量化、反量化和反变换的重构过程，根据率失真代价Jmode最小的原则选取最终预测模式，进入熵编码。

假设帧内压缩图像宽度和高度分别为W和H，宏块/超级块大小为C×C，则总的宏块/超级块数为：

以1 280×720的图像为例，宏块大小为16×16，按4×4的子块划分方式，得到4×4的亮度子块，则RecCnt的理论值为576 000次，意味着如此大量次数的变换、量化、反量化、反变换和率失真计算代价。

2 快速算法

为减少帧内压缩的运算量，可以从两方面入手：一方面减少亮度子块的重构次数，另一方面优化帧内压缩的算法程序。下面主要讨论前者。

2.1 最近邻加速法

最近邻加速法利用当前子块与其最近邻子块的相关性，以最近邻子块的预测模式作为其最终预测模式，从而减少遍历预测模式带来的重构次数。

图3所示为将图像中一个16×16的宏块划分为16个4×4的亮度子块，虚线框表示当前子块，箭头所在子块表示其候选最近邻子块。

首先根据当前子块在宏块中的位置确定最邻近子块。设当前子块为Si，j，3个候选最近邻子块分别为Si-1，j、Si，j-1、Si-1，j-1。S1，1作为第一个子块，不存在最近邻子块。

将Si，j的最邻近子块定义为NBi，j，当候选最近邻子块仅存在于水平和垂直方向时，有：

当候选最近邻子块存在水平、垂直和对角方向时，则先根据不同方向上子块的率失真代价从候选最近邻子块中确定最近邻子块：

其中，Jl，m为3个方向率失真代价Ji，j-1、Ji-1，j、Ji-1，j-1中最小的，l和m代表最近邻子块的坐标。则有：

假设最近邻子块NBi，j的最佳预测模式为mode，对当前子块在该模式下进行重构和率失真Ji，j计算。当满足如下关系时，将模式mode作为当前子块的最终预测模式。

否则将对当前子块进行预测模式的遍历，得到最终预测模式。

在最近邻子块的判断过程中，要在当前宏块/超级块范围内，保存当前子块Si，j的前序子块的最佳预测模式和与其对应的率失真，用于与当前子块直接比较以简化率失真计算。2.2 阈值加速法

对当前子块的率失真Ji，j设置阈值TH。当某一预测模式下的Ji，j满足如下关系时，终止对预测模式的遍历，将该预测模式作为当前子块的最终预测模式：

否则将继续进行下一个预测模式。如果所有预测模式对应的率失真均不满足式(9)，则根据RDO原则选取最佳预测模式。

阈值的选取直接影响最终结果。阈值越大，越容易提前终止对预测模式的遍历，从而提高压缩速度，同时降低压缩质量；反之阈值越小，越难满足阈值要求，遍历的预测模式越多，从而保持压缩质量，但压缩速度提高少。式(10)给出了阈值选取公式：

其中，J表示已有子块率失真的集合，Jmax和Jmin分别为J中的最大率失真和最小率失真，Coef取值0.062 5。

2.3 两级加速法

采用最近邻法加速时，如果当前子块存在最近邻子块，则能够减少子块重构运算量；否则仍需要对所有预测模式进行遍历。采用阈值加速法时，如果当前子块的率失真满足阈值条件，则能够减少子块重构运算量；否则仍需要对所有预测模式进行遍历。

将上述两种加速方法结合，构成如图4所示的两级加速法，使帧内压缩速度进一步提高。两级加速法的第一级为最近邻加速，第二级为阈值加速。