Operaciones morfológicas rápidas por descomposición del elemento de estructura mediante discos

CENTRO DE INVESTIGACIÓN Y DE ESTUDIOS AVANZADOS DEL INSTITUTO POLITÉCNICO NACIONAL

UNIDAD ZACATENCO DEPARTAMENTO DE CONTROL AUTOMÁTICO

Operaciones morfológicas rápidas por descomposición del elemento de estructura mediante discos Tesis que presenta

Ing. Arturo Gamino Carranza Para Obtener el Grado de

Maestro en Ciencias En la Especialidad de

Control Automático Dirección de la Tesis:

Dr. Juan Luis Díaz de León Santiago (CIC-IPN) Dra. Petra Wiederhold Grauert (CINVESTAV-IPN)

México, D.F.

Diciembre, 2004

Dedicatoria El presente fruto de mi esfuerzo lo dedico con cariño para: Dios: Por darme la oportunidad de vivir, de brindarme unos excelentes padres y por nunca dejarme en los momentos difíciles de la vida. Mis padres: Flora Carranza Guatemala. Artemio Gamino Aguilar. Por brindarme una maravillosa familia, y porque sin su esfuerzo, dedicación y amor hacia mi; no sería nadie en la vida. Mi hermano: David Gamino Carranza. Por compartir invaluables momentos de su vida junto a mi y por querernos como nos queremos.

i

Agradecimientos Agradezco sinceramente a mi asesor Dr. Juan Luis Díaz de León Santiago, por haber confiado en mi, por brindarme su apoyo y dirigir este trabajo de tesis como lo hizo. Así como mi asesora Dra. Petra Wiederhold Grauert por sus acertados comentarios y sugerencias, para la realización de esta tesis. También extiendo mi agradecimiento a los miembros del jurado de mi tesis: Dr. Alejandro Malo Tamayo. Dr. Gabriel Villa Salvador. por sus atinados comentarios para la elaboración de esta tesis. A mis amigos y compañeros de maestría: Salvador Juárez. Israel Álvarez. Miguel Alvarado. Eduardo Velázquez. Isaac Chairez. por haberme brindado su invaluable ayuda, en momentos difíciles de mi vida. Así como también mis compañeros de trabajo y estudio, por los gratos momentos. En especial quiero agradecer a Ángel Martínez, Carlos García, Carlos Rito, Raúl Cruz, Valentín Trujillo, por haberme apoyado durante la maestría y por su grata amistad que nos une; además a mis profesores, por haberme brindado una buena formación académica. A la c. Lucero Fernández Campos por su estupendo apoyo secretarial, al c. Carlos Guerrero Rojo por su apoyo técnico y a la c. Sonia Araceli Alfaro Llamas por mostrarme un aspecto más de la condición humana. Finalmente agradezco al CINVESTAV, CONACYT y TELMEX por su apoyo económico y moral para la realización de mis estudios de posgrado.

ii

Índice general 1. Introducción 1.1. Motivación . . . 1.2. Antecedentes . 1.3. Formulación del 1.4. Contribuciones

. . . . . . . . . . . . problema. . . . . . .

. . . .

. . . .

. . . .

. . . .

2. Marco Teórico 2.1. Dilatación . . . . . . . . . . . . . 2.2. Erosión. . . . . . . . . . . . . . . 2.3. Dualidad erosión-dilatación. . . . 2.4. Apertura y cerradura. . . . . . . 2.5. Esqueleto morfológico. . . . . . . 2.6. Espacios métricos. . . . . . . . . 2.7. Transformada de distancia . . . . 2.8. Transformada rápida de distancia

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

1 2 3 4 5

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

7 10 12 15 15 17 20 23 23

3. Estado del arte 3.1. Descomposición del elemento de estructura. . . 3.2. Procesamiento de contorno . . . . . . . . . . . . 3.3. Uso de la transformada de distancia. . . . . . . 3.4. Uso de la transformada de distancia Euclideana. 3.5. Método Talbot-Van Droogenbroeck. . . . . . . . 3.5.1. Descripción del algoritmo. . . . . . . . . 3.5.2. Complejidad del algoritmo. . . . . . . . . 3.5.3. Implementación del algoritmo . . . . . . 3.5.4. Discusión y resultados. . . . . . . . . . . 3.6. Método “2-D scan” . . . . . . . . . . . . . . . . 3.6.1. Algoritmo basado en un barrido 2D . . . 3.6.2. Implementaciones a la salida . . . . . . . 3.6.3. Resultados. . . . . . . . . . . . . . . . . 3.7. Método Díaz. . . . . . . . . . . . . . . . . . . . 3.7.1. Descripción del algoritmo . . . . . . . . 3.7.2. Discusión. . . . . . . . . . . . . . . . . . 3.8. Análisis del estado del arte . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

25 25 27 28 28 30 30 31 33 34 34 35 37 37 38 38 39 39

. . . . . . . .

. . . . . . . .

iii

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

4. Descomposición del elemento de estructura en discos.

41

5. Discusiones experimentales

53

6. Conclusiones y trabajo a futuro

61

Bibliografía

63

iv

Índice de figuras 2.1. Reflexión del conjunto A. . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Traslación del conjunto A por x = (4, 3). . . . . . . . . . . . . . . . . 2.3. Complemento del conjunto A. . . . . . . . . . . . . . . . . . . . . . . 2.4. Suma de Minkowski del conjunto A por el elemento de estructura B. 2.5. Sustracción del conjunto A − B, B − A. . . . . . . . . . . . . . . . . . 2.6. Erosión del conjunto A por el elemento de estructura B. . . . . . . . 2.7. La erosión no es conmutativa. . . . . . . . . . . . . . . . . . . . . . . 2.8. Interpretación geométrica de la apertura. . . . . . . . . . . . . . . . . 2.9. Interpretación geométrica de la cerradura. . . . . . . . . . . . . . . . 2.10. Centros maximales de B0 y B1 en el conjunto A. . . . . . . . . . . . . 2.11. Bolas de radio unitario para métricas discretas. . . . . . . . . . . . . 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.7.

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

Ejemplos de descomposición del elemento de estructura en subconjuntos propios. Error de la transformada de distancia quasi Euclideana. . . . . . . . . . . . . Traslación de B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Histograma local para una traslación de B. . . . . . . . . . . . . . . . . . . . Barrido de la imagen según su forma. . . . . . . . . . . . . . . . . . . . . . . Barridos horizontal y vertical de la imagen original. . . . . . . . . . . . . . . Resultado de la apertura. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1. Imagen A. . . . . . . . 5.2. Imagen B. . . . . . . . 5.3. Imagen C. . . . . . . . 5.4. Imagen D. . . . . . . . 5.5. Imagen E. . . . . . . . 5.6. Imagen F. . . . . . . . 5.7. Imagen G. . . . . . . . 5.8. Imagen H. . . . . . . . 5.9. Imagen I. . . . . . . . 5.10. Dilatación de A con G. 5.11. Dilatación de I con E. 5.12. Dilatación de B con F. 5.13. Dilatación de C con H. 5.14. Dilatación de D con D.

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

v

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

8 8 9 9 10 13 13 16 17 18 21 26 29 31 32 33 36 36 54 54 54 54 55 55 55 55 56 57 57 58 58 59

Lista de símbolos Lógica ∀ ∃ @ ∨ ∧ −→ ←→

cuantificador universal (para todo...). cuantificador existencial (existe...). cuantificador existencial negado (no existe...). disyunción (o). conjunción (y). condicional (si...entonces). bicondicional (si y sólo si).

Conjuntos A, B, C... a, b, c, ..., x, y, z {, } | {|} ∈ ∈ / |A| Z Z+ R R+ N = Z+ ∪ {0} {ai } ∅ ⊆ ⊂ U ∪ ∩ A−B Ac A− {Xi }i∈∆

letras mayúsculas representan conjuntos letras minúsculas representan elementos descripción de un conjunto por extensión tal que...(o tales que...) descripción de un conjunto por especificación pertenencia no pertenencia cardinalidad del conjunto A conjunto de los números enteros conjunto de los números enteros positivos conjunto de los números reales conjunto de los números reales positivos conjunto de los números naturales sucesión entera conjunto vacío subconjunto subconjunto propio conjunto universo unión intersección diferencia de conjuntos complemento de un conjunto reflexión de un conjunto (o conjunto reflejado) familia de conjuntos

Morfología Matemática ⊕ (A)x ª ◦ • S(A)

suma de Minkowski (dilatación) traslación de A por x resta de Minkowski (erosión) apertura cerradura esqueleto morfológico de A vii

Transformación de distancia N(x) = {p ∈ Z2 |d(x, p) = 1} δ(x) V min(), W max(), Di ® o(f (x))

vecindad centrada en x función de transformación de distancia de x mínimo máximo disco de radio i origen orden de una función f (x)

viii

Capítulo 1 Introducción La morfología matemática es un área reciente que ha mostrado ser un marco de trabajo que se utiliza con enorme éxito en el procesamiento digital de imágenes binarias. Este marco de trabajo está basado en la teoría de conjuntos. La dilatación y la erosión son los dos operadores básicos de la morfología matemática; a partir de ellos, se pueden formar más operadores que se utilizan para el procesamiento digital de imágenes, todos estos operadores usan un conjunto de píxeles llamado elemento de estructura. En este trabajo se presenta la base teórica para la construcción de operaciones morfológicas rápidas con elementos de estructura arbitrarios (representados por un conjunto B), dentro de una familia de 4 espacios métricos. Se entiende por elemento de estructura arbitrario un arreglo finito de píxeles que forman un conjunto no vacío (ver Capítulo 2). La base teórica desarrollada en esta tesis, resalta propiedades de algunos espacios métricos; además se introducen conceptos como esqueleto morfológico usando la transformada rápida de distancia. Los resultados desarrollados aquí, son generales en el sentido de que engloban métricas comúnmente utilizadas, tales como las métricas d4 , d8 , d6L y d6R . El objetivo principal de este trabajo es conocer el estado del arte de los métodos más utilizados para realizar operaciones morfológicas rápidas, debido a que a partir de éstas se pueden obtener métodos y algoritmos para el procesamiento de imágenes, por ejemplo filtrado, segmentación, entre otras; además se realizará un estudio minucioso y se propondrán nuevas formulaciones acerca de los algoritmos más importantes para realizar operaciones morfológicas rápidas, que se basan en los siguientes enfoques: 1. Descomposición del elemento de estructura. 2. Técnicas basada en una transformación de distancia. En el desarrollo del trabajo se tratará de obtener una metodología mixta, que aproveche las ventajas de ambos enfoques y que permita realizar operaciones morfológicas rápidas con elementos de estructura arbitrarios; en especial esta descomposición se realizará a través del esqueleto morfológico usando la transformada de distancia, tópicos que serán tratados más adelante.

1

La organización del trabajo es la siguiente: en el Capítulo 2 se introducen conceptos clásicos de morfología matemática, espacios métricos y transformada distancia. En el Capítulo 3 se presenta un análisis de los métodos convencionales más utilizados. En el Capítulo 4 se dan generalizaciones y nuevos resultados relacionados con transformada rápida de distancia y esqueleto morfológico, los cuales son utilizados para realizar operaciones morfológicas rápidas con elementos de estructura arbitrarios. En el Capítulo 5 se presentan los resultados experimentales y finalmente el trabajo futuro y las conclusiones se presentan en el Capítulo 6.

1.1.

Motivación

La morfología matemática es una teoría concebida para el análisis de la forma de objetos y funciones ([33]). Usualmente los operadores morfológicos están formados de 2 partes: (a) una forma de referencia, llamada elemento de estructura el cual es comparado con la forma original y (b) un mecanismo que detalla como debe de ser la comparación. Debido a lo anterior la morfología matemática es una excelente herramienta para representar y describir la forma de una región de interés como esqueletos y contornos. En la actualidad la morfología matemática con sus operaciones no lineales se ha convertido en un área muy popular, esto debido a que se pueden generar herramientas poderosas que hacen de la morfología un área competitiva en comparación con otras operaciones lineales. Parte de este suceso es el hecho de mejorar la eficiencia de varios algoritmos empleados dentro de la morfología matemática, lo que hoy en día es una línea abierta de investigación. De los diversos investigadores dedicados a la morfología matemática, la mayoría que mejora la eficiencia de las operaciones morfológicas, fundamentan sus algoritmos en la descomposición y/o codificación del elemento de estructura o utilizan alguna transformación, en especial una transformación de distancia. Es por ello que muchos de estos algoritmos tienen complejidad polinomial, cuadrática, logarítmica y, en el mejor de los casos, lineal respecto al número de píxeles del contorno del elemento de estructura. Estos investigadores utilizan como elemento de estructura vecindades especiales, estas vecindades son derivadas de las métricas d4 , d8 , d6R , d6L ; a pesar de esto existe un número reducido de investigadores que utilizan la transformada rápida de distancia, la cual proporciona algoritmos de tiempo constante para realizar operaciones morfológicas para dichas vecindades. De la discusión anterior, es claro que, para realizar operaciones morfológicas cuando el elemento de estructura es arbitrario (y no las vecindades), donde su principal característica sea el menor tiempo de procesamiento posible, existe un número limitado de trabajos; además recordemos que el éxito de la morfología sobre las técnicas convencionales (por ejemplo Fourier) se basa en una característica relevante, que es: la forma del elemento de estructura. Es por ello que el presente trabajo pretende estar en la frontera del estado del arte de la morfología matemática, contribuyendo con algoritmos de tiempo mínimo para operaciones morfológicas usando elementos de estructura arbitrarios, donde dicho elemento es descompuesto a través del esqueleto morfológico tal y como se mencionó anteriormente.

2

1.2.

Antecedentes

Las técnicas de procesamiento digital de imágenes han cambiado significativamente desde el siglo pasado. Estos cambios han sido motivados por una gran diversidad de problemas en el análisis, descripción y representación de imágenes. Las herramientas más utilizadas para resolver problemas en el procesamiento de imágenes han sido: filtrado lineal y no lineal, análisis de Fourier, entre otras. Por otro lado, en forma simultánea pero independiente se desarrolló la morfología matemática como método para el análisis de imágenes binarias, que se basa exclusivamente en la teoría de conjuntos. Las bases teóricas de esta disciplina se deben al científico alemán nacido en Rusia, Herman Minkowski (1864-1909), la suma de Minkowski apareció por primera vez en 1903 ([24]), la resta de Minkowski que es la operación dual de la suma de Minkowski fue propuesta por Hadwiger en 1957 ([17]). Basado en las ideas fundamentales de Minkowski y Hadwiger, George Matheron inicia la morfología matemática en 1964 con su trabajo de investigación en análisis de imágenes en el ámbito de medios porosos ([22]), posteriormente en 1982 Jean Serra dio un impulso más a la morfología matemática con la publicación de su libro ([33]), y sus avances ([34]) en 1988. A partir de aquí se han sumado otros investigadores a nivel mundial, entre los que han destacado: Haralick, Stenberg, Heijmans, Dougherty, Maragos, Pitas y Díaz de León. Los dos operadores básicos dentro de la morfología matemática son la dilatación y la erosión ([33], [34], [23]). A partir de éstos, se han desarrollado muchos filtros no lineales (otros operadores morfológicos), usualmente de complejidad polinomial. Esto último se debe a que las operaciones dependen fuertemente de la definición de una clase de conjuntos llamados elementos de estructura. La mayoría de los esfuerzos encaminados a mejorar la velocidad de los algoritmos, se basan en la descomposición y/o codificación eficiente del elemento de estructura ([35], [11], [12], [37]). Una transformación relacionada con la morfología matemática es conocida como transformación de distancia donde algunos resultados importantes han sido desarrollados por Rosenfeld ([31]), Pfaltz ([31]) y Borgefors ([1]), quienes presentan para vecindades particulares, algoritmos mejorados para el cálculo de transformaciones de distancia. De estas ideas, Nacken ([25]) construyó algoritmos eficientes dentro de la morfología matemática, para una métrica en particular (chamfer (5,7)). Por otro lado, recientemente, O Cuisenaire, B. Macq, M. Van Droogenbroeck han construído algoritmos eficientes para imágenes binarias ([11], [3]). Pero todos estos trabajos han sido mejorados por J. L. Díaz de León ([6]) por algoritmos de tiempo constante usando la transformada rápida de distancia. La mayoría de los investigadores que han trabajado sobre la transformada de distancia como herramienta para realizar operaciones morfológicas, y en la descomposición del elemento de estructura para realizar estas operaciones también, basan sus resultados en las métricas d4 y d8 ; pero es bien sabido que los operadores morfológicos dependen fuertemente de un elemento de estructura, el cual puede ser de forma arbitraria (incluyendo las vecindades derivadas de las métricas d4 y d8 ). La transformada de distancia y el elemento de estructura son tópicos de importancia en este trabajo, de manera que serán recapitulados más adelante con miras a utilizarlo dentro de la morfología matemática.

