Ця стаття не містить . (квітень 2021) |
Восьмиточковий алгоритм — це алгоритм, який використовується в комп'ютерному баченні для оцінки істотної матриці або фундаментальної матриці, що відповідає парі камер, за допомогою множини відповідних точок двох зображень. [en] запропонував цей алгоритм у випадку істотної матриці у 1981 році. Теоретично цей алгоритм може бути використано і для визначення фундаментальної матриці, але на практиці нормалізований восьмиточковий алгоритм, описаний Річардом Хартлі 1997 року, більше підходить для цього випадку.
Назва алгоритму походить від того факту, що він оцінює істотну матрицю або фундаментальну матрицю по множині з восьми (або більше) відповідних точок зображення. Однак варіації алгоритму можуть бути використані у випадку менш ніж на восьми точок.
Умова копланарності
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOW1MMll5TDBWd2FYQnZiR0Z5WDBkbGIyMWxkSEo1TVM1emRtY3ZNekF3Y0hndFJYQnBjRzlzWVhKZlIyVnZiV1YwY25reExuTjJaeTV3Ym1jPS5wbmc=.png)
Можна виразити епіполярну геометрію двох камер та точки простору за допомогою алгебраїчного рівняння. Зверніть увагу, незалежно від того де знаходиться точка у просторі, вектори
,
і
належать одній площині. Позначимо як
координати точки
у системі координат лівого ока та як
координати точки
у системі координат правого ока; позначимо як
обертання та переміщення при переході між системами координат, тобто
- це співвідношення між координатами
у двох системах координат. Наступне рівняння завжди виконується, оскільки вектор, отриманий як
є ортогональним до обох векторів
і
:
Оскільки матриця обертання є ортогональною, тобто , ми отримуємо
.
Замінивши на
, ми отримуємо
Зверніть увагу на те, що векторний добуток може розглядатися як множення вектора на матрицю; Символом
було позначено цю матрицю. Добуток
часто називають істотною матрицею і позначають
.
Вектори паралельні векторам
і тому обмеження копланарності виконується, якщо ми підставляємо ці вектори. Якщо ми позначимо як
координати проєкцій
на площини лівого та правого зображення, тоді умова копланарності може бути записана як
Базовий алгоритм
Далі описано базовий восьмиточковий алгоритм для оцінки істотної матриці . Він складається з трьох кроків. Спочатку формулюється однорідне лінійне рівняння, де розв'язком є матриця
, а потім розв’язується це рівняння, враховуючи, що воно може не мати точного розвʼязку. Нарешті, накладаються внутрішні обмеження результуючої матриці. Перший крок описаний у роботі Лонгет-Гіггінса, другий і третій кроки є стандартними підходами в теорії оцінки.
Умова компланарності накладена суттєвою матрицею :
для відповідних точок зображення, представлених у нормалізованих координатах зображення . Задача, яку вирішує алгоритм, полягає у визначенні
для набору відповідних точок зображення. На практиці на координати зображення точок зображення впливає шум, і рішення також може бути надмірно визначеним, що означає, що не вдасться знайти
яка задовольняє вищезазначеним умовам точно для всіх точок. Це питання розглядається на другому етапі алгоритму.
Крок 1: Формулювання однорідного лінійного рівняння
Запишемо
і
і
тоді умову компланарності можна переписати як
або
де
і
це, представляє істотну матрицю у вигляді 9-мірного вектора, і цей вектор повинен бути ортогональним вектору
.
Кожна пара відповідних точок зображення створює вектор . Дано набір 3D-точок
що відповідає набору векторів
, всі вони повинні задовольнити
для вектора . Якщо надано достатньо (принаймні вісім) лінійно незалежних векторів
вектор
можна визначити вирішивши систему лінійних рівнянь. Запишемо усі вектори
як стовпці матриці
і тоді:
Це означає що є рішенням системи лінійних однорідних рівнянь.
Крок 2: Розв’язок рівняння
Стандартний підхід до вирішення цього рівняння передбачає, що є лівим сингулярним вектором
якому відповідає нульове сингулярне значення. За умови, що принаймні вісім лінійно незалежних векторів
використовуються для побудови
випливає, що цей особливий вектор є унікальним і, отже,
і
можна визначити.
У випадку, коли для побудови використовується більше восьми відповідних точок не виключено, що вона не має жодного особливого значення, рівного нулю. Цей випадок трапляється на практиці, коли на координати зображення впливають різні типи шумів. Поширеним підходом до вирішення цієї задачі є використання методу найменших квадратів; знаходиться
що мінімізує
коли . Роз'язок полягає у виборі
як лівого сингулярного вектора, що відповідає найменшому особливому значенню
. Переписавши цей вектор
знову як матрицю
отримаємо результат цього кроку, що далі позначено як
Крок 3: Накладення внутрішніх обмежень
Іншим наслідком роботи з шумними координатами зображень є те, що отримана матриця може не задовольняти внутрішнім обмеженням істотної матриці, тобто два її особливих значення є рівними і ненульовими, а інше дорівнює нулю. Залежно від імплементації, менші або більші відхилення від внутрішніх обмежень можуть бути, а можуть і не бути проблемою. Якщо критично важливо, щоб знайдена матриця задовольняла внутрішнім обмеженням, це може бути досягнуто шляхом пошуку матриці рангу 2, яка мінімізує
де є матрицею отриманою на кроці 2 та використовується норма матриці Фробеніуса . Рохзвʼязок задається обчисленням сингулярного розкладу значення
:
де є ортогональними матрицями та
є діагональною матрицею, яка містить особливі значення
. В ідеальному випадку один з діагональних елементів
має бути нульовим або принаймні малим порівняно з двома іншими, які повинні бути однаковими. У будь-якому випадку вважаємо
де - найбільше та друге за величиною сингулярні значення
відповідно. Нарешті,
Матриця є результуючою оцінкою істотної матриці, отриманою за допомогою алгорита.
Реалізації
Восьмиточковий алгоритм реалізовано в бібліотеці OpenCV, де йому відповідає функція cv::findFundamentalMat
[ 4 березня 2021 у Wayback Machine.], яка викликається із параметром cv::FM_8POINT
.
Див. також
Посилання
- Richard I. Hartley (June 1997). In Defense of the Eight-Point Algorithm. IEEE Transactions on Pattern Recognition and Machine Intelligence. 19 (6): 580—593. doi:10.1109/34.601246.
- Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. ISBN .
- H. Christopher Longuet-Higgins (September 1981). A computer algorithm for reconstructing a scene from two projections. Nature. 293 (5828): 133—135. doi:10.1038/293133a0.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno kviten 2021 Vosmitochkovij algoritm ce algoritm yakij vikoristovuyetsya v komp yuternomu bachenni dlya ocinki istotnoyi matrici abo fundamentalnoyi matrici sho vidpovidaye pari kamer za dopomogoyu mnozhini vidpovidnih tochok dvoh zobrazhen en zaproponuvav cej algoritm u vipadku istotnoyi matrici u 1981 roci Teoretichno cej algoritm mozhe buti vikoristano i dlya viznachennya fundamentalnoyi matrici ale na praktici normalizovanij vosmitochkovij algoritm opisanij Richardom Hartli 1997 roku bilshe pidhodit dlya cogo vipadku Nazva algoritmu pohodit vid togo faktu sho vin ocinyuye istotnu matricyu abo fundamentalnu matricyu po mnozhini z vosmi abo bilshe vidpovidnih tochok zobrazhennya Odnak variaciyi algoritmu mozhut buti vikoristani u vipadku mensh nizh na vosmi tochok Umova koplanarnostiPriklad epipolyarnoyi geometriyi Dvi kameri z vidpovidnimi centrami proyekcijnih tochok O L i O R sposterigayut tochku P Proyekciya P na kozhnu z ploshin zobrazhennya poznachayetsya p L i p R Tochki E L i E R ye epipolyami Mozhna viraziti epipolyarnu geometriyu dvoh kamer ta tochki prostoru za dopomogoyu algebrayichnogo rivnyannya Zvernit uvagu nezalezhno vid togo de znahoditsya tochka P displaystyle P u prostori vektori OLP displaystyle overline O L P ORP displaystyle overline O R P i OROL displaystyle overline O R O L nalezhat odnij ploshini Poznachimo yak XL displaystyle X L koordinati tochki P displaystyle P u sistemi koordinat livogo oka ta yak XR displaystyle X R koordinati tochki P displaystyle P u sistemi koordinat pravogo oka poznachimo yak R T displaystyle R T obertannya ta peremishennya pri perehodi mizh sistemami koordinat tobto XR R XL T displaystyle X R R X L T ce spivvidnoshennya mizh koordinatami P displaystyle P u dvoh sistemah koordinat Nastupne rivnyannya zavzhdi vikonuyetsya oskilki vektor otrimanij yak T XL displaystyle T wedge X L ye ortogonalnim do oboh vektoriv T displaystyle T i XL displaystyle X L XLTT XL TTT XL XL T TT XL 0 displaystyle X L T T wedge X L T T T wedge X L X L T T T wedge X L 0 Oskilki matricya obertannya ye ortogonalnoyu tobto I RTR displaystyle I R T R mi otrimuyemo XL T TRTRT XL 0 displaystyle X L T T R T RT wedge X L 0 Zaminivshi XL T TRT displaystyle X L T T R T na XRT displaystyle X R T mi otrimuyemo XRTRT XL XRTRSXL XRTEXL 0 displaystyle X R T RT wedge X L X R T RSX L X R T EX L 0 Zvernit uvagu na te sho vektornij dobutok T displaystyle T wedge mozhe rozglyadatisya yak mnozhennya vektora na matricyu Simvolom S displaystyle S bulo poznacheno cyu matricyu Dobutok RT RS displaystyle RT wedge RS chasto nazivayut istotnoyu matriceyu i poznachayut E displaystyle E Vektori OLpL ORpR displaystyle overline O L p L overline O R p R paralelni vektoram OLP ORP displaystyle overline O L P overline O R P i tomu obmezhennya koplanarnosti vikonuyetsya yaksho mi pidstavlyayemo ci vektori Yaksho mi poznachimo yak y y displaystyle y y koordinati proyekcij P displaystyle P na ploshini livogo ta pravogo zobrazhennya todi umova koplanarnosti mozhe buti zapisana yak y TEy 0 displaystyle y T mathbf E y 0 Bazovij algoritmDali opisano bazovij vosmitochkovij algoritm dlya ocinki istotnoyi matrici E displaystyle mathbf E Vin skladayetsya z troh krokiv Spochatku formulyuyetsya odnoridne linijne rivnyannya de rozv yazkom ye matricya E displaystyle mathbf E a potim rozv yazuyetsya ce rivnyannya vrahovuyuchi sho vono mozhe ne mati tochnogo rozvʼyazku Nareshti nakladayutsya vnutrishni obmezhennya rezultuyuchoyi matrici Pershij krok opisanij u roboti Longet Gigginsa drugij i tretij kroki ye standartnimi pidhodami v teoriyi ocinki Umova komplanarnosti nakladena suttyevoyu matriceyu E displaystyle mathbf E y TEy 0 displaystyle mathbf y T mathbf E mathbf y 0 dlya vidpovidnih tochok zobrazhennya predstavlenih u normalizovanih koordinatah zobrazhennya y y displaystyle mathbf y mathbf y Zadacha yaku virishuye algoritm polyagaye u viznachenni E displaystyle mathbf E dlya naboru vidpovidnih tochok zobrazhennya Na praktici na koordinati zobrazhennya tochok zobrazhennya vplivaye shum i rishennya takozh mozhe buti nadmirno viznachenim sho oznachaye sho ne vdastsya znajti E displaystyle mathbf E yaka zadovolnyaye vishezaznachenim umovam tochno dlya vsih tochok Ce pitannya rozglyadayetsya na drugomu etapi algoritmu Krok 1 Formulyuvannya odnoridnogo linijnogo rivnyannya Zapishemo y y1y21 displaystyle mathbf y begin pmatrix y 1 y 2 1 end pmatrix i y y1 y2 1 displaystyle mathbf y begin pmatrix y 1 y 2 1 end pmatrix i E e11e12e13e21e22e23e31e32e33 displaystyle mathbf E begin pmatrix e 11 amp e 12 amp e 13 e 21 amp e 22 amp e 23 e 31 amp e 32 amp e 33 end pmatrix todi umovu komplanarnosti mozhna perepisati yak y1 y1e11 y1 y2e12 y1 e13 y2 y1e21 y2 y2e22 y2 e23 y1e31 y2e32 e33 0 displaystyle y 1 y 1 e 11 y 1 y 2 e 12 y 1 e 13 y 2 y 1 e 21 y 2 y 2 e 22 y 2 e 23 y 1 e 31 y 2 e 32 e 33 0 abo e y 0 displaystyle mathbf e cdot tilde mathbf y 0 de y y1 y1y1 y2y1 y2 y1y2 y2y2 y1y21 displaystyle tilde mathbf y begin pmatrix y 1 y 1 y 1 y 2 y 1 y 2 y 1 y 2 y 2 y 2 y 1 y 2 1 end pmatrix i e e11e12e13e21e22e23e31e32e33 displaystyle mathbf e begin pmatrix e 11 e 12 e 13 e 21 e 22 e 23 e 31 e 32 e 33 end pmatrix ce e displaystyle mathbf e predstavlyaye istotnu matricyu u viglyadi 9 mirnogo vektora i cej vektor povinen buti ortogonalnim vektoru y displaystyle tilde mathbf y Kozhna para vidpovidnih tochok zobrazhennya stvoryuye vektor y displaystyle tilde mathbf y Dano nabir 3D tochok Pk displaystyle mathbf P k sho vidpovidaye naboru vektoriv y k displaystyle tilde mathbf y k vsi voni povinni zadovolniti e y k 0 displaystyle mathbf e cdot tilde mathbf y k 0 dlya vektora e displaystyle mathbf e Yaksho nadano dostatno prinajmni visim linijno nezalezhnih vektoriv y k displaystyle tilde mathbf y k vektor e displaystyle mathbf e mozhna viznachiti virishivshi sistemu linijnih rivnyan Zapishemo usi vektori y k displaystyle tilde mathbf y k yak stovpci matrici Y displaystyle mathbf Y i todi eTY 0 displaystyle mathbf e T mathbf Y mathbf 0 Ce oznachaye sho e displaystyle mathbf e ye rishennyam sistemi linijnih odnoridnih rivnyan Krok 2 Rozv yazok rivnyannya Standartnij pidhid do virishennya cogo rivnyannya peredbachaye sho e displaystyle mathbf e ye livim singulyarnim vektorom Y displaystyle mathbf Y yakomu vidpovidaye nulove singulyarne znachennya Za umovi sho prinajmni visim linijno nezalezhnih vektoriv y k displaystyle tilde mathbf y k vikoristovuyutsya dlya pobudovi Y displaystyle mathbf Y viplivaye sho cej osoblivij vektor ye unikalnim i otzhe e displaystyle mathbf e i E displaystyle mathbf E mozhna viznachiti U vipadku koli dlya pobudovi Y displaystyle mathbf Y vikoristovuyetsya bilshe vosmi vidpovidnih tochok ne viklyucheno sho vona ne maye zhodnogo osoblivogo znachennya rivnogo nulyu Cej vipadok traplyayetsya na praktici koli na koordinati zobrazhennya vplivayut rizni tipi shumiv Poshirenim pidhodom do virishennya ciyeyi zadachi ye vikoristannya metodu najmenshih kvadrativ znahoditsya e displaystyle mathbf e sho minimizuye eTY displaystyle mathbf e T mathbf Y koli e 1 displaystyle mathbf e 1 Roz yazok polyagaye u vibori e displaystyle mathbf e yak livogo singulyarnogo vektora sho vidpovidaye najmenshomu osoblivomu znachennyu Y displaystyle mathbf Y Perepisavshi cej vektor e displaystyle mathbf e znovu yak matricyu 3 3 displaystyle 3 times 3 otrimayemo rezultat cogo kroku sho dali poznacheno yak Eest displaystyle mathbf E rm est Krok 3 Nakladennya vnutrishnih obmezhen Inshim naslidkom roboti z shumnimi koordinatami zobrazhen ye te sho otrimana matricya mozhe ne zadovolnyati vnutrishnim obmezhennyam istotnoyi matrici tobto dva yiyi osoblivih znachennya ye rivnimi i nenulovimi a inshe dorivnyuye nulyu Zalezhno vid implementaciyi menshi abo bilshi vidhilennya vid vnutrishnih obmezhen mozhut buti a mozhut i ne buti problemoyu Yaksho kritichno vazhlivo shob znajdena matricya zadovolnyala vnutrishnim obmezhennyam ce mozhe buti dosyagnuto shlyahom poshuku matrici E displaystyle mathbf E rangu 2 yaka minimizuye E Eest displaystyle mathbf E mathbf E rm est de Eest displaystyle mathbf E rm est ye matriceyu otrimanoyu na kroci 2 ta vikoristovuyetsya norma matrici Frobeniusa Rohzvʼyazok zadayetsya obchislennyam singulyarnogo rozkladu znachennya Eest displaystyle mathbf E rm est Eest USVT displaystyle mathbf E rm est mathbf U mathbf S mathbf V T de U V displaystyle mathbf U mathbf V ye ortogonalnimi matricyami ta S displaystyle mathbf S ye diagonalnoyu matriceyu yaka mistit osoblivi znachennya Eest displaystyle mathbf E rm est V idealnomu vipadku odin z diagonalnih elementiv S displaystyle mathbf S maye buti nulovim abo prinajmni malim porivnyano z dvoma inshimi yaki povinni buti odnakovimi U bud yakomu vipadku vvazhayemo S s1000s20000 displaystyle mathbf S begin pmatrix s 1 amp 0 amp 0 0 amp s 2 amp 0 0 amp 0 amp 0 end pmatrix de s1 s2 displaystyle s 1 s 2 najbilshe ta druge za velichinoyu singulyarni znachennya S displaystyle mathbf S vidpovidno Nareshti E displaystyle mathbf E E US VT displaystyle mathbf E mathbf U mathbf S mathbf V T Matricya E displaystyle mathbf E ye rezultuyuchoyu ocinkoyu istotnoyi matrici otrimanoyu za dopomogoyu algorita RealizaciyiVosmitochkovij algoritm realizovano v biblioteci OpenCV de jomu vidpovidaye funkciya cv findFundamentalMat 4 bereznya 2021 u Wayback Machine yaka viklikayetsya iz parametrom cv FM 8POINT Div takozhFundamentalna matricya Epipolyarna geometriya Istotna matricya Trifokalnij tenzorPosilannyaRichard I Hartley June 1997 In Defense of the Eight Point Algorithm IEEE Transactions on Pattern Recognition and Machine Intelligence 19 6 580 593 doi 10 1109 34 601246 Richard Hartley and Andrew Zisserman 2003 Multiple View Geometry in computer vision Cambridge University Press ISBN 978 0 521 54051 3 H Christopher Longuet Higgins September 1981 A computer algorithm for reconstructing a scene from two projections Nature 293 5828 133 135 doi 10 1038 293133a0