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

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

Колодникова Наталья Владимировна

АЛГОРИТМЫ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ТЕМАТИЧЕСКОГО АНАЛИЗА МНОГОСПЕКТРАЛЬНЫХ АЭРОКОСМИЧЕСКИХ СНИМКОВ ЗЕМНЫХ ПОКРОВОВ

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

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

Томск - 2005

Работа выполнена в Томском государственном университете систем управления и радиоэлектроники и в Институте оптики атмосферы СО РАН.

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

профессор Мицель Артур Александрович

Официальные оппоненты: доктор технических наук,

профессор Шелупанов Александр Александрович

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

Ведущая организация: Институт водных и экологических проблем

СО РАН (г. Барнаул)

Защита состоится 22 сентября 2005г. в 15 час. 15 мин. на заседании диссертационного совета Д 212.268.02 при Томском государственном университете систем управления и радиоэлектроники по адресу: 634050, г. Томск, ул. Белинского, 53.

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета систем управления и радиоэлектроники.

Автореферат разослан « 15» августа 2005г.

Ученый секретарь

диссертационного совета ЦуХеМ^ Клименко А.Я.

Л1 9

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

Актуальность. Дистанционные методы изучения растительности, почв, экосистем и геосистем интенсивно разрабатываются с 50-х годов XX века Начиная с середины 60-х годов получают развитие новые виды съемки (тепловые, радиотепловые, спектрометрические, радарные и т п ) Затем с конца 60-х годов большой вклад в развитие дистанционных методов внесла разработка космических методов землеведения с использованием спутниковой информации [1]. Применение спутниковых данных имеет большие преимущества по сравнению с контактными методами исследований Во-первых, в отличие от контактных методов исследования земной поверхности спутниковые приборы оцифровывают за один раз территорию земной поверхности в несколько десятков тысяч квадратных километров, что позволяет в течение одного дня наблюдать и анализировать огромную площадь Земной поверхности, к тому же большая часть этой территории недоступна для контактных методов исследования Во-вторых, высокая периодичность обращения спутников вокруг Земли позволяет вести оперативный мониторинг за состоянием природных экосистем практически в режиме реального времени В-третьих, в отличие от аэрофотосъемки спутники охватывают большое количество природных комплексов на одном изображении, например, Большое Васюганское болото, что позволяет исследователю выявлять новые закономерности изменения природных сред. Благодаря этим и многим другим преимуществам спутниковая информация завоевала большую популярность в научном мире.

Для обработки спутниковых изображений используются специализированные программные продукты, например, ERDAS, ENVI, Idrisi, ER Mapper В этих пакетах используются алгоритмы контролируемой и неконтролируемой классификации, которые не учитывают тот факт, что в разных кластерах разброс данных различен. Например, в классах «почва» и «растительность» наблюдения тесно группируются около своего центра, а в классе «облака» наблюдения отстают друг от друга на значительном расстоянии Кроме того, рассмотренные программные продукты не позволяют проводить детальную работу с классами. В связи с этим, развитие алгоритмов и программного обеспечения для дешифрирования спутниковых изображений является актуальной задачей.

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

ков, а также разработка

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

1 Провести критический анализ современного состояния методов дешифрирования космических снимков.

2 Создать алгоритмы кластерного и текстурного анализа спутниковых изображений земной поверхности.

3 Разработать программное обеспечение для контролируемой и неконтролируемой классификации космических изображений

4 Решить практические задачи космического мониторинга земной поверхности и облаков

Методы исследований Для решения задач, сформулированных в диссертационной работе, использовались методы теории вероятности и математической статистики, современные методы дистанционного зондирования различных объектов и явлений окружающей среды, методы текстурного и кластерного анализа, полиномиальные сплайны и результаты научных исследований отечественных и зарубежных ученых (Н Г Загоруйко, С А. Айвазян, А.А Потапов, Robert M Haralick, J T Tou, R. С. Gonzalez и др ).

Научную новизну, полученных в работе результатов, определяют'

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

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

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

4 Расширенная система информативных текстурных признаков, являющаяся обобщением известных в литературе признаков, используемая алгоритмами текстурного анализа

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

Степень достоверности результатов работы Достоверность полученных результатов определяется строгостью используемых матема-

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

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

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

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

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

Внедрение работы Разработанный программный продукт внедрен в ООО «Агрохимсервис» (г Новосибирск), в институте «Кибернетический центр» ТПУ (г. Томск), в НИИ экологического мониторинга (г. Барнаул), в институте водных и экологических проблем СО РАН (г Барнаул). Результаты работы программы использовались департаментом водной службы главного управления природных ресурсов по Томской области, Томской базой авиационной охраны лесов, институтом космических исследований (республика Казахстан), лесной службой главного управления природных ресурсов и охраны окружающей среды России по Томской области.

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

Основные результаты работы докладывались и обсуждались на следующих конференциях и симпозиумах' региональная научно-техническая конференция «Радиотехнические устройства, информационные технологии и системы управления» (Томск, 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 (Томск, 2002), X Joint International Symposium «Atmospheric and ocean optics Atmospheric physics» (Томск 2003), всероссийская научно-техническая конференция (Томск 2004), II Всероссийская научно-практическая конференция студентов (Томск, 2004), Вторая Всероссийская конференция по дистанционному зондированию земных покровов и атмосферы аэрокосмическими средствами (Санкт-Петербург 2004); XI Joint International Symposium «Atmospheric and ocean optics Atmospheric physics» (Томск

2004), Международная конференция по измерениям, моделированию и информационным системам для изучения окружающей среды ENVI-ROMIS (Томск, 2004), IV международный симпозиум «Контроль и реабилшация окружающей среды», (Томск 2004), XII международный симпозиум «Atmospheric and ocean optics Atmospheric physics» (Томск

2005)

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

1 Постановка задачи, цели исследования и методы исследования были определены руководителем Мицелем Артуром Александровичем совместно с Протасовым Константином Тихоновичем.

2 Алгоритм кластеризации признакового пространства гиперсферами и формирование системы текстурных признаков на основе литературных источников выполнено лично автором

3 Алгоритмизация алгоритмов текстурного и кластерного анализа выполнена совместно с Протасовым К Т.

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

5 Применение программы Analyser для решения ресурсно-экологических задач выполнено совместно с Загорулько В.А. и Протасовой В П.

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

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

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

Для более эффективного и быстрого кластерного анализа больших изображений мы предлагаем следующий подход, состоящий из трех этапов выделение наиболее характерных для рассматриваемого изображения фрагментов и формирования на их основе мелких кластеров; попарное укрупнение мелких кластеров до выполнения некоторого критерия (в простейшем случае заданного пользователем количества кластеров); распознавание всего изображения, используя сформированные на втором этапе кластеры. Для каждого этапа распознавания приведены свои меры расстояния. В главе 1 также рассмотрены наиболее популярные методы и алгоритмы кластерного анализа, такие как метод /^-средних, метод ближайшего соседа, метод самого дальнего соседа, алгоритм «FOREL», алгоритм ISODATA и. др. Проанализированы преимущества и недостатки изложенных методов.

