авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Людмила григорьевна скелетная сегментация и циркулярная морфология многоугольников

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

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

УДК 519.72,519.68 Домахина Людмила Григорьевна СКЕЛЕТНАЯ СЕГМЕНТАЦИЯ И ЦИРКУЛЯРНАЯ МОРФОЛОГИЯ МНОГОУГОЛЬНИКОВ 01.01.09 - Дискретная математика и математическая кибернетика.

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

Москва 2012 г.

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

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

Официальные оппоненты: д.ф.-м.н., с.н.с., начальник подразде ления 3000 Государственного научно исследовательского института авиацион ных систем Визильтер Юрий Валентинович к.ф.-м.н., старший преподаватель кафед ры математической физики ВМиК МГУ Мизотин Максим Михайлович

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

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

Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в фундаментальной библиотеке Московского государственного университета имени М.В. Ломоносова Автореферат разослан « » августа Председатель чл.-корр. РАН, профессор диссертационного совета Королев Л.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Подход к достижению указанных целей основан на понятии срединной оси фигуры. Понятие срединной оси плоской фигуры (или скелета) было впервые введено в конце 1960-х годов Blum1. Он показал, что медиальное Blum H. A transformation for extracting new descriptors of shape. In 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) Неопределенность понятия качество сегментации и необходимость формализации данного понятия. Критерий качества сегментации фигуры должен привноситься извне и формироваться исходя из дальнейшего ис пользования результатов. В частности, необходимо сформулировать крите Местецкий Л. М. Непрерывная морфология бинарных изображений. Фигуры. Скелеты. Циркуляры Москва, ФИЗМАТЛИТ, Рис. 1: Скелеты многоугольников.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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





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

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

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

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

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

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

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

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

08 01-00670 ”Методы анализа и распознавания формы изображений на основе непрерывных моделей”.

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

Структура диссертации Работа состоит из оглавления, введения, четырех глав, заключения и списка литературы. Содержание работы изложено на 147 страницах. Список литературы включает 75 наименований. Текст работы иллюстрируется рисунками и 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. Под сегментацией скелета будем понимать процесс его ко нечного разбиения — получение декомпозиции скелета.

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

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

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

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

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

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

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

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

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

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

Москва, ФИЗМАТЛИТ 2009 г.

Рис. 2: Пример: максимальные простые подциркуляры.

Определение 7. Срединный циркуляр cma (F ) фигуры F — это такой циркуляр, что • его осевой граф совпадает со скелетом фигуры F ;

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

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

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

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

