>>>>> Princípios da geração de imagens utilizando Sistemas L <<<<<

Princípios da Geração de Imagens
Sistemas L

- Introdução

Apresentaremos "Princípios da geração de imagens utilizando Sistemas L" . Primeiramente introduziremos a noção de Sistemas L (L Systems) e sistemas DOL (DOL-Systems), depois partimos para o principal ponto de discussão que é a geração de imagens usando sistemas DOL. Discutiremos como, usando a interpretação por vetores ou da geometria da tartaruga (turtle geometry), os sistemas DOL podem produzir todas as imagens que podem ser geradas por linguagens regulares. Uma extensão da geometria da tartaruga que é introduzida possibilita que os sistemas L gerem imagens de tons cinza. Com esta extensão, mostra-se que todos os autômatos finitos valorados (Weighted Finite Automata - WFA) podem ser simulados por um sistema DOL.

- Definições

Definamos como linguagens regulares podem formar imagens. Primeiro, definimos uma correspondência bijetiva entre palavras de tamanho k e um alfabeto com um número quadrado de elementos. (ex: S2={0,1,2,3}, S3={0,1,2,3,4,5,6,7,8}, Sm = {0, 1,...,(m*m) - 1 }, etc), e subquadrados de uma tesselação (conjunto de subquadrados infinitamente pequenos) de tamanho (m elevado a k) × (m elevado a k) . Um conjunto T de palavras contido em (SxS) pode ser interpretado como uma coloração P(T) da tesselação citada: um subquadrado é preto se e somente se seu endereço estiver em T. Finalmente, a linguagem T é interpretada como uma sequência P(T0),P(T1),... de imagens de resolução finita com resoluções crescentes.

As tesselacoes com k=1 e k=2 estao nas figuras abaixo respectivamente.

Exemplo: considere o alfabeto S={0,1,2,3} e a linguagem regular {1,2}S*. Todo subquadrado com endereco na linguagem {1,2}S* sera' pintado de preto. Com isso teremos desenhado um tabuleiro de xadrez.

- O que são Sistemas L?

O Sistema L é um formalismo matemático proposto pelo biólogo Aristid Lindenmayer em 1968 como uma base para uma teoria axiomática para modelar o desenvolvimento celular. Mais recentemente, Sistemas L tem sido encontrados em várias aplicações em computação gráfica. Duas principais áreas incluem:

Geração de fractais

Modelos realísticos de plantas

A fundamento central é a reescritura. Onde a idéia básica é definir objetos complexos substituindo, sucessivamente, partes de um objeto simples usando um conjunto de regras de reescrita ou produções.

O trabalho de Chomsky nas gramáticas formais (1957) geraram um largo interesse em sistemas de reescrita. Conseqüentemente, um período de fascínio com a sintaxe, gramáticas e sua aplicação em Ciência da Computação deram origem ao campo de linguagens formais.

O trabalho de Aristid Lindenmayer introduziu um novo tipo de string que reescreve o mecanismo, denominado conseqüentemente Sistemas L. A diferença essencial entre gramáticas de Chomsky e Sistemas L encontra-se no método de aplicar produções. Em gramáticas de Chomsky as produções são aplicadas seqüencialmente, visto que nos Sistemas L são aplicadas em paralelo, substituindo simultaneamente todas as letras numa dada palavra. Esta diferença reflete a motivação biológica dos Sistemas L. As produções capturam divisões na célula em organismos multicelulares, onde muitas divisões podem ocorrer ao mesmo tempo. As células são representadas por símbolos e as divisões celulares são modeladas através da substituição destes símbolos por strings.

Daqui pra frente daremos início a classe mais simples dos Sistemas L denominada sistemas DOL. Para fornecer uma compreensão intuitiva da idéia principal sobre sistemas DOL, deixe-nos considerar este exemplo dado por Prusinkiewicz e por Lindenmayer (1991) na figura abaixo.

