由于视频信息具有真实、具体、生动、全面、信息量大等特点, 人们对各种视频信息的需求与日俱增, 使得大数据中海量视频信息的占比已过半, 因此, 保证海量视频信息的高效、优质、标准化的压缩日显重要^[1]. H.264/AVC^[2]视频编码标准逐渐不能满足应用需求, 所以H.265/HEVC^[3]视频编码标准应运而生.

HEVC视频编码性能的高效, 是以更高的算法复杂度换取的. 相对于H.264, 它在很多地方有了革命性的变化. HEVC放弃了之前编码标准中使用的宏块, 采用了具有四叉树递归划分的编码单元(CU)、预测单元(PU)和变换单元(TU). 这让编码更符合视频图像细节的特性. 但同时也显著增加了计算复杂度^[4]. 所以在不影响HEVC编码效果的前提下, 有效降低编码复杂度是目前研究的热点.

帧内编码是视频编码的一个重要组成部分. HEVC中CU、PU和TU的四叉树递归划分和35种帧内预测模式, 导致了编码复杂度极高. 相关学者提出了很多帧内快速编码算法, 主要可以分为两大类: 1) 根据当前CU周围相邻已编码重建单元的编码结果, 对当前CU的最佳划分方式进行估计, 跳过一些可能性较小的结构; 2) 根据视频图像本身的纹理特性, 通过一些预处理方式, 实现各深度下CU的早划分或早裁剪或减少PU预测模式数量. Zhang等^[5]通过分析空间上相邻的已编码完成的CU和时间上前一帧相同位置的CU与当前CU的关系, 对当前CU进行快速分割; Zhao等^[6]根据相邻CU的结构相似性, 当前CU的划分结构和预测模式直接利用相邻相似度高的已编码CU的结果; 文献[7,8]用当前CU内像素方差值表示CU复杂程度, 根据复杂程度决定CU分割; 文献[9,10]利用Sobel算子对当前CU进行边缘检测, 进而分析纹理复杂程度, 根据纹理复杂程度决定CU是否划分. 蔡婷婷等^[11]根据CU在水平、垂直、45°和135°方向上的全局边缘复杂度来判断CU是否划分, 并通过比较水平和垂直方向的边缘复杂度大小减少预测模式数量, 但全局边缘复杂度计算比较复杂, 且预测模式数量减少较少。

目前多数算法是单一的从CU的尺寸选择或PU预测模式的快速决策入手. 通过分析HEVC帧内编码过程, 本文提出一种基于编码块纹理特征的CU尺寸提早划分, PU预测模式快速决策算法. 通过一种预处理算法获取当前CU的纹理复杂度和方向性. 根据纹理复杂度决定部分CU的划分方式, 根据纹理方向性减少PU预测模式的数量. 从CU和PU两方面来降低帧内编码的复杂度.

1 HEVC帧内编码复杂度分析

在HEVC测试软件HM中, 一帧图像首先被分割成多个最大编码单元(LCU), 对每个LCU以光栅扫描的顺序进行编码. 单个LCU可以进一步划分成多个CU. 深度(Depth)为0, 1, 2, 3分别对应CU的尺寸为64×64, 32×32, 16×16, 8×8. 当深度为0 , 1 , 2时, PU尺寸与CU相同, 当深度为3时, PU尺寸可以是8×8, 也可以4×4. 因此, 在CU与PU划分组合的过程中, 需要进行 ${4^0} + {4^1} + {4^2} + {4^3} + {4^4} = 341$ 次递归划分. 递归划分过程如图1所示, LCU先自上而下分割成4个尺寸为32×32的子CU (sub-CU),每个 sub-CU还可以继续分割成4个sub-CU, 直到深度为3为止. 然后自下而上进行CU裁剪. 对每个sub-CU分别进行35种帧内预测模式搜索, 找到率失真代价最小的最佳预测模式, 并将4个sub-CU的率失真代价和与其父CU的率失真代价进行比较决定父CU是否划分. 若父CU的率失真代价小于4个sub-CU的率失真代价和, 则这个父CU不分割成4个sub-CU, 反之则分割.

