色彩量化

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

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

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

迄今为止最流行的色彩量化算法是 Paul Heckbert 于 1979 年发明的中值切割算法。目前使用的許多算法都是该方案的變體。在此之前，大多數色彩量化是使用population algorithm或population method完成的，其本質上是建立一個等大小範圍的直方圖，並将顏色分配给包含最多點的範圍。一種更現代的流行方法是使用八叉树進行聚類，該方法首先由 Gervautz 和 Purgathofer 構思，並由Xerox PARC研究員Dan Bloomberg改進。
如果调色板是固定的，就像操作系统中使用的实时色彩量化系统中经常出现的情况一样，色彩量化通常使用“直线距离”或“最近顏色”算法来完成，该算法简单地采用每个原始圖像中的顏色并找到最近的调色板条目，其中距离由三维空间中两个对应点之间的距离确定。换句话说，如果顏色是和 ，我们想要最小化欧氏距离：



這有效地将顏色立方体分解为Voronoi 图，其中调色板条目是点，单元格包含映射到单个调色板条目的所有顏色。计算几何中有有效的算法来计算 Voronoi 图并确定给定点落在哪个区域；在实践中，索引调色板太小了，以至于它们通常是矫枉过正的。
色彩量化经常結合抖色一起運用，這可以消除令人不快的伪像，例如量化平滑渐變时出现的条带，并提供大量顏色的外观。一些现代色彩量化方案往往是圖将调色板選擇与抖色整合為單一階段，而不是单独執行它们。

另有其他一些較少見的方案，它们採取完全不同的作法。 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.

Category:图像处理