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

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

Потапов Алексей Сергеевич АВТОМАТИЧЕСКИЙ АНАЛИЗ ИЗОБРАЖЕНИЙ И РАСПОЗНАВАНИЕ ОБРАЗОВ НА ОСНОВЕ ПРИНЦИПА РЕПРЕЗЕНТАЦИОННОЙ МИНИМАЛЬНОЙ ДЛИНЫ ОПИСАНИЯ Специальности:

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

АВТОРЕФЕРАТ

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

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

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

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

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

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

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

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

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

Отзывы и замечания по автореферату (в двух экземплярах), заверенные печатью, просим направлять в адрес университета:

197101, г.Санкт-Петербург, Кронверкский пр., д.49, секретарю диссертационного совета.

Ученый секретарь диссертационного совета кандидат технических наук, доцент В.М. Красавцев -2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-8 Апробация работы Основные результаты работы докладывались на конференции “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 статей в рецензируемых изданиях, входящих в перечень ВАК для диссертаций на соискание ученой степени доктора наук, а также два свидетельства о государственной регистрации программ для ЭВМ. Список работ приведен в конце автореферата.

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

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

Список цитируемой литературы содержит 204 наименования.

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

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

В первой главе рассмотрено современное состояние проблемы анализа изображений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- 11 Строгое определение данного принципа следует из обращения задачи оптимального кодирования [15]: если в задаче оптимального кодирования по известной модели источника данных строится код минимальной длины, то в обратной задаче производится поиск модели, позволяющей закодировать данные оптимальным образом. В рамках алгоритмической теории информации оптимальная модель µ * для данных определяется как µ * = arg min[K ( | µ) + l (µ)], (1) µ где данные и модель µ интерпретируются как битовые строки, K ( | µ) – условная алгоритмическая сложность строки при данной строке µ (длина минимальной программы для универсальной машины Тьюринга (УМТ), порождающей строку при получении на вход строки µ ), l (µ) – длина строки µ. Уравнение (1) задает решение общей задачи индуктивного вывода, заключающейся в поиске модели, наилучшим образом описывающей исходные данные.

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

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

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

Показано, что использование принципа МДО (1) для выбора критерия качества решения в методах, которые применяются для независимого анализа изображений некоторой выборки f1,..., f n из n изображений, то есть для решения n задач вида - 12 µ * = arg min[K ( f i | µ) + l (µ)], не является вполне корректным, поскольку принцип МДО в i µ такой формулировке может быть использован только для выбора оптимальной модели всей совокупности изображений, то есть для решения задачи вида µ * = arg min[K ( f1 f 2... f n | µ) + l (µ)]. В то же время имеет место неравенство µ n min[K ( f i | µ) + l (µ)] min[K ( f1 f 2... f n | µ) + l (µ)], µ µ i = поскольку изображения содержат большой объем взаимной информации, который можно трактовать как индуктивное смещение (априорное предпочтение при выборе модели) задачи индуктивного вывода (1). Таким образом, впервые выявлена причина, по которой в существующих работах по применению принципа МДО к задачам анализа изображений происходит отказ от теоретически обоснованного критерия (1) в пользу привлечения эвристических схем кодирования для вычисления значений длины описания.

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

Определение. Пусть S – некоторая программа для УМТ U. S будем называть F = { f1,..., f n }, представлением для множества изображений если (f F )(µ, {0,1}* )U ( Sµ) = f.

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

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

- длины модели l (µ) ;

- длины описания изображения в рамках модели K S ( f | µ) = K ( f | Sµ).

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

LS ( f, µ) = K S ( f | µ) + l (µ), (2) а лучшая модель должна выбираться следующим образом:

µ * = arg min[K S ( f | µ) + l (µ)]. (3) µ - 13 2. Наилучшим представлением S для данной выборки изображений F = { f1,..., f n } является представление, для которого минимизируется сумма:

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

n K S ( fi ), - суммарной длины описаний изображений в рамках представления i = где K S ( f ) = min[K S ( f | µ) + l (µ)].

µ Критерий качества и лучшее представление определяются как n L( F, S ) = l ( S ) + K S ( f i ), (4) i = n S * = arg min l ( S ) + K S ( f i ). (5) S i = Во второй главе на основе принципа РМДО предложены строгие и обоснованные формулировки важных для иконики понятий • качества представления изображений (4);

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

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

