2.常用数据压缩技术

1、常用数据压缩技术n主要内容n香农-范诺编码nHuffman编码n算术编码n行程编码(Run Length Encoding)n词典编码n预测编码n变换编码O、香农-范诺编码n熵(Entropy)的概念n熵是信息量的度量方法，表示一条信息中真正需要编码的信息量。熵的单位是bits。事件发生的可能性越小数学上就是概率越小，表示某一事件出现的消息越多。n某个事件的信息量用Ii -log2 pi 表示， 其中pi 为第 i 个事件的概率， 0 pi 1O、香农-范诺编码n信源S 的熵n按照香农(Shannon)的理论，信源 S 的熵定义为其中 为符号S i 在S中出现的概率。 表示包含在S i 中的信

2、息量，也就是编码S i 所需要的位数。n按照香农的理论，熵是平稳信源的无损压缩效率的极限。例如，一幅用256级灰度表示的图像，如果每一个像素点灰度的概率均为 pi=1/256，编码每一个像素点就需要8位比特，bit。 例例 对下面这条只出现了对下面这条只出现了 a a、b b、c c 三个字符的字符串：三个字符的字符串：aabbaccbaaaabbaccbaa，字符串长度为，字符串长度为 10 10，字符，字符 a b c a b c 分别出现了分别出现了 5 5、3 3、2 2 次，那么次，那么 a a、b b、c c 在信息中出现的概率分别为在信息中出现的概率分别为 0.5 0.3 0.2

3、0.5 0.3 0.2，他们的熵分别为：，他们的熵分别为： Ea = -log2(0.5) = 1 Ea = -log2(0.5) = 1 Eb = -log2(0.3) = 1.737 Eb = -log2(0.3) = 1.737 Ec = -log2(0.2) = 2.322 Ec = -log2(0.2) = 2.322整条信息的熵也即表达整个字符串需要的位数为：整条信息的熵也即表达整个字符串需要的位数为： Ea Ea * * 5 + Eb 5 + Eb * * 3 + Ec 3 + Ec * * 2 = 14.855 2 = 14.855 位位 如果用计算机中常用的如果用计算机中常用

4、的 ASCII ASCII 编码，表示上面的字符编码，表示上面的字符串需要整整串需要整整8080位！位！ 信息为什么能被压缩而不丧失原有的信息内容呢？简信息为什么能被压缩而不丧失原有的信息内容呢？简单地讲，用较少的位数表示较频繁出现的符号，这就是数单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的根本准那么。据压缩的根本准那么。 例例 有一幅4040个象素组成的灰度图像，灰度共有5 5级，分别用符号A、B、C、D和E表示，4040个象素中出现灰度A的象素数有1515个，出现灰度B的象素数有7 7个，出现灰度C的象素数有7 7个等等，如表所示。如果用3 3个位表示5 5个等级的灰度值，也

5、就是每个象素用3 3位表示，编码这幅图像总共需要120120位。香农-范诺编码算法步骤n按照符号出现的概率减少的顺序将待编码的符号排成序列。 n将符号分成两组，使这两组符号概率和相等或几乎相等。 n将第一组赋值为0，第二组赋值为1。 n对每一组，重复步骤2、3的操作。01000111ABCDE按照这种方法进行编码得到的总位数为91，实际的压缩比约为120 : 911.3 : 1 一、Huffman编码nHuffman编码属于信息熵编码的方法之一；n信息熵编码又称统计编码,它是根据信源符号出现概率的分布特性而进行的压缩编码；n信息熵编码根本思想: 在信源符号和码字之间建立明确的一一对应关系，以便

