Итеративная ближайшая точка

Итеративная ближайшая точка ( ICP ) ^[1]^[2]^[3]^[4] — это алгоритм , используемый для минимизации разницы между двумя облаками точек . ICP часто используется для реконструкции 2D или 3D поверхностей на основе различных сканирований, для локализации роботов и достижения оптимального планирования пути (особенно когда одометрия колес ненадежна из-за скользкой местности), для совместной регистрации костей моделей и т. д.

Обзор

Алгоритм итеративной ближайшей точки сохраняет одно облако точек, эталон или цель, фиксированным, одновременно преобразуя другое, источник, для наилучшего соответствия эталону. Преобразование (комбинация перемещения и вращения) оценивается итеративно, чтобы минимизировать метрику ошибки, обычно это сумма квадратов разностей между координатами совпадающих пар. 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 . ПМИД 21869429 . S2CID 8724100 .
^ Jump up to: ^а ^б Бесл, Пол Дж.; Н. Д. Маккей (1992). «Метод регистрации объемных фигур». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 14 (2): 239–256. дои : 10.1109/34.121791 .
^ Jump up to: ^а ^б Чен, Ян; Жерар Медиони (1991). «Моделирование объектов путем регистрации изображений нескольких диапазонов». Изображение Vision Comput . 10 (3): 145–155. дои : 10.1016/0262-8856(92)90066-C .
^ Jump up to: ^а ^б Чжан, Чжэнъю (1994). «Итеративное сопоставление точек для регистрации кривых и поверхностей произвольной формы». Международный журнал компьютерного зрения . 13 (12): 119–152. CiteSeerX 10.1.1.175.770 . дои : 10.1007/BF01427149 . S2CID 14673939 .
^ Jump up to: ^а ^б Русинкевич, Шимон; Марк Левой (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 .

[arun1987-1] Арун, Сомани; Томас С. Хуанг; Стивен Д. Блостейн (1987). «Аппликация по методу наименьших квадратов двух трехмерных наборов точек». Анализ шаблонов IEEE и машинный интеллект . 9 (5): 698–700. CiteSeerX 10.1.1.467.9356 . дои : 10.1109/TPAMI.1987.4767965 . ПМИД 21869429 . S2CID 8724100 .

[autogenerated239-2] Jump up to: ^а ^б Бесл, Пол Дж.; Н. Д. Маккей (1992). «Метод регистрации объемных фигур». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 14 (2): 239–256. дои : 10.1109/34.121791 .

[autogenerated145-3] Jump up to: ^а ^б Чен, Ян; Жерар Медиони (1991). «Моделирование объектов путем регистрации изображений нескольких диапазонов». Изображение Vision Comput . 10 (3): 145–155. дои : 10.1016/0262-8856(92)90066-C .

[zhang_IJCV_1994-4] Jump up to: ^а ^б Чжан, Чжэнъю (1994). «Итеративное сопоставление точек для регистрации кривых и поверхностей произвольной формы». Международный журнал компьютерного зрения . 13 (12): 119–152. CiteSeerX 10.1.1.175.770 . дои : 10.1007/BF01427149 . S2CID 14673939 .

[rusinkiewicz145-5] Jump up to: ^а ^б Русинкевич, Шимон; Марк Левой (2001). Эффективные варианты алгоритма ICP . Материалы Третьей международной конференции по трехмерной цифровой визуализации и моделированию. Квебек-Сити, Квебек, Канада. стр. 145–152. дои : 10.1109/IM.2001.924423 .

[reviewPointCloud-6] Померло, Франсуа; Колас, Фрэнсис; Зигварт, Роланд (2015). «Обзор алгоритмов регистрации облаков точек для мобильной робототехники» . Основы и тенденции в робототехнике . 4 (1): 1–104. CiteSeerX 10.1.1.709.2212 . дои : 10.1561/2300000035 . S2CID 62361231 .

[7] Кок-Лим Лоу (февраль 2004 г.). «Линейная оптимизация метода наименьших квадратов для регистрации поверхности ICP точка-плоскость» (PDF) . Comp.nys.edu.sg. Технический отчет TR04-004, факультет компьютерных наук, Университет Северной Каролины в Чапел-Хилл . Проверено 27 февраля 2017 г.

[8] Франсуа Померло, Фрэнсис Кола, Роланд Зигварт и Стефан Магненат. Сравнение вариантов ICP с наборами реальных данных. В Autonomous Robots, 34(3), страницы 133–148, DOI: 10.1007/s10514-013-9327-2, апрель 2013 г.

[PCL-Tutorial-9] Хольц, Дирк; Ичим, Александру Э.; Томбари, Федерико; Русу, Раду Б.; Бенке, Свен (2015). «Регистрация в библиотеке облаков точек: модульная структура для выравнивания в 3D» . Журнал IEEE Robotics Automation . 22 (4): 110–124. дои : 10.1109/MRA.2015.2432331 . S2CID 2621807 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]