Компьютерная инженерия

Шмуленкова Е. Е.

Омский государственный технический университет, Россия

Моделирование процедуры анализа векторных изображений на основе использования теории графов

При задании различных геометрических значений переменных параметрической 3-D модели режущего инструмента, например в системе T-FLEX, и получении на основе ее плоского чертежа могут возникнуть проблемы, связанные с тем, что произойдет выход отдельных изображений видов или сечений за пределы границ чертежа или их взаимное пересечение [1]. Как правило, этот чертеж редактируется пользователем вручную, на что уходит некоторое количество времени. Поэтому актуальной задачей является разработка программ, которые автоматизированным способом позволяют наиболее оптимально располагать фрагменты изображений видов, сечений, текстов технических требований и др.

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

Анализ векторных изображений, состоящих из отдельных примитивов и совокупностей графических объектов возможен с использованием функций доступа к примитивам по заранее заданным критериям. При этом анализ изображений осуществляется в системе AutoCAD с использованием языка программирования AutoLISP [2]. Процесс автоматизированной оценки чертежей металлорежущих инструментов, как правило, разделен на этапы. На первом этапе создаются наборы примитивов по различным признакам (по принадлежности заданным областям, слоям и т.п.). На втором этапе создаются списки опорных точек примитивов (начальные и конечные точки прямых, вершины многоугольников т.д.). На третьем этапе осуществляется систематизация примитивов. Эта процедура выполняется на основе оценки положения указанных точек по заранее заданным критериям. При этом объектами исследования являются конечные дискретные множества. Например, множество координат начальных и конечных точек горизонтальных и вертикальных прямых, множества начальных и конечных точек прямых, проходящих через заданную точку и т.д. Для установления взаимосвязи между указанными дискретными множествами используем теорию графов. Граф представляет собой совокупность вершин (Q₁, Q ₂, …) и дуг (ребер) (e₁, e₂, …), которые соединяют вершины [3]. Вершины графа определяют конечные дискретные множества, а дуги отражают взаимосвязи между этими множествами. На основе установления данных взаимосвязей между конечными дискретными множествами с помощью теории графов возможно моделирование процессов анализа различных векторных изображений по заданным критериям.

Рассмотрим граф, отражающий установление взаимосвязей между дискретными множествами координат точек различных геометрических объектов (ГО) при оценке их взаимного расположения. Данные объекты представлены на рисунке 1.

Рисунок 1 – Взаимное положение объектов на чертеже

а) положение прямых а₁, …, а₆ определяющих допустимое расстояние до рамки чертежа и основной надписи; б) положение прямой а₇, задающей контур зоны технических требований

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

Для автоматизированного анализа взаимного положения ГО Q₁, Q₂, …, Q₆ создаются списки координат точек принадлежащих их контурам . Данные координаты точек определяются на основе функций доступа к примитивам и анализа принадлежности тому или иному слою. При этом получается шесть различных дискретных множеств. На рисунке 1 изображены прямые а₁, …, а₇ по отношению к которым необходимо оценивать положения ГО Q₁, Q₂, …. Прямые а₁, а₂, а₃ и а₄ определяют допустимое минимальное расстояние до рамки чертежа, а а₅, а₆ – соответственно допустимое расстояние до основной надписи. Положение данных прямых зависит от размеров и ориентации формата. Таким образом анализ взаимного положения ГО основан на определении взаимного положения точек замкнутых контуров объектов Q₁, …, Q₆ и по отношению к областям заданных точками прямых а₁, ….

Установление взаимосвязей между конечными множествами рационально выполнить с помощью графов, матриц инциденций и смежностей. При этом вершины графа будут задавать дискретные конечные множества которые обозначаются , , .., и , , …, . Множества , …, определяются соответственными координатами точек, которые задают прямые а₁, …, а₇. Учитывая то, что ГО Q₁, Q₂ и Q₃ находятся в проекционной связи, при этом объект Q₂ всегда располагается ниже объекта Q₁, а объект Q₃ правее Q₁ и в целях сокращения времени расчета рационально определять не пересечения областей Q₁∩Q₇, Q₂∩Q₇, Q₃∩Q₇, а пересечения с областями определяемыми прямыми а₁, …, а₇. Q₇ – задает внешнюю область контура рамки чертежа, которая определяется с учетом допустимого заданного расстояния. Ребра графа определяют условия установления взаимосвязей между множествами , … и , , ….

Известно, что сумма всех элементов строки матрицы дает полустепень исхода вершин , а сумма элементов столбца - полустепень захода всех вершин .

Сумма полустепеней захода равна всех вершин графа равна сумме полустепеней исхода всех вершин и равна числу дуг в графе, что можно выразить следующей зависимостью [4]:

(1)

где n – число вершин, m – число дуг, d_и – полустепень исхода вершин, d_з – полустепень захода вершин.

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

