前文參考之適應性二元算術編碼

(重定向自CABAC

前文參考之適應性二元算術編碼Context-based Adaptive Binary Arithmetic Coding,簡稱CABAC)是視訊壓縮標準H.264采用的演算法。

原理

CABAC分為三個部份,Binarizer, Context Modeler和Arithmetic Coding Engine。CABAC的設計概念,對於發生機率P(x)>0.5的事件有效地編碼,改進了傳統算術編碼(Arithmetic coding)需要大量的乘法運算的問題,而在效能與壓縮效率上取得相當大的改善空間。CABAC的生命週期是slice,CABAC與UVLC最大的不同點在於其編碼方式具有適應性(adaptive),對於編碼過程中各個符號(symbol)出現的機率會一直動態地去統計並更新。

Arithmetic Coding中以Low及Range表示壓縮過程的範圍。Binarizer可將Codec分析後的句法元素(Syntax Element),轉化成為位元字串(bin string),每個位元稱為一個bin,而bin即為傳給Arithmetic Coder的Symbol。CABAC的符號(symbol)只有0或1兩種,所以bin就是0或1。如果原本就是binary value,就不需要binarization。此一步驟的輸出稱為bin string。接下來要把這些bin sting做arithmetic coding,每個bin可能會有某種機率分佈,如果不具有分佈(regular),即是bin value,就進行Bypass Coding Engine,如果是regular,就前往Context Modeler選擇目前這個bin的model。

Context Modeler再針對所要壓縮的bin去作機率的估測(Probability Estimation)和更新(Binary Arithmetic Coding)。Regular Coding Engine利用bin的model和Context Index查表,並透過Markov Chain Model建表,隨時更新Low與Range的數值,更可得出MPS(Most Probable Symbol)與Probability State。MPS表示機率大於0.5,另一個LPS(Least Probable Symbol)是機率小於0.5。

Bypass Coding Engine和Regular Coding Engine都是Binary Arithmetic coder,均會產生coded bits,形成bitstream,最後輸出。

CABAC不同於Various Length Coding,因此更能夠接近資料的熵編碼(Entropy)。CABAC每個symbol和bitstream不再有一對一的絕對關係,N個symbol有可能使用小於N個bit.在機率估計準確的前提下,CABAC的算術編碼(Arithmetic Coding)的壓縮率可以大於Huffman Coding,也就是說CABAC善用了統計學的期望值,壓縮的bin機率相當接近0.5,表示預測的效率相當低,可直接進行Bypass,直接輸出,以降低memory access與計算。

目前CABAC不支援Baseline以及Extended profiles.另外,CABAC面臨的問題是在於由於循序處理造成資料依存性(Data Dependency)偏高。

參考書目

  • H.264/MPEG-4 Part 10 White Paper, two page summary of MPEG CABAC, October 2002 [1]
  • E. G. Richardson, Iain. H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia. Chichester: John Wiley & Sons Ltd. 2003. 

外部連結

參見