Узгодження множин точок

Узгодження множин точок (англ. point set registration, англ. point matching) у теорії розпізнавання образів та комп'ютерному зорі є процесом знаходження просторового перетворення, яке узгоджує дві множини точок. Метою знаходження такого перетворення є злиття декількох множин точок у глобально цілісну модель і відображення нового вимірювання на відомий набір даних для виявлення ознак або оцінювання його ^[en]. Множина точок може бути вхідними даними з 3D-сканера або масивом, отриманим від далекоміра. Для використання в обробці зображень і реєстрації зображень на основі ознак, множина точок може бути множиною ознак, отриманою виділянням ознак із зображення, наприклад, виявленням кутів. Узгодження множин точок має широке застосування в оптичному розпізнаванні символів, у доповненій реальності та суміщенні даних магнітно-резонансної томографії зі знімками комп'ютерної томографії.

Узгодження множин точок є процесом узгодження двох множин точок. На малюнку, блакитна риба узгоджується з червоною.

Формулювання

Проблему можна узагальнити наступним чином:

Нехай ${\displaystyle \lbrace {\mathcal {M}},{\mathcal {S}}\rbrace }$ — це дві множини точок скінченного розміру у скінченновимірному дійсному векторному просторі ${\displaystyle \mathbb {R} ^{d}}$, які містять ${\displaystyle M}$ і ${\displaystyle N}$ точок відповідно (наприклад, ${\displaystyle d=3}$ демонструє типовий випадок, коли ${\displaystyle {\mathcal {M}}}$ і ${\displaystyle {\mathcal {S}}}$ є множинами 3D-точок). Завдання полягає в тому, щоб знайти таке перетворення, яке буде застосовано до рухомої «моделі» множини точок ${\displaystyle {\mathcal {M}}}$ так, щоб різниця (зазвичай визначається як евклідова відстань) між ${\displaystyle {\mathcal {M}}}$ та статичною множиною об'єктів «сцени» ${\displaystyle {\mathcal {S}}}$ була зведена до мінімуму. Іншими словами, потрібно знайти відображення з ${\displaystyle \mathbb {R} ^{d}}$ на ${\displaystyle \mathbb {R} ^{d}}$, яке дає найкраще вирівнювання між трансформованими «модельною» множиною та множиною «сцени». Відображення може складатися з ^[en] або нежорсткого перетворення. Модель перетворення можна записати як ${\displaystyle T}$, за допомогою якої перетворена та узгоджена множина точок моделі матиме вигляд:

${\displaystyle T({\mathcal {M}}).}$

Таким чином, результатом алгоритму узгодження множин точок є оптимальне перетворення ${\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}}),}$

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

де ${\displaystyle \|\cdot \|_{2}}$ вказує на довжину вектора, а ${\displaystyle s_{m}}$ — на відповідну точку в множині ${\displaystyle {\mathcal {S}}}$, яка досягає найкоротшої відстані до даної точки ${\displaystyle m}$ у множині ${\displaystyle {\mathcal {M}}}$ після перетворення. Мінімізація такої функції у випадку ^[en] еквівалентна методу найменших квадратів.

Види алгоритмів

Якщо співвідношення (тобто, ${\displaystyle s_{m}\leftrightarrow m}$) відомі до оптимізації, наприклад, за допомогою методів (зіставлення ознак), тоді оптимізація має на меті лише оцінити перетворення. Цей тип узгодження називається узгодженням на основі відповідностей (заочне узгодження). З іншого боку, якщо відповідності невідомі, то оптимізації потрібно одночасно знайти відповідності та перетворення. Цей тип узгодження називається одночасним узгодженням положення та відповідності.

Жорстке узгодження

За допомогою жорсткого узгодження можна отримати ^[en], яке відображає одну множину точок нанесену на іншу. Жорстке перетворення визначається як перетворення, яке не змінює відстань між будь-якими двома точками. Зазвичай така трансформація складається з паралельного перенесення та обертання. У рідкісних випадках множина точок також може бути дзеркальною. Найбільшого застосування жорстке узгодження множин точок набує у робототехніці та комп'ютерному зорі.

Нежорстке перетворення

За допомогою нежорсткого узгодження можна отримати нежорстке (нелінійне) узгодження, яке відображає одну множину точок на іншу. Нежорсткі перетворення містять в собі афінні перетворення, такі як ^[en] та відображення зсуву. Однак, у контексті узгодження множини точок нежорстке зазвичай включає нелінійне перетворення. Якщо відомі власні вектори множини точок, нелінійне перетворення може бути параметризоване власними значеннями. Нелінійне перетворення також може бути параметризовано за допомогою ^[en].

