本文起源于我们在奥本大学过去几年开发的数据压缩课程。该课程是基础的，从香农和霍夫曼的基本（文本）压缩方法开始。有些方法可以通过纸笔示例来理解；其他方法，例如要通过压缩修改的图像，则需要一些机器实验。

学生可以选择提交项目作为课程评估的一部分。我们见过各种各样的项目，包括一个有趣的在手持计算器上进行霍夫曼编码的例子，一个关于 PNG（便携式网络图形）的概述演示，以及一个关于 JPEG 平滑处理的项目。

我们将介绍 JPEG 和小波的变换技术，讨论这些方法共享的一些数学主题，并演示如何使用高级线性代数软件包来理解这些方案。这些图像主要是在 GNU/Linux (x86) 和 Solaris (SPARC) 上，以及 Macintosh 上使用 Octave 和 Matlab 生成的。

无信息损失的数据压缩方法已在图像数据上使用了一段时间。事实上，流行的 GIF 格式使用 LZW 方案（UNIX compress 中使用的基本方法）来压缩 256 色图像。PNG 更复杂、功能更强大，它使用预测器（或过滤器）来准备数据，以便进行 gzip 风格的压缩。（Greg Roelofs 对 PNG 进行了介绍，并对关于 GIF 的专利问题做了一些注释 [参见资源 8]。）然而，使用具有数千种颜色的高分辨率图像的应用可能需要比这些 无损 方法所能实现的更高的压缩率。

有损 方案会丢弃一些数据，以获得更好的压缩效果。当然，问题在于决定哪些信息应该被妥协。压缩文本时的信息丢失通常是不可接受的，尽管从英文文本中消除每个元音等简单方案可能会在某些地方找到应用。图像和声音的情况则不同；在这些情况下，一些数据丢失可能是完全可以接受的，甚至是无法察觉的。

在 20 世纪 80 年代，联合图像专家组 (JPEG) 成立，旨在制定静止图像压缩标准。该规范包括无损和有损模式，尽管后者可能最受关注（通常也是“JPEG 压缩”的含义）。G. K. Wallace 发表了一篇论文（参见资源 10），详细讨论了该标准。

有损 JPEG 中的方法依赖于一个重要的数学和物理主题来进行压缩：局部逼近。JPEG 组采用了这个想法，并根据对人类视觉系统研究的成果对其进行了微调。由此产生的方案得到了广泛的应用，部分原因是它是一个开放标准，但主要是因为它在很大一类图像上表现良好，并且资源需求相当适中。

JPEG 和小波方案都属于变换方法的一般范畴。小波技术的开发比 JPEG 中的经典方法出现得更晚，并且是永无止境地寻找“更好”的基本图像的结果。

粗略地说，像 JPEG 和小波这样的有损压缩方案的第一步是将图像分解成更简单、更基本的图像的加权序列。在这个阶段，图像可以从基本图像及其相应的权重中完全重建。该方法的有效性很大程度上取决于基本图像的选择。一旦选择了基本图像集或基，任意图像就可以被等效的权重集合所取代。具有相应较大权重的基本图像表明其在整体图像中的特征重要性。（这里的假设是基图像已经归一化，因此它们具有相同的数学大小。）

这个过程背后的数学原理用线性代数的语言来表达。在基本图像的选择上有相当大的数学自由度；然而，在实践中，它们通常被选择来展示感兴趣的图像类别的内在特征。例如，JPEG 选择的基本图像旨在反映某些经典的空间频率。

使用基将图像分解为权重集合的过程称为变换。为了简化事情，我们将考虑灰度图像（颜色将在结论中简要讨论），灰度图像可以表示为整数的 mxn 数组。值的范围对于理解数学思想并不重要，尽管通常将值限制在 [0,255] 区间内，总共给出 256 个灰度级别。例如，图 3(a) 显示了一个包含 256x256 像素和 145 种灰度阴影的图像。

从数学上讲，mxn 灰度图像空间的任何基都必须包含正好 mn 个图像——mxn 图像中的像素数。因此，mxn 图像的变换将具有 mn 个权重。权重可以方便地排列成一个 mxn 数组，称为变换后的图像，即使它根本不是真正的图像。

