1.7 Geometría Digital
Esta sección presenta algunas de las propiedades geométricas básicas de los subconjuntos de una imagen digital. Anteriormente mencionamos el concepto de conectividad para tales subconjuntos; ahora definimos este concepto de una manera más precisa. También definimos los bordes de un subconjunto, e indicamos por qué pueden ser contemplados como curvas cerradas. También se presentarán algunos otros conceptos de la geometría digital, incluyendo algunas funciones de distancia digitales básicas tales como la distancia “bloque de ciudad” y la distancia “tablero de ajedrez”.
Los resultados presentados en esta sección no son evidentes en absoluto; muchos de ellos requieren demostraciones bastante extensas. No daremos esas demostraciones aquí; para una introducción matemática al tema ver [55].
Un punto P = (x, y) de una imagen digital S tiene cuatro vecinos horizontales y verticales, a saber, los puntos
(x – 1, y), (x, y – 1), (x, y + 1), (x + 1, y)
Llamaremos a estos puntos los 4-vecinos de P, y diremos que son 4-adyacentes a P. Además, P tiene cuatro vecinos diagonales, a saber,
(x – 1, y – 1), (x - 1, y + 1), (x + 1, y - 1), (x + 1, y + 1)
Estos, junto a los 4-vecinos, reciben el nombre de 8-vecinos de P (8-adyacentes a P). Nótese que si P está en el borde de S, alguno de sus vecinos pueden no existir. Si S y T son subconjuntos de S, decimos que S es 4- (8-) adyacente a T si algún punto de S es 4- (8-) adyacente a algún punto de T.
a.
Conectividad
Un camino p de longitud n desde P a Q en S es una secuencia de puntos P = P0, P1, ..., Pn = Q tal que Pi es un vecino de Pi-1, 1 £ i £ n. Nótese que hay dos versiones de esta y de la siguientes definiciones, dependiendo de si “vecino” significa “4-vecino” o “8-vecino”. Así podemos hablar de p siendo un 4-camino o un 8-camino.
Sea S un subconjunto de S, y sean P, Q puntos de S. Decimos que P está (4- o 8-) conectado a Q en S si existe un (4- o 8-) camino desde P a Q que esté formado enteramente por puntos de S. Para cada P de S, el conjunto de puntos que están conectados a P en S se dice que es una componente conexa de S. Si S tiene sólo una componente, se dice que es un conjunto conexo. Por ejemplo, si denotamos los puntos de S mediante 1’s, el conjunto
1
1
es 8-conexo pero no 4-conexo.
Se puede ver fácilmente que el “estar conectado a” es reflexivo, simétrico, y transitivo, así que es una relación de equivalencia, i.e., para todos los puntos P, Q, R de S:
(a) P está conectado a P (apunte: un camino p puede tener longitud n = 0);
(b) Si P está conectado a Q, entonces Q está conectado a P;
(c) Si P está conectado a Q y Q a R, entonces P está conectado a R.
Así dos puntos están conectados entre ellos en S sii pertenecen a la misma componente de S.
b. Agujeros y “estar
rodeado”
Sea Š el complemento de S. Asumiremos , por simplicidad, que el borde S’ de S (i.e. su primera y última fila y sus columnas izquierda y derecha) está en Š. A la componente de Š que contiene a S’ se le llama el fondo (background) de S. A todas las demás componentes de Š, si las hay, se les llama agujeros (holes) en S. Si S es conexa y no tiene agujeros, se le llama conexa simple; si es conexa pero tiene agujeros se le llama conexa múltiple.
Tratando con conectividad en S y Š , se hace deseable usar tipos opuestos de conectividad para S y para Š, i.e., si usamos 4- para S, entonces deberemos usar 8- para Š, y viceversa. Esto nos permitirá tratar los bordes como curvas cerradas. Adoptaremos este convenio a partir de ahora.
Sean S y T cualesquier subconjunto de S. Decimos que T rodea a S si cualquier camino desde cualquier punto de S al borde de S debe encontrarse con T, i.e., si para cualquier camino P0, P1, ..., Pn tal que P0 está en S y Pn está en el borde de la imagen, algún Pi debe estar en T. Evidentemente el fondo de S rodea a S. Por otro lado, S rodea cualquier agujero de S; si no fuera así, habría un camino desde el agujero al borde de S que no pasara por S, contradiciendo así el hecho de que el agujero y el borde están en diferentes componentes de Š. El tipo de camino aquí (4- o 8-) debe ser el mismo que el tipo de conectividad usada para Š.
c.
Bordes
Como se indicó en la Sección 1.3, el borde S’ de un conjunto S es el conjunto de puntos de S que son adyacentes a Š. Asumiremos, por simplicidad, que “adyacente” aquí significa “4-adyacente”. Al conjunto de los puntos de S que no pertenecen al borde se le llama el interior de S.
Sea C un componente de S, y sea D un componente de Š que es adyacente a C. Nótese que si C y D son 8-adyacentes, también son 4-adyacentes; verdaderamente, consideremos el patrón
P
X
Y Q
donde P está en C y Q en D. Si X está en S, está en C y si está en Š, entonces está en D, y de forma similar para Y; así en cualquier caso C y D son “4-adyacentes”.
Al conjunto CD de puntos de C que son adyacentes a D se le llama el D-borde de C. De forma análoga, al conjunto DC de puntos de D que son adyacentes a C se le llama el C-borde de D. Son estos componentes de borde los que pueden ser considerados como curvas cerradas, y para los que podemos definir algoritmos de seguimiento de bordes, como veremos en la Sección 2.2.
Se puede demostrar que si C es adyacente a varios componentes de Š, entonces exactamente uno de esos componentes, digamos D0, rodea a C, y los otros están rodeados por C. Al D0-borde de C se le llama borde externo, y a los otros D-bordes de C, si los hay, se les llama bordes de agujero. Esta propiedad de “estar rodeado” es la que nos permite tratar los bordes como curvas cerradas. Es cierto sólo si usamos tipos opuestos de conectividad para S y para Š. Por ejemplo, supongamos que usamos 4-conectividad tanto para S como para Š, y que los puntos de S son
1 1
1 1
1 1 1 1
1 1 1 1
1 1
1 1
Entonces cada bloque C de 1’s es una 4-componente de S, y el bloque D de 0’s que rodean es una 4-componente de Š, pero CD y DC no son curvas cerradas, y D no rodea a los C’s ni éstos le rodean a él. De forma similar, si usamos 8-conectividad tanto para S como para Š, entonces S y Š cada uno consiste en una sola componente pero SŠ y ŠS no son curvas cerradas. Por otro lado, si usamos 4-conectividad para S y 8- para Š, entonces cada bloque C de S es una componente, todo Š es una sola componente, y cada CŠ y ŠC es una curva cerrada. Similarmente, si usamos 8- para S y 4- para Š, entonces S consiste en una sola componente, Š tiene el bloque D de 0’s rodeado como una componente, y SD y DS son curvas cerradas.
De forma alternativa, podemos definir el (C, D)-borde (de C o D) como el conjunto de pares (P, Q) tales que P está en C, Q en D, y P, Q son 4-adyacentes. Esto es lo mismo que el conjunto de “fisuras” entre los puntos de C y los puntos adyacentes de D. Es evidente que cualesquiera tales borde deben ser disjuntos.
Las propiedades de “estar rodeado” y curvas cerradas se mantienen sólo cuando C y D son componentes de un conjunto S y su complemento, respectivamente. Si tomamos un C y un D, subconjuntos conexos arbitrarios de S, no podemos decir nada sobre el D-borde de C; C y D pueden tocarse en muchos sitios diferentes, ninguno de los dos tiene por qué rodear al otro, y el borde no tiene por qué ser nada parecido a una curva cerrada.
d.
Distancia
La distancia euclídea entre dos puntos P = (x, y) y Q = (u, v) es
A veces es conveniente trabajar con medidas más simples de distancia sobre imágenes digitales. En concreto, la distancia bloque de ciudad entre P y Q se define como
d4(P, Q) = ½x – u ½ + ½ y – v ½
y la distancia tablero de ajedrez entre ellos es
d8(P, Q) = max(½x – u ½,½ y – v ½)
Se puede comprobar que estas tres medidas, de, d4, y d8, son métricas, i.e., para cada P, Q, R tenemos
d(P, Q) ³ 0, y = 0 sii P = Q
d(P, Q) = d(Q, P)
d(P, R) £ d(P, Q) + d(Q, R)
En otras palabras, cada una de estas d’s es definida positiva, simétrica, y satisface la desigualdad triangular.
No es difícil ver que los puntos a una distancia bloque de ciudad £ t de P forman un rombo (i.e. un cuadrado orientado diagonalmente) centrado en P. Por ejemplo, si representamos los puntos por sus distancias a P (entonces P se representa por un 0), los puntos a distancia £ 2 son
En concreto, los
puntos a distancia 1 son justo los 4-vecinos de P. Se puede demostrar que d4(P, Q) es igual que la longitud del 4-camino
más corto desde P hasta Q. (¡Nótese que podría haber muchos
caminos así!)
Análogamente, los puntos a distancia tablero de ajedrez £ t de P forman un cuadrado vertical centrado en P; e.g., los puntos a distancia £ 2 son
así que los puntos a
distancia 1 son los 8-vecinos de P. En general, d8(P, Q) es la longitud del 8-camino más corto
de P a Q, y muchos de tales caminos.
La distancia entre un punto P y un conjunto S se define como la mínima distancia entre P y cualquier punto de S. El diámetro de un conjunto es la mayor distancia entre dos puntos cualesquiera del conjunto.