每一个CU都需要进行PU模式选择. 图2是HEVC帧内预测的35种预测模式示意图.

首先, 利用公式(1)对PU的35种预测模式进行粗选(Rough Mode Decision, RMD).

${J_{\rm {RMD}}} = SATD + {\lambda _{\rm {pred}}} \times Bit$

(1)

其中, SATD表示残差信息Hadamard变换绝对值之和, ${\lambda _{\rm {pred}}}$ 为拉格朗日乘子, Bit为编码码率. 当PU尺寸是8×8和4×4时分别粗选出8种预测模式; 当PU尺寸是64×64, 32×32, 16×16时分别粗选出3种预测模式^[12]. 然后再从周围已编码的块中提取出当前PU的最有可能模式(Most Probable Mode, MPM). 将粗选出的模式和MPM一起加入到候选列表中, 进行率失真优化(RDO)计算, 确定这个PU最佳的预测模式. RDO计算公式(2)如下:

${J_{\rm {RDO}}} = SSE + {\lambda _{\rm {mode}}} \times Bit$

(2)

其中, SSE为残差平方和, ${\lambda _{\rm {mode}}}$ 为拉格朗日乘子, Bit为编码所需码率. 在这个过程中一共需要进行 $35 \times \left( {{4^0} + {4^1} + {4^2} + {4^3} + {4^4}} \right) = 11\;935$ 次J_RMD的计算, 然后至少需要进行 $3 \times \left( {{4^0} + {4^1} + {4^2}} \right){\rm{ + }}8 \times \left( {{4^3}{\rm{ + }}{4^4}} \right){\rm{ = }}2623$ 次RDO计算. 这些计算导致帧内编码的复杂度极高^[13].

图3是HM10.0 (HEVC Test Model)实际编码一帧图像的CU划分图. 从图3中, 我们可以看出纹理平坦的区域如背景墙壁和地面, 适合用大尺寸的CU进行编码. 而纹理复杂的区域如人脸和篮球, 适合用较小尺寸的CU编码. 所有可以根据图像的纹理特征避免一些不必要的递归划分.

2 HEVC帧内编码快速算法 2.1 编码块纹理特征提取函数的提出

在HEVC帧内编码的过程中, 图像的纹理特征与CU的划分方式以及PU预测模式有着非常紧密的联系. 所以, 本文提出一种纹理特征提取函数, 提取编码块水平、垂直、45°和135°方向上的纹理复杂度. 计算公式如(3)~(6).

$VarH = \frac{1}{{N \times N}}\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{N - 1} {\left| {Y(i,j) - {Y_H}(i)} \right|} } $

(3)

$VarV = \frac{1}{{N \times N}}\sum\limits_{j = 0}^{N - 1} {\sum\limits_{i = 0}^{N - 1} {\left| {Y(i,j) - {Y_V}(j)} \right|} } $

(4)

$Var{45^ \circ } = \frac{1}{{N \times N}}(Var{45^ \circ }_L + Var{45^ \circ }_R)$

(5)

$Var{135^ \circ } = \frac{1}{{N \times N}}(Var{135^ \circ }_L + Var{135^ \circ }_R)$

(6)

在公式(3)和(4)中, VarH和VarV分别表示水平和垂直方向的纹理复杂度(Variance), Y(i,j)为编码块在第i行第j列的像素值, Y_H(i)为第i行像素的均值, Y_V(j)为第j列像素的均值, N表示当前编码块的尺寸. 在公式(5)和(6)中, Var45°和Var135°分别表示45°和135°方向上的纹理复杂度. 以CU尺寸64×64为例说明特征提取函数, 如图4所示, 将尺寸为64×64编码块的所有像素点划分到45°和135°方向. 纹理复杂度的计算将沿对角线分成左右两部分用Var45°_L、Var45°_R、Var135°_L和Var135°_R表示. 公式(5)和公式(6)可以进一步分解成公式(7)~(10). 其中, N表示当前CU的尺寸, Y_45°(k)表示从左上角到右下角第k(0<=k<=2×N-1)个45°方向上像素点的均值, Y_135°(k)表示从左下角到右上角第k(0<=k<=2×N-1)个135°方向上像素点的均值, 绝对值中的被减数表示沿着第k个45°或135°方向上相应位置处的像素值.

