多媒体数据压缩(第2章)

1、第二章第二章 数据压缩的理论基础数据压缩的理论基础l掌握数据压缩的理论极限掌握数据压缩的理论极限l寻找数据压缩的基本途径寻找数据压缩的基本途径2.12.1数据压缩与信息论数据压缩与信息论 经典的数据压缩技术是建立在信息论的基础上。一个故事：一个故事：据说在欧洲的一个小镇,有一个叫Albert的年轻学者在专利局工作，从事专利审核工作，上班的第一天，上司让他审核这样一份申请：该申请人自称发明了一种装置，能将任意一份计算机存储的计算机的英文文件，以10个字母只需1bit的压缩率存储起来Albert束手无策，请教好友克劳德（通信工程师），他看完专利申请后，告诉Albert，这个专利破坏了信息论中的基本

2、极限，因而不可能实现。Shanon信息论认为，信源所含有的平均信息量就是无失真压缩的理论极限。英文文件由27个字符组成：27英文字母和一个空格，其信源的熵为bit/字符（参考周炯磐信息论基础）4 . 1)(XH2.22.2信源的熵信源的熵 一、信息量与熵1.“1.“消息消息”与与“信息信息” 在人们的日常的生活中，如果收到一封电报，接到一个电话，从信息论的角度来看，只能称之为“消息”（message），而不能到“信息”（information），不过信息存在于消息之中，而且同样一个消息会带有不相等的信息量。 2.2.信息量信息量不同的消息中包含的信息有多有少不同的消息中包含的信息有多有少比如同

3、样收到一封仪器成功的电报。如果原先预计成功的可能性为99%，那么它所带来的信息量是微小的，好象“不出所料”，但是如果预计的可能性不大，比如只有1%的可能，而这时受到成功的电报，就会提供极大的信息量，似乎有“十分意外”的感觉。此时对人们的心理上的鼓励作用，从技术的肯定性，都表明消息所含有的信息量是较多的。显然，用户在收到消息之前，是处于某种不确定状态中，而收到此消息之后，就解除了不确定性，从而获得信息。 山农信息论应用“概率”来描述不确定性，也就是说，事件出现的概率越小，不确定性越多。)(ipH？不确定函数，要满足以下几个基本要求:1）当事件为确定事件时，即 ，则 , 此时毫不确定而言。) 越小

4、，不确定性越大，反之越小。3) 如果两件事件同时存在，则有联合不确定性。且当两事件相互独立时，有： )(ipH1ip0)(ipHip)(),(,kjkjbpapHpH)()(,kjkjbpHapHpH根据以上三条要求，人们成功找到了不确定性的合理表达式：iippHlog)(3. 3. 自信息量自信息量信源:是信息的来源，它一般以符号的形式发出信息，包含信息的符号常常有随机性。信源连续信源：随机变量取值于连续区间离散信源：随机变量取值于离散区间 假设某一离散信源X可能发生各种可用的符号所组成的离散符号集为 ，各种符号出现的概率为自信息量：自信息量：符号出现所携带的自信息量定义为上式中，对数的底不

5、同，取值也不同，单位也不同。取2时， 单位为比特（bit）。取e时，单位为奈特（nat）。取10时，单位为哈特（hart）。ja. 信源的熵信源的熵(entropy)u 信源的熵是对该信源进行无失真编码的极限。u 对信源进行无失真编码的最低码率就是该信源的熵。u 如果对信源进行编码的码率小于信源的熵，则这种编码是有失真的。2) 熵对数据压缩编码的理论意义11( ). ( ).logmmjjjjjjH XP I aPP1)定义：某一信源 中各种可能出现的符号的自信息量的概率平均值，即11.jmjmaaaXppp例题 例：某一信源X有四个符号，其出现概率为： 8/ 18/ 14/ 12/ 1432