Взаимосвязь вершин и ориентацию ребер отражает матрица инциденций (см. рисунок 3).

	0	0	0	0	0	0	0	1	0	0	1	0
	0	0	0	0	0	0	0	0	0	0	1	1
	0	0	0	0	0	0	0	0	0	1	0	0
	0	0	0	0	0	0	0	1	0	0	0	0
	0	0	0	0	0	0	0	0	1	0	0	0
	0	0	0	0	0	0	0	0	1	0	0	1
	0	0	0	0	0	0	0	0	0	1	0	1
	1	0	0	1	0	0	0	0	1	1	0	0
	0	0	0	0	1	1	0	1	0	0	1	1
	0	0	1	0	0	0	1	1	0	0	0	0
	1	1	0	0	0	0	0	0	1	0	0	1
	0	1	0	0	0	1	1	0	1	0	1	0

Рисунок 2 – Матрица смежности графа, представленного на рисунке 4

	е1	е2	е3	е4	е5	е6	е7	е8	е9	е10	е11	е12	е13	е14	е15	е16
	0	-1	0	0	0	0	0	0	0	0	-1	0	0	0	0	0
	0	0	0	0	0	0	0	0	0	0	0	-1	0	-1	0	0
	0	0	0	0	0	0	0	0	-1	0	0	0	0	0	0	0
	-1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
	0	0	0	0	0	0	-1	0	0	0	0	0	0	0	0	0
	0	0	0	0	0	0	0	-1	0	0	0	0	0	0	0	-1
	0	0	0	0	0	0	0	0	0	-1	0	0	0	-1	0	0
	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0
	0	0	-1	0	1	1	1	1	0	0	0	0	0	0	0	0
	0	0	0	-1	0	0	0	0	1	1	0	0	0	0	0	0
	0	0	0	0	-1	0	0	0	0	0	1	1	1	0	0	0
	0	0	0	0	0	-1	0	0	0	0	0	0	-1	1	1	1

Рисунок 3 – Матрица инциденций графа, представленного на рисунке 4

На рисунке 4 представлен ориентированный граф, отражающий процесс анализа положений фрагментов изображений Q₁,…, Q₇ на чертеже.

Рисунок 4 – Граф, отражающий процесс анализа положений

объектов Q₁,…, Q₇ на чертеже

На рисунке 4 приняты следующие обозначения: ,…, – множества значений координат вершин многоугольников ,…, ; , …, - множества значений координат точек задающих прямые и полуплоскости а₁, …, а₇, е₁,…, е₁₅ – ребра графа, отражающие критерии взаимосвязи множеств , …, .

Как видно из рисунка 4 наибольшую степень равную пяти имеют вершины , . Ребра е₁, е₂, е₇, е₈, е₉, е₁₀, е₁₁, е₁₂, е₁₄, е₁₅ определяют подмножества Q_i полученные пересечением областей, которые заданы многоугольниками ,…, с областями заданными прямыми , …, . Указанные подмножества вычисляются подпрограммой (PER-OBL O1x O1y ax by P1 P2). Ребра е₃, е₄, е₅, е₆, е₁₃ задают подмножества полученные пересечением многоугольников (Obl-PER-nMNI-nMNJ PMNI PMNJ PNI PNJ) [5]. Нумерация ребер соответствует упорядоченному исследованию пар множеств , …, и , …, .

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

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

На рисунке 5а представлена параметрическая 3-D модель, а на рисунках 5б и 5в соответственно изображены ассоциативные виды до автоматизированного анализа и корректировки и после.

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

Рисунок 5 – Результаты работы программного обеспечения связанного с автоматизированным анализом и корректировкой положения фрагментов изображений

а) изображение параметрической 3-D модели резца расточного; б) фрагмент изображения ассоциативных видов до автоматизированного анализа; в) фрагмент изображения ассоциативных видов после автоматизированного анализа и корректировки положения объектов

Литература

1. Глотова, В. Опыт параметрического проектирования в системе T-FLEX CAD / В. Глотова // САПР и графика. – 2004. – № 1. – С. 56–59.

2. Гладков, С. А. Программирование на языке Автолисп в системе САПР Автосад / С.А. Гладков. – М. : МИФИ, 1992. – 90 с.

3. Асанов, М. О. Дискретная математика: графы, матроиды, алгоритмы / М. О. Асанов, В. А. Баранский, В. В. Расин. – Ижевск, 2001. – 288 с.

4. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – М., 1978. – 432 с.

5. Притыкин, Ф. Н. Автоматизированный способ оценки взаимного положения фрагментов изображений на чертежах металлорежущего инструмента / Ф. Н. Притыкин, Е. Е. Шмуленкова // Вестник СибАДИ. – 2011. – № 1 (19). С. 59–62.