algorithm - 颜色列表中最接近的 RGB 颜色

Question

我在接受采访时被要求为以下问题创建一个有效的算法:

输入:

我们有一个 RGB 颜色列表。 3坐标表示的每种颜色<x,y,z>介于 0 到 255 之间。此列表永远不会改变。

我们每次都会获得一些额外的颜色(不一定必须来自上面的列表)，我们需要从列表中返回最接近(距离)的颜色到额外的颜色。

注意事项:

1. 我们可以对颜色列表进行一些预处理，因为该列表永远不会改变。

2. 颜色之间的距离定义为: d = ((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2)^1/2

示例:

令:列表:{<1,1,1>,<1,0,1>,<2,2,2>,<0,1,0>}附加颜色:<0,0,0>

结果:到<0,0,0> 的最小距离是<0,1,0> .

我试图解决这个问题:

1. 显然我们可以进行预处理并保留世界上的所有颜色对并节省距离，我们可以在 O(1) 运行时间中获得解决方案，但需要大量内存 (255^3*n)

2. 最天真的解决方案是遍历列表并计算列表中每种颜色与附加颜色之间的距离，并返回距离最小的颜色。需要 O(n)其中 n 是颜色列表的长度。

我试着用 x、y、z 坐标对列表进行某种排序，并保留 3 个排序列表或按到 <0,0,0> 的距离排序。但我不知道如何继续。

我还看到了this但问题不在于解决问题的算法方法。

Answer 1

现在预计算一个完整的查找表并不是不可想象的。只要您的引用颜色少于 256 种，所需的数组就有 256³(不是 255³)个条目，即 17 MB。 (65536 色的两倍。)但您确实需要充分的理由来使用这样的设备。

如果颜色的数量是合理的，那么朴素的解决方案是完全可以接受的。

对于更多的颜色(比如 10 种以上)，有几种可行的解决方案:

• 一棵 kD 树(其中 k=3)；查询时间接近 O(Log N)；

• 一个八叉树；如果颜色不聚类，查询时间接近 O(Log N)；

• 一个网格(例如 4096 个大小为 16 的单元格)；查询时间 O(N)，但在幸运的情况下，渐近常数可以做得很小。

计算几何工具可能建议将 3D Voronoi 图组合到 3D 分割中的定位器，但这些工具非常复杂且很难实现，即使它们将支持有保证的 O(Log N) 查询时间。

我个人更喜欢 kD 树。