基于深度预测的HEVC编码单元快速划分算法

赵 宏 蒋雨晨 李靖波

(兰州理工大学计算机与通信学院 甘肃 兰州 730050)

基于深度预测的HEVC编码单元快速划分算法

赵 宏 蒋雨晨 李靖波

(兰州理工大学计算机与通信学院 甘肃 兰州 730050)

高效视频编码HEVC(High Efficiency Video Coding)采用计算复杂度较高的率失真优化方法对编码单元CU(Coding Unit)划分进行判决，具有较高的时间复杂度，编码所需时间较长。为降低HEVC编码复杂度，加快编码速度，提出一种基于深度预测的CU快速划分算法。首先依据当前CU与周围相邻CU和参考帧中当前位置CU的深度相关性，预测当前CU的最优深度，然后使用相邻相关分割法或依据当前CU深度和预测深度的关系对当前CU进行递归划分。为减少预测带来的误判，在CU深度级别由2级到3级的划分中，使用率失真或百分比的方式进行二次判定。实验结果表明，该算法与原始的HEVC编码方法相比，在亮度峰值信噪比减小0.07 dB，编码比特率增加0.88%的情况下，整体编码单元划分时间缩短37.7%，具有较高的时间效率。

高效视频编码(HEVC) 深度预测 快速划分 编码单元(CU)

0 引 言

高效视频编码HEVC主要面向高清(1 920×1 080)，甚至超高清分辨率(7 680×4 320)视频的应用[1-2]。为了更有效地对视频信息进行压缩，HEVC在沿用经典的基于块的混合编码方式的基础上，采用灵活的四叉树结构组织编码单元CU(Coding Unit)、预测单元PU和变换单元TU(Transform Unit)[3]，其中，CU是编码的基本单元，大小是以2的幂次方为宽高的正方形，有64×64、32×32、16×16、8×8等四种尺寸，对应深度级别分别为0级到3级。按照四叉树结构，采用递归的方式对CU进行划分，使得HEVC编码效率得到显著提高，但编码复杂度也随之增加。

HEVC标准测试模型HM10[4]在对测试场景进行仿真编码时，按照四叉树结构，由64×64的最大编码单元开始，采用递归的方式对CU进行划分。通过遍历每一个深度的CU，并使用所有可能的预测模式计算其率失真代价RD-Cost(Rate Distortion Cost)，选择最小RD-Cost的划分结构作为最佳CU划分模式，这一过程导致较高的计算复杂度。文献[5-6]通过在CU划分过程中设置阈值，并且和率失真代价相比较，确定是否进一步划分，这种方式并未考虑视频图像纹理的特殊性，同时对视频压缩质量影响较大。文献[7-8]分别从帧内预测和帧间预测的角度，对CU划分进行预判，但是忽略了在特定深度区间上提前终止CU分割。

本文提出一种基于深度预测的CU快速划分算法。该算法根据Cur_CU(当前编码CU)的Left_CU(与左边界相邻的CU)和Up_CU(与上边界相邻的CU)以及Col_CU(参考帧中当前位置CU)的深度来预测Cur_CU的最优深度，依据当前深度与预测深度的关系决定是否对Cur_CU继续划分，减少不必要的遍历和率失真代价计算，以保证压缩后视频质量为前提，最大程度降低计算复杂度，缩短视频编码时间。

1 HM中CU划分及复杂度分析

文献[9]详细介绍了HM10的CU划分过程。HM10中，首先分割一帧图像为若干最大编码单元LCU(Largest CU)，LCU尺寸为64×64，深度为0。对LCU计算其RD-Cost，然后将LCU分割成4个尺寸为32×32，深度为1的子CU，并分别计算其RD-Cost。之后以Z字形扫描顺序，按照深度优先的方式对4个子CU继续划分，直至子CU尺寸为8×8，深度为3时结束。对已完成划分的LCU，从深度为3的子CU开始，采用率失真优化方法进行划分模式判决，如果4个8×8子CU的RD-Cost之和小于其对应的16×16的父CU的RD-Cost，则保留这个8×8分割，否则合并为16×16的模式。按照这种方式，逐级向上处理，回溯至深度为0的LCU时，判决结束。率失真是指编码的码率与图像失真度之间的相互关系，率失真代价函数定义为：

