參考
知乎 張濤的 算術編碼（轉載加筆記）
【H.264/AVC視頻編解碼技術詳解】十八：算術編碼的基本原理與實現(xiàn)

按：最近復習了下算術編碼，算術編碼的核心思想是為整個輸入序列（而不是單個字符）分配碼字，因而平均每字符可以分配長度小于1的碼字。找到一篇比較適合新手學習的文章，加入些自己的理解，算是個讀書心得吧。

一、Huffman 編碼的缺點

1.最小碼字長度為1
Huffman 編碼使用整數(shù)個二進制位對符號進行編碼，這種方法在許多情況下無法得到最優(yōu)的壓縮效果。假設某個字符的出現(xiàn)概率為 80%，該字符事實上只需要 -log2(0.8) = 0.322 位編碼，但 Huffman 編碼一定會為其分配一位 0 或一位 1 的編碼?？梢韵胂螅麄€信息的 80% 在壓縮后都幾乎相當于理想長度的 3 倍左右，壓縮效果可想而知。

2.Huffman 編碼需要預先掃描所有符號，得到總體的概率分布并存儲更新，額外增加了復雜度。

難道真的能只輸出 0.322 個 0 或 0.322 個 1 嗎？是用剪刀把計算機存儲器中的二進制位剪開嗎？計算機真有這樣的特異功能嗎？慢著慢著，我們不要被表面現(xiàn)象所迷惑，其實，在這一問題上，我們只要換一換腦筋，從另一個角度……哎呀，還是想不通，怎么能是半個呢？好了，不用費心了，數(shù)學家們也不過是在十幾年前才想到了算術編碼這種神奇的方法，還是讓我們虛心地研究一下他們究竟是從哪個角度找到突破口的吧。

二、算術編碼例子 輸出：一個小數(shù)

更神奇的事情發(fā)生了，算術編碼對整條信息（無論信息有多么長），其輸出僅僅是一個數(shù)，而且是一個介于 0 和 1 之間的二進制小數(shù)。例如算術編碼對某條信息的輸出為 1010001111，那么它表示小數(shù) 0.1010001111，也即十進制數(shù) 0.64。

咦？怎么一會兒是表示半個二進制位，一會兒又是輸出一個小數(shù)，算術編碼怎么這么古怪呀？不要著急，我們借助下面一個簡單的例子來闡釋算術編碼的基本原理。為了表示上的清晰，我們暫時使用十進制表示算法中出現(xiàn)的小數(shù)，這絲毫不會影響算法的可行性。

1.壓縮

考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的信息為 bccb。

在沒有開始壓縮進程之前，假設我們對 a b c 三者在信息中的出現(xiàn)概率一無所知（我們采用的是自適應模型），沒辦法，我們暫時認為三者的出現(xiàn)概率相等，也就是都為 1/3，我們將 0 - 1 區(qū)間按照概率的比例分配給三個字符，即 a 從 0.0000 到 0.3333，b 從 0.3333 到 0.6667，c 從 0.6667 到 1.0000。用圖形表示就是：

+-- 1.0000 | Pc = 1/3 | | +-- 0.6667 | Pb = 1/3 | | +-- 0.3333 | Pa = 1/3 | | +-- 0.0000

現(xiàn)在我們拿到第一個字符 b，讓我們把目光投向 b 對應的區(qū)間 0.3333 - 0.6667。這時由于多了字符 b，三個字符的概率分布變成：Pa = 1/4，Pb = 2/4，Pc = 1/4。好，讓我們按照新的概率分布比例劃分 0.3333 - 0.6667 這一區(qū)間，劃分的結果可以用圖形表示為：

+-- 0.6667 Pc = 1/4 | +-- 0.5834 | | Pb = 2/4 | | | +-- 0.4167 Pa = 1/4 | +-- 0.3333

接著我們拿到字符 c，我們現(xiàn)在要關注上一步中得到的 c 的區(qū)間 0.5834 - 0.6667。新添了 c 以后，三個字符的概率分布變成 Pa = 1/5，Pb = 2/5，Pc = 2/5。我們用這個概率分布劃分區(qū)間 0.5834 - 0.6667：

