图像压缩基础与无损压缩

1948 年，Claude Shannon 在其开创性论文《A Mathematical Theory of Communication》中提出了信息熵的概念，为数据压缩建立了数学基础。

对于一个离散随机变量 $X$，其可能取值为 $\{x_1, x_2, \ldots, x_n\}$，对应概率为 $\{p_1, p_2, \ldots, p_n\}$，香农定义的信息熵为：

熵的单位是比特（bit）。它衡量的是每个符号平均需要多少比特来编码。关键性质：

• 均匀分布时熵最大：当所有符号等概率出现时，$H(X) = \log_2 n$

• 确定性事件熵为零：当某个符号概率为 1 时，$H(X) = 0$

• 熵是无损压缩的理论下界：任何无损编码方案的平均码长不可能低于 $H(X)$

一幅图像中存在三种类型的冗余，压缩的本质就是消除这些冗余：

1. 统计冗余（Statistical Redundancy）：像素值的概率分布不均匀。例如，白色背景的图像中像素值 255 出现频率远高于其他值，可以用更短的编码表示高频值。

2. 空间冗余（Spatial Redundancy）：相邻像素之间存在强相关性。自然图像中，相邻像素的值通常非常接近。

3. 视觉冗余（Visual Redundancy）：人眼对某些信息不敏感。例如，人眼对亮度变化比对色度变化更敏感，对高频细节的感知也有限。

无损压缩只能消除前两种冗余，而有损压缩（后续文章会详细讨论）还可以利用视觉冗余进一步提高压缩比。

Shannon 的率失真理论（Rate-Distortion Theory）回答了一个核心问题：在允许一定失真的前提下，最少需要多少比特来编码信源？

率失真函数定义为：

其中 $D$ 是允许的失真度量（如均方误差），$I(X; \hat{X})$ 是原始信号与重建信号之间的互信息。$R(D)$ 给出了在失真不超过 $D$ 时的最小编码速率。

率失真函数是所有有损压缩算法性能的理论上限。实际的压缩算法（如 JPEG、H.264）都在努力逼近这个理论极限。

David Huffman 在 1952 年提出的 Huffman 编码是最经典的变长编码算法。其核心思想很简单：给高频符号分配短码，给低频符号分配长码。

1. 统计频率：遍历数据，统计每个符号出现的频率

2. 构建优先队列：将所有符号按频率放入最小堆

3. 构建 Huffman 树：

• 取出频率最小的两个节点，合并为一个新节点（频率为两者之和）

• 将新节点放回堆中

• 重复直到堆中只剩一个节点（即根节点）

4. 生成编码表：从根节点出发，左分支标记为 0，右分支标记为 1，每个叶子节点的路径即为该符号的编码

假设有一个包含 5 个符号的信源，频率如下：

构建 Huffman 树后，可能得到如下编码：

平均码长 = 0.35×1 + 0.25×2 + 0.20×3 + 0.12×4 + 0.08×4 = 2.12 bit/symbol

而熵 $H(X) = -0.35\log_2 0.35 - 0.25\log_2 0.25 - 0.20\log_2 0.20 - 0.12\log_2 0.12 - 0.08\log_2 0.08 \approx 2.07$ bit/symbol

Huffman 编码的平均码长非常接近理论下界。

• Huffman 编码是整数比特编码：每个符号至少分配 1 bit，即使其概率很高

• 对于二元信源（只有 0 和 1），如果 $P(0) = 0.9$，Huffman 仍需至少 1 bit 来表示 0，而理论最优只需要 $-\log_2 0.9 \approx 0.15$ bit

• 需要两遍扫描：第一遍统计频率构建编码表，第二遍实际编码

算术编码克服了 Huffman 编码的整数比特限制。它将整个消息编码为一个介于 0 和 1 之间的浮点数，而不是为每个符号分配独立的码字。

1. 初始化区间为 $[0, 1)$

2. 对于消息中的每个符号，根据其概率将当前区间细分为子区间

3. 选择对应符号的子区间作为新的当前区间

4. 编码完成后，输出当前区间内的一个数作为编码结果

假设信源有三个符号 A(0.5)、B(0.3)、C(0.2)，要编码消息 "BAB"：

最终编码为 $[0.575, 0.62)$ 区间内的任意值，例如 0.59。

算术编码的优势在于：它可以为符号分配非整数比特的编码，从而更接近熵的理论极限。在实践中，算术编码比 Huffman 编码平均可以节省 5%–10% 的比特数。

