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

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

Г' г б о;,

1 6 [>др 1923

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

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

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

05.13.17 - Теоретические основы информатики

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

Н. Новгород 1998

Работа выполнена на кафедре вычислительной гечпикн Нижегородского государственного конического университет

Научный консультант:

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

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

доктор технических наук, профессор Васин ЮЛ'., доктор технических наук, профессор Сойфер В.Л., доктор технических наук, профессор Шольгкн 11.1 .

Ведущая организация: Вычислительный центр Российской Академии наук (г. Москва).

Защита состоится " __1998г. в час на заседании диссертационного совета Д 063 85.02 в Нижегородском государственном техническом университете по адресу. 603600. г. Нижний Новгород, ГСП-41, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке НГТУ Автореферат разослан "

/Л „ 0г

1998г.

Ученый секретарь диссертационного совета

А.П. Иванов

ОБЩАЯ ХАРАКТЕРИСТИКА НАУЧНОГО НАПРАВЛЕНИЯ И ВЫПОЛНЕННЫХ ИССЛЕДОВАНИЙ

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

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

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

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

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

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

На заьцнту выносятся: ■

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

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

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

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

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

ных векторных и топологических векторных пространств, теории распознавания образов, цифровой обработ!си изображений.

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

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

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

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

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

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

6. Разработана модель информационных преобразований изображения в условиях априорной неопределенности последнего в виде последовательных этапов формирование исходного' описания на -пирамиде, выде-" ления структурных элементов и их связей (отношений) на ^/¿-пирамиде, анализа, синтеза и принятия решений на и-пнрамиде. Доказано, что данная модель, во-первых, есть модель активного восстановления (идентификации

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

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

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

изображений на уровне предварительной обработки.

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

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

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

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

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

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

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

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

нар "Распознавание образов и понимание изображений" (г. Новгород, 1996); 8-ой Всероссийской конференции "Математические методы распознавания образов" (г. Москва, 1997); "The 2 International Conference on Microelectronics and Computer Science" (Chisinau, 1997),

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

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

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

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

Первая глава посвящена анализу состояния развития современных систем обработка изображений (СОИ) и состоянию теории распознавания образов в приложении к проблемам распознавания изображений:

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

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

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

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

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

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

Глава 2 посвящена разработке концептуальной модели раскрытия априорной неопределенности изображения. Исходные положения:

1. Изображение есть объект исследования. Поскольку последний априори неопределен, то ставится задача раскрытия неопределенности объекта как черного ящика.

2. Изображение априори принадлежит окружающему миру. Поэтому объективные законы и известные свойства этого мира есть законы и свойства изображения. '

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

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

м _Ь(х,у), ¡Их,у)50сИг 0)

определенная на конечном множестве точек замкнутой двумерной области й евклидова пространства, суммируемая

II И(х,у)<1хс1у <°° (2)

(х,у)еО

и квадратично интегрируемая

|](ц(х,у))2с1хс1у<оо

(х,у)еО

на этом множестве, наделенном свойствами:

1. Замкнутости области определения - для любой М( е М выполняется

0)-

2. Суммируемости - для любой М,еМ существует (2).

3. Упорядоченности - если между точками а, Ь е М1 определено отношение а < Ь, то выполняется (а + с) < (Ь + с), /л < ).Ь для всех а, Ь, с е М,, любых е М и Л > 0.

4. Структурированности: а) семейство открытых кругов сЗ(А,В) < 8 с центром А, где В - любая точка области О, 5 - радиус О, образует базу в С; б) для каждой пары (а,Ь) е М, , где М( - упорядоченное по < множество, имеется зир(а,Ь) и ¡ге^а.Ь), и это справедливо для любых е М.

5. Дискретности: в пространстве - для любых М( е М справедливо р(х,у) ~ {р(ц): (у) ев ; I, ] = 0, ], ...}; во времени - для любой М1 е М на интервале [т,т'] выполняется Д) = Д +- т), если д ^ с(т' -т), где с -скорость распространения действия; т, т' е Тм ; Т» - отрезок времени наблюдения; I е [тУ); Д ~ расстояние между Мь М, , где И б [т,т').

Отсюда следуют два понятия изображения: 1. Статическое изображение (просто изображение) - это функция (Г), определенная в момент 1 6 Тк с Т. 2. Динамическое изображение Ма = (р( I, К^ ) , 0 < I < Тм . Поскольку изображение наделено свойством дискретности, то е М есть решетчатая (сеточная) функция, определенная в квадратной (в условиях априорной неопределенности при отсутствии предпочтения естественно принять равномерную сетку и квадратную область определения) области О = N х N (поле зрения). Тогда все множество изображений конечно и имеет мощность к„,„ _ где р _ макхимальное число уровней градаций яркости. Следова-

тельно все многообразие изображении ограничено условным объемом М, е Мс V з N х N х Р. Полученный результат позволяет использовать аппарат алгебры моделей.

Предложение 1. Любое множество Мс\':

образует группу О = <М; +> н является подпространством *Г{М) скалярного поля '6", где £(М) - тело действительных чисел на бинарных операциях т: М х М—> М, га = { •};

есть подпространство ЩМ) векторного пространства ЭЬ. над телом <?(М) с метрикой с!(а,Ь) = |] а - Ь ||, где а, Ь - вектора из .®(М),

есть структура Ь = < М; и,П, еь е0 >, если на М определены бинарные операции и, П с соответствующей аксиоматикой, единичный и нулевой элементы и отношение порядка р ( < );

есть подпространство ЩМ) топологического пространства ¿¡Г с базой на семействе открытых областей, изоморфное на классы упорядоченных векторных пространств и направленных векторных решеток.

В п.2.2 проблематика раскрытия неопределенности рассмотрена с позиций теоретико-множественного подхода. Используя понятие покрытия А конечного множества М получена иерархия уровней исходного описания изображения М в виде -пирамиды,.вершиной которой является единичный элемент е„ - образ предшествующего уровня, полученный в результате отображения а" : М -> ет , где и* = {(а[), а) е А х Ао: ад = н'(а)}, Ао = {ар,а^,...,ар}, ет = ат, { 1 =1,..., т }.

Теорема 1 (необходимость). Пусть А, = {а-: ] еС,} и А1 с М, А, е А, где р.(х,у) = а- ¥(х,у), j б О,с О . Тогда представление произвольного М с V в виде 0'= { £5^: 1 =1,..., т } на последовательностях {а]}, сходящихся к а'0 = || ц(х,у)с1хс1у. VI, (3)

(Х.у)бО;

фундаментально.

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

Рассматривая изображение с позиций теории групп получаем: 1) в условиях априорной неопределенности элементы множества М находятся в отношении эквивалентности есМ к М, 2) линейный оператор есть

ш _|1(х,у), 11:(х,у)еО;СО (4)

0, ¡Г(х,у) ей,

по всем О; £ С; 3) существует преобразование обратное (3), т.е. —п где преобразованию »» можно поставить в соответствие единственный линейный оператор на непересекающихся подобластях G1',Gf с О;

