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

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

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

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

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

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

Проблему можно резюмировать следующим образом:[11]Позволять два набора точек конечного размера в конечномерное вещественное векторное пространство , которые содержат и баллов соответственно (например., восстанавливает типичный случай, когда и являются трехмерными наборами точек). Проблема состоит в том, чтобы найти преобразование, которое будет применяться к движущемуся набору точек "модели". такая, что разница (обычно определяемая в смысле точечной Евклидово расстояние ) между и статический набор "сцены" сводится к минимуму. Другими словами, отображение из к желательно, что дает наилучшее выравнивание между преобразованным набором «модель» и набором «сцена». Отображение может состоять из жесткого или нежесткого преобразования. Модель трансформации может быть записана как , с использованием которого преобразованный, зарегистрированный набор точек модели:

 

 

 

 

(1)

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

 

 

 

 

(2)

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

 

 

 

 

(3)

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

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

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

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

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

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

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

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

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

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

Методы, основанные на корреспонденции, предполагают предполагаемые соответствия даются за каждую точку . Таким образом, мы приходим к настройке, в которой оба точечных набора и имеют точки и соответствия даны.

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

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

 

 

 

 

(cb.1)

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

 

 

 

 

(cb.2)

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

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

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

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

 

 

 

 

(cb.3)

где, если ая пара является инльером, то он подчиняется модели без выбросов (cb.1), т.е. получается из пространственным преобразованием плюс небольшой шум; однако, если ая пара выброс, то может быть любым произвольным вектором . Поскольку заранее неизвестно, какие соответствия являются выбросами, надежная регистрация в рамках генеративной модели (cb.3) имеет первостепенное значение для компьютерного зрения и робототехники, развернутой в реальном мире, потому что современные методы сопоставления признаков имеют тенденцию выводить сильно искаженные соответствия, где больше соответствий могут быть выбросами.[20]

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

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

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

 

 

 

 

(cb.4)

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

Хотя точное решение максимизации консенсуса сложно, существуют эффективные эвристики, которые довольно хорошо работают на практике. Одна из самых популярных эвристик - Консенсус случайной выборки (RANSAC) схема.[26] RANSAC - это итеративный метод гипотезы и проверки. На каждой итерации метод сначала случайным образом выбирает 3 из общего числа соответствует и вычисляет гипотезу используя метод Хорна,[16] затем метод оценивает ограничения в (cb.4), чтобы подсчитать, сколько соответствий действительно согласуются с такой гипотезой (т. е. вычисляет остаточную и сравнивает с порогом для каждой пары измерений). Алгоритм завершается либо после того, как он найдет консенсусный набор, имеющий достаточно соответствий, либо после того, как он достигнет общего количества разрешенных итераций. RANSAC очень эффективен, потому что основное вычисление каждой итерации - выполнение решения в замкнутой форме в методе Хорна. Однако RANSAC не является детерминированным и хорошо работает только в режиме низкого отношения выбросов (например., ниже ), потому что время его выполнения растет экспоненциально по отношению к коэффициенту выбросов.[20]

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

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

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

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

М-оценка

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

 

 

 

 

(cb.5)

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

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

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

 

 

 

 

(cb.6)

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

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

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

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

 

 

 

 

(cb.7)

который получается выбором робастной функции стоимости TLS , куда - предварительно определенная константа, определяющая максимально допустимые остатки, которые следует рассматривать как выбросы. Целевая функция TLS обладает тем свойством, что для внутренних соответствий () применяется обычный штраф по методу наименьших квадратов; а для резко отклоняющихся соответствий () штраф не применяется, выбросы отбрасываются. Если оптимизация TLS (cb.7) решается до глобальной оптимальности, то это эквивалентно запуску метода Хорна только для внутренних соответствий.

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

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

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

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

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

алгоритм ICP()        в то время как не зарегистрировано: Икс := ∅        за :                                θ := наименьших квадратов (Икс)    возвращаться θ

Здесь функция наименьших квадратов выполняет наименьших квадратов оптимизация для минимизации расстояния в каждом из пары, используя замкнутые решения Хорна[16] и Арун.[17]

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

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

