2.1
Bloques
a.
MATs
En la sección 1.2a definimos el MAT como un conjunto de bloques maximales de valor constante (= cuadrados con lados de longitud impar) en S. Cuando S es dividido en S y Š, podemos hablar del MAT de S (definido por el bloques maximales que están contenidos en S) y del MAT de Š.
Observemos primero que el MA de S (= el conjunto de los centros de los bloques del MAT) consiste en aquellos puntos de S cuya distancia tablero de ajedrez (= d8) desde Š es la máxima local. Recordemos que los puntos dentro de una distancia tablero de ajedrez dada de P forman un cuadrado centrado en P. Si d8(P, Š) = d, entonces el cuadrado SP (d-1) de radio d – 1 centrado en P no puede intersectar Š (puesto que habría entonces un punto de Š a una distancia £ d – 1 de P), pero el cuadrado de radio d sí intersecta Š. Supongamos que d8(P, Š) no es un máximo local; entonces P tiene un vecino Q tal que d8(Q, Š) ³ d + 1. Así un cuadrado SQ de radio ³ d centrado en Q no intersecta a Š; pero SQ contiene a SP (d-1) así que SP (d-1) no es un bloque maximal. Recíprocamente, si SP (d-1) no es maximal, no es difícil ver que debe estar contenido en un cuadrado SQ de valor constante centrado en algún vecino de P, y SQ tiene de radio al menos d; así d8(Q, Š) ³ d, de forma que d8(P, Š) no es maximal.
De forma análoga, si definimos el MAT usando cuadrados orientados diagonalmente mejor que verticales, podemos mostrar que el MA de S consiste en aquellos puntos de S cuyas distancias bloque de ciudad (d4) desde Š son máximos locales. En este caso “máximo local” significa que ningún 4-vecino del punto tiene una distancia mayor desde Š, mientras que en el caso previo los puntos MA eran 8-vecinos de distancia máxima. La Figura 8 muestra los conjuntos de distancias bloque de ciudad y tablero de ajedrez a Š cuando S es un rectángulo o un rombo; el máximo local en cada caso está subrayado.
Estas observaciones implican que podemos construir el MAT de S calculando las distancias a Š desde todos los puntos de S y descartando los que no son máximos. En las siguientes dos subsecciones presentaremos algunos algoritmos para calcular estas distancias a partir de una matriz binaria dada o una representación fila-a-fila.
Puesto que el MA es un conjunto de distancias locales máximas, normalmente es bastante disconexo; de hecho, dos máximos no pueden ser adyacentes a menos que sus valores sean iguales. Podemos intentar hacer el MA conexo manteniendo algunos de los no máximos. Por ejemplo, en el caso d8, podríamos conservar P si al menos alguno de sus 8-vecinos tiene una distancia mayor a Š, y si tiene un 4-vecino que es una distancia máxima. [La primera condición implica que el estrato de puntos a una distancia d8(P) de Š se va afilando en P]. Por supuesto, cuando descartamos menos puntos, tenemos una representación menos económica de S. De todas formas, si podemos encontrar un conjunto de arcos y curvas que contengan al MA, podemos representar esas curvas mediante códigos de cadenas, mejor que teniendo que enumerar todos los puntos individualmente, así que la economía de la representación puede ser mejorada.
Fig.8 Distancias a Š por los puntos de un rectángulo y un
rombo; los puntos MA están subrayados. (a) d4; (b) d8 .
Nótese que los valores de d4 y d8 para el rectángulo son los mismos. Los radios de los MAT
son una unidad menor que las distancias.
b. Cálculo de la
distancia
Primero damos un algoritmo para el cálculo de distancias ordenadores multiprocesadores. Este algoritmo vale para cualquier medida d que sea un entero y tenga la siguiente propiedad:
Para todo P, Q tales que d(P, Q) ³ 2, existe un punto R, diferente de P y Q, tal que d(P, Q) = d(P, R) + d(R, Q).
A tales métricas las llamaremos regulares. Se puede comprobar que d es regular si, y sólo si, para todo P, Q , distintos, existe un punto R tal que d(P, R) = 1 y d(P, Q) = d(R, Q) + 1. §
Dado cS, que vale 1 en los puntos de S y 0 en cualquier otro, definimos cS (m) por inducción para m = 1,2,... como sigue:
(1)
donde cS (0) = cS. Así cS (m) puede ser calculado realizando una operación local sobre el par de matrices cS (0) y cS (m-1) en cada punto.
Para ver como (1) trabaja, fíjese primero que los 0’s (i.e., los puntos de Š) continúan siendo 0’s, puesto que si cS (0)(P) = 0 tenemos
De forma similar, los 1’s a distancia 1 de Š (por ejemplo, 1’s del borde) permanecen como1’s, puesto que para tales puntos también, el mínimo es 0. Por otro lado, en la primera iteración de (1), todos los 1’s a distancia > 1 de Š (i.e., los 1’s interiores) se convierten en 2’s, ya que para tales puntos el mínimo es 1. En la segunda iteración, todos los 2’s interiores ( = todos los 2’s a distancia > 2 de Š) se convierten en 3’s, ya que el mínimo para esos puntos es 2. En la tercera iteración, todos los 3’s interiores se pasan a 4’s, y así sucesivamente. De esta manera, si d(P, Š) = k > 0, los valores de cS (m)(P) para m = 1,2,...,k son 1,2,...,k, respectivamente, y el valor se mantiene k en todas las iteraciones subsiguientes. Se ve que si m es la distancia mayor entre Š y cualquier punto de la imagen, tenemos cS (m)(P) = d(P, Š) para todo P. Realmente es suficiente con iterar (1) un número de veces igual al diámetro de la imagen; para una imagen n x n, es 2(n – 1) para d4, y n – 1 para d8.
Si queremos encontrar el camino más corto desde cada P a Š, entonces en la iteración en la que cS (m)(P) deja de incrementarse, creamos un puntero desde P a uno de sus vecinos que tenga el mínimo valor en (1). Este vecino debe estar en un camino más corto desde P hasta Š, así que si seguimos los punteros empezando en P, debemos movernos a lo largo de un camino más corto a Š [61]: Nótese, a propósito, que P es un punto MA sii no se encuentra en un camino más corto desde otro punto de S hasta Š. De hecho, si P estuviera en un camino más corto desde Q hasta Š, su predecesor en este camino sería un vecino de P y tendría mayor distancia a Š que P.
Las métricas d4 y d8 son muy no-euclídeas; el conjunto de puntos a distancia £ k desde un punto dado es un cuadrado, más que un círculo, para estas métricas. Podemos calcular una distancia en la que este conjunto es un octágono usando d4 y d8 en iteraciones alternadas en (1). Los puntos a una “distancia octogonal” £ 2 son
Para obtener el MAT
para esta distancia, podemos usar el 4-vecino máximo. Cuando la distancia es
impar, y el 8-vecino máximo cuando
es par, para asegurarse de que el argumento dado en la subsección (a) continúa
siendo válido.
El algoritmo (1) es bastante eficiente en un ordenador multiprocesador, puesto que cada iteración puede ser realizada para todos los puntos en paralelo, y el número de iteraciones es como máximo el diámetro de la imagen. En un ordenador convencional, por el contrario, cada iteración requiere un número de pasos proporcional al área de la imagen. Ahora presentamos un algoritmo que calcula todas las distancias (d4 o d8) a Š en sólo dos rastreos de la imagen, de forma que no es necesario un gran número de iteraciones. Asumimos que el borde de la imagen está compuesto completamente por 0’s. Sea N1(P) el conjunto de (4- ó 8-) vecinos que preceden a P en un rastreo fila a fila (de izquierda a derecha, de arriba a abajo), y N2(P) los restantes (4- ó 8-)vecinos de P; i.e., N1(x, y) está compuesto por los 4-vecinos (x – 1, y) y (x, y + 1), también los 8-vecinos (x – 1, y + 1) y (x + 1, y + 1). Entonces el algoritmo es como sigue:
Así podemos calcular
cS’ en un simple rastreo de
izquierda a derecha y de arriba debajo de la imagen, ya que para cada P, cS’ ya ha sido calculado para
los Q’s de N1.
De forma similar, podemos calcular cS’’ en un simple rastreo inverso (de derecha a izquierda, de abajo a arriba). Entonces para todos los P tenemos cS’’(P) = d4(P, Š) o d8(P, Š), dependiendo de si usamos 4- ó 8- vecinos en el algoritmo. Como un ejemplo muy simple sea cS’
0 1 1 1
1 1 1 0
1 1 1 1
rodeado de 0’s. Entonces cS’ en el caso de 4-vecinos es
0 1 1 1
1 2 2 0
1 2 3 1
y cS’’ es
0 1 1 1
1 2 1 0
1 1 1 1
c. Encogimiento y
expansión
Cualquier S puede ser “encogido” borrando repetidamente su borde, y expandido añadiéndole repetidamente el borde de su complemento Š. En general, con el borde de S queremos decir el conjunto de puntos que están a distancia 1 de Š. Sea S’ el borde de S en este sentido general; entonces las estaciones sucesivas durante el encogimiento de S son S(0) º S, S(-1) º S – S’, S(-2) º S(-1) – S(-1)’, y así sucesivamente. De forma similar, las estaciones sucesivas durante la expansión de S son S(1) º S È (Š)’; S(2) º S(1) È (Š (1))’; y así sucesivamente. Se puede ver fácilmente que para cualquier k tenemos
o, de forma
equivalente,
Dado cS, obtenemos cS (1) cambiando los 0’s por 1’s si tienen algún 1’s como vecino (i.e., a distancia 1), y obtenemos cS (-1) cambiando los 1’s a 0’s si tienen algún 0’s como vecinos.
Debería señalarse que el encogimiento y la expansión no conmutan entre sí;(S(m))(-n) no tiene que ser necesariamente igual que (S(-n))(m), y ninguna de ellas es igual que S(m-n). Por ejemplo, si S consta de un solo punto P, entonces S(1) consta de P y sus vecinos, y (S(1))(-1) = S = {P}; pero S(-1) está vacío, y también (S-1)(1). De todas maneras, se puede demostrar que (S(-n))(m) Í S(m-n) Í (S(m))(-n). En particular, tenemos (S(-k))(k) Í S Í (S(k))(-k) para todo k.
En la secciones 3.2d y 3.4b enseñaremos como pueden usarse combinaciones de encogimiento y expansión para definir y detectar partes alargadas, partes aisladas, grupos de partes de un conjunto de S y eliminar el “ruido” de S. En esta sección estamos interesados principalmente en cómo el encogimiento y la expansión están relacionados con la distancia y con el MAT. Puesto que S’ es el conjunto de puntos de S que están a distancia 1 de Š, S(t) se lee como el conjunto de puntos a distancia £ t de S, y S(-t) es el conjunto de puntos a distancia > t de Š. Así cS (m) = cS + cS (-1) + ...+ cS (-m), lo que nos da un algoritmo para calcular las distancias a Š mediante sucesivos encogimientos y expansiones.
Para obtener el MA de S mediante encogimiento y expansión procedemos como sigue:
Sea Sk = S(-k) – (S(-k-1))(1) (nótese que el primero de estos conjuntos contiene al segundo). Cualquier punto P de Sk está exactamente a una distancia k + 1 de Š, ya que si estuviera más lejos estaría en S(-k-1), por tanto en (S(-k-1))(1). Es más, P no tiene vecinos cuyas distancias desde Š sean mayores que k + 1, ya que cualquier vecino así estaría en S(-k-1), así que P estaría en (S(-k-1))(1). Así la distancia de P a Š es un máximo local, haciéndole un punto MA; de hecho, Sk es justo el conjunto de puntos MA que están a distancia k + 1 de Š.
El encogimiento y la expansión pueden hacer uso de vecindades arbitrarias [70]. Denotemos con N(P) la “vecindad” de P; ésta podría consistir en P junto con cualquier conjunto de puntos que tengan una posición relativa dada con P. Entonces podemos definir la N-expansión de S como
y la N-contracción de S como
{ P Î S | N(P) Ç Š = Æ }
Si las vecindades son simétricas [i.e., Q Î N(P) sii P Î N(Q)], estas operaciones son complementarias, i.e. la N-contracción de S es el complemento de la N-expansión de Š, y viceversa. Estas operaciones pueden ser iteradas o combinadas de diversas formas, como antes. Nótese que si N(P) consta de los puntos a distancia £ 1 de P, estas definiciones se reducen a las dadas anteriormente.
Las operaciones análogas al encogimiento y expansión para imágenes multivaluadas [41] son operaciones de min local y max local definidas sobre una vecindad dada. Nótese que si hay sólo 2 valores, 0 y 1, local min encoge los 1’s, mientras que local max los expande. Así como el encogimiento y expansión pueden ser usados para borrar el ruido de una imagen segmentada (2-valuada), las operaciones min local y max local pueden ser usadas para suavizar imágenes multivaluadas.
Un paso simple de encogimiento o expansión puede ser hecho en una sola operación en un ordenador multiprocesador, pero requiere un rastreo completo de la imagen en un ordenador convencional. En cada fila, los puntos son marcados para cambiar (de 1 a 0 o de 0 a 1), pero no son realmente cambiados hasta que la siguiente fila ha sido marcada. Si queremos hacer una secuencia de k pasos sin tener que rastrear la imagen entera k veces, podemos operar sobre las filas en una secuencia tal como 1; 2,1; 3, 2, 1; 4, 3, 2, 1, ...(Una vez que hemos operado sobre la segunda fila, podemos hacer una segunda operación sobre la primera fila; una vez que hemos operado sobre la tercera fila, podemos hacer una segunda operación sobre la segunda y entonces una tercera operación sobre la primera fila; y así sucesivamente.) Una vez que hemos alcanzado la fila k-èsima, y hecho la secuencia k, (k – 1),...2,1 hemos terminado con la primera fila, ya que ha sido procesada k veces. La siguiente secuencia es (k +`1), k, ..., 3, 2, después de la cual habremos terminado con la segunda fila, y la primera ya puede ser abandonada. La siguiente secuencia es (k + 2), (k + 1), ..., 4, 3, después de la cual la segunda fila puede ser abandonada, y así sucesivamente. Así sólo k + 2 filas (aquellas que están siendo procesadas, más una anterior y otra detrás de ellas) tienen que estar disponibles al mismo tiempo.
d. Reconstrucción a partir de
los MATs
Dado el MAT de S, podemos construir cS creando cuadrados sólidos de 1’s con centro y radio especificados. De forma alternativa, podemos representar el MAT por una imagen SS cuyos valores a la distancia máxima son iguales a sus distancias, y constan de 0’s en cualquier parte. Podemos, entonces, reconstruir el conjunto completo de distancias a Š aplicando un algoritmo iterativo a SS [compare (1)]:
El número de
iteraciones requerido es una unidad menor a el valor de la distancia máxima
mayor. Como ejemplo, si SS es
(ver Fig. 8a), donde los 0’s están
representados por blancos, entonces dos iteraciones de (3) usando d4 dan
como en la Fig. 8a. De forma alternativa, podemos reconstruir las
distancias usando el siguiente algoritmo en dos pasos [compare (2)]:
(3)
Aquí primero
calculamos S’ en un rastreo de izquierda a derecha y de arriba a abajo, y
entonces calculamos S’’ en un rastreo de derecha a izquierda y de abajo a arriba. En el
ejemplo dado más arriba usando d4, SS‘y SS‘’son
respectivamente. Se puede demostrar que el MAT es el conjunto más pequeño de los valores de distancia a partir del cual todos los valores de distancia pueden ser reconstruidos usando (3) o (4). S, a su vez, es entonces justo el conjunto de puntos que tienen valores distintos a cero después de que (3) y (4) hayan sido aplicados.
e. Árboles de
cuadrados
En esta subsección describimos brevemente métodos de conversión entre el árbol de cuadrados y la representación binaria de un S dado. Los detalles de los algoritmos se pueden encontrar en tres artículos de Samet [63,65,67].
En la Sección 1.2b describíamos un método para la construcción del árbol de cuadrados correspondiente a una imagen binaria dada, subdividiendo recursivamente la imagen en bloques que sean cuadrantes, subcuadrantes, .... Si un bloque consta sólo de 1’s o 0’s , corresponde a un nodo hoja “negro”(relleno) o “blanco”(hueco) en el árbol; en otro caso corresponde a un nodo no-hoja “gris”, que tiene cuatro hijos que se corresponden con sus cuatro cuadrantes. Si hacemos esto en secuencia “arriba-abajo”, i.e., primero examinar la imagen entera, después sus cuadrantes, después los cuadrantes de los cuadrantes, etc., tanto como haga falta, puede requerir un esfuerzo computacional excesivo, puesto que partes de la imagen que contienen mezclas sútilmente divididas de 0’s y 1’s serán examinados repetidamente.
Como una alternativa, podemos construir el árbol de cuadrados de abajo a arriba rastreando la imagen en el un orden adecuado, e.g,. en la secuencia
donde los números indican el orden en el que los puntos son examinados. Conforme descubramos bloques maximales de 0’s o de 1’s, añadimos nodos hojas al árbol, junto con sus nodos grises antecesores correspondientes. Esto puede ser hecho de una forma en la que los nodos hojas no son nunca creados hasta que se sabe que son maximales, así nunca es necesario fusionar cuatro hojas del mismo color y cambiar su nodo padre común de gris a blanco o negro . Para detalles de este algoritmo ver [65].
La construcción de árboles de cuadrados de abajo a arriba llega a ser algo más complicado si queremos rastrear la imagen fila a fila. Aquí añadimos un nodo hoja al árbol cuando descubrimos bloques maximales 1 x 1 ó 2 x 2 de 0’s ó 1’s; si cuatro hojas con un padre común tienen todas el mismo color, son fusionadas. Los detalles pueden ser encontrados en [67].
Dado un árbol de cuadrados, podemos construir la correspondiente imagen binaria recorriendo el árbol y, para cada hoja, creando un bloque de 0’s ó 1’s del tamaño adecuado en la posición adecuada. Un proceso más complicado puede ser usado si queremos crear la imagen fila a fila. Aquí debemos visitar cada nodo del árbol de cuadrados una vez para cada fila que lo intersecte (i.e., un nodo correspondiente a un bloque 2k x 2k es visitado 2k veces), y, para cada hoja, devolver una secuencia de 0’s ó 1’s de la longitud apropiada (2k) en la posición adecuada. Para los detalles, ver [63].