автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Разработка методов машинного зрения для построения пространственных моделей трехмерных сцен

РГ6

Государственный комитет Российской Федерации

по высшему образованию д Московский Физико-Технический Институт

2 3 П ■Г'^

На правах рукописи УДК 528 (048).061.8

СИБИРЯКОВ Александр Витальевич

РАЗРАБОТКА МЕТОДОВ МАШИННОГО ЗРЕНИЯ ДЛЯ ПОСТРОЕНИЯ ПРОСТРАНСТВЕННЫХ МОДЕЛЕЙ ТРЕХМЕРНЫХ СЦЕН

Специальность 05.13.16 - «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва -1998

Работа выполнена в Московском Физико-Техническом Институте

Научный руководитель:

к.т.н„ с.н.с. Желтов Сергей Юрьевич

Официальные оппоненты:

д.ф.-м.н., проф., Тюкавкин Дмитрий Викторович д.т.н., проф., Тюфлин Юрий Сергеевич

Ведущая организация:

Институт Прикладной Математики им. Келдыша

Защита диссертации состоится "18" суеи^оЬ^ 1998 г. в часов на заседании диссертационного совета К 063.91.08 при Московском физико-техническом Институте по адресу:

141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9.

С диссертацией можно ознакомиться в библиотеке Московского Физико-Технического Института.

Автореферат разослан "Ца." кру^ол 1998 года.

Ученыйхекретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

В последние годы бурно развиваются информационные технологии, предназна-№нные для модельного представления окружающего мира. Одной из важнейших об-пастей применения таких технологий являются геоинформационные системы (ГИС), обеспечивающие сбор, обработку и отображение пространственных данных. Современные ГИС оперируют с цифровымй моделями трехмерных сцен, которые являются ■говым способом представления пространственных данных.

Одна из важнейших задач при создании цифровых моделей трехмерных сцен -толучение реальных трехмерных данных. Их источниками могут быть как данные дистанционного зондирования, под которыми обычно понимаются авиационные и косми-<еские изображения, так и данные ручной фотографической съемки. Для последующе-■о применения из этих данных должна быть извлечена необходимая информация об изображенных объектах и характерных чертах местности.

Одними из наиболее сложных и дорогих операций с точки зрения временных затрат являются построение цифровой модели рельефа (ЦМР), а также распознавание и гокализация различных трехмерных объектов искусственного происхождения. Из-за зольших затрат на обработку данных, автоматизация этих процессов является актуальной проблемой.

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

Для достижения цели исследования решались следующие задачи; ¡. Создание методики автоматического построения высокоточной ЦМР по стереопаре изображений;

!. Создание эффективного в вычислительном смысле алгоритма поиска соответствующих точек на стереопаре (задача стереоотождествления); I. Создание вычислительно эффективного метода высокоточного измерения положения соответствующих точек (задача субпиксельного стереоотождествления); :. Разработка алгоритма автоматического обнаружения трехмерных объектов искусственного происхождения;

5. Разработка алгоритма автоматической реконструкции сегментированных трехмер ных объектов.

Научная новизна работы •создана новая методика построения ЦМР, отличающаяся использованием иерархк ческой стратегии и автоматической обработкой аномальных ошибок; •создана новая методика стереоотождествления, отличающаяся предварительны! определением информативных участков изображения; иерархическим отождествлен ем по пирамиде изображений, субпиксельным уточнением;

• разработан новый метод определения информативных участков изображения, обес печивающий надежную и устойчивую работу алгоритма корреляционного стереоото» дествления;

•предложен новый метод субпиксельной корреляции, отличающийся использование! аффинной модели деформации отождествляемых образов при вычислении коррел? ционной функции;

• разработаны новые алгоритмы обработки ЦМР с целью устранения аномальны ошибок с учетом геоморфологических черт рельефа, основанные на локальной филы рации значений высот, глобальном сглаживании поверхности и более тонкой корре! ции ЦМР по ортофото;

• предложены оригинальные процедуры обнаружения искусственных объектов н авиационных изображениях на основе комплектования различных видов данны: включающих цветную, многозональную и черно-белую съемку, ЦМР, и априорные гес метрические характеристики;

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

Положения, выносимые на защиту

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

2. Созданные автоматические методы построения и обработки ЦМР обладают сво£ ством устойчивости по отношению к разнообразным формам рельефа;

3. Разработанная методика автоматического обнаружения и реконструкции искуссп венных объектов по их геометрическим моделям позволяет эффективно решать задг

ty реконструкции объектного состава сцены при наличии необходимого объема пер-зичных данных.

Практическая значимость диссертации

Практическая значимость диссертации состоит в применении разработанных методов для создания алгоритмического и программного обеспечения (ПО) для персональной ЭВМ IBM PC, которое осуществляет эффективное по сравнению с традиционными методами построение трехмерных моделей сцен по авиационным и космическим снимкам. Данное ПО является частью разрабатываемых в ГосНИИАС программно-алгоритмических комплексов:

» Система стереофотограмметрической обработки космических снимков полученных камерами МК-4, ТК-350, КВР-1 ООО;

» Система обработки стереопарной и маршрутной авиационной съемки; » Система короткобазисной фотограмметрии.

Результаты, полученные при написании диссертации, были неоднократно использованы в рамках НИР "Вертел", "Феникс", "Информационные технологии - 97", выполнявшихся по заказам Министерства Обороны РФ, Министерства Экономики РФ, Министерства Науки РФ, а также в совместных работах ГосНИИАС и Межотраслевой Ассоциации "Совинформспугник". На базе предложенных методов и разработанного ПО были созданы ЦМР различных участков поверхности Земли, общей площадью бо-пее 1000 км2. Методы, разработанные в диссертации, были применены при создании пространственных моделей местности, предназначенных для отработки современных компьютерных авиационных тренажерных комплексов, основанных на технологии виртуальной реальности.

Апробация работы и публикации по теме

По результатам диссертации опубликовано 8 печатных работ и 5 научно-технических отчетов. Основные результаты работы докладывались и обсуждались на XXXIX научной конференции МФТИ «Современные проблемы фундаментальной и при-<ладной физики и математики», г.Долгопрудный, 1996г., на научно-технической конференции «Современное состояние и перспективы развития геодезии, фототопографии, гартографии и геоинформационных систем» в ЦНИИ геодезии, аэрофотосъемки и картографии, г.Москва, 1997г., на международной научной конференции «Optical 3D-Vleasurements», г. Цюрих, Швейцария, 1997г., на международных конференциях cAeroSense», г.Орландо, США, 1997г., 1998г.

Структура и объем диссертации

Диссертация состоит из введения, пяти глав, заключения, списка литератур включающего 62 наименования и двух приложений. Общий объем работы составля 123 страницы машинописного текста, 100 рисунков, 14 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении рассмотрены этапы построения трехмерных компьютерных м делей сцен по их изображениям (рис.1). Показаны взаимосвязи предметных облает цифровой фотограмметрии и машинного зрения с различными этапами создания тре мерных моделей. Также показана степень автоматизации, применяемая на кажде этапе. Кратко рассмотрен круг вопросов, рассматриваемых в данной диссертационж работе (темная область на рис.1). Далее, в каждой главе диссертации рассматривае ся одна из задач исследования, делается обзор публикаций по рассматриваемой т ме, затем производится обоснование выбора метода решения задачи, подробно ра сматриваются разработанные методы, и в заключении кратко перечисляются основнь результаты главы. Все разработанные методы проиллюстрированы на примерах обр ботки реальных авиационных и космических изображений.

