Регистрация набора точек - Point set registration - Wikipedia

Регистрация набора точек - это процесс совмещения двух наборов точек. Здесь синяя рыба записывается на красную.

В компьютерное зрение, распознавание образов, и робототехника, регистрация набора точек, также известный как регистрация облака точек или же сканирование соответствия, это процесс поиска пространственного трансформация (например., масштабирование, вращение и перевод ), который выравнивает два облака точек. Цель поиска такого преобразования включает в себя объединение нескольких наборов данных в глобально согласованную модель (или систему координат) и сопоставление нового измерения с известным набором данных для идентификации функций или оценить его позу. Необработанные данные облака точек 3D обычно получают из Лидары и RGB-D камеры. 3D-облака точек также могут быть созданы с помощью алгоритмов компьютерного зрения, таких как триангуляция, регулировка связки, а в последнее время - оценка глубины монокулярного изображения с использованием глубокое обучение. Для регистрации двухмерных точек, используемых при обработке изображений и на основе функций регистрация изображения, набор точек может быть двухмерными пиксельными координатами, полученными извлечение признаков из изображения, например обнаружение угла. Регистрация облака точек имеет обширное применение в автономное вождение,^[1] оценка движения и 3D-реконструкция,^[2] обнаружение объекта и оценка позы,^[3][4] роботизированная манипуляция,^[5] одновременная локализация и отображение (SLAM),^[6][7] сшивание панорамы,^[8] виртуальная и дополненная реальность,^[9] и медицинская визуализация.^[10]

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

Обзор проблемы

Данные двух 3D-сканирований одной и той же среды необходимо согласовать с помощью регистрации набора точек.

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

Проблему можно резюмировать следующим образом:^[11]Позволять ${ Displaystyle lbrace { mathcal {M}}, { mathcal {S}} rbrace}$ два набора точек конечного размера в конечномерное вещественное векторное пространство ${ Displaystyle mathbb {R} ^ {d}}$, которые содержат ${ displaystyle M}$ и ${ displaystyle N}$ баллов соответственно (например., ${ displaystyle d = 3}$ восстанавливает типичный случай, когда ${ Displaystyle { mathcal {M}}}$ и ${ Displaystyle { mathcal {S}}}$ являются трехмерными наборами точек). Проблема состоит в том, чтобы найти преобразование, которое будет применяться к движущемуся набору точек "модели". ${ Displaystyle { mathcal {M}}}$ такая, что разница (обычно определяемая в смысле точечной Евклидово расстояние ) между ${ Displaystyle { mathcal {M}}}$ и статический набор "сцены" ${ Displaystyle { mathcal {S}}}$ сводится к минимуму. Другими словами, отображение из ${ Displaystyle mathbb {R} ^ {d}}$ к ${ Displaystyle mathbb {R} ^ {d}}$ желательно, что дает наилучшее выравнивание между преобразованным набором «модель» и набором «сцена». Отображение может состоять из жесткого или нежесткого преобразования. Модель трансформации может быть записана как ${ displaystyle T}$, с использованием которого преобразованный, зарегистрированный набор точек модели:

${ Displaystyle Т ({ mathcal {M}})}$

(1)

Таким образом, на выходе алгоритма регистрации набора точек оптимальная трансформация ${ Displaystyle Т ^ { звезда}}$ такой, что ${ Displaystyle { mathcal {M}}}$ лучше всего соответствует ${ Displaystyle { mathcal {S}}}$, согласно некоторому определенному понятию функции расстояния ${ Displaystyle OperatorName {dist} ( cdot, cdot)}$:

${ displaystyle T ^ { star} = arg min _ {T in { mathcal {T}}} { text {dist}} (T ({ mathcal {M}}), { mathcal { S}})}$

(2)

куда ${ displaystyle { mathcal {T}}}$ используется для обозначения набора всех возможных преобразований, которые пытается найти оптимизация. Самый популярный выбор функции расстояния - это взять квадрат Евклидово расстояние для каждой пары очков:

${ displaystyle operatorname {dist} (T ({ mathcal {M}}), { mathcal {S}}) = sum _ {m in T ({ mathcal {M}})} Vert m -s_ {m} Vert _ {2} ^ {2}, quad s_ {m} = arg min _ {s in { mathcal {S}}} Vert sm Vert _ {2} ^ {2}}$

(3)

куда ${ Displaystyle | cdot | _ {2}}$ обозначает вектор 2-норма, ${ displaystyle s_ {m}}$ это соответствующий пункт в комплекте ${ Displaystyle { mathcal {S}}}$ что достигает кратчайшее расстояние к заданной точке ${ displaystyle m}$ в комплекте ${ Displaystyle { mathcal {M}}}$. Минимизация такой функции при жесткой регистрации эквивалентна решению наименьших квадратов проблема. Когда соответствия (т.е. ${ displaystyle s_ {m} leftrightarrow m}$) задаются перед оптимизацией, например, с использованием методов сопоставления признаков, тогда при оптимизации необходимо только оценить преобразование. Этот вид регистрации называется заочная регистрация. С другой стороны, если соответствия неизвестны, то требуется оптимизация, чтобы совместно определить соответствия и совместное преобразование. Этот вид регистрации называется Одновременная регистрация позы и переписки.

Жесткая регистрация

Учитывая два набора точек, жесткая регистрация дает жесткая трансформация который отображает один набор точек на другой. Жесткое преобразование определяется как преобразование, которое не изменяет расстояние между любыми двумя точками. Обычно такое преобразование состоит из перевод и вращение.^[12] В редких случаях набор точек также может быть зеркальным. В робототехнике и компьютерном зрении жесткая регистрация имеет наибольшее применение.

Нежесткая регистрация

Зарегистрированное облако точек из лидар установлен на движущемся автомобиле.

Для двух наборов точек нежесткая регистрация приводит к нежесткому преобразованию, которое отображает один набор точек на другой. Нежесткие преобразования включают аффинные преобразования Такие как масштабирование и картирование сдвига. Однако в контексте регистрации набора точек нежесткая регистрация обычно включает нелинейное преобразование. Если собственные моды вариации набора точек известны, нелинейное преобразование может быть параметризовано собственными значениями.^[13] Нелинейное преобразование также можно параметризовать как шлиц тонкой пластины.^[14][13]

Алгоритмы регистрации набора точек

Некоторые подходы к регистрации набора точек используют алгоритмы, которые решают более общие сопоставление графиков проблема.^[11] Однако вычислительная сложность таких методов, как правило, высока, и они ограничиваются жесткой регистрацией. Алгоритмы, специфичные для задачи регистрации набора точек, описаны в следующих разделах. PCL (библиотека облаков точек) - это платформа с открытым исходным кодом для n-мерного облака точек и обработки трехмерной геометрии. Он включает в себя несколько алгоритмов регистрации точек.^[15]

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

Соответствующие методы

Методы, основанные на корреспонденции, предполагают предполагаемые соответствия ${ displaystyle m leftrightarrow s_ {m}}$ даются за каждую точку ${ displaystyle m in { mathcal {M}}}$. Таким образом, мы приходим к настройке, в которой оба точечных набора ${ Displaystyle { mathcal {M}}}$ и ${ Displaystyle { mathcal {S}}}$ имеют ${ displaystyle N}$ точки и соответствия ${ displaystyle m_ {i} leftrightarrow s_ {i}, i = 1, dots, N}$даны.