6、在恢复时能准确地再现原信号，同时要使平均码长或码率尽量小；n信息熵编码的代表nHuffman编码n算术编码一、 Huffman编码nHuffman编码的理论根底是Huffman定理；nHuffman定理1952年Huffman提出的 在变长编码中,对出现概率大的信源符号赋于短码字,而对于出现概率小的信源符号赋于长码字。如果码字长度严格按照所对应符号出现概率大小逆序排列,那么编码结果平均码字长度一定小于任何其它排列方式。n也称为最正确编码，平均码长最短。Huffman编码步骤(1) 将信源符号按概率递减顺序排列；(2) 把二个最小概率相加作为新符号的概率，并按(1) 重排；(3) 重复(1)、(

7、2)，直到概率为1；(4) 在每次合并信源时，将合并的信源分别赋“0和“1(如概率大的赋“0,概率小的赋“1)；(5) 寻找从每一信源符号到概率为1处的路径，记录下路径上的“1和“0；(6)写出每一符号的“1、“0序列(从树根到信源符号节点)。Huffman编码例如n平均码字长度: R=Pii= n该信源的信息熵：H=Pilog2Pi =(i )(Pi)M0M1M2M3M4M5M6M710M0M1M2M3M4M5M6M710信源符号信源符号概率概率编码过程编码过程码字码字码长码长(i)x1 x2x3x4x5x6x7x80.40 0.180.10 0.10 0.070.060.050.041 0

8、0101100000100010100010 000111 33444550101010.090.130.190.230.370.601010011平均码字长度: R=？该信源的信息熵：H= ？！编程实现Huffman编解码算法R=Pii=0.401+0.183+0.103+0.104+0.074 +0.064+0.055+0.045二、算术编码n20世纪60年代初，Elias提出了算术编码Arithmetic Coding的概念。n1976年，Rissanen和Pasco首次介绍了它的实用技术。其根本原理是：将编码的信息表示成实数0和1之间的一个间隔(Interval) ，信息越长，编码表示

9、它的间隔就越小，表示这一间隔所需的二进制位就越多。n算术编码对整条信息无论信息有多么长，其输出仅仅是一个数，而且是一个介于 0 和 1 之间的二进制小数。例如算术编码对某条信息的输出为 1010001111，那么它表示小数 0.1010001111，也即十进制数 0.64。算术编码例如n采用固定模式符号概率分配如下： 字符: a e i o u 概率 范围:0,0.2) 0.2,0.5) 0.5,0.6)0.6,0.8)0.8,1.0)n编码数据串为eai。令high间隔的高端， low为低端，range为间隔的长度， rangelow为编码字符分配的间隔低端， rangehigh为编码字符分

10、配的间隔高端。 n初始high=1，low=0， range=high-low， 一个字符编码后新的low和high按下式计算： low=low+rangerangelow； high=low+rangerangehigh。(1) 在第一个字符e被编码时， e的rangelow=0.2， rangehigh=0.5， 因此： 此时分配给e的范围为0.2， 0.5) (2) 第二个字符a编码时使用新生成范围0.2，0.5)， a的rangelow=0， rangehigh=0.2， 因此： 范围变成0.2， 0.26) (3) 对下一个字符i编号， i的rangelow=0.5，rangehig

11、h=0.6，range=0.06， 那么： 结果：用0.23， 0.236)表示数据串eai，如果解码器知道最后范围是0.23， 0.236)，它马上可解得一个字符为e， 然后依次得到惟一解a、i， 最终得到eai。 1e 0.5ea 0.26 0.2360.80.60.50.20uoieauoieauoieauoiea 0.2 0.2 0.23eai字符: a e i o u概率范围:0,0.2) 0.2,0.5) 0.5,0.6)0.6,0.8)0.8,1.0)eai算术编码过程表示算术编码过程表示n算术编码的优缺点：n对整个消息只产生一个码字,无需用一个特定的代码替代一个输入符号；n小数

12、的精度不可能无限长，在运算中存在溢出的问题需要解决；n对错误非常敏感；n信源符号概率接近时，建议使用算术编码，这种情况下其效率高于Huffman编码(约5%)。n可以不必预先定义概率模型，自适应模式自适应模式具有独特的优点；！编程实现算术编解码算法三、行程编码n行程编码RLE， Run Length EncodingRLE编码的结果是：80315084180压缩比：73 ：11 7 ：1！编程实现RLE编解码算法三、行程编码nRLE所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。nRLE压缩编码尤