Интерактивные методы__

Полуавтомата — ческие методы

Автоматические мполи

Создание модели трехмерной сцены

Ориентнроиание снимков

Восстановление иц..|4>о[..д1 молем! рельефа

«Ф югр 1>ГП ф.Ы

Визуализация трехмерной едены |_Машинная графика |

Рис. 1 Общая концепция создания моделей трехмерных сцен по данным дистан —

ционного зондирования

В первой главе «Метод иерархического корреляционного стереоотождествл'

ния» поставлена следующая задача стереоотождествления: по исходным данньи

включающим в себя: 1) оцифрованные изображения трехмерной сцены; 2) априорну

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

1. Разработка метода выбора наиболее информативных участков изображений;

2. Разработка метода стереоотождествления с пиксельной точностью;

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

на стереопаре изображений, и описана новая методика стереоотождествления, блокам а которой показана на рис.2. Новые методы решения разработаны для следующих Злоков: 1) Выбор информативных эталонов; 2) Стереоотождествление по пирамиде изображений; 3) Субпиксельное уточнение.

Выбор метода решения задачи стереоотождествления производился на основе анализа большого количества реальных авиационных и космических изображений. Бы-1и выделены основные факторы, затрудняющие стереоотождествление: IСущественные яркостные различия изображений стереопары, возникающие при гъемке поверхностей объектов под разными углами; 2)Существенные геометрические юкажения, вызванные рельефом местности; 3)Наличие на изображениях областей с лапой вариацией яркости (пустыни, водохранилища и т.д.). Для получения подробных |МР возникает необходимость отождествления большого количества точек, поэтому 1ажным критерием при разработке метода являлось быстродействие.

Рассмотрены следующие основные проблемы, возникающие при стереоотожде-твлении и пути их преодоления: 1) ограничение области поиска, которое осущесгвля-тся за счет применения эпиполярной геометрии, априорного оценивания диапазона ысот рельефа, применения пирамиды изображений; 2) выбор уникальных эталонов, существляемый на основе анализа информативности фрагментов изображений; 3) ыбор начального приближения положения соответствующих образов, которое осуще-твляется за счет применения иерархической стратегии построения ЦМР; 4) геометри-еские искажения образов, устраняемые путем пересчета изображений; 5) яркостные скажения образов, устраняемые явным введением параметров искажений и их оцен-

кой; 6) ложное отождествление, выявляемое с помощью анализа вида корреляционно функции (КФ).

Стереопара ^-► Предобработка: фильтрация шумов, подчеркивание краав |

|Предобрабоханная:

стереопара

|Пирам1Сда

1~1

Построение пирамиды изображений.

]

оторооппр

й—I

Определение точек интереса (эталонов)

НСиис!

Карта диспаратностеи

)

'Список точек интереса

Стереоотождествление по пирамиде изображений

Ш!

ш

Стереоотождествлеыие эталонов на ом уровне пирамиды стереопар

N = 1

да

Фильтрация диспаратностей

ШШШВЩ

X

Субпиксслыгое уточнение

Рис.2 Блок—схема метода иерархического корреляционного стереоотождествления

Рассмотрены следующие вычислительно эффективные показатели информг тивности фрагментов изображений: 1) среднеквадратическое отклонение (СКО) сигнг ла; 2) отношение сигнал/шум; 3) корреляционный радиус сигнала. Для более строгог решения выбран показатель СКО сигнала, на основе которого разработан новый мето, определения информативности фрагментов изображения на основе анализа статистиче ских свойств шума по оптическому клину. Метод состоит в следующем.

Для участка изображения рассматривается статистическая гипотеза Но о тон/ что выборка, состоящая из значений яркостей 4 однородная:

Но: Ъ = и+ /7,, л, е N(0, а2(и)), где и - предполагаемое постоянное значение яркости на фрагменте, /7, -отсчеты шумг о{и) - зависимость СКО шума от яркости, полученная из анализа шума по оптическом клину.

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

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

После равносильных преобразований гипотезы, она сводится к проверке, принадлежит ли выборочная дисперсия фрагмента распределению %2 (М-1). Решающее правило имеет вид: если

то гипотеза Н0 отвергается. Здесь <т - СКО значений яркости на фрагменте, М - длина выборки, ар- квантиль нормального распределения. Критерий (1) позволяет решить: 1) является ли данный фрагмент информативным; 2) если фрагмент не является информативным, то можно ли изменить его размеры так, чтобы он стал информативным. Для этого разработана алгоритмическая процедура, основанная на проверке критерия при увеличении размера фрагмента до некоторого максимального размера.

Найденные информативные фрагменты используются в качестве эталонных образов для стереоотождествления. Рассмотрен корреляционный метод стереоотожде-ствления с помощью пирамиды изображений. Метод основан на поиске максимума КФ

I Ax,ymxl>yi)-Nfg

. , ч _ _(_!£>_____, (2)

где р - вектор параметров преобразования между системами координат эталона f(x,у) и отождествляемого образа g(Xi,yi), который в данном случае содержит только параметры сдвига: р = (а,й)т, т.е.

х, = х + а, у, = у + b

Пирамида изображений представляет собой последовательность N изображений, причем каждое последующее изображение получается из предыдущего путем фильтрации и прореживания в два раза по схеме: 1) Исходное изображение fN-i(x,y)\ 2) Высокочастотная фильтрация с ядром h(u,v): g(x,y)=/fiN.i(x-u,y-v)h(u,v)dudv, 3) Уменьшение размеров в 2 раза: ff^(x,y)=g(2x,2y). Фильтрация изображении необходима для подавления высокочастотных шумов. В качестве ядра h(u,v) используется функция Гаусса. Пирамидальная структура данных имеет две основные цели: 1) сокращение времени обработки изображений; 2) определение более точных начальных приближений для обработки нижних уровней по результатам обработки верхних уровней (уменьшение области поиска). Для каждого эталона, выбранного на левом изображении, на всех уровнях пирамиды решается задача стереоотождествления:

(а',¿>*), = агдтахк(а,Ь), /" = Л/,...,I О

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

Задача (3) решается путем последовательного перебора значений параметре сдвига из допустимого диапазона. На верхнем уровне (т.е. на изображении с самым ни ким разрешением) для ограничения области поиска используется эпиполярная геометр!» и априорное оценивание диапазона высот рельефа. На более детальных уровнях и пользуется начальное приближение полученное с предыдущих уровней.

Показано, что для типичных размеров области поиска применение пирамид изображений сокращает время стереоотождествления в 5 раз. На рис.3 показан пр1 мер влияния пирамиды на качество ЦМР. Та же ЦМР, вычисленная без применен пирамиды изображений, содержит большое количество выбросов.

Рис.3 Вычисление ЦМР с помощью иерархического корреляционного стереотождествл! ния по четырехуровневой пирамиде изображений с использованием: (а)- только 4-1 уровня пирамиды; (б)- 4 и 3-го уровней; (в)- 4,3,2 уровней; (г)- 4,3,2,1 уровней. Высот показаны в виде яркости._

Рассмотрена обобщенная форма метода корреляционного стереоотождествл!

ния, предназначенная для отождествления образов произвольной формы: 1) эталс имеет произвольную форму; 2) каждый пиксел эталона имеет свой вес; нулевые вес указывают на то, что данный пиксел не участвует в вычислении КФ; 3) область поио имеет произвольную форму, которая оценивается априорно; каждый пиксел обласп поиска имеет индикатор, который указывает, нужно ли вычислять в нем КФ. В качестЕ примера применения корреляционного отождествления в произвольной форме ра< смотрена задача стереоотождествления прямых линий на стереопаре, которая име« важное значение при детализации ЦМР, построенной по снимкам, содержащим иску ственные объекты.

