Скелетная сегментация и циркулярная морфология многоугольников тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. Ломоносова

На правах рукописи УДК 519.72,519.68

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

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

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

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

1 1 ОКТ 2012

Москва 2012 г.

005053054

005053054

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

Научный руководитель:

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

доктор технических наук, профессор, зав. кафедры информатики и математики Международного унивеситета в Москве Местецкий Леонид Моисеевич

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

Визильтер Юрий Валентинович

к.ф.-м.н., старший преподаватель кафедры математической физики ВМиК МГУ Мизотин Максим Михайлович

Санкт-Петербургский Академический Университет — научно-образовательный центр нанотехнологий РАН (Академический Университет)

Защита состоится «28» сентября 2012 г. в 11 часов на заседании диссертационного совета Д501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991 ГСП-1 Москва, Ленинские горы, МГУ имени М.В.Ломоносова, 2-й учебный корпус, факультет ВМК. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в фундаментальной библиотеке Московского государственного университета имени М.В. Ломоносова

Ведущая организация:

Автореферат разослан августа 2012

Председатель диссертационного совета

Ъы , к^ихф. Ь,<М ^

чл.-корр. РАН, профессор Королев Л.Н.

Общая характеристика работы

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

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

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

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

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

'Blum H. A transformation tor extracting new descriptors of shape. !n W. Wathen-Dunn, editor, Models for the Perception of Speech and Visual Form. MIT Press, 1967.pp. 362-380.

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

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

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

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

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

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

2Местецкий Л. М. Непрерывная морфология бинарных изображений. Фигуры. Скелеты. Циркуляры Москва, ФИЗМАТЛИТ, 2009

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

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

Структура предлагаемого метода решения

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

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

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

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

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

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

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

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

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

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

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

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

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

5

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

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

3. Критерий качества скелетной сегментации пары фигур.

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

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

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

Научная новизна

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

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

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

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

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

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

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

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

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

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

Внедрение результатов

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

Представленные в работе результаты частично вошли в книгу "Обработка и анализ изображений в задачах машинного зрения. Курс лекций и практический занятий" (Физматкнига, 2011), рекомендованную в качестве учебного пособия в технических ВУЗах.

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

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

Апробация

Представленные в работе результаты докладывались и обсуждались на

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.

Содержание работы

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

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

Определение 1. Скелетом ma(F) 3 фигуры F называется множество центров всех ее максимальных пустых кругов.

Определение 2. Под сегментацией скелета будем понимать процесс его конечного разбиения — получение декомпозиции скелета.

Зта от англ. medial axes

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

Определение 4. Скелетный граф фигуры — геометрический граф с множеством вершин и ребер скелета фигуры.

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

Определение 5. Однореберный скелетный оператор та0 : F -> Бк0 по фигуре строит максимальную евклидову цепь подграфа ее скелета.

Теорема 1. Однореберный скелетный оператор таР : F —> вк0 устойчив на паре метрических пространств (Ф,Л) с расстояниями рф(.,.) — расстояние Хаусдорфа и р\{-,-) — топологическое скелетное расстояние (разность числа ребер скелетных графов).

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

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

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

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

*Местецкий Л. М. Непрерывная морфология бинарных изображений. Фигуры. Скелеты. Циркуляры. Москва, ФИЗМАТЛИТ 2009 г.

Рис. 2: Пример: максимальные простые подциркуляры. Определение 7. Срединный циркуляр ста(Р) фигуры Р — это такой циркуляр, что

« его осевой граф совпадает со скелетом фигуры F;

• его множество кругов совпадает со множеством максимальных вписанных пустых кругов фигуры Р.

Лемма 1. Любой плоской фигуре Р соответствует единственный срединный циркуляр.

Таким образом, задача сегментации многоугольника сводится к задаче сегментации циркуляра.

