熵编码及其常用方法

2023-06-21 理论教育版权反馈

【摘要】：常用的熵编码有基于图像概率分布特性的哈夫曼编码、算术编码和游程编码三类。采用哈夫曼编码时有两个问题值得注意：1）哈夫曼编码没有错误保护功能，在解码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。3）重复第2）步，最后输出的“当前区间”的下边界就是该给定符号序列的算术编码。

根据信息论基础知识可知，信源冗余是由信源本身的相关性和信源概率分布的不均匀性引起的。熵编码的基本原理就是去除图像信源在空间和时间上的相关性，利用图像信源像素值的概率分布不均匀性，使编码码字的平均码长接近信源的熵而不产生失真。由于这种编码完全基于图像的统计特性，因此，有时也称为统计编码。

常用的熵编码有基于图像概率分布特性的哈夫曼编码、算术编码和游程编码三类。

1.哈夫曼编码

哈夫曼（Huffman）编码是一种可变长度码，各符号与码字一一对应。哈夫曼编码算法基于一种称为“码树”的技术，具体的编码步骤如下：

1）初始化，根据符号概率的大小按由大到小的顺序对符号进行排序。

2）把概率最小的两个符号组成一个新符号，即新符号的概率等于这两个符号概率之和。

3）重复第2）步，直到形成一个符号为止，其概率最后等于1。

4）从码树的根开始回溯到待编码的符号，并将每一个下分枝赋值为“1”，上分枝赋值为“0”（反之也可）。每个符号所对应的哈夫曼码就是从根节点经过若干个中间节点到达叶节点的路径上遇到的二进制码元“1”或“0”的顺序组合。

采用哈夫曼编码时有两个问题值得注意：

1）哈夫曼编码没有错误保护功能，在解码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅仅是1位出现错误，也会引起一连串的错误，这种现象称为错误传播。

2）哈夫曼编码是可变长度码，因此很难随意查找或调用压缩码流中间的内容，然后再解码，这就需要在存储代码之前加以考虑。

2.算术编码

算术编码将被编码的信源符号序列表示成实数半开区间[0，1）中的一个数值区间。这个区间随着信源符号序列中每一个信源符号的输入逐步减小，每次减小的程度取决于当前输入的信源符号的出现概率。符号序列越长，编码表示它的区间就越小，表示这一区间所需的二进制位就越多。算术编码用到两个基本的参数：符号的概率和它的编码区间。信源符号的概率决定了压缩编码的效率，也决定了编码过程中信源符号的区间。编码过程中的区间决定了符号编码后的输出。

给定符号序列的算术编码步骤如下：

1）编码器在开始时将“当前区间”[L，H）设置为[0，1）。

2）对符号序列中每一个输入的信源符号，编码器将“当前区间”分为子区间，每一个信源符号对应一个子区间，每个子区间的大小与信源符号出现的概率成比例，编码器选择对应于当前输入符号的子区间，并使它成为新的“当前区间”。

3）重复第2）步，最后输出的“当前区间”的下边界就是该给定符号序列的算术编码。

3.游程编码

游程长度（Run-Length），简称游程或游长，指的是由符号（或信号样值）构成的数据流中各个符号重复出现的字符的长度。游程编码，也称行程编码或游长编码，是一种建立在数据相关性基础上的数据压缩编码形式，其基本思想是将具有相同数值（例如像素的灰度值）的、连续出现的信源符号构成的符号序列用其数值及串的长度表示。以图像编码为例，如果沿图像的水平方向有一串L个像素具有相同的灰度值G，则对其进行游程编码后，就可用数来表示二元组（G，L）。游程编码往往与其他编码方法结合使用。

熵编码及其常用方法

相关推荐