利用运动信息及率失真代价的HEVC帧间快速算法

罗志伟，冯 桂

华侨大学 信息科学与工程学院，福建 厦门 361021

利用运动信息及率失真代价的HEVC帧间快速算法

罗志伟，冯 桂

华侨大学 信息科学与工程学院，福建 厦门 361021

针对高效视频编码（HEVC）帧间预测过程所引入较高的复杂度，分别提出提前决策skip模式，编码单元（CU）提前终止分割以及变换单元（TU）提前终止分割。首先，根据自然视频序列多采用skip模式，利用当前块和空间相邻块的已编码信息提前决定skip模式；其次，为了避免编码不必要的深度，利用先前已编码块的率失真代价（rdcost）决策CU提前终止分割；最后，利用当前预测残差块的纹理复杂度决策TU的提前终止分割。实验结果表明，提出的算法最终可以节省编码时间43.78%，同时造成bjøntegaard delta bit rate（BDBR）的损失为1.675%。通过实验数据的比较，在对视频质量的影响忽略不计的情况下，能够很大程度上减少复杂度。

高效视频编码；已编码信息；率失真代价；残差块

1 引言

高效视频编码的提出有利于满足人们对如今高清视频（2K和4K）的需求。相比于前一代视频编码标准H.264做了大量改进与创新。它首先提出了三种单元类型：编码单元（Coding Unit，CU），预测单元（Prediction Unit，PU），变换单元（Transform Unit，TU），支持的单元尺寸大小从64×64至4×4。在帧间预测方面，HEVC引入更多的PU分割类型，即4种对称分割和4种非对称分割；在帧内预测方面，HEVC支持35种方向预测模式，这些创新使得HEVC与H.264相比，在视频感知质量相同的情况下，减少的码率达到50%[1]。国内外进行帧内帧间优化的文献有文献[2]至文献[13]。文献[2]用LBP算子决策帧内方向预测模式，计算不同方向的图像纹理的变化，提前在35种预测模式中选出几种预测模式。文献[3]用变换差绝对值之和模拟块的纹理复杂程度，减少率失真候选模式。文献[5]使用Sobel算子对最大编码单元（Largest Coding Unit，LCU）计算边缘值，若边缘值小于提出的阈值则提前决策编码单元的深度。文献[6]根据时间邻近块的最优深度预测当前块的最优深度；利用经过Inter_2N×2N后得出的残差预测块提前决定skip模式；文献[7]构建一个CU内最大灰度值与最小灰度值之差的灰度直方图，利用直方图的值决定CU是否分割，再用Sobel算子计算一个CU的垂直方向梯度值与水平方向梯度值，利用这两个梯度值提前决策PU模式。文献[10-11]采用数据挖掘进行帧间快速算法研究。上述文献的研究一定程度上减少了编码器的复杂度，但HEVC现存的复杂度依旧十分巨大，不利于工业应用，科研工作者们需要研究性能更加优秀的算法来改善编码器。本文获取CU的空域邻近块的信息提前决策出skip模式，采集先前已编码块的率失真代价决策CU是否分割，同时针对TU分割的优化，模拟残差块的纹理复杂程度决策TU是否分割。

图1 HEVC四叉树分割及各深度下的PU模式

2HEVC帧间预测过程

HEVC采用四叉树的结构将CU和TU分割成更小的单元进行预测编码，如图1。它支持的CU尺寸大小为64×64至8×8，其预测编码过程如下：先计算LCU的率失真代价，此时CU大小为64×64，深度为0；将LCU划分成四个子块，分别计算这四个块的rdcost，CU大小为32×32，深度为1；再将深度为1的四个CU分别划分成16个子CU，计算这16个CU的rdcost，CU大小为16×16，深度为2；最后把深度为2的16个CU分割成64个子CU，CU大小为 8×8，深度为3，计算64个CU的rdcost。接着对深度为3的4个CU的rdcost之和同其深度为2的父CU的rdcost作比较，若父CU的率失真代价较大，则选择最佳分割尺寸为8×8，若不是，继续将深度为2的CU同其父CU作比较，直到得出最优的分割尺寸。TU的四叉树分割编码过程和CU相同，但TU支持的尺寸为32×32至4×4，且当前TU最大尺寸不能超过所在的CU尺寸。

