Блочная оптимизация алгоритма восстановления геометрии трехмерной сцены по набору изображений

Активное внедрение методов компьютерного зрения в различных отраслях науки и техники делает актуальной и перспективной для исследования проблему восстановления геометрии трехмерной сцены по набору изображений. В частности, эта задача необходима при построении и уточнении карт высот, трехмерных моделей местности и архитектурных сооружений, в системах мониторинга и навигации.
Стандартным методом поиска оптимального решения этой задачи является метод разреженного совместного уравнивания невязок (SBA, sparse bundle adjustment). Этот метод подразумевает оптимизацию ошибки проецирования трехмерной точки на изображение (reprojection error) с использованием начального приближения параметров камер и трехмерной сцены.
Классическим инструментом поиска оптимума в SBA является алгоритм Левенберга-Марквардта, основанный на нелинейном методе наименьших квадратов (МНК) с использованием различных стратегий регуляризации. Основной акцент на каждой итерации МНК делается на структуру получаемых уравнений, в частности, формируемая разреженная матрица системы разделяется на блоки с учетом структуры параметров, что дает возможность свести общую задачу к раздельному решению систем уравнений относительно параметров камер и трехмерной сцены.
Главным недостатком классического подхода является то, что трудоемкость пропорциональна квадрату количества изображений. Данный факт особенно значим для очень больших последовательностей изображений. В данной работе рассматривает вопрос оптимизации классического подхода на предмет уменьшения вычислительной сложности путем разбиения исходной последовательности изображений на перекрывающиеся блоки с выполнением поиска оптимума в каждом блоке и последующим согласованием результатов.
Рассматриваемый в докладе подход позволяет существенно сократить время работы алгоритма и снизить затраты по памяти. Вместе с тем, при некорректном формировании блоков как по количеству изображений в них, так и по степени их взаимного перекрытия (для смежных блоков), оптимум может восстанавливаться со значительными погрешностями, что требует дополнительного исследования алгоритма.
Алгоритм был реализован на языке С++ . Произведено сравнение классического алгоритма и его модификации, предлагаемой в данной работе, на нескольких тестовых наборах изображений в терминах баланса между вычислительной сложностью и точностью восстановления оптимума.