LS ( f,µ1 ) LS ( f,µ 2 ) QS (µ1, µ 2 | f ) = 1 2 ;

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

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

Введено новое понятие существенного превосходства представления S1 над представлением S2 на выборке F, если выполняется условие L( F, S1 ) L( F, S 2 ) & (f F ) K S1 ( f ) K S2 ( f ). Данное понятие использовано при исследовании представлений в главах 3 и 4.

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

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

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

F1 F2, то 2. Если имеются две выборки изображений F1 и F2, причем K S1 ( f ) K S2 ( f ). Это верно, в частности, для случая F1 F2, то есть эффективность f F1 f F более общего метода анализа изображений всегда не выше, чем эффективность оптимального частного метода, разработанного для конкретной выборки. При перенесении некоторого метода анализа изображений на новую предметную область сохранение его эффективности гарантировано быть не может без дополнительных ограничений, устанавливающих связь между F1 и F2.

3. Если имеются три предметные области, задаваемые выборками изображений F1, F2, F3, причем F1 = F2 F3 и F2 F3 =, и S1 и S2 – оптимальные модели областей F1 и F K S1 ( f ) K S2 ( f ).

соответственно, то Иными словами, более общий метод анализа f F3 f F изображений является не менее эффективным на любой подобласти F3 области F1, чем частный метод, перенесенный на область F3 из непересекающейся с ней области F2.

В рамках разработанной теории выбора критерия качества рассмотрена проблема построения иерархических представлений изображений. На каждом последующем уровне иерархических представлений модель, выбранная на предыдущем уровне, рассматривается в качестве исходных данных для построения модели следующего уровня. В частности, если на первом шаге анализа изображений происходит их сегментация с разделением изображения на области, то на следующем уровне границы областей представляются в виде совокупности структурных элементов. Независимому последовательному построению описаний разных уровней соответствует совокупность задач вида N [ ] = arg min K S1 ( f | µ1 ) + l (µ1 ) и µ *+1 = arg min K Si +1 (µ * | µ i +1 ) + l (µ i +1 ), * µ1 (6) i i i = µ1 µi + где Si – i-й уровень иерархического представления, состоящего из N уровней.

Показано, что решение задач вида (6) не является оптимальным в смысле критерия РМДО (и, следовательно, в смысле степени инвариантности), который для иерархического представления может быть записан в виде N LS1,..., S N ( f, µ1,..., µ N ) = K S1 ( f | µ1 ) + K Si (µ i | µ i +1 ) + l (µ N ). (7) i = - 15 Таким образом, обоснована необходимость совместного решения таких задач, как выделение контуров, построение структурных элементов и их группирование, поскольку критерии качества решения в этих задачах не могут оптимизироваться независимо.

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

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

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

Первая задача. Пусть описание образа f в рамках представления S = ( S1, S 2,..., S d ) имеет структуру (µ, ), где µ обозначает номер класса 1,2,..., d (d – общее число классов) в некотором алфавите классов = {a1, a2,..., ad }, а – описание образа f в рамках представления Sµ. Следовательно, выполняется равенство K S ( f | µ) = K Sµ ( f ). Выбор оптимальной модели для образа f в соответствии с принципом РМДО осуществляется на основе соотношения µ* = arg min LS ( f, µ) = arg min[l (µ) + K Sµ ( f )]. (8) µ =1,...,d µ =1,...,d Рассмотренная задача заключается в классификации единичного объекта.

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

При распознавании с учителем обучающая выборка содержит не образы f i, а пары ( f i, µ i ), где µ i – класс, к которому относится образ f i. В связи с введением дополнительного элемента во входные данные общий критерий качества представления L( F, S ) должен быть ( ) ( ) L {( f i, µ i )}in=1, S, либо как критерий L {µ i }in=1, S | { f i }in=1. Для уточнен, как критерий обозначения постановки задачи распознавания в зависимости от вида используемого критерия введены понятия индуктивного и предиктивного распознавания соответственно.

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

- 16 При распознавании без учителя по совокупности данных F = { f1,..., f n } ищется представление S, минимизирующее значение L( F, S ). При этом установлено, что данная задача отличается от общей задачи индуктивного вывода (5) тем, что представление S должно иметь априорно заданную структуру (принадлежать к некоторому семейству, не являющемуся алгоритмически полным).

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

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