HEVC对当前深度的CU进行PU模式选择见图1。先进行skip/merge模式预测，再进行4种对称模式预测，即Inter_2N×2N，Inter_N×2N，Inter_2N×N，Inter_N×N，再进行4种非对称模式预测（AMP），即Inter_2N×NU，Inter_2N×NB，Inter_NL×2N，Inter_NR×2N，其中AMP模式只有在CU深度不为3的情况下才启用，而Inter_N×N只有在CU深度等于3时才启用。计算所有的PU模式的rdcost，根据最小的rdcost作为最优预测模式。

3 skip模式提前决策

一般情况下，自然视频中处于静止或运动平缓区域的内容居多，这些区域选择skip模式为最优预测模式的概率很高，若能提前选择出skip模式，略过剩余的PU模式预测，能够很大程度上降低复杂度。为了证明该假设，选择6个测试序列，QP设为27，32，37，编码帧数为50，统计不同序列在不同QP下选择skip模式的概率，如表1所示。

表1 不同QP下选择skip模式为最优预测模式的概率%

从表1中可以看出，选择skip模式的概率较高，在静止画面较多的序列中拥有极高的概率，且概率随着QP的增加而增加，所以使用合适的算法提前选择出skip模式对降低复杂度有很大的意义。

一般来说，处于静止或运动缓慢区域的运动矢量（Motion Vector，Mv）都很小，它们往往会选择较大尺寸的分割方法，如skip模式。根据文献[13]，当前CU和空间邻近CU具有较高的相关性。可以利用空间已编码块的信息进行当前CU的模式选择。为了衡量当前CU的运动情况，定义了一个运动矢量长度len(Mv)和运动矢量最大值maxlen(Mv)。

在式（1）中，|Mvx|表示水平方向运动矢量的绝对值，|Mvy|表示垂直方向运动矢量的绝对值。在式（2）中，Mvcur表示当前CU的 Mv，Mvleft表示左邻近CU的Mv，Mvabove表示上邻近CU的Mv。

按照式（2）来判断，若maxlen(Mv)小于提出的某个阈值，就能判断当前CU是否处于静止或运动缓慢区域。提出的算法1如下所示：

步骤1先进行skip模式和Inter_2N×2N模式预测，根据式（1）计算当前CU和左邻近CU以及上邻近CU的运动矢量长度。

步骤2根据式（2）得出最大的运动矢量长度maxlength(Mv)。

步骤3若当前CU的最优PU模式为skip模式且maxlength(Mv)小于提出的某个阈值，跳过剩余的PU模式预测，若不满足，对剩余PU模式依次进行运动估计。

下面选取6个典型序列验证算法1的有效性，QP设为27，32，37，编码帧数为50，统计当前CU满足算法1的条件下，选择skip模式为最优模式的概率，实验如表2所示。

表2 skip模式提前选择的命中率%

如表2所示，本文提出的skip模式提前选择的命中率均在97%以上。

4 CU划分提前剪枝

先前HEVC帧间预测介绍CU的分割结构是根据最小率失真代价准则，直观上，若一个CU采用较大尺寸的CU进行编码（如64×64和32×32），往往该CU的rdcost比较小，反之则rdcost比较大。所以本文提出一个假设：一个CU的分割与不分割与其计算出来的rdcost呈现出一种规律性，可以找出这种规律来提前终止CU的分割。为了检验该假设，选择序列BasketballDrill，QP设为32，编码帧数为50，统计CU分割与不分割的rdcost分布情况。

从图2的实验结果看来，不分割CU的rdcost往往集中在较小值附近，并呈现一种峰值，而分割CU的rdcost分布比较散乱，没有什么规律性可言，故可以找出一种阈值来提前决定CU是否分割。

图2CU分割与不分割的rdcost取值分布图

CU在当前深度下进行PU模式的预测是根据最小率失真代价（rate-distortion cost）准则，选择最小的rdcost作为其最优PU模式。当选择不同的PU分割时，计算出来的率失真代价的值相差很大。图3是选择序列BasketballDrill，在QP为32，编码帧数为50的情况下统计出来的，它反映当前CU选择不同PU分割模式的率失真代价分布状况。从图中可以看出，选择skip模式和2N×2N模式的rdcost值偏小的比率比较高，在rdcost值偏大的比率比较低，而AMP模式呈现相反的分布状况。可以利用先前已编码块的rdcost值来提前终止分割。

