图像压缩的奥秘

1、图像压缩的奥秘David Austin关键词： 图像压缩，应用数学，快速算法本文所有文字的HTML文件大约有25000个字节。这小于你从这个网页上下载的任何一个图像文件。因为图像文件通常比文字文件大得多，并由于网页包含许多常被传送因而传速变慢的图像，将图像以一种压缩快送方式传送变得非常重要。在这篇文章中我们将看到一个JPEG文件怎样利用尽量小的计算机存储来表示图像。我们也将讨论一些JPEG背后的数学。被更广泛地称为数据压缩的论题问的是：“我们怎样以紧凑、有效的方式表示信息？”除了图像文件外，通常要压缩数据、影像、音乐文件。例如，如何压缩8个GB的iPod Nano的2000首歌曲？问

2、题的关键是通过某种方式组织信息，揭示出可被消除的固有的多余之处。在这篇文章中，我们将用下图作为例子，探讨JPEG基线压缩算法（JPEG为“联合图像专家组”的英文单词第一个字母组成的缩写）。一些压缩算法是无损的，它们保留所有的原始信息。其他的一些，如JPEG基线算法，是有损的，某些信息会被丢失，但仅仅是那些被判断为不重要的信息。在着手之前，我们先天真地确定这张图需要多少计算机存储。首先，图像被布置在一个矩形的像素网格，其尺寸为250×375，总共有93750像素。各像素的颜色通过指定多少比例的红、绿和蓝色的颜色混合在一起来确定。每个颜色分量被表示为0和255之间的一个整数，因此需要一个

3、字节的计算机存储。因此，每个像素需要3个字节的存储空间，这意味着整个图像应该要求93750×3=281250字节。然而，这里显示的JPEG图只有32414个字节，换言之，它已被压缩了大约9倍。我们将描述怎样用压缩过的小文件表示图像，并怎样从被压缩的文件重构图像。压缩算法首先，图像被分成8×8的块状像素。因为每一块都与其他块无关地被处理，我们集中讨论单独一块。特别，我们考察下图中划出阴影的那一块。这里是同一小块放大后的样子，其中每个像素看上去更明显。注意所有8×8像素之间没有太大的变化（但其他块则不一定）。记得数据压缩的目的是以揭示一些多余性的方式表达数据。我们可以

4、想到把每个像素的颜色表示为由红、绿、蓝分量组成的一个三维向量(R,G,B)。在典型的图像中，这些分量之间有巨大的相关性。由于这个理由，我们将使用一个颜色空间变换，它产生一个新的向量，其分量代表亮度Y及蓝色和红色的色度，分别记为Cb和Cr：YCbCr=0.299000.168740.500000.587000.331260.418690.114000.500000.08131RGB.亮度描述了像素的光亮性，而色度则携带有关色调的信息。这三个量通常比(R,G,B)的分量的相关性低。此外，心理视觉实验表明，人的眼睛对亮度比色度更加敏感，这意味着我们可以忽视色度较大的变化，而不会影响我们对图像的感知。

5、由于这种转变是可逆的，我们将能够从向量(Y,Cb,Cr)恢复向量(R,G,B)。当我们希望重建图像时，这是很重要的。（确切地说，我们通常会让色度分量加上128，使得它们表示为0和255之间的数。）当我们将这种变换用到我们的块中的每个像素后，我们得到对应于每个分量的三个新块。这些由下图所示，较亮的像素对应较大的值。如通常所见的，亮度比色度具有较多的变化。由此缘故，通过假设色度在2×2小块上为常数，有时可以得到较大的压缩比，因此记录较少的值。例如，图像编辑软件Gimp当将一个图像存为JPEG文件时，提供了以下的菜单：“Subsampling”选项允许抽取色度值不同方式的选择。这里同样值得

6、注意的是“Quality”参数，它的重要性在下面将变得很清楚。离散余弦变换现在我们到达压缩算法的核心。我们的期望是，这块8×8像素上向量(Y,Cb,Cr)分量的变化相当温和，如上例所示。我们不记录各个分量的值，而是记录比方说平均值以及每个像素值与平均值相差多少。在许多情况下，我们能期待与这些平均值的差相当小，因此可以安全地忽略。这是现在将要解释的离散余弦变换(DCT)的本质。我们先集中于这块中某一行的三个分量当中的一个，想象这8个值由f0,f1,f7代表。我们想以某种方式表示这些值使得它们的变化变得更明显。为此，我们把这些值视为由一个函数fx给出，其中x从0到7之间取值，并把该函数写

