Conectividad de píxeles

En el procesamiento de imágenes , la conectividad de píxeles es la forma en que los píxeles en imágenes bidimensionales (o hipervóxeles en imágenes n-dimensionales) se relacionan con sus vecinos .

Formulación

Las 9 posibles conectividades en un barrio 5x5x5

Para especificar un conjunto de conectividades, se debe especificar la dimensión N y el ancho del vecindario n . La dimensión de un vecindario es válida para cualquier dimensión . Un ancho común es 3, lo que significa que a lo largo de cada dimensión, la celda central estará adyacente a 1 celda en cada lado para todas las dimensiones. ${\displaystyle n\geq 1}$

Sea un vecindario hipercúbico N-dimensional con tamaño en cada dimensión de ${\displaystyle M_{N}^{n}}$ ${\displaystyle n=2k+1,k\in \mathbb {Z} }$

Sea un vector discreto en la primera ortante desde el elemento estructurante central hasta un punto en el límite de . Esto implica que cada elemento y que al menos un componente ${\displaystyle {\vec {q}}}$ ${\displaystyle M_{N}^{n}}$ ${\displaystyle q_{i}\in \{0,1,...,k\},\forall i\in \{1,2,...,N\}}$ ${\displaystyle q_{i}=k}$

Sea una hiperesfera N-dimensional con radio de . ${\displaystyle S_{N}^{d}}$ ${\displaystyle d=\left\Vert {\vec {q}}\right\Vert }$

Defina la cantidad de elementos en la hiperesfera dentro del vecindario como E . Para un dado , E será igual a la cantidad de permutaciones de multiplicada por el número de ortantes. ${\displaystyle S_{N}^{d}}$ ${\displaystyle M_{N}^{n}}$ ${\displaystyle {\vec {q}}}$ ${\displaystyle {\vec {q}}}$

Sea la cantidad de elementos del vector que toman el valor j . ${\displaystyle n_{j}}$ ${\displaystyle {\vec {q}}}$ ${\displaystyle n_{j}=\sum _{i=1}^{N}(q_{i}=j)}$

El número total de permutaciones de se puede representar mediante un multinomio como ${\displaystyle {\vec {q}}}$ ${\displaystyle {\frac {N!}{\prod _{j=0}^{k}n_{j}!}}}$

Si hay alguno , entonces el vector es compartido en común entre los ortantes. Debido a esto, el factor multiplicador en la permutación debe ajustarse de a ${\displaystyle q_{i}=0}$ ${\displaystyle {\vec {q}}}$ ${\displaystyle 2^{N}}$ ${\displaystyle 2^{N-n_{0}}}$

Al multiplicar la cantidad de permutaciones por la cantidad ajustada de ortantes se obtiene:

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

Sea V el número de elementos dentro de la hiperesfera dentro del vecindario . V será igual al número de elementos en la hiperesfera más todos los elementos en las capas internas. Las capas deben ordenarse por orden creciente de . Suponga que a los vectores ordenados se les asigna un coeficiente p que representa su lugar en el orden. Entonces, un vector ordenado si todos los r son únicos. Por lo tanto, V se puede definir iterativamente como ${\displaystyle S_{N}^{d}}$ ${\displaystyle M_{N}^{n}}$ ${\displaystyle \left\Vert {\vec {q}}\right\Vert =r}$ ${\displaystyle {\vec {q}}}$ ${\displaystyle {\vec {q}}_{p},p\in \left\{1,2,...,\sum _{x=1}^{k}(x+1)\right\}}$

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

o

${\displaystyle V_{{\vec {q}}_{p}}=\sum _{x=1}^{p}E_{{\vec {q}}_{x}}}$

Si hay algunos , entonces ambos vectores deben considerarse como el mismo p tal que Nótese que cada vecindario deberá tener los valores del siguiente vecindario más pequeño agregados. Ej. ${\displaystyle \left\Vert {\vec {q}}_{x}\right\Vert =\left\Vert {\vec {q}}_{y}\right\Vert }$ $${\displaystyle V_{{\vec {q}}_{p}}=V_{{\vec {q}}_{p-1}}+E_{{\vec {q}}_{p,1}}+E_{{\vec {q}}_{p,2}},V_{{\vec {q}}_{0}}=0}$$ ${\displaystyle V_{{\vec {q}}=(0,2)}=V_{{\vec {q}}=(1,1)}+E_{{\vec {q}}=(0,2)}}$