图3 不同模式下rdcost取值分布图

根据上述统计分析，在CU进行完当前深度的PU分割模式预测后，设计四种CU：（1）当前深度的CU选择最佳模式为skip模式；（2）当前深度的CU选择最佳模式为Inter_2N×2N；（3）当前深度的CU选择最佳模式为Inter_N×2N 或Inter_2N×N ；（4）当前深度的CU选择最佳模式为AMP。提出的算法2如下所示：

步骤1进行当前深度下所有PU分割模式预测，判断深度在0，1，2的情况下的CU属于上述介绍的哪一类，并将其率失真代价的值存储到J(i,d)中（i表示CU的划分类型，i=1，2，3，4，d 是深度）

步骤2判断当前CU的J(i,d)是否小于提出的阈值Thr(i,d)，若小于，则提前终止分割；反之则继续分割。

Thr(i,d)是根据一帧内先前已编码CUi,d{CUi,d处于深度 d 下，归为类型 i（i=1，2，3，4）}的rdcost的平均值。

统计算法2的命中率，统计结果如表3所示。“—”表示满足的个数很少，基本不影响编码器的性能。

表3 CU分割提前终止的命中率

从表3可以看到，算法2的命中率在大部分情况下的命中率很高，且随着QP的上升而增加。

5 TU划分提前剪枝

在运动估计后，编码器会生成残差信息，它由运动补偿生成的预测块与原始块之差得到。残差信息也反映了编码器的预测精准度，若残差块的值较小，说明编码器生成的预测块接近于原始块，预测精度较高，同时反映出该区域的运动情况比较缓慢，在进行TU分割编码时往往采用较大尺寸的TU分割模式。反之若残差块的值偏大，反映出运动情况比较剧烈，TU往往会分割成更小尺寸的分割模式。本文利用残差块的纹理复杂度来判断该区域的运动情况，提出一种硬阈值法来提前终止TU分割。

经过运动补偿后，编码器会生成当前深度的残差块，将残差块分割成16个残差子块，如图4所示。残差子块尺寸大小分别为8×8，4×4，2×2，对应的残差块深度分别为1，2，3。

本文采用式（3）的偏离平均值的绝对差之和（Sum of Absolute Difference over Average，SADA）来衡量残差块纹理信息。

图4 残差块分割

K是残差子块的宽度和高度，resi_pixel(x,y)是残差子块在(x,y)位置的像素值，pix_avei,j是第(i,j)个残差子块的像素平均值，SADAi,j是第(i,j)个残差子块偏离平均值的绝对差之和。

本文通过这16残差子块的SADA和 pix_ave判定残差信息的大小，提出的算法3如下所示：

步骤1获取编码器经过运动补偿后得出的残差信息，通过式（3）计算出16个残差子块的 SADA和pix_ave。

步骤2若16个残差子块中至多只有一个残差子块的SADA不小于式（4）所示的阈值ThrSADA，且所有残差子块的 pix_ave均小于给出的阈值Thrave，则提前终止当前TU继续划分为更小TU。

其中depth是当前TU所在的深度，ct是设定的常数。而找出常数ct和阈值Thrave是算法3的关键，本文后面将通过实验来选择合适的ct和Thrave。

6 算法流程

集合第3章、第4章和第5章的三个算法得出总体算法流程（图5），如下所示：

步骤1读入一个CU后进行skip模式运动估计以及Inter_2N×2N运动估计，获取当前CU的运动矢量和左邻近块的运动矢量以及上邻近块的运动矢量。

步骤2判断算法1的条件是否满足，若满足则跳过剩余模式的运动估计，转至步骤4；否则，转至步骤3。

步骤3计算剩余的帧间PU模式，转至步骤4。

步骤4执行帧内预测，判断CU属于哪一深度、哪一类型，将其存储至J(i,d)，转至步骤5。

步骤5执行算法2，判断是否满足算法2的条件，若满足，转至步骤6；若不满足，转至步骤7。

步骤6则终止当前CU的继续分割，转至步骤8。

图5 总体算法流程框图

步骤7判断当前深度是否为3，若是，转至步骤8；若不是，将CU划分成四个子CU，深度加1，转至步骤1。