3

1.3.

Formulación del problema.

De la discusión anterior se concluye que cualquier operación morfológica depende fuertemente de un elemento de estructura B, el cual puede ser arbitrario, es decir, puede ser cualquier forma. Es también sabido que cualquier operación morfológica se puede hacer bajo dos enfoques: 1. Descomposición del elemento de estructura. 2. Técnicas basadas en una transformación de distancia. De manera que se tiene los siguientes problemas: i) Cuando se utilizan los métodos de 1) se debe encontrar una manera eficiente de descomponer el elemento de estructura; esta clase de operación morfológica con respecto a Bn se reduce n operaciones con respecto a B1 , cuando el elemento de estructura es posible descomponerlo como dilataciones sucesivas, lo cual muchas veces está limitado a ciertos elementos de forma conocida (ver Sección 3.1). Cuando el elemento de estructura no es posible descomponerlo de esa forma la velocidad de los algoritmos es aumentada considerablemente, y en la mayoría de los casos la fuerza bruta se hace necesaria, i.e. las operaciones de conjuntos de Minkowski se deben realizar completamente. Por otro lado, existe otra variante de descomposición, la cual utiliza el contorno del objeto (región de interés representada por el conjunto A, ver Sección 3.2), no obstante, de que ésta metodología puede ser utilizada para cualquier elemento de estructura, proporciona una complejidad lineal respecto al número de píxeles del contorno del conjunto A más un término cuadrático que se utiliza para encontrar dicho contorno, con lo que se siguen teniendo algoritmos de complejidad cuadrática, posteriormente se propuso la misma idea aplicándola a ambos conjuntos, i.e., encontrar el contorno del conjunto A y el contorno del conjunto B (elemento de estructura). Para todas estas metodologías la velocidad sigue siendo una característica que se desea mejorar. ii) Para 2) el uso de la transformada de distancia muchas veces no es una manera eficiente de realizar operaciones morfológicas, dada la naturaleza de su definición, la complejidad de esta metodología es cuadrática (ver Sección 3.3). Aunque existen variantes de ésta transformación, como es el caso de la transformada de distancia Euclideana, donde su complejidad es usualmente cúbica (ver Sección 3.4); en ambos casos la velocidad es mayor o igual que los métodos utilizados en 1). Por otro lado, existe la manera de reducir la complejidad y la velocidad de la transformada de distancia; esto gracias al uso de la transformada rápida de distancia, con lo cual los algoritmos son de complejidad constante, es decir, de tiempo constante (ver Secciones 3.6 y 3.7). Pero estos métodos se encuentran particularizados para elementos de estructura de cierta forma: vecindades de radio i ó elementos rectangulares (entiéndase por vecindades de radio i aquellos elementos de estructura que se construyen como dilataciones sucesivas de B1 , por ejemplo, B1 es derivado de las métricas d4 , d6R , d6L y d8 ). Por otro lado no existe un método generalizado para realizar operaciones morfológicas con elementos de estructura arbitrarios, que proporcionen algoritmos de complejidad lineal y que 4

su característica principal sea el menor tiempo de procesamiento posible. Es por ello que se propone el uso de la transformada rápida de distancia para obtener el esqueleto morfológico (ver Capítulo 4), él cual proporciona la reconstrucción exacta de cualquier elemento de estructura utilizado, es decir, a partir del esqueleto morfológico del elemento de estructura B, se puede obtener dicho elemento; además como se verá en la Sección 3.7 el uso del método Díaz proporciona algoritmos de complejidad constante, es decir, de tiempo constante para las vecindades derivadas de las métricas d4 , d6R , d6L y d8 . Combinando ambos métodos se puede generalizar un algoritmo que realice operaciones morfológicas de complejidad lineal y tiempo mínimo con elementos de estructura arbitrarios, donde su eficiencia será más notoria cuando el número de píxeles del elemento de estructura sea muy grande.

1.4.

Contribuciones

En este trabajo, se propone el uso del esqueleto morfológico visto desde un nuevo enfoque, que es el de la transformada rápida de distancia y utilizando sus propiedades se puede obtener una descomposición eficiente del elemento de estructura; lo anterior permitirá generalizar una operación morfológica rápida con un elemento de estructura arbitrario, como consecuencia de ello se mejorará sensiblemente la velocidad de los algoritmos con respecto a los algoritmos existentes discutidos en el Capítulo 3.

5

Capítulo 2 Marco Teórico La morfología matemática es una excelente herramienta para extraer componentes de un objeto de interés, útiles para representar y describir la forma de una región, tales como fronteras y esqueletos. La morfología matemática se ha utilizado con gran éxito en el procesamiento de imágenes y el lenguaje utilizado es la teoría de conjuntos, dado que una imagen se representa por medio de un conjunto. En su forma actual la morfología matemática no termina en el procesamiento de imágenes o señales, y dado que su única premisa de trabajo es la de utilizar el álgebra de conjuntos y sus propiedades, es de utilidad para cualquier clase de problema que se modele por medio de conjunto y donde la “forma” sea la característica más relevante. Todos los resultados que se presentan en este capítulo y en los próximos son válidos para X = Z2 , es decir, para una región de interés A ⊆ Z2 con A finito y no vacío, el conjunto A relacionado con la región en cuestión es el conjunto de puntos (x, y) ∈ Z2 tales que dicho píxel sea negro (por convención). Nótese que como X = Z2 , el operador + cumple que: es cerrado sobre X, es conmutativo, es asociativo, existe un elemento neutro, existe su inverso aditivo. De aquí en adelante cualquier subconjunto será no vacío y finito, además cuando se diga que B es un elemento de estructura arbitrario, se entiende que también es finito, no vacío y que es diferente a un disco usando las métricas d4 , d6R , d6L y d8 . Las operaciones morfológicas quedan definidas completamente por la adición de conjuntos de Minkowski. Algunas operaciones de conjuntos básicas ([33], [23], [10]) son las siguientes: Definición 1 La reflexión de A ⊆ X (o conjunto reflejado de A), cuya notación es A− , se define como el conjunto formado por los inversos aditivos de los elementos de A. Es decir: A− = {−x|x ∈ A}. Ejemplo 1 La reflexión del conjunto A = {(1, 1), (2, 1), (3, 1), (4, 1), (2, 2), (3, 2)} es: A− = {(−1, −1), (−2, −1), (−3, −1), (−4, −1), (−2, −2), (−3, −2)},ver Figura 2.1. De aquí en adelante en las figuras mencionadas como referencias la cruz dentro de un píxel indica el origen.

7

Figura 2.1: Reflexión del conjunto A. Definición 2 La traslación de A ⊆ X por un elemento x se denota por (A)x y se define así: (A)x = {a + x|a ∈ A}. Ejemplo 2 La traslación del conjunto A = {(−1, 0), (−1, −1), (0, 0), (0, −1), (0, −2), (−1, −3)} por x = (4, 3) es: (A)(4,3) = {(3, 3), (3, 2), (4, 3), (4, 2), (4, 1), (3, 0)}; esto se muestra en la Figura 2.2.

