《计算机科学概论(第12版)》—第1章1.9节数据压缩-阿里云开发者社区

开发者社区> 人工智能> 正文

《计算机科学概论(第12版)》—第1章1.9节数据压缩

简介:

本节书摘来自异步社区《计算机科学概论(第12版)》一书中的第1章1.9节数据压缩,作者【美】J. 格伦•布鲁克希尔(J. Glenn Brookshear) , 丹尼斯•布里罗(Dennis Brylow),更多章节内容可以访问云栖社区“异步社区”公众号查看。

*1.9 数据压缩
为了存储或传输数据,在保留原有内容的同时,缩小所涉及数据的大小是有益的(有时也是必须的)。用于完成这一过程的技术称为数据压缩(data compression)。本节,我们首先要学习一些普通的数据压缩方法,然后要了解一些为特殊应用设计的方法。

1.9.1 通用的数据压缩技术
数据压缩方案有两类,一类是无损的(lossless),另一类是有损的(lossy)。无损方案在压缩过程中是不丢失信息的,有损方案在压缩过程中会丢失信息。通常有损技术比无损技术更能压缩,因此在可以容忍小错误的应用中很流行,如图像和音频压缩。

对于被压缩数据由一长串相同的数值组成的情况,普遍使用称为行程长度编码(run-length encoding)的压缩技术,这是一种无损方法。它的过程是,将一组相同的数据成分替换成一个编码,指出重复的成分以及其在序列中出现的次数。例如,指出一个位模式包括253个1,接着118个0,接着87个1,这样要比实际列出458个位节省空间。

另外一种无损数据压缩技术是频率相关编码(frequency-dependent encoding),在这个系统里,用于表示数据项的位模式的长度与这个项的使用频率是反相关的。这种编码是变长编码的例子,意思是项由不同长度的模式表示。戴维·赫夫曼的功劳是发现了一般用于开发频率相关编码的算法,人们一般称用这种方法开发的编码为赫夫曼编码(Huffman code)。因此,现在使用的大多数频率相关编码都是赫夫曼编码。

让我们看一个频率相关编码的例子,考虑一下编码英文文本的任务。在英文中,字母e、t、a和i的使用频率要大于字母z、q和x。因此,当为英文文本编码时,如果用短位模式表示前面的字母,用长位模式表示后面的字母,那么就能节省空间。结果得到的编码中,英文文本的表示长度要比用统一长度编码时的短。

在某些情况下,压缩的数据流由各个数据单元组成,每一个数据单元与其前面一个差别很小。动画的连续帧就是一个例子。这时,使用相对编码(relative encoding)——也称为差分编码(differential encoding)——技术是很有用的。这些技术记录下了两个连续数据单元之间的区别,而不是全部单元;也就是说,每个单元是根据其与前一个单元的关系被编码的。相对编码用无损形式或有损形式都可以实现,具体取决于两个连续数据单元之间的差别是精确编码还是近似编码。

还有其他流行的基于字典编码(dictionary encoding)技术的压缩系统,这里的术语字典(dictionary)指的是一组构造块,压缩的信息通过它们建造起来,而信息本身被编码成字典的一系列参照符。我们一般认为字典编码系统是无损系统,不过在学习图像压缩时我们将看到,有时候字典条目仅仅是正确数据成分的近似值,这就使其成了有损压缩系统。

字处理程序可以使用字典编码来压缩文本文档,因为这些字处理程序中已经包含了用于拼写检查的字典,而这些字典都是出色的压缩字典。特别值得一提的是,一个完整的单词可以编码成字典的一个单独参照符,而不是像使用UTF-8系统那样编码成一系列单独的字符。在字处理程序中,一个典型的字典大约有25 000个条目,这就意味着,单个的字典条目可以用0到24999范围内的整数来标识。也就是说,字典中的一个特定条目用15位的模式就足可标识。相反,如果用到的单词包括6个字母,则它的逐字符编码在使用UTF-8时需要48位。

字典编码的一个变体是自适应字典编码(adaptive dictionary encoding,也称动态字典编码)。在自适应字典编码系统中,字典在编码过程中是可以改变的。一个流行的例子是LZW编码(Lempel-Ziv-Welsh encoding),这个编码的名称是根据它的创造者Abraham Lempel、Jacob Ziv和Terry Welsh的姓氏命名的。要用LZW对信息编码,首先要从包含基础构造块的字典开始,用字典中的构造块来构造信息。但是,当人们在信息中发现更大的单元时,会把它们加到字典上——这意味着,这些单元在未来出现时可以被编码为一个(而不是多个)字典参照符。例如,当对英文文本编码时,人们首先要从包含单独字符、数字和标点符号的字典开始。但是,当信息中的单词被标识后,会被加到字典中。因此,随着信息的不断编码,字典会不断增大,而随着字典的不断增大,信息中会有更多的单词(或者重复的单词模式)被编码为单个的字典参照符。

