多媒体技术-图像与视频压缩(1)资料

1、 第七章 图像(t xin)与视频压缩（1）共八十页第七章 图像(t xin)与视频压缩1 通用(tngyng)数据压缩2 多媒体数据压缩共八十页1 通用(tngyng)数据压缩1.1 数据压缩概述1.2 数据压缩主要(zhyo)方法游程编码统计编码字典编码共八十页数据压缩(sh j y su)-定义 “数据压缩(sh j y su)”在汉英词典中的解释： data compression (A method of reducing the amount of memory required to store data by encoding it and minimizing redunda

2、ncy. Compressed data takes less time to transmit, but more computation time to restore it to its original form when needed for processing.)共八十页数据压缩(sh j y su)-作用 通俗地说，就是用最少的数码来表示信号。其作用是：能较快地传输各种信号，如传真、Modem通信等；在现有的通信干线并行开通更多的多媒体业务，如各种增值业务；紧缩数据(shj)存储容量，如CDROM、VCD和DVD等；降低发信机功率，这对于多媒体移动通信系统尤为重要。由此看来，通

3、信时间、传输带宽、存储空间甚至发射能量，都可能成为数据压缩的目的。 共八十页数据压缩(sh j y su)-概要 在计算机科学和信息论中，数据压缩或者信源编码(bin m)是按照特定的编码(bin m)机制用比未经编码(bin m)少的数据位元（或者其它信息相关的单位）表示信息的过程。例如，如果我们将“compression”编码为“comp”那么这篇文章可以用较少的数据位表示。一种流行的压缩实例是许多计算机都在使用的ZIP 文件格式，它不仅仅提供了压缩的功能，而且还作为归档工具Archive使用，能够将许多文件存储到同一个文件中。共八十页数据压缩(sh j y su)-概要 对于任何形式的通

4、信来说，只有当信息的发送方和接受方都能够理解编码机制的时候压缩数据通信才能够工作。例如，只有当接受方知道这篇文章需要用英语(yn y)字符解释的时候这篇文章才有意义。同样，只有当接受方知道编码方法的时候他才能够理解压缩数据。一些压缩算法利用了这个特性，在压缩过程中对数据进行加密，例如利用密码加密，以保证只有得到授权的一方才能正确地得到数据。共八十页数据压缩(sh j y su)-概要 数据压缩能够实现是因为多数现实世界的数据都有各种冗余。例如，字母“e”在英语中比字母“z”更加常用，字母“q”后面是“z”的可能性非常小。无损压缩算法(sun f)通常利用利用了统计冗余，这样就能更加简练地、但仍

5、然是完整地表示发送方的数据。 如果允许一定程度的保真度损失，那么还可以实现进一步的压缩。例如，人们看图画或者电视画面的时候可能并不会注意到一些细节并不完善。同样，两个音频录音采样序列可能听起来一样，但实际上并不完全一样。有损压缩算法在带来微小差别的情况下使用较少的位数表示图像、视频或者音频。共八十页数据压缩(sh j y su)-概要 由于可以帮助减少如硬盘空间与连接带宽这样的昂贵资源的消耗，所以压缩非常重要，然而压缩需要消耗信息处理资源，这也可能是费用昂贵的。所以数据压缩机制的设计需要在压缩能力、失真度、所需计算资源以及(yj)其它需要考虑的不同因素之间进行折衷。共八十页数据压缩(sh j

6、y su)-应用 一种非常简单的压缩方法是行程长度编码，这种方法使用数据及数据长度这样简单的编码代替同样的连续数据，这是无损数据压缩的一个实例。这种方法经常(jngchng)用于办公计算机以更好地利用磁盘空间、或者更好地利用计算机网络中的带宽。对于电子表格、文本、可执行文件等这样的符号数据来说，无损是一个非常关键的要求，因为除了一些有限的情况，大多数情况下即使是一个数据位的变化都是无法接受的。共八十页数据压缩(sh j y su)-应用 对于视频和音频数据，只要不损失数据的重要部分一定程度的质量下降是可以接受的。通过利用人类感知系统的局限，能够大幅度得节约存储空间并且得到的结果质量与原始数据质

