Vizinhança de Moore

Em Autômatos celulares, a Vizinhança de Moore consiste em oito células ao redor de uma célula central em uma grade quadrada. A vizinhança foi nomeada em homenagem à Edward F. Moore, um pioneiro da teoria dos autômatos celulares. Este conceito é um dos mais usados, assim como a Vizinhança de von Neumann, onde se usam 4 células ao redor do centro. Jogo da vida, por exemplo, utiliza vizinhança de Moore. Possui uma noção similar à uma conexão de 8 pixels em Computação gráfica. Este conceito pode ser estendido para dimensões maiores. A vizinhança de Moore de um ponto é o conjunto dos pontos que estão à uma distancia de 1, utilizando a métrica da Distância de Chebyshev. O número de células em uma vizinhança de Moore de raio r é $(2r+1)^{2}-1$.

Algoritmo

A ideia por trás da formulação da vizinhança de Moore é achar o contorno de um grafo dado. Essa ideia foi um grande desafio para muitos analistas do século 18 e, como resultado, um algoritmo foi derivado do Grafo de Moore, que mais tarde foi chamado de algoritmo da vizinhança de Moore. Segue uma descrição do algoritmo de procura de vizinhos de Moore:

Entrada: Uma grade quadrada T, contendo uma grade conectada P de pixels negros.
Saída: Uma sequência B (b1, b2, ..., bk) de pixels de borda, i.e. o contorno.
Defina M(a) para ser a vizinhança de Moore do pixel a.
Defina p como o pixel central atual.
Defina c como o pixel atual sob observação em M(p), i.e. pixel que está sendo testado.
Defina b como o backtrack de c (vizinho do pixel p que foi previamente testado)
 
início
  defina B para vazio.
  escaneie as células de T de baixo para cima e da esquerda para direita até um pixel negro s, de P, ser achado.
  insira s em B.
  defina o atual pixel central p para s, i.e. p = s
  defina b = o pixel no qual s foi inserido durante o scan da imagem.
  defina c como o próximo pixel em sentido horário (a partir de b) em M(p).
  enquanto c for diferente de s faça
    se c for um pixel negro
      insira c em B
      defina b = p
      defina p = c
      (backtrack: mova o atual pixel c para o pixel no qual p foi inserido)
      defina c = próximo pixel em sentido horário (a partir de b) em M(p).
    senão
      (avance o pixel atual c para o próximo pixel no sentido horário em M(p) e atualize o backtrack)
      Faça b = c
      Faça c = próximo pixel em sentido horário (a partir de b) em M(p).
    fim-se
  fim-enquanto
fim

Condição de Terminação

A condição de terminação original era parar após visitar o pixel inicial pela segunda vez. Isso limitava o conjunto de contornos que o algoritmo iria procurar completamente. Uma condição de parada mais eficiente, proposta por Jacob Eliosoff é parar após visitar o pixel inicial pela segunda vez na mesma direção que você originalmente visitou.

Aplicações

Por causa da sua flexibilidade, esse conceito é amplamente usado na maioria dos softwares de edição de imagem, em ferramentas responsáveis pelas questões de autômatos celulares.

Veja também

• Vizinhança (teoria dos grafos)
• Grade quadrada (página em inglês)
• Distância de Chebyshev (página em inglês)
• Grafo do rei (página em inglês)

Referências

• Weisstein, Eric W. «Moore Neighborhood» (em inglês). MathWorld 
• Tyler, Tim, The Moore neighborhood at cell-auto.com

Notas

• Este artigo foi inicialmente traduzido, total ou parcialmente, do artigo da Wikipédia em inglês cujo título é «Moore neighborhood».