Pixel connectivity

In image processing, pixel connectivity is the way in which pixels in 2-dimensional (or hypervoxels in n-dimensional) images relate to their neighbors.

FormulationEdit

 
The 9 possible connectivities in a 5x5x5 neighborhood


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 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,  

 [1]

Table of Selected ConnectivitiesEdit

Neighborhood Size:

 

Connectivity Type Typical Vector:

 

Sphere Radius

 

Elements on Sphere:

 

Elements in Sphere:

 

Neighborhood Connectivity:

 

1 edge (0) 0 1*1=1 1 0
3 point (1) 1 1*2=2 3 2
5 point-point (2) 4 1*2=2 5 4
...
1x1 face (0,0) 0 1*1=1 1 0
3x3 edge (0,1) 1 2*2=4 5 4
point (1,1) 2 1*4=4 9 8
5x5 edge-edge (0,2) 4 2*2=4 13 12
point-edge (1,2) 5 2*4=8 21 20
point-point (2,2) 8 1*4=4 25 24
...
1x1x1 volume (0,0,0) 0 1*1=1 1 0
3x3x3 face (0,0,1) 1 3*2=6 7 6
edge (0,1,1) 2 3*4=12 19 18
point (1,1,1) 3 1*8=8 27 26
5x5x5 face-face (0,0,2) 4 3*2=6 33 32
edge-face (0,1,2) 5 6*4=24 57 56
point-face (1,1,2) 6 3*8=24 81 80
edge-edge (0,2,2) 8 3*4=12 93 92
point-edge (1,2,2) 9 3*8=24 117 116
point-point (2,2,2) 12 1*8=8 125 124
...
1x1x1x1 hypervolume (0,0,0,0) 0 1*1=1 1 0
3x3x3x3 volume (0,0,0,1) 1 4*2=8 9 8
face (0,0,1,1) 2 6*4=24 33 32
edge (0,1,1,1) 3 4*8=32 65 64
point (1,1,1,1) 4 1*16=16 81 80
...

ExampleEdit

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 & NEdit

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 connectivityEdit

2-dimensionalEdit

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

4-connectedEdit

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-connectedEdit

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-connectedEdit

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-dimensionalEdit

6-connectedEdit

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-connectedEdit

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-connectedEdit

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 alsoEdit

ReferencesEdit

  1. ^ Jonker, Pieter (1992). Morphological Image Processing: Architecture and VLSI design. Kluwer Technische Boeken B.V. pp. 92–96. ISBN 978-1-4615-2804-3.