Структура із руху

Структура із руху (англ. Structure from motion, SfM) — це техніка діапазонної візуалізації; вона являє собою процес побудови тривимірної структури із послідовності двовимірних зображень, що можуть сполучатися із місцевими сигналами руху^[en]. Ця техніка вивчається в галузі комп'ютерного бачення і при вивчені зору. В біологічному зорі, під структурою із руху мають на увазі феномен, за допомогою якого люди (та інші зрячі істоти) можуть відновлювати тривимірну структуру із двовимірних проєкцій (на сітківку) слідів руху від рухомих об'єктів або сцени.

Отримання тривимірної інформації із двовимірних зображень

Людина сприймає багато інформації про просторову структуру об'єктів довкілля при переміщенні в ньому. Коли спостерігач рухається і об'єкти зміщуються довкола нього, інформація отримується із образів, що сприймаються протягом часу.^[1]

Відбудова структури рухомих об'єктів є задачею, схожою на відбудову структури зі стереоскопічних зображень. В обох випадках необхідно знайти відповідність між зображеннями та реконструювати тривимірний об'єкт.

Для знаходження відповідності між зображеннями на них відстежують такі ознаки як кутові точки (грані із градієнтом в різних напрямках). Одним із найширше вживаних алгоритмів пошуку ознак є алгоритм SIFT (англ. Scale-invariant feature transform). Як ознаки він використовує максимуми піраміди різниць гаусіан. Першим кроком алгоритму SIFT є віднаходження домінантного напряму градієнта. Для того, щоб зробити це інваріантним до обертання, повертають дескриптор таким чином, щоби він збігся з даною орієнтацією.^[2] Іншим поширеним алгоритмом виділення ознак є SURF (англ. Speeded Up Robust Features).^[3] В алгоритмі SURF різниці гаусіан замінюють операцією виділення областей на базі матриці Гессе. Також замість підрахунку гістограм градієнтів SURF проводить розрахунки на основі сум градієнтних компонент і сум їхніх абсолютних значень.^[4] Виділені на всіх зображеннях ознаки потім зіставляються. Одним із алгоритмів такого зіставлення, що відстежує ознаки від одного зображення до іншого, є відстежувач Лукаса-Канаде.^[5]

Іноді деякі із зіставлених ознак зіставляються не вірно. Тому знайдені результати має бути також відфільтровано. Зазвичай для усунення викидів відповідності використовується алгоритм RANSAC (англ. Random Sample Consensus). У праці Фішера та Боллза RANSAC використовується для розв'язання задачі визначення положення (англ. Location Determination Problem, LDP), у якій метою є визначення точок у просторі, що проектуються на зображення у множину орієнтирів з відомими положеннями.^[6]

Траєкторії виділених елементів зображення, що переміщуються з плином часу, використовуються для реконструкції їхніх положень у тривимірному просторі та руху камери.^[7] Альтернативою є так звані прямі підходи, де геометрична інформація (тривимірна структура та рух камери) визначаються із зображень напряму, без проміжного абстрагування до ознак або кутів.^[8]

Існує декілька підходів до отримання структури з руху. В інкрементній структурі з руху положення камери розв'язуються та додаються до колекції одне по одному. В глобальній структурі з руху всі положення камери розв'язуються одночасно. Дещо проміжним підходом є структура з руху із зовнішньою пам'яттю^[en], в якій обчислюються деякі часткові реконструкції, що потім інтегруються в глобальний розв'язок.

Див. також

Література

Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in Computer Vision. Cambridge University Press. ISBN 0-521-54051-8. (англ.)
Olivier Faugeras and Quang-Tuan Luong and Theodore Papadopoulo (2001). The Geometry of Multiple Images. MIT Press. ISBN 0-262-06220-8. (англ.)
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. (англ.)

Примітки

↑ Linda G. Shapiro, George C. Stockman (2001). Computer Vision. Prentice Hall. ISBN 0-13-030796-3. (англ.)
↑ 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). The structure-from-motion reconstruction pipeline – a survey with focus on short image sequences. 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). Structure from Motion without Correspondence (PDF). IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Архів оригіналу (PDF) за 24 вересня 2015. Процитовано 22 лютого 2015. (англ.)
↑ Engel, Jakob; Schöps, Thomas; Cremers, Daniel (2014). European Converence on Computer Vision (ECCV) 2014 (PDF). Архів оригіналу (PDF) за 22 жовтня 2014. Процитовано 22 лютого 2015. {{cite journal}}: Проігноровано |contribution= (довідка) (англ.)