Регистрация без выбросов

В простейшем случае можно предположить, что все соответствия верны, а это означает, что точки ${ displaystyle m_ {i}, s_ {i} in mathbb {R} ^ {3}}$ генерируются следующим образом:

${ displaystyle s_ {i} = lRm_ {i} + t + epsilon _ {i}, i = 1, dots, N}$

(cb.1)

куда ${ displaystyle l> 0}$ - универсальный коэффициент масштабирования (во многих случаях ${ displaystyle l = 1}$ предполагается), ${ displaystyle R in { text {SO}} (3)}$ - правильная 3D-матрица вращения (${ displaystyle { text {SO}} (d)}$ это специальная ортогональная группа степени ${ displaystyle d}$), ${ Displaystyle т ин mathbb {R} ^ {3}}$ вектор 3D-трансляции и ${ displaystyle epsilon _ {я} in mathbb {R} ^ {3}}$ моделирует неизвестный аддитивный шум (например., Гауссов шум ). В частности, если шум ${ displaystyle epsilon _ {я}}$ предполагается, что оно следует изотропному гауссовскому распределению с нулевым средним со стандартным отклонением ${ displaystyle sigma _ {я}}$, т.е. ${ displaystyle epsilon _ {i} sim { mathcal {N}} (0, sigma _ {i} ^ {2} I_ {3})}$, то можно показать, что следующая оптимизация дает оценка максимального правдоподобия для неизвестного масштаба, поворота и перевода:

${ displaystyle l ^ { star}, R ^ { star}, t ^ { star} = arg min _ {l> 0, R in { text {SO}} (3), t в mathbb {R} ^ {3}} sum _ {i = 1} ^ {N} { frac {1} { sigma _ {i} ^ {2}}} left Vert s_ {i} -lRm_ {i} -t right Vert _ {2} ^ {2}}$

(cb.2)

Обратите внимание, что когда коэффициент масштабирования равен 1, а вектор сдвига равен нулю, тогда оптимизация восстанавливает формулировку Проблема вахбы. Несмотря на невыпуклость оптимизации (cb.2) из-за невыпуклости множества ${ displaystyle { text {SO}} (3)}$, плодотворная работа Бертольд К.П. Рог показало, что (cb.2) фактически допускает решение в замкнутой форме, разделяя оценку масштаба, поворота и перемещения.^[16] Похожие результаты обнаружил Арун. и другие.^[17] Кроме того, чтобы найти уникальное преобразование ${ Displaystyle (л, р, т)}$, по меньшей мере ${ Displaystyle N = 3}$ в каждом наборе точек требуются неколлинеарные точки.

Совсем недавно Бриалес и Гонсалес-Хименес разработали полуопределенная релаксация с помощью Лагранжева двойственность, для случая, когда модельный набор ${ Displaystyle { mathcal {M}}}$ содержит различные 3D-примитивы, такие как точки, линии и плоскости (что имеет место, когда модель ${ Displaystyle { mathcal {M}}}$ представляет собой трехмерную сетку).^[18] Интересно, что полуопределенная релаксация эмпирически точна, т.е. достоверно глобально оптимальный решение может быть извлечено из решения полуопределенной релаксации.

Надежная регистрация

В наименьших квадратов формулировка (cb.2), как известно, ведет себя сколь угодно плохо в присутствии выбросы. Отклоняющееся соответствие - это пара измерений ${ displaystyle s_ {i} leftrightarrow m_ {i}}$ что отходит от генеративной модели (cb.1). В этом случае можно рассмотреть другую генеративную модель следующим образом:^[19]

${ displaystyle s_ {i} = { begin {cases} lRm_ {i} + t + epsilon _ {i} & { text {if}} i - { text {th пара является вставкой}} o_ {i} & { text {if}} i - { text {-я пара является выбросом}} end {cases}}}$

(cb.3)

где, если ${ displaystyle i-}$ая пара ${ displaystyle s_ {i} leftrightarrow m_ {i}}$ является инльером, то он подчиняется модели без выбросов (cb.1), т.е. ${ displaystyle s_ {i}}$ получается из ${ displaystyle m_ {i}}$ пространственным преобразованием плюс небольшой шум; однако, если ${ displaystyle i-}$ая пара ${ displaystyle s_ {i} leftrightarrow m_ {i}}$ выброс, то ${ displaystyle s_ {i}}$ может быть любым произвольным вектором ${ displaystyle o_ {i}}$. Поскольку заранее неизвестно, какие соответствия являются выбросами, надежная регистрация в рамках генеративной модели (cb.3) имеет первостепенное значение для компьютерного зрения и робототехники, развернутой в реальном мире, потому что современные методы сопоставления признаков имеют тенденцию выводить сильно искаженные соответствия, где больше ${ displaystyle 95 \%}$ соответствий могут быть выбросами.^[20]

Далее мы опишем несколько общих парадигм надежной регистрации.

Максимальный консенсус

Максимальный консенсус стремится найти наибольший набор соответствий, согласующихся с генеративной моделью (cb.1) для некоторого выбора пространственного преобразования ${ Displaystyle (л, р, т)}$. Формально, максимальный консенсус решает следующую оптимизацию:

${ displaystyle max _ {l> 0, R in { text {SO}} (3), t in mathbb {R} ^ {3}, { mathcal {I}}} vert { mathcal {I}} vert, quad { text {при условии}} { frac {1} { sigma _ {i} ^ {2}}} Vert s_ {i} -lRm_ {i} -t Vert _ {2} ^ {2} leq xi, forall i in { mathcal {I}}}$

(cb.4)

куда ${ displaystyle vert { mathcal {I}} vert}$ обозначает мощность из набора ${ displaystyle { mathcal {I}}}$. Ограничение в (cb.4) обеспечивает, чтобы каждая пара измерений в наборе inlier ${ displaystyle { mathcal {I}}}$ должны быть остатки меньше предварительно определенного порога ${ Displaystyle xi}$. К сожалению, недавний анализ показал, что глобальное решение проблемы (cb.4) невозможно. NP-Hard, а глобальные алгоритмы обычно прибегают к разветвленный (BnB) методы, которые в худшем случае принимают экспоненциально-временную сложность.^{[21][22][23][24][25]}

Хотя точное решение максимизации консенсуса сложно, существуют эффективные эвристики, которые довольно хорошо работают на практике. Одна из самых популярных эвристик - Консенсус случайной выборки (RANSAC) схема.^[26] RANSAC - это итеративный метод гипотезы и проверки. На каждой итерации метод сначала случайным образом выбирает 3 из общего числа ${ displaystyle N}$ соответствует и вычисляет гипотезу ${ Displaystyle (л, р, т)}$ используя метод Хорна,^[16] затем метод оценивает ограничения в (cb.4), чтобы подсчитать, сколько соответствий действительно согласуются с такой гипотезой (т. е. вычисляет остаточную ${ displaystyle Vert s_ {i} -lRm_ {i} -t Vert _ {2} ^ {2} / sigma _ {i} ^ {2}}$ и сравнивает с порогом ${ Displaystyle xi}$ для каждой пары измерений). Алгоритм завершается либо после того, как он найдет консенсусный набор, имеющий достаточно соответствий, либо после того, как он достигнет общего количества разрешенных итераций. RANSAC очень эффективен, потому что основное вычисление каждой итерации - выполнение решения в замкнутой форме в методе Хорна. Однако RANSAC не является детерминированным и хорошо работает только в режиме низкого отношения выбросов (например., ниже ${ displaystyle 50 \%}$), потому что время его выполнения растет экспоненциально по отношению к коэффициенту выбросов.^[20]

