WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     || 2 |

«ДАННЫХ СИСТЕМЫ АВТОМАТИЗИРОВАННОГО РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ ...»

-- [ Страница 1 ] --

РОССИЙСКАЯ АКАДЕМИЯ НАУК

САНКТ - ПЕТЕРБУРГСКИЙ ИНСТИТУТ ИНФОРМАТИКИ И АВТОМАТИЗАЦИИ

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

Харинов Михаил Вячеславович

УДК 681.322.05}51 + 681.391.837}51

РАЗРАБОТКА ДИНАМИЧЕСКИХ СТРУКТУР ДАННЫХ

СИСТЕМЫ АВТОМАТИЗИРОВАННОГО РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ

Специальность: 05.13.16 применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

ДИССЕРТАЦИЯ

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

Научный руководитель доктор технических наук, профессор Александров В.В.

Санкт - Петербург Введение

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

1.1. Теоретические предпосылки комплексного решения

1.2. Задача адаптивного многоуровневого представления полутонового изображения.......... 1.3. Базовый алгоритм выделения объектов............ 1.4. Цель и задачи работы

Глава 2. Многоуровневая модель изображения............... 2.1. Понятие многоуровневой модели.................. 2.2. Алгебраическое определение объекта............. 2.3. Структура данных для выделения объектов 2.3.1 Понятие видеоданных

2.3.2 Представление связных областей в виде деревьев

2.3.3 Табличное описание соседства областей........ 2.4 Генерация структуры. Обеспечение прямого доступа

2.5. Формы организации данных. Аппроксимация объектов

2.6. Метод анализа полутонового изображения по яркости

Выводы по главе 2

Глава 3. Геометрическое описание и структурный анализ объектов

3.1. Аналитическое описание объектов, исходя из свойств осевой симметрии 3.1.1 Сохранение симметрии при линейных преобразованиях

3.1.2 Центральные и средние значения координат.

Условие координатной симметрии............... 3.1.3 Запись в 2-мерном подпространстве n-мерного векторного пространства

3.1.4 Поворот. Определение ориентации............... 3.1.5 Собственные преобразования Лоренца.

Приведение к собственным осям.................. 3.1.6 Интерпретация

3.1.7 Разложение WWL в произведение ортогонального и симметричного операторов. Отождествление плоскостей

3.1.8 Характеристика фигуры посредством сдвига системы координат

3.2. Структурное описание объектов посредством частичного анализа

Выводы по главе 3

Глава 4. Распознавание (идентификация) объектов.......... 4.1. Задача автоматизированной идентификации видеообъектов

4.2. Библиотека объектов

4.3. Реализация. Эксперимент. Обучение.

Самообучение

Выводы по главе 4

Заключение

Литература

Приложение

ВВЕДЕНИЕ

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

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

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

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

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

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



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

Основные результаты в области разработки иерархических структур видеоданных принадлежат С.Л. Танимото, А.Розенфельду, А. Клингеру, В.В. Александрову.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3) Разработка методов структурного анализа изображения по яркостным и геометрическим признакам.

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

5) Экспериментальное исследование развиваемых технических решений путём обработки реальных изображений на ЭВМ.

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

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

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

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

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

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

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

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

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

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

С целью автоматизации экспериментальных исследований по теме диссертации автором на базе ЭВМ РС/286 реализованы:

- пакет прикладных программ многоуровневой сегментации для выделения объектов на полутоновых изображениях размером 256*256 при 256 градациях яркости;

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

Проведённые в СПИИРАН многочисленные эксперименты с аэрокосмическими снимками и с изображениями, полученными с помощью телекамеры, а также введёнными со сканера, обеспечили верификацию разработанных теоретических положений. Внедрение работы в ПО "Севморгеология" позволило расширить возможности применяемого аппаратного комплекса "Pericolor" и улучшить качество обработки глубоководных снимков. Разработанные программные системы эксплуатируются в в/ч 41513, 32103.

Представленные к защите результаты являются составной частью работ, проводимых в СПИИ РАН по темам:"Создание и ввод в эксплуатацию специализированной автоматизированной системы обработки изображений на основе пирамидально-рекурсивных структур данных" (НТП 0.80.03, задание 07.05), "ЛАМПАС-ГКНО" (НИР, выполняемая с в/ч 4153, 32103 согласно договору между научно-техническим центром "Наука" Миннауки России и СПИИ РАН на основании решения Государственной комиссии по ВПВ от 11.09.90 № 264), "Разработка моделирующих инструментальных средств нелинейной системостатики"(НТП "Информатизация России", проект 1.4.1), "Разработка интеллектуальных систем анализа и синтеза визуальной информации на основе рекурсивных структур"("Перспективные информационные технологии", проект № 539, шифр -"Эволюция").

ГЛАВА 1. ПРЕДПОСЫЛКИ КОМПЛЕКСНОГО РЕШЕНИЯ

ПРОБЛЕМЫ РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ

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

Анализируются особенности распознавания видеоданных.

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

1.1. Теоретические предпосылки комплексного решения.

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