J(CUd)=(SSEluma+wChroma·SSEChroma)+λd·Bd

(1)

其中，d是Cur_CU的深度，Bd是编码Cur_CU的候选预测模式中的总比特数，λd表示拉格朗日乘数。在帧内预测中，wchroma为0.57[10-11]，SSEluma和SSEchroma分别是亮度和色度的原始输入图像块和预测块之间的误差平方和，如式(2)所示：

(2)

其中，IO(i,j)是原始输入图像块的像素值，IR(i,j)是重建块的像素值。

在HM10的CU划分过程中，确定LCU的最优四叉树结构，需要遍历85种CU模式(1个64×64模式，4个32×32模式，16个16×16模式，64个8×8模式)[12]，并且需进行106(85+16+4+1)次相关RD-Cost计算和比较。在计算RD-Cost时，每一种CU模式又需遍历35种帧内预测模式，以及4×4、8×8像素等不同大小的TU模式[13]。如此带来的计算复杂度，限制了HEVC的实际应用。因此，以不降低视频质量为前提，为HEVC编码建立一种快速CU划分算法，是非常必要的。

2 基于深度预测的CU划分算法

2.1CU深度预测

HM10中，CU的深度级别为0到3，深度较大的CU模式适用于处理图像纹理较复杂的区域，深度较小的CU模式适用于处理平滑区域。对比区域图像纹理特性与其CU模式发现，如图1所示，Cur_CU的最优深度与其Unit单元(左上角8×8像素块)关于左边界线对称的8×8像素块所在的最小编码单元Left_CU的深度left_dep，关于上边界线对称的8×8像素块所在的最小编码单元Up_CU的深度up_dep以及在参考帧中当前位置的8×8像素块所在的最小编码单元Col_CU的深度col_dep存在密切关系。已知left_dep，up_dep和col_dep，定义通过式(3)和式(4)可得到Cur_CU的预测深度pre_dep。依据pre_dep和cur_dep(Cur_CU的当前深度)的关系，确定是否对Cur_CU进一步划分。

图1 CU深度预测

temp=α·left_dep+β·up_dep+γ·col_dep

(3)

(4)

其中，α、β、γ分别为Left_CU、Up_CU和Col_CU的预测代价，且满足α+β+γ=1。通过对JCTVC提供的通用标准测试序列进行观察统计，验证α=0.2、β=0.2、γ=0.6为较优取值。

2.2 基于深度预测的CU划分判决

将Cur_CU所在的LCU表示为Cur_LCU，同理可得Left_LCU、Up_LCU和Col_LCU。分别用dep1、dep2表示与Cur_CU左边界和上边界相邻的所有CU(不包含left_CU和Up_CU)的最大深度，用dep3表示Col_CU中子CU的最大深度。获得Cur_CU的预测深度pre_dep后，若满足cur_dep=pre_dep=0或cur_dep=pre_dep=1，且dep1≤2&&dep2≤2&&dep3≤1，即Cur_CU的预测深度pre_dep、相邻CU的最大深度dep1和dep2以及Col_CU中子CU的最大深度dep3都比较小，说明Cur_CU内部及其相邻区域的纹理特性都比较简单，此时可终止对Cur_CU的划分。

当cur_dep=pre_dep=0或cur_dep=pre_dep=1,而dep1=3||dep2=3||dep3≥2时，说明Cur_CU内部总体较平滑，但在边缘位置可能存在纹理较复杂的区域。此时采用相邻相关分割法对Cur_CU进行划分。即参照相关CU的深度，直接将Cur_CU边缘纹理复杂区域划分至相应深度，之后采用率失真优化方法进行验证，以消除误判。

