Сопоставление множеств точек

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

Нежёсткая регистрация позволяет искать более общие преобразования между множествами — аффинные (например, масштабирование, сдвиг/сдвиг) или нелинейные. Если известны моды изменений в структуре множества, нелинейное преобразование может быть параметризовано по собственным значениям^[13]. Часто нелинейные преобразования выражаются с помощью тонкопластинных сплайнов (англ. Thin Plate Splines, TPS)^[13][14], что легло в основу алгоритма TPS-RPM (англ. Robust Point Matching), который объединяет TPS с вероятностным установлением соответствий (англ. softassign) и методом детерминированного отжига. В дальнейшем этот подход развивался в сторону использования математически более строгих диффеоморфных преобразований, сохраняющих топологию объекта^[15], и расширения за счёт учёта дополнительной информации, например, векторов нормалей к поверхности (алгоритм TPSN-RPM).

Развитие методов нежёсткой регистрации было направлено на повышение устойчивости к шуму, выбросам и неполным данным. В середине 2010-х годов появились контекстно-зависимые подходы, например, использующие гауссовы поля^[16]. К 2024 году были представлены методы, которые решают задачу без явного поиска соответствий между точками (англ. correspondence-free). Такие подходы напрямую оптимизируют поле деформации, что позволяет избежать ошибок, связанных с неверным сопоставлением, и особенно эффективно при работе с объектами, претерпевшими значительные изменения формы^[17].

Часть подходов к регистрации множеств точек сводится к более общей задаче сопоставления графов^[11], однако такие методы обычно применимы только к жёсткой регистрации и характеризуются высокой вычислительной сложностью.

PCL (Point Cloud Library) — открытая библиотека для работы с n-мерными облаками точек и 3D-геометрией; содержит несколько алгоритмов регистрации точек^[18]. В середине 2010-х годов развитие библиотеки было сосредоточено не на добавлении принципиально новых алгоритмов, а на улучшении существующих. Так, в версии 1.8.0 (2016 год) были внесены исправления и оптимизации в такие методы, как TransformationEstimationSVD, ICP и GeneralizedIterativeClosestPoint (GICP)^[19]. В 2017 году работа была направлена на внутреннюю реорганизацию кода: например, логика нелинейной оптимизации по методу Левенберга-Марквардта была вынесена из класса IterativeClosestPointNonLinear в отдельный компонент TransformationEstimationLM. Это изменение, вошедшее в версию 1.9.0, повысило модульность и расширяемость библиотеки, но не добавило нового алгоритма с точки зрения пользователя^[20].

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

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

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

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

Когда ${\displaystyle l=1}$, ${\displaystyle t=0}$ — это сводится к формулировке задачи Вахбы. Несмотря на невыпуклость задачи, работа Б. Хорна показала, что её можно решить в замкнутом виде, разделяя оценку масштаба, вращения и сдвига^[27]. Аналогичные методы предложили также Арун и др^[28]. Для уникального определения преобразования ${\displaystyle (l,R,t)}$ необходимо не менее трёх неколлинеарных точек в каждом множестве.

Для случая, когда модель ${\displaystyle {\mathcal {M}}}$ содержит разные 3D-примитивы (точки, линии, плоскости), была предложена полуопределённая релаксация с использованием двойственности Лагранжа^[29].

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

• Гибридные подходы, сочетающие классические методы оптимизации с глубоким обучением. В таких системах нейронные сети используются для извлечения устойчивых признаков и поиска надёжных соответствий между точками, которые затем уточняются с помощью итерационных алгоритмов^[30][31]. Также возрос интерес к регистрации данных из разных источников (англ. cross-source registration), например, совмещению данных с лидара и фотограмметрической реконструкции^[30].
• Вероятностные методы. Получили развитие подходы, рассматривающие регистрацию как задачу выравнивания двух распределений вероятностей, что делает их более устойчивыми к шуму. В 2021 году был предложен обобщённый байесовский когерентный дрейф точек (англ. Generalized Bayesian Coherent Point Drift, GBCPD), который расширяет подход BCPD, используя информацию о нормалях к поверхности. Это позволяет повысить точность, формулируя задачу в шестимерном пространстве (координаты и ориентация нормали)^[32].
• Методы на основе оптимального транспорта (ОТ). В 2021 году было показано, что применение робастного оптимального транспорта позволяет создавать точные и масштабируемые алгоритмы, эффективно справляющиеся с выбросами. Они могут использоваться как для грубого, так и для точного совмещения в рамках классических и нейросетевых моделей^[33].

Максимальный консенсус ищет наибольшее подмножество соответствий, совместимых с моделью:

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