• K Sµ (x) = log 2 n + log 2 x x µ, + C и L( F, S ) = l ( S ) + n log 2 n + nC, где x – классифицируемый образ;

x µ, – образ обучающей выборки, принадлежащий µ -му классу и являющийся ближайшим к образу x ;

C – некоторая константа, не зависящая от классифицируемого образа и номера класса;

x yµ d nµ + log 2 µ + C и L( F, S ) = l ( S ) + (l (µ) + K (x µ,i | S µ ) ), • K Sµ ( x ) = (2 ln 2) µ µ =1 i = где y µ и µ – эталонный образ и радиус µ -го класса, выступающие в качестве параметров представления S µ ;

x µ,i – i-й образ обучающей выборки, принадлежащий µ -му классу, а nµ – число образов в µ -м классе;

C' – некоторая константа;

) ( M µ nµ d L( F, S ) = lµ,i log 2 P x µ, | {[ wµ,i ]lµ,i }i =1 nµ log 2 P(µ), Mµ • µ =1 i =1 = где P (x | w µ ) – плотность распределения вероятностей образов µ -го класса, задаваемая вектором параметров w µ размерности M µ, на описание i-го компонента [ wµ,i ]lµ,i которого выделено lµ,i бит;

P (µ) – априорная вероятность появления образа, принадлежащего µ -му классу;

- 17 n M M 1 n L({ } |{ } = li + log 2 z i [ w j ]l j y j (x), n n • z i i =1, S x i i =1 ) n i =1 2 i =1 j = где величина zi – принимает значение -1, если i-й образ принадлежит первому классу, и 1 – если второму классу;

[ w j ]l j – j-й компонент вектора параметров обобщенной решающей функции, на описание которого выделено l j бит;

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

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

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

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

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

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

а) б) в) г) Рис. 1. Решающие функции с разным числом параметров (а – 4, б – 9, в – 16, г – 25), найденные по одинаковой обучающей выборке, состоящей из 24 векторов В табл. 1 для каждой решающей функции приведены число параметров, процент ошибок на обучающей выборке, процент ошибок на тестовой выборке, составленной из образов, не вошедших в обучающую выборку, и длина описания L({zi }i =1, S | {x i }i =1 ).

n n Таблица 1. Сравнение решающих функций разной сложности № %обуч. %тест.

M L 1 4 16,7 6,4 26, 2 9 12,5 8,5 33, 3 16 0,0 23,0 36, 4 25 0,0 41,0 55, Таким образом, показано, что процент ошибок на обучающей выборке не определяет однозначно процент ошибок для образов, не вошедших в обучающую выборку. В то же время, выбор решающей функции по критерию РМДО соответствует выбору решающей функции с минимальным процентом ошибок на тестовой выборке.

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

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

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

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

Рис. 2. Пример аппроксимации точек полиномами различной степени;

«o» – тестовая точка, не использованная в выборке В табл. 2 приведены характеристики полиномов различной степени:

среднеквадратичное значение невязок 0 в точках выборки;

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

- 20 Таблица 2. Значения ошибок аппроксимации ( 1, 2,3 ) и суммарных длин (L) описания для полиномов различных степеней (M) 0 1 M L 1 20,8 15,4 64,5 45, 2 18,0 13,6 62,8 45, 3 8,4 2,5 6,0 35, 4 8,1 2,5 27,0 36, 5 8,0 2,5 70,9 38, 6 7,6 2,5 326,8 39, 7 7,5 3,2 590,9 40, 8 6,6 5,5 8332 40, 9 6,0 9,9 34912 40, Как видно из таблицы, ошибка на данной выборке точек ( 0 ) уменьшается с ростом степени полинома, но при этом ошибка в точках, не вошедших в выборку, после некоторого значения M начинает увеличиваться. В то же время, критерии, построенные на основе принципа РМДО, позволяют выбирать полином, дающий минимальную ошибку как в задаче интерполяции ( 1 ), так и в задаче экстраполяции ( 2 ), причем в последней задаче различия в ошибках для разных полиномов могут становиться чрезвычайно большими, что не находит отражения в классическом критерии среднеквадратичного отклонения 0.

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

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

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

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

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

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