Хотя постановка задачи распознавания на первый взгляд предельно проста и сводится к моделированию на ЭВМ способности человека запоминать указанные объекты и затем их узнавать, тем не менее принципы решения этой задачи на современном этапе находятся в стадии формирования. Большинство приложений ориентировано на участие человека, для которого комфортные условия восприятия могут не совпадать с оптимальными формами преобразования информации в ЭВМ. Так, предварительные преобразования фильтрации в виде реставрации, улучшения качества изображений [48,70] могут не иметь принципиального значения при продолжении обработки на ЭВМ. Классические методы распознавания образов [56,57] могут оказаться не оптимальными при автоматизированной подготовке данных признакового описания объектов. Таким образом, совокупность технических решений, повышающих эффективность распознавания человека, не обеспечивает автоматизацию процесса распознавания в целом и для формирования элементов теории необходим комплексный подход, при котором в полной мере проявляется специфика проблемы автоматизированной обработки изображений.

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

Недостаточная формализация распознавания, вероятно, связана прежде всего с не вполне адекватным сопоставлением математических и реальных понятий. При этом точные математические формулировки задач и решений [9,35] оказываются относительно громоздкими и существенно менее доступными, чем словесное описание. Таким образом, для моделирования простейших функций распознавания особое значение имеет удачная интерпретация постановки и решения задач, обеспечивающая достижение цели средствами стандартной математики. При моделировании более сложных функций распознавания адекватная интерпретация [52-55] может усилить эффект применения развиваемого нового математического аппарата алгебры алгоритмов [26-28], алгебры образов и теории нечётких множеств [44,86,90,92].

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

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

Другая трудность связана с изменением множества обрабатываемых данных в процессе распознавания на ЭВМ. Автоматизированное распознавание характерно тем, что включает по крайней мере две классификации, вложенные одна в другую. Первая классификация состоит в объединении точек в объекты, втораяв идентификации объектов, что сводится к нахождению их обозначений в виде названий или имён. Группировку точек при выделении объектов и идентификацию или распознавание объектов не всегда разделяют между собой. Например, при поиске объектов методом сравнения с эталоном [4,5,72-75,93] выделение и распознавание объектов производятся одновременно, что достигается благодаря сужению возможной области приложения задачами поиска объектов фиксированного масштаба и влечёт необходимость оптимизации выполнения перебора вариантов.

Разделение процедур классификации [77] позволяет строить распознавание на основе анализа информации не об ожидаемых, а об имеющихся объектах, что позволяет расширить рассматриваемую предметную область.

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

Необходимая для классификации объектов подготовка данных может достигаться в процессе выделения объектов и этим ограничиваться. Так, при распознавании по эталонам под данными понимаются сами объекты в виде наборов точек. В методах структурного анализа [3,21,49,50,58,59] под данными понимаются образы в виде стилизованных объектов или их признаковых описаний, выраженные в терминах структур достаточно сложной природы (примитивы, таблицы, графы, гистограммы, спектры и т.д.). Указанные структуры являются "полуфабрикатами" обработки, формируются как некоторый эквивалент изображения в терминах стандартных непроизводных элементов и отражают многообразие свойств объектов (отношений объектов). Сложная природа структур данных, применяемых для выделения объектов, связана с необходимостью сохранения информационной избыточности изображения относительно каждого из возможных запросов при условии оптимизации процесса выполнения текущих запросов по времени. При этом оптимизация по времени достигается за счёт того, что специальные структуры данных позволяют оперировать с некоторыми комплексами точек, а информационная избыточность обеспечивает возможность неоднозначного объектного описания изображения.

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

Наиболее удобный подход к структурному анализу используется в методе голосования [29,30], в наглядной интерпретации которого объект представляется набором составных частей, оценивается сходство каждой части с частями известных объектов и в результате порогового анализа оценок строится прогноз. При этом объект описывается в терминах компонент адекватной сложности, что упрощает язык описания и позволяет представить объект в виде числового вектора данных.

Согласно идее В.В. Александрова [1,6,8] распознавание изображения представляется непрерывным процессом чередования анализа и синтеза объектов, где под синтезом понимается интерпретация группировки точек в объекты в терминах исходной матрицы, для которой устанавливается принадлежность исходных точек определённым объектам. Если переход к внутренней структуре данных при выделении объектов согласно текущему запросу обеспечивает возможность восстановления адекватного однозначного разбиения изображения, то структурный анализ производится вслед за выделением объектов посредством обработки исходной матрицы. Проведение структурного анализа объектов независимо от внутренней формы организации данных для выделения объектов обеспечивает схему преобразования данных рис. 1, в которой однозначные преобразования составляют логически естественную цепь обработки.

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

Разработка адекватных систем признаков при комплексном решении проблемы распознавания с целью создания эффективных программных систем является одной из важнейших задач, что прежде всего связано с необходимостью получения описания объектов вне зависимости от изменения условий съёмки. При этом в качестве основных факторов, влияющих на изображение, обычно рассматривают поворот и изменение масштаба. Известно, что неинвариантность методов представления и обработки изображения [3,32,80] относительно изменения ориентации и масштаба либо ограничивают область применения, либо требуют специальных усилий для их преодоления.

Что касается учёта ориентации объектов, то применяемые методы разделяются на эвристические [11] и аналитические [17,77,81,82]. С принципиальной точки зрения вторые представляются более перспективными, так как позволяют учесть возможность непрерывного изменения ориентации объектов и избежать перебора вариантов. К современным аналитическим методам эффективного анализа различным образом ориентированных объектов следует также отнести методы представления объектов на основе признаков, построенных из соображений инвариантности относительно поворота [16,76,85,89].

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

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

