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

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

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

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

Обзор проблемы [ править ]

Проблема может быть резюмирована следующим образом: ^[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 T({\mathcal {M}})}$

( 1 )

Таким образом, результат алгоритма регистрации набора точек является оптимальным преобразованием , которое лучше всего согласовано с некоторым определенным понятием функции расстояния :${\displaystyle T^{\star }}$${\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 s-m\Vert _{2}^{2}}$

( 3 )

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

Жесткая регистрация [ править ]

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

Нежесткая регистрация [ править ]

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

Алгоритмы [ править ]

Некоторые подходы к регистрации набора точек используют алгоритмы, которые решают более общую задачу сопоставления графов . ^[11] Однако вычислительная сложность таких методов, как правило, высока, и они ограничиваются жесткой регистрацией. Алгоритмы, специфичные для задачи регистрации набора точек, описаны в следующих разделах. PCL (точка Облако библиотека) представляет собой каркас с открытым исходным кодом для п-мерного облака точек и 3D обработки геометрии. Он включает в себя несколько алгоритмов регистрации точек. ^[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)}$${\displaystyle {\text{SO}}(d)}$${\displaystyle d}$${\displaystyle t\in \mathbb {R} ^{3}}$${\displaystyle \epsilon _{i}\in \mathbb {R} ^{3}}$ ${\displaystyle \epsilon _{i}}$${\displaystyle \sigma _{i}}$ ${\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\in \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 ) из-за невыпуклости множества , основополагающая работа Бертольда К.П. Хорна показала, что ( cb.2 ) фактически допускает решение в замкнутой форме, путем разделения оценки масштаба, вращение и перевод. ^[16] Подобные результаты были обнаружены Arun et al . ^[17] Кроме того, чтобы найти уникальное преобразование , требуются как минимум неколлинеарные точки в каждом наборе точек.${\displaystyle {\text{SO}}(3)}$${\displaystyle (l,R,t)}$${\displaystyle N=3}$

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

Надежная регистрация [ править ]

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

${\displaystyle 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}}}$

( cb.3 )

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

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

Максимальный консенсус [ править ]

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

${\displaystyle \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}}}$

( cb.4 )

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

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

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

Удаление выбросов [ править ]

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

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

М-оценка [ править ]

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

${\displaystyle 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)}$

( cb.5 )

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

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

Градуированная невыпуклость (GNC) - это универсальная среда для решения невыпуклых задач оптимизации без инициализации. Он добился успеха в приложениях для раннего видения и машинного обучения. ^{[33] [34]} Ключевая идея GNC - решить сложную невыпуклую задачу, начав с простой выпуклой задачи. В частности, для данной устойчивой функции стоимости можно построить суррогатную функцию с гиперпараметром , настройка которого может постепенно увеличивать невыпуклость суррогатной функции до тех пор, пока она не сходится к целевой функции . ^{[34] [35]} Следовательно, на каждом уровне гиперпараметра решается следующая оптимизация:${\displaystyle \rho (\cdot )}$${\displaystyle \rho _{\mu }(\cdot )}$${\displaystyle \mu }$${\displaystyle \rho _{\mu }(\cdot )}$${\displaystyle \rho (\cdot )}$${\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, адаптированную для функции Гемана-МакКлюра, Чжоу и др. разработал алгоритм быстрой глобальной регистрации, устойчивый к выбросам в корреспонденции. ^[30] Совсем недавно Ян и др.${\displaystyle 80\%}$показали, что совместное использование GNC (адаптированной к функции Джемана-МакКлюра и усеченной функции наименьших квадратов) и двойственности Блэка-Рангараджана может привести к универсальному решателю для надежных проблем регистрации, включая облака точек и регистрацию сетки. ^[35]

Гарантированно надежная регистрация [ править ]

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

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

${\displaystyle 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)}$

( CB.7 )

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

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

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

Одновременные позы и методы корреспонденции [ править ]

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

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

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

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

Поскольку функция стоимости регистрации зависит от нахождения ближайшей точки к каждой точке , она может меняться по мере выполнения алгоритма. Таким образом, трудно доказать, что ICP действительно сходится точно к локальному оптимуму. ^[37] Фактически, эмпирически ICP и EM-ICP не сходятся к локальному минимуму функции стоимости. ^[37] Тем не менее, поскольку ICP интуитивно понятен и прост в реализации, он остается наиболее часто используемым алгоритмом регистрации набора точек. ^[37] Было предложено множество вариантов ICP, влияющих на все фазы алгоритма от выбора и сопоставления точек до стратегии минимизации. ^{[13] [38]}${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {M}}}$Например, алгоритм максимизации ожидания применяется к алгоритму 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{ corresponds to point }}s_{j}\\0&{\text{otherwise}}\end{matrix}}\right.}$

(об / мин.1 )

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

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

