Узгодження множин точок (англ. point set registration, англ. point matching) у теорії розпізнавання образів та комп'ютерному зорі є процесом знаходження просторового перетворення, яке узгоджує дві множини точок. Метою знаходження такого перетворення є злиття декількох множин точок у глобально цілісну модель і відображення нового вимірювання на відомий набір даних для виявлення ознак або оцінювання його [en]. Множина точок може бути вхідними даними з 3D-сканера або масивом, отриманим від далекоміра. Для використання в обробці зображень і реєстрації зображень на основі ознак, множина точок може бути множиною ознак, отриманою виділянням ознак із зображення, наприклад, виявленням кутів. Узгодження множин точок має широке застосування в оптичному розпізнаванні символів, у доповненій реальності та суміщенні даних магнітно-резонансної томографії зі знімками комп'ютерної томографії.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOW1MMlpsTDBOd1pGOW1hWE5vWDJGbVptbHVaUzVuYVdZdk1qSXdjSGd0UTNCa1gyWnBjMmhmWVdabWFXNWxMbWRwWmc9PS5naWY=.gif)
Формулювання
Проблему можна узагальнити наступним чином:
Нехай — це дві множини точок скінченного розміру у скінченновимірному дійсному векторному просторі
, які містять
і
точок відповідно (наприклад,
демонструє типовий випадок, коли
і
є множинами 3D-точок). Завдання полягає в тому, щоб знайти таке перетворення, яке буде застосовано до рухомої «моделі» множини точок
так, щоб різниця (зазвичай визначається як евклідова відстань) між
та статичною множиною об'єктів «сцени»
була зведена до мінімуму. Іншими словами, потрібно знайти відображення з
на
, яке дає найкраще вирівнювання між трансформованими «модельною» множиною та множиною «сцени». Відображення може складатися з [en] або нежорсткого перетворення. Модель перетворення можна записати як
, за допомогою якої перетворена та узгоджена множина точок моделі матиме вигляд:
Таким чином, результатом алгоритму узгодження множин точок є оптимальне перетворення таке, що
найкраще вирівнюється по
відповідно до поняття функції відстані
:
де використовується для позначення набору всіх можливих перетворень, які намагається знайти оптимізація. Найпоширенішим вибором функції для обчислення відстані є квадрат евклідової відстані для кожної пари точок:
де вказує на довжину вектора, а
— на відповідну точку в множині
, яка досягає найкоротшої відстані до даної точки
у множині
після перетворення. Мінімізація такої функції у випадку [en] еквівалентна методу найменших квадратів.
Види алгоритмів
Якщо співвідношення (тобто, ) відомі до оптимізації, наприклад, за допомогою методів (зіставлення ознак), тоді оптимізація має на меті лише оцінити перетворення. Цей тип узгодження називається узгодженням на основі відповідностей (заочне узгодження). З іншого боку, якщо відповідності невідомі, то оптимізації потрібно одночасно знайти відповідності та перетворення. Цей тип узгодження називається одночасним узгодженням положення та відповідності.
Жорстке узгодження
За допомогою жорсткого узгодження можна отримати [en], яке відображає одну множину точок нанесену на іншу. Жорстке перетворення визначається як перетворення, яке не змінює відстань між будь-якими двома точками. Зазвичай така трансформація складається з паралельного перенесення та обертання. У рідкісних випадках множина точок також може бути дзеркальною. Найбільшого застосування жорстке узгодження множин точок набує у робототехніці та комп'ютерному зорі.
Нежорстке перетворення
За допомогою нежорсткого узгодження можна отримати нежорстке (нелінійне) узгодження, яке відображає одну множину точок на іншу. Нежорсткі перетворення містять в собі афінні перетворення, такі як [en] та відображення зсуву. Однак, у контексті узгодження множини точок нежорстке зазвичай включає нелінійне перетворення. Якщо відомі власні вектори множини точок, нелінійне перетворення може бути параметризоване власними значеннями. Нелінійне перетворення також може бути параметризовано за допомогою [en].
Інші види
Деякі підходи до узгодження множин точок використовують алгоритми, які вирішують більш загальну задачу [en]. Однак, обчислювальна складність таких методів, як правило, висока, і вони обмежені жорсткими узгодженнями. PCL (Point Cloud Library) — це фреймворк з відкритим вихідним кодом для n-вимірної множини точок і обробки 3D-геометрії, що містить кілька алгоритмів узгодження точок.
Узгодження на основі відповідностей
Методи на основі відповідностей припускають, що можливі відповідності задані для кожної точки
. Таким чином, отримуємо ситуацію, де обидві множини точок
і
мають
точок, а
— це задані відповідності.
Узгодження без викидів
У найпростішому випадку можна припустити, що всі відповідності є правильними, тобто точки генеруються наступним чином:
-
(
)
де є сталим [en] обчислень (у багатьох випадках
),
є правильною 3D матрицею обертання (
є спеціальною ортогональною групою степеня
),
— це вектор паралельного перенесення та
моделює невідомий адитивний шум (наприклад, шум Гауса). Зокрема, якщо припустити, що шум
має нульове середнє значення та ізотропний гаусівський розподіл зі стандартним відхиленням стандартним відхиленням
, тобто
, то оптимізація для отримання оцінки максимальної правдоподібності для невідомого масштабу, обертання та перетворення матиме наступний вигляд:
-
(
)
Зауважимо, що коли коефіцієнт масштабування дорівнює 1, а вектор паралельного перенесення дорівнює нулю, то тоді оптимізація відновлює формулювання [en]. Незважаючи на неопуклість оптимізації (див. 2) через неопуклість множини основоположна робота Бертольда К. П. Хорна показала, що (див. 2) фактично має розв'язок у вигляді замкнутої формули, шляхом розділення оцінки масштабу, повороту та паралельного перенесення. Подібні результати були виявлені Аруном та співавторами. Крім того, щоб знайти унікальне перетворення
для кожної множини точок потрібно як мінімум
неколінеарні точки.
Зовсім нещодавно Бріалес і Гонсалес-Хіменес розробили напіввизначену релаксацію, використовуючи двоїстість Лагранжа, для випадку, коли множина моделей містить різні 3D-примітиви, такі як точки, лінії та площини (в тому випадку, коли модель
є 3D-сіткою). Цікаво, що напіввизначена релаксація є емпірично жорсткою, тобто з розв'язку напіввизначеної релаксації можна отримати глобально оптимальний розв'язок.
Стійке узгодження
Відомо, що формулювання методу найменших квадратів (див. 2) може працювати з низькою ефективністю за наявності викидів. Відповідність викидів — це пара вимірювань що відхиляється від породжувальної моделі (див. 1). У цьому випадку можна розглянути іншу породжувальну модель таку, як:
-
(
)
де якщо -та пара
входить до множини вхідних даних, то вона відповідає моделі без випадкових помилок (див. 1), тобто
отримується з
шляхом просторового перетворення і додавання невеликого шуму. Однак, якщо
-та пара
є викидом, то вектор
може бути будь-яким довільним вектором
. Оскільки заздалегідь невідомо, які відповідності є викидами, стійке узгодження за породжувальною моделлю (див. 3) є надзвичайно важливим для комп'ютерного зору та робототехніки, бо поточні методи зіставлення функцій мають тенденцію виводити сильно спотворені відповідності, де понад
відповідностей можуть бути викидами.
Далі опишемо кілька поширених парадигм стійкого узгодження.
Максимальний консенсус
Максимальний консенсус прагне знайти найбільшу множину відповідностей, яка узгоджуюється з породжувальною моделлю (див. 1) для певного вибору просторового перетворення . Формально, максимальний консенсус вирішує наступну оптимізацію:
-
(
)
де позначає потужність множини
. Обмеження у формулі (див. 4) забезпечують те, що кожна пара вимірювань у множині відповідних точок
, що задовольняють моделі без викидів, має менший залишок, ніж заданий поріг
. На жаль, нещодавні дослідження показали, що глобальне розв'язання проблеми (див. 4) є NP-складною задачею, і глобальні алгоритми, як правило, мають використовувати метод гілок і меж, який має експоненційну складність у найгіршому випадку.
Хоча розв'язання задачі максимального консенсусу є складним, існують ефективні евристики, які досить добре працюють на практиці. Однією з найпоширеніших евристикою є метод RANSAC. RANSAC — це ітеративний метод гіпотези та перевірки. На кожному кроці ітерації метод спочатку випадково вибирає 3 із загальної кількості відповідності та обчислює гіпотезу
з використанням методу Горна, потім метод оцінює обмеження в (див. 4), щоб порахувати, скільки відповідностей фактично збігаються з такою гіпотезою (тобто обчислює залишкову величину
та порівнює її з порогом
для кожної пари вимірювань). Алгоритм завершується або після того, як він знайшов множину консенсусу з достатньою кількістю відповідностей, або після того, як було досягнуто загальної кількості допустимих ітерацій. RANSAC є високоефективний, оскільки основним обчисленням на кожній ітерації є розв'язання задачі за допомогою методу Горна. Однак RANSAC є недетермінованим та працює добре тільки в режимі низького відсотку викидів (наприклад, менше
), оскільки його час роботи зростає експоненційно відносно відсотку викидів.
Для заповнення прогалини між швидким, але неточним методом RANSAC та точним, але вичерпним оптимізаційним методом гілок і меж, останні дослідження розробили детерміновані наближені методи вирішення максимізації консенсусу.
Видалення викидів
Методи видалення викидів спрямовані на попередню обробку набору сильно пошкоджених відповідностей перед оцінкою просторового перетворення. Метою видалення викидів є зменшення кількості викидів, при цьому зберігаючи внутрішні відповідності, щоб оптимізація через перетворення стала легшою та ефективнішою (наприклад, RANSAC працює погано, коли відношення викидів вище але працює досить добре, коли коефіцієнт викиду нижче
).
Парра Бустос та ін. запропонували метод під назвою Гарантоване Видалення Викидів (ГВВ), який використовує геометричні обмеження для скорочення відповідностей викидів, гарантуючи збереження внутрішніх відповідностей. Встановлено, що метод гарантованого видалення викидів здатний різко зменшити коефіцієнт викидів, що може значно підвищити ефективність максимізації консенсусу за допомогою RANSAC або методу гілок і меж. Янг і Карлоун запропонували побудувати попарні інваріантні вимірювання зсуву та обертання (англ. translation-and-rotation-invariant measurements) з вихідного набору вимірювань та вбудувати TRIM як ребра графа, вузлами якого є тривимірні точки. Оскільки внутрішні точки попарно узгоджені з точки зору масштабу, то вони повинні утворювати кліку в межах графа. Таким чином, використовуючи ефективні алгоритми для обчислення максимальної кліки на графі, можна знайти вхідні значення та ефективно виключити викиди. Метод видалення викидів на основі задачі про кліки також виявився досить корисним у проблемах узгодження множин точок у реальному світі. Подібні ідеї видалення викидів також були запропоновані Парра Бустосом та ін..
М-оцінка
M-оцінка замінює метод найменших квадратів у (див. 2) стійкою функцією витрат, яка є менш чутливою до викидів. Формально М-оцінка прагне вирішити наступну проблему:
-
(
)
де представляє вибір стійкої функції витрат. Варто звернути увагу, що вибір
відновлює оцінку за методом найменших квадратів у (див. 2). Поширені стійкі функції витрат містять
— норми втрат, втрати Губера, втрати Джемана-МакКлюра і втрати за методом найменших квадратів. М-оцінка була однією з загальновживаних парадигм стійкої оцінки в робототехніці та комп'ютерному зорі. Оскільки стійкі цільові функції зазвичай не є опуклими (наприклад, обрізана відносна квадратична втрата в порівнянні з відносною квадратичною втратою), алгоритми для розв'язання задачі невипуклої оцінки М-шляхом, зазвичай ґрунтуються на локальній оптимізації, де спочатку відбувається початкове припущення, а потім застосовуються ітеративні виправлення перетворення, щоб продовжувати зменшувати значення об'єктивної функції. Локальна оптимізація, як правило, працює добре, коли початкове припущення близьке до глобального мінімуму, але вона також має схильність застрягати в локальних мінімумах, якщо надано погану початкову ініціалізацію.
Градуйована неопуклість
Градуйована неопуклість (англ. Graduated non-convexity) — це структура загального призначення для розв'язання задач невипуклої оптимізації без ініціалізації. Ця структура досягла успіху в додатках раннього зору та машинного навчання. Ключова ідея градуйованої неопуклості полягає в тому, щоб вирішити складну неопуклу проблему, починаючи з легкої опуклої задачі. Зокрема, для заданої стійкої функції витрат , можна побудувати допоміжну функцію
з гіперпараметром
, налаштування якої може поступово збільшувати невипуклість допоміжної функції
поки вона не зійдеться до цільової функції
. Отже, на кожному рівні гіперпараметра
, вирішується наступна оптимізація:
-
(
)
Блек і Рангараджан довели, що для цільової функції кожної оптимізації (див. 6) можна створити двоїстість на [en] і так звану функцію процесу викиду на вагових коефіцієнтах, які визначають достовірність оптимізації в кожній парі вимірювань. Використовуючи подвійність Блека-Рангараджана та градуйовану неопуклість, спеціально розроблену для функції Джемана-МакКлюра, Чжоу та ін. розробили швидкий глобальний алгоритм узгодження, який є стійким до приблизно 80 % викидів у відповідностях. Нещодавно Янг на ін. показали, що спільне використання градуйованої неопуклості (призначеної для функції Гемана-МакКлура і усіченої функції найменших квадратів) та двоїстості Блека-Рангараджана може призвести до розв'язку загального призначення для стійких проблем узгодження, включаючи узгодження хмари точок та сітки.
Сертифіковано стійке узгодження
Майже жоден із згаданих вище алгоритмів стійкого узгодження (за винятком алгоритму гілок і меж, який у гіршому випадку працює в експоненційному часі) не має гарантій продуктивності, а це означає, що ці алгоритми можуть повертати абсолютно неправильні оцінки без попередження. Тому ці алгоритми не є найдіними для критично важливих застосувань, таких як самокероване водіння.
Зовсім нещодавно Янг та співавтори розробили перший алгоритм стійкого узгодження з гарантією надійності, під назвою «Оцінка за методом усічених найменших квадратів і напіввизначеної релаксації» (англ. Truncated least squares Estimation And Semidefinite Relaxation). Для угодження множини точок TEASER не тільки виводить оцінку перетворення, але й кількісно визначає оптимальність даної оцінки. TEASER використовує наступний оцінювач за методом усічених найменших квадратів:
-
(
)
який отримується шляхом вибору усічених найменших квандратів (УНК) надійної функції втрат , де
є заздалегідь визначеною константою, яка зумовлює максимально дозволені залишки, які вважаються внутрішніми. Цільова функція УНК має таку властивість, яка визначає, що для внутрішніх відповідностей (
), застосовується звичайний метод штрафів найменших квадратів; у той час як для відповідностей викидів (
) цей штраф не застосовується, а викиди відхиляються. Якщо оптимізація УНК (див. 7) розв'язується з глобальною оптимальністю, то вона еквівалентна методу Хорна лише для внутрішніх відповідностей.
Однак, розв'язання (див. 7) є досить складним через його комбінаторний характер. Оцінка за методом усічених найменших квадратів і напіввизначеної релаксації розв'язує (див. 7) наступним чином: (i) Вона створює інваріантні вимірювання таким чином, що оцінка масштабу, обертання та перетворення можуть бути відокремлені та розв'язана окремо. Ця стратегія заснована на оригінальній схемі Горнера.
(ii) Та ж оцінка усічених найменших квадратів (далі — УНК) застосовується для кожної з трьох підзадач, де задача УНК масштабу може бути розв'язана за допомогою алгоритму, що називається адаптивним голосуванням. Задача обертання УНК можна послабити до напіввизначеної програми, де релаксація є точною на практиці, навіть із великою кількістю викидів. Задачу зсуву УНК можна вирішити використовуючи покомпонентне адаптивне голосування. Швидке впровадження, що використовує градуйовану неопуклість, має наступний код з відкритим доступом тут. На практиці оцінка за методом усічених квадратів і напіввизначенох релаксації може витримати більше ніж викидів відповідностей і виконуватись за мілісекунди.
Крім розробки оцінки за методом усічених квадратів і напіввизначеної релаксації, Янг та співавтори також довели, що за деяких слабких умов на заданій множині точок оцінка перетворення усічених квадратів і напіввизначеної релаксації має певні похибки в порівнянні із справжнім перетворенням.
Див. також
Примітки
- 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. (англ.)
- 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. (англ.)
- 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. (англ.)
- 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. (англ.)
- 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. (англ.)
- 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.(англ.)
- 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.(англ.)
- 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.(англ.)
- 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.
- 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.
- 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=
() - 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.
- 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.
- 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.
- 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.
- 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 .
- 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=
() - 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.
- 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.
- 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 .
- 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 .
- 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 .
- 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.
- 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 .
- 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.
- 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.
- Blake, Andrew; Zisserman, Andrew (1987). Visual reconstruction. The MIT Press. ISBN .
- 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.
- 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.
- 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Uzgodzhennya mnozhin tochok angl point set registration angl point matching u teoriyi rozpiznavannya obraziv ta komp yuternomu zori ye procesom znahodzhennya prostorovogo peretvorennya yake uzgodzhuye dvi mnozhini tochok Metoyu znahodzhennya takogo peretvorennya ye zlittya dekilkoh mnozhin tochok u globalno cilisnu model i vidobrazhennya novogo vimiryuvannya na vidomij nabir danih dlya viyavlennya oznak abo ocinyuvannya jogo en Mnozhina tochok mozhe buti vhidnimi danimi z 3D skanera abo masivom otrimanim vid dalekomira Dlya vikoristannya v obrobci zobrazhen i reyestraciyi zobrazhen na osnovi oznak mnozhina tochok mozhe buti mnozhinoyu oznak otrimanoyu vidilyannyam oznak iz zobrazhennya napriklad viyavlennyam kutiv Uzgodzhennya mnozhin tochok maye shiroke zastosuvannya v optichnomu rozpiznavanni simvoliv u dopovnenij realnosti ta sumishenni danih magnitno rezonansnoyi tomografiyi zi znimkami komp yuternoyi tomografiyi Uzgodzhennya mnozhin tochok ye procesom uzgodzhennya dvoh mnozhin tochok Na malyunku blakitna riba uzgodzhuyetsya z chervonoyu FormulyuvannyaProblemu mozhna uzagalniti nastupnim chinom Nehaj M S displaystyle lbrace mathcal M mathcal S rbrace ce dvi mnozhini tochok skinchennogo rozmiru u skinchennovimirnomu dijsnomu vektornomu prostori R d displaystyle mathbb R d yaki mistyat M displaystyle M i N displaystyle N tochok vidpovidno napriklad d 3 displaystyle d 3 demonstruye tipovij vipadok koli M displaystyle mathcal M i S displaystyle mathcal S ye mnozhinami 3D tochok Zavdannya polyagaye v tomu shob znajti take peretvorennya yake bude zastosovano do ruhomoyi modeli mnozhini tochok M displaystyle mathcal M tak shob riznicya zazvichaj viznachayetsya yak evklidova vidstan mizh M displaystyle mathcal M ta statichnoyu mnozhinoyu ob yektiv sceni S displaystyle mathcal S bula zvedena do minimumu Inshimi slovami potribno znajti vidobrazhennya z R d displaystyle mathbb R d na R d displaystyle mathbb R d yake daye najkrashe virivnyuvannya mizh transformovanimi modelnoyu mnozhinoyu ta mnozhinoyu sceni Vidobrazhennya mozhe skladatisya z en abo nezhorstkogo peretvorennya Model peretvorennya mozhna zapisati yak T displaystyle T za dopomogoyu yakoyi peretvorena ta uzgodzhena mnozhina tochok modeli matime viglyad T M displaystyle T mathcal M Takim chinom rezultatom algoritmu uzgodzhennya mnozhin tochok ye optimalne peretvorennya T displaystyle T star take sho M displaystyle mathcal M najkrashe virivnyuyetsya po S displaystyle mathcal S vidpovidno do ponyattya funkciyi vidstani dist displaystyle operatorname dist cdot cdot T arg min T T dist T M S displaystyle T star arg min T in mathcal T text dist T mathcal M mathcal S de T displaystyle T vikoristovuyetsya dlya poznachennya naboru vsih mozhlivih peretvoren yaki namagayetsya znajti optimizaciya Najposhirenishim viborom funkciyi dlya obchislennya vidstani ye kvadrat evklidovoyi vidstani dlya kozhnoyi pari tochok dist T M S m T M m s m 2 2 s m arg min s S s m 2 2 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 de 2 displaystyle cdot 2 vkazuye na dovzhinu vektora a s m displaystyle s m na vidpovidnu tochku v mnozhini S displaystyle mathcal S yaka dosyagaye najkorotshoyi vidstani do danoyi tochki m displaystyle m u mnozhini M displaystyle mathcal M pislya peretvorennya Minimizaciya takoyi funkciyi u vipadku en ekvivalentna metodu najmenshih kvadrativ Vidi algoritmivYaksho spivvidnoshennya tobto s m m displaystyle s m leftrightarrow m vidomi do optimizaciyi napriklad za dopomogoyu metodiv zistavlennya oznak todi optimizaciya maye na meti lishe ociniti peretvorennya Cej tip uzgodzhennya nazivayetsya uzgodzhennyam na osnovi vidpovidnostej zaochne uzgodzhennya Z inshogo boku yaksho vidpovidnosti nevidomi to optimizaciyi potribno odnochasno znajti vidpovidnosti ta peretvorennya Cej tip uzgodzhennya nazivayetsya odnochasnim uzgodzhennyam polozhennya ta vidpovidnosti Zhorstke uzgodzhennya Za dopomogoyu zhorstkogo uzgodzhennya mozhna otrimati en yake vidobrazhaye odnu mnozhinu tochok nanesenu na inshu Zhorstke peretvorennya viznachayetsya yak peretvorennya yake ne zminyuye vidstan mizh bud yakimi dvoma tochkami Zazvichaj taka transformaciya skladayetsya z paralelnogo perenesennya ta obertannya U ridkisnih vipadkah mnozhina tochok takozh mozhe buti dzerkalnoyu Najbilshogo zastosuvannya zhorstke uzgodzhennya mnozhin tochok nabuye u robototehnici ta komp yuternomu zori Nezhorstke peretvorennya Za dopomogoyu nezhorstkogo uzgodzhennya mozhna otrimati nezhorstke nelinijne uzgodzhennya yake vidobrazhaye odnu mnozhinu tochok na inshu Nezhorstki peretvorennya mistyat v sobi afinni peretvorennya taki yak en ta vidobrazhennya zsuvu Odnak u konteksti uzgodzhennya mnozhini tochok nezhorstke zazvichaj vklyuchaye nelinijne peretvorennya Yaksho vidomi vlasni vektori mnozhini tochok nelinijne peretvorennya mozhe buti parametrizovane vlasnimi znachennyami Nelinijne peretvorennya takozh mozhe buti parametrizovano za dopomogoyu en Inshi vidi Deyaki pidhodi do uzgodzhennya mnozhin tochok vikoristovuyut algoritmi yaki virishuyut bilsh zagalnu zadachu en Odnak obchislyuvalna skladnist takih metodiv yak pravilo visoka i voni obmezheni zhorstkimi uzgodzhennyami PCL Point Cloud Library ce frejmvork z vidkritim vihidnim kodom dlya n vimirnoyi mnozhini tochok i obrobki 3D geometriyi sho mistit kilka algoritmiv uzgodzhennya tochok Uzgodzhennya na osnovi vidpovidnostejMetodi na osnovi vidpovidnostej pripuskayut sho mozhlivi vidpovidnosti m s m displaystyle m leftrightarrow s m zadani dlya kozhnoyi tochki m M displaystyle m in mathcal M Takim chinom otrimuyemo situaciyu de obidvi mnozhini tochok M displaystyle mathcal M i S displaystyle mathcal S mayut N displaystyle N tochok a m i s i i 1 N displaystyle m i leftrightarrow s i i 1 dots N ce zadani vidpovidnosti Uzgodzhennya bez vikidiv U najprostishomu vipadku mozhna pripustiti sho vsi vidpovidnosti ye pravilnimi tobto tochki m i s i R 3 displaystyle m i s i in mathbb R 3 generuyutsya nastupnim chinom s i l R m i t ϵ i i 1 N displaystyle s i lRm i t epsilon i i 1 dots N div 1 de l gt 0 displaystyle l gt 0 ye stalim en obchislen u bagatoh vipadkah l 1 displaystyle l 1 R SO 3 displaystyle R in text SO 3 ye pravilnoyu 3D matriceyu obertannya SO d displaystyle text SO d ye specialnoyu ortogonalnoyu grupoyu stepenya d displaystyle d t R 3 displaystyle t in mathbb R 3 ce vektor paralelnogo perenesennya ta ϵ i R 3 displaystyle epsilon i in mathbb R 3 modelyuye nevidomij aditivnij shum napriklad shum Gausa Zokrema yaksho pripustiti sho shum ϵ i displaystyle epsilon i maye nulove serednye znachennya ta izotropnij gausivskij rozpodil zi standartnim vidhilennyam standartnim vidhilennyam s i displaystyle sigma i tobto ϵ i N 0 s i 2 I 3 displaystyle epsilon i sim mathcal N 0 sigma i 2 I 3 to optimizaciya dlya otrimannya ocinki maksimalnoyi pravdopodibnosti dlya nevidomogo masshtabu obertannya ta peretvorennya matime nastupnij viglyad l R t arg min l gt 0 R SO 3 t R 3 i 1 N 1 s i 2 s i l R m i t 2 2 displaystyle l star R star t star arg min l gt 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 div 2 Zauvazhimo sho koli koeficiyent masshtabuvannya dorivnyuye 1 a vektor paralelnogo perenesennya dorivnyuye nulyu to todi optimizaciya vidnovlyuye formulyuvannya en Nezvazhayuchi na neopuklist optimizaciyi div 2 cherez neopuklist mnozhini SO 3 displaystyle text SO 3 osnovopolozhna robota Bertolda K P Horna pokazala sho div 2 faktichno maye rozv yazok u viglyadi zamknutoyi formuli shlyahom rozdilennya ocinki masshtabu povorotu ta paralelnogo perenesennya Podibni rezultati buli viyavleni Arunom ta spivavtorami Krim togo shob znajti unikalne peretvorennya l R t displaystyle l R t dlya kozhnoyi mnozhini tochok potribno yak minimum N 3 displaystyle N 3 nekolinearni tochki Zovsim neshodavno Briales i Gonsales Himenes rozrobili napivviznachenu relaksaciyu vikoristovuyuchi dvoyistist Lagranzha dlya vipadku koli mnozhina modelej M displaystyle mathcal M mistit rizni 3D primitivi taki yak tochki liniyi ta ploshini v tomu vipadku koli model M displaystyle mathcal M ye 3D sitkoyu Cikavo sho napivviznachena relaksaciya ye empirichno zhorstkoyu tobto z rozv yazku napivviznachenoyi relaksaciyi mozhna otrimati globalno optimalnij rozv yazok Stijke uzgodzhennya Vidomo sho formulyuvannya metodu najmenshih kvadrativ div 2 mozhe pracyuvati z nizkoyu efektivnistyu za nayavnosti vikidiv Vidpovidnist vikidiv ce para vimiryuvan s i m i displaystyle s i leftrightarrow m i sho vidhilyayetsya vid porodzhuvalnoyi modeli div 1 U comu vipadku mozhna rozglyanuti inshu porodzhuvalnu model taku yak s i l R m i t ϵ i if i th pair is an inlier o i if i th pair is an outlier displaystyle s i begin cases lRm i t epsilon i amp text if i text th pair is an inlier o i amp text if i text th pair is an outlier end cases div 3 de yaksho i displaystyle i ta para s i m i displaystyle s i leftrightarrow m i vhodit do mnozhini vhidnih danih to vona vidpovidaye modeli bez vipadkovih pomilok div 1 tobto s i displaystyle s i otrimuyetsya z m i displaystyle m i shlyahom prostorovogo peretvorennya i dodavannya nevelikogo shumu Odnak yaksho i displaystyle i ta para s i m i displaystyle s i leftrightarrow m i ye vikidom to vektor s i displaystyle s i mozhe buti bud yakim dovilnim vektorom o i displaystyle o i Oskilki zazdalegid nevidomo yaki vidpovidnosti ye vikidami stijke uzgodzhennya za porodzhuvalnoyu modellyu div 3 ye nadzvichajno vazhlivim dlya komp yuternogo zoru ta robototehniki bo potochni metodi zistavlennya funkcij mayut tendenciyu vivoditi silno spotvoreni vidpovidnosti de ponad 95 displaystyle 95 vidpovidnostej mozhut buti vikidami Dali opishemo kilka poshirenih paradigm stijkogo uzgodzhennya Maksimalnij konsensus Maksimalnij konsensus pragne znajti najbilshu mnozhinu vidpovidnostej yaka uzgodzhuyuyetsya z porodzhuvalnoyu modellyu div 1 dlya pevnogo viboru prostorovogo peretvorennya l R t displaystyle l R t Formalno maksimalnij konsensus virishuye nastupnu optimizaciyu max l gt 0 R SO 3 t R 3 I I subject to 1 s i 2 s i l R m i t 2 2 3 i I displaystyle max l gt 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 div 4 de I displaystyle vert mathcal I vert poznachaye potuzhnist mnozhini I displaystyle mathcal I Obmezhennya u formuli div 4 zabezpechuyut te sho kozhna para vimiryuvan u mnozhini vidpovidnih tochok I displaystyle mathcal I sho zadovolnyayut modeli bez vikidiv maye menshij zalishok nizh zadanij porig 3 displaystyle xi Na zhal neshodavni doslidzhennya pokazali sho globalne rozv yazannya problemi div 4 ye NP skladnoyu zadacheyu i globalni algoritmi yak pravilo mayut vikoristovuvati metod gilok i mezh yakij maye eksponencijnu skladnist u najgirshomu vipadku Hocha rozv yazannya zadachi maksimalnogo konsensusu ye skladnim isnuyut efektivni evristiki yaki dosit dobre pracyuyut na praktici Odniyeyu z najposhirenishih evristikoyu ye metod RANSAC RANSAC ce iterativnij metod gipotezi ta perevirki Na kozhnomu kroci iteraciyi metod spochatku vipadkovo vibiraye 3 iz zagalnoyi kilkosti N displaystyle N vidpovidnosti ta obchislyuye gipotezu l R t displaystyle l R t z vikoristannyam metodu Gorna potim metod ocinyuye obmezhennya v div 4 shob porahuvati skilki vidpovidnostej faktichno zbigayutsya z takoyu gipotezoyu tobto obchislyuye zalishkovu velichinu s i l R m i t 2 2 s i 2 displaystyle Vert s i lRm i t Vert 2 2 sigma i 2 ta porivnyuye yiyi z porogom 3 displaystyle xi dlya kozhnoyi pari vimiryuvan Algoritm zavershuyetsya abo pislya togo yak vin znajshov mnozhinu konsensusu z dostatnoyu kilkistyu vidpovidnostej abo pislya togo yak bulo dosyagnuto zagalnoyi kilkosti dopustimih iteracij RANSAC ye visokoefektivnij oskilki osnovnim obchislennyam na kozhnij iteraciyi ye rozv yazannya zadachi za dopomogoyu metodu Gorna Odnak RANSAC ye nedeterminovanim ta pracyuye dobre tilki v rezhimi nizkogo vidsotku vikidiv napriklad menshe 50 displaystyle 50 oskilki jogo chas roboti zrostaye eksponencijno vidnosno vidsotku vikidiv Dlya zapovnennya progalini mizh shvidkim ale netochnim metodom RANSAC ta tochnim ale vicherpnim optimizacijnim metodom gilok i mezh ostanni doslidzhennya rozrobili determinovani nablizheni metodi virishennya maksimizaciyi konsensusu Vidalennya vikidiv Metodi vidalennya vikidiv spryamovani na poperednyu obrobku naboru silno poshkodzhenih vidpovidnostej pered ocinkoyu prostorovogo peretvorennya Metoyu vidalennya vikidiv ye zmenshennya kilkosti vikidiv pri comu zberigayuchi vnutrishni vidpovidnosti shob optimizaciya cherez peretvorennya stala legshoyu ta efektivnishoyu napriklad RANSAC pracyuye pogano koli vidnoshennya vikidiv vishe 95 displaystyle 95 ale pracyuye dosit dobre koli koeficiyent vikidu nizhche 50 displaystyle 50 Parra Bustos ta in zaproponuvali metod pid nazvoyu Garantovane Vidalennya Vikidiv GVV yakij vikoristovuye geometrichni obmezhennya dlya skorochennya vidpovidnostej vikidiv garantuyuchi zberezhennya vnutrishnih vidpovidnostej Vstanovleno sho metod garantovanogo vidalennya vikidiv zdatnij rizko zmenshiti koeficiyent vikidiv sho mozhe znachno pidvishiti efektivnist maksimizaciyi konsensusu za dopomogoyu RANSAC abo metodu gilok i mezh Yang i Karloun zaproponuvali pobuduvati poparni invariantni vimiryuvannya zsuvu ta obertannya angl translation and rotation invariant measurements z vihidnogo naboru vimiryuvan ta vbuduvati TRIM yak rebra grafa vuzlami yakogo ye trivimirni tochki Oskilki vnutrishni tochki poparno uzgodzheni z tochki zoru masshtabu to voni povinni utvoryuvati kliku v mezhah grafa Takim chinom vikoristovuyuchi efektivni algoritmi dlya obchislennya maksimalnoyi kliki na grafi mozhna znajti vhidni znachennya ta efektivno viklyuchiti vikidi Metod vidalennya vikidiv na osnovi zadachi pro kliki takozh viyavivsya dosit korisnim u problemah uzgodzhennya mnozhin tochok u realnomu sviti Podibni ideyi vidalennya vikidiv takozh buli zaproponovani Parra Bustosom ta in M ocinka M ocinka zaminyuye metod najmenshih kvadrativ u div 2 stijkoyu funkciyeyu vitrat yaka ye mensh chutlivoyu do vikidiv Formalno M ocinka pragne virishiti nastupnu problemu l R t arg min l gt 0 R SO 3 t R 3 i 1 N r 1 s i s i l R m i t 2 displaystyle l star R star t star arg min l gt 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 div 5 de r displaystyle rho cdot predstavlyaye vibir stijkoyi funkciyi vitrat Varto zvernuti uvagu sho vibir r x x 2 displaystyle rho x x 2 vidnovlyuye ocinku za metodom najmenshih kvadrativ u div 2 Poshireni stijki funkciyi vitrat mistyat ℓ 1 displaystyle ell 1 normi vtrat vtrati Gubera vtrati Dzhemana MakKlyura i vtrati za metodom najmenshih kvadrativ M ocinka bula odniyeyu z zagalnovzhivanih paradigm stijkoyi ocinki v robototehnici ta komp yuternomu zori Oskilki stijki cilovi funkciyi zazvichaj ne ye opuklimi napriklad obrizana vidnosna kvadratichna vtrata v porivnyanni z vidnosnoyu kvadratichnoyu vtratoyu algoritmi dlya rozv yazannya zadachi nevipukloyi ocinki M shlyahom zazvichaj gruntuyutsya na lokalnij optimizaciyi de spochatku vidbuvayetsya pochatkove pripushennya a potim zastosovuyutsya iterativni vipravlennya peretvorennya shob prodovzhuvati zmenshuvati znachennya ob yektivnoyi funkciyi Lokalna optimizaciya yak pravilo pracyuye dobre koli pochatkove pripushennya blizke do globalnogo minimumu ale vona takozh maye shilnist zastryagati v lokalnih minimumah yaksho nadano poganu pochatkovu inicializaciyu Gradujovana neopuklist Gradujovana neopuklist angl Graduated non convexity ce struktura zagalnogo priznachennya dlya rozv yazannya zadach nevipukloyi optimizaciyi bez inicializaciyi Cya struktura dosyagla uspihu v dodatkah rannogo zoru ta mashinnogo navchannya Klyuchova ideya gradujovanoyi neopuklosti polyagaye v tomu shob virishiti skladnu neopuklu problemu pochinayuchi z legkoyi opukloyi zadachi Zokrema dlya zadanoyi stijkoyi funkciyi vitrat r displaystyle rho cdot mozhna pobuduvati dopomizhnu funkciyu r m displaystyle rho mu cdot z giperparametrom m displaystyle mu nalashtuvannya yakoyi mozhe postupovo zbilshuvati nevipuklist dopomizhnoyi funkciyi r m displaystyle rho mu cdot poki vona ne zijdetsya do cilovoyi funkciyi r displaystyle rho cdot Otzhe na kozhnomu rivni giperparametra m displaystyle mu virishuyetsya nastupna optimizaciya l m R m t m arg min l gt 0 R SO 3 t R 3 i 1 N r m 1 s i s i l R m i t 2 displaystyle l mu star R mu star t mu star arg min l gt 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 div 6 Blek i Rangaradzhan doveli sho dlya cilovoyi funkciyi kozhnoyi optimizaciyi div 6 mozhna stvoriti dvoyistist na en i tak zvanu funkciyu procesu vikidu na vagovih koeficiyentah yaki viznachayut dostovirnist optimizaciyi v kozhnij pari vimiryuvan Vikoristovuyuchi podvijnist Bleka Rangaradzhana ta gradujovanu neopuklist specialno rozroblenu dlya funkciyi Dzhemana MakKlyura Chzhou ta in rozrobili shvidkij globalnij algoritm uzgodzhennya yakij ye stijkim do priblizno 80 vikidiv u vidpovidnostyah Neshodavno Yang na in pokazali sho spilne vikoristannya gradujovanoyi neopuklosti priznachenoyi dlya funkciyi Gemana MakKlura i usichenoyi funkciyi najmenshih kvadrativ ta dvoyistosti Bleka Rangaradzhana mozhe prizvesti do rozv yazku zagalnogo priznachennya dlya stijkih problem uzgodzhennya vklyuchayuchi uzgodzhennya hmari tochok ta sitki Sertifikovano stijke uzgodzhennya Majzhe zhoden iz zgadanih vishe algoritmiv stijkogo uzgodzhennya za vinyatkom algoritmu gilok i mezh yakij u girshomu vipadku pracyuye v eksponencijnomu chasi ne maye garantij produktivnosti a ce oznachaye sho ci algoritmi mozhut povertati absolyutno nepravilni ocinki bez poperedzhennya Tomu ci algoritmi ne ye najdinimi dlya kritichno vazhlivih zastosuvan takih yak samokerovane vodinnya Zovsim neshodavno Yang ta spivavtori rozrobili pershij algoritm stijkogo uzgodzhennya z garantiyeyu nadijnosti pid nazvoyu Ocinka za metodom usichenih najmenshih kvadrativ i napivviznachenoyi relaksaciyi angl Truncated least squares Estimation And Semidefinite Relaxation Dlya ugodzhennya mnozhini tochok TEASER ne tilki vivodit ocinku peretvorennya ale j kilkisno viznachaye optimalnist danoyi ocinki TEASER vikoristovuye nastupnij ocinyuvach za metodom usichenih najmenshih kvadrativ l R t arg min l gt 0 R SO 3 t R 3 i 1 N min 1 s i 2 s i l R m i t 2 2 c 2 displaystyle l star R star t star arg min l gt 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 div 7 yakij otrimuyetsya shlyahom viboru usichenih najmenshih kvandrativ UNK nadijnoyi funkciyi vtrat r x min x 2 c 2 displaystyle rho x min x 2 bar c 2 de c 2 displaystyle bar c 2 ye zazdalegid viznachenoyu konstantoyu yaka zumovlyuye maksimalno dozvoleni zalishki yaki vvazhayutsya vnutrishnimi Cilova funkciya UNK maye taku vlastivist yaka viznachaye sho dlya vnutrishnih vidpovidnostej s i l R m i t 2 2 s i 2 lt c 2 displaystyle Vert s i lRm i t Vert 2 2 sigma i 2 lt bar c 2 zastosovuyetsya zvichajnij metod shtrafiv najmenshih kvadrativ u toj chas yak dlya vidpovidnostej vikidiv s i l R m i t 2 2 s i 2 gt c 2 displaystyle Vert s i lRm i t Vert 2 2 sigma i 2 gt bar c 2 cej shtraf ne zastosovuyetsya a vikidi vidhilyayutsya Yaksho optimizaciya UNK div 7 rozv yazuyetsya z globalnoyu optimalnistyu to vona ekvivalentna metodu Horna lishe dlya vnutrishnih vidpovidnostej Odnak rozv yazannya div 7 ye dosit skladnim cherez jogo kombinatornij harakter Ocinka za metodom usichenih najmenshih kvadrativ i napivviznachenoyi relaksaciyi rozv yazuye div 7 nastupnim chinom i Vona stvoryuye invariantni vimiryuvannya takim chinom sho ocinka masshtabu obertannya ta peretvorennya mozhut buti vidokremleni ta rozv yazana okremo Cya strategiya zasnovana na originalnij shemi Gornera ii Ta zh ocinka usichenih najmenshih kvadrativ dali UNK zastosovuyetsya dlya kozhnoyi z troh pidzadach de zadacha UNK masshtabu mozhe buti rozv yazana za dopomogoyu algoritmu sho nazivayetsya adaptivnim golosuvannyam Zadacha obertannya UNK mozhna poslabiti do napivviznachenoyi programi de relaksaciya ye tochnoyu na praktici navit iz velikoyu kilkistyu vikidiv Zadachu zsuvu UNK mozhna virishiti vikoristovuyuchi pokomponentne adaptivne golosuvannya Shvidke vprovadzhennya sho vikoristovuye gradujovanu neopuklist maye nastupnij kod z vidkritim dostupom tut Na praktici ocinka za metodom usichenih kvadrativ i napivviznachenoh relaksaciyi mozhe vitrimati bilshe nizh 99 displaystyle 99 vikidiv vidpovidnostej i vikonuvatis za milisekundi Krim rozrobki ocinki za metodom usichenih kvadrativ i napivviznachenoyi relaksaciyi Yang ta spivavtori takozh doveli sho za deyakih slabkih umov na zadanij mnozhini tochok ocinka peretvorennya usichenih kvadrativ i napivviznachenoyi relaksaciyi maye pevni pohibki v porivnyanni iz spravzhnim peretvorennyam Div takozhZistavlyannya tochkovih oznak Triangulyaciya mnozhini tochokPrimitkiChui 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 angl 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 angl Allan Max Kapoor Ankur Mewes Philip Mountney Peter 1 sichnya 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 angl 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 angl 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 s 27 36 angl 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 angl 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 angl 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 angl Horn Berthold K P 1 kvitnya 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 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 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 978 1 5386 0457 1 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a hdl access vimagaye hdl dovidka Parra Bustos Alvaro 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 Chin Tat Jun Suter David 27 lyutogo 2017 The Maximum Consensus Problem Recent Algorithmic Advances Synthesis Lectures on Computer Vision amer 7 2 1 194 doi 10 2200 s00757ed1v01y201702cov011 ISSN 2153 1056 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 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 Bazin Jean Charles Seo Yongduek Pollefeys Marc 2013 Lee Kyoung Mu Matsushita Yasuyuki Rehg James M Hu Zhanyi red Globally Optimal Consensus Set Maximization through Rotation Search Computer Vision ACCV 2012 Lecture Notes in Computer Science angl Berlin Heidelberg Springer 7725 539 551 doi 10 1007 978 3 642 37444 9 42 ISBN 978 3 642 37444 9 Hartley Richard I Kahl Fredrik 1 kvitnya 2009 Global Optimization through Rotation Space Search International Journal of Computer Vision angl 82 1 64 79 doi 10 1007 s11263 008 0186 9 ISSN 1573 1405 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a hdl access vimagaye hdl dovidka 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 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 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 978 0 9923747 5 4 Huber Peter J Ronchetti Elvezio M 29 sichnya 2009 Robust Statistics Wiley Series in Probability and Statistics angl Hoboken NJ USA John Wiley amp Sons Inc doi 10 1002 9780470434697 ISBN 978 0 470 43469 7 Zhou Qian Yi Park Jaesik Koltun Vladlen 2016 Leibe Bastian Matas Jiri Sebe Nicu Welling Max red Fast Global Registration Computer Vision ECCV 2016 Lecture Notes in Computer Science angl Cham Springer International Publishing 9906 766 782 doi 10 1007 978 3 319 46475 6 47 ISBN 978 3 319 46475 6 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 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 978 1 4799 1986 4 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 Black Michael J Rangarajan Anand 1 lipnya 1996 On the unification of line processes outlier rejection and robust statistics with applications in early vision International Journal of Computer Vision angl 19 1 57 91 doi 10 1007 BF00131148 ISSN 1573 1405 Blake Andrew Zisserman Andrew 1987 Visual reconstruction The MIT Press ISBN 9780262524063 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 Black Michael J Rangarajan Anand 1 lipnya 1996 On the unification of line processes outlier rejection and robust statistics with applications in early vision International Journal of Computer Vision angl 19 1 57 91 doi 10 1007 BF00131148 ISSN 1573 1405 Yang Heng Shi Jingnan Carlone Luca 21 sichnya 2020 TEASER Fast and Certifiable Point Cloud Registration arXiv 2001 07715 cs RO angl PosilannyaReference 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