基于模式分组的帧内预测模式快速选择算法

谢晓燕，王 欢

(西安邮电大学 计算机学院，陕西 西安 710061)

近年来，数字视频技术迅速发展，而已颁布的视频标准H.264/AVC 在面对高清晰率、高帧率、高压缩率这些需求时，已经无法提供最佳的压缩效率［1］。因此在2010 年1 月，视频编码专家组ITU－T VCEG(Video Coding Experts Group)和运动图像专家组ISO/IEC MPEG(Moving Picture Experts Group)成立了JCT－VC(Joint Collaborative Team on Video Coding)联合小组，制定了新一代高效率视频编码标准HEVC(High Efficiency Video Coding)［2］，其核心目的是在H.264/AVC 的基础上，将压缩效率提高一倍［3］。为了达到这个目标，HEVC 必须采用更高复杂度的视频编解码算法，因此也引入了极高的计算复杂度［4］。

1 HEVC 预测编码

HEVC 预测编码包括帧内预测编码和帧间预测编码。帧内预测编码消除了大量空域冗余，它是利用同一帧已编码完成的像素点对即将编码的像素点进行预测。HEVC 帧内预测模式由原有的9 种增加到35 种，即DC 模式(模式0)，Planar平面模式(模式1)，和33 种角度预测模式(模式2 ～35)。33种角度预测方向与其对应的预测模式编号分别如图1 和图2所示。

预测模式的增加大大提高了帧内预测的准确性，但同时也带来了非常高的计算复杂度。HEVC 帧内预测通过采用粗模式选择(Rough Mode Decision，RMD)和最有可能预测模式(Most Probable Mode，MPM)相结合的方法来减少预测过程中所需的预测模式，从而降低计算复杂度。HEVC 帧内预测编码过程首先要进行RMD，遍历35 种预测模式，对每一种预测模式进行代价函数的计算，筛选出N 个代价值较小的预测模式作为候选模式，候选模式N 的数目在文献［5］中提出，如表1 所示。MPM 分别利用当前编码块的左方预测块与上方预测块的最佳预测模式来预测当前块的MPM，同时判断当前块的MPM 是否已经包含在RMD 的候选模式集中，若没有包含在内，则将当前块的MPM 加入到候选模式集中一起进行高精度的率失真优化(Rate Distortion Optimization，RDO)计算，最终选择出最优帧内预测模式。

图1 HEVC 帧内预测的33 个方向

图2 HEVC 帧内预测模式编号

表1 不同PU 尺寸的N 值

在帧内预测过程中，RMD 要对全部的预测模式进行代价函数计算，其运算量非常巨大。如果可以通过预先判断，在进行代价函数计算之前减少预测模式的数量，就能够有效地降低帧内预测的计算复杂度。很多学者就此提出了一些优化算法。文献［6］提出跳过变换量化等步骤，通过预处理提前排除一些可能性极小的预测模式。文献［7］提出了一种基于边缘信息的快速算法，利用图像处理中的索贝尔算子(Sobel operator)对4×4 的子块进行边缘检测，然后通过边缘方向的灰度直方图来确定最后的预测模式。文献［8］在文献［7］的基础上进行改进，提出一种基于显著边沿强度的快速模式选择算法，采用了不同的边缘检测算子，结果说明比文献［7］中的算法有了一定的提升。

文献［9］提出了一种基于梯度的HEVC 帧内预测快速模式选择算法。主要利用Sobel 算子计算当前PU 每个像素的梯度向量角。然后，在35 种预测模式里找到与梯度向量角最接近的角度对应的预测模式;与此预测模式垂直的预测模式就是此像素的最优预测模式。该算法在减少20%的编码时间同时，平均增加1%的码率。

文献［10］在帧内预测快速预处理阶段定义了一种简单的代价函数计算公式，并结合基于贝叶斯决策原理在帧内预测模式选择过程中训练的基于SATD(Hadamard transformed SAD)的率失真代价最佳阈值，最终将进行RMD 的35 种预测模式减少到9 种。这种低复杂度的帧内预测算法减少了近一半的编码时间，信噪比PSNR 减少了0.12 dB，但是这种方法与原编码相比平均增加了2.4%的码率。

