автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Методы обработки в условиях априорной неопределенности

Ao // M , 3?

" • Xi ■;■ ■' '

i ■ x * ' , ^ ч 1------------

;i Ноча; - H-vniïc: j -

[[ ________________ pcM^^m^t

Нижегородский Государственный технический университет

На правах рукописи УДК 519.6

УТРОБИН Владимир Александрович

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

Специальность 05.13.17 - Теоретические основы информатики

(по техническим наукам)

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

Научный консультант: Член-корреспондент РАН, профессор Кондратьев В.В.

Нижний Новгород 1997

ОГЛАВЛЕНИЕ

Введение.............................................................................................................5

Глава 1. Проблемы построения систем обработки изображений .........................................................................................................................12

1.1. Архитектура современных систем обработки изображений......................................................................................................................................................13

1.2. Анализ состояния теории обработки изображений.. 20

1.2.1. Анализ состояния теории обработки изображений с позиций теории распознавания образов..........................................20

1.2.1.1. Декомпозиция проблемы распознавания......................................22

1.2.1.2. Проблемы формирования исходного описания................23

1.2.1.3. Проблемы формирования системы признаков....................25

1.2.1.4. Проблемы принятия решений в условиях априорной неопределенности....................................................28

1.2.2. Анализ состояния теории обработки изображений с позиций зрительного восприятия.....................................29

1.3. Цель и задачи исследования..........................................34

Глава 2. Концептуальная модель процесса раскрытия

априорной неопределенности......................................35

2.1. Формализация понятия изображения..................................................35

2.1.1. Аксиоматика свойств изображения........................................................37

2.1.2. Математические модели изображения..............................................43

2.2. Раскрытие неопределенности с позиций теоретико-множественного подхода............................................................................................45

2.2.1. Свойства пирамидальной модели..............................................................50

2.2.2. Конструктивное определение пирамидальной модели^..........................................................................................................................................................53

2.3. Раскрытие неопределенности с позиций системного

анализа..........................................................................................................................58

2.3.1. Раскрытие неопределенности с позиций теоретико-вероятностного подхода........................................................................59

2.3.2. Раскрытие неопределенности с позиций системно-теоретического подхода..................................................................................................63

2.4. Обработка изображения в условиях неопределенности...............................................................................................................................66

2.4.1. Точность представления на пирамидальной модели 66

2.4.2. Размерность пирамидальной модели......................................................70

2.4.3. Связность пирамидальной модели......................................74

2.4.4. Оптимальность пирамидальной модели............................................78

Выводы ....................................................................................................................................................................................88

Глава 3. Анализ изображения в условиях априорной неопределенности............................................................................................................................90

3.1. Конструктивное определение пирамидальной модели д>-ж......................................................................................................................................................9i

3.2. Универсальность функциональной пирамидальной модели..............................................................................................................................................................105

3.2.1. Полнота пирамидальной модели....................................................................108

3.2.2. Устойчивость описания на пирамидальной модели.. 118

3.2.3. Чувствительность описания на пирамидальной модели......................................................................................................................................................124

3.3. Формирование описания на пирамидальной модели 128

3.3.1. Восстановление трехмерности описания........................................139

Выводы ...............................................................................................................................144

Глава 4. Синтез изображения........................................................................................................146

4.1. Алгебра изображения в условиях априорной неопределенности......................................................................................................................................146

4.2. Грамматика описания изображения........................................................156

4.3. Группы алгебры изображения......................................................................159

4.4. Алгебра групп на решетке V(x,y)................................................................172

4.5. Формирование эталона................................................................................................185

4.5.1. Формирование изобразительного описания............................188

4.5.2. Аксиоматика алгебры групп..................................................195

4.5.3. Инвариантность описания образа..............................................................200

4.5.4. Компактность описания.................................................................217

Выводы ...................................................................................................240

Глава 5. Реализация модели раскрытия априорной неопределенности...........................................................................244

5.1. Информационная модель процесса принятия решений...................................................................................................244

5.1.1. Пространство классов.......................................................................................244

5.1.2. Свойства пространства классов....................................................................248

5.1.3. Принятие решений.........................................................250

5.2. Симметрические свойства элементов алгебры изображения.....................................................................................................254

5.2.1. Группы симметрии..............................................................................................254

5.2.2. Группы движений..................................................................................................................263

5.2.3. Суперпозиция групп симметрии....................................................274

5.2.4. Суперпозиция групп движений......................................................................295

5.3. Ориентационные свойства системы полных групп.. 305

5.4. Приложения модели.................................................................325

Выводы ..................................................................................................................................................................................357

Основные результаты и выводы.................................................................360

Список литературы ............................... ..............................................................................363

Приложения....................................................................................................................................................................393

ВВЕДЕНИЕ

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

Вопросы обработки, анализа и распознавания изображений получили фундаментальное развитие в работах научных коллективов Вычислительного центра РАН, Института проблем передачи информации РАН, Института систем обработки изображений РАН, Института прикладной математики и кибернетики при Нижегородском госуниверситете, Тульского госуниверситета и др. Значительный вклад в решение проблемы распознавания изображений внесли М.А. Айзерман, Э.М. Браверман, В.Н. Вапник, Ю.Г. Васин, А.И. Галушкин, А.Л. Горелик, И.Б. Гуревич, Р. Дуда, Ю.И. Журавлев, Н.Г. Загоруйко, Д. Марр, М. Минский, Ю.И. Неймарк, С. Пейперт, Ф. Розенблатт, А. Розенфельд, В.А. Сойфер, Р. Фишер, К. Фу, П. Харт, М.И. Шлезингер и другие российские и зарубежные ученые.

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

тики в задачи моделирования биосистем. Была высказана гипотеза - механизм восприятия есть классифицирующая система, и сформулирована задача построения машины способной обучаться. Результатом такой общей постановки проблемы являются два крупных взаимосвязанных направления исследований, сохранившихся до настоящего времени: разработка математических моделей зрительного восприятия (В .К. Ла-бутин, Д. Марр, Ф. Розенблатт и др.); разработка математических методов информационных преобразований изображения как многомерного сигнала (М.А. Айзерман, Э.М. Браверман, Н.Г. Загоруйко и др.), породившая теорию распознавания образов (Ю.И. Журавлев, К. Фу и др.). В силу исторических причин разработки по второму направлению отошли от проблем обработки изображений и в настоящее время представляют самостоятельную теоретическую дисциплину, предметом которой является построение математических моделей классификации объектов в режиме обучения. Результатом является отрыв практики построения систем обработки изображений от теоретических исследований, и отсутствие на настоящий момент теории распознавания изображений.

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

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

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

Автор защищает:

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

2. Модели и средства анализа изображения в условиях априорной неопределенности.

3. Модели и средства синтеза изображения в условиях априорной неопределенности.

4. Модель процесса принятия решений в условиях априорной неопределенности.

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

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

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

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

3. Разработана пирамидальная модель раскрытия априорной неопределенности изображения ((^-пирамида). Доказана ее фундаментальность, оптимальность и реализуемость. Тем самым решена проблема этапа формирования системы признаков (с позиций теории распознавания образов).

4. Разработаны основы алгебры описания изображений. Тем самым решена проблема анализа изображения в условиях априорной неопределенности.

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

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

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

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

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

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

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

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

5. Сформулированы основные правила восстановления трехмерности объекта по его единственному двумерному изображению.

6. Разработаны методы анализа симметричных и регулярных изображений.

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

Реализация результатов работы. Результаты исследований по обработке изображений в условиях априорной неопределенности реализованы в программном продукте НИР "Теоретические исследования и машинное моделирование процесса активного восприятия изображений в условиях априорной неопределенности", финансируемой по программе РФФИ (проект №96-01-00143), а также учебном процессе в Нижегородском государственном техническом университете.

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

МФИ-92, Нижегородская секция (г. Н. Новгород, 1992 г.); 6-ая науч. -техн. конф. "Радиоприем и обработка сигналов" (г. Н. Новгород, 1993г.); науч.-техн. конф. факультета радиоэлектроники и технической кибернетики НГТУ (г. Н. Новгород, 1995, 1996 г.г.); науч.-техн. конф. с международным участием "Математические методы распознавания образов" (г. Пущино, 1995 г.); Международная науч.-техн. конф. " Непрерывно-логические и нейронные сети и модели" (г. Ульяновск, 1995г.); Международная науч.-техн. конф. "Применение математического моделирования для решения задач в науке и технике " (г. Ижевск, 1996 г.); 4-ый Российско - Немецкий открытый семинар "Распознавание образов и понимание изображений" (г. Новгород, 1996 г.).

Публикации. Основное содержание диссертационной работы отражено в 21 печатной работе.

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