Во второй главе предложены новые алгоритмы кластерного анализа: алгоритм кластеризации признакового пространства гиперсферами и алгоритм декомпозиции гистограмм.

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

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

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

Алгоритм декомпозиции гистограмм основан на построении для каждого наблюдения гистограммы евклидовых расстояний (1) до других наблюдений Также на основе имеющихся данных строится эталонная гистограмма с помощью распределения Релея

где и - параметр распределения Релея, который считается по формуле и = —, где с1„ — минимальное расстояние Евклида между 1.2533

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

(1)

I

г

--- , если / > О,

2-й2)

О, если КО,

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

Сравнительный анализ алгоритмов кластеризации был проведен [три обработке 20 спутниковых изображений Томской области размером 982x891 пикселей Для анализа использовались снимки прибора АУНЯЯ спутника МОАА В алгоритме построения гиперсфер в качестве значения константы, задаваемой пользова1елем, было задано число 12. В алгоритме декомпозиции 1истограмм окончательное количество кластеров для дешифрирования было установлено равным 100 В обоих алгоритмах для одного и того же снимка использовались одинаковые фрагменты для обучения размером 50x50 пикселей. Таким образом, алгоритмы были поставлены в равные условия при самообучении. Для сравнения был взят один из лучших алгоритмов дешифрирования спутниковых изображений 15СЮАТА.

На рис. 1 показано среднее время работы каждого алгоритма (в секундах), необходимое на дешифрирование спутникового изображения Из рисунка видно, что самым быстрым алгоритмом был алгоритм построения гиперсфер.

□ алгоритм построения шг^кфер

В алгоритм декомполодш гистограмм

□ алгорггтм 180Г)АТА

Рис. 1 Среднее время (сек), Рис 2 Среднее значение ошибки затраченное разными алгорит- кластеризации алгоритмами кла-мами на кластеризацию стерного анализа

Медленней всех оказался алгоритм декомпозиции гистограмм Его средний результат - 8 минут 7 секунд Это объясняется необходимостью рассчитывать расстояние между всеми точками на этапе самообучения Анализ показал, что для увеличения скорости работы этого

алгоритма необходимо уменьшить размер фрагментов, выбираемых для самообучения. Использование 11 фрагментов размером 32x32 пикселя для самообучения позволило увеличить скорость работы алгоритма примерно в 7 раз (35 секунд), и ошибка кластеризации при этом была 7 6%.

На рис. 2 представлены средние показатели ошибки кластеризации для каждого алгоритма, которые рассчитывались по формуле'

1 N

М=-Уе, NTt

где М - средняя ошибка кластеризации алгоритма, е - ошибка, рассчитанная на одном изображении, N - количество изображений, которые использовались для расчета средней ошибки (в нашем случае N = 20)

В третьей главе рассматриваются алгоритмы текстурного анализа. Текстура, в широком смысле этого слова, это некоторый участок изображения, но не любой, а только тот который имеет однородные статистические характеристики, и, следовательно, текстуру можно описать некоторыми признаками. Под признаками текстур обычно понимают характерные свойства, общие для всех текстур данного класса [2] Из различных литературных источников нами сформирована система из 16 текстурных признаков. В работе рассмотрена проблема выбора информативных признаков и предложен оригинальный комбинированный алгоритм выбора оптимального подмножества признаков Перед выполнением этого алгоритма пользователю необходимо задать так называемый «вектор плана экспериментов» J Выполнение алгоритма возможно двумя путями'

• С выбором наиболее информативных признаков

В данном варианте сначала алгоритм перебирает все возможные подмножества из ./' текстурных признаков 'I о подмножес! во, которое дало минимальное значение выбранного критерия ошибки (в нашем случае это средний риск), счигается наиболее информативным и фиксируется для дальнейшего рассмотрения Затем алгоритм перебирает подмножества из J2 текстурных признаков и тд пока не будет рассмотрен весь вектор плана экспериментов В частном случае, полагая вектор экспериментов равным J = (1,1,...,1), мы получим алгоритм «Add» [3].

• С удалением наименее информативных признаков

Этот вариант аналогичен предыдущему Отличие заключается в том, что в данном случае мы удаляем из системы признаков те признаки, которые дают наибольшее значение риска, то есть являются наи-

менее информативными Таким образом, задавая вектор плана экспериментов, мы говорим, сколько признаков надо исключить из начального множества. В частном случае, полагая вектор экспериментов равным J = (1,],...,!), мы получим алгоритм «Del» [3]

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

Перед началом работы любого из предложенных оригинальных алгоритмов эксперт или учитель задает необходимое количество обучающих выборок х,,. ,,\N е v , то есть Nv - объем выборки класса v, для каждого из С классов и указывает значения компонентов вектора плана экспериментов При этом количество классов, количество фрагментов в каждом классе, количество и значения компонентов вектора экспериментов определяется учителем.

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

