Bundle Adjustment (оптимизация в задаче трёхмерной реконструкции)

Материал из MachineLearning.

Статья написана с использованием LLM Claude Sonnet 5 и проверена участником Участник:Georgii Kvaratsкheliia 19 июля 2026 Промпт приводится полностью в Обсуждение: Bundle Adjustment (оптимизация в задаче трёхмерной реконструкции)

Содержание 1 Определение 1.1 Формальная постановка 1.2 Разреженная структура задачи 2 Мотивация 3 История 4 Методы решения 4.1 Метод Гаусса — Ньютона и Левенберга — Марквардта 4.2 Блочная структура и дополнение по Шуру 4.3 Альтернатива: пересечение-засечка (частный случай альтернированной минимизации) 5 Практические аспекты 5.1 Калибровочная свобода (gauge freedom) 5.2 Робастные функции потерь 6 Применения в машинном обучении и искусственном интеллекте 6.1 Структура из движения и трёхмерная реконструкция по фотографиям 6.2 SLAM и визуальная одометрия 6.3 Дифференцируемый Bundle Adjustment в глубоком обучении 6.4 Совместная оптимизация камер и нейронных полей излучения 7 Ограничения 8 См. также 9 Примечания 10 Литература

Bundle Adjustment (рус. «уравнивание связки», «оптимизация связки лучей») — метод совместной нелинейной оптимизации параметров камер (положения, ориентации, внутренней калибровки) и координат трёхмерных точек сцены, минимизирующий суммарную ошибку репроекции между наблюдаемыми и предсказанными положениями точек на изображениях. Название происходит от «связки» (bundle) лучей, соединяющих центр каждой камеры с наблюдаемыми ею 3D-точками: метод одновременно «подгоняет» (adjust) все такие связки лучей так, чтобы они наилучшим образом сходились в согласованных точках пространства. Bundle Adjustment — заключительный и обычно наиболее точный этап практически любого конвейера трёхмерной реконструкции по изображениям: восстановления структуры по движению (Structure from Motion, SfM), визуальной одометрии и SLAM, а также — в последние годы — обучения нейронных представлений сцены, таких как поля нейронного излучения (NeRF).

Определение

Формальная постановка

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

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

Разреженная структура задачи

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

Мотивация

• Накопление ошибки при инкрементальной реконструкции. Практические конвейеры SfM обычно строят реконструкцию последовательно, добавляя камеры и точки одну за другой; ошибки оценки на каждом шаге накапливаются («дрейф»). Bundle Adjustment периодически пересматривает все параметры сразу, распределяя накопленную невязку по всей системе и устраняя систематический дрейф — по этой причине метод часто называют «золотым стандартом» точности в фотограмметрии и компьютерном зрении[1].
• Совместность геометрии и калибровки. Ошибки в оценке внутренней калибровки камеры (фокусное расстояние, дисторсия) и ошибки в оценке внешних параметров (положения) взаимно компенсируют друг друга при независимой оценке; совместная оптимизация — единственный способ корректно разделить эти источники ошибки, если калибровка сама неизвестна точно.
• Максимизация точности при наличии измерительного шума. При гауссовом шуме измерений на изображении минимизация суммы квадратов ошибок репроекции соответствует оценке максимального правдоподобия для параметров камер и структуры сцены — статистически оптимальному способу использования всех доступных наблюдений одновременно[1].

История

Истоки метода лежат в аэрофотограмметрии середины XX века, где задача уравнивания связок лучей с наземных и аэроснимков решалась для построения точных топографических карт задолго до появления компьютерного зрения как отдельной дисциплины. Общая численная основа для решения таких нелинейных задач наименьших квадратов была заложена Левенбергом в 1944 году, предложившим демпфирование метода Гаусса — Ньютона для повышения устойчивости сходимости[2], и уточнена Марквардтом в 1963 году, придавшим этому демпфированию адаптивную, статистически обоснованную форму — так возник широко используемый по сей день метод Левенберга — Марквардта[3].