Во второй главе «Метод субпиксельной корреляции в задаче предельно точн< го отождествления соответствующих точек стереоизображений» поставлена следуй щая задача субпиксельного стереоотождествления: по исходным данным, вклн чающим в себя: 1) эталонный участок одного изображения стереопары; 2) приблиз!

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

1. Выбор модели деформации соответственных участков изображений;

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

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

л; = а, + агх+а^у, у, = й, + Ь2х+Ь3у (4)

Метод является развитием классического корреляционного метода. В работе эассмотрены теоретические основы метода, а также детали его реализации. Показано, -гго последовательное применение нормализованной корреляции приводит к постановке задачи нахождения вектора поправок 6-параметрического аффинного преобразования в виде задачи на обобщенные собственные значения. После равносильных преобразований выражения (2) и линеаризации по параметрам преобразования (4), (2) принимает вид отношения Рэлея

у еЛпч__w __"г ""г /

(W Лрг(Ь8г-Л1ПГ)Др~ЛргВЛр' u

-де Дрг - [l Дв, Да2 Дя3 Ab, Д62 Дй3]- вектор приращений параметров преобра-ювания (4); А = г гг - матрица размером 7x7, г = - вектор размерности 7,

? =\g' ё', Хё'х yg'x ё'у xg'y вектор, полученный при линеаризации функции фкости участка правого изображения в каждом пикселе (х,у), В= £ggт- NggT - мат-

Uy)

>ица размером 7x7. Матрица В- симметрическая и положительно определенная. Победнее следует из того, что знаменатель формулы (5) есть величина пропорциональ-шя дисперсии яркости участка правого изображения. Для реальных изображений мат-)ицу В можно считать невырожденной. Таким образом задача (3) приводится к задаче 5), которая эквивалентна задаче на обобщенные собственные значения вида (6).

Ах=ЛВх (6

Предложено теоретическое решение задачи (6) с учетом специфической струи туры матриц, получающихся при линеаризации задачи. Для этого доказана следующая Теорема. Пусть имеется произвольный вектор а размерности п и симметриче екая, положительно определенная и невырожденная матрица В размером лхл. Тогд, для решений обобщенной задачи на собственные значения (6), где А=аат справедлив1 следующие утверждения: 1) Имеются два обобщенных собственных значения: Я»=| кратности п-1 и Аг>0 кратности 1; 2) Обобщенный собственный вектор, соответствую щий Лг находится по формуле х=В"1а, 3) Дг=атх, где х-собственный вектор, соответст вующий Л2.

Из теоремы решение задачи (5) находится по формуле

Лр = В'г (7

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

А:(аДр) -> шах (8

Решение задачи (8) получается аналогично, с помощью преобразования и линеариза ции (2) по а, и применения теоремы. Таким образом, решение задачи (3) сводится двум шагам, характерным для многих методов оптимизации: 1) нахождение вектор< параметров аффинного преобразования (4), определяющего направление в 6-мерно» пространстве параметров; 2) нахождение шага вдоль этого вектора.

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

тг, м.

Вариант метода с использованием одного начального приближения -1 10 0

Вариант метода с усреднением результатов сходимости различных начальных поиближоний 0 1 76

Табл.1 Точность отождествления контрольных точек стереопары методом субпиксельной корреляции. тг, о2- среднее и СКО расхождений высот в контрольных точках. Разрешение пиксела на местности для используемых изображений равняется 9 метров.

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

яПх,=0. i*j. s = Uz, (9)

'=1

Цля учета геометрических искажений образов, вызванных перспективной проекцией и грехмерной формой объектов сцены, для каждой области у„| вводится свое аффинное искажение (4). Показано что после линеаризации по всем параметрам задача снова <шеет вид (5), где матрицы имеют блочную структуру вида

"а, 0 0 В, 0 о"

А = 0 0 В = 0 0

0 0 А„ 0 0 В„.

Поэтому задача максимизации коэффициента корреляции имеет вид, удовле-"воряющий условиям доказанной теоремы.

Распространение метода субпиксельной корреляции на случай, когда известна ]редварительная сегментация (9) позволяет решить проблему проведения высокоточ-1ых фотограмметрических измерений различных особых точек сцены (углов и краев лногогранных объектов, особых точек ЦМР).

В третьей главе «Построение ЦМР с помощью иерархической стратегии» по-тавлена следующая задача построения ЦМР по стереопаре изображений: по юходным данным, включающим в себя: 1) оцифрованные изображения трехмерной цены; 2) параметры ориентирования изображений; 3) априорную информацию о полу-аемой ЦМР, необходимо построить цифровую модель рельефа, представляющую со-юй набор трехмерных точек сцены, удовлетворяющую следующим критериям: . Критерий адекватности: адекватное представление характерных черт наблюдае-юй трехмерной сцены при визуальном сравнении ЦМР и самой сцены; . Критерий точности: величина расхождений значений ЦМР и реальных трехмерных оординат сцены, вычисленных в контрольных точках должна быть минимально допус-

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

1. Разработка метода стереоотождветвления (рассмотрено в главах 1,2).

2. Разработка метода построения трехмерной поверхности.

3. Разработка методов анализа и коррекции поверхности.

Карта диспаратностей |_ Вычисление трехмерных координат

Набор трехмерных I*-' ¡Построение регулярной ЦМР точек

ЦМР Автоматическое редактирование ЦМР

Рис.4. Блок —схема метода построения ЦМР

В главе рассмотрены различные формы представления ЦМР и выбрана квад ратная сетка, как наиболее удобная форма с точки зрения реализации разработанкы) методов построения и обработки ЦМР. Рассмотрен метод построения регулярной ЦМР по нерегулярным данным стереоотождествления, блок-схема которого показана не рис.4. На левом изображении выбираются эталоны, центры которых располагаются нг квадратной сетке. В результате процесса стереоотождествления получается набо[ соответствующих точек - на левом, - на правом изображении, для которы) вычисляются трехмерные координаты их прообразов в трехмерной сцене. Вы