Определение 8. Назовем С2 € & подциркуляром циркуляра с1 или вложенным в циркуляр си если осевой граф сг вложен в осевой граф с\ и все круги, соответствующие принадлежат и сх:

Определение 9. Подциркуляр, осевой граф которого представляет собой простую цепь максимальной длины т<?(с'), назовем максимальным простым подцикруляром (рис. 2): с! С с .

Определение 10. Циркуляр с £ © называется циркуляром уникальной проекции, если его максимальный простой подциркуляр с! С. с единственный. 0 — множество всех циркуляров уникальной проекции на плоскости.

Лемма 2. Максимальный простой подциркуляр циркуляра уникальной проекции также принадлежит множеству всех плоских, циркуляров уникальной проекции: с е © =ф- с! е ©.

Определение и. Монотонное подмножество циркуляра ©5(с*) уникальной проекции с* е © — это все подциркуляры из множества всех циркуляров 0, подциркуляром которых является также максимальный простой подциркуляр циркуляра с: ©3(с*) = {с' С с С с*}

(1)

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

Теорема 2. Оператор Рг\(с) = с! на множестве циркуляров уникальной проекции в, который ставит циркуляру с € О в соответствие его максимальный простой подциркуляр с! € В является оператором проекции на множестве циркуляров.

Доказательство. Идея доказательства в том, что осевой граф максимального простого подциркуляра является простой цепью, поэтому Рг\(с!) — ё. □

Определение 12 (Расстояние между парой циркуляров). Расстоянием между циркулярами с\ € 0 и С2 € в назовем величину, равную расстоянию Хаусдорфа между их силуэтами:

Определение 13. Назовем оператор Рг\{с) максимальным единичным проектором, а максимальный простой подциркуляр — максимальной единичной проекцией.

Определение 14. Циркулярная функция штрафа — это функция на множестве пар циркуляров Ф : 0 х в -» Я следующего вида:

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

Определение 15. Циркулярная функция соответствия Зс(с,с!) равна расстоянию Хаусдорфа между циркуляром-проецируемым образом и циркуляром-проекцией для всех проекций, являющихся подциркулярами проецируемого образа.

Определение 16. Множеством допустимых проекций7 функции Ф назовем множество всех проекций, на которых функция Ф(А, В) принимает конечное значение: У(Л, Ф) = {В : Ф(Л, В) < +оо }

ьВизильтер Ю.В., Желтое С.Ю., Бондаренко A.B., Ососков М.В., Моржин A.B. Обработка и анализ изображений в задачах машинного зрения. Курс лекций и практических занятий.- М: Физматкнига, с. 384389, 2010.

7Визильтер Ю.В. Обобщенная проективная морфология. Компьютерная Оптика, Институт систем обработки изображений РАН, том 32, номер выпуска 4, с. 384-399, 2008.

£>h(ci,c2) = Dn(Sil(cj),Sil(c2))

(2)

Фс(с, d) = Jc(c, с') + хс(с, с') + аcQc(c')

(3)

(4)

Лемма 3. При определении функции соответствия 7с(с, с!) через расстояние Хаусдорфа (4), множеством допустимых проекций У(с, Фс) функции Фс будут только подциркуляры циркуляра с.

Определение 17. Базовый подциркуляр циркуляра с* с точностью а — это минимальный подциркуляр ¿а) циркуляра с* такой, что расстояние Хаусдорфа между циркуляром и подциркуляром не превосходит а.

'¿^ С с*

• £>я(с*,с<а>) <а (5)

ус С с* : £>н(с*, с)<а=¥ ¿а) С с

Алгоритм построения монотонных цепочек циркуляров на основе стрижки

Базовые подциркуляры можно получать при последовательной стрижке терминальных ветвей циркуляра. Таким образом, для циркуляра с можно построить монотонные вложенные цепочки подциркуляров. Первый подциркуляр совпадает с циркуляром с: с0 = с. Далее от него на каждом шаге "отстригается" такая терминальная ветвь, что ее удаление наименьшим образом влияет на силуэт циркуляра БЩс). Если на каком-то шаге таких ветвей несколько, то они отстригаются все.

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