$Var{45^ \circ }_L = \sum\limits_{k = 0}^{N - 1} {\sum\limits_{i = 0}^k {|Y[(i \times N),(k - i)] - {Y_{{{45}^ \circ }}}(k)|} } $

(7)

$Var{45^ \circ }_R = \sum\limits_{k = N}^{2 \times N - 2} {\sum\limits_{i = k - (N - 1)}^{N - 1} {|Y[(i \times N),(k - i)] - {Y_{{{45}^ \circ }}}(k)|} } $

(8)

$Var{135^ \circ }_L \!=\! \sum\limits_{k = 0}^{N - 1} {\sum\limits_{j = 0}^k {|Y[(N \!- \!1 \!+\! j - k) \times N,j] \!- \!{Y_{{{135}^ \circ }}}(k)|} } $

(9)

$Var{135^ \circ }_R =\!\!\! \sum\limits_{k = N}^{2 \times N - 2} \!\!\!{\sum\limits_{j = k - (N - 1)}^{N - 1} \!\!\!\!\!\!\!{|Y[(N - 1 + j - k) \times N,j] - {Y_{{{135}^ \circ }}}(k)|} } $

(10)

图像纹理简单区域, 像素点的值比较接近, 那么VarH、VarV、Var45°、Var135°的值都会很小. 如果图像纹理存在方向性, 比如沿水平方向, 那么水平方向的像素值相差就不会很大, 则VarH的值最小, VarV、Var45°和Var135°相对要大. 所以通过分析VarH、VarV、Var45°和Var135°可以得出编码块的复杂度和方向特性.

2.2 CU分割快速算法

本文CU快速分割算法是通过上述四个方向上计算出来的编码块的复杂度与阈值进行比较, 决定当前编码块是否要分割. 所以阈值的选取至关重要, 在HM10.0中加入特征提取函数, 让HM10.0在正常编码测试序列ClassA~ClassE的过程中分析阈值的取值. 当QP=32时, 通过大量仿真实验表明, 选取阈值Var_Thre=6时, 编码效果最佳. 本文提出的CU快速分割算法, 具体实现步骤如下:

首先计算当前编码块的VarH、VarV、Var45°和Var135°. 求出这四个值里面的最大值VarMax和最小值VarMin, 如式(11)和式(12).

$VarMax = \max (VarH,VarV,Var{45^ \circ },Var{135^ \circ })$

(11)

$VarMin = \min (VarH,VarV,Var{45^ \circ },Var{135^ \circ })$

(12)

然后通过VarMax和VarMin与Var_Thre进行比较决定部分CU是否划分. 如果VarMax小于Var_Thre, 可以认为当前编码块是纹理简单区域, 则CU不用进行子块划分. 如果VarMin大于1.25×Var_Thre, 则可以认为当前编码块为纹理复杂区域, 直接跳过率失真代价计算, 将CU划分成4个Sub-CU. 如果不满足前面的两个条件, 则按照HM10.0的算法进行正常流程的CU划分的判断. 这样挑选出编码过程中根据纹理特征本可避免递归划分的CU, 直接进行划分判断, 所以本算法可以大大减少CU四叉树划分的时间.

本文快速CU分割算法, 实际分割的一帧图像如图5所示. 满足纹理复杂区域用小尺寸CU编码, 纹理简单区域用大尺寸CU编码. 与图3标准算法分割图相比, 省去了一些不重要位置的详细划分, 不会影响重建图像的视觉效果. 但更为简单的划分方式, 可以很好地缩短CU划分的时间.

2.3 PU预测模式优化算法

由前面分析可知最佳预测模式一般是与纹理方向保持一致. 所以先对35种预测模式进行分类, 通过VarMin判断当前编码块最佳预测模式落在哪个类中, 然后只在这个类中进行寻找. 将图2中的0–34种预测模式分成四类, 可得C₀–C₃候选集^[14]. 如表1所示.

