基于图像空间相关性与纹理的HEVC块划分快速算法

姚英彪，李晓娟

（杭州电子科技大学通信工程学院 杭州 310018）

1 引言

随着视频技术的发展，以H.264/AVC为代表的第二代视频编码标准已不能满足人们对于实际应用的要求。在这一形势下，VCEG和MPEG两大标准组织成立JCT-VC（joint collaborative team on video coding）[1]，在全球范围内征集新的视频编码技术提案，统一制定新一代高效率视频编码（high efficiency video coding，HEVC）标准。HEVC的核心目标是在H.264/AVC高档次（high profile，HP）的基础上压缩效率提高1倍，即在保证相同视频图像质量的前提下，视频流的码率减少50%[2]。

HEVC沿用H.264/AVC的混合编码框架，但在帧内编码方面，采用新的多角度帧内预测技术和基于大尺寸四叉树块的分割结构，预测模式由H.264/AVC的9种增加为35种，包括33种方向模式和DC（direct current）模式、planar模式；使用编码树单元（coding tree unit，CTU）、编码单元（coding unit，CU）、预测单元（prediction unit，PU）和变换单元（transform unit，TU）描述整个编码过程[2]。大量的预测模式提高了预测精度，灵活的块结构能更好地适应编码图像的内容。

对于每帧图像，可以将其划分为多个CTU，每个CTU又可以划分为1个或多个CU。CU是帧内、帧间预测编码的基本单元，最大的CU即最大编码单元尺寸为64×64，最小编码单元尺寸为8×8。CTU划分深度depth范围及CU深度范围固定为0～3，深度0、1、2、3对应的编码块大小分别为64×64、32×32、16×16、8×8。CU概念便于编码块的递归划分及四叉树编码结构的形成，具体编码单元的划分如图1所示。PU是预测编码的基本单元，用来传输与预测过程相关的信息，在CU的基础上划分而来。PU最多有12种不同模式，对于帧内预测而言，只有2N×2N和N×N两种模式，若当前CU不是最小编码单元，PU采用2N×2N模式的预测单元，即PU尺寸同当前CU尺寸，当CU尺寸为8×8即CU为最小编码单元时，PU需要检测2N×2N和N×N两种模式，最终选择率失真代价最小的模式。TU是变换和量化的基本单元，与PU相同，也是在CU的基础上划分而来，TU结构与CU结构类似，采用了残差四叉树（residual QuadTree，RQT）编码结构。

在帧内编码过程中，需要遍历所有的CU、PU、TU的组合以及35种预测模式，经过率失真优化 （rate distortion optimization，RDO）过程选择率失真代价最小的单元和预测模式进行最终编码。率失真代价函数如下：

图1 CU、PU块划分

其中，JRDO表示率失真代价，SSE表示当前块与重建块的残差平方和，λ表示拉格朗日系数，B表示当前预测模式下编码所需的比特数。

由于率失真代价的计算需要进行完整的编码，过程复杂，而大量的预测模式和复杂的块结构大大增加了进行率失真运算的次数，这就造成帧内编码算法的运算复杂度和编码时间增加，从而极大地限制了HEVC的应用范围。因此，在保证编码性能的前提下，如何降低HEVC帧内编码算法的复杂度是当前HEVC实际应用的研究热点之一。

2 HEVC帧内编码优化算法

[3]提出经过粗选（rough mode decision，RMD）过程，利用简化的率失真模型筛选出部分预测模式，再进行最后的RDO计算。参考文献[4]利用空间相关性，提出最有可能预测模式（most possible mode，MPM）的概念，即邻近块的最佳预测模式，将RMD筛选后得到的模式与MPM一并作为最后的RDO候选模式。参考文献[5～9]利用图像的纹理特征筛选出部分模式进行RMD和RDO计算。以上方法都是针对给定大小的PU，从减少所要遍历的帧内预测模式出发，实现帧内快速编码，减少算法复杂度。

