Налаштування пучка: відмінності між версіями

[неперевірена версія]

← Попереднє редагування Наступне редагування →

Вилучено вміст Додано вміст

Лінійно

Версія за 18:05, 29 квітня 2021

Маючи набір зображень тривимірних точок для різних положень камер(и), налаштування пучка (англ. Bundle adjustment) можна визначити як проблему одночасної оптимізації тривимірних координат точок сцени, параметрів відносного руху та оптичних характеристик камер(и), що використовується для отримання оптимальних координат точок сцени, які мінімізують загальну помилку репроекції.

Використання

Налаштування пучків зазвичай використовується як останній крок методів об'ємної відбудови заснованих на пошуку відповідностей. Він являє собою задачу оптимізації тривимірної структури та параметрів камери (тобто положення камери і можливо, внутрішнього калібрування та радіального спотворення) з метою отримання реконструкції сцени яка є оптимальною за певних припущень щодо характеру шуму зображень^[1]: якщо шум має нормальний розподіл із нульовим середнім, тоді налаштування пучків є пошуком максимальної вірогідності^[2]^:2. Назва методу пов'язана із пучками світлових променів, що виходять із кожної тривимірної точки та сходяться в оптичному центрі кожної камери, які оптимально підлаштовуються як щодо структури сцени, так і параметрів камер. Метод налаштування пучків було розроблено для вирішення задач фотограмметрії в 1950-х роках та останнім часом все частіше застосовується дослідниками комп'ютерного зору^[2]^:2.

Загальний підхід

Налаштування пучка зводиться до мінімізації помилки репроекції між положеннями спостережуваних та передбачуваних точок зображення, яку можна виразити як суму квадратів великої кількості нелінійних, дійсних функцій. Таким чином, вирішення задаці мінімізації досягається за допомогою нелінійних алгоритмів найменших квадратів. З них метод Левенберга — Марквардта виявився одним з найуспішніших завдяки простоті реалізації та високої зходимості для широкого кола початкових оцінок. При вирішенні задач мінімізації, що виникають в рамках налаштування пучка, рівняння мають розріджену структуру блоків через відсутність зв'язку між параметрами різних 3D-точок і камер. Ця обставина може бути використана для отримання значних обчислювальних переваг, використовуючи розріджений варіант алгоритму Левенберга — Марквардта^[2]^:3.

Математичне визначення

Налаштування пучка є задачею спільної оптимізації набору початкових оцінок параметрів камери та структури сцени для знаходження таких значень параметрів, які найбільш точно передбачають положення спостережуваних точок у наборі доступних зображень. Більш формально^[3] припустимо, що $n$ тривимірних точок видно на $m$ зображеннях і нехай $\mathbf {x} _{ij}$ — проекція $i$ -ї точки на зображенні $j$ . Вважатимемо що значення $\displaystyle v_{ij}$ дорівнює 1, якщо точку $i$ видно на зображенні $j$ та 0 — інакше. Припустимо також, що параметри камери відповідного зображення $j$ задані вектором $\mathbf {a} _{j}$ а параметри тривимірної точки $i$ задані вектором $\mathbf {b} _{i}$ . Налаштування пучка мінімізує загальну помилку репроекції щодо всіх параметрів тривимірної точки та камери

\min _{\mathbf {a} _{j},\,\mathbf {b} _{i}}\displaystyle \sum _{i=1}^{n}\;\displaystyle \sum _{j=1}^{m}\;v_{ij}\,d(\mathbf {Q} (\mathbf {a} _{j},\,\mathbf {b} _{i}),\;\mathbf {x} _{ij})^{2},

де $\mathbf {Q} (\mathbf {a} _{j},\,\mathbf {b} _{i})$ — прогнозована проекція точки $i$ на зображенні $j$ та $d(\mathbf {x} ,\,\mathbf {y} )$ позначає евклідову відстань між точками зображення, представленими векторами $\mathbf {x}$ та $\mathbf {y}$ . Очевидно, що налаштування пучка за визначенням стійке до відсутності проекцій частини точок зображення та мінімізує фізично значущі параметри.

Див. також

Програмне забезпечення

