基于HEVC的快速帧间预测算法

李静敏，杨　静

(上海海事大学 信息工程学院，上海　201306)



基于HEVC的快速帧间预测算法

李静敏，杨静

(上海海事大学 信息工程学院，上海201306)

针对HEVC中PU划分模式和帧间运动模式的选择引起的高复杂度，提出一种快速帧间预测算法。首先，判断图像的运动状态和纹理复杂度，根据当前图像的时空域相关性及图像内容的特点，减少PU划分模式。然后，根据运动剧烈程度对当前PU运动模式预判，从而不需要遍历所有的运动模式。实验结果表明，在视频重建质量基本相当的前提下，改进后的算法编码时间与参考算法相比节省30%～60%左右。

HEVC；帧间预测；PU划分模式；运动模式；时空域相关性；运动状态；纹理复杂度

HEVC[1]作为最新的视频压缩标准，沿袭了H.264基于块的混合编码框架，但其去除了H.264标准的“宏块”概念，针对每个模块重新定义了编码单元(Code Unit，CU)、预测单元(Prediction Unit，PU)、变换单元(Transform Unit，TU)等概念[2]。块划分模式的增多以及运动模式(Merge_Mode、Inter_Mode)的详细划分，在提高视频编码效率的同时也造成计算复杂度的上升。

针对HEVC中帧间预测的新特点引起的高复杂度，很多学者做了大量的研究，如已经被HM收入，并作为PU划分模式判决的快速算法：1)提前终止算法(Early_CU)[3]利用MODE_SKIP终止该CU后续四叉树划分及模式判决。2)早期跳出算法[4](Early_SKIP)，如果当前CU的PU划分为2N×2N，预测模式为Inter_Mode(帧间预测模式)，且CBF和MVD均为零，则认为当前的PU划分模式为该CU的最佳模式，不再遍历剩余的PU划分模式，直接进行下步的四叉树分割或者子CU的模式判别。3)快速CBF算法(CBF_Fast)[5]，即如果CU的预测模式为Inter_Mode ，它所对应的预测残差不包含非零的变换系数，则跳过该CU的其他预测模式，当前PU划分模式为当前CU的最优模式。但这3个算法利用的是当前CU的特殊情况。

针对CU的一般性情况，Rhee等[6]利用不同深度间PU划分模式的相关性，预测当前PU的划分模式；Tian 充分利用全零残差块终止PU划分[7]；马祥等[8]利用CU不同深度的相关性和同一深度相邻空域的相关性，减少PU模式遍历；李元等[9]和刘娟等[10]利用图像时域的相关性，根据前后两帧的CU面积特征，提前结束PU模式遍历。

上述算法从各个方面来减少PU划分模式抉择的复杂度，考虑了视频的帧间相关性，但都没有与当前块空域相关性结合，且没有涉及运动模式(Merge_Mode，Inter_Mode)的判决。综合以上分析，本文根据图像的运动特性和纹理复杂度，针对PU模式判别过程和运动模式预判两方面进行了改进，以减少帧间预测复杂度。

1　本文算法

帧间预测编码作为视频压缩编码的一个重要模块，利用图像帧间相关性，根据相邻时域已编码块来预测当前块的信息，去除视频的时域冗余，达到压缩目的。为了降低HEVC中帧间预测编码复杂度，本文提出了一种快速算法。首先，判断图像的运动特征及纹理复杂性。然后，利用时空域的相关性，分别对PU模式选择和运动模式判别进行快速模式选择和模式预判。

1.1图像运动特征与纹理复杂度的分析

图像的运动剧烈程度对图像编码有很大的影响，静止或者运动平缓的图像，相邻两帧间的相似性很高，当前块的编码信息可以参考或者拷贝相邻时域的相应块的有图像信息。运动剧烈的图像，帧间相关性相对较弱，对于视频的帧间压缩效率有所影响。本文利用相邻帧相应位置的CU的MV来判断当前块的运动特征。首先定义一个全局变量来保存相邻帧相应位置已编码块的MV，根据式(1)求出当前CU的平均MVave

(1)

式中：2N×2N是当前CU的大小；MVx(i，j)和MVy(i，j)分别表示当前CU在(i，j)处的运动矢量的X和Y分量。根据多次实验观察得到合适的门限值THR0=3，当MVave>THR0时，表示当前块运动较为剧烈；当MVave≤THR0时，表示当前CU的运动缓慢或者静止。

对于运动剧烈的图像，图像帧间的相关性较弱。本文结合了空域相关性，对图形的纹理信息进行分类，将CU分为纹理平坦区域和纹理复杂区域。CU区域的纹理较为平坦时，对于去除图像空间冗余有很好的效果。目前已经有很多方法检测图像的纹理复杂度，如应用高斯马尔科夫随机场来进行纹理复杂度的分类[11]，此方法较为有效，但其计算复杂度也很大，本文不考虑此算法。利用Sobel算子计算当前CU的梯度值[12]，通过梯度值来衡量该区域的纹理复杂度。本文使用当前CU与空域相邻块的绝对差值和的平均值VSAD，来确定该CU的纹理复杂度。VSAD的计算如下

