【论文解读】高性能视频编码帧间预测的单元划分优化算法

时间：2016
机构：西北工业大学
摘要：HEVC 提高了视频编码的性能，也大大增加了整个编码过程，尤其是预测编码阶段的计算复杂度。该文提出一种应用于高性能视频编码帧间预测的快速单元划分算法。该算法基于HEVC灵活的四叉树结构，根据被编码单元的运动特性来确定所编码信息的阈值，并以此作为单元划分的提前终止条件，从而减少了不必要的单元划分操作和率失真代价的相关计算，达到节省编码时间和降低编码复杂度的目的。实验结果表明，在峰值信噪(PSNR)损失仅为0.0418 dB的情况下，所提算法可以平均降低 46.1% 的编码时间。

引言：如何进一步提高编码效率和降低编码复杂度仍然是该领域内极具挑战性的热点问题。本文首先根据被编码单元的运动特性将编码单元所在的区域分类，从而将编码运动信息所需要的比特数作为判断是否进行下一步划分的阈值初值，再根据其对应率失真代价的变化计算阈值补偿， 并进行自适应调整，从而达到节省编码时间，降低编码复杂度的目的。

HEVC中的划分

HEVC将编码帧分成若干编码树块CTB (Coding Tree Block)，CTB是进行预测、变换、量 化、熵编码等一系列处理的基本单元。相同位置的 一个亮度CTB和两个色度CTB，以及它们的语法 元素组成了编码树单元CTU(Coding Tree Unit)。

HEVC 仍然采用的是分块编码方式，但是块的尺寸和划分方式可以自适应的变化，包括三类变化，编码单元 CU、预测单元 PU、变换单元 TU。

编码单元CU：灵活的四叉树结构划分，如下图某一帧某一个 CTU，实线是 CU划分，虚线是 PU划分。

预测单元PU：一个 CU按照所计算的最佳率失真代价被划分为 1 个、2 个或4 个 PU，可以是对称的，也可以是非对称的；如下图一共有 8 中 PU 划分方式。

率失真优化： 基于Shannon的率失真编码理论，视频压缩算法的效率是由编码产生的比特和压缩产生的失真共同来衡量的，通过在两者之间的折中，达到在一定视频质量的条件下使用尽可能少的编码比特，或者在一定码率要求下尽可能降低视频失真的目的。

标准的划分流程：
● 计算深度 i 的 CU被划分前的 cost，记作 cost_unsplit
● 分别计算被划分为 i+1 深度后 4 个子 CU 的cost，然后对其求和，记作 cost_split，假设 i+1 不是最大深度，还要逐层递归达到最大深度
● 比较cost_unsplit和cost_split，如果 cost_split < cost_unsplit,继续划分，否则不需要划分 CU
● 按照 Z 扫描所有CU，执行以上步骤，一个 64x64 的 LCU 需要计算和比较 85 个不同大小的 CU

CU的快速划分算法

快速划分算法的思想：下图是不同 QP 下最优划分的分布情况，大量最终划分深度 0、1、2的 CU 或 PU 仍然会进行深度为 3 的计算和比较工作；且随着 QP 的增大，最优划分为最小深度的还会变得更小。

CU 划分的自适应阈值：通过对视频序列分析得出，编码比特数主要集中在 100以下的范围内，而且在运动较平缓的区域内，编码比特数较小，CU 不再进行下一步的划分概率较大。

因此，可以设定某种阈值，当编码运动信息所需要的比特数小于该阈值时，则可以跳过划分。因此提出自适应编码比特阈值划分判定模型。

设增量cost表示一个CU以某个比特值作为划分阈值后与最优划分模式相比所增加的cost ，则其与比特之间的关系可以表示为

简化上式

考虑 Bits = 0 时，Dcost = 0，则 a = 0

快速划分算法的流程：如下图

实验结果

实验值：比特数可以作为是否进行划分的初始阈值α = 30，自适应改变阈值 β = 0.4，阈值每变化 1 比特，对应 cost 增量γ = 12，则根据 cost 的变化自适应调节编码比特阈值：

源码版本：HM-13.0

在峰值信噪(PSNR)损失仅为0.0418 dB的情况下，所提算法可以平均降低 46.1% 的编码时间。

备注

解读论文，其原理逻辑稍缺严谨，实用价值待考究，仅参考。