Содержание к диссертации
Введение
Глава 1. Аналитический обзор современных алгоритмов распознавания графических образов и технологий параллельного программирования 14
1.1. Классы графических образов 14
1.2. Методы предобработки данных 15
1.3. Методы сегментации изображений 16
1.4. Методы распознавания графических образов 16
1.5. Программные системы распознавания на основе нейронных сетей ...25
1.6. Особенности решения задач распознавания с использованием высокопроизводительных вычислительных средств 27
1.7. Технологии параллельного программирования 30
1.8. Архитектура программной системы «ПС ИНС» 32
Глава 2. Разработка алгоритмического обеспечения как технологии автоматического выделения объектов на снимках космического назначения 37
2.1. Разработка метода адаптивного преобразования цветного изображения 37
2.1.1. Анализ способов преобразования цветного изображения 37
2.1.2. Применение метода главных компонент (МГК) 38
2.1.3. Исследование результатов применения адаптивного метода 41
2.2. Разработка метода выделения объектов с помощью гистограмм 43
2.2.1. Разработка метода удаления фона 45
2.2.2. Сравнение методов удаления фона 47
2.2.3. Выделение локальных объектов 48
2.2.4. Устранение полостей в объектах 49
2.2.5. Отсеивание объектов 51
2.2.6. «Сборка» объектов 52
2.2.7. Формирование списка кандидатов 53
2.3. Разработка метода сегментации объектов на изображении на основе выделения границ 55
2.3.1. Сглаживание, выделение и бинаризация границ 56
2.3.2. Выделение сегментов, присоединение границ к сегментам и «сборка» сегментов 56
2.4. Специальная обработка распознаваемых объектов и эталонов 57
Глава 3. Разработка метода настройки и программная реализация ИНС Кохонена для кластеризации и распознавания графических образов на кластерных установках 60
3.1. Постановка задачи распознавания и кластеризации 60
3.2. Алгоритмы обучения ИНС Кохонена и распознавания объектов 62
3.3. Выбор оптимальной стратегии реализации ИНС Кохонена с метрикой Евклида на КВУ 65
3.4. Исследование ИНС Кохонена с метриками Махаланобиса и Евклида-Махаланобиса 71
3.4.1. Особенности метрик Махаланобиса и Евклида-Махаланобиса...71
3.4.2. Метод настройки ИНС Кохонена на метрики Махаланобиса и Евклида-Махаланобиса 72
3.4.3. Решение на КВУ задач кластеризации и распознавания на основе метрики Махаланобиса и Евклида-Махаланобиса 74
Глава 4. Программное обеспечение кластерной установки для распознавания графических образов 80
4.1. Требования к программному комплексу 80
4.2. Архитектура программного комплекса 80
4.3. Графический интерфейс для формирования задач распознавания образов 87
4.4. Построение схем обработки космических снимков средствами графического интерфейса 93
4.5. Основные характеристики и результаты тестирования программного обеспечения 96
Заключение 103
Список литературы 105
Приложение
- Программные системы распознавания на основе нейронных сетей
- Разработка метода выделения объектов с помощью гистограмм
- Выбор оптимальной стратегии реализации ИНС Кохонена с метрикой Евклида на КВУ
- Графический интерфейс для формирования задач распознавания образов
Введение к работе
В России проводится большая работа по проектированию суперкомпьютеров, средств распараллеливания вычислительных процессов и созданию прикладных программных систем на их основе. С созданием отечественных мультипроцессорных систем появилась возможность построения программных комплексов для решения различных сложных задач требующих больших временных ресурсов, таких как: расчеты обтеканий тел, моделирование процессов горения, расчет движения и столкновения многих объектов и т.д. Одна из актуальных задач алгоритмического обеспечения мультипроцессорных систем связана с обработкой потоков данных, доставляемых из космоса средствами технического зрения (СТЗ) с целью обнаружения заданных объектов (летательных аппаратов, регионов, сооружений и т.д.). Под потоком понимается последовательность снимков, преобразованных к цифровой форме. В силу высокой сложности решение задачи целесообразно разбить на ряд последовательных этапов (предварительная обработка снимка, выделение объектов, получение интегральных информативных параметров, кластеризация, распознавание, определение местоположения и ориентации), каждый из которых имеет самостоятельное значение, но может быть использован, при необходимости, как составная часть общего алгоритма. При этом существенную в вычислительном отношении долю составляют средства интеллектуальной обработки графической информации, которые целесообразно реализовать на мультипроцессорной системе. Большой вклад в развитие теории распознавания образов внесли российские ученые: Ю.И. Журавлев, Э.М. Браверман, Л.И. Розоноэр, М.А. Айзерман, В.А. Сойфер, В.Л. Матросов, В.Н. Вапник, А.Я. Червоненкис, А.Н. Горбань, М.Ю. Хачай, Н.Г Загоруйко и др. Известны различные методы распознавания образов: детерминистские, структурные, статистические. В последнее время большое распространение получили методы, основанные на математическом аппарате искусственных нейронных сетей (ИНС). Одно из направлений обработки изображений связано с ИНС, которые эффективно фильтруют данные (сеть Хопфилда), распознают графические образы (сеть Хемминга, многослойный персептрон), кластеризуют объекты (сеть Кохонена), а также выполняют другие немаловажные функции. Существенный вклад в развитие теории нейронных сетей и нейрокомпьютеров внесли А.Н. Горбань, А.И. Галушкин, Е.М. Миркес, В.Г.Редько, В.Г. Яхно и др.
Реализация программного обеспечения может осуществляться в виде пакетов прикладных программ, библиотек прикладных или системных программных средств. На данный момент существует множество программных пакетов, с помощью которых можно проектировать, настраивать и применять ИНС для решения различных задач, например, Neurooffice, Neuro Emulator, BrainMaker, Neural 10, Neural Planner, Mathlab и др. Специально для обработки данных ДЗЗ разработаны современные программные комплексы: ENVI (Environment for Visualizing Images), ER Mapper, ERDAS Imagine. Кроме этого имеются библиотеки для обработки и распознавания изображений, такие как OpenCV, LTI, VXL и др. Однако перечисленные нейропакеты и программные комплексы не рассчитаны на потоковую обработку снимков и на использование параллельных вычислителей. Решение же практических задач требует быстрого анализа последовательности изображений большого формата, доставляемых СТЗ. С появлением отечественных мультипроцессорных систем стала актуальной задача построения программных систем, ориентированных на параллельную обработку снимков с целью ускорения процессов выделения и распознавания требуемых объектов.
Как показывают проведенные экспериментальные исследования, и накопленный опыт, возможности ИНС при работе с реальными космическими снимками весьма ограничены и раскрываются только в сочетании с другими сопутствующими алгоритмами. Для успешного функционирования ИНС необходимо выполнить предварительные преобразования изображений, направленные на выделения информативных признаков. Среди таких преобразований можно отметить особые классы сегментации, выделения и нормализации локальных объектов. Для выделения объектов часто используют метод сканирующего окна, который предполагает знание размеров и ориентации объекта, что достаточно трудоемко для объектов имеющих случайное местоположение, различную размерность и масштаб. Таким образом, необходимы новые эффективные алгоритмы и программные средства обработки космических снимков, хорошо сочетающиеся с нейросетевыми методами распознавания и суперкомпьютерными технологиями параллельных вычислений.
Предлагаемое в рамках настоящей работы алгоритмическое и программное обеспечение основывается на разработке параллельных алгоритмов ИНС и предварительной обработки изображений, при этом учитываются возможности современных технологий параллельного программирования и аппаратных средств отечественного суперкомпьютера типа «СКИФ». Задача программного обеспечения заключается в предоставлении пользователю возможностей компоновки программных компонентов ИНС, средств обработки изображений и их интеграции для решения прикладных задач распознавания графических образов, как на ПЭВМ, так и на суперкомпьютере. Программный комплекс содержит удобные, понятные пользователю и одновременно с этим, мощные средства создания задач распознавания графических образов.
В настоящей диссертационной работе предлагаются новые подходы к улучшению качества работы ИНС, основанные на процедурах построения гистограмм, извлечения из них информативных параметров и нормализации объектов, способствующих решению задач кластеризации и распознавания с применением кластерных установок. Работа выполнена в рамках следующих проектов ИПС РАН:
• НИР "Перспективные алгоритмы и структуры вычислительных устройств для задач обработки изображений, распознавания образов и управления движением".
• проект РФФИ № 06-07-89083а «Разработка новых методов непрерывной идентификации и прогнозирования состояний динамических объектов на основе интеллектуального анализа данных».
• проект РФФИ № 07-07- 12029-офи «Создание интеллектуальной технологии для анализа данных и распознавания образов».
• программа Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоёмких компьютерных технологий на базе мультипроцессорных вычислительных систем», шифр «ТРИАДА», проект ПР5 «Разработка новых алгоритмов, принципов создания систем обработки изображений и другой информации от космических средств наблюдения, ориентированных на применение многопроцессорных вычислительных кластеров повышенной вычислительной мощности».
Программные системы распознавания на основе нейронных сетей
Известны программные реализации систем распознавания и обработки данных на основе нейронных сетей. Рассмотрим некоторые из них.
Программный пакет NeuroOfflce [9] ориентирован на проектирование нейронных сетей и включает в себя средства генерации, моделирования и обучения нейронных сетей. В пакет входят следующие модули: нейронная сеть, электронная таблица (для подготовки данных) и прогресс-индиктор (для визуального отображения процесса функционирования сети). Модуль нейронной сети может использоваться в большинстве современных программ, поддерживающих технологии СОМ - начиная от Microsoft Office и заканчивая средствами для разработки ПО (Visual C++, Delphi, C++ Builder, Visual Basic). NeuroShell 2 - это универсальный коммерческий пакет, предназначенный для нейросетевого анализа данных [45]. С его помощью можно решать широкий спектр задач, таких как прогнозирование курсов акций (облигаций, фьючерсов, валют, цен на нефть и т.д.), задачи геофизики и др. NeuralWorks Pro II/Plus является коммерческим пакетом программ, поддерживающим различные операционные системы, различные типы нейронных сетей и алгоритмы обучения, имеет средства графического отображения [33]. Коммерческий пакет программ NeuroSolution [33] содержит широкий набор типов нейросетей (многослойный персептрон, гибридные нейросети, нейросети анализа главных компонентов, Кохонена, LVQ и т.д.). Симулятор прост в освоении, имеет справочную систему и развитый графический интерфейс. Пакет программ MatLab + Neural Network Toolbox [74] содержит различные наборы нейронных сетей и средств для обработки изображений.
На сегодняшний момент существует несколько программ, позволяющих работать с картами Кохонена - это программы SoMine, Statistica, NeuroShell, NeuroScalp [55]. SoMine имеет большой арсенал встроенных средств анализа карт Кохонена. Недостатком является отсутствие опции показа карты в трехмерном виде. Пакет Statistica предназначен для статистического анализа, а самоорганизующиеся карты в нем представлены в виде отдельного модуля. Возможности распознавания графических образов довольно скудны. В NeuroShell есть карты Кохонена, но к сожалению они представлены в одномерном варианте и не имеют средств для визуального анализа. В пакет NeuroScalp входит модуль "Карты Кохонена". В программе реализован собственный язык программирования, позволяющий использовать индикаторы технического анализа. Реализован богатый инструментарий для проведения анализа карт Кохонена.
Современные системы обработки данных ДЗЗ — это сложные программные комплексы, обладающие широкими возможностями для проведения профессионального анализа входной информации. Такие системы характеризуются, прежде всего, набором базовых процедур, доступных пользователю. Система ENVI (Environment for Visualizing Images - среда для отображения снимков) является наиболее совершенным и в то же время очень простым в управлении программным обеспечением для работы с данными дистанционного зондирования [12]. ENVI используется в самых разных прикладных областях: мониторинг лесных и сельскохозяйственных угодий, анализ природных катаклизмов, охрана окружающей среды, планирование и развитие городской инфраструктуры, государственная безопасность. Пакет ER Mapper 6.4 [14] представляет программное решение для задач анализа и обработки изображений, создания карт и подготовки данных для геоинформационных систем. Общая идеология пакета ER Mapper - алгоритмическая структура работы с данными. Система обработки изображений ERDAS Imagine [13] в настоящее время является наиболее развитым коммерческим продуктом для обработки ДДЗ, доступным широкому кругу пользователей. Последняя версия - ERDAS Imagine 8.7 представляет собой следующий уровень развития продукта. ERDAS Imagine версии 8.7 содержит усовершенствованные инструменты обработки изображений, новые инструменты импорта и экспорта изображений, усовершенствованный инструмент монтажа изображений, а также новые возможности трёхмерной визуализации. Недостатками перечисленных готовых продуктов являются: 1) отсутствие гибкости при формировании задач пользователя; 2) закрытые исходные коды; 3) отсутствие параллельных программных модулей и возможности работы на мультипроцессорных системах.
Разработка метода выделения объектов с помощью гистограмм
Выделение объекта на панорамных снимках заключается в формировании описания независимого фрагмента изображения, отвечающего определенным требованиям, таким как размер, соотношение площадей, местоположение и др. Выделенные объекты далее подаются на другие подсистемы, отвечающие за распознавание. Решение задачи выделения локальных объектов осуществляется в настоящей работе на основе построения и анализа гистограммы изображения. Схема формирования задачи выделения объектов средствами специального языка графического интерфейса программного комплекса, показана на рис.2.2, и содержит следующие модули: - интенсивность пикселя в точке с координатами (х, у), 1С - величина интенсивности в пике гистограммы, вычисляемая по формуле 1С = arg(max«(/)), 1=0,..., 255, 7/ и 1Г - протяженность области фона соответственно слева и справа от пика (рис. 2.3). Таким образом, с помощью данного метода можно удалить пиксели, яркости которых занимают большую часть площади на изображении.
Протяженность удаляемой области справа и слева от пика можно выбирать в зависимости от крутизны гистограммы справа и слева соответственно. Удаление циклическим методом В этом методе на каждой итерации преобразования удаляются все пиксели (х, у) с интенсивностью 1(х, у), удовлетворяющие равенству 1(х, у) = 1С. Таким образом, от итерации к итерации удаляются пиксели изображения, яркость которых равна текущему значению яркости в пике гистограммы (рис. 2.4). Здесь для удаления фоновых областей используются гистограммы эталонов. Все полученные гистограммы эталонов свертываются в одну общую гистограмму путем суммирования и усреднения. На этой гистограмме находится значение максимального пика, которое умножается на нормирующий коэффициент (лежит в диапазоне [0..1]) с целью получения значения нижней границы яркости. Из таблицы видно, что исследуемые методы показывают разные результаты. Метод удаления интервалом выдает лучший результат при наличии одного глобального пика на гистограмме, в то время как метод удаления циклически выдает лучший результат при наличии нескольких существенных пиков. Удаление фона с помощью эталонов дает равномерный результат независимо от типа гистограммы. С помощью алгоритма быстрой маркировки [65] производится выделение отдельных, не связанных друг с другом объектов. Алгоритм является линейным и выполняется за два прохода: 1) В первом проходе, выполняемом попиксельно сверху вниз и слева направо, производится маркировка связных объектов, а также устанавливается их связность между собой. 2) Во втором проходе, выполняемом в том же порядке, связные объекты маркируются в несвязные объекты. Следует отметить, что такой алгоритм поиска связных компонент является универсальным, и при использовании различных критериев связности может быть использован в целом ряде других алгоритмов. В данном же случае таким критерием служат четырехсвязная и восьмисвязная области пикселей. Применяя данный алгоритм вслед за алгоритмом удаления фона можно промаркировать объекты, оставшиеся на изображении. В результате работы данного алгоритма номера всех промаркированных объектов идут не по порядку, что приводит к увеличению времени обработки данных.
В модифицированном алгоритме во время второго прохода производится правильная перенумерация. Пример результатов работы исходного алгоритма [65] и модифицированного показан на рис.2.5. Входное изображение приведено в упрощенном бинарном виде, где 0 - пиксели фона. Модифицированный алгоритм позволяет не только промаркировать объекты на изображении, но и существенно снизить затраты памяти в последующих операциях предобработки.
Выбор оптимальной стратегии реализации ИНС Кохонена с метрикой Евклида на КВУ
Построение прикладной программной системы обработки космических снимков является одной из важнейших задач обработки и распознавания космических изображений, доставляемых средствами технического зрения. Такая система должна отвечать следующим требованиям: 1) Потоковая и параллельная обработка данных. 2) Обработка снимков различного типа и качества. 3) Наличие дружественного пользовательского интерфейса. Под потоковой обработкой данных понимается возможность системы обрабатывать большие объемы снимков космического назначения.
Кроме потоковой обработки необходима параллельная обработка снимков. Основной особенностью архитектуры системы явилось обеспечение гибкости и расширяемости. На рис.4.1. показана общая архитектура программного комплекса, которая в целом наследует архитектуру программной системы «ПС ИНС» (рис. 1.7, рис 1.8), разработанной силами сотрудников лаборатории интеллектуального управления Института программных систем РАН, в рамках проекта ПР5 Программы Союзного государства «Триада» [52,61]. Основу программного комплекса составляют универсальная моделирующая среда (УМС), графический интерфейс, модули параллельных реализаций ИНС, фильтров и других алгоритмов. УМС обеспечивает связь модулей в процессе выполнения задачи. С помощью графического интерфейса формируется образ задачи, который записывается в виде XML-файла и может быть сохранен и/или выполнен на КВУ. Основные назначения УМС — загрузка назначенных модулей задачи, выполнение цикла распознавания и обеспечение отказоустойчивости. В том числе: чтение xml-файлов с описанием решения задачи и каждого из требуемых модулей; инициализация каналов передачи данных; запуск системы и ожидание завершения работы системы. Гибкость системы обеспечивается использованием механизмов каналов и схем описания задачи. У каждого конкретного модуля есть набор входов и выходов (каналов), по которым он получает данные на обработку и отсылает обработанные результаты. Механизм схемы описания задачи позволяет задать произвольный набор модулей и связей между ними. Выбранная архитектура обеспечивает расширяемость системы, т.к. допускает реализацию и включение новых модулей в различные схемы задачи пользователя. Модули системы реализуются в виде подгружаемых библиотек и могут содержать как последовательную, так и параллельную реализацию алгоритма.
В первом случае параллелизм обеспечивает УМС (разделяя все обрабатываемые данные между доступными узлами кластера), во втором, стратегию параллельной обработки определяет программист, реализующий модуль. Помимо параллелизма используются возможности конвейерной обработки потока данных. Пакеты данных от одного модуля передаются следующему в цепочке (возможно, на другой узел кластера) после чего, сразу же, запускается их обработка. Шаблон модулей В соответствии с требованиями архитектуры все алгоритмы - модули должны быть оформлены определенным стандартным образом. У каждого модуля есть ряд характеристик, определяющих его положение в системе: параллельная или последовательная реализация алгоритма, число и тип каналов для пересылки данных, настройки модуля «по умолчанию» и специально для текущей задачи, и т.д. Структура шаблона состоит из следующих частей: - типа модуля и типа его реализации, - раздела описания параметров модуля, - раздела писания входных и выходных данных (каналов) модуля, - раздела описания модуля для интерфейса. В типе модуля указывается, является ли данный модуль обработчиком данных или нейронной сетью, а в типе реализации — является ли его реализация параллельной или нет. В разделе описания входных и выходных данных (каналов) описываются типы данных, которые получает и отсылает модуль, а для различия каналов модуля им присваиваются уникальные имена.
В разделе описания параметров указываются имена параметров, их типы, а также значения, присваиваемые им по умолчанию. Среди типов параметров модуля можно выделить возможность указания
Графический интерфейс для формирования задач распознавания образов
Для удобства формирования задач разработан специальный графический интерфейс (рис. 4.2) с использованием алгоритмов машинной графики [15]. Посредством функций интерфейса возможно: - выбирать методы предварительной обработки, типы и конфигурации ИНС, - создавать и запускать на выполнение схемы распознавания и сохранять полученные результаты, - задавать входные данные и отображать результаты работы. Функционирование графического интерфейса в семействе операционных систем Windows обеспечивается возможностями .Net Framework версии 2.0, в Unix-подобных операционных системах (в том числе и Linux) поддерживается работа интерфейса с графическими библиотеками libgdiplus и Mono, open-source реализации .Net. Графический интерфейс состоит из следующих компонент: - базовой и дочерних форм, - формы настроек интерфейса и модулей, - служебных классов, - файла настроек в xml-формате. Для работы интерфейса необходимо также иметь информацию о существующих модулях.
Описания существующих модулей содержаться в xml-файлах и подгружаются динамически при загрузке интерфейса. В разделе описания модуля для интерфейса указываются: - полное название модуля и его описание, - класс модуля, - описания параметров и их возможные значения, - описания входных и выходных данных (каналов). Во время динамической загрузки описаний модулей создается соответствующее меню (рис. 4.3) с динамически всплывающими подсказками. При выборе пункта этого меню появляется модуль на поле редактирования (рис. 4.4). Выделив модуль на поле редактирования можно отредактировать его параметры, которые соответствуют xml-описанию данного модуля. Как уже говорилось, модули могут быть либо обработчиками данных, либо нейронными сетями. В тоже время можно условно подразделить модули обработки данных на: - считывающие входные данные, - записывающие результаты работы, - обрабатывающие данные. В процессе редактирования схемы распознавания для обеспечения пересылки данных между модулями необходимо инициализировать каналы.
Это делается путем соединения выходного канала одного модуля с входным каналом другого модуля. При этом типы данных, пересылаемых по каналам должны совпадать (рис. 4.5). В результате сохранения такой схемы на жесткий диск создается xml-файл, состоящий из раздела описания списка модулей с установленными параметрами, а также из раздела описания связей между каналами соответствующих модулей. Для удобства пользователя в интерфейсе предусмотрены специальные модули интерфейса для определения входных данных и отображения результатов. Модули интерфейса для определения входных данных используются для визуализации процесса создания списка параметров, например списка файлов или директорий (рис. 4.6). Такой список хранится в специальном файле(ах) и подается как параметр модуля системы. Модули интерфейса отображения данных используются соответственно для отображения данных работы модулей сохранения результатов (рис. 4.7). При использовании графического интерфейса параметризация запуска вычислительного ядра решается автоматически согласно сохраненным настройкам. Кроме того, в реализации интерфейса используются библиотеки позволяющие посредством 88Н2-протокола запускать интерфейс независимо от остальной системы установленной, например, на удаленной машине. Кроме того, в интерфейсе существует специальная форма настроек визуального отображения блоков-модулей и классификации модулей.
Для упрощения поиска необходимого модуля в интерфейсе предусмотрена возможность создания специальных групп модулей (рис 4.8). Для каждой такой группы можно указать - название группы, - форму, цвет и величины отступов текста от границ блока, - тип, размер и цвет шрифта блока, а также для всех групп настроить цвета, шрифт и отступы активных и неактивных каналов модулей. На другой вкладке формы настроек можно классифицировать модули по созданным группам (рис. 4.9).
