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

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

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

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

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

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

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

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

Методи на основі відповідностей припускають, що можливі відповідності ${\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) фактично має розв'язок у вигляді замкнутої формули, шляхом розділення оцінки масштабу, повороту та паралельного перенесення.^[9] Подібні результати були виявлені Аруном та співавторами.^[10] Крім того, щоб знайти унікальне перетворення ${\displaystyle (l,R,t)}$ для кожної множини точок потрібно як мінімум ${\displaystyle N=3}$ неколінеарні точки.

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

Відомо, що формулювання методу найменших квадратів (див. 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\%}$ відповідностей можуть бути викидами.^[12]

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

Максимальний консенсус прагне знайти найбільшу множину відповідностей, яка узгоджуюється з породжувальною моделлю (див. 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-складною задачею, і глобальні алгоритми, як правило, мають використовувати метод гілок і меж, який має експоненційну складність у найгіршому випадку.^{[13][14][15][16][17]}

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

Для заповнення прогалини між швидким, але неточним методом RANSAC та точним, але вичерпним оптимізаційним методом гілок і меж, останні дослідження розробили детерміновані наближені методи вирішення максимізації консенсусу.^{[13][14][19][15]}

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

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

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}}$ — норми втрат, втрати Губера,^[21] втрати Джемана-МакКлюра^[22] і втрати за методом найменших квадратів.^[23][20] М-оцінка була однією з загальновживаних парадигм стійкої оцінки в робототехніці та комп'ютерному зорі.^[24][25] Оскільки стійкі цільові функції зазвичай не є опуклими (наприклад, обрізана відносна квадратична втрата в порівнянні з відносною квадратичною втратою), алгоритми для розв'язання задачі невипуклої оцінки М-шляхом, зазвичай ґрунтуються на локальній оптимізації, де спочатку відбувається початкове припущення, а потім застосовуються ітеративні виправлення перетворення, щоб продовжувати зменшувати значення об'єктивної функції. Локальна оптимізація, як правило, працює добре, коли початкове припущення близьке до глобального мінімуму, але вона також має схильність застрягати в локальних мінімумах, якщо надано погану початкову ініціалізацію.

Градуйована неопуклість (англ. Graduated non-convexity) — це структура загального призначення для розв'язання задач невипуклої оптимізації без ініціалізації. Ця структура досягла успіху в додатках раннього зору та машинного навчання.^[26][27] Ключова ідея градуйованої неопуклості полягає в тому, щоб вирішити складну неопуклу проблему, починаючи з легкої опуклої задачі. Зокрема, для заданої стійкої функції витрат ${\displaystyle \rho (\cdot )}$, можна побудувати допоміжну функцію ${\displaystyle \rho _{\mu }(\cdot )}$ з гіперпараметром ${\displaystyle \mu }$, налаштування якої може поступово збільшувати невипуклість допоміжної функції ${\displaystyle \rho _{\mu }(\cdot )}$ поки вона не зійдеться до цільової функції ${\displaystyle \rho (\cdot )}$ .^[27][28] Отже, на кожному рівні гіперпараметра ${\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] і так звану функцію процесу викиду на вагових коефіцієнтах, які визначають достовірність оптимізації в кожній парі вимірювань.^[29] Використовуючи подвійність Блека-Рангараджана та градуйовану неопуклість, спеціально розроблену для функції Джемана-МакКлюра, Чжоу та ін. розробили швидкий глобальний алгоритм узгодження, який є стійким до приблизно 80 % викидів у відповідностях.^[22] Нещодавно Янг на ін. показали, що спільне використання градуйованої неопуклості (призначеної для функції Гемана-МакКлура і усіченої функції найменших квадратів) та двоїстості Блека-Рангараджана може призвести до розв'язку загального призначення для стійких проблем узгодження, включаючи узгодження хмари точок та сітки.^[28]

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

Зовсім нещодавно Янг та співавтори розробили перший алгоритм стійкого узгодження з гарантією надійності, під назвою «Оцінка за методом усічених найменших квадратів і напіввизначеної релаксації» (англ. 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) Та ж оцінка усічених найменших квадратів (далі — УНК) застосовується для кожної з трьох підзадач, де задача УНК масштабу може бути розв'язана за допомогою алгоритму, що називається адаптивним голосуванням. Задача обертання УНК можна послабити до напіввизначеної програми, де релаксація є точною на практиці,^[23] навіть із великою кількістю викидів. Задачу зсуву УНК можна вирішити використовуючи покомпонентне адаптивне голосування. Швидке впровадження, що використовує градуйовану неопуклість, має наступний код з відкритим доступом тут. На практиці оцінка за методом усічених квадратів і напіввизначенох релаксації може витримати більше ніж ${\displaystyle 99\%}$ викидів відповідностей і виконуватись за мілісекунди.

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

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

• 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