图像调色板减少

Question

我是第一次玩计算机图形编程。我想将 RGB（24 位）图像转换为索引调色板（8 位）图像（如 GIF）。我最初的想法是使用 k-means（k=256）。

如何为给定图像选择最佳调色板？这对我来说是一次学习经历，所以我更喜欢概述类型的答案而不是源代码。

编辑：抖动目前不是主题。我仅指“简单”的颜色转换，心理视觉/感知模型除外；色彩空间目前也是题外话，尽管在色彩空间之间移动是我首先想到这一点的原因:)

Answer 1

• http://en.wikipedia.org/wiki/Color_quantization
• 八叉
• 树中值切割
• K 均值
• 色域细分
• http://www.cs.berkeley.edu/~dcoetzee/downloads/scolorq /

Answer 2

人们提供的参考链接很好，这个问题有几种解决方案，但由于我最近一直在研究这个问题（完全不知道其他人如何解决它），我用简单的英语提供我的方法：

首先，认识到（人类感知的）颜色是三维的。这从根本上来说是因为人眼有 3 种不同的感受器：红色、绿色和蓝色。同样，您的显示器也有红色、绿色和蓝色像素元素。可以使用其他表示，例如色调、饱和度、亮度 (HSL)，但基本上所有表示都是 3 维的。

这意味着 RGB 颜色空间是一个立方体，具有红、绿、蓝轴。从 24 位源图像来看，该立方体在每个轴上有 256 个离散级别。将图像缩小至 8 位的简单方法是简单地减少每个轴的级别。例如，通过获取红色和绿色值的高 3 位以及蓝色值的高 2 位，可以轻松创建具有 8 个红色和绿色级别、4 个蓝色级别的 8x8x4 立方体调色板。这很容易实现，但有几个缺点。在最终的 256 调色板中，许多条目根本不会被使用。如果图像具有使用非常微妙的颜色偏移的细节，则当颜色捕捉到相同的调色板条目时，这些偏移将消失。

自适应调色板方法不仅需要考虑图像中的平均/常见颜色，还需要考虑颜色空间的哪些区域具有最大的方差。也就是说，具有数千种微妙的浅绿色色调的图像与具有数千个完全相同的浅绿色色调的像素的图像需要不同的调色板，因为后者理想地对该颜色使用单个调色板条目。

为此，我采用了一种方法，生成 256 个桶，每个桶中包含完全相同数量的不同值。因此，如果原始图像包含 256000 个不同的 24 位颜色，则该算法会生成 256 个桶，每个桶包含 1000 个原始值。这是通过使用存在的不同值的中值（而不是平均值）对颜色空间进行二元空间分区来实现的。

用英语来说，这意味着我们首先将整个颜色立方体分成小于中值红色值的像素的一半和大于中值红色值的像素的一半。然后，将所得的每一半除以绿色值，然后除以蓝色值，依此类推。每个分割都需要一个位来指示像素的下半部分或上半部分。经过 8 次分割后，方差已有效地分割为颜色空间中的 256 个同等重要的簇。

在伪代码中：

// count distinct 24-bit colors from the source image
// to minimize resources, an array of arrays is used 
paletteRoot = {colors: [ [color0,count],[color1,count], ...]} // root node has all values 
for (i=0; i<8; i++) {
  colorPlane = i%3 // red,green,blue,red,green,blue,red,green
  nodes = leafNodes(paletteRoot) // on first pass, this is just the root itself
  for (node in nodes) {
    node.colors.sort(colorPlane) // sort by red, green, or blue
    node.lo = { colors: node.colors[0..node.colors.length/2] }
    node.hi = { colors: node.colors[node.colors.length/2..node.colors.length] } 
    delete node.colors // free up space! otherwise will explode memory
    node.splitColor = node.hi.colors[0] // remember the median color used to partition
    node.colorPlane = colorPlane // remember which color this node split on
  }
}

您现在有 256 个叶节点，每个叶节点包含与原始图像相同数量的不同颜色，在空间上聚集在颜色立方体中。要为每个节点分配单一颜色，请使用颜色计数求加权平均值。权重是一种优化，可以改善感知颜色匹配，但并不那么重要。确保独立平均每个颜色通道。结果非常好。请注意，蓝色的划分比红色和绿色少一次是有意的，因为眼睛中的蓝色受体对细微变化的敏感度低于红色和绿色。

还有其他可能的优化。通过使用 HSL，您可以在亮度维度中放置更高的量化而不是蓝色。此外，上述算法将稍微减少整体动态范围（因为它最终会平均颜色值），因此动态扩展结果调色板是另一种可能性。

Answer 3

编辑：
更新为支持 256 种颜色的调色板

如果您需要最简单的方法，那么我建议基于直方图的方法：

Calculate histograms of R/G/B channels
Define 4 intensity ranges
For each channel in intensity range
  Split histogram into 4 equal parts
  For each histogram part
    Extract most frequent value of that part

现在您将拥有 4*4^3=256 种颜色的调色板。将像素分配给调色板颜色时，只需计算像素的平均强度即可查看必须使用的强度区域。之后，只需将 64 种颜色的强度区域之一映射到像素值即可。

祝你好运。

Answer 4

这可能有点晚了，但试试这个：

1. 为图像中的每种颜色制作一组，
2. 根据红色，然后绿色，然后蓝色（如果前面的通道相等）对它们进行排序，（它们现在进入列表）
3. 抑制附近的颜色如果太相似，即 RGB 空间中的距离小于 4。
4. 如果它们仍然太多，则抑制最少使用的颜色。

每次抑制颜色时，您都必须将颜色及其目的地添加到 hash_map 中。