13、其适用于计算机生成的图像，对颜色丰富的自然图像就显得力不从心。n在自然图像的压缩中少不了RLE，但需要和其他的压缩编码技术联合应用。 四、词典编码n词典编码的根据：数据本身包含有重复代码 n词典编码的种类：n第一类：查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的局部，它的输出仅仅是指向早期出现过的字符串的“指针 。四、词典编码n第二类：企图从输入的数据中创立一个“短语词典，编码数据过程中当遇到已经在词典中出现的“短语时，编码器就输出这个词典中的短语的“索引号，而不是短语本身。 LZ77LZ77算法n几个术语 n输入数据流(input stream)：要被

14、压缩的字符序列n字符(character)：输入数据流中的根本单元 n编码位置(coding position)：输入数据流中当前要编码的字符位置 n前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器 n窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数n指针(pointer)：指向窗口中的匹配串且含长度的指针 LZ77LZ77算法n编码步骤：n把编码位置设置到输入数据流的开始位置 n查找窗口(最近输入的W个字符)中最长的匹配串n以“(Pointer, Length) Characters的格式输出，其

15、中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器不匹配的第1个字符。 n如果前向缓冲存储器不是空的，那么把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。 位置位置1 12 23 34 45 56 67 78 89 9字符字符 A AA AB BC CB BB BA AB BC C步骤步骤位置位置匹配串匹配串 字符字符 输出输出 1 11 1-A A(0,0) (0,0) A A2 22 2A AB B(1,1) (1,1) B B3 34 4-C C(0,0) (0,0) C C4 45 5B BB B(2,1)

16、 (2,1) B B5 57 7A BA BC C(5,2) (5,2) C C待编码的数据流待编码的数据流 编码过程编码过程 LZSSLZSS算法nLZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。 nLZSS根本思想：如果匹配串的长度比指针本身的长度长就输出指针，否那么就输出真实字符。LZSSLZSS算法nLZSS编码算法的具体执行步骤如下：n1. 把编码位置置于输入数据流的开始位置。n2. 在前向缓冲存储器中查找与窗口中最长的匹配串 Poi

17、nter：= 匹配串指针。 Length ：= 匹配串长度。n3. 判断匹配串长度Length是否大于等于最小匹配串长度，如果“是：输出指针，然后把编码位置向前移动Length个字符。如果“否：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。n4. 如果前向缓冲存储器不是空的，就返回到步骤2。 输入数据流输入数据流编码过程编码过程( (MIN_LENGTH MIN_LENGTH = 2)= 2)步骤步骤位置位置 匹配串匹配串输出输出1 11 1-A A2 22 2A AA A3 33 3-B B4 44 4B BB B5 55 5-C C6 66 6B BB B(3,2)(3

18、,2)7 78 8A A BA A B(7,3)(7,3)8 81111C CC C位置位置1 12 23 34 45 56 67 78 89 910101111字符字符 A AA AB BB BC CB BB BA AA AB BC CLZ78算法n几个术语n字符流(Charstream)：要被编码的数据序列，即输入的数据流n字符(Character)：字符流中的根本数据单元 n前缀(Prefix)：在一个字符之前的字符序列 n缀 符串(String)：前缀字符 n码字(Code word)：码字流中的根本数据单元，代表词典中的一串字符 n码字流(Codestream)：码字和字符组成的序列

19、，是编码器的输出 LZ78算法n词典(Dictionary)：缀-符串表。按照词典中的索引号对每条缀 符串(String)指定一个码字(Code word)n当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。n当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。 n当前码字(Current code word)：在译码算法中使用，指当前处理的码字，用W表示当前码字，表示当前码字的缀 符串。 LZ78算法nLZ78的编码思想是不断地从字符流中提取新的缀 符串(String)，通俗地理解为新“词条，然后

20、用“代号也就是码字(Code word)表示这个“词条。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Charstream)，生成码字流(Codestream)，从而到达压缩数据的目的。 LZ78算法nLZ78 编码的具体算法如下:n步骤1： 在开始时，词典和当前前缀 P 都是空的。n步骤2： 当前字符 C := 字符流中的下一个字符。n步骤3： 判断 P+C 是否在词典中：n (1) 如果“是：用C扩展P，让 P := P+C ；n (2) 如果“否：n 输出与当前前缀 P 相对应的码字和当前字符 C；n 把字符串 P+C 添加到词典中。n 令 P :=空值。n