[ 1(х,у), ^(х,у)бШ (5)

1 \-1(х,у),

Ю

Теорема 2 (достаточность). Пусть McV. Тогда представление М в виде £Р- {!?,: i =1,..., m }, где = еш, достаточно для раскрытия априорной неопределенности М с помощью единственной бинарной операции г, (М) = «<М2) - ^(Mj), где f/<Mi), //<М2) определены по (3).

Теорема 3 (реализуемость). Пусть на Мс V выполняется отношение эквивалентности. Тогда подгруппы

< „, > = { <rP, </•', ... , <t<P~l } , < « > = { ... , V»"1 } (6) являются наименьшими и фундаментальными с точностью до изоморфизма, а каждый их элемент элементарен и однотипен на операторах (4), (5).

В п.2.3 раскрытие неопределенности рассмотрено с позиций системного анализа. Используя понятия вероятностного пространства А.Н. Колмогорова, вероятностной меры, свойств изображения (опред.1) показано, что, в силу Мс V, справедливо:

1) в условиях априорной неопределенности процесс ее раскрытия есть процесс дихотомии области определения изображения на равные по площади подобласти (S(Gj) = const Vi) с использованием однородной на G процедуры (3), позволяющей представить объект исследования набором значений (m(Gj)} по любой G1 с G

m(_G0 =р(х',у')-S(G,) =jj n(x,y)dxdy (?)

и это представление достоверно;

2) функция вида (7) определяет массу (визуальную массу) изображения, определенную в подобласти Gi с G, как меру, с соответствующей аксиоматикой;

3) отношение меры m = m(G) к площади всей области S(G) есть математическое ожидание случайной равномерно-распределенной функции р(х,у) = S(G)"1 с вероятностью P(G) = 1;

4) дихотомия области G с последующим определением (7) по всем Gj есть, с одной стороны, разложение ц(х,у) на множестве математических ожиданий {ц(х!,,Уо)}. с ДРУг°й стороны, восстановление аддитивной функции (массы) m(G) по ее шютности (плотности массы) ц(х,у) с представлением вида {nij} е {rn(Gj)}.

Используя понятие сложности любой алгоритмической системы по АН. Колмогорову, показано, что множество операторов {V,}, каждый из которых реализует бинарную операцию на базе (5), есть множество минимального состава мощности 2г°, где п - число аргументов. Используя понятия системы произвольной природы по У. Эшбн, организации системы по К. Шеннону, а также исходя из полученных выше свойств изображения, вводится понятие модели неопределенности.

Определение 2. Пусть М = {а,: 4 = 1,к}.Моделью неопределетаости - изображения М называется описание

Ж: р; = р VI; Н = Нт = 1о§к;^=0; (а^е^у, (8) где р = 1/к - условие равномерного распределения; Н, Нт - текущая и максимальная энтропия (сложность системы); б = (Н - Нш) - организация системы, как реализованная неопределенность; е - отношение эквивалентности.

В п.2.4- рассмотрена задача обработки изображения на базе полученных результатов. При этом под обработкой (обработкой в узком смысле) понимается необходимое и достаточное множество преобразований {««}

для задачи формирования исходного описания М с V. Решение задачи разбито на этапы - исследование точности, размерности, связности и оптимальности ^-пирамиды. В соответствии с (7) каждый элемент множества М есть аддитивная функция своей области С, с в, а б соответствии с (3) -представляет свою область 01 в точке В - центре области С,. Тогда: 1) в силу теоремы Гаусса о гармонических функциях преобразование (7) есть отображение вида ш: М $Р с , где Сш - бесконечно гладкое многообразие; 2) каждый элемент множества А® по А.Н. Колмогорову является достоверной оценкой своей Е-окрестности с точностью до е (е-точная оценка), а покрытие А, реализующее разбиение, есть £-покрытие с абсолютной энтропией Колмогорова

. Н,(М) = 1о8ЩМ), (9)

где "НЕ(М) - число элементов покрытия.

Теорема 4 (достоверность). Пусть {ш,} г {т(0,)} определено в своих е-окрестностях. Тогда отображение : М -> а. С®, достоверно, £-точно и имеет е-энтропию по (9).

Преобразование (7), реализующее отображение «*: М -> ¡Р с. С", является основным и единственным на этапе исходного описания. Названо О-преобразованием и наделено следующими основными свойствами: универсальность - применимость к объектам любой природы и размерности, удовлетворяющих относительно слабым ограничениям опред.1; фундаментальность, реализуемость и достаточность (теоремы 1 - 3); имеет обратное преобразование, которым является внешнее дифференцирование (в смысле теоремы Стокса); реализует отображение в действительное пространство и имеет минимально возможную вычислительную сложность - это сложность реализации операции сложения.. ' -

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

лено умножение А- В = {(а • Ь): аеА, Ье В}. Пусть М - группа. Тогда отображение иг М вм есть мономорфизм группы М в группу <2М; ■ > = , а семейство подмножеств вм = {//'(к): А с М) есть классы эквивалентности для множества М, разделенного на 4 подмножества в Я2, каждому из которых может быть поставлена в соответствие масса (7). Если М - множество точек, то Ом - необходимое множество подмножеств, где может находиться одна точка, принадлежащая М. Применяя аналогичный подход к множеству 2МхМ всех подмножеств множества в = М х М, получаем, что отображение и* . § -> есть мономорфизм группы 8 в группу

< 25', ->=0МхМ. С одной стороны, семейство подмножеств вМхМ - { «/»(А) : А с Б } есть классы эквивалентности для Б, разделенного на 4x4 подмножества, каждому из которых может быть поставлено в соответствие масса (7). С другой стороны, группа О МхМ есть группа всех бинарных отношений на множестве М с законом умножения отношений р] • р^. Поэтому, если М - множество точек, а О МхМ- необходимое множество подмножеств, где могут находиться две точки множества М, каждая из которых может находиться в любом подмножестве множества Ом, то 0М);М есть достаточное множество подмножеств, позволяющее выявить все отношения на множестве М.

Итак, для выявления всех отношений на М необходимо и достаточно 1 б-ти мерного упорядоченного пространства, а порядок изоморфных композиционных рядов (б) равен 16. Это соответствует 16 вариантам разбиения множества Мс V, включая нулевое -разбиение. В результате имеем 16-ти уровневую пирамиду ё? с С°° исходного описания, как периодическую группу

^=<с>={{1}= ..:, 0ъ=скьм}. сю)

где {1} есть еш; каждый £Р\ есть результат разбиения исходного М для выявления одного класса отношений с использованием обратного преобразования 1>; в МхМ есть результат разбиения М на 4 х 4 подмножества.

Лемма 1. Пусть £>(0МхМ)- векторное пространство размерности 16. Пусть »«' = гп^ — - преобразование, определяющее направление по 1 в векторном пространстве между массами, полученными в результате дихотомии ш,. Тогда множество

л (11) •

есть канонический базис пространства {е,: 1 = 1,..., 16}

Пусть (11) есть базис векторного пространства Л16. Тогда: а) векторная сумма ц(х,у) = ще! + ... + ЦкЛ'к, называется разложением изображения

