Содержание к диссертации
Введение
Глава 1. Кластерный анализ спутниковых снимков земной поверхности (неконтролируемая классификация) 17
1.1 Теоретические основы кластерного анализа 18
1.1.1 Описание предметной области 18
1.1.2 Классическое решение поставленной задачи 19
1.2 Общая структура алгоритмов кластерного анализа 25
1.2.1 Объединение объектов 26
1.2.2 Объединение кластеров 29
1.2.3 Классификация образов 31
1.3 Определение качества кластеризации 35
1.4 Обзор существующих методов кластерного анализа 38
1.5 Основные результаты и выводы по главе 45
Глава 2 Новые алгоритмы кластерного анализа 47
2.1 Алгоритм кластеризации признакового пространства гиперсферами 48
2.2 Алгоритм декомпозиции гистограмм 52
2.3 Экспериментальное сравнение эффективности работы алгоритмов кластерного анализа 59
2.4 Основные результаты и выводы по главе 65
Глава 3 Алгоритмы текстурного анализа космических снимков (контролируемая классификация) 67
3.1 Общие определения и понятия 67
3.2 Этапы проведения текстурного анализа 70
3.2.1 Определение цели текстурного анализа 71
3.2.2 Выбор информативных спектрально-текстурных признаков 71
3.2.2.1 Проблема выбора размера скользящего окна 71
3.2.2.2 Принцип формирования признаков на основе матрицы смежности 73
3.2.2.3 Система текстурных признаков 75
3.2.2.4 Анализ информативности признаков по критерию минимума эмпирического риска 79
3.2.3 Применение метода контролируемой классификации 82
3.3 Параметрический алгоритм текстурного анализа, основанный на аппроксимациях сплайнами 83
3.4 Непараметрический алгоритм текстурного анализа 89
3.5 Основные результаты и выводы по главе 95
Глава 4 Программное обеспечение дешифрирования спутниковых снимков земной поверхности 97
4.1 Обзор программных продуктов для контролируемой и неконтролируемой классификации 98
4.1.1 ENVI 98
4.1.2 ERDAS Imagine 103
4.1.3 Idrisi32 106
4.1.4 ER Mapper 107
4.2 Обоснование необходимости создания нового программного продукта 108
4.3 Описание разработанного программного продукта 109
4.3.1 Подпрограмма кластерного анализа ПО
4.3.2 Подпрограмма текстурного анализа 115
4.3.3 Режимы вывода результатов на экран 121
4.4 Стандартизация программы по ГОСТ 127
4.5 Основные результаты и выводы по главе 128
Глава 5 Примеры решения практических задач спутникового мониторинга земной поверхности и облаков 130
5.1 Структурирование видеоданных Большого Васюганского Болота 130
5.2 Распознавание типов облачных полей 140
5.3 Мониторинг схода снежного покрова 145
5.4 Мониторинг паводковой обстановки на территории Томской области 153
5.5 Основные результаты и выводы по главе 160
Заключение 162
Список литературы 165
Приложение
- Общая структура алгоритмов кластерного анализа
- Экспериментальное сравнение эффективности работы алгоритмов кластерного анализа
- Параметрический алгоритм текстурного анализа, основанный на аппроксимациях сплайнами
- Обоснование необходимости создания нового программного продукта
Введение к работе
Актуал ьность
Дистанционные методы изучения растительности, почв, экосистем и геосистем интенсивно разрабатываются с 50-х годов XX века. Начиная с середины 60-х годов получили развитие новые виды съемки (тепловые, радиотепловые, спектрометрические, радарные и т. п.). Затем с конца 60-х годов большой вклад в развитие дистанционных методов внесла разработка космических методов землеведения [1]. Применение спутниковых данных имеет большие преимущества по сравнению с контактными методами исследований. Во-первых, в отличие от контактных методов исследования земной поверхности спутниковые приборы оцифровывают за один раз территорию земной поверхности в несколько десятков тысяч квадратных километров, что позволяет в течение одного дня наблюдать и анализировать огромную площадь Земной поверхности, к тому же большая часть этой территории недоступна для контактных методов исследования. Во-вторых, высокая периодичность обращения спутников вокруг Земли позволяет вести оперативный мониторинг за состоянием природных экосистем практически в режиме реального времени. В-третьих, в отличие от аэрофотосъемки спутники охватывают большое количество природных комплексов на одном изображении, например, Большое Васюганское болото, что позволяет исследователю выявлять новые закономерности изменения природных сред. Благодаря этим и многим другим преимуществам дистанционные методы исследования подстилающей поверхности Земли (ППЗ) и облаков завоевали большую популярность в научном мире.
Дистанционные методы, как правило, являются косвенными, то есть с их помощью измеряют не интересующие нас параметры объектов, а некоторые связанные с этими объектами величины. В качестве таких величин при съемке с самолета или искусственного спутника Земли (ИСЗ) регистрируют
7 отраженное от объекта излучение в различных спектральных диапазонах — оптических, инфракрасных и микроволновых. [2]
Использование отраженного излучения при применении методов дистанционного зондирования стало возможным благодаря различной отражательной способности разных типов 11113 и облаков. Поэтому использование
отражательной способности для различных типов поверхности и различных
»
участков спектра — это ключ к распознаванию деталей на спутниковых изображениях Земли. Так, например, отражательная способность зеленой растительности мала в видимой части спектра и велика в ближней инфракрасной (ПК) области. В то время как отражательная способность свежевыпавшего снега велика (98%) в оптическом диапазоне и гораздо меньше в ИК-области. Это позволяет компьютеру уверенно отделить снег и растительность друг от друга. Мало того, более низкая отражательная способность старого и влажного снега (примерно 45%) позволяет отделить его от свежевыпавшего. А использование диапазона 1.55 — 1.65 мкм позволяет уверенно отделить снег от облаков. [3] Здесь приведены наиболее очевидные случаи отделения одних типов поверхности от других, но часто бывают ситуации, когда не все так однозначно. В этих случая целесообразно использовать соотношение нескольких спектральных диапазонов для более точного разделения типов 11113. Поэтому сейчас запускаются спутники с многоспектральной аппаратурой. К таким спутникам относятся NOAA, EOS, Terra, Aqua, LANDSAT, SPOT, Pecypc-Ol и
др.
При работе над диссертацией были использованы снимки двух спутников NOAA и Terra. Остановимся на них поподробнее.
ИСЗ серии NOAA предназначены в основном для наблюдений атмосферы, но информация с них может успешно использоваться для изучения суши и океана. В настоящее время на орбите функционируют несколько спутников этой серии. В нашей работе были использованы данные прибора AVHRR. Этот прибор является одним из трех основных приборов на борту
8 спутников серии NOAA. Он предназначен для спектрального исследования метеорологических, океанографических и гидрологических параметров через измерения излученной или отраженной радиации в пяти спектральных поло-сах. Разрешающая способность прибора 1.1x1.1 км в надире. Угол сканирования прибора ±55, полоса обзора около 3000 км, поэтому за один проход спутника удается получить информацию с поверхности около 3000x7000 км. Прибор имеет 5 спектральных каналов: 1-ый канал — 0,58-0,68 мкм (красный участок спектра), 2-ой канал - 0,72-1,1 мкм (ближний ИК), 3-ий канал - 3,55-3,93 мкм (участок ИК-диапазона, оптимальный для измерения излучения лесных и других пожаров), 4-ый канал — 10,3-11,3 мкм (канал для измерения температуры поверхности суши, воды и облаков), 5-ый канал — 11,5-12,5 мкм (используется также, как и 4-ый канал). На спутниках NOAA, начиная с 15-го, установлен дополнительный канал, работающий в диапазоне 1.55-1.66 мкм для распознавания снега и льда.[3, 4]
Радиометр MODIS (спутники Terra и Aqua) обеспечивает получение данных, необходимых для изучения глобальных биологических процессов на поверхности Земли и в нижних слоях атмосферы. Для этого предусмотрена возможность измерения температуры поверхности суши и моря, анализа характеристик светимости хролофилла, плотности растительного и снежного покровов, контроля распределения облачности над поверхностью суши. Число спектральных диапазонов — 36. Общий перекрываемый участок спектра 0.4 — 14.4 мкм. Разрешающая способность прибора различна для разных диапазонов. Ширина полосы обзора — 2300 км.
Данные описанных выше спутников были использованы для структурирования Большого Васюганского болота, проведения мониторинга схода снежного покрова и разлива рек и др. Естественно, что для эффективного выполнения этих задач необходимо использование специальных алгоритмов и программ. Нами было проведен обзор наиболее популярных программных продуктов обработки спутниковых изображений (ERDAS, ENVI, Idrisi, ER
9 Mapper). Выявленные недостатки этих программных пакетов, которые заключаются в использовании алгоритмов дешифрирования спутниковой информации, не имеющих строгого математического обоснования и требующих от пользователя задания порогов, не позволяют учитывать специфику анализируемых данных. Кроме того, рассмотренные программные продукты не позволяют проводить детальную работу с классами. В связи с этим, развитие алгоритмов и программного обеспечения для дешифрирования спутниковых изображений является актуальной задачей.
Цели работы и задачи исследования
Целью диссертационной работы является создание новых более эффективных алгоритмов кластерного и текстурного анализа для дешифрирования спутниковых снимков, а также разработка программного обеспечения для выполнения дешифрирования спутниковых снимков алгоритмами контролируемой и неконтролируемой классификации. Для достижения поставленной цели необходимо решить следующие задачи:
Провести критический анализ современного состояния методов дешифрирования космических снимков.
Создать алгоритмы кластерного и текстурного анализа спутниковых изображений земной поверхности.
Разработать программное обеспечение для контролируемой и неконтролируемой классификации космических изображений.
Решить практические задачи космического мониторинга земной поверхности и облаков.
Методы исследований
Для решения задач, сформулированных в диссертационной работе, использовались методы теории вероятности и математической статистики, современные методы дистанционного зондирования различных объектов и явлений окружающей среды, методы текстурного и кластерного анализа, поли-
10 номиальные сплайны и результаты научных исследований отечественных и зарубежных ученых (Н.Г. Загоруйко, С.А. Айвазян, А.А. Потапов, Robert М. Haralick, J.T. Той, R. С. Gonzalez и др.).
Научную новизну, полученных в работе результатов, определяют:
Алгоритмы кластерного анализа спутниковых снимков, отличающиеся от известных алгоритмов наличием динамического порога принятия решения о принадлежности вектора наблюдаемых величин кластеру.
Алгоритм текстурного анализа, основанный на модифицированном ядре Епанечникова, отличающийся использованием единого параметра сглаживания для всех размерностей данных при анализе пространства текстурных признаков.
Алгоритм текстурного анализа, отличающийся использованием кубического сплайна для аппроксимации функций распределения текстурных признаков, не попавших в «узлы» функции распределения.
Расширенная система информативных текстурных признаков, являющаяся обобщением известных в литературе признаков, используемая алгоритмами текстурного анализа.
Алгоритм поиска подмножества наиболее информативных текстурных признаков, являющийся обобщением существующих алгоритмов «Add» и «Del» усеченного перебора признаков, основанный на минимизации среднего риска.
Степень достоверности результатов работы
Достоверность полученных результатов определяется строгостью используемых математических методов, удовлетворительным совпадением результатов, полученных с помощью предложенных алгоритмов и ранее известными алгоритмами, качественным совпадением результатов с картографической информацией.
Практическая ценность и реализация результатов работы
Практически значимыми являются новые алгоритмы кластерного и текстурного анализа: алгоритм декомпозиции гистограмм, алгоритм построения в признаковом пространстве гиперсфер, непараметрический алгоритм с модифицированным ядром Епанечникова и параметрический алгоритм, основанный на аппроксимации функции плотности вероятности кубическим сплайном. Кроме этого практическую ценность представляет и разработанный программный продукт Analyser, который используется для мониторинга состояния природных комплексов и решения ресурсно-экологических задач.
Основные положения, выносимые на защиту:
Новые алгоритмы кластерного анализа спутниковых снимков земной поверхности, позволяющие проводить кластерный анализ в среднем в 3.5 раза быстрее одного из лучших алгоритмов ISODATA при сохранении того же качества распознавания изображений.
Новые алгоритмы текстурного анализа космических снимков земной поверхности и облаков, которые на основе обучающей информации эксперта позволяют дешифрировать изображение на указанное количество классов.
Программный комплекс «Analyser», в котором реализованы новые алгоритмы дешифрации, позволяющий проводить контролируемую и неконтролируемую классификацию спутниковых изображений и просматривать результаты работы программы в удобных для пользователя режимах.
Внедрение работы
Разработанный программный продукт внедрен в ООО «Агрохимсер-вис» (г. Новосибирск), в институте «Кибернетический центр» ТПУ (г. Томск), в НИИ экологического мониторинга (г. Барнаул), в институте водных
12 и экологических проблем СО РАН (г. Барнаул), о чем свидетельствуют акты, приведенные в приложении А.
Результаты работы программы использовались департаментом водной службы главного управления природных ресурсов по Томской области, Томской базой авиационной охраны лесов, институтом космических исследований (республика Казахстан), лесной службой главного управления природных ресурсов и охраны окружающей среды России по Томской области, что подтверждается актами, приведенными в приложении Б.
Апробация работы
Проверка эффективности работы алгоритмов кластерного анализа осуществлялась в ходе обработки реальных спутниковых снимков.
Основные результаты работы докладывались и обсуждались на следующих конференциях и симпозиумах: региональная научно-техническая конференция «Радиотехнические устройства, информационные технологии и системы управления» (Томск, 2001); VII Join International Symposium. «Atmospheric and ocean optics. Atmospheric physics» (Иркутск, 2001); международная конференция «Моделирование, базы данных и информационные системы для атмосферных наук» (Иркутск, 2001); IX Международный симпозиум «Оптика атмосферы и океана. Физика атмосферы» (томск, 2002); Международная конференция «ENVIROMIS-2002» «Измерения, моделирование и информационные системы как средства реабилитации окружающей среды на городском и региональном уровне» (Томск, 2002); III Международный симпозиум «Контроль и реабилитация окружающей среды» (Томск, 2002); научно-техническая школа-семинар студентов, аспирантов и молодых специалистов «Информационные системы мониторинга окружающей среды» (Томск 2002); Ninth Joint International Symposium on Atmospheric and Ocean Optics. Atmospheric Physics.(ToMCK, 2002); X Joint International Symposium «Atmospheric and ocean optics. Atmospheric physics» (Томск 2003); всероссийская на-
13 учно-техническая конференция (Томск 2004); II Всероссийская научно-практическая конференция студентов (Томск, 2004); Вторая Всероссийская конференция по дистанционному зондированию земных покровов и атмосферы аэрокосмическими средствами (Санкт-Петербург 2004); XI Joint International Symposium «Atmospheric and ocean optics. Atmospheric physics» (Томск 2004); Международная конференция по измерениям, моделированию и информационным системам для изучения окружающей среды ENVIROMIS (Томск, 2004); IV международный симпозиум «Контроль и реабилитация окружающей среды», (Томск 2004), XII международный симпозиум «Atmospheric and ocean optics. Atmospheric physics» (Томск 2005).
По результатам работы имеется 22 публикации, из них 6 статей, в том числе одна в рецензируемом журнале.
Личный вклад
Постановка задачи, цели исследования и методы исследования были определены руководителем Мицелем Артуром Александровичем совместно с Протасовым Константином Тихоновичем.
Алгоритм кластеризации признакового пространства гиперсферами и формирование системы текстурных признаков на основе литературных источников выполнено лично автором.
Алгоритмизация алгоритмов текстурного и кластерного анализа выполнена совместно с Протасовым К.Т.
Разработка программного обеспечения Analyser для дешифрирования спутниковых изображений выполнена лично автором, за исключением алгоритма декомпозиции гистограмм и расчета коэффициентов кубического сплайна, которые были закодированы Протасовым К.Т.
Применение программы Analyser для решения ресурсно-экологических задач выполнено совместно с Загорулько В.А. и Протасовой В.П.
Содержание работы
Диссертационная работа состоит из введения, пяти глав, заключения, списка используемых литературных источников и приложений. Работа содержит 60 рисунков и 5 приложений. Список используемой литературы содержит 106 источников. В диссертационной работе принята двойная нумерация формул и рисунков: первая цифра указывает на номер главы, а вторая — это порядковый номер рисунка, или формулы в данной главе.
В первой главе рассматриваются известные методы и алгоритмы кластерного анализа. В начале главы излагаются теоретические основы методов кластерного анализа. В качестве классического подхода к разбиению спутникового изображения на некоторое число кластеров приведен ЕМ-алгоритм. Этот двух итерационный алгоритм лежит в основе большинства методов и алгоритмов кластерного анализа. Рассмотрены наиболее популярные методы и алгоритмы кластерного анализа, такие как метод іС-средних, метод ближайшего соседа, метод самого дальнего соседа, алгоритм «FOREL», алгоритм ISODATA и. др. Проанализированы преимущества и недостатки изложенных методов.
Во второй главе предложены новые алгоритмы кластерного анализа: алгоритм кластеризации признакового пространства гиперсферами и алгоритм декомпозиции гистограмм. Предложенные алгоритмы используют динамический порог, который учитывает особенности данных и вычисляется заново каждый раз при создании нового кластера. Проведено экспериментальное сравнение эффективности работы новых алгоритмов кластерного анализа с одним из лучших алгоритмов ISODATA. При распознавании одного и того же снимка алгоритм построения гиперсфер затратил меньше всего времени на кластеризацию и при этом показал лучшее качество распознавания.
В третьей главе рассматриваются алгоритмы текстурного анализа. Даны основные понятия и определения по теме. Приведены этапы проведения текстурного анализа. Проведен анализ проблемы выбора размера скользящего окна. Рассмотрен принцип формирования признаков на основе матрицы смежности. Из различных литературных источников сформирована система из 16 текстурных признаков. Рассмотрена проблема выбора информативных признаков и предложен оригинальный комбинированный алгоритм выбора оптимального подмножества признаков, который отбирает признаки исходя из вектора плана экспериментов, заданного пользователем.
Приведены оригинальные алгоритмы текстурного анализа: параметрический алгоритм, основанный на аппроксимации функции плотности вероятности кубическим сплайном и непараметрический алгоритм, использующий модифицированное ядро Епанечникова.
В четвертой главе рассмотрены наиболее популярные программные продукты для обработки и анализа спутниковой информации, которые содержат этапы контролируемой и неконтролируемой классификации. Описаны их преимущества, недостатки и функциональные возможности. Приведено обоснование необходимости разработки нового программного продукта Analyser. Описаны оригинальные подсистемы кластерного и текстурного анализа. Также подробно описана подсистема вывода результата на экран, основанная на различных режимах работы с дешифрированным изображением. Проведена стандартизация программы Analyser по ГОСТ 28195-89.
Пятая глава отражает примеры использования программного продукта Analyser для решения различных задач ресурсно-экологического мониторинга. Используя подпрограмму текстурного анализа программы Analyser, была проведена предварительная дифференциация Большого Васюганского болота в междуречье рек Кенги, Парбига, Тартаса, Ичи на естественные географические единицы — ландшафты и их составные элементы. С помощью подсистемы кластерного анализа, было проведено структурирование всей
территории Большого Васюганского болота. В рамках проведенной работы дана краткая характеристика Большого Васюганского болота. Показана необходимость использования спутниковой информации для структурирования территории Большого Васюганского болота.
Приведен пример отделения облаков от подстилающей поверхности Земли с оценкой площади подстилающей поверхности, занимаемой облаками с выделением классов «облака», «разорванная облачность», «снег» и др. Показана возможность применения программы Analyser в метеорологии. Рассмотрен пример использования программы для решения проблемы обнаружения грозовых полей на сплошной облачности.
Приведен результат мониторинга схода снежного покрова на территории Томской области, который был проведен весной 2004г. и мониторинг паводковой обстановки на основных и малых реках Томской области (весна 2004г.). Проведенный мониторинг позволил своевременно выдать предупреждение о разливе рек штабу ГО и ЧС.
Благодарности
Автор выражает глубокую и искреннюю благодарность своим научным руководителям д. т. н., проф. Мицелю Артуру Александровичу и с.н.с. к.т.н. Протасову Константину Тихоновичу за помощь, оказанную при работе над диссертацией. Автор благодарит сотрудников кафедры АСУ ТУСУР и лаборатории распространения оптических сигналов ИОА СО РАН за ценные замечания и советы.
Общая структура алгоритмов кластерного анализа
В задачах анализа видеоинформации требуется обрабатывать большие и сложные изображения, которые имеют размеры порядка 512x512 — 2048x2048 и более дискретных элементов. Для более эффективного и быстрого кластерного анализа больших изображений мы предлагаем следующий подход, состоящий из трех этапов (рис. 1.1):
На первом этапе мы предлагаем выделить несколько наиболее характерных фрагментов на изображении, и на них сформировать множество мелких кластеров. Таким образом, все виды различных наблюдений будут представлены при формировании кластеров, но при этом мы избавим алгоритм от просмотра большого количества однообразной информации. На этом этапе необходимо определить метрику, позволяющую объединять отдельные наблюдения в кластеры. Различные виды таких метрик представлены в параграфе 1.2.1.
На следующем этапе мы предлагаем провести попарное укрупнение имеющихся кластеров. Этап заканчивается при достижении желаемого пользователем числа кластеров (если этот параметр задан явно), либо при выполнении некоторых заданных в алгоритме условий. Здесь необходимо определить метрики объединения двух кластеров. Различные виды таких метрик представлены в параграфе 1.2.2.
И, наконец, на третьем этапе происходит классификация всех оставшихся наблюдений. Для этого нужно определить вид решающей функции, которая отнесет некоторое рассматриваемое наблюдение к одному из имеющихся кластеров. Различные виды решающих функций представлены в параграфе 1.2.3.
В частном случае описанной структуры второй этап может отсутствовать, тогда при распознавании всей совокупности данных используют кластеры, созданные на первом этапе, без применения к ним этапа укрупнения.
Наиболее трудным и наименее формализованным в данной задаче является определение понятия однородности объектов. В большинстве случаев понятие однородности объектов задается введением правила вычислений расстояния p(xjtXj) между любой парой объектов исследуемого множества {х,,х2,...,х„}. Если задана функция p(xitXj), то близкие в смысле этой метрики объекты считаются однородными, принадлежащими к одному классу. Естественно, при этом необходимо сопоставление р(х;.,ху) с некоторым пороговым значением, определяемым в каждом конкретном случае по-своему.
При задании функции расстояния мы должны помнить о необходимости соблюдения следующих естественных требований: требования симметрии /?(х,,ху.) = р(ху,х.), требования максимального сходства объекта с самим собой /?(х,.,х.) = тахр(х,.,х ).
Конечно, выбор метрики является узловым моментом исследования, от которого решающим образом зависит окончательный результат разбиения объектов на классы при заданном алгоритме разбиения. В каждой конкретной задаче этот выбор должен производиться по-своему. При этом решение данного вопроса зависит в основном от главных целей исследования, физической и статистической природы вектора наблюдений х, полноты априорных сведений о характере вероятностного распределения х.
В качестве примеров расстояний и мер близости, сравнительно широко используемых в задачах кластерного анализа, приведем здесь следующие: метрика махалонобисского типа
В общем случае зависимых компонент дс1, 2,.- " вектора наблюдений х и их различной значимости в решении вопроса об отнесении объекта (наблюдения) к тому или иному классу обычно пользуются обобщенным (взве шенным) расстоянием махалонобисского типа, задаваемым формулой следующего типа где Е-1 — обратная ковариационная матрица генеральной совокупности, из которой извлекаются наблюдения х,, а Л — некоторая симметричная неотрицательно-определенная матрица "весовых" коэффициентов, которая чаще всего выбирается диагональной.
Следующие три вида расстояний являются частными случаями метрики рм(х-,ху.), но все же засуживают специального описания.
Понятие близости объектов при использовании евклидова расстояния совпадает с понятием геометрической близости в п -мерном пространстве. В этом случае считается, что компоненты х1,х2,...,х" вектора наблюдений х однородны по своему физическому смыслу, причем установлено, например, с помощью опроса экспертов, что все они одинаково важны с точки зрения решения вопроса об отнесении объекта к тому или иному классу.
Экспериментальное сравнение эффективности работы алгоритмов кластерного анализа
Сравнительный анализ алгоритмов кластеризации был проведен при обработке 20 спутниковых изображений Томской области размером 982x891 пиксель. Для анализа использовались снимки прибора AVHRR спутника NOAA. В алгоритме построения гиперсфер в качестве значения константы, задаваемой пользователем, было задано число 12. В алгоритме декомпозиции гистограмм окончательное количество кластеров для дешифрирования было установлено равным 100. В обоих алгоритмах для одного и того же снимка использовались одинаковые фрагменты для обучения размером 50x50 пикселей. Таким образом, алгоритмы были поставлены в равные условия при самообучении. Для алгоритма ISODATA для всех снимков были заданы одни и те же значения входных параметров, которые были подобраны автором после большого количества экспериментов. Количество кластеров — 100; минимальное количество точек в кластере — 10; среднеквадратичное отклонение в кластере — 1; компактность кластера — 0.8; максимальное количество пар центров для объединения - 1; количество итераций — 2.
На рис. 2.3 показано время работы каждого алгоритма (в секундах), необходимое на дешифрирование спутникового изображения. Из рисунка видно, что самым быстрым алгоритмом был алгоритм построения гиперсфер. Его среднее время 29 секунд. Алгоритм ISODATA потратил время в среднем на полторы минуты больше - 105 секунд (1 минута 45 секунд). Медленней всех оказался алгоритм декомпозиции гистограмм. Его средний результат - 8 минут 7 секунд. Это объясняется необходимостью высчитывать расстояние между всеми точками на этапе самообучения. Анализ показал, что для увеличения скорости работы этого алгоритма необходимо уменьшить размер фрагментов, выбираемых для самообучения. Использование 11 фрагментов размером 32x32 пикселя для самообучения позволило увеличить скорость работы алгоритма примерно в 7 раз (35 секунд), и ошибка кластеризации при этом была 7.6%.
На рис. 2.4 представлены средние ошибки кластеризации для каждого алгоритма, которые рассчитывались по формуле: і ,v все-таки, немного лучше алгоритма ISODATA (ошибка равна 5.5%). У алгоритма декомпозиции гистограмм среднее качество немного хуже (ошибка равна 8.2%), но вполне приемлемо для дешифрирования спутниковых изображений. Для иллюстрации качества работы алгоритмов ниже приведен снимок спутника NOAA и результат кластеризации каждого алгоритма.
На рис. 2.5 приведен исходный снимок NOAA-14, использованный для дешифрирования, а на рис. 2.6-2.8 приведены результаты работы различных алгоритмов с изображением на рис. 2.5. Анализ рис. 2.6-2.8 показал, что представленные здесь алгоритмы кластерного анализа показывают очень хорошее качество кластеризации. Результаты дешифрирования практически не отличаются от оригинала. Лишь очень сильно приглядевшись можно отличить исходное изображение от результата применения алгоритма кластерного анализа. Например, алгоритм построения гиперсфер не очень точно передал переход от сплошной облачности к чистой атмосфере, а алгоритм декомпозиции гистограмм отнес часть облачной дымки к растительности (середина левого края). Автор не считает это серьезной ошибкой и абсолютно уверен, что ситуация легко поправима добавлением еще одного или нескольких фрагментов проблемных мест для самообучения. 1. Предложены новые алгоритмы кластерного анализа: алгоритм кластеризации признакового пространства гиперсферами и алгоритм декомпозиции гистограмм. Новые алгоритмы используют динамический порог, который высчитывается каждый раз при создании нового кластера. 2. Приведен сравнительный анализ эффективности новых алгоритмов кластерного анализа. Для сравнения с существующими алгоритмами по качеству и времени кластеризации использовался один из самых лучших алго ритмов кластерного анализа — ISODATA. Анализ эффективности показал, что новый алгоритм построения гиперсфер и по качеству и по быстродействию лучше общепризнанного алгоритма ISODATA.
Параметрический алгоритм текстурного анализа, основанный на аппроксимациях сплайнами
Получивший в последнее время широкое распространение метод аппроксимации функций с помощью сплайнов, ввиду линейности модели по параметрам в сочетании с высокой точностью аппроксимации, может быть использован для восстановления вероятностных распределений по выборочным данным.
Пусть результатом наблюдения является совокупность оцифрованных полей видеоданных, заданных в нескольких спектральных диапазонах, так что каждый пиксель изображения подстилающей поверхности Земли и облачности, зафиксированный системой регистрации, характеризуется случайным вектором х = (х1,...,х") , XGR". Компоненты х\ / = 1,...,п вектора наблюдения х характеризуют отражательные (радиояркостные) свойства ландшафтов и облачности в каждом спектральном диапазоне соответственно. Перед началом работы алгоритма эксперт или учитель задает Nv обучающих выборок Xj,... eSv для каждого класса, то есть Nv — объем выборки класса v. Заранее оговоримся, что поиск оптимальной подсистемы текстурных признаков аналогичен подобной процедуре в непараметрическом алгоритме с использованием модифицированного ядра Епанечникова (см. п. 3.4).
Для того чтобы создать аппроксимацию функции плотности вероятности кубическим сплайном необходимо построить, определенное с точностью до параметров, преобразование где 0 — вектор параметров, 0єЛ , который переводит случайный вектор хєі?" с функцией распределения F(x) и функцией плотности /(х) в случайный вектор у є Rm с функцией распределения G(y) и функцией плотности g(y), причем G(-) и g(-) предполагаются известными. После чего неизвестная функция плотности случайной величины х находится стандартным образом где Z)# (-)/fct —якобиан преобразования (3.1). Здесь для простоты предполагается п = т. Для построения преобразования случайного вектора х = (х\...,х") в у є R" [45, 46] определим непрерывные условные функции распределения ім х х1,...,х 1)\ следующим образом
Преобразование (3.3) переводит случайный вектор х в вектор z с независимыми равномерно распределенными на квадрате [0,1],...,[0,1] координатами. На втором этапе зададим строго возрастающие функции распределений G,(У) такие, что где z — случайные величины, определяемые в (3.3). В этом случае функция плотности случайного вектора у будет иметь вид где —-С?,.(У) — функция плотности / -ой компоненты вектора у. ду В целях упрощения далее будем полагать, что каждая из компонент вектора у зависит лишь от одномерных функций Ff(x ) из (3.3) а именно
Для определенности и без потери общности функции 7,. (У), i = 1,...,п будем полагать гауссовыми распределениями [47]. Совместное распределе ниє компонент вектора у будем считать многомерным гауссовым распределением с матрицей корреляции и вектором средних ц, то есть
Это в какой-то мере позволяет учесть взаимосвязь компонент вектора у, а значит, и х. Следует заметить, что одномерные распределения компонент вектора могут быть нормальными и в том случае, когда совместное распределение отлично от нормального [46].
Искомая функция плотности исходного вектора х с учетом (3.5), (3.4) и (3.2) запишется следующим образом
При вычислении выражения (3.6) следует иметь в виду, что G7 ( ) — есть обратная функция к гауссову распределению и не выражается в аналитическом виде. Однако, известны достаточно точные аппроксимационные выражения, как для интеграла вероятности, так и для обратной к нему функции. Например, для указанных целей можно использовать X -распределение, введенное Дж. Тьюкки [48, 49]. Простая форма обращения Л.-распределения, с достаточно высокой для практики точностью аппроксимирует обратные функции непрерывных распределений, даже если последние не существуют в аналитическом виде. Обратная функция Я - распределения имеет вид где ZG(0,1), Л,— параметр локальности, Л2 — параметр масштаба, Л — параметр формы. Если аппроксимируемое распределение имеет четыре первых момента, то Л — параметры в (3.7) определяют методом моментов [48, 49]. В частности, для описания обратной функции нормального распределения со средним // и дисперсией т2 имеем следующие значения Л - величин
Используя (3.7) вычислим составляющую dGjX )1 dz1 якобиана преобразования в выражении (3.6), а именно
Обоснование необходимости создания нового программного продукта
Все рассмотренные выше программные продукты это большие пакеты для обработки и анализа данных дистанционного зондирования Земли. Эти программы создавались долгие годы большим коллективом сотрудников. Использование этих пакетов позволяет решать практически любые задачи дистанционного исследования НИЗ и облаков. Однако для конкретной реализации поставленной задачи необходимо доскональное знание возможностей пакетов и способов работы с ними. Кроме того, универсальность этих программ имеет и обратную сторону: она обуславливает сложность реализации многих часто используемых операций. [70]
Нисколько не уменьшая значимость рассмотренных выше программных продуктов, хочется заметить, что в части касающейся контролируемой и неконтролируемой классификации они имеют общие недостатки, которые заключаются в использовании статистического порога принятия решения о принадлежности наблюдений кластеру. Основные недостатки этих методов подробно рассмотрены в гл. 1.
Кроме того, в рассмотренных программах недостаточно, на наш взгляд, уделено внимания работе с полученными результатами. Не всегда есть возможность вывести на экран отдельные кластеры и сохранить их, например, для последующей публикации. Также в рассмотренных выше программах результат работы алгоритмов представляется в псевдоцветах, что очень неудобно и затрудняет визуальную оценку качества выполненного дешифрирования. Говоря об этих пакетах, нельзя не отметить и их высокую стоимость (до нескольких тысяч долларов) [65], а потому недоступность рядовому отечественному исследователю.
Учитывая все выше сказанное, было решено создать свой программный продукт и реализовать в нем новые алгоритмы дешифрирования спутниковых изображений, избавленные от упомянутых недостатков, а также предоставить пользователю дополнительные возможности работы с полученными результатами.
Приведем описание программы Analyser, разработанной нами в Институте Оптики Атмосферы СО РАН и в Томском университете систем управления и радиоэлектроники. Программный продукт работает в подпрограммах кластерного и текстурного анализа (рис. 4.1). Перед запуском одной из подпро грамм необходимо открыть файл со спутниковой информацией прибора AVHRR спутника NOAA.
Подпрограмма кластерного анализа позволяет проводить кластерный анализ новыми алгоритмами: алгоритмом кластеризации признакового пространства гиперсферами и алгоритмом декомпозиции гистограмм, а также широко известным алгоритмом ISODATA (рис. 4.2).
Для того чтобы провести кластерный анализ нужно нажать в главном окне программы кнопку «Кластерный анализ». Главное окно подпрограммы кластерного анализа представлено на рис. 4.3. В заголовке окна пишется имя открытого региона, номер спутника, дата и время съемки данных.
В окне кластерного анализа выбранное изображение показывается в цвете, где в качестве синего слоя используются данные первого канала, в качестве зеленого слоя — данные второго канала и в качестве красного слоя — третий канал.
Также можно посмотреть изображение каждого канала по отдельности. В строке состояния отображается широта и долгота пикселя, на который указывает курсор мыши, а также ширина, высота и масштаб изображения (исходный масштаб обозначается как xl). В программе имеется возможность нанести координатную сетку на изображение, а также вывести на экран границы областей, озера, реки и другую карто графическую информацию. На рис. 4.4 показано окно кластерного анализа с нанесенной фаницей Томской области, реками и названиями населенных пунктов.
В любой момент работы профаммы можно сохранить текущее изображение со всеми нанесенными на него объектами. Также с помощью кнопок быстрого доступа можно изменить масштаб изображения: увеличить в нужное количество раз или уменьшить до истинного размера.
Перед работой алгоритмов можно при необходимости изменить любой парамеф любого алгоритма, а также изменить общие насфойки, такие как: максимальное количество фрагментов, размер фрагментов и т. д. (рис. 4.5).
