卞鳳杰，齊金鵬，劉樹(shù)娟，李林鴿

(東華大學(xué) 信息工程與科學(xué)技術(shù)學(xué)院，上海 201600)

基于H.264預(yù)測(cè)模式選擇的并行算法

卞鳳杰，齊金鵬，劉樹(shù)娟，李林鴿

(東華大學(xué) 信息工程與科學(xué)技術(shù)學(xué)院，上海 201600)

針對(duì)H.264編碼器提出了一種基于線(xiàn)程級(jí)別的并行化算法，用于快速RDO模式?jīng)Q策，可以有效地解決H.264編碼器幀內(nèi)模式?jīng)Q策和幀間模式?jīng)Q策之間的數(shù)據(jù)依賴(lài)性，開(kāi)發(fā)出線(xiàn)性級(jí)別的并行快速模式?jīng)Q策算法。此外，該方法可以容易地映射到硬件架構(gòu)，同時(shí)采用改進(jìn)的比特率估計(jì)算法和低復(fù)雜性的整數(shù)失真估計(jì)方法。實(shí)驗(yàn)結(jié)果表明，文中算法減少了總編碼時(shí)間，降低了運(yùn)動(dòng)估計(jì)ME的計(jì)算開(kāi)銷(xiāo)，同時(shí)保持較低的PSNR損失和比特率增加。

H.264/AVC；視頻編碼；幀內(nèi)預(yù)測(cè)；幀間預(yù)測(cè)；并行；多核處理器

H.264/AVC的多種預(yù)測(cè)模式和幀內(nèi)、幀間預(yù)測(cè)方法的不同組合，明顯地改善了編碼效率[1]。同時(shí)，繁瑣的模式選擇加重計(jì)算負(fù)荷,許多H.264/AVC的快速模式?jīng)Q策算法被提出。目前，國(guó)內(nèi)對(duì)于快速模式?jīng)Q策方法主要有以下幾種。第一種是通過(guò)邊界方向檢測(cè)，只對(duì)最可能的幾種模式進(jìn)行預(yù)測(cè)[2-3]。第二種是根據(jù)時(shí)域和空域活動(dòng)指標(biāo)限制搜索模式[4]。還有一種是制定類(lèi)決策指標(biāo)，劃分宏塊類(lèi)，優(yōu)化了已有的模式?jīng)Q策算法[5]。由于多核處理器的普及以及半導(dǎo)體技術(shù)的飛速發(fā)展，基于硬件的快速并行幀間模決策算法被研究人員提出，采用多核處理器的硬件結(jié)構(gòu)，同時(shí)獲得每種模式的編碼成本，加快模式?jīng)Q策過(guò)程。

本文對(duì)已有幀間模式?jīng)Q策滑流算法和跳躍算法進(jìn)行改進(jìn)，可以有效解決H.264編碼器幀內(nèi)模式?jīng)Q策和幀間模式?jīng)Q策數(shù)據(jù)之間的依賴(lài)性依賴(lài)性，開(kāi)發(fā)出線(xiàn)性級(jí)別的并行快速模式?jīng)Q策的算法。在保證沒(méi)有過(guò)大的峰值噪比PSNR(Peak Signal to Noise Ratio)值損失和比特率增加的前提下減少總編碼時(shí)間?；贘M18.6的實(shí)驗(yàn)結(jié)果表明，本文提出的算法可以在保證可以忽略的PSNR損失和比特率增加的前提下，編碼器編碼時(shí)間為僅為原標(biāo)準(zhǔn)編碼器的70%。

1 問(wèn)題提出

1.1 復(fù)雜的RDO模式?jīng)Q策過(guò)程

H.264/AVC編碼器的編碼性能取決于預(yù)測(cè)模式的選擇[6]。對(duì)視頻圖像進(jìn)行編碼，要同時(shí)保證解碼后的低失真和編碼輸出的比特流盡可能小。H.264/AVC主要采用兩種模型，對(duì)各預(yù)測(cè)模式計(jì)算相應(yīng)的代價(jià)函數(shù)值，取代價(jià)函數(shù)值最小的模式作為當(dāng)前塊的最佳預(yù)測(cè)模式。