Мс Ув системе координат {е,}; б) упорядоченное множество (р^, как результат (¿-преобразования, называется представлением (исходным описанием) изображения в системе координат {е^; в) этап отображения и>: {т;} -» {рз}, где {т^е £Р, - этап анализа; г) пирамида (11) есть приз-

наковая пирамида.

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

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

Теорема 5 (оптимальность). Пусть МсУ и его описание есть (8). Пусть глобальная функция качества.имеет вид £(иор[) = шах (Яи, 8(и)) =

Нш. Тогда:

1. Иерархия ^(10) есть результат оптимальной декомпозиции с межу-ровневой функцией.

2. Иерархия Л (11) есть результат оптимальной декомпозиции с внутриуровневой функцией

Если результат преобразования и> определить как структурный элемент множества М (либо любого его подмножества), то: 1) преобразование и-- (7) глобально оптимально, абсолютно устойчиво и раскрывает неопределенность М на уровне одного структурного элемента; 2) преобразование п глобально оптимально по управляющему воздействию и выявляет комбинаторную структуру 1-го уровня описания М.

Определение 3. Система, реализующая пирамиды ¿Р, Ж и необходимо обеспечивающая на множествах преобразований <м»>, <-?>> оптимальность по в(иор|) = шах Б(и)) = Нт на каждом шаге преобразования, называется самоорганизующейся.

Заключительным этапом раскрытия неопределенности является рес:.,-ние задачи реализации т.е. задачи установления соответствия внутренней

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

1. Формирование исходного описания ((^-преобразование) - ёР\ М -> {ш}, где & = <гя>. •

2. Анализ - Ж\ {ш} —> {ц}, где Ж = <п>. При этом в силу замкнутости преобразований 1п ~ ■»>"' {д} ;Мв базисе'(1 ]).

3. Синтез - ^Г: (ц} ->М, такой, что М = М на множестве {ц}.

В главе 3 рассмотрен этап анализа изображения, целью которого является получение описания {р^ в базисе (11). Для этого в п.3.1 решается задача конструктивного определения композиционного ряда <п>, т.е. построения множества операторов по структуре (5), выявляющих множество структур на С"-многообразии, как исходном описании. Пусть множество М определено на сетке С = сху = N х N. Тогда можно построить горизонтальные 5(к,х) = (а(у): ¿ех} и вертикальные 5(к,у) = (а(у): jey} кортежи (к - параметр кортежа) элементов - атомов, каждый из которых а(у) есть {1} = зир р(у), либо {0} = - {1} = {-1} = - вир Результатом построения является комплекс (иерархия) симплексов (симплекс - объедине-- ние атомов)

= = Щ = = • ". О2)

где - фильтр - матрица, полученная на кортежах с к = 4 и операции

1 } [-Зу, ^^Бла^

(порядок нумерации "фильтров произволен); С?^ - (^-фильтр, реализующий преобразование *» по направлению х ¡- раз, по направлению у j- раз ( преобразование & реализуется по направлению х, либо у столько раз сколько раз происходит изменение знака {1}, {-1} на элементах кортежа по этому направлению). Показано, что множество образует пирамиду (Р-

пирамиду), изоморфно множеству элементов ряда <»»> и определяет базис пространства и (рис. 1)

{<2х.у} = {}; л»"*'*.*'*; *<ч.

2 3.2 3 3 2 , ' ^

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

где (0^,02) " паРа подобластей как результат к-ой дихотомии области в,

есть представление {р,} изображения М с V.

Теорема 6. Пусть {Р^ - комплекс симплексов, являющийся реализацией базиса (И). Тогда: 1) любые две реализации базиса изоморфны; 2) каждое М с-У может быть представлено на комплексе как упорядоченное множество {ц,}а ^т) е Я (14).

Следствие 1 (изоморфизм изображений). Два изображения топологически эквивалентны, если равны их разложения на (13), т.е.

М1~М2о{р!} = {р,2}. (15)

(^-пирамида является объ-у единением 9> -, Л -пирамид и определена как функциональная пирамидальная модель' раскрытия априорной неопределенности изображения (рис. 1).

В п.3.2 с позиций общесистемных законов адекватности и инвариантности доказывается универсальность <3 - пирамиды. Для этого исследуются вопросы полноты модели (п.3.2.1), устойчивости (п.3.2.2) и чувствительности (п.3.2.3) описания на пирамидальной модели. Проблема полноты рассмотрена с позиций удо-, влетворения полной системе законов сохранения. Пусть изображение М с V есть система материальных точек с массами {^г £ =1,11} и координатами (х;,у,). Условие М с V означает изолированность системы материальных точек. Условие, что множество {р,} - множество масс, есть условие однородности точек множества М.

Тогда — = 0, т = =сопб1 есть интегральный закон сохранения ^ 1=1

массы. Следовательно, любой оператор е VI инвариантен к любым видам преобразований ц(х,у), где (х,у) е Оь не нарушающим интегральный закон сохранения массы. Поскольку последний не зависит от размерности

Рис. 1

системы масс, то и -пирамида инвариантна к размерности объекта М тогда и только тогда, когда Мс V.

Показано, что для системы масс материальных точек {т;} упорядоченных в пространстве R2 и образующих несвязанную, свободную систему масс (где определены по (7), упорядочены на матрице 4x4) справедливо: каждый Fj е {Fi} локализует достоверно и е-точно глобальное движение центра масс изображения по направлению t относительно центра изображения и инвариантен по ортогональному к £ - направлению; каждому Fj е

{Fi} соответствует дифференциальный оператор вида V: = — = е1, вы-

di ex'

являющий отношение между элементами системы {щ} достоверно и е-точно; три группы фильтров (Fi, F2, F3), (F4, F5, Fs), (F9, F10, F15) с базисами Ox, «у, *>%), (»ex. ("'.. «у, t'ly) соответственно образуют полную

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

вида 1% = = о, где <р(Ао) - гармоническая функция, принадлежащая

d£

Cw - многообразию.

Используя стандартный подход анализа, устойчивости с помощью функции Ляпунова (функции расстояния), показано, что: I) преобразование (3) глобально асимптотически устойчиво по Ляпунову, т.е. траектории движений (возможных) на множестве М абсолютно сходятся в точку равновесия в своих подобластях G, с G; 2) каждый фильтр Fj е {Fj}, применяемый к входному множеству М, реализует интегро - дифференциальное преобразование вида

q — -»»°««= d ° J 0 б)

с

и является функционалом, выявляющим достоверно и е-точно.единственное движение из множества движений — = f. (х,у), — = fv (х, у) в облас-

dt dt

ти G с центром в точке Ао, в которую помещено начало системы координат; 3) каждый фильтр Fj е {Fj} имеет два направления - направление инвариантности (направление s, по которому Fi 6 Q (V; е JC) инвариантен к преобразованию F, (s) = Fi (s + а), где а - const) и ортогональное ему направление чувствительности.

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

ходной характеристики произвольной системы S путем подачи на ее вход ■ единичной функции от некоторой управляющей системы "Ж

Теорема 7 (единственность). Пусть и\ i? - однородные функции системы Ж. Пусть каждый фильтр F¡ 6 Q, где i =1,15, удовлетворяет (16). Пусть множество {Fí: i = 0,15} есть (13). Тогда :

1. Конечное множество {F¡: i = 1,15} есть множество функций чувствительности.