+-- 0.6667 | Pc = 2/5 | | +-- 0.6334 | Pb = 2/5 | | +-- 0.6001 Pa = 1/5 | +-- 0.5834

現(xiàn)在輸入下一個字符 c，三個字符的概率分布為：Pa = 1/6，Pb = 2/6，Pc = 3/6。我們來劃分 c 的區(qū)間 0.6334 - 0.6667：

+-- 0.6667 | | Pc = 3/6 | | | +-- 0.6501 | Pb = 2/6 | | +-- 0.6390 Pa = 1/6 | +-- 0.6334

輸入最后一個字符 b，因為是最后一個字符，不用再做進一步的劃分了，上一步中得到的 b 的區(qū)間為 0.6390 - 0.6501，好，讓我們在這個區(qū)間內隨便選擇一個容易變成二進制的數(shù)，例如 0.64，將它變成二進制 0.1010001111，去掉前面沒有太多意義的 0 和小數(shù)點，我們可以輸出 1010001111，這就是信息被壓縮后的結果，我們完成了一次最簡單的算術壓縮過程。

2.解壓

怎么樣，不算很難吧？可如何解壓縮呢？那就更簡單了。解壓縮之前我們仍然假定三個字符的概率相等，并得出上面的第一幅分布圖。解壓縮時我們面對的是二進制流 1010001111，我們先在前面加上 0 和小數(shù)點把它變成小數(shù) 0.1010001111，也就是十進制 0.64。這時我們發(fā)現(xiàn) 0.64 在分布圖中落入字符 b 的區(qū)間內，我們立即輸出字符 b，并得出三個字符新的概率分布。類似壓縮時采用的方法，我們按照新的概率分布劃分字符 b 的區(qū)間。在新的劃分中，我們發(fā)現(xiàn) 0.64 落入了字符 c 的區(qū)間，我們可以輸出字符 c。同理，我們可以繼續(xù)輸出所有的字符，完成全部解壓縮過程（注意，為了敘述方便，我們暫時回避了如何判斷解壓縮結束的問題，實際應用中，可以通過加休止符的方式解決）。

現(xiàn)在把教程拋開，仔細回想一下，直到理解了算術壓縮基本原理，并產(chǎn)生許多新的問題為止。

3.真的能接近極限嗎？

現(xiàn)在你一定明白了一些東西，也一定有了不少新問題，沒有關系，讓我們一個一個解決。

首先，我們曾反復強調，算術壓縮可以表示小數(shù)個二進制位，并由此可以接近無損壓縮的熵極限，怎么從上面的描述中沒有看出來呢？

算術編碼實際上采用了化零為整的思想來表示小數(shù)個二進制位，我們確實無法精確表示單個小數(shù)位字符，但我們可以將許多字符集中起來表示，僅僅允許在最后一位有些許的誤差。

結合上面的簡單例子考慮，我們每輸入一個符號，都對概率的分布表做一下調整，并將要輸出的小數(shù)限定在某個越來越小的區(qū)間范圍內。對輸出區(qū)間的限定是問題的關鍵所在，例如，我們輸入第一個字符 b 時，輸出區(qū)間被限定在 0.3333 - 0.6667 之間，我們無法決定輸出值得第一位是 3、4、5 還是 6，也就是說，b 的編碼長度小于一個十進制位（注意我們用十進制講解，和二進制不完全相同），那么我們暫時不決定輸出信息的任何位，繼續(xù)輸入下面的字符。直到輸入了第三個字符 c 以后，我們的輸出區(qū)間被限定在 0.6334 - 0.6667 之間，我們終于知道輸出小數(shù)的第一位（十進制）是 6，但仍然無法知道第二位是多少，也即前三個字符的編碼長度在 1 和 2 之間。等到我們輸入了所有字符之后，我們的輸出區(qū)間為 0.6390 - 0.6501，我們始終沒有得到關于第二位的確切信息，現(xiàn)在我們明白，輸出所有的 4 個字符，我們只需要 1 點幾個十進制位，我們唯一的選擇是輸出 2 個十進制位 0.64。這樣，我們在誤差不超過 1 個十進制位的情況下相當精確地輸出了所有信息，很好地接近了熵值（需要注明的是，為了更好地和下面的課程接軌，上面的例子采用的是 0 階自適應模型，其結果和真正的熵值還有一定的差距）。

