许东旭，林其伟――基于二维直方图的HEVC帧内快速深度决策算法.doc

基于二维直方图的 HEVC 帧内快速深度决策算法 许东旭 林其伟 (华侨大学信息科学与工程学院 福建 厦门 361021) 摘要：为了进一步缓解 HEVC 帧内预测巨大的计算复杂度，提出了一种基于二维直方图的快速深度 决策算法。算法首先对当前 LCU 采用 3×3 矩阵进行滤波，然后分别统计原始 LCU 以及滤波后 LCU 的像素分布，生成二维灰度直方图。通过该二维直方图所表征的纹理特征，进行深度的自适应选择， 减少不必要的深度计算。实验结果表明，同原始 HM10.1 相比，本文提出的算法可以节省编码时间 21.6%，同时保证视频质量几乎不变。 关键词：高效率视频编码；深度；二维直方图；快速模式选择；编码单元；灰度直方图 中图分类号：TN919.81 文献标识码：A Fast Depth Decision Algorithm Based on Two-Dimensional Histogram for HEVC Intra Coding Xu Dong-xu Lin Qi-wei Department of Information Science and Engineering, Huaqiao University, Fujian, Xiamen, China，361021 Abstract ： In order to further reduce the great computational complexity for HEVC intra coding, a fast depth decision algorithm has been proposed in this paper. First, a 3×3 matrix is used to filter current LCU. Then, a two-dimensional histogram which is based on the distribution of the gray values of the original LCU and the filtered LCU can be generated. By using the two-dimensional histogram, we can skip some of the depth levels that are unnecessary. Experimental results show that the proposed algorithm can save 21.6% of the encoding time on average with negligible loss of coding efficiency compared with the HM10.1. Key words：HEVC; Depth; Two-dimensional histogram; Fast mode decision; CU; Gray histogram 基金项目：福建省自然科学基金项目（2012J01275） Deleted: we proposed Deleted: we use Deleted: the Deleted: we can create 1.引言 HEVC(High Efficiency Video Coding 高效率视频编码)是继 H.264 之后的又一新的视频编码标准，相 比于 H.264 其引进了大量的创新技术:更多种的编码单元尺寸的选择，以及更多的帧内预测模式的选择。 同时还创新性地引入了三种新型编码单元的概念：CU(Coding Unit 编码单元)，PU（Prediction Unit 预测 单元） ，TU（Transform Unit 变换单元）。引进的这些创新技术使得 HEVC 相比于 H.264 在提供相同视频质 量的同时，可以节省将近 50%的比特率[1]。但与此同时，也引入了巨大的计算复杂度。比如为了得到最优 的 CU，HEVC 需穷尽地递归搜索 CU,PU,TU 的最优组合，同时对于每个 CU 帧内又需要遍历高达 35 种的 预测模式。所以，现阶段很多学者围绕 CU 尺寸的快速选择以及帧内模式的快速决策这 2 个角度，做了大 量的努力。文献[2]利用 5 个滤波模板求得当前 PU 的主要边缘方向，并依据求得的主要边缘方向进一步减 少模式计算的数量。文献[3]，对当前编码块与其周围相邻的编码块的空间相关性做了研究。文献[4]，利 用 Sobel 算子提取当前 CU 的边缘信息，最后按生成的边缘梯度直方图进一步排除冗余的预测模式。文献 [5],利用 DCT 变换后的系数进行边缘检测以此进一步减少模式数量。文献[6]，采用 4 个方向的梯度滤波器 判 断 当 前 CU 的 纹 理 特 征 ， 提 前 决 定 当 前 CU 是 否 进 行 分 割 。 文 献 [7] 利 用 离 线 设 置 的 RDcost （Rate-Distortion cost 率失真代价）阈值提前终止某些 CU 的进一步分割。文献[6-7]的主要思想都是采用 某种策略终止某些块的分割进程，即对分割的子树进行修剪。上述这些算法都在一定程度上减少了 HEVC Deleted: 提前决策 Deleted: 帧内模式数量的缩小 Deleted: 滤波系数 Deleted: 来 Deleted: 当前编码块跟周围已编码块的预测方向以及深 度之间存在的相关 Deleted: 对 Deleted: 只选取几个边缘幅值较强的 Deleted: 进行 RDO(Rate-Distortion Optimization 率失真 优化) Deleted: 计算 的编码复杂度，但 HEVC 仍不利于实时应用，所以有必要进一步研究高效准确的快速算法来优化 HEVC 编码器。从子树修剪的角度来加速 HEVC 的编码器，是个好的方法，但搜索深度仍然固定。本文从提取 当前 LCU(Largest Coding Unit 最大编码单元)内部的纹理特征角度，利用改进的二维直方图法[8]建立二维 直方图与当前 LCU 深度之间的统计关系，提出了一种新的快速深度决策算法。 Deleted: 以 Deleted: 为 Deleted: 7 Deleted: ，并 Deleted: 起 2. HEVC 帧内预测过程 如图 1 所示，HEVC 采用四叉树的递归分割结构。首先，当 CU 不划分时，称为 LCU，其尺寸为 64×64， 深度为 0，接着对该 LCU 进行预测编码，得其 RD（Rate-Distortion 率失真）代价。然后继续对 LCU 进行分 割，此时 CU 尺寸为 32×32，深度为 1，同样对当前 CU 进行预测编码，得其 RD 代价。若当前 CU 尺寸为 8× 8 时，即此时深度为 3 时，便不再进行分割。接着从 8×8 的 CU 尺寸开始，往上进行修剪：首先比较 4 个 8× 8 的 RD 代价是否小于其上一深度对应的 16×16 尺寸 CU 的 RD 代价，如果小于，则选择 8×8 的 CU 尺寸， 否则选择 16×16 尺寸的 CU。如此比较下去，直到深度为 0。最后选出具有最小 RD 代价的 CU 作为最终的分 割模式。 对于帧内 2N×2N 的 CU，其对应的 PU 尺寸只能为 N×N 或 2N×2N。而 N×N 的 PU 在当前 CU 为 8×8 时才被允许使用。 同时，在每个深度级上，HEVC 的帧内预测需在包括 2-34 等 33 种角度预测模式以及 planar 和 DC 模式之 间进行 RDO（Rate Distortion Optimization 率失真优化）计算后，最终选取具有最小 RD 代价的模式作为最优 的预测模式，可见其计算量相当巨大。所以为了缓解对 35 种模式进行 RDO 计算所带来的高额计算复杂度， HEVC 首先进行 RMD（Rough Mode Decision 粗略模式选择）过程[9]：首先利用 Hadamard 变换代替 RDO 计 算，接着从 35 种模式中粗略选出 N 个具有最小的 Hadamard 代价（即对残差进行 Hadamard 变换求得该残差 的变换绝对差值和，同时考虑需要编码的比特数这两者所花费的代价）作为候选模式，并且考虑了当前 CU 来 自左边与上边 CU 的 MPMs（Most Probable Modes 最有可能模式），接着对这可能的 N 到 N+2 个候选模式进 行 RDO 计算，从中选出代价最小的预测模式作为最优的模式，该算法极大地提高了 HEVC 的编码速度。帧内 总的预测算法流程图如图 2 所示。 Depth=0,64×64 split 0 1 2 3 0 1 2 3 0 1 2 3 CU0 Intra PU Depth=1,32×32 CU1 Depth=2,16×16 CU2 Depth=3,8×8 CU3 2N×2N N×N Deleted: 如图 2 所示， Deleted: 的 Deleted: 8 Deleted: 的 Deleted: 。 图 1 HEVC 的四叉树递归分割过程 Deleted: Depth=0,64×64 （开始） 读入一个LCU 此时深度为0 尺寸为64x64的CU split 0 1 2 3 0 1 2 3 0 1 2 3 CU0 Depth=1,32×32 读入一个CU CU1 2N×2N Depth=2,16×16 对35种模式进行 RMD，从中选择出N 种最优的候选模式 CU2 Depth=3,8×8 对由上一步选择出的N 种候选模式同时考虑 MPMs,对这N倒N+2个候 选模式进行RDO计算， 从中选择具有最小 RDcost的模式作为最优 的预测模式 调用递归函数，将 当前CU划分成4个 子CU，深度+1或尺 寸/2 CU3 Deleted: 1 Deleted: CU 递归划分过程 否 Deleted: 深度为3？ 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 18 是 17 否 当前LCU是否全 部完成所有CU 的编码 16 15 14 13 是 图 2 HEVC 的帧内算法流程图 12 11 10 9 8 0:intra planar mode 1:intra DC mode 7 6 3. 基于二维灰度直方图的快速深度决策算法 本文算法之所以考虑二维直方图，是因为普通的一维直方图只是统计了某一个 LCU 的像素组成，不能反 映出该 LCU 所有像素的位置信息及其内部特征。通常一个 LCU 块内部周围的像素相关性是非常强的，所以我 们要充分利用这些相关性。基于上述分析，本文首先根据当前像素与其周围像素相关程度（与当前像素的距离 大小）的高低采用不同的权值进行求和，并通过当前像素与滤波后的像素联立构造二维像素直方图。可见该二 维直方图不仅利用了该像素本身携带的信息，而且还利用了其周围像素的的信息，这在一定程度上可以反映出 5 4 3 2 Deleted: 图 2 HEVC 的 35 种帧内预测模式¶ Deleted: 对 Deleted: 是 当前 LCU 的纹理特征。接着利用该提取的纹理特征选择当前 LCU 最有可能的深度范围，跳过不必要的深度计 算，加快编码速度。 Deleted: 通过提取的 3.1 二维直方图的构造 图像的灰度直方图是统计某一幅图像的灰度级内容，它表达了某一幅图像各个灰度级出现的次数或者概率。 其横轴覆盖的灰度级范围，可以表示出当前图像的色调变化情况，纵轴可以表示当前色调范围内的灰度值数量 或者频率。我们可以从该直方图读出该幅图像的很多信息。比如，如果某一灰度级出现的次数很多，说明组成 该幅图像的灰度值种类较少，该幅图像色调比较单一，纹理可能相对平坦。相反如果组成该幅图像的灰度级很 多种，说明该幅图像的色调变化剧烈，纹理可能很复杂。这启发我们，可以通过统计当前 LCU 的灰度组成， 来判别当前 LCU 是否平坦。因为直观上，一个 LCU 若处于一幅图像的背景区域，那么其纹理应该相对平坦， 对于纹理较为平坦的 LCU 一般不可能分割到太小的尺寸。相反一个 LCU 若处于图像的边缘或细节区域，那么 其纹理应该会相对复杂，此类的 LCU 一般要分割到比较小的尺寸。所以研究一个 LCU 的纹理特征可以帮助我 们提前决策出当前 LCU 需要进行 RDO 计算的深度级，从而跳过不必要的深度计算。本文通过构造二维直方 图来提取当前 LCU 的纹理特征。因为二维直方图不仅利用了本身的像素信息，而且也包含了周围像素的信息， 这在很大程度上是能够表示出当前 CU 的内部纹理特征。而对于纹理比较复杂的编码块，一般会分割到比较小 的尺寸，即比较大的深度，所以对于此类的编码块，我们可以直接跳过大尺寸分割时的编码计算；反之亦然。 下面将详细说明，二维直方图的构造以及验证前面的假设。 为了减少计算量，首先对当前 64×64 尺寸的 LCU 分成 16×16 个 4×4 的子块，接着对每个 4×4 子块的 像素进行求平均，最后对于 64×64 的 LCU，可以得到 16×16=256 个像素值。我们把由这 256 个像素所组成 的 LCU 记为 P。通常来讲，距离当前像素越近的像素与当前像素的相关程度应该越高，所以根据当前像素与 其周围像素相关程度的高低分配不同的权值，同时需要满足权值的累加和为 1，最后我们采用如式（1）所示 的矩阵模板进行滤波，并把滤波后的 LCU 记为 Q。接着取 P 中的任一像素值（记为 X）和 Q 中的任一像素值 （记为 Y），可见 X 与 Y 都属于[0,255]区间内，统计由（X,Y）组成的坐标出现的次数，并把相应坐标出现 的次数记为 Z，可见 Z 属于[0,256]区间内。最后由（X，Y, Z）可以生成当前 LCU 的二维灰度直方图。通过以 上描述，可知该二维灰度直方图不仅考虑了当前像素的信息，还包含了其周围像素的信息。 Deleted: 深度 æ1 2 1ö 1ç ÷ H= ç2 4 2÷ 16 ç ÷ è1 2 1ø （1） 图 3 是 HEVC 中某个典型的属于纹理比较平坦的 LCU 的二维灰度直方图，通过使用 HEVC 的编解码参考 软件 HM 10.1，我们发现该 LCU 经过 RDO 计算后最终以当前深度 0 作为最优的深度。相反，图 4 是 HEVC 中某个典型的纹理复杂的 LCU 的二维灰度直方图，该 LCU 经过 RDO 计算后最终分割到了深度 3。图 3 图 4 有力地证明了我们之前的假设，即 LCU 的二维灰度直方图确实能在一定程度上反映出当前 LCU 需要分割到的 深度级。 图 3 典型的纹理平坦的 LCU 二维灰度直方图 Deleted: 进行深度的自适应选择 Deleted: 即 æ1 2 1ö 1ç ÷ Deleted: H= 2 4 2÷ 16 ç ç1 2 1÷ è ø 图 4 典型的纹理复杂的 LCU 二维灰度直方图 3.2 基于二维直方图的快速深度决策算法 从图 3 与图 4 所表示的两种典型纹理的 LCU 的直方图特征，可以进一步发现，对于像如图 3 所示的这类 平坦的 LCU 的二维直方图的灰度值对应的最大像素个数值是一个较大的值，说明这一类平坦的 LCU 主要仅有 几种灰度组成，很有可能是平坦的。相反，对于如图 4 所示的这一类细节较多的复杂 LCU 其对应的二维直方 图比较分散，其灰度值对应的最大像素个数值较小，说明该类 LCU 由多种灰度级构成，该类 LCU 内部的灰度 变化可能会比较剧烈。根据这样的特点，考虑选取当前 LCU 生成的二维直方图中灰度值对应的最大像素个数 值结合设置的阈值进行判断。 经过以上分析及对大量阈值和不同序列进行测试后，本文基于二维直方图的快速深度决策算法步骤描述如 下： Step 1: 对当前 LCU 分成 16×16 个 4×4 的子块，接着对每个 4×4 子块的像素进行求平均，得到 256 个像素 值。对这 256 个像素采用式(1)所示的模板进行滤波，统计由该原始 LCU 以及滤波后的 LCU 的像素分布，构 造二维灰度直方图。 Step 2:找出该二维灰度直方图最大的像素个数值，记为 max_value。 Step 3：判断 max_value 所属的区间。如果 max_value 小于 10，则当前 LCU 的最小深度级设置为 2；如果 max_vale 大于等于 10 而小于 30，则当前 LCU 的最小深度级设置为 1；如果 max_vale 大于等于 30 而小于 40，则当前 LCU 的最小深度级设置为 1 同时最大深度级设置为 2；如果 max_vale 大于等于 40 而小于 50，则当前 LCU 的最大 深度级设置为 2；如果 max_value 大于等于 50，则当前 LCU 的最小与最大深度级同时设置为 0。 经过上述分析，可知本文算法是采用 4 个阈值：10, 30, 40, 50，将搜索的深度区间分为五种，即[2, 3],[1, 2, 3], [1, 2], [0, 1, 2], [0]。 可以看出相比 HEVC 原始帧内预测算法均统一进行 4 个深度级[0, 1, 2, 3]的 RDO 计算， 采用本文算法，至少可以减少 1 个深度级的 RDO 计算。若此时减少的刚好是深度级 3，则可以减少 64 次 CU 的 RDO 计算，减少的编码时间相当可观。 为了证明本文 4 个阈值(10,30,40,50）的合理性，我们取纹理特征互不相同的 4 个序列，量化参数分别选 取 22，27，32，37，统计其命中率,结果如表 1 所示。通过表 1，可看出本文基于二维直方图快速深度决策算 法对于测试序列命中率高达 90%以上，说明本文算法可精确排除不必要的深度计算。 表 1 本文基于二维直方图的快速深度决策算法命中率 序列 总的 LCU 块数 错判的 LCU 块数 命中率(%) BasketballDrill 18200 166 99.1 BQMall 18200 955 94.8 BlowingBubbles 3600 19 99.5 BQSquare 3600 300 91.7 4.实验结果与分析 实验采用 HM10.1 测试模型，测试的环境为具有 Intel(R) Core(TM)2 Quad CPUQ9400 @2.66GHz,4.0 GB 内 存的计算机，采用 VS2008 编译器。因为本文只针对帧内编码进行优化，故采用的编码配置为全帧内编码模式， 量化参数 QP 分别选取 22,27,32,37，序列全部统一编码 50 帧，其余为默认配置[10]。分别选取了 ABCDE 5 个 等级的分辨率共 11 个序列进行测试。需要注意的是，本部分所用的 11 个实验序列不与表 1 中的统计序列重合。 由于文献[3]也同样提出了帧内快速深度决策算法，所以我们也实现了文献[3]的快速深度决策算法部分，以用 来跟本文提出的算法进行比较。采用文献[3]以及本文算法与原始 HM10.1 比较的实验结果如表 2 所示。其中 BDBR 与 BDPSNR 是文献[11]中提出的评价准则，分别表示在同样的客观质量下，两种方法的平均码率节省情况 以及在给定的同等码率下，两种方法的平均 Y-PSNR 的差异。 △Time 定义如下式（2）所示： DTime = 其中 1 4 TimeHM 10.1(QPi ) - Timepro (QPi ) ´ 100% å 4 i =1 TimeHM 10.1(QPi ) （2） TimeHM 10.1(QPi ) ， Timepro (QPi ) 分别是原始 HM10.1 以及提出的算法在不同 QP 值下的编码时间。 表 2 本文算法与文献[3]比较的实验结果 文献[3]快速深度决策算法 序列 本文算法 BDBR(%) BDPSNR(dB) △Time(%) BDBR(%) BDPSNR(dB) △Time(%) Class A Traffic 0.800 -0.039 -21.0 0.850 -0.041 -19.6 2560×1600 PeopleOnStreet 0.664 -0.033 -21.0 1.678 -0.085 -19.4 Class B ParkScene 0.708 -0.027 -22.7 0.704 -0.027 -25.2 1920×1080 BasketballDrive 1.932 -0.045 -25.8 1.816 -0.042 -19.8 Cactus 0.621 -0.021 -22.8 1.115 -0.038 -23.7 Class C PartyScene 0.028 -0.002 -17.8 0.015 -0.001 -23.8 832×480 RaceHorses 0.342 -0.019 -17.1 0.392 -0.021 -21.7 Class D BasketballPass 0.989 -0.050 -11.0 0.389 -0.020 -13.5 416×240 RaceHorses 0.107 -0.006 -11.9 0.223 -0.012 -19.4 Class E FourPeople 0.644 -0.033 -20.3 1.228 -0.064 -28.4 1280×720 Vidyo1 1.439 -0.065 -21.6 1.100 -0.050 -23.5 Average 0.752 -0.031 -19.4 0.865 -0.036 -21.6 通过表 2， 我们可看出本文提出的算法与原始 HM10.1 相比，平均 Y BDPSNR 仅降低 0.036dB,而平均 BDBR 仅增加 0.865%，同时可以节省 21.6%的编码时间。从表 2 可以进一步看出，本文算法对于像 PartyScene 这类 纹理清晰的序列有较好的预测，基本不会影响其率失真性能，而同时可以减少 23.8%的编码时间。与文献[3]相 比，两者的率失真性能几乎相近，但本文算法编码时间减少量更多，提高了 2.2%。而且，本文算法是基于当 前 LCU 块的内部纹理特征，而文献[3]是基于一帧视频内空间上的连续性，即当前 LCU 块与周围已编码的 LCU 块最优深度之间满足的较强相关性。所以本文算法独立于文献[3]的算法，可以与其进一步融合，更大地减少 HEVC 的帧内编码复杂度。 图 5 给出了 Traffic 序列分别采用本文算法与原始 HM10.1 算法的 RD 曲线图。从图中我们可看出该序列 采用本文算法后的 RD 曲线与采用原始算法的 RD 曲线几乎重合，即在不同的比特率上本文提出的算法几乎与 HEVC 原始算法取得相同的 PSNR，这也进一步说明本文提出的算法具有较高的命中率。 Deleted: 9 Deleted: 0 45 43 Y-PSNR(dB) 41 39 37 HM10.1 35 本文算法 33 10000 20000 30000 40000 50000 60000 70000 Bit rate(kbps) 80000 90000 100000 110000 图 5 本文算法与原始 HM10.1 算法分别适用于 Traffic(class A 2560×1600)序列的 RD 曲线 5.结论 本文通过构造二维直方图提取当前 LCU 的纹理特征，并利用该纹理特征进行深度的自适应选择，跳过不 必要的深度计算。实验结果表明，本文算法可以保证取得与原始 HM10.1 几乎相同的率失真性能，同时可以减 少编码时间 21.6%，极大地降低了 HEVC 的编码复杂度。而且，本文算法独立于现阶段出版的大部分帧内快 速算法，可以与其他帧内快速算法融合,进一步减少 HEVC 的帧内编码复杂度。现阶段所做的研究工作都在快 速 CU 尺寸决策的层面上进行，下一步工作将尝试对帧内 35 种预测模式进行优化，以更大地减少 HEVC 的编 码复杂度。 参 考 文 献 [1] Han G J, Ohm J R, Han W J, et al. Overview of the High Efficiency Video Coding(HEVC) Standard[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(12): 1649-1668. [2] da Silva T L, Agostini L V, and da Silva Cruz L A. Fast HEVC intra prediction mode decision based on EDGE direction information[C]// Proceedings of the 20th European Signal Processing Conference (EUSIPCO). Piscataway, N. J: IEEE Press, 2012: 1214-1218. [3] Shen Liquan, Zhang Zhaoyang, and An Ping. Fast CU Size Decision and Mode Decision Algorithm for HEVC Intra Coding [J]. IEEE Transactions on Consumer Electronics, 2013, 59 (1): 207-213. [4] Jiang Wei, Ma Hanjie, and Chen Yaowu. Gradient Based Fast Mode Decision Algorithm for Intra Prediction in HEVC[C]// 2nd International Conference on Consumer Electronics, Communications and Networks (CECNet). Piscataway, N. J: IEEE Press, 2012: 1836-1840. [5] Ting Y C, Chang T S. Fast intra prediction algorithm with transform domain edge detection for HEVC[C]//Asia Pacific Conference on Circuits and Systems (APCCAS). IEEE Press, 2012: 144-147. [6] Zhang Yongfei, Li Zhe, and Li Bo. GRADIENT-BASED FAST DECISION FOR INTRA PREDICTION IN HEVC[C]//Visual Communications and Image Processing (VCIP). Piscataway, N. J: IEEE Press, 2012:1-6. [7] Kim J, Choe Y, Kim Y G. Fast Coding Unit size decision algorithm for intra coding in HEVC[C]//Consumer Electronics (ICCE), 2013 IEEE International Conference on. IEEE, 2013: 637-638. [8] 谢晶, 贾克斌. 一种基于二维直方图的 H.264/AVC 快速帧内预测判决算法[J]. 电子与信息学报, 2005, 27 (7): Deleted: 7 1053-1057. [9] Zhao Liang, Zhang Li, Ma Siwei, et al.. Fast mode decision algorithm for intra prediction in HEVC[C]//Visual Deleted: 8 Communications and Image Processing (VCIP). Piscataway, N. J: IEEE Press, 2011: 1-4. [10] Bossen F. HM 10 common test conditions and software reference configurations[C]// Proc.12th JCT-VC Meeting, Deleted: 9 Geneva, Switzerland, No. JCTVC-L1100. 2013: 1-3. [11] Bjontegard G. Calculation of average PSNR differences between RD-curves[J]. ITU-T VCEG-M33, 2001. 通信作者：林其伟（1959-） ，主要从事 HEVC 中的快速算法，qwlin@hqu.edu.cn，13615977053 基金项目：福建省自然科学基金资助项目（2012J01275） 许东旭，硕士，13615902173,807614322@qq.com Deleted: 0