7、量相比并没有明显的差别。这些有损数据压缩方法通常需要在压缩速度、压缩数据大小以及质量损失三者之间进行折衷。 有损图像压缩用于数码相机(sh m xin j)中，大幅度地提高了存储能力，同时图像质量几乎没有降低。用于DVD的有损MPEG-2编解码视频压缩也实现了类似的功能。共八十页数据压缩(sh j y su)-应用 在有损音频压缩中，心理声学的方法用来去除信号中听不见或者很难听见的成分。人类语音的压缩经常使用更加专业的技术，因此人们有时也将“语音压缩”或者“语音编码”作为一个独立的研究领域(ln y)与“音频压缩”区分开来。不同的音频和语音压缩标准都属于音频编解码范畴。例如语音压缩用于因特网电

8、话，而音频压缩被用于CD翻录并且使用 MP3 播放器解码。共八十页数据压缩(sh j y su)-理论 压缩的理论基础是信息论（它与算法信息论密切相关）以及率失真理论，这个领域的研究(ynji)工作主要是由 Claude Shannon 奠定的，他在二十世纪四十年代末期及五十年代早期发表了这方面的基础性的论文。 Doyle 和 Carlson 在2000年写道数据压缩“是所有的工程领域最简单、最优美的设计理论之一”。密码学与编码理论也是密切相关的学科，数据压缩的思想与统计推断也有很深的渊源。共八十页数据压缩(sh j y su)-理论 许多无损数据压缩系统都可以看作是四步模型，有损数据压缩系统

9、通常包含更多的步骤，例如它包括预测、频率(pnl)变换以及量化。 Lempel-Ziv（LZ）压缩方法是最流行的无损存储算法之一。DEFLATE是 LZ 的一个变体，它针对解压速度与压缩率进行了优化，虽然它的压缩速度可能非常缓慢，PKZIP、gzip 以及 PNG 都在使用EFLATE。LZW （Lempel-Ziv-Welch）是 Unisys 的专利，直到2003年6月专利到期限，这种方法用于 GIF 图像。 共八十页数据压缩(sh j y su)-理论 最好的压缩工具将概率模型预测结果用于算术编码。算术编码由 Jorma Rissanen 发明，并且由 Witten、Neal 以及(yj

10、) Cleary 将它转变成一个实用的方法。这种方法能够实现比众人皆知的哈夫曼算法更好的压缩，并且它本身非常适合于自适应数据压缩，自适应数据压缩的预测与上下文密切相关。算术编码已经用于二值图像压缩标准 JBIG、文档压缩标准 DejaVu。文本 输入系统 Dasher 是一个逆算术编码器。共八十页1 通用(tngyng)数据压缩1.1 数据压缩概述(i sh)1.2 数据压缩主要方法游程编码统计编码字典编码共八十页游程(yu chn)编码（RLE）思想：如果数据项d在输入流中出现n次，则以单个字符对nd替换n次出现者。这个连续出现的数据项叫做游程n，这种数据压缩方法称为(chn wi)游程编码

11、或RLERLE文本压缩RLE图像压缩共八十页RLE文本(wnbn)压缩 2. all is too well 2. a2l is t2o we2l一个解决方法就是在重复部分前缀一个特殊的提示字符(z f)，我们用作提示，则字符串被替换成: 2. a2l is t2o we2l共八十页 RLE 文本压缩的步骤 读入第一个字符后，计数值为1，保存(bocn)该字符。将后续字符与已保存(bocn)者相比较，相同则重复计数器加1。如果读入一个不同字符，则操作取决于重复次数：如果次数很小，把已保存的字符写入压缩文件，保存新读入的字符；否则先写一个，在输出重复次数及被保存的字符。下图是游程文本压缩器的流程