Учёт ориентации и масштаба имеет немаловажное значение при использовании для распознавания изображений метода [29-30] распознавания образов по частичному прецеденту. Если составление частичного описания трактуется в буквальном смысле дробления исходного объекта, то выбор конкретного способа разделения целого на части представляется проблематичным.

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

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

Для современного подхода к методам устранения противоречия между имеющимися и желаемыми результатами распознавания характерно пассивное отношение к требуемому результату, который считается достижимым независимо от степени соответствия входных и установленных выходных данных. В общеупотребительном подходе [26-28] к распознаванию образов для согласования признакового описания объектов с их именами используются два механизма адаптации алгоритмов идентификации обектов. Первый сводится к изменению отображения наборов значений признаков в имена объектов посредством варьирования параметров решающих алгоритмов. Второй механизм обеспечивается за счёт расширения множества решающих алгоритмов на основе формального определения алгебраических операций.

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

Нельзя не отметить глубокое значение идеи алгебраического замыкания [26-28], которая обеспечивает возможность развития методов идентификации не только на основе расширения множества решающих правил, но также посредством формирования алгебраически упорядоченной системы накапливаемых в виде обучающей информации сведений об объектах. В сочетании с частичным анализом [29,30] эта идея представляет самостоятельный практический интерес, так как обеспечивает эффективные расчёты на основе использования алгебраических комбинаций результатов признакового описания изображения. При этом для конкретизации подхода применительно к распознаванию изображений представляется необходимым развитие физической интерпретации формальных алгебраических объектов и операций.

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

Если концепция обучения (на примерах) в теории распознавания образов является хорошо изученной [68,88], то её конкретная интерпретация в случае распознавания изображений нуждается в уточнении, отражающем особенности данной области. В контексте разработки самоорганизующихся систем распознавания видеоинформации задача обучения не сводится к простому частному случаю классической теории распознавания образов, так как помимо поиска адекватного прогнозирования идетифицируемых объектов включает задачу управления выделением объектов.

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

Атрибутами поступающих по мере обучения в ЭВМ сведений об объектах являются значения признаков и идентификаторы.

Посредством интерполяции множеств значений признаков известных объектов определяются соответсвующие области допустимых значений (ОДЗ),характеризуемые диапазонами изменений рассматриваемых величин. Численные характеристики ОДЗ в виде диапазонов рассматриваются в системе автоматического распознавания изображений как внутренние управляющие параметры, определяющие адаптацию системы к данной предметной области. Посредством учёта ОДЗ осуществляется выделение объектов.

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

В режиме интерактивного обучения рассматриваются все без исключения обнаруженные объекты.

Таким образом, распознавание объектов некоторой предметной области иллюстрируется схемой рис.2.

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

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

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

Классическая концепция обучения ориентирована на некоторую бесконечную последовательность примеров, что предполагает использование неограниченной памяти ЭВМ. Простейшей реализацией обучения на примерах при обработке изображений является метод использования эталонов, который до сих пор является одним из самых распространённых при решении некоторых прикладных задач [11,93]. Большой объём оперативной памяти, необходимой для накопления эталонов, влечёт снижение быстродействия в силу резкого возрастания количества данных, анализируемых методом перебора.

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

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

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

Концепция ограниченной памяти позволяет по-новому представить проблему автоматического обучения, постановка которой до сих пор является предметом обсуждения [15,16,67]. В [67] обучение трактуется как автоматическое расширение накопленной обучающей информации. В [15,16] формулируется задача построения признакового пространства, адекватного объектам.

Как вариант развития [15,16,67] представляется целесообразным развитие идеи формирования признакового описания без непосредственного использования понятия признакового пространства в общепринятом смысле, что достигается отождествлением "близости" объектов по данному признаку со случаем совпадения. При этом распознавание организуется независимо от порядка значений признака, оптимальный выбор которого может оказаться проблематичным [9,61]. Самообучение (автоматическое обучение без использования изображений) трактуется как оптимизация процесса обучения посредством моделирования насыщения обучающей информации. При этом складывающиеся по мере накопления информации закономерности в зависимости от конкретных предметных областей могут влиять на применяемые алгоритмы моделирования. В качестве общего механизма реализации самообучения может использоваться интерполяция, которую естественно назвать интерполяцией знаний. Благодаря возможности экспериментальной проверки правильности интерполяции самообучение определяется хотя и не вполне строго, но конструктивно, что даёт методологическую основу для алгоритмической организации вычислений.

Эффективное использование аппаратного обеспечения на завершающей стадии распознавания достигается в виде разумного распределения оперативной памяти, занимаемой блоком признакового описания объектов и обучающей информацией (библиотекой знаний). Оба блока информации при распознавании (идентификации) объектов используются одновременно и поэтому в оптимальном случае по суммарному объёму не должны превосходить ресурсов ЭВМ. При ограниченных ресурсах оперативной памяти ЭВМ (типа IBM PC) имеет смысл предположить, что по сравнению с блоком знаний блок признакового описания требует большего оперативного пространства, так как содержит многокомпонентное представление всех имеющихся на изображении объектов в виде некоторых наборов составных частей. Положение об относительно небольшом объёме отводимой под знания оперативной памяти согласуется также и с тем, что в принципе инициализация работы обучаемой программной системы производится при нулевом объёме знаний, на которые по идее должна расходоваться пренебрежимо малая память. Средства поддержки стандартных баз знаний современных экспертных систем [4,7] сами по себе требуют существенных затрат оперативной памяти, что ограничивает возможности их использования в обучаемых системах автоматического распознавания. Таким образом, при ограниченных ресурсах оперативной памяти организация библиотеки знаний обучаемой системы представляет самостоятельный интерес.

