Многолистная фигура и ее медиальные дескрипторы тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Мехедов, Иван Сергеевич

• Мехедов, Иван Сергеевич
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Мехедов, Иван Сергеевич

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ной фигуры

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

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

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

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

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

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

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

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

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

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

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

Заключение

Обозначения

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

Введение диссертации (часть автореферата) на тему «Многолистная фигура и ее медиальные дескрипторы»

Введение

Актуальность темы. Понятие срединной оси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 посвящены вопросам вычисления медиальных дескрипторов многоугольной многолистной фигуры. Показано сведение задачи вычисления срединной оси, диаграммы Вороного, медиальной и радиальной функций к задаче построения графа Делоне многоугольной многолистной фигуры, в основе которой лежит бинарная операция склейки графов Делоне смежных многоугольных фигуры. Дана оценка вычислительной сложности предложенных алгоритмов.

В третье главе показано применение разработанного алгоритма вычисления медиальной функции многоугольной многолистной фигуры в решении актуальных задач преобразования геометрического представления пространственных данных в геоинформационных системах. Класс таких задач описан в разделе 3.1. Разделы 3.2-3.4 посвящены постановке и решению трех задач этого класса — свертки площадных объектов в линейные, преобразованию общего полигонального представления улично-дорожной сети к линейному, преобразованию общего полигонального представления улично-дорожной сети к содержательному полигональному представлению. Раздел 3.5 содержит краткое описание вычислительного эксперимента.

Личный вклад автора в работу. Разделы 1.1 первой главы и 2.1 второй главы содержат известные результаты, включенные в работу для понимания основного ее содержания. Разделы 1.2, 1.3 первой главы

и разделы 2.2 и 2.3 второй главы содержат новые научные результаты, полученные автором самостоятельно. Что касается результатов третьей, «практической» главы, то разделы 3.1 и 3.2 содержат общее описание проблематики различного геометрического представления пространственных данных в геоинформатике, разделы 3.3 и 3.4 содержат новые полученные автором результаты.

Заключение диссертации по теме «Теоретические основы информатики», Мехедов, Иван Сергеевич

Заключение

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

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

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

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

Направление дальнейших исследований

• Алгоритм построения графа Делоне многоугольной многолистной фигуры для произвольного разбиения. При рассмотрении этого алгоритма во второй главе на множество многоугольных фигур разбиения V многоугольной многолистной фигуры ф накладывались ограничение в том, что для любых двух фигур Р\,Р2 £ V в их пересечении содержится не более одной ломаной (|Рг)! ^ !)• Кроме того, если разбиение V содержит три и более многоугольной фигуры, то на множество V накладывались ограничения: допущение о единственности склейки и о независимости склейки). Тем не менее, данные ограничения могут быть сняты при определенной модификации разработанных алгоритмов.

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

• Алгоритм построения срединной оси произвольной лоскутной поверхности. В случае если проекция 7гг лоскутной поверхности П на плоскость является изометрической, имеет смысл вычислять срединную ось лоскутной поверхности посредством вычисления срединной оси многолистной фигуры $ = 7тг(П) относительно некоторого разбиения Т такого, что О) = Л4($, Т). В дальнейшей работе планируется разработка такого алгоритма.

• На рис. 3.14 представлено изображение ладони человека с ок-клюзиями — пальцы частично перекрывают друг друга. Данная фигура, расположенная в плоскости, не является ни плоской, ни многолистной, однако идеи, изложенные в работе, вероятно, можно с некоторыми модификациями применить к подобной фигуре при определении понятия самой фигуры и ее медиальных дескрипторов. Распространение идеи медиального представления многолистной фигуры на объекты такого рода позволит решить задачу восстановления серединных осей трехмерного объекта по стереопаре его плоских проекций. Это может быть использовано при решении задач распознавания поз и жестов в системах компьютерного зрения.

Рис. 3.14. Изображение ладони с окклюзиями.

Обозначения

Условные обозначения в схемах работы алгоритмов построения графа Делоне | сзйт-сегментоднойизфигур Г~] удаленный сайт-сегмент сайт-сегмент другой фигуры ¡§3 удаленный сайт-сегмент общий сайт- сегмент двух фигур удаленный общий сайт-сегмент

I I новый добавленный сайт-сегмент

3 сайт-точка одной из фигур

С ) удаленный сайт-точка

Щ общий сайт-точка двух фигур ^ удаленный общий сайт-точка ф сайт-точка другой фигуры удаленный сайт-точка

