автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Методы поиска соответствий на изображениях трёхмерных сцен

На правах рукописи

Гошин Егор Вячеславович

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

05.13.18 — Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата технических наук

Самара - 2014

005558882

005558882

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)» (СГАУ) на кафедре суперкомпьютеров и общей информатики и федеральном государственном бюджетном учреждении науки Институте систем обработки изображений Российской академии наук.

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

доктор технических наук, профессор Владимир Алексеевич Фурсов

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

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

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

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

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

Защита состоится 12 декабря 2014 г. в 14:00 на заседании диссертационного совета Д 212.215.01, созданного при федеральном государственном автономном образовательном учреждении высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)», по адресу: 443086, г. Самара, Московское шоссе, д. 34.

С диссертацией можно ознакомиться в библиотеке федерального государственного автономного образовательного учреждения высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)» и на сайте http://www.diss.ssau.ru.

Автореферат разослан 5 ноября 2014 г.

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

С.В. Востокин

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

Актуальность

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

Большой вклад в развитие теории и разработку методов и алгоритмов реконструкции трёхмерных моделей по разноракурсным изображениям, в т.ч. для систем технического зрения, внесли отечественные (Гиммельфарб Г.Л., Желтов С.Ю., Ви-зильтер Ю.В., Киричук B.C., Грузман И.С., Гомозов O.A., Кузнецов А.Е., Лукьяни-ца A.A.) и зарубежные (Поллефейсом М, Хартли Р., Циссерман Э, Лонге-Хиггинс К., Форсайт Д., Понс Ж, Маллон Ж., Монассе П. и др.) ученые.

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

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

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

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

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

Результаты исследования соответствуют пунктам 3 - «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий», 4 - «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента», 5 - «Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента» паспорта научной специальности 05.13.18 -Математическое моделирование, численные методы и комплексы программ.

Цель и задачи исследований

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

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

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

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

3. Создание информационной технологии и программного комплекса для реконструкции трёхмерных моделей сцен и построения ЦММ, проведение экспериментальных исследований, оценка качества разработанных методов, алгоритмов и сквозной информационной технологии.

Научная новизна работы

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

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

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

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

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

Практическая значимость работы

Результаты диссертационной работы использованы ОАО «РКЦ «Прогресс» в НИР «Создание высокотехнологичного производства маломассогабаритных космических

аппаратов наблюдения с использование гиперспектральной аппаратуры в интересах социально-экономического развития России и международного сотрудничества». Разработанный программный комплекс являются составной частью разрабатываемого СГАУ и ИСОИ РАН в рамках указанной НИР специализированного программно-аппаратного комплекса обработки гиперспектральной информации и построения 3D-моделей по стереопарам, реализуемого на гибридных высокопроизводительных вычислительных системах. Планируется использование этого программного комплекса для обработки данных, регистрируемых КА «Ресурс-П».

Реализация результатов работы

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

Проекты РФФИ № 12-07-00581, № 13-07-12030 офи_м, № 13-07-13166, проект «Разработка комплекса технологий использования ресурсов суперкомпьютера «Сергей Королёв» в целях развития инновационной и научно-образовательной среды университета», выполненный в рамках Программы развития национального исследовательского университета. По теме диссертации опубликованы 17 работ, в том числе 6 в изданиях, рекомендованных ВАК, 4 работы выполнены автором лично, остальные написаны в соавторстве. Кроме того, получено свидетельство о государственной регистрации программы ЭВМ.

Методы исследования

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

Апробация работы

Основные результаты, связанные с разработкой моделей и алгоритмов поиска соответствий на разноракурсных изображениях в задачах реконструкции трёхмерных цифровых моделей сцен, докладывались на следующих конференциях: «Королёвские чтения» (2011, Самара), «Управление в технических, эргатических, организационных и сетевых системах» (УТЭОСС-2012, Санкт-Петербург), «Image Mining. Theory and Applications» (IMTA-4-2013, Барселона), «llth International Conference on Pattern Recognition and Image Analysis: New Information Technologies» (PR1A-11-2013, Самара), «Актуальные проблемы ракетно-космической техники» (III Козловские чтения, 2013, Самара).

