Visualizar - Polis Educacional

Transcrição

Anderson Aparecido de Assis
R.A. 0502004
UTILIZAÇÃO DE TÉCNICAS DE GEOMETRIA FRACTAL PARA
GERAÇÃO DE IMAGENS
Jaguariúna
2008
Anderson Aparecido de Assis
R.A. 0502004
UTILIZAÇÃO DE TÉCNICAS DE GEOMETRIA FRACTAL PARA
GERAÇÃO DE IMAGENS
Monografia apresentada à disciplina
Trabalho de Graduação, do Curso de
Ciência da Computação da Faculdade
de Jaguariúna, sob a orientação do
Prof. Ms. Silvio Petroli Neto, como
exigência essencial à conclusão do
curso de graduação.
Jaguariúna
2008
1
Aos meus pais, famíliares e amigos que
sempre motivaram e apoiaram meus
estudos. E também à Janaina Pimentel
por sua paciência, apoio e dedicação.
2
AGRADECIMENTOS
A realização desta Monografia só foi possível pelo apoio de inúmeras pessoas. A
todos manifesto minha sincera gratidão. E de modo particular:
Ao Professor e orientador Silvio Petroli Netto pela orientação dedicada e pelo
constante estímulo em todas as fases de realização deste trabalho e durante as fases do meu
estudo.
3
Viver é enfrentar um problema atrás do
outro. O modo como você o encara é que
faz a diferença. (Dr. Lair Ribeiro)
4
DE ASSIS, Anderson Aparecido. ESTUDO DE TÉCNICAS DE GEOMETRIA
FRACTAL. Monografia (Bacharelado em Ciência da Computação) – Curso de
Ciência da Computação da Faculdade de Jaguariúna, Jaguariúna.
Resumo
Este projeto apresenta uma visão geral sobre fractais, bem como formas e métodos
utilizados para demonstrá-los.
Mostra como os métodos como Sistema-L e Sistemas de Funções Iterativas são de
grande utilidade para o desenvolvimento na área de estudos cientificos.
Para tal projeto será vista a sua utilização ao se unir os métodos de criação de imagens
fractais e as técnicas de computação gráfica, resultando em códigos responsáveis pela geração
das imagens ao invés do armazenamento da própria imagem, porém com maior exigência da
máquina ou computador, quanto ao tempo de processamento necessário para tal geração.
Situação esta de se armazenar a própria imagem, torna-se necessária para os casos de
se criar uma imagem através de ferramentas de criação de imagem de forma interativa com o
usuário.
Palavra-chave: Computação Natural, Geometria Fractal, Sistemas de Funções Iterativas,
Sistema-L, ferramenta de programação matemática.
5
Sumário
1. INTRODUÇÃO..................................................................................................................9
2. COMPUTAÇÃO NATURAL ..........................................................................................11
2.1
Computação inspirada na natureza. .......................................................................... 12
2.1.1
Redes neurais artificiais........................................................................................ 13
2.1.2
Algoritmos evolutivos. ......................................................................................... 14
2.1.3
Inteligência coletiva ou swarm intelligence. ........................................................ 14
2.1.4
Sistemas imunológicos artificiais. ........................................................................ 15
2.2
Estudo sobre a natureza através da computação....................................................... 16
2.2.1
Vida artificial........................................................................................................ 17
2.2.2
Geometria computacional (fractal) da natureza.................................................... 17
3. GEOMETRIA FRACTAL ...............................................................................................18
3.1
Auto-similaridade estrita; ......................................................................................... 19
3.2
Auto-similaridade estatística (auto-afinidade); ........................................................ 19
3.4
Os primeiros fractais................................................................................................. 20
3.5
O conjunto de cantor................................................................................................. 20
3.6
A curva de Koch (floco de neve).............................................................................. 21
3.7
O triângulo de Sierpinski.......................................................................................... 23
3.8
A curva de Peano...................................................................................................... 23
3.9
Dimensão euclidiana e dimensão fractal .................................................................. 24
3.10 Sistemas de Lindenmayer (Sistemas-L) ................................................................... 25
3.10.1
Sistema-DOL (DOL-Systems) ............................................................................. 26
3.11 Sistemas de funções iterativas (IFS – Iterated Function Systems)........................... 27
4. CONCEITOS SOBRE COMPUTAÇÃO GRÁFICA ......................................................30
4.1 Translação....................................................................................................................... 31
4.2 Escalonamento................................................................................................................ 32
4.3 Reflexão.......................................................................................................................... 33
4.4 Rotação ........................................................................................................................... 34
5. APLICAÇÃO DE TECNICAS DE GEOMETRIA FRACTAL ......................................36
5.1 Criação de árvore utilizando o Sistema-L ...................................................................... 36
5.2 Criação de árvore utilizando o Sistema de Funções Iterativas ....................................... 38
5.3 Criação das imagens unindo os modelos fractais em um mesmo algoritmo .................. 40
5.4 Criação da imagem através da Ferramenta PAINT ........................................................ 41
5.5 Comparativo entre os dois métodos utilizados, para a criação de uma mesma imagem.
.............................................................................................................................................. 42
6. CONCLUSÃO..................................................................................................................45
7. REFERÊNCIAS BIBLIOGRÁFICAS .............................................................................46
8. ANEXOS ..........................................................................................................................47
6
Lista de Siglas
DIFS
.JPG
IFS
.M
RNAs
SIA
Deterministic Iterated Function System
Joint Photographic Group
Iterated Function Systems
Extensão de arquivos gerados e excutados de uma ferramenta de
programação matemática
Redes Neurais Artificiais
Sistemas Imunológicos Artificiais
7
Lista de Figuras
Figura 1 - Exemplo de auto-similaridade na natureza [Castro, 2007]...................................... 19
Figura 2 - Exemplo de auto-similaridade estrita [Castro, 2007]. ............................................. 19
Figura 3 - Exemplo de auto-similaridade estatística ou auto-afinidade [Castro, 2007]. .......... 20
Figura 4 - Exemplo dos primeiros passos do Conjunto de Cantor [Castro, 2007]. .................. 21
Figura 5 - Exemplo dos primeiros passos da Curva de Koch [Castro, 2007]........................... 22
Figura 6 - Exemplo da Ilha de Koch, também conhecida como Floco de Neve ...................... 22
Figura 7 - Exemplo dos primeiros passos na construção do Triângulo de Sierpinski.............. 23
Figura 8 - Exemplo dos primeiros passos na construção da Curva de Peano [Castro, 2007]. . 24
Figura 9 - Exemplos de plantas geradas através da técnica do Sistema de Lindenmayer. ....... 25
Figura 10 - O Arbusto de Barnsley, gerado pelo código da Tabela 02. ................................... 29
Figura 11 - Modelo Conceitual sobre Computação Gráfica [Vianna, 2002]............................ 30
Figura 12 - Exemplo de translação ........................................................................................... 32
Figura 13 - Exemplo de escalonamento ................................................................................... 33
Figura 14 - Exemplo de reflexão .............................................................................................. 34
Figura 15 - Exemplo de rotação da imagem (rotacionando a folha 30º sentido horário)......... 35
Figura 16 – Exemplo de sistemas L ......................................................................................... 37
Figura 17 – Imagem gerada através da duplicação da figura gerada pelo Sistema-L, na forma
de reflexo. ......................................................................................................................... 38
Figura 18 – Reprodução de várias folhas formando uma árvore, através das coordenadas dos
pontos ou pixels de uma folha, armazenados em uma matriz. ......................................... 39
Figura 19 - Imagens geradas a partir do código ....................................................................... 40
Figura 20 - Imagem gerada através da ferramenta PAINT, de forma prática e interativa. ...... 41
8
1. INTRODUÇÃO
Há tempos, matemáticos eram reconhecidos pelos cálculos clássicos, nos quais havia a
possibilidade imediata de aplicação. Raros eram os que buscavam saber o real valor para tais
fórmulas e cálculos. Em tempos mais recentes, este tipo de pensamento vem sendo mudado,
pois há um interesse maior em se descobrir com maior detalhe a formação, por exemplo, de
estruturas da natureza como: uma montanha, uma nuvem, uma costa marítima, pois estas não
podem ser reproduzidas com formas de esferas, cones, nem mesmo círculos.
Como se sabe, as formas de geometria pura ou geometria Euclidiana descrevem
formas como caixas sendo cubos, lápis sendo cilindros, bolas sendo esferas. Porém, esta
geometria não tem capacidade para descrever a forma de um floco de neve, por exemplo. Para
isso, a geometria fractal, que vem do Latin “fractus” e corresponde ao verbo quebrar, ou seja,
criar formas irregulares vem sendo aprimorada, criando-se modelos matemáticos oriundos dos
padrões sintéticos da natureza.
Através de estudos de técnicas de modelagens e sínteses de padrões naturais
comprovou-se que a Natureza é fractal. Estas pesquisas vêm sendo auxiliadas pela
computação gráfica, tornando possível tais descobertas de maneira cada vez mais prática
[CASTRO, 2007].
Desta forma, podem-se ter ferramentas que auxiliam na formação de novas formas de
plantas ou até mesmo de reprodução de espécies raras ou extintas.
Atualmente vê-se a geometria fractal como uma forma de reproduzir arte, com
imagem (fotografias) nunca antes vislumbradas, ou até mesmo utilizando-se da mesma para
criar maior realismo em filmes que reproduzem o mundo real virtualmente.
Dentre os métodos e algoritmos criados para a obtenção destas reproduções da
Natureza, será abordado o Sistema-L e o Sistema de Funções Iterativas.
O Sistema-L é um dos mais compactos e práticos modelos de fractais, recebeu a letra
“L” devido o nome do biólogo alemão A. Lindenmayer, que introduziu o conceito de
autômatos celulares para descrever os processos de crescimento de organismos constituídos
por células, através da matemática. Sistema-L pode ser também discutido como um algoritmo
de desenvolvimento, que consiste em descrever todo um processo de desenvolvimento
multicelular, ou seja, da passagem de um determinado organismo desde sua fase embrionária
até sua maturidade [CASTRO, 2007].
9
Sistemas de Funções Iterativas (IFS - Iterated Function Systems) foram desenvolvidos
por J. Hutchinson, M. Barnsley e S. Demko. Os IFS consistem basicamente da aplicação
recursiva de um conjunto de transformações, que após um determinado período de iterações,
haverá uma certa configuração geométrica. Esta aplicação pode também ser conhecida como
mapeamentos contrativos, na qual é gerada uma imagem sobre ela mesma, havendo sempre
uma convergência para o mesmo ponto.
Ambos os métodos, Sistema-L e Sistemas de Funções Iterativas, são bastante úteis
para desenho e modelagem de paisagens naturais, ornamentais e ilustrações botânicas entre
outras.
No decorrer deste projeto, será visto mais a fundo os métodos, Sistema-L e Sistemas
de Funções Iteraticas, efetuando testes utilizando uma ferramenta de programação matemática
na criação de imagens gráficas, demonstrando boas práticas e suas utilidades no campo da
computação científica.
Unindo as técnicas Sistema-L e Sistema de Funções Iterativas com uma ferramenta de
programação matemática para criação de imagens gráficas, também criando imagens
semelhantes através da ferramenta da Microsoft, o PAINT, será possível realizar o objetivo
principal deste projeto que será, através dos resultados obtidos, analisar as vantagens e
desvantagens em se otimizar dados, armazenando apenas linhas de códigos responsáveis pela
reprodução da imagem, de forma a aproveitar o processamento do computador. Será
observado também a vantagem em se armazenar as imagens criadas através da ferramenta
PAINT, utilizando pouco processamento da máquina, porém ocupando mais espaço no
armazenamento.
10
2. COMPUTAÇÃO NATURAL
A computação natural vem cada vez mais se aproximando dos conceitos utilizados na
natureza. Hoje, há a possibilidade, por exemplo, de se desenvolver um sistema especialista
que absorva informações a ponto de obter inteligência por si só.
Aprende-se com a natureza e seus fenômenos, métodos que resolvem e/ou criam
grandes possibilidades para se criar novas tecnologias que auxiliam em muitas áreas, como a
engenharia, botânica, além de criar eletroeletrônicos ou eletrodomésticos “inteligentes” em
que auxiliam até mesmo no cotidiano de pessoas comuns.
Fundamentalmente, a computação natural é constituída por novas abordagens
computacionais caracterizadas por uma maior proximidade com a natureza.
Segundo Castro (2007):
Desenvolver ferramentas matemáticas e computacionais para a solução de
problemas complexos em diversas áreas do conhecimento;
Projetar dispositivos (computacionais) que simulam, emulam, modelam e
descrevem sistemas e fenômenos naturais;
Sintetizar novas formas de vida, denominadas de vida artificial;
Utilizar mecanismos naturais, como cadeias de DNA e técnicas de
engenharia genética, como novos paradigmas de computação. Estes novos
paradigmas vêm suplementar e/ou complementar os computadores atuais
baseados em tecnologia de silício e arquitetura de Von Newmman.
A visão que se pode ter atualmente sobre o que é a computação natural é a de que
trata-se de um processo de análise ou extração de idéias, mecanismos, fenômenos e da síntese
da natureza para se desenvolver sistemas “artificiais”.
É importante salientar que a palavra “artificial” no contexto de computação natural,
significa apenas que os sistemas e dispositivos resultantes são desenvolvidos por seres
humanos ao invés de serem produtos diretos da evolução das espécies.
A área da computação natural pode ser dividida em três grandes subáreas na qual
patrocinam a proposição de poderosas ferramentas computacionais para a solução de
problemas complexos da engenharia e têm permitido a geração de novos paradigmas de
computação, são elas:
11
2.1
•
Computação inspirada na natureza;
•
Estudos sobre a natureza através da computação;
•
Computação com mecanismos naturais;
Computação inspirada na natureza.
A computação inspirada na natureza é apenas um ramo de estudo voltado à
computação, porém esta observação da natureza estudada permitiu o desenvolvimento de
diversas leis e teorias sobre os comportamentos da mesma.
Alguns exemplos que foram primordiais para o desenvolvimento cientifico, voltados à
física como:
•
Leis do movimento (leis de Newton);
•
Leis do eletromagnetismo (leis de Maxwell);
Há também exemplos de objetos inspirados na natureza que compõem o dia-a-dia,
alguns exemplos:
•
Velcro inspirado nas plantas;
•
Coletes a prova de bala são inspirados nas teias de aranha;
•
Sonares são inspirados em morcegos ao qual utilizam como meio de se
orientarem em seus percursos;
•
Aviões são inspirados em pássaros;
•
Submarinos são inspirados em peixes;
O mais antigo e bem consolidado, portanto mais conhecido ramo da computação
natural, a computação inspirada na natureza, surgiu através da descoberta de princípios e
teorias sobre a natureza. Com isso, pesquisadores da área de engenharia e computação viram
12
uma grande oportunidade de tirar proveito desta, na elaboração de sistemas computacionais
capazes de resolverem problemas complexos.
A computação inspirada na natureza compreende principalmente:
•
Redes neurais artificiais;
•
Algoritmos evolutivos;
•
Inteligência coletiva;
•
Sistemas imunológicos artificiais;
2.1.1 Redes neurais artificiais.
O primeiro trabalho voltado a computação inspirada na natureza surgiu em 1943 por
McCulloch & Pitts, introduzindo o primeiro modelo matemático (lógico) de um neurônio.
Este modelo conhecido como neurônio artificial foi quem deu origem a linha de pesquisa
conhecida atualmente como redes neurais artificiais.
O cérebro é reconhecido como o órgão mais complexo e também mais cobiçado em
relação a pesquisas pelos cientistas. É ele que contém a maior parte do controle do corpo e por
isso ele é um especialista em desempenhar funções como reconhecimento de padrões,
controle motor, percepção, inferência, intuição, adivinhações, etc.
Sabe-se que os neurônios são considerados as unidades básicas de processamento do
cérebro. Baseando-se neste comportamento é que as redes neurais artificiais (RNAs) se
inspiram, utilizando-se de uma grande quantidade de unidades simples de processamento
(neurônios artificiais) interligados entre si de forma bastante distribuída.
O conhecimento de uma rede neural se dá pela aprendizagem, que é realizada através
de uma considerável modificação nas sinapses dos neurônios.
Sinapse é o nome dado à conexão entre um neurônio e outro que armazenam as
informações que, mediante seu peso, as transportam até o neurônio receptor.
13
2.1.2 Algoritmos evolutivos.
Outra abordagem baseada na computação inspirada na natureza usa idéias da biologia
evolutiva como forma de desenvolver algoritmos úteis para tarefas de busca e otimização para
a resolução de problemas complexos e simular processos evolutivos naturais.
A idéia de algoritmos evolutivos surgiu na década de 60 por I. Rechenberg (1973), H.
P. Schwefel (1965), L. Fogel (1966) e J. Holland (1975).
Baseado na teoria de Darwin, que se baseia principalmente na “seleção natural” como
forma de manutenção das variações favoráveis através da seleção natural, na qual, ao longo de
um grande espaço de tempo acarretará o aparecimento de novos organismos que são tão
distintos de seus antecessores que acabam por se caracterizarem como uma nova espécie.
No caso da teoria da evolução através da seleção natural, os principais processos
algorítmicos envolvidos são:
•
Reprodução com herança genética;
•
Variação genética;
•
Seleção natural;
2.1.3 Inteligência coletiva ou swarm intelligence.
O temo inteligência coletiva ou de “enxame” surgiu na década de 80 e busca a idéia de
tentativa de projeção de algoritmos ou dispositivos distribuídos baseados em comportamentos
de insetos e outras sociedades animais para resolver problemas.
A inteligência coletiva possui duas frentes principais de pesquisa:
•
Algoritmos baseados no comportamento coletivo de insetos sociais: este tipo
de algoritmo busca desenvolver soluções de problemas de otimização
combinatória, agrupamento de dados, robótica coletiva, etc.
14
•
Algoritmos baseados na habilidade das sociedades humanas em processar
conhecimento: para este caso de algoritmo, os mesmos são eficazes para a
realização de buscas em espaços contínuos.
A idéia principal neste caso é buscar o crescimento mútuo em uma sociedade, cujo
conhecimento se dará como um todo e ao mesmo tempo será descentralizado de algum tipo de
poder, sendo distribuídas todas as responsabilidades por igual, ou seja, será valorizada a
responsabilidade de cada um, sendo vantajoso para todos em relação a enriquecimento
cultural.
2.1.4 Sistemas imunológicos artificiais.
Os sistemas imunológicos artificiais possuem idéias extraídas do sistema imunológico
dos seres vertebrados e tem sua aplicação desde a biologia até a robótica.
Esta área de pesquisa bastante nova, surgiu por volta da década de 80 e busca utilizar
um dos sistemas mais complexos da natureza.
Uma das principais funções deste sistema é defender o organismo contra infecções
causadas por patógenos, que são seres causadores de doenças, como vírus, bactérias, fungos e
parasitas.
O sistema imunológico pode ser dividido em duas partes:
•
Sistema inato: Este sistema é a primeira barreira contra os patógenos, elas
servem para emitir sinais para outras células, caso uma das células do sistema
inato reconheça algum patógeno.
•
Sistema adaptativo: Como nem todos os patógenos são reconhecidos pelo
sistema inato, o sistema adaptativo é responsável por reconhecer os mesmos, já
que este sistema adapta-se com os antígenos, criando anticorpos específico
para combater o mesmo e também pode manter uma memória dos patógenos
reconhecidos para combater os mesmos, caso haja um novo ataque no futuro.
15
Baseando-se principalmente na idéia de sistema adaptativo foi que os sistemas
imunológicos artificiais (SIA) surgiram com o propósito de resolver um determinado
problema baseado nas características do próprio problema, aplicando-a na obtenção da
solução.
2.2
Estudo sobre a natureza através da computação.
Este ramo da computação, ao contrário da computação inspirada na natureza, busca
utilizar mecanismos computacionais para o estudo de organismos artificiais, ou seja, estudar
novos fenômenos que podem nunca ter sido observados na natureza, mas que possuem
características suficientes para serem denominados e/ou qualificados de “naturais”.
O estudo da natureza através da computação busca simular e emular fenômenos
naturais de maneira não-determinística.
Quando se fala em simulação, o estudo busca desenvolver, ou seja, criar fenômenos
que podem vir a ser semelhantes ou até idênticas as existentes na natureza, mas de uma forma
virtual, como a criação de uma imagem de determinadas plantas existentes na natureza, ou até
mesmo de algumas espécies que já se extinguiram, ou ainda do que poderia existir
futuramente de acordo com as condições reais existentes hoje na natureza, por exemplo.
Na emulação, o ato de emular se dá ao fato de criar fenômenos similares
(concorrentes) aos encontrados na natureza, por exemplo, as colônias de formigas, que são
estudos de uma característica presente na natureza e que, através de estudos ciêntificos, foi
possível que se utilizasse a mesma técnica para determinados problemas, como forma de
solução e sem ter que utilizar literalmente as formigas para tal função.
Este estudo contém duas principais frentes de pesquisa, são elas:
•
Vida artificial;
•
Geometria computacional (fractal) da natureza;
A pesquisa em vida artificial e a geometria computacional da natureza vêm permitindo
a criação de modelos realistas da natureza e a simulação e/ou emulação de diversas espécies
de plantas e animais, inclusive em mídias como cinema e televisão, e têm contribuído para a
síntese e conseqüente estudo de fenômenos naturais [CASTRO, 2007].
16
2.2.1 Vida artificial.
A vida artificial tem como objetivo tentar recriar a vida natural de uma maneira virtual
ou sintética, ou seja, por eventos que não são causados pela natureza e sim pela criação do
homem através de sistemas complexos.
Estas pesquisas surgiram na década de 80 pelo pesquisador Cristopher Lagon e
diferente da Computação Inspirada na Natureza ela não busca resolver problemas encontrados
em determinadas áreas cientificas, mas procura demonstrar de maneira artificial, a vida como
forma de estendê-la melhor. A vida artificial busca dar ênfase ao desenvolvimento cientifico.
2.2.2 Geometria computacional (fractal) da natureza.
O termo “fractal” que do latim significa fractus, que corresponde ao verbo quebrar e
apesar de ser um estudo já há bastante tempo estudado por matemáticos e cientistas, recebeu
este nome através do matemático Benoit Mandelbrot (1983).
Mandelbrot não só criou o termo “fractal” como também elaborou padrões e modelos
de fractais.
A geometria fractal surgiu como um meio de revolucionar a geometria euclidiana, na
qual só é possível modelar objetos artificiais. Esta nova geometria busca formas irregulares e
fragmentadas da natureza, como fonte de inspiração para a criação de imagens artificiais das
mesmas, além de um estudo de formas “possíveis” de vida no planeta.
17
3. GEOMETRIA FRACTAL
A partir da obra “The Fractal Geometry of the Nature” (A Geometria Fractal da
Natureza), foi que o matemático Benoit Mandelbrot, no ano de 1983, criou a chamada
geometria fractal.
A também conhecida Geometria da Natureza, através de suas irregularidades e
estruturas complexas, teve um grande avanço na computação gráfica, tornando-se um grande
aliado na construção de imagens e animações, além de estruturas naturais com grande
realismo.
Com esta eficiência, a utilização do fractal na computação gráfica trouxe um grande
avanço em pesquisas científicas, sendo de grande utilidade para a criação de paisagens
naturais, plantas existentes ou mesmos extintas, estudo de processos de desenvolvimento e
crescimento.
A Geometria Fractal auxiliou também na modelagem e síntese de diversos padrões e
formas naturais, através de grandes estudiosos.
Através das descobertas de novas formas geométricas, foi possível criar padrões e
algoritmos que auxiliassem na formação de tais fractais, como o Sistema-L, criado por A.
Lindenmayer. Além desta técnica, há muitas outras existentes, como os Sistemas de Funções
Iterativas (Iterated Function Systems).
Na natureza, observamos que suas formas são infinitamente irregulares, não se
assemelhando em nada a geometria euclidiana ou geometria clássica, que é encontrada em
objetos uniformes cunhados artificialmente.
A Geometria Fractal tem como principal objetivo ser útil na representação da natureza
como terrenos, plantas, nuvens, montanhas, raios, arbustos, costas marítimas, ou até mesmo
de organismos complexos como pulmões, cérebro, rins, etc.
Em resumo, os fractais são irregulares, contendo o mesmo grau de irregularidade em
todas as escalas, além de poderem ser auto-similares, ou seja, os fractais parecem os mesmos
quando observado de muito perto ou a distância.
Um exemplo bastante encontrado em literaturas para descrever a auto-similaridade na
Natureza de maneira intuitiva é a representação do brócolis (Figura 1), sendo a primeira
imagem um brócolis fotografado por inteiro e na segunda imagem, apenas uma pequena parte
retirada do brócolis, onde a menor parte sofre muito poucas variações sobre a imagem do
todo:
18
Figura 1 - Exemplo de auto-similaridade na natureza [Castro, 2007].
Há dois tipos de auto-similaridade com uma sutil diferença entre si:
3.1
Auto-similaridade estrita;
Para um fractal, cujas partes sejam uma cópia exata (réplica) de seu todo, a auto-
similaridade é dita estrita. Vejamos o fractal dado na figura 2, no qual suas partes são
idênticas à sua imagem por inteiro:
Figura 2 - Exemplo de auto-similaridade estrita [Castro, 2007].
3.2
Auto-similaridade estatística (auto-afinidade);
A Auto-similaridade estatística, também conhecida como auto-afinidade tem uma
ligeira diferença em relação à auto-similaridade estrita, pois no exemplo abaixo percebe-se
que a imagem do todo da árvore é formada a partir do tronco por duas partes com afinidade
com a arvore como um todo. Sendo estas “filiais” com afinidade ao todo da árvore, define-se
19
que a propriedade de auto-similaridade é restringida as filiais desta árvore, pois não mantêm
fixas as proporções originais da mesma, como mostra a figura 3.
Figura 3 - Exemplo de auto-similaridade estatística ou auto-afinidade [Castro, 2007].
3.4
Os primeiros fractais
Mesmo antes de se pensar na existência ou do auxílio da computação como forma de
desenvolver as imagens de forma mais prática, deixando a parte de processamento para que a
máquina se encarregue de desenvolver tal papel, já havia estudos e funções sendo
desenvolvidas por estudiosos, na maioria matemáticos, que buscavam resolver problemas
ainda antes não questionados ou resolvidos.
Os primeiros fractais foram descobertos por K. Weierstrass, G. Cantor, H. von Koch,
W. Sierpinski, entre outros.
O primeiro fractal foi descoberto por K. Weierstrass em 1861, que descobriu uma
função contínua que não é diferenciável em ponto algum, ou seja, uma curva constituída
somente por “cantos”.
Apesar de ter sido uma teoria genérica, esta função deu origem a várias outras idéias,
auxiliando na expansão dos estudos sobre fractais.
3.5
O conjunto de cantor
O fractal conhecido como Conjunto de Cantor foi introduzido pelo russo Georg
Ferdinand Ludwig Philip Cantor em 1883. É obtido a partir da subdivisão do intervalo, ou
seja, de maneira prática o processo se dá como visto na figura 4, inserir uma linha, logo após,
20
quebrar esta linha em três partes iguais, retirando a parte do meio gerando assim um novo
passo.
A seguir, deve-se repetir o mesmo procedimento para as duas partes agora existentes,
gerando um novo passo com uma quantidade exponencialmente maior de linhas. Este
processo se dá de forma infinita.
Figura 4 - Exemplo dos primeiros passos do Conjunto de Cantor [Castro, 2007].
Segundo Castro, o Conjunto de Cantor tem algumas características interessantes:
Não possui comprimento algum ou interior;
Cada uma de suas partes é constituída basicamente de buracos;
É totalmente formado por pontos desconexos;
Contém a mesma quantidade de pontos que a curva da qual ele é
derivado;
Cada um de seus pontos é um ponto limite, ou seja, existe uma quantidade
infinita de outros pontos do conjunto na sua vizinhança.
3.6
A curva de Koch (floco de neve)
Outro fractal, conhecido como Curva de Koch, foi inventado pelo matemático sueco
Niels Fabian Helge Von Koch, em 1904 tem como característica dividir uma linha reta em
três partes iguais, pegando a terceira parte (central) e substituindo-a por duas de tamanhos
iguais a desta parte substituída, formando um triângulo eqüilátero sem base. No segundo
passo, será efetuado o mesmo processo, separando as novas linhas retas em três partes iguais e
substituindo a terceira parte por duas partes, formando um outro triângulo eqüilátero sem base
para cada linha reta.
21
Figura 5 - Exemplo dos primeiros passos da Curva de Koch [Castro, 2007].
Segundo Castro, a Curva de Koch tem algumas características interessantes:
No limite a curva de Koch não possui segmento algum de reta; a curva é
inteiramente constituída por cantos;
Portanto a curva não apresenta derivada (tangente) em ponto algum;
Embora ela se inicie a partir de uma reta de comprimento V, seu
comprimento é infinito;
No passo t a curva possui 4t segmentos, cada qual com comprimento 1/3t.
Portanto, o comprimento total da curva é (4/3)t;
Dando seqüência a curva de Koch, será notado que em um determinado
momento esta curva tornará uma ilha, mas que sua implementação
continuará sendo infinita, ou seja, uma curva de comprimento infinito pode
ser colocada em uma área finita [Castro, 2007].
Figura 6 - Exemplo da Ilha de Koch, também conhecida como Floco de Neve [Castro, 2007].
22
3.7
O triângulo de Sierpinski
O matemático V. Sierpinski introduziu seu fractal no ano de 1916, o qual ficou
conhecido como Triângulo de Sierpinski.
Embora os princípios adjacentes já serem conhecidos por milênios, a idéia de
implementação de uma forma fractal se torna mais recente, na qual divide-se um triângulo
eqüilátero em quatro pequenas partes dentro dele, seguindo o mesmo procedimento para os
demais passos, pegando uma das pequenas partes e dividindo-a em outras quatro menores
partes dentro desta, obtendo pequenas cópias do todo, como na figura 7.
Figura 7 - Exemplo dos primeiros passos na construção do Triângulo de Sierpinski.
3.8
A curva de Peano
Por volta do ano de 1800, Giuseppe Peano e David Hilbert apresentaram uma curva
capaz de preencher o espaço, no qual este fractal efetua um processo de preenchimento dos
espaços não sendo necessariamente dentro da área fechada. Este fractal ficou conhecido como
a Curva de Peano.
Na Curva de Peano, conhecida como a curva que preenche o espaço, cada passo no
processo de construção será consistido por nove pequenos segmentos de linhas para cada
linha gerada através do passo anterior. Como no exemplo abaixo, a Curva de Peano procura
preencher os espaços ainda não utilizados ocupando, a cada iteração um espaço maior, porém
sem expandir sua dimensão.
23
Figura 8 - Exemplo dos primeiros passos na construção da Curva de Peano [Castro, 2007].
Este fractal se baseia na idéia de organização de organismos, pois um organismo deve
ser feito para suportar suas substâncias necessárias como água, sangue e oxigênio. Este
organismo, apesar de estar preenchido por suas substancias terá, através de sua estrutura de
organização, uma otimização no espaço para ser usado em algumas funções.
A Curva de Peano trouxe certo desconforto para os matemáticos da época, pois, hoje
se sabe que o mesmo pode auxiliar na resolução de problemas de como organizar uma
estrutura complicada de maneira eficiente [Castro, 2007].
3.9
Dimensão euclidiana e dimensão fractal
A dimensão da qual temos conhecimentos através dos primeiros anos de estudos
escolares, apresenta dimensões conhecidas através da geometria euclidiana, usualmente
denominada dimensão topológica. Como se sabe, esta dimensão mostra que pontos possuem
dimensão 0, linhas e curvas possuem dimensão 1, planos e superfícies possuem dimensão 2 e
sólidos possuem dimensão 3.
De forma simplificada, a dimensão topológica é definida como um conjunto possuindo
dimensão d se d variáveis independentes (coordenadas) são necessárias para descrever a
vizinhança de cada ponto [Castro, 2007].
Quanto à dimensão fractal, a complexidade em definí-lo torna-se um problema, pois os
fractais observados acima como a Curva de Koch, por exemplo, contêm dimensões nos quais
24
os pontos não são definidos entre uma dimensão e outra na perspectiva da geometria
Euclidiana, podendo ser um número entre as dimensões 1 e 2, ou seja, o comprimento entre
quaisquer dois pontos da curva é infinito, pois entende-se que esta dimensão é muito grande
para ser unidimensional e pequena demais para ser bidimensional [Castro, 2007].
3.10 Sistemas de Lindenmayer (Sistemas-L)
A. Lindenmayer, biólogo alemão introduziu em 1968 um conceito matemático, na
intenção de simular o desenvolvimento de organismos multicelulares (autômatos celulares),
que ficou conhecido como Sistemas-L (L-Systems) ou algoritmos de desenvolvimento
(developmental algorithms).
O desenvolvimento multicelular consiste na geração de estruturas através da divisão,
crescimento, diferenciação e morte celular. Ele corresponde a uma série de mudanças que os
organismos sofrem durante sua passagem do estado embrionário para a maturidade. [Castro,
2007].
t = 8, δ = 22.5º
ω: G
G = F+[[G]-G]]-F[-FG]+G
F = FF
Figura 9 - Exemplos de plantas geradas através da técnica do Sistema de Lindenmayer.
25
A teoria matemática do Sistema-L foi desenvolvida tendo como principal objetivo a
modelagem de plantas, além de reconstrução de plantas extintas ou projetos de novas
variedades de plantas, criação de paisagens, projetos ornamentais e ilustração botânica.
Porém, com sua praticidade na geração de imagens realistas, o Sistema-L também é utilizado
para o auxilio nos estudos científicos de um modo geral, como desenvolvimento biológico, a
microbiologia, biodiversidade, agronomia e ecologia, além de outros.
3.10.1
Sistema-DOL (DOL-Systems)
As formas geométricas (fractais) a serem estudadas são palavras em uma linguagem
formal paralela. As gramáticas em Sistemas-L são similares às gramáticas formais
apresentadas
anteriormente,
porém
as
produções
são
aplicadas
simultaneamente
(paralelamente) e não existe distinção entre símbolos terminais e não-terminais [Castro,
2007].
Um exemplo de Sistema-L pode ser observado da seguinte forma, sendo o alfabeto
G = {a,b,c}, onde c é o axioma (ponto de partida).
•
a→c
•
b → ac
•
c→b
Partindo-se do axioma (ponto de partida) que consiste na letra c, o primeiro passo é
substituir o axioma utilizando a regra 3 (c → b). Portanto o axioma c é substituído por b. No
segundo passo substitui-se b por ac utilizando a regra 2 (b → ac), e assim por diante de
acordo com a Tabela 01. Este processo de aplicação das regras é denominado de processo de
derivação ou de reescrita, no qual se dá por um processo infinito, contendo reescrita de forma
infinita [Castro, 2007].
26
Iteração
Palavra
0
c
1
b
2
ac
3
cb
4
bac
5
accb
6
cbba
7
bacaccb
8
accbcbbac
9
cbbacbacaccb
10
bacaccbaccbcbbac
Tabela 01 – Exemplo de Iteração partindo do axioma, ao qual consiste a letra c.
3.11 Sistemas de funções iterativas (IFS – Iterated Function
Systems)
Uma outra forma de se construir fractais é através do Sistema de Funções Iterativas,
também conhecido como mapeamentos contrativos, que foi desenvolvido a partir de 1986 por
J. Hutchinson, M. Barnsley e S. Demko.
O IFS (do inglês, Iterated Function Systems), foi criado como uma ferramenta para
geração de uma imagem criada através de uma aplicações recursivas de uma imagem sobre si
mesma, executando em um determinado número de iteração especificado a princípio, onde ao
final dessa iteração será gerado uma imagem através de uma forma geométrica.
Uma propriedade importante de contrações é que independentemente do ponto inicial,
a aplicação iterativa do mapeamento contrativo resulta sempre na convergência para o mesmo
ponto, denominado de atrator [Castro, 2007].
27
Para se entender melhor sobre os passos de funcionamento de uma transformação
através do IFS, deverá ser compreendido que, uma transformação sobre X é uma função
f: X → X que especifica exatamente um ponto f(x) X a cada ponto x X.
Sendo assim, a forma w(x1,x2) = (ax1 + bx2 + e, cx1 + dx2 + f), onde a, b, c, d, e, e f
são números reais é denominada de transformação afim (bi-dimensional).
Em notação matricial:
 x1   a b  x1   e 
  +   = Ax + t
