Алгоритм итеративной ближайшей точки сохраняет одно облако точек, эталон или цель, фиксированным, одновременно преобразуя другое, источник, для наилучшего соответствия эталону. Преобразование (комбинация перемещения и вращения) оценивается итеративно, чтобы минимизировать метрику ошибки, обычно представляющую собой сумму квадратов разностей между координатами совпадающих пар. ICP — один из широко используемых алгоритмов выравнивания трехмерных моделей с учетом первоначального предположения о требуемом жестком преобразовании . [5]
Алгоритм ICP был впервые представлен Ченом и Медиони, [3] а также Беслом и Маккеем. [2]
Входные данные: опорные и исходные облака точек, первоначальная оценка преобразования для выравнивания источника по опорному (необязательно), критерии остановки итераций.
Результат: усовершенствованная трансформация.
По сути, шаги алгоритма таковы: [5]
Для каждой точки (из всего набора вершин, обычно называемого плотным, или из набора пар вершин из каждой модели) в исходном облаке точек сопоставьте ближайшую точку в облаке опорных точек (или выбранном наборе).
Оцените комбинацию вращения и перемещения, используя среднеквадратичный метод минимизации метрики расстояния между точками, который наилучшим образом выровняет каждую исходную точку по ее совпадению, найденному на предыдущем шаге. Этот шаг также может включать взвешивание точек и отбраковку выбросов перед выравниванием.
Преобразуйте исходные точки, используя полученное преобразование.
Чжан [4] предлагает модифицированный алгоритм дерева k -d для эффективного вычисления ближайшей точки. В этой работе статистический метод, основанный на распределении расстояний, используется для борьбы с выбросами, окклюзией, появлением и исчезновением, что позволяет сопоставлять подмножества.
Существует множество вариантов ICP, [6] из которых наиболее популярными являются «точка-точка» и «точка-плоскость». Последний обычно работает лучше в структурированных средах. [7] [8]
Реализации
MeshLab — инструмент обработки сеток с открытым исходным кодом, который включает реализацию алгоритма ICP под лицензией GNU General Public License.
CloudCompare — инструмент обработки точек и моделей с открытым исходным кодом, включающий реализацию алгоритма ICP. Выпущено под лицензией GNU General Public License.
PCL (Point Cloud Library) — это платформа с открытым исходным кодом для n-мерных облаков точек и обработки трехмерной геометрии. Он включает в себя несколько вариантов алгоритма ICP. [9]
Реализации алгоритма ICP на C++ с открытым исходным кодом доступны в библиотеках VTK , ITK и Open3D.
libpointmatcher — это реализация ICP «точка-точка» и «точка-плоскость», выпущенная под лицензией BSD.
simpleICP — это реализация довольно простой версии алгоритма ICP на различных языках.
^ Арун, Сомани; Томас С. Хуанг; Стивен Д. Блостейн (1987). «Аппликация по методу наименьших квадратов двух трехмерных наборов точек». Анализ шаблонов IEEE и машинный интеллект . 9 (5): 698–700. CiteSeerX 10.1.1.467.9356 . дои : 10.1109/TPAMI.1987.4767965. PMID 21869429. S2CID 8724100.
^ аб Бесл, Пол Дж.; Н. Д. Маккей (1992). «Метод регистрации трехмерных фигур». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 14 (2): 239–256. дои : 10.1109/34.121791.
^ Аб Чен, Ян; Жерар Медиони (1991). «Моделирование объектов путем регистрации изображений нескольких диапазонов». Изображение Vision Comput . 10 (3): 145–155. дои : 10.1016/0262-8856(92)90066-C.
^ Аб Чжан, Чжэнъю (1994). «Итеративное сопоставление точек для регистрации кривых и поверхностей произвольной формы». Международный журнал компьютерного зрения . 13 (12): 119–152. CiteSeerX 10.1.1.175.770 . дои : 10.1007/BF01427149. S2CID 14673939.
^ аб Русинкевич, Шимон; Марк Левой (2001). Эффективные варианты алгоритма ICP . Материалы Третьей международной конференции по трехмерной цифровой визуализации и моделированию. Квебек-Сити, Квебек, Канада. стр. 145–152. дои : 10.1109/IM.2001.924423.
^ Померло, Франсуа; Колас, Фрэнсис; Зигварт, Роланд (2015). «Обзор алгоритмов регистрации облаков точек для мобильной робототехники». Основы и тенденции в робототехнике . 4 (1): 1–104. CiteSeerX 10.1.1.709.2212 . дои : 10.1561/2300000035. S2CID 62361231.
^ Кок-Лим Лоу (февраль 2004 г.). «Линейная оптимизация метода наименьших квадратов для регистрации поверхности ICP точка-плоскость» (PDF) . Comp.nys.edu.sg. Технический отчет TR04-004, факультет компьютерных наук, Университет Северной Каролины в Чапел-Хилл . Проверено 27 февраля 2017 г.
^ Франсуа Померло, Фрэнсис Кола, Роланд Зигварт и Стефан Магненат. Сравнение вариантов ICP с наборами реальных данных. В Autonomous Robots, 34(3), страницы 133–148, DOI: 10.1007/s10514-013-9327-2, апрель 2013 г.
^ Хольц, Дирк; Ичим, Александру Э.; Томбари, Федерико; Русу, Раду Б.; Бенке, Свен (2015). «Регистрация в библиотеке облаков точек: модульная структура для выравнивания в 3D». Журнал IEEE Robotics Automation . 22 (4): 110–124. дои : 10.1109/MRA.2015.2432331. S2CID 2621807.
