正文

数据压缩——有益无害(10)

改变未来的九大算法 作者:(美)约翰·麦考密克


但请记住,我们在使用有损压缩,并没有免费午餐。午餐很便宜,但我们必须付钱。当我们将压缩过的文件之一解压到原图大小时,看看发生了什么。因为其中一些像素行和列被删除,计算机必须推测这些消失像素的颜色是什么。最简单的可能推测是给任一消失像素以其相邻像素之一的颜色。选择任一相邻像素都可以,但在这个例子里,计算机选择了消失像素正上方和左边的像素。

这一解压机制的结果显示在图右侧。能看到大部分视觉特征得到了保留,但在画质和细节上有一些明显损失,特别是在树、角楼房顶以及房屋山形墙的格子通气孔等复杂区域。另外,特别是在解压自80×60图片的版本中,你能在房屋屋顶的斜线等区域看到一些相当令人不悦的锯齿。这些现象被我们称为“压缩缺陷”(compression artifact):不仅仅是细节的损失,而且有损压缩的某种方法会在接下来的解压中引入明显的新特征。

尽管抛弃把戏在理解有损压缩的基本思想上很有用,但在这里描述的简单抛弃把戏却极少用到。计算机的确会“抛弃”信息以实现有损压缩,但它们对抛弃哪些信息却要小心得多。这方面的常见例子之一,就是JPEG图像压缩格式。JPEG是一种精心设计的图像压缩技术,它在效果上要比每两行(列)抛弃一行(列)的抛弃把戏好很多。仔细看看下面的图,将图片的质量和大小与上图相比。最上方的JPEG图片大小为35 KB,但几乎和原始图片相同。通过抛弃更多信息并继续使用JPEG格式,我们得到了中间大小为19 KB的图。尽管房屋的格子通气孔有些模糊和细节上的损失,但中间图片的质量依然很棒。但如果压缩得太厉害,JPEG格式也会有压缩缺陷:最底部的JPEG图被压缩到只有12 KB,你能看到天空中出现了一些块状效果,在房顶斜线右边的天空也出现了一些令人不快的斑点。

尽管JPEG抛弃战略的细节太过技术化,在这里不能完整描述,但这项技术的基本原理还算好说。JPEG首先将整张图片划分为8×8像素的小方块,每个方块都会被单独压缩。注意,在没有压缩的情况下,每个方块代表8×8=64个数字。(我们假设这是张黑白照片——如果它是彩色图片,那么就会有三种不同的颜色,数字会是原来的三倍,但在这里我们不要担心这一细节。)如果方块恰好只有一种颜色,整个方块就能由一个数字代表,而计算机就能“抛弃”63个数字。如果方块大部分由一种颜色组成,只有少数像素的颜色略有不同(也许一片天空的灰度都相同),计算机也可以用单个数字代表方块,让方块得到好的压缩结果,并在稍后解压时只出现少量错误。在上图中的最后一张图中,天空中一些8×8的块,就是采用这种方法压缩,导致出现了一些单色方块。

如果8×8方块从一种颜色渐变为另一种颜色(比如左边是深灰色,右边是浅灰色),那么64个数字也许能被压缩到只有2个:一个深灰的值和一个浅灰的值。JPEG算法并不一定这么运作,但它使用了相同的思想:如果一个8×8方块符合一些已知模式如时时色(constant color)或渐变色(smoothly varying color)的组合,那么其大部分信息就可以被抛弃,只需存储每个模式的级别或量即可。


上一章目录下一章

Copyright © 读书网 www.dushu.com 2005-2020, All Rights Reserved.
鄂ICP备15019699号 鄂公网安备 42010302001612号