Робастное согласование точек (RPM) было введено Gold et al.[39] Метод выполняет регистрацию с использованием детерминированный отжиг и мягкое задание соответствий между наборами точек. В то время как в ICP соответствие, генерируемое эвристикой ближайшего соседа, является двоичным, RPM использует мягкий соответствие, при котором соответствие между любыми двумя точками может быть от 0 до 1, хотя в конечном итоге оно сходится либо к 0, либо к 1. Соответствия, обнаруженные в RPM, всегда взаимно однозначны, что не всегда имеет место в ICP.[14] Позволять быть й пункт в и быть й пункт в . В матрица соответствия определяется как таковое:

 

 

 

 

(об / мин.1)

Тогда проблема определяется как: Даны два точечных набора и Найди Аффинное преобразование и матрица соответствия это лучше всего их соотносит.[39] Знание оптимального преобразования упрощает определение матрицы соответствия, и наоборот. Однако алгоритм RPM определяет и то, и другое одновременно. Преобразование можно разложить на вектор перевода и матрицу преобразования:

Матрица в 2D состоит из четырех отдельных параметров , которые представляют собой масштаб, вращение и компоненты вертикального и горизонтального сдвига соответственно. Тогда функция стоимости будет следующей:

 

 

 

 

(об / мин.2)

при условии , , . В термин смещает цель в сторону более сильной корреляции, уменьшая стоимость, если в матрице соответствия больше единиц. Функция служит для регуляризации аффинного преобразования за счет штрафов за большие значения компонентов масштаба и сдвига:

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

Метод RPM оптимизирует функцию стоимости с помощью Softassign алгоритм. Здесь будет выведен одномерный случай. Учитывая набор переменных куда . Переменная связан с каждым такой, что . Цель - найти что максимизирует . Это можно сформулировать как непрерывную задачу, введя управляющий параметр . в детерминированный отжиг метод, управляющий параметр медленно увеличивается по мере выполнения алгоритма. Позволять быть:

 

 

 

 

(об / мин.3)

это известно как функция softmax. В качестве увеличивается, оно приближается к двоичному значению, как требуется в уравнении (об / мин.1). Теперь проблему можно обобщить на 2D-случай, когда вместо максимизации , максимальное количество:

 

 

 

 

(об / мин.4)

куда

Это просто, за исключением того, что теперь ограничения на находятся дважды стохастическая матрица ограничения: и . Таким образом, знаменатель из уравнения (об / мин.3) нельзя просто выразить для 2D случая. Чтобы удовлетворить ограничения, можно использовать результат Синкхорна,[39] который утверждает, что дважды стохастическая матрица получается из любой квадратной матрицы со всеми положительными элементами посредством итеративного процесса чередования нормализации строк и столбцов. Таким образом, алгоритм записывается так:[39]

алгоритм RPM2D    т := 0                пока :        пока μ не сошлись: // обновляем параметры корреспонденции с помощью softassign                                    // применяем метод Синхорна            пока  не сошлись:                // Обновить  путем нормализации по всем строкам:                                // Обновить  путем нормализации по всем столбцам:                            // обновляем параметры позы по координатному спуску            Обновить θ с помощью обновления аналитического решения т с помощью обновления аналитического решения а, б, в с помощью Метод Ньютона                    возвращаться а, б, в, θ и т

где детерминированный параметр управления отжигом изначально установлен на и увеличивается в раз пока не достигнет максимального значения . Суммирование шагов нормализации в сумме дает и вместо просто и потому что ограничения на неравенства. Таким образом й и th элементы слабые переменные.

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

Тонкая пластина, шлицы, надежное согласование точек
Анимация 2D нежесткой регистрации набора зеленой точки на набор пурпурных точек испорчен шумными выбросами. Размер синих кружков обратно пропорционален управляющему параметру. . Желтые линии обозначают соответствие.

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

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

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

 

 

 

 

(kc.1)

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

 

 

 

 

(kc.2)

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

 

 

 

 

(kc.3)

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

 

 

 

 

(kc.4)

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

 

 

 

 

(kc.5)

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

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

 

 

 

 

(kc.6)

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

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

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

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

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

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

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

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

 

 

 

 

(cpd.1)

в которой D размеры, это Гауссово распределение по центру .

Вероятности членства одинаков для всех компонентов GMM. Вес равномерного распределения обозначается как . Тогда модель смеси выглядит так:

 

 

 

 

(cpd.2)

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

 

 

 

 

(cpd.3)

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