а) б) в) Рис. 3. Примеры фрагментов изображений из выборок а) аэрокосмических изображений;

б) радиолокационных изображений;

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

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

На первом уровне изображение представлено в виде совокупности областей, в каждой из которых распределение яркостей описывается собственной моделью. Построение описания изображения f ( x, y ) на данном уровне сведено к задаче сегментации, которая заключается в том, чтобы разбить область G, на которой задано изображение, на d областей G1,..., Gd таких, что G1 G2... Gd = G и Gi G j i = j, где d также неизвестно, и сужение изображения f i ( x, y ) = f ( x, y ) G на область Gi описать собственной регрессионной i моделью g i ( x, y, w i ) : Gi R, где w i – вектор ее параметров.

Рассмотрены три частных представления изображений S1(1), S 21) и S 31) первого ( ( уровня, различающихся выбором семейства функций g i ( x, y, w i ).

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

S 21) ( g i ( x, y, w i ) В представлении были использованы функции вида g ( x, y, w ) = w0 + w1 x + w2 y + w3 x 2 + w4 xy + w5 y 2, описывающие плавные изменения яркости поверхностей.

В представлении S 31) были использованы функции g i ( x, y, w i ) вида ( ~ g ( x, y | w ) = g,,, ( x x0, y y0 ), ~2 +2 ~ x y ~ x ~ w = ( x0, y0,,,, ), g,,, ( x, y ) = e cos 2 +, (9) ~ = x cos + y sin, ~ = x sin + y cos.

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

Для представлений выведены критерии РМДО для оценки качества сегментации S1(1), S 21) и S 31) :

( ( ( f, {Gi }id=1 ) = ( Gi H ( f i ) + N int log 2 N int + Gi log 2 N dir );

L (1) S i d (1) ( f, {Gi, w i }i =1 ) = ( Gi H ( ri ) + N int log 2 N int + Gi log 2 N dir + 1 + l ( w i ) ), d L S i = ( ) ri ( x, y ) = f i ( x, y ) wi,0 + wi,1 x + wi, 2 y + wi,3 x 2 + wi, 4 xy + wi,5 y 2 ;

{ } f, G, {w }mi = d L i, j j = i S31) ( i =, ( ( )) d = Gi H (ri ) + N int log 2 N int + Gi log 2 N dir + log 2 mi + l {w i, j }m= i j i = mi ri ( x, y ) = f i ( x, y ) Ai, j g ( x, y | w i, j ), j = где H – энтропия, оцененная по гистограмме соответствующей величины, Ndir – число направлений на следующую точку контура (тип связности), Nint – число уровней яркостей изображения, – коэффициент при j-й Габоровской функции из mi функций, Ai, j описывающих i-ю область изображения.

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

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

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

Рис. 4. Примеры сегментации фрагментов изображений, полученных внутри помещений, с помощью представлений S1(1) (посередине) и S 21) (справа) ( В табл. 3 приведены результаты количественного сравнения качества разработанных представлений на разных выборках.

Таблица 3. Сравнение эффективности представлений S 21) и S 31) с S1(1) ( ( Выборка Отношение длин описания F F1 F 0,985 0,999 0, K (1) ( F ) K (1) ( F ) S2 S K 57% 1% 100% P( K (1) ( F ) (1) ( F )) S2 S 0,946 0,988 0, K (1) ( F ) K (1) ( F ) S3 S K 100% 63% 28% P( K (1) ( F ) (1) ( F )) S3 S - 25 Таким образом, подтверждено влияние предметной области на выбор оптимального представления изображений.

Показано также, что эффективность представлений S1(1), S 21) и S 31) существенно ( ( превосходит на объединении выборок F1, F2, и F3 эффективность представления S 01), в ( котором все изображение описывается единым образом без выполнения сегментации. Таким образом, могут быть выделены характеристики представлений, которые должны быть использованы в методах анализа изображений для разнообразных предметных областей.

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

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

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

представление S 32), в ( котором используются также кривые третьего порядка.

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

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

Таблица 4. Сравнение эффективности представлений S n2), n {0,1,2,3} ( Выборка Отношение длин описания F F1 F ( 2 ) (G ) ( 2 ) (G ) 0,809 0,812 0, K K S1 S (G ) K (G ) 0,831 0,845 0, K ( 2) ( 2) S2 S (G ) K (G ) 1,007 1,007 1, K ( 2) ( 2) S3 S - 26 Показано, что наибольшей эффективностью на используемых выборках изображений обладает представление S 22). Таким образом, приведено обоснование использования ( отрезков прямых и сегментов кривых второго порядка в качестве контурных структурных элементов и показана неэффективность сегментов кривых третьего порядка на основании того, что их введение в представление ухудшает среднюю длину описания по каждой из выборок, что соответствует уменьшению степени инвариантности структурных элементов.

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

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

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

( ) S1( H ) = S1(1), S 22), S 23). Представлены ( ( Рассмотрено иерархическое представление разработанные алгоритмы построения иерархических структурных описаний изображений, включающих уровни пикселей, контуров, структурных элементов и их групп. При этом качество описаний повышено за счет введения обратных связей от верхних уровней к нижним. Структура обратных связей выбрана на основе теоретико-информационной модели адаптивного резонанса, предложенной в главе 2. В частности, разработан алгоритм адаптивной коррекции контуров в процессе построения структурных элементов (см. рис. 5).

а) б) в) г) Рис. 5. Пример адаптивной коррекции контуров в процессе построения структурных элементов: а) и б) – исходный результат сегментации изображения и границ областей;

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

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

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