В компьютерном зрении систематическое, ставшее почти канонической точкой отсчёта изложение метода дала работа Триггса, Маклохлана, Хартли и Фицгиббона 2000 года «Bundle Adjustment — A Modern Synthesis», объединившая опыт фотограмметрии XX века с современными на тот момент численными методами разреженной оптимизации, робастными функциями потерь и вопросами калибровочной (gauge) инвариантности решения[1]. Стандартным справочным изложением геометрии многовидовых систем и роли в ней Bundle Adjustment для сообщества компьютерного зрения стал учебник Хартли и Зиссермана «Multiple View Geometry in Computer Vision»[4].

Появление крупномасштабных наборов фотографий из интернета поставило перед Bundle Adjustment вызов иного порядка: Агарвал, Снавли, Саймон, Зейтц и Шелиски показали в 2009 году («Building Rome in a Day»), что параллельные и распределённые алгоритмы сопоставления и уравнивания способны реконструировать трёхмерную модель целого города по десяткам тысяч неупорядоченных туристических фотографий[5]. Позднее Шёнбергер и Фрам (2016) представили открытый программный конвейер COLMAP, ставший де-факто отраслевым стандартом инкрементального SfM с Bundle Adjustment в качестве заключительного этапа уточнения[6].

С конца 2010-х годов началась интеграция Bundle Adjustment с методами глубокого обучения. Тан и Тан (2019) предложили BA-Net — архитектуру, делающую саму процедуру Bundle Adjustment дифференцируемой и обучаемой: сеть учится предсказывать параметр демпфирования метода Левенберга — Марквардта и признаки, по которым вычисляется ошибка репроекции, что позволяет обучать весь конвейер восстановления глубины и позы камеры сквозным градиентным спуском[7]. Тид и Дэн (2021) в системе DROID-SLAM встроили дифференцируемый слой Bundle Adjustment непосредственно в рекуррентную нейронную сеть, итеративно уточняющую оптические потоки, глубину и позы камер в реальном времени по видеопотоку[8]. Наконец, Лин, Ма, Торральба и Люси (2021) в работе BARF показали, что идею совместной («связочной») оптимизации можно распространить на обучение нейронных полей излучения (NeRF): при неточно известных позах камер поля излучения и сами позы камер оптимизируются совместно, по аналогии с классическим Bundle Adjustment, но с нейронной сетью в роли представления сцены вместо явного облака 3D-точек[9].

Методы решения

Метод Гаусса — Ньютона и Левенберга — Марквардта

Обозначим через вектор всех невязок репроекции, а через — его матрицу Якоби по всем параметрам камер и точек. Классический шаг Гаусса — Ньютона решает линеаризованную систему нормальных уравнений

а демпфированный вариант Левенберга — Марквардта добавляет регуляризацию для повышения устойчивости на итерациях, далёких от решения:

где параметр адаптивно увеличивается при неудачном шаге (приближая метод к градиентному спуску) и уменьшается при удачном (приближая его к чистому Гауссу — Ньютону)[2][3].

Блочная структура и дополнение по Шуру

Разделив параметры на блок камер и блок точек , систему нормальных уравнений можно записать в блочном виде

где блок , отвечающий за точки, сам блочно-диагонален (поскольку разные точки не связаны друг с другом напрямую в целевой функции). Это позволяет аналитически исключить блок точек через дополнение по Шуру, сведя задачу к существенно меньшей системе относительно одних лишь параметров камер:

после чего восстанавливается обратной подстановкой . Именно этот приём, подробно систематизированный в[1], делает возможным применение Bundle Adjustment к сценам с миллионами точек: обращение блочно-диагональной матрицы тривиально распараллеливается, а итоговая система для камер, число которых обычно на порядки меньше числа точек, решается быстро даже плотными методами.

Альтернатива: пересечение-засечка (частный случай альтернированной минимизации)