相邻相关分割法中涉及平滑区域与复杂区域的边界在相邻CU中的分布，分别有三种情况，如图2所示。由于每帧图片中的图像纹理特性具有随机性，所以绝大部分情况如图2中a或c所示，即相邻CU公共边附近区域的纹理复杂度差异性较小。

图2 复杂区域与平滑区域边界分布

相邻相关分割法 如图3所示，Up_LCU和Left_LCU为已编码的LCU。假设编码前Cur_CU的深度cur_dep=0，且求得pre_dep=0。由于与Cur_CU左边界相邻的2、4号CU的深度较大，预测Cur_CU中左下角阴影部分为纹理复杂区域，深度与相邻2、4号CU的深度相等，虚线部分为预划分结果。但实际可能出现以下情况，复杂区域与平滑区域的边界包含于2、4号CU或阴影部分中，边界的左侧是复杂区域，右侧是平滑区域，这种情况将导致对Cur_CU中阴影部分深度的误判。为消除这种误判，对预划分结果使用率失真优化方法进行验证，决定是否合并不必要的划分，逐级向上判断，确定最优CU模式。

图3 相邻相关分割法图例

如果pre_dep>cur_dep，采用递归的方式对Cur_CU进行划分，在深度级别0到1和1到2的划分过程中，不采取任何判断，直接划分。深度较大的CU模式计算复杂度高，编码时间长，因此在深度级别2到3的划分过程中，需进一步验证以减少误判。首先通过计算参考帧中Col_CU所在的深度为1的CU中，深度为3的CU所占百分比pro，预测Cur_CU的纹理复杂程度。如果pro大于50%，表明该区域纹理特性复杂，可以直接划分。如果pro小于50%，则采取率失真优化方法，判断是否需要进一步划分。

2.3 基于深度预测的CU快速划分算法的整体流程

对于一帧图像，首先将其完全分割为若干LCU，然后以Z扫描顺序对所有LCU进行划分。划分过程中，最先输入的Cur_CU是LCU，然后获取相应Left_CU、Up_CU及Col_CU的深度并计算Cur_CU的预测深度pre_dep。如果pre_dep较小，而周边相邻CU深度较大，采用相邻相关分割法对Cur_CU进行划分；如果pre_dep较大，采用递归的方式进行划分。算法具体流程如图4所示。

图4 算法整体流程图

算法具体流程如下：

Step1 输入当前需编码的Cur_CU。

Step2 确定其Left_CU、Up_CU以及Col_CU，并获得相应深度left_dep、up_dep和col_dep。

Step3 根据式(3)和式(4)计算Cur_CU的预测深度pre_dep。

Step4 如果cur_dep=pre_dep=0或cur_dep=pre_dep=1，转Step5，否则转Step6。

Step5 如果满足条件dep1≤2&&dep2≤2&&dep3≤1转Step11，否则转Step6。

Step6 采用相邻相关分割法分割Cur_CU，转Step11。

Step7 如果cur_dep=pre_dep=2，转Step11。

Step8 如果cur_dep<2&&pre_dep>cur_dep,分割Cur_CU为4个子CU，按照Z字形扫描顺序分别表示为CU1、CU2、CU3、CU4，以CU1、CU2、CU3、CU4为输入的Cur_CU并转Step1。

Step9 如果cur_dep=2&&pre_dep=3，求出参考帧中Col_CU所在的深度为1的CU中，深度为3的CU所占百分比pro。如果pro大于50%，分割Cur_CU为4个子CU，转Step11，否则转Step10。

Step10 将Cur_CU预划分为4个子CU，按照Z字形扫描顺序分别表示为CU1、CU2、CU3、CU4，如果满足RD_Cost(Cur_CU)>RD_Cost(CU1) + RD_Cost(CU2) + RD_Cost(CU3) + RD_Cost(CU4)，分割Cur_CU为4个子CU，之后转Step11，否则直接转Step11。

Step11 终止CU划分，转Step12。

Step12 结束。

3 实验结果及分析

