Modelagem de Autômatos Celulares
no Reconhecimento de Bordas
Leonardo Carvalho
LCG-COPPE-UFRJ
Introdução
• Criado por Von Neumann, um autômato celular (AC)
é um conceito matemático criado para designar um
sistema de elementos conjugados que mudam de
comportamento por meio de interações locais guiadas
por regras.
• É um modelo intrínsicamente paralelo
• Já foram utilizados com sucesso em muitos aspectos
tais como:
– Dinâmica dos fluidos
– Biologia
– Controle de tráfego
– Criptografia
– Modelagem de meio-ambiente
– Finanças e etc
O que são AC?
• Sejam:
– L um reticulado regular cujos elementos serão
chamados de células
– S um conjunto finito de estados
– N um conjunto finito (de tamanho n=|N|) de
vizinhanças, de forma que:
– f: Sn → S uma função de transição
• Chamamos de autômato celular a quadrupla:
(L,S,N,f)
O que são AC?
• Uma configuração Ci: Sn → S associa cada célula
com um estado
• A função de transição f muda a configuração Ct em
uma nova configuração Ct+1 de acordo com a regra:
• onde
Reconhecimento de Retângulos
●
●
●
Idéia Básica:
Transformar a imagem em um AC
Combinação de AC com o conceito operador de
borda
Existem diversas escolhas a serem feitas:
●
Geometria do Reticulado
●
Tamanho da vizinhança
●
Condições de contorno
●
Condições iniciais
●
Conjunto de Estados
●
Regra de Transição
Modelagem do Autômato
Reticulado retangular bidimensional do tamanho da
imagem. Assim, pode ser estabelecida uma relação
um-para-um com as células do autômato.
●Vizinhança de Moore
●No contorno da imagem será usada reflexão
●Estado inicial da célula é a cor do pixel (0 ou 1)
●Regra de transição (aspecto mais importante...)
●
Regra de Transição
Aspecto mais importante na modelagem do AC
●Permite ao AC realizar a tarefa de reconhecimento
●Método proposto divide a tarefa em duas fases:
● Fase de caracterização
● É determinado um vetor para cada célula de
acordo com seu estado inicial
● Fase de evolução
● Reconhecimento através da evolução das células
pela regra de transição
●
Fase de Caracterização
Usamos o conceito de operador de borda para
identificar o vetor característico de cada célula
●O processo pode ser resumido assim:
● Para cada célula calcular os valores
correspondentes às oito direções possíveis
●
8 1 2
-1 -1 -1
0 -1 -1
1
0 -1
7
6
0
1
1 0 -1
1 1 0
1
1
0 -1
0 -1
0 3
5 4
direções
●
0 0
1 1
...
elem. estrut. pos. 2
pos. 3
(pos. 1)
Encontrar o máximo dos valores calculados e usar
a coordenada da direção como vetor característico
Fase de Evolução
●
Vamos examinar um exemplo simples:
1
1
1
1
1
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
1
1
1
1
1
Imagem binarizada com
um retângulo simples
Fase de Evolução
1a.=-2
●
Calculando o vetor característico...
1
1
1
1
1
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
1
1
1
1
1
1 1 1
1 0 0
1 0 0
-2
-1 -1 -1
0 0 0
1 1 1
1a. Coordenada
Fase de Evolução
●
1a.=-2
2a.=0
Calculando o vetor característico...
1
1
1
1
1
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
1
1
1
1
1
1 1 1
1 0 0
1 0 0
0
0 -1 -1
1 0 -1
1 1 0
2a. Coordenada
Fase de Evolução
●
1a.=-2
2a.=0
3a.=2
Calculando o vetor característico...
1
1
1
1
1
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
1
1
1
1
1
1 1 1
1 0 0
1 0 0
2
1 0 -1
1 0 -1
1 0 -1
3a. Coordenada
Fase de Evolução
●
Continuando os cálculos...
1
1
1
1
1
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
1
1
1
1
1
1 1 1
1 0 0
1 0 0
1a.=-2
2a.=0
3a.=2
4a.=3
5a.=2
6a.=0
7a.=-2
8a.=-3
A coordenada onde se obteve maior valor foi a 4a.,
logo...
Fase de Evolução
●
Cálculo para um pixel...
1
1
1
1
1
1
1
4
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
1
1
1
1
1
Fase de Evolução
●
Repetindo o processo, temos a matriz de vetores:
Podemos notar o seguinte:
4
3
3
2
5 5
1616
1616
1 1
6
7
7
8
•Se uma célula está na borda, então
ela possui exatamente dois
vizinhos na borda
•A diferença entre os vetores da
célula e de seus dois vizinhos é 0, 1
ou 7
Portanto, a regra de transição pode ser
dada da seguinte forma:
●
Para cada célula:
●
●
●
Encontre os vizinhos cuja diferença entre os vetores seja: 0,
1 ou 7. Se o número de vizinhos não for 2, mude o vetor
para 16.
Repita o passo anterior até os vetores não se alterarem mais.
Exiba as células onde os vetores são diferentes de 16.
Fase de Evolução
●
Resultado:
Detecção de bordas em uma imagem mais
complicada
A cor de um pixel pode ter valores diferentes de 0 e 1
●Não podemos decidir precisamente se a célula está na
borda
●Como resolver o problema?
●
Idéia Básica
Além da coordenada correspondente ao valor máximo das oito
direções, devemos guardar o valor em si
●Nesse tipo de imagem, a célula de borda pode possuir mais de
duas células vizinhas que satisfazem a condição
●
Por outro lado...
Se a célula possui menos que dois vizinhos de borda, então ela
precisa estar fora da borda
●Eliminando as células que não estão na borda, nós temos a
borda em si
●
Modificações nas duas fases
É necessário fazer algumas mudanças nas regras das duas
fases:
●
Fase de Caracterização
Devemos guardar também, além da direção maximal, o valor
calculado nesta direção
●
Modificações nas duas fases
Fase de Evolução
●Se a célula possui menos que dois vizinhos que satisfazem as
condições:
●
●
●
|V(x1) - V(x)| < a1
|V(x1)| + |V(x)| > a2
|d(x1) - d(x)| < a3
Nós aplicamos à célula o valor 16 para seu vetor. Onde:
●
●
●
●
●
x é uma célula
x1 seu vizinho
V(x) é o valor da direção maximal da célula x
d(x) a coordenada correspondente à direção maximal
a1, a2 e a3 são parâmetros dados
Conclusões
O artigo demonstra que autômatos celulares são uma
ferramenta potencial para o processamento de imagens.
●Além disso, o método nos dá um novo ponto de vista para
descrever e extrair características de imagens.
●O processo pode ser adaptado para uma grande gama de
aplicações de processamento de imagens.
●
Bibliografia
●
●
Artigo original: “Cellular Automata Modeling in
Edge Recognition”, Chen Yang e Hao Ye
http://www.stephenwolfram.com/publications/a
rticles/ca/83-cellular/index.html