а) б) в) Рис. 6. Примеры а) изображений целей, использованных при решении задачи распознавания целей;

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

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

На основе предложенных в главе 4 представлений изображений разработаны методы совмещения изображений. При этом проблема совмещения изображений поставлена как проблема построения их совместного описания (см. рис. 7), в качестве одного из компонентов которого выступает описание взаимного пространственного преобразования изображений. Критерий качества совмещения, основанный на принципе РМДО (2), в данной задаче принял форму:

LS ( f1, f 2, µ, T ) = K S ( f1 | µ) + K S ( f 2 o T | µ) + l (µ) + l (T ), где µ – общая часть описания изображения f1 и изображения f 2 o T, преобразованного с помощью отображения T. В качестве представления S выступает иерархическое структурное представление S1( H ), предложенное в главе 4.

Пиксельный Контурный Структурный уровень уровень уровень Описание Изображение 1 совмещенной пары изображений Изображение Пиксельный Контурный Структурный уровень уровень уровень Рис. 7. Совмещение изображений как построение их совместного описания В результате, разработанные методы совмещения изображений обладают следующими особенностями, отличающими их от существующих методов совмещения:

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

• используются иерархические структурные представления изображений, инвариантные к условиям съемки, что приводит к инвариантности методов совмещения (см. рис. 8);

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

а) б) в) г) д) Рис. 8. Пример совмещения а) радиолокационного изображения и б) оптического изображения;

в) и г) – их структурные описания;

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ В диссертационной работе дано решение актуальной научной проблемы создания теории выбора решения в методах анализа изображений и распознавания образов и разработки методологии исследования представлений изображений в целях повышения эффективности (вероятности распознавания и степени инвариантности по отношению к условиям съемки) и расширения (на предметные области с высокой априорной неопределенностью) сферы применения оптико-электронных приборов и комплексов.

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

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

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

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

- 31 б) Сформулированы и доказаны утверждения о зависимости свойств оптимальных представлений от характеристик предметной области и связи критерия РМДО с степенью априорной неопределенности и инвариантностью представлений изображений.

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

3. В рамках теории выбора решения на основе критерия РМДО получены частно теоретические результаты в области признакового анализа изображений.

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

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

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

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

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

- 32 ЦИТИРУЕМАЯ ЛИТЕРАТУРА 1. Florczyk S. Robot Vision: Video-based Indoor Exploration with Autonomous and Mobile Robots / Wiley, 2005. 216 p.

2. Тарасов В.В., Якушенков Ю.Г. Инфракрасные системы "смотрящего" типа. М.: ЛОГОС, 2004. 443 с.

3. Batchelor B., Whelan P.F. Intelligent vision systems for industry / Springer-Verlag, 2002. 457 p.

4. Image processing and analysis. A practical approach / Baldock R. and Graham J. (eds). New York: Oxford university press. 2000. 301 p.

5. Atkinson K.B. Close range photogrammetry and machine vision / Whittles Pub. 2003. 384 P.

6. Форсайт Д., Понс Д. Компьютерное зрение. Современный подход. Вильямс. 2004. 928 с.

