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

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

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

(cb.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}$

(cb.2)

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

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

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

Відомо, що формулювання методу найменших квадратів ( cb.2 ) може працювати з низькою ефективністю за наявності викидів . Відповідність викидів – це пара вимірювань $s_{i}\leftrightarrow m_{i}$ що відхиляється від породжувальної моделі ( cb.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}}$

(cb.3)

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

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

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

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

(cb.4)

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

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

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

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

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

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

М-оцінка

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

(cb.5)

де $\rho (\cdot )$ представляє вибір стійкої функції витрат. Варто звернути увагу, що вибір $\rho (x)=x^{2}$ відновлює оцінку за методом найменших квадратів у ( cb.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)$

(cb.6)

Блек і Рангараджан довели, що для цільової функції кожної оптимізації ( cb.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)$

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

Однак, розв’язання ( cb.7 ) є досить складним через його комбінаторний характер. TEASER розв'язує ( cb.7 ) наступним чином:

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

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

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