视频的熵编码

一、定长编码

$\quad$特点：为每个符号分配等长比特码字。码字长度固定，编码和解码都很简单，易实现。

二、变长编码

$\quad$为每个编码符号分配的比特数不一定相等。平均码长小于定长码，编解码计算复杂。

1、Huffman编码

$\quad$基本思想：出现频率最高的符号用最短的码字，反之用最长的码字。
$\quad$数学表示：设被编码的信源有m种符号，符号集合为$\{a_i|i=0,1,\cdots,m-1\}${ai​∣i=0,1,⋯,m−1}，出现概率为$\{P(a_i)|I=0,1, \cdots,m-1\}${P(ai​)∣I=0,1,⋯,m−1}。
$\quad$编码方式

• 1、将信源概率分布按大小依递减次序排列；合并两概率最小者，得到信新源；并分配 0,1 符号
• 2、新信源若包含两个以上符号返回1， 否则到3
• 3、从最后一级向前按顺序写出每信源符号所对应的码字

$\quad$举个例子。一信源S的符号集$A=\{a_1,a_2,a_3,a_4,a_5\}$A={a1​,a2​,a3​,a4​,a5​}，概率分别为：0.4，0.2，0.2，0.1，0.1；试对信源符号进行二元Huffman编码。

$\quad$信源熵
$H=\sum_{i=0}^{m-1}-P(i)log_2{P(i)}$H=i=0∑m−1​−P(i)log2​P(i)
信源熵表示信源能够被编码长度的理论下界。在上面例子中，$H=-0.4*log(0.4)-2*(0.2log(0.2))-2*(0.1*log(0.1))=2.122$H=−0.4∗log(0.4)−2∗(0.2log(0.2))−2∗(0.1∗log(0.1))=2.122
$\quad$平均码长
$\overline{L}=\sum_{i=0}^{m-1}P(a_i)*l$L=i=0∑m−1​P(ai​)∗l
平均码长表示经过编码后每个信源符号对应码字长度的平均值。$\overline{L}=0.4*2+0.2*2*2+0.1*3*2=2.2$L=0.4∗2+0.2∗2∗2+0.1∗3∗2=2.2
$\quad$编码效率
$\eta=\frac{H}{\overline{L}}$η=LH​

2、指数哥伦布编码(用于H.264/H.265)

$\quad$特点

• 码长随编码序号递增而变长
• 码字结构。每个码字的编码和解码可以通过算法计算得到，而非查找表
  $\quad$编码
  
  
  Zero prefix: 有M个连续0组成，其中$M=floor[log_2(codeNum+1)]$M=floor[log2​(codeNum+1)]
  INFO:$codeNum+1-2^M$codeNum+1−2M
  $\quad$解码
• 读出以1结尾的前M个0
• 根据得到的M，读出1后面的INFO
• $codeNum = 2^M+INFO - 1$codeNum=2M+INFO−1
  
  $\quad$程序如下

#include <bits/stdc++.h>
using namespace std;

string dec2bit(int num)
{
	if(num==0) return "0";
	string res = "";
	while(num)
	{
		int temp = num%2;
		res += temp+'0';
		num /= 2;
	}
	reverse(res.begin(), res.end());
	return res;
}

string encode(int codeNum)
{
	string res = "";
	int M = log(codeNum+1)/log(2)+1e-6;
	for (int i = 0; i < M; ++i)
	{
		res += '0';
	}
	res += '1';
	int INFO = codeNum+1-(int)(pow(2,M)+0.1);
	string INFObit = dec2bit(INFO);
	for (int i = 0; i < M-INFObit.length(); ++i)
	{
		res += '0';
	}
	res += INFObit;
	return res;
}

int decode(string s)
{
	int M;
	for (int i = 0; i < s.length(); ++i)
	{
		if(s[i]=='1')
		{
			M = i;
			break;
		}
	}
	int INFO = 0;
	for (int i = M+1; i < s.length(); ++i)
	{
		INFO += (s[i]-'0')*pow(2,s.length()-1-i);
	}
	int res = pow(2,M)+INFO-1+0.1;
	return res;
}
int main(int argc, char const *argv[])
{
	int codeNum = 107;
	cout << encode(codeNum) << endl;
	string mazi = "000000011100011";
	cout << decode(mazi) << endl;
	return 0;
}

3、行程编码

$\quad$特点：把连续相同的符号用出现次数+符号的形式编码出来。

三、算术编码（AC编码）

$\quad$特点

• 属于变长编码，根据概率分配码字，编码效率高。
• 不同于Huffman，无须为每个符号设定码字。
• 将不同信源符号序列表示为与其长度成正比的一维空间长度。
• 每个符号属于一个子空间，子空间互不重叠，总和归一化为1。
• 每进来一个新符号，就找到对应空间的那一段，那段空间唯一表示序列的所有符号和排序。
• 在信源符号概率比较接近时，AC比Huffman效率高

四、CAVLC-上下文自适应可变长编码

• 专门用来编码变换、量化后的残差系数
• 变换、量化后的残差系数的特点 ：数据减少、稀疏、能量集中、0系数增多
• CAVLC采用行程编码来处理量化后的残差系数
  $\quad$编码过程

1、将4*4的方块进行zigzag扫描得到一个大小为16的序列
2、编码非零系数个数和拖尾系数数目

• 非零系数个数：指所有不为0的元素个数，范围为0-16
• 拖尾系数：矩阵重排列后，序列末尾连续出现的±1±1的个数（中间可以间隔任意多个0）。如果±1±1的个数大于3个，则只有最后三个±1±1会被视为拖尾系数，其余的被视为普通的非零系数。范围为0-3

a.对于每个拖尾系数（±1）只需要指明其符号，其符号用一个比特表示（0 表示正+，1 表示负-）。编码的顺序是按照反向扫描的顺序，从高频数据开始
b.编码其余的非零系数

• 每个非零系数，无论正负，均用“level”表示，得到 level VLC
• 从高频区域逆向“之” 字扫描
• Level VLC 包含 level_prefix前缀 和 level_suffix 后缀level_prefix 由 n-bit 前导 0 和 1-bit 1 构成
  
• level_suffix 长度为 suffixLength 个bits。suffixLength初始化为0，当非零系数多于10个并且拖尾1少于3个；suffixLength初始化为1 当系数的绝对值超过阈值，suffixLength加1, suffixLength的最大值为6。
  
  3、编码非零系数前零的个数
  对最后一个非零系数前的零的个数编码，得到TotalZeros。
  4、对“零”0 用游程编码
  从高频开始，对每一个非零系数之前的连续 0 的个数编码，得到run_before。