CABAC中等概率符號的并行解碼算法

陳海燕

(華東政法大學(xué)計算機(jī)科學(xué)與技術(shù)系，上海 201620)

H.264［1］是最新的國際視頻編碼標(biāo)準(zhǔn)，在數(shù)字電視、視頻拍攝、流媒體等方面得到了廣泛的應(yīng)用。由于其高復(fù)雜度，對于它的解碼算法的優(yōu)化變得尤為重要。H.264中有兩種熵編碼算法，一種是基于哈夫曼變長碼的內(nèi)容自適應(yīng)變長編碼(CAVLC)［2］，另一種是基于二進(jìn)制算術(shù)編碼的內(nèi)容自適應(yīng)二進(jìn)制算術(shù)編碼(CABAC)［3］。CABAC中共有3類符號，即一般的二進(jìn)制位符號、等概率二進(jìn)制位符號(也叫旁路符號)和終止二進(jìn)制位符號。其一般的解碼流程都是逐位進(jìn)行解碼。CABAC算法目前已經(jīng)有硬件方面的實(shí)現(xiàn)，具體可以參考文獻(xiàn)［4］。本文的特色在于使用純軟件的方法，提出一種等概率二進(jìn)制位符號的多位并行解碼算法，用以加快H.264視頻解碼的速度。

1 技術(shù)背景

CABAC是H.264中一種高效的熵編碼方法，與基于哈夫曼變長碼的方法相比，能節(jié)省大約10%的碼率，而由于需要逐二進(jìn)制位算術(shù)解碼，其計算復(fù)雜度也大大提升。在CABAC中，所有待編碼符號首先被二進(jìn)制化為一系列二進(jìn)制位比特串，然后根據(jù)一定的內(nèi)容模型逐位進(jìn)行算術(shù)編碼。二進(jìn)制位比特串共分為3類，一般的二進(jìn)制位比特串、等概率二進(jìn)制位比特串和終止二進(jìn)制位比特串。等概率二進(jìn)制位比特串是一種重要的類型，較大的運(yùn)動向量(MV)和量化DCT系數(shù)(Level)、運(yùn)動向量和DCT系數(shù)的符號都需要用等概率二進(jìn)制位序列編碼。對于較大的運(yùn)動向量和量化DCT系數(shù)，數(shù)值首先被二進(jìn)制化為指數(shù)－哥倫布碼［4］，然后逐位進(jìn)行等概率符號編碼。在解碼器中，首先逐位解碼出指數(shù)－哥倫布碼，然后還原出數(shù)值。指數(shù)－哥倫布碼如表1所示，它由兩部分組成，第一部分是前導(dǎo)1結(jié)構(gòu)，由n(n≥0)個連續(xù)的1最后跟一個0組成，該算法中，稱其為前導(dǎo)1符號;第二部分是定長編碼部分，其長度為m(m≤n)。如表1中數(shù)值3，4，5，6所對應(yīng)的指數(shù)哥倫布碼的前導(dǎo)1符號都是110，前導(dǎo)1長度為2，定長編碼部分長度也是2。

針對作為等概率符號編碼的指數(shù)哥倫布碼的前導(dǎo)1部分和定長編碼部分各提出一種快速的并行解碼算法，與原來的逐位解碼相比，該算法可以一次解碼出數(shù)位等概率二進(jìn)制位，大大提高了解碼速度。

表1 指數(shù)哥倫布碼

2 CABAC中等概率符號的快速解碼

2.1 CABAC中等概率符號解碼過程

在一個CABAC解碼器中，假設(shè)多字節(jié)基的輸入輸出，基本變量有 value，bitsleft和 range，其中 range∈［0x100，0x1ff］且 0 ≤ value ＜ (range ＜ ＜ bitsleft)，bitsleft≥0。等概率符號的解碼基本過程如下:

當(dāng)bitsleft遞減至小于0時，從碼流中讀取一定長度字節(jié)填充至value末尾，并相應(yīng)的更新bitsleft。讀取n字節(jié)具體過程如下:

該算法約定value和bitsleft的初始狀態(tài)表示為valuen和bitsleftn，當(dāng)解碼了n位等概率二進(jìn)制位后，其狀態(tài)分別用valuen和bitsleftn表示，從以上解碼過程中易知bitsleftn=bitsleft0－n，如果bitsleftn不小于0，則有0≤valuen＜ (range＜ ＜bitsleftn)。

2.2 前導(dǎo)1部分的并行解碼算法

