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

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

Мехедов Иван Сергеевич

Многолистная фигура и ее медиальные дескрипторы

Специальность 05.13.17-теоретические основы информатики

Автореферат

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

1 2 ННВ 2012

Москва 2011

005007359

Работа выполнена в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН.

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

Местецкий Леонид Моисеевич

Официальные оппоненты: доктор физико-математических наук,

член-корреспондент РАН Щешш Евгений Витальевич

кандидат физико-математических наук Вяткина Кира Вадимовна

Ведущая организация: Нижегородский государственный университет

им. Н.И. Лобачевского

Защита диссертации состоится «16» февраля 2012 г. в 15 часов на заседании диссертационного совета Д 002.017.02 в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН по адресу: 119333, Москва, ул.Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Вычислительный центр им. А. А. Дородницына РАН.

Автореферат разослан «29» декабря 2011 г.

Ученый секретарь диссертационного совета

Л

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

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

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

Рис. 1: Плоская фигура и ее срединная ось. Круг с центром в точке b и радиусов гь касается границы фигуры в двух точках.

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

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

1от англ. medial axis; в русскоязычной литературе зачастую срединная ось называется скелетом.

2Н. Blum. 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.

радиальной функции, а также обобщением понятия срединной оси на другие объекты, прежде всего — на п—мерное многообразие с краем, вложенное в Ш,1+к,к^ 0;

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

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

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

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

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

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

Рис. 2: Примеры многолистных фигур.

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

Рис. 3: Срединная ось многолистной фигуры: неформализованное представление.

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

Цель работы состоит в расширение теории медиального представления формы в части обобщения ее на многолистные фигуры.

Задачи, решаемые в диссертационной работе:

• Определение понятия многолистной фигуры;

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

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

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

Предлагаемый подход к решению этих задач основывается на следующей идее. Для того, чтобы многолистная плоская фигура имела естественную интерпретацию, в качестве границы предлагается рассматривать не произвольные замкнутые кривые, а только те, которые являются проекцией границы некоторого двумерного многообразия с краем на плоскость — так называемой порождающей поверхности (поскольку она «порождает» при проекции на плоскость многолист-пую фигуру). Кроме того, ограничения накладываются и на саму порождающую поверхность. Требуется, чтобы каждая ее точка имела окрестность, которую любая вертикальная прямая пересекает не более, чем в одной точке. При этом каждая точка срединной оси должна представлять собой центр круга, который касается границ проекции в двух или более точках и имеет гомеоморфный прообраз на порождающей поверхности (рис.4, слева). Идея вычисления медиальных дескрипторов основана на декомпозиции многоугольной многолистной фигуры на конечное множество обычных многоугольных фигур (рис.4, справа), построение их графов Делоне по отдельности и их сращение в граф Делоне многолистной фигуры, на основе которого вычисляются остальные медиальные дескрипторы.

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

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

Научная новизна. До сих пор в теории медиального представления формы рассматривались только п-мерные многообразия с краем, вложенные в Кп+А:, к ^ 0. В настоящей работа рассматривается двумерное многообразие с краем П, которое не вкладывается в К2 (п = 2, к = 0). При этом оказывается возможным при определенных условиях, наложенных наП, определить понятия и исследовать свойства медиальных дескрипторов погружения П в К2. Новыми результатами являются: определение многолистной фигуры, ее медиальных дескрипторов, алгоритмы вычисления медиальных дескрипторов многоугольной многолистной фигуры и их приложение к решению задач геоинформатики.

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

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

Результаты, выносимые на защиту.

1) Определение и основные свойства многолистной фигуры и ее медиальных дескрипторов: срединной оси, радиальной и медиальной функций, диаграммы Вороного, графа Делоне;

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

3) Алгоритмы преобразования геометрического представления пространственных данных в геоинформационных системах.

