三、熵编码

H264H265视频编解码算法文章汇总
1、熵编码概念

• 熵：

• • 化学与热力学概念，用于度量能量退化的指标；

  • 熵越高，物体/系统做功的能力越低；

• 信息学中的熵：

• • 用于度量消息的平均信息量，和信息的不确定性；

  • 越是随机的、前后不相关的信息，其熵越高；

• 信源编码定理：

• • 说明了香农熵与信源符号概率之间的关系

  • 信息的熵为信源无损编码后平均码长的下限

2、熵与混乱程度

混乱程度高

image.png

混乱程度低

image.png

3、熵编码

• 基本思想：

• • 使前后的码字之间尽量更加随机，减少前后相关性，更加接近其信源的香农熵；

• 常用熵编码算法：

• • 变长编码：运算复杂度和编码效率都较低，常用方法：哈夫曼编码、香农-费诺编码等；

  • 算术编码：运算较复杂，但编码效率更高；

4、熵编码的简单实现------哈夫曼编码（在图像编码MJPEG中用的多，H264中用的少）

• 哈夫曼编码：

• • 变长编码的一种，依赖于码字的概率来构造平均长度最短的编码方法；

  • 关键步骤：建立符合哈夫曼编码规则的二叉树，即哈夫曼树；

• 哈夫曼树：

• • 一种特殊的二叉树，终端节点个数等同于码元数，且每个终端节点带有各自的权值；

  • 加权路径长度，即根节点到终端节点的路径长度乘以权值的总和最小

5、构建哈夫曼树

image.png image.png

如何构建哈夫曼树呢？将出现频次最低的两个合并生成一个新的节点，依次循环向上合并，最终生成哈夫曼树。如上图所以，可以使用C++中的优先级队列，对所有的Node进行排序。生成了从小到大的优先级队列，顶点为出现频次最小的节点，也就是哈弗曼树中最底层最后的权值最低的节点。

排序之后可以对哈夫曼树进行遍历，左子树+0，右子树+1，生成哈夫曼码字，最终生成一个完整的哈夫曼码字。如果文本文件按照哈夫曼编码，将文本文件中的每一个字符按照码表中的字符进行替换，就实现了哈夫曼编码，若重复出现的字符越多(码字越短)，压缩率越高。

须保存哈夫曼编码的码表，因为不同的信源每一个符号分布情况是不一样的，获取码表才能进行还原解码，否则不知道每一个符号的概率和生成的哈夫曼树是什么样的。

image.png