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

004617535

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

Вершовский Евгений Алексеевич

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

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (вычислительная техника и информатика)

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

1 С ДЕК 2010

Таганрог 2010

004617585

Работа выполнена в Южном федеральном университете

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

Родзин Сергей Иванович

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

Колесников Анатолий Аркадьевич (Южный федеральный университет, Технологический институт в г. Таганроге)

кандидат технических наук, Евдокимов Алексей Викторович

(Ростовский государственный университет путей сообщения, г. Ростов-на-Дону)

Ведущая организация: Федеральное государственное

унитарное предприятие «Таганрогский научно-исследовательский институт связи», г. Таганрог

Защита диссертации состоится «23» декабря 2010 г. в 14:20 на заседании диссертационного совета Д 212.208.22 при Южном федеральном университете по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в научной библиотеке Южного федерального университета но адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан «17« ноября 2010 г.

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

диссертационного совета Д 212.208.22, доктор технических наук, профессор

Целых А.Н.

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

Актуальность темы. Мультиспектральные данные дистанционного зондирования Земли (ДЗЗ), получаем!,ie с помощью космической съемки, позволяют исследовать характеристики объектов земной поверхности, которые не проявляются в панхроматическом режиме. Эта информация находит применение во многих отраслях: в сельском и лесном хозяйстве, нефтегазовом комплексе, картографировании, экологии, охране окружающей среды и в управлении чрезвычайными ситуациями, что свидетельствует об актуальности и важности задач обработки информации и дешифрирования мультиспектральных снимков.

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

Перечисленные особенности обусловили выбор в качестве объекта исследования методы и алгоритмы кластеризации мультиспектральных данных ДЗЗ. Большой вклад в становление и развитие теории и практики обработки информации и анализа данных ДЗЗ внесли отечественные и зарубежные учёные Арманд H.A., Асмус В.В., Вудс Р.. Гонсалес Р., Жардан JL Журкин И.Г.. Злобин В.К.. Кронберг П., Лукьящснко В.И., Лупян Е.А., Макриденко Л.А., Новиков М.В., Новикова H.H., Полищук Г.М., Прэтт У., Розенфельд А., Селиванов A.C., Сойфер В.А., Хуапг Т., Чернявский Г.М. и др.

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

I

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

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

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

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

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

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

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

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

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

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

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

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

Практическая ценность заключается в реализации в виде программного обеспечения разработанных методов и алгоритмов. Программное обеспечение «ЯБМООиз» может использоваться для кластеризации данных ДЗЗ и проведения предварительного анализа отдельных спектральных каналов. Об этом свидетельствует успешная апробация результатов в научно-производственной компании «Бюро Кадастра Таганрога», одним из приоритетных профиль ных направлений которой является обработка данных зонального ДЗЗ.

Реализация и внедрение результатов работы. Диссертационные исследования являются частью плановых научно-исследовательских работ. Они были использованы в НИР№2.1.2/1652 «Разработка теории и когнитивных принципов принятия решений на основе распределенных алгоритмов, инспирированных природными системами», в гранте РФФИ № 09-01-00492-а «Разработка общей теории и когнитивных принципов эволюционных вычислений» (2009-2011 гг.), в гранте РФФИ № 09-07-00318-а «Разработка новых принципов извлечения знаний на основе распределенных алгоритмов генетического программирования и роевого интеллекта» (2009-2011 гг.), а также в рамках госбюджетной НИР № 12050. Кроме того, результаты диссертационной работы реализованы в учебном процессе факультета автоматики и вычислительной техники Таганрогского технологического института Южного федерального университета.

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

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

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

3.Разработанный дивизимный алгоритм кластеризации данных ДЗЗ позволяет снизить количество итераций на 20-25%, по сравнению с применением ¿-средних и 180ЭАТА, при сохранении достоверности кластеризации, имеет линейную оценку временной сложности в зависимости от количества объектов, кластеров и спектральных каналов.

4.Роевой алгоритм кластеризации данных ДЗЗ позволяет добиться значительного повышения точности кластеризации, что подтверждается снижением среднеквадратичной ошибки кластеризации по сравнению с алгоритмами А-средних и 18СЮАТА, в среднем, на 38%.

Публикации. Полученные в диссертации теоретические и практические результаты нашли своё отражение в 12 печатных работах. Из них 3 статьи опубликованы в изданиях из списка ВАК. Имеется свидетельство об официальной регистрации программы для ЭВМ. Результаты также отражены в учебно-методическом пособии по программированию алгоритмов распознавания изображений в интерактивной среде МаЦлЬ.

Апробация основных теоретических и практических результатов работы проводилась на научных семинарах кафедры МОП ЭВМ; па международных конференциях: «Проблемы агропромышленного комплекса» (Бангкок-Паттайя, 2009), «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, 2007); на всероссийских конференциях: «Технологии М!сгояо11 в теории и практике программирования» (Таганрог, 2008), «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки» (Таганрог, 2009, 2010), «Информационные технологии, системный анализ и управление» (Таганрог, 2009), «Перспективы развития информационных технологий» (Новосибирск, 2010).

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

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

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

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

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

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

4

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

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

Исследование стандартного восьмиканалыюго мультиспектрального снимка с целью выявления наиболее информативных каналов позволило исключить из дальнейшего рассмотрения 3 канала, оставив наиболее информативные с точки зрения автоматической кластеризации каналы Red, NIR, SWIR, MIR и панхроматический канал Р (рисунок 1 и рисунок 2).

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

Blue

Green

SIVIR TIR MIR P

Рисунок l. Гистограммы спектральных каналов восьмиканалыюго снимка

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

5

25 20 15 10 5 0

Blue

Green

Red

NIR

SWIR

TIR

MIR

^'^Среднеквадратичная ошибка

Максимальное среднее расстояние от точек до асоциироеанныхс ними кластеров Минимальное расстояние между всеми парами кластеров

Рисунок 2. Сравнение результатов кластеризации спектральных каналов алгоритмом \i-means (20 итераций, 5 классов)

а б в г

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

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

В качестве индекса для усиления классификатора в задаче кластеризации данных ДЗЗ используются следующие индексы:

• относительный вегетационный индекс (RVI)

NIR

RVI = -

RED

• нормализованный разностный вегетационный индекс (NDVI)

NIR - RED

NDVI = -

NIR + RED

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

• изовегетационные линии сходятся в начале координат;

• почвенная линия (наклон = 1) проходит через начало координат;

• возможные значения находятся на интервале [0, а> ).

Влияние индексов на кластеризационные свойства получаемого

изображения предлагается оценивать по следующему алгоритму.

1. Вычислить индекс для каждой спектральной сигнатуры пикселя.

2. Провести кластеризацию одномерного индексированного изображения.

3. Полученную кластеризационную карту спроецировать на многомерное пространство исходно мультиспсктральпого снимка.

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

Вычислительная трудоемкость алгоритма составляет О (т*п2), где п -количество точек, т - количество каналов. Результаты кластеризации приведены на рисунках 4-6 в виде графиков изменения показателей кластеризации по алгоритму А-шеапБ (4 класса, 20 итераций): исходного 6-каналыюго снимка, 1-каналыюго ЫОУ1-изображепия и 1-канального изображения (а - динамика среднеквадратичной ошибки, б - динамика впутрикластерного расстояния, в - динамика межкластерного расстояния).

а б в

