Главная >> Диссертации - все темы

Pages: |

| 2 |

«СКЕЛЕТНАЯ СЕГМЕНТАЦИЯ И ЦИРКУЛЯРНАЯ МОРФОЛОГИЯ МНОГОУГОЛЬНИКОВ ...»

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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М.В. Ломоносова

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

Кафедра математических методов прогнозирования

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

УДК 519.72,519.68

Домахина Людмила Григорьевна

СКЕЛЕТНАЯ СЕГМЕНТАЦИЯ И

ЦИРКУЛЯРНАЯ МОРФОЛОГИЯ

МНОГОУГОЛЬНИКОВ

01.01.09 - Дискретная математика и математическая кибернетика.

Диссертация на соискание степени кандидата физико-математических наук

Научный руководитель доктор технических наук, профессор Л.М. Местецкий Москва 2013 г.

Оглавление Введение Глава 1. Задача сегментации фигуры и скелета 1.1. Фигура 1.2. Скелетное и циркулярное представление фигуры 1.2.1. Скелет фигуры 1.2.2. Скелетное представление фигуры 1.3. Сегментация изображения, фигуры и скелета 1.3.1. Задача сегментации фигуры 1.3.2. Задача сегментации скелета 1.3.3. Геометрический граф 1.3.4. Скелетный граф 1.3.5. Циркулярный граф 1.3.6. Циркулярное представление фигуры 1.4. Обзор литературы 1.4.1. Методы сегментации фигуры 1.4.2. Примеры сегментации скелета в литературе 1.5. Скелетная сегментация фигуры 1.6. Качество скелетной сегментации 1.6.1. Некорректность задачи скелетизации 1.6.2. Устойчивость сегментации и регуляризация скелета по Тихонову 1.6.3. Базовая скелетная сегментация фигуры и ее свойства 1.7. Выводы главы Глава 2. Скелетная сегментация многоугольника на основе циркулярной морфологии 2.1. Метрические критерии сходства циркуляров 2.1.1. Расстояние Хаусдорфа для пары циркуляров 2.1.2. Погрешность аппроксимации фигуры циркуляром 2.1.3. Срединный циркуляр фигуры 2.2. Топологические критерии сходства циркуляров: изоморфизм 2.2.1. Изоморфизм скелетов 2.2.2. Изоморфизм циркуляров 2.3. Оператор проектирования на множестве циркуляров 2.3.1. Ветвь циркуляра 2.3.2. Подциркуляр 2.3.3. Максимальный простой подциркуляр и циркуляр уникальной проекции 2.3.4. Проектор максимальной длины 2.3.5. Модельное множество проектора максимальной длины 2.4. Морфологический анализ циркуляров: критериальные морфологии 2.4.1. Критериальные морфологии для множества циркуляров 2.4.2. Циркулярная функция штрафа 2.5. Базовый подциркуляр с контролируемой точностью 2.5.1. Стрижка терминального ребра и ветви циркуляра 2.5.2. Алгоритм построения монотонных цепочек подциркуляров на основе стрижки 2.5.3. Циркуляры общего положения 2.6. Базовый циркуляр с контролируемой точностью 2.6.1. Рекурсивное определение базового циркуляра с контролируемой точностью 2.7. Циркулярная функция соответствия 2.7.1. Задача поиска циркулярной проекции 2.7.2. Свойства циркулярной функции соответствия 2.7.3. Множество допустимых проекций циркулярной функции штрафа 2.7.4. Монотонность функции соответствия 2.8. Циркулярная функция устойчивости проекции 2.9. Свойства циркулярной функции штрафа 2.10. Выводы главы Глава 3. Скелетная сегментация и циркулярная морфология пары 3.2. Морфологический проектор с априорным условием изоморфизма 3.2.2. Функция устойчивости на основе априорной информации об 3.2.5. Морфологический проектор с априорным условием изоморфизма 3.2.6. Задача поиска проекции с априорным условием изоморфизма 3.3. Свойства функций, введенных на парах циркуляров 3.3.1. Описание множества допустимых проекций для пар циркуляров 3.3.2. Ограниченность множества допустимых проекций 3.3.3. Непрерывность функции соответствия на множестве допустимых 3.3.4. Непрерывность функции устойчивости на множестве 3.3.5. Непрерывность функции штрафа на множестве допустимых 3.3.6. Замкнутость множества монотонных изоморфных подциркуляров 3.4. Существование проектора с априорным условием изоморфизма 3.5. Единственность решения задачи поиска оптимальной проекции на 3.5.1. Задача поиска проекции на множестве циркуляров общего 3.5.2. Теорема о локализации одного решения задачи поиска проекции 3.5.3. Теорема о единственности решения задачи поиска проекции на 3.6. Решение задачи поиска проекции функции с априорным условием 3.6.2. Алгоритм проверки изоморфизма циркуляров 3.6.3. Поиск проекции функции с априорным условием изоморфизма в 3.6.4. Алгоритм поиска изоморфной пары в монотонных цепочках 3.7. Вычислительная сложность алгоритма решения задачи поиска 3.7.1. Вычислительная сложность алгоритма построения монотонных 3.7.2. Вычислительная сложность алгоритма проверки изоморфизма 3.7.3. Вычислительная сложность алгоритма решения задачи поиска 3.7.4. Оптимизация алгоритма решения задачи поиска проекции Глава 4. Сравнение формы на основе скелетной сегментации 4.1.1. Обзор известных методов сравнения формы с использованием 4.1.2. Проблемы при использовании скелета для сравнения формы 4.1.3. Новый подход к сравнению формы с использованием 4.2. Метрика на основе проектора — циркулярное расстояние с 4.2.1. Определение циркулярного расстояния с условием изоморфизма 4.2.2. Свойства циркулярного расстояния с условием изоморфизма 4.3.1. Экспериментальное пороговое циркулярное расстояние:

4.3.2. Экспериментальное пороговое циркулярное расстояние: свойства 4.4. Задача распознавания на основе скелетной сегментации 4.5. Сравнение формы: эксперименты с запросами Список основных обозначений:

B(c, ) — функция базового циркуляра c с контролируемой точностью > ct — круг с центром в точке t;

c = {ct,t T } — семейство кругов с центрами на множестве T — циркулярный граф;

#c — количество ребер циркуляра c;

cma (F) — срединный циркуляр фигуры F;

c — циркуляр из множества ;

c1 c2 — изоморфизм циркуляров;

c() — базовый подциркуляр циркуляра c c контролируемой точностью 0;

cB — базовый циркуляр c точностью для циркуляра общего положения deg(vi ) — степень вершины vi ;

DH (F1, F2 ) — расстояние Хаусдорфа между фигурами F1 и F2 ;

DH (c1, c2 ) — расстояние Хаусдорфа между циркулярами c1 и c2 ;

e, e0, e1 — ребра графа G = (V, E);

F, F1, F2 — многоугольные фигуры;

G = (V, E) — граф со множеством вершин V и множеством ребер E;

ma(F) — непрерывный скелет фигуры F (от английского ”medial axis” — срединные оси);

mg(c) — осевой граф циркуляра c (от английского ”medial graph”);

ma(F1 ) ma(F2 ) — изоморфизм скелетных графов фигур F1 и F2 ;

O(n) — линейная по параметру n вычислительная сложность алгоритма;

(c1, c2 ) — функция проверки изоморфизма циркуляров c1 и c2 ;

Pr — оператор проектирования;

Pr1 (c) — максимальный единичный проектор на множестве плоских циркуляров ;

Pr2 (c) — оператор проекции на максимальный стриженный подциркуляр;

(x, y) — евклидово расстояние между точками x R2 и y R2 ;

c (F1, F2 ) — циркулярное расстояние между фигурами F1 и F2 с условием изоморфизма;

R2 — евклидова плоскость;

Sil(c) = ct — силуэт циркулярного графа c;

— множество всех циркуляров на плоскости;

— множество всех циркуляров уникальной проекции на плоскости;

— множество всех циркуляров общего положения на плоскости;

2 = {(c1, c2 ) : c1, c2 } — множество всех пар циркуляров на плоскости;

2 = {(c1, c2 ) : c1, c2 } — множество всех пар циркуляров общего положения на плоскости;

2 = {(c1, c2 ) : c1, c2 : mg(c1 ) mg(c2 )} — множество всех пар изоморфных циркуляров на плоскости;

S (c ) = {c : Pr2 (c ) c c } — множество монотонных подциркуляров циркуляра c ;

B (c ) = {c : c = B(c, ), > 0} — множество всех базовых циркуляров циркуляра c ;

S (c1, c2 ) = {(c, c ) : c S (c1 ), c S (c2 )} — все пары монотонных подциркуляров пары (c1, c2 ) на плоскости;

S (c1, c2 ) = {(c, c ) : c S (c1 ), c S (c2 ) : mg(c ) mg(c )} — множество монотонных изоморфных подциркуляров пары циркуляров (c1, c2 ) на плоскости;

