基于H.264预测模式选择的并行算法

卞凤杰，齐金鹏，刘树娟，李林鸽

(东华大学 信息工程与科学技术学院，上海 201600)

基于H.264预测模式选择的并行算法

卞凤杰，齐金鹏，刘树娟，李林鸽

(东华大学 信息工程与科学技术学院，上海 201600)

针对H.264编码器提出了一种基于线程级别的并行化算法，用于快速RDO模式决策，可以有效地解决H.264编码器帧内模式决策和帧间模式决策之间的数据依赖性，开发出线性级别的并行快速模式决策算法。此外，该方法可以容易地映射到硬件架构，同时采用改进的比特率估计算法和低复杂性的整数失真估计方法。实验结果表明，文中算法减少了总编码时间，降低了运动估计ME的计算开销，同时保持较低的PSNR损失和比特率增加。

H.264/AVC；视频编码；帧内预测；帧间预测；并行；多核处理器

H.264/AVC的多种预测模式和帧内、帧间预测方法的不同组合，明显地改善了编码效率[1]。同时，繁琐的模式选择加重计算负荷,许多H.264/AVC的快速模式决策算法被提出。目前，国内对于快速模式决策方法主要有以下几种。第一种是通过边界方向检测，只对最可能的几种模式进行预测[2-3]。第二种是根据时域和空域活动指标限制搜索模式[4]。还有一种是制定类决策指标，划分宏块类，优化了已有的模式决策算法[5]。由于多核处理器的普及以及半导体技术的飞速发展，基于硬件的快速并行帧间模决策算法被研究人员提出，采用多核处理器的硬件结构，同时获得每种模式的编码成本，加快模式决策过程。

本文对已有帧间模式决策滑流算法和跳跃算法进行改进，可以有效解决H.264编码器帧内模式决策和帧间模式决策数据之间的依赖性依赖性，开发出线性级别的并行快速模式决策的算法。在保证没有过大的峰值噪比PSNR(Peak Signal to Noise Ratio)值损失和比特率增加的前提下减少总编码时间。基于JM18.6的实验结果表明，本文提出的算法可以在保证可以忽略的PSNR损失和比特率增加的前提下，编码器编码时间为仅为原标准编码器的70%。

1 问题提出

1.1 复杂的RDO模式决策过程

H.264/AVC编码器的编码性能取决于预测模式的选择[6]。对视频图像进行编码，要同时保证解码后的低失真和编码输出的比特流尽可能小。H.264/AVC主要采用两种模型，对各预测模式计算相应的代价函数值，取代价函数值最小的模式作为当前块的最佳预测模式。

在运动估计部分，运动矢量(MV)和选择参考帧(REF) 是基于绝对误差和(SAD)的复杂度代价函数计算模型Jmotion

Jmotion=SAD+λmotion·R(MV,REF)

(1)

(2)

其中，SAD是当前块实际像素值与预测像素值差的绝对值之和；Jmotion是拉格朗日乘数；R是对该预测模式下编码后比特率估计值；QP是每个宏块的量化参数。

在RDO(Rate Distortion Optimization)模式决策部分，采取基于拉格朗日函数率失真优化的高复杂度代价函数计算模型

Jmode=SSD+λmode·R(m|QP)

(3)

其中，R(m|QP)表示在对应模式下的熵编码后所输出的比特流大小；SSD指当前块与重建块的绝对误差平方的和；R(i，j)是重建块中的像素值；O(i，j)表示当前块像素值编码器将遍历计算4×4或16×16子块所有模式下的代价值，选择最小的Jmode|min，其对应模式就是该子块帧间最佳预测模式。

(4)

RDO代价函数值Jmode的计算过程非常复杂。H.264/AVC采用了多个编码模式，编码模式的确定过程消耗较大的整体计算。为确定每种模式的编码成本，需要多次进行运动估计和熵编码的运算。运动估计和模式决策RDO的计算占H.264编码器整个计算的约80%[7]。

1.2 宏块帧间编码的概率分析

