基于欧几里得距离调色板的快速检索算法

图像颜色量化是一项非常有趣的技术，为此我花了一个月的时间研究它，其中调色板检索是颜色量化的步骤之一。调色板检索就是给定n个颜色的列表A(根据图像生成或者自己选定)，输入颜色x，输出A中距离x最近的颜色的索引。这里的距离不一定要用欧几里得距离，但欧几里得距离是效果最好的，同时也难以优化。本文将介绍一种基于欧几里得距离调色板的优化算法，当n=256时，平均比较3~4次就可以找出最近颜色的索引。

有经验的小伙伴应该可以想到在RGB空间建立n个泰森多面体，然后把RGB空间切分成若干个立方体，每个立方体只要比较包含的泰森多面体对应的颜色。这种做法是最优的，但是实现代价太大(可能是我比较蒻才这样觉得)。下面我们讨论另一种方法，这种方法不是最优的，也就比最优差那么一点点，但是实现简单。

首先我们将RGB空间(256*256*256)均匀切分成K*K*K个正方体(下文称Cube)，K的推荐值是16。然后把调色板的n个颜色分别放入对应的Cube内，有些Cube可能没有任何颜色，有些可能有好几个颜色。最终我们的目标是为每个Cube建立索引集，当有颜色输入时，遍历对应Cube索引集里所有颜色，找出与输入最近的颜色编号并输出。一开始所有Cube的索引集都是空的，接下来对每个Cube进行下面的操作：

(1) 若Cube内不存在任何颜色，则找到距离Cube最近的颜色；否则在Cube内找到与Cube最远距离值最大的颜色。两种情况找到的颜色都设为a，并把a加入Cube的索引集。

(2) 枚举a的a与Cube两倍最远距离半径内的颜色(不包括a)，当前枚举出来的颜色设为e。

    (2.1) 找到Cube索引集中距离e最近的颜色，设为b。

    (2.2) 若b与e的中垂面与Cube相交，那么e加入索引集。

(3) Cube的索引集建立完毕。

（颜色与Cube的最远距离：颜色分别与Cube的8个顶点距离的最大值）

图解算法步骤（原谅我只会画2d，但在3d上原理一样）：

上述步骤中，有3个小问题有一些优化技巧，分别是：

问题1：如何快速找到距离Cube最近的颜色？

问题2：如何快速枚举某颜色指定半径内的所有颜色？

问题3：如何快速判定两个颜色的中垂面与Cube相交？

为了解决问题1和问题2，我们创建一个n*n的二维数组，数组第i行第j列的内容为：与编号为i的颜色的第j个最近颜色的编号与距离。（i和j都是从0开始）

例如有调色板：

[(0,0,0), (2,3,3), (1,1,1), (6,6,6)]

那么建立的二维数组即：

考虑到性能，实际代码中的距离不需要开平方，并且使用整型，因此上述例子的距离没有开平方。

问题2的解法可以很直观的看出来，因此不过多解释了。枚举编号i的颜色半径r内的所有颜色，遍历数组第i行，如果距离大于等于r就退出循环。但是如何解决问题1就没有那么直观了，毕竟从数组中不能直接看出颜色和Cube的距离关系。

问题1的解法：

(1) 从与当前Cube相邻的Cube中找到任一颜色，设为a，并求出a与当前Cube的距离d1和最远距离d2；若找不到直接结束该算法，改用遍历所有颜色的方法。

(2) 枚举a两倍d2半径内的所有颜色(不包括a)，当前枚举出来的颜色设为b。

    (2.1) 若b到Cube的距离小于a到Cube的距离，那么a←b，d1←b到Cube的距离，d2←b与Cube的最远距离，停止枚举然后跳转到(2)开始新的枚举。

(3) a即所求的与Cube距离最近的颜色。

问题3的解法：

很容易发现若存在某个向量vi与向量u的点积小于0（在这个算法中是这样，通常情况下要同时出现正负号才能判断为相交），那么中垂线（三维里是中垂面）与正方形（Cube）相交。

那么为什么是中垂面，为什么要判断与Cube相交？

我们先来看一张图

a与b的中垂线把平面分割成了两部分，其中红色区域到点a的距离是最近的，蓝色区域到点b的距离是最近的，因此很明显x1更接近b，x2更接近a。如果中垂面和Cube相交，那么说明Cube中有部分区域要离b更近，因此要将b加入到索引集。

之前有说过该算法不是最优的，原因是当索引集颜色数≥2时，有可能出现如下情况：

按照算法流程，c是要加入索引集的，想要最优结果的话那么c不应该加入索引集，因为很明显蓝色区域距离b更近而不是c。不过这种情况是个低概率事件，因此可以不用管。

另外需要注意的是，如果距离不开平方，那么算法中描述的各种两倍距离，实际上代码中要乘以4。

该算法在我的AMD A10-5750M cpu(2.5GHz)上单线程运行，运行耗时情况如下。

（下面的图已经和本文无关了，只是欣赏一下图像颜色量化的效果）

有空再更新颜色量化吧