Исследование и разработка алгоритмов интеллектуальной поддержки классификации графической информации

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

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

Большое количество исследователей в настоящее время работают над узкоспециализированными областями, ограничиваясь лишь одним методом решения [23−25]. Данная исследовательская область считалась до недавнего времени трудоемкой, малоизученной и рассматривала только черно-белые изображения. Это связано в первую очередь с трудностью определения целевой функции (как правило, в роли нее выступает мнение эксперта по поводу решения) и значительное время обработки изображения. Так же затруднительна разработка универсальных подходов и подбор параметров для изображений различных классов и типов. Рост областей применения компьютерного зрения и их количества становятся причиной для разработки новых подходов в решении задач автоматизированной обработке изображений. В данный момент появляются интеллектуальные и проблемно-ориентированные подходы, использующие численные методы для большей эффективности обработки, что позволяет в некоторых случаях получать решения удовлетворительного качества даже в режиме реального времени. Конечной целью любой задачи компьютерного зрения является уменьшение участия человека в процессе обработки изображений до контроля полученных результатов.

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

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

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

Эволюционные алгоритмы становятся все более популярными среди исследователей, что подтверждается более чем 2000 ежегодно публикуемыми статьями по этой теме [26]. Они представляют собой упрощенное моделирование процесса эволюции в природе, т. е. механизмов селекции и генетики. Одним из их главных преимуществ является способность выходить из локальных максимумов и находить нестандартные решения [27−29].

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

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

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

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

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

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

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

Из всех органов чувств человека зрение является наиболее важнымоколо 90% информации мы получаем именно посредством его. Наше поведение напрямую зависит от интерпретации того, что мы видим. Относительно недавно начавшиеся исследования проблем зрительного восприятия направлены на понимание общих проблем обработки оптической информации визуальной системой человека. Совокупность задачи автоматизации обработки изображения и разработка специализированной аппаратуры и алгоритмов, в какой-то степени моделирующих зрительную систему млекопитающих, становится сейчас все более популярной [1−5]. Поэтому для улучшения полученного решения наиболее перспективным подходом является численное моделирование зрительных систем млекопитающих.

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

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

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

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

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

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

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

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

Построение программного модуля эволюционной оптимизации составляющих обучающего набора.

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

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

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

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

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

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

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

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

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

3. Разработан метод классификации векторов в многомерном пространстве признаков с использованием аппарата машин опорных векторов.

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

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

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

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

Одним из возможных применений системы классификации являются медицинские изображения. Применительно к этой области был построен аппаратно-программный комплекс, используемый во врачебной практике в университетском госпитале Штутгарта. Программная часть разработана под операционную систему Windows, написана на языке С++. Компиляция проведена в среде объектно-ориентированного программирования Microsoft Visual С++®-. Предложенные методы позволяют достигнуть улучшенных ^ показателей автоматизированной сегментации изображений.

Реализация результатов работы. Основные практические и теоретические результаты диссертационной работы использованы в научных исследованиях по гранду Фраунгоферовского общества (Германия) в Институте информационных коммуникаций, г. Сант-Августин, Германия, а так же в промышелнном проекте «CRAFT-WUNSENS — Automatic Segmentation of Wound Images», выполненом так же в Институте иформационных технологий, > г. Санкт-Августин, Германия.

Материалы диссертации были использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

Апробация результатов работы. Основные теоретические и практические результаты работы докладывались и обсуждались на следующих конференциях: международная научно-техническая конференция «Интеллектуальные САПР» (г.Дивноморск, 2001, 2002 гг.), AISB'03 Cognition in Machines & Animals (Великобритания, г. Аберистуит, 7−11 апреля 2003 г.), Biologically Motivated Computer Vision 2002 (BMCV'02) (Германия, г.

Тюбинген, 22−24 ноября 2002 г.), Scandinavian Conference on Image Analysis 2003, 13th Scandinavian Conference (SCIA'03) (Швеция, Хальмштадт, 29 июня -2 июля 2003 г.).

Публикации. Результаты диссертационной работы отражены в 9 печатных работах.

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

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 170 стр., включая 63 рис., 5 табл., список литературы из 115 наименований, 5 страниц приложений.

4.7. Выводы и рекомендации.

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

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

5. Реализован новый подход' на биологической основе для интегрированного обнаружения границ в цветных изображениях. Модель использует итеративную обработку визуального входа и локальные усиливающие взаимодействия нейронов, — чувствительных к ориентации и к цвету. Стадия обработки основана на • основных принципах нейронных соединений, найденных в визуальной системе млекопитающих. Ключевая особенность модели: с итерациями усиливаются границы, присутствующие как в цветовых, так и в яркостных переходах. Конечно, реальная модель VI гораздо более сложна. Несмотря на это упрощение, комбинированная модель выявления цветовых границ является удачной попыткой моделирования эффекта локального взаимного возбуждения нейронов. Применение контуров объектов, найденных данным алгоритмом для работы активного контура позволило существенно улучшить решение, полученное машинами векторной поддержки.

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

7. Произведена программная реализация системы классификации графической информации. При разработке программного обеспечения были учтены критерии для продолжения исследований в обозначенной области, такие как интуитивность и простота работы системы в целом и отдельных ее компонент. Программа сохраняет не только итоговое решение, но так же решения промежуточных стадий — в различных форматах представления. В качестве языка программирования был выбран С++, так как система обладает значительной вычислительной сложностью. Интерфейс был написан на языке Visual С++ 6.0 под операционную систему Windows ХР и был протестирован на двухпроцессорном компьютере. Минимальные требования для устойчивой работы программы — Intel Pentium® — совместимый процессор под управлением 32-х разрядной операционной системы Windows, в зависимости от мощности обучающего набора 30−400 МБ свободного места на жестком диске, 128 МБ оперативной памяти без учета требований операционной системы.

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