Story Transcript
Tesis para optar por el título de Doctor en Ingeniería con orientación Electrónica
“DISTANCIAS NO-EUCLÍDEAS APLICADAS AL PROCESAMIENTO DE IMÁGENES MÉDICAS”
Lic. Juan Ignacio Pastore
Director: Dra. Emilce Moler Co-Director: Dra. Virginia Laura Ballarin.
FACULTAD DE INGENIERÍA UNIVERSIDAD NACIONAL DE MAR DEL PLATA CONICET
Índice Capítulo 1: Introducción
1-1
1.1 Motivación y presentación del problema 1.2 Objetivos de esta tesis 1.3 Estructura de la tesis
1-1 1-3 1-3
Capítulo 2: Segmentación de imágenes
2-1
2.1 Introducción 2.2 Antecedentes en segmentación de imágenes biomédicas 2.2.1 2.2.2 2.2.3 2.2.4
Segmentación manual Segmentación basada en procesamiento de imágenes Segmentación basada en reconocimiento de patrones Métodos Híbridos
2.3 Imágenes provenientes de TC. e IRM. 2.3.1 Imágenes de Tomografía Computada 2.3.2 Imágenes de Resonancia Magnética
2.4 Estado de la técnica y problemas abiertos
2-1 2-2 2-3 2-3 2-4 2-5 2-6 2-6 2-8 2-12
Capítulo 3: Preliminares Matemáticos
3-1
3.1 Elementos de la teoría de conjuntos
3.2.1 Elementos notables de un conjunto ordenado
3-1 3-1 3-2 3-3 3-4 3-5 3-6
3.2.2 Reticulados
3-7
3.2.3 Isomorfismo de Reticulados
3-7
3.1.1. Conjuntos 3.1.2. Operaciones con conjuntos 3.1.3. Relación de orden entre conjuntos 3.1.4. Funciones
3.2 Elementos de la teoría de reticulados
3.3. Nociones básicas de espacios topológicos 3.3.1. Espacios métricos 3.3.2. Espacios Topológicos
3-11
3.3.3. Topologías definidas en un conjunto
3-12
3.3.4. Propiedades Topológicas
3-13
Capítulo 4: Morfología Matemática 4.1. 4.2.
4-1
Introducción Principios de Morfología Matemática 4.2.1. Operadores Morfológicos básicos: Erosión y Dilatación 4.2.2. Morfología Matemática en Niveles de Gris
4.3.
3-8 3-8
Morfología Matemática: Geodésica
i
4-1 4-2 4-2 4-10 4-17
4.3.1. Operadores Morfológicos Geodésicos 4.3.2. Aplicaciones de la reconstrucción geodésica
Capítulo 5: Extracción de componentes conectadas: método propuesto
4-17 4-22 5-1
5.1.
Algoritmo general para extraer componentes conectadas de una imagen
5-2
5.2.
Aplicación del método propuesto
5-4
Capítulo 6: Validación de la segmentación: un nuevo índice de similitud
6-1
6.1. 6.2. 6.3.
6-1 6-7 6-8 6-8 6-9
Medidas de similitud Índice de similitud propuesto Imágenes de prueba 6.3.1. Imágenes de prueba provenientes de simulaciones 6.3.2. Imágenes de prueba reales
Capítulo 7: Resultados
7-1
7.1.
7-1
Resultados obtenidos en imágenes simuladas
7.1.1. Imágenes simuladas sin distorsión 7-1 7.1.2. Imágenes simuladas con ruido y distorsión por inhomogeniedades de campo magnético 7-3
7.2. 7.3.
Resultados obtenidos en imágenes reales Discusión
7-7 7-9
Capítulo 8: Conclusiones
8-1
Capítulo 9: Bibliografía
9-1
ii
PUBLICACIONES QUE DIERON ORIGEN A ESTA TESIS
Esta tesis se enmarca dentro de los proyectos de investigación (15G166) “CLASIFICACIÓN Y SEGMENTACIÓN EN IMÁGENES BIOMÉDICAS” y (15G209) “PROCESAMIENTO DE IMÁGENES BIOMÉDICAS” desarrollados en el Laboratorio de Procesos y Mediciones de Señales, dependiente del Departamento de Electrónica de la Facultad de Ingeniería de la Universidad Nacional de Mar del Plata y se fundamenta en las siguientes publicaciones desarrolladas con anterioridad a la escritura de esta tesis: 1.
Segmentación de biopsias de médula ósea mediante filtros morfológicos y regiones homogéneas, Pastore, Juan Ignacio, Moler Emilce, Meschino Gustavo. Publicado en la Revista Brasileira de Engenharia Biomédica v. 21, n. 1, p. 81-88. © SBEB Sociedade Brasileira de Engenharia Biomédica. ISSN 1517-3151. Abril 2005.
2.
Segmentation of brain magnetic resonance images through morphological operators and geodesic distancea, Pastore, Juan Ignacio; Moler Emilce; Ballarin Virginia. Publicado en Digital Signal Processing Vol. 15/2 pp. 2005. 153-160. ISSN 10512004.
3.
Topological Concepts applied to Digital Image Processing, Pastore, Juan Ignacio, Bouchet, Agustina, Moler Emilce, Ballarin Virginia. Publicado. Publicado en el Journal of Computer Science and Technology, JCS&T Vol 6 No.2 pag. 80-84. Octubre de 2006. ISSN 1666-6038.
4.
Operadores Morfológicos Multiescala y Distancia Geodésica Aplicados a la Segmentación de Imágenes de Tomografía Axial Computada, Pastore, Juan Ignacio, Moler, Emilce, Ballarin, Virginia. Publicado en la revista IEEE America Latina. Volumen 5. Issue:1. Marzo de 2007. ISSN: 1548-0992.
5.
Segmentation of Medical Images using Fuzzy Mathematical Morphology, Bouchet A., Pastore Juan Ignacio, Ballarin, Virginia. Aceptado para su publicación en Journal of Computer Science and Technology. JCS&T Vol. 7 No. 3. pp 256-262. October de 2007.ISSN 1666-6038.
6.
Quantification of the efficiency of segmentation methods on medical images by means of non-euclidean distances. Pastore, Juan Ignacio, Ballarin, Virginia, Moler, Emilce. Aceptado para su publicación en el Journal of Physics Conference Series. Septiembre de 2007. ISSN 1742-6588 (Print), ISSN 1742-6596 (Online).
7.
Reconstrucción Geodésica de Imágenes a través de Componentes Conectadas, Bouchet, Agustina, Pastore, Juan Ignacio, Moler, Emilce. Publicado en la revista IEEE America Latina, Agosto de 2008. ISSN: 1548-0992.
8.
Procesamiento Digital de Imágenes a través de Filtros Morfológicos Direccionales, Pastore, Juan Ignacio, Moler, Emilce, Ballarin, Virginia. Publicado en la Revista Argentina de Bioingeniería de la Sociedad Argentina de Bioingeniería. Mayo de 2008. ISSN 0329-5257.
i
PUBLICACIONES QUE DIERON ORIGEN A ESTA TESIS
Así también, parte de las investigaciones incluidas en esta tesis fueron presentadas en diferentes reuniones científicas, con referato: 1. Segmentación morfológica de partículas mediante técnicas iterativas de esqueletos por zonas de influencia, E. Moler, V. Ballarin, J. Rodriguez, J. Pastore. Presentado en la IX Reunión de Trabajo en Procesamiento de Información y Control (IX RPIC 2001), organizado por la Universidad Nacional del Litoral, la Asociación Argentina de Control automático, IEEE Argentina, IEEE Control System Society y el Centro Regional de Investigación y Desarrollo de Santa Fe. Santa Fe. Septiembre de 2001. 2. Cuantificación de células adiposas mediante técnicas de watershed con marcadores, E. Moler, U. Zanetto, J. Pastore, J. Rodriguez. Presentado en el XIII Congreso Argentino de Bioingeniería - II Jornadas de Ingeniería Clínica, organizado por la Sociedad Argentina de Bioingeniería conjuntamente con el Departamento de Bioingeniería de la Facultad de Ciencias Exactas y Tecnología. Universidad Nacional de Tucumán. Tucumán. Septiembre de 2001. 3. Segmentación morfológica de biopsias de médula ósea mediante filtros secuenciales alternativos, J. Pastore, M. Meschino, E. Moler. Presentado en el XIV Congreso Argentino de Bioingeniería - III Jornadas de Ingeniería Clínica, organizado por la Sociedad Argentina de Bioingeniería. Córdoba. Argentina. Octubre de 2003. 4. Detección de vasos sanguíneos mediante operadores de reconstrucción morfológica, E. Moler, J. Pastore, A. Bouchet. Presentado en el XIV Congreso Argentino de BioingenieríaIII Jornadas de Ingeniería Clínica, organizado por la Sociedad Argentina de Bioingeniería. Córdoba. Argentina. Octubre de 2003. 5. Segmentación de imágenes a través de reconstrucción morfológica en niveles de gris, E. Moler, J. Pastore, A. Bouchet. Presentado en el IX Congreso Argentino de Ciencias de la Computación (CACIC 2003), organizado por la Facultad de Informática de la Universidad Nacional de La Plata. La Plata. Argentina. Octubre de 2003 6. Segmentación de Imágenes de Resonancia Magnética de cerebros a través de Operadores Morfológicos y Distancia Geodésica, Pastore, Moler y Ballarin, presentado en el X Congreo Argentino de Ciencias de la Computación CACIC 2004, organizado por la Universidad Nacional de la Matanza. La Matanza, Provincia de Buenos Aires. Octubre 2004. 7. Segmentación de Imágenes a través de Morfología Matemática Difusa, A. Bouchet, J. Pastore, V. Ballarin, Reunión de Procesamiento de la Información y Control (XI RPIC). Universidad Nacional de Río IV. Córdoba. Septiembre de 2005. 8. Aplicación de Operadores Morfológicos Multiescala y Distancia Geodésica a la Segmentación de Imágenes de Tomografía Axial Computada, J. Pastore, V. Ballarin, E. Moler, XV Congreso Argentino de Bioingeniería- IV Jornadas de Ingeniería Clínica (SABI 2005), organizado por la Sociedad Argentina de Bioingeniería conjuntamente con la Facultad de Ingeniería de la Universidad Nacional de Entre Ríos. Entre Ríos. Septiembre de 2005.
ii
PUBLICACIONES QUE DIERON ORIGEN A ESTA TESIS
9. Aplicación de la Teoría De Clases Conectadas para Segmentación de Imágenes Digitales, Bouchet A., Pastore J., Ballarin V. y Dra. Moler E., III Congreso Internacional de Matemática Aplicada a la Ingeniería y Enseñanza de la Matemática en Ingeniería, Universidad de Buenos Aires. Buenos Aires, Argentina. Octubre 2005. 10. Las componentes conectadas como herramienta para la reconstrucción de imágenes, Agustina Bouchet, Juan I. Pastore, Emilce G. Moler, Asociación Argentina de control automático (ADECA 2006). Buenos Aires. Argentina Agosto de 2006. 11. Digital Image Processing through a Morphological Power Spectrum, Blotta, E., Pastore, J., Ballarin, V., Rabal, H. XV Conference on Nonequilibrium Statistical Mechanics and Nonlinear Physics. Mar del Plata. Argentina. Diciembre de 2006. 12. Cuantificación de la Eficiencia de Métodos de Segmentación en Imágenes Médicas Mediante Distancias No-Euclideanas, Pastore J., Ballarin V., Moler E. XVI Congreso Argentino de Bioingeniería - V Jornadas de Ingeniería Clínica (SABI 2007), organizado por La Regional Cuyo de la Sociedad Argentina de Bioingeniería y el Gabinete de Tecnología Médica de la Facultad de Ingeniería de la Universidad Nacional de San Juan. San Juan. Argentina. Septiembre de 2007. ISBN: 978-950-605-505-9.
iii
1. Introducción
1. Introducción 1.1. Motivación y presentación del problema La sociedad actual es producto, en gran medida, de las transformaciones producidas por las Tecnologías de la Información y las Comunicaciones, algo difícil de imaginar hace tan sólo un par de décadas atrás. Estas transformaciones han influido, tanto directa como indirectamente, en las múltiples áreas de la ciencia y el conocimiento. Un área en la que este desarrollo tecnológico ha tenido especial relevancia es la salud, en particular, el diagnóstico por imagen ha sido uno de los grandes beneficiados por estos desarrollos, permitiendo el avance de técnicas cada vez más sofisticadas para la obtención y análisis de datos de interés clínico. Las imágenes médicas han revolucionado el diagnóstico de muchas enfermedades desde su inicio. A finales del siglo XIX, el físico alemán Wilhelm C. Roentgen, descubrió que los rayos X podían penetrar objetos opacos y proporcionar una imagen de su estructura interna, desde entonces, ésta ha sido la herramienta más importante ya que es utilizada ampliamente en medicina clínica, tanto como instrumento de diagnóstico como con propósitos terapéuticos. En la actualidad existen numerosas modalidades de imágenes médicas como las obtenidas por Tomografía Computada (TC), Resonancia Magnética (RM), Tomografía por Emisión de Positrones (PET), entre otras modalidades (Marshall et al., 2006). La variabilidad de estas imágenes se debe a los diferentes parámetros de adquisición, el alto contenido de ruido y textura que poseen, los diversos campos de estudio y los diversos tipos de patologías que se presentan (Krestel, 1990). Estas imágenes juegan un rol prominente en el diagnóstico y tratamiento de enfermedades, debido a que permiten que los especialistas obtengan información vital observando el interior del cuerpo humano de una forma no invasiva, incrementando enormemente el conocimiento de patologías y anatomías para la investigación médica. Además son un componente crítico en la planificación de diagnósticos y tratamientos.
1-1
CAPITULO 1
INTRODUCCIÓN
Con el incremento en tamaño y número de este tipo de imágenes se ha hecho indispensable el uso de la computadora como herramienta para facilitar el procesamiento y análisis de las mismas. En particular, la habilidad de detectar estructuras con características determinadas dentro de una imagen constituye un aspecto fundamental para la automatización de diverso tipo de aplicaciones. Este tipo de procedimiento, conocido como segmentación de imágenes, permite la descomposición de una imagen en regiones significativas, según cada aplicación particular (Pastore J., et al. 2007). Si bien existen numerosos métodos de segmentación de imágenes biomédicas, siguen surgiendo nuevas técnicas año tras año dejando en evidencia que aún no existen soluciones definitivas ni algoritmos generales, por lo que la segmentación de imágenes constituye un campo de continua investigación. Algunos de estos sistemas utilizan una delimitación minuciosa por parte de un observador experimentado de los objetos presentes en la imagen. Este tipo de procedimiento es denominado comúnmente segmentación manual. Esta práctica constituye una tarea tediosa y poco repetible, además de ser propensa a errores. Por este motivo el desarrollo de métodos de segmentación que sean independientes de la intervención del usuario contribuye sustancialmente a la precisión de la segmentación de imágenes médicas. Estos métodos se denominan automáticos y el objetivo fundamental es facilitar el uso rutinario por parte del usuario entrenado y no entrenado, evitando disparidad de criterios. Sin embargo la presencia de ruido, los cambios graduales de intensidad o la similitud de intensidades entre diferentes estructuras anatómicas provoca que esta tarea no resulte sencilla, siendo muchas veces imposible. Es por esto que la alternativa más utilizada es la segmentación semi-automática donde se requiere una intervención mínima por parte del experto. Usualmente, en este caso se le presenta al usuario experimentado en forma automática una primera segmentación y se le permite mejorar la exactitud de la misma modificando los parámetros del algoritmo si la segmentación presentada no es la esperada. El desarrollo de métodos automáticos de segmentación tiene el potencial de reducir sustancialmente el tiempo insumido por algunos procedimientos médicos, los que así podrían llevarse a cabo con mayor efectividad, mas precisión y menor riesgo.
1-2
CAPITULO 1
INTRODUCCIÓN
En consecuencia, puede afirmarse que la tarea de analizar imágenes médicas es compleja y dificultosa tanto para los especialistas como para los métodos de análisis de Procesamiento Digital de Imágenes (PDI). Es por ello que los esfuerzos abocados al procesamiento y posterior cuantificación de estas imágenes surgen de una amplia variedad de aplicaciones. El Procesamiento Digital de Imágenes se aplica con el fin de evitar la ambigüedad de los diferentes criterios utilizados por los especialistas y disminuir los tiempos de las evaluaciones.
1.2. Objetivos de esta tesis El objetivo de esta tesis es desarrollar una técnica robusta para la segmentación de imágenes biomédicas utilizando distancias no euclídeas que sea aplicable en un amplio espectro de situaciones clínicas reales. Como así también presentar un nuevo índice de similitud para comparar la eficiencia de la técnica de segmentación propuesta. En este sentido, los objetivos específicos de la tesis son los siguientes: • Evaluar una técnica de filtrado que sea robusta al ruido inherente de las imágenes biomédicas. • Diseñar, desarrollar y evaluar una técnica robusta de segmentación de imágenes de RM y TAC con distancias no euclídeas. • Presentar un nuevo índice de similitud ( H _ DS α ), que combina una medida de similitud espacial a través de la métrica de Hausdorff y la diferencia de las áreas de los contornos comparados utilizando la diferencia simétrica entre conjuntos.
1.3. Estructura de la tesis A continuación, se describe la estructura y los contenidos principales de cada capítulo. En el capítulo 2, se analiza tanto el estado actual de las técnicas de segmentación de imágenes como así también los problemas existentes en dicho campo. Además, se explican los conceptos básicos de la Tomografía Computada y Resonancia Magnética
1-3
CAPITULO 1
INTRODUCCIÓN
Nuclear que permitirán comprender las características de las imágenes multiespectrales que se utilizarán a lo largo del trabajo. En el capítulo 3, se presentan conceptos relacionados a la Teoría de Conjuntos, Teoría de Reticulados y nociones generales de Espacios Métricos y Topológicos. La intención de este capítulo es reunir los elementos básicos utilizados a lo largo del texto con el objetivo de proporcionar una referencia rápida e introducir las nociones y nomenclatura utilizadas. En el capítulo 4 se presentan las nociones básicas y resultados de la Morfología Matemática para imágenes binarias y con niveles de gris, como así también los operadores geodésicos, destacándose los filtros secuenciales alternados y la operación reconstrucción. En el capítulo 5 se introduce el nuevo algoritmo de segmentación propuesto como alternativa a los ya existentes.
En el capítulo 6 un nuevo índice de similitud es propuesto para cuantificar la eficiencia y robustez del método de segmentación presentado en esta tesis, tanto en imágenes reales como en imágenes provenientes de simulaciones. En el capítulo 7, se presentan los resultados obtenidos en imágenes simuladas e imágenes reales. Finalmente en el capítulo 8 se presentan las conclusiones y se discuten algunos posibles trabajos a futuro.
1-4
2. Segmentación de Imágenes
2. Segmentación de imágenes. 2.1. Introducción La habilidad de detectar objetos con características determinadas dentro de una imagen constituye un aspecto fundamental para la automatización de diverso tipo de aplicaciones. Este tipo de procedimientos, conocidos como segmentación de imágenes, permiten la descomposición de una imagen en regiones de interés, según cada aplicación específica (Pham et al., 2000). Esta etapa es de suma importancia en cualquier sistema automatizado de visión, ya que es el primer nivel de la tarea de entendimiento de la imagen y afecta severamente al proceso posterior de interpretación de la imagen, proporcionando estructuras útiles tales como regiones y bordes. La segmentación de imágenes tiene su origen en numerosos estudios psicológicos que indican la preferencia de los seres humanos por agrupar regiones visuales en términos de proximidad, similitud y continuidad, para construir un conjunto de unidades significativas (Geman, S., et al., 1984). En cuanto a la unidad significativa que rige la segmentación de imágenes suele corresponder a píxeles, regiones o contornos que muestran o disciernen una similitud en cuanto a intensidad, color, textura, gradiente local, movimiento, etc. La operación de segmentar una imagen para el cerebro humano es tan automática y veloz que pocas veces es posible darse cuenta de su complejidad. Esta complejidad se percibe cuando se intenta reproducir el proceso de segmentación por medio de una computadora. Desafortunadamente, realizar esta separación automática en regiones por medio de algoritmos no es nada fácil y los criterios de agrupamiento varían de un problema a otro, sin haberse logrado aún, imitar la capacidad visual de los seres humanos. Los expertos, especialistas en el dominio de la aplicación, son capaces de analizar una imagen y reconocer un objeto con mayor facilidad que un algoritmo diseñado para tal fin. La mayor limitación de los algoritmos es la dificultad de transformar el conocimiento global en operaciones locales computacionales. Sin embargo, la ventaja de los algoritmos computacionales radica en que son capaces de reproducir resultados y eliminar discrepancias, dos aspectos sumamente importantes en medicina donde existe 2-1
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
la necesidad entre especialistas de reproducir resultados y eliminar las discrepancias que conllevan a diferencias en los diagnósticos y pronósticos.
2.2 Antecedentes en segmentación de imágenes biomédicas. Las imágenes médicas son utilizadas cotidianamente en rutinas clínicas para establecer un diagnóstico y escoger o controlar una acción terapéutica. Estas imágenes provienen principalmente de Tomografía Computarizada (TC), Resonancia Magnética (RM), Radiografía Computarizada (RC), exámenes de medicina nuclear (SPECT, PET) y Ultrasonido (US), entre otras. A pesar de que estas imágenes brindan información sobre la morfología y el funcionamiento de los órganos, su interpretación objetiva y cuantitativa es una tarea aún difícil de realizar. Este aspecto ha llevado a la comunidad de análisis de imágenes, un dominio multidisciplinario, a involucrarse en el desafiante problema de extraer, con ayuda de la computadora, información clínica útil acerca de estructuras anatómicas de las imágenes a fin de construir nuevas herramientas de ayuda al diagnóstico, planeación y seguimiento terapéutico. Una de las tareas más importantes en el análisis de imágenes biomédicas es la segmentación, donde se busca una partición de la imagen de manera tal que las regiones obtenidas correspondan a distintas estructuras anatómicas o regiones de interés. Una segmentación precisa es requisito indispensable para una gran cantidad de aplicaciones, como el cálculo de volúmenes de ciertos tejidos y su posterior rendering tridimensional, terapia de radiación, planes de cirugía, detección de tejidos anormales, etc. Una vez realizada la segmentación, la información puede ser usada por los especialistas para comparar volúmenes, morfologías y características de los tejidos con estudios normales u otras regiones en la misma imagen. Así pueden determinarse parámetros de normalidad con la idea de detectar patologías y asistir a las decisiones en diagnóstico y terapia (Moler, 2003, Courchesne et al., 2000). En los últimos años se ha trabajado mucho en la automatización de la segmentación de imágenes biomédicas, sin embargo, aunque la mayoría de los métodos desarrollados proporcionan soluciones para algunos pasos del análisis cuantitativo, muchos no pueden ser utilizados en la práctica porque no tienen en cuenta aspectos importantes como:
2-2
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
a) La existencia de distintos objetos que tienen o pueden tener brillos similares. La ausencia de valores absolutos en las unidades de intensidad. b) La presencia de determinados ruidos asociados a cada tecnología en la formación de las imágenes. A pesar de esto, cada nuevo resultado constituye un pequeño paso hacia la evolución de la práctica de la medicina. Los métodos propuestos en la literatura para dar solución al problema de la segmentación son muy variados dado que no hay una metodología que pueda ser aplicada a cualquier tipo de escena. No obstante, éstos pueden ser agrupados, a groso modo, en cuatro clases (Skarbek y Koschan 1994, González y Woods 1996, Jianping et al. 2001, Betancur 2002). 2.2.1
SEGMENTACIÓN MANUAL
Las segmentaciones así obtenidas se basan en la selección, por parte de un experto, de los píxeles que pertenecen al objeto de interés de forma interactiva, seleccionando píxel por píxel o bien usando herramientas semiautomáticas. Esta segmentación suelen ser subjetiva, dependiente del operador, y los resultados obtenidos no son siempre repetibles. De todas maneras, una adecuada segmentación manual realizada por especialistas es una tarea necesaria para la evaluación de los métodos de clasificación automáticos o semiautomáticos para utilizarla como referencia o “gold standard”. 2.2.2
SEGMENTACIÓN BASADA EN PROCESAMIENTO DE IMÁGENES
Técnicas de umbralamiento (thresholding). Utilizan generalmente la información del histograma (Sahoo et al., 1988). Su resultado es satisfactorio sólo si el histograma es bimodal. A pesar de que esta técnica es de fácil implementación, depende fuertemente de la elección del umbral (threshold). No existen en la bibliografía trabajos que den cuenta de la aplicación directa de este método en la segmentación de imágenes biomédicas debido a las limitaciones que conlleva la superposición de intensidades de grises que corresponden a distintas estructuras anatómicas.
2-3
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
Métodos basados en contornos. Utilizan como hipótesis que las regiones en una imagen son suficientemente homogéneas y por lo tanto la transición entre ellas puede ser determinada sólo por las discontinuidades en los niveles de gris (Palmer, Dabis y Kittler 1996). Entre los detectores de contornos más sencillos se pueden mencionar Sobel, Prewitt, Gradiente o Laplaciano. Todos ellos tienen como objetivo seleccionar aquellos píxeles de la imagen que delimitan la frontera del objeto de interés. El sustento matemático de la mayoría de las técnicas de detección de bordes es el cálculo de un operador local derivativo. Otra técnica que se puede incluir dentro de este grupo es el seguimiento de contornos. Esta técnica agrupa a una cadena de puntos en la imagen que tienen propiedades comunes, de modo que las regiones que son separadas por esta colección de puntos tengan un cambio significante en esas propiedades. Los puntos seleccionados de ésta constituyen el contorno de una región (Saghri J.A., and Freeman H., 1981).
Métodos basados en regiones. Se sustentan en la hipótesis según la cual los píxeles que pertenecen a una misma región tienen características visuales similares (textura, color, forma, etc.). Se destacan la técnica de división y unión (split and merge) y la de Crecimiento de Regiones (region growing) a partir de semillas. La técnica de crecimiento de regiones es una técnica para extraer regiones de la imagen que están conectadas según un criterio definido. Requiere de un valor inicial, denominado semilla (seed point), elegido manualmente. A partir de allí se establece una propiedad para determinar el conjunto de píxeles que cumplen dicha propiedad y se va etiquetando (labeling) hasta que se alcanza el contorno del objeto a identificar (Fan et al., 2005). Se han utilizado estos algoritmos en IRM para segmentar regiones de tumores, vasos sanguíneos, ventrículos o diferentes partes anatómicas, pero no resultan métodos adecuados cuando se trata de identificar diferentes tejidos (Chulho and Dong Hun, 2007).
2.2.3
SEGMENTACIÓN BASADA EN RECONOCIMIENTO DE PATRONES
Un paradigma muy utilizado para la segmentación consiste en el agrupamiento o clasificación de los píxeles mediante diversas técnicas. Los píxeles quedan caracterizados por vectores numéricos que los identifican con algún criterio, siendo sus componentes los
2-4
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
denominados característicos o descriptores. Estos vectores ingresan al algoritmo de clasificación. Los característicos, también denominados descriptores, se extraen de las imágenes a segmentar. La selección de un buen conjunto de descriptores es una etapa clave en cualquier proceso de clasificación, en este caso para lograr una segmentación adecuada. 2.2.4
MODELOS HÍBRIDOS
La combinación de dos o más técnicas da lugar a los denominados “modelos híbridos”, de gran aplicación en diversos campos y en particular en la segmentación de imágenes (Castellanos y Mitra, 2000). El método de segmentación que se presenta en esta tesis se puede ubicar dentro de esta última clasificación ya que se basa en la integración de un Filtrado Morfológico y un posterior criterio de etiquetado de regiones aplicando distancia geodésica, el cuál puede evolucionar adaptándose a la topología de los objetos presentes en la imagen. Esta integración plantea un enfoque interesante de segmentación, ya que combina la robustez de los filtros morfológicos con nociones básicas de la topología general. Debido a las características de las imágenes de RM y TAC, imágenes para las cuales se diseñó el método de segmentación propuesto en este trabajo, se decidió estudiar distancias no euclídeas que permitan una mejor caracterización de la topología de los objetos presentes en las mismas. Estas imágenes están compuestas por objetos con una amplia variabilidad de formas, tamaños, intensidades y textura y en general poseen una baja relación señal a ruido y bajo contraste. Propiedades que no se mantienen uniformes siquiera en el interior de un mismo objeto. Estas características evitan su correcto y eficiente procesamiento mediante técnicas que emplean la distancia euclidiana ya que éstos consideran a la imagen como un conjunto indivisible debido a que esta distancia ignora bordes, convexidad, y todo tipo de estructuras topológicas presentes en la misma a la hora de caracterizarlas. La utilización de distancias no euclídeas, como la distancia geodésica, permite una mejora en la caracterización tanto de la imagen en su conjunto como en una región específica de la misma. En la siguiente sección se presenta una breve descripción de la formación de las imágenes provenientes de RM y TC para comprender las características de las imágenes multiespectrales en las que se aplicará el método de segmentación propuesto. Para una
2-5
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
completa descripción de la técnica se recomienda los trabajos de Slichter (Slichter, 1996) y Callaghan (Callaghan, 1995). Los exámenes provenientes de este tipo de tecnologías poseen diferente rendimiento en función de lo que se quiere estudiar y de la hipótesis diagnóstica. No obstante, en muchas situaciones clínicas su indicación no es excluyente, sino que más bien actúan como métodos de estudio complementarios. La RM está basada en principios físicos totalmente diferentes de los de la TAC; la RM coincide con la TAC en que una energía es radiada dentro del paciente, pero presentan una diferencia fundamental a la hora de detectar la energía que produce la imagen: en la TAC la energía detectada es la remanente que el paciente no ha absorbido; mientras que en la RM esa energía se detecta al emerger del propio paciente (Liang et al., 2000). En el caso de la RM la energía radiada consiste en ondas de radiofrecuencia en lugar de rayos X como ocurre en la TAC. Al igual que en la TAC, la energía detectada a la salida se correlaciona con varios parámetros característicos del tejido. La gran ventaja de la RM es que es capaz de diferenciar tejidos con densidades muy próximas entre sí o incluso similares (densidades radiológicas) si su composición es distinta. Ello la hace muy superior a otros métodos de imagen, sobre todo en el estudio del sistema nervioso central y del sistema musculoesquelético, donde prácticamente todos las densidades -salvo el hueso- están comprendidas entre la grasa y el agua. Además, la capacidad para diferenciar tantos tejidos permite obtener imágenes con un detalle anatómico excepcional y en cualquier plano del espacio.
2.3 Imágenes provenientes de TC. e IRM. 2.3.1 Imágenes de Tomografía Computada La tomografía computarizada (TC) es tal vez la técnica más sofisticada en la aplicación de los rayos X en medicina. La palabra tomografía proviene del griego tomos que significa corte o sección y grafía que significa representación gráfica. La técnica de TC trata de producir un mapa bidimensional de los coeficientes de atenuación lineal de un cuerpo tridimensional, a partir de un número muy grande de medidas de transmisión, llamadas proyecciones. En términos prácticos, este mapa bidimensional corresponde a una imagen transversal del paciente. Si un conjunto de mapas bidimensionales son
2-6
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
ensamblados, uno detrás del otro, puede obtenerse una imagen tridimensional que punto a punto da información sobre los coeficientes de atenuación lineal del paciente, es decir, da información sobre su anatomía. Los algoritmos matemáticos para la reconstrucción de imágenes tomográficas a partir de sus proyecciones fueron desarrollados por el físico alemán J. Radon en 1917 (Radon 1917). Sin embargo, su aplicación en medicina no pudo ser posible sino hasta principios de los años 70, cuando el primer dispositivo de TC fue puesto en práctica clínica por el científico británico G.N. Hounsfield (Hounsfield 1973).
Figura. 1 Esquema de adquisición de datos en T.A.C.
Las proyecciones se obtienen irradiando al paciente con un haz de rayos X y midiendo la intensidad de la radiación transmitida con un arreglo de detectores, cada uno de los cuales consiste normalmente de un cristal centellador (por ejemplo NaI o CsI) acoplado a un fotodiodo. Tanto el tubo de rayos X como el detector deben rotar (y a veces también ser trasladados) alrededor del paciente. La figura 1 muestra esquemáticamente como se forma una proyección suponiendo una geometría sencilla en la adquisición de datos. En este ejemplo, la distribución de coeficientes de atenuación lineal está representada por la función (1) y corresponde a un solo plano del paciente. El sistema de coordenadas XY está centrado y fijo en el objeto mientras que X 'Y ' es un sistema que tiene el mismo origen y que rota un ángulo α alrededor del objeto. La intensidad del haz transmitido, I ( y ' , α ) , puede expresarse matemáticamente como:
{
}
I ( y ' , α ) = I 0 ( y ' , α ) exp − ∫∫ µ ( x, y ) k ( x, y, y ' , α ) dxdy
2-7
(2.1)
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
donde I 0 ( y ' , α ) es la intensidad del haz incidente. La integral se calcula a lo largo de una trayectoria definida por la función k ( x, y, y ' , α ) , que en el caso ideal es una línea recta. En el diagrama, esta trayectoria corresponde a la recta que une a la fuente de rayos X y al detector. Para cada ángulo α , se obtiene una ecuación de esta forma. Este conjunto de ecuaciones se puede resolver utilizando diferentes métodos matemáticos. El más común por su rapidez y facilidad de implementación es llamado retroproyección filtrada y utiliza métodos de Fourier.
Figura 2. Sección transversal del mediastino obtenida con tomografía axial computarizada
Los dispositivos de TC más modernos, pueden producir imágenes con diferencias en densidad de hasta el 0.5% y resoluciones espaciales de hasta 0.5 mm. La figura 2 muestra un ejemplo real del tipo de imágenes que se obtienen con la técnica de TC. Las imágenes de la TC permiten analizar las estructuras internas de las distintas partes del organismo, lo cual facilita el diagnóstico de fracturas, hemorragias internas, tumores o infecciones en los distintos órganos. Así mismo, permiten conocer la morfología de la médula espinal y de los discos intervertebrales (tumores o derrames en el canal medular, hernias discales, etc.), o medir la densidad ósea (osteoporosis). En determinados casos puede ser necesario utilizar contraste radiológico, que inyectado en el líquido cefalorraquídeo, en los vasos arteriales, etc., facilita el diagnóstico.
2.3.2 Imágenes de Resonancia Magnética El fenómeno de RM fue descubierto en 1946 independientemente por Felix Block en Stanford y por Edward Purcell en Harvard, por lo que fueron galardonados con el
2-8
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
Premio Nóbel de Física en 1952. Consiste en la posibilidad que tienen algunas partículas de absorber energía en forma de radiofrecuencia cuando la frecuencia de esta onda coincide con la frecuencia natural de precesión de dichas partículas. Esta característica puede utilizarse para excitar de forma selectiva el protón de los átomos de hidrógeno de un cuerpo y así poder recoger posteriormente su señal inducida en el proceso de relajación. Esta señal inducida puede utilizarse para obtener la distribución de estas partículas en el cuerpo (imagen de RM) o la concentración de distintas sustancias usando para ello su desplazamiento químico respecto a la frecuencia de resonancia o frecuencia de Larmor (espectro de RM). Entre 1950 y 1970 se desarrollaron las primeras aplicaciones de RM para análisis físico y químico de moléculas. En 1971 Raymond Damadian mostraba cómo los tiempos de relajación nuclear magnética de los tejidos normales y los tumores eran diferentes, lo que motivó la aplicación de la RM a la detección de enfermedades. En la década de los 70 se obtuvieron las primeras imágenes de RM. En líneas generales, el fenómeno de RM consiste en que determinados núcleos atómicos (por ejemplo, el del Hidrógeno) cuando se someten a la acción de un campo magnético estático B0 intenso pueden absorber energía selectivamente en forma de radiación electromagnética de radio-frecuencia (RF), (fenómeno de resonancia), que devuelven al retornar al estado de equilibrio, induciendo una señal eléctrica en una antena o bobina de recepción que analizada y procesada proporciona las imágenes de RM (IRM) o los espectros de RM (ERM). En la figura 3 se muestra un esquema de dicho proceso.
Figura 3. Esquema del proceso de obtención de imágenes y espectros de RM.
2-9
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
El análisis de las señales inducidas en la antena de recepción proporciona información sobre el contenido de los distintos elementos de volumen o vóxeles que forman el objeto de estudio. El vocablo anglicista vóxel proviene de la composición entre los términos volumen y píxel. Un vóxel es un elemento de volumen que contiene información gráfica asociada a un punto en un espacio tridimensional. Al igual que sucede con un píxel en un espacio con dos dimensiones, el vóxel es la mínima unidad de volumen que constituye un objeto en 3D. En una imagen de RM cada píxel de la imagen representa la información contenida en el vóxel al que representa.
Figura 4. Figura tridimensional constituida por unidades elementales de volumen o vóxels.
Existen distintos tipos de imágenes de RM según el fenómeno que domine en su formación. A estas adquisiciones diferenciadas se las denomina potenciaciones, y se consiguen mediante la aplicación de distintos pulsos de radiofrecuencia, gradientes de campo magnético y modificación de los parámetros de contraste, para potenciar o ponderar un determinado efecto a fin de maximizar el contraste entre tejidos específicos (figura 5). Las potenciaciones básicas son las siguientes: •
DP: Densidad Protónica. La intensidad del píxel de la imagen resultante es proporcional a la concentración de protones de hidrógeno del vóxel.
•
T1: Tiempo de relajación longitudinal. La intensidad del píxel de la imagen resultante es proporcional a la concentración de protones de hidrógeno y además depende del tiempo de relajación longitudinal propio de cada tejido.
•
T2: Tiempo de relajación transversal. La intensidad del píxel de la imagen resultante es proporcional a la concentración de protones de hidrógeno y depende del tiempo de relajación transversal propio de cada tejido.
2-10
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
Figura 5. De derecha a izquierda. Imágenes potenciadas en T1, DP y T2.
Las imágenes de RM presentan ruidos específicos propios a este tipo de técnica, entre los que se encuentran los comúnmente llamados artefactos. A continuación, se presentan algunos de los más frecuentes. Cuadratura. Se debe a problemas en el circuito de la antena de detección, específicamente por un mal funcionamiento de los canales del detector. Este artefacto es debido a un fallo del hardware y para solucionarlo el aparato debe ser revisado (figura 6). Inhomogeneidad. La inhomogeneidad de la imagen es una variación lenta de la intensidad a lo largo de la imagen, la causa puede ser una no uniformidad del campo de radiofrecuencia B1 o una no uniformidad de la sensibilidad de la antena de recepción entre otras razones. Algunas antenas, como las superficiales, tienen variaciones en su sensibilidad e incorporarán siempre este artefacto inherente a su diseño (figura 6 B)). Movimiento. El movimiento de los objetos dentro del campo de visión durante la adquisición de la imagen produce un emborronamiento y un efecto de imágenes fantasma (ecos en la imagen) en la dirección de la codificación de fase. La solución es inmovilizar al paciente tanto como sea posible. Los latidos del corazón o la respiración pueden producir movimiento en la imagen, en estos casos la solución es sincronizar la adquisición con dichos procesos. Aumentar el número de veces que se repite el experimento, o número de adquisiciones, minimiza este artefacto mediante el promediado de las señales. En la figura 6 C) se puede observar un artefacto de movimiento pulsátil causado por una vena. Volumen parcial. Es un artefacto causado por la resolución limitada del dispositivo de medida. Si el tamaño del vóxel es muy grande para el objeto, la mezcla de distintos 2-11
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
tejidos en un mismo vóxel produce un emborronamiento de las regiones límite entre tejidos. En el ejemplo de la figura 6 D) se puede observar la diferencia entre dos cortes del mismo cerebro con distintos espesores de corte (3mm y 10mm). Hay que tener en cuenta también que a menor tamaño de vóxel menor relación señal ruido (en inglés, Signal to Noise-Ratio, SNR).
Figura 6. Ejemplos de artefactos de RM. A) Artefacto de cuadratura. B) Ruido de inhomogeneidad. C) Artefacto de movimiento por pulsación de la vena sagital superior . D) Efecto de volumen parcial (obsérvese cómo cambian los contornos en función del tamaño del vóxel para cortes de 3 y de 10 mm de espesor).
2.4 Estado de la técnica y problemas abiertos Existen numerosos enfoques para dar solución al problema de la segmentación de imágenes y en particular de imágenes biomédicas. Sin embargo, el hecho de que siguen proponiéndose nuevos paradigmas indica que ninguno de ellos es autosuficiente ni ha solucionado el problema en su totalidad. Aunque la segmentación de imágenes biomédicas es uno de los campos donde más se ha trabajado en los últimos años, este sigue siendo un problema abierto y
2-12
CAPITULO 2
SEGMENTACIÓN DE IMÁGENES
numerosos grupos de investigación en el mundo continúan trabajando en la búsqueda de soluciones. Mientras tanto, cada nuevo resultado constituye un pequeño paso hacia la revolución de la práctica de la medicina. La complejidad del tema, unido a la diversidad de situaciones experimentales y clínicas, complica en gran medida el desarrollo de técnicas eficientes y robustas. Actualmente, es siempre necesaria la supervisón humana de los resultados producidos automáticamente. El porqué de esta situación se puede encontrar en la falta de técnicas robustas frente a alteraciones de las situaciones reales no esperadas o el uso de modelos que no se adaptan a la realidad. El desarrollo de métodos orientados a la patología puede reducir el margen de variación, haciendo el problema de la segmentación más abordable.
2-13
3. Preliminares Matemáticos
3. Preliminares Matemáticos Las definiciones y conceptos incluidos en este capítulo no pretenden esbozar toda la teoría, sino apenas presentar los elementos necesarios para abordar las siguientes subsecciones, y que el lector se familiarice con la notación utilizada a lo largo de esta tesis. Cabe destacar que no serán exhibidas las demostraciones de las propiedades y resultados citados pues éstas se encuentran en forma completa en las referencias citadas.
3.1 Elementos de la teoría de conjuntos En esta sección se presentan algunas definiciones y propiedades elementales de la teoría de conjuntos.
3.1.1 Conjuntos Un conjunto A es una colección de elementos de un determinado universo, generalmente denotado por U . Si un elemento x de U pertenece a A , se escribe x ∈ A , en caso contrario, se nota x ∉ A. Un conjunto vacío, denotado por ∅ , es un conjunto que no contiene ningún elemento. Un conjunto finito, es un conjunto con una cantidad finita de elementos. El cardinal de un conjunto A , denotado por A , corresponde al número de elementos pertenecientes a A . Dos conjuntos A y B son iguales si y solo sí todo elemento que pertenece a uno de ellos también pertenece al otro. Esto es, A = B ⇔ ( x ∈ A ⇔ x ∈ B, ∀x ) . Son diferentes, si y solo si existe al menos un elemento que pertenece a uno de ellos y no pertenece al otro. Esto es, A ≠ B ⇔ ( ∃ x ∈ A : x ∉ B o ∃ x ∈ B : x ∉ A) . Un conjunto A está contenido en otro conjunto B si y solo si todo elemento de A pertenece a B , esto es, A ⊆ B ⇔ ( x ∈ A ⇒ x ∈ B, ∀x ) . En este caso se dice que A es un subconjunto de B .
3-1
CAPITULO 3
PRELIMINARES MATEMÁTICOS
Un conjunto A está propiamente contenido en otro conjunto B si y solo sí A está contenido en B y A es diferente de B , esto es, A ⊂ B ⇔ ( A ⊂ B y A ≠ B) . En este caso se dice que A es un subconjunto propio de B . El conjunto de partes de un conjunto A , denotado por P ( A) , es el conjunto cuyos elementos son todos los subconjuntos de A , esto es, P ( A) = { X : X ⊂ A} . Se puede observar que ∅, A ⊂ P ( A) y si A = n entonces P ( A) = 2n .
3.1.2 Operaciones con conjuntos Complemento El complemento de un conjunto A , A ⊂ B , en relación al conjunto B es el conjunto de todos los elementos de B
que no pertenecen a
A . Esto es,
Ac = { x ∈ B : x ∉ A} . Cuando el conjunto B está claramente definido por el contexto o
cuando el complemento es en relación al conjunto universal U , se escribe simplemente Ac = { x : x ∉ A} .
Intersección de conjuntos La intersección de dos conjuntos A y B es el conjunto formado por todos los elementos que pertenecen simultáneamente a los dos conjuntos. Esto es, A ∩ B = { x : x ∈ A ∧ x ∈ B} .
La intersección de n conjuntos A1,…, An es el conjunto formado por todos los elementos
que
pertenecen
simultáneamente
a
los
n
conjuntos.
Esto
es,
n
∩ A = { x : x ∈ A ∀ i = 1,…, n} . i
i
i =1
Dos conjuntos A y B son disjuntos si y solo sí A ∩ B = ∅ . Unión de conjuntos
La Unión de dos conjuntos A y B es el conjunto formado por todos los elementos que pertenecen por lo menos a uno de los dos conjuntos. Esto es, A ∪ B = { x : x ∈ A ∨ x ∈ B} .
3-2
CAPITULO 3
PRELIMINARES MATEMÁTICOS
La unión de n conjuntos A1,…, An es el conjunto de los elementos que pertenecen al menos a uno de los n conjuntos. Esto es,
n
∪ A = { x : x ∈ A ∀ i = 1,…, n} . i
i
i =1
3.1.3 Relación de orden entre conjuntos. Relación entre conjuntos. Una relación ℜ de un conjunto A con un conjunto B es una terna ordenada ℜ = ( G, A, B) , donde G ⊆ A× B . Si ( x, y ) ∈G , se dice que el elemento x está relacionado
con el elemento y por la relación ℜ y se escribe x ℜ y . Si ( x, y ) ∉G entonces se escribe x ℜ y . Cuando A = B diremos simplemente que ℜ es una relación en A .
Relación de orden en un conjunto Dado un conjunto no vacío A , una relación binaria ≤ en A es llamada orden parcial si las siguientes propiedades se satisfacen para todo x, y, z ∈ A : I. x ≤ x
(Reflexiva);
II. x ≤ y e y ≤ x ⇒ x = y
(Anti-simétrica);
III. x ≤ y e y ≤ z ⇒ x ≤ z
(Transitiva).
Un conjunto A con un orden parcial ≤ es llamado un conjunto parcialmente ordenado o poset (del ingles “partially ordered set”) y es denotado por
( A, ≤ )
o
simplemente por A si no hay motivo de confusión. Conjunto totalmente ordenado
Se dice que un conjunto parcialmente ordenado ( A, ≤ ) es totalmente ordenado si x ≤ y o y ≤ x , para todo x, y ∈ A .
Si ≤ es un orden parcial en A , entonces la relación ≥ también define un orden parcial en A , llamado orden parcial dual. Si ordenado, entonces
( A, ≥ )
( A, ≤ )
es un conjunto parcialmente
también es un conjunto parcialmente ordenado llamado
conjunto parcialmente ordenado dual. Para toda definición, propiedad, proposición en
( A, ≤ )
existe una correspondiente dual en ( A, ≥ ) .
3-3
CAPITULO 3
PRELIMINARES MATEMÁTICOS
Una vez que un conjunto se ha dotado de una relación de orden, es posible explotar esta relación para extraer varios resultados interesantes. La teoría de reticulados (Birkhoff G., 1967, Szász G., 1963, Grätzer G., 1978) estudia exactamente las propiedades y resultados que se desprenden de conjuntos dotados con una relación de orden bien caracterizada. Intervalo cerrado.
Sea A un conjunto ordenado por la relación de orden ≤ y sea a, b ∈ A , a ≤ b . El conjunto [ a, b] = { x ∈ A : a ≤ x ≤ b} se denomina intervalo cerrado con extremo izquierdo a y extremo derecho b .
En el desarrollo de esta tesis se denotará al intervalo de números reales por [ a, b ] y el intervalo de números enteros como a, b o [ a,… , b ] .
3.1.4. Funciones Una función (Filho E., 1980) es una relación binaria f = ( F , A, B) , F ⊆ A× B si: I. ∀x ∈ A ∃ y ∈ B tal que ( x, y ) ∈ F , II.
( x, y1 ) ∈ F
y ( x, y2 ) ∈ F ⇒ y1 = y2 ∀x .
Una función f de A en B es indicada por f : A → B . Para cada elemento x ∈ A , el único elemento y ∈ B tal que ( x, y ) ∈ F es denominado la imagen de x por la función f y el valor de la función f en el elemento x es denotado por f ( x) .
Los conjuntos A y B son respectivamente el dominio y codominio de la función f . La imagen de la función f es el conjunto formado por todos los elementos que son
imágenes de elementos de A . El conjunto de todas las funciones de A en B se indica BA .
Función inyectiva
Una función f : A → B es inyectiva si y solo sí dados dos elementos distintos cualesquiera de A sus imágenes también son distintas en B ,esto es: ∀x1, x2 ∈ A, x1 ≠ x2 ⇒ f ( x1 ) ≠ f ( x2 ).
3-4
CAPITULO 3
PRELIMINARES MATEMÁTICOS
Función suryectiva
Una función f : A → B es suryectiva si y solo sí para todo y ∈ B existe x ∈ A tal que f ( x) = y , esto es: ∀y ∈ B ⇒ ∃ x ∈ A : f ( x) = y.
Función biyectiva
Una función f : A → B es biyectiva si y solo sí es al mismo tiempo inyectiva y suryectiva. Función inversa
Dados
A, B
y
F ⊆ A× B ,
definimos
F −1 = {( y, x) : ( x, y) ∈ F}
la
relación
f −1 = ( F −1, B, A) si y solo sí la relación f = ( F , A, B) es una biyección. La función f −1 es
llamada la función inversa de f . Toda función biyectiva f : A → B y su inversa f −1 : B → A establecen una correspondencia biunívoca entre A y B . Composición de funciones
Sean A, B, C tres conjuntos. F1 ⊆ A× B y F2 ⊆ B × C . Se define F2 F1 de la siguiente manera: F2 F1 = {( x, y ) : ∃ z, ( x, z ) ∈ F1 ∧ ( z, y ) ∈ F2 } .
Sean f1 : A → B y f2 : B → C dos funciones. La relación f2 f1 = ( F2 F1, A, C ) definida por f2 f1 (x) = f2 ( f1 ( x)) ∀x ∈ A es una función de A en C denominada función compuesta.
3.2 Elementos de la teoría de reticulados Como ya se mencionó anteriormente, una vez que un conjunto ha sido dotado de una relación de orden, es posible explotar esta relación para extraer varios resultados interesantes. La teoría de reticulados estudia exactamente las propiedades y resultados derivados de conjuntos dotados con una relación de orden bien caracterizada.
3-5
CAPITULO 3
PRELIMINARES MATEMÁTICOS
3.2.1 Elementos notables de un conjunto ordenado Mínimo y máximo de un conjunto.
Sea A un conjunto parcialmente ordenado y M un subconjunto de A : Un elemento a ∈ M es el mínimo elemento de M si a ≤ y para todo y ∈ M . Esto es: min(M ) = a ⇔ ( a ∈ M y ( a ≤ y, ∀y ∈ M ) ) .
De la misma forma, un elemento b ∈ M es el máximo elemento de M si y ≤ b para todo y ∈ M . Esto es: max(M ) = b ⇔ ( b ∈ M y ( y ≤ b, ∀y ∈ M ) ) .
Un resultado que se puede demostrar fácilmente es que si existen el mínimo y el máximo de un conjunto estos son únicos. Para todo elemento A∈P ( E ) , se verifica que ∅, A ⊂ E y por lo tanto el mínimo y máximo elemento de P ( E ) son respectivamente ∅, E . Limites inferiores y superiores
Sea A un conjunto parcialmente ordenado y M un subconjunto de A : Un elemento a ∈ A tal que a ≤ x para todo x ∈ M es denominado límite inferior de M en A , esto es: X = {a ∈ A : a ≤ x, ∀x ∈ M } .
De la misma forma un elemento b ∈ A tal que x ≤ b para todo x ∈ M es denominado límite superior de M en A , esto es: X = {a ∈ A : x ≤ a, ∀x ∈ M } .
Ínfimo y supremo
Dado un conjunto parcialmente ordenado A y un subconjunto M ⊂ A , si el conjunto de límites inferiores de M posee un máximo, éste es llamado el ínfimo de M y denotado por ∧ . De la misma forma, si el conjunto de límites superiores de M posee un mínimo, este es llamado el supremo de M y denotado por ∨ .
3-6
CAPITULO 3
PRELIMINARES MATEMÁTICOS
3.2.2 Reticulados Un conjunto parcialmente ordenado A es un reticulado si todo subconjunto finito de A posee ínfimo y supremo en A . Un subreticulado de un reticulado A es un conjunto D ⊂ A tal que, a ∧ b ∈ D y a ∨ b ∈ D , ∀a, b ∈ D .
Un reticulado A es: Completo si y solo sí cualquier subconjunto de A posee ínfimo y
supremo en A . Distributivo si y solo sí x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ) , ∀x, y, z ∈ A . Complementario si y solo sí todos sus elementos poseen complemento.
El complemento de un elemento x en un reticulado A con min ( A ) y max ( A ) es un elemento y ∈ A tal que x ∧ y = min ( A) y x ∨ y = max ( A) , y se denota xc . Booleano si y solo sí es distributivo y complementario.
3.2.3 Isomorfismo de reticulados Sean A y B dos reticulados ordenados por la relación de orden ≤A y ≤B respectivamente. Sea ψ : A → B una función biyectiva de A en B . La función f es un isomorfismo de A en B si y solo sí, para todo x, y ∈ A , se verifica: x ≤A y ⇔ f ( x) ≤B f ( y) .
La Morfología Matemática, estudia mapeos entre dos reticulados cualesquiera. Como se definió precedentemente un reticulado completo es una estructura matemática que puede formalizar una relación de orden con dos operaciones: ínfimo ( ∧ ) y supremo
( ∨ ) . Estas operaciones cumplen un papel importante en Morfología de niveles de gris al igual que la erosión y la dilatación en la Morfología binaria (Dougherty, E., 1992). Por la importancia que tiene la Morfología Matemática en esta tesis se desarrollará esta teoría en el siguiente capítulo haciendo mayor hincapié en los Operadores Morfológicos Geodésicos.
3-7
CAPITULO 3
PRELIMINARES MATEMÁTICOS
3.3 Nociones básicas de espacios topológicos En esta sección se introducen definiciones y resultados de topología general, que serán utilizados para definir el método de segmentación propuesto en esta tesis y el índice de similitud para evaluar la segmentación propuesta.
3.3.1 Espacios métricos Una métrica o función distancia definida en un conjunto M distinto de vacío es una función d : M × M → , que asocia a cada par ordenado
( x, y ) ∈ M × M
un
número real d ( x, y ) llamado la distancia de x a y , de modo tal que las siguientes condiciones se satisfagan para cualesquiera x, y, z ∈ M : d1) d ( x, y ) ≥ 0 ; d2) d ( x, y ) = 0 ⇔ x = y ; d3) d ( x, y ) = d ( y, x ) ; d4) d ( x, y ) ≤ d ( x, z ) + d ( z , y ) . Un espacio métrico es un par ( M , d ) , donde M es un conjunto distinto de vacío y d es una métrica en M (Lima, 1977). Una seudo-métrica en un conjunto M es una función d : M × M → que cumple las condiciones de métrica, salvo el hecho de que puede ser la d ( x, y ) = 0 y x ≠ y . Un espacio seudo-métrico es un par ( M , d ) donde M es un conjunto y d es
una seudo-métrica para M . Todo conjunto puede ser considerado un espacio métrico de manera muy simple. Para esto, basta definir la métrica d : M × M → de la siguiente manera: 1 si x ≠ y d ( x, y ) = 0 si x = y
Las condiciones d1) a d4) se pueden verificar fácilmente. Otro ejemplo de espacio métrico es el de la recta real, o sea, el conjunto de los números reales . La distancia entre dos puntos x, y ∈ está definida por d ( x, y ) = x − y . Las condiciones d1) a d4) resultan inmediatas de las propiedades 3-8
CAPITULO 3
PRELIMINARES MATEMÁTICOS
elementales del valor absoluto de un número real. Ésta es llamada la “métrica usual” de la recta. En n existen tres maneras naturales de definir una distancia entre dos puntos: 1/ 2
n i) d ( x, y ) = ∑ ( xi − yi ) i =1 n
ii) d1 ( x, y ) = ∑ xi − yi i =1
iii)
d ∞ ( x, y ) = max xi − yi 1≤i ≤ n
Una métrica de suma importancia es la que se define en la esfera hueca, también conocida como “2-esfera”, centrada en el origen y radio r > 0 , cuya definición analítica es: S r2 = {( x, y, z ) ∈ 3 : x 2 + y 2 + z 2 = r 2 } .
Figura 1 Geodésicas en la esfera hueca.
La distancia entre dos puntos x e y pertenecientes a la superficie, se calcula usando la longitud de la geodésica que une a estos puntos. Las curvas que unen dos puntos, de tal forma que su longitud sea mínima, se llaman geodésicas. Las geodésicas corresponden a arcos de circunferencias máximas, que resultan de la intersección de la superficie esférica con planos que pasan por el centro de la esfera. A partir de esta noción surge una nueva distancia de suma utilidad en Morfología Matemática y en el desarrollo de esta tesis, denominada distancia geodésica. A diferencia de la distancia euclidiana dada por la longitud del segmento de línea (camino más corto) que une los dos puntos, en el marco geodésico, el camino está sujeto a ciertas limitaciones: éste debe estar totalmente contenido en un conjunto dado. Formalmente, la distancia geodésica entre dos puntos p y q de un conjunto X se define
3-9
CAPITULO 3
PRELIMINARES MATEMÁTICOS
como el ínfimo de las longitudes de los lazos que unen p con q en X; si tales lazos existen (Lantuéjoul, C. and Beucher, S., 1981). d g , X ( p, q ) = min { ( γ ) , γ camino interior a X , γ ( a ) = p, γ ( b ) = q} donde ( γ ) corresponde a la longitud del camino. Si no existe tal camino, se define d g , X ( p, q ) = +∞ . Dado el papel principal que esta métrica cumple en el desarrollo de esta tesis se demuestra a continuación que cumple con los cuatro axiomas de métrica. De la definición se desprende que d g , X ( x, y ) = 0 ⇔ x = y , y además que d g , X ( x, y ) = d g , X ( y , x ) . Si d g , X ( x, y ) y d g , X ( y , z ) son ambas finitas, existen dos caminos
γ x , y y γ y , z de longitud finita que unen x con y e y con z ; el camino γ x , z que surge de seguir primero el camino que une x con y y luego el que une y con z , es de
{
}
longitud finita y en consecuencia d g , X ( x, z ) < ∞ y como la d g , X ( x, y ) = inf l ( γ x , y ) : d g , X ( x, z ) ≤ d g , X ( x, y ) + d g , X ( y , z )
Finalmente, si uno de los términos del lado derecho de la desigualdad es infinito la relación es trivial. Si
(M ,d )
es un espacio métrico, todo subconjunto S ⊂ M , puede ser
considerado de forma natural, como un espacio métrico: basta considerar la restricción de d a S × S . Cuando esto ocurre, S es llamado un subespacio de M y la métrica de S se dice inducida por la métrica de M .
Dado un espacio métrico ( M , d ) , un punto a ∈ M , y un número real r > 0 , la
bola
abierta
(bola
cerrada)
B ( a, r ) = { x ∈ M : d ( a, x ) < r}
de
centro
a
y
radio
r
es
el
conjunto
(respectivamente B [ a, r ] = { x ∈ M : d ( a, x ) ≤ r} ).
La
noción de bola es fundamental en el estudio de espacios métricos. Sea S un subespacio del espacio métrico M . Para cada a ∈ S y cada r > 0 , sea BS ( a, r ) la bola abierta de centro a y radio r , relativa a la métrica inducida en S . Se tiene BS ( a, r ) = B ( a, r ) ∩ S , donde B ( a, r ) es la bola abierta de centro a y radio r en el espacio M . Análogamente, vale BS [ a, r ] = B [ a, r ] ∩ S . 3-10
CAPITULO 3
PRELIMINARES MATEMÁTICOS
Si se considera 2 con las métricas d , d1 , d ∞ , la bola abierta B ( a, r ) es el interior de un círculo de centro a y radio r , o el interior de un cuadrado de centro a y lados de longitud 2r , paralelos a los ejes o el interior de un cuadrado de centro a y diagonales paralelas a los ejes, ambas de longitud 2r respectivamente. Otra métrica fundamental para la definición del índice de similitud, utilizado para validar la segmentación propuesta, es la distancia o métrica de Hausdorff. La distancia o métrica de Hausdorff mide el grado de semejanza entre dos conjuntos de puntos que están en una posición fija con respeto el uno al otro (Huttenlocher D. P., Klanderman G. A., and Rucklidge W. J., 1993). Dados dos conjuntos A, B ⊂ X , la distancia de Hausdorff es definida como: H(A, B) = sup ( h ( A, B ) , h ( B, A ) ) donde h ( A, B ) y h ( B, A ) representan la distancia directa entre los conjuntos A y B : h ( A, B ) = sup inf d(a, b) a∈A b∈B
para alguna distancia definida en X (por ejemplo la norma Euclídea o L2 ).
3.3.2 Espacios topológicos Una topología (o estructura topológica) en un conjunto X ≠ ∅ es una familia ℑ de subconjuntos de X que satisface las siguientes condiciones:
•
∅ y X son miembros de ℑ .
•
la intersección finita de miembros de ℑ es miembro de ℑ .
•
la unión de los miembros de cualquier subfamilia de ℑ es miembro de ℑ . El conjunto X se llama espacio de la topología ℑ , y ℑ es una topología para X
(Lima E. 1977, Serra, 1982). El par ( X , ℑ) es un espacio topológico. Los miembros de la topología se llaman ℑ -abiertos o simplemente abiertos con respecto a la topología
ℑ . Un conjunto F en el espacio es ℑ -cerrado o en forma simplificada cerrado si su complemento relativo es abierto, es decir, si ( X − F ) ∈ ℑ . Cuando no hay motivo de confusión hablaremos de abiertos y cerrados de la topología. Una familia B ⊂ ℑ se dice una base para la topología ℑ en X si todo conjunto abierto puede escribirse como la unión de elementos de B . En este caso, ℑ se dice
3-11
CAPITULO 3
PRELIMINARES MATEMÁTICOS
generada por B . Similarmente, la familia U ⊂ ℑ se dice una subbase para la topología ℑ en X si todo conjunto abierto puede escribirse como la unión de intersecciones
finitas de elementos de U . En este caso, también se dice que ℑ es generada por U . La topología generada por una base B (respectivamente subbase U ) es la menor topología que contiene a B (respectivamente a U ).
3.3.3 Topologías definidas en un conjunto Topología discreta e indiscreta:
Entre las topologías que se pueden considerar en un conjunto X , existen dos que representan extremos opuestos. Una es la topología discreta ℑ1 = P ( X ) , donde se toman todas las partes de X como conjuntos abiertos, y la otra es la topología indiscreta o caótica, ℑ2 = {∅, X } , donde ∅ y X son los únicos abiertos. ℑ1 y ℑ2 son la mayor y menor topología que se pueden definir en un conjunto respectivamente. Topología a partir de sistemas de entornos
Un conjunto U de un espacio topológico ( X , ℑ) es un entorno ( ℑ -entorno) de un punto x si y solo si U contiene un conjunto abierto al cual x pertenece. Denotaremos por U ( x ) al sistema de entornos del punto x . Sea ( X , ℑ) un espacio topológico y, para cada x ∈ X , sea U ( x ) el sistema de entornos del punto x . Entonces: i) Si U ∈ U ( x ) entonces x ∈ U . ii) Si U y V son miembros de U ( x ) , entonces U ∩V ∈U ( x) . iii) Si U ∈ U ( x ) y U ⊂ V , entonces V ∈ U ( x ) . iv) Si U ∈ U ( x ) , entonces existe un entorno V ∈V ( x ) tal que V ⊂ U y V ∈U ( y ) para cada y de V (es decir, V es entorno de cada uno de sus puntos). Si ℵ es una función que a cada x ∈ X le asigna una familia no vacía U ( x ) , de partes de X que satisface i), ii), iii), entonces la familia ℑ de aquéllos conjuntos U tales que U ∈ U ( x ) para cada x de U , es una topología de X . Si también se cumple iv), entonces U ( x ) es justamente el sistema de entornos de x con respecto a la
3-12
CAPITULO 3
PRELIMINARES MATEMÁTICOS
topología ℑ (Kelley J., 1975). Topología a partir de una función distancias
Existen muchos espacios topológicos donde la topología se deduce de una noción de distancia. Para el caso particular de esta tesis el espacio topológico estará dado por la distancia geodésica. Dada una distancia d se definen la bola abierta (cerrada) de centro x y radio r > 0:
B ( x, r ) = { y ∈ X : d ( x, y ) < r} bola abierta de centro x y radio r, B [ x, r ] = { y ∈ X : d ( x, y ) ≤ r} bola cerrada de centro x y radio r, a partir de éstas definiciones se definen los abiertos del espacio X : un conjunto A ⊂ X es abierto si y solo si para todo x ∈ A existe una bola abierta de centro x y radio r incluida en A . Luego la familia formada por todos los abiertos es una topología, llamada topología asociada a la distancia d (Lima, 1977). Topología relativa
Si ( X , ℑ) es un espacio topológico, e Y es parte de X , podemos construir una topología ℑY de Y que se llama la topología relativa o la relativización de ℑ a Y . La topología relativa ℑY se define como la familia de todas las intersecciones de miembros de ℑ con Y . Todo miembro U de la topología relativa ℑY se dice abierto en Y . Al espacio topológico (Y , ℑY ) se lo llama subespacio del espacio ( X , ℑ) .
3.3.4 Propiedades Topológicas Conectividad
La conectividad es una propiedad topológica de suma utilidad en el tratamiento de imágenes (Bouchet A., et. al., (2008), Braga-Neto U., et. al., 2004, Pastore, et. al., 2006). Un conjunto S ⊂ X se dice conectado si no se puede escribir como la unión de dos conjuntos abiertos disjuntos no vacíos. Otra manera de expresar la conexión de un conjunto es diciendo que se puede pasar de un punto a otro del conjunto por un movimiento continuo, sin salirse del conjunto. Esto nos lleva a la definición de espacio conectado por caminos, o simplemente, espacio conectado. Un camino en un espacio topológico X es una función continua f : [ 0,1] → X . Los puntos a = f ( 0 ) y b = f (1) 3-13
CAPITULO 3
PRELIMINARES MATEMÁTICOS
son los extremos del camino f y se dice que el camino liga al punto a con el punto b . Cuando a = b se dice que f es un camino cerrado. Si f , g : [ 0,1] → X son dos caminos que verifican que f (1) = g ( 0 ) , se define el camino f ∨ g : [ 0,1] → X , que consiste en seguir primero al camino f y después al camino g (figura 2). Formalmente, un conjunto S ⊂ X se dice conectado por caminos cuando dos puntos cualesquiera de S pueden ser ligados por un camino f en S . f(0)
g(1) f(1)=g(0)
f ∨ g:[0,1]→ X Figura.2 Ejemplo de espacios conectados por caminos.
Un espacio topológico X se dice localmente conectado por caminos cuando para todo x ∈ X y todo entorno U de x existe un entorno conectado por caminos V tal que x ∈V ⊂ U .
Partición
Una partición de un conjunto X se define como una división del mismo en clases X 1 , X 2 , X 3 ... X n de manera tal que si x ∈ X pertenece a una y sólo una de estas clases. Formalmente definimos una partición de X como una función p : X → ℑ tal que ∀x ∈ X , x ∈ p ( x) = X j y ∀( x, y ) ∈ X , p ( x)
p( x) = p( y ) o p( x) ∩ p( y ) = ∅ siendo
la partición de X que contiene a x . Las definiciones y conceptos presentados anteriormente permitirán definir
matemáticamente la segmentación propuesta para esta tesis, como así también presentar en el capítulo 6 un nuevo índice de similitud para comparar la eficiencia de la esta nueva técnica de segmentación.
3-14
4. Morfología Matemática
4. Morfología Matemática Dada la importancia que tiene la Morfología Matemática en esta tesis, en este capítulo se describen los operadores morfológicos clásicos y a posteriori los operadores morfológicos geodésicos. Éstos permitirán definir los filtros secuenciales alternados por reconstrucción que se utilizaron para la segmentación propuesta.
4.1 Introducción Desde una perspectiva científica, la palabra Morfología se refiere al estudio de las formas y estructuras que la materia puede tomar. En procesamiento de imágenes, morfología es el nombre de una metodología específica para analizar las estructuras geométricas dentro de una imagen (Serra J., 1982). En los años sesenta dos investigadores de Paris School of Mines, en Fontainebleau, Georges Matheron y Jean Serra trabajaron en problemas de mineralogía y petrografía. Su principal objetivo era caracterizar propiedades físicas de ciertos materiales, como la permeabilidad de medios porosos, examinando su estructura geométrica. Así fue como surgió la Morfología Matemática (MM), teoría basada en conceptos de Geometría, Álgebra, Topología y Teoría de Conjuntos (Ronse C., et al., 1991, Serra, J., 1982). El objetivo principal de la MM es extraer información relativa a la geometría y topología de un conjunto desconocido presente en la imagen. La clave de esta metodología está en el “elemento estructurante”, un conjunto completamente definido y de geometría conocida, que es comparado, a partir de una transformación, con el conjunto desconocido de la imagen. La forma y tamaño del elemento estructurante permiten testear y cuantificar de que manera el elemento estructurante “está, o no está contenido” en la imagen (Facon J., 1996). Una de las ventajas de la MM es su simplicidad de implementación y sus pilares son sus dos operaciones básicas, la erosión y la dilatación, a partir de las cuales, por composición, es posible construir nuevos operadores, lo que hace que la MM se destaque de otras técnicas de procesamiento de imágenes donde, en la mayoría de los casos, las implementaciones no hacen uso de las herramientas ya existentes (Bangham and Marshall, 1998). 4-1
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
Existen tres tipos de MM: morfología matemática binaria que se aplica sobre imágenes binarias, morfología en niveles de gris que se aplica en imágenes con niveles de gris y la morfología en colores que aún está en pleno desarrollo.
4.2 Principios de Morfología Matemática Una imagen binaria se puede representar como un subconjunto D de 2 . Si {0,1}
D
representa el conjunto de las funciones definidas de un subconjunto
D ⊂ 2 en el conjunto {0,1} , se puede establecer una biyección entre este conjunto y el
conjunto de imágenes binarias definidas en D , así toda imagen binaria puede representarse por una función característica χD : 2 → {0,1} . Una imagen en niveles de gris I se define como una aplicación con dominio DI ⊂ 2 sobre . p ∈ DI → I ( p ) ∈
(4.1)
Es claro que imágenes binarias son simplemente imágenes en niveles de gris que solo toman dos valores: 0 o 1.
4.2.1
Operadores Morfológicos básicos: Erosión y Dilatación
La idea central de la MM es examinar las estructuras geométricas de una imagen por superposición con pequeños patrones localizados (denominados elementos estructurantes) en distintas partes de la misma. Un elemento estructurante es un subconjunto de 2 , cuyo tamaño y forma se escoge a priori de acuerdo a la morfología del conjunto sobre el que se va a interactuar y de acuerdo a la extracción de formas que se desean obtener. En la figura 1 se muestran ejemplos básicos de elementos estructurantes utilizados en la práctica.
Figura 1. Formas básicas de elementos estructurantes planos. ∨
B notará el conjunto transpuesto, esto es:
4-2
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
∨
B = {−b : b ∈ B}
(4.2)
∨
B es simplemente obtenido por rotar B 180 sobre el origen O . El origen O es
llamado el centro del elemento estructurante B . Bx denotará la traslación de B por x : Bx = {b + x : b ∈ B}
(4.3)
Las operaciones u operadores morfológicos erosión y dilatación constituyen la base de la MM, la erosión queda completamente sustentada por la definición de resta de Minkowski mientras que la suma de Minkowski sustenta la definición de la dilatación (Serra, 1992). Al igual que en la bibliografía, se definen en primer término los operadores morfológicos para imágenes binarias y luego se extienden a imágenes en niveles de gris.
Erosión Binaria Sean X , B dos subconjuntos de 2 , la erosión de X por el elemento estructurante B , denotada por ε B ( X ) , es el conjunto de puntos x ∈ 2 tal que el conjunto Bx está incluido en X :
ε B ( X ) = { x ∈ 2 : Bx ⊆ X }
(4.4)
Informalmente, la operación erosión consiste en hacer decrecer al conjunto X a través de un proceso controlado de eliminación de elementos, tomando como referencia el elemento estructurante B . El tamaño y forma final del conjunto erosionado dependerá fuertemente del tamaño y forma del elemento estructurante (Dougherty E., 1993). Como se mencionó anteriormente, la erosión queda sustentada a partir de la resta de Minkowsky. Dados dos conjuntos X , B ⊂ 2 , se define la resta de Minkowsky X B de X por B como: X B = ∩ Xb b∈B
4-3
(4.5)
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
La relación entre la erosión y la resta de Minkowsky está dada por la siguiente igualdad: ∨
{
∨
ε B ( X ) = X B = x ∈ 2 : ∀b ∈ B, x − b ∈ X
}
(4.6)
Figura 2. Ejemplo de erosión en una imagen binaria euclidea.
En la figura 2 se presenta un ejemplo sencillo de una erosión de una imagen con un elemento estructurante circular. El área encerrada por la línea a trazo continuo constituyen la erosión de X por B y la línea punteada indica el conjunto original X tomado como referencia.
Dilatación Binaria Sean X , B ⊂ 2 , la dilatación de X por un elemento estructurante B , denotada por δ B ( X ) , es el conjunto de puntos x ∈ 2 tal que el conjunto Bx tiene intersección no vacía con el conjunto X :
δ B ( X ) = { x ∈ 2 : Bx ∩ X ≠ ∅}
(4.7)
En palabras, dilatar la imagen X por el elemento estructurante B consiste en eliminar del fondo todos los puntos x para los cuales el conjunto Bx no esté incluido, o de forma equivale asignar a la imagen dilatada todos los puntos x tales que Bx intercepte a la imagen. Al igual que con la erosión, la dilatación es sustentada por la suma de Minkowsky. Dados dos conjuntos X , B ⊂ n , se define la suma de Minkowsky X ⊕ B de X por B como: X ⊕ B = ∪ Xb b∈B
4-4
(4.8)
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
La relación entre la dilatación y la suma de Minkowsky está dada por la siguiente igualdad: ∨
{
∨
}
δB ( X ) = X ⊕ B = x + b : x ∈ X ,b ∈ B
(4.9)
Figura 3. Ejemplo de dilatación en una imagen binaria euclidea.
La figura 3 muestra un ejemplo de una dilatación de una imagen con un elemento estructurante circular. La zona encerrada por la línea a trazo completo constituye la dilatación de X por B mientras que la línea punteada indica el conjunto original que se toma como referencia. De los ejemplos de erosión y dilatación mostrados en las figura 2 y 3, es claro que el operador erosión “contrae” el conjunto, mientras que la dilatación lo “expande”. A través de la dilatación, diferentes componentes de un conjunto se pueden conectar, algunos agujeros se pueden llenar, mientras que a través de la erosión, los huecos se agrandan y algunos objetos pueden desaparecer. Formalmente, estos operadores poseen las siguientes propiedades: 1. La erosión y la dilatación son operadores crecientes, es decir, preserva la relación de inclusión entre conjuntos, esto es, X ⊆ Y ⇒ ψ ( X ) ⊆ ψ (Y ) . 2. La erosión y la dilatación son operadores duales, es decir, ∀X
(ψ ( X )) = (ψ c
*
( X ))
c
.
3. Cuando el elemento estructurante contiene a su centro, la erosión por B es antiextensiva y la dilatación por B es extensiva. Un operador es extensivo si y solo sí, para todo conjunto X , X ⊆ ψ ( X ) . Similarmente, ψ se dice anti-extensivo si y solo si, para cualquier conjunto X ,
ψ (X )⊆ X . 4-5
CAPITULO 4
4.
MORFOLOGÍA MATEMÁTICA
δ B ⊕B ( X ) = δ B ( δ B ( X ) ) = δ B ( δ B ( X ) ) 1
2
1
2
2
1
ε B ⊕ B ( X ) = ε B ( ε B ( X ) ) = ε B (ε B ( X ) ) 1
2
1
2
2
1
5. δ B1∪B2 ( X ) = δ B1 ( X ) ∪ δB2 ( X ) = δB2 ( X ) ∪ δ B1 ( X )
ε B ∪B ( X ) = ε B ( X ) ∪ ε B ( X ) = ε B ( X ) ∪ ε B ( X ) 1
2
1
2
2
1
La propiedad 2 es particularmente interesante en la práctica, afirma que erosionar la figura es equivalente a dilatar el fondo. Las propiedades 4 y 5 también son de especial interés. Dado un elemento estructurante B complejo, si se puede hallar una descomposición de B como una unión y/o suma de Minkowsky de elementos simples, entonces se puede realizar la dilatación (respectivamente la erosión) por
B
como una combinación de dilataciones
(respectivamente erosiones) por formas simples. De
la
combinación de
los
operadores
erosión
y dilatación,
nuevas
transformaciones morfológicas son derivadas.
Extracción de bordes De las propiedades anti-extensiva y extensiva de la erosión y dilatación respectivamente, se pueden determinar bordes en una imagen binaria examinando la diferencia entre una dilatación y una erosión de la imagen original, una dilatación y la imagen original o la diferencia entre la imagen original y su erosión. Sean X , B ⊂ 2 , el gradiente por dilatación, denotado por ΓδB ( X ) , se define como: ΓδB ( X ) = δ B ( X ) − X
(4.10)
el gradiente por erosión, denotado por ΓεB ( X ) , se define como: ΓεB ( X ) = X − ε B ( X )
(4.11)
y finalmente el gradiente por dilatación y erosión, denotado por ΓδB,ε ( X ) , se define como: δ ,ε
ΓB ( X ) = δ B ( X ) − ε B ( X )
4-6
(4.12)
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
Apertura y Cierre Binarias Generalmente, la erosión
X → ε B ( X ) y la dilatación
X → δ B ( X ) son
operaciones que no admiten inversas, por lo tanto, no hay manera de determinar el origen X desde las imágenes ε B ( X ) o δ B ( X ) . Por ejemplo, si se erosiona un conjunto X por un elemento estructurante B , no siempre se puede recuperar X dilatando por B el conjunto erosionado ε B ( X ) . El siguiente ejemplo ilustra gráficamente, este resultado:
X =
• • • • • • • • • • •
• • • • • • • • • • • • • •
• • • • • • • • •
δ B (ε B ( X ) ) =
B = • • •
• • • • • • • • • • • • • • • • • • • •
Esta reconstrucción reconstruye sólo una parte de X más simple y con menos detalles, pero que puede considerarse como su parte esencial (Gonzalez et al., 1996). A continuación se definen las operaciones de apertura y cierre, conocidas en morfología matemática como filtros básicos a partir de los cuales se desarrollan otros más complejos.
Apertura Binaria Sean X , B ⊂ 2 , la apertura (openig) de X por el elemento estructurante B se define como:
γ B ( X ) = δ (ε B ( X ) ) ∨
B
4-7
(4.13)
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
En la figura 4 se ilustra el efecto de una apertura de un conjunto X ⊂ 2 por un elemento estructurante en forma de disco.
Figura 4. Ejemplo de apertura en una imagen binaria euclidea.
Cierre binario Sean X , B ⊂ 2 , el cierre (closing) de X por el elemento estructurante B está definido por:
φB ( X ) = ε (δ B ( X ) ) ∨
B
(4.14)
Figura 5. Ejemplo de apertura en una imagen binaria euclidea.
En la figura 5 se presenta un ejemplo, en el cual a una imagen euclideana se le aplica una operación de cierre con un elemento estructurante en forma de disco. La apertura y cierre tienen un significado morfológico más fuerte que la erosión y la dilatación, pues permiten filtrar una imagen.
Propiedades de la apertura y el cierre morfológico Asumiendo un elemento estructurante simétrico: Dualidad: apertura (Opening) y cierre (closing) son operadores duales. Crecientes: Siendo los operadores apertura y cierre composición de operadores
crecientes (erosión y dilatación), estos son también crecientes.
4-8
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
Relación de orden: el operador apertura es anti-extensivo, mientras que el cierre es
extensivo. Esto significa que se puede presentar la siguiente relación de orden:
δε ≤ X ≤ εδ . Idempotente: apertura y cierre son operadores idempotentes.
La apertura y el cierre difieren de la erosión y la dilatación en la propiedad de idempotencia, propiedad sumamente importante en el proceso de filtrado.
Reconstrucción binaria Una operación de suma importancia en morfología matemática es la reconstrucción tanto para imágenes binarias como para imágenes en niveles de gris (Braba-Neto, U., 2004, Desencierre F., et al., 1997). Sean X (máscara) e Y (marca) dos imágenes binarias definidas en el mismo dominio D tal que Y ⊆ X , esto es, ∀ p ∈ D, Y ( P ) = 1 ⇒ X ( p ) = 1 . Si X 1 , X 2 … , X n son las componentes conectadas de X , la reconstrucción binaria ρX (Y ) de la máscara X a partir de la marca Y se define como la unión de todas las componentes conectas X k de X que contienen al menos un punto de Y , esto es:
ρX (Y ) = ∪( X ∩Y ≠∅) X k k
(4.15)
Figura 6. Ejemplo de apertura por reconstrucción en una imagen binaria euclidea.
Una aplicación de la reconstrucción binaria es la de filtrar una imagen. Un caso especial dentro de estas transformaciones, es la denominada apertura por reconstrucción. En imágenes binarias, la apertura por un elemento estructurante es utilizada usualmente para filtrar las componentes conectadas de una imagen que no contienen al
4-9
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
elemento estructurante (Vincent, 1993). Sin embargo, en algunos casos se desea filtrar todas las componentes conectadas que no contienen al elemento estructurante y dejar sin modificaciones las restantes. El resultado de esta transformación recibe el nombre de aperturas por reconstrucción (Serra y Vincent, 1992). La apertura binaria por reconstrucción γ Brec ( X ) de la imagen X por el elemento estructurante B consiste en una apertura binaria de X por B seguida de la reconstrucción de X a partir de la imagen obtenida después de aplicarle el operador apertura γ B ( X ) , esto es:
γ Brec ( X ) = ρX (γ B ( X ))
(4.16)
Este operador constituye uno de los filtros más interesantes en el tratamiento de imágenes binarias (Heijmans H., 1997).
4.2.2
Morfología Matemática en Niveles de Gris
Cuando se quieren aplicar las Transformaciones Morfológicas Binarias a imágenes con niveles de gris, se presenta el problema que, a diferencia de las imágenes binarias, éstas no son representadas como subconjuntos de 2 , sino como funciones con dominio en 2 y rango en . Sobre estas funciones no es posible utilizar directamente las herramientas desarrolladas en la Morfología Matemática Binaria. La solución a este problema es ampliar en una dimensión el espacio de trabajo. Para esto se bebe considerar la umbra de una imagen. Umbra significa sombra, y la umbra de un conjunto X en el espacio tridimensional incluye al mismo tiempo al conjunto y al volumen de los puntos de su sombra. Matemáticamente hablando la umbra de un conjunto es definida como un sólido tridimensional que se extiende continua e indefinidamente en la dirección negativa del eje z . Formalmente, la solución adoptada es considerar el subconjunto de puntos en el espacio tridimensional U [ I ] = {( x, y, z ) ∈ 3 : z ≤ f ( x, y )} , donde f : DI ⊆ 2 → es la función que representa a la imagen en niveles de gris, es decir, el subconjunto de 3 formado
por
todos
los
puntos
que
están
por
debajo
de
la
S ( I )( x, y ) = {( x, y , z ) ∈ 3 : z = f ( x, y )} .
A partir del conjunto U [ I ] es posible recuperar la función f como:
4-10
superficie
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
f ( x, y ) = sup { z ∈ : ( x, y, z ) ∈ U [ I ]}
(4.17)
Inversamente, si ℵ denota la clase de umbraes, esto es:
{
ℵ = U : U ∈ F ( 2 × ) , ∀ ( x, y , z ) ∈ U ; z ≤ z * ⇒ ( x , y , z * ) ∈ U
}
(4.19)
A cada elemento U ∈ℵ le corresponde una y solo una función f : 2 → para la cual U es su umbra. La relación de orden U [ f ] ⊆ U [ g ] es equivalente a:
∀ ( x, y ) ∈ D f ∩ Dg f ( x, y ) ≤ f ( x, y )
(4.20)
Por lo tanto ℵ constituye un reticulado para la inclusión, por ser cerrado para la intersección y para uniones finitas. Si interpretamos esto en términos de funciones, para toda familia (finita o no) de índices i tenemos: f ≤ g ⇔ U [ f ] ≤ U [ g ] sii ∀ ( x, y ) ∈ 2 , f ( x, y ) ≤ g ( x, y )
{ } ∨ f = { f : U [ f ] = ∪ U [ f ]} ∧ fi = f : U [ f ] = ∩ U [ fi ] i
i
i
i
i
i
Bajo estás condiciones se pueden definir la erosión y la dilatación en niveles de gris. En primer lugar se asocia una umbra a la imagen y al elemento estructurante. Luego se aplican las definiciones de erosión y dilatación definidas anteriormente en el espacio tridimensional. El resultado es una umbra, a partir de la cual se puede obtener la única función que representa la imagen en niveles de gris, que representa la imagen resultante de dicha operación. Por consiguiente, los operadores morfológicos en niveles de gris se pueden considerar como una extensión de los operadores morfológicos binarios en el espacio tridimensional. Sean f : D f ⊆ 2 → y g : Dg ⊆ 2 → , Dg ⊆ D f dos imágenes en niveles de gris. La erosión de f por el elemento estructurante g es definida por:
4-11
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
{
}
ε g ( f ) = sup εU [ g ] (U [ f ])
(4.21)
La cual es equivalente a:
ε ( f , g )(s, t) = min { f (s + x, t + y) − g( x, y) / ( s + x, t + y ) ∈ Df ; ( x, y ) ∈ Dg }
(4.22)
La dilatación de f por el elemento estructurante g es definida por:
{
}
δ g ( f ) = sup δU [ g ] (U [ f ])
(4.23)
La cuál es equivalente a la definición:
δ ( f , g)(s, t ) = max { f (s − x, t − y) + g( x, y) / ( s − x, t − y ) ∈ Df ; ( x, y ) ∈ Dg }
(4.24)
Si el elemento estructurante es plano, es decir, g ( x, y ) = 0 ∀ ( x, y ) ∈ Dg , las ecuaciones (4.23) y (4.24) se simplifican:
ε ( f , g )(s, t) = min { f (s + x, t + y) / ( x, y ) ∈ Dg }
(4.25)
δ ( f , g)(s, t ) = max{ f (s − x, t − y) / ( x, y ) ∈ Dg }
(4.26)
Una interpretación grafica se puede hacer sobre una señal unidimensional.
Figura 7. Ejemplo de erosión en una imagen binaria euclidea.
Cuando se aplica la operación erosión a una imagen con niveles de gris se aprecian los siguientes efectos:
Debido a que punto a punto la intensidad de cada pixel es menor o igual que la
intensidad del pixel original, la imagen erosionada resulta más oscura que la imagen original.
El área que ocupa una zona clara de la imagen rodeada por zonas oscuras, tiende
a reducirse. Si el tamaño de la zona clara es menor que el tamaño del elemento estructurante desaparece, quedando sólo la zona oscura. Cuando se aplica la operación dilatación a una imagen con niveles de gris se aprecian los siguientes efectos: 4-12
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
Debido a que punto a punto la intensidad de cada pixel es mayor o igual que la
intensidad del pixel original, la imagen dilatada resulta más clara que la imagen original.
El área que ocupa una zona clara de la imagen rodeada por zonas oscuras, tiende
a ampliarse. Si el tamaño de la zona oscura es menor que el tamaño del elemento estructurante, la zona oscura desaparece, quedando sólo la zona clara. Al igual que en el caso binario, a partir de las definiciones de erosión y dilatación se definen la apertura (opening) y cierre (closing) morfológico de la siguiente manera: Apertura morfológica: γ g ( f ) = δ g ( ε g ( f ) ) . Cierre morfológico: φg ( f ) = ε g (δ g ( f ) ) . La apertura generalmente suaviza el contorno de la imagen, elimina las partes angostas y las salientes delgadas. Es de utilidad para eliminar detalles luminosos pequeños en relación al elemento estructurante, quedando el resto de la imagen relativamente sin modificaciones. Desde el punto de vista de filtrado, cuando se erosiona una imagen, el área de una zona clara rodeada de zonas oscuras, se ve reducida. En particular, si el tamaño del elemento estructurante es mayor que el área de la zona clara, ésta desaparece, se reducen los detalles luminosos pequeños y sólo queda la zona oscura. Luego, al dilatar la imagen resultante, el área de una zona clara rodeada de zonas más oscuras, tiende a ampliarse y por lo tanto la imagen recupera su intensidad o tamaño anterior, excepto que los detalles eliminados por la erosión previa, no vuelven a aparecer. El cierre también tiende a suavizar secciones de los contornos, pero a diferencia de la apertura fusiona espacios angostos, y entradas largas y delgadas, elimina huecos pequeños y rellena espacios en el contorno. Es de utilidad para eliminar detalles oscuros pequeños en relación al elemento estructurante, quedando el resto de la imagen relativamente sin modificaciones. Cuando se dilata una imagen, el área de una zona clara rodeada de zonas más oscuras, se ve ampliada. En particular, si el tamaño del elemento estructurante es mayor que el área de la zona oscura, ésta desaparece, se reducen los detalles oscuros pequeños. Luego, al erosionar la imagen resultante, el área de una zona clara rodeada de zonas más 4-13
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
oscuras, tiende reducirse y por lo tanto la imagen recupera su intensidad o tamaño anterior, excepto que los detalles eliminados por la dilatación previa, no vuelven a aparecer. La forma, tamaño e intensidad en niveles de gris del elemento estructurante determinan la estructura de la imagen trasformada. En las figuras 8 y 9 se muestran los resultados de una apertura y un cierre morfológico a una señal unidimensional con un elemento estructurante lineal.
Figura 8. Apertura de una señal unidimensional con un elemento estructurante lineal.
Figura 9. Cierre de una señal unidimensional con un elemento estructurante lineal.
Gradiente Morfológico La información del gradiente es muy usada en el procesamiento de imágenes para detectar bordes. De forma general, la información gradiente es una versión digital de la información diferencial. Sea f una señal diferenciable en todo su dominio, la derivada de f según la coordenada h en la dirección α en el borde B es:
δf δf ( x ) = ( x ) + σ cos(θ ) − αδ x ( B ) δh δh
(4.27)
δ f donde la función representa la derivada en el término continuo, σ el salto en el δh
punto x ∈ B , el ángulo θ representa la recta perpendicular a B en el punto x orientada en sentido positivo del salto, y δ x ( B ) es el pulso de Dirac en el punto x .
4-14
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
δ f La definición del gradiente de f en el punto x es el vector δx
δ f , δy
asociado con la función diferencial df : df =
δf δf dx + dy δx δy
(4.28)
En morfología matemática, existen varias implementaciones digitales del gradiente. Las más usadas son el gradiente morfológico por erosión, el gradiente morfológico por dilatación y el gradiente morfológico por erosión y dilatación. El gradiente morfológico gradmε ( f , b ) de una función f por un elemento estructurante b a partir de la erosión es: gradmε ( f , b ) = f − ε ( f , b )
(4.29)
El Gradiente por erosión en niveles de gris detecta bordes en las posiciones de los niveles de gris más elevados en los bordes. El gradiente morfológico gradmδ ( f , b ) de una función f por un elemento estructurante b a partir de la dilatación es: gradmε ( f , b ) = δ ( f , b ) − f
(4.30)
El Gradiente por dilatación en niveles de gris detecta bordes en las posiciones de los niveles de gris más bajos en los bordes. El tercer tipo de gradiente morfológico mencionado, consiste en usar en forma simultánea los operadores de erosión y dilatación. Formalmente, el gradiente morfológico gradmε ,δ ( f , b ) de una función f por un elemento estructurante b a partir de los operadores dilatación y erosión es: gradmεδ ( f , b ) = δ ( f , b ) − ε ( f , b )
(4.31)
El gradiente por dilatación y erosión en niveles de gris agrupa los resultados de los gradientes por erosión y dilatación. Por lo tanto, podemos observar que los operadores del gradiente gradmε ( f , b ) y presentan contornos más finos que el operador gradmε ,δ ( f , b ) .
4-15
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
Filtros Morfológicos Un filtro morfológico es un operador creciente e idempotente. La apertura es un filtro morfológico anti-extensivo, mientras que la clausura es un filtro morfológico extensivo. De las propiedades de crecimiento, idempotencia, extensividad y antiextensividad, la apertura y el cierre morfológico constituyen filtros de gran importancia dentro de esta teoría. Estos filtros no representan los únicos filtros con estas propiedades, más aún constituyen una buena base.
Filtros Secuenciales Alternados (AFSs) A partir de una apertura, se puede definir una familia de aperturas de parámetro
λ = nb de la siguiente manera:
(
γ λ ( f ) = γ nb ( f ) = γ nb γ ( n−1) b (…γ b ( f ) )
)
(4.32)
Dicha familia tiene la siguiente propiedad:
∀f , λ ≥ µ ⇒ γ λ ( f ) ≤ γ µ ( f
)
(4.33)
De la misma manera podemos definir una familia de cierres de parámetro λ = nb de la siguiente manera:
(
φ λ ( f ) = φ nb ( f ) = φ nb φ ( n−1) b (…φ b ( f ) )
)
(4.34)
que verifica la siguiente propiedad:
∀f , λ ≤ µ ⇒ φ λ ( f ) ≥ φ µ ( f
)
(4.35)
La generación de estas dos familias permite definir los denominados filtros secuenciales alternados (Jackway P., and Deriche M., 1996): El filtro alternado secuencial γφ λ está definido por:
( (
(
(
γφ nb ( f ) = γ nb φ nb γ ( n−1) b φ ( n −1) b …γ b (φ b ( f ) )
))))
(4.36)
))))
(4.37)
y el filtro alternado secuencial φγ λ está definido por:
( (
(
(
φγ nb ( f ) = φ nb γ nb φ ( n−1) b γ ( n−1) b …φ b ( γ b ( f ) )
4-16
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
En la primera iteración, con un elemento estructurante unidad, el filtro secuencial alternado γφ nb elimina el ruido pequeño al aplicar un cierre φ , recuperando información aplicando una apertura γ . En las sucesivas iteraciones el elemento estructurante crece y se repite el efecto.
4.3 Morfología Matemática: Geodésica Los operadores presentados anteriormente consideran las imágenes como conjuntos indivisibles. Pero a menudo surge la necesidad de restringir los procesos a una región específica de la imagen. Para ello las transformaciones morfológicas pueden ser modificadas de manera tal que se trabaje sobre un subconjunto de la imagen. Es así como surgen las transformaciones geodésicas. La teoría geodésica para el análisis de imágenes fue propuesta por Ch. Lantuéjoul y S. Beucher en (Lantuéjoul, 1981). Las transformaciones geodésicas son extremadamente interesantes cuando se quiere procesar un subconjunto del espacio de análisis.
4.3.1 Operadores Morfológicos Geodésicos. En el capítulo 3 se definió la distancia geodésica entre dos puntos p y q de un conjunto X como el ínfimo de las longitudes de los lazos que unen p con q en X, si tales lazos existen. Si p y q pertenecen a dos componentes conectadas disjuntas de X , d g , X ( x, y ) = +∞ . En otras palabras, d g , X se presenta como una función distancia
apropiada para trabajar con problemas de conectividad.
4-17
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
Figura 10. Distancia Geodésica entre x e y;
d g , X ( p, q ) ;
La distancia geodésica entre un punto p del conjunto X y un subconjunto A de X se define como la menor de las distancias geodésicas entre p y cualquier punto a ∈ A . En este caso, al conjunto A se lo conoce como marca y al conjunto X como
máscara. De la definición de distancia geodésica se desprende el concepto de bola geodésica, que será empleada como elementos estructurantes en las transformaciones geodésica y tendrá un papel fundamental en el algoritmo de segmentación propuesto en esta tesis. Bg ( p, λ ) = { x ∈ X / d g , X ( p, x) < λ}
Figura 11. Disco Geodésico de radio
λ
en la mascara
(4.38)
X
Las definiciones de erosión y dilatación geodésica están íntimamente relacionadas con la definición de distancia geodésica. La erosión geodésica elemental de una imagen f (marcador), por un elemento estructurante g (mascara), g ≤ f , ( g ( x) ≤ f ( x) ∀x ∈ Dg ⊂ D f ), se define como:
ε b(1),g ( f ) = ε b ( f ) ∨ g siendo ∨ el supremo.
4-18
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
La imagen marcadora f se erosiona y seguidamente se calcula el supremo entre la función erosionada y la máscara. El efecto visual de este tipo de erosión es que la máscara retiene al marcador para que éste no desaparezca (se limita la contracción del marcador). En este caso la erosión geodésica es mayor o igual que la máscara, además es una operación creciente y anti-extensiva. La figura 12 muestra la diferencia entre una erosión clásica (figura 12b) y una erosión geodésica (figura 12c). En la erosión geodésica se puede observar el límite por la máscara a la desaparición del marcador. La erosión geodésica de tamaño n , n ≥ 0 , se define como la iteración de erosiones geodésicas de tamaño creciente, esto es:
ε (bn,g) (f ) = ε (b1,)g (ε (b1,)g (.....ε (b1,)g (f )))
n veces
(4.39)
Una erosión geodésica de tamaño n = 0 no produce cambios en la imagen original, ε b(0) ,g ( f ) = f .
Figura 12. Erosión geodésica de una señal marcadora g con respecto a una señal mascara f. (a) Señales originales. (b) Erosión clásica de g. (c) Erosión geodésica de g respecto de f.
La dilatación geodésica elemental de una imagen f (marcador), por un elemento estructurante b, condicionada a g (mascara), f ≤ g , ( f ( x) ≤ g ( x)∀x ∈ D f ⊂ Dg ), se define como:
δ b(1),g ( f ) = δ b ( f ) ∧ g , siendo ∧ el ínfimo. La máscara actúa como límite de propagación de la dilatación del marcador por lo tanto δ b(1),g ( f ) ≤ g . La dilatación geodésica es, al igual que la dilatación clásica, un operador creciente y extensivo. En la figura 13 se observa la dilatación geodésica de una señal unidimensional, en la misma se observa como la señal marcadora es inferior a la
4-19
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
señal máscara (figura 13a). El resultado de dilatar el marcador con un elemento estructurante de tamaño 3 se presenta en la (figura 13b). La dilatación geodésica del marcador respecto a la máscara suprime los puntos de g mayores a f (figura 13c). La máscara frena la dilatación clásica del marcador.
Figura 13. Dilatación geodésica de una señal marcadora g con respecto a una señal mascara f. (a) Señales originales. (b) Dilatación clásica de g. (c) Dilatación geodésica de g respecto de f.
La dilatación geodésica de tamaño n , n ≥ 0 , como en la erosión geodésica, se define como la iteración de dilataciones geodésicas de tamaño creciente, esto es: (n) (1) (1) (1) δ b, g = δ b, g (δ b, g (..........δ b, g (f )))
n veces
(4.40)
La apertura geodésica morfológica de la imagen f , se define como:
γ b, g ( f ) = δ b, g (ε b , g ( f ))
(4.41)
y la cerradura geodésica morfológica como:
φb , g ( f ) = ε b , g (δ b , g ( f ))
(4.42)
La erosión y la dilatación geodésica poseen la particularidad de que cuando se iteran hasta la estabilidad o idempotencia permiten la definición de poderosos algoritmos de reconstrucción morfológica. Tanto la erosión geodésica como la dilatación convergen a la idempotencia en un número finito de iteraciones (Vicent, 1993). La reconstrucción por dilatación de una imagen máscara f desde una imagen marcador g , ambas con el mismo dominio g ≤ f , se define como la dilatación geodésica de g respecto a f hasta la idempotencia y se denota ρ g ( f ) :
4-20
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
ρ g ( f ) = ∨ δ b(,nf) ( g ) n ≥1
(4.43)
Como f actúa como límite de propagación, ρ g ( f ) ≤ f , por lo que llegado el momento la dilatación geodésica no produce ninguna variación de la señal. La reconstrucción por dilatación es una operación anti-extenciba (Salembier P., and Serra J., 1995). En la figura 14 se muestra un ejemplo de reconstrucción por dilatación de una señal unidimensional. Cada una de las dilataciones geodésicas que componen la reconstrucción se realiza a partir de la dilatación geodésica de la iteración anterior. De este modo el marcador puede ir reduciendo progresivamente su intensidad en la propagación bajo la máscara (Crespo J., et al., 1997).
Figura 14. Reconstrucción geodésica por dilatación de la señal f desde la señal g.
Análogamente se define la reconstrucción dual, ρ *g ( f ) a partir de una imagen g , g ≤ f , como:
ρb*, g ( f ) = N M ax − ρ N
max − g
(g − f )
(4.44)
La idea de iterar varias veces consiste en propagar el valor mínimo (máximo) de cada componente hasta homogeneizar la componente entera. Ese mínimo (máximo) representa el nivel de gris de la reconstrucción del objeto, por lo que la reconstrucción de una imagen en niveles de gris no será perfectamente reconstruida, como sí sucederá en el caso binario.
4-21
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
La apertura por reconstrucción de tamaño n de una imagen f se define como la reconstrucción por dilatación de f a partir de la erosión clásica de tamaño n de f : rec γ bdil ,bc ( f ) = γ bc , g ( f )
(4.45)
donde g = ε ( f , bero) . Contrariamente a la apertura clásica, la apertura por reconstrucción preserva perfectamente la forma de los objetos que no son eliminados por la erosión. Todos los objetos menores que le elemento estructurante son eliminados, el resto permanece sin alteración en la imagen. En la figura 6 se ilustra este sencillo filtro morfológico sobre una imagen binaria en la que se sitúan objetos de diferente forma y tamaño. En la apertura por reconstrucción, los objetos más pequeños que el elemento estructurante son eliminados por una erosión clásica, los objetos más grande también pierden definición, pero esta se recupera totalmente al actuar de marcadores en la dilatación geodésica (hasta la estabilidad o idempotencia) de la reconstrucción. El cierre por reconstrucción se define por dualidad y se corresponde con la erosión geodésica hasta la idempotencia de la imagen dilatada: rec Φ bdil ,bc ( f ) = Φ bc , g ( f )
(4.46)
donde g = δ ( f , bdil ) . Es posible observar la siguiente relación de orden entre los filtros de apertura y cierre geodésicos y los filtros clásicos:
γ ≤ γ rec ≤ I ≤ φ rec ≤ φ
(4.47)
4.3.2 Aplicaciones de la reconstrucción geodésica Los algoritmos basados en la reconstrucción geodésica son la base de numerosas transformaciones de imágenes. Los resultados de la reconstrucción están fuertemente influenciados por la elección correcta de los conjuntos máscara y marca.
4-22
CAPITULO 4
MORFOLOGÍA MATEMÁTICA
Filtros Secuenciales Alternados (ASFs) por Reconstrucción. Si bien los filtros secuenciales alternados de apertura y cierre, han demostrado ser útiles en aplicaciones de filtrado de imágenes (Serra y Vincent, 1992; Vincent, 1993) debido a que los objetos brillantes u oscuros de una imagen son eliminados, la forma original queda distorsionada. La propuesta de esta tesis es utilizar estos filtros incorporando la reconstrucción en cada iteración. Esta nueva clase de operadores presenta la ventaja de filtrar los objetos deseados sin alterar la forma original, lo que produce menor distorsión en la imagen. Los filtros secuenciales alternados por reconstrucción consisten en la repetición de operaciones de aperturas y cierres por reconstrucción con elementos estructurantes de tamaño creciente, interviniendo un segundo elemento estructurante usado en la reconstrucción. Formalmente se define el filtro secuencial "OC" (opening - closing) ( n iteraciones) como: nb, bc − γ rec Φ rec ( f ) = γ nbrec,bc (Φ rec (γ (rec Φ rec (… γ brec (Φ rec ( f ))))) nb , bc n −1) b , bc ( n −1) b , bc , bc b , bc
(4.48)
el filtro secuencial "CO" (closing - opening) ( n iteraciones) como: nb, bc − Φ rec γ rec ( f ) = Φ rec (γ nbrec,bc (Φ rec γ (rec (… Φ rec (γ brec ( f ))))) nb , bc ( n −1) b , bc n −1) b , bc b , bc , bc
(4.49)
donde n es un número entero positivo que representa el factor de escala del elemento estructurante b : nb = δ b (δ b … (δ b (b)))
( n −1) veces
Convencionalmente nb = {( 0, 0 )} para n = 0 . En el próximo capítulo se describe el algoritmo de segmentación propuesto en esta tesis con el fin de dar solución a la extracción de componentes conectadas de una imagen.
4-23
5. Extracción e Componentes Conectadas: Método Propuesto
5. Extracción de componentes conectadas: método propuesto. En el presente capítulo se describe un nuevo algoritmo de segmentación de imágenes desarrollado con el fin de dar solución a la extracción de componentes conectadas de una imagen. Dicho algoritmo se basa en la integración de un filtrado morfológico de la imagen original mediante operadores morfológicos, con el fin de homogeneizar las regiones de interés para evitar una sobre-segmentación, y un posterior etiquetado de regiones aplicando distancia geodésica, el cual puede evolucionar adaptándose a la topología de los objetos presentes en la imagen. Esta integración plantea un enfoque interesante de segmentación ya que combina la robustez de los filtros morfológicos con nociones básicas de la topología general.
5.1 Algoritmo general para extraer componentes conectadas de una imagen De acuerdo con el teorema de Jordan, una componente conectada acotada en el plano bidimensional es el interior de una curva simple cerrada. A partir de este resultado surge la primer definición, que permite extraer componentes conectadas de una imagen: “el interior de una curva simple cerrada (componente conectada acotada) que contiene a un punto p ” está dado por:
C p∈2 = { x ∈ 2 : d g ( x, p ) < ∞}
(5.1)
donde d g es la distancia geodésica (Pastore J., et al, 2005). Aplicando esta última definición extraer una componente conectada de una imagen es una tarea sencilla. Sin embargo, la desventaja más notoria que presenta esta primera aproximación a la solución del problema de segmentar una imagen es que no siempre se obtienen curvas simples y cerradas a partir de técnicas de detección de bordes (Dougherty E., et al, 1994, Hansen et al., 1999; Van Dr Ville et al., 2003). Esta desventaja motivó el desarrollo de un nuevo algoritmo, más general, basado en conceptos de topología general.
5-1
CAPITULO 5
EXTRACCIÓN DE COMPONENTES CONECTADAS: método propuesto
Este nuevo enfoque consiste en considerar la imagen como un subconjunto del espacio tridimensional con la topología relativa al espacio Geodésico. El proceso de segmentación se inicia con un punto arbitrario sobre la superficie de la imagen, para luego evolucionar iterativamente con el fin de incorporar aquellos puntos de la superficie que satisfacen un determinado criterio de aceptación prefijado, finalizando cuando se haya obtenido un cubrimiento de la superficie por conjuntos conectados que representan cada una de las regiones de interés. Establecer un criterio apropiado para generar un cubrimiento de la superficie, es decir, definir la estrategia de crecimiento y las propiedades que los puntos deben cumplir para ser incorporados a una u otra región es la fase más importante del diseño del algoritmo. A continuación se establecen el criterio de aceptación de puntos y la estrategia de crecimiento para el algoritmo propuesto. Criterio de aceptación de puntos.
Sea ( 3 , d ) el espacios tridimensional y sea f una imagen definida de 2 en . Sea G ( f ) = {( x, y ) ∈ 2 × / y = f ( x )} ⊆ 3 el gráfico de la función f : 2 → con la topología relativa ℑG ( f ) al espacio. Sean S ⊂ ℑG( f ) y ϕ : S × G ( f ) → tal que:
ϕ ( A, x ) = d ( γ ( A ) , x ) , con γ ( A) una caracterización de A y d una métrica. ϕ establece la relación de semejanza del conjunto A ∈ S con x ∈ G ( f ) ⊆ 3 , en función de γ ( A) . Dados ε y δ fijos, y S ⊂ ℑG ( f ) . Sean G ( f ) ⊆ 3 y A ∈ S , se dice que un elemento x ∈ G ( f ) pertenece a A si se cumple el siguiente criterio: B3 ( x, ε ) ∩ A \ { x} ≠ ∅ y ϕ ( A \ { x} , x ) ≤ δ , en otras palabras,
S
es un cubrimiento de
x ∈G ( f ), ∃ A∈ S : x ∈ A .
5-2
G ( f ) . Es decir para cada
Estrategia de crecimiento
La incorporación de puntos se basa en una estrategia de búsqueda en amplitud (BFS - Breadth First Search). Los puntos que son visitados y cumplen con la condición de aceptación son insertados en una lista hasta el momento de ser procesados y eventualmente integrados a la región. Inicialmente se incluye la semilla. Luego se realiza el crecimiento en forma iterativa, extrayendo en cada ciclo el primer elemento de la lista, el cual es rotulado como perteneciente a la región para evitar su re-evaluación, y a partir de él se evalúan sus vecinos en el entorno inmediato. Este esquema asegura que cada punto se evalúa una única vez, aunque sí es posible que sea considerado más de una vez en el análisis del entorno de sus vecinos. A continuación se presenta en un lenguaje artificial e informal una representación de las instrucciones a seguir y el orden lógico de su ejecución del algoritmo que se aproxima al código fuente final. Sea ( 3 , d ) el espacios tridimensional y sea f una imagen definida de 2 en . Sea G ( f ) = {( x, y ) ∈ 2 × / y = f ( x )} ⊆ 3 el gráfico de la función f : 2 → con la topología relativa ℑG ( f ) al espacio. Sea ϕ la función que determina el criterio de segmentación, definida por la distancia geodésica y γ ( A) = {a ∈ A : a elemento arbitrario de A} . Dado ε fijo, se crea el primer conjunto An = { x} para algún x ∈ G ( f ) , con n = 1.
Paso 1: Mientras ∃ y ∈ G ( f ) tal que y ∉ Ai ∀i = 1,… , n hacer pasos 2 y 3; si no existe y ∈ G ( f ) ir al paso 4.
Paso 2: Para i = 1,… , n si B3 ( y, ε ) ∩ Ai
≠∅ y
ϕ ( Ai , y ) < ∞ , en I = I ∪ {i} (siendo I un
conjunto de índices). Paso 3: Si
I ≠ ∅ entonces
Ai = Ai ∪ { y}∀i ∈ I ; en caso contrario n = n + 1 ;
An = An ∪ { y} . Paso 4: Una vez obtenido el cubrimiento S = ∪ Ai , se generan las componentes i∈I
5-3
conectadas C j . Debido a la presencia de ruido en imágenes provenientes de reconstrucción Tomográfica o MRI, originado en el proceso de adquisición o de reconstrucción de las mismas, si el criterio de segmentación propuesto es aplicado directamente a la imagen original se produce una sobre-segmentación, es decir, cada uno de los objetos está delimitado por más de una región (Vincent et al., 1991). La sobre-segmentación se puede disminuir mediante técnicas de pre-procesamiento. Por lo que se propone aplicar, en una primera etapa, un pre-procesamiento mediante Filtros Secuenciales Alternados (ASFs) de cerradura y apertura por reconstrucción. Estos filtros, definidos en el capítulo anterior, consisten en una iteración de operaciones de aperturas y cierres morfológicos por Reconstrucción con elementos estructurantes de tamaño creciente, siendo necesario utilizar un segundo elemento estructurante para la operación Reconstrucción. Estos filtros presentan la ventaja de filtrar los objetos deseados sin alterar la forma original, lo que produce menor distorsión en la imagen, y además mantienen las regiones conectadas de la imagen que describen detalles significativos (Pastore J., et al., 2007).
5.2 Aplicación del método propuesto En esta sección se describe una aplicación directa del método propuesto anteriormente para la segmentación automática del espacio intracraneal, entendida ésta como la separación del encéfalo del resto de los tejidos contiguos que normalmente carecen de interés y que tienen brillos similares. En la figura 1 se muestran los resultados obtenidos en las diferentes etapas de la segmentación propuesta en una imagen axial de RM pesada en T2. Primero se presenta la imagen original, a continuación la imagen después de aplicarle los filtros secuenciales alternados por reconstrucción donde se puede observar la región del cerebro homogeneizada, en la imagen c) se puede observar que los contornos extraídos forman una curva simple cerrada, por lo se puede aplicar la distancia geodésica para obtener una máscara del cerebro (imagen d). En la imagen e) se observa la segmentación del cerebro extraído de la imagen anterior. En f) se presenta la imagen original y el borde exterior del cerebro superpuesto a fin de poder apreciar la calidad de la segmentación obtenida.
5-4
(a)
(b)
(c)
(d)
(e)
(f)
Figura 1. Segmentación del cráneo y las meninges en una imagen coronal de RM pesada en T2. a) imagen original. b) imagen resultado de la aplicación de los filtros secuenciales alternativos por reconstrucción. c) contornos extraídos. d) imagen resultado de la aplicación de la distancia geodésica. e) imagen segmentada. f) imagen original superpuesta el borde exterior del cerebro.
En este caso al obtenerse una curva simple cerrada luego de binarizar el gradiente se aplicó directamente la definición de interior de una curva simple cerrada utilizando la distancia geodésica para extraer la componente conectada de la imagen que representa al cerebro. El siguiente ejemplo corresponde al caso particular en el cual no se obtuvo una curva simple cerrada después de aplicar la detección de bordes, por lo que no se puede aplicar la distancia geodésica para realizar la segmentación del espacio intracraneal, debiéndose aplicar el criterio de segmentación general.
5-5
(a)
(b)
(c)
(d)
(e)
(f)
Figura 2. Segmentación del cráneo y las meninges en una imagen coronal de RM pesada en T2. a) imagen original. b) imagen etiquetada. c) Superficie topográfica de la imagen. d) imagen segmentada por el método propuesto. e) mascara del cerebro. f) cerebro.
En la figura 2 se muestran los resultados obtenidos con el método propuesto en una imagen coronal de RM pesada en T2. Primero se presenta la imagen original, a continuación la imagen b) es el resultado de aplicarle a la imagen original un algoritmo clásico de etiquetamiento (labeling). La imagen c) representa la superficie topográfica de la imagen original sobre la cual se aplica el método propuesto. La imagen d) es la segmentación obtenida. Finalmente, en las imágenes e) y f) se observa la correcta 5-6
segmentación de cerebro. Una vez propuesto un nuevo método de segmentación es necesario validarlo, para esto es necesario contar con un índice de similitud que permita cuantificar la eficiencia del mismo. En el próximo capítulo se define un nuevo índice basado en la distancia de Hausdorff y la métrica definida a partir la diferencia simétrica.
5-7
6. Validación de la segmentación: un nuevo índice de similitud
6. Validación de la segmentación: un nuevo índice de similitud. Para cuantificar la eficiencia de un método de segmentación, es necesario llevar acabo experimentos de validación, lo cual consiste en comparar el resultado obtenido con algún modelo real (Barra and Lundervold, 2007, Bouix et al., 2007, Crum et al., 2006). La manera más directa para comparar una segmentación es realizar una simple inspección visual entre la segmentación realizada y una obtenida manualmente por un especialista. Sin embargo, esto no garantiza una validación debido a la gran variabilidad inter e intra-usuario. Una vez obtenida la segmentación de referencia, es necesario establecer alguna medida de similitud para cuantificar la precisión y exactitud del método de segmentación. En este capítulo se presenta un nuevo índice de similitud definido a partir de métricas no euclídeas.
6.1 Medidas de similitud Existe en la bibliografía un gran número de medidas o índices de similitud, entre los más utilizados se pueden mencionar: Coeficiente de Tanimoto (TC, Tanimoto Coefficient), se define como: TC ( A, B ) =
A∩ B A + B − A∩ B
(6.1)
donde ⋅ denota el cardinal del conjunto (Bouix et al., 2007, Jimenez-Alaniz et al., 2006, Santalla et al., 2007, Song et al., 2004, Song et al., 2007). Es decir la medida de Tanimoto
es la razón entre el número de elementos que los vectores tienen en común y el número de elementos distintos. En el caso particular de variables binarias. Las entradas de los dos vectores se pueden resumir en la siguiente tabla: A B
0 1
0 a c
1 b d
donde a representa el número de posiciones donde los vectores A y B coinciden en tomar el valor 0. Similarmente b representa el número de coincidencias donde A y B
6-1
CAPITULO 6
VALIDADCIÓN DE LA SEGMENTACIÓN: un nuevo índice de similitud
valen ambos 1. Mientras que c y d representan el número de no coincidencias. La medida de Tanimoto se reduce a: TC ( A, B ) =
a+d a + 2(c + b) + d
(6.2)
Coeficiente de Dice. A partir del coeficiente de Tanimoto se define el coeficiente
de Dice de la siguiente manera: DICE ( A, B ) =
2TC ( A, B ) 1 + TC ( A, B )
(6.3)
Coeficiente de exactitud. La medición de exactitud (ACC, Accuracy) en la
segmentación tiene en cuenta la cantidad de pixeles que han sido correctamente clasificados con respecto a la cantidad total de pixeles que se esperaba detectar. Este coeficiente se define como: ACC ( A, B ) =
A∩ B B
(6.4)
Matriz de Confusión. La matriz de confusión se utiliza para evaluar el resultado
de cualquier algoritmo de clasificación (Kohavi y Provost, 1998). Esta aplicación, permite cuantificar explícitamente cuantos pixeles han sido correctamente clasificados, pero además permite evaluar como se han propagado los errores erróneamente clasificados (Piovost et al., 1997). Si bien la matriz de confusión posibilita evaluar la segmentación obtenida, no resulta una manera resumida de expresar el resultado para efectuar comparaciones rápidas. Distancia de Hausdorff: En el capítulo 3 se definió formalmente esta métrica, la
cual mide el grado de semejanza entre dos conjuntos A y B que están en una posición fija uno respecto del otro. Una definición equivalente de esta distancia, usando el operador morfológico dilatación definido en el capítulo 4, es la siguiente: Sea ϑ el espacio formado por todos los subconjunto compacto de 2 no vacíos. Si K1 y K 2 denotan dos conjuntos compactos (no vacíos) de 2 (o simplemente dos elementos de ϑ ), y B ( λ ) la bola cerrada de radio λ , la cantidad:
{
}
H ⊕(K1, K 2) = inf λ : K1 ⊂ δ B( λ ) ( K 2 ) , K 2 ⊂ δ B ( λ ) ( K1 )
6-2
(6.5)
CAPITULO 6
VALIDADCIÓN DE LA SEGMENTACIÓN: un nuevo índice de similitud
define una métrica en ϑ , conocida como la métrica de Hausdorff. La identidad K1 ≡ K 2 implica H ⊕ = 0 ; inversamente si H ⊕ = 0 , entonces por definición K1 ⊂ K 2 y K 2 ⊂ K1 , por lo tanto K1 = K 2 . La simetría es una consecuencia inmediata de la definición. Para demostrar la desigualdad triangular, consideremos tres conjuntos compactos K1 , K 2 y K 3 con distancias asociadas: ρ1 = H ⊕(K 2, K 3) ;
ρ2 = H ⊕(K 3, K1) ;
ρ3 = H ⊕(K1, K 2)
Dado que K 3 ⊂ δ B( ρ ) ( K1 ) y δ B(ρ ) ( K3 ) ⊃ K 2 tenemos que: 2
1
(
)
K 2 ⊂ δ B(ρ ) δ B(ρ ) ( K1 ) = δ B(ρ +ρ ) ( K1 ) . 1
Similarmente
2
1
2
K1 ⊂ δ B(ρ +ρ ) ( K 2 ) . Luego ρ3 ≤ ρ1 + ρ2 . 1
2
Geométricamente, H ⊕ es el radio de la menor bola cerrada B tal que K1 esta contenido en el conjunto dilatado δ B( x ) ( K 2 )
y
K2
está contenido en el
conjunto δ B( x ) ( K1 ) .
Figura 1. Distancia de Hausdorff entre los conjuntos A y B
Esta medida presenta una limitación a la hora de ser usada para validar un método de segmentación de imágenes: “Puntos aislados influyen fuertemente en la distancia de Hausdorff” (Pastore J., et al., 2007). Si se considera el caso particular en el cual K 2 = K1 ∪ { x} donde x ∈ 2 es un punto distante de K1 , la distancia H ⊕ ( K1 , K 2 ) será igual a la d ( x, K1 ) , lo cual impide cualquier posibilidad de robustez al ruido, situación que ocurre frecuentemente en análisis de imágenes, para comparar conjuntos de puntos.
6-3
CAPITULO 6
VALIDADCIÓN DE LA SEGMENTACIÓN: un nuevo índice de similitud
En esta tesis se propone combinar la métrica de Hausdorff con la métrica definida a partir de la diferencia simétrica a fin de lograr que el índice propuesto resulte robusto respecto al ruido. Diferencia Simétrica. Sean A y B dos conjuntos, la diferencia simétrica entre A y B ,
denotada por A∆B , se define como: A∆B = ( A \ B ) ∪ ( B \ A )
(6.6)
Figura 2. Diferencia Simétrica
Sea ξ la familia de subconjuntos finitos de un conjunto X. La función d ∆ en ξ× ξ definida por: d ∆ ( A, B ) = ( A \ B ) ∪ ( B \ A ) = A∆B
(6.7)
cuantifica la diferencia entre dos contornos basándose en el área asociada a los mismos, la idea de aplicarlo es la de cuantificar la diferencia entre las áreas no contenidas por ambos conjuntos. Esta métrica en general no es acotada ni independiente del tamaño de A y B. En efecto, dos conjuntos con cardinales grandes que difieren en 3 elementos y dos con cardinales pequeños que también difieren en 3 elementos miden lo mismo por d∆ . Si normalizamos d ∆ por: A∆B d ∆n ( A, B ) = A ∪ B 0
( ξ, d ) es un espacio métrico y d ∆n
∆n
si
A∪ B ≠ ∅
en otro caso
resulta acotada por [ 0,1] .
( ξ, d ) es un espacio métrico si para todo A, B, C ∈ ξ , d ∆n
i)
(6.8)
d ∆ n ( A, B) = 0 ⇔ A = B , 6-4
∆n
satisface:
CAPITULO 6
VALIDADCIÓN DE LA SEGMENTACIÓN: un nuevo índice de similitud
ii)
d ∆ n ( A, B) = d ∆n ( B, A) ,
iii)
d ∆ n ( A, C ) ≤ d ∆ n ( A, B) + d ∆n ( B, C ) .
i) es inmediato pues A ∩ B = A ∪ B si y sólo si A = B . La segunda condición se satisface desde la propiedad conmutativa de las operaciones básicas de conjuntos. La condición iii) (desigualdad triangular) no es inmediata y requiere un mayor esfuerzo para su demostración: Demostrar la desigualdad triangular es equivalente a probar que: 1−
A∩ B B∩C A∩C +1− ≥ 1− A∪ B B∪C A∪C
(6.9)
Esta desigualdad es inmediata si, A ∪ B = ∅ , B ∪ C = ∅ o A ∪ C = ∅ . Sea ahora el caso en el que A ∪ B ≠ ∅ , B ∪ C ≠ ∅ y A ∪ C ≠ ∅ . La unión de una cantidad finita de conjuntos, siempre es posible escribirla como la unión disjunta de subconjuntos (figura 3), cuyos cardinales son: a = A \ (B ∪ C) , b = B \ ( A ∪ C) , c = C \ ( A ∪ B) , ab = ( A ∩ B ) \ ( A ∩ B ∩ C ) , bc = ( B ∩ C ) \ ( A ∩ B ∩ C ) , ac = ( A ∩ C ) \ ( A ∩ B ∩ C ) , abc = ( A ∩ C ) \ ( A ∩ B ∩ C ) ,
6-5
CAPITULO 6
VALIDADCIÓN DE LA SEGMENTACIÓN: un nuevo índice de similitud
Figura 3. Partición de la unión
Si se considera γ = ab + ac + bc + abc , la ecuación (6.9) puede escribirse en forma simplificada como: ab + abc bc + abc ac + abc + ≤ +1 a+b+γ b+c+γ a+c+ γ
(6.10)
Sin pérdida de generalidad se puede eliminar b de los denominadores, siendo suficiente demostrar que: ab + abc bc + abc ac + abc + ≤ +1 a+γ c+γ a+c+γ
(6.11)
Reemplazando 1 por γ / γ , y luego sumando las fracciones se tiene: (c + γ )(ab + abc) + (a + γ )(bc + abc) (ac + abc) γ + (a + c + γ ) γ ≤ (a + γ )(c + γ ) (a + c + γ ) γ
dado que
(a + γ )(c + γ ) = ac + a γ + cγ + γ 2 ≥ a γ + c γ + γ 2 = (a + c + γ ) γ
(6.12) es suficiente
mostrar que la desigualdad es verdadera para los numeradores, es decir: (c + γ )(ab + abc) + (a + γ )(bc + abc) ≤ (ac + abc ) γ + (a + c + γ ) γ
(6.13)
Partiendo del lado izquierdo de la desigualdad tenemos: (c + γ )(ab + abc) + (a + γ )(bc + abc) ≤ cγ + γ (ab + abc) + a γ + γ (bc + abc) = cγ + γ (ab + bc + abc + abc) + a γ ≤ cγ + γ 2 + γabc + a γ ≤ (ac + abc) γ + (a + c + γ ) γ.
(
)
Luego ξ, d ∆ n es un espacio métrico.
6-6
.
CAPITULO 6
VALIDADCIÓN DE LA SEGMENTACIÓN: un nuevo índice de similitud
Observaciones: -
Si A = B , d ∆ n ( A, B) = 0 .
-
Si A ∩ B = ∅ , d ∆ n ( A, B) = 1 .
6.2 Índice de similitud propuesto. Como propuesta adicional para esta tesis se propone un nuevo índice de similitud. La combinación lineal de la distancia de Hausdorff y de la diferencia simétrica, genera un nuevo índice el cual será denotado por H _ DSα , que mide la similitud espacial y la diferencia
de
las
áreas
de
los
contornos
comparados,
es
decir:
H _ DSα = α H ⊕ + (1 − α ) ε∆ , donde: H ⊕ ( A, B) , siendo k = max {diámetro( A), diámetro( B)} ; k
-
H ⊕ ( A, B) =
-
ε ∆ = d ∆ n ( A, B) el error de intersección de las áreas.
El factor de peso α establece el comportamiento del índice H _ DS α . Si se considera el factor de peso α = 0.5 se considera de manera equitativa los dos parámetros, si se utilizara α > 0.5 , H _ DSα cuantificará más la similitud espacial, mientras que si α < 0.5 , H _ DSα cuantificará la diferencia entre las áreas no contenidas por ambos contornos. En los casos extremos, cuando α = 0 o α = 1 , estaremos en presencia de la métrica definida a partir de la diferencia simétrica o la métrica de Hausdorff respectivamente. Es importante señalar que el índice H _ DS α debe ser menor o igual a un umbral T , para que el método de segmentación sea considerado aceptado. Ya establecido el nuevo índice de similitud para cuantificar la precisión y exactitud de un método de segmentación, es necesario disponer de imágenes que puedan ser tomadas como referencia, situación que se hace difícil en la práctica. Imágenes de referencia pueden lograrse por una segmentación manual realizada por un especialista o bien mediante simulaciones computacionales. El trazado manual de las diferentes estructuras que se desean detectar en una imagen es un trabajo arduo que suele consumir varias horas a un especialista o grupo de
6-7
CAPITULO 6
VALIDADCIÓN DE LA SEGMENTACIÓN: un nuevo índice de similitud
especialistas, aún si esta tarea se efectúa con una computadora. Además, los resultados de la segmentación pueden variar de un operador a otro, y sus resultados no son, en la mayoría de las veces, repetibles. De todas maneras, una adecuada segmentación realizada por especialistas es una tarea necesaria para la evaluación de métodos de clasificación automáticos o semiautomáticos. Por otro lado, imágenes provenientes de simulaciones computacionales presentan una segmentación de referencia objetiva dado que se conoce la distribución de los pixeles, como así también permiten evaluar el desempeño de un método de segmentación bajo condiciones de distorsiones conocidas.
6.3 Imágenes de prueba
6.3.1
Imágenes de prueba provenientes de simulaciones
En primer lugar el método propuesto será aplicado a imágenes simuladas provenientes de una base de datos (Simulated Brain Database, SBD) construida por Investigadores de la Universidad de McGill. Estos datos se disponen libremente y pueden ser utilizados para evaluar el desempeño del método propuesto, ya que se conoce la verdadera ubicación espacial de los píxeles (Montreal Neurological Institute, 2007). Esta base de datos consta de imágenes normales y patológicas obtenidas por simulación de un equipo de RM en tres secuencias: pesadas en T1, pesadas en T2 y pesadas según la densidad de protones (PD, Proton Density). Pueden elegirse estudios simulados configurando el ancho de corte (distancia entre cortes), el nivel de ruido y el nivel de no-uniformidad de la intensidad (INU) de la imagen. El nivel de ruido presente en la imagen puede elegirse variando la desviación estándar de ruido gaussiano que se suma a los canales reales e imaginario del simulador de resonador. Se indica como el porcentaje de ruido que multiplica al máximo valor de intensidad que presenta uno de los tejidos tomado como referencia (el rango entonces es de 0 a 100%). El ruido se calcula como ruido pseudoaleatorio gaussiano y se suma a la magnitud final que entrega el simulador.
6-8
CAPITULO 6
VALIDADCIÓN DE LA SEGMENTACIÓN: un nuevo índice de similitud
La INU se indica en porcentaje, de modo que, por ejemplo, para un nivel de 20%, el campo de no-uniformidades multiplicativo tiene un rango entre 0.9 y 1.1 sobre el área del cerebro. En la figura 4 se puede observar un corte pesado en T1 con diferentes combinaciones de ruido e INU, pudiéndose apreciar la degradación en la calidad de la imagen, lo que dificulta su segmentación, especialmente en los métodos que trabajan píxel a píxel.
6.3.2
Imágenes de prueba reales
Dado que las imágenes simuladas se alejan de la realidad, no debe pasarse por alto la valoración de un método con imágenes reales. Estos dos tipos de imágenes (reales y simuladas) poseen diferente rendimiento, no obstante, no son excluyentes, sino más bien deben actuar como complementos en la evaluación de un método. Para evaluar el método con imágenes reales, se utilizarán imágenes de la base de datos IBSR (Internet Brain Segmentation Repository) de cerebros sanos del Centro de Análisis Morfométrico del Hospital General de Massachussets, para las cuales está disponible la segmentación manual de los cerebros, realizada por expertos. Los cortes coronales de estas imágenes son de 256x256 píxeles con resolución 1x1 mm2 (IBSR 1997).
6-9
CAPITULO 6
VALIDADCIÓN DE LA SEGMENTACIÓN: un nuevo índice de similitud
INU = 0 %
INU = 20 %
INU = 40 %
N=0%
N=3%
N=7%
N=9%
Figura 4. Imágenes pesadas en T1 con distintos niveles de distorsión. Se observan todas las combinaciones de diferentes niveles de ruido (N) y de no-uniformidades en la intensidad (INU). La imagen sin distorsiones se encuentra en el extremo superior izquierdo y el peor caso en el extremo inferior derecho.
6-10
7. Resultados
6-11
7. Resultados En las siguientes secciones se muestran los resultados obtenidos al aplicar el método de segmentación desarrollado para esta tesis en imágenes de RM provenientes de simulaciones e imágenes reales provenientes de las bases de datos SBD y IBSR respectivamente. Además se evalúa su eficiencia con el índice H _ DSα propuesto en el capítulo anterior.
7.1 Resultados obtenidos en imágenes simuladas Para evaluar la robustez del método propuesto se segmentaron un total de 15 volúmenes completos con todas las combinaciones entre nivel de ruido: 0, 1, 3, 7 y 9% y niveles de INU: 0, 20 y 40%. Los estudios analizados consisten de 181 cortes, tomados cada 1 mm, con un volumen de vóxel de 1 mm3, de los cuales 121 cortes son considerados significactivos.
7.1.1
Imágenes simuladas sin distorsión
En la figura 1 pueden observarse los resultados del procesamiento de cuatro cortes elegidos arbitrariamente (#50, #80, #110, #140) de una imagen 3D obtenida por simulación sin distorsión de ningún tipo. En la primera columna se muestra la imagen original, en la segunda la segmentación objetivo o “Gold Standard”, en la tercer columna la segmentación lograda con el método propuesto y finalmente en la última columna la imagen original a la cual se le ha superpuesto el contorno objetivo en color rojo y el contorno que surge del método propuesto en color verde. Como puede apreciarse en todos los casos, comparando con la segmentación de referencia, los resultados obtenidos son visualmente similares a los de la simulación.
7-1
CAPITULO 7
Imagen Original
RESULTADOS
Segmentación
Segmentación
Superposición de
Objetivo
Propuesta
contornos
Figura 1: Resultados obtenidos en los corte #50, #80, #110 y #140 de una imagen simulada, sin distorsiones. (Ruido: 0, INU: 0).
Con el fin de evaluar las segmentaciones obtenidas de una manera más rigurosa, se calculó el índice H _ DSα en cada uno de los cortes.
7-2
CAPITULO 7
RESULTADOS
En la Tabla I se muestran estos valores y además se incluyen los valores de los índices DH (Distancia de Hausdorff), DHN (Distancia de Hausdorff Normalizada) y del índice DS que surge de aplicar la diferencia simétrica. CORTE
DH
DHN
DS
H _ DSα
#50
6
1.5028e-004
0.0416
0.0109
#80
5
1.2523e-004
0.0350
0.0176
#110
8
2.0038e-004
0.0361
0.0181
#140
13
3.2561e-004
0.1092
0.0248
Tabla I: Medidas de calidad de la segmentación obtenidas en 4 cortes (imágenes simuladas).
Se puede observar que los valores obtenidos para el índice H _ DSα son muy bajos aún en los cortes superiores donde los especialistas aducen tener mayores dificultades a la hora de realizar una segmentación manual.
7.1.2
Imágenes simuladas con ruido y inhomogeniedades de campo magnético.
distorsión
por
Con el fin de determinar la robustez del método frente a la presencia de ruido e inhomogeneidades de campo magnético se procesaron imágenes simuladas con diferentes niveles de ruido (0%, 1%, 3%, 5%, 7% y 9%) y de INU (0%, 20%, 40%). En la figura 2 se muestran los resultados para un nivel medio de ruido e inhomogeneidades: nivel de ruido de 3% y de INU de 20%. Los cortes son los mismos que se mostraron en la figura anterior. En la figura 3 se muestran los resultados obtenidos en el caso extremo, nuevamente se procesaron los mismos cortes pero ahora con el máximo nivel de ruido (9%) y de INU (40%) disponibles. Puede apreciarse en todos los casos, comparando con la segmentación de referencia, que los resultados obtenidos son visualmente muy similares a los de la simulación.
7-3
CAPITULO 7
RESULTADOS
Imagen Original
Segmentación
Segmentación
Superposición de
Objetivo
Propuesta
contornos
Figura 2: Resultado obtenido con nivel de ruido de 3% y de INU de 20%.
7-4
CAPITULO 7
Imagen Original
RESULTADOS
Segmentación
Segmentación
Superposición de
Objetivo
Propuesta
contornos
Figura 3: Resultado obtenido en el caso de máximo nivel de ruido y de INU disponible en simulación.
En la Tabla II se muestran los valores promedio y desviaciones estándar de los H _ DSα calculados en 121 cortes, para los distintos niveles de ruido y de INU disponibles.
7-5
CAPITULO 7
RESULTADOS
INU 0%
INU 20%
INU 40%
RUIDO 0%
H _ DSα
0.0183
0.0237
0.0244
σ
0.0048
0.0069
0.0053
RUIDO 3%
H _ DSα
0.0238
0.0251
0.0255
σ
0.0103
0.0123
0.0112
RUIDO 7%
H _ DSα
0.0246
0.0254
0.0258
σ
0.0100
0.0093
0.0113
RUIDO 9%
H _ DSα
0.0256
0.0258
0.0263
σ
0.0099
0.0110
0.0116
Tabla II: H _ DSα promedio obtenidos en imágenes 3D simuladas con diferentes distorsiones.
Figura 4: Índices de similitud obtenidos con el método propuesto para el espacio intracraneal.
7-6
CAPITULO 7
RESULTADOS
En la figura 4 se ven representados gráficamente los valores promedio del índice de similitud H _ DSα obtenidos con el método propuesto en imágenes simuladas para las distintas combinaciones de ruido (0, 3, 7 y 9%) y de INU (0, 20, 40%) disponibles (Tabla II). Puede observarse como se estabiliza el índice en un entorno del punto 0.025 a medida que aumentan los diferentes porcentajes de ruido y de INU. Si se afirma que un método de segmentación es robusto al ruido cuando el resultado de aplicarlo a una imagen con ruido es similar al de aplicarlo a la imagen sin ruido, los resultados obtenidos confirman la robustez del método propuesto al ruido.
7.2 Resultados obtenidos en imágenes reales Si bien las imágenes simuladas son de gran utilidad para evaluar la robustez de un método de segmentación dado que se conoce la exacta distribución espacial de los píxeles, éstas difieren de las imágenes que se obtienen en la práctica clínica. Por lo que una evaluación con imágenes reales es necesaria y complementaria. Teniendo en cuenta esto, se segmentaron 20 volúmenes de estudios reales cuya segmentación manual fue realizada por expertos, mediante un algoritmo semi-automatizado de seguimiento de contorno [Kennedy, Filipek y Caviness, 1989]. En la figura 5 se muestran algunos resultados y también se incluye la segmentación manual de algunos cortes a distintos niveles.
7-7
CAPITULO 7
Imagen Original
RESULTADOS
Segmentación
Segmentación
Superposición de
Objetivo
Propuesta
contornos
Figura 5: Resultado obtenido en el caso de máximo nivel de ruido y de INU disponible en simulación.
Una simple inspección visual permite afirmar que en los diferentes cortes los resultados obtenidos son visualmente similares cuando se comparan con la segmentación de referencia. Con el fin de evaluar, de manera más rigurosa y presisa, las segmentaciones obtenidas se calcularon los índices H _ DSα para los distintos cortes, los que se muestran en la Tabla III junto con los índices HHN y DS.
7-8
CAPITULO 7
RESULTADOS
CORTE
DHN
DS
H _ DSα
#1
7.6294e-005
0.0378
0.0189
#2
1.2207e-004
0.0456
0.0229
#3
1.2207e-004
0.0418
0.0210
#4
6.1035e-005
0.0312
0.0156
Tabla III: Medidas de calidad de la segmentación obtenidas en imágenes reales.
Los valores del índice H _ DSα obtenidos con imágenes reales no experimentaron cambios con respecto a los obtenidos con imágenes simuladas. El valor promedio y desviación estándar de los índices H _ DSα calculados en los 20 volúmenes fueron 0.0201 y 0.00998 respectivamente. Esto confirma que aún en el caso de las imágenes reales la segmentación propuesta sigue siendo robusta.
7.3 Discusión Los valores obtenidos para el índice H _ DSα tanto en las imágenes simuladas como en las reales son bajos, aun en las peores condiciones de nivel de ruido y de INU para el caso de imágenes simuladas, lo que permite asegurar la robustez del método propuesto. Cuando se probó el método con imágenes simuladas sin distorsiones el índice H _ DSα tomó siempre valores inferiores a 0.025. La utilización de distancias no euclídeas proveyó resultados estables y coherentes según se observó en los gráficos que muestran como el índice H _ DSα tiende a ser constante cuando se disminuye la calidad de las imágenes a segmentar (aumento del ruido y las INU). El criterio definido para generar el cubrimiento de la superficie podría variar. Podrían definirse, por ejemplo, criterios basados en la textura de la imagen, la utilización de otras métricas, entre otros, dependiendo de las características de la imagen a segmentar. Dada la relativa simplicidad de las operaciones involucradas, el método propuesto puede ser programado en cualquier lenguaje sin necesidad de motores de cálculo ni cualquier otra librería específica. Esto abre la posibilidad de implementarlo
7-9
CAPITULO 7
RESULTADOS
en hardware, por ejemplo a través de software insertado en un microprocesador, de manera de obtener una herramienta en tiempo real.
7-10
8. Conclusiones
8. Conclusiones En esta tesis se presentó un nuevo método para segmentar distintas estructuras en IRM y TAC utilizando distancias no euclídeas y conceptos de topología general. El método de segmentación propuesto permitió generar una partición de la imagen en regiones significativas. La aplicación de los filtros secuenciales alternados por reconstrucción en la etapa de pre-procesamiento resultó esencial para evitar una sobre-segmentación de la imagen. Para cuantificar la precisión y exactitud del método propuesto se definió un nuevo índice de similitud que combina una medida de similitud espacial a través de la métrica de Hausdorff y la diferencia de las áreas de los contornos comparados utilizando la diferencia simétrica entre conjuntos. Una vez definidos el método de segmentación y el índice de similitud, se utilizaron imágenes simuladas e imágenes reales procedentes de dos bases de datos que incluyen la segmentación objetivo, instrumento necesario para llevar a cabo la validación de cualquier método de segmentación. Los experimentos realizados con estas imágenes permitieron concluir que el método resulta robusto frente al ruido y distorsión por inhomogeniedades de campo magnético, dificultades inherentes a las IRM y TAC. Siendo las operaciones involucradas relativamente sencillas, los tiempos de cálculo resultaron bajos respecto a otros métodos descriptos en la bibliografía, lo que hace al método ser altamente adecuado para estudios en los que deben segmentarse una gran cantidad de imágenes. Además, este sistema puede ser programado en cualquier lenguaje sin requerir grandes motores de cálculo ni librerías especiales lo que abre la posibilidad de su futra implementación en hardware. Se concluye que el tratamiento de la imagen como un subconjunto del espacio tridimensional con la topología relativa al espacio geodésico permite lograr una partición de la misma con un índice de similitud H _ DSα inferir a 0.02. Es decir, con un 98 % de exactitud.
8-1
CAPITULO 8
CONCLUSIONES
Además se puede afirmar que el índice de similitud H _ DSα
es más
representativo que el que surge de la distancia de Hausdorff dado que se encuentra acotado superiormente por el valor 1, siendo además más robusto al ruido. Como líneas de trabajo futuras, se continuará trabajando en la mejora de la técnica propuesta para mejorar aún más los resultados obtenidos con el algoritmo propuesto. Así como también optimizar los mismos para reducir los requerimientos computacionales necesarios. Finalmente se propone evaluar exhaustivamente las posibles mejoras que puede ofrecer la utilización de otras métricas.
8-2
9. Bibliografía
9. Bibliografía -
Bangham, J.A. and Marshall S., (1998). “Image and Signal processing with mathematical morphology,” IEE Electronics & Communication Engineering Journal, 10, 117-128.
-
Barra V., Lundervold A., (2007). “A Collaborative Software Tool for the Evaluation of MRI Brain Segmentation Methods”. En proceedings de Lundervold, A. (Ed.) International Symposium on Information Technology Convergence (ISITC 2007). pp. 235-239. ISBN 978-0-7695-3045-1.
-
Berry K. J., and Mielke P. W., (1998). “A generalization of Cohen’s kappa agreement measure to interval measurement and multiple raters,” Educational, Psychological Meas., vol. 48, pp. 921–933.
-
Beucher S., (1990). “Morpholological segmentación”, J. Vis. Commun Image Represent., vol. 1, pp. 21-46.
-
Birkhoff G., (1967). “Lattice Theory”. American Mathematical Society, Providence, Rhode Island.
-
Bland J., and Altman D., (1986). “Statistical methods for assessing the agreement between two methods of clinical measurement,” Lancet, vol. 1, pp. 307–310.
-
Bouchet A., Pastore J., Moler E., (2008). “Image geodesic reconstruction by connected components”, revista IEEE America Latina. ISSN: 1548-0992.
-
Bouchet A., Pastore J., Ballarin V., (2007). “Segmentation of Medical Images using Fuzzy Mathematical Morphology”, Journal of Computer Science and Technology. JCS&T vol. 7 No. 3. pp 256-262, ISSN 1666-6038.
-
Bouix S., Martin-Fernandez M., Ungar L., Nakamura M., Koo M. S., Mccarley R. W., Shenton M. E. (2007). “On evaluating brain tissue classifiers without a ground truth”. Neuroimage, Vol. 36 (4), pp. 1207-1224. doi: 10.1016/j.neuroimage.2007.04.031.
-
Bouma C., Niessen W., Zuiderveld K., Gussenhoven E., and Viergerver M., (1996). “Evaluation of segmentation algorithms for intravascular ultrasound images,” Visualization and Biomed. Computing, pp. 203–212.
-
Braga-Neto U., (2004). “Multiscale Connected Operators”, Submitted to JM IV Special Issue on Mathematical Morphology after 40 Years, 2004.
-
Braga-Neto U. and Goutsias J., (2004). “Grayscale Level Connectivity: Theory and Applications”, IEEE Transactions on Image Processing, Vol. 13, No 12, pp. 1567-1580, 2004. 9-1
-
Callaghan P. 1995. “Principles of Nuclear Magnetic Resonance Microscopy. Clarendon Press”, Oxford, 2nd edition, 1995.
-
Castellanos R., Mitra S., (2000). “Segmentation of Magnetic Resonance Images Using a Neuro-Fuzzy Algorithm”. En proceedings de 13th IEEE Symposium on Computer-Based Medical Systems (CBMS '00). pp. 207. Washington, DC, USA, IEEE Computer Society. ISBN 0-7695-0484-1.
-
Chulho W., and Dong Hun K., (2007). “Region growing method using edge sharpness for brain ventricle detection”. En proceedings de SICE Annual Conference. pp. 1930-1933. ISBN 978-4-9077-6427-2. Couprie M. and Bertrant G., (1997). “Topological grayscale Watershed Transform”, SPIE Vision Geometry Proceedings, vol. 3168, pp. 136-146.
-
Courchesne E., Chisum H. J., Townsend J., Cowles A., Covington J., Egaas B., Harwood M., Hinds S., Press G. A., (2000). “Normal brain development and aging: quantitative analysis at in vivo MR imaging in healthy volunteers”. Radiology, Vol. 216 (3), pp. 672-682.
-
Crespo J., Schafer R. W., Serra J., Meyer F., Gratin C., (1997). “The flat zone approach: A general low level región merging segmentation method”, Signal Processing, vol. 62, pp. 37-60.
-
Crum W. R., Camara O., Hill D. L. G., (2006). “Generalized Overlap Measures for Evaluation and Validation in Medical Image Analysis”. IEEE Transactions on Medical Imaging, Vol. 25 (11), pp. 1451-1461.
-
Decencière F., Marshall S. and Serra J., (1997). “Application of the morphological geodesic reconstruction to image sequence analysis”, IEEE Image Signal Process, Vol. 144, No 6, pp. 339-344.
-
DeGraaf C., Koster A., Vincken K., and Viergerver M., (1992). “A methodology for validation of image segmentation algorithms,” Proc. IEEE Symp. ComputerBased Medical Systems, pp.17-24.
-
Dougherty, E. (1992): “An Introduction to Morphological Image Processing”, (SPIE, Washington).
-
Dougherty E. R., (1993). “Mathematical Morphology in Image Processing”, CRC Press. ISBN 0-8247-8724-2.
-
Dougherty, E. R. y Astola J., (1994). “An introduction to nonlinear image prossesing”, Tutorial Texts in optical engineering, vol. TT16.
-
Fan J., Zeng G., Body M., Hacid M.-S. (2005). “Seeded region growing: an extensive and comparative study”. Pattern Recognition Letters, Vol. 26 (8), pp. 1139-1156.
-
Facon J., (1996). “Morfología Matemática. Teoría y ejemplos”, Curitiba Brasil, CITS.
-
Filho E. R., (1980). “Teoria Elementar dos Conjuntos”. Livraria Novel S.A., Sao Paulo.
-
Gatica-Perez D., Gu C. and Sun M., (2001). “Extensive Partition Operators, Gray-Level Connected operators, and RegionMerging/Classification Segmentation Algorithms: Theoretical Links”, IEEE Transactions on Image Processing, Vol. 10, No 9, pp. 1332-1345.
-
Geman, S. and Geman, D., (1984). “Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images”. IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. PAMI-6, pp. 721-741.
-
Glasbey, C. A. y Horgan G. W., (1994). “Image analysis for the biological science”, Statistics in Practice, Series Editor Vic Barnett., Jonh Wiley and Sons.
-
González, R. y Woods, R., (1996). “Tratamiento Digital de imágenes”, Addison Wesley.
-
Gomes J. and Velho L., (1997). “Image Processing for Computer Graphics”, Springer-Verlag New York, EEUU.
-
Grau V., Mewes A.V.J., et al, (2004). “Improved watershed transform for medical image segmentation using prior information”, IEEE Trans. on Medical Imaging, vol. 23, no. 4.
-
Grätzer G., (1978). “General Lattice Theory”. Academic Press.
-
Kelley, J. L., (1975). “General Topology”, Springer Verlag, New York.
-
Hai Gaio, Ping Xue y Weisi Lin, (2004). “A new marker-based watershed algorithm”, IEEE ISCAS.
-
Hansen M. W., Higgins W. E., (1999). “Watershed-based maximunhomogeneity filtering”, IEEE Trans. on Image Processing, vol. 8, no. 7.
-
Hanbury A. and Serra J., (2001). “Morphological operators on the unit circle”, IEEE Transactions on Image Processing, vol. 10, no. 2, pp.1842-1850.
-
Heijmans H., (1997). “Connected Morphological Operators for Binary Images”, Probability Networks and Algorithms (PNA), PNA-R9708.
-
Hernandez S. E. and Barner K. E., (2000). “Joint region merging criteria for Watershed-Based image segmentation”, IEEE Trans on Image Processing.
-
Huttenlocher D. P., Klanderman G. A., and Rucklidge W. J., (1993). “Comparing images using the Hausdorff distance”, IEEE Trans. Pattern Anal. Machine Intell., vol. 15, pp. 850–863.
-
Image Pro-Plus (1999): The Proven Solution for Image Analysis. Image ProPlus Reference Guide for Windows TM. Version 4.1 Media Cybernetics.
-
Krestel E., (1990). “Imaging systems for Medical Diagnostics”, Siemens.
-
IBSR, (1997). http://www.cma.mgh.harvard.edu/ibsr.
-
Jackway P. T. and Deriche M., (1996). “Scale-Space Properties of the Multiscale Morphological Dilation-Erosion”, IEEE Trans.on Pattern Analysis and Machine Intelligence, vol. 18, no.1, pp.38-51.
-
Jain, A., (1998). “Fundamentals of Digital Image Processing”, Prentice Hall, Englewood Cliffs, New Jersey.
-
Jimenez-Alaniz J. R., Medina-Banuelos V., Yanez-Suarez O. (2006). “Datadriven brain MRI segmentation supported on edge confidence and a priori tissue information”. IEEE Transactions on Medical Imaging, Vol. 25 (1), pp. 74-83.
-
Keller, P. (1990): ‘Basic principles of Magnetic Resonance Imaging,’ (General Electric Medical Systems, Milwaukee, U.S.A.).
-
Lantuéjoul, C. and Beucher, S. (1981). “On the use of the geodesic metric in image analysis”, J. Microsc., 121, 39-49.
-
Lantuéjoul, C. and F. Maisonneuve (1984). “Geodesic methods in Quantitative image Analysis”, Pattern Recognition, 2, 177-187.
-
Liang Z. P., Lauterbur P. C., Ieee Engineering in Medicine and Biology Society. (2000). “Principles of magnetic resonance imaging : a signal processing perspective”, Bellingham, Wash, New York, SPIE Optical Engineering Press; IEEE Press. ISBN 0-7803-4723-4.
-
Lima, E. L., (1977). “Espacios Métricos”, Instituto de Matemática Pura y Aplicada. 2nd. Edition.
-
Marshall, S. y Sicuranza G., (2006). “Advances in nonlinear signal and image prcessing”, Eurasip.
-
Meschino G., Moler E. (2002). “Algoritmo de Crecimiento de Regiones con característicos de texturas: una aplicación en biopsias de médula ósea”. Proceedings del VIII Congreso Argentino de Ciencias de la Computación (Cacic 2002). Buenos Aires, 15-18 Octubre.
-
Meyer, F.y S. Beucher, (1990). “Morphological segmentation”, J. Visual Commun. Image Repres. 1, 21-45.
-
Moler E., Ballarin V., Rodríguez J. y Pastore J., (2001). “Segmentación Morfológica de partículas mediante técnicas iterativas de esqueletos por zonas
de influencia,” IX Reunión de Procesamiento de la Información y el Control, Santa. Fe, Argentina. -
Moler E. G. (2003). “Técnicas de procesamiento digital de imágenes aplicadas al cálculo de parámetros histomorfométricos no-euclidianos”. Revista Argentina de Bioingeniería, Vol. 9 (1), pp. 11-15.
-
Montréal Neurological Institute, (2007). MNI's BrainWeb dataset: http://www.bic.mni.mcgill.ca/brainweb/. Montréal Neurological Institute, McGill University.
-
Mukhopadhyay, S., Chanda, B., (2003). “Multiscale Morphological Segmentation of Gray-Scale Images”, IEEE Transactions on Image Processing, 12, 533-549.
-
Otsu N., (1979). “A threshold selection method from gray-level histograms”, IEEE Trans. on SMC, vol. SMC-9, pp. 62-66.
-
Pham D. L., Xu C., Prince J. L., (2000). Current methods in medical image segmentation. Annual Review of Biomedical Engineering, Vol. 2, pp. 315-37. doi: 2/1/315 [pii] 10.1146/annurev.bioeng.2.1.315.
-
Pastore J., Ballarin V., Moler E., (2007). “Quantification of the efficiency of segmentation methods on medical images by means of non-euclidean distances”, Journal of Physics Conference Series. ISSN 1742-6588 (Print), ISSN 1742-6596 (Online).
-
Pastore J., Moler E., Ballarin V., (2007). “Operadores Morfológicos Multiescala y Distancia Geodésica Aplicados a la Segmentación de Imágenes de Tomografía Axial Computada”, revista IEEE America Latina. vol. 5-1. ISSN: 1548-0992.
-
Pastore J., Moler E., Meschino G., (2005). “Segmentación de biopsias de médula ósea mediante filtros morfológicos y regiones homogéneas” Revista Brasileira de Engenharia Biomédica, vol. 21, n. 1, pp. 81-88, ISSN 1517-3151. 2005.
-
Pastore J, Moler E. and Ballarin V., (2005). “Segmentation of brain magnetic resonance images through morphological operators and geodesic distancea”, Digital Signal Processing, vol. 15-2 pp., 153-160. ISSN 1051-2004.
-
Pastore, J., Bouchet, A., M. Emilce, Ballarin, V., (2006). “Topological Concepts applied to Digital Image Processing,. Publicado. Publicado en el Journal of Computer Science and Technology, JCS&T Vol 6 No.2 pag. 80-84. ISSN 16666038.
-
Segmentation of Medical Images using Fuzzy Mathematical Morphology, Bouchet A., Pastore Juan Ignacio, Ballarin, Virginia. Aceptado para su publicación en Journal of Computer Science and Technology. JCS&T Vol. 7 No. 3. pp 256-262. October de 2007.ISSN 1666-6038.
-
Pastore, J., Moler, E., Ballarin, V., (2008). “Procesamiento Digital de Imágenes a través de Filtros Morfológicos Direccionales”. Revista Argentina de Bioingeniería de la Sociedad Argentina de Bioingeniería. ISSN 0329-5257.
-
Provost F. J., and Fawcett T., (1997). “Analysis and Visualization of Classifier Performance: Comparison Ander Imprecise Class and Cost Distributions,” Proc. Third International Conference on Knowledge Discovery and Data Mining, pp. 43–48.
-
Ronse C. and Heijmas H., (1991). “The algebraic basis of mathematical morphology. Part II: Openings and closings”, Comp. Vision Graph. Image Process: Image Understanding, 54, 74-97.
-
Sahoo P. K., Soltani S., Wong A. K. C., Chen Y. C., (1988). “A survey of thresholding techniques”. Computer Vision, Graphics, and Image Processing, Vol. 41 (2), pp. 233-260. doi: 10.1016/0734-189X(88)90022-9.
-
Santalla H., Meschino G. J. and Ballarin V. L., (2007). “Effects on MR images compression in tissue classification quality”. Journal of Physics: Conference Series, Vol. 90. doi: 10.1088/1742-6596/90/1/012061.
-
SDC (2001). SDC Morphology Toolbox for MATLAB 5. User’s Guide. SDC Information Systems.
-
Saghri, J.A., and Freeman, H., (1981). “Analysis of the Precision of Generalized Chain Codes for the Representation of Planar Curves, IEEE Journal of Pattern Recognition and Machine Intelligence, No. 5, pp. 533-539.
-
Salembier P., and Serra J., (1995). “Flat Zones Filtering, Connected Operators, and Filters by Reconstruction”, IEEE Transactions on Image Processing, Vol. 7, No 4, pp. 555-570.
-
Slichter P. 1996. “Principles of Magnetic Resonance”. Springer, New York, 3rd edition.
-
Soille P. and Pesaresi M., (2002). “Advances in Matematical Morphology aplied to geoscience and remote sensing”, IEEE Trans. Geoscience and remote sensing, vol. 40, pp. 2042-2055.
-
Song T., Angelini E. D., Mensh B. D., Laine A., (2004). “Comparison study of clinical 3D MRI brain segmentation evaluation”. En proceedings de Annual International Conference of the IEEE Engineering in Medicine and Biology Society. 3, pp. 1671-1674. San Francisco, CA, USA.
-
Song T., Jamshidi M. M., Lee R. R., Huang M., (2007). “A Modified Probabilistic Neural Network for Partial Volume Segmentation in Brain MR Image”. IEEE Transactions on Neural Networks, Vol. 18 (5), pp. 1424-1432.
-
Serra J., (1975). “Image Analysis and Mathematical Morphology”, Vol. I, Academic Press, London.
-
Serra J., (1992). “Image analysis and Mathematical Morphology”, Vol. II Academic Press.
-
Serra, J. and Vincent L., (1992). “An Overview of Morphological Filtering”, Circuits, Systems and Signal Processing. pp. 47-108.
-
Sijbers J., Poot D., Den Dekker A. J., Pintjens W., (2007). “Automatic estimation of the noise variance from the histogram of a magnetic resonance image”. Physics in Medicicine and Biology, Vol. 52, pp. 1335-1348.
-
Simmmons, G. F., (1963). “Introduction to Topology and Modern Analysis”, International Student Edition. McGraw-Hill Kogakusha, Ltd.
-
Szász G., (1963). “Introduction to Lattice Theory”. Academic Press.
-
Van Der Ville D., Nachtegal M., Van Der Weken., Kerre E. E., Philips W., Lemahien I., (2003). “Noise Reduction by fuzzy image filtering”, IEEE Trans. On Fuzzy System, vol. 1, no 4.
-
Vincent L., (1993). “Morphological Grayscale Reconstruction in Image Analysis: Applications and efficient Algorithms”, IEEE Transactions On Image Processing, vol 2, 176-201.
-
Williams G. W., (1976). “Comparing the joint agreement of several raters with another rater,” Biometrics, vol. 32, pp. 619–627.
-
Zijdenbos A., Dawant B. M., Margolin R. A., and Palmer A. C., (1994). “Morphometric Analysis of With Matter Lesions in MR Images: Method an Validation”, IEEE Transactions on Medical Imaging, 13(4), pp. 716-724.
Agradecimientos. Durante estos años son muchas las personas e instituciones que de una u otra manera han participado en este trabajo y a quienes quiero expresar mi gratitud por el apoyo y la confianza que me han prestado de forma desinteresada. En primer lugar quiero agradecer a las Doctoras Emilce Moler y Virginia Ballarín, por su constante apoyo y asesoramiento en todos los aspectos de la investigación y elaboración de esta Tesis, así como por la confianza depositada en mí. En segundo lugar al Ingeniero Manuel Gonzalez, que de igual modo me ha brindado su confianza. En tercer lugar destacar que el trabajo presentado en esta tesis ha sido posible gracias a la colaboración de diversas instituciones y es por ello que me gustaría agradecer sus aportes tanto en el terreno científico como en el personal: debo citar especialmente a la Universidad Nacional de Mar del Plata y al Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET). Finalmente quiero agradecer a mis compañeros de trabajo, compañeros en la ciencia y en los detalles de la vida diaria, quienes alegran y enriquecen con sus aportes mi trabajo diario.