中位切分法颜色量化

首先举两个例子。

有一种视频接口叫VGA，这种视频接口有一个最大的缺点，就是同一时刻无法显示超过256种颜色。而对于一张true-color的图片，R、G、B都是有1个byte标示，因此一张true-color的图片可能有2^24种颜色。这远远超过了VGA可以同时展示的颜色数量。

我们都知道有一种图片格式叫PNG(
PNG格式分析与压缩原理)。它的编码方案中，有一种使用调色板的编码方案。调色板上最多有256种颜色。这样每一种颜色都可以用一个byte的索引值代替。如果将一副超过256种颜色的png图使用调色板的编码方式，那么就可以明显的减少图片的体积。

那么如何将2^24种颜色用256种颜色表示呢？或者说，如何将m种颜色使用n种颜色来代替表示(m>n)。这就是这篇文章主要讨论的问题。

首先，如下图所示，RGB可以映射到三维空间中，R代表X轴，G代表Y轴，B代表Z轴。这样，任意一个RGB的组合都可以在空间中以一个点表示。

对于一个24-bit的图片来说，通常来说颜色空间是连续的，因为颜色之间的最小差异是几乎不可能察觉的。现在，这个连续的颜色空间要被映射到256种离散的颜色上。将一个连续的变量映射到离散的集合上，就叫做量化。

有了上面这些说明后，现在有一张颜色很多的图片。图片上所有的点都被映射到一个空间中的立方体上。因为图片上点的分布一般不是均匀的，那么就可能有很多个点的聚集块。一般来说，聚集的越密，代表这些点的颜色越接近，那么如果我们将这些聚集块的点用聚集块中心点的颜色来表示，这样就可以将很多接近的颜色用一种颜色来代替。其实，这个过程跟聚类是很相似的。只不过一般的聚类算法都是无监督的机器学习，效率要较差。而中位切分法则可以用很快的速度完成这样的聚类。

中位切分法

中位切分法用简短的话描述：将一个图片对应的RGB立方体切割成目标数量的紧凑的RGB立方体，然后用立方体的质心值代表立方体内所有点的值。重复这个过程直到得到想要的颜色数量。

这里假设我们要获取256个颜色。详细的流程如下：

• 将整张图片转换成一个RGB立方体
• 找到立方体的最长边，从中位数的地方开始切割。得到两个包含相同数量点的立方体。
• 对分割成的立方体重复上一步的切割过程直到得到256个立方体。
• 256个立方体的质心就是要计算的256个颜色值。

用一个例子来说明（为了简单，这里没有B颜色空间）,这里有6种颜色，共14个点。想要得到4中颜色输出。

1. 初始情况

Color	(r,g)-coordinates	Count
C0	(20,40)	3
C1	(40,20)	2
C2	(5,60)	4
C3	(50,80)	2
C4	(60,30)	1
C5	(80,50)	2

2. 3次切割后的情况

Cube	HistPtr.lower	HistPtr.upper	Colors Enclosed	Cube Centroid
A3	0	0	C0	(20,40)
B3	1	1	C2	(5,60)
A2	2	3	C1,C4	(46.7,23.3)
B2	4	5	C5,C3	(65,65)

具体流程图如下：

第一次：最长边是Ｒ,中位数是（20 + 40) / 2 = 30。从30处切割。得到收缩后的矩形。左边的矩形为A1,右边为B1。
第二次: 切割B1的R边，得到A2,B2
第三次: 切割A1的R边，得到A3,B3

这个时候我们已经有4个矩形了。

这里我们有两个颜色映射方式。第一种是快速映射，以矩形的质心作为映射后的颜色值。第二种是最佳映射，得到和其他点的距离和最短的点作为映射后的颜色值。

中位切分法的实现

1. 递归方式。在描述的时候，我们RGB块描述成递归的方式。如下

Split(Cube){
  if (ncubes == 4) return;
  find longest axis of Cube;
  cut Cube at median to form CubeA, CubeB;
  Split(CubeA);
  Split(CubeB);
}

但是这种递归切割的方式是有问题的。结果如下图

在递归情况下，B1将一直不会被处理。

2.为了解决1中的问题。我们可以设定一个最大深度(level)。比如我们要得到4个输出颜色。那么log 2 4=2。最大深度应该是2。当切割到最大深度时，我们就不再往下切割，转而切割那些还未被处理的更大的区域。

maxlevel = 2;
Split(Cube,level){
  if (ncubes == 4) return;
  if (Cube's level == maxlevel) return;
  find longest axis of Cube;
  cut Cube at median to form CubeA, CubeB;
  Split(CubeA, level+1);
  Split(CubeB, level+1);
}

3. 但是这样又会有新的问题出现。如果一个立方体中只有一种颜色（实际上此时只有一个点)，不能再往下切割。因此我们需要一种方案去解决这个问题。这里可以维持一个包含所有立方体的数组，然后根据优先级排序切割。优先级可以按照level从小到大排序，但是所有颜色数量为1的立方体都会被忽略。这样每次切割前对这个数组做一次排序，取出优先级最高的立方体进行切割。直到切割出指定数量的立方体或者所有的立方体颜色都为1。

build initial cube from histogram;
set initial cube's level to 0;
insert initial cube in list of cubes;
ncubes = 1;
while (ncubes < maxcubes){
  search for Cube with smallest level;
  find the longest axis of Cube;
  find the median along this axis;
  cut Cube at median to form CubeA, CubeB;
  set CubeA's level = Cube's level + 1;
  set CubeB's level = Cube's level + 1;
  insert CubeA in Cube's slot;
  add CubeB to end of list of cubes;
  ncubes = ncubes + 1;
}

实践

1. 使用中位切分法提取图片的主题色

2. 使用中位切分法压缩图片

中位切分法的实现的go语言版本:joyme123/MedianCut。点击这里进行效果预览

参考文献

Median-Cut Color Quantization

前端图片主题色提取