4.小數(shù)有多長？

你一定已經(jīng)想到，如果信息內容特別豐富，我們要輸出的小數(shù)將會很長很長，我們該如何在內存中表示如此長的小數(shù)呢？

其實，沒有任何必要在內存中存儲要輸出的整個小數(shù)。我們從上面的例子可以知道，在編碼的進行中，我們會不斷地得到有關要輸出小數(shù)的各種信息。具體地講，當我們將區(qū)間限定在 0.6390 - 0.6501 之間時，我們已經(jīng)知道要輸出的小數(shù)第一位（十進制）一定是 6，那么我們完全可以將 6 從內存中拿掉，接著在區(qū)間 0.390 - 0.501 之間繼續(xù)我們的壓縮進程。內存中始終不會有非常長的小數(shù)存在。使用二進制時也是一樣的，我們會隨著壓縮的進行不斷決定下一個要輸出的二進制位是 0 還是 1，然后輸出該位并減小內存中小數(shù)的長度。

5.靜態(tài)模型如何實現(xiàn)？

我們知道上面的簡單例子采用的是自適應模型，那么如何實現(xiàn)靜態(tài)模型呢？其實很簡單。對信息 bccb 我們統(tǒng)計出其中只有兩個字符，概率分布為 Pb = 0.5，Pc = 0.5。我們在壓縮過程中不必再更新此概率分布，每次對區(qū)間的劃分都依照此分布即可，對上例也就是每次都平分區(qū)間。這樣，我們的壓縮過程可以簡單表示為：

輸出區(qū)間的下限 輸出區(qū)間的上限 --------------------------------------------------
壓縮前 0.0 1.0 輸入 b 0.0 0.5 輸入 c 0.25 0.5 輸入 c 0.375 0.5 輸入 b 0.375 0.4375

我們看出，最后的輸出區(qū)間在 0.375 - 0.4375 之間，甚至連一個十進制位都沒有確定，也就是說，整個信息根本用不了一個十進制位。如果我們改用二進制來表示上述過程的話，我們會發(fā)現(xiàn)我們可以非常接近該信息的熵值（有的讀者可能已經(jīng)算出來了，該信息的熵值為 4 個二進制位）。

6.為什么用自適應模型？

既然我們使用靜態(tài)模型可以很好地接近熵值，為什么還要采用自適應模型呢？

要知道，靜態(tài)模型無法適應信息的多樣性，例如，我們上面得出的概率分布沒法在所有待壓縮信息上使用，為了能正確解壓縮，我們必須再消耗一定的空間保存靜態(tài)模型統(tǒng)計出的概率分布，保存模型所用的空間將使我們重新遠離熵值。其次，靜態(tài)模型需要在壓縮前對信息內字符的分布進行統(tǒng)計，這一統(tǒng)計過程將消耗大量的時間，使得本來就比較慢的算術編碼壓縮更加緩慢。

另外還有最重要的一點，對較長的信息，靜態(tài)模型統(tǒng)計出的符號概率是該符號在整個信息中的出現(xiàn)概率，而自適應模型可以統(tǒng)計出某個符號在某一局部的出現(xiàn)概率或某個符號相對于某一上下文的出現(xiàn)概率，換句話說，自適應模型得到的概率分布將有利于對信息的壓縮（可以說結合上下文的自適應模型的信息熵建立在更高的概率層次上，其總熵值更?。?，好的基于上下文的自適應模型得到的壓縮結果將遠遠超過靜態(tài)模型。

例如一段碼流，某符號在前面出現(xiàn)概率較大而后面概率小，甚至忽大忽小，采用自適應模型就可以更好的適應這樣的變動，壓縮效率會比靜態(tài)模型更高。主流視頻編碼標準如H.264/H.265都使用自適應模型。

7.自適應模型的階

我們通常用“階”(order)這一術語區(qū)分不同的自適應模型。本章開頭的例子中采用的是 0 階自適應模型，也就是說，該例子中統(tǒng)計的是符號在已輸入信息中的出現(xiàn)概率，沒有考慮任何上下文信息。