Чтобы заполнить пробел между быстрой, но неточной схемой RANSAC и точной, но исчерпывающей оптимизацией BnB, недавние исследования разработали детерминированные приближенные методы для решения максимизации консенсуса.^{[21][22][27][23]}

Удаление выбросов

Методы удаления выбросов стремятся предварительно обработать набор сильно искаженных соответствий перед оценкой пространственного преобразования. Мотивация удаления выбросов состоит в том, чтобы значительно уменьшить количество соответствий выбросов при сохранении соответствий внутренних, так что оптимизация преобразования становится проще и эффективнее (например., RANSAC плохо работает, когда коэффициент выбросов выше ${ displaystyle 95 \%}$ но работает достаточно хорошо, когда коэффициент выбросов ниже ${ displaystyle 50 \%}$).

Парра и другие. предложили метод под названием "Гарантированное удаление выбросов" (GORE), который использует геометрические ограничения для сокращения выбросов, при этом гарантируя сохранение исходных соответствий.^[20] Доказано, что GORE может резко снизить коэффициент выбросов, что может значительно повысить производительность максимизации консенсуса с использованием RANSAC или BnB. Янг и Карлоне предложили построить парные измерения, инвариантные к сдвигу и вращению (TRIM) из исходного набора измерений, и встроить TRIM как края график узлы которого являются трехмерными точками. Поскольку инлисты попарно согласованы по масштабу, они должны образовывать клика внутри графика. Таким образом, используя эффективные алгоритмы вычисления максимальная клика графика может находить выбросы и эффективно удалять выбросы.^[4] Также показано, что метод удаления выбросов на основе максимальной клики весьма полезен в реальных задачах регистрации набора точек.^[19] Подобные идеи удаления выбросов были также предложены Паррой. и другие..^[28]

М-оценка

M-оценка заменяет целевую функцию наименьших квадратов в (cb.2) с надежной функцией стоимости, которая менее чувствительна к выбросам. Формально M-оценка направлена ​​на решение следующей задачи:

${ displaystyle l ^ { star}, R ^ { star}, t ^ { star} = arg min _ {l> 0, R in { text {SO}} (3), t в mathbb {R} ^ {3}} sum _ {i = 1} ^ {N} rho left ({ frac {1} { sigma _ {i}}} left Vert s_ {i } -lRm_ {i} -t right Vert _ {2} right)}$

(cb.5)

куда ${ displaystyle rho ( cdot)}$ представляет собой выбор надежной функции стоимости. Обратите внимание, что при выборе ${ Displaystyle rho (х) = х ^ {2}}$ восстанавливает оценку наименьших квадратов в (cb.2). Популярные надежные функции затрат включают: ${ displaystyle ell _ {1}}$-нормальная потеря, Потеря Хубера,^[29] Потеря Джемана-МакКлюра^[30] и усеченная потеря наименьших квадратов.^[19][8][4] М-оценка была одной из самых популярных парадигм надежной оценки в робототехнике и компьютерном зрении.^[31][32] Поскольку робастные целевые функции обычно невыпуклые (например., потеря усеченных наименьших квадратов в сравнении с потери наименьших квадратов), алгоритмы решения невыпуклой M-оценки обычно основаны на локальная оптимизация, где сначала предоставляется начальное предположение, за которым следуют итерационные уточнения преобразования для постоянного уменьшения целевой функции. Локальная оптимизация имеет тенденцию работать хорошо, когда первоначальное предположение близко к глобальному минимуму, но она также может застрять в локальных минимумах, если обеспечивается плохая инициализация.

Градуированная невыпуклость

Градуированная невыпуклость (GNC) - это универсальная среда для решения невыпуклых задач оптимизации без инициализации. Он добился успеха в приложениях для раннего видения и машинного обучения.^[33][34] Ключевая идея GNC - решить сложную невыпуклую задачу, начав с простой выпуклой задачи. В частности, для данной устойчивой функции стоимости ${ displaystyle rho ( cdot)}$, можно построить суррогатную функцию ${ Displaystyle rho _ { му} ( cdot)}$ с гиперпараметром ${ displaystyle mu}$, настройка, которая может постепенно увеличивать невыпуклость суррогатной функции ${ Displaystyle rho _ { му} ( cdot)}$ пока он не сходится к целевой функции ${ displaystyle rho ( cdot)}$.^[34][35] Следовательно, на каждом уровне гиперпараметра ${ displaystyle mu}$, решается следующая оптимизация:

${ displaystyle l _ { mu} ^ { star}, R _ { mu} ^ { star}, t _ { mu} ^ { star} = arg min _ {l> 0, R in { text {SO}} (3), t in mathbb {R} ^ {3}} sum _ {i = 1} ^ {N} rho _ { mu} left ({ frac {1 } { sigma _ {i}}} left Vert s_ {i} -lRm_ {i} -t right Vert _ {2} right)}$

(cb.6)

Блэк и Рангараджан доказали, что целевая функция каждой оптимизации (cb.6) можно дуализировать в сумму взвешенный метод наименьших квадратов и так называемая функция обработки выбросов на весах, которые определяют достоверность оптимизации в каждой паре измерений.^[33] Используя двойственность Блэка-Рангараджана и GNC, адаптированную для функции Гемана-МакКлюра, Чжоу и другие. разработал алгоритм быстрой глобальной регистрации, устойчивый к примерно ${ displaystyle 80 \%}$ выбросы в соответствиях.^[30] Совсем недавно Ян и другие. показали, что совместное использование GNC (адаптированной к функции Джемана-МакКлюра и усеченной функции наименьших квадратов) и двойственности Блэка-Рангараджана может привести к универсальному решателю для надежных проблем регистрации, включая облака точек и регистрацию сетки.^[35]

Гарантированно надежная регистрация

Практически ни один из упомянутых выше надежных алгоритмов регистрации (за исключением алгоритма BnB, который в худшем случае выполняется в экспоненциальном времени) не имеет гарантии исполнения, что означает, что эти алгоритмы могут возвращать совершенно неверные оценки без уведомления. Следовательно, эти алгоритмы нежелательны для критически важных для безопасности приложений, таких как автономное вождение.

Совсем недавно Ян и другие. разработал первый сертифицированный надежный алгоритм регистрации, названный Усеченная оценка методом наименьших квадратов и неопределенная релаксация SE (ТИЗЕР).^[19] Для регистрации облака точек TEASER не только выводит оценку преобразования, но также количественно определяет оптимальность данной оценки. TEASER использует следующую оценку методом усеченных наименьших квадратов (TLS):

${ displaystyle l ^ { star}, R ^ { star}, t ^ { star} = arg min _ {l> 0, R in { text {SO}} (3), t в mathbb {R} ^ {3}} sum _ {i = 1} ^ {N} min left ({ frac {1} { sigma _ {i} ^ {2}}} left Vert s_ {i} -lRm_ {i} -t right Vert _ {2} ^ {2}, { bar {c}} ^ {2} right)}$

