颜色量化

[anjia]

背景

R、G、B 各有一个 byte，所以我们要用 (2^8)^3=2^24 种颜色表示。

场景一：有种视频接口 VGA，同一时刻无法显示超过 256 种颜色。所以，我们需要将 2^24 种颜色，用 256 种颜色来表示。或者，用 n 种颜色来替代 m 种颜色（m>n）。

场景二：PNG 的压缩。PNG 有种编码方式，是使用调色板的编码方案。即使用最多 256 种颜色表示一张图片。如此，每种颜色就都可以用一个 byte 来替代了。

对于 24-bit 的图片来说，颜色空间是连续的（断的地方肉眼几乎不可见）。要将连续的颜色空间，映射到 256 种离散的颜色上，这种将连续变量映射到离散集合上就叫做量化。

颜色量化（color quantization）的方法：

• 流行色算法，popularity algorithm：出现频次最多的n种颜色（可能会丢失出现频次较低但是视觉效果明显的信息）
• 中位切割算法，median cut algorithm
• 八叉树颜色量化，octree（效率高，占内存少。据说选出的调色板最合理）

中位切割算法

算法：

1. 提取整张图片里的所有 RGB，将其转换成一个 RGB 立方体
2. 找到立方体的最长边，从"中位数"处切割。得到两个数量点相同的立方体
3. 对分割成的立方体，重复步骤2，直到得到 256 个（目标个数）立方体
4. 256 个立方体的“质心”，就是要计算的 256 个颜色值

说明：

• 中位数：按序排列之后，取最中间的那个数（或者最中间两个数的平均数）
• 质心：质量中心，是个假想点（质心/距离所有点距离最短的点/平均颜色）
  • 与重心（重力的作用点）不同，质心不一定要在重力场的系统中，除非重力场是均匀的

https://github.com/lokesh/color-thief 用了中位切割算法

getPalette(sourceImage, colorCount=10, quality=10) 返回：[{r,g,b},{r,g,b},...,{r,g,b}]

使用中位切割算法将相似的颜色聚类

• colorCount：决定调色板的大小；返回颜色的数量
• quality：必须是整数，1是最高质量。数字越大，调色板生成的速度越快，错过的颜色可能性也就越大