2. Каждый фильтр F,, где i = 1,15, выявляет дифференциальную структуру по одному из направлений

" г д>~1 Л д г d¡~1 Л дТ г d¡" ъ

дх дх^ду' ду дхкду'~ ' бхду^дк^ду'-1"' <17)

где k, г = U, к + г = 6, j = 1,6.

3. Разложение изображения ц(х,у), заданного в области G с-центром в, точке х = у = 0, есть

15

ц(х,у) = ц0+£^ , (18)

¡=i

на множестве базисных функций {ei} (11), определенных по (17).

4. Представления (17), (18) однозначны, достоверны, £-точны и являются фундаментальными представлениями в условиях априорной неопределенности. 1.

В п.3.3 рассмотрены вопросы формирования описания изображения на множестве {ц,} е R. Для этого использован подход, применяемый в теории аналитических функций при анализе особых точек (подход допустим в силу ёР с Сю). Исходя из условия неразрывности Даламбера -Эйлера установлено соответствие направлений чувствительности и инвариантности множества фильтров с линиями тока и потенциала.

Теорема 8 (интерпретация). Пусть {F,} определено по (12) как множество преобразований (16). Тогда распределение атомов в составе каждого симплекса Fi соответствует интегральной кривой i-ro решения системы дифференциальных уравнений и это соответствие е-точно.

Итак, каждый фильтр конструктивно содержит в себе интегральную кривую движения (например, фильтру F6 или F7 s-близка, т.е. близка с точностью до касательных парабола, F13 или Fu - строфоида (рис. 2)) и если выполняется условие ln¡l= |io, то эта кривая (отражающая распределение масс) есть дифференциальная структура, принадлежащая анализируемому изображению и может быть определена как изобразительное описание последнего.

В силу, независимости множества преобразований (13) каждое движение принадлежит независимому направлению и задает вектор этого движе-

Рис. 2

V

ния. Поскольку число таких векторов равно 15 (если не считать нуль-вектор), то имеем 15 линейно'независимых векторов, определяющих 15-ти мерное векторное поле Киллинга. Тогда композиционные ряды (6) раскрывают неопределенность 5-ти мерного С°- многообразия достоверно и е-точно и являются его векторной моделью.

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

d'(p(x,y) _ (с-const О9)

дккдут " 1°

Решением для (19) является трехмерная поверх. носгь z = ф(х,у). Поэтому каждый двумерный :С>|'->мг*т' фильтр F, б Q можно рассматривать как результат ортогонального проектирования 3-х мерной поверхности на плоскость хОу, рассекающую поверхность, с учетом расположения поверхности над плоскостью (рис. 3).

Теорема 9 (восстановление). Пусть каждый фильтр Fi из {Fj} реализует преобразование (17), где ф(х,у) е С-многообразию. Тогда Fi = PrzS(x,y,z), где S(x,y,z) есть трехмерная поверхность.

Глава 4 посвящена решению проблемы синтеза изображений - .Л': {pi} М, т.е. необходимо найти систему правил JT, позволяющих по результату разложения изображения М на Q-пирамиде построить такое изображение М (идеальное изображение), которое £ - тождественно исходному М = М.

В п.4.1 рассмотрены вопросы формализации процесса описания изображения, представленного множеством {р,}. Вводится понятие множества операторов (матриц размера 4x4) {Vj} = V, состоящих "из 0, '1 и упорядоченных в соответствии с конструктивным определением множества {Fi} (рис. 1). При этом V; = V(ni), т.е. щ > 0 => Vj, Ц) < 0 => Vi, где ==> означает "следует". Для элементов матриц V;, Vj е V вводятся операции сложения и умножения .

[aL)+UL]=[aL+aU[aL]'raim] = [aL-aL,] Vn,m, (20) такие, что для них справедливы операции рулевой алгебры. Тогда-= V, Ф Vj есть прямая сумма (покрытие) со сложением й умножением по (20).

Рис. 3

Определение 4, Алгеброй описания изображения (просто алгеброй изображения) М с V называется класс -Л(У) объектов {V(p,)}, в котором: 1) для любых V(uí) определены бинарные операции (20) с соответствующей аксиоматикой и существует обратный элемент V¡ +V¡= ei , Vj • V¿= eo; 2) V,j принадлежит (замкнутость); 3) определены нулевой и единичный элементы e¡ = V0 = [1] , eo = V0 = [0]; 4) любому M соответствует

f(Vo(Hü),Vl(pi), ... ,Vl5(pi5)). _ .

