0 引言

随着科技的飞速发展和人们生活水平的提高,人们对高分辨率视频的需求越来越大,与此同时高码率的视频传输和大容量的视频存储成为人们关注的热点。高效视频编码(High Efficiency Video Coding,HEVC)^[1]是目前为止最新的视频编码标准,它是在视频编码联合专家组(Joint Collaborative Team on Video Coding,JCT-VC)的努力下形成的。与H.264/AVC^[2-4]相比,HEVC采用了35种帧内预测模式、灵活的树形编码结构、采样点自适应偏移(Sample Adaptive Offset,SAO)、并行化设计等新方法。因此,在同等画质的条件下,HEVC编码效率比H.264提高了一倍,但与此同时也大大增加了编码复杂度。HEVC想要实时应用,就必须优化其内部算法提高编码速度。

H.265/HEVC仍采用基于块的混合编码框架,它的帧内编码快速算法在H.264基础上主要对以下两方面加以改进。一种是帧内35种预测模式快速最优的选择:文献^[5] 提出一种基于边缘方向强度检测的快速帧内预测模式选择算法,该算法将35种帧内预测模式数减少为11种,省去了对不必要的预测模式的率失真优化(Rate Distortion Optimization,RDO)计算；但该算法只对预测模式数进行了优化,未考虑帧内预测模式率失真优化计算过程,对编码速度的提升还不是很明显。文献^[6]通过将帧内预测模式分级计算,将35种帧内预测模式数只利用其中17种模式即能得出最佳预测模式,然而该算法平均码率增加约5.23%。另一种是提前终止编码单元的划分或跳过编码单元的某些深度:文献^[7]利用在一帧图像中相邻编码单元之间具有较强的相关性,设计出两种方案来优化帧内编码,主要思路是跳过在其他相邻编码单元(Coding Unit,CU)中几乎不常见的某些特定深度或预测模式,从而减少编码时间；但该算法由于利用的是相邻CU之间的相关性仍需要大量的计算,平均编码时间只减少21%。文献^[8]利用贝叶斯决策准则方法,提前对CU的裁剪过程作判断,减少不必要的深度计算,从而减少了当前HM(HEVC Test Model)的计算复杂度;然而该方法没有考虑到一帧图像相邻编码单元内部纹理的相关性。文献^[9]对于CU的划分,提出了一种基于绝对误差和(Sum of Absolute Transformed Difference,SATD)的方法,从而提前终止CU的划分过程。该算法通过对每个编码单元最小的SATD值与指定的阈值进行比较,最终确定该编码单元是否需要继续被划分,该方法很有效,对多数视频序列都有所改进,但该方法对比较简单的视频序列帧内编码时间的改进不是很明显。文献^[10] 提出了一种基于时域相关性的帧内快速深度决策算法,该算法利用关联帧编码树单元(Coding Tree Unit,CTU)和当前编码单元的相关性来估计当前最大编码单元(Largest Coding Unit,LCU)的深度值；但该算法忽略了帧内相邻编码单元空域间相关性,使压缩时间减少了21.3%。

以上算法都在一定程度上减少了HEVC的编码时间,但对比较简单的视频序列帧内编码时间的改进不是很明显。本文提出了一种基于空域相关性的帧内快速深度决策算法,该算法对比较简单的视频序列编码时间的改进比较明显。首先由左方、上方、左上方和右上方CTU的深度值通过线性加权得出当前的CTU的深度预测值;然后对当前CTU深度的估计值设置较为合适的上下阈值提前终止编码单元的划分或跳过CTU的某些深度,从而缩小了每个编码单元深度的遍历区间,省去了大量CU不必要的计算和模式预测,减轻了帧内编码的负担。

1 LCU 最佳分割方式选择过程

HM是由JCT-VC所采用的HEVC的标准测试模型^[11],该模型的最基本的编码单元是CU。它把视频中每一帧图像分割成多个等大的LCU方形块,LCU是最大的编码单元,其尺寸是64×64,深度为0。如图 1所示,LCU在HM中采用递归的方式进行四叉树结构的划分,LCU每分割一次其尺寸就变为原来的一半,深度值增加1,直到分割为最小编码单元(Smallest Coding Unit,SCU)时停止划分,它的尺寸是8×8,深度为3。