在運(yùn)動(dòng)估計(jì)部分，運(yùn)動(dòng)矢量(MV)和選擇參考幀(REF) 是基于絕對(duì)誤差和(SAD)的復(fù)雜度代價(jià)函數(shù)計(jì)算模型Jmotion

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

(1)

(2)

其中，SAD是當(dāng)前塊實(shí)際像素值與預(yù)測(cè)像素值差的絕對(duì)值之和；Jmotion是拉格朗日乘數(shù)；R是對(duì)該預(yù)測(cè)模式下編碼后比特率估計(jì)值；QP是每個(gè)宏塊的量化參數(shù)。

在RDO(Rate Distortion Optimization)模式?jīng)Q策部分，采取基于拉格朗日函數(shù)率失真優(yōu)化的高復(fù)雜度代價(jià)函數(shù)計(jì)算模型

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

(3)

其中，R(m|QP)表示在對(duì)應(yīng)模式下的熵編碼后所輸出的比特流大??；SSD指當(dāng)前塊與重建塊的絕對(duì)誤差平方的和；R(i，j)是重建塊中的像素值；O(i，j)表示當(dāng)前塊像素值編碼器將遍歷計(jì)算4×4或16×16子塊所有模式下的代價(jià)值，選擇最小的Jmode|min，其對(duì)應(yīng)模式就是該子塊幀間最佳預(yù)測(cè)模式。

(4)

RDO代價(jià)函數(shù)值Jmode的計(jì)算過(guò)程非常復(fù)雜。H.264/AVC采用了多個(gè)編碼模式，編碼模式的確定過(guò)程消耗較大的整體計(jì)算。為確定每種模式的編碼成本，需要多次進(jìn)行運(yùn)動(dòng)估計(jì)和熵編碼的運(yùn)算。運(yùn)動(dòng)估計(jì)和模式?jīng)Q策RDO的計(jì)算占H.264編碼器整個(gè)計(jì)算的約80%[7]。

1.2 宏塊幀間編碼的概率分析

在實(shí)際編碼過(guò)程中，P幀或B幀的幀內(nèi)編碼時(shí)只有一小部分的宏塊被編碼。所以當(dāng)某宏塊的最佳編碼方式不是幀內(nèi)模式之一時(shí)，幀內(nèi)Jmode計(jì)算可以省略，總編碼時(shí)間可以大幅縮短。很多文獻(xiàn)提出不同的算法以降低幀內(nèi)模式?jīng)Q策的復(fù)雜性[7-9]。

本文的研究重點(diǎn)在于，當(dāng)P或B幀中某個(gè)宏塊的最佳編碼方式不是幀內(nèi)模式之一時(shí)，設(shè)計(jì)出省略大部分幀內(nèi)模式的Jmode計(jì)算，同時(shí)保證不造成PSNR損失和比特率增加的算法。

如上文所述，RDO幀內(nèi)模式?jīng)Q策占據(jù)H.264編碼器編碼的大部分計(jì)算。如果開(kāi)發(fā)出線(xiàn)程級(jí)并行算法來(lái)使RDO模式?jīng)Q策實(shí)現(xiàn)并行，可以大幅減少總編碼時(shí)間。

2 快速模式?jīng)Q策并行算法

本文提出模式?jīng)Q策的快速并行算法，算法的基本思想是讓編碼過(guò)程中某些步驟在多核處理器的不同內(nèi)核實(shí)現(xiàn)并行，但由于存在數(shù)據(jù)依賴(lài)關(guān)系，從算法角度只能實(shí)現(xiàn)兩個(gè)步驟(即RDO幀內(nèi)模式?jīng)Q策和運(yùn)動(dòng)估計(jì)的部分計(jì)算)的并行，但是，實(shí)驗(yàn)驗(yàn)證相比之前的順序流程編碼過(guò)程，還是可以節(jié)省至少30%的編碼時(shí)間。