Утверждение 1. Пусть {|p,[: i =1,15} - результат разложения изображения М. Тогда долевое участие каждого V¿, принадлежащего множеству {V,: i =1,15} однозначно распределению масс |pi| е {1pí[}.

Утверждение 2. Пусть множество {p¡: i = 1,15} однородно, т.е. = const Vpi ^ 0, и выполняется {р,} {Vi}, где {V¡: i = 1,15}. Тогда условия

ylHil = i Ы = 1 vi (21)

Tfo fío

являются необходимыми и достаточными для описания изображения соответственно с помощью операций сложения и умножения операторов V¡, для которых pi * 0, т.е.

i i где {V¡} - множество операторов, участвующих в операции (22).

Показано, что алгебра изображения есть булева алгебра, для которой выполняется соответствие < V; +, • ><->■< V; ЦП >. Тем самым введена возможность расширения конечного множества одноместных операций, реализуемых фильтром {Q'¿}, и возможность построения предикатов P({Vj}), выявляющих любые m-арные отношения на конечном множестве ' бинарных отношений 4

В п.4.2 вводится понятие грамматики описания изображения (Г) в алгебре как системы правил на операциях логического "и", "или" объединения предикатов P({Vj}) = p¡ из {P¡} в предложения. Показано, что операции -

1 > i

на множестве {Vj} достоверно локализует общие области в переменных V¡ по нулям к единицам соответственно. Вводится понятие полной группы на множестве {Vj}, упорядоченном на решетке V(x,y) (рис. 1).

Определение 5. Пусть {V¡} - произвольное подмножество прямых и (или) инверсных операторов, принадлежащих V. Подмножество {V¡} называется полной группой Р„ = ({Vi}), если выполняются условия

2>i=e„ nv¡ =Р*Р»- <24)

Вводится понятие семейства групп (8а = {Рш} для полных групп), на которых и определена грамматика.

Определение 6. Пусть: {ц;} - результат разложения изображения М в базисе (2.93); {V,} - множество операторов, для которых щ*0. Тогда предложение Р = Р({У^) е Г называется изобразительным описанием М.

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

<25>

называется вектор М = {ц,(У0} в базисе (25). Вводится понятие графа (и орграфа) на решетке У(х,у) и исследуются свойства графов групп. Разработана методология обнаружения и описания выделенных групп:

1. Пусть {V;} е Рп. Тогда М = Рш если выполняется условие ||Д,| = ро VI.

2. Пусть V;, 'Vj е V, где 1 * ^ I,) * 0. Тогда всегда существует третий оператор VI е V, где к * 0, обеспечивающий замкнутость группы (УьУ^УО относительно условия (24).

3. Пусть (У^у^Уь) - полная группа. Тогда число инверсных операторов в составе группы четно и описания группы вида УтУд = У„УР = УтУр = Рп тождественны, минимальны и не зависят от упорядоченности операторов в составе группы (п.4.4),

4. Пусть (Ут,УшУр) - полная группа. Тогда для операторов группы выполняется тождество Р=УгаУп+ Ут Уа = (УтУп+- Уш Уа )Ур и любая пара операторов связана с третьим предикатамиУшУв+Ут V,, = Ур, Ут Уп+Ут Уп = Ур.

5. Упорядоченное множество {У^.У^У,}, где любые три оператора не образуют полной группы, является замкнутой группой Р* тогда и только тогда, когда число инверсных операторов множества нечетно.

6. Пусть {VI} е Р5. В этом случае М = Р, тогда и только тогда, когда выполняется условие |ц,| = ц < р0 УУ, е Р,, Ур.( ф 0.

7. Пусть {У;,%,Ук,Уг} £ Р„ Тогда описания Р, = (V; + Уз)(Ук + Уг) = ViVj + УкУг > (У; + Ук)(У] +У,) в У,Ук + У3У, з У;УГ 4- У,Ук 3 (V; + Уг)(^ + Ук) тождествеш1Ы и не зависят от упорядоченности операторов в составе группы. Здесь {VI: I = у,к,г} - прямые и инверсные операторы, удовлетворяющие правилу 5.

8. Пусть Р5= (УьУ|,Ук,Уг) - замкнутая группа. Тогда Р, допускает описания вида (п.4.5.4) Р, = УпЛ^+У^У, = У„У;Ук+Уа^Уг = Ур^Ук + Ур У,УГ, где (УШ,У„,У„) е Рц - полная, внешняя для Р5 группа.

В п.4.4 рассматривается многообразие групп на множестве упорядоченном на решетке У(х,у) и проводится классификация множества полных групп. Выделены два класса - скалярные (например, группы на операторах (УьУьУвХ (У2,У5,Ую), (Уз.Ув.Уи), названные центральными) и векторные (например - (V 1,У2,Уз), (Уз,У1з,У14), (УьУпУгз), принадлежащие подмножеству центральных) группы. Вводятся понятия предикатов обнаружения, различения, совпадения и различия. Предикат Ро называется предикатом обнаружения, если при минимальном числе операторов на операции объединения (сложения) позволяют локализовать область (или подобласть) нахождения объекта (точки - атома или совокупности однородных (по критерию принадлежности еь либо ео) точек). Предикат Р„ называется предикатом различения (собственно локализации), если при минимальном числе операторов на операции пересечения (умножения) позволяет локализовать группу однородных точек, названных компактом. Показывается, что: \'о - оператор обнаружения любой совокупности точек "в области определения, если цо # 0, т.е. Ро(Уо) =И (истина); каждый У^ е У(х,у) есть оператор обнаружения и различения 8-и связанных точек (атомов) тогда и только тогда, когда для V; выполняется условие (21) (правое).

Определение 7. Пусть Рь Р2 - группы. Тогда предикатами совпадения и различия на элементах однородности матрицы 4x4 называются предикаты вида Рс = Р1Р2, Рр = Р1Р2 + РХР2. Пусть {РЛ = Р - множество групп. Пусть определены операции Рс, Рр на Р. Тогда алгебраическая структура ДР) = < Р; Рс, Рр > называется алгеброй групп на решетке У(х,у).

В п.4.5 рассмотрены вопросы формирования эталона. Поскольку результат действия -пирамиды принадлежит Л и наделен свойствами меры, то масса (визуальная) наделена необходимыми свойствами критерия однородности (гипотеза компактности в теории распознавания). Поэтому до- ■ пустимы следующие меры (п.4.5.4): 1) мера отклонения образа О изображения М от эталона От - это предикат Рр = ООт+ О От (4.72); 2) мера совпадения образа О с От - это предикат Рс - ООх = От. Здесь под образом изображения понимается (п.4.5.1) описание'в виде Р({У1}) на операциях (22).

Определение 8. Пусть {От} = М - множество эталонов. В этом случае этап он Оте М и образ О з М с соответствующими визуальными массами рт, ц0 компактны тогда и только тогда, когда выполняется условие пи'пЬ -ц |=> {тш Р., тахР }. (26)

0гем' 0 11 0тбм р ог ем

В п.4.5.1 с позиций разработанных методов синтеза формализуются некоторые интуитивные понятия этапа понимания СОИ. В частности понятия образа (см. выше) и остова. Пусть подмножество однородных (по е^ элементов матрицы 4x4, образует кортеж по любому направлению х, у, ху (или х = -у, т.е. -ху), т.е. сегмент с критерием 8-ми связности, и пусть

P({V,}) - описание множества сегментов и P({Vi}) s M. Тогда а) сегменты образуют сильносвязанную структурную модель изображения, если они связаны по критерию 8-и связности, и слабосвязанную структурную модель изображения в противном случае; б) множество остовов сегментов, принадлежащих описанию, называется остовом образа изображения (или скелетом изображения). Установлено соответствие остовов множества {Vi} на решетке V(x,y) с касательными к соответствующим интегральным кривым.

В п.4.5.2 исследуются свойства алгебры групп.

Лемма 2. Любая пара непересекающихся полных групп (Р„, = V,Vj\'\, Pnj = VraVnVP) на множестве операторов {V,} ортогональна.

Свойство 1. Пусть множество операторов V = {V;: i = 1,15} принадлежит двумерной решетке V(x,y). Тогда: а) число непересекающихся полных групп равно 5; б) множество {P„i. i = 1,5} полно на множестве вершин решетки V(x,y); в) через любую вершину решетки про-Д, ходит семь полных групп (их орграфов), пересекающихся на этой вершине (рис. 4).

