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

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

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

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

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

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

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

Таким чином, результатом алгоритму узгодження множин точок є оптимальне перетворення $T^{\star }$ таке, що ${\mathcal {M}}$ найкраще вирівнюється по ${\mathcal {S}}$ відповідно до поняття функції відстані $\operatorname {dist} (\cdot ,\cdot )$:

$T^{\star }=\arg \min _{T\in {\mathcal {T}}}{\text{dist}}(T({\mathcal {M}}),{\mathcal {S}}),$

де $T$ використовується для позначення набору всіх можливих перетворень, які намагається знайти оптимізація. Найпоширенішим вибором функції для обчислення відстані є квадрат евклідової відстані для кожної пари точок:

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

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

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

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

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

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

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

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

Інші види

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

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

Методи на основі відповідностей припускають, що можливі відповідності $m\leftrightarrow s_{m}$ задані для кожної точки $m\in {\mathcal {M}}$ . Таким чином, отримуємо ситуацію, де обидві множини точок ${\mathcal {M}}$ і ${\mathcal {S}}$ мають $N$ точок, а $m_{i}\leftrightarrow s_{i},i=1,\dots ,N$ — це задані відповідності.

Узгодження без викидів

У найпростішому випадку можна припустити, що всі відповідності є правильними, тобто точки $m_{i},s_{i}\in \mathbb {R} ^{3}$ генеруються наступним чином:

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

(див. 1)

де $l>0$ є сталим коефіцієнтом масштабування обчислень (у багатьох випадках $l=1$), $R\in {\text{SO}}(3)$ є правильною 3D матрицею обертання (${\text{SO}}(d)$ є спеціальною ортогональною групою степеня $d$), $t\in \mathbb {R} ^{3}$ — це вектор паралельного перенесення та $\epsilon _{i}\in \mathbb {R} ^{3}$ моделює невідомий адитивний шум (наприклад, шум Гауса). Зокрема, якщо припустити, що шум $\epsilon _{i}$ має нульове середнє значення та ізотропний гаусівський розподіл зі стандартним відхиленням стандартним відхиленням $\sigma _{i}$, тобто $\epsilon _{i}\sim {\mathcal {N}}(0,\sigma _{i}^{2}I_{3})$, то оптимізація для отримання оцінки максимальної правдоподібності для невідомого масштабу, обертання та перетворення матиме наступний вигляд:

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

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

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

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

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

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

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

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

Максимальний консенсус прагне знайти найбільшу множину відповідностей, яка узгоджуюється з породжувальною моделлю (див. 1) для певного вибору просторового перетворення $(l,R,t)$. Формально, максимальний консенсус вирішує наступну оптимізацію:

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

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

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

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

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

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

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

М-оцінка

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

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

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

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

Градуйована неопуклість (англ. Graduated non-convexity) — це структура загального призначення для розв'язання задач невипуклої оптимізації без ініціалізації. Ця структура досягла успіху в додатках раннього зору та машинного навчання. Ключова ідея градуйованої неопуклості полягає в тому, щоб вирішити складну неопуклу проблему, починаючи з легкої опуклої задачі. Зокрема, для заданої стійкої функції витрат $\rho (\cdot )$, можна побудувати допоміжну функцію $\rho _{\mu }(\cdot )$ з гіперпараметром $\mu$, налаштування якої може поступово збільшувати невипуклість допоміжної функції $\rho _{\mu }(\cdot )$ поки вона не зійдеться до цільової функції $\rho (\cdot )$ . Отже, на кожному рівні гіперпараметра $\mu$, вирішується наступна оптимізація:

$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) можна створити двоїстість на зважену суму найменших квадратів і так звану функцію процесу викиду на вагових коефіцієнтах, які визначають достовірність оптимізації в кожній парі вимірювань. Використовуючи подвійність Блека-Рангараджана та градуйовану неопуклість, спеціально розроблену для функції Джемана-МакКлюра, Чжоу та ін. розробили швидкий глобальний алгоритм узгодження, який є стійким до приблизно 80 % викидів у відповідностях. Нещодавно Янг на ін. показали, що спільне використання градуйованої неопуклості (призначеної для функції Гемана-МакКлура і усіченої функції найменших квадратів) та двоїстості Блека-Рангараджана може призвести до розв'язку загального призначення для стійких проблем узгодження, включаючи узгодження хмари точок та сітки.

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

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

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

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

який отримується шляхом вибору усічених найменших квандратів (УНК) надійної функції втрат $\rho (x)=\min(x^{2},{\bar {c}}^{2})$, де ${\bar {c}}^{2}$ є заздалегідь визначеною константою, яка зумовлює максимально дозволені залишки, які вважаються внутрішніми. Цільова функція УНК має таку властивість, яка визначає, що для внутрішніх відповідностей ($\Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}<{\bar {c}}^{2}$), застосовується звичайний метод штрафів найменших квадратів; у той час як для відповідностей викидів ($\Vert s_{i}-lRm_{i}-t\Vert _{2}^{2}/\sigma _{i}^{2}>{\bar {c}}^{2}$) цей штраф не застосовується, а викиди відхиляються. Якщо оптимізація УНК (див. 7) розв'язується з глобальною оптимальністю, то вона еквівалентна методу Хорна лише для внутрішніх відповідностей.

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

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

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

Див. також

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

Посилання

• 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