使用自适应空间细分进行颜色缩减

算法描述 • 测量颜色缩减误差

本文档描述了 ImageMagick 如何对图像进行颜色缩减。为了完全理解以下内容，您应该了解基本的图像处理技术、树数据结构和术语。

算法描述

为了进行颜色分配，图像是一组 n 个像素，其中每个像素都是 RGB 空间中的一个点。RGB 空间是一个三维向量空间，每个像素 p(i) 由红、绿、蓝坐标的有序三元组定义，(r(i), g(i), b(i))。

每个主要颜色分量 (红色, 绿色 或 蓝色) 代表一个强度，该强度从 0 线性变化到最大值 Cmax，对应于该颜色的完全饱和度。颜色分配是在 RGB 空间中以 (0, 0, 0) 和 (Cmax, Cmax, Cmax) 为对角顶点的立方体组成的域上定义的。ImageMagick 要求 Cmax= 255。

该算法将该域映射到一棵树上，树中的每个节点都代表该域内的立方体。在下面的讨论中，这些立方体由两个相对顶点的坐标定义：RGB 空间中离原点最近的顶点和离原点最远的顶点。

树的根节点代表整个域，从 (0,0,0) 到 (Cmax, Cmax, Cmax)。树的每个较低层都是通过将一个节点的立方体细分为八个大小相同的较小立方体来生成的。这对应于用通过每个边的中点的平面将父立方体二等分。

基本算法分为三个阶段

1. 分类
2. 缩减
3. 分配

分类

分类为图像构建了一个颜色描述树。缩减会压缩这棵树，直到它所代表的数量最多等于输出图像中所需的颜色数量。分配定义了输出图像的颜色映射，并通过在缩减后的树中重新分类来设置每个像素的颜色。我们的目标是最小化原始颜色和量化颜色之间的数值差异。要详细了解量化误差，请参阅 测量颜色缩减误差。

分类首先通过初始化一个足够深的颜色描述树来开始，以在叶节点中表示每个可能的输入颜色。但是，对于实际的 Cmax 值，在分类阶段生成一个完全形成的颜色描述树是不切实际的。如果输入图像中的颜色分量被量化为 k 位精度，使得 Cmax = 2^k-1，那么树将需要 k 层在根节点下方，才能在叶节点中表示每个可能的输入颜色。这变得不可行，因为树的节点总数

total nodes = 1+Sum(8^i), i=1,k

For k=8,
nodes = 1 + (8^1+8^2+....+8^8)
      = 1 + 8(8^8 - 1)/(8 - 1)
      = 19,173,961 

因此，为了避免构建一个完全填充的树，ImageMagick

1. 仅在需要时才初始化节点数据结构；
2. 选择树的最大深度作为输出图像中所需颜色数量的函数（当前为 二进制 对数 Cmax）。

For Cmax=255,
maximum tree depth = log2(256)
                   = 8 

这种深度的树通常允许以最快的计算速度和最少的内存量获得对源图像的最佳表示。但是，对于某些图像，默认深度是不合适的。因此，调用者可以请求特定的树深度。

对于输入图像中的每个像素，分类从颜色描述树的根节点向下扫描。在树的每一层，它识别出代表包含像素颜色的 RGB 空间中的立方体的单个节点。它更新每个此类节点的以下数据

n1

颜色包含在此节点所代表的 RGB 立方体中的像素数量；

n2

颜色不在树中较低深度节点中表示的像素数量；最初，对于除树的叶节点之外的所有节点，n2=0。

Sr,Sg,Sb

所有未在较低深度进行分类的像素的 红色、绿色 和 蓝色 分量值的总和。这些总和与 n2 的组合将最终表征由该节点表示的一组像素的平均颜色。

E

包含在节点内的每个像素与节点中心的 RGB 空间中的平方距离。这表示节点的量化误差。

缩减

缩减会重复修剪树，直到 n2 > 0 的节点数量小于或等于输出图像中允许的最大颜色数量。在对树进行的任何给定迭代中，它会选择那些 E 值最小的节点进行修剪，并将它们的色彩统计信息向上合并。它使用修剪阈值 Ep 来控制节点选择，如下所示

Ep = 0
while number of nodes with (n2 > 0) > required maximum number of colors
   prune all nodes such that E <= Ep
   Set Ep  to minimum E in remaining nodes 

这在合并两个节点时会最小化任何量化误差。

当要修剪的节点有子节点时，修剪过程会递归调用自身，以便从叶节点向上修剪树。被修剪节点中的 n2、Sr、Sg 和 Sb 值始终会添加到该节点父节点中的对应数据中。这保留了被修剪节点的颜色特征，以便以后进行平均。

对于每个节点，n2 个像素存在，对于这些像素，该节点表示包含这些像素颜色的 RGB 空间中的最小体积。当 n2 > 0 时，该节点将唯一地定义输出图像中的一种颜色。在缩减开始时，对于除代表输入图像中存在的颜色的树的叶节点之外的所有节点，n2 = 0。

另一个像素计数 n1 表示该节点所代表的立方体体积内的总颜色数量。这包括 n1 - n2 个像素，这些像素的颜色应该由树中较低级别的节点定义。

分配

分配从修剪后的树生成输出图像。输出图像包含两个部分

1. 颜色映射，它是一个颜色描述（RGB 三元组）数组，用于输出图像中存在的每种颜色。
2. 像素数组，它将每个像素表示为指向颜色映射数组的索引。

首先，分配阶段对修剪后的颜色描述树进行一次遍历，以建立图像的颜色映射。对于每个 n2 > 0 的节点，它将 Sr、Sg 和 Sb 除以 n2。这将生成所有未低于此节点进行分类的像素的平均颜色。这些颜色中的每一个都成为颜色映射中的一个条目。

最后，分配阶段在修剪后的树中重新分类每个像素，以识别包含像素颜色的最深节点。像素数组中的像素值成为此节点的平均颜色在颜色映射中的索引。

经验证据表明，YUV 或 YIQ 等色彩空间中的距离比 RGB 空间中的距离更能对应于感知的颜色差异。在对图像进行颜色缩减时，这些色彩空间可能会产生更好的结果。这里算法与描述的相同，只是每个像素都是替代色彩空间中的一个点。为方便起见，颜色分量被归一化为从 0 到最大值 Cmax 的范围。然后可以按照描述的那样进行颜色缩减。

测量颜色缩减误差

根据图像的不同，颜色缩减误差可能是明显的或不可见的。具有高空间频率（例如头发或草）的图像显示的误差远小于具有大平滑阴影区域（例如面部）的图像。这是因为颜色缩减过程引入的高频轮廓边缘被图像中的高频掩盖了。

为了测量原始图像和颜色缩减图像之间的差异（总颜色缩减误差），ImageMagick 在图像中的所有像素上累加 RGB 空间中每个原始像素值与其颜色缩减值之间的平方距离。ImageMagick 打印了多个误差测量值，包括每个像素的平均误差、归一化平均误差和归一化最大误差。

归一化误差测量值可用于比较图像。通常，平均误差越接近零，量化图像就越类似于源图像。理想情况下，误差应该是感知性的，因为人眼是量化质量的最终评判者。

当在 -colors 和 -verbose 选项上指定 magick 命令行时，会测量和打印这些误差