Содержание к диссертации
Введение
1. Анализ методов сегментации и идентификации объектов земной поверхности по данным гиперспектральной съемки 11
1.1. Анализ отечественных и зарубежных систем гиперспектральной съемки Земли 11
1.2. Анализ методов сегментации гиперспектральных изображений 18
1.3. Анализ методов идентификации объектов по данным гиперспектральной съемки 25
1.4. Основные направления исследований по созданию алгоритмов идентификации объектов с использованием методов искусственного интеллекта 29
Основные результаты 30
2. Сегментация гиперспектральных изображений на основе алгоритмов нечеткой кластеризации, генетических алгоритмов и нейронных сетей 32
2.1. Алгоритмы кластеризации гиперспектральных изображений в условиях неопределенности 33
2.2. Генетические алгоритмы оптимизации результатов кластеризации 47
2.3. Алгоритмы уточнения результатов кластеризации с применением искусственных нейронных сетей 70
Основные результаты 75
3. Сегментация гиперспектральных изображений с применением ансамбля алгоритмов кластеризации 78
3.1. Подходы к формированию кластерного ансамбля с использованием векторов меток кластеров 79
3.2. Ансамбль алгоритмов кластеризации, основанных на применении генетического алгоритма для максимизации количества взаимной информации 85
3.3. Ансамбль алгоритмов кластеризации, основанный на консолидированной матрице подобия векторов меток кластеров 99
3.4. Экспериментальные результаты 124
Основные результаты 126
4. Реализация и экспериментальные исследования системы сегментации объектов по данным гиперспектральной съемки 130
4.1. Информационные технологии формирования базы данных эталонных объектов 133
4.2. Комплексирование разнородных баз данных эталонных спектральных характеристик объектов 136
4.3. Формирование оперативной БД объектов, нормирование спектральных характеристик получаемых из разных БД 137
4.4. Архитектура системы идентификации объектов 138
4.5. Процедуры повышения оперативности доступа к БД объектов гиперспектральных изображений 144
Основные результаты 145
Заключение 146
Список литературы
- Анализ методов идентификации объектов по данным гиперспектральной съемки
- Генетические алгоритмы оптимизации результатов кластеризации
- Ансамбль алгоритмов кластеризации, основанных на применении генетического алгоритма для максимизации количества взаимной информации
- Формирование оперативной БД объектов, нормирование спектральных характеристик получаемых из разных БД
Введение к работе
Актуальность диссертации и степень разработанности темы.
Гиперспектральная съемка является приоритетным направлением развития систем дистанционного зондирования Земли (ДЗЗ). Она предполагает одновременное получение сотен и тысяч изображений одной и той же сцены, зафиксированных в очень узких соприкасающихся диапазонах спектра. В результате формируется многомерное гиперспектральное изображение (ГСИ), называемое гиперкубом. Каждой точке земной поверхности гиперкуб ставит в соответствие спектральную характеристику (СХ), которая описывает распределение энергии излучения по длине волны. Знание СХ для множества точек вполне определенных объектов позволяет автоматизировать процесс сегментации объектов и установить их физико-химические свойства. Поэтому материалы гиперспектральной съемки находят широкое применение во многих сферах человеческой деятельности: экологии, сельском и лесном хозяйствах, анализе атмосферы, поиске полезных ископаемых, военной сфере и др.
Гиперспектральная съемка начала внедряться в практику ДЗЗ совсем недавно. За рубежом работы в этом направлении начаты 12 лет назад и активно развиваются. Создан ряд образцов гиперспектральной аппаратуры (ГСА) космического и авиационного базирования, лучшими из которых являются: Hyperion (TRW Inc., США, 2000 г.); CHRIS (Sira Technology Ltd, Великобритания; Verhaert Design and Development, Бельгия, 2001 г.); HICO (The Aerospace Corporation, Johnson Space Center, США, 2009 г.); HSI (Kayser-Threde GmbH, German Research Centre for Geosciences, Германия, планируется к использованию в 2015 г.). Каждая из указанных фирм-разработчиков ГСА включает десятки специализированных научно-производственных организаций.
В нашей стране впервые ГСА выведена на орбиту на спутнике МКА-ФКИ (головной разработчик - НПО им. С.А. Лавочкина) в июле 2012 года. В соответствии с Федеральной космической программой России на 2006-2015 годы в ближайшее время планируется запуск серии спутников, оснащенных ГСА: с 2013 г. - в составе космической системы «Ресурс-П» №1, №2, №3 (головной разработчик - Ракетно-космический центр «ЦСКБ-Прогресс»); с 2015 г. - в составе космической системы «Обзор-О» (головной разработчик - Космический научно-производственный центр им. М.В.Хруничева).
Широко известны в России научно-инженерные школы по созданию ГСА и средств обработки получаемой от нее информации: это предприятия ракетно- космической промышленности - Красногорский завод им. С.А. Зверева, Ракетно-космический центр «ЦСКБ-Прогресс», ЦНИИмаш, НПО им. С.А. Лавочкина, Корпорация «ВНИИЭМ», Центр Келдыша, НПО «Лептон», НПП «ЭЛАР», Госцентр «Природа», НИЦ «Планета»; это вузы и институты РАН - ВКА им. А.Ф.Можайского, МФТИ, МГТУ им. Н.Э.Баумана, РГРТУ, НТЦ уникального приборостроения, ВНИИ физико-технических измерений, Институт физики атмосферы, МГУ им. М.В. Ломоносова и др.
В то же время ГСИ - это принципиально новый вид информации о земной поверхности, развитие средств ее получения и обработки находятся в самой начальной стадии. Особую актуальность приобретают вопросы создания методов и средств обработки этой специфичной информации. Основной задачей, для решения которой собственно и создается ГСА, является повышение уровня автоматизации процессов сегментации и последующей классификации объектов наблюдаемой сцены.
Анализ характерных свойств гиперспектральных изображений показывает наличие сильной корреляции между отдельными элементами гиперкуба как в пространственной, так и в спектральной области. Другой характерной особенностью ГСИ является значительное влияние на спектральные характеристики ряда искажающих факторов: условий съемки и освещенности земной поверхности, состояния атмосферы, сезонности наблюдений, погодных условий и др. Все это вносит некоторую неопределенность в отображение объектов, регистрируемых в различных спектральных диапазонах, и, кроме того, приводит к размытию границ переходов от одного объекта к другому. В связи с этим автор считает, что наиболее перспективным направлением по сегментации объектов на ГСИ является совместное применение алгоритмов кластеризации в условиях неопределенности (в частности, FCM-, PCM- и PFCM-алгоритмов), обеспечивающих разбиение на кластеры с учетом свойств кластерной относительности и/или кластерной типичности. Настоящая диссертационная работа посвящена исследованию комплексной применимости данных алгоритмов при решении задачи сегментации ГСИ.
Цель диссертации заключается в создании высокоэффективных алгоритмов сегментации объектов земной поверхности по данным гиперспектральной съемки с использованием методов искусственного интеллекта: алгоритмов кластеризации на основе нечетких множеств, искусственных нейронных сетей и генетических алгоритмов.
Для достижения поставленной цели решаются следующие основные задачи:
проводится анализ отечественного и зарубежного опыта создания математических и технических средств сегментации объектов на гиперспектральных изображениях;
разрабатываются алгоритмы сегментации гиперспектральных изображений с использованием методов искусственного интеллекта;
создаются алгоритмы субоптимальной сегментации объектов на гиперспектральных изображениях с использованием ансамбля алгоритмов нечеткой кластеризации;
проводятся экспериментальные исследования на натурной информации от различных систем гиперспектральной съемки разработанных алгоритмов сегментации, оценка их качественных характеристик и определение области использования.
Научная новизна работы заключается в том, что впервые предлагаются гибридные алгоритмы, основанные на методах искусственного интеллекта для комплексного решения задачи сегментации объектов на гиперспектральных снимках, а так же алгоритмы поиска в базе данных эталонных гиперспектральных объектов в условиях неопределенности.
Основные положения, выносимые на защиту:
алгоритмы повышения качества сегментации гиперспектральных изображений путем комплексного использования алгоритмов нечеткой кластеризации, генетических алгоритмов и искусственных нейронных сетей;
алгоритм субоптимальной сегментации гиперспектральных изображений, основанный на максимизации с помощью генетических алгоритмов совокупной информации, полученной с использованием различных подходов нечеткой кластеризации;
алгоритм повышения точности сегментации гиперспектральных изображений за счет обобщенного анализа результатов нечеткой кластеризации на основе формирования консолидированной матрицы подобия меток кластеров объектов;
алгоритм разбиения графа, соответствующего матрице подобия меток кластеров объектов, основанный на применении спектральной фильтрации и алгоритма нечетких с-средних;
результаты экспериментальной оценки показателей качества сегментации гиперспектральных изображений с применением разработанных алгоритмов нечеткой кластеризации и с привлечением информации от различной ГСА отечественного и зарубежного производства.
Практическая ценность работы состоит в том, что на базе предложенных в диссертации алгоритмов разработаны программные комплексы, используемые при обработке гиперспектральных изображений от космических систем «Ресурс-П» в Научном центре оперативного мониторинга Земли Корпорации «Российские космические системы» и в Институте систем обработки изображений РАН. Результаты работы также используются в учебном процессе в дисциплинах «Элементы теории нечетких множеств» и «Системы искусственного интеллекта».
Апробация работы. Основные положения диссертации докладывались и обсуждались на международной и всероссийских научно-технических конференциях. Всего сделано 15 докладов. На международной конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (Рязань, 2012). На всероссийских научно-технических конференциях: «Актуальные проблемы ракетно-космического приборостроения и информационных технологий» (Москва, 2012); «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, 2011, 2012); «Гиперспектральные приборы и технологии» (Красногорск, 2013); «Современные проблемы дистанционного зондирования Земли из космоса» (Москва, 2011, 2012); «Актуальные проблемы ракетно-космической техники» (Самара, 2011).
Публикации. По результатам диссертационных исследований опубликованы 29 работ: 12 статей (3 статьи в изданиях по списку ВАК), 15 тезисов докладов на международной и всероссийских конференциях, 2 свидетельства на регистрацию программ.
Внедрение результатов работы. Диссертационная работа выполнена в Рязанском государственном радиотехническом университете в рамках ОКР 9-09, ОКР 10-10, ОКР 3-11, НИР 15-12Г. Результаты работы в виде алгоритмов и программного обеспечения внедрены в Институте систем обработки изображений РАН, в Научном центре оперативного мониторинга Земли Корпорации «Российские космические системы», в учебном процессе РГРТУ, что подтверждается актами.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Основной текст работы содержит 147 стр., 22 рисунка и 17 таблиц. Список литературы содержит 15 стр. и включает 161 наименование. В приложении приведены акты о внедрении результатов диссертации.
Анализ методов идентификации объектов по данным гиперспектральной съемки
Основным принципом построения гиперспектральной аппаратуры является принцип «push broom» - это сканирование подстилающей поверхности оптико-электронным преобразователем (ОЭП) в виде матрицы приборов с зарядовой связью (ПЗС-матрицы). Лучистая энергия, пройдя через узкую щель объектива, попадает на дисперсионное устройство, которое расщепляет в пространстве излучение по мере изменения длины волны. Расщепленное излучение попадает на ПЗС-матрицу. Каждая ПЗС-линейка матрицы преобразует лучистую энергию из вполне определенного узкого спектрального диапазона. Таким образом отдельная линия на земной поверхности преобразуется в набор строк (по числу спектральных каналов, ПЗС-линеек), каждая из которых характеризует распределение интенсивности излучения во вполне определенном спектральном диапазоне. В результате движения спутника на вход аппаратуры поступает излучение от новой линии на поверхности Земли и в конечном счете формируется гиперкуб - набор изображений зафиксированных в различных спектральных диапазонах. Основным функциональным узлом, отличающим гиперспектральную аппаратуру от других типов съемочных систем, является дисперсионное устройство. В настоящее время применяется два вида таких устройств: спектроделительная призма и дифракционная решетка.
Для расширения рабочего спектрального диапазона в гиперспектральной аппаратуре часто используются несколько ОЭП, каждый из которых обслуживает вполне определенный спектральный диапазон. Обычно разделяют датчики, фиксирующие видимое и ближнее инфракрасное (400 - 1000 нм) и инфракрасное излучение (1000 - 2500 нм). Пример построения гиперспектральной съемочной аппаратуры (ГСА), которая входит в состав КА «Ресурс-П», представлена на рис. 1.1 [4]. ГСА состоит из общего изображающего объектива и двух каналов. Каждый канал включает собственный объектив, призму и зеркало.
Различные гиперспектральные съемочные устройства могут иметь существенно отличающиеся схемы расположения функциональных элементов. Однако общая структура гиперспектрометра обычно включает входной объектив, щель, коллимационный объектив, дисперсионное устройство, проекционный объектив и ПЗС матрицу.
В настоящее время ведутся активные разработки гиперспектральной аппаратуры как космического, так и авиационного базирования.
Впервые гиперспектральная аппаратура космического базирования Hyperion со спектроделительной призмой была использована на американском спутнике ЕО-1 (Earth Observing - 1) [29, 33]. КА был выведен на орбиту 21.11.2000 г. Параметры ГСА Hyperion приведены в таблице 1.1. Таблица 1.1. Основные характеристики ГСА Hyperion КА ЕО- Наименование характеристики Значение характеристики [33, 106], разрабатываемый в настоящее время Германией. Он будет имеет полосу обзора 30 км, что в четыре раза превосходит аналогичную характеристику Hyperion КА ЕО-1. Основной задачей ГСА КА ЕпМАР является определение в глобальном масштабе биофизических, биохимических и геохимических параметров экосистем, получение оперативных и высококачественных данных для создания и уточнения моделей, необходимых для понимания процессов в биосфере и геосфере Земли. Запуск КА запланирован на 2015 г. Характеристики гиперспектральной аппаратуры «HSI» КА ЕпМАР представлены в таблице 1.2.
Первая гиперспектральная аппаратура с дифракционной решеткой НІСО (The Hyperspectral Imager for the Coastal Ocean) была установлена на Международную космическую станцию (МКС). 10 сентября 2009 г. гиперспектрометр НІСО был доставлен на МКС с помощью транспортного корабля Н-2 [98, 137]. Основной задачей аппаратуры НІСО является исследование прибрежных районов океана: прозрачности воды, типов и рельефа дна, береговой растительности. Можно привести еще целый ряд космических аппара тов, созданных различными зарубежными странами, для гиперспектральной съемке Земли.
За рубежом также разработан ряд удачных образцов ГСА авиационного базирования [84, 85, 91, 97, 155, 156].
1.1.3. В России в последние годы ведутся активные разработки гиперспектральных съемочных систем как космического, так и авиационного базирования. К наиболее передовым образцам авиационных датчиков относятся «Сокол-ГЦП», «Фрегат» и ГСА производства НПО «Лептон». Впервые в России на космическую платформу гиперспектрометр установлен в составе МКА ФКИ (малый космический аппарат для фундаментальных космических исследований) и К А «Ресурс-П».
Видеоспектрометр «Сокол-ГЦП» [5] разработан ОАО «Красногорский завод им. С.А.Зверева» в рамках ФЦП «Комплексные меры противодействия злоупотребления наркотикам и их незаконному обороту» в составе авиаци-онно-технического комплекса ФГУП «Госцентр «Природа». Параметры ГСА «Сокол-ГЦП» представлены в таблице 1.3.
Как уже отмечалось, сегментация объектов на гиперспектральном изображении (ГСИ) является одной из основных задач, ради решения которых и создаются ГСА. Эта задача состоит в том, чтобы на основе анализа спектральных и пространственных характеристик наблюдаемых объектов создать технологии их выделения, которые бы отличались высокими качеством и степенью автоматизации этого трудоемкого процесса.
Анализ отечественной и зарубежной литературы [83] дает основания сделать вывод, что все подходы к сегментации гиперспектральных изображений можно систематизировать в виде 3 групп: - подходы, использующие пространственную информацию, то есть группирующие соседние пиксели на основе некоторой меры сходства пространственных характеристик; - решения, использующие спектральную информацию, объединяющие пиксели без учета их пространственного расположения, а лишь на основе их спектральной характеристики; - комбинированные подходы, учитывающие как пространственные, так и спектральные характеристики пикселей изображения при выделении объектов. Алгоритмы первых двух групп, разработанные применительно к данным панхроматической и спектрозанальной съемок, при обработке гиперспектральной информации, как и следует ожидать, дают результаты хуже, чем комбинированные, так как не используют весь объем информации, имеющейся в гиперспектральных изображениях. Поэтому ниже будем рассматривать только пространственно-спектральные подходы к сегментации объектов.
. Морфологическая сегментация. Этот подход основан на применении традиционного алгоритма водораздела, который часто используется для сегментации спектрозональных изображений, путем его дополнения мерами сходства в виде морфологических градиентов. Такая модификация алгоритма водораздела позволяет распространить его на случай обработки гиперспектральных данных, а так же снизить влияние шумов и повысить надежность сегментации [140].
Генетические алгоритмы оптимизации результатов кластеризации
Выполнен анализ отечественных и зарубежных систем гиперспектральной съемки Земли. Рассмотрены параметры, принципы построения и функционирования наиболее передовой гиперспектральной аппаратуры. Показано, что это принципиально новый тип аппаратуры, который требует разработки соответствующих методов, алгоритмов и программных средств обработки гиперспектральных данных.
Выполнен анализ методов сегментации объектов поверхности Земли по данным гиперспектральной съемки. Рассмотрены наиболее передовые отечественные и зарубежные подходы и методы по решению этой задачи. Установлено, что известные подходы хотя и учитывают пространственные и спектральных характеристики ГСИ, однако не позволяют достичь высокого качества и надежности процесса сегментации. Обоснована актуальность научных исследований по совершенствованию технологий сегментации на основе использования методов искусственного интеллекта.
Выполнен анализ методов идентификации объектов земной поверхности по данным гиперспектральной съемки. Показано, что разработанные методы, подходы и алгоритмы не позволяют сегодня достичь высокого качества решения задачи идентификации и высокого уровня ее автоматизации. Обоснована актуальность научных исследований по созданию новых методов идентификации.
По результатам выполненного анализа определена необходимость в проведении научных исследований по следующим трем направлениям:
Первое направление связано с исследованием различных подходов к сегментации ГСИ на основе алгоритмов кластеризации в условиях неопределенности, генетических алгоритмов и нейронных сетей. Оно предусматривает изучение вопросов нечеткой кластеризации ГСИ, исследование применимости генетических алгоритмов для решения этой задачи и алгоритмов уточнения результатов кластеризации на базе искусственных нейронных сетей.
Второе направление основано на идее сегментации объектов на ГСИ с использованием ансамбля алгоритмов кластеризации, обеспечивающего повышение надежности решения задачи сегментации. Здесь основным для исследования вопросом является анализ подходов к формированию кластерного ансамбля с использованием меток кластеров. Другим важным вопросом является изучение подходов к формированию кластерного ансамбля, основанных на применении генетических алгоритмов с целью максимизации количества взаимной информации и на использовании консолидированной матрицы подобия векторов меток кластеров.
Третьим важным направлением является реализация и экспериментальное исследование программных средств сегментации объектов на ГСИ с привлечением материалов гиперспектральной съемки от различных зарубежных и отечественных систем наблюдения Земли. Основными вопросами здесь являются проектирование информационных технологий сегментации, формирование баз данных эталонных объектов и экспериментальные исследования качества функционирования предложенных алгоритмов
Как уже отмечалось, гиперспектральное изображение - это гиперкуб данных, который включает в себя пространственную 20-информацию об объекте, дополненную спектральной информацией по каждой пространственной координате. Таким образом, каждой точке гиперспектрального изображения соответствует спектр, полученный в одноименной точке объекта земной поверхности.
Одной из основных задач, возникающих при обработке гиперспектральных изображений, является распознавание принадлежности тому или иному известному классу выявленных зон объектов местности.
Обычно для решения подобных задач используются технологии, основанные на применении алгоритма AdaBoost (сокращение от Adaptive Boosting), метода опорных векторов (SVM - Surport Vector Machine), инструментария искусственных нейронных сетей, аппарата линейного дискрими-нантного анализа (Linear Discriminat Analysis) [13, 51-53, 69, 82, 125].
Существующие технологии распознавания неопределенных зон гиперспектрального изображения являются недостаточно эффективными, в связи с чем возникает необходимость в разработке новых технологий решения этой задачи.
Поскольку формулировка задачи распознавания неопределенных зон гиперспектрального изображения предполагает проведение анализа данных в условиях неопределенности, то для ее решения целесообразным является использование так называемых алгоритмов кластеризации в условиях неопределенности [17, 55-59, 62, 131]. Применение таких алгоритмов позволит явно разделить спектры различных поверхностей местности, соответствующие различным объектам природного и искусственного происхождения. При этом для уточнения принадлежности точек изображения тому или иному классу предлагается разработать и исследовать ансамбль классификаторов, основанный на алгоритмах кластеризации в условиях неопределенности, генетических алгоритмах и нейронных сетях [20, 40, 58].
Наиболее известным алгоритмом кластеризации, основанном на учете того или иного вида неопределенности, являются алгоритм нечетких с-средних (fuzzy с -means - FCM-алгоритм) [87, 104, 110, 113, 147]. Он основан на учете свойства кластерной относительности. Известны его модификации: алгоритм возможностных с -средних (possibilistic с -means - РСМ-алгоритм) [135], который обеспечивает учет свойства кластерной типичности; алгоритм возможностных нечетких с-средних (possibilistic fuzzy с-means -PFCM-алгоритм) [96], который реализует одновременный учет свойств кластерной относительности и кластерной типичности [17].
Под задачей кластеризации ГСИ в условиях неопределенности будем понимать нахождение нечеткого разбиения исходного множества объектов, образующих в анализируемых ГСИ некоторую структуру нечетких кластеров. Задача нечеткой кластеризации сводится к нахождению степеней принадлежности объектов искомым нечетким кластерам, определяющим нечеткое разбиение исходного множества объектов [16, 17, 32, 55]. Она может быть решена с применением FCM-алгоритма, в основе которого лежит метод неопределенных множителей Лагранжа [73, 74, 87, 114].
Ансамбль алгоритмов кластеризации, основанных на применении генетического алгоритма для максимизации количества взаимной информации
При этом для каждой новой хромосомы, признанной «жизнеспособной», должен выполняться расчет значений «ширины зоны» т]; ( j = 1, с ) кластеров в соответствии с формулами (2.15) или (2.16). В целом генетический алгоритм с хромосомой переменной для оптимизации результатов кластеризации на основе FCM-алгоритма реализуется аналогично генетическому алгоритму с хромосомой переменной для оптимизации результатов кластеризации на основе FCM-алгоритма.
Алгоритм кластеризации, реализующий совместное использование РСМ-алгоритма и генетического алгоритма, обеспечивает поиск оптимального разбиения на кластеры и может быть описан следующей последовательностью шагов [58].
Шаг 1. Для формирования начальной популяции хромосом размером G выполняется один шаг FCM-алгоритма. Для каждой хромосомы в соответствии с формулами (2.15) или (2.16) вычисляются значения «ширины зоны» rjj
(j = \,c) кластеров и реализуется один шаг РСМ-алгоритма с вычислением значений функций типичности (возможностных степеней принадлежности) объектов центрам кластеров в соответствии с формулой (2.12), координат центров кластеров в соответствии с формулой (2.14) и значений функции соответствия для популяции хромосом размером G в соответствии с формулой (2.11) (или (2.18)).
Шаг 2. При выполнении условия продолжения генетического алгоритма осуществляется один шаг генетического алгоритма с реализацией операций скрещивания и мутации и вычислением значений функции соответствия в соответствии с формулой (2.11) (или (2.18)) для хромосом популяции размером 2 Rc G, состоящей из хромосом-потомков.
Шаг 3. Для популяции хромосом размером (G + 2 Rc G) выполняется один шаг РСМ-алгоритма с вычислением значений функций типичности (возможностных степеней принадлежности) объектов центрам кластеров в соответствии с формулой (2.12), координат центров кластеров в соответствии с формулой (2.14). Затем осуществляется уточняющий пересчет значений функций типичности (возможностных степеней принадлежности) объектов центрам кластеров в соответствии с формулой (2.12) и вычисление значений функции соответствия (2.11) (или (2.18)).
Шаг 4. Из расширенной популяции размером (2-G + 2-Rc -G), полученной путем объединения популяции размером G предыдущего поколения и популяции размером (G + 2 Rc G) текущего поколения, удаляются «нежизнеспособные» (G + 2 Rc G) хромосом с худшими (максимальными) значениями функции соответствия (2.11) (или (2.18)). Если выполняется условие продолжения генетического алгоритма, осуществляется переход к шагу 2. Если выполняется условие завершения генетического алгоритма, то работа генетического алгоритма завершается и осуществляется переход к шагу 5.
Шаг 5. Выбирается лучшая хромосома, которая минимизирует функцию соответствия (2.11) (или (2.18)). В качестве искомых координат центров кластеров берутся координаты центров кластеров, соответствующие лучшей хромосоме. В качестве искомых возможностных степеней принадлежности объектов центрам кластеров полагаются возможностные степени принадлежности объектов центрам кластеров, соответствующие лучшей хромосоме.
Так как при решении задачи поиска оптимальных результатов кластеризации на основе РСМ-алгоритма выполняется итерационное уточнение координат центров кластеров, значений возможностных степеней принадлежности объектов центрам кластеров, расчет значений «ширины зоны» г}у кластеров и вычисление значений функции соответствия, то наряду с популяцией хромосом, закодированных координатами центров, существуют популяции значений возможностных степеней принадлежности объектов центрам кластеров, значений «ширины зоны» r\} (j = l,c) кластеров и значений функции соответствия.
Как показывают экспериментальные исследования, совместное использование РСМ-алгоритма и генетического алгоритма позволяет получить адекватные субоптимальные результаты кластеризации объектов с приемлемыми временными затратами в случае, если множество объектов кластеризации содержит шумовые объекты.
Генетический алгоритм с хромосомой переменной для оптимизации результатов кластеризации на основе PFCM-алгоритма
При реализации генетического алгоритма с хромосомой переменной для оптимизации результатов кластеризации на основе PFCM-алгоритма в качестве функции соответствия целесообразно использовать целевую функцию (2.21) или функцию (2.23), а хромосома, закодированная координатами центров кластеров, может быть представлена в соответствии с (2.24). При этом, как и при реализации генетического алгоритма с хромосомой переменной для оптимизации результатов кластеризации на основе FCM-алгоритма, для каждой новой хромосомы, признанной «жизнеспособной», должен выполняться расчет значений «ширины зоны» т]} (у = 1,с) кластеров в соответствии с формулами (2.15) или (2.16). В целом генетический алгоритм с хромосомой переменной для оптимизации результатов кластеризации на основе PFCM-алгоритма реализуется аналогично генетическому алгоритму с хромосомой переменной для оптимизации результатов кластеризации на основе FCM-алгоритма.
Алгоритм кластеризации, реализующий совместное использование PFCM-алгоритма и генетического алгоритма, обеспечивает поиск оптимального разбиения на кластеры и может быть описан следующей последовательностью шагов [58].
Формирование оперативной БД объектов, нормирование спектральных характеристик получаемых из разных БД
Если считать, что оптимальный консолидированный вектор меток кластеров Я тот, при котором средняя нормализованная взаимная информация максимальна фАШ/\А,Л), то для нахождения искомого консолидированного вектора меток кластеров Я необходимо решить задачу максимизации целевой функции (3.5) [152, 153]. В этом случае консолидированный вектор меток кластеров Я будет содержать результирующие (консолидированные) номера меток кластеров объектов кластеризации.
При использовании целевой функции (3.5) каждый вектор меток кластеров рассматривается, как равноценный (равновесный) другим имеющимся векторам меток кластеров. Если по тем или иным причинам вектора меток кластеров имеют разную значимость (ценность), целевая функция (3.5) может быть обобщена на случай взвешенного среднего [153]: где wr - весовой коэффициент г -го вектора меток кластеров; г -1, R. Если некоторым объектам кластеризации в некоторых векторах меток кластеров не сопоставлены метки кластеров, то есть при наличии пропусков значений в векторах меток кластеров, целевая функция (3.5) может быть вычислена как взвешенное среднее взаимной информации для известных меток кластеров. При этом весовые коэффициенты wr (r = l,R) определяются пропорционально количеству известных меток кластеров в г-м векторе меток кластеров.
Алгоритм оценки весовых коэффициентов частных алгоритмов кластеризации
Как уже было отмечено в п. 3.2.1, возможны ситуации, когда некоторым объектам кластеризации не сопоставлены метки кластеров. В этом случае при построении ансамбля алгоритмов кластеризации используется целевая функция ANMI (3.6), реализующая оценку взвешенного среднего взаимной информации для известных меток кластеров, назначенных объектам кластеризации [153]. При применении частных алгоритмов кластеризации, описанных в главе 2, всем объектам кластеризации тем или иным образом сопоставляются значения функций принадлежности и/или типичности [20, 58]. При этом, в силу специфики данных частных алгоритмов кластеризации некоторые объекты могут быть классифицированы, как принадлежащие (типичные) двум или более кластерам с одинаковой степенью принадлежности (типичности). При выполнении кластеризации таким объектам принудительно назначается принадлежность (типичность) одному из кластеров (обычно - кластеру с меньшим номером из тех кластеров, принадлежность (типичность) которым одинакова) [17, 20].
На самом же деле в этом случае можно говорить о том, что частный алгоритм кластеризации затрудняется однозначным образом определить бо льшую принадлежность (типичность) объекта одному из кластеров, то есть реально метка кластера данному объекту не сопоставлена.
В связи с этим предлагается для каждого непосредственно используемого частного алгоритма кластеризации определять количество однозначно классифицируемых объектов (в соответствии со значениями функций принадлежности (типичности)) и использовать количества однозначно классифицируемых каждым частным алгоритмом кластеризации объектов для вычисления весовых коэффициентов частных алгоритмов применительно к конкретному гиперспектральному изображению [20]. При этом при вычислении целевой функции могут использоваться исходные вектора меток кластеров или их модификации (с учетом того, что реально некоторым объектам метки кластеров не сопоставлены).
Вопрос оценки значений весовых коэффициентов при использовании результатов сегментации гиперспектральных изображений, уточненных с использованием алгоритмов уточнения с применением искусственных нейронных сетей, требует проведения дополнительных исследований, так как, с одной стороны, метки кластеров для всех объектов определены уже однозначно, а, с другой стороны, наличие объектов, одновременно относящихся к двум или более кластерам с одинаковой степенью принадлежности (типичности) в результатах кластеризации с применением частных алгоритмов кластеризации, даже если принадлежность этих объектов кластерам позднее определяется с использованием алгоритмов уточнения результатов кластеризации с применением искусственных нейронных сетей, свидетельствует о наличии в реализациях частных алгоритмов кластеризации смещений координат центров кластеров от реальных значений [20, 58].
При выполнении данных исследований предполагалось, что алгоритмы уточнения результатов кластеризации с применением искусственных нейронных сетей однозначным образом назначают метки кластеров объектам, то есть объекты, для которых неизвестны метки кластеров, отсутствуют. Исходя из этих соображений выполнялась оценка весовых коэффициентов алгоритмов кластеризации, используемых при вычислении взвешенного среднего взаимной информации ANMI по формуле (3.6).
Алгоритм оценки весовых коэффициентов алгоритмов кластеризации может быть представлен следующей последовательностью шагов [20].
Шаг 1. Для каждого частного алгоритма кластеризации (FCM-, РСМ- и PFCM-алгоритма) оценивается количество однозначно классифицируемых объектов (в соответствии со значениями функций принадлежности (типичности)) nr (r = l,R, где R - количество частных алгоритмов кластеризации). Для каждого частного алгоритма уточнения результатов кластеризации, полученных с применением частного алгоритма кластеризации, количество однозначно классифицируемых объектов полагается общему количеству объектов кластеризации п.