Апробация работы. Результаты работы докладывались на научных семинарах МГУ, СПбГУ, ВЦ РАН, а также Международных научных конференциях по компьютерной графике и машинному зрению «Графикон» (Москва, 2009г.; Санкт-Петербург, 2010 г.), Всероссийской научной конференции «Математические методы распознавания образов» (Суздаль, 2009 г), Международной научной конференции «Интеллектуализация обработки информации» (Пафос, Кипр, 2010 г.), Международной научной конференции «International Conference on Computational Scionco and Its Applications» (Фукуока, Япония, 2010 г.), Международной научной конференции «International Symposium on Voronoi Diagrams in Science and Engineering» (Квебек, Канада, 2010 г.), Всероссийской конференции «Электронные услуги и сервисы на основе пространственных данных» (Мытищи, Московская обл., 2010 г.).

Публикации по теме диссертации в изданиях списка ВАК: [1, 2]. Другие публикации по теме диссертации: [3, 4, 5, 6, 7]. Результаты включались в отчет по проекту РФИИ № 08-01-00670.

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

многолистной фигуры»), заключения, списка иллюстраций (45 иупктои), списка обозначений, списка литература (56 пунктов). Общий объем работы — 135 стр.

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

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

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

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

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

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

Лоскутом будем называть компактную поверхность, вложенную в К'', которую любая вертикальная прямая {(х,у,г),х = с\,у = с?} пересекает не более, чем в одной точке.

Лоскутной поверхностью4 будем называть такую компактную поверхность, вложенную в М3, каждая точка которой имеет окрестность, образ которой (при вложении в К3) является лоскутом.

Рассмотрим пару (F, С), где F - плоская фигура, а С = {h,..., 4} — конечное множество замкнутых кривых на плоскости, при этом каждая кривая может быть г.амопорсескающсйся, и любые две кривые из С могут иметь общие точки.

Определение 1.1. Упорядоченная пара$ = (F, С) называется многолистной фигурой, если существует лоскутная поверхность Г2 такая, что 7гг(П) = F и 7Гг(сК2) = С, где irz(x,y,z) = (х,у) — проекция лоскутной поверхности на плоскость.

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

Множество П будем называть порождающей поверхностью для 5, а фигуру 5 будем также обозначать 7rz(S~i).

Доказывается, что если il - лоскутная поверхность, то найдется конечное число лоскутов fii,..., таких, что любые два не имеют общих внутренних точек, иП= fli U... Ufln. Множество таких лоскутов будем называть разбиением лоскутной поверхности.

В работе определяется понятие разбиения многолистной фигуры на множество плоских фигур. Проекция всех лоскутов разбиения порождающей поверхности на плоскость даст некоторое разбиение многолистной фигуры. При этом, если два лоскута f2i и 0,2 разбиения лоскутной поверхности Г2 имеют в пересечении некоторое число общих жордановых дуг, то среди компонент связности пересечения F\ = Tr2(fii) и F2 = 7Г2(П2) тоже найдется это же число жордановых дуг. Такие плоские фигуры будем называть смежными. Множество жордановых дуг с пересечении F\ и F2 обозначим J(Fi, F2).

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

Определение 1.2. Будем говорить, что круг 0Г(х,£1,ых) лежит внутри многолистной фигуры $ относительно порождающей поверхности Q и точки wx

4Термшш лоскут и лоскутная поверхность являются авторскими переводами терминов terrain и generalized terrain, cooturtctbohho, встречающихся в англоязычной литературе и имеющих те же определения, что и данные хчг.п,.

на ней, если найдется множество С О такое, что:

1) П. С тгГ^ОДх));

2) сужение 7гг на Пх является гомеоморфизмом 7гг|пт : Ог(х);

3) шх = ПхПтг^^а;).

Далее определим понятия ближайшей граничной и срединной точки много-листной фигуры.