在实际编码过程中，P帧或B帧的帧内编码时只有一小部分的宏块被编码。所以当某宏块的最佳编码方式不是帧内模式之一时，帧内Jmode计算可以省略，总编码时间可以大幅缩短。很多文献提出不同的算法以降低帧内模式决策的复杂性[7-9]。

本文的研究重点在于，当P或B帧中某个宏块的最佳编码方式不是帧内模式之一时，设计出省略大部分帧内模式的Jmode计算，同时保证不造成PSNR损失和比特率增加的算法。

如上文所述，RDO帧内模式决策占据H.264编码器编码的大部分计算。如果开发出线程级并行算法来使RDO模式决策实现并行，可以大幅减少总编码时间。

2 快速模式决策并行算法

本文提出模式决策的快速并行算法，算法的基本思想是让编码过程中某些步骤在多核处理器的不同内核实现并行，但由于存在数据依赖关系，从算法角度只能实现两个步骤(即RDO帧内模式决策和运动估计的部分计算)的并行，但是，实验验证相比之前的顺序流程编码过程，还是可以节省至少30%的编码时间。

本文算法改进主要有两部分，其中主要是采用帧间模式决策滑流算法(Slipstream，SL)和SKIP算法,此外还对其他算法进行优化，使得本算法性能更优，以下简称本文算法为PL算法。

图1 PL工作流程图

2.1 帧间模式决策滑流算法和SKIP算法

本文提出帧间模式决策滑流算法(SL算法)来去除数据依赖性，主要并行部分RDO模式决策过程，改善运动估计模块的计算性能。帧间模式决策滑流算法把RDO帧内模式决策过程移动到ROD帧内模式决策和运动估计可以并行化的滑流位置来提高运动估计模块的计算性能[10-12]。

采取帧间模式决策SKIP算法移除一部分计算开销大的RDO帧内模式决策计算。这意味着运动估计和RDO帧内模式决策通过SL算法并行执行了，大多数RDO帧内模式决策可以提前完成以及最佳帧内模式可以在RDO帧间模式决策过程之前确定。

2.2 其他算法

为降低计算复杂度, 本文还采用一种改进的比特率估计算法。该算法应用于熵编码和RDO过程，无需查表,可以更好地适用于CAVLC(Context Adaptive Variable Length Coding)编码过程，减少了模式决策过程的计算量[13]。另外，本文采用J.M.Moon提出的基于整数计算的低复杂度率失真估计算法[14]。这两种算法节省了一部分编码时间，却带来了峰值信噪比损失，但可以忽略。

2.3 PL算法实现

图1显示了基于线程级别的并行化PL算法流程图。在本文提出的算法中,RDO帧内模式决策和运动估计的部分计算可以在多核处理器上同时进行(即S1和S2)。S2应该在S5和S6之间进行，采用SL算法，可以使S1和S2同时在多核处理器上的不同内核中同时进行。

首先S1：实现了运动估计。该步骤通过比较帧间模式16×16, 16×8， 8×16的Jmotion值大小为每个宏块选择最佳REF(Reference Frame，参考帧)和MV(Motion Vector，运动估计)。S2: RDO帧内模式决策，基于SL算法计算每个块对于I4×4和I16×16帧内模式的RD代价函数值，预先选择最好的帧内模式。如图1所示，S1和S2在多核处理器的不同内核上并行执行。

RD_CostI4×4=min(Jmode(I4×4_Mode|λmode))I4×4_Mode∈{mode0～8}

(5)

RD_CostI6×6=min(Jmode(I6×6_Mode|λmode))I6×6_Mode∈{mode0～3}

(6)

最佳帧内模式为MINm(RD_CostM),其中，M∈{I6×16,I4×4}。

接着S3：比较P8×8每个宏块的Jmotion值大小为选择最佳REF和MV，同时通过比较帧间模式8×8,8×4,4×8的Jmode值，选择出最佳帧间模式。S4为SKIP模式确定最佳MV。

下面是模式决策过程，包括S5、S6、S7、S8、S9，共5个步骤，其中S2本来应在S5和S6之间进行，通过采用SL算法，可以使S1和S2同时在多核处理器上的不同内核中同时进行。S5:通过计算帧间模式的Jmode确定RD值

