基于Syntax 級(jí)分組和多線程處理的HEVC 熵編碼并行算法*

邸金紅，張克新，祁 躋，張?chǎng)蚊?/p>

(1.鄭州航空工業(yè)管理學(xué)院 電子通信工程系，鄭州450015;2.阿拉巴馬大學(xué)，美國(guó) 塔斯卡盧薩870118;3.中國(guó)艦船研究院，北京100192)

1 引 言

高效視頻編碼(High Efficiency Video Coding，HEVC)是由ISO 的動(dòng)態(tài)圖像編碼專家組(Moving Pictures Experts Group/Motion Pictures Experts Group，MPEG)和ITU 的視頻編碼專家組(Video Coding Experts Group，VCEG)共同提出和制定的下一代視頻編碼標(biāo)準(zhǔn)。作為現(xiàn)行視頻編碼標(biāo)準(zhǔn)H.264/AVC的繼任者，HEVC 的目標(biāo)是較H. 264/AVC 有2 倍的壓縮效率并支持到7680×4320 的視頻分辨率［1］。HEVC 以算法復(fù)雜度的增加來?yè)Q取壓縮效率的進(jìn)一步提高［2－3］，然而，算法復(fù)雜度越高，運(yùn)算消耗的資源也就越大，從目前HEVC 標(biāo)準(zhǔn)測(cè)試代碼HM 的運(yùn)算時(shí)間來看，難以滿足實(shí)際應(yīng)用中實(shí)時(shí)編碼的需求。針對(duì)這一難題，面向并行多核/眾核處理器的視頻編碼并行算法為大數(shù)據(jù)量運(yùn)算問題提供了一種重要的解決手段，也是當(dāng)前多媒體技術(shù)領(lǐng)域研究的熱點(diǎn)之一。

不同于H.264/AVC 中分別應(yīng)用與基本檔和高檔編碼配置的兩種熵編碼算法，HEVC 僅采用一種熵編碼模式，即基于上下文的自適應(yīng)二進(jìn)制算術(shù)編碼(Context－ Adaptive Binary Arithmetic Coding，CABAC)［4］。熵編碼模塊以其與其他模塊的緊耦合性和數(shù)據(jù)之間的強(qiáng)相關(guān)性，成為并行化處理的瓶頸。針對(duì)HEVC 測(cè)試模型，K. Misra［5］等提出了Entropy Slice 的概念，它具有較高的并行粒度，并且良好地解決了負(fù)載不均衡的問題。Clare［6］提出行波并行處理算法(Wave－front Parallel Processing，WPP)，波面用于實(shí)現(xiàn)幀層次的并行，相當(dāng)于多幀多線程處理。隨后在WPP 的基礎(chǔ)上提出相應(yīng)的CABAC 編碼方法［7］。Arild［8］提出一種對(duì)宏塊分割的新結(jié)構(gòu)Tiles，有利于減小并行中宏塊分割所帶來的失真。對(duì)于CABAC，隨著下文模型動(dòng)態(tài)更新機(jī)制的引入，使得整個(gè)熵編碼過程成為了一個(gè)高度緊耦合的串行過程。強(qiáng)行進(jìn)行圖像塊的劃分，必然會(huì)導(dǎo)致編碼性能的下降。因此，基于現(xiàn)有串行的編碼框架體系，使用并行計(jì)算加速編碼的總體效果并不理想。

為了提高HEVC 編碼速度，本文依據(jù)并行計(jì)算的適用特點(diǎn)，提出了一種基于Syntax 分組流水線處理和多線程處理的并行算法，并在HM 10.0 平臺(tái)上進(jìn)行了仿真。

2 HEVC 熵編碼并行策略分析

HEVC 熵編碼的并行策略主要有Bin 級(jí)并行處理、Slice 級(jí)并行處理和Syntax 級(jí)并行處理3 種。

2.1 Bin 級(jí)并行處理

Bin 級(jí)的并行策略主要是在二進(jìn)制算術(shù)編碼部分進(jìn)行并行處理。輸入的句法元素經(jīng)過二值化被映射成一個(gè)二進(jìn)制序列，這個(gè)二進(jìn)制序列在經(jīng)過上下文建模和概率估計(jì)后，以比特為單位被分拆成若干部分分別進(jìn)行算術(shù)編碼，編碼完后再進(jìn)行組合最終形成輸出碼流。Bin 級(jí)并行處理策略的并行粒度取決于上下文建模和概率估計(jì)的處理能力，因此對(duì)提高系統(tǒng)性能方面影響不大，有時(shí)反而會(huì)引起系統(tǒng)性能的下降。

2.2 Slice 級(jí)并行處理

