Регистрация набора точек

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

В компьютерном зрении , распознавании образов робототехнике регистрация и набора точек , также известная как регистрация облака точек или сопоставление сканов , представляет собой процесс поиска пространственного преобразования ( например, масштабирования , вращения и перемещения ), которое выравнивает два облака точек . Цель поиска такого преобразования включает в себя объединение нескольких наборов данных в глобально согласованную модель (или систему координат) и сопоставление нового измерения с известным набором данных для идентификации функций или оценки их положения . Необработанные данные трехмерного облака точек обычно получают с помощью лидаров и камер RGB-D . Трехмерные облака точек также могут быть созданы с помощью алгоритмов компьютерного зрения, таких как триангуляция , корректировка пучков и, в последнее время, оценка глубины монокулярного изображения с использованием глубокого обучения . Для регистрации набора 2D-точек, используемой при обработке изображений и регистрации изображений на основе признаков , набор точек может представлять собой 2D-координаты пикселей, полученные путем извлечения признаков из изображения, например, обнаружения углов . Регистрация облака точек имеет широкое применение в автономное вождение , оценка движения и 3D-реконструкция , обнаружение объекта и оценка позы , роботизированные манипуляции , одновременная локализация и картографирование (SLAM), сшивка панорамы , виртуальная и дополненная реальность , и медицинская визуализация .

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

Формулировка

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

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

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

$T({\mathcal {M}})$ ( 1 )

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

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

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

$\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 s-m\Vert _{2}^{2}$ ( 3 )

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

Типы алгоритмов

Когда соответствия ( т. е. $s_{m}\leftrightarrow m$) задаются перед оптимизацией, например, с использованием методов сопоставления признаков , тогда оптимизации необходимо только оценить преобразование. Такой вид регистрации называется заочной регистрацией . С другой стороны, если соответствия неизвестны, то требуется оптимизация для совместного нахождения соответствий и преобразования вместе. Этот тип регистрации называется одновременной регистрацией позы и соответствия .

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

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

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

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

Учитывая два набора точек, нежесткая регистрация дает нежесткое преобразование, которое сопоставляет один набор точек с другим. Нежесткие преобразования включают аффинные преобразования, такие как масштабирование и сдвиговое отображение . Однако в контексте регистрации набора точек нежесткая регистрация обычно включает нелинейное преобразование. Если собственные формы изменения множества точек, нелинейное преобразование может быть параметризовано собственными значениями. известны Нелинейное преобразование также можно параметризовать как сплайн тонкой пластины .

Другие типы

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

PCL (Библиотека облаков точек) — это платформа с открытым исходным кодом для n-мерного облака точек и обработки трехмерной геометрии. Он включает в себя несколько алгоритмов регистрации точек.

Заочная регистрация

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

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

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

$s_{i}=lRm_{i}+t+\epsilon _{i},i=1,\dots ,N$ ( cб.1 )

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

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

Обратите внимание, что когда масштабный коэффициент равен 1, а вектор перевода равен нулю, оптимизация восстанавливает формулировку задачи Вахбы . Несмотря на невыпуклость оптимизации ( cb.2 ) из-за невыпуклости множества ${\text{SO}}(3)$, плодотворная работа Бертольда К.П. Хорна показала, что ( cb.2 ) фактически допускает решение в замкнутой форме за счет разделения оценки масштаба, вращения и перемещения. Аналогичные результаты были получены Аруном и др . Кроме того, чтобы найти уникальное преобразование $(l,R,t)$, по меньшей мере $N=3$ Требуются неколлинеарные точки в каждом наборе точек.

Совсем недавно Бриалес и Гонсалес-Хименес разработали полуопределенную релаксацию с использованием лагранжевой двойственности для случая, когда модельный набор ${\mathcal {M}}$ содержит различные 3D-примитивы, такие как точки, линии и плоскости (это тот случай, когда модель ${\mathcal {M}}$ is a 3D mesh). Интересно, что полуопределенная релаксация является эмпирически точной, т. е. достоверно глобально оптимальное из решения полуопределенной релаксации можно получить решение.

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

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

$s_{i}={\begin{cases}lRm_{i}+t+\epsilon _{i}&{\text{if }}i-{\text{th pair is an inlier}}\\o_{i}&{\text{if }}i-{\text{th pair is an outlier}}\end{cases}}$ ( cб.3 )

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

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

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

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

$\max _{l>0,R\in {\text{SO}}(3),t\in \mathbb {R} ^{3},{\mathcal {I}}}\vert {\mathcal {I}}\vert ,\quad {\text{subject to }}{\frac {1}{\sigma _{i}^{2}}}\Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}\leq \xi ,\forall i\in {\mathcal {I}}$ ( cб.4 )

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

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

