Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,931

ALGORITHM FOR FINDING CORRESPONDENCES IN IMAGES BASED ON ENERGY MINIMIZATION APPROACH

Tuzhilkin A.Yu. 1 Zakharov A.A. 1 Yashkov V.S. 1
1 Murom Institute (Branch) of Vladimir State University named after Alexander G. and Nicholas G. Stoletovs
В работе рассматривается алгоритм нахождения плотных стереосоответствий на изображениях с использованием подхода минимизации энергии. Алгоритм может применяться для реконструкции трехмерных сцен, определения положения и ориентации объектов в пространстве. Алгоритм основан на полигональном разбиении изображения. Сегментация изображения осуществляется на основе спектральной теории графов. Основная идея алгоритма состоит в нахождении диспаритета между регионами на основе метода суммы квадратов разностей. Это позволяет получить более гладкую карту глубины по сравнению с точечными методами. Применяется метод минимизации энергии. Функция энергии представляет сумму компонентов: меры цветового сходства примитивов, меры связности примитивов, меры перекрытия областей. Для минимизации энергии задаются исходные параметры наблюдаемой сцены. Параметры сцены итеративно оптимизируются. Приведены результаты работы алгоритма на тестовых изображениях.
Dense stereo correspondence algorithm for finding the images using the energy minimization approach is considered in the work. The algorithm can be used for the reconstruction of three-dimensional scenes, determining the position and orientation of objects in space. The algorithm is based on the polygon partition image. Image segmentation is based on spectral graph theory. The main idea of the algorithm is to find the disparity between regions on the basis of the sum of squares of the differences. This enables to obtain more smooth depth map compared with point methods. Energy minimization method is used. The energy function is the sum of the components: color similarity measures primitives, measures of connectivity primitives, measures the overlap regions. The initial parameters of the observed scene are set to minimize energy. Scene parameters iteratively optimized. The results of the algorithm on test images are shown.
energy minimization
stereo correspondence
Image processing

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

Рис. 1. Эпиполярная конфигурация нормальной пары изображений

Эпиполярной плоскостью называется плоскость, которой принадлежит трехмерная точка , оптические центры двух камер и , две проекции и точки на плоскости изображений. Эпиполярными прямыми называются две прямые и , которые являются прямыми пересечения эпиполярной плоскости с двумя плоскостями изображений и . Расстояние между оптическими центрами камер называется базой .

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

Рис. 2. Схема измерения диспаритета

Из рис. 2 можно получить следующие соотношения.

;

,

где , – значения координат точки на левом и правом изображениях;

– фокусное расстояние (расстояние от оптического центра до плоскости изображения);

– координата точки ;

– координата точки ;

– расстояние между оптическими центрами камер (база).

Из полученных соотношений можно вычислить значение диспаритета :

.

Задача вычисления диспаритета осложняется присутствующими на изображениях шумами и бликами, наличием слаботекстурированных областей, взаимными перекрытиями объектов, резкими перепадами глубины в сценах. Кроме того, для приложений реального времени необходимо обеспечить компромисс между качеством нахождения стереосоответствий и вычислительной сложностью алгоритмов.

Обзор методов стереосопоставления

Выделяют методы нахождения плотного и разреженного стереосоответствий [1, 6]. Методы нахождения плотных соответствий вычисляют диспаритет для каждой точки изображения. Методы нахождения разреженных соответствий вычисляют диспаритет только между выделенными особенностями изображений.

Стереоалгоритмы бывают локальными и глобальными [6]. Локальные алгоритмы используют для вычисления диспаритета в каждой точке информацию о части пикселей изображения, находящихся в окрестности данной точки. Глобальные алгоритмы стремятся найти решение, при котором каждый пиксель изображения оказывает влияние на решение во всех остальных пикселях. Локальные алгоритмы требуют меньше вычислительных затрат. Однако, глобальные алгоритмы формируют более точные дальнометрические данные. Существуют также полуглобальные методы, которым присущи особенности локальных и глобальных методов [3].

Успехи в области стереосопоставления были достигнуты с развитием таких методов оптимизации, как разрезы на графах [5] и распространение доверия [4]. Основным недостатком этих методов являются высокие вычислительные затраты.