本文算法改進(jìn)主要有兩部分，其中主要是采用幀間模式?jīng)Q策滑流算法(Slipstream，SL)和SKIP算法,此外還對(duì)其他算法進(jìn)行優(yōu)化，使得本算法性能更優(yōu)，以下簡(jiǎn)稱(chēng)本文算法為PL算法。

圖1 PL工作流程圖

2.1 幀間模式?jīng)Q策滑流算法和SKIP算法

本文提出幀間模式?jīng)Q策滑流算法(SL算法)來(lái)去除數(shù)據(jù)依賴(lài)性，主要并行部分RDO模式?jīng)Q策過(guò)程，改善運(yùn)動(dòng)估計(jì)模塊的計(jì)算性能。幀間模式?jīng)Q策滑流算法把RDO幀內(nèi)模式?jīng)Q策過(guò)程移動(dòng)到ROD幀內(nèi)模式?jīng)Q策和運(yùn)動(dòng)估計(jì)可以并行化的滑流位置來(lái)提高運(yùn)動(dòng)估計(jì)模塊的計(jì)算性能[10-12]。

采取幀間模式?jīng)Q策SKIP算法移除一部分計(jì)算開(kāi)銷(xiāo)大的RDO幀內(nèi)模式?jīng)Q策計(jì)算。這意味著運(yùn)動(dòng)估計(jì)和RDO幀內(nèi)模式?jīng)Q策通過(guò)SL算法并行執(zhí)行了，大多數(shù)RDO幀內(nèi)模式?jīng)Q策可以提前完成以及最佳幀內(nèi)模式可以在RDO幀間模式?jīng)Q策過(guò)程之前確定。

2.2 其他算法

為降低計(jì)算復(fù)雜度, 本文還采用一種改進(jìn)的比特率估計(jì)算法。該算法應(yīng)用于熵編碼和RDO過(guò)程，無(wú)需查表,可以更好地適用于CAVLC(Context Adaptive Variable Length Coding)編碼過(guò)程，減少了模式?jīng)Q策過(guò)程的計(jì)算量[13]。另外，本文采用J.M.Moon提出的基于整數(shù)計(jì)算的低復(fù)雜度率失真估計(jì)算法[14]。這兩種算法節(jié)省了一部分編碼時(shí)間，卻帶來(lái)了峰值信噪比損失，但可以忽略。

2.3 PL算法實(shí)現(xiàn)

圖1顯示了基于線(xiàn)程級(jí)別的并行化PL算法流程圖。在本文提出的算法中,RDO幀內(nèi)模式?jīng)Q策和運(yùn)動(dòng)估計(jì)的部分計(jì)算可以在多核處理器上同時(shí)進(jìn)行(即S1和S2)。S2應(yīng)該在S5和S6之間進(jìn)行，采用SL算法，可以使S1和S2同時(shí)在多核處理器上的不同內(nèi)核中同時(shí)進(jìn)行。

首先S1：實(shí)現(xiàn)了運(yùn)動(dòng)估計(jì)。該步驟通過(guò)比較幀間模式16×16, 16×8， 8×16的Jmotion值大小為每個(gè)宏塊選擇最佳REF(Reference Frame，參考幀)和MV(Motion Vector，運(yùn)動(dòng)估計(jì))。S2: RDO幀內(nèi)模式?jīng)Q策，基于SL算法計(jì)算每個(gè)塊對(duì)于I4×4和I16×16幀內(nèi)模式的RD代價(jià)函數(shù)值，預(yù)先選擇最好的幀內(nèi)模式。如圖1所示，S1和S2在多核處理器的不同內(nèi)核上并行執(zhí)行。

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)

