基于區間劃分的快速重歸一化算法

摘 要:重歸一化是H.264/AVC標準二進制算術編碼器的一個關鍵部分，在算術編碼器中，重歸一化計算量很大，嚴重制約了算術編碼器的效率;同時重歸一化算法是一個按位操作過程，很多情況下通過運行一次重歸一化算法并不能完成重歸一化操作，因此消耗了大量編碼時間。為了減少編碼時間，針對影響重歸一化速度的瓶頸問題，提出了一種基于區間劃分的快速重歸一化算法。根據重歸一化循環次數提出六種不同的區間劃分標準來去除H.264/AVC重歸一化算法中消耗大量編碼時間的按位操作過程;通過去除重歸一化的循環過程，使得算法在單位時間內向編碼流中輸出更多的比特數，能夠更好地滿足實時性的要求。實驗表明，快速重歸一化算法在原重歸一化算法基礎上減少了21.9%~26.7%的重歸一化次數和14.5%~33.7%的編碼時間。

關鍵詞:二進制算術編碼器; 重歸一化; 按位操作; 區間劃分

中圖分類號:TN919.8

文獻標志碼:A

文章編號:1001-3695(2010)02-0439-04

doi:10.3969/j.issn.1001-3695.2010.02.009

Fast renormalization algorithm based on interval division

REN Sheng-bing， JIANG Wei， CHEN Yuan， HUANG Zi-wu

(Academy of Information Science Engineering， Central South University， Changsha 410083， China)

Abstract:Renormalization is a key part of BAC in H.264/AVC standard. In BAC， the renormalization has seriously constrained the efficiency of the arithmetic coding because its computational complexity is high. Renormalization algorithm is a bitwise-operation procedure. In many cases，the renormalization operation can’t be finished by running renormalization algorithm for one time， so it is consuming a lot of coding time. In order to reduce the coding time， this paper introduced a fast renormalization algorithm based on interval division to deal with the bottleneck problem in renormalization. According to the number of cycles in renormalization loop， this fast renormalization algorithm introduced six different interval division standards to replace time-consuming， bitwise-operation procedure. At the same time， through removing the cycle of renormalization procedure， the algorithm could output more bits to coding stream in unit time and better meet the requirements of real-time. Experiment results indicate that the proposed fast renormalization algorithm enables reduce the number of renormalization algorithm by 21.9%~26.7% and their corresponding run time by 14.5%~33.7%.

Key words:binary arithmetic coder (BAC); renormalization; bitwise-operation; interval division

0 引言

基于上下文的自適應二進制算術編碼CABAC(context-based adaptive binary arithmetic coding)是H.264/AVC 標準的兩種熵編碼方案之一，與另一熵編碼方式CAVLC以及傳統的VLC基線熵編碼方式相比，提高了30%的壓縮率[1]。但由于上下文模型選擇、概率更新、重歸一化等過程也大大增加了計算復雜度[2]，從而影響了整個CABAC編碼器的速度。

在H.264/AVC標準中，重歸一化過程是一種按位操作的過程[2]，它由編碼區間R來控制重歸一化的循環次數。在重歸一化過程中，一次重歸一化并不能保證重歸一化過程結束，且在循環過程中要不斷調整編碼下限L的范圍，因此帶循環的重歸一化過程消耗了大量的時鐘和資源[3]。由于重歸一化循環過程的限制，一次重歸一化并不能輸出多個比特值，影響了輸出比特數，成為提高編碼器吞吐率的一大障礙。

為了減少重歸一化計算的復雜度，人們在提高重歸一化速度方面做了大量的工作[4~6] 。在硬件方面，通過流水線將重歸一化分成兩部分來減少編碼時間[4];或者根據重歸一化的特征將區間變化的大小存在表中，在重歸一化過程中通過查表來去除重歸一化的循環過程[5]。雖然在性能上有所改進，但重歸一化計算復雜度還是很高。