V incluye el hipervóxel central, que no está incluido en la conectividad. Al restar 1 se obtiene la conectividad del vecindario, G

${\displaystyle G=V-1}$^[1]

Tabla de conectividades seleccionadas

Ejemplo

Considere resolver para ${\displaystyle G|{\vec {q}}=(0,1,1)}$

En este escenario, dado que el vector es tridimensional, dado que hay un . Asimismo, . dado que . . La vecindad es y la hiperesfera es ${\displaystyle N=3}$ ${\displaystyle n_{0}=1}$ ${\displaystyle q_{i}=0}$ ${\displaystyle n_{1}=2}$ ${\displaystyle k=1,n=3}$ ${\displaystyle \max q_{i}=1}$ ${\displaystyle d={\sqrt {0^{2}+1^{2}+1^{2}}}={\sqrt {2}}}$ ${\displaystyle M_{3}^{3}}$ ${\displaystyle S_{3}^{\sqrt {2}}}$

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

El básico en el vecindario , . La distancia de Manhattan entre nuestro vector y el vector básico es , por lo que . Por lo tanto, ${\displaystyle {\vec {q}}}$ ${\displaystyle N_{3}^{3}}$ ${\displaystyle {\vec {q}}_{1}=(0,0,0)}$ ${\displaystyle \left\Vert {\vec {q}}-{\vec {q}}_{0}\right\Vert _{1}=2}$ ${\displaystyle {\vec {q}}={\vec {q}}_{3}}$

${\displaystyle G_{{\vec {q}}_{3}}=V_{{\vec {q}}_{3}}-1=E_{{\vec {q}}_{1}}+E_{{\vec {q}}_{2}}+E_{{\vec {q}}_{3}}-1=E_{{\vec {q}}=(0,0,0)}+E_{{\vec {q}}=(0,0,1)}+E_{{\vec {q}}=(0,1,1)}}$

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

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

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

Que coincide con la tabla suministrada

Valores más altos de k y N

La suposición de que todos son únicos no se cumple para valores más altos de k & N. Considere , y los vectores . Aunque se encuentra en , el valor para , mientras que está en el espacio más pequeño pero tiene un valor equivalente . pero tiene un valor más alto de que el vector mínimo en . ${\displaystyle \left\Vert {\vec {q}}_{p}\right\Vert =r}$ ${\displaystyle N=2,k=5}$ ${\displaystyle {\vec {q}}_{A}=(0,5),{\vec {q}}_{B}=(3,4)}$ ${\displaystyle {\vec {q}}_{A}}$ ${\displaystyle M_{2}^{5}}$ ${\displaystyle r=25}$ ${\displaystyle {\vec {q}}_{B}}$ ${\displaystyle M_{2}^{4}}$ ${\displaystyle r=25}$ ${\displaystyle {\vec {q}}_{C}=(4,4)\in M_{2}^{4}}$ ${\displaystyle r=32}$ ${\displaystyle M_{2}^{5}}$

Para que esta suposición sea válida, ${\displaystyle {\begin{cases}N=2,k\leq 4\\N=3,k\leq 2\\N=4,k\leq 1\end{cases}}}$

A valores más altos de k y N , los valores de d se tornarán ambiguos. Esto significa que la especificación de un d dado podría referirse a múltiples . ${\displaystyle {\vec {q}}_{p}\in M_{n}^{N}}$

Tipos de conectividad

Bidimensional

Ejemplo de vecindad de píxeles: asociación de ocho y cuatro píxeles

4-conectado

Los píxeles 4-conectados son vecinos de cada píxel que toca uno de sus bordes. Estos píxeles están conectados horizontal y verticalmente. En términos de coordenadas de píxeles, cada píxel que tiene las coordenadas

${\displaystyle \textstyle (x\pm 1,y)}$o ${\displaystyle \textstyle (x,y\pm 1)}$

está conectado al píxel en . ${\displaystyle \textstyle (x,y)}$

6-conectado

Los píxeles 6-conectados son vecinos de cada píxel que toca una de sus esquinas (lo que incluye los píxeles que tocan uno de sus bordes) en una cuadrícula hexagonal o una cuadrícula rectangular con enlaces de camilla .