最佳幀內(nèi)模式為MINm(RD_CostM),其中，M∈{I6×16,I4×4}。

接著S3：比較P8×8每個(gè)宏塊的Jmotion值大小為選擇最佳REF和MV，同時(shí)通過(guò)比較幀間模式8×8,8×4,4×8的Jmode值，選擇出最佳幀間模式。S4為SKIP模式確定最佳MV。

下面是模式?jīng)Q策過(guò)程，包括S5、S6、S7、S8、S9，共5個(gè)步驟，其中S2本來(lái)應(yīng)在S5和S6之間進(jìn)行，通過(guò)采用SL算法，可以使S1和S2同時(shí)在多核處理器上的不同內(nèi)核中同時(shí)進(jìn)行。S5:通過(guò)計(jì)算幀間模式的Jmode確定RD值

RD_CostM=min(M|λmode)

(7)

最佳幀間模式為MINm(RD_CostM)，M∈{SKIP,16×16，16×8，8×16，P8×8mode}。接下來(lái)，S6比較最佳幀內(nèi)模式RD值和最佳幀間模式RD值，如果最佳幀間模式RD值小于最佳幀內(nèi)RD值,跳轉(zhuǎn)到S7。反之，跳轉(zhuǎn)到S8。 其中，S7為確定幀間模式的最佳模式，跳轉(zhuǎn)到第9步；S9為最佳幀間模式恢復(fù)配置，執(zhí)行S2的結(jié)果作為幀內(nèi)編碼模式。S8確定幀內(nèi)模式的最佳模式。最后，S10確定宏塊熵編碼的最佳模式(CABAC或CAVLC )。

3 實(shí)驗(yàn)結(jié)果

JVT發(fā)布的H.264標(biāo)準(zhǔn)軟件JM18.6[15]，在PC平臺(tái)上的Visual C++2013結(jié)合使用便攜式支持共享內(nèi)存并行系統(tǒng)的多處理器編程處理接口OpenMP進(jìn)行仿真實(shí)驗(yàn)。

JM的實(shí)驗(yàn)參數(shù)設(shè)置為：(1)選擇基本檔次編碼；(2)選擇CABAC熵編碼；(3)量化參數(shù)為36；(4)levelIDC設(shè)為40(可支持分辨率2 k×1 k、每秒最大參考幀為62 914 560幀)；(5)幀數(shù)為100、參考幀為2、幀率30幀內(nèi)/s。選擇的測(cè)試序列是QCIF格式的視頻序列news、foreman、aklye、trevor和CIF格式的news、foreman、slient、stefan。

從表1和表2可以看出無(wú)論是QCIF還是CIF，本文提出的PL算法相較于JVT最新的H.264最新標(biāo)準(zhǔn)軟件JM19.0能節(jié)省約30%的編碼時(shí)間。運(yùn)動(dòng)估計(jì)模塊平均加速4.57%。對(duì)于輸出碼流，本文算法平均碼流增加率的平均值為1.625，可以忽略不計(jì)。平均峰值信噪比損失值為0.012 5，對(duì)于QCIF和CIF序列上的平均峰值信噪比損失值分別為0.019和0.006。

如圖2所示是QCIF視頻格式中的視頻序列Foreman在編碼前后的視頻截圖，其中，左圖是編碼前的視頻截圖，右圖是編碼后的視頻截圖，編碼后的視頻圖像和編碼前的相比，幾乎無(wú)區(qū)別，仔細(xì)觀(guān)察可以發(fā)現(xiàn)人物的帽子邊沿有些模糊，即在顏色的過(guò)渡上，本算法存在明顯缺陷。但對(duì)整個(gè)視頻圖像的質(zhì)量不會(huì)造成明顯影響。本算法在一些對(duì)細(xì)節(jié)或邊沿要求不高的場(chǎng)景中有較大的應(yīng)用價(jià)值。

