ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 2, с. 68-79
РАСПОЗНАВАНИЕ ОБРАЗОВ И ОБРАБОТКА ИЗОБРАЖЕНИЙ
УДК 519.722
ПЛОТНАЯ РЕКОНСТРУКЦИЯ РЕЛЬЕФА МЕСТНОСТИ НА ОСНОВЕ МОДИФИЦИРОВАННОГО АЛГОРИТМА ПОЛУГЛОБАЛЬНОГО СТЕРЕООТОЖДЕСТВЛЕНИЯ
© 2014 г. В. А. Горбачев
Москва, ФГУП ГОСНИИАС Поступила в редакцию 12.11.13 г.
Представлена технология создания трехмерных моделей местности по данным цифровых аэрофотоснимков на основе алгоритма полуглобального стереоотождествления. Показан способ иерархического применения алгоритма. Предложен ряд модификаций и усовершенствований на всех этапах работы алгоритма, таких, как учет градиентной и цветовой информации на изображении, интерполяция метрики сравнения точек для увеличения разрешающей способности алгоритма и повышения устойчивости к небольшим искажениям входных данных, фильтрация стоимости соответствия и постобработка получаемой карты диспарат-ности билатеральным фильтром. Продемонстрированы результаты применения алгоритма и преимущества модификаций на примере обработки пар аэрофотоснимков высокого разрешения.
DOI: 10.7868/S0002338814020103
Введение. В настоящее время широкое распространение получили геоинформационные системы, системы навигации и виртуальные тренажеры, работающие с трехмерными цифровыми моделями реально существующих объектов или местности. Для создания трехмерных моделей объектов для таких систем могут применяться радары, лазерные сканеры либо системы сте-реозрения (стереореконструкции). При этом последние гораздо более дешевы, имеют достаточно большое разрешение и являются пассивными устройствами, что важно в ряде приложений. Кроме того, системы стереозрения, работающие в реальном времени, могут быть установлены на беспилотных летательных аппаратах для предоставления пространственной информации бортовой системе управления. Подобные системы на основе обработки данных видеокамер, используемые для получения текущей пространственной информации о дорожной обстановке, уже устанавливаются на некоторые серийно выпускаемые автомобили [1].
Алгоритм полуглобального стереоотождествления (Semi-global matching, SGM) служит для решения описанных выше задач и на сегодняшний день является одним из наиболее передовых методов стереореконструкции. Он сочетает в себе высокое качество получаемой поверхности, свойственное глобальным методам, и высокую скорость обработки, сопоставимую с локальными методами. При этом метод подходит как для автоматической реконструкции рельефа, так и для сложных городских сцен, так как он способен воссоздавать резкие края и тонкие детали объектов. Возможна высокоэффективная реализации алгоритма SGM на графическом процессоре (graphics processing unit, GPU) для обработки данных в реальном времени [2].
1. Обзор методов стереоотождествления. Методы восстановления поверхности основаны на том, что при наличии двух различных изображений одной и той же точки в пространстве и информации об ориентации камер можно восстановить положение этой точки в пространстве. Таким образом, для решения задачи стереореконструкции необходимо произвести поиск на паре изображений точек, являющихся образами одной и той же точки объектного пространства. Иначе говоря, требуется решить задачу стереоотождествления.
Традиционно используемые для решения этой задачи локальные методы стереоотождествле-ния для отдельных точек изображения производят поиск соответствующих им точек на другом изображении. В качестве соответствующей выбирается точка, окрестность которой (или ее характеристики) наиболее похожа на окрестность исходной точки. При этом, как правило, используется неявное предположение об одинаковой диспаратности в окрестности точки, которое не выполняется в областях резкого перепада глубины. Кроме того, точки рассматриваются незави-
"1 1
1 1 1
т п
1
L
а б в
\ /
\ /
/
/ Г у \
/ \
где Рис. 1. Виды графов зависимостей для приближенных методов стереоотождествления
симо друг от друга, взаимное расположение точек может учитываться только на этапе отбраковки соответствий. Вследствие этого для точек из слаботекстурированных областей (либо областей с повторяющейся текстурой) построить верное отождествление с помощью локальных методов невозможно.
Методы глобального стереоотождествления ставят задачу нахождения оптимального соответствия для всех пикселей изображения совместно, учитывая взаимосвязи между ними. Ясно, что отдельные пиксели могут не обладать уникальной отличительной особенностью, однако, рассматривая каждый пиксель во взаимосвязи со своими соседями и другими пикселями изображения, можно построить гораздо более точную и подробную, чем при использовании локальных методов, карту соответствия.
Если значение диспаратности D(p) для пикселя p изображения представить как его метку, то задачу глобального стереоотождествления можно в общем виде сформулировать как задачу построения оптимальной разметки дискретного двумерного множества пикселей изображения, минимизирующей функционал энергии соответствия изображений:
E(D()) = У С(p,D(p)) + У У W(D(p),D(q)) ^ min. (1.1)
DeD
pel pel qeN(p)
Функционал энергии соответствия (1.1) имеет вид суммы унарных и бинарных потенциалов. Унарный потенциал диспаратности С (p, D(p)) описывает стоимость отождествления пикселя р на исходном изображении и пикселя на другом изображении с диспаратностью D(p). Бинарный потенциал диспаратности
У W (D(p), D(q))
qeN (p)
описывает штраф за рассогласование диспаратности D(p) пикселя p и диспаратностей D(q) его соседей из окрестности N(p). Суммирование потенциалов производится по всем пикселям p из множества пикселей I рассматриваемого изображения. Перед решением задачи минимизации (1.1) задается диапазон диспаратностей (Dmin, Dmax), в котором производится поиск. Карта диспаратности считается допустимой (D е 2), если все значения диспаратностей этой карты лежат в выбранном диапазоне.
Учет только первого слагаемого в (1.1) соответствует принципу работы локальных методов, когда минимизируется суммарная стоимость индивидуальных соответствий. Второе слагаемое отличает глобальные от локальных методов, вводя учет взаимосвязей между пикселями. Как правило, оно налагает условие гладкости решения, штрафуя присвоение сильно различающихся значений диспаратности соседним пикселям.
Форма окрестности N(p) в (1.1) определяет отношение соседства между пикселями изображения и формирует граф зависимостей, вершинами в котором являются все пиксели, а ребра соответствуют отношению соседства пикселей. Вид этого графа оказывает определяющее влияние на сложность решения задачи (1.1). Оказывается, что точное решение задачи минимизации функционала (1.1) для четырехсвязного отношения соседства (рис. 1, а) оказывается NP-трудной за-
дачей [3], т.е. вычислительная сложность такой задачи экспоненциально зависит от размера входных данных. Такая трудоемкость неприемлема для практической реализации.
Для решения задачи оптимизации (1.1) предложен ряд методов, например на основе разреза графов (Graph Cut) и распространения доверия (Belief propagation), характеризующихся высокой вычислительной сложностью. Другие, более быстрые приближенные методы основаны на том, что вместо графа, отвечающего четырехсвязному отношению соседства пикселей изображения, предлагается выбирать его подграф или другой граф, не содержащий циклов. Самым простым из таких методов является метод построчной оптимизации (рис. 1, б). В этом методе отбрасывается связь между соседними строчками пикселей, что максимально упрощает вычисления, но приводит к сильному рассогласованию результатов отождествления строк. В [4] предлагается строить минимальное покрывающее дерево с помощью отбрасывания ребер между пикселями с наиболее различающимися значениями яркости (рис. 1, в), в [5, 6] — выбирать в каждой точке дерево решетчатой (рис. 1, г, д) или звездчатой формы (рис. 1, е), имеющего центром рассматриваемую точку. После выбора такого подграфа для каждой точки вычисляется диспаратность, минимизирующая (1.1) на построенном дереве. Так как дерево не содержит циклов, то искать на нем минимум функционала энергии можно эффективно, например с помощью метода динамического программирования. Оптимизация в последних двух методах производится независимо для каждого пикселя. Из-за учета большого числа связей с другими пикселями методы сохраняют достаточно высокую точность. Для деревьев на рис. 1, г-е предложены алгоритмы, строящие карту диспаратности за время O(WHB), где W, H — размеры изображения, B = Dmax - Dmin — ширина диапазона поиска диспаратности.
2. Алгоритм SGM. Наиболее удобным и известным среди приближенных методов оптимизации энергии соответствия изображений (1.1) является алгоритм SGM, предложенный Хир-шмюллером в [6]. В нем используются звездчатый граф зависимостей (рис. 1, е) и двухступенчатая функция штрафа за негладкость. За отклонение диспаратности между соседними точками на единицу вводится штраф P1, за отклонение на большие значения — P2. Функционал энергии, зависящий от карты диспаратности D, в этом случае имеет вид
E (D()) = £ С (p, D(p)) + £ J £ P [|D(p) - D(q)| = 1] + £ p Ql) - D(q)| > 1] L (2.1)
pel pel [qeN(p) qeN(p) J
где C — функция стоимости соответствия точки p = (x, y) на одном снимке и смещенной точки p' = (x + D(p), y) на другом, N(p) — окрестность точки p. Здесь и далее квадратными скобками [А] обозначена следующая операция преобразования булевой переменной А в число:
[A] J1' A = true, (О, A = false.
Выбор графа зависимостей простой формы и не содержащего циклов позволяет от двухмерной оптимизации перейти к одномерной оптимизации вдоль восьми лучей, показанных на рис. 1, е. Лучи задаются направлениями r смещения к одному из восьми пикселей, соседних с данным. Так, r1 = (1,0), r2 = (1,1), ..., r8 = (1,-1). Одномерную оптимизацию можно эффективно произвести с помощью метода динамического программирования. Для этого рекурсивно вычисляются частичные функции стоимости Lr вдоль направлений r:
Lr(p, d) = C(p, d) - min Lr(p - r, k) +
k (2.2) + min{Lr(p - r,d),Lr(p - r,d - 1) + P1,Lr(p - r,d + 1) + P1,m
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.