Содержание к диссертации
Введение
Глава I. Анализ космических съемочных систем предназначенньгх для получения геопространственных данных 13
1.1. Классификация космических съемочных систем 13
1.2. Обзор космических съемочных систем высокого разрешения 14
1.2.1. Космическая съемочная система Ikonos 14
1.2.2. Космическая съемочная система QuickBird 15
1.2.3. Космическая съемочная система Eros-A, Eros-B 17
1.2.4. Космическая съемочная система OrbView-З 20
1.2.5. Космическая съемочная система IRS-P5 (Indian Remote Sensing Satellite-P5)/Cartosat-l 23
1.2.6. Космическая съемочная система Cartosat-2 26
1.2.7. Космическая съемочная система Монитор-Э 29
1.2.8. Космическая съемочная система Ресурс ДК 31
1.3. Обзор космических съемочных систем среднего разрешения 33
1.3.1. Космическая съемочная система SPOT 33
1.3.2. Космическая съемочная система TERRA (платформа ASTER) 39
1.3.3. Космическая съемочная система Landsat 7 42
1.3.4. Космическая съемочная система ALOS 45
1.3.5. Космическая съемочная система "Комета" 50
1.4. Выводы по главе 56
Глава II. Разработка технологической схемы процесса создания цмр и ее обоснование 58
2.1. Обобщенная технологическая схема процесса создания ЦМР 58
2.2. Сканирование и предобработка снимков 59
2.3. Технология взаимного ориентирования космических снимков 61
2.4. Технология использования снимков высокого пространственного разрешения при построении цифровой модели рельефа по материалам космических съемок 67
2.4.1. Учет кривизны Земли 67
2.4.2. Условия совместного использование снимков различного разрешения для повышения точности внешнего ориентирования стереомодели 72
2.4.3. Внешнее ориентирование стереопары с помощью снимка высокого разрешения 73
2.4.4. Внешнее ориентирование стереопары, построенной по снимкам различного разрешения 77
2.4.5. Методика внешнего ориентирования 77
2.5. Геометрическая модель панорамного снимка 80
2.6. Эпиполярное трансформирование 87
2.7. Исследование технологии автоматической корреляции идентичных точек на стереопаре 87
2.8. Построение регулярной ЦМР (регуляризация) и автоматическая коррекция 91
2.9. Выводы по главе 92
Глава III. Разработка метода и алгоритма построения ЦМР по космическим снимкам 94
3.1. Обзор и анализ алгоритмов триангуляции 94
3.1.1. Обзор алгоритмов триангуляции 95
3.1.2. Алгоритм "разделяй и властвуй" (Divide-and-Conquer) 97
3.1.3. Итеративный алгоритм Гибаса и Штольфи 98
3 Л .4. Сравнение алгоритмов 101
3.2. Разработка алгоритма триангуляции на основе выпуклых
оболочек 105
3.2.1. Обобщенный алгоритм триангуляции на основе выпуклых оболочек 105
3.2.2. Анализ алгоритма 106
3.2.3. Алгоритм триангуляции с помощью выпуклых оболочек с учетом организации исходных данных 107
3.2.4. Анализ алгоритма 109
3.3. Алгоритм регуляризации нерегулярной сети высотных точек 109
3.4. Выводы по главе 115
Глава IV. Экспериментальные исследования 116
4.1. Результаты экспериментальных исследований определения элементов внутреннего и внешнего ориентирования космических снимков тестовых стереопар 116
4.2. Результаты исследований алгоритмов триангуляции 132
4.3. Построение ЦМР 139
4.4. Выводы по главе 142
Заключение 144
Список литературы
- Обзор космических съемочных систем высокого разрешения
- Технология взаимного ориентирования космических снимков
- Исследование технологии автоматической корреляции идентичных точек на стереопаре
- Алгоритм "разделяй и властвуй" (Divide-and-Conquer)
Введение к работе
Развитие геоинформационных технологий обусловлено следующими
основными факторами - это развитие средств дистанционного зондирования
Земли, развитие технологий спутникового позиционирования и развитие
методов и алгоритмов обработки данных на основе совершенствования
вычислительной техники [62]. Одним из обязательных слоев
геоинформационных приложений является слой цифровой модели рельефа (ЦМР). Кроме обычного использования ЦМР в картографии [149,164,180,44], можно привести следующие области, где использование геоинформационных технологий и ЦМР позволили получить новые интересные результаты -геология [60], геоморфология [17,18,191], палеогеографические реконструкции в геологии [28], мониторинг современного вулканизма [75], поиск и диагностика астроблем [56], системы гидрологического назначения [27,47,59,64], градостроительная деятельность [43,160], землеустройство нефтепромыслов [41], инженерно-геологический и эколого-геологический мониторинг [30], исследования вегетации растительности [118], задачи классификации [182], техническая инвентаризация [24], диагностика техносферы [80], интернет-ориентированные приложения для хранения пространственной информации [136]. Цифровые модели рельефа могут использоваться либо самостоятельно, либо как высотная основа для ортотрансформирования изображений местности и создания картографической продукции. Для получения ЦМР на большие территории наиболее эффективным решением является обработка космических снимков. Данное исследование посвящено разработке технологии использования снимков высокого пространственного разрешения при построении цифровой модели рельефа по материалам космических съемок на примере обработки данных космической системы «Комета».
Актуальность постановки и решения научно-технической проблемы
подтверждается следующими факторами:
1 .Отсутствием на настоящий момент эффективной и производительной технологии построения ЦМР с использованием совместной обработки космических снимков различного пространственного разрешения.
Данные систем высокого разрешения позволяют создавать ЦМР с характерной точностью до 0.5-2 пиксела снимка (Ikonos - СКОь=7м, шаг 30 м по орбитальным данным и с субпиксельной точностью до 0.5-3.0 м при использовании GPS точек [114,199], SPOT-5 - CKOh=5M [140] ). По снимкам с разрешением более 10 м (среднего разрешения) возможно создание ЦМР с точностью 1-2 пиксела при внутренней точности менее пиксела [199]. Стандартное программное обеспечение не позволяет одновременно обрабатывать снимки различного разрешения, что является препятствием для получения субпиксельной точности при обработке снимков среднего разрешения.
2. Наличием большого архива космических снимков среднего разрешения, в том числе и снимков системы «Комета», который может быть использован для построения ЦМР.
На настоящий момент накоплен огромный архив снимков среднего разрешения, которые могут быть использованы для построения цифровых моделей рельефа. Материалы космических съемок покрывают большую часть земного шара [111]. В связи с большими характеристическими временами изменения рельефа данный архив может быть успешно использован для целей получения ЦМР. Одним из достоинств космической системы «Комета», позволивших выбрать её в качестве источника данных для разрабатываемой технологии, является наличие в ее составе камеры высокого разрешения КВР-1000 и камеры среднего разрешения ТК-350, что позволяет наглядно продемонстрировать технологию использования снимков
высокого разрешения при построении ЦМР по снимкам камеры ТК-350 для повышения точности получаемой ЦМР.
3. Совершенствованием методов и средств, в том числе технических,
построения цифровых моделей рельефа.
Построение ЦМР на большие территории - сложная вычислительная задача, требующая обработки больших объемов информации. Для примера, объем отсканированного с разрешением 14 мкм снимка камеры ТК-350 составляет 870 Мб. До недавнего времени обработка таких объемов информации была возможна только на специализированных рабочих станциях. На настоящий момент развитие вычислительной техники привело к тому, что возможно организовать обработку вышеуказанных объемов информации на настольной персональной системе. Кроме" того, эффективность обработки в первую очередь зависит не от вычислительной мощности компьютера, а от способа организации обработки информации и примененных алгоритмов обработки. Для обработки указанных объемов информации необходимо применение специализированных алгоритмов с минимальной оценкой вычислительной сложности - не более 0(п2),где п -количество обрабатываемых точек.
4. Наличием большого спроса на цифровые модели рельефа для целей
картографии, связи, экологии, ГИС-приложений.
Цифровые модели рельефа могут использоваться как отдельный слой ГИС-приложения, или самостоятельно для ортотрансформирования снимков*(см. выше). Для ортотрансформирования снимков высокого разрешения (снимки с разрешением менее 2 м, например снимки КВР-1000 имеют разрешение 2 метра, снимки Ikonos, Quick Bird имеют разрешение Іметр и до 0.6 метра соответственно) и имеющих характерные углы наклона не более 15 градусов, точность используемой ЦМР должна быть не хуже 10 м по высоте (СКО), что позволяет использовать ЦМР, полученную по снимкам среднего разрешения
при условии использования разработанной технологии повышения точности ЦМР.
Цель работы - разработка и исследование компьютерной технологии, позволяющей эффективно создавать ЦМР на большие территории при совместной обработке космических снимков различного пространственного разрешения на примере данных системы «Комета».
Задачи исследования
Исследование искажений снимков, построение эффективных процедур автоматизации процесса внутреннего ориентирования.
Разработка методик и алгоритмов внешнего ориентирования стереомодели, обеспечивающих повышение точности внешнего ориентирования путем совместной обработки снимков разного разрешения.
Разработка алгоритмов поиска одноименных точек на снимках стереопары, позволяющих увеличить скорость обработки данных большого объема. Для эффективной обработки больших объемов данных оценка времени работы алгоритма (верхняя оценка) не должна превышать 0(п2). Алгоритмы поиска одноименных точек должны обеспечивать субпиксельную точность отождествления и критерии для определения успешности отождествления.
4. Разработка методов получения регулярной ЦМР по нерегулярному
набору точек.
Методы исследований. Перечисленные задачи решены методами вычислительной математики, математического моделирования и математического программирования.
Научная новизна 1. Разработаны метод и алгоритм повышения точности внешнего ориентирования на основе использования совместной обработки снимков
различного разрешения, отличающиеся от существующих большей точностью.
Разработана геометрическая модель панорамного снимка, используемая в алгоритме повышения точности внешнего ориентирования и при ортотрансформировании снимков с панорамной и сканерной геометрией, отличающаяся от существующих простотой реализации без потери точности модели.
Разработан новый алгоритм триангуляции нерегулярной сети высотных точек на основе выпуклых оболочек, отличающийся от существующих большей устойчивостью за счет учета особенностей исходных данных, получаемых в процессе стереоотождествления.
Практическая значимость работы
1. На основе разработанного алгоритма повышения точности внешнего
ориентирования разработана программа геометрической привязки:
космических снимков «Комета».
2. Разработана программная реализация модели панорамного снимка,
позволяющая использовать ее как в процедуре повышения точности
внешнего ориентирования стереомодели, так и для
ортотрансформирования одиночных снимков.
Разработана программная реализация алгоритма поиска одноименных точек.
Разработана программа построения нерегулярной сети высотных точек, входящая в состав программного пакета для получения ЦМР по снимкам ТК-350.
Разработана программа; регуляризации нерегулярной сети высотных точек.
Доказана высокая эффективность совместного использования снимков с различной геометрией и пространственным разрешением при выполнении фотограмметрических работ.
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений.
В главе 1 рассмотрены особенности существующих космических съемочных систем, предназначенных для получения геопространственных данных. Проанализированы типы искажений, присущие исходным данным. Обоснован выбор данных системы «Комета» как информационной основы для отработки технологии использования снимков высокого пространственного разрешения при построении цифровой модели рельефа по материалам космических съемок.
В главе 2 рассмотрена структура технологического процесса, позволяющего решить поставленные задачи. Описаны методы взаимного ориентирования, позволяющие учесть специфические особенности исходных данных в процессе взаимной обработки снимков с различными параметрами внутреннего ориентирования - камер ТК-350 и КВР-1000. Процесс приведения к единой системе эпиполярных изображений модифицирован для снимков с различными параметрами внутреннего ориентирования. Предложены две методики повышения точности внешнего ориентирования, использующие совместную обработку стереопары среднего разрешения и снимка высокого разрешения - для первой методики, и построение стереопары из снимков различного разрешения - для второй методики. Приведено описание геометрической модели панорамного снимка (КВР-1000, Ikonos, QuickBird), используемой в методике повышения точности внешнего ориентирования и при ортотрансформировании панорамных снимков. Проанализированы методы поиска взаимнооднозначных точек на снимках стереопары - алгоритмы корреляции. Для обработки исходных данных большого объема сформулированы критерии для синтеза алгоритма корреляции - скорость работы, достоверность работы и субпиксельная точность работы. По данным критериям синтезирован алгоритм корреляции.
В главе 3 описаны результаты анализа методов построения нерегулярных сетей высотных точек и получение регулярной ЦМР по данным точкам. Описан разработанный алгоритм триангуляции высотных точек и проведен анализ его производительности.
В главе 4 приведены результаты экспериментальных исследований разработанных методик и алгоритмов. Показаны результаты исследований искажений исходных данных, подтверждена эффективность процедур автоматизации внутреннего ориентирования и приведены точности процедур внутреннего ориентирования. Для тестовых районов приведены результаты внешнего ориентирования по стандартной методике и по разработанной методике повышения точности ориентирования. Приведены результаты тестирования геометрической модели панорамного снимка. Тестирование проводилось путем создания ортотрансформированных изображений снимков камер КВР-1000 и Ikonos. Рассмотрены результаты исследований алгоритмов корреляции и построения ЦМР.
В заключении перечисляются основные результаты диссертационной работы и формулируются необходимые выводы.
На защиту выносятся:
Методы и алгоритмы повышения точности внешнего ориентирования с использованием совместной обработки снимков различного разрешения.
Геометрическая модель панорамного снимка, используемая в алгоритме повышения точности внешнего ориентирования и при ортотрансформировании снимков с панорамной и сканерной геометрией.
Критерии синтеза алгоритма поиска одноименных точек и алгоритму синтезированный по данным критериям.
Разработанный алгоритм построения нерегулярной сети высотных точек - алгоритм триангуляции.
Разработанный алгоритм регуляризации нерегулярной сети высотных точек.
Основные положения и результаты диссертационной работы
докладывались на:
4-ой Международной конференции «Методы дистанционного зондорования
и ГИС-технологии для контроля и диагностики состояния окружающей
среды» МИИГАиК, г. Москва, 21-23 декабря 1998 г;
4-ой научно-практической конференции «Современные проблемы
фотограмметрии и дистанционного зондирования» г. Москва, 28-29 октября
2003 г. ее 28-29;
Третьей учебно-практической конференции "Проблемы ввода и обновления
пространственной информации" Москва, 23-27 февраля 1998 г.;
Научно-технической конференции " Russian Concept and Technology of
Satellite Remote Sensing and Cartography" " г. Сеул, Южная Корея, 3 марта
2001г., рр 31-58;
Международном симпозиуме ISPRS «International Symposium on Resource and
Environmental Monitoring» в г. Хайдарабаде, Индия, 3-6 декабря 2002г.
Материалы диссертационных исследований опубликованы в 5 статьях в периодических научных изданиях, 4 публикациях в виде тезисов докладов. Отдельные результаты теоретических и экспериментальных исследований отражены в отчетах по научно-исследовательским работам и материалах опытно-конструкторских работ.
Обзор космических съемочных систем высокого разрешения
В настоящее время существует ряд оптических космических систем дистанционного зондирования Земли, данные с которых позволяют построить цифровые модели рельефа, данные большинства из них доступны в России [40,49]. Главной особенностыо данных систем является возможность получения снимков Земли со стереоперекрытием. Для целей данного исследования целесообразно классифицировать данные системы по : пространственному разрешению на местности [31]. По данному критерию космические системы можно разделить на системы высокого разрешения - с -, разрешением на местности 2 и менее метров [19], системы, среднего разрешения — с разрешением от 2 до 30 метров и системы с разрешением более 30 метров - системы низкого разрешения [9,21,22,23]. Данное разделение достаточно условно, однако оно отражает возможность использования разработанной технологии использования снимков высокого разрешения при построении ЦМР. Для снимков высокого разрешения (при внутренней субпиксельной точности для снимков Ikonos и QuickBird [171]) возможно непосредственное использование высокоточных GPS измерений в процессе построения ЦМР [197,199,201]. Для снимков среднего разрешения целесообразно использование разработанной технологии использования снимков высокого разрешения и высокоточных GPS измерений. Данные систем низкого разрешения использовать в фотограмметрических системах построения ЦМР нерационально, так как точность получаемых ЦМР сравнима с точностями ЦМР, полученных радиолокационным методом
[200,211] и имеющихся в свободном доступе, например, данные Shuttle Radar Topographic Mission (SRTM) [97,137,138,176]. К наиболее распространенным системам высокого разрешения можно отнести следующие системы: иностранные - Ikonos, QuickBird, EROS-A,EROS-B, OrbView-3 [98,196], IRS-P5, Cartosat-2, Монитор-Э, Ресурс-ДК1, Formosat-2 [14,150], Kompsat-2 [187,197]. К наиболее распространенным спутникам среднего разрешения можно отнести следующие спутники: SPOT, Landsat-7, ASTER (TERRA) [99], ALOS [102,103,120,125], отечественная система «Комета» [96,97,99].
Спутник IKONOS [106] (см. рис. 1.1) запущен 24 сентября 1999 года на синхронно-солнечную орбиту с периодом обращения 98 минут на высоту приблизительно 680 километров [203]. Время прохождения одной и той же территории 10:30 ежедневно. Спутник IKONOS может обеспечивать съемку заданной местности с периодом в 3 дня. . Спектральные диапазоны: 1-метровый черно-белый (панхроматический) - 0.45 - 0.90 мм. 4-метровый мультиспектральный Голубой: 0.45 - 0.52 мм Зеленый: 0.51 - 0.60 мм Красный: 0.63 - 0.70 мм Ближний ИК: 0.76 - 0.85 мм.
Система IKONOS обеспечивает динамический диапазон данных 11 бит. Так как сенсоры системы могут обеспечивать 1-метровые панхроматические и 4-метровые мультиспектральные снимки [84,85] с отклонением от надира до 60 градусов по любому азимуту, то стерео возможности обеспечиваются как вдоль, так и поперек траектории [124].
Стерео данные системы IKONOS Стерео возможности системы IKONOS [82,114] обеспечиваются тремя особенностями: возможность наклонной съемки по любому азимуту, отношение (В/Н) от 0.6 и более (сходное с аэроснимками) и высокое разрешение. Возможность наклонной съемки обеспечивает стереоскопическое изображение при съемке с различных орбит, : как у системы SPOT-HRV, так же как и возможность стереосъемки вдоль траектории как у систем SPOT-HRS, JERS-1. Стереоснимки IKONOS распространяются как квази-эпиполярные [192], где оставлен только-высотный параллакс. Доступ к описанию точной геометрической модели сенсора затруднен, поэтому для обработки как одиночных снимков, так и стереопар используется модель рациональных полиномиальных коэффициентов (Rational polynomial coefficients - RPC) [71,100,112,113,114,129,132,174]. Сравнение результатов обработки с использованием точной и приближенной моделей снимков Ikonos приведено в [73,181,213]. В настоящее время предложены различные алгоритмы получения ЦМР по данным системы Ikonos [209]. Существующие методы обработки стереопар системы Ikonos позволяют получать угловую точность 1-2 градуса и позиционную точность до 1 пиксела [194].
Спутник QuickBird-2 [106] (см. рис. 1.2) предназначается для съемки поверхности Земли с разрешением 60 см в черно-белом режиме и 2,5 м в мультиспектральном режиме что уже сравнимо с характеристиками снимков цифровых аэросъемочных комплексов [1]. Спутник построен компанией Ball Aerospace & Technology, его владельцем является компания Earth Watch. Основные характеристики спутника [154] приведены в таблице 1.1.
Технология взаимного ориентирования космических снимков
Радиометрические харктеристики: Диапазон оптических плотностей от О до 3.41ogD (4.0 log Dmax ) Исходные материалы: Цветные или черно-белые изображения, прозрачные или непрозрачные позитивные или негативные плоские или катушечные снимки. Область сканирования : 330 х 440 мм (13 х 17.3 дюймов) с низким разрешением 280 х 440 мм (11 х 17.3 дюймов) с высоким разрешением. Устройство для сканирования пленок уменьшает область сканирования до: 252 х 246 мм (9.9 х 9.7 дюймов) при высоком разрешении 264 х 246 мм (10.4 х 9.7 дюймов) при низком разрешении. Глубина цвета: 3 х 12 бит на АЦП и 3 х 16 бит в программном обеспечении. Технология сканирования: Планшетный CCD сканер Массив CCD с 3 х 6000 элементов Технология с подвижной по х-у CCD-матрицей Геометрические параметры: Геометрическая точность +/- 2мкм. Оптическое разрешение: 5мкм (высокое разрешение) 29мкм (низкое разрешение). Пользователь может выбрать выходное разрешение в пределах от 5мкм до 500мкм. Выходные форматы:ТТРТ, TIFF16, EPS, DCS, RAW, PostScript формат.
В соответствии с [32] величина элемента геометрического разрешения вычисляется P=0.4/R, где R-разрешающая способность исходного снимка. Для снимков ТК-350 с оптическим разрешением 38-80 линий/мм разрешение-сканирования должно составлять 5-11 мкм, однако практически было выяснено, что сканирование с разрешением менее Юмкм приводит к значительному увеличению шумов из-за появления зернистости изображения» и значительному увеличению размера файла. Сканирование осуществляется с разрешением 14 мкм (для особо точной обработки может быть использовано разрешение сканирования 8 мкм) [117]. Данная аппертура сканирования при стандартной высоте полета соответствует разрешению на местности 9-11 метров. Сканирование снимков может осуществляться любыми Г фотограмметрическими сканерами [58], обеспечивающими не худшие результирующие параметры. Внутреннее ориентирование снимков осуществляется для каждого снимка стереопары - левого и правого в следующей последовательности: 1. задание типа камеры для снимка (обобщенных параметров камеры); 2. коррекция параметров камеры (фокусного расстояния, аппертуры сканирования ) если необходимо; 3. задание системы координат снимка.
Для снимка ТК-350 возможно задание либо обобщенных параметров камеры, либо калиброванных значений, определяемых для каждого снимка по результатам наземной обработки. Для каждого снимка определяются параметры подвижки. Для одного запуска определяются параметры дисторсии объектива. И отдельно для каждого маршрута определяются положение главной точки и калиброванное значение фокусного расстояния камеры.
Взаимное ориентирование осуществляется в соответствии с моделью камеры центральной проекции [46].
Стереопара может быть составлена из снимков, имеющих область перекрытия, но взятых с разных запусков, в этом случае параметры камеры для левого и правого снимков стереопары могут различаться. Для учета данного факта алгоритм взаимного ориентирования доработан для снимков камер с разным фокусным расстоянием.
Получение ЦМР высокой точности возможно при использовании снимков высокого разрешения, геометрические свойства которых хорошо известны. Геометрические свойства снимка камеры ТК-350 детально изучены и представляют собой снимки камеры центральной проекции. Однако разрешение снимка 9-11 метров на местности накладывает ограничения на точность получаемых ЦМР [36,37,76]. В связи с этим задача использования в паре со снимком камеры ТК-350, обладающего хорошо известными геометрическими свойствами, снимка высокого разрешения является весьма перспективной. Рассмотрим условия получения стереомодели по стереопаре, образованной снимком камеры ТК-350 и снимком камеры КВР-1000. При вычислении параметров ориентирования необходимо учитывать разные фокусные расстояния камер, кроме того, для снимка КВР-1000 неизвестно расположение главной точки. Все эти особенности необходимо учитывать при взаимном ориентировании снимков [167]. Причем данными особенностями обладают и снимки высокого разрешения других камер.
Исследование технологии автоматической корреляции идентичных точек на стереопаре
Для минимизации объема обработки при поиске одноименных точек необходимо приведение снимков стереопары к эпиполярным [87,146,157], что позволяет свести к минимуму влияние углов разворота снимков стереопары и использовать простые алгоритмы выделения ключевых точек [152]. В этом случае поиск одноименных точек осуществляется только вдоль і одной строки, что позволяет использовать одномерное окно поиска в процедуре поиска одноименных точек, упрощается процедура" ." субпиксельного уточнения, за счет решения не двумерной задачи [52], а " аналогичной одномерной задачи. Кроме того, наблюдение в стереорежиме эпиполярной стереопары наиболее комфортно для оператора.
Задача поиска идентичных точек на изображениях, составляющих стереопару [81,83,88,89,94] имеет большое практическое значение для использования в системе построения ЦМР по космическим снимкам среднего и высокого разрешения. Космические снимки обладают рядом особенностей: большой размер, невысокое значение отношения сигнал/шум [116]. Размерность задачи накладывает особые требования на вычислительную сложность алгоритма [90,91], которая для данной задачи может достигать 0(N5) [142]. Для процедуры автоматической корреляции были сформулированы критерии синтеза алгоритма поиска одноименных точек снимка, позволяющие минимизировать вычислительную сложность [54,189]. К ним относятся: Минимальная сложность функции, задающей меру близости двух изображений Объем перебора при поиске наилучшего соответствия двух изображений Стратегия поиска (полный перебор - О (Mlsf), пирамидальные слои, градиентный поиск в среднем В соответствии с этими критериями был разработан алгоритм поиска одноименных точек. В качестве стандартных мер близости используют различные нормы: норма LI = ExsRF(x+h)-G(x) норма L2 = (SxeR[F(x+h)-G(x)]2),/2 нормализованная кросс-корреляция
Минимальной вычислительной сложностью обладает норма L1.
Для минимизации объема перебора при поиске решения возможно использование алгоритма SSDA sequential similarity detection algorithm (SSDA) [153] , который только оценивает ошибку для каждого вектора диспаратности. Однако использование алгоритма SSDA не позволяет принять решение о приемлемости найденного решения. Для оценки найденного решения используется функция нормализованной кросс-корреляции [183,204], позволяющая по значению коэффициента корреляции судить о достоверности решения. При этом значение функции вычисляется только для небольшого окна оценки, что уменьшает вычислительные затраты. В зависимости от размеров окна оценки вычисляется пороговый коэффициент корреляции (см. рис. 2.6.). . Зависимость порогового коэффициента корреляции от размера образца Для данной задачи требуется субпиксельная точность. Рассмотрены три способа субпиксельного уточнения: аппроксимация параболоидом - точность СКО=0.025-0.044 пиксела [172] (см. рис. 2.7.),
Субпиксельное уточнение (аппроксимация) параболоидом, адаптивная субпиксельная кросс-корреляция (adaptive subpixel cross-correlation) [210], Субпиксельное уточнение (аппроксимация) параболоидом, адаптивная субпиксельная кросс-корреляция (adaptive subpixel cross-correlation) [210], к(Р) = yZdf(x,y)g(xl,yl) X/W)-;yr S s2(wi)- fe: (х,У) \1 .У) (2) для которой максимизируется выражение p = arg max k(p) (3) адаптивная корреляция методом наименьших квадратов [119] (Adaptive Least Squares Correlation). Для синтеза алгоритма используется аппроксимация параболоидом, обладающая по сравнению с адаптивная корреляцией методом наименьших квадратов (Adaptive Least Squares Correlation) и адаптивной субпиксельной кросс-корреляцией ар е subpixel cross-correlation) меньшей вычислительной сложностью и точностью порядка 0.05-0.125 пиксела. Блок-схема алгоритма приведена на рис. 2.8. Космическая система «Комета» позволяет получать стереопары с различным перекрытием (см. Таблицу 1.4), что приводит к значительным вариациям размеров окна поиска. Учет данного факта позволил минимизировать объем перебора при поиске наилучшего соответствия двух изображений [175]. Для космической системы «Комета» синтезированный алгоритм позволяет получить следующие результаты: 1 .Использование алгоритма последовательного алгоритма обнаружения подобия значительно увеличивает скорость обработки (до 10 раз по сравнению с методом корреляции), однако приводит к увеличению числа ошибочных определений. 2.Использование фушщии оценки позволяет отбрасывать данные ошибочные определения. 3.Метод субпиксельного уточнения найденного решения позволяет получить точность порядка 0.1-0.01 пиксела. 4.Введение геометрических ограничений значительно уменьшает область поиска. Точность и эффективность разработанного алгоритма была оценена на реальных данных космической системы «Комета».
Алгоритм "разделяй и властвуй" (Divide-and-Conquer)
Выбрать при обходе по ходу часовой стрелки крайнюю точку si другой строки Исключить si из списка точек строки Создать ребро оболочки Цикл по всем крайним точкам всех строк Если крайняя точка строки s[i] левее ребра, То Удалить текущее ребро Добавить ребро el : начало - точка s, конец- новая крайняя точка строки Исключить s[i] из списка точек строки Текущее ребро := el Иначе Текущее ребро := следующее ребро Конец Цикла Конец цикла //Шаг 2 Цикл по всем выпуклым оболочкам Образовать замкнутый полигон из оболочки_і и оболочки_і+1 Триангуляция замкнутого полигона Конец цикла Конец алгоритма Поскольку при формировании выпуклых оболочек каждая точка включается в оболочку только один раз, время работы первого шага алгоритма будет оцениваться в худшем случае 0(N). Для шага 2 триангуляция сводится к триангуляции замкнутого полигона, и при ее реализации методом "разделяй и властвуй" [105] оценка составит 0(N log(N)) . В худшем случае этот метод приводит к времени работы 0(N log(N)). Суммарная оценка времени работы алгоритма составляет 0(N log(N)) по наибольшей оценке первого шага, где N - число точек.
В значительном числе фотограмметрических и ГИС приложений необходимо использовать регулярную сетку точек с заданными параметрами качества, такими как шаг и точность [38,131,135]. По результатам построения триангуляционной сети высотных точек мы получим лишь нерегулярную сеть, в которой решена задача определения близости точек, что позволяет, используя локальные алгоритмы[5], построить регулярную сетку высот (в дальнейшем называемой цифровой моделью рельефа - ЦМР) [126] для заданной области интереса [206]. Большой объем данных, получаемый по снимкам космических систем, требует использовать максимально быстрые линейные алгоритмы, с минимальной оценкой времени работы [145].
Простейшим алгоритмом построения ЦМР на основе триангуляционной сети высотных точек является аппроксимация ЦМР набором плоскостей, проходящих через узлы триангуляции [57]. Данный метод использует естественное разбиение триангуляционной сети на множество непересекающихся треугольников и то факт, что три пространственные точки единственным образом определяют плоскость в пространстве.
Для плоскости, проходящей Через Три ТОЧКИ (Xi,ybZi) (X2,y2,Z2)-(X3,y3,Z3) можно записать условие компланарности трех векторов. Таким условием является равенство нулю их смешанного произведения [33]. Смешанное -произведение вычисляется с помощью определителя третьего порядка, строками которого являются координаты векторов в ортонормированном базисе. Для построения гладкой поверхности, можно использовать сплайн-интерполяцию [5] или полиномиальную функцию, проходящую через заданные точки [145]. Однако даже для минимальной функции, например, описанной уравнением (7) [79], Z = fi + f2 (x-x0) + ҐЗ (У-УО) + f4 (x-x0)2 + f5 (x-x0) (y-yo) + f6 (y-y0)2 (7) необходимо определить шесть коэффициентов уравнения (7), для чего необходимо задать не менее шести точек, через которые проходит полиномиальная поверхность. В триангуляции можно использовать тот факт, что количество точек для заданного треугольника и соседних треугольников, прилежащих к его сторонам равно шести (см. рис. 3.6).
В результате составления и решения системы уравнений (8) по шести точкам - вершинам текущего треугольника и смежных с ним треугольников определяются коэффициенты уравнения (7). АХ = В, где (8) А = 1 (ХІ-ХО) (Уі-уо) (Хі-хо)2 (ХІ-Х0) (УІ-УО) (УІ-УО)2 І XT=f1f2f3f4f5f6 Вт = Zi z2 z3 z4 z5 z6 I Систему (8) необходимо решить относительно коэффициентов полинома Х = АТВ(9)
Данный подход позволяет провести гладкую поверхность через заданный треугольник триангуляционной сети, однако обладает двумя отрицательными особенностями: 1. для определения коэффициентов полинома необходимо решить систему линейных уравнений, что ведет к значительным вычислительным затратам [35]; 2. построение гладкой поверхности для заданного треугольника не ведет автоматически к построению гладкой поверхности на сети треугольников, так как отдельные функции совпадают на вершинах треугольников, но плохо сшиваются на границах треугольников. Для обеспечения общей гладкой поверхности необходимо дополнительно уравнивать границы треугольников, в результате генерация ЦМР не может быть осуществлена только локальными функциями и необходимо использовать глобальные для всей ЦМР методы, что не всегда возможно с точки зрения используемых вычислительных ресурсов. Для построения гладкой поверхности можно использовать метод взвешенной интерполяция по ближайшему соседу, аналогичный методу интерполяции Гаусса (при р=2 формулы совпадают).
Использование данной формулы интерполяции позволяет построить гладкую поверхность, проходящую через вершины треугольника (для построения поверхности используем только вершины треугольников). Однако по-прежнему на ребрах смежных треугольников не удается обеспечить требуемую гладкость. Для обеспечения гладкости на ребрах треугольника необходимо предпринять дополнительные меры. Для этого построим собственно границы смежных треугольников и будем использовать эти границы как дополнительные точки, обеспечивающие гладкость интерполяции на ребрах смежных треугольников. Построение границы треугольника можно произвести методом билинейной интерполяции по четырем точкам, для того чтобы обеспечить учет поверхности смежного треугольника.