Чтобы заполнить пробел между быстрой, но неточной схемой RANSAC и точной, но исчерпывающей оптимизацией BnB, недавние исследования разработали детерминированные приближенные методы для решения задачи максимизации консенсуса.

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

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

Парра и др. предложили метод под названием «Гарантированное удаление выбросов» (GORE), который использует геометрические ограничения для удаления выбросов, гарантируя при этом сохранение выбросов. Было показано, что GORE способен радикально снизить коэффициент выбросов, что может значительно повысить производительность максимизации консенсуса с использованием RANSAC или BnB. Ян и Карлоне предложили построить парные измерения, инвариантные к сдвигу и вращению (TRIM), из исходного набора измерений и встроить TRIM в качестве ребер графа, узлами которого являются трехмерные точки. Поскольку вставки попарно согласованы с точки зрения масштаба, они должны образовывать клику внутри графа. Следовательно, использование эффективных алгоритмов вычисления максимальной клики графа позволяет найти вкрапления и эффективно удалить выбросы. Также показано, что метод удаления выбросов на основе максимальной клики весьма полезен в реальных задачах регистрации набора точек. Подобные идеи удаления выбросов были также предложены Parra et al. .

M-оценка

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

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

где $\rho (\cdot )$ представляет собой выбор робастной функции стоимости. Обратите внимание, что выбор $\rho (x)=x^{2}$ восстанавливает оценку методом наименьших квадратов в ( cb.2 ). Популярные надежные функции стоимости включают в себя $\ell _{1}$-нормальная потеря, потеря Губера , Поражение Джемана-МакКлюра и усеченная потеря по методу наименьших квадратов . М-оценка была одной из самых популярных парадигм надежной оценки в робототехнике и компьютерном зрении. Поскольку надежные целевые функции обычно невыпуклы ( например, усеченная потеря по методу наименьших квадратов по сравнению с потерей по методу наименьших квадратов), алгоритмы решения невыпуклой M-оценки обычно основаны на локальной оптимизации , где сначала предоставляется начальное предположение, а затем путем итеративных уточнений преобразования, чтобы продолжать уменьшать целевую функцию. Локальная оптимизация имеет тенденцию работать хорошо, когда начальное предположение близко к глобальному минимуму, но она также склонна застревать в локальных минимумах, если обеспечивается плохая инициализация.

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

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

$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)$ ( cб.6 )

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

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

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

Совсем недавно Ян и др. разработал первый сертифицированный надежный алгоритм регистрации, получивший название « Оценка усеченных наименьших квадратов и полуопределенная релаксация» (TEASER). Для регистрации облака точек TEASER не только выводит оценку преобразования, но также количественно определяет оптимальность данной оценки. TEASER использует следующую оценку методом усеченных наименьших квадратов (TLS):

$l^{\star },R^{\star },t^{\star }=\arg \min _{l>0,R\in {\text{SO}}(3),t\in \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)$ ( cб.7 )

который получается путем выбора робастной функции стоимости TLS $\rho (x)=\min(x^{2},{\bar {c}}^{2})$, где ${\bar {c}}^{2}$— это предопределенная константа, определяющая максимально допустимые остатки, которые считаются вкраплениями. Целевая функция TLS обладает тем свойством, что для внутренних соответствий ( $\Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}<{\bar {c}}^{2}$), применяется обычный штраф наименьших квадратов; в то время как для выбросов выбросов ( $\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), где релаксация на практике точен, даже при большом количестве выбросов; Проблема перевода TLS может быть решена с помощью покомпонентного адаптивного голосования. Быстрая реализация с использованием GNC находится в открытом доступе здесь . На практике TEASER может выдержать более $99\%$ выбросы соответствия и выполняются в миллисекундах.

Помимо разработки TEASER, Yang et al. также докажите, что при некоторых мягких условиях на данных облака точек предполагаемое преобразование TEASER имеет ограниченные ошибки по сравнению с фактическим преобразованием.

Одновременная регистрация позы и соответствия

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

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

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

algorithm ICP(M, S)
    θ := θ0
    while not registered:
        X := ∅
        for mi ∊ T(M, θ):
            ŝi := closest point in S to mi
            X := X + ⟨mi, ŝi⟩
        θ := least_squares(X)
    return θ

Здесь функция least_squares выполняет оптимизацию методом наименьших квадратов , чтобы минимизировать расстояние в каждом из $\langle m_{i},{\hat {s}}_{i}\rangle$ пары, используя решения Хорна в замкнутой форме и Арун.

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

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

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