На первоначальном этапе выделения объектов большой объём оперативной памяти занимает многозначное внутреннее представление изображения. При этом однозначное выделение объектов реализуется в соответствие с содержанием блока накопленных знаний. Признаковое описание объектов формируется на промежужуточном этапе обработки в процессе структурного анализа, что требует оперативного использования данных о принадлежности исходных точек изображения выделенным объектам. При этом пронумерованные объекты задаются посредством разметки №(.) точек исходного изображения. Таким образом, использование оперативной памяти ЭВМ на трёх последовательных стадиях обработки характеризуется схемой рис.3.

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

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

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

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

1.2. Задача многоуровневой адаптивной аппроксимации Аппроксимация полутонового изображения, при котором оно замещается некоторым близким аналогом, используется для оптимизации хранения и передачи видеоинформации и хорошо изучено [48] в применении к системам, расчитанных на участие человека. В качестве меры близости обычно принимается среднеквадратичное отклонение по яркости. Наиболее употребительными методами аппроксимации являются "кодирование с преобразованием" и блочное кодирование. Первое [31,83] выполняется на основе подавления спектральных составляющих, с визуальной точки зрения не влияющих на качество изображения, второе [3,71] производится на основе использования набора стандартных блоков различных размеров. Применение как первого, так и второго метода влечёт искажение формы изображённых объектов и с точки зрения возможности автоматизированного распознавания может ухудшать качество изображений, что вызывает необходимость использования адаптивных методов аппроксимации [19,22,33,84,91].

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

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

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

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

В современном контексте создания автоматизированных систем обработки сжатие видеоинформации трактуется [35] как приведение данных к виду, удобному для последующего распознавания, что в конкретной интерпретации сводится к упрощению изображения. Упрощение изображения можно трактовать как укрупнение частей объектов за счёт их взаимного слияния и удаление объектов, в контексте данной предметной области считающихся заведомо ложными. Таким образом, сжатие видеоинформации обеспечивается на предварительной стадии распознавания изображения - при перечислении объектов. При этом специфика состоит в том, что перечисление объектов осуществляется независимо от их идентификации, которая в классической схеме распознавания изображений [77] выполняется на одном из последующих этапов обработки.

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

использованием [19,22,84,91] адаптивных методов аппроксимации результаты итеративного преобразования изображения [33] трактуются в более общем смысле. Итеративная аппроксимация объектов областями различной формы и размеров, достигаемая в алгоритме [33], порождает объектно-ориентированное представление, в котором все несовпадающие области рассматриваются равноправно. Считается, что каждая из полученных областей в контексте той или иной задачи может рассматриваться как объект или по крайней мере как часть объекта. При этом вопрос об оптимальной аппроксимации изображения на некоторой итерации снимается, уступая место проблеме эффективного описания объектов посредством элементов, вычисленных в базовом алгоритме выделения объектов [33] на различных итерациях.

1.3. Базовый алгоритм выделения объектов.

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

Принятый в работе базовый алгоритм сегментации полутоновых изображений [33,34] обеспечивает выделение объектов, устойчивое к изменению условий съёмки. Он относится к алгоритмам сегментации [18,23,45] посредством наращивания областей и сводится к поэтапному слиянию областей, наиболее близких по средней яркости.

Наглядно базовый алгоритм описывается следующим.

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

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

Все точки считаются свободными.

заканчивается. В противном случае находим свободную точку.

формируется рекурсивно} при включении точки в данную область близкой яркости.

области их арифметическим средним, возвращаемся к п.1.

Для получения стабильного результата преобразования, имеет смысл при фиксированном пороге повторять обработку согласно пп.1-3 до получения устойчивой картины.

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

При этом параметр определяет яркостное разделение областей между собой.

На практике оказывается допустимым наращивать порог непосредственно с каждой итерацией, определяемой пп.1-3.

Рис. 4 иллюстрирует обработку реального изображения.

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

Практическое применение базовый алгоритм обработки изображений [33] нашёл при анализе глубоководных снимков (рис.5).

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

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

вещения учитывается по нескольким рабочим снимкам. При этом выделение конкреций сводится к пороговому преобразованию [13] с учётом неравномерности освещения. В системе KMTV для поиска конкреций применяется также метод выделения границ по перепаду яркости, что недостаточно эффективно и усложняет расчёты в силу необходимости устранения разрывов при выявлении замкнутых областей ([14]). С целью анализа фотоснимков разрабатыватся также и отечественные системы [12].

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

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

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

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

Рис. 6. Гистограмма яркостей исходного изображения.

