清华大学：《多媒体技术》课程教学资源（教材教案讲义）第4章无损数据压缩.doc_大学文库

第4章无损数据压缩冰水水冰本水冰水水水冰水水水本水冰本客*冰水水水水冰本水冰水水水水水水冰本冰客水冰水水水冰客水冰本水水水水水冰水水冰本水冰水水水水水水水*客 4.1仙农-范诺与赫夫曼编码 4.1.1仙农-范诺编码 4.1.2赫夫曼编码 4.2算术编码 4.3RLE编码 4.4词典编码 4.4.1词典编码的思想 4.4.2LZ77算法 4.4.3LZSS算法 4.4.4LZ78算法 4.4.5LZW算法练习与思考题参考文献和站点水冰水水求水水水冰客水水水水水水水水本水水水水水水水客*客水水水水冰水水水水水水水客水水水水水冰水客水水水水水水冰*水水水水水水半水*水水冰水数据压缩可分成两种类型,一种叫做无损压缩,另一种叫做有损压缩无损压缩是指使用压缩后的数据进行重构(或者叫做还原,解压缩),重构后的数据与原来的数据完全相同;无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平,无损压缩算法一般可以把普通文件的数据压缩到原来的1/2~1/4。一些常用的无损压缩算法有赫夫曼( Huffman)算法和 LZW( Lengel-Ziv& Welch)压缩算法有损压缩是指使用压缩后的数据进行重构,重构后的数据与原来的数据有所不同,但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如,图像和声音的压缩就可以采用有损压缩,因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息,丢掉一些数据而不至于对声音或者图像所表达的意思产生误解,但可大大提高压缩比。本章主要介绍目前用得最多和技术最成熟的无损压缩编码技术,包括包含赫夫曼编码、算术编码、RLE编码和词典编码。对于不打算开发压缩技术和编写压缩程序的读者可不必深究编译码的详细过程。 4.1仙农-范诺与赫夫曼编码 4.1.1仙农-范诺编码仙农-范诺编码算法需要用到下面两个基本概念: 1. Entropy(熵)的概念 (1)熵是信息量的度量方法,它表示某一事件出现的消息越多,事件发生的可能性就越小,数学上就是概率越小 2)某个事件的信息量用J1=-bog2P1表示,其中P,为第i个事件的概率, p 2.信源S的熵的定义按照仙农( Shannon)的理论,信源S熵定义为 H(s)=7=∑pbog2(l/P) 其中P是符号S在出现的概率;bog2(/p1)表示包含在S中的信息量,也就是编码s所需要的位数。例如,一幅用256级灰度表示的图像,如果每一个像素点灰度的概率均为 P1=1/256,编码每一个像素点就需要8比特

第4章无损数据压缩 *************************************************************************** 4.1 仙农-范诺与赫夫曼编码 4.1.1 仙农-范诺编码 4.1.2 赫夫曼编码 4.2 算术编码 4.3 RLE编码 4.4 词典编码 4.4.1 词典编码的思想 4.4.2 LZ77算法 4.4.3 LZSS算法 4.4.4 LZ78算法 4.4.5 LZW算法练习与思考题参考文献和站点 *************************************************************************** 数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩。无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的 1/2 ～ 1/4 。一些常用的无损压缩算法有赫夫曼 (Huffman) 算法和 LZW(Lenpel-Ziv & Welch)压缩算法。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。本章主要介绍目前用得最多和技术最成熟的无损压缩编码技术，包括包含赫夫曼编码、算术编码、RLE编码和词典编码。对于不打算开发压缩技术和编写压缩程序的读者可不必深究编译码的详细过程。 4.1 仙农-范诺与赫夫曼编码 4.1.1 仙农-范诺编码仙农-范诺编码算法需要用到下面两个基本概念： 1. Entropy(熵)的概念 (1) 熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。 (2) 某个事件的信息量用 i pi I 2 = −log 表示，其中 i p 为第 i 个事件的概率， 0  pi 1 2. 信源S的熵的定义按照仙农(Shannon)的理论，信源S的熵定义为 ( ) log (1/ ) 2 i i H s = =  pi p 其中 i p 是符号 i s 在S中出现的概率； log (1/ ) 2 pi 表示包含在 i s 中的信息量，也就是编码 i s 所需要的位数。例如，一幅用256级灰度表示的图像，如果每一个像素点灰度的概率均为 pi =1/ 256 ，编码每一个像素点就需要8比特