Пусть х 6 Р. Будем говорить, что круг Ог(х,П,их), лежащий внутри многолистной фигуры, является максимальным с центром в точке х относительно порождающей поверхности П и точки шх на ней, если пересечении 7г~1(Ог(х', Г2,шх)) и дО. не пусто.

Будем говорить, что точка у £ £ является ближайшей граничной точкой к точке х € Р многолистной фигуры 5 = (Р, С) относительно порождающей поверхности П и точки шх на ней, если я г1 (у) £ тг^1(Ог(х,С1,шх)).

Определение 1.3. Точка х € Р называется срединной точкой многолистной фигуры ^ относительно порождающей поверхности если существует точка шх 6 П такая, что х имеет, по крайней мере, две ближайшие граничные точки относительно порождающей поверхности П и точки и>х на ней.

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

Определение 1.4. Точка ш 6 П называется срединной точкой порождающей поверхности Г2 относительно погружения 7гг, если точка пг(и) является срединной точкой многолистной фигуры У = 7гг(П) относительно П.

Обозначим Мес11!1 (П) множество срединных точек порождающей поверхности Г2 относительно погружения тт2.

Теорема 1.1. является связным одномерным стратифицированным

многообразием, вложенным в Г2, либо состоит ровно из одной точки ш б П.

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

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

Определение 1.5. Срединной осью П) многолистной фигуры 5 относительно порождающей поверхности П называется погружение 7г2 : Мей^^О) —»• К2.

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

Рис. 5: Порождающая лоскутная поверхность 1), многолистная фигура ¡^ = 7Г2(П), множество срединных точек П, срединная ось П) многолистной фигуры У относительно П.

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

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

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

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

Определение 1.6. Срединной осью Л4(Т7) многолистной фигуры $ относительно разбиения Т называется срединная ось .М^, П) относительно какой-либо лоскутной поверхности Г2 из класса Пу если О.? 0.5

"'Кгли 5 — многолистная фигура и Т — се некоторой разбиение, то будем обозначать множество лоскутных

