Algoritmo Heurístico Morfológico para Extracción de Esqueletos en Imágenes en Tonos de Gris

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

87 ISBN: 978-968-9516-00-4

Algoritmo Heurístico Morfológico para Extracción de Esqueletos en Imágenes en Tonos de Gris

J. C. Salgado Ramírez, R. Rojas Hernández, A. Gamino Carranza, A. Ortiz Montes, V. Trujillo Mora

Abstract This article shows an algorithm which enable us to find the geometrical skeleton on gray levels images using the mathematical morphology. The heuristical algorithm maps the image in gray levels to binarial one, and with the Fast Distance Transformation, the skeleton is obtained. The suggested binarial method keeps the edges as well as other features, therefore the skeleton keeps the geometrical relationship with the image in gray tones after being extracted. Keywords: Fast Distance Transformation, Images in gray levels, mathematical morphology, skeleton.

Introducción El procesamiento digital de imágenes es una herramienta muy importante para el reconocimiento de patrones (RP) [2-3]; por ejemplo, un dilema al que algunos algoritmos de RP como las redes neuronales, las memorias asociativas y los clasificadores se enfrentan, hablando de imágenes, es saber qué información de ésta es necesaria para que sean robustos al aprender, recuperar y clasificar patrones [11-12]. El punto es, que encontrar la información que necesitan los algoritmos de RP para ser robustos no es una tarea trivial [46]. De aquí la importancia del procesamiento de imágenes. Un posible método para la extracción de información relevante es el adelgazamiento de imágenes [1][8] proporcionando rasgos que describan patrones a los algoritmos de RP. El algoritmo de adelgazamiento o también llamado esqueleto, proporciona información mínima de una imagen que normalmente guarda relación geométrica con la imagen original [7-8]. El algoritmo, que se propone, para encontrar esqueletos en tonos de gris se basa en el esqueleto morfológico para imágenes binarias; dos de las propiedades de este algoritmo de esqueletización son: 1) que la imagen binaria puede ser reconstruida a partir del esqueleto morfológico y 2) que el esqueleto guarda relación geométrica con la imagen original a pesar de que éste no es conexo [13]. Existen muchos métodos que generan el esqueleto morfológico de imágenes binarias [7][13][16] con características interesantes; otros más extraen esqueletos de imágenes en tonos de gris [17-21]. Hay además algoritmos iterativos de adelgazamiento en tonos de gris que lo generan [9]. A diferencia de los métodos de esqueletización anteriores, el método que proponemos encuentra el esqueleto no conexo de una imagen en tonos de gris a partir de una imagen binaria haciendo uso de la Transformada Rápida de Distancia y el esqueleto morfológico y se propone también un método de binarizado.

Gradiente Morfológico

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

88 ISBN: 978-968-9516-00-4

El gradiente morfológico se basa en las operaciones básicas de la morfología matemática, como lo son la dilatación y la erosión; al hacer la diferencia de la dilatación con la erosión en ese orden, se obtiene la extracción del contorno enfatizado de la imagen [13-14]. El gradiente morfológico se define como:

donde

y

es la erosión y se define como:

es la dilatación, definida como:

En las ecuaciones 2 y 3 se deduce que

es una función que representa a la imagen y

es el elemento de estructura. En la figura 1 se muestra la vecindad de Moore usada como elemento de estructura.

Figura 1. Elemento de estructura: Vecindad de Moore

Al aplicar a una imagen (figura 1) el gradiente morfológico obtiene el contorno enfatizado de la imagen original, como lo muestra la figura 2.

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

89 ISBN: 978-968-9516-00-4

Figura 2. Imagen original

Binarizado. El proceso de binarizado para encontrar el esqueleto consta de cuatro etapas:

Figura 2. Gradiente morfológico

1). Se binariza el gradiente morfológico en función de

donde U representa el umbral de binarizado 2). Se obtiene el negado de 4:

3). De se obtienen niveles de gris mayores a un umbral para ser considerados en el binarizado final, de la siguiente forma:

4). Finalmente el binarizado se obtiene considerando 5 y 6:

donde T es el umbral que se define a partir de qué tono de gris debe conservarse de la imagen original. Este algoritmo de binarizado garantiza que los bordes se conservarán, hecho necesario para que la Transformada Rápida de Distancia proporcione sentido geométrico en la imagen binaria con respecto a la imagen original.

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

