[科普中国]-编码单元

简介

高效率视讯编码利用编码单元指出这个单元是利用画面内预测(IntraPrediction)或是画面间预测(InterPrediction)。这些编码单元可以很方便地利用四分树(Quadtree)的方式呈现，四分树是一种递回结构，四分数上的数字表示这个节点是否继续做分割，若此节点会继续分割则为1，若不继续分割则为0。节点上的数字为0时，此节点为编码单元。换句话说，在编码树内叶子节点(LeafNode)为编码单元。在编码单元上采用Z-scan的方式，对编码树来说即为深度优先遍历。编码单元的大小支援2Nx2N，其中N=4、8、16或32，因此高效率视讯编码(HEVC)的四分树最高深度(Depth)为4。

深度遍历选择和早期编码单元裁剪为了降低新一代高效视频编码 （High Efficiency Video Coding，HEVC）标准的编码复杂度，提出了一种基于四叉树结构类型分析和早期编码单元（Coding Unit，CU）裁剪的 HEVC快速编码新算法。首先，通过分析已编码的最大编码单元（Largest CU，LCU）四叉树结构类型，确定其深度遍历区间 （Depth Range，DR）类 型。然后，利用相邻已编码 的LCU以及前向参考帧和后向参考帧中坐标位置相同的 LCU的 DR类型来预测当前 LCU的 DR类型，并根据预测得到的 DR类型对当前 LCU设定 CU深度遍历区间。最后，采用贝叶斯决策原理获取阈值，并利用该阈值在 CU分割过程进行早期 CU裁剪。1

编码复杂度分析HEVC采用率失真优化方式决定 LCU最 终四叉树结构的分割形式，这样，可以在保证视频质量的前提下获得最小的码率。其率失真代价函数J（CUd）为：

J（CUd）=SSEd+λ×Bd，

其中：d表示当前 CU的深度值，Bd 代表当前 CU经过各种 PU预测和模式选择后编码所需的比特数，λ为拉格朗 日算子，SSEd（Sum of Square Error，SSE）表示原始图像块和重建图像块之间的误差平方和。1

深度遍历选择和早期裁剪新算法在充分考虑到 HEVC的四叉树编码结构和视频的时空域相关性的基础上，首先通过对四叉树结构类型进行分析，确定其深度遍历区间 （Depth Range，DR）类型，利用参考帧相同位置的 LCU和相邻LCU的 DR类型来预测当前 LCU的 CU深度遍历区间；然后，再根据预测的深度区间进行编码。同时，采用贝叶斯决策训练原理获取阈值，并利用该阈值对 CU分割进行早期 CU裁剪。1

1、DR类型的确定：

HEVC采用四叉树结构进行编码，一 个LCU最终的分割类型是通过其 CU深度值确定的，大小为64×64的 LCU包 括 256个 4×4块，每 个 4×4块都用 一 个深度值 depth（depth∈[0，3]）表示。不同四叉树结构的 LCU，其 CU深度值的分布情况也不同，LCU的四叉树结构类型可以分为 8种（即 A，B，C，D，E，F，G，H）。若能在 LCU四叉树结构划分前对其类型进行预测，通过该类型设定 CU深度遍历范围，就可以减少不必要的 CU深度遍历，从而降低其编码复杂度。但过于精细的预测遍历区间会很容易造成误判。因此，将深度值分布相近的四叉树结构类型进行合并，并定义 T1、T2、T3 和 T4 种 DR类型。例如，T2包括 C和 D2种四叉树结构类型，其中：C的 深度值为1和2，D的深度值则全为 2，故 将这 2种四叉树结构 的 DR类型定为T2。算法根据DR类型进行 CU深度遍历，相比原始 0～3的 全遍历，明显减少了编码复杂度。1

2、利用时空相关性的中值 DR类型预测：

在视频序列中，当前编码 LCU与相邻已编码的 LCU以及前一帧和后一帧中与当前编码LCU位置相同的 LCU（以下简称为对应 LCU）之间有很大的相关性。 LeftLCU、Top LCU、Left－top LCU、Col1LCU和Col2LCU共5个参选预测 LCU的 DR类型来预测当前编码 LCU的 DR类型。

3、基于贝叶斯决策的早期 CU裁剪预判：

在 LCU的块划分过程中，若当前 CU（depth∈[1，2]）为其上一层 CU的第4个分割 CU，则在计算完其率失真代价J后 ，就有可能通过预判断提前进行早期 CU裁剪过程 。