步骤8结束CU的编码。

在计算每种帧间PU模式的时候，需要进行残差编码。

步骤1获取残差信息，编码TU，转至步骤2。

步骤2若TU深度不为4，则计算16个残差子块的SADA和 pix_ave，转至步骤3；否则，转至步骤5。

步骤3若满足算法3给出的条件，则终止TU继续分割，转至步骤5；否则，转至步骤4。

步骤4 TU继续分割成四个子TU，TU的深度加1，转至步骤5。

步骤5结束TU的编码。

7 实验结果与分析

本实验采用HM16.0测试模型，测试硬件为英特尔酷睿2四核Q9400@2.66 GHz的CPU，可用内存3.21 GB，Window 7旗舰版的计算机，使用Visual Studio 2010编译器。对HEVC官方规定Class A-E的18个序列进行测试[14]，序列统一设定为50帧，量化参数QP取22，27，

32，37。 使 用 Bjøntegaard Delta Bit Rate（BD-BR）和 Bjøntegaard Delta Peak Signal-to-Noise Rate（BDPSNR）[15]衡量率失真性能，ΔT衡量复杂度的减少程度。BD-BR是在同等客观质量条件下，两种方法的码率的节省情况。BD-PSNR是在给定的同等码率下，两种方法的Y-PSNR的差异。ΔT的定义如式（5）所示：

其中，TimeHM16.0(QPi)是原始算法HM16.0的编码时间，Timepro(QPi)是本文提出的算法的编码时间。

为了选择算法3中合适的ct和Thrave以达到最佳的编码效果，单独对算法3进行了实验测试，选择序列Class C和Class D，编码帧数为50，其实验结果如表4所示。

表4 不同的ct和Thrave对编码器的影响

从表4可以看出若选择较大的ct和Thrave，所减少的时间也增多，但BDBR和BDPSNR的损失也大，若选择较小的ct和Thrave，虽然BDBR和BDPSNR的损失较小，但是减少的时间过少，所以选择ct为5，Thrave为8。

表5是本文总体算法的实验结果，采用低延迟P帧（Low-Delay P，LDP）配置文件，即使用前一参考帧进行运动估计，本文算法降低的时间多达43.78%，同时带来的平均Y-BDPSNR的降低仅有-0.06 dB，BDBR的增加也只有1.67%。选择文献[7]与本文算法进行比较，从表5中可以看出本文算法与文献[7]相比，无论是编码时间的减少量，还是率失真性能都取得了更好的效果，相比于文献[7]达到的编码时间减少量约为8.58%，同时降低了0.22%的BD-BR，提升了0.1 dB的BD-PSNR。从表中可以进一步看出，对于Class E这样的平稳序列，文中算法基本不会影响其率失真性能的损失，且时间的减少量达到70%以上。图6给出了本文算法与原始算法HM16.0应用在序列 BasketballDrive（class B，1 920×1 080）与序列PartyScene（class C，832×480）下的率失真曲线图。这两个序列在本文算法下编码分别能获得较好的率失真性能以及较差的率失真性能。从图6中可曲线几乎重合，即在不同的比特率上，本文算法与原始算法能够获得几乎相同的峰值信噪比。

表5 在配置文件LDP下的实验结果

图6 本文算法与原始算法HM16.0编码的率失真曲线

8 结束语

通过获取当前CU和邻近CU的运动矢量来模拟运动剧烈程度，提前选择出skip模式；利用先前已编码块的率失真代价提前终止CU的分割；估计残差块纹理的平稳性来提前终止TU的分割。实验结果表明：文中算法可以获得与HM16.0算法几乎相同的率失真性能，同时减少的编码时间为43.78%。

[1]Sullivan G J，Ohm J，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]Lee J H，Jang K S，Kim B G，et al.Fast intra mode decision algorithm based on local binary patterns in High Efficiency Video Coding（HEVC）[C]//IEEE International Conference on Consumer Electronics，Las Vegas，NV，2015：270-272.

[3]Gwon D，Choi H，Youn J M.HEVC fast intra mode decision based on edge and SATD cost[C]//Conference on Multimediaamp;Broadcasting，Kuta，2015：1-5.

[4]Liu X，Liu Y，Wang P，et al.An adaptive mode decision algorithm based on video texture characteristics for HEVC intra prediction[J].IEEE Transactions on Circuitsamp;Systems for Video Technology，2016：1.