с = {с0, • • • , с"}; ё = {е°, • • • , е"} (6)

Рассматривается случай, когда всем точностям из цепочки ё = •••,£"} (6) соответствует ровно по одной "отстриженной" терминальной ветви. То есть V* = 1, • • • ,п =Ф- {е<} ее е\ Описанное условие называется уникальностью терминальной стрижки.

Определение 18. Циркуляр общего положения — это циркуляр, для которого выполнено условие уникальности терминальной стрижки.

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

Лемма 4. При фиксированном циркуляре с функция соответствия 0С(с, с!) как функция от одной переменной с! е У(с, Фс) является строго монотонной на упорядоченном множестве с* € с = {с0, • • • , с"}.

Определение 19. Базовый циркуляр с точностью а для циркуляра общего положения с* — это максимальный циркуляр ¿а*\ находящийся между "соседними" базовыми подциркулярами такой, что расстояние Хаусдорфа между ним и циркуляром с* в точности равно а:

V < а < е'+1 с< йс!»*);^1"'1 =е" « сМ с с"; с?\с<+1 = е{\ е" С е' (7)

£>я(с*, с^) = а V* 6 тд(с^) ^ЕсЧ^е

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

Определение 20. Функция базового циркуляра с контролируемой точностью а > 0, которая циркуляру с ставит в соответствие базовый циркуляр с^ с точностью а:

В(с,а):(с,а0^сИ (8)

Теорема 3. Функция В(с,а) базового циркуляра (8) непрерывна по точности аппроксимации а на множестве а е [О, Я+) с расстоянием Хаусдорфа на множестве образов 05(с*).

Доказательство. Идея доказательства: по определению непрерывности функции в точке. □

Определение 21. Рассмотрим функцию соответствия 3С(с,</). Фиксируем циркуляр с. Зс(с, с1) : 9 й. Назовем функцию 3~1{с, с!) — обратной функцией соответствия: 7с_1(с,е) : Я 6, если для любого циркуляра из монотонного множества циркуляров ё £ с = {с0,-- - ,сп} верно следующее: 3е(с, с!) = £ 3~1{с,е) = с!.

Лемма 5. Обратная функция соответствия с*) существует на монотонном множестве (6): ё е с = {с0, • • • , с"}.

Лемма 6. Функция соответствия Зс(с,с!) является обратной к функции базового скелета с контролируемой точностью В(с,а) на множестве допустимых проекций У (с, Фс): 3~1(с, а) = В(с,а) для всех а > 0 и Зс(с, с!) = В~х{с,ё) для всех с! е У(с,Фс).

13

Лемма 7. Функция соответствия Jc(c, d) непрерывна по переменной d на множестве допустимых проекций V{c, Фс).

Определение 22. Функция устойчивости — это расстояние Хаусдорфа между циркуляром- проекцией d и максимальной единичной проекцией Frj(c'):

Qc(d) = DH(d,Prl(d)) (9)

Лемма 8. Функция штрафа Фс (3) эквивалентна следующей функции (упрощенная функция штрафа): Фс(с, d) = Jc{c, d) + acQc{d).

Теорема 4. Функция штрафа Фс (3) хорошо определена8, то есть требования соответствия и устойчивости противоположны. Чем ближе проекция к максимальной единичной, тем она устойчивее, но дальше от исходной. И наоборот.

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

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

Ф(с, Ф) = агдттФс(с, с')

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

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

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

6Визилътер Ю.В. Обобщенная проективная морфология. Компьютерная Оптика, Институт систем обработки изображений РАН, том 32, номер выпуска 4, с. 384-399, 2008.

Определение 24. Два циркуляра ci и c-i изоморфны, если изоморфны их осевые графы: тд{с\) = mg(c2).

б2 = {(cj, сг) : с\ G 0,С2 € 6} — множество всех пар циркуляров на плоскости.

0(с1,сг) = {с^ С ci,4 Q ¿2 '■ 4 — 4) — множество всех пар изоморфных подциркуляров (с1,сг) на плоскости.

0(ci,c2) = {ci С С с2 : ci = 4} — множество пар всех базовых циркуляров общего положения (ci, са) на плоскости.

Определение 25. Функция устойчивости для пар циркуляров — это индикатор их изоморфизма:

<?2(с1,С2) = < (10)

[+00,7715(4) £mfl(4)

Определение 26. Функция соответствия для пары циркуляров с\ и с2 имеет вид:

•/2(ci,4,c2,4) =max{Jc(ci,ci), JC(C2,4)} (Ш

Определение 27. Функция штрафа для пары циркуляров ci и с2 имеет вид:

Фг(с1,с2,4) = -^(ci, ci, 02,4) + <?2(ci, 4) (12)

Определение 28. Морфологический проектор с априорным условием изоморфизма выглядит следующим образом:

^2(ci,c2,ci,4) = Pr(ci,c2,J2,Q2) — arg min <$2(ci,4,c2,4,./2,Q2) (13)

Определение 29. Проекция пары циркуляров (ei,c2) — это пара (ci,4)> Д°" ставляющая минимум функции штрафа Ф2(с1,4>с2,4, ■•'г,^)-

Задача 1. Для любой пары циркуляров из множества (ci,c2) 6 в(сх,с2) найти проекцию (4,4) = -Рф1,с2, <5г) (13).

Для решения поставленной задачи доказан ряд утверждений.

Теорема 5. Множество допустимых проекций функции (12) Фг(сь4,с2>4) — 9то множество всех изоморфных подциркуляров с\ и с2.

Теорема 6. Множество V(ci,c2,Ф2) = ö(ci,c2) ограничено в метрическом пространстве в2 с расстоянием Ph({ci,c2), (4,4)) = тах{Я(сьс2), #(4,4)}.

15

Доказательство. Идея доказательства: выбрать значением числа — максимальный из диаметров циркуляров с\ и с2. Показать, что для любой пары циркуляров (4,4) из множества \;{сис2) Ф2) - 6(сьс2), верно, что

Теорема 7. Функция 72(с1,4,с2,4) соответствия (11) непрерывна по переменным (4.4) на множестве допустимых проекций функции Фг(сь (4,4) е У(сьс2,Ф2) на метрическом пространстве

в(сьс2) с расстоянием ^Л(с'1,с'2) = тах{-0/7(сь 4), £>я(с2, 4)}-

Доказательство. Идея доказательства: по определению непрерывности функции в метрическом пространстве. □

Лемма 9. Функция устойчивости на основе априорной информации об изоморфизме <52(4,4) непрерывна на множестве допустимых проекций функции Ф2(съ4>с2>4)'

Лемма 10. Множество монотонных изоморфных подциркуляров пары циркуляров (с!,с2) на плоскости в(с!,с2) замкнуто относительно в2.

Теорема 8. Функция штрафа для пары циркуляров Ф2(с1,4>с2,4) (12) непрерывна на множестве допустимых проекций.

Доказательство. Это утверждение следует из непрерывности суммы двух непрерывных функций ./2(сь 4^2,4) и <32(4>4) от переменных (4,4) на множестве допустимых проекций. □

Теорема 9. Для каждой пары циркуляров существует проекция функции Ф03).

Доказательство. Идея доказательства: множество, в котором лежит проекция, сужается до подмножества ©(с!,с2), которое не пусто. В силу леммы 10 множество 6(със2) замкнуто относительно в2. Получается, что функция Ф2 непрерывна (теорема 8) на замкнутом ограниченном (теорема 6) множестве 6(с1,с2). Поэтому достигает на этом множестве своего минимального значения. П

Теорема 10. При условии уникальности терминальной стрижки, выполненном для каждого из циркуляров и с2, одно из решений задачи поиска проекции для пары циркуляров (1) лежит в монотонных упорядоченных множествах с1 и с2, то есть 3(4,4) е Ф2(сь с2,4,4) : 4 € с~ьс2 е с2.

Р, о —с\ —и С1 —Рг(С1)

11-1-1 ез ^ е®(с1,с2) -3-* ё(сьс2) е(Рг(с,),Рг(с2))

11-1-1 я««-"»(Я) с5 ¿2 Рг(с2)

Рис. 3: Схема преобразования циркулярного представления к проекциям, а-фигуры и их срединные циркуляры; Ь-подциркуляры; с-изоморфные подциркуляры; (1-проекции циркуляров;

Доказательство. Идея доказательства: пусть в монотонных множествах с\ и ¿2 выбрана пара изоморфных графов с\ е с\,сР2 £ ¿2 : 4 =4 с минимальными индексами г,^. Предположение о том, что пара (с\,сне оптимальная для функции Ф2(с1,с'1,с2,4) на множестве 0(с1,сг) приводит к противоречию. □

Теорема 11. Для пары циркуляров общего положения с\, сг решение задачи поиска проекции для пары циркуляров с\, с$ единственно.

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

Лемма 11. Для циркуляра общего положения количество ветвей циркуляров из цепочек с\ и с2 (6) равно: {п + 1,п, ■ • • , 1} и {т + 1,т, ■ ■ ■ , 1} соответственно. Где пит — количество циркуляров цепочек и ¿2 соответственно.

Предположим, без ограничения общности, что т <п, тогда #с1П_т'+1 = #Сз- Поэтому для любого значения г = 0, ...,т количество ветвей циркуляров из цепочки с соответствующими индексами тп — г и п — I одинаково, т.е. #с"~* = #С21-1. Решение задачи сводится к поиску минимального индекса при котором вложенный циркуляр первой цепочки изоморфен вложенному циркуляру второй. Проверку изоморфизма предлагается свести к поиску топологической эквивалентности диаграмм смежности соответствующих освевых графов циркуляров. Если существует их наложение, то циркуляры изоморфны. Вычислительная сложность алгоритма решения задачи поиска проекции квадратична по минимальному числу ребер одного из циркуляров с\ и с2.

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

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

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

Определение 30. Циркулярное расстояние с условием изоморфизма для пары фигур — это значение функции штрафа на паре проекций функции с априорным условием изоморфизма срединных циркуляров этих фигур:

= (14)

где (с{, с*2) = Ф^с™^),^^)^,^)

Теорема 12. Циркулярное расстояние удовлетворяет четырем аксиомам полуметрики: 1) = 0; 2) > 0; 3) Рс(Ръ^г) = 0 => ста{Р1) = ста(Р2), но необязательно = 4) + Ре(Р-г, Рз) > ^з) для любых Л, ^ Я

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

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

Рис. 4: Прямоугольники с уменьшающимся шумовым отростком.

12 34 567$ 9 10

Рис. 5: Последовательность ослы-зайцы.

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

Эксперимент 2: Монотонность расстояний при морфинге фигур. Рассматривается последовательность фигур животных, для которых происходит плавный морфинг одной фигуры в другую: "осел превращается в зайца" (рис. 5). Графики циркулярных расстояний от осла до остальных фигур рис. 6 (слева) и от зайца до остальных фигур рис. 6 (справа) показывают монотонность последовательности этих расстояний. Таким образом, предложенная мера сходства хорошо отделяет различные фигуры, даже имеющие незначительные структурные различия. Это преимущество достигается за счет метрической компоненты предложенной меры сходства.___

V 0.0009 0.00238 0.0077 4 0.00867 4 0.0381 0.2O9

\ 0.0012 > 0.017 4 0.023 :> 0,039' Г 0.0516 V 0.074-

■A 4 0.00048 V □ 001 0.0015 ^ 0.0439 :> 0.0048 4 0.00926

4 0.0004 > 0.0006 0.0019 V 0.003 4 0.009 0.10297

4 > 0.0002 > 0.0005 V 0.0105 A 0.01388 4 0.0139 0.1292

4 D.0176 4 0 07260 ^ 0.1338 0.1338 A 01397 V 0.1397

4 0.00005 > 0.0002 0 0017 V 0 0032 0.0836 4 0.0064

V Э» \ 4

0.088 O.081 0.108. одм 0492 0.187

\ :> A Э» 4 f V

0.053 0.0Я o.oey 0.08(1 0.087 0.112

О* Э" 4 4 V

o.aio aoje IttKH 0.084 0.092 0.108

Э» A 4 V 4

o.oil 0,030 0.054 0.081 0.O86 0.110

\ 4 > V

0 080 o:o84 O.OSO 0.095 o.ies 0.132

4 A 4 S' V

0.088 Ш fl.0% o.ira 0.128 0.186

p V 4 4 *

0.021 o;ims U,(KS 0.0M 0.102 0.128

Рис. 7: Слева: циркулярное расстояние (14). Справа: "Производная" скелетная мера сходства (Torsello, 2004).

Эксперимент 3: классификация инструментов.

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

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

9Torsello A. and Hancock Е. P. A Skeletal Measure of 2D Shape Similarity. Computer Vision and Image Understanding, vol. 95, no. 1, pp. 1-29, 2004.

ь Г^ г* Г^ !

•г гггг

^ 4 4 4 V V г^

^ГУ. V- V- V-^ ^ ф ф ^ ф ^ \

Рис. 8: База данных 181 плоская фигура.

рестановок для всех инструментов. В результате метод ТогееИо дает 34% перестановок до правильных последовательностей, а циркулярная мера сходства всего 20%, что показывает ее более высокое качество в сортировке инструментов.

Эксперимент 4: Задача распознавания на основе скелетной сегментации.

Заданы: 142 фигуры в виде бинарных изображений (рис. 8), содержащая объекты трех классов: мыши (69 объектов), руки (22 объекта) и птицы (51 объект).

Необходимо: решить задачу распознавания с набором прецедентов и контрольных объектов. Решение:

(1) Построение признакового пространства на множестве всех объектов.

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

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

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

4 V- X к

1 г* V- у X

2 V- У 1

3 г V- X V Т

4 г- % > < /

5 Ш Г / X * /

6 4 ¥ | 1 X

Рис. 9: 6 ближайших по циркулярному расстоянию (14) фигур из базы Эксперимент 5: Сравнение формы: эксперименты с запросами. Имеется база изображений, состоящая из 181 фигуры (рис. 8).

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

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

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

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

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

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

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

7. Домахина Л.Г., Охлопков А.Д. Изоморфные скелеты растровых изображений. Труды 18 межд. конференции ГРАФИКОН, 2008.

8. Домахина Л.Г. Устойчивость скелетной сегментации. Журнал Таврический вестник информатики и математики. Изд-во НАН Украины, №1, 2008.

9. 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, 2009.

10. L. Domakhina Skeleton-Based Shape Segmentation, The Proceedings of the Second International Workshop on Image Mining, Theory and Applications (IMTA 2009). Lisbon, Portugal, 2009.

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

12. Domakhina L.G. Skeleton-Based Segmentation and Decomposition of Raster Pairs of Shapes. Pattern Recognition and Image Analysis, №. 3, 2010, pp.293-316

13. 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.

14. Домахина Л.Г. Критериальные и проективные морфологии для множества плоских циркуляров. Журнал вычислительной математики и математической физики, №7, 2012.

Напечатано с готового оригинал-макета

Подписано в печать 28.08.2012 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 319.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 939-3890. Тел./факс 939-3891.