Autômato Celular

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Celullar Automata
Aluno: Antonino Calisto dos Santos Neto
Profº: Dr. Aristófanes Corrêa Silva
1
Sumário 
O que é Autômato Celular ?
Histórico
Dimensão do Autômato Celular
Características dos Autômatos Celulares 
Comportamentos dos Autômatos Celulares
Autômatos Celulares Unidimensionais
Autômatos Celulares Bidimensionais
Autômatos Celulares e Computação
Aplicações
2
O que é Autômato Celular ?
Segundo (AGUIAR; COSTA, 2000)
Autômatos celulares (ACs) são modelos matemáticos simples de sistemas naturais. 
Os valores evoluem, em passos de tempo discretos, de acordo com regras determinísticas que especificam os valores de cada célula em termos dos valores das células vizinhas.
São ferramentas simples e poderosas para a representação de sistemas evolutivos que a partir de uma configuração inicial aleatória, cada componente do sistema tem sua evolução baseada na situação atual de seus vizinhos e num conjunto de regras que são iguais para todos os componentes.
3
Histórico
4
Dimensão do Autômato Celular 
O Autômato Celular (AC) pode ser representado por um vetor ou matriz de comprimento infinito ou não e os elementos constituintes são as células, que representam cada posição do vetor ou matriz.
Figura 1: Dimensão: a) uma, b) duas e c) três. Fonte (Leite et al., 2007).
5
Características dos Autômatos Celulares
Um AC possui uma estrutura discreta de células que tem características [ILABS, 2009]:
Homogeneidade
Estados discretos
Interações locais
Dinâmicas deterministas
6
Características dos Autômatos Celulares
 A geometria é a forma da grade de células, formada por dimensão e formato.
7
Características dos Autômatos Celulares
Os ACs têm quatro elementos fundamentais, que caracterizam a sua identidade específica:
Os estados possíveis de cada célula 
8
Características dos Autômatos Celulares
Os ACs têm quatro elementos fundamentais, que caracterizam a sua identidade específica:
A sua vizinhança
9
Comportamentos dos Autômatos Celulares
Classe I (estado homogêneo ): todas células estão no mesmo estado.
 
Classe II (estável simples ou limite periódico): as células não possuirão todas o mesmo valor e criarão imagens que se repetem com a evolução temporal.
10
Comportamentos dos Autômatos Celulares
Classe III (padrão irregular): Não possui padrão reconhecível.
 
 
Classe IV (Estrutura complexa): apresentam uma repetição irregular, no tempo, de padrões, a diferentes escalas e posições no espaço. 
11
Autômatos Celulares Unidimensionais
12
também tem sido usado como um gerador de números aleatórios em Mathematica, [3] e também tem sido proposta como um possível cifra de fluxo para uso na criptografia. [4]
 e na biologia para padrões de concha
12
Autômatos Celulares Unidimensionais
A figura abaixo ilustra as primeiras 15 gerações da elementar regra 30 de um AC iniciando com uma simples célula preta. 	
13
13
Autômatos Celulares Bidimensionais
Um AC bidimensional é constituído por uma matriz de células, onde cada célula (i , j) toma um valor e é atualizado o seu valor no decorrer do tempo t;
Algumas vizinhanças bastante conhecidas são:
Von Neumann - Consiste dos vizinhos imediatamente acima e abaixo e dos vizinhos imediatamente a esquerda e a direita.
14
Autômatos Celulares Bidimensionais
Algumas vizinhanças bastante conhecidas são:
Moore – Estendida ,que consiste, além dos 8 vizinhos adjacentes, dos adjacentes a esses 8 vizinhos e vizinhança aleatória, que consiste de uma condição inicial aleatória.
15
Autômatos Celulares Bidimensionais
Exemplos de ACs bidimensionais:
Jogo da vida
Formiga de Langton
 O jogo da vida é um AC bidimensional. Ele é governado por um conjunto de regras simples que definem o nascimento, a sobrevivência ou a morte das células.
Cada célula desse espaço bidimensional pode apresentar dois estados: vivo ou morto.
O Jogo da vida utiliza a vizinhança de Moore, quer dizer, 8 células vizinhas possíveis para uma célula central.
16
Autômatos Celulares Bidimensionais
As regras para o jogo da vida são:
Sobrevivência: Cada célula viva que tenha duas ou três células adjacentes vivas continuará viva na próxima geração.
Nascimento: Cada célula morta com exatamente três células adjacentes vivas nasce na próxima geração.
Morte: Cada célula viva com quatro ou mais células adjacentes vivas morrerá por sufocamento (excesso de densidade populacional).
Morte: Cada célula com menos de duas células vivas adjacentes morre por isolamento.
17
17
Autômatos Celulares Bidimensionais
Exemplo de jogo da vida: 
18
 - 2 células vizinhas = Morre
 2 a 3 células vizinhas = Vive
 + 3 células vizinhas = Morre
 3 células vizinhas = Nasce
