查看“Colour Quantisation”的源代码

{{Stub}}
[[Category:Graphical UI]]

在图形操作系统环境中，有时需要在显示设备上显示图像。  如果显示设备无法表示图像中的所有颜色，则必须有一种机制，将图像中的颜色映射到设备调色板中最接近的可显示颜色。  这种颜色映射的一般术语是颜色量化（色彩量化，Colour Quantisation）。  颜色量化器是系统中负责执行此操作的部分。

在本文中，源图像被认为是每像素24位的位图图像，红色、绿色和蓝色分量各为8位。  这通常是最糟糕的情况（在48位摄影处理之外），任何其他情况都可以这样表示。

虽然颜色量化本身可以用来产生图像的合理表示，但大多数应用程序可能想要考虑将[[Dithering|抖动仿色]]应用于图像以产生更准确的整体再现。

“颜色量化（或色彩量化Colour Quantisation）”一词还指的是从保留了大部分颜色细节的图像中计算低调色板的过程，但这里不讨论这种用法。

''免责声明：  这篇文章并不是为了给你这个问题的最终答案，也不是为了给你提供最好的解决方案，而是为了介绍这个概念，并希望提供一些在大多数情况下都能奏效的东西。  这里介绍的方法应该能让你的项目在短期内克服这个障碍，然后在将来被替换和改进。”

== Non-paletted量化 ==

如果您的显示设备是非调色板类型，但它不能显示所有所需颜色，例如每通道只有5个像素的15位显示器，颜色量化是简单的，但您可能仍然想考虑[[Dithering|抖动仿色]]图像。

=== 颜色收缩（Colour Contraction）===

简单地说，为了将24位颜色映射到较小的颜色空间，可以使用逻辑和位移位来保留源颜色中每个通道中的最高有效位，并将其压缩到目标空间中的颜色中。

例如，给定一个24位颜色，其位的形式如下
    { R0, R1, R2, R3, R4, R5, R6, R7, G0, G1, G2, G3, G4, G5, G6, G7, B0, B1, B2, B3, B4, B5, B6, B7 }
（其中R0是八位红色分量中的最高有效位，R7是最低有效位）， 通过从每个通道中移除最低有效的三位，可以将其制作成15位颜色，给出以下结果
    { R0, R1, R2, R3, R4, G0, G1, G2, G3, G4, B0, B1, B2, B3, B4 }.

可以根据需要考虑用于向上或向下“舍入”结果值的第六位的值，而不显著影响图像质量。

=== 颜色扩展（Colour Extension） ===

通过上述类似的方法，在低位加入额外的位，把低位的颜色移动到高位。  例如，针对15位值
    { R0, R1, R2, R3, R4, G0, G1, G2, G3, G4, B0, B1, B2, B3, B4 }
通过在每个通道中插入三个零位，可以将其转换为24位颜色，从而产生
    { R0, R1, R2, R3, R4, 0, 0, 0, G0, G1, G2, G3, G4, 0, 0, 0, B0, B1, B2, B3, B4, 0, 0, 0 }.

==Paletted 量化==

针对目标调色板的颜色量化是这项技术最有价值的应用场景。（译者注：指目标调色板可用颜色数有限）  为了尽可能准确地再现图像，1600万种（24位颜色）可能的颜色中的任何一种都可能需要处理并显示为调色板颜色。  如果只有少量颜色可用，例如VGA Mode 12h屏幕（译者注：该模式提供320×200×16色）上提供的16种颜色，那么颜色量化的好方法至关重要。  各种技术可以扩展到生成灰度甚至半色调（黑白）颜色表示。

=== 欧几里德距离（Euclidean Distance）===

颜色量化最基本的方法是欧几里德距离技术。  对于图像中的每个颜色像素，欧几里德公式（毕达哥拉斯（勾股）定理的扩展）可以依次应用于调色板中的每个颜色，以确定哪个调色板颜色最接近所需颜色。  然后，该调色板颜色用于表示像素。

在伪代码中，算法如下所示：
    将C定义为源颜色
    将ND定义为迄今为止最近的距离
    将NP定义为迄今为止最接近的调色板条目
    
    将ND设置为一个较大的值
    对于每个调色板条目P
    	计算D为（C.R-P.R）的平方加上（C.G-P.G）的平方加上（C.B-P.B）的平方
    	如果D小于ND
    		设置ND=D
    		设置NP=P
    	如果结束
    下一轮循环
    使用NP作为结果

虽然该算法的实现非常简单，但该算法必须依次使用三个平方运算符将源图像中的每个像素与目标调色板中的每个颜色进行比较，这意味着它的操作非常缓慢。  （请注意，可以省略欧几里德算法要求的平方根运算符，因为它不会影响结果。）

使用欧几里德距离的另一个主要问题是，它认为红-绿-蓝颜色空间是具有线性分布的规则立方体，但事实并非如此。  例如用欧几里德距离算法被表示颜色作为灰度，纯绿色和纯蓝色将得到相同的灰色阴影，尽管绿色是大约比蓝色轻七倍。  如果想尝试的人也许可以修改这个算法，以考虑亮度的变化。

===预先计算的映射===

上述欧几里德距离法的一个逻辑改进是预先计算一组可能的源颜色的最近调色板颜色表。  无论何时设置或更改显示调色板，都可以计算此表，并提供颜色量化器的快速查找，以显著提高性能。

查找表的每个索引将代表RGB颜色立方体中规则网格上的一个点，相应的值将存储最近可显示调色板条目的索引。  网格中计算的点越多，量化的准确性就会提高，但存储的内存越多，计算的处理时间也越多。

这种情况的极端情况是使用一个点网格来表示24位颜色空间的所有可能组合。  这样做需要1600万个数组元素（16Mb，每个调色板索引一个字节），计算时间与使用欧几里德算法量化4096x4096像素的图像相同。  而另一个极端，使用太少的元素将导致不准确的映射。

下表详细介绍了各种网格大小选项和生成的表格大小：
{| {{wikitable}}
! 每通道比特数
! 映射表条目
! 每个调色板条目的计算条目
! 讨论
|-
| 1 || 8 || 0.5 || 太少，无法使用，甚至不能映射到每个调色板颜色。
|-
| 2 || 64 || 4 || 最小合理的表尺寸，将作为一个快速的程序。
|-
| 3 || 512 || 32 || 合理的表。在较少的内存中提供良好的映射。
|-
| 4 || 4096 || 256 || 非常精确的表格。可以整齐地放入一页内存中。
|-
| 5 || 32768 || 2048 || 16种颜色的不合理精确表格。需要使用八个页大小。
|-
| 8 || 16777216 || 1048576 || 16种颜色的表非常精确。使用16Mb。
|}

从这个表来看，每个通道存储3位似乎是16色模式12h屏幕的良好开端。

由于表中的每个索引项代表RGB颜色空间中的一个点，因此计算颜色映射表非常简单：
    分配颜色表
    循环颜色表中的条目数
    	计算网格中与此数组索引对应的颜色
    	使用欧几里德距离计算找到最接近颜色的调色板条目
    	将调色板条目存储到相应的数组元素中

一旦计算出表，就可以一直存储它，并且不需要重新计算，除非发生调色板条目的更改。

当需要量化器在显示设备上表示图像时，应用以下算法：
    循环源图像中的每个像素
    	通过颜色收缩（如上所述）从源颜色计算网格中的等效颜色
    	使用网格颜色作为索引访问颜色表
    	使用数组元素内容作为该颜色的调色板条目。

==另见==
===外部链接===
*[http://en.wikipedia.org/wiki/Color_quantization Wikipedia page on the subject]