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

Размещено на http://www.allbest.ru/

1

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

Специальности: 05.11.07 - Оптические и оптико-электронные приборы и комплексы 05.13.01 - Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ диссертации на соискание ученой степени

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

Потапов Алексей Сергеевич

Санкт-Петербург 2008

Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики

Научный консультант: Доктор технических наук, профессор Гуров Игорь Петрович

Официальные оппоненты: Член-корреспондент РАН, доктор технических наук, профессор Мирошников Михаил Михайлович

Доктор технических наук, профессор Коняхин Игорь Алексеевич

Доктор технических наук, профессор Ерош Игорь Львович

Ведущая организация: Филиал ФГУП "ЦНИИ "Комета" "Научно-проектный центр оптоэлектронных комплексов наблюдения", г. Санкт-Петербург

Защита состоится « 02 » декабря 2008 года в 15 часов 30 минут на заседании диссертационного совета Д212.227.01 при Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: Санкт-Петербург, пер. Гривцова, д.14, ауд. 314.

С диссертацией можно ознакомиться в библиотеке СПбГУ ИТМО.

Автореферат разослан «___» _________ 2008 г.

Отзывы и замечания по автореферату (в двух экземплярах), заверенные печатью, просим направлять в адрес университета: 197101, г.Санкт-Петербург, Кронверкский пр., д.49, секретарю диссертационного совета.

Ученый секретарь

диссертационного совета

кандидат технических наук, доцент В.М. Красавцев

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

Актуальность проблемы

Оптико-электронные приборы и комплексы, использующие автоматические методы анализа изображений, широко применяются в робототехнике, системах навигации и управления движением [1], в системах обнаружения и сопровождения целей [2], промышленных приложениях (таких, как контроль качества выпускаемой продукции, мониторинг производственных помещений [3]), разнообразных областях биомедицины [4], фотограмметрии, дистанционном сборе данных [5] и др. Дальнейшее совершенствование оптико-электронных систем определяется приоритетными направлениями науки, технологии и техники Российской Федерации - «Безопасность и противодействие терроризму», «Перспективные вооружения, военная и специальная техника», «Рациональное природопользование», «Транспортные, авиационные и космические системы».

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

В то же время, благодаря развитию технологии приемников излучения, за последние 10-15 лет произошло существенное повышение детальности получаемых изображений и удешевление (примерно на два порядка) устройств, формирующих цифровые изображения, при обеспечении их компактности [6]. В результате, использование оптико-электронных приборов и комплексов, ориентированных на формирование и обработку цифровых изображений, стало экономически оправданным во многих приложениях. Возросла также и производительность электронных компонентов оптико-электронных приборов, что создало возможности использования вычислительно более ресурсоемких алгоритмов анализа изображений.

Однако разработанные к настоящему времени в рамках иконики (науке об изображениях) научно-технические решения не в полной мере обеспечили возможности реализации автоматических методов обработки и распознавания изображений в новых предметных областях. Востребованность этих методов привела к появлению большого числа сторонников «практичного» подхода [7], в рамках которого критикуются попытки создания общетеоретических основ обработки и анализа изображений за непрактичность и предлагается рассматривать лишь вопросы построения систем обработки изображений, предназначенных для решения конкретных прикладных задач [8]. Такой подход позволил заполнить нишу методов анализа изображений ad hoc алгоритмами. Эти алгоритмы, как правило, не являются переносимыми, то есть они не могут быть повторно использованы для решения других аналогичных задач. Как следствие, при создании оптико-электронного комплекса существенная часть стоимости приходится на разработку и реализацию алгоритмов анализа изображений [9].

Хотя указанный подход и сыграл определенную положительную роль в развитии оптико-электронных приборов, однако сложившаяся к настоящему моменту ситуация многими исследователями воспринимается как кризисная [10, 11], а ее причина заключается в недостаточном внимании к теоретическим аспектам иконики и применении большого числа эвристических и слабо проверенных методов [12, с. 12].

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