变换过程本身当然不是一种压缩技术（因为变换后的图像与原始图像的大小相同），但它可以导致压缩。假设可以选择基图像，以便对于广泛的图像类别，许多权重最终都很小：对于给定的图像，将这些小权重设置为零，并使用生成的修改后的权重数组来表示它。由于图像的变换已被修改，因此它只能用于逼近原始图像。逼近效果如何？这取决于方案在丢弃非零权重方面的效果，即取决于基元素的适当性和可以丢弃的权重数量。JPEG 和小波方法都采用了这种类型的过程，并提供了显着的压缩优势，通常对再现质量的影响最小。它们在基本图像的选择上有所不同，即在使用的变换上有所不同，随后在用于丢弃小权重的方法上也有所不同。然而，两者都共享一个想法，即选择一个可以有效表示图像的基，通常只使用其少量基本图像。

在本节中，将介绍几个使用余弦变换的示例。这种变换被 JPEG 使用，应用于图像的 8x8 部分。对于每个 N，都存在 NxN 余弦变换，它将空间信息交换为频率信息。对于 N=4 的情况，给定图像的 4x4 部分可以写成图 1(a) 中出现的 16 个基本图像的线性组合。

该变换提供了线性组合中的系数，允许根据频率内容对原始图像进行逼近或调整。一种可能性是简单地消除某些频率，从而获得一种部分和逼近。例如，JPEG 中的隐含假设是，图像中的高频信息对于人眼来说往往不太重要。

图 1 中的图像可以从我们网站上提供的脚本中获得（参见资源 4），如下所示。我们将使用“>”来表示 Matlab 或 Octave 打印的提示符，但这会因平台而异。

定义测试图像

> x = round(rand(4)*50) % 4x4 random matrix,
                       % integer entries in
[0,50]

这将显示一些（随机）矩阵，可能是

    | 10 20 10 41 |
    | 40 30 2  12 |
    | 20 35 20 15 |

我们可以使用以下指令查看此“图像”

> imagesc(x);      % Matlab users
> imagesc(x, 8);   % Octave users

将显示类似于图 1(b) 左下方较小图像的内容。（我们选择 4x4 示例是为了清晰起见；但是，Octave 中的查看器可能无法正确显示它。在这种情况下，可以先填充图像然后再显示，或者可以选择更大的图像。）现在请求部分和矩阵（图 1(b) 中的较大图像）

> imagesc(psumgrid(x)); % Display the 16 partial
                        % sums

部分和是从基本元素按照上面锯齿形顺序构建的。图 1(a) 中的这条路径是基于基本元素频率的增加。粗略地说，图 1(b) 中的人工图像是就 JPEG 压缩而言最糟糕的一种。由于它是随机的，因此它可能具有显着的高频项。我们可以通过执行离散余弦变换来看到这些

> Tx = dct(x, 4) % 4
                 % of x

对于上面的例子，这给出了矩阵

     | 79.25   9.47  4.75 -11.77 |
     |  6.25 -19.69 -4.25 -11.60 |
     |  5.97   8.02 12.73 -15.64 |

用于从基本元素构建图 1 中部分和的系数。左上角的条目被特别认可为DC 系数，表示平均灰度级；其他的是AC 系数，AC0,1 到 AC3,3。

Tx 右下角的项对应于图像的高频部分。请注意，即使在这种情况下的“最坏情况”中，图 1 也表明，无需使用所有 16 项也可以获得相当好的图像。

部分和逼近的过程应用于图 2 中的“真实”图像，其中显示了 32x32 图像的 1024 项中的 1/4、1/2 和 3/4。这些可以使用以下形式的调用生成

> x = getpgm('math4.pgm'); % Get a graymap image
> n = length(x);        % n is the number of rows
                        % in the square image
> y = psum(x, n*n / 2); % y is the partial sum
                        % using 1/2 of the terms
> imagesc(y);           % Display the result

我们的逼近保留了与来自低于某个选定阈值值的锯齿形序列的项相对应的所有频率信息；其余的高频信息被丢弃。尽管这可以被认为是类似 JPEG 方案的特例，但 JPEG 允许更复杂地使用频率信息。

