Разработка алгоритмов высокодетального моделирования объектов на основе анализа цифровых изображений тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Горбачев, Вадим Александрович

• Горбачев, Вадим Александрович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Горбачев, Вадим Александрович

Содержание

Введение

Глава 1. Локальные методы отождествления контурных особенностей изображения

1.1. Обзор методов отождествления контуров

1.2. Отождествление замкнутых контуров

1.2.1. Построение синтезированных замкнутых контуров

1.2.3. Форма представления контуров

1.2.4. Отождествление контуров методом динамического программирования

1.2.5. Устранение ошибок отождествления

1.2.6. Привязка точек на основе отождествлённых контуров

1.2.7. Оценка точности привязки точек на основе контуров

1.3. Отождествление точечных особенностей

1.3.1. Задача построения ЦМП

1.3.2. Исходные данные для построения ЦМП

1.3.3. Общая характеристика метода локального отождествления точек интереса

1.3.4. Недостатки метода локального стереоотождествления точечных особенностей

1.4. Отождествление контурных особенностей

1.4.1. Выделение контуров на изображениях

1.4.2. Формирование элементарных отрезков

1.4.3. Поиск возможных соответствий для концевых точек элементарных отрезков

1.4.4. Формирование списков кандидатов для элементарных отрезков

1.4.5. Выбор лучших соответствий для элементарных отрезков

1.4.6. Разрешение коллизий при неоднозначном соответствии

1.5. Метод вероятностной релаксации

1.5.1. Основы метода вероятностной релаксации

1.5.2. Определение набора соседей для объекта

1.5.3. Вычисление коэффициента взаимного влияния

1.5.4. Использование контуров в процедуре глобального

стереоотождествления

1.6. Выводы

Глава 2. Глобальные методы отождествления точек изображения

2.1. Обзор методов стереоотождествления

2.2. Обзор моделей связей

2.3. Алгоритм полуглобального стереоотождествления (БОМ)

2.4. Модификации метода полуглобального отождествления

2.4.1. Модификация метрики сравнения

2.4.2. Иерархическая обработка

2.4.3. Использование градиентной информации

2.4.4. Субпиксельность в алгоритме 8вМ

2.4.5. Устранение влияния ошибок нормализации

2.4.6. Фильтрация матрицы стоимости

2.4.7. Сглаживание карты диспаратности

2.4.8. Блочная обработка

2.5. Плотное многолучевое отождествление изображений

2.5.1. Проблема слепых зон

2.5.2. Полуглобальная оптимизация при многолучевом отождествлении

2.5.3. Оценка оптимального перекрытия

2.6. Выводы

Глава 3. Модельно-ориентированный метод построения трёхмерных моделей зданий

3.1. Постановка задачи и исходные данные

3.2. Построение геометрической модели объекта

3.2.1 Локализация элементов объекта на изображениях

3.2.2 Локализация положения элементов объекта в пространстве

3.2.3 Уточнение модели объекта

3.3. Поиск элементов фасада по цифровому эталону

3.3.1 Использование комплексного эталона

3.3.2 Инвариантный к масштабу поиск объектов

3.4. Текстурирование

3.5. Выводы

Заключение

Список литературы

Приложение. Основные сведения о фотограмметрических методах

1 .Математическая модель камеры

2. Эпиполярная геометрия и ректификация

3. Стереореконструкция

4. Проблема стереоотождествления

Введение диссертации (часть автореферата) на тему «Разработка алгоритмов высокодетального моделирования объектов на основе анализа цифровых изображений»

Введение

Актуальность темы. В настоящее время широкое распространение получили геоинформационные системы, системы навигации и виртуальные тренажеры, работающие с трехмерными цифровыми моделями реально существующих объектов или местности. Кроме того, системы стереозрения [1], работающие в реальном времени, могут быть установлены на беспилотных летательных аппаратах для предоставления пространственной информации бортовой системе управления. Подобные системы на основе обработки данных видеокамер, используемые для получения текущей пространственной информации о дорожной обстановке, уже устанавливаются на некоторые серийно выпускаемые автомобили. Для создания трехмерных моделей объектов для таких систем могут применяться радары, лазерные сканеры либо системы стереозрения (стереореконструкции), получающие информацию от цифровых снимков сцены. При этом последние гораздо более дешевы, более компактны, однако имеют достаточно большую разрешающую способность и являются пассивными устройствами, что важно в ряде приложений. Камеры могут быть установлены на наземные платформы, самолёты и БПЛА, космические аппараты. Построение цифровой модели поверхности (ЦМП) на основе анализа изображений является бурно развивающейся темой, и хотя созданы различные алгоритмы построения ЦМП, задача построения трёхмерных моделей по цифровым фотоснимкам далека от окончательного решения.

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