Результаты, связанные с разработкой программного комплекса, докладывались на следующих конференциях: «Научный сервис в сети Интернет: поиск новых решений» (2012, Новороссийск), «Параллельные вычислительные технологии, 2013» (ПаВТ'2013, Челябинск), «Параллельные вычислительные технологии, 2014» (ПаВТ2014, Ростов-на-Дону).

Достоверность результатов

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

Основные положения диссертации, выносимые на защиту:

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

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

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

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

Структура и объём работы

Диссертация состоит из введения, четырёх глав, заключения, списка литературы. Общий объём работы составляет 107 страниц, 25 рисунков, 1 таблица, 2 приложения. Библиографический список насчитывает 82 наименования.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Преобразование координат точки трехмерного пространства М{х,у,г) в координаты на изображении т(и,у) осуществляется в соответствии со следующими соотношениями:

V Г/. 0 "о" / ги гп гп О

т = V ~АГ(Л | ¡)М = 0 Л Г2Х Г22 Г2> Ч

Л ,0 0 и /л гп ГУУ Ч)

ч /

где (г/0,у„) - координаты главной точки относительно начала естественных координат фотоприёмника, т =[н — проективные координаты точки т, а

/.=/>. /,=//*•

Здесь к и И - масштабы вдоль соответствующих осей координат, определяемые расстояниями между ячейками матричного фотоприёмника вдоль строк и столбцов, Л - матрица направляющих косинусов размерности 3x3, описывающая поворот стандартной системы координат относительно глобальной; г — трёхмерный вектор смещения начала координат глобальной системы относительно стандартной; / - фокусное расстояние камеры.

Соответственные точки т, т' на двух проекциях связаны фундаментальной 3x3 -матрицей Р:

(т')тРш = 0, (2)

где

и и' г»

ш = V ш' = V р= К, (3)

1 1 л Ъг

Если известны центры с, с' камер и проекции ш, т' точки М на изображениях первой и второй камеры, координаты точки М в трёхмерном пространстве могут быть вычислены как пересечение лучей (с, т) и (с', т'). Таким образом, центральной в задачах реконструкции ЗО-сцен является задача сопоставления точек на изображениях.

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

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

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

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

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

Во второй главе рассматриваются вопросы построения алгоритмов сопоставления изображений. Рассматриваются два способа задания эпиполярных ограничений. В

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

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

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

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

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

ф=ДХ/*М-4(и'У))2, ф=£|/Л«,у)-/;(и>')|, (4)

V <=1 к=1

где (и,у) и (и'У) - координаты соответствующих точек, заданные в системах отсчёта, связанных с единичными квадратами.

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

В качестве дескрипторов составных фрагментов исследовались также градиенты на этих же элементарных фрагментах. В частности, рассматривались два типа дескрипторов: инвариантные и неинвариантные к повороту.

1. Дескрипторы, инвариантные к повороту. К ним относятся:

- значения интенсивности, в том числе цветные и мультиспектральные:

1к{и^),Гк(иУ), к=Щ, (5)

Рисунок 1 - Пример формирования составных фрагментов

- значения величин (норм) градиентов в заданных точках

|grad 1к (и,у)|, |grad Гк [и',у')|, к =\,Ы. (6)

Достоинство этого типа дескрипторов - простота реализации, т.к. указанные характеристики не зависят от направления эпиполярной линии.

2. Дескрипторы второго типа включают значения градиентов по направлениям:

gradll /Дн,у), gradl: Гк(и',\>'), к = (7)

gradv/'k(u',v'), gradvIk(u,v), . (8)

Это приводит к некоторому усложнению реализации, т.к. при определении соответствий необходимо вычислять ориентацию указанных градиентов относительно направлений эпиполярных линий, однако число ошибочных решений при этом существенно уменьшается. На рисунке 2 приведен пример реконструкции сцены с использованием описанного алгоритма при задании дескрипторов по соотношениям (5, 7, 8).

а б

Рисунок 2 - Исходное (а) и восстановленное (б) изображения

В ситуации, когда направления эпиполярных линий примерно одинаковы (характерно для космических изображений), более подходящим является второй способ учёта эпиполярных ограничений. В данном случае задача состоит в поиске для каждой дискретной точки (и,у) на первом изображении, соответствующей дискретной точке (г/,у') на втором изображении, где (Дм,Ду) - искомый относительный сдвиг. В качестве меры близости будем использовать квадратичную норму: е(и,у, А«,Ау) = ||/(и,у) - /'(и + Аи,у+ Ау)| , (9)

где /(и,у) и /'(м + Ам,у +Ау)— функции распределения яркости отсчётов на этих изображениях.

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

£(«0,у0,Дм,Ду)= ^ а(м,у)е(м,у,Д1/,Ду), (10)

где ¿)(«0,у0) - заданная область вокруг точки (н0,у0).

Эпиполярные ограничения в (10) учитываются в виде множителя и'/ :

^ = ехр= ехрру;^1} , (10

где с1{(и,у'),1') - расстояние от точки (»',у') на втором изображении до эпиполярной

прямой /', соответствующей точке (г<ол'0) на первом изображении, а а,Ь,с - коэффициенты в уравнении эпиполярной прямой а и' + Ь'\>' + с' = 0, определяемые в силу соотношения (2) как а' ~ Щ^и + У0^12 + ^¡з>

= + + (12)

Коэффициент (10), по существу, задает функцию «штрафа» при удалении точки от эпиполярной линии.

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

Е(ив,\'0,Аи,Ау)= £ и>с-и>,-и>/-е(м,у,Д1<,Ду), (13)

(«,»)еС(«0, у„)

где

н;„=ехр{-||(м0,у0)-(м,у)||2}, («,у)бД (14)

\мс = ехр|-||/(м0,У0)- /(м,у)|2|, (н,у)е£>. (15)

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

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

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

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

Экспериментальные исследования разработанного алгоритма проводились на тестовых изображениях. Для экспериментальных исследований использовались изображения из широко известной базы «ТвикиЬа» (Ъttp://www.cvlab■cs.tsukuba.ac.ir>/dataset/tsцkubastereo.php). содержащей 600 разнора-курсных изображений сцен, зарегистрированных в различных условиях. Для оценки качества реконструкции использовались карты диспарантности, также входящие в базу.

Сравнение с наиболее популярным алгоритмом 5!тр1еР1о\у на указанной базе "ТвикиЬа" проводилось для двух видов съёмки: при дневном свете и при освещении направленным светом. Для количественной оценки качества реконструкции использовалось число пикселов карты диспарантности, не являющихся окклюзиями и отличающихся от истинных более чем на 10%.

В таблице 1 приведено Таблица 1 _ Цисло ошибочных соответствий

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

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

Обычно для этой цели применяют алгоритм ЯА^АС, устойчивый к большому числу грубых ошибок в наблюдениях. Однако высокая эффективность этого алгоритма проявляется при достаточно большом числе наблюдений. В диссертации исследовано применение метода согласованной идентификации фундаментальной матрицы по малому числу наблюдений. Задача формулируется следующим образом.

Для одной пары заданных соответствующих точек соотношение (1) является линейным однородным уравнением относительно коэффициентов FIJ, г,_/ = 1,3 фундаментальной матрицы. Для N пар (N > М, М = 8) соответствующих точек (г;,,у ) и (м,',у|) , полагая во всех соотношениях = 1, можно записать переопределённую

систему N неоднородных линейных уравнений вида

у = Хс + ^, (16)

где с - вектор искомых параметров, составленный из коэффициентов фундаментальной матрицы Р:

Условия съёмки Алгоритм с ЭО 81тр1еР1о\у

Дневной свет 19 191 (-8,3%) 21 187 (-9,1%)

Направленный свет 15 645 (-6,7%) 21 088 (-9,1%)

С-^С,, С,, ••■, -[/м 1*12 Ец Г23

а Л'хМ -матрица Х(.М> М, Л/ = 8) и N х 1 -векторы у и ^ определяются как

и[щ «¡V, и\ 1'| -Г V

г/л/, и-, 1/т V, >У = -1 II

"Л "у «ЛГ V -1 А».

Здесь - ошибки, связанные с неточным заданием координат предвари-

тельно сопоставленных точек.

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

Решения, полученные на этих подсистемах, образуют множество 0 оценок:

0 = {с,еЕ, |Е|<С}-

Из этого множества формируются подмножества ©, оценок, либо в виде оценок, принадлежащих подсистемам размерности M<P<N:

©,={с,де©„ |©,|<С£}, |©,|<С£, либо в виде простого задания допустимого числа принадлежащих ему оценок. Для характеристики подмножеств 0, вводится критерий взаимной близости оценок:

где К = С*Р.

Подмножество 0,, для которого принимает минимальное значение, назы-

вают наиболее согласованным. Задача заключается в отыскании этого множества и построении на нем точечной оценки. По существу задача сводится к отысканию индекса / :

IV (I) = тт Щв,). (18)

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

Для каждой подсистемы нижнего уровня, включающей М строк и далее обозначаемой как формируется подмножество подсистем нижнего уровня

©,. путем замены одной из строк подсистемы любой не вошедшей в

неё строкой системы (16).

Для характеристики подсистемы и соответствующего ей подмно-

жества 0, критерий взаимной близости задаётся следующим образом:

Е ..........

.....кт.г'>ф

где с(к],к2.....км) - оценка на подсистеме 5(к,,к2,...,км) ■ Далее решается задача

минимизации критерия (19).

На рисунке 3 приведены графики зависимости средних значений погрешности верных идентификаций от числа аномальных ошибок для различных значений числа оцениваемых параметров (светлый - для метода ИАТЧБАС, тёмный - для метода согласованной идентификации).

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

Четвёртая глава посвящена описанию разработанного программного комплекса.

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

- предварительное сопоставление изображений,

- формирование фундаментальной матрицы,

-точное сопоставление изображений с учётом эпиполярных ограничений.

- формирование карты диспарантности и цифровой модели местности.

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

а)

б)

Рисунок 3 - Средняя погрешность верных идентификаций: а) N=12, М=8; б) N=16, М=8

а)

б)

■ II

I

Рисунок 4 - Число ложных идентификаций на 100 экспериментов: а) N=12, М=8; б) N=16, М=8

г

щвВт

б) в) г)

Рисунок 5 - Тестовая пара «Пентагон»: а, б) исходные изображения, в) карта диспарантности, г) восстановленная ЦММ Был проведён также эксперимент на изображениях, полученных со спутника \VorldView. На рисунках 6а и 66 приведен фрагмент одного (левого) изображения с нанесёнными на нем светлыми линиями, иллюстрирующими величины и направления ошибок сдвигов, найденных при сопоставлении точек на изображениях. На рисунке 6а показан результат предварительного сопоставления, а на рисунке 66 -результат сопоставления с учётом эпиполярных ограничений. Нетрудно заметить, что разработанная технология позволяет значительно снизить число ошибок сопоставления.

Рисунок 6 - Изображения с нанесёнными светлыми линиями, показывающими векторы сдвигов: а) алгоритм 81тр1еР1о\у; б) с эпиполярными ограничениями.

На рисунках 7а и 76 приведены, соответственно, карта диспарантности и трёхмерная модель местности в относительных высотах.

а) б)

Рисунок 7 - а) карта диспарантности, б) восстановленная ЦММ.

Основные результаты диссертации:

Основные результаты диссертации:

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

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

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

4. Создан программный комплекс реконструкции трёхмерных моделей сцен и построения цифровых моделей местности по космическим изображениям, проведены экспериментальные исследования разработанной информационной технологии, показавшие уменьшение ошибок на 10% по сравнению с наиболее эффективным известным алгоритмом сопоставления изображений (8тр1еР1ом'),

Основные результаты опубликованы:

в журналах, рекомендованных ВАК:

1.Гошин Е.В. Моделирование последовательности рельефов по опорным изображениям местности [Текст] / В.А. Фурсов, Е.В. Гошин II Компьютерная оптика - 2011. - Том 35. -№3.-С. 380-384.

2.Гошин Е.В. Метод согласованной идентификации в задаче определения соответственных точек на изображениях [Текст] / В.А. Фурсов, Е.В. Гошин // Компьютерная оптика. - 2012. — Том 36. - № 1. - С. 131 -135.

3. Гошин Е.В. Решение задачи автокалибровки камеры с использованием метода согласованной идентификации [Текст] / В.А. Фурсов, Е.В. Гошин // Компьютерная оптика -2012. - Том 36. -№4. - С. 605-609.

4. Гошин Е.В. Реконструкция ЗО-сцен на пучках эпиполярных плоскостей стереоизображений [Текст] / В.А. Фурсов, С.А Бибиков, Е.В. Гошин // Мехатроника, Автоматизация, Управление - 2013. -№9(150) - С. 19-24.

5.Гошин Е.В. Реконструкция ЗО-сцен по неректифицированным стереоизображениям с прореживающей фильтрацией [Текст] / Е.В. Гошин // Известия Самарского научного центра РАН. - 2013 - Том 15. - №6(3).- С. 748-753.

6.Гошин Е.В. Информационная технология реконструкции цифровой модели местности по стереоизображениям [Текст] / В.А. Фурсов, С.А Бибиков, Е.В. Гошин // Компьютерная оптика. - 2014 - Том 38. - №2. - С. 335-342.

в прочих изданиях:

7. Гошин Е.В. Формирование последовательности карт высот с использованием опорных изображений [Текст] / В.А. Фурсов, Е.В. Гошин // Информатика и вычислительная техника: сборник научных трудов. - Ульяновск: УлГТУ, 2011. - С. 190-193.

L

8.Гошин E.B. Кластерная реализация метода согласованной идентификации [Текст] / Е.В. Гошин // Международная конференция «Королёвские чтения», сборник трудов. - Самара: Издательство СГЛУ, 2011. - С. 277.

9.Гошин Е.В. Параллельная реализация вычислительно трудоемких робастных алгоритмов определения параметров моделей [Текст] / В.А. Фурсов, Е.В. Гошин // Научный сервис в сети Интернет: поиск новых решений: Труды Международной суперкомпьютерной конференции (17-22 сентября 2012 г., г. Новороссийск).- М.: Изд-во МГУ, 2012. - С. 300-306.

10. Гошин Е.В. Гошин Е. В. Метод согласованной идентификации в задаче ректификации изображений [Текст] / Е. В. Гошин // Технические науки: теория и практика: материалы междунар. науч. конф. (г. Чита, апрель 2012 г.). — Чита: Издательство Молодой ученый, 2012. — С. 3-6.

11. Гошин Е.В. Метод согласованной идентификации в задаче слабой калибровки стереоизображений [Текст] / Е.В. Гошин // Материалы Всероссийской научно-практической конференции «Прикладная информатика и компьютерное моделирование» - Уфа: БГПУ им.М.Акмуллы, 2012. — С. 27-29.

12. Гошин Е.В. Эффективная по используемым ресурсам памяти реализация последовательного алгоритма согласованной идентификации [Текст] / В.А. Фурсов, Е.В. Гошин // Материалы конференции «Управление в технических, эргатических, организационных и сетевых системах» - М.:ГНЦ РФ ОАО "Концерн "ЦНИИ "Электроприбор", 2012. -С. 486489.

13. Гошин Е.В. Параллельная реализация модифицированного алгоритма реконструкции трехмерной сцены по стереоизображениям [Текст] / В.А. Фурсов, С.А Бибиков, Е.В. Гошин, Д.А Жердев // Параллельные вычислительные технологии (ПаВТ'2013): труды международной научной конференции - Челябинск: Издательский центр ЮУрГУ, 2013. -С. 624.

14. Гошин Е.В. Conformed Identification of the Fundamental Matrix in the Problem of a Scene Reconstruction, using Stereo Images [Текст] / Image Mining. Theory and Applications. Proceedings of IMTA-4 - Barcellona, 2013. - P. 29-37.

15. Гошин E.B. 3D Scene Reconstruction From Unrectified Stereo Images [Текст] / В.А. Фурсов, Е.В. Гошин // 1 Ith International Conference on Pattern Recognition and Image Analysis: New Information Technologies (PR1A-11-2013). - Samara: IPSI RAS, 2013. - P. 190193.

16. Гошин E.B. 3D реконструкция по космическим стереоизображениям [Текст] / В.А. Фурсов, С.А Бибиков, Е.В. Гошин // Материалы III Всероссийской научно-технической конференции «Актуальные проблемы ракетно-космической техники» (III Козловские чтения) - Самара: СамНЦ РАН, 2013. - С. 191-193.

17. Гошин Е.В. Параллельная CUDA-реализация алгоритма сопоставления стерео-изображений[Текст] / В.А. Фурсов, Е.В. Гошин, А.П. Котов // Параллельные вычислительные технологии (ПаВТ'2014): труды международной научной конференции - Челябинск: Издательский центр ЮУрГУ, 2014. - С. 330-335.

Полученные свидетельства о РИД:

18. Гошин Е.В.. Программный комплекс «СтереоЦМР» / Гошин Е.В. // Свидетельство о государственной регистрации программы для ЭВМ № 2014616002, 2014.

Подписано в печать 10.10.2014 Формат 60 х 84/16. Бумага ксероксная. Печать оперативная.

Объем - 1,0 усл. п. л. Тираж 100 экз. Заказ №156.

Отпечатано в типографии ООО «Инсома-пресс» 443080, г. Самара, ул. Санфировой, 110А; тел.:222-92-40