FLANN в opencv работает слишком медленно

Question

У меня есть набор точек cloub (количество точек cloub≈2million). Я хотел бы найти ближайшего k-соседа для каждой точки в точке cloub. Я сделал что-то вроде этого

flann::Index flann_index(data_m, flann::KDTreeIndexParams(),cvflann::FLANN_DIST_EUCLIDEAN);// create the object of flann 
    for (int i = 0; i < numberOfPointsInPointCloub; i++){ 
    flann_index.knnSearch(data_m.row(i), indices, dists,num_of_knn); //each row is a new set of point in 3D 
    ..//save the results "dist" and "indices" in somewhere else 
} 

Но это работает очень медленно. В цикле for он работает 1000 раз в течение 20 секунд, что очень медленно. Я использую это неправильно? Или есть какой-нибудь метод, чтобы я мог его ускорить?

Обновление: Точка запроса, которую мне нужно найти, - это точно точка, используемая для построения дерева. Мне нужно найти ближайший соседний k для каждой точки в дереве, таким образом, я беру точку из каждой строки данные и выполнить knnSearch.

Answer 1

У меня были подобные проблемы в последнее время. Вот некоторые идеи:

Во-первых, убедитесь, что вы находитесь в режиме освобождения. Неоптимизированный код может серьезно повлиять на производительность. Мой последний тест показал улучшение в 70 раз после переключения с отладки на выпуск кода.

Во-вторых, вы используете значение по умолчанию для flann :: KDTreeIndexParams(), что составляет 4 дерева. Для скорости вы можете уменьшить это до 1. Это может снизить точность, но может помочь в производительности.

В-третьих, по крайней мере, в последних версиях OpenCV существует пятый параметр для функции knnSearch, а именно: SearchParams(). Его первый параметр конструктора, который «определяет количество раз, когда дерево (деревья) в индексе должно быть рекурсивно пройдено», может быть изменено, чтобы сбалансировать производительность с точностью. Подробности см. На странице OpenCV documentation.

В-четвертых, кажется, что вы ищете соседние точки запроса за раз. Попробуйте запустить с несколько точек запроса за раз. Возвращаемые параметры «индексы» и «dists» будут матрицами, где каждая строка r представляет соседние точки в индексе r (а первый элемент каждой строки представляет собой точку запроса).

И, наконец, если это еще не достаточно быстро, возможно, проверьте реализацию KdTree в VCG ibrary. До сих пор я видел прирост производительности режима версии> 2x поверх FLANN OpenCV. Вы также можете попробовать распараллеливать, хотя я бы пошел по этой дороге только после того, как вы вытащили как можно больше производительности из своей непараллельной версии.