1. Разработка робастного метода привязки изображений на основе отождествления замкнутых контуров изображений, инвариантного к масштабированию и повороту изображений.

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

3. Разработка алгоритма плотного стереоотождествления точек изображений для увеличения точности и ускорения построения ЦМП по аэрофотоснимкам высокого разрешения.

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

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

Научная новизна. В диссертационной работе получены следующие результаты:

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

2. Создан оригинальный метод отождествления контуров и устранения неоднозначностей отождествления на основе поиска кратчайшего пути на графах, в комбинации с алгоритмом вероятностной релаксации повышающий точность и детальность построения ЦМП в среднем на 20%.

3. Разработан модифицированный алгоритм полуглобальной оптимизации энергии соответствия для плотного отождествления точек изображений. Применены иерархическая обработка, использование градиентной информации, интерполяция метрики, постобработка кроссбилатеральным фильтром, в целом повышающие точность на 20-30% (по сравнению с базовым алгоритмом БвМ) и разрешающую способность алгоритма вдвое, увеличивающие устойчивость к искажениям во входных данных и снижающие количество выбросов.

4. Предложен новый метод многолучевого отождествления на основе полу глобальной оптимизации энергии соответствия, ускоряющий процесс плотного отождествления трёх и более изображений для построения ЦМП.

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

Практическая ценность. Созданные в диссертационной работе методы и алгоритмы позволяют существенно повысить точность и детальность получаемых ЦМП. Увеличение точности моделей на разных данных может достигать 20%. Применение разработанных методов плотного отождествления позволяет восстанавливать модели зданий с резкими краями, что невозможно при использовании традиционных (корреляционных) методов. Разработанное на базе методов программное обеспечение позволяет производить автоматическое построение высокодетальных ЦМП по наборам аэрофотоснимков высокого разрешения. Полученные высокодетальные модели могут быть использованы для наполнения ГИС, при подготовке полётных зданий летательных объектов, а в перспективе для задач навигации мобильных автономных объектов.

Методы исследования. При решении поставленных задач использовались методы цифровой обработки изображений, теории вероятностей, теории графов, дискретной оптимизации. Для практической реализации алгоритмов применялись численные методы оптимизации и методы объектно-ориентированного программирования.

Реализация и внедрение. Разработанные в диссертации методы и алгоритмы были реализованы в виде программных компонент объёмом порядка 30000 строк кода, имеющих высокомодульную структуру. Компоненты были включены в состав цифрового фотограмметрического комплекса 28расе, и использовались при проведении ПИР и ОКР ГосНИИАС по проведению

дистанционного зондирования и построения трёхмерных моделей рельефа и местности по данным аэрофотосъемки. Работоспособность и качество работы методов были протестированы на больших объёмах фотографических данных, располагаемых ГосНИИАС.

Апробация работы. Результаты работы были доложены на ряде конференций: Всероссийская научно-техническая конференция «Моделирование авиационных систем» (Москва, 2011), Всероссийская научно-техническая конференция "Навигация, наведение и управление летательными аппаратами" (Москва-Раменское, 2012), V Международный межотраслевой научно-технический форум «Молодёжь и будущее авиации и космонавтики» (Москва, 2013), на конкурсе «УМНИК» на лучшую предпринимательскую инициативу в научно-технической сфере в рамках XIV Всероссийской выставки научно-технического творчества молодежи (Москва, 2014).

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

Публикации. По теме диссертации опубликовано 6 работ, в том числе 4 статьи в журналах, рекомендованных ВАК Минобрнауки РФ.

Личный вклад соискателя в работы с соавторами включает все результаты, вынесенные на защиту. Ряд вспомогательных операций обработки изображений, необходимых для демонстрации работы разработанных методов, был произведён с помощью ПО и методик, разработанных в ФГУП ГосНИИАС.

Структура диссертации. Диссертация общим объёмом 135 с. состоит из введения, трёх глав, приложения, содержит 85 рисунков, 2 таблицы и перечень используемой научно-технической литературы из 55 наименований. Основные положения, выносимые на защиту: 1. Метод привязки изображений на основе отождествления замкнутых контуров и процедуры голосования.

2. Метод отождествления контуров и устранения неоднозначностей отождествления на основе поиска кратчайшего пути на графах.

3. Модифицированный алгоритм полу глобального отождествления.

4. Метод многолучевого отождествления на основе полуглобальной оптимизации энергии соответствия.

5. Методика автоматического построения трёхмерных моделей зданий на основе комплексирования данных наземной съёмки и дополнительной опорной информации.