w( x ) = w  = 
x
c
d
 x2   f 
 2 
(01)
w
a
b
c
d
e
f
p
1
0
0
0
0.16
0
0
0.01
2
0.85
0.04
-0.04
0.85
0
1.6
0.85
3
0.2
-0.26
0.23
0.22
0
1.6
0.07
4
-0.15
0.28
0.26
0.24
0
0.44
0.07
Tabela 02 – Tabela específica para criação do Arbusto de Barnsley.
28
Figura 10 - O Arbusto de Barnsley, gerado pelo código da Tabela 02.
Com a utilização da equação (01) unindo-se aos valores padrão da tabela 02, tornou-se
possível gerar, através de um determinado número de interação realizado no algortimo, o
arbusto de Barnsley.
Este resultado também pode ser armazenado em matrizes, sendo possível a sua
reutilização como será observado mais adiante, no decorrer do trabalho.
Algoritmo genérico para implementação de um IFS:
procedimento [ ] = RIFS (max_it, x0, W, p)
x ← x0;
t←1
enquanto t < Max_it faça,
j ← selecionar (p) // selecionar um mapeamento j
// com uma probabilidade pj
x ← x j (x)
desenhar(x)
t ←t + 1
fim enquanto
fim procedimento
// aplique mapeamento j em x
// imprima o ponto x
Estas transformações possuem propriedades algébricas e geométricas importantes. As
quatro principais transformações afim são translação, escalamento, reflexão e rotação.
29
4. CONCEITOS SOBRE COMPUTAÇÃO GRÁFICA
A Computação Gráfica é uma área da Ciência da Computação que, derivada de outras
áreas como Física, Matemática, Engenharia, Arquitetura, etc., estuda a geração, manipulação
e interpretação de modelos e imagens de objetos utilizando computadores para dados em
dispositivos gráficos e vice-versa.
Figura 11 - Modelo Conceitual sobre Computação Gráfica [Vianna, 2002].
Imagens Gráficas são basicamente formadas por códigos que contêm cálculos para a
interpretação do computador na geração da imagem.
Mesmo utilizando de ferramentas que facilitam a geração de tais imagens, é
extremamente necessário ter o entendimento sobre os conceitos básicos da Computação
Gráfica para a execução deste projeto.
30
Para a geração das imagens, o algoritmo apoiado por uma ferramenta de programação
matemática, gera imagens através de combinações de cálculos de pequenos pontos coloridos
conhecidos como pixels ou pontos, no qual são associados números à esses pontos como
forma de coordenadas (x,y).
Será visto a seguir e utilizado para a manipulação das imagens gráficas fractais no
plano 2D, quatro transformações essenciais da computação gráfica, são elas a translação,
escalonamento, reflexão e rotação.
4.1 Translação
A translação é a alteração da posição inicial de um ponto através da soma de
constantes, deslocando suas coordenadas, é normalmente aplicada sobre todos os pontos de
uma figura, de maneira a possibilitar a sua movimentação no espaço.
Para a translação das imagens gráficas fractais utilizadas neste projeto, será utilizado a
seguinte fórmula:
 x`  x  Tx 
P`= P + T =   =   +  
 y`  y  Ty 
(02)
Onde P(x,y), sendo P um vetor com coordenadas de vários pontos responsáveis pela
geração de uma imagem.
T(Tx,Ty), sendo T um vetor com valores de deslocamento dos pontos em P.
P’ é o resultado da soma dos pontos contidos no vetor P com unidades contidas no
vetor de deslocamento T.
31
Ou seja, x e y são as coordenadas da localização de um ponto e Tx é uma variável de
unidades em relação ao eixo x, assim como Ty é uma variável de unidades em relação ao eixo
y.
Figura 12 - Exemplo de translação
4.2 Escalonamento
O escalonamento é uma transformação, onde o resultado da multiplicação das
coordenadas de um ponto por valores de variáveis de escalonamento, resulta na alteração do
tamanho da imagem de um todo em relação a imagem original, ou seja, as coordenadas x e y
de cada ponto será multiplicada pelas variáveis de escalonamento Sx e Sy respectivamente,
produzindo então as coordenadas transformadas x’ e y’.
32
[x`
y `] = [x
S x
y] 
0
0
S y 
(03)
A alteração dos valores destes pontos, que juntamente formam a imagem, não resultam
em uma imagem diferente ou deforme, mas apenas na alteração do tamanho desta imagem,
sendo que, caso os valores de Sx e Sy forem maiores que um, haverá o aumento do tamanho
da imagem. Caso estes valores forem menores que um, a imagem será reduzida.
Figura 13 - Exemplo de escalonamento
4.3 Reflexão
Reflexão é a obtenção da visualização da imagem por um outro ângulo, como se
observasse esta através de um espelho.
A obtenção do reflexo da imagem se faz através de cálculos da coordenada dos pontos
que compõem a imagem gráfica fractal.
33
Para se obter o resultado esperado nesta transformação, é necessário que o vetor que
contenha as coordenadas dos pontos desta imagem P(x,y), seja multiplicado pela matriz
R(-1,0;0,1) resultando no vetor transformado P’(x’,y’).
 x`  x  − 1 0
