Блочное уравнивание — это одновременное уточнение 3D-координат, описывающих геометрию сцены, параметров относительного движения и оптических характеристик камеры (камер), используемых для получения изображений, при наличии набора изображений, отображающих ряд 3D-точек с разных ракурсов.
Использование Блочное уравнивание почти всегда используется в качестве последнего шага алгоритмов трёхмерной реконструкции на основе признаков. Оно сводится к задаче оптимизации 3D-структуры и параметров просмотра (то есть положения камеры и, возможно, внутренней калибровки и радиальной дисторсии), для получения реконструкции, которая является оптимальной при определённых предположениях относительно шума, относящегося к наблюдаемым признакам изображения: если ошибка изображения является гауссовой с нулевым средним, то блочное уравнивание является оценкой максимального правдоподобия. Блочное уравнивание было первоначально разработано в области фотограмметрии в 1950-х годах и всё чаще используется исследователями компьютерного зрения в последние годы.
Общий подход Блочное уравнивание сводится к минимизации между наблюдаемыми и предсказанными положениями точек на изображениях. Эта ошибка выражается как сумма квадратов большого числа нелинейных вещественных функций. Следовательно, минимизация достигается с помощью алгоритмов нелинейных наименьших квадратов. Алгоритм Левенберга — Марквардта зарекомендовал себя как один из наиболее успешных благодаря простоте реализации и эффективной стратегии демпфирования, которая обеспечивает быструю сходимость из широкого диапазона начальных приближений. Итеративно линеаризуя минимизируемую функцию в окрестности текущей оценки, алгоритм Левенберга-Марквардта включает решение систем линейных уравнений, называемых . При решении задач минимизации, возникающих в рамках блочного уравнивания, нормальные уравнения имеют разреженную блочную структуру из-за отсутствия взаимодействия между параметрами для различных 3D-точек и камер. Это можно использовать для получения огромных вычислительных преимуществ, применяя разреженный вариант алгоритма Левенберга-Марквардта, который явно использует шаблон нулей нормальных уравнений, избегая хранения и операций с нулевыми элементами.
Математическое определение Блочное уравнивание заключается в совместном уточнении набора начальных оценок параметров камеры и структуры для нахождения набора параметров, которые наиболее точно предсказывают положения наблюдаемых точек в наборе доступных изображений. Более формально, предположим, что 3D-точек видны в ракурсах, и пусть — это проекция -й точки на изображение . Пусть обозначает бинарные переменные, равные 1, если точка видна на изображении , и 0 в противном случае. Предположим также, что каждая камера параметризуется вектором , а каждая 3D-точка — вектором . Блочное уравнивание минимизирует общую ошибку репроекции по всем параметрам 3D-точек и камер, а именно
где — это прогнозируемая точки на изображение , а обозначает евклидово расстояние между точками изображения, представленными векторам и . Поскольку минимум вычисляется по множеству точек и изображений, метод блочного уравнивания по определению устойчив к отсутствующим проекциям изображений, и если метрика расстояния выбрана разумно (например, евклидово расстояние), блочное уравнивание также минимизирует физически значимый критерий.
См. также
Стереоизображение Алгоритм Левенберга — Марквардта Разреженная матрица
SLAM (метод)
Примечания
Литература
Литература для дальнейшего чтения A. Zisserman. Bundle adjustment. CV Online.
Ссылки Программное обеспечение : Apero/MicMac, бесплатное программное обеспечение для фотограмметрии с открытым исходным кодом. Лицензия Cecill-B. sba: Универсальный пакет C/C++ для разреженного блочного уравнивания на основе алгоритма Левенберга — Марквардта (C, MATLAB). GPL. cvsba : Оболочка OpenCV для библиотеки sba (C++). GPL. ssba: Простой пакет разреженного блочного уравнивания на основе Алгоритм Левенберга — Марквардта (C++). LGPL. OpenCV: Библиотека компьютерного зрения в модуле сшивки изображений. Лицензия BSD. mcba: Многоядерное блочное уравнивание (CPU/GPU). GPL3. libdogleg: Универсальный решатель разреженных нелинейных задач наименьших квадратов, основанный на методе Пауэлла с ломаным шагом. LGPL. ceres-solver: Программа минимизации нелинейного метода минимальных кадратов. Лицензия BSD. g2o: Общая Графическая Оптимизация (C++) – средства разработки для решения разреженных нелинейных функций ошибок. LGPL. DGAP: Программа DGAP реализует фотограмметрические методы блочного уравнивания, разработанные Гельмутом Шмидом и Дуаной Браун. GPL. Bundler: Система «структура из движения» для неупорядоченной коллекции изображений (например, изображения из интернета) от Noah Snavely. GPL. COLMAP: Система «структура из движения» общего назначения с графическим интерфейсом и интерфейсом командной строки. Лицензия BSD. Theia: Библиотека компьютерного зрения, нацеленная на обеспечение эффективных и надёжных алгоритмов для поиска структур из движения. Лицензия New BSD. имеет инструменты для блочного уравнивания (Apache II лицензия). 3Dsurvey software включает средства блочного уравнивания.
Категория:Геометрия в компьютерном зрении Категория:Геодезия Категория:Фотограмметрия Категория:Межевание Категория:Картография