新一代视频压缩编码标准高效视频编码(High Efficiency Video Coding，HEVC)^[1]由MPEG与VCEG组成的视频编码联合专家组(JCT-VC)制定，最初于2010年1月启动，并于2013年1月正式完成发布^[2].HEVC的目标在于大幅提高视频编码效率，在相同图像质量的前提下，压缩率比H.264/AVC高档次(High Profile)提高一倍，支持从320×240到7 980×4 320各种分辨率的视频^[3].同时，相比H.264的传输特点^[4]，HEVC的码流结构更适合传输速度越来越快的网络环境^[5].为此, HEVC在编码流程的各个环节都做了大量的改进.其中在帧内预测方面，预测模式由8种扩展为36种；编码块尺寸由4×4和8×8两种扩展为由4×4到64×64共5种尺寸.但多种模式和多层深度的遍历计算，在提高了预测精度的同时，也大幅增加了运算复杂度^[6].因此，对HEVC的应用推广来说，快速帧内预测算法的提出是必然需求.

现阶段HEVC的快速帧内预测算法可分为两类.第一类是减少遍历计算的模式个数，尤其是进入率失真优化(Rate-Distortion Optimization，RDO)阶段的候选模式个数.如文献[7-8]提出的根据像素梯度统计信息，减少进入粗模式选择(Rough Mode Decision，RMD)和RDO的候选模式个数.文献[7]的算法在HEVC标准测试模型HM4.0的测试中，编码时间减少了20%，码率增加了0.74%.此外，文献[9]利用组合比较的方法, 减少了RMD遍历的模式个数.文献[10-11]利用分组合并的方法快速得到编码单元(Codiny Unit, CU)的最佳模式.第二类是减少遍历计算的层次深度.如文献[11]提出了基于CU当前深度的总代价与当前量化参数(Quantization Parameter, QP)的比较，跳过之后的深度遍历，该算法在HM5.2rc1的测试中，编码时间减少了24%，码率增加了0.83%.此外，文献[12]提出了通过CU当前深度与上一深度的率失真代价(Rate-Distortion Cost，RD Cost)的比较跳过当前以及之后的深度遍历的算法；文献[13-14]提出了根据区域图像特征快速选定CU划分深度的算法.以上算法虽然都在一定程度上减少了编码时间，但减少幅度还不大.本文提出的算法能在码率增幅极小的前提下，大幅减少帧内预测编码时间，更有利于HEVC的应用推广.

1 HEVC帧内编码 1.1 帧内编码块和预测模式

HEVC划定了如图 1所示的四叉树结构的编码单元(Coding Unit, CU), 以此作为单位进行编码.先规定最大的CU(Largest CU, LCU)，最大为64×64，往下可逐层划分，最小尺寸为8×8.每一层成为一个深度，并规定LCU的深度为0，往下递增.在帧内编码中，LCU之间按光栅扫描顺序逐个编码，而在LCU内部则按Z扫描顺序对各个深度的CU进行遍历预测.在非最大深度CU中，预测单元(Prediction Unit, PU)尺寸都与CU相同，即按2N×2N方式划分.当完成最大深度CU的预测后，则要在最大深度CU的基础上再往下划分一层深度PU进行遍历预测，即按N×N方式划分.如图 2所示，HEVC的帧内预测模式有36种，其中包括33种角度预测模式(编号为2到33)，2种非角度预测模式(编号为0的Planar和编号为1的DC模式)，1种色度预测特有的亮度导出模式(编号为36的DM，编号为35的LM预测模式已被弃用，但仍保留其编号)^[15].

1.2 帧内预测流程

自2013年JCT-VC正式发布了HEVC后，其标准测试软件HM趋向稳定.根据HM13.0，HEVC的帧内亮度预测流程如图 3所示，可分为4个环节.首先进行RMD，对PU遍历35种模式预测.每次对预测块与原始块的残差使用哈达玛变换，得到其SATD值.定义每个模式RMD预测的总代价HC为