采用贝叶斯决策原理在帧内模式选择过程中训练基于 SATD（Hadamard trans－formed SAD）的率失真代价最佳阈值。1

帧内预测编码单元划分快速算法高效率视频编码(HEVC)采用基于编码单元(CU)的四叉树块分区结构，能灵活地适应各种图像的纹理特征，显著提高编码效率，但编码复杂度大大增加，提出一种缩小深度范围且提前终止CU 划分的快速 CU 划分算法。基于Sobel 边缘检测算子计算一帧中各深度边缘点阈值，缩小后面若干帧中CU 遍历的深度范围；同时，统计该帧中各 CU 划分为各深度的率失真(RD)代价，计算各深度的 RD 代价阈值。然后，在后续视频帧中，利用RD 代价阈值在缩小的深度范围内提前终止CU 划分。为了符合视频内容的变化特性，统计参数是周期性更新的。经测试，在平均比特率增加仅1。2%时，算法时间平均减少约59%，有效提高了编码效率。2

基于代价的划分提前终止HM 的 CU 划分过程，是在4个深度级范围内逐级比较 RD 代价，并选择 RD 代价最小的划分作为最佳划分。由 LCU 边缘点确定的2个或3个深度级范围内进行 CU 划分。为进一步加快 CU 划分速度，采用基于 RD 代价的 CU 划分提前终止策略。2

一般情况下，若 CU 当前深度的 RD 代价越小，则说明当前划分方式的效果越好，该 CU 继续划分的可能性越小。也就是说，若 CU 当前深度 RD 代价小于某个阈值，就无需继续划分，这就是“CU 划分提前终止策略”。

在学习帧中，除了得到边缘点数目与深度级范围的对应关系外，还利用 HM 得到各 LCU 的划分深度及对应的 RD 代价，并计算每个深度级所对应的 RD 代价的均值及标准差，再计算用于提前终止的 RD 代价阈值。在此后的应用帧中，从最小深度级开始计算当前深度级的 RD 代价，若当前深度级 CU 的 RD 代价小于对应深度级的 RD代价阈值，则该 CU 不继续划分，提前终止，否则继续按深度增加逐级比较。这样，就大大减小了RD代价的计算量。2

快速划分算法流程对于整个算法流程，首先是学习帧基于梯度获得一帧图像中各深度的边缘点阈值，在统计边缘点的同时也统计一帧中各LCU最终划分时各子CU的RD 代价，并对统计得到的各个深度级 RD 代价求均值和标准差，获得用于判断的 RD 代价阈值。然后在应用帧中，先依据边缘点阈值获得当前 LCU 需遍历的深度范围，再在该深度范围内，比较当前深度 CU 的 RD 代价和 RD 代价阈值的大小，若小于RD 代价阈值则 CU 提前终止。具体步骤为：

(1)首先是学习帧，对每个 LCU 依据 Sobel 边缘检测算子计算各像素点的梯度值，获得梯度图后，将梯度图按 LCU 扫描顺序划分为4块；

(2)利用 otsu 算法计算每块的分割阈值Gfouri，i = 0，1，…，3 (取计算得到值的0。75)，并依据该阈值判断该块内各 LCU 的边缘点数；2

(3)依据 HM 中该帧图像各 LCU 最终划分深度将 LCU 的边缘点数分组(深度 0 和1 并为一组)，分别计算各深度边缘点数的均值和标准差，剔除边缘点数目落在标准差之外的 CU，重新计算，将再次计算的均值和标准差之和作为对应深度级的阈值Th_Edgej ， j = 1，2 ；

(4)在统计各 LCU 梯度的同时，统计该帧中各CU 最终划分时的 RD 代价，并计算各深度级的 RD代价均值和标准差，获得 RD 代价阈值，阈值计算公式为式(4) ；

(5)学习帧结束后，进入应用帧，根据步骤(3)中得到的阈值判断当前 LCU 的边缘点数属于哪个划分深度，获得遍历的深度范围，然后将递归过程中当前深度 CU 的 RD 代价RDk 与对应深度的阈值Th_RDk ，k = 0，1，…，3 进行比较，若小于阈值，则终止当前 CU 划分，CU 最终划分深度为k 。否则，深度加1，继续比较下一深度的 RD 代价和相应阈值，直至最大深度。然后进入下一个 LCU 的比较，再次执行步骤(5)。若执行到学习帧，则返回到步骤(1)。2