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

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

БАРЛИТ Александр Васильевич^

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

Специальность 05.13 01 - «системный анализ, управление и обработка информации»

АВТОРЕФЕРАТ

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

Таганрог 2005

Рабо)а выполнена в Таганрогском Университете ('["РТУ )

Научный руководитель

Официальные оппоненты:

Ведущая организация:

Государственном Радиотехническом

заслуженный деятель науки РФ, д-р техн. наук, проф. Курейчик В.М.

д-р техн. наук, проф. Карелин В II д-р техн. наук, проф. Витиска Н И

Федеральное Государственное унитарное предприятие

Таганрогский НИИ связи (г Таганрог)

Защита состоится " " июля 2005 I и !420 на заседании диссертационного совета Д 212.259.03 по защите диссертаций при Таганрогском Государственном Радиотехническом Университете по адресу 347922, г Таганрог, пер Некрасовский, 44, ауд. Д-406

С диссертацией можно ознакомиться в библиотеке Таганрогского I 'осу дарственного радиотехнического университета

Автореферат разослан " " мая 2005 г.

Ученый секретарь диссертационного совета д-р техн. наук, проф.

А. Н. Целых

¿006 >4

з

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

Актуальность работы.

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

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

При решении задач кластеризации и распознавания образов необходимо использовать аппарат обработки и хранения экспертных знаний о классах изображения или объектов Распространенным методом являются искусственные нейронные сети, которые так же обладают рядом недостатков, в том числе проблема «исключающего или» и неоптимальность найденного решения "Этих недостатков лишен новый подход к построению разделяющих гиперплоскостей, названный машинами опорных векторов Принцип их работы закчючается в нелинейном проецировании точек из Евклидова пространства признаков в пространство Гильберта, где строится линейная разделяющая гиперплоскость

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

В решении оптимизационных задач хорошо зарекомендовали себя методы генетического поиска Их основным отличием от других поисковых методов является оперирование целым множеством частных решений Решение оценивается с помощью целевой функции Для модификации частных решений используются генетические операторы, основа которых лежит в естественных системах. Основные из них - оператор кроссинговера и мутации Послр^тямфшшшиШвШргося множества решений осуществляется выбор лучш „| «де-МАПЦИМЫ вЦрснове формируется новое множество частных решений. I емируя

• <» тУтт^Ь

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

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

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

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

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

задачи-

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

3 Создание алгоритма параметрического синтеза системы обработки и храпения эксперт ной информации

4 Разработка алгоритма параметрического синтеза машины опорных векторов.

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

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

1 Разработке комплекса алгоритмов решения задачи автоматизированной кластеризации графической информации

2 Создании алгоритма параметрического синтеза системы обработки экспертной информации и машины опорных векторов

3 Разработке системы классификации ючек и пространстве признаков на основе машин опорных векторов

Практическую иенность работы представляют

1 Методы обрабо1ки и хранения экспертной информации о клаоерач графической информации

2 Алгоритмы и программное обеспечение для решения задачи интеллектуальной поддержки при классификации графической информации

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной научно-исследовательской работе ТРТУ «Разработка теории и -принципов построения интеллектуальных систем авгоматизированнбго' проектирования на основе эволюционной адаптации, нейро'сстевых м6йЙле# й методов принятия решений»

Материалы диссертации использованы в учебном процессе на кафедре С AI IP ТРТУ при чтении лекций по курсам «Методы оптимизации», «Компьютерная графика», «Геометрическое моделирование в САПР», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования», а так же на кафедре обработки изображений Швейцарского Федерального Технологического Института, г Цюрих, Швейцария Разработанный программный комплекс был успешно протестирован и принят к использованию госпиталем при институте г Штутгарт, Германия, и являлся частью проекта «Craft Wunsens», выполненного институтом Fraunhofer Gesellschaft, Санкт Августин, Германия

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

1. Комплекс алгоритмов для решения задачи кластеризации изображений.

2 Параметрический синтез системы обработки и хранения экспертной информации.

3 Система классификации точек в пространстве признаков на основе машины опорных векторов

Апробация работы и публикации. Основные теоретические и практические результаты работы представлены на Международной научно-техническая конференция «Интеллектуальные САПР» (г Дивноморск, 2001, 2002 гт), Cognition in Machines & Animals (Великобритания, г Аберистуит, 2003 г.), Biologically Motivated Computer Vision (Германия, г Тюбинген, 2002 г ), Scandinavian Conference on Image Analysis, 13th Scandinavian Conference (Швеция, Хальмпггадт, 2003 г)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

гистограмма интенсивности; двумерные гистограммы цветовых составляющих; контрастность отдельного пикселя; одномерная гистограмма контрастности; локальный двоичный образ, как и контрастность, описывающий информацию о текстуре; одномерная гистограмма локального двоичного образа; двухмерная гистограмма текстурных признаков; трехмерная гистограмма цветовых составляющих; применение диаграммы Вороного вместо последовательного алгоритма построения многомерных гистограмм, построение гистограмм с определением областей по методу Монте-Карло; применение цветовой кодировки Ohta вместо RGB Всего во входной информации, с учетом применения различных методов построения гистограмм и цветовых кодировок, содержится 54 признака графических объектов

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

основных этапов скрещивание (кроссинговер), отбор (селекция), мутация Частные решения с лучшей целевой функцией будут преобладать в ходе решения, так как 1 выбор решения оператором селекции пропорционален целевой функции частного

решения

Постановка задачи параметрического синтеза описана кортежем- <Х, D, Q>. Где X - является множеством всех решений, D - офаничения, накладываемые на множество X, для получения допустимых решений и Q - целевая функция (ЦФ), с помощью которой можно определить наилучшее (оптимальное) решение

X - множество всех возможных хромосом в популяции Эти хромосомы могут быть нерелевантными, те кодировать в себе недопустимые решения, или решения, не приводящие ни к какому результату Обозначим популяцию на шаге ГА / как Р,, а хромосому с номером / И, Тогда можно записать, что популяция на шаге t Р,^ fh,, , И„},тце t = [1,Т],п - [!,N], Т-количество итераций ГА иN-количество хромосом в популяции Параметр Т может варьироваться в заданных пределах Тогда X можно записать в следующей форме'