(cb.7)

который получается выбором робастной функции стоимости TLS ${ displaystyle rho (x) = min (x ^ {2}, { bar {c}} ^ {2})}$, куда ${ displaystyle { bar {c}} ^ {2}}$- предварительно определенная константа, определяющая максимально допустимые остатки, которые следует рассматривать как выбросы. Целевая функция TLS обладает тем свойством, что для внутренних соответствий (${ displaystyle Vert s_ {i} -lRm_ {i} -t Vert _ {2} ^ {2} / sigma _ {i} ^ {2} <{ bar {c}} ^ {2}}$) применяется обычный штраф по методу наименьших квадратов; а для резко отклоняющихся соответствий (${ displaystyle Vert s_ {i} -lRm_ {i} -t Vert _ {2} ^ {2} / sigma _ {i} ^ {2}> { bar {c}} ^ {2}}$) штраф не применяется, выбросы отбрасываются. Если оптимизация TLS (cb.7) решается до глобальной оптимальности, то это эквивалентно запуску метода Хорна только для внутренних соответствий.

Однако решение (cb.7) является довольно сложной задачей из-за своей комбинаторной природы. TEASER решает (cb.7) следующим образом: (i) он строит инвариантные измерения, так что оценка масштаба, вращения и перемещения может быть отделена и решена отдельно, стратегия, вдохновленная оригинальным методом Хорна; (ii) Одна и та же оценка TLS применяется для каждой из трех подзадач, где задача TLS масштаба может быть решена точно с использованием алгоритма, называемого адаптивным голосованием, задача TLS вращения может быть ослаблена до полуопределенная программа (SDP), где релаксация является точной на практике,^[8] даже при большом количестве выбросов; Решить проблему TLS трансляции можно с помощью покомпонентного адаптивного голосования. Быстрая реализация с использованием GNC - это здесь с открытым исходным кодом. На практике TEASER может терпеть больше, чем ${ displaystyle 99 \%}$ выбросы соответствуют и запускаются в миллисекундах.

Помимо разработки TEASER, Ян и другие. также доказать, что при некоторых мягких условиях для данных облака точек расчетное преобразование TEASER имеет ограниченные ошибки из преобразования наземной истины.^[19]

Одновременные позы и заочные методы

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

В итеративная ближайшая точка (ICP) алгоритм был представлен Беслом и Маккеем.^[36]Алгоритм выполняет жесткую регистрацию итеративным способом, чередуя (i) с учетом преобразования, находя ближайшая точка в ${ Displaystyle { mathcal {S}}}$ за каждую точку в ${ Displaystyle { mathcal {M}}}$; и (ii) учитывая соответствия, найти наилучшее жесткое преобразование путем решения наименьших квадратов проблема (cb.2). Таким образом, он работает лучше всего, если исходная поза ${ Displaystyle { mathcal {M}}}$ достаточно близко к ${ Displaystyle { mathcal {S}}}$. В псевдокод, основной алгоритм реализуется следующим образом:

алгоритм ICP(${ displaystyle { mathcal {M}}, { mathcal {S}}}$)    ${ displaystyle  theta: =  theta _ {0}}$    в то время как не зарегистрировано: Икс := ∅        за ${ displaystyle m_ {i}  in T ({ mathcal {M}},  theta)}$:            ${ displaystyle { hat {s}} _ {j}: = { text {ближайшая точка в}} { mathcal {S}} { text {to}} m_ {i}}$            ${ displaystyle X: = X +  langle m_ {i}, { hat {s}} _ {j}  rangle}$        θ := наименьших квадратов (Икс)    возвращаться θ

Здесь функция наименьших квадратов выполняет наименьших квадратов оптимизация для минимизации расстояния в каждом из ${ displaystyle langle m_ {i}, { hat {s}} _ {j} rangle}$ пары, используя замкнутые решения Хорна^[16] и Арун.^[17]

Поскольку функция стоимости регистрации зависит от нахождения ближайшей точки в ${ Displaystyle { mathcal {S}}}$ к каждой точке в ${ Displaystyle { mathcal {M}}}$, он может меняться по мере работы алгоритма. Таким образом, трудно доказать, что ICP действительно сходится точно к локальному оптимуму.^[37] Фактически, эмпирически ПМС и EM-ICP не сходятся к локальному минимуму функции стоимости.^[37] Тем не менее, поскольку ICP интуитивно понятен и прост в реализации, он остается наиболее часто используемым алгоритмом регистрации набора точек.^[37] Было предложено множество вариантов ICP, влияющих на все фазы алгоритма от выбора и сопоставления точек до стратегии минимизации.^[13][38]Например, максимизация ожидания алгоритм применяется к алгоритму ICP для формирования метода EM-ICP, и Алгоритм Левенберга-Марквардта применяется к алгоритму ICP для формирования LM-ICP метод.^[12]

Надежное согласование точек

Робастное согласование точек (RPM) было введено Gold et al.^[39] Метод выполняет регистрацию с использованием детерминированный отжиг и мягкое задание соответствий между наборами точек. В то время как в ICP соответствие, генерируемое эвристикой ближайшего соседа, является двоичным, RPM использует мягкий соответствие, при котором соответствие между любыми двумя точками может быть от 0 до 1, хотя в конечном итоге оно сходится либо к 0, либо к 1. Соответствия, обнаруженные в RPM, всегда взаимно однозначны, что не всегда имеет место в ICP.^[14] Позволять ${ displaystyle m_ {i}}$ быть ${ displaystyle i}$й пункт в ${ Displaystyle { mathcal {M}}}$ и ${ displaystyle s_ {j}}$ быть ${ displaystyle j}$й пункт в ${ Displaystyle { mathcal {S}}}$. В матрица соответствия ${ Displaystyle mathbf { mu}}$ определяется как таковое:

${ displaystyle mu _ {ij} = left lbrace { begin {matrix} 1 & { text {if point}} m_ {i} { text {соответствует точке}} s_ {j} 0 & { text {иначе}} end {matrix}} right.}$

(об / мин.1)

Тогда проблема определяется как: Даны два точечных набора ${ Displaystyle { mathcal {M}}}$ и ${ Displaystyle { mathcal {S}}}$ Найди Аффинное преобразование ${ displaystyle T}$ и матрица соответствия ${ Displaystyle mathbf { mu}}$ это лучше всего их соотносит.^[39] Знание оптимального преобразования упрощает определение матрицы соответствия, и наоборот. Однако алгоритм RPM определяет и то, и другое одновременно. Преобразование можно разложить на вектор перевода и матрицу преобразования:

${ Displaystyle Т (м) = mathbf {A} м + mathbf {т}}$

Матрица ${ displaystyle mathbf {A}}$ в 2D состоит из четырех отдельных параметров ${ displaystyle lbrace a, theta, b, c rbrace}$, которые представляют собой масштаб, вращение и компоненты вертикального и горизонтального сдвига соответственно. Тогда функция стоимости будет следующей:

${ displaystyle operatorname {cost} = sum _ {j = 1} ^ {N} sum _ {i = 1} ^ {M} mu _ {ij} lVert s_ {j} - mathbf {t } - mathbf {A} m_ {i} rVert ^ {2} + g ( mathbf {A}) - alpha sum _ {j = 1} ^ {N} sum _ {i = 1} ^ {M} mu _ {ij}}$

(об / мин.2)

при условии ${ Displaystyle forall j ~ сумма _ {я = 1} ^ {M} mu _ {ij} leq 1}$, ${ Displaystyle forall я ~ сумма _ {j = 1} ^ {N} mu _ {ij} leq 1}$, ${ Displaystyle forall ij ~ mu _ {ij} in lbrace 0,1 rbrace}$. В ${ displaystyle alpha}$ термин смещает цель в сторону более сильной корреляции, уменьшая стоимость, если в матрице соответствия больше единиц. Функция ${ Displaystyle г ( mathbf {A})}$ служит для регуляризации аффинного преобразования за счет штрафов за большие значения компонентов масштаба и сдвига:

${ displaystyle g ( mathbf {A} (a, theta, b, c)) = gamma (a ^ {2} + b ^ {2} + c ^ {2})}$

для некоторого параметра регуляризации ${ displaystyle gamma}$.

Метод RPM оптимизирует функцию стоимости с помощью Softassign алгоритм. Здесь будет выведен одномерный случай. Учитывая набор переменных ${ Displaystyle lbrace Q_ {j} rbrace}$ куда ${ Displaystyle Q_ {j} in mathbb {R} ^ {1}}$. Переменная ${ displaystyle mu _ {j}}$ связан с каждым ${ displaystyle Q_ {j}}$ такой, что ${ Displaystyle сумма _ {j = 1} ^ {J} mu _ {j} = 1}$. Цель - найти ${ Displaystyle mathbf { mu}}$ что максимизирует ${ Displaystyle сумма _ {j = 1} ^ {J} mu _ {j} Q_ {j}}$. Это можно сформулировать как непрерывную задачу, введя управляющий параметр ${ displaystyle beta> 0}$. в детерминированный отжиг метод, управляющий параметр ${ displaystyle beta}$ медленно увеличивается по мере выполнения алгоритма. Позволять ${ Displaystyle mathbf { mu}}$ быть:

${ displaystyle mu _ { hat {j}} = { frac { exp {( beta Q _ { hat {j}})}} { sum _ {j = 1} ^ {J} exp {( beta Q_ {j})}}}}$

(об / мин.3)

это известно как функция softmax. В качестве ${ displaystyle beta}$ увеличивается, оно приближается к двоичному значению, как требуется в уравнении (об / мин.1). Теперь проблему можно обобщить на 2D-случай, когда вместо максимизации ${ Displaystyle сумма _ {j = 1} ^ {J} mu _ {j} Q_ {j}}$, максимальное количество:

${ displaystyle E ( mu) = sum _ {j = 1} ^ {N} sum _ {i = 0} ^ {M} mu _ {ij} Q_ {ij}}$

(об / мин.4)

куда

${ Displaystyle Q_ {ij} = - ( lVert s_ {j} - mathbf {t} - mathbf {A} m_ {i} rVert ^ {2} - alpha) = - { frac { partial operatorname {cost}} { partial mu _ {ij}}}}$

Это просто, за исключением того, что теперь ограничения на ${ displaystyle mu}$ находятся дважды стохастическая матрица ограничения: ${ Displaystyle forall j ~ сумма _ {я = 1} ^ {M} mu _ {ij} = 1}$ и ${ Displaystyle forall я ~ сумма _ {j = 1} ^ {N} mu _ {ij} = 1}$. Таким образом, знаменатель из уравнения (об / мин.3) нельзя просто выразить для 2D случая. Чтобы удовлетворить ограничения, можно использовать результат Синкхорна,^[39] который утверждает, что дважды стохастическая матрица получается из любой квадратной матрицы со всеми положительными элементами посредством итеративного процесса чередования нормализации строк и столбцов. Таким образом, алгоритм записывается так:^[39]

алгоритм RPM2D${ displaystyle ({ mathcal {M}}, { mathcal {S}})}$    т := 0    ${ displaystyle a,  theta, b, c: = 0}$    ${ displaystyle  beta: =  beta _ {0}}$    ${ displaystyle { hat { mu}} _ {ij}: = 1+  epsilon}$    пока ${ displaystyle  beta < beta _ {f}}$:        пока μ не сошлись: // обновляем параметры корреспонденции с помощью softassign            ${ displaystyle Q_ {ij}: = - { frac { partial  operatorname {cost}} { partial  mu _ {ij}}}}$            ${ displaystyle  mu _ {ij} ^ {0}: =  exp ( beta Q_ {ij})}$            // применяем метод Синхорна            пока ${ displaystyle { hat { mu}}}$ не сошлись:                // Обновить ${ displaystyle { hat { mu}}}$ путем нормализации по всем строкам:                ${ displaystyle { hat { mu}} _ {ij} ^ {1}: = { frac {{ hat { mu}} _ {ij} ^ {0}} { sum _ {i = 1 } ^ {M + 1} { hat { mu}} _ {ij} ^ {0}}}}$                // Обновить ${ displaystyle { hat { mu}}}$ путем нормализации по всем столбцам:                ${ displaystyle { hat { mu}} _ {ij} ^ {0}: = { frac {{ hat { mu}} _ {ij} ^ {1}} { sum _ {j = 1 } ^ {N + 1} { hat { mu}} _ {ij} ^ {1}}}}$            // обновляем параметры позы по координатному спуску            Обновить θ с помощью обновления аналитического решения т с помощью обновления аналитического решения а, б, в с помощью Метод Ньютона        ${ displaystyle  beta: =  beta _ {r}  beta}$        ${ displaystyle  gamma: = { frac { gamma} { beta _ {r}}}}$    возвращаться а, б, в, θ и т

где детерминированный параметр управления отжигом ${ displaystyle beta}$ изначально установлен на ${ displaystyle beta _ {0}}$ и увеличивается в раз ${ displaystyle beta _ {r}}$ пока не достигнет максимального значения ${ displaystyle beta _ {f}}$. Суммирование шагов нормализации в сумме дает ${ displaystyle M + 1}$ и ${ displaystyle N + 1}$ вместо просто ${ displaystyle M}$ и ${ displaystyle N}$ потому что ограничения на ${ displaystyle mu}$ неравенства. Таким образом ${ displaystyle M + 1}$й и ${ displaystyle N + 1}$th элементы слабые переменные.

Алгоритм также может быть расширен для наборов точек в 3D или более высоких измерениях. Ограничения на матрицу соответствия ${ Displaystyle mathbf { mu}}$ в случае 3D такие же, как и в случае 2D. Следовательно, структура алгоритма остается неизменной, с основным отличием в том, как решаются матрицы поворота и сдвига.^[39]

Тонкая пластина, шлицы, надежное согласование точек

Анимация 2D нежесткой регистрации набора зеленой точки ${ Displaystyle { mathcal {M}}}$ на набор пурпурных точек ${ Displaystyle { mathcal {S}}}$ испорчен шумными выбросами. Размер синих кружков обратно пропорционален управляющему параметру. ${ displaystyle beta}$. Желтые линии обозначают соответствие.