и - принимаемое решение (в простейшем случае - номер класса); />(м0 - априорная вероятность появления класса м>; /^{м) - условные функции плотности Для этого рассматриваемое наблюдение подставляется в функцию плотности следующего вида'

где Е- матрица корреляции наблюдений (спектральных яркостей) в классе м , р. ~ вектор средних яркостей в классе м>, п - размерность

и = arg max P(w)/(х I w),

»-1 с

(2)

признакового пространства, Г(х) непрерывные условные функции распределения, СГ'() - есть обратная функция к гауссову распределению класса м Она не выражается в аналитическом виде, поэтому аппроксимируется Л-распределением, введенным Дж Тьюкки. [4]

¿сг'ОО

дг'

: (г "8М| + (1 - г) "8651 )• / - якобиан преобразования обратной

гауссовой функции, а /(х') - функция плотности [5,6]

При этом если значение точки не попадает в «узел» оценки функции распределения текстурного признака, то значение функции распределения в этой точке аппроксимируется кубическим сплайном [7-9]. Наблюдение относится к тому классу, на котором решающее правило (2) приняло минимальное значение. Таким образом, рассматривается каждое наблюдение исходных данных

Еще один алгоритм, предлагаемый нами, - это непараметрический алгоритм, использующий модифицированное ядро Епанечникова На первом шаге алгоритм рассчитывает значения текстурных признаков на образцах классов. Затем из всего множества текстурных и спектральных признаков, заданных в программе, оригинальным комбинированным методом усеченного перебора (приведенным выше) находится подсистема оптимальных признаков Затем каждое наблюдение относится к некоторому классу в соответствии с байесовым решающим правилом (2) Если неизвестны условные функции плотности, естественно использовать их непараметрические оценки /(х(м') по обучающим последовательностям хп . ,Хд, е . В качестве непараметрической оценки неизвестной функции плотности будем использовать следующую оценку с ядром Епанечникова с "в1гутренней" системой координат, обеспечивающей разворот эллипса рассеяния, согласованный с рассеянием выборочных данных [10,11]

К л

1

ек

а-Ь-

2

V V

ял

где введена следующая вспомогательная система координат

оЛ

и = 0х,м[иит~\ = см

о о

х х

в' = = Л ,Л =

в - матрица декоррелирующего ортогонального преобразования, Л/[.] - оператор математического ожидания, V - матрица ортогональных

о

преобразований, х - центрированные наблюдения, Л - диагональная матрица собственных значений, - оценка ковариационной матрицы класса V , а = 3/475, Ь = а/5 , Я, — / -тое собственное значение, /г^ -параметр сглаживания класса V. Особенность модифицированного ядра Епанечникова, предлагаемого нами, заключается в том, что используется единый параметр сглаживания для всех размерностей пространства наблюдений Поиск параметра /г осуществляется следующим образом' на первом этапе в области поиска случайно с равномерным распределением бросается точка, затем из этой точки осуществляется градиентный спуск, при этом используется процедура поиска Цыпкина [12].

Для иллюстрации работы алгоритма были использованы снимки территории Томской области, зафиксированные радиометром АУНЯК

|#Г w

И

Ч

:* *

¡у_

4 Результат работы алгорит-темно-серые области - грозо-поля)

Целью работы алгоритма было определение грозовых полей над территорией Томской области. Результаты работы приведены на рис. 4. Ошибка распознавания исходного снимка составляет 4,2%.

В четвертой главе рассмотрены наиболее популярные программные продукты (ENVI, ERDAS, Idrisi, ER Mapper) для обработки и анализа спутниковой информации, которые содержат алгоритмы контролируемой и неконтролируемой классификации В рассмотренных программах недостаточно, на наш взгляд, уделено внимания работе с полученными результатами. Не всегда есть возможность вывести на экран отдельные кластеры и сохранить их, например, для после-

спутника NOAA-12 (рис. 3).

Рис 3 Исходный снимок террито- Рис. рии Томской области 27 июня ма ( 2000 г. вые

дующей публикации Также в рассмотренных выше программах результат работы алгоритмов представляется в псевдоцветах, что очень неудобно и затрудняет визуальную оценку качества выполненного дешифрирования. Но самый главный недостаток этих пакетов заключается в применении методов классификации с использованием статического порога принятия наблюдения в кластер[13-17] Этот порог задается оператором в зависимости от его опыта и не учитывает особенности данных, их расположение в пространстве [18-21].

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

В программе используется интуитивно-понятный интерфейс работы с результатами. Имеется возможность вывести отдельный кластер или группу кластеров на экран и посмотреть все кластеры, последовательно выводя их на экран монитора. Возможен также вывод на экран различной картографической информации: границы областей, озера, реки, населенные пункты и т.д. а, кроме того, выводить координатную сетку. Программный продукт Analyser стандартизован по ГОСТ 28195-89. На рис. 5 приведены некоторые «окна» программы Analyser.

Пятая глава отражает примеры использования программного продукта Analyser для решения различных задач ресурсно-

j « en

тя

Рис. 5 Примеры «окон» программы Analyser

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

Рис. 6 Результат текстурного анализа снимка МСЮ18 (выделены 4 типа болотных экосистем)

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

Приведен пример отделения облаков от подстилающей поверхности Земли (рис. 7, 8) с оценкой площади подстилающей поверхности, занимаемой облаками с выделением классов «облака», «разорванная облачность», «снег» и др.

Рис. 7 Исходное изображение Томской области от 15 мая 2000г., полученное со спутника МОАА

Рис 8 Текстурный анализ снимка от 15 мая 2000г. Выделены классы «плотная облачность», «легкая дымка», «снег» и «земля».

Рис. 9 Исходный снимок спутника NOAA за 4 мая 2004г.

Рис. 10 Кластерный анализ снимка NOAA за 4 мая 2004г.

Показана возможность применения программы Analyser в метеорологии. Рассмотрен пример использования программы для решения проблемы обнаружения грозовых полей на сплошной облачности.

Приведен результат мониторинга схода снежного покрова на территории Томской области, который был проведен весной 2004г. (рис. 9, 10) и мониторинг паводковой обстановки на основных и малых реках Томской области (весна 2004г.) (рис. 11, 12). На рис 10 видно, что граница таяния снега проходит севернее Большого Васюганского болота.

Выделенная белым квадратом часть изображения рис 11 представлена на рис 12. Ширина разлившейся Оби в точке А составляет 10-12 км, в точке Б - 4-5 км, а ширина Томи (точка В) составляет 6-8 км.

Рис. 11 Исходный снимок спут- снимка спутника МОАА от 23 ника ИОАА от 23 апреля 2004 г. апРеля 2004 г- с кластерным анализом. Виден разлив реки от г. Томска до г Красного Яра.

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

1. Изложены теоретические основы кластерного анализа'

• приведена структура классического решения задачи кластерного анализа с помощью ЕМ-алгоритма, так как именно на его основе построены все популярные методы кластерного анализа;

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

2. Предложены новые алгоритмы кластерно1 о анализа, алгоритм кластеризации признакового пространства гиперсферами и алгоритм декомпозиции I истограмм, в которых используется динамический порог, рассчитываемый каждый раз при создании кластера Приведен сравнительный анализ эффективности новых алгоритмов кластерного анализа. Самым быстрым алгоритмом стал алгоритм построения гиперсфер. Его среднее время 29 секунд Алгоритм ГБООАТА потратил на дешифрирование того же изображения 1 минуту 45 секунд В среднем качество дешифрирования алгоритма построения гиперсфер сопоставимо (ошибка составила 5%), но все-таки, немного лучше алгоритма 15СЮАТА (ошибка равна 5 5%). Алгоритм декомпозиции гистограмм показал несколько худшие, но вполне приемлемые результаты для дешифрирования спутниковых изображений.

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

4. Приведено описание нового непараметрического алгоритма текстурного анализа, основанного на использовании модифицированного ядра Епанечникова. На примерах проиллюстрирована работа алгоритма. Анализ снимков показал, что разделение классов в пространстве признаков происходит достаточно надежно

5. Приведено описание нового параметрического алгоритма текстурного анализа, основанного на аппроксимации эмпирической функции распределения сплайнами.

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

достатки существующих пакетов в части контролируемой и неконтролируемой классификации.

7. Дано обоснование необходимости создания нового программного продукта, в котором применяются алгоритмы с динамическими порогами.

8 Приведено описание созданного программного продукта Analyser. Подробно описаны оригинальные подпрограммы кластерного и текстурного анализа, а также предложены удобные режимы работы с результатами.

9. Продемонстрированы широкие возможности новой программы для решения задач ресурсно-экологического мониторинга

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

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

• Получены результаты мониторинга схода снежною покрова и паводковой обстановки на территории Томской области весной 2004г. Проведенный мониторинг позволил своевременно выдать предупреждение о разливе рек штабу ГО и ЧС.

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

11 Разработанный программный продукт Analyser внедрен в ООО «Агрохимсервис» (г. Новосибирск), в институте «Кибернетический центр» ТПУ (г. Томск), в НИИ экологического мониторинга (г. Барнаул), в институте водных и экологических проблем СО РАН (г Барнаул), о чем получены соответствующие акты

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

1. Ткаличева Н.В Кластерный анализ данных, полученных со спутников серии NOAA //Тезисы докладов региональной научно-технической конференции «Радиотехнические устройства, информационные технологии и системы управления», 15-18мая 2001, Ч. 2-Томск, 2001.-С. 10-12.

2. Tkalicheva N V., Protasov К.Т. Nonparametric classification algorithm of cluster analysis of the Large Basyugan bog from the data of the AVHRR/NOAA device //VII Join International Symposium «Atmospheric and ocean optics Atmospheric physics», June 25-29, Irkutsk, 2001 - С 207

3. Ткаличева H В Алгоритм кластерного анализа спутниковых изображений подстилающей поверхности Земли для ГИС //По материалам международной конференции «Моделирование, базы данных и информационные системы для атмосферных наук», 25 - 29 июня 2001, Иркутск.

4 Колодникова Н В Разработка алгоритмов кластеризации для анализа данных прибора AVHRR спутника NOAA //Доклады Томского государственного университета систем управления и радиоэлектроники^ 7'Сб научных трудов. - Томск 2002. - С 106-112.

5 Колодникова Н В , Протасов К.Т Алгоритм выделения кластеров путем оценивания локальных мод смешивающего распределения //IX Международный симпозиум «Оптика атмосферы и океана Физика атмосферы» 2-5 июля 2002, Томск

6 Колодникова Н В , Протасов К.Т. Алгоритмы кластерного анализа спутниковых изображений подстилающей поверхности земли для ДЗ //Международная конференция «ENVIROMIS-2002» «Измерения, моделирование и информационные системы как средства реабилитации окружающей среды на городском и региональном уровне» 6 -12 июля 2002, Томск

7 Колодникова Н В , Протасов К Т Алгоритм выделения кластеров путем оценивания локальных мод смешивающего распределения //Материалы докладов III Международного симпозиума «Контроль и реабилитация окружающей среды», 10-12 июля, Томск, 2002 - С 52-53

8 Колодникова Н В Выделение кластеров с помощью метода построения гиперсфер //Труды постоянно действующей научно-технической школы-семинара студентов, аспирантов и молодых специалистов «Информационные системы мониторинга окружающей среды», Вып. 1, Томск, 2002. - С. 41^18.

9 Kolodnikova N V , Protasov K.T. Algorithm for clustering by means of assessment of local modes of a mixed distribution //Proc. of SPIE. Atmospheric and Ocean Optics, 2002 - Vol 5026. - P.253-259.

10. Kolodnikova NV, Protasov К Т. Context approach to development of algorithm for cluster analysis of aerospace images //X Joint International Symposium «Atmospheric and ocean optics Atmospheric physics», June 24-28, 2003, Tomsk -P 91

11. Ивитская О В , Колодникова Н В Анализ матрицы смежности, используемой для расчета текстурных признаков для задач распознавания изображений //Материалы всероссийской научно-технической конференции, 18-20 мая 2004, Томск, Ч 1 - Томск, 2004 - С. 179180.

12 Колодникова Н В Обзор текстурных признаков для задач распознавания образов //Сб трудов сотрудников ТУСУРа, Томск, 2004.

13. Мицель А А , Колодникова II В., Протасов К Т Непараметрический алгоритм текстурного анализа аэрокосмических снимков //Известия ТПУ, №1, 2005. - С.65-70.

14. Колодникова Н.В., Протасов К.Т. Функционалы текстур при формировании контекстных признаков для алгоритмов распознавания образов //Сб. трудов Н-ой Всероссийской научно-практической конференции студентов, г. Томск, 25-26 февраля 2004 - С 75-76

15. Колодникова II.В., Протасов КТ Синтез параметрических распределений для решающих правил распознавания земных покровов и облаков //Материалы Второй Всероссийской конференции по дистанционному зондированию земных покровов и атмосферы аэрокосмическими средствами, Санкт-Петербург, 16-18 июня 2004. - С.57-61

16. Колодникова Н В., Протасов К Т. Распознавание земных покровов и облаков непараметрическим решающим правилом в пространстве информативных текстур //Материалы Второй Всероссийской конференции по дистанционному зондированию земных покровов и атмосферы аэрокосмическими средствами, Санкт-Петербург, 1618 июня, 2004.-С 62-66.

17. Kolodnikova N.V , Protasov К.Т The recognition of clouds fields types by nonparametric algorithm in textural feature space on cosmic data //XI Joint International Symposium «Atmospheric and ocean optics. Atmospheric physics», Tomsk, June 23-26, 2004 -P. 105-106

18. Колодникова HB , Загорулько В.A , Протасов КТ Распознавание текстурно-однородных полей видеоданных Васюганского болота по данным космосьемки //Международная конференция по измерениям, моделированию и информационным системам для изучения окружающей среды ENVIROMIS-2004, Томск, 16-22 июля 2004. -С.43.

19 Колодникова Н В , Загорулько В А , Протасов К Т. Распознавание текстурно-однородных полей видеоданных Васюганского болота по данным космосьемки //География и природные ресурсы, спец выпуск, 2004. - С.64-70.

20 Колодникова Н В., Протасова В П , Загорулько В А Пространственно-структурная организация геосистемы Большого Васюганского болота по результатам космомониторинга //IV международный симпозиум «Контроль и реабилитация окружающей среды», Томск, 21-23 июля 2004 -С.70-71

21 Kolodnikova N V , Protasov К Т The recognition of clouds fields types by nonparametric algorithm in textural feature space on cosmic data //Proc ofSPIE, 2005

22 Kolodnikova N V , Protasov К T Cluster analysis algorithm based on the modified EM-approach of decomposition of the mixing distribution» //XII международный симпозиум «Atmospheric and ocean optics Atmospheric physics», Томск, 27-30 июня, 2005 - С 82-83

Список цитируемой литературы

1. Виноградов Б.В. Аэрокосмический мониторинг экосистем, М:

Наука, 1984 - 320с 2 Андреев Г. А., Базарский О. В , Глауберман А. С и др Анализ и синтез случайных пространственных текстур, Зарубежная радиоэлектроника, №2, 1984.-С 3-33 3. http //math.nsc ru/AP/oteks/Russian/links/SPA/index.html

4 Ramberg J S , Dudewicz E J , Tadikamalla P R , Mykytka E F A probability distribution and its uses in fitting data Technometrics, Vol 21, №2, 1979.-P. 201-214

5 Пугачев В С Теория вероятностей и математическая статистика, М • Наука, 1979 -496с

6 Форсайт Дж , Малькольм М , Моулер К Машинные методы математических вычислений, М ■ Мир, 1980 —290с

7. Завьялов Ю.С, Квасов Б И., Мирошниченко В. JI. Методы сплайн-функций, М : Наука, 1980. - 352с

8 Мицель А А Вычислительная математика' Лабораторный практикум - Томск- Томский государственный университет систем управления и радиоэлектроники, 1999. - 106с

9 Мицель А А Катаев М Ю Приближение сплайнами- Учебное пособие Томск- Томский государственный университет систем управления и радиоэлектроники, 2001. — 40с.

10 Епанечников В А Непараметрическая оценка многомерной плотности верояшости //Теория вероятностей и ее применение 1969. -Т ¡4 -Вып. 1.-С. 156-161.

11. Тарасснко Ф.П Непараметрическая статистика. - Томск- ТГУ, 1976. -294с

12. Цыпкин Я 3 Адаптация и обучение в автоматических системах, М. Наука, 1968.-400с.

13. ERDAS IMAGINE 8.5 Tour Guides, ERDAS Inc., 2001

14. http //www amlab ru/paper_max shtml

15 http.//www geo.pu.ru/ecobez/edu/books/eis/index.htm

16 http//www.clarklabs.org

17 awww.royint com/ermapper/

18. Денисов Д.А , Низовкин В.А Сегментация изображений на ЭВМ //Зарубежная радиоэлектроника, №10, 1985 - С 5-30

19 Той, J Т. and Gonzalez R С, 1974. Pattern Recognition Principles, Addison-Wesley Publishing Company, Reading, Massachusetts

20. ENVI 3.4 User's Guide, BSC Inc, 2001.

21 Richards JA Remote Sensing Digital Image Analysis, SpringerVerlag, Berlin, 1994.-P. 340.

»146 8 1

РНБ Русский фонд

2006-4 10239

Тираж 100. Заказ 758. Томский государственный университет систем управления и радиоэлектроники. 634050, г. Томск, пр. Ленина, 40.

ВВЕДЕНИЕ.

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

КЛАССИФИКАЦИЯ).

1.1 Теоретические основы кластерного анализа.

1.1.1 Описание предметной области.

1.1.2 Классическое решение поставленной задачи.

1.2 Общая структура алгоритмов кластерного анализа.

1.2Л Объединение объектов.

1.2.2 Объединение кластеров.

1.2.3 Классификация образов.

1.3 Определение качества кластеризации.

1.4 Обзор существующих методов кластерного анализа.

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

Дистанционные методы изучения растительности, почв, экосистем и геосистем интенсивно разрабатываются с 50-х годов XX века. Начиная с середины 60-х годов получили развитие новые виды съемки (тепловые, радиотепловые, спектрометрические, радарные и т. п.). Затем с конца 60-х годов большой вклад в развитие дистанционных методов внесла разработка космических методов землеведения [1]. Применение спутниковых данных имеет большие преимущества по сравнению с контактными методами исследований. Во-первых, в отличие от контактных методов исследования земной поверхности спутниковые приборы оцифровывают за один раз территорию земной поверхности в несколько десятков тысяч квадратных километров, что позволяет в течение одного дня наблюдать и анализировать огромную площадь Земной поверхности, к тому же большая часть этой территории недоступна для контактных методов исследования. Во-вторых, высокая периодичность обращения спутников вокруг Земли позволяет вести оперативный мониторинг за состоянием природных экосистем практически в режиме реального времени. В-третьих, в отличие от аэрофотосъемки спутники охватывают большое количество природных комплексов на одном изображении, например, Большое Васюганское болото, что позволяет исследователю выявлять новые закономерности изменения природных сред. Благодаря этим и многим другим преимуществам дистанционные методы исследования подстилающей поверхности Земли (11113) и облаков завоевали большую популярность в научном мире.

Дистанционные методы, как правило, являются косвенными, то есть с их помощью измеряют не интересующие нас параметры объектов, а некоторые связанные с этими объектами величины. В качестве таких величин при съемке с самолета или искусственного спутника Земли (ИСЗ) регистрируют отраженное от объекта излучение в различных спектральных диапазонах — оптических, инфракрасных и микроволновых. [2]

Использование отраженного излучения при применении методов дистанционного зондирования стало возможным благодаря различной отражательной способности разных типов 11113 и облаков. Поэтому использование отражательной способности для различных типов поверхности и различных участков спектра — это ключ к распознаванию деталей на спутниковых изображениях Земли. Так, например, отражательная способность зеленой растительности мала в видимой части спектра и велика в ближней инфракрасной (ИК) области. В то время как отражательная способность свежевыпавшего снега велика (98%) в оптическом диапазоне и гораздо меньше в ИК-области. Это позволяет компьютеру уверенно отделить снег и растительность друг от друга. Мало того, более низкая отражательная способность старого и влажного снега (примерно 45%) позволяет отделить его от свежевыпавшего. А использование диапазона 1.55 — 1.65 мкм позволяет уверенно отделить снег от облаков.[3] Здесь приведены наиболее очевидные случаи отделения одних типов поверхности от других, но часто бывают ситуации, когда не все так однозначно. В этих случая целесообразно использовать соотношение нескольких спектральных диапазонов для более точного разделения типов 11113. Поэтому сейчас запускаются спутники с многоспектральной аппаратурой. К таким спутникам относятся NOAA, EOS, Terra, Aqua, LANDSAT, SPOT, Pecypc-Ol и др.

При работе над диссертацией были использованы снимки двух спутников NOAA и Terra. Остановимся на них поподробнее.

ИСЗ серии NOAA предназначены в основном для наблюдений атмосферы, но информация с них может успешно использоваться для изучения суши и океана. В настоящее время на орбите функционируют несколько спутников этой серии. В нашей работе были использованы данные прибора AVHRR. Этот прибор является одним из трех основных приборов на борту спутников серии NOAA. Он предназначен для спектрального исследования метеорологических, океанографических и гидрологических параметров через измерения излученной или отраженной радиации в пяти спектральных полол сах. Разрешающая способность прибора 1.1x1.1 км в надире. Угол сканирования прибора ±55°, полоса обзора около 3000 км, поэтому за один проход спутника удается получить информацию с поверхности около 3000x7000 км. Прибор имеет 5 спектральных каналов: 1-ый канал — 0,58-0,68 мкм (красный участок спектра), 2-ой канал — 0,72-1,1 мкм (ближний ИК), 3-ий канал - 3,553,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

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

Цели работы и задачи исследования

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

1. Провести критический анализ современного состояния методов дешифрирования космических снимков.

2. Создать алгоритмы кластерного и текстурного анализа спутниковых изображений земной поверхности.

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

4. Решить практические задачи космического мониторинга земной поверхности и облаков.

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

Для решения задач, сформулированных в диссертационной работе, использовались методы теории вероятности и математической статистики, современные методы дистанционного зондирования различных объектов и явлений окружающей среды, методы текстурного и кластерного анализа, полиномиальные сплайны и результаты научных исследований отечественных и зарубежных ученых (Н.Г. Загоруйко, С.А. Айвазян, АА. Потапов, Robert М. Haralick, J.T. Той, R. С. Gonzalez и др.).

Научную новизну, полученных в работе результатов, определяют:

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

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

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

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

5. Алгоритм поиска подмножества наиболее информативных текстурных признаков, являющийся обобщением существующих алгоритмов «Add» и «Del» усеченного перебора признаков, основанный на минимизации среднего риска.

Степень достоверности результатов работы

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

Практическая ценность и реализация результатов работы

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

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

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

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

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

Внедрение работы

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

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

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

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

Основные результаты работы докладывались и обсуждались на следующих конференциях и симпозиумах: региональная научно-техническая конференция «Радиотехнические устройства, информационные технологии и системы управления» (Томск, 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); всероссийская научно-техническая конференция (Томск 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 статей, в том числе одна в рецензируемом журнале.

Личный вклад

1. Постановка задачи, цели исследования и методы исследования были определены руководителем Мицелем Артуром Александровичем совместно с Протасовым Константином Тихоновичем.

2. Алгоритм кластеризации признакового пространства гиперсферами и формирование системы текстурных признаков на основе литературных источников выполнено лично автором.

3. Алгоритмизация алгоритмов текстурного и кластерного анализа выполнена совместно с Протасовым К.Т.

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

5. Применение программы Analyser для решения ресурсно-экологических задач выполнено совместно с Загорулько В.А. и Протасовой В.П.

Содержание работы

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

5.5 Основные результаты и выводы по главе

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

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

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

4. В работе представлены результаты мониторинга схода снежного покрова и паводковой обстановки весной 2004г. Проведенный мониторинг позволил своевременно выдать предупреждение о разливе рек штабу ГО и ЧС.

ЗАКЛЮЧЕНИЕ

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

1. Изложены теоретические основы кластерного анализа:

• приведена структура классического решения задачи кластерного анализа с помощью ЕМ-алгоритма, так как именно на его основе построены все популярные методы кластерного анализа;

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

2. Предложены новые алгоритмы кластерного анализа: алгоритм кластеризации признакового пространства гиперсферами и алгоритм декомпозиции гистограмм, в которых используется динамический порог, рассчитываемый каждый раз при создании кластера. Приведен сравнительный анализ эффективности новых алгоритмов кластерного анализа. Самым быстрым алгоритмом стал алгоритм построения гиперсфер. Его среднее время 29 секунд. Алгоритм ISODATA потратил на дешифрирование того же изображения 1 минуту 45 секунд. В среднем качество дешифрирования алгоритма построения гиперсфер сопоставимо (ошибка составила 4,9%), но все-таки, немного лучше алгоритма ISODATA (ошибка равна 5.5%). Алгоритм декомпозиции гистограмм показал несколько худшие, но вполне приемлемые результаты для дешифрирования спутниковых изображений.

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

4. Приведено описание нового непараметрического алгоритма текстурного анализа, основанного на использовании модифицированного ядра Епанечни-кова. На примерах проиллюстрирована работа алгоритма. Анализ снимков показал, что разделение классов в пространстве признаков происходит достаточно надежно.

5. Приведено описание нового параметрического алгоритма текстурного анализа, основанного на аппроксимации эмпирической функции распределения сплайнами.

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

7. Дано обоснование необходимости создания нового программного продукта, в котором применяются алгоритмы с динамическими порогами.

8. Приведено описание созданного программного продукта Analyser. Подробно описаны оригинальные подпрограммы кластерного и текстурного анализа, а также предложены удобные режимы работы с результатами.

9. Продемонстрированы широкие возможности новой программы для решения задач ресурсно-экологического мониторинга.

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

Структурирование позволило выделить 11 различных типов природных комплексов Большого Васюганского болота.

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

• Получены результаты мониторинга схода снежного покрова и паводковой обстановки на территории Томской области весной 2004г. Проведенный мониторинг позволил своевременно выдать предупреждение о разливе рек штабу ГО и ЧС.

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

11. Разработанный программный продукт Analyser внедрен в ООО «Агро-химсервис» (г. Новосибирск), в институте «Кибернетический центр» ТПУ (г. Томск), в НИИ экологического мониторинга (г. Барнаул), в институте водных и экологических проблем СО РАН (г. Барнаул), о чем получены соответствующие акты.

1. Виноградов Б.В. Аэрокосмический мониторинг экосистем, М.: Наука, 1984.-320с.

2. Мкртчян Ф. А., Шутко А. М. Физические принципы дистанционного мониторинга земной поверхности //Проблемы окружающей среды и природных ресурсов, №4, 2002.- С. 17-21

3. Кашкин В.Б., Сухинин А.И., Дистанционное зондирование из космоса, цифровая обработка изображений, Учебное пособие. М.: Логос, 2001. — 264 с.

4. Егоров В.В., Федотова З.К. Задачи, программы и космические системы исследования Земли //Итоги науки и техники. Исследование Земли из космоса, ВИНИТИ, Том 1. С. 180-194.

5. Прикладная статистика: Классификация и снижение размерности Справочное издание //Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д.; под ред. Айвазяна С.А.-М.: Финансы и статистика, 1989 — 607с.

6. Ту Дж., Гонсалес Р. Принципы распознавания образов — М., Мир, 1978. — 414с.7. http://astra.geosys.ru/pageslab/articles/aanna2.htm

7. GOVAERT G. Spatial Fuzzy Clustering using EM and Markov Random Fields Systems //Research and Information Systems, Vol. 8, 1998 P. 183-202.

8. Айвазян C.A., Бежаева З.И., Староверов O.B. Классификация многомерных наблюдений. М:. «СТАТИСТИКА», 1974.-240 с.

9. Рао С.Р. Линейные статистические методы и их применение. Пер. с англ. — М.: Наука. 1968. 548 с.

10. Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1976.

11. Прэтт У. Цифровая обработка изображений: Пер. с англ. — М.: Мир, 1982. -Кн. 1 -312 е.; Кн. 2-480 с.

12. Фукунага К. Введение в статистическую теорию распознавания образов. Пер. с англ. — М.: Наука. Главная редакция физ.-мат. лит. 1979. — 368с.

13. Патрик Эдвард А. Основы теории распознавания образов: Пер. с англ. /Под ред. Б.Р. Левина. М.: Сов. Радио, 1980. - 408с.

14. Загоруйко Н.Г., Ёлкина В.Н., Емельянов С.В., Лбов Г.С. Пакет прикладных программ ОТЭКС. — М.: Финансы и статистика, 1986.

15. Денисов Д.А., Низовкин В.А. Сегментация изображений на ЭВМ //Зарубежная радиоэлектроника, №10. — 1985. С.5-30.

16. Колодникова Н. В. Разработка алгоритмов кластеризации для анализа данных прибора AVHRR спутника NOAA //Доклады томского государственного университета систем управления и радиоэлектроники, Т. 7, Сб. научных трудов, Томск, 2002. С. 106-112

17. Kolodnikova N.V., Protasov К.Т. Context approach to development of algorithm for cluster analysis of aerospace images //«Atmospheric and ocean optics. Atmospheric physics.» X Joint international Symposium, June, 24-28, Tomsk, 2003.-P. 91

18. Колодникова H. В., Протасов К.Т. Алгоритм выделения кластеров путем оценивания локальных мод смешивающего распределения //IX Международный симпозиум «Оптика атмосферы и океана. Физика атмосферы» 2-5 июля, Томск, 2002.

19. Жиглявский А.А. Математическая теория глобального случайного поиска. Л.: Изд-во Ленингр. ун-та., 1985. - 296 с.

20. Протасов К. Т. Рюмкин А. И. Непараметрический алгоритм распознавания объектов подстилающей поверхности Земли по данным аэрокосмической съемки //Вестник Томского Государственного Университета, №275, апрель 2002.-С. 41-46

21. Хомяков Ю.Н., Саушкин В.А. Методы классификации текстур //Зарубежная радиоэлектроника №2,1986. — С. 33—46

22. Харалик Р. М. Статистический и структурный подходы к описанию текстур, ТИИЭР, Т.67, №5, май, 1979.

23. Андреев Г. А., Базарский О. В., Глауберман А. С. и др. Анализ и синтез случайных пространственных текстур //Зарубежная радиоэлектроника, №2, 1984.-C.3-33

24. Потапов А. А. Новые информационные технологии на основе вероятностных текстурных и фрактальных признаков в радиолокационном обнаружении малоконтрастных целей //Радиотехника и электроника, Т. 48, №9, 2003. — С. 1101 1119

25. Напрюшкин А.А. Алгоритмическое и программное обеспечение системы интерполяции аэрокосмических изображений для решения задач картирования ландшафтных объектов //Диссертация на соискание ученой степени кандидата технических наук. Томск, 2002. — 183 с.

26. Robert M. Haralick, К. Shanmugam, Its'hak Distein Texural features for image classification //IEEE transaction in systems, man, and cybernetics, Vol. SMC-3, №6, 1973.-P. 610-621

27. Обиралов А. И. Дешифрование снимков для целей сельского хозяйства. — М., Недра, 1982.-144 с.

28. Ивитская О.В., Колодникова Н.В. Анализ матрицы смежности, используемой для расчета текстурных признаков для задач распознавания изображений //Материалы всероссийской научно-технической конференции, 18—20 мая, Томск, Ч. 1, 2004. С. 179-180

29. Колодникова Н.В. Обзор текстурных признаков для задач распознавания образов //Сборник трудов сотрудников ТУСУРа, Томск. 2004

30. Колодникова Н.В., Протасов К.Т. Функционалы текстур при формировании контекстных признаков для алгоритмов распознавания образов //Сборник трудов П-ой Всероссийской научно-практической конференции студентов, 25-26 февраля, Томск, 2004. — С.75-76

31. Базарский О.В., Коржик Ю.В. Система признаков для анализа и распознавания изображений случайных пространственных текстур //Исследование Земли из космоса №2, 1985. С.108-110

32. Панюшев Д.И. Тхабисимов Д.К. Усиков Д.А. Чеботарев Н.Г. Математические основы построения систем инвариантных признаков в задаче распознавания образов //Математические методы исследования природных ресурсов Земли из космоса. — М.: Наука, 1984. — С.11—23

33. Дистанционное зондирование: количественный подход //Дейвис Ш.М., Ландгребе Д.А., Филлипс Т.Л. и др. /Под ред Свейна Ф. и Дейвис Ш. Пер. с англ. М., Недра, 1983.-415 с.

34. Загоруйко Н.Г. Методы распознавания и их применение. — М.: Советское радио, 1972.-208 с.

35. Васильев В.И. Распознающие системы //Справочник, Киев, Наукова думка, 1983

36. Цыпкин Я.З. Основы теории обучающихся систем М., Наука, 1970. — 252 с.43. http://math.nsc.ru/AP/oteks/Russian/links/SPA/index.html

37. Кузнецов В.П. Представление процессов в задачах приема сигналов. — Радиотехника, Т. 26, № 4, 1971. С. 50-55

38. Пугачев B.C. Теория вероятностей и математическая статистика. — М.: Наука, 1979.-496 с.

39. Завьялов Ю.С., Квасов Б. И., Мирошниченко В. JI. Методы сплайн-функций. — М.: Наука, 1980. — 352 с.

40. Ramberg J.S., Schmeiser B.W. An approximate method for generating symmetric random variables. Communication of the Acm, Vol. 15, № 11, 1972. — P. 987-990

41. Ramberg J.S., Dudewicz E.J., Tadikamalla P.R., Mykytka E.F. A probability distribution and its uses in fitting data — Technometrics, Vol. 21, № 2, 1979. — P. 201-214

42. Форсайт Дж., Малькольм M., Моулер К. Машинные методы математических вычислений. -М.: Мир, 1980

43. Мицель А.А. Вычислительная математика: Лабораторный практикум. — Томск: Томский государственный университет систем управления и радиоэлектроники, 1999. 106с.

44. Мицель А.А. Катаев М.Ю. Приближение сплайнами: Учебное пособие. — Томск: Томский государственный университет систем управления и радиоэлектроники, 2001. 40 с.

45. Мицель А.А., Колодникова Н.В., Протасов К.Т. Непараметрический алгоритм текстурного анализа аэрокосмических снимков //Известия ТПУ, №1, 2005. — С.65-70

46. Епанечников В.А. Непараметрическая оценка многомерной плотности вероятности //Теория вероятностей и её применение, Т. 14, Вып. 1, 1969. С. 156-161

47. Тарасенко Ф.П. Непараметрическая статистика. — Томск: ТГУ, 1976. — 294с.

48. Цыпкин Я.З. Адаптация и обучение в автоматических системах — М.: Наука, 1968.-400с.

49. Той, J. Т. and Gonzalez R. С. Pattern Recognition Principles, Addison-Wesley Publishing Company, Reading, Massachusetts, 1974.

50. ENVI 3.4 User's Guide, BSC Inc, 2001.

51. Richards J.A., 1994, Remote Sensing Digital Image Analysis, Springer-Verlag, Berlin. P. 340.

52. Kruse, F. A., Lefkoff, А. В., Boardman, J. В.и др. The Spectral Image Processing System (SIPS) //Interactive Visualization and Analysis of Imaging spectrometer Data: Remote Sensing of Environment, Vol. 44, 1993. P. 145 - 163

53. Mazer, A. S., Martin, M., Lee, M., and Solomon, J. E. Image Processing Software for Imaging Spectrometry Analysis //Remote Sensing of Environment, Vol. 24, № 1, 1988.-P. 201-210

54. Rumelhart D., Mc Clelland J. Learning Internal Representation by Error Propagation //Parallel Distributed Processing, Vol. 1, 1987

55. ERDAS IMAGINE 8.5 Tour Guides, ERDAS Inc. 200165. http://www.amlab.ru/papermax.shtml66. http://www.geo.pu.ru/ecobez/edu/books/eis/index.htm67. http://www.clarklabs.org68. www.royint.com/ermapper/69. http://www.sovzond.ru/soft/ermapper.html

56. Загубный Д.Г. Новая программа обработки векторных и растровых дистанционных материалов для ГИС //Исследование Земли из космоса, №5, 2004

57. Ожегов С. И. «Словарь русского языка» М.: Русский язык, 1989. - 750с.

58. Пьявченко, Козловская, Изучение болотных биогеоценозов //Программа и методика биогеоценотических исследований. — М., Наука, 1974. — С.267—280.

59. Глебов Ф.З. Экологическая терминология в болотоведении //Сибирский экологический журнал, №5, 2000. — С. 549 555

60. Лисс О.Л., Абрамова Л.И., Аветов Н.А. и др. Болотные системы Западной Сибири и их природоохранное значение /под ред. д.б.н. проф. В.Б. Куваева. — Тула, Гриф и К°, 2001. 584с.

61. Нейдштат М. И. Научные предпосылки освоения болот Западной Сибири М., Наука, 1977. - 228 с.

62. Лапшина Е.Д., Королюк А.Ю., Блойтен В. и др. Структура растительного покрова западной части Большого Васюганского болота (на примере ключевого участка «Узас») //Сибирский экологический журнал, №5, 2000. — С. 563 -576

63. Топографическая карта М 1:500 000. Лист O-44-B (Северное). ГШ СССР: Предприятие №8, 1987

64. Инишева Л.И., Трунов А.Е., Хмелев В.А. Торфоболотные экосистемы Западной Сибири, направления их исследований и использования //Сибирский экологический журнал, №5, 2000. — С. 557-562.

65. Ипполитов И.И., Кабанов М.В., Комаров А.И., Кусков А.И. Роль Большого Васюганского болота в формировании температурного режима Западной

66. Сибири //III Международный симпозиум «Контроль и реабилитация окружающей среды», Материалы докладов, Томск. — 2002

67. Кобак К.И., Боч М.С., Кранкина О.Н. Роль болот в углеродном цикле (на примере Ленинградской области) //Материалы третьей научной школы «Болота и биосфера» 13-16 сентября, Томск, 2004. С. 10-20

68. Инишева Л.И., Головацкая Е.А. Сток и эмиссия углерода в Васюганском болоте //Большое Васюганское Болото. Современное состояние и процессы развития /под общей ред. чл.-коор. РАН М.В. Кабанова. — Томск, изд-во Института оптики Атмосферы СО РАН, 2002.

69. Порохина Е.В. Эмиссия СОг мелиорированными торфяными почвами Западной Сибири) //Материалы третьей научной школы «Болота и биосфера» 13-16 сентября, Томск, 2004. С. 100-110

70. Ракович В.А., Бамбалов Н.Н. Влияние болот на формирование парниковых газов (на примере Беларуси) //Материалы третьей научной школы «Болота и биосфера» 13-16 сентября, Томск, 2004. — С. 38-20

71. Крылова А.И. Крупчатников В.Н. Глобальное моделирование потоков метана об болотных экосистем //сб. трудов «Большое Васюганское болото» — Томск: ИОМ СО РАН, 2002. С.98-103.

72. Чекалина Т.И. Использование аэрокосмической информации в географических исследованиях и решении народно-хозяйственных задач // Итоги науки и техники. Серия «Исследование Земли из космоса», Т.З, 1989.-С.81-209.

73. Колодникова Н.В., Загорулько В.А., Протасов К.Т. Распознавание текстурно однородных полей видеоданных васюганского болота по данным космосьемки //География и природные ресурсы, Спец. вып., 2004. С.64-70

74. Альтер С.П. Ландшафтный метод дешифрирования аэрофотоснимков. Общие принципы и положения. — М.: Наука, 1966. — 88 с.

75. Виноградов Б.В. Космические методы изучения природной среды. — М.: Мысль, 1976.-286 с.

76. Аковецкий В.И. Дешифрирование снимков. — М.: Недра, 1983.—374 с.

77. Ильин Р.А. Природа Нарымского края, Томск, 1930

78. Протасов К. Т. Выделение полей облачности на космических снимках алгоритмом сегментации, основанным на классификации и распознавании образов //Оптика атмосферы и океана, №1, 1998. С. 79-85

79. Облака и облачная атмосфера. Справочник /Под ред. Мазина И.П., Хргиа-на А.Х. Ленинград, Гидрометеоиздат, 1989

80. Kolodnikova N. V., Protasov K.T. The recognition of clouds fields types by nonparametric algorithm in textural feature space on cosmic data //Proceeding of SPIE, 2005

81. Курилова Ю.В., Колосов П.А., Поплавская JI.К., Соколов Ю.С. Методики дешифрирования спутниковой информации на примере исследования снежного покрова. //Сб. статей: Аэрокосмические исследования Земли. — М.: Наука, 1979.-304 с.

82. Бураков Д.А., Кашкин В.Б., Сухинин А.И. и др. Методика определения заснеженности речного бассейна по спутниковым данным для оперативных прогнозов стока //Метеорология и гидрология, № 8, 1996. — С. 100-109

83. Бураков Д.А., Авдеева Ю.В. Технология оперативных прогнозов ежедневных расходов (уровней) воды на основе спутниковой информации о заснеженности (на примере р. Нижней Тунгуски). //Метеорология и гидрология, № 10, 1996.-С. 75-87.

84. Бухаров М.В., Геохланян Т.Х., Соловьев В.И. Распознавание типов снежного и ледового покровов по микроволновым измерениям со спутника «NOAA». //Метеорология и гидрология, № 11, 2003. С. 54-63.

85. Кронберг П. Дистанционное изучение Земли: Основы и методы дистанционных исследований в геологии: Пер. с нем. — М.: Мир, 1988.-343 с.106. www.offer.com.ua