因此,为了选择一个最优的CU,需要遍历所有64×64到8×8的分割。最终,通过比较率失真代价(Rate Distortion Cost,RD-Cost)选择出LCU 的最佳分割方式,LCU最佳分割方式选择过程如图 2所示。

第1步 对LCU进行分割。如图 2向下的细黑色箭头表示该过程是自上而下进行的,其中D表示编码单元的深度值。首先,对尺寸为64×64的 LCU编码单元a经过帧内预测,计算其RD-Cost值。然后,对编码单元a进行一次分割,得到深度为1的四个子块:b₀、b₁、b₂、b₃；并对b₀块通过帧内预测,计算其RD-Cost值。对编码单元b₀继续分割,得到深度为2的四个子块:c₀、c₁、c₂、c₃；并对c₀块通过帧内预测,计算其RD-Cost值。对编码单元c₀继续分割,得到深度为3的四个子块:d₀、d₁、d₂、d₃；并对四个子块分别通过帧内预测,计算出各自的RD-Cost值。此时,d₀、d₁、d₂、d₃四个子块尺寸大小都为8×8,以达到最小的编码单元(SCU),不可以再继续分割。

第2步 对LCU进行修剪。如图 2向上的粗灰色箭头表示该过程是自下而上进行的。主要将每个父CU的RD-Cost值与其相应的四个子CU的RD-Cost之和的值进行比较,最终来决定父CU是否进行分割。从8×8的子SCU开始,若深度为3的四个子块:d₀、d₁、d₂、d₃率失真代价之和小于其对应的深度为2的父块c₀的率失真代价,则保留深度为3的CU分割方式；否则丢弃深度为3的CU分割,选择深度为2的父块c₀的分割方式。以此类推,继续往上修剪,直到深度为0的编码单元a。

通过以上两步找出该LCU的最佳划分方式,且需要进行4⁰+4¹+4²+4³=85次不同深度CU的率失真代价计算。每个CU还需要进行大量的帧内预测。在帧内预测过程中,对于编码单元的一个亮度块,前期粗略模式选择(Rough Modes Decision,RMD)共需要计算35×(4⁰+4¹+4²+4³+4⁴)=11935次哈达玛变换代价的值,然后对于尺寸小于或等于8×8的PU选取候选模式数为8,尺寸大于8×8的PU选取候选模式数为3,此外,还需要加上MPM(Most Probable Mode)^[12]共同构成候选模式集,所以后期至少需要进行3×(4⁰+4¹+4²)+8×(4³+4⁴)=2623次率失真代价计算。由此可见,HEVC的编码更加精确细致，但同时也大大增加了编码的复杂度和编码时间,不利于实时应用。

2 HEVC帧内快速深度决策算法 2.1 CTU的深度

在HM中CTU的大小为64×64,划分深度从0到3。最小的CU为8×8,最大的CU为64×64。所以每个CTU内部CU的深度不完全一致,那么本文算法中的CTU深度值分别用下面的方法来得出。本文利用CTU编码深度的相关性:用上方、左方、左上方和右上方CTU的深度值来加权得出当前CTU深度的估计值。如图 3所示,左上方CTU的深度值用该CTU右下角CU的深度值D₁来代替；右上方CTU深度值用该CTU左下角CU的深度值D₂来代替；上方CTU的深度值用该CTU下边界处出现概率最大的CU的深度值P_{u_max}来替代；左方CTU的深度值用该CTU右边界处出现概率最大的CU的深度值P_{l_max}来替代。

2.2 HEVC帧内快速深度决策算法

在HM中各编码单元具有空域相关性,CU的深度值与图像的纹理特征密切相关。图像纹理平坦区域CU的深度值一般都比较小，反之图像纹理复杂的区域CU的深度值会比较大。如图 4所示,在纹理平坦区域1和2处的深度值都为1,在纹理复杂区域3和4处的深度值都是3。在一帧视频图像中,相邻的像素间具有较强的相关性,相邻CTU的纹理特征会比较相似。因此,相邻CTU的各个深度值之间也具有较强的相关性。在HM中,对于整个视频序列,每一个编码单元都会遍历从0到3所有的深度值,由上面计算可知这是一个相当耗时的过程。如图 3所示,本文根据相邻CTU各个深度值间较强的相关性,由左方、上方、左上方和右上方CTU的深度值通过线性加权得出当前的CTU的深度预测值;如式(1)所示,当前CTU深度值的估计值由相邻CTU的深度值线性加权表示。

