Структура із руху (англ. Structure from motion, SfM) — це техніка діапазонної візуалізації; вона являє собою процес побудови тривимірної структури із послідовності двовимірних зображень, що можуть сполучатися із місцевими [en]. Ця техніка вивчається в галузі комп'ютерного бачення і при вивчені зору. В біологічному зорі, під структурою із руху мають на увазі феномен, за допомогою якого люди (та інші зрячі істоти) можуть відновлювати тривимірну структуру із двовимірних проєкцій (на сітківку) слідів руху від рухомих об'єктів або сцени.
Отримання тривимірної інформації із двовимірних зображень
Людина сприймає багато інформації про просторову структуру об'єктів довкілля при переміщенні в ньому. Коли спостерігач рухається і об'єкти зміщуються довкола нього, інформація отримується із образів, що сприймаються протягом часу.
Відбудова структури рухомих об'єктів є задачею, схожою на відбудову структури зі стереоскопічних зображень. В обох випадках необхідно знайти відповідність між зображеннями та реконструювати тривимірний об'єкт.
Для знаходження відповідності між зображеннями на них відстежують такі ознаки як кутові точки (грані із градієнтом в різних напрямках). Одним із найширше вживаних алгоритмів пошуку ознак є алгоритм SIFT (англ. Scale-invariant feature transform). Як ознаки він використовує максимуми піраміди різниць гаусіан. Першим кроком алгоритму SIFT є віднаходження домінантного напряму градієнта. Для того, щоб зробити це інваріантним до обертання, повертають дескриптор таким чином, щоби він збігся з даною орієнтацією. Іншим поширеним алгоритмом виділення ознак є SURF (англ. Speeded Up Robust Features). В алгоритмі SURF різниці гаусіан замінюють операцією виділення областей на базі матриці Гессе. Також замість підрахунку гістограм градієнтів SURF проводить розрахунки на основі сум градієнтних компонент і сум їхніх абсолютних значень. Виділені на всіх зображеннях ознаки потім зіставляються. Одним із алгоритмів такого зіставлення, що відстежує ознаки від одного зображення до іншого, є відстежувач Лукаса-Канаде.
Іноді деякі із зіставлених ознак зіставляються не вірно. Тому знайдені результати має бути також відфільтровано. Зазвичай для усунення викидів відповідності використовується алгоритм RANSAC (англ. Random Sample Consensus). У праці Фішера та Боллза RANSAC використовується для розв'язання задачі визначення положення (англ. Location Determination Problem, LDP), у якій метою є визначення точок у просторі, що проектуються на зображення у множину орієнтирів з відомими положеннями.
Траєкторії виділених елементів зображення, що переміщуються з плином часу, використовуються для реконструкції їхніх положень у тривимірному просторі та руху камери. Альтернативою є так звані прямі підходи, де геометрична інформація (тривимірна структура та рух камери) визначаються із зображень напряму, без проміжного абстрагування до ознак або кутів.
Існує декілька підходів до отримання структури з руху. В інкрементній структурі з руху положення камери розв'язуються та додаються до колекції одне по одному. В глобальній структурі з руху всі положення камери розв'язуються одночасно. Дещо проміжним підходом є структура з руху [en], в якій обчислюються деякі часткові реконструкції, що потім інтегруються в глобальний розв'язок.
Див. також
- Одночасне визначення місцезнаходження та картографування (англ. SLAM)
- [en]
- [en]
- [en]
- Епіполярна геометрія
- [en]
Література
- Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in Computer Vision. Cambridge University Press. ISBN . (англ.)
- Olivier Faugeras and Quang-Tuan Luong and Theodore Papadopoulo (2001). The Geometry of Multiple Images. MIT Press. ISBN . (англ.)
- Yi Ma, S. Shankar Sastry, Jana Kosecka, Stefano Soatto, Jana Kosecka (November 2003). An Invitation to 3-D Vision: From Images to Geometric Models. Interdisciplinary Applied Mathematics Series, #26. Springer-Verlag New York, LLC. ISBN . (англ.)
Примітки
- Linda G. Shapiro, George C. Stockman (2001). Computer Vision. Prentice Hall. ISBN . (англ.)
- D. G. Lowe (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision. (англ.)
- H. Bay, T. Tuytelaars, and L. Van Gool (2006). Surf: Speeded up robust features. 9th European Conference on Computer Vision. (англ.)
- K. Häming and G. Peters (2010). . Kybernetika. Архів оригіналу за 18 лютого 2015. Процитовано 22 лютого 2015. (англ.)
- B. D. Lucas and T. Kanade. An iterative image registration technique with an application to stereo vision. IJCAI81. (англ.)
- M. A. Fischler and R. C. Bolles (1981). Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM. (англ.)
- F. Dellaert, S. Seitz, C. Thorpe, and S. Thrun (2000). (PDF). IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Архів оригіналу (PDF) за 24 вересня 2015. Процитовано 22 лютого 2015. (англ.)
- Engel, Jakob; Schöps, Thomas; Cremers, Daniel (2014). (PDF). Архів оригіналу (PDF) за 22 жовтня 2014. Процитовано 22 лютого 2015.
{{}}
: Проігноровано|contribution=
() (англ.)
Посилання
Програмні інструментарії структури з руху
Відкриті рішення
C++
- Bundler [ 27 січня 2013 у Wayback Machine.] — структура з руху для невпорядкованих колекцій фотографій, автор — Noah Snavely
- openMVG [ 22 лютого 2015 у Wayback Machine.] бібліотека Open Multiple View Geometry + демонстратори структури з руху
- Libmv [ 18 лютого 2018 у Wayback Machine.] — бібліотека структури з руху
- — швидка та масштабована бібліотека структури з руху, випущена на базі ліцензії BSD
- MicMac [ 4 березня 2015 у Wayback Machine.] — вільний джерельний код структури з руху, випущений [en]
- LSD-SLAM — великомасштабне пряме монокулярне одночасне визначення місцезнаходження та картографування в реальному часі, автор — Jakob Engel
- , автор — Simon Fuhrmann, TU Darmstadt.
- ceres-solver для загальних нелінійних найменших квадратів [ 14 квітня 2015 у Wayback Machine.]. Має функції для зрівнювання зв'язок. Раніше використовувався всередині компанії Google для Google Maps. Випущено в світ у 2012 році.
- SBA [ 18 березня 2013 у Wayback Machine.] для загального зрівнювання зв'язок, автор — Manolis Lourakis.
Matlab
- , автор — Vincent Rabaud
- Matlab Functions for Multiple View Geometry [ 15 березня 2015 у Wayback Machine.], автор — Andrew Zissermann
- , автор — Phil Torr
- Matlab Code for Non-Rigid Structure from Motion [ 5 грудня 2014 у Wayback Machine.], автор — Lorenzo Torresani
Python
- — відкритий ГІК структури із руху (запускач Easy SfM та щільної множини точок), автори — Pierre Moulon та Arc-Team
Інше програмне забезпечення
- Smart3DCapture [ 14 березня 2015 у Wayback Machine.], повне рішення для фотограмметрії від Acute3D.
- 3DF Samantha [ 2 лютого 2015 у Wayback Machine.] — конвеєрна командно-рядкова структура із руху для Windows від 3Dflow SRL. Безкоштовна для некомерційного призначення.
- Automatic Camera Tracking System (ACTS) [ 6 лютого 2012 у Wayback Machine.] — система структури із руху для Microsoft Windows, автор — State Key Lab з CAD&CG, Zhejiang University.
- VisualSFM: A Visual Structure from Motion System [ 10 жовтня 2016 у Wayback Machine.], автор — Changchang Wu
- SFMToolkit [ 23 грудня 2014 у Wayback Machine.], повне рішення для фотограмметрії на базі відкритого програмного забезпечення
- , програмне забезпечення для сканувальних електронних мікроскопів. 3D отримується нахилом зразка + фотограмметрією.
- Voodoo Camera Tracker [ 30 квітня 2016 у Wayback Machine.], некомерційний інструмент для поєднання віртуальних та реальних сцен.
Первісний сайт, заархівований: - , структура з руху для доповненої реальності на мобільних пристроях.
- TacitView [ 2 квітня 2015 у Wayback Machine.] від [en]
- Catena Python Abstract Workflow Framework з компонентами структури з руху.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Struktura iz ruhu angl Structure from motion SfM ce tehnika diapazonnoyi vizualizaciyi vona yavlyaye soboyu proces pobudovi trivimirnoyi strukturi iz poslidovnosti dvovimirnih zobrazhen sho mozhut spoluchatisya iz miscevimi en Cya tehnika vivchayetsya v galuzi komp yuternogo bachennya i pri vivcheni zoru V biologichnomu zori pid strukturoyu iz ruhu mayut na uvazi fenomen za dopomogoyu yakogo lyudi ta inshi zryachi istoti mozhut vidnovlyuvati trivimirnu strukturu iz dvovimirnih proyekcij na sitkivku slidiv ruhu vid ruhomih ob yektiv abo sceni Cifrova model poverhni transportnoyi rozv yazki avtomagistrali pri budivnictviOtrimannya trivimirnoyi informaciyi iz dvovimirnih zobrazhenTrivimirna cifrova model miscevosti aerodromu Bezmigova Gorishnya vidobuta z danih zibranih protyagom 30 hvilinnogo polotu BPLA en Realne foto Struktura z ruhu z teksturnim kolorom Struktura z ruhu z prostim zatinennyam Zrobleno za dopomogoyu Python Photogrammetry Toolbox GUI ta vizualizovano v Blender with Cycles Lyudina sprijmaye bagato informaciyi pro prostorovu strukturu ob yektiv dovkillya pri peremishenni v nomu Koli sposterigach ruhayetsya i ob yekti zmishuyutsya dovkola nogo informaciya otrimuyetsya iz obraziv sho sprijmayutsya protyagom chasu Vidbudova strukturi ruhomih ob yektiv ye zadacheyu shozhoyu na vidbudovu strukturi zi stereoskopichnih zobrazhen V oboh vipadkah neobhidno znajti vidpovidnist mizh zobrazhennyami ta rekonstruyuvati trivimirnij ob yekt Dlya znahodzhennya vidpovidnosti mizh zobrazhennyami na nih vidstezhuyut taki oznaki yak kutovi tochki grani iz gradiyentom v riznih napryamkah Odnim iz najshirshe vzhivanih algoritmiv poshuku oznak ye algoritm SIFT angl Scale invariant feature transform Yak oznaki vin vikoristovuye maksimumi piramidi riznic gausian Pershim krokom algoritmu SIFT ye vidnahodzhennya dominantnogo napryamu gradiyenta Dlya togo shob zrobiti ce invariantnim do obertannya povertayut deskriptor takim chinom shobi vin zbigsya z danoyu oriyentaciyeyu Inshim poshirenim algoritmom vidilennya oznak ye SURF angl Speeded Up Robust Features V algoritmi SURF riznici gausian zaminyuyut operaciyeyu vidilennya oblastej na bazi matrici Gesse Takozh zamist pidrahunku gistogram gradiyentiv SURF provodit rozrahunki na osnovi sum gradiyentnih komponent i sum yihnih absolyutnih znachen Vidileni na vsih zobrazhennyah oznaki potim zistavlyayutsya Odnim iz algoritmiv takogo zistavlennya sho vidstezhuye oznaki vid odnogo zobrazhennya do inshogo ye vidstezhuvach Lukasa Kanade Inodi deyaki iz zistavlenih oznak zistavlyayutsya ne virno Tomu znajdeni rezultati maye buti takozh vidfiltrovano Zazvichaj dlya usunennya vikidiv vidpovidnosti vikoristovuyetsya algoritm RANSAC angl Random Sample Consensus U praci Fishera ta Bollza RANSAC vikoristovuyetsya dlya rozv yazannya zadachi viznachennya polozhennya angl Location Determination Problem LDP u yakij metoyu ye viznachennya tochok u prostori sho proektuyutsya na zobrazhennya u mnozhinu oriyentiriv z vidomimi polozhennyami Trayektoriyi vidilenih elementiv zobrazhennya sho peremishuyutsya z plinom chasu vikoristovuyutsya dlya rekonstrukciyi yihnih polozhen u trivimirnomu prostori ta ruhu kameri Alternativoyu ye tak zvani pryami pidhodi de geometrichna informaciya trivimirna struktura ta ruh kameri viznachayutsya iz zobrazhen napryamu bez promizhnogo abstraguvannya do oznak abo kutiv Isnuye dekilka pidhodiv do otrimannya strukturi z ruhu V inkrementnij strukturi z ruhu polozhennya kameri rozv yazuyutsya ta dodayutsya do kolekciyi odne po odnomu V globalnij strukturi z ruhu vsi polozhennya kameri rozv yazuyutsya odnochasno Desho promizhnim pidhodom ye struktura z ruhu en v yakij obchislyuyutsya deyaki chastkovi rekonstrukciyi sho potim integruyutsya v globalnij rozv yazok Div takozhOdnochasne viznachennya misceznahodzhennya ta kartografuvannya angl SLAM en en en Epipolyarna geometriya en LiteraturaRichard Hartley and Andrew Zisserman 2003 Multiple View Geometry in Computer Vision Cambridge University Press ISBN 0 521 54051 8 angl Olivier Faugeras and Quang Tuan Luong and Theodore Papadopoulo 2001 The Geometry of Multiple Images MIT Press ISBN 0 262 06220 8 angl Yi Ma S Shankar Sastry Jana Kosecka Stefano Soatto Jana Kosecka November 2003 An Invitation to 3 D Vision From Images to Geometric Models Interdisciplinary Applied Mathematics Series 26 Springer Verlag New York LLC ISBN 0 387 00893 4 angl PrimitkiLinda G Shapiro George C Stockman 2001 Computer Vision Prentice Hall ISBN 0 13 030796 3 angl D G Lowe 2004 Distinctive image features from scale invariant keypoints International Journal of Computer Vision angl H Bay T Tuytelaars and L Van Gool 2006 Surf Speeded up robust features 9th European Conference on Computer Vision angl K Haming and G Peters 2010 Kybernetika Arhiv originalu za 18 lyutogo 2015 Procitovano 22 lyutogo 2015 angl B D Lucas and T Kanade An iterative image registration technique with an application to stereo vision IJCAI81 angl M A Fischler and R C Bolles 1981 Random sample consensus a paradigm for model fitting with applications to image analysis and automated cartography Commun ACM angl F Dellaert S Seitz C Thorpe and S Thrun 2000 PDF IEEE Computer Society Conference on Computer Vision and Pattern Recognition Arhiv originalu PDF za 24 veresnya 2015 Procitovano 22 lyutogo 2015 angl Engel Jakob Schops Thomas Cremers Daniel 2014 PDF Arhiv originalu PDF za 22 zhovtnya 2014 Procitovano 22 lyutogo 2015 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite journal title Shablon Cite journal cite journal a Proignorovano contribution dovidka angl PosilannyaProgramni instrumentariyi strukturi z ruhu Vidkriti rishennya C Bundler 27 sichnya 2013 u Wayback Machine struktura z ruhu dlya nevporyadkovanih kolekcij fotografij avtor Noah Snavely openMVG 22 lyutogo 2015 u Wayback Machine biblioteka Open Multiple View Geometry demonstratori strukturi z ruhu Libmv 18 lyutogo 2018 u Wayback Machine biblioteka strukturi z ruhu shvidka ta masshtabovana biblioteka strukturi z ruhu vipushena na bazi licenziyi BSD MicMac 4 bereznya 2015 u Wayback Machine vilnij dzherelnij kod strukturi z ruhu vipushenij en LSD SLAM velikomasshtabne pryame monokulyarne odnochasne viznachennya misceznahodzhennya ta kartografuvannya v realnomu chasi avtor Jakob Engel avtor Simon Fuhrmann TU Darmstadt ceres solver dlya zagalnih nelinijnih najmenshih kvadrativ 14 kvitnya 2015 u Wayback Machine Maye funkciyi dlya zrivnyuvannya zv yazok Ranishe vikoristovuvavsya vseredini kompaniyi Google dlya Google Maps Vipusheno v svit u 2012 roci SBA 18 bereznya 2013 u Wayback Machine dlya zagalnogo zrivnyuvannya zv yazok avtor Manolis Lourakis Matlab avtor Vincent Rabaud Matlab Functions for Multiple View Geometry 15 bereznya 2015 u Wayback Machine avtor Andrew Zissermann avtor Phil Torr Matlab Code for Non Rigid Structure from Motion 5 grudnya 2014 u Wayback Machine avtor Lorenzo Torresani Python vidkritij GIK strukturi iz ruhu zapuskach Easy SfM ta shilnoyi mnozhini tochok avtori Pierre Moulon ta Arc Team Inshe programne zabezpechennya Smart3DCapture 14 bereznya 2015 u Wayback Machine povne rishennya dlya fotogrammetriyi vid Acute3D 3DF Samantha 2 lyutogo 2015 u Wayback Machine konveyerna komandno ryadkova struktura iz ruhu dlya Windows vid 3Dflow SRL Bezkoshtovna dlya nekomercijnogo priznachennya Automatic Camera Tracking System ACTS 6 lyutogo 2012 u Wayback Machine sistema strukturi iz ruhu dlya Microsoft Windows avtor State Key Lab z CAD amp CG Zhejiang University VisualSFM A Visual Structure from Motion System 10 zhovtnya 2016 u Wayback Machine avtor Changchang Wu SFMToolkit 23 grudnya 2014 u Wayback Machine povne rishennya dlya fotogrammetriyi na bazi vidkritogo programnogo zabezpechennya programne zabezpechennya dlya skanuvalnih elektronnih mikroskopiv 3D otrimuyetsya nahilom zrazka fotogrammetriyeyu Voodoo Camera Tracker 30 kvitnya 2016 u Wayback Machine nekomercijnij instrument dlya poyednannya virtualnih ta realnih scen Pervisnij sajt zaarhivovanij struktura z ruhu dlya dopovnenoyi realnosti na mobilnih pristroyah TacitView 2 kvitnya 2015 u Wayback Machine vid en Catena Python Abstract Workflow Framework z komponentami strukturi z ruhu