Рис. 7. Гистограмма яркостей сегментированного изображения Следует отметить, что для обсуждаемого алгоритма характерно симметричное рассмотрение областей, при котором считается, что все области в равной степени представляют объекты (части объектов). Поэтому он применим для выделения на полутоновых изображениях объектов различных типов, что помимо практики обработки глубоководных снимков подтверждено результатами многочисленных экспериментов с аэрокосмическими изображениями и изображениями, полученными с помощью телекамеры (рис.4). Эксперименты с телевизионными изображениями проводились на примере снимков человеческих лиц. Аэрокосмические изображения изучались в виде снимков земной поверхности и искусственных космических объектов. Обработка изображений лиц показала, что разумная степень сегментации исходных изображений практически не влияет на распознавание, так как глазом различие воспринимается слабо. По сравнению с изображениями лиц снимки земной поверхности геометрически более просты и на них легче рассмотреть результаты укрупнения областей. Как показал опыт, после 10-15 итераций обработки снимков земной поверхности наблюдаемые объекты результирующего изображения представляются равнояркостными областями с резкими границами, что удобно для автоматизации распознавания.

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

циклического применения базового алгоритма сегментации до определённого предела можно рассматривать как удаление сегментированным изображения стандартных программ факсимильного сжатия (pkzip, ice и др.). Как показал эксперимент со снимками искусственных космических объектов, для сегментированных полутоновых изображений с укрупнёнными равнояркостными областями коэффициент сжатия возрастает от 1-1.5 до 10-30.

Таким образом, замещение исходных снимков изображениями с укрупнёнными областями решает задачу хранения изображений при ресурсах ПЭВМ.

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

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

изображения N*N оценивается числом r2*N. Для реального полутонового изображения разброс встречающихся площадей обычно значительно меньше. В процессе итеративной сегментации число областей различной площади растёт, достигая при определённом максимального значения (рис.8).

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

Число различных площадей полутонового изображения размером 256* сегментации позволяет улучшить качество аппроксимации объектов, однако, ведёт к большим временным затратам. Снижение оптимизации операций со связными областями произвольной формы и размеров, что требует разработки структуры данных, отличной от матричной. При этом базовый алгоритм сегментации сохраняет практическое значение для отладки программ и в условиях ограниченных ресурсов ПЭВМ может использоваться для редукции изображений по количеству областей с целью уменьшения необходимой оперативной памяти. Необходимо отметить, что редукция изображения по количеству областей согласно базовому алгоритму допускает оптимизацию вычислений с комбинированной структурой данных [60,61], но выигрыш по времени достигается за счёт неадекватного возрастания сложности алгоритмов.

Ресурсов памяти ПЭВМ достаточно для самостоятельной разработки отличного от матричного способа представления изображения.

1.4. Цель и задачи работы.

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

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

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

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

2) Формализация понятия объекта на основе аппроксимации минимальным числом связных областей различных уровней сегментации изображения.

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

4) Построение системы аналитического и структурного (частичного) анализа интегральных геометрических признаков произвольных объектов по свойствам симметрии независимо от ориентации и масштаба.

5) Разработка механизма запоминания и автоматизированной идентификации видеообъектов по повторяющимся значениям признаков.

6) Экспериментальное обоснование разработанных решений.

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

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

ГЛАВА 2. МНОГОУРОВНЕВАЯ МОДЕЛЬ ИЗОБРАЖЕНИЯ

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

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

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

2.1. Понятие многоуровневой модели.

информации строится на множестве приближений полутонового изображения посредством областей однородной яркости (рис.4).

Многоуровневая модель - это своего рода алгебраический "конструктор", обеспечивающий аппроксимацию объектов сцены сливаться друг с другом, что позволяет представить объекты минимальным количеством частей.

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

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

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

2.2. Алгебраическое определение объекта.

частями объектов, как правило, на разных уровнях. Возникает частей, путём совмещения областей различных уровней. Имеется простое решение [64].

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

Представим вначале, что нам известны некие "кирпичики", найдём и сами объекты, которые можно разделить между собой по признаку связности, если каждый объект занимает отдельное место. Для того, чтобы составить некоторое макроописание объектов, следует предположить, что "кирпичики" объединяются между собой в укрупнённые @блоки@.

сформировать из некоторых исходных стандартных элементов путём слияния последних по определённому принципу.

Тогда представление об объекте полутонового изображения сводится к следующему:

различные "кирпичики";

признаку;

объектов сцены;

целого.

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

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

значений (ОДЗ), например, имеющих площадь и среднюю яркость множество частей (элементов) различных объектов.

объект занимает отдельное место. В общем случае разделение объектов может определяться также и другими соображениями.

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

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

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

2.3 Структура данных для выделения объектов 2.3.1 Понятие видеоданных.

позволяет эффективно организовать обработку видеоинформации.

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

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

составных частей. Решаются также и другие задачи.

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

2.3.2 Представление связных областей в виде деревьев.

от 1 до N.

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

Рис 9. Описание слияния пары областей в форме слияния деревьев. Новая связь обозначена пунктиром.

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

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

В исходном состоянии массив f[n] представляет собой ряд начального разбиения изображения на связные области, в являются обозначениями элементов начального разбиения.

обозначение области замещается меньшим.

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

Значение данного элемента определяет адрес следующего.

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

В терминах языка СИ алгоритм циклической переадресации выражается оператором:

где n - адрес рассматриваемого узла.

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

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

2.3.3 Табличное описание соседства областей.

