Pixel connectivity

Template:Graph connectivity sidebar 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

The 9 possible connectivities in a 5x5x5 neighborhood

In order to specify a set of connectivities, the dimension Template:Mvar and the width of the neighborhood Template:Mvar, must be specified. The dimension of a neighborhood is valid for any dimension $n\ge 1$. 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{Z}$

Let $\overrightarrow{q}$ represent a discrete vector in the first orthant from the center structuring element to a point on the boundary of $M_N^n$. This implies that each element $q_i\in \{0,1,...,k\},\mathrm{\forall }i\in \{1,2,...,N\}$ and that at least one component $q_i=k$

Let $S_N^d$ represent a N-dimensional hypersphere with radius of $d=\Vert \overrightarrow{q}\Vert$.

Define the amount of elements on the hypersphere $S_N^d$ within the neighborhood $M_N^n$ as Template:Mvar. For a given $\overrightarrow{q}$, Template:Mvar will be equal to the amount of permutations of $\overrightarrow{q}$ multiplied by the number of orthants.

Let $n_j$ represent the amount of elements in vector $\overrightarrow{q}$ which take the value Template:Mvar. $n_j=\sum _{i=1}^N(q_i=j)$

The total number of permutation of $\overrightarrow{q}$ can be represented by a multinomial as $\frac{N!}{\prod _{j=0}^k{n}_j!}$

If any $q_i=0$, then the vector $\overrightarrow{q}$ is shared in common between orthants. Because of this, the multiplying factor on the permutation must be adjusted from $2^N$ to be $2^{N-n_0}$

Multiplying the number of amount of permutations by the adjusted amount of orthants yields,

$E=\frac{N!}{\prod _{j=0}^k{n}_j!}{2}^{N-n_0}$

Let Template:Mvar represent the number of elements inside of the hypersphere $S_N^d$ within the neighborhood $M_N^n$. Template:Mvar 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 $\Vert \overrightarrow{q}\Vert =r$. Assume the ordered vectors $\overrightarrow{q}$ are assigned a coefficient Template:Mvar representing its place in order. Then an ordered vector ${\overrightarrow{q}}_p,p\in \{1,2,...,\sum _{x=1}^k(x+1)\}$ if all Template:Mvar are unique. Therefore Template:Mvar can be defined iteratively as

$V_{{\overrightarrow{q}}_p}=V_{{\overrightarrow{q}}_{p-1}}+E_{{\overrightarrow{q}}_p},V_{{\overrightarrow{q}}_0}=0$,

or

$V_{{\overrightarrow{q}}_p}=\sum _{x=1}^p{E}_{{\overrightarrow{q}}_x}$

If some $\Vert {\overrightarrow{q}}_x\Vert =\Vert {\overrightarrow{q}}_y\Vert$, then both vectors should be considered as the same Template:Mvar such that $$V_{{\overrightarrow{q}}_p}=V_{{\overrightarrow{q}}_{p-1}}+E_{{\overrightarrow{q}}_{p,1}}+E_{{\overrightarrow{q}}_{p,2}},V_{{\overrightarrow{q}}_0}=0$$ Note that each neighborhood will need to have the values from the next smallest neighborhood added. Ex. $V_{\overrightarrow{q}=(0,2)}=V_{\overrightarrow{q}=(1,1)}+E_{\overrightarrow{q}=(0,2)}$

Template:Mvar includes the center hypervoxel, which is not included in the connectivity. Subtracting 1 yields the neighborhood connectivity, Template:Mvar

$G=V-1$

Table of Selected Connectivities

Neighborhood Size: $M_N^n$	Connectivity Type	Typical Vector: $\overrightarrow{q}$	Sphere Radius:	Elements on Sphere:	Elements in Sphere:	Neighborhood Connectivity:
1	edge	(0)	Template:Square root	1Template:Times1 = 1	1	0
3	point	(1)	Template:Square root	1Template:Times2 = 2	3	2
5	point-point	(2)	Template:Square root	1Template:Times2 = 2	5	4
...
1Template:Times1	face	(0,0)	Template:Square root	1Template:Times1 = 1	1	0
3Template:Times3	edge	(0,1)	Template:Square root	2Template:Times2 = 4	5	4
	point	(1,1)	Template:Square root	1Template:Times4 = 4	9	8
5Template:Times5	edge-edge	(0,2)	Template:Square root	2Template:Times2 = 4	13	12
	point-edge	(1,2)	Template:Square root	2Template:Times4 = 8	21	20
	point-point	(2,2)	Template:Square root	1Template:Times4 = 4	25	24
...
1Template:Times1Template:Times1	volume	(0,0,0)	Template:Square root	1Template:Times1 = 1	1	0
3Template:Times3Template:Times3	face	(0,0,1)	Template:Square root	3Template:Times2 = 6	7	6
	edge	(0,1,1)	Template:Square root	3Template:Times4 = 12	19	18
	point	(1,1,1)	Template:Square root	1Template:Times8 = 8	27	26