6、14aaaaA则该信源的熵为： = 1.75 bit/符号 平均码长: L= =1/2*1+1/4*2+1/8*3= 1.75 bit/符号81log41*241log4121log)21()(xH 1111101004321aaaaiilp3. 性质u 非负性 u 确定性 u 严格上凸性u 极值性 0)(pH(1,0,.,0)(0,1,.,0) .(0,0,.,1)0mmmHHH所有的概率分布所构成的熵，以等概率时最大。最大熵定理 12111(,.,)(,.,)logmmmHp ppHmm mmmax()()log()rHXH XmH X对一个两符号的信源，其熵函数的曲线为1p11(,1)H

7、 pp启示：只要信源不是等概率分布的，就存在无失真数据压缩的可能性。 启示：既然非负，严格上凸，且等概率时达到最大，任一时达到最小值0，那么我们可以通过某中变换 T:，使中某一个符号发生的概率尽可能大（）使其他的尽可能小（），这将有利于压缩，这就是变换编码的途径之一。 )(pHmjp=1mmBA 10,21mmbbbB二、率失真理论率失真理论(Rate-distortion Theory) ,jmaA编码器编码输出集Y,jnbB 信源X有失真压缩编码的理论极限 研究在限定失真下为了恢复信源符号所必需的编码率，简称率失真理论。一、几个重要的定义. 联合概率( ,)ijP a b信源发出 ，编码输

8、出 的概率 iajb. 条件概率()ijaPb()jibQa已知编码输出为 ，估计对应信源发出符号 的概率 jbia已知信源发出符号为 ，估计编码输出为 的概率 jbia. 条件自信量 4. 条件熵 )(log)(jijibaPbaI已知编码输出为时，对猜测信源是否发出的不确定程度。 jbia)(log)(ijijabQabI()( ,). (/)ijjiijYHp a bI baX表示已知编码输入集为X时，编码输出集为Y所剩余的不确定性。 ()( ,). (/)ijijijXHp a bI abY5. 联合熵 (; )( ,)log( ,)ijijijH X Yp a bp a b 表示输入

9、为，输出为时，整个系统所具有的不确定程度. 互信息量 (; )()(/)I X YH XH X Y已知编码输出为Y时，编码输入集为X所剩余的不确定性。X所含有的不确定性。“Y已知后，所获得的关于的信息量”或者说“中所含有的的信息量”(; )()(/)( )log( )( ,).log(/)(/). ( )( )log( )( ). (/).log()iiijijiijjiiiiijiiijjI X YH XH X Yp ap ap a bP abQ bap ap ap ap a Q baQ b 在已知，的情况下，互信息量是条件概率的函数(; )I X YX()H XY( )H Y(/)H X

10、Y( /)H YX(; )I X Y(; )H X YXY()H X( )H Y(/)()H X YH X( /)( )H YXH Y(; )0I X Y (; )H X YX和相互独立时XY()H X( )H Y(/)( /)0H X YH YX(; )()( )I X YH XH Y(; )()( )H X YH XH YX和一一映射时11111010110001101000100087654321: jiba1110010087654321比如 输入和输出一一对应 ,无失真 iiba 输入和输出不是一一对应,有失真,每个符号节省1bit 可见，只要允许误差存在，就可以减少编码输出的字符数

11、，降低码率。输出字符数越少，译码误差失真就越大。问题是：在给定的失真条件下，最起码需要多大的码率，才能保证不超过允许的失真？二、离散信源的率失真函数二、离散信源的率失真函数 1a1b2a2b是对应关系，无失真1a1b2a2b2b1a2a1b有误差),(jibad设 代表某种失真度量1111( )( ,). ( ,)( ). (/). ( ,)mnmnijijijiijijijD Qp a bd a bp a Q bad a b则平均失真若要求平均失真不超过D，即DQD)(则必存在这样概率)(ijabQ)(QD使 不超过D。定义 DQDQQD)(|1.1.失真的度量失真的度量互信息量是的函数(;

12、 )I X Y将率失真函数 定义为在 范围内寻找最起码的平均互信息量。()R DDQ即( )min (; )DQ QR DI X Y. 率失真函数的定义率失真函数的定义率失真函数是在允许失真为D的条件下，信源编码给出的平均互信息量的下界。 有失真时的信源编码的逆定理当编码码率R时，无论用何种编码方式，其平均失真必大于D )(DR)(DR. . 的性质：的性质：)()0(XHR)0(Ru，代表失真为0时的编码。)(DRuD a2 a1 a2 a1 a3 a2例：信源符号概率码A码B码C码D码E码Fa11/2000000a21/40110010110a31/8111110011011101a41/

13、8101111110111111111不可不可不是不是不是3.23.2哈夫曼哈夫曼(Huffman)(Huffman)编码编码 哈夫曼与1952年提出一种编码方法，他完全依据字符出现概率概率来构造品均长度最短的异字头码字。在变长编码中，若各码字长度严格按照所对应符号出现概率的大小逆序排列，则其平均码长最小。实现步骤：实现步骤：将信源符号出现概率按减小的顺序排列；将两个最小的概率进行组合相加，并继续这一步；对每队组合中的上边指定为1，下边指定为0；画出由每个信源符号概率到1、0处的路径，记下路径的1和0；对于每个信源符号，写出1、0序列。则从右到左就得到哈夫曼码。例：信源符号 概率a1 0.20

14、a2 0.19a3 0.18a4 0.17a5 0.15a6 0.10a7 0.01u需要统计概率u需要存储或传输码表哈夫曼编码的缺点：哈夫曼编码的缺点：通常，给出通用码表，省略以上过程3.33.3游程编码（游程编码（Run-Length Coding) )游程长度(RL):由字符(或信号采样值)构成的数据流中各个字符重复出现而形成字符串的长度。如果给出了形成串的字符、串的长度及串的位置，就能换算出原来的数据流。游程长度编码(RLC)就是用二进制码字给出上述信息的一类方法。基本的RLC就是在数据流中直接用三个字符来给出上述三种信息。数据流ajScRL常将游程编码与Huffman编码等结合起来，