Теоретические положения, позволяющие решить проблему анализа изображений и распознавания образов, должны быть основаны на строгом математическом базисе, прежде всего, на теории индуктивного вывода, в рамках которой рассматриваются задачи выбора моделей, наилучшим образом описывающих данные наблюдений [13]. Под моделью обычно понимается результат обобщения данных с выделением некоторых существенных характеристик при отвлечении от несущественных, случайных, деталей. При этом основным элементом индуктивного вывода является критерий оптимальности, в соответствии с которым осуществляется выбор модели.

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

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

Цель работы

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

Основные задачи

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

2. Разработка теоретических основ построения критерия оптимальности выбора решения в методах распознавания образов и анализа изображений.

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

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

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

Методы исследований

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

Научная новизна работы

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

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

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

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

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

Практическая значимость

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

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

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

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

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

Достоверность результатов работы

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

На защиту выносятся следующие положения и результаты:

1. Предложенный принцип репрезентационной минимальной длины описания (РМДО) обеспечивает оптимальность критериев выбора решения в задачах с существенным индуктивным смещением, использование которых позволяет максимизировать степень инвариантности методов анализа изображений.

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

3. Методология использования принципа РМДО в исследовании представлений информации, привлекаемых в методах распознавания образов и анализа изображений.

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

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

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

7. Аналитические выражения, устанавливающие связь степени априорной неопределенности выборки изображений и степени инвариантности методов анализа изображений с критерием РМДО.

Реализация результатов работы

Результаты диссертационной работы были использованы в НИР 12200-060-03 «Разработка и создание методов, алгоритмов и программ автоматического текстурного и структурного анализа изображений в задачах измерения, контроля и сопоставления изображений», выполнявшейся ФГУП НПК «ГОИ им. С.И. Вавилова» по заказу Министерства науки (2003 г.), НИР 0120.0 601227 «Создание систем анализа изображений и распознавания образов на основе высокопроизводительных видеоприложений», проводимой СПбГУ ИТМО по плану фундаментальных исследований по заказу Федерального агентства по образованию (2007-2008 гг.), а также при постановке и проведении ОКР «Разработка устройства цифровой обработки видеоданных оптико-электронных систем обнаружения, сопровождения и распознавания целей» шифр «Сатрап», выполняемой ФГУП НПК «ГОИ им. С.И. Вавилова» по заказу Управления развития базовых военных технологий и специальных проектов МО РФ (2004-2005 гг.). Результаты диссертационной работы были также использованы в ОКР «Сфера», проводимой в ЗАО НИИВЦ «Карат» (2005 г.), и в проекте «Раннее обнаружение лесных пожаров», выполнявшемся в ОАО «Оптико-электронные системы» (2006 г.).

Результаты работы использованы в учебном процессе СПбГУ ИТМО при выполнении курсовых и выпускных работ, а также в учебном курсе по дисциплине «Технологии искусственного интеллекта».

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

Апробация работы

Основные результаты работы докладывались на конференции “Battlespace Digitization and Network-Centric Warfare II” в рамках международного научного симпозиума “AeroSence-2002” (Orlando, 2002); конференции “Image and Signal Processing for Remote Sensing IX” в рамках международного симпозиума “Remote Sensing - 2003” (Barcelona, 2003); VII-ой международной конференции “Неразрушающие методы контроля и компьютерное моделирование в науке и технике” NDTCS-2003 (С.-Петербург, 2003); конференции “Automatic Target Recognition XIV” в рамках международного симпозиума “Defense and Security - 2004” (Orlando, 2004); VIII-ой международной конференции “Неразрушающие методы контроля и компьютерное моделирование в науке и технике”, NDTCS-2004 (С.-Петербург, 2004); VIII-ой общероссийской научной конференции “Современная логика: проблемы теории, истории и применения в науке” (С.-Петербург, 2004); конференции “Automatic Target Recognition XV” в рамках международного научного симпозиума “Defense and Security - 2005” (Orlando, 2005); 10-й Пущинской школе-конференции молодых ученых "Биология - наука XXI века" (Пущино, 2006); 26-й Европейской конференции по зрительному восприятию ECVP-06 (С.-Петербург, 2006); Всероссийской научно-технической конференции «Медицинские информационные системы-2006» (Таганрог, 2006); XXXVI научной и учебно-методической конференции профессорско-преподавательского и научного состава (С.-Петербург, 2007); международной научной конференции «Измерительные и информационные технологии в охране здоровья, Метромед-2007» (С.-Петербург, 2007); V международной конференции молодых ученых и специалистов «Оптика-2007» (С.-Петербург, 2007); XXXVII научной и учебно-методической конференции СПбГУ ИТМО (С.-Петербург, 2008); X конференции молодых ученых "Навигация и управление движением" (С.-Петербург, 2008); V Всероссийской межвузовской конференции молодых ученых (С.-Петербург, 2008); 2-й Международной конференции по оптическим сенсорам и машинному зрению OSAV'2008 (С.-Петербург, 2008).