根據(jù)H.264/AVC 中Slice 分割的思想，HEVC在保留傳統(tǒng)Slice 的基礎(chǔ)上引入了Entropy Slice［5，9］的并行編碼策略。與傳統(tǒng)的Slice 不同的是，Entropy Slice 將鄰近編碼片的位置信息寫入碼流，使其在重建圖像的時(shí)候可以利用鄰近Slice 中包括運(yùn)動(dòng)估計(jì)及幀內(nèi)預(yù)測(cè)在內(nèi)的編碼信息，編碼性能得到進(jìn)一步提高。Entropy Slice 允許在一個(gè)Slice 內(nèi)部再切分成多個(gè)Entropy Slices，這樣熵編碼器可以并行編碼，從而提高了并行處理能力，使編碼器的負(fù)載更加均衡。利用Entropy Slice 并行方案，可以同時(shí)調(diào)動(dòng)CPU 和GPU 進(jìn)行運(yùn)算，使整個(gè)編碼系統(tǒng)的運(yùn)算能力得以充分發(fā)揮。無論是傳統(tǒng)Slice 還是Entropy Slice，其并行粒度依然局限于編碼片的劃分。對(duì)于當(dāng)今大規(guī)模并行計(jì)算的需求，依然有很大的差距。隨著HEVC編碼框架的完善和新的方法不斷涌現(xiàn)，該技術(shù)已不再被標(biāo)準(zhǔn)所推崇［6－8］。

2.3 Syntax 級(jí)并行處理

Syntax 級(jí)的并行策略不將一組二進(jìn)制符號(hào)分配到不同的熵編碼器中，也不按照實(shí)際編碼單元進(jìn)行分割，而是按照語(yǔ)法元素的不同進(jìn)行分割從而實(shí)現(xiàn)并行處理。在現(xiàn)行的熵編碼框架中，對(duì)于每種語(yǔ)法元素，都使用特定的上下文模型進(jìn)行建模，因此，按照語(yǔ)法元素進(jìn)行分類，可以使這些上下模型進(jìn)行盡可能多的訓(xùn)練過程，從而使編碼概率估計(jì)更加精確，因此本文采用了Syntax 級(jí)并行策略。此外，無論是大型數(shù)據(jù)工作站還是個(gè)人計(jì)算機(jī)，其核心CPU 都具備多線程架構(gòu)，并且隨著CPU 技術(shù)的發(fā)展，其核心數(shù)會(huì)越來越多。多線程技術(shù)是并行計(jì)算的一個(gè)重要組成部分，因此可以利用CPU 的多線程計(jì)算能力來實(shí)現(xiàn)HEVC 幀級(jí)的并行編碼。結(jié)合兩者的優(yōu)點(diǎn)，本文提出了基于Syntax 級(jí)分組和多線程處理的并行算法，下面詳細(xì)介紹具體實(shí)現(xiàn)過程。

3 提出的熵編碼并行算法

3.1 Syntax 級(jí)分組

與H.264/AVC 相類似，HEVC 中的語(yǔ)法元素同樣可以進(jìn)行分組以實(shí)現(xiàn)Syntax 級(jí)的并行處理。對(duì)于HEVC 中一個(gè)編碼樹單元(Coding Tree Unit，CTU)里的編碼信息，按照語(yǔ)法元素進(jìn)行劃分可以分為以下幾組:編碼塊劃分信息SpiltFlag，編碼方式PredMode，塊劃分方式PartSize，預(yù)測(cè)信息PredInfo，變換系數(shù)塊標(biāo)志位Cbf，非零變換系數(shù)位置信息Sig-Map 和非零變換系數(shù)信息Coeff。具體來說，PredInfo 包括IntraDirLumaAng、IntraDirChroma 等幀內(nèi)角度預(yù)測(cè)信息和MergeFlag、SkipFlag、MergeIndex、RefFrmIdx 和Mvd 等幀間運(yùn)動(dòng)估計(jì)信息;SigMap 包括LastSignificantX/Y、SignificantCoeffFlag、SignificantCoeffGroupFlag 等非零變換系數(shù)位置信息;Coeff 包括C1Flag、C2Flag、AbsCoeff 和CoeffSigns 等非零變換系數(shù)幅值和符號(hào)信息。

這些語(yǔ)法元素之間具有信息間的依賴性，如圖1所示。需要注意的是語(yǔ)法元素SkipFlag，該語(yǔ)法元素和其對(duì)應(yīng)的語(yǔ)法元素MergeIndex 雖然也屬于PredInfo 一組，但并不同其他屬于PredInfo 的語(yǔ)法元素一樣依賴于PartSize 和PredMode 的信息，因此，需要將此語(yǔ)法元素單獨(dú)分離出來?；谏鲜龇治?，構(gòu)建一個(gè)如圖2所示的Syntax 級(jí)并行編碼器。

