查看“︁色彩量化”︁的源代码

{| style="float:right"
|[[File:Dithering_example_undithered.png|frame| 24 位 RGB 顏色的示例圖像]]
|-
|<!-- 檔案不存在 [[File:Dithering_example_undithered_16color_palette.png|frame|将同一圖像缩减为特地選擇的 16 色调色板，以最好地代表该圖像；底部的方塊顯示調色板所选顏色。 ]] ，可從英文維基百科取得 -->
|-
|
|}
在[[计算机图形|計算機圖學]]中，'''色彩量化'''或'''彩色圖像量化'''是应用于[[色彩空間|色彩空间的]]量化；這是一个减少[[图像|圖像]]中使用的不同[[颜色|顏色]]數量的过程，通常是为了使新圖像在视觉上尽可能与原始圖像相似。自 1970 年代以来，人们一直在研究对點陣图執行色彩量化的计算机算法。色彩量化对于在通常由于内存限制而只能显示有限數量顏色的设备上显示具有多种顏色的圖像至关重要，并且可以有效壓縮某些类型的圖像。

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

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

迄今为止最流行的色彩量化算法是 Paul Heckbert 于 1979 年发明的[[中位切割演算法|中值切割]]算法。目前使用的許多算法都是该方案的變體。在此之前，大多數色彩量化是使用''population algorithm''或''population method''完成的，其本質上是建立一個等大小範圍的直方圖，並将顏色分配给包含最多點的範圍。一種更現代的流行方法是使用[[八叉树]]進行聚類，該方法首先由 Gervautz 和 Purgathofer 構思，並由[[帕羅奧多研究中心|Xerox PARC]]研究員[[Dan Bloomberg]]改進。
{|
|[[File:Rosa_Gold_Glow_2_small_noblue.png|left|frame|一张已移除蓝色通道的小照片。這意味着它的所有像素顏色都位于顏色立方体的二维平面中。]]
|[[File:Rosa_Gold_Glow_2_small_noblue_color_space.png|left|thumb|300x300px|左侧照片的色彩空间，以及[[Adobe Photoshop|Photoshop]]生成的 16 色优化调色板。显示了每个调色板条目的 Voronoi 区域。]]
|}
如果调色板是固定的，就像操作系统中使用的实时色彩量化系统中经常出现的情况一样，色彩量化通常使用“直线距离”或“最近顏色”算法来完成，该算法简单地采用每个原始圖像中的顏色并找到最近的调色板条目，其中距离由三维空间中两个对应点之间的距离确定。换句话说，如果顏色是<math>(r_1, g_1, b_1)</math>和<math>(r_2, g_2, b_2)</math> ，我们想要最小化[[欧几里得距离|欧氏距离]]：

: <math>\sqrt{(r_1-r_2)^2 + (g_1-g_2)^2 + (b_1-b_2)^2}.</math>

這有效地将顏色立方体分解为[[沃罗诺伊图|Voronoi 图]]，其中调色板条目是点，单元格包含映射到单个调色板条目的所有顏色。[[计算几何]]中有有效的算法来计算 Voronoi 图并确定给定点落在哪个区域；在实践中，索引调色板太小了，以至于它们通常是矫枉过正的。
[[File:Spatial_color_quantization_-_rainbow,_4_colors.png|frame|使用空间色彩量化将彩色圖像减少为 4 种顏色。]]
色彩量化经常結合[[抖動 (數位訊號處理)|抖色]]一起運用，這可以消除令人不快的伪像，例如量化平滑渐變时出现的条带，并提供大量顏色的外观。一些现代色彩量化方案往往是圖将调色板選擇与抖色整合為單一階段，而不是单独執行它们。

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

在色彩量化的早期，[[K-平均算法|k-means 聚類]]算法因其較高的算力要求和對起始資料的敏感性而被認為是不切實際。2011 年，M. Emre Celebi 重新研究了 k-means 作為色彩量化器的性能。<ref>
{{Cite journal |last=Celebi, M. E. |year=2011 |title=Improving the performance of k-means for color quantization |journal=[[Image and Vision Computing]] |volume=29 |issue=4 |page=260–271 |arxiv=1101.0395 |bibcode=2011arXiv1101.0395E |doi=10.1016/j.imavis.2010.10.002 |s2cid=9557537}}</ref> 他證明了 k-means 的有效實現优于大多數的色彩量化方法。