числение происходит по стандартным фотограмметрическим формулам с учетом из вестных параметров ориентирования. В результате получается набор трехмерных то чек (Х,У',2)у, ¡=1,...,МХ,]=1,...,МУ, топологически эквивалентный квадратной сетке. Значе ния высот ЦМР вычисляются с помощью билинейной интерполяции высот 3/. Значена в пропущенных узлах интерполируются с помощью метода Шеппарда, в котором ин терполированное значение вычисляется как средневзвешенное значение измеренные данных:

Нц = ^-, где = — , 12цк1 = (Хк1 -X/ + (Уы - У/

тт

<М)

Здесь знак £ обозначает суммирование по тем точкам, которые лежат в окрестное™

интерполируемой точки.

Рассмотрена иерархическая стратегия построения ЦМР (рис.5), при которой последовательно получаются ЦМР с разным разрешением и каждая ЦМР служит для ло-

Задание параметров начальной ЦМР

............

¡Построение начальной ЦМР

Определение начальных приближений

ДЛЯ бОАОО ДОТаЛЬНОЙ ЦМР

кальной оценки размеров области поиска для стереотождествления при построении следующей ЦМР.

Применение данной стратегии ведет к существенному ускорению времени отождествления и построения ЦМР, что показано в табл.2. Из таблицы видно, что при увеличении разрешения ЦМР в два раза, временные характеристики алгоритма увеличиваются не в четыре раза, как было бы, если бы использовалась область поиска с постоянными размерами, а всего лишь в три раза. Экспериментально найдено, что при больших размерах ЦМР (порядка 10е точек), это приводит к общему выигрышу по времени в два раза по сравнению с методом без применения иерархической стратегии.

I

¡Построение детальной ЦМР ¡Проверка и; коррекция ЦМР

Рис.5. Иерархическая стратегия _построения ЦМР_

Разрешение ЦМР, К' Размер по оси X (чиcлJ ячеек) Размер по оси У (число ячеек) Полное время построения • ЦМР, сек Время сте-реоотож: • дествления, сек Число отождествленных точек Скорость стереоотох-;!<эс1 агония точек/сек

200 26 26 27 26 668 22

100 51 51 60 £"8 J 2490 43

50 101 101 199 189 • 10823 52

25 201 201 601 563 43179 77

125 401 401 2036 1881 173427 "1 92

Табл.2 Характеристики алгоритма построения ЦМР с применением иерархической стратегии

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

1)Фильтрация методом бинарных срезов по высоте. Метод состоит из следующих шагов:

•задание текущей высоты: /?к = Ьтах - кЛЬ

.бинаризация ЦМР: = 1, если Нц > /?<,; Ь(1,]) = 0, если Н9</)*

•морфологическая фильтрация бинарного среза Ь(1,Д

•коррекция ЦМР: Ну = й* если элемент Ь(ц) изменился на предыдущем шаге.

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

2) Ранговая фильтрация. Метод состоит в итерационном применении к каждому узлу ЦМР Нд следующих шагов:

•составление вариационного ряда в окрестности узла H,j: Н(ц й Н® ^ ... £ Н<„г) .фильтрация значения высоты: Ну = H(„2ß), если = Н(1} или Н$ = Н(„г)

3) Бикубическая о-фильтрация. Метод состоит в применении к каждому узлу ЦМР Нц следующих шагов:

• Аппроксимация ЦМР в окрестности Rn(iJ) размером пхп бикубической поверхностью вида

Z{x,y)=a0+aix+a2y+a3x2+a4xy+a5y2+a6x3+a7x2y+a8xy2+asy3 Аппроксимация выполняется методом наименьших квадратов.

• Вычисление характеристик (среднее, СКО) отклонения ЦМР от бикубической поверхности

т = \ Z(Ht,-z(XkJ,))2-m2

П (*.')«*„ CV) " (*,0еЛ.(/,У)

• Фильтрация значения высоты с помощью а-фильтра:

Hj = z(0,0), если Hij^m - aa или т + acr<, Нц, где a - параметр, определяющий величину допустимого отклонения значения Нц от поверхности (параметр сглаживания).

4) Сглаживание методом Гоимсона. Метод основан на минимизации функционала E(z), являющегося суммой внутренней и внешней энергий поверхности:

и-ги-\ и-1м-г м-\и-г

= XIte-v-Ц -Ц +ZU+У ~Z<J« +Z-4.,/+.)3 +

/=1 у=о i=o № i=o j»i

i

В работе показано, что данные методы дают хорошие результаты при обработке ЦМР, в том числе - ЦМР, содержащих большое количество аномальных ошибок.

Для учета особенностей ЦМР при обработке, предложен новый метод автоматического анализа геоморфологических черт ЦМР, позволяющий классифицировать особые точки, особые линии и области малой изменчивости рельефа. Метод основан на вычислении информативности небольшой окрестности ЦМР. В качестве показателя информативности выбрано СКО направлений градиентов в точках поверхности (а).

Особые точки рельефа имеют значение а, принимающее локальный максимум. Особые линии рельефа, имеют соответствующую форму на карте информативности. Области малой изменчивости рельефа имеют малое значение а. Знания о геоморфологической структуре ЦМР позволяют существенно повысить эффективность применения фильтров. В методе ранговой фильтрации при составлении вариационного ряда каждое значение высоты берется в количестве, пропорциональном его информативности. В методе бикубической ст-фильтрации, сглаживающий параметр а берется прямо пропорциональным значению информативности, в методе сглаживания по Гримсону в части функционала, соответствующей внешней энергии поверхности, коэффициенты р берутся также пропорционально значению информативности. Все это обеспечивает более сильную фильтрацию в областях малой изменчивости рельефа, а особые точки и линии рельефа остаются практически Неизменными.

Для учета ошибок ЦМР, вызванных геометрическими искажениями из-за рельефа местности, был разработан метод коррекции ЦМР с применением ортофото. Метод основан на том, что если параметры внешнего ориентирования стереопары известны достаточно точно, с помощью данной ЦМР можно сгенерировать два ортофото по двум изображениям стереопары, которые должны быть одинаковы. Различия в двух ортофото могут быть вызваны только ошибками ЦМР. Эти различия измеряются с помощью корреляционного метода стереоотождествления и пересчитываются в поправки к ЦМР. Этот метод можно применять итеративно, то есть после коррекции ЦМР опять генерируются два ортофото, которые снова используются для коррекции ЦМР. Статистика поправок к высотам ЦМР при работе метода показана в табл.3. Из таблицы видно, что на первой итерации устраняется систематическая ошибка высот ЦМР, вторая итерация лишь незначительно изменила высоты ЦМР. Экспериментальное исследование метода показало, что при 2-3 итерациях метода среднее значение поправок высот становится близким к нулю, что позволяет говорить о равномерной сходимости метода. Визуальное сравнение ЦМР до и после коррекции (рис.6) показывает существенное улучшение геоморфологической структуры ЦМР.

В конце главы рассмотрен вопрос о точности получаемых ЦМР. Величина допустимого расхождения высот ЦМР в контрольных точках зависит от точности параметров ориентирования и точности оцифровки изображений. На точность ЦМР влияют в основном ошибки интерполяции, которые существенно ухудшают точность только, в местах со слабой текстурой на изображении. В табл.4 показана точность четырех различных ЦМР, построенных по разным стереопарам, полученным камерой ТК-350. Показа-

но разрешение каждой ЦМР, количество используемых контрольных точек, а также величины среднего и СКО разности высот ЦМР и высот контрольных точек. Разрешение пиксела на местности для используемых изображений равно 9 метров, поэтому из таблицы видно, что данные ЦМР удовлетворяют критерию точности.

Итерация Среднее значение поправок, м. СКО поправок, м

4.9 101

2 0.7 - 63

Табл.3 Статистика поправок к высотам в методе коррекции ЦМР по ортофото.

Название стереопары Разрешение ЦМР м Число контропьньк точек Среднее отклонение, м. СКО м