参考文献[10～12]针对视频内容的时间或者空间相关性，利用已编码的上一帧对应位置的CU或者空间邻近CU块的划分深度预测当前块的划分深度，跳过当前块的编码计算或者提前终止其子块划分。参考文献[10]利用图像内容的相关性，在对当前CU块进行划分时，跳过空间相邻CU较少使用的深度。参考文献[11]利用时空相邻的CTU/CU之间的相关性，通过已编码时空相邻CTU/CU的最佳深度预测当前CTU/CU的深度范围和深度值，跳过和提前终止不必要的块划分计算。参考文献[12]利用视频帧的时间相关性，通过前一帧的划分深度预测当前帧对应位置处CTU的最小划分深度，并计算当前CU的运动矢量差值和预测残差系数，得到其最大划分深度，从而跳过部分大块CU的块划分和避免小块CU的块划分。

参考文献[13～17]利用每个深度CU编码过程中计算得到的率失真代价、预测残差、像素值的方差、熵等信息提前终止或跳过划分块。参考文献[13]分析了率失真代价与块划分的关系，在划分过程中将每个CU块的率失真代价与之前设定的阈值进行比较，判断是否提前终止该CU块的子块划分。参考文献[14]利用CU块不同划分深度与RMD和RDO过程中计算得到的基于SATD的代价值和RDO代价值，跳过大块编码计算和提前终止子块划分。参考文献[15]利用预测残差能够反映预测准确性的思想，在每一个编码块进行编码时，判断其预测残差是否足够小，若小于事先设定的阈值，则提前终止其子块划分。参考文献[16]利用视频内容的平滑区域与最终编码块大小的相应关系，根据当前已编码单元的编码信息对当前区域是否平滑进行检测，根据检测结果提前终止一些不必要的子块划分。参考文献[17]利用视频序列第一帧像素值的方差，分析视频纹理特性并减少部分块划分过程。

本文利用视频内容的空间相关性及编码块大小与其纹理的关联，提出一种基于图像空间相关性与纹理的HEVC块划分快速算法。首先，通过分析不同视频序列相邻CTU之间的划分深度范围的相关性，提出CTU最有可能深度范围（most possible depth range，MPDR）的概念及计算方法。其次，通过检测相邻CTU之间的主要边缘方向来分析邻近CTU间的纹理差异性，并根据该纹理差异判决当前待编码CTU的划分深度范围是采用MPDR，还是采用HM原有算法中的0～3。最后，通过统计不同序列、不同尺寸块的块划分与像素方差的概率密度，得到纹理复杂的阈值计算式；在每个CU编码之前，计算并比较像素方差与阈值，检测该CU的纹理复杂程度，判断是否可以跳过该块的编码计算而直接划分。与HM13.0相比，本文算法能够保证在编码性能几乎不变的情况下，将编码时间减少20%以上。

3 CTU最有可能深度范围

3.1 CTU深度范围与视频内容的相关性

在HEVC帧内编码过程中，每帧图像都将被划分为多个CTU，在对CTU块划分寻找最佳CU块尺寸的过程中，HEVC标准算法将CTU的深度范围固定为0～3，递归遍历所有CU块尺寸类型，并进行相关的PU、TU划分和预测模式的选择，最终得到率失真代价最小的块划分类型。但由于不同序列、不同CTU块之间存在纹理复杂度的差别，CTU深度范围可能小于标准规定的0～3。

为分析不同内容特性的视频序列的CTU划分深度范围，选取5个不同类别、不同分辨率和不同纹理的视频序列在不同量化参数（QP=22、27、32、37）下，统计所有CTU最小划分深度分别为0、1、2、3的平均比重和最大划分深度分别为0、1、2、3的平均比重，分别见表1和表2。表1中pmindepth0、pmindepth1、pmindepth2、pmindepth3分别表示最小划分深度为0、1、2、3所占平均比重， 表2中pmaxdepth0、pmaxdepth1、pmaxdepth2、pmaxdepth3分别表示最大划分深度为0、1、2、3所占平均比重。