Алгоритм согласования устойчивых точек тонких пластин (TPS-RPM), разработанный Чуи и Рангараджаном, дополняет метод RPM для выполнения нежесткой регистрации путем параметризации преобразования как шлиц тонкой пластины.^[14]Однако, поскольку параметризация тонкой пластинки существует только в трех измерениях, метод не может быть расширен на задачи, включающие четыре или более измерений.

Корреляция ядра

Подход на основе ядерной корреляции (KC) регистрации набора точек был введен Цином и Канаде.^[37]По сравнению с ICP алгоритм KC более устойчив к зашумленным данным. В отличие от ICP, где для каждой точки модели учитывается только ближайшая точка сцены, здесь каждая точка сцены влияет на каждую точку модели.^[37] Таким образом, это многосвязный алгоритм регистрации. Для некоторых функция ядра ${ displaystyle K}$, корреляция ядра ${ displaystyle KC}$ двух точек ${ displaystyle x_ {i}, x_ {j}}$ определяется так:^[37]

${ Displaystyle KC (x_ {i}, x_ {j}) = int K (x, x_ {i}) cdot K (x, x_ {j}) dx}$

(kc.1)

В функция ядра ${ displaystyle K}$ для регистрации набора точек обычно выбирается симметричное неотрицательное ядро, подобное тем, которые используются в Окно Парзена оценка плотности. В Гауссово ядро обычно используется из-за своей простоты, хотя другие, такие как Ядро Епанечникова и ядро ​​трикуба может быть заменено.^[37] Корреляция ядра всего набора точек ${ Displaystyle { mathcal { chi}}}$ определяется как сумма корреляций ядра каждой точки в наборе с каждой другой точкой в ​​наборе:^[37]

${ displaystyle KC ({ mathcal {X}}) = sum _ {i neq j} KC (x_ {i}, x_ {j}) = 2 sum _ {i$

(kc.2)

Логарифм KC набора точек пропорционален с точностью до постоянного множителя информационная энтропия. Заметьте, что KC является мерой «компактности» набора точек - тривиально, если бы все точки в наборе точек находились в одном и том же месте, KC оценил бы большое значение. В функция стоимости алгоритма регистрации набора точек для некоторого параметра преобразования ${ displaystyle theta}$ определяется так:

${ displaystyle operatorname {cost} ({ mathcal {S}}, { mathcal {M}}, theta) = - sum _ {m in { mathcal {M}}} sum _ {s in { mathcal {S}}} KC (s, T (m, theta))}$

(kc.3)

Некоторые алгебраические манипуляции дают:

${ displaystyle KC ({ mathcal {S}} cup T ({ mathcal {M}}, theta)) = KC ({ mathcal {S}}) + KC (T ({ mathcal {M}) }, theta)) - 2 operatorname {cost} ({ mathcal {S}}, { mathcal {M}}, theta)}$

(kc.4)

Выражение упрощается, если заметить, что ${ displaystyle KC ({ mathcal {S}})}$ не зависит от ${ displaystyle theta}$. Кроме того, предполагая жесткую регистрацию, ${ Displaystyle KC (Т ({ mathcal {M}}, theta))}$ инвариантен, когда ${ displaystyle theta}$ изменяется, потому что евклидово расстояние между каждой парой точек остается неизменным под жесткая трансформация. Таким образом, приведенное выше уравнение можно переписать как:

${ displaystyle KC ({ mathcal {S}} cup T ({ mathcal {M}}, theta)) = C-2 operatorname {cost} ({ mathcal {S}}, { mathcal { M}}, theta)}$

(kc.5)

В оценки плотности ядра определяются как:

${ displaystyle P _ { mathcal {M}} (x, theta) = { frac {1} {M}} sum _ {m in { mathcal {M}}} K (x, T (m , theta))}$

${ displaystyle P _ { mathcal {S}} (x) = { frac {1} {N}} sum _ {s in { mathcal {S}}} K (x, s)}$

Затем можно показать, что функция стоимости является корреляцией двух оценок плотности ядра:

${ displaystyle operatorname {cost} ({ mathcal {S}}, { mathcal {M}}, theta) = - N ^ {2} int _ {x} P _ { mathcal {M}} cdot P _ { mathcal {S}} ~ dx}$

(kc.6)

Создав функция стоимости, алгоритм просто использует градиентный спуск найти оптимальное преобразование. Вычисление функции стоимости с нуля на каждой итерации требует больших затрат вычислительных ресурсов, поэтому дискретная версия функции стоимости Уравнение (kc.6) используется. Оценки плотности ядра ${ Displaystyle P _ { mathcal {M}}, P _ { mathcal {S}}}$ могут быть оценены в точках сетки и сохранены в Справочная таблица. В отличие от ICP и связанных с ним методов, нет необходимости находить ближайшего соседа, что позволяет алгоритму KC быть сравнительно простым в реализации.

По сравнению с ICP и EM-ICP для зашумленных наборов точек 2D и 3D, алгоритм KC менее чувствителен к шуму и чаще приводит к правильной регистрации.^[37]

Модель гауссовой смеси

Оценки плотности ядра представляют собой суммы гауссианов и поэтому могут быть представлены как Модели гауссовой смеси (GMM).^[40] Цзянь и Вемури используют версию GMM алгоритма регистрации KC для выполнения нежесткой регистрации, параметризованной шлицы тонкой пластины.

Когерентный дрейф точки

Жесткая (с добавлением масштабирования) регистрация набора синей точки ${ Displaystyle { mathcal {M}}}$ к набору красной точки ${ Displaystyle { mathcal {S}}}$ с использованием алгоритма когерентного дрейфа точки. Оба набора точек были повреждены удаленными точками и случайными ложными выбросами.

Аффинная регистрация множества синей точки ${ Displaystyle { mathcal {M}}}$ к набору красной точки ${ Displaystyle { mathcal {S}}}$ с использованием алгоритма когерентного дрейфа точки.

Нежесткая регистрация набора синей точки ${ Displaystyle { mathcal {M}}}$ к набору красной точки ${ Displaystyle { mathcal {S}}}$ с использованием алгоритма когерентного дрейфа точки. Оба набора точек были повреждены удаленными точками и случайными ложными выбросами.

Когерентный дрейф точки (CPD) был представлен Мироненко и Сонг.^[13][41]Алгоритм использует вероятностный подход к выравниванию наборов точек, аналогичный методу GMM KC. В отличие от более ранних подходов к нежесткой регистрации, которые предполагали шлиц тонкой пластины Модель трансформации, CPD не зависит от используемой модели трансформации. Набор точек ${ Displaystyle { mathcal {M}}}$ представляет Модель гауссовой смеси (GMM) центроиды. Когда два набора точек оптимально выровнены, соответствие является максимумом GMM. апостериорная вероятность для данной точки данных. Чтобы сохранить топологическую структуру наборов точек, центроиды GMM вынуждены двигаться когерентно как группа. В максимизация ожидания алгоритм используется для оптимизации функции стоимости.^[13]

Пусть будет M указывает в ${ Displaystyle { mathcal {M}}}$ и N указывает в ${ Displaystyle { mathcal {S}}}$. GMM функция плотности вероятности на точку s является:

${ Displaystyle p (s) = сумма _ {я = 1} ^ {M + 1} P (i) p (s | i)}$

(cpd.1)

в которой D размеры, ${ displaystyle p (s | i)}$ это Гауссово распределение по центру ${ displaystyle m_ {i} in { mathcal {M}}}$.

${ displaystyle p (s | i) = { frac {1} {(2 pi sigma ^ {2}) ^ {D / 2}}} exp { left (- { frac { lVert s -m_ {i} rVert ^ {2}} {2 sigma ^ {2}}} right)}}$

Вероятности членства ${ Displaystyle P (я) = { гидроразрыва {1} {M}}}$ одинаков для всех компонентов GMM. Вес равномерного распределения обозначается как ${ Displaystyle ш в [0,1]}$. Тогда модель смеси выглядит так:

${ displaystyle p (s) = w { frac {1} {N}} + (1-w) sum _ {i = 1} ^ {M} { frac {1} {M}} p (s | i)}$

(cpd.2)

Центроиды GMM повторно параметризованы набором параметров ${ displaystyle theta}$ оценивается путем максимизации вероятности. Это эквивалентно минимизации отрицательного функция логарифмического правдоподобия:

${ displaystyle E ( theta, sigma ^ {2}) = - sum _ {j = 1} ^ {N} log sum _ {i = 1} ^ {M + 1} P (i) p (s | i)}$

(cpd.3)

где предполагается, что данные независимые и одинаково распределенные. Вероятность соответствия между двумя точками ${ displaystyle m_ {i}}$ и ${ displaystyle s_ {j}}$ определяется как апостериорная вероятность центроида GMM с учетом точки данных:

${ Displaystyle P (я | s_ {j}) = { frac {P (i) p (s_ {j} | i)} {p (s_ {j})}}}$

В максимизация ожидания (EM) алгоритм используется для поиска ${ displaystyle theta}$ и ${ displaystyle sigma ^ {2}}$. Алгоритм EM состоит из двух шагов. Сначала в шаге E или оценка шаг, он угадывает значения параметров («старые» значения параметров), а затем использует Теорема Байеса для вычисления апостериорного распределения вероятностей ${ displaystyle P ^ { text {old}} (я, s_ {j})}$ компонентов смеси. Во-вторых, в M-шаге или максимизация На шаге «новые» значения параметров затем находятся путем минимизации математического ожидания полной отрицательной функции логарифмического правдоподобия, то есть функции стоимости:

${ displaystyle operatorname {cost} = - sum _ {j = 1} ^ {N} sum _ {i = 1} ^ {M + 1} P ^ { text {old}} (i | s_ { j}) log (P ^ { text {new}} (i) p ^ { text {new}} (s_ {j} | i))}$

(cpd.4)

Игнорирование констант, не зависящих от ${ displaystyle theta}$ и ${ displaystyle sigma}$, Уравнение (cpd.4) можно выразить так:

${ displaystyle operatorname {cost} ( theta, sigma ^ {2}) = { frac {1} {2 sigma ^ {2}}} sum _ {j = 1} ^ {N} sum _ {i = 1} ^ {M + 1} P ^ { text {old}} (i | s_ {j}) lVert s_ {j} -T (m_ {i}, theta) rVert ^ { 2} + { frac {N _ { mathbf {P}} D} {2}} log { sigma ^ {2}}}$

(cpd.5)

куда

${ displaystyle N _ { mathbf {P}} = sum _ {j = 0} ^ {N} sum _ {i = 0} ^ {M} P ^ { text {old}} (i | s_ { j}) leq N}$

с ${ Displaystyle N = N _ { mathbf {P}}}$ только если ${ displaystyle w = 0}$. Апостериорные вероятности компонентов GMM, вычисленные с использованием предыдущих значений параметров ${ displaystyle P ^ { text {old}}}$ является:

${ displaystyle P ^ { text {old}} (i | s_ {j}) = { frac { exp left (- { frac {1} {2 sigma ^ {{ text {old}}) 2}}} lVert s_ {j} -T (m_ {i}, theta ^ { text {old}}) rVert ^ {2} right)} { sum _ {k = 1} ^ { M} exp left (- { frac {1} {2 sigma ^ {{ text {old}} 2}}} lVert s_ {j} -T (m_ {k}, theta ^ { текст {старый}}) rVert ^ {2} right) + (2 pi sigma ^ {2}) ^ { frac {D} {2}} { frac {w} {1-w}} { frac {M} {N}}}}}$