${{\text{D}}_{\text{p}}}\text{=a}\times \left( {{\text{D}}_{\text{u}}}+{{\text{D}}_{\text{l}}} \right)\text{+b}\times \left( {{\text{D}}_{\text{l }\!\!\_\!\!\text{ u}}}+{{\text{D}}_{\text{r }\!\!\_\!\!\text{ u}}} \right)$

(1)

其中:D_p表示当前CTU的深度的估计值； D_u、D_l、D_{l_u}和D_{r_u}分别表示与当前编码树单元相邻的上方、左方、左上方和右上方已编码树单元的深度值；a表示上方和左方CTU权重因子的值；b表示左上方和右上方CTU权重因子的值。就空间位置而言,相对于左上方和右上方CTU,上方和左方的CTU离当前CTU更近,那么上方和左上方CTU与当前CTU的相关性更大,所以相对而言它们的加权系数也会比较大。因此,式(1)中权重因子a取0.4,b取0.1。

经过大量的实验,得出了较为合适的深度双阈值,通过上下阈值将深度区间划分为0到0.5、0.5到1.5和大于1.5这三部分。若深度估计值D_p在0~0.5,则当前CTU块的最大深度值D_{c_max}不超过1,也就是CTU中每个CU的最大深度值都不超过1,提前终止了编码单元的划分;若D_p在0.5~1.5,则当前CTU的最大深度值D_{c_max}不超过2,也就是CTU中每个CU的最大深度值都不超过2,提前终止了编码单元的划分;若D_p大于1.5,则跳过深度值为0的深度。从而实现深度自适应选择,减少不必要的深度计算。

随着编码深度的增大,所耗的编码时间也越来越大。当CU的深度值大于1时,即CU的尺寸小于32×32,其耗时占整个CU模式判决的60%^[13]。因此,用深度自适应选择的方法来提前终止或跳过CTU的某些特定深度,对降低编码时间很有效。

由以上算法可知,本文算法对简单类视频序列编码时间的改进会更加明显。因为,简单类视频序列的D_p都比较小,所以提前终止很多编码单元的划分。如图 5所示,周围相邻四块的CTU块比较简单,假设它们的深度值都为0,那么按照式(1)求得的D_p小于0.5,所以当前块的最大深度值是1,CU只需遍历0到1的深度,省去CU遍历深度值为2到3的大量计算。

为此,本文先对文献^[9]中14个视频序列的第一帧用式(2)作复杂度判断：若第一帧图像亮度分量的复杂度大于等于26.7小于等于40.4时,此时的视频序列相对比较简单用本文算法进行编码；反之,若第一帧图像亮度分量的复杂度小于26.7或大于40.4时,则该视频序列用文献^[9]算法进行编码。实验结果表明,引入该判断所损耗的时间几乎忽略不计,但却使得该算法对所有视频序列都具有普适性。

$V\text{a}{{r}_{\text{y}}}=\frac{1}{M\times N}\times S $

(2)

其中:

$S\text{=}\sum\limits_{i=0}^{M}{\sum\limits_{j=0}^{N}{\left| P(i,j)-\frac{1}{M\times N}\times (\sum\limits_{i=0}^{M}{\sum\limits_{j=0}^{N}{P(i,j)}}) \right|}}$

P(i,j)表示(i,j)点所对应的像素值;M和N分别表示第一帧视频图像的长和宽;Var_y表示视频序列第一帧视频图像亮度分量的复杂度。

2.3 算法流程

本文算法步骤如下:

1) 读入视频序列。

2) 用式(2)求出视频序列第一帧图像亮度分量的复杂度Var_y。

3) Var_y与上下阈值进行比较,若26.7≤Var_y≤40.4,则该视频序列用本文算法进行编码，并进入第4)步；否则该视频序列用文献^[9]算法进行编码。

4) 本文算法进行编码,获取CTU块,并得到左方、上方、左上方和右上方已编码的CTU块的深度值。

5) 判断相邻的CTU块是否存在。如果存在,那么通过2.1节所提出的方法计算出相邻CTU块各自的深度值;否则赋固定深度值给相邻的CTU。

6) 将以上四个相邻CTU块的深度值线性加权得到当前CTU块的深度估计值D_p。

