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

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

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

Обзор

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

Алгоритм 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.

Смотрите также

Рекомендации

  1. ^ Арун, Сомани; Томас С. Хуанг; Стивен Д. Блоштейн (1987). «Подгонка по методу наименьших квадратов двух наборов трехмерных точек». Анализ шаблонов IEEE и машинный интеллект.
  2. ^ а б Besl, Paul J .; Н.Д. Маккей (1992). «Метод регистрации трехмерных фигур». IEEE Transactions по анализу шаблонов и машинному анализу. 14 (2): 239–256. Дои:10.1109/34.121791.
  3. ^ а б Чен, Ян; Жерар Медиони (1991). «Моделирование объектов путем регистрации многодиапазонных изображений». Image Vision Comput. 10 (3): 145–155. Дои:10.1016 / 0262-8856 (92) 90066-С.
  4. ^ а б Чжан, Чжэнъю (1994). «Итерационное сопоставление точек для регистрации кривых и поверхностей произвольной формы». Международный журнал компьютерного зрения. 13 (12): 119–152. CiteSeerX  10.1.1.175.770. Дои:10.1007 / BF01427149.
  5. ^ а б Русинкевич, Шимон; Марк Левой (2001). Эффективные варианты алгоритма ICP. Труды Третьей международной конференции по трехмерной цифровой визуализации и моделированию. Квебек-Сити, Квебек, Канада. С. 145–152. Дои:10.1109 / IM.2001.924423.
  6. ^ Померло, Франсуа; Колас, Фрэнсис; Зигварт, Роланд (2015). «Обзор алгоритмов регистрации облаков точек для мобильной робототехники». Основы и тенденции в робототехнике. 4 (1): 1–104. CiteSeerX  10.1.1.709.2212. Дои:10.1561/2300000035.
  7. ^ Кок-Лим Лоу (февраль 2004 г.). "Линейная оптимизация методом наименьших квадратов для регистрации поверхности ICP" точка-плоскость " (PDF). Comp.nys.edu.sg. Технический отчет TR04-004, Департамент компьютерных наук, Университет Северной Каролины в Чапел-Хилл. Получено 2017-02-27.
  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. Дои:10.1109 / MRA.2015.2432331.