Pixel connectivity

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 ${\displaystyle 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 ${\displaystyle M_N^n}$ represent a N-dimensional hypercubic neighborhood with size on each dimension of ${\displaystyle n=2k+1,k\in \mathbb{Z}}$

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

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

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

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

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

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

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

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

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

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

or

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

If some ${\displaystyle \Vert {\overrightarrow{q}}_x\Vert =\Vert {\overrightarrow{q}}_y\Vert }$, then both vectors should be considered as the same p such that $${\displaystyle 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. ${\displaystyle V_{\overrightarrow{q}=(0,2)}=V_{\overrightarrow{q}=(1,1)}+E_{\overrightarrow{q}=(0,2)}}$

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

${\displaystyle G=V-1}$

Table of Selected Connectivities

Example

Consider solving for ${\displaystyle G|\overrightarrow{q}=(0,1,1)}$

In this scenario, ${\displaystyle N=3}$ since the vector is 3-dimensional. ${\displaystyle n_0=1}$ since there is one ${\displaystyle q_i=0}$. Likewise, ${\displaystyle n_1=2}$. ${\displaystyle k=1,n=3}$ since ${\displaystyle max{q}_i=1}$. ${\displaystyle d=\sqrt{0^2+1^2+1^2}=\sqrt{2}}$. The neighborhood is ${\displaystyle M_3^3}$ and the hypersphere is ${\displaystyle S_3^{\sqrt{2}}}$

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

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

${\displaystyle 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)}}$

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

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

${\displaystyle G=1+6+12-1=18}$

Which matches the supplied table

Higher values of k & N

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

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

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