15、以进一步去除冗余，提高压缩比。 3.4MH/MR编码 、Modified Huffman (MH)针对二值图像（仅有黑、白两个亮度值的图像，如传真机扫描的二值图像）的压缩方法。 MH码的主要方法是：以多帧标准传真图像样本为统计依据，根据各种RL的出现的概率编出哈夫曼码表，实际过程只是查表，可以实时处理。由于规定每行标准取样1728点，又根据统计结果，实际RL在063居多，故MH编码表分为结尾码与组合基于码。MH码表(一)结尾码RL长度白游程码字黑游程码字00011010100001101111000111010201111131000104101101151100001163001101000

16、00001100111MH码表(二)组合基于码RL长度白游程码字黑游程码字64110110000001111128100100000110010001921728EOL000000000001000000000001编码规则如下：RL=063,用一个相应的结尾码表示；RL=641728，用一个组合基于码加一个补充结尾码，例如RL(白)=128,其编码为10010 00110101 补充结尾码为(白)。若RL(白)=129，则其编码为10010 000111规定每行都从白游程开始，若实际扫描行由黑开始，则需要在行首加零长度的游程；每行结束时，要加行同步码EOL，每页文件第一个数据前加EOL;为了

17、同步操作的需要,规定一个编码的结束时间T最小为20ms，最大为5 s，不是20ms的行需要再EOL之前填充足够的0，不可填在数据中间。每行恢复像素应为1728个，否则认为该行的传输有误。连续发6个EOL码，表示文件传输结束，转回控制规程，以后发送机将按照帧格式的CCITT建议.30规定的控制信号速率发送各种报文后命令。二、二、MRMR编码编码1978年12月，日本提出READ(Relative Element Address Designate)编码方案最后形成标准时，又参照其他国家的提案，对READ进行了修改，即Modified READ，简称MR 1. MR提出的动机MH仅使用了每一扫描行

18、内的相关性， 没有充分利用图象的相关性MR编码是MH编码的扩展，是一种二维逐行编码方式。 把一页文件沿列扫描方向分成若干组，每组有K行图像数据; 第一行用一维MH编码，其余K-1行则利用行间相关性对当前像素模式识别后编码。MR编码方法1)1) 迁移像素迁移像素沿扫描行由黑变白或由白变黑的的第一像素 参考行：编码行：.a0a1a2b1b2a0：在编码行上起参考作用的一个迁移像素。在编码行的开始，a0为假想的白像素，位于该行第一个实际像素之前，在编码过程中，由前一次编码来确定。a1：在参考行上位于a0之后的下一个迁移像素。a2：在参考行上位于a1之后的下一个迁移像素。b1：在参考行上位于a0右边，

19、且与a0颜色相反的第一个迁移像素。b2：在参考行上位于b1之后的下一个迁移像素。2 2）编码的模式）编码的模式READ方案将扫描行的各种变化归纳为三种格式，MRC就是识别编码行上的每一个迁移像素应属于哪一个模式，并输出相应的码字，从而编码简化，压缩比提高。特征特征:a1位于b2右边的一种模式； 编码方法编码方法:在通过模情况下，无论a0、b2多长，只用一个码字“0001”表示其长度。 此后开始下一个模式编码，以b2正下方的像素 作为下一个编码模式的参考模式a0。 u 通过模通过模( (用用P P表示表示) ) 参考行：编码行：.a0a1b1b2a00au垂直模（用垂直模（用V V表示）表示）

20、参考行：编码行：.a0a1a2b1b2特征特征:a1位于b2左边，且 的一种模式1 13ab 以a1作为下一个编码模式的a0编码方法编码方法:按下表的码字对 的长度编码。1 1ab模模需编码的像素需编码的像素符号符号码字码字通过a0 b2p0001水平a0 a1 a1a2H001+M(a0 a1 )+ M(a1a2 )垂直a1正好在b1之下a1b1=0V(0)1a1在b1右面a1b1=1VR(1)011a1b1=2VR(2)000011a1b1=3VR(3)0000011a1在b1左面a1b1=1VL(1)010a1b1=2VL(2)000010a1b1=3VL(3)0000010MRMR码表