(cpd.6)

Минимизация функции стоимости в уравнении (cpd.5) обязательно уменьшает отрицательную функцию логарифмического правдоподобия E в уравнении (cpd.3), если это уже не локальный минимум.^[13] Таким образом, алгоритм может быть выражен с помощью следующего псевдокода, где точка задает ${ Displaystyle { mathcal {M}}}$ и ${ Displaystyle { mathcal {S}}}$ представлены как ${ Displaystyle M раз D}$ и ${ Displaystyle N раз D}$ матрицы ${ displaystyle mathbf {M}}$ и ${ displaystyle mathbf {S}}$ соответственно:^[13]

алгоритм CPD${ displaystyle ({ mathcal {M}}, { mathcal {S}})}$    ${ displaystyle  theta: =  theta _ {0}}$    инициализировать ${ Displaystyle 0  Leq ш  Leq 1}$    ${ displaystyle  sigma ^ {2}: = { frac {1} {DNM}}  sum _ {j = 1} ^ {N}  sum _ {i = 1} ^ {M}  lVert s_ {j } -m_ {i}  rVert ^ {2}}$    пока не зарегистрирован: // E-шаг, вычислить п        за ${ Displaystyle я  в [1, М]}$ и ${ displaystyle j  in [1, N]}$:            ${ displaystyle p_ {ij}: = { frac { exp  left (- { frac {1} {2  sigma ^ {2}}}  lVert s_ {j} -T (m_ {i},  theta)  rVert ^ {2}  right)} { sum _ {k = 1} ^ {M}  exp  left (- { frac {1} {2  sigma ^ {2}}}  lVert s_ {j} -T (m_ {k},  theta)  rVert ^ {2}  right) + (2  pi  sigma ^ {2}) ^ { frac {D} {2}} { frac { ш} {1-нед}} { frac {M} {N}}}}}$        // M-шаг, решение для оптимального преобразования        ${ Displaystyle  lbrace  theta,  sigma ^ {2}  rbrace: =  mathbf {решать} ( mathbf {S},  mathbf {M},  mathbf {P})}$    возвращаться θ

где вектор ${ displaystyle mathbf {1}}$ - вектор-столбец из единиц. В решать функция зависит от типа выполненной регистрации. Например, при жесткой регистрации на выходе получается шкала а, матрица вращения ${ displaystyle mathbf {R}}$, и вектор перевода ${ Displaystyle mathbf {т}}$. Параметр ${ displaystyle theta}$ можно записать как кортеж из них:

${ displaystyle theta = lbrace a, mathbf {R}, mathbf {t} rbrace}$

который инициализируется единицей, единичная матрица, и вектор-столбец из нулей:

${ displaystyle theta _ {0} = lbrace 1, mathbf {I}, mathbf {0} rbrace}$

Набор выровненных точек:

${ Displaystyle Т ( mathbf {M}) = а mathbf {M} mathbf {R} ^ {T} + mathbf {1} mathbf {t} ^ {T}}$