Каир 100 - 15 ,0,99 3 6

Кавказ 50 12 01 2.1

Турция 200 14 -3.1 7,7 -

Йемен 20 17 -5 7 90

Табл.4 Точность ЦМР

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

1. Обнаружение трехмерных объектов (определение областей на изображении, содержащих объекты);

2. Реконструкция трехмерных объектов (точное восстановление геометрической формы объектов).

В четвертой главе «Обнаружение трехмерных объектов на основе комплекси-рования различных видов данных» поставлена следующая задача обнаружения трехмерных объектов: по исходным данным, включающим в себя: 1) оцифрованные цветные изображения; 2) дополнительные источники информации (ЦМР); 3) априорные знания о размерах объектов, необходимо разработать методы сегментации изображений с целью выделения областей, содержащих объекты. Метод сегментации должен комплексировать различные виды информации, такие как цветные, черно-белые, спектрозонапьные изображения, ЦМР, априорные знания. Решены следующие подзадачи:

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

2. Разработка метода уточнения сегментации областей объектов с помощью ЦМР и априорной информации.

Блок-схема разработанного метода показана на рис.7.

девв -

изображение

[Хроматическое | изображение

Размеченное изображение

■ Маска искусственных | объектов

'■ Изображение |

искусственных

объектов

Преобразовали.-! цветовой модели

К л.К Г.пф|ТК>ЩГЯ

Выбор кластера искусственных

оё^ШзШШШШ

е

,МР

Выделение максимумов на ЦМР

Максимумы | на ЦМР I

Маскирование.

исходного

изображения

'Изображение краев

Выделение ; краев

Проектирование

ЩйййЩрШ®5^

исходное изображение

Маска максимумов ЦМР

)

ШгШвдумШШя

.ЩЩШШЙЁ»:

соответствующих

максимумов, соответст-вующих. зданиям

Морфологическая обработка

Рис.7 Блок—схема метода детектирования искусственных объектов на цветных авиационных снимках.

В данной работе используется предположение, что все объекты, которые необходимо классифицировать, различаются по цвету. Равноконтрастное цветовое пространство 1_*а*Ь*, принятое Международной Комиссией по Освещению в 1931г., специально было сконструировано так, чтобы промоделировать восприятие цвета зрительной системой человека. Чем более похожи два цвета для человека, тем меньше расстояние между ними в пространстве 1_*а*Ь*. Поэтому, естественно ожидать, что одинаково окрашенные предметы образуют в пространстве 1_*а*Ь* отдельные кластеры. В пространстве 1_*а*Ь* координата 1.* характеризует интенсивность цвета. Цветовой тон и насыщенность характеризуются координатами а* и Ь*. Для отделения искусственных объектов от природных в данной работе используется цветовое пространство а*Ь* (без

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

Разработана итерационная процедура классификации, которая на каждой итерации разделяет пространство признаков на небольшое число классов, затем выбирает класс, соответствующий искусственным объектам. Выбранный класс используется на следующей итерации. Задача такой последовательной классификации - получить классы, соответствующие только зданиям и' при этом снизить ошибки классификации.

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

(а) (б) (в)

Рис.8 Обнаружение зданий (а) комбинирование результата цветовой классификации и результата выделения краев; (б) результат наложения областей максимумов ЦМР -искусственные объекты, не являющиеся зданиями, (в)- детектированные здания (вычитание изображений (а) и (б) с последующей морфологической обработкой.

Второй подход использует выделенные области максимумов, соответствующие зданиям, на цифровой модели рельефа. Эти области приближенно указывают класс искусственных объектов. Было разработано три метода выделения областей ЦМР, соответствующих зданиям: 1) Метод бинарных срезов по высоте; 2) Метод нормализации фона; 3) Метод сегментации ЦМР с использованием оператора Марра. Все три метода имеют сходные характеристики по быстродействию.

На рис.8 показан пример работы метода обнаружения объектов.

В пятой главе «Реконструкция трехмерных объектов на основе моделей» поставлена следующая задача реконструкции трехмерных объектов: по исходным данным, включающим в себя: 1) оцифрованные черно-белые изображения; 2) априорные модели трехмерных объектов, заданные в виде набора формальных правил; 3) дополнительные источники информации (ЦМР, параметры ориентирования), необходимо разработать методы обработки изображений с целью обнаружения и реконструкции объектов, удовлетворяющих априорным геометрическим моделям, и получить трехмерную форму объектов при помощи дополнительных источников информации. Решены следующие подзадачи:

1. Разработка метода обнаружения объектов (задача главы 4);

2. Разработка метода выделения характерных признаков объектов;

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

4. Разработка метода реконструкции трехмерной формы объектов.

Ис ХОД11О0 изображение

Знания о моделях

ЦМР

Выделение прямых линий и их атрибутов

Список прямых линий и их атрибутов

Группировка прямых линий

Формирование длинных коллинеарных линий

Формирование параллельных пар

Формирование П —структур

Формирование прямоугольных структур

X

Трехмерная реконструкция-

Рис.9 Блок—схема метода реконструкции трехмерных объектов

]

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

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

Для поиска прямых линий на изображении используется модификация метода выделения областей поддержки линии. Для каждого отрезка I сохраняются следующие атрибуты, в которых содержится достаточно полная информация об исходном изображении: крайние точки (х/, у/, х2', у2'), длина (\1), нормализованные параметры уравнения линии (а', й', с!, где (а)2 + (Ь1)2 = 1), угол между линией и осью абсцисс ( с/), средние яркости в полосе с одной и с другой стороны от линии (// и 1г )■ Положение пикселов полос вычисляется по целочисленному алгоритму Брезенхема.

Для отрезков вводятся следующие операции:"!) 0((хо,Уо),/) - Расстояние между некоторой точкой (х0,у0) и концами отрезка I: 2) £/((Хо,уо),/) - Расстояние между некоторой точкой (Хо.уо) и линией /: 3) Перекрытие между двумя отрезками /»и /2 ( где 11 длиннее 12 ):0\/(Л,/2) - Абсолютное перекрытие; ОУЦЛ,/2) - Относительное перекрытие более длинного отрезка; ОУЭ^иЬ) - Относительное перекрытие более короткого отрезка. 4) Расстояние 0(Л,/2) между двумя отрезками /( и I2: 5) Точка пересечения линий Р(/,,/2), на которых лежат два данных отрезка Л и /г: 6) Относительный угол а(/^/2) между двумя отрезками /* и 1г. 7) Абсолютный угол Д/л/г) между двумя отрезками /(и /2, который определяется следующим образом. Пусть у- индексы (у= 1 или 2) для которых расстояние между точками (х/1, у/1) и (хр,у^) минимально. Тогда, абсолютный угол Д/(,/2) ме>еду двумя отрезками /»и /2 - это угол между векторами Ь* и 12* против часовой стрелки, где

.У'1,~УП 1 ~ Ьз2-, " У!2 Для отрезков вводятся следующие отношения: Близость(/,,/2) = 0(/(,/2) < О*

Коллинеарность^,/2)=| (Л,/2) - | < Ла,' и О\/(/(,/г) < Параллельность^,,/2)=|а(/(,/2)| < и |а(/),/2) - |<4а,'и а(/?,'г)-2 | < 4а/ Перпендикулярность(/,,/2)=| а(/(,/2) - 12 | < <4а2"или | а(/,,/г) - 3 /2 | < Ла2" Угол(/,,/2) = не Параллельность(/,,/2) и 0(Р(/,,/2), /,) < О," и 0(Р(/,,/2), /2) < О," Т-Соединение(/,,/2) = Перпендикулярность^) и не Угал^./г) и ((Р(/,,/2) е I, и Р(/,,/2)г /2)

или (Р(/,,/2) е /2 и Р(/,,/2) г /,)) Здесь О*, Ла,, Лаг, О/ - числовые пороги.