第4章无损数据压缩例4.1]有一幅40个像素组成的灰度图像,灰度共有5级,分别用符号表示,40个像素中出现灰度A像素数有15个,出现灰度B的像素数有7个,出现灰度C的数有7个等等,如表4-01所示。如果用3个比特表示5个等级的灰度值,也就是每个像素用3 比特表示,编码这幅图像总共需要120比特表4-01符号在图像中出现的数目号 ABCIDE 出现的次数|15|77[6|5 按照仙农理论,这幅图像的熵为 H(S)=(15/40)×bog2(40/15)+(7/40)×log2(40/7)+…+(5/40)×bog2(40/5) =2.196 这就是说每个符号用2.196比特表示,40个像素需用87.84比特。最早阐述和实现这种编码的是 Shannon(1948年)和Fano(1949年),因此被称为仙农-范诺 ( Shannon-Fano)算法。这种方法采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序,例如,A,B,C,D和E,如表4-02所示。然后使用递归方法分成两个部分,每一部分具有近似相同的次数,如图4-01所示。按照这种方法进行编码得到的总比特数为91,实际的压缩比约为1.3:1。表4-02 Shannon-Fano算法举例表符号出现的次数(P2)pg2(/P)分配的代码需要的比特数 15(0.375) 1.4150 B7(0175)2.514 14 6(0.150) 110 5(0.125) 3.0000 111 图4-01仙农-范诺算法编码举例 4.1.2赫夫曼编码赫夫曼( Huffman)在1952年提出了另一种编码方法,即从下到上的编码方法。现仍以一个具体的例子说明它的编码步骤 (1)初始化,根据符号概率的大小按由大到小顺序对符号进行排序,如表4-03和图4-02 所示。 (2)把概率最小的两个符号组成一个节点,如图4-02中的D和E组成节点P1 (3)重复步骤2,得到节点P、B和P,形成一棵“树”,其中的理称为根节点。 4)从根节点理开始到相应于每个符号的“树叶”,从上到下标上“0”(上枝)或者“1” (下枝),至于哪个为“1”哪个为“0”则无关紧要,最后的结果仅仅是分配的代码不同,而代码的平均长度是相同的

第4章无损数据压缩 2 [例4.1] 有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E 表示，40个像素中出现灰度A的像素数有15个，出现灰度B的像素数有7个，出现灰度C的像素数有7个等等，如表4-01所示。如果用3个比特表示5个等级的灰度值，也就是每个像素用3 比特表示，编码这幅图像总共需要120比特。表4-01 符号在图像中出现的数目符号 A B C D E 出现的次数 15 7 7 6 5 按照仙农理论，这幅图像的熵为 H(S) = (15/40)  2 log (40/15) + (7/40)  2 log (40/7) +  + (5/40)  2 log (40/5) =2.196 这就是说每个符号用2.196比特表示，40个像素需用87.84比特。最早阐述和实现这种编码的是Shannon(1948年)和Fano(1949年)，因此被称为仙农-范诺 (Shannon- Fano)算法。这种方法采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序，例如， A ， B ，C ， D 和 E ，如表4-02所示。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图4-01所示。按照这种方法进行编码得到的总比特数为91，实际的压缩比约为1.3 : 1。表4-02 Shannon-Fano算法举例表符号出现的次数( i p ) log (1/ ) 2 pi 分配的代码需要的比特数 A 15 (0.375) 1.4150 00 30 B 7 (0.175) 2.5145 01 14 C 7 (0.175) 2.5145 10 14 D 6 (0.150) 2.7369 110 18 E 5 (0.125) 3.0000 111 15 图4-01 仙农-范诺算法编码举例 4.1.2 赫夫曼编码赫夫曼(Huffman)在1952年提出了另一种编码方法，即从下到上的编码方法。现仍以一个具体的例子说明它的编码步骤： (1) 初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如表4-03和图4-02 所示。 (2) 把概率最小的两个符号组成一个节点，如图4-02中的D和E组成节点P1。 (3) 重复步骤2，得到节点P2、P3和P4，形成一棵“树”，其中的P4称为根节点。 (4) 从根节点P4开始到相应于每个符号的“树叶”，从上到下标上“0”(上枝)或者“1” (下枝)，至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的