симметричной таблицей связности, в начальном состоянии имеющей размеры N*N (рис. 10). Подобные таблицы применяются машинной графике [94] для описания трёхмерных объектов.

описании преобразований конкретных объектов.

Рис. 10 Описание соседства областей посредством таблицы.

(столбцы) таблицы связности в порядке возрастания номеров.

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

Наглядное представление Рис. 11 Представление таблицы связности списками областей.

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

С помощью верхней диагональной части таблицы связности слияние областей описывается почти так же просто (рис.12, ср. с рис.10). Почленное объединение пары строк (столбцов) по закону логического сложения сопровождается вычёркиванием строки (столбца) с большим номером. Точки, попадающие при слиянии столбцов в нижнюю часть таблицы связности путём зеркального отражения относительно диагонали переносятся в преобразования таблицы рис.12 организуются как операции со списками (рис.11).

Результат слияния сегментов Рис. 12 Преобразование таблицы связности при слиянии областей.

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

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

2.4. Генерация структуры. Обеспечение прямого доступа.

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

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

в следующем.

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

циклической переадресации вычисляется текущее обозначение;

- если вычисленные текущие обозначения не совпадают, то заменяется значением меньшего. Одновременно суммируются суммирования в качестве атрибутов приписываются меньшему элементу массива f.

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

При одном просмотре производится соответствующее слияние (рис.12). В процессе слияния строк для укрупнённых областей вычисляются новые средние яркости.

остаются строки (столбцы), отвечающие укрупнённым областям.

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

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

охарактеризована как сегментация с "памятью".

Рис.13. Описание уровней посредством индексации связей Практическое значение сегментации с "памятью" состоит в преобразования видеоданных к матричному виду, что необходимо для интерактивного контроля видеоинформации. Если разбиение искомого уровня находится по дереву с индексированными связями, необходимые для вычисления средних значений яркости аддитивные характеристики областей определяются посредством суммирования характеристик элементов исходного разбиения, то ЭВМ IBM/PC-286 две-четыре секунды.

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

2.5. Формы организации данных. Аппроксимация объектов.

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

таблицы связности. Если исходное изображение размечено так, превышающими некоторого числа K, является связной областью [61], то просмотр таблицы связности можно осуществлять в режиме автосканирования, который сводится к следующему:

(номеров областей), содержащий вначале единственную 1;

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

оказывается вся таблица связности.

схемой рис.14.

Рис. 14. Схема автосканирования таблицы связности.

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

установленного порядка слияния компонент может описываться эквивалентны (рис. 15).

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

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

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

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

от одного из них к другому.

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

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

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

определению объектов п. 2.2, что использовалось практически при отладке программной реализации.

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

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

Самостояльный интерес компьютерная модель распознавания представляет для интерпретации механизмов зрительного восприятия.

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

учитываются все области различных уровней, что согласуется с состояний, достигаемых в процессе формирования рецептивных рецепторов [20] формирование связных областей для описания объектов производится на основе оценки энергии [47] и других аддитивных характеристик.

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

2.6. Метод анализа полутонового изображения по яркости.

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

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

яркостных экстремумов состоит в следующем.

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

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

повторяется до тех пор, пока все области рассматриваемого разбиения изображения не разделятся на области трёх типов:

локальные минимумы, локальные максимумы и области смешанного типа.

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

Окончательный результат локализации объектов наглядно представляется картиной с тремя градациями яркости (рис.19), экстремумов смешанного типа окрашены, соответственно, в белый, чёрный и серый цвета.

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

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

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

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

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

пограничные тёмные, пограничные светлые и пограничные серые.

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

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

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

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

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

По сравнению c характеристиками объектов полутоновых изображений признаки объектов двухградационных изображений следует признать более общими. Ориентация является одним из признаков, характерных для изображений обоих типов. Известно [47], что в зрительной системе человека определённую роль играют нейронные системы, оппонентные к взаимно-ортогональным ориентациям. Поэтому для компьютерного моделирования механизмов зрительного восприятия развитие аппарата многоуровнего представления посредством исследования способов формального описания ориентации объектов также представляет интерес.

Выводы по главе 2.

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

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

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

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

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

ГЛАВА 3. ГЕОМЕТРИЧЕСКОЕ ОПИСАНИЕ

И СТРУКТУРНЫЙ АНАЛИЗ ОБЪЕКТОВ

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

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

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

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

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

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

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

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

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

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

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

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

3.1. Аналитическое описание объектов, исходя из свойств осевой симметрии 3.1.1 Сохранение симметрии при линейных преобразованиях Традиционный аппарат современных фундаментальных исследований, основанный на изучении инвариантов относительно групповых преобразований, в области обработки изображений интенсивно применяется с момента зарождения и по настоящее время [37]. Его сочетание с удачной физической интерпретацией даёт наиболее сильный эффект. Известной методологией физической интерпретации являются построения на основе соображений симметрии.

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

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

Свойства инвариантности осевой симметрии относительно поворота и растяжения одной оси с одновременным сжатием другой являются основой дальнейших рассуждений.

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

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

3.1.2 Центральные и средние значения координат. Условие распределением n точек xi, y i.

x, y, определяемых как следующие величины x, y :



Pages:     || 2 |