Figura 2.2: Traslación del conjunto A por x = (4, 3). Definición 3 El complemento de un conjunto A ⊆ X respecto a X (conjunto universo) o simplemente complemento, denotado por Ac , se define como el conjunto formado por aquellos elementos de X que no pertenecen a A, / A}. Ac = {x ∈ X|x ∈ Ejemplo 3 En la Figura 2.3 se representa un conjunto A y su complemento Ac .

8

Figura 2.3: Complemento del conjunto A. Definición 4 La suma de Minkowski de A ⊆ X y B ⊆ X, denotada por A ⊕ B es el conjunto que resulta de sumar cada elemento de A con cada elemento de B. Es decir: A ⊕ B = {a + b|a ∈ A ∧ b ∈ B}. A la suma de Minkowski también se le conoce como la dilatación de un conjunto A por un conjunto B. Ejemplo 4 Sea A = {(−1, −1), (−1, 0), (−1, 1), (0, −1), (0, 0), (0, 1), (1, −1), (1, 0), (1, 1)} y B = {(0, 0), (1, 0), (2, 0)}, entonces la suma de A y B es: A⊕B = {(−1, −1), (−1, 0), (−1, 1), (0, −1), (0, 0), (0, 1), (1, −1), (1, 0), (1, 1)(2, −1), (2, 0), (2, 1), (3, −1), (3, 0), (3, 1)}. La Figura 2.4 representa el conjunto A, el conjunto B y la suma A ⊕ B.

Figura 2.4: Suma de Minkowski del conjunto A por el elemento de estructura B. Definición 5 La diferencia de conjuntos de A ⊆ X y B ⊆ X, representada como A − B, se define como el conjunto formado por aquellos elementos de A que no pertenecen a B: A − B = {x ∈ A|x ∈ / B}. 9

Ejemplo 5 En la Figura 2.5 se representa el diagrama de Venn de A−B, para dos conjuntos diferentes A y B cualesquiera, dado un conjunto universo X. En general se tiene (A − B) ∩ (B − A) = ∅.

Figura 2.5: Sustracción del conjunto A − B, B − A.

2.1.

Dilatación

La dilatación, primera de las dos operaciones básicas de la morfología matemática queda completamente sustentada por la definición de la suma de Minkowski (Definición 4), mientras que la resta de Minkowski (Definición 6) tendrá relevante importancia en la definición inicial de erosión (ver Sección 2.2). En esta sección se presenta la dilatación desde dos enfoques distintos pero equivalentes; además se mostrarán las propiedades de la dilatación para concluir. Todos las demostraciones empleadas en los teoremas de este capítulo fueron tomadas de ([10]), a menos que se especifique lo contrario. La dilatación de un conjunto A por un conjunto B es la suma de Minkowski dada en la Definición 4. La Figura 2.4 muestra un ejemplo de dilatación entre un conjunto A y un conjunto B, al conjunto B se le conoce indistintamente con el nombre de elemento estructurante o elemento de estructura. Teorema 1 La dilatación es conmutativa. Sean A ⊆ X y B ⊆ X, entonces: A ⊕ B = B ⊕ A. Demostración A⊕B = {x = a+b|a ∈ A∧b ∈ B} = {x = b+a|b ∈ B ∧a ∈ A} = B ⊕A. El teorema anterior muestra que el proceso de dilatar un conjunto A por un conjunto B arroja resultados idénticos al proceso de dilatar el conjunto B por el conjunto A. Teorema 2 Sean dos conjuntos A ⊆ X y B ⊆ X, se cumple que: [ A⊕B = (A)b . b∈B

10

Demostración Se sabe que (A)x = {a + x|a ∈ A},[ entonces (A)b . A ⊕ B = {a + b|a ∈ A ∧ b ∈ B} = {(A)b |b ∈ B} = b∈B

Esto nos da un algoritmo para encontrar la dilatación de un conjunto A por un elemento de estructura B de cardinalidad k. 1. Escoger un elemento del conjunto B, digamos b1 ∈ B. 2. Encontrar (A)b1 , la traslación del conjunto A por el elemento b1 ∈ B. 3. Repetir los pasos 1 y 2 para cada uno de los demás elementos de B : b2 , ..., bk . 4. Encontrar el conjunto unión de la familia {(A)bi }i=1,2,...,k . El resultado es el conjunto A ⊕ B. La operación de dilatación tiene propiedades algebraicas y geométricas interesantes, algunas de las cuales permiten realizar procesos específicos sobre los elementos de estructura, que conlleva a un uso más eficiente de esta operación morfológica básica. Estas propiedades como se verá más adelante son aprovechadas para poder realizar el objetivo de esta tesis que es hacer operaciones morfológicas rápidas con elementos de estructura arbitrarios. Teorema 3 (Asociatividad) La dilatación es asociativa. Sean A, B y C subconjuntos de X, entonces: A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C. Demostración Esta demostración es desarrollada en detalle en ([9]) A ⊕ (B ⊕ C) = {z = a + y|a ∈ A ∧ (y = a + b) ∈ (B ⊕ C)} = {z = a + y|a ∈ A ∧ b ∈ B ∧ c ∈ C} = {z = a + b + c|a ∈ A ∧ b ∈ B ∧ c ∈ C} = {z = (a + b) + c|a ∈ A ∧ b ∈ B ∧ c ∈ C} = {z = d + c|(d = a + b) ∈ (A ⊕ B) ∧ c ∈ C} = (A ⊕ B) ⊕ C. El Teorema 3 ejemplifica la manera más sencilla de un tema de intenso estudio e investigación dentro de la morfología matemática: la descomposición del elemento de estructura, tal como se verá en la Sección 3.1. Teorema 4 (Invarianza a la traslación) Sean A y B dos subconjuntos de X y sea x ∈ X arbitrario, entonces: (A)x ⊕ B = (A ⊕ B)x . Demostración (A)x ⊕ B = {y = z + b|z ∈ (A)x ∧ b ∈ B} = {y|(y = z + b) ∧ (z − x ∈ A) ∧ b ∈ B} = {y|(y = (x + a) + b) ∧ a ∈ A ∧ b ∈ B} = {y|(y = x + (a + b)) ∧ a ∈ A ∧ b ∈ B} = {y = x + d|d ∈ A ⊕ B} = (A ⊕ B)x . Este teorema muestra que la dilatación es invariante a la traslación; es decir, el resultado es idéntico si se realiza cualquiera de las dos secuencias siguientes: 1. Se traslada el conjunto A por un punto x y luego se hace la dilatación con el elemento de estructura B. 11

2. Se dilata el conjunto A con el elemento de estructura B y después se traslada el conjunto A ⊕ B por el punto x. Teorema 5 (Distributividad respecto a la unión) Sean A, B y C subconjuntos de X, entonces: (A ∪ C) ⊕ B = (A ⊕ B) ∪ (C ⊕ B). [ Demostración (A ∪ C) ⊕ B = (A ∪ C)b por el Teorema 2 b∈B [ [ [ = [(A)b ∪ (C)b ] = [(A)b ] ∪ [(C)b ] = (A ⊕ B) ∪ (C ⊕ B). b∈B

b∈B

b∈B

Por último es bien sabido que si B contiene al origen entonces, la dilatación es una operación que cumple con la extensividad (ver demostración en [33], [10]), es decir, el conjunto A esta contenido en A ⊕ B, i.e. A ⊆ A ⊕ B, es claro que A es igual a A ⊕ B cuando B = {0} y como A y B son finitos, si B 6= {0}, 0 ∈ B, entonces A ⊂ A ⊕ B; además la dilatación es una operación creciente (ver demostración en [33], [10]), es decir, que con la dilatación se preserva la relación de contención, i.e. A ⊆ C −→ A ⊕ B ⊆ C ⊕ B.

2.2.

Erosión.

La operación de erosión consiste en hacer decrecer un conjunto A a través de un proceso controlado de eliminación de elementos, tomando como referencia un elemento de estructura B. Al igual que sucede en la dilatación, el tamaño y forma finales del conjunto erosionado dependerá fuertemente del tamaño y forma del elemento de estructura B. Definición 6 Sean dos conjuntos A ⊆ X, B ⊆ X. La erosión de A por B, denotada por A ª B, es definida como la resta de Minkowski de A y B, es decir: A ª B = {x ∈ X|x + b ∈ A, ∀b ∈ B}. La definición anterior nos indica un procedimiento para encontrar el conjunto erosión A ª B: 1. Escoger un punto x ∈ X. 2. Sumar ese elemento x con cada uno de los elementos de b ∈ B. 3. Si se cumple que x + b ∈ A para todas las suma posibles con x fijo, entonces x ∈ A ª B, y de acuerdo con la definición basta que la condición falle en una suma, para afirmar que x ∈ / A ª B. Es decir, es suficiente que exista un elemento de B, cuya suma con x no sea elemento de A, para decir que x no pertenece a la erosión. 4. Repetir los pasos 1, 2 y 3 para todos los elementos del espacio de trabajo X.

12

La Figura 2.6 muestra un ejemplo de erosión entre un conjunto A y un conjunto B, recordemos que al conjunto B se le conoce con el nombre de elemento estructurante o elemento de estructura.

Figura 2.6: Erosión del conjunto A por el elemento de estructura B. A diferencia de la dilatación, la erosión no es una operación que cumpla con la propiedad de ser conmutativa y para esto basta con demostrar con un ejemplo que no se cumple. Esto se puede ver en la Figura 2.7, vemos que el conjunto A ª B tiene un sólo elemento mientras que el conjunto B ª A no contiene ningún elemento.

Figura 2.7: La erosión no es conmutativa. Teorema 6 Sean dos conjuntos A ⊆ X y B ⊆ X, se cumple que: \ (A)−b . AªB = b∈B

Demostración A ª B = {x|x + b ∈ A, ∀b ∈ B} = {x|x ∈ (A)−b , ∀b ∈ B} =

\

b∈B

(A)−b .

Esto nos proporciona un algoritmo para encontrar la erosión de un conjunto A por un elemento de estructura B de cardinalidad k. 1. Escoger un elemento del conjunto B, digamos b1 ∈ B. 13

2. Encontrar (A)−b1 , la traslación del conjunto A por el inverso aditivo del elemento b1 ∈ B. 3. Repetir los pasos 1 y 2 para cada uno de los demás elementos de B : b2 , ..., bk . 4. Encontrar el conjunto intersección de la familia {(A)−bi }i=1,2,...,k . El resultado es el conjunto erosión A ª B. La erosión posee propiedades que la diferencian notablemente de la dilatación. Teorema 7 Sean A, B y C subconjuntos de X, entonces: (A ª B) ª C = A ª (B ⊕ C). Demostración (A ª B) ª C = {x|x + c ∈ (A ª B), ∀c ∈ C} = {x|x + b + c ∈ A, ∀c ∈ C, ∀b ∈ B} = {x|x + (b + c) ∈ A, ∀c ∈ C, ∀b ∈ B} = {x|x + (b + c) ∈ A, ∀(b + c) ∈ (B ⊕ C)} = {x|x + (b + c) ∈ A, ∀(b + c) ∈ (B ⊕ C)} = A ª (B ⊕ C). El Teorema 8 es importante porque permite la descomposición de elementos estructurantes. Teorema 8 Sean A y B dos subconjuntos de X y sea x ∈ X arbitrario, entonces: (A)x ª B = (A ª B)x , A ª (B)x = (A ª B)−x . Demostración Primera parte: (A)x ª B = {y|y + b ∈ (A)x , ∀b ∈ B} = {y|y + b − x ∈ A, ∀b ∈ B} = {y|y + b + (−x) ∈ A, ∀b ∈ B} = {y|y + (−x) + b ∈ A, ∀b ∈ B} = {y|[y + (−x)] + b ∈ A, ∀b ∈ B} = {y|y − x ∈ A ª B} = {y|y ∈ (A ª B)x } = (A ª B)x . Segunda parte: A ª (B)x = {y|y + c ∈ A, ∀c ∈ (B)x } = {y|y + c ∈ A, ∀c − x ∈ B} = {y|y + b + x ∈ A, ∀b ∈ B} = {y|y + x + b ∈ A, ∀b ∈ B} = {y|(y + x) + b ∈ A, ∀b ∈ B} = {y|(y + x) ∈ A ª B} = {y|y ∈ (A ª B)−x } = (A ª B)−x . Teorema 9 (Distributividad respecto a la intersección) Sean A, B y C subconjuntos de X, entonces: (A ∩ C) ª B = (A ª B) ∩ (C ª B). \ (A ∩ C)−b por el Teorema 6. Demostración (A ∩ C) ª B = b∈B \ \ \ = [(A)−b ∩ (C)−b ] = (A)−b ∩ (C)−b = (A ª B) ∩ (C ª B). b∈B

b∈B

b∈B

Por último se sabe que si B contiene al origen entonces la erosión es una operación que cumple con la antiextensividad (ver demostración en [33], [10]), es decir, AªB esta contenido en A, i.e. A ª B ⊆ A, es claro que A ª B es igual a A cuando B = {0} y como A y B son finitos, si B 6= {0}, 0 ∈ B, entonces A ª B ⊂ A; además la erosión, al igual que la dilatación, es una operación creciente (ver demostración en [33], [10]), es decir, que con la erosión se preserva la relación de contención, i.e. A ⊆ C −→ A ª B ⊆ C ª B. 14

2.3.

Dualidad erosión-dilatación.

La dilatación y la erosión exhiben la propiedad de dualidad, con la particularidad de que entran en juego el complemento del conjunto operando y el conjunto reflejado del elemento estructurante. Teorema 10 (Dualidad erosión-dilatación) Sean A y B subconjuntos de X, entonces se cumple que: (A ª B)c = Ac ⊕ B − . #c " \ [ [ [ (A)−b = [(A)−b ]c = (Ac )−b = (Ac )b = Demostración (A ª B)c = b∈B

c

b∈B

−

A ⊕B .

b∈B

b∈B −

El significado de la dualidad entre la dilatación y la erosión es relevante. Quiere decir que la acción de erosionar un conjunto A por un elemento de estructura B dado es en cierto sentido equivalente a dilatar el complemento del conjunto A con el reflejado del elemento de estructura B. Recíprocamente, dilatar un conjunto A por un elemento de estructura B es equivalente a erosionar su complemento (Ac ) con el reflejado del elemento de estructura B.

2.4.

Apertura y cerradura.

En un gran porcentaje de procesos de análisis de conjuntos (imágenes binarias), a pesar de que la dilatación y la erosión son operaciones básicas independientes, dentro de la morfología matemática se usan por parejas alternadas; es decir, normalmente se realizan procesos iterativos del tipo: erosión seguida de una dilatación y una dilatación seguida de una erosión. En un principio podría pensarse que en ambos procesos se obtendrá el mismo resultado, pero no es así, la erosión y la dilatación no son operaciones inversas, es por ello que a estos procesos se les conoce con el nombre de apertura y cerradura, respectivamente, y de hecho se consideran como operaciones fundamentales (básicas) de la morfología matemática, no obstante su definición en términos de la dilatación y la erosión. Definición 7 ([10]) La apertura de un conjunto A ⊆ X por el elemento de estructura B ⊆ X se denota como A ◦ B y se define así: A ◦ B = (A ª B) ⊕ B. Existe una interpretación geométrica simple de la operación de apertura para una región del plano real, si el elemento de estructura es un disco euclideano. Dada una región A en R2 y un disco euclideano de radio r, como elemento de estructura B, la apertura A ◦ B se forma por todos los puntos de A tal que B ⊆ A, mientras que B “rueda” en el interior de A. Esto se puede ver en la Figura 2.8.

15

Figura 2.8: Interpretación geométrica de la apertura. La caracterización geométrica de la apertura se sigue de que: A ◦ B = lo cual se demuestra en detalle en ([33], [10]).

[

(B)x ,

x∈{y|(B)y ⊆A}

Los efectos de la apertura en una región de interés dada se pueden resumir en cuatro aspectos: a) Se eliminan islas de tamaño menor al elemento de estructura. b) Se eliminan picos o cabos más delgados que el elemento de estructura. c) Se rompen istmos cuya anchura sea menor al diámetro del elemento de estructura. La apertura al igual que la erosión cumple con las propiedades de ser una operación antiextensiva y creciente. Definición 8 ([10]) La cerradura de un conjunto A ⊆ X por el elemento de estructura B ⊆ X se denota como A • B y se define así: A • B = (A ⊕ B) ª B. De manera similar a lo que sucedió con la apertura, también existe una interpretación geométrica simple de la operación cerradura. Dada una región A en R2 y un disco euclideano de radio r, como elemento de estructura B, la cerradura A • B se forma por todos los puntos de A con la unión de todos los puntos de Ac tal que B * Ac , mientras que B “rueda” en el exterior de A (véase Figura 2.9).

16

Figura 2.9: Interpretación geométrica de la cerradura. La caracterización geométrica de la cerradura se sigue de que: A•B = lo cual se demuestra en detalle en ([33], [10]).

\

[(B − )x ]c ,

x∈{y|(B − )y ∩A=∅}

La cerradura produce efectos diferentes a los que produce la apertura, según se exhibe en la siguiente lista. La cerradura produce los siguientes efectos: a) Se rellenan los lagos o huecos de tamaño menor al elemento de estructura. b) Se rellenan rajaduras o golfos más delgados que el elemento de estructura. c) Se funden estrechos cuya anchura sea menor al diámetro del elemento de estructura. La cerradura al igual que la dilatación cumple con las propiedades de ser una operación extensiva y creciente. Hay muchas aplicaciones para las operaciones de erosión, dilatación, apertura y cerradura. Estas cuatro operaciones definen prácticamente todos los filtros y procesos dentro de la morfología matemática. En este trabajo sólo se introducirán algunas conforme se requieran, debido a que el tema central de esta tesis no requiere de todas las operaciones.

2.5.

Esqueleto morfológico.

Suponga que se tiene una familia infinita numerable de elementos estructurales de la siguiente forma: H = {B0 , B1 , B2 , B3 , ...} con B0 conteniendo únicamente el origen del espacio de trabajo X, i.e B0 = {0}; B1 ⊆ X un elemento de estructura que cumple con B1 finito, B1 6= B0 , B0 ⊆ B1 y Bi = Bi−1 ⊕ B1 para i = 1, 2, 3, ..., n Tal construcción de H asegura que: 17

H.1 El origen se encuentre en todo miembro de la familia H. H.2 |Bi | > |Bi−1 | para toda i = 1, 2, 3, ..., n donde |B| significa la cardinalidad del conjunto B. Una vez construída H podemos dar una clasificación de las traslaciones de sus miembros en función de un conjunto A dado como sigue: Definición 9 ([10]) Sea H una familia como se definió anteriormente y sea A ⊆ X; la traslación de un miembro de H por p ∈ X, (Bi )p , se dice maximal o conjunto maximal en A con centro en p si y sólo si: a) (Bi )p ⊆ A. b) @q, j tales que (Bj )q ⊆ A y (Bi )p ⊂ (Bj )q . De esta manera se separan las traslaciones de los miembros de H en dos clases: maximales y no maximales (véase Figura 2.10).