Рисунок 4. Результаты кластеризации 6-канапьного снимка .,

\ \

\ \ \ V ..

а б в

Рисунок 5. Результаты кластеризации I-канального N1) V! изображения

\

а б в

Рисунок б. Результаты кластеризации 1-канального ЯУ1 изображения

Таким образом, усиление классификатора в задаче кластеризации данных ДЗЗ, комбинирующее гистограммкые преобразования информативных каналов

и вычисление вегетационного индексированного изображения с помощью N04^1 и индексов позволяет увеличить межкластерные расстояния и

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

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

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

К алгоритму кластеризации данных ДЗЗ предъявляется требование отсутствия блуждания в окрестности оптимального решения, за счет повторного объединения/разделения кластеров. Это предопределяет однонаправленность кластеризации: агломеративная либо дивизимная кластеризация. Под агломеративной кластеризацией подразумевается последовательное объединение кластеров до множества, совпадающего по мощности с исходным пространством объектов. Это неприемлемо при кластеризации ДЗЗ ввиду большого количества спектральных сигнатур. Оптимальным вариантом является не объединение синглетонов до получения требуемого количества кластеров, а последовательное разбиение исходного множества объектов на непересекающиеся кластеры. Тем самым, определяется дивизимный характер разрабатываемого алгоритма.

При работе с набором {х/, х2,...,хц¡, составленным из /V спектральных сигнатур, предлагаемый новый алгоритм включает следующие шаги.

1. Задаются параметры, определяющие процесс кластеризации:

К - необходимое число кластеров;

М/, - количество измерений спектральных сигнатур;

/-допустимое число циклов итерации.

2. Заданные Л'образов распределяются по кластерам по правилу

х1 в Су если ||х, - г, || < Цд:, - = 1,2 ...N¿1 Ф = 1,2 ...¿V, где С} - подмножество образов выборки, включенных в кластер с центром Правило применяется ко всем образам х, вошедшим в выборку.

3. Каждый центр кластера г,,у-1, 2 ... корректируется посредством приравнивания его выборочному среднему по подмножеству С) , то есть

4. Вычисляется среднее расстояние между объектами, входящими в

8

подмножество Ср и соответствующим центром кластера по формуле Dj= = 1,2--.\Cj\.

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

6. Для каждого подмножества с помощью соотношения

aij = Ji^iZxeqfak -Zijf .i = 1-2 ~Nb; j = 1,2 ...Nc.

вычисляется вектор среднеквадратичного отклонения Oj = (ffiy^y, ....Одг у), где Nb - размерность образа, x,k - i-я компонента к-го объекта в подмножестве Су, 7y — i-я компонента вектора, представляющего центр кластера z,, |Су|-количество выборочных образов, включенных в подмножество Су. Каждая компонента вектора оу характеризует среднеквадратичное отклонение образа, входящего в подмножество Су, по одной из главных осей координат.

7. В каждом векторе среднеквадратичного отклонения Оу, j= 1, 2,..., Nc отыскивается максимальная компонента Ojmax-

8. Если для любого Ojmax, j= 1, 2,..., Nc выполняются условия Dy > I) и Nc < К, то кластер с центром :t расщепляется на два новых кластера с центрами -у. и гу. соответственно, кластер с центром zj ликвидируется, а значение Nc увеличивается на 1. Для определения центра кластера к компоненте вектора г,, соответствующей максимальной компоненте вектора <т;, прибавляется заданная величина у,; центр кластера;,- определяется вычитанием этой же величины у, из той же самой компоненты вектора г,. В качестве величины Yj выбирается доля значения максимальной среднеквадратичной компоненты а;^, то есть определяется у„ = к а)пшх, где 0 < k < I.

9. Если текущий цикл итерации является последним, то выполнение алгоритма прекращается. Иначе следует возвратиться к шагу 2.

Общая структурная схема алгоритма представлена на рисунке 7.

Оценка временной сложности представленного алгоритма равна O(nkd), оценка пространственной сложности равна О(п), где п - количество объектов, к - количество кластеров, d - количество спектральных каналов.

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

В главе также разрабатывается эволюционный алгоритм кластеризации на основе оптимизации роя частиц. Роевой оптимизатор представляет собой эволюционный поисковый процесс, в котором частицы группируются в рой. Каждая частица в рое кодирует потенциальное решение задачи кластеризации изображения. Она представляет A't средних кластеров, то есть каждая частица кодируется как Xi — (тц,......,miNc), где т^ - вектор центра 7-010

кластера /-ой частицы.

Задание определяющих

параметров кластеризации

Объекты ( пиксели) распределяются по кластерам, соответствующим выбранным исходным центрам

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

Вычисляется среднее расстояние ^ между объектами, входящими в подмножество кластера, и соответствующим центром кластера

Вычисляется обобщенное среднее расстояние О между объектами, находящимися в отдельных кластерах, и соответствующими центрами кластеров

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

©

6

Рисунок 7. Схема дивизимного алгоритма кластеризации Целевая функция оптимизации в роевом алгоритме выглядит следующим образом:

= + М2(7,тах - (¿тш(Х)),

где гтах - максимальное значение спектральной сигнатуры пикселя в мультиспектральном изображении, 1 - матрица принадлежности спектральных сигнатур пикселей кластерам частицы /. Элемент 7.цр е 2показывает, принадлежит ли спектральная сигнатура пикселя ?р кластеру C¡j частицы /. Константы IV!и и/2 являются весовыми коэффициентами, задаваемыми на начальном этапе алгоритма. Максимальное среднее евклидово расстояние от частиц до ассоциированных с ними кластеров вычисляется но формуле

х^) = таху=1

