Открыть сервис
Главная → Блог → Bundle Adjustment

Bundle Adjustment

Bundle Adjustment — это метод оптимизации, используемый в компьютерном зрении и фотограмметрии для одновременного уточнения трёхмерных координат точек сцены и параметров камер (внутренних и внешних), на основе набора двумерных изображений. Целью метода является минимизация ошибки перепроецирования — разницы между наблюдаемыми точками на изображениях и их проекциями, предсказанными текущей моделью. Bundle Adjustment является ключевым этапом в построении трёхмерных моделей по фотографиям, обработке данных с камер мобильных устройств, в системах дополненной реальности и в фотограмметрических задачах.

История

Истоки метода Bundle Adjustment лежат в фотограмметрии — науке об измерении объектов по фотографиям. В 1950-х годах, с развитием вычислительной техники, фотограмметристы начали разрабатывать методы совместной коррекции ошибок, возникающих при стереоскопическом измерении. Термин «bundle adjustment» (буквально «корректировка пучков») был введён в 1970-х годах и отражает суть метода: оптимизация пучков лучей, идущих от каждой камеры к каждой точке сцены. В 1980-х и 1990-х годах, с развитием компьютерного зрения, метод был адаптирован для автоматической обработки изображений. Ключевой вклад в развитие теории и практики внесли такие исследователи, как Билл Триггс, Ричард Хартли и Эндрю Зиссерман. В 2000-х годах, с появлением больших наборов данных (например, в проектах по реконструкции городов), были разработаны эффективные алгоритмы разреженной оптимизации, позволяющие обрабатывать миллионы точек и тысячи камер.

Постановка задачи

Пусть имеется набор из n трёхмерных точек X<sub>j</sub> (j = 1, …, n) и m камер с параметрами P<sub>i</sub> (i = 1, …, m). Каждая камера характеризуется внутренними параметрами (фокусное расстояние, главная точка, дисторсия) и внешними параметрами (положение и ориентация в пространстве). Для каждой пары (камера i, точка j) известно, проектируется ли точка на изображение камеры, и если да, то зафиксированы координаты её проекции x<sub>ij</sub> (в пикселях). Задача Bundle Adjustment состоит в нахождении таких X<sub>j</sub> и P<sub>i</sub>, которые минимизируют суммарную ошибку перепроецирования:

\[ \min_{\mathbf{P}_i, \mathbf{X}_j} \sum_{i=1}^{m} \sum_{j=1}^{n} v_{ij} \cdot \rho \left( \| \mathbf{x}_{ij} - \pi(\mathbf{P}_i, \mathbf{X}_j) \|^2 \right) \]

где:

  • \( v_{ij} \) — индикатор видимости (1, если точка j видна на изображении i, иначе 0);
  • \( \pi(\mathbf{P}_i, \mathbf{X}_j) \) — функция проекции точки X<sub>j</sub> на изображение камеры с параметрами P<sub>i</sub>;
  • \( \rho \) — функция потерь (например, квадратичная или более устойчивая к выбросам, как Huber loss).

Математическая основа

Модель камеры

Наиболее распространённой моделью является модель камеры-обскуры (pinhole camera). Внешние параметры задаются матрицей поворота R и вектором трансляции t. Внутренние параметры — матрицей K:

\[ \mathbf{K} = \begin{bmatrix} f_x & 0 & c_x \\ 0 & f_y & c_y \\ 0 & 0 & 1 \end{bmatrix} \]

где \( f_x, f_y \) — фокусные расстояния в пикселях, \( c_x, c_y \) — координаты главной точки. Проекция точки X = (X, Y, Z) на изображение вычисляется как:

\[ \mathbf{x} = \mathbf{K} [\mathbf{R} | \mathbf{t}] \mathbf{X} \]

Оптимизация

Bundle Adjustment — это задача нелинейной оптимизации методом наименьших квадратов. Для её решения применяются итерационные алгоритмы, такие как:

Ключевой особенностью Bundle Adjustment является разреженная структура матрицы Якоби. Каждая точка зависит только от небольшого числа камер (обычно от 2 до 10), а каждая камера — от небольшого числа точек. Это позволяет применять эффективные методы разреженной линейной алгебры, такие как метод Шура (Schur complement), который существенно ускоряет вычисления.

Применение

Фотограмметрия