B (c1, c2 ) = {(c, c ) : c B (c1 ), c B (c2 ) : mg(c ) mg(c )} — множество пар изоморфных базовых циркуляров пары циркуляров (c1, c2 ) на плоскости;

Term(c0 ) — множество терминальных ветвей циркуляра c0.

v, v0, v1 — вершины графа G = (V, E);

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

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

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

В первом значении сегментация изображения понимается как выделение объекта интереса. Это разбиение всего изображения на отдельные фрагменты, соответствующие объектам или фону. Такое выделение осуществляется по цвету, текстуре, краю, низкочастотной или высокочастотной составляющей изображения. Для этого используется большой набор методов обработки изображений: точечные, пространственные, геометрические, алгебраические преобразования, фильтры, методы выделения краёв, спектральные разложения по различным системам базисных функций. Результатом сегментации является определение некоторых подмножеств изображения, которые содержательно соответствуют представленным на изображении объектам. Критерии такой сегментации обычно носят эвристический характер, выбираются в соответствии с конкретными задачами. Известные подходы, в частности, описаны в работах Ю.В.Визильтера [6, 7, 8], П.П.Кольцова [13]. Известна модель сегментации Мамфорда-Шаха [26]. Такую сегментацию естественно называть сегментацией объектов. В диссертации вопросы сегментации объектов не рассматриваются.

Тема диссертации относится к сегментации формы.

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

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

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

Такая постановка задачи сегментации формы существенно зависит от принятого способа описания формы объекта. Известны различные способы такого описания:

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

• бинарным растровым изображением в виде некоторого множества точек на целочисленной решётке;

• непрерывной границей объекта;

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

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

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

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

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

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

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

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

Актуальность Скелет является дескриптором формы. Скелетное представление дает полное описание фигуры, то есть по нему можно полностью восстановить фигуру.

Такое описание избыточно и не подходит для решения задачи классификации.

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

Таким образом, с одной стороны, скелетное представление формы открывает принципиальную возможность построения и использования скелетной сегментации при сравнении и классификации формы. Разработанные в последнее время методы описания формы дискретных изображений в виде непрерывного скелетного представления многоугольных фигур (Местецкий [15], Рейер [17], Семёнов [18]) позволяют использовать скелетное представление для анализа и распознавания изображений. С другой стороны, известные методы сегментации формы основываются на эвристических правилах, не имеют формальных критериев качества сегментации и не приспособлены для решения задач сравнения формы объектов.

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

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

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

Сложность этих задач обусловливается несколькими факторами.

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

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

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

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

Предлагаемое решение поставленных задач основывается на следующем подходе:

Во-первых, выделим две задачи скелетной сегментации:

• Задача генерации скелетных дескрипторов формы по критериям полноты описания — задача сегментации фигуры.

• Задача селекции скелетных признаков по критериям отделимости классов — задача сравнения формы фигуры.

Во-вторых, обозначим следующий подход к решению указанных задач:

(1) Задача сегментации фигуры:

(a) Циркулярное представление фигуры — задание полного описания фигуры. Данное представление содержит в себе ”лишнюю” информацию для описания формы.

(b) Определение признаков формы — множеств подциркуляров фигуры при помощи морфологических функций и проекций.

(d) Определение функции устойчивости образа.

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

(2) Задача сравнения формы фигур:

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

(b) Определение функции устойчивости пары образов — метрическая функция устойчивости.

(c) Селекция признаков по критериям отделимости классов — оптимизация по топологической и метрической функциям устойчивости.

(d) Определение меры сходства на паре образов.

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

(2) Критерий качества скелетной сегментации пары фигур.Метод скелетной сегментации пары фигур, основанный на минимизации циркулярной функции штрафа для пар.

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

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

Научная новизна (1) Подход к определению критерия качества скелетной сегментации фигуры через методы математической морфологии.

(2) Идея определения моделей сегментации формы на основе оптимизации по соответствию и качеству.

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

(4) Новый метод скелетной сегментации фигуры, основанный на минимизации циркулярной функции штрафа.

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

(6) Новый метод скелетной сегментации пары фигур на основе оригинального критерия качества.

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

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

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

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

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

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

Апробация Представленные в работе результаты докладывались и обсуждались на:

(1) 12-й, 13-й и 14-й всероссийских конференциях ”Математические методы распознавания образов” (Московская обл. 2005, Ленинградская обл.

2007 год, Владимирская обл. 2009 год);

(2) международных конференциях ”Интеллектуализация обработки информации - 2006” и ”Интеллектуализация обработки информации - 2008” (Симферополь 2006, 2008);

(3) международной научной конференции студентов, аспирантов и молодых ученых ”Ломоносов-2006” в секциях ”Математика и механика” и ”Вычислительная Математика и Кибернетика” (Москва 2006);

(4) научной школе-семинаре ”Дискретная математика и математическая кибернетика”, Московская область, март 2006;

(5) 18-й международной конференции по компьютерной графике и машинному зрению ”Графикон” (Москва 2008 год);

(6) 4-ой международной конференции по теории компьютерного зрения и приложениям (The fourth International Conference on Computer Vision Theory and Applications VISAPP- 2009), Лиссабон, Португалия 2009;