與上述方法不同，本文在研究CABAC常規編碼器的過程中，根據重歸一化次數提出了一種基于區間劃分的快速重歸一化算法。算法的基本思想如下:

a)根據溢出的編碼區間與2b-2(b為編碼器精度)比較來確定重歸一化算法的執行次數。

b)根據算法的執行次數，編碼下限可以通過排列組合的原理得出編碼下限區間的劃分標準。

c)通過編碼下限的區間劃分標準來去掉重歸一化循環過程。

d)結合重歸一化原循環過程輸出結果，提高單位時間內輸出比特數。

在JM10.2[7]中的模擬實驗結果表明，采用本文提出的快速重歸一化算法，可以比原重歸一化算法減少21.9%~26.7%的重歸一化次數并節約14.5%~33.7%的編碼時間。

1 CABAC的重歸一化原理

二進制算術編碼器是根據二進制算術編碼原理設計的編碼器[1，8]。二進制算術編碼的基本思想是基于遞歸間隔劃分的編碼方法，在遞推過程中需要保存它的編碼下限L和編碼寬度R。假設當前字符的概率為Px，那么R的遞進關系如式(1)所示。

R=R×Px(1)

在常規編碼器中，每一個待編碼的信源符號值為0或1，用MPS(most probable symbol)表示最可能出現的字符，用LPS(least probable symbol)表示較小概率的字符。LPS的概率值由64個典型的概率值Pδ∈[0.01875，0.5]表示，其中δ(0≤δ≤63)代表狀態索引值。每一個上下文模型對應一個相應的概率值，上下文模型的概率值與最大概率符號值(valMPS)決定了常規編碼器間隔的劃分。在常規編碼時，給定的間隔R被分成兩個子間隔，即LPS間隔RLPS =R×РLPS，MPS間隔RMPS =R-RLPS。H.264/AVC標準中，L被初始化為0，R初始化為0x1FE。在區間劃分中，為了除去求LPS區間的乘法操作，在編碼器中采用了查表的方法來計算LPS的編碼區間。LPS的編碼區間RLPS通過量化值Q(R)估算，Q(R)由量化器索引ρ決定， ρ由(2)式求出。

ρ=(R>>6)3(2)

根據索引ρ和編碼器初始輸入的概率狀態索引δ，通過查一個二維的64×4表格TabRangeLPS來決定LPS相關的區間RLPS，其中0≤δ≤63，0<ρ<3。通過查表的方法使得編碼區間劃分不需要進行乘法計算，提高了計算速度。

LPS編碼區間選擇后就可以得到MPS的編碼區間，然后將當前編碼的符號與當前上下文模型中的valMPS相比較。如果編碼的符號等于當前上下文模型中的valMPS值，那么MPS的編碼區間將被選擇，L不變;否則選擇LPS的編碼區間RLPS，L變為L+RMPS。通過查表的方法來更新概率模型，最后進行重歸一化的過程。

常規編碼器在編碼過程中對區間不斷地細分，導致細分精度不斷降低。為了防止編碼區間的溢出，保證編碼區間在一定的范圍內，引入了重歸一化過程[9]。CABAC的重歸一化過程偽代碼如下所示:

// interval subdivision

1)

RLPS=TabRangeLPS[δ][ ρ]

2)

RMPS=R-RLPS

3)

if(value==valMPS)

4)

R= RMPS

5)

else

6)

L=L+ RMPS

7)

R= RLPS

// renormalization

8)

while(R<2b-2)

//path 3

9)

if (L>=2b-1)

10)

putBit(1)

11)

L=L-2b-1

12)

else

// path 1

13)

if(L<2b-2)

14)

PutBit(0)

15)

else

// path 2

16)

L=L-2b-2

17)

bitOutstanding++

18)

R=R<<1

19)

L=L<<1

為了提高編碼器的利用率，在重歸一化的過程中，如果確定了編碼區間的高位值，就要輸出高位，以保證遞進計算的同時不斷地輸出碼流。算術編碼器將2b-2作為重歸一化的閾值，存在四種情況:

