In
image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
, pixel connectivity is the way in which
pixels in 2-dimensional (or
hypervoxel
In 3D computer graphics, a voxel represents a value on a regular grid in three-dimensional space. As with pixels in a 2D bitmap, voxels themselves do not typically have their position (i.e. coordinates) explicitly encoded with their values. Ins ...
s in n-dimensional) images relate to their
neighbors.
Formulation
In order to specify a set of connectivities, the dimension
and the width of the neighborhood
, must be specified. The dimension of a neighborhood is valid for any dimension
. A common width is 3, which means along each dimension, the central cell will be adjacent to 1 cell on either side for all dimensions.
Let
represent a N-dimensional
hypercubic
In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perp ...
neighborhood with size on each dimension of
Let
represent a discrete vector in the first
orthant from the center structuring element to a point on the boundary of
. This implies that each element
and that at least one component
Let
represent a N-dimensional
hypersphere with radius of
.
Define the amount of elements on the hypersphere
within the neighborhood
as
. For a given
,
will be equal to the amount of permutations of
multiplied by the number of orthants.
Let
represent the amount of elements in vector
which take the value
.
The total number of permutation of
can be represented by a
multinomial as
If any
, then the vector
is shared in common between orthants. Because of this, the multiplying factor on the permutation must be adjusted from
to be
Multiplying the number of amount of permutations by the adjusted amount of orthants yields,
:
Let
represent the number of elements inside of the hypersphere
within the neighborhood
.
will be equal to the number of elements on the hypersphere plus all of the elements on the inner shells. The shells must be ordered by increasing order of
. Assume the ordered vectors
are assigned a coefficient
representing its place in order. Then an ordered vector
if all
are unique. Therefore
can be defined iteratively as
:
,
or
:
If some
, then both vectors should be considered as the same
such that
Note that each neighborhood will need to have the values from the next smallest neighborhood added. Ex.
includes the center hypervoxel, which is not included in the connectivity. Subtracting 1 yields the neighborhood connectivity,
:
Table of Selected Connectivities
Example
Consider solving for
In this scenario,
since the vector is 3-dimensional.
since there is one
. Likewise,
.
since
.
. The neighborhood is
and the hypersphere is
:
The basic
in the neighborhood
,
. The
Manhattan Distance between our vector and the basic vector is
, so
. Therefore,
:
:
:
:
Which matches the supplied table
Higher values of k & N
The assumption that all
are unique does not hold for higher values of k & N. Consider
, and the vectors
. Although
is located in
, the value for
, whereas
is in the smaller space
but has an equivalent value
.
but has a higher value of
than the minimum vector in
.
For the this assumption to hold,
At higher values of
&
, Values of
will become ambiguous. This means that specification of a given
could refer to multiple
.
Types of connectivity
2-dimensional
4-connected
4-connected pixels are neighbors to every pixel that touches one of their edges. These pixels are
connected horizontally and vertically. In terms of pixel coordinates, every pixel that has the coordinates
:
or
is connected to the pixel at
.
6-connected
6-connected pixels are neighbors to every pixel that touches one of their corners (which includes pixels that touch one of their edges) in a
hexagonal grid or
stretcher bond rectangular grid.
There are several ways to map hexagonal tiles to integer pixel coordinates. With one method, in addition to the 4-connected pixels, the two pixels at coordinates
and
are connected to the pixel at
.
8-connected
8-connected pixels are neighbors to every pixel that touches one of their edges or corners. These pixels are connected horizontally, vertically, and diagonally. In addition to 4-connected pixels, each pixel with coordinates
is connected to the pixel at
.
3-dimensional
6-connected
6-connected pixels are neighbors to every pixel that touches one of their faces. These pixels are connected along one of the
primary axes. Each pixel with coordinates
,
, or
is connected to the pixel at
.
18-connected
18-connected pixels are neighbors to every pixel that touches one of their faces or edges. These pixels are connected along either one or two of the primary axes. In addition to 6-connected pixels, each pixel with coordinates
,
,
,
,
, or
is connected to the pixel at
.
26-connected
26-connected pixels are neighbors to every pixel that touches one of their faces, edges, or corners. These pixels are connected along either one, two, or all three of the primary axes. In addition to 18-connected pixels, each pixel with coordinates
,
,
, or
is connected to the pixel at
.
See also
*
Grid cell topology
*
Moore neighborhood
References
*
*
*{{Citation
, url = http://homepages.inf.ed.ac.uk/rbf/HIPR2/connect.htm
, title = Subband Weighting With Pixel Connectivity for 3-D Wavelet Coding
, year = 2009
, author =
, journal = IEEE Transactions on Image Processing
, pages = 52–62
, volume = 18
, issue = 1
, doi = 10.1109/TIP.2008.2007067
, isbn =
, accessdate = 2009-02-16
, pmid = 19095518
, last1 = Cheng
, first1 = CC
, last2 = Peng
, first2 = GJ
, last3 = Hwang
, first3 = WL
Digital topology
Graph connectivity