(2)

式中：2N表示当前CU的尺寸；P(i，j)表示当前CU区域内(i，j)点的像素值；p′(i，j)表示相邻CU内(i，j)点的像素值。当VSAD的值小于阈值THR1时，则认为当前CU区域稳定平坦；反之，则认为当前CU纹理复杂。阈值THR1是经过大量实验得到，取THR1=4.5。

1.2快速PU划分模式选择算法

PU是进行预测编码的基本单元，最小的PU划分模式为4×4。HEVC的PU划分模式包括4种对称的(2N×2N，2N×N，N×2N，N×N)和4种非对称的运动划分模式(Asymmetric Motion Partition，AMP)(2N×UN，2N×DN，LN×2N，RN×2N)。HEVC标准的PU划分模式判别，就是采用基于拉格朗日的率失真优化计算每种模式的率失真代价，选择代价最小者为最优PU划分模式。但不是所有的模式都需要进行遍历。为了降低PU划分模式选择的复杂度，本文根据图像的内容特性将其PU模式分为三类：上下结构I1={2N×N，2N×UN，2N×DN}、左右结构I2={N×2N，LN×2N，RN×2N}、不分块或者均匀分块I3={2N×2N，N×N}。

考虑到文献[9]中统计的相邻两帧间的PU模式相同概率较高，该快速PU划分模式选择算法先考虑时域相关性再结合空域相关性，具体步骤如下。

根据1.1节中的运动特征分析，判断当前编码块的运动剧烈程度。

若MVave≤THR0，判定当前编码块运动较为平缓或静止。考虑到此时相邻两帧间有较大的相关性，统计相邻帧相应块PU划分模式(PUcol)。

如果PUcol划分模式属于I1集合，则当前编码块遍历I1集合中的PU划分模式，而为了保证视频编码的性能，2N×2N的PU划分模式也需要考虑，其他模式则不需要再遍历。

如果PUcol划分模式属于I2集合，则当前编码块只需要遍历I2集合中的PU划分模式和2N×2N。

如果PUcol划分模式属于I3集合，当前编码块只需遍历I3集合中的PU划分模式。

当MVave>THR1时，当前块运动较为剧烈，如果仍然参考相邻帧相应位置PU划分模式，可能会对视频的质量造成一定的损失。为了减少视频质量的损失，当前块编码块运动剧烈时，本文根据1.1节中的图像纹理复杂度的分析，判断当前编码块的纹理复杂度。

若VSAD≤THR1，判定当前编码块纹理平坦，统计当前编码块的空域相邻块的PU划分模式(PUNeR)。

如果PUNeR划分模式属于I1集合，则当前CU只遍历I1集合中的PU划分模式和2N×2N。如果PUNeR划分模式为I2集合，则当前CU只需要遍历I2集合中的PU模式和2N×2N。如果PUNeR划分模式属于I3集合，当前PU只需遍历I3集合中的PU划分模式。

若MVave>THR1且VSAD>THR1，当前编码块模运动剧烈且纹理复杂，需要遍历所有的PU划分模式以得到最优PU划分模式。

改进的快速PU划分模式选择算法流程图如图1示。

图1　快速PU划分模式选择算法流程图

1.3快速运动模式预判

计算每种PU划分模式的率失真代价是为PU选择最优的帧间预测参数，如参考图像的列表、参考图像索引、运动矢量和加权值等。由于HEVC引入了 Merge模式和AMVP技术，使得每种PU模式都需要遍历两种运动模式Merge_Mode和Inter_Mode，从两位种模式中选择率失真代价最小的为最优运动模式，提高了编码效率的同时也增加了编码时间。

但两种运动模式有很大的区别，Merge_Mode可以从时间和空间相邻块中得到运动信息，根据率失真优化计算候选列表中的候选项的率失真代价以选择最优候选块，只需要最优候选块的索引信息即可。对于帧间变化较少或者运动静止的图像区域可以有效地降低图像的计算复杂度和编码比特数。Inter_Mode需要搜索不同的运动参数组合，根据率失真优化计算各种组合的率失真代价，选择RDCost最小的为最优Inter_Mode。Inter_Mode类似于Merge_Mode，都需要建立候选列表，但与之不同的是其不需要5个候选项只需要2个即可。Inter_Mode只利用很少的候选项是因为需要执行运动估计来计算当前块的运动矢量残差，通过传递残差来实现图像的编码。Inter_Mode对于运动剧烈或者纹理复杂的图像，能够最小失真地重建图像，但计算复杂度又有所增加。