a)R<2b-2，L<2b-2，(R+L)<2b-1，可以確定編碼區間的最高位為0，可以輸出這個0比特。寄存器通過左移1位的操作來將0移出去，即以上代碼中的path 1所示。

b)R<2b-2，L>2b-1，(R+L)>2b-1，同樣可以確定編碼區間的最高位為1，可以輸出這個1 bit，即以上代碼中的path 3所示。

c)R<2b-2，L介于2b-2~2b-1，(R+L)將會落在(2b-1，2b-1+2b-2)和(2b-2，2b-1)兩個區間內，即高兩位可能是01，也可能是10，因此無法確定最高有效位是1還是0。此時可以通過移出高位、縮小區間、判斷次高位符號的方法來確定移出的高位符號值，即以上代碼中path 2所示。若次高位值又落在path 2，將延遲移出次高位，代碼中的bitOutstanding代表非確定的延遲移出的高位值，通過繼續判斷當前位的值來輸出編碼區間的高位值。當落在path 1或path 3，都將輸出惟一確定的值而移出高位比特串。

d)R>2b-2時，(L+R)的值可以落在(2b-2，2b-1)的任何位置，無法確定編碼的高位值，因此無須進行重歸一化的過程。

2 基于區間劃分的快速重歸一化算法

從重歸一化過程中很容易發現，重歸一化的次數renorm的大小與編碼區間有關。若當前重歸一化的編碼區R為大概率符號事件，有R×РMPS=RMPS′(RMPS′<256，RLPS≤0.5≤РMPS，256≤R)，可以看到RMPS′<<1時，РMPS×2≥1，即有R×РMPS×2一定會大于R。所以大概率符號重歸一化的次數只能為1，只需要根據最高位值來判斷重歸一化的次數，次數由式(3)求出:

renorm=( RMPS>>8)XOR 1(3)

若當前重歸一化的編碼區間R為小概率符號事件，從TabRangeLPS表中發現編碼區間(δ<63)的下限大于等于6，也就是說重歸一化時，只要歸結為除去低3位的剩余5位的數字特征就能夠確定重歸一化的次數，其重歸一化的次數由式(4)求得。RenormTAB為根據低3位確定的一個重歸一化次數的表。

renorm=renormTAB[RLPS>>3](4)

renorm的次數可以總結為0≤renorm≤6的整數，對于renorm為0的重歸一化過程不做任何操作。其1~6的重歸一化過程在下面會作詳細的介紹。

2.1 Renorm為1的快速重歸一化算法

Renorm為1的重歸一化算法劃分區間的長度為256，以256為區間長度將編碼區間分成三部分，即小于256的部分(path 1)、介于256~512的部分(path 2)和大于512的部分(path 3)。Renorm為1的重歸一化算法和原重歸一化算法計算復雜度相差不大，本算法將重歸一化分成編碼和輸出兩部分，代碼如下所示:

// interval subdivision

1)

RLPS=TabRangeLPS[δ][ ρ]

2)

RMPS=R-RLPS

3)

if(value==valMPS)

4)

R= RMPS

5)

renorm=(range>>8)^1

6)

else

7)

L=L+RMPS

8)

R= RLPS

9)

renorm=renorm_table[(rLPS>> 3) 0x1F]

10)

R<

// renormalization

// encoding part

11)condition 1= (L<2b-2)

12)condition 2= (L>=2b-1)

13)path=2-condition 1+condition 2

14)dec=(path-1)(2b-2)

15)L=L-Dec

16)

bitOutstanding+=(path==2)

17)

L<<1

// writing part

18)

if (path!=2)

19)

putBit(path==3)

以上代碼為renorm為1的快速重歸一化過程，編碼部分負責判斷路徑。如果是path 1、path 3，那么可以輸出高位字節，執行輸出部分的操作;如果是path 2時無法確定高位字節，輸出比特數量加1，完成重歸一化的過程。將快速重歸一化的過程分成編碼和輸出部分，避免了原重歸一化過程等待輸出的情況，有利于重歸一化處理的并行執行。