Figura 2.10: Centros maximales de B0 y B1 en el conjunto A. 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 10 ([10]) Sean A, B subconjuntos de X y sea la familia de elementos estructurantes H como se definió anteriormente. El esqueleto morfológico de A, dado B, queda expresado por: K [ S(A) = Sk (A) k=0

con Sk (A) = (A ª Bk ) − (A ª Bk ) ◦ B1 , y donde K es un número natural tal que K = min{k|A ª Bk = ∅}. 18

Si además B1 es simétrico, i.e. B1 = B1− , el esqueleto morfológico recibe el nombre de transformada al eje medio. Veamos ahora la relación que existe entre la clasificación de las traslaciones de los miembros de H, el conjunto A y la definición de esqueleto morfológico de A. Para ésto, nos apoyaremos de los siguientes teoremas: Teorema 11 ([10]) Si a ∈ A ⊆ X, entonces a pertenece a algún conjunto maximal en A. Demostración Sea a ∈ A, entonces a ∈ (Bk )a para algún k, por ejemplo k = 0, implica que (B0 )a = {a}. Dicho lo anterior, existen dos casos: Caso 1: (Bk )a es maximal. Caso 2: (Bk )a no es maximal, como A es finito, entonces existe (Bl )p tal que (Bl )p ⊆ A, y (Bk )a ⊆ (Bl )p , lo que implica que (Bl )p es maximal, por lo tanto a ∈ (Bl )p . Teorema 12 ([10]) Sea (Bk )p ⊆ A ⊆ X. Si (Bk )p es maximal en A entonces p ∈ Sk (A). Demostración Se demostrará por el método indirecto. / (A ª Bk ) − (A ª Bk ) ◦ B1 . Pero la apertura es Suponga que p ∈ / Sk (A), entonces p ∈ antiextensiva y además, por la definición de erosión, (Bk )p ⊆ A −→ p ∈ (AªB[ k ). De manera (B1 )c de que p ∈ (A ª Bk ) ◦ B1 = ((A ª Bk ) ª B1 ) ⊕ B1 −→ p ∈ (A ª Bk+1 ) ⊕ B1 = c∈(AªBk+1 )

donde ∃c ∈ (A ª Bk+1 ) tal que p ∈ (B1 )c . Sin embargo c[ ∈ (A ª Bk+1 ) implica que (Bk+1 )c ⊆ A. Por otro lado, si p ∈ (B1 )c se cumple que (Bk )p ⊆ (Bk )b = Bk ⊕ (B1 )c = (Bk+1 )c lo b∈(B1 )c

que implicaría que (Bk )p no es maximal.

De esta manera, el esqueleto S(A) de A obtenido como la unión de los subesqueletos Sk (A), tiene la propiedad de que A es una de sus reconstrucciones. Es decir, se puede obtener A de nuevo a partir de S(A), por medio de la unión de dilataciones de los subesqueletos como se establece a continuación: Teorema 13 ([10]) Sea S(A) =

K [

k=0

B ⊆ X, se cumple

Sk (A) el esqueleto de algún conjunto A ⊆ X. Dado

A=

K [

k=0

Sk (A) ⊕ Bk .

Demostración Parte 1: Resulta claro, a partir de la definición de Sk (A) que Sk (A) ⊆ (A ª Bk ) para k = 0, 1, 2, ..., K. Pero la apertura es antiextensiva así como la erosión para cualquier miembro de H. De modo que Sk (A) ⊆ A para k = 0, 1, 2, ..., K. De donde Sk (A) ⊕ K [ Bk ⊆ (A ª Bk ) ⊕ Bk para k = 0, 1, 2, .... Finalmente Sk (A) ⊕ Bk ⊆ A. k=0

19

Parte 2: Sea a ∈ A entonces existe un maximal (Bk )p en A tal que a ∈ (Bk )p , por K [ Sk (A) ⊕ Bk . De donde se consiguiente p ∈ Sk (A) de manera que a ∈ Sk (A) ⊕ Bk ⊆ k=0

concluye que A ⊆

K [

k=0

Sk (A) ⊕ Bk .

Se puede observar que dada la naturaleza del esqueleto morfológico S(A), éste se puede obtener como la unión de todos los centros maximales posibles que están en el conjunto A. Una de las grandes ventajas del esqueleto morfológico sobre otros tipo de esqueletos (adelgazamiento) es que puede ser utilizado como método de descomposición para un conjunto cualquiera, dado que a partir de éste se puede reconstruir exactamente el conjunto original; como consecuencia de ello, el esqueleto morfológico es único para un conjunto cualquiera. Se sabe que dentro de la morfología matemática es importante el elemento de estructura debido a que todas las operaciones morfológicas depende fuertemente del mismo. En la práctica el elemento de estructura es usualmente simétrico. Por otro lado los elementos de estructura más interesantes son aquellos que forman discos en algún espacio métrico. Dentro de la morfología clásica, para 4 métricas particulares (d4 , d8 , d6R y d6L ) en el plano discreto es posible desarrollar una erosión (o dilatación) con un disco de radio i por medio de i erosiones (o dilataciones). Para estas 4 métricas, la operación morfológica crece linealmente con respecto al radio del disco usado como elemento de estructura. Por lo que es necesario introducir algunos conceptos acerca de métricas y transformada de distancia.

2.6.

Espacios métricos.

En esta sección los siguientes resultados, son reportados de ([7], [8]), donde son demostrados en detalle, de aquí en adelante Y ⊆ R. Recordemos primero el concepto bien sabido de métrica. Definición 11 Sea Y un conjunto. Una métrica sobre Y (también llamada distancia) es una función d : Y × Y −→ R+ ∪ {0} tal que: a) d(x, y) = 0 ←→ x = y con x, y ∈ Y. b) d(x, y) = d(y, x) ∀x, y ∈ Y. c) d(x, y) ≤ d(x, z) + d(z, y) ∀x, y, z ∈ Y (desigualdad del triángulo). La dupla (Y, d) es llamada espacio métrico. Ahora se presentan algunas propiedades importantes de las métricas: Teorema 14 ([6]) Dadas d1 , d2 métricas en Y se sigue que: d3 (x, y) = α · d1 (x, y) + β · d2 (x, y); con α, β ∈ R+ es una métrica en Y . 20

Definición 12 Sea d una métrica en Y tal que para cualquier x, y, c ∈ Y se tiene que: d(x, y) = d(x + c, y + c). Entonces d se llama invariante bajo traslación. Las métricas usadas comúnmente en Z2 , las cuales formarán parte de este trabajo, se definen como sigue. Sean p1 = (x, y), p2 = (u, v) dos puntos sobre Z2 . d4 (p1 , p2 ) d8 (p1 , p2 ) d6L (p1 , p2 ) d6R (p1 , p2 )

= = = =

|u − x| + |v − y|, max{|u − x|, |v − y|}, max{|u − x|, |v − y|, |u − x + v − y|}, max{|u − x|, |v − y|, |u − x − v + y|}.

En la Figura 2.11 se pueden observar las bolas de radio unitario para estas métricas.

Figura 2.11: Bolas de radio unitario para métricas discretas. Propiedad 1 ([6]) Las métricas d4 , d8 , d6R y d6L son métricas invariantes a traslación. Lema 1 ([6]) Las funciones dl (x, y) = α · d4 (x, y) + β · d8 (x, y) + γ · d6R (x, y); α, β, γ ∈ R+ ó dl (x, y) = α · d4 (x, y) + β · d8 (x, y) + γ · d6L (x, y); α, β, γ ∈ R+ son métricas invariantes a traslación. Definición 13 Sea Nk (c) = {p ∈ Z2 |dk (c, p) = min(D − {0})} la k-vecindad centrada en c, donde dk ∈ {d4 , d8 , d6R , d6L , dl } y D es el rango de la métrica. El conjunto K(c) = {(p − c, dk (p, c))|p ∈ Nk (c)} es llamado la k-vecindad de distancia de c inducida por dk . Lema 2 ([6]) Una métrica d ∈ {d4 , d8 , d6R , d6L , dl }, induce la misma vecindad de distancia de K(c), ∀c ∈ Z2 .

21

Definición 14 Sea (Z2 , dk ) el espacio métrico con dk ∈ {d4 , d8 , d6R , d6L , dl }. El conjunto definido por: E(R) = {x ∈ R|min{dk (x, y)} > min(D − {0}); y ∈ / R}

donde D es el rango de la métrica dk ; es llamado el conjunto erosionado de R, donde R es la región de interés y el operador definido como E es llamado simplemente erosión para la métrica dk . Definición 15 Sea (Z2 , dk ) un espacio métrico con dk ∈ {d4 , d8 , d6R , d6L , dl }. El conjunto definido por: / R} r E(R) = {x ∈ R|min{dk (x, y)} > r, y ∈

donde D es el rango de la métrica dk ; es llamado el conjunto r-erosionado de R, donde R es la región de interés y el operador definido como r E es llamado erosión simultanea para la métrica dk .

Lo anterior permite definir operadores morfológicos básicos en función de la transformada de distancia la cual será definida con detalle en la siguiente sección. Teorema 15 ([6]) Si (Z2 , dk ) es el espacio métrico con dk ∈ {d4 , d8 , d6R , d6L , dl }, entonces se tiene que: n E(R) = {x ∈ R|δ(x) > n}

/ R} es una función de transformación de distancia y R es la donde δ(x) = min{dk (x, y)|y ∈ región de interés (ver Sección 2.7). Definición 16 Sea (Z2 , dk ) el espacio métrico con dk ∈ {d4 , d8 , d6R , d6L , dl }. El conjunto definido por: T (R) = R ∪ {y ∈ / R|min{d(x, y)} = min{D − {0}}; x ∈ R} donde D es el rango de la métrica dk ; es llamado el conjunto dilatado de R, donde R es la región de interés y el operador definido como T es llamado simplemente dilatación para la métrica dk . Definición 17 Sea (Z2 , dk ) el espacio métrico con dk ∈ {d4 , d8 , d6R , d6L , dl }. El conjunto definido por: / R|min{d(x, y)} ≤ r, r ∈ D; x ∈ R} r T (R) = R ∪ {y ∈

donde D es el rango de la métrica dk ; es llamado el conjunto r-dilatado de R, donde R es la región de interés y el operador definido como r T es llamado dilatación simultanea para la métrica dk . Como la dilatación y la erosión son operaciones duales es evidente que: Teorema 16 ([6]) Si (Z2 , dk ) es un espacio métrico con dk ∈ {d4 , d8 , d6R , d6L , dl }, entonces se mantiene que: c c n T (R) = {x ∈ R |δ(x) > n}

donde δ(x) = min{dk (x, y)|y ∈ / R} es una función de transformación de distancia y R es la región de interés (ver Sección 2.7). 22

Es claro que teniendo algoritmos de tiempo constante para la erosión y dilatación, entonces se obtienen algoritmos de tiempo mínimo para cualquier operador morfológico debido a que los operadores morfológicos se construyen a partir de éstos dos, por ejemplo apertura, cerradura, y esqueleto morfológico. El propósito principal de esta tesis, es mostrar que con el uso de un nuevo enfoque basado en la estructura de espacio métrico y redefiniendo (generalizando) algunos conceptos del procesamiento de imágenes y morfología matemática, es posible reducir la complejidad de las operaciones morfológicas para cualquier elemento de estructura B. Se propone el uso de la transformada rápida de distancia, debido a que esta transformación engloba la información concerniente a todos los discos incluidos en la región.

2.7.

Transformada de distancia

La transformación de distancia convierte una región binaria, en otra región, donde el valor de cada píxel es la distancia del mismo al píxel más cercano del fondo. La transformada de distancia se ha analizado en la literatura bajo tres puntos de vista: 1. Como método para comprimir la información contenida en la imagen. 2. Como una herramienta para generar esqueletos. 3. Como una base para el análisis de características de la imagen. Definición 18 ([6]) Un mapeo DT : DT : F −→ ∆ = {(x, δ(x))}; x ∈ X F = {(x, f (x))}; f : X −→ {0, 1} f (x) = 1 ←→ x ∈ R ⊆ X y f (x) = 0 ←→ x ∈ /R n + δ : X ⊆ R −→ R ∪ {0} δ(x) = min{d(x, y)|y ∈ / R} es llamado transformada de distancia, donde d ∈ {d4 , d8 , d6R , d6L } es una métrica, R la región de interés, F y ∆ son imágenes y δ es llamada función de transformación de distancia. Lo anterior quiere decir que para una región de interés la cual corresponde al conjunto de duplas {x, f (x)} tal que f (x) = 1, al aplicarle la función de transformación de distancia δ se obtiene otro conjunto de duplas {x, δ(x)} tal que δ(x) ∈ N. A continuación se presenta una consecuencia directa de la definición de transformada de distancia.

2.8.

Transformada rápida de distancia

La transformada rápida de distancia proporciona una herramienta eficiente para la obtención de operaciones morfológicas de tiempo constante, es decir, de complejidad constante. A continuación se presenta el fundamento teórico para realizar dicha transformación.

23

Teorema 17 ([5]) Si d es una de las métricas d4 , d8 , d6R , d6L y N(c) = {pi ∈ Z2 : d(c, pi ) = 1}, entonces para c, p ∈ Z2 , c 6= p y c ∈ R , donde R es la región de interés se tiene: a) d(c, p) = min{d(pi , p) : pi ∈ N(c)} + 1 b) d(c, p) = max{d(pi , p) : pi ∈ N(c)} − 1 Este teorema nos permite definir lo siguiente: Si tenemos la transformada de distancia de todos los puntos de N(c) ∈ R, es decir los vecinos de c, podemos encontrar la transformada de distancia de c, donde δ(c) = min{distancias de sus vecinos} + 1. Ahora tenemos una transformada de distancia en sólo 2 pasos: 1) Barrer la imagen binaria de arriba hacia abajo y de izquierda a derecha, en este orden, asignando para todo píxel c ∈ R, donde R es la región de interés. δ(c) = 1 + min{δ(pj ) : pj ∈ D}, R la región a transformar y D alguno de los siguientes conjuntos según la métrica dada. p2 p1 c Para la métrica d4

p3 p4 p2 c p1

p2 p3 p1 c

Para la métrica d8

Para la métrica d6L

p3 p2 c p1 Para la métrica d6R

donde los espacios en blancos son valores que no importa su valor debido a que no intervienen en el barrido de la imagen. 2) Barrer la imagen de abajo hacia arriba y de derecha a izquierda en este orden, asignando a todo c ∈ R, el valor: δ(c) = min{δ(c), 1 + min{{δ(pi ) : pi ∈ E}}}, con E alguno de los siguientes conjuntos según la métrica dada. c p1 p2 Para la métrica d4

p1 c p2 p4 p3

c p1 p3 p2

Para la métrica d8

Para la métrica d6L

p1 c p2 p3 Para la métrica d6R

Este método tiene las siguientes características comparado con la transformada de distancia: 1. Es mucho más rápido ya que sólo requiere calcular mínimos en un conjunto de cardinalidad fija. 2. El tiempo de procesamiento es el mismo para cualquier imagen a diferencia de la transformada de distancia. 3. El resultado de la transformada de distancia es exactamente el mismo. El uso de la transformada rápida de distancia proporciona algoritmos de tiempos constante ya que éste no depende de que tan gruesa sea la imagen y como se verá en el Capítulo 4 proporciona una herramienta muy eficiente para obtener el esqueleto morfológico, el cual es empleado para la metodología de descomposición del elemento de estructura. 24

Capítulo 3 Estado del arte En este capítulo se presenta el estado del arte de los métodos más utilizados para realizar operaciones morfológicas rápidas, dichos métodos son analizados minuciosamente con la finalidad de ser comparados con el algoritmo propuesto en esta tesis. Todos los resultados presentados en este capítulo son desarrollados con detalle en las publicaciones que se dan como referencia. Primero se dan algoritmos clásicos utilizados en la morfología matemática, posteriormente se analizan 3 artículos que a consideración del autor se apegan al tema de la presente tesis. La dilatación y la erosión son las dos operaciones básicas de la morfología matemática ([33]). La dilatación de un conjunto A por un elemento de estructura B, representado por A ⊕ B, es la suma de Minkowski (Definición 4): A ⊕ B = {a + b|a ∈ A ∧ b ∈ B}, la erosión se obtiene por dualidad de la dilatación, i.e., el complemento de la dilatación caracterizado sobre el complemento del conjunto A (Teorema 10), es decir: A ª B = (Ac ⊕ B − )c , otros operadores morfológicos pueden ser derivados de las dos operaciones básicas. Una aplicación directa de la definición de arriba permite un costo de complejidad computacional o(n2 · i2 ) (donde o(f (x)) es el orden de la función f (x), véase más detalles en ([30])) para una región de interés A ⊆ X de tamaño n × n, es decir, A esta contenido en una cuadrícula de n píxeles de ancho por n píxeles de largo (véase Figura 3.1) y un elemento de estructura B que es un disco de radio i, i.e., B = {(x, y) ∈ Z2 |d(x, y) ≤ i} con d ∈ {d4 , d6R , d6L , d8 }, proporciona un algoritmo de complejidad cuadrática; es por ello que se han desarrollado diversas técnicas para la implementación de operaciones morfológicas rápidas, las cuales serán mencionadas a continuación.

3.1.

Descomposición del elemento de estructura.

La dilatación es una operación asociativa ([33], [10]), i.e. (Teorema 3): A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C. 25

Lo anterior ejemplifica de una manera sencilla un tema de intenso estudio e investigación dentro de la morfología matemática: la descomposición de elementos estructurantes. Una cantidad importante de investigadores se ha dado a la tarea de buscar métodos para descomponer elementos estructurantes en subconjuntos propios de éstos (véase Figura 3.1), con el propósito de lograr ventajas computacionales.

Figura 3.1: Ejemplos de descomposición del elemento de estructura en subconjuntos propios. Aplicando las dilataciones con elementos de estructura más pequeños sucesivamente (B1 , B2 , ..., Bn ), se obtiene el mismo resultado que si se aplica el elemento de estructura original, i.e. B = B1 ⊕ B2 ⊕ ... ⊕ Bn , esto nos permite reducir el número de operaciones que se realiza en la dilatación (ó erosión); además para estas implementaciones la complejidad se reduce a o(n2 · i) para un disco B de radio i ([33], [10]). Por ejemplo para un disco B de radio i usando al métrica d8 , esta operación se reduce de o(n2 · (2i + 1)2 ) a o(n2 · 2(2i + 1)). Aunque este método reduce considerablemente el número de operaciones en una dilatación ó erosión, sólo puede ser aplicado a elementos de estructura de cierta forma (discos de radio i utilizando cualquiera de las métricas básicas). Como consecuencia de ello para elementos de estructura arbitrarios en su gran mayoría no funcionará, dado que la descomposición no es directa para estos elementos, a diferencia de las presentadas en la Figura 3.1. Lo anterior ha motivado a los investigadores a encontrar métodos distintos para realizar operaciones morfológicas rápidas; con lo que se puede concluir que este método es muy deficiente en tiempo de procesamiento y complejidad con respecto a los algoritmos utilizados actualmente, en particular comparado con el método que se presenta en este trabajo tiene grandes desventajas: 26

La complejidad es mayor (polinomial). Sólo se puede aplicar para ciertos elementos de estructura conocidos. El tiempo de procesamiento es mucho mayor.

3.2.

Procesamiento de contorno

Para implementar una dilatación de un conjunto A, solamente es necesario considerar el contorno de este conjunto, lo cual nos proporciona lo siguiente: A ⊕ B = A ∪ (∂(A) ⊕ B), donde ∂(A) es el contorno de A, definido como ∂(A) = A − (A ª B). Si l es la longitud del contorno de A, i.e. la cardinalidad del conjunto ∂(A), entonces la complejidad computacional es reducida a o(l · i2 ) para cualquier disco de radio i, más un término o(n2 ) que se utiliza para determinar los píxeles que pertenecen a ∂(A) como se menciona en ([35]). De esta última ecuación, en combinación con la propiedad de asociatividad de la dilatación, se tienen las bases para algoritmos de procesamiento de contornos para descomponer elementos de estructura, tal como lo presentaron Van Vliet y Verweer ([35]), quienes redujeron la complejidad a o(lmax · d) donde lmax es el máximo tamaño del contorno durante las iteraciones con elementos de estructura. Finalmente, Vincent ([37]) propuso un algoritmo usando ambos contornos, ∂(A) y ∂(B), del conjunto A y el elemento de estructura B, respectivamente. Este algoritmo tiene una complejidad proporcional al producto del número de píxeles de cada contorno, lo cual significa o(l · i) para un disco de radio i más dos términos cuadráticos que se utilizan para determinar los contornos de estos conjuntos como se señaló anteriormente. Podemos observar que ambos métodos propuesto reducen la complejidad y el tiempo de procesamiento con respecto a la descomposición de los elementos de estructura; no obstante estos métodos se vuelven ineficientes cuando los elementos de estructura son arbitrarios y sobre todo son imágenes de gran tamaño, lo anterior se debe al cálculo que se realizan para obtener los píxeles del contorno, donde se utilizan definiciones de 4-conectividad y 8conectividad de Groen & Foster ([16]). Estas definiciones de 4 y 8 conectividad se realizan mediante una sumatoria de 4 y 8 vecinos de cada píxel de la imagen, y es por ello que los algoritmos son ineficientes cuando el conjunto a dilatar crece. El método propuesto en esta tesis presenta ventajas marcadas respecto a los algoritmos mencionados: El tiempo de procesamiento es menor, sobre todo cuando los conjuntos son de mayor tamaño, i.e. un número muy grande de píxeles. La complejidad es menor. 27

3.3.

Uso de la transformada de distancia. 2

Cuando B ⊆ Z es una bola o disco, i.e. cuando está definida como: B = {b|d(b, 0) ≤ i}, donde d es una métrica definida sobre Z2 , entonces la dilatación por B también puede ser expresada como un umbral de una función de distancia, i.e. A ⊕ B = {x|d(x, A) ≤ i} donde, d(x, A) es la distancia del píxel x al conjunto A, i.e. la distancia del píxel x al píxel más cercano perteneciente a A, como lo definió Borgerfors ([1]). Esto significa que la dilatación puede ser considerada como un umbral de la transformada de distancia. Para un disco B de radio i los algoritmos correspondientes a la transformada de distancia son de complejidad o(n2 ) para conjuntos de n × n, con lo cual las operaciones morfológicas utilizando este método también son de complejidad cuadrática. En general, este método es menos eficiente que las técnicas de procesamiento de contorno, como consecuencia es menos eficiente que el método propuesto en esta tesis. Aunque la mayoría de estos algoritmos son de complejidad cuadrática, J. L. Díaz de León usa la transformada rápida de distancia ([5]), reduciendo la complejidad a o(2n), lo cual permite implementar unos de los algoritmos más rápidos para obtener operaciones morfológicas para las métricas básicas cuando el elemento de estructura son bolas o discos de radio i; el método propuesto por J. L. Díaz de León ([7], [8]), es la base de este trabajo, por lo cual sólo presenta una sola desventaja respecto al mismo: Sólo es aplicable a bolas o discos de radio i y no a elementos de estructura arbitrarios (que no sean discos).

3.4.

Uso de la transformada de distancia Euclideana.

Ragnelmam ([28]) propone combinar el procesamiento de contorno y la umbralización de la transformada de distancia. Él fusionó el concepto de bucket sorting propagation de Piper and Granum ([27]) y Verwer ([36]) con la métrica de distancia quasi Euclideana de Danielsson ([4]). El resultado de la transformada de distancia quasi Euclideana por propagación puede ser restringida a los píxeles con una distancia menor que i; una implementación muy eficiente produciría una complejidad similar que los métodos de procesamiento de contorno. Desafortunadamente, como lo señaló Ragnelmam ([29]), la transformada de distancia de Danielsson no es Euclideana exacta y puede llevarnos a pequeños errores en configuración de píxeles de objetos particulares, como se ilustra en la Figura 3.2. Mientras este error es pequeño para una simple dilatación, esto puede traer consecuencias catastróficas cuando uno considera otros operadores tal como la cerradura morfológica (Definición 8), ó A • B = ((A ⊕ B)c ⊕ B)c , 28

usando solamente la dilatación y el complemento de un conjunto, esto debido a la dualidad de la erosión y la dilatación (Teorema 10).

Figura 3.2: Error de la transformada de distancia quasi Euclideana. Considerando el ejemplo de la Figura 3.2, un conjunto A = {a, b, c} y un elemento estructural B = {b|d(b, 0) ≤ 13} el píxel x es erróneamente clasificado como perteneciente a (A ⊕ B)c . Durante la segunda dilatación, el error no es reproducido. Por lo cual el píxel b es incluido en (A ⊕ B)c ⊕ B, y la cerradura morfológica de A por B no contiene b, i.e. A • B = {a, b}. Esto contradice una propiedad fundamental de la cerradura: extensividad, i.e.: A ⊆ (A • B). Es posible evitar este problema por el uso de algoritmos de una transformada de distancia Euclideana exacta por propagación más tarde propuestos por Ragnelmam ([29]) ó Eggers ([14]). Desafortunadamente estos algoritmos tienen una complejidad o(n3 ) para imágenes de n × n. Esto no es mejor que la aplicación directa de métodos de procesamiento de contorno para discos de radio i. Otra manera de hacer operaciones morfológicas a través de la distancia Euclideana es el método propuesto por Cuisenaire ([3]), quién a través de un algoritmo de propagación logra conseguir complejidades iguales a los métodos de procesamiento de contorno reduciendo el tiempo. De la discusión anterior podemos concluir que en el mejor de los casos la complejidad se ha llegado a reducir a complejidades iguales a los métodos de procesamiento de contorno, pero en estos algoritmos de propagación se ha reducido el tiempo de procesamiento; no obstante el calcular una transformada Euclideana implica realizar operaciones de multiplicación y suma, aunque en un principio se podría pensar que esto no tiene gran relevancia, marca una diferencia en el tiempo de procesamiento con respecto a las operaciones unión y traslación, las cuales son empleadas en el método propuesto en este trabajo, de ahí que los algoritmos que utilizan la transformada de distancia Euclideana por propagación tienen las mismas desventajas que los métodos de procesamiento de contorno respecto al propuesto en este trabajo.

29

3.5.

Método Talbot-Van Droogenbroeck.

M. Van Droogenbroeck & Hugues Talbot ([13]) proponen un algoritmo general que realiza operaciones básicas de morfología matemática, como erosiones y aperturas, con elementos de estructura arbitrarios en una manera eficiente. Además mostraron que la complejidad de su algoritmo es menor o igual que los algoritmos que utilizan una transformación de distancia, pero con la particularidad que el tiempo de procesamiento es menor. Introduciremos brevemente las definiciones usadas en este método. La definición de suma de Minkowski es tomada de Haralick ([18]). Sea f una función definida sobre el espacio Z2 (f : Z2 −→ Z), B ⊆ Z2 un elemento de estructura y fb (x) = f (x − b) la traslación de f (x) por b en Z2 , la erosión de f ª B (respectivamente dilatación f ⊕ B) de una función f por B mapea f en otra función definida como: ^ {f−b (x)}, (f ª B)(x) = b∈B

(f ⊕ B)(x) =

V

W

_

b∈B

{fb (x)},

donde (min) y (max) denotan respectivamente las operaciones del mínimo y máximo. Para el caso de imágenes binarias, f tiene valores de 0 y 1. Lo anterior nos permitirá desarrollar un algoritmo, el cual se describe a continuación.

3.5.1.

Descripción del algoritmo.

Por simplicidad Droogenbroeck y Talbot solo presentaron el caso de erosión, el caso de dilatación es obtenido por dualidad (Teorema 10). También asumieron que B contiene el origen, i.e. 0 ∈ B. En una implementación de la definición de la erosión mencionada anteriormente, se debe calcular el valor mínimo de f−b (p) para todo b ∈ B para un punto p, lo cual es algo ineficiente en tiempo de procesamiento. Para reducir este tiempo de procesamiento se realiza lo siguiente: Para la erosión (f ª B)(p), se calcula el valor mínimo de f−b (p) para todo b ∈ B, es decir se calcula el valor mínimo de f dentro de (B)p . Este cálculo debe hacerse para todos los píxeles de la imagen f , esto se logra haciendo un barrido de píxel a píxel de izquierda a derecha en una línea horizontal, lo cual corresponde a una traslación de B de píxel a píxel. Esto se puede observar en la Figura 3.3, donde (B)p es una traslación del elemento de estructura B por el punto p y (B)q es otra traslación. Ahora hay que calcular (f ª B)(q), lo que equivale a calcular el valor mínimo de f dentro de (B)q , pero se conoce el valor mínimo de f dentro de (B)p , como la traslación es de un píxel, es claro que los valores de f dentro de (B)p ∩ (B)q son totalmente conocidos, entonces para obtener el valor mínimo de f dentro de (B)q , sólo es necesario considerar los valores de f para lo puntos que pertenecen a (B)q que no se encuentran en la intersección, en la Figura 3.3 se muestran estos puntos con los símbolos “+” y “-”, el símbolo + es cuando se realiza una dilatación (pueden ser puntos de dilatación) y el símbolo - es cuando se realiza una erosión (pueden ser puntos de erosión). 30

Como la traslación de B es de un píxel el subconjunto formado por los símbolos + (o por los símbolos -) corresponden al contorno de B. A continuación se realiza lo mismo para todos los puntos de la imagen f . Es claro que el realizar lo anterior dismuye el tiempo de procesamiento porque no se requiere estar calculando el valor mínimo de (f ª B)(x) para cada punto x. Para calcular el mínimo valor de f dentro de Bq , es suficiente memorizar el histograma de todos los puntos de f dentro de Bp , entonces contamos los puntos los cuales aparecen y aquellos que desaparecen en el histograma durante la traslación hacia Bq . El mínimo valor puede ser obtenido del nuevo histograma, el cual es ciertamente el histograma de los valores de f dentro de Bq . Es mucho más eficiente trabajar con el histograma que estar buscando el mínimo valor después de cada traslación.

Figura 3.3: Traslación de B.

3.5.2.

Complejidad del algoritmo.

Como el tiempo necesario para calcular el mínimo valor en un histograma no depende del número de puntos que forman el histograma, sino que depende solamente del número de posibles niveles de grises en la imagen, se puede derivar una complejidad teórica del algoritmo descrito anteriormente. Caso peor: el peor de los casos sucede cuando el elemento de estructura a ser usado es tal que no existe intersección entre el elemento de estructura en una posición y su siguiente posición en la gráfica después de haber hecho solamente una traslación. En este caso, el algoritmo examinará todos los puntos en el elemento de estructura para cada traslación. En otras palabras, la complejidad del algoritmo en este caso es la misma que el método trivial, el cual es proporcional al área A del elemento de estructura. Ejemplos de estos elementos de estructura son segmentos de líneas no orientados en la dirección de la traslación, o del grosor de un píxel (anillos delgados).

31

Caso mejor: el mejor caso sucede cuando el número de píxeles los cuales son modificados durante una traslación es muy pequeño comparado con el número total de píxeles del elemento de estructura. En este caso, la complejidad para el método es constante, o casi constante. Este es el caso particular para líneas orientadas en la misma dirección de la propagación: la complejidad del algoritmo y el tiempo de procesamiento son independientes de la longitud del segmento. Caso típico: típicamente, el elemento de estructura tiene un perímetro mucho menor que su área. Para tal elemento de estructura típico, el conjunto de píxeles modificados durante una traslación del elemento de estructura es incluido en el perímetro del mismo, lo cual es proporcional a la raíz cuadrada del diámetro del elemento de estructura. Por ejemplo si consideramos un elemento de estructura cuadrado, los píxeles modificados durante una traslación son aquellos que pertenecen al borde del elemento de estructura perpendicular a la dirección de la traslación (véase Figura 3.4).√Si A es el área del elemento de estructura, entonces la complejidad del método es o( A).

Figura 3.4: Histograma local para una traslación de B. En el caso digital, necesitamos ser capaces de arreglar las traslaciones de un píxel del elemento de estructura considerado a lo largo de un subconjunto de las direcciones principales de la retícula; ejemplos de estos subconjuntos son mostrados en la Figura 3.5.

32

Figura 3.5: Barrido de la imagen según su forma. Necesitamos empezar el proceso por calcular un (y si es posible, solamente uno) histograma bajo una posición del elemento de estructura (por ejemplo, en la coordenada superior izquierda), y entonces trasladar píxel a píxel el elemento de estructura con el algoritmo descrito anteriormente hasta cubrir toda la imagen.

3.5.3.

Implementación del algoritmo

Aquí se presenta el pseudo-código completo del algoritmo en el caso de una erosión para un elemento de estructura sobre un red cuadrada. Algoritmo 1 Talbot- Van Droogenbroeck. Declaración de datos. imIn, imagen original f imOut, imagen de salida. B, imagen binaria conteniendo el elemento de estructura. histo, histograma. Inicialización. Encontrar los puntos del borde de B en cada dirección usando traslaciones. Llenar el histograma para la primera posición de B. Programa principal Para cada línea l de imIn Para cada punto c de la línea l Trasladar B un píxel a la derecha y adaptar el histograma; ImOut[c, l] ←− min(histo); Fin Trasladar B un píxel hacia abajo y adaptar el histograma; Para cada punto c de la línea l + 1 Trasladar B un píxel a la izquierda y adaptar el histograma; ImOut[c, l + 1] ←− min(histo); Fin 33

Fin Para la implementación de la dilatación, es suficiente reemplazar el operador min() por max().

3.5.4.

Discusión y resultados.

En los resultados presentados en el artículo de Droogenbroeck & Talbot ([13]) se muestra claramente que el método descrito, tiene una complejidad menor y que el tiempo de procesamiento es rápido, pero en base a estos resultados se puede observar que el método de descomposición lineal del elemento de estructura mencionado en la Sección 2.1 es más rápido que el método Talbot-Van Droogenbroeck, aunque este último puede ser aplicado a cualquier elemento de estructura (a diferencia de la descomposición lineal que sólo es para ciertas formas). De lo anterior es claro que el método Talbot-Van Droogenbroeck respecto al presentado en este trabajo tendrá las siguientes desventajas: La complejidad es mayor. El tiempo de procesamiento es mayor.

3.6.

Método “2-D scan”

Uno de los algoritmos más recientes y más rápidos para realizar aperturas binarias es el que propone M. Van Droogenbroeck ([11]). Este algoritmo es basado en un barrido horizontal y vertical, este último se obtiene a partir del barrido horizontal. Con el resultado de estos dos barridos es posible realizar la apertura con respecto a un rectángulo de cualquier tamaño. Como es sabido la erosión A ª B (Teorema 6) y la dilatación A ⊕ B (Teorema 2) de un conjunto A ⊆ Z2 por un elemento de estructura B ⊆ Z2 son: \ A−b , AªB = b∈B

A⊕B =

[

Ab .

b∈B

La apertura de A ◦ B (Definición 7) es obtenida de una erosión seguida de una dilatación. Un disco B ⊆ Z2 de radio i, denotado por iB, es usualmente definido como: iB = B ⊕ B ⊕ ... ⊕ B (n − 1 dilataciones) donde B es el disco de radio unitario. En el artículo ([11]) se adopta que el elemento de estructura B es un rectángulo, es decir, un arreglo de n píxeles de largo por m píxeles de largo, i.e n × m y nH es una línea horizontal de n píxeles, por ejemplo si n = 2, entonces 2H es la línea horizontal que tiene 2 píxeles. 34

3.6.1.

Algoritmo basado en un barrido 2D

El algoritmo propuesto en ([11]) se puede resumir en dos fases. En la primera fase se barre el conjunto de entrada y se construyen dos matrices. Estas matrices contienen toda la información necesaria para poder realizar una apertura con un rectángulo de cualquier tamaño. En la segunda fase el conjunto de salida es llenada con valores umbrales de una matriz que es computada durante la primera fase. Este algoritmo descrito en dos fases, es nombrado “2-D scan”, el cual es similar a los algoritmos rápidos de dilatación y erosión que usan umbrales de mapeos de distancia, excepto que esta técnica permite obtener directamente la apertura de las dos matrices computadas. Descripción de la primera fase: la primera matriz, denotada por HOR[i, j] o HOR, es obtenida con los valores de distancia de cada píxel contenido en un objeto (región de interés) al borde derecho de dicho objeto. Una barrido horizontal de derecha a izquierda permite obtener la matriz HOR. Para calcular la segunda matriz, denotada por V ER, el algoritmo compara los valores en las columnas de HOR. V ER[i, j] es la longitud del segmento vertical de HOR que tiene todos sus valores mayores o iguales que HOR[i, j]. En el Algoritmo 2 se da una versión simplificada del fragmento del programa correspondiente al cómputo de V ER, mientras que en la Figura 3.6 se muestra un ejemplo de la obtención de las matrices HOR y V ER. Algoritmo 2 2-D Scan Para todo i, j hacer Si HOR[i, j] 6= 0 longitud ←− 1 k ←− j − 1 Mientras HOR[i, k] ≥ HOR[i, j] hacer longitud ←− longitud + 1 k ←− j − 1 Fin k ←− j + 1 Mientras HOR[i, k] ≥ HOR[i, j] hacer longitud ←− longitud + 1 k ←− k + 1 Fin V ER[i, j] ←− longitud De lo contrario V ER[i, j] ←− 0 Fin Fin

35

Figura 3.6: Barridos horizontal y vertical de la imagen original. Descripción de la segunda fase: La primera fase no depende del tamaño del elemento de estructura; es una fase genérica que provee todos los rectángulos incluidos en A. Debido a que V ER fue construida a partir de HOR, parece ser que HOR y V ER son suficientes para computar la apertura con un rectángulo de cualquier tamaño. En la segunda fase, cada par de elementos HOR[i, j], V ER[i, j] es analizado en orden para encontrar valores apropiados. Suponga que queremos computar A◦(nH ⊕mV ). Si HOR[i, j] ≥ n y V ER[i, j] ≥ m entonces el valor HOR[i, j] es copiado al conjunto de salida, denotada por OUT , no solamente en (i, j), también en la columna en posiciones vecinas donde nH ⊕ mV cabe. Estas posiciones vecinas (i, k) son tales que HOR[i, k] ≥ HOR[i, j]. Debido a posibles accesos múltiples en OUT [i, j], es importante que un nuevo valor sea puesto en OUT [i, j] solamente si es más grande que el valor previo. Después de que todos los pares han sido analizados, OUT contiene las longitudes de todos los segmentos horizontales de A ◦ (nH ⊕ mV ). Sólo resta llenar la imagen de salida OU T a la derecha de acuerdo a los valores de OUT [i, j]. La Figura 3.7 muestra el resultado intermedio de la apertura de la imagen original (ver Figura 3.6) con un elemento estructurante B = 4H ⊕ 4V , las posiciones donde HOR[i, j] ≥ 4 y V ER[i, j] ≥ 4 han sido subrayadas, además muestra el resultado final, i.e. OUT .

Figura 3.7: Resultado de la apertura.

36

3.6.2.

Implementaciones a la salida

De una gran diversidad de técnicas que existen para optimizar algoritmos el autor de este artículo ([11]) propone estas 3 formas que a consideración de él, son las de mayor optimización: Mejor uso de las características de hardware y software. Debido a la estructura lineal de los bloques de memoria, accesar a lo largo de una fila en un arreglo 2-D es más rápido que accesar a lo largo de una columna. En orden para acelerar la computación de V ER, HOR es transpuesta antes de ser almacenada. Evitar algunos cálculos redundantes. Si HOR[i, j] = HOR[i, j − 1] entonces (i, j) y (i, j − 1) pertenecen al mismo rectángulo, y como consecuencia se tiene la misma extensión vertical. Esto significa que V ER[i, j] = V ER[i, j − 1]. Evitar rescribir píxeles en la imagen de salida. Como se puede ver en las Figuras 3.6 y 3.7, algunos píxeles (i, j) son parte de varias longitudes de segmento. Para evitar que un píxel de OUT sea direccionado varias veces, el algoritmo empieza a llenar OU T , y compara el resto del valor de longitud del segmento de la matriz intermedia en cada localización. Entonces se adapta el resto de las longitudes si el valor contenido en la matriz intermedia es mayor.

3.6.3.

Resultados.

Los resultados obtenidos del algoritmo anterior pueden ser reducidos hasta en un 50 % de tiempo de procesamiento, esto se logra sustituyendo los valores de HOR y V ER por cero cuando éstos sean estrictamente menores que el tamaño del rectángulo. En este artículo ([11]) se muestra que el algoritmo en el peor de los casos es superior 2 veces en tiempo de procesamiento sobre aquellos algoritmos que utilizan descomposición lineal ([35], [37], [26]), propagación ([12], [15], [32]), histograma binario ([20], [2]) y el Algoritmo de Van Herk ([19]). El algoritmo propuesto por M. Van Droogenbroeck es uno de los algoritmos más rápidos que realizan aperturas binarias con rectángulos de cualquier tamaño de todos los propuestos actualmente; esto debido a que la apertura obtenida en su algoritmo es realizada en 4 barridos del objeto (región de interés), lo cual nos proporciona un algoritmo de tiempo constante; idea semejante que J. L. Díaz de León ([6]) propuso con el uso de la transformada rápida de distancia quien también utiliza 4 barridos del objeto para realizar la apertura. El algoritmo propuesto en esta tesis presenta ventajas marcadas sobre el algoritmo de M. Van Droogenbroeck, las cuales se listan a continuación: El algoritmo propone ser utilizado con elementos de estructura arbitrarios, es decir, su “forma” puede ser cualquier figura (como caso particular un rectángulo de cualquier tamaño). El algoritmo es general en el sentido que éste podrá realizar cualquier operación morfológica (dilatación, erosión, apertura, cerradura). 37

En tiempo de procesamiento, el algoritmo propone ser de tiempo mínimo. Para el caso particular de un rectángulo de cualquier tamaño, el tiempo de procesamiento es todavía menor.

3.7.

Método Díaz.

J. L. Díaz de León ([7], [8]) propuso uno de los métodos más rápidos para realizar operaciones morfológicas (el más rápido de todos los propuestos actualmente). Cabe mencionar que las bases teóricas y las ideas que surgieron al realizar el método de esta tesis, son en su mayoría extensiones de las ideas propuestas originalmente por J. L. Díaz de León, es por ello que en esta sección sólo se mencionarán algunos conceptos del Algoritmo Díaz y las desventajas que presenta respecto al algoritmo presentado en este trabajo. Como se observó en la Sección 3.3, el método de la transformada de distancia para realizar operaciones morfológicas no es muy eficiente, sin embargo su complejidad puede ser reducida a o(2n). Este método conocido como transformada rápida de distancia nos da algoritmos de tiempo constante, ya que ésta solo se hace en dos barridos del conjunto (objeto de interés) y posteriormente se le aplica un umbral a esta transformada rápida de distancia, para obtener los mismo resultados y reducir considerablemente el tiempo de procesamiento. El método Díaz es general en el sentido de que puede ser utilizado con las métricas más comúnmente utilizadas en el tratamiento de imágenes (d4 , d8 , d6R , y d6L ).

3.7.1.

Descripción del algoritmo

1. Se obtiene la transformada rápida de distancia en dos barridos del objeto de interés bajo una métrica ([5]). 2. Se aplica una umbralización a la imagen que contiene la transformada de distancia. El umbral es el radio del disco utilizado como elemento de estructura. A continuación se presenta el pseudo-código del algoritmo para dilatar un objeto de interés con un elemento estructural B, donde B es un disco de radio i, bajo una métrica dada. Algoritmo 3 Díaz Entrada: Una imagen F = {(x, f (x) ∈ {0, 1})} El índice de dilatación i Salida: Una imagen iT = {(x, τ (x) ∈ {0, 1})} Iniciar Obtener F c . Obtener la transformada de distancia DT = {(x, δ(x))} de F c . 38

Fin

3.7.2.

Para i = 1, 2, 3, . . . , M1 − 1. Para j = 1, 2, 3, . . . , M2 − 1. p = (i, j) © ª δ(p)≤i τ (p) = 10 de si, otra manera

Discusión.

El método Díaz descrito anteriormente es el método de menor complejidad y sobre todo el más rápido, cuando el elemento de estructura es un disco de radio i. Cuando no es un disco entonces el método Díaz no es aplicable. Díaz no propone un algoritmo para elementos de estructura arbitrarios. Es importante mencionar que el Algoritmo Díaz, es un caso particular del método propuesto en este trabajo cuando el elemento de estructura es un disco de radio i; esto se debe a que el esqueleto morfológico del disco de radio i es un sólo punto, con lo cual el método es idéntico al método Díaz.

3.8.

Análisis del estado del arte

En este capítulo se han presentado los métodos más rápidos para realizar operaciones morfológicas. Estos algoritmos se puede clasificar desde dos puntos de vista, el primero es por la complejidad que presentan y el segundo es el elemento de estructura a utilizar. El método Díaz y el 2D-scan son los métodos de menor complejidad, sin embargo como se vió estos métodos no son aplicables a elementos de estructura arbitrarios. Por otro lado el método de procesamiento de contorno y el método de Talbot- Van Droogenbroeck son aplicables a elementos de estructura arbitrarios, pero estos métodos no son eficientes en tiempo de procesamiento. Como conclusión, el método presentado en este trabajo respecto a todos los métodos discutidos en este capítulo es menor o igual en tiempo de procesamiento, menor complejidad y es aplicable a elementos de estructura arbitrarios.

39

Capítulo 4 Descomposición del elemento de estructura en discos. En el Capítulo 3, se dieron algunos métodos de operaciones morfológicas rápidas en base a los enfoques que se dieron en la introducción; así como en el Capítulo 2, se introdujeron los conceptos necesarios para poder desarrollar el presente capítulo, en el cual se formulará un método basado en los mismo enfoques, y se tratará de mejorar algunas características principales, primordialmente la velocidad. En lo que sigue denotamos por Di el disco de radio i ∈ N con centro en el origen ®, es decir Di = {x|d(x, ®) ≤ i} donde d ∈ {d4 , d8 , d6R , d6L }. En la Sección 2.5 se mencionó que la familia H la cual, para un elemento de estructura B que cumpla con las condiciones H.1 y H.2, entonces es posible obtener el esqueleto morfológico de una región de interés A. Por otro lado sabemos que para un disco Di , existe un algoritmo de tiempo constante para realizar operaciones morfológicas (Algoritmo Díaz). Debido a lo anterior se propone una familia H 0 , la cual es formada por discos concéntricos y que cumple con las mismas condiciones que H (i.e. H.1 y H.2), luego entonces puede observarse que H 0 es un caso particular de H, lo cual implica que Di ⊆ Bi ∀i . Lo anterior se muestra en el siguiente teorema. Teorema 18 Sea H 0 una familia infinita numerable de elementos de estructura definida de la siguiente forma H 0 = {D0 , D1 , D2 , . . .}. Entonces se cumple lo siguiente: i) D0 = {®}, ii) ® ∈ Di , ∀i, iii) |Di | > |Di−1 |, ∀i, 41