В классической фотограмметрии Bundle Adjustment используется для точного построения карт, планов местности и трёхмерных моделей зданий по аэрофотоснимкам и спутниковым изображениям. Метод позволяет компенсировать ошибки, вызванные дисторсией объектива, неточностью GPS/IMU и атмосферными искажениями.

Компьютерное зрение

  • Структура из движения (Structure from Motion, SfM): Bundle Adjustment является финальным этапом SfM, где по набору фотографий восстанавливается как трёхмерная структура сцены, так и параметры камер. Примеры: реконструкция достопримечательностей (например, проект «Rome Reborn»), создание 3D-моделей для музеев.
  • Визуальная одометрия и SLAM (Simultaneous Localization and Mapping): в системах дополненной реальности (например, ARKit от Apple, ARCore от Google) и робототехнике Bundle Adjustment используется для уточнения карты окружающей среды и положения камеры в реальном времени. В SLAM-системах метод часто применяется в виде «локального» Bundle Adjustment (оптимизация только недавно добавленных точек и камер) для снижения вычислительной нагрузки.
  • Калибровка камер: Bundle Adjustment позволяет совместно уточнять внутренние и внешние параметры камер по набору изображений калибровочного шаблона.

Робототехника

В робототехнике Bundle Adjustment используется для построения карт местности и навигации. Например, в беспилотных автомобилях метод помогает уточнять положение автомобиля относительно дорожной разметки и препятствий.

Реализации

Существует множество программных реализаций Bundle Adjustment, как открытых, так и коммерческих:

  • Ceres Solver (Google) — библиотека нелинейной оптимизации, широко используемая в компьютерном зрении и робототехнике. Поддерживает разреженные матрицы, автоматическое дифференцирование и различные функции потерь.
  • g2o (General Graph Optimization) — библиотека для оптимизации графов, часто применяемая в SLAM-системах.
  • SBA (Sparse Bundle Adjustment) — одна из первых реализаций, написанная на C++.
  • OpenMVG (Open Multiple View Geometry) — библиотека для SfM, включающая модуль Bundle Adjustment.
  • COLMAP — популярная программа для SfM и MVS (Multi-View Stereo), использующая Ceres Solver для Bundle Adjustment.

Преимущества и недостатки

Преимущества

  • Высокая точность: метод позволяет достичь субпиксельной точности при достаточном количестве изображений.
  • Робастность: устойчив к выбросам при использовании подходящих функций потерь.
  • Масштабируемость: современные реализации могут обрабатывать миллионы точек и тысячи камер.

Недостатки

  • Вычислительная сложность: полный Bundle Adjustment на больших наборах данных требует значительных вычислительных ресурсов и времени.
  • Чувствительность к начальной оценке: метод сходится к локальному минимуму, поэтому требуется хорошее начальное приближение.
  • Требование к данным: для успешной работы необходимо, чтобы каждая точка была видна на нескольких изображениях (обычно не менее 2-3).

Связанные методы

  • Структура из движения (SfM): предшествующий этап, который даёт начальную оценку для Bundle Adjustment.
  • Многовидовая стерео (MVS): этап, следующий за Bundle Adjustment, для построения плотной трёхмерной модели.
  • Визуальная одометрия: метод оценки движения камеры, часто использующий Bundle Adjustment для уточнения.
  • SLAM: система, объединяющая оценку положения и построение карты, где Bundle Adjustment является одним из ключевых компонентов.

Источники

  1. Triggs, B., McLauchlan, P. F., Hartley, R. I., & Fitzgibbon, A. W. (1999). Bundle Adjustment — A Modern Synthesis. In: Triggs, B., Zisserman, A., Szeliski, R. (eds) Vision Algorithms: Theory and Practice. Lecture Notes in Computer Science, vol 1883. Springer, Berlin, Heidelberg.
  2. Hartley, R., & Zisserman, A. (2004). Multiple View Geometry in Computer Vision (2nd ed.). Cambridge University Press.
  3. Szeliski, R. (2010). Computer Vision: Algorithms and Applications. Springer.
  4. Agarwal, S., & Mierle, K. (2010). Ceres Solver. URL: http://ceres-solver.org
  5. Kümmerle, R., Grisetti, G., Strasdat, H., Konolige, K., & Burgard, W. (2011). g2o: A General Framework for Graph Optimization. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы