色彩量化

在计算机图学中，色彩量化或彩色图像量化是应用于色彩空间的量化；这是一个减少图像中使用的不同颜色数量的过程，通常是为了使新图像在视觉上尽可能与原始图像相似。自 1970 年代以来，人们一直在研究对点阵图执行色彩量化的计算机算法。色彩量化对于在通常由于内存限制而只能显示有限数量颜色的设备上显示具有多种颜色的图像至关重要，并且可以有效压缩某些类型的图像。

“色彩量化”这个名称主要用于计算机图形学研究文献；在应用程序中，使用诸如优化调色板生成、最佳调色板生成或降低颜色深度等术语。其中一些具有误导性，因为标准算法生成的调色板不一定是最优的。

## 算法

大多数标准技术将色彩量化视为三维空间中聚类点的问题，其中点代表原始图像中的颜色，三个轴代表三个颜色通道。几乎任何三维聚类算法都可以应用于色彩量化，反之亦然。在定位簇之后，通常对每个簇中的点进行平均以获得该簇中所有颜色映射到的代表颜色。三个颜色通道通常是红色、绿色和蓝色，但另一种流行的选择是Lab 颜色空间，因为在这空间下欧氏距离更能够感知差异。

迄今为止最流行的色彩量化算法是 Paul Heckbert 于 1979 年发明的中值切割算法。目前使用的许多算法都是该方案的变体。在此之前，大多数色彩量化是使用population algorithm或population method完成的，其本质上是建立一个等大小范围的直方图，并将颜色分配给包含最多点的范围。一种更现代的流行方法是使用八叉树进行聚类，该方法首先由 Gervautz 和 Purgathofer 构思，并由Xerox PARC研究员Dan Bloomberg改进。

<image>

｜

<image>

如果调色板是固定的，就像操作系统中使用的实时色彩量化系统中经常出现的情况一样，色彩量化通常使用“直线距离”或“最近颜色”算法来完成，该算法简单地采用每个原始图像中的颜色并找到最近的调色板条目，其中距离由三维空间中两个对应点之间的距离确定。换句话说，如果颜色是$(r_1, g_1, b_1)$和$(r_2, g_2, b_2)$，我们想要最小化欧氏距离：

$$\sqrt{(r_1-r_2)^2 + (g_1-g_2)^2 + (b_1-b_2)^2}.$$

这有效地将颜色立方体分解为Voronoi 图，其中调色板条目是点，单元格包含映射到单个调色板条目的所有颜色。计算几何中有有效的算法来计算 Voronoi 图并确定给定点落在哪个区域；在实践中，索引调色板太小了，以至于它们通常是矫枉过正的。

<image>

色彩量化经常结合抖色一起运用，这可以消除令人不快的伪像，例如量化平滑渐变时出现的条带，并提供大量颜色的外观。一些现代色彩量化方案往往是图将调色板选择与抖色整合为单一阶段，而不是单独执行它们。

另有其他一些较少见的方案，它们采取完全不同的作法。Local K-means 算法由 Oleg Verevka 于 1995 年构思，设计用于窗口系统，其中一组核心的“保留颜色”被固定供系统使用，许多具有不同配色方案的图像可能同时显示。它是一种后聚类方案，对调色板进行初步猜测，然后迭代地对其进行细化。

在色彩量化的早期，k-means 聚类算法因其较高的算力要求和对起始资料的敏感性而被认为是不切实际。2011 年，M. Emre Celebi 重新研究了 k-means 作为色彩量化器的性能。他证明了 k-means 的有效实现优于大多数的色彩量化方法。

高质量但速度较慢的NeuQuant算法通过训练Kohonen 神经网络将图像减少到 256 种颜色，“该网络通过学习自组织以匹配输入图像中的颜色分布。获取每个神经元在 RGB 空间中的位置会给出一个高质量的颜色图，其中相邻颜色相似。” 这对于具有渐变的图像特别有利。

最后，一种较新的方法是空间色彩量化，由波恩大学的 Puzicha、Held、Ketterer、Buhmann 和 Fellner 构想，它将抖色与调色板生成和简化的人类感知模型相结合，即使对于很少的颜色。它并不严格地将调色板选择视为聚类问题，因为原始图像中附近像素的颜色也会影响像素的颜色。请参阅 示例图像。

## 历史与应用