iv) Di = Di−1 ⊕ D1 , ∀i. Demostración i) D0 = {x|d(x, ®) ≤ 0} = {®} ii) De la definición de Di , es evidente que ® ∈ Di , ∀i , puesto que d(®, ®) = 0 ≤ i, ∀i iii) Se debe demostrar que Di−1 ⊂ Di debido a que, para dos conjuntos finitos A ⊆ X y B ⊆ X, si A ⊂ B entonces |B| > |A|. Por la definición de Di se tiene que Di = {x|d(x, ®) ≤ i − 1} ∪ {x|d(x, ®) = i}. Por otro lado para d ∈ {d4 , d8 , d6R , d6L }, para cada i existe un x ∈ Z2 tal que d(x, ®) = i, por lo que se puede decir que Di−1 ⊂ Di . Por lo tanto |Di | > |Di−1 |, ∀i. iv) Se debe demostrar para cada métrica: Para d4 se tiene: Parte 1: Sea i ≥ 1 un índice, entonces Di−1 ⊕ D1 = {a + b|a ∈ Di−1 ∧ b ∈ D1 } = {a + b|d(a, ®) ≤ i − 1 ∧ d(b, ®) ≤ 1}. Por desigualdad del triángulo: d(a + b, ®) ≤ d(a + b, b) + d(b, ®) = d(a, ®) + d(b, ®). Por tanto Di−1 ⊕ D1 ⊆ {c ∈ Z2 |d(c, ®) ≤ (i − 1) + 1} = Di . Parte 2: Recíprocamente, si c ∈ Di entonces d(c, ®) ≤ i. Sea c = (x, y) ∈ Z2 , entonces d(c, ®) = |x| + |y| ≤ i. Si |x| + |y| ≤ i − 1 entonces d(c, ®) ≤ i − 1 y c = c + 0 ∈ Di−1 ⊕ D1 . Si |x| + |y| = i , sin pérdida de generalidad podemos suponer que x 6= 0. Sea c0 = (x − 1, y) si x > 0 ó c0 = (x + 1, y) si x < 0, entonces c = c0 ± (1, 0) lo cual implica que d(c0 , ®) = |x| + |y| − 1 = i − 1 y d(±1, ®) = 1, por lo tanto c ∈ Di−1 ⊕ D1 . Para d8 se tiene: Parte 1: Lo mismo que la métrica d4 . Parte 2: Se demostrará por casos: Caso 1: x = y = i. Si c ∈ Di entonces d(c, ®) ≤ i. Sea c = (x, y) ∈ Z2 , entonces d(c, ®) = max{|x|, |y|} ≤ i. Como x = y = i implica que d(c, ®) = max{|i|, |i|} = i, sin pérdida de generalidad podemos suponer que x 6= 0. Sea c0 = (x − 1, y − 1) = (i − 1, i − 1) si x > 0, entonces c = c0 + (1, 1) lo cual implica que d(c0 , ®) = max{|x|, |y|}−1 = i−1 y d(1, 1) = 1, por lo tanto c ∈ Di−1 ⊕D1 . Caso 2: x = i, y = −i. Si c ∈ Di entonces d(c, ®) ≤ i. Sea c = (x, y) ∈ Z2 , entonces d(c, ®) = max{|x|, |y|} ≤ i. Como x = i, y = −i implica que d(c, ®) = max{|i|, | − i|} = i, sin pérdida de generalidad podemos suponer que x 6= 0. Sea c0 = (x − 1, y + 1) = (i − 1, −i + 1) si x > 0, entonces c = c0 + (1, −1) lo cual implica que d(c0 , ®) = max{|x|, |y|} − 1 = i − 1 y d(1, −1) = 1, por lo tanto c ∈ Di−1 ⊕ D1 . Caso 3: x = i, |y| ≤ i − 1. Si c ∈ Di entonces d(c, ®) ≤ i. Sea c = (x, y) ∈ Z2 , entonces d(c, ®) = max{|x|, |y|} ≤ i. Como x = i, y ≤ i − 1 implica que d(c, ®) = max{|i|, |y|} = i, sin pérdida de generalidad podemos suponer que x 6= 0. Sea c0 = (x − 1, y) si x > 0, entonces c = c0 + (1, 0) lo cual implica que d(c0 , ®) = max{|x|, |y|} − 1 = i − 1 y d(1, 0) = 1, por lo tanto c ∈ Di−1 ⊕ D1 . Caso 4: Similar al caso 1 con x = −i, y = i. Caso 5: Similar al caso 2 con x = y = −i. Caso 6: Similar al caso 3 con x = −i, |y| ≤ i − 1. Caso 7: |x| ≤ i − 1, y = i. Si c ∈ Di entonces d(c, ®) ≤ i. Sea c = (x, y) ∈ Z2 , entonces d(c, ®) = max{|x|, |y|} ≤ i. Como |x| ≤ i − 1, y = i implica que d(c, ®) = max{|x|, |i|} = i, sin pérdida de generalidad 42