7 = 1.....Л/с | ^ ¿(2р

™ц)!\Сц\(

где |С[.-| - мощность множества (?,.-. Минимальное евклидово расстояние между

всеми нарами кластеров.

тИ,-тИг

Фитнесс функция обеспечивает выполнение одновременно двух оптимизационных подзадач:

• сведение к минимуму внутренних расстояний между спектральными сигнатурами пикселей кластеров и их средними, обеспечиваемое <1тах(2, Х;);

• сведение к максимуму внешних расстояний между любыми парами кластеров, обеспечиваемое dmin(xi).

Приоритеты между этими целями могут быть определены на этапе инициализации значений и'1и

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

1. Случайным образом установить Д^ средних кластеров для каждой частицы.

2. Цикл от /=1 до 1„юх

a. Для каждой частицы

¡. Для каждой спектральной сигнатуры пикселя изображения 2р:

• вычислить для всех кластеров Сц,

• произвести присвоение сигнатуры пикселя кластеру на основании сравнения

¿(гр,ти) = ттУс=1.....^Д й{гр,ти)}

п. Вычислить целевую фунщию/(х((С), ¿),

b. Найти лучшее глобальное решение

у(1) = тт^О). 1), Г(х2(0, Ъ).....ПХ(0, г)}

c. Пересчитать значения центров кластеров с учетом выражений

+ 1) = 1^,(0 + £^(0(^(0 -+ с2г2(0(у(0 -х1{1 + 1)= *,-(£) + ^(£ + 1). Структурная схема разработанного алгоритма представлена на рисунке 8.

Рисунок 8. Схема алгоритма роевой кластеризации Оценка временной сложности представленного алгоритма равна О(пксй), оценка пространственной сложности равна 0(пс1), где п - количество объектов, к - количество кластеров, с! - количество частиц, 1 - количество итераций.

п

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

Бенчмарки для общей задачи кластеризации, например Fisher's Fris dataset, не могут быть использованы для оценки точности кластеризации данных ДЗЗ, так как, предполагают семантический, а не пространственно-графический характер объектов и допускают пересечение кластеров, что противоречит специфике данных ДЗЗ. Использование же матрицы ошибок обладает существенными недостатками: необходимостью взаимно-однозначного соответствия классов и наличия проверочной кластеризационной карты.

В таблице 1 представлена матрица соответствия. Al, А2...Ап - классы, полученные кластеризацией снимка алгоритмом А. В1, В2...Вп - классы, полученные кластеризацией снимка алгоритмом В. Неизвестно, какому из классов Al, А2...Ап соответствует какой класс из BI, В2...Вп. В ячейках таблицы указано количество сигнатур, располагающихся одновременно в классах столбца и строки.

Остальные значения матрицы соответствия вычисляются по формулам: С-т = Ъ^А/ш J1..... п ;cAj. = УcAjm ,i I.....п ;

N = jfi.Hr- jcAj.J=l,...,n,j=/,..., п.

__Таблица 1- Матрица соответствия

Результат кластеризации алгоритмом В

BI В2 вз Bn Cai-

Результат кластеризации алгоритмом А AI Caibi са1в2 CAIB3 сд1в, CAlBn

А2 сд2в! са2в2 ca2b3 ca2bî ca2bn CA2-

A3 сдзв1 сазв2 сдзвз Сазв| сазвп Саз-

ед[В | сдпв1 cajb2 _ сд[вз_ сапвз CajBj e.\!!n слппп елп-

An саПв2 CAnBi

Zbi С-в1 С-в2 С-вз е., C-Bn N

Соответствие классов устанавливается следующей процедурой.

1. Пусть/

2. Поиск максимального элемента в строке матрицы сАкц,„ тлх(сА//1т).

3. Проверка, является ли найденный элемент также максимальным и в столбце. Нсли сАкНт = тах^мн,), тогда класс Ак соответствует классу Вт. Исключаем к-ю строку и т-й столбец из дальнейшего рассмотрения. В противном случае увеличиваем/.

4. Если j п, завершаем процедуру. В противном случае переход к шагу 1. Обозначим через с1Акц,п значение ячейки к-ой строки т-ого столбца,

которое устанавливает соответствие класса Ак классу Вт и является максимальным в данной строке и столбце. Сумма значений с[АкНт показывает общее количество отнесенных к соответствующим друг другу классам пикселей, а отношение этого количества к общему количеству пикселей N назовем общим соответствием (Охега11Ассоп1апсе) кластеризации

OverallAccordance = 1. MBL

N

11оказатель точности соответствия для каждого алгоритма (AccordanceAccuracy)отображает отношение количества пикселей, лежащих на пересечении k-ой строки и m-ого столбца, к сумме значений по строке или по столбцу, в зависимости от того, оценка какого алгоритма необходима. Тогда

^-АкВтп.

AccordanceAccuracyAk = -.

сАк-

Ошибкой соответствия класса Ак по результатам работы алгоритма А, которому соответствует класс Вт, полученный в результате работы алгоритма В. назовем выражение:

Accordance ErrorAk = 1 - Accordance AccuracyАк.

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

£7=1 Accordance AccuracyAi Accordance AccuracyA = -.

Общий показатель ошибки соответствия рассчитывается как:

£™=1 Accordance ErrorAi

Accordance Err orА = -.

д n

Аналогичным образом показатели определяются для класса В.

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

щтщшш т л* т 4r\---«л»

Ix^re г Л W

Рисунок 9. Результаты кластеризации: а,б алгоритма А и алгоритма В без проведения соответствия классов, в, г алгоритма А и алгоритма В после проведения соответствия

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

алгоритмов с классическими алгоритмами кластеризации, применяемыми в задаче автоматического дешифрирования данных ДЗЗ.

В экспериментах использованы десятки мультиспектральных снимков, охватывающих различные климатические зоны (степи, горные рельефы, различные леса и водоемы). В частности, был использован снимок г. Таганрога (6 каналов, 251779 точек) и снимок Таганрогского залива и г. Ростов-на-Дону (6 каналов, 1307748 точек). Все снимки получены из открытого хранилища снимков спутников Ьаг^а1ЕТМ, расположенного в глобальной сети Интернет по адресу http://landsat.orft/, и не являются секретной информацией.

Сравнение характеристик существующих и разработанных алгоритмов представлено в таблице 2.

Таблица 2 - Сравнение алгоритмов кластеризации

Название алгоритма Временная сложность алгоритма Вычислительная сложность алгоритма Недостатки алгоритма (с точки зрения кластеризации данных ДЗЗ)

CURE 0(n2*logn) 0(n) Требует задания пороговых значений и количества кластеров.

BIRCH 0(п) 0(n) Требует задания пороговых значений.

K-means O(nkl) 0(k+n) Является критичным к выбросам, невозможно выявить пересекающиеся кластеры.

ISODATA O(nkl) 0(k) Требует задания количества кластеров. Низкая скорость обработки больших объемов данных.

CLOPE O(nk) 0(n) Обработка категориальных данных, плохие результаты при кластеризации данных с нормальным распределением.

Карты Кохонена O(nkl) 0(k+n) Обработка только числовых данных, требуется задание количества кластеров.

Fuzzy C-Means 0(ndlkJ) 0(nd + nk) Неопределенность с равноудаленными от центров кластеров объектами.

Hard C-means O(nkdl) O(kd) Многократный перебор исходных данных в пределах итерации.

Лишними i.iii алгоритм O(nkd) 0(n+k) За счет нситеративиого характера не позволяет улучшить текущий результат.

Соевой алгоритм 0(n2kdi) O(ndk) Сравнительно большая вычислительная сложность.

В результате экспериментов установлено следующее:

• метод оценки точности кластеризации обладает устойчивостью и достоверностью;

• применение гистограммных преобразований и вегетационного

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

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

• дивизимный алгоритм кластеризации ДЗЗ позволяет получать результаты, не худшие, по сравнению с применением классических алгоритмов ¿-средних и 18СШАТЛ за меньшее количество итераций; роевой алгоритм кластеризации мультиспектральных ДЗЗ позволяет получать существенно лучшие, по сравнению с ними результаты, но за большее время.

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

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

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

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

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

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

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

15

сохранением результативности кластеризации. Оценка временной сложности дивизимного алгоритма равна O(nkd), оценка пространственной сложности равна О(п), где п - количество объектов, к - количество кластеров, d -количество спектральных каналов. Применение алгоритма позволило сократить количество итераций при кластеризации мультиспектрального снимка на 20-25%, по сравнению с применением ¿-means и ISODATA.

4. Разработан новый роевой алгоритм кластеризации на основе метода оптимизации роя частиц, отличающийся от аналогов уменьшением эффекта зависимости результатов от начальных условий, а также увеличением эффективности кластеризации за счет получения меньших внутрикластерных расстояний в процессе оптимизации роя. Оценка временной сложности алгоритма роевой кластеризации равна 0(n2kd¡), оценка пространственной сложности равна O(ndk), где п-количество объектов, к-количество кластеров, d-количество частиц, ¡-количество итераций. Применение алгоритма позволило обеспечить минимизацию среднеквадратичной ошибки по результатам кластеризации по сравнению с применением ¿-means и ISODATA, в среднем, на 38%, тем самым обеспечивая более высокую точность кластеризации.

5. Разработано программное обеспечение кластеризации мультиспектральных данных дистанционного зондирования «RSMDCIus», получившее промышленное внедрение.

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

Публикации в изданиях, рекомендованных ВАК РФ

1. Вершовский Е.Л. Алгоритмы предварительной обработки изображений методами интеллектуального анализа многомерных данных // Известия ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФУ, 2008, № 2. - С. 37 -40.

2. Вершовский Е.А. Роевой алгоритм оптимизации в задаче кластеризации мультиспектрального снимка //Известия ЮФУ. Технические науки. - 2010. -№5(106).-С. 102- 107.

3. Вершовский Е.А. Метод контроля качества кластеризации мультиспектрального изображения // Известия ЮФУ. Технические науки. -Таганрог: Изд-во ТГИ ЮФУ, 2010. - №7(108). - С. 191-198.

Свидетельства о регистрации программ на ЭВМ

4. Вершовский Е.А.Свидетельство № 2010613236 об официальной регистрации программы для ЭВМ от 17.05.2010. Программа кластеризации мультиспектральных данных дистанционного зондирования "RSMDCIus".

Учебно-методические пособия

5. Родзин С.И., Вершовский Е.А. Программирование алгоритмов распознавания изображений в интерактивной среде MatLab. - Таганрог: Изд-во ТТИ ЮФУ, 2010. - 68 с.

Публикации в других изданиях

6. Вершовский Е.А. Интеллектуальный анализ мультиспектральных характеристик цифровых снимков земной поверхности // В сб. докладов V научной конференции аспирантов базовых кафедр Южного научного центра РАН. - Ростов-на-Дону: Изд-во ЮПЦ РАН, 2009. -С. 85-86.

7. Вершовский Е.А. Методика объектно-ориентированного дешифрирования в задачах мониторинга территорий // Современные наукоемкие технологии, 2009, № 12.-С. 33-34.

8. Вершовский Е.А. Информационная система аналитической обработки данных на основе технологий Microsoft // Труды V Всероссийской конференции "Технологии Microsoft в теории и практике программирования". - Таганрог: Изд-во ТГИ ЮФУ, 2008. - С. 97-103.

9. Вершовский Е.А. Особенности распознавания видового разнообразия растительного покрова на многоспектральных аэрокосмических изображениях // Труды Всероссийской научной школы-семинара «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки». 2009 г., г. Таганрог. - Таганрог: Изд-во ТТИ ЮФУ, 2009. - С. 4-7.

10. Вершовский Е.А. Спектрально-ориентированная методика обработки космических снимков // Сб. трудов VII Всероссийской научной конференции "Информационные технологии, системный анализ и управление". - Таганрог: Изд-во ТТИ ЮФУ, 2009. - С. 228-232.

11. Вершовский Е.А. Интерпретация данных ДЗЗ // Сб. материалов II Всероссийской научно-практической конференции «Перспективы развития информационных технологий». - Новосибирск: ЦРНС - Издательство СИБПРИИТ, 2010. - С. 43-45.

12. Вершовский Е.А. Методика объектно-ориентированного дешифрирования в задачах мониторинга территорий // Современные наукоемкие технологии, 2009, № 12.-С. 33-34.

Личный вклад автора в работах, опубликованных в соавторстве: [5] -

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

алгоритмов.

Соискатель ------Е.А. Вершовский

Вершовский Евгений Алексеевич

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

Автореферат

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

Подписано в печать 15 11.10 Формат бумаги 60*84 1/16. Гарнитура Тайме. Бумага офисная. Печать цифровая Усл. печ. л. 1,0 Уч.-изд. л. 1 0 Тираж 100 эт

Технологический институт «Южного федерального университета» в г.Тагамроге 347928, г. Таганрог, пер. Некрасовский, 44

ВВЕДЕНИЕ.

1 СИСТЕМНЫЙ АНАЛИЗ ОБРАБОТКИ МУЛЬТИСПЕКТРАЛЬНОЙ ИНФОРМАЦИИ ДИСТАНЦИОННОГО ЗОНДИРОВАНИЯ ЗЕМЛИ.

1.1 Обзор систем обработки мультиспектральной информации дистанционного зондирования Земли.

1.2 Стратегии интерпретации мультиспектральной информации дистанционного зондирования Земли.

1.3 Формулировка проблемной ситуации.

1.4 Выводы.:.

2 РАЗРАБОТКА МЕТОДА СОКРАЩЕНИЯ РАЗМЕРНОСТИ И УСИЛЕНИЯ КЛАССИФИКАТОРА.

2.1 Определение цели разработки и критериев ее достижения.

2.2 Пространственный анализ спектральных каналов.

2.3 Поиск оптимального варианта решения.

2.3.1 Отбор информативных спектральных каналов.

2.3.2 Гистограммное усиление классификатора.

2.3.3 Усиление классификатора вегетационным индексированием.

2.4 Выводы.

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

3.1 Определение цели разработки и критериев ее достижения.

3.2 Кластерный анализ мультиспектрального снимка.

3.3 Поиск оптимального варианта решения.

3.3.1 Разработка дивизимного алгоритма кластеризации.

3.3.2 Разработка алгоритма роевой кластеризации.

3.4 Выводы.

4 РАЗРАБОТКА МЕТОДА ОЦЕНКИ ТОЧНОСТИ КЛАСТЕРИЗАЦИИ.

4.1 Определение цели разработки и критериев ее достижения.

4.2 Стратегии сравнения результатов.

4.3 Поиск оптимального варианта решения.

4.4 Выводы.

5 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ МЕТОДОВ И АЛГОРИТМОВ ОБРАБОТКИ МУЛЬТИСПЕКТРАЛЬНОЙ ИНФОРМАЦИИ.

5.1 Планирование экспериментов.

5.2 Анализ метода сравнительной оценки точности кластеризации.

5.3 Анализ метода усиления классификатора.

5.4 Анализ дивизимного алгоритма кластеризации.

5.5 Анализ алгоритма роевой кластеризации.

5.6 Выводы.

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

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

Исходя из анализа методов дешифрирования космических снимков [3-6], а также из обзоров [7-10] программных продуктов мировых лидеров в области обработки космических снимков (ENVI, ERDAS), можно сделать следующие выводы:

• применяемые алгоритмы обработки „ мультиспектральной информации - алгоритм k-средних (K-means) и итеративный самоорганизующийся метод анализа данных (Isodata - Iterative Self-Organizing Data Analysis Techniques) не обеспечивают высокого уровня точности и достоверности результатов;

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

• применение рассчитываемых спектральных (вегетационных) индексов позволяет увеличить качество дешифрирования областей растительности на снимках, однако данное множество признаков используется лишь для визуальной интерпретации снимков и не участвует в процессе неконтролируемой классификации [12-14] .

Одновременно с этим, на основании анализа перспективных направлений в области кластерного анализа [15-18], можно заключить следующее:

• современные масштабируемые алгоритмы (EM^CLOPE) разработанные для кластеризации нечетких (категориальных) данных неприемлемы для задачи дешифрирования данных дистанционного зондирования Земли, в которых основными признаками распознаваемых объектов поверхности являются числовые показатели яркости отраженного света в определенном спектре;

• современные разработки в области кластеризации, направленные на новые масштабируемые алгоритмы, как показывает ряд экспериментов [19] не являются эффективными по сравнению с базовыми основополагающими алгоритмами, например K-means, модифицированным в рамках увеличения скорости и уменьшения количества итераций (проходов по исходным данным) [20] ;

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

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

Значительный вклад в развитие направления обработки и анализа данных дистанционного зондирования Земли внесли отечественные и зарубежные 5 специалисты: Арманд H.A., Асмус В.В. Вудс Р., Гонсалес Р., Жардан Л., Журкин И.Г., Злобин В.К., Кронберг П., Лукьященко В.И., Лупян Е.А., Макриденко Л.А., Новиков М.В., Новикова H.H., Полищук Г.М., Прэтт У., Розенфельд А., Селиванов A.C., Сойфер В.А., Хуанг Т.,Чернявский Г.М. и др. Их исследования в этой и других областях составляют теоретическую основу для решения поставленных в данной работе задач.

Цель работы

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

Общая научная задача

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

Объект и предмет исследования

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

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

Направления проводимых в работе исследований относятся к проблемам разработки и применения методов обработки информации, целенаправленного воздействия человека на объекты исследования, включая вопросы анализа, моделирования, оптимизации, совершенствования управления и принятия решений, с целью повышения эффективности функционирования объектов исследования, и соответствуют формуле специальности 05.13.01 «Системный анализ, управление и обработка информации (технические науки)».

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

Направления проводимых в работе исследований соответствуют следующим областям исследования специальности 05.13.01 «Системный анализ, управление и обработка информации (технические науки)» :

• разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации;

• разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации; 7

• визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации.

Для достижения поставленной цели решались следующие задачи:

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

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

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

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

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

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

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

Научная новизна работы заключается в следующем:

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

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

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

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

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

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

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

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

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

Кроме этого, практическую значимость работы определяет следующее:

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

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

• создано программное обеспечение кластеризации мультиспектральных данных дистанционного зондирования «ЫЗМОСЛиэ» (свидетельство № 2010613236 об официальной регистрации программы для ЭВМ от 17.05.2010).

Разработанный программный продукт может быть применен для кластеризации многомерных данных дистанционного зондирования Земли. И

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

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

Диссертационные исследования являются частью плановых научно-исследовательских работ и были использованы в:

• НИР № 2.1.2/1652 «Разработка теории и когнитивных принципов принятия решений на основе распределенных алгоритмов, инспирированных природными системами»" (№ госрегистрации 01200954120), выполненного в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2009-2010 годы)» по мероприятию 2.1.2 «Проведение фундаментальных исследований в области технических наук»;

• гранте РФФИ № 09-01-00492-а "Разработка общей теории и когнитивных принципов эволюционных вычислений" (2009-2011 гг.);

• гранте РФФИ № 09-07-00318-а "Разработка новых принципов извлечения знаний на основе распределенных алгоритмов генетического программирования и роевого интеллекта" (2009-2011 гг.);

• в рамках научно-исследовательской госбюджетной работы № 12050 по направлению «Интеллектуальные системы обработки информации и могокритериального управления».

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

12 производственной апробации результатов диссертационной работы в научно-производственной компании «Бюро Кадастра Таганрога» (см. прил.1), одним из приоритетных профильных направлений которой является обработка данных дистанционного зонального зондирования Земли.

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

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

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

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

4. Значительное повышение эффективности кластеризации данных дистанционного зондирования Земли, по сравнению с классическими алгоритмами ЗОБАТА и К-теапБ, позволяет получить итеративный

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

5. При наличии выделенных технических средств достаточной мощности для задачи автоматической обработки данных дистанционного зондирования Земли целесообразно использовать алгоритм кластеризации данных, дистанционного зондирования оптимизацией роя частиц, позволяющий добиться; значительного: повышение точности кластеризации; данных дистанционного зондирования Земли; по сравнению с классическими алгоритмами^ ISODATA и K-means.

6: Программное обеспечение «RSMDClus», реализующее разработанные методы и алгоритмы, в отличие от известных систем, таких как ERDAS . Imagine и ENVI, ориентированных только на применение алгоритмов K-means и ISODATA без возможностей усиления, классификатора и сокращения размерности исходных данных в: автоматическом: режиме, позволяет проводить более точную автоматическую, кластеризацию мультиспектральных данных дистанционного зондирования Земли.

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

По; результатам диссертационных, исследований; имеется; 12 публикаций, (вместе с тезисами докладов). Из них, 3 статьи в издании из списка ВАК [2123]; 4 статьи [24-27], 1 труд в материалах Международных конференций [28]. Имеется свидетельство об официальной регистрации программы для ЭВМ №2010613236 [29]. Также результаты диссертационных исследований вошли в учебно-методическое. пособие по программированию алгоритмов распознавания;,изображений в интерактивной средеMatLab [30].

Основные положения диссертационной. работы докладывались и обсуждались на:

• V Ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН, г.Ростов-на-Дону, 8-27 апреля 2009г.,

• V Всероссийской конференции "Технологии Microsoft в теории и практике программирования", г.Таганрог, 13-14 марта 2008г.,

• Международной конференции «Проблемы агропромышленного комплекса» Бангкок-Паттайя (Тайланд), 20-30 декабря 2009

• Всероссийской научной школе-семинаре студентов, аспирантов и молодых ученых «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки», г. Таганрог , 2009 г.,

• VII Всероссийской научной конференции молодых ученых, аспирантов и студентов "Информационные технологии, системный анализ и управление", г. Таганрог, 2009 г.

• VIII Всероссийской научной конференции молодых ученых, аспирантов и студентов "Информационные технологии, системный анализ и управление", г. Таганрог, 2009 г.

• II Всероссийской научно-практической конференции «Перспективы развития информационных технологий», Новосибирск, 2010 г.

• Всероссийской научно-технической конференции с международным участием: "Компьютерные и информационные технологии в науке, инженерии и управлении", г. Таганрог, 2007

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

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

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

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

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

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

3. Разработан новый дивизимный алгоритм кластеризации многозональных космических снимков на основе итеративного самоорганизующегося алгоритма кластеризации, отличающийся от аналогов сокращением числа итераций, получением чётко заданного числа классов, минимизацией количества задаваемых эвристик, с сохранением результативности кластеризации. Результаты экспериментальных исследований показали, что реализация предложенного алгоритма обеспечивает высокое качество кластеризации данных дистанционного зондирования Земли и обладает преимуществами в сравнении с классическими алгоритмами кластеризации, такими как снижение количества итераций при сохранении достоверности кластеризации. Оценка временной сложности дивизимного алгоритма равна О(пкё), оценка пространственной сложности равна О(п), где п - количество объектов, к - количество кластеров, с1 - количество спектральных каналов. Применение алгоритма позволило сократить количество итераций при кластеризации мультиспектрального снимка на 20-25%, по сравнению с применением К-теаш и 1800АТА.

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

151 сложности алгоритма роевой кластеризации равна 0(п2ксИ), оценка пространственной сложности равна О(пёк), где п — количество объектов, к - количество кластеров, с! - количество частиц, 1 — количество итераций. Применение алгоритма позволило обеспечить минимизацию среднеквадратичной ошибки по результатам кластеризации по сравнению с применением К-шеапБ и КСЮАТА, в среднем, на 38%, тем самым обеспечивая более высокую точность кластеризации.

5. Разработано программное обеспечение кластеризации мультиспектральных данных дистанционного зондирования «Я81УЮС1ш» (свидетельство №2010613236 об официальной регистрации программы для ЭВМ от 17.05.2010). Разработанное программное обеспечение внедрено на предприятии ОАО «Научно-производственная компания «Бюро Кадастра Таганрога» (о чем имеется соответствующий акт в приложении 1). Сферы возможного применения программного обеспечения «ЯЗМОСЬб» включают повышение качества разработок творческих и научных коллективов в отрасли обработки мультиспектральной информации и дешифрирования аэрокосмической съемки. Новые знания, полученные в диссертационной работе, способствуют повышению квалификации кадров и вошли в учебную программу обучения студентов.

ЗАКЛЮЧЕНИЕ

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

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

1. Lee, С. Analyzing High Dimensional Multispectral Data / C. Lee ,D. Landgrebe // IEEE Transactions on Geoscience and Remote Sensing, July. 1993. - № 4, pp. 792 - 800.

2. Цветков, В.Я. Геоинформационные системы и технологии /В. Я. Цветков. -М.: Финансы и статистика, 1998. — 288 с.

3. Новаковский, Б. А. Фотограмметрия и дистанционные методы изучения Земли / Б. А.Новаковский. М.: Изд-во Моск. ун-та, 1997. - 193 с.

4. Лурье, И.К. Основы геоинформационного картографирования. М.: Изд-во Моск. ун-та, 2000. - 143 е.

5. Колодникова, Н. В. Алгоритмы и программное обеспечение тематического анализа многоспектральных аэрокосмических снимков земных покровов : дис. . канд. техн. наук : 05.13.18 : / Колодникова Н. В. Томск, 2005. - 200 с.

6. Хлебникова, Е. П. Повышение эффективности регионального мониторинга по космическим снимкам на основе использования эталонов : дисс. канд. техн. наук : 25.00.34 / Е. П. Хлебникова. Новосибирск, 2007 142 с. РГБ ОД, 61:07-5/3342.

7. Программный комплекс ENVI. Учебное пособие. М.: Совзонд. 2009. - 265 с.

8. Наумов, C.B. Особенности обработки космических снимков высокого разрешения / С.В.Наумов // ArcReview 2008. URL: http ://www. dataplus.ru/Arcrev/Numberl 7/10Snimok.htm (дата обращения 02.03.2009).

9. Ермошкин, И.С Современные средства автоматизированного дешифрирования космических снимков / И.С. Ермошкин // ArcReview № 1 (48). 2009. URL: http://www.dataplus.ru/ARCREV/Number48/12deshifr.html (дата обращения 23.09.2009).

10. Обзор международного рынка дистанционного зондирования Земли. Характеристики спутниковых систем Электронный ресурс. URL: http://www.ugi.ru/articles/dzz/review-dzz (дата обращения 17.05.2009).

11. Панарин, В.А. Применение космических снимков в муниципальном управлении урбанизированных территорий для задач территориального планирования /В.А.Панарин , Р.В.Панарин // Журнал "Геоматика/Geomatics"153

12. М: Инф. агентство «ГРОМ». - 2010. - с. 40 - 56.

13. Черепанов, А.С. Спектральные свойства растительности и вегетационные индексы /А.С. Черепанов, Е.Г. Дружинина // Журнал "Геоматика/Geomatics" №3 М: Инф. агентство «ГРОМ». - 2010 . - с. 28 - 33.

14. Huete, A. Modis Vegeation Index (MOD13) / A.Huete , G.Justice //Algorithm theoretical basis document. 1999. - pp. 1331 - 1364.

15. Landgrebe, D. Multispectral Data Analysis: A Signal Theory Perspective / D. Landgrebe // School of Electrical & Computer Engineering Purdue University. -2003.-pp. 508.

16. Паклин, H. Алгоритмы кластеризации на службе Data Mining Электронный ресурс. URL: http://basegroup.ru/clusterization/datamining.htm (дата обращения 03.04.2009).

17. Bradley, P.S. Scaling clustering algorithms to large databases / P.S. Bradley ,U.M. Fayyad,C.A. Reina //Proc. 4th Int. Conf. Knowledge Discovery and Data Mining, Menlo Park, Calif.: AAAI Press .- 1998. pp.9 - 15.

18. Yang, Y. CLOPE: A fast and-Effective Clustering Algorithm for*Transactional Data / Y. Yang, H. Guan,J. You // Proceedings of SIGKDD'02, July 23-26, 2002, Edmonton, Alberta, Canada. 2002'. pp. 682 - 687.

19. Farnstrom, F. Scalability for clustering algorithms revisited / F.Farnstrom, J.Lewis,C.Elkan //SIGKDD Explorations . 2000. - Vol.2 № 1. - pp. 51 - 57.

20. Elkan, C. Using the triangle inequality to accelerate k-means /С. Elkan // Proc. Twentieth Int. Conf. on Machine Learning (ICML'03). 2003. - pp. 147 - 153.

21. Вершовский Е.А. Роевой алгоритм оптимизации в задаче кластеризации мультиспектрального снимка //Известия ЮФУ. Технические науки. 2010 .1545(106).-С. 102- 107.

22. Вершовский Е.А. Метод контроля качества кластеризации мультиспектрального изображения // Известия ЮФУ. Технические науки. Тематический выпуск "Интеллектуальные САПР". -Таганрог: Изд-во ТТИ ЮФУ, 2010. -№7(108). -С.191-198.

23. Вершовский, Е. А. Методика объектно-ориентированного дешифрирования в задачах мониторинга территорий / Е. А. Вершовский // Журнал "Современные наукоемкие технологии", 2009, № 12. С. 33 - 34.

24. Свидетельство № 2010613236 об официальной регистрации программы для ЭВМ от 17.05.2010. Программа кластеризации мультиспектральных данных дистанционного зондирования "RSMDClus". Вершовский Е.А.

25. Родзин, С.И Программирование алгоритмов распознавания изображений в интерактивной среде MatLab. Лабораторный практикум.Курсовая работа / Е.А.

26. Вершовский, С.И. Родзин — Таганрог : Изд-во ТТИ ЮФУ, 2010. 68 с.

27. Landgrebe, D. The Evolution of Landsat Data Analysis / D. Landgrebe // Photogrammetric Engineering and Remote Sensing. 1997. - Vol. LXIII, No.7 . -pp. 859 - 867.

28. Яне, Б. Цифровая обработка изображений /Б. Яне. М.: Техносфера, 2007.

29. Лурье, И.К. Основы геоинформатики и создание ГИС. Дистанционное зондирование и географические информационные системы. Часть 1. /И. К. Лурье. -М.Издательство ООО "ИНЭКС-92", 2002. 140 с.

30. Некрасов, В. В. Разработка технологии использования снимков высокого пространственного разрешения при построении цифровой модели рельефа по материалам космических съемок : дис. канд. техн. наук : 25.00.34 / В.В.Некрасов. Москва, 2008. - 174 с.

31. ДеМерс, М.Н. Геоинформационные системы. Основы. М: Изд-во Дата+, 1999.-490 с.

32. Дробышев, Ф.В. Основы аэрофотосъемки и фотограмметрии . М: Недра, 1973.-288 с.

33. Гонсалес, В. Цифровая обработка изображений в среде MATLAB /

34. B.Гонсалес, Р.Вудс, С.Эддинс, Москва: Техносфера, 2006. - 616 е.

35. Scheunders, P. A Genetic C-Means Clustering Algorithm Applied to Image Quantization / P. Scheunders // Pattern Recognition 1997 . - No 30(6). - pp. 859 -866.

36. Scheunders, P. A Comparison of Clustering Algorithms Applied to Color Image Quantization // Pattern Recognition Letters 1997 - Vol 18. - pp. 1379 - 1384.

37. Методы компьютерной обработки изображений / Под ред. В.А. Сойфера. -М.: Физматлит, 2001.

38. Unsupervised Robust Change Detection on Multispectral Imagery Using Spectral and Spatial Features / R. Wiemker, A. Speck //Proceedings of the Third International Airborne Remote Sensing Conference ,Copenhagen, Denmark, 1997. Vol 1. - pp. -640 - 647.

39. Evangelou, I.E. Data Mining and Knowledge Discovery in Complex Image Data using Artificial Neural Networks / I.E. Evangelou, D.G. Hadjimitsis, A.A. Lazakidou,

40. C. Clayton // Workshop on Complex Reasoning on Geographical Data, Cyprus.2001.-pp.688 699.

41. Remote Sensing and Image Interpretation / T. Lillesand, R. Kiefer // John Wiley & Sons Publishing. 1994. - pp. 804.

42. Richards, B. Remote Sensing Digital Image Analysis / B. Richards, A. John // An Introduction, Second Edition, Springer Verlag. 1993 . - pp. 255.

43. Книжников, Ю.Ф. Аэрокосмические методы географических исследований / Ю.Ф. Книжников, В.И. Кравцова, О.В. Тутубалина. М.: Академия, 2004. - 336 с.

44. Козлов, Д.Н. Инвентаризация ландшафтного покрова методами пространственного анализа для целей ландшафтного планирования /Д.Н. Козлов // Труды Международной школы-конференции "Ландшафтное планирование". М.: Географический факультет МГУ, 2006. - 280 с.

45. Cooper, G. R. Probabilistic Methods of Signal and System Analysis / G. R. Cooper, C. D. McGillem // Second Edition, Holt, Rinehart & Winston. 1986. - pp. 480.

46. Lee, S.U. A comparitive performance study of several global thresholding techniques for segmentation / S.U.Lee, S.Y.Chung, R.H.Park // Computer Vision, Graphics, and Image Processing. 1998. - No 52. - pp. 171 - 190.

47. Лурье, И.К. Теория и практика цифровой обработки изображений. Дистанционное зондирование и географические информационные системы / И.К.Лурье, А.Г.Косиков. Под ред. А.М.Берлянта. М.: Научный мир, 2003. -168 с.

48. Злобин, В.К.Колораметрический подход к сегментации облачных образований на многозональных снимках / В.К.Злобин, А.М.Кочергин // Тез. докл. Междунар. науч.-техн. конф. "Космонавтика, Радиоэлектроника, Геоинформатика".- Рязань, 2003. С. 314.

49. Кузнецов, А.Е. Формирование цветных снимков по спутниковым изображениям среднего и высокого пространственного разрешения / А.Е.Кузнецов, П.Н.Светелкин // Цифровая обработка сигналов. 2009. - №3. -С. 36 - 40.

50. Hwang, J. Nonparametric Multivariate Density Estimation / J. Hwang, S.Lay // IEEE Transactions on Signal Processing. 1994. - Vol. 42, № 10. - pp. 2795 - 2810.

51. Зубков, И.А. Применение алгоритмов неконтроллируемой класификации157при обработке данных ДЗЗ / И.А.Зубков, В.О.Скрипачев // Современные проблемы дистанционного зондирования Земли из космоса. М: Институт космических исследований РАН, 2007. - С. 57 - 62.

52. Scarpa, G. A hierarchical texture model for unsupervised segmentation of remotely sensed images / G. Scarpa, M.Haindl, J.Zerubia// Lecture Notes in Computer Science. 2007. - pp. 303 - 312.

53. Козодеров, B.B. Методы оценки состояния природно-техногенной сферы по данным аэрокосмического мониторинга: учеб. пособие. — М.: МФТИ, 2008.

54. Чабан, JI.H. Тематическая классификация многозональных (многослойных) изображений в пакете ERDAS Imagine. Методические указания для лабораторного практикума. — М.: МИИГАиК, 2006.

55. Papoulis, A. Probability, Random Variables, and Stochastic Processes / A. Papoulis // Second Edition, McGraw-Hill. 1984. - pp. 666.

56. Дистанционное зондирование: количественный подход / под ред. Ф. Свейна, Ш. Дэйвис. — М.: Недра, 1983.

57. Scott, D. W. Multivariate Density Estimation. / D. W. Scott // John Wiley & Son. 1992 .-pp. 208-212.

58. Crippen, R. E. Calculating the Vegetation Index Faster // Remote Sensing of Environment, 1990. vol 34. - pp. 71-73.

59. Huete, A. Spectral response of a plant canopy with different soil backgrounds / A.Huete, R.Jackson, D. Post // Remote Sensing of Environment. 1985. - vol. 17. -pp.37 - 53.

60. Jackson, R. Spectral indices in n-space / R. Jackson // Remote Sensing of Environment. 1983. - vol. 13. - pp. 409 - 421.

61. Richardson, A. J. Using spectra vegetation indices to estimate rangeland productivity / A. J. Richardson, J. H.Everitt, // Geocarto International. 1992. - vol. l.-pp. 63 - 69.

62. Horowitz, S. L. Picture segmentation by a tree traversal algorithm / S. L.

63. Horowitz, Т. Pavlidis // J. ACM. 1976. - Vol. 23, No. 2. - pp. 368 - 388.

64. Осипов, Г. С. Искусственный интеллект: состояние исследований и взгляд в будущее / Г. С. Осипов // Новости искусственного интеллекта. 2001. - № 1. Электронный ресурс. - Режим доступа: http://www.raai.org/about/persons/osipov/pages/ai/ai.html. .

65. Hoffman, D. D. Parts of recognition: Tech. Rep. AIM-732 / D. D. Hoffman, W. Richards. 1983. - pp. 96 - 99.

66. Introduction to Statistical Pattern Recognition / Fukunaga, K. San Diego, California: Academic Press Inc. - 1990. - pp. 618.

67. Сергиенко, А.Б. Цифровая обработка сигналов / А.Б. Сергиенко. СПб.: Питер, 2003 . - С. 608.

68. Родзин, С.И. Искусственный интеллект: Учебное пособие / С.И. Родзин.-Таганрог: Изд-во ТТИ ЮФУ, 2009. 200 с.

69. Терехина, А.Ю. Анализ данных, многомерное шкалирование / А.Ю.Терехина.-М.:Наука, 1986.-168 с.

70. Ахо, А. Построение и анализ вычислительных алгоритмов / А.Ахо, Д.Хопкрофт, Д. Ульман . -М. : Мир . 1979.- С. 535.

71. Дюк, B.Data Mining: Учеб. курс / В.Дюк, А. Самойленко . СПб: Питер, 2001.-368 е.

72. Ball, G. A Clustering Technique for Summarizing Multivariate Data / G. Ball, D. Hall//Behavioral Science. 1967. - Vol. 12, pp. 153 - 155.

73. Чубукова, И.A. Data Mining: Учеб. пособие /И.А. Чубукова M.: Интернет-Университет Информационных Технологий, 2006. - 328 с.

74. Программный комплекс ENVI. Учебное пособие / Совзонд М.: Совзонд. -2007.-265.

75. ERDAS Imagine 8.5. Field Guide. — Atlanta, USA. 2001. - pp. 319.

76. IMAGINE Spectral Analysis. User's Guide / Leica Geosystems GIS&Mapping, LLC, Atlanta, USA. 2003. - pp. 321.

77. Чабан, JI.H. Исследование возможностей классификации растительного покрова по гиперспектральным изображениям в пакетах тематической обработки данных дистанционного зондирования // Труды МФТИ. — 2009. —1. З.Том 1 — С. 171-180.

78. Chan, Р. К.Spectral к-way ratio-cut partitioning and clustering / P. K. Chan, M. D. F. Schlag, J. Y. Zien // IEEE Trans. Computer- Aided Design. 1994. - No 13(8). -pp.1088 - 1096.

79. Saghri, J. A Viable End-Member Selection Scheme for Spectral Unmixing of Multispectral Satellite Imagery Data / J. Saghri, A. Tescher, F. Jaradi //Journal of Imaging Science and Technology. 2000. - №44(3). - pp. 196 - 203.

80. Tso, B. Classification Methods for Remotely Sensed Data / B. Tso, P. M. Mather // Taylor & Francis Group. 2009. - pp. 317.

81. Hartigan, J. Clustering Algorithms / J. Hartigan // John Wiley & Sons, New York.- 1975.-pp. 254.

82. Гонсалес, P. Принципы распознавания образов / Д. Ту, Р. Гонсалес . М.: 1970.-540 с.

83. Вапник, В.Н. Теория распознавания образов / В.Н. Вапник,А.Я.Червоненкис .-М.: Наука, 1974.-415 с.

84. Баранов, A. Data Mining. Теория и практика / А. Баранов, И. Брянцев, И. Жевлаков. БДЦ-пресс. - 2006. - С. 208.

85. Jain, А.К. Algorithms for Clastering Data. — Englewood Cliffs (NJ): Prentice-Hall. 1988. - pp.320.

86. Андреев, Г.Г. Методика автоматизированной тематической обработки многозональной космической информации при отсутствии или недостатке наземных данных/ Г.Г. Андреев, Л.Н.Чабан // Исследования Земли из космоса.1999. — № 2. — С. 40 52.

87. Zhang, Y. J. Evaluation and comparison of different segmentation algorithms /Y. J. Zhang //Pattern Recognition Letters. 1997. - No 18- pp. 963 - 974.

88. Кормен, Т. Алгоритмы: построение и анализ / Т.Кормен, Ч.Лейзерсон, Р.Ривест. —М.:МЦНМО, 1999,- С. 960.

89. Горелик, А.Л.Методы распознавания. Учеб. пособие для вузов / А.Л.Горелик, В.А. Скрипкин М.: Высш. шк., 2004. - 261 с.

90. Барсегян, А. А. Методы и модели анализа данных: OLAP и Data Mining: учеб.пособие / А. А. Барсегян и др.. СПб. : БХВ- Петербург. - 2004. - 336 с.

91. Wann, C.D. A Comparative study of self-organizing clustering algorithms / C.D.Wann//Neural Networks. -1997. No 10. - pp. 737 - 743.

92. Zhang, T. BIRCH: A new data clustering algorithm and its applications / T. Zhang, R.Ramakrishnan, M.Linvy // Journal of Data Mining and Knowledge Discovery. 1997.-No 1.-pp.141 - 182.

93. Engelbrecht, A. P. Fundamentals of Computational Swarm Intelligence / A. P. Engelbrecht // John Wiley & Sons, Chichester, UK. 2005. - pp. 672.

94. Study of Different Approach to Clustering Data by Using the Particle Swarm Optimization Algorithm / A. Esmin, D. Pereira , F. Araujo, IEEE Congress on Evolutionary Computation. 2008. - pp. 1817 - 1822 .

95. Van den Bergh, F. An Analysis of Particle Swarm Optimizers / PhD Thesis, University of Pretoria, South Africa. 2002. - pp. 208.

96. Poli, R. Analysis of the publications on the applications of particle swarm optimisation /R. Poli// Journal of Artificial Evolution and Applications. 2008. - pp. 39-49.

97. Красовский A.A., Колесников A.A., Веселов Г.Е. Синергетика и проблемы теории управления / под ред. Колесникова А.А. М.: Физматлит, 2004. - 504 е.

98. Клир Дж. Системология. Автоматизация решения системных задач: Пер. с англ. -М.: 1990. 534 е.

99. Растригин ДА. Современные принципы управления сложными объектами.- М.: Советское радио, 1980. -230 С.

100. Балашов Е.П. Эволюционный синтез систем. М.: Радио и связь, 1985. -328 е.

101. Двоенко, С. Д. Неиерархический дивизимный алгоритм кластеризации / С.Д.Двоенко // Автоматика и телемеханика. 1999. № 4. - С. 117-124.

102. Двоенко, С. Д. Восстановление пропусков в данных методом неиерархических разбиений / С.Д.Двоенко // Автоматика и телемеханика. 2001.- № 3. С. 134-140.

103. Двоенко, С. Д.Задача распознавания образов в массивах взаимосвязанных объектов. Алгоритм распознавания / С.Д. Двоенко, А.В.Копылов, В.В.Моттль // Автоматика и телемеханика. 2005. № 12. - С. 162-176.

104. Kennedy, J. Particle Swarm Optimization /J. Kennedy, R.C. Eberhart //161

105. Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia. 1995,-Vol. 4. -pp 1942 - 1948.

106. Clerc, M. Particle Swarm Optimization /-ISTE, London, UK. 2006. - pp.58 -73.

107. Kennedy, J. Swarm Intelligence /J. Kennedy, R.Eberhart, Y. Shi //Academic Press, Inc.p. 2001. - pp. 253.

108. Shi, Y. A Modified Particle Swarm Optimizer / Y.Shi , R.C. Eberhart // Proceedings of IEEE International Conference on Evolutionary Computation, World Congress on Computational Intelligence, Anchorage, Alaska. 1998 . - pp. 69-73.

109. Kennedy, J. Small Worlds and Mega-Minds: Effects of Neighborhood Topology on Particle Swarm Performance // Proceedings of the Congress on Evolutionary Computation. 1999. - pp 1931 - 1938.

110. Shi, Y. Parameter Selection in Particle Swarm Optimization / Y. Shi, R.C. Eberhart // Evolutionary Programming, Vol VII, Proceedings of Evolutionary Programming . 1998. - pp. 591 - 600.

111. МакКоннелл, Д. Основы современных алгоритмов /Д. МакКоннелл. М.: Техносфера, 2004. - 368 с.

112. Дубровский, С.А. Прикладной многомерный статистический анализ /С.А. Дубровский М.: Финансы и статистика, 1982. - 216 с.

113. Матрица ошибок и расчет показателей точности тематических карт Электронный ресурс. // Gis-Lab: Геоинформационные системы и Дистанционное зондирование Земли [сайт]. URL: http://gis-lab.info/qa/error-matrix.html (дата обращения 13.01.2010).

114. Glossary of remote sensing terms Электронный ресурс. // The Canada Centre for Remote Sensing [сайт]. URL: http://www.ccrs.nrcan.gc.ca/glossary/indexe.php?id=3124 (дата обращения 13.01.2010).