Публикации

Основные научные результаты диссертации опубликованы в 30 научных работах общим объемом 50 п.л., среди которых одна монография, 8 статей в рецензируемых изданиях, входящих в перечень ВАК для диссертаций на соискание ученой степени доктора наук, а также два свидетельства о государственной регистрации программ для ЭВМ. Список работ приведен в конце автореферата.

Личный вклад автора

Представленные в диссертации результаты получены лично автором или при его непосредственном участии и руководстве. Все результаты, представленные в гл. 2 и 3 получены лично автором. Результаты, представленные в гл. 4 и 5, также получены лично автором за исключением части результатов по практическому применению методов структурного сопоставления изображений, которые получены в соавторстве в процессе совместной работы.

Структура и объем диссертации

Диссертация состоит из введения, пяти глав, заключения и списка цитируемой литературы. Она содержит 299 страниц машинописного текста, 62 рисунка и 20 таблиц. Список цитируемой литературы содержит 204 наименования.

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

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

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

В первой группе выделены подходы, использующие следующие типы представлений изображений:

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

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

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

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

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

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

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

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

· байесовский подход;

· энтропийный подход;

· теоретико-информационный подход.

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

Показано, что использование принципа минимальной длины описания (МДО) позволяет в определенной мере решить проблемы, возникающие в байесовском и энтропийном подходах. Наиболее широко принцип МДО формулируется [14] в форме «лучшей моделью является модель, которая позволяет минимизировать сумму длины описания данных в рамках модели и длины описания самой модели».

Строгое определение данного принципа следует из обращения задачи оптимального кодирования [15]: если в задаче оптимального кодирования по известной модели источника данных строится код минимальной длины, то в обратной задаче производится поиск модели, позволяющей закодировать данные оптимальным образом. В рамках алгоритмической теории информации оптимальная модель для данных определяется как

, (1)

где данные и модель интерпретируются как битовые строки, - условная алгоритмическая сложность строки при данной строке (длина минимальной программы для универсальной машины Тьюринга (УМТ), порождающей строку при получении на вход строки ), - длина строки . Уравнение (1) задает решение общей задачи индуктивного вывода, заключающейся в поиске модели, наилучшим образом описывающей исходные данные.

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

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

Во второй главе создана теория выбора критерия качества решения при распознавании образов и анализе изображений и осуществлена разработка методологии исследования представлений изображений на основе принципа репрезентационной (относящейся к представлениям) МДО (РМДО), предложенного в качестве уточнения принципа МДО.

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

,

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

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

Определение. Пусть S - некоторая программа для УМТ U. S будем называть представлением для множества изображений , если .

На основе таким образом введенного понятия представления изображений впервые предложен следующий принцип репрезентационной МДО, в котором выделяются два типа задач: построение описания одного изображения и построение представления изображений данной предметной области (по некоторой выборке изображений).

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

- длины модели ;

- длины описания изображения в рамках модели .

Критерий в данной задаче имеет вид:

, (2)

а лучшая модель должна выбираться следующим образом:

. (3)

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

- длины представления l(S);

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

Критерий качества и лучшее представление определяются как

, (4)

. (5)

Во второй главе на основе принципа РМДО предложены строгие и обоснованные формулировки важных для иконики понятий

· качества представления изображений (4);

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

· достоверности выбора лучшей из двух моделей и изображения f: ;

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

В частности, показано, что степень инвариантности методов анализа непосредственно связана с критерием (2), что позволяет использовать принцип РМДО для определения критерия оптимальности методов анализа изображений как в теоретических, так и в эмпирических исследованиях.

Введено новое понятие существенного превосходства представления S₁ над представлением S₂ на выборке F, если выполняется условие . Данное понятие использовано при исследовании представлений в главах 3 и 4.

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

В частности, впервые строго обоснованы следующие утверждения.

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

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

3. Если имеются три предметные области, задаваемые выборками изображений F₁, F₂, F₃, причем и , и S₁ и S₂ - оптимальные модели областей F₁ и F₂ соответственно, то . Иными словами, более общий метод анализа изображений является не менее эффективным на любой подобласти F₃ области F₁, чем частный метод, перенесенный на область F₃ из непересекающейся с ней области F₂.

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

и ,(6)

где S_i - i-й уровень иерархического представления, состоящего из N уровней.

Показано, что решение задач вида (6) не является оптимальным в смысле критерия РМДО (и, следовательно, в смысле степени инвариантности), который для иерархического представления может быть записан в виде

.(7)

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

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

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

Сформулированы следующие типы задач в области распознавания образов.

Первая задача. Пусть описание образа f в рамках представления имеет структуру , где обозначает номер класса (d - общее число классов) в некотором алфавите классов , а - описание образа f в рамках представления . Следовательно, выполняется равенство . Выбор оптимальной модели для образа f в соответствии с принципом РМДО осуществляется на основе соотношения

.(8)

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

Вторая задача. Производится построение представления S по выборке образов . В зависимости от количества априорной информации обычно выделяют две постановки задачи распознавания: с учителем и без учителя [16, с. 32-33].

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

При распознавании без учителя по совокупности данных ищется представление S, минимизирующее значение . При этом установлено, что данная задача отличается от общей задачи индуктивного вывода (5) тем, что представление S должно иметь априорно заданную структуру (принадлежать к некоторому семейству, не являющемуся алгоритмически полным).

Рассмотрен дискриминантный подход к распознаванию образов, в рамках которого образ f - это N-мерный вектор вещественных признаков , где - пространство признаков. Затем произведен анализ логических и синтаксических методов распознавания.

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

и ,

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

 и ,

где и - эталонный образ и радиус -го класса, выступающие в качестве параметров представления ; - i-й образ обучающей выборки, принадлежащий -му классу, а - число образов в -м классе; C' - некоторая константа;

,

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

,

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

Установлено, что в указанных методах выбор лучшего представления производится из ограниченного (не полного алгоритмически) семейства представлений, которое в каждом из методов задается разработчиком априорно. При этом строгого обоснования выбора и сравнения семейств представлений, как правило, не осуществляется.

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

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

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

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



Размещено на http://www.allbest.ru/

1

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

.

Таблица 1

Сравнение решающих функций разной сложности

№	M	%обуч.	%тест.	L
1	4	16,7	6,4	26,9
2	9	12,5	8,5	33,7
3	16	0,0	23,0	36,7
4	25	0,0	41,0	55,0

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

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

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

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

Установлено, что повышение точности моделей регрессии и сегментации на исходных данных не гарантирует повышения точности моделей в областях пространства признаков, не вошедших в исходные данные. В частности, на рис. 2 представлен пример аппроксимации набора точек полиномами различной степени (M).



Размещено на http://www.allbest.ru/

1

В табл. 2 приведены характеристики полиномов различной степени: среднеквадратичное значение невязок в точках выборки; средние ошибки (относительно истинной кривой, по которой с аддитивным шумом порождались точки выборки) во внутреннем для выборки диапазоне [10, 235] - и в расширенном диапазоне [-102, 347] - . В таблице представлены также соответствующие длины описания.