若当前编码块的纹理平坦, 不存在纹理方向性, 那么VarMax与VarMin比较接近, 即VarMax–VarMin<0.1×VarMin, 则将DC、Planar和MPM模式进行RDO计算, 选出最佳模式. 若VarSecMin–VarMin<0.1×VarMin, 其中VarSecMin为VarH, Var45°, VarV和Var135°中的第二小值, 说明当前编码块存在两个纹理方向, 将这两个方向对应的候选集C_i和C_j作为先选模式, 根据当前深度粗选出J_RMD值较小的前N(数量同文献[12])个候选模式和MPM 模式一起进行RDO计算. 其它情况下, 说明当前编码块只存在一个纹理方向, 若此时编码块的深度小于等于2, 则将候选集C_i先进行RMD计算粗选出J_RMD值较小的前3种候选模式和MPM模式一起进行RDO计算. 若当前编码块深度大于2, 则将候选集C_i和MPM模式一起进行RDO计算, 选出最佳模式.

2.4 帧内编码快速算法的流程

帧内编码快速算法的流程如图6.

3 实验结果与分析

为了评估本文快速算法的编码性能, 本文以HEVC的参考实现软件HM10.0为参照进行试验. 实验硬件平台是Intel(R) Core(TM) i5-3317U CPU@1.70 GHz, 内存为4 GB, 软件开发环境是Windows7, Visual Studio 2010. 因为本文只针对帧内编码进行优化, 故采用的编码配置模式为全I帧(AI)模式, QP选取32, 测试时使用JCT-VC提供的标准视频测试序列ClassA~ClassE, 全部统一编码100帧. 为了分析算法的性能, 使用节省的编码时间百分比 $\Delta ET$ 、比特率增量 $\Delta BR$ 、峰值信噪比增量 $\Delta PSNR$ 作为衡量标准. 计算公式为(13)~(15).

$\Delta ET = ({T_{\rm {HM10.0}}} - {T_{\rm {proposed}}})/{T_{\rm {HM10.0}}} \times 100\% $

(13)

$\Delta BR = (B{R_{\rm {proposed}}} - B{R_{\rm {HM10.0}}})/B{R_{\rm {HM10.0}}} \times 100\% $

(14)

$\Delta PSNR = PSN{R_{\rm {proposed}}} - PSN{R_{\rm {HM10.0}}}$

(15)

其中, T_proposed、BR_proposed、PSNR_proposed分别表示本文快速算法的编码时间、比特率和峰值信噪比; T_HM10.0、BR_HM10.0、PSNR_HM10.0分别表示HEVC测试模型HM10.0的编码时间、平均比特率和峰值信噪比.

表2是本文算法与标准算法HM10.0对比的实验结果. 根据表2, 本文算法在码率升高0.649%, 峰值信噪比降低0.059 dB的情况下, 编码时间平均减少56.18%.

表3是本文算法和参考文献其它快速算法与HM标准算法的比较结果. 根据表3的数据, 本文快速算法与其它快速算法在码率和峰值信噪比相差不大的情况下, 能够节省更多的编码时间.

图7是本文算法与HM10.0的RD性能比较. 如图所示, 本文算法在编码视频序列BasketballPass(416×240_50)下的RD曲线与HM10.0算法的RD曲线基本重合. 所以本文算法的编码性能与HEVC标准算法相比, 没有明显的下降.

从主观评价上, 本文算法和HM10.0标准算法编码重构后的图像如图8和9. 从这两幅图像的比较中, 可以看出本文算法与HM10.0标准算法实际编码并没有明显差异.

4 结束语

本文快速算法是根据当前编码单元的纹理特征, 来降低帧内编码算法的复杂度, 节省编码时间. 实验结果显示, 在保证视频质量和码率的情况下, 有效地降低了编码时间. 本文算法考虑了编码块的纹理特征, 并没有考虑到视频信息中存在的时空相关性, 接下来将研究编码单元划分深度的时空相关性进一步降低HEVC视频编码算法的复杂度, 缩减编码时间. 之后, 本文快速算法将应用于智能回收箱项目的视频监控.