JPEG 利用局部逼近的思想进行压缩：使用余弦变换变换完整图像的 8x8 部分，然后通过一种倾向于抑制高频元素并减少每个项所需比特数的方法量化每个块。为了“恢复”图像，使用了反量化步骤，然后是逆变换。（我们忽略了 JPEG 中对量化器的输出进行无损压缩的部分，但这不会影响图像质量。）矩阵运算可以图解为

  transform    quantize     dequantize     invert
x  ------>  Tx  ----->  QTx  -------> Ty  ---> y

在 Octave 或 Matlab 中，各个步骤可以写成

> x = getpgm('bird.pgm'); % Get a graymap image
> Tx = dct(x);       % Do the 8
> QTx = quant(Tx);   % Quantize, using standard
                     % 8
> Ty = dequant(QTx); % Dequantize
> y = invdct(Ty);    % Recover the image
> imagesc(y);        % Display the image

准确地说，应该对矩阵 y 进行舍入过程。此外，我们忽略了标准中指定的零移位，它会影响量化的 DC 系数。

应该强调的是，我们无法完全恢复图像——在量化阶段已经有信息丢失。比较矩阵 x 和 y 以及这种实验的差异图像 x-y 是很有启发意义的，如图 3(f) 所示。使用这些矩阵的某些函数来测量“图像质量损失”引起了人们的极大兴趣。考虑到人类视觉系统的复杂性，这是一个难题。

图 3 中的图像是在几个“质量”级别生成的，使用了来自独立 JPEG 组的软件（参见资源 5）。尺寸以每像素比特数 (bpp) 给出；即，平均而言，存储图像矩阵表示中的每个数字所需的比特数。GIF 和 PNG 版本的尺寸也包含在内以供参考。（“Bird”是滑铁卢 BragZone [参见资源 11] 中提出的标准图像集合的一部分，并已为本文的目的进行了修改。）

类似 JPEG 方案的一个麻烦方面是“块效应”的出现，这是在块之间经常出现的明显不连续性，通常在激进量化之后出现。图 6 左侧的图像是使用建议的亮度量化器的标量倍数生成的。可以清楚地看到块，尤其是在图像的“平滑”区域。

JPEG 对图像中的单个 8x8 块进行操作并独立处理它们。如果量化激进，则单个块内的细节信息可能会显着丢失。JPEG 中使用的余弦变换具有可能（间接地）有助于平滑相邻块之间过渡的属性；然而，当块被重新组装并且图像被恢复时，块到块处理的轨迹可能是明显的。在这种情况下，可能希望将平滑方案作为恢复过程的一部分来实现。本节考虑了 JPEG 静止图像数据压缩标准 一书（参见资源 7）中讨论的后端平滑过程。

JPEG 解压缩器可能只对许多原始频率信息有粗略的估计，但它通常对其每个原始 8x8 块中的平均灰度级有相当好的估计（因为量化器的选择方式）。其思想是使用给定块的最近邻居的平均灰度（DC 系数）信息来调整给定块的（AC 系数）频率信息。图 4 用一个“超块”说明了这个过程，该超块由一个中心 8x8 图像及其最近邻居组成。右侧图像中的中心块已通过其最近邻居（周围的八个 8x8 块）的影响进行了“平滑”。

图 5 说明了更复杂图像上的过程。在这里，图像被绘制成一个表面，在每个像素 (y,x) 处，表面的高度表示灰度值。对于给定的 8x8 块，由其最近邻居组成的 3x3 超块包含 3282 个总条目。多项式

         + a6y2 + a7x + a8y + a9

通过要求每个子块上的平均值与平均灰度估计值相匹配来拟合（这给出了未知数 a1,...,a9 的九个方程）。多项式定义了中心块上的一个表面，该表面逼近了原始表面的相应部分。图 5 显示了 (a) 中的表面及其在 (b) 中的多项式逼近。

JPEG 解压缩器可以对多项式逼近执行变换过程，从而获得原始图像频率信息的一组预测器。可以使用这些预测器调整压缩器传递的原始估计值，以期减少块效应问题。