Поскольку множество непересекающихся полных групп (Pni'. i = 1,5} полно, то оно определяет некоторое семейство Snb = S(Pn), которое назовем семейством базисных полных групп. Показано, что S„b есть группа по условию (24) (левому).

Лемма 3. Пусть {PQi:"i = 1,5} б S0b. Тогда: I. Любое подмножество {Рч-: j = 1,3} с {Pni} есть проекция 3-х мерного базиса на V(x,y). 2. Описания подмножества {Рщ} вида

К = = (27)

j-1. ¿=1

замкнуты Pv + Pv = е; и минимальны. 3. Предикат (предложение) Рг есть группа (базисная группа) на множестве предикатов (слов) {P„j: j = 1,3}.

На рис. 5 приведен пример базисной группы Ру, где Ov - образ группы. С позиций алгебры моделей группа Р„ - это группа над множеством полных групп и поле над множеством операторов, т.е., если каждая полная группа на тройке своих операторов задает трехмерный базис* векторного пространства, то каждая тройка ортогональных полных групп есть 3-х мерный базис нового пространства, как объединения трех 3-х мерных векторных пространств, каждое из которых ортогонально остальным. Аналогично, если алгебра описания изображения определена на множестве {Vi}, то алгебра групп определена на более крупном комплексе - множестве групп.

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

р„,

Но =10;

щ = 2 VV, е = 1,2,3} ■ >1

Рис.5

Лемма 4. Пусть задано множество {Рп, Ра, Р„ Р£}. Тогда:

1) отношение между образами на любом наборе прямых, инверсных операторов в составе Рп, Р8, удовлетворяющих необходимым требованиям определения групп, есть отношение вида 0(РЕ) з 0(РД 0(Р„) => 0(Р5) V 0(РД 0(Р,)с0(Р^0(У(

2) иерархия значений визуальных масс образов множества имеет вид Цо(Р„) > роО^) = ц0( Р8) > йо(Рп).

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

Теорема 10. Семейство 5(Р5,Рп) фундаментально и замкнуто на множестве {Рм}}.

Следствие-2. Для описания произвольного бинарного образа 0(М) 'йз множества мощности 24x4 на операции ©¡Рщ необходима тройка полных

групп (Рш,РчЛк). <

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

В п.5.1 рассматривается информационная модель принятия решений. Пусть в, - подобласть поля зрения в (п.5.1.1). Тогда применение пирамиды ко всему изображению, определенному в О;, с получением вектора М(0,) (25), есть £-точное разложение изображения М(С0 с: М(в) у ровня 1 Поэтому применение (^-пирамиды ко всему полю С есть разложение уровня 0 (либо 1). Уточнения изображения М могут быть (в общем случае) продолжены до предела разрешения (до пиксела исходного изображения).

Утверждение 3. Пусть <3 есть (13) и удовлетворяет условиям теоремы 7. Тогда множество <3 необходимо и достаточно для достоверного и е-точного раскрытия априорной неопределенности в любой подобласти в, с О области определения изображения и минимально необходимо для раскрытия неопределенности с любой заданной точностью.

Результатом является многоуровневая иерархия (и-пирамида) и(<3) = ис(и|(и:(... ЩС!)) ■• ), где 1Л(0) = {М(Ок)} - множество разложений изоб-

ражения М, определенного в области в, с Б; М(Ок) = {рОк - разложение изображения М, определенного в подобласти Ок, на (^-пирамиде; См ^ в.

Подмножество изображений {Мк} с. М, удовлетворяющих М; ~ М^ <=> 0(М,) = О(М)), где 0(М;), 0(М|) - описания (бинарные) образов в базисе (25) определим точечным классом У;(О,(М0) изображений с эталонным изображением От(М,) на полутоновой матрице 4x4 |[гпу((. Тогда критерий однородности имеет вид

М1 ~М2 ^О}, ~ {щ: 1 * 0}2 <=> 0(М,) з 0(М2). (28)

Свойство 2. Пусть М„ М^ - изображения уровней ¡, 3 и-пирамиды. Пусть У;(От(М)) = У,СМ) е У(М) - класс изображения М] на множестве классов У(М) и для М„ М^ справедливо (28). Тогда М^ ~ М; о (VI;, М^ е У,(М).

Определение 9. Пусть 0;(М), 0|(М) - образы изображений М,, М,, не удовлетворяющие (28). Подмножество изображений {Мк} с М, удовлетворяющих 0,(М) ~ О/М) « (0,(М), ОДМ) е Б^Л)) л (Рс(0,(М), О/М)) = О^Э,)) называется классом эталона У;(От(5)) (размытым классом) подсемейства 8,(Р5,Р„) е 3(Р;,Ра) с эталоном СЦ^,) е М. Пространство 3>п(Ч) с базисом (Уь I = 1,15}, определенным по (25), называется пространством классов.

Каждый размытый класс - подмножество точечных классов изображений, объединенных критерием однородности на эталоне.

В п.5.1.2 исследованы' свойства пространства классов и показано, что: 55°(У) замкнуто 8(РВ,РП) с с 4 х 4 х Р, где Р - максимальное число градаций яркости; 35П(У) есть точечное риманово пространство с ортогональным локальным базисом (25), где множеству {Рщ} соответствует множество {^?(У)}; 3>"(У) изоморфно С"-многообразию на множестве • определяющем множество единственных геодезических линий этого пространства; и-пирамида с базовым представлением на (^-пирамиде Св- согласована. ' .

В п.5.1.3 рассмотрен собственно процесс принятия решения. Семейство 5(Р5,Рп) задает иерархию уровней описания изображения М.и соответствующую ей иерархию принятия решения в пределах одного ьго уровня и-пирамиды по критерию (28) на множестве эталонов (СЦБк)} семейства. Результатом является иерархия уровней описания - 1Г-дерево, где ЩМ) -дерево описания изображения М на мзм уровне.

