1.2
Bloques
a.
MATs
Con cada punto P de la imagen S, asociaremos un conjunto de cuadrados de lados de longitud impar n centrados en P. (Nuestra discusión se generaliza a cualquier familia de formas mutuamente similares, pero para simplificar asumiremos que son cuadrados verticales y que todos tienen P en sus centros). Sea SP el más grande de tales cuadrados que está contenido en S y tiene un valor constante, y sea rP el radio de SP. Pueden existir otros puntos Q tales que SP está contenido en SQ; si no existe tal Q, llamaremos a SP un bloque maximal.
Es fácil ver que si especificamos el conjunto de centros P, radios rP , y valores vP de los bloques maximales, S está completamente determinada, puesto que cualquier punto de S se encuentra en al menos un bloque maximal. De hecho, necesitamos sólo hacer esto para m – 1 de los valores; los puntos no cubiertos por alguno de estos bloques deben tener el valor omitido. Así en el caso en el que hay sólo dos valores, necesitamos sólo especificar los bloques para un valor. El bloque maximal para una imagen simple se muestra en la fig. 2.
El conjunto de centros y radios (y valores) de un bloque maximal se denomina medial axis (o symetrical axis) transformation de S, abreviadamente MAT o SAT. Tiene este nombre porque los centros están localizados en los puntos medios, o a lo largo de los ejes simétricos locales, de las regiones de valor constante en S. De forma intuitiva, si un bloque SP es maximal y está contenido en la región S de valor constante, debe tocar el borde de S en al menos dos sitios; en caso contrario podríamos encontrar un vecino Q de P que estaba mucho más lejos que P del borde de S, y entonces SQ contendría a SP. Un tratamiento más riguroso de estas ideas se dará en la sección 2.1.
Evidentemente, si S consta sólo de unas pocas regiones de valor constante que tengan figuras simples (i.e., que son uniones de unos pocos bloques sólo), su representación MAT será bastante compacta. Para una imagen n ´ n, harán falta 2log2 n bits para especificar las coordenadas de cada bloque centro y (log2 n) – 1 bits para especificar el radio; así si hay b bloques en el MAT, el número total de bits necesarios para especificarlo es b(3log2 n + log2 (m-1) – 1).
Fig. 2
Ejemplo simple de una representación MAT. (a) imagen binaria 8
´ 8, con los centros de los bloques MAT (de
1’s) subrayados. (b) Coordenadas de los centros y radios de los bloques MAT (la
esquina inferior izquierda tiene coordenadas (1,1)).
Nótese que la representación MAT puede incluso ser redundante, i.e., algunos bloques pueden estar contenidos en uniones de otros. No parece haber ninguna forma simple de reducir esta redundancia sin desarrollar un largo proceso de búsqueda.
b. Árboles de
cuadrados
Los bloques maximales pueden ser de cualquier tamaño y estar en cualquier posición; son análogos a las secuencias en el caso uni-dimensional. (Las regiones maximales conexas de valor constante son también análogas a las secuencias, pero no son buenos elementos originales para propósitos de representación, puesto que en sí mismos no pueden ser especificados de forma compacta; un bloque, por otra parte, se define especificando su centro y su radio.) Describiremos a continuación una representación bi-dimensional basada en árboles de grado 4; es análoga a la representación de árbol binario para las filas. Asumimos por simplicidad que el tamaño de la imagen S es 2k ´ 2k .
El nodo raíz del árbol representa la imagen completa. Si la imagen tiene un sólo valor, marcamos el nodo raíz con ese valor y paramos. En otro caso, añadimos cuatro descendientes al nodo raíz, representando los cuatro cuadrantes de la imagen. El proceso se repite entonces para cada uno de esos nuevos nodos; y así sucesivamente. En general, los nodos del nivel h (si hay alguno) representan bloques de tamaño 2k-h ´ 2k-h , en posiciones cuyas coordenadas son múltiplos de 2k-h . Si un bloque tiene valor constante, su nodo es un nodo hoja; en otro caso, su nodo tiene cuatro descendientes a nivel h + 1, correspondientes a los cuatro cuadrantes del bloque. Los nodos del nivel k, si hay alguno, son todos nodos hojas correspondientes a pixeles únicos.
Fig. 3
Árbol de cuadrados para la imagen de la Fig. 2. (a) Imagen, con los
bloques del árbol de cuadrados marcados. (b) Árbol; misma notación que la Fig.
1. Hay 41 nodos, 31 de los cuales son nodos hoja. El orden de los hijos de cada
fila es NO, NE, SO, SE.
El árbol construido de esta forma se denomina árbol de cuadrados, puesto que sus nodos que no son hojas tienen todos grado 4. Un ejemplo simple de una imagen y su correspondiente árbol de cuadrados se muestra en la Fig. 3. El espacio necesario para almacenar el árbol es proporcional al número de nodos, como en el caso uni-dimensional. Nótese que, a diferencia del MAT, la representación de árbol de cuadrados no es redundante.
La principal desventaja de la representación del árbol de cuadrados es que, a diferencia de la representación sin árbol aquí considerada, dos imágenes que difieran sólo en una translación pueden dar origen a árboles de cuadrados muy distintos. Así es difícil decir desde su representación de árbol de cuadrados si dos imágenes son congruentes.