结果是,信息用一部相当大的、完全针对本信息的字典进行编码。但是在对这条信息进行解码时,不必用这个大字典,只需要用原始的小字典即可。事实上,解码过程可以与编码过程用同一个小字典。接着,随着解码进程的继续,会遇到编码过程中发现的相同单元,因此可以将它们加到字典中,作为未来编码过程的参照符。

举例说明,考虑对下列信息应用LZW编码:

xyx xyx xyx xyx

首先从一个只有3个条目的字典开始,第1个条目是x,第2个条目是y,第3个条目是空格。我们先将xyx编码为121,意思是这个信息的第一个模式依次包括第一个字典条目、第二个字典条目、第一个字典条目。接着,空格被编码产生结果1213。但是因为有了一个空格,我们知道前面的字符串已经形成了一个单词,所以我们将模式xyx加到字典里作为第4个条目。继续使用这种编码方式,整个信息将被编码为121343434。

如果我们现在从原始的3条目字典开始对这条信息进行解码,那么我们首先要将起始的1213串解码为xyx加1个空格。这时我们意识到xyx串形成了一个单词,因此将其加到字典中作为第4个条目,同编码过程中所做的一样。我们接着对这个信息解码,发现信息中的4指的是这第4个新条目,将其解码为单词xyx,因此产生模式:

xyx xyx

继续使用这种解码方式,我们最终把121343434串解码为:

xyx xyx xyx xyx

这就是原始信息。

1.9.2 图像压缩
在1.4节中,我们已经看到如何用位图技术对图像编码。不过,得到的位图通常是非常大的。因此,人们专门为图像表示开发出了许多压缩方案。

一种称为GIF(是graphic interchange format的缩写,即图像交换格式,一些人将其读作“Giff”,还有一些人将其读作“Jiff”)的系统是一个字典编码系统,由CompuServe公司研制开发。它处理压缩问题的方法是,将赋予一个像素的颜色数量减少到只有256个。每一种颜色的“红—绿—蓝”组合都用3个字节编码,这256个编码被存储在一个称为调色板的表格(一个字典)里。图像中的每个像素都可以用一个字节表示,该字节的值指出了这个像素的颜色是由256个调色板条目中的哪一个表示的。(回顾:一个字节能够包括256个不同位模式中的任意一个。)需要注意的是,在将GIF应用于任意图像时,它是一个有损压缩系统,因为调色板中的颜色可能与原始图像中的颜色不一致。

通过使用LZW技术将这个简单的字典系统扩展为自适应字典系统,GIF可以进一步压缩。尤其是,编码过程中遇到的像素模式可以被加到字典中,使得这些模式在将来出现时可以被更加高效地编码。因此,最终的字典是由原始调色板和一组像素模式构成的。

GIF调色板中的某一个颜色通常会被赋予值“透明”,意思是背景色可以透过每一个被赋予该“颜色”的区域表现出来。这个选择,与GIF系统的相对简便性相结合,使得GIF成为简单动画应用(这动画应用中的多重图像必须在计算机屏幕上移动)的合理选择。另一方面,它只能够对256种颜色编码,这使得它不适合精确度要求较高的应用,如摄影领域。

另外一种流行的图像压缩系统是JPEG(读作“JAY-peg”)。它是由ISO中的联合图像专家组(Joint Photographic Experts Group,标准因此得名)研制开发的标准。JPEG已经被证明是压缩彩色照片的一种有效标准,并被广泛用于摄影业,这一点可由大多数数码相机都将JPEG作为它们默认的压缩技术这一事实来证明。

JPEG标准实际上包含多种图像压缩方法,每种都有它自己的目标。在需要绝对精确的情况下,JPEG可提供无损模式。不过,相对于JPEG的其他模式,JPEG的无损模式不能形成高级别的压缩。而且,JPEG的其他模式已被证明很成功,这就意味着人们很少使用其无损模式。相反,称为JPEG基线标准(也称为JPEG的有损顺序模式)的JPEG模式已经成为许多应用的选择标准。

使用JPEG基线标准的图像压缩有几个步骤,其中有一些是利用人眼的局限性设计的。尤其是,相对于颜色的变化,人眼对亮度的变化更为敏感。因此,我们首先来看一幅用亮度成分和色度成分进行编码的图像。第一步是在一个2×2的像素方块中求色度的平均值。这能将色度信息的大小减小为$\frac{1}{4}$,同时保留所有的原始亮度信息。结果是,在没有明显损失图像质量的情况下获得了很高的压缩率。