在 PC 的早期，由于显示内存的限制，显卡通常只支持 2、4、16 以至于 256 色；比起呈现更多颜色，开发商更愿意将内存用在更多像素（更高分辨率）的显示。色彩量化有助于证明这种权衡的合理性，因为它可以在 16 色和 256 色模式下以有限的视觉降级显示许多高彩色图像。在 256 色显示模式下查看高色彩图像时，许多操作系统会自动执行量化和抖色处理，这在仅限于 256 色模式的视频设备占主导地位时非常重要。现代计算机现在可以同时显示数百万种颜色，远远超过人眼所能分辨的颜色，因此主要将此应用程序限制在移动设备和旧硬件上。

如今，色彩量化主要用于GIF和PNG图像。GIF 一直以来都是万维网上最流行的无损动画点阵图格式，但其最多只支持 256 色，因而大多数图像都须经过量化。一些早期的网络浏览器限制图像使用称为网络颜色的特定调色板，导致与最佳优化的调色板相比有更大程度的颜色失真。PNG 图像支持 24 位颜色，但通常可以通过应用色彩量化使文件大小变得更小而不会牺牲太多视觉效果，因为 PNG 格式对调色图像使用的每像素位数更少。

相机镜头所能呈现的无数种颜色是不可能在电脑屏幕上显示出来的；因此将任何照片转换为数位的过程中必然涉及一些量化。实际上，24 位颜色已相当丰富，可以表示人类可感知的几乎所有颜色，并且在可用颜色空间内具有足够小的误差，在视觉上完全相同（如果忠实呈现）。然而，无论是在相机检测器中还是在屏幕上，颜色的数字化必然会限制可用的颜色空间。因此，无论使用多少位来表示颜色，都有许多颜色可能无法再现。例如，在典型的 RGB 色彩空间（计算机显示器上常见）中就无法完全再现人眼所能感知的全部绿色。

由于早期计算机上可用的颜色很少，不同的量化算法会产生非常不同的输出图像。因此，大量时间花在编写复杂的算法上，以使其更逼真。

### 用于图像压缩的色彩量化

许多影像档案格式都支持索引色。

整个图像调色板通常为整个图像选择 256 种“代表性”颜色，其中每个像素引用调色板中的任何一种颜色，如 GIF 和 PNG 文件格式。

区块调色板通常为每个 4x4 像素块选取 2 或 4 种颜色，用于BTC、 CCC、 S2TC和S3TC。

### 编辑器支持

许多位图图形编辑器包含对色彩量化的内置支持，并且在将具有多种颜色的图像转换为具有较少颜色的图像格式时会自动执行它。这些实现中的大多数都允许用户准确设置所需颜色的数量。此类支持的示例包括：

- Photoshop 的模式→索引颜色功能提供了许多量化算法，从固定的 Windows 系统和 Web 调色板到专有的本地和全局算法，用于生成适合特定图像的调色板。
- Paint Shop Pro 在其颜色→减少颜色深度对话框中提供三种标准色彩量化算法：中值切割、八叉树和固定的标准“网络安全”调色板。
- 在 GIMP 2.8 中，Convert Image to Indexed Colors 选项（Image → Mode → Indexed..）允许生成最佳调色板，可选择 2 到 256 种颜色，使用 web 优化调色板的选项，使用黑白调色板（1 位）或使用自定义调色板。它允许从调色板中删除未使用的颜色，并提供多种抖动选项：无、Floyd-Steinberg（正常）、Floyd-Steinberg（减少颜色渗色）和定位以及启用透明度抖动的能力。

色彩量化也用于创建色调分离效果，尽管色调分离的目标略有不同，即尽量减少同一色彩空间中使用的颜色数量，并且通常使用固定的调色板。

一些矢量图形编辑器还利用色彩量化，特别是光栅到矢量技术，这些技术在边缘检测的帮助下创建位图图像的描摹。

- Inkscape 的Path→Trace Bitmap: Multiple Scans: Color函数使用八叉树量化来创建颜色轨迹。

## 也可以看看

- 索引颜色
- 调色盘 (电脑图形学)
- 软件调色板列表#自适应调色板部分。
- 抖动 (数字信号处理)
- 量化 (图像处理)
- 图像分割

## 延伸阅读

- 保罗·S·赫克伯特。帧缓冲器显示的彩色图像量化。ACM SIGGRAPH '82 论文集。首次发布中值切割算法。
- 丹布隆伯格。使用八叉树进行色彩量化。轻音。
- 奥列格·韦列夫卡。Windows 系统中使用局部 K 均值算法的彩色图像量化。95 年西方计算机图形学研讨会论文集。
- J. Puzicha、M. Held、J. Ketterer、JM Buhmann 和 D. Fellner。关于彩色图像的空间量化。（全文 .ps.gz）技术报告 IAI-TR-98-1，波恩大学。1998.