實(shí)驗(yàn)結(jié)果說(shuō)明,本文算法減少了總編碼時(shí)間，降低了運(yùn)動(dòng)估計(jì)ME的計(jì)算開(kāi)銷(xiāo)。同時(shí)保證PSNR損失和比特率增加，在可忽略不計(jì)的范圍內(nèi)。

圖2 編碼前后的圖像比較

測(cè)試序列PSNR/dBBit-rate/kbit·s-1ME時(shí)間/sEncoding時(shí)間/sNewsJM19.030.91226.71146.57184.401PL30.90427.93744.53457.701比較結(jié)果-0。0080.7744.3731.63%續(xù)表1ForemanJM19.030.63134.42948.12985.813PL30.61536.43045.59459.055比較結(jié)果-0.0162.0015.56031.18%AklyeJM19.032.63110.44946.52280.364PL32.60211.22744.63656.522比較結(jié)果-0.0290.7784.26021.50%TrevorJM19.031.31244.71347.77484.778PL31.28847.57346.51759.602比較結(jié)果-0.0241.8042.70029.70%

表2 本文算法針對(duì)視頻序列CIF的性能

4 結(jié)束語(yǔ)

本文提出的PL算法包括幀間模式?jīng)Q策滑流算法(SL算法)和幀間模式?jīng)Q策SKIP算法，同時(shí)還采用比特率估計(jì)算法和低復(fù)雜性的整數(shù)失真估計(jì)方法，可以減少總編碼時(shí)間，降低計(jì)算開(kāi)銷(xiāo)。提出SL模式?jīng)Q策算法，實(shí)現(xiàn)運(yùn)動(dòng)估計(jì)和RDO幀內(nèi)模式?jīng)Q策可以并行執(zhí)行，SKIP算法去除了RDO幀內(nèi)模式?jīng)Q策的大多數(shù)不必要計(jì)算。此外，SL算法通過(guò)從共享二級(jí)高速緩存數(shù)據(jù)預(yù)先獲取，可以加快運(yùn)動(dòng)估計(jì)的計(jì)算過(guò)程。本文算法可以減少編碼時(shí)間，同時(shí)保證PSNR損失和比特率增加在可忽略的范圍內(nèi)。基于JM19.0的實(shí)驗(yàn)結(jié)果表明，該算法減少了總平均編碼時(shí)間29.18%，同時(shí)的平均PSNR值僅為0.012 5，平均碼流增加率平均值為1.625，可忽略不計(jì)。

[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] 何宜寶,陳再秀.利用邊緣方向檢測(cè)實(shí)現(xiàn)H.264 幀內(nèi)預(yù)測(cè)編碼的新算法[J].西安電子科技大學(xué)學(xué)報(bào),2009,36(6):1126-1131.

[3] 高蒿,陳耀武.基于紋理區(qū)域分割的SVC 快速模式模式?jīng)Q策算法[J].計(jì)算機(jī)工程,2011,37(22):256-249.

[4] 吳笛,卿粼波,何小海.基于MVMW 的H.264/AVC自適應(yīng)快速幀間模式?jīng)Q策算法[J].系統(tǒng)工程與電子技術(shù),2013,35(6):1330-1335.

[5] 吳笛,卿粼波,何小海.基于MVMW 的H.264/AVC自適應(yīng)快速幀間模式?jīng)Q策算法[J].系統(tǒng)工程與電子技術(shù),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

國(guó)家自然科學(xué)基金(61104154)；上海市自然科學(xué)基金(16ZR1401300；16ZR1401200)

卞鳳杰(1990-)，女，碩士研究生。研究方向：數(shù)字圖像處理。齊金鵬(1977-)，男，博士，副教授，碩士生導(dǎo)師。研究方向：數(shù)字圖像處理。劉樹(shù)娟(1991-),女,碩士研究生。研究方向：數(shù)字圖像處理。

10.16180/j.cnki.issn1007-7820.2017.04.021

TN919.81

A

1007-7820(2017)04-083-05