Разработка методов и алгоритмов кластеризации мультиспектральных данных дистанционного зондирования земли тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Вершовский, Евгений Алексеевич

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

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

ВВЕДЕНИЕ.

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). Сферы возможного применения программного обеспечения «ЯЗМОСЬб» включают повышение качества разработок творческих и научных коллективов в отрасли обработки мультиспектральной информации и дешифрирования аэрокосмической съемки. Новые знания, полученные в диссертационной работе, способствуют повышению квалификации кадров и вошли в учебную программу обучения студентов.

ЗАКЛЮЧЕНИЕ

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

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

Список литературы диссертационного исследования кандидат технических наук Вершовский, Евгений Алексеевич, 2010 год

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).