[5]Taeyoung N，Sangkwon A，Kiwon Y.A probabilistic-based CU size pre-determination method for parallel processing ofHEVC encoders[C]//IEEE InternationalConference on Consumer Electronics，Las Vegas，NV，2015：327-330.

[6]Wenjun Z，Takao O，Tian S.Hierarchical structure-based fast mode decision for H.265/HEVC[J].IEEE Transactions on Circuitsamp;Systems for Video Technology，2015，25（10）：1651-1664.

[7]Huang X，Zhang Q，Zhao X，et al.Fast inter prediction mode decision algorithm for HEVC[J].Signal Image and Video Processing，2016：1-8.

[8]Shen L，Zhang Z，Zhang X，et al.Fast TU size decision algorithm for HEVC encoders using Fast TU size decision algorithm for HEVC encoders using Bayesian theorem detection[J].SignalProcessing Image Communication，2015，32：121-128.

[9]Zhang Y，Kwong S，Wang X.Machine learning-based coding unit depth decisions for flexible complexity allocation in high efficiency video coding[J].IEEE Transactions on Image Processing，2015，24（7）：2225-2238.

[10]Correa G，Assuncao P，Agostini L，et al.Fast HEVC encoding decisions using data mining[J].IEEE Transactions on Circuitsamp;Systems for Video Technology，2015，25（4）：660-673.

[11]Correa G，Assuncao P，Agostini L，et al.Four-step algorithm for early termination in HEVC inter-frame prediction based on decision trees[C]//Visual Communicationsamp;Image Processing Conference，Valletta，2014：65-68.

[12]Hu Q，Zhang X，Shi Z.Neyman-pearson-based early mode decision for HEVC encoding[J].IEEE Transactions on Multimedia，2016，18（3）：379-391.

[13]Shen L，Liu Z，Zhang X，et al.An effective CU size decision method for HEVC encoders[J].IEEE Transactions on Multimedia，2013，15（2）：465-470.

[14]Bossen F.Common test conditions and software reference configurations[C]//JCTVC-L1100，Joint Collaborative Team on Video Coding（JCT-VC） of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11 12th Meeting，Geneva，2013：1-4.

[15]Bjontegaard G.Calculation of average PSNR differences between RD-curves[C]//ITU-Telecommunications Standardization Sector Study Group 16 Question 6 Video Coding Experts Group（VCEG），VCEG-M33，Austin，US，2001：1-4.

LUO Zhiwei,FENG Gui

College of Information Science and Engineering,Huaqiao University,Xiamen,Fujian 361021,China

HEVC Inter fast algorithm use of motion information and rate-distortion cost.Computer Engineering and Applications,2017,53（21）：167-173.

High Efficient Video Coding（HEVC）of inter-frame prediction process is introduced for a high complexity.This paper proposes early skip mode decision,Coding Unit（CU）early termination partition and Transform Unit（TU）early termination partition.First,natural video sequence has a high probability of using skip mode,using current block and encoded information blocks of spatially adjacent early decide on skip mode.Meanwhile,in order to avoid unnecessary coding depth,the rate-distortion cost of the previously encoded block is used to decide on CU early termination partition.Last,TU early termination partition is decided by using texture complexity of the current prediction residual block.Experimental results show the proposed algorithm can save encode time 43.78%,at the same time 1.67%of losses of bjøntegaard delta bit rate（BDBR）.By comparing the experimental data under the condition that the quality of video is negligible,can largely reduce the complexity of encoder.

High Efficient Video Coding（HEVC）;encoded information;rate-distortion cost;residual block

A

TN919.81

10.3778/j.issn.1002-8331.1605-0026

福建省自然科学基金（No.2016J01306）。

罗志伟（1992—），男，硕士研究生，主研方向为视频编码中的算法优化，E-mail：798916526@qq.com；冯桂（1960—），女，博士，教授，主研方向为信号与信息处理、通信系统信息安全理论、多媒体通信、计算机视觉、模式识别与影像理解等。

2016-05-05

2016-08-15

1002-8331（2017）21-0167-07

CNKI网络优先出版：2016-09-29,http://www.cnki.net/kcms/detail/11.2127.TP.20160929.1650.030.html