《human与压缩技术0》由会员分享，可在线阅读，更多相关《human与压缩技术0（5页珍藏版）》请在金锄头文库上搜索。
1、1. 哈夫曼编码4大量信息中 除了时间冗余和空间冗余外，在一般的图象数据中还存在信息熵冗余、结构冗余、知识冗余和视觉冗余。各种冗余就是压缩数据的出发点。数据压缩技术就是研究如何利用数据的冗余性来减少数据量的方法。因此，进行压缩研究的起点是研究数据的冗余性。1. 空间冗余。在静态图像中有一块表面颜色均匀的区域，在这个区域中所有点的光强和色彩以及色饱和度都相同，具有很大的空间冗余。这是由于基于离散像素采样的方法不能表示物体颜色之间的空间连贯性导致的。2. 时间冗余。电视图像、动画等序列图片，当其中物体有位移时，后一帧的数据与前一帧的数据有许多共同的地方，如背景等位置不变，只有部分相邻帧改变的画面，
2、显然是一种冗余，这种冗余称为时间冗余。3. 结构冗余。在有些图像的纹理区，图像的像素值存在着明显的分布模式。例如，方格状的地板图案等，称此为结构冗余。如果已知分布模式，就可以通过某一过程生成图像。4. 知识冗余。对于图像中重复出现的部分，我们可以构造出基本模型，并创建对应各种特征的图像库，进而使图像的存储只需要保存一些特征参数，从而可以大大减少数据量。知识冗余是模型编码主要利用的特性。5. 视觉冗余。事实表明，人的视觉系统对图像的敏感性是非均匀性和非线性的。在记录原始的图像数据时，对人眼看不见或不能分辨的部分进行记录显然是不必要的。因此，大可利用人的视觉的非均匀性和非线性，降低视觉冗余。6.
3、图像区域的相同性冗余。它是指在图像中的两个或多个区域所对应的所有像素值相同或相近，从而产生的数据重复性存储，这就是图像区域的相似性冗余。在以上的情况下，当记录了一个区域中各像素的颜色值，则与其相同或相近的其他区域就不需要记录其中各像素的值。采用向量量化（Vector quantization）方法就是针对这种冗余性的图像压缩编码方法。随着对人的视觉系统和图像模型的进一步研究，人们可能会发现图像中存在着更多的冗余性，使图像数据压缩编码的可能性越来越大，从而推动图像压缩技术的进一步发展。允许图像有一定的失真也是图像可以压缩的一个重要原因，在许多应用场合，并不要求经过压缩后复原的图像和原始图像完全相
4、同，而允许有少量的失真。只要这些失真并不被人眼所察觉，在许多情况下是完全可以接受的。这就个图像压缩提供了十分有利的条件。图像质量允许的失真越多，可以实现的压缩比就越大。这种有失真的压缩编码称为限失真编码。 大多数存储数字的信息编码系统都采用位数固定的定长码，即使用相同位数对数据进行编码。如常用的ASCII码，用8位二进制数表示一个英文字符。正像一篇文章中，每个字符出现的频度是不同的。有些字符出现的频率高，有些字符出现的频率低。同样，在一幅图像中，有些图像数据出现的频率高，有些图像数据出现的频率低。如果对出现频率高的数据用较少的比特数来表示，出现频率低的数据用较多的比特数来表示，这样从总的效果看
5、还是节省了存储空间。采用这种办法对数据进行编码时，代码的位数不固定，这种码称为变长码。这种编码思想首先由香农提出，哈夫曼对它提出了改进，用这种方法得到的编码称为哈夫曼码。哈夫曼编码（Huffman）是运用信息熵原理的一种无损编码方法。哈夫曼编码于1952年问世，迄今为止仍经久不衰，广泛应用于各种数据压缩技术中。压缩编码思想是利用变长编码将图像中出现概率大的灰度值赋予短码字，而对出现概率小的灰度值赋予长字码，从而达到压缩图像数据的目的。哈夫曼编码的理论依据是变字长编码理论。在变字长编码中，编码器的编码输出码字是字长不等的码字，按编码输入信息符号出现的统计概率，给输出码字分配以不同的字长。对于编码
6、输入中，出现大概率息符号，赋以短字长的输出码字；对于编码输入中，出现小概率的信息符号，赋以长字长的输出码字。可以证明，按照概率出现大小的顺序，对输出码字分配不同码字长度的变字长编码方法，其输出码字的平均码长最短，与信源熵值最接近。哈夫曼码字长度和信息符号出现概率大小次序正好相反，即大概信息符号分配码字长度短，小概率信息符号分配码字长度长，编码方法最佳。哈夫曼编码具有以下特点：(1) 哈夫曼编码构造出来的编码值不是唯一的。原因是在给两个最小概率的图像的灰度值进行编码时，可以是大概率为“0”，小概率为“1”，但也可相反；而当两个灰度值的概率相等时，“0”、“1”的分配也是随机的，这就造成了编码的不
7、唯一性，可是其平均码长却是相同的，所以不影响编码效率和数据压缩性能。(2) 哈夫曼编码对不同的信源其编码效率是不同的，当信源概率为2的负幂次方时，哈夫曼编码的编码效率达到100。因此只有当信源概率分布很不均匀时，哈夫曼编码才会收到显著的效果。换句话说，在信源概率比较接近的情况下，一般不使用哈夫曼编码方法。(3) 哈夫曼编码结果码字不等长，虽说平均码字最短，效率最高，但是码字长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差，为此，研究人员提出了一些修正方法，如双字长哈夫曼编码（也称亚最佳编码方法），希望通过降低一些效率来换取硬件实现简单的实惠。双字长编码只采用两种字长的码
8、字，对出现概率高的符号用短码字，对出现概率低的符号用长码字。短码字中留下一个码字不用，作为长码字前缀，这种方法编码压缩效果不如哈夫曼码，但其硬件实现相对简单，抗干扰能力也比哈夫曼方法强得多。(4) 哈夫曼编码应用时，均需要与其他编码结合起来使用，才能进一步提高数据压缩比。例如，在静态图像国际压缩标准JPEG中，先对图像进行分块，然后进行DCT变换、量化、Z形扫描、行程编码后，再进行哈夫曼编码。哈夫曼编码的一般算法如下：(1) 首先选出出现的概率，按出现概率从大到小排序。(2) 把最小的两个概率相加合并成新的概率，与剩余的概率组成新的概率集合。(3) 对新的概率集合重新排序，再次把其中最小的两个
9、概率相加，组成新的概率集合。如此重复进行，直到最后两个概率的和为1。(4) 分配码字。度值的概率分布不同，哈夫曼的编码效率有所差别。度值分布很不均匀时，哈夫曼编码的编码效率就高。而度值分布比较均匀时，哈夫曼编码的编码效率就很低。哈夫曼编码的性质：(1) 哈夫曼编码构造出来的码不是惟一的，主要有两个原因：一是在两个符号概率相加给两条支路分配“0”和“1”时，这一选择是任意的；二是当两个消息的概率相等时，0，1分配也是随意的。(2) 哈夫曼编码对不同的信源，其编码效率是不同的。(3) 哈夫曼编码中，没有一个码字是另一个码字的前缀，因此，每个码字惟一可译。每从文件中读出一个字符ch,用查哈夫曼编码表
10、的方式得到对应的码字,然后用这个码字替换相应的字符g ( f ( ch) ) 。当文件中的所有字符都经过了码字替换,则得到一个比原文件要小的压缩文件。文件之所以能够被压缩,是因为每个字符都占8个二进制位的空间。然而,通过码字替换相应的字符后,有的码字比相应的字符的码长要短,有的码字比相应的字符的码长要长,但文件在被压缩后总的长度比原来要短。文件的解压过程是文件的压缩过程的逆过程,即将一个压缩文件还原成它的本来面目。因为一个压缩文件是不能够直接使用的,只有被解压后才能使用。一个被压缩的文件如果不能被解压,则这种压缩是毫无意义的。由于哈夫曼编码是即时码,因此只要得到一个码字c,则通过查哈夫曼编码表
11、得到相应的字符f- 1( g- 1 ( c) ) ,用这个字符替换相应的码字就是还原的过程。因此,每从压缩文件中读出一个码字,就从哈夫曼编码表查得相应的字符替换,当文件中所有的码字被替换掉,这个解压过程也就完成了。压缩：首先从源文本文件当中读取数据，统计出字符各自出现的概率；在此基础上，根据统计出的概率建立哈夫曼树，并将该哈夫曼树的存储结果用文件保存；哈夫曼树建立好后，然后进行哈夫曼编码，并且将各个字符编码后的0、1码存储在文件当中；再一次读取源文件，对源文件进行压缩，将压缩后的二进制代码存储再文本文件中，生成一个文本文件；最后，对这个文本文件进行处理，生成一个二进制文件，其中一个字节代表上一
12、个文件的8个0、1码。 b、解压：首先根据二进制文件生成一个文本文件，这个文本文件比那个二进制文件要大，其中一个字节代表压缩文件的1位；按照哈夫曼树，将哈夫曼文件当中的哈夫曼编码生成对应的字符，存储在一个文本文件当中。至此，哈夫曼的编码/译码器就实现了。文件解压过程文件的解压过程是文件的压缩过程的逆过程,即将一个压缩文件还原成它的本来面目。因为一个压缩文件是不能够直接使用的,只有被解压后才能使用。一个被压缩的文件如果不能被解压,则这种压缩是毫无意义的。由于哈夫曼编码是即时码,因此只要得到一个码字c,则通过查哈夫曼编码表得到相应的字符f-1(g-1(c),用这个字符替换相应的码字就是还原的过程。因此,每从压缩文件中读出一个码字,就从哈夫曼编码表查得相应的字符替换,当文件中所有的码字被替换掉,这个解压过程也就完成了