第4章无损数据压缩 (5)从根节点P开始顺着树枝到每个叶子分别写出每个符号的代码,如表4-03所示。 (6)按照仙农理论,这幅图像的熵为 BS)=(15/39)×bg2(39/15)+(7/39)xkog2(39/7)+…+(5/39)x bog2(39/5)=2.1859 压缩比1.37:1 表4-03赫夫曼编码举例符号出现的次数|1og2(1/p)分配的代码需要的位数 A15(0.3846 15 B7(0.1795)2.48 C6(0.1538) 2.70 101 D6(0.1538270 110 E5(0.1282) 2.96 111 A(0.3846) 0 B(0.1795) c015381P2 D(01538)-0 E(0.1282) PI 图4-02赫夫曼编码方法赫夫曼码的码长虽然是可变的,但却不需要另外附加同步代码。例如,码串中的第1位为0,那末肯定是符号A,因为表示其他符号的代码没有一个是以0开始的,因此下一位就表示下一个符号代码的第1位。同样,如果出现“110”,那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”,即码簿,那么就可以根据码簿一个码一个码地依次进行译码采用赫夫曼编码时有两个问题值得注意:①赫夫曼码没有错误保护功能,在译码时,如果码串中没有错误,那么就能一个接一个地正确译出代码。但如果码串中有错误,哪怕仅仅是1位出现错误,不但这个码本身译错,更糟糕的是一错一大串,全乱了套,这种现象称为错误传播( error propagation)。计算机对这种错误也无能为力,说不出错在哪里,更谈不上去纠正它。②赫夫曼码是可变长度码,因此很难随意查找或调用压缩文件中间的内容,然后再译码,这就需要在存储代码之前加以考虑。尽管如此,赫夫曼码还是得到广泛应用。与仙农一范诺编码相比,这两种方法都自含同步码,在编码之后的码串中都不须要另外加标记符号,即在译码时分割符号的特殊代码。此外,赫夫曼编码方法的编码效率比仙农范诺编码效率高一些。请读者自行验证。 4.2算术编码算术编码在图像数据压缩标准(如JPEG,JBIG)中扮演了重要的角色。在算术编码中,消息用0到1之间的实数进行编码,算术编码用到两个基本的参数:符号的概率和它的编码间隔信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔,而这些间隔包含

第4章无损数据压缩 3 (5) 从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码，如表4-03所示。 (6) 按照仙农理论，这幅图像的熵为 H(S) = (15/39)  2 log (39/15) + (7/39)  2 log (39/7) +  + (5/39)  2 log (39/5) = 2.1859 压缩比1.37:1。表4-03 赫夫曼编码举例符号出现的次数 log2(1/pi) 分配的代码需要的位数 A 15(0.3846) 1.38 0 15 B 7(0.1795) 2.48 100 21 C 6(0.1538) 2.70 101 18 D 6(0.1538) 2.70 110 18 E 5(0.1282) 2.96 111 15 图4-02 赫夫曼编码方法赫夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。采用赫夫曼编码时有两个问题值得注意：①赫夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅仅是1位出现错误，不但这个码本身译错，更糟糕的是一错一大串，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。②赫夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，赫夫曼码还是得到广泛应用。与仙农-范诺编码相比，这两种方法都自含同步码，在编码之后的码串中都不须要另外添加标记符号，即在译码时分割符号的特殊代码。此外，赫夫曼编码方法的编码效率比仙农 -范诺编码效率高一些。请读者自行验证。 4.2 算术编码算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含

第4章无损数据压缩 4 在0到1之间。编码过程中的间隔决定了符号压缩后的输出。算术编码器的编码过程可用下面的例子加以解释。 [例4.2] 假设信源符号为{00, 01, 10, 11}，这些符号的概率分别为{ 0.1, 0.4, 0.2, 0.3 }，根据这些概率可把间隔[0, 1)分成4个子间隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1)，其中 [x, y) 表示半开放间隔，即包含 x 不包含 y 。上面的信息可综合在表4-04中。表4-04 信源符号，概率和初始编码间隔符号 00 01 10 11 概率 0.1 0.4 0.2 0.3 初始编码间隔 [0, 0.1) [0.1, 0.5) [0.5, 0.7) [0.7, 1] 如果二进制消息序列的输入为：10 00 11 00 10 11 01，编码时首先输入的符号是10，找到它的编码范围是[0.5, 0.7]。由于消息中第二个符号00的编码范围是[0, 0.1)，因此它的间隔就取[0.5, 0.7)的第一个十分之一作为新间隔[0.5, 0.52)。依此类推，编码第3个符号11时取新间隔为[0.514, 0.52)，编码第4个符号00时，取新间隔为[0.514, 0.5146)，… 。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图4-03所示。图4-03 算术编码过程举例这个例子的编码和译码的全过程分别表示在表4-05和表4-06中。根据上面所举的例子，可把计算过程总结如下。考虑一个有 M 个符号 a (1,2, ,M ) i =  的字符表集，假设概率 p ai = pi ( ) ，而 ( )＝ 1 2 ) 1 1  + + + = = M M i pi ai p p  p 。输入符号用 n x 表示，第 n 个子间隔的范围用  = − = = = − + − − − + i i n i i i I n l n rn l n dn pi l n d p 1 1 1 1 1 1 1 [ , ) [ , ) 表示。其中 l 0 = 0 ，d0 = 1 和 p0 = 0， n l 表示间隔左边界的值, n r 表示间隔右边界的值， n n n d = r − l 表示间隔长度。编码步骤如下：步骤1：首先在1和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率，初始子间隔的范围用 I1 = [l 1 ,r1 ) = [ = − i i pi 1 1 ，= i i i p 1 )表示。令 1 1 1 d = r −l ， 1 L = l 和 1 R = r 。步骤2：L和R的二进制表达式分别表示为：