No exemplo acima, o Sistema L possui duas células representadas por A e B. A célula A se subdivide em duas células representadas pelo símbolo AB e a B se subdivide em duas células representadas pelo símbolo BA. A ordem dos símbolos é relevante num Sistema L. O organismo que esta abstração do sistema L representa cresce através de repetidas divisões celulares. Ao nascer o organismo possui apenas a célula A, depois de uma subdivisão, o organismo possui duas células representadas pela string AB. Após mais duas subdivisões, cada célula se dividindo de acordo com as regras descritas acima, o organismo possuirá quatro células dadas pela string ABBA e assim por diante. Por este motivo, os Sistemas L também são conhecidos como sistemas de reescrita paralela de strings (parallel string-rewrite systems).

Um outro exemplo seria o seguinte:

V = {a,b}
w = a

A primeira geração g0 é o axioma w.

g0	a
g1	b
g2	ba
g3	bab
g4	babba
g5	babbabab
g6	babbababbabba

Se observarmos com cuidado poderemos que notar que existe uma certa recursão na geração dessa cadeia. Podemos notar o seguinte:

g2 = g1g0
g3 = g2g1

E assim por diante. Isso nos faz lembrar a série de Fibonacci. Onde:
F(0) = F(1) = 1
F(n+2)=F(n+1)+F(n) ou seja, a série seria: 1, 1, 2, 3, 5, 8, 13, 21, ...

- Sistemas DOL

São os sistemas L mais elementares. Formalmente, um sistema DOL é uma tripla D=( ,h,w) onde

é um alfabeto finito,

é um morfismo e w é uma palavra vazia pertencente a

chamada axioma.O sistema DOL D gera as seqüências finitas w0,w1,... de palavras, onde w0=w e, para todo k>=1

.

As palavras

são interpretadas como imagens usando ou interpretação por vetores ou geometria da tartaruga. Para refletir o fato que nós comparamos Sistemas L com linguagens regulares que definem imagens compostas de quadrados preto e branco, uma leve modificação à interpretação original é feita.

- Interpretação por vetores

Quando usamos a interpretação por vetores, o alfabeto

se divide em dois subconjuntos disjuntos,

, o conjunto dos símbolos visíveis, e

, o conjuntos dos símbolos invisíveis. Mas adiante, um vetor

é nomeado para cada a pertecente a

. Logo, a compreensão de qualquer string w pertencente a

é definida recursivamente. Para w =

(vazio) a cabeça de desenho é posicionada na origem e nenhum desenho é feito. Para w = va, entendemos por v como um quadrado desenhado na posição corrente se a pertence a

(visível) e sempre avançando a cabeça de desenho na direção e tamanho do vetor

.
Tomemos

como sendo um sistema-DOL onde h é dada por :

Os vetores principais são:

T -> (0,0), a -> (1,0), b -> (-1,1) , c -> (0,-1).
Com esses dados, G gera como primeiras strings :
W0 = T ,
W1 = TaTbTc ,
W2 = TaTbTcaaTaTbTcbbTaTbccc
Na figura abaixo é mostrado a interpretação gráfica das strings w1, w2, e w3, usando escala

. Note que é a mesma imagem definida pela linguaguem regular {0,1,2}* sobre

Conseqüentemente, várias interpretações geométricas dos Sistemas L foram propostas a fim de torná-los em uma ferramenta versátil para modelar fractais. Muitos fractais podem ser pensados como seqüências de elementos primitivos (segmentos de linha). Para produzir fractais, as strings geradas por Sistemas L devem conter a informação necessária sobre a figura geométrica. Uma interpretação gráfica das strings, baseada na geometria da tartaruga, é descrita por Prusinkiewicz. Esta interpretação pode ser usada para produzir imagens fractais. Ou seja, os Sistemas L são uma forma compacta de descrever gráficos iterativos usando a analogia da Geometria da tartaruga...

- Geometria da tartaruga

Como antecipamos a Geometria da tartaruga é um instrumento para desenho que se move através do plano euclideano. Onde o estado da tartaruga é definido como a tripla (x, y, a) onde as coordenadas cartesianas (x, y) representam a posição da tartaruga e o ângulo 'a', chamado de seta ou cabeça, é interpretado como a direção para qual a tartaruga está voltada. Dado o tamanho do passo 'd' e o ângulo de incremento 'b', a tartaruga pode responder aos comandos representados pelos seguintes símbolos:

Lê	Então faça
F	Pinta um quadrado unitário e dá um passo adiante. O estado da tartaruga muda para (x', y', a)
f	Move adiante um passo de tamanho d contudo sem desenhar
+	Vira à esquerda por um ângulo b. O estado muda para (x, y, a+b)
-	Vira à direita por um ângulo b. O estado muda para (x, y, a-b)
[	Insere (push) um estado na pilha e o transforma no estado atual da tartaruga
]	Retira (pop) o corrente estado da pilha

- Um breve exemplo. Para este caso consideramos um ângulo de Pi/3 radianos

V = {F, +, -}
w = F
p1 = F -> F+F--F+F

Primeira Interação = (F+F--F+F):

Segunda Interação = (F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F):

Terceira Interação = (F+F--F+F+F+F--F+F...(148 caracteres no total)...F+F+F+F--F+F):

- Simulando um autômato finito através de um Sistema DOL

Linguagens regulares e sistemas DOL são interpretados como imagens através de caminhos diferentes. Toda seqüência de imagens de resolução finita definida por uma linguagem regular pode ser produzida por um sistema DOL. A principal razão, é que intuitivamente, por trás dessa observação, um sistema DOL pode simular em paralelo qualquer autômato finito. Mas precisamente, a k-ésima interação do sistema DOL é uma codificação de um autômato finito com todas as palavras de entrada de tamanho K. Vamos mostrar o resultado utilizando interpretação por vetores.

Teorema 1:
Para todo autômato finito A = (Q,

, s, E) reconhecendo uma linguagem L, então existe um sistema DOL

, tal que, a escala

são usados com interpretação de vetores,

para todo

, onde

denota

. Conseqüentemente, se P(L) existe, então T(G)=P(L).

Fonte: Revista Acta Informática - volume: 31 - paginas: 761-773 (1994).

- Sistemas L Valorados [WFA]

Para desenhar imagens em tons de cinza usando Sistemas L nós fazemos uma pequena adição na operação da tartaruga: ela não irá guardar apenas a sua posição e direção, mas também o valor(ou peso), o qual pode ser qualquer número real, negativo ou positivo. A tartaruga pode mudar seu peso, porém ela o empilha juntamente com a sua posição e direção. Agora, ao invés de pintar sempre preto, a tartaruga poderá pintar quadrados cinza com a intensidade dada pelo peso corrente. Se parte do quadrado já tiver sido pintado anteriormente, o peso da tartaruga é simplesmente adicionado ou subtraído (se negativo), com a parte totalmente escura.
Mais detalhes...

- Conclusão

Este trabalho teve como idéia o estudar a relação entre linguagens formais e os princípios da geração de imagens usando Sistemas L . Na abordagem mostramos como linguagens regulares podem gerar imagens e a relação(simulação) entre autômatos finitos e sistemas DOL. Como tambem o que são os Sistemas L e algumas de suas utilidades. Fizemos um paralelo com o crescimento das plantas, idéia inicial do biólogo Aristid Lindenmayer e uma recente interpretação geométrica dos Sistemas L foi propostas a fim de torná-los uma ferramenta versátil para modelar fractais . (Utilizando, por exemplo, interpretaçao por vetores ou pela geometria da tartaruga). Por último expomos como sistemas DOL (valorados) podem gerar todas as imagens que podem ser geradas por um automato finito (valorado) e que é possível desenhar imagens em tons de cinza usando Sistemas L. Tais imagens em tonalidades de cinza representam imagens com qualidade visual mais fiel. E apartir dessa abstração poderá se gerar se imagens coloridas trocando o comando F (que pinta um quadrado cinza) por comandos Y para amarelo, G para verde, R para vermelho e etc.

- Fontes e Links

Link 1:

Cellular Automata | Fractals and scale | Fuzzy systems - a tutorial

Link 2:

Morphogenesis | An Introductory L-system Tutorial | Music | L-system Plant Geometry Generator

Link 3:

Definições básicas | Tipos de Sistemas L | Os famosos Sistemas L da história da Matemática | etc.