Более старая и более простая, но заметно медленнее сходящаяся схема — попеременное уточнение засечки (resection: оценка параметров камеры по фиксированным точкам) и пересечения (intersection: оценка точек по фиксированным камерам):

(засечка при фиксированных точках),

(пересечение при фиксированных камерах).

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

Практические аспекты

Калибровочная свобода (gauge freedom)

Целевая функция Bundle Adjustment инвариантна относительно глобального преобразования подобия всей реконструкции (поворот, сдвиг и масштаб сцены как целого можно менять произвольно, не меняя ни одной ошибки репроекции), что делает систему нормальных уравнений вырожденной без дополнительной фиксации системы отсчёта. Решения этой проблемы («калибровочной» или «gauge»-неоднозначности) — фиксация одной из камер, добавление слабых якорных ограничений или явная факторизация свободы подобия — подробно рассмотрены в[1].

Робастные функции потерь

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

Применения в машинном обучении и искусственном интеллекте

Структура из движения и трёхмерная реконструкция по фотографиям

Bundle Adjustment — обязательный завершающий этап практически всех современных конвейеров SfM, включая широко используемый открытый пакет COLMAP[6], а масштабируемые параллельные реализации метода сделали возможной реконструкцию городских сцен по десяткам тысяч неупорядоченных интернет-фотографий[5].

SLAM и визуальная одометрия

В задачах одновременной локализации и картографирования (SLAM) локальный вариант Bundle Adjustment («локальное уравнивание связки» по скользящему окну последних кадров) — стандартный компонент современных систем визуальной одометрии, обеспечивающий согласованность оценки траектории камеры и локальной карты сцены в реальном времени.

Дифференцируемый Bundle Adjustment в глубоком обучении

BA-Net встраивает саму процедуру Bundle Adjustment как дифференцируемый слой внутрь нейросетевого конвейера восстановления глубины, позволяя обучать признаки изображения так, чтобы результирующая задача Bundle Adjustment была легче для оптимизации, — вместо использования вручную спроектированных признаков[7]. DROID-SLAM развивает эту идею для полноценного визуального SLAM в реальном времени: рекуррентная сеть предсказывает обновления оптического потока, а дифференцируемый слой Bundle Adjustment на каждой итерации уточняет позы камер и карту глубины, согласуя предсказания сети с геометрическими ограничениями многовидовой съёмки[8]. Показательно, что даже спустя десятилетие развития end-to-end глубокого обучения классические методы Bundle Adjustment на основе явной геометрии по точности всё ещё превосходят многие чисто нейросетевые альтернативы в задачах структуры из движения — именно поэтому направление дифференцируемого и гибридного Bundle Adjustment остаётся активной областью исследований, а не просто исторической сноской[7].

Совместная оптимизация камер и нейронных полей излучения

BARF распространяет идею совместной («связочной») оптимизации на современные нейронные представления сцены: вместо явного облака 3D-точек оптимизируется параметрическая нейронная сеть, кодирующая радиационное поле сцены (NeRF)[10], а параметры камер уточняются совместно с весами этой сети точно так же, как координаты точек уточняются совместно с параметрами камер в классическом Bundle Adjustment[9]. Это показывает, что базовый принцип метода — совместная нелинейная оптимизация геометрии наблюдения и представления сцены по критерию согласованности предсказаний с изображениями — переживает смену конкретного представления сцены (явные 3D-точки → неявная нейронная функция) и остаётся актуальным математическим каркасом даже в задачах, изначально далёких от классической фотограмметрии.

Ограничения

