【H.264/AVC視訊編解碼技術具體解釋】十三、熵編碼算法（3）：CAVLC原理

​

上下文自适應的變長編碼(Context-based Adaptive Variable Length Coding, CAVLC)

1. 引言

在前述的幾章節的博文/視訊中，我們已經了解到熵編碼是利用資訊的統計備援進行資料壓縮的無損編碼方法。而且已經讨論過了熵編碼的基本原理、H.264中使用的文法元素解析算法“指數哥倫布編碼”的算法與實踐：

在我們已經實作的H.264碼流結構（如NAL Unit、Slice Header等）的解析中，大多使用定長編碼或者指數哥倫布編碼實作。而比如預測殘差等占領碼流大量體積的資料則必須使用壓縮率更高的算法，如CAVLC和CABAC等。前者是我們将在本文中讨論的内容。後者将在興許内容中詳述。

2. CAVLC的基本原理

我們知道。CAVLC的全稱叫做“上下文自适應的變長編碼Context-based Adaptive Variable Length Coding”。所謂“上下文自适應”，說明了CAVLC算法不是像指數哥倫布編碼那樣採用固定的碼流-碼字映射的編碼，而是一種動态編碼的算法，因而壓縮比遠遠超過固定變長編碼UVLC等算法。

在H.264标準中，CAVLC主要用于預測殘差的編碼。

在​​本系列第二篇博文​​中我們給出了H.264的編碼流圖，當中可知，熵編碼的輸入為幀内/幀間預測殘差經過變換-量化後的系數矩陣。

以4×4大小的系數矩陣為例，經過變換-量化後，矩陣通常呈現下面特性：

1. 經過變換量化後的矩陣通常具有稀疏的特性。即矩陣中大多數的資料已0為主。CAVLC能夠通過遊程編碼高效壓縮連續的0系數串；
2. 經過zig-zag掃描的系數矩陣的最高頻非0系數一般是值為±1的資料串。CAVLC能夠通過傳遞連續的+1或-1的長度來高效編碼高頻分量；
3. 非零系數的幅值通常在靠近DC（即直流分量）部分較大。而在高頻部分較小。
4. 矩陣内非0系數的個數同相鄰塊相關；

鑒于上述的特性3和4，針對待編碼的系數在系數矩陣中不同的位置，以及相鄰塊的有關資訊，在編碼時採用不同的碼表進行編碼。CAVLC的這樣的特性。展現了命名中的“上下文自适應”的方法。

3. CAVLC的編碼流程

在CAVLC中，熵編碼不是像哈夫曼編碼等算法一樣針對某一個碼元進行編碼，而是針對一個系數矩陣進行。如果我們希望對一個例如以下變換系數塊進行CAVLC編碼：

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

對于一個4×4大小的變換系數矩陣進行CAVLC編碼。首先須要對其進行掃描。将二維矩陣轉化為一維數組。

如前一節所講，掃描依照zig-zag順序進行。即依照例如以下順序：

是以，掃描之後變換系數将進行又一次排列，得到的結果為：

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

在編碼過程中須要注意下面重要的文法元素：

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

在上述各類型資料中，編碼非零系數的level相對最為複雜。

其主要過程為：

1. 确定suffixLength的值：

• suffixLength初始化：通常情況下初始化為0；當TotalCoeffs大于10且TrailingOnes小于3時，初始化為1；
• 若已經編碼好的非零系數大于門檻值，則suffixLength加1。該門檻值定義為3 << ( suffixLength − 1 )。編碼第一個level後。suffixLength應加1；

1. 将有符号的Level值轉換為無符号的levelCode:

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

1. 編碼level_prefix：level_prefix的計算方法為：level_prefix = levelCode/(1 << suffixLength);level_prefix到碼流的相應關系由9-6表示；
2. 确定字尾的長度：字尾的長度levelSuffixSize通常情況下等于suffixLength。例外情況有：

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

1. 計算level_suffix的值：level_suffix = levelCode%(1 << suffixLength);
2. 依照levelSuffixSize的長度編碼level_suffix;

1. 在H.264标準協定文檔的表9-5中查得，coeff_token的值為0x00000100;
2. 編碼拖尾系數的符号，從高頻到低頻，拖尾系數符号為+、-、-，是以符号的碼流為011。
3. 編碼非零系數的幅值，三個普通非零系數分别為1、2、3；
4. 編碼1：suffixLength初始化為0；levelCode=0;level_prefix=0，查表得相應的碼流為1。suffixLength=0，是以不正确字尾編碼；
5. 編碼2：suffixLength自增1等于1。levelCode=2;level_prefix=1，查表可知相應的碼流為01;suffixLength=1，level_suffix=0，是以字尾碼流為0。
6. 編碼3：suffixLength不滿足自增條件，依舊為1。levelCode=4;level_prefix=2。查表可知相應的碼流為001。suffixLength=1。level_suffix=0，是以字尾碼流為0；
7. 綜上所述，非零系數的幅值部分的碼流為10100010。
8. 編碼最後非零系數之前0的個數TotalZeros： TotalCoeffs=6,TotalZeros=2時。在表9-7中可知碼流為111。
9. 編碼每一個非零系數前0的個數：從高頻到低頻，每一個非零系數前0的總個數(zerosLeft)分别為2、1、0、0、0、0，每一個非0系數前連續0的個數(run_before)分别為1、1、0、0、0、0。依據标準文檔表9-10可得：

• run_before=1。zerosLeft=2，相應碼流為01；
• run_before=1。zerosLeft=1，相應碼流為0；
• 全部的0系數都已經編碼完畢，無需再繼續進行編碼；