《H.264/AVC視訊編解碼技術詳解》視訊教程已經在“CSDN學院”上線，視訊中詳述了H.264的背景、标準協定和實作，并通過一個實戰工程的形式對H.264的标準進行解析和實作，歡迎觀看！
“紙上得來終覺淺，絕知此事要躬行”，隻有自己按照标準文檔以代碼的形式操作一遍，才能對視訊壓縮編碼标準的思想和方法有足夠深刻的了解和體會！
連結位址：H.264/AVC視訊編解碼技術詳解
GitHub代碼位址：點選這裡
本節視訊免費
1. 熵編碼概念
“熵”這一概念原本來自于化學和熱力學，用于度量能量退化的名額，即熵越高，物體或系統的做功能力越低。後來香農将這一概念引入到資訊論中，用于表示消息的平均資訊量。信源的熵通常可以表示信源所發出資訊的不确定性，即越是随機的、前後不相關的資訊，其熵越高。
在資訊論中，香農提出了信源編碼定理。該定理說明了香農熵與信源符号機率之間的關系，說明資訊的熵為信源無損編碼後的平均碼字長度的下限。任何的無損編碼方法都不可能使編碼後的平均碼長小于香農熵，隻能使其盡量接近。
基于此，對信源進行熵編碼的基本思想，是使其前後的碼字之間盡量更加随機，盡量減小前後的相關性，更加接近其信源的香農熵。這樣在表示同樣的資訊量時所用的資料長度更短。
在實際使用中，常用的熵編碼主要有變長編碼和算術編碼等方法。其中變長編碼相對于算術編碼較為簡單，但平均壓縮比可能略低。常見的變長編碼方法有哈夫曼編碼和香農-費諾編碼等。
2. 熵編碼的簡單實作——哈夫曼編碼
戴維·哈夫曼（David·A·Huffman）于1952年在麻省理工學院的羅伯特·費諾的指導下攻讀博士學位時，發明了一種基于有序頻率二叉樹的編碼方法，該方法的編碼效率超過了他的導師和資訊論之父香農的研究成果（香農-費諾編碼），是以又稱作“最優編碼方法”。
哈夫曼編碼時變長編碼方法的一種，該方法完全依賴于碼字出現的機率來構造整體平均長度最短的編碼方法。進行哈夫曼編碼的關鍵步驟是建立符合哈夫曼編碼規則的二叉樹，該樹又稱作哈夫曼樹。
哈夫曼樹是一種特殊的二叉樹，其終端節點的個數與待編碼的碼元的個數等同，而且每個終端節點上都帶有各自的權值。每個終端節點的路徑長度乘以該節點的權值的總和稱為整個二叉樹的權重路徑長度。在滿足條件的各種二叉樹中，該路徑長度最短的二叉樹即為哈夫曼樹。
在使用哈夫曼編碼執行對碼元的實際編碼過程時，碼元的權值可設定為其機率值，那麼可以根據其權值來建構哈夫曼樹。我們假設使用哈夫曼編碼對以下機率的碼字進行編碼：
碼字 機率
A 0.1
B 0.1
C 0.15
D 0.2
E 0.2
F 0.25
根據機率表建構哈夫曼樹的過程如下圖所示：
最終我們可以得到如下圖所示的哈夫曼樹：
在哈夫曼樹建構完成後，便可以得到每一個碼元的哈夫曼編碼的碼字。具體方法是：從哈夫曼樹的根節點開始周遊，直至每一個終端節點，當通路某個節點的左子樹時賦予碼字0，通路右子樹時賦予一個碼字1（反之亦可），直到周遊到終端節點時這一路徑所代表的0和1的串便是該碼元的哈夫曼編碼碼字。
例如上圖的哈夫曼樹，根節點通路左子樹ABCF，賦予碼字0；然後再通路左子樹ABC，賦予碼字0，此時整個碼字為00，然後通路右子樹得到終端節點C，賦予碼字1，此時便可以得到C的哈夫曼編碼碼字001。以此規律，整個六個元素的碼元集合的編碼碼表為：
- A: 0000
- B: 0001
- C: 001
- D: 10
- E: 11
- F: 01
從這個碼表中還可以看出另外一個規律：哈夫曼編碼的任意一個碼字，都不可能是其他碼字的字首。是以通過哈夫曼編碼的資訊可以緊密排列連續傳輸，而不用擔心解碼時的歧義性。
3. 哈夫曼樹的建構Demo
下面的程式段給出一個建構哈夫曼樹，并生成對應碼元的哈夫曼編碼的過程：
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
//每一個符号定義為一個結構體，包括字元和出現頻次
typedef struct
{
unsigned char character;
unsigned int frequency;
} CharNode;
static bool open_input_file(ifstream &input, const char *inputFileName)
{
input.open(inputFileName);
if (!input.is_open())
{
return false;
}
return true;
}
struct MinHeapNode
{
char data;
unsigned int freq;
MinHeapNode *left, *right;
MinHeapNode(char data, unsigned freq)
{
left = right = NULL;
this->data = data;
this->freq = freq;
}
};
typedef struct MinHeapNode MinHeapNode;
struct compare
{
bool operator()(MinHeapNode* l, MinHeapNode *r)
{
return (l->freq > r->freq);
}
};
static void get_huffman_code(MinHeapNode *root, string code)
{
if (!root)
{
return;
}
if (root->data != -1)
{
cout << root->data << " : " << code << endl;;
}
get_huffman_code(root->left, code + "0");
get_huffman_code(root->right, code + "1");
}
int _tmain(int argc, _TCHAR* argv[])
{
ifstream inputFile;
if (!open_input_file(inputFile, "input.txt"))
{
cout << "Error: opening input file failed!" << endl;
return -1;
}
char buf = inputFile.get();
CharNode nodeArr[256] = { { 0, 0 } };
while (inputFile.good())
{
cout << buf;
nodeArr[buf].character = buf;
nodeArr[buf].frequency++;
buf = inputFile.get();
}
cout << endl;
priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;
for (int idx = 0; idx < 256; idx++)
{
if (nodeArr[idx].frequency > 0)
{
cout << "Node " << idx << ": [" << nodeArr[idx].character << ", " << nodeArr[idx].frequency << "]" << endl;
minHeap.push(new MinHeapNode(nodeArr[idx].character, nodeArr[idx].frequency));
}
}
MinHeapNode *leftNode = NULL, *rightNode = NULL, *topNode = NULL;
while (minHeap.size() != 1)
{
leftNode = minHeap.top();
minHeap.pop();
rightNode = minHeap.top();
minHeap.pop();
topNode = new MinHeapNode(-1, leftNode->freq + rightNode->freq);
topNode->left = leftNode;
topNode->right = rightNode;
minHeap.push(topNode);
}
get_huffman_code(topNode, "");
inputFile.close();
return 0;
}
程式的詳細解釋過程請到視訊中觀看。