Срединная ось многолистной фигуры представляет собой геометрический граф на плоскости, у которого разрешены пересечения ребер. Этот граф будем называть медиальным графом и обозначать (7м(5, П) (относительно лоскутной поверхности) либо (относительно разбиения).

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

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

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

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

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

Доказывается критерий смежности сайтов относительно порождающей поверхности:

Теорема 1.3. Сайты а и Ъ, не являющиеся соседними, смежны тогда и

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

41у{а,Ь,й)

a

10 12 П Q

Рис. 6: Слева: многолистная многоугольная фигура ф из рис. 5; ее ячейки Вороного относительно лоскутной поверхности П (пронумерованы от 1 до 13); ее диаграмма Вороного (изображена жирными линиями); один из бисекторов диаграммы Вороного lv(a,b,Sl) сайтов а и Ь. Справа: лоскутная поверхность П из рис. 5; ее лоскуты Вороного (пронумерованы от 1 до 13); ее сеть Вороного (изображена жирными линиями); соответствующий lv(а, Ь, П) лоскутный бисектор А" (а, !>). Каждая ячейка Вороного и соответствующий ей лоскут Вороного обозначены одинаковым числом и цветом.

только тогда, когда существует круг Ог(х), касающийся этих двух сайтов, и существует лоскут С il, имеющий непустое пересечение с тс~1(а) и n~l(b), причем Or(x) = 7rz(f2iT).

Определение 1.7. Графом Делоне DG(S.р, Г2) многоугольной многолистной фигуры ф = 7гг(Г2) относительно порождающей поверхности П называется граф (V, f), у которого множество вершин V состоит из сайтов многоугольной многолистной фигуры, а множество ребер £ содержит все пары смежных либо соседних сайтов из V.

Во всех данных в этой главе определениях выражение «относительно порождающей поверхности» можно заменить равносильным — «относительно разбиения». Доказательство этого утверждения для каждого определения полностью аналогично доказательству теоремы 1.2.

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

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

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

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

найти все пары смежных сайтов ф. Уравнения сайтов и бисекторов позволяют вычислить значения радиальной функции на каждом ребре медиального графа, которое является бисектором диаграммы Вороного, образованного сайтами, не являющимися соседними. Таким образом, построение графа Делоне многоугольной многолистной фигуры позволяет вычислить все ее остальные медиальные дескрипторы, а сложность их вычисления определяется сложностью алгоритма вычисления графа Делоне и равна в худшем случае 0(ЛГ2 • где N — число

вершин ф.

В разделе 2.3 описан алгоритм вычисления ф.Р). Задача построения /}(7(ф, V) ставится следующим образом. Пусть ф — многоугольная многолистная фигуры и V = {Р1,...,Р/,} — ее некоторое разбиение. Требуется вычислить

г>с(ф,п

Если |Р| = 1, т.е. разбиение состоит ровно из одной многоугольной фигуры Р, то £>С(ф, 7>) = £>С(Р).

Случай, при котором \Р\ = 2 или V = {Рх, Р2}, описан в подразделах 2.3.1 и 2.3.2.

Определение 2.1. Назовем склейкой бинарную операцию над графами Делоне многоугольных фигур Р\ и Р2, результатом которой является граф Делоне £С(ф,7>): Вв{Р\) © Ов{Р2) = £>С(ф, {РЬР2}), где Ф - обозначение операции склейки.

Идея алгоритма состоит в том, чтобы построить по отдельности графы Делоне 00{Р\) и £>С(Р2) отдельных фигур разбиения, а затем определенным образом

6Л. М. Местсцкий. Скелетизация многоугольной многоевлзной фигуры на основе дерева смежности ее границы // Сибирский журнал вычислительной математики, 2006.— Т. 9, № 3. — с. 299-314.

срастить их в граф Делоне DG(ty,V). При этом значительная часть вершин и ребер графов Делоне DG(Pj) и DG(P2) войдут в DG(?ß,P), кроме того, появятся новые ребра и, возможно, вершины, не входящие в DG(P\) и DG(P2).

Обозначим <Si — множество сайтов Р\, ¿>2 ~ множество сайтов Р2, Sll2 — множество сайтов обеих фигур, образующих J(P\,P2), называемое линией склейки, S\2 — множество сайтов ф, £\ — множество ребер DG(Px), £2 — множество ребер DG{P2), £12 — множество ребер ф, iSj^ — множество сайтов Р\ и Л), не входящих в S12, S\2 — множество сайтов, не входящих в <Si U ¿>2, но входящих в <Si2, S'12 — множество сайтов, смежных сайтам из iSj~2 в -DG(Pi) или DG(P2), S{2 — подмножество ребер £\ U £■>, не входящих в £п, £\2 ~ подмножество ребер £\2, не входящих в £\ U £2; S¡2W назовем множеством сшиваемых сайтов, S^" = £12 \«S,f2t<' = US^ — множеством базовых сайтов, = £^£2^12 — множеством базовых ребер. Из равенств Su — «SiU^USJjV^ и ¿^12 = £\ U £2 U £12 \ £\2 видно, что задача вычисления DG(?ß, V) = (1S12, £12) сводится к вычислению множеств <S12, ¿>i2>£i2>

Алгоритм склейки графов Делоне смежных многоугольных фигур состоит из четырех шагов:

Построение объединенной границы Pj и Р2. На этом шаге вычисляются множества iS^ и на основе поиска пересечения отрезков границ фигур.

Очистка графов смежности. На этом шаге вычисляется £f2. Доказывается, что:

• В £¿2 входят те и только те ребра £\ U£2, которые соединяют вершины множества Syf с вершинами множества

• £\г — £п.

Формирование последовательности сшиваемых сайтов . На этом шаге формируется последовательность (Sj™'"', содержащие определенным образом упорядоченные сайты множества Sil"';

Сшивка графов смежности. Ha, этом шаге вычисляется Доказывается, что если е = (а, 6) 6 то а, Ь е ¿Jff1", т-е- новые ребра могут появиться только между сшиваемыми сайтами.

Сшивка графов смежности основана на парадигме «разделяй и властвуй», а сам алгоритм сшивки полностью аналогичен алгоритму итерационного слияния графов Делоне подмножеств сайтов многоугольной фигуры при построении графа Делоне многоугольной фигуры. При этом алгоритм сшивки применяется к последовательности сшиваемых сайтов БЦ™""'. Отличие заключается в проверке условия Делоне, которое формулируется как критерий смежности сайтов относительно разбиения:

Рис. 7: Две смежные многоугольные фигуры (рис. а); графы Делоне фигур, белыми кружочками отмечены сайты-точки первой фигуры, белыми квадратиками — сайты-сегменты первой фигуры, черными кружочками — сайты-точки второй фигуры, черными квадратиками — сайты-сегменты второй фигуры, смежные сайты в каждом из двух графов Делоне соединены ребрами (рис. 5); построение объединенной границы и очистка графов Делоне, новые добавленные сайты раскрашены в серый цвет, удаленные сайты заштрихованы, удаленные ребра изображены пунктиром (рис. в); сшивка графов Делоне (рис. г); -5>{2 = {«1, а2, а3, а4,а5, Ь1,Ъг, 63, 64, 65}, ¿>12 = {11,02,03,04,05,68,43,64},

с+ __Г,, ,, "1 с(1Ф __Г., ,, ,/! са „а а „а „а „а ,,« „Ь „Ь „Ь ,,Ь Л ../> 1

Оаешвед _ Г.. Л ,.Ь ,,!> СМ ,.Ь ,.Ь ,,1> Ь , ..а .,'1 ..а „о ,,а ..а „а ..а ..а ,, \

<->12 — \с1> °1| 61> 62> 4' 361 7' с2> «О, 8ц я2! 53> 54' 65! 6С> 67> 58> вИ ав/-

Теорема 2.1.

1) Пусть а 6 ¿>1 П ¿>12Ш,Ь € ¿>2 П ¿ГЦ"'. Тогда а и Ь являются смежными в ДС(ф.'Р) тогда и только тогда, когда существует круг Ог(х) с границей 0?(х) такой, что:

1.1) 0?(х) касается сайтов а и Ъ\

1.2) О^(х) не является пустой относительно ¿,|2;