5Template:Times5Template:Times5	face-face	(0,0,2)	Template:Square root	3Template:Times2 = 6	33	32
	edge-face	(0,1,2)	Template:Square root	6Template:Times4 = 24	57	56
	point-face	(1,1,2)	Template:Square root	3Template:Times8 = 24	81	80
	edge-edge	(0,2,2)	Template:Square root	3Template:Times4 = 12	93	92
	point-edge	(1,2,2)	Template:Square root	3Template:Times8 = 24	117	116
	point-point	(2,2,2)	Template:Square root	1Template:Times8 = 8	125	124
...
1Template:Times1Template:Times1Template:Times1	hypervolume	(0,0,0,0)	Template:Square root	1Template:Times1 = 1	1	0
3Template:Times3Template:Times3Template:Times3	volume	(0,0,0,1)	Template:Square root	4Template:Times2 = 8	9	8
	face	(0,0,1,1)	Template:Square root	6Template:Times4 = 24	33	32
	edge	(0,1,1,1)	Template:Square root	4Template:Times8 = 32	65	64
	point	(1,1,1,1)	Template:Square root	1Template:Times16 = 16	81	80
...

Example

Consider solving for $G|\overrightarrow{q}=(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{0^2+1^2+1^2}=\sqrt{2}$. The neighborhood is $M_3^3$ and the hypersphere is $S_3^{\sqrt{2}}$

$E=\frac{3!}{1!*2!*0!}{2}^{3-1}=\frac{6}{2}4=12$

The basic $\overrightarrow{q}$ in the neighborhood $N_3^3$, ${\overrightarrow{q}}_1=(0,0,0)$. The Manhattan Distance between our vector and the basic vector is ${\Vert \overrightarrow{q}-{\overrightarrow{q}}_0\Vert }_1=2$, so $\overrightarrow{q}={\overrightarrow{q}}_3$. Therefore,

$G_{{\overrightarrow{q}}_3}=V_{{\overrightarrow{q}}_3}-1=E_{{\overrightarrow{q}}_1}+E_{{\overrightarrow{q}}_2}+E_{{\overrightarrow{q}}_3}-1=E_{\overrightarrow{q}=(0,0,0)}+E_{\overrightarrow{q}=(0,0,1)}+E_{\overrightarrow{q}=(0,1,1)}$

$E_{\overrightarrow{q}=(0,0,0)}=\frac{3!}{3!*0!*0!}{2}^{3-3}=\frac{6}{6}1=1$

$E_{\overrightarrow{q}=(0,0,1)}=\frac{3!}{2!*1!}{2}^{3-2}=\frac{6}{2}2=6$

$G=1+6+12-1=18$

Which matches the supplied table

Higher values of k & N

The assumption that all $\Vert {\overrightarrow{q}}_p\Vert =r$ are unique does not hold for higher values of k & N. Consider $N=2,k=5$, and the vectors ${\overrightarrow{q}}_A=(0,5),{\overrightarrow{q}}_B=(3,4)$. Although ${\overrightarrow{q}}_A$ is located in $M_2^5$, the value for $r=25$, whereas ${\overrightarrow{q}}_B$ is in the smaller space $M_2^4$ but has an equivalent value $r=25$. ${\overrightarrow{q}}_C=(4,4)\in M_2^4$ but has a higher value of $r=32$ than the minimum vector in $M_2^5$.

For this assumption to hold, $\{\begin{array}{c}N=2,k\le 4\\ N=3,k\le 2\\ N=4,k\le 1\end{array}$

At higher values of Template:Mvar & Template:Mvar, Values of Template:Mvar will become ambiguous. This means that specification of a given Template:Mvar could refer to multiple ${\overrightarrow{q}}_p\in M_n^N$.

Types of connectivity

2-dimensional

Example of neighborhood of pixels - association of eight and four pixels

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

$(x\pm 1,y)$ or $(x,y\pm 1)$

is connected to the pixel at $(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 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 $(x+1,y+1)$ and $(x-1,y-1)$ are connected to the pixel at $(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 $(x\pm 1,y\pm 1)$ is connected to the pixel at $(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 $(x\pm 1,y,z)$, $(x,y\pm 1,z)$, or $(x,y,z\pm 1)$ is connected to the pixel at $(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 $(x\pm 1,y\pm 1,z)$, $(x\pm 1,y\mp 1,z)$, $(x\pm 1,y,z\pm 1)$, $(x\pm 1,y,z\mp 1)$, $(x,y\pm 1,z\pm 1)$, or $(x,y\pm 1,z\mp 1)$ is connected to the pixel at $(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 $(x\pm 1,y\pm 1,z\pm 1)$, $(x\pm 1,y\pm 1,z\mp 1)$, $(x\pm 1,y\mp 1,z\pm 1)$, or $(x\mp 1,y\pm 1,z\pm 1)$ is connected to the pixel at $(x,y,z)$.

See also

• Grid cell topology
• Moore neighborhood

References

• Template:Citation
• Template:Citation
• Template:Citation