如果我們將模型變成統(tǒng)計符號在某個特定符號后的出現(xiàn)概率，那么，模型就成為了 1 階上下文自適應模型。舉例來說，我們要對一篇英文文本進行編碼，我們已經(jīng)編碼了 10000 個英文字符，剛剛編碼的字符是 t，下一個要編碼的字符是 h。我們在前面的編碼過程中已經(jīng)統(tǒng)計出前 10000 個字符中出現(xiàn)了 113 次字母 t，其中有 47 個 t 后面跟著字母 h。我們得出字符 h 在字符 t 后的出現(xiàn)頻率是 47/113，我們使用這一頻率對字符 h 進行編碼，需要 -log2(47/113) = 1.266 位。

對比 0 階自適應模型，如果前 10000 個字符中 h 的出現(xiàn)次數(shù)為 82 次，則字符 h 的概率是 82/10000，我們用此概率對 h 進行編碼，需要 -log2(82/10000) = 6.930 位?？紤]上下文因素的優(yōu)勢顯而易見。

我們還可以進一步擴大這一優(yōu)勢，例如要編碼字符 h 的前兩個字符是 gt，而在已經(jīng)編碼的文本中 gt 后面出現(xiàn) h 的概率是 80%，那么我們只需要 0.322 位就可以編碼輸出字符 h。此時，我們使用的模型叫做 2 階上下文自適應模型。

最理想的情況是采用 3 階自適應模型。此時，如果結合算術編碼，對信息的壓縮效果將達到驚人的程度。采用更高階的模型需要消耗的系統(tǒng)空間和時間至少在目前還無法讓人接受，使用算術壓縮的應用程序大多數(shù)采用 2 階或 3 階的自適應模型。

8.轉義碼的作用

使用自適應模型的算術編碼算法必須考慮如何為從未出現(xiàn)過的上下文編碼。例如，在 1 階上下文模型中，需要統(tǒng)計出現(xiàn)概率的上下文可能有 256 * 256 = 65536 種，因為 0 - 255 的所有字符都有可能出現(xiàn)在 0 - 255 個字符中任何一個之后。當我們面對一個從未出現(xiàn)過的上下文時（比如剛編碼過字符 b，要編碼字符 d，而在此之前，d 從未出現(xiàn)在 b 的后面），該怎樣確定字符的概率呢？

比較簡單的辦法是在壓縮開始之前，為所有可能的上下文分配計數(shù)為 1 的出現(xiàn)次數(shù)，如果在壓縮中碰到從未出現(xiàn)的 bd 組合，我們認為 d 出現(xiàn)在 b 之后的次數(shù)為 1，并可由此得到概率進行正確的編碼。使用這種方法的問題是，在壓縮開始之前，在某上下文中的字符已經(jīng)具有了一個比較小的頻率。例如對 1 階上下文模型，壓縮前，任意字符的頻率都被人為地設定為 1/65536，按照這個頻率，壓縮開始時每個字符要用 16 位編碼，只有隨著壓縮的進行，出現(xiàn)較頻繁的字符在頻率分布圖上占據(jù)了較大的空間后，壓縮效果才會逐漸好起來。對于 2 階或 3 階上下文模型，情況就更糟糕，我們要為幾乎從不出現(xiàn)的大多數(shù)上下文浪費大量的空間。

我們通過引入“轉義碼”來解決這一問題?！稗D義碼”是混在壓縮數(shù)據(jù)流中的特殊的記號，用于通知解壓縮程序下一個上下文在此之前從未出現(xiàn)過，需要使用低階的上下文進行編碼。

