Алгоритм ближайшей точки |Как это улучшить?

Question

Я написал алгоритм кластеризации 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)

Answer 1

Существует несколько структур данных для эффективных запросов ближайших соседей. Для 3d kdtree работает очень хорошо и имеет сложность O (log n) для каждого запроса в среднем, что улучшило бы ваше текущее O (n).

Таким образом, с помощью этой структуры вы можете добавить к ней все свои точки из кластеров, а затем для каждой точки в точках вы можете использовать структуру для запроса ближайшей точки. Для вашего конкретного случая достаточно статического kdtree, так как вам не нужно обновлять точки.

Другой подход :

Мы можем попытаться рискнуть сделать дополнительные вычисления для некоторых пунктов в обмен на меньшее на другие. Этот метод должен хорошо работать со следующими допущениями:

• Расстояние между кластером и другим далеко
• Расстояние между точкой и соседней точкой невелико

Я думаю, что это применимо к вашему случаю, потому что у ваших кластеров мало цветов, а ваши точки получены из реального изображения, которое имеет тенденцию иметь похожие цвета между соседними пикселями.

Для каждой точки создайте кучу. Вместо того, чтобы хранить ближайший кластер, сохраните в max heap ближайший k кластеров. Когда вы переходите к следующему пункту, мы можем использовать эту информацию. Назовем эту точку P и ее k-й ближайший кластер C.

Теперь для новой точки P2, перед сравнением со всеми кластерами мы проверим, находится ли ближайший кластер к P2 в нашей куче. Это может быть верно только в том случае, если расстояние между любым кластером от кучи и P2 равно <= distance (P, C) - distance (P, P2). Когда это верно, мы можем проверять только в нашей куче, а не во всех кластерах. Когда это не так, мы сравниваем все и перестраиваем нашу кучу, а P будет P2. </p>

Вам нужно будет попробовать разные значения k, чтобы посмотреть, улучшится ли он. В случае K = 2, возможно, стоит избегать дополнительной сложности кучи и просто использовать переменные.