从表1和表2可以看出，并非所有序列CTU的最小划分深度都为0，最大划分深度都为3。对于纹理复杂的序列（如序列BQSquare），应该进行较细致的划分，块尺寸较小；最小划分深度为0的概率非常小，若采用原有的划分深度范围0～3，则有不必要的深度块（深度0）的编码。对于平坦序列（如序列Kimono1），块尺寸较大；最大划分深度为3的比重较小，若采用原有的划分深度范围0～3，则有不必要的深度块（深度3）的编码。因此，可以根据CTU之间的空间相关性缩小CTU块划分时的深度范围，并且每个CTU内部由于纹理的不同，可以针对不同的纹理选择不同的块大小，从而避免不必要的块划分带来的复杂计算（包括RDO计算）。

3.2 CTU划分深度的相关性分析及其MPDR

由于每帧图像存在内容的相关性，空间相邻CTU的划分深度之间也存在着相关性，下面的统计数据也证明了这一点。各邻近CTU分别为上方CTU、左方CTU、左上方CTU和右上方CTU，如图2所示。当前CTU的最小和最大划分深度与各邻近已编码CTU的最小和最大划分深度分别为mindepth、maxdepth、mindepth_a、maxdepth_a、mindepth_l、maxdepth_l、mindepth_al、maxdepth_al、mindepth_ar、maxdepth_ar。

图2 邻近已编码CTU与当前CTU

定义4个邻近已编码CTU的最小划分深度中的最小值为mp_mindepth，4个邻近已编码CTU的最大划分深度中的最大值为mp_maxdepth，如下：

定义当前CTU的MPDR为：

即用4个邻近已编码CTU的最小划分深度中的最小值mp_mindepth和4个邻近已编码CTU的最大划分深度中的最大值mp_maxdepth估计当前CTU的MPDR。如果当前CTU经过HM原有算法编码后的最佳划分深度均在[mp_mindepth,mp_maxdepth]，说 明MPDR可 以 作 为 当 前CTU划分深度范围。

表1 最小划分深度分别为0、1、2、3所占平均比重

表2 最大划分深度分别为0、1、2、3所占平均比重

表3分别统计了当前CTU的最小划分深度大于或等于任意一个邻近CTU最小划分深度即mp_mindepth的概率和最大划分深度小于或等于任意一个邻近CTU的最大划分深度即mp_maxdepth的概率。表3中较大的概率值说明当前CTU的最小、最大划分深度与利用各个邻近CTU的最小、最大划分深度得到的mp_mindepth、mp_maxdepth及MPDR具有较强的相关性。区间[mp_mindepth，mp_maxdepth]可以作为当前CTU的MPDR。

表3 当前CTU在不同QP下划分深度范围与邻近CTU划分深度范围的比较

4 基于内容相关性及图像纹理的块划分快速算法

以上CTU划分深度相关性分析，验证了可以根据邻近已编码CTU的划分范围得到当前待编码CTU的合适的划分范围（即MPDR），该范围根据空间相关性适当缩小了原来固定的划分范围，避免了不必要的块划分所引起的复杂计算。考虑到图像纹理的区域性分布特征，即邻近CTU的纹理可能存在明显的差异，此种情况下，利用邻近CTU的划分范围估计当前CTU的最有可能划分范围的方法极容易造成误判。而如果当前CTU的划分范围估计错误（如划分范围被缩小），就会影响之后的CTU划分范围的估计，从而造成错误累加，最终使编码性能大大下降。因此，需要在将MPDR作为当前CTU的划分范围之前，对当前CTU的纹理与邻近CTU纹理的差异性进行分析，如果当前CTU的纹理与该纹理方向上的邻近CTU的纹理相差较大（如垂直），则采用标准算法的深度范围0～3进行预测，否则利用空间相关性根据式（2）～式（4）得到当前CTU的MPDR。

4.1 空间邻近CTU的纹理差异性检测

