Содержание к диссертации
Введение
Глава 1. Локальные методы отождествления контурных особенностей изображения 10
1.1. Обзор методов отождествления контуров. 11
1.2. Отождествление замкнутых контуров 14
1.2.1. Построение синтезированных замкнутых контуров . 14
1.2.3. Форма представления контуров. 19
1.2.4. Отождествление контуров методом динамического программирования. 21
1.2.5. Устранение ошибок отождествления. 26
1.2.6. Привязка точек на основе отождествлённых контуров. 27
1.2.7. Оценка точности привязки точек на основе контуров 32
1.3. Отождествление точечных особенностей 37
1.3.1. Задача построения ЦМП. 37
1.3.2. Исходные данные для построения ЦМП. 38
1.3.3. Общая характеристика метода локального отождествления точек интереса. 39
1.3.4. Недостатки метода локального стереоотождествления точечных особенностей... 42
1.4. Отождествление контурных особенностей 45
1.4.1. Выделение контуров на изображениях. 46
1.4.2. Формирование элементарных отрезков . 46
1.4.3. Поиск возможных соответствий для концевых точек элементарных отрезков. 48
1.4.4. Формирование списков кандидатов для элементарных отрезков 49
1.4.5. Выбор лучших соответствий для элементарных отрезков. 50
1.4.6. Разрешение коллизий при неоднозначном соответствии. 52
1.5. Метод вероятностной релаксации 56
1.5.1. Основы метода вероятностной релаксации. 56
1.5.2. Определение набора соседей для объекта. 58
1.5.3. Вычисление коэффициента взаимного влияния. 60
1.5.4. Использование контуров в процедуре глобального стереоотождествления. 62
1.6. Выводы 66
Глава 2. Глобальные методы отождествления точек изображения 68
2.1. Обзор методов стереоотождествления. 69
2.2. Обзор моделей связей 73
2.3. Алгоритм полуглобального стереоотождествления (SGM). 75
2.4. Модификации метода полуглобального отождествления 77
2.4.1. Модификация метрики сравнения. 77
2.4.2. Иерархическая обработка. 81
2.4.3. Использование градиентной информации 83
2.4.4. Субпиксельность в алгоритме SGM. 85
2.4.5. Устранение влияния ошибок нормализации. 86
2.4.6. Фильтрация матрицы стоимости. 87
2.4.7. Сглаживание карты диспаратности. 89
2.4.8. Блочная обработка. 91
2.5. Плотное многолучевое отождествление изображений 93
2.5.1. Проблема слепых зон. 93
2.5.2. Полуглобальная оптимизация при многолучевом отождествлении 94
2.5.3. Оценка оптимального перекрытия 96
2.6. Выводы 100
Глава 3. Модельно-ориентированный метод построения трёхмерных моделей зданий 102
3.1. Постановка задачи и исходные данные 103
3.2. Построение геометрической модели объекта 105
3.2.1 Локализация элементов объекта на изображениях 106
3.2.2 Локализация положения элементов объекта в пространстве 109
3.2.3 Уточнение модели объекта 111
3.3. Поиск элементов фасада по цифровому эталону 115
3.3.1 Использование комплексного эталона 116
3.3.2 Инвариантный к масштабу поиск объектов. 118
3.4. Текстурирование 120
3.5. Выводы 121
Заключение 123
Список литературы 125
- Построение синтезированных замкнутых контуров
- Формирование элементарных отрезков
- Модификации метода полуглобального отождествления
- Поиск элементов фасада по цифровому эталону
Построение синтезированных замкнутых контуров
Среди всех типов особенностей, используемых при отождествлении, контуры особенно важны по трём причинам: они обладают высокой устойчивостью по отношению к разным видам геометрических и фотометрических искажений и, с другой стороны, являются естественными наиболее различимыми визуально границами на изображении для большинства объектов сцены, представляющих реальный интерес. Кроме того, контуры обладают большей уникальностью, чем точечные особенности в силу более сложной структуры. Безусловно, разными авторами предлагались подходы к решению задачи отождествления контуров [2, 3], но нетрудно видеть, что все они имеют весьма общий характер и едва ли предназначены для работы с реальными изображениями сцен произвольного содержания. Тематический поиск показывает, что статей, посвященных применению точек интереса, существует десятки, а, возможно, и сотни, в то время как тема применения контуров для анализа изображений практически не представлена в публикациях. Учитывая безусловную актуальность темы, это должно означать, что к настоящему времени данная задача еще далека от своего окончательного решения.
Можно обозначить следующие существенные проблемы, которые должен решать разрабатываемый метод анализа и привязки контуров предъявляемых изображений для того, чтобы представлять действительную ценность при решении широкого класса практических задач.
При просмотре космических или аэрофотоснимков нетрудно убедиться, что видимые контуры естественных и искусственных объектов претерпевают заметные изменения от изображения к изображению. Эти изменения могут значительно усиливаться, если съемка относится к различному времени суток или сезонам года. Наибольшие геометрические искажения достигаются в наземной съемке с сильно отличающихся ракурсов. К сожалению, существующие алгоритмы выделения контуров во многих случаях дают результат, еще и заметно не совпадающий с тем, что видит человеческий глаз. Поэтому хотелось бы, прежде всего, разработать технику выделения контуров, обладающую повышенной устойчивостью по отношению к изменениям условий получения изображений.
При наличии выделенных границ высокого качества их сравнение все еще не является простой задачей - слишком велика локальная изменчивость изображений, обусловленная естественными причинами и, прежде всего, различными шумами. Поэтому попытки отождествления контуров на основе только их локальных особенностей зачастую приводят к неоднозначным результатам. Следовательно, разрабатываемый метод должен обладать свойством разрешения неоднозначностей в таких ситуациях.
Решение задачи привязки изображений предполагает не только отождествление различных изображений объекта, но и определение в результате координат ряда точек, представляющих интерес [4]. Как известно, большинство численных алгоритмов обработки координат, включая стандартные фотограмметрические процедуры ориентирования, опирающиеся на уравнение коллинеарности, используют в качестве входных данных сопряженные точки. Проблема в том, что отдельные точки сопряженных кривых, вообще говоря, не являются сопряженными, поэтому задачу выбора связующих точек из числа краевых необходимо решать отдельно. Например, в качестве связующих можно выбрать характерные точки кривых, в которых достигается максимальная кривизна [5]. Однако и в этом случае соответствие является лишь приблизительным и требует уточнения, тем более сложно говорить здесь о субпиксельной точности отождествления найденных пар точек. Таким образом, задача измерения координат точек на основе точек контуров не является тривиальной и необходима разработка точного и устойчивого метода ее решения.
При анализе изображений под контурами, как правило, подразумевают линии перепада яркости. Точки таких линии можно детектировать с помощью дискретных аналогов оператора производной (например Прюит, Робертса, Собела) [6]. Чтобы собрать контур из контурных точек, используется предположение о том, что нормаль к контуру направлена вдоль направления градиента в точке. Для получения удобных для дальнейшего использования тонких (толщиной в 1 пиксель) контуров применяется детектор краёв Канни [7].
Вид представления контура существенно влияет на возможности его анализа и отождествления. После выделения контуры представлены в виде цепного кода, либо списком входящих в него точек. Такое представление неудобно для дальнейшего анализа, так как положение отдельных пикселей контура сильно зависит от изменений в ракурсе, освещении или зашумлённости изображения. Вследствие этого предлагаются различные виды представлений для контуров. Одно из старейших способов представления - это представление контура в виде коэффициентов Фурье. Базисом в таком случае выступают, например, правильные многоугольники [8]. Аналогично, можно составить описание контура с помощью вейвлет-преобразования [9]. Однако такие способы представления подходят только для замкнутых контуров.
Другим способом представления является представление контура в виде кривой, и её последующей параметризации. Рассматривается представление в виде (а,р) - дальность в зависимости от центра, (s,K) - кривизны в зависимости от длины дуги, (s,\f/) - угла излома в зависимости от длины дуги контура [2]. На практике удобнее рассматривать контур не как гладкую кривую, а как ломаную. Тогда можно использовать дискретные аналоги указанных выше характеристик. Вместо кривизны удобно использовать так называемую k-величину изгиба (k-slope value). Она представляет собой угол излома при вершине ломаной по отношению к точкам, отстоящим от неё на k вершин [10].
Помимо геометрических признаков, при представлении контура можно использовать информацию о точках, из которых он состоит, и фотометрическую информацию о яркости (либо перепаде яркости) изображения в окрестности контура.
Формирование элементарных отрезков
Метод локального отождествления точек интереса для восстановления ЦМП характеризуется тем, что поиск соответствий происходит отдельно для каждой точки. Как следствие, результат отождествления точки не зависит от результатов отождествления остальных. Для проведения отождествления сначала производится поиск особенных точек на обоих изображениях каким-либо детектором особых точек (или точек интереса, interest points). Затем для всех выбранных точек строится компактное описание окрестности изображения вокруг этих точек с помощью дескрипторов (например SIFT, SURF, BRIEF [23,24,25]). После этого для каждой точки первого изображения производится поиск точек другого изображения с наиболее похожим (в смысле минимизации какой-либо метрики) дескриптором. Как правило, процедура отождествления состоит из нескольких этапов: не итеративный процесс подготовки данных и итеративный иерархический процесс формирования ЦМП [26].
Не итеративный процесс. Не итеративный процесс заключается в подготовке входных данных для процедур иерархического процесса и включает в себя фильтрацию снимков и формирование аппроксимирующей поверхности для самого низкого уровня пирамиды. Для получения набора связующих точек в условиях отсутствия априорных данных в задаче привязки изображений используется сильно перегруженная вычислениями и низкоэффективная техника отождествления точек интереса, которая также используется для построения внутреннего и внешнего ориентирований стереопары. Требования различных видов инвариантности и отсутствие существенных ограничений на расположение точек при поиске приводят к необходимости применения сложных дескрипторов с последующей проверкой результата пространственными фильтрами различных типов. Результатом такого отбора из нескольких тысяч кандидатов является небольшой набор из нескольких десятков точек, удовлетворяющих всем требованиям. Для построения высокодетальной ЦМП требуется гораздо большее число точек (десятки-сотни тысяч), для их генерации нужно использовать алгоритмы другого типа.
Итеративный процесс. Итеративный иерархический процесс происходит последовательно на всех уровнях пирамиды изображения, начиная со снимка самого грубого разрешения, заканчивая самым детальным снимком. На каждом уровне пирамиды происходит построение соответствующей сетки. Итеративный процесс локального стереоотождествления состоит из нескольких этапов.
1. Для формирования и последующего сгущения сетки на левом снимке используются точки интереса с использованием различных операторов интереса (Харрис, Фёрстнер, Моравек). Комбинации вышеперечисленных операторов позволяют извлечь максимально возможное количество точек, с учетом различных свойств локальных примитивов (рис. 21). В результате этого, триангуляционная сетка, получаемая в результате процесса восстановления ЦМП, сгущается в областях с наибольшей информативностью, а в остальных регионах остается разреженной.
2. Поиск соответствующих точек на правом изображении происходит с использованием процедуры взаимного корреляционного отождествления. Основное ограничение определяется эпиполярной геометрией. Левый и правый образы точки должны лежать на соответствующих эпиполярах. Размеры области поиска зависят от разброса высот аппроксимирующей поверхности в окрестности искомого образа точки. Полученная ЦМП передается на следующий уровень процесса локального стереоотождествления, на котором она в свою очередь используется в качестве аппроксимирующей поверхности для поиска соответствующих точек на более детальном изображении. В результате происходит последовательное уточнение ЦМП и сгущение сетки по мере спуска по пирамиде изображений. В данной работе использовалось три уровня пирамиды.
3. Все отождествленные точки проходят процедуру фильтрации, отбрасывающую неверно отождествленные точки, также называемые выбросами. Эффективным средством контроля выбросов являются медианные фильтры, в том числе их адаптивные модификации [26, 27]. Недостатки метода локального стереоотождествления точечных особенностей.
Как показывают практические результаты, значительная часть точек, поступивших в процедуру локального стереоотождествления, не получает однозначного отождествления Однозначное отождествление образа точки на левом изображении с одним из кандидатов определяется на основе анализа ярко выраженных пиков (локальных максимумов) графика взаимной корреляции, построенного в области поиска. Если на графике присутствует только один пик, и он превышает некоторое пороговое значение, или если один из пиков графика существенно превосходит остальные по величине коэффициента взаимной корреляции, то соответствующая пику точка на правом снимке однозначно отождествляется с точкой на левом снимке (рис. 22).
Модификации метода полуглобального отождествления
После построения карты диспаратности, как правило, необходимо провести ее сглаживающую фильтрацию для устранения ошибок и выбросов. Хиршмюллер для постобработки рекомендует применять медианную фильтрацию [39]. Медианная фильтрация хорошо устраняет шум типа соль и перец, т. е. ошибки в отдельных пикселах. Однако более крупные ошибки и негладкости поверхностей медианным фильтром не устраняются. Для более качественной постобработки интерес представляет такой метод нелинейной фильтрации, как билатеральный фильтр [44], так как он обладает хорошей сглаживающей способностью, но при этом сохраняет резкие границы объектов. При использовании билатерального фильтра, вклад точки зависит не только от расстояния до центральной точки (как в гауссовском фильтре), но и от разности значений сглаживаемой функции в этих точках. Благодаря этому сглаживание производится только внутри относительно однородных областей, а различные области не влияют друг на друга, их края не смазываются. В случае фильтрации диспаратности можно использовать дополнительную информацию – значения яркостей на исходном изображении. Это позволит производить сглаживание только в пределах однородных по цвету областей. Учет яркостей можно производить, добавив в фильтр дополнительное ядро, зависящее от яркости на исходном изображении (кроссбилатеральная фильтрация [45]).
С использованием трех различных ядер, учитывающих яркости пикселей на исходном изображении, диспаратность и расстояние от центра ядра, кроссбилатеральная фильтрация будет выглядеть следующим образом:
Использование кроссбилатерального фильтра позволяет не только сгладить неровности карты диспаратности, вызванные ошибками стереоотождествления, но и повысить точность границ объектов. Кроссбилатеральный фильтр показывает лучшие результаты и является более предпочтительным среди остальных, так как при фильтрации использует дополнительную информацию -значения яркостей на исходном изображении (рис. 56-57).
Для обработки снимков большого размера требуется существенный объем памяти ЭВМ. Чтобы снизить требования к доступному объему памяти, исходный снимок разбивается на отдельные блоки меньшего размера [39]. При формировании блоков с перекрытием можно исключить зависимость результатов обработки блоков между собой, что позволяет обрабатывать их параллельно. После завершения обработки всех блоков производится слияние полученных карт диспаратности. Пример получаемой после сшивки трехмерной модели для снимка размером 1500 на 3600 пикселей показан на рис. 58. Отдельные фрагменты модели показаны на рис. 59.
Процесс построения цифровой модели сцены по стереопаре обладает существенным недостатком - наличием так называемых слепых зон (рис. 60). Точки сцены, которые находятся в слепых зонах, видны только на одном из изображений, либо не видны вовсе. Для таких точек невозможно построить верное стереоотождествление, следовательно невозможно определить их глубину по стереопаре. Вследствие наличия слепых зон на модели будут возникать пропуски либо ошибки.
Решением этой проблемы является использование для реконструкции трёх и более снимков одной и той же сцены (рис. 61). При правильном выборе набора изображений с разными точками съёмки, во-первых, исключается возникновение слепых зон, во-вторых, появляется возможность повышения качества модели за счёт избыточности входной информации.
В случае использования трёх и более изображений невозможно использовать непосредственно метод SGM или другие подобные методы, так как они рассчитаны на отождествление пары изображений между собой. Однако задачу можно привести к форме, аналогичной задаче SGM. Для этого можно использовать многовидовой метод заметающей плоскости (multi-view plane sweep) [46]. Он заключается в том, что оптимизация производится не относительно диспаратности D, а непосредственно в объектном пространстве относительно глубины Z. Для этого в объектном пространстве выбирается семейство плоскостей (для удобства их можно выбирать параллельным базовому снимку, key view), и сетка на плоскости. Далее для каждой точки сетки выбирается оптимальная плоскость, которой она должна соответствовать (рис. 62). Номер плоскости является меткой точки, аналогично диспаратности в задаче SGM-стереоотождествления.
Поиск элементов фасада по цифровому эталону
Завершающим этапом построения фотореалистичной модели объекта является наложение текстур на подготовленную каркасную модель. Для решения этой задачи использовалась методика формирования текстур из исходных снимков, разработанная в [53], также полностью автоматическая. При текстурировании для каждой поверхности модели выбирается снимок из коллекции, на котором она видна наилучшим образом. Критериями выбора являются во-первых угол между нормалью к поверхности объекта в пространстве и нормалью к плоскости снимка, во-вторых площадь на снимке, которую занимает изображение выбранной поверхности. При таком выборе получаемые текстуры будут иметь максимальное разрешение и минимальные искажения вследствие ресемплинга. Результат работы алгоритмов – завершённая текстурированная представлена на рис. 81.
В этой главе представлена оригинальная методика автоматического построения по данным наземной фотосъёмки трёхмерных цифровых моделей для зданий типовой застройки, необходимая для наполнения ЦМП
фотореалистичными моделями зданий, расположенными на местности. Особенностью предлагаемого подхода является оригинальная постановка задачи, связанная с использованием дополнительной информации в виде плана здания и дополнительных геометрических ограничений на форму здания. Такая постановка приводит к совершенно иной, по сравнению с техникой работы по стереопарам, организации процесса построения трёхмерных моделей зданий. В дополнение к этому предложен оригинальный метод масштабно-инвариантного поиска на изображениях объектов, заданных комплексным эталоном, для обнаружения элементов фасада здания на ректифицированных изображениях. В результате весь процесс построения модели существенно упрощается, и становится возможным внедрить автоматизированную методику на всех его этапах. При этом строится сначала основная каркасная модель здания, затем производится текстурирование и добавляются фасадные элементы.
Результаты всех этапов работы проиллюстрированы на конкретном примере для коллекции наземных снимков и плана типового здания поликлиники. Представлен результат работы – завершенная текстурированная модель здания.
Представляется перспективным развитие метода для построения моделей более широкого класса зданий, а так же повышение детальности фасадов путём выделения выступающих элементов на стенах зданий.
В диссертации рассмотрены основные этапы технологии построения высокодетальных цифровых моделей поверхности на основе цифровых изображений. На ключевых этапах обработки изображений были предложены новые оригинальные методы и существенные модификации: робастная автоматическая привязка изображений на основе сопоставления замкнутых синтезированных контуров; метод стереоотождествления контуров изображений и его применение в методе вероятностной релаксации для увеличения надёжности и точности локальных методов построения ЦМП; модифицированный алгоритм полуглобального отождествления для плотного сопоставления точек изображений, повышающий точность и детальность ЦМП; метод многолучевого отождествления на основе полуглобальной оптимизации энергии соответствия, ускоряющий процесс плотного отождествления трёх и более изображений; высокопроизводительный метод автоматического построения моделей типовых зданий по данным наземной съёмки с применением комплексирования информации, дополняющий цифровую модель поверхности фотореалистичными моделями зданий.
Все предложенные методы направлены на то, чтобы благодаря более глубокому семантическому анализу информации, которую несут в себе изображения, повысить точность и детальность трёхмерной цифровой модели сцены, восстанавливаемой на основе данных изображений.
В ходе работы были созданы программные модули, позволяющие осуществлять практически полный цикл технологии построения ЦМП в соответствии с предложенными методами и модификациями. Работоспособность и эффективность методов была подтверждена многочисленными испытаниями на реальных данных – коллекциях аэрофотоснимков, располагаемых ФГУП «ГосНИИАС».
В свете поступательного развития технологий фотосъёмки и увеличения вычислительной мощности компьютерных систем, для дальнейших исследований автору представляется наиболее перспективными разработка глобальных методов отождествления контуров по схеме многие-ко-многим и развитие методов плотного многолучевого отождествления. Такие методы хотя и являются крайне вычислительно-затратными, но могли бы привести к значительному увеличению точности и детальности получаемых моделей.