2.2 Renorm為2的快速重歸一化算法

Renorm為2的重歸一化算法劃分區間的長度為128，可將整個重歸一化過程劃分成七個區間。區間的劃分標準和結合重歸一化循環結果的方法如下:

a)如果0

b)如果0

c)如果0512，可以得到L的范圍L>256。兩不等式不存在交集，所以這種情況不存在。

d)如果256

e)如果256

f)如果256512(L′=(L-256))，可以得到L的范圍L>512。兩L范圍的交集不存在，故此情況不存在。

g)如果L>512，假設重歸一化0

h)如果L>512，假設重歸一化后256

i)如果L>512，假設重歸一化后L′>512(L′=2(L-512))，可以得到L>768，結合兩L范圍的交集可以得到L>768時，輸出結果L=L-0x0C00，輸出編碼的高位值1。根據bitOutstanding數目確定輸出0的數目，最后輸出一位高位值1。

L在不同的區間作不同的處理，而不需要將編碼區間R左移一位再進行判斷，去除了重歸一化中復雜的循環操作過程。除了384

// interval subdivision

1)

RLPS=TabRangeLPS[δ][ρ]

2)

RMPS=R- RLPS

3)

if(value==valMPS)

4)

R= RMPS

5)

renorm=(range>>8)^1

6)

else

7)

L=L+RMPS

8)

R=RLPS

9)

renorm=renorm_table[(rLPS>> 3) 0x1F]

10)

R<

// renormalization

//L<128區間

11)

if (L<128)

12)

L<<2

13)

putBit(0)

14)

putBit(0)

//128

15)

else if (128

16)

L<<2-0x0200

17)

putBit(0)

18)

bitOutstanding++

//256

19)

else if (256

20)

L<<2-0x0400

21)

bitOutstanding++

22)

putBit(0)

//384

23)

else if (384

24)

L<<2-0x0600

25)

bitOutstanding+2

//512

26)

else if (512

27)

L<<2-0x0800

28)

putBit(1)

29)

putBit(0)

//640

26)

else if (640

27)

L<<2-0x0A00

28)

putBit(1)

29)

bitOutstanding++

//L>768區間

26)

else if (L>768)

27)

L<<2-0x0C00

28)

putBit(1)

29)

putBit(1)

2.3 Renorm大于2的快速重歸一化算法

運用同樣的方法，可以將renorm為3的重歸一化算法劃分區間長度為64，將重歸一化過程分成15個區間。Renorm為4、5、6區間劃分長度分別為32、16、8，它們分別將重歸一化過程分成了31、63、127個不同情況的區間。根據編碼區間的大小和重歸一化次數就可以通過一次重歸一化過程來完成重歸一化過程，避免了復雜的循環過程，提高了重歸一化的速度。同時在重歸一化次數大于2的情況下，在一次重歸一化時間內能夠輸出更多的比特數，提高了常規編碼器的吞吐率。

綜合上述描述，本算法的特征可以歸納如下:

a)重歸一化的循環過程被除去。

b)重歸一化的過程根據重歸一化的次數分成六種情況，每種情況又由不同的區間來決定執行的操作。

c)重歸一化次數不僅決定了重歸一化的區間大小，而且決定了重歸一化輸出的比特數。

d)重歸一化的過程符合H.264標準，并沒有對編碼質量產生影響。

3 實驗結果分析

為了分析本算法的性能，將本文的快速重歸一化算法與原重歸一化算法進行比較，如表1所示。從表1可以看到，一次重歸一化減少的計算并不明顯;一次重歸一化發生于大概率事件中，且一次重歸一化不存在循環，只有一個輸出結果，因此改進效果不明顯。若重歸一化次數越大，那么計算的復雜度越大，使用本算法減少的計算越明顯，編碼時間減少得越多，單位時間向視頻流中輸出的比特數也越多。