在HEVC标准测试模型HM10中添加本文算法，同HEVC原有编码算法进行对比测试。实验测试平台为：处理器Intel Core i5，主频2.6 GHz，内存4 GB，操作系统64位windows7。实验采用4个JCTVC提供的通用标准测试序列，分别为BasketballDrive_1920x1080, ChinaSpeed_1024x768，CITY_704x576以及CREW_352x288。 实验在encoder_intra_main配置下进行，量化参数QP值分别设置为22,27,32和37。实验中，编码性能使用比特率BR(Bit Rate)和峰值信噪比PSNR(Peak Signal to Noise Ratio)度量，编码复杂度使用消耗的编码时间度量。本文使用亮度峰值信噪比增量(▽PSNR(Y))、编码比特率增量(▽BR)和编码时间增量(▽T)三个参数作为评价指标[14]，对比本文算法和HM10原有的编码算法，其计算公式如下：

▽PSNR(Y)=PSNR(Y)p-PSNR(Y)HM10

(5)

(6)

(7)

其中，PSNR(Y)p，Bp和Tp是本文提出的快速划分算法的亮度分量的PSNR，比特率和总编码时间；PSNR(Y)HM10.0，BHM10.0和THM10.0是HM10原有编码算法的亮度分量的PSNR，比特率和总编码时间。

如表1所示，在encoder_intra_main配置和不同QP值情况下，相比于HM10原有的编码算法，本文采用的基于深度预测的CU快速划分算法通过预测和判断，跳过部分深度级CU的预划分和率失真代价计算，避免额外的计算量，使得编码效率明显提高。在相同测试序列的不同QP值配置下，随着QP值的增加，编码比特率增量依次递减，但节省的编码时间却在逐渐增加。对于整体的编码效率，CU划分时间平均减少37.37%，编码比特率平均增加0.88%，而亮度峰值信噪比增量的波动范围很小，仅减少0.07dB，本文算法在几乎不影响视频质量的情况下，降低了编码复杂度，具有时间效率。

表1 本文算法与HM10编码算法性能比较

续表1

4 结 语

HM10原有的CU划分过程计算复杂度高，编码效率低。针对该问题，本文提出一种CU快速划分算法，通过参考与当前CU左边界和上边界相邻的CU以及参考帧中当前位置的CU的深度，预测当前CU的最优深度，根据预测的最优深度对当前CU进行划分，跳过不必要的CU遍历和率失真代价比较。实验结果验证了本文算法的高效性，相比HM10原有的编码算法，可在编码比特率平均上升0.88%的情况下，编码单元划分时间缩短37.37%，在几乎不影响视频质量的情况下，缩短编码时间，降低编码复杂度，具有良好的实际应用价值。

本文优化算法的实质是在视频压缩质量和编码时间之间做一个均衡，通过反复的对比实验和算法改进，实现在对视频压缩质量影响较小的前提下，加快编码速度，缩短编码时间，最终达到实际应用。本文根据相邻图像帧的相同位置以及同一图像帧中相邻区域的纹理特征的相关性，在CU划分中增加预判过程。预判过程不可能达到每次都能准确的判断，总会存在一定概率的误判，如果在图像纹理复杂区域误判出CU的深度较小，将导致该区域编码失真，影响编码后的画面质量。本文通过采用相邻相关分割算法虽然可以大幅减少误判，但误判无法从根本上消除。因此，本文方法的缺点之一为产生误判导致的编码失真，但在编码总体效果上是可以接受的。此外，本文的优化算法建立在HM10的基础上，在其他HEVC模型中的应用效果需要做进一步验证。

[1] 雷海军,危雄,杨张,等.一种快速HEVC帧内预测模式决策算法[J].计算机工程,2014,40(5):270-273.

[2] Wiegand T,Ohm J R,Sullivan G J,et al.Special Section on the Joint Call for Proposals on High Efficiency Video Coding (HEVC) Standardization[J].IEEE Transactions on Circuits and Systems for Video Technology,2010,20(12):1661-1666.

[3] Bross B,Han W J,Ohm J R,et al.High Efficiency Video Coding (HEVC) text specification draft 10 (for FDIS & Consent)[C]//12th Joint Collaborative Team on Video Coding Meeting,Geneva,Switzerland,2013:179-201.

