Функционально-воксельное моделирование при построении геометрического скелета

М.А. Локтев,

н. с., лаб.№18, Loktevrus@gmail.com,
А.В. Толок,

зав., лаб.№18, atol@ipu.ru,

ИПУ РАН, г. Москва

В работе представлен графический способ выделения геометрической конструкции скелета на основе функционально-воксельного моделирования (ФВМ). Замкнутый контур представляется в аналитическом виде с помощью математического аппарата R-функций (RFM). Заполнение графической информацией функционального пространства приведет к получению рельефа поверхности функции, выраженный прямолинейным скелетом или диаграммой Вороного.

 

This paper presents the graphical method for forming the geometric skeleton based on functional-voxel modeling (FVM). Closed loop is presented in analytical form using the mathematical apparatus of R-functions (RFM). Filling the graphic information of the function space will lead to the formation of surface relief of function expressed by straight skeleton or the Voronoi diagram.

Введение

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

В работе [1] подробно описывается принцип вычисления локальных геометрических характеристик и построения на их основе базовых М-образов ФВМ. Для этого линейно аппроксимируется поверхность выбранной функции w1, где каждой точке пространства сцены соответствует уравнение плоскости Aix+Biy+Ciw+Di=0. Повысив размерность нормали к площадке на одно измерение, получим уравнение Aix+Biy+Ciw+Dit=0. В результате имеем четыре локальных геометрических характеристики, т.е. компоненты нормали (Ai, Bi, Ci, Di) для каждой из точек функциональной области w1 [1]. Воксельное представление ФВМ-модели предполагает монохромное отображение для каждой локальной характеристики, которую можно представить нормированием и приведением в соответствие значению градации цветовой палитры P в диапазоне [0, 255]. Порождение М-образа Сх осуществляется с помощью двухкомпонентного нормирования вектора нормали в плоскости xOy:

                                                                                (1)

 

            

Рис. 1 - Порожденные М-образы ФВМ-модели

                                                               (2)

 

 

где f1 и f2 – функции, определяющие исходные геометрические объекты. В системе R-функций (2) особое место занимает коэффициент α, принимающий значения -1<α1  и определяющий способ заполнения функционального пространства.

Рассмотрим различные способы заполнения функционального пространства на рисунке 2 представлен сложный невыпуклый контур, описанный с помощью последовательности R-функциональных операций. При α=0 система R-функций приобретает частный случай и поведение рельефа функции отвечает квадратичному закону (рис. 2а). Квадратичный случай (рис. 2а) позволяет получить единственный экстремум на положительной области контура.  Увеличение коэффициента приводит к появлению не дифференцируемых точек на положительной области, а на самом рельефе начинают проявляться очертания прямолинейного скелета. (рис. 2б). Помимо этого, сам способ заполнения функционального пространства начинает стремится к линейному закону, что характерно видно, когда α приближается к единице (рис. 2в). А в случае α=1 система R-функций (2) приобретает другой частный случай:

                                                                          (3)

 

Заполнение функционального пространства на М-образе, полученном на основе R-операций системы (3), отвечает линейному закону (рис. 2г) Данный образ представляет наибольший интерес, поскольку ребра R-функции являются прямолинейным скелетом.

                  

                                           а)                                                               б)                                                              в)                                                              г)

Рис. 2 - Способы заполнения функционального пространства

Само понятие прямолинейного скелета было предложено в работе [4], построение которого происходит в результате параллельного движения всех ребер с постоянной скоростью.  Один из самых распространённых способов построения прямолинейного скелета основывается на движении всех ребер с постоянной скоростью параллельно самим себе. Сжатие вершин многоугольника, приводит к объединению угловых бисекторов, определяющий прямолинейный скелет. Реализация одного из таких алгоритмов [5] приводится на рисунке 3а, на котором представлен прямолинейный скелет рассмотренного ранее контура.

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

             13

                                                                                             а)                                                                                               б)

Рис. 3 - Прямолинейный скелет на основе алгоритма [5] и программное выделение скелета на М-образе

Помимо этого, использование ФВМ позволяет строить диаграмму Вороного, являющаяся разбиением плоскости для конечного множества точек, при котором каждая область разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества. Точки представляют собой окружности с минимальным радиусом. При использование линейной системы R-функций (3) получаем М-образы, которые представляют собой диаграмму Вороного для конечного числа точек (рис. 4). Геометрически такое представление можно объяснить переходом в повышенное пространство. Каждая точка, описанная окружностью в повышенном пространстве, представляет собой гиперболоид. В результате соседние гиперболоиды при пересечении образуются линии, и при проецировании этих линий на плоскость, образуется диаграмма Вороного.

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

           

                                                                                                     а)                                                                       б)

Рис. 4 - Диаграмма Вороного для 10 точек на основе М-образов

Количество точек заданного множества может быть ограничено только габаритным размером функционального пространства, так для массива 1000х1000 без труда строится диаграмма Вороного на 200 (рис. 5а) и 1000 точек (рис. 5б).

       

 а) 200 точек                                                         б) 1000 точек

Рис. 5. Диаграмма Вороного для различного числа точек

Заключение

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

Литература

1.  Толок А.В. Функционально-воксельный метод в компьютерном моделировании. – Москва.: Физматлит, 2016. – 105 с.

2.  Рвачев В.Л. Теория R - функций и некоторые ее приложения. - Киев: Наукова думка, 1982. - 552 с.

3.  Локтев М.А., Толок А.В. Метод функциональной вокселизации полигональных объектов на основе математического аппарата R-функций // Прикладная информатика. 2016. Т. 11, № 1 (61). С. 127-134.

4.  Aichholzer O. et al. A novel type of skeleton for polygons. – Springer Berlin Heidelberg, 1996. – С. 752-761.

5.  Felkel, P. Straight skeleton implementation / P. Felkel, S. Obdrzalek // Proceedings of spring conference on computer graphics. – Budmerice, Slovakia. – 1998 – P. 210-218.

6.  Bhattacharya, P. Roadmap-based path planning-Using the Voronoi diagram for a clearance-based shortest path / P. Bhattacharya, M. L. Gavrilova // IEEE Robotics & Automation Magazine. – 2008. – Vol. 15. – №. 2. – P. 58-66.