В максимизация ожидания (EM) алгоритм используется для поиска и . Алгоритм EM состоит из двух шагов. Сначала в шаге E или оценка шаг, он угадывает значения параметров («старые» значения параметров), а затем использует Теорема Байеса для вычисления апостериорного распределения вероятностей компонентов смеси. Во-вторых, в M-шаге или максимизация На шаге «новые» значения параметров затем находятся путем минимизации математического ожидания полной отрицательной функции логарифмического правдоподобия, то есть функции стоимости:

 

 

 

 

(cpd.4)

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

 

 

 

 

(cpd.5)

куда

с только если . Апостериорные вероятности компонентов GMM, вычисленные с использованием предыдущих значений параметров является:

 

 

 

 

(cpd.6)

Минимизация функции стоимости в уравнении (cpd.5) обязательно уменьшает отрицательную функцию логарифмического правдоподобия E в уравнении (cpd.3), если это уже не локальный минимум.[13] Таким образом, алгоритм может быть выражен с помощью следующего псевдокода, где точка задает и представлены как и матрицы и соответственно:[13]

алгоритм CPD        инициализировать         пока не зарегистрирован: // E-шаг, вычислить п        за  и :                    // M-шаг, решение для оптимального преобразования            возвращаться θ

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

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

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

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

Solve_rigid                             // разложение по сингулярным числам из      // диаг (ξ) это диагональная матрица сформированный из вектора ξ         // tr это след матрицы            возвращаться 

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

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

решить_affine                                    возвращаться 

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