高质量但速度较慢的''NeuQuant''算法通过训练[[自组织映射|Kohonen 神经网络]]将圖像减少到 256 种顏色，“该网络通过学习自组织以匹配输入圖像中的顏色分布。获取每个神经元在 RGB 空间中的位置会给出一个高质量的顏色图，其中相邻顏色相似。” <ref>{{Cite web|title=NeuQuant: Neural Image Quantization|url=http://members.ozemail.com.au/~dekker/NEUQUANT.HTML|url-status=dead|archive-url=https://web.archive.org/web/20060614072845/http://members.ozemail.com.au/~dekker/NEUQUANT.HTML|archive-date=2006-06-14|access-date=2006-05-02}}</ref>這对于具有渐變的圖像特别有利。

最后，一种较新的方法是''空间色彩量化''，由[[波恩大学]]的 Puzicha、Held、Ketterer、Buhmann 和 Fellner 构想，它将抖色与调色板生成和简化的人类感知模型相结合，即使对于很少的顏色。它并不严格地将调色板選擇视为聚類问题，因为原始圖像中附近像素的顏色也会影响像素的顏色。请参阅[https://web.archive.org/web/20160426135306/www.cs.berkeley.edu/~dcoetzee/downloads/scolorq/#sampleimages 示例圖像]。

== 歷史與應用 ==
在 PC 的早期，由于顯示記憶體的限制，顯示卡通常只支持 2、4、16 以至於 256 色；比起呈現更多顏色，開發商更願意将記憶體用在更多像素（更高解析度）的顯示。色彩量化有助于证明這种权衡的合理性，因为它可以在 16 色和 256 色模式下以有限的視覺降級顯示許多高彩色圖像。在 256 色顯示模式下查看高色彩圖像时，許多操作系统会自動執行量化和抖色處理，這在仅限于 256 色模式的视频设备占主导地位时非常重要。现代计算机现在可以同时显示數百万种顏色，远远超过人眼所能分辨的顏色，因此主要将此应用程序限制在移动设备和旧硬件上。

如今，色彩量化主要用于[[GIF]]和[[PNG]]圖像。GIF 一直以來都是[[万维网]]上最流行的無損動畫點陣图格式，但其最多只支持 256 色，因而大多數圖像都須經過量化。一些早期的网络浏览器限制圖像使用称为[[网页颜色|网络顏色的]]特定调色板，导致与最佳優化的调色板相比有更大程度的顏色失真。 PNG 圖像支持 24 位顏色，但通常可以通过應用色彩量化使文件大小變得更小而不会犧牲太多视觉效果，因为 PNG 格式对调色圖像使用的每像素位數更少。

相机镜头所能呈现的无數种顏色是不可能在电脑屏幕上显示出来的；因此将任何照片转换为數位的過程中必然涉及一些量化。实际上，24 位顏色已相當丰富，可以表示人类可感知的几乎所有顏色，并且在可用[[色彩空間|顏色空间]]内具有足够小的误差，在视觉上完全相同（如果忠实呈现）。{{Citation needed|date=July 2011}}然而，无论是在相机检测器中还是在屏幕上，顏色的數字化必然会限制可用的顏色空间。因此，无论使用多少位来表示顏色，都有許多顏色可能无法再现。例如，在典型的 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''函數使用八叉树量化来创建顏色轨迹。 <ref name="Inkscape">{{Cite web|last=Bah|first=Tavmjong|date=2007-07-23|title=Inkscape » Tracing Bitmaps » Multiple Scans|url=http://tavmjong.free.fr/INKSCAPE/MANUAL/html/Trace-Multi.html|access-date=2008-02-23|archive-date=2023-04-26|archive-url=https://web.archive.org/web/20230426002957/http://tavmjong.free.fr/INKSCAPE/MANUAL/html/Trace-Multi.html|dead-url=no}}</ref>

== 也可以看看 ==

* [[索引顏色|索引色]]
* [[調色盤 (電腦圖形學)|调色板（電腦）]]
* 软件调色板列表-自适应调色板部分。
* [[抖動 (數位訊號處理)|抖色（抖動）]]
* 量化（圖像处理）
* [[图像分割|圖像分割]]

== 参考 ==
{{Reflist}}

== 延伸阅读 ==

* 保罗·S·赫克伯特。[https://web.archive.org/web/20050606233131/http://citeseer.ist.psu.edu/heckbert80color.html 帧缓冲器显示的彩色圖像量化]。 ACM SIGGRAPH '82 论文集。首次发布中值切割算法。
* 丹布隆伯格。[https://web.archive.org/web/20030718130054/http://www.leptonica.com/papers/colorquant.pdf 使用八叉树进行色彩量化]。轻音。
* 奥列格·韦列夫卡。 [http://citeseer.ist.psu.edu/100440.html Windows 系统中使用局部 K 均值算法的彩色圖像量化] {{Wayback|url=http://citeseer.ist.psu.edu/100440.html |date=20061105002242 }}。 ''95 年西方计算机图形学研讨会论文集。''
* J. Puzicha、M. Held、J. Ketterer、JM Buhmann 和 D. Fellner。[https://web.archive.org/web/20111019093114/http://www.iai.uni-bonn.de/III/forschung/publikationen/tr/abstracts/IAI-TR-98-1.abstract-en.html 关于彩色圖像的空间量化]。 （[https://web.archive.org/web/20070609233403/http://www.informatik.uni-bonn.de/III/forschung/publikationen/tr/reports/IAI-TR-98-1.ps.gz 全文 .ps.gz] ）技术报告 IAI-TR-98-1，波恩大学。 1998.

[[Category:图像处理]]