Налаштування пучка

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

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

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

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

Налаштування пучка зводиться до мінімізації помилки репроєкції між положеннями спостережуваних та передбачуваних точок зображення, яку можна виразити як суму квадратів великої кількості нелінійних, дійсних функцій. Таким чином, вирішення задаці мінімізації досягається за допомогою нелінійних алгоритмів найменших квадратів. З них метод Левенберга — Марквардта виявився одним з найуспішніших завдяки простоті реалізації та високої сходимості для широкого кола початкових оцінок. При вирішенні задач мінімізації, що виникають в рамках налаштування пучка, рівняння мають розріджену структуру блоків через відсутність зв'язку між параметрами різних 3D-точок і камер. Ця обставина може бути використана для отримання значних обчислювальних переваг, використовуючи розріджений варіант алгоритму Левенберга — Марквардта^: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 and A. Fitzgibbon, Bundle Adjustment — A Modern Synthesis, Vision Algorithms: Theory and Practice, 1999. (англ.)
• M.I.A. Lourakis and A.A. Argyros, SBA: A Software Package for Generic Sparse Bundle Adjustment, ACM Transactions on Mathematical Software, 2009. (англ.)
• A. Zisserman. Bundle adjustment. CV Online. (англ.)

Посилання

• [2]: Apero/MicMac, a free open source photogrammetric software. Cecill-B licence. (англ.)
• sba: A Generic Sparse Bundle Adjustment C/C++ Package Based on the Levenberg–Marquardt Algorithm (C, MATLAB). GPL. (англ.)
• cvsba: An OpenCV wrapper for sba library (C++). GPL. (англ.)
• ssba: Simple Sparse Bundle Adjustment package based on the Levenberg–Marquardt Algorithm (C++). LGPL. (англ.)
• OpenCV: Computer Vision library in the Images stitching module. BSD license. (англ.)
• mcba: Multi-Core Bundle Adjustment (CPU/GPU). GPL3. (англ.)
• libdogleg: General-purpose sparse non-linear least squares solver, based on Powell's dogleg method. LGPL. (англ.)
• ceres-solver: A Nonlinear Least Squares Minimizer. BSD license. (англ.)
• g2o: General Graph Optimization (C++) - framework with solvers for sparse graph-based non-linear error functions. LGPL. (англ.)
• DGAP: The program DGAP implement the photogrammetric method of bundle adjustment invented by Helmut Schmid and Duane Brown. GPL. (англ.)
• Bundler: A structure-from-motion (SfM) system for unordered image collections (for instance, images from the Internet) by Noah Snavely. GPL. (англ.)
• COLMAP: A general-purpose Structure-from-Motion (SfM) and Multi-View Stereo (MVS) pipeline with a graphical and command-line interface. BSD license. (англ.)
• Theia: A computer vision library aimed at providing efficient and reliable algorithms for Structure from Motion (SfM). New BSD license. (англ.)