Похожие работы:

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Бокова, Светлана Владимировна Особенности проектирования влагозащитной спецодежды для работников автосервиса Москва Российская государственная библиотека diss.rsl.ru 2006 Бокова, Светлана Владимировна Особенности проектирования влагозащитной спецодежды для работников автосервиса : [Электронный ресурс] : Дис. . канд. техн. наук  : 05.19.04. ­ Шахты: РГБ, 2005 (Из фондов Российской Государственной Библиотеки) Технология швейных изделий...»

«04200951398 Бабурина Елена Вячеславовна НАРУШЕНИЯ ИММУНОЛОГИЧЕСКОГО СТАТУСА И ИХ КОРРЕКЦИЯ ГЛУТОКСИМОМ У БОЛЬНЫХ С ОСТРЫМ И ОБОСТРЕНИЯМИ ХРОНИЧЕСКОГО САЛЬПИНГООФОРИТОВ ДИССЕРТАЦИЯ на соискание учёной степени кандидата медицинских наук 14.00.36 - аллергология и...»

«Кондаков Василий Гаврильевич Обобщение схемы КАБАРЕ на многомерные уравнения задач газовой динамики специальность: 05.13.18 – Математическое моделирование, численные методы и комплексы программ Диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель : д.ф.-м.н. С.А. Карабасов Москва - Содержание Введение Глава 1. Схема КАБАРЕ для уравнений...»

«Богоутдинов Наиль Шамильевич БИОТЕХНОЛОГИЧЕСКИЕ АСПЕКТЫ РАЗРАБОТКИ ЭКСПЕРИМЕНТАЛЬНОЙ ТЕРАПЕВТИЧЕСКОЙ ВАКЦИНЫ ПРОТИВ АКТИНОМИКОЗА КРУПНОГО РОГАТОГО СКОТА 03.01.06 – биотехнология (в том числе бионанотехнологии) 03.02.03 – микробиология Диссертация на соискание ученой степени кандидата биологических наук Научные руководители: доктор...»

«Черная Елена Юрьевна Милица Васильевна Нечкина – историк отечественной исторической наук и Специальность: 07.00.09 – Историография, источниковедение и методы исторического исследования. Диссертация на соискание ученой степени кандидата исторических наук Научный руководитель д.и.н., проф. Умбрашко К.Б. Новосибирск 2014 Оглавление Введение.. Первая глава...»

«Человеков Иван Васильевич СВОЙСТВА РЕНТГЕНОВСКОГО ИЗЛУЧЕНИЯ АККРЕЦИРУЮЩИХ НЕЙТРОННЫХ ЗВЕЗД СО СЛАБЫМ МАГНИТНЫМ ПОЛЕМ ПО ДАННЫМ ОРБИТАЛЬНЫХ ОБСЕРВАТОРИЙ ГРАНАТ, RXTE И ИНТЕГРАЛ 01.03.02 Астрофизика и радиоастрономия ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук Научный руководитель д.ф.-м.н. Гребенев С.А. Москва В первую очередь я хочу выразить глубокую благодарность своим учителям:...»

«МИНЕЕВА ВАЛЕНТИНА ИВАНОВНА Правовая политика российского государства в области экологии: проблемы реализации 12.00.01 – теория и история права и государства; история учений о праве и государстве 12.00.06 – природоресурсное право; аграрное право; экологическое право Диссертация На соискание учёной степени кандидата юридических наук Научный руководитель : Некрасов Евгений Ефимович, доктор юридических наук, профессор...»

«СОЛОЩЕВА Мария Алексеевна ПОЛИТИКА ИМПЕРИИ ЦИН В ОТНОШЕНИИ ТИБЕТА В ПЕРИОД ПРАВЛЕНИЯ ИМПЕРАТОРА ЮНЧЖЭНА (1723–1735 гг.) Специальность 07.00.03 – всеобщая история (средние века) Диссертация на соискание ученой степени кандидата исторических наук Научный руководитель : доктор исторических наук Успенский Владимир Леонидович Санкт-Петербург 2014 2 Оглавление Введение Глава 1. Китайско-тибетские отношения до 1720 года:...»

«УДК616.66-007.26.089.168.1- 06.053.5 Худойбердиев Азиз Абдуганиевич Хирургическое лечение осложнений уретропластики при гипоспадии у детей. Специальность-5А720202 детская хирургия Диссертация на соискание академической степени магистра Научный руководитель : д.м.н., профессор Шамсиев Азамат...»

«УРБАН ОЛЬГА АНДРЕЕВНА СОЦИАЛЬНЫЙ МЕХАНИЗМ ИНСТИТУЦИОНАЛЬНОЙ ТРАНСФОРМАЦИИ ХОЗЯЙСТВА В МОНОПРОДУКТОВОМ РЕГИОНЕ Специальность 22.00.03 – экономическая социология и демография Диссертация на соискание ученой степени доктора социологических наук Научный консультант – доктор социологических наук, профессор Мостовая Е.Б. Новосибирск СОДЕРЖАНИЕ...»

«УДК БЕЛЯЕВА ЗОЯ ВЛАДИМИРОВНА ГЕОМЕТРИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОСТРАНСТВЕННЫХ КОНСТРУКЦИЙ 05.13.18 Математическое моделирование, численные методы и комплексы программ Диссертация на соискание ученой степени кандидата технических наук Научный руководитель доктор физико-математических наук, профессор...»

