[多媒体]04b无损数据压缩.ppt

本章内容 数据压缩的概念 香农-范诺与霍夫曼编码 算术编码 RLE编码 词典编码 行程编码 RLE (Run Length Encoding)编码 现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。 RLE 行程编码：不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值以及具有相同颜色值的行数。 行程长度：具有相同颜色并且是连续的象素数目。 例子 假定一幅灰度图像，第n行的象素值为： 用RLE编码方法得到的代码为： 80315084180。 代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。 例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。 特点 对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用11个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1 这说明RLE确实是一种压缩技术，而且这种编码技术相当直观，也非常经济。 压缩比 RLE所能获得的压缩比有多大，这主要是取决于 图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。 译码 译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。 因此，RLE是无损压缩技术。 缺点 RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。 然而，RLE对颜色丰富的自然图像就显得力不从心，在同一行上具有相同颜色的连续象素往往很少，而连续几行都具有相同颜色值的连续行数就更少。如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。 这并不是说RLE编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中还真少不了RLE，只不过是不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。 适用场景 行程编码多用于黑白二值图像的压缩中。例如0000000011111111111100000111111 8 12 5 6 被转化为一系列黑串和白串长度的编码：8C56 (0x) RLE用于文本压缩 对于文本压缩: RLE的效果不好 例如：JiaoDa-J1i1a1o1D1a1 除非经常遇到 “Ahhhhhhhhhhhhhhhhh!”, “Noooooooooo!”. “Gooooooooooooooooooooooogle” 字典编码 通用编码技术 有许多场合，开始时不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。 词典编码：不需要知道统计特性 词典编码(dictionary encoding)的根据是数据本身包含有重复代码这个特性。 山羊上山，山碰山羊角；水牛下水，水没水牛腰。 第一类词典编码 企图查找正在压缩的字符序列是否在以前输入的数据中出现过。 然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。 例子 吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮 LZ77算法 第一类词典编码里：所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。 这类编码中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年开发和发表的称为LZ77算法为基础的 Jacob Ziv, Abraham Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, 23(3):337-343, May 1977. LZ77算法 LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。 LZ77 首先介绍算法中用到的几个术语： 输入数据流(input stream)：要被压缩的字符序列。 字符(character)：输入数据流中的基本单元。 编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。 前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。 窗口(window)：指包含W个字符的窗口，字符从编码位置开始向后数，也