[1]: Apero / MicMac, вільне фотограмметричне програмне забезпечення з відкритим кодом. Ліцензія Cecill-B.
sba: Універсальна реалізація налаштування пучка на базі алгоритма Левенберга — Марквардта написана на C / C++. GPL.
cvsba: OpenCV обгортка для бібліотеки sba (C ++). GPL.
ssba: Пакет для задач налаштування пучка, що базується на алгоритмі Левенберга — Маркварда (C ++). LGPL.
OpenCV: бібліотека комп'ютерного зору. Ліцензія BSD.
mcba: налаштування пучка для багатоядерних обчислювальних систем (CPU / GPU). GPL3.
libdogleg: Загальний розріджений нелінійний вирішувач найменших квадратів, заснований на методі Dogleg Пауелла. LGPL.
ceres-solver: Нелінійний мінімізатор найменших квадратів. Ліцензія BSD.
DGAP: Програма DGAP реалізує фотограмметричний метод регулювання пучків, винайдений Гельмутом Шмідом та Дуейном Брауном. GPL.
COLMAP: конвеєр загального призначення для Structure-from-Motion (SfM) та Multi-View Stereo (MVS) із графічним інтерфейсом та інтерфейсом командного рядка. Ліцензія BSD.

Посилання

↑ B. Triggs; P. McLauchlan; R. Hartley; A. Fitzgibbon (1999). Bundle Adjustment — A Modern Synthesis. ICCV '99: Proceedings of the International Workshop on Vision Algorithms. Springer-Verlag. с. 298—372. doi:10.1007/3-540-44480-7_21. ISBN 3-540-67973-1.
↑ ^а ^б ^в M.I.A. Lourakis and A.A. Argyros (2009). SBA: A Software Package for Generic Sparse Bundle Adjustment. ACM Transactions on Mathematical Software. 36 (1): 1—30. doi:10.1145/1486525.1486527. S2CID 474253.
↑ R.I. Hartley and A. Zisserman (2004). Multiple View Geometry in computer vision (вид. 2nd). Cambridge University Press. ISBN 978-0-521-54051-3.

[triggs1999-1] B. Triggs; P. McLauchlan; R. Hartley; A. Fitzgibbon (1999). Bundle Adjustment — A Modern Synthesis. ICCV '99: Proceedings of the International Workshop on Vision Algorithms. Springer-Verlag. с. 298—372. doi:10.1007/3-540-44480-7_21. ISBN 3-540-67973-1.

[sba2009-2] а ^б ^в M.I.A. Lourakis and A.A. Argyros (2009). SBA: A Software Package for Generic Sparse Bundle Adjustment. ACM Transactions on Mathematical Software. 36 (1): 1—30. doi:10.1145/1486525.1486527. S2CID 474253.

[3] R.I. Hartley and A. Zisserman (2004). Multiple View Geometry in computer vision (вид. 2nd). Cambridge University Press. ISBN 978-0-521-54051-3.

[1]

[2]

[3]

@@ Рядок 1: / Рядок 1: @@
+Маючи набір зображень тривимірних точок для різних положень камер(и), '''налаштування пучка''' ({{lang-en|Bundle adjustment}}) можна визначити як проблему одночасної оптимізації тривимірних [[Система координат|координат]] точок сцени, параметрів відносного руху та оптичних характеристик камер(и), що використовується для отримання оптимальних координат точок сцени, які мінімізують загальну помилку репроекції.
-Маючи набір зображень тривимірних точок для різних положень камер(и), '''налаштування пучка''' можна визначити як проблему одночасної оптимізації тривимірних [[Система координат|координат]] точок сцени, параметрів відносного руху та оптичних характеристик камер(и), що використовується для отримання оптимальних координат точок сцени, які мінімізують загальну помилку репроекції.
 == Використання ==
