ВВЕДЕНИЕ

Рассматриваемый в статье подход для построения прямолинейного скелета является продолжением целого цикла исследований, проводимых проф. Толоком А.В. Он посвящен применению метода функционально-воксельного моделирования (ФВМ) [10] в решении прикладных задач. При этом, рассмотрению подлежат такие задачи как поиск пути с препятствиями [1], задачи математического моделирования [2], задачи на вычисление интегральных значений объектов сложной геометрии [3], решение задач математического программирования [4] и т.п. Основой метода ФВМ является принцип организации символьно-графической информации, сочетающей аналитическую форму описания многомерной модели с воксельным представлением ее локальных геометрических характеристик. Такой подход позволяет получать для исследования дифференциальные и интегральные характеристики в точках функциональной многомерной области в компьютерном представлении.

Метод анализа формы плоского объекта на основе построения его геометрического скелета широко применяется в обработке изображений, распознавании образов, геометрическом моделировании и визуализации [5]. Геометрический скелет фигуры связан с такими понятиями как срединная ось и прямолинейный скелет. Срединная ось была предложена в работе Гарри Блюма (Harry Blum) [6], как способ эффективного описания геометрической структуры объекта. Построение срединных осей сводится к представлению множества внутренних точек фигуры, каждая из которых имеет, по меньшей мере, две ближайшие граничные точки (рис.1а). Каждая точка срединной оси фигуры является центром вписанного в фигуру круга, т.е. круга, все внутренние точки которого лежат внутри фигуры.

Понятие прямолинейного скелета было предложено в работах Освина Айхгольцера (Oswin Aichholzer) и Франца Ауренхаммера (Franz Aurenhammer) [8,9], построение которого происходит в результате параллельного движения всех ребер с постоянной скоростью (рис.1б).

 

1.  Использование м-образов

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

В работе [10] подробно описан принцип вычисления локальных геометрических характеристик рельефа. Для этого линейно аппроксимируется поверхность выбранной функции w₁, где каждой точке пространства сцены соответствует уравнение плоскости A_ix+B_iy+C_iw+D_i=0. Повысив размерность нормали к площадке на одно измерение, получим уравнение A_ix+B_iy+C_iw+D_it=0. В результате имеем четыре локальных геометрических характеристики, т.е. компоненты нормали (A_i, B_i, C_i, D_i) для каждой из точек функциональной области w₁ [10].

 

а) Срединная ось                      б) Прямолинейный скелет

Рисунок 1: Геометрические скелеты невыпуклого контура [7]

 

Рисунок 2: Порожденные М-образы

 

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

Рассмотрим возможность порождения образа С_х как результат двухкомпонентного нормирования вектора нормали в плоскости xOy:

(1)

где P – градация интенсивности тона палитры цвета, А и В – коэффициенты касательной плоскости в точке поверхности.

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

2.  Способ аналитического описания контура

Для аналитического построения замкнутого контура сложной формы в методе ФВМ используется математический аппарат R-функционального моделирования (RFM). Фундаментальные основы этого направления были заложены В.Л Рвачевым в трудах [11], в которых R-функции были выделены в отдельный класс теоретико-множественных операций над функциями-предикатами.  Теория R-функций позволила решать обратную задачу аналитической геометрии: построение уравнения для заданного геометрического объекта[12]. Это открывает возможность создавать сложные геометрические объекты аналитического описания, с сохранением главного условия: ноль на границе, положительные значения внутри границ объекта, а отрицательные снаружи [11].

Применение RFM позволяет строить и комбинировать сложные функционально-воксельные геометрические модели [13]. Наибольшее распространение в аналитическом моделировании получила α -система R-функций, состоящая из трех уравнений:

 

(2)

 

где f₁ и f₂ – функции-предикаты, в нашем случае определяющие исходные геометрические объекты. При этом стоит отметить, что в  α -системе особое место занимает коэффициент α, принимающий значения -1<α1  и влияющий на способ формирования функционального пространства. При  α=0 α -система приобретает частный случай, при этом поведение формируемого рельефа функции отвечает квадратичному закону (рис. 3).

 

 