Глава 1.

Локальные методы отождествления контурных особенностей изображения

Отождествление изображений, или привязка фрагментов, представляет собой важную задачу, возникающую во многих приложениях машинного зрения. Экологический мониторинг, анализ лесных ресурсов, мониторинг городских территорий, автоматический поиск данных дистанционного зондирования в больших базах данных - только некоторые из приложений, при решении которых возникает задача распознавания и привязки фрагмента в пределах большого изображения. Существенные перемены в применении методов такого типа связаны с разработкой и реализацией нового поколения устройств, беспилотных летательных аппаратов и наземных автономных роботов с элементами искусственного интеллекта, системы управления которых используют для ориентирования в окружающей среде алгоритмы распознавания с последующим определением координат реальных объектов. Этим объясняется возросшая актуальность разработки специализированных алгоритмов для обработки данных различных видов съемки, включая, в первую очередь, авиационную и космическую. По сложившейся к настоящему времени классификации выделяют алгоритмы низкого, среднего и высокого уровней [2], причем два последних типа используют для распознавания характерных особенностей изображения {FBM, feature based methods), такие, как точки, контуры или области [3]. В отличие от низкоуровневых, площадных (ABM, area-based methods) FBM-методы обладают более высокой устойчивостью в отношении условий регистрации изображений. Это свойство позволяет более успешно использовать FBM-методы в ситуациях, когда условия освещения или геометрия съемки меняются или точная информация о масштабе и ориентации изображений отсутствует. С другой стороны, они, естественно, являются более наукоемкими и требуют более высоких вычислительных затрат.

1.1. Обзор методов отождествления контуров.

Среди всех типов особенностей, используемых при отождествлении, контуры особенно важны по трём причинам: они обладают высокой устойчивостью по отношению к разным видам геометрических и фотометрических искажений и, с другой стороны, являются естественными наиболее различимыми визуально границами на изображении для большинства объектов сцены, представляющих реальный интерес. Кроме того, контуры обладают большей уникальностью, чем точечные особенности в силу более сложной структуры. Безусловно, разными авторами предлагались подходы к решению задачи отождествления контуров [2, 3], но нетрудно видеть, что все они имеют весьма общий характер и едва ли предназначены для работы с реальными изображениями сцен произвольного содержания. Тематический поиск показывает, что статей, посвященных применению точек интереса, существует десятки, а, возможно, и сотни, в то время как тема применения контуров для анализа изображений практически не представлена в публикациях. Учитывая безусловную актуальность темы, это должно означать, что к настоящему времени данная задача еще далека от своего окончательного решения.

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

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

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

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

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

При анализе изображений под контурами, как правило, подразумевают линии перепада яркости. Точки таких линии можно детектировать с помощью дискретных аналогов оператора производной (например Прюит, Робертса, Собела) [6]. Чтобы собрать контур из контурных точек, используется предположение о том, что нормаль к контуру направлена вдоль направления

градиента в точке. Для получения удобных для дальнейшего использования тонких (толщиной в 1 пиксель) контуров применяется детектор краёв Канни [7].

Вид представления контура существенно влияет на возможности его анализа и отождествления. После выделения контуры представлены в виде цепного кода, либо списком входящих в него точек. Такое представление неудобно для дальнейшего анализа, так как положение отдельных пикселей контура сильно зависит от изменений в ракурсе, освещении или зашумлённости изображения. Вследствие этого предлагаются различные виды представлений для контуров. Одно из старейших способов представления - это представление контура в виде коэффициентов Фурье. Базисом в таком случае выступают, например, правильные многоугольники [8]. Аналогично, можно составить описание контура с помощью вейвлет-преобразования [9]. Однако такие способы представления подходят только для замкнутых контуров.

Другим способом представления является представление контура в виде кривой, и её последующей параметризации. Рассматривается представление в виде (а,р) - дальность в зависимости от центра, (s,к) - кривизны в зависимости от длины дуги, (s,i¡/) - угла излома в зависимости от длины дуги контура [2]. На практике удобнее рассматривать контур не как гладкую кривую, а как ломаную. Тогда можно использовать дискретные аналоги указанных выше характеристик. Вместо кривизны удобно использовать так называемую ^-величину изгиба {к-slope valué). Она представляет собой угол излома при вершине ломаной по отношению к точкам, отстоящим от неё на к вершин [10].

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

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

непрерывные представления, и представления в виде коэффициентов Фурье или вейвлет-преобразования.

Использование при отождествлении контуров дополнительной информации об ориентировании изображения, а именно использование эпиполярного ограничения предложено в [11].