{ mg(c2 ) mg(c1 ) c2 c1 (1) t mg(c2 ) : ct c2 ct c Определение 9. Подциркуляр, осевой граф которого представляет собой про стую цепь максимальной длины mg(c ), назовем максимальным простым подцикруляром (рис. 2): c c.

Определение 10. Циркуляр c называется циркуляром уникальной проек ции, если его максимальный простой подциркуляр c c единственный.

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

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

Определение 11. Монотонное подмножество циркуляра S (c ) уникальной проекции c — это все подциркуляры из множества всех циркуляров, подциркуляром которых является также максимальный простой подцирку ляр циркуляра c: S (c ) = {c c c } Функции, задающие полноту и устойчивость циркулярного представле ния, определены на базе математического аппарата критериальных и проек тивных морфологий Визильтера 6.

Теорема 2. Оператор P r1 (c) = c на множестве циркуляров уникальной проекции, который ставит циркуляру c в соответствие его мак симальный простой подциркуляр c является оператором проекции на множестве циркуляров.

Доказательство. Идея доказательства в том, что осевой граф максимально го простого подциркуляра является простой цепью, поэтому P r1 (c ) = c.

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

(2) DH (c1, c2 ) = DH (Sil(c1 ), Sil(c2 )) Определение 13. Назовем оператор P r1 (c) максимальным единичным проек тором, а максимальный простой подциркуляр — максимальной единичной проекцией.

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

c (c, c ) = Jc (c, c ) + c (c, c ) + c Qc (c ) (3) Где c — циркуляр-проецируемый образ, а c — циркуляр-проекция.

Определение 15. Циркулярная функция соответствия Jc (c, c ) равна рассто янию Хаусдорфа между циркуляром-проецируемым образом и циркуляром проекцией для всех проекций, являющихся подциркулярами проецируемого образа. { DH (c, c ), c c (4) Jc (c, c ) = +, c c Определение 16. Множеством допустимых проекций7 функции назовем множество всех проекций, на которых функция (A, B) принимает конечное значение: V (A, ) = {B : (A, B) + } Визильтер Ю.В., Желтов С.Ю., Бондаренко А.В., Ососков М.В., Моржин А.В. Обработка и анализ изображений в задачах машинного зрения. Курс лекций и практических занятий.- М: Физматкнига, с. 384 389, 2010.

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

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

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

c() c D (c, c() ) (5) H c c : DH (c, c) c() c Алгоритм построения монотонных цепочек циркуляров на основе стрижки Базовые подциркуляры можно получать при последовательной стрижке терминальных ветвей циркуляра. Таким образом, для циркуляра c можно построить монотонные вложенные цепочки подциркуляров. Первый подцир куляр совпадает с циркуляром c: c0 c. Далее от него на каждом шаге ”отстригается” такая терминальная ветвь, что ее удаление наименьшим об разом влияет на силуэт циркуляра Sil(c). Если на каком-то шаге таких ветвей несколько, то они отстригаются все.

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

c = {c0, · · ·, cn };

= {0, · · ·, n } (6) Рассматривается случай, когда всем точностям из цепочки = {0, · · ·, n } (6) соответствует ровно по одной ”отстриженной” тер минальной ветви. То есть i = 1, · · ·, n {ei } ei. Описанное условие называется уникальностью терминальной стрижки.

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

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

Лемма 4. При фиксированном циркуляре c функция соответствия Jc (c, c ) как функция от одной переменной c V (c, c ) является строго моно тонной на упорядоченном множестве c c = {c0, · · ·, cn }.

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

i i+ i () i () c = c ;

c \c = ei c() c ;

ci \ci+1 = ei ;

ei ei (7) DH (c, c() ) = t mg(c() ) : ct ci ct c() Таким образом, базовый подциркуляр и базовый циркуляр с точностью 0 соотносятся следующим образом: они почти полностью совпадают с точностью до одного терминального ребра, которое у последнего укорочено.

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

B(c, ) : (c, ) c() (8) Теорема 3. Функция B(c, ) базового циркуляра (8) непрерывна по точно сти аппроксимации на множестве [0, R+ ) с расстоянием Хаусдорфа на множестве образов S (c ).

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

Определение 21. Рассмотрим функцию соответствия Jc (c, c ). Фиксируем цир куляр c. Jc (c, c ) : R. Назовем функцию Jc (c, c ) — обратной функ цией соответствия: Jc (c, ) : R, если для любого циркуляра из монотонного множества циркуляров c c = {c0, · · ·, cn } верно следующее:

1 Jc (c, c ) = Jc (c, ) = c.

Лемма 5. Обратная функция соответствия Jc (c, c ) существует на мо нотонном множестве (6): c c = {c0, · · ·, cn }.

Лемма 6. Функция соответствия Jc (c, c ) является обратной к функ ции базового скелета с контролируемой точностью B(c, ) на множе стве допустимых проекций V (c, c ): Jc (c, ) = B(c, ) для всех 0 и Jc (c, c ) = B 1 (c, c ) для всех c V (c, c ).

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

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

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

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

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

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

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

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

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

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

Определение 24. Два циркуляра c1 и c2 изоморфны, если изоморфны их осе вые графы: mg(c1 ) mg(c2 ).

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

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

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

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

{ 0, mg(c1 ) mg(c2 ) = Q2 (c1, c2 ) (10) = +, mg(c1 ) mg(c2 ) Определение 26. Функция соответствия для пары циркуляров c1 и c2 имеет вид:

J2 (c1, c1, c2, c2 ) = max{Jc (c1, c1 ), Jc (c2, c2 )} (11) Определение 27. Функция штрафа для пары циркуляров c1 и c2 имеет вид:

2 (c1, c1, c2, c2 ) = J2 (c1, c1, c2, c2 ) + Q2 (c1, c2 ) (12) Определение 28. Морфологический проектор с априорным условием изомор физма выглядит следующим образом:

2 (c1, c2, c1, c2 ) = P r(c1, c2, J2, Q2 ) = arg min 2 2 (c1, c1, c2, c2, J2, Q2 ) (13) (c1,c2 ) Определение 29. Проекция пары циркуляров (c1, c2 ) — это пара (c, c ), до ставляющая минимум функции штрафа 2 (c1, c1, c2, c2, J2, Q2 ).

Задача 1. Для любой пары циркуляров из множества (c1, c2 ) (c1, c2 ) найти проекцию (c1, c2 ) = P r(c1, c2, J2, Q2 ) (13).

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

Теорема 5. Множество допустимых проекций функции (12) 2 (c1, c1, c2, c2 ) — это множество всех изоморфных подциркуляров c и c2.

Теорема 6. Множество ограни V (c1, c2, 2 ) = (c1, c2 ) чено в метрическом пространстве с расстоянием µH ((c1, c2 ), (c1, c2 )) = max{H(c1, c2 ), H(c1, c2 )}.

Доказательство. Идея доказательства: выбрать значением числа M1 — максимальный из диаметров циркуляров c1 и c2. Показать, что для любой пары циркуляров (c1, c2 ) из множества V (c1, c2, 2 ) = (c1, c2 ), верно, что µH ((x, y ), (c1, c2 )) M1.

Теорема 7. Функция J2 (c1, c1, c2, c2 ) соответствия (11) непрерывна по переменным (c1, c2 ) на множестве допустимых проекций функции 2 (c1, c1, c2, c2 ): (c1, c2 ) V (c1, c2, 2 ) на метрическом пространстве (c1, c2 ) с расстоянием µc1,c2 (c1, c2 ) = max{DH (c1, c1 ), DH (c2, c2 )}.

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

Лемма 9. Функция устойчивости на основе априорной информации об изоморфизме Q2 (c1, c2 ) непрерывна на множестве допустимых проекций функции 2 (c1, c1, c2, c2 ).

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

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

Доказательство. Это утверждение следует из непрерывности суммы двух непрерывных функций J2 (c1, c1, c2, c2 ) и Q2 (c1, c2 ) от переменных (c1, c2 ) на множестве допустимых проекций.

Теорема 9. Для каждой пары циркуляров существует проекция функции 2 (c1, c1, c2, c2 ) (13).

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

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

12 b c d c F1 cma (F1 ) c P r(c1 ) = = S (c1, c2 ) (c1, c2 ) (P r(c1 ), P r(c2 )) = = b c d c F2 cma (F2 ) c P r(c2 ) Рис. 3: Схема преобразования циркулярного представления к проекциям. a-фигуры и их срединные циркуляры;

b-подциркуляры;

с-изоморфные подциркуляры;

d-проекции циркуля ров;

Доказательство. Идея доказательства: пусть в монотонных множествах c1 i j j и c2 выбрана пара изоморфных графов c1 c1, c2 c2 : c1 = c2 с минималь i ными индексами i, j. Предположение о том, что пара (ci, cj ) не оптимальная 1, c2 ) приводит к противоре для функции 2 (c1, c1, c2, c2 ) на множестве (c чию.

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

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

Лемма 11. Для циркуляра общего положения количество ветвей цирку ляров из цепочек c1 и c2 (6) равно: {n + 1, n, · · ·, 1} и {m + 1, m, · · ·, 1} соответственно. Где n и m — количество циркуляров цепочек c1 и c2 соответственно.

Предположим, без ограничения общности, что m n, тогда (nm)+ #c1. Поэтому для любого значения i = 0,..., m количество #c1 ветвей циркуляров из цепочки с соответствующими индексами m i и n i одинаково, т.е. #cni #cmi. Решение задачи сводится к поиску 1 минимального индекса i, при котором вложенный циркуляр первой це почки изоморфен вложенному циркуляру второй. Проверку изоморфизма предлагается свести к поиску топологической эквивалентности диаграмм смежности соответствующих освевых графов циркуляров. Если существует их наложение, то циркуляры изоморфны. Вычислительная сложность ал горитма решения задачи поиска проекции квадратична по минимальному числу ребер одного из циркуляров c1 и c2.

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

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

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

c (F1, F2 ) = 2 (cma (F1 ), c, cma (F2 ), c ) (14) 1 где (c, c ) = 2 (cma (F2 ), cma (F2 ), 2, Q2 ) Теорема 12. Циркулярное расстояние удовлетворяет четырем ак сиомам полуметрики: 1) c (F, F ) = 0;

2) c (F1, F2 ) 0;

3) c (F1, F2 ) = 0 cma (F1 ) cma (F2 ), но необязательно F1 = F2 ;

4) = c (F1, F2 ) + c (F2, F3 ) c (F1, F3 ) для любых F1, F2, F3.

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

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

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

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

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

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

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

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

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

Необходимо для каждого инструмента отсортировать расстояния от него до остальных.

Для решения задачи рассчитываются все расстояния от каждого инстру мента до остальных. Получаются последовательности расстояний. Опреде ляются верные последовательности инструментов и последовательности на основе полученных расстояний. Рассчитывается количественная оценка ка чества работы методов с помощью перестановок до верно отсортированных последовательностей. Процент ошибки — это количество перестановок для каждого из инструментов, нормированное по максимальному количеству пе Torsello A. and Hancock E. R. A Skeletal Measure of 2D Shape Similarity. Computer Vision and Image Understanding, vol. 95, no. 1, pp. 1-29, 2004.

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

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

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

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

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

Решение:

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

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

Использование метода скользящего контроля.

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

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

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

Рис. 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.

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



 

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





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

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