1! =

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

Длинный_отрезок(/,,/2)=(ЩхДу/<),/2)<си„ или ((хЛуг'Ш^/п/л) и Коллинеарность^,,/?)

Дпинный_отрезок{/(,/2...../„)= Параллельность^,//) и OVS(/,//) >s и Коллинеарность(/;,/у), /Jel.r?

Параллельная_пара(/,,/2) = Параллельность(/,,/2) и OVL(/(,/2) > Л и OVS(/,,/2) > /2 и D(/,,/2) > Sm/n П-Структура(/,,/2,/3) = Параллельная_пара(^,/2) и Угол(/,,/3) и Перпендикулярность^,,/э) и П-Форма(/,,/2,/з), где П_Форма(/,,/2,/3) = | Д/,,/э) - Д/3,/() | < 2W

Прямоугольник^,ЛАМ = П-Структура(/,,/2,/3) и П-Структура(/,,/2,/4) и | P(/j,/3) + р(/,,/4) - 2л |<2Ла2" Скат{liJzl&UU) = Прямоугольник(/г,/2,/э,/4) и Параллельностью/г) и Параллельность(/2,/5) и (OVL(/,,/5) > s или OVL(/2,/5) > s) и D(/,,/s) < DQ1J2) и D(/2,/5) < D(/,,/2) Пример результатов группировки отрезков показан на рис.10(а)-(д). Далее происходит трехмерная реконструкция объектов на основе информации о высотах, получаемой из предварительно построенной ЦМР (рис.10(е)).

Рис.10 Группировка отрезков на основе моделей и трехмерная реконструкция. (а) исходное изображение; (б) результат выделения прямых линий; (в) параллельные пары; (г) прямоугольники; (д) модель крыши «скат»; (е) Результат трехмерной реконструкции

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

• высокая (субпиксельная) точность стереоотождествления;

• одновременная коррекция геометрических и яркостных искажений, что позволяет не проводить вычислительно трудоемкий эпиполярный разворот изображений;

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

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

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

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

6.Разработаны новые алгоритмы обработки ЦМР с учетом геоморфологически)! черт рельефа, основанные на локальной фильтрации значений высот, глобальной сглаживании поверхности и более тонкой коррекции ЦМР по ортофото. Алгоритмы

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

7.Предложены процедуры обнаружения искусственных объектов на авиационных изображениях на основе комплексирования различных видов данных, включающих цветную, многозональную и черно-белую съемку, ЦМР, и априорные геометрические характеристики. Показано, что классификация в хроматическом пространстве а*,Ь* позволяет эффективно отделять классы искусственных и природных объектов, что существенно упрощает процесс обнаружения. Применение дополнительной информации, такой как ЦМР и перепады яркости позволяет точно локализовать области, содержащие искусственные объекты. Разработаны методы сегментации ЦМР, позволяющие надежно выделить области, содержащие искусственные объекты.;

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. S.Yu.Zheltov, A.V.Sibiryakov, Adaptive' Subpixel Cross-Correlation in a Point Correspondence Problem II Optical 3D Measurement Techniques, Zurich, 29 September- 2 October, 1997, pp.86-95.

2. S.Yu.Zheltov, A.V.Sibiryakov, Adaptive Subpixel Cross-Correlation Based On Preliminary Segmentation // International Symposium on Real-Time Imaging and Dynamic Analysis, Inteernational Archives for Photogrammetry and Remote Sensing, Hakodate,1998.

3. С.Ю.Желтов, А.В.Сибиряков, Метод субпиксельной корреляции в задаче предельно точного отождествления соответствующих точек стереоизображений, // Юбилейная Научно-Техническая Конференция «Современное состояние и перспективы развития -еодезии, фототопографии, картографии и геоинформационных систем», Тезисы докладов, 24-25 сентября, 1997, Москва, с.81-82.

4. А.В.Сибиряков, Методы автоматического построения трехмерных моделей искусственных пространственных объектов - элементов аэрофотосъемки, II там же, с.85-86;

5. С.Ю.Желтов, А.В.Сибиряков, Методы повышения устойчивости автоматического построения рельефа местности на базе стереофотограмметрической обработки космос-нимков // Тезисы докладов XXXIX Юбилейной Научной Конференции МФТИ «Современные проблемы фундаментальной и прикладной физики и математики», Выл.1, Физика и электроника, г.Долгопрудный, 29-30 ноября 1996г., с.77.

6. А.В.Сибиряков, Методы автоматического построения трехмерных моделей искусственных пространственных объектов - элементов аэрофотосъемки, // там же, с.78.

7. S.Yu.Zheltov, Y.B. Blokhinov, АЛ. Stepanov, A.V.Sibiryakov, Computer 3D Site Mode Generation Based On Aerial Images, II SPIE Proceedings, Vol.3084,1997

8. V.A. Knyaz, A.V.Sibiryakov, The Development Of New Coded Targets For Automated Point Identification And Non-Contact 3d Surface Measurements II International Symposium on Real-Time Imaging and Dynamic Analysis, Inteemational Archives for Photogrammetr) and Remote Sensing, Hakodate,1998.

Личный вклад автора

В работах, опубликованных в соавторстве, соискателю принадлежит теоретическая разработка и экспериментальный анализ метода субпиксельной корреляции [1-3] распространение метода субпиксельной корреляции на случай предварительной сегментации изображений [2], экспериментальное изучение различных методов вычисления информативности изображений [5], разработка метода иерархического стереоото-ждествления [5,7], разработка методов построения и анализа ЦМР [7], разработка методов субпиксельных измерений в задачах короткобазисной фотограмметрии [8].

... -л. ,. .........#

/ / \ * ; 6 '/ V , О

Государственный комитет Российской Федерации по высшему образованию Московский Физико-Технический Институт

На правах рукописи УДК 528 (048).061.8

СИБИРЯКОВ Александр Витальевич

РАЗРАБОТКА МЕТОДОВ МАШИННОГО ЗРЕНИЯ ДЛЯ ПОСТРОЕНИЯ ПРОСТРАНСТВЕННЫХ МОДЕЛЕЙ

ТРЕХМЕРНЫХ СЦЕН

Специальность 05.13.16 - «Применение вычислительной техники, математического моделирования и математических методов в

научных исследованиях»

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель -кандидат технических наук С.Ю.Желтов

Москва -1998

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.............................................................................................................................6

ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ И ПОСТАНОВКА ЗАДАЧ................................. 10

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ........................................................... 13

1. МЕТОД ИЕРАРХИЧЕСКОГО КОРРЕЛЯЦИОННОГО СТЕРЕООТОЖДЕСТВЛЕНИЯ . 17

1.1 ОБЗОР РАБОТ ПО МЕТОДАМ СТЕРЕООТОЖДЕСТВЛЕНИЯ ..................................17

1.2. ПРОБЛЕМЫ, ВОЗНИКАЮЩИЕ ПРИ СТЕРЕООТОЖДЕСТВЛЕНИИ........................19

1.3 ВЫБОР МЕТОДА РЕШЕНИЯ ЗАДАЧИ СТЕРЕООТОЖДЕСТВЛЕНИЯ....................................26

1.4. ВЫБОР НАИБОЛЕЕ УСТОЙЧИВЫХ ИНФОРМАТИВНЫХ УЧАСТКОВ ИЗОБРАЖЕНИЯ ПУТЕМ ЛОКАЛЬНОГО СТАТИСТИЧЕСКОГО АНАЛИЗА.....................27

1.4.1. ВЫЧИСЛИТЕЛЬНО ЭФФЕКТИВНЫЕ ПОКАЗАТЕЛИ ИНФОРМАТИВНОСТИ .... 29

1.4.2. АНАЛИЗ НАЛИЧИЯ СИГНАЛА НА ФРАГМЕНТЕ ИЗОБРАЖЕНИЯ.....................35

1.4.3. ДИСПЕРСИЯ ЯРКОСТИ КАК ПОКАЗАТЕЛЬ ИНФОРМАТИВНОСТИ УЧАСТКОВ ИЗОБРАЖЕНИЙ ...............................................................................................................40

1.5. КОРРЕЛЯЦИОННОЕ СТЕРЕООТОЖДЕСТВЛЕНИЕ С ИСПОЛЬЗОВАНИЕМ ПИРАМИДЫ СТЕРЕОПАР..................................................................................................40

1.6. ОБОБЩЕННАЯ ФОРМА КОРРЕЛЯЦИОННОГО СТЕРЕООТОЖДЕСТВЛЕНИЯ......46

1.7. ПРЕДСТАВЛЕНИЕ РЕЗУЛЬТАТОВ СТЕРЕООТОЖДЕСТВЛЕНИЯ.......................... 50

1.8. ЗАКЛЮЧЕНИЕ К ГЛАВЕ 1................................................................................................................................51

2. МЕТОД СУБПИКСЕЛЬНОЙ КОРРЕЛЯЦИИ В ЗАДАЧЕ ВЫСОКОТОЧНОГО ОТОЖДЕСТВЛЕНИЯ СООТВЕТСТВУЮЩИХ ТОЧЕК СТЕРЕОИЗОБРАЖЕНИЙ...........52

2.1. ОБЗОР МЕТОДОВ СУБПИКСЕЛЬНОГО КОРРЕЛЯЦИОННОГО

СТЕРЕООТОЖДЕСТВЛЕНИЯ............................................................................................52

2.2. ЛИНЕАРИЗАЦИЯ ЗАДАЧИ................................................................................................................................55

2.3. РЕШЕНИЕ ЗАДАЧИ НА ОБОБЩЕННЫЕ СОБСТВЕННЫЕ ЗНАЧЕНИЯ................... 57

2.4. РЕШЕНИЕ ЗАДАЧИ МАКСИМИЗАЦИИ КОРРЕЛЯЦИОННОЙ ФУНКЦИИ................ 62

2.5. ЭКВИВАЛЕНТНОСТЬ СУБПИКСЕЛЬНОЙ КОРРЕЛЯЦИИ И КОРРЕЛЯЦИИ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ..........................................................................................................................64

2.6. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДА СУБПИКСЕЛЬНОЙ

КОРРЕЛЯЦИИ...................................................................................................................... 67

2.7 МЕТОД СУБПИКСЕЛЬНОЙ КОРРЕЛЯЦИИ С УЧЕТОМ ПРЕДВАРИТЕЛЬНОЙ СЕГМЕНТАЦИИ ИЗОБРАЖЕНИЙ ...................................................................................... 75

2.7.1. ВВЕДЕНИЕ РЕЗУЛЬТАТА СЕГМЕНТАЦИИ В МОДЕЛЬ

СТЕРЕООТОЖДЕСТВЛЕНИЯ........................................................... ...........................................75

2.7.2. ЛИНЕАРИЗАЦИЯ ЗАДАЧИ......................................................................................................................77

2.7.3.ПРЕ0БРА30ВАНИЕ КОЭФФИЦИЕНТА КРОСС-КОРРЕЛЯЦИИ..........................77

2.7.4. ПРЕОБРАЗОВАНИЕ МОРФОЛОГИЧЕСКОГО КОЭФФИЦИЕНТА КОРРЕЛЯЦИИ78

2.7.5. МАКСИМИЗАЦИЯ КОЭФФИЦИЕНТА КОРРЕЛЯЦИИ.........................................81

2.8. ЗАКЛЮЧЕНИЕ К ГЛАВЕ 2............................................................................................82

3. ПОСТРОЕНИЕ ЦМР С ПОМОЩЬЮ ИЕРАРХИЧЕСКОЙ СТРАТЕГИИ.........................83

3.1 ОБЗОР МЕТОДОВ ПОСТРОЕНИЯ ЦМР...................................................................... 83

3.2 ВЫБОР МЕТОДА РЕШЕНИЯ ЗАДАЧИ ПОСТРОЕНИЯ ЦМР......................................83

3.3. ПРЕДСТАВЛЕНИЕ ЦМР...............................................................................................85

3.4. ПОЛУЧЕНИЕ ЦМР НА РЕГУЛЯРНОЙ СЕТКЕ.............................................................86

3.5. ПРИМЕНЕНИЕ ИЕРАРХИЧЕСКОЙ СТРАТЕГИИ ДЛЯ СОЗДАНИЯ ЦМР.................88

3.6. ЗАДАНИЕ СТРАТЕГИЙ ДЛЯ РАЗЛИЧНЫХ ОБЛАСТЕЙ ПРИ ПОСТРОЕНИИ ЦМР. 90

3.7. АВТОМАТИЧЕСКАЯ КОРРЕКЦИЯ ЦМР. ФИЛЬТРАЦИЯ И СГЛАЖИВАНИЕ...........91

3.8. ПРИМЕНЕНИЕ ОРТОФОТО ДЛЯ КОРРЕКЦИИ ЦМР................................................97

3.9. АНАЛИЗ ГЕОМОРФОЛОГИЧЕСКОЙ СТРУКТУРЫ ЦМР............................................99

3.10 АНАЛИЗ ТОЧНОСТИ ЦМР........................................................................................103

3.11 ПОСТРОЕНИЕ ЦМР ПУТЕМ ОТОЖДЕСТВЛЕНИЯ В ОБЪЕКТНОМ

ПРОСТРАНСТВЕ..........................................................................................

3.12 ЗАКЛЮЧЕНИЕ К ГЛАВЕ 3...........................................................................................................................107

4. ОБНАРУЖЕНИЕ ТРЕХМЕРНЫХ ОБЪЕКТОВ НА ОСНОВЕ КОМПЛЕКСИРОВАНИЯ РАЗЛИЧНЫХ ВИДОВ ДАННЫХ........................................................................................108

4.1. ОБЗОР РАБОТ ПО ОБНАРУЖЕНИЮ ТРЕХМЕРНЫХ ОБЪЕКТОВ......................... 108

4.2.ВЫБОР МЕТОДА РЕШЕНИЯ ЗАДАЧИ ОБНАРУЖЕНИЯ ТРЕХМЕРНЫХ ОБЪЕКТОВ!09