第4章无损数据压缩 5   = − = 1 2 k k L uk 和   = − = 1 2 k k k R v 其中 k u 和 k v 等于“1”或者“0”。比较 1 u 和 1 v ：①如果 1 1 u  v ，不发送任何数据，转到步骤3；②如果 1 1 u = v ，就发送二进制符号 1 u 。比较 u2 和 2 v ：①如果 2 2 u  v ，不发送任何数据，转到步骤3；②如果 2 2 u = v ，就发送二进制符号 u2 。 … 这种比较一直进行到两个符号不相同为止，然后进入步骤3，步骤3： n 加1，读下一个符号。假设第 n 个输入符号为 n ai x = ，按照以前的步骤把这个间隔分成如下所示的子间隔：   = = = = − + − − − + − i i i i n n n n n i n dn pi I I r I d p I 1 1 1 1 1 1 1 [ , ) [ , ) 令 n L = I ， n R = r 和 n n n d = r − I ，然后转到步骤2。表4-05 编码过程步骤输入符号编码间隔编码判决 1 10 [0.5, 0.7] 符号的间隔范围[0.5, 0.7) 2 00 [0.5, 0.52] [0.5, 0.7]间隔的第一个1/10 3 11 [0.514, 0.52] [0.5, 0.52]间隔的最后三个1/10 4 00 [0.514, 0.5146] [0.514, 0.52]间隔的第一个1/10 5 10 [0.5143, 0.51442] [0.514, 0.5146]间隔的第五个1/10开始，二个1/10 6 11 [0.514384, 0.51442] [0.5143, 0.51442]间隔的最后3个1/10 7 01 [0.5143836, 0.514402] [0.514384, 0.51442]间隔的4个1/10，从第1个1/10 开始 8 从[0.5143876, 0.514402)中选择一个数作为输出：0.5143876 表4-06 译码过程步骤间隔译码符号译码判决 1 [0.5, 0.7] 10 0.51439在间隔 [0.5, 0.7) 2 [0.5, 0.52] 00 0.51439在间隔 [0.5, 0.7)的第1个1/10 3 [0.514, 0.52] 11 0.51439在间隔[0.5, 0.52)的第7个1/10 4 [0.514, 0.5146] 00 0.51439在间隔[0.514, 0.52)的第1个1/10 5 [0.5143, 0.51442] 10 0.51439在间隔[0.514, 0.5146)的第5个1/10 6 [0.514384, 0.51442] 11 0.51439在间隔[0.5143, 0.51442)的第7个1/10 7 [0.51439, 0.5143948] 01 0.51439在间隔[0.51439, 0.5143948] 的第 1个 1/10 7 译码的消息：10 00 11 00 10 11 01 [例3] 假设有4个符号的信源，它们的概率如表4-07所示：表4-07 符号概率信源符号ai a1 2 a 3 a 4 a 概率 i p p1 = 0.5 p2 = 0.25 p3 = 0.125 p4 = 0.125