为了降低运动模式抉择的计算复杂度，本文根据运动模式的特性与图像的运动复杂度，预判帧间预测的运动模式，具体步骤如下：

1)考虑到PU划分模式为2N×2N时，SKIP模式类似于Merge_Mode。此时对于当前编码块的运动模式，不进行预判。

2)再次利用1.1节中运动特征的分析，判断当前编码块的运动剧烈程度。

3)当MVave≤THR0时，当前编码块运动较为平缓或静止，而Merge模式对于帧间变化较少或者运动静止的图像区域只需要很少的比特，且能很好地将当前块运动信息传递到解码端，所以，此时使用Merge_Mode来搜索当前块的运动信息。

4)当MVave>THR0时，当前编码块运动较为剧烈，若采用Merge_Mode，会导致视频质量的损失，使用Inter_Mode来搜索当前块的运动信息，在保证了当前块图像质量的基础上又不需要遍历Merge_Mode。

运动模式预判算法的流程图如图2所示。

图2　运动模式预判流程图

2　结果分析

本文提出的快速帧间预测算法在编码器HM10.0仿真实验，实验平台为CPU 4.30 GHz、Intel Core i7、内存4 Gbyte、操作系统为Windows 7的64位计算机，运行环境是Microsoft Visual Studio 2010，编码结构为IPPP。实验结果如表1～5所示，其中P表示本文所提出的快速PU模式选择算法，C为文献[10]基于时域相关性的快速PU选择算法，L即为快速PU模式选择与运动模式预判相结合的快速帧间预测算法。

表1本文快速算法与参考算法和HM算法对比结果1

序列算法Bitrate/(kbit·s-1)ΔB/%PSNR/dBΔP/dBTime/sΔT/%BClassParkSceneHM1619.0592—34.3312—15326.047—P与HM差值—0.28—-0.01—-43.48P与C差值—-0.05—0.01—4.88L与HM差值—0.07—0.02—-55.74L与C差值—-0.25—0.04—-17.86BasketballDriveHM2863.776—36.3958—18573.315—P与HM差值—0.19—-0.01—-37.57P与C差值—-0.02—0.02—3.82L与HM差值—0.52—-0.03—-55.44L与C差值—0.31—-0.01—-25.90

表2本文快速算法与参考算法和HM算法对比结果2

序列算法Bitrate/(kbit·s-1)ΔB/%PSNR/dBΔP/dBTime/sΔT/%CClassParkSceneHM113.8176—39.0295—2027.428—P与HM差值—0.94—-0.04—-38.66P与C差值—1.17—0.04—4.45L与HM差值—0.69—-0.06—-54.51L与C差值—0.92—0.01—-22.55BasketballDriveHM2431.872—30.6077—3907.89—P与HM差值—0.61—-0.02—-16.41P与C差值—0.27—0.03—6.27L与HM差值—1.67—-0.05—-42.15L与C差值—1.32—0—-22.30

表3本文快速算法与参考算法和HM算法对比结果3

序列算法Bitrate/(kbit·s-1)ΔB/%PSNR/dBΔP/dBTime/sΔT/%DClassParkSceneHM367.776—31.6735—1270.124—P与HM差值—1.06—-0.04—-10.95P与C差值—-0.94—0.03—6.28L与HM差值—1.45—-0.08—-29.40L与C差值—-0.57—0—-15.74BasketballDriveHM446.544—31.3487—950.857—P与HM差值—2.04—-0.03—-20.14P与C差值—0.49—0.01—1.63L与HM差值—2.09—-0.08—-40.05L与C差值—0.54—-0.04—-23.71

表4本文快速算法与参考算法和HM算法对比结果4

序列算法Bitrate/(kbit·s-1)ΔB/%PSNR/dBΔP/dBTime/sΔT/%EClassParkSceneHM540.9312—37.7616—4295.491—P与HM差值—0.53—-0.02—-48.51P与C差值—-1.71—0.06—3.14L与HM差值—0.91—-0.01—-56.21L与C差值—-1.33—0.64—-12.29BasketballDriveHM437.184—38.7191—4448.543—P与HM差值—0.76—-0.01—-48.86P与C差值—-1.07—0.02—-23.61L与HM差值—1.32—-0.05—-51.87L与C差值—-0.52—-0.01—-28.11

表5本文快速算法与参考算法和HM算法对比结果5

序列算法Bitrate/(kbit·s-1)ΔB/%PSNR/dBΔP/dBTime/sΔT/%FClassParkSceneHM1445.7648—35.7467—7083.064—P与HM差值—1.04—-0.04—-30.04P与C差值—-0.34—0.01—2.06L与HM差值—1.59—-0.08—-46.60L与C差值—0.21—-0.03—-22.10BasketballDriveHM227.4368—42.7508—5493.914—P与HM差值—-0.09—-0.04—-49.19P与C差值—-0.20—-0.05—4.44L与HM差值—0.50—0—-69.45L与C差值—0.39—-0.01—-37.21

