使用MySQL,在三维空间中查找欧几里得距离的最有效方法是什么?

11
我有一个MySQL表,其中包含存储在3个列R、G、B中的数千个数据点。如何使用欧几里得距离找到最接近给定点(a,b,c)的数据点?
我将颜色的RGB值分别保存在一个表中,因此每个列的值限制在0-255之间。我正在尝试做的是通过找到具有最小欧几里得距离的颜色来找到最接近的颜色匹配。
我可以显然地遍历表中的每个点来计算距离,但这不足以高效扩展。有什么想法吗?

3
如果您确实在谈论颜色,那么您应该不要在RGB空间中使用欧几里得距离。 - AakashM
5个回答

3

我认为以上评论都是正确的,但在我看来它们并没有回答原问题。(如果我错了请纠正我)所以,让我来补充一下我的看法:

你正在寻找一个select语句,假设你的表名叫做“colors”,你的列名分别是r、g和b,它们都是介于0到255之间的整数,而你正在寻找与给定值最接近的值,在你的表中,比如:rr、gg、bb,那么我建议尝试以下方法:

select min(sqrt((rr-r)*(rr-r)+(gg-g)*(gg-g)+(bb-b)*(bb-b))) from colors;

现在,我会给出这个答案,但需要说明一些限制,因为我不确定我是否正确理解了你的问题,请确认我的理解是否正确,或者纠正我,以便我能够提供帮助。


嗯?啥?我本来想打星号(*)来做乘法,结果代码变成了斜体,哈哈哈...所以,在(rr-r)(rr-r)的括号里应该是一个星号。同样的,(gg-g)(gg-g)也是一样,哈哈哈...这是自1980年代在大型机上使用的LaTeX格式风格!!!(是啊,我是个老家伙)... - David Svarrer
感谢您在 SQL 中回答了我的问题 - 尽管我想知道这是否非常高效。 - soulkphp

2
我看到你可以进行的第一级优化是将要限制查询的距离平方,这样你就不需要为每行执行平方根。我鼓励你进行的第二级优化是一些预处理,以减轻每个查询的多余平方需求(对于大量RGB表可能会增加额外运行时间)。你需要进行一些基准测试来确定,但通过替换a、b、c和d的值,然后执行查询,你可以减轻MySQL的一些压力。
请注意,最后两行之间的性能差异可能是微不足道的。你需要在系统上使用测试查询来确定哪个更快。
我刚刚重新阅读并注意到你正在按距离排序。在这种情况下,应删除d并将所有内容移动到一侧。你仍然可以插入常量以防止MySQL端的额外处理。

2
  1. 由于您正在寻找最小距离而不是精确距离,因此可以跳过平方根。我认为平方欧几里得距离适用于这里。
  2. 您已经说过值介于0-255之间,因此可以使用255个值的索引查找表。

以下是我在SQL方面的想法。r0g0b0表示目标颜色。表Vector将保存上述第2点中提到的平方值。该解决方案将访问所有记录,但通过排序并仅选择第一行,结果集可以设置为1。

select 
    c.r, c.g, c.b,
    mR.dist + mG.dist + mB.dist as squared_dist
from 
    colors c,
    vector mR,
    vector mG,
    vector mB
where
    c.r-r0 = mR.point and
    c.g-g0 = mG.point and
    c.b-b0 = mB.point
group by
    c.r, c.g, c.b

我必须说,我认为你的解决方案是不正确的,user845279... 如果你把这三个值相加,由于数学中加法的交换律,你会发现10 + 50 + 80 = 140,但是10 + 120 + 10也是一样的,1 + 138 + 1也是一样的,或者80 + 50 + 10也是一样的。如果你至少使用距离公式,用每个分量的平方和的平方根,那么你将得到一个更好的三维空间距离公式,该空间由X-Y-Z立方体(R-G-B)组成,每个维度的范围在0到255之间... - David Svarrer

0

我认为有两个选项。

你必须要么像你说的那样遍历整个集合并与你最初设置的一个不可能低于-1的最大值进行比较和检查。这将在线性时间内运行n次(因为你只比较一个点与集合中的每个点,所以这是线性的)。

我还在考虑另一个选择……类似于从输入点开始进行广度优先搜索,直到在搜索点处找到集合中的一个点,但这需要更多的思考(我想3D空间必须相当密集才能平均更有效率)。


0
如果您遍历每个点并计算距离,请不要使用平方根函数,这是不必要的。最小平方和就足够了。
这是您正在尝试解决的问题(平面情况下,按x、y或z轴选择所有点进行排序。然后使用PHP对它们进行处理)。
MySQL还有一个空间数据库,可能会有这样的功能。我不确定。

我也看了一下维基百科上关于最近点对问题的页面,但那是将所有点与其他所有点进行比较以找到每对之间的最小距离。更不用说我认为您需要根据三个维度中的两个进行排序,而排序会影响效率。此外,似乎空间数据库只处理二维点,尽管我没有使用过。 - shaunhusain

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接