CABAC中等概率符號(hào)的并行解碼算法

陳海燕

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

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

1 技術(shù)背景

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

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

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

2 CABAC中等概率符號(hào)的快速解碼

2.1 CABAC中等概率符號(hào)解碼過(guò)程

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

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

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

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

對(duì)于前導(dǎo)1結(jié)構(gòu)的解碼，其解碼就是循環(huán)進(jìn)行等概率二進(jìn)制位解碼直到獲得第一個(gè)0。假設(shè)已連續(xù)解碼了x個(gè)1，根據(jù)以上過(guò)程，valuex=value0－(range＜＜bitsleft)+(range＜ ＜ (bitsleft－x))，且valuex≥0，如果下一個(gè)符號(hào)仍然是1，那么有 valuex≥ (range＜＜(bitsleft－x－1))，否則下一個(gè)符號(hào)為0。所以解碼一個(gè)前導(dǎo)1符號(hào)的本質(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)并沒(méi)有考慮bitsleft可能會(huì)變的小于0的問(wèn)題。在一個(gè)實(shí)際的實(shí)現(xiàn)中，由于MV和Level的最大值是有限制的，所以相應(yīng)的最大的前導(dǎo)1數(shù)目也是有限制的，如19，所以在執(zhí)行一個(gè)前導(dǎo)1并行解碼過(guò)程前，首先從碼流中讀取一定數(shù)量字節(jié)并遞增bitsleft，使其長(zhǎng)度大于最大前導(dǎo)1數(shù)目，這樣就可以用上述算法一次解碼出一個(gè)前導(dǎo)1符號(hào)來(lái)。

2.3 定長(zhǎng)編碼部分的并行解碼

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

以上推導(dǎo)并沒(méi)有考慮bitsleft可能會(huì)變的小于并行解碼位數(shù)n的問(wèn)題。在一個(gè)實(shí)際的實(shí)現(xiàn)中，如要實(shí)現(xiàn)一個(gè)4個(gè)二進(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長(zhǎng)度的碼流，然后比較逐位解碼和本文所述的快速前導(dǎo)1解碼算法的性能，結(jié)果如表2所示。可以看出當(dāng)前導(dǎo)1數(shù)目較大時(shí)，該算法相比逐位解碼具有很大的優(yōu)勢(shì)。而當(dāng)前導(dǎo)1數(shù)目很小時(shí)，該算法比逐位解碼的要慢一些。

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

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

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

本文針對(duì)CABAC中作為等概率符號(hào)編碼的指數(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è)計(jì)和實(shí)現(xiàn)［J］.電視技術(shù)，2004，28(11):14－16.