表1 快速重歸一化算法與原算法比較

renorm原算法執行操作改進算法執行操作減少操作

1比較操作2次減法操作1次移位操作2次比較操作2次減法操作1次移位操作2次不明顯

2比較操作4次減法操作2次移位操作4次比較操作2次減法操作1次移位操作2次2次比較操作1次減法操作2次移位操作

3比較操作6次減法操作4次移位操作6次比較操作2次減法操作1次移位操作2次4次比較操作3次減法操作4次移位操作

4比較操作8次減法操作6次移位操作8次比較操作2次減法操作1次移位操作2次6次比較操作5次減法操作6次移位操作

5比較操作10次減法操作8次移位操作10次比較操作2次減法操作1次移位操作2次8次比較操作7次減法操作8次移位操作

6比較操作12次減法操作10次移位操作12次比較操作2次減法操作1次移位操作2次10次比較操作9次減法操作10次移位操作

為了測試本算法的性能，在JM10.2將原重歸一化部分替代為本算法的快速重歸一化算法，然后測試重歸一化的次數以及編碼的時間。通過不同的視頻圖像得到的測試結果如表2所示。

表2 快速重歸一化算法實驗結果

視頻名原重歸一化次數本算法重歸一化次數原編碼時間/s現編碼時間/s

foreman5 156 3654 020 0005.9075.749

news10 892 6807 668 2582.6732.293

silent5 454 3954 146 3226.0946.000

clair3 681 9282 846 9445.3295.188

bridge6 474 1794 752 3355.6575.532

tempete13 311 2889 862 0912.2512.029

stefan11 179 5308 268 3332.1032.063

hall5 651 9714 193 1246.0235.875

實驗結果表明，本文提出的算法在減少重歸一化次數的前提下減少了原算法的編碼時間。在統計的視頻中，重歸一化算法次數減少了21.9%~26.7%，與原算法編碼時間比減少了14.5%~33.7%。本文提出的算法通過重歸一化循環次數，劃分不同的區間以除去循環操作，減少了重歸一化次數和編碼時間。

4 結束語

重歸一化是CABAC熵編碼中計算復雜度最大的一個過程。本文從重歸一化循環次數著手，提出了一種基于區間劃分的快速重歸一化算法，免除了重歸一化按位操作的循環過程。實驗結果表明，本文算法可以減少視頻編碼時間，更好地滿足了實時性的要求，有很強的實用價值。

參考文獻:

[1]MARPE D， SCHWARZ H， WIEGAND T. Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard[J]. IEEE Trans on Circuits and Systems for Video Technology， 2003， 13(7):620-636.

[2]OSTERMANN J， BORMANS J， LIST P， et al. Video coding with H.264/AVC: tools， performance， and complexity[J]. IEEE Trans on Circuits and Systems for Video Technology， 2004， 4(1):7-28.

[3]ITU-T. ITU-T H.264建議書[S]. 2005.

[4]曹斌，李云松，劉凱，等. JPEG2000中MQ編碼器的VLSI結構[J]. 西安電子科技大學學報:自然科學版， 2004， 31(5):741-749.

[5]MIN B， YOON S， RA J， et al. Enhanced renorma lization algorithm in MQ-Coder of JPEG2000[C]//Proc of IEEE International Sympo-sium on Information Technology Convergence. Washington DC:IEEE Computer Society， 2007:213-216.

[6]JIA Yun-wei， YANG En-hui. A greedy renormalization method for arithmetic coding[J]. IEEE Trans on Communications， 2007， 55(8):1494-1503.

[7]Reference software of JVT. JM10.2 [M/OL]. 2004 [2009-04-10]. http://bs.hhi.de/suehring/tml/download/jm10.2.zip.

[8]SALOMON D， MOTTA G， BRYANT D. Data compression: the complete reference[M]. Berlin:Springer， 2009.

[9]黃波，賈蓉，樊豐. H.264中的CABAC熵編碼研究[J]. 中國有線電視，2007(8):758-763.