將CTU 中的語(yǔ)法元素進(jìn)行分組后，需要在每組語(yǔ)法元素之前設(shè)置一個(gè)標(biāo)志位(StartFlag)以與其他組進(jìn)行區(qū)分。在本文提出的并行算法中，利用一元碼來設(shè)置StartFlag。對(duì)于圖2中9 組語(yǔ)法元素，按照流水線的先后處理順序分別賦予0、10、110、1110、11110、111110、1111110、11111110 和111111110 作為標(biāo)志位碼字。

圖2 HEVC 中Syntax 級(jí)并行編碼器結(jié)構(gòu)Fig.2 The parallel structure based on syntax－level in HEVC

3.2 多線程處理

在HEVC 中，如果采用全I(xiàn) 幀編碼，則各幀之間編碼數(shù)據(jù)相互獨(dú)立，各幀在編碼時(shí)不需要數(shù)據(jù)間的相互通信。在本文提出的多線程編碼方法中，需要單獨(dú)開辟一個(gè)線程進(jìn)行碼流的排序和拼接。以八線程處理為例，首先將視頻序列的前7 幀依次送入第1～7 個(gè)線程后分別進(jìn)行編碼，編碼完畢后這7 個(gè)線程進(jìn)行同步，并輸出碼流到第8 個(gè)線程，在第8 個(gè)線程中進(jìn)行碼流的排序和拼接。同時(shí)，將視頻序列的第8～14 幀再依次送入到前7 個(gè)線程中進(jìn)行編碼，以后依次類推，整個(gè)編碼過程如圖3所示。

圖3 全I(xiàn) 幀八線程編碼方案Fig.3 Eight－thread coding scheme for I frame

如果采用I/B/P 幀編碼，則各幀之間數(shù)據(jù)不相互獨(dú)立，B/P 幀進(jìn)行編碼時(shí)都需要利用參考幀的信息，因此需要數(shù)據(jù)間的相互通信。在本文提出的多線程編碼方法中，不僅需要單獨(dú)開辟一個(gè)線程進(jìn)行碼流的排序和拼接，還需開辟一個(gè)線程進(jìn)行參考幀管理。以八線程處理為例，首先將視頻序列的前6幀依次送入第1～6 個(gè)線程，然后在第一個(gè)線程編碼第一幀，進(jìn)而將編碼完后的數(shù)據(jù)信息送入用于參考幀管理的第7 個(gè)線程，將碼流送入用于輸出碼流的第8 個(gè)線程，接著開啟第2～6 幀的編碼。在這5 幀編碼期間，第7 個(gè)線程需要不斷地進(jìn)行數(shù)據(jù)通信和協(xié)調(diào)同步處理，以完成幀間編碼運(yùn)動(dòng)估計(jì)，然后這5幀將碼流輸入到第8 個(gè)線程，在第8 個(gè)線程中進(jìn)行碼流的排序和拼接。同時(shí)，將視頻序列的第7～12幀再依次送入到前6 個(gè)線程中進(jìn)行編碼，以后依次類推，整個(gè)編碼過程如圖4所示。

圖4 I/B/P 幀八線程編碼方案Fig.4 Eight－thread coding scheme for I/B/P frame

HEVC 中參考幀列表管理非常復(fù)雜，如果將完整的雙向預(yù)測(cè)放入一個(gè)線程中進(jìn)行管理，就會(huì)導(dǎo)致該線程負(fù)荷過重，反而會(huì)降低處理速度。因此，為了提高多線程計(jì)算效率，本文提出的方法中幀間預(yù)測(cè)中僅采用前向預(yù)測(cè)。

4 實(shí)驗(yàn)結(jié)果及分析

算法測(cè)試的硬件平臺(tái)所用的CPU 型號(hào)為Intel Core i7，主頻為3.5 GHz，核心數(shù)為四核，可支持八線程計(jì)算。由于是并行算法，實(shí)驗(yàn)主要是從時(shí)間加速方面來驗(yàn)證算法的有效性，同時(shí)也考慮了視頻壓縮的主客觀質(zhì)量，其中，客觀質(zhì)量是用PSNR 來衡量的。在驗(yàn)證并行算法效果時(shí)，對(duì)于全I(xiàn) 幀并行處理，選用官方編碼器中只支持全I(xiàn) 幀編碼的All Intra(AI)設(shè)置與其進(jìn)行比較;而對(duì)于I/B/P 幀并行處理，由于算法中幀間預(yù)測(cè)僅采用前向預(yù)測(cè)，因此，選用官方編碼器中只支持前向預(yù)測(cè)的LowDelay(LD)設(shè)置與其進(jìn)行比較。