1.3) Ог(х) = (От(х) П Рх) и (Ог(х) П Р2).

2) Пусть а, Ь € ¿>1 П^х™ или а, Ь 6 ¿>2 Лс^"'- Тогда а и Ь являются смежными в

тогда и только тогда, когда е = (а,Ь) 6 Е^' либо выполняются следующие условия:

2.1) Ог(х) касается сайтов а и Ь;

2.2) Ог(х) = (Ог(х) П РО и (Ог{х) П Р2).

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

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

• При линейном представлении улично-дорожная сеть описывается геометрическим графом, в котором вершины соответствуют перекресткам, а ребра — участкам дорог между перекрестками;

• При полигональном представлении улично-дорожная сеть описывается набором многоугольных фигур, каждая из которых соответствует произвольному участку проезжей части {«общее полигональное представление»)

или определенному в соответствии с некоторым правилом фрагменту проезжей части («содержательное полигональное представление»).

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

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

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

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

В разделе 3.3 описан алгоритм преобразование общего полигонального представления улично-дорожной сети к линейному, состоящий из двух шагов (рис.8):

1) Построение срединной оси ,М(ф,'Р) многоугольной многолистной фигуры ф относительно заданного разбиения V\

'Haunfxt J.-II., Scster M. Area Collapse and Road Centerlines based on Straight Skeletons // Geoinformat.ica, 2008.-Vol. 12, №.2-pp. 169-191.

Рис. 8: Участок улично-дорожной сети, содержащий дороги, мосты и тоннели, и его небольшой фрагмент (рис. а); спутниковое изображение этого фрагмента (Яндекс.Карты) (рис. б); общее полигональное представление этого фрагмента — многолистная фигура и ее разбиение (рис. е), темным цветом обозначен тоннель, светлым — мосты, промежуточным — дороги; скелеты отдельных многоугольных фигур в составе разбиения многолистной фигуры (рис. г); срединная ось многолистной фигуры — результат склейки скелетов смежных многоугольных фигур разбиения (рис. (?); медиальный граф См((9,'Р) после удаления несущественных ребер (рис. е).

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

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

Рис. 9: Общее полигональное представление улично-дорожной сети (слева) и базовая модель улично-дорожной сети — множество участков проезжей части, соответствующих перекресткам и перегонам между перекрестками (справа).

В разделе 3.5 описан вычислительный эксперимент, проведенный с использованием геоинформационной системы «Марр1» и пространственных данных (векторные картографические слои «Дороги», «Мосты», «Тоннели») Единой государственной картографической основы г. Москвы.

В заключении подводится краткий итог диссертации.

Список публикаций по теме диссертации

1. Мехедов И. С . Многолистная плоская фигура и се срединная ось // Известия вузов. Математика, 2011.—№ 12.— с. 42-53.

2. Mekhedov /., Mestetskiy L. Skeleton of a Multi-Ribbon Surface // Lecture Notes in Computer Science, 2010.— Vol. 6016, Part. I.— pp. 557-573.

3. Mekhedov I. S., Mestetskiy L. M. Fusion as a Novel Binary Operation on Medial Axes //In Proc. Int. Symp. on Voronoi Diagrams in Science and Engeneering, Quebec, Canada, IEEE-CS, 2010. - pp. 66-73.

4. Задонский Д., Макарова E., Мехедов И. Топологическая модель многоуровневой улично-дорожной сети на основе скелета //В сборнике докладов 19-й международной конференции по компьютерной графике и машинному зрению «Графикон'2010». - СПбГУ ИТМО, 2010. - с. 230-237.

5. Мехедов И. С . Многолистная многоугольная фигура и ее скелет // В сборнике докладов 8-й международной конференции «Интеллектуализация обработки информации» ИОИ-2010. - М.: МАКС Пресс, 2010. - с. 383-386.

6. Мехедов И. С. Поиск шаблонов перекрестков на цифровой векторной карте городской улично-дорожной сети. // В сборнике докладов 14-й Всероссийской конференции «Математические методы распознавания образов». — М.: МАКС Пресс, 2009.-с. 414-417.

7. Мехедов И. С., Козлов А. В. Модель улично-дорожной сети на основе скелета // В сборнике докладов 19-й международной конференции по компьютерной графике и машинному зрению «Графикон'2009». — М.: МАКС Пресс, 2009.-с. 356-359.

Подписано в печать:

28.12.2011

Заказ № 6464 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www. autoreferat. ru

61 12-1/516

Учреждение Российской академии наук Вычислительный центр им. А. А. Дородницына РАН

Многолистная фигура и ее медиальные дескрипторы

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

Специальность - 05.13.17 «Теоретические основы информатики»

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

профессор

Местецкий Леонид Моисеевич

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

Мехедов Иван Сергеевич

Москва 2011

Оглавление

Введение 4

1. Определение многолистной фигуры и ее медиальных дескрипторов 15

1.1 Плоская фигура и ее медиальные дескрипторы............................15

1.1.1 Плоская фигура, её срединная ось, радиальная функция и медиальная функции..................................................15

1.1.2 Диаграмма Вороного многоугольной фигуры ......................18

1.1.3 Граф Делоне многоугольной фигуры................................22

1.1.4 Связь между срединной осью, диаграммой Вороного и графом Делоне многоугольной фигуры ......................................24

1.2 Многолистная фигура, ее срединная ось, радиальная и медиальная функции..........................................................................26

1.2.1 Лоскутная поверхность................................................26

1.2.2 Многолистная плоская фигура...........................27

1.2.3 Разбиение многолистной фигуры ....................................29

1.2.4 Срединная ось многолистной фигуры................................32

1.2.5 Радиальная функция многолистой фигуры ........................43

1.2.6 Медиальная функция многол истой фигуры........................44

1.3 Многоугольная многолистная фигуры, ее диаграмма Вороного и граф Делоне............................................................................45

1.3.1 Диаграмма Вороного многоугольной многолистной фигуры ... 45

1.3.2 Граф Делоне многоугольной многолистной фигуры ..............56

1.3.3 Связь между срединной осью, диаграммой Вороного и графом Делоне многоугольной многолистной фигуры......................57

2. Вычисление медиальных дескрипторов многоугольной многолист-

ной фигуры 60

2.1 Вычисление медиальных дескрипторов плоской фигуры......... 60

2.2 Вычисление срединной оси, диаграммы Вороного, радиальной и медиальной функций многоугольной многолистной фигуры.......... 70

2.3 Построение графа Делоне многоугольной многолистной фигуры .... 72

2.3.1 Построение графа Делоне многоугольной многолистной фигуры относительно разбиения мощности 2 ................ 73

2.3.2 Построение графа Делоне многоугольной многолистной фигуры относительно разбиения произвольной мощности.........101

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

3.1 Преобразование геометрического представления пространственных данных в ГИС.................................106

3.2 Свертка площадных объектов в линейные . . ...............111

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

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

3.5 Вычислительный эксперимент и внедрение результатов .........124

Заключение 127

Обозначения 130

Список литературы 131

Введение

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

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

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

хот англ. medial axis; в русскоязычной литературе зачастую срединная ось называется скелетом, хотя скелет является более общим понятием, включающим в себя как срединную ось, так и прямолинейный скелет [2, 31], криволинейный скелет [9], а также скелет бинарного изображения [38].

Рис. 0.1. Плоская фигура и ее срединная ось. Круг с центром в точке Ь и радиусом гь касается границы фигуры в двух точках.

три направления исследований:

• теоретическое, связанное с изучением свойств медиальных дескрипторов, например, связности срединной оси, непрерывности и дифференцируемости радиальной функции, а также обобщением понятия срединной оси на другие объекты, прежде всего — нап— мерное многообразие с краем, вложенное в Мп+/с, к ^ 0;

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

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

Так, Блюм расширил понятие медиального представления формы на объекты трехмерных сцен. Позже понятие срединной оси было обобщено в работах [33] на объекты произвольной размерности («центральное множество»), [4] («множество симметрии»), а также [21]. Фундаментальным трудом по математическим основам медиального представления плоских фигур является работа [8]. Аналогичные результаты, но уже

для трехмерных объектов, были получены в [28]. Наконец, обобщающие теоретические результаты для объектов произвольной размерности были представлены в работе [34], а также в работе [6], кроме того было доказано, что в пространстве произвольной размерности объект и его срединная ось гомотопически эквивалентны [20]. Для поверхности (двумерного многообразия с краем, вложенного вМ3) также было определено и исследованы понятие срединной линии ([13, 26]).

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

Исторически первым алгоритмом построения диаграммы Вороного произвольного множества отрезков на плоскости был алгоритм Киркпра-трика (1979) [16]. Кроме того стоит отметить, прежде всего, алгоритмы [18, 19, 37, 30, 32, 15, 17, 7]. Алгоритм построения графа Делоне произ-

2диаграммы Вороного множества сторон и вершин фигуры, называемых сайтами

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

вольной многосвязной многоугольной фигуры за время 0(N • log N), где N — число вершин фигуры, был предложен JI. М. Местецким[40].

Разработанные алгоритмы находят широкое применение в анализе формы изображений ([42]), компьютерной графике и визуализации ([25]), биометрических технологиях ([24]), геоинформатике ([12, 43, 47]).

Существует класс прикладных задач, например, некоторые задачи геоинформатики [44], в котором исходные данные представлены не обычными плоскими фигурами, а фигурами, в которых ограничивающие кривые могут иметь самопересечения, а также пересекаться друг с другом (рис. 0.2). Такие фигуры будем называть многолистными фигурами.

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

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

Рис. 0.2. Примеры многолистных фигур.

ление.

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

Цель работы состоит в расширение теории медиального представления формы в части обобщения ее на многолистные фигуры.

Задачи, решаемые в диссертационной работе:

• Определение понятия многолистной фигуры;

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

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

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

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

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

Методика исследований. Решение поставленных задач основывается на использовании результатов следующих научных и инженерно-

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

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

Научная новизна. До сих пор в теории медиального представления формы рассматривались только п-мерные многообразия с краем, вложенные в Мп+/с, к ^ 0. В настоящей работе рассматривается двумерное многообразие с краем Г2, которое не вкладывается в!2 (п = 2, к = 0). При этом оказывается возможным при определенных условиях, наложенных на П, определить понятия и исследовать свойства медиальных дескрипторов погружения О, в М2. Новыми результатами являются: определение многолистной фигуры, ее медиальных дескрипторов, алгоритмы вычисления медиальных дескрипторов многоугольной многолистной фигуры и их приложение к решению задач геоинформатики.

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

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

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

Апробация работы. Результаты работы докладывались на научных семинарах МГУ, СПбГУ, ВЦ РАН, а также Международных научных конференциях по компьютерной графике и машинному зрению «Графикон» (Москва, 2009г.; Санкт-Петербург, 2010 г.), Всероссийской научной конференции «Математические методы распознавания образов» (Суздаль, 2009 г), Международной научной конференции «Интеллектуализация обработки информации» (Пафос, Кипр, 2010 г.), Международной научной конференции «International Conference on Computational Science and Its Applications» (Фукуока, Япония, 2010 г.), Международной научной конференции «International Symposium on Voronoi Diagrams in Science and Engineering» (Квебек, Канада, 2010 г.), Всероссийской кон-

ференции «Электронные услуги и сервисы на основе пространственных данных» (Мытищи, Московская обл., 2010 г.).

Публикации по теме диссертации в изданиях списка ВАК: [46, 22]. Другие публикации по теме диссертации: [23, 44, 45, 47, 43]. Результаты включались в отчеты по проектам РФИИ № 08-01-00670 и № 11-01-00783.

Структура и объем работы. Работа состоит из оглавления, введения, трех глав — теоретической («Определение многолистной фигуры и ее медиальных дескрипторов»), алгоритмической («Вычисление медиальных дескрипторов многоугольной многолистной фигуры») и прикладной («Решение некоторых прикладных задач на основе вычисления медиальной функции многоугольной многолистной фигуры»), заключения, списка литература (56 пунктов).

Краткое содержание работы по главам.

Первая глава разделена на три раздела. В разделе 1.1 приводятся известные понятия плоской фигуры и ее медиальных дескрипторов — срединной оси, радиальной и медиальной функций, диаграммы Вороного и графа Делоне (последние два дескриптора — только для многоугольных фигур). В разделе 1.2 вводятся два главных понятия диссертационной работы — многолистная плоская фигура и ее срединная ось. Многолистная плоская фигура является обобщением обычной плоской фигуры на случай, когда ограничивающие кривые могут иметь самопересечения и, кроме того, пересекаться друг с другом. Понятия срединной оси, радиальной и медиальной функций плоской фигуры также обобщаются на случай многолистной плоской фигуры. В разделе 1.3 рассматривается особый класс многолистных фигур — многоуголь-

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

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