podemos suponer que y 6= 0. Sea c0 = (x, y − 1) si y > 0, entonces c = c0 + (0, 1) lo cual implica que d(c0 , ®) = max{|x|, |y|} − 1 = i − 1 y d(0, 1) = 1, por lo tanto c ∈ Di−1 ⊕ D1 . Caso 8: |x| ≤ i − 1, y = −i. Si c ∈ Di entonces d(c, ®) ≤ i. Sea c = (x, y) ∈ Z2 , entonces d(c, ®) = max{|x|, |y|} ≤ i. Como |x| ≤ i−1, y = −i implica que d(c, ®) = max{|x|, |−i|} = i, sin pérdida de generalidad podemos suponer que y 6= 0. Sea c0 = (x, y + 1) si y < 0, entonces c = c0 + (0, −1) lo cual implica que d(c0 , ®) = max{|x|, |y|} − 1 = i − 1 y d(0, −1) = 1, por lo tanto c ∈ Di−1 ⊕ D1 . Para d6R se tiene: Parte 1: Lo mismo que la métrica d4 . Parte 2: Se demostrará por casos: Caso 1: x = i. Si c ∈ Di entonces d(c, ®) ≤ i. Sea c = (x, y) ∈ Z2 , entonces d(c, ®) = max{|x|, |y|, |−x+ y|} ≤ i. Como x = i, entonces si y = −i implica que d(c, ®) = max{|i|, |−i|, |−i+i|} = i, sin pérdida de generalidad podemos suponer que x 6= 0. Sea c0 = (x − 1, y + 1) = (i − 1, −i + 1) si x > 0, entonces c = c0 +(1, −1) lo cual implica que d(c0 , ®) = max{|x|, |y|, |−x+y|}−1 = i−1 y d(1, −1) = 1, por lo tanto c ∈ Di−1 ⊕ D1 . Por otro lado si y > −i y c0 = (x − 1, y) si x > 0 satisface d(c0 , ®) = max{|i − 1|, |y|, | − i + 1 + y|} = i − 1, entonces c = c0 + (1, 0) con d(1, 0) = 1, por lo tanto c ∈ Di−1 ⊕ D1 . Caso 2 x = −i. Si c ∈ Di entonces d(c, ®) ≤ i. Sea c = (x, y) ∈ Z2 , entonces d(c, ®) = max{|x|, |y|, | − x + y|} ≤ i. Como x = −i, si y > −i y c0 = (x + 1, y) si x < 0 satisface d(c0 , ®) = max{| − i + 1|, |y|, | − i + 1 + y|} = i − 1, entonces c = c0 + (−1, 0) con d(−1, 0) = 1, por lo tanto c ∈ Di−1 ⊕ D1 . Caso 3: Similar al caso 1 con y = i. Caso 4: Similar al caso 2 con y = −i. Caso 5: |x| ≤ i − 1, |y| ≤ i − 1, |x + y| = i. Si x + y = i, x < 0 es imposible pues si x < 0, y = i − x > i. Por tanto x ≥ 0 lo cual implica que y = i − x ≤ i − 1, por lo que x > 0. Sea c = (x, y) ∈ Z2 y c0 = (x − 1, y) satisface d(c0 , ®) = max{|x − 1|, |y|, | − x + 1 + y|} = i − 1, entonces c = c0 + (1, 0) con d(1, 0) = 1, por lo tanto c ∈ Di−1 ⊕ D1 . Finalmente si x + y = −i, analogamente se tiene x < 0, y < 0 y c0 = (x + 1, y) satisface d(c0 , ®) = max{|x + 1|, |y|, | − x − 1 + y|} = i − 1, entonces c = c0 + (−1, 0) con d(−1, 0) = 1, por lo tanto c ∈ Di−1 ⊕ D1 . Para d6L se tiene: Análogo a d6R . El teorema anterior muestra que para la familia de discos de H 0 , cumple con las condiciones H.1 y H.2 de la familia H definida en la Sección 2.5. Ahora como los elementos de estructura son discos, algunas de las definiciones vistas en la Sección 2.5 son reescritas para esta nueva familia H 0 . Como se mencionó anteriormente, esta familia de discos será utilizada para obtener el esqueleto morfológico. De la Definición 2 se tiene que para p ∈ X y un disco Di ⊆ X, la traslación del disco Di por p se denota como (Di )p = {a + p|a ∈ Di }. Lo anterior nos sirve para definir un disco maximal como sigue:

43

Definición 19 Sea H 0 = {Di }i≥0 la familia definida en el Teorema 18, la traslación de un disco Di ∈ H 0 por p, donde p ∈ X; (Di )p se dice disco maximal o maximal en A ⊆ X con centro en p si y sólo si: i) (Di )p ⊆ A ii) @q, j tales que (Dj )q ⊆ A ∧ (Di )p ⊂ (Dj )q . A partir de esta definición, es posible hacer una observación entre elementos de la familia H definida en la Sección 2.5 y los elementos de la familia H 0 , esto se enuncia en lo siguiente: H ’.1 H 0 satisface las condiciones H.1 y H.2 dadas en la Sección 2.5. Teorema 19 Para A ⊆ X, existen i ≥ 0 un índice y y ∈ X, si a ∈ A entonces a pertenece a algún disco maximal en A. Demostración Es una consecuencia directa usando la condición H’.1 y la demostración del Teorema 11: Sea a ∈ A, como A es finito y no vacío, entonces a ∈ (Di )a para todo índice i ≥ 0. Fijemos i. Tenemos dos casos: Caso 1: (Di )a es maximal. Caso 2: (Di )a no es maximal, entonces existe q, j tal que (Dj )q ⊆ A ∧ (Di )a ⊂ (Dj )q , lo cual implica que (Bl )p es maximal, por lo tanto a ∈ (Dl )p . El teorema anterior muestra la relación existente entre la clasificación de los miembros de H y el conjunto A: como se mencionó en la Sección 2.5 (Teorema 13) el esqueleto morfológico S(A), puede obtenerse como la unión de todos los centros maximales posibles que están en el conjunto A; a partir de ello podemos observar que cualquier punto a ∈ A puede clasificarse como punto del esqueleto morfológico o no; cuando a es punto del esqueleto morfológico, entonces a es el centro de un disco maximal, pero si a no es punto de esqueleto morfológico, el teorema muestra que a esta contenido en algún disco maximal del conjunto A. 0

Teorema 20 Sea x, y ∈ X, i ≥ 0 un índice, A ⊆ X y (Di )x ⊆ A. (Di )x es maximal en A si y sólo si no existe y ∈ N(x) tal que δ(y) > δ(x), con i = δ(x) − 1. Demostración Primera parte: suponga cierto que ∃y ∈ N(x) tal que δ(y) > δ(x). Esto implica que existe z ∈ X tal que (Di )z ⊆ A con i = δ(x) − 1 y existe un índice j ≥ 0 tal que (Dj )y ⊆ A con j = δ(y)−1. Por la desigualdad del triángulo se tiene d(y, z) ≤ d(y, x)+d(x, z). Suponga que z ∈ (Di )x lo cual implica que d(z, x) ≤ i. Como y ∈ N(x) se sigue que d(z, y) ≤ i + 1, lo cual implica que z ∈ (Di+1 )y y (Di )x ⊆ (Di+1 )y ⊆ (Dj )y , por transitividad se tiene que (Di )x ⊆ (Dj )y , por lo tanto (Di )x no es maximal. Segunda parte: ahora suponga que (Di )x no es maximal en A, entonces existen y ∈ X y un índice j ≥ 0, tales que (Dj )y ⊆ A ∧ (Di )x ⊂ (Dj )y . Por el Teorema 18 iniciso iii) es claro que (Di )x ⊂ (Dj )y implica que j > i, además i = δ(x) − 1 y j = δ(y) − 1, lo cual implica que δ(y) > δ(x). La relación estrecha entre un punto de esqueleto morfológico obtenido por la Definición 10 y su transformada de distancia es esclarecida por el teorema anterior; es evidente que el disco maximal Di contiene la información necesaria para reconstruir la imagen original. 44

