11

我有一个 MySQL 表，其中存储在 3 列 R、G、B 中的数千个数据点。如何使用欧几里德距离找到最接近给定点（a、b、c）的数据点？

我将颜色的 RGB 值分别保存在表格中，因此每列中的值限制为 0-255。我要做的是通过找到欧几里得距离最小的颜色来找到最接近的颜色匹配。

我显然可以遍历表中的每个点来计算距离，但这不足以有效地进行缩放。有任何想法吗？

4

5 回答 5

3

我认为上述评论都是正确的，但它们 - 在我的拙见中 - 没有回答最初的问题。（如我错了请纠正我）。所以，让我在这里加上我的 50 美分：

您要求一个 select 语句，假设您的表称为“颜色”，并且您的列称为 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;

现在，这个答案有很多警告，因为我不确定我的问题是否正确，所以请确认它是否正确，或者纠正我，以便我可以提供帮助。

于 2012-06-11T05:06:42.263 回答
2

我看到你可以做的第一级优化是将你想要限制查询的距离平方，这样你就不需要对每一行执行平方根。我鼓励的第二级优化是一些预处理，以减轻对每个查询的无关平方的需要（这可能会为大型 RGB 表创建一些额外的运行时间）。您必须进行一些基准测试才能看到，但是通过将值替换为 a、b、c 和 d，然后执行查询，您可以减轻 MySQL 的压力。

乳胶

请注意，最后两行之间的性能差异可以忽略不计。您必须在系统上使用测试查询来确定哪个更快。

我刚刚重新阅读并注意到您是按距离订购的。在这种情况下，应该删除 d 一切都应该移到一侧。您仍然可以插入常量以防止在 MySQL 端进行额外处理。

于 2012-06-08T05:22:55.443 回答
2
  1. 由于您正在寻找最小距离而不是确切距离，因此您可以跳过平方根。我认为平方欧几里得距离适用于此。
  2. 您已经说过这些值的范围在 0-255 之间，因此您可以制作一个包含 255 个值的索引查找表。

这是我在 SQL 方面的想法。r0, g0, 和b0表示目标颜色。该表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
于 2012-06-08T06:16:29.563 回答
0

我相信有两种选择。

正如您所说的那样，您必须遍历整个集合，并比较并检查您最初设置的最大值，该最大值是-1 之类的极低数字。这在线性时间内运行，n 次（因为您只是将 1 点与集合中的每个点进行比较，所以它以线性方式缩放）。

我仍在考虑另一种选择......类似于在远离输入点的地方进行广度优先搜索，直到在搜索点的集合中找到一个点，但这需要更多的思考（我想平均而言，3D 空间必须非常密集才能更有效）。

于 2012-06-08T05:17:23.380 回答
0

如果你遍历每个点并计算距离，不要使用平方根函数，没有必要。最小的平方和就足够了。

这是您要解决的问题。（平面情况，选择所有按ax、y或z轴排序的点。然后用PHP处理）

MySQL 也有一个空间数据库，它可能有这个功能。虽然我并不积极。

于 2012-06-08T05:24:45.300 回答