Ecuaciones diferenciales geométricas en visión por ordenador y aplicaciones

^. UNIVERSIDAD DE LAS PALMAS DE GRAN CANARIA Departamento de Informática y Sistemas UNIVERSIDAD DE LAS PALMAS DE GRAN CANARIA DEPARTAMENTO DE INFORMÁTICA Y SISTEMAS j? ^ •:J TESIS DOCTORAL ECUACIONES DIFERENCIALES GEOMÉTRICAS EN VISIÓN POR ORDENADOR Y APLICACIONES Francisco J. Santana Pérez Las Palmas de Gran Canaria, Octubre 2004 Anexo I D. LUIS MAZORRA MANRIQUE DE LARA, SECRETARIO DEL DEPARTAMENTO DE INFORMÁTICA Y SISTEMAS DE LA UNIVERSIDAD DE LAS PALMAS DE GRAN CANARIA CERTIFICA, Que el Consejo del Departamento en su sesión de fecha del 29 de Octubre de 2004 tomó el acuerdo de dar el consentimiento para su tramitación, a la tesis doctoral titulada "ECUACIONES DIFERENCIALES GEOMÉTRICAS EN VISIÓN POR ORDENADOR Y APLICACIONES" presentada por el doctorando D. Francisco J. Santana Pérez y dirigida por el Doctor D. Luis Álvarez León y codirigida por el Doctor D. Luis Mazorra Manrique de Lara. Y para que así conste, y a efectos de lo previsto en el Art73.2 del Reglamento de Estudios de Doctorado de esta Universidad, firmo la presente en Las Palmas de Gran Canaria, a 29 de Octubre de 2004 que de Lara Anexo II UNIVERSIDAD DE LAS PALMAS DE GRAN CANARIA Departamento: "Departamento de Informática y Sistemas" Programa de Doctorado: "Percepción Artificial y Aplicaciones" Título de la Tesis ECUACIONES DIFERENCIALES GEOMÉTRICAS EN VISIÓN POR ORDENADOR Y APLICACIONES Tesis Doctoral presentada por D/DFrancisco J. Santana Pérez Dirigida por el Dr/a. D/DLuis Álvarez León Codirigida por el Dr/a. D/DLuis Mazorra Manrique de Lara El/la Director/a (firma) ector/a 'ma) Luis Álvarez León El/la Doctorando/a firma) uis Maz&rfá iVIanriatíe de Lara Francisco J. Santana Pérez TESIS DOCTORAL Autor: Director: Codirector: Título: Universidad: Departamento: Programa: Grado: Fecha: Francisco J. Santana Pérez Luis Álvarez León Luis Mazorra Manrique de Lara Ecuaciones Diferenciales Geométricas en Visión por Ordenador y Aplicaciones Universidad de Las Palmas de Gran Canaria Departamento de Informática y Sistemas Percepción Artificial y Aplicaciones Doctor en Informática Octubre - 2004 Tesis doctoral presentada por D. Francisco J. Santana Pérez, y dirigida por el profesor D. Luis Álvarez León y codirigida por el profesor D. Luis Mazorra Manrique de Lara, para la obtención del grado de Doctor en Informática. A Olga, Silvia y Paula, mis 3 mujeres Agradecimientos En primer lugar, destacar un agradecimiento especial a Luis Alvarez León, director de este trabajo, amigo y compañero. Gracias Luis por tu fuerza, por tu valía y sobre todo por tu empeño en que terminara este trabajo. No solo eres una persona estupenda sino que eres un Director de grupo ejemplar. A mi codirector, amigo y compañero de "dolencias algebraicas " Luis Mazorra por apoyarme siempre; y por confiar en mí para muchas cosas, no solo este trabajo. También agradecer a los compañeros y amigos que han hecho posible este trabajo, incluso indirectamente, entre risas, cafés y ratos compartidos. Gracias a Abraham, Paqui y Miguel. A mi compañero de despacho y amigo Miguel Alemán, por aguantarme ¡que no es poco! También por sus consejos y por sus ánimos. Y porque sé que siempre ha intentado ser exigente y riguroso con sus comentarios, pues así es él con sus cosas. Al director del Departamento de Informática y Sistemas, D. Santiago Candela Sola: ¡gracias por tu apoyo, por los medios y por tu amistad; y sobre todo por tu insistencia en la terminación de este trabajo!. A todos los que se me olvidan por citar y que se sientan aludidos también les agradezco su apoyo. Contenidos 1 Introducción. 1 1.1 Descripción General. Estado del Arte 1 1.2 Aportaciones originales de nuestro trabajo 5 1.2.1 Sobre la discretización de operadores no lineales 5 1.2.2 Sobre la Representación de Formas Planas 7 1.3 Estructura de nuestro trabajo 9 2 Principios del Análisis Multiescala Morfológico 11 2.1 Ecuaciones diferenciales e invariantes 13 2.2 Principios del Análisis Multiescala 16 2.3 Resultados Generales de la Teoría 22 2.4 Otros Ejemplos de Análisis Multiescala 29 2.5 Análisis Numérico 31 2.5.1 Discretización de la ecuación del calor 31 2.5.2 Discretización del gradiente 35 2.5.3 Discretización de ecuaciones no-lineales 37 2.5.4 Análisis Numérico de una Ecuación hiperbólica 42 i ii CONTENIDOS 3 Discretización de Operadores no lineales. 45 3.1 Discretización del operador r(M) 45 3.2 Minimización del Error cometido en la discretización 49 3.3 Algunas aplicaciones del operador T{U) 53 3.3.1 Estudio de la Evolución de radios en círculos 54 3.3.2 Evolución de Esquinas 71 4 Representación de Formas Planas. 75 4.1 Introducción 75 4.2 Evolución del área y del perímetro de una forma bajo la acción de un análisis multiescala morfológico 79 4.3 Representación morfológica invariante a similitudes de una forma. 80 4.3.1 Evolución del cociente isoperimétrico normalizado en escala 83 4.4 Representación morfológica afín invariante de una forma 85 4.5 Resultados Numéricos 88 4.6 Aplicación a la clasificación de formas 95 5 Aplicaciones: Detector Morfológico de Esquinas. 105 5.1 Extracción de puntos característicos y calibración de un sistema con múltiples cámaras 105 5.2 Detector morfológico de esquinas 106 5.2.1 Aplicación del detector de esquinas morfológico en condiciones no ideales 108 5.2.2 Resultados experimentales 109 6 Conclusiones. 117 7 Trabajos Futuros. 121 índice de Figuras 3.1 Círculo de radio 80 pixels 55 3.2 Evolución de los radios del círculo, con s=0.1, y umbral 50 ... . 58 3.3 Evolución de los radios del círculo, con s=0.1, y umbral 128 ... 58 3.4 Evolución de los radios del círculo, con s=0.1, y umbral 230 ... 59 3.5 Evolución de los radios del círculo, con s=0.5, y umbral 50 ... . 59 3.6 Evolución de los radios del círculo, con s=0.5, y umbral 128 ... 60 3.7 Evolución de los radios del círculo, con s=0.5, y umbral 230 ... 60 3.8 Evolución de los cortes de un círculo de radio 200 pixels, tomando s = 0.1 62 3.9 Evolución de los cortes de un círculo de radio 200 pixels, tomando s = 0.5 62 3.10 Elipse de radio mayor 80 pixels, y de radio menor 40 pixels .... 64 3.11 Evolución de los radios de la elipse (tomada como círculo), con s=0.025, y umbral 50 66 3.12 Evolución de los radios de la elipse (tomada como círculo), con s=0.025, y umbral 128 66 3.13 Evolución de los radios de la elipse (tomada como círculo), con s=0.025, y umbral 230 67 3.14 Evolución de los radios de la elipse (tomada como círculo), con s=0.05, y umbral 50 67 iii 1. Introducción. Uno de los objetivos que perseguíamos era el descubrir alguna otra técnica alternativa (a la anteriormente descrita y a la que otros autores han realizado hasta el momento de la realización de este trabajo) que permitiera utilizar un tipo de discretización de algunos operadores que aparecen en ciertas ecuaciones diferenciales, que al ser aplicados como filtros, resultan importantes. Por otro lado, uno de los objetivos de la visión por computador se basa en, dada una escena, intentar identificar objetos que forman parte de la misma. El principal problema de ello es que los objetos no tienen siempre las mismas proporciones en una escena o en otra, sino que pueden estar rotados, desplazados, deformados, o con otra transformación. Es por ello que su identificación resulta, en muchos casos, muy difícil de realizar. En este trabajo pretendíamos, como segundo objetivo de nuestras investigaciones, establecer una representación invariante de formas (figuras) geométricas planas, utilizando el análisis morfológico multiescala y sus propiedades. Para ello, en primer lugar se utilizan algunos resultados teóricos sobre la evolución del perímetro y el área de las formas. Esto nos permitirá aprender y averiguar algunos mecanismos que nos ayudarán posteriormente a encontrar fórmulas, basadas en los análisis mutiescala, que nos ayuden a identificar determinadas figuras planas, basándonos en la evolución su área y de su perímetro en las distintas escalas. En caso de tener transformaciones de similitud, el invariante geométrico propuesto se basa en la evolución normalizada en escala del cociente isoperimétrico de la forma. En caso de transformaciones geométricas afines generales el invariante geométrico se basa en la evolución normalizada en escala del área. Presentamos además algunos resultados numéricos para evaluar el rendimiento de los modelos propuestos. El método que nosotros proponemos en este trabajo consiste en utilizar la evolución del área y/o perímetro de la forma a través de las escalas utilizando diferentes análisis multiescala morfológicos como herramientas básicas para extraer una representación global escala-espacial de la forma. Los métodos de representación de formas juegan un papel muy importante en los sistemas de reconocimiento y análisis de objetos. Según la clasificación de los métodos de análisis de formas propuestos por Pavlidis [Pav78] y Loncaric [Lon98], por métodos de representación de formas se entienden métodos que nos 1. Introducción. proporcionan una representación no numérica de la forma (por ejemplo un grafo). La descripción de la forma se refiere a los métodos que determinan descriptores numéricos de la forma y que podrían suponer el paso siguiente a la representación de formas. Dentro de los métodos de descripción de formas, podemos distinguir dos clases. Por un lado, los métodos basados en el contorno de la forma (también llamados externos) y otro los métodos basados en características globales de la forma (también llamados internos). El segundo objetivo principal de esta segunda parte de nuestro trabajo va a basarse en la aportación de las propiedades de invarianza morfológica y geométrica de los análisis multiescala morfológicos para determinar una representación de formas global fiable. Las representaciones de formas en la escala espacial lineal han sido estudiadas por diversos autores: Witkin [Wit84] propone una aproximación de filtrado en escala espacial mediante el seguimiento de los puntos de inflexión en las imágenes filtradas por gausianas. Asada y Brady [AB86] propusieron una representación denominada the curvature primal sketch. Los contornos de la forma son filtrados con funciones gaussianas con ancho incremental para obtener una representación multiescala de la forma basada en la curvatura de los contornos. Mokhtarian y Mackworth [MM92] proponen también una representación de los contornos de las formas en la escala espacial basada en la evolución de las curvaturas a través de las escalas. En el contexo de los espacios de escala morfológicos, Maragos [Mar89] propuso una representación del espectro de patrones basada en la evolución del área de la forma obtenida mediante la apertura de la forma con un disco de medida incremental. Cohignac et al., [CLM94] y [CM95], propusieron un método de reconocimiento de formas invariantes afines basados en el análisis multiescala morfológico invariante afín. Utilizaron el análisis multiescala para recuperar puntos característicos en la forma. Lisani et al. [LMMMOO], utilizaron el análisis multiescala invariante afín para suavizar las imágenes antes de hacer una codificación local de los elementos de la forma. El método que nosotros proponemos en esta memoria consiste en utilizar la evolución del área y/o perímetro de la forma a través de las escalas utilizando diferentes análisis multiescala morfológicos como herramientas básicas para extraer una representación global escala-espacial de la forma. Para ello en una primera parte de este segundo bloque de nuestro trabajo, una vez introducidos algunos aspectos teóricos, veremos en detalle cómo hemos 1. Introducción. encontrado dos invariantes, para dos tipos de formas distintas, basados en la evolución del área y del perímetro de las formas. En una segunda parte, veremos cómo encontrar un criterio de similitud mediante una definición de distancias que nos permitirán encontrar formas similares dentro de los dos conjuntos de formas definidos. 1.2 Aportaciones originales de nuestro trabajo Tal como se ha citado en el apartado anterior, hemos dividido nuestro trabajo en dos objetivos principales. Es por ello que vamos a establecer brevemente qué aportaciones originales propias hemos propuesto para cada uno de ellos. De todos modos, todas las aportaciones de nuestro trabajo quedan detalladamente establecidas en cada capítulo. 1.2.1 Sobre la discretización de operadores no lineales. • Análisis direccional del error de discretización. En este trabajo se propone una nueva forma de analizar el error cometido al discretizar ciertos operadores diferenciales no lineales. Hacemos un análisis direccional del término del error de dicretización, lo cual nos permite fijar los grados de libertad inherentes al proceso de discretización. A partir de este análisis proponemos un nuevo algoritmo de discretización óptimo en el sentido de que el error de discretización es minimizado en la dirección del gradiente. Hasta el momento de la realización de este trabajo, normalmente y por simplicidad, la técnica utilizada para discretizar operadores no lineales involucrados en ecuciones diferenciales era el discretizar cada uno de los operadores por separado. Nosotros utilizamos un esquema distinto: discretizamos el operador no lineal como un único operador diferencial independiente. Esto nos permite aplicar ciertas propiedades de los operadores que no se podrían aplicar discretizando los operadores lineales que lo componen de forma independiente. Este tipo de discretización la utilizaremos para la aplicación de filtros para imágenes. A la hora de discretizar los operadores no lineales, procedemos a una primera minimización del error 1. Introducción. 6 según los estándares convencionales (minimizando según la aproximación polinómica que deseamos). Pero en nuestro estudio, también procedemos a la minimización del error en una determinada dirección: gradiente y ortogonal del gradiente. Esto se ha hecho debido a que la derivada de una función toma su mayor valor (mayor error) en la dirección al gradiente, y su menor valor (menor error) en la dirección ortogonal al mismo. • Estudio comparativo exhaustivo de diferentes técnicas de discretización. A partir del conocimiento teórico de la solución de la ecuación diferencial subyacente para datos iniciales como funciones indicatrices de círculos, elipses, y esquinas, hacemos un estudio experimental comparativo sobre diferentes técnicas de discretización para los operadores diferenciales que nos ocupan. Realizamos una triple comparativa en la que intervienen distintos valores que podemos dar a un parámetro, AQ, que aparece en nuestro esquema de discretización de operadores diferenciales no lineales, en la que se reflejan claramente en primer lugar nuestros resultados comparados con otros dos: uno de "elección natural" de la que hablamos en el capítulo en cuestión y otro resultado de un artículo que aparece en el que se estiman los valores de los parámetros según las distintas regiones de la imagen [AM94c]. En esta comparativa analizamos la variación del radio de un círculo y de una elipse, debido a que sabemos las evoluciones teóricas que las mismas han de seguir según el operador discretizado que aparezca en la ecuación diferencial que se está aplicando a cada imagen. • Aplicación a la detección de esquinas y la calibración de cámEiras. La detección con alta precisión de puntos singulares en la imagen, como pueden ser las esquinas, es un problema de gran importancia en visión por ordenador. A partir de un estudio teórico sobre la variación de una esquina utilizando el modelo de análisis multiescala, y de las técnicas de discretización propuestas aquí, hemos desarrollado en colaboración con Don Carmelo Cuenca, miembro de nuestro grupo investigador, un nuevo algoritmo de detección de esquinas que permite localizar esquinas con una precisión subpixel (error medio inferior a 0.5 pixels). Este algoritmo ha sido utilizado con éxito por el profesor Don Carmelo Cuenca en el ámbito de la calibración de cámaras. 1. Introducción. El algoritmo se basa en un estudio de cuál debe ser la variación teórica de una esquina de 90°, utilizando distintos valores de los parámetros estudiados y con distintos valores de pasos discretización. Como anexo a nuestro trabajo incluimos un detector de esquinas basado en nuestros resultados realizado por un compañero de nuestro Departamento y colega de nuestro Grupo de Investigación. 1.2.2 Sobre la Representación de Fornicis Planas. • Csiracterización de los análisis multiescala morfológicos. Habitualmente, en la literatiira sobre el tema, no se explotan todos los grados de libertad que podemos tener al trabajar con análisis multiescala morfológicos; es decir, se utilizan casi exclusivamente los generados por la ciirvatura media y el modelo invariante afín. En este trabajo mostramos que si relajamos la hipótesis de que el análisis multiescala sea invariante al cambiar de signo el dato inicial, entonces aparecen nuevos grados de libertad que serán de gran interés para facilitar la caracterización de una forma. Concretamente, mostramos que un análisis morfológico invariante por similitudes depende exclusivamente de tres parámetros que determinan completamente el operador diferencial. Por otro lado, mostramos también que el análisis multiescala morfológico invariante afin depende de dos parámetros. Aunque esta caracterización se deduce fácilmente de resultados precedentes en la literatura, lo que es realmente novedoso es, que aparentemente, hasta ahora nadie haya utilizado el potencial que ofrecen estos grados de libertad que aparecen en el operador diferencial. • Representación de formas inv£iriante por similitudes. Proponemos una nueva manera de representar formas planas, invariante por similitudes, basada en el seguimiento a través de las escalas del cociente isoperimétrico de una forma a partir de un análisis multiescala morfológico. Utilizando el esquema de discretización numérica de operadores diferenciales propuesto también en esta tesis, proponemos un nuevo algoritmo para hacer el seguimiento de una forma a través de las escalas y extraer en cada escala la información de área y perímetro necesarios para evaluar el cociente isoperimétrico. • Representación de formas invariante por transformaciones afines. 1. Introducción. 8 Proponemos una nueva manera de representar formas planas, invariante por transformaciones afines, basada en el seguimiento a través de las escalas del área de una forma a partir de un análisis multiescala morfológico invariante afín. • Compatración de formas. Definición de nuevas distancias. Proponemos una nueva manera de evaluar la distancia entre formas tanto desde el punto de vista de invarianza por similitudes, como del punto de vista de invarianza por transformaciones afines. En el caso de la invarianza por similitudes, proponemos una distancia basada en la combinación de la evolución del cociente isoperimétrico utilizando tres análisis multiescala invariantes por similitudes. En el caso de la invarianza por transformaciones afines, también proponemos una distancia basada en la combinación de la evolución del área utilizando tres análisis multiescala invariantes por transformaciones añnes. Se han establecido dos conjuntos de imágenes diseñados exclusivamente para estudiar la evolución de los dos invariantes geométricos propuestos (uno para evaluar la evolución del cociente de área invariante afín normalizado en escala y otro para evaluar el cociente isoperimétrico normalizado en escala), de forma que sean significativos los resultados numéricos obtenidos. Utilizamos una base de datos con imágenes plangis representando distintas formas de peces que se ha desarrollado en la Universidad de Surrey (ver [MAK96] para más detalles) en la que aparecen 200 formas distintas. Se han rotado, impreso, escaneado (con la consiguiente introducción de ruido inherente a los métodos utilizados) algunas de ellas y se han añadido a la base de datos. A partir de ella, intentamos encontrar las formas más parecidas a una forma dada. Tanto para el caso de las formas euclídeas como para el de las formas inviariantes afines se han definido unos criterios de distancia que permitan discriminar las formas y presentar numéricamente las más "similares" según las fórmulas definidas. Incluso, para obtener un comportamiento discriminatorio más fuerte, se ha combinado la información de diversos análisis multiescala. 1. Introducción. 9 1.3 Estructura de nuestro trabajo El trabajo que presentamos está estructurado de la siguiente forma: En primer lugar introducimos el problema objeto del análisis y desarrollo de nuestro trabajo [Capítulo 1]. A continuación explicamos los principios del análisis multiescala para dar una breve descripción de por qué queríamos desarrollar este trabajo y en dónde empezó nuestro interés por el mismo. Asimismo, explicamos cómo estaba el campo de los Análisis Multiescala Morfológicos en el momento de desarrollar nuestro trabajo. [Capítulo 2] Una vez presentado el problema, nos dispusimos a estudiar cómo discretizar algunos operadores no lineales [Capítulo 3], pero no como convencionalmente se hacía hasta ahora, es decir, discretizando los operadores lineales que intervenían en la ecuación por separado para posteriormente sustituirlos en la ecuación original, sino estudiando la discretización del operador no lineal como único operador diferencial independiente. Esto nos permite aplicar ciertas propiedades de los operadores que no se podrían aplicar discretizando los operadores lineales que lo componen de forma independiente. Además, como aplicación de nuestro esquema de discretiazación, utilizaremos dicha discretización sobre operadores no lineales para la aplicación de filtros a imágenes. Como complemento adicional, mostramos ,en el último capítulo, una aplicación de la utilización de esta discretización de operadores no lineales en un "detector de esquinas" [Capítulo 5] según el trabajo del colega D. Carmelo Cuenca Hernández en su Tesis Doctoral presentada en la Universidad de Las Palmas de Gran Canaria (ver [Cue03]). Debido a que es un extracto de otro trabajo, adjuntamos la bibliografía a la que hace referencia el mismo. Como segunda parte de nuestro trabajo presentamos un enfoque que permite detectar algunas formas específicas. Nos interesaba la forma en que podrían utilizar los análisis multiescala morfológicos para discriminar ciertas formas [Capítulo 4]. Para ello, proponemos una representación invariante de formas geométricas utilizando el análisis morfológico multiescala. 1. Introducción. 10 En un primer lugar, veremos como algunas formas evolucionan según un invariante morfológico basado en el cociente isoperimétrico normalizado en escala de las formas y otras lo hacen según un invariante morfológico basado en el cociente de superficie invariante afín normalizado en escala. Veremos algunos experimentos de nuestras propuestas sobre una base de datos real desarrollada en la Universidad de Surrey en la que aparecen multitud de peces de distinta forma y tamaño y en la que pudimos probar nuestras funciones de similitud que se basan en la invarianza del perímetro y del área de las formas en diferentes casos. En segundo lugar, y dentro de este segundo bloque, estudiamos un criterio de distancia que para cada uno de los dos casos definidos anteriormente, que nos permitirá determinar qué formas son más parecidas agrupándolas y ordenándolas según esos criterios que no son más que criterios de similitud basados en los análisis multiescalas. Para finalizar, analizamos las conclusiones de nuestro trabajo. Hemos intentado reflejar nuestras reflexiones acerca de los resultados obtenidos y de las pruebas y re-organizaciones que estos resultados han supuesto para nuestro trabajo original. [Conclusiones]. También reflejamos, en un último capítulo, las tareas en las que proponemos seguir trabajando en el futuro por su interés (según nuestra opinión) y su posible utilidad en la investigación de este campo. [Trabajos Futuros]. Por último, damos paso a la Bibliografía utilizada y recomendada para entender este trabajo. [Bibliografía] Capítulo 2 Principios del Análisis Multiescala Morfológico En este capítulo, vamos presentar una visión global de los análisis multiescala morfológicos en el contexto de la visión por ordenador, así como una breve descripción de los esquemas numéricos que habitualmente se utilizan para su implementación. Los resultados presentes en este capítulo pueden encontrarse de forma más extendida en las siguientes referencias: [ALM92], [AGLM92c], [AGLM92b], [AGLM92a], [AGLM93a], [AM94a], [AM94c], [AM94d], [AM94b], [AE97]. En lo que sigue, consideraremos que una imagen es una función / : 3?" —> 3? donde en general n = 2, aunque en algunos casos estudiaremos también n — 1 ó n = 3, hoy en día, los ordenadores son capaces de trabajar con imágenes de una gran definición (tamaño) y calidad, por ello, en general las imágenes con las que trabajamos son de una gran complejidad, y para poder extraer de ellas algún tipo de información, (objetos presentes en la imagen, etc.), dichas imágenes deben ser simplificadas. La simplificación consiste en general en intentar eliminar elementos de menor importancia para poder discriminar mejor las propiedades importantes de la imagen. Dicho coloquialmente: " queremos eliminar los árboles para poder observar el bosque'\ Por supuesto, la primera cuestión que aparece es que en ocasiones "los árboles" pueden ser más importante que el "bosque". Ello introduce de forma natural una noción de escala. Nosotros podemos mirar la imagen a diferentes escalas. En una escala fina los detalles que aparecen como importantes son los árboles, y a una escala más grosera, los detalles que resaltan están referidos a la configuración total del bosque. Esta reflexión nos plantea 11 12 2. Principios del Análisis Multiescala Morfológico un problema importante y en general irresoluble: ¿ Cual es la mejor escala para mirar una imagen?, obviamente no existe en general una escala mejor que otra, todo depende del tipo de detalle que queramos observar. El tema central de estudio de un análisis multiescala es el siguiente: partimos de una imagen inicial que está a una determinada escala de resolución y nos planteamos estudiar métodos que nos permitan pasar de esta imagen a otra que esté a una resolución más grosera. La teoría que desarrolla estos métodos se denomina ^^ Análisis Multiescala de Imágenes ó Scale-Space''' y ha recibido una gran atención en los últimos años tanto por matemáticos, como por ingenieros dedicados al tratamiento de Imágenes. Matemáticamente, el Análisis Multiescala se puede formalizar de la siguiente forma: Dada ima imagen / : 3Í" —> 9Í, un análisis multiescala viene determinado por una familia de transformaciones {Tt}t>Q donde el parámetro t representa la escala, de tal forma que para cada imagen / , Tt(/) es una nueva imagen que representa la imagen / a una escala más grosera dada por t . Históricamente, los primeros ejemplos de Análisis Multiescala han sido diseñados a partir de convoluciones. es decir: Tt{f){x)^ f K{t,y-x)f{y)dy (2.1) donde K{t, x) representa un núcleo de convolución. A continuación, a título ilustrativo, pondré 3 ejemplos de Análisis Multiescala que han sido frecuentemente empleados. Por simplicidad los escribiré en dimensión 1, Km{t,x) 1 Kc{t,x) = nt'^ + x'^ 1 :r2 Kgit,x) = 'A-Kt El primer núcleo K^{t,x) determina como Análisis Multiescala una media del valor de la imagen en un entorno de radio t , el segundo núcleo Kc{t, x) es conocido como densidad de Cauchy, y el tercer núcleo Kg{t, x) determina una función gaussiana. Los tres, corresponden a distintos modelos de Análisis Multiescala. Como veremos, existen muchas otras formas de definir Análisis Multiescala, incluyendo por supuesto modelos no-lineales. La principal pregunta que vamos 2. Principios del Análisis Multiescala Morfológico 19 Lo que nos indica que da lo mismo hacer el cambio de contraste y a continuación el análisis Tt{f), que primero el análisis Tt{f) y a continuación el cambio de contraste. Estableceremos también un principio ligeramente más fuerte cuando permitimos que la función de contraste g{.) pueda ser también estrictamente decreciente. El hecho de tomar funciones decrecientes, corresponde a realizar una inversión de video de la imagen, que nos indica que percibimos de la misma forma un objeto claro sobre fondo obscuro que el mismo objeto oscuro sobre fondo claro. Definición 7 Invarianza Morfológica fuerte. Diremos que un análisis Tt{f) verifica el principio de invarianza morfológica fuerte si verifica el principio de Invarianza morfológica para funciones g{.) estrictamente crecientes o decrecientes. Estos principios morfológicos son incompatible con la linealidad, por tanto, los análisis Tt{f) generados a través de convoluciones, que son lineales, no pueden satisfacer este principio. Ejemplo 3 Consideremos el caso de un análisis Tt{f) lineal dado por una convolución. La invarianza morfológica implicaría: / K{t,y - x){g o f){y)dy = g o / K{t,y - x)f{y)dy para cualquier función creciente g y cualquier imagen f. Si g{.) es lineal, es decir g{s) = as + b, entonces la anterior igualdad se cumple. Sin embargo, normalmente los cambios de contraste son no-lineales, en cuyo caso la anterior igualdad no se cumple. Tómese por ejemplo g{s) = s^. Ejemplo 4 Veamos como existen sin embargo otro tipo de análisis Tt{f) que sí verifican la invarianza morfológica. Consideremos el análisis Tt{f) definido por: T,(/)(a;)= sup f{y) (2.4) donde Btix) representa la bola centrada en x y de radio t. Este operador se conoce con el nombre de dilatación en la terminología de la teoría de la morfología matemática. La invarianza morfológica se verifica trivialmente puesto que si g : 3? —> 3Í es estrictamente creciente, entonces sup{gof) = gosiip{f). (Sin embargo no se verifica el principio de invarianza morfológica fuerie). Por otro lado, este 20 2. Principios del Análisis Multiescala Morfológico análisis verifica todos los principios propuestos anteriormente. Efectivamente la comparación local es trivial dada la forma del análisis. La causalidad y la regularidad salen de las siguientes estimaciones fáciles de comprobar. Tt+h{f){x) = sup f{y) = yeBt+h{x) = sup ( sup f{y)] =n{f)oT,{f) yeBh(x) \yeBt(x) J además, si f{x) — c + p^{x — XQ) + ^{X — a;o)*A(x — XQ) se tiene: j . Ttt+h{f) ~" / / \ II II Limh^o+— j^ {XQ) =11 p II Los siguientes y últimos principios que plantearemos están referidos a las de invarianza geométrica. El primero de ellos es la invarianza euclidiana que determina que el análisis es completamente independiente de la posición y orientación en el espacio y se formaliza de la siguiente manera Definición 8 Invarianza Euclidiana. Sea S G 3?" x 3?" una matriz ortonormal y b ^ ^"' un vector. Se considera la transformación hsfi : 3?" -^ 3Í" definida por hB,b{x) — Bx + b. Entonces se verifica: TtU0hBfi)=Tt{f)0hB,b es decir, es lo mismo trasladar y rotar antes o después de aplicar el análisis Tt{f). Este principio nos indica que no hay preferencia por ninguna posición u orientación en el espacio. El último principio que vamos a establecer es la invarianza por transformaciones afines generales. Definición 9 Invarianza afín. Sea A G 3Í"' x 3Í" una matriz no singular y b E W^ un vector. Se considera la transformación h^^b : 5í" —> 9Í" definida por hA,b{x) = Ax + b. Entonces se verifica que existe una función t'{t, A) tal que Tt{fohA,b)^Tt'it,A)if)°hA,b además ^{t,XId) > 0. 2. Principios del Análisis Multiescala Morfológico 21 La condición ||(í, A) > O se puede interpretar de la siguiente manera: Si consideramos la afinidad A = Xld que corresponde a una expansión de la imagen, entonces, cuanto mayor sea A mayor es la escala necesaria en el análisis para recuperar la imagen. Por otro lado, ello también nos indica que no podemos esperar en general que t'{t,A) = t como en el caso euclidiano puesto que una afinidad puede cambiar la definición de la imagen y por tanto ello también cambiará la escala. Si bien la necesidad de la invarianza euclidiana resulta obvia, la importancia de la invarianza afín no parece tan clara. Sin embargo, una afinidad representa como veremos un tipo de proyección particular de un espacio tridimensional a un espacio bidimensional. Consideremos un plano de proyección dado por un punto P = (^1)^2,^3) y dos vectores directores m = (mi, m2, iris) y n = (ni, n2, na). Un punto en el plano se representará como p + xm + yn, donde {x, y) representan las coordenadas locales del punto en el plano. Si consideramos por simplicidad que el foco o punto a través del cual realizamos la proyección es el (0,0,0), entonces, dado un punto {x, y, z) en el espacio su proyección (x, y) en el plano a través del punto (0,0,0) viene dada por las dos expresiones siguientes: " _ -j:(p2n3-p3n2)-3/(p3ni-pi"3)-z(piW2-p2"l) x{rn2n3—rnzri2)+y{'m3n-í—rn-iriz)+z{rn\n2—'m.2n\) - __ -x{m2P3-m3P2)-y{Tn3pi-mip3)—z{mip2-m2P\) " x(rn2n3—razn2)+y{m3n\—m\nz)+z{min2—m2n\) donde en el denominador aparece la ecuación de un plano paralelo al plano de proyección que pasa por foco. Ahora bien, si nosotros tenemos en nuestro mundo tridimensional un objeto incluido en un plano (ima puerta, una ventana, los lados de una mesa, etc..) la proyección anterior que es una aplicación de ^ en 3?^ se puede entender como una aplicación de 9?^ en 3?^. Efectivamente, si establecemos un sistema de referencia en el plano donde se encuentra el objeto, cualquier punto del objeto (o del plano) se puede escribir como {x, y,z) = q+xl+yr donde g,l,r e ^^ y {x,y) representan las coordenadas locales del objeto. Por tanto, la fórmula que determina la proyección, también determina una correspondencia entre {x,y) y {x,y). Esta aplicación es una afinidad en el caso particular de que el objeto se encuentre en un plano paralelo al plano de proyección en cuyo caso el denominador de las fórmulas que determinan la proyección es constante. Este es el caso, por ejemplo, de tomar diferentes fotografías de un objeto plano, moviéndonos en planos paralelos a él. Tendremos que la proyección del objeto en cada fotografía corresponde a diferentes afinidades del objeto. Si el objeto 22 2, Principios del Análisis Multiescala Morfológico no se encuentra en un plano paralelo al plano de proyección pero la distancia entre el objeto y el punto de proyección es mucho mayor que la distancia entre el punto de proyección y el plano de proyección, lo que sucede habitualmente en una cámara fotográfica, entonces, el denominador de la fórmula que determina la proyección fluctúa poco. En este caso, una afinidad representa una aproximación de una transformación proyectiva entre planos. Bajo este punto de vista, la invarianza afín es muy importante porque representa un primer paso para abordar el problema de la invarianza proyectiva necesaria para el reconocimiento de objetos tridimensionales a través de sus proyecciones en planos. Para profundizar sobre las aplicaciones de la geometría proyectiva al tratamiento de imágenes véase [Fau93]. 2.3 Resultados Generales de la Teoría En esta sección enunciaremos algunos teoremas que determinan a partir de los principios enunciados en la sección anterior como son los Análisis Multiescala posibles. Teorema 1 (Fundamental) . Si un Análisis Multiescala Tt{f) satisface causalidad, comparación local y regularidad, entonces u{t,x) = Tt{f){x) es una solución de viscosidad de la siguiente ecuación diferencial: ut{t,x) = F{D\Du,u,x,t) (2.5) donde D^u representa la matriz de segundas derivadas espaciales de la función u{t,x), Du es el vector gradiente y F{A,p,c,xo,t) la función definida en el principio de regularidad. Por otro lado, si u{t, x) es una solución de viscosidad de la anterior ecuación el análisis Tt{f) definido por Tt{f){x) — u{t, x) satisface los principios de causalidad, comparación local y regularidad. Una primera versión de este teorema fue demostrada en [AGLM93a]. Para una demostración simplificada véase [AM94c] (Apéndice 1). Este resultado nos muestra la íntima relación entre los análisis multiescalas y las ecuaciones en derivadas parciales. La Teoría de soluciones de viscosidad de ecuaciones en derivadas parciales, véase por ejemplo [CIL92] desarrollada por M.G. Crandal, PL. Lions, etc.. permite definir y estudiar soluciones incluso discontinuas de ecuaciones diferenciales 2. Principios del Análisis Multiescala Morfológico 23 y es un marco adecuado para el estudio de ecuaciones fuertemente no-lineales donde los métodos clásicos resultan insuficientes. Consideremos el análisis Tt{f) dado por la convolución con una gaussiana. En este caso observamos que la función F{.) definida en el principio de regularidad es F{A,p, c, XQ, t) = Traza{A). Por tanto la ecuación diferencial asociada es : ut = Uxx + Uyy + ... = Atí (2.6) Otro Ejemplo que ya podemos presentar es el caso del análisis dado por la dilatación Tt{f){x) = supy^Q^MÍiv)- En este caso habíamos observado que la función F{.) viene dada por F{A,p,c,xo,t) —1| p || y por tanto la ecuación diferencial asociada es: Ut =11 Du II (2.7) El siguiente resultado nos muestra como la ecuación del calor (2.6) o equivalentemente la convolución con una función gaussiana. representa im caso especial dentro de los Análisis Multiescala lineales. Teorema 2 La ecuación del calor determina el único Análisis Multiescala lineal que satisface causalidad fuerte, comparación local, e invarianza euclidiana. Este resultado clásico ha sido demostrado por varios autores en distintos trabajos, como Koenderink, Babaud, Witkin,etc. En el contexto de esta teoría una demostración de este resultado puede encontrarse en [AGLM93a]. Por lo tanto, en el contexto de estos principios, dentro de la clase de análisis Tt{f) lineales, el mejor es el asociado a la ecuación del calor. Sin embargo este análisis no satisface la invarianza morfológica ni la invarianza afín. Para llegar a ellas deberemos trabajar con análisis Tt{f) no-lineales. A continuación nos centraremos en el caso de dimensión 2. El siguiente resultado, demostrado también en [AGLM93a] simplifica considerablemente la forma del Análisis Multiescala. Teorema 3 Si un Análisis Multiescala satisface causalidad, comparación local, regularidad, invarianza morfológica e invarianza eucUdea entonces u(t,x,y) = Tt{f){x,y) es una solución de viscosidad de la siguiente ecuación diferencial: ut=\\Vu\\G{t,curv{u)) (2.8) 24 2. Principios del Análisis Multiescala Morfológico donde curv{u) denota la curvatura de las lineas de nivel, es decir, cada punto (í, X, y) está incluido en una linea de nivel de la forma: {{x,y) : u{t,x,y) = C} lo que determina una curva que tendrá una cierta curvatura. En términos de derivadas parciales la curvatura se puede escribir como: curv[u) — —^ 3 (2.9) veamos con algo más de detalle esta fórmula. Dado un punto (ío,a;o,í/o) del conjunto {(a^,y) : u{t,x,y) = C} existe una curva {x{s),y{s)), {xo,yo) = {x{so),y{so)) y u{t,x{s),y{s)) = C Vs (2.10) La curvatura en el punto {xo,yo) de la curva, viene dada por la razón entre la variación del ángulo de la pendiente y la variación de la longitud de arco. Formalmente esto se escribe como: arctan(4^) - arctan(^) curv(u)(tQ,xo,yo) = lim ,, , un cálculo directo de este límite nos lleva a: curv{u){to,xo,yo) = § (2.11) (x'isoy + y'isoy)-' veamos como podemos expresar la curvatura en términos de derivadas parciales de la función u{t,x,y) para obtener la expresión (2.9). Si derivamos respecto a s la igualdad (2.10) obtenemos: U:c{t, x{s), y{s))x'(s) + Uy{t, x{s), y{s))y'{s) = O por tanto existe una función 7(5) tal que x'{s) -=-f{s)uy{t,x{s),y{s)) y'{s) = -^{s)ux{t,x{s),y{s)) finalmente sustituyendo estas expresiones en (2.11) obtenemos la fórmula (2.9) que determina la curvatura en términos de derivadas parciales. 2. Principios del Análisis Multiescala Morfológico 25 La curvatura de las lineas de nivel es una propiedad intrínseca de la geometría de dichas curvas y por supuesto no depende en absoluto de los cambios de contraste. De hecho, como conclusión del teorema anterior observamos que la curvatiira es el único operador diferencial de segundo orden que verifica esta propiedad. Ejemplo 5 Si en la ecuación general anterior (2.8) consideramos como casos particulares G{t, curv{u)) = ±1 obtenemos los operadores de la morfología matemática conocidos como dilatación y erosión que corresponden a las ecuaciones diferenciales: ut = ±\\ Vu II Otro ejemplo de ecuación muy conocida que cae dentro de este grupo es la ecuación de curvatura media que corresponde a elegir G{t,curv{u)) = t-curv{u). Es decir: Uf =11 Vií II t • curv{u) esta ecuación tiene la propiedad de que verifica además el principio de invarianza morfológica en sentido fuerte, es decir es invariante por cambios de contrastes crecientes y decrecientes y esta normalizada respecto a la escala, es decir es invariante por transformaciones del tipo {t,{x,y),u) -^ {Xt,{Xx,Xy),u), una forma equivalente de escribir esta ecuación es la siguiente UyUxx '^UxUyUxy "T "^x^ ui + % el operador diferencial de segundo orden que se encuentra a la derecha de la igualdad, puede interpretarse como la derivada direccional de la función u{t, x, y) siguiendo la dirección ortogonal al gradiente, que corresponde a la dirección de mínima variación de la función u{t,x,y). Por tanto podemos decir que la ecuación produce una difusión de la imagen a lo largo de las lineas de nivel. Veamos una interpretación geométrica de la ecuación general (2.8) que nos permite visualizar como evoluciona una forma presente en la imagen a través de las escalas. Por una forma entendemos cualquier componente conexa de una linea de nivel dada por {{x, y) : u{t, x,y) = C}. Consideremos como antes que dicha curva se puede parametrizar como (x(s),y(s)). La dirección normal a la curva en cada punto s viene dada por 26 2. Principios del Análisis Multiescala Morfológico el vector: {-y'{s),x'{s)) n = ^yx'isoy + y'isoT si expresamos la normal en términos de derivadas parciales de u{t, x, y) obtenemos: Vu n = „ '^^ II denotemos ahora por {x{t, s), y{t, s)) a la evolución de la forma o linea de nivel a través de las escalas, es decir u{t, x{t, s), y{t, s)) = C. Si derivamos esta expresión respecto a t, obtenemos: ut + XtUo, + ytUy = O si sustituimos Ut por su valor siguiendo la ecuación (2.8) obtenemos: por tanto el sistema de ecuaciones {xt,yt) = -G{t,curv{u))ñ determina una solución de la anterior ecuación que podemos interpretar geométricamente como que un punto se mueve siguiendo la dirección normal a una velocidad que viene dada por la fiinción G{t, curv{u)). Nótese que la evolución de un punto depende exclusivamente de la geometría de la linea de nivel donde se encuentra y no depende en absoluto de la presencia de otras líneas de nivel cercanas. Ejemplo 6 Consideremos el caso en que {x{t,s),y{t,s)) una familia de circunferencias de radio R{t) = ^Jx'^{t,s) +y'^{t,s). La ecuación anterior es equivalente a: xt = -G{t,4^^y'' R{t)'R{t) yt--G{t,4rO-^ R{t)'R{t) de donde podemos obtener fácilmente que R{t) satisface la ecuación: 2. Principios del Análisis Multiescala Morfológico 27 las soluciones de esta ecuación determinan la evolución del radio. Por ejemplo en el caso de la dilatación o erosión (G = ±1) obtenemos que R'it) es constante lo cual significa que el radio de las circunferencias disminuye o aumenta, (siguiendo el signo de G) a la misma velocidad. Es decir R{t) = Ro^t. En el caso de considerar la ecuación de la curvatura media {G{t, k) = tk, obtenemos que el radio R{t) satisface: R'it) = R{t) y esta ecuación tiene por solución R(t) = y/R^ — f^. Lo que determina la evolución del radio Como puede constatarse existe un amplio abanico de posibilidades, cambiando la elección de la función (j(í, s), de modelos de Análisis Multiescala que verifican todos los principios propuestos salvo la invarianza afín. Para finalizar esta sección expondremos el "gran" resultado de esta teoría: existe \m único modelo que verifica todos los invariantes propuestos hasta ahora más la invarianza afin. El resultado que vamos a presentar fue obtenido por dos grupos de investigación de manera independiente. Por un lado un grupo formado por investigadores de la Universidad Paris IX y la Universidad de Las Palmas de Gran Canaria, y por otro lado otro grupo formado por investigadores americanos e israelies (véase [ST92],[ST93]). Teorema 4 Existe un único Análisis Multiescala normalizado respecto a la escala satisfaciendo causalidad, comparación local, regularidad, invarianza morfológica fuerte e invarianza afín, y viene dado por la ecuación Ut = t3 [UIUXX - 2UxUyUxy + ulUyy) ^ (2-13) Además, dada una afinidad definida por una matriz A, se tiene que t'{t,A) = t^/det{A). La primera demostración de este resultado a través de una formalización axiomática se encuentra en [AGLM93a]. En lugar de concentrarnos en la demostración del resultado, nos centraremos en su interpretación. En primer lugar nótese que esta ecuación corresponde a un caso particular de la ecuación general (2.8) tomando G{t,s) = Í353. 28 2. Principios del Análisis Multiescala Morfológico A continuación veremos las implicaciones de la invarianza afín que nos indica que para cualquier transformación aii ai2 y para cualquier t >0, existe t' = ty/det{A) tal que Veamos ahora que esta igualdad implica que efectivamente la ecuación está normalizada respecto a la escala . La transformación {x,y) —>• {Xx,Xy) es una afinidad que tiene por determinante det(yi) = A^. Por tanto siguiendo el resultado del teorema tendremos que t'{t,A) = tX, por tanto, si u{t,x,y) es una solución de la ecuación, entonces dada cualquier constante A, v{t, x, y) = u{tX, xX, yX) también es solución. Consideremos ahora una afinidad más compleja dada por la matriz cuyo determinante es áet[A) — A7. A título ilustrativo comprobemos que efectivamente la invarianza afín se verifica. Veamos que si u{t,x,y) es solución, entonces v{t,x,y) = u(ty/)rf,xX,yj) también es solución. Efectivamente, podemos escribir vt{t, X, y) = y/yfUt{t^/X^, xX, y-f) = t^ ((^Jí^xx - 2v^V:,y + vlvyy){t, X, y)y . Veamos ahora que sucede cuando una linea de nivel inicial corresponde a una circunferencia. Razonando como hemos hecho anteriormente podemos deducir que si R{t) es el radio de la circunferencia en la escala t, dicho radio verifica la siguiente ecuación diferencial ordinaria R'{t) = '' RitYs cuya solución es : 2. Principios del Análisis Multiescala Morfológico 35 Si calculamos Au en el punto central a través de la anterior fórmula obtenemos: 2 1 Au{hio, hjo) = 7^ + (1 - 7)^ ahora bien, si rotamos 45 grados la imagen inicial entorno al punto (/i¿o, hjo) obtenemos como imagen: 1 1 0 1 0 0 0 0 0 Si calculamos de nuevo Au en el mismo punto obtenemos: 1 2 Au{hio, hjo) = 7— + (1 - 7)— Por lo tanto si queremos que ambos valores de Au coincidan, debemos elegir 7 = |. Hablando en términos de teoría de la señal e a convolucionar la imagen con la siguiente máscara: 7 = |. Hablando en términos de teoría de la señal el calculo de Au nos llevaría 1 3 1 3 1 3 1 3 8 3 1 3 1 3 1 3 1 3 /l2 Si denotamos Aufj = Au{kn, hi, hj) podemos discretizar tal y como hicimos en dimensión 1 la ecuación del calor (2.6) obteniendo esquemas explícitos o implícitos según tomemos el valor de la derivada respecto al tiempo hacia adelante o hacia atrás. 2.5.2 Discretización del gradiente. Siguiendo el desarrollo de Taylor mostrado anteriormente obtenemos la siguiente expresión para el gradiente: K,)x-(i-7)^"Hr'""''^- Ah I „, ^-t+l.J+l "i-l,J+l+"t I (""+l.j+l~"H-l..j-l+""-l,.;+l~'""-l,j-l) donde 7 es de nuevo un parámetro a elegir. Teniendo en cuenta que la norma del gradiente es invariante por rotaciones, en particular lo es para rotaciones de 36 2. Principios del Análisis Multiescala Morfológico 45 grados, de donde deducimos, utilizando el mismo argumento que para el Aw que 7 = 2 — \/2. Por tanto, estamos calculando u^ utilizando la máscara: y Uy utilizando: 1 i 4^ -(2-v^) -2(v^-l) -(2 - v^) 0 0 0 (2-v^) 2(V^-1) (2-x/2) -(2 - ^) 0 (2-v^) 2(A/2-1) 0 -2(V2-1) -(2 - v^) 0 (2-x/2) 4^ Una observación interesante es que podemos llegar a la misma discretización del gradiente utilizando un método de optimización. Efectivamente, si consideramos la forma lineal: p{x, y) = ul^ + ax + hy e intentamos ajustar a, h para que dicha forma lineal aproxime lo mejor posible a la imagen en el entorno 3x3 del punto, ello nos lleva a minimizar una función de energía. Si consideramos como energía la función: E{a,b) = [u^^^^^ - ul^ - haf + [uUj - ul^ + ha)'' (2.14) + ( u, j+i <, -hhY + {ui,_,- ui^+ hty +^ «+i,,+i - <i - ha-hbf + ^«-ij-i-<.+ ha + hby 3 H ;= {U'L, ,^^-U. ^¿-1,J+1 íj hh + ha)' 1 donde los elementos diagonales los hemos modulado por la distancia al punto central (\/^). Entonces podemos obtener fácilmente que los valores a, 6 que minimizan la anterior energía corresponden exactamente a los valores de (w¿^j)x y k^,i)v calculados anteriormente. 2. Principios del Análisis Multiescala Morfológico 37 Por supuesto existen otras muchas formas de discretizar el gradiente. La forma que hemos presentado posee un buen grado de simetría. Sin embargo posee un punto débil y es que en el caso de que en una discontinuidad aislada donde en el punto central la imagen tiene un valor, y en el resto de los puntos posee otro valor el gradiente siguiendo esta discretización es nulo (0,0), lo que en ciertas aplicaciones puede ser perjudicial. Por ejemplo en algunos de los modelos que hemos visto en la sección anterior se utiliza la norma del gradiente para discriminar elementos de poca importancia o ruido. En estos casos, para calcular la norma del gradiente, puede resultar más conveniente modificar las fórmulas anteriores, sustituyendo (w"+ij — •""-1^) Por |w¿Vij — 'ÍÍ"J| + Pi^j "~ '"F-ijl' i'^i'+ij+i ~ K-i,j+i) por F^Yij+i - •"•"j+il+ Pi^j+i ~ u^-ij+i\, etc.. Ello nos determina entonces una aproximación de |(w"j)x | y K'iíi^j)?/!, para eliminar el valor absoluto del gradiente debemos discriminar entre 4 posibilidades que son: (IK,).|, |K,),|), (-|K,)x|, |«,).|), (IK,)x|,-!K,-)yl) Y {~\{''^i',j)x\,—\{u!¡'j)y\). Para hacerlo, podemos, por ejemplo, evaluar para cada opción la energía E{a, b) descrita anteriormente, y quedarnos con la opción de menor energía. 2.5.3 Discretización de ecuaciones no-lineales. Consideremos en primer lugar el caso de un operador no-lineal como Habitualmente, la discretización de un operador diferencial conlleva dos etapas. En primer lugar, se discretiza cada derivada parcial. Ux, Uy, Uxx, Uxy, Uyy como un operador independiente utilizando algún criterio de optimización, véase por ejemplo [VF94], y posteriormente se sustituye su valor en la expresión del operador diferencial que se quiere discretizar, en este caso ^{u). El enfoque que hay que aqui vamos a utilizar es distinto, vamos a discretizar S>(w) globalmente como un único operador diferencial. La ventaja de hacerlo de esta forma, es que introducimos en la discretización propiedades específicas del operador ^{u) que no pueden manifestarse estudiando cada derivada parcial por separado. Cocretamente procederemos de la siguiente forma: Supondremos calculado (ux, Uy) utlizando las técnicas descritas en el apartado anterior. A continuación, utilizando el desarrollo en serie de Taylor tal y como hicimos en el caso del laplaciano obtenemos: (2.15) 38 2. Principios del Análisis Multiescala Morfológico A2(w¿+lj + Ui,j+l) + X^iUi+ij-i + M¿+ij_i) + + Xiiui+ij+i + líj+ij+i))] + 0{h) donde AQ, Ai, A2, A3, A4 deben satisfacer las relaciones Al = 2Ao - ul A2 = 2Ao - ul A3 = -Ao + Q.b{UyUj, + ul + ul) A4 = -Ao + 0.5{-UyUx + ul + ul) quedando el parámetro AQ como un parámetro libre que elegiremos en base a criterios geométricos y de estabilidad. En general tendremos que AQ es una función del vector gradiente: Xo{ux,Uy). Con respecto a la estabilidad, como se demuestra en [AM94c] (lema 3 Pg. 42) es importante que los coeficientes Ai, A2, A3, A4 sean nonegativos. Desafortunadamente dada la forma que tienen estos coeficientes ello es imposible. Efectivamente, si, por ejemplo Ux > Uy > O tendremos que: Al > A2 y As > A4 ahora bien A2 > O =» Ao > -^ ul + ul — UxUy A4 > o =» Ao < ^ -^ pero estas dos condiciones sobre Ao son incompatibles puesto que ul ul+ulU^Uy Y - 2 además observamos que cuanto mayor es A2 menor es A4. Para minimizar el valor negativo de estos coeficientes definiremos Ao como el promedio de las dos funciones que determinan las regiones de positividad de A2 y A4, es decir: Xo{U:„Uy) = ^ (2.16) 2. Principios del Análisis Multiescala Morfológico 39 Por supuesto, esta definición es válida sólo en la región {ÍX^ > Uy > 0}, donde los coeficientes AQ, Ai, A2, A3, A4 serían entonces: Ao = 0.25(2w^ + ^ ~ UxUy) Al = 0.5(2lí2 -U^- Ua:Uy) A2 = 0.5(w^ - u^Uy) A3 = 0.2b{ul + Su^Uy) A4 = 0.25(u^ - UxUy) Por simetría, los coeficientes AQ, Ai, A2, A3, A4, serán los mismos en la región {ux < Uy <0}. Podemos expresar este procedimiento como una máscara no-lineal, que cambia en cada punto y cuyos coeficientes son: Uy+3UxUy 4 Uy—UxUy 2 Uy UxUy 4 2 UxUy - 2ul - ul 2u^—ufi—UxUy 2 Uy UxUy 4 li^—UxUy 2 U^+3UxUy 4 Por otro lado, siguiendo los valores de {uj;,Uy) obtenemos, utilizando el mismo razonamiento que en esta primera región, que: En la región {\ux\ > \uy\ and u^Uy < 0} los coeficientes son: ' Ao = 0.25(2M2 + ^,2 ^ UxUy) Al = 0.5(2íx2 -ul-\- UxUy) A2 = 0.5(W^ - UxUy) A3 = 0.25(ííJ + UxUy) A4 = 0.25(w^ — ZuxUy) En la región {\uy\ > \ux\ and UxUy > 0} obtenemos ' Xo = 0.25{2ul + ul-UxUy) Al = 0.b{ul - UxUy) A2 = 0.5{2Uy — ulUxUy) A3 = 0.2b{ul + SuxUy) A4 = 0.25(íí^ - UxUy) Finalmente, en la región {\uy\ > \ux\ and u^Uy < 0} obtenemos 40 2. Principios del Análisis Multiescala Morfológico Ao = 0.25(2^^ + «I + UxUy) Al = 0.5{ul + u^Uy) A2 = 0.5(2i¿^ -ul + UxUy) A3 = 0.25{ul + UxUy) A4 = 0.25(t¿^ — SuxUy) Nótese además que está discretización verifica la siguiente importante propiedad: Si el gradiente {ux, Uy) señala alguna de las direcciones principales, (los ejes, o las diagonales), entonces el operador '^{u) sólo depende de la variación de tí, en la dirección ortogonal. Por ejemplo si [u^, Uy) = (o, 0) entonces AQ = 0.5a^, Ai = a^, A2 = A3 = A4 = O, o si {ux,Uy) = {a, a), entonces AQ = 0.5a^, A3 = a^, Ai = A2 = A4 = 0. No es difícil comprobar que esta propiedad no se verifica si para aproximar '^{u) discretizamos de forma independiente las derivadas parciales. Una vez discretizado el operador diferencial 9(w), podemos abordar ahora la discretización de las ecuaciones que involucran este operador. Empezaremos por la ecuación de ciirvatura media propuesta en [ALM92] u, = Pdl VG *«II) :^^^ X y utilizemos la notación Í/"^ = u{nk,ih,jh), gfj = g{\\ VG * u^j \\ ) y %j{D'u^,Du') = {U\J)IÍUY:J)XX2{u\^^)x{uyy{u^j)xy+ {uyiKj)yy Plantearemos dos estrategias de discretización. En primer lugar un esquema explícito que viene determinado por: u: "+^ — Qi'^ Ci¡ í n2„,n ^,J ul^ _ %^^{D'u^,Du-) si despejamos v!¡^^ obtenemos <f = <A + KMU^ + ^IVi,^) + <M3-^ + <j+i) + El estudio de la estabilidad de este esquema no se puede realizar utilizando técnicas de análisis de fourier puesto que la ecuación es no-lineal. Sin embargo, una condición necesaria de estabilidad es que el coeficiente a"^- sea nonegativo (en caso contrario un dato inicial positivo podría dar lugar a un valor negativo). Ahora bien el cálculo de a"^, si Ux >Uy > O, nos lleva a: h'''' {uWl + {ul^)\ 2. Principios del Análisis Multiescala Morfológico 41 y como O < gl^ < 1, y si w, > w, > O entonces O < ''^^'^'i^f^:^^^'^" < 2, concluimos que a"^- > O si p < 2. Lo que determina una condición necesaria de estabilidad. Experimentalmente podemos comprobar que de hecho, dicha condición es suficiente y que el algoritmo se comporta bien cuando ^ < 2. En segundo lugar plantearemos un esquema implícito de la forma: <I'-<j _„n^i,ÁD'u-'-\Du-) Para calcular u^t^ es necesario resolver un sistema lineal de ecuaciones. Dicho sistema se puede escribir de la siguiente forma: <x:^'=<j+K^^-h+<:IJ)+^Mo-^+<Si)+ Para aproximar la solución del sistema resulta my efectivo utilizar un algoritmo recursivo basado en el método de Gauss-Seidel. Sea 2m el número de , i__ iteraciones que se van a emplear para pasar de u^j a u^j^. Denotamos por u^j ^™ _i_1 TL I '"^ rr | la aproximación de u^J en el paso 1. Para calcular ÍX^ ^"^ a partir de w- ^"^, si / es impar recorremos la imagen de izquierda a derecha y de abajo hacia arriba de tal forma que: <J si / es par hacemos el recorrido en sentido inverso, de tal forma que: n+^ _ <J + ^".-«-Í + Cf) + U2m <, este esquema converge rápidamente hacia la solución y experimentalmente el número de iteraciones 2m necesarias para pasar de t¿"^^ a w" depende por supuesto de los valores de /i y A;, pero normalmente se encuentra entre seis u ocho iteraciones. Hemos comprobado también experimentalmente que este esquema implícito es incondicionalmente estable lo que permite tomar valores altos de k, y por tanto avanzar rápidamente a través de las escalas. Por último vamos a discretizar la ecuación del modelo invariante afin que recordamos se puede expresar como: Ut = {UIUJ:X - 2UxUyUxy + ulUyy) 42 2. Principios del Análisis Multiescala Morfológico nótese que empleamos la ecuación sin el factor í 3 en el operador diferencial, para recuperar la solución de la ecuación original con dicho factor debemos hacer el cambio de variable t —>• {^t)*. Para dicretizar la ecuación utilizaremos el mismo tipo de técnicas que anteriormente. Como método explícito podemos plantear: u"t^ —qjV-. 1 en este caso, debido a la presencia de la potencia | no es posible dar condiciones analíticas de estabilidad. Experimentalmente, hemos comprobado que el esquema se comporta bien cuando, aproximadamente, ^ < 0.2. 2.5.4 Análisis Numérico de una Ecuación hiperbólica. En este apartado estudiaremos algunos fundamentos sobre la forma de discretizar una ecuación hiperbólica. Estas nociones son necesarias para abordar la discretización de filtros de choque como los descritos en la sección anterior. Para fijar ideas tomaremos como problema modelo la ecuación en dimensión 1: Ut = CUx donde c es una constante. Es bien conocido que la solución de esta ecuación para un dato inicial /, u{0, x) = f{x), viene dada por u{t,x) — f{x + ct) es decir la evolución corresponde simplemente a un desplazamiento de la función /, si c > O la solución se desplaza hacia la izquierda, y si c < O la solución se desplaza hacia la derecha, este simple argumento nos da una indicación de como debemos discretizar la ecuación. Efectivamente, una discretización cualquiera de la ecuación se escribirá como: donde u^ = u{nk,hj), ahora bien si c>0 si la solución se desplaza hacia la izquierda entonces tí""*"^ sólo debe depender de M", Uj_^.-¡^, «"+2) etc.. Ello nos lleva a plantear una discretización de la ecuación que respete este hecho como por ejemplo: k h 2. Principios del Análisis Multiescala Morfológico 43 de donde Si multiplicamos la igualdad por el término e"'^'^^^ y sumamos en j obtenemos OO / h- \ OO Y, uf^e-'""^^ = í 1 - c^(l - e-'""^) j Y, ^"e" -iwhj J — -00 ^ ' j=-OC por tanto para obtener estabilidad debe verificarse I 1-4(1-6"^'"'^) |<1 yw lo que se verifica si También es posible utilizar un método implícito de la forma: A; /i de donde (1+4)u^+' - 4^f ^ = u^i Si multiplicamos la igualdad por el término e"™'*-' y sumamos en j obtenemos OO ^ OO E n+1 -iwhj ^ t Y^ y^n^-i^hj j=—OO \ a ^ '/ j=—OO dando lugar a un esquema incondicionalmente estable. Además, como se demostró en [AM94a], haciendo A = c| podemos obtener: 1 + A ¿-; 11 m 1 1 Jll / \ (1 + A(l - e-^"''^)) 1 + A^Vl + A ^ ^ '' m=0 ^ ' y por tanto podemos deducir: l + A^^Al + A Análogamente, en el caso en que c < O debemos proceder de la misma forma pero utilizando diferencias regresivas para la discretización de u^^ es decir Capítulo 3 Discretización de Operadores no lineales. En esta sección vamos a proceder a la discretización de un operador no lineal, de un modo distinto al convencional. Normalmente, dado un operador no lineal a discretizar, se suele utilizar el siguiente esquema: se discretizan los operadores lineales que aparecen como componentes de dicho operador no lineal por separado mediante algún criterio conocido, y luego se sustituyen dichas discretizaciones para obtener la discretización del operador deseado. Aquí vamos a utilizar un esquema distinto: discretizaremos el operador no lineal como un único operador diferencial independiente. Ésto nos permite aplicar ciertas propiedades de los operadores que no se podrían aplicar discretizando los operadores lineales que lo componen de forma independiente. Además utilizaremos esta discretización para la aplicación de filtros a imágenes. Consideraremos una imagen como una función u de una región del plano í) C 3^2 en 3?, de forma que u estará definida como u : Q, ^ ^. 3.1 Discretización del operador T{U). En la siguiente sección vamos a proceder a la discretización del operador no lineal T\U) — '^y'^xx ^'^x'^y'^xy \ '^x^yy 45 52 3. Discretización de Operadores no lineales. 1 1 Errorr(u),j = j^{Xi + ^4 +X3)p'^ + i^i^a-^^)p^q +- (A3 + X4)p^q^ + - (-A4 + X3)pq^ + — (A4 + A2 + A3) 9^ 4 = ^ CiV\^~^ = Co9^ + cipq^ + C2P^q^ + c^p^q + c^p^ 1=0 Obtenemos las siguientes relaciones: co = T^ (A3 + A4 + A2) ci = - (-A4 + A3) C2 = 2 (-^4 + As) C3 = 2 ^^^ ~ ^"^^ C4 = T^ (Al + As + A4) Como el coeficiente k^ es el que acompaña al factor que representa la dirección en la que el error es mayor, lo vamos a anular, de modo que, sustituyendo en la expresión anterior de A;4, resolvemos la ecuación A;4 = 0. a^hcz + a^6^C2 + ah^ci + h^CQ + 0^0^ = O aH(-\K + \M) + a262 (ÍA3 + ÍA4) + a63 (-ÍA4 + |As) + ^' (Á^2 + é^3 + ¿A4) + (¿Al + ¿A4 + ¿As) a^ = -|a^&A4 + \a%Xi + \a%''Xs + ^a'^b'^X^ - \ah^X^ + \ah^Xz + ^^h^X2 + ¿6^ As + ¿6^A4 + ¿a'^Ai + ^a^X^ + ¿a^As = -la^h"^ + a262 (ia2 - Ao + ^6^) _ ia264 = o Con lo que obtenemos que, \a%^ - a^b'^Xo + |a264 =. Q ^ a'^b'^Xo = \ {a%^ + a^fe^) cuya solución es Ao = i(a2 + 62) Y sustituyendo, como habíamos indicado en un principio: a = Uy, b = —u^ 3. Discretización de Operadores no lineales. 53 >^o = l{ul + ul) (3.3) 3.3 Algunas aplicaciones del operador T{U). En esta sección veremos dos casos en los que se utilizara el operador no lineal T{U) de forma que, variando algunos de los resultados anteriores, obtendremos la discretización de la ecuación diferencial en la que aparece dicho operador. Curvatura Media. En términos de derivadas parciales, la curvatura se expresa como: curv[u) = —^— (ul + ul) ^ de forma que la ecuación diferencial de la curvatura media es: Ut — ||Vtt|| • t • curv{u) sustituyendo cada término que aparece en dicho producto, y como ||VM|| = •y^ul + M^ ^obtenemos : ulUxx - 2UxUyUxy + ulUyy T(u) Ut = t • -^ r- =t ul +ul ul + ul A efectos prácticos eliminaremos el parámetro t en la ecuación anterior. Para ello, realizaremos un cambio de variable en la ecuación para simplificar los cálculos, de forma realizamos el cambio t ^^ y . De este modo, la ecuación quedará de la forma T{U) Ut = ul + ul En este caso, para aproximar la discretización de la ecuación diferencial anterior utilizaríamos el siguiente esquema: ul + ul siendo s el incremento de tiempo. 54 3. Discretización de Operadores no linecJes. Ahora, el operador no lineal a utilizar sería T'{U) — ^2 V^^a • En realidad, todos los resultados obtenidos anteriormente son válidos, con unas pequeñas variaciones. En el apartado (1.1) en vez de utilizar el cambio de variables a = Uy Y b= —Ux, utilizaremos los cambios a = ,"^ „ Y b = ,'y ^. De esta forma, los resultados finales son: ^2 = -^ + 2Ao A3 = 1 ^^=^^¡¡27^^ + 4 + -^-^-^° De esta forma, para minimizar el error, y siguiendo los resultados obtenidos, el valor que ha de tomar AQ será: Nótese además que para la denominada "elección natiiral de AQ" dado en la expresión (1.2) en este caso AQ = |. 3.3.1 Estudio de la Evolución de radios en círculos. Para comprobar los resultados de la discretización expuesta, hemos aplicado la ecuación anterior a una imagen sintética de un círculo de radio 80 píxels. La razón de utilizar este tipo de imagen es muy sencilla: conocemos la evolución real (teórica) de los círculos al utilizar este tipo de operador. Si se aplica la ecuación de la curvatura media a un círculo, éste se va transformando en otros círculos concéntricos cada vez más pequeños, de forma que éste tiende a desaparecer en un tiempo determinado. Lo primero que hemos hecho ha sido calcular numéricamente en qué unidad de tiempo debería desaparece el círculo (su radio se hace cero). Veamos, pues, primero el cálculo de t para que el radio del círculo sea 0. La evolución del círculo para la ecuación de la curvatura media T{U) Ut = ul + ul 3. Discretización de Operadores no lineales. 55 es: Rt = ;^, es decir, Rt • R{t) = — 1. Así pues, \-{R\t) - i?2(0)) = -t ^ R\t) = i?2(o)_2.t ^ R{t) = ^/R^{0) - 2 • t => Para que R{t) -^ O =^ O = VSO^ - 2 • t =í> 2 • t = 6400 =4> t = 3200 unidades de tiempo. Resultados prácticos. Hemos realizado varias pruebas utilizando una imagen sintética del 200 x 200 pixels que corresponde a un círculo de radio 80 pixels, con 8 bits de profundidad que nos permiten 256 niveles de gris, y que tiene un color negro en su interior y blanco fuera de él, como se indica en la figiira 3.1. Figura 3.1: Círculo de radio 80 pixels En estas pruebas, para discretizar t, hemos tomado distintos pasos de tiempo s, de forma que t =ns. Hemos probado con s = 0.5, que corresponde a realizar 6400 iteraciones para que el radio del círculo se haga teóricamente cero, es decir, para que el círculo desaparezca, y hemos utilizado s = 0.1, necesitando realizar 32000 iteraciones para lograr nuestro objetivo. Para cada uno de los distintos valores de los pasos de tiempo utilizados, hemos variado el valor del parámetro Ao, según las distintas conclusiones llegadas en este estudio. Estos valores corresponden a los distintos casos siguientes: (a) Ao = |, que corresponde a la principal conclusión llegada en nuestras investigaciones. 56 3. Discretización de Operadores no lineales. (b) Ao = |, que correspondería a la "elección natural" del parámetro AQ. (c) Ao variable. Este valor variable del parámetro AQ corresponde a un estudio realizado por los investigadores Alvarez, L. y Morell, J.M. (ver [AM94c]). En este trabajo se refleja que, con respecto a la estabilidad, es importante que todos los coeficientes A¿={o,,..,4} han de ser no negativos. Debido a la naturaleza de los mismos, esto no es posible conseguirlo. Lo que hacen los autores en este trabajo es definir distintas regiones comparando los valores de Ux y de Uy, definiendo en cada una de ellas los valores que han de tomar los distintos parámetros A¿={o,...,4}. Así llegan como conclusión a lo siguiente: • Región (1): { \ux\ > \uy\ AUx-Uy>0} >^0 = IC^ul + ul - UxUy) X2 = l{ul-UxUy) -^3 = l{ul + 3UxUy) ^4= liul-U^Uy) • Región (1): { |«x| > \uy\ Au^-Uy <0} ^= IC^UI + Ul + U^Uy) >^l = W^UI - Ul + U^Uy) A2 = U'^lUxUy) •^4 = \{l4-^UxUy) • Región (2): { \ux\ > \uy\ Aux • Uy >0} ^0 ^ li'^ul + Ul - UxUy) A2 = \{ul-UxUy) >^3 = l{ul + 3UxUy) A4 = l{ul-UxUy) 3. Discretización de Operadores no lineales. 57 • Región (3): { \ux\ < \uy\ /\ Ux • Uy > 0} ^ = iC^ul + ul - UxUy) Al = l{ul -u^Uy) ^3 = l{ul + 3UxUy) A4 = \{UI -UxUy) • Región (4): {\ux\ < \uy\ /\Ux • Uy <0} ^0 ^ 1{2UI + Ul + UxUy) A2 = 1{2UI - Ul + UxUy) ^3 = \{ul + UxUy) A4 = \{ul-3uxUy) Evolución del radio de un círculo. Vamos a presentar, dentro de los distintos valores que damos a los parámetros s y AQ, diversas pruebas que hemos realizado a la imagen del círculo ya comentada. En este tipo de pruebas, hemos calculado la curva teórica que debe seguir un círculo de radio 80 pixels y la hemos representado junto con la evolución experimental de cada prueba para cada valor distinto del par (s, AQ). Para ello, hemos ido creando, a medida que se aplica nuestro operador a la imagen, un fichero de 100 valores de radios por los que va pasando en distintas iteraciones nuestro círculo original. Cuando analizamos el radio del círculo nos planteamos cuál es el nivel de gris adecuado a partir del cual consideramos que es negro, a efectos de la medición de dicho radio. Es decir, nos planteamos la necesidad de un umbral. Pues bien, hemos realizado pruebas con distintos valores de umbral: 50, 128 y 230 de forma que podamos establecer distintos grados de precisión. (En nuestra imagen, el nivel de gris O corresponde al "negro" y el nivel de gris 255 corresponde al "blanco". ) ^ , AzuhAo = 0.25 Verde: AQ = 0.5 , lomando como : los resultados Magenta : AQ variable Rojo : gráf. real obtenidos han sido los siguientes: 58 3. Discretización de Operadores no lineales. Bmiución Radios Círculo, Umbral = 50, s = 0.1 500 1000 1500 2000 2500 3000 Figura 3.2: Evolución de los radios del círculo, con s=0.1, y umbral 50 Evolución Radios Qrculo, Umbral = 128; s = 0.1 500 1000 1500 2000 2500 3000 Figura 3.3: Evolución de los radios del círculo, con s=0.1, y umbral 128 3. Discretización de Operadores no lineales. 59 Evolución Radios Círculo, Umbral = 230, s = 0.1 2500 3000 Figura 3.4: Evolución de los radios del círculo, con s=0.1, y umbral 230 80 60 40 20 0 Evolución Radios Qrculo, Umbral = 50, s = 0.5 ^K^. ^^V \^ • • ' - \\\\ '^^\ • ' 1 - 500 1000 1500 2000 2500 3000 Figura 3.5: Evolución de los radios del círculo, con s=0.5, y umbral 50 60 3. Discretización de Operadores no lineales. Bwlución Radios Círculo, Umbral = 128, s = 0.5 500 1000 1500 2000 2500 3000 Figura 3.6: Evolución de los radios del círculo, con s=0.5, y umbral 128 Evolución Radios Qrculo, Umbral = 230, s = 0.5 1500 2000 2500 3000 Figura 3.7: Evolución de los radios del círculo, con s=0.5, y umbral 230 3. Discretización de Operadores no lineales. 61 En las gráficas observamos que obtenemos el mejor resultado utilizando el esquema que más minimiza el error, es decir, AQ = 0.25. Además, en los resultados obtenidos con pasos de tiempo s = 0.1 y s = 0.5 apenas se aprecian diferencias, con lo que nos quedamos con s = 0.5 lo cual implica que con menos iteraciones obtenemos casi el mismo resultado. En las otras gráficas en las que aparecen los umbrales 230 y 128 parece que el esquema no es muy estable debido a convergencias con lo que nos quedamos con el umbral 50 en el que los valores de los radios convergen a la curva teórica de la variación del mismo.. Además, hemos realizado otro tipo de comparación entre los distintos valores de AQ. Hemos representado, para los mismos valores de AQ, ocho cortes al centro de la imagen (que corresponde a cortes en la parte central del círculo), realizados a evolución de tiempos distintos, que van reflejando la evolución del diámetro del círculo en el tiempo. Así pues, para cada grupo de cortes, reflejamos el nivel de gris (0..255) que tiene cada pixel de la sección central de la imagen del círculo. Los resultados obtenidos son los siguientes: a) Para AQ = 0.25 b) Para AQ = 0.5 c) Para Ao variable, tal como se explicó anteriormente. En las figuras 3.8 y 3.9 se muestran los resultados obtenidos. Podemos apreciar que con el valor de AQ = 0.25 los valores del radio llegan antes a los valores esperados (desaparece más acorde con la evolución teórica). De igual forma, son s = 0.1 y s = 0.5 los resultados han sido similares. 68 3. Discretización de Operadores no lineales. Evolución Radios Círculo, Umbral = 128, s = 0.05 Figura 3.15: Evolución de los radios de la elipse (tomada como círculo), con s=0.05, y umbral 128 Evolución Radios Círculo, Umbral = 230, s = 0.05 Figura 3.16: Evolución de los radios de la elipse (tomada como círculo), con s=0.05, y umbral 230 3. Discretización de Operadores no lineales. 69 Haciendo el mismo estudio que en el caso del círculo, vemos la evolución de los cortes del centro de la imagen de la elipse (tratada como círculo) obteniendo los siguientes resultados que aparecen en las figiiras 3.17, 3.18 y 3.19. 300 250 200 150 100 50 An = 0.25 í'I I ! i '[ \ I ! I ! I ,' t 250 200 150 100 50 i! i MI! i_ \ _Zz ü 50 100 150 200 Ao variable m 50 100 150 200 An = 0.5 --l'-^-^-^-p^ • 250—mxrr\-^ í-r-r fWH50 100 150 200 Figura 3.17: Evolución de los cortes de un círculo de radio 200 pixels, s=0.025 70 3. Discretización de Operadores no lineales. 300 250 2(X} 150 100 50 200 150 100 50 Ao = 0^5 -Mj\¡^f\ \jAj,ilU\i ' i \\ \,^ ; I I ¡ i I 50 100 150 200 Ao variable \ i ! i ! 1 ! 50 100 150 200 250 r 200 15Q\ 100] 50 '•T^i'^m' ÍÍMM \\ 1; ni i \ rrrrrm \ \J I 11 50 100 150 200 Figura 3.18: Evolución de los cortes de un círculo de radio 200 pixels, s=0.05 Ao = 0.25 300 250 200 Í50 100 50 250 200 150 100 50 Xo = 0.5 50 100 150 200 Ao variable _:lil 100 f! 150 AX) 50 100 150 200 Figura 3.19: Evolución de los cortes de un círculo de radio 200 pixels, s=0.1 3. Discretización de Operadores no lineales. 71 3.3.2 Evolución de Esquinas. De igual forma que hicimos con el modelo invariante afín: Ut = t3 • (ulu^:^ - 2uxUyUxy + uluyy) 3 = í3 . r(ií)3 en el que a efectos prácticos eliminamos el parámetro U en la ecuación anterior, tomando: t '-> |í3 . quedando la ecuación de la forma, sabemos que la velocidad de variación de una esquina con el operador anterior es v = X-t siendo A = tan ' (f)^ Así pues, partimos de que conocemos la velocidad a la que teóricamente varía la esquina al aplicarle el operador no lineal en cuestión. Resultados prácticos. Hemos realizado varias pruebas utilizando una imagen sintética de 401 x 219 pixels que corresponde a una esquina que forma un ángulo de | radianes, con 8 bits de profundidad que nos permiten diferenciar 256 niveles de gris (ver figura siguiente), y que tiene un color negro en su interior y blanco fuera de él. Tal como se había obtenido en la sección anterior, la velocidad con la que avanca la esquina sería v = t, pues a — ^. Hemos realizado una estimación del tiempo que necesitamos para avanzar 20 pixels desde la proia esquina hacia adentro durante el proceso de aplicar nuestro algoritmo a la imagen. En estas pruebas hemos tomado distintos pasos de tiempo s (s = n-t). Hemos probado con s — 0.03, que corresponde a realizar n = 1357 iteraciones para que la esquina avance 20 pixels hacia adentro (hacia la izquierda); hemos 72 3. Discretización de Operadores no lineales. Figiira 3.20: Esquina de 90 grados. utilizado también s = 0.05, necesitando realizar n = 814 iteraciones para el mismo propósito, y por último, s = 0.1 para el que se obtiene un número total de iteraciones igual a 407. Paxa cada uno de los distintos valores de pasos de tiempo utilizados, hemos variado el valor del parámetro AQ, según las distintas conclusiones que hemos obtenido en nuestro estudio: AQ = j, Ao = | y por último AQ variable. Evolución de una esquina de | radianes. Vamos a presentar, dentro de los distintos valroes que damos a los parámetros AQ y s, diversas pruebas que hemos realizado a la imagen de la esquina anteriormente comentada. En este tipo de pruebas, hemos calcularo la recta teórica que corresponde a la evolución de una esquina de | rad y la hemos representado junto con la evolución experimental de cada prueba para cada valor distinto del par (s, Ao). Para ello, hemos ido creando, a medida que se aplica nuestro operador a la imagen, un fichero de 100 valores de radios por los que va pasando en distintas iteraciones nuestra esquina original. Para obtener una visión de la evolución de las esquinas para cada valor de paso en la discretización, hemos realizado un análisis independiente del umbral 3. Discretización de Operadores no lineales. 73 An = 0.25 300 250 200 150 100 50 1 ffi ^M\ % I i ili ^;Í; ',1 250 200 150 100 50 50 100 150 Ao variable i «L 200 50 100 150 200 250 200 150 100 50 "I á 1 1 1 Ao = 0.5 50 100 150 200 Figura 3.21: Esquinas, s=0.030 escogido. Hemos realizado nueve cortes en momentos equiespaciados de tiempo de forma que cada uno representa un barrido del valor de nivel de gris de cada punto del centro de la imagen. Los resultados obtenidos son los siguientes: 74 3. Discretización de Operadores no lineales. 300 250 200 150 100 50 piil j 11" i illi'i i.iilli 50 250 iSO 100 50 —in i 1 1 ll¡l 'lili 50 Ao = 0.25 100 150 Ao variable 100 150 200 200 250 200 150 100 50 "1: ii'liÍ i ¡iiil 11 50 Ao = 0.5 100 150 200 Figura 3.22: Esquinas, s= 0.05 300 250 200 150 100 50 s "TI iif ! lí i'il _ i'lL___._ 60 Ao = 0.2 100 5 150 200 Ao variable 250 200 150 100 t 50'- iiüL50 fOO 150 200 Afl = 0.5 50 100 150 200 Figura 3.23: Esquinas, s=0.1 Capítulo 4 Representación de Formas Planas. En este capítulo, proponemos una representación invariante de formas geométricas utilizando el análisis morfológico multiescala. Esta invarianza geométrica se basa en la evolución del área y del perímetro de la forma bajo la acción de un análisis multiescala morfológico. Primero, presentaremos algunos resultados teóricos sobre la evolución del perímetro y del área de las formas. En caso de tener transformaciones de similitud, el invariante geométrico propuesto se basa en la evolución normalizada en escala del cociente isoperimétrico de la forma. En caso de transformaciones geométricas afines generales el invariante geométrico se basa en la evolución normalizada en escala del área. Presentamos además algunos resultados numéricos para evaluar el rendimiento de los modelos propuestos. 4.1 Introducción. Los métodos de representación de formas juegan un papel muy importante en los sistemas de reconocimiento y análisis de objetos. Según la clasificación de los métodos de análisis de formas propuestos por Pavlidis [Pav78] y Loncaric [Lon98], por métodos de representación de formas se entienden métodos que nos proporcionan una representación no numérica de la forma (por ejemplo un grafo). La descripción de la forma se refiere a los métodos que determinan descriptores numéricos de la forma y que podrían suponer el paso siguiente a la representación 75 76 4. Representación de Formas Planas. de formas. Dentro de los métodos de descripción de formas, podemos distinguir dos clases. Por un lado, los métodos basados en el contorno de la forma (también llamados externos) y otro los métodos basados en características globales de la forma (también llamados internos). En los últimos años, el análisis multiescala se ha convertido en tma herramienta muy común para muchas tareas relacionadas con la visión por ordenador. Un análisis multiescala puede definirse como un operador Tt{f) que proporciona, para una imagen original /, ima secuencia de imágenes Tt(f) que representan la imagen en una escala más grosera t. En nuestro trabajo trataremos con análisis multiescala morfológicos, que satisfacen la invarianza morfológica, es decir, que el análisis multiescala Tt{f) conmuta con cualquier modificación creciente del histograma de la imagen. Esto significa que para cualquier función creciente g{.) Tt{f)og = T,{fog) la hipótesis subyacente asociada a esta invarianza morfológica es que el contraste entre diferentes objetos presentes en la imagen no es importante, y que toda la información presente en la imagen se describe mediante la geometría de los conjuntos de nivel de la imagen. En particular, el modo en que la forma cambia bajo la acción de un análisis multiescala morfológico depende únicamente de la geometría de su borde. El objetivo principal de este capítulo va a ser explotar las propiedades de invarianza morfológica y geométrica de los análisis multiescala morfológicos para determinar vma representación de formas global fiable. Las representaciones de formas en la escala espacial lineal han sido estudiadas por diversos autores: Witkin [Wit84] propone una aproximación de filtrado en escala espacial mediante el seguimiento de los puntos de inflexión en las imágenes filtradas por gausianas. Asada y Brady [AB86] propusieron una representación denominada the curvature primal sketch. Los contornos de la forma son filtrados con funciones gaussianas con ancho incremental para obtener una representación multiescala de la forma basada en la curvatura de los contornos. Mokhtarian y Mackworth [MM92] proponen también una representación de los contornos de las formas en la escala espacial basada en la evolución de las curvaturas a través de las escalas. En el contexo de los espacios de escala morfológicos, Maragos [Mar89] propuso una representación del espectro de patrones basado en la evolución del área de la forma obtenida mediante la apertura de la forma con un 4. Representación de Formas Planas. 77 disco de medida incremental. Cohignac et al., [CLM94] y [CM95], propusieron un método de reconocimiento de formas invariantes afínes basados en el análisis multiescala morfológico invariante afín. Utilizaron el análisis multiescala para recuperar puntos característicos en la forma. Lisani et al. [LMMMOO], utilizó el análisis multiescala invariante afín para suavizar las imágenes antes de hacer una codificación local de los elementos de la forma. El método que nosotros proponemos en esta memoria consiste en utilizar la evolución del área y/o perímetro de la forma a través de las escalas utilizando diferentes análisis multiescala morfológicos como herramientas básicas para extraer una representación global escala-espacial de la forma. Tal y como demostraron Alvarez, Guichard, Lions y Morel en [LAM93], bajo algunas hipótesis mínimas sobre la arquitectura utilizada, todos los análisis multiescalas morfológicos e invariantes euclídeos están generados por la ecuación en derivadas parciales: - = I3{curv{u)) \\Wu\\ (4.1) en dónde /3(.) es una función no decreciente y curv{u){x,y) es la curvatura de la línea de nivel que pasa por el punto (x, y), es decir: curv{u) = div V^l! Por ello, si u{t, x, y) es la solución de la ecuación (4.1), para el dato inicial /, entonces: u{t,x,y) = Tt{f){x,y) Nótese que estos análisis multiescalas morfológicos son invariantes a transformaciones euclidianas y simétricas {{x,y) —> {±x, ±y)). Siguiendo el principio morfológico, consideramos que vina forma SQ viene dada por un conjunto de nivel de la imagen /, es decir So = {{x,y): f{x,y) < A} 84 4. Representación de Formas Planas. Definición 10 Let he SQ a hounded shape, we define the scale-normalized isopeñmetric ratio evolution I^p°¡3_^,0j^) (i) as the function ^(Í-,..,)(í~) = 47r <S'(p,/3_i,/3i)(í-y/|5'o|) C'(p,/3_l,/9i)(í\/|<5'o|) Definición 11 Dada So una forma definida, definimos la evolución del cociente isoperimétrico normalizado en escala l^p°0_j^,0j^){i) como la función C-...)(í~) = 47r (ívW) C(p,e_i,/3i)(í\/| 5*01) Observamos que í(p°p_^,0j^){i) < 1, y -^(p°/3_i,/3i)(¿^) = 1 sólo en el caso de que S'(p,/3_i,/3i)(í-y^|<S'o|) sea un círculo. A continucación, mostraremos que I(p,^_^,p.^){i) es im invariante por similitudes de la forma SQ. Teorema 5 Sea T^ ""^' (/) un análisis multiescala morfológico invariante bajo transformaciones de similitud, y sean 2 formas definidas So, SQ, de forma que existe una transformación de similitud H, con H{SQ) = SQ, Entonces: Demostración. : Sea k el factor de escala de la transformación H, utilizando (4.11) obtenemos: • A??._„.,)(í) = 47r = 47rS(p,l3_ C(,p,0_ .MiV\s^\) ^,UW\s'o\) = 47rS¡p,0_,,,AtkV\S^\) CU-..i)(í~^vW) lo cual concluye nuestra demostración. — ^(p,l3_i,0i)\'t) 4. Representación de Formas Planeis. 85 Observación: Hacemos notar que en el caso de la evolución de la curvatura {{p,(3_i,l3i) = (1,-1,1)), si C{t) es una familia de curvas de Jordán simples, entonces según los resultados de la sección anterior tendremos que 5(i,-M)(íVÑ)| = |5o|(l-7rP) + así que tenemos una forma de expresión analítica para la evolución del área. En particular tendremos que ya que 5(1,-1,1) (í) converge hacia un círculo que se desvanece, entonces I(i°-i,i) (i) satisface: Lim /J_i,i)(í) = l. Por otro lado, en el caso de p = O tendremos que Cw_i,/3i)(í\/Ñ)| = (|Co| -27r/3itx/¡5oí)_^ así que obtenemos una expresión analítica para la evolución del perímetro. 4.4 Representación morfológica afín invariante de una forma. Consideremos una transformación afín general dada por en donde A es una matriz de 2 x 2 con |A| 7¿ O En [LAM93], se mostró que el único análisis multiescala morfológico invariante afín viene dado por "^^ ^ ^ /9-i(-«)^ if s<0 86 4. Representación de Formas Planas. En donde y^i > O y /3_i < 0. En este caso tenemos que H{T,^HMf))-TtiHif)) dónde t'{H,t) = \A\h Por otro lado, dadas 2 formas definidas 5*0, 5"^, tales que existe una transformación afín H con H{SQ) = So, tenemos que: '^(p,^_i,^i) S(r„0-M(.i)\ = —— Ví>0 (4.12) 1^1 En el caso de la representación invariante afín, no podemos utilizar el cociente f isoperimétrico normalizado en escala porque el perímetro no es un invariante bajo ^ o. transformaciones afines. Por ello proponemos un invariante geométrico basado | únicamente en la evolución del área. Introduciremos, a tal fin, la evolución del j cociente de superficie normalizado en escala. | Definition 1 Definición 12 Sea una forma definida So, definimos la evolución del cociente de superficie normalizada en escala SRf°f¡_^i¡^^{i)como la función S^(.p,0-i,0i) (O — S(p,í}_l,0J^){t^/\So\) \So A continuación, mostraremos que S'i?^°^_^^^j)(í) es un invariante afín de la forma SoTeorema 6 Sea T/ ' ~^' (/) un análisis multiescala morfológico invariante ante transformaciones afínes (p = |), sean 2 formas definidas So, SQ, tales que existe una transformación afín H con H{S'Q) = ^o. Entonces: 4. Representación de Formas Plstnas. 87 Demostración. : Utilizando (4.12) obtenemos ^^fL i,w(*~) = '5(i.-„..)(ívW) s'^^^^(tV\s^\) \So\ \S'o\ \So\ \A\ ii) lo cual concluye nuestra demostración. La escala de desvanecimiento. Definición 13 Dado un análisis multiescala morfológico T¿ ^' (/) conp > O y dada la forma SQ, definiemos la escala de desvanecimiento t£ ~^' ^ (So) como un numero: t>o Observación: Nótese que si /3i > O y S'o es una forma, entonces por el principio de inclusión tenemos que ,y por ello &^-''^'\s^) < Rp-'/W,{p + 1)) < oo. Observación: Nótese que si usamos la escala i, dada en (4.6), en vez de t, entonces la escala de desvanecimiento para un círculo de radio RQ viene dado por : ^^-"^'\Bn,{xo,yo)) = PrRo Por otro lado, bajo la acción de una transformación afín o de similitud HQ tenemos que í^'^"''^'^ -> k^^^~'"^^\en dónde A; es el factor de escala de la similitud o i^ -"•' '^ -^ ^/\A\t'£^^-'"'^^'' en el caso de una transformación afín. Esta 88 4. Representación de Forni£is Planas. relación nos proporciona otra forma de normalizar la escala en el cociente isoperimétrico normalizado en escala y del cociente de área normalizado en escala, en otras palabras, las siguientes funciones son invariantes por similitudes (respectivamente invariantes afínes) de las formas •^(p,0-i,0i)\^) ~ S'(p,/3_i,/3i)(í(íoo' ^' ^ )) •S-R|,_,..,® '(¿,/3_l,0l) (H*0¿ ;ihPU,Pi) )) {é'-''*^'y Así que podemos calcular íoo' ~^' ^ para un valor particular de {^l, P*_i) y luego normalizar la escala con ít'^-^'^^^ para cualquier análisis multiescala (/5x,/3_i). 4.5 Resultados Numéricos. Los algoritmos numéricos que utilizamos para aproximar numéricamente los análisis multiescalas morfológicos que usamos están basados en técnicas desarrolladas en esta memoria en el capítulo sobre discretización de operadores diferenciales. Primero, presentamos algunas experiencias utilizando la evolución del cociente isoperimétrico normalizado en escala /(f°^_j,^j)(í). Utilizaremos algunas formas sintéticas dadas en la figura 4.1. para todas las formas (excepto para el círculo) tenemos un cociente isoperimétrico inicial similar (de hecho, teóricamente el cociente isoperimétrico es exactamente el mismo para todas las formas, sin embargo, en la práctica, debido a rmdos y errores numéricos el cociente isoperimétrico calculado no es el mismo). Las formas han sido organizadas de la siguiente forma: para cada forma se ha aplicado una transformación de similitud donde hemos rotado y cambiado el tamaño original de la forma. Así, las formas 1 — 2, 3 — 4, 4 — 5, 5 — 6y7 — 8 son equivalentes módulo una transformación de similitud. La forma 9 es similar a la forma 7 pero en la forma 9, hemos cambiado la localización del cuadrado del interior. Compararemos /(i°0_i,^i)(^) para las distintas formas para te [0,0.3]. Recordamos que 4. Representación de Forméis Plañáis. 89 Figura 4.1: Formas de prueba utilizadas peira evaluar el cociente isoperimétrico normalizado en escala. Por ello, i = AA ~ 0.56 es el límite superior para el que tiene sentido la comparación de las escalas. En la figura 4.2, presentamos la evolución de /(^°_i,i)(í) para las formas de la figura 4.1. Cada forma tiene asociados varios gráficos que corresponden a la evolución de /(^°_i,i)(í) para las distintas transformaciones de las formas. Observamos que siguiendo la evolución de -^(i^i,!) (í) podemos discriminar bastante bien entre las distintas formas. Nótese que las figuras 7 — 8 — 9 presentan evoluciones similares debido a que la evolución de /(f"_i,i)(í) no se altera por la localización del cuadrado de dentro de las formas. En la figura 4.3, presentamos la evolución de /(^°o,i) (^) P^^^ ^^ formas de la figura 4.1. Nótese que en este caso, las formas 7 y 9 tienen una evolución diferente siguiendo la localización del cuadrado de su interior. Este comportamiento se ilustra en la figura 4.4 en donde mostramos algunos pasos de la evolución de S{i,o,i){t) a través de las escalas para la figura 9. En la figura 4.5, presentamos la evolución de I(i°o.i){i) psiva. las formas de la figura 4.1. 90 4. Representación de Formas Planas. 1 - 0.9 - 0.8 - 0.7 - 0.6 0.5 ^ ^- ' y^ Xy -.x -r.-- 0.4 0.00 0.03 0.06 0.09 0.12 0.15 0.18 0.21 0.24 0.27 0.30 Figura 4.2: Evolución de ifl^^^S) para las formas de la figura 1. 0.00 0.03 0.06 0.09 0.12 0.15 0.18 0.21 0.24 0.27 0.30 Figura 4.3: Evolución de 1%^^-^ (í)para las formas de la figura 1. 4. Representación de Formas Planas. 91 Figura 4.4: De izquierda a derecha y de airriba a abajo: Evolución de 5(1,0,1) (í) pgira la forma 9 de la figura 1. 0.00 0.03 0.06 0.09 0.12 0.15 0.18 0.21 0.24 0.27 0.30 Figura 4.5: Evolución de para las formas de /(^°_i,o)(í) la figura 1. 92 4. Representación de Formas Planas. <)(0o •f-10 Figura 4.6: Formas de prueba utilizadas paira evalusir la evolución del cociente de superficie invciriante afín normalizado en escala. A continuación, presentaremos algunas experiencias utilizando la evolución del cociente de áreas normalizado en escala SRfi , ^ Ai). Utilizaremos algunas formas sintéticas dadas en la figura 4.6. Para cada forma hemos aplicado una transformación afín en donde hemos cambiado las medidas horizontales y verticales de las mismas de forma diferente. Así, las formas 1 — 2, 3 — 4, 4 — 5, 5 — 6, 7 — 8 y 9 — 10 son equivalentes módulo una transformación afín. Compararemos i (í) para las distintas formas para i G [0,0.3]. SRf', En la figura 4.7, presentamos la evolución de SR^^l_^Ai) para las formas de la figura 4.6. Cada forma tiene asociada 2 gráficas que corresponden a la evolución de SR^° _^ {i) para las distintas transformaciones de las formas. En la figura 4.8 presentamos la evolución de SR^° „ l^ (^) P^^ ^^^ formas de la figura 4.6. Nótese que en este caso, únicamente la región convexa de las formas evoluciona, así que este comportamiento produce una discriminación fuerte entre la evolución de las formas siguiendo la geometría de sus regiones cóncavas y convexas. Puede observarse este efecto si se compara la evolución de las formas 3 y 7. La evolución de SR^° ^ (í) para estas dos formas es muy diferente, pero la 4. Representación de Fornicis Planas. 93 0.8 0.6 0.4 0.2 0.00 0.03 0.06 0.09 0.12 0.15 0.18 0.21 0.24 0.27 0.30 Figura 4.7: Evolución de SRf?_^^^{i) para, cada forma de la figura 6. Evolution of SR^i _^ (t) for the shapes of figure 6. evolución de ^it:f|_j^^(í) para las mismas formas son mucho más parecidas. Así que en la práctica, significa que utilizando la información de la evolución del área con diferentes valores de /5_i y /3i obtenemos un poder mejor de discriminación para las formas. En la figura 4.8, presentamos la evolución de SR^? _^ (i) para las formas de la figvira 4.6.La evolución con el análisis multiescala T^' es más sensible a ruidos de pixels que aquellos correspondientes a /3i > 0. La razón es que en este caso no hemos tenemos un efecto de regularización en los bordes. Este comportamiento puede observarse en esta experiencia numérica: Por ejemplo la evolución de los triángulos dados por las formas 5 y 6 son claramente diferentes debido a los errores de pixels introducidos por la aplicación de la transformación afín a la forma 5. 100 4. Representación de Formas Planas. €/ 15 ^? ^í ^ ^H» ^ Figura 4.13: De izquierda a derecha, mostramos para las 16 formas de la base de datos, las 6 más similares ordenadas según el criterio de distancia de'~ {So, S'Q). para la forma 2 de la segunda columna parece ser más razonable, desde un punto de vista perceptual, que en el primer experimento. En la figura 4.13 presentamos vm. experimento numérico en donde hemos tomado 16 formas de nuestra base de datos y hemos estimado las 6 formas más similares según el criterio de distancia Euclidiana di ' ' '{So, S'Q). En este caso, obtenemos, en algunos casos, una combinación de formas no esperada como en el caso de la forma 4 de la primera columna, o como la 8 de las segunda. De todas formas, obtenemos que la versión distorsionada incluida en nuestra base de datos es siempre la más similar (excepto para el caso de la figura 8 de la segunda columna). En la figura 4.14 presentamos un experimento numérico en donde hemos tomado 16 formas de la base de datos y hemos estimado las 6 formas más similares según el criterio de distancia Euclidiana de{So,S'Q) en donde hemos combinado 3 análisis multiescala. Nótese, que en general, la clasificación es bastante buena desde un punto de vista perceptual. En la tabla 4.1 presentamos los 4. Representación de Forméis Planas. 101 ^JH^^t/^-^ku^if^^yr^^ 15 ^1 I C % ^1 ^ma^^'^^'f^ Figiira 4.14: De izquierda a derecha, mostramos para las 16 formas de la base de datos, las 6 más similares ordenadas según el criterio de distancia de{SQ, S'Q). valores del criterio de distancia de{So,S'Q) para el experimento numérico de la figura 4.14. Observamos que para la figura 8 de la segunda columna, el único caso en que el método falla en el sentido de que la forma más similar no es la distorsionada incluida en la base de datos, las figuras son muy similares y los valores de distancia son muy bajos. También observamos que cuando no hay figuras similares en la base de datos para la figura que queremos clasificar, hay unos valores de distancia altos de entre la versión distorsionada de la forma y la más similar en nuestra base de datos, como ocurre con las formas 2,5,6,7,8 de la primera columna. A continuación presentamos algunos experimentos numéricos relativos a la clasificación invariante afín. Para simplificar la exposición daremos los resultados obtenidos con la combinación de los 3 análisis multiescalas asociados. En la figura 4.15 presentamos un experimento numérico en donde dadas 16 formas de la base de datos hemos estimado las 6 formas más similares según el criterio de distancia invariante afín da(5'o,S'¿). Primero observamos que estamos clasificando las formas desde un punto de vista de invarianza afín, y que una transformación 102 4. Representación de Formas Planas. Tabla 4.1: Para el experimento de la figura 4.14, mostramos los valores de la función distancia de{So, S'Q) 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.1-02 3.3-02 5.2-03 1.4-02 1.3-02 2.1-02 2.3-02 4.0-02 5.4-02 2.0-01 3.8-02 2.6-02 1.2-01 2.6-01 1.1-01 2.5-01 5.7-02 2.0-01 4.8-02 1.1-01 1.2-01 3.0-01 2.4-01 2.7-01 7.7-02 2.2-01 8.4-02 1.2-01 1.2-01 3.1-01 3.0-01 2.7-01 1.1-01 2.3-01 1.1-01 1.2-01 1.5-01 3.2-01 3.4-01 2.9-01 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 9.7-03 2.2-02 1.9-02 2.3-02 2.1-02 1.5-02 2.7-02 1.7-02 1.0-01 2.7-02 8.0-02 5.4-02 1.4-01 7.0-02 8.9-02 2.7-02 1.1-01 8.0-02 1.1-01 8.6-02 1.4-01 7.2-02 2.0-01 2.8-02 1.6-01 1.0-01 1.2-01 8.7-02 1.8-01 1.1-01 2.5-01 3.8-02 1.7-01 1.1-01 1.3-01 8.7-02 1.8-01 1.1-01 2.5-01 7.6-02 afín general puede modificar perceptualmente la geometría de una forma en gran medida. Por ejemplo, en la forma 4 de la segunda colunma, la forma original y la tercera más similar (en términos de distancia afín) son, de hecho, muy similares desde un punto de vista afín (hemos de expandir el eje vertical para pasar de una imagen a otra). En otras palabras, la clasificación afín no podía ser la mejor desde un punto de vista de percepción humana. En cualquier caso, los resultados han sido bastante buenos, obteniendo que de las 12 formas, el método encuentra que la forma más similar es la forma distorsionada introducida en la base de datos, en las figuras 3 de la primera columna, y en la 2 y 8 de la segunda hay otras formas en nuestra base de datos que son muy similares. El método parece fallar para la figura 4 de la segunda columna en donde la forma distorsionada no aparece entre las 6 más similares. La razón, según se muestra en la tabla 4.2 en dónde presentamos los valores del criterio de distancia (¿a(S'o,S'¿) para este experimento, es que desde el punto de vista de las transformaciones afines, la distancia entre esta forma y las propuestas es muy pequeña. Nota (robustez frente al ruido): En nuestro trabajo, no hemos hecho un énfasis especial en mejorar la robustez frente al ruido de nuestros anáfisis, porque de hecho, como podemos ver en los experimentos de la base de datos reales, nuestro análisis es muy robusto frente al ruido incluso sin ima estrategia específica para mejorar el comportamiento en este sentido. Sin embargo hay espacio para algunas mejores en el comportamiento frente al ruido, que, por falta de tiempo, no hemos examinado en este trabajo: Primero, podemos observar que 4. Representación de Formas Planas. 103 Figura 4.15: De izquierda a derecha, mostramos para las 16 formas de la base de datos, las 6 más similares ordenadas según el criterio de distancia da{So, S'Q). Tabla 4.2: Se muestra, para el experimento de la figura 4.15, los valores de la distancia da{So, S'Q) 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.3-02 4.4-02 4.4-03 3.9-02 1.9-02 8.0-02 4.5-02 2.6-02 2.6-02 1.1-01 1.1-02 3.9-02 6.7-02 2.8-01 8.4-02 6.5-02 3.0-02 1.4-01 1.4-02 8.2-02 6.8-02 3.1-01 1.5-01 7.5e-02 3.4-02 1.4-01 1.4-02 9.0-02 6.8-02 3.1-01 1.5-01 8.2-02 3.5-02 1.8-01 2.5-02 9.0-02 6.9-02 3.2-01 1.8-01 8.3-02 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 2.4-02 2.0-02 2.5-02 3.3-02 1.5-02 3.4-02 1.2-01 1.8-02 2.8-02 2.7-02 2.9-02 3.6-02 2.6-02 5.7-02 1.7-01 1.9-02 2.9-02 2.9-02 4.3-02 3.9-02 2.7-02 5.7-02 3.3-01 2.1-02 6.2-02 3.4-02 4.4-02 4.2-02 4.3-02 5.8-02 3.5-01 2.3-02 6.3-02 3.4-02 6.4-02 4.2-02 4.9-02 6.7-02 4.0-01 2.9-02 104 4. Representación de Formas Planas. cuando Pi es igual a O el análisis multiescala no posee un efecto regularizante sobre la forma, es decir, no tiende a suavizar los contornos de las formas, como es el caso, por ejemplo, del análisis multiescala generado por la ecuación de curvatura media que suaviza las formas y elimina el ruido de una forma muy eficiente. Podemos evitar el caso ^^ = O tomando como análisis multiescala (p, /?i, /3_i) = (p, —1,1), (p, —1, e), (p, —e, 1) en donde e > O sería un parámetro a ajustar en las aplicaciones. Nótese que con esta elección, mantenemos la invarianza del análisis bajo la inversión del histograma de la imagen (cambiando / por —/). En segundo lugar, observamos en los experimentos (ver figuras 4.2, 4.3, 4.5) que la mayoría del ruido se concentra en las primeras escalas de la evolución, así que la forma de mejorar el comportamiento de la robustez del ruido es la de comparar la evolución del radio isoperimétrico de dos formas no en el intervalo [O, í/] sino en el intervalo [io,if] en dónde ¿o > O sería un parámetro a ajustar en las aplicaciones. También podríamos cambiar el peso de la influencia de cada análisis multiescala en la comparación de formas. Por ejemplo, la curvatura media es el análisis multiescala más robusto respecto al ruido, así que podríamos asignar un peso mayor a este análisis multiescala en la comparación de formas. Finalmente, podríamos estimar también el área inicial de la forma de una forma más robusta. Además, en el caso en que tratáramos con formas sin agujeros en donde el contorno viniera dado por una curva de Jordán simple, sabemos que la evolución del área bajo la acción de la curvatura media viene dada por \S(t)\ = |5o| — 27rí. Así pues, podríamos aplicar la curvatura media para eliminar el ruido hasta una escala dada ¿i > O y luego estimaríamos el área inicial de la forma utilizando la fórmula \So\ = |5'(íi)| -|-27r¿i. No hemos utilizado todos estos tipos de mejoras en el comportamiento del análisis de la robustez del ruido debido a que no queríamos añadir parámetros extras a nuestros experimentos que pudieran perturbar la interpretación de los resultados (si tenemos muchos parámetros a manejar sería mucho más difícil la interpretación de los resultados). Sin embargo, tal y como hemos señalado, los resultados numéricos han sido bastante buenos incluso sin utihzar una estrategia de mejora del comportamiento de la robustez frente al ruido. Capítulo 5 Aplicaciones: Detector Morfológico de Esquinas. Una aplicación de los resultados obtenidos se refleja en la Tesis Doctoral de D. Carmelo Cuenca Hernández ([Cue03]), compañero de la Universidad de Las Palmas Gran Canaria, titulada "Reconstrucción de una Geometría Tridimensional de una escena a partir de múltiples vistas". En su trabajo, Cuenca utiliza el esquema de discretización que hemos detallado para la calibración de múltiples cámaras. A continuación se detalla un fragmento del Trabajo de Cuenca . 5.1 Extracción de puntos CEiracterísticos y calibración de un sistema con múltiples cámaras Un paso previo a dar para la calibración de un sistema con múltiples cámaras, consiste en la detección de un conjunto de características en correspondencia en las diferentes vistas. Generalmente, estas características son puntos que corresponden a las esquinas de los objetos, o rectas que corresponden a segmentos de bordes de los objetos. Para la extracción de características, en la sección 5.2, describimos un detector morfológico de esquinas desarrollado en el marco del análisis multiescala [Lin93, Lin94] que, a diferencia de otros detectores clásicos de la visión por com105 106 5. Aplicaciones; Detector Morfológico de Esquinas. putador [Can86, HS88], presenta la propiedad de depender únicamente de la forma de los objetos y no, de las condiciones de iluminación. La calibración de secuencias largas de imágenes es un problema complejo y dista mucho de ser todavía un problema resuelto en el campo de la visión por computador. 5.2 Detector morfológico de esquinas Para iniciar el proceso de calibración, es necesario haber extraído previamente un conjunto de características de las imágenes. Estas características suelen ser los puntos que definen las esquinas de los objetos o los segmentos de rectas que marcan los bordes de los objetos. La exactitud con la cual estén definidas las características influye directamente en la calidad de los resultados del proceso de calibración. En esta sección, presentamos el detector de esquinas morfológico empleado en los experimentos de reconstrucción tridimensional. Está basado en el análisis multiescala [AGLM93b, Koe84, Wit83] y presenta como principales características la invariancia frente a cambios en las condiciones de ilimiinación (que tengan la propiedad de preservar el orden de los niveles de grises de los píxeles de las imágenes), y la robustez frente al ruido. Un análisis multiescala asocia a una imagen /(x) una secuencia de imágenes con menos detalle /(x, í). Esta secuencia depende de un parámetro abstracto í > O que representa la escala, y debe cumplirse que /(x, 0) = /(x). La imagen /(x, t) recibe el nombre de análisis de la imagen /(x) a la escala t. Ocurre que los datos en la imagen /(x) no son absolutos desde el punto de vista de la percepción visual y pueden ser considerados como representativos de una determinada clase de equivalencia. Por ejemplo, si ^ representa ima transformación afín del plano y g(s) es una función monótona que representa un cambio de contraste, las imágenes g{I{x.)) e I(Ax) son equivalentes, en tanto en cuanto, contienen la misma información. Estas consideraciones nos centran en el único análisis multiescala que satisface estos requisitos de invarianza, el análisis multiescala morfológico afín. Este anáhsis multiescala viene dado por It - ¿3 (W^M^J. - 2U¿U.yU^y + ulUyy)3 (5.l) Este anáfisis multiescala fue introducida por primera vez por Álvarez, 5. Aplicaciones: Detector Morfológico de Esquinas. 107 Guichard, Lions y Morel en [AGLM93b]. El operador diferencial de la parte derecha de (5.1) no es nuevo para la detección de esquinas. De hecho, Kitchen y Rosenfeld [KR82] propusieron un detector de esquinas basado en los máximos locales del operador *^y^xx ^^x^y^xy ~r ^x V ul + ul y el cual corresponde a la segunda derivada direccionai en la dirección ortogonal al gradiente. La curvatura en el punto 2D (x, y)-^ de una línea de nivel que pasa por dicho punto 2D viene dada por el operador ^y^xx ^^x^y^xy ~r ^x •yy {ul + ulY y la detección de esquinas con esta operación es un proceso de umbralizado de los máximos locales de este operador. El principal problema de esta clase de operadores es su sensibilidad al ruido. Para evitar estos problemas, diferentes autores, [Lin93, Roh94, DG93], han propuesto soluciones basadas en el análisis multiescala lineal gaussiano (que corresponde a la convolución de la imagen original con funciones gaussianas), en las cuales, la anchura de la función gaussiana es cada vez mayor. El análisis multiescala afín presenta la ventaja, frente al operador curvatura, de posibilitar conocer el desplazamiento de la localización de los vértices a medida que la escala cambia. De hecho, Álvarez et al., en [AM97], demuestran que si (a;o, yoY ^s la localización de una esquina (un extremo de la función curvatura) en la imagen a la escala original UQ{x,y), y si o es el ángulo de la esquina, y si b = {hx,hyY es el vector unitario en la dirección de la línea bisectriz de la esquina, entonces la localización {x{t),y{t)Y del extremo de la función de curvatura, ver la figura 5.1, cambia a lo largo de la secuencia siguiendo la recta ^ ^_(&x, hyf VMf) 108 5. Aplicaciones; Detector Morfológico de Esquinas. a\ _ .ex Figura 5.1: Evolución de un extremo de la curvatura a lo largo de la bisectriz de la esquina a medida que cambia la escala. 5.2.1 Aplicación del detector de esquinsis morfológico en condiciones no ideales El resultado descrito en la sección 5.2 es válido únicamente cuando no existe ruido en las imágenes. Aún así, es posible adaptar este resultado teórico a las situaciones reales para desarrollar un algoritmo morfológico detector de esquinas robusto. Álvarez et al. describen en [ACMOl] los pasos del algoritmo: 1. En el primer paso, calculamos, utilizando el análisis multiescala descrito por la ecuación (5.1), las imágenes u{tn,x,y) a las escalas tn — to + nAt, para n = 1, • • • ,N, donde Ai representa el paso de discretización de xma escala a la siguiente y ÍQ representa la escala inicial desde la que empezamos a buscar una esquina. 2. Para la escala ¿o, calculamos la localización de los extremos de la curvatura, que denotaremos por {XQ, y^Y-, para n = 1, • • • , M, donde M es el número máximo de candidatos iniciales a ser esquinas. A continuación, seguimos estos candidatos a ser esquinas a lo largo de la escala. 3. Para cada secuencia de puntos (xjj, y^)^, calculamos de manera robusta la mejor línea que aproxima la la secuencia de puntos {x\, y^Y, esta línea corresponde a la bisectriz de la esquina. Después de eliminar los puntos clasificados como erróneos, la secuencia de puntos queda como {x\^,yl^^, Y==i...Nk- 5. Aplicaciones: Detector Morfológico de Esquinas. 109 Figura 5.2: Vistas de un calibrador Tsai. 4. Finalmente, estimamos la localización {x\y^) de la esquina asociada con la imagen original uo{x, y) como a. ix\yY = «,2/;j' -tan(-)-2í„,(6,,6,) 5.2.2 Resultados experimentales En esta sección, presentamos los resultados de la aplicación del detector morfológico de esquinas con dos secuencias de vistas, una formada por un conjunto de vistas de un calibrador de Tsai [Tsa87] y la otra, por una secuencia de vistas de unos balones con condiciones de iluminación naturales. La calidad de los resultados, la medimos en función del resultado que obtenemos en el proceso posterior de calibración. Secuencia del calibrador de Tsai La figura 5.2 son seis vistas diferentes de im calibrador de Tsai. Para localizar las esquinas de los cuadrados trazados sobre los planos del calibrador, hemos aplicado el detector morfológico de esquinas. Las posiciones de las esquinas y las correspondencias entre ellas son las entradas a los procesos de calibración descritos en anteriores apartados de nuestro trabajo. Capítulo 6 Conclusiones. Como ya se ha podido apreciar a lo largo de nuestro trabajo, hemos centrado nuestra atención en dos partes bien diferenciadas. Por un lado hemos dedicado parte de nuestro esfuerzo a la búsqueda de una forma alternativa de discretización de operadores no lineales que aparecen en algunas ecuaciones en derivadas parciales que son importantes al utilizarse como parte de diversos análisis multiescalas morfológicos. Para ello, hemos perseguido en todo momento, tanto la minimización del error cometido de forma estándar, como la minimización del error cometido en las direcciones del gradiente y ortogonal al mismo, debido a que en esas direcciones aparece el mayor y menor valor del error cometido, respectivamente. Las imágenes utilizadas para aplicar los análisis multiescalas correspondientes han sido diseñadas expresamente debido a que en cada caso elegido, se conocía "a priori" la evolución teórica de los parámetros analizados (en nuestro caso, los radios de los círculos y/o elipses diseñadas), lo cual nos ha permitido, no sólo hacer un estudio comparativo sobre distintos valores del parámetro (uno de ellos el objeto perseguido en nuestro trabajo, AQ), sino también comparar dichos valores con los datos reales (teóricos) conocidos de antemano sobre las imágenes con las que hemos experimentado. Los algoritmos utilizados en la aplicación de los análisis multiescala morfológicos (filtros) a las imágenes pre-elaboradas sintéticamente han sido algoritmos sencillos e iterativos. Los resultados obtenidos en este caso han sido muy satisfactorios, bajo nue117 118 6. Conclusiones. stro punto de vista. No sólo se detalla teóricamente que el resultado podría ser bueno, sino que los resultados numéricos nos demuestran en casi la totalidad de los casos que dichos estudios teóricos eran acertados. En ese sentido, creemos que hemos cumplido nuestro objetivo inicial. Por otro lado, hemos intentado aplicar las propiedades de los análisis multiescala morfológicos para intentar encontrar imo o varios parámetros que indicaran de alguna manera como van evolucionando distintas formas concretas (figuras) en el tiempo, según iban actuando dichos anáfisis multiescala. Para ellos buscábamos proponer una representación invariante de formas geométricas utilizando el análisis multiescala morfológico. Esta invarianza geométrica se basa en la evolución del área y del perímetro de la forma bajo la acción de xm análisis multiescala morfológico. Se ha presentado, en un principio, algunos resultados teóricos sobre la evolución del perímetro y del área de las formas. Distinguimos dos tipos de invariantes para identificar las formas anaüzadas, según fueran formas euclídeas, o bien formas invariantes afines. En caso de tener transformaciones de similitud, el invariante geométrico propuesto se basa en la evolución normalizada en escala del cociente isoperimétrico de la forma. En el segundo caso de trasnformaciones geométricas afines generales, el invariante geométrico lo hemos basado en la evolución normalizada en escala del área. Para cada uno de los casos, diseñamos un pequeño conjunto de formas sintéticas que nos permitían testear la evolución de cada tipo de invariante propuesto, que podría en cada caso identificar un tipo de forma distinto. Los resultados numéricos nos permitieron corroborar nuestros resultados teóricos propuestos. Por supuesto, en los algoritmos presentados para la obtención de los resultados numéricos se han utilizado las técnicas desarrolladas en el capítvilo 3 de nuestro trabajo. Primero presentamos algunas experiencias utilizando la evolución del cociente isoperimétrico normalizado en escala. En todos los casos, excepto para el círculo, todas las formas tenían un cociente isoperimétrico inicial similar. De hecho, todas las formas deberían tener teóricamente el mismo, aunque en la práctica el ruido y los errores numéricos calculados hacen que dicho cociente no sea el mismo. Para el conjunto de formas sintéticas utilizadas se han realizado transformaciones de similitud en donde se han rotado y se ha cambiado el tamaño original de la forma. Así, existen formas eqmvalentes módulo invariantes en similitud, en 6. Conclusiones. ^ 119 donde podríamos definir una relación de equivalencia implícita en la que dos formas están relacionadas si son invariantes en similitud. Pues bien, siguiendo los invariantes propuestos, hemos concluido que podemos discriminar bastante bien una forma de entre todas las demás, o sea, que podemos obtener un representante de cada clase de equivalencia, y dentro de la relación de equivalencia definida, dar el conjunto cociente. Esto es debido a que cada representante de las distintas clases de equivalencia (conjunto cociente) tiene una evolución de su cociente isoperimétrico normalizado en escala similar, casi "idéntico" (con un margen pequeño de error). De la misma forma, se ha diseñado otro conjimto de imágenes sintéticas (especialmente diseñadas según el invariante que nos interesaba identificar). En este caso hemos aplicado una transformación afín en donde hemos cambiado las medidas horizontales y verticales de las mismas de forma distinta. Establecemos, de igual forma, una relación de equivalencia entre las formas de igual manera que se explicó en el caso anterior. En este caso, como la evolución del perímetro en el tiempo no es adecuada, se analizó la evolución del área para las distintas transformaciones de las formas. Dentro de esta parte del capítiilo, hemos realizado una aplicación a la clasificación de formas. Para ello se ha utilizado una base de datos real deserroUada por la Universidad de Surrey. Partimos de una selección de 200 formas de esta base de datos. Con el objetivo de introducir ruido real a las formas, se han impreso, rotado y escaneado algunas de las formas y se han añadido a la base de datos (previa normalización del tamaño de las formas para poder incluirlas todas en una única imagen). El problema que se ha tratado consiste en, dada una forma, intentar encontrar las formas más parecidas de la base de datos, siguiendo algún criterio de distancia. En el caso de las formas euclídeas y dado un análisis multiescala invariante por similitudes, definimos una distancia basada en los cocientes isoperimétricos normalizados en escala, y para el caso de representación de formas invariantes afines definimos otro distinto basado en los cocientes normalizados en escala de las áreas. En ambos casos, y para obtener un comportamiento discriminatorio más fuerte se han combinado la información de diversos análisis multiescala. Los resultados obtenidos han sido francamente buenos desde el punto de vista perceptual. Algunas excepciones (fallos del método propuesto) se explican detalladamente en el capítulo y se da una explicación a las mismas. 120 6. Conclusiones. Por tanto, y a modo de conclusión final, podemos decir que los análisis multiescalas morfológicos proporcionan una herramienta muy útil en el análisis de imágenes; los algoritmos de discretización propuestos funcionan bien para aproximar dichos análisis multiescalas, y la representación invariante de las formas propuestas explota toda la potencia de estos análisis y permite discriminar correctamente entre las formas. Capítulo 7 Trabajos Futuros. Las posibles ampliaciones que proponemos al trabajo realizado son las siguientes: Aceleración de los algoritmos propuestos. Por un lado, y en la parte de discretización de operadores diferenciales no lineales, las imágenes utilizadas para aplicar los análisis multiescalas correspondientes han sido diseñadas expresamente debido a que en cada caso elegido, se conocía "a priori" la evolución teórica de los parámetros analizados (en nuestro caso los radios de los círculos y/o elipses diseñadas), lo cual nos ha permitido no sólo hacer un estudio comparativo sobre distintos valores del parámetro (uno de ellos el objeto perseguido en nuestro trabajo) AQ, sino comparar dichos valores con los datos reales (teóricos) conocidos de antemano sobre las imágenes con las que hemos experimentado. Los algoritmos utilizados en la aplicación de los análisis multiescala morfológicos (filtros) a las imágenes pre-elaboradas sintéticamente han sido algoritmos sencillos e iterativos. Una de las posibles mejoras podrían incidir en el tipo de algoritmos utilizados, de forma que se pudieran acelerar la acción de los mismos sobre las imágenes de entrada. En un principio, nunca se persiguió que los programas generaran salidas muy rápidas, aún cuando el tiempo que se utilizaban para generar los resultados numéricos eran enormes. Debido a que los ficheros de datos eran grandes, quizá una de las posibles y futuras implementaciones para utilizar en aplicaciones de la discretización propuesta por nosotros de los operadores analizados podría ser la optimización de los algoritmos de entrada, bien analizando la posible inclusión 121 122 7. Trabajos Futuros. de paralelismo en los mismos o bien refinando los procedimientos y funciones utilizado. Asimismo, podría haberse utilizado algima imagen real en la que se pudiera ver la aplicación de los parámetros seleccionados para la discretización de nuestros operadores, tal y como se presentó en el capítulo 5, un resumen del trabajo realizado por el compañero D. Carmelo Cuenca para la búsqueda de esquinas de imágenes reales. En nuestro caso, no se utilizó ninguna imagen real debido a que queríamos realizar un estudio comparativo con un resultado teórico y las imágenes sintéticas eran la mejor forma de hacerlo. Mejora de la robustez frente ed ruido. Por otro lado, y dentro de la búsquedas de invariantes geométricos en nuestro trabajo, no hemos hecho un énfasis especial en mejorar la robustez frente al ruido de nuestros análisis, porque de hecho, como podemos ver en los experimentos de la base de datos reales, nuestro análisis es muy robusto frente al ruido incluso sin una estrategia específica para mejorar el comportamiento en este sentido. Sin embargo hay espacio para algunas mejoras en el comportamiento frente al ruido, que,no hemos explorado en este trabajo: Primero, podemos observar que cuando ^^ es igual a O el análisis multiescala no posee un efecto regularizante sobre la forma, es decir, no tiende a suavizar los contornos de las formas, como es el caso, por ejemplo, del análisis multiescala generado por la ecuación de curvatura media que suaviza las formas y elimina el ruido de una forma muy eficiente. Podemos evitar el caso /3-¡^ = O tomando como análisis multiescala {p, /5i, /?_i) = {{p, —1,1), {p, —1, e), {p, —e, 1)} en donde e > O sería un parámetro a ajustar en las aplicaciones. Nótese que con esta elección, mantenemos la invarianza del análisis bajo la inversión del histograma de la imagen (cambiando / por —/)• En segundo lugar, observamos en los experimentos que la mayoría del ruido se concentra en las primeras escalas de la evolución, así que la forma de mejorar el comportamiento de la robustez del ruido es la de comparar la evolución del radio isoperimétrico de dos formas no en el intervalo [O, í/j sino en el intervalo [ío, ij] en dónde ío > O sería un parámetro a ajustar en las aplicaciones. También podríamos cambiar el peso de la influencia de cada análisis multiescala en la comparación de formas. Por ejemplo, la curvatm-a media es el análisis multiescala más robusto respecto al ruido, así que podríamos asignar un peso mayor a este anáüsis multiescala en la comparación de formas. Finalmente, podríamos 7. Trabajos Futuros. 123 estimar también el área inicial de la forma de una forma más robusta. Además, en el caso en que tratáramos con formas sin agujeros en donde el contorno viniera dado por una curva de Jordán simple, sabemos que la evolución del área bajo la acción de la curvatura media viene dada por 15(^)1 = \So\ — 2nt. Así pues, podríamos aplicar la curvatura media para eliminar el ruido hasta una escala dada íi > O y luego estimaríamos el área inicial de la forma utilizando la fórmula |S'o| = |S'(íi)| -|-27ríi. No hemos utilizado todos estos tipos de mejoras en el comportamiento del análisis de la robustez del ruido debido a que no queríamos añadir parámetros extras a nuestros experimentos que pudieran perturbar la interpretación de los resultados (si tenemos muchos parámetros a manejar sería mucho más difícil la interpretación de los resultados). Sin embargo, tal y como hemos señalado, los resultados numéricos han sido bastante buenos incluso sin utilizar una estrategia de mejora del comportamiento de la robustez frente al ruido. Aplicación de los esquemas de discretización a otras ecuaciones. Otro aspecto que queremos abordar en el futuro es la aplicación de los esquemas de discretización propuestos para los operadores diferenciales estudiados a otro tipo de ecuaciones diferenciales distintas de las asociadas a los análisis multiescala morfológicos. Existen muchas ecuaciones y modelos en visión por computador que utilizan de alguna forma operadores diferenciales direccionales como los estudiados en este trabajo. Un buen ejemplo de ello es el modelo de snakes propuesto por Caselles, Kimmel y Sapiro, basado en la ecuación donde observamos que aparece el término div (Ñ^^) ||VIÍ|| que corresponde al operador de curvatura media estudiado en este trabajo. Por tanto, podríamos aplicar las técnicas aqm' propuestas para discretizar la anterior ecuación. Bibliografía [AB86] H. Asada and M. Brady. The curvatiire primal sketch. IEEE Transactions on PAMI, 8:2-14, 1986. [ACMOl] L. Ál varez, C. Cuenca, and L. Mazorra. Morphological comer detection. apphcation to camera caUbration. In Proceedings of the lASTED International Conference on Signal Processing, Pattem Recognition, and Applications. Rhodes, Grecia, pages 21-26. The International Association of Science and Technology for Development - lASTED, July 2001. [AE97] L. Alvaxez and J. Esclarin. Image quantification using reactiondifFusion equations. SIAM J. on Applied Mathematics., 57(1):153175, 1997. [AGLM92a] L. Alvarez, F. Guichard, P.L. Lions, and J.M. Morel. Analyse m\iltiechelle de films. C. R. Acad. Sci. París, 315(1):1145-1148, 1992. [AGLM92b] L. Alvarez, F. Guichard, P.L. Lions, and J.M. Morel. Axiomatization et nouveaux operateurs de la morphologie mathematique. C. R. Acad. Sci. Paris, 315(1):265-268, 1992. [AGLM92c] L. Alvarez, F. Guichard, P.L. Lions, and J.M. Morel. Axiomes et equations fondamentales du traitement d'images (analyse multiechelle et e.d.p.). C. R. Acad. Sci. Paris, 315(1):135-138, 1992. [AGLM93a] L. Alvarez, F. Guichard, P.L. Lions, and J.M. Morel. Axioms and fundamental equations of image processing. Arch. for Rat. Mechanics, 123(3): 199-257, 1993. 125 126 BIBLIOGRAFÍA [AGLM93b] L. Ál varez, F. Guichard, P.L. Lions, and J.M. Morel. Axioms and fundamental equations of image processing. Arch. for Rat. Mechantes, 123(3): 199-257, 1993. [ALM92] L. Alvarez, P.L. Lions, and J.M. Morel. Image selective smoothing and edge detection by nonlinear diíiusion (ii). SIAM J. on Numerieal Analysis, 29(3):845-866, 1992. [AM94a] L. Alvarez and L. Mazorra. Signal and image restoration using shock filter and anisotropic diífusion. SIAM J. on Numerieal Analysis, 31(2):590-605, 1994. [AM94b] L. Alvarez and F. Morales. AfRne morphological multiscale analysis of corners and múltiple junctions. submitted to International Journal of Computer Vision, 1994. [AM94c] L. Alvarez and J.M. Morel. Formalization and computational aspects of image analysis. Aeta Numeriea, pages 1-61, 1994. [AM94d] L. Alvarez and J.M. Morel. A morphologieal approaeh to multiscale analysis. Prom principies to equations, pages 249-276. Kluwer Academia Publishers, 1994. [AM97] L. Ál varez and F. Morales. Affine morphological multiscale analysis of corners and múltiple jvmctions. International Journal of Computer Vision, 25(2):91-105, 1997. [Can86] J. Canny. A computational approaeh to edge detection. IEEE Transactions on Pattem Analysis and Machine Inteligence, 8(6):679-698, /1986. [CCLM92] F. Catté, T. CoU, P.L. Lions, and J.M. Morel. Image selective smoothing and edge detection by nonlinear diífusion. SIAM Journal on Numerieal Analysis, 29(1):182-193, February 1992. [CIL92] M. G. Crandall, H. Ishii, and P. L. Lions. User's guide to viscosity Solutions of second order partial diferential equations. Bulletin of the American Mathematical Society, (27): 1-67, 1992. BIBLIOGRAFÍA 127 [CLM94] T. Cohignac, C. López, and J. M. Morel. Integral and local afRne invariant parameter and application to shape recognition. Proceedings of ICPR conference, pages 164-168, 1994. [CM95] T. Cohignac and J. M. Morel. Scale space and afíine invariant recognition of occluded shapes. Proceedings of Spie conference, investígate and triol image processing, 2567:214-222, 1995. [Cue03] C. Cuenca. Reconstrucción de Una Geometría Tridimensional de Una Escena a Partir de Múltiples Vistas. PhD thesis. Universidad de Las Palmas de Gran Canaria, Departamento de Informática y Sistemas, 2003. [Der90] R. Deriche. Fast algorithms for low-level visión. IEEE Transactions on Pattem Analysis and Machine Intellegence, 12(l):78-87, 1990. [DG93] R. Deriche and G. Giraudon. A computational approach for córner and vértex detection. IJCV, 10(2): 101-124, 1993. [Fau93] O. Faugeras. Three-Dimensional Computer Vision: A Geometric Viewpoint. MIT Press, 1993. [GA93] G.Sapiro and A.Tannenbaum. Affine invariant scale space. International Journal of Computer Vision, 11:25-44, 1993. [HS88] Chris Harris and Mike Stephens. A combined córner and edge detector. In M. M. Matthews, editor, Proceedings of the 4th ALVEY visión conference, University of Manchester, England, pages 147151, September 1988. [Koe84] J.J. Koenderink. The structure of images. BioCyber, 50:363-370, 1984. [KR82] L. Kitchen and A. Rosenfeld. Gray level comer detection. Pattem Recognition Letters, 1:95-102, Dec 1982. [LAM93] P.-L. Lions L. Alvarez, F. Guichard and J.-M. Morel. Axioms and fundamental equations in image processing. Arch. Rational Mech. Anal, 123:199-257, 1993.