Посилання

Програмні інструментарії структури з руху

Відкриті рішення

C++

Bundler [Архівовано 27 січня 2013 у Wayback Machine.] — структура з руху для невпорядкованих колекцій фотографій, автор — Noah Snavely
openMVG [Архівовано 22 лютого 2015 у Wayback Machine.] бібліотека Open Multiple View Geometry + демонстратори структури з руху
Libmv [Архівовано 18 лютого 2018 у Wayback Machine.] — бібліотека структури з руху
Theia — швидка та масштабована бібліотека структури з руху, випущена на базі ліцензії BSD
MicMac [Архівовано 4 березня 2015 у Wayback Machine.] — вільний джерельний код структури з руху, випущений Національним географічним інститутом Франції^[en]
LSD-SLAM — великомасштабне пряме монокулярне одночасне визначення місцезнаходження та картографування в реальному часі, автор — Jakob Engel
MVE — The Multi-View Environment, автор — Simon Fuhrmann, TU Darmstadt.
ceres-solver для загальних нелінійних найменших квадратів [Архівовано 14 квітня 2015 у Wayback Machine.]. Має функції для зрівнювання зв'язок. Раніше використовувався всередині компанії Google для Google Maps. Випущено в світ у 2012 році.
SBA [Архівовано 18 березня 2013 у Wayback Machine.] для загального зрівнювання зв'язок, автор — Manolis Lourakis.

Matlab

Structure from Motion toolbox for Matlab, автор — Vincent Rabaud
Matlab Functions for Multiple View Geometry [Архівовано 15 березня 2015 у Wayback Machine.], автор — Andrew Zissermann
Structure and Motion Toolkit, автор — Phil Torr
Matlab Code for Non-Rigid Structure from Motion [Архівовано 5 грудня 2014 у Wayback Machine.], автор — Lorenzo Torresani

Python

Python Photogrammetry Toolbox GUI — відкритий ГІК структури із руху (запускач 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.], повне рішення для фотограмметрії на базі відкритого програмного забезпечення
MountainsMap SEM, програмне забезпечення для сканувальних електронних мікроскопів. 3D отримується нахилом зразка + фотограмметрією.
Voodoo Camera Tracker [Архівовано 30 квітня 2016 у Wayback Machine.], некомерційний інструмент для поєднання віртуальних та реальних сцен.
Первісний сайт, заархівований: Laboratorium für Informationstechnologie, University of Hannover
MetaIO Toolbox, структура з руху для доповненої реальності на мобільних пристроях.
TacitView [Архівовано 2 квітня 2015 у Wayback Machine.] від 2d3 Sensing^[en]
Catena Python Abstract Workflow Framework з компонентами структури з руху.

[1] Linda G. Shapiro, George C. Stockman (2001). Computer Vision. Prentice Hall. ISBN 0-13-030796-3. (англ.)

[2] D. G. Lowe (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision. (англ.)

[3] H. Bay, T. Tuytelaars, and L. Van Gool (2006). Surf: Speeded up robust features. 9th European Conference on Computer Vision. (англ.)

[4] K. Häming and G. Peters (2010). The structure-from-motion reconstruction pipeline – a survey with focus on short image sequences. Kybernetika. Архів оригіналу за 18 лютого 2015. Процитовано 22 лютого 2015. (англ.)

[5] B. D. Lucas and T. Kanade. An iterative image registration technique with an application to stereo vision. IJCAI81. (англ.)

[6] 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. (англ.)

[7] F. Dellaert, S. Seitz, C. Thorpe, and S. Thrun (2000). Structure from Motion without Correspondence (PDF). IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Архів оригіналу (PDF) за 24 вересня 2015. Процитовано 22 лютого 2015. (англ.)

[8] Engel, Jakob; Schöps, Thomas; Cremers, Daniel (2014). European Converence on Computer Vision (ECCV) 2014 (PDF). Архів оригіналу (PDF) за 22 жовтня 2014. Процитовано 22 лютого 2015. {{cite journal}}: Проігноровано |contribution= (довідка) (англ.)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]