4.3. ОБНАРУЖЕНИЕ ИСКУССТВЕННЫХ ОБЪЕКТОВ НА ЦВЕТНЫХ АВИАЦИОННЫХ ИЗОБРАЖЕНИЯХ..............................................................................................................111

4.3.1. КЛАСТЕРИЗАЦИЯ В ХРОМАТИЧЕСКОМ ПРОСТРАНСТВЕ.............................111

4.3.2. ДЕТЕКТИРОВАНИЕ ТРЕХМЕРНЫХ ОБЪЕКТОВ С ПОМОЩЬЮ ИТЕРАТИВНОЙ КЛАССИФИКАЦИИ В ХРОМАТИЧЕСКОМ ЦВЕТОВОМ ПРОСТРАНСТВЕ А*,В*.......115

4.3.3. ПРЕОБРАЗОВАНИЯ РОВ-ПРОСТРАНСТВА......................................................118

4.3.4. АВТОМАТИЧЕСКИЙ ВЫБОР КЛАССА ИСКУССТВЕННЫХ ОБЪЕКТОВ.......... 122

4.4. ИСПОЛЬЗОВАНИЕ ДРУГИХ ИСТОЧНИКОВ ИНФОРМАЦИИ ПРИ ДЕТЕКТИРОВАНИИ ИСКУССТВЕННЫХ ОБЪЕКТОВ..................................................125

4.4.1. ИСПОЛЬЗОВАНИЕ ЦМР......................................................................................125

4.4.2. АВТОМАТИЧЕСКОЕ ОПРЕДЕЛЕНИЕ КЛАССА ИСКУССТВЕННЫХ ОБЪЕКТОВ С ИСПОЛЬЗОВАНИЕМ ЦМР..........................................................................................129

4.4.3. ИСПОЛЬЗОВАНИЕ ПЕРЕПАДОВ ЯРКОСТИ...................................................... 130

4.4.4. СОВМЕСТНОЕ ИСПОЛЬЗОВАНИЕ РЕЗУЛЬТАТА КЛАССИФИКАЦИИ, ЦМР, КРАЕВ ДЛЯ ДЕТЕКТИРОВАНИЯ ТРЕХМЕРНЫХ ИСКУССТВЕННЫХ ОБЪЕКТОВ... 131

4.4.5. СОВМЕСТНОЕ ИСПОЛЬЗОВАНИЕ РЕЗУЛЬТАТА КЛАССИФИКАЦИИ И КРАЕВ ДЛЯ ДЕТЕКТИРОВАНИЯ ТРЕХМЕРНЫХ ИСКУССТВЕННЫХ ОБЪЕКТОВ...............133

4.5 ЗАКЛЮЧЕНИЕ К ГЛАВЕ 4...........................................................................................134

5. РЕКОНСТРУКЦИЯ ТРЕХМЕРНЫХ ОБЪЕКТОВ НА ОСНОВЕ МОДЕЛЕЙ................. 136

5.1. ОБЗОР РАБОТ ПО РЕКОНСТРУКЦИИ ТРЕХМЕРНЫХ ОБЪЕКТОВ....................136

5.2. ВЫБОР МЕТОДА РЕКОНСТРУКЦИИ ТРЕХМЕРНЫХ ОБЪЕКТОВ........................138

5.3 ВЫДЕЛЕНИЕ ПРЯМЫХ ЛИНИЙ НА ИЗОБРАЖЕНИИ И УСТАНОВЛЕНИЕ ОТНОШЕНИЙ МЕЖДУ НИМИ..................................................................................................................140

5.3.1. МЕТОД ВЫДЕЛЕНИЯ ПРЯМЫХ ЛИНИЙ И ИХ АТРИБУТОВ ............................ 140

5.3.2. ОТНОШЕНИЯ МЕЖДУ ЛИНЕЙНЫМИ СЕГМЕНТАМИ.......................................145

5.4 ГРУППИРОВКА ПРЯМОЛИНЕЙНЫХ ОТРЕЗКОВ.....................................................147

5.5. ИСПОЛЬЗОВАНИЕ АПРИОРНЫХ МОДЕЛЕЙ..........................................................152

5.6. ИСПОЛЬЗОВАНИЕ ЦМР ДЛЯ ВЫДЕЛЕНИЯ ТРЕХМЕРНЫХ ОБЪЕКТОВ ............. 152

5.7. ЗАКЛЮЧЕНИЕ К ГЛАВЕ 5..........................................................................................152

ЗАКЛЮЧЕНИЕ....................................................................................................................154

СПИСОК ЛИТЕРАТУРЫ....................................................................................................157

ПРИЛОЖЕНИЕ 1................................................................................................................162

ПРИЛОЖЕНИЕ 2.............................................................................................................................................163

ВВЕДЕНИЕ

В последние годы бурно развиваются информационные технологии» предназначенные для модельного представления окружающего мира. Одной из важнейших областей применения таких технологий являются геоинформационные системы (ГИС), обеспечивающие сбор, обработку и отображение пространственных данных. Современные ГИС оперируют с цифровыми моделями трехмерных сцен, которые являются новым способом представления пространственных данных.

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

Одной из важнейших задач при создании цифровых моделей трехмерных сцен является обеспечение их реальными трехмерными данными. Такими данными могут быть как данные дистанционного зондирования, под которыми обычно понимаются авиационные и космические изображения, так и данные ручной фотографической съемки. Космические изображения охватывают большую площадь поверхности Земли (до 400x400 км.), и поэтому могут служить для построения обзорных моделей сцен. Аэрофотоснимки обычно охватывают не большую территорию (примерно 4x4 км.), и поэтому могут быть использованы для построения более детальных трехмерных моделей.

Одними из наиболее сложных и дорогих операций с точки зрения временных затрат являются построение цифровой модели рельефа (ЦМР) а также распознавание и локализация различных трехмерных объектов искусственного происхождения. Из-за больших затрат на обработку данных, автоматизация этих процессов является актуальной проблемой.

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

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

Создание модели трехмерной сцены

Интерактивные методы _

Пслу автомата — веские методы

Визуализация трехмерной сцены | Машинная графика |

Рис.1 Общая концепция создания моделей трехмерных сцен по данным

дистанционного зондирования

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

ОРИЕНТИРОВАНИЕ СНИМКОВ

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

- внутренней С К камеры и СК изображения (внутреннее ориентирование):

- СК разных изображений стереопары (взаимное ориентирование);

- СК камеры и СК наблюдаемой сцены (внешнее ориентирование).

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

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

ВОССТАНОВЛЕНИЕ ЦИФРОВОЙ МОДЕЛИ РЕЛЬЕФА

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

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

- нахождение соответствующих точек стереопары (стереоотождветвление);

- интерполяция поверхности;

- проверка и редактирование ЦМР.

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

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

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

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

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

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

РЕКОНСТРУКЦИЯ ОБЪЕКТОВ

Под реконструкцией объектов понимается получение полной трехмерной модели объекта (в отличие от 2.5-мерного описания).

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

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

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

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

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

1.Обнаружение трехмерных объектов (определение областей на изображении, содержащих объекты);

2. Реконструкция трехмерных объектов (точное восстановление геометрической формы объектов).

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

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

ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ И ПОСТАНОВКА ЗАДАЧ

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