为了判别邻近CTU间的纹理差异性，采用参考文献[18]中的边缘检测方法，对当前CTU和邻近CTU进行主要边缘检测（dominant edge detection），判别各自的主要边缘（dominant edge，DE）隶属于0°、45°、90°、135°的哪一种方向，CTU的主要边缘方向如图3所示。如果当前CTU的主要边缘方向DEc垂直于该方向上邻近CTU的主要边缘DE′，则认为当前CTU与邻近CTU的纹理差异较大，不宜采用MPDR作为当前CTU的划分深度范围，否则可以将MPDR作为当前CTU的划分深度范围。

图3 CTU的主要边缘方向

图4 将CTU划分为5个子块

为了得到当前CTU和邻近CTU的主要边缘方向，将N×N（N=64）大小的CTU块按照如图4所示方式划分为a、b、c、d、e共5个子块，并分别计算5个子块的像素平均值Pa、Pb、Pc、Pd、Pe。定义不同方向上像素差的绝对值之和为主要边缘方向一致性（dominant edge assent，DEA），利用式（5）分别计算0°、45°、90°、135°这4个主要边缘方向一致性DEA1、DEA2、DEA3、DEA4，并取其中最小值所对应的方向作为该CTU的主要边缘方向DE，DE表示0°、45°、90°、135°中的一种。

对当前CTU和邻近各个CTU（上方CTU、左方CTU、左上方CTU、右上方CTU）分别进行如式（5）所示的计算，得到各个CTU的主要边缘方向，当前CTU的主要边缘方向用DEc表示，各个邻近CTU的主要边缘方向分别表示为DEa、DEl、DEal、DEar。如前所述，如果当前CTU的主要边缘方向DEc垂直于该边缘方向上的CTU的主要边缘DE′，即满足式（6），则认为当前CTU与邻近CTU的纹理差异较大。

由图3可以看出，0°与90°垂直，45°与135°垂直，若当前CTU的边缘方向DEc满足式（7）～式（10）中的其中一个，则认为DEc⊥DE′，即当前CTU与邻近CTU的纹理差异较大，不宜采用MPDR作为当前CTU的划分深度范围。

4.2 编码单元CU的纹理复杂度检测

如前所述，如果编码块较平滑，则该编码块适合大尺寸编码单元进行预测；如果编码块纹理较复杂，宜选用小尺寸编码单元进行预测，而实验进一步证明[17,19]，纹理复杂的编码块的像素值方差较大，平滑块的像素值方差较小。因此，在块划分过程中，可以通过计算比较像素值方差的大小判断编码块的纹理复杂程度，进而判断当前深度的编码块大小是否适合该纹理的块，若不适合则不进行该深度块的编码计算，从而大大减少编码复杂度和编码时间。像素方差v计算如下：

其中，v表示N×N大小的块的像素方差，pij表示N×N块位置（i，j）处的像素值，u表示该块的所有像素均值。

图5给出了序列Kimono1和Vidyo1不同尺寸的CU块的像素方差概率密度分布。从图5可以看出，对于所有的块尺寸，当方差达到一定值以后，随着方差的增大，出现的概率随之减小，最终概率急速下降趋近于0。这就表明，如果一个CU块的像素方差大于某一个值（如某一个阈值），说明该块内纹理复杂，这种情况下的尺寸几乎不可能是最佳的块尺寸，需要进一步划分。在CU子块划分过程中，在CU块进行编码计算（RDO计算）之前，需首先进行纹理复杂度判断，即判断CU块的像素方差是否大于某一个阈值Thv，如果大于，则说明该CU需要进一步分割以减少方差，对于当前深度块无需进行编码计算而直接进行下一深度的划分运算；否则，在估计的深度范围内进行正常的块划分过程。

从图5可以看出，块尺寸越大，概率急剧下降所对应的方差越大，阈值Thv应该与块尺寸有关，且块尺寸越大即深度越小，阈值应该设定得越大。考虑到不同量化参数QP块划分的不同，该阈值也应该与QP值有关，QP越大，阈值越大。通过实验统计不同序列不同尺寸块的像素方差值的分布，得到阈值Thv：