В Solve_rigid Тогда функция жесткой регистрации может быть записана следующим образом, с выводом алгебры, объясненным в статье Мироненко 2010 года.^[13]

Solve_rigid${ Displaystyle ( mathbf {S},  mathbf {M},  mathbf {P})}$    ${ Displaystyle N _ { mathbf {P}}: =  mathbf {1} ^ {T}  mathbf {P}  mathbf {1}}$    ${ displaystyle  mu _ {s}: = { frac {1} {N _ { mathbf {P}}}}  mathbf {S} ^ {T}  mathbf {P} ^ {T}  mathbf {1 }}$    ${ displaystyle  mu _ {m}: = { frac {1} {N _ { mathbf {P}}}}  mathbf {M} ^ {T}  mathbf {P}  mathbf {1}}$    ${ displaystyle { hat { mathbf {S}}}: =  mathbf {S} -  mathbf {1}  mu _ {s} ^ {T}}$    ${ displaystyle { hat { mathbf {M}}}: =  mathbf {M} -  mathbf {1}  mu _ {m} ^ {T}}$    ${ displaystyle  mathbf {A}: = { hat { mathbf {S} ^ {T}}}  mathbf {P} ^ {T} { hat { mathbf {M}}}}$    ${ Displaystyle  mathbf {U},  mathbf {V}: =  mathbf {svd} ( mathbf {A})}$ // разложение по сингулярным числам из ${ Displaystyle  mathbf {A} =  mathbf {U}  Sigma  mathbf {V} ^ {T}}$    ${ displaystyle  mathbf {C}: =  operatorname {diag} (1, ..., 1,  det ( mathbf {UV} ^ {T}))}$ // диаг (ξ) это диагональная матрица сформированный из вектора ξ    ${ Displaystyle  mathbf {R}: =  mathbf {UCV} ^ {T}}$    ${ displaystyle a: = { frac { operatorname {tr} ( mathbf {A} ^ {T}  mathbf {R})} { operatorname {tr} ( mathbf {{ hat { mathbf {M }}} ^ {T}  operatorname {diag} ( mathbf {P}  mathbf {1}) { hat { mathbf {M}}}})}}}$ // tr это след матрицы    ${ displaystyle  mathbf {t}: =  mu _ {s} -a  mathbf {R}  mu _ {m}}$    ${ displaystyle  sigma ^ {2}: = { frac {1} {N _ { mathbf {P}} D}} ( operatorname {tr} ( mathbf {{ hat { mathbf {S}}}) ^ {T}  operatorname {diag} ( mathbf {P} ^ {T}  mathbf {1}) { hat { mathbf {S}}}}) -a  operatorname {tr} ( mathbf {A } ^ {T}  mathbf {R}))}$    возвращаться ${ displaystyle  lbrace a,  mathbf {R},  mathbf {t}  rbrace,  sigma ^ {2}}$

Для аффинной регистрации, цель которой - найти аффинное преобразование вместо жесткого на выходе получается матрица аффинного преобразования ${ displaystyle mathbf {B}}$ и перевод ${ Displaystyle mathbf {т}}$ таким образом, что набор выровненных точек:

${ Displaystyle Т ( mathbf {M}) = mathbf {M} mathbf {B} ^ {T} + mathbf {1} mathbf {t} ^ {T}}$

В решить_affine Тогда функция жесткой регистрации может быть записана следующим образом, с выводом алгебры, объясненным в статье Мироненко 2010 года.^[13]

решить_affine${ Displaystyle ( mathbf {S},  mathbf {M},  mathbf {P})}$    ${ Displaystyle N _ { mathbf {P}}: =  mathbf {1} ^ {T}  mathbf {P}  mathbf {1}}$    ${ displaystyle  mu _ {s}: = { frac {1} {N _ { mathbf {P}}}}  mathbf {S} ^ {T}  mathbf {P} ^ {T}  mathbf {1 }}$    ${ displaystyle  mu _ {m}: = { frac {1} {N _ { mathbf {P}}}}  mathbf {M} ^ {T}  mathbf {P}  mathbf {1}}$    ${ displaystyle { hat { mathbf {S}}}: =  mathbf {S} -  mathbf {1}  mu _ {s} ^ {T}}$    ${ displaystyle { hat { mathbf {M}}}: =  mathbf {M} -  mathbf {1}  mu _ {s} ^ {T}}$    ${ displaystyle  mathbf {B}: = ({ hat { mathbf {S} ^ {T}}}  mathbf {P} ^ {T} { hat { mathbf {M}}}) ({ шляпа { mathbf {M} ^ {T}}}  operatorname {diag} ( mathbf {P}  mathbf {1}) { hat { mathbf {M}}}) ^ {- 1}}$    ${ displaystyle  mathbf {t}: =  mu _ {s} -  mathbf {B}  mu _ {m}}$    ${ displaystyle  sigma ^ {2}: = { frac {1} {N _ { mathbf {P}} D}} ( operatorname {tr} ({ hat { mathbf {S} ^ {T}}) }  operatorname {diag} ( mathbf {P} ^ {T}  mathbf {1}) { hat { mathbf {S}}}) -  operatorname {tr} ({ hat { mathbf {S}) ^ {T}}}  mathbf {P} ^ {T} { hat { mathbf {M}}}  mathbf {B} ^ {T}))}$    возвращаться ${ Displaystyle  { mathbf {B},  mathbf {t} },  sigma ^ {2}}$

Также можно использовать CPD с нежесткой регистрацией, используя параметризацию, полученную с помощью вариационное исчисление.^[13]

Суммы гауссовых распределений могут быть вычислены в линейное время с использованием быстрое преобразование Гаусса (FGT).^[13] Следовательно, временная сложность CPD составляет ${ Displaystyle О (М + N)}$, что асимптотически намного быстрее, чем ${ displaystyle O (MN)}$ методы.^[13]

Сортировка пространства корреспонденции (SCS)

Этот алгоритм был представлен в 2013 году Х. Ассалихом для регистрации изображений сонара.^[42] Эти типы изображений, как правило, имеют большое количество шумов, поэтому ожидается, что в наборах точек будет много выбросов. SCS обеспечивает высокую устойчивость к выбросам и может превосходить показатели ICP и CPD при наличии выбросов. SCS не использует итеративную оптимизацию в многомерном пространстве и не является ни вероятностным, ни спектральным. SCS может соответствовать жестким и нежестким преобразованиям и лучше всего работает, когда целевое преобразование составляет от трех до шести. степени свободы.

Байесовский когерентный дрейф точки (BCPD)

Вариант когерентного дрейфа точки, называемый байесовским когерентным дрейфом точки (BCPD), был получен с помощью байесовской формулировки регистрации набора точек.^[43]BCPD имеет несколько преимуществ перед CPD, например, (1) нежесткая и жесткая регистрация может выполняться в одном алгоритме, (2) алгоритм может быть ускорен независимо от гауссовости матрицы Грама для определения согласованности движения, (3) алгоритм более устойчив к выбросам из-за более разумного определения распределения выбросов. Кроме того, в байесовской формулировке согласованность движения вводилась через предварительное распределение векторов смещения, обеспечивая четкую разницу между параметрами настройки, которые управляют согласованностью движения.

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

• Сопоставление точечных объектов

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