Содержание к диссертации
Введение
Глава 1. Обзор методов решения задачи классификации графической информации 15
1.1 Методы классификации графической информации 15
1.2 Постановка задачи классификации графической информации 27
1.3. Методы получения, обработки и хранения экспертной информации, методы
1.3.1. Искусственные нейронные сети 35
1.3.2. Машины векторной поддержки 46
1.3.3. Анализ генетических методов '. 50
1.4. Выводы 59
Глава 2. Структурно-параметрический синтез системы классификации графических объектов 61
2.1. Формирование исходного набора признаков графического объекта 62
2.2. Разработка алгоритма параметрического синтеза системы 86
2.2.1. Принципы кодирования и декодирования хромосом 89
2.2.2. Формирование начальной популяции 90
2.2.3. Модифицированные генетические операторы 93
2.3. Анализ эффективности алгоритма параметрического синтеза 97
2.4. Выводы 98
Глава 3. Разработка математического обеспечения системы классификации графических объекто в 99
3.1. Разработка системы классификации изображений 100
3.1.1. Разработка машины векторной поддержки 100
3.1.2. Алгоритм параметрического синтеза машин векторной поддержки 115
3.2. Построение алгоритмов улучшения качества решения 118
3.2.1. Алгоритм активного контура 119
3.2.2. Детектор границ объектов 130
3.3. Выводы 139
Глава 4. Программная реализация и ее экспериментальные исследования 141
4.1. Архитектура программной системы классификации графических объектов 141
4.2. Цель экспериментальных исследований 143
4.3. Исследование эффективности программы параметрического синтеза 143
4.4. Исследование эффективности алгоритма обучения и классификации 146
4.5. Исследование эффективности алгоритма обнаружения контуров в изображении 150
4.5. Исследование эффективности алгоритма активного контура 152
4.6. Область применения предложенной системы классификации 156
4.7. Выводы и рекомендации ; 157
Заключение 158
Литература 160
- Методы классификации графической информации
- Формирование исходного набора признаков графического объекта
- Разработка системы классификации изображений
- Архитектура программной системы классификации графических объектов
Введение к работе
Интеллектуальная поддержка при классификации графической информации является актуальной задачей, решение которой может существенно облегчить многие рутинные операции в областях, использующих компьютерное зрение. Компьютерное зрение (Computer Vision) является одним из самых востребованных направлений современной информатики и имеет множество применений. Примеры можно найти в областях, начиная с обработки медицинских изображений, цель которой идентификация и диагностика, до анализа изображений и их реконструкции в астрономии. Практические приложения ограничиваются не только обработкой отдельных изображений, так как с развитием компьютерных технологий стала возможной реконструкция трехмерной структуры объектов по наборам их фотографий, снятых с различных ракурсов, а так же обработка видео потоков. В области робототехники оптическая составляющая сенсорной обратной связи становится доминирующей. Любая область, где присутствие человека может быть заменено автоматикой, является хорошим приложением для компьютерной обработки изображений. С увеличением количества областей применения компьютерного зрения, как в микромире, например, электронные микроскопы, так и в макромире, как астрономия, стоит ожидать увеличения потребности в электронных оптических средствах, поэтому решение проблем в этой области становится все более актуальной и востребованной задачей.
В данной диссертационной работе рассматривается разработка и исследование системы интеллектуальной поддержки при калассификации графической информации с предварительным обучением на основе экспертных данных. Данная проблема сведена к алгоритму сегментации изображений - т.е. разделению всего массива данных на некоторые классы, заданные пользователем, признаки которых система определяет самостоятельно. Для параметрического синтеза системы использован генетический алгоритм. Его
задача заключается в нахождении оптимального информативного набора признаков подклассов изображения. Для улучшения качества решения произведен теоретико-информационный анализ системы низкоуровневой обработки изображений у млекопитающих некоторых физико-биологических процессов.
Большое количество исследователей в настоящее время работают над узкоспециализированными областями, ограничиваясь лишь одним методом решения [23-25]. Данная исследовательская область считалась до недавнего времени трудоемкой, малоизученной и рассматривала только черно-белые изображения. Это связано в первую очередь с трудностью определения целевой функции (как правило, в роли нее выступает мнение эксперта по поводу решения) и значительное время обработки изображения. Так же затруднительна разработка универсальных подходов и подбор параметров для изображений различных классов и типов. Рост областей применения компьютерного зрения и их количества становятся причиной для разработки новых подходов в решении задач автоматизированной обработке изображений. В данный момент появляются интеллектуальные и проблемно-ориентированные подходы, использующие численные методы для большей эффективности обработки, что позволяет в некоторых случаях получать решения удовлетворительного качества даже в режиме реального времени. Конечной целью любой задачи компьютерного зрения является уменьшение участия человека в процессе обработки изображений до контроля полученных результатов.
Большинство задач компьютерного зрения не являются NP-полными, но проверка целевой функции при определенном наборе параметров представляет собой линейную вычислительную задачу, на решение которой требуется значительное время, которое, как правило, зависит только от аппаратного обеспечения и не может быть сокращено за счет оптимизации.
Нетривиальность задачи сегментации изображений обуславливает важность модуля параметрического синтеза системы, оптимизированного для
работы с большими массивами данных и большими вычислительными затратами.
Имеющиеся сейчас системы компьютерного зрения уже позволяют автоматически работать над изображениями, привлекая человека лишь для коррекции результатов. Одной из главных проблем, стоящих на пути дальнейшего их улучшения является большое количество параметров для оптимизации. Для разрешения этой задачи используют самообучающиеся системы, нейронные сети, численные методы, позволяющие оперировать областями с большим количеством переменных и многокритериальностью. Среди оптимизационных аппаратов особо выделяются эволюционные модели.
Эволюционные алгоритмы становятся все более популярными среди исследователей, что подтверждается более чем 2000 ежегодно публикуемыми статьями по этой теме [26]. Они представляют собой упрощенное моделирование процесса эволюции в природе, т.е. механизмов селекции и генетики. Одним из их главных преимуществ является способность выходить из локальных максимумов и находить нестандартные решения [27-29].
Как было отмечено выше, задачи компьютерного зрения мало формализованы, имеют большое количество параметров, изменение которых может привести к неожиданному результату. В ходе решения таких многопараметрических задач нельзя сформулировать четкие причинно-следственные правила. Для решения всех перечисленных проблем наиболее адоптированными являются, опять же, эволюционные алгоритмы, принадлежащие к классу случайно-направленных и находящих близкое к оптимальному, или эффективное решение. При применении такого рода алгоритмов для плохо структурированных задач требуется привлечение экспертов для каждой узкой области рассматриваемой тематики, а так же поставленной задачи в общем.
Одной из разновидностей эволюционных алгоритмов являются генетические алгоритмы. Они имеют два ключевых отличия. Во-первых, они
оперируют пространством поиска (популяцией), используя генетические операторы на частные решения (хромосомы). Во-вторых, что уникально для генетических алгоритмов, они используют оператор рекомбинации применительно к частным решениям. Новые решения формируются путем создания и добавления к имеющимся решениям нового генетического материала (строительных блоков), что аналогично процессу генной инженерии - формированию новых видов и программирование их свойств, таких как устойчивость к болезням, путем включения в цепочки ДНК новых фрагментов. В этом состоит одно из отличий генной инженерии, и, соответственно, алгоритмов на ее основе, от естественной селекции, в которой потомки могут формироваться лишь на основе имеющегося генетического материала, за исключением редких случаев мутации.
Задача сегментации изображений является фундаментальной проблемой компьютерного зрения и обработки изображений. Кластеризация так же является одним из первых шагов любой задачи анализа изображений. Системы распознавания графической информации, такие как идентификация человеческого лица или некоего объекта, часто предполагают, что исходный образ уже сегментирован.
В общем случае процесс сегментации (кластеризации) сводится к созданию комплекса проблемно-ориентированных программ, последовательно выполняющих составные этапы разработанного алгоритма. Разработка структуры программного комплекса и его составных частей производится по следующей последовательности. В первую очередь находится набор уникальных признаков подклассов изображения, а затем производится разделение на заданное количество кластеров. Этот этап оказывает на конечный результат и время его получения наибольший эффект. Многие признаки могут быть взаимозависимыми, т.е. избыточными. Увеличение количества признаков значительно увеличивает время получения решения. Обычно эта задача решается путем перебора возможных вариантов либо
упрощенным моделированием поведения системы при наличии тех или иных признаков кластеров. Второй подход заключается в априорной экспертной оценке каждой рассматриваемой характеристики графической последовательности.
Разнообразие признаков классов увеличивает качество решения [30]. Чаще всего исследователи рассматривают функциональные характеристики изображений, такие как кривые цветовых и интенсивной составляющих, текстуры и направление градиента.
Так как задача сегментации изображений является комплексной, исследователю необходимо решить как минимум две задачи - выбор признаков и метод их классификации. Наиболее эффективным решением первой задачи является интегральный подход, сочетающий в себе преимущества априорной оценки отличительных признаков и интеллектуальный перебор возможных решений. Целью интегрального подхода является полное исключение участия человека в обработке изображения. Достичь такой эффективности возможно комбинацией различных объектно-ориентированных модулей в единый комплекс. Вторая задача является по своей сути проблемой получения, анализа и обработки экспертной информации. Ее решению уделена значительная часть данной диссертационной работы.
Одним из методов повышения качества решения является применение гибридных подходов, в которых к полученному решению применяются различные алгоритмы, уменьшающие общую погрешность решения.
Из всех органов чувств человека зрение является наиболее важным -около 90% информации мы получаем именно посредством его. Наше поведение напрямую зависит от интерпретации того, что мы видим. Относительно недавно начавшиеся исследования проблем зрительного восприятия направлены на понимание общих проблем обработки оптической информации визуальной системой человека. Совокупность задачи автоматизации обработки изображения и разработка специализированной аппаратуры и алгоритмов, в
какой-то степени моделирующих зрительную систему млекопитающих, становится сейчас все более популярной [1-5]. Поэтому для улучшения полученного решения наиболее перспективным подходом является численное моделирование зрительных систем млекопитающих.
Решение проблемы сегментации изображений в диссертационной работе рассматривается как линейная система, состоящая из комплекса проблемно-ориентированных программ, в которой выход одного модуля служит входом для следующего. Каждая составная часть системы является отдельной программой, которые объединяет только целостность представления данных.
Недостатком использования последовательного подбора необходимых признаков является значительное время проверки целевой функции каждого частного решения и трудность распараллеливания выполнения программы. Но данный этап работы системы проводится лишь один раз, и при дальнейшем обучении системы для тренировочного набора данных и при сегментации используются только оптимально-полезные признаки. Этот этап является определяющим для качества решения и времени его получения.
В диссертации на этапе формирования решения используются, подтвердившие на практике эффективность своего применения, алгоритмы численного моделирования естественных систем, таких как визуальные и физические. Применение такой стратегии позволяет повысить скорость получения решения и его качество при низкой скорости работы стадии подбора параметров и обучения системы.
Целью диссертационной работы является разработка и исследование комплекса проблемно-ориентированных алгоритмов по интеллектуальной поддержке при классификации графической информации.
В ходе работы над диссертацией решены следующие задачи: Исследование возможности построение системы классификации изображений в виде последовательно-связанных модулей.
Разработка и исследование алгоритмов параметрического синтеза для компонентов системы сегментации.
Исследование разносторонних характеристик графической информации и их информативности для различных классов изображений с целью ускорения работы генетического алгоритма по их подбору. Создание базы признаков классификации и эффективной области изменения их параметров.
Разработка методов кодирования решения, а так же его хранения и трансформации при работе генетического алгоритма.
Построение программного модуля эволюционной оптимизации составляющих обучающего набора.
Разработка и исследование метода получения, анализа и обработки экспертной информации в виде векторов гиперпространства.
Построение и исследование системы обнаружения контуров в изображениях на основе теоретического анализа естественных зрительных систем.
Исследование проблемы и разработка алгоритма активных контуров, используя теоретико-множественный анализ естественных природных систем.
Разработка комплекса соответствующих проблемно-ориентированных программ и исследование его эффективности.
Методы исследования основаны на теории алгоритмов, элементов теории множеств, теории обработки экспертной информации, параметрического синтеза сложных систем, теоретико-множественном и теоретико-информационном анализе естественных систем, элементах теории эволюционного моделирования.
Методы решения опираются на теорию классификации сложных систем, параметрического синтеза, получения, обработки и анализа экспертной
информации, многоуровневых иерархических систем, эволюционных алгоритмов, методов кластеризации математических пространств.
Научная новизна диссертационной работы заключается в следующем:
Разработан метод интеллектуальной поддержки при решении задачи классификации графической информации с помощью системы взаимодействующих проблемно-ориентированных программ.
Построен алгоритм параметрического анализа пространства признаков изображений с их предварительным отбором на основании эмпирических оценок с использованием эволюционного подхода. Созданы проблемно-ориентированные генетические операторы.
Разработан метод классификации векторов в многомерном пространстве признаков с использованием аппарата машин опорных векторов.
Разработана итеративная модель функционирования зрительной системы млекопитающих для выявления контуров цветных изображений.
Предложен новый подход анализа и обработки экспертной информации с отображением ее в многомерное пространство признаков изображений. В качестве основы взяты машины векторной поддержки.
Создан алгоритм активного контура для улучшения решения, использующего принципы естественных биологических и физических систем.
Практическая ценность. Разработанная система проблемно-
ориентированных программ позволяет осуществлять автоматизированную интеллектуальную поддержку при классификации графической информации на принадлежность одному из заданных пользователем классов. Проведенный теоретико-множественный и теоретико-информационный анализ признаков изображений и естественных систем позволил значительно улучшить качество
решения. Предложенный комплекс алгоритмов выполняет полностью автоматизированную сегментацию графических данных.
Одним из возможных применений системы классификации являются медицинские изображения. Применительно к этой области был построен аппаратно-программный комплекс, используемый во врачебной практике в университетском госпитале Штутгарта. Программная часть разработана под операционную систему Windows, написана на языке C++. Компиляция проведена в среде объектно-ориентированного программирования Microsoft Visual C++. Предложенные методы позволяют достигнуть улучшенных показателей автоматизированной сегментации изображений.
Реализация результатов работы. Основные практические и теоретические результаты диссертационной работы использованы в научных исследованиях по гранду Фраунгоферовского общества (Германия) в Институте информационных коммуникаций, г. Сант-Августин, Германия, а так же в промышелнном проекте «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 страниц приложений.
СОДЕРЖАНИЕ РАБОТЫ.
ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, поставлена цель работы, дано общее ее описание.
В ПЕРВОЙ главе приведена постановка задачи интеллектуальной
поддержки при классификации графической информации.. Рассмотрены
^ основные алгоритмы решения задачи классификации графической информации,
обработки экспертной информации в многомерном пространстве признаков. Выявлены их недостатки и достоинства. Описаны методы параметрического синтеза на примере генетического поиска, генетические операторы, их основные отличия от других оптимизационных методов. Указаны взятые за основу методы и модели, используемые в данной работе.
ВО ВТОРОЙ ГЛАВЕ произведены анализ проблем, возникающих при классификации графической информации. Приведена постановка задачи параметрического синтеза системы формирования вектора признаков изображения. Выполнен анализ наиболее распространенных признаков для кластеризации изображений, предложен набор новых признаков. Сделаны выводы по использованию различных характеристик графической информации
для выборки информативных и отличительных ее составляющих. Приведена структура и принципы представления информации для работы генетического алгоритма параметрического синтеза набора характеристик экспертной информации в виде составления списка признаков изображения. Разработан алгоритм построения начальной популяции и методы кодирования решений. Предложены генетические операторы для модифицированного генетического алгоритма, целевая функция качества решений с учетом специфики рассматриваемой задачи. Произведена теоретическая оценка алгоритма параметрического синтеза для классификации графической информации.
В ТРЕТЬЕЙ ГЛАВЕ поставлена задача получения, обработки и использования экспертной информации. Рассмотрена схема системы обучения классификационной программы. Разработано специальное математическое обеспечение для представления обучающей экспертной информации и ее сохранения. Описана структура алгоритма обучения системы и дальнейшей классификации входной информации. Исследована разработанное математическое программное обеспечение системы обработки экспертной информации и классификации пикселей изображения на ее основе. Разработан алгоритм параметрического синтеза ядра системы классификации. Сделан вывод о преимуществах и недостатках использования предложенного математического аппарата, а так же его теоретический сравнительный анализ с имеющимися аналогами.
Разработаны методы повышения качества решения. Построено математическое обеспечение обработки графической информации, моделирующее функционирования зрительной системы млекопитающих на низком уровне. Приведен ее детальный алгоритм. Доказана высокая эффективность нахождения границ в изображениях с ее помощью. Разработан алгоритм активного контура, использующий теоретико-информационный анализ поведения естественных систем организмов. Выбраны комплексные
критерии оценки качества решения с учетом как количества неправильно идентифицированных пикселей, так и времени получения решения.
В ЧЕТВЕРТОЙ ГЛАВЕ описана программная реализация и произведены экспериментальные исследования предложенного комплекса программ интеллектуальной поддержке в принятии решений при сегментации изображений на примере медицинских систем. Приведены результаты работы алгоритма параметрического синтеза системы с помощью генетического алгоритма по нахождению информативных признаков различных классов графических данных. Произведены экспериментальные исследования по сегментации изображений, используя признаки, найденные алгоритмом параметрического синтеза. Приведены результаты тестирования математического обеспечения модели зрительной системы млекопитающих, описанной в третьей главе, на естественных изображениях. Произведена экспериментальная оценка системы получения, обработки и использования экспертной информации, описанной во второй главе. Разработан план тестирования системы в целом. Подтверждена высокая эффективность как системы программ, так и ее отдельных компонентов. Произведено описание программного обеспечения по интеллектуальной поддержке при сегментации изображений.
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.
В ПРИЛОЖЕНИИ приведены акты об использовании результатов работы.
Методы классификации графической информации
Классификация графической информации, или сегментация изображений имеет богатую историю в контексте исследований в области обработки изображений. Было предложено много различных подходов, использующих различные признаки изображений, такие как яркость, цветность и текстуры. Существует аспект, делающий задачу сегментации изображений не совсем корректной - это то, что такое приложение будет всегда зависимым от конкретной сферы применения. Для натуральных изображений хорошо себя зарекомендовала комбинация интенсивности, цвета и текстуры. Для других сфер применения, таких как фотографии рукотворных объектов, чаще всего используют только интенсивность пикселей.
Существующие методы сегментации могут быть классифицированы как основанные на областях и на границах объектов. Примером граничной сегментации может служить метод, проводящий границу объекта через самые ярко выраженные из найденных границ. В качестве примера региональной сегментации может служить метод, разделяющий входную информацию на регионы, в которых минимизирована дисперсия. Любой участок изображения можно охарактеризовать комбинацией признаков, выделенных из двух основных классов - интенсивности или цвета и текстуры рассматриваемого региона. Соответственно, какой бы классификатор не использовался в системе, он основывается на этой комбинации признаков в многомерном признаковом пространстве.
Обнаружение границ. Начало исследований в области обнаружения границ изображений относится к семидесятым года двадцатого века. При рассмотрении решения такого типа можно найти следующие общие характеристики: границы, обычно, непоследовательны и сегментация изображений на их основе весьма затруднительна. Ранние методы находили контура объектов с помощью выделения максимума градиента на изображении [32]. Процесс представляет собой установление пересечения с нулевой координатой лапласиана оператора Гаусса (LOG). Далее, в 80-х данная техника привлекла интерес исследователей для анализа изображений с определенным набором степеней увеличения. При этом даже если замкнутые контура и были выделены, то все равно, оператор LOG является очень чувствительным к наличию шума в изображении. Канни [33] показал, что LOG имеет низкое отношение сигнал/шум и слабо локализован. Он получил оптимальный линейный фильтр для обнаружения резких границ даже при наличии белого шума. Под термином оптимальный понимается положение границ, их высокое разрешение, работа за один проход. Результирующий фильтр очень схож с первой производной оператора Гаусса. Детектор границ Канни до сих пор широко используется, и почти в каждой работе по обнаружению границ результаты сравниваются именно с ним. Основная идея этих подходов заключается в создании скалярной функции, определяющей величину границы и ее ориентацию для каждого пикселя. Сами же границы определяются путем применения минимаксного подхода и пороговой классификацией функции границ.
Следующий метод, заслуживающий внимания создал Харалик [34]. В нем производится подборка линейной комбинации дискретного базиса полинома Чебышевского и вычисление первой и второй направленной производной операторов Гаусса и Канни.
Работа Канни основана на разработке линейного фильтра для резких границ. С тех пор было предпринято много попыток создания нелинейных фильтров, работающих лучше линейных. Один из таких подходов использует квадратуру пар четных и нечетных фильтров [35, 36]. Перона и Малик [36] показали, что использование второй производной оператора Гаусса с ориентацией в нескольких направлениях идентично фильтрам четной симметрии и трансформация Гильберта идентична фильтрам нечетной симметрии, и они могут находить границы объектов и линии. Это является главным отличием от алгоритма Кании, способного находить только границы объектов (ступени в уровни яркости) и на выходе фильтров нет реакции на постоянный градиент (например, перепад освещения). Другой нелинейный детектор границ называется SUSAN [37]. В этой работе центральная точка окружности сопоставляется всем точкам окружности. Значение общего соответствия минимизируется в точках, лежащих на границах и в углах. Преимущество этого метода заключается в отказе от использования оператора производной, что уменьшает чувствительность к шуму. Другой интересный нелинейный детектор создан Ницбергом [38]. Он основан на вычислении матрицы 2x2 N(x, d)=Ga (Vl-Vf). Характеристическое число этой матрицы дает максимум и минимум изменения яркости. Этот тип детекторов был широко использован для обнаружения углов [39]. Так же он эффективен для выделения текстур. В последнее время предложены нелинейные детекторы, основанные на гистограммах или распределениях [40, 41], хорошо работающие с цветными изображениями и текстурами. Окружение точки имеет форму круга и при анализе изображения одна половина круга сравнивается с другой на наличие изменения распределения признаков. Другие нелинейные детекторы включают технику анизотропной диффузии и будут рассмотрены позже.
Многие работы посвящены улучшению детекторов границ. Один из таких подходов [42] использует кривые характеристики оперирующего ресивера (ROC) для эволюции относительного превосходства восьми линейных и нелинейных детекторов границ, включая Канни и SUSAN. Кривые ROC показывают зависимость процента неверно распознанных границ от процента нераспознанных контуров. Эволюция нелинейных детекторов, основанных на анизотропии, рассмотрена в [43].
Формирование исходного набора признаков графического объекта
Как показал анализ исследований в области выявления признаков областей изображений, при решении проблемы автоматической сегментации нельзя ограничиваться только одним типом признаков. Необходимо принимать во внимание как яркостные характеристики отдельных пикселей, так и различные функции их распределения в рассматриваемой области, включая текстуры. В данном разделе производится изучение различных характеристик изображения, которые могут помочь идентифицировать класс области, которой они принадлежат.
Квантование цветов. Данная задача подробно рассмотрена в [1]. Процесс квантования цветов состоит из двух шагов: определение палитры цвета (обычно от 8 до 256) и согласование цвета пикселя с имеющимися в палитре цветами. С точки зрения распознавания образов, квантование цветов может быть рассмотрено как автоматическая классификация обычно трехмерного цветового пространства, каждый класс которого, представляется одним цветом палитры. Так как цветное изображение в системе RGB может содержать до 25б3 оттенков цветов, то в проблеме классификации вовлекается большое количество результатов обработки пикселей в пространстве малой размерности. Существует несколько методов решения этой задачи. Сначала цветовое пространство делится на непересекающиеся области путем последовательного разбиения. Затем для каждой выбранной области выбирается цвет, который заносится в цветовую палитру. Два наиболее часто применимые алгортима этого класса - алгоритм разреза посередине (МСА) [2]
и алгоритм на основе дисперсии (VBA) [3]. Существуют так же алгоритмы этого класса на основе визуальной системы человека (например [4]). В общем, данный класс алгоритмов имеет низкую временную сложность. Другой класс методов квантования пользует за основу цветовое пространство и кластеры представляют собой цвета палитры. Наиболее известный алгоритм этого класса- «Алгоритм цветовой кластеризации» (СМА) [5]. В нем происходят итерационное присваивание цветов кластеров и классификация пикселей.
Вышеупомянутые алгоритмы кластеризации обычно рассматриваются как оптимальные в своей области, но основным их недостатком является трудоемкость. Кроме того, хотя решение и удовлетворительно, оно зависит от начальных условий. В большинстве случаев такие условия известны или могут быть получены посредством их унификации, но при некорректном параметре или при необычном изображении результат работы алгоритма получается крайне неудовлетворительным. Данный эффект наблюдается при обработке черно-белого изображения с помощью СМА. Выход из этой проблемы -применение генетических алгоритмов. Один из примеров такого подхода можно найти
Текстура изображения. Наиболее полной характеристикой как черно белого, так и цветного изображения является его текстура. Точного определения термина «текстура» не существует. Примитивная текстура, текстурный элемент, тексель, - все эти понятия обозначают нечто, состоящее из взаимосвязанных элементов. Вид текстуры сильно зависит от масштаба. При разном увеличении текстура должна быть узнаваема, например, на рис. 2.1 фотографии dOOl, d006, d014 изображают одно и тоже. В зависимости от этого текстуры делятся на тонкие, грубые, размытые, (ii гранулированные и т.д. Тон текстуры - основывается на свойствах отдельных пикселей в примитивах. Структура текстуры обозначает пространственные отношения между примитивами.
Описание текстуры включает: пиксели - их местонахождение и тональность, примитивная структура - смежный набор пикселей с некоторыми тональными и/или региональными свойствами (средняя интенсивность, максимум или минимум интенсивности, размеры, форма), пространственные отношения примитивов (случайные, парно зависимые, некоторые примитивы могут быть обоюдно зависимы), текстура изображений (число и тип примитивов, пространственные отношения примитивов).
На основе анализа литературы можно выделить следующие типы структур: тон текстуры и ее структура — зависимые величины. тонкая (четкая) структура - примитивы структуры в изображении малы и разница в тональности между соседними примитивами значительна. грубая структура - примитивы структуры достаточно велики. слабо выраженная (слабая) структура - между примитивами наблюдается лишь небольшое пространственное взаимодействие. четко выраженная (сильная) структура - пространственные взаимодействия между примитивами регулярны. постоянная текстура - характеризуется постоянством, медленным изменением или некоторой периодичностью.
Для описания текстуры с целью ее дальнейшего распознавания необходимо выработать соответствующие подходы. Существует три основных направления в описании текстур: 1. статистический - размер примитивов текстур соизмерим с размерами пикселя. 2. синтаксический - примитивы могут быть описаны используя больший набор свойств, чем лишь свойства тональности. 3. гибридный - комбинация первого и второго подходов.
Разработка системы классификации изображений
Как показал анализ исследований в области выявления признаков областей изображений, при решении проблемы автоматической сегментации нельзя ограничиваться только одним типом признаков. Необходимо принимать во внимание как яркостные характеристики отдельных пикселей, так и различные функции их распределения в рассматриваемой области, включая текстуры. В данном разделе производится изучение различных характеристик изображения, которые могут помочь идентифицировать класс области, которой они принадлежат.
Квантование цветов. Данная задача подробно рассмотрена в [1]. Процесс квантования цветов состоит из двух шагов: определение палитры цвета (обычно от 8 до 256) и согласование цвета пикселя с имеющимися в палитре цветами. С точки зрения распознавания образов, квантование цветов может быть рассмотрено как автоматическая классификация обычно трехмерного цветового пространства, каждый класс которого, представляется одним цветом палитры. Так как цветное изображение в системе RGB может содержать до 25б3 оттенков цветов, то в проблеме классификации вовлекается большое количество результатов обработки пикселей в пространстве малой размерности. Существует несколько методов решения этой задачи. Сначала цветовое пространство делится на непересекающиеся области путем последовательного разбиения. Затем для каждой выбранной области выбирается цвет, который заносится в цветовую палитру. Два наиболее часто применимые алгортима этого класса - алгоритм разреза посередине (МСА) [2] и алгоритм на основе дисперсии (VBA) [3]. Существуют так же алгоритмы этого класса на основе визуальной системы человека (например [4]). В общем, данный класс алгоритмов имеет низкую временную сложность. Другой класс методов квантования пользует за основу цветовое пространство и кластеры представляют собой цвета палитры. Наиболее известный алгоритм этого класса- «Алгоритм цветовой кластеризации» (СМА) [5]. В нем происходят итерационное присваивание цветов кластеров и классификация пикселей.
Вышеупомянутые алгоритмы кластеризации обычно рассматриваются как оптимальные в своей области, но основным их недостатком является трудоемкость. Кроме того, хотя решение и удовлетворительно, оно зависит от начальных условий. В большинстве случаев такие условия известны или могут быть получены посредством их унификации, но при некорректном параметре или при необычном изображении результат работы алгоритма получается крайне неудовлетворительным. Данный эффект наблюдается при обработке черно-белого изображения с помощью СМА. Выход из этой проблемы -применение генетических алгоритмов. Один из примеров такого подхода можно найти в [6].
Текстура изображения. Наиболее полной характеристикой как черно белого, так и цветного изображения является его текстура. Точного определения термина «текстура» не существует. Примитивная текстура, текстурный элемент, тексель, - все эти понятия обозначают нечто, состоящее из взаимосвязанных элементов. Вид текстуры сильно зависит от масштаба. При разном увеличении текстура должна быть узнаваема, например, на рис. 2.1 фотографии dOOl, d006, d014 изображают одно и тоже. В зависимости от этого текстуры делятся на тонкие, грубые, размытые, (ii гранулированные и т.д. Тон текстуры - основывается на свойствах отдельных пикселей в примитивах. Структура текстуры обозначает пространственные отношения между примитивами.
Описание текстуры включает: пиксели - их местонахождение и тональность, примитивная структура - смежный набор пикселей с некоторыми тональными и/или региональными свойствами (средняя интенсивность, максимум или минимум интенсивности, размеры, форма), пространственные отношения примитивов (случайные, парно зависимые, некоторые примитивы могут быть обоюдно зависимы), текстура изображений (число и тип примитивов, пространственные отношения примитивов).
На основе анализа литературы можно выделить следующие типы структур: тон текстуры и ее структура — зависимые величины. тонкая (четкая) структура - примитивы структуры в изображении малы и разница в тональности между соседними примитивами значительна. грубая структура - примитивы структуры достаточно велики. слабо выраженная (слабая) структура - между примитивами наблюдается лишь небольшое пространственное взаимодействие. четко выраженная (сильная) структура - пространственные взаимодействия между примитивами регулярны. постоянная текстура - характеризуется постоянством, медленным изменением или некоторой периодичностью.
Для описания текстуры с целью ее дальнейшего распознавания необходимо выработать соответствующие подходы. Существует три основных направления в описании текстур: 1. статистический - размер примитивов текстур соизмерим с размерами пикселя. 2. синтаксический - примитивы могут быть описаны используя больший набор свойств, чем лишь свойства тональности. 3. гибридный - комбинация первого и второго подходов.
Архитектура программной системы классификации графических объектов
При обзоре методов классификации в многомерном пространстве был рассмотрен метод построения оптимальной разделяющей гиперплоскости. В качестве инструмента для решения поставленной задачи были выбраны машины векторной поддержки. Они формируют расширение стандартного метода построения оптимальной разделяющей гиперплоскости. Машины векторной поддержки отображают входное пространство признаков в пространство большей размерности посредством некоторого нелинейного преобразования с выбранным приоритетом. Затем строится оптимальная разделяющая гиперплоскость в пространстве признаков. Это делает возможным построение линейных плоскостей в пространстве признаков с соответствием им нелинейных решающих плоскостей во входном пространстве.
Возьмем пример из введения, добавив в него одну дополнительную точку (рис. 3.1). Очевидно, что не может быть найдено ни одной разделяющей линейной гиперплоскости, за исключением случая, когда возможно использование нелинейных гиперплоскостей, что соответствует проецированию в пространство большей размерности. В данном случае разделение возможно (рис. 3.2).
Основная проблема, возникающая при этом — как осуществить проецирование всех векторов в пространство признаков. Эта операция проецирования должна генерировать вектора с высокой размерностью, занимая при этом минимум аппаратных ресурсов и имея приемлемую вычислительную стоимость. Проблема размерности не является сложной для разрешения, так как все, что нам необходимо - скалярное произведение векторов в пространстве признаков. Если мы выберем проецирование из входного пространства X в пространство высокой размерности Z, то функцию проецирование можно обозначить следующим образом (к: Х- Т)\
Пусть мы имеем квадрат в двумерном пространстве, определяющий область положения наших данных - изображения: [-1,1] х [-1,1] eR . Нарис. 3.3 показан вид этого квадрата после проецирования. Двумерное изображение может существовать в пространствах очень высокой размерности, но это будет всегда лишь искаженная плоскость.
Следующий вопрос, который необходимо рассмотреть - кернфункции. В зависимости от используемой кернфункции, получаются различные типы машин векторной поддержки: Нахождение подходящей кернфункции является наиболее проблематичной частью использования машин векторной поддержки. Рассмотрим случаи, когда построение разделяющих плоскостей невозможно. Данные случаи могут быть обработаны, так же как и обычные,
Так как это приводит к сложной процедуре оптимизации, необходимо найти более простой подход. Если вместо процедуры минимизации функционала (3.7) при соответствующих ограничениях минимизировать функцию (3.10) для заданного значения С и при ограничениях (3.8), то сложность вычислений значительно уменьшиться.
Рассмотрим семейство классификаторов (т.е. набор функций Ф в пространстве Rd) которое мы назовем «устойчивые к провалам классификаторы». Отдельно взятый классификатор ф є Ф определен положением и радиусом шара в Rd и двумя гиперплоскостями с параллельными нормалями. Назовем набор точек, лежащих между плоскостями, но не на них, «граничный набор». Функции решения ф определены как делящие точки, лежащие внутри шара, но не в граничном наборе на два класса {-1,+1} в зависимости от того, по какую сторону от граничного набора они находятся. Все остальные точки просто определены как «правильные» - это значит, что они не были приписаны никакому классу и не обладают никаким риском. Ситуация для двумерного случая обобщена на рис. 3.4. Эта, предпочтительно нечетная, семья классификаторов, вместе с условиями, как они были обучены, будет формировать систему, очень схожую с машинами векторной поддержки, и для которых может быть продемонстрирована структура минимизации риска. Обозначим диметр шара D и дистанцию между двумя гиперплоскостями М. Введем понятие VC измерения. В данном случае оно обозначает максимальное количество точек, которые могут быть разделены по семействам, т.е. классам.
Очевидно, что мы не можем контролировать VC семьи этих классов, контролируя минимальную границу М и максимальный диаметр D, которые являются частью семейство. Поэтому нам необходимо основываться на некотором предположении. Для примера, рассмотрим семейство классификаторов граничного набора в двумерном пространстве с диаметром D = 2, показанное на рис. 3.4. Классификаторы, граница которых удовлетворяет неравенству М 3/2 могут разграничить три точки; если 3/2 М 2, то они могут классифицировать две точки; если М больше или равно двум, то они могут классифицировать только одну точку. Каждое из этих трех семейств соответствует одному из наборов классификаторов на рис. 3.5, но только степень включения равна трем.
Эти идеи могут быть использованы для того, чтобы показать, как граничные наборы реализуют минимизацию риска. Расширением вышеприведенного примера для пространств произвольной размерности заключены в теореме Вапника [18].
Теорема. Для данных в пространстве R , значение VC - h граничных наборов минимального значения М и максимального диаметра D ограничено сверху следующим выражением: min {[L?mJ Г? minl, d}+l
Для доказательства мы выведем следующую лемму, которую Вапник доказал для следования симметричности аргументов:
Лемма. Рассмотрим n d + 1 точек, лежащих в шаре В є Rd. Пусть точки будут разделены граничным набором с границей М. Тогда для того, чтобы максимизировать М, точки должны лежать в вершинах (п-1) размерного симплекса, и должны так же лежать на поверхности шара. Доказательство. Нам необходимо рассмотреть только случай когда количество точек п удовлетворяет n d + \ (большее количество точек будут неделимы, так как VC ориентированных гиперплоскостей в Rd равно d+1, и любое распределение точек, которое может быть разделено на классы граничным набором, могут быть так же разделены гиперплоскостями; это так же выражается неравенством h d + \). Снова рассмотрим точки на сфере диаметром D, где сфера сама по себе имеет размерность d-2 и воспользуемся выводами статьи [20]. Если п четное, мы можем найти распределение п точек, которые могут быть разделены граничным набором, если и тах/М „,м=п - 1.