在连续的视频图像中，相邻帧之间的图像纹理具有很强的相关性，根据这一特点文献［11］提出利用Co－located PU 及相邻PU 块的预测模式进行预判，来减少RMD 过程的预测模式数量，使得RMD 选择过程中预测模式数量减少到17 种，但是这种方法引起了码率明显的升高。

文献［12］使用边缘匹配检测器对预测模式进行选择，利用类似统计直方图的核密度估计方法来提高边缘匹配检测器的准确度，平均降低了36.7%的编码时间，与原有的算法相比增加了1.65%的码率。

文献［13］利用变换域边缘检测来缩小预测模式的选择范围。根据不同尺寸的PU，采用不同的类别系数，计算选取的类别系数绝对值之和，根据和值选取对应的权重对帧内预测模式进行选择。这样，只对一部分的预测模式进行计算，然而，这种方法使码率增加了2.8%。

以上几种快速算法都是利用一些额外的编码信息来减少计算复杂度。虽然算法的性能极其逼近标准算法，但是编码时间减少的幅度并不大，并且码率的增加也比较明显，均在1%以上。本文在不引进额外编码信息的基础上对RMD 过程进行优化，充分利用候选模式集中排列第一的预测模式与最优预测模式之间的强相关性，提出一种基于模式分组的帧内预测模式快速选择算法。该算法有效地降低了HEVC 帧内预测算法的计算复杂度，与HEVC 的测试模型HM10.0 相比，所提出的算法在基本不改变图像的质量下，编码时间平均减少了41.8%，而码率仅增加0.78%。

2 快速帧内预测模式选择算法

2.1 帧内预测模式选择可优化处的分析

HEVC 的测试模型(HEVC Test Model)HM［14］是由JCTVC 编写的一个标准代码库，可以对不同的测试场景进行仿真编码。在HM 中，RMD 过程的候选列表和其对应的代价值列表分别存放在uiRdModeList 和CandCostList 数组中。其中，CandCostList 按照代价值从小到大进行排列，uiRdModeList 存放的预测模式是按照其对应的代价值的大小进行排序，即候选列表uiRdModeList 中第1 个候选模式的代价值最小，第2个次之。一般情况下，代价值小的预测模式所对应的率失真代价值也低。因此，uiRdModeList 中排列第一的预测模式被选为最优预测模式的概率最高。为此，本文对uiRdModeList排列前3 位预测模式分别被选为最优预测模式的比例进行了统计，结果如图3 所示，排列第一的预测模式作为最优预测模式的比例为75.4%，第2 个模式和第3 模式平均比例分别为24.2%和0.04%。

图3 候选模式被选为最优预测模式所占的比例

为了使预测结果更加精确，HEVC 还将MPM 模式加入到uiRdModeList 中。接下来对最优预测模式在MPM 中的PU 比例进行统计，实验发现MPM 成为最优预测模式的概率高达85.1%。实验数据如表2 所示。

表2 MPM 选为最优预测模式的比例

由于uiRdModeList 中排列第一的预测模式及MPM 被作为最优预测模式的概率非常高，因此可以利用这一特性对算法进行优化，减少不必要的率失真代价的计算，从而提高编码效率。

2.2 基于模式分组的帧内预测模式快速选择算法

根据1.1 节的统计分析，得到MPM 以及uiRdModeList 中排列第一的预测模式被作为最优预测模式的比例非常高。因此如何在35 种预测模式中快速精确地找到成为候选模式集中排列第一的预测模式对降低帧内预测的计算复杂度至关重要。针对这一问题，本文提出了一种基于模式分组的快速模式选择算法。具体算法流程如下:

1)初次筛选:选取编号从3 开始，且编号为3 的倍数的所有角度预测模式进入初始的RMD 筛选模式列表。由于平面模式0、DC 模式1、水平预测模式10 以及垂直预测模式26 的预测值的计算比较特殊，所以将这4 种模式添加到筛选模式列表中。初始的RMD 筛选模式列表集为{0，1，3，6，9，10，12，15，18，21，24，26，27，30，33}。然后计算筛选模式列表中各模式的代价值，按照代价值从小到大的顺序将对应的模式加入到uiRdModeList 中。