Различные контуры изображения можно разделить на два существенно различающихся типа - замкнутые и незамкнутые. Для поиска соответствий контуров каждого типа применяются различные методы. Их отдельному рассмотрению посвящены две части данной главы. Сначала будет представлен метод отождествления замкнутых контуров, как более робастный и геометрически инвариантный, затем метод отождествления незамкнутых контуров, который в своей работе использует параметры ориентирования снимков. Необходимые параметры ориентирования можно получить, используя, например, результаты работы первого подхода.

1.2. Отождествление замкнутых контуров

1.2.1. Построение синтезированных замкнутых контуров.

Имея в виду трудности, с которыми приходится сталкиваться при выделении контуров на реальных изображениях, в [12] был разработан подход, в котором для выделения контуров используется информация, полученная как от контуров, так и от областей.

1.2.1.1. Общая характеристика метода. Лилейные особенности могут представлять собой контуры объектов, береговой линии, рек и дорог, изображенных на аэрофотоснимках. Стандартные методы выделения контуров, такие, как детектор Канни или детектор на основе оператора Марра [13], часто используются для выделения линейных особенностей. Однако на реальных изображениях эти методы, как правило, не дают контуров требуемого качества из-за наличия разрывов и заметных отличий в условиях освещения.

Области на изображениях могут представлять любые высококонтрастные объекты определенного размера, такие, как пруды, озера, здания, парковки машин или просто тени. Как основной критерий области рассматривается замкнутость ее границы. Часто области описываются своим центром тяжести, который инвариантен к вращению, масштабированию, искажению, а также к шумам и определенным изменениям фотометрического уровня. Области выделяются посредством методов сегментации [14]. Точность сегментации может существенно влиять на результат последующего позиционирования. Многие исследователи приложили значительные усилия, чтобы разработать технику сегментации, слабо чувствительную к условиям фотосъемки [4].

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

Рис. 4. Изображения исходной стереопары

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

1.2.1.2. Выделение контуров. Для начального выделения контуров использовались оператор Собела [6] и детектор краев Канни [6]. После этого применялись морфологические фильтры для очищения контурного препарата.

Рис. 5. Контуры

Результаты показаны на рис. 5. Данная техника позволяет выделить большое количество контуров, которые, однако, все еще отрывочны и достаточно зашумлены.

1.2.1.3. Сегментация изображений. При разработке алгоритма сегментации был принят за основу подход Ши [15], анализирующий связность изображения как графа на его пикселях. Предложенная здесь модификация заключается в том, что связными в графе считаются не все соседние пикселы, а только те из них, которые являются похожими по выбранному критерию. Тогда задача разрезания графа заменяется задачей выделения связных компонент. Для полутоновых изображений основным признаком сходства пикселей является значение их яркости. Поэтому пиксели считаем похожими, если их яркость отличается не более чем на величину порога L.

Пусть F(x,y) - матрица яркости изображения. Определим соответствующий этой матрице граф связности пикселей G=(V,E) следующим образом: его узлами

будут являться все пикселы изображения У={(х,у)}, а рёбра Е в графе поставим только между соседними пикселями, схожими по яркости:

= (01,У1М*2,У2)) е Е о ^О^у!) -/Ч*2,у2)| < (1.1)