Матрица в 2D состоит из четырех отдельных параметров , которые представляют собой масштаб, поворот и компоненты вертикального и горизонтального сдвига соответственно. Тогда функция стоимости будет следующей:${\displaystyle \mathbf {A} }$${\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~\sum _{i=1}^{M}\mu _{ij}\leq 1}$${\displaystyle \forall i~\sum _{j=1}^{N}\mu _{ij}\leq 1}$${\displaystyle \forall ij~\mu _{ij}\in \lbrace 0,1\rbrace }$${\displaystyle \alpha }$${\displaystyle g(\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 \sum _{j=1}^{J}\mu _{j}=1}$${\displaystyle \mathbf {\mu } }$${\displaystyle \sum _{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 . По мере увеличения оно приближается к двоичному значению, как требуется в уравнении (об / мин.1 ). Теперь проблема может быть обобщена на 2D-случай, где вместо максимизации максимизируется следующее:${\displaystyle \beta }$${\displaystyle \sum _{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}}}}$

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

алгоритм RPM2D ${\displaystyle ({\mathcal {M}},{\mathcal {S}})}$ t  : = 0  while : пока μ не сошлось :  // обновить параметры соответствия с помощью softassign // применить метод Sinkhorn, пока не сошлось : // обновить путем нормализации по всем строкам: // обновить путем нормализации по всем столбцам: / / обновить параметры позы путем спуска по координатам; обновить θ с помощью аналитического решения.${\displaystyle a,\theta ,b,c:=0}$ ${\displaystyle \beta :=\beta _{0}}$ ${\displaystyle {\hat {\mu }}_{ij}:=1+\epsilon }$  ${\displaystyle \beta <\beta _{f}}$   ${\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}}}}$  обновить t с помощью аналитического решения обновить a, b, c, используя метод Ньютона, вернуть a, b, c, θ и t${\displaystyle \beta :=\beta _{r}\beta }$ ${\displaystyle \gamma :={\frac {\gamma }{\beta _{r}}}}$  

где детерминированный параметр управления отжигом изначально установлен и увеличивается в раз, пока не достигнет максимального значения . Суммирования на этапах нормализации суммируют, а не просто, и потому, что ограничения на них являются неравенствами. Таким образом, элементы th и th являются резервными переменными .${\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}$

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

Устойчивое согласование точек тонких шлицевых пластин [ править ]

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

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

Корреляция ядра [ править ]

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

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

( kc.1 )

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

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

( 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(T({\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 ). Оценки плотности ядра можно оценивать в точках сетки и сохранять в справочной таблице . В отличие от ICP и связанных с ним методов, нет необходимости находить ближайшего соседа, что позволяет алгоритму KC быть сравнительно простым в реализации.${\displaystyle P_{\mathcal {M}},P_{\mathcal {S}}}$

По сравнению с 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 не зависит от используемой модели преобразования. Набор точек представляет собой центроиды модели смеси Гаусса (GMM). Когда два набора точек оптимально выровнены, соответствие является максимумом апостериорной вероятности GMM для данной точки данных. Чтобы сохранить топологическую структуру наборов точек, центроиды GMM вынуждены двигаться когерентно как группа. Ожидания максимизация${\displaystyle {\mathcal {M}}}$алгоритм используется для оптимизации функции стоимости. ^[13]

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

${\displaystyle p(s)=\sum _{i=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)}}$

Вероятности членства одинаковы для всех компонентов GMM. Вес равномерного распределения обозначается как . Тогда модель смеси выглядит так:${\displaystyle P(i)={\frac {1}{M}}}$${\displaystyle w\in [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 )

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

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

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

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

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

${\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}$

с только если . Апостериорные вероятности компонентов GMM, вычисленные с использованием предыдущих значений параметров :${\displaystyle N=N_{\mathbf {P} }}$${\displaystyle w=0}$${\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 ^{\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 ), если она уже не находится на локальном минимуме. ^[13] Таким образом, алгоритм может быть выражен с помощью следующего псевдокода, где множество точек , и представлены в виде и матриц и соответственно: ^[13]${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle M\times D}$${\displaystyle N\times D}$${\displaystyle \mathbf {M} }$${\displaystyle \mathbf {S} }$

алгоритм CPD${\displaystyle ({\mathcal {M}},{\mathcal {S}})}$  инициализируется, пока не зарегистрирован:  // E-шаг, вычисление P для и : // M-шаг, решение для оптимального возврата преобразования θ${\displaystyle \theta :=\theta _{0}}$ ${\displaystyle 0\leq w\leq 1}$ ${\displaystyle \sigma ^{2}:={\frac {1}{DNM}}\sum _{j=1}^{N}\sum _{i=1}^{M}\lVert s_{j}-m_{i}\rVert ^{2}}$   ${\displaystyle i\in [1,M]}$${\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 {w}{1-w}}{\frac {M}{N}}}}}$  ${\displaystyle \lbrace \theta ,\sigma ^{2}\rbrace :=\mathbf {solve} (\mathbf {S} ,\mathbf {M} ,\mathbf {P} )}$  

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

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

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

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

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

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

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

Solve_rigid ${\displaystyle (\mathbf {S} ,\mathbf {M} ,\mathbf {P} )}$ // разложение по сингулярным значениям // diag (ξ) - это диагональная матрица, сформированная из вектора ξ // tr - это след матрицы return${\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} }}} )}}}$    ${\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 {t} }$

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

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

решить_affine ${\displaystyle (\mathbf {S} ,\mathbf {M} ,\mathbf {P} )}$ return${\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} }})({\hat {\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 составляет , что асимптотически намного быстрее, чем у методов. ^[13]${\displaystyle O(M+N)}$${\displaystyle O(MN)}$

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

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

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

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

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

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

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