О новый добавленный сайт-точка ребро графа смежности удаленное или добавленное ребро графа Делоне

Список литературы диссертационного исследования кандидат физико-математических наук Мехедов, Иван Сергеевич, 2011 год

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

1. Ahlfors L. V., Sario L. Riemannian surfaces. — Princeton, N. J.: Princeton University Press, 1960. — Chapter I.

2. Aichholzer 0., Aurenhammer F. Straight Skeletons for General Polygonal Figures in the Plane // Lecture Notes in Computer Science. — SpringerVerlag, 1996.-Vol. 1090.-pp. 117-126.

/

3. Aurenhammer F., Klein R. Voronoi diagrams // In: J. Sack, J. Urrutia (Eds.), Handbook of Computational Geometry. — Elsevier, Amsterdam, 2000.-pp. 201-290.

4. Bruce J.W., Giblin P.J. and Gibson C.G. Symmetry sets // Proc. Roy. Soc. Edinburgh, 1983.-Vol. lOlA.-pp. 163-186.

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

6. Chazal F., Soufflet R. Stability and finiteness properties of Medial Axis and Skeleton // Journal of Dynamic and Control Systems, 2004. — Vol. 10, № 2.-pp. 149-170.

7. Chin F., Snoeyink J., Wang C.A. Finding the Medial Axis of a Simple Polygon in Linear Time // Discrete Comput Geom, 1999.—Vol. 21.— p.405-420.

8. Choi H.I., Choi S.W. and Moon H.P. Mathematical Theory of Medial Axis. Transform // Pacific Journal of Mathematics, 1997.—Vol. 181, № l.-pp. 57-88.

9. Cornea N., Silver D., Min P. Curve-skeleton properties, applications

and algorithms // IEEE Transactions on Visualization and Computer Graphics, 2007.-Vol. 13, No 3.-pp. 530-548.

10. Haunert J.-H., Sester M. Area Collapse and Road Centerlines based on Straight Skeletons // Geoinformatica, 2008.-Vol. 12, №. 2-pp. 169191.

11. Shekhar S., Xiong H. (Eds). Encyclopedia of GIS. - Springer, 2008.1370 p.

12. Gold C. The Dual is the Context: Spatial Structures for GIS. //In Proc. Int. Symp. on Voronoi Diagrams in Science and Engeneering, Quebec, Canada, IEEE-CS, 2010.-pp. 3-12.

13. Gursoy H.N. Shape Interrogation by Medial Axis Transform for Automated Analysis // PhD thesis, Massachusetts Institite of Technology, 1989.

14. Eppstein D., Mumford E. Self-overlapping curves revisited // In SODA'09: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009. —pp. 160—169.

15. Fortune S. A sweepline algorithm for Voronoi diagrams // Algorithmica, 1987. 2. -pp. 153-174.

16. Kirkpatrick D.G. Efficient computation of continuous skeletons //In Proceedings of the 20th Annual IEEE Symposium on FOCS, 1979. -pp. 18-27.

17. Klein R., Lingas A. Fast skeleton construction //In Proc. 3rd Europ. Symp. on Alg. (ESA'95), 1995.

18. Lee D. Medial axis transform of a planar shape // IEEE Trans. Pat. Anal. Math. Int., 1982.-PAMI-4 (4).-pp. 363-369.

19. Lee D.T., Schachter B.J. Two algorithms for constructing a Delaunay triangulation // Int. J. Comput. Inf. Sci., 1980.9.-pp. 219-242.

20. Lieutier A. Any open bounded subset of has the same homotopy type as its medial axis // Solid Modeling Theory and Applications, 2004. — Vol. 36, № 11. - pp. 1029-1046.

21. Mather J.N. Distance From a Submanifold in Euclidean Space // Proceedings of Symposia in Pure Mathematics, 1983.—Vol. 40, N2 2.— pp. 199-216.

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

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

24. Mestetskiy L., Bakina I., Kurakin A. Hand geometry analysis by continous skeletons // Lecture Notes in Computer Science: Image Analysis and Recognition, Part II. — Springer-Verlag, 2011. — Vol. 6754. — pp. 279282.

25. Mestetskiy L.M. Fat curves and representation of planar figures // Computers and Graphics, 2000.-Vol 24 (1-2).-pp. 9-21.

26. Rausch T., Wolter F.E. and Sniehotta O. Computations of Medial Curves on Surfaces //In Welfen Laboratory Reports, Report No. 1, August 1996.