[4] McCann K,Bross B,Han W J,et al.High Efficiency Video Coding (HEVC) Test Model 10 (HM 10) encoder description[C]//12th Joint Collaborative Team on Video Coding Meeting,Geneva,Switzerland,2013:195-234.

[5] Cassa M B,Naccari M,Pereira F.Fast rate distortion optimization for the emerging HEVC standard[C]//Proceedings of 2012 Picture Coding Symposium. Piscataway,NJ,USA:IEEE,2012:493-496.

[6] Kim J,Choe Y,Kim Y G.Fast coding unit size decision algorithm for intra coding in HEVC[C]//2013 IEEE International Conference on Consumer Electronics (ICCE),Las Vegas,NV,USA,2013:637-638.

[7] Cho S,Kim M.Fast CU splitting and pruning for suboptimal CU partitioning in HEVC intra coding[J].IEEE Transactions on Circuits and Systems for Video Technology,2013,23(9):1555-1564.

[8] Tan H L,Liu F,Tan Y H,et al.On fast coding tree block and mode decision for High-Efficiency Video Coding (HEVC)[C]//2012 IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP),Kyoto,Japan,2012:825-828.

[9] 齐美彬,陈秀丽,杨艳芳,等.高效率视频编码帧内预测编码单元划分快速算法[J].电子与信息学报,2014,36(7):1699-1705.

[10] Shen L,Zhang Z,An P.Fast CU size decision and mode decision algorithm for HEVC intra coding[J].IEEE Transactions on Consumer Electronics,2013,59(1):207-213.

[11] 李维,张和仙,杨付正.高效率视频编码快速模式判决算法[J].西安交通大学学报,2013,47(8):104-109,140.

[12] 赵亮.HEVC帧内模式决策及其核心技术的研究[D].哈尔滨:哈尔滨工业大学,2011.

[13] 蒋刚毅,杨小祥,彭宗举,等.高效视频编码的快速编码单元深度遍历选择和早期编码单元裁剪[J].光学精密工程,2014,22(5):1322-1330.

[14] 李元,何小海,钟国韵,等.一种基于时域相关性的高性能视频编码快速帧间预测单元模式判决算法[J].电子与信息学报,2013,35(10):2365-2370.

FAST PARTITION ALGORITHM FOR HEVC CODING UNIT BASED ON DEPTH PREDICTION

Zhao Hong Jiang Yuchen Li Jingbo

(SchoolofComputerandCommunication,LanzhouUniversityofTechnology,Lanzhou730050,Gansu,China)

A rate-distortion optimization method with high computational complexity is used for CU (coding unit) mode decision in HEVC (High Efficiency Video Coding), which has high time complexity and needs a long encoding time. In order to decrease the coding complexity of HVEC and accelerate the coding speed, a CU fast partition algorithm based on depth prediction is proposed. First, according to the depth correlation between the current CU and the surrounding CU and the current position CU in the reference frame, the optimal depth of the current CU is predicted. Then, the adjacent splitting method or partition decisions based on the relationship between the current depth and the predict depth of the current CU are used to split recursively the current CU. In order to reduce the misjudgment caused by the prediction, in the CU depth level by the two to three levels of division, we use rate distortion or percentage of the way to determine again. Experimental results show that compared with the original HEVC coding method, the algorithm reduced the coding time by 37.7% when the peak signal-to-noise ratio is reduced by 0.07 dB and the coding bit rate is increased by 0.88%, which has high time efficiency.

High efficiency video coding (HEVC) Depth prediction Fast partition Coding unit (CU)

2016-01-14。国家自然科学基金项目(61262016)；甘肃省高校基本科研基金项目(14-0220)；甘肃省自然科学基金项目(1208RJZA239)。赵宏，教授，主研领域：网格计算，视频，智能信息处理，嵌入式。蒋雨晨，硕士生。李靖波，硕士生。

TP3

A

10.3969/j.issn.1000-386x.2017.05.040