21、码表u 水平模水平模( (用用H H表示表示) ) 特征特征:a1位于b2左边且a1b13的一种模式。 编码方法编码方法:统计表明，对a1b1编码还不如直接对a0 a1 和a1 a2两个游程长度编码的效率高。 编码之后，a2作为下一次编码时的a0 程序演示程序演示3.5 3.5 算术编码算术编码(Arithmetic Coding)(Arithmetic Coding) 1.1.引言引言 早在60年代初期，Elias就提出了算术编码的概念，Rissanen和Pasco首次介绍了他的实用技术。算术编码方法的具体实现方法，在80年代才有了报道。到目前为止，这一方法还不为很多人知道。近期出版了数据编

22、码的书，也仅仅简单提及。算术编码在有些方面优于Huffman方法，算术编码方法使表示的信息尽量紧凑，并对输入的数据信息没有分块的要求，算术编码方法计算效率高并且容易提供自适应模式。2.2.算术编码原理算术编码原理算术编码就是将被编码的信息表示成实数0和1之间的一个间隔，信息越大，编码表示它的间隔就越小，表示这一间隔所需要的二进制位就越多。 例：假定信源中可能出现的符号有a, e, I, o, u, l，出现的概率如下，用算术编码对输入串eaiil编码2 . 0 , 0字符 概率 范围（range） rangelow ,rangehigh) a 0.2e 0.3 5 . 0 , 2 . 0i 0

23、.1 6 . 0 , 5 . 0o 0.2 8 . 0 , 6 . 0u 0.1 9 . 0 , 8 . 0l 0.1 1 , 9 . 001aeioul定义：range(n)=high(n)-low(n) 。下一次low(n+1) = low(n) + range(n) * rangelow high(n+1) = low(n) + range(n) * rangehig初始 high(0) =1，low(0) =0。low = 0 + 1 * 0.2=0.2high = 0 + 1* 0.5=0.5range=high low =0.5-0.2=0.3e 编码过程a low = 0.2 +

24、 0.3 * 0=0.2high = 0.2 + 0.3* 0.2=0.26range=high low =0.26-0.2=0.061 1）编码过程）编码过程编码字符区间范围lowhigh初始01)e0.20.5)a0.20.26)i0.230.26)i0.2330.2336)l0.233540.2336)euoieaeuoieaeuoieaeuoieaeuoieaeuoiea0.20.50.20.260.230.260.2330.2360.233540.2336）解码过程）解码过程只要将编码后的最后范围以二进制形式存储即可。从而达到压缩l如果解码器也知道这一最后的范围2336. 0 ,23

25、354. 0马上就可以解出第一个字符e,只有e产生的范围能包含2336. 0 ,23354. 0l在解出e后，范围变成5 . 0 , 2 . 0l得到这个范围，我们就可以对上述所有字符再依据上式计算，并与最终范围比较，不难解出第二个字符为a。 l依次类推 算术编码除了有基于概率统计的固定模式外，还有其他模式。 自适应模式各个符号的概率初始值都相同，它们依据出现的符号而相应地改变。只要编解码器使用相同的初始值和改变值的规则，则它们的概率模型将保持一致。 ）算术编码的特点：）算术编码的特点：l算术编码的方法不必预先统计概率；l当信源概率比较接近时，Huffman编码的效率不高，算术编码要好于Huf

26、fman。l算术编码的实现方法要比Huffman方法复杂一些.6 LZ .6 LZ 编码（基于编码（基于字典字典的无失真编码方法）的无失真编码方法）一、基本定义一、基本定义：基于字典的编码方法基于字典的编码方法是由生活中的字典概念而引申的。例：A good example of how dictionary based compression 采用简明硬汉词典（共有2200页，每页单词少于256），对上述8个词编码如下：1/1 811/3 674/4 1343/60 928/75 550/32 173/46 421/2页号该页单词的序号分析：未编码时：43 Bytes编码时：页码：12 bit

27、s, 词条序号8 bits，对一个词的编码共需2.5 Bytes这段话共需8 2.520Bytes静态字典：字典是不变的，编码简单，效率较低动态字典：字典随编码过程而变，编码复杂，效率较高字典二、分类二、分类Ziv和Lempel(两位以色列人）在1977和1978年在IEEE Transactions on Information Theory 发表的两篇论文A universal algorithm for sequential data compression77787878787878LZSSLZLZWLZSLZELZLZSELZEPLZSEPLZY目前许多计算机的压缩软件，如Winzip，Arj等均基于LZ算法三、实现方