7. Tarr M.J., Black M.J. A computational and evolutionary perspective on the role of representation in vision // CVGIP: Image Understanding. 1994. V. 60. No 1. P. 65–73.

8. Aloimonos J. Purposive and qualitative active vision // Proc. 10th International Conference on Pattern Recognition. 1990. V. 1. P. 346–360.

9. Rares A., Reinders M.J.T., Hendriks E.A. Image Interpretation Systems // Technical Report (MCCWS 2.1.1.3.C), MCCWS project, Information and Communication Theory Group. TU Delft. 1999. 32 p.

10. Jain R.C., Binford T.O. Ignorance, myopia and naivete in computer vision systems // CVGIP:

Image Understanding. 1991. V. 53. No. 1. P. 112–117.

11. Jain R.C., Binford T.O. Revolutions and experimental computer vision // CVGIP: Image Understand. 1991. V. 53. No 1. P. 127–128.

12. Фурман Я.А. и др. Введение в контурный анализ и его приложения к обработке изображений и сигналов: М., ФИЗМАТЛИТ. 2002. 592 с.

13. Baxter R.A. Minimum Message Length Inference: Theory and Applications: PhD thesis, Department of Computer Science, Monash University, Clayton, Australia. 1996. 246 p.

14. Vitanyi P.M.B. and Li M. Minimum description length induction, Bayesianism, and Kolmogorov complexity // IEEE Transactions on Information Theory. 2000. V. 46. No. 2. P.

446–464.

15. Solomonoff R.J. The Discovery of Algorithmic Probability // J. of Computer and System Sciences. 1997. V. 55. No. 1. P. 73–88.

16. Ту Дж., Гонсалес Р. Принципы распознавания образов: М., Мир. 1978. 412 с.

17. Марр Д. Зрение. Информационный подход к изучению представления и обработки зрительных образов: М., Радио и связь. 1987. 400 с.

18. Kruizinga P., Petkov N. Nonlinear operator for oriented texture // IEEE Transactions on image processing, 1999. V. 8. No. 10. P. 1395–1407.

- 33 ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ Монографии 1. Потапов А.С. Распознавание образов и машинное восприятие: общий подход на основе принципа минимальной длины описания: С-Пб, Политехника. 2007. 548 с.

Статьи в журналах, рекомендованных ВАК 2. Потапов А.С., Малышев И.А., Луцив В.Р. Совмещение аэрокосмических изображений с субпиксельной точностью методом локальной корреляции // Оптический журнал. 2004. Т.

71. № 5. С. 31-36.

3. Потапов А.С. Влияние взаимных геометрических искажений изображений на возможность их пространственного совмещения методом локальной корреляции // Оптический журнал. 2004. Т. 71. № 8. С. 74-80.

4. Потапов А.С., Малышев И.А., Луцив В.Р. Принцип минимальной длины описания как средство улучшения дискриминантных методов распознавания // Оптический журнал.

2006. Т. 73. № 10. С. 41-46.

5. Андреев В.С., Губкин А.Ф., Ильяшенко А.С., Кадыков А.Б., Лапина Н.Н., Луцив В.Р., Малышев И.А., Новикова Т.А., Потапов А.С. Алгоритмы автоматической обработки и анализа аэрокосмических снимков // Оптический журнал. 2007. Т. 74. № 5. С. 12-30.

6. Потапов А.С. Выбор модели пространственного преобразования изображений по критерию минимальной длины описания // Оптический журнал. 2007. Т. 74. № 5. С. 48-53.

7. Потапов А.С. Теоретико-информационный подход к введению обратных связей в многоуровневых системах компьютерного зрения // Оптический журнал. 2007. Т. 74. № 10. С. 59-65.

8. Потапов А.С. Исследование представлений изображений на основе принцип репрезентационной длины описания // Изв. вузов. Приборостроение. 2008. Т. 51. № 7. С.

3-7.

9. Потапов А.С., Петроченко В.Г. Количественное описание законов перцептивного группирования с помощью принципа репрезентационной минимальной длины описания // Оптический журнал. 2008. Т. 75. № 8. С. 42-47.

- 34 Научные публикации в прочих изданиях 10. Lutsiv V.R., Malyshev I.A., Pepelka V., Potapov A.S. Target independent algorithms for description and structural matching of aerospace photographs // Proc. SPIE. 2002. V. 4741. P.