第4章无损数据压缩表4-08译码过程表接受的数字间隔译码输出 [0.5,1) [0.5,0.75) [0.5,0.609375 [0.5625,0.609375) [0.59375,0.609375)a 在上面的例子中,我们假定编码器和译码器都知道消息的长度,因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符,当译码器看到终止符时就停止译码在算术编码中需要注意的几个问题: (1)由于实际的计算机的精度不可能无限长,运算中出现溢出是一个明显的问题,但多数机器都有16位、32位或者64位的精度,因此这个问题可使用比例缩放方法解决 (2)算术编码器对整个消息只产生一个码字,这个码字是在间隔[0,1)中的一个实数因此译码器在接受到表示这个实数的所有位之前不能进行译码 (3)算术编码也是一种对错误很敏感的编码方法,如果有一位发生错误就会导致整个消息译错。算术编码可以是静态的或者自适应的。在静态算术编码中,信源符号的概率是固定的。在自适应算术编码中,信源符号的概率根据编码时符号出现的频繁程度动态地进行修改,在编码期间估算信源符号概率的过程叫做建模。需要开开发态算术编码的原因是因为事先知道精确的信源概率是很难的,而且是不切实际的。当压缩消息时,我们不能期待一个算术编码器获得最大的效率,所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键, 4.3RLE编码现实中有许多这样的图像,在一幅图像中具有许多颜色相同的图块。在这些图块中,许多行上都具有相同的颜色,或者在一行上有许多连续的像素都具有相同的颜色值。在这种情况下就不需要存储每一个像素的颜色值,而仅仅存储一个像素的颜色值,以及具有相同颜色的像素数目就可以,或者存储一个像素的颜色值,以及具有相同颜色值的行数。这种压缩编码称为行程编码( run length encoding,RLE),具有相同颜色并且是连续的像素数目称为行程长度。为了叙述方便,假定有一幅灰度图像,第n行的像素值如图4-05所示: 00000000111888······888111100000000 } 8个03个150个 4个18 图4-05RLE编码的概念用RLE编码方法得到的代码为:80315084180。代码中用黑体表示的数字是行程长度,黑体字后面的数字代表像素的颜色值。例如黑体字50代表有连续50个像素具有相同的颜色值, 它的颜色值是8。对比RLE编码前后的代码数可以发现,在编码前要用73个代码表示这一行的数据,而编码后只要用11个代码表示代表原来的73个代码,压缩前后的数据量之比约为7:1,即压缩比为7:1。这说明RLE确实是一种压缩技术,而且这种编码技术相当直观,也非常经济。RLE所