舉例來講，在 3 階上下文模型中，我們剛編碼過 ght，下一個要編碼的字符是 a，而在此之前，ght 后面從未出現(xiàn)過字符 a，這時，壓縮程序輸出轉義碼，然后檢查 2 階的上下文表，看在此之前 ht 后面出現(xiàn) a 的次數(shù)；如果 ht 后面曾經(jīng)出現(xiàn)過 a，那么就使用 2 階上下文表中的概率為 a 編碼，否則再輸出轉義碼，檢查 1 階上下文表；如果仍未能查到，則輸出轉義碼，轉入最低的 0 階上下文表，看以前是否出現(xiàn)過字符 a；如果以前根本沒有出現(xiàn)過 a，那么我們轉到一個特殊的“轉義”上下文表，該表內包含 0 - 255 所有符號，每個符號的計數(shù)都為 1，并且永遠不會被更新，任何在高階上下文中沒有出現(xiàn)的符號都可以退到這里按照 1/256 的頻率進行編碼。

“轉義碼”的引入使我們擺脫了從未出現(xiàn)過的上下文的困擾，可以使模型根據(jù)輸入數(shù)據(jù)的變化快速調整到最佳位置，并迅速減少對高概率符號編碼所需要的位數(shù)。

9.存儲空間問題

在算術編碼高階上下文模型的實現(xiàn)中，對內存的需求量是一個十分棘手的問題。因為我們必須保持對已出現(xiàn)的上下文的計數(shù)，而高階上下文模型中可能出現(xiàn)的上下文種類又是如此之多，數(shù)據(jù)結構的設計將直接影響到算法實現(xiàn)的成功與否。

在 1 階上下文模型中，使用數(shù)組來進行出現(xiàn)次數(shù)的統(tǒng)計是可行的，但對于 2 階或 3 階上下文模型，數(shù)組大小將依照指數(shù)規(guī)律增長，現(xiàn)有計算機的內存滿足不了我們的要求。

比較聰明的辦法是采用樹結構存儲所有出現(xiàn)過的上下文。利用高階上下文總是建立在低階上下文的基礎上這一規(guī)律，我們將 0 階上下文表存儲在數(shù)組中，每個數(shù)組元素包含了指向相應的 1 階上下文表的指針，1 階上下文表中又包含了指向 2 階上下文表的指針……由此構成整個上下文樹。樹中只有出現(xiàn)過的上下文才擁有已分配的節(jié)點，沒有出現(xiàn)過的上下文不必占用內存空間。在每個上下文表中，也無需保存所有 256 個字符的計數(shù)，只有在該上下文后面出現(xiàn)過的字符才擁有計數(shù)值。由此，我們可以最大限度地減少空間消耗。

10.關于CABAC（原創(chuàng)）

CABAC被視頻標準H.264/H.265所采用，對量化后的系數(shù)進一步的壓縮，測試表明壓縮后可以節(jié)省10-15%的碼率。CABAC可以分為二值化、上下文建模和二進制算術編碼三個步驟。

其中上下文建模相當于把整段碼流進行了再次的細分，把相同條件下的字符bin（比如塊大小/亮度色度/語法元素/掃描方式/周圍情況等）歸屬于某個context，形成一個比較獨立的子隊列而進行編碼，其更新只與當前的狀態(tài)和當前字符是否MPS有關（換句話說，只和歷史該子隊列編碼字符和當前字符有關），而與別的子隊列/字符是無關的。當然輸出碼字往往是根據(jù)規(guī)則而“混”在一起的。

對于某個子隊列，context的狀態(tài)會隨著當前編碼符號進行更新，以更貼近目前的實際概率。同時比較其范圍，移出上下限相同的位的比特進入碼流，再編碼下一個符號。一般而言，若當前編碼符號為LPS，由于其概率小于0.5，根據(jù)自信息計算有1-5比特要移出；而如果是MPS符號，其自信息是不到1比特的，這時候結合之前編碼情況決定是否移出比特。目前在碼率估計方面，就可以利用查表來估計每個符號對應的碼字長度，從而省去二進制算術編碼環(huán)節(jié)。

CABAC雖然性能很好，但也存在以下幾點不足：

• 復雜度過高，不易并行處理。存在塊級依賴（左/上角的塊沒有碼率估計/熵編碼，后繼塊就無法得到更新后的狀態(tài)，從而無法開始碼率估計/熵編碼）、Bin級依賴（同一個子隊列的bin存在前后依賴性，后繼的bin要等前面bin編完后才能得到更新后的上下文狀態(tài)）以及編碼的幾個環(huán)節(jié)依賴，這些依賴性會影響編碼器的并行實現(xiàn)。