Teorema 21 Sea i ≥ 0 un índice, A ⊆ X y (Di )x ⊆ A para x ∈ X. Si (Di )x es maximal en A entonces x ∈ Si (A). Demostración Es una consecuencia directa usando la condición H’.1 y la demostración en el Teorema 12: / (A ª Di ) − (A ª Di ) ◦ D1 . Pero la apertura es Suponga que p ∈ / Si (A), entonces p ∈ antiextensiva y además, por la definición de erosión, (Di )p ⊆ A −→ p ∈ (A ªD[ i ). De manera (D1 )c de que p ∈ (A ª Di ) ◦ D1 = ((A ª Di ) ª D1 ) ⊕ D1 −→ p ∈ (A ª Di+1 ) ⊕ D1 = c∈(AªDi+1 )

donde ∃c ∈ (AªDi+1 ) tal que p ∈ (D1 )c . Sin embargo c[ ∈ (AªDi+1 ) implica que (Di+1 )c ⊆ A. Por otro lado, si p ∈ (D1 )c se cumple que (Di )p ⊆ (Di )b = Di ⊕ (D1 )c = (Di+1 )c , lo b∈(D1 )c

que implicaría que (Di )p no es maximal.

De esta manera, el esqueleto S(A) de A es obtenido como la unión de los centros de discos maximales Di contenidos en A. Es decir, se puede obtener A de nuevo a partir de S(A), por medio de la unión de las traslaciones de los discos Di . Teorema 22 Sea A ⊆ X, x, y ∈ X y sea la familia H 0 = {Di }i≥0 definida en el Teorema 18. Entonces el esqueleto morfológico de A, queda expresado por: S(A) = {x|(x, δ(x)) ∈ S ∗ (A)}, con S ∗ (A) = {(x, δ(x))|δ(x) ≥ δ(y), ∀y ∈ N(x)}. Demostración Del Teorema 21 se sigue que si (Di )x es maximal entonces x ∈ Si (A), además cuando hablamos de (Di )x , nos referimos a la dupla (x, δ(x)) por lo que Si (A) = K [ ∗ {x|(x, i + 1) ∈ S (A)}. Luego entonces de la Definición 10 se sabe que S(A) = Sk (A) y por el Teorema 20 se tiene que S ∗ (A) = {(x, δ(x))|δ(x) ≥ δ(y), ∀y ∈ N(x)}.

k=0

Este resultado muestra una nueva metodología para obtener el esqueleto morfológico, con la gran ventaja que en tiempo de procesamiento y en complejidad es mucho menor que cualquier algoritmo existente para obtener dicho esqueleto morfológico. Tal y como se ha mencionado durante el desarrollo de esta tesis, este nuevo resultado es utilizado como metodología de descomposición del elemento de estructura; no obstante lo anterior esto puede ser empleado para obtener otros resultados importantes dentro de la morfología matemática como la generalización de una familia de esqueletos tal como propone S. Juárez en ([21]). Teorema 23 Sea S(A) el esqueleto morfológico de algún conjunto A ⊆ X. Entonces se cumple [ A= (Dδ(s)−1 )s . s∈S(A)

Demostración Si a ∈ A es centro de un disco maximal implica que existe (Di )a tal que a ∈ Si (A). De la definición de un disco maximal y del hecho de que el esqueleto morfológico de un conjunto A es la unión de todos los centros de los discos maximales, los cuales 45

pertenecen a un subesqueleto Si (A), entonces A es la unión de todos estos discos maximales, [ (Di )s , con i = δ(s) − 1. en consecuencia A = s∈S(A)

Es claro que un elemento de estructura arbitrario B, es posible descomponerlo en discos usando su esqueleto morfológico, tal como se ha demostrado a lo largo de este capítulo. Ahora es posible realizar una operación morfológica con un elemento de estructura arbitrario B, esto se enuncia en el siguiente teorema: [ Teorema 24 Sea B = (Dδ(s)−1 )s , entonces se cumple que: s∈S(B)

A⊕B =

Demostración B =

[

[

(A ⊕ Dδ(s)−1 )s .

s∈S(B)

⎡

(Dδ(s)−1 )s = ⎣

s∈S(B)

[

⎤ ⎡

(D1 )s ⎦∪⎣

s∈S1 (B)

[

⎤

⎡

(D2 )s ⎦∪...∪⎣

s∈S2 (B)

[

(Dk )s ⎦,

s∈Sk (B)

k = δ(s) − 1. Como la dilatación es invariante bajo traslación (Teorema 4) y distributiva respecto a la unión (Teorema 5), ⎤ ⎡ se tiene que: [ [ [ (D1 )s ∪ (D2 )s ∪ ... ∪ (Dk )s , ⎦, k = δ(s) − 1 A⊕B =A⊕⎣ s∈S1 (B)

⎡

= ⎣A ⊕ =

[

s∈S(B)

=

[

[

⎤

⎡

s∈S2 (B)

(D1 )s ⎦ ∪ ⎣A ⊕

s∈S1 (B)

[

s∈Sk (B)

⎡

(D2 )s ⎦ ∪ ... ∪ ⎣A ⊕

s∈S2 (B)

A ⊕ (Dk )s , k = δ(s) − 1

⎤

[

⎤

(Dk )s ⎦, k = δ(s) − 1

s∈Sk (B)

(A ⊕ Dk )s , k = δ(s) − 1.

s∈S(B)

El Teorema 24 nos proporciona un algoritmo para realizar dilataciones con elementos de estructura arbitrarios, cabe mencionar que para las dilataciones del conjunto A con los discos Di , se utiliza el Algoritmo 3 (método Díaz), para que el algoritmo sea de tiempo mínimo. El pseudo-código del nuevo algoritmo se presenta a continuación: Algoritmo 4 Dilatación con un elemento de estructura arbitrario. Entrada: Imagen de entrada A = {(x, f (x) ∈ {0, 1})} Imagen del elemento de estructura arbitrario B = {(x, f (x) ∈ {0, 1})} Salida: Una imagen A ⊕ B = {(x, τ (x) ∈ {0, 1})} Inicialización: 46

⎤

A ⊕ B = {(x, 0)} Inicio Obtener la transformada de distancia de Ac , i.e DT (Ac ) = (x, δ(x)). Obtener la transformada de distancia de B, i.e DT (B) = (x, δ(x)). Obtener S ∗ (B) de DT (B). { Para i = 1, 2, ..., M1−1 (ancho de B) Para j = 1, 2, ..., M2−1 (largo de B) x = (i, ¾ ½ j) 1 si δ(x) ≥ δ(y), ∀y ∈ (N)x x= 0 de otra manera } Para k = 1, 2, . . . , max(δ(x) : x ∈ B) de DT (B) Para l = 1, 2, ..., M1−1 (ancho de S ∗ (B)) Para m = 1, 2, ..., M2−1 (largo de S ∗ (B)) y = (l, m) Si (y ∈ S ∗ (B) tal que δ(y) = k) { Para i = 1, 2, ..., M1−1 (ancho de A) Para j = 1, 2, ..., M2−1 (largo de A) p = (i, ½ j) ¾ 1 si δ(p) > k p= 0 de otra manera A ⊕ B = (A ⊕ B) ∪ (A)y } (A ⊕ B)c Fin. Una implementación directa del Algoritmo 4, muestra que el tiempo de procesamiento es mínimo, pero se puede observar que A es dilatado con Di n veces, donde n es el número de puntos que pertenecen al subesqueleto i. Aunque el algoritmo es eficiente en tiempo de procesamiento, es posible reducir este tiempo, esto se muestra en el siguiente teorema: [ Teorema 25 Sea B = (Dδ(s)−1 )s , entonces se cumple que: s∈S(B)

A⊕B =

K [

(A ⊕ Sk (B) ⊕ Dk )s ,

k=0

donde K = max{δ(x) : x ∈ B} − 1. Demostración Del Teorema 24 se tiene que A ⊕ B = Definición 10 se sigue que S(B) =

K [

k=0

[

(A ⊕ Dδ(s)−1 )s , pero de la

s∈S(B)

Sk (B), donde K = max{δ(x) : x ∈ B} − 1, además de 47

los Teoremas 2, 5 y 16 se tiene que A⊕B =

K [

(A⊕Sk (B)⊕Dk ), K = max{δ(x) : x ∈ B}−1.

k=0

El Teorema 25 nos proporciona un algoritmo para realizar dilataciones con elementos de estructura arbitrarios más eficiente en tiempo de procesamiento que el Algoritmo 4, esto se debe a que ahora sólo se realiza una dilatación para cada disco Di ; a continuación se presenta el pseudo-código del algoritmo: Algoritmo 5 Optimización del Algoritmo 4. Entrada: Imagen de entrada A = {(x, f (x) ∈ {0, 1})} Imagen del elemento de estructura arbitrario B = {(x, f (x) ∈ {0, 1})} Imagen temporal C = {(x, f (x) ∈ {0, 1})} Salida: Una imagen A ⊕ B = {(x, τ (x) ∈ {0, 1})} Inicialización: A ⊕ B = {(x, 0)} Inicio Obtener la transformada de distancia de Ac , i.e DT (Ac ) = (x, δ(x)). Obtener la transformada de distancia de B, i.e DT (B) = (x, δ(x)). Obtener S ∗ (B) de DT (B). { Para i = 1, 2, ..., M1−1 (ancho de B) Para j = 1, 2, ..., M2−1 (largo de B) x = (i, ½ j) ¾ 1 si δ(x) ≥ δ(y), ∀y ∈ (N)x x= 0 de otra manera } Para k = 1, 2, . . . , max(δ(x) : x ∈ B) de DT (B) Para l = 1, 2, ..., M1−1 (ancho de S ∗ (B)) Para m = 1, 2, ..., M2−1 (largo de S ∗ (B)) y = (l, m) Para todo y ∈ Sk∗ (B) tal que δ(y) = k { C = A ⊕ Sk∗ (B) Para i = 1, 2, ..., M1−1 (ancho de C) Para j = 1, 2, ..., M2−1 (largo de C) p = (i, ¾ ½ j) 1 si δ(p) > k p= 0 de otra manera A ⊕ B = (A ⊕ B) ∪ C } (A ⊕ B)c Fin. 48

También se puede obtener un algoritmo eficiente para la erosión; aprovechando que la dilatación es la operación dual de la erosión se obtiene el siguiente resultado . [ (Dδ(s)−1 )s , entonces se cumple que: Teorema 26 Sea B = s∈S(B)

AªB =

\

(A ª Dδ(s)−1 )−s .

s∈S(B)

Demostración Por dualidad A ª⎡B = (Ac ⊕ B − )c , A ⊕ B⎤= (Ac ª B − )c , H 0 = {Di }i≥0 , y c \ ¡ [ ¡ ¢ ¢c B = B − . Se tiene que (Ac ⊕ B − )c = ⎣ Ac ⊕ Dδ(s)−1 s ⎦ = (Ac ⊕ Dδ(s)−1 )s = s∈S(B)

s∈S(B)

\ ¡ \ \ ¢c (A ª (Dδ(s)−1 )s ) = (A ª Dδ(s)−1 )−s . Ac ⊕ (Dδ(s)−1 )s =

s∈S(B)

s∈S(B)

s∈S(B)

El Teorema 26 nos proporciona un algoritmo para realizar erosiones con elementos de estructura arbitrarios, recordemos que cuando nos referimos a un elemento de estructura arbitrario, sabemos que B debe ser finito y no vacío; cabe mencionar que para las erosiones del conjunto A con los discos Di , se utiliza el Algoritmo 3 (método Díaz), para que el algoritmo sea de tiempo mínimo. El pseudo-código del nuevo algoritmo se presenta a continuación: Algoritmo 6 Erosión con un elemento de estructura arbitrario. Entrada: Imagen de entrada A = {(x, f (x) ∈ {0, 1})} Imagen del elemento de estructura B = {(x, f (x) ∈ {0, 1})} Salida: Una imagen A ª B = {(x, τ (x) ∈ {0, 1})} Inicialización: A ª B = {(x, 0)} Inicio Obtener la transformada de distancia de A, i.e DT (A) = (x, δ(x)). Obtener la transformada de distancia de B, i.e DT (B) = (x, δ(x)). Obtener S ∗ (B) de DT (B). { Para i = 1, 2, ..., M1−1 (ancho de B) Para j = 1, 2, ..., M2−1 (largo de B) x = (i, ½ j) ¾ 1 si δ(x) ≥ δ(y), ∀y ∈ (N)x x= 0 de otra manera } Para k = 1, 2, . . . , max(δ(x) : x ∈ B) de DT B Para l = 1, 2, ..., M1−1 (ancho de S ∗ (B)) Para m = 1, 2, ..., M2−1 (largo de S ∗ (B)) y = (l, m) 49

Si (y ∈ S ∗ (B) tal que δ(y) = k) { Para i = 1, 2, ..., M1−1 (ancho de A) Para j = 1, 2, ..., M2−1 (largo de A) p = (i, ¾ ½ j) 1 si δ(p) > k p= 0 de otra manera A ª B = (A ª B) ∩ (A)−y } Fin. Aunque el Algoritmo 6 proporciona un algoritmo eficiente para realizar una erosión, sólo es necesario programar el Algoritmo 5 de dilatación y obtener por dualidad el algoritmo de erosión o viceversa, o ambos algoritmos según las necesidades. Tal como es sabido a partir de estas dos operaciones (dilatación y erosión) podemos obtener cualquier operación morfológica. Utilizando los Algoritmos 4 ó 5 se tiene la ventaja que, para toda operación morfológica, el elemento de estructura puede ser arbitrario, es decir, cualquier forma, esto debido a que la importancia de las operaciones morfológicas radica en el elemento de estructura. Finalmente, esta metodología proporciona exactamente el mismo resultado que se llegaría con los métodos propuestos en el Capítulo 3. Sin embargo, existen ventajas sobre éstos: 1. El método propuesto en este trabajo (Algoritmos 5 y 6) es aplicable a elementos de estructura arbitrarios, ya que se utiliza el esqueleto morfológico, el cual nos proporciona la reconstrucción exacta del elemento de estructura B. 2. La velocidad de procesamiento es menor dado que la obtención del esqueleto morfológico es obtenido a través de una transformada rápida de distancia. En resumen, se obtuvo un método con los mismo resultados que los métodos propuestos en el Capítulo 3, pero más eficiente en tiempo de procesamiento, y la diferencia de velocidad se hace más notoria cuanto más píxeles tenga el elemento de estructura B. La complejidad del método propuesto en este trabajo se puede analizar desde dos perspectivas: 1. La complejidad es lineal respecto al número de uniones, i.e. lineal respecto al número de puntos del esqueleto morfológico. 2. La complejidad es lineal respecto al número de discos, i.e. número de veces que se aplica el método Díaz que proporciona algoritmos de tiempo constante (Algoritmo 3). De lo anterior se puede observar que el algoritmo propuesto en este trabajo presenta una complejidad lineal, a diferencia de los métodos presentados en el Capítulo 2, salvo el método Díaz y el método 2D-scan. No obstante lo anterior, este nuevo método presentado para realizar dilataciones (ó erosiones) con elementos de estructura arbitrario presenta la 50

ventaja de utilizar cualquier forma del elemento de estructura a diferencia de éstos dos últimos métodos. Las aplicaciones en las cuales se puede explotar la eficiencia de los Algoritmos 5 y 6 se dejan a consideración del amable lector y quedan fuera del contexto de este trabajo dado que el objetivo principal de esta tesis es encontrar una metodología que generalice operaciones morfológicas rápidas con elementos de estructura arbitrarios.

51

Capítulo 5 Discusiones experimentales Los experimentos realizados con el método propuesto en esta tesis, se implementaron en una computadora personal con un procesador Pentium 4 a una velocidad de 2GHz. El lenguaje de programación utilizado fue Borland C++. Todas las imágenes son binarias y de un tamaño de 200 × 200 píxeles. La medición del tiempo en éstos experimentos fue restringida a los clock ticks de la PC. De las Figuras 5.1 a 5.9 muestran las imágenes con las cuales se realizaron los experimentos; el elemento de estructura puede ser cualquiera de éstas imágenes según se especifique. Los resultados (ver Tablas 5.1-5.4) muestran que para el tiempo de procesamiento del Algoritmo 5 cuando se utiliza la métrica d6R ó d6L es la que proporciona resultados de menor tiempo junto con el d4 , según la forma de la imagen, d8 es el más lento; pese a lo anterior, vemos que la diferencia entre estas métricas usando el Algoritmo 5 es mínima. Dado que el método Díaz ([6]), es el algoritmo más rápido para realizar operaciones morfológicas, es evidente que el Algoritmo 5 es el método más rápido para operaciones morfológicas con elementos de estructura arbitrario; en las tablas de resultados, se muestra el tiempo de procesamiento para el método trivial e incluso se muestra un método de BitBlt, el cual es una optimización del procesador y aún así es claro que es más eficiente el método propuesto es esta tesis. De la discusión anterior, es evidente que el Algoritmo 5 es más eficiente en comparación con los métodos discutidos en el Capítulo 3 cuando el elemento de estructura es más grueso. Cabe mencionar que para un elemento de estructura igual a un disco de radio i para cualquiera de las métricas básicas, el Algoritmo 5 se convierte en el Algoritmo Díaz (Algoritmo 3). Por último sólo se muestra el ejemplo para la operación de dilatación, ésto se justifica debido a que la operación dual de esta operación es la erosión y el tiempo de procesamiento es el mismo. También se sabe que a partir de la dilatación y la erosión se pueden formar otros operadores morfológicos utilizados para el procesamiento de imágenes binarias, por ejemplo filtros. De las Figuras 5.10 a 5.11 se muestran los resultados de los experimentos realizados (dilatación).

53

Figura 5.1: Imagen A.

Figura 5.2: Imagen B.

Figura 5.3: Imagen C.

Figura 5.4: Imagen D.

54

Figura 5.5: Imagen E.

Figura 5.6: Imagen F.

Figura 5.7: Imagen G.

Figura 5.8: Imagen H.

55

Figura 5.9: Imagen I.

Observación 1 En todas las imágenes utilizadas en los experimentos, se asume que el origen es la esquina superior izquierda, i.e. (0,0).

Métrica D4 0.531 seg.

Métrica D6R 0.625 seg.

Métrica D6L 0.5 seg.

Métrica D8 0.578 seg.

Método Trivial BitBlt 214.875 seg. 1.421 seg.

Tabla 5.1 Dilatación de la figura A con la figura G.

Métrica D4 0.485 seg.

Métrica D6R 0.578 seg.

Métrica D6L 0.469 seg.

Métrica D8 0.515 seg.

Método Trivial BitBlt 99.063 seg. 1.11 seg.

Tabla 5.2 Dilatación de la figura I con la figura E.

Métrica D4 0.484 seg.

Métrica D6R 0.515 seg.

Métrica D6L 0.437 seg.

Métrica D8 0.437 seg.

Método Trivial BitBlt 220.625 seg. 0.844 seg.

Tabla 5.3 Dilatación de la figura B con la figura F.

Métrica D4 0.468 seg.

Métrica D6R 0.547 seg.

Métrica D6L 0.437 seg.

Métrica D8 0.469 seg.

Método Trivial BitBlt 165.391 seg. 0.984 seg.

Tabla 5.4 Dilatación de la figura C con la figura H.

Métrica D4 0.531 seg.

Métrica D6R 0.625 seg.

Métrica D6L 0.516 seg.

Métrica D8 0.579 seg.

Método Trivial BitBlt 189.844 seg. 1.188 seg.

Tabla 5.5 Dilatación de la figura D con la figura D.

56

Figura 5.10: Dilatación de A con G.

Figura 5.11: Dilatación de I con E.

57

Figura 5.12: Dilatación de B con F.

Figura 5.13: Dilatación de C con H.

58

Figura 5.14: Dilatación de D con D.

Nótese que en los experimentos realizados, el elemento de estructura es del mismo tamaño que el conjunto a dilatar, esto se hace con la finalidad de mostrar la eficiencia del algoritmo (tiempo de procesamiento); sin embargo, esto en la práctica no es común, por lo regular el elemento de estructura es de menor tamaño respecto al conjunto a dilatar; a pesar de lo anterior, los Algoritmos 5 y 6 siguen siendo más eficientes que los presentados en el Capítulo 3.

59

Capítulo 6 Conclusiones y trabajo a futuro Un conjunto de resultados relacionados con el esqueleto morfológico, utilizando la transformada de distancia y la morfología matemática fueron, presentados en este trabajo. Ambos tópicos, como se vió, se encuentran fuertemente ligados entre sí. Estos resultados son válidos para una familia de espacios métricos. En general los resultados obtenidos tiene las siguientes características: 1. Todos los resultados son generales para una familia infinita de espacios métricos, la cual cubre todas las métricas que se aplican en el área de Visión por Computadora. 2. Dos tópicos que aparentemente no tiene conexión en el procesamiento de imágenes, resultaron estar fuertemente conectados (esqueleto morfológico y transformada de distancia). 3. Se desarrolló un nuevo algoritmo para operaciones morfológicas con elementos de estructura arbitrarios. 4. Los algoritmos desarrollados en este trabajo son eficientes en tiempo de procesamiento y muestran una complejidad mínima respecto a todos los algoritmos actuales. Como trabajo futuro, se pretenden desarrollar operaciones morfológicas con los esqueletos morfológicos de A y de B, i.e. S(A) y S(B), de la siguiente manera: Obtener los esqueletos morfológicos de A y de B. A partir de estos esqueletos morfológicos generar el esqueleto morfológico de A ⊕ B, i.e. S(A ⊕ B). Finalmente reconstruir A ⊕ B a partir de su esqueleto morfológico.

61

Bibliografía [1] Borgerfors G., Distance transformations in digital images, CVGIP, 34, 344-371, 1986. [2] Chaudhuri B., An efficient algorithm for running window pel gray level ranking in 2-D images, Pattern Recognition Letters, 11(2):77-80, February 1990. [3] Cuisenaire O. and Macq B., Fast Euclidean morphological operators using local distance transformation by propagation, IPA 99 - 7th Conference on Image Processing and its Applications, Manchester, July 12-15, 1999, Proceedings, pp. 856-860. [4] Danielsson P. E., Euclidean distance mapping, CGIP, 14, 227-248, 1980. [5] Díaz de León J. L., Algoritmos de esqueletización de imágenes digitales binarias, Tesis de maestría, CINVESTAV-IPN, México, 1993. [6] Díaz de León J. L., Morfología Matemática basada en espacios métricos de combinación lineal, Tesis doctoral, CINVESTAV-IPN, México, 1996. [7] Díaz de León J. L. and Sossa H., Mathematical Morphology on Linear Combined Metric Spaces on Z2 : Part I, Journal of Mathematical Imaging and Vision, Vol. 12, 2, pp. 137-154, 2000. [8] Díaz de León J. L. and Sossa H., Mathematical Morphology on Linear Combined Metric Spaces on Z2 : Part II, Journal of Mathematical Imaging and Vision, Vol. 12, 2, pp. 155-168, 2000. [9] Díaz de León J. L., Notas del curso de introducción a la morfología matemática de conjuntos, manuscrito sin publicar, CIC-IPN, México, D.F., 2003. [10] Díaz de León J. L. y Yáñez C., Introducción a la morfología matemática de conjuntos, Fondo de cultura económica, México, 2003, ISBN 970-36-0075-1. [11] Droogenbroeck M. V., Algorithms for openings of binary and label images with rectangular structuring elements, In: H. Talbot and R. Beare, Editors, Mathematical Morphology, pages 197-207. CSIRO Publishing, Sydney, Australia, April 2002. [12] Droogenbroeck M. V., On the implementation of morphological operations, In: J. Serra and P. Soille, Editors, Mathematical Morphology and its Applications to Image Processing, pages 241-248. Kluwer Academic Publishers, Dordrecht, 1994.

63

[13] Droogenbroeck M.V. and Talbot H., Fast Computation of morphological operations with arbitrary structuring elements, Pattern Recognition Letters, 17(14):1451-1460, 1996. [14] Eggers H., Euclidean distance transformation in Z2 based on sufficient propagation, CVIU, 69, 106-116, 1998. [15] Gil J. and Kimmel R., Efficient dilation, erosion, opening and closing algorithms, In: J. Goutsias, L. Vincent, and D. Bloomberg, Editors, Mathematical Morphology and its Applications to Image and Signal Processing V, pages 301-310, Palo-Alto, USA, June 2000. Kluwer Academic Publisher. [16] Groen F.C.A. and Foster N.J., A fast algorithm for Cellular Logic operations on sequential machines, Pattern Recognition Letters 2, 333-338, 1984. [17] Hadwiger H., Vorlesungen über Inhalt, Oberfläche und Isoperimetrie, Springer, Berlín, 1957. [18] Haralick R., Sternberg S. and Zhuang X., Image analysis using mathematical morphology, IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(4): 532-550, 1987. [19] Herk M.V., A fast algorithm for local minimum and maximum filters on rectangular and octagonal kernels, Pattern Recognition Letters, 13(7):517-521, July 1992. [20] Huang T., Yang G. and Tang C., A fast two-dimensional median filtering algorithm, IEEE Transactions on Acoustic, Speech and Signal Processing, 27(1):13-18, February 1979. [21] Juárez S., Esqueletos morfológicos continuos y discretos en el plano, Tesis de maestría, CINVESTAV-IPN, México, D.F., 2004. [22] Matheron G., Elements Pour une Tioree des Mulieux Poreux, Masson, París, 1965. [23] Matheron G., Random Sets and Integral Geometry, Wiley, New York (1975). [24] Minkowski H., Volumen und Oberfläche. Math. Ann. vol. 57, pp. 447-495. [25] Nacken P.F.M., Chamfer Metrics in Mathematical Morphology, Journal of Mathematical Imaging and Vision, 4, pp. 233-253, 1994. [26] Petch J., Speed up successive Minkowski operations, Pattern Recognition Letters, 3(2):113-117, 1985. [27] Piper J. and Granum E., Computing distance transformations in convex and no-convex domains, Pattern Recognition, 20, 599-615, 1987. [28] Ragnelmam I., Fast erosion and dilation by contour processing and thresholding of distance maps, Pattern Recognition Letters, 13, 161-166, 1992.

64

[29] Ragnelmam I., Neighborhoods for distance transformations using ordered propagation, CVGIP Image Understanding, 56, 399-409, 1992. [30] Rosen K., Discrete Mathematics and Its Applications, Mc Graw Hill, New York, 2003, ISBN 0-07-242434-6. [31] Rosenfeld A. and Pfaltz J.L., Distance Functions on Digital Pictures, Pattern Recognition, 1, pp. 33-61, 1968. [32] Schmmit M., Des algorithms morphologiques á l’intelligence artificielle, PhD thesis, École nationale supérieure des mines de Paris. February 1989. [33] Serra J., Image Analysis and Mathematical Morphology, Vol. 1, Academic Press, San Diego 1982. [34] Serra J., Image Analysis and Mathematical Morphology, Vol. 2, Academic Press, San Diego 1988. [35] Van Vliet J.L., Verwer B.J.H, A contour processing method for fast binary neighborhood operations, Pattern Recognition Letters, Vol. 7, No. 1, 1988, 27-36. [36] Verwer B.J.H., Verbeek P.W. and Dekker S.T., An efficient uniform cost algorithm applied to distance transformations, IEEE Trans. PAMI, 11, 425-429, 1989. [37] Vincent L., Morphological transformations of binary images with arbitrary structuring elements, Signal Processing, 22(1):3-23, January 1991.

65