$\mu _{ij}={\begin{cases}1&{\text{if point }}m_{i}{\text{ corresponds to point }}s_{j}\\0&{\text{otherwise}}\end{cases}}$ ( об/мин.1 )

Тогда проблема определяется следующим образом: Учитывая два набора точек ${\mathcal {M}}$ и ${\mathcal {S}}$ найти аффинное преобразование $T$ и матрица совпадений $\mathbf {\mu }$ это лучше всего их связывает. Зная оптимальное преобразование, можно легко определить матрицу соответствия и наоборот. Однако алгоритм RPM определяет оба одновременно. Преобразование можно разложить на вектор перемещения и матрицу преобразования:

$T(m)=\mathbf {A} m+\mathbf {t}$

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

$\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 )

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

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

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

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

$\mu _{\hat {j}}={\frac {\exp {(\beta Q_{\hat {j}})}}{\sum _{j=1}^{J}\exp {(\beta Q_{j})}}}$ ( об/мин.3 )

это известно как функция softmax . Как $\beta$ увеличивается, оно приближается к двоичному значению, как это требуется в уравнении ( rpm.1 ). Теперь проблему можно обобщить на двумерный случай, где вместо максимизации ${\textstyle \sum _{j=1}^{J}\mu _{j}Q_{j}}$, максимизируется следующее:

$E(\mu )=\sum _{j=1}^{N}\sum _{i=0}^{M}\mu _{ij}Q_{ij}$ ( об/мин.4 )

где

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

Это просто, за исключением того, что теперь ограничения на $\mu$ являются дважды стохастическим матричными ограничениями: ${\textstyle \forall j~\sum _{i=1}^{M}\mu _{ij}=1}$ и ${\textstyle \forall i~\sum _{j=1}^{N}\mu _{ij}=1}$. Таким образом, знаменатель из уравнения ( rpm.3 ) не может быть просто выражен для двумерного случая. Для удовлетворения ограничений можно использовать результат Синкхорна: в котором говорится, что дважды стохастическая матрица получается из любой квадратной матрицы со всеми положительными элементами с помощью итерационного процесса чередующейся нормализации строк и столбцов. Таким образом, алгоритм записывается так:

algorithm RPM2D$({\mathcal {M}},{\mathcal {S}})$
    t := 0
    a, θ b, c := 0
    β := β0
    ${\hat {\mu }}_{ij}:=1+\epsilon$
    while β < βf:
        while μ has not converged:
            // update correspondence parameters by softassign
            $Q_{ij}:=-{\frac {\partial \operatorname {cost} }{\partial \mu _{ij}}}$
            $\mu _{ij}^{0}:=\exp(\beta Q_{ij})$
            // apply Sinkhorn's method
            while ${\hat {\mu }}$ has not converged:
                // update ${\hat {\mu }}$ by normalizing across all rows:
                ${\hat {\mu }}_{ij}^{1}:={\frac {{\hat {\mu }}_{ij}^{0}}{\sum _{i=1}^{M+1}{\hat {\mu }}_{ij}^{0}}}$
                // update ${\hat {\mu }}$ by normalizing across all columns:
                ${\hat {\mu }}_{ij}^{0}:={\frac {{\hat {\mu }}_{ij}^{1}}{\sum _{j=1}^{N+1}{\hat {\mu }}_{ij}^{1}}}$
            // update pose parameters by coordinate descent
            update θ using analytical solution
            update t using analytical solution
            update a, b, c using Newton's method
        $\beta :=\beta _{r}\beta$
        $\gamma :={\frac {\gamma }{\beta _{r}}}$
    return a, b, c, θ and t

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

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

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

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

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

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

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

$KC(x_{i},x_{j})=\int K(x,x_{i})\cdot K(x,x_{j})dx$ ( кс.1 )

ядра Функция $K$ Для регистрации набора точек обычно выбирается симметричное и неотрицательное ядро, подобное тем, которые используются при оценке плотности окна Парцена . Обычно используется ядро ​​Гаусса из-за его простоты, хотя его можно заменить другими ядрами, такими как ядро ​​Епанечникова и трехкубическое ядро. Корреляция ядра всего набора точек ${\mathcal {\chi }}$ определяется как сумма ядерных корреляций каждой точки набора с каждой другой точкой набора:

$KC({\mathcal {X}})=\sum _{i\neq j}KC(x_{i},x_{j})=2\sum _{i<j}KC(x_{i},x_{j})$ ( кс.2 )

Логарифм KC набора точек пропорционален, с точностью до постоянного множителя, информационной энтропии . Обратите внимание, что KC является мерой «компактности» набора точек — тривиально, если бы все точки в наборе точек находились в одном и том же месте, KC имел бы большое значение. Функция стоимости алгоритма регистрации множества точек для некоторого параметра преобразования $\theta$ определяется так:

$\operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )=-\sum _{m\in {\mathcal {M}}}\sum _{s\in {\mathcal {S}}}KC(s,T(m,\theta ))$ ( кс.3 )

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

$KC({\mathcal {S}}\cup T({\mathcal {M}},\theta ))=KC({\mathcal {S}})+KC(T({\mathcal {M}},\theta ))-2\operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )$ ( кс.4 )

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

$KC({\mathcal {S}}\cup T({\mathcal {M}},\theta ))=C-2\operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )$ ( кс.5 )

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

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

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

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

$\operatorname {cost} ({\mathcal {S}},{\mathcal {M}},\theta )=-N^{2}\int _{x}P_{\mathcal {M}}\cdot P_{\mathcal {S}}~dx$ ( кс.6 )

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

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

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

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

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

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

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

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

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

Пусть имеется M точек. ${\mathcal {M}}$ и N точек в ${\mathcal {S}}$. GMM Функция плотности вероятности для точки s :

$p(s)=\sum _{i=1}^{M+1}P(i)p(s|i)$ ( cpd.1 )

где в D измерениях $p(s|i)$ это распределение Гаусса с центром в точке $m_{i}\in {\mathcal {M}}$.

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

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

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

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

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

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

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

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

$\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 )

Игнорирование констант, независимых от $\theta$ и $\sigma$, Уравнение ( cpd.4 ) можно выразить следующим образом:

$\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 )

где

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

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

$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 ^{\text{old}})\rVert ^{2}\right)+(2\pi \sigma ^{2})^{\frac {D}{2}}{\frac {w}{1-w}}{\frac {M}{N}}}}$ ( cpd.6 )

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

algorithm CPD$({\mathcal {M}},{\mathcal {S}})$
    θ := θ0
    initialize 0 ≤ w ≤ 1
    $\sigma ^{2}:={\frac {1}{DNM}}\sum _{j=1}^{N}\sum _{i=1}^{M}\lVert s_{j}-m_{i}\rVert ^{2}$
    while not registered:
        // E-step, compute P
        for i ∊ [1, M] and j ∊ [1, N]:
            $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 {w}{1-w}}{\frac {M}{N}}}}$
        // M-step, solve for optimal transformation
        {θ, σ2} := solve(S, M, P)
    return θ

где вектор $\mathbf {1}$ — вектор-столбец из единиц. solve Функция отличается типом выполняемой регистрации. Например, при жесткой регистрации выходными данными являются масштаб a , матрица вращения. $\mathbf {R}$и вектор перевода $\mathbf {t}$. Параметр $\theta$ можно записать в виде кортежа из них:

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

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

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

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

$T(\mathbf {M} )=a\mathbf {M} \mathbf {R} ^{T}+\mathbf {1} \mathbf {t} ^{T}$

The solve_rigid Функция для жесткой регистрации может быть записана следующим образом, с выводом алгебры, объясненным в статье Мироненко 2010 года.

solve_rigid(S, M, P)
    NP := 1TP1
    $\mu _{s}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {S} ^{T}\mathbf {P} ^{T}\mathbf {1}$
    $\mu _{m}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {M} ^{T}\mathbf {P} \mathbf {1}$
    ${\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}$
    ${\hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}$
    $\mathbf {A} :={\hat {\mathbf {S} ^{T}}}\mathbf {P} ^{T}{\hat {\mathbf {M} }}$
    U, V := svd(A) // the singular value decomposition of A = UΣVT
    C := diag(1, …, 1, det(UVT)) // diag(ξ)is the diagonal matrix formed from vector ξ
    R := UCVT
    $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 is the trace of a matrix
    t := μs − aRμm
    $\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} ))$
    return {a, R, t}, σ2

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

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

The solve_affine Функция для жесткой регистрации может быть записана следующим образом, с выводом алгебры, объясненным в статье Мироненко 2010 года.

solve_affine(S, M, P)
    NP := 1TP1
    $\mu _{s}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {S} ^{T}\mathbf {P} ^{T}\mathbf {1}$
    $\mu _{m}:={\frac {1}{N_{\mathbf {P} }}}\mathbf {M} ^{T}\mathbf {P} \mathbf {1}$
    ${\hat {\mathbf {S} }}:=\mathbf {S} -\mathbf {1} \mu _{s}^{T}$
    ${\hat {\mathbf {M} }}:=\mathbf {M} -\mathbf {1} \mu _{m}^{T}$
    $\mathbf {B} :=({\hat {\mathbf {S} }}^{T}\mathbf {P} ^{T}{\hat {\mathbf {M} }})({\hat {\mathbf {M} }}^{T}\operatorname {diag} (\mathbf {P} \mathbf {1} ){\hat {\mathbf {M} }})^{-1}$
    t := μs − Bμm
    $\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}))$
    return {B, t}, σ2

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

