Нахождение соответствий на изображениях является актуальной задачей в таких областях, как реконструкция трехмерных сцен, автономная навигация, визуальный контроль и т.д. Для этого часто используются стереоизображения. Два изображения одной области пространства, полученные с двух различных точек зрения, называются стереоскопической парой снимков (стереопарой). На основе вычисленных соответствий по стереопаре можно определить трехмерные координаты сцены. Для вычислений используется понятие эпиполярной конфигурации. В простейшем случае две одинаковые плоскости изображений параллельны базе стереосистемы (рис. 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 на выполнение государственных работ в сфере научной деятельности в рамках базовой части государственного задания Минобрнауки России.
Рецензенты:
Жизняков А.Л., д.т.н., профессор, первый зам. директора, МИ (ф) ВлГУ, г. Муром;
Орлов А.А., д.т.н., доцент, зав. кафедрой физики и прикладной математики, МИ (ф) ВлГУ,
г. Муром.