(7) 2-ом международном семинаре по анализу изображений: теории и приложениям (The Second International Workshop on Image Mining. Theory and Applications (IMTA 2009), Лиссабон, Португалия 2009;

(8) 10-й международной конференции по вычислительным наукам и приложениям (ICCSA 2010), Фукоука, Япония 2010 — победитель в номинации лучшая работа;

(9) семинарах ”Морфологический анализ данных”, Московский Государственный Университет имени М.В. Ломоносова, 2011.

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

(1) Домахин М.А., Местецкий Л.М., Мехедов И.С., Петрова Л.Г. Восстановление полутоновых изображений по изолиниям яркости. Труды Всероссийской конференции Математические Методы Распознавания Образов (ММРО-12), Москва„ 2005, с. 305-308.

(2) Петрова Л.Г., Местецкий Л.М. ”Построение гомеоморфизма односвязных многоугольных областей с изоморфными базовыми скелетами методом построения вложенных цепочек подграфов”. Труды XIII международной конференции студентов, аспирантов и молодых ученых, Москва, 2006, том 4, секция ”Математика и Механика” с. 69-70.

(3) Петрова Л.Г., Местецкий Л.М. ”Расчет гомеоморфизма многоугольников методом разбиения скругленных областей на собственные области ребер базовых скелетов”. Труды XIII международной конференции студентов, аспирантов и молодых ученых, Москва, 2006, секция ”Вычислительная Математика и Кибернетика” с. 32-33.

(4) Петрова Л.Г., Местецкий Л.М., Расчет гомеоморфизма односвязных многоугольных областей с изоморфными базовыми скелетами. Сборник ”Искусственный интеллект”, Таврический национальный университет им. В.И. Вернадского, г. Симферополь, Украина, 2006.

(5) Петрова Л.Г. Непрерывные модели преобразования растровых изображений // Сборник тезисов лучших дипломных работ 2006 года. М.: Издательский отдел Факультета ВМиК МГУ им. М.В. Ломоносова, 2006.

(6) Петрова Л.Г. Преобразование растровых изображений на основе непрерывных моделей гранично-скелетного представления, Сборник статей ВМиК МГУ, выпуск 2, 2006.

(7) Домахина Л.Г., Об одном методе сегментации растровых объектов для задач преобразования формы, Труды 13 Всероссийской конференции Математические Методы Распознавания Образов (ММРО-13), Ленинградская обл., г.Зеленогорск, 2007, с. 312-315.

(8) Домахина Л.Г., Охлопков А.Д. Изоморфные скелеты растровых изображений, Труды 18 международной конференции ГРАФИКОН-2008, (9) Домахина Л.Г. Устойчивость скелетной сегментации, журнал Таврический вестник информатики и математики. Изд-во НАН Украины, 2008.

(10) L. Domakhina, A. Okhlopkov Shape Comparison Based on Skeleton Isomorphism, The Proceedings of the the fourth International Conference on Computer Vision Theory and Applications (VISAPP), Lisbon, Portugal, (11) L. Domakhina Skeleton-Based Shape Segmentation, The Proceedings of the Second International Workshop on Image Mining. Theory and Applications (IMTA 2009), Lisbon, Portugal, 2009.

(12) Домахина Л.Г., Регуляризация скелета для задачи сравнения формы, Труды 14 Всероссийской конференции Математические Методы Распознавания Образов (ММРО-14), Суздаль, 2009, с. 342-346.

(13) Domakhina L.G. Skeleton-Based Segmentation and Decomposition of Raster Pairs of Shapes // Pattern Recognition and Image Analysis, No. 3, 2010, pp.293- (14) Домахина Л.Г. Критериальные и проективные морфологии для множества плоских циркуляров // Журнал вычислительной математики и математической физики, № 7, 2012.

(15) Liudmila Domakhina ”On the Minimization of a Circular Function on the Isomorphic Shrunk Subset,” ICCSA, pp.51-60, 2010 International Conference on Computational Science and Its Applications, 2010 (победитель в номинации ”лучший доклад”).

Обоснование специальности По специальности 01.01.09 - ”Дискретная математика и математическая кибернетика” работа относится к направлениям ”1. Дискретная математика” и ”5.

Математическая теория распознавания и классификации”.

Внедрение результатов Выносимые на защиту методы были разработаны, исследованы и практически использованы в ходе работ по проектам Российского Фонда фундаментальных исследований (РФФИ) 05-01-00542 ”Методы распознавания формы изображений на основе дискретно-непрерывных преобразований”; 08-01Методы анализа и распознавания формы изображений на основе непрерывных моделей”.

Представленные в работе результаты частично вошли в книгу Ю.В. Визильтера и соавторов ”Обработка и анализ изображений в задачах машинного зрения” [8], рекомендованную в качестве учебного пособия в технических ВУЗах.

Структура диссертации

Работа состоит из оглавления, введения, четырех глав, заключения и списка литературы. Содержание работы изложено на 149 страницах. Список литературы включает 75 наименований. Текст работы иллюстрируется 48 рисунками и 6 таблицами.

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

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

Рассматривается вопрос качества сегментации. Описаны неустойчивые элементы (нерегулярности) скелетной сегментации. Рассматривается понятие базового скелета и базовой скелетной сегментации на его основе.

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

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

Четвертая глава относится к задаче сравнения формы плоских фигур.

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

Описываются эксперименты по применению данных методов к задаче распознавания формы.

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

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

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

Необходимо определить объекты, с которыми мы работаем.

ОПРЕДЕЛЕНИЕ 1 (Область). Область на евклидовой плоскости — непустое связное открытое множество точек [2].

ОПРЕДЕЛЕНИЕ 2 (Замкнутая область). Замкнутая область на плоскости — минимальное замкнутое множество на плоскости, содержащее область.

ОПРЕДЕЛЕНИЕ 3 (Нормальная область). Нормальная область [35] — ограниченная замкнутая область, граница которой представляет собой объединение конечного числа замкнутых контуров, каждый из которых в свою очередь состоит из конечного числа участков аналитических кривых.

ОПРЕДЕЛЕНИЕ 4 (Непрерывная фигура). Непрерывной фигурой будет считаться любая нормальная область.

ОПРЕДЕЛЕНИЕ 5 (Односвязная непрерывная фигура). Если в границе непрерывной фигуры всего один контур, то фигура односвязна.

ОПРЕДЕЛЕНИЕ 6 (Простая непрерывная фигура). Простая непрерывная фигура — односвязная непрерывная фигура.

ОПРЕДЕЛЕНИЕ 7 (Простой многоугольник). Простой многоугольник — замкнутая ломаная без самопересечений [34].

ОПРЕДЕЛЕНИЕ 8 (Простая многоугольная фигура). Простая многоугольная фигура — замкнутая область, ограниченная простым многоугольником [15].

ОПРЕДЕЛЕНИЕ 9 (Многосвязная фигура). Если в границе непрерывной фигуры более одного контура, то фигура многосвязна.

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

На рисунке 1.1 изображены примеры различных фигур.

1.2. Скелетное и циркулярное представление фигуры 1.2.1. Скелет фигуры.

ОПРЕДЕЛЕНИЕ 10 (Пустой круг). Пустым кругом фигуры F называется замкнутое множество точек Sr (p) = {q : q R2, p R2, r 0, d(p, q) r} такое, что Sr (p) F. При r = 0 Sr (p) также является пустым кругом.

ОПРЕДЕЛЕНИЕ 11 (Максимальный пустой круг). Максимальным пустым кругом фигуры называется пустой круг фигуры, который не содержится ни в одном другом пустом круге фигуры.

ОПРЕДЕЛЕНИЕ 12 (Скелет фигуры). Скелетом ma(F) фигуры F [16] (рис. 1.2) называется множество центров всех ее максимальных пустых кругов.

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

F — фигура;

ma(F) — скелет фигуры F (medial axes).

Такой скелет также называют множеством срединных осей [35].

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

ОПРЕДЕЛЕНИЕ 13 (Cкелетное представление фигуры). Cкелетное представление фигуры [15] — это ее скелет вместе с множеством всех вписанных пустых кругов.

Рис. 1.3. Циркулярное представление фигуры.

1.3. Сегментация изображения, фигуры и скелета Рассмотрим подробно понятия ”сегментация изображения”, ”сегментация фигуры” и ”сегментация скелета”.

ОПРЕДЕЛЕНИЕ 14 (Сегментация изображения). Сегментация изображения — выделение на нем объектов (рис. 1.4) [52].

Рис. 1.7. Сегментация, отражающая структуру фигуры.

Рис. 1.8. Сегментация, неустойчивая к граничным шумам.

ОПРЕДЕЛЕНИЕ 15 (Сегментация фигуры). Под сегментацией фигуры будем понимать ее разбиение на конечное множество областей (рис. 1.5).

ОПРЕДЕЛЕНИЕ 16 (Сегментация скелета). Сегментация скелета — его конечное разбиение.

На рис. 1.6 изображена фигура и ее сегментированный скелет.

1.3.1. Задача сегментации фигуры. Задача сегментации фигуры в общем виде — построить разбиение фигуры.

1.3.2. Задача сегментации скелета. Задача сегментации скелета в общем виде — построить скелет и его разбиение.

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

Примеры критериев для задачи сегментации фигуры:

(1) Сегментация задает представление структуры фигуры (рис. 1.7 — пример сегментации фигуры, отражающей структуру).

Рис. 1.9. Сегментация скелета, устойчивая к незначительным деформациям фигуры.

Рис. 1.10. Сегментация скелета, сходная для пары фигур.

(2) Устойчивость к граничным шумам (рис. 1.8 — пример неустойчивой к граничным шумам сегментации фигуры).

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

(4) Сходство для похожих фигур (рис. 1.10 — пара похожих фигур со сходными сегментациями).

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

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

ОПРЕДЕЛЕНИЕ 17 (Геометрический граф). Геометрический граф G [56] — это совокупность G =< V, E >, где V - непустое множество точек пространства, а E — множество простых кривых (возможно, направленных), удовлетворяющих следующим условиям:

1. каждая замкнутая кривая множества E содержит только одну точку множества V ;

2. каждая незамкнутая кривая множества E содержит ровно две точки множества V — ее граничные точки;

3. кривые множества E не имеют общих точек, за исключением точек из множества V.

Элементы множества V называют вершинами графа, а само это множество - носителем графа; элементы множества E называются ребрами графа, а само E — его сигнатурой.

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

1.3.4. Скелетный граф. Скелет фигуры можно рассматривать как геометрический граф.

ОПРЕДЕЛЕНИЕ 18 (Вершина скелета). Вершинами скелета назовем все центры максимальных пустых кругов, кроме тех, что касаются границы фигуры в двух точках.

ОПРЕДЕЛЕНИЕ 19 (Ребро скелета). Ребром скелета, соединяющим две вершины, назовем срединные оси фигуры, состоящие из центров окружностей, каждая из которых касается границы ровно в двух точках.

ОПРЕДЕЛЕНИЕ 20 (Скелетный граф). Геометрический граф с множеством вершин и ребер скелета назовем скелетным графом.

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

• вершины скелетного графа — точки разбиения;

• ребра скелетного графа — элементы разбиения.

1.3.5. Циркулярный граф. Понятие ”гранично-скелетного представления” было обобщено [15], [18] до циркулярного представления фигуры.

ОПРЕДЕЛЕНИЕ 21 (Циркулярный граф, силуэт циркулярного графа). Рассмотрим множество точек T евклидовой плоскости R2, имеющее вид геометрического графа. С каждой точкой t T связан круг Ct с центром в этой точке. Семейство кругов c = {Ct,t T } называется циркулярным графом [15] или циркуляром. Граф T называется осевым графом циркулярного графа. Объединение Sil(c) = Ct всех кругов семейства c называется силуэтом циркулярного графа.

c = {Ct,t T } — обозначение циркулярного графа;

Ct — обозначение круга на осевом графе циркуляра;

Sil(c) — обозначение силуэта циркулярного графа c;

— множество всех циркуляров на плоскости.

1.3.6. Циркулярное представление фигуры. Рассмотрим фигуру F и ее скелетный граф c множеством максимальных пустых кругов C(F) (их центры и образуют скелетный граф) {ma(F),C(F)}. Получим циркуляр, образованный семейством этих кругов. Рассмотрим множество всех точек, принадлежащих множеству кругов C(F). Это множество совпадает с исходной фигурой F. При этом данное представление можно использовать для генерации дескрипторов формы, поэтому оно будет использоваться далее в настоящей работе (рис. 1. [15]).

ОПРЕДЕЛЕНИЕ 22 (Циркуляр фигуры). Описанное циркулярное представление на основе скелетного графа будем называть циркуляром фигуры.

Аналогично с обозначением скелета фигуры ma(F) обозначим mg(c) — осевой граф циркулярного представления.

1.4.1. Методы сегментации фигуры. Существующие методы сегментации фигуры (рис. 1.12) можно условно разбить на два класса:

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

(2) Основанные на информации о внутренней структуре.

В качестве методов сегментации, не связанных с построением скелета, можно выделить морфологические подходы [70, 71], в которых происходит разбиение фигуры с использованием заданного структурного элемента путем морфологических операций (эрозия, открытие, закрытие). В работе [71] — пример ”эффективной и точной” сегментации формы. Основной целью предложенного авторами [71] разбиения фигур было предотвращение ”перекрытий” при морфологическом разбиении фигуры. Также авторы [71] указывают на то, что их метод дает значительно меньше компонент фигуры в разбиении по сравнению с некоторыми другими методами. В работе [27] основной задачей является разбиение фигуры на так называемую ”основную форму” и ”дополнительные отклонения” от нее. Для решения этой задачи используются дескрипторы Фурье, которые дают базовые характеристики формы такие как вытянутость, эллиптические и циркулярные характеристики. Внутренние свойства фигуры не рассматриваются. В [59] приведен пример разбиения на основе анализа выпуклости фигуры. Единственным его достоинством является простота. О стабильности таких подходов нет речи. Аналогичный подход предложен в [53]. В этой работе авторы говорят о ”визуальном качестве” их подхода, так как выпуклые части фигуры визуально выделяются и должны быть отнесены к различным областям сегментации. Шумы на границе предлагается устранить с помощью выбора подходящей аппроксимирующей фигуры.

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

Методы второго класса часто используют скелеты [43, 54, 65, 66]. Большинство известных методов не содержат корректных критериев выбора метода сегментации. Нет критериев сегментации для работы с парами фигур.

В [43] предложены критерии качества сегментации:

(1) полнота — сегментация содержит всю информацию об объекте;

(2) компактность — сегментация содержит небольшое количество информативных компонент;

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

(4) высокая алгоритмическая скорость вычислимости.

Авторы [43] предлагают представление формы, основанное на ”деревьях симметричных осей”. Обосновывается полнота предложенного представления [43]. Вычислительная скорость построения представления равна O(N 4 ) по количеству вершин контура. Компактность и робастность представления показаны на примерах.

Имеется ряд работ, в которых рассмотрены дискретные фигуры и для построения разбиения используются дискретные скелеты. Например, [65] представляет иерархическое разбиение, основанное на осевом графе фигуры — дискретном скелете (модель, в которой граница фигуры и скелет представлены в виде растровых изображений). Обоснованием выбора метода является тот факт, что осевой граф отражает геометрические свойства фигуры, а иерархическое представление фигуры может быть использовано для задач определения коллизий (пересечений двух объектов) [46]. Метод обладает всеми недостатками, присущими дискретному скелету: отсутствие строгого определения, наличие шумовых ветвей, затрудняющих анализ формы [15].

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

В качестве методов сегментации, не связанных с построением скелета, можно выделить морфологические подходы [70, 71], в которых происходит разбиение фигуры с использованием заданного структурного элемента путем морфологических операций: эрозия и дилатация — строятся вложенные по эрозии скелетные подмножества. В работе [71] — пример ”эффективной и точной” сегментации формы с использованием восьми структурных элементов. Делается 8 разбиений при помощи эрозии, из которых затем составляется одно оптимальное со структурирующим элементом восьмиугольником. Основной целью предложенного авторами разбиения фигур было предотвращение ”перекрытий” при морфологическом разбиении фигуры. Также авторы указывают на то, что их метод дает значительно меньше компонент фигуры в разбиении по сравнению с некоторыми другими методами.

В [59] приведен пример разбиения на основе анализа выпуклости фигуры.

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

Аналогичный подход предложен в [53]. В этой работе авторы говорят о ”визуальном качестве” их подхода, так как выпуклые части фигуры визуально выделяются и должны быть отнесены к различным областям разбиения.

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

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

Данный скелет можно также представить в виде скелетного графа и строить его сегментацию. Преимущества при выборе такого скелета для решения прикладных задач обосновывается тем, что все ребра такого скелета — линейные отрезки, что является преимуществом по сравнению со множеством срединных осей [35], в котором встречаются отрезки парабол. Преимущество линейного скелета также его простая алгоритмическая вычислимость. Тем не менее вычислительная сложность не может быть по определению ниже субкубической: O(n log2 n [37] или O(n1+ ) [42] по числу ребер многоугольника. Кроме того, линейный скелет для фигур с большими невыпуклыми углами, очень далек от множества центральных осей и представляет собой сомнительный инструмент для использования на практике (рис. 1.15).

В работе [67] предложено разбиение простого многоугольника на основе линейного скелета [28]. Данное разбиение обладает теми же недостатками, что и сам линейный скелет. Значимые части, выделяемые при помощи такого подхода, обоснованы лишь ”визуальным качеством”. Кроме того, построение линейного скелета имеет большую вычислительную сложность по сравнению с множеством срединных осей.

В работе [66] предлагает метод разбиения простого многоугольника на значимые части, основанный на прямолинейных скелетах (рис. 1.15). При этом даже для пары похожих фигур указанный метод не всегда дает одни и те же значимые части. Это означает, что значимые части определены некорректно, и метод неустойчив и неприменим к задачам распознавания и морфинга.

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

1.4.2. Примеры сегментации скелета в литературе. Скелет обладает рядом недостатков, таких как шумовые ребра и иные нерегулярности. Поэтому во многих работах рассмотрены модификации скелетных графов. Более подробно нерегулярности скелета будут рассмотрены во второй главе.

Рис. 1.14. Скелетный граф на основе базового скелета.

В работах [60], [49], [61] предлагается модифицировать скелетные графы пары фигур при помощи операций ”стрижка” и ”склейка” ребер скелетных графов до получения скелетных графов одинаковой структуры. При этом происходит (1) получение скелетов определенного вида;

(2) сегментация полученных скелетных графов на ребра (рис. 1.13).

И.А. Рейер [17] предлагает метод построения подграфа скелетного графа в виде базового скелета (рис. 1.14).

Прямолинейный скелет, предложенный Mirela Tanase [66], представляет собой модификацию линейного скелета, предложенного Aichholzer и Aurenhammer [28]. Он состоит также лишь из прямолинейных отрезков, но имеет ту же топологию, что и множество срединных осей и приближен к нему (рис. 1.16). В работе Mirela Tanase [66] предложен метод декомпозиции фигуры на основе прямолинейного скелета.

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

ОПРЕДЕЛЕНИЕ 23 (Собственная область ребра скелета). Собственная область ребра скелета — это минимальное подмножество точек фигуры, ограниченное ребром скелетного графа и соответствующими радиальными отрезками (перпендикулярами, опущенными из вершин скелетного графа).

ОПРЕДЕЛЕНИЕ 24 (Скелетная сегментация фигуры). Скелетной сегментацией фигуры [9] будем называть ее разбиение (рис. 1.17) на собственные области, связанные с ребрами скелетного графа.

На рисунке 1. (a) граница фигуры;

(b) скелет (скелетный граф с заданными вершинами представляет собой скелетную сегментацию);

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

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

Рассмотрим:

• виды нерегулярностей скелета;

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

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

1.6.1. Некорректность задачи скелетизации.

ОПРЕДЕЛЕНИЕ 25 (Корректно поставленная задача). Задача поставлена корректно (задача корректна) [23] если (1) задача разрешима при любых входных данных;

(2) имеется единственное решение;

(3) решение непрерывно зависит от входных данных (малому изменению входных данных соответствует малое изменение решения) - иными словами задача устойчива.

Возникает вопрос: корректно ли поставлена задача скелетизации? Проведем анализ скелета.

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

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

рис. 1.19: две фигуры звезды, одна из которых имеет неровную границу — скелет такой звезды имеет множество ветвей скелета, исходящих из выпуклых рис. 1.20: две фигуры человечков, руки которых находятся в разных положениях — при обходе их скелетных графов в одинаковом направлении, некоторые вершины ”меняются местами”;

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

Первая ”нерегулярность” непрерывного скелета — это терминальные шумовые ребра, вызванные неровностью границы фигуры, не имеющие ничего общего со структурой фигуры (рис. 1.19).

рудиментные терминальные ребра неровности границы фигуры: рис. 1. перехлест внутренних вершин короткие внутренние ребра: рис. 1. Рис. 1.19. Рудиментные ребра скелетного графа.

Вторая ”нерегулярность” кроется во внутренних ребрах скелета: при незначительных вариациях фигуры внутренние узлы короткого ребра скелета могут поменяться местами — перехлест внутренних узлов скелета (рис. 1.20).

Вывод: скелетизация — некорректная задача по Адамару [24] в том смысле, что не обладает устойчивостью. Метод решения некорректных задач — получение некоторого приближенного решения, которое было бы более устойчивым [24]. Такой метод называется регуляризацией по Тихонову.

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

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

Например, при помощи ”склейки” (рис. 1.21) близко (в некоторой метрике) расположенных вершин [10].

В данной работе будет подробно рассмотрен первый вид нерегулярностей — рудиментные терминальные ребра. Для устранения данного вида нерегулярностей будут предложены теоретически обоснованные методы.

1.6.2. Устойчивость сегментации и регуляризация скелета по Тихонову.

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

ОПРЕДЕЛЕНИЕ 26 (Устойчивость геометрических объектов). Устойчивость применительно к геометрическим или иным объектам, зависящим от параметров, — это непрерывная зависимость этих объектов от параметров [4].

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

ОПРЕДЕЛЕНИЕ 27 (Устойчивость скелета). Скелет, полученный с помощью оператора : F Sk устойчив на паре метрических пространств (, ) с расстояниями (F1, F2 ) и (Sk1, Sk2 ), если для всякого > 0 существует такое () > 0, что для любых двух фигур F1, F2 из неравенства (F1, F2 ) < следует неравенство (Sk1, Sk2 ) < (), где Sk1 = (F1 ), Sk2 =(F2 ).

Зададим в явном виде расстояния (F1, F2 ) и (Sk1, Sk2 ).

ОПРЕДЕЛЕНИЕ 28 (Расстояние Хаусдорфа между двумя подмножествами метрического пространства). Пусть (x, y) — евклидово расстояние между точками x R2 и y R2. Тогда расстоянием Хаусдорфа между некоторыми компактными множествами F1 = {x R2 } и F2 = {y R2 } (подмножества R2 ) назовем величину ОПРЕДЕЛЕНИЕ 29 (Топологическое скелетное расстояние). Топологическим скелетным расстоянием (Sk1, Sk2 ) на множестве назовем модуль разности числа ребер скелетных графов Sk1 и Sk2.

ТЕОРЕМА 1. Оператор непрерывного скелета ma : F Sk неустойчив на паре метрических пространств (, ) — пространство фигур и скелетных графов с расстояниями (.,.) — расстояние Хаусдорфа, (.,.) — топологическое скелетное расстояние.

ДОКАЗАТЕЛЬСТВО. Перепишем определение неустойчивости. Существует такое > 0, что для любого > 0, найдутся две фигуры F1, F2, что из неравенства (F1, F2 ) < следует неравенство (Sk1, Sk2 ) >, где Sk1 = (F1 ), Sk2 =(F2 ). Пример: 2 звезды (одна с ”бахромой”, другая — нет - рис. 1.19).

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

ОПРЕДЕЛЕНИЕ 30 (Максимальная евклидова цепь скелета фигуры). Максимальная евклидова цепь скелета фигуры Sk0 — подграф скелета, состоящий из цепочки ребер максимальной длины среди всевозможных цепочек, являющихся подграфами скелета фигуры.

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

Пусть Sk j = {e1, e2,..., en } F — произвольная цепочка из этого множества.

Тогда ее длина равна сумме длин всех ребер цепочки:

Тогда максимальная евклидова цепь скелета фигуры F —это такая цепочка Sk0 F, что ее длина максимальна:

ОПРЕДЕЛЕНИЕ 31 (Однореберный скелетный оператор). Обозначим ma0 : F Sk0 — однореберный скелетный оператор, который по фигуре строит максимальную евклидову цепь ее скелета (рис. 1.22в).

ТЕОРЕМА 2. Однореберный скелетный оператор ma0 : F Sk0 устойчив на паре метрических пространств (, ) с расстояниями (.,.) — расстояние Хаусдорфа и (.,.) — топологическое скелетное расстояние.

ДОКАЗАТЕЛЬСТВО. По определению для любого сколь угодно малого > и для любых двух фигур F1, F2 однореберный оператор строит скелетные графы, состоящие ровно из одного ребра. А значит, если положить, например () = > 0, в любом случае неравенство (Sk1, Sk2 ) < () будет верным, так как число ребер в каждом из скелетов Sk1 и Sk2 равно единице, следовательно:

Однореберный скелетный оператор ma0 (F) для задач сравнения формы не несет в себе достаточной информации, хотя может быть использован как признак описания фигуры. Оператор ma(F) неустойчив, что делает его для задач сравнения формы также непригодным. Необходимо найти какой-то промежуточный скелетный оператор (рис. 1.22б) между неустойчивым, содержащим в себе ”лишнюю” информацию (ma(F)—рис. 1.22а) и устойчивым, но содержащим в себе мало информации (ma0 (F)—рис. 1.22в). Для этого можно использовать регуляризацию по Тихонову [24]. Предлагается определить некоторый функционал, минимизация которого и даст этот ”оптимальный”, то есть достаточно устойчивый, но при этом информативный скелетный оператор.

Рис. 1.22. Регуляризация скелета: а-непрерывный скелет; б-промежуточный скелет; в-устойчивое решение.

Рис. 1.23. Устранение рудиментных терминальных ребер — базовый скелет.

1.6.3. Базовая скелетная сегментация фигуры и ее свойства. Поиск некого промежуточного решения рассмотрен в различной известной литературе. Чаще всего в основе лежит стрижка ветвей скелета по некоторому критерию. Например, в работе [66] выполняется стрижка всех терминальных ребер скелета. Большинство методов стрижки эвристические. Математически строго определенный метод — построение базового скелета с фиксированной точностью аппроксимации [17] (рис. 1.23 — рисунок взят из книги [15]). Рассмотрим его подробнее.

Базовый скелет фигуры ОПРЕДЕЛЕНИЕ 32 (Укороченный подграф скелета). Рассмотрим скелет S = ma(F) фигуры F. С каждой точкой скелета s S связан максимальный пустой круг радиуса r(s) фигуры F: V (s) = {v : (v, s) r(s)}. Объединение VS = множества максимальных пустых кругов с центрами на ветвях скелета совпадает с самой фигурой F, т.е. VS = C. Пусть S = (P, E ) некоторый связный Рис. 1.24. Построение силуэта подграфа скелета: (а) многоугольная фигура, (б) скелет фигуры, (в) укороченный подграф, (г) силуэт подграфа.

подграф скелета S = (P, E), такой, что P P, E E и среди ребер из множества E \ E нет циклических ребер скелета S. Это означает, что граф S может быть получен из скелета S путем удаления (”обрезки”) части вершин и ребер скелета S, причем удаление не разрушает циклов и не нарушает связности графа. Такой граф S будем называть укороченным подграфом скелета S.

ОПРЕДЕЛЕНИЕ 33 (Силуэт фигуры). Рассмотрим фигуру VS = sS V (s), образованную путем объединения всех максимальных пустых кругов, центры которых лежат на укороченном подграфе S. Такую фигуру будем называть силуэтом подграфа S. Важное свойство силуэта укороченного подграфа — топологическая эквивалентность фигуре F. В частности, силуэт представляет собой связное множество.

На рис. 1.24 представлен пример построения силуэта (рисунок взят из книги [15]).

ОПРЕДЕЛЕНИЕ 34 (Базовый скелет фигуры). Базовым скелетом фигуры F с точностью будем называть такой минимальный (как минимальное множество точек) укороченный подграф S ее скелета S, для силуэта которого VS выполнено условие DH (F,VS ), где — заданная положительная величина, а DH — расстояние Хаусдорфа между фигурой F и силуэтом VS Базовый скелетный граф является подграфом скелета фигуры фигуры F:.

Рис. 1.25. Базовая скелетная сегментация различных фигур.

На рисунке 1.25 — пример базовых скелетов и на их основе скелетных сегментаций различных фигур.

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

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

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

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

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

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

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

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

– инструментами для регуляризации скелета являются понятия ”базовый скелет” и ”изоморфизм скелетов”;

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

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

• Скелет — неустойчивая конструкция, чувствительная к локальным изменениям границы фигуры.

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

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

– Качество скелетной сегментации строго определяется через понятие устойчивость и регуляризация скелета по Тихонову.

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

– Базовый скелет фигуры улучшает качество скелетной сегментации.

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

Скелетная сегментация многоугольника на основе циркулярной В данной главе решаются две главные задачи:

(1) Определение критерия качества скелетной сегментации многоугольника.

(2) Построение наилучшей (оптимальной) сегментации многоугольника с использованием критерия качества.

Для определения оптимальной скелетной сегментации предлагается использовать аппарат критериальной проективной математической морфологии [6], обобщающей свойства морфологий Пытьева [21] и Серра [72]. Предлагается применить морфологии для циркулярного представления фигур [18], [15] с использованием введенных на множестве циркуляров топологических и метрических критериев.

Формализация понятий в области циркулярного представления через понятийный аппарат математической морфологии Пытьева [21], Серра [72] и Визильтера [6] позволяет:

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

(2) поставить задачу поиска проекции морфологического проектора с априорным условием изоморфизма на множестве монотонных циркуляров;

(3) установить связь базового скелета [17] и функции соответствия [6], введенных на множестве циркуляров.

Для решения поставленных задач предлагается:

(1) формализовать теорию морфологий для множества циркуляров:

(2) определить функции на множестве пар циркуляров:

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

(4) доказать, что решение поставленной задачи существует;

(5) решить поставленную задачу конструктивно при помощи метода стрижки циркуляров:

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

• доказать, что решение при условии уникальности терминальной • найти решение за полиномиальное время.

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

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

2.1.1. Расстояние Хаусдорфа для пары циркуляров.

ОПРЕДЕЛЕНИЕ 35 (Расстояние между парой циркуляров). Расстоянием между циркулярами c1 и c2 назовем величину, равную расстоянию Хаусдорфа между их силуэтами:

2.1.2. Погрешность аппроксимации фигуры циркуляром.

ОПРЕДЕЛЕНИЕ 36 (Погрешность аппроксимации фигуры циркуляром). Погрешностью аппроксимации непрерывной фигуры F циркуляром c назовем расстояние Хаусдорфа между непрерывной фигурой и силуэтом циркулярного графа:

DH (F, Sil(c)).

ОПРЕДЕЛЕНИЕ 37 (Точная аппроксимация фигуры циркуляром). Циркулярное представление аппроксимирует непрерывную фигуру точно, если погрешность этой аппроксимации равна нулю.

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

2.1.3. Срединный циркуляр фигуры.

ОПРЕДЕЛЕНИЕ 38 (Срединный циркуляр фигуры). Назовем срединным циркуляром cma (F) фигуры F такой циркуляр, что mg(cma (F)) ma(F);

• множество максимальных вписанных пустых кругов фигуры F — множество кругов циркуляра cma (F).

ЛЕММА 1. Любой плоской фигуре F соответствует единственный срединный циркуляр.

ДОКАЗАТЕЛЬСТВО. Следует из того, что скелет (множество срединных осей) и соответствующее множество вписанных пустых кругов однозначно определены для каждой фигуры.

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

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

2.2.1. Изоморфизм скелетов. Рассмотрим два скелетных графа на плоскости.

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

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

(1) опустим радиальные отрезки из всех вершин скелетного графа к границе фигуры;

(2) определим последовательность точек P = {p1, p2,..., pN } на границе фигуры следующим образом: это все терминальные вершины скелета, которые лежат на границе фигуры и все точки касания радиальных отрезков; этому множеству соответствует множество всех вершин скелетного (3) фиксируем одну точку p1 ;

(4) упорядочим последовательность точек P = {p1, p2,..., pN } на границе фигуры таким образом: P = {p j1, p j2,..., p jN }, что для любой пары p ji, p ji+1 между ними на куске границы фигуры, их соединяющей, не содержится никакой другой точки p jk ;

(5) такое упорядочение можно сделать всего двумя способами и оно задает обход фигуры; назовем его ”упорядочиванием вершин скелетного графа по обходу фигуры”;

(6) определим направление обхода: он положительный, если сумма векторных произведений положительна, отрицательный — если она отрицательна;

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

ОПРЕДЕЛЕНИЕ 39 (Сохранение ориентации вершин скелетных графов при отображении). Будем говорить, что отображение вершин скелетных графов : V 1 V 2 (v1 v1,..., v1 v1 ) сохраняет ориентацию, если при их упорядоn n чивании по положительному направлению обхода фигур c начальных вершин ется полное соответствие:

то есть v21 = (v11 ), v22 = (v12 ),..., v2n = (v1n ) Иными словами отображение инвариантно относительно упорядочивания множеств вершин скелетных графов в одном и том же направлении (положительном).

ОПРЕДЕЛЕНИЕ 40 (Изоморфизм скелетов). Будем говорить, что два скелета изоморфны, если существует изоморфизм соответствующих скелетных графов [25], сохраняющий ориентацию вершин двух скелетных графов.

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

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

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

Обозначим V (c) — множество вершин осевого графа mg(c) всех степеней, кроме вершин степени равной двум.

Обозначим E(c) — множество ветвей осевого графа mg(c).

ОПРЕДЕЛЕНИЕ 41 (Изоморфизм осевых графов циркуляров). Два осевых графа циркуляров c1 и c2 изоморфны: mg(c1 ) mg(c2 ), если (1) существует биекция V (c1 ) V (c2 ), соответствующих осевых графов c (2) существует биекция соответствующих ветвей E(c1 ) E(c2 );

(3) биекция сохраняет ориентацию любых трех подряд идущих вершин из множеств V (c1 ) и V (c2 ) при положительном направлении обхода двух осевых графов.

Таким образом, отличие изоморфизма осевых графов от изоморфизма скелетов заключается в том, что ”ветвь” осевого графа рассматривается с точки зрения отображения как ”ребро”.

ОПРЕДЕЛЕНИЕ 42 (Изоморфизм циркуляров). Два циркуляра c1 и c2 изоморфны, если существует изоморфизм соответствующих осевых графов, сохраняющий ориентацию вершин обхода двух осевых графов: mg(c1 ) mg(c2 ).

2.3. Оператор проектирования на множестве циркуляров Рассмотрим проективные и критериальные морфологии на множествах циркуляров и пар циркуляров в терминологии, введенной в работах Визильтера [6], [7].

Сначала определим оператор проектирования (проектор) на множестве плоских циркуляров.

Пусть имеется множество.

Введем на оператор проектирования Pr: A (2) Pr(0) = 0; 0 — нулевой элемент множества.

(3) Pr(A) = Pr(Pr(A)) ОПРЕДЕЛЕНИЕ 43 (Модельное множество проектора). Множество собственных (стабильных) элементов проектора назовем модельным множеством или моделью [7].

Проектор Pr имеет смысл оператора проектирования образа на модель M.

2.3.1. Ветвь циркуляра.

ОПРЕДЕЛЕНИЕ 44 (Инцидентность ребра и вершины графа). Если v1, v2 — вершины графа, а e = (v1, v2 ) — соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны [25].

ОПРЕДЕЛЕНИЕ 45 (Терминальная вершина скелета). Вершина скелета, имеющая одно инцидентное ребро, называется терминальной, более одного - узлом скелета [15].

ОПРЕДЕЛЕНИЕ 46 (Терминальное и внутреннее ребро скелета). Ребро скелета называется терминальным, если оно содержит хотя бы одну терминальную вершину скелета, иначе — внутренним.

ОПРЕДЕЛЕНИЕ 47 (Путь в графе). Путем в графе G = (V, E) [25] называется последовательность вершин и ребер, в которой каждый элемент кроме v0 и v инцидентен предыдущему и последующему.

Число n в данных обозначениях называется длиной пути.

ОПРЕДЕЛЕНИЕ 48 (Цепь в графе). Цепью [25] называется путь, в котором нет повторяющихся ребер.

ОПРЕДЕЛЕНИЕ 49 (Простая цепь в графе). Простой цепью [25] называется путь без повторения вершин.

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

ОПРЕДЕЛЕНИЕ 51 (Ветвь циркуляра). Ветвь циркуляра — объединение всех кругов циркулярного представления, центры которых лежат на некоторой ветви скелета.

2.3.2. Подциркуляр.

ОПРЕДЕЛЕНИЕ 52 (Подциркуляр). Рассмотрим циркуляр c1. Назовем циркуляр c2 подциркуляром циркуляра c1 (обозначение: c2 c1 ) или вложенным в циркуляр c1, если осевой граф c2 — подграф c1 (т.е. mg(c2 ) mg(c1 )) и все круги с центрами на осевом графе mg(c2 ) совпадают с кругами, принадлежащими c1 :

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

(1) Подциркуляр и его осевой граф являются связными множествами.

(2) Силуэт подциркуляра c2 c1 лежит внутри силуэта циркуляра c1 :

2.3.3. Максимальный простой подциркуляр и циркуляр уникальной проекции.

ОПРЕДЕЛЕНИЕ 53 (Максимальный простой подциркуляр). Рассмотрим осевой граф mg(c) циркуляра c. В нем имеется простая цепь максимальной длины mg(c ), являющаяся его подграфом: mg(c ) mg(c). Соответствующий подциркуляр c назовем максимальным простым подцикруляром циркуляра c.

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

ОПРЕДЕЛЕНИЕ 54 (Циркуляр уникальной проекции). Циркуляр c называется циркуляром уникальной проекции, если его максимальный простой подциркуляр c c единственный.

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

ЛЕММА 2. Максимальный простой подциркуляр циркуляра уникальной проекции принадлежит множеству всех плоских циркуляров уникальной проекции: c c.

ДОКАЗАТЕЛЬСТВО. Данное утверждение следует из того, что цепь максимальной длины циркуляра уникальной проекции c совпадает с цепью максимальной длины c. А так как она единственна, значит, у c единственный максимальный простой подциркуляр совпадает с ним самим: (c ) c. Таким образом, по определению c — тоже циркуляр уникальной проекции.

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

ТЕОРЕМА 3. Оператор Pr1 (c) = c на множестве циркуляров уникальной проекции, который ставит циркуляру c в соответствие его максимальный простой подциркуляр c, — оператор проектирования на множестве циркуляров.

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

(2) Pr1 (0) = 0.

(3) Pr1 (c) = Pr1 (Pr1 (c)), так как максимальный простой подциркуляр максимального простого подциркуляра тождественно равен себе.

ОПРЕДЕЛЕНИЕ 55 (Проектор максимальной длины). Назовем максимальный простой подциркуляр проекцией максимальной длины, а оператор Pr1 (c) — проектором максимальной длины.

На рисунке 2.1 пример проекций максимальной длины для фигур мыши и осла.

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

ЛЕММА 3. Модельным множеством проектора Pr1 являются все циркуляры из множества циркуляров уникальной проекции, осевые графы которых имеют вид простой цепи.

ДОКАЗАТЕЛЬСТВО.

(2) Рассмотрим произвольный циркуляр из множества уникальной проекции c, не являющийся простой цепью: c 1. Его проекцией будет циркуляр, имеющий вид простой цепи Pr1 (c ) = c. Но c = c.

2.4. Морфологический анализ циркуляров: критериальные морфологии Рассмотрим критериальные морфологии на множествах циркуляров и пар циркуляров в терминологии [6], [7].

ОПРЕДЕЛЕНИЕ 56 (Задача построения критериального морфологического фильтра).

Пусть задана целевая функция-критерий (A, B) : R +. Задача построения критериального морфологического фильтра [7] заключается в поиске проекции, доставляющей минимальное значение функции-критерию (A, B) на множестве :

• A — проецируемый образ;

• B — проекция;

• (A, ) — функция-проектор, зависящая от проецируемого образа и параметра: функции-критерия.

ОПРЕДЕЛЕНИЕ 57 (Множество допустимых проекций). Множеством допустимых проекций функции при проецировании исходного образа A [7] назовем множество всех проекций, на которых функция-критерий (A, B) принимает конечное значение. Обозначим:

ОПРЕДЕЛЕНИЕ 58 (Функция соответствия проекции и проецируемого образа).

J(A, B) : R — функция соответствия проекции и проецируемого образа (matching function) — это функция, отображающая пару проекции и образа в неотрицательное значение, обладающая следующим свойством:

ОПРЕДЕЛЕНИЕ 59 (Функция допустимости решения). (A, B) — функция (предикат) допустимости решения (validation function), определяющая множество допустимых проекций, вида ОПРЕДЕЛЕНИЕ 60 (Функция устойчивости проекции). Q : R функция устойчивости проекции (projection quality function) — это функция, отображающая проекцию в неотрицательное значение, характеризующее ее устойчивость.

Чем меньше значение Q(B), тем устойчивее проекция B.

ОПРЕДЕЛЕНИЕ 61 (Стандартная функция штрафа). Стандартная функция штрафа проекции B [7] имеет вид суммы трех функций: соответствия, допустимости решения и устойчивости проекции:

0 — структурирующий параметр, обеспечивающий компромисс между функциями соответствия и устойчивости.

ОПРЕДЕЛЕНИЕ 62 (Проектор на базе структурирующих критериев и параметров). Назовем морфологический проектор проектором на базе структурирующих критериев и параметров [7]:

так как зависит от вида функций Q : R, J(A, B) : R, (A, B), (A, B) и параметра.

(A, B, J,,, Q) — обозначение функции-критерия (A, B) и ее зависимости от вида функций J,, Q и параметра.

Pr(A, J,,, Q) — обозначение проектора Pr(A) и его зависимости от вида функций J,, Q и параметра.

ОПРЕДЕЛЕНИЕ 63 (Хорошо определенная функция штрафа). Функция штрафа (2.10) хорошо определена, если требования соответствия и устойчивости оказываются противоположными: из неравенства ”функция соответствия на проекции B1 меньше или равна функции соответствия на проекции B2 ” следует обратное неравенство для функции устойчивости: Q(B1 ) Q(B2 ), а из неравенства ”функция устойчивости на проекции B1 больше или равна функции устойчивости на проекции B2 ” следует обратное неравенство для функции соответствия:

J(A, B1 ) J(A, B2 ).

ОПРЕДЕЛЕНИЕ 64 (Функция минимального расстояния). Пусть функция соответствия обладает свойствами расстояния: A, B,C : J(A, B) 0; J(A, A) = 0;

J(A, B) = J(B, A); J(A, B) + J(A,C) J(B,C) Назовем такую функцию соответствия функцией минимального расстояния (в соответствии с терминологией в [7]).

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

2.4.2. Циркулярная функция штрафа. Рассмотрим целевую функциюкритерий : R на множестве всех циркуляров. Множеством ее допустимых проекций будет V (c, ) = {c : (c, c ) < +}.

ОПРЕДЕЛЕНИЕ 65 (Циркулярная функция штрафа). Определим целевую функциюкритерий : R как стандартную функцию штрафа (2.10) и обозначим следующим образом:

Где c — циркуляр-проецируемый образ, а c — циркуляр-проекция.

Назовем ее циркулярной функцией штрафа.

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

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

Этот метод будем использовать в данной работе.

2.5.1. Стрижка терминального ребра и ветви циркуляра.

ОПРЕДЕЛЕНИЕ 66 (Стрижка терминального ребра циркуляра). Пусть дан циркуляр c и соответствующий осевой граф T1 = mg(c1 ), имеющий терминальное ребро e T1. Операция стрижки терминального ребра e T1 циркуляра c1 заключается в удалении из осевого графа T1 = mg(c1 ) ребра e, а из циркуляра c1 — Рис. 2.2. Стрижка терминального ребра скелета и изменение силуэта.

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

Аналогично можно делать стрижку ветви циркуляра.

ОПРЕДЕЛЕНИЕ 67 (Стрижка терминальной ветви циркуляра). Пусть дан циркуляр c и соответствующий осевой граф T1 = mg(c1 ), имеющий терминальную ветвь e T1. Операция стрижки терминальной ветви e T1 циркуляра c1 заключается в удалении из осевого графа T1 = mg(c1 ) ветви e, а из циркуляра c1 — в удалении всех кругов, центры которых лежат на ветви e.

В работе [15] понятие ”базового скелета” переформулировано в конструктивное определение: базовым скелетом S фигуры F с контролируемой точностью называется минимальный укороченный подграф скелета S такой, что расстояние Хаусдорфа между фигурой и силуэтом подграфа S не превосходит : DH (F, Sil(S )).

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

ОПРЕДЕЛЕНИЕ 68 (Базовый подциркуляр c контролируемой точностью 0). Базовым подциркуляром с точностью, равной нулю, является сам циркуляр: c(=0) c.

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

Иными словами выполнены четыре условия:

c c подциркуляр D (c, c() ) расстояние не превосходит c c : c=c, DH (c, c) c c подциркуляр c минимальный < c() c(1 ) вложен во все базовые подциркуляры с меньшей точностью Стоит отметить, что для каждого фиксированного циркуляра c существует верхний порог точности max (c ) такой, что для любых точностей, превосходящих данный порог, базового подциркуляра не существует. Подциркуляром с точностью max (c ) будет являться круг с центром в одной из вершин осевого графа циркуляра c, то есть вырожденный циркуляр. В этом случае базовый подциркуляр может быть определен неоднозначно: может возникнуть случай, когда вырожденным базовым подциркуляром может являться круг с центром в любой из двух вершин осевого графа циркуляра c. А для точности меньше max (c ) базовый подциркуляр будет содержать как минимум одно ребро осевого графа. Таким образом, имеет смысл рассматривать точность в пределах:

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

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

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

Term(c0 ) — обозначим множество терминальных ребер циркуляра c0.

(2) Из множества терминальных ребер циркуляра c0 выберем терминальное ребро e0 такое, что его удаление из графа c0 вместе с соответствующими кругами наименьшим образом влияет на силуэт циркуляра Sil(c), то Если таких ребер несколько, то выберем их все и обозначим {e0 }.

Стрижка с контролируемой точностью, равной 1, дает циркуляр с (3) Далее выберем терминальное ребро e1 Term(c1 ) такое, что его удаление из графа c1 вместе с соответствующими кругами наименьшим образом влияет на силуэт циркуляра Sil(c), то есть Если таких ребер несколько, то выберем их все и обозначим {e1 }.

(n) И так продолжим до получения следующей цепочки вложенных подциркуляров:

Им соответствуют точности:

Обозначим упорядоченное множество вложенных осевых подциркуляров c:

ОПРЕДЕЛЕНИЕ 69 (Монотонное подмножество циркуляра c). Множество c (2.17) назовем монотонным подмножеством циркуляра c.

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

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

2.5.3. Циркуляры общего положения. Рассмотрим упрощенный случай, когда всем точностям из цепочки = {0, · · ·, n } (2.18) соответствует ровно по одному отрезанному терминальной ребру. То есть ОПРЕДЕЛЕНИЕ 70 (Уникальность терминальной стрижки). Будем называть описанное условие (2.19) — уникальность терминальной стрижки.

ОПРЕДЕЛЕНИЕ 71 (Циркуляр общего положения). Будем называть циркуляром общего положения циркуляр, для которого выполнено условие (2.19) — уникальность терминальной стрижки, а сам процесс построения цепочки (2.19) по алгоритму выше — процессом терминальной стрижки.

ОПРЕДЕЛЕНИЕ 72 (Множество циркуляров общего положения). Обозначим — множество всех циркуляров общего положения на плоскости.

ЛЕММА 4. Для любого циркуляра общего положения: c cуществует такой номер j > 0, что в его цепочке подциркуляров (2.17), полученных в процессе терминальной стрижки, осевой граф циркуляра cn j является простой цепочкой, а сам циркуляр cn j принадлежит модельному множеству проектора Pr1.

ДОКАЗАТЕЛЬСТВО. Покажем, что таким циркуляром является cn1 или цепочка, в которую циркуляр cn1 входит. Покажем, что для j = 1 лемма верна.

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

В силу леммы 4 можно найти максимальный такой номер j > 0, что cn j является простой цепочкой.

ОПРЕДЕЛЕНИЕ 73 (Максимальный стриженный подциркуляр). Максимальный стриженный подциркуляр — циркуляр, полученный в результате алгоритма, описанного в 2.5.2, осевой граф которого представляет собой максимальную простую цепочку.

ОПРЕДЕЛЕНИЕ 74 (Оператор проектирования на максимальный стриженный подциркуляр). Назовем оператором проектирования циркуляра c на максимальный стриженный подциркуляр оператор, ставящий в соответствие циркуляру c его максимальный стриженный подциркуляр. Обозначим такой оператор Pr2 (c).

Pr2 : ; Pr2 (c) = cn j, j = max {i : cni c простая цепочка} (2.20) Операторы проекции Pr1 и Pr2 можно использовать для генерации признаков формы. Для фиксированного циркуляра c проекции Pr1 (c) и Pr2 (c) являются признаками, описывающими циркуляр c.

2.6. Базовый циркуляр с контролируемой точностью 2.6.1. Рекурсивное определение базового циркуляра с контролируемой точностью.

ОПРЕДЕЛЕНИЕ 75. Базовый циркуляр c точностью для циркуляра общего положения c — это максимальный циркуляр cB, находящийся между ”соседними” базовыми подциркулярами или совпадающий с одним из базовых подциркуляров, такой, что расстояние Хаусдорфа между ним и циркуляром c в точности равно :

< i+1 ; i, i+1 — величина находится между точностями из монотонной цепочки (2.18);

c = c, c c — циркуляр ci из монотонной цепочки (2.17) изоморфен базовому циркуляру c() ;

c \c = ei или ci = c() — разницу между циркуляром ci из монотонной цепочки и базовым циркуляром cB составляет кусок одного ребра или же они совпадают;

D (c, c() ) = — расстояние Хаусдорфа между базовым циркуляром c() и исходным циркуляром c в точности равно ;

t mg(c() ) : Ct ci Ct c() — все круги с центрами на осевом графе mg(c() ) принадлежат базовому циркуляру c().

Таким образом, базовый подциркуляр с точностью > 0 и базовый циркуляр с точностью > 0 соотносятся следующим образом:

(1) они совпадают, если точность > 0 находится в монотонном множестве (2) они почти полностью совпадают, если, с точностью до одного терминального ребра, которое у последнего укорочено, а так же с точностью до соответствующих ”отстриженных” кругов, центры которых лежат на ”отстриженной” части терминального ребра.

ОПРЕДЕЛЕНИЕ 76. Функция базового циркуляра с контролируемой точностью > 0, которая циркуляру общего положения c ставит в соответствие базовый циркуляр cB с точностью :

Таким образом, можно рассматривать функцию базового циркуляра B(c, ) с контролируемой точностью как параметрическую функцию на множестве монотонных подциркуляров S (c ). Фиксируем циркуляр общего положения и рассмотрим функцию от переменной-параметра > 0. Похожая функция рассмотрена в работе К.Жуковой и И.Рейера [11]. Там показано, что базовый скелет фигуры непрерывно зависит от точности аппроксимации > 0 в смысле расстояния Хаусдорфа между исходной фигурой и ее силуэтом базового скелета с точностью > 0.

Пусть c — базовое подмножество циркуляра c. Рассмотрим соответствующее множество значений точности (2.16).

ОПРЕДЕЛЕНИЕ 77. Базовое множество циркуляра c — множество всех базовых циркуляров циркуляра c с точностями из отрезка [0, n ].

Pages: |

| 2 |

Главная >> Диссертации - все темы

[ СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА .pdf ]

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

«Кинев Николай Вадимович Генерация и прием ТГц излучения с использованием сверхпроводниковых интегральных устройств (01.04.03 – Радиофизика) Диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель : д.ф.-м.н., проф. Кошелец В.П. Москва – 2012 Оглавление Список используемых сокращений и...»

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

«из ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Сергеева, Галина Георгиевна 1. Прецедентные имена и понимание ик в молодежной среде 1.1. Российская государственная Библиотека diss.rsl.ru 2005 Сергеева, Галина Георгиевна Прецедентные имена и понимание ик в молодежной среде [Электронный ресурс]: Школьники 10-11 класса : Дис.. канд. филол. наук : 10.02.19.-М.: РГБ, 2005 (Из фондов Российской Государственной Библиотеки) Теория языка Полный текст: http://diss.rsl.ru/diss/05/0377/050377020.pdf...»

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

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

«Сучков Евгений Александрович МЕТОД КОЛИЧЕСТВЕННОГО ОПРЕДЕЛЕНИЯ В БИОЛОГИЧЕСКОМ МАТЕРИАЛЕ И ФАРМАКОКИНЕТИЧЕСКИЕ СВОЙСТВА НОВОГО ПРОИЗВОДНОГО АДЕНИНА, ОБЛАДАЮЩЕГО ПРОТИВОВИРУСНОЙ АКТИВНОСТЬЮ 14.03.06 – фармакология, клиническая фармакология 14.04.02 – фармацевтическая химия, фармакогнозия Диссертация на соискание ученой степени кандидата биологических наук Научный...»

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

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

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

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

«ШЕЛЕПИНА НАТАЛЬЯ ВЛАДИМИРОВНА НАУЧНО-ПРАКТИЧЕСКОЕ ОБОСНОВАНИЕ ЭФФЕКТИВНЫХ СПОСОБОВ ПЕРЕРАБОТКИ ЗЕРНА СОВРЕМЕННЫХ СОРТОВ И ФОРМ ГОРОХА Специальность 05.18.01 – Технология обработки, хранения и переработки злаковых, бобовых культур, крупяных продуктов, плодоовощной продукции и виноградарства Диссертация на соискание ученой степени...»

«УДК 530.145 51-71 512.54 Алексеев Олег Вадимович Физические состояния в некоторых точно решаемых моделях двумерной квантовой теории поля Специальность 01.04.02 Теоретическая физика Диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель : доктор физико-математических наук Белавин Александр Абрамович Черноголовка 2012 Оглавление...»

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

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

«из ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Пятков, Владимир Викторович 1. Формирование мотивационно-ценностного отношения студентов к физической культуре (На материале педвузов) 1.1. Российская государственная библиотека diss.rsl.ru 2002 Пятков, Владимир Викторович Формирование мотивационно-ценностного отношения студентов к физической культуре (На материале педвузов) [Электронный ресурс]: Дис.. канд. пед. наук : 13.00.04 - М.: РГБ, 2002 (Из фондов Российской Государственной Библиотеки)...»

«ОСИПОВА ТАТЬЯНА ВЯЧЕСЛАВОВНА Погребения с разрушенными костяками в средневековых могильниках Окско-Сурского междуречья Исторические наук и 07.00.06 – археология Диссертация на соискание ученой степени кандидата исторических наук Научный руководитель : доктор исторических наук, профессор...»

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

«БОГОПОЛЬСКИЙ Павел Майорович ИСТОРИЯ РЕКОНСТРУКТИВНОЙ ХИРУРГИИ ПИЩЕВОДА В РОССИИ Диссертация на соискание ученой степени доктора медицинских наук 07.00.10 – История науки и техники (медицинские науки) Научные консультанты: д.м.н. С.А. Кабанова д.м.н. проф. М.М. Абакумов Москва – 2014 г. ОГЛАВЛЕНИЕ Страницы Введение 5– Глава I. Исследования по истории развития...»

«Бутенко Светлана Викторовна ВВЕДЕНИЕ ПОТРЕБИТЕЛЯ В ЗАБЛУЖДЕНИЕ КАК АБСОЛЮТНОЕ ОСНОВАНИЕ ДЛЯ ОТКАЗА В ПРЕДОСТАВЛЕНИИ ПРАВОВОЙ ОХРАНЫ ТОВАРНОМУ ЗНАКУ 12.00.03 – гражданское право; предпринимательское право; семейное право; международное частное право ДИССЕРТАЦИЯ на соискание ученой степени кандидата юридических...»

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

наверх

<< ГЛАВНАЯ | КОНТАКТЫ

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