从表1中可以看出，本文中的快速PU划分模式选择算法与HM编码器相比较，其时间可以节省平均25%左右，同时PSNR减少0.03 dB左右，并有0.5%左右的码率增加。与参考文献算法[10]相比较，大部分的图像的率失真性能明显较好，尤其是针对运动较为剧烈而纹理较为平坦的图像。但个别视频因为考虑了空域相关性，率失真性能略有下降。

加入运动模式预判算法的快速帧间预测联合算法与文献算法[10]相比，其时间可进一步减少15%～25%，且视频的率失真效果基本相当。与HM编码器相比，其时间可以节省69%，同时视频的质量损失可忽略不计。

3　结论

本文主要针对帧间预测的PU模式抉择和运动模式进行了分析和改进。提出的快速帧间预测联合算法，根据图像的运动状态来减少需要遍历的PU模式和对运动模式的预判。同时对于运动剧烈的图像，又利用图像纹理复杂度减少了PU划分模式遍历。仿真结果表明：本文提出的快速帧间预测算法大幅度减少了编码时间，且图像质量损失可忽略不计。

[1]JCT-VC.JCTVC-L1004，High efficiency video coding(HEVC)text specification draft 10[S].2013.

[2]WIEGAND T，OHM J R，SULLIVAN G J，et al. Special section on the joint call for proposals on High Efficiency Video Coding(HEVC)standardization[J]. IEEE transactions on circuits and systems for video technology， 2010， 20(12)：1661-1666.

[3]GWEON R H， LEE Y L，LIM J Y. Early termination of CU encoding to reduce HEVC complexity[EB/OL]. [2016-01-09]. http：//phenix.int-evry.fr/jct/index.php.

[4]YANG J Y，KIM J W，WON K H，et al. Early SKIP detection for HEVC[EB/OL]. [2016-01-09]. http：//phenix. intevry. fr/jct/index.php.

[5]CHOI K，PARK S H，JANG E S. Coding tree pruning based CU early termination[EB/OL]. [2016-01-09]. http：//phenix. intevry.fr/jct/index.php.

[6]RHEE C E，LEE H J. Early decision of prediction direction with hierarchical correlation for HEVC compression [J].IEICE transactions on information and systems，2013(96)：972-975.

[7]TIAN G，GOTO S. An optimization scheme for quadtree-struture prediction and residual encoding in HEVC[C]//Proc. IEEE Asia Pacific Conference on Circuits and Systems(APCCAS).[S.l.]：IEEE，2012：547-550.

[8]马祥.基于宏块模式相关性的深度帧内跳过编码[J].华南理工大学学报，2013，41(8)：28-33.

[9]李元，何小海，钟国韵，等.一种基于时域相关性的高性能视频编码快连速帧间预测单元模式判决算法[J].电子与信息学报，2013，10(35)：2365-2370.

[10]刘娟，钟国韵，王蕾，等.基于时域相关性的快速HEVC帧间模式判决方法[J].电视技术，2014，38(13)：1-5.

[11]UCHIYAMA T，MUKAWAN，KANEKO H. Estimation of homogeneous regions for segmentation of textured images[J].IEEE transactions on information and systems，2000(3)：7084-7084.

[12]WU D，WU S，LIM K P. Block inter mode decision for fast encoding of H.264[J].IEEE transactions on information and systems，2004，3(3)：181.

责任编辑：时雯

Fast inter-frame prediction algorithm based on HEVC

LI Jingmin，YANG Jing

(CollegeofInformationandEngineering，ShanghaiMaritimeUniversity，Shanghai201306，China)

In order to solve the high complexity which result from the choice of PU mode and frame movement patterns which is the new technology in HEVC，a fast inter frame Prediction algorithm is proposed in this paper. Firstly，it is determine the movement of images and texture complexity，and reduce PU mode based on the current image in spatial domain correlation and characteristics of image content. Then，according to the characteristics of inter-frame motion mode，it is predict the current PU Motion mode by motion state，and it is not need traverse all of the patterns of motion. Experimental results show that the modified algorithm saves encoding time 30%～60% and video quality loss is negligible.

HEVC； inter-frame prediction； prediction unit (PU) mode； motion mode； correlation of temporal and spatial； motion state； texture complexity

TN919.81

ADOI：10.16280/j.videoe.2016.07.001

国家自然科学基金项目(61401270)

2016-02-21

文献引用格式：李静敏，杨静.基于HEVC的快速帧间预测算法[J].电视技术，2016，40(7)：1-5.

LI J M，YANG J.Fast inter-frame prediction algorithm based on HEVC[J].Video engineering，2016,40(7)：1-5.