12、图共八十页 共八十页 RLE 文本解压的步骤：一旦读入一个(y )，则立即读入重复次数及实际字符，并在输出流中重复写该字符n次。共八十页 共八十页 RLE 方法(fngf)存在的问题普通英文中并没有多少重复。有许多双写，但是很少有3次重复的。 在输入流中，字符可能(knng)是文本的一部分，此时必须选一个不同的提示字符。由于重复计数值以字节形式写在输出流中，只能计到255。共八十页 RLE的压缩比 假设待压缩字符长度为N，字符中包含M次重复，每次重复的平均长度为L。M次中的每一次重复可用3字节(z ji)代替，因此，压缩后字符串的长度为N-M(L-3)，压缩因子为 N/(N-M(L-3)如果N

13、=1000,M=10,L=4,则压缩因子1.01， 如果N=1000,M=50,L=10 压缩因子1.538共八十页RLE图像压缩二值图像灰度图像彩色图像 RLE图像压缩基于这样的事实：如果我们在该图像中随机(su j)选择一个像素，其相邻像素色彩相同的可能性很大，因此压缩器逐行扫描位图，搜索色彩相同之像素的游程。共八十页二值图像(t xin)假设图像(t xin)从黑像素或白像素开始，按行扫描位图，给出黑白像素的游程。例如：开始17个白像素，其后跟随一个黑像素，再跟55个白像素等，则把17，1，55，写入压缩流。共八十页灰度图像(t xin)12,12,12,12,12,12,12,12,1

14、2,35,76,112,67,87,87,87,5,5,5,5,5,5,1, 被压缩为9，12，35，76，112，67，3，87，6，5，1，我们要区分是含灰度值的字节和含计数值的字节，解决(jiju)方法如下：共八十页区分(qfn)灰度值和游程的方法如果图像限制为只有128级灰度，我们可以用每个字节中的一位来表示该字节所含的是灰度值还是计数值。如果灰度级为256，则可降为255，保留一个值作标志，至于(zhy)每个游程计数字节之前。每字节均加一位，以表示该字节所含是灰度值还是计数值。此时这些附加位每8个累计为一组，每组先于其所属的8个字节写到输出流中共八十页彩色图像对于(duy)彩色图像，

15、通常将每像素存为3个字节，代表其红、绿、蓝3基色的强度，因此把像素分成3个序列，每一序列分别游程编码。（171,85,34）、(172,85,35)、(172,85,30)、(173,85,33)共八十页各行单独(dnd)编码的原因有时用户只查看图像的一般形状不需要细节，各行单独编码可以各行解码。逐步(zhb)重建可以只抽取图像的一部分合并两幅图像不必先解码共八十页1 通用(tngyng)数据压缩1.1 数据压缩概述(i sh)1.2 数据压缩主要方法游程编码统计编码字典编码共八十页统计(tngj)编码香农-费诺编码(bin m)哈夫曼编码算术编码共八十页香农-费诺编码(bin m)信息的度量

16、变长码特性(txng)香农费诺编码共八十页信息(xnx)的度量给定一个k位十进制数和一个k位二进制数，一个很自然的问题是，这两个k数位(shwi)包含了多少信息？这可以通过计算它们为表示同一个数而各自所需的位数来回答。 共八十页给定一个n进制数，有 ，即1位n进制数所含的信息相当于 位二进制数包含的信息。如果(rgu)发射机传送一个符号需要1/s单位时间，则其传送速率是每单位时间s个符号。在一个单位时间内发射机可以发出s个符号，包含的信息量是 位。我们用 表示信息量，单位为位数/单位时间。信息(xnx)的度量共八十页假设 在数据(shj)中出现的概率是 ，自然有 在 的等概率特例下，由 可推出

17、： 假定数据是由 到 所生成的字符串，这样一个集合就是(jish)一个有n个符号的字母表。信息的度量共八十页 在数据中出现的概率是 ，那么它在单位时间内平均(pngjn)出现了 次，因此它对H的贡献是那么n个符号对H的贡献之和是： 这里H表示信息量，是单位时间传送的符号位数。所以一个n进制符号所含有(hn yu)的信息量就是H/S（因其需要1/s时间传送一个符号）或 ，称为被传送数据的熵（entropy）信息的度量共八十页变长码 符号 概率(gil) 编码1 编码2 0.49 1 1 0.25 01 01 0.25 010 000 0.01 001 001共八十页因而遵循以下两条规则(guz)

18、就可以设计变长码：（1）把短码赋给出现频率高的字符；（2）遵循前缀性。共八十页香农费诺编码(bin m)按概率把符号从大到小排序将这些符号划分成概率几乎相同的两个子集一个(y )子集以开始，另一个(y )以开始在按照同样的步骤划分这两个子集，一直到子集不能被划分共八十页香农-费诺编码(bin m) 概率(gil) 步骤 码字 1. 0.25 1 1 :11 2. 0.20 1 0 :10 3. 0.15 0 1 1 :011 4. 0.15 0 1 0 :010 5. 0.10 0 0 1 :001 6. 0.10 0 0 0 1 :0001 7. 0.05 0 0 0 0 :0000共八十页

19、练习(linx)首先从第3个和第4个符号中间(zhngjin)划分子集，计算平均码长？共八十页统计(tngj)编码香农-费诺编码(bin m)哈夫曼编码算术编码共八十页哈夫曼编码(Huffman Coding)是可变长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个(y )符号）进行编码。这张编码表的特殊之处在于，它是根据每一个(y )源字符出

20、现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。 哈夫曼（Huffman）码共八十页 例如，在英文中e出现概率很高，而z出现概率则最低。 当利用(lyng)哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。 二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 哈

21、夫曼（Huffman）码共八十页 哈夫曼压缩是个无损的压缩算法，一般用来压缩文本(wnbn)和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本(wnbn)文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 哈夫曼（Huffman）码共八十页一、二进制哈夫曼编码1.步骤(bzhu)(1) 信源符号按概率分布大小，以递减次序排列； (2) 取两个最小的概率，分别赋以“0”,“1”;然后把这两个概率值相加，作为新概率值与其他概率重新排序(3) 按重排概率值，重复(2), 直到概率和达到1为止(4)

22、 由后向前排列码序，即得哈夫曼编码哈夫曼（Huffman）码共八十页2. 例题 x1 0.4 x2 0.2 x3 0.2 x4 0.1 x5 0.1平均(pngjn)码长码方差12=E(li-L)2=p(xi) (li-L)2 = 1.36 0.20.40.61.001010101X:p(x)(0.4,0.2,0.2,0.1,0.1)（合并(hbng)后概率下放）哈夫曼（Huffman）码01100000100011共八十页方法一：合并后的新符号排在其它相同概率(gil)符号的后面；哈夫曼（Huffman）码共八十页 3. 上例00 x1 0.4 10 x2 0.211 x3 0.2010 x

23、4 0.1011 x5 0.1010.20.40.61.0010101（合并(hbng)后概率上放）哈夫曼（Huffman）码共八十页 3. 上例00 x1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1 平均码长 码方差22 = 0.16 两法平均码长相同(xin tn)，故信息率R、冗余度相同；但码方差不同，码方差小要好.010.20.40.61.0010101（合并(hbng)后概率上放）哈夫曼（Huffman）码共八十页方法二：合并后的新符号排在其它相同(xin tn)概率符号的前面.哈夫曼（Huffman）码共八十页两种编码的平均码长是一样的，都

24、是2.2，那一种更好呢，我们可以(ky)计算一下平均码长的方差。定义(dngy)码字长度的方差2：哈夫曼（Huffman）码共八十页可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；显然，第二种编码方法更简单、更容易实现，所以更好。结论：在哈夫曼编码过程中，对缩减(sujin)信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。哈夫曼（Huffman）码共八十页 3. 上例00 x

25、1 0.4 10 x2 0.211 x3 0.2010 x4 0.1011 x5 0.1 平均码长 结论 码方差22 = 0.16 两法平均码长相同(xin tn)，故信息率R、冗余度相同；但码方差不同，码方差小要好.010.20.40.61.0010101（合并(hbng)后概率上放）哈夫曼（Huffman）码共八十页定理：在变长编码中，若各码字长度严格按照所对应符号出现概率的大小逆序排列，则其平均(pngjn)长度为最小。结论：哈夫曼编码方法，它完全依据字符出现概率来构造平均长度最短的异字头码字，有时称之为最佳编码。 哈夫曼（Huffman）码共八十页 应该指出的是，由霍夫曼编码(bin

26、m)过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码(bin m)效率与数据压缩性能。 此外，由于码长不等，还存在一个输入与输出的速率匹配问题。解决的办法是设置一定容量的缓冲寄存器。 而随着微电子与计算技术的发展，霍夫曼编码已可做成单片IC，并成为许多国际标准中的主要技术内核之一。能够用较低的处理代价，来换取昂贵的通信开销，是完全值得的。哈夫曼（Huffman）码方差(fn ch)最小者最佳共八十页0.60010.090.130.190.230.371.00101010101010100 x5 0.070101 x6 0.0600010 x7 0.0500011 x8 0.040

27、11 x3 0.10000 x4 0.1001 x2 0.18 1 x1 0.4010010110101010000000001000011哈夫曼（Huffman）码4.例题(lt)X:p(x)(0.4,0.18,0.1,0.1,0.07, 0.06,0.05,0.04)共八十页二、D进制哈夫曼编码1. 编码步骤同二进制，但需注意两点：每次取最小的D个概率,分别赋以0,1, D-1；信源符号(fho)个数r必须满足：r=(D-1)+D. 当r不满足时，在信源符号集中补充一些对应概率为0的符号.哈夫曼（Huffman）码共八十页 2.例题(lt)某离散无记忆信源符号集a1,a2,a3,a4,a5

28、,a6,a7,a8，a9，已知所对应的概率，试对其进行四元(s yun)编码！ 哈夫曼（Huffman）码解：其中D=4. 若取=2可得大于9但与9最接近的正整数10，因此在编码时加入一个零概率符号.对其进行四元编码： 共八十页 哈夫曼（Huffman）码共八十页哈夫曼码考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短(sudun)，从而实现了对信源的压缩；哈夫曼码的编码方法都不惟一；哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，因此综合性较优.哈夫曼（Huffman）码共八十页Huffman码在具体实用时，设备较复杂.在编码器中需要增加缓冲寄存器，因为每

29、个信源符号所对应的码符号长度不一，负责会造成输入和输出不能保持平衡.优点：提高编码效率；缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定(hngdng)的码率进行传送；在传输的过程中如果出现了误码，容易引起错误扩散，所以要求有优质的信道。哈夫曼（Huffman）码共八十页哈夫曼码也是译码的工具(gngj)：哈夫曼（Huffman）码共八十页0.60010.090.130.190.230.371.00101010101010100 x5 0.070101 x6 0.0600010 x7 0.0500011 x8 0.04011 x3 0.10000 x4 0.1001 x2 0.18 1 x

30、1 0.40哈夫曼（Huffman）码4.例题(lt)X:p(x)(0.4,0.18,0.1,0.1,0.07, 0.06,0.05,0.04)共八十页10010110101010000000001000011哈夫曼（Huffman）码4.例题(lt) X:p(x)(0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04)若接收(jishu)的字符串是：00010100101100011000101001011000110001010010110001100010100101100011共八十页统计(tngj)编码香农-费诺编码(bin m)哈夫曼编码算术编码共八十页算术(s

31、unsh)编码算法思想Huffman编码中每个符号都用整数个bits来表示，影响编码效率。若能把一串符号作为编码单位，则效率还可提高。符号串的区间(q jin)表示法设符号串为：bacedbbdea 则它可以映射成为0，1）中的唯一的一个子区间。共八十页00.20.50.60.81abcdeabcdeabcdeabcde0.2b 0.5a 0.260.2360.20.23字符abcde概率0.20.30.10.20.2范围0,0.2)0.2,0.5)0.5,0.6)0.6,0.8)0.8,1.0)共八十页high为编码区间的高端,low为低端,range为区间长度, lowrange为字符(z

32、 f)分配区间的低端 highrange 为区间的高端。初始化： high=1,low=0,range=high-low=1 一个字符编码后新的low和high为：Low=low+range* lowrangeHigh=low+range* highrange0子区间1lowhighrangelowrangehigh共八十页计算过程： 1）将 0，1）区间按照概率的比例(bl)分配给五个字符，即（如图形表示）： a= 0，0.2， b= 0.2，0.5, c= 0.5，0.6 d= 0.6，0.8 e= 0.8，1)high=1,low=0,range=high-low=1 2)输入第一个字符