90 ISBN: 978-968-9516-00-4

La figura 3, muestra el resultado del proceso de binarizado con U=31 y T=96.

Figura 3. Proceso de binarizado

Espacios métricos Definición 1. Sea X un conjunto. Una métrica en X, también llamada distancia, es una función que:

Entonces la dupla (X,d) es llamado espacio métrico. Si d es una métrica, X=Z y d es llamada métrica discreta.

Sean

1.

y

puntos sobre

, tal

entonces

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

91 ISBN: 978-968-9516-00-4

2. 3.

4. Las métricas listadas anteriormente, mostradas en la figura 4, son llamadas discos cerrados de radio 1. Estos discos corresponden a las k-vecindades, donde k {4,8, 6L, 6R} y las distancias que hacen uso de estas vecindades se expresan como d [13-15]. Estas k-vecindades son ampliamente usadas en el procesamiento digital de imágenes.

Figura 4. Métricas discretas de las k-vecindades

Transformada de Distancia Definición 2. El mapeo de la Transformada de Distancia (TD) es:

donde Distancia, la función

, F es una imagen binaria,

recibe el nombre de Transformada de

se llama Transformación de Distancia y R es la región de interés.

La definición 2 significa: Que para una región de interés R, donde R es un conjunto de puntos x tales que al aplicar a x la transformación de distancia , se obtiene como resultado un conjunto de duplas tal que . El resultado de esta transformación es una imagen en tonos de gris; cada valor de tono de gris representa la distancia numérica que tiene cada punto (pixel) con respecto a su complemento.

Transformada Rápida de Distancia

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

Definición 3. Si d es una de las métricas se tiene que:

92 ISBN: 978-968-9516-00-4

y

, para

1. 2.

De lo anterior, se desprende lo siguiente: Si se tiene la transformada de distancia de los vecinos de c se puede encontrar la transformación de distancia , donde:

Ahora, se tiene una transformada de distancia en 2 pasos:

1. Barrer la imagen binaria de arriba hacia abajo y de izquierda a derecha. Para cada pixel c R es la región de interés, se asigna:

R, donde

E es alguno de los siguientes conjuntos según la métrica a utilizar:

Figura 5. Conjunto E según la métrica

solo los puntos asignados en E son usados en la primera parte de la transformación. 2. Barrer la imagen binaria de abajo hacia arriba y de derecha a izquierda. Para cada pixel c R es la región de interés, se asigna:

R, donde

D es alguno de los siguientes conjuntos según la métrica a utilizar; solo los puntos asignados en D son usados para la segunda parte de la transformación:

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

93 ISBN: 978-968-9516-00-4

Figura 6. Conjunto D según la métrica

La transformada rápida de distancia tiene las siguientes ventajas:

1. TRD es mucho más rápida debido a que sólo requiere calcular mínimos en un conjunto de cardinalidad fija. 2. El tiempo de procesamiento es constante para cualquier imagen binaria.

La figura 7 muestra el resultado obtenido con la TRD de la figura 3.

Figura 7. Transformada Rápida de Distancia

Esqueleto Morfológico Definición 4. Dado un conjunto A, se llama segmentación al proceso de obtener uno o más segmentos de éste Definición 5. Dada una familia finita de transformaciones de conjuntos segmento de un conjunto A si y sólo si

, un conjunto B es

y existe una sucesión de transformaciones, miembros de F,

De lo anterior se desprende: La única diferencia entre el concepto de segmento de y el conjunto similar a, radica en que en el primero se exige que B sea un subconjunto de A; es decir, algunas transformaciones como la traslación son excluidas. Si la identidad de conjuntos es miembro de F, A puede ser segmento de sí mismo. El hecho de que B sea segmento de A no implica que se pueda obtener A a partir de B, a menos que las transformaciones involucradas sean invertibles todas en F, o que la transformación global sea invertible. Suponga que tiene una familia infinita de elementos estructurales de la siguiente forma:

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

Con conteniendo únicamente el origen del espacio de trabajo X; cumple con y para .

94 ISBN: 978-968-9516-00-4

, un elemento de estructura que

Tal construcción de H asegura que:

1. El origen se encuentra en todo miembro de la familia H 2.

para toda

Una vez construida H se puede dar una clasificación de las traslaciones de sus miembros en función de un conjunto A dado a continuación:

Definición 6. Sea H definida como en Definición 4 y sea , se dice maximal en A con centro en p si y sólo si

1. 2.

tales que

; la traslación de un miembro de H por

y

De esta manera, se separan las traslaciones de los miembros de la familia H en dos clases: maximales y no maximales. Por otro lado, el esqueleto morfológico de una región o conjunto A, se define directamente en función de erosiones y aperturas como sigue:

Definición 7. Sean A, B subconjuntos de X y sea la familia de elementos de estructura H como se definió en 4; el esqueleto morfológico de A, dado B, queda expresado por:

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

95 ISBN: 978-968-9516-00-4

Figura 8. Centros maximales

con

donde k es un número natural tal que

Obsérvese que la selección de es importante para el proceso de esqueletización, porque es probable que para algún dado no exista un k finito que cumpla . Dado este caso, se dice que el esqueleto bajo no existe; por otro lado, si además es simétrico, esto es , entonces el esqueleto morfológico recibe el nombre de transformada al eje medio. Cuando el esqueleto de un conjunto existe, resulta ser un subconjunto de este último; en la figura 8, se observa el esqueleto morfológico (color negro) obtenido, de una figura cualquiera, utilizando un elemento de estructura que se basa en la métrica .

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

96 ISBN: 978-968-9516-00-4

Figura 8. Esqueleto morfológico obtenido con un elemento de estructura con métrica

La Transformada Rápida de Distancia guarda relación estrecha con el esqueleto morfológico [13]. Para obtener el esqueleto morfológico a partir de la TRD, basta con encontrar los centros maximales contenidos en un elemento de estructura . El algoritmo para encontrar el esqueleto morfológico a través de la TRD es: 1. Se obtiene la TRD de la imagen binaria. Los valores de distancia mayores a 0 pertenecen al conjunto A y los valores de distancia en 0 son considerados como el complemento del conjunto A. 2. Hacer: Para y=1 hasta el alto de la imagen Para x=1 hasta el ancho de la imagen si para para si

entonces hasta hasta

Al aplicar el algoritmo anterior genera como resultado el esqueleto morfológico a partir de la TRD como se muestra la figura 9.

Figura 9. Esqueleto morfológico obtenido a partir de la TRD

Esqueleto morfológico de una imagen en tonos de gris. Para obtener el esqueleto morfológico de una imagen en tonos de gris se procede de la siguiente manera: 1. Aplicar el gradiente morfológico de la imagen en tonos de gris, obteniendo así el contorno enfatizado de la imagen. 2. Aplicar el proceso de binarizado descrito en la sección 3. 3. Obtener la TRD, descrita en la sección 6. 4. Obtener el esqueleto morfológico como se explicó en la sección 7.

En la figura 10, se observa el esqueleto morfológico de una imagen en tonos de gris. Se resalta en ésta que el esqueleto no es conexo, sin embargo guarda relación geométrica con los gradientes altamente contrastantes de la imagen original.

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

97 ISBN: 978-968-9516-00-4

Figura 10. Esqueleto morfológico de una imagen en tonos de gris

Conclusiones En este artículo se mostró cómo al combinar de forma inteligente herramientas para el procesamiento de imágenes, en específico de la morfología matemática, se obtuvo el esqueleto de una imagen en tonos de gris aunque se trabajo prácticamente en su representación binaria. Se destaca, además, que la Transformada Rápida de Distancia se relaciona de forma natural con la obtención del esqueleto. El método de binarizado que se presentó, conserva el contorno de la imagen en tonos de gris. Estos resultados pueden ser útiles, por ejemplo, a métodos de RP para obtener información de imágenes cuando se quiera aprender, recuperar y clasificar patrones.