LZ77（Lempel-Ziv 1977）是一种基于字典的压缩算法，由 Abraham Lempel 和 Jacob Ziv 在 1977 年提出。其核心思想是利用数据中的重复模式。

LZ77 使用一个滑动窗口来维护已处理的数据。对于当前位置的数据，算法在窗口中搜索匹配的字符串：

• 如果找到匹配，输出一个 (长度, 距离) 对，表示"从当前位置回退距离个字符，复制长度个字符"

• 如果没找到匹配，输出原始字符

窗口大小决定了可以引用的最大距离，匹配长度决定了可以复制的最大字符数。

DEFLATE 是 LZ77 和 Huffman 编码的组合，由 Phil Katz 在 1993 年为 ZIP 文件格式设计，后来被 gzip、PNG 等广泛采用。

DEFLATE 的工作流程：

1. LZ77 压缩：用滑动窗口查找重复字符串，替换为 (长度, 距离) 对

2. Huffman 编码：对 LZ77 的输出（包括 literal/length 符号和 distance 符号）分别构建 Huffman 树进行编码

3. 动态/静态 Huffman：DEFLATE 支持动态生成 Huffman 表（更优）和使用预定义的静态 Huffman 表（更快）

DEFLATE 的滑动窗口大小为 32KB，匹配长度范围为 3–258 字节。这个设计在压缩比和速度之间取得了良好的平衡。

PNG 的压缩过程分为两个主要阶段：过滤（Filtering）和 DEFLATE 压缩。

过滤是 PNG 独特的预处理步骤。它在 DEFLATE 压缩之前运行，目的是消除像素间的空间冗余，使数据更适合 DEFLATE 压缩。

PNG 定义了 5 种过滤器类型，对每行像素逐一应用：

其中 Paeth 预测器是 PNG 最精巧的设计之一。它根据左侧、上方、左上方三个邻居像素，选择最接近当前像素值的一个作为预测值。具体规则：

p = a + b - c
if |p - a| <= |p - b| and |p - a| <= |p - c|: 选择 a
elif |p - b| <= |p - c|: 选择 b
else: 选择 c

过滤后的残差值（实际值减去预测值）通常集中在 0 附近，这使得后续的 DEFLATE 压缩效率大幅提升。

过滤后的数据被送入 DEFLATE 压缩器。DEFLATE 结合了 LZ77 的字典匹配和 Huffman 编码的熵压缩：

1. LZ77 阶段：在 32KB 的滑动窗口中搜索重复的字节序列，用 (长度, 距离) 对替换

2. Huffman 编码阶段：对 literal/length 符号和 distance 符号分别构建最优 Huffman 树

3. 块输出：DEFLATE 将数据分成多个块，每个块可以选择存储未压缩数据、使用静态 Huffman 表或动态 Huffman 表

PNG 文件由一系列 chunks 组成，每个 chunk 包含 4 字节长度、4 字节类型、数据和 4 字节 CRC 校验：

• IHDR：图像头信息（宽、高、位深、颜色类型等）

• IDAT：压缩后的图像数据（可以有多个 IDAT chunk）

• IEND：图像结束标记

• PLTE：调色板（仅索引色图像）

• tEXt/iTXt：文本元数据

优势：

• 完全无损，适合医疗影像、截图、图标等对精度要求极高的场景

• 支持 Alpha 通道透明度

• 广泛的浏览器和软件支持

• 无专利限制

局限：

• 压缩比通常低于有损格式（JPEG 等）

• 不支持动画（APNG 扩展了这一功能）

• 不支持渐进式加载（标准 PNG 不支持）

• 对于连续色调的自然图像，压缩效率不如 JPEG

根据香农的源编码定理，无损压缩的平均码长 $L$ 满足：

这意味着无损压缩可以把平均码长压缩到接近熵的水平，但永远无法低于熵。对于一个 8bit 灰度图像，如果像素值均匀分布，熵为 8 bit/pixel，此时无损压缩无法减小文件大小。

不同图像类型的无损压缩比差异很大：

这就是为什么无损格式（PNG）适合截图和图标，而自然照片通常选择有损格式（JPEG）的原因。

无损压缩的理论极限意味着：对于连续色调的自然图像，仅靠消除统计冗余和空间冗余，压缩比很难超过 3:1。要进一步提高压缩比，必须引入有损压缩——即允许丢失一些视觉冗余信息。

下一篇将深入讲解 JPEG 的有损压缩流程，包括色彩空间转换、DCT 变换、量化等核心步骤，展示有损压缩如何在可接受的质量损失下实现 10:1 甚至 50:1 的压缩比。