相信很多人都看过 Dribbble 上的 Color Palettes, 如下图。我当年看到后就一直很喜欢,我也想知道这些颜色是怎么抽取出来的。如果知道了所有的像素颜色,如何提取出指定数量的出现次数最多的颜色呢?

Dribbble Color Palettes

去年的时候还专门找过解决方案,当时找到的解决方案有以下两个:

1.ImageMagick

Fred's ImageMagick Scripts: SPECTRUMHIST

这个应该是比较成熟的解决方案了, 可以直接指定颜色数量,色彩空间(colorspace), 压缩等级,排序方式等。核心部分是用的 ImageMagic 的 -colors 参数。我参考这个脚本也写了一个,方便输出 JSON 格式。代码放在 Gist:

https://gist.github.com/cyrilis/eec13e35870a27a0bc96


[2015-3-1 更新:]

已发布为 Node Module:

https://www.npmjs.com/package/colors-palette


2.Color-Thief

第二个可能很多人知道了,Javascript 实现的,地址是: https://github.com/lokesh/color-thief ,Demo 地址:http://lokeshdhakar.com/projects/color-thief/ ,算法后面会讲到。

通过一些图片的测试,我还是觉得 ImageMagick 的更加精准一些。他们是怎么实现的呢?以下是我的个人理解:

算法

在 Wikipedia 上有个关于颜色压缩的介绍:http://en.wikipedia.org/wiki/Color_quantization ,关于核心算法,介绍最全也最容易理解的的相关论文应该是 Anthony H. Dekker 的这篇: Kohonen Neural Networks for Optimal Colour Quantization。里面详细介绍了几种 Color Quantize 的核心原理:见下图:MMCQ(modified median cut quantization),sophisticated Median, Oct-tree,和 Kohonen Neural Networks.

此外,业界对颜色压缩的论文可以找到一大堆,不过大概不超过以上几种。

颜色差异计算公式:

r,g,b 分别为颜色的 RGB 色彩空间里的对应的 red, green, blue 通道的值。

1.MMCQ 算法:

MMCQ 算法是指的是 将色彩空间里的颜色按照密集程度分组,先将整个 ColorSpace 视为一个整体A,然后通过计算颜色差值:

找到 median point,然后切割成两个分组A1 和 A2,然后再找到最大的一个组(比如A1),计算差值找到 median point, 继续切割成A3,A4,现在我们有了三个分组(A2,A3,A4),继续找到最大分组切割,直到达到所需的颜色数量 N。然后得到 N 个分组,这 N 个分组的 median point 的颜色值即为要求的颜色值。颜色比例即为 N 个分组的大小比值。

2.Oct-Tree 算法

Otc-Tree Algorithm 所谓 Otc-tree 算法,跟 MMCQ 算法相反,先将所有颜色分布在 ColorSpace 里,视为一个 Otc-tree, 每个树上的分支有含有pixel 的节点。然后遍历所有节点,根据差异计算找到差异最大的节点,然后对此节点收缩到上级分支,然后再进行下一轮遍历, 直到分支数量等于或者小于所需颜色数量 N。

3.Equal-sized 算法

Equal-sized Algorithm 这个算法就简单了,将颜色按数量均分,median point 的计算方法不是按照差异距离算法,而是按照数量多少来计算,就是说,每个分组的数量是相同的,所以这种算法只能用在要求的颜色数量为2的幂值的情况。而且获得的颜色结果并不准确。个人不推荐这种算法。

4.Kohonen Neural Networks 算法

神经网络算法。这个完全看不懂。希望有理解的可以解释下,不胜感激。

总结

Nick Rabinowitz 将 Leptonica 的 MMCQ 算法 的算法改写成了 Javascript, 上面说到的 Color-thief 就是用的 Nick Rabinowitz 的 核心算法。 除此之外我还找到另外一个 MMCQ 算法的实现,用 TypeScript 写的,相对更容易理解一些。

ImageMagic 的则是用的 Otc-Tree 的算法,官方对此有大概算法解析:http://www.imagemagick.org/script/quantize.php ,解释了 Otc-tree 算法的原理。不明白的可以仔细看看这篇文章。

Otc-Tree 算法相比好像计算量更加大,如果用 Javascript 的话估计不太现实, 我试过自己用 JS 写了一遍,但效率很差,一个 600x800 的图片 筛选10 个颜色要大概10s左右才能取得结果。相比之下 MMCQ 计算量要更小一些。但 C++ 写的 ImageMagick 效率明明很不错,一定是我算法写的不够好,C 和 Js 效率不可能差那么多。

大概就是这些了。水平有限难免有疏漏之处,望大家指正。

Have a nice day!

Reference:

  1. Color quantization using modified median cut
  2. Color quantization using octrees
  3. Computerized simulation of color appearance for dichromats
  4. Optimized Mean Shift Algorithm for Color Segmentation in Image Sequences
  5. An Algorithm for Fast Segmentation of Color Images
  6. Color Reduction Using K-Means Clustering