Пусть {У^, {Рщ} - алфавиты описания изображения М. Первый есть алфавит букв, второй - алфавит слов. Тогда любое изображение М есть предложение на множествах {V,}, {Рш}, объединенных операцией В результате получаем модель преобразований изображения М, представленного множеством {ц,} со свойствами: конечности (сходимости); однород-

ности; целостности; одномоментности; универсальности; врожденности. Показано, что модель раскрытия априорной неопределенности на базе системы (<3,Ц)-пирамид - это информационная модель врожденных механизмов зрительного восприятия, а множества {V,}, {Рп;} есть множество врожденных эталонов.

В п.5.2 исследуются симметрические свойства элементов алгебры изображений с позиций кристаллографии. Показано (п.5.2.1), что: множество {Р;} <г> {"У;} есть множество единственных с точностью до изоморфизма точечных групп симметрии 8С; множество {У;: 1 = 1,15} есть множество единственных с точностью до изоморфизма точечных групп антисимметрии Ба; каждый оператор множества {V;: [ = 1,15}, как двухцветный ( бинарный) образ, необходимо содержит в себе элементы семейств 5„ Бс; множество {V;} содержит операторы с правой и левой винтовой осью симметрии; на множестве {У;} существует подмножество предельных точечных групп симметрии (групп Кюри).

Теорема 11. Множество {У^ есть множество единственных с точностью до изоморфизма предельных точечных групп симметрии.

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

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

Следствие 3. Пусть -^УУ алгебра описания изображения. Тогда на любом уровне Ь'-пирамиды есть алгебра взаимодействия групп симметрии {V,}. . ..

Теорема 12 (замкнутость взаимодействия). Пусть Уь Vj - две взаимодействующие группы симметрии. Тогда необходимо существует третья группа Ук, замыкающая первые две по условию (24) (левому в (24)).

Показано, что мощность множества полных групп Рп = {Рш} с {РШ(У)} на множестве прямых операторов равна 35, из которых: 11 - центральные (4 - скалярные и 7 - векторные); 24 - производные (два подмножества (по 9), порожденных операторами из Р„(х) = У^Уэ, Р„(у) = У^зУю и б групп, связывающих Рп(х), Р„(у)).

Утверждение 4. Каждая полная группа Рш выявляет (распознает) новое свойство объекта.

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

Лемма 5. Множество Рп определяет пространство ЙП(Р), где Р„о -нуль-подпространство.

Полученный результат означает, что каждая группа Рщ из Р„ имеет собственные направления чувствительности н инвариантности в пространстве .7)"(Р).

Теорема 13. Множество {Рт: 1 = 1,34} - множество групп движений относительно Рпо-

Предложение 2. Пусть Р„ = {Рг,,: 1 = 1,35} - множество полных групп на множестве прямых операторов. Тогда Р„(х), Р„(у), Рп(ху) - это группы направлений (группы роста) по х, у, ху а оставшиеся группы {Р^} с Р„ есть нейтральные крнстатлографические группы.

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

инверсных операторов имеет моделью в 3? бинарный куб в координатах х, у, г на операции (23), в который вписаны две ортогональные тригональные пирамиды (рис. 6). Последняя определена как II-ячейка.

Следствие 4. и-ячейка есть кристаллографическая модель полной группы. Пусть {РШ(У, V)}, {11;} - множества полных групп и и-ячеёк соответственно. Тогда мощности этих подмножеств равны соответственно 280 и 35.

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

Пусгь Рю, Рщ • две полные группы с соответствующими им Кубическими оболочками. Кубические оболочки групп называются связанными, если они совпадают на вершинах одной из главных диагоналей. Поскольку в один куб (исходный) можно вписать по его четырем главным диагоналям четыре других куба, связанных с исходным, то получаем систему та пяти связанных кубических оболочек. Так как на множестве полных групп мощности 35 существует пять ортогональных полных групп (свойство 1), то система из пяти связанных 17-ячеек (Ц-система) есть модель взаимодействия пяти ортогональных потных групп. В соответствии с известными законами двойникования ку-

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

Следствие 5. Пусть Ui - исходная U-ячейка с одноименной кубической оболочкой. Пусть U2, U3 - связанные с Ui U-ячейки. Тогда решеткз V(x,y) есть ортогональная проекция на плоскость системы из трех связанных U-ячеек - (иьЩиз).

Теорема 14. Пусть {Ц: i =1,5} - множество U-ячеек, соответствующих подмножеству ортогональных полных трупп. Тогда (1Щ ç 3j31(P), которое есть ориентационное пространство (поле направлений).

Следствие 6. На множестве {Рш: i = 1,35} существует 7 групп {Sut,}, образующих 7 замкнутых U-систем из 5-ти связанных U-ячеек.

В п.5.3 исследуются ориентационные свойства множества тт-систем. Каждой U-системе поставлена б соответствие ориентация исходной оболочки в пространстве "система наблюдения (поиска) Su - объект, принадлежащий окружающей среде". Показано: каждой U-системе на множестве вариантов ориентирования соответствуют три решетки на плоскости ориентирования; матрица MJx4 позволяет измерять углы ориентации элементов изображения (остова, скелета) как отношение целых взаимно простых чисел; U-систеиа имеет две пары троек ортогональных зрительных конусов, обеспечивающих равномерный обзор 3-х мерного пространства с углом поворота я/4 и утлом совмещения я/2 (рис. 7); объединение шести U-систем обеспечивает равномерную дискретизацию 3-мерного пространства на сектора обзора (pi I ) с шагом я/4 и дискретизацией внутри зрительного конуса в проекции на плоскость в соответствии со следующим утверждением.

Следствие 7. Пусть <р*,у(£ ) - проекция конуса J^^L ф(£) на плоскость хОу. Тогда 0,5(pXiy(2) = 4/

j^AX ЛАС] +{9,74°; 11,31°; 13,26°; 15,79°; 19,47°}', где ц/ = I ^ I т (кя/4 ± 2яп) - угол, образованный осью проекции ij/^^sT^S конуса <Рх,>(£) с осью х системы координат; к = Х/у Va/ 0,7 ; п - любое целое число.

■ Показано, что множество взаимодействующих Рис 7 i^T м°лель U-снстем (мощности 6) в плоскости хОу образует 8-ми лепестковую систему кругового обзора с осями симметрии х, у, \у, -\у. Известно, что нейроны ориентационньгх колонок в составе " сверхколонок" зрительной коры имеют "шаг" ориентации приблизительно 10° (б соответствии со след,7 - 9,74°).

Введем понятие критерия эффективности системы Su по угловому Д(П;

разрешению SL<(?) = 1---, где = 0,5j<pxy(i +1) - «рху(>)| - угловое ра>

9с

Изображение

О-пнрзмида

Формирование исходного описания на ¿^-пирамиде

/-пирамида

Разложение на базисе ^-пирамиды

Отображение на У (точечное описание)

Отображен}» на Р„ (поэлементное описание)

Понимание

Синтез на множествах

(композпшю кное

описание) .....+

Принятие реахений на алфавите эталонов

Исходное представление - множество М

Входное полутоновое представление'[

решение на множестве значений (след.6); <р0 = 19,47°; Бс(ф) а 80((р); - значение критерия в точке срх у(1).

Свойство 3. Множество и-систем {1^: 1 = 1,7 } имеет направленную асимметричную диаграмму разрешений по углу. В системе Б и : преобладает левое (либо, правое) направление повышения разрешения по углу; существуют приоритетные направления повышения разрешения по углу.

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

Пусть модель раскрытия априорной неопределенности на базе ((3-11)-пирамид - это е-модель. Тогда алгоритмы обработки изображений, использующие базовую вычислительную операцию на основе (^-преобразования, базовую вычислительную процедуру на основе и-ячейки и раскрывающие 'неопределенность в соответствии с е-моделью называются е-алгоритмами, а вычислительные структуры и системы их реализующие отвечают требованиям и-архитекту-ры: параллельность; однородность; постоянство (врожденность), и предполагают иерархию функций и представлений по рис. 8.

"■Показано, что: каждый фильтр из Р реализует операцию покрытия £-области плоскости, касательной к двумерной поверхности, выявляя тем самым геометрию (форму) этой поверх-

Входное точечное Представление {ц,}

Бинарное тачечное

Представление (V,}

{буквы алфавита)

Бинарное групповое предстдиение {Р*} (слои)

Образное представление к» {У|), {Ры) с учетом долевого участка (Предложение)

Неюобринпашюе описанш

Выход на лицэ пртшиотсс решение (ДПР) Рис. 8

ности; направления х, у, ху на решетке У(х,у) есть проекции специально ориентированной и отображенной 3-х мерной декартовой системы коорди-' нат, где ху - направление глубины; при отсутствии ограничений на занимаемую площадь допустима плоская сетчатка, как чувствительный орган зрения; множества V, Р„ - множества черно-белых образов, решающих на операции задачу анализа изображения (любого) через его синтез.

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

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

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

Основные научные и практические результаты работы:

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

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

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

в) построена схема информационных преобразований как этапов последователь но-параллельных отображений на ¡Р-, «Л-пнрамидах, образующих С2-пирамиду, и П-пирамиде описаний и решений на множествах бинарных операторов У и полных групп Р„. .

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

3. С позиций обработки изображений (обработки в широком смысле) разработана методология анализа и синтеза изображений, заключающаяся:

а) в конструктивном определении изоморфных множеств (конечных) универсальных Р-фильгроа О-пирамвды и операторов V и-пирамнды;

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

4. С позиций теории принятия решений (без обучения):

а) доказано, что множества V, Р„ - множества врожденных эталонов;

б) разработана методология построения (синтеза) эталона класса изображений, как решение задачи анализа изображения через его синтез;

в) решена задача быстрого, одномоментного принятия решения при наличии эталона.

5. Разработана система правил восстано¿пения- 3-х мерности объекта изображения по его единственному двумерному изображению и доказано, что множества F, V, Р„ есть множества позволяющие прямо восстанавливать форму объекта.

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

7. Показана принципиальная возможность использования разработанной модели с ее элементами (операциями) на базе Q-преобразования и процедурами на базе U-ячейки в построении вычислительных структур новой архитектуры, объединяющей положительные свойства как архитектуры Дж. фон Неймана, так и модели коллектива вычислителей по Э.В. Евреи-нову, <

ОСНОВНЫЕ ПУБЛИКАЦИИ

1. Кондратьев В.В., Шаповал A.B., Утробин ВА Алгоритмическое обеспечение обработки изображений на основе психофизиологии зрительного восприятия И Тез. Докл. Международного Форума информатизации, МФИ - 92, Нижегородская секция. Г. Н.Новгород, 1992, с.46 - 49.

2. Кондратьев В.В., Утробин В.А., Шаповал A.B. Обработка изображений на основе психофизиологии зрительного восприятия // Тез. докл. бой Всероссийской науч.-техн. конф. "Радиоприем и обработка сигналов". Г. Н.Новгород, 1993, с.57.

3. Мисевич П.В., Никулин Е.А., Утробин В.А., Шаповал A.B. Алгоритмическое обеспечение выявления признаков объектов изображения на основе стратегий зрительного восприятия // Тез. докл. 6-ой Всероссийской научн'о-техн. конф. "Радиоприем и обработка сигналов". Г. Н Новгород. 1993, с.56.

4. Утробин В.А. Описание морфологии объектов изображения И Тез. докл. 6-ой Всероссийской научно-техн. конф. "Радиоприем и обработка сигналов". Г. Н.Новгород, 1993, с.56 - 57.

5. Кондратьев В.В., Утробин В.А. Информационный подход к моделированию целостного зрительного восприятия // Докл. АН, 1994, т.338, №5, с.610 - 612.

6. Утробин В А. Инвариантность описания двумерных изображений // Тез. докл. науч.-техн. конф. ФРК НГТУ. Г. Н.Новгород, 1995, с.28 - 29.

7. Утробин ВЛ. Симмегрийный анализ изображения И Тез. докл. Конференции с международным участием, посвященной 60-летию акад. РАН Ю.И. Журавлева, "Математические методы распознавания образов". Г. Пушило, 1995, с.62 - 63.

8. Кондратьев В.В., Утробин В.А., Шаповал A.B. Архитектурные особенности модели зрительного восприятия // Тез. докл> науч.-техн. конф. ФРК НГТУ. Г. Н.Новгород, 1995, с.28.

9. Кондратьев В.В., Утробин В.А. Формализация описания изображения в условиях неопределенности II Тез. докл. Конференции с международным участием, посвященной 60-летию акад. РАН Ю.И. Журавлева, '"Математические методы распознавания образов". Г. Пущино, 1995, с.34. .

10. Кондратьев В.В., Утробин В.А. Модель зрительного восприятия в нейросетевом базисе // Тр. Межд. научно-техн. конф. " Непрерывнологиче-ские и нейронные сети и модели". -Ульяновск: Ул. ГТУ, 1995. -Т.1. С.73 -74.

П. Кондратьев В.В., Утробин В.А. Математическая модель процесса идентификации в условиях априорной неопределенности // Докл. Межд. конф. "Применение математического моделирования для решения задач в науке и технике". Г. Ижевск, 31 янв. - 3 февр. 1996г.

12. Кондратьев В.В., Утробин В.А. Идентификация двумерных изображений в условиях неопределенности II Сб. науч. тр. ТулГУ- "Элементы и системы оптимальной идентификации и управления технологическими процессами". -Тула, 1996. С.З -12.

13. Кондратьев В.В., Утробин В.А. Формирование описания изображения в условиях неопределенности //Докл. АН, 1996, т.347, №3, с.316 -318 -

14. Кондратьев В.В., Утробин В.А. Активное восстановление - решение проблемы неопределенности // Докл. АН, 1996, т.350, №3, с.315-317.

15. Кондратьев В.В., Утробин В.А. Анализ изображений в условиях неопределенности // Мсжвуз. сб. науч. тр. "Системы обработки информации и управления". - Н.Новгород, 1996. С.7 - 17.

16. Утробин В.А. Новый подход к проблеме восстановления трехмерности двумерного изображения // Тез. докл. науч.-техн. конф. ФРК НГТУ. Г. Н. Новгород, 1996, с.44 - 45.

17. Утробин В.А. Потенциальные операторы оценивания изображений //Межвуз. сб. науч. тр. "Системы обработки информации и управления". -Н.Новгород, 1996. С.17- 26. .

18. Кондратьев В.В., Утробин В.А. Основы теории активного восприятия изображений. -Н.Новгород: НГТУ, 1997. -249с.

19. Кондратьев В.В., Утробин В.А. Модель неопределенности в задаче идентификации изображений //Тез. докл. научн.-техн. конф. ФРК НГТУ. Г. Н.Новгород, 1997, с.33-34.

20. Утробин В.А. Алгебра инвариантности изображения //Тез. докл. научн.-техн. конф. ФРК НГТУ. Г. Н.Новгород, 1997, с.34-35.

21. Кондратьев В.В., Утробин В.А., Рогинский А.В. Двухэтапный алгоритм распознавания отпечатков пальцев ЛТез. докл. научн.-техн. конф. ФРК НГТУ. Г. Н Новгород,- 1997, с,35-36.

22. Кондратьев В В., Утробнн В.А., Колебанов С.В. Поиск и использование информативных точек на базе метода активного восстановления изображений //Тез. докл. научн.-техн. конф. ФРК НГТУ. Г. Н.Новгород, 1997, с.36.

23. Утробин В.А. Информационная модель преобразований изображения в условиях априорной неопределенности последнего //Тез. докл. 8 Всероссийская конференция ММРО-8. Г. Москва, 1997, с. 112-113.

24. Кондратьев В.В., Угробин В.А. Способ обработки изображения объекта//БИ, № 31, 10.11.96, c.t 15, полож. реш. от05.01.1998.

25. Кондратьев В.В., Утробин В.А. Математическая модель процесса идентификации в условиях априорной неопределенности // Сб. науч. тр. "Применение математического моделирования для решения задач в науке и технике". -Ижевск, 1996. С. 63-73.

26. Кондратьев В.В., Утробин В.А. Симметрия 5-ти мерного евклидова пространства//Докл. АН, 1997, т.356, №2, с. 178-181.

27. Kondrat'ev V.V., Utrobin V.A. Inderteimination uncovering model in identification problem // The 4-th' open Russian - German workshop "Pattern Recognition and Image Analysis" Valday, the Russian Federation, March 3-9,

1996, p.80 - 82.

28. Kondrat'ev V.V., Utrobin V.A. Foundation of image active restoration theory H Pattern Recognition and Image Analysis, 1996, №1, p.55-75.

29. Kondrat'ev V.V., Utrobin. V.A. Uncovering of indeterminacy in identification problems // Pattern Recognition and Image Analysis, 1996, №2, p.250-259.

30. Kondrat'ev V., Utrobin V., Balabanov A. Information model of decision making process for image recognition // Computer Science Journal of Moldova,

1997, vol.5, №2, p. 123-145.