Привет, Хабр! Сегодня мы расскажем про один из способов повышения качества склейки панорамы. Существует широко используемый подход склейки панорамы плоских объектов, но поскольку данный подход не лишен недостатков, мы предлагаем свое улучшение.
Задача панорамирования заключается в построении одного составного изображения на основе набора исходных изображений (см. рис. 1). Она находит применение в решении таких практических задач, как:
- зондирование поверхности Земли со спутника или с дрона;
- склейка изображений, полученных с помощью микроскопа;
- склейка видео;
- получение изображения в супер-разрешении.
Рисунок 1 — Исходные изображения и панорама
В общем виде алгоритм склейки панорамы можно сформулировать следующим образом [1] (см. рис. 2). В самом начале требуется извлечь из видеопотока достаточное количество кадров. Это можно делать в режиме "онлайн", последовательно считывая все кадры и выбирая отдельные из них с необходимой частотой.
Рисунок 2 — Блок-схема работы алгоритма склейки панорамы, использующего особые точки
После этого, последовательно перебирая пары изображений из набора, следует произвести детектирование особых точек и вычисление их дескрипторов на этих изображениях [2–4]. Именно эти особые точки позволяют построить геометрическое соответствие между двумя кадрами. Далее следует сопоставление особых точек на основе их дескрипторов. Стоит иметь в виду, что при этом не исключено получение ложных соответствий.
Далее, имея два набора особых точек, следует найти проективное преобразование, которое переводило бы точки одного кадра в соответствующие точки другого наилучшим образом. Для решения этой задачи может быть использован подход RANSAC [5]. Подробнее данный подход описан в работах [6, 7]
Для поиска проективного преобразования между кадрами также может использоваться оптический поток, который часто применяется в задаче склейки панорамы [8].
После получения нужного набора проективных преобразований имеет место техническая процедура склейки изображений, а именно: для каждого пикселя конечной панорамы (x,y) по каждому каналу (RGB) рассчитывается среднее арифметическое значение интенсивностей пикселей с координатами (x,y) всех кадров, включающих в себя пиксель с такими координатами.
С помощью методов поиска проективных преобразований можно определять смещение положения камеры относительно предыдущего положения в пространстве. В лабораторных условиях точности вычислений этих данных достаточно для построения панорамы плоского неподвижного объекта. В реальных условиях, при вычислении смещения положения камеры относительно предыдущего положения возникает погрешность вычислений (ошибка замеров/помехи/ограничения, накладываемые алгоритмами и т.п.). С течением времени аккумулятивная ошибка продолжает нарастать таким образом, что, несмотря на приемлемую точность определения смещения между соседними положениями, общая панорама объекта будет содержать уже серьезные отклонения (см. рис. 3).
Рисунок 3 — Аккумулятивная ошибка
Мы поставили для себя цель разработать метод согласования графа проективных преобразований для задачи панорамирования плоских неподвижных объектов, устойчивый к проблеме накопления ошибок. Еще одной целью является разработка метода таким образом, чтобы он не зависел от метода вычисления параметров проективного преобразования.
Должно выполняться одно из условий:
- ведется съемка неподвижного псевдоригидного объекта;
- ведется съемка объекта близкого к плоскому с достаточно большого расстояния;
- для всех положений камеры во время съемки выполнено требование: для всех точек изображения лучи, соединяющие эти точки с фокусом камеры, не совпадают друг с другом.
Описание алгоритма согласования графа проективных преобразований
Введем понятие единой системы координат. Под единой системой координат будем понимать такую систему координат, где одни и те же точки объекта с разных изображений будут иметь одинаковые координаты. Это требование можно выразить следующей формулой:
где 
– это отображение определенное на общей части кадров и переводящее точки первого кадра в точки второго кадра, 
– координаты точки в системе координат первого кадра, 
– координаты точки в системе координат второго кадра.
В том случае, когда отображение может быть корректно продолжено за область пересечения кадров, мы можем дополнить второй кадр информацией из первого. Таким образом будет получена карта, склеенная как мозаика, из двух или более кадров.
После нахождения проективных преобразований между соседними кадрами имеется первоначальная склейка, задающая однозначное расположение кадров в единой системе координат (см. рис. 4).
Рисунок 4 — Однозначное расположение кадра на карте
После построения первичной склейки изображений строится граф проективных преобразований 
:
где 
– множество четверок точек, являющихся вершинами проективно исправленных изображений; 
, 
– множество проективных преобразований между кадрами; 
.
Ребро между вершинами строится только в том случае, если кадры пересекаются не менее, чем на 
на первичной склейке (IoU – Intersection over Union) (см. рис. 5, 6):
Рисунок 5 — Область пересечения кадров
Порог 
подбирается в зависимости от используемого метода поиска проективного преобразования путем балансирования между обусловленностью задачи поиска проективного преобразования между двумя кадрами и желаемым ожидаемым количеством ребер и циклов в графе.
Рисунок 6 — Пример построения графа
В итоге граф проективных преобразований выглядит следующим образом (см. рис. 7):
Рисунок 7 — Итоговый граф проективных преобразований
Если граф содержит циклы (см. рис. 6), то в нем появляется избыточная информация, которая к тому же может содержать противоречия. Чтобы определить, какого рода противоречия могут возникнуть, рассмотрим некоторый цикл графа (см. рис. 8). Пусть этот цикл состоит из вершин 
. Тогда мы имеем серию проективных отображений вдоль этого цикла:
Рассмотрим композицию этих отображений:
Рисунок 8 — Цикл графа
Отображение 
должно быть тождественным отображением. Если отображение отличается от тождественного, то мы говорим, что получено противоречие. Цикл в таком случае будем называть несогласованным. Таким образом, существует проблема, связанная с наличием несогласованных циклов в графе проективных отображений, поскольку при идеальной склейке противоречия в графе проективных преобразований должны отсутствовать.
Опишем алгоритм согласования графа проективных преобразований, т. е. согласования всех его циклов. Для минимизации аккумулятивной ошибки, которая проявляется при замыкании цикла в графе проективных преобразований, применяется концепция метода SLAM (Simultaneous Localization And Mapping) [9].
Рассмотрим в каждом кадре четверку точек общего положения. Пусть кадры пронумерованы от 
до 
, тогда четверки точек будем обозначать через 
, где 
. Такой набор четверок точек 
однозначно задает единую систему координат, так как для любых двух кадров можно единственным образом найти проективное отображение, переводящее одну четверку точек в другую.
Чтобы найти набор четверок точек, который будет задавать искомый согласованный граф, можно воспользоваться методом наименьших квадратов. Мы минимизируем функционал, который равен сумме по всем ребрам из набора графа , а для каждого ребра — сумме по четырем точкам величин 
. Для нахождения решения, минимизирующего функционал, предлагается использовать метод сопряженных градиентов.
После того, как для каждого кадра имеется проективное преобразование, однозначно задающее положение кадра на карте, можно получить изображение панорамы.
Экспериментальные результаты
На сегодняшний день не существует универсального метода оценки качества склейки изображений. Как правило качество склейки оценивается экспертами органолептически, но для научных исследований предпочтительней иметь количественную, автоматически вычисляемую оценку качества.
Для того, чтобы оценить качество склейки без участия человека-эксперта необходимо иметь эталонную склейку, с которой будет сравниваться результат. Подход, при котором склейка была получена из реального видео, а эталонной склейкой считается фотография всего объекта, требует хороших лабораторных условий с использованием манипулятора, который способен физически фиксировать (с помощью датчиков) положение камеры в пространстве. Однако данный метод оценки качества является высокозатратным.
В работе [10] для количественной оценки качества склейки панорамы авторы предлагают, имея изображение высокого разрешения, создать искусственное видео, кадрами которого являются проективно искаженные области исходного изображения (см. рис. 9). Проективно искажаются все кадры, за исключением первого, поскольку единая система координат задается относительно первого кадра. Далее эти кадры искусственного видео склеиваются в панораму, которая в дальнейшем сравнивается с исходным эталонным изображением. При данном подходе удается избежать проблем разницы яркости полученной и эталонной склеек, а также искажений сцены.
Рисунок 9 — Исходное изображение и кадры искусственного видео
Для сравнения качества склейки до и после согласования графа была подготовлена тестовая выборка из 50 изображений, создано 50 искусственных видео из исходных изображений, по которым производилась склейка (см. рис. 10). Все полученные панорамы приводились к размерам исходных изображений и для каждой панорамы рассчитывалась мера ошибки:
где 
– высота изображения, 
– ширина изображения, 
– интенсивность пикселя 
полученной панорамы на красном канале ( – зеленый канал, 
– синий канал), 
– интенсивность пикселя исходного изображения на красном канале ( – зеленый канал, – синий канал).
Рисунок 10 — Панорама до согласования графа (RMSE = 35.3) и после (RMSE = 14.2)
В графическом представлении RMSE на тестовой выборке выглядит следующим образом (см. рис. 11):
Рисунок 11 — RMSE на тестовой выборке. Кадры отсортированы в порядке возрастания RMSE до согласования графа.
В соответствие каждому значению корня среднеквадратичной ошибки до согласования представлены значения корня среднеквадратичной ошибки после согласования графа. Медианное значение RMSE на тестовой выборке до согласования графа составляет 35.5, после согласования графа – 13.9.
Заключение
Исходя из результатов сравнения качества склейки можно сделать вывод, что согласование графа существенно снижает накопленную ошибку и повышает качество склейки панорамы. Однако, надо иметь в виду, что согласование графа может помочь только в том случае, если в графе проективных преобразований имеются циклы. При отсутствии циклов в графе проективных преобразований модуль согласования графа не ухудшает качество склейки панорамы.
Стоит отметить, что данный метод согласования графа работает с набором проективных преобразований и способ, которым были найдены эти проективные преобразования, для данного метода роли не играет.
В дальнейшем планируется оптимизировать сложность работы алгоритма, поскольку применим он только для «оффлайн» юзкейсов.
Литература
[1] Губин А.Ю., Ковин Р.В. Простой подход к задаче склейки перекрывающихся изображений в панораму // X Международная научно-практическая конференция студентов, аспирантов и молодых ученых "Молодежь и современные информационные технологии", с. 79-81, 2012.
[2] Drummond T., Rosten E. Machine Learning for high-speed corner detection // 9th European Conference on Computer Vision (ECCV), p. 430-443, 2006.
[3] Lowe D.G. Distinctive Image Features from Scale-Invariant Keypoints // International Journal of Computer Vision, p. 91-110, 2004.
[4] Bay H., Ess A., Yuitelaars T., Van Gool L. SURF: Speeded up robust features // Computer Vision and Image Understanding, v. 110, p. 346-359, 2008.
[5] Martin A. Fischler, Robert C. Bolles. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography // Comm. of the ACM, v. 24, p. 381-395, 1981.
[6] Арлазаров В.Л., Булатов К.Б., Чернов Т.С. Метод нечеткого поиска изображений в больших объемах видеоданных // Системы высокой доступности, Т. 12, № 1, с. 53-58, 2016.
[7] Skoryukina N. et al. Snapscreen: TV-stream frame search with projectively distorted and noisy query // 9th International COnference on Machine Vision (ICMV) — Proc. SPIE V. 10341, P. 103410Y, 2017.
[8] Bouguet J.Y. Pyramidal implementation of the affine lucas kanade feature tracker: destription of the algorithm // Intel corporation, V. 5, p. 1-10, 2001.
[9] Newman P., Ho K. SLAM-loop closing with visually salient features // IEEE Proc. of International Conference on Robotics and Automation, p. 635-642, 2005.
[10] Paalanen P., Kamarainen J.K., Kalviainen H. Image based quantitative mosaic evaluation with artificial video // Scandinavian Conference on Image Analysis, Springer (Berlin, Heidelberg), p. 470-479, 2009.