Інші види

Деякі підходи до узгодження множин точок використовують алгоритми, які вирішують більш загальну задачу ^[en]. Однак, обчислювальна складність таких методів, як правило, висока, і вони обмежені жорсткими узгодженнями. PCL (Point Cloud Library) — це фреймворк з відкритим вихідним кодом для n-вимірної множини точок і обробки 3D-геометрії, що містить кілька алгоритмів узгодження точок.

Узгодження на основі відповідностей

Методи на основі відповідностей припускають, що можливі відповідності ${\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,}$

(див. 1)

де ${\displaystyle l>0}$ є сталим ^[en] обчислень (у багатьох випадках ${\displaystyle l=1}$), ${\displaystyle R\in {\text{SO}}(3)}$ є правильною 3D матрицею обертання (${\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}}$

(див. 2)

Зауважимо, що коли коефіцієнт масштабування дорівнює 1, а вектор паралельного перенесення дорівнює нулю, то тоді оптимізація відновлює формулювання ^[en]. Незважаючи на неопуклість оптимізації (див. 2) через неопуклість множини ${\displaystyle {\text{SO}}(3),}$ основоположна робота Бертольда К. П. Хорна показала, що (див. 2) фактично має розв'язок у вигляді замкнутої формули, шляхом розділення оцінки масштабу, повороту та паралельного перенесення. Подібні результати були виявлені Аруном та співавторами. Крім того, щоб знайти унікальне перетворення ${\displaystyle (l,R,t)}$ для кожної множини точок потрібно як мінімум ${\displaystyle N=3}$ неколінеарні точки.

Зовсім нещодавно Бріалес і Гонсалес-Хіменес розробили напіввизначену релаксацію, використовуючи двоїстість Лагранжа, для випадку, коли множина моделей ${\displaystyle {\mathcal {M}}}$ містить різні 3D-примітиви, такі як точки, лінії та площини (в тому випадку, коли модель ${\displaystyle {\mathcal {M}}}$ є 3D-сіткою). Цікаво, що напіввизначена релаксація є емпірично жорсткою, тобто з розв'язку напіввизначеної релаксації можна отримати глобально оптимальний розв'язок.

Стійке узгодження

Відомо, що формулювання методу найменших квадратів (див. 2) може працювати з низькою ефективністю за наявності викидів. Відповідність викидів — це пара вимірювань ${\displaystyle s_{i}\leftrightarrow m_{i}}$ що відхиляється від породжувальної моделі (див. 1). У цьому випадку можна розглянути іншу породжувальну модель таку, як:

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

(див. 3)

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

Далі опишемо кілька поширених парадигм стійкого узгодження.

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

Максимальний консенсус прагне знайти найбільшу множину відповідностей, яка узгоджуюється з породжувальною моделлю (див. 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}}\,}$

(див. 4)

де ${\displaystyle \vert {\mathcal {I}}\vert }$ позначає потужність множини ${\displaystyle {\mathcal {I}}}$. Обмеження у формулі (див. 4) забезпечують те, що кожна пара вимірювань у множині відповідних точок ${\displaystyle {\mathcal {I}}}$, що задовольняють моделі без викидів, має менший залишок, ніж заданий поріг ${\displaystyle \xi }$. На жаль, нещодавні дослідження показали, що глобальне розв'язання проблеми (див. 4) є NP-складною задачею, і глобальні алгоритми, як правило, мають використовувати метод гілок і меж, який має експоненційну складність у найгіршому випадку.

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

Для заповнення прогалини між швидким, але неточним методом RANSAC та точним, але вичерпним оптимізаційним методом гілок і меж, останні дослідження розробили детерміновані наближені методи вирішення максимізації консенсусу.

Видалення викидів

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