其中，α、β、γ为参数，实验得到其值分别为45、93、3，depth为当前块的编码深度，可以取0、1、2、3，分别对应64×64、32×32、16×16、8×8块大小，QP为量化参数。

如果计算出的v大于Thv，即满足式（13），则认为该尺寸的编码块纹理复杂，需要进一步划分，无需对该深度的CU进行编码运算。

4.3 编码块快速划分算法总体流

基于以上分析，提出一种基于图像纹理复杂度及空间相关性的块划分快速算法。该算法对某一个CTU进行编码之前，首先对该CTU的划分范围进行估计，即对当前CTU与邻近CTU的纹理差异性进行分析，若差异不明显，则利用邻近CTU的划分深度范围估计得到当前CTU的MPDR并进行接下来的编码计算；若差异明显，则采用原有算法的深度范围0～3进行编码计算。其次在对每一个CU编码之前，利用式（11）和式（12）计算其像素方差与阈值，并将两者进行比较，判断该尺寸块的纹理是否非常复杂、是否可以直接进行子块划分。划分深度估计算法流程如图6所示，块划分快速算法的总体流程如图7所示。

图5 部分序列的各个尺寸编码块的像素方差的概率密度分布

5 实验结果与分析

为了验证本文算法的正确性，将该算法加载在HEVC的官方测试模型HM13.0[20]上，对不同类型的视频测试序列实现全I帧配置，在不同量化参数QP（QP=22,27,32,37）下进行测试。

测试中，通过码率BitRate、峰值信噪比PSNR、编码时间T的变化情况分析算法的性能。编码性能由BD-Rate和BD-PSNR[21]来度量，编码时间的增减百分比ΔT用来度量编码复杂度的减少情况，计算如下：

表4给出了本文算法及参考文献[10]算法与HM原有算法在编码效率和计算复杂度方面的比较结果，正数表示增加，负数表示减少。可以看出，本文算法较HM原有算法平均节约20%以上的编码时间，而比特率平均仅增加0.84%，PSNR平均下降仅0.04 dB，编码性能下降微乎其微。特别地，对于序列Kimono1和BQSquare，编码时间减少得最多，可以节约30%以上，同时性能下降也很小。与参考文献[10]相比，本文算法能够在降低相近的编码时间的同时，保证编码性能下降得也很小，因此本文算法优于参考文献[10]算法。以上数据及分析说明了本文算法能够保证在编码性能下降很小的情况下，减少编码时间，降低编码复杂度。

图6 CTU划分深度范围估计算法流程

图7 块划分快速算法总体流程

表4 本文算法及参考文献[10]算法与HM13.0的性能比较

6 结束语

本文基于空间相关性及纹理复杂度提出了一种HEVC块划分快速算法，该算法应用于CTU块划分过程中。在CTU进行划分前，通过边缘检测方法分析当前待编码CTU与邻近已编码CTU的纹理差异，若差异明显，则采用原有划分范围0～3进行编码计算；若差异不明显，则利用邻近CTU的划分范围估计得到当前待编码CTU的MPDR，并利用MPDR进行编码计算。在CU划分过程中，在每个CU编码之前，通过比较像素方差与阈值来分析该CU的纹理复杂程度，并判断是否可以跳过该深度块的编码计算而直接划分。仿真结果表明，与HM13.0原有算法相比，本文算法能够保证在编码性能几乎不变的情况下，将编码时间减少20%以上。

参考文献

1 ISO/IEC JTC1/SC29/WG11/N11113.ITU-T Q6/16 Visual Coding and ISO/IEC JTC1/SC29/WG11 Coding of Moving Pictures and Audio.Joint Call for Proposals on Video Compression Technology,2010

2 Sullivan G J,Ohm J,Han W J,et al.Overview of the high efficiency video coding(HEVC)standard.IEEE Transactions on Circuits and Systems for Video Technology,2012,22(12):1649～1668