仿真實(shí)驗(yàn)選用HEVC 官方標(biāo)準(zhǔn)視頻序列庫(kù)Class B(1920× 1080，1080P)中的Kimono、Park-Scene、BQTerrace、BasketballDrive 序 列 和Class C(832× 480，WVGA)中的BasketballDrill、BQMall、RaceHorses 和PartyScene 序列，這兩組序列分別在AI、LD 兩種編碼條件下進(jìn)行測(cè)試。表1和表2為4個(gè)1080P 序列分別在AI、LD 設(shè)置下的性能比較結(jié)果，表3和表4為4 個(gè)WVGA 序列分別在兩種不同設(shè)置下的性能結(jié)果比較。

表1 AI 設(shè)置編碼1080P 序列串行計(jì)算與并行計(jì)算速度性能比較Table 1 The performance comparison between serial computing and parallel computing for 1080P(AI)

表2 LD 設(shè)置編碼1080P 序列串行計(jì)算與并行計(jì)算速度性能比較Table 2 The performance comparison between serial computing and parallel computing for 1080P(LD)

表3 AI 設(shè)置編碼WVGA 序列串行計(jì)算與并行計(jì)算速度性能比較Table 3 The performance comparison between serial computing and parallel computing for WVGA(AI)

表4 LD 設(shè)置編碼WVGA 序列串行計(jì)算與并行計(jì)算速度性能比較Table 4 Theperformance comparison between serial computing and parallel computing for WVGA(LD)

由表1～4可見，從編碼時(shí)間上來看，本文提出的并行算法與HM10.0 相比，在AI 設(shè)置上平均有70%左右的編碼時(shí)間節(jié)省，在LD 設(shè)置上平均有65%左右的編碼時(shí)間節(jié)省。從這一數(shù)據(jù)可以看出，多線程計(jì)算并不能達(dá)到完全的成倍加速，其原因在于線程間數(shù)據(jù)需要相互通信，線程間并行處理需要不斷進(jìn)行同步，這些過程都需要消耗一定的時(shí)間。從編碼圖像的BD－rate 來看，本章提出的并行算法與HM10.0 相比，在AI 設(shè)置上平均有0.4%左右的BD－rate 損失，在LD 設(shè)置上平均有1.8%左右的BD－rate 損失，其原因在于并行處理還是損害了編碼數(shù)據(jù)之間的相關(guān)性，從而使得熵編碼的上下文建模過程和概率估計(jì)過程精確度下降。而由圖5可見，應(yīng)用本節(jié)的并行算法后，輸出的編碼圖像相比于HM10.0 在主觀質(zhì)量上并沒有太大的變化。

圖5 Kimono 序列Fig.5 Coding results of Kimono sequence

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

為了提高HEVC 編碼系統(tǒng)的運(yùn)算速度，本文提出一種基于Syntax 分組流水線處理和多線程計(jì)算的并行算法。該算法借鑒H.264/AVC 中Syntax 級(jí)的并行算法思路，將碼流中的語(yǔ)法元素分組并以流水線形式實(shí)現(xiàn)并發(fā)處理，同時(shí)，采用多線程并行處理技術(shù)，充分利用CPU 的核心數(shù)量，合理進(jìn)行資源調(diào)度。將所提出的并行算法與傳統(tǒng)的串行算法進(jìn)行比較，驗(yàn)證了該算法的有效性。但是當(dāng)前并行算法框架加速比不夠高，遠(yuǎn)遠(yuǎn)不能滿足實(shí)時(shí)視頻編碼的要求，需要進(jìn)一步研究視頻編碼中的各種編碼數(shù)據(jù)之間的依賴關(guān)系，找到更優(yōu)的壓縮效率與計(jì)算速度的折衷方案，加大整個(gè)系統(tǒng)的并行計(jì)算粒度。

［1］ JCTVC－A124，Samsung's response to the call for proposals on video compression technology［S］.

［2］ Correa G，Assuncao P，Agostini L，et al. Performance and Computational Complexity Assessment of High－Efficiency Video Encoders［J］. IEEE Transactions on Circuits and Systems for Video Technology，2012，22(12):1899－1909.

［3］ Frank B，Bross B，Sühring K，et al.HEVC Complexity and Implementation Analysis［J］. IEEE Transactions on Circuits and Systems for Video Technology，2012，22(12):1685－1696.

［4］ Vivienne S，Budagavi M. High Throughput CABAC Entropy Coding in HEVC［J］. IEEE Transactions on Circuits and Systems for Video Technology，2012，22(12):1778－1791.

［5］ JCTVC－B111，Entropy slices for parallel entropy coding［S］.

［6］ JCTVC－F274，Wavefront Parallel Processing for HEVC Encoding and Decoding［S］.

［7］ JCTVC－F275，Wavefront and CABAC Flush:Different Degrees of Parallelism Without Transcoding［S］.

［8］ JCTVC－F335，Tiles［S］.

［9］ JCTVC－D070，Lightweight slicing for entropy coding［S］.