• Невыпуклость и чувствительность к инициализации. Задача Bundle Adjustment существенно невыпукла из-за нелинейности проективной геометрии; метод Левенберга — Марквардта сходится лишь к локальному минимуму и требует достаточно точной начальной оценки параметров камер и точек, обычно получаемой инкрементальным SfM до запуска глобального уравнивания.
• Вычислительная стоимость при экстремальных масштабах. Несмотря на разреженную структуру и дополнение по Шуру, вычислительная стоимость всё же растёт с размером сцены; для действительно огромных коллекций изображений применяют дополнительные приближения — иерархическое или распределённое уравнивание, редукцию камер и разбиение сцены на перекрывающиеся кластеры.
• Устойчивость к выбросам требует отдельного внимания. Без робастных функций потерь или явной предварительной фильтрации ошибочных соответствий даже небольшая доля грубо неверных наблюдений может существенно исказить результат совместной оптимизации.
• Калибровочная неоднозначность. Необходимость явно фиксировать систему отсчёта (gauge freedom) — источник частых практических ошибок при самостоятельной реализации метода, если не следовать стандартным рецептам вроде описанных в[1].

См. также

• Альтернированная минимизация
• Метод Ньютона-Рафсона
• Компьютерное зрение
• Нейронное поле излучения
• Тензорное разложение

Примечания

1. Triggs B., McLauchlan P. F., Hartley R. I., Fitzgibbon A. W. Bundle Adjustment — A Modern Synthesis // Vision Algorithms: Theory and Practice (International Workshop on Vision Algorithms, IWVA 1999), Lecture Notes in Computer Science, vol. 1883. — Springer, 2000. — С. 298–372.
2. Levenberg K. A Method for the Solution of Certain Non-Linear Problems in Least Squares // Quarterly of Applied Mathematics. — 1944. — Т. 2, № 2. — С. 164–168.
3. Marquardt D. W. An Algorithm for Least-Squares Estimation of Nonlinear Parameters // Journal of the Society for Industrial and Applied Mathematics. — 1963. — Т. 11, № 2. — С. 431–441.
4. Hartley R., Zisserman A. Multiple View Geometry in Computer Vision. — 2-е изд. — Cambridge University Press, 2004.
5. Agarwal S., Snavely N., Simon I., Seitz S. M., Szeliski R. Building Rome in a Day // Proceedings of the IEEE International Conference on Computer Vision (ICCV). — 2009. — С. 72–79.
6. Schönberger J. L., Frahm J.-M. Structure-from-Motion Revisited // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). — 2016. — С. 4104–4113.
7. Tang C., Tan P. BA-Net: Dense Bundle Adjustment Networks // International Conference on Learning Representations (ICLR). — 2019.
8. Teed Z., Deng J. DROID-SLAM: Deep Visual SLAM for Monocular, Stereo, and RGB-D Cameras // Advances in Neural Information Processing Systems 34 (NeurIPS). — 2021. — С. 16558–16569.
9. Lin C.-H., Ma W.-C., Torralba A., Lucey S. BARF: Bundle-Adjusting Neural Radiance Fields // Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV). — 2021. — С. 5741–5751.
10. Mildenhall B., Srinivasan P. P., Tancik M., Barron J. T., Ramamoorthi R., Ng R. NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis // European Conference on Computer Vision (ECCV). — 2020. — С. 405–421.

Литература

• Triggs B., McLauchlan P. F., Hartley R. I., Fitzgibbon A. W. Bundle Adjustment — A Modern Synthesis // Vision Algorithms: Theory and Practice, LNCS 1883. — Springer, 2000. — С. 298–372.
• Hartley R., Zisserman A. Multiple View Geometry in Computer Vision. — 2-е изд. — Cambridge University Press, 2004.
• Schönberger J. L., Frahm J.-M. Structure-from-Motion Revisited // CVPR. — 2016. — С. 4104–4113.
• Agarwal S., Snavely N., Simon I., Seitz S. M., Szeliski R. Building Rome in a Day // ICCV. — 2009. — С. 72–79.
• Teed Z., Deng J. DROID-SLAM: Deep Visual SLAM for Monocular, Stereo, and RGB-D Cameras // NeurIPS. — 2021.
• Lin C.-H., Ma W.-C., Torralba A., Lucey S. BARF: Bundle-Adjusting Neural Radiance Fields // ICCV. — 2021. — С. 5741–5751.