7、出余弦函数的一个线性组合：fx=12w=07CwFwcos(2x+1)w16.不要担心Cw（除了C0=1/2外，对所有w都有Cw=1）前面的因子1/2。这个表达式的重要之处在于它把fx用具有变化的频率、带有系数Fw的余弦函数的一个线性组合来表示。下图显示的是对应于频率w的其中4个余弦函数的图像：当然，具有较高频率的余弦函数显示了更快的变化。因此，如果值fx相对慢地改变，较大频率的系数Fw将相对小。故我们可以不记录这些系数以便减少图像文件的尺寸。这些DCT系数可以通过利用反变换Fw=12Cwx=07fxcos(2x+1)w16得到。注意这隐含DCT是可逆的。例如，我们从fx开始，记录Fw。然而，

8、当我们希望重建图像时，我们将有Fw，并重新计算fx。我们并不是仅仅对每块的行运用DCT，而是将探讨图像的二维特性。离散余弦变换首先用到我们这块像素的所有行。如果在垂直方向上图像变化不是太快的话，系数的变化亦然。由此原因，我们可以固定w的一个值，把离散余弦变换运用到从8行像素得到的8个Fw值。这导致了系数Fw,u，其中w是水平频率，u是垂直频率。我们把这些系数存到下图所示的另一个8×8块中。注意到在该块中向下和向右移动时，我们遇到较高频率的系数，它们的重要性如所期望地将变小。DCT系数可由快速离散余弦变换有效地计算，这与用快速傅里叶变换有效计算离散傅里叶系数具有同一思想。量化当然，系数

9、Fw,u是实数，存储为整数。这意味着我们需要将系数四舍五入；我们的舍入方法有利于更大的压缩。我们不是仅仅简单地四舍五入系数Fw,u，而是用一个量化因子除它，然后记录round(Fw,u/Qw,u).这容许我们对另一些频率而言更有所强调。更具体地说，人类的眼睛对图像的迅速变化并不敏感。这意味着，通过对高频选择一个较大的量化因子，我们可以降低较高频率的重要性。这样做并不会显著地影响图像的视觉质量。当一个JPEG文件被产生后，算法诉诸一个参数来控制图像质量及图像的压缩比例。我们称为q的这个参数是从1到100的一个整数。你应该把q看成图像质量的一个测度：较高的q值对应于较高质量的图像和较大的文件尺寸。

10、q产生了另一个量=50q250qif1q50if50q100.下面是作为q的函数的图像：注意较大的q值给出较小的值。然后我们将权舍入成round(Fw,u/Qw,u).自然地，通过这个舍入过程，信息将被失去。当或Qw,u增加时（记得较大的值对应于较小的质量参数q值），更多的信息失去了，且文件尺寸也减少。这里是JPEG标准所推荐的典型Qw,u值。比如考虑亮度系数：和色度系数：这些值被选取以强调较小频率的影响。让我们看看这在上面的例子中怎样工作。记得我们有下面的三块数值：用q=50量化，得到下面的三块：左上角的元素本质上表示了整块的平均。向右移增加水平频率，而向下移增加垂直频率。这里重要之处是有许

11、多个0。现在我们按如下方式对系数排序，使得较小的频率首先出现。对亮度系数，我们可以简记为20711011000000021100000.我们不必把所有的0都记下，而只需告诉多少0出现（注意在色度权中有更多的0）。以这种方式，DCT系数的序列大大地缩短了，而这就是压缩算法的目的。事实上，JPRG算法运用特别有效的方法像这样对序列译码。当重建DCT系数时，我们发现从信息中重建图像是相当直接的。量化矩阵存储在文件中，故DCT系数的近似值可被重新计算出。从这里，向量(Y,Cb,Cr)通过逆离散余弦变换而找到。然后，向量(R,G,B)通过对颜色空间变换求逆而再次获得。这里是取q=50的8×8像

12、素块的重建：下图的重建是当质量参数q=10时的情形。如所期待的，较高的参数q值给出较高质量的图像。JPEG 2000虽然JPEG压缩算法已经取得相当的成功，有几个因素导致了我们构造新算法的想法。下面描述其中的两个因素。首先，DCT在JPEG算法中的运用导致8×8像素块之间边界的不连续性。例如，在某块边缘处的一个像素的颜色可以被该块中任何地方的其他像素的颜色所影响，但却不会被临近的其他块的像素左右。这导致了阻碍之物，可从从质量参数设置为q=5所得到的图像上看出来（顺提一句，该图像文件的尺寸仅为1702比特），也解释了为何JPEG不是存储线状艺术的理想形式。此外，JPEG算法只允许我们以

13、一种分辨率恢复图像。在一些例子中，希望的是以低分辨率恢复图像，同时允许在整个图像被下载过程中以逐步提高的分辨率展示图像。为了这些及其他需要，JPEG 2000标准于2000年12月推出。虽然这两个算法之间有些不同，我们集中于这个事实：JPEG 2000用小波变换取代了DCT。在解释用于JPEG 2000的小波变换之前，我们考虑小波变换的一个较简单的例子。如前一样，想象我们与每个像素的亮度-色度值打交道。DCT把其变换每次用到一行，然后变换列。小波变换将以类似方式工作。为此目的，我们想象有一个序列f0,f1,fn描绘像素中一行三个分量之一的值。与以前一样，我们想将序列中的快速变化与缓慢变化分别开

14、来。为此目的，我们产生一个小波系数序列：a0=(f0+f1)/2a1=(f0f1)/2a2=(f2+f3)/2a3=(f2f3)/2=注意到偶数下标系数记录了两个相邻值的平均数-我们把此称为低通过带，因为高频率变化的信息丧失-而奇数下标系数记录了两个相邻值的差-我们把此称为高通过带，因为高频率信息通过。低通过系数的个数为原先序列中值的个数的一半（和高通过系数一样）。重要的是注意到我们能够从小波系数恢复原先的f值，因为当我们重建图像是需要这样做的：f0=a0+a1f1=a0a1我们重新排序小波系数，把低通过系数列在高通过系数之前。恰如在二维DCT的情形，我们现在可以把同样的运算垂直地变换小波系数

15、。这导致小波系数的二维网格，通过低通过带和高通过带分成四块：如前，我们利用人类的眼睛对图像的迅速变化并不敏感这一事实，通过与在JPEG算法里见到的类似的量化过程，让在高通过系数中见到的迅速变化不显重要性。注意LL区域由2×2像素块中的值的平均化得到，因此表示了图像的一个低分辨率版本。在实际中，我们的图像被分成许多瓦片，通常具有尺寸64×64。选择2的幂次的理由马上就会明了。我们将用这里指定了瓦片的图像来说明之。（这个瓦片是128×128，故在此网页上可以更清楚地看到。）注意，如果首先在LL区域传递系数，我们能在所有系数已经到达之前低分辨率地重建图像，这是JPEG

16、2000算法的目的之一。我们现在能在LL区域内对低分辨率图像执行同样的运算，因而得到越来越低的分辨率图像。小波系数可以通过如下的提升过程计算：a0=(f0+f1)/2,   a1=a0f1,其益处是不必占用额外的计算机内存计算这些系数-a0首先取代f0，然后，a1取代f1。并且，JPEG2000算法所运用的小波变换中，提升运算使得系数的计算更快。JPEG 2000小波变换上面描述的小波变换虽然与JPEG 2000标准中的小波变换精神相似，但比后者简单。例如，有必要对两次以上逐次得到的值再平均，以便重建的图像具有更大的连续性，因此避免像阻碍物这样的现象。用到的一种小波变换是Le Gall(5,3)样条，其中低通过（偶）和高通过（奇）系数由下式计算：a0=18f2+14f1+34f018f1,a1=12f1+f012f1.和前面一样，这个变换是可逆的，且存在提升方案使之有效运行。包含在标准中的另一个小波变换是Cohen-Daubechies-Faura