最近点算法|如何改进

Question

我写了一个k-means聚类算法和一个颜色量化算法。就结果而言，它们的效果如预期，但我想让它们更快。在这两种实现中，我都需要解决一个问题：在3D空间中有两个点阵列，然后对于第一个阵列的每个点，你需要从第二个阵列中找到最近的点。我是这样做的：

size_t closest_cluster_index;
double x_dif, y_dif, z_dif;
double old_distance;
double new_distance;
for (auto point = points.begin(); point != points.end(); point++)
{
//FIX
//as suggested by juvian
//K = 1
if (point != points.begin())
{
auto cluster = &(clusters[closest_cluster_index]);
r_dif = cluster->r - point->r;
g_dif = cluster->g - point->g;
b_dif = cluster->b - point->b;
new_distance = r_dif * r_dif + g_dif * g_dif + b_dif * b_dif;
if (new_distance <= std::sqrt(old_distance) - ColorU8::differenceRGB(*(point - 1), *point))
{
old_distance = new_distance;
//do sth with closest_cluster_index;
continue;
}
}
//END OF FIX
old_distance = std::numeric_limits<double>::infinity();
for (auto cluster = clusters.begin(); cluster != clusters.end(); cluster++)
{
x_dif = cluster->x - point->x;
y_dif = cluster->y - point->y;
z_dif = cluster->z - point->z;
new_distance = x_dif * x_dif + y_dif * y_dif + z_dif * z_dif;
if (new_distance < old_distance)
{
old_distance = new_distance;
closest_cluster_index = cluster - clusters.begin();
}
}
//do sth with: closest_cluster_index
}

我该如何改进？(我不想让它多线程或由GPU计算(

Answer 1

有多种数据结构可用于高效的最近邻查询。对于3d，kdtree工作得非常好，平均每个查询的复杂度为O(logn(，这将改善您当前的O(n(。

因此，使用此结构，您可以将集群中的所有点添加到其中，然后对于点中的每个点，您可以使用该结构来查询最近的点。对于您的特定情况，静态kdtree就足够了，因为您不需要更新点。

另一种方法：

我们可以冒险在某些点上做额外的计算，以换取在其他点上做更少的计算。该方法应能很好地满足以下假设：

• 一个集群与另一个集群之间的距离很远
• 点和相邻点之间的距离较低

我认为这些适用于您的情况，因为您的聚类颜色很少，并且您的点来自真实图像，而真实图像在相邻像素之间往往具有相似的颜色。

对于每个点，创建一个堆。不要存储最近的集群，而是在最大堆中存储最近的k个集群。当您转到下一点时，我们可以使用这些信息。让我们把这个点称为P和它的第k个最近的簇C。

现在，对于新的点P2，在与所有集群进行比较之前，我们将检查离P2最近的集群是否在我们的堆中。只有当来自堆的任何集群与P2之间的距离<=距离(P，C(-距离(P、P2(。当这种情况成立时，我们只能在堆中进行检查，而不能在所有集群中进行检查。当它不是真的时，我们与所有的进行比较并重建我们的堆，P将是P2。

你需要尝试不同的k值，看看它是否有所改善。对于K=2的情况，可能值得避免堆的复杂性，只使用变量。