В общем случае задача NP-трудна, и глобальные точные решения требуют методов ветвей и границ^[34][35]. На практике часто используется RANSAC (Random Sample Consensus) — итеративный метод генерации и проверки гипотез^[36]. При повышенном проценте выбросов (выше 50 %) эффективность RANSAC существенно снижается^[37].

Для компромисса между точностью и скоростью разработаны детерминированные аппроксимирующие методы^[34][35][38].

Методы удаления выбросов предварительно сокращают объём некорректных соответствий перед основным этапом регистрации. Такие методы могут кардинально снизить долю выбросов, ускоряя последующую оптимизацию по преобразованию. Например, GORE («Guaranteed Outlier Removal») производит геометрическую фильтрацию с гарантией сохранения корректных пар^[37]. Другой подход строит граф из паропрочных измерений и ищет в нём наибольшую клику, соответствующую инлайнерам^[4][39]. Аналогичные идеи реализованы и в других исследованиях^[40].

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

${\displaystyle l^{\star },R^{\star },t^{\star }=\arg \min _{\dots }\sum _{i=1}^{N}\rho \left({\frac {1}{\sigma _{i}}}\left\Vert s_{i}-lRm_{i}-t\right\Vert _{2}\right)}$,

где ${\displaystyle \rho (\cdot )}$ — робастная функция, например норма ℓ1, потери Хьюбера^[41], функция потерь Джемана-Макклюра^[42] и усечённые квадраты (truncated least squares)^[4][8][39]. М-оценка широко применяется в робототехнике и компьютерном зрении^[43][44].

Градуированная невыпуклость (GNC) — общий подход для решения невыпуклых задач оптимизации без начального приближения. Идея — начинать с простой выпуклой задачи и поэтапно усложнять функцию стоимости до желаемой невыпуклой формы^[45][46]. Активные применения GNC получили в раннем компьютерном зрении и машинном обучении^[47].

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

TEASER («Truncated least squares Estimation And SEmidefinite Relaxation»), разработанный Ян и соавторами^[39], — первый гарантированно робастный алгоритм подобного рода. Он реализует комбинированную оценку по усечённым квадратам для масштаба, вращения и сдвига, что позволяет устойчиво отсеивать выбросы и получать решение, близкое к глобальному оптимуму даже при их доле, близкой к 99 %.

Алгоритм итерального ближайшего соседа (ICP) был предложен Беслом и Маккеем^[48]. Он попеременно на каждом шаге: (i) для каждой точки в ${\displaystyle {\mathcal {M}}}$ находит ближайшую в ${\displaystyle {\mathcal {S}}}$; (ii) по найденным соответствиям вычисляет оптимальное жёсткое преобразование (путём минимизации суммы квадратов расстояний). Алгоритм хорошо работает при достаточном начальном приближении между множествами.

алгоритм ICP(M, S):
    θ := θ₀
    пока не зарегистрировано:
        X := ∅
        для каждого mᵢ ∈ T(M, θ):
            ŝᵢ := ближайшая точка в S к mᵢ
            X := X ∪ ⟨mᵢ, ŝᵢ⟩
        θ := наименьшие_квадраты(X)
    вернуть θ

Здесь функция наименьшие_квадраты вычисляет параметры преобразования по формуле Хорна^[27] или Аруна^[28].

Несмотря на отсутствие гарантий сходимости к локальному минимуму^[49], ICP остаётся наиболее распространённым подходом благодаря простоте реализации. Существует множество его вариантов (например, EM-ICP и LM-ICP^[12]).

Метод робастного сопоставления точек (RPM) предложен Голдом и др^[50]. В отличие от ICP, RPM использует «мягкие» соответствия на промежутке [0, 1] и детерминированное отжиговое минимизирование. Метод всегда строит взаимно однозначные соответствия.

Критерием качества служит минимизация:

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

где ${\displaystyle \mathbf {A} }$ — матрица (масштаб, поворот, сдвиг).

Обновление матрицы соответствий реализовано через итеративное нормирование по методу Синхорна (матричные «мягкие назначения»). Варианты алгоритма существуют для 2D, 3D и выше^[50]. Для нежёсткой регистрации функция преобразования параметризуется посредством тонкого пластино-сплайна^[14].

В последующие годы алгоритм TPS-RPM получил дальнейшее развитие. Одним из направлений стало применение математически более строгих диффеоморфных преобразований, которые гарантируют сохранение топологии объекта. Была также предложена модификация для более надёжной обработки выбросов, особенно в случаях, когда они присутствуют в обоих наборах данных. Кроме того, был разработан алгоритм TPSN-RPM (англ. Thin Plate Spline with Normals Robust Point-Matching), который при сопоставлении одновременно учитывает положения точек и ориентацию векторов нормалей к поверхности, что позволяет получать более качественные и физически корректные деформации.