在图 5 中，最低的五个频率被考虑用于通过预测器进行调整：压缩器传递的零值被预测值替换（受一定程度的钳制）。应用于激进量化鸟图像的过程如图 6 所示。deblock.m 脚本（参见资源 4）执行平滑处理。以下代码用于生成右侧图像

> x = getpgm('bird.pgm'); % Get a graymap image
> Tx = dct(x);       % Do the 8
> QTx = quant(Tx, 4*stdQ); % Quantize, using
                           % 4*luminance
> Ty = dequant(QTx);       % Dequantize
> Tz = deblock(Ty);        % Smooth
> z = invdct(Tz);          % Recover the image
> imagesc(z);              % Display the image

这种平滑方案很有吸引力，部分原因是它的简单性，以及它可以作为 JPEG 的后端程序使用（无论原始文件是否考虑到这一点进行压缩）。然而，JPEG 通过丢弃信息来实现其相当令人印象深刻的压缩效果。平滑过程有时会对丢失的数据做出很好的猜测，但它无法恢复原始信息。

我们希望检查的信号特征可以指导我们寻找“正确”的基向量。例如，余弦变换是傅里叶变换的衍生，傅里叶变换的发展在某种意义上是寻找基本频率的结果，周期信号可以用这些基本频率来分解。

傅里叶变换是信号分析领域不可或缺的工具。当用作压缩设备时，我们可能希望它具有能够突出局部频率信息的能力——通常，它没有。信号的傅里叶展开给出的权重可以产生关于频率整体强度的信息，但信息是全局的。即使权重很大，它通常也不会给我们任何线索，说明相应频率在其上显着的“时间间隔”的位置。

近年来，由于 Ingrid Daubechies（参见资源 1）证明了存在具有紧支撑的连续（且更平滑）小波，人们对小波变换的兴趣和使用显着增长。它们已在数学和物理学中找到作为理论设备的归宿，并作为应用于无数领域的实用工具，包括表面分析、图像编辑和查询，当然还有图像压缩。

在本节中，我们介绍一个使用 Haar 小波的示例，在某种意义上，它是最简单的小波。图 7 中的 16 个基本元素构成了 4x4 图像集的基。将这些与图 1 中的余弦变换元素进行比较。即使在这个“粗糙”的分辨率级别，也可以开始看到具有局部支撑的元素的形成。

示例中使用的简单（有损）压缩方案不如 JPEG 中使用的量化方案复杂。基本上，我们丢弃任何小于某个选定阈值的权重。在图 8 中，我们在几个容差设置下对“鸟”使用了这个简单的方案。

将变换后的图像中的权重设置为零等效于消除图像展开中相应的基本数组。这说明了一种简单的部分和（投影）压缩方法，类似于图 2 中的示例。更复杂的小波方案的示例可以使用 Geoff Davis 的小波图像压缩构建工具包（参见资源 2）来完成。Strang 的文章（参见资源 9）对小波进行了简短的基础介绍。

关于 JPEG 和小波的讨论集中在灰度图像上。彩色图像可以为每个像素分配一个红色、绿色和蓝色三元组 (rgb)，尽管也可以选择其他方式。以亮度、色调和饱和度指定的颜色（称为亮度-色度表示）可能从压缩的角度来看是可取的，因为人类视觉系统对亮度分量中的误差比对色度分量中的误差更敏感（参见资源 7）。给定颜色表示，JPEG 和小波方案可以应用于三个平面中的每一个。

本文改编自最近出版的一本书（参见资源 3）。更多信息，例如平滑过程的详细信息，以及脚本和完整文档，可以从我们的网站获得（参见资源 4）。

有关 Matlab（适用于 GNU/Linux 和其他平台）的信息，请访问 http://www.mathworks.com/。Octave 由 John W. Eaton 开发，并由许多人贡献，根据 GNU 通用公共许可证分发。完整源代码和适用于多个平台的即用型可执行文件可通过 ftp 从 ftp.che.wisc.edu 的 /octave 目录匿名获取。Linux Journal 之前的文章（参见资源 6）中介绍了 Octave，在线信息可以在 http://www.che.wisc.edu/octave/ 上找到。

资源