目前面向高清视频的新一代高效率视频编码 (high efficiency video coding, HEVC) 标准已经被发布。HEVC中采用了复杂但有效的编码技术, 与H.264标准相比, 其能在保证相同重建视频质量的同时, 减少近50%的码率[1]。但较高的编码复杂度限制了HEVC的应用, 所以开发快速的HEVC编码技术一直是一个研究热点。HEVC沿用了H.264的基于预测变化量化的编码框架, 其中预测部分所占的编码时间最多。文中即针对预测部分中的编码单元 (coding unit, CU) 深度划分问题展开研究, 开发了能够快速进行CU划分的方法。
HEVC的基本处理单元是编码树状单元 (coding tree unit, CTU), 每个CTU又可以划分为1个或多个CU。最大CU, 即最大编码单元 (largest coding unit, LCU) 的尺寸为64×64像素, 而最小CU, 即最小编码单元 (smallest coding unit, SCU) 的尺寸为8×8像素, 其他可选的CU尺寸还包含16×16与32×32像素。CU划分深度被定义为4个等级 (0~3), 深度等级0、1、2、3分别对应的CU尺寸为64×64、32×32、16×16、8×8像素。所以CTU的最优CU划分可以认为是一个包含不同CU尺寸的CU组合。在视频图像中, 不同纹理复杂度区域对于图像的质量有着不同的影响[2], 而HEVC中CTU的四叉树编码结构, 通过遍历编码所有的CU深度, 可以为不同纹理复杂度的区域选择合适的CU划分, 有效地提高了视频编码的率失真性能。但在这个过程中需要遍历编码所有CU深度, 这极大地增加了视频编码的复杂度。所以一些研究者已经针对CU深度划分复杂度过高的问题展开研究, 并取得了一系列的成果。
文献[3]针对HEVC的帧内编码结构提出了快速进行CU划分的方法, 但是相较于帧内编码结构, 帧间编码结构以其较高的编码性能, 有着更广泛的实际应用。文献[4]提出了一个概率决定模型, 并在帧间预测编码之前通过此模型来去除一些CU划分方式, 从而加快了视频编码的速度。文献[5]提出的方法通过考虑最优预测单元模式, 次优预测单元模式及编码块标记来快速进行CU划分。文献[6]提出了根据编码前一帧同一空间位置的CU划分结果来跳过当前CU划分中某些备选划分的算法。文献[7]提出的算法通过联合考虑运动矢量, 编码块标记及像素自适应补偿滤波模块的信息来判断是否终止CU的进一步划分。文献[6-7]都需要用到相邻帧的信息, 所以不利用并行编码。类似于文献[7], 文献[8]也提出了一种联合考虑编码信息来判断是否需要提前终止CU划分的算法, 这里需要考虑的编码信息包括相邻CU的划分信息, 运动信息及同一CU深度的平均率失真代价。实验结果表明, 文献[4-8]的算法都可以降低视频编码的复杂度, 但其带来的编码率失真性能损失也比较大。所以怎样在有效降低算法复杂度的同时还能保证较高的编码率失真性能, 是CU快速划分研究中的难点。
论文通过分析相邻CU深度对应的失真及编码比特数满足的关系, 提出了预测相邻CU深度率失真代价的模型, 并基于此模型提出了一种既能保证编码率失真性能还能有效降低算法复杂度的CU划分方法。
1 HEVC中的CU划分HEVC中CTU的四叉树编码结构可以根据图像区域复杂度进行递归式自适应划分, 从而提高编码的率失真性能。划分时根据CU深度, 由深度0到深度3依次划分。对每个CU块采用帧内/帧间模式进行编码, 经过预测、变换、量化、熵编码等过程得到该模式对应的码率和失真。最终通过计算率失真代价来判断最优的CU划分方式。在HEVC中率失真代价由 (1) 式计算
(1) |
式中, Di、Ri、Ji分别表示第i个CU深度对应的失真、码率及率失真代价。λ是拉格朗日因子。
HEVC的测试模型HM[9]中的CU划分的具体步骤为:
1) 首先对深度为0的CU进行编码, 得到最优编码模式对应的率失真代价J0;
2) 将深度为0的CU进行四叉树分割, 得到4个大小32×32的深度为1的CU, 并对每个深度为1的CU进行编码得到最优编码模式对应的率失真代价J1;
3) 将每个深度为1的CU进行四叉树分割, 每个深度为1的CU都会得到4个大小16×16的深度为2的CU, 并对深度为2的CU进行编码, 得到每个深度为2的CU的最优编码模式对应的率失真代价J2;
4) 将每个深度为2的CU进行四叉树分割, 每个深度为2的CU都会得到4个大小8×8的深度为3的CU, 并对深度为3的CU进行编码得到每个深度为3的CU的最优编码模式对应的率失真代价J3;
5) 通过步骤1) 至步骤4) 已经得到了所有CU块对应的率失真代价。从本步骤开始即通过比较率失真代价来获得最优的CU划分方式。首先计算每个深度为2的CU对应的四叉树分割后的4个深度为3的CU代价之和, 若代价之和大于该深度为2的CU的代价, 则此次比较中, 深度为2的CU划分为较优划分;
6) 类似步骤5), 比较所有深度的CU块代价及其四叉树分割后的4个CU块代价之和。最终选择率失真代价最小的一组CU划分为整个LCU的最优CU划分方式。
图 1所示为采用HM12.0[9]编码器编码后的1帧最优的CU划分方式。由图可以看出, CTU的四叉树编码结构可以为不同纹理复杂度的区域选择合适的CU划分, 即纹理越复杂的区域其划分的CU块越小, 这样可以用更加精细的编码设置来编码此区域, 从而有效提高了视频编码的率失真性能。
由以上步骤可知, 为了能够获得最佳的划分方式, HEVC采用全深度搜索方式, 对每个CU深度的所有编码模式遍历编码以确定最优的编码参数。这虽然能够获得最优的划分结果, 但是其极高的复杂度限制了其在实际中的应用, 因此研究快速CU划分方法具有重要的实际应用价值。
2 快速CU划分方法在HEVC中, 需要对所有深度的CU进行编码以获得其对应的率失真代价, 然后选择代价最小的为最优CU划分方式。尽管这种方法可以得到最优的结果, 但编码复杂度极高。本文首先通过理论推导和实验分析, 得到了相邻CU深度的码率和失真关系, 从而利用此关系得到了相邻深度CU代价预测的模型。通过此模型即可在编码完当前深度CU后快速地预测下一深度CU的代价, 假如当前深度CU代价小于下一深度CU的代价, 则选择当前深度CU对应的划分为整个CTU最优的CU划分方式。下面将详细说明提出的算法。
2.1 相邻CU深度的失真和编码比特数关系在HEVC中, 编码残差经离散余弦变换 (discrete cosine transform, DCT) 后的系数符合拉普拉斯分布[10], 且不同CU深度的拉普拉斯分布参数不同, 即符合混合拉普拉斯分布[11], 则每个深度的DCT系数分布如 (2) 式所示
(2) |
式中,
(3) |
则第i个CU深度对应的失真可以由 (4) 式[11]计算, 这里失真用均方差 (mean square error, MSE) 表示
(4) |
式中,q表示量化步长, δ表示量化偏移量。
对于帧间编码的图像, δ的典型取值为1/6[12], 则由 (4) 式可以得到 (5) 式
(5) |
所以相邻CU深度对应的失真比可由 (6) 式表示。
(6) |
通过实验发现相邻CU深度对应的残差标准差满足 (7) 式所示的线性关系, 其中k表示斜率。图 2中给出了2个标准测试序列的实验结果, 使用HM12.0[9]编码视频, 采用低时延 (low delay, LD) 编码结构, 量化参数 (quantization parameter, QP) 为27。
(7) |
基于 (7) 式, 并结合DCT变换能量守恒关系可以得到 (8) 式[13]
(8) |
式中,θ为模型参数。将 (8) 式代入 (3) 式可得
(9) |
将 (9) 式代入 (6) 式可得到 (10) 式。
(10) |
在低码率的情况下,
(11) |
即相邻CU深度对应失真之间满足线性关系。图 3a) 的结果也实验验证了失真的线性关系, 此关系最终用 (12) 式表示, 其中αi为模型参数
(12) |
由于较之前的视频编码标准, HEVC采用了大量的复杂编码技术, 这有效降低了视频编码比特数, 但同时也显著提高了头比特在压缩码流中所占的比重[12]。视频编码中的头比特通常包含四叉树划分信息、运动矢量信息、预测模式信息以及滤波参数信息等。文献[12]通过实验验证, 在使用HEVC编码器编码后的码率中, 头比特所占比重随着QP的增大而增大, 并最终超过纹理比特所占的比重。由于头比特不同于纹理比特, 通常无法通过理论推导进行建模估计。本文采用实验的方式来分析相邻CU深度对应编码比特数的关系。
由实验发现不同CU深度对应的纹理比特与头比特都分别满足线性关系, 图 3b)、c)给出了BasketballDrill序列的实验结果。所以相邻CU深度的编码比特数关系可以用 (13) 式表示
(13) |
式中,Ri-1, t和Ri-1, h分别表示编码第i-1个深度CU产生的纹理比特与头比特。βi, t和βi, h为相应的模型参数。
2.2 算法步骤本文提出结合率失真代价预测的快速CU划分算法, 即C-CU (cost based CU) 的详细步骤如图 4所示。在提出的算法中, 模型参数αi、βi, t、βi, h需要更新。本文采用最小二乘法拟合得到这些参数, 并且考虑视频内容是不断变化的, 参数会在每秒开始的图像组进行更新。
当更新模型参数时, CU划分方法采用HM中的方法。考虑到LD与随机接入 (random access, RA) 编码结构, 不同的帧会被分配不同的时间等级, 并且不同时间等级的帧在编码时的重要性也是不一样的, 这反映在编码上就是要使用不同的编码参数组合来编码不同的帧, 以获得较高的率失真性能。因此, 在提出的算法中, 不同的时间级都会通过最小二乘法拟合得到适合该时间级模型参数。
然后, 使用更新的参数, 对当前CU进行编码。基于 (1) 式、(12) 式、(13) 式, 编码完第i-1个深度的CU后, 会获得Di-1, Ri-1, t, Ri-1, h, Ji-1, 则深度为i-1的CU对应的4个四叉树分割的CU块的率失真代价之和Ji可用下式估计。
(14) |
比较Ji与Ji-1的值即可判断是否需要进一步划分。若Ji<Ji-1, 则进行进一步的划分, 若Ji≥Ji-1则停止划分, 继续编码下一个LCU, 直到编码完当前帧及整个视频序列。
3 实验结果与分析下面设计实验来验证提出算法的性能。选择标准内容特性丰富的5类共18个视频序列建立测试序列数据库。使用HM12.0编码器对序列编码, 编码结构为LD与RA, QP被分别设置为22、27、32、37。其他编码参数参照标准推荐值[14]进行设置。使用被广泛采用的BD-rate[15]测度来评价视频编码的客观率失真性能, 即BD-rate为正值表明编码率失真性能下降。(15) 式中定义的ΔT来评价算法的复杂度。
(15) |
式中, Tpro为改进算法的编码时间, THM为HM12.0对应的编码时间。
为了更加直观地说明文中提出算法性能, 文献[4, 7-8]中的算法也被实现, 并且在性能比较时HM12.0的算法被选为基准算法。表 1和表 2分别给出LD与RA 2种编码结构的实验结果。首先, 由实验数据易看出, 相较于HM12.0的算法, 文中提出C-CU算法的客观率失真性能的降低是最少的, 对于LD与RA编码结构, BD-rate分别为0.2与0.6, 而其他3种算法的BD-rate值都超过了1。其次, 考虑编码时间的降低, 文献[7]算法降低的时间是最多的, 其次为文中提出的C-CU算法, 而文献[4, 8]算法降低编码时间较少。如前面分析, 文献[7]算法首先明显降低了视频编码的客观率失真性能, 另外其需要用到相邻已编码帧的信息, 这使得视频不能够并行编码, 限制了此算法的应用。所以综上, 文中提出的C-CU算法可以在保证视频编码率失真性能的同时, 有效地降低视频编码复杂度。另外提出算法的参数是实时更新的, 也适合于场景切换的视频应用。
在分析了HEVC相邻CU深度对应失真及码率关系基础上, 提出了结合率失真代价预测模型的快速CU划分算法。实验结果表明所提算法在保证编码率失真性能前提下, 有效地降低了算法复杂度。同时在提出算法中, 模型参数每隔一秒会被更新一次, 可以有效地适应包含场景切换的视频应用。
[1] | Sullivan G J, Ohm J, Han W J, et al. Overview of the High Efficiency Video Coding (HEVC) Standard[J]. IEEE Trans on Circuits and Systems for Video Technology, 2012, 22(12): 1649–1668. DOI:10.1109/TCSVT.2012.2221191 |
[2] |
张兆林, 史浩山, 万帅.
基于线性回归分析的视频质量评估方法[J]. 西北工业大学学报, 2012, 30 (3): 451–456.
Zhang Zhaolin, Shi Haoshan, Wan Shuai. A Computationally Efficient Video Quality Assessment Method Based on Linear Regression Analysis[J]. Journal of Northwestern Polytechnical University, 2012, 30(3): 451–456. (in Chinese) |
[3] | Zhang T, Sun M T, Zhao D B, et al. Fast Intra Mode and CU Size Decision for HEVC[EB/OL](2016-4-20).[2016-5-28]. http://ieeexplore.ieee.org/document/7457241. |
[4] | Na T, Na S, Yoo K. A Probabilistic-Based CU Size Pre-Determination Method for Parallel Processing of HEVC Encoders[C]//Proceedings of the IEEE International Conference on Consumer Electronics, Las Vegas, 2015:327-330 |
[5] | Wu J F, Guo B L, Hou J, et al. A Fast CU Encoding Scheme Based on the Joint Constraint of Best and Second-Best PU Modes for HEVC Inter Coding[C]//Proceedings of the IEEE International Conference on Imaging Systems and Techniques, Macau, 2015:1-5 |
[6] | Lee H, Kim K, Kim T, et al. Fast Encoding Algorithm Based on Depth of Coding-Unit for High Efficiency Video Coding[J]. Optical Engineering, 2012, 51(6): 067402. DOI:10.1117/1.OE.51.6.067402 |
[7] | Ahn S, Lee B, Kim M. A Novel Fast CU Encoding Scheme Based on Spatiotemporal Encoding Parameters for HEVC Inter Coding[J]. IEEE Trans on Circuits and Systems for Video Technology, 2015, 25(3): 422–435. DOI:10.1109/TCSVT.2014.2360031 |
[8] | Shen L, Liu Z, Zhang X, et al. An Effective CU Size Decision Method for HEVC Encoders[J]. IEEE Trans on Multimedia, 2013, 15(2): 465–470. DOI:10.1109/TMM.2012.2231060 |
[9] | Bossen F, Flynn D, Suhring K. HM Software[EB/OL]. (2013-5-28)[2016-05-28]. http://hevc.kw.bbc.co.uk/svn/jctvc-hm/ |
[10] | Gao W, Kwong S, Yuan H, et al. DCT Coefficient Distribution Modeling and Quality Dependency Analysis Based Frame-Level Bit Allocation for HEVC[J]. IEEE Trans on Circuits and Systems for Video Technology, 2016, 26(1): 139–153. DOI:10.1109/TCSVT.2015.2444671 |
[11] | Lee B, Kim M. Modeling Rates and Distortions Based on a Mixture of Laplacian Distributions for Inter-Predicted Residues in Quadtree Coding of HEVC[J]. IEEE Signal Processing Letters, 2011, 18(10): 471–574. |
[12] | Lee B, Kim M, Nguyen Q T. A Frame-Level Rate Control Scheme Based on Texture and Nontexture Rate Models for High Efficiency Video Coding[J]. IEEE Trans on Circuits and Systems for Video Technology, 2014, 24(3): 465–478. DOI:10.1109/TCSVT.2013.2276880 |
[13] | Pao I M, Sun M T. Modeling DCT Coefficients for Fast Video Encoding[J]. IEEE Trans on Circuits and Systems for Video Technology, 1999, 9(4): 608–616. DOI:10.1109/76.767126 |
[14] | Gong Y, Wan S, Yang K, et al. Rate-Distortion-Optimization-Based Quantization Parameter Cascading Technique for Random-access Configuration in H.265/HEVC[EB/OL]. (2016-3-8)[2016-5-8]. http://ieeexplore.ieeee.org/document/7428876 |
[15] | Yang K, Wan S, Gong Y, et al. Perceptual Based SAO Rate-Distortion Optimization Method with a Simplified JND Model for H.265/HEVC[J]. Signal Processing:Image Communication, 2015, 31(2): 10–24. |