где (хьуО и (х2,у2) - соседние (в смысле 4-связномсти) пиксели, а Ь - выбранный порог. Областью на изображении будем считать множество пикселей, между которыми существует путь в получившемся графе. Или, что тоже самое, областью можно считать множество всех пикселей, связанных с выбранной «затравочной» точкой г путём на графе:

хе V:Зи> = (ере2,...,еДе( еЕ,г = \...к, = (х,ух),ек = {ук,г),у, еУ,г = 1 -к

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

А(г) = -

Рис. 6. Области

Результаты сегментации изображений показаны на рис. 6. Процедура работает крайне быстро, так как задачу выделения связных компонент на графе решает стандартный алгоритм поиска в глубину [16] сложностью

где N - количество пикселей на изображении. Для

выделения границы полученных областей последовательно применяются морфологические операции наращивания и эрозии [6]:

дХ = Х(&В\ХеВ, (1.3)

где В - структурирующий элемент, 0 - операция наращивания, 0 - эрозии, \ -операция вычитания множеств.

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

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

• отбрасывать все замкнутые контуры, если они полностью содержатся внутри некоторой области,

• сливать все области в одну область, если они полностью содержатся внутри замкнутого контура,

• произвести уточнение границ областей, принимая ближайший независимый контур в качестве точного положения границы.

Рис. 7. Сравнение контуров и областей

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

Рис. 8. Уточненные контуры на исходных изображениях

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

1.2.3. Форма представления контуров.

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

Наиболее простым и быстрым методом аппроксимации является кусочно-линейное представление. Построение ломаной производится на основе

классического алгоритма выбора концевых точек Форзена [17]. Процедура дробления в этом алгоритме осуществляется итеративно и продолжается до тех пор, пока максимальное значение отклонения точек контура от аппроксимирующей ломаной больше заданного порога. Точность аппроксимации этого метода определяется величиной порога. Такое представление кривой обладает своими недостатками, но, как показывают результаты, в нашем случае является достаточным.

Для кривых произвольного вида сравнение может осуществляться по одномерному представлению контура в виде кривизны, рассматриваемой как функция дуги кривой [2, 3]. Для ломаной в качестве аналога кривизны принят угол 0 при вершине, вычисляемый по формулам

(х,+1 -х,)(х, - Х,-1)

соз(в) =

БШ(^) -

— — 5

Х(+1 — X

(х,+1 -х,)х(х, -Х,-[)

(1.4)

— X/

.X/ X/—1

в = ^«(бш^)) • агссоз(соз((9)), (1.5)

где X,- - это координаты угловых точек. Тогда функция представления контура принимает вид, изображенный на рис. 9. Такое представление неоднозначно, так как зависит от выбора начальной точки ломаной. Изменение начальной точки влечёт циклический сдвиг отсчётов функции представления. Начальная точка каждой ломаной выбирается на этапе аппроксимации случайным образом и в дальнейшем, должна быть уточнена в процессе отождествления контуров.

5

Рис. 9. Дискретное (5,6) представление контура

Далее для полученного представления контуров в форме (5,9) («длина дуги - угол излома») строится процедура их отождествления. Существенно, что форма контура одного и того же объекта, выделенная на различных изображениях, может заметно различаться. Изменение условий освещённости, тени, перекрытия на изображениях, а также ошибки сегментации могут приводить к появлению или исчезновению как отдельных особенностей, так и целых участков контура. Поэтому процедуру отождествления контуров необходимо строить так, чтобы эти факторы нивелировались. Такой процедурой, позволяющей строить оптимальное сопоставление последовательностей с учётом возможных пропусков, добавлений и неточных совпадений признаков, является метод динамического программирования (ДП) [18].

Список литературы диссертационного исследования кандидат наук Горбачев, Вадим Александрович, 2014 год

Список литературы

1. Форсайт Д., ПонсЖ. Компьютерное зрение. Современный подход / Под ред. А.В.Назаренко - М.: Вильяме, 2004. - 466 с.

2. Davis E.R. Machine Vision, Third Edition: Theory, Algorithms, Practicalities. -Amsterdam: Elsevier, 2005. - 934 p.

3. Schenk T. Digital Photogrammetry. V.l. - Dayton: TerraScience, 1999. 422 p.

4. Zitova В., FlusserJ. Image registration methods: a survey // Image and Vision Computing. - 2003. - V.21. - P. 977-1000.

5. Blokhinov Y., Gribov D., Zheltov S. An automatic contour based detection of terrestrial objects from aerial imagery data // XXIth ISPRS Congr. Beijing, China. - 2008. - V. XXXVII. Pt B3. - P. 413-419.

6. Гонсалес P., Вудз P., Цифровая обработка изображений / Под ред. П.А. Чочиа. - М.: Техносфера, 2005. -1072 с.

7. Canny J. A Computational Approach to Edge Detection // IEEE Trans, on Pattern Analysis and Machine Intelligence. - 1986. - V. 8, N. 6. - P. 679-698.

8. Фурман Я.А. Введение в контурный анализ. Приложения к обработке изображений и сигналов. -М.: Физматлит, 2003. - 592 с.

9. Chitang G.C.-H., Као C.-C.J. Wavelet descriptor of planar curves: theory and applications // IEEE Trans, on Image Processing. - 1996. - V. 5. - P.56-70.

10.Rosenfeld А., Как A.C. Digital Picture Processing, V. 2, Second Edition. - New York: Morgan Kaufman, 1982. -349p.

11.Han J.H., ParkJ.S. Contour Matching Using Epipolar Geometry // IEEE Trans. Pattern Analysis and Machine Intelligence. - 2000. - V. 22, N. 4. - P. 358-370.

12.Блохинов Ю.Б., Горбачев В.А. Привязка наземных объектов на аэрофотоснимках на основе анализа контуров // Известия РАН. Теория и Системы Управления. -2011. - №5 - С.83-94.

13.NademejadЕ., Sharifzadeh S., Hassanpour Н. Edge Detection Techniques: Evaluations and Comparisons // Applied Mathematical Sciences. - 2008. - V.2, N. 31.-P. 1507-1520.

\A.Pal N., Pal S. A review on image segmentation techniques // Pattern Recognition.

- 1993. - V.26. - P. 1277-1294. 15.Shi J., Malik J. Normalized Cuts and Image Segmentation // IEEE Trans, on pattern analysis and machine intelligence. - 2000. - V. 22, N. 8. - P. 888-905.

16.Кормен Т., Лейзерсон Ч., Ривест Р. и др. Алгоритмы: построение и анализ / Под ред. И. В. Красикова. 2-е изд. - М.: Вильяме, 2005. - 1296 с.

17.Прэтт У. Цифровая обработка изображений Т.2. - М.: Мир, 1982. - 480 с. 18.Ohta Y., Kanade Т. Stereo by Intra- and Inter-Scanline Search Using Dynamic

Programming. //IEEE PAMI. - 1985. -V.7, N.2. - P. 139-154. \9.Fangeras, O., Hotz, В., Mathieu, M., Viville, Т., Zhang, Z., Fiia, P., Thron, E., Moll, L., Beny, G. Real-time correlation-based stereo: algorithm, implementation and applications. Technical Report RR-2013 / INRIA, 1993.

20.Ballard D. H. Generalizing the Plough Transform to detect arbitrary shapes // Pattern Recognition. - 1981. - V.13, N.2.-P. 111-122.

21.Fung P.F., Lee W.S. King I. Randomized Generalized Hough Transform for 2-D grayscale object detection // Proc. of the 13th Int. Conf. on Pattern Recognition. -1996,-V.2.-P. 511-515.

22.Блохгшов Ю.Б., Грибов Д.А., Чернявский А.С. Задача привязки изображений для некоторых случаев ракурсной фотосъемки // Изв. РАН. ТиСУ. — 2008. №6.-С. 129-143.

23.Lowe D.G. Distinctive image features from scale-invariant keypoints // Int. journal of computer vision. - 2004. №2. - P. 91-110.

24.Bay H., Tuytelaars Т., Van Gool L. Surf: Speeded up robust features // Proc. ECCV. - 2006. - P. 404-417.

25.Calonder M., Lepetit V., Strecha, C., Fua P. Brief: Binary robust independent elementary features // ECCV 2010

2в.Блохинов Ю.Б., Веркеенко M.C. Алгоритмы построения цифровых

трехмерных моделей уникальных объектов // Изв. РАН. ТиСУ. - 20 И. — №4.-С. 118-131.

21 .Lingua A., Marenchino D., Nex F. Automatic Digital Surface Model (DSM) generation procedure from images acquired by Unmanned Aerial Systems (UASs) // RevCAD - J. Geodesy and Cadastre. " 1 DECEMBRIE 1918" UNIVERSITY. - 2009. - P. 53-64.

28.Блохинов Ю.Б., Веркеенко M.C., Горбачев В.А. Разработка алгоритмов стереоотождествления особенностей изображений в методе построения высокодетальной цифровой модели местности // Известия РАН. Теория и Системы Управления. - 2013. - №2 - С. 76-91.

29.ZangL. Automatic Digital Surface Model Generation from Linear Array Images // DISS. ETHNO. 16078. - Zurich, 2005. -219 p.

30.Christmas, W. J., Kittler, J., Petrou, M. Structural Matching in Computer Vision Using Probabilistic Relaxation // PAMI. - 1995. - V. 17, N. 8. - P. 749-764.

31 .Goshtasby A., Page K. Image Matching by a Probabilistic Relaxation Labeling Process // Proc.7-th Int. Conf. Pattern Recognition. Montreal, Canada. - 1984. -V.l.-P. 307-309.

32.Скворцов A.B. Триангуляция Делоне и её применение. - Томск: Изд-во Томского ун-та, 2002. -127 с.

33.Prazdny К. Detection of Binocular Disparities // Biological Cybernetics. - 1985. -V.52.-P. 93-99.

3A.Franke U., Gehrig S. How Cars Learned to See I 154th Photogrammetric Week. Stuttgart, Germany. -2013. - P. 3-10.

35.Ernst I., Hirschmiiller H. Mutual Information Based Semi-Global Stereo Matching on the GPU // Int. Symp. on Visual Computing. Las Vegas, Nevada, USA. - 2008. - V. 1. - P. 228-239.

36.Veksler O. Efficient Graph-based Energy Minimization Methods in Computer Vision. PhD thesis. Cornell University. - 1999. -90 p.

37. Veksler O. Stereo correspondence by dynamic programming on a tree // IEEE Conf. on Computer Vision and Pattern Recognition. San Diego, California, USA. -2005. - V. 2.-P. 384-390.

Ъ%.В1еуег М., Gelautz М. Simple but effective tree structures for dynamic

programming-based stereo matching // 3rd Int. Conf. on Computer Vision Theory and Applications. Funchal, Madeira, Portugal. - 2008. - P. 415-422.

39.Hirschmtiller H. Accurate and efficient stereo processing by semi-global matching and mutual information // IEEE Conf. on Computer Vision and Pattern Recognition. San Diego, California, USA. - 2005. - V. 2. - P. 807-814.

40. Woodford O., Torr P., ReidL, Fitzgibbon A. Global stereo reconstruction under second order smoothness priors // CVPR. 2008.

41 .Горбачев В.А. Плотная стереореконструкция рельефа местности на основе модифицированного алгоритма SGM // Известия РАН. Теория и Системы Управления. -2014. - №2 - С. 68-79.

42..Hirschmtiller Н., Scharstein D. Evaluation of stereo matching costs on images with radiometric differences // IEEE Trans, on Pattern Analysis and Machine Intelligence. - 2009. - V. 31 (9). - P. 1582-1599.

АЪ.Hirschmtiller H., Gehrig S. Stereo Matching in the Presence of Sub-Pixel Calibration Errors // IEEE Conf. on Computer Vision and Pattern Recognition. Miami, Florida, USA. - 2009. - P. 437-444.

AA.Tomasi C., Manduchi R. Bilateral filtering for gray and color images // IEEE Int. Conf. on Computer Vision. Mumbai, India. - 1998. - P. 839-846.

45.Paris S., Kornprobst P., Tumblin J. et al. A gentle introduction to bilateral filtering and its applications // Proc. SIGGRAPH. New York, USA. - 2007.

46 Jrschara, A., Rumpler, M., Meixner, P., Pock, Т., Bischof H. Efficient and globally optimal multi view dense matching for aerial images // ISPRS Ann. Photogramm. Remote Sens. Spatial Inf. Sci. - 2012. Pt 1-3. - P. 227-232.

47.Блохинов Ю.Б. Алгоритмы формирования цифровой модели поверхности и текстурного покрытия в наземной фотограмметрии // Известия РАН, Теория и системы управления.-2011. №1.-С. 51-57.

48.Блохинов Ю.Б., Веркеенко М.С., Горбачев В.А., Скрябин С.В. Методика автоматического построения цифровой трехмерной модели здания на

основе цифровых снимков и плана // Известия ВУЗов. Геодезия и аэрофотосъемка. -2011. -№6. - С. 54-60.

49.Hartley R., Zisserman A. Multiple View Geometry in Computer Vision. -Cambridge University Press, 2004. - 672 p.

50.Parzert E. On estimation of a probability density function and mode // Annals of Mathematical Statistics.-1962.-V. 33,N.3.-P. 1065-1076.

51 .Mayer H., ReznikS. MCMC linked with implicit shape models and plane

sweeping for 3D building facade interpretation in image sequences // Proc. ISPRS Congress. - 2008.

52.Гнилицкий B.B., Инсаров В.В., Чернявский А.С. Алгоритмы принятия решения в задаче селекции объектов на изображениях наземных сцен // Известия РАН, Теория и системы управления. - 2010. - №6. - С. 143-151.

53.Блохинов Ю.Б., Веркеенко М.С. Алгоритмы формирования видеореалистичных текстур по данным наземной фотосъемки // Известия ВУЗов. Геодезия и аэрофотосъемка. - 2010. - №5. - С. 44-49.

5А.Веркеенко М.С., Горбачев В.А. Использование метода вероятностной релаксации для восстановления цифровой модели поверхности (ЦМП) объекта// Тезисы докладов всероссийской научно-технической конференции "Навигация, наведение и управление летательными аппаратами" - Москва-Раменское: «Научтехлитиздат», 2012. - С. 221-224.

55.Горбачев В.А. Методика построения цифровой трёхмерной модели здания на основе его цифровых снимков и плана // Сборник аннотаций докладов юбилейной всероссийской научно-технической конференции «Моделирование авиационных систем» - М.: типогр. ФГУП «ГосНИИАС», 2011.-С. 126-127.

Приложение. Основные сведения о фотограмметрических

методах

1.Математическая модель камеры.

В традиционных фотокамерах, используемых в технических системах, снимок формируется по закону центрального проектирования, кода точка снимка получается как точка пересечения прямой, проходящей через центр проекции (точку съёмки) и точку объекта, с плоскостью снимка (рис. 82).

Пиксельная система координат снимка имеет начало в левом верхнем углу изображения. Оси направлены вдоль осей снимка. Традиционно для задач обработки изображения, ось у направлена вниз. Пространственная система координат камеры имеет начало в центре проектирования. Ось 2 направлена перпендикулярно плоскости снимка по направлению к центру съёмки. Оси х и у параллельны осям снимка. Пусть тх,ту - размер пиксела, ЬХ,ЬУ - положение центральной точки на снимке, / - фокусное расстояние (расстояние от центра проектирования до плоскости снимка). Тогда пиксельные координаты (хр,хур1х) связаны с координатами (х,у^) в системе камеры следующим образом:

Рис.82. Математическая модель камеры

У а = ту(ьу - ур1х) у = уа + Ау

где Ах, Ау - нелинейные искажения камеры. Как правило, нелинейные искажения вводятся в виде:

Ах = а0уа + ха( а^г2 + а2г4 + а3г6) + а4(г2 + 2x1) + 2 а5хауа Ау = а0ха + уа(агг2 + а2г4 + а3г6) + а4(г2 + 2у2) + 2 а5хауа где г2 = Хд + Уд — расстояние до центра снимка.

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

Можно представить преобразование в матричном виде:

Перспективная проекция точки пространства (в координатах

камеры) в точку (х,у/) на плоскости снимка:

(Хр1х\ ДМх 0 Ьх

ХУрис) "I о -1 /ту Ъу

У

В матричном виде в однородных координатах:

Тогда

■•кам

Ур1х )

V 1 / \ о о 1

хр1х = К[1 0]^ Здесь К— так называемая матрица внутренней калибровки камеры. Переход от мировой системы координат в систему координат, связанную с камерой осуществляется с помощью матрицы С внешней калибровки:

С * И

с " Ц0 0 0] 1)

с-1 = I

V)

,[0 о 0]

^кам _

хР1х = К[1 0]С-^миР = piмиp здесь Р - так называемая проективная матрица камеры, Я - матрица поворота системы координат, Т— вектор смещения.

В общем случае проективная матрица Р имеет 12 параметров, один из которых свободный:

&Хр1х — РХ р

Калибровку камеры, то есть определение параметров калибровки можно произвести, имея набор пар координат точек в пространстве и на изображении [1].

2. Эпиполярная геометрия и ректификация.

Рассмотрим два изображения, на которых изображена одна и та же точка сцены Р. Её изображения — точки р, р\ центры съёмки соответствующих камер -

О, О'. Тогда пять точек: Р, р, р', О, О' будут находиться в одной плоскости, называемой эпиполярной плоскостью. Точки пересечения базовой линии ОО' называются эпиполями. Эпиполи е,ё - это проекции центров съёмки камер на другой снимок. Линия /', соотнесённая с точкой р и проходящая через р' и ё— называется эпиполярной линией, или эпиполярой (рис. 83).

Заметим, что любая точка, проецирующаяся в точку р, будет проецироваться строго на эпиполяру /', соответствующую р. Так, на рисунке 2, точка Р, проецирующаяся в точку р на левом снимке, на правом снимке проецируется в точку р', которая, так же как и р\ лежит на /'. Поэтому при известных параметрах взаимного ориентирования поиск соответствующих точек можно производить только вдоль эпиполярных линий. Такое ограничение существенно сужает область поиска, и будет использовано в дальнейшем при построении методов отождествления в главе 1.

Р

Рис. 83. Эпиполярная геометрия

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

производить вдоль строк изображений. Именно с ректифицированными изображениями работает метод, описанный в главе 2.

Р

\ /

\ ^ -л/

О ......(У

Рис. 84. Ректифицированные изображения

3. Стереореконструкция.

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

Один из способов восстановления трёхмерной точки заключается в выборе точки в пространства, минимально отстоящей от лучей зрения, проходящих через соответствующие точки изображений (точка Р и её образы р и р' на рис. 85). Другой способ заключается в выборе точки пространства (), минимизирующей отклонение с/2(р, с?) + с£2(р', <?') её проекций д и д' на снимки на от действительных положений р и р' [1]. Минимизацию можно производить методом наименьших квадратов.

Рис. 85. Восстановление трёхмерной точки по её проекциям.

4. Проблема стереоотождествления.

Как уже было показано, как задача определения взаимного ориентирование двух камер и их калибровки, так и задача стереореконструкции приводит к необходимости поиска пар точек на двух изображениях, соответствующих одной и той же точке в пространстве. Такая проблема называется проблемой стереоотождествления (stereo matching).

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