Huffman图片压缩

1、小组小组成员成员分分工工Huffman编码：编码：Huffman解码：解码：UI 设设 计计 ：PPT 及及 文文 档档 ：测测 试试 ：一：图像压缩概述二：压缩的必要性三：图像压缩编码分类四：Huffman 编码压缩五：Huffman 解码六：Huffman 图片压缩特点图像压缩概述图像压缩概述 去除多余数据以数学的观点来看，这一过程实际上就是将二维像素阵列变换为一个在统计上无关联的数据集合。 图像压缩是指以较少的比特有损或无损地表示原来的像素矩阵的技术，也称图像编码。 编码压缩的必要性编码压缩的必要性从传送的角度来看，在信道带宽、通信链路容从传送的角度来看，在信道带宽、通信链路容量一定的前

2、提下，采用编码压缩技术，减少传量一定的前提下，采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段。因此，输数据量，是提高通信速度的重要手段。因此，更要求数据量压缩。更要求数据量压缩。 处理速度处理速度存储容量存储容量图像量化所需数据量大图像量化所需数据量大计算机计算机图像编码分类图像编码分类量化量化预测预测编码编码DPCM基于频率基于频率变换编码变换编码子带编码子带编码小波变换小波变换编码编码基于统计基于统计哈夫曼哈夫曼编码编码算术编码算术编码游程编码游程编码RLE国际标准国际标准JPEGJPEG标准（标准（静静态图像）态图像）MPEGMPEG标准标准（电视图像）电视图像）H.261H

