Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Идея итеративного алгоритма ближайшей точки

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

Обзор [ править ]

В итеративной ближайшей точке или, в некоторых источниках, в итеративной соответствующей точке одно облако точек (облако вершин), ссылка или цель остается фиксированной, в то время как другое, источник , преобразуется, чтобы наилучшим образом соответствовать ссылке. Алгоритм итеративно пересматривает преобразование (комбинацию перемещения и вращения), необходимое для минимизации метрики ошибки, обычно расстояния от источника до облака опорных точек, например суммы квадратов разностей между координатами согласованных пар. ICP - один из широко используемых алгоритмов для выравнивания трехмерных моделей с учетом первоначального предположения о требуемом жестком преобразовании . [5]Алгоритм ICP был впервые представлен Ченом и Медиони [3], а также Беслом и Маккеем. [2]

Алгоритм Iterative Closest Point отличается от алгоритма Kabsch и других решений ортогональной проблемы Procrustes в том, что алгоритм Kabsch требует соответствия между наборами точек в качестве входных данных, тогда как Iterative Closest Point обрабатывает соответствие как переменную, которую нужно оценить.

Входные данные: облака точек отсчета и источника, начальная оценка преобразования для выравнивания источника относительно опорного значения (необязательно), критерии остановки итераций.

Выход: изысканная трансформация.

По сути, шаги алгоритма следующие: [5]

  1. Для каждой точки (из всего набора вершин, обычно называемых плотными, или набора пар вершин из каждой модели) в исходном облаке точек сопоставьте ближайшую точку в облаке опорных точек (или выбранном наборе).
  2. Оцените комбинацию вращения и смещения, используя метод минимизации среднеквадратичного расстояния от точки до точки, который наилучшим образом выровняет каждую исходную точку по совпадению, найденному на предыдущем шаге. Этот шаг также может включать в себя взвешивание и отклонение выбросов перед выравниванием.
  3. Преобразуйте исходные точки, используя полученное преобразование.
  4. Итерировать (повторно связать точки и т. Д.).

Чжан [4] предлагает модифицированный алгоритм k -d-дерева для эффективного вычисления ближайшей точки. В этой работе статистический метод, основанный на распределении расстояний, используется для работы с выбросами, окклюзией, появлением и исчезновением, что позволяет сопоставить подмножество-подмножество.

Существует множество вариантов ICP [6], из которых наиболее популярны точка-точка и точка-плоскость. Последний обычно лучше работает в структурированной среде. [7] [8]

Реализации [ править ]

  • MeshLab - инструмент обработки сетки с открытым исходным кодом, который включает реализацию алгоритма ICP по стандартной общественной лицензии GNU.
  • CloudCompare - инструмент обработки точек и моделей с открытым исходным кодом, который включает реализацию алгоритма ICP. Выпущено под Стандартной общественной лицензией GNU.
  • PCL (библиотека облаков точек) - это платформа с открытым исходным кодом для n-мерных облаков точек и обработки трехмерной геометрии. Он включает несколько вариантов алгоритма ICP. [9]
  • Реализации алгоритма ICP на C ++ с открытым исходным кодом доступны в библиотеках VTK , ITK и Open3D .
  • libpointmatcher - это реализация ICP точка-точка и точка-плоскость, выпущенная под лицензией BSD.
  • simpleICP - это реализация довольно простой версии алгоритма ICP на разных языках.

См. Также [ править ]

Ссылки [ править ]

  1. ^ Арун, Сомани; Томас С. Хуанг; Стивен Д. Блоштейн (1987). «Подгонка по методу наименьшего квадрата двух наборов трехмерных точек». Анализ шаблонов IEEE и машинный интеллект .
  2. ^ a b Besl, Paul J .; Н.Д. Маккей (1992). «Метод регистрации трехмерных фигур». IEEE Transactions по анализу шаблонов и машинному анализу . 14 (2): 239–256. DOI : 10.1109 / 34.121791 .
  3. ^ а б Чен, Ян; Жерар Медиони (1991). «Моделирование объектов путем регистрации многодиапазонных изображений». Image Vision Comput . 10 (3): 145–155. DOI : 10.1016 / 0262-8856 (92) 90066-C .
  4. ^ a b Чжан, Чжэнъю (1994). «Итерационное сопоставление точек для регистрации кривых и поверхностей произвольной формы». Международный журнал компьютерного зрения . 13 (12): 119–152. CiteSeerX 10.1.1.175.770 . DOI : 10.1007 / BF01427149 . 
  5. ^ a b Русинкевич, Шимон; Марк Левой (2001). Эффективные варианты алгоритма ICP . Труды Третьей международной конференции по трехмерной цифровой визуализации и моделированию. Квебек, Квебек, Канада. С. 145–152. DOI : 10.1109 / IM.2001.924423 .
  6. ^ Померло, Франсуа; Колас, Фрэнсис; Зигварт, Роланд (2015). «Обзор алгоритмов регистрации облака точек для мобильной робототехники» . Основы и тенденции в робототехнике . 4 (1): 1–104. CiteSeerX 10.1.1.709.2212 . DOI : 10.1561 / 2300000035 . 
  7. ↑ Kok-Lim Low (февраль 2004 г.). "Линейная оптимизация методом наименьших квадратов для регистрации поверхности ICP" точка-плоскость " (PDF) . Comp.nys.edu.sg . Технический отчет TR04-004, Департамент компьютерных наук, Университет Северной Каролины в Чапел-Хилл . Проверено 27 февраля 2017 . CS1 maint: discouraged parameter (link)
  8. ^ Франсуа Померло, Фрэнсис Колас, Ролан Сигварт и Стефан Магнена. Сравнение вариантов ПМС на реальных наборах данных. В автономных роботах, 34 (3), страницы 133–148, DOI: 10.1007 / s10514-013-9327-2, апрель 2013 г.
  9. ^ Хольц, Дирк; Ichim, Alexandru E .; Томбари, Федерико; Русу, Раду Б .; Бенке, Свен (2015). «Регистрация в библиотеке облака точек: модульная структура для трехмерного выравнивания» . Журнал IEEE Robotics Automation . 22 (4): 110–124. DOI : 10.1109 / MRA.2015.2432331 .