从颜色列表中最接近的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>但我不知道如何继续使用它.

我也看到了这个,但问题不在于问题的算法方法.

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树.