3 Piao Y,Min J,Chen J.Encoder Improvement of Unified Intra Prediction.JCTVC-C207,2010

4 Zhao L,Zhang L,Ma S,et al.Fast mode decision algorithm for intra prediction in HEVC.Proceedings of IEEE Visual Communications and Image Processing(VCIP),Taiwan,China,2011:1～4

5 Jiang W,Ma H,Chen Y.Gradient based fast mode decision algorithm for intra prediction in HEVC.Proceedings of the 2nd International Conference on Consumer Electronics,Communications and Networks(CECNet),Three Gorges,China,2012:1836～1840

6 Chen G,Pei Z,Sun L,et al.Fast intra prediction for HEVC based on pixel gradient statistics and mode refinement.Proceedings of IEEE China Summit and International Conference on Signal and Information Processing(ChinaSIP),Beijing,China,2013:514～517

7 Chen G,Liu Z,Ikenaga T,et al.Fast HEVC intra mode decision using matching edge detector and kernel density estimation alike histogram generation.Proceedings of IEEE International Symposium on Circuits and Systems(ISCAS),Beijing,China,2013:53～56

8 Da Silva T L,Agostini L V,Da Silva Cruz L A.Fast HEVC intra prediction mode decision based on EDGE direction information.Proceedings of the 20th European Signal Processing Conference(EUSIPCO),Bucharest,Romania,2012:1214～1218

9 Fang C M,Chang Y T,Chung W H.Fast intra mode decision for HEVC based on direction energy distribution.Proceedings of IEEE 17th International Symposium on Consumer Electronics(ISCE),Taiwan,China,2013:61～62

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

11 晏轲,滕国伟,胡锦雯等.一种基于时空相关性的编码单元深度快速分级判决算法.光电子·激光,2014,25(1):156～162 Yan K,Teng G W,Hu J W,et al.A rapid classification decision algorithm on CU depth based on temporal-spatial correlation.Journal of Optoelectronics·Laser,2014,25(1):156～162

12 李维,张和仙,杨付正.高效率视频编码快速模式判决算法.西安交通大学学报,2013,47(8):104～109 Li W,Zhang H X,Yang F Z.A fast mode decision algorithm for high efficiency video coding.Journal of Xi'an Jiaotong University,2013,47(8):104～109

13 Kim J,Choe Y,Kim Y G.Fast coding unit size decision algorithm for intra coding in HEVC.Proceedings of IEEE International Conference on Consumer Electronics(ICCE),Las Vegas,NV,United States,2013:637～638

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

15 Ma S,Wang S,Wang S,et al.Low complexity rate distortion optimization for HEVC.Proceedings of 2013 Data Compression Conference(DCC),Snowbird,UT,United States,2013:73～82

16 蒋洁,郭宝龙,莫玮等.利用平滑区域检测的HEVC帧内编码快速算法.西安电子科技大学学报,2013(3)Jiang J,Guo B L,Mo W,et al.Fast intra coding algorithm using smooth region detection for HEVC.Journal of Xidian University,2013(3)

17 Khan M U K,Shafique M,Henkel J.An adaptive complexity reduction scheme with fast prediction unit decision for HEVC intra encoding.Proceedings of the 20th IEEE International Conference on Image Processing(ICIP),Melbourne,VIC,Australia,2013:1578～1582

18 Tsai A C,Wang J F,Lin W G,et al.A simple and robust direction detection algorithm for fast H.264 intra prediction.Proceedings of IEEE International Conference on Multimedia and Expo(ICME),Beijing,China,2007:1587～1590

19 Tian G,Goto S.Content adaptive prediction unit size decision algorithm for HEVC intra coding.Proceedings of the 29th Picture Coding Symposium(PCS),Krakow,Poland,2012:405～408

20 McCann K,Bross B,Han W J,et al.JCTVC-O1002 High Efficiency Video Coding(HEVC)Test Model 13(HM 13)Encoder Description.JCT-VC,Tech Rep,2014