Apuntes de Topología Digital: Representación

Introducción

La segmentación descompone una imagen en subconjuntos o regiones. Las propiedades geométricas de estos subconjuntos –conectividad, tamaño, forma, etc.- son frecuentemente importantes en la descripción de la imagen. Como veremos, hay muchos métodos de medir tales propiedades; habitualmente el método preferido depende de cómo se representan los subconjuntos. Este capítulo discute varios esquemas de representación y sus aplicaciones a la medida de la propiedad geométrica.

En estos apuntes, S representa una imagen; los subconjuntos de S se representan por S_i, T,... y los puntos por P, Q,...

En general, una imagen S segmentada se divide en una colección de subconjuntos no vacíos S₁,..., S_m  de tal forma que È^m_i=1 S_i = S y S_i Ç S_j = Æ para todo i ¹ j. Un caso especial importante es m = 2, i.e., S  consiste en un conjunto S y su complemento Š. En el caso general, podemos tomar cualquiera de los S_i como S, de tal forma que È^m_j=1,j¹iS_j = Š. Nótese que los conjuntos S no son necesariamente conexos.

1. Esquemas de representación

Cualquier subconjunto S de una imagen digital puede ser representado por una imagen binaria (o “bit plano”) c_s del mismo tamaño que S, teniendo 1’s en los puntos de S y 0’s en cualquier otro lugar. Si S es n´ n, la representación c_s requiere n² bits. c_s puede ser considerada como la función característica del subconjunto S; ésta es la función que hace corresponder los puntos de S con 1’s y los puntos de Š con 0’s.

De forma más general, cualquier partición de una imagen digital  en S₁,...,S_m puede ser representada por una imagen m-valuada teniendo i’s en los puntos de S_i, 1 £ i £ m. En concreto, si S es cualquier imagen, entonces en este sentido, S representa su propia partición en conjuntos de nivel gris constante, i.e., S_i es el conjunto de puntos de S que tienen nivel gris i. Para una imagen n ´ n, esta representación requiere n²log₂ m bits.

Las exigencias de almacenamiento de esta representación trivial son las mismas para todas las particiones de S en un número de conjuntos dado. Nuestro principal interés en este capítulo es estudiar las representaciones que son más económicas para las particiones “simples”. En las siguientes secciones definiremos varias de tales representaciones.

2. Conversión entre representaciones

Algunas de las conversiones entre una representación y otra son bastante sencillas. Por ejemplo, es obvio cómo convertir matrices a secuencias: rastrear la matriz fila a fila; incrementar un contador mientras el valor permanece constante; cuando el valor cambia, concatenar el valor (viejo) y la cuenta a la lista de la secuencia y resetear el contador. Recíprocamente, para convertir una secuencia a una tabla, creamos la matriz fila a fila, introduciendo el valor actual y decrementando la longitud de la secuencia actual hasta que alcance el cero, punto en el que cambiaremos al siguiente valor y longitud de la lista de secuencias.

En esta sección damos algoritmos de conversión que implican bloques (MAT, árbol de cuadrados) y representaciones de bordes. También describimos algoritmos para el adelgazamiento de líneas en arcos y curvas. Como antes, normalmente trataremos sólo con el caso donde la imagen dada S esta dividida en un conjunto S y su complemento.

Por convención, los algoritmos descritos aquí serían implementados en un   ordenador digital ordinario (monoprocesador), que procesaría la imagen dada fila a fila. Por otro lado, algunos de los algoritmos son muy adecuados para su implementación en un multiprocesador, en el que un procesador es asignado a cada pixel, de forma que las operaciones locales pueden ser realizadas a todos los pixeles simultáneamente. Actualmente ya existen o están siendo construidos ordenadores multiprocesadores de un tamaño razonable (100 por 100 procesadores o más), y se espera que puedan jugar un papel fundamental en el procesamiento de imágenes en los próximos años.

3. Medidas de propiedad geométrica

En esta sección describimos cómo medir las propiedades geométricas de  relaciones entre subconjuntos de una imagen digital, usando las representaciones introducidas anteriormente. Además discutiremos métodos de obtener nuevas segmentaciones de uno dada, basados en propiedades o relaciones geométricas. las conversiones entre una representación y otra son bastante sencillas. 

Notas bibliográficas

Sólo se mencionan aquí unas pocas referencias generales. Referencias seleccionadas sobre métodos particulares se dan en el texto; no se ha intentado dar una bibliografía completa.

La representación MAT es debida a Blum [6]: sobre su teoría en el caso digital ver Rosenfeld y Pfaltz [58] y Mott-Smith [40]. La representación del árbol de cuadrados fue introducida por Klinger [30, 31]; los detalles de los algoritmos para convertir entre árboles de cuadrados y otras representaciones, y para el cálculo de propiedades geométricas a partir de árboles de cuadrados, puede encontrarse en una serie de artículos de Samet et al. [14, 16, 63-68, 72] (ver también Alexandridirs y Klinger [2] y Hunter y Steiglitz [27,28]). Los códigos de cadena y sus generalizaciones han sido estudiadas extensamente por Freeman, el cual las revisa en [19]. Sobre la representación de los bordes mediante secuencias de arcos circulares definidos por sucesivas tripletas de puntos de bordes ver Shapiro y Lipkin [71].

