![Moore neighborhood with cardinal directions](https://upload.wikimedia.org/wikipedia/commons/4/4d/Moore_neighborhood_with_cardinal_directions.svg)
In
cellular automata
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
, the Moore neighborhood is defined on a two-dimensional
square lattice
In mathematics, the square lattice is a type of lattice in a two-dimensional Euclidean space. It is the two-dimensional version of the integer lattice, denoted as . It is one of the five types of two-dimensional lattices as classified by their ...
and is composed of a central cell and the eight cells that surround it.
Name
The neighborhood is named after
Edward F. Moore, a pioneer of cellular automata theory.
Importance
It is one of the two most commonly used neighborhood types, the other one being the
von Neumann neighborhood
In cellular automata, the von Neumann neighborhood (or 4-neighborhood) is classically defined on a two-dimensional square lattice and is composed of a central cell and its four adjacent cells. The neighborhood is named after John von Neumann, ...
, which excludes the corner cells. The well known
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further ...
, for example, uses the Moore neighborhood. It is similar to the notion of
8-connected
In image processing, pixel connectivity is the way in which pixels in 2-dimensional (or hypervoxels in n-dimensional) images relate to their neighbors.
Formulation
In order to specify a set of connectivities, the dimension N
and the width ...
pixels in
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
.
The Moore neighbourhood of a cell is the cell itself and the cells at a
Chebyshev distance
In mathematics, Chebyshev distance (or Tchebychev distance), maximum metric, or Lā metric is a metric defined on a vector space where the distance between two vectors is the greatest of their differences along any coordinate dimension. It is na ...
of 1.
The concept can be extended to higher dimensions, for example forming a 26-cell cubic neighborhood for a cellular automaton in three dimensions, as used by
3D Life
3D Life is a cellular automaton. It is a three-dimensional extension of Game of Life, investigated by Carter Bays. A number of different semitotalistic rules for the 3D rectangular Moore neighborhood were investigated.
It was popularized by A. ...
. In dimension ''d,'' where
, the size of the neighborhood is 3
''d'' ā 1.
In two dimensions, the number of cells in an ''extended'' Moore neighbourhood, given its range ''r'' is (2''r'' + 1)
2.
Algorithm
The idea behind the formulation of Moore neighborhood is to find the contour of a given graph. This idea was a great challenge for most analysts of the 18th century, and as a result an algorithm was derived from the
Moore graph
In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is and its diameter is , its girth must e ...
which was later called the Moore Neighborhood algorithm.
The
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
for the Moore-Neighbor tracing algorithm is
Input: A square tessellation, T, containing a connected component P of black cells.
Output: A sequence B (b1, b2, ..., bk) of boundary pixels i.e. the contour.
Define M(a) to be the Moore neighborhood of pixel a.
Let p denote the current boundary pixel.
Let c denote the current pixel under consideration i.e. c is in M(p).
Let b denote the backtrack of c (i.e. neighbor pixel of p that was previously tested)
Begin
Set B to be empty.
From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
Insert s in B.
Set the current boundary point p to s i.e. p=s
Let b = the pixel from which s was entered during the image scan.
Set c to be the next clockwise pixel (from b) in M(p).
While c not equal to s do
If c is black
insert c in B
Let b = p
Let p = c
''(backtrack: move the current pixel c to the pixel from which p was entered)''
Let c = next clockwise pixel (from b) in M(p).
else
''(advance the current pixel c to the next clockwise pixel in M(p) and update backtrack)''
Let b = c
Let c = next clockwise pixel (from b) in M(p).
end If
end While
End
Termination condition
The original termination condition was to stop after visiting the start pixel for the second time. This limits the set of contours the algorithm will walk completely. An improved stopping condition proposed by Jacob Eliosoff is to stop after entering the start pixel for the second time in the same direction you originally entered it.
See also
*
Neighbourhood (graph theory)
In graph theory, an adjacent vertex of a vertex in a graph is a vertex that is connected to by an edge. The neighbourhood of a vertex in a graph is the subgraph of induced by all vertices adjacent to , i.e., the graph composed of the ver ...
*
King's graph
In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m king's graph ...
*
Chain code A chain code is a lossless compression based image segmentation method for binary images based upon tracing image contours. The basic principle of chain coding, like other contour codings, is to separately encode each connected component, or "blob" ...
*
Von Neumann neighborhood
In cellular automata, the von Neumann neighborhood (or 4-neighborhood) is classically defined on a two-dimensional square lattice and is composed of a central cell and its four adjacent cells. The neighborhood is named after John von Neumann, ...
References
*
* Tyler, Tim,
The Moore neighborhood' a
cell-auto.com
{{DEFAULTSORT:Moore Neighborhood
Cellular automata