Referencias [1] Shang, Lifeng; Yi, Zhang, “A class of binary images thinning using two PCNNs”, Neurocomputing, Jan 2007, Vol. 70 Issue 4-6, p1096-1101. *2+ Reddy L, Rama K., Babu, G. R., “Multiscale Feature And Single Neural Network Based Face Recognition”, Journal of Theoretical & Applied Information Technology, 2008, Vol. 4 Issue 7, p571-576. *3+ Jahan Z, Muhammad Y. J. and Usman Q., “Low Resolution Single Neural Network Based Face Recognition”. International Journal of Biomedical Sciences, 2007, Vol. 2 Issue 3, p206-210. [4] Ritter, G. X., Sussner, P. and Diaz-de-Leon, J. L., “Morphological Associative Memories”, IEEE Transactions on Neural Networks, 1998, pp. 281-293. [5] Ritter, G. X., Diaz-de-Leon, J. L. and Sussner, P., “Morphological bidirectional associative memories”, Neural Networks, 1999. pp. 851-867. *6+ Yáñez C. (2002). “Memorias Asociativas Basadas en Relaciones de Orden y Operadores Binarios”, Tesis doctoral, CIC-IPN, México. *7+ Zhang, S and Fu S. A, “A Thinning Algorithm for Discrete Binary Images”, Proceedings of the International Conference on Computers and Applications, Beijing China, 1984, pp 879-886.

Raíces para el futuro de las Tecnologías de la Información y Comunicaciones

98 ISBN: 978-968-9516-00-4

[8] Díaz de León, J. L. and Yañez, C, Introducción a la Morfología Matemática de Conjuntos, Fondo de cultura Económica, IPN, México D.F., 2003, pp 254-262 *9+ Wang Y. and Lee T., “Curve-skeleton extraction using iterative least squares optimization”, IEEE Transactions On Visualization And Computer Graphics [IEEE Trans Vis Comput Graph], ISSN: 1077-2626, 2008 Jul-Aug; Vol. 14 (4), pp. 926-36. *10+ Wong, W., Shih and F., Su, T., “Thinning algorithms based on quadtree and octree representations”, Information Sciences, May2006, Vol. 176 Issue 10, p1379-1394 [11] Sheng-fang H., Ruey-feng C., Woo K. M., Yu-hau L., Chen D. and Sun J., “Analysis of Tumor Vascularity Using Three-Dimensional Power Doppler Ultrasound Images”, IEEE Transactions on Medical Imaging, Mar2008, Vol. 27 Issue 3, p320-330. [12] Li, Z, Ferrer, M., Travieso, C. and Alonso, J., “Biometric based on ridges of palm skin over the head of the second metacarpal bone”, Electronics Letters, 3/30/2006, Vol. 42 Issue 7, p391-393 [13] Juárez-López. S, “Esqueletos morfológicos en el plano discreto”, 2004, Tesis de maestría, CINVESTAVIPN, México. [14] Gamino A., "Operaciones morfológicas por descomposición del elemento estructura mediante discos", 2004, Tesis de Maestría, CINVESTAV-IPN, México. [15] Diaz-de-Leon, J. L. (1996) “Combinación lineal de espacios Métricos en CINVESTAV-IPN, México.

”, 1996, Tesis de doctorado,

[16] Díaz-de-León J.L., “Algortimos de esqueletización de imágenes binarias”, 1993, Tesis de Maestría, CINVESTAV-IPN, México. *17+ Jianning Xu, “A Generalized Discrete Morphological Skeleton Transform With Multiple Structuring Elements for the Extraction of Structural Shape Components”, 2003,IEEE Transactions on Image Processing, vol. 12, 1677-1686. *18+ Abe, K., Mizutani, F. and Wang, C., “Thinning of grayscale images with combined sequential and parallel conditions for pixel removal”, Feb. 1994, IEEE Trans. on Systems Man Cybernetics, vol. 24, no. 2, pp. 294299, *19+ Arcelli, C. and Ramella, G.,”Finding grey-skeletons by iterated pixel removal”, Apr. 1995,Image and Vision Computing, vol. 13, no. 3, pp. 159-267. *20+ Dyer, C. R. and Rosenfeld, A., “Thinning algorithms for grayscale pictures”, Jan. 1979,IEEE Trans. Pattern Anal and Machine Intell., vol. 1, no. 1, pp. 88-90. *21+ Wang, L. and Pavlidis, T., “Direct gray-scale extraction of features for character recognition”, Oct. 1993, IEEE Trans. on Pattern Anal. And Machine Intell., vol. 15, no. 10, pp. 1053-1067.