RD_CostM=min(M|λmode)

(7)

最佳帧间模式为MINm(RD_CostM)，M∈{SKIP,16×16，16×8，8×16，P8×8mode}。接下来，S6比较最佳帧内模式RD值和最佳帧间模式RD值，如果最佳帧间模式RD值小于最佳帧内RD值,跳转到S7。反之，跳转到S8。 其中，S7为确定帧间模式的最佳模式，跳转到第9步；S9为最佳帧间模式恢复配置，执行S2的结果作为帧内编码模式。S8确定帧内模式的最佳模式。最后，S10确定宏块熵编码的最佳模式(CABAC或CAVLC )。

3 实验结果

JVT发布的H.264标准软件JM18.6[15]，在PC平台上的Visual C++2013结合使用便携式支持共享内存并行系统的多处理器编程处理接口OpenMP进行仿真实验。

JM的实验参数设置为：(1)选择基本档次编码；(2)选择CABAC熵编码；(3)量化参数为36；(4)levelIDC设为40(可支持分辨率2 k×1 k、每秒最大参考帧为62 914 560帧)；(5)帧数为100、参考帧为2、帧率30帧内/s。选择的测试序列是QCIF格式的视频序列news、foreman、aklye、trevor和CIF格式的news、foreman、slient、stefan。

从表1和表2可以看出无论是QCIF还是CIF，本文提出的PL算法相较于JVT最新的H.264最新标准软件JM19.0能节省约30%的编码时间。运动估计模块平均加速4.57%。对于输出码流，本文算法平均码流增加率的平均值为1.625，可以忽略不计。平均峰值信噪比损失值为0.012 5，对于QCIF和CIF序列上的平均峰值信噪比损失值分别为0.019和0.006。

如图2所示是QCIF视频格式中的视频序列Foreman在编码前后的视频截图，其中，左图是编码前的视频截图，右图是编码后的视频截图，编码后的视频图像和编码前的相比，几乎无区别，仔细观察可以发现人物的帽子边沿有些模糊，即在颜色的过渡上，本算法存在明显缺陷。但对整个视频图像的质量不会造成明显影响。本算法在一些对细节或边沿要求不高的场景中有较大的应用价值。

实验结果说明,本文算法减少了总编码时间，降低了运动估计ME的计算开销。同时保证PSNR损失和比特率增加，在可忽略不计的范围内。

图2 编码前后的图像比较

测试序列PSNR/dBBit-rate/kbit·s-1ME时间/sEncoding时间/sNewsJM19.030.91226.71146.57184.401PL30.90427.93744.53457.701比较结果-0。0080.7744.3731.63%续表1ForemanJM19.030.63134.42948.12985.813PL30.61536.43045.59459.055比较结果-0.0162.0015.56031.18%AklyeJM19.032.63110.44946.52280.364PL32.60211.22744.63656.522比较结果-0.0290.7784.26021.50%TrevorJM19.031.31244.71347.77484.778PL31.28847.57346.51759.602比较结果-0.0241.8042.70029.70%

表2 本文算法针对视频序列CIF的性能

4 结束语

本文提出的PL算法包括帧间模式决策滑流算法(SL算法)和帧间模式决策SKIP算法，同时还采用比特率估计算法和低复杂性的整数失真估计方法，可以减少总编码时间，降低计算开销。提出SL模式决策算法，实现运动估计和RDO帧内模式决策可以并行执行，SKIP算法去除了RDO帧内模式决策的大多数不必要计算。此外，SL算法通过从共享二级高速缓存数据预先获取，可以加快运动估计的计算过程。本文算法可以减少编码时间，同时保证PSNR损失和比特率增加在可忽略的范围内。基于JM19.0的实验结果表明，该算法减少了总平均编码时间29.18%，同时的平均PSNR值仅为0.012 5，平均码流增加率平均值为1.625，可忽略不计。

[1] Joch A,Kossentini F,Schwarz H,et al.Performancecomparison of video coding standards using Lagrangian coder control[C].UT,USA:Proceedings of International Conference on Image Processing, 2002.