$ {\rm{HC}} = {\rm{SAT}}{{\rm{D}}_{{\rm{pre}}}} + \lambda \cdot R, $

(1)

其中SATD_pre是预测块与原始块的SATD值，λ是拉格朗日乘子，R是使用该模式编码的比特率.在这35种模式中，根据PU的尺寸选择其HC最小的N个模式作为候选模式集MC.若PU尺寸大于或等于16×16，则N= 3；否则N= 8.其次，进行最有可能模式选择(Most Probable Mode，MPM)，即根据当前PU的左、上边已编码的邻近PU的模式，添加1或2种模式进候选模式集MC，并更新N的值.然后对这N种候选模式进行第一次率失真优化(RDO1)，定义其率失真代价RC为

$ {\rm{RC}} = {\rm{SS}}{{\rm{D}}_{{\rm{rec}}}} + \lambda \cdot R, $

(2)

其中SSD_rec(Sum of Squared Difference)是使用该模式编码的重建块与原始块的残差.RC最小的模式即为帧内预测的最佳模式.最后对该最佳模式进行第二次率失真优化(RDO2)，该次RDO使用了TU划分，根据两者RC的比较，以确定PU是作为一个TU，还是划分为多个TU进行编码.

2 HEVC快速帧内预测算法 2.1 减少遍历计算的模式个数

HM标准帧内预测算法中，在RMD环节要计算35个模式，在两次RDO环节共要计算N+1个模式，其计算量过于庞大.由于RDO使用的是重建块，每计算一次RDO，就相当于对PU做了一次完整的编码流程，计算量更是远大于RMD.因此，本文提出如图 4所示的一系列快速算法，以减少进入RMD和RDO环节的模式个数.

2.1.1 减少RMD计算的模式个数

RMD的快速算法分4步，每计算一个模式则排序更新一次RMD候选模式集MC.首先计算17个编号为偶数的角度模式，并根据其HC值，由小到大排序，选取前N个模式组成RMD候选模式集MC.其次，检测当前PU是否存在左、上、左上、右上邻近PU，以及其所属上一深度的PU.若这些PU存在并已完成预测，则对当前PU计算它们所采用的模式.然后，比较MC内前两个模式M₁、M₂的HC值，若满足式(3)，则分别计算这两个模式的两个未被检测过的邻近编号模式，否则只计算M₁的两个邻近编号模式. α的值本文取1.2.例如若M₁=4，则要检测编号为3与5的两个模式；若M₁=9，则要检测编号为7与11的两个模式.最后计算编号为0和1的两个非角度模式.经此修改，RMD实际遍历计算的模式个数通常只有21到23个，仅占全部模式个数的60%.该部分算法全流程如图 5所示.此算法的思路在于舍弃原本全搜索得到最佳候选集的方式，改为由疏到密的隔点抽样，逐步逼近最佳的候选模式.其中对邻近PU以及上层PU模式的检测，是基于它们与当前PU之间存在一定的空域相似性，有较大可能选取相同或相近的最佳模式.

$ {\rm{H}}{{\rm{C}}_2} < \alpha \cdot {\rm{H}}{{\rm{C}}_1} $

(3)

2.1.2 提前确定最佳模式

在进入第一次RDO之前，检测当前PU的左、上邻近PU以及所属上一深度的PU是否都存在，并且它们所选的最佳模式是否都与当前PU的RMD最佳候选模式相同.若相同，再检测左上、右上邻近PU.只要这两者中存在一个，并且其所选的最佳模式与当前PU的RMD最佳候选模式相同，则确定此最佳候选模式为最佳模式，不再对其他候选模式进行RDO计算；否则进行像素梯度检测，再次筛选候选模式集MC.

2.1.3 像素梯度检测