-Налаштування пучків зазвичай використовується як останній крок методів [[Об'ємна відбудова|об'ємної відбудови]] заснованих на пошуку відповідностей. Він являє собою задачу оптимізації тривимірної структури та параметрів камери (тобто положення камери і можливо, внутрішнього [[Калібрування камери|калібрування]] та [[Дисторсія|радіального спотворення]]) з метою отримання реконструкції сцени яка є оптимальною за певних припущень щодо характеру шуму зображень: якщо шум має [[Нормальний розподіл|нормальний]] розподіл із нульовим середнім, тоді налаштування пучків  є пошуком [[Метод максимальної правдоподібності|максимальної вірогідності]] . <ref name="sba2009">{{Cite journal|last=M.I.A. Lourakis and A.A. Argyros|year=2009|title=SBA: A Software Package for Generic Sparse Bundle Adjustment|journal=ACM Transactions on Mathematical Software|volume=36|issue=1|pages=1–30|doi=10.1145/1486525.1486527}}</ref> {{Rp|2}}  Назва методу пов'язана із пучками світлових променів, що виходять із кожної тривимірної точки та сходяться в оптичному центрі кожної камери, які оптимально підлаштовуються як щодо структури сцени, так і параметрів камер. Метод налаштування пучків було розроблено для вирішення задач [[Фотограмметрія|фотограмметрії]] в 1950-х роках та останнім часом все частіше застосовується дослідниками [[Комп'ютерний зір|комп'ютерного зору.]]  {{Rp|2}}
+Налаштування пучків зазвичай використовується як останній крок методів [[Об'ємна відбудова|об'ємної відбудови]] заснованих на пошуку відповідностей. Він являє собою задачу оптимізації тривимірної структури та параметрів камери (тобто положення камери і можливо, внутрішнього [[Калібрування камери|калібрування]] та [[Дисторсія|радіального спотворення]]) з метою отримання реконструкції сцени яка є оптимальною за певних припущень щодо характеру шуму зображень<ref name="triggs1999">{{cite conference |
+title=Bundle Adjustment — A Modern Synthesis |
+author=B. Triggs |author2=P. McLauchlan |author3=R. Hartley |author4=A. Fitzgibbon |
+book-title=ICCV '99: Proceedings of the International Workshop on Vision Algorithms |
+pages=298–372 |
+doi=10.1007/3-540-44480-7_21 |
+isbn=3-540-67973-1 |
+publisher=Springer-Verlag |
+year=1999
+}}</ref>: якщо шум має [[Нормальний розподіл|нормальний]] розподіл із нульовим середнім, тоді налаштування пучків є пошуком [[Метод максимальної правдоподібності|максимальної вірогідності]]<ref name="sba2009">{{cite journal |
+title=SBA: A Software Package for Generic Sparse Bundle Adjustment |
+author=M.I.A. Lourakis and A.A. Argyros |
+journal=ACM Transactions on Mathematical Software |
+pages=1–30 |
+volume=36 |
+issue=1 |
+doi=10.1145/1486525.1486527 |
+year=2009|
+s2cid=474253 }}</ref>{{rp|2}}. Назва методу пов'язана із пучками світлових променів, що виходять із кожної тривимірної точки та сходяться в оптичному центрі кожної камери, які оптимально підлаштовуються як щодо структури сцени, так і параметрів камер. Метод налаштування пучків було розроблено для вирішення задач [[Фотограмметрія|фотограмметрії]] в 1950-х роках та останнім часом все частіше застосовується дослідниками [[Комп'ютерний зір|комп'ютерного зору]]<ref name="sba2009" />{{rp|2}}.
 == Загальний підхід ==