«Дурандин Никита Александрович ФИЗИКО-ХИМИЧЕСКИЕ ХАРАКТЕРИСТИКИ АНАЛОГОВ ОЛИВОМИЦИНА А И ИХ КОМПЛЕКСОВ С ДНК 02.00.04 – физическая химия Диссертация на соискание ученой степени кандидата химических наук Научный руководитель : Доктор химических наук, профессор Кузьмин Владимир Александрович Москва-2014 2 ВВЕДЕНИЕ. 1. ЛИТЕРАТУРНЫЙ ОБЗОР. 1.1 Типы...»

«ТУЧИН Андрей Георгиевич Баллистико-навигационное проектирование полётов к Луне, планетам и малым телам Солнечной системы Специальность 01.02.01 – Теоретическая механика Диссертация на соискание учёной степени доктора физико-математических наук Москва – 2010 Содержание Обозначения и сокращения Введение Глава 1 Проектирование квазисинхронных орбит КА вокруг Фобоса для решения задачи посадки...»

«Казаринов Никита Андреевич Динамические и волновые особенности процесса разрыва твердых тел при их квазистатическом нагружении Специальность 01.02.04 – механика деформируемого твердого тела ДИССЕРТАЦИЯ на соискание ученой степени кандидата физ.-мат. наук Научный руководитель член-корр. РАН доктор физ.-мат. наук, профессор Петров Ю.В. Санкт-Петербург 2014 Оглавление Основы механики разрушения. Эволюция критериев разрушения....»

«Серчугина Ольга Михайловна ОРГАНИЗАЦИЯ СИСТЕМЫ ВНУТРЕННЕГО КОНТРОЛЯ НА ОСНОВЕ ЗАКОНА САРБЕЙНСАОКСЛИ Специальность 08.00.12 – Бухгалтерский учет, статистика Диссертация на соискание ученой степени кандидата экономических наук Научный руководитель д.э.н., проф. Каморджанова Н.А. Санкт-Петербург 2014г. Оглавление Введение Глава 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ФОРМИРОВАНИЯ СИСТЕМЫ ВНУТРЕННЕГО КОНТРОЛЯ 1.1. Контроль как функция...»

«Иноземцева Татьяна Васильевна УПРАВЛЕНИЕ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИМ ПОТЕНЦИАЛОМ РАЗВИТИЯ СЕЛЬСКИХ МУНИЦИПАЛЬНЫХ ОБРАЗОВАНИЙ (на материалах Удмуртской Республики) Специальность 08.00.05 – региональная экономика ДИССЕРТАЦИЯ на соискание ученой степени кандидата экономических наук Научный руководитель доктор экономических наук профессор В. И. Некрасов Ижевск - 2006 СОДЕРЖАНИЕ ВВЕДЕНИЕ.. 1. ОСОБЕННОСТИ...»

«Волченко Татьяна Сергеевна ОПТИМИЗАЦИЯ ПАРАМЕТРОВ ВИБРОЗАЩИТЫ ГРУЗОВЫХ АВТОТРАНСПОРТНЫХ СРЕДСТВ ПО КРИТЕРИЮ МИНИМУМА ДИНАМИЧЕСКИХ НАГРУЗОК Специальность 01.02.06 Динамика, прочность машин, приборов и аппаратуры ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук Научный руководитель : д.т.н., профессор Шефер Л.А. Челябинск – 2014 СОДЕРЖАНИЕ ВВЕДЕНИЕ Глава ОБЗОР ЛИТЕРАТУРЫ И НАУЧНЫХ ИССЛЕДОВАНИЙ В...»

«Зарембо Наталия Александровна ПСИХОЛОГО-ПЕДАГОГИЧЕСКОЕ СОПРОВОЖДЕНИЕ ПРЕОДОЛЕНИЯ ТРУДНОСТЕЙ ВУЗОВСКОЙ АДАПТАЦИИ ВЫПУСКНИКОВ СЕЛЬСКИХ СРЕДНИХ ШКОЛ 19.00.07 – Педагогическая психология (психологические наук и) Диссертация на соискание ученой степени кандидата психологических наук Научный руководитель : доктор психологических наук, профессор Н.А. Рождественская Научный консультант : доктор...»

«Хасаншин Илгиз Абрарович ПРОЦЕССУАЛЬНЫЕ ГАРАНТИИ ПРАВ УЧАСТНИКОВ ПРОИЗВОДСТВА В АРБИТРАЖНОМ СУДЕ ПЕРВОЙ ИНСТАНЦИИ 12.00.15. – гражданский процесс, арбитражный процесс Диссертация на соискание ученой степени кандидата юридических наук Научный руководитель д.ю.н., проф. Валеев Д.Х. Казань-2014 Оглавление Введение..3 Глава 1. Сущность процессуальных гарантий в...»

«ЧУПРЫНОВА Мария Юрьевна ОСОБЕННОСТИ ТЕЧЕНИЯ HELICOBACTER PYLORI-АССОЦИИРОВАННОГО ГАСТРИТА У ПОДРОСТКОВ ПРИ ИНФИЦИРОВАНИИ СЛИЗИСТОЙ ОБОЛОЧКИ ЖЕЛУДКА ВИРУСОМ ЭПШТЕЙНА-БАРР 14. 01. 08 - педиатрия диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель : доктор...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

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