Introduction
In binary valued digital imaging, a pixel can either have a value of 1 -when it's part of the pattern- , or 0 -when it's part of the background- i.e. there is no grayscale level. (We will assume that pixels with value 1 are black while zero valued pixels are white).
In order to identify objects in a digital pattern, we need to locate groups of black pixels that are "connected" to each other. In other words, the objects in a given digital pattern are the connected components of that pattern.
In general, a connected component is a set of black pixels, P, such that for every pair of pixels pi and pj in P, there exists a sequence of pixels pi, ..., pj such that:
a) all pixels in the sequence are in the set P i.e. are black, and
b) every 2 pixels that are adjacent in the sequence are "neighbors"
As a result, an important question arises: When can we say that 2 pixels are "neighbors"?
Since we are using square pixels, the answer to the previous question is not trivial. The reason for that is: in a square tessellation, pixels either share an edge, a vertex, or neither. There are 8 pixels sharing an edge or a vertex with any given pixel; these pixels make up the Moore neighborhood of that pixel. Should we consider pixels having only a common vertex as "neighbors" ? Or should 2 pixels have a common edge in order for them to be considered "neighbors"?
This gives rise to 2 types of connectedness, namely: 4-connectivity and 8-connectivity.
4-Connectivity
When can we say that a given set of black pixels is 4-connected ?
First, we have to define the concept of a 4-neighbor (also known as a direct-neighbor):
Definition of a 4-neighbor:
A pixel, Q, is a 4-neighbor of a given pixel, P, if Q and P share an edge.
The 4-neighbors of pixel P (namely pixels P2,P4,P6 and P8) are shown in Figure 2 below.
Definition of a 4-connected component :
A set of black pixels, P, is a 4-connected component if for every pair of pixels pi and pj in P, there exists a sequence of pixels pi, ..., pj such that:
a) all pixels in the sequence are in the set P i.e. are black, and
b) every 2 pixels that are adjacent in the sequence are 4-neighbors
Examples of 4-connected patterns :
The following diagrams are examples of patterns that are 4-connected:
8-Connectivity
When can we say that a given set of black pixels is 8-connected ?
First, we have to define the concept of an 8-neighbor (also known as an indirect-neighbor):
Definition of an 8-neighbor:
A pixel, Q, is an 8-neighbor (or simply a neighbor) of a given pixel, P, if Q and P either share an edge or a vertex.
The 8-neighbors of a given pixel P make up the Moore neighborhood of that pixel.
Definition of an 8-connected component:
A set of black pixels, P, is an 8-connected component (or simply a connected component) if for every pair of pixels pi and pj in P, there exists a sequence of pixels pi, ..., pj such that:
a) all pixels in the sequence are in the set P i.e. are black, and
b) every 2 pixels that are adjacent in the sequence are 8-neighbors
NOTE
All 4-connected patterns are 8-connected i.e. 4-connected patterns are a subset of the set of 8-connected patterns.
On the other hand, an 8-connected pattern may not be 4-connected.
Example of 8-connected pattern :
The diagram below is an example of a pattern that is 8-connected but not 4-connected:
Example of a pattern that's not 8-connected:
The diagram below is an example of a pattern that is not 8-connected i.e. is made up of more than one connected component (there are 3 connected components in the diagram below):
No comments:
Post a Comment