• 計算精度問題。為簡化計算，CABAC采用128個狀態(tài)來近似，根據(jù)原來狀態(tài)和當前符號性質查表得到下個狀態(tài)。這個過程中會有一些精度的損失。另外，如果當一連串的MPS到來，狀態(tài)到達62后就不會繼續(xù)改變，只會“原地踏步”。換句話說，當概率到達0.01975時就不會隨著符號繼續(xù)變小，這樣會影響壓縮效率。

• Context的設計問題。部分context利用頻率很低，在測試中平均一幀都用不到幾次，而有的context使用頻率很高，需要進一步的優(yōu)化。

PS：當年學視頻編碼的CABAC，還真的有點暈頭轉向的。理解是個循序漸進的過程，水到渠成吧~~

三、更多關于CABAC

參考
【H.264/AVC視頻編解碼技術詳解】十九、熵編碼(5)：CABAC語法元素的二值化
【H.264/AVC視頻編解碼技術詳解】二十一、熵編碼(6)：CABAC的上下文環(huán)境
CABAC編碼解析
CABAC熵編碼
H.264協(xié)議CABAC熵編碼學習(一)
H.264協(xié)議CABAC熵編碼學習(二)
H.264協(xié)議CABAC熵編碼學習(三)
H.264協(xié)議CABAC熵編碼學習(四)
H.264協(xié)議CABAC熵編碼學習(五)

四、CAVLC

參考
【H.264/AVC視頻編解碼技術詳解】十三、熵編碼算法（3）：CAVLC原理
【H.264/AVC視頻編解碼技術詳解】十三、熵編碼算法（4）：H.264使用CAVLC解析宏塊的殘差數(shù)據(jù)
1.引言
在我們已經(jīng)實現(xiàn)的H.264碼流結構（如NAL Unit、Slice Header等）的解析中，大多使用定長編碼或者指數(shù)哥倫布編碼實現(xiàn)。而例如預測殘差等占據(jù)碼流大量體積的數(shù)據(jù)則必須使用壓縮率更高的算法，如CAVLC和CABAC等。前者是我們將在本文中討論的內容，后者將在后續(xù)內容中詳述。

2.CAVLC的基本原理
我們知道，CAVLC的全稱叫做“上下文自適應的變長編碼Context-based Adaptive Variable Length Coding”。所謂“上下文自適應”，說明了CAVLC算法不是像指數(shù)哥倫布編碼那樣采用固定的碼流-碼字映射的編碼，而是一種動態(tài)編碼的算法，因而壓縮比遠遠超過固定變長編碼UVLC等算法。

在H.264標準中，CAVLC主要用于預測殘差的編碼。在本系列第二篇博文中我們給出了H.264的編碼流圖，其中可知，熵編碼的輸入為幀內/幀間預測殘差經(jīng)過變換-量化后的系數(shù)矩陣。以4×4大小的系數(shù)矩陣為例，經(jīng)過變換-量化后，矩陣通常呈現(xiàn)以下特性：

• 經(jīng)過變換量化后的矩陣通常具有稀疏的特性，即矩陣中大多數(shù)的數(shù)據(jù)已0為主。CAVLC可以通過游程編碼高效壓縮連續(xù)的0系數(shù)串；
• 經(jīng)過zig-zag掃描的系數(shù)矩陣的最高頻非0系數(shù)通常是值為±1的數(shù)據(jù)串。CAVLC可以通過傳遞連續(xù)的+1或-1的長度來高效編碼高頻分量；
• 非零系數(shù)的幅值通常在靠近DC（即直流分量）部分較大，而在高頻部分較?。?/li>
• 矩陣內非0系數(shù)的個數(shù)同相鄰塊相關；

鑒于上述的特性3和4，針對待編碼的系數(shù)在系數(shù)矩陣中不同的位置，以及相鄰塊的有關信息，在編碼時采用不同的碼表進行編碼。CAVLC的這種特性，體現(xiàn)了命名中的“上下文自適應”的方法。