27. Roberts S.A, Brent Hall G., and B. Boots. Street Centerline Generation with an Approximated Area Voronoi Diagram //In P.F. Fisher (Ed.), Developments in Spatial Data Handling, 11th International Symposium on Spatial Data Handling, 2004. - pp. 435-446.

28. Sherbrooke E.C, Patrikalakis N.M., Wolter F.-E. Differential and Topological Properties of Medial Axis Transforms // Graphic Models and Image Processing, 1996.—Vol. 58, № 6.-pp. 574-592.

29. Siddiqi К., Pizer S. Medial Representations: Mathematics, Algorithms and Applications — Springer, 2008.

30. Srinivasan V., Nackman L.R., Tang J.-M., Meshkat S.N. Automatic mesh generation using the symmetric axis transform of polygonal domains // Proc. of the IEEE, 1992.-Vol. 80, № 9.-pp. 1485-1501.

31. On the Structure of Straight Skeleton // Lecture Notes In Computer Science, 2009.-Vol. 5730/2009. - p. 362-379.

32. Yap C.K. An 0(N log N) algorithm for the Voronoi diagram of the set of simple curve segments // Discrete Comput. Geom., 1987. — N2 2.— pp. 365-393.

33. Yomdin Y. On the Local Structure of a Generic Central Set // Compositio Mathematica, 1981.-Vol. 43, Ж 2.-pp. 225—238.

34. Wolter F.-E. Cut Locus and Medial Axis in Global Shape Interrogation and Representation, 1993. — Design Laboratory Memorandum 92-2, MIT, Department of Ocean Engineering, Cambridge, MA.

35. Делоне Б.Н. О пустом шаре // Известия АН СССР, 1934. —VII серия, Т. 6. - с. 793-800.

36. Иванов А.О., Тужилин А.А. Погруженные многоугольники и их диагональные триангуляции // Изв. РАН. Сер. матем., 2008.— Т. 72, № 1.-е. 67-98.

37. Лагно Д., Соболев А. Модифицированные алгоритмы Форчуна и Ли скелетизации многоугольной фигуры // Труды межд. конф. «Графикон-2001», 2001.

38. Местецкий Л.М. Непрерывный скелет бинарного растрового изображения //В сборнике докладов 8-й международной конференции по компьютерной графике и машинному зрению «Графикон'98», 1998.

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

фигуры, скелеты, циркуляры. - М.: ФИЗМАТЛИТ, 2009.-288 с.

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

41. Местецкий Л. М. Скелет многоугольной фигуры — представление плоским прямолинейным графом // Труды 20-й международной конференции по компьютерной графике и машинному зрению «Гра-фикон'2010». — СПб, ИТМО, 2010.-е. 222-229.

42. Местецкий Л.М., Рейер И.А. Непрерывное скелетное представление изображения с контролируемой точностью //В сборнике докладов 13-й международной конференции по компьютерной графике и машинному зрению «Графикон'2003». — М.: МАКС Пресс, 2003.— с. 246—249.

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

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

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

46. Мехедов И. С. Многолистная плоская фигура и ее срединная ось //

Известия вузов. Математика, 2011.—№ 12. —с. 42-52.

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

48. Мищенко М.С., Фоменко М.В. Курс дифференциальной геометрии и топологии. — М.: Факториал Пресс, 2000. — 448 с.

49. Новиков Ф.А. Дискретная математика для программистов.— СПб.: Питер, 2000.-304 с.

50. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. — М.:Мир, 1989.-478 с.

51. Скворцов A.B. Геоинформатика: Учеб. пособие. — Томск: Изд-во Том. ун-та, 2006.-336 с.

52. Скворцов A.B., Мирза Н.С. Алгоритмы построения и анализа триангуляции. — Томск: Изд-во Том. ун-та, 2006. — 168 с.

53. Федоров Р.К., Хмельнов А.Е., Бычков И.В. Об одном подходе к анализу топологии пространственно-распределенных данных с использованием логического вывода. // Вычислительные технологии, 2005.-Т. 10, № 1. — с. 116-130.

54. Интернет-страница продкута «ГИС Mappl» http ://www.mappl.ru/component

55. Интернет-страница ресурса «Единая государственная картографическая основа г. Москвы» http : //www. egko. ru/Map/index. html

56. Интернет-портал «Яндекс.Карты» http : //www. maps. yandex. ru