第4章无损数据压缩 7 表4-08 译码过程表接受的数字间隔译码输出 1 [0.5, 1) - 0 [0.5, 0.75) a2 0 [0.5, 0.609375) 1 a 1 [0.5625, 0.609375) - 1 [0.59375, 0.609375) 3 a … … … 在上面的例子中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符，当译码器看到终止符时就停止译码。在算术编码中需要注意的几个问题： (1) 由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。 (2) 算术编码器对整个消息只产生一个码字，这个码字是在间隔[0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。 (3) 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开开发态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。 4.3 RLE编码现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的像素都具有相同的颜色值。在这种情况下就不需要存储每一个像素的颜色值，而仅仅存储一个像素的颜色值，以及具有相同颜色的像素数目就可以，或者存储一个像素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码(run length encoding，RLE)，具有相同颜色并且是连续的像素数目称为行程长度。为了叙述方便，假定有一幅灰度图像，第n行的像素值如图4-05所示： 00000000 111 888 • • • • • • 888 1111 00000000 8个0 3个1 50个8 4个1 8个0 图4-05 RLE编码的概念用RLE编码方法得到的代码为：80315084180。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表像素的颜色值。例如黑体字50代表有连续50个像素具有相同的颜色值，它的颜色值是8。对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用11个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1。这说明RLE确实是一种压缩技术，而且这种编码技术相当直观，也非常经济。RLE所

第4章无损数据压缩能获得的压缩比有多大,这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大,图像块数目越少,获得的压缩比就越高。反之,压缩比就越小。译码时按照与编码时采用的相同规则进行,还原后得到的数据与压缩前的数据完全相同。因此,RLE是无损压缩技术 RLE压缩编码尤其适用于计算机生成的图像,对减少图像文件的存储空间非常有效。然而,RE对颜色丰富的自然图像就显得力不从心,在同一行上具有相同颜色的连续像素往往很少,而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法,不仅不能压缩图像数据,反而可能使原来的图像数据变得更大。请注意,这并不是说RLE编码方法不适用于自然图像的压缩,相反,在自然图像的压缩中还真少不了RLE,只不过是不能单纯使用RLE一种编码方法,需要和其他的压缩编码技术联合应用。 4.4词典编码有许多场合,开始时不知道要编码数据的统计特性,也不一定允许你事先知道它们的统计特性。因此,人们提出了许许多多数的据压缩方法,企图用来对这些数据进行压缩编码在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。词典编码 ( Dictionary Encoding)技术就是属于这一类,这种技术属于无损压缩技术。 4.4.1词典编码的思想词典编码( dictionary encoding)的根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图像就具有这种特性。词典编码法的种类很多,归纳起来大致有两类。第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过, 然后用已经出现过的字符串替代重复的部分,它的输出仅仅是指向早期出现过的字符串的 “指针”。这种编码概念如图4-06所示数据回回四国国国国国… 数据流国国d画图4-06第一类词典法编码概念这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以 Abraham Lempel和 Jakob Ziv在1977年开发和发表的称为LZ77算法为基础的,例如1982年由 Storer和 Szymanski改进的称为LZSS算法就是属于这种情况第二类算法的想法是企图从输入的数据中创建一个“短语词典( dictionary of the phrases)”,这种短语不一定是像“严谨勤奋求实创新”和“国泰民安是坐稳总统宝座的根本”这类具有具体含义的短语,它可以是任意字符的组合。编码数据过程中当遇到己经在词典中出现的“短语”时,编码器就输出这个词典中的短语的“索引号”,而不是短语本身。这个概念如图4-07所示

第4章无损数据压缩 8 能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE是无损压缩技术。 RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。然而，RLE对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。请注意，这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中还真少不了RLE，只不过是不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。 4.4 词典编码有许多场合，开始时不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。因此，人们提出了许许多多数的据压缩方法，企图用来对这些数据进行压缩编码，在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。词典编码 (Dictionary Encoding)技术就是属于这一类，这种技术属于无损压缩技术。 4.4.1 词典编码的思想词典编码(dictionary encoding)的根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图像就具有这种特性。词典编码法的种类很多，归纳起来大致有两类。第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的 “指针”。这种编码概念如图4-06所示。图4-06 第一类词典法编码概念这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年开发和发表的称为LZ77算法为基础的，例如1982年由Storer和Szymanski改进的称为LZSS算法就是属于这种情况。第二类算法的想法是企图从输入的数据中创建一个“短语词典(dictionary of the phrases)”，这种短语不一定是像“严谨勤奋求实创新”和“国泰民安是坐稳总统宝座的根本”这类具有具体含义的短语，它可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。这个概念如图4-07所示

第4章无损数据压缩囗国四囗区国囗四四图407第二类词典法编码概念 J.Ziv和A. Lempel在1978年首次发表了介绍这种编码方法的文章。在他们的研究基础上 Terry A. Welch在1984年发表了改进这种编码算法的文章,因此把这种编码方法称为 Lzw( Lempel- Ziv Walch)压缩编码,首先在高速硬盘控制器上应用了这种算法 4.4.2LZ77算法为了更好地说明LZ7算法的原理,首先介绍算法中用到的几个术语: (1)输入数据流( Input stream):要被压缩的字符序列。 (2)字符( character):输入数据流中的基本单元。 (3)编码位置( coding position):输入数据流中当前要编码的字符位置,指前向缓冲存储器中的开始字符。 (4)前向缓冲存储器( Lookahead buffer):存放从编码位置到输入数据流结束的字符序列的存储器 (5)窗口( window):指包含W个字符的窗口,字符是从编码位置开始向后数也就是最后处理的字符数 (6)指针( pointer):指向窗口中的匹配串且含长度的指针 LZ7编码算法的核心是査找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下 (1)把编码位置设置到输入数据流的开始位置。 (2)查找窗口中最长的匹配串 (3)以“( Pointer, Length) Characters”的格式输出,其中 Pointer是指向窗口中匹配串的指针, Length表示匹配字符的长度, Characters是前向缓冲存储器中的不匹配的第1个字符。 (4)如果前向缓冲存储器不是空的,则把编码位置和窗口向前移( Length+1)个字符, 然后返回到步骤2。 [例4.匀]待编码的数据流如表4-09所示,编码过程如表4-10所示。现作如下说明: “步骤”栏表示编码步骤。 ②)“位置”栏表示编码位置,输入数据流中的第1个字符为编码位置1 (3)“匹配串”栏表示窗口中找到的最长的匹配串。 (4)“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符 (5)“输出”栏以“( Back chars, Chars length) Explicit character”格式输出其中,( Back chars, Chars length)是指向匹配串的指针,告诉译码器“在这个窗口中向后退 Back chars个字符然后拷贝 Chars length个字符到输出” Explicit character是真实字符。例如,表4-10中的输出“(5,2)C”告诉译码器回退5个字符,然后拷贝2个字符“AB