351-362.

11. Lutsiv V., Malyshev I., Potapov A. Hierarchical structural matching algorithms for registration of aerospace images // Proc. SPIE. 2003. V. 5238. P. 164-175.

12. Potapov A.S., Luciv V.R. Information-theoretic approach to image description and interpretation // Proc. 7th Int. Workshop on New Approaches to High-Tech: Nondestructive Testing and Computer Simulations in Science and Engineering. 2003. V. 7. P. F8-F11.

13. Потапов А.С. Принцип минимальной длины описания и сравнение гипотез // Современная логика: проблемы теории, истории и применения в науке. Труды VIII Общероссийской научной конференции. С-Пб. 2004. С. 409-412.

14. Potapov A.S., Luciv V.R. Information-theoretic approach to image description and interpretation // Proc. SPIE. 2003. V. 5400. P. 277-283.

15. Potapov A.S. Image matching with the use of the minimum description length approach // Proc.

SPIE. 2004. V. 5426. P. 164-175.

16. Potapov A.S., Gamayunova O.S. Information criterion for constructing the hierarchical structural representations of images // Proc. SPIE. 2005. V. 5807. P. 443-454.

17. Potapov A.S., Luciv V.R., Malyshev I.A. Sub-pixel precise image analysis in the industrial environment // Proc. 8th Int. Workshop on New Approaches to High-Tech: Nondestructive Testing and Computer Simulations in Science and Engineering. 2004. V. 8. P. E17-E20.

18. Bahvalov J.N., Potapov A.S. A statistical model of interpolation and its application to texture segmentation // Proc. 8th Int. Workshop on New Approaches to High-Tech: Nondestructive Testing and Computer Simulations in Science and Engineering. 2004. V. 8. P. E26-E30.

19. Lutsiv V., Potapov A., Novikova T., Lapina N. Hierarchical 3D structural matching in the aerospace photographs and indoor scenes // Proc. SPIE. 2005. V. 5807. P. 455-466.

20. Bahvalov J.N., Potapov A.S. A statistical model of interpolation and its application to texture segmentation // Proc. SPIE. 2005. V. 5831. P. 191-198.

21. Potapov A.S., Luciv V.R., Malyshev I.A. Sub-pixel precise image analysis in the industrial environment // Proc. SPIE. 2005. V. 5831. P. 199-203.

22. Potapov A.S. Information-theoretic interpretation of Gestalt // Perception. 2006. V. 35. P. 78.

23. Lyakhovetskii V., Potapov A., Ivanov S. Strategies for storing spatial transformations of chess positions // Perception. 2006. V. 35. P. 105.

- 35 24. Ляховецкий В.А., Потапов А.С., Попечителев Е.П. Методика изучения и модель информационной структуры памяти человека // Известия ТРТУ, Таганрог, 2006. № 11. C.

4-9.

25. Потапов А.С. Новые методы автоматического анализа изображений в задачах экологического мониторинга // Труды межд. научн. конф. Измерительные и информационные технологии в охране здоровья, Метромед-2007. 2007. С. 155-162.

26. Потапов А.С., Новикова Т.Н. Распознавание дымов на основе текстур динамических изображений // Труды V межд. конф. молодых ученых и специалистов «Оптика-2007».

СПб: СПбГУ ИТМО. 2007. С. 364-365.

27. Потапов А.С. Технологии искусственного интеллекта: анализ проблематики и построение структуры учебной дисциплины // Научно-технический вестник СПбГУ ИТМО. 2007.

Вып. 43. С. 308-313.

28. Potapov A.S. Synthetic pattern recognition methods based on the representational minimum description length principle // Digest of the 2nd International Topical Meeting on Optical Sensing and Artificial Vision, OSAV’2008. 2008. P. 124-125.

29. Потапов А.С. Программный модуль «Перцептивное группирование структурных элементов» // Свидетельство о государственной регистрации программы для ЭВМ. М.:

РОСПАТЕНТ. 2008. № 2008612428.

30. Потапов А.С. Программный модуль «Теоретико-информационная аппроксимация изображений габоровскими функциями» // Свидетельство о государственной регистрации программы для ЭВМ. М.: РОСПАТЕНТ. 2008. № 2008612429.

- 36