P`= P * R =   =   

 y `  y   0 1 
(04)
Figura 14 - Exemplo de reflexão
4.4 Rotação
A rotação é o giro de um determinado ângulo de um ponto em torno de um ponto de
referência, não havendo alteração da distância entre eles. Estes ângulos são comumente
encontrados com valores fixos como 90° e 180°, porém há a possibilidade de efetuar a rotação
34
para qualquer valor de ângulo, desde que seja respeitada a regra da função de multiplicação de
vetores de coordenadas vista a seguir.
 x`  x   cos(θ ) sen(θ )
 y` =  y  − sen(θ ) cos(θ ) 
    

(05)
Figura 15 - Exemplo de rotação da imagem (rotacionando a folha 30º sentido horário)
35
5. APLICAÇÃO DE TECNICAS DE GEOMETRIA FRACTAL
Com a combinação entre Técnicas de Geometria Fractal, entendimento sobre
conceitos de Computação Gráfica e uma ferramenta de programação matemática, para
geração das imagens, tornou-se possível desenvolver uma combinação de reprodução destas
imagens possibilitando construir, por exemplo, uma árvore utilizando as informações de uma
folha contidas em um vetor.
5.1 Criação de árvore utilizando o Sistema-L
Para a criação do algoritmo de criação de imagens fractais utilizando o método de
Sistemas-L, houve uma facilidade em sua construção, pois na ferramenta de programação
matemática há um auxilio na geração de linhas a partir de dois pontos dados como
coordenada. Porém, esta solução da ferramenta no intuito de auxiliar o usuário da mesma,
torna-se pouco flexível quando se necessita aplicar cálculos de novas coordenadas como as
utilizadas neste projeto (translação, escalonamento, reflexão e rotação), no intuito de se gerar
uma nova imagem, reaproveitando as informações da imagem original.
Para que haja um maior aproveitamento da imagem é necessário obter a coordenada
dos pontos ou pixels.
Para tal problema, houve a necessidade de se armazenar todo o percurso de um ponto a
outro dos galhos e folhas em uma matriz.
Onde existia a linha criada automaticamente pela ferramenta de programação
matemática, houve um mapeamento e gravação dessas coordenadas para então utilizá-la
posteriormente.
36
Figura 16 – Exemplo de sistemas L
(a) galhos e folhas gerados com linhas
(b) criado através de plotagem
Através do processamento para a criação da imagem fractal, baseada no modelo do
Sistema-L e o armazenamento destes pontos em uma matriz, torna-se possível criar outras
imagens a partir destas coordenadas, sem a necessidade de reproduzi-las novamente, gerando
uma nova matriz, mas apenas reutilizando estes pontos para criar imagem semelhantes, porém
com tamanho, posicionamento e graus diferentes em relação a imagem original.
37
Figura 17 – Imagem gerada através da duplicação da figura gerada pelo Sistema-L, na forma de
reflexo.
Com o armazenamento das coordenadas de cada ponto ou pixel em um matriz, tornase possível a geração de imagens das mais variadas formas sem a necessidade de se gerar uma
matriz para cada imagem.
Reutilizando a matriz gerada e adicionando os conceitos de Computação Gráfica,
torna-se possível a geração de imagens como a da Figura 17.
5.2 Criação de árvore utilizando o Sistema de Funções Iterativas
Para a criação de uma imagem em Sistema de Funções Iterativas, utilizou-se um
algoritmo responsável pela criação do Arbusto de Barnsley.
38
Com o armazenamento em uma matriz destas coordenadas dos pontos ou pixels
responsáveis pela criação da imagem do Arbusto de Barnsley, tornou-se possível à criação de
uma árvore, apenas com a reutilização destas coordenadas.
Torna-se possível observar que a idéia de reaproveitamento das coordenadas, geradas
através de uma interação pode ser praticada para ambos os modelos de geração de fractais
utilizados neste trabalho.
Figura 18 – Reprodução de várias folhas formando uma árvore, através das coordenadas dos
pontos ou pixels de uma folha, armazenados em uma matriz.
Para a elaboração da árvore, através do Sistema de Funções Iterativas, utilizou-se de
um determinado tempo para se resolver o problema de harmonia entre as folhas ou arbustos,
buscando resultar este grupo de folhas em uma árvore. Com isso houve a necessidade de se
criar um caule, além de escalonar, transladar e rotacionar as folhas ou arbustos, em busca de
um melhor posicionamento.
39
5.3 Criação das imagens unindo os modelos fractais em um mesmo
algoritmo
No momento da união dos algoritmos com métodos distintos, Sistema de Funções
Iterativas e o Sistema-L, há a necessidade de se definir um tamanho padrão para ambas as
imagens, tendo também a necessidade de se corrigir o algoritmo responsável pela criação do
caule, onde o tamanho do mesmo deve acompanhar as folhas geradas pelo algoritmo de
Sistemas de Funções Iterativas.
Com o tamanho das imagens já definidos nos algoritmos, o próximo passo é o
posicionamento das imagens, de forma que cada uma ocupe seu plano sem que não haja uma
imagem sobrescrevendo outra.
(a)
(b)
(c)
(d)
Figura 19 - Imagens geradas a partir do código
(a) Imagem gerada através do código contendo o modelo de Sistema de Funções Iterativas;
(b) Imagem gerada através do código contendo o modelo de Sistema-L;
(c) Imagem gerada através do código contendo o modelo de Sistema-L;
(d) Imagem gerada através do código contendo o modelo de Sistema de Funções Iterativas;
Logo após a criação do algoritmo que gera a figura 20, torna-se necessário apenas o
armazenamento deste código gerador da imagem, não necessitando o armazenamento da
imagem gerada, que por sua vez ocupa mais espaço de armazenamento de dados. Sendo
40
assim, será poupado espaço de armazenamento, mas haverá maior exigência da máquina ou
computador sempre que houver a necessidade de se gerar a imagem novemente.
5.4 Criação da imagem através da Ferramenta PAINT
Com uma ferramenta específica para tratamento de imagens como a ferramenta básica
PAINT da Microsoft, o ato de construir uma imagem torna-se uma tarefa mais prática e
iterativa, onde o usuário não necessita de conhecimentos sobre codificação de algoritmos,
pois as ferramentas deste gênero dão ao usuário, a sensação de estar manuseando de fato um
objeto.
Com a utilização de ferramentas de construção de imagens iterativas, a geração de
uma imagem consome menos tempo de processamento de máquina em relação à geração de
imagens através de algoritmos, utilizando modelos de criação de imagens fractais onde o
mesmo baseia-se em algoritmos recursivos, que por sua vez, são algoritmos responsáveis por
aproveitar mais tempo de processamento e menos trabalho humano, ou seja, transferir todo o
trabalho para a máquina ou computador.
(a)
(b)
(c)
(d)
Figura 20 - Imagem gerada através da ferramenta PAINT, de forma prática e interativa.
(a) Imagem gerada no PAINT de forma interativa simulando o Sistema de Funções Iterativas;
(b) Imagem gerada no PAINT de forma interativa, simulando o Sistema-L;
(c) Imagem gerada no PAINT de forma interativa, simulando o Sistema-L;
(d) Imagem gerada no PAINT de forma interativa simulando o Sistema de Funções Iterativas;
41
Através desta prática de criação de imagens de forma prática, há a necessidade de se
armazenar esta imagem, ao contrário da prática vista anteriormente, onde se armazena o
algortimo responsável por gerar a imagem e não a imagem gerada.
Com tal prática, torna-se necessário a utilização de maior espaço em armazenamento de
dados, porém sendo menos exigido o tempo de processamento de tal máquina ou computador.
5.5 Comparativo entre os dois métodos utilizados, para a criação de
uma mesma imagem.
Para testar o tempo de processamento necessário na criação de imagens fractais
através de uma ferramenta de programação matemática, responsável por gerar imagens
através de algoritmos e compará-las ao tempo de criação de imagens semelhantes, porém
utilizando-se da ferramenta Paint para criá-las, foi utilizado um Notebook da HP (Compaq
nx6125) com as seguintes configurações:
Hardware:
•
Processador 1.6 GHz;
•
Memória RAM DDR (333 Mhz) de 512 MB (duas de 256 MB cada);
•
Placa de video compartilhada (NVIDIA) de 128 MB;
•
Hard Disk com capacidade de 40 GB.
•
Sistema Operacional Windows XP Professional (Service Pack 3);
•
Ferramenta de programação matemática;
•
Paint (Microsoft).
Software:
42
Para a obtenção dos resultados obtidos na Tabela 03, foi efetuado testes através da
geração da Figura 19 por uma ferramenta de programação matemática.
EXECUÇÃO
1
2
3
4
MÉDIA FINAL
TEMPO DE
PROCESSAMENTO
(EM SEGUNDOS)
TEMPO DE
PROCESSAMENTO
(PADRÃO HH:MM:SS)
83,953
83,312
82,281
84,859
83,60125
00:01:24
00:01:23
00:01:22
00:01:25
00:01:23
Tabela 03 – Tabela de testes de processamento para criação das imagens fractais através de uma
ferramenta de programação matemática.
No caso da criação da mesma imagem utilizando a ferramenta PAINT, não há um
consumo de tempo de processamento relevante da máquina ou computador, já que o mesmo é
uma ferramenta interativa.
Vale lembrar que o arquivo .JPG, gerado pela ferramenta PAINT é a própria imagem
gerada, enquanto que o arquivo .M é o código que contém apenas o algoritmo responsável
pela geração da imagem.
NOME DA
IMAGEM
GERADO
TAMANHO
GERADO
TIPO DE
DOS
ATRAVÉS DO
ATRAVÉS
ARQUIVO
MÉTODO
DO MÉTODO
ARQUIVOS
GERADO
TRADICIONAL FRACTAL
(EM KB)
Figura 19 (a)
Figura 20 (a)
X
X
.M
5 KB
.JPG
69 KB
TAMANHO
DOS
ARQUIVOS
(EM %)
7,24% do
tamanho
total do
arquivo .JPG
1380% maior
que o arquivo
.M
Tabela 04 – Testes comparativos com as imagens (a) de ambos os métodos de criação.
43
NOME DA
IMAGEM
GERADO
GERADO
TAMANHO
TIPO DE
ATRAVÉS DO ATRAVÉS DO
DOS
ARQUIVO
MÉTODO
MÉTODO
ARQUIVOS
GERADO
TRADICIONAL
FRACTAL
(EM KB)
Figura 19 (b)
Figura 20 (b)
X
X
.M
7 KB
.JPG
150 KB
TAMANHO
DOS
ARQUIVOS
(EM %)
4,66% do
tamanho
total do
arquivo .JPG
2143% maior
que o arquivo
.M
Tabela 05 – Testes comparativos com as imagens (b) de ambos os métodos de criação.
NOME DA
IMAGEM
GERADO
GERADO
TAMANHO
TIPO DE
DOS
ARQUIVO
MÉTODO
MÉTODO
ARQUIVOS
GERADO
TRADICIONAL
FRACTAL
(EM KB)
Figura 19 (c)
Figura 20 (c)
X
X
.M
7 KB
.JPG
147 KB
TAMANHO
DOS
ARQUIVOS
(EM %)
4,76% do
tamanho
total do
arquivo .JPG
2100% maior
que o arquivo
.M
Tabela 06 – Testes comparativos com as imagens (c) de ambos os métodos de criação.
NOME DA
IMAGEM
GERADO
TAMANHO
GERADO
TIPO DE
DOS
ARQUIVO
MÉTODO
MÉTODO
ARQUIVOS
GERADO
TRADICIONAL
FRACTAL
(EM KB)
Figura 19 (d)
Figura 20 (d)
X
X
.M
5 KB
.JPG
70 KB
TAMANHO
DOS
ARQUIVOS
(EM %)
7,14% do
tamanho
total do
arquivo .JPG
1400% maior
que o arquivo
.M
Tabela 07 – Testes comparativos com as imagens (d) de ambos os métodos de criação.
Importante ressaltar também que, havendo a necessidade de aumentar o número de
imagens, esta alteração não afeta o tamanho do arquivo (contendo o código) .M da mesma
proporção em que será afetado o tamanho do arquivo (contendo a imagem) .JPG.
44
6. CONCLUSÃO
Como demonstrado, com os avanços contínuos da tecnologia e o crescimento
exponencial da capacidade dos hardwares, torna-se bastante aceitável o fato de se aproveitar
cada vez mais estas tecnologias, ao mesmo tempo poupando espaço de armazenamento de
dados, possibilitando um maior número de códigos responsáveis por gerações de imagens.
Com a combinação de modelos de geometria fractal, o Sistema de Funções Iterativas e
o Sistema-L, aliado aos estudos de conceitos de computação gráfica resultaram na
possibilidade de se criar imagens fractais, permitindo o reaproveitamento das mesmas
armazenando as informações das coordenadas destas imagens em matrizes. Através destas
informações, há possibilidade de reprodução de várias outras imagens provenientes da
original, apenas pela inserção de algumas linhas de códigos.
Porém, o resultado da geração destas imagens pode conter um crescimento
considerável.
Confrontando-se com um problema ainda existente no meio da informática, como
enviar um arquivo por e-mail, sabendo-se que há um determinado limite de tamanho deste
arquivo para envio, variando de acordo com cada prestador deste tipo de serviço, poderia se
pensar em utilizar fractais para compactação da imagem a ser enviada, embora não tenha sido
o problema abordado no trabalho.
O mesmo problema não ocorre quando se trata do arquivo que contém o algoritmo
responsável pela geração desta imagem, desde que haja por parte do receptor, a ferramenta
responsável pela transformação deste código em uma imagem.
45
7. REFERÊNCIAS BIBLIOGRÁFICAS
DEITEL, H.M; DEITEL P.J. Java: Como programar. 4ª Ed. Porto Alegre: Bookman, 2003. 893p.
CASTRO, Leandro Nunes; CAMPELLO, Ricardo J. G. B.; HRUSCHKA, Eduardo R.; ROSATELLI, Marta C..
Computação Natural: Uma Breve Visão Geral. Programa de Mestrado em Informática da Universidade
Católica de Santos, Santos, S.P., BR. Disponível via URL pelo LABORATÓRIO DE INTELIGÊNCIA
COMPUTACIONAL
APLICADA
em:
http://www.eletrica.ufsj.edu.br/~nepomuceno/ensino/complex/castro_nanobio.pdf. Acesso em 08/03/2008.
LABORATÓRIO VIRTUAL DE COMPUTAÇÃO NATURAL.
Geometria Fractal. Disponível via URL em: http://lsin.unisantos.br/lvcon. Acesso em 17/05/2008.
CASTRO, Leandro Nunes. Fundamentals of Natural Computing: Basic Concepts, Algorithms and
Applications. Local: Chapman & Hall/Crc, 2007.
CASTRO,
Leandro
Nunes
de.
Inteligência
de
Enxame.
http://lsin.unisantos.br/lvcon/tema?tema=6. Acesso em 15/03/2008.
Disponível
UNIVERSIDADE FEDERAL DO PARANA.
Fractais:
Propriedades
e
Construção.
Disponível
http://gauss.mat.ufpr.br/~karas/geralic2003.pdf. Acesso em 25/05/2008.
via
via
URL
URL
em:
em:
ZUBEM, Professor Fernando J. Von. Introdução a Computação Natural. Disponível via FTP para download
em ftp://ftp.dca.fee.unicamp.br/pub/docs/vonzuben/ia013_1s07/topico8_07.pdf. Acesso em 18/06/2008.
PONTÍFICA UNIVERSIDADE CATÓLICA DO RIO GRANDE DO SUL. Origens da Computação Gráfica.
Disponível via URL em: http://www.inf.pucrs.br/~pinho/CG/Aulas/Intro/intro.htm. Acesso em 13/07/2008.
VIANNA,
Arlindo
Cardarett.
Computação
Gráfica.
Disponível
via
URL
em:
http://www.inf.ufes.br/~thomas/graphics/www/apostilas/CIV2801AcvCompGraf.pdf. Acesso em 27/07/2008.
VOLANTE, La Hoja. Disponível via URL em: http://www.uam.es/otros/hojavol/hoja12/fractales12.html.
Acessado em 10/10/2008.
MAPLE,
Introduction
to
MATLAB,
Disponível
via
URL
http://www.math.tamu.edu/%7Eboas/courses/math696/matlab-introduction.html. Acesso em 30/08/2008.
em:
MATCH WORKS, Accelerating the pace of engineering and science. Disponível via URL em:
http://www.mathworks.es/matlabcentral/index.html. Acesso em 06/09/2008.
46
8. ANEXOS
%##############################################################
% ALGORITMO RESPONSAVEL PELA GERACAO DA FIGURA 19 #
%##############################################################
%
%##############################################################
%
CRIAÇAO DO SISTEMA-L
#
%##############################################################
clear all;
clf;
aux = [];
%
tic %inicio da marcaçao do tempo
%
% Parte 0. Variaveis de Entrada
%===============================
% Inclusao de regras para a construçao das imagens
rule(1).vorher = 'F';
rule(1).danach = 'FF';
rule(2).vorher = 'G';
rule(2).danach = 'F-[[G]+G]+F[+FG]-G';
n_Rules = length(rule);
% angulo: '+' = rotaciona sentido anti-horario;
% angulo: '-' = rotaciona sentido horario.
alpha = 25; % (angulo)
% tamanho das linhas F e G
length_F = 0.5;
length_G = 0.1;
% inicializando o string
axiom = 'G';
% iteraçao (escolha somente de 1 a 7, >= 8
n_Repeats = 7;
% Parte 1. Calcular a STRING
%=================================
%####################################################
hold on % armazena todas as plotagens durante o processamento #
%####################################################
for i = 1:n_Repeats
axiomINcells = cellstr(axiom');
for j = 1:n_Rules
% encontrar todas as ocorrencias daquele axioma
hit = findstr(axiom, rule(j).vorher);
if (length(hit) >= 1)
for k = hit
axiomINcells{k} = rule(j).danach;
end
end
end
axiom = [];
for j = 1:length(axiomINcells)
% colocar todos os strings juntos
47
axiom = [axiom, axiomINcells{j}];
end
end
%
% Parte 2. - PLOTAR
%===================
% inicializaçao
xT = 0;
yT = 0;
aT = 0;
da = alpha/180*pi; % converter em raio
stkPtr = 1;
%
for i = 1:length(axiom)
cmdT = axiom(i);
switch cmdT
% é possivel adicionar multiplos casos aqui.
case 'F'
newxT = xT + length_F*cos(aT);
newyT = yT + length_F*sin(aT);
% plotar caracteristicas da linha
% plotagem original das linhas sem salvamento dos pontos
%line([yT newyT], [xT newxT],'color',[.3 .3 0], 'linewidth',2);
% inicio da coleta de pontos dos galhos
%alteraçao para salvar cada plotagem ponto-a-ponto dos galhos
for y = 1:200
aux = [newyT;newxT];
end;
%
var_vet_1 = aux;
var_vet_1 = var_vet_1 + [200;0]; % transladar a esquerda do eixo central
var_vet_2 = [-1,0;0,1]*aux;
% refletir imagem
var_vet_2 = var_vet_2 + [-200;0]; % transladar a direira do eixo central
%
plot(var_vet_1(1,1),var_vet_1(2,1),'g.');
plot(var_vet_2(1,1),var_vet_2(2,1),'r.');
% final da coleta de pontos
xT = newxT;
yT = newyT;
case 'G'
newxT = xT + length_G*cos(aT);
newyT = yT + length_G*sin(aT);
% plotar caracteristicas da linha
%line([yT newyT], [xT newxT],'color','g', 'linewidth',2);
% inicio da coleta de pontos das folhas
%alteraçao para salvar cada plotagem ponto-a-ponto das folhas
for y = 1:200
aux = [newyT;newxT];
end;
%
var_vet_1 = aux;
var_vet_1 = var_vet_1 + [200;0]; % transladar a esquerda do eixo central
var_vet_2 = [-1,0;0,1]*aux;
% refletir imagem
var_vet_2 = var_vet_2 + [-200;0]; % transladar a direira do eixo central
%
plot(var_vet_1(1,1),var_vet_1(2,1),'m.');
plot(var_vet_2(1,1),var_vet_2(2,1),'k.');
% final da coleta de pontos
xT = newxT;
48
yT = newyT;
case '+' % rotacionar sentido anti-horario
aT = aT + da;
case '-' % rotacionar sentido horario
aT = aT - da;
case '[' % salvar a posicao corrente
stack(stkPtr).xT = xT ;
stack(stkPtr).yT = yT ;
stack(stkPtr).aT = aT ;
stkPtr = stkPtr +1 ;
case ']' % retornar a posiçao de inicio (ultima posicao salva)
stkPtr = stkPtr -1 ;
xT = stack(stkPtr).xT ;
yT = stack(stkPtr).yT ;
aT = stack(stkPtr).aT ;
otherwise
disp('error');
return
end
end
%
%##############################################################
%
CRIAÇAO DOS CAULES
#
% #############################################################
caule_a = [];
caule_b = [];
y = 0.0;
x = 0.0;
k=1;
for i = 1:10
for j = 1:20
caule_a(k,:)=[x,y];
caule_b(k,:)=[x,y];
y = y + 1;
k=k+1;
end
x = x + 0.5;
y = 0.000;
end
[tamanho_vetor,qqcoisa] = size(caule_a(:,1));
caule_a(:,1) = caule_a(:,1)+70; % transladar caule
caule_b(:,1) = caule_b(:,1)-74; % transladar caule
for i=1:tamanho_vetor
plot(caule_a(i,1),caule_a(i,2), 'g.');
plot(caule_b(i,1),caule_b(i,2), 'g.');
end;
%
%#############################################################
%
CRIAÇAO DAS FOLHAS
#
%#############################################################
it_max = 5000;
x=[0;5];
%
M=[ 0, 0, 0, 0.16, 0, 0, 0.01;
0.85, 0.04, -0.04, 0.85, 0, 1.6, 0.85;
0.2, -0.26, 0.23, 0.22, 0, 1.6, 0.07;
49
-0.15, 0.28, 0.26, 0.24, 0, 0.44, 0.07];
%
vet = [];
for i=1:it_max
p= int8(1+(100-1)*rand);
if p<=M(1,7)*100
L=1;
else
if p>M(1,7)*100 & p<=M(1,7)*100+M(2,7)*100
L=2;
else
if p>M(1,7)*100+M(2,7)*100 & p<=M(1,7)*100+M(2,7)*100+M(3,7)*100
L=3;
else
if p>M(1,7)*100+M(2,7)*100+M(3,7)*100 & p<M(1,7)*100+M(2,7)*100+M(3,7)*100+M(4,7)*100
L=4;
end
end
end
end
w1(1,1)=M(L,1);
w1(1,2)=M(L,2);
w1(2,1)=M(L,3);
w1(2,2)=M(L,4);
w2(1,1)=M(L,5);
w2(2,1)=M(L,6);
x = w1*x+w2;
vet(:,i) = x;
end
%
for i=1:it_max
%==============================================================================
%=
FORMAR IMAGENS DAS FOLHAS A PARTIR DO CAULE FORMANDO UMA PLANTA
=
%==============================================================================
% folhas da arvore B (esquerda)
folha_d1_b = [-1,0;0,1]*vet(:,i); % receber informacao da imagem padrao
% rotacionar folha horario
folha_d1_b = [cos(50*(pi/180)),sin(50*(pi/180));-sin(50*(pi/180)),cos(50*(pi/180))]*folha_d1_b;
folha_d1_b = folha_d1_b + [0;1]; % transladar folha
folha_d1_b = folha_d1_b * 10;
% escalonar
%
folha_e1_b = [cos(-50*(pi/180)),sin(-50*(pi/180));-sin(-50*(pi/180)),cos(-50*(pi/180))]*vet(:,i);
folha_e1_b = folha_e1_b + [0;1]; % transladar folha
folha_e1_b = folha_e1_b * 10;
% escalonar
%
% escalonar
%
% escalonar
%
50
% escalonar
%
% escalonar
%
% escalonar
%
% escalonar
%
% escalonar
%
% escalonar
%
%
%
% reutilizar as folhas formadas para a criaçao de novas arvores
%
%folhas da arvore A (direita)
folha_d1_a = folha_d1_b + [72;0]; % transladar folha
folha_e1_a = folha_e1_b + [72;0]; % transladar folha
%
%folhas da arvore A (esquerda)
folha_d1_b = folha_d1_b + [-72;0]; % transladar folha
folha_e1_b = folha_e1_b + [-72;0]; % transladar folha
51
folha_d2_b = folha_d2_b + [-72;0];
folha_e2_b = folha_e2_b + [-72;0];
% transladar folha
% transladar folha
% transladar folha
% transladar folha
% transladar folha
% transladar folha
% transladar folha
% transladar folha
% transladar folha
% transladar folha
%
% plotar pontos das folhas da planta B
plot(folha_d1_b(1,1),folha_d1_b(2,1),'g.');
plot(folha_e1_b(1,1),folha_e1_b(2,1),'g.');
%
% plotar pontos das folhas da planta A
plot(folha_d1_a(1,1),folha_d1_a(2,1),'g.');
plot(folha_e1_a(1,1),folha_e1_a(2,1),'g.');
%
end
%
% sets data aspect ratio
daspect([1,1,1]);
%
tempo = toc
52

Visualizar - Polis Educacional

Transcrição

Documentos relacionados

fractais – a linguagem do caos

A MATEMÁTICA FRACTAL E O GEOGEBRA NO ENSINO

TETRAEDROS DE SIERPINSKI: UMA PROPOSTA DE

Engenharia de Software Processamento de Imagens

Programa - Logic - Engenharia de Sistemas

INVESTIGAÇÕES EM SALA DE AULA DE MATEMÁTICA: A

Sistema de computação

PIRATAS DO Vale do silício

Computação Gráfica - Departamento de Informática

Introdução a Realidade Virtual