Скелетная сегментация и циркулярная морфология многоугольников тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Домахина, Людмила Григорьевна
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2013
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. Ломоносова
На правах рукописи УДК 519.72,519.68
Домахина Людмила Григорьевна
СКЕЛЕТНАЯ СЕГМЕНТАЦИЯ И ЦИРКУЛЯРНАЯ МОРФОЛОГИЯ МНОГОУГОЛЬНИКОВ
01.01.09 - Дискретная математика и математическая кибернетика.
Автореферат диссертации на соискание степени кандидата физико-математических наук
Москва 2014 г.
005547545
Работа выполнена на кафедре математических методов прогнозирования факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова
Научный руководитель: доктор технических наук, профессор,
зав. кафедры информатики и математики Международного унивеситета в Москве Местецкий Леонид Моисеевич
Официальные оппоненты: д.ф.-м.н., с.н.с., начальник подразделения 3000 Государственного научно-исследовательского института авиационных систем
Визильтер Юрий Валентинович
к.ф.-м.н., доцент кафедры автоматики и телемеханики Тульского государственного университета Середин Олег Сергеевич
Ведущая организация: Федеральное государственное бюджетное
учреждение науки Институт системного анализа Российской академии наук
Защита состоится «16» мая 2014 г. в 11 часов на заседании диссертационного совета Д501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991 ГСП-1 Москва, Ленинские горы, МГУ имени М.В.Ломоносова, 2-й учебный корпус, факультет ВМК. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня по тел. 939-30-10 (для оформления заявки на пропуск).
С диссертацией можно ознакомиться в фундаментальной библиотеке Московского государственного университета имени М.В. Ломоносова
Автореферат разослан /ф апреля 2014
Председатель • профессор
диссертационного совета /^-¿^•■sz-jJ^ Васин A.A.
/ С
Общая характеристика работы
В диссертации рассматривается задача сегментации выделенных в изображении объектов для сравнения и классификации этих объектов по их форме. Обычно в основе классификации формы лежит сравнение тестируемого объекта с эталонными объектами, форма которых считается известной (например, сходство с геометрическими фигурами). Сегментация в этом случае имеет целью декомпозицию объекта сложной формы на составляющие его элементы, форма которых имеет более простой вид и, соответственно, допускает более простую классификацию.
В диссертации исследуются методы сегментации, основанные на медиальном представлении формы объектов. Медиальное представление объекта включает множество срединных осей объекта (называемое скелетом) и радиальную функцию, заданную в точках скелета. Такое представление широко используется в качестве информативного дескриптора, описывающего общую структуру объекта. Скелет плоской фигуры представляет собой множество центров максимальных вписанных в фигуру окружностей. Скелет фигуры имеет вид геометрического графа. Скелетная сегментация состоит в разбиении скелетного графа на составляющие части — подграфы, соответствующие отдельным структурным элементам формы объекта. Скелетная сегментация формы основывается на построении медиального представления формы и анализе полученного скелетного графа и радиальной функции.
В диссертации задача скелетной сегментации рассматривается лишь для многоугольных фигур. Представление формы объектов изображения многоугольными фигурами широко используется в компьютерной графике, обработке и анализе изображений. С одной стороны, многоугольными фигурами можно приблизить любые, сколь угодно сложные, фигуры, представленные как неявным описанием, так и явным заданием границы, либо цифровым бинарным изображением. С другой стороны, скелет многоугольной фигуры имеет аналитическое описание в виде геометрического графа с ребрами, являющимися отрезками прямых линий и квадратичных парабол, что существенно упрощает его вычисление и анализ.
Цель работы: разработка эффективных методов скелетной сегментации формы многоугольных фигур, основанных на математически корректных моделях, имеющих формальные показатели качества сегментации и позволяющих сравнивать и классифицировать объекты по форме.
Подход к достижению указанных целей основан на понятии срединной оси фигуры. Понятие срединной оси плоской фигуры (или скелета) было впервые введено в конце 1960-х годов Blum1. Он показал, что медиальное представление объектов (от англ. medial representation), присутствующих на двумерных изображениях, является эффективным способом описания их
1Blum H. A transformation [or 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.
геометрической структуры.
Существующие методы сегментации, в том числе методы, использующие скелетное представление, основываются на эвристических правилах. Для оценки качества сегментации используются экспертные критерии на базе субъективных визуальных оценок. Это не позволяет оптимизировать сегментацию формы, а также сравнивать между собой различные методы сегментации.
Таким образом, с одной стороны, скелетное представление формы открывает принципиальную возможность построения и использования скелетной сегментации при сравнении и классификации формы. Разработанные в последнее время методы описания формы дискретных изображений в виде непрерывного скелетного представления многоугольных фигур (Местец-кий2) позволяют использовать скелетное представление для анализа и распознавания изображений. С другой стороны, известные методы сегментации формы основываются на эвристических правилах, не имеют формальных критериев качества сегментации и не приспособлены для решения задач сравнения формы объектов. Этим обосновывается актуальность темы, направленной на исследование и разработку новых методов сегментации формы, которые позволили бы преодолеть указанные недостатки известных методов.
Научная задача заключается в разработке новых методов сегментации формы, основанных на скелетном представлении и имеющих формальные показатели качества сегментации. Сложность этой задачи обусловливается несколькими факторами:
1) Скелетизация — некорректная задача по Адамару. Использование скелета для представления формы объектов порождает проблему "шумовых" ветвей (рис. 1). Для нескольких аппроксимирующих фигур, различия которых практически незаметны для глаза, можно получить скелеты с разной топологической структурой. Небольшие нерегулярности в границе фигуры, являющиеся зачастую следствием шумов, приводят к появлению соответствующих шумовых ветвей скелета. Отсюда возникает проблема регуляризации скелетного графа в интересах дальнейшей его сегментации.
2) Неопределенность понятия качество сегментации и необходимость его формализации. Критерий качества сегментации фигуры должен привноситься извне и формироваться исходя из дальнейшего использования результатов. В частности, необходимо сформулировать критерий качества сегментации применительно к задаче классификации формы объектов.
3) Необходимость корректной работы с парами фигур. Задача совместной сегментации пар фигур возникает при разработке метрик, описывающих сходство и различие формы изображений в задачах классификации.
2Местецкий Л. М. Непрерывная морфология бинарных изображений. Фигуры. Скелеты. Циркуляры Москва. ФИЗМАТЛИТ, 2009
Рис. 1: Скелеты многоугольников.
Структура предлагаемого метода решения
Предлагаемое решение поставленных задач основывается на выделении
последовательном решении двух задач скелетной сегментации:
1. Задача генерации скелетных дескрипторов формы по критериям полноты описания — задача сегментации фигуры.
(a) Циркулярное представление фигуры — задание полного описания фигуры. Данное представление содержит в себе "лишнюю" информацию для описания формы.
(b) Определение признаков формы — множеств подциркуляров фигуры при помощи морфологических функций и проекций.
(c) Определение устойчивой проекции фигуры — малоинформативное, но устойчивое описание фигуры.
((1) Определение функции устойчивости сегментации, (е) Генерация признаков по критериям соответствия и полноты описания.
2. Задача селекции скелетных признаков по критериям отделимости классов — задача сравнения формы фигуры.
(a) Определение априорной информации об изоморфизме циркуляров — топологическая функция устойчивости.
(b) Определение функции устойчивости пары образов — метрическая функция устойчивости.
(c) Селекция признаков по критериям отделимости классов — оптимизация по топологической и метрической функциям устойчивости.
(с)) Определение меры сходства на паре фигур.
На защиту выносятся следующие новые научные результаты:
1. Критерий качества скелетной сегментации фигуры, основанный на определении функции штрафа при помощи противоположных по смыслу функций соответствия и устойчивости. Метод скелетной сегментации фигуры, основанный на минимизации циркулярной функции штрафа.
2. Критерий качества скелетной сегментации пары фигур. Метод скелетной сегментации пары фигур, основанный на минимизации циркулярной функции штрафа для пар.
3. Алгоритм поиска оптимальной сегментации пары фигур, основанный на определении циркулярной функции штрафа для пары фигур с учетом априорной информации об изоморфизме скелетов и на минимизации функции штрафа для пары. Определение множества циркуляров общего положения. Доказательство существования и единственности решения на множестве базовых циркуляров общего положения.
4. Циркулярная мера сходства формы фигур, основанная на проекции циркулярной функции штрафа на множестве пар циркуляров.
Научная новизна
1. Подход к определению критерия качества скелетной сегментации фигуры через методы математической морфологии.
2. Идея определения моделей сегментации формы на основе оптимизации по соответствию и качеству.
3. Формализация аппарата циркулярной морфологии: множества циркуляров, операторы проектирования на множествах циркуляров, циркуляры уникальной проекции, максимальный единичный проектор, циркулярные функции штрафа, соответствия, устойчивости.
4. Новый метод скелетной сегментации фигуры, основанный на минимизации циркулярной функции штрафа.
5. Новый критерий качества скелетной сегментации пары фигур, основанный на циркулярной функции штрафа для пары фигур и априорной информации об изоморфизме.
6. Новый метод скелетной сегментации пары фигур на основе оригинального критерия качества.
7. Алгоритм построения монотонного множества вложенных цепочек циркуляров, алгоритм поиска оптимальной сегментации пары фигур.
8. Новая циркулярная мера сходства формы фигур, основанная на проекции циркулярной функции штрафа на множестве пар циркуляров.
Научная значимость работы состоит в формализации математической морфологии на множестве циркуляров — определении аппарата циркулярной морфологии, который может быть использован для определения общих и прикладных мер для сравнения плоских фигур, а также в определении теоретически корректного критерия сегментации одной фигуры и зависимого критерия сегментации пары фигур.
Практическая значимость заключается в том, что представление фигур с помощью скелетной сегментации и циркулярной морфологии может
быть использовано в задачах распознавания формы. Полученные результаты могут найти применение в программных комплексах двумерной векторной графики, в системах распознавания изображений, машинного зрения.
Внедрение результатов
Выносимые на защиту методы были разработаны, исследованы и практически использованы в ходе работ по проектам Российского Фонда фундаментальных исследований (РФФИ) 05-01-00542 "Методы распознавания формы изображений на основе дискретно-непрерывных преобразований"; 0801-00670 "Методы анализа и распознавания формы изображений на основе непрерывных моделей". Представленные в работе результаты частично вошли в книгу "Обработка и анализ изображений в задачах машинного зрения. Курс лекций и практический занятий" (Физматкнига, 2011), рекомендованную в качестве учебного пособия в технических ВУЗах.
Структура диссертации
Работа состоит из оглавления, введения, четырех глав, заключения и списка литературы. Содержание работы изложено на 149 страницах. Список литературы включает 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-ом международном семинаре no анализу изображений: теории и приложениям (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. Под сегментацией скелета будем понимать процесс его конечного разбиения — получение декомпозиции скелета.
Определение 3. Вершинами скелета назовем все центры максимальных пустых кругов, кроме тех, что касаются границы фигуры в двух точках. Ребром скелета, соединяющим две вершины, назовем срединные оси фигуры, состоящие из центров окружностей, каждая касается границы ровно в двух точках. Ветвью скелета назовем простую цепь скелетного графа, в которой все вершины имеют степень два, кроме двух крайних вершин. Ветвь скелета называется терминальной, если она содержит хотя бы одну терминальную вершину скелета, иначе — внутренней. Скелетный граф фигуры — геометрический граф с множеством вершин и ребер скелета фигуры.
Скелетный граф задает скелетную сегментацию, так как его вершины задают разбиение скелета. Но такая сегментация является избыточным описанием и не подходит для решения задач классификации. Кроме того, она неустойчива, так как при незначительных изменениях фигуры скелет может существенно измениться.
Определение 4. Однореберный скелетный оператор та0 : F —> Sk° по фигуре строит максимальную евклидову цепь подграфа ее скелета.
Теорема 1. Однореберный скелетный оператор та0: F —>• Sk° устойчив на паре метрических пространств (Ф,Л) с расстояниями рФ(.,.) — расстояние Хаусдорфа и р\{.,.) — топологическое скелетное расстояние (разность числа ребер скелетных графов).
Зта от англ. medial axes
Представления в виде однореберных скелетных подграфов являются малоинформативными и не позволяют решать задачи классификации и сравнения формы. Возникает вопрос о поиске достаточно устойчивого, но при этом достаточно информативного промежуточного скелета.
Таковым является базовый4 скелет фигуры, полученный за счет стрижки терминальных ветвей скелета. Он улучшает качество скелетной сегментации, на его основе можно построить "базовую скелетную сегментацию фигуры", которая лучше отражает структуру фигуры по сравнению с сегментацией на основе скелета фигуры.
Вторая глава посвящена скелетной сегментации и циркулярной морфологии многоугольника. Предлагаемый в работе подход базируется на расширенном по сравнению со скелетным представлением фигуры: циркулярным.
Определение 5. Циркуляр — геометрический граф с множеством кругов с центрами на нем. Объединение всех его кругов называется его силуэтом.
Определение 6. Срединный циркуляр с™^) фигуры Р1 — это такой циркуляр,
• его осевой граф совпадает со скелетом фигуры F\
• его множество кругов совпадает со множеством максимальных вписанных пустых кругов фигуры F.
Лемма 1. Любой плоской фигуре F соответствует единственный срединный циркуляр.
Таким образом, задача сегментации многоугольника сводится к задаче сегментации циркуляра.
Определение 7. Назовем С2 е в подциркуляром циркуляра ci или вложенным в циркуляр си если осевой граф С2 вложен в осевой граф с\ и все круги, соответствующие сг, принадлежат и с\\
с2СС1 ЛШ9(С2)^7(С1)5 (1)
\Vt € mg(C2) : с( е С2 Q е С]
Функции, задающие полноту и устойчивость циркулярного представления, определены на базе математического аппарата критериальных и проективных морфологии Визильтера б.
*Местецкий J1. М. Непрерывная морфология бинарных изображений. Фигуры. Скелеты. Циркуляры.
Москва, ФИЗМАТЛИТ 2009 г.
6Визильтер Ю.В., Желтое С.Ю., Бондаренко A.B., Ососков М.В., Моржин A.B. Обработка и анализ изображений в задачах машинного зрения. Курс лекций и практических занятий.- М: Физматкнига, с. 384389, 2010.
Определение 8 (Расстояние между парой циркуляров). Расстоянием между циркулярами с\ € 6 и сг 6 9 назовем величину, равную расстоянию Хаусдорфа между их силуэтами:
Пн(сис2) = ВЕ (5й(с1), 5г/(с2)) (2)
Определение 9. Базовым подциркуляром с точностью, равной нулю, является сам циркуляр: с(£=0) = с*. Базовым подциркуляром циркуляра с* с точностью е > 0 назовем минимальный подциркуляр с(г) циркуляра с*, вложенный во все базовые подциркуляры с точностями меньше е, такой, что расстояние Хаусдорфа между циркуляром и подциркуляром не превосходит е.
¿е) с с* — подциркуляр
£>я(с*,с^) < е — расстояние не превосходит е • Ус С с*: сф№, £>я(с*, с) < е => с^ с с - подциркуляр минимальный
Уех < е =>■ с(£) С с(£1' - вложен во все базовые подциркуляры с меньшей
точностью
д (3)
Алгоритм построения монотонных цепочек циркуляров на основе стрижки
Базовые подциркуляры можно получать при последовательной стрижке терминальных ветвей циркуляра. Так для циркуляра с можно построить монотонные вложенные цепочки подциркуляров. Первый подциркуляр совпадает с циркуляром с: с° = с. От него на каждом шаге "отстригается" такая терминальная ветвь, что ее удаление наименьшим образом влияет на силуэт 5г/(с). Если таких ветвей несколько, то они отстригаются все.
Обозначим упорядоченное множество полученных вложенных подциркуляров и соответствующее множество точностей их стрижки:
с={с0,.-. ,сп};£ = {£0,... ,е»} (4)
Рассмотрим случай, когда всем точностям из цепочки ё = ■•■ ,еп} (4) соответствует ровно по одной "отстриженной" терминальной ветви. То есть Уг = 1, •■• ,п {ег} = е\ Описанное условие называется уникальностью терминальной стрижки.
Определение 10. Циркуляр общего положения — это циркуляр, для которого выполнено условие уникальности терминальной стрижки.
Замечание: использование расстояния Хаусдорфа дает в общем случае неэффективный алгоритм полиномиальной сложности. На практике можно использовать другие расстояния, которые делают алгоритм субкубической сложности И2 к^ N. Например, расстояние, равное сумме длин отстригаемых ребер или верхнюю оценку расстояния Хаусдорфа, которую можно
Рис. 2: Пример: подциркуляры-проекции.
сделать для подциркуляров. Такие расстояния вычисляются аналитически и суммируются на каждом шаге, засчет чего достигается высокая эффективность алгоритма.
Определение 11 (Максимальный стриженный подциркуляр). Максимальный стриженный подциркуляр — циркуляр, полученный в результате алгоритма построения монотонного подмножества циркуляра, осевой граф которого представляет собой максимальную простую цепочку.
Определение 12 (Оператор проектирования на максимальный стриженный подциркуляр). Назовем оператором проектирования циркуляра с € в на максимальный стриженный подциркуляр оператор, ставящий в соответствие циркуляру с его максимальный стриженный подциркуляр. Обозначим такой оператор Рг2(с).
Рг2 : в 0; Ргг(с) = ] = тах {г : 6с - простая цепочка} (5)
Лемма 2. Для любого циркуляра общего положения: с € 0 существует такой номер у > 0, что в его цепочке подциркуляров 4 осевой граф циркуляра является простой цепочкой, а сам циркуляр с"-'' принадлежит модельному множеству проектора Рг2-
Доказательство. Достаточно показать, что для ] = 1 лемма верна. □
Оператор проекции Рг2 можно использовать для генерации признаков формы. Для фиксированного циркуляра с проекция Ргг(с) — это признак циркуляра с.
Определение 13. Базовый циркуляр с точностью е для циркуляра общего положения с* — это максимальный циркуляр Сд\ находящийся между "соседними" базовыми подциркулярами или совпадающий с одним из базовых подциркуляров, такой, что расстояние Хаусдорфа между ним и циркуляром
с* в точности равно е:
е' < е < £,+1;eI,e,+I бе — величина е находится между точностями из монотонной цепочки (4);
с* = Cß ,с1 ее — циркуляр с* из монотонной цепочки (4) изоморфен базовому циркуляру с^';
c'\cg = егв или с1 — ¿-> — разницу между циркуляром с® из монотонной < цепочки и базовым циркуляром составляет кусок одного ребра или же они совпадают;
DH(c*,Cß) = £ — расстояние Хаусдорфа между базовым циркуляром и исходным циркуляром с* в точности равно е;
Vi € mg(c^ß) : Ct&d Ct £ c^' — все круги с центрами на осевом графе тд(с^) принадлежат базовому циркуляру
(6)
Определение 14. Монотонное подмножество циркуляра Qs{c*) общего положения с* £ © — это все подциркуляры из множества всех циркуляров 9, подциркуляром которых является также максимальный стриженный подцир-куляр циркуляра с: вs(c") = (с? С с С с*}
Определение 15. Базовое множество циркуляра с — множество всех базовых циркуляров циркуляра с с точностями из отрезка [0,еп].
св = { 4е):£6[0,£"]} (7)
Определение 16. Циркулярная функция штрафа — это функция на множестве пар циркуляров Ф : 0 х © R следующего вида:
Фс(с, с') = Jc(c, d) + Хс(с, с') + acQc(c') (8)
Где с — циркуляр-проецируемый образ, а d — циркуляр-проекция.
0.1 Задача поиска циркулярной проекции
Сформулируем задачу поиска циркулярной проекции.
Задача 1. Найти циркуляр, доставляющий минимум циркулярной функции штрафа.
®i(ci, ci) = Pr{cu Je, Qe) = arg min Фс(сь c[) (9)
И)ее
Определение 17 (Хорошо определенная функция штрафа). Функция штрафа (8) хорошо определена, если требования соответствия и устойчивости оказываются противоположными: из неравенства "функция соответствия на проекции В\
меньше или равна функции соответствия на проекции В2" следует обратное неравенство для функции устойчивости: Q(Bi) > Q(B2), а из неравенства "функция устойчивости на проекции В\ больше или равна функции устойчивости на проекции В2" следует обратное неравенство для функции соответствия: J(A, В{) < J(A,B2).
ул € п • ¡VBh Bí € ф): J(A Bí) - J{A Bí) * Q{Bl) - Q{Bl}
' \vß3,-B4 € : Q(B3) > Q(B4) =► J(A,B3) < J(A,B4)
(10)
Определение 18. Циркулярная функция соответствия Jc(c, d) — это расстояние Хаусдорфа между циркуляром-образом и циркуляром-проекцией для всех проекций, являющихся подциркулярами проецируемого образа.
(11)
1+00, с % с
Теорема 2. Функция J{c,d) является функцией соответствия на множестве допустимых проекций V(c, Ф).
Определение 19. Множеством допустимых проекций функции Ф назовем множество всех проекций, на которых функция Ф(Л, В) принимает конечное значение: V(A, Ф) = {В : Ф(Л, В) < +оо }
Лемма 3. При определении функции соответствия Jc(c, с') через расстояние Хаусдорфа (11), множеством допустимых проекций V (с, Фс) функции Фс будут только подциркуляры циркуляра с.
Лемма 4. Функция соответствия Jc(c, d) является монотонной (не убывающей) на множестве допустимых проекций V(c, Ф) и строго монотонной (возрастающей) на множестве d е с = {с0, • • • , с"}.
Определение 20. Функция устойчивости — это расстояние Хаусдорфа между циркуляром- проекцией d и максимальной единичной проекцией Pr2(d):
Qc(c') = DH(c',Pr2(d)) (12)
Лемма 5. Функция штрафа Фс (8) эквивалентна следующей функции (упрощенная функция штрафа): ФC(c,d) = Jc{c,d) + acQc(d).
Теорема 3. Функция штрафа Фс (8) хорошо определена
Доказательство. В силу леммы 5 теорема доказывается по определению хорошо определенной функции на упрощенной функции штрафа. □
Поэтому задача поиска наилучшей сегментации поставлена как задача поиска циркуляра, минимизирующего функцию штрафа:
Ф(с, Ф) = arg min Ф Je, с')
с'ей
Лемма 6. Решение задачи 1 (минимум функции Фс(с, с!)) находится в монотонном подмножестве циркуляра с (4).
Параметр ас функции штрафа определяет степень важности устойчивости или соответствия искомого оптимального циркуляра. Он должен задаваться исходя из прикладной задачи, в которой необходимо искать оптимальный циркуляр. Монотонность функции соответствия позволяет найти оптимальный циркуляр конструктивно, выбрав его из множества вложенных монотонных подциркуляров (4).
Третья глава посвящена выбору наилучшей скелетной сегментации для пар фигур. Для пар циркуляров вводятся аналогичные операторы и критерии, что и для циркуляров. Описываются их свойства. Для пары плоских циркуляров предлагается концепция морфологического проектора с априорным условием изоморфизма.
Определение 21. Два скелета изоморфны, если существует изоморфизм соответствующих скелетных графов, сохраняющий ориентацию любых трех подряд идущих вершин при положительном направлении обхода двух скелетных графов.
Определение 22. Два циркуляра с\ и сг изоморфны, если изоморфны их осевые графы: тд(с\) = тд(с2).
Введем обозначения:
©2 = {(с1>с2) : С1 е 6,сг € © : тд(с\) = тд(с2)} — множество всех пар изоморфных циркуляров на плоскости;
9(с1 ,сг) = К С С с2 : с! = 4} - множество всех пар изоморфных подциркуляров (с1,сг) на плоскости.
0(с1,сг) = {с^ С С1,4 С сг : с^ = ¿¿} — множество пар всех базовых циркуляров общего положения (с1,сг) на плоскости.
Определение 23. Функция устойчивости для пар циркуляров — это индикатор их изоморфизма:
Определение 24. Функция соответствия для пары циркуляров с\ и съ
Мс1,с[,с2,4) =шах{7с(с1,с'1), 7с(с2,с2)} (14)
Определение 25. Функция штрафа для пары циркуляров С\ и сг имеет вид: ^2(01,^,02,4) = Нси^.со^с^ + С}^^) (15)
О, тд(4) ^ тд{с +оо,тд^1) % тд(с
(13)
Определение 26. Морфологический проектор с априорным условием изоморфизма выглядит следующим образом:
Щсис2,с'1,^2)=рг(с1,с2)=агд min Ф2(си с[, с2, с'2) (16)
(ci,4)€e2
Определение 27. Проекция пары циркуляров (ci,c2) — это пара (cj, Cj), доставляющая минимум функции штрафа <b2(c\,dx,c2,d^.
Задача 2. Построить морфологический проектор (16) с априорным условием изоморфизма Ф2(с1,с2,с'1,4) на множестве в2.
Для решения поставленной задачи доказан ряд утверждений.
Теорема 4. Множество допустимых проекций функции (15) Ф2 — это множество всех изоморфных подциркуляров cj и с2.
Теорема 5. Множество V(cuc2, Ф2) = 6(ci,c2) ограничено в метрическом пространстве ©2 с расстоянием wr((ci, С2), (ci,с'2)) = max{DH(ci, с2), £>#(4,4)}.
Доказательство. Идея доказательства: выбрать значением числа М\ — максимальный из диаметров циркуляров сг и с2. Показать, что для любой пары циркуляров (ci,4) из множества У(сьс2,Ф2) = 9(ci,c2), верно, что Ин((х',у*),{с?ъс'2))<М1. □
Теорема 6. Функция J2(ci,4,c2,4) соответствия (14) непрерывна по переменным {dx,4) на множестве допустимых проекций функции ^2{c\,dl,C2,d2): (4,4) е V(cuc2. Ф2) на метрическом пространстве в(сь с2) с расстоянием /4}'C2(4, 4) = тах{£»я(сь ci), DH(c2, 4)}-
Доказательство. Идея доказательства: по определению непрерывности функции в метрическом пространстве. □
Лемма 7. Функция устойчивости на основе априорной информации об изоморфизме Q2(4,4) непрерывна на множестве допустимых проекций функции Ф2(ci,4,c2,4).
Определение 28. Расстоянием между двумя парами циркуляров из множества всех изоморфных циркуляров в2 назовем следующую величину
т?асжлис'1,4)) =
(| тах{0я(сь 4), Dh(c2, 4)} - max{DH{cu 4'), DH(c2,4')}|, = 1 при (ci, с^) 6 ёв(сис2),{с'{,<%) е вв(сис2) (17)
[Л/, иначе
Где М > 0 — фиксированная положительная величина, равная максимуму по всем циркулярным расстояниям из множества 0B(ci,c2):
М = /Г((си):(с'/,4')) (18)
(c'„4)6es(cl,c2);(ciIcJ)eeB(cl,c2)
Л с; ¿1 -*-» Рг(С1)
11-1-1 02 е5(С1,С2) -2-» в(С1,С2) в(Рф1),Рг(с2))
1 I -Т -1
—с^ —с2 —Рг(са)
Рис. 3: Схема преобразования циркулярного представления к проекциям, а-фигуры и их срединные циркуляры; Ь-подциркуляры; с-изоморфные подциркуляры; (1-проекции;
Лемма 8. Расстояние между двумя парами циркуляров из множества всех изоморфных циркуляров (17) удовлетворяет аксиоме метрики: "неравенство треугольника".
Доказательство. Для произвольных трех пар циркуляров необходимо рассмотреть 4 случая их принадлежности множеству монотонных подциркуля-ров ев(сьс2). □
Лемма 9. Множество монотонных изоморфных подциркуляров пары циркуляров (с^сг) на плоскости 6в(с1,с2) замкнуто относительно в2.
Теорема 7. Функция штрафа для пары циркуляров Ф2(с1,с2, 4) (¡5) непрерывна на множестве допустимых проекций.
Доказательство. Это утверждение следует из непрерывности суммы двух непрерывных функций ^(сь^цсг.^) и <32(с'154) от переменных (с^с^) на множестве допустимых проекций. □
Теорема 8. Для каждой пары циркуляров существует проекция функции Ф2(С1,<А,С2,4) (16).
Доказательство. Идея доказательства: множество, в котором лежит проекция, сужается до подмножества 6(сь с2), которое не пусто. В силу леммы 9 множество ©(с^сг) замкнуто относительно в2. То есть функция непрерывна (теорема 7) на замкнутом ограниченном (теорема 5) множестве ©(съсг), поэтому достигает на нем своего минимального значения. □
Переформулируем задачу (16) на множестве циркуляров общего положения.
Задача 3. Для любой пары циркуляров общего положения (с^сг) € 0 найти проекцию (<^,4) = Рг(сис2,12,<22).
Теорема 9. Одно из решений задачи поиска проекции для пары циркуляров (задача 3) лежит в монотонных упорядоченных множествах с\ и ¿2, то есть 3(с^сг) 6 Фг(съ сг.с^Сг) : с* е 6 с2.
Доказательство. Пусть в монотонных множествах с\ и ¿2 выбрана пара изоморфных подциркуляров с\ 6 ¿г, £ ¿2: с\ = ¿2 с минимальными индексами 1,3. Предположение о том, что пара (с\,с!,) не оптимальная для функции Фг(с1, (4,02,4) на множестве 6(с1,с2) приводит к противоречию. □
Теорема 10. Для пары циркуляров общего положения с1,с2 решение задачи поиска проекции для пары циркуляров с\,с% единственно.
Таким образом, для решения задачи 1 необходимо построить цепочки монотонных подциркуляров и найти решение в этих цепочках.
Лемма 10. Для циркуляра общего положения количество ветвей циркуляров из цепочек с! и с2 (4) равно: {п + 1,п,••• ,1} и {т + 1,т, ■ ■ ■ , 1} соответственно. Где пит — количество циркуляров цепочек ¿1 и с2 соответственно.
Предположим, без ограничения общности, что т <п, тогда = #<4. Поэтому для любого значения г = 0,...,т количество ветвей циркуляров из цепочки с соответствующими индексами т — г и п — г одинаково, т.е. = Решение задачи сводится к поиску
минимального индекса г, при котором вложенный циркуляр первой цепочки изоморфен вложенному циркуляру второй. Проверку изоморфизма предлагается свести к поиску топологической эквивалентности диаграмм смежности соответствующих осевых графов циркуляров. Если существует их наложение, то циркуляры изоморфны. Алгоритм построения монотонных множеств с, ё имеет полиномиальную вычислительную сложность по числу ребер циркуляра с. Оптимизировать алгоритм для решения практических задач можно в трех направлениях:
1. Замена расстояния Хаусдорфа на менее вычислительно трудоемкое расстояние.
2. Построение цепочек монотонных циркуляров не полностью.
3. Использование информации о предыдущих шагах алгоритма.
Применяя все способы оптимизации, можно свести вычислительную сложность алгоритма решения задачи поиска проекции сводится к субкубической по минимальному числу ребер одного из циркуляров с\ и с2 в худшем случае.
Итак, можно считать, что найденная проекция является наилучшей парой циркуляров, аппроксимирующих две заданные фигуры. С одной стороны она хорошо (в смысле расстояния Хаусдорфа) аппроксимирует обе фигуры, с другой стороны является наиболее "простой" (в смысле близости к максимальным единичным циркулярам). Кроме того, априорное условие изоморфизма ограничивает множество допустимых проекций и дает интересное в прикладном смысле множество решений для пар фигур.
й
•к
з®
6
Рис. 4: Проверка изоморфизма осевых графов циркуляров: круговая диаграмма смежности.
В четвертой главе описано приложение теории циркулярной морфологии с задачам сравнения формы.
Определение 29. Циркулярное расстояние с условием изоморфизма для пары фигур — это значение функции штрафа на паре проекций функции с априорным условием изоморфизма срединных циркуляров этих фигур:
где (с*,с2) = Ф2(ста(^),с'м(^),Ф2,д2)
Теорема 11. Циркулярное расстояние удовлетворяет четырем аксиомам полуметрики: 1) рс{Р,Е) = 0; 2) рс{Р\,Р2) > 0; 3) = 0 = но необязательно Я = 4)
Я) + рс(*2, > -Рз) ЙАЯ любых Я,
Определение 30. Экспериментальным пороговым циркулярным расстоянием с порогом г) назовем следующую величину:
Экспериментальное пороговое расстояние позволяет упростить и ускорить алгоритм поиска проекции.
Описано 5 модельных экспериментов, подтверждающих достоверность и эффективное применение разработанных методов к задачам распознавания формы плоских фигур и запросам по базе изображений.
Эксперимент 1: устойчивость к деформации Рассматривается упорядоченное множество из прямоугольников с уменьшающимся шумовым отростком (рис. 5). Рассчитываются расстояния от первого, среднего и последнего многоугольников до остальных. Эксперимент показывает устойчивость предложенной меры сходства к незначительным деформациям.
(19)
(20)
Рис. 5: Прямоугольники с уменьшающимся шумовым отростком.
12 34 5678 9 10
Рис. 7: Диаграммы циркулярных расстояний: от осла до остальных фигур (слева), от зайца до остальных фигур (справа).
Эксперимент 2: Монотонность расстояний при морфинге фигур. Рассматривается последовательность фигур животных, для которых происходит плавный морфинг одной фигуры в другую: "осел превращается в зайца" (рис. 6). Графики циркулярных расстояний от осла до остальных фигур рис. 7 (слева) и от зайца до остальных фигур рис. 7 (справа) показывают монотонность последовательности этих расстояний. Таким образом, предложенная мера сходства хорошо отделяет различные фигуры, даже имеющие незначительные структурные различия. Это преимущество достигается за счет метрической компоненты предложенной меры сходства.
Эксперимент 3: классификация инструментов.
Проведен эксперимент, предложенный Torsello7. Имеется множество, состоящее из двух классов инструментов: разводные ключи и плоскогубцы. Необходимо для каждого инструмента отсортировать расстояния от него до остальных.
Для решения задачи рассчитываются все расстояния от каждого инструмента до остальных. Получаются последовательности расстояний. Определяются верные последовательности инструментов и последовательности на основе полученных расстояний. Рассчитывается количественная оценка качества работы методов с помощью перестановок до верно отсортированных последовательностей. Процент ошибки — это количество перестановок для каждого из инструментов, нормированное по максимальному количеству перестановок для всех инструментов. В результате метод Torsello дает 34% перестановок до правильных последовательностей, а циркулярная мера сходства всего 20%, что показывает ее более высокое качество в сортировке
7Torsello A. and Hancock Е. R. A Skeletal Measure of 2D Shape Similarity. Computer Vision and Image Understanding, vol. 95, no. 1, pp. 1-29. 2004.
V 0.0009 > 0.00238 > 0.0077 Ч 0.00857 Ч 0.0381 0.209
ч Р 0.0012 0.017 Ч 0.023 0.039' <? 0.0516 V 0.074-
ч 0.С0048 V 0.001 :> 0.0015 0.0439 > 0.0048 Ч 0.00926
ч сахд > 0.0005 0.0019 V 0.003 Ч 0.009 0.10297
Ч > 0.0002 :> 0.0005 V 0.0105 р 0.013® Ч 0.0139 0.1292
ч 0.0176 Ч 0.07268 0.1338 > 0.1338 01397 V 0.1397
ч 0.00005 0.0002 0.0017 V 0.0032 0.0635 ч 0.0064
V ЭР СХ р ч ч
0.068 0.061 0.108 0,112 0.132 0.18Т
ч ^ э» ч ^ V
0.053 0.054 0:063 0.Ш1 0.087 0.112
> ч ч ^ V
о.озо 0.048 0.054 0.081 0.092 0.108
> > 4- ч V ч
0.021 0:030 0.064 0.081 ¡¿086 апо
ч ч р ^ ^ 3» V
:о.ш 0:084 0.086. 0:095.: 9.102 0.132
ч ч Э» V
О.038 0.092 0.095 0.11« .0.128. 0.186
э» :> ¿- V ч ч
0:021 0:048 0.068 о:обэ 0.102 0.128
Рис. 8: Слева: циркулярное расстояние (19). Справа: "Производная" скелетная мера сходства (ТогееИо, 2004).
инструментов.
Эксперимент 4: Задача распознавания на основе скелетной сегментации.
Заданы: 142 фигуры в виде бинарных изображений (рис. 9), содержащая объекты трех классов: мыши (69), руки (22) и птицы (51).
Необходимо: решить задачу распознавания с набором прецедентов и контрольных объектов. Решение:
(1) Построение признакового пространства на множестве всех объектов.
(2) Случайное разделение всей выборки на обучающую и контрольную.
-------------
г\
МкШ
Г ? V V- V- Ч»— ^ ^ 3
V* Г ^ ^ Ч ^
* ^ ф Ф а? К
Рис. 9: База данных 181 плоская фигура. 20
ч >
1 ¿у >
2 ♦ ¥ ✓ 1
3 Г V- К •0
4 Ч > < /
5 / / X /
6 * ¥ 1 г"- щ V X
Рис. 10: 6 ближайших по циркулярному расстоянию (19) фигур из базы Использование метода скользящего контроля.
(3) Использование стандартных методов обучения выборки (метод к-ближайших соседей, голосование по логическим закономерностям классов, метод опорных векторов, комбинированный комитетный метод), оценка точности работы алгоритма на контрольной выборке.
В работе наилучшего алгоритма всего один объект классифицирован неверно: мышь, отнесенная к классу птиц. Таким образом, подход к сравнению формы с помощью изоморфных непрерывных скелетов был успешно реализован и проверен на модельном приложении распознавания формы. Проведенные эксперименты показали очень хорошие результаты.
Эксперимент 5: Сравнение формы: эксперименты с запросами. Имеется база изображений, состоящая из 181 фигуры (рис. 9).
Задача: для каждой фигуры найти ближайшие в смысле циркулярного расстояния 6 фигур. В результате для каждой из фигур от 4 до 6 ближайших найденных относятся к тому же классу, кто и сама фигура (рис. 10).
В заключении перечислены основные результаты работы.
Список ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ
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 4th International Conf. 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.
Напечатано с готового оригинал-макета
Подписано в печать 12.03.2014 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 034.
Издательство ООО "МАКС Пресс" Лицензия ИДЫ 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.
московский государственный университет
имени М.В. Ломоносова ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ
Кафедра математических методов прогнозирования
На правах рукописи удк 519.72,519.68
04201457555
Домахина Людмила Григорьевна
СКЕЛЕТНАЯ СЕГМЕНТАЦИЯ И ЦИРКУЛЯРНАЯ МОРФОЛОГИЯ МНОГОУГОЛЬНИКОВ
01.01.09 - Дискретная математика и математическая кибернетика.
Диссертация на соискание степени кандидата физико-математических наук
Научный руководитель доктор технических наук, профессор Л.М. Местецкий
Москва 2013 г.
Оглавление
Введение 11
Глава 1. Задача сегментации фигуры и скелета 27
1.1. Фигура 28
1.2. Скелетное и циркулярное представление фигуры 29
1.2.1. Скелет фигуры 29
1.2.2. Скелетное представление фигуры 30
1.3. Сегментация изображения, фигуры и скелета 31
1.3.1. Задача сегментации фигуры 32
1.3.2. Задача сегментации скелета 32
1.3.3. Геометрический граф 33
1.3.4. Скелетный граф 34
1.3.5. Циркулярный граф 35
1.3.6. Циркулярное представление фигуры 36
1.4. Обзор литературы 36
1.4.1. Методы сегментации фигуры 36
1.4.2. Примеры сегментации скелета в литературе 41
1.5. Скелетная сегментация фигуры 43
1.6. Качество скелетной сегментации 45
1.6.1. Некорректность задачи скелетизации 45
1.6.2. Устойчивость сегментации и регуляризация скелета по Тихонову 48
1.6.3. Базовая скелетная сегментация фигуры и ее свойства 52
1.7. Выводы главы
54
Глава 2. Скелетная сегментация многоугольника на основе циркулярной
морфологии 57
2.1. Метрические критерии сходства циркуляров 59
2.1.1. Расстояние Хаусдорфа для пары циркуляров 59
2.1.2. Погрешность аппроксимации фигуры циркуляром 59
2.1.3. Срединный циркуляр фигуры 60
2.2. Топологические критерии сходства циркуляров: изоморфизм 60
2.2.1. Изоморфизм скелетов 61
2.2.2. Изоморфизм циркуляров 63
2.3. Оператор проектирования на множестве циркуляров 64
2.3.1. Ветвь циркуляра 64
2.3.2. Подциркуляр 65
2.3.3. Максимальный простой подциркуляр и циркуляр уникальной
проекции 66
2.3.4. Проектор максимальной длины 67
2.3.5. Модельное множество проектора максимальной длины 68
2.4. Морфологический анализ циркуляров: критериальные морфологии 69
2.4.1. Критериальные морфологии для множества циркуляров 71
2.4.2. Циркулярная функция штрафа 72
2.5. Базовый подциркуляр с контролируемой точностью 72
2.5.1. Стрижка терминального ребра и ветви циркуляра 72
2.5.2. Алгоритм построения монотонных цепочек подциркуляров на
основе стрижки 75
2.5.3. Циркуляры общего положения 77
2.6. Базовый циркуляр с контролируемой точностью 78 2.6.1. Рекурсивное определение базового циркуляра с контролируемой
точностью 78
2.7. Циркулярная функция соответствия 80
2.7.1. Задача поиска циркулярной проекции 81
2.7.2. Свойства циркулярной функции соответствия 81
2.7.3. Множество допустимых проекций циркулярной функции штрафа 82
2.7.4. Монотонность функции соответствия 83
2.8. Циркулярная функция устойчивости проекции 83
2.9. Свойства циркулярной функции штрафа 84
2.10. Выводы главы 86
Глава 3. Скелетная сегментация и циркулярная морфология пары
многоугольников 88
3.1. Наилучшая скелетная сегментация пар фигур 88
3.2. Морфологический проектор с априорным условием изоморфизма
для пар циркуляров 89
3.2.1. Априорная информация об изоморфизме 90
3.2.2. Функция устойчивости на основе априорной информации об
изоморфизме 91
3.2.3. Функция соответствия для пары циркуляров 91
3.2.4. Функция штрафа для пары циркуляров 92
3.2.5. Морфологический проектор с априорным условием изоморфизма 92
3.2.6. Задача поиска проекции с априорным условием изоморфизма 93
3.3. Свойства функций, введенных на парах циркуляров 93 3.3.1. Описание множества допустимых проекций для пар циркуляров 93
3.3.2. Ограниченность множества допустимых проекций 95
3.3.3. Непрерывность функции соответствия на множестве допустимых
проекций 96
3.3.4. Непрерывность функции устойчивости на множестве
допустимых проекций 97
3.3.5. Непрерывность функции штрафа на множестве допустимых
проекций 98
3.3.6. Замкнутость множества монотонных изоморфных подциркуляров 98
3.4. Существование проектора с априорным условием изоморфизма 101
3.5. Единственность решения задачи поиска оптимальной проекции на
множестве циркуляров общего положения 102
3.5.1. Задача поиска проекции на множестве циркуляров общего
положения 103
3.5.2. Теорема о локализации одного решения задачи поиска проекции 103
3.5.3. Теорема о единственности решения задачи поиска проекции на
множестве циркуляров общего положения 105
3.6. Решение задачи поиска проекции функции с априорным условием
изоморфизма 106
3.6.1. Общая схема решения задачи 106
3.6.2. Алгоритм проверки изоморфизма циркуляров 106
3.6.3. Поиск проекции функции с априорным условием изоморфизма в
монотонных цепочках 110
3.6.4. Алгоритм поиска изоморфной пары в монотонных цепочках 110
3.7. Вычислительная сложность алгоритма решения задачи поиска
проекции 111
3.7.1. Вычислительная сложность алгоритма построения монотонных
цепочек циркуляров 111
3.7.2. Вычислительная сложность алгоритма проверки изоморфизма 112
3.7.3. Вычислительная сложность алгоритма решения задачи поиска
проекции 113
3.7.4. Оптимизация алгоритма решения задачи поиска проекции 113 3.8. Выводы главы 115
Глава 4. Сравнение формы на основе скелетной сегментации 118
4.1. Сравнение формы с использованием скелетов 119
4.1.1. Обзор известных методов сравнения формы с использованием
скелетов 119
4.1.2. Проблемы при использовании скелета для сравнения формы 122
4.1.3. Новый подход к сравнению формы с использованием
изоморфизма скелетов 122
4.2. Метрика на основе проектора — циркулярное расстояние с
условием изоморфизма 124
4.2.1. Определение циркулярного расстояния с условием изоморфизма 124
4.2.2. Свойства циркулярного расстояния с условием изоморфизма 125
4.3. Эксперименты с циркулярным расстоянием 128
4.3.1. Экспериментальное пороговое циркулярное расстояние:
определение 128
4.3.2. Экспериментальное пороговое циркулярное расстояние: свойства 128
4.3.3. Примеры решения модельных задач 130
4.3.4. Устойчивость к деформации 131
4.3.5. Гладкое изменение структуры 132
4.3.6. Примеры решения реальных задач 133
4.4. Задача распознавания на основе скелетной сегментации 137
4.5. Сравнение формы: эксперименты с запросами 140
4.6. Выводы главы 142
Заключение 143
Литература 145
Список основных обозначений:
В(с, а) — функция базового циркуляра с с контролируемой точностью а > О ct — круг с центром в точке t;
с = {cf,i бГ}- семейство кругов с центрами на множестве Т — циркулярный граф;
#с — количество ребер циркуляра с; cma(F) — срединный циркуляр фигуры F; с € © — циркуляр из множества 0; с\ = С2 — изоморфизм циркуляров;
с(е) _ базовый подциркуляр циркуляра с с контролируемой точностью £ > 0;
(е)
св — базовый циркуляр с точностью £ для циркуляра общего положения се®;
deg(vi) — степень вершины v,;
Dh{F\,F2) — расстояние Хаусдорфа между фигурами Fi и F2, Dh{c\->ci) — расстояние Хаусдорфа между циркулярами с\ и С2", е, ео, е\ — ребра графа G = (V,£); F, Fi, Fi — многоугольные фигуры;
G = (V,E) — граф со множеством вершин V и множеством ребер Е; ma(F) — непрерывный скелет фигуры F (от английского "medial axis" — срединные оси);
mg(c) — осевой граф циркуляра с (от английского "medial graph"); ma (Fi) = ma{Fi) — изоморфизм скелетных графов фигур F\ и F2; 0(п) — линейная по параметру п вычислительная сложность алгоритма; П(с1,С2) — функция проверки изоморфизма циркуляров с\ и С2\ Рг — оператор проектирования;
Рг\ (с) — максимальный единичный проектор на множестве плоских циркуляров 0;
Ргг{с) — оператор проекции на максимальный стриженный подциркуляр; — евклидово расстояние между точками х G R2 и у Е R2',
Pc(Fi,/<2) — циркулярное расстояние между фигурами Fi и F2 с условием изоморфизма;
R2 — евклидова плоскость;
Sil (с) = IJ ct — силуэт циркулярного графа с;
0 — множество всех циркуляров на плоскости;
0 — множество всех циркуляров уникальной проекции на плоскости;
0 — множество всех циркуляров общего положения на плоскости;
02 = {(с\,С2) '■ с\ G 0,С2 G 0} — множество всех пар циркуляров на плоскости;
02 = {(ci,C2) : с\ G 0,с'2 € 0} — множество всех пар циркуляров общего положения на плоскости;
02 = {(с\,С2) '-с\ G 0,С2 G © : mg(c]) = mg(c2)} — множество всех пар изоморфных циркуляров на плоскости;
05(с*) = {с : Рг2(с*) Ç с С с*} — множество монотонных подциркуляров циркуляра с*;
0й(с*) = {с: с = /?(с*,е),£ > 0} — множество всех базовых циркуляров циркуляра с*;
®5(ci,C2) = {(c']ic'2) : с\ G ®s(c\),c'2 G 05(с2)} — все нары монотонных подциркуляров пары (с\,с2) на плоскости;
®\с1,с2) = {{с\,с,2):с\е&\сх),с'2е(д\с2):т§{с\)^тК{с'2)} - множество монотонных изоморфных подциркуляров пары циркуляров (С1,С2) на плоскости;
®В(сис2) = {(с;,4) : с', е е &в(с2) : т^с',) ~ т8{с'2)} - множе-
ство пар изоморфных базовых циркуляров пары циркуляров (с\,с2) на плоскости;
Тегт(с°) — множество терминальных ветвей циркуляра с0.
V, vo, VI — вершины графа С — (У,Е);
Введение
Диссертационная работа посвящена исследованию и разработке математических методов сегментации многоугольников для задачи сравнения формы. Вводится аппарат математической морфологии на множестве циркуляров — так называемая, циркулярная морфология. Для пар многоугольников на основе циркулярной морфологии предлагаются меры для их сравнения.
Предмет исследования
Термин сегментация применительно к изображениям используется в двух смыслах, причём в обоих случаях это разделение целого на составные (пересекающиеся или не пересекающиеся) части в соответствии с содержательными критериями.
В первом значении сегментация изображения понимается как выделение объекта интереса. Это разбиение всего изображения на отдельные фрагменты, соответствующие объектам или фону. Такое выделение осуществляется по цвету, текстуре, краю, низкочастотной или высокочастотной составляющей изображения. Для этого используется большой набор методов обработки изображений: точечные, пространственные, геометрические, алгебраические преобразования, фильтры, методы выделения краёв, спектральные разложения по различным системам базисных функций. Результатом сегментации является определение некоторых подмножеств изображения, которые содержательно соответствуют представленным на изображении объектам. Критерии такой сегментации обычно носят эвристический характер, выбираются в соответствии
с конкретными задачами. Известные подходы, в частности, описаны в работах Ю.В.Визильтера [6, 7, 8], П.П.Кольцова [13]. Известна модель сегментации Мамфорда-Шаха [26]. Такую сегментацию естественно называть сегментацией объектов. В диссертации вопросы сегментации объектов не рассматриваются. Тема диссертации относится к сегментации формы.
В диссертации рассматривается сегментация выделенных в изображении объектов для сравнения и классификации этих объектов по их форме. Поскольку в основе общепринятых "человеческих"способов классификации формы лежит сравнение с некими эталонными объектами, форма которых считается известной (например, сходство с геометрическими фигурами), сегментация в этом случае имеет целью декомпозицию объекта сложной формы на составляющие его элементы, форма которых имеет более простой вид и соответственно более простое описание. Такая декомпозиция объекта на части в интересах анализа и преобразования формы объекта называется в диссертации сегментацией формы.
Содержательно задача сегментации формы ставится следующим образом. Дано описание объекта в виде множества точек на плоскости. Нужно разбить это множество на подмножества (выделить элементы), которые имеют простое описание, позволяющее легко классифицировать форму этих элементов, и далее на основе этого производить анализ и (или) преобразование всего объекта в целом.
Такая постановка задачи сегментации формы существенно зависит от принятого способа описания формы объекта. Известны различные способы такого описания:
• неявный, с помощью неравенства через функцию двух переменных, задающих координаты точки на картинной плоскости;
• бинарным растровым изображением в виде некоторого множества точек на целочисленной решётке;
• непрерывной границей объекта;
• медиальным представлением объекта в виде срединных осей (скелета) и радиальной функции, заданной в точках скелета. Такое описание называется скелетным или медиальным.
Скелетное представление плоской фигуры в виде множества серединных осей, образованных центрами окружностей, вписанных в фигуру, представляет собой мощный инструмент анализа структуры формы объектов.
Для описания формы широко используются многоугольные фигуры. С одной стороны, они имеют достаточно простое и универсальное описание. А с другой - многоугольными фигурами можно приблизить любые, сколь угодно сложные, фигуры, представленные неявными способами, бинарными изображениями, либо описанием границы. Скелетное представление многоугольных фигур имеет простое аналитическое описание в виде геометрических графов с рёбрами, являющимися отрезками прямых линий и квадратичных парабол.
Задача сегментации формы при скелетном описании формы сводится к сегментации соответствующего скелета. Сегментация скелета - это разбиение скелета на составляющие части.
Предметом диссертации являются вопросы сегментации формы, основанные на скелетном представлении фигур: постановка задач, методы и алгоритмы, критерии качества такой сегментации.
Цель работы
Разработка эффективных методов скелетной сегментации формы многоугольных фигур, основанных на математически корректных моделях, имеющих формальные показатели качества сегментации и позволяющих сравнивать и классифицировать объекты по форме.
Подход
Подход к достижению указанных целей основан на понятии срединной оси фигуры. Понятие срединной оси плоской фигуры (или скелета) было впервые введено в конце 1960-х годов Blum [33]. Он показал, что медиальное представление объектов (от англ. medial representation), присутствующих на двумерных изображениях, является эффективным способом описания их геометрической структуры. По сравнению с традиционным представлением формы медиальное представление является более информативным, оно отражает как общую структуру объекта, так и более детальную структуру его элементов.
Скелет плоской фигуры представляет собой множество центров максимальных вписанных в фигуру окружностей. Внешне скелет выглядит как плоский граф. Топологические свойства этого графа отражают общую структуру исходного объекта. Поэтому скелетное представление хорошо подходит для интегрального анализа структуры объекта и может служить основой для построения морфологических разбиений фигур.
Актуальность
Скелет является дескриптором формы. Скелетное представление дает полное описание фигуры, то есть по нему можно полностью восстановить фигуру. Такое описание избыточно и не подходит для решения задачи классификации.
Существующие методы сегментации, в том числе методы, использующие скелетное представление, основываются на эвристических правилах. Для оценки качества сегментации используются экспертные критерии на базе визуальных субъективных оценок. Это не позволяет оптимизировать сегментацию формы, а также сравнивать между собой различные методы сегментации.
Таким образом, с одной стороны, скелетное представление формы открывает принципиальную возможность построения и использования скелетной сегментации при сравнении и классификации формы. Разработанные в последнее время методы описания формы дискретных изображений в виде непрерывного скелетного представления многоугольных фигур (Местецкий [15], Рейер [17], Семёнов [18]) позволяют использовать скелетное представление для анализа и распознавания изображений. С другой стороны, известные методы сегментации формы основываются на эвристических правилах, не имеют формальных критериев качества сегментации и не приспособлены для решения задач сравнения формы объектов.
Итак, скелет является избыточным дескриптором формы, содержащим в себе всю информацию об объекте. Необходимо минимизировать размерность скелетного представления, сохраняя при этом достаточную полноту описания — задача генерации скелетных дескрипторов. Построить скелетную сегментацию меньшей размерности можно различными способами. Отсюда возникает необходимость математической формализации критерия качества скелетной сегментации. Задача сравнения и классификации формы фигуры порождает другой тип критериев минимизации скелетного описания: скелетная сегментация должна быть достаточно полной для решения задачи сравнения формы. Это критерий отделимости классов, то есть задача селекции скелетных
дескрипторов. Неоднозначность выбора скелетной сегментации в данном случае порождает проблему определения качества скелетной сегментации для пар фигур.
Этим обосновывается актуальность темы, направленной на исследование и разработку новых методов сегментации формы, которые позволили бы преодолеть указанные недостатки известных методов.
Научная задача
Разработка новых методов сегментации формы, основанных на скелетном представлении и