對于前導(dǎo)1結(jié)構(gòu)的解碼，其解碼就是循環(huán)進(jìn)行等概率二進(jìn)制位解碼直到獲得第一個0。假設(shè)已連續(xù)解碼了x個1，根據(jù)以上過程，valuex=value0－(range＜＜bitsleft)+(range＜ ＜ (bitsleft－x))，且valuex≥0，如果下一個符號仍然是1，那么有 valuex≥ (range＜＜(bitsleft－x－1))，否則下一個符號為0。所以解碼一個前導(dǎo)1符號的本質(zhì)就是max{x|(value0－(range＜＜bitsleft)+(range＜＜(bitsleft－x)))≥0}，即max{x|(range＜＜(bitsleft－x))≥(range＜＜bitsleft)－value0}。考慮到 range的范圍，可以先求出 diff0=(range＜＜bitsleft)－value0，然后用前導(dǎo)0指令，如x86/x64下的BSF或ARM下的CLZ，求出其最高有效位y，即(1＜＜y)≤diff0＜(1＜＜(y+1))，然后和range＜＜(y－8)比較，如果(range＜＜(y－8))≥diff0，那么x=bitsleft－y+8，否則 x=bitsleft－y+9。

以上推導(dǎo)并沒有考慮bitsleft可能會變的小于0的問題。在一個實(shí)際的實(shí)現(xiàn)中，由于MV和Level的最大值是有限制的，所以相應(yīng)的最大的前導(dǎo)1數(shù)目也是有限制的，如19，所以在執(zhí)行一個前導(dǎo)1并行解碼過程前，首先從碼流中讀取一定數(shù)量字節(jié)并遞增bitsleft，使其長度大于最大前導(dǎo)1數(shù)目，這樣就可以用上述算法一次解碼出一個前導(dǎo)1符號來。

2.3 定長編碼部分的并行解碼

式中:/表示整數(shù)除法;%表示求余指令。在實(shí)際的實(shí)現(xiàn)中，由于除法運(yùn)算非常耗時，考慮到range∈［0x100，0x1ff］，可以將65536 /range預(yù)先求出并存在一個整數(shù)常量 表 L［range］中，于 是 S ≈ Sappro= value0×L［range］＞＞(bitsleft+16－n)，這樣就可以用查表運(yùn)算和乘法運(yùn)算代替除法運(yùn)算。由于表示精度問題，通過這種方式計算出的value(S)可能并不能滿足0≤value(S)＜(range＜＜(bitsleft－n))。于是可以對邊界進(jìn)行判斷，如果value(S)＜0，那么遞減S以至value(S)≥0，如果value(S)≥(range＜＜(bitsleft－n))，那么遞增S。為了進(jìn)一步減少運(yùn)算量，可以設(shè)計常量表L［range］，使對于任意value，都有value0－Sappro×(range＜＜(bitsleftn))≥0，于是只需要對右邊界進(jìn)行判斷就可以了。一般來說，這個計算過程很精確，判斷部分只需要很小的計算量就能滿足。

以上推導(dǎo)并沒有考慮bitsleft可能會變的小于并行解碼位數(shù)n的問題。在一個實(shí)際的實(shí)現(xiàn)中，如要實(shí)現(xiàn)一個4個二進(jìn)制位并行解碼模塊，可以在解碼前首先判斷bitsleft是否小于4，如果小于，那么從碼流中讀入字節(jié)并遞增bitsleft使其大于等于4。

2.4 算法性能分析

實(shí)驗(yàn)在Intel Core 2 Quad 2.5 GHz CPU上進(jìn)行，DRAM為2 Gbyte。首先用CABAC編碼器分別產(chǎn)生1 Mbyte具有不同前導(dǎo)1長度的碼流，然后比較逐位解碼和本文所述的快速前導(dǎo)1解碼算法的性能，結(jié)果如表2所示。可以看出當(dāng)前導(dǎo)1數(shù)目較大時，該算法相比逐位解碼具有很大的優(yōu)勢。而當(dāng)前導(dǎo)1數(shù)目很小時，該算法比逐位解碼的要慢一些。

表2 前導(dǎo)1解碼性能比較(基準(zhǔn)是逐位解碼)

然后比較定長解碼的性能。首先用CABAC編碼器產(chǎn)生1 Mbyte等概率碼流，然后比較4符號并行解碼算法和逐位解碼的性能。結(jié)果表明逐位解碼需要4符號并行解碼算法2.51倍的時間。

3 結(jié)束語

本文針對CABAC中作為等概率符號編碼的指數(shù)—哥倫布碼提出了一種多二進(jìn)制位并行解碼算法，實(shí)驗(yàn)結(jié)果

表明該算法相比逐位解碼具有更快的解碼速度。

［1］ITU－T.ISO/IEC International Standard 14496－10 AVC［S］.2004.

［2］RICHARDSON I E G.H.264 and MPEG－4 video compression:video coding for next－generation multimedia［M］.Chichester:John Wiley ＆Sons Ltd.，2003.

［3］MARPE D，SCHWARZ H，WIEGAND T，et al.Context－based adaptive binary arithmetic coding in the H.264/AVC video compression standard［J］.IEEE Trans.Circuits and Systems for Video Technology，2003，13(7):620－636.

［4］姚棟，虞露.H.264指數(shù)哥倫布碼解碼部件的硬件設(shè)計和實(shí)現(xiàn)［J］.電視技術(shù)，2004，28(11):14－16.