На рисунке 3 приведён пример описания контура по заданным точкам методом, предложенным в работах В.Л. Рвачёва [11]  и доработанного Локтевым М.А. в работе [13] применительно к автоматизированному подходу для решения такой задачи.

На первом шаге аналитического представления фигуры необходимо выделить сегменты выпуклого контура (рис. 3.2а). В результате пересечения полуплоскостей, полученных на основе нормального уравнения прямой, проходящей через точки  и :

,

формируется функциональная область сегментов выпуклого контура :

(3)

Остальные отрезки образуют три подконтура (рис. 4б), каждый из которых будет описывать свою функциональную область ,  и:

(4)

  

а)                                                         б)

 

Рисунок 4: Функциональные подобласти выпуклых сегментов (а) и внутренних подконтуров (б), формирующие невыпуклый контур

 

Конечное аналитическое выражение контура может быть представлено как пересечение выпуклой области (3) с отрицательными областями внутренних подконтуров:

(5)

Применяя правила алгебры логики, из уравнения (2) следует что отрицание функциональной области приводит к смене операции пересечения на объединения, таким образом уравнения из (4) могут быть представлены в следующем виде:

(6)

Подставляя получившиеся значения из (6), в общее аналитическое выражение контура (5), получаем описание функциональной области  (рис.), выраженное через чередование теоретико-множественных операций объединения и пересечения:

(7)

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

 

а)                                                                  б)

Рисунок 5: Представление функции замкнутого контура, описанного аналитически: а) графическое, б) М-образ С_х

 

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

3.  Способ компьютерно-графического определения точек скелета

Способ формирования линейного скелета на основе R-функционального описания контура уже был предложен в работах [14-15]. Авторы представляют способ получения R-функции для замкнутого не выпуклого контура, с помощью набора полупространств, выраженных в неявном виде. Для получения линейного скелета выделяются ребра, определяющие пересечение полупространств, определяемых границами контура.  Полученные ребра проецируются на плоскость многоугольника, т.е. по сути, определяются не дифференцируемые точки R-функции. Полученная при этом поверхность не имеет четко выраженных хребтов и лощин, поэтому в работах [14-15] применяется конечно-разностная аппроксимация Лапласа для выделения ребер скелета.

 

а)                                 б)

Рисунок 6: Построение прямолинейного скелета[16]

 

Очевидно, что визуализация функционально-воксельного пространства на рисунке 5 определяет зрительно единственную не дифференцируемую точку, а рельеф показанного М-образа не способен выделить геометрическую конструкцию скелета. Для решения поставленной задачи достаточно увеличить коэффициент α для управления рельефом поверхности и изображением М-образа, причем визуальные рельефные изменения поверхности наблюдаются только при значительном увеличении α (α>0.5).  На рисунке 6 демонстрируется наглядное изменение рельефа функционально-воксельного пространства на М-образе при различных значениях α.

 

 

Рисунок 7: Изменение функционально-воксельного пространства при различных значениях коэффициента α

 

Увеличение коэффициента приводит к появлению новых не дифференцируемых точек на положительной области, а на самом рельефе начинают проявляться очертания прямолинейного скелета (рис.7). Наибольший интерес представляет М-образ при α=1 (Рис.8а), рельеф которого формирует очевидные цветовые переходы в местах предполагаемого скелета. Система R-функций в таком случае приобретает другой частный случай и преобразует систему (2) к линейному виду (8):

 

(8)

 

Вычисление скелета для компьютера заключается в распознавании разности значений палитры в соседних точках и не требует дополнительных численных преобразований. Так геометрическая конструкция скелета (Рис. 8б), полученная на основании компьютерно-графического анализа М-образа (Рис. 8а) полностью совпадает со своим аналогом, полученным с помощью алгоритма описанного в работе [16] без применения сложных вычислений.  Этим демонстрируется эффективность метода организации исходной вычислительной модели методом функционально-воксельного моделирования в решении задач, связанных со скелетным представлением геометрических фигур.

 

а)                    б)

Рисунок 8: М-образ при α=1 (a) и результат программного выделения ребер скелета (б)

 

