8-connectivity
   HOME

TheInfoList



OR:

In image processing, pixel connectivity is the way in which
pixels In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a raster image, or the smallest point in an all points addressable display device. In most digital display devices, pixels are the sm ...
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 of the neighborhood n , must be specified. The dimension of a neighborhood is valid for any dimension n\geq1 . 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 M_N^n represent a N-dimensional hypercubic neighborhood with size on each dimension of n=2k+1, k\in\mathbb Let \vec represent a discrete vector in the first
orthant In geometry, an orthant or hyperoctant is the analogue in ''n''-dimensional Euclidean space of a quadrant in the plane or an octant in three dimensions. In general an orthant in ''n''-dimensions can be considered the intersection of ''n'' mutua ...
from the center structuring element to a point on the boundary of M_N^n. This implies that each element q_i \in \ ,\forall i \in \ and that at least one component q_i = k Let S_N^d represent a N-dimensional
hypersphere In mathematics, an -sphere or a hypersphere is a topological space that is homeomorphic to a ''standard'' -''sphere'', which is the set of points in -dimensional Euclidean space that are situated at a constant distance from a fixed point, call ...
with radius of d=\left \Vert \vec \right \Vert. Define the amount of elements on the hypersphere S_N^d within the neighborhood M_N^n as E. For a given \vec, E will be equal to the amount of permutations of \vec multiplied by the number of orthants. Let n_j represent the amount of elements in vector \vec which take the value j. n_j = \sum_^N (q_i=j) The total number of permutation of \vec can be represented by a multinomial as \frac If any q_i = 0 , then the vector \vec is shared in common between orthants. Because of this, the multiplying factor on the permutation must be adjusted from 2^ to be 2^ Multiplying the number of amount of permutations by the adjusted amount of orthants yields, :E=\frac2^ Let V represent the number of elements inside of the hypersphere S_N^d within the neighborhood M_N^n. V 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 \left \Vert \vec \right \Vert = r. Assume the ordered vectors \vec are assigned a coefficient p representing its place in order. Then an ordered vector \vec, p \in \ if all r are unique. Therefore V can be defined iteratively as :V_ = V_ + E_, V_=0, or :V_ = \sum_^p E_ If some \left \Vert \vec \right \Vert = \left \Vert \vec \right \Vert, then both vectors should be considered as the same p such that
V_ = V_ + E_ + E_, V_=0
Note that each neighborhood will need to have the values from the next smallest neighborhood added. Ex. V_ = V_ + E_ V includes the center hypervoxel, which is not included in the connectivity. Subtracting 1 yields the neighborhood connectivity, G :G=V-1


Table of Selected Connectivities


Example

Consider solving for G, \vec=(0,1,1) In this scenario, N=3 since the vector is 3-dimensional. n_0=1 since there is one q_i=0. Likewise, n_1=2. k=1, n=3 since \max q_i = 1. d=\sqrt=\sqrt. The neighborhood is M^3_3 and the hypersphere is S_3^\sqrt :E=\frac2^=\frac4=12 The basic \vec in the neighborhood N^3_3, \vec = (0,0,0). The
Manhattan Distance A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian co ...
between our vector and the basic vector is \left \Vert \vec - \vec \right \Vert_1 = 2, so \vec = \vec. Therefore, :G_ = V_ - 1 = E_ + E_ + E_ - 1 = E_ + E_ + E_ :E_ = \frac2^ = \frac1 = 1 :E_ = \frac 2^=\frac 2 = 6 :G = 1 + 6 + 12 - 1 = 18 Which matches the supplied table


Higher values of k & N

The assumption that all \left \Vert \vec \right \Vert = r are unique does not hold for higher values of k & N. Consider N=2, k=5, and the vectors \vec=(0,5), \vec=(3,4). Although \vec is located in M_2^5, the value for r=25, whereas \vec is in the smaller space M_2^4 but has an equivalent value r=25. \vec=(4,4) \in M_^ but has a higher value of r=32 than the minimum vector in M_2^5. For the this assumption to hold, \begin N=2, k \leq 4 \\ N=3, k \leq 2 \\ N=4, k \leq 1 \end At higher values of k & N, Values of d will become ambiguous. This means that specification of a given d could refer to multiple \vec \in M_n^N.


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 Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...
horizontally and vertically. In terms of pixel coordinates, every pixel that has the coordinates : \textstyle(x\pm1, y) or \textstyle(x, y\pm1) is connected to the pixel at \textstyle(x, y).


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 In geometry, a hexagon (from Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°. Regular hexagon A '' regular hexagon'' has ...
grid or
stretcher bond Brickwork is masonry produced by a bricklayer, using bricks and mortar. Typically, rows of bricks called ''courses'' are laid on top of one another to build up a structure such as a brick wall. Bricks may be differentiated from blocks by siz ...
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 \textstyle(x+1,y+1) and \textstyle(x-1,y-1) are connected to the pixel at \textstyle(x,y).


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 \textstyle(x\pm1,y\pm1) is connected to the pixel at \textstyle(x,y).


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 \textstyle(x\pm1, y, z), \textstyle(x, y\pm1, z), or \textstyle(x, y, z\pm1) is connected to the pixel at \textstyle(x, y, z).


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 \textstyle(x\pm1, y\pm1, z), \textstyle(x\pm1, y\mp1, z), \textstyle(x\pm1, y, z\pm1), \textstyle(x\pm1, y, z\mp1), \textstyle(x, y\pm1, z\pm1), or \textstyle(x, y\pm1, z\mp1) is connected to the pixel at \textstyle(x, y, z).


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 \textstyle(x\pm1, y\pm1, z\pm1), \textstyle(x\pm1, y\pm1, z\mp1), \textstyle(x\pm1, y\mp1, z\pm1), or \textstyle(x\mp1, y\pm1, z\pm1) is connected to the pixel at \textstyle(x, y, z).


See also

*
Grid cell topology The grid cell topology is studied in digital topology as part of the theoretical basis for (low-level) algorithms in computer image analysis or computer graphics. The elements of the ''n''-dimensional grid cell topology (''n'' ≥ 1) are all ''n ...
*
Moore neighborhood In cellular automata, the Moore neighborhood is defined on a two-dimensional square lattice 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 aut ...


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