Суммы гауссовых распределений могут быть вычислены в линейное время с использованием быстрое преобразование Гаусса (FGT).[13] Следовательно, временная сложность CPD составляет , что асимптотически намного быстрее, чем методы.[13]

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

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

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

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

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

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

  1. ^ Чжан, Цзи; Сингх, Санджив (май 2015 г.). «Визуально-лидарная одометрия и картографирование: низкий дрейф, надежность и скорость». Международная конференция IEEE по робототехнике и автоматизации, 2015 г. (ICRA): 2174–2181. Дои:10.1109 / ICRA.2015.7139486. ISBN  978-1-4799-6923-4.
  2. ^ Чхве, Сонджун; Чжоу, Цянь-И; Колтун, Владлен (2015). «Надежная реконструкция внутренних сцен» (PDF). Материалы конференции IEEE по компьютерному зрению и распознаванию образов (CVPR): 5556–5565.
  3. ^ Лай, Кевин; Бо, Лифэн; Рен, Сяофэн; Фокс, Дитер (май 2011 г.). «Крупномасштабный иерархический набор данных объектов RGB-D с несколькими представлениями». 2011 Международная конференция IEEE по робототехнике и автоматизации: 1817–1824. CiteSeerX  10.1.1.190.1598. Дои:10.1109 / ICRA.2011.5980382. ISBN  978-1-61284-386-5.
  4. ^ а б c Ян, Хэн; Карлоне, Лука (2019). «Решение с полиномиальным временем для надежной регистрации с экстремальными выбросами». Робототехника: наука и системы (RSS). arXiv:1903.08588. Bibcode:2019arXiv190308588Y. Дои:10.15607 / RSS.2019.XV.003. ISBN  978-0-9923747-5-4.
  5. ^ Калли, Берк; Сингх, Арджун; Брюс, Джеймс; Уолсман, Аарон; Конолиге, Курт; Шриниваса, Сиддхартха; Аббель, Питер; Доллар, Аарон М (2017-03-01). «Набор данных Йель-CMU-Беркли для исследования манипуляций с роботами». Международный журнал исследований робототехники. 36 (3): 261–268. Дои:10.1177/0278364917700714. ISSN  0278-3649.
  6. ^ Кадена, Сезар; Карлоне, Лука; Каррильо, Генри; Латиф, Ясир; Скарамуцца, Давиде; Нейра, Хосе; Рид, Ян; Леонард, Джон Дж. (Декабрь 2016 г.). «Прошлое, настоящее и будущее одновременной локализации и картирования: к эпохе устойчивого восприятия». IEEE Transactions по робототехнике. 32 (6): 1309–1332. arXiv:1606.05830. Bibcode:2016arXiv160605830C. Дои:10.1109 / TRO.2016.2624754. ISSN  1941-0468.
  7. ^ Мур-Арталь, Рауль; Montiel, J.MM .; Тардос, Хуан Д. (октябрь 2015 г.). «ORB-SLAM: универсальная и точная монокулярная система SLAM». IEEE Transactions по робототехнике. 31 (5): 1147–1163. arXiv:1502.00956. Bibcode:2015arXiv150200956M. Дои:10.1109 / TRO.2015.2463671. ISSN  1941-0468.
  8. ^ а б c Ян, Хэн; Карлоне, Лука (2019). «Основанное на кватернионе гарантированно оптимальное решение проблемы Вахбы с выбросами» (PDF). Труды Международной конференции IEEE по компьютерному зрению (ICCV): 1665–1674. arXiv:1905.12536. Bibcode:2019arXiv190512536Y.
  9. ^ Ньюкомб, Ричард А .; Изади, Шахрам; Хиллигес, Отмар; Молино, Дэвид; Ким, Дэвид; Дэвисон, Эндрю Дж .; Кохи, Пушмит; Шоттон, Джейми; Ходжес, Стив; Фитцгиббон, Эндрю (октябрь 2011 г.). «KinectFusion: картографирование и отслеживание плотной поверхности в реальном времени». 2011 10-й международный симпозиум IEEE по смешанной и дополненной реальности: 127–136. CiteSeerX  10.1.1.453.53. Дои:10.1109 / ISMAR.2011.6092378. ISBN  978-1-4577-2183-0.
  10. ^ Audette, Michel A .; Ферри, Фрэнк П .; Питерс, Терри М. (01.09.2000). «Алгоритмический обзор методов регистрации поверхности для медицинской визуализации». Анализ медицинских изображений. 4 (3): 201–217. Дои:10.1016 / S1361-8415 (00) 00014-1. ISSN  1361-8415. PMID  11145309.
  11. ^ а б Цзянь, Бинг; Вемури, Баба С. (2011). «Надежная регистрация множества точек с использованием моделей гауссовой смеси». IEEE Transactions по анализу шаблонов и машинному анализу. 33 (8): 1633–1645. Дои:10.1109 / tpami.2010.223. PMID  21173443.
  12. ^ а б Фитцгиббон, Эндрю В. (2003). «Надежная регистрация наборов точек 2D и 3D». Вычисления изображений и зрения. 21 (13): 1145–1153. CiteSeerX  10.1.1.335.116. Дои:10.1016 / j.imavis.2003.09.004.
  13. ^ а б c d е ж грамм час я j k л Мироненко, Андрей; Песня, Сюбо (2010). «Регистрация набора точек: когерентный дрейф точки». IEEE Transactions по анализу шаблонов и машинному анализу. 32 (2): 2262–2275. arXiv:0905.2635. Дои:10.1109 / тпами.2010.46. PMID  20975122.
  14. ^ а б c Чуй, Хайли; Рангараджан, Ананд (2003). «Новый алгоритм сопоставления точек для нежесткой регистрации». Компьютерное зрение и понимание изображений. 89 (2): 114–141. CiteSeerX  10.1.1.7.4365. Дои:10.1016 / S1077-3142 (03) 00009-2.
  15. ^ Хольц, Дирк; Ichim, Alexandru E .; Томбари, Федерико; Русу, Раду Б .; Бенке, Свен (2015). «Регистрация в библиотеке облака точек: модульная структура для трехмерного выравнивания». Журнал IEEE Robotics Automation. 22 (4): 110–124. Дои:10.1109 / MRA.2015.2432331.
  16. ^ а б c Хорн, Бертольд К. П. (1987-04-01). «Закрытое решение абсолютной ориентации с использованием единичных кватернионов». JOSA A. 4 (4): 629–642. Bibcode:1987JOSAA ... 4..629H. Дои:10.1364 / JOSAA.4.000629. ISSN  1520-8532.
  17. ^ а б Arun, K. S .; Huang, T. S .; Blostein, S. D. (сентябрь 1987 г.). «Аппроксимация методом наименьших квадратов двух наборов трехмерных точек». IEEE Transactions по анализу шаблонов и машинному анализу. ПАМИ-9 (5): 698–700. Дои:10.1109 / TPAMI.1987.4767965. ISSN  1939-3539. PMID  21869429.
  18. ^ Бриалес, Иисус; Гонсалес-Хименес, Хавьер (июль 2017 г.). «Выпуклая глобальная трехмерная регистрация с лагранжевой двойственностью». Конференция IEEE 2017 по компьютерному зрению и распознаванию образов (CVPR): 5612–5621. Дои:10.1109 / CVPR.2017.595. HDL:10630/14599. ISBN  978-1-5386-0457-1.
  19. ^ а б c d е Ян, Хэн; Ши, Цзиннань; Карлоне, Лука (21 января 2020 г.). «TEASER: быстрая и сертифицированная регистрация облака точек». arXiv:2001.07715 [cs.RO ].
  20. ^ а б c Парра Бустос, Альваро; Чин, Тат-Джун (декабрь 2018 г.). «Гарантированное удаление выбросов для регистрации облака точек с корреспонденциями». IEEE Transactions по анализу шаблонов и машинному анализу. 40 (12): 2868–2882. arXiv:1711.10209. Дои:10.1109 / TPAMI.2017.2773482. ISSN  1939-3539. PMID  29990122.
  21. ^ а б Чин, Тат-Джун; Сутер, Дэвид (2017-02-27). «Проблема максимального консенсуса: последние достижения в области алгоритмов». Синтез лекций по компьютерному зрению. 7 (2): 1–194. Дои:10.2200 / s00757ed1v01y201702cov011. ISSN  2153-1056.
  22. ^ а б Вэнь, Фэй; Инь, Рендун; Гонг, Чжэн; Лю, Пэйлинь (февраль 2020 г.). «Эффективные алгоритмы для максимального согласования робастного соответствия». IEEE Transactions по робототехнике. 36 (1): 92–106. Дои:10.1109 / TRO.2019.2943061. ISSN  1941-0468.
  23. ^ а б Цай, Чжипэн; Чин, Тат-Джун; Колтун, Владлен (2019). "Новый взгляд на поиск дерева максимизации консенсуса". Труды Международной конференции IEEE по компьютерному зрению (ICCV): 1637–1645. arXiv:1908.02021. Bibcode:2019arXiv190802021C.
  24. ^ Базен, Жан-Шарль; Со, Ёндук; Поллефейс, Марк (2013). Ли, Кён Му; Мацусита, Ясуюки; Rehg, Джеймс М .; Ху, Чжаньи (ред.). «Оптимизация глобального набора консенсуса путем поиска вращения». Компьютерное зрение - ACCV 2012. Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 7725: 539–551. Дои:10.1007/978-3-642-37444-9_42. ISBN  978-3-642-37444-9.
  25. ^ Хартли, Ричард I; Каль, Фредрик (01.04.2009). «Глобальная оптимизация через поиск пространства вращения». Международный журнал компьютерного зрения. 82 (1): 64–79. Дои:10.1007 / s11263-008-0186-9. ISSN  1573-1405.
  26. ^ Фишлер, Мартин; Боллес, Роберт (1981). «Консенсус случайной выборки: парадигма подгонки модели с приложениями для анализа изображений и автоматизированной картографии». Коммуникации ACM. 24 (6): 381–395. Дои:10.1145/358669.358692.
  27. ^ Ле, Ху Минь; Чин, Тат-Джун; Эрикссон, Андерс; До, Тхань-Тоан; Сутер, Дэвид (2019). «Детерминированные приближенные методы для максимального согласования робастного соответствия». IEEE Transactions по анализу шаблонов и машинному анализу: 1. arXiv:1710.10003. Дои:10.1109 / TPAMI.2019.2939307. ISSN  1939-3539. PMID  31494545.
  28. ^ Бустос, Альваро Парра; Чин, Тат-Джун; Нойман, Франк; Фридрих, Тобиас; Кацманн, Максимилиан (04.02.2019). «Практический алгоритм максимальной клики для сопоставления с попарными ограничениями». arXiv:1902.01534 [cs.CV ].
  29. ^ Хубер, Питер Дж .; Ронкетти, Эльвезио М. (29 января 2009 г.). Надежная статистика. Серия Уайли по вероятности и статистике. Хобокен, Нью-Джерси, США: John Wiley & Sons, Inc. Дои:10.1002/9780470434697. ISBN  978-0-470-43469-7.
  30. ^ а б Чжоу, Цянь-И; Парк, Яесик; Колтун, Владлен (2016). Лейбе, Бастиан; Матас, Иржи; Себе, Нику; Веллинг, Макс (ред.). «Быстрая глобальная регистрация». Компьютерное зрение - ECCV 2016. Конспект лекций по информатике. Чам: Издательство Springer International. 9906: 766–782. Дои:10.1007/978-3-319-46475-6_47. ISBN  978-3-319-46475-6.
  31. ^ МакТавиш, Кирк; Барфут, Тимоти Д. (2015). «Любой ценой: сравнение надежных функций затрат для выбросов камеры». 2015 12-я конференция по компьютерному зрению и зрению роботов: 62–69. Дои:10.1109 / CRV.2015.52. ISBN  978-1-4799-1986-4.
  32. ^ Боссе, Майкл; Агаменнони, Габриэль; Гилищенский, Игорь (2016). «Робастная оценка и приложения в робототехнике». Основы и тенденции в робототехнике. сейчас же. 4 (4): 225–269. Дои:10.1561/2300000047.
  33. ^ а б Черный, Майкл Дж .; Рангараджан, Ананд (1 июля 1996 г.). «Об объединении линейных процессов, отклонении выбросов и надежной статистике с приложениями в раннем видении». Международный журнал компьютерного зрения. 19 (1): 57–91. Дои:10.1007 / BF00131148. ISSN  1573-1405.
  34. ^ а б Блейк, Эндрю; Зиссерман, Андрей (1987). Визуальная реконструкция. MIT Press. ISBN  9780262524063.
  35. ^ а б Ян, Хэн; Антонанте, Паскуале; Тзумас, Василиос; Карлоне, Лука (2020). «Градуированная невыпуклость для устойчивого пространственного восприятия: от неминимальных решателей к глобальному отклонению выбросов». Письма IEEE по робототехнике и автоматизации. 5 (2): 1127–1134. arXiv:1909.08605. Дои:10.1109 / LRA.2020.2965893. ISSN  2377-3774.
  36. ^ Бесл, Поль; Маккей, Нил (1992). «Метод регистрации трехмерных фигур». IEEE Transactions по анализу шаблонов и машинному анализу. 14 (2): 239–256. Bibcode:1992SPIE.1611..586B. Дои:10.1109/34.121791.
  37. ^ а б c d е ж грамм час я Цин, Янхай; Канаде, Такео (2004). Основанный на корреляции подход к надежной регистрации набора точек. Компьютерное зрение ECCV. Конспект лекций по информатике. 3023. Springer Berlin Heidelberg. С. 558–569. CiteSeerX  10.1.1.156.6729. Дои:10.1007/978-3-540-24672-5_44. ISBN  978-3-540-21982-8.
  38. ^ Русинкевич, Шимон; Левой, Марк (2001). Эффективные варианты алгоритма ICP. Труды Третьей Международной конференции по трехмерной цифровой визуализации и моделированию, 2001. IEEE. С. 145–152. Дои:10.1109 / IM.2001.924423.
  39. ^ а б c d е Голд, Стивен; Рангараджан, Ананд; Лу, Цзянь-Пин; Сугуна, Паппу; Mjolsness, Эрик (1998). «Новые алгоритмы сопоставления 2-х и 3-х точек :: оценка позы и соответствие». Распознавание образов. 38 (8): 1019–1031. Дои:10.1016 / S0031-3203 (98) 80010-1.
  40. ^ Цзянь, Бинг; Вемури, Баба С. (2005). Надежный алгоритм регистрации набора точек с использованием смеси гауссианов. Десятая международная конференция IEEE по компьютерному зрению 2005 г. 2. С. 1246–1251.
  41. ^ Мироненко, Андрей; Песня, Сюбо; Каррьера-Перпинан, Мигель А. (2006). «Регистрация нежесткой точки: когерентный дрейф точки». Достижения в системах обработки нейронной информации. 19: 1009–1016. Получено 31 мая 2014.
  42. ^ Ассалих, Хасан. (2013). "Глава 6: Сортировка пространства корреспонденции" (PDF). 3D-реконструкция и оценка движения с помощью переднего сонара (Кандидат наук.). Университет Хериот-Ватт.
  43. ^ Хиросе, Осаму (2020). «Байесовская формулировка когерентного дрейфа точки». IEEE Transactions по анализу шаблонов и машинному анализу. Ранний доступ: 1–18. Дои:10.1109 / TPAMI.2020.2971687. PMID  32031931.

внешняя ссылка