我写了一个k均值聚类算法和一个颜色量化算法。它们在结果方面按预期工作,但我想使其更快。在这两种实现方式中,我都需要解决一个问题:在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计算)

最佳答案

有多种数据结构可用于有效的最近邻居查询。对于3d,kdtree的效果非常好,平均每个查询的复杂度为O(log n),这将改善您当前的O(n)。

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

另一种方法:

我们可以尝试冒险在某些点上进行额外的计算,以换取其他点上的更少。该方法应在以下假设下很好地起作用:

  • 群集之间的距离很远
  • 一个点和相邻点之间的距离很短

  • 我认为这些适用于您的情况,因为您的群集几乎没有颜色,并且您的点来自真实图像,该图像在相邻像素之间往往具有相似的颜色。

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

    现在,对于新点P2,在与所有群集进行比较之前,我们将检查与P2最接近的群集是否在堆中。仅当从堆到P2的任何群集之间的距离
    您将需要尝试不同的k值,以查看它是否有所改善。对于K = 2的情况,可能值得避免增加堆的复杂性,而只需使用变量即可。

    08-05 18:50