Формирование поверхности функционального пространства, отображённого одной из локальных геометрических характеристик  на М-образе, полученного на основе R-операций α -системы (3), отвечает линейному закону (рис.8а.). Данный образ представляет наибольший интерес, поскольку «не дифференцируемые» точки поверхности принадлежат линейному скелету контура описанной функции (рис.8б).

 

4.  ЗАКЛЮЧЕНИЕ

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

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

1.       Васильев С.Н., Локтев М.А., Толок А.В., Толок Н.Б., Ульянов С.А. К планированию маршрутов в 3d-среде с многовариантной моделью // Труды СПИИРАН. 2016. №2(45). С. 5-25

2.       Толок А. В. Применение воксельных моделей в процессе автоматизации математического моделирования //Автоматика и телемеханика. – 2009. – №. 6. – С. 167-180.

3.       Толок А.В., Силантьев Д.А., Лоторевич Е.А., Пушкарёв С.А. Воксельно-математическое моделирование при решении задач определения площади для поверхностей деталей // Информационные технологии в проектировании и производстве №3, 2013,С 29-33.

4.       Васильев С.Н., Толок А.В. Решение оптимизационных задач средствами функционально-воксельного моделирования // Тезисы 15-ой Международной конференции "Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта" (CAD/CAM/PDM–2015). М.: OOO "Аналитика". 2015. C. 111.

5.       Местецкий Л.М. Непрерывный скелет бинарного растрового изображения. Труды межд. конф. "Графикон-98". Москва, 1998.

6.       Blum H. A transformation for extracting new descriptions of shape, Symp. on Models for the Perception of Speech and Visual Form, 1964

7.       Eppstein D., Erickson J. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions //Discrete & Computational Geometry. – 1999. – Т. 22. – №. 4. – С. 569-592.

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

9.       Aichholzer O., Aurenhammer F. Straight skeletons for general polygonal figures in the plane. – Springer Berlin Heidelberg, 1996. – С. 117-126.

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

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

12.   Максименко- Шейко К.В., Мацевитый А.М., Толок А.В., Шейко Т.И..R-функции и обратная задача аналитической геометрии в трехмерном пространстве // Информационные технологии. 2007. №10. C. 23-32

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

14.   Eftekharian A. A., Ilieş H. T. Distance functions and skeletal representations of rigid and non-rigid planar shapes //Computer-Aided Design. – 2009. – Т. 41. – №. 12. – С. 865-876.

15.   Eftekharian A. A., Ilies H. T. Curve Skeletons of Planar Domains //Computer-Aided Design and Applications. – 2011. – Т. 8. – №. 1. – С. 87-97.

16.   K. Sugihara, Straight Skeleton for Automatic Generation of 3-D Building Models with General Shaped Roofs, in: 21st Int. Conf. Comput. Graphics, Visualizat., Comput. Vision, 2013, pp. 175–183.

---

Construction of linear structure of a skeleton for the closed path of complex geometry on the basis of the method of functional voxel modeling

Authors: A.B. Tolok^1,A, M.A. Loktev^2,A, N.B. Tolok^3,B, N.D. Zhilina^4,C, M.B. Lagunova^5,C

^A МSТU «STANKIN», Moscow, Russia

^B ICS of RAS, Moscow, Russia

^C NNGASU, Nizhny Novgorod, Russia

¹ ORCID: 0000-0002-7257-9029, a.tolok@stankin.ru

² ORCID: 0000-0002-0465-1201, m.loktev@stankin.ru

³ ORCID: 0000-0002-5511-4852, nat_tolok@mail.ru

⁴ ORCID: 0000-0002-4814-2716, zhilina@nngasu.ru

⁵ ORCID: 0000-0002-0671-8609, logunova@nngasu.ru

 

Abstract

In this paper the way of construction of straight skeleton for complex closed contours described by means of a mathematical apparatus of R-functions is proposed. Applied a-system for the R-functional of description of the circuit and shown the results of the function at various values of the ratio a. Shows the transition from the organization of separate extreme points of R-functional surfaces to the organization of the linear structure of the skeleton of the zero contour. Here we describe the principle of M-images constructing on the basis of the method of functional voxel modeling (FVM). FVM-method, is the organizing principle of symbolic-graphic information, combining the analytic form of the description of a multidimensional model with a voxel representation of its local geometric characteristics. Selected class of M-images allows to automate the definition of the points and lines making a skeleton structure on the basis of delimitation of color transition. Such approach is based on preliminary representation of graphic information as a functional voxel model and allows to considerably simplify the computational process of search for solutions. Also we make the comparative analysis of a classical way of construction of straight skeleton with the offered computer graphic approach.

 