Суммы распределений Гаусса можно вычислить за линейное время с помощью быстрого преобразования Гаусса (FGT). Следовательно, временная сложность CPD равна $O(M+N)$, что асимптотически намного быстрее, чем $O(MN)$ методы.

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

Вариант когерентного смещения точки, называемый байесовским когерентным смещением точки (BCPD), был получен посредством байесовской формулировки регистрации набора точек. BCPD имеет несколько преимуществ перед CPD, например: (1) нежесткая и жесткая регистрация может выполняться в одном алгоритме, (2) алгоритм может быть ускорен независимо от гауссовости матрицы Грама для определения когерентности движения, (3) алгоритм более устойчив к выбросам из-за более разумного определения распределения выбросов. Кроме того, в байесовской формулировке когерентность движения была введена посредством предварительного распределения векторов смещения, обеспечивая четкую разницу между параметрами настройки, которые управляют когерентностью движения. BCPD был дополнительно ускорен с помощью метода под названием BCPD++, который представляет собой трехэтапную процедуру, состоящую из (1) понижения дискретизации наборов точек, (2) регистрации уменьшенных наборов точек и (3) интерполяции поля деформации. Метод может регистрировать наборы точек, состоящие из более чем 10 миллионов точек, сохраняя при этом точность регистрации.

дрейф точки с локальной геометрией поверхности (LSG-

Вариант когерентного дрейфа точек, называемый CPD с локальной геометрией поверхности (LSG-CPD), для жесткой регистрации облака точек. Этот метод адаптивно добавляет различные уровни штрафов между точками и плоскостями поверх штрафов между точками, основанных на плоскостности локальной поверхности. Это приводит к появлению компонентов GMM с анизотропными ковариациями вместо изотропных ковариаций в исходном CPD. Анизотропная ковариационная матрица моделируется как:

$\Sigma _{m}^{-1}={\frac {1}{\sigma ^{2}}}\left(\alpha _{m}\mathbf {n} _{m}\mathbf {n} _{m}^{T}+\mathbf {I} \right)$ ( lsg-cpd.1 )

где

$\alpha _{m}={\frac {1-\exp \left(\lambda \left(3-{\frac {1}{\kappa _{m}}}\right)\right)}{1+\exp \left(\lambda \left(3-{\frac {1}{\kappa _{m}}}\right)\right)}}\alpha _{max}$ ( lsg-cpd.2 )

$\Sigma _{m}$ – анизотропная ковариационная матрица m-й точки целевого набора; $\mathbf {n} _{m}$ – вектор нормали, соответствующий той же точке; $\mathbf {I}$ — это единичная матрица, служащая регуляризатором, устраняющим некорректность задачи. $\alpha _{m}$ — это коэффициент штрафа (модифицированная сигмовидная функция), который устанавливается адаптивно для добавления различных уровней штрафа от точки к плоскости в зависимости от того, насколько плоской является локальная поверхность. Это реализуется путем оценки изменения поверхности $\kappa _{m}$ в окрестности m-й целевой точки. $\alpha _{max}$ является верхней границей штрафа.

Регистрация облака точек формулируется как задача оценки максимального правдоподобия (MLE) и решается с помощью алгоритма максимизации ожидания (EM). На этапе E вычисление соответствия преобразуется в простые матричные манипуляции и эффективно вычисляется на графическом процессоре. На этапе M проводится неограниченная оптимизация матричной группы Ли, позволяющая эффективно обновлять жесткое преобразование регистрации. Используя преимущества локальных геометрических ковариаций, метод демонстрирует превосходную точность и устойчивость к шуму и выбросам по сравнению с базовым CPD. Ожидается повышение производительности во время выполнения благодаря ускорению вычислений соответствия на графическом процессоре. Реализация LSG-CPD находится в открытом доступе здесь .

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

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

См. также

• Сопоставление точечных объектов
• Триангуляция множества точек
• Нормальные распределения преобразуют

Внешние ссылки

• Эталонная реализация надежного сопоставления точек сплайна тонкой пластины
• Эталонная реализация регистрации набора точек корреляции ядра
• Эталонная реализация когерентного дрейфа точки
• Эталонная реализация вариантов ICP
• Эталонная реализация байесовского когерентного дрейфа точки
• Эталонная реализация LSG-CPD