Existen varias formas de asignar mosaicos hexagonales a coordenadas de píxeles enteros. Con un método, además de los 4 píxeles conectados, los dos píxeles en las coordenadas y están conectados al píxel en . ${\displaystyle \textstyle (x+1,y+1)}$ ${\displaystyle \textstyle (x-1,y-1)}$ ${\displaystyle \textstyle (x,y)}$

8-conectado

Los píxeles conectados en 8 direcciones son vecinos de cada píxel que toca uno de sus bordes o esquinas. Estos píxeles están conectados horizontal, vertical y diagonalmente. Además de los píxeles conectados en 4 direcciones, cada píxel con coordenadas está conectado al píxel en . ${\displaystyle \textstyle (x\pm 1,y\pm 1)}$ ${\displaystyle \textstyle (x,y)}$

3-dimensional

6-conectado

Los píxeles 6-conectados son vecinos de cada píxel que toca una de sus caras. Estos píxeles están conectados a lo largo de uno de los ejes primarios . Cada píxel con coordenadas , o está conectado al píxel en . ${\displaystyle \textstyle (x\pm 1,y,z)}$ ${\displaystyle \textstyle (x,y\pm 1,z)}$ ${\displaystyle \textstyle (x,y,z\pm 1)}$ ${\displaystyle \textstyle (x,y,z)}$

18-conectado

Los píxeles conectados de 18 bits son vecinos de cada píxel que toca una de sus caras o bordes. Estos píxeles están conectados a lo largo de uno o dos de los ejes primarios. Además de los píxeles conectados de 6 bits, cada píxel con coordenadas , , , , o está conectado al píxel en . ${\displaystyle \textstyle (x\pm 1,y\pm 1,z)}$ ${\displaystyle \textstyle (x\pm 1,y\mp 1,z)}$ ${\displaystyle \textstyle (x\pm 1,y,z\pm 1)}$ ${\displaystyle \textstyle (x\pm 1,y,z\mp 1)}$ ${\displaystyle \textstyle (x,y\pm 1,z\pm 1)}$ ${\displaystyle \textstyle (x,y\pm 1,z\mp 1)}$ ${\displaystyle \textstyle (x,y,z)}$

26-conectado

Los píxeles conectados de 26 bits son vecinos de cada píxel que toca una de sus caras, bordes o esquinas. Estos píxeles están conectados a lo largo de uno, dos o los tres ejes primarios. Además de los píxeles conectados de 18 bits, cada píxel con coordenadas , , o está conectado al píxel en . ${\displaystyle \textstyle (x\pm 1,y\pm 1,z\pm 1)}$ ${\displaystyle \textstyle (x\pm 1,y\pm 1,z\mp 1)}$ ${\displaystyle \textstyle (x\pm 1,y\mp 1,z\pm 1)}$ ${\displaystyle \textstyle (x\mp 1,y\pm 1,z\pm 1)}$ ${\displaystyle \textstyle (x,y,z)}$

Véase también

• Topología de celdas de cuadrícula
• Barrio de Moore

Referencias

1. Jonker, Pieter (1992). Procesamiento de imágenes morfológicas: arquitectura y diseño VLSI . Kluwer Technische Boeken BV págs. 92–96. ISBN 978-1-4615-2804-3.

• A. Rosenfeld, AC Kak (1982), Procesamiento de imágenes digitales , Academic Press, Inc., ISBN 0-12-597302-0
• Cheng, CC; Peng, GJ; Hwang, WL (2009), "Ponderación de subbanda con conectividad de píxeles para codificación wavelet 3-D", IEEE Transactions on Image Processing , 18 (1): 52–62, Bibcode :2009ITIP...18...52C, doi :10.1109/TIP.2008.2007067, PMID  19095518 , consultado el 16 de febrero de 2009
• Cheng, CC; Peng, GJ; Hwang, WL (2009), "Ponderación de subbanda con conectividad de píxeles para codificación wavelet 3-D", IEEE Transactions on Image Processing , 18 (1): 52–62, Bibcode :2009ITIP...18...52C, doi :10.1109/TIP.2008.2007067, PMID  19095518 , consultado el 16 de febrero de 2009