Парра Бустос та ін. запропонували метод під назвою Гарантоване Видалення Викидів (ГВВ), який використовує геометричні обмеження для скорочення відповідностей викидів, гарантуючи збереження внутрішніх відповідностей. Встановлено, що метод гарантованого видалення викидів здатний різко зменшити коефіцієнт викидів, що може значно підвищити ефективність максимізації консенсусу за допомогою RANSAC або методу гілок і меж. Янг і Карлоун запропонували побудувати попарні інваріантні вимірювання зсуву та обертання (англ. translation-and-rotation-invariant measurements) з вихідного набору вимірювань та вбудувати TRIM як ребра графа, вузлами якого є тривимірні точки. Оскільки внутрішні точки попарно узгоджені з точки зору масштабу, то вони повинні утворювати кліку в межах графа. Таким чином, використовуючи ефективні алгоритми для обчислення максимальної кліки на графі, можна знайти вхідні значення та ефективно виключити викиди. Метод видалення викидів на основі задачі про кліки також виявився досить корисним у проблемах узгодження множин точок у реальному світі. Подібні ідеї видалення викидів також були запропоновані Парра Бустосом та ін..

М-оцінка

M-оцінка замінює метод найменших квадратів у (див. 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)}$

(див. 5)

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

Градуйована неопуклість

Градуйована неопуклість (англ. Graduated non-convexity) — це структура загального призначення для розв'язання задач невипуклої оптимізації без ініціалізації. Ця структура досягла успіху в додатках раннього зору та машинного навчання. Ключова ідея градуйованої неопуклості полягає в тому, щоб вирішити складну неопуклу проблему, починаючи з легкої опуклої задачі. Зокрема, для заданої стійкої функції витрат ${\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)}$

(див. 6)

Блек і Рангараджан довели, що для цільової функції кожної оптимізації (див. 6) можна створити двоїстість на ^[en] і так звану функцію процесу викиду на вагових коефіцієнтах, які визначають достовірність оптимізації в кожній парі вимірювань. Використовуючи подвійність Блека-Рангараджана та градуйовану неопуклість, спеціально розроблену для функції Джемана-МакКлюра, Чжоу та ін. розробили швидкий глобальний алгоритм узгодження, який є стійким до приблизно 80 % викидів у відповідностях. Нещодавно Янг на ін. показали, що спільне використання градуйованої неопуклості (призначеної для функції Гемана-МакКлура і усіченої функції найменших квадратів) та двоїстості Блека-Рангараджана може призвести до розв'язку загального призначення для стійких проблем узгодження, включаючи узгодження хмари точок та сітки.

Сертифіковано стійке узгодження

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

Зовсім нещодавно Янг та співавтори розробили перший алгоритм стійкого узгодження з гарантією надійності, під назвою «Оцінка за методом усічених найменших квадратів і напіввизначеної релаксації» (англ. Truncated least squares Estimation And Semidefinite Relaxation). Для угодження множини точок TEASER не тільки виводить оцінку перетворення, але й кількісно визначає оптимальність даної оцінки. TEASER використовує наступний оцінювач за методом усічених найменших квадратів:

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

(див. 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}}$) цей штраф не застосовується, а викиди відхиляються. Якщо оптимізація УНК (див. 7) розв'язується з глобальною оптимальністю, то вона еквівалентна методу Хорна лише для внутрішніх відповідностей.

Однак, розв'язання (див. 7) є досить складним через його комбінаторний характер. Оцінка за методом усічених найменших квадратів і напіввизначеної релаксації розв'язує (див. 7) наступним чином: (i) Вона створює інваріантні вимірювання таким чином, що оцінка масштабу, обертання та перетворення можуть бути відокремлені та розв'язана окремо. Ця стратегія заснована на оригінальній схемі Горнера.

(ii) Та ж оцінка усічених найменших квадратів (далі — УНК) застосовується для кожної з трьох підзадач, де задача УНК масштабу може бути розв'язана за допомогою алгоритму, що називається адаптивним голосуванням. Задача обертання УНК можна послабити до напіввизначеної програми, де релаксація є точною на практиці, навіть із великою кількістю викидів. Задачу зсуву УНК можна вирішити використовуючи покомпонентне адаптивне голосування. Швидке впровадження, що використовує градуйовану неопуклість, має наступний код з відкритим доступом тут. На практиці оцінка за методом усічених квадратів і напіввизначенох релаксації може витримати більше ніж ${\displaystyle 99\%}$ викидів відповідностей і виконуватись за мілісекунди.

Крім розробки оцінки за методом усічених квадратів і напіввизначеної релаксації, Янг та співавтори також довели, що за деяких слабких умов на заданій множині точок оцінка перетворення усічених квадратів і напіввизначеної релаксації має певні похибки в порівнянні із справжнім перетворенням.

Див. також

• Зіставляння точкових ознак
• Тріангуляція множини точок

Примітки

