Построение автоматных моделей простейших графических примитивов

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2010
Hauptverfasser:	Козловский, В.А., Молчанова, В.С.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2010
Schriftenreihe:	Штучний інтелект
Schlagworte:	Интеллектуальные системы планирования, управления, моделирования и принятия решений
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/58482
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Построение автоматных моделей простейших графических примитивов / В.А. Козловский, В.С. Молчанова // Штучний інтелект. — 2010. — № 4. — С. 375-380. — Бібліогр.: 7 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-58482
record_format	dspace
spelling	irk-123456789-584822014-03-26T03:01:14Z Построение автоматных моделей простейших графических примитивов Козловский, В.А. Молчанова, В.С. Интеллектуальные системы планирования, управления, моделирования и принятия решений В статье рассматривается задача векторизации растрового изображения простейших графических примитивов. Предлагается алгоритм описания растровых изображений отрезков прямых и эллипсов и их простейших комбинаций в в виде систем автоматных уравнений. У статті розглядається задача векторизації растрового зображення найпростіших графічних примітивів. Пропонується алгоритм опису растрових зображень відрізків прямих і еліпсів і їх найпростіших комбінацій у вигляді систем автоматних рівнянь. The problem of vectorzation of the raster image is considered in the article. The algorithm of the description of raster images of straight line pieces and ellipses, as well as their elementary combinations in the form of systems of the automaton equations is offered. 2010 Article Построение автоматных моделей простейших графических примитивов / В.А. Козловский, В.С. Молчанова // Штучний інтелект. — 2010. — № 4. — С. 375-380. — Бібліогр.: 7 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/58482 004.93:519.71 ru Штучний інтелект Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Интеллектуальные системы планирования, управления, моделирования и принятия решений Интеллектуальные системы планирования, управления, моделирования и принятия решений
spellingShingle	Интеллектуальные системы планирования, управления, моделирования и принятия решений Интеллектуальные системы планирования, управления, моделирования и принятия решений Козловский, В.А. Молчанова, В.С. Построение автоматных моделей простейших графических примитивов Штучний інтелект
description	В статье рассматривается задача векторизации растрового изображения простейших графических примитивов. Предлагается алгоритм описания растровых изображений отрезков прямых и эллипсов и их простейших комбинаций в в виде систем автоматных уравнений.
format	Article
author	Козловский, В.А. Молчанова, В.С.
author_facet	Козловский, В.А. Молчанова, В.С.
author_sort	Козловский, В.А.
title	Построение автоматных моделей простейших графических примитивов
title_short	Построение автоматных моделей простейших графических примитивов
title_full	Построение автоматных моделей простейших графических примитивов
title_fullStr	Построение автоматных моделей простейших графических примитивов
title_full_unstemmed	Построение автоматных моделей простейших графических примитивов
title_sort	построение автоматных моделей простейших графических примитивов
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2010
topic_facet	Интеллектуальные системы планирования, управления, моделирования и принятия решений
url	http://dspace.nbuv.gov.ua/handle/123456789/58482
citation_txt	Построение автоматных моделей простейших графических примитивов / В.А. Козловский, В.С. Молчанова // Штучний інтелект. — 2010. — № 4. — С. 375-380. — Бібліогр.: 7 назв. — рос.
series	Штучний інтелект
work_keys_str_mv	AT kozlovskijva postroenieavtomatnyhmodelejprostejšihgrafičeskihprimitivov AT molčanovavs postroenieavtomatnyhmodelejprostejšihgrafičeskihprimitivov
first_indexed	2025-07-05T09:42:38Z
last_indexed	2025-07-05T09:42:38Z
_version_	1836799553890680832
fulltext	«Штучний інтелект» 4’2010 375 5К УДК 004.93:519.71 В.А. Козловский, В.С. Молчанова Институт прикладной математики и механики НАН Украины, г. Донецк kozlovskii@iamm.ac.dn.ua, vp24@yandex.ru Построение автоматных моделей простейших графических примитивов В статье рассматривается задача векторизации растрового изображения простейших графических примитивов. Предлагается алгоритм описания растровых изображений отрезков прямых и эллипсов и их простейших комбинаций в в виде систем автоматных уравнений. Введение Проблема компактного описания растровых изображений по-прежнему является актуальной, и предлагаются различные методы ее решения. Их эффективность в зна- чительной степени определяется типом изображений [1]. По-видимому, в общем слу- чае, нет эффективного перехода от растрового изображения к их векторному описанию. В работе предлагается способ такого перехода для графических изображений, которые можно синтезировать на основе небольшого набора простых графических примитивов. Например, для чертежей в основном достаточно отрезков прямых и кри- вых второго порядка. Идея предлагаемого перехода опирается на автоматное пред- ставление графических примитивов системами уравнений, задающих генерирующий автомат. В данной работе излагается общая идея синтеза генерирующего автомата и дается построение автомата, описывающего эллипс. Таким образом, целью работы является разработка алгоритма получения компактного описания растровых изобра- жений графических примитивов на основе автоматных моделей. Синтез автомата, генерирующего отрезок прямой Будем исходить из следующих предположений. Исходное изображение является растровым, под растром понимаем прямоугольную матрицу конечной размерности, эле- менты которой равны 0 или 1, в зависимости от наличия или отсутствия фрагмента изображения, попадающего на элемент матрицы. В более общем случае каждому эле- менту может сопоставляться некоторое число, указывающее оттенки серого или цвет- ность. Геометрически растр интерпретируется как фрагмент декартовой плоскости, разбитой на квадраты, вершины которых имеют целочисленные координаты. Каждому такому квадрату сопоставляем координату его правой верхней вершины. Описание объектов будем выполнять в алфавите непроизводных символов V = = {0,1,2,3,4,5,6,7} цепочечного кода Фримена [2], геометрический смысл которых ясен из рис.1. Слово в этом алфавите, кодирующее образ или его фрагмент, будет формировать- ся некоторым автоматом-генератором. В общем случае образ может задаваться со- вокупностью W таких слов. Если такое множество W задано априори, то его можно понимать как задание на синтез автомата, генерирующего данное множество, возмож- но, из разных состояний. Козловский В.А., Молчанова В.С. «Искусственный интеллект» 4’2010 376 5К Рисунок 1 – Непроизводные элементы Под автоматом (инициальным) понимаем шестерку A = (S, X, Y, δ, λ, s0), где S – конечное множество состояний, X – конечное множество входных символов (входной алфавит), Y – конечное множество выходных символов (выходной алфавит), δ – функ- ция переходов, определяющая следующее состояние, λ: S×X→Y – функция выходов, s0∈S – начальное состояние [3]. Если все три множества S, X, Y конечны, автомат на- зывается конечным. Так как рассматриваются автоматы-генераторы, то автомат можно считать автономным, т.е. таким, функции переходов и выходов которого не зависят от входов, и автомат А можно рассматривать как пятерку (S, Y, δ, λ, s0). Основным спосо- бом задания автомата выберем его описание в виде системы уравнений в некотором поле или кольце, что принципиально уменьшает размер описания автомата по сравне- нию с его заданием таблицей переходов-выходов. Будем полагать, что на растре задана декартова система координат, начало ко- торой совпадает с нижней левой точкой растра. Рассмотрим в этой декартовой плос- кости прямую a и отрезок AB на ней с концами A(x1,y1) и B(x2,y2). Пусть a описывается уравнением y=kx (1) , где k = (y2-y1)/(x2–x1) (2), причем k – положительное рациональное, не равное 1 и представлено в виде несократимой дроби m/n. Растровое изображение такой прямой может быть сформировано на основе различных моделей. Близкой к из- лагаемой ниже модели является модель Брезенхема [4]. Модель Брезенхема основыва- ется на расчете значения функции, задающей прямую, и определении знака накапли- ваемой ошибки, возникающей при округлении значения функции до целого значения. Тогда направление перемещения из одной клетки изображения в следующую опре- деляется по знаку этой ошибки. В отличие от метода Брезенхема предлагается способ формирования дискретной прямой на основе минимального отклонения растрового изображения от идеальной прямой, что представляется более естественным по сравнению с методом Брезенхема. На основании этого строится система автоматных уравнений, генерирующих описание изображения растровой прямой. Затем аналогичный прием используется и для описа- ния окружности или эллипса. Рассмотрим соответствующий автомат-генератор А (автономный). Множеством его состояний является множество пар (Sx, Sy), где Sx, и Sy – целые неотрицательные, не превышающие n, а выходным алфавитом является Y = {0, 1, 2}. Указанные значения интерпретируются следующим образом: Sx определяет смещение автомата по изобра- жению вдоль оси абсцисс от начала координат, Sy определяет аналогичное смещение вдоль оси ординат; Y определяет направление смещения по отношению к текущей клет- ке изображения (0 – движение вдоль оси абсцисс, 2 – движение вдоль оси ординат, 1 – движение по диагонали вверх). Положим Sx(0) = 0, Sy(0) = 0, Y(0) = 0. 5 7 123 4 0 6 Построение автономных моделей простейших графических примитивов «Штучний інтелект» 4’2010 377 5К Так как Sx и Sy целые, а k может быть дробным, то при округлении произведения kSx(i) к ближайшему целому возникает погрешность ∆, поэтому уравнение прямой (1) перепишем в виде (3). Sy(i) = k·Sx(i) + ∆. (3) Целочисленные значения Sx и Sy на каждом шаге будут изменяться не более, чем на 1, поэтому введем вспомогательные параметры α(i), β(i), с использованием кото- рых (3) перепишем в виде: Sy(i – 1) + β(i) = k·(Sx(i – 1) + α(i)) + ∆, (4) где α(i) и β(i) указывают смещение автомата на i-м шаге по оси x или y соответствен- но, и α(i), β(i) ∈ {0, 1}, α(i) +β(i) ≠ 0. Параметры α(i) и β(i) подбираем таким образом, чтобы \|∆\| был минимальным. Понимая \|∆\| как функцию ( ) ( )( ) ( ) ( )( )iiSi,if y ββα −+−= 1 ( ) ( )( )iiSk x α+−− 1 , определим (α(i), β(i)), при которых ( ) ( )( )( )i,if βα достигает мини- мума, где минимум берется по всем α(i), β(i) таким, что α(i), β(i) ∈ {0, 1}, α(i)+β (i)≠ 0. Значения Y(i) также рассмотрим как зависящие от α(i), β(i), т.е. Y(i) = Y(α(i), β(i)), и Y(1,0) = 0, Y(1,1) = 0, Y(0,1) = 2, а Y(0,0) не определено. Так как α(i) и β(i) в рассмат- риваемом случае одновременно не могут принимать значение 0, то Y(0,0) может быть взято произвольным. В данном случае положим Y(0,0) = 1. Пусть ( ) 1, 0 0, 0 , 1, 1 sign γ γ γ γ > = = − < тогда на основании вышесказанного Y(α(i), β(i)) можно представить в виде: Y(α(i),β(i)) = 1 + sign(β(i) – α(i)), (5) и для автомата, генерирующего слово описания прямой y = (m/n)x, можно указать за- дающие его следующие уравнения: ( ) ( ) ( )( )( ) ( ) ( ) ( )( )( ) ( ) ( ) ( ) ( ) ( ) ( )        = == = −+−= −−+−= 00 00,00 )-sign(+1 mod11 mod121 Y SS iiiY niYsigniSiS miYsigniSiS yx yy xx αβ . (6) Приведенные рассуждения справедливы для отрезков на прямых, у которых k > 0. При k < 0 отрезку на прямой y = kx можно сопоставить симметричный ему относитель- но оси y отрезок на прямой y = \|k\|x. Из рис. 1 видно, что направлениям «0», «1» и «2», использованным при описании отрезка прямой с k > 0, относительно оси y симмет- ричны направления «0», «7» и «6» при движении слева направо. Для описания отрезка на прямой y = kx (k < 0) необходимо описать отрезок на прямой y = \|k\|x, а затем выпол- нить перекодировку: «0» – «0», «1» – «7», «2» – «6». Из уравнений (6) следует, что, как и в других моделях, слова, сформированные предложенным автоматом и описывающие отрезки прямых, являются подсловами не- которых периодических слов. Слово P называется периодическим, если его можно представить в виде kPP 1= , где kP1 обозначает k раз повторенное слово P1, k = 1, 2,...; наименьшее такое k называется периодом слова P. В [2] было предложено автомат- ное описание слов, соответствующих прямым при другом способе перехода к раст- ровому изображению прямой. Предложенный способ описания позволяет привести к единой форме описание как прямых, так и кривых второго порядка. Козловский В.А., Молчанова В.С. «Искусственный интеллект» 4’2010 378 5К Синтез автомата, генерирующего окружность и эллипс Одним из наиболее часто встречающихся вариантов кривой второго порядка яв- ляется окружность. В силу симметричности окружности достаточно построить автомат, генерирующий одну из ее четвертей, остальные четверти окружности могут быть по- лучены путем симметричных отражений первой относительно осей координат. Построим автомат для первой четверти окружности. Состояние автомата опре- деляется парой (Sx, Sy), Sx∈(0, r–1), Sy∈(0, r–1), где r – радиус окружности (r натураль- ное). Будем считать, что изначально автомат находился в точке (0, 0), т.е. Sx(0) = 0, Sy(0) = 0, и на каждом такте хотя бы одна из составляющих состояния должна увели- читься на 1. Рассматриваем следующие варианты движения от построенной точки: вправо на 1 позицию, по диагонали вправо вниз на позицию, вниз на 1 позицию, что будет соответствовать выходным значениям автомата 1,0, –1, которые кодируются со- ответственно кодами «0», «7», «6» алфавита V. Поэтому примем Y = {– 1, 0, 1}. Используя те же рассуждения, что и при построении описания отрезка прямой, получим следующие уравнения функционирования автомата: ( ) ( ) ( ) ( )         = == += −−+−= −+−= 1Y(0) 0(0)0,(0)S *Y(i) mod1))Y(isign(1)(i(i)S mod1))sign(Y(i1)(iS(i)S x y x x y x S ii rS r βα . (7) Здесь (α(i),β(i)) = argmin(f(α(i),β(i))) для функции f(α(i), β(i)) = \|r2 – ((Sx(i) + + α(i))2 + (r – Sy(i) + β(i)))2\|, и минимум берется по всем α(i), β(i), таким, что α(i)∈{0,1}, β(i)∈{–1, 0}, α(i)2 + β(i)2 ≠ 0. Изменив формулу для f(α(i), β(i)) можно получить описание первой четверти эл- липса с осями a и b, параллельными осям координат. В этом случае f(α(i),β(i)) = \|a2b2– (Sx(t) + α(i))2b2 – (Sy(t) + β(i))2a2\| и arg min(f(α(i), β(i)))=(α(i), β(i)). При построении эллипса автомат-генератор возвращается в начальное состояние, когда Sx(t) = a, Sy(t) = b. Поскольку изначально в качестве алфавита описания образов использовался ал- фавит V = {0, 1, 2, 3, 4, 5, 6, 7}, а в рассмотренном выше способе решения для коди- ровки используются символы из множества V' = {–1, 0, 1} для указания направлений «0», «6» и «7», определим правило преобразования символов алфавита V' в символы алфавита V. Пусть v – символ из алфавита V, v' – символ из алфавита V'. Легко заметить, что v = v'+7. При построении первой четверти будет получено слово P1=α1(1)α1(2)… α1(t)… α1(k). Вторая четверть окружности симметрична первой относительно оси ординат и со- ответствующее выходное слово P2 может быть получено следующей перекодировкой: α2(i) = 12–α1(i). Для третьей четверти выходное слово P3 будет получено по соотноше- нию: α3(i) = 8–α2(i), а для четвертой – α4(i)=4 – α3(i). Построение произвольных кривых второго порядка Выше рассмотрена задача построения эллипса, у которого оси параллельны ко- ординатным. Предложенный подход может быть распространен и на случай более об- щей задачи описания произвольной кривой второго порядка. Построение автономных моделей простейших графических примитивов «Штучний інтелект» 4’2010 379 5К Уравнение кривой второго порядка, у которой оси параллельны координатным, имеет вид: 02222 =++++ FEyDxCyAx , если оси кривой не параллельны координат- ным, то она задается уравнением: 0222 22 =+++++ FEyDxCyBxyAx (8). Общая структура уравнения (8) может быть использована для описания произ- вольной кривой второго порядка. Особенности этой кривой фиксируются функцией f(a,b): f(α(i),β(i)) = \|A(Sx(i) + α(i))2 + 2B(Sy(i) + β(i))(Sx(i) + α(i)) + C(Sy(i) + β(i))2+2D(Sx(i) + + α(i))+2E(Sy(i)+β)+F\|, и argmin(f(α(i),β(i))) = (α(i),β(i)), где минимум берется по всем α(i), β(i), таким, что α(i)∈{0, 1}, β(i)∈{–1,0}, α(i)2 + β(i)2 ≠ 0. Тогда Y(i) = α(i) + β(i)*. В случае произвольной кривой второго порядка предвари- тельно необходимо ограничить область, на которой эта кривая строится. Предложенные описания задают прямые, окружности и эллипсы, линия контура которых имеет «единичную» толщину. Расширим этот способ на контуры большей толщины. Окружность с толщиной линии контура m и радиусом r (при относительно ма- лом отношении m/r) описывается как конкатенация слов Y(r), Y(r - 1), …, Y(r – m + 1). Эллипс с толщиной линии контура m и осями a и b описывается как конкатенация слов Y(a,b), Y(a – 1,b – 1), …, Y(a –m + 1, b – m+1). Расcмотренный подход синтеза генерирующего автомата опирается на структур- ные особенности образов, отраженных в данном случае в уравнении, задающих непре- рывный прототип растрового изображения. Возможен и другой подход к решению задачи. Он исходит из произвольности множества слов W, формируемых специальным обходом автомата-сканера, по которым строится система уравнений генерирующего автомата. В этом случае необходимо наложить ограничения на систему уравнений, на- пример, можно рассматривать автомат, реализуемый на сдвиговом регистре с линейной обратной связью. Учитывая мощность алфавита V, его элементы можно рассматривать как элементы поля Галуа GF(8). Пусть W состоит из одного слова. Тогда для построе- ния автомата с наименьшей линейной сложностью, т.е. с наименьшей длиной регистра, можно использовать алгоритм Берлекэмпа-Месси [5]. В более общем случае, когда линейная сложность велика, можно перейти к построению нелинейных уравнений, или к сдвиговым регистрам с нелинейной обратной связью. Если мощность W боль- ше 1, то предварительно можно выделить общие суффиксы у слов, входящих в W, что позволит уменьшить сложность синтезируемого автомата. При этом можно использо- вать методы синтеза автоматов по наблюдаемому поведению [6]. Заключение В статье описана задача синтеза автоматов-генераторов синтаксических описаний линии, окружности, эллипса и произвольных кривых второго порядка. Такие описания могут служить основой для формирования векторного описания сложных образов, синтезированных из указанного набора простых геометрических примитивов. Исполь- зование автоматных моделей позволяет привлечь для решения задач анализа и синте- за образов богатый аппарат теории автоматов. На основании полученных моделей разработана программа, позволяющая полу- чать синтаксическое описание растровых изображений и строить по ним их векторное описание и обратно. Козловский В.А., Молчанова В.С. «Искусственный интеллект» 4’2010 380 5К Литература 1. Абламейко С.В. Обработка изображений: технология, методы, применение / С.В. Абламейко, Д.М. Ла- гуновский. – Минск : Амалфея, 2000. – 304 с. 2. Введение в контурный анализ; приложения к обработке изображений и сигналов / Я.А. Фурман, А.В Кревецкий, А.К. Передреев и др. ; под ред. Я.А. Фурмана. – М. : ФИЗМАТЛИТ, 2003. – 592 с. 3. Кудрявцев В.Б. Введение в теорию автоматов / В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин. – М. : Наука, 1985. – 320 с. 4. Шикин А.В. Компьютерная графика. Полигональные модели / А.В. Шикин, А.В. Боресков. – М. : ДИАЛОГ-МИФИ, 2001. – 464 с. 5. Блейхут Р. Теория и практика кодов, контролирующих ошибки / Блейхут Р. – М. : Мир, 1986. – 576 с. 6. Грунский И.С. Синтез и идентификация автоматов / И.С. Грунский, В.А. Козловский. – Киев : Наук. думка, 2004. – 245 с. 7. Деглина Ю.Б. Автоматные алгоритмы синтеза образов / Ю.Б. Деглина, В.С. Денисова, В.А. Коз- ловский // Искусственный интеллект. – 2008. – № 3. – С. 290-295. В.А. Козловський, В.С. Молчанова Побудова автоматних моделей найпростіших графічних примітивів У статті розглядається задача векторизації растрового зображення найпростіших графічних примітивів. Пропонується алгоритм опису растрових зображень відрізків прямих і еліпсів і їх найпростіших комбінацій у вигляді систем автоматних рівнянь. V.A. Kozlovsky, V.S. Molchanova Construction of Automaton Models of the Simplest Graphics Primitives The problem of vectorzation of the raster image is considered in the article. The algorithm of the description of raster images of straight line pieces and ellipses, as well as their elementary combinations in the form of systems of the automaton equations is offered. Статья поступила в редакцию 24.06.2010.

Построение автоматных моделей простейших графических примитивов

Institution

Ähnliche Einträge