Structure from Motion

Structure from Motion (сокр. SfM, с англ. — «структура из движения») — это фотограмметрический метод трёхмерной реконструкции, позволяющий восстанавливать трёхмерную геометрию объектов и сцен, а также параметры камеры (положение, ориентацию, фокусное расстояние) на основе набора двумерных изображений, полученных с разных точек съёмки. Метод основан на анализе соответствий между ключевыми точками на перекрывающихся снимках и не требует предварительной информации о калибровке камеры или положении объекта в пространстве. SfM широко применяется в компьютерном зрении, геодезии, археологии, робототехнике, кинематографии и цифровом моделировании.

История

Истоки метода Structure from Motion восходят к развитию фотограмметрии в XIX веке, однако его современная математическая основа была заложена в 1970–1980-х годах с появлением компьютерного зрения. В 1979 году Ханс-Петер Моррисон и Джеймс Кроули предложили алгоритмы восстановления глубины по последовательности кадров. Ключевой прорыв произошёл в 1990-х годах, когда Ричард Хартли и другие исследователи формализовали задачу SfM как решение системы уравнений, связывающих координаты точек на изображениях с их трёхмерными координатами. В 2000-х годах развитие методов поиска и описания ключевых точек (SIFT, SURF) и алгоритмов разреженной реконструкции (Bundle Adjustment) сделало SfM пригодным для обработки тысяч изображений. С 2010-х годов метод стал доступен широкому кругу пользователей благодаря открытым библиотекам (OpenMVG, COLMAP, VisualSFM) и интеграции в коммерческие продукты (Agisoft Metashape, RealityCapture).

Основные принципы

1. Поиск и описание ключевых точек

На каждом изображении алгоритм находит характерные особенности (ключевые точки) — углы, границы, текстуры, устойчивые к изменениям освещения, масштаба и поворота. Для этого используются дескрипторы, например SIFT (Scale-Invariant Feature Transform) или AKAZE. Каждая точка описывается вектором признаков, позволяющим сопоставлять её с точками на других снимках.

2. Сопоставление точек

Для каждой пары изображений вычисляется множество соответствий между ключевыми точками. Если точка на одном снимке соответствует точке на другом, она может быть одной и той же физической точкой на объекте. Для отбора надёжных соответствий применяется геометрическая фильтрация, например алгоритм RANSAC (Random Sample Consensus), который отбрасывает выбросы на основе эпиполярной геометрии.

3. Оценка относительного положения камер

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

4. Триангуляция

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

5. Глобальная оптимизация (Bundle Adjustment)

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

6. Плотная реконструкция (опционально)

После получения разреженного облака и точных параметров камер можно построить плотное облако точек (dense point cloud) или сетку (mesh) с помощью методов стереосопоставления (например, MVS — Multi-View Stereo). Для этого каждый пиксель изображения сопоставляется с соответствующими пикселями на соседних снимках, что позволяет восстановить детальную поверхность.

Классификация методов SfM

По типу входных данных

• Одиночная камера (monocular SfM) — съёмка с одной камеры, движущейся в пространстве. Требует достаточного перекрытия между кадрами.
• Стерео SfM — использование стереопары (двух камер с известным базисом) для получения масштаба и повышения точности.
• Мульти-камерные системы — одновременная съёмка с нескольких камер, что ускоряет процесс и улучшает покрытие.

По способу инициализации

• Последовательный (incremental) SfM — реконструкция начинается с одной пары изображений, затем добавляются новые кадры один за другим. Наиболее распространённый подход (например, в COLMAP). Медленный, но точный.
• Глобальный (global) SfM — все изображения обрабатываются одновременно, параметры камер и точек вычисляются из единой системы уравнений. Быстрее, но менее устойчив к шуму.
• Иерархический (hierarchical) SfM — изображения группируются в кластеры, реконструкция выполняется для каждого кластера, затем кластеры объединяются.

По масштабу

• Локальный SfM — для одного объекта (статуя, здание, артефакт). Обычно 10–100 изображений.
• Среднемасштабный SfM — для сцен размером до нескольких километров (археологические раскопки, городские кварталы). 100–1000 изображений.
• Глобальный SfM — для реконструкции целых городов или регионов (например, проект «Google Earth»). Тысячи и миллионы снимков.

Применение

Археология и культурное наследие

SfM используется для создания точных 3D-моделей археологических объектов, раскопок, фресок и скульптур. Например, метод применялся для документирования храмов Пальмиры (Сирия) до разрушения, а также для реконструкции древних городов в Перу и Греции. Позволяет получать модели с разрешением до 0,1 мм.

Геодезия и картография

С помощью беспилотных летательных аппаратов (БПЛА) и SfM строятся ортофотопланы и цифровые модели рельефа (ЦМР) для мониторинга оползней, ледников, строительных площадок. Точность может достигать 1–5 см при высоте съёмки 50–100 м.

Робототехника и навигация

В системах SLAM (Simultaneous Localization and Mapping) SfM используется для одновременного построения карты окружающей среды и определения положения робота. Например, в автономных автомобилях и дронах.

Кинематография и компьютерная графика

SfM применяется для совмещения виртуальных объектов с реальной съёмкой (match moving). Программы, такие как PFTrack и SynthEyes, используют SfM для восстановления движения камеры по видеоряду.

Медицина и биология

Метод используется для создания 3D-моделей органов по серии медицинских снимков (например, КТ или МРТ), а также для реконструкции поверхности клеток и тканей в микроскопии.

Преимущества и ограничения

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

• Не требует дорогостоящего оборудования (достаточно цифровой камеры или смартфона).
• Автоматизирован — минимальное участие оператора.
• Высокая точность при достаточном перекрытии и хорошем освещении.
• Масштабируемость — от одного объекта до целых ландшафтов.

Ограничения

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

Программное обеспечение

Открытое

• COLMAP — популярная библиотека для инкрементального SfM и MVS, поддерживает CUDA.
• OpenMVG — модульная библиотека для SfM, включает глобальные и инкрементальные алгоритмы.
• VisualSFM — графический интерфейс на базе OpenMVG, удобен для начального знакомства.
• Meshroom — узел-ориентированный интерфейс на основе AliceVision, включает полный пайплайн SfM и MVS.

Коммерческое

• Agisoft Metashape — профессиональный пакет для фотограмметрии, поддерживает SfM и плотную реконструкцию.
• RealityCapture — высокопроизводительное решение, используемое в игровой индустрии и кинематографе.
• Pix4Dmapper — специализированное ПО для БПЛА-съёмки и геодезии.

Интересные факты

• Метод SfM лежит в основе технологии «фотограмметрического сканирования», которая позволяет создавать 3D-модели объектов без физического контакта.
• В 2019 году с помощью SfM была реконструирована статуя Будды в Бамиане (Афганистан), уничтоженная талибами (организация признана террористической и запрещена в РФ), по старым фотографиям.
• Алгоритмы SfM используются в системах дополненной реальности (AR) для привязки виртуальных объектов к реальному миру.

Источники

• Hartley, R., Zisserman, A. (2004). Multiple View Geometry in Computer Vision. Cambridge University Press.
• Snavely, N., Seitz, S. M., Szeliski, R. (2006). «Photo Tourism: Exploring Photo Collections in 3D». ACM Transactions on Graphics.
• Schonberger, J. L., Frahm, J.-M. (2016). «Structure-from-Motion Revisited». IEEE Conference on Computer Vision and Pattern Recognition.
• OpenMVG documentation (2020). «Structure from Motion Pipeline».
• Agisoft Metashape User Manual (2023).