-Налаштування пучка зводиться до мінімізації помилки репроекції між положеннями спостережуваних та передбачуваних точок зображення, яку можна виразити як суму квадратів великої кількості нелінійних, дійсних функцій. Таким чином, вирішення задаці мінімізації досягається за допомогою нелінійних алгоритмів [[Метод найменших квадратів|найменших квадратів.]] З них метод Левенберга – Марквардта виявився одним з найуспішніших завдяки простоті реалізації та високої зходимості для широкого кола початкових оцінок. При вирішенні задач мінімізації, що виникають в рамках налаштування пучка, рівняння мають [[Розріджена матриця|розріджену]] структуру блоків через відсутність зв'язку між параметрами різних 3D-точок і камер. Ця обставина може бути використана для отримання значних обчислювальних переваг, використовуючи розріджений варіант алгоритму Левенберга – Марквардта <ref name="sba2009">{{Cite journal|last=M.I.A. Lourakis and A.A. Argyros|year=2009|title=SBA: A Software Package for Generic Sparse Bundle Adjustment|journal=ACM Transactions on Mathematical Software|volume=36|issue=1|pages=1–30|doi=10.1145/1486525.1486527}}<cite class="citation journal cs1" data-ve-ignore="true" id="CITEREFM.I.A._Lourakis_and_A.A._Argyros2009">M.I.A. Lourakis and A.A. Argyros (2009). "SBA: A Software Package for Generic Sparse Bundle Adjustment". ''ACM Transactions on Mathematical Software''. '''36''' (1): 1–30. [[Цифровий ідентифікатор об'єкта|doi]]:[[doi:10.1145/1486525.1486527|10.1145/1486525.1486527]]. [[S2CID (ідентифікатор)|S2CID]]&nbsp;[https://api.semanticscholar.org/CorpusID:474253 474253].</cite></ref> {{Rp|3}}
+Налаштування пучка зводиться до мінімізації помилки репроекції між положеннями спостережуваних та передбачуваних точок зображення, яку можна виразити як суму квадратів великої кількості нелінійних, дійсних функцій. Таким чином, вирішення задаці мінімізації досягається за допомогою нелінійних алгоритмів [[Метод найменших квадратів|найменших квадратів.]] З них метод Левенберга&nbsp;— Марквардта виявився одним з найуспішніших завдяки простоті реалізації та високої зходимості для широкого кола початкових оцінок. При вирішенні задач мінімізації, що виникають в рамках налаштування пучка, рівняння мають [[Розріджена матриця|розріджену]] структуру блоків через відсутність зв'язку між параметрами різних 3D-точок і камер. Ця обставина може бути використана для отримання значних обчислювальних переваг, використовуючи розріджений варіант алгоритму Левенберга&nbsp;— Марквардта<ref name="sba2009"></ref>{{Rp|3}}.
 == Математичне визначення ==
-Налаштування пучка є задачею спільної оптимізації набору початкових оцінок параметрів камери та структури сцени для знаходження таких значень параметрів, які найбільш точно передбачають положення спостережуваних точок у наборі доступних зображень. Більш формально <ref>{{Cite book
+Налаштування пучка є задачею спільної оптимізації набору початкових оцінок параметрів камери та структури сцени для знаходження таких значень параметрів, які найбільш точно передбачають положення спостережуваних точок у наборі доступних зображень. Більш формально<ref>{{Cite book
 |title=Multiple View Geometry in computer vision
 |last=R.I. Hartley and A. Zisserman
@@ Рядок 16: / Рядок 33: @@
 |edition=2nd
 |isbn=978-0-521-54051-3
-}}</ref> припустимо, що <math>n</math> тривимірних точок видно на <math>m</math> зображеннях і нехай <math>\mathbf{x}_{ij}</math> - проекція <math>i</math>-ї точки на зображенні <math>j</math>. Вважатимемо що значення <math>\displaystyle v_{ij}</math> дорівнює 1, якщо точку <math>i</math> видно на зображенні <math>j</math> та 0 - інакше. Припустимо також, що параметри камери відповідного зображення <math>j</math> задані вектором <math>\mathbf{a}_j</math> а параметри тривимірної точки <math>i</math> задані вектором <math>\mathbf{b}_i</math> . Налаштування пучка мінімізує загальну помилку репроекції щодо всіх параметрів тривимірної точки та камери
+}}</ref> припустимо, що <math>n</math> тривимірних точок видно на <math>m</math> зображеннях і нехай <math>\mathbf{x}_{ij}</math>&nbsp;— проекція <math>i</math>-ї точки на зображенні <math>j</math>. Вважатимемо що значення <math>\displaystyle v_{ij}</math> дорівнює 1, якщо точку <math>i</math> видно на зображенні <math>j</math> та 0&nbsp;— інакше. Припустимо також, що параметри камери відповідного зображення <math>j</math> задані вектором <math>\mathbf{a}_j</math> а параметри тривимірної точки <math>i</math> задані вектором <math>\mathbf{b}_i</math> . Налаштування пучка мінімізує загальну помилку репроекції щодо всіх параметрів тривимірної точки та камери
 : <math>
 \min_{\mathbf{a}_j, \, \mathbf{b}_i} \displaystyle\sum_{i=1}^{n} \; \displaystyle\sum_{j=1}^{m} \; v_{ij} \, d(\mathbf{Q}(\mathbf{a}_j, \, \mathbf{b}_i), \; \mathbf{x}_{ij})^2,
 </math>
+де <math>\mathbf{Q}(\mathbf{a}_j, \, \mathbf{b}_i)</math>&nbsp;— прогнозована [[Матриця камери|проекція]] точки <math>i</math> на зображенні <math>j</math> та <math>d(\mathbf{x}, \, \mathbf{y})</math> позначає евклідову відстань між точками зображення, представленими векторами <math>\mathbf{x}</math> та <math>\mathbf{y}</math>. Очевидно, що налаштування пучка за визначенням стійке до відсутності проекцій частини точок зображення та мінімізує фізично значущі параметри.
+== Див. також ==
-де <math>\mathbf{Q}(\mathbf{a}_j, \, \mathbf{b}_i)</math> - прогнозована [[Матриця камери|проекція]] точки <math>i</math> на зображенні <math>j</math> і <math>d(\mathbf{x}, \, \mathbf{y})</math> позначає евклідову відстань між точками зображення, представленими векторами <math>\mathbf{x}</math> і <math>\mathbf{y}</math> . Очевидно, що налаштування пучка за визначенням стійке  до відсутності проекцій частини точок зображення та мінімізує фізично значущі параметри.
-== Дивіться також ==
 === Програмне забезпечення ===
-* [http://logiciels.ign.fr/?Telechargement,20] : Apero / MicMac, вільне фотограмметричне програмне забезпечення з відкритим кодом. Ліцензія Cecill-B.
+* [http://logiciels.ign.fr/?Telechargement,20]: Apero / MicMac, вільне фотограмметричне програмне забезпечення з відкритим кодом. Ліцензія Cecill-B.
-* [http://www.ics.forth.gr/~lourakis/sba/ sba] : Універсальна реалізація налаштування пучка на базі алгоритма Левенберга – Марквардта написана на C / C++. GPL.
+* [http://www.ics.forth.gr/~lourakis/sba/ sba]: Універсальна реалізація налаштування пучка на базі алгоритма Левенберга&nbsp;— Марквардта написана на C / C++. GPL.
-* [http://www.uco.es/investiga/grupos/ava/node/39/ cvsba]: OpenCV обгортка для бібліотеки [http://www.ics.forth.gr/~lourakis/sba/ sba] [[C++|(C ++]] ). GPL.
+* [http://www.uco.es/investiga/grupos/ava/node/39/ cvsba]: OpenCV обгортка для бібліотеки [http://www.ics.forth.gr/~lourakis/sba/ sba] [[C++|(C ++]]). GPL.
-* [https://github.com/royshil/SfM-Toy-Library/tree/335d7d2a0c1e603ec994d0e025bdec8ebeb493bc/3rdparty/SSBA-3.0 ssba:]  Пакет для задач налаштування пучка, що  базується на алгоритмі Левенберга – Маркварда (C ++). LGPL.
+* [https://github.com/royshil/SfM-Toy-Library/tree/335d7d2a0c1e603ec994d0e025bdec8ebeb493bc/3rdparty/SSBA-3.0 ssba:] Пакет для задач налаштування пучка, що базується на алгоритмі Левенберга&nbsp;— Маркварда (C ++). LGPL.
-* [http://opencv.org/ OpenCV] : бібліотека комп'ютерного зору. Ліцензія BSD.
+* [http://opencv.org/ OpenCV]: бібліотека комп'ютерного зору. Ліцензія BSD.
-* [http://grail.cs.washington.edu/projects/mcba/ mcba] : налаштування пучка для багатоядерних обчислювальних систем (CPU / GPU). GPL3.
+* [http://grail.cs.washington.edu/projects/mcba/ mcba]: налаштування пучка для багатоядерних обчислювальних систем (CPU / GPU). GPL3.
-* [https://github.com/dkogan/libdogleg libdogleg] : Загальний розріджений нелінійний вирішувач найменших квадратів, заснований на методі Dogleg Пауелла. LGPL.
+* [https://github.com/dkogan/libdogleg libdogleg]: Загальний розріджений нелінійний вирішувач найменших квадратів, заснований на методі Dogleg Пауелла. LGPL.
-* [http://ceres-solver.org/ ceres-solver] : Нелінійний мінімізатор найменших квадратів. Ліцензія BSD.
+* [http://ceres-solver.org/ ceres-solver]: Нелінійний мінімізатор найменших квадратів. Ліцензія BSD.
-* [http://www.ifp.uni-stuttgart.de/publications/software/openbundle/index.en.html DGAP] : Програма DGAP реалізує фотограмметричний метод регулювання пучків, винайдений Гельмутом Шмідом та Дуейном Брауном. GPL.
+* [http://www.ifp.uni-stuttgart.de/publications/software/openbundle/index.en.html DGAP]: Програма DGAP реалізує фотограмметричний метод регулювання пучків, винайдений Гельмутом Шмідом та Дуейном Брауном. GPL.
 * [https://colmap.github.io/ COLMAP]: конвеєр загального призначення для Structure-from-Motion (SfM) та Multi-View Stereo (MVS) із графічним інтерфейсом та інтерфейсом командного рядка. Ліцензія BSD.

Налаштування пучка: відмінності між версіями

Версія за 18:05, 29 квітня 2021

Зміст

Використання

Загальний підхід

Математичне визначення

Див. також

Програмне забезпечення

Посилання

Навігаційне меню

Налаштування пучка: відмінності між версіями

Версія за 18:05, 29 квітня 2021

Використання

Загальний підхід

Математичне визначення

Див. також

Програмне забезпечення

Посилання

Навігаційне меню

Пошук