Autômatos Celulares Bidimensionais
Exemplo de jogo da vida: 
19
 - 2 células vizinhas = Morre
 2 a 3 células vizinhas = Vive
 + 3 células vizinhas = Morre
 3 células vizinhas = Nasce
Autômatos Celulares Bidimensionais
Exemplo de jogo da vida: 
20
 - 2 células vizinhas = Morre
 2 a 3 células vizinhas = Vive
 + 3 células vizinhas = Morre
 3 células vizinhas = Nasce
Autômatos Celulares Bidimensionais
Exemplo de jogo da vida: 
21
 - 2 células vizinhas = Morre
 2 a 3 células vizinhas = Vive
 + 3 células vizinhas = Morre
 3 células vizinhas = Nasce
Autômatos Celulares Bidimensionais
Exemplo de jogo da vida: 
22
 - 2 células vizinhas = Morre
 2 a 3 células vizinhas = Vive
 + 3 células vizinhas = Morre
 3 células vizinhas = Nasce
Autômatos Celulares Bidimensionais
Exemplo de jogo da vida: 
23
 - 2 células vizinhas = Morre
 2 a 3 células vizinhas = Vive
 + 3 células vizinhas = Morre
 3 células vizinhas = Nasce
Autômatos Celulares Bidimensionais
Exemplo de jogo da vida: 
24
 - 2 células vizinhas = Morre
 2 a 3 células vizinhas = Vive
 + 3 células vizinhas = Morre
 3 células vizinhas = Nasce
Autômatos Celulares Bidimensionais
Exemplo de jogo da vida (padrão Glider): 
25
 - 2 células vizinhas = Morre
 2 a 3 células vizinhas = Vive
 + 3 células vizinhas = Morre
 3 células vizinhas = Nasce
Autômatos Celulares Bidimensionais
A formiga de Langton é um autômato que evolui seguindo regras simples (inventada por Chris Langton em 1986):
Estando em um quadrado branco, vire 90° para a esquerda, mude a cor do quadrado e avance uma unidade;
Estando em um quadrado preto, vire 90° para a direita, mude a cor do quadrado e avance uma unidade.
A formiga de Langton apresenta três modos distintos de comportamento são:
Simplicidade: Durante as primeiras centenas de movimentos cria padrões muito simples que muitas vezes são simétricos.
Caos: Depois de algumas centenas de movimentos, um padrão irregular de quadrados pretos e brancos aparece. A formiga traça um caminho pseudoaleatório até aproximadamente 10.000 passos.
26
Autômatos Celulares Bidimensionais
 Funcionamento:
27
Estando em um quadrado branco, vire 90° para a esquerda, mude a cor do quadrado e avance uma unidade;
Estando em um quadrado preto, vire 90° para a direita, mude a cor do quadrado e avance uma unidade.
Autômatos Celulares e Computação
Um exemplo voltado a processamento de imagens seria na segmentação de nódulos pulmonares (Maura et al. CBIS 2016):
Os pixels da imagem que têm intensidade semelhante do parênquima pulmonar passam a representar o estado morto (cor preta) e os pixels de intensidade diferentes do parênquima o estado vivo (cor branca), formando assim uma imagem com apenas dois estados;	
28
Aplicações
Propagação de incêndio 
Esse autômato tem
por objetivo simular a propagação do incêndio e prever qual será a situação dentro de um determinado período, para onde ele irá se espalhar, observando principalmente o vento que tem grande influência, dessa forma ajudando as pessoas na orientação sobre onde iniciar o combate ao incêndio.
Possíveis estados
Célula verde vegetação (floresta)
Célula vermelha em chamas (fogo)
Células pretas queimada (carbonizada)
29
Aplicações
Propagação de incêndio 
Transições	
A transição entre os estados da célula será da seguinte forma:
Floresta -> fogo -> queimada 
Passando de floresta para fogo, passando de fogo para queimada, nesta ordem sem retornar ao seu estado inicial.
Regras 
A floresta considerada possui uma vegetação verde, onde o incêndio se propaga de forma mais lenta e demora um certo tempo até que a vegetação se torne cinzas, pois as condições de clima favorecem a vegetação.
30
Aplicações
31
Imagem Original
Aplicações
32
Imagem Original
Imagem Equalizada
Gaussiano Adaptativo
Célula estabilizada
Vizinhança da célula que será modificada
Célula que será modificada
Aplicações
Propagação de tráfego urbano
Incêndios florestais
Criptografia
Sistemas Sociais
Criatividade Musical
Formação de cristais
Propagação de epidemias
Reações químicas
Autômatos celulares são usados na prática para simular e prever eventos e comportamentos de sistemas que evoluem com o tempo, como modelagem de fenômenos físicos, biológicos e sociológicos, aplicativos que processam imagens digitais:
33
Celullar Automata
Aluno: Antonino Calisto dos Santos Neto
Profº: Dr. Aristófanes Corrêa Silva
34