第4章无损数据压缩 9 图4-07 第二类词典法编码概念 J.Ziv和A.Lempel在1978年首次发表了介绍这种编码方法的文章。在他们的研究基础上， Terry A.Weltch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为 LZW(Lempel-Ziv Walch)压缩编码，首先在高速硬盘控制器上应用了这种算法。 4.4.2 LZ77算法为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语： (1) 输入数据流(input stream)：要被压缩的字符序列。 (2) 字符(character)：输入数据流中的基本单元。 (3) 编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。 (4) 前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。 (5) 窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。 (6) 指针(pointer)：指向窗口中的匹配串且含长度的指针。 LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下： (1) 把编码位置设置到输入数据流的开始位置。 (2) 查找窗口中最长的匹配串。 (3) 以“(Pointer, Length) Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。 (4) 如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。 [例4.4] 待编码的数据流如表4-09所示，编码过程如表4-10所示。现作如下说明： (1) “步骤”栏表示编码步骤。 (2) “位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。 (3) “匹配串”栏表示窗口中找到的最长的匹配串。 (4) “字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。 (5) “输出”栏以“(Back_chars, Chars_length) Explicit_character”格式输出。其中，(Back_chars, Chars_length)是指向匹配串的指针，告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”， Explicit_character是真实字符。例如，表4-10中的输出“(5,2) C”告诉译码器回退5个字符，然后拷贝2个字符“AB

