减色算法

算法说明 • 减色误差的测量

本文档说明 ImageMagick 如何对图像进行减色。要完全理解下文，您应当具备基本图像处理技术以及树（tree）数据结构及其术语的知识。

算法说明

为了进行颜色分配，图像被视为 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)。树的每个下层都是通过将一个节点的立方体细分为 8 个大小相等的较小立方体而生成的。这对应于用经过每条边中点的平面将父立方体二等分。

基本算法分三个阶段运行：

1. 分类（Classification）
2. 削减（Reduction）
3. 分配（Assignment）

分类

分类为图像构建一棵颜色描述树。削减不断收缩这棵树，直到它所表示的颜色数最多等于输出图像中所需的颜色数。分配定义输出图像的颜色映射表，并通过在收缩后的树中重新分类来设置每个像素的颜色。我们的目标是使原始颜色与量化后颜色之间的数值差异最小化。要了解更多关于量化误差的信息，请参阅“减色误差的测量”。

分类首先初始化一棵深度足以在叶子中表示每个可能的输入颜色的颜色描述树。然而，对于现实的 Cmax 值，在分类阶段生成一棵完全形成的颜色描述树是不切实际的。如果输入图像的颜色分量被量化到 k 位精度，使得 Cmax = 2^k-1，那么树需要在根节点之下有 k 层，才能在叶子中表示每个可能的输入颜色。由于树的节点总数的缘故，这会变得难以承受：

                   = 8

这种深度的树通常能以最快的计算速度和最少的内存实现源图像的最佳表示。但是，默认深度对某些图像并不合适。因此，调用方可以请求特定的树深度。

对于输入图像中的每个像素，分类从颜色描述树的根开始向下扫描。在树的每一层，它识别出表示 RGB 空间中包含该像素颜色的立方体的那个唯一节点。然后它更新每个这样的节点的以下数据：

n1

颜色被包含在该节点所表示的 RGB 立方体中的像素数量。

n2

其颜色未在树中更低深度的节点上表示的像素数量；初始时，除树的叶子外，所有节点的 n2=0。

Sr,Sg,Sb

所有未在更低深度被分类的像素的红、绿、蓝分量值之和。这些和与 n2 的组合最终将刻画该节点所表示的像素集合的平均颜色。

E

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

削减

削减反复修剪这棵树，直到 n2 > 0 的节点数小于或等于输出图像中允许的最大颜色数。在对树的任意一次迭代中，它选择 E 值最小的那些节点进行修剪，并将其颜色统计数据向上合并。它使用修剪阈值 Ep 按如下方式控制节点选择：

Ep = 0
while （n2 > 0 的节点数）> 所需的最大颜色数
   修剪所有满足 E <= Ep 的节点
   将 Ep 设为剩余节点中最小的 E

这能在合并两个节点时使量化误差最小化。

当要修剪的节点有子节点时，修剪过程会递归调用自身，以便从叶子向上修剪树。被修剪节点的 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 会打印若干误差测量值，包括每像素平均误差、归一化平均误差和归一化最大误差。

归一化误差测量值可用于比较图像。一般而言，平均误差越接近 0，量化图像就越接近源图像。理想情况下，由于人眼是量化质量的最终评判者，误差应当是基于知觉的。

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