21、(3) 判断字符流中是否还有字符需要编码n 如果“是：返回到步骤2。n 如果“否：假设当前前缀 P 不是空的，输出相应于当前前缀 P 的码字， 然后结束编码。 编码字符串编码字符串位置位置1 12 23 34 45 56 67 78 89 9字符字符 A AB BB BC CB BC CA AB BA A编码过程编码过程步骤步骤位置位置 词典词典输出输出 1 11 1A A(0,(0,A)A)2 22 2B B(0,(0,B)B)3 33 3B CB C(2,(2,C)C)4 45 5B C AB C A(3,(3,A)A)5 58 8B AB A(2,(2,A)A)1 D= P= C=A P

22、+C=A N: output (0,A) D1=A P=2 C=B P= P+C=B N: output (0,B) D2=B P=3 C=B P= P+C=B Y: P=P+C=B4 C=C P=B P+C=BC N: output (2,C) D3=BC P=5 C=B P= P+C=B Y: P=P+C=B6 C=C P=B P+C=BC Y: P=P+C=BC7 C=A P=BC P+C=BCA N: output (3,A) D4=BCA P=8 C=B P= P+C=B Y: P=P+C=BLZW算法nLZW与LZ78 的差异nLZW只输出代表词典中的缀 符串(String)的码字

23、(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root) ；n由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在词典中搜索的第1个缀 符串有两个字符。 LZW算法n编码算法：n 步骤1: 开始时的词典包含所有可能的根(Root)，而当前前 缀 P 是空的；n 步骤2: 当前字符(C) := 字符流中的下一个字符；n 步骤3: 判断缀 符串 P+C 是否在词典中 (1) 如果“是：P := P+C / (用C扩展P) ； (2) 如果“否 把代表当前前

24、缀 P 的码字输出到码字流; 把缀 符串 P+C 添加到词典; 令 P := C /(现在的P仅包含一个字符C);n 步骤4: 判断码字流中是否还有码字要译 (1) 如果“是，就返回到步骤2； (2) 如果“否 把代表当前前缀P的码字输出到码字流; 结束。 被编码的字符串被编码的字符串位置位置1 12 23 34 45 56 67 78 89 9字符字符 A AB BB BA AB BA AB BA AC CLZWLZW的编码过程的编码过程步骤步骤 位置位置 词典词典输出输出(1)(1)A A(2)(2)B B(3)(3)C C1 11 1(4)(4)A BA B(1)(1)2 22 2(5)

25、(5)B BB B(2)(2)3 33 3(6)(6)B AB A(2)(2)4 44 4(7)(7)A B AA B A(4)(4)5 56 6(8)(8)A B A CA B A C(7)(7)6 6-(3)(3)1 P= C=A P+C=A Y: P=P+C=A2 C=B P=A P+C=AB N: output A.w=1 D=D+AB P=B3 C=B P=B P+C=BB N: output B.W=2 D=D+BB P=B4 C=A P=B P+C=BA N: output B.W=2 D=D+BA P=A5 C=B P=A P+C=AB Y: P=P+C=AB 6 C=A P=

26、AB P+C=ABA N: output AB.W=4 D=D+ABA P=A7 C=B P=A P+C=AB Y: P=P+C=AB8 C=A P=AB P+C=ABA Y: P=P+C=ABA9 C=C P=ABA P+C=ABAC N: output ABA.W=7 D=D+ABAC P=Cn译码算法：n 步骤1: 在开始译码时词典包含所有可能的前缀根(Root) n 步骤2: cW := 码字流中的第一个码字 ；n 步骤3: 输出当前缀 符串string.cW到字符流 n 步骤4: 前码字 pW := 当前码字cW n 步骤5: 当前码字 cW := 码字流中的下一个码字 n 步骤6:

27、 判断先前缀 符串string.cW是否在词典中 (1) 如果“是，那么： 把当前缀 符串string.pW输出到字符流。 当前前缀 P := 先前缀 符串string.pW。 当前字符 C := 当前前缀 符串string.cW的第一个字符。 把缀 符串 P+C 添加到词典。 (2) 如果“否，那么： 当前前缀 P :=先前缀 符串string.pW。 当前字符 C :=当前缀 符串string.cW的第一个字符。 输出缀 符串 P+C 到字符流，然后把它添加到词典中。n 步骤7：判断码字流中是否还有码字要译 (1) 如果“是，就返回到步骤4。 (2) 如果“否, 结束。 步骤步骤代码代码词

28、典词典输出输出(1)A(2)B(3)C1(1)-A2(2)(4)ABB3(2)(5)BBB4(4)(6)BAAB5(7)(7)ABAABA6(3)(8)ABACCLzwLzw的译码过程的译码过程1 cW=1 out 1.S=A2 pW=1 cW=2 Y: out 2.S=B P=1.S=A C=2.S=B D=D+AB3 pW=2 cW=2 Y: out 2.S=B P=2.S=B C=2.S=B D=D+BB4 pW=2 cW=4 Y: out 4.S=AB P=2.S=B C=4.S=A D=D+BA5 pW=4 cW=7 N: P=4.S=AB C= A out ABA D=D+ABA6

29、 pW=7 cW=3 Y: out 3.S=C P=7.S=ABA C= C D=D+ABAC五、预测编码n预测编码n根本原理是基于图像中相邻像素之间具有较强的相关性。每个像素可根据的前几个像素来作预测。因此在预测编码中，编码和传输的并不是像素采样值本身，而是这个采样值的预测值与其实际值之间的差值。五、预测编码n分类n线性预测n差分脉冲编码调制DPCMDifferential Pulse Code Modulation典型代表n增量调制DMn自适应增量调制ADMn自适应脉冲编码调制APCMn自适应差分脉冲编码调制ADPCMn非线性预测不讨论DPCMn在PCM系统中，原始的模拟信号经过采样后得到

30、的每一个样值都被量化成为数字信号。n为了压缩数据，可以不对每一样值都进行量化，而是预测下一样值，并量化实际值与预测值之间的差值，这就是DPCMDifferential Pulse Code Modulation，差分脉冲编码调制。DPCM系统原理框图n差分信号是离散输入信号和预测器输出的估算值之差。nDPCM系统是一个负反响系统，采用这种结构可以防止量化误差的积累。nDPCM适用于图像和语音数据n例子： 23 45 48 52 60 76 89 90 95 23 22 3 4 8 16 13 1 5) 1()()(kskskde自适应脉冲编码调制(APCM) n自适应脉冲编码调制(a adap

31、tive p pulse c code m modulation，APCM)是根据输入信号幅度大小来改变量化阶大小的一种波形编码技术。这种自适应可以是瞬时自适应，即量化阶的大小每隔几个样本就改变，也可以是音节自适应，即量化阶的大小在较长时间周期里发生变化。 自适应差分脉冲编码调制(ADPCM) n自适应脉冲编码调制ADPCM根本思想：n利用自适应的思想改变量化阶的大小，即使用小的量化阶(step-size)去编码小的差值，使用大的量化阶去编码大的差值；n使用过去的样本值估算下一个输入样本的预测值，使实际样本值和预测值之间的差值总是最小。 增量调制DM调制n是PCM编码的一种变形。PCM是对每个采样信号的整个幅度进行量化编码，因此它具有对任意波形进行编码的能力；DM是对实际的采样信号与预测的采样信号之差的极性进行编码，将极性变成“0和“1这两种可能的取值之一。如果实际的采样信号与预测的采样信号之差的极性为“正，那么用“1表示；相反那么用“0表示，或者相反。由于DM编码只须用1位对话音信号进行编码，所以DM编码系统又称为“1位系统。增量调制DM调制在输入信号变化快的区域，斜率过载是关心的焦点，而在输入信号变化慢的区域，关心的焦点是粒状噪声。为了尽可能防止出现斜率过载，就要加大量化阶，但这样做又会加大粒状噪声；相反，如果要减小粒状噪声，就要减