3. CAVLC的編碼流程
   在CAVLC中，熵編碼不是像哈夫曼編碼等算法一樣針對某一個碼元進行編碼，而是針對一個系數(shù)矩陣進行。假設我們希望對一個如下變換系數(shù)塊進行CAVLC編碼：

{
    3,  2, -1,  0,
    1,  0,  1,  0,
    -1, 0,  0,  0,
    0,  0,  0,  0,
}

對于一個4×4大小的變換系數(shù)矩陣進行CAVLC編碼，首先需要對其進行掃描，將二維矩陣轉化為一維數(shù)組。如前一節(jié)所講，掃描按照zig-zag順序進行，即按照如下順序：

image.png

因此，掃描之后變換系數(shù)將進行重新排列，得到的結果為：

[3, 2, 1, -1, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

在編碼過程中需要注意以下重要的語法元素：

• 非零系數(shù)的個數(shù)(TotalCoeffs)：取值范圍為[0, 16]，即當前系數(shù)矩陣中包括多少個非0值的元素；
• 拖尾系數(shù)的個數(shù)(TrailingOnes)：取值范圍為[0, 3]，表示最高頻的幾個值為±1的系數(shù)的個數(shù)。拖尾系數(shù)最多不超過3個，若超出則只有最后3個被認為是拖尾系數(shù)，其他被作為普通的非0系數(shù)；
• 拖尾系數(shù)的符號：以1 bit表示，0表示+，1表示-；
• 當前塊值(numberCurrent)：用于選擇編碼碼表，由上方和左側的相鄰塊的非零系數(shù)個數(shù)計算得到。設當前塊值為nC，上方相鄰塊非零系數(shù)個數(shù)為nA，左側相鄰塊非零系數(shù)個數(shù)為nB，計算公式為nC = round((nA + nB)/2);對于色度的直流系數(shù)，nC = -1;
• 普通非0系數(shù)的幅值(level)：幅值的編碼分為prefix和suffix兩個部分進行編碼。編碼過程按照反序編碼，即從最高頻率非零系數(shù)開始。
• 最后一個非0系數(shù)之前的0的個數(shù)(TotalZeros);
• 每個非0系數(shù)之前0的個數(shù)(RunBefore):按照反序編碼，即從最高頻非零系數(shù)開始；對于最后一個非零系數(shù)（即最低頻的非零系數(shù)）前的0的個數(shù)，以及沒有剩余的0系數(shù)需要編碼時，不需要再繼續(xù)進行編碼。

在上述各類型數(shù)據(jù)中，編碼非零系數(shù)的level相對最為復雜。其主要過程為：

• 確定suffixLength的值：
  • suffixLength初始化：通常情況下初始化為0；當TotalCoeffs大于10且TrailingOnes小于3時，初始化為1；
  • 若已經(jīng)編碼好的非零系數(shù)大于閾值，則suffixLength加1；該閾值定義為3 << ( suffixLength ? 1 )；編碼第一個level后，suffixLength應加1；

• 將有符號的Level值轉換為無符號的levelCode:

  • 若level > 0，levelCode = (level << 1) - 2;
  • 若level < 0，levelCode = -(level << 1) - 1;

• 編碼level_prefix：level_prefix的計算方法為：level_prefix = levelCode/(1 << suffixLength);level_prefix到碼流的對應關系由9-6表示；

• 確定后綴的長度：后綴的長度levelSuffixSize通常情況下等于suffixLength，例外情況有：

  • level_prefix = 14時，suffixLength = 0, levelSuffixSize = 4;
  • level_prefix = 15時，levelSuffixSize = 12;

• 計算level_suffix的值：level_suffix = levelCode%(1 << suffixLength);

• 按照levelSuffixSize的長度編碼level_suffix;

在上述的系數(shù)矩陣中，非零系數(shù)個數(shù)TotalCoeffs=6,拖尾系數(shù)個數(shù)TrailingOnes=3,最后一個非零系數(shù)之前0的個數(shù)TotalZeros=2;假設nC=0。

• 在H.264標準協(xié)議文檔的表9-5中查得，coeff_token的值為0x00000100;

• 編碼拖尾系數(shù)的符號，從高頻到低頻，拖尾系數(shù)符號為+、-、-，因此符號的碼流為011；

• 編碼非零系數(shù)的幅值，三個普通非零系數(shù)分別為1、2、3；

  • 編碼1：suffixLength初始化為0；levelCode=0;level_prefix=0，查表得對應的碼流為1；suffixLength=0，因此不對后綴編碼；
  • 編碼2：suffixLength自增1等于1；levelCode=2;level_prefix=1，查表可知對應的碼流為01;suffixLength=1，level_suffix=0，因此后綴碼流為0；
  • 編碼3：suffixLength不滿足自增條件，依然為1；levelCode=4;level_prefix=2，查表可知對應的碼流為001；suffixLength=1，level_suffix=0，因此后綴碼流為0；
  • 綜上所述，非零系數(shù)的幅值部分的碼流為10100010；

• 編碼最后非零系數(shù)之前0的個數(shù)TotalZeros： TotalCoeffs=6,TotalZeros=2時，在表9-7中可知碼流為111；

• 編碼每個非零系數(shù)前0的個數(shù)：從高頻到低頻，每個非零系數(shù)前0的總個數(shù)(zerosLeft)分別為2、1、0、0、0、0，每個非0系數(shù)前連續(xù)0的個數(shù)(run_before)分別為1、1、0、0、0、0。根據(jù)標準文檔表9-10可得：

  • run_before=1，zerosLeft=2，對應碼流為01；
  • run_before=1，zerosLeft=1，對應碼流為0；
  • 所有的0系數(shù)都已經(jīng)編碼完成，無需再繼續(xù)進行編碼；

綜上所述，整個4×4系數(shù)矩陣經(jīng)過CAVLC編碼之后，輸出碼流為：0000010001110100010111010。

五、CAVLC CABAC對比

H.264 是由國際電信聯(lián)盟（ITU）和國際標準化組織（ISO）共同制定的新一代視頻編碼標準。 它有兩個熵編碼方案：一個是從可變長編碼發(fā)展而來的上下文自適應可變長編碼 （CAVLC）；另一個是從算術編碼發(fā)展而來的基于上下文的自適應二進制算術編碼（CABAC）。

CAVLC 是從概率統(tǒng)計分布模型得出的， 應用單一的碼表，沒有考慮編碼符號間的相關性， 不允許根據(jù)實際符號的統(tǒng)計特性進行調整。 而實際符號的統(tǒng)計特性會隨著空間、時間、視頻源、編碼條件的變化而發(fā)生變化，CAVLC 用于高比特率視頻流信息時性能不理想。

CABAC 充分利用視頻流的上下文信息，對不同的視頻流能夠自適應，克服了可變長編碼的缺點，且算術編碼在實際應用中的計算精度和計算復雜度，提高了編碼效率。 基于以上的優(yōu)點,CABAC 被 H.264 標 準 采 納， 成 為 H.264 中兩個熵編碼方案之一。

CABAC 是一種高效的熵編碼，它充分利用了視頻流的統(tǒng)計和相關特性， 并且從試驗結果可以看出，CABAC 編碼效率高于CAVLC。 CAVLC 雖然利用了上下文信息，但是由于變長編碼的固有缺點，限制了壓縮率的進一步提升。 CABAC 的速度雖然不如 CAVLC，但是在芯片技術飛速發(fā)展的今天，降低碼率比提高速度顯得非常重要。 CABAC 作為 H.264 標準的熵編碼方案，它對 H.264 的低碼率做了很大貢獻，這對于發(fā)展 H.264 在 3G 無線通信方面的應用非常重要。

H.265/HEVC(High Efficiency Video coding)是目前正在制定中的下一代視頻編碼標準。它同樣是由ITU和MPEG聯(lián)合制定。與H. 264視頻標準相比，它在保證相同圖像質量的前提下，可以將視頻的碼率降低50%。為了達到這一目的，它的計算復雜度也將上升3-4倍。 HEVC有望成為當前H. 264視頻編碼標準的繼承者，在下一個5到10年的時間取代H. 264成為新的主流視頻標準。為了提高編碼效率，HEVC中的熵編碼將只采用高效率的CABAC，不再使用CAVLC。