轉：H.264熵編碼分析
利用信源的随機過程統計特性進行碼率壓縮的編碼方式稱為熵編碼。它是把所有的文法（句法）元素（包括控制流資料，變換量化殘差系數和運動矢量資料）以一定的編碼形式映射成二進制比特流。熵編碼是無損壓縮編碼方法，它生成的碼流可以經解碼無失真地恢複出資料。在資訊論中表示一個資料符号的理論上最佳的比特數通常是一個分數而不是整數，這個比特數用log2(1/P)表示，其中P是每個資料符号的出現機率。這裡Log2(1/P)指的就是熵的概念。熵的大小與信源的機率模型有着密切的關系，各個符号出現的機率不同，信源的熵也不同。當信源中各事件是等機率分布時，熵具有極大值。信源的熵與其可能達到的最大值之間的內插補點反映了該信源所含有的備援度。信源的備援度越小，即每個符号所獨立攜帶的資訊量越大，那麼傳送相同的資訊量所需要的序列長度就越短，符号位也越少。是以，資料壓縮的一個基本的途徑是去除信源的符号之間的相關性，盡可能地使序列成為無記憶的，即前一符号的出現不影響以後任何一個符号出現的機率。
熵編碼可以是定長編碼，變長編碼或算術編碼；變長編碼對出現頻率高的符号用短碼字表示，對出現頻率低的符号用長碼字表示。算術編碼是一種遞推形式的連續編碼，其思想是用0到1的區間上的一個數來表示一個字元輸入流，它的本質是為整個輸入流配置設定一個碼字，而不是給輸入流中的每個字元分别指定碼字。算術編碼是用區間遞進的方法來為輸入流尋找這個碼字的，它從于第一個符号确定的初始區間（0到1）開始，逐個字元地讀入輸入流，在每一個新的字元出現後遞歸地劃分目前區間，劃分的根據是各個字元的機率，将目前區間按照各個字元的機率劃分成若幹子區間，将目前字元對應的子2區間取出，作為處理下一個字元時的目前區間。到處理完最後 一個字元後，得到了最終區間，在最終區間中任意挑選一個數作為輸出。算術編碼是一種高效的熵編碼方案，其每個符号所對應的碼長被認為是分數。由于對每一個符号的編碼都與以前編碼的結果有關，是以它考慮的是信源符号序列整體的機率特性，而不是單個符号的機率特性， 因而它能夠更大程度地逼近信源的極限熵，降低碼率。
在H.264标準中有3種熵編碼方案: 一個是指數哥倫布編碼(Exponential Golomb Codes)；一個是從可變長編碼發展而來的上下文自适應可變長編碼(CAVLC)；另一個是從算術編碼發展而來的基于上下文的自适應二進制算術編碼(CABAC)。前兩種屬于變長編碼，而第三種屬于算術編碼。研究表明CABAC的壓縮效率比CAVLC提高了9%～14%。在标準中通過描述子(Descriptor)的形式來說明熵編碼的方法。
Exp‐Golomb Codes
Exp‐Golomb的描述子有無符号指數哥倫布編碼ue(v)，有符号指數哥倫布編碼se(v)，截斷指數哥倫布編碼te(v)和映射指數哥倫布編碼me(v)。
0階指數哥倫布編碼是一種有規則結構的變長編碼，它的結構可以表示為
[M zeros][1][INFO]
其中M zeros稱為字首，由M個零組成，而M位INFO稱為資訊字尾。碼字總長為2M+1。M和INFO的值由要編碼的值索引code_num得到。（可參考标準表9‐1）
ue(v)從v到code_num的轉換公式為code_num = v。（可參考标準表9‐2）
se(v)從v到code_num的轉換公式為：
te(v)從v到code_num的轉換，首先根據文法元素v值位數範圍，如果v的位數大于1，v到code_num的轉換過程和ue(v)相同；如果v的位數等于1，即v等于0或1，則code_num與v的值相同，但最終的編碼值與code_num這個值相反。
me(v)從v到code_num的轉換參考标準表9‐4。
CAVLC
CAVLC的描述子是ce(v)。
基于上下文自适應編碼的CAVLC利用相鄰已編碼符号所提供的相關性為所要編碼的符号選擇合适的上下文模型，大大降低了符号間的備援度。上下文模型的選擇主要展現在非零系數和拖尾系數的個數編碼所需表格(nC)的選擇以及非零系數的幅值編碼字尾長度(suffixLength)的更新。CAVLC編碼的具體過程由以下五部分組成，編碼順序和Zig‐zag掃描順序相反：
(1) 對非零系數的數目(TotalCoeffs)以及拖尾系數(TrailingOnes)的數目進行編碼。根據這兩個值一共有3個變長表格和1個定長表格（這4個表格隻針對于亮度系數，色度系數使用其它表格）可供選擇（選擇的表格由相鄰塊非零系數的個數nC值确定，具體參見标準表9‐5）。其中的定長表格的碼字是六個比特長，高四位表示TotalCoeffs，低兩位表示TrailingOnes。
(2) 對每個拖尾系數的符号進行編碼。（+1用0表示，‐1用1表示）
(3) 對除了拖尾系數之外的非零系數的幅值(Levels)進行編碼。這一步比較複雜，這裡詳細介紹對單個幅值的編碼方法：
a) 将有符号的level轉換成無符号的levelCode：
如果level是正的，levelCode = (level<<1)‐2;
如果level是負的，levelCode = ‐(level<<1)‐1;
特别地，當TrailingOnes<3時，第一個非拖尾系數的幅值level要加1（當幅值為負）或減1（當幅值為正）後再計算levelCode。
b) 計算level_prefix：
level_prefix = levelCode / (1<<suffixLength)；
根據level_prefix的值查标準表9‐6即可得到對應的字元串字首。當TotalCoeffs>10且TrailingOnes<1時suffixLength初始為1，其它情況下suffixLength初始為0。
c) 計算level_suffix：
level_suffix = levelCode % (1<<suffixLength)；
字元串字尾是level_suffix值的二進制無符号數形式。
d) suffixLength值更新為下一個編碼作準備，如果目前已編碼的非零系數值大于預先定義好的門檻值，suffixLength加1。僞代碼如下（注意這裡隐含了上下文自适應過程）：
If ( suffixLength == 0 )
suffixLength++；
else if ( Abs(level) > (3<<(suffixLength‐1)) && suffixLength <6)
suffixLength++;
e) 編碼值為字首和字尾的拼接。
(4) 對最後一個非零系數前零的數目(TotalZeros)進行編碼（參見标準表9‐7,9‐8,9‐9）。
(5) 對每個非零系數前零的個數(RunBefore)進行編碼（參見标準表9‐10）。還有一個變量ZerosLeft表示目前非零系數左邊的所有零的個數，ZerosLeft的初始值等于TotalZeros，在每個非零系數的RunBefore值編碼後進行更新。注意在以下兩種情況下是不需要編碼的：
a) 最後一個非零系數(run_before[0])前零的個數。
b) 沒有剩餘的零需要編碼(ZerosLeft=0)。
CABAC
CABAC的描述子是ae(v)。
CABAC充分考慮和利用了視訊流統計特性，克服了VLC編碼中的缺點，充分利用了視訊流的上下文資訊，并且能夠自适應視訊流的統計資訊，提高了編碼效率。CABAC的編碼流程如圖1所示，主要分為3部分：文法元素二進制化、上下文模組化和自适應二進制算術編碼器。
大緻編碼過程如下：如果輸入的文法元素是非二進制的文法元素則進行二進制化, 二進制的文法元素跳過這一過程。 二進制字元串進入編碼器, 可以進行快速編碼, 直接進入旁路編碼器, 以固定的機率模型進行編碼; 通常是根據文法元素的類型選擇上下文, 然後二進制值和選擇的上下文模型一起進入編碼器, 輸出編碼碼流, 并且根據編碼符号更新上下文模型。CABAC要編碼的文法元素包括兩類：第一類包含關于宏塊類型、子塊類型以及時間和空間預測模式資訊的元素；第二類包括所有殘差元素，也就是所有變換系數相關的文法元素。
下面将詳細介紹流程中的三個部分。
A. 文法元素二進制化
H.264通過二進制化把多元算術編碼轉化為二進制算術編碼，提高了運算速度。文法元素二進制化就是把非二進制的符号映射成若幹位的二進制串。CABAC引入了二進制化預處理過程來減小要編碼的文法元素符号集的大小, 對于給定的文法元素用一個惟一的二進制串代替。CABAC二進制化方案由基本方案，串接方案（參考标準子條款9.3.2.3，9.3.2.6）以及特别的手工選擇方案（參考标準子條款9.3.2.5）組成。基本方案有一進制碼、截斷一進制碼、K階指數哥倫布碼和定長碼4種；串接方案由基本方案串接而成；手工選擇方案有5種，專門針對mb_type和sub_mb_type這兩種文法元素。對文法元素的二進制化方案參考标準表9‐25。經二進制化編碼輸出的是MPS機率極高的比特流，這樣可以達到極高的壓縮效果。
B. 上下文模組化
利用相鄰的編碼符号的相關性，用已編碼符号為待編碼符号選擇合适的上下文模型，上下文模型提供了對目前待編碼符号的機率估計，上下文資訊可以降低符号間的備援度。在H.264中通過索引選擇的方法利用上下文資訊。首先建立上下文集合，上下文變量按線性排列，每一個變量用索引值來表示，然後為每一個文法元素配置設定上下文變量，最後通過編碼符号的上下文資訊選擇上下文變量。
在H.264中用64個有代表性的機率值來表示LPS(Least Probability Symbol)的機率。這64個機率值
通過下式産生:
其中
表示機率的索引值（
），在H.264中機率模型用上下文變量表示，而上下文變量由2個變量組成, 分别為6位機率狀态索引值
（pStateIdx）和1位最大可能符号值
（valMPS），是以機率狀态空間總共有7位128個狀态。最大可能符号值MPS(Most Probability Symbol)取"0"或"1"，（ctxIdx）為上下文變量的索引值，各文法元素的
取值範圍可參考标準表9‐11，其準确值是這樣計算的：
如果索引偏移值（标準表9‐11中範圍的左值，即ctxIdxOffset）在标準表9‐30中，則ctxIdx是ctxIdxOffset與索引增加量（ctxIdxInc）之和，而ctxIdxInc取決于位索引（binIdx）和ctxIdxOffset；否則，ctxIdx是ctxIdxOffset，ctxIdxInc與上下文種類偏移（ctxIdxBlockCatOffset）之和。此時ctxIdxInc與ctxIdxBlockCatOffset的值和上下文種類（ctxBlockCat）相關。ctxBlockCat的取值可參考标準表9‐33。
上下文變量初始值由訓練序列得到（參考标準子條款9.3.1.1），注意上下文變量初始值對于所有上下文變量的索引值ctxIdx都要計算，其計算表達式如下：
preCtxState = Clip3( 1, 126, ( ( m