[2] 何宜宝,陈再秀.利用边缘方向检测实现H.264 帧内预测编码的新算法[J].西安电子科技大学学报,2009,36(6):1126-1131.

[3] 高蒿,陈耀武.基于纹理区域分割的SVC 快速模式模式决策算法[J].计算机工程,2011,37(22):256-249.

[4] 吴笛,卿粼波,何小海.基于MVMW 的H.264/AVC自适应快速帧间模式决策算法[J].系统工程与电子技术,2013,35(6):1330-1335.

[5] 吴笛,卿粼波,何小海.基于MVMW 的H.264/AVC自适应快速帧间模式决策算法[J].系统工程与电子技术,2013,35(6):1330-1335.

[6] Joch A,Kossentini F,Schwarz H,et al.Performance comparison of video coding standards using Lagrangian coder control[C].SA,USA:Proceedings of International Conference on Image Processing,2002.

[7] Wang Dayong,Sun Yu.A fast mode decision algorithm applied in medium-grain quality scalable video coding[J].Journal of Visual Communication and Image Representation,2016,34(1):78-88.

[8] La B,Eorn M,Choe Y.Fast mode decision for intra prediction in H.264/AVC encoder[J].Journal of ICIP,2007,5(9):321-324.

[9] Pan Feng.Fast mode decision algorithm for intra prediction in H.264/AVC video coding[J].IEEE Transaction on Circuits System for Video Technology,2005,15(7):784-791.

[10] Chen Jianwen, John Villasenor, Yun He, et al.Parallel fast inter mode decision for H.264/AVC encoding[J].Journal of Visual Communication and Image Representation,2013,24(8):1443-1449.

[11] Tian G.An efficient fast mode decision algorithm for H.264/AVC intra prediction[J].Congress on Image and Signal Processing,2008,1(5):597-605.

[12] Sundaramoorthy K.Slipstream processors: improving both performance and fault tolerance[C].Shanghai:ASPLOS-IX,2000.

[13] Moon J M,Kim J H.A new low-complexity integer distortion estimation method for H.264/AVC encoder[J].IEEE Transactions on Circuits and Systems for Video Technology,2010,20(2):207-212.

[14] Po L M,Guo K.Transform-domain fast sum of the squared difference computation for H.264/AVC rate-distortion optimization[J].IEEE Transactions on Circuits and Systems for Video Technology,2007,17 (6):765-773.

[15] JVT.H.264/AVC reference software JM19.0available online[EB/OL].(2015-02-01)[2016-02-14]http:∥iphome.hhi.de/suehring/tml/download.

The Parallel Fast Prediction Mode Selection Algorithm Based on H.264

BIAN Fengjie ,QI Jinpeng, LIU Shujuan, LI Linge

(School of Information Engineering and Science Technology,Donghua University, Shanghai 201600,China)

A new fast RDO inter frame mode decision algorithm based on thread level parallelization is proposed in this paper. It can effectively solve the data dependence between H.264 Intra Mode Decision and the inter frame mode decision, the fast RDO inter frame mode decision algorithm based on thread level parallelization can be proposed. In addition, the proposed method can be easily mapped to hardware architectures which use multi-core processors. The paper also uses the improved bit rate estimation algorithm and a low complexity integer distortion estimation method. Experimental results show that the algorithm in this paper reduces the total encoding time, and reduces the computational overhead of motion estimation ME, while maintaining very low PSNR loss and bit rate increment.

H.264/AVC video coding;frame prediction;inter-frame prediction; parallel; multi-core processors

2016- 58- 24

国家自然科学基金(61104154)；上海市自然科学基金(16ZR1401300；16ZR1401200)

卞凤杰(1990-)，女，硕士研究生。研究方向：数字图像处理。齐金鹏(1977-)，男，博士，副教授，硕士生导师。研究方向：数字图像处理。刘树娟(1991-),女,硕士研究生。研究方向：数字图像处理。

10.16180/j.cnki.issn1007-7820.2017.04.021

TN919.81

A

1007-7820(2017)04-083-05