Современные информационные технологии / 3. Программное обеспечение

К.т.н. Колдаев В.Д.

Национальный исследовательский университет «МИЭТ», Россия

Создание панорамных изображений в системах технического зрения

Одной из ключевых проблем при обработке цифровых изображений, заданных дискретными сетками отсчетов, является привязка изображений, которая заключается в установлении соответствия между сопряженными точками двух и более изображений. В системах видеонаблюдения с помощью нескольких камер при наблюдении с различных ракурсов, сшивка по наборам сопряженных точек, находящихся на различных удалениях от камеры, дает принципиально разные результаты. Таким образом, становится очевидной, необходимость в объединение информации поступающих с нескольких камер и создании панорамного изображения. Разработанный алгоритм сшивки изображений в системах видеонаблюдения имеет следующие этапы:

Этап 1. Нахождение особых точек на каждом из кадров, которые статически отличаются от однородного фона изображения (углы, границы предметов или текстур). Локальная особая точка изображения – это точка с характерной окрестностью, которая имеет особые признаки, существенно отличающие ее от основной массы точек. Это означает, что особая точка может быть угловой, изолированной точкой локального максимума (минимума) линии интенсивности, концом линии или точкой на кривой, где кривизна локально максимальна. Каждая точка описывается набором признаков – дескрипторов, инвариантных относительно поворота и изменения масштаба изображения. Дескрипторы могут быть представлены внешними (границей) или внутренними (совокупностью элементов области) характеристиками [1]. Дескрипторы границ включают в себя: сигнатуры (описание границ объектов с помощью одномерной функции); аппроксимацию многоугольниками (число сегментов в многоугольнике равно числу точек границы, так что каждая пара соседних точек определяет сегмент многоугольника); описание скелета области в виде графа, цепные коды. Дескрипторы областей характеризуются: площадью области (число пикселей, содержащихся в пределах ее границы); большой и малой осями области (для определения ориентации объекта); периметром области (длиной ее границы); дескриптором текстуры.

Поиск особой точки подразделяется на две задачи: определение возможного ближайшего элемента и поиск ближайших элементов в заданном диапазоне. Пусть дано дерево tree. Анализируем вершины дерева от корня к его листьям по условию и определяем ближайший элемент с минимальным расстоянием: Алгоритм поиска ближайшего элемента в заданном диапазоне определяется радиусом, который корректируется в ходе анализа:

Этап 2. Расчет преобразований одного из кадров – определение параметров преобразований, переводящих координаты исходного изображения в координаты панорамного (проективного) изображения (рис.1).

Рис.1. Проективное преобразование

Проективное преобразование точки (x, y) записывается следующей системой:

или в матричном виде:

Искажения изображения, возникающие при склейке, являются результатом проективного преобразования точек:

Решением такой системы является бесконечно множество кортежей коэффициентов (матриц преобразования). Приняв c=1, можно принудительно решить систему линейных уравнений и получить необходимую матрицу трансформации. Возможны случаи, когда две различные матрицы задают одно и то же преобразование:

и .

Этап 3. При создании результирующего изображения один из кадров переносится на результирующее изображение, для второго изображения на основе матрицы трансформации (попиксельно) вычисляется координата перемещения пикселя. Если кадр был подвергнут растяжению, по какой-либо оси, то появятся разрывы в перенесенном изображении. В этом случае значения этих пикселей можно заполнить с помощью билинейной интерполяции [2].

Существуют несколько алгоритмов позволяющих находить особые точки и создавать дескрипторы инвариантные повороту и масштабу: SURF, SIFT, BLOB, FAST, MSER [1,2].

Алгоритм SURF основан на матрице Гессе – квадратной матрице, образованной вторыми частными производными функции. Детерминант матрицы Гессе (гессиан) достигает экстремума в точках максимального изменения градиента яркости. Он хорошо детектирует пятна, углы и края линий. Гессиан инвариантен относительно вращения, но не инвариантен масштабу, поэтому алгоритм SURF использует разномасштабные фильтры для нахождения гессианов. Для каждой ключевой точки считается направление максимального изменения яркости (градиент) и масштаб, взятый из масштабного коэффициента матрицы Гессе. Градиент в точке вычисляется с помощью фильтров Хаара. Матрица Гессе для двумерной функции и ее детерминант определяется следующим образом [3]:

Значение гессиана используется для нахождения локального минимума или максимума яркости изображения. На рис.2 показано, что особые точки (очерчены кругами) представляют собой локальные экстремумы яркости изображения.

Рис. 2 Выделение особых точек изображения

Элементы матрицы Гессе вычисляются как свертка (сумма произведений) пикселей изображения и элементов фильтров. Обычно алгоритм SURF использует бинаризированную аппроксимацию Лапласиана гауссиан (рис.3).

Рис. 3. Фильтры, используемые для нахождения матрицы Гессе

Белые области соответствуют значению +1, черные -2, серые – нулевые. Этот фильтр более устойчив к вращению, и его можно эффективно вычислить с помощью интегральной матрицы. Таким образом, в алгоритме SURF, гессиан вычисляется по формуле: где D_xx, D_yy, D_xy – свертки по фильтрам; коэффициент 0,9 корректирует приближенный характер вычислений.

Алгоритм SIFT обнаруживает и описывает локальные особенности изображения. При определении особых точек осуществляется построение пирамиды гауссианов и разностей гауссианов (DoG). Изображение размытое гауссовым фильтром (гауссиан) представляется следующим образом: где L – значение гауссиана в точке с координатами (x, y); – радиус размытия; G – гауссово ядро; I – исходное изображение; «*» – операция свертки.

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

Масштабируемым пространством изображения является набор всевозможных, сглаженных некоторым фильтром, версий исходного изображения. Гауссово масштабируемое пространство является линейным, инвариантным относительно сдвигов, вращений, масштаба, не смещающим локальные экстремумы, и обладает свойством полугрупп. Различная степень размытия изображения гауссовым фильтром может быть принята за исходное изображение, взятое в некотором масштабе. В каждом изображении из пирамиды DoG находятся точки локального экстремума. Каждая точка текущего изображения DoG сравнивается с ее восемью соседями и с девятью соседями в DoG, расположенными на уровнях выше и ниже в пирамиде. Если эта точка больше (меньше) всех соседей, то она принимается за точку локального экстремума [2,3].

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

В алгоритме SIFT дескриптором является вектор. Как и направление ключевой точки, дескриптор вычисляется на гауссиане, ближайшем по масштабу к ключевой точке, и исходя из градиентов в некотором окне ключевой точки. Перед вычислением дескриптора это окно поворачивают на угол направления ключевой точки, чем и достигается инвариантность относительно поворота.

Исследование реальных кадров показало, что на изображении размером 1024×768 пикселей может быть найдено несколько тысяч особых точек, которые будут обрабатываться от 3 до 8 с., что не позволяет проводить обработку изображения в реальном времени. После изменения разрешения до 640×480 пикселей, было определено среднее арифметическое времени работы алгоритмов: SURF – 0,03 с.; SIFT – 0,06 c. Расчеты показали, что часть особых точек на исходном и преобразованном изображениях совпадают: 40,7 % для алгоритма SUFR и 18,8 % для алгоритма SIFT. Совпавшими считались точки, координаты которых отличались не более чем на два пикселя. Реализованный программный модуль позволяет получать результат сшивания кадров изображений в среднем за время равное 65 мс.

Литература

1. Колдаев В.Д. Методологические подходы к контурной сегментации изображений в автоматизированных производственных системах [Текст] / Л.Г. Гагарина, В.Д. Колдаев // – М.: Научно-технический журнал «Известия высших учебных заведений. Электроника». – 2014. – №4(108).– С.64-72.

2. Колдаев В.Д. Эвристические и квазитопологические алгоритмы контурной сегментации изображений [Текст] / В.Д. Колдаев // – М.: Научно-технический журнал «Известия высших учебных заведений. Электроника». – №6, 2008. – С.41-45.

3. Форсайт Д. Компьютерное зрение. Современный подход [Текст] / Д. Форсайт, Ж. Понс. – М.: Вильямс, 2004. – 928 с.