pixel connectivity

File:5x5x5 connectivity.png

In order to specify a set of connectivities, the dimension {{mvar|N}} and the width of the neighborhood {{mvar|n}}, must be specified. The dimension of a neighborhood is valid for any dimension $n\backslash 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\backslash in\backslash mathbb\{Z\}$

Let $\backslash vec\{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\; \backslash in\; \backslash \{0,1,...,k\backslash \}\; ,\backslash forall\; i\; \backslash in\; \backslash \{1,2,...,N\backslash \}$ and that at least one component $q\_i\; =\; k$

Let $S\_N^d$ represent a N-dimensional hypersphere with radius of $d=\backslash left\; \backslash Vert\; \backslash vec\{q\}\; \backslash right\; \backslash Vert$.

Define the amount of elements on the hypersphere $S\_N^d$ within the neighborhood $M\_N^n$ as {{mvar|E}}. For a given $\backslash vec\{q\}$, {{mvar|E}} will be equal to the amount of permutations of $\backslash vec\{q\}$ multiplied by the number of orthants.

Let $n\_j$ represent the amount of elements in vector $\backslash vec\{q\}$ which take the value {{mvar|j}}. $n\_j\; =\; \backslash sum\_\{i=1\}^N\; (q\_i=j)$

The total number of permutation of $\backslash vec\{q\}$ can be represented by a multinomial as $\backslash frac\{N!\}\; \{\backslash prod\_\{j=0\}^kn\_j!\}$

If any $q\_i\; =\; 0$

, then the vector $\backslash vec\{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=\backslash frac\{N!\}\{\backslash prod\_\{j=0\}^kn\_j!\}2^\{N-n\_0\}$

Let {{mvar|V}} represent the number of elements inside of the hypersphere $S\_N^d$ within the neighborhood $M\_N^n$. {{mvar|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 $\backslash left\; \backslash Vert\; \backslash vec\{q\}\; \backslash right\; \backslash Vert\; =\; r$. Assume the ordered vectors $\backslash vec\{q\}$ are assigned a coefficient {{mvar|p}} representing its place in order. Then an ordered vector $\backslash vec\{q\}\_\{p\},\; p\; \backslash in\; \backslash left\backslash \{1,\; 2,\; ...,\; \backslash sum\_\{x=1\}^k\; (x+1)\backslash right\backslash \}$ if all {{mvar|r}} are unique. Therefore {{mvar|V}} can be defined iteratively as

:$V\_\{\backslash vec\{q\}\_\{p\}\}\; =\; V\_\{\backslash vec\{q\}\_\{p-1\}\}\; +\; E\_\{\backslash vec\{q\}\_\{p\}\},\; V\_\{\backslash vec\{q\}\_\{0\}\}=0$,

or

:$V\_\{\backslash vec\{q\}\_\{p\}\}\; =\; \backslash sum\_\{x=1\}^p\; E\_\{\backslash vec\{q\}\_\{x\}\}$

If some $\backslash left\; \backslash Vert\; \backslash vec\{q\}\_\{x\}\; \backslash right\; \backslash Vert\; =\; \backslash left\; \backslash Vert\; \backslash vec\{q\}\_\{y\}\; \backslash right\; \backslash Vert$, then both vectors should be considered as the same {{mvar|p}} such that

$$V\_\{\backslash vec\{q\}\_\{p\}\}\; =\; V\_\{\backslash vec\{q\}\_\{p-1\}\}\; +\; E\_\{\backslash vec\{q\}\_\{p,1\}\}\; +\; E\_\{\backslash vec\{q\}\_\{p,2\}\},\; V\_\{\backslash vec\{q\}\_\{0\}\}=0$$

Note that each neighborhood will need to have the values from the next smallest neighborhood added. Ex. $V\_\{\backslash vec\{q\}=(0,2)\}\; =\; V\_\{\backslash vec\{q\}=(1,1)\}\; +\; E\_\{\backslash vec\{q\}=(0,2)\}$

{{mvar|V}} includes the center hypervoxel, which is not included in the connectivity. Subtracting 1 yields the neighborhood connectivity, {{mvar|G}}

:$G=V-1${{Cite book|last=Jonker|first=Pieter|title=Morphological Image Processing: Architecture and VLSI design|publisher=Kluwer Technische Boeken B.V.|year=1992|isbn=978-1-4615-2804-3|pages=92–96}}

Consider solving for $G|\backslash vec\{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 $\backslash max\; q\_i\; =\; 1$. $d=\backslash sqrt\{0^2\; +\; 1^2\; +\; 1^2\}=\backslash sqrt\{2\}$. The neighborhood is $M^3\_3$ and the hypersphere is $S\_3^\backslash sqrt\{2\}$

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

The basic $\backslash vec\{q\}$ in the neighborhood $N^3\_3$, $\backslash vec\{q\}\_\{1\}\; =\; (0,0,0)$. The Manhattan Distance between our vector and the basic vector is $\backslash left\; \backslash Vert\; \backslash vec\{q\}\; -\; \backslash vec\{q\}\_\{0\}\; \backslash right\; \backslash Vert\_1\; =\; 2$, so $\backslash vec\{q\}\; =\; \backslash vec\{q\}\_\{3\}$. Therefore,

:$G\_\{\backslash vec\{q\}\_\{3\}\}\; =\; V\_\{\backslash vec\{q\}\_\{3\}\}\; -\; 1\; =\; E\_\{\backslash vec\{q\}\_\{1\}\}\; +\; E\_\{\backslash vec\{q\}\_\{2\}\}\; +\; E\_\{\backslash vec\{q\}\_\{3\}\}\; -\; 1\; =\; E\_\{\backslash vec\{q\}=(0,0,0)\}\; +\; E\_\{\backslash vec\{q\}=(0,0,1)\}\; +\; E\_\{\backslash vec\{q\}=(0,1,1)\}$

:$E\_\{\backslash vec\{q\}=(0,0,0)\}\; =\; \backslash frac\{3!\}\{3!*0!*0!\}2^\{3-3\}\; =\; \backslash frac\{6\}\{6\}1\; =\; 1$

:$E\_\{\backslash vec\{q\}=(0,0,1)\}\; =\; \backslash frac\{3!\}\{2!*1!\}\; 2^\{3-2\}=\backslash frac\{6\}\{2\}\; 2\; =\; 6$

:$G\; =\; 1\; +\; 6\; +\; 12\; -\; 1\; =\; 18$

Which matches the supplied table

The assumption that all $\backslash left\; \backslash Vert\; \backslash vec\{q\}\_\{p\}\; \backslash right\; \backslash Vert\; =\; r$ are unique does not hold for higher values of k & N. Consider $N=2,\; k=5$, and the vectors $\backslash vec\{q\}\_\{A\}=(0,5),\; \backslash vec\{q\}\_\{B\}=(3,4)$. Although $\backslash vec\{q\}\_\{A\}$ is located in $M\_2^5$, the value for $r=25$, whereas $\backslash vec\{q\}\_\{B\}$ is in the smaller space $M\_2^4$ but has an equivalent value $r=25$. $\backslash vec\{q\}\_\{C\}=(4,4)\; \backslash 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, $\backslash begin\{cases\}\; N=2,\; k\; \backslash leq\; 4\; \backslash \backslash \; N=3,\; k\; \backslash leq\; 2\; \backslash \backslash \; N=4,\; k\; \backslash leq\; 1\; \backslash end\{cases\}$

At higher values of {{mvar|k}} & {{mvar|N}}, Values of {{mvar|d}} will become ambiguous. This means that specification of a given {{mvar|d}} could refer to multiple $\backslash vec\{q\}\_\{p\}\; \backslash in\; M\_n^N$.

File:Sasiedztwa 4 8.svg

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

: $\backslash textstyle(x\backslash pm1,\; y)$ or $\backslash textstyle(x,\; y\backslash pm1)$

is connected to the pixel at $\backslash textstyle(x,\; y)$.

{{See also|Von Neumann neighborhood}}

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 $\backslash textstyle(x+1,y+1)$ and $\backslash textstyle(x-1,y-1)$ are connected to the pixel at $\backslash textstyle(x,y)$.

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

{{See also|Moore neighborhood}}

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

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

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

• Grid cell topology
• Moore neighborhood

{{Reflist}}

• {{Citation | author=A. Rosenfeld, A. C. Kak | title=Digital Picture Processing | publisher=Academic Press, Inc.| year=1982 | isbn=0-12-597302-0 }}
• {{Citation

| url = http://www.mathworks.com/access/helpdesk_r13/help/toolbox/images/morph12.html

| title = Subband Weighting With Pixel Connectivity for 3-D Wavelet Coding

| year = 2009

| journal = IEEE Transactions on Image Processing

| pages = 52–62

| volume = 18

| issue = 1

| doi = 10.1109/TIP.2008.2007067

| accessdate = 2009-02-16

| pmid = 19095518

| last1 = Cheng

| first1 = CC

| last2 = Peng

| first2 = GJ

| last3 = Hwang

| first3 = WL

| bibcode = 2009ITIP...18...52C

}}

• {{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

| journal = IEEE Transactions on Image Processing

| pages = 52–62

| volume = 18

| issue = 1

| doi = 10.1109/TIP.2008.2007067

| accessdate = 2009-02-16

| pmid = 19095518

| last1 = Cheng

| first1 = CC

| last2 = Peng

| first2 = GJ

| last3 = Hwang

| first3 = WL

| bibcode = 2009ITIP...18...52C

}}

Category:Digital topology

Category:Graph connectivity