2)再次筛选:由于相邻的角度预测模式间的预测值很接近，为了更加精确地找到最小代价值所对应的预测模式，本文继续对存放在uiRdModeList 中前3 个最小代价值对应的模式进行筛选。筛选过程如下:假设uiRdModeList 的前3 个预测模式分别为A，B，C，对应的代价值用CX表示，X 表示模式序号。分别对如下3 个组的模式进行计算:(A－1，A，A+1)(B－1，B，B+1)(C－1，C，C+1)。比较每组3 个模式的代价值之和与其标准差的和的大小，记为gi;即比较g1=(CA－1+CA+CA+1+δ1)，g2=(CB－1+CB+CB+1+ δ2)，g3=(CC－1+CC+CC+1+δ3)的大小，即

其中:δj为每组3 个代价值x1，x2，x3的标准差，μ 为它们的均值。

3)找出g1，g2，g3的最小值，该最小值所对应的组则包含可能的最优预测方向。将该组的3 个模式再次进行代价值的计算，直到找出代价值最小的模式作为uiRdModeList 中第1个预测模式，并将MPM 添加到uiRdModeList 中作为第2 个预测模式一起进行RDO 计算，最终选择出最优的预测模式。算法流程如图4 所示。

本文提出的快速算法首先对35 种预测模式进行初次筛选，选取15 个预测模式进入RMD 计算，这样大大减少了代价函数的运算量;经过再次筛选保证了每个预测模式都能被覆盖到，确保了算法对所有预测模式的适用性。经过这两步筛选，最终快速精确的求出候选列表uiRdModeList 中排列第一的预测模式。

图4 两种算法比较

3 仿真与验证

为了验证文中所提算法的有效性，将优化的算法集成到HEVC 的测试环境HM10.0 上。在全I 帧的结构下，采用18个通用视频标准序列进行实验，量化参数QP 取值分别为22，27，32，37，分别测试10 帧。这里主要从所提算法节省的编码时间以及付出的相应代价—峰值信噪比与编码码率来考虑算法的性能，具体包括Δtime，Δbitrate 和ΔY_PSNR［15］。

1)Δtime 指本文所提出的方法与HM 的编码时间之差的百分比，编码器计算复杂度的度量采用编码器平均执行时间的减少量Δtime 表示，定义如下

2)Δbitrate 指本文所提出的方法与HM 的编码码率之差的百分比，定义如下

其中:bitrateproposed(QPi)表示文中方法的编码码率;bitrateHM(QPi)表示HM 编码器得到的编码码率;编码码率越小说明视频图像的压缩效率越好。

3)ΔY_PSNR 指本文所提出的方法与HM 的峰值信噪比的百分比，定义为

式中:Y_PSNRpro(QPi)表示文中方法的亮度峰值信噪比;Y_PSNRHM(QPi)表示HM 编码器得到的亮度峰值信噪比。PSNR 表示视频图像的质量，PSNR 越高，表明图像的质量越好。

由于本文的快速算法是略过部分编码模式来达到降低计算复杂度的目的，所以从原理上讲选择出来的最终预测模式有可能不是最优的，必然会导致编码性能的降低——PSNR的下降或者输出的码率增大。但所提出的算法在明显的降低编码时间的同时只有极小码率增加和很小的PSNR 下降。表3 的数据可以看出本文所提出的方法与HM－10.0 相比，编码时间平均减少了41.8%，而Y_PSNR 降低了0.12 dB，bitrate仅增加了0.78%。对比文献［9－13］，码率的增加幅度平均在1%以上，本文所提的算法在大幅度降低编码时间的同时，码率仅控制在0.78%的增加。因此，本文的方法在保证视频质量基本不变的前提下，有效地降低了编码时间，提高了编码效率。

表3 节省的编码时间与编码质量的对比

为了更直观地表示本文所提出的算法对HEVC 编码器性能造成的影响。图5、图6 和图7 分别对CLASS A(2 560×1 600)、CLASS B(1 920×1 080)和CLASS E(1 280×720)的RD 曲线进行比较。横坐标表示输出的码率，纵坐标表示亮度峰值信噪比。

图5 Traffic(Class A)的RD 曲线

图6 Kimomo(Class B)的RD 曲线