X = {Ph t=J, . ,T} {h,„t 4, . , Т; i = /, .,Nj

О - множество ограничений Решение представляется в виде неоднородной хромосомы Исходя из этого условия, каждый ген может приминать только 01раниченное количество значений, чтобы удовлетворять условию Ис^Х, г е принадлежать области допустимых решений Для генов, кодирующих наличие определенного признака, это значения 0 и 1 - г е признак отсутствует или присутствует в данном решении Для гена, кодирующего размер окна анализа, это значения от 5 (анализируется только один пиксель) до 99 (анализируются 992 пикселей).

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

Я = */£>, + к£Е,

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

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

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

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

3 Вычисление процента ошибок Для того же изображения берется фиксированное число точек на нем, которые гак же расположены в умах сетки с квадратными ячейками и для них стоятся те же вектора признаков за исключением Ю10, чю класс, которому принадлежит пиксель, не известен Номер класса, которому принадлежит пиксель, определяется модулем классификации на основе данных обучения Процент" неправильно классифицированных точек является второй составляющей целевой функции

Время выполнения первого и третьего этапов - первая составляющая критерия оптимизации (? Оптимизация задачи параметрического синтеза сводится к минимизации критерия т е <2(Х)—*тш.

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

принимающие значения от 0 до 9 Они формируют две порядковых составляющих размера графического объекта Начальная популяция формируется случайным образом с учетом вышеперечисленных ограничений и следующих эвристик: количество признаков в частном решении должно лежать в пределах 11,5] и размер фафического объекта варьируется от 5 до 99 Ксли последнее значение меньше нижнего порога, то ему присваивается 5

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

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

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

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

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

Рассмотрим случай бинарной классификации Каждому вектору пространства признаков .v, соответствует число у„ равное 1 или -1 в зависимости от того, какому классу относится данный вектор Задача заключается в нахождении такой функции, что yf(xj О V / Данная функция представима в виде f(x) (x,w) ' b, 1де скобки обозначают скалярное произведение на некоторый вектор w, b -константа Условие разделения классов переписывается в виде yf((W,XJ i b)>0 V i, a уравнение разделяющей гиперплоскости (W,X) * b ~() Вектора, лежащие между плоскостями (fV,XJ i b-1 - (! и (IV,X) ' b -1 0, называются опорными Предлагается минимизировать функцию половины квадрата длины (),5W W и задача минимизации приобретает вид' Q,5WW —min(W, b), yf((W,XJ * b)>0 V i Она равносильна поиску точек экстремума оператора Лагранжа

L(W,b,A) = 0,5W -W-YMy,X,) + b-1)

/

no множителям Лагранжа Л>0 V i Таким образом, параметры разделяющей гиперплоскости выражены через множители Лагранжа и обучающие вектора А для классификации любого вектора необходимо вычислить

1 /