3、.261（可视（可视通信）通信）MHEGMHEG标准标准（超媒体）（超媒体）PCMPCM离散信源熵离散信源熵,log1log)(11iNiiiNiippppXH 即即信源信源 X X 的平均自信息量称为的平均自信息量称为信源熵信源熵，记记为为定义定义, )(XH其中，其中， 为消息符号为消息符号 出现的概率，出现的概率，ipix为信源的状态数。为信源的状态数。N. ),()()(21NpppHxpHXH 由于由于 因此熵实际上是一因此熵实际上是一个个 元元连续函数。连续函数。,1 ip1 N 可见，熵是信源概率空间的函数，可见，熵是信源概率空间的函数，一般还可写成一般还可写成编码压缩方法编码压

4、缩方法-HuffmanHuffman编码编码 哈夫曼（哈夫曼（HuffmanHuffman）编码编码 HuffmanHuffman编码是编码是2020世纪世纪5050年代提出的一种基于统年代提出的一种基于统计的无损编码方法，它利用变长的码来使冗余量计的无损编码方法，它利用变长的码来使冗余量达到最小。通过二叉树来编码，使常出现的字符达到最小。通过二叉树来编码，使常出现的字符用较短的码表示，不常出现的字符用较长的码表用较短的码表示，不常出现的字符用较长的码表示。这些代码都是二进制码，且码的长度是可变示。这些代码都是二进制码，且码的长度是可变的。例如，有一个原始数据序列，的。例如，有一个原始数据序列

5、，ABACCDAAABACCDAA则编则编码为码为A A（0 0），），B B（1010），），C C（110110），），D D（111111），），压缩后为压缩后为010011011011100010011011011100。静态。静态HuffmanHuffman编码使编码使用一个依据字符出现的概率事先生成好的编码树用一个依据字符出现的概率事先生成好的编码树进行编码。而动态进行编码。而动态HuffmanHuffman编码需要编码需要 在编码的过在编码的过程中建立编码树，需要对原始数据扫描两遍，第程中建立编码树，需要对原始数据扫描两遍，第一遍扫描要精确地统计出原始数据中的每个值出一遍扫描要精

6、确地统计出原始数据中的每个值出现的频率，第二遍是建立现的频率，第二遍是建立HuffmanHuffman编码树进行编编码树进行编码。码。1 1 信号源的数据按照出现概率递减的信号源的数据按照出现概率递减的顺序排列。顺序排列。2 2 合并两个最小出现概率，作为新数合并两个最小出现概率，作为新数据出现概率。据出现概率。3 3 重复进行重复进行1212，直至概率相加为，直至概率相加为1 1为止。为止。4 4 合并运算时，概率大者取合并运算时，概率大者取0 0，概率，概率小者取小者取1 1（或者小者取（或者小者取0.0.大者取大者取1 1）。）。5 5 记录概率为记录概率为1 1处到信号源的处到信号源的

7、0 0、1 1序序列。列。例，例，对信源对信源X X 进行进行HuffmanHuffman编码编码的过程如下：的过程如下： 04.005.006.007.010.010.018.040.0:87654321xxxxxxxxX 1 1 1 0 00011 5 1 1 0 0011 3 1 1 0编码压缩方法编码压缩方法-Huffman-Huffman编码编码 哈夫曼（哈夫曼（HuffmanHuffman）编码）编码编码压缩方法编码压缩方法-HuffmanHuffman编码编码 哈夫曼（哈夫曼（HuffmanHuffman）编码）编码61. 2504. 0505. 0406. 0407. 0410

8、. 0310. 0318. 0140. 01niiiLPd55. 2)04. 0log04. 005. 0log05. 006. 0log06. 007. 0log07. 010. 0log10. 0218. 0log18. 040. 0log40. 0()(log)()(2222222812 iiixPxPxH对信源对信源X X进行进行HuffmanHuffman编码的平均码字长度为编码的平均码字长度为：信源信源X X的熵为的熵为 04. 005. 006. 007. 010. 010. 018. 040. 0:87654321xxxxxxxxX1 001 011 0000 0100 010

9、1 00010 00011已知编码：已知编码：11000001000110011100000100011001解码？解码？解码：解码：x1x1x4x5x3x2x1x1x4x5x3x2Huffman 解码：由于由于HuffmanHuffman编码是瞬时的、唯一可解码的编码是瞬时的、唯一可解码的分组编码。之所以是分组编码，是因为每个分组编码。之所以是分组编码，是因为每个源符号映射到了一个固定的码符号序列；之源符号映射到了一个固定的码符号序列；之所以是瞬时的，是因为在码符号串中的每一所以是瞬时的，是因为在码符号串中的每一个码字可以不参照随后的符号而被解码。换个码字可以不参照随后的符号而被解码。换言之

10、，在任意一个给定的言之，在任意一个给定的HuffmanHuffman码中，没码中，没有码字是其他码字的前缀。并且之所以是唯有码字是其他码字的前缀。并且之所以是唯一可解码的，是因为码符号串仅有唯一的解一可解码的，是因为码符号串仅有唯一的解码方法。这样，码方法。这样，HuffmanHuffman码的符号的任意串码的符号的任意串可以通过从左到右的方式检测单独的符号来可以通过从左到右的方式检测单独的符号来解码。解码。Huffman Huffman 解码：解码：在进行在进行HuffmanHuffman编码压缩之后，获得一个稀疏矩编码压缩之后，获得一个稀疏矩阵，其中存放的是码字与像素之间的对应关系。阵，其

11、中存放的是码字与像素之间的对应关系。还有一个还有一个uint8uint8型型 zippedzipped向量，它是由一串向量，它是由一串0 0 1 1 序列转换而得到的。通过这两个信息，我们序列转换而得到的。通过这两个信息，我们可以对已经压缩的图像进行解码。可以对已经压缩的图像进行解码。Step1Step1：将将zippedzipped向量中的数据转换成一串向量中的数据转换成一串0 10 1序序列列stringstringStep2Step2：取出取出stringstring中的未操作的第一个码字，中的未操作的第一个码字，在稀疏矩阵中查找该码字，若能够找到，则进行在稀疏矩阵中查找该码字，若能够找

12、到，则进行Step3Step3，否则，进行，否则，进行Step4Step4Step3Step3：将与该码字对应的像素值，放到一将与该码字对应的像素值，放到一个矩阵个矩阵vector vector 的的相对应位置。相对应位置。Step4Step4： 取出取出stringstring中的下一个字符与之前的码字中的下一个字符与之前的码字组成组成 新新的码字的码字，在，在若能若能在稀疏矩阵在稀疏矩阵中找到与该码字匹配的码字中找到与该码字匹配的码字， 则进行则进行Step3Step3，否则继续进行，否则继续进行Step4Step4。直至，。直至，stringstring中中所所 有有的的序列都序列都被操

13、作被操作过，到过，到Step5.Step5.Step5Step5：对这个一维的矩阵对这个一维的矩阵vectorvector进行进行reshapereshape，就能得，就能得 到一幅解压之后的图片到一幅解压之后的图片了了Huffman Huffman 解码：解码：编码压缩方法编码压缩方法-HuffmanHuffman编码编码编码特点编码特点1 1 编码长度可变，压缩与解压缩较慢。编码长度可变，压缩与解压缩较慢。2 2 硬件实现困难。硬件实现困难。3 3 编码效率取决于信号源的数据出现概率；当信源概编码效率取决于信号源的数据出现概率；当信源概率是率是2 2的负次幂时，的负次幂时，HuffmanH

14、uffman码的编码效率达到码的编码效率达到100100；当；当信源概率相等时，其编码效率最低。这表明在使用信源概率相等时，其编码效率最低。这表明在使用HuffmanHuffman方法编码时，只有当信源概率分布很不均匀时，方法编码时，只有当信源概率分布很不均匀时，HuffmanHuffman码才会收到显著的效果。码才会收到显著的效果。4 Huffman4 Huffman编码应用时，均需要与其他编码结合起来使编码应用时，均需要与其他编码结合起来使用，才能进一步提高数据压缩比。例如，在静态图像处用，才能进一步提高数据压缩比。例如，在静态图像处理标准理标准JPEGJPEG中，先对图像像素进行中，先对