图7 Vidyo3(Class E)的RD 曲线

从图中可以看出，本文中的算法与HM－10.0 原有的算法RD 曲线几乎重叠，表明本文算法与HEVC 算法相比，两者编码性能差异极小。由此证明了本文所提出的算法的有效性。

4 小结

基于模式分组的帧内预测模式快速选择算法充分利用了候选模式集中排列第一的预测模式与最优预测模式之间的强相关性。通过对35 种预测模式进行初次筛选和再次筛选，快速精确地找到成为最优预测模式概率最大的候选模式，大大减少了进入RDO 过程的模式数量，有效地降低了原有帧内预测编码算法的计算复杂度。实验结果表明，新的算法在牺牲了0.78%的码率与0.12 dB 的信噪比的同时，节省了41.8%的编码时间，提高编码效率，为将来多视点、高效率视频编码的研究及应用打下基础。

［1］KIM J，CHOE Y，KIM Y G.Fast coding unit size decision algorithm for intra coding in HEVC［C］//Proc.2013 IEEE Iternational Comference Consumer Electronics(ICCE).［S.l］:IEEE Press，2013:637－638.

［2］LAINEMA J，BOSSEN F，HAN W J，et al.Intra coding of the HEVC standard［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，22(12):1792－1801.

［3］田小平，田永召.面向交互应用的HEVC 编码性能分析［J］.西安邮电大学学报，2014，19(3):6－10.

［4］齐美彬，朱广辉. 利用纹理和空间相关性的HEVC 帧内预测模式选择［J］.中国图象图形学报，2014，19(8):1119－1125.

［5］ZHAO L，ZHANG L，MA S W，et al.Fast mode decision algorithm for intra prediction in HEVC［C］//Proc. IEEE Visual Communications and Image Processing(VCIP).［S.l］:IEEE Press，2011:1－4.

［6］MIN J，LEE S，KIM I，et al.Unification of the directional intra prediction methods in TMuC:B100［R］.Geneva，Switzerland:JCT－VC，2011.

［7］PAN F，LIN X，RAHARDJA S，et al.Fast mode decision algorithm for intra－prediction in H.264/AVC video coding［J］.IEEE Trans.Circuits and Systems for Video Technology，2005，15(7):813－822.

［8］WANG Jiaching，WANG Jhingfa，YANG Jarferr，et al. A fast mode decision algorithm and its VLSI design for H.264/AVC intra－prediction［J］.IEEE Trans. Circuits and Systems for Video Technology，2007，17(10):1414－1422.

［9］JIANG W，MA H，CHEN Y.Gradient based fast mode decision algorithm for intra prediction in HEVC［C］//Proc.IEEE the 2nd International Conference on Consumer Electronics，Communications and Networks(CECNet).［S.l］:IEEE Press，2012:1836－1840.

［10］SUN H M，ZHOU D J，GOTO S.A low－complexity HEVC intra－prediction algorithm based on level and mode filtering［C］//Proc.IEEE International Conference on Multimedia and Expo(ICME).［S.l］:IEEE Press，2012:1085－1090.

［11］MOTRAC A S，GUPTA A，SHUKLA M.Fast intra mode decision for HEVC video encoder［C］//Proc. IEEE the 20th International Conference on Software，Telecommunications and Computer Networks(SoftCOM).［S.l］:IEEE Press，2012:1－5.

［12］CHEN G，LIU Z Y，AKESHI I.Fast HEVC intra mode decision using matching edge detector and kernel density estimation alike histogram generation［C］//Proc. IEEE International Symposium on Circuits and Systems(ISCAS).［S.l］:IEEE Press，2013:53－56.

［13］TING Y C，CHANG T S，SHUKLA M.Fast intra prediction algorithm with transform domain edge detection for HEVC［C］//Proc.IEEE Asia Pacific Conference on Circuits and Systems(APCCAS).［S.l］:IEEE Press，2012:144－147.

［14］严顺卿.HEVC 帧内预测快速模式选择算法研究［D］.上海:上海交通大学，2012.

［15］蒋洁，郭宝龙.利用平滑区域检测的HEVC 帧内编码快速算法［J］.西安电子科技大学学报:自然科学版，2013，19(3):194－200.