Данная функция зависит только от коэффициентов у, и скалярных произведений векторов признаков Поэтому при проецировании в пространство Гильберта <p(Xj необходимо знать только функцию вычисления скалярного произведения в этом пространстве' K(XhX2) = ( <p(Xi), ф(Х:)) Данная функция называется ядром, так как является ядром интефального оператора при вычислении f(X)

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

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

• масштабирование данных обучения в пределах [0,1 J,

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

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

• автоматизированная классификация новых изображений

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

оставшихся п-1 поднаборов Таким образом, производится объективная оценка оптимальности рассматриваемых параметров Данная процедура выполняется для четырех основных гипов функций ядра' полиномиальная, сигмоидальная, радиально-базисная, скалярная функция расстояний Найденным решением считается набор параметров, который показал наилучший результат

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

líe основные свойства: принимаемые значения лежат в пределах [0,1], имеет минимальное число параметров, может проецировать вектор в пространство большей размерности так же, как и полиномиальная.

Алгоритм параметрического синтеза позволяет избежать эффекта «переобучения», т е когда разделяющая полоса получается очень тонкой.

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

Для уменьшения количества неправильно классифицированных графических объектов применяется алгоритм активного контура. Контур представляется в виде набора вершин, соединенных векторами. Функция топологии ивисит от оценки локальной искривленности контура и расстояния между его вершинами, а функция изображения зависит от яркости градиента пикселей. Функция энергии рассматривается только для позиции вершины бе) учета направлений векторов Алгоритм начинает работу с контура, полученного во время работы модуля сегментации Сжимающие внутренние силы зависят от формы контура, а поле внешних сил определяется самим изображением. Внутренние силы стараются минимизировать кривизну контура, в то время как поле внешних сил изменяет контур в соответствии с изображением. Процесс деформации контура включает определенное число шагов На каждом шаге пересчитываются позиция, скорость и ускорение каждой вершины Баланс внешних и вну тренних сил изменяет скорость вершины и ее ускорение В ходе деформации контура Moi-yi появиться два нежелательных эффекта - сжатие контура и кластеризация (скопление вершин в определенных частях контура) Первую проблему предлагается решить введением влияния на локальную кривизну контура свойств смежных вершин, вторую - учетом юлько радиальной составляющей сил для каждой вершины Целыо работы аетивного контура является обеспечение точного совмещения получаемого контура с реальными границами изображения при минимальном участии пользователя. Данный метод может быть применен для любой системы, описываемой пикселями или матрицей параметрических вершин На основе разработанной двухмерной модели может быть построена и трехмерная модель.

Для решения проблемы сжатия контура под действием внутренних сил был использован фильтр, содержащий три ненулевых значения. k¡ {.. ,0,0, -1/2, 1, -1/2, 0, 0, }. Сила, действующая на каждую вершину, подвергается воздействию этого фильтра В результате контур любой формы без воздействия внешних сил за некоторое число итераций превратится в круг В качестве внешних сил выбрано поле

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

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

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

Для проведения экспериментальных исследований разработан комплекс программ сешентации изображений Программы написаны на языке С++ и скомпилированы в среде Visual С++ 6 (f для операционных систем семейства Windowb 95, 98, NT, 2000, XI' Эксперименты проводились на компьютере семейства PC с двумя процессорами Intel Xeon 2,8 ГГц и оперативной памят ью I ГБ.

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

Рис 1 Структурная схема системы классификации графических объектов.

Экспериментальные исследования проводились в 5 этапов. На первом этапе происходит параметрический синтез информации о графическом объекте Работа алгоритма была ограничена 24 часами и программа произвела 142 итерации Как отмечалось выше, данный процесс выполняется один раз пред первым обучением системы. Найденными признаками являются трехмерная цветовая гистограмма и двухмерная гистограмма по текстуре Второй этап - обучение машины опорных векторов Третий этап - классификация изображения, не входившего в обучающую последовательность Четвергый этап - определение контуров этого изображения Заключительный этан - работа алгоритма активного контура

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

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

Проведенные исследования показали, ччо разработанный комплекс алгоритмов дает результат качеспю которого превосходи! существующие аналоги В частности машина опорных векторов неправильно классифицировала только 3,15% графических объеюов в ю время, как многослойный персептрон более 20%

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

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

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

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

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

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

2 Разработан комплекс алгоритмов кластеризации графической информации Определена теоретическая и экспериментальная оценки временной сложности комплекса программ сегментации изображений Она составляв! 0(N), где N - число графических объектов

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

4 Реализован модифицированный алгоритм машины опорных векторов и ее параметрический синтез Применение машины опорных векторов для обработки экспертной информации и автоматизированной классификации точек в пространстве признаков, позволило улучшить качество решения на 15-20%

5 Использование комплекса алгоритмов повышения качества решения позволило уменьшить количество неправильно классифицированных фафических объектов на 2-5%

6 Для реализации предложенного комплекса алгоритмов разработано программное обеспечение При ра(работке про!рамм учтены критерии создания пользовательского интерфейса Он является максимально упрощенным, так как задачей пользователя является только выбор входного изображения и считвание выходной информации Программа выводит информацию о проделанной работе в виде набора изображений, показывающих несколько вариантов представления найденной области Программа написана на языке программирования С++ и скомпилирована в среде Visual С++ 6 0 для ОС Windows 95, 98, 2000 ХР Большинство реализованных алгоритмов могут быть скомпилированы в любой операционной системе, имеющей реализацию языка С++ Для запуска программы потребуется PC - совместимый компьютер с процессором Pentium или выше и объемом оперативной памяти - 256 МБ

Особенностями разработанной программной реализации являются распараллеливание процесса анализа изображений при использовании многопроцессорных систем и возможность внедрения в автономные системы. Время работы одного цикла кластеризации изображения разрешением 800x600 составляет 580 секунд, улучшение качества решения - 32 минуты при пяти итерациях работы алгоритма Требуемый объем памяти для кластеризации изображения - 32 МБ, для комплекса алгоритмов улучшения решения - 312 МБ.

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

1. Барлит А В , Нужное Е В Параллельный генетический алгоритм трехмерной упаковки объектов Интеллектуальные системы. Коллективная монография - М.' Физматлит, 2005, с.257-264.

2. Барлит А В., Нужнов Е В. Применение модели активного контура для уточнения фаниц объекто§ изображений Труды Международных научно-технических конференций «Интеллектуальные системы» (IEEE AIS'03) и «Интеллектуальные САПР» (CAD-2003). Научное издание. Том 2. - Москва: Издательство Физико-математической литературы, с. 271-285

3. Барлит А В., Нужнов Е В Решение задачи трехмерной упаковки с помощью параллельного генетического алгоритма Труды Международных конференций «Искусственные интеллектуальные системы» (IEEE ICAIS'02) и «Интеллектуальные САПР» (CAD-2002). Научное издание. Москва: Издательство Физико-математической литературы, 2002, с 338-344.

4 Барлит А В , Нужнов Е В Сегментация изображений и выявление контуров об1>ектов на основе генетических алгоритмов Известия ТРТУ Тематический выпуск: Интеллектуальные САПР Материалы Международной научно-технической конференции "Интеллектуальные САПР" Таганрог- Иэд-во ТРТУ, 2003, № 2, с 114120.

5 Barlit A.V , Nuzhnov E.V Active Outline Model Application For More Precise Definition Of Object Image Borders Proceedings Of The International Scientific Conferences "Intelligent Systems" (IEEE AIS'03) and "Intelligent CAD's" (CAD-2003) Moscow Physmathlit Publishing 2003 VoI3,pp 116-123

6 Kolesnik, M, Barlit, A , Zubkov, E Iterative Tuning of Simple Cells for Contrast Invariant Edge Enhancement Proceedings of International Workshop on Biologically Motivated Computer Vision (BMCV'2002). Tübingen, Germany, 22-24 November, 2002, pp.27-37

7 Kolesnik, M., Barlit, A Iterative Orientation Tuning of Simple Cells in VI: A Comparative Study of Two Computational Models for Contrast Detection in Images. Proceedings of the AISB'03 Symposium on Biologically-Inspired Machine Vision, Theory and Application. UK, Aberystwyth, 2003, pp.122-130.

8 Kolesnik, M., Barlit, A Iterative orientation Tuning in VI a Simple Cell Circuit with Cross-Orientation Suppression. Proceedings of the Scandinavian Conference on Image Analysis, Sweden, 2003, pp. 313-321

9 Kolesnik M., Barlit A. Zubkov E.. Simple Cell Interaction for Iterative Contrast Detection Proceedings of the IHRE international Conference on Artificial Intelligence

stems, USA, California, Computer Society, 2002, pp. 122-128.

Личный вклад автора в работах, опубликованных в соавторстве: [1-4] -разработка структуры алгоритмов, [5] - программная реализация и проведение экспериментальных исследований, [6-9] - разработка математического обеспечения предлагаемых систем и их параметрический синтез

»124 17

Соискатель А.В. Барлит

РНБ Русский фонд

2006-4 10918

Тип.ТРТУ Заказ

ВВЕДЕНИЕ.

Глава 1. ОБЗОР МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ КЛАССИФИКАЦИИ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ.

1.1 Методы классификации графической информации.

1.2 Постановка задачи классификации графической информации.

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

1.3.1. Искусственные нейронные сети.

1.3.2. Машины векторной поддержки.

1.3.3. Анализ генетических методов.

1.4. Выводы.

Глава 2. СТРУКТУРНО-ПАРАМЕТРИЧЕСКИЙ СИНТЕЗ СИСТЕМЫ щ КЛАССИФИКАЦИИ ГРАФИЧЕСКИХ ОБЪЕКТОВ.

2.1. Формирование исходного набора признаков графического объекта.

2.2. Разработка алгоритма параметрического синтеза системы.

2.2.1. Принципы кодирования и декодирования хромосом.

2.2.2. Формирование начальной популяции.

2.2.3. Модифицированные генетические операторы.

2.3. Анализ эффективности алгоритма параметрического синтеза.

2.4. Выводы.

Глава 3. РАЗРАБОТКА МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ СИСТЕМЫ КЛАССИФИКАЦИИ ГРАФИЧЕСКИХ ОБЪЕКТОВ.

3.1. Разработка системы классификации изображений.

3.1.1. Разработка машины векторной поддержки.

3.1.2. Алгоритм параметрического синтеза машин векторной поддержки.

3.2. Построение алгоритмов улучшения качества решения. ф 3.2.1. Алгоритм активного контура.

3.2.2. Детектор границ объектов.

3.3. Выводы.

Глава 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ЕЕ ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ.

4.1. Архитектура программной системы классификации графических объектов.

4.2. Цель экспериментальных исследований.

4.3. Исследование эффективности программы параметрического синтеза.

4.4. Исследование эффективности алгоритма обучения и классификации.

4.5. Исследование эффективности алгоритма обнаружения контуров в изображении.

4.5. Исследование эффективности алгоритма активного контура.

4.6. Область применения предложенной системы классификации.

Интеллектуальная поддержка при классификации графической информации является актуальной задачей, решение которой может существенно облегчить многие рутинные операции в областях, использующих компьютерное зрение. Компьютерное зрение (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. Проведенные экспериментальные исследования показали эффективность предложенной системы классификации графической информации. Предложенный подход позволяет уменьшить участие человека в наблюдении за динамикой изменения кожных ран до контроля результатов.

1. Scheunders P. "A comparison of clustering algorithms applied to color image quantization"

2. Heckbert P. "Color image quantization for frame buffer display." Comput. Graphics 16 (3), 1982, 297-307.

3. Wan S.J., P. Prusinkiewicz, S.K.M. Wong "Variance-based color image quantization for frame buffer display". Color. Res. Appl. 15, 1990, 52-58.

4. Balasubramanian R., J.P. Allebach,C.A. Bouman. "Color-image quantization with * use of a fast binary splitting technique." J. Opt. Soc. Am. A Vol. 11,11, 1994, 27772786.

5. Celenk M. "A color clustering technique for image segmentation". Computer Vision, Graphics and Image Processing 52, 1990, 145-170.

6. Scheunders P. "A genetic C-means clustering algorithm applied to color image quantization." Pattern Recognition,Vol. 30, 1997, nr. 6.

7. Matti Pietikainen, Topi Maenpaa, Jaakko Viertola "Color Texture Classification with Color Histograms and Local Binary Patterns"ft»

8. Rosenfeld A., Ye-Wang C. and Wu A., "Multispectral Texture," IEEE Trans. Systems, Man, Cybern., vol. SMC-12, no. 1, pp. 79-84, 1982.

9. Caelli T. and Reye D., "On the Classification of Image Regions by Colour, Texture and Shape," Pattern Recognition, vol. 26, no. 4, pp. 461-470, 1993.

10. Mirmehdi M. and Petrou M., "Segmentation of Color Textures," IEEE Trans. Pattern Anal. Machine Intell, vol. 22, no. 2, pp. 142-159, 2000.11^ Swain M., Ballard D., "Color Indexing," Int. J. Comput. Vis., vol. 7, no. 1, pp. 1132, 1991.

11. Ojala Т., Pietikainen M., and Harwood D., "A Comparative Study of Texture Measures with Classification Based on Feature Distributions,"Pattern Recognition, vol. 29, pp. 51-59,1996.

12. E. Монахова, "Нейрохирурги" с Ордынки, PC Week/RE, №9, 1995.

13. Ф.Уоссермен, Нейрокомпьютерная техника, М.,Мир, 1992.

14. Итоги науки и техники: физические и математические модели нейронныхсетей, том 1, М., изд. ВИНИТИ, 1990.

15. Artificial Neural Networks: Concepts and Theory, IEEE Computer Society Press, 1992.

16. Richard P. Lippmann, An Introduction to Computing with Neural Nets, IEEE Acoustics, Speech, and Signal Processing Magazine, April 1987.

17. Vladimir N. Vapnik. The nature of Statistical Learning Theory. Springer, New York, 1995.

18. R. Courant and D. Hilbert. Methods of Mathematical Physics. Volume I. Springer

19. Verlag, Berlin, first English edition, 1953.

20. Christopher J.C. Burges. A Tutorial on Support Vector Machines for Pattern Recognition. Data mining and Knowledge Discovery. 1998.

21. R. Watt. Visual Processing: Computational, Psychophysical and Cognitive Research. Lawrence Erlbaum Associates, Publishers, 1988.

22. Айзерман M.A., Бравеман Э.М., Розоноэр JI.H. Проблема обучения машин распознаванию внешних ситуаций. Сб.: Самообучающиеся автоматическиесистемы, Наука, 1966.

23. Wei-Ying Ma and В S Manjunath. Edge°ow: a technique for boundary detection and image segmentation. IEEE Transactions on Image Processing, August 2000.

24. Luminita A. Vese and Tony F. Chan. A multiphase level set framework for image segmentation using the mumford and shah model. International Journal of Computer Vision, December 2002.

25. J. Shah. A common framework for curve evolution, segmentation and anisotropic difusion. In IEEE Computer Society Conference on Computer Vision and Pattern

26. Recognition (CVPR), June 1996.

27. Griffith P.S., Proestaki A., Sinclair M.C. Heuristic topological design of low-cost optical telecommunication network. Proc. 12-th UK Performance Engineering workshop, Edinburg, 1996.

28. J. R. Koza, F. H. Bennett, D. Andre and M. A. Keane, "Genetic Programming III: Darwinian Invention and Problem Solving", San Francisco, С A: Morgan Kaufmann. 1999.

29. Корячко В.П., Курейчик B.M., Норенков И.П. Теоретические основы САПР. Москва.: Энергоатомиздат, 1987.

30. Kureichik V. М., Kureichik V.V. Genetic Algorithms. Hartung-Gorre Verlag, Konstanz 2004.

31. Concetta Morrone M. and D. C. Burr. Feature detection in human vision: A phase-dependent energy model. Proceedings of the Royal Society of London. Series B, Biological Sciences, 1988.

32. Luminita A. Vese and Tony F. Chan. A multiphase level set framework for image segmentation using the mumford and shah model. International Journal of Computer Vision, 2002

33. D. Marr and E. Hildreth. Theory of edge detection. Proceedings of the Royal Society of London. Series B, Biological Sciences, 1980.

34. John Canny. Finding edges and lines in images. Technical report, MIT Artificial Intelligence Laboratory AITR-720, 1983.

35. R. Haralick. Digital step edges from zero crossings of second directional derivatives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984.

36. M. Concetta Morrone and D. C. Burr. Feature detection in human vision: A phase-dependent energy model. Proceedings of the Royal Society of London. Series B, Biological Sciences, 1988.

37. P. Perona and J. Malik. Detecting and localizing edges composed of steps, peaks and roofs. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 1990.

38. Stephen M. Smith and J. Michael Brady. Susan a new approach to low level image processing. International Journal of Computer Vision, 1997

39. M. Nitzberg, D. Mumford, and T. Shiota. Filtering, Segmentation and Depth. Springer-Verlag, 1993.

40. M. Zuliani, C. Kenney, and B. S. Manjunath. A mathematical comparison of point detectors. In Image and Video Registration Workshop (IVR), 2004.

41. M.A. Ruzon and C. Tomasi. Color edge detection with the compass operator. IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 1999.

42. D.R. Martin, C.C. Fowlkes, and J. Malik. Learning to detect natural image boundaries using local brightness, color, and texture cues. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004.

43. K. Bowyer, C. Kranenburg, and S. Dougherty. Edge detector evaluation using empirical roc curves. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 1999.

44. M.J. Black, G. Sapiro, D.H. Marimont, and D. Heeger. Robust anisotropic diffusion. IEEE Transactions on Image Processing, 1998.

45. F. Heitger. Feature detection using suppression and enhancement. Technical Report TR 163, Image Science Lab, ETH-Zurich, 1995.

46. S. Konishi, A.L. Yuille, J. Coughlan, and Song Chun Zhu. Fundamental bounds on edge detection: an information theoretic evaluation of different edge cues. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 1999.

47. D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In IEEE International Conference on Computer Vision (ICCV), 2001.

48. M Kass, A Witkin, and D Terzopoulos. Snakes: active contour models. International Journal of Computer Vision, 1987.

49. J. Shah. A common framework for curve evolution, segmentation and anisotropic diffusion. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 1996.

50. Stanley Osher and James A Sethian. Fronts propagating with curvature-dependent speed: Algorithms based on hamilton-jacobi formulations. Journal of Computational Physics, 1988.

51. J A Sethian. Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science. Cambridge University Press, 1999.

52. V Caselles, R Kimmel, and G Sapiro. Geodesic active contours. International Journal of Computer Vision, 1997.

53. Chenyang Xu, A Jr Yezzi, and J L Prince. On the relationship between parametric and geometric active contours. In Asilomar Conference on Signals, Systems and Computers, 2000.

54. S. Kichenassamy, A. Kumar, P. Olver, A. Tannenbaum, and A. Yezzi. Gradient flows and geometric active contour models. In International Conference on . Computer Vision (ICCV), 1995.

55. V Caselles, F Catte, T Coll, and F Dibos. A geometric model for active contours . in image processing. Numerische Mathematik, 1993.

56. M Tabb and N Ahuja. Multiscale image segmentation by integrated edge and region detection. IEEE Transactions on Image Processing, May 1997.

57. L. D. Cohen and I. Cohen. Finite-element methods for active contour models and balloons for 2-d and 3-d images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993.

58. J. Canny. A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986.

59. Chenyang Xu and J. L. Prince. Snakes, shapes, and gradient vector flow. IEEE Transactions of Image Processing, 1998.

60. Jianbo Shi and J Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000.

61. S. Sarkar and P. Soundararajari. Supervised learning of large perceptual organization: graph spectral partitioning and learning automata. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000.

62. H. Jermyn and H. Ishikawa. Globally optimal regions and boundaries as minimum ratio weight cycles. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001.

63. J.M. Gauch. Image segmentation and analysis via multiscale gradient watershed hierarchies. IEEE Transactions on Image Processing, 1999.

64. M.W. Hansen and W.E. Higgins. Watershed-based maximum-homogeneity filtering. IEEE Transactions on Image Processing, 1999.

65. Tremeau and P. Colantoni. Regions adjacency graph applied to color image segmentation. IEEE Transactions on Image Processing, 2000.

66. Pitas and C.I. Cotsaces. Memory efficient propagation-based watershed and influence zone algorithms for large images. IEEE Transactions on Image Processing, 2000.

67. Jaesang Park and J.M. Keller. Snakes on the watershed. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001.

68. O. Lezoray and H. Cardot. Cooperation of color pixel classification schemes and color watershed: a study for microscopic images. IEEE Transactions on Image1. Processing, 2002.

69. Hieu Tat Nguyen, M. Worring, and R. van den Boomgaard. Watersnakes: energy-driven watershed segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003.

70. I Vanhamel, I Pratikakis, and H Sahli. Multiscale gradient watersheds of color images. IEEE Transactions of Image Processing, 2003.

71. P.R. Hill, C.N. Canagarajah, and D.R. Bull. Image segmentation using a texture gradient based watershed transform. IEEE Transactions on Image Processing, 2003.

72. O. Pichler, A. Teuner, and B.J. Hosticka. An unsupervised texture segmentation algorithm with feature space reduction and knowledge feedback. IEEE Transactions on Image Processing, 1998.

73. T. Hofmann, J. Puzicha, and J.M. Buhmann. Unsupervised texture segmentation in a deterministic annealing framework. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998.

74. T. Randen and J.H. Husoy. Texture segmentation using filters with optimized energy separation. IEEE Transactions on Image Processing, 1999.

75. L.M. Kaplan. Extended fractal analysis for texture classification and segmentation. IEEE Transactions on Image Processing, 1999.

76. Hsi-Chia Hsin. Texture segmentation using modulated wavelet transform. IEEE Transactions on Image Processing, 2000.

77. M.L. Comer and E.J. Delp. The em/mpm algorithm for segmentation of textured images: analysis and further experimental results. IEEE Transactions on Image Processing, 2000.

78. Christophe Samson, Laure Blanc-Fraud, Gilles Aubert, and Josiane Zerubia. A level set model for image classification. International Journal of Computer Vision, pages 2000.

79. J.A. Rushing, H. Ranganath, T.H. Hinke, and S.J. Graves. Image segmentation using association rule features. IEEE Transactions on Image Processing, 2002.

80. M. Achaiyya, R.K. De, and M.K. Kundu. Extraction of features using m-band wavelet packet frame and their neuro-fuzzy evaluation for multitexture segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003.

81. J.-F. Aujol, G. Aubert, and L. Blanc-Feraud. Wavelet-based level set evolution for classification of textured images. IEEE Transactions on Image Processing, 2003.

82. P Brodatz. Textures: A photographic album for artists and designers. 1966.

83. Zhuowen Tu, Song-Chun Zhu, and Heung-Yeung Shum. Image segmentation by ^ data driven markov chain monte carlo. In IEEE International Conference on1. Computer 2001.

84. Zhuowen Tu and Song-Chun Zhu. Image segmentation by data-driven markov chain monte carlo. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002.

85. Hoffman T.; Tsochantaridis I., Altun Y., Support Vector Machine Learning for Interdependent and Structural Output Spaces. International Conference on Machine Learning, 2004.

86. J. Koza. Genetic Programming: on the Programming of Computers my Means of Natural Selection, Cambridge, MA: MIT Press, 1992.

87. Bentley P., "An Introduction to evolutionary design by computers", In Evolutionary design by computers, Morgan Kaufmann, 1999, pp. 1-74.

88. Holland John H., Adaptation in Natural and Artificial Systems: An Introductory * Analysis with Application to Biology, Control, and Artificial Intelligence. USA:

89. University of Michigan, 1975.

90. Goldberd D. E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989, 412 p.

91. Курейчик В.В. Концепция оптимизации на основе моделирования эволюции. Новые информационные технологии. Разработка и аспекты применения. -Таганрог: изд-во ТРТУ, 2000; стр.49-51.

92. Курейчик В.М. Генетические алгоритмы: Монография. Таганрог: изд-во ТРТУ, 1998.

93. В.В. Курейчик. Эволюционные методы решения оптимизационных задач. Таганрог, 1999, ТРТУ.

94. Bentley P., "An Introduction to evolutionary design by computers", In Evolutionary design by computers, Morgan Kaufmann, 1999.

95. Змитрович А. И. Интеллектуальные информационные системы — Минск: Тетрасистемс, 1997, — 368 с.

96. Скурихин А.Н. Генетические алгоритмы / Новости искусственного интеллекта, 1995, №4, с. 6-46.101. http://www.ux.his.no/~tranden/brodatz.html

97. Kolesnik, М., Fexa, A. Segmentation of Wounds in the Combined Color-Texture Feature Space. Proceedings of SPIE: Medical Imaging 2004, San-Diego, USA.

98. Y. Linde, A. Buzo, and R. M. Gray. An Algorithm for Vector Quantizer Design. IEEE Transactions on Communications, 1980.

99. Marina Kolesnik, Alexander Barlit, Evgeny Zubkov Simple Cell Interaction for Iterative Contrast Detection. ICAIS'02

100. Kolesnik, M., Barlit, A. Iterative orientation Tuning in VI: a Simple Cell Circuit with Cross-Orientation Suppression. Proceedings of the Scandinavian Conference on Image Analysis (SCIA'2003).

101. Kolesnik, M., Barlit, A. Iterative Orientation Tuning of Simple Cells in VI: A Comparative Study of Two Computational Models for Contrast Detection in Images.

102. Proceedings of the AISB'03 Symposium on Biologically-Inspired Machine Vision,

103. Theory and Application. Aberystwyth, UK, 7-11 April 2003

104. Барлит А.В., Нужнов E.B. Решение задачи трехмерной упаковки с помощью чу параллельного генетического алгоритма. Труды Международных конференций

105. Искусственные интеллектуальные системы» (IEEE ICAIS'02) и «Интеллектуальные САПР» (CAD-2002). Научное издание. Москва: Физматлит, 2002.

106. V Издательство Физико-математической литературы, 2003. ISBN 5-9221-0447-0.

107. Kass M., Witkin A. and Terzopolous D. Snakes: Active contour models II Int. J. Comput. Vision, 1988.

108. Miller J.V., Breen D. E. and Wozny M.J. Extracting geometric models through ^ constraint minimization // Rensselaer Polytechnic Institute, Tech. Rep. № 90024,1990.

109. Terzopolous D., Piatt J., Barr A. Elastically deformable models // Comput. Graphics, vol. 21, №4, 1987

110. Барлит A.B., Нужнов E.B. Параллельный генетический алгоритм трехмерной упаковки объектов. Интеллектуальные системы. Коллективная монография. -М.: Физматлит, 2005, с.257-264.