33、 b，得b.high=0.5,b.low=0.2b.range=b.high-b.low=0.3 3)将 0.2，0.5）区间按照概率的比例分配给五个字符，如图形表示。共八十页 4)输入第二个字符 a，得a.high=0.26,a.low=0.2a.range=a.high-a.low=0.06 5)将 0.2，0.26）区间按照概率的比例分配给五个字符，如图形表示。 6)输入第三个字符 c，得c.high=0.236,c.low=0.23c.range=c.high-c.low=0.006依次重复输入后续字符，重复执行5)-6）步,直到输入最后一个字符。在最后这个区间内选择ENDc.low

34、, 将它变成二进制 ，去掉前面的 0 和小数点，我们可以(ky)输出二进制数这就是被压缩后的结果。共八十页 编码过程首先定义Low和High两个变量，并设置 Low0 High1当读入和处理字符时，Low和High按照如下方式更新 NewHigh：OldLow+RangeHighRange（X）; NewLow：OldLow+RangeLowRange（X）；其中RangeOldHighOldLow， LowRange（X）和HighRange（X）表示符号(fho)X所对应区间的下限和上限。共八十页 例：给出对短串“SWISS MISS”的压缩步骤。 字符 频率(pnl) 概率 范围 累计频

35、率(pnl) Total CumFreq 10 S 5 5/10=0.5 0.5,1.0) 5 W 1 0.1 0.4,0.5) 4 I 2 0.2 0.2,0.4) 2 M 1 0.1 0.1,0.2) 1 1 0.1 0.0,0.1) 0 概率和频率表共八十页 算法编码过程(guchng) 字符 Low和High的计算 S L 0.0+(1-0.0) 0.5=0.5 H 0.0+(1-0.0) 1.0=1.0 W L 0.5+(1.0-0.5) 0.4=0.7 H 0.5+(1.0-0.5) 0.5=0.75 I L 0.7+(0.75-0.70) 0.2=0.71 H 0.7+(0.75

36、-0.70) 0.4=0.72 S L 0.71+(0.72-0.71) 0.5=0.715 H 0.71+(0.72-0.71) 1.0=0.72共八十页 S L 0.715+(0.72-0.715) 0.5=0.7175 H 0.715+(0.72-0.715) 1.0=0.72 L 0.7175+(0.72-0.7175) 0.0=0.7175 H 0.7175+(0.72-0.7175) 0.1=0.71775 M L 0.7175+(0.71775-0.7175) 0.1=0.717525 H 0.7175+(0.71775-0.0.7175) 0.2=0.71755 I L 0.717525+(0.71755-0.717525) 0.2=0.717530 H 0.717525+(0.71755-0.717525) 0.4=0.717535 S L0.717530+(0.717535-0.717530) 0.5=0.7