Для дальнейшего совершенствования методов исследователи уделяли больше внимания проблемам перекрытий и слаботекстурированных областей. В последнее время стали популярны методы определения соответствий на основе регионов [7]. Эти методы позволяют получить хорошие результаты, когда поверхности объектов имеют однородную закраску.

В представленном алгоритме предлагается использовать информацию о сегментах изображения для вычисления значений диспаритетов. Определение диспаритета используется для каждого региона в отдельности на основе метода суммы квадратов разностей.

Функция энергии

Цель плотной реконструкции по стереоизображениям состоит в восстановлении глубины каждого пикселя. Предполагается, что стереопара ректифицирована. Каждому диспаритету точки сопоставима функция энергии, которая количественно описывает степень соответствия. Цель алгоритма – минимизировать значение функции для нахождения наилучшего соответствия. Функцию энергии -ого региона определим следующим образом:

,

где – штраф за несоответствие цветовых свойств сопоставляемых пикселей;

– штраф за несоответствие свойств соседних пикселей изображения диспаритета (разрыв диспаритета). Обычно к таким областям относятся участки изображения, для которых ошибочно найдены значения диспаритета.

– штраф за перекрытие области изображения. Это участки изображения, для которых не найдены соответствия на стереопарах.

Составляющая функционала энергии определяется на основе метода суммы квадратов разностей (SSD- Sum of Squared Differences) для каждого региона:

,

где – значение диспаритета между соответствующими пикселями правого и левого изображений;

, – яркости пикселей правого и левого изображений с координатами и .

Составляющая функционала энергии определяется следующим образом:

где – множество граничных пикселей текущего региона;

– множество соседних пикселей c приграничными пикселями региона. Пиксели и – два 4-связанных пикселя на правом изображении;

и – значения диспаритета для пикселей и ;

– константа штрафа за несоответствие свойств соседних пикселей.

Составляющая функционала энергии определяется следующим образом:

где – множество пикселей текущего региона;

– значение диспаритета в пикселе ;

– максимальное значение диспаритета на всем диапазоне проверяемых значений;

– константа штрафа за перекрытие областей изображения.

Алгоритм нахождения стереосоответствий

Шаг 1. Выполнение сегментации изображения на основе спектральной теории графов [2].

Шаг 2. Вычисление значения диспаритета каждого региона на основе SSD-алгоритма. Определение пикселей региона осуществляется на основе четырехсвязной заливки областей. Формируется изображение, интенсивность которого в каждой точке представляет собой значения диспаритета.

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

Результаты работы алгоритма

Для оценки полученных результатов были использованы тестовые изображения (рис .3). Время работы программы в среде MATLAB на компьютере c процессором Pentium T2390 и оперативной памятью 2 Gb составило 28 с.

Рис. 3. Тестовые стереоизображения

В результате сегментации правого снимка тестовой стереопары было получено изображение_(рис. 4).

Рис. 4. Сегментация изображения на основе спектральной теории графов

 а) ­    б)

Рис. 5. Изображения диспаритета: а) эталонное изображение диспаритета,

б) изображение диспаритета, полученное на основе представленного алгоритма

Заключение

В работе был представлен алгоритм нахождения стереосоответствий на основе минимизации энергии. Алгоритм использует предварительную сегментацию изображения на основе спектральной теории графов. Алгоритм позволяет получать хорошие результаты для слаботекстурированных областей. Недостатком алгоритма является достаточно большое время работы, так как выполняется четырехсвязная заливка областей. Для ускорения работы алгоритма в дальнейшем предлагается использовать построчную заливку.

Работа выполнена при поддержке гранта РФФИ 13-07-97523, задания №2014/13 на выполнение государственных работ в сфере научной деятельности в рамках базовой части государственного задания Минобрнауки России.

Рецензенты:

Жизняков А.Л., д.т.н., профессор, первый зам. директора, МИ (ф) ВлГУ, г. Муром;

Орлов А.А., д.т.н., доцент, зав. кафедрой физики и прикладной математики, МИ (ф) ВлГУ,
г. Муром.