Keywords: functional Voxel Modeling, M-image, R-functions, straight skeleton.

 

References

               

1.       Vassilyev S.N., Loktev M.A., Tolok A.V., Tolok N.B., Ulyanov S.A. Route Planning in 3D Environment with a Multivariant Model. Tr. SPIIRAN, 2016, no. 45, pp. 5–25 (In Russian)

2.       Tolok A.V. Using voxel models in automation of mathematical modeling. Avtomatika i Telemekhanika, 2009, no. 6, pp. 167-180.

3.       Tolok A.V., Silantyev D.A., Lotorevich E.A., Pushkaryov S.A. Voxel-mathematical modelling at the solution of problems of definition of working surfaces of details. Informacionnye tehnologii v proektirovanii i proizvodstve -“Information technology of CAD/CAM/CAE, 2013, vol. 4, no. 3, pp. 29-33 (In Russian).

4.       Vassilyev S.N., Tolok A.V. Reshenie optimizatsionnyih zadach sredstvami funktsionalno-vokselnogo modelirovaniya [The solution of optimization problems of functional voxel modeling tools]. In proceedings of the 15th Int. Conf.  “System design, production planning and control step life cycle of industrial product (CAD/CAM/PDM - 2009)”. Moscow, Institute of Control Sciences of Russian Academy of Sciences, 2009, pp. 111-114 (In Russian). 

5.       Mestetskiy L.M. Nepreryvnyy skelet binarnogo rastrovogo izobrazheniya [The Continuous Skeleton of The Digital Binary Image]. In proceedings of the 8th Int. Conf. on Coputer Graphics and Vision GraphiCON, 1998 (In Russian). 

6.       Blum H. A transformation for extracting new descriptions of shape, Symp. on Models for the Perception of Speech and Visual Form, 1964

7.       Eppstein D., Erickson J. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions //Discrete & Computational Geometry. – 1999. – Т. 22. – №. 4. – С. 569-592.

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

9.       Aichholzer O., Aurenhammer F. Straight skeletons for general polygonal figures in the plane. – Springer Berlin Heidelberg, 1996. – С. 117-126.

10.   Tolok A.V. Functional-voxel model . Functional-voxel method in computer modeling, Moscow, Fizmatlit, Publ. 2016. 105 p. (In Russian)  

11.   Rvachev V. L. Theory of R-functions and Some Applications. Kiev, Naukova Dumka., Publ., 1982. 552 p.(In Russian)

12.   Maksimenko-Sheiko K.V., Matsevityi A.M., Tolok A.V., Sheiko T.I., R-functions and Inverse Problem of Analytic Geometry in the Three-dimensional Space, Ezhemes. Teoret. Prikl. Nauch.-tekhn. Zh., 2007, vol. 10, pp. 23–32.

13.   Loktev M.A., Tolok A.V. Method of a functional voxelization of polygonal objects on the basis of mathematical apparatus of R-functions. Prikladnaya Informatika — Journal of Applied Informatics, 2016, vol. 11, no. 1 (64), pp. 127 — 134 (in Russian).

14.   Eftekharian A. A., Ilieş H. T. Distance functions and skeletal representations of rigid and non-rigid planar shapes //Computer-Aided Design. – 2009. – Т. 41. – №. 12. – С. 865-876.

15.   Eftekharian A. A., Ilies H. T. Curve Skeletons of Planar Domains //Computer-Aided Design and Applications. – 2011. – Т. 8. – №. 1. – С. 87-97.

16.   K. Sugihara, Straight Skeleton for Automatic Generation of 3-D Building Models with General Shaped Roofs, in: 21st Int. Conf. Comput. Graphics, Visualizat., Comput. Vision, 2013, pp. 175–183.