下一步是将图像划分成8×8的像素块,然后将每一个块作为一个单元来压缩信息。这是通过一种称为离散余弦转换的数学技术实现的,我们现在不需要关心这个转换的细节。更重要的是,这种转换将原始的8×8块变成了另外一种块(这种块中的条目反映了原始块中的像素之间是如何相互联系的),而不是实际像素值。在这个新块里,那些低于预定极限的数值将被0替代,反映的是这些数值所表示出的变化非常小,人眼无法觉察。例如,如果原始块中包含一个棋盘(checkerboard)模式,那么新块就可能表现为平均色。(一个典型的8×8像素块表示的是图像中一个非常小的方块,因此人眼根本不能够识别棋盘的外观。)

这时候,可以应用更传统的行程长度编码、相对编码以及变长编码技术进行进一步的压缩。总之,JPEG基线标准一般能在没有明显质量损失的情况下,将彩色图像压缩至少10倍,有时甚至能压缩30倍。

另外一个数据压缩系统是TIFF(tagged image file format的缩写,即标记图像文件格式)。不过,TIFF最普遍的应用不是数据压缩,而是存储照片及其相关的信息(如日期、时间以及相机设置)的一个标准格式。在存储照片时,图像本身通常会被存储为没有压缩的红、绿、蓝像素成分。

TIFF标准集合里的确有数据压缩技术,其中大多数是为在传真应用中压缩文本文档的图像设计的。为了利用文本文档包含长串的白色像素这一事实,这些标准使用了行程长度编码的变体。TIFF标准中的彩色图像压缩选择是以类似于GIF所使用的技术为基础的,因此并没有被广泛应用于摄影业。

1.9.3 音频和视频压缩
音频及视频的编码和压缩最常用的标准是由ISO领导的运动图像专家组(Motion Picture Experts Group,MPEG)研制开发的,因此这些标准称为MPEG。

MPEG包含许多不同应用的各种标准。例如,高清晰度电视(high definition television,HDTV)广播的要求与视频会议的就不同,广播信号必须找到在各种容量可能很有限的通信路径上传输的方式。另外,这两种应用又都不同于存储视频的应用,它的有些部分可以被重放或略过。

MPEG使用的技术已经超出了本书的范围,但是一般说来,视频压缩技术是以图片序列构建成的视频为基础的,与将运动图像录制到胶片上的方式基本相同。为了压缩这些序列,只有一部分称为I帧(I-frame)的图片是被整个编码的。在两个I帧之间的图片是采用相对编码技术进行编码的,即并没有对整个图片进行编码,而只是记录了与前一个图片的差别。I帧本身经常使用类似于JPEG的技术压缩。

最著名的音频压缩系统是MP3,它是在MPEG标准中开发出来的。事实上,MP3是MPEG layer 3的缩写。与其他压缩技术相比,MP3利用人耳的特性,删除了人耳觉察不到的细节。其中一个特性称为暂时模糊(temporal masking),指的是在一次巨大声响后,短时间内人耳觉察不到本可以听见的轻柔声音。另一个称为频率模糊(frequency masking),指的是某一频率的声音可能掩盖相近频率的轻柔声音。利用这些特性,可以通过MP3获得显著的音频压缩,而且保持接近CD的音质。

使用MPEG和MP3压缩技术,摄像机用128 MB的存储空间就可以录制长达1小时的视频,便携音乐播放器用1 GB的存储空间就可以存储多达400首流行歌曲。但是,不同于其他压缩目的,音频和视频的压缩目的不一定是节省存储空间。真正重要的是获得编码,使得信息能够通过现在的通信系统得到及时的传输。如果每一个视频帧需要1 MB的存储空间,而传播帧的通信路径每秒只能传输1 KB,那么根本无法实现成功的视频会议。因此,除了被认可的复制质量,音频和视频压缩系统的选择还要看及时数据通信的传输速度。这些速度通常用比特每秒(bits per second,bit/s)来度量。常见的单位包括Kbit/s(kilo-bps的简写,即千比特每秒,等于103 bit/s)、Mbit/s(mega-bps的简写,即兆比特每秒,等于106bps)和Gbit/s(giga-bps的简写,即吉比特每秒,等于109 bit/s)。使用MPEG技术,视频展示可以在40 Mbit/s传输速率的通信路径上成功传输。MP3录制需要的传输速率一般不超过64 Kbit/s。

问题与练习

1.列出4种通用的压缩技术。

2.如果使用LZW压缩,并且最初字典只包含x、y和一个空格(如文中所述),对下列信息编码,结果是什么?

xyx yxxxy xyx yxxxy yxxxy

3.在对彩色卡通编码时,为什么GIF比JPEG要好?

4.假设你是航天器设计团队的一员,要设计能驶向其他星球并发回照片的航天器。那么,为了减少存储和传输图像所需的资源,使用GIF或JPEG的基准标准压缩照片是否是一个好主意?

5.JPEG的基准标准利用了人眼的什么特性?

6.MP3利用了人耳的什么特性?

7.说出一种在把数字信息、图像和声音编码为位模式时常见的麻烦现象。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章