Метод kernel correlation (KC), предложенный Цзинь и Канаде^[49], вычисляет величину перекрытия гауссовых ядер, ассоциированных с каждой точкой, и использует градиентный спуск по критерию

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

что делает метод более устойчивым к шуму по сравнению с ICP.

Алгоритм может быть обобщён до регистрации на базе смесей гауссиан (GMM), позволяя задавать более гибкие классы трансформаций^[51]. Логическим развитием этого направления стал вероятностный метод Coherent Point Drift (CPD), представленный Андреем Мироненко и Сюбо Сонгом в 2006 году. Он развивает идею представления одного из множеств точек как центроидов гауссовой смешанной модели, но добавляет ограничение на когерентность движения для сохранения топологической структуры объекта^[52].

Алгоритм когерентного дрейфа точек (англ. Coherent Point Drift, CPD) — вероятностный метод, представленный Андреем Мироненко и Сюбо Сонгом в 2006 году и предназначенный как для жёсткой, так и для нежёсткой регистрации. Он построен на идее представления одного из множеств точек как центроидов гауссовой смешанной модели (GMM), а второго — как набора данных, генерируемых этой моделью. Ключевым нововведением стало введение ограничения на когерентность движения, которое заставляет точки двигаться как единая группа, сохраняя топологическую структуру объекта. Выравнивание осуществляется с помощью EM-алгоритма.

Для жёсткой регистрации результатом оптимизации являются масштаб, матрица вращения и вектор переноса:

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

Аналитические формулы для обновления параметров приведены в оригинальной статье.

Модификации и развитие:

• Робастные версии (2016): Были разработаны модификации CPD, повышающие устойчивость к сильным деформациям, шуму и выбросам за счёт использования структурной информации.
• BCPD: Байесовский когерентный дрейф точек — единая модель для жёсткой и нежёсткой регистрации, ускоренная, с явным моделированием согласованности движений.
• GBCPD (2021): Обобщённый байесовский когерентный дрейф точек, который расширяет подход BCPD, используя информацию о нормалях к поверхности. Это позволяет повысить точность, формулируя задачу в шестимерном пространстве (координаты и ориентация нормали)^[32].
• LSG-CPD: Модифицированный CPD с учётом локальной геометрии поверхности (анизотропные ковариационные матрицы, ускорение на GPU)^[53].

Алгоритм Sorting the Correspondence Space (SCS) был введён в 2013 году для регистрации сонарных изображений с большим числом шумовых выбросов^[54]. Метод не использует итерации в высокоразмерном пространстве, не является вероятностным и не основан на спектральных методах. Позволяет регистрировать как жёсткие, так и нежёсткие преобразования при количестве степеней свободы от 3 до 6.

DeepVCP (англ. Deep Virtual Corresponding Points, «глубокие виртуальные соответствующие точки») — это сквозной (end-to-end) алгоритм на основе глубокого обучения для регистрации (совмещения) трёхмерных облаков точек. Он вычисляет необходимое жёсткое преобразование (поворот и перенос) для совмещения двух облаков точек^[61].

Ключевой особенностью DeepVCP является отказ от поиска точных соответствий между существующими точками в двух облаках. Вместо этого алгоритм генерирует «виртуальные» соответствующие точки для ключевых точек исходного облака. Эти виртуальные точки создаются на основе изученных вероятностей совпадения среди группы точек-кандидатов в целевом облаке, что позволяет повысить точность регистрации, поскольку в реальных, особенно разреженных, данных точного аналога для каждой точки может не существовать^[61].

Принцип работы алгоритма включает несколько последовательных шагов^[61]:

1. Извлечение признаков. Сеть, используя архитектуру, подобную PointNet, извлекает семантические признаки для каждой точки в исходном и целевом облаках.
2. Обнаружение ключевых точек. Специальный слой сети анализирует исходное облако и выделяет из него наиболее значимые (ключевые) точки. Благодаря сквозному обучению, детектор учится выбирать стабильные точки на стационарных объектах, игнорируя динамические (движущиеся).
3. Генерация виртуальных соответствующих точек (CPG). Для каждой ключевой точки из исходного облака специальный слой (англ. Corresponding Point Generation layer) на основе анализа признаков генерирует одну виртуальную точку, которая является наилучшим соответствием.
4. Расчёт преобразования. После того как для всех ключевых точек найдены их виртуальные пары, алгоритм вычисляет итоговое жёсткое преобразование с помощью классического метода, такого как SVD.

К преимуществам DeepVCP относятся высокая робастность к неточному начальному положению и наличию движущихся объектов, а также отсутствие необходимости в эвристических алгоритмах отсеивания выбросов, таких как RANSAC. Алгоритм продемонстрировал свою эффективность и точность, сопоставимую с передовыми геометрическими методами, на таких наборах данных для задач автономного вождения, как KITTI и Apollo-SouthBay^[61].