Итеративный алгоритм ближайших точек

Итеративный алгоритм ближайших точек (англ. Iterative Closest Point, ICP) — это вычислительный метод, используемый для минимизации разницы между двумя облаками точек, обычно в трёхмерном пространстве. Алгоритм предназначен для нахождения оптимального преобразования (поворота и переноса) одного облака точек относительно другого, чтобы максимизировать их совмещение. ICP широко применяется в задачах компьютерного зрения, робототехники, обработки трёхмерных сканов и реконструкции объектов.

История

Итеративный алгоритм ближайших точек был независимо предложен несколькими исследователями в начале 1990-х годов. Наиболее известные публикации принадлежат Чену и Медьони (1992), а также Беслу и Маккею (1992). Алгоритм быстро стал стандартным инструментом для регистрации трёхмерных данных благодаря своей простоте и эффективности. В последующие годы было разработано множество модификаций, направленных на повышение скорости сходимости, устойчивости к шумам и выбросам, а также на работу с частично перекрывающимися облаками точек.

Основные принципы

Постановка задачи

Пусть имеются два облака точек: исходное (source) — набор точек \( P = \{p_1, p_2, \dots, p_n\} \) и целевое (target) — набор точек \( Q = \{q_1, q_2, \dots, q_m\} \). Задача заключается в нахождении такого преобразования \( T \) (в трёхмерном случае — жёсткого преобразования, состоящего из матрицы поворота \( R \) и вектора переноса \( t \)), которое минимизирует сумму квадратов расстояний между точками из \( P \) и их ближайшими соответствиями в \( Q \):

\[ E(R, t) = \sum_{i=1}^{n} \| R p_i + t - q_{j(i)} \|^2 \]

где \( q_{j(i)} \) — точка из \( Q \), ближайшая к \( R p_i + t \).

Алгоритм

ICP является итеративным методом, который на каждом шаге выполняет два основных этапа:

1. Поиск соответствий: для каждой точки из исходного облака находится ближайшая точка в целевом облаке (обычно с использованием k-d дерева или других структур для ускорения поиска).
2. Вычисление преобразования: на основе найденных пар точек решается задача минимизации среднеквадратичной ошибки. Для жёсткого преобразования решение может быть получено аналитически, например, с помощью разложения по сингулярным значениям (SVD) или метода кватернионов.

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

Разновидности и модификации

По типу преобразования

• Жёсткий ICP: ищет только поворот и перенос (6 степеней свободы). Наиболее распространённая версия.
• Аффинный ICP: допускает масштабирование и сдвиг (12 степеней свободы).
• Нежёсткий (деформируемый) ICP: позволяет облаку точек деформироваться, что полезно для регистрации нежёстких объектов (например, человеческого тела).

По критерию соответствия

• Point-to-point ICP: минимизирует расстояние между точками. Прост, но чувствителен к шуму.
• Point-to-plane ICP: минимизирует расстояние от точки до плоскости, аппроксимирующей локальную поверхность целевого облака. Обеспечивает лучшую сходимость на гладких поверхностях.
• Plane-to-plane ICP: использует соответствия между плоскостями, что повышает точность на объектах с плоскими гранями.

По способу поиска соответствий

• Стандартный ICP: использует евклидово расстояние.
• ICP с фильтрацией: отбрасывает пары с большим расстоянием или несоответствием нормалей.
• ICP с использованием цветовой информации: учитывает цвет точек для более точного сопоставления.

Применение

Трёхмерное сканирование и реконструкция

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

Робототехника

В задачах локализации и картирования (SLAM) ICP применяется для оценки движения робота на основе данных лидара или глубинных камер. Алгоритм позволяет сопоставлять текущие измерения с картой окружающей среды.

Компьютерное зрение

ICP используется для отслеживания объектов, оценки позы камеры, а также для выравнивания моделей (например, при наложении виртуальных объектов на реальные сцены в дополненной реальности).

Медицина

В медицинской визуализации ICP применяется для регистрации предоперационных и интраоперационных данных (например, КТ-снимков с данными ультразвука), а также для навигации при хирургических вмешательствах.

Преимущества и недостатки

Преимущества

• Простота реализации и понимания.
• Высокая скорость работы при использовании эффективных структур данных.
• Хорошая точность при правильном начальном приближении.
• Возможность адаптации под различные типы данных и задачи.

Недостатки

• Чувствительность к начальному положению облаков: при большом смещении алгоритм может сходиться к локальному минимуму.
• Требовательность к качеству данных: шум, выбросы и частичное перекрытие могут существенно ухудшить результат.
• Необходимость в большом количестве итераций для сложных сцен.
• Отсутствие гарантии глобальной сходимости.

Интересные факты

• Название «итеративный алгоритм ближайших точек» отражает два ключевых аспекта: итеративный характер процесса и использование ближайших точек для установления соответствий.
• Существуют варианты ICP, которые работают в реальном времени на встраиваемых системах, что делает их пригодными для использования в дронах и мобильных роботах.
• Алгоритм лёг в основу многих коммерческих программных продуктов для обработки трёхмерных данных, таких как CloudCompare, MeshLab и библиотеки Point Cloud Library (PCL).

Критика

Основная критика ICP связана с его неспособностью гарантировать нахождение глобального оптимума при неблагоприятных начальных условиях. Это привело к разработке методов глобальной регистрации, таких как RANSAC или алгоритмы на основе случайных выборок, которые часто используются для предварительного выравнивания перед запуском ICP. Кроме того, в задачах с большим количеством точек или высокой размерностью данных алгоритм может быть вычислительно затратным, что требует применения ускорений, таких как понижение разрешения облаков или использование GPU.

Источники

• Besl, P. J., & McKay, N. D. (1992). A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2), 239–256.
• Chen, Y., & Medioni, G. (1992). Object modelling by registration of multiple range images. Image and Vision Computing, 10(3), 145–155.
• Rusinkiewicz, S., & Levoy, M. (2001). Efficient variants of the ICP algorithm. Proceedings of the Third International Conference on 3-D Digital Imaging and Modeling, 145–152.
• Point Cloud Library (PCL). Documentation on ICP registration.