La teoría de conectividad digitales fue desarrollada por Rosenfeld, y se revisa en [55]. Sobre la teoría de la distancia digital ver Rosenfeld y Pfaltz [59]; sobre los primeros trabajos utilizando encogimiento y expansión para el análisis de las formas ver Moore [39].

La convexidad digital ha sido extensamente estudiada por Sklansky (e.g., [73]; ver también [74] en una aproximación paralela para rellenar concavidades añadiendo iterativamente “puntos cóncavos” a S). Otra aproximación para la construcción de envolvente convexa basada en una sucesión de polígonos inscritos se describe en [21]. Muchos algoritmos rápidos han sido propuestos para resolver varios problemas geométricos que relacionados con intersecciones (e.g., construyendo la envolvente convexa de un conjunto de puntos intersectando un conjunto de medios-planos) y distancias (e.g., encontrando parejas de puntos que son los vecinos más cercanos).

Técnicas sobre el análisis de formas son revisadas por Pavlidis [47, 48]; para una revisión extensa de la percepción de la forma ver Zusne [78].

D. Proffitt and D. Rosen, Metrication errors and coding efficiency oF chain-encoding schemes for the representation of lines and coges, Comput Graphics Image Processing 10, 1979, 318-332.  

C. V. Kameswara Rao, B. Prasada, and K. R. Sarma, A parallel shrinking algorithm for binary patterns, Comput. Graphics Image Processing 5, 1976, 261-270.  

A. Rosenfeld, Compact figures in digital pictures, IEEE Trans. Syst. Man Cybernet 4, 1974, 211-223.  

A. Rosenfeld, Digital straight line segments, IEEE Trans. Comput 23. 1974 1264 1269  

A. Rosenfeld, A characterization of parallel thinning algorithms, lnformat. Control 29, 1975, 286-291.  

A. Rosenfeld, "Picture Languages : Format Models for Picture Recognition," Chapter 2. Academic Press, New York, 1979.  

A. Rosenfeld and L. S. Davis.A note on thinning, IEEE Trans. Systems Man Cybernet 6, 1976, 226-228.  

A. Rosenfeld and E. Johnston, Angle detection on digital curves, IEEE Trans. Comput. 22. 1973, 875-878.  

A. Rosenfeld and J. L. Pfaltz, Sequential operations in digital picture processing, J. ACM 13, 1966, 471-494.  

A. Rosenfeld and J. L. Pfaltz. Distance functions on digital pictures, Pattern Recognition 1, 1968, 33-61.  

A. Rosenfeld and J. Weszka. An improved method of angle detection on digital curves, IEEE Trans. Comput, 24, l975, 940-941.  

D. Rutovitz, Data structures for operations on digital images, in "Pictorial Pattern  Recognition" (G. C. Cheng et al., eds.), pp. 105-133 Thompson, Washington, D.C., 1968.  

D. Rutovitz, An algorithm for in-line generation of a convex cover, Comput. Graphics Image Processing 4, l975, 74-78.  

H. Samet, Region representation: quadtree-to-raster conversion, Computer Science Center TR-768, Univ. of Maryland, College Park, Maryland, June 1979.  

H. Samet, Region representation quadtrees from boundary codes, Comm. ACM 23, 1980, 163-170.  

H. Samet, Region representation quadtrees from binary arrays, Comput. Graphics lmage Processing l3, l980, 88-93.  

H. Samet, Connected component labelling using quadtrees, J. ACM 28, 1981,487-501.  

H. Samet, An algorithm for converting rasters to quadtrees, IEEE Trans. Pattern Anal. Machine Intelligence 3, 1981, 93-95.  

H. Samet, Computing perimeters of images represented by quadtrees, IEEE Trans. Pattern Anal Machine lntelligence, 3, 1981, 683-687.  

P. Y. Sankar and E. V. Krishnamurthy, On the compactness of subsets of digital pictures, Comput. Graphics Image Processing 8, 1978, 136-143.  

J. Serra, Theoretical basis of the Leitz texture analysis system, Leitz Sci. Tech. Informat. Suppl. 1 (4), 1974, l25-136.  

B. Shapiro and L. Lipkio, The circle transform, an articulable shape descriptor, Comput. Biomed. Res. 10, 1977, 511-528.  

M. Shneier.Calculations af geometrie properties using quadtrees, Comput. Graphics ImageProccesing 16, 1981, 296-302.  

J. Sklansky, Recognition of convex blobs, Pattern Recognition 2, 1970, 3-10.  

J. Sklansky, L. P. Cordella, and S. Levialdi, Parallel detection of concavities in cellularblobs, IEEE Trans. Comput. 25, 1976, 187-196.

J. P. Strong III and A. Rosenfeld, A region coloring technique for scene analysis, Comm. ACM 16, 1973, 237-246.  

P. H. Winston, Learning structural descriptions from examples,in "The Psychology ofComputer Vision" (P. H. Winston.ed), pp. 157-209. McGraw-Hill, New York, 1975.  

 I. T. Young, J. E. Walker, and J. E. Bowie, An analysis technique for biological shape,Informat. Control 25, 1974, 357-370.