Таблица 2

Значения ошибок аппроксимации () и суммарных длин (L) описания для полиномов различных степеней (M)

M				L
1	20,8	15,4	64,5	45,5
2	18,0	13,6	62,8	45,1
3	8,4	2,5	6,0	35,6
4	8,1	2,5	27,0	36,9
5	8,0	2,5	70,9	38,2
6	7,6	2,5	326,8	39,3
7	7,5	3,2	590,9	40,8
8	6,6	5,5	8332	40,6
9	6,0	9,9	34912	40,9

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

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

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

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

В четвертой главе представлены результаты исследования проблемы представления изображений в условиях значительной априорной неопределенности. Сформированы представительные выборки (см. рис. 3) оптических аэрокосмических изображений (выборка F₁), радиолокационных аэрокосмических изображений (выборка F₂) и оптических изображений, полученных внутри помещений (выборка F₃). Каждая из выборок была использована для независимой оценки качества представлений изображений при последовательной оптимизации критерия РМДО.

Размещено на http://www.allbest.ru/

1

В связи с высокой априорной неопределенностью, характеризующей сформированные выборки, конструируемые представления, содержащие общую для изображений каждой из выборок информацию, должны опираться на наиболее общие свойства изображений, обусловленные соответствующими свойствами пространственной организации видимого мира и процессами формирования изображений [7]. В качестве таких свойств выбраны сформулированные в словесной форме Д. Марром [17, с. 57-63] предположения, заключающиеся в том, что наблюдаемая сцена состоит из совокупности видимых поверхностей, каждая из которых может быть описана функцией отражательной способности определенного вида, причем поверхности разделены почти всюду гладкими границами.

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

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

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

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

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

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

,

, ,(9)

, .

Функции вида (9) являются Габоровскими функциями, использующимися для описания рецептивных полей клеток зрительной коры приматов, селективных к пространственно-периодическим паттернам. Здесь - константа, определяющая вытянутость рецептивного поля клетки, а - свободные параметры, определяющие конкретную форму рецептивного поля (его ориентацию, размеры, а также частоту и фазу периодической компоненты). Иногда также используют фиксированное отношение , которое, как полагается [18], характерно для нейронов зрительной коры.

Для представлений выведены критерии РМДО для оценки качества сегментации , и :

;

,

;

,

,

где H - энтропия, оцененная по гистограмме соответствующей величины, N_dir - число направлений на следующую точку контура (тип связности), N_int - число уровней яркостей изображения, - коэффициент при j-й Габоровской функции из m_i функций, описывающих i-ю область изображения.

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

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

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

Размещено на http://www.allbest.ru/

1

В табл. 3 приведены результаты количественного сравнения качества разработанных представлений на разных выборках.

Таблица 3

Сравнение эффективности представлений и с

	Выборка
Отношение длин описания
	0,985	0,999	0,921
	57%	1%	100%
	0,946	0,988	0,996
	100%	63%	28%

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

Показано также, что эффективность представлений , и существенно превосходит на объединении выборок F₁, F₂, и F₃ эффективность представления , в котором все изображение описывается единым образом без выполнения сегментации. Таким образом, могут быть выделены характеристики представлений, которые должны быть использованы в методах анализа изображений для разнообразных предметных областей.

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

Рассмотрены три частных представления: представление , в котором контур описывается как совокупность сегментов, для каждого из которых проводится отрезок прямой с минимальной энтропией невязок (отклонений отрезка от точек контура); представление , в котором помимо отрезков прямых используются в качестве структурных элементов дуги окружностей и кривые второго порядка; представление , в котором используются также кривые третьего порядка.

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

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

Таблица 4

Сравнение эффективности представлений ,

	Выборка
Отношение длин описания
	0,809	0,812	0,679
	0,831	0,845	0,791
	1,007	1,007	1,006

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

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

...