第4章无损数据压缩表4-09待编码的数据流位置12|3456789 字符|AA| BCBBALBIC 表4-10编码过程步骡位置|匹配串字符|输出 A|(0,0)A C(0,0)C B(2,1)B 57ABc[65,2)d 4.4.3LZSS算法 LZ7通过输出真实字符解决了在窗口中出现没有匹配串的问题,但这个解决方案包含有冗余信息。冗余信息表现在两个方面,一是空指针,二是编码器可能输出额外的字符,这种字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题,它的思想是如果匹配串的长度比指针本身的长度长就输出指针,否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身,为了区分它们就需要有额外的标志位,即ID位 LZSS编码算法的具体执行步骤如下: (1)把编码位置置于输入数据流的开始位置。 (2)在前向缓冲存储器中查找与窗口中最长的匹配串 ① Pointer:=匹配串指针。 2 Length:=匹配串长度 (3)判断匹配串长度 Length是否大于等于最小匹配串长度 Length≥ MIN LENGTH), 如果“是”:输出指针,然后把编码位置向前移动 Length个字符。如果“否”:输出前向缓冲存储器中的第1个字符,然后把编码位置向前移动一个 (4)如果前向缓冲存储器不是空的,就返回到步骤2 [例4.5]编码字符串如表4-11所示,编码过程如表4-12所示。现说明如下 (1)“步骤”栏表示编码步骤。 (2)“位置”栏表示编码位置,输入数据流中的第1个字符为编码位置1 (3)“匹配”栏表示窗口中找到的最长的匹配串。 (4)“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符 (5)“输出”栏的输出为 ①如果匹配串本身的长度 Length≥ MIN LENGTH,输出指向匹配串的指针,格式为( Back chars, Chars length)。该指针告诉译码器“在这个窗口中向后退 Back chars个字符然后拷贝 Chars length个字符到输出” ②如果匹配串本身的长度 Length≤ MIN LENGTH,则输出真实的匹配串。表4-11输入数据流 12|34567 AABIBICBIB 表4-12编码过程 MIN LENGTH=2) 步骤位置匹配串输出

第4章无损数据压缩 10 表4-09待编码的数据流位置 1 2 3 4 5 6 7 8 9 字符 A A B C B B A B C 表4-10 编码过程步骤位置匹配串字符输出 1 1 -- A (0,0) A 2 2 A B (1,1) B 3 4 -- C (0,0) C 4 5 B B (2,1) B 5 7 A B C (5,2) C 4.4.3 LZSS算法 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即ID位。 LZSS编码算法的具体执行步骤如下： (1) 把编码位置置于输入数据流的开始位置。 (2) 在前向缓冲存储器中查找与窗口中最长的匹配串 ① Pointer ：=匹配串指针。 ② Length ：=匹配串长度。 (3) 判断匹配串长度Length是否大于等于最小匹配串长度(Length  MIN_LENGTH) ，如果“是”：输出指针，然后把编码位置向前移动Length个字符。如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。 (4) 如果前向缓冲存储器不是空的，就返回到步骤2。 [例4.5] 编码字符串如表4-11所示，编码过程如表4-12所示。现说明如下： (1) “步骤”栏表示编码步骤。 (2) “位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。 (3) “匹配”栏表示窗口中找到的最长的匹配串。 (4) “字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。 (5) “输出”栏的输出为： ① 如果匹配串本身的长度Length  MIN_LENGTH，输出指向匹配串的指针，格式为(Back_chars, Chars_length)。该指针告诉译码器“在这个窗口中向后退 Back_chars个字符然后拷贝Chars_length个字符到输出”。 ② 如果匹配串本身的长度Length  MIN_LENGTH，则输出真实的匹配串。表4-11 输入数据流位置 1 2 3 4 5 6 7 8 9 10 11 字符 A A B B C B B A A B C 表4-12 编码过程(MIN_LENGTH = 2) 步骤位置匹配串输出 1 1 -- A 2 2 A A

清华大学：《多媒体技术》课程教学资源（教材教案讲义）第4章 无损数据压缩

清华大学：《多媒体技术》课程教学资源（教材教案讲义）第4章无损数据压缩