每进入一个新的LCU，则对该LCU内每个像素计算其梯度方向.定义像素P_{x, y}的右边和下边邻近像素分别为P_{x+1, y}和P_{x, y+1}.若P_{x, y}是LCU的右或下边界像素，则令其右或下邻近像素与其相等.像素梯度方向为

$ {\rm{Angle}} = \frac{{{P_{x,y}} - {P_{x,y + 1}}}}{{{P_{x,y}} - {P_{x + 1,y}}}}. $

(4)

定义与Angle相对应的角度模式编号如表 1所示.在该LCU内的各个深度的PU，都可统计该PU内采用某个模式的像素个数.对候选模式集MC第3个及之后的候选模式检测，定义当前PU中采用编号为i(2≤i≤33)的角度候选模式的像素个数为n_i，当前PU的宽度为W，高度为H.若满足式(5)^[8]，则可认为在全部33个角度模式中，模式i成为最佳模式的概率远低于平均水平，可以在MC中舍弃模式i.

$ \left\{ \begin{array}{l} {n_i} = 0,\\ {n_{i - 1}} \le W \cdot H/33,\\ {n_{i + 1}} \le W \cdot H/33. \end{array} \right. $

(5)

若当前PU尺寸大于或等于16×16，则对所有角度模式按其所包含的像素个数由多到少进行排序，选取前N个模式作为比较集MC₀与MC中第3个以及之后的角度候选模式逐个对照.若某个候选模式不在MC₀之中，则舍弃该候选模式.由于尺寸为8×8和4×4的PU所含的像素个数较少，各n_i相差不明显，该排序比较算法的准确性会因而下降，故不适用于它们.

2.1.4 子PU残差比较

一个PU的SATD，是对其划分为多个8×8或4×4块分别计算得到的SATD的总和.因此，在计算某个非最大深度PU的SATD时，可记录它所包含的4个子PU各自的SATD，记为subSATD_i.并定义这4个子PU残差值之间的总相对误差率为subR.

$ {\rm{Average}} = \frac{{\sum\limits_{i = 1}^4 {{\rm{subSAT}}{{\rm{D}}_i}} }}{4}. $

(6)

$ {\rm{sub}}R = \frac{{\sum\limits_{i = 1}^4 {\left( {{\rm{subSAT}}{{\rm{D}}_i} - {\rm{Average}}} \right)} }}{{4 \cdot {\rm{Average}}}}. $

(7)

PU的帧内预测都是基于左、上邻近PU的像素得到的，因此在PU内部，越靠右、下方向的像素，其预测误差越大，这种情况在PU包含丰富的纹理信息时愈加明显.从式(6)~(7)可知，对某个非最大深度PU来说，可根据其subR的大小体现它包含的纹理信息的丰富程度，并由此推测PU是否需要TU划分乃至下一深度的PU划分.

从实验数据可知，4×4的PU必定不需TU划分；8×8的PU有极大几率不需TU划分，因此可以跳过RDO2；尺寸在16×16及以上的PU是否需TU划分的随机性较大，不应跳过RDO2.本文提出的算法是：4×4、8×8、64×64的PU跳过RDO2；尺寸在16×16及以上的PU最佳模式若满足式(8)则跳过RDO2. β的值本文取0.3.

$ {\rm{sub}}R < \beta . $

(8)

2.2 减少遍历计算的层次深度

若当前PU是深度为d(d＞0)的第k(1≤k≤4)个PU，在完成该PU的帧内预测后，可检测其上一深度的subR_d-1值，若不满足式(9), 则按照原本的预测流程继续；否则可进一步比较率失真代价.定义上一深度的PU的率失真代价为RC_d-1，其4个子PU采用最佳模式下的STAD值分别为subSATD_{d-1, i}，当前深度k个PU的率失真代价分别为RC_{d, i}.若满足式(12)^[12]，则可认为当前CU的图像比较平缓，不需更大深度的划分，即跳过之后的遍历计算流程，提前确定d-1为当前LCU的最佳划分深度. γ的值本文取0.1.

$ {\rm{sub}}{R_{d - 1}} < \gamma . $

(9)

$ {\rm{Th1}} = {\rm{min}}\left( {\frac{4}{k},\frac{{\sum\limits_{i = 1}^4 {{\rm{subSAT}}{{\rm{D}}_{d - 1,i}}} }}{{\sum\limits_{i = 1}^k {{\rm{subSAT}}{{\rm{D}}_{d - 1,i}}} }}} \right). $

(10)

$ {\rm{Th2}} = \left\{ \begin{array}{l} 1.6,k = 1;\\ 1.4,k = 2;\\ 1.2,k = 3;\\ 1,k = 4. \end{array} \right. $

(11)

$ \sum\limits_{i = 1}^k {{\rm{R}}{{\rm{C}}_{d,i}}} \cdot {\rm{Th1}} > {\rm{R}}{{\rm{C}}_{d - 1}} \cdot {\rm{Th2}}{\rm{.}} $

(12)

3 实验结果与分析 3.1 实验条件

本文所提出的算法已在HEVC标准测试模型HM13.0实现，编码采用HM13.0附带的All Intra和Random Access的Main Profile标准配置文件.对27个HEVC通用测试序列各以22、27、32、37共4个QP进行编码.实验环境是：主频3.3GHz的IntelCore i3-2120 CPU，4Gbyte内存的Windows 7 (64位)系统，代码编译工具使用VS2010.

3.2 实验结果分析

本文所提出的算法与原HM13.0之间的性能比较由Bjontegaard^[16]的算法体现.BDRate是经由RD曲线拟合得到的，在相同亮度PSNR下，本文算法相比HM13.0所增加的比特率百分比.同理，BDPSNR是在相同比特率下，本文算法与HM13.0的亮度PSNR差值.ATSP(Average Time Saving Percent)是本文算法相比HM13.0所减少的编码时间百分比.

$ \begin{array}{l} \ \ \ \ \ \ \ {\rm{ATSP}} = \\ \frac{1}{4}\sum\limits_{i = 1}^4 {\frac{{{\rm{Tim}}{{\rm{e}}_{{\rm{HM13}}.0}}\left( {{\rm{Q}}{{\rm{P}}_i}} \right) - {\rm{Tim}}{{\rm{e}}_{{\rm{proposed}}}}\left( {{\rm{Q}}{{\rm{P}}_i}} \right)}}{{{\rm{Tim}}{{\rm{e}}_{{\rm{HM13}}.0}}\left( {{\rm{Q}}{{\rm{P}}_i}} \right)}}} \cdot 100\% . \end{array} $

(13)

测试结果如表 2所示.在All Intra配置下，从Class A到Class E皆是由摄像机拍摄的常规视频序列，它们的峰值信噪比平均下降0.045dB，比特率增加0.858%.Class F为特殊用途视频序列，峰值信噪比平均下降0.270dB，比特率增加2.346%.全部视频序列的峰值信噪比总体下降0.079dB，比特率增加1.079%，编码时间减少53.67%.在Random Access配置下，从Class A到Class E视频序列的峰值信噪比平均下降0.026dB，比特率增加0.795%.Class F的峰值信噪比平均下降0.182dB，比特率增加1.832%.全部视频序列的峰值信噪比总体下降0.049dB，比特率增加0.949%，编码时间减少12.97%.由此可见，本文所提出的算法能大幅减少帧内编码时间，而所造成的总体图像质量下降和码率增加非常轻微.

4 结语

本文介绍了新一代视频编码标准HEVC的帧内预测技术，以及一些前人关于HEVC快速帧内预测算法的研究成果，并提出了新的快速帧内预测算法.该算法以像素梯度统计和子PU残差比较作为参考要素，在帧内预测时，舍弃了某些模式和深度的遍历计算.在与HM13.0的实验结果比较中，本文所提出的算法大幅减少了帧内编码时间，而因此只有轻微的图像质量下降和比特率增加.