In cellular automata, the Moore neighborhood comprises the eight cells surrounding a central cell on a two-dimensional square lattice

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. It is one of the five types of two-dimensional lattices as classified by their symmetry groups; its symmetry group is known symbolically as p4m.Two...

. The neighborhood is named after Edward F. Moore

Edward F. Moore

Edward Forrest Moore was an American professor of mathematics and computer science, the inventor of the Moore finite state machine, and an early pioneer of artificial life....

, a pioneer of cellular automata theory. It is one of the two most commonly used neighborhood types, the other one being the 4-cell von Neumann neighborhood

Von Neumann neighborhood

In cellular automata, the von Neumann neighborhood comprises the four cells orthogonally surrounding a central cell on a two-dimensional square lattice. The neighborhood is named after John von Neumann, who used it for his pioneering cellular automata including the Universal Constructor...

. The well known Conway's Game of Life

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....

, for example, uses the Moore neighborhood. It is similar to the notion of 8-connected pixel

Pixel

In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....

s in computer graphics

Computer graphics

Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

.

The concept can be extended to higher dimensions, for example forming a 26-cell cubic neighborhood for a cellular automaton in three dimensions.

The Moore neighbourhood of a point is the points at a Chebyshev distance

Chebyshev distance

In mathematics, Chebyshev 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...

 of 1.

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 which was later then called the Moore Neighborhood algorithm.

The following is a formal description of the Moore-Neighbor tracing algorithm:
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
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
b = p
p = c
(backtrack: move the current pixel c to the pixel from which p was entered)
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)
b = c
c = next clockwise pixel (from b) in M(p).
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.

Applications

Because of its flexibility, it is widely used on most image editing software such as the Photoshop

Adobe Photoshop

Adobe Photoshop is a graphics editing program developed and published by Adobe Systems Incorporated.Adobe's 2003 "Creative Suite" rebranding led to Adobe Photoshop 8's renaming to Adobe Photoshop CS. Thus, Adobe Photoshop CS5 is the 12th major release of Adobe Photoshop...

 line of Adobe Systems

Adobe Systems

Adobe Systems Incorporated is an American computer software company founded in 1982 and headquartered in San Jose, California, United States...

 and the MX Fireworks of Macromedia

Macromedia

Macromedia was an American graphics and web development software company headquartered in San Francisco, California that produced such products as Flash and Dreamweaver. Its rival, Adobe Systems, acquired Macromedia on December 3, 2005 and controls the line of Macromedia...

. It is used on their image editing tool with concerns regarding cellular automata on image engine. Some of these tools are the edge finder and magic wand which greatly deals with the proper management and allocation of the boundary and edge of a digital image