c++ - 最近点算法 |如何改进？

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(log n)，这将改善您当前的 O(n)。

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

另一种方法:

我们可以尝试冒险对某些点进行额外的计算，以换取对其他点进行更少的计算。此方法应适用于以下假设:

• 一个簇与另一个簇之间的距离很远
• 一个点与相邻点之间的距离很小

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

对于每个点，创建一个堆。不是存储最近的集群，而是存储在 max heap 中最近的 k 个簇。当您移动到下一个点时，我们可以使用此信息。我们将此点称为 P 及其第 k 个最接近的簇 C。

现在对于一个新点 P2，在与所有集群进行比较之前，我们将检查离 P2 最近的集群是否在我们的堆中。仅当来自堆的任何集群与 P2 之间的距离 <= distance(P, C) - distance(P, P2) 时，这才为真。当这成立时，我们可以只检查我们的堆而不是所有集群。如果不成立，我们将与所有人进行比较并重建我们的堆，P 将是 P2。

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