1. Chui, Haili; Rangarajan, Anand (2003). A new point matching algorithm for non-rigid registration. Computer Vision and Image Understanding. 89 (2): 114—141. doi:10.1016/S1077-3142(03)00009-2. (англ.)
2. Fitzgibbon, Andrew W. (2003). Robust registration of 2D and 3D point sets. Image and Vision Computing. 21 (13): 1145—1153. doi:10.1016/j.imavis.2003.09.004. (англ.)
3. Allan, Max; Kapoor, Ankur; Mewes, Philip; Mountney, Peter (1 січня 2015). Non Rigid Registration of 3D Images to Laparoscopic Video for Image Guided Surgery. International Workshop on Computer-Assisted and Robotic Endoscopy. Springer International Publishing: 109—116. (англ.)
4. Hill, Derek LG; Hawkes, D. J.; Crossman, J. E.; Gleeson, M. J.; Cox, T. C. S.; Bracey, E. E. C. M. L.; Strong, A. J.; Graves, P. (1991). Registration of MR and CT images for skull base surgery using point-like anatomical features. British journal of radiology. 64 (767): 1030—1035. doi:10.1259/0007-1285-64-767-1030. (англ.)
5. Studholme, C.; Hill, D. L.; Hawkes, D. J. (1995). Automated 3D Registration of Truncated MR and CT Images of the Head. Proceedings of the Sixth British Machine Vision Conference. с. 27—36. (англ.)
6. Jian, Bing; Vemuri, Baba C. (2011). Robust Point Set Registration Using Gaussian Mixture Models. IEEE Transactions on Pattern Analysis and Machine Intelligence. 33 (8): 1633—1645. doi:10.1109/tpami.2010.223. PMID 21173443. S2CID 10923565.(англ.)
7. Myronenko, Andriy; Song, Xubo (2010). Point set registration: Coherent Point drift. IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (2): 2262—2275. arXiv:0905.2635. doi:10.1109/tpami.2010.46. PMID 20975122. S2CID 10809031.(англ.)
8. Holz, Dirk; Ichim, Alexandru E.; Tombari, Federico; Rusu, Radu B.; Behnke, Sven (2015). Registration with the Point Cloud Library: A Modular Framework for Aligning in 3-D. IEEE Robotics Automation Magazine. 22 (4): 110—124. doi:10.1109/MRA.2015.2432331. S2CID 2621807.(англ.)
9. Horn, Berthold K. P. (1 квітня 1987). Closed-form solution of absolute orientation using unit quaternions. JOSA A (EN) . 4 (4): 629—642. Bibcode:1987JOSAA...4..629H. doi:10.1364/JOSAA.4.000629. ISSN 1520-8532.
10. Arun, K. S.; Huang, T. S.; Blostein, S. D. (September 1987). Least-Squares Fitting of Two 3-D Point Sets. IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-9 (5): 698—700. doi:10.1109/TPAMI.1987.4767965. ISSN 1939-3539. PMID 21869429.
11. Briales, Jesus; Gonzalez-Jimenez, Javier (July 2017). Convex Global 3D Registration with Lagrangian Duality. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR): 5612—5621. doi:10.1109/CVPR.2017.595. ISBN . {{}}: |hdl-access= вимагає |hdl= ()
12. Parra Bustos, Álvaro; Chin, Tat-Jun (December 2018). Guaranteed Outlier Removal for Point Cloud Registration with Correspondences. IEEE Transactions on Pattern Analysis and Machine Intelligence. 40 (12): 2868—2882. arXiv:1711.10209. doi:10.1109/TPAMI.2017.2773482. ISSN 1939-3539. PMID 29990122.
13. Chin, Tat-Jun; Suter, David (27 лютого 2017). The Maximum Consensus Problem: Recent Algorithmic Advances. Synthesis Lectures on Computer Vision (амер.). 7 (2): 1—194. doi:10.2200/s00757ed1v01y201702cov011. ISSN 2153-1056.
14. Wen, Fei; Ying, Rendong; Gong, Zheng; Liu, Peilin (February 2020). Efficient Algorithms for Maximum Consensus Robust Fitting. IEEE Transactions on Robotics. 36 (1): 92—106. doi:10.1109/TRO.2019.2943061. ISSN 1941-0468.
15. Cai, Zhipeng; Chin, Tat-Jun; Koltun, Vladlen (2019). Consensus Maximization Tree Search Revisited. Proceedings of IEEE International Conference on Computer Vision (ICCV): 1637—1645. arXiv:1908.02021. Bibcode:2019arXiv190802021C.
16. Bazin, Jean-Charles; Seo, Yongduek; Pollefeys, Marc (2013). Lee, Kyoung Mu; Matsushita, Yasuyuki; Rehg, James M.; Hu, Zhanyi (ред.). Globally Optimal Consensus Set Maximization through Rotation Search. Computer Vision – ACCV 2012. Lecture Notes in Computer Science (англ.). Berlin, Heidelberg: Springer. 7725: 539—551. doi:10.1007/978-3-642-37444-9_42. ISBN .
17. Hartley, Richard I.; Kahl, Fredrik (1 квітня 2009). Global Optimization through Rotation Space Search. International Journal of Computer Vision (англ.). 82 (1): 64—79. doi:10.1007/s11263-008-0186-9. ISSN 1573-1405. {{}}: |hdl-access= вимагає |hdl= ()
18. Fischler, Martin; Bolles, Robert (1981). Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM (EN) . 24 (6): 381—395. doi:10.1145/358669.358692. S2CID 972888.
19. Le, Huu Minh; Chin, Tat-Jun; Eriksson, Anders; Do, Thanh-Toan; Suter, David (2019). Deterministic Approximate Methods for Maximum Consensus Robust Fitting. IEEE Transactions on Pattern Analysis and Machine Intelligence. 43 (3): 842—857. arXiv:1710.10003. doi:10.1109/TPAMI.2019.2939307. ISSN 1939-3539. PMID 31494545.
20. Yang, Heng; Carlone, Luca (2019). A polynomial-time solution for robust registration with extreme outlier rates. Robotics: Science and Systems. arXiv:1903.08588. doi:10.15607/RSS.2019.XV.003. ISBN .
21. Huber, Peter J.; Ronchetti, Elvezio M. (29 січня 2009). Robust Statistics. Wiley Series in Probability and Statistics (англ.). Hoboken, NJ, USA: John Wiley & Sons, Inc. doi:10.1002/9780470434697. ISBN .
22. Zhou, Qian-Yi; Park, Jaesik; Koltun, Vladlen (2016). Leibe, Bastian; Matas, Jiri; Sebe, Nicu; Welling, Max (ред.). Fast Global Registration. Computer Vision – ECCV 2016. Lecture Notes in Computer Science (англ.). Cham: Springer International Publishing. 9906: 766—782. doi:10.1007/978-3-319-46475-6_47. ISBN .
23. Yang, Heng; Carlone, Luca (2019). A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers (PDF). Proceedings of the IEEE International Conference on Computer Vision (ICCV): 1665—1674. arXiv:1905.12536. Bibcode:2019arXiv190512536Y.
24. MacTavish, Kirk; Barfoot, Timothy D. (2015). At all Costs: A Comparison of Robust Cost Functions for Camera Correspondence Outliers. 2015 12th Conference on Computer and Robot Vision: 62—69. doi:10.1109/CRV.2015.52. ISBN .
25. Bosse, Michael; Agamennoni, Gabriel; Gilitschenski, Igor (2016). Robust Estimation and Applications in Robotics. Foundations and Trends in Robotics. now. 4 (4): 225—269. doi:10.1561/2300000047.
26. Black, Michael J.; Rangarajan, Anand (1 липня 1996). On the unification of line processes, outlier rejection, and robust statistics with applications in early vision. International Journal of Computer Vision (англ.). 19 (1): 57—91. doi:10.1007/BF00131148. ISSN 1573-1405.
27. Blake, Andrew; Zisserman, Andrew (1987). Visual reconstruction. The MIT Press. ISBN .
28. Yang, Heng; Antonante, Pasquale; Tzoumas, Vasileios; Carlone, Luca (2020). Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection. IEEE Robotics and Automation Letters. 5 (2): 1127—1134. arXiv:1909.08605. doi:10.1109/LRA.2020.2965893. ISSN 2377-3774.
29. Black, Michael J.; Rangarajan, Anand (1 липня 1996). On the unification of line processes, outlier rejection, and robust statistics with applications in early vision. International Journal of Computer Vision (англ.). 19 (1): 57—91. doi:10.1007/BF00131148. ISSN 1573-1405.
30. Yang, Heng; Shi, Jingnan; Carlone, Luca (21 січня 2020). TEASER: Fast and Certifiable Point Cloud Registration. arXiv:2001.07715 [cs.RO].(англ.)

Посилання

• Reference implementation of thin plate spline robust point matching
• Reference implementation of kernel correlation point set registration
• Reference implementation of coherent point drift
• Reference implementation of ICP variants