7) D_p与所设定的上下阈值进行比较,若D_p≤0.5,则当前CTU的最大深度值D_{c_max}≤1,也就是CTU中每个CU的最大深度值都不超过1,提前终止了编码单元的划分;若0.5<D_p≤1.5,则当前CTU的最大深度值D_{c_max}≤2,也就是CTU中每个CU的最大深度值都不超过2,提前终止了编码单元的划分;若D_{c_max}>1.5,跳过深度值为0的深度。从而减少不必要的深度计算,大大减少了编码的计算复杂度。

在HM12.0中是通过xCompressCU函数的递归调用来判断当前的编码单元是否进行划分,从而实现对CU的递归划分。HM代码中各类之间的关系流程如图 6所示。

3 实验结果与分析

通过HEVC的标准测试模型HM12.0验证本文的帧内快速深度决策算法。所用计算机的处理器为 Intel Core i5-4200MC PU @ 2.50GHz,内存为4GB,64位Windows 7操作系统,并在Microsoft Visual Studio 2008下编译和运行程序。HM12.0中的主要配置参数同文献^[9]一样,LCU为64×64,视频测试序列的编码帧数为50帧,量化参数(Quantization Parameter,QP)分别设置为22.27.32 .37 ,编码深度范围为0~3,并采用全I帧的编码模式。本文算法分别从比特率、亮度峰值信噪比、编码时间三方面分别与文献^[7]算法和文献^[9]算法进行比较,文献^[7]算法和文献^[9]算法的实验数据均来源于文献^[9]。表 1中的BDPSNR(Bjøntegaard Delta Peak Signal-to-Noise Rate)和BDBR(Bjøntegaard Delta Bit Rate)是文献^[14]中提出的评价准则,分别表示相同码率条件下两种方法的平均Y-PSNR(Y-Peak Signal-to-Noise Ratio)的差异和相同PSNR(Peak Signal-to-Noise Ratio)条件下码率的变化百分比;ΔT表示编码时间变化的百分比,如式(3)所示:

$\Delta T = \frac{1}{4}\sum\limits_{i = 1}^4 {\frac{{Tim{e_{HM12.0}}(Q{P_i}) - Tim{e_{pro}}(Q{P_i})}}{{Tim{e_{HM12.0}}(Q{P_i})}}} \times 100\% $

(3)

其中:Time_HM12.0(QP_i)、Time_pro(QP_i)分别是原始HM12.0以及本文算法在不同QP值下的编码时间。

本文算法主要对简单类视频序列的编码加以改进,通过实验测试ParkScene、Kimono、BQMall、RaceHorses(C类)和RaceHorses(D类)这5个视频序列第一帧图像亮度分量的复杂度Var_y的值均介于26.7~40.4,图像的复杂度都比较低,所以实验仿真主要选取了这5个复杂度比较小的视频序列进行测试。

从表 1可知,本文算法对比较简单的视频序列有较明显的改进,本文算法与HM12.0相比,在亮度峰值信噪比几乎不变的情况下(平均降低0.02dB),编码时间平均减少了34.6%。本文算法在亮度峰值信噪比不变的情况下,比特率和编码时间两方面均优于文献^[7],比特率和编码时间分别减少了0.02%和11.2%。与文献^[9]所提出的帧内快速算法相比,在视频质量影响可以忽略的情况下,压缩时间平均减少10%。本文算法对比较简单的高清视频序列改善更为可观,对于像Kimono序列优化效果非常明显,在率失真性能几乎不变的情况下,编码时间减小58.8%。

图 7给出了 Kimono序列分别采用 HM12.0 原算法与本文算法的率失真(Rate Distortion,RD) 曲线,两种算法的RD曲线几乎重合,即图像的客观质量和比特率几乎不变,这表明与HM12.0原算法相比,本文算法的编码性能几乎没变。图 8给出了 Kimono序列的第一帧HM12.0算法重建图像和本文算法重建图像。由图 8可以看出,两种算法重建图像的主观质量几乎一样。

4 结语

本文基于CTU的深度和图像纹理之间的相关性,揭示出当前CTU的深度与相邻编码树单元(CTU)深度有着密切的关系,提出一种基于视频序列空域相关性的帧内快速深度决策算法。

通过该算法缩小了编码单元深度的划分区间,使得在编码时间大量减少的前提下,峰值信噪比几乎不变,更利于视频实时的传送与播放。此外,本文算法易于仿真,有利于软硬件的实现。下一步打算对帧内35种预测模式的选择进行优化。