deteccion y seguimiento de´ eyecciones coronales masivas...

Universidad de Buenos AiresFacultad de Ciencias Exactas y Naturales

Departamento de Computacion

Deteccion y seguimiento deeyecciones coronales masivas en

secuencias de imagenes

Tesis presentada para optar al tıtulo de Licenciatura enCiencias de la Computacion de la Universidad de Buenos

Aires

Norberto Goussies

Directora de tesis: Dra. Marta Estela MejailBuenos Aires, 2008

2

A mis viejosA mi familia

RESUMEN

El Observatorio Solar y Heliosferico -SOHO-, una mision conjunta de las agenciasESA/NASA, fue lanzado en diciembre de 1995 para comprender mejor el Sol. El estu-dio del sol es importante debido a que las tormentas solares pueden afectar los sistemastecnologicos, de los cuales nos hemos convertido muy dependientes.

Las eyecciones coronales masivas son un tipo de evento que se pueden observar enlas imagenes provenientes del SOHO. La gran cantidad de informacion provista porlos instrumentos dentro del SOHO y, mas recientemente, del Solar Terrestrial Rela-tions Observatory (STEREO) hace que la deteccion y el seguimiento de eyeccionescoronales masivas basada en la valoracion un experto, sea excesivamente costosa. Eneste trabajo presentamos metodos automaticos para la deteccion y el seguimiento deeyecciones coronales masivas.

El metodo propuesto se basa en un modelo de competicion de regiones, en el cualse busca encontrar los contornos de los objetos que componen una imagen mediantela minimizacion de un funcional que incluye un modelo estadıstico sobre los objetos.Se propone un nuevo modelo estadıstico que utiliza matrices de co-ocurrencias pararepresentar texturas de las eyecciones coronales masivas.

La minimizacion del funcional se logra evolucionando una curva mediante un cam-po de velocidad, que se obtiene del funcional a minimizar. Las tecnicas de conjuntos denivel han sido propuestas como una implementacion numerica para analizar y describirla evolucion de la curva. Proponemos una modificacion a una implementacion rapidade conjuntos de nivel.

Resumen 4

Agradecimientos

Gracias a Marta por todo el tiempo y esfuerzo que invirtio en mı.Gracias a Julio por sus valiosos comentarios.Gracias a Motta por estar en las buenas y en las malas.Gracias a los pibes, con los que curse casi todas las materias y compartimos tantas

noches y fines de semanas estudiando.Gracias a Guillermo Stenborg por mostrarme la pasion que tiene en analizar la

informacion del SOHO y explicarme lo que el observa en las imagenes.Gracias al Programa Academico de Microsoft por los fondos aportados para el

desarrollo de la tesis.

INDICE GENERAL

1.. INTRODUCCION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.. PRELIMINARES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.1. Nociones de procesamiento imagenes . . . . . . . . . . . . . . . . . 132.2. Ecuaciones diferenciales . . . . . . . . . . . . . . . . . . . . . . . . 142.3. Calculo de variaciones . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.. EVOLUCION DE CURVAS . . . . . . . . . . . . . . . . . . . . . . . . . 173.1. Propiedades de las funciones implıcitas . . . . . . . . . . . . . . . . 193.2. Funciones de distancias con signo . . . . . . . . . . . . . . . . . . . 193.3. Evolucion por normal . . . . . . . . . . . . . . . . . . . . . . . . . . 213.4. Evolucion por curvatura . . . . . . . . . . . . . . . . . . . . . . . . . 223.5. Metodos basados en la resolucion de las PDEs . . . . . . . . . . . . . 233.6. Metodos rapidos sin resolver PDEs . . . . . . . . . . . . . . . . . . . 24

3.6.1. Primer Paso . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.6.2. Segundo Paso . . . . . . . . . . . . . . . . . . . . . . . . . . 283.6.3. Algoritmo Completo . . . . . . . . . . . . . . . . . . . . . . 31

3.7. Metodo rapido basado en representacion regiones y contornos . . . . 313.7.1. Representacion de la region . . . . . . . . . . . . . . . . . . 343.7.2. Evolucion de la curva . . . . . . . . . . . . . . . . . . . . . . 34

3.8. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.. SEGMENTACION DE IMAGENES POR EVOLUCION DE CURVAS . . . 374.1. Segmentacion basada en bordes . . . . . . . . . . . . . . . . . . . . 37

4.1.1. Contornos activos geodesicos . . . . . . . . . . . . . . . . . 384.2. Segmentacion basada en regiones . . . . . . . . . . . . . . . . . . . . 38

4.2.1. Contornos activos sin bordes . . . . . . . . . . . . . . . . . . 38

5.. EVOLUCION DE CURVAS BASADO EN REGIONES . . . . . . . . . . . 415.1. Maximum a posteriori de la particion de la imagen . . . . . . . . . . 42

5.1.1. Restricciones sobre la particion . . . . . . . . . . . . . . . . 425.1.2. Restricciones sobre las regiones . . . . . . . . . . . . . . . . 425.1.3. Formulacion de la energıa . . . . . . . . . . . . . . . . . . . 435.1.4. Minimizacion de la energıa . . . . . . . . . . . . . . . . . . . 43

5.2. Vectores de caracterısticas . . . . . . . . . . . . . . . . . . . . . . . 445.2.1. Caracterizacion de regiones con texturas . . . . . . . . . . . . 44

5.3. Modelos estadısticos . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Indice general 6

5.3.1. Modelos basados en estadıstica parametrica . . . . . . . . . . 465.3.2. Modelos basados en estadıstica no parametrica . . . . . . . . 475.3.3. Modelos basados en test de hipotesis . . . . . . . . . . . . . . 49

5.4. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

6.. APLICACION A LA DETECCION Y SEGUIMIENTO DE CMES EN SE-CUENCIA DE IMAGENES . . . . . . . . . . . . . . . . . . . . . . . . . 536.1. Modelo de deteccion de CMEs . . . . . . . . . . . . . . . . . . . . . 546.2. Modelo de seguimiento de CMEs . . . . . . . . . . . . . . . . . . . . 556.3. Calculo de propiedades de los CME . . . . . . . . . . . . . . . . . . 586.4. Deteccion y seguimiento basado en niveles de gris y metodos parametri-

cos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606.5. Deteccion y seguimiento basado en texturas y metodos basados en test

de hipotesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636.6. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

7.. RESULTADOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

8.. CONCLUSIONES Y TRABAJO FUTURO . . . . . . . . . . . . . . . . . 70

Bibliografıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

INDICE DE FIGURAS

1.1. Imagen proveniente del LASCO C2. . . . . . . . . . . . . . . . . . . 10

3.1. Representacion implıcita de la curva x2 + y2 = 1 mediante la funcionde conjuntos de nivel φ = x2 + y2−1. . . . . . . . . . . . . . . . . . 18

3.2. Representacion implıcita de la curva x2 + y2 = 1 mediante la funcionde conjuntos de nivel φ =

√x2 + y2−1 (en azul). La interseccion de la

funcion con el plano z = 0, en celeste, es el conjunto de nivel cero. . . 203.3. Evolucion de curva en direccion de la normal. . . . . . . . . . . . . . 213.4. Evolucion de curva por curvatura. . . . . . . . . . . . . . . . . . . . 223.5. Funcion de distancia con signo en una banda angosta cerca del conjunto

de nivel cero. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.6. Curva (marcada en negrito) representada mediante listas Lin, Lout y φ. 273.7. Diferentes Fa juste para evolucionar la curva de la Fig. 3.6. . . . . . . . 273.8. Evolucion del contorno mediante los valores de Fa juste de la Fig. 3.7(b),

utilizando el Alg. 4. . . . . . . . . . . . . . . . . . . . . . . . . . . 273.9. Evolucion del contorno mediante los valores de Fa juste de la Fig. 3.7(a),

utilizando el Alg. 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.10. Resultado de eliminar los puntos redundantes de la de la representacion

de la curva de la Fig. 3.8, mediante el Alg. 5. . . . . . . . . . . . . . 293.11. Resultado de eliminar los puntos redundantes de la curva de la Fig. 3.9,

mediante el Alg. 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.12. Evolucion de la curva de la Fig. 3.8 mediante el Alg. 10, con una itera-

cion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.1. Segmentacion utilizando diferentes valores de µ. . . . . . . . . . . . . 394.2. Comparacion del resultado de la segmentacion de contornos activos sin

bordes, usando el metodo de banda angosta y resolviendo las PDEs. . 40

5.1. Ejemplo de regiones homogeneas, el fondo fue creado con una distri-bucion gaussiana de niveles de gris de media 128 y desviacion estandar20. La cara de Mickey Mouse fue creada con una distribucion gaussia-na de niveles de gris de media 128 y desviacion estandar 80. . . . . . 41

5.2. Fuerzas estadısticas actuando sobre un punto entre dos regiones. . . . 445.3. Estimacion de la funcion de densidad utilizando un nucleo Gaussiano

y variando el h. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Indice de figuras 8

5.4. Funciones de densidad de dos distribuciones Normales. La distribucionde la izquierda tiene media menos uno y varianza uno, la de la derechatiene media uno y misma varianza. La region en gris es la de posibleclasificacion erronea, la cual tiene probabilidad del 32 %. . . . . . . . 49

5.5. Funciones de densidad de dos distribuciones Normales. Una distribu-cion tiene media cero y varianza dos, la otra tiene la misma media perovarianza cuatro. La region en gris es la de posible clasificacion erronea,la cual tiene probabilidad del 55 %. . . . . . . . . . . . . . . . . . . . 50

5.6. Comparacion entre regiones de clasificacion erronea para el par de dis-tribuciones N(µ1,σ

21) y N(µ2,σ

22) (lıneas solidas) y para el par de dis-

tribuciones N(µ1,σ2

1m ) y N(µ2,

σ22

m ) (lıneas punteadas) que se obtienentomando ventanas de tamano m. . . . . . . . . . . . . . . . . . . . . 50

5.7. Estimacion de matrices de co-ocurrencia. . . . . . . . . . . . . . . . 52

6.1. Comparacion de imagenes utilizando la tecnica de running differencespara realzar el contraste de los CMEs. . . . . . . . . . . . . . . . . . 53

6.2. Imagen en la que se puede observar el leading edge brillante, la regionoscura que le sigue, la cola del CMEs y el disco oclutor. . . . . . . . . 54

6.3. Disposicion y evolucion del contorno inicial para detectar CMEs enuna imagen con CME. . . . . . . . . . . . . . . . . . . . . . . . . . 56

6.4. Disposicion y evolucion del contorno inicial para detectar CMEs enuna imagen sin CME. . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.5. Seguimiento de CMEs usando el Alg. 19 de varios CMEs. . . . . . . 596.6. Propiedades de una CME segmentada. El punto D es el punto mas dis-

tante del contorno de la CME desde el centro del Sol. Los vectoresA y B son los bordes laterales izquierdo y derecho. El vector C es elresultado de la suma de los vectores A y B, que permite calcular el CPA. 60

6.7. Deteccion y seguimiento exitoso de CME observado por LASCO/C2,usando modelo basado en competicion de regiones con niveles de grisy suponiendo distribuciones Normales. . . . . . . . . . . . . . . . . . 61

6.8. Deteccion y seguimiento fallido de CME observado por LASCO/C2,usando modelo basado en competicion de regiones con niveles de grisy suponiendo distribuciones Normales. . . . . . . . . . . . . . . . . 62

6.9. Histogramas de la CME y del fondo de la Fig. 6.8(a). . . . . . . . . . 636.10. Matrices de co–ocurrencia para un CME (gris oscuro) y para el fondo

(gris claro). Cada columna corresponde a un bin de 32 niveles de gris. 646.11. Deteccion y seguimiento de CME observado por LASCO/C2, usando

el modelo propuesto. El mismo CME no pudo ser seguido utilizando elmetodo de la seccion anterior. . . . . . . . . . . . . . . . . . . . . . 65

6.12. Deteccion y seguimiento de CME observado por LASCO/C2, usandoel modelo propuesto. El mismo CME pudo ser seguido utilizando elmetodo de la seccion anterior. . . . . . . . . . . . . . . . . . . . . . 66

LISTA DE ALGORITMOS

1. ContraerContorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252. ExpandirContorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263. ContraerContornoAjuste . . . . . . . . . . . . . . . . . . . . . . . . 264. ExpandirContornoAjuste . . . . . . . . . . . . . . . . . . . . . . . . 265. EliminarPuntosRedundantesEnLin . . . . . . . . . . . . . . . . . . . 286. EliminarPuntosRedundantesEnLout . . . . . . . . . . . . . . . . . . 297. Primer Paso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308. ExpandirContornoSuavizado . . . . . . . . . . . . . . . . . . . . . . 309. ContraerContornoSuavizado . . . . . . . . . . . . . . . . . . . . . . 3010. Segundo Paso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3111. Evolucion rapida de Conjuntos de Nivel . . . . . . . . . . . . . . . . 3212. ExpandirContornoModificado . . . . . . . . . . . . . . . . . . . . . 3313. ContraerContornoModificado . . . . . . . . . . . . . . . . . . . . . . 3314. AgregarPunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3415. EliminarPunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3516. Evolucion rapida de Conjuntos de Nivel utilizando la region . . . . . 3617. Calcular matriz de co-ocurrencia . . . . . . . . . . . . . . . . . . . . 4518. Deteccion de CMEs . . . . . . . . . . . . . . . . . . . . . . . . . . . 5519. Seguimiento de CMEs . . . . . . . . . . . . . . . . . . . . . . . . . 5820. Ancho angular de una CME . . . . . . . . . . . . . . . . . . . . . . 59

1. INTRODUCCION

El Observatorio Solar y Heliosferico -SOHO- [DFP95], una mision conjunta de lasagencias ESA/NASA, fue lanzado en Diciembre de 1995 para comprender mejor elSol. El estudio de este ultimo es importante debido a que las tormentas solares puedenafectar los sistemas tecnologicos, de los cuales nos hemos convertido muy dependien-tes.

El satelite SOHO consiste de 12 instrumentos, entre los cuales se encuentra el LAS-CO (Large Angle and Spectrometric Coronagraph) que consiste de un conjunto de trescoronografos: C1, C2 y C3. Detalles tecnicos sobre los coronografos del LASCO sepueden encontrar en [BHK+95].

Un coronografo es un instrumento que bloquea la luz proveniente del disco solar(creando un eclipse solar artificial) para revelar las debiles senales de luz blanca pro-venientes de las capas superiores de la atmosfera solar, llamada corona solar.

En la Fig. 1.1(a) se puede observar una imagen, sin procesar, proveniente del LAS-CO C2; el disco negro del centro es el disco oclutor, que se utiliza para bloquear la luzsolar. Debido a que las Eyecciones Coronales Masivas (CMEs por sus siglas en ingles),en este tipo de imagenes, suelen ser muy debiles existen varias tecnicas para realzar sucontraste. La mas usada se conoce como running differences (diferencias corridas), enla cual se restan dos imagenes sucesivas. En la Fig. 1.1(b) se puede observar la imagenrealzada.

(a) Imagen proveniente del LASCO C2sin procesar.

(b) Imagen proveniente del LASCO C2realzada usando running differences.

Fig. 1.1: Imagen proveniente del LASCO C2.

Uno de los tipos de eventos que los fısicos solares estan interesados en detectar y

1. INTRODUCCION 11

seguir son las CMEs, las cuales son vistas dentro del campo de vision de un coronogra-fo como una nueva y discreta luz blanca que se mueve con velocidad radial saliente.Si se dirige hacia la Tierra (y obedece caracterısticas particulares) puede llegar a oca-sionar apagones (debido a la produccion de picos de tension en las redes electricas) ycausar auroras.

Los algoritmos disenados para detectar y seguir CMEs usando las imagenes pro-venientes de los coronografos, deben lidiar con una amplia gama de dificultades. Paranombrar algunas, los CMEs son diferentes entre sı y, aunque mantengan algunas desus propiedades constantes durante su desarrollo, en las imagenes capturadas por loscoronografos, el contraste con respecto al fondo puede variar enormemente de una ima-gen a la siguiente. Pueden desarrollarse varios CMEs en forma cercana, tanto espacialcomo temporalmente. Las imagenes obtenidas por los coronografos son la proyeccionde fenomenos en tres dimensiones. Ademas, aun no existe una definicion objetiva deCME, es decir, que tan grande o luminoso debe ser el evento para ser considerado comotal.

El problema se ha atacado en [RB04] obteniendose diferentes grados de exito de-pendiendo de la secuencia de imagenes analizadas. El metodo propuesto en [RB04]consiste en dos pasos. En el primer paso se preprocesan las imagenes de los coronogra-fos C2 y C3, reduciendo el tamano de las mismas, transformandolas a coordenadas po-lares y ordenandolas cronologicamente para obtener un arreglo tridimensional [θ,r, t].En el segundo paso, utilizando la transformada de Hough para lıneas, para cada unode los sub arreglos [r, t] se detectan los eventos que suceden y se agrupan utilizandotecnicas de clustering.

El objetivo en este trabajo, al igual que en [RB04], es generar una lista de eventosdetectados en una secuencia de imagenes de los coronografos LASCO C2/C3. Sin em-bargo, en esta tesis proponemos un metodo diferente e innovador para la deteccion yel seguimiento de los CMEs. El metodo, se basa en la segmentacion del frente de losCMEs en cada imagen. En particular, el resultado de la segmentacion de una imagen dela secuencia se usa como estimacion inicial para la segmentacion en la siguiente ima-gen. Es decir, la deteccion y el seguimiento de los CMEs se convierte en un problemade segmentacion.

Varias tecnicas de segmentacion pueden encontrarse en la literatura. Entre ellas po-demos citar la propuesta por Comaniciu y Meer [CM02], que se basa en mean shift, o lapropuesta por Shi y Malik [SM00], donde el problema se trata como el de particionadode grafos. En contraste, en esta tesis seguimos un enfoque basado en templates defor-mables, propuestos por Terzopoulos a finales de los 80’s y basados en la minimizacionde un funcional.

El modelo de competencia de regiones [ZLY95] busca encontrar los contornos delos objetos que componen una imagen mediante la minimizacion de un funcional que seobtiene de suponer que los pixels de una region pueden modelarse con una distribucionestadıstica apropiada.

La minimizacion del funcional se logra evolucionando una curva mediante un cam-po de velocidad, que se obtiene del funcional a minimizar. Las tecnicas de conjuntosde nivel [OS88] han sido propuestas como una implementacion numerica para analizary describir la evolucion de la curva. En este trabajo proponemos una modificacion a laimplementacion rapida de conjuntos de nivel presentada en [SK05].

1. INTRODUCCION 12

Ademas, se propone un nuevo modelo estadıstico para las regiones, que se basaen el test estadıstico chi-cuadrado para lidiar con regiones que son difıciles de distin-guir entre sı usando informacion de un solo pixel, o cuando es difıcil encontrar unafamilia de distribuciones para modelar las regiones. Esta estrategia es diferente a la delmodelo de competencia de regiones [ZLY95], en la cual se utiliza un modelo basadoen estadıstica parametrica y que, en las circunstancias descritas, su desempeno se veseveramente afectado.

El nuevo metodo de segmentacion propuesto, se utiliza para la segmentacion delfrente de las CMEs, luego de analizar los problemas que se encuentran al intentar utili-zar el modelo de competencia de regiones [ZLY95]. El metodo es supervisado y requie-re que se estimen los histogramas de la regiones a segmentar. Ademas, utiliza matricesde co-ocurrencias para representar texturas de las CMEs.

La tesis esta organizada de la siguiente manera:

En la Sec. 2 hacemos una breve introduccion a las herramientas y notacionesmatematicas que se usan a lo largo de la tesis.

En la Sec. 3 presentamos el problema de evolucion de curvas, haciendo especialhincapie en los metodos de conjuntos de nivel [OS88]. Y vemos diferentes im-plementaciones numericas. Ademas, proponemos un nuevo metodo de evolucionde curvas, basado en el propuesto en [SK05].

En la Sec. 4 presentamos algunos modelos de segmentacion de imagenes pro-puestos en la literatura que utilizan conjuntos de nivel.

En la Sec. 5 vemos modelos de segmentacion de imagenes basados en una inter-pretacion estadıstica del problema de segmentacion de imagenes. Proponemosel nuevo modelo basado en el test estadıstico chi-cuadrado y en las matrices deco-ocurrencias.

En la Sec. 6 proponemos utilizar la evolucion de curvas basadas en regiones parala deteccion y el seguimiento de CMEs. Proponemos algoritmos para calcular laspropiedades de los CMEs. Analizamos los resultados que obtenemos utilizandoel modelo de competicion de regiones y el modelo que proponemos.

En la Sec. 7 comparamos los resultados de nuestro metodo de deteccion y segui-miento de CMEs, con el catalogo de CMEs elaborado por el grupo de expertosdel LASCO.

Finalmente, en la Sec. 8 resumimos los resultados de la tesis y vemos posiblesmejoras.

2. PRELIMINARES

2.1. Nociones de procesamiento imagenes

Una imagen se puede definir como una funcion I : Ω ⊆ Rm 7−→ Rn. Donde loselementos de Ω son las coordenadas de la imagen. Las imagenes digitales son funcionesdiscretas I : Ω ⊆ Nm 7−→ Rn que toman valores discretos y se suelen representar enlas computadoras mediante matrices. En general se supone que una imagen digital esuna discretizacion lo suficiente fina de una imagen. Existen varios tipos de imagenesdiferentes, en particular una imagen escalar es una funcion I : Ω ⊆ N2 7−→ N, que leasocia a cada coordenada bidimensional un nivel de gris. En este trabajo usaremossolamente imagenes escalares.

Filtrado Gaussiano de imagenes

Se define un nucleo gaussiano Gt : R2 7−→ R de varianza t como :

Gt(x,y) =1

t√

2πe

x2+y2

2t2 (2.1)

Aplicar un filtro gaussiano Gt a una funcion f : R2 7−→R es realizar la convolucion:

R(x,y) = f ⊗Gt =∫ ∫

f (x− i,y− j)Gt(i, j)did j (2.2)

El efecto de aplicar un filtro gaussiano a una funcion es el de suavizar la funcion.Mientras mayor sea la varianza, mayor suavizado se obtiene. Una de las propiedadesmas importantes que tiene el filtrado gaussiano es que aplicar primero un filtro gaus-siano de varianza

√t1 y luego otro de varianza

√t2 es equivalente a aplicar un filtro

gaussiano de varianza√

t1 + t2. Es decir que se cumple la siguiente relacion :

( f ⊗G√t1)⊗G√t2 = f ⊗G√t1+t2 . (2.3)

Se define la discretizacion de un nucleo gaussiano como una mascara M de n×m

M(i, j) = cei2+ j2

2t2 (2.4)

donde c se elige para que la suma de los coeficientes de M sea uno.Finalmente, aplicar una discretizacion de un nucleo gaussiano M a una funcion

discretizada φ se define como:

R(x,y) = φ⊗M =n

∑i=0

m

∑j=0

φ(x− i,y− j)M(i, j) (2.5)

2. PRELIMINARES 14

2.2. Ecuaciones diferenciales

Una ecuacion diferencial relaciona una funcion con sus derivadas, de tal forma quela funcion en sı misma es la incognita a determinar. Lo cual difiere de una ecuacionalgebraica, como por ejemplo:

x2−2x+1 = 0

cuya solucion es un numero. Una ecuacion diferencial tıpica es:

u′(t) = u(t)

cuya solucion esta dada por la funcion:

u(t) = cet

donde la contante c es usualmente determinada por una condicion adicional. Por ejem-plo si pedimos que u(0) = 1/2 entonces c = 1/2 y u(t) = 1/2et . Siempre la solucion auna ecuacion diferencial es una funcion.

Usualmente las ecuaciones diferenciales se clasifican en ecuaciones diferencia-les en derivadas parciales (PDEs) y ecuaciones diferenciales en derivadas ordinarias(ODEs). Las PDEs involucran derivadas parciales de varias variables, mientras queODEs involucran derivadas con respecto a una sola variable.

Una de las ecuaciones diferenciales que aparecen comunmente es la ecuacion delcalor:

u(~x,0) = u0(~x)∂u∂t = ∆u(~x, t),

(2.6)

siendo ∆u(~x, t) = ∑ni=1

∂uxi

y u0 el estado inicial del sistema. La Ec. 2.6 describe, entreotros, la variacion de temperatura en una region a lo largo del tiempo. La solucionanalıtica esta dada por [Sap01]:

u(~x, t) = G√2t(~x)⊗u0(~x) (2.7)

donde G√2t(~x) es un nucleo gaussiano de varianza√

2t. La relacion entre la ecuacionde calor y la convolucion con nucleos gaussianos es fundamental en el procesamientode imagenes.

Soluciones debiles

Algunas ecuaciones diferenciales pueden ser reescritas de tal forma que no apa-rezcan las derivadas de la funcion que se busca, esta forma de expresar una ecuaciondiferencial se llama formulacion debil.

Se llama solucion debil de una ecuacion diferencial a la funcion que cumple con laformulacion debil. Las soluciones debiles de una ecuacion diferencial no requieren elmismo grado de diferenciabilidad sobre la funcion, lo que da lugar a un conjunto masgrande de soluciones.

Las soluciones debiles de las ecuaciones diferenciales son importantes pues grancantidad de veces las ecuaciones diferenciales no admiten soluciones diferenciables en

2. PRELIMINARES 15

todo su dominio y la unica forma de encontrar una solucion es que cumpla la formula-cion debil.

Un ejemplo tıpico es la ecuacion de onda unidimensional:

∂u∂t

=∂u∂x

. (2.8)

La solucion de la ecuacion debe ser una funcion derivable respecto a las variablesx y t. Sin embargo, si integramos a ambos lados de la ecuacion con respecto a x en unintervalo [a,b], obtenemos:

∂

∂t

∫ b

au dx = u(b)−u(a). (2.9)

Las soluciones de la ecuacion deben ser derivables respecto a t. La formulacionexpuesta es conocida como formulacion integral a la ecuacion diferencial.

2.3. Calculo de variaciones

Un funcional es una funcion E : RΩ 7−→ R que dada una funcion como argumentodevuelve un numero Real. El calculo de variaciones es una herramienta matematica quenos permite encontrar puntos extremos de funcionales [Tsc02]. Por ejemplo, encontrarI : Ω 7−→ R que minimiza E(I) :

mınI:Ω 7−→R

E(I) =∫

Ω

F(~x, I(~x),∇I(~x))dΩ (2.10)

siendo F una funcion que toma valores reales, no es un problema sencillo.Una de las formas mas comunes de encontrar el maximo o el mınimo de una fun-

cion suave es verificar cuando la derivada es cero. Las ecuaciones de Euler-Lagrange,uno de los resultados fundamentales del calculo de variaciones, usan la misma idea pe-ro aplicada a funcionales. Las ecuaciones de Euler-Lagrange surgen de evaluar comovarıa el funcional cuando la funcion de entrada varıa, una condicion necesaria que debeverificar I para alcanzar el mınimo E(I) es:

∂E∂I

=∂F∂I−

N

∑i=1

∂

∂xi

∂F∂Ixi

= 0 (2.11)

Para evitar la resolucion analıtica de la Ec. 2.11 se utiliza un metodo iterativo,analogo al metodo de descenso por gradiente. La Ec. 2.11 se puede interpretar como elgradiente del funcional E(I). Empezando con una aproximacion inicial I0 y moviendo-se en la direccion opuesta al gradiente se obtiene un mınimo local Imin de E(I):

It=0 = I0∂I∂t =− ∂E

∂I =−(

∂F∂I −∑

Ni=1

∂

∂xi∂F∂Ixi

) (2.12)

Notar que la evolucion de la PDE ha sido parametrizada por una variable de tiempoartificial t, la cual describe la evolucion de la funcion I que minimiza E(I). Cuando I

2. PRELIMINARES 16

es un mınimo de E(I) entonces ∂I∂t = 0. En general este metodo converge a mınimos

locales, por lo que la funcion inicial I0 debe ser elegida cuidadosamente.De esta forma, las ecuaciones de Euler-Lagrange vinculan la resolucion de PDEs

con la minimizacion de funcionales mediante descenso por gradiente.Un funcional que es de interes minimizar es:

E(I) =∫

Ω

‖∇I(~x)‖22dΩ, (2.13)

el mınimo del funcional se alcanza en la funcion cuyo ‖∇I(~x)‖22 es cero en todo Ω,

las funciones que cumplen esta condicion son las funciones constantes. Usando lasecuaciones de Euler-Lagrange se obtiene el siguiente descenso por gradiente [Tsc02]:

It=0 = I0∂I∂t = ∆I

(2.14)

siendo I0 una aproximacion inicial.La Ec. 2.14 es interesante pues relaciona la Ec. 2.13 con la ecuacion del calor Ec.

2.6 y por ende con la convolucion con nucleos gaussianos.

3. EVOLUCION DE CURVAS

Desde que se propuso el modelo snake [KWT88], la evolucion de curvas ha recibi-do mucha atencion y se han encontrado multiples aplicaciones. En esta seccion revisa-mos las ideas basicas de evolucion de curvas y en especial la evolucion por medio deconjuntos de nivel.

La representacion parametrica de una curva C, en dos dimensiones, esta dada porla funcion C : [0,1] 7−→ R2. La evolucion de curvas consiste en analizar y calcular elmovimiento de una curva C0 bajo un campo de velocidad F : R 7−→ R2, el cual puededepender de la posicion, el tiempo, y la geometrıa de la curva (curvatura y normal).En el procesamiento de imagenes, la eleccion del campo de velocidad F depende dela aplicacion, diferentes campos de velocidad se han propuesto para segmentacion deimagenes y para seguimiento en secuencias de vıdeos, entre otros.

Para analizar la evolucion temporal de la curva se agrega la variable temporal t.Luego la evolucion de la curva puede expresarse como:

C(s,0) = C0(s) s ∈ [0,1]∂C∂t (s, t) = F(s, t) s ∈ [0,1], t ∈ (0,∞)

, (3.1)

donde, una curva inicial C0 es evolucionada usando una funcion F . Generalmente esde interes encontrar la curva tal que ∂C

∂t (s, t)≈ 0.Una formulacion al problema de evolucion de curvas, llamada conjuntos de nivel,

fue propuesta en [OS88]. En esta formulacion, la curva se representa en forma implıci-ta, como el conjunto de nivel cero de una funcion suave φ : R2 7−→ R:

φ(~x) < 0, ~x ∈Ω

φ(~x) > 0, ~x /∈Ω

φ(~x) = 0, ~x ∈C, (3.2)

siendo Ω la region que se encuentra encerrada por la curva C. La representacion de lacurva C mediante la funcion φ permite distinguir facilmente el interior de C (φ(~x) <0), del exterior C (φ(~x) > 0), como se ve en la Fig. 3.1(a). La Fig. 3.1(b) muestra larepresentacion de la curva C = (x,y)|x2 + y2 = 1 mediante una posible eleccion defuncion φ.

La funcion φ se hace evolucionar de acuerdo a un campo de velocidad W : R2 7−→R2, el cual se debe definir sobre todo el dominio a diferencia del campo de velocidadF que solo se define sobre la curva. Para analizar la evolucion temporal de la funcion φ

se agrega la variable temporal t. Luego la evolucion de la funcion φ puede expresarse

3. EVOLUCION DE CURVAS 18

-

6

?

x

y

φ < 0interior

φ > 0exterior

∂Ω

φ = x2 + y2−1 = 0

(a) Curva C = (x,y)|x2 + y2 = 1 . (b) Funcion x2 +y2−1 en celeste y el planoz = 0, la interseccion de ambos son el con-junto de nivel cero de la funcion.

Fig. 3.1: Representacion implıcita de la curva x2 + y2 = 1 mediante la funcion de conjuntos denivel φ = x2 + y2−1.

como: φ(~x,0) = φ0∂φ

∂t +W ·∇φ = 0(3.3)

siendo φ0 una funcion inicial que es evolucionada usando una funcion W . Las formulasen (3.3) son conocidas como las ecuaciones de movimiento de conjuntos de nivel.

El exito de la tecnica de conjuntos de nivel, como se explica en [OF03], radica enque representa las curvas que se desea evolucionar en forma implıcita, lo que permiteevitar problemas de inestabilidad y manejar el cambio de topologıa de las curvas enforma natural.

Cuando el campo W se define como W = WN~N +WT~T , siendo ~N el vector normalsaliente de la curva C y siendo ~T un vector tangente a C, la Ec. 3.3 es equivalente a:

∂φ

∂t+WN~N ·∇φ = 0 (3.4)

pues ~T ·∇φ = 0, como se vera en la siguiente seccion. Ademas dado que:

~N ·∇φ =∇φ

|∇φ|·∇φ =

|∇φ|2

|∇φ|= |∇φ| (3.5)

se obtiene que la Ec. 3.3 es equivalente a:φ(~x,0) = φ0∂φ

∂t +WN |∇φ|= 0(3.6)

La conexion expuesta entre la Ec. 3.3 y la Ec. 3.6 expresa que para analizar laevolucion de una curva C de acuerdo a cualquier campo de velocidad W =WN~N+WT~Tbasta con analizar como evoluciona la curva C en la direccion de la normal bajo elcampo de velocidad WN : R2 7−→ R.


3.1. Propiedades de las funciones implıcitas

Usando φ como la representacion implıcita de C se pueden expresar caracterısticasgeometricas relevantes de C [OF03]. El gradiente de la funcion φ es ∇φ =

(∂φ

∂x , ∂φ

∂y

),

el cual es perpendicular a los iso–contornos de φ. Por ende, si ~x0 es un punto del iso–contorno cero de la funcion φ, es decir un punto de la curva C, entonces ∇φ(~x0) apuntaen la misma direccion a la normal de la curva C. Por ende,

~N =∇φ

|∇φ|(3.7)

es la normal unitaria para puntos en la curva C. Por otro lado, tambien se puede expresarla curvatura κ de C en funcion de φ mediante

κ = div

(∇φ

|∇φ|

)(3.8)

donde div( f ) es la divergencia de la funcion f y se define como : div( f ) = ∑ni=1

∂ f∂xi

.Ademas, utilizando la funcion φ se puede expresar la integral de una funcion sobre

la region Ω encerrada por la curva C :∫Ω

f (~x) d~x =∫

f (~x)H(φ(~x)) d~x (3.9)

siendo H(x) la funcion de Heaviside definida como:

H(z) =

0 z≥ 01 z < 0

Tambien se puede expresar la integral sobre la curva C :∫C

f (~x) d~x =∫

f (~x)δ(φ(~x))|∇φ(~x)| d~x (3.10)

siendo δ(x) la funcion delta de Dirac, definida como δ(x) = H ′(x). Pues δ(φ(~x))|∇φ(~x)|es diferente a cero unicamente en los puntos de C.

3.2. Funciones de distancias con signo

Hasta el momento, poco se ha dicho sobre la funcion de conjuntos de nivel φ masque lo expresado en la Ec. 3.2. Existen gran cantidad de funciones que cumplen dichasrestricciones. Sin embargo, no todas se comportan numericamente de la misma forma.En especial, las funciones de distancias con signo son un subconjunto de las posibleselecciones de φ que deben cumplir una condicion adicional |∇φ(~x)|= 1.

Una funcion distancia con signo es una funcion implıcita, que se define como:

φ(~x) =

−mın~y∈C |~x−~y| ~x ∈Ω

0 ~x ∈Cmın~y∈C |~x−~y| ~x /∈Ω

(3.11)


Fig. 3.2: Representacion implıcita de la curva x2 + y2 = 1 mediante la funcion de conjuntos denivel φ =

√x2 + y2− 1 (en azul). La interseccion de la funcion con el plano z = 0, en

celeste, es el conjunto de nivel cero.

En la Fig. 3.2 se puede ver la representacion implıcita de la curva C = (x,y)|x2 +y2 = 1 mediante una funcion de distancia con signo.

Dado que la funcion de distancia con signo es una distancia Euclıdea se cumple que|∇φ(~x)|= 1. Por ende se simplifican las ecuaciones removiendose las normalizaciones.La Ec. 3.7 se simplifica a

~N = ∇φ (3.12)

la Ec. 3.8 se simplifica aκ = ∆φ (3.13)

por ultimo, la Ec. 3.10 se simplifica a∫C

f (~x) d~x =∫

f (~x)δ(φ(~x)) d~x (3.14)

Dadas las simplificaciones en las formulas, es conveniente inicializar φ0 en la Ec.3.3 como una funcion de distancia con signo. Sin embargo, a medida que evoluciona lafuncion mediante la Ec. 3.3 la propiedad de que φ sea una funcion distancia con signo,en general, no se mantiene. Para resolver este problema se debe reinicializar (encontraruna nueva funcion φ que represente la misma curva) periodicamente la funcion φ auna funcion de distancia con signo. Diferentes tecnicas de reinicializacion se puedenencontrar en [OF03].


(a) t = 0 (b) t = 10 (c) t = 20

(d) t = 30 (e) t = 40 (f) t = 50

Fig. 3.3: Evolucion de curva en direccion de la normal.

3.3. Evolucion por normal

Un caso especial de evolucion es cuando la evolucion es proporcional a la normal,es decir:

∂φ

∂t+a|∇φ|= 0 (3.15)

siendo a una constante. Cuando a > 0 la curva se mueve en la direccion de la normal,mientras que cuando a < 0 la curva se mueve en direccion contraria a la normal. Cuan-do a = 0 la ecuacion se reduce a ∂φ

∂t = 0, donde φ es contante todo el tiempo. La Fig.3.3 muestra la evolucion de una curva moviendose en direccion de la normal.

Cuando φ0 es una funcion distancia con signo, la Ec. 3.15 se reduce a

∂φ

∂t=−a (3.16)

y los valores de φ se incrementan o se reducen dependiendo del signo de a. Ademas secumple que :

φ(~x, t) =−at + f (~x) (3.17)

siendo f una funcion que depende solamente de ~x. Ademas, como vale que φ(~x,0) =φ0(~x), entonces:

φ(~x, t) =−at +φ0(~x) (3.18)

Por ende :∂φ

∂xi(~x, t) =

∂φ0

∂xi(~x) (3.19)


(a) t = 0 (b) t = 10 (c) t = 20

(d) t = 30 (e) t = 40 (f) t = 50

Fig. 3.4: Evolucion de curva por curvatura.

o lo que es equivalente ∇φ(~x, t) = ∇φ(~x,0), para todo t. Dado que φ0 es una funcionde distancia con signo, se tiene que vale que φ(~x, t) es una funcion distancia con signopara todo t.

3.4. Evolucion por curvatura

Otro caso de interes es cuando la curva se hace evolucionar mediante la curvatura,es decir:

∂φ

∂t+bκ|∇φ(~x)|= 0 (3.20)

donde b es una constante.Toda curva cerrada simple que evoluciona por su curvatura colapsa suavemente en

un punto sin cruzarse sobre si misma. La Fig. 3.4 muestra la evolucion de una curvamediante su curvatura.

Cuando la funcion φ es una funcion de distancia con signo la Ec. 3.20 se convierteen la ecuacion del calor (Ec. 2.6) :

∂φ

∂t=−b∆φ (3.21)

pues bκ|∇φ| y b∆φ son identicos y se pueden usar en forma intercambiable. Por endese puede hacer uso de la conexion entre la ecuacion del calor y la convolucion connucleos gaussianos expuesta en la Sec. 2.2.


3.5. Metodos basados en la resolucion de las PDEs

Los metodos basados en la resolucion de las PDEs utilizan diferentes formulas paraaproximar numericamente las derivadas de las funciones. Dada una funcion f : Rn 7−→R se define la diferencia forward como:

∂ f∂xi≈ D+xi f =

f (x1, . . . ,xi +∆x, . . . ,xn)− f (x1, . . . ,xi, . . . ,xn)∆x

, (3.22)

la diferencia backward como:

∂ f∂xi≈ D−xi f =

f (x1, . . . ,xi, . . . ,xn)− f (x1, . . . ,xi−∆x, . . . ,xn)∆x

, (3.23)

y la diferencia central como:

∂ f∂xi≈ D0x f =

f (x1, . . . ,xi−∆x, . . . ,xn)− f (x1, . . . ,xi +∆x, . . . ,xn)2∆x

, (3.24)

todas son aproximaciones numericas de primer orden a ∂ f∂xi

.En [OF03] existen varios metodos para resolver Ec. 3.3. Un problema que se debe

tener en cuenta es que el metodo numerico debe poder encontrar soluciones debiles queconverjan a la solucion viscosa correcta [OF03, Set99]. En particular cuando se tieneevolucion por curvatura y evolucion por normal y φ0 es una funcion de distancia consigno, se puede aproximar el laplaciano mediante diferencias centradas y ∂φ

∂t se puedeaproximar con diferencias forward.

Para analizar la evolucion de la curva se deben calcular los valores de φ(~x, t) paradiferentes tn, siendo tn+1 = tn + ∆t, φ(tn) = φn y n el numero de iteracion. Utilizandodiferencias forward para aproximar ∂φ

∂t se pueden encontrar los valores φn+1 para cadapunto (i, j) de la grilla, usando los valores de φn. Luego la Ec. 3.6 (con |∇φ|= 1, puesφ es una funcion de distancia con signo) se puede discretizar como:

φn+1−φn

∆t︸︷︷︸D+t φ

+W nN = 0 (3.25)

donde WN es un campo que solo tiene evolucion por curvatura y normal WN = a−bκ.Despejando de la Ec. 3.25 se puede calcular los nuevos valores de φ:

φn+1 = φ

n−∆tW tN . (3.26)

Luego de calcular los valores de φn+1, puede suceder que los mismos no sean unafuncion de distancia con signo y sea necesario reinicializar la funcion.

Un problema que sufren los metodos que resuelven las PDEs sobre todo el dominioes su lentitud. La misma se debe a que deben calcular el valor de la funcion φ sobretodo el dominio, cuando los unicos valores que definen la curva son los que se encuen-tran cerca del conjunto de nivel cero. Por este motivo, se ha propuesto el metodo debanda angosta [AS95] donde solamente se actualizan los puntos cercanos a la curva.


Fig. 3.5: Funcion de distancia con signo en una banda angosta cerca del conjunto de nivel cero.

Esta banda es creada en forma dinamica basandose en la curva actual, incluyendo lospuntos que se encuentran a una distancia menor a una predefinida. Cuando la curva seencuentra muy cercana a los bordes de la banda, la banda se vuelve a crear. Los puntosque se encuentran a distancia mayor a la distancia prefijada se asume que tienen el va-lor de la distancia. En la Fig. 3.5 se puede ver una funcion de distancia con signo, en lacual solo los puntos cercanos al conjunto de nivel cero tienen el valor de distancia a lacurva. Los puntos alejados al conjunto de nivel cero tienen un valor fijo.

Si bien la tecnica de banda angosta mejora considerablemente los tiempos de ejecu-cion, los mismos no son aceptables para procesamiento en tiempo real. En la siguienteseccion revisamos un metodo, basado en conjuntos de nivel que permite procesamientoen tiempo real.

3.6. Metodos rapidos sin resolver PDEs

En [SK05] se analiza la evolucion de curvas representadas implıcitamente, median-te conjuntos de nivel, en rejillas regulares y se propone un metodo rapido. El metodopropuesto se basa en la utilizacion de dos listas linkeadas Lin y Lout para representar yevolucionar la curva que se desea seguir y de esta forma no tener que resolver el PDEexplıcitamente.

El metodo utiliza las siguientes estructuras de datos:

Una matriz para representar la funcion φ.


Dos listas linkeadas Lin y Lout de pixeles vecinos a C.

dondeLout = ~x| φ(~x) > 0,∃~y ∈ N(~x) tal que φ(~y) < 0Lin = ~x| φ(~x) < 0,∃~y ∈ N(~x) tal que φ(~y) > 0N(~x) =

~y ∈ Z2|‖~x−~y‖1 = 1

φ(~x) =

3 si~x /∈Ω,~x /∈ Lout

1 si~x ∈ Lout

−1 si~x ∈ Lin

−3 si~x ∈Ω,~x /∈ Lin

Los valores −3,−1,1,3 se toman para que φ sea una funcion de distancia consigno dentro de una banda angosta de ancho uno. En la Fig. 3.6 se puede ver una curvaque se desea representar, la representacion usando φ y las listas Lin y Lout . La curva serepresenta implıcitamente como el conjunto de nivel cero de la funcion φ, marcados ennegrita.

El metodo se basa en que la evolucion de una curva se puede realizar intercam-biando puntos entre las listas Lin y Lout . Para evolucionar la curva hacia adentro en unpunto de Lin es necesario intercambiar el punto con la lista Lout , utilizando la funcionContraerContorno, como se puede ver en el Alg. 1. Para evolucionar la curva haciaafuera en un punto de Lout es necesario intercambiar el punto con la lista Lin, utilizandola funcion ExpandirContorno, como se puede ver en el Alg. 2.

Algoritmo 1 ContraerContorno1: function CONTRAERCONTORNO(~x)2: Eliminar~x de Lin3: Agregar~x a Lout4: φ(~x)← 15: for all~y ∈ N(~x) do6: if φ(~y) =−3 then7: Agregar~y a Lin8: φ(~y)←−19: end if

10: end for11: end function

El metodo analiza en particular campos de velocidad WN = Fsuavizado + Fa juste quetienen un termino de evolucion por curvatura Fsuavizado = µκ y un termino Fa juste deevolucion que no involucra derivadas. El metodo propone separar la evolucion de lacurva, en dos pasos que se repiten hasta encontrar la solucion.

3.6.1. Primer Paso

En el primer paso se hace evolucionar la curva utilizando los valores de Fa juste,contrayendo la curva cuando Fa juste(~x) < 0 y expandiendo la curva cuando Fa juste(~x) >0. Para contraer la curva se aplica la funcion ContraerContorno a cada punto de Lin,


Algoritmo 2 ExpandirContorno1: function EXPANDIRCONTORNO(~x)2: Eliminar~x de Lout3: Agregar~x a Lin4: φ(~x)←−15: for all~y ∈ N(~x) do6: if φ(~y) = 3 then7: Agregar~y a Lout8: φ(~y)← 19: end if

10: end for11: end function

como se puede ver el Alg. 3. De forma similar, para expandir la curva se aplica lafuncion ExpandirContorno a cada punto de Lout , como se puede ver el Alg. 4.

Algoritmo 3 ContraerContornoAjuste1: procedure CONTRAERCONTORNOAJUSTE2: for all~x ∈ Lin do3: if Fa juste(~x) < 0 then4: ContraerContorno(~x)5: end if6: end for7: end procedure

Algoritmo 4 ExpandirContornoAjuste1: procedure EXPANDIRCONTORNOAJUSTE2: for all~x ∈ Lout do3: if Fa juste(~x) > 0 then4: ExpandirContorno(~x)5: end if6: end for7: end procedure

En la Fig. 3.8 se muestra el resultado de evolucionar la curva de la Fig. 3.6, me-diante el Alg. 4, utilizando los valores de Fa juste de la Fig. 3.7(b). Dado que los valoresde Fa juste de la Fig. 3.7(b) son todos positivos, y que se esta evolucionando la curva dela Fig. 3.6 en direccion de la normal (ver Sec. 3.3), la curva resultante en la Fig. 3.8se expandio en todas direcciones. De forma similar, la Fig. 3.9 muestra el resultado deevolucionar la curva de la Fig. 3.6, mediante el Alg. 3, utilizando los valores de Fa justede la Fig. 3.7(a).

Como se puede ver en las Fig. 3.8 y Fig. 3.9, los Alg. 3 y Alg. 4 no mantienenla representacion de la curva, pues luego de su ejecucion sobre la curva de la Fig. 3.6


Lin

Lin

Lin

Lin

Lout

Lout

Lout

Lout

Lout Lout

LoutLout

(a) Representacion usando listas.

−3−1

−1

−1

−1

1

1

1

1

1 1

11

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3 3 3

3 3

3 3 3

3 3

(b) Representacion usando φ.

Fig. 3.6: Curva (marcada en negrito) representada mediante listas Lin, Lout y φ.

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

(a) Fa juste con velocidad entrante.

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

+1

(b) Fa juste con velocidad saliente.

Fig. 3.7: Diferentes Fa juste para evolucionar la curva de la Fig. 3.6.

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

(a) Representacion del contorno usan-do listas luego de evolucionar, los pun-tos redundantes en rojo.

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−3−1

−1

−1

−1

3

3

3

3

3

3 3

3

3

3

3

3

3

3

3

3

3

33

3

3

3

3

3

(b) Representacion del contorno usan-do φ luego de evolucionar, los puntosredundantes en rojo.

Fig. 3.8: Evolucion del contorno mediante los valores de Fa juste de la Fig. 3.7(b), utilizando elAlg. 4.


LinLout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout Lout

LoutLout

(a) Representacion del contorno usan-do listas luego de evolucionar, los pun-tos redundantes en rojo.

−11

1

1

1

1

1

1

1

1 1

11

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3 3 3

3 3

3 3 3

3 3

(b) Representacion del contorno usan-do φ luego de evolucionar, los puntosredundantes en rojo.

Fig. 3.9: Evolucion del contorno mediante los valores de Fa juste de la Fig. 3.7(a), utilizando elAlg. 3.

quedaron valores que no respetan la definicion de Lin, Lout ni de la φ. Los puntos queno respetan las definiciones fueron marcados en rojo en las Fig. 3.9 y Fig. 3.8. Paracorregir los valores de estos puntos, que llamaremos puntos redundantes, es necesarioejecutar los Alg. 5 y Alg. 6.

Algoritmo 5 EliminarPuntosRedundantesEnLin1: procedure ELIMINARPUNTOSREDUNDANTESENLIN2: for all~x ∈ Lin do3: if ∀~y ∈ N(~x) =⇒ φ(~y) < 0 then4: Eliminar~x de Lin5: φ(~x)←−36: end if7: end for8: end procedure

En la Fig. 3.10, se muestra el resultado de eliminar los puntos redundantes de larepresentacion de la curva de la Fig. 3.8, mediante el Alg. 5. De forma similar, en laFig. 3.11, se muestra el resultado de eliminar los puntos redundantes de la curva de laFig. 3.9, mediante el Alg. 6.

Finalmente, el primer paso se puede resumir en el Alg. 7. El parametro Na controlala cantidad de iteraciones.

3.6.2. Segundo Paso

En el segundo paso, se intenta suavizar la curva imitando el comportamiento quese obtiene por el termino Fsuavizado = µκ. El metodo utiliza la relacion entre la ecuaciondel calor y la convolucion de funciones con nucleos gaussianos Ec. 2.7. Se convolu-ciona la funcion φ con un filtro gaussiano que controla el suavizado, a diferencia de lo


Algoritmo 6 EliminarPuntosRedundantesEnLout1: function ELIMINARPUNTOSREDUNDANTESENLOUT2: for all~x ∈ Lout do3: if ∀~y ∈ N(~x) =⇒ φ(~y) > 0 then4: Eliminar~x de Lout5: φ(~x)← 36: end if7: end for8: end function

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lin

(a) Representacion del contorno usan-do listas luego de evolucionar y elimi-nar puntos redundantes.

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−3 −3 −3

−3

−3

−3

3

3

3

3

3

3 3

3

3

3

3

3

3

3

3

3

3

33

3

3

3

3

3

(b) Representacion del contorno usan-do φ luego de evolucionar y eliminarpuntos redundantes.

Fig. 3.10: Resultado de eliminar los puntos redundantes de la de la representacion de la curva dela Fig. 3.8, mediante el Alg. 5.

LinLout

Lout

Lout

Lout

(a) Representacion del contorno usan-do listas luego de evolucionar y elimi-nar puntos redundantes.

−11

1

1

1

3

3

3

3

3 3

33

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3 3 3

3 3

3 3 3

3 3

(b) Representacion del contorno usan-do φ luego de evolucionar y eliminarpuntos redundantes.

Fig. 3.11: Resultado de eliminar los puntos redundantes de la curva de la Fig. 3.9, mediante elAlg. 6.


Algoritmo 7 Primer Paso1: for i← 1 to Na do . Evolucionar contorno usando termino de ajuste2: Calcular Fa juste para cada punto en Lin y Lout3: ExpandirContornoA juste4: EliminarPuntosRedundantesEnLin5: ContraerContornoA juste6: EliminarPuntosRedundantesEnLout7: end for

propuesto en los metodos anteriores donde el suavizado se efectuaba implıcitamente alevolucionar los PDEs.

Para suavizar la curva se utilizan los valores de G⊗ φ, siendo G un nucleo gaus-siano, contrayendo la curva cuando G⊗φ(~x) < 0 y expandiendo la curva cuando G⊗φ(~x) > 0. Al igual que en el primer paso, se aplica ContraerContorno a cada punto dela curva, como puede verse en el Alg. 9 y ExpandirContorno a cada punto de la curva,como puede verse en el Alg. 8.

Algoritmo 8 ExpandirContornoSuavizado1: procedure EXPANDIRCONTORNOSUAVIZADO2: for all~x ∈ Lout do3: if G⊗φ(~x) < 0 then4: ExpandirContorno(~x)5: end if6: end for7: end procedure

Algoritmo 9 ContraerContornoSuavizado1: procedure CONTRAERCONTORNOSUAVIZADO2: for all~x ∈ Lin do3: if G⊗φ(~x) > 0 then4: ContraerContorno(~x)5: end if6: end for7: end procedure

Al igual que sucede en el primer paso con las funciones ContraerContornoAjuste yExpandirContornoAjuste, las funciones ContraerContornoSuavizado y ExpandirCon-tornoSuavizado no mantienen la representacion de las curvas, por lo que es necesarioejecutar los Alg. 5 y Alg. 6 para eliminar los puntos redundantes. El segundo paso sepuede resumir en el Alg. 10, el parametro Ng controla la cantidad de iteraciones.

En la Fig. 3.12 se puede observar el resultado de evolucionar la curva de la Fig. 3.8mediante el Alg. 10. El parametro Ng controla la cantidad de iteraciones.


Algoritmo 10 Segundo Paso1: for i← 1 to Ng do . Evolucionar contorno usando termino de suavizado2: ExpandirContornoSuavizado3: EliminarPuntosRedundantesEnLin4: ContraerContornoSuavizado5: EliminarPuntosRedundantesEnLout6: end for

Lin Lin Lin

Lin Lin Lin

Lin

Lin

Lin

Lin

Lin

Lin

Lout Lout Lout

Lout Lout Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

Lout

(a) Representacion del contorno usan-do listas luego de evolucionar.

−3

−3

−3

−3

−3

−3

−3

−3

−3

−1 −1 −1

−1 −1 −1

−1

−1

−1

−1

−1

−1

1 1 1

1 1 1

1

1

1

1

1

1

1

1

1

1

3

3

3 3

3 33

3

33 3

3

33 3

3

(b) Representacion del contorno usan-do φ luego de evolucionar.

Fig. 3.12: Evolucion de la curva de la Fig. 3.8 mediante el Alg. 10, con una iteracion.

3.6.3. Algoritmo Completo

El metodo propuesto en [SK05] se puede ver en el Alg. 11, en el cual se haceevolucionar la curva hasta que no haya cambios en la misma.

Mayores tamanos de mascaras generan contornos mas suaves y regiones con menoshuecos. Los parametros Na y Ng controlan la cantidad de iteraciones de cada ciclo,y por ende el peso que tiene cada ciclo, mayores tamanos de mascaras pueden serreemplazados incrementando el valor del parametro Ng.

Experimentalmente, es aconsejable que los parametros Na y Ng se encuentren entre3 y 10. Si los parametros son muy pequenos la curva tardara mucho en ajustarse alcontorno que se desea segmentar. Si son muy grandes, mas de 10, el metodo se vuelveinestable.

3.7. Metodo rapido basado en representacion regiones y contornos

En el metodo propuesto en [SK05] tanto ExpandirContorno como ContraerCon-torno, no mantienen la representacion de la curva por lo que luego de ser invocadasrepetidas veces, se debe invocar a las funciones EliminarPuntosRedundantesEnLiny EliminarPuntosRedundantesEnLout para restablecer la representacion de la curva.Planteados de esta forma se acoplan los algoritmos que representan la region y la cur-va, con los algoritmos que hacen evolucionar la curva, pues es necesario identificar


Algoritmo 11 Evolucion rapida de Conjuntos de Nivel1: Inicializar φ, Lin, Lout2: while la solucion no es estacionaria do3: for i← 1 to Na do . Evolucionar contorno usando termino de ajuste4: Calcular Fa juste para cada punto en Lin y Lout5: ExpandirContornoA juste6: EliminarPuntosRedundantesEnLin7: ContraerContornoA juste8: EliminarPuntosRedundantesEnLout9: En caso de que la solucion es estacionaria suavizar el contorno y terminar.

10: end for11: for i← 1 to Ng do . Evolucionar contorno usando termino de suavizado12: ExpandirContornoSuavizado13: EliminarPuntosRedundantesEnLin14: ContraerContornoSuavizado15: EliminarPuntosRedundantesEnLout16: end for17: end while

cuando se recorrieron todos los puntos de la curva para ejecutar las funciones Elimi-narPuntosRedundantesEnLin y EliminarPuntosRedundantesEnLout.

En este trabajo se propone una modificacion a las funciones ExpandirContornoy ContraerContorno que mantiene la representacion de la curva y por ende no sonnecesarias las llamadas a EliminarPuntosRedundantesEnLin ni a EliminarPuntosRe-dundantesEnLout. Utilizando estas funciones como base, logramos crear una nuevaestructura de datos que permite representar una region y obtener su contorno de ma-nera eficiente. Esta nueva representacion de una region nos permite separar el com-portamiento relacionado a evolucionar la curva mediante WN y el comportamiento quemantiene la representacion de la curva.

La modificacion propuesta a las funciones ExpandirContorno y ContraerContornose basa en la observacion de que los puntos redundantes que se eliminan en las llama-das a EliminarPuntosRedundantesEnLin y a EliminarPuntosRedundantesEnLout pue-den ser identificados y eliminados directamente en las funciones ExpandirContorno yContraerContorno. Los puntos que se deben verificar, si se deben o no eliminar, sonlos vecinos del punto que se esta contrayendo o expandiendo.

Los puntos de Lin que son redundantes luego de expandir el contorno, utilizandoExpandirContorno, son aquellos cuyos vecinos son interiores. Basta con verificar estacondicion en los vecinos del punto que se esta expandiendo, para poder localizar yeliminar los puntos redundantes. En el Alg. 12 se puede ver la version modificada.

En forma similar, los puntos de Lout que son redundantes luego de contraer el con-torno, utilizando ContraerContorno, son aquellos cuyos vecinos son exteriores. Bastacon verificar esta condicion en los vecinos del punto que se esta contrayendo, para po-der localizar y eliminar los puntos redundantes. En el Alg. 13 se puede ver la versionmodificada.


Algoritmo 12 ExpandirContornoModificado1: function EXPANDIRCONTORNOMODIFICADO(~x)2: Eliminar~x de Lout3: Agregar~x a Lin4: φ(~x)←−15: for all~y ∈ N(~x) do6: if φ(~y) = 3 then7: Agregar~y a Lout8: φ(~y)← 19: end if

10: if φ(~y) =−1 then11: EliminarPuntosRedundantesDeLinCercaDe(~y)12: end if13: end for14: end function15: function ELIMINARPUNTOSREDUNDANTESDELINCERCADE(~x)16: if ∀~y ∈ N(~x) =⇒ φ(~y) < 0 then17: Eliminar~x de Lin18: φ(~x)←−319: end if20: end function

Algoritmo 13 ContraerContornoModificado1: function CONTRAERCONTORNOMODIFICADO(~x)2: Eliminar~x de Lin3: Agregar~x a Lout4: φ(~x)← 15: for all~y ∈ N(~x) do6: if φ(~y) =−3 then7: Agregar~y a Lin8: φ(~y)←−19: end if

10: if φ(~y) = 1 then11: EliminarPuntosRedundantesDeLoutCercaDe(~y)12: end if13: end for14: end function15: function ELIMINARPUNTOSREDUNDANTESDELOUTCERCADE(~x)16: if ∀~y ∈ N(~x) =⇒ φ(~y) > 0 then17: Eliminar~x de Lout18: φ(~x)← 319: end if20: end function


3.7.1. Representacion de la region

Un algoritmo necesario es AgregarPunto, que permite agregar un punto a una re-gion. En caso de que el punto ya sea parte de la region (punto interior), AgregarPuntono debe modificar la region. Si el punto se encuentra en el borde exterior, entonces sedebe utilizar ExpandirContorno para agregar el punto a la region. En caso contrario,el punto se encuentra ”alejado” de la region, entonces alcanza con marcar el punto co-mo borde interior y agregar los vecinos a la lista de borde exterior, si hiciera falta. Elalgoritmo se puede ver en Alg. 14.

Algoritmo 14 AgregarPunto1: function AGREGARPUNTO(~x)2: if φ(~x) < 0 then3: return4: end if5: if φ(~x) = 1 then6: ExpandirContornoModi f icado(~x)7: else8: AgregarPuntoAle jado(~x)9: end if

10: end function11: function AGREGARPUNTOALEJADO(~x)12: Agregar~x a Lin13: φ(~x)←−114: for all~y ∈ N(~x) do15: if φ(~y) = 3 then16: Agregar~y a Lout17: φ(~y)← 118: end if19: end for20: end function

Otro algoritmo necesario es EliminarPunto, que permite eliminar un punto de unaregion. En caso de que el punto no sea parte de la region (punto exterior), EliminarPun-to no debe modificar la region. Si el punto se encuentra en el borde interior, entonces sedebe utilizar ContraerContorno para eliminar el punto a la region. En caso contrario,el punto se encuentra muy dentro de la region, entonces alcanza con marcar el puntocomo borde exterior y agregar los vecinos a la lista de borde interior, si hiciera falta. Elalgoritmo se puede ver en Alg. 15.

3.7.2. Evolucion de la curva

El algoritmo para evolucionar la curva utilizando la representacion basada en re-giones, es casi identico al Alg. 11 excepto que no se llama ni a la funcion Eliminar-PuntosRedundantesEnLin ni a la funcion EliminarPuntosRedundantesEnLout, pues seutilizan las funciones AgregarPunto y EliminarPunto. Se puede ver en Alg. 16.


Algoritmo 15 EliminarPunto1: function ELIMINARPUNTO(~x)2: if φ(~x) > 0 then3: return4: end if5: if φ(~x) =−1 then6: ContraerContornoModi f icado(~x)7: else8: EliminarPuntoAle jado(~x)9: end if

10: end function11: function ELIMINARPUNTOALEJADO(~x)12: Agregar~x a Lout13: φ(~x)← 114: for all~y ∈ N(~x) do15: if φ(~y) =−3 then16: Agregar~y a Lin17: φ(~y)←−118: end if19: end for20: end function

3.8. Resumen

En esta seccion revisamos los algoritmos de evolucion de curvas basados en elenfoque de conjuntos de nivel. Basados en [SK05], presentamos nuevos algoritmos quepermiten representar una region y obtener su contorno de manera eficiente. Utilizandoestos alogritmos planteamos algoritmos de evolucion de curvas.


Algoritmo 16 Evolucion rapida de Conjuntos de Nivel utilizando la region1: Inicializar φ, Lin, Lout2: while la solucion no es estacionaria do3: for i← 1 to Na do . Evolucionar contorno usando termino de ajuste4: Calcular Fa juste para cada punto en Lin y Lout5: for all~x ∈ Lout do6: if Fa juste(~x) > 0 then7: AgregarPunto(~x)8: end if9: end for

10: for all~x ∈ Lin do11: if Fa juste(~x) < 0 then12: ElminarPunto(~x)13: end if14: end for15: En caso de que la solucion es estacionaria suavizar el contorno y terminar.16: end for17: for i← 1 to Ng do . Evolucionar contorno usando termino de suavizado18: for all~x ∈ Lout do19: if G⊗φ(~x) < 0 then20: AgregarPunto(~x)21: end if22: end for23: for all~x ∈ Lin do24: if G⊗φ(~x) > 0 then25: EliminarPunto(~x)26: end if27: end for28: end for29: end while

4. SEGMENTACION DE IMAGENES POR EVOLUCION DECURVAS

Los modelos propuestos en la literatura que usan conjuntos de nivel para segmentarimagenes se pueden clasificar en dos: los modelos basados en bordes [CKS95] y losmodelos basados en regiones [CV01].

En los modelos basados en bordes, se plantea un funcional en el que solo se utilizainformacion cercana al contorno a segmentar, lo que los hace aplicables en un ampliorango de aplicaciones. Sin embargo, usualmente se necesitan buenas aproximacionesiniciales para obtener resultados adecuados.

En los modelos basados en regiones, se plantea un funcional que utiliza informa-cion de toda la imagen, y por ende, se suelen hacer suposiciones mas fuertes sobrelas imagenes. Usualmente, cuando las imagenes cumplen las suposiciones, se obtie-nen metodos que son convergentes, aun cuando se tenga una aproximacion inicial maspobre.

Los modelos basados en bordes, generalmente, obtienen peores resultados en image-nes texturadas o imagenes donde los bordes no se encuentran bien definidos [CV01]que los modelos basados en regiones.

En lo que sigue revisamos los modelos mas populares, propuestos en la literatura,para segmentar imagenes utilizando conjuntos de nivel.

4.1. Segmentacion basada en bordes

La idea basica en la segmentacion basada en bordes es la de evolucionar una curva,sujeta a restricciones provenientes de una imagen I para detectar objetos en la misma.Se empieza con una curva alrededor del objeto a detectar, y luego se evoluciona lacurva en direccion a su normal hasta que se ajuste al borde del objeto a detectar.

Sea I : D 7−→ R una imagen y C : [0,1] 7−→ D la parametrizacion de una curva. Elmodelo snake [KWT88] busca el mınimo del funcional:

E(C) = α

∫ 1

0|C′(s)|2ds+β

∫ 1

0|C′′(s)|2ds−λ

∫ 1

0|∇I(C(s))|2ds (4.1)

donde α,β,λ son parametros positivos. Los dos primeros terminos controlan el sua-vizado de la curva (energıa interna), mientras que el tercero atrae la curva hacia losobjetos de la imagen (energıa externa).

Los primeros intentos propuestos de encontrar el mınimo de la Ec. 4.1 se basaronen metodos de descenso por gradiente, utilizando una parametrizacion de la curva. Sibien utilizando este enfoque se han logrado implementaciones en tiempo real, tiene ladesventaja de no poder lidiar con cambios de topologıa en la curva.

4. SEGMENTACION DE IMAGENES POR EVOLUCION DE CURVAS 38

4.1.1. Contornos activos geodesicos

Los contornos activos geodesicos fueron propuestos en [CKS95], partiendo del mo-delo snake [KWT88] y se propone minimizar el funcional:

E(C) = α

∫ 1

0|C′(s)|2ds−λ

∫ 1

0g(∇I(C(s)))ds (4.2)

donde g(~z) es una funcion que debe ser positiva, decreciente y cumplir:

lım|z|→∞

g(~z) = 0 (4.3)

las funciones g que cumplen dichas condiciones se llaman funciones de deteccion debordes. Una eleccion tıpica de g es:

g(|∇I|) =1

1+ |∇(G⊗ I)|p(4.4)

siendo G una gaussiana y p≥ 1.Se pueden expresar las ecuaciones de Euler-Lagrange de la Ec. 4.2 dentro del for-

malismo de conjuntos de nivel como:

∂φ

∂t= |∇φ|g(∇I)κ+∇g(∇I) ·∇φ. (4.5)

Las ecuaciones de movimiento que se obtienen utilizando el gradiente para guiar ydetener la evolucion de la curva. Por lo tanto, los objetos que se pueden detectar coneste enfoque deben tener bien definidos sus bordes. En la siguiente seccion, revisare-mos enfoques basados en regiones que integran informacion de toda la imagen, paraevolucionar la curva, y permiten detectar objetos aun cuando sus bordes no esten tandefinidos.

4.2. Segmentacion basada en regiones

En esta seccion vemos el modelo de contornos activos sin bordes [CV01], el cualse basa en el funcional Mumford-Shah. En la Sec. 5 vemos en detalle modelos quegeneralizan el modelo de contornos activos sin bordes.

4.2.1. Contornos activos sin bordes

El modelo de Contornos activos sin bordes fue introducido en [CV01], el mismosupone que la imagen que se desea segmentar se conforma de dos regiones, cuyasintensidades de grises G1,G2 son aproximadamente contantes dentro de cada region.

Basados en el funcional de Mumford-Shah, en [CV01] proponen minimizar el fun-cional:

ECA(G1,G2,φ) = µ∫

Dδ(~x)|∇φ(~x)|d~x+ν

∫D

H(φ)d~x

+λ1

∫D|I0(~x)−G1|2H(φ(~x))d~x

+λ2

∫D|I0(~x)−G2|2(1−H(φ(~x)))d~x

(4.6)


(a) Imagen a segmen-tar.

(b) Contorno resultante utili-zando µ grande.

(c) Contorno resultante utili-zando µ chico.

Fig. 4.1: Segmentacion utilizando diferentes valores de µ.

donde D⊆R2 es el dominio de la imagen I0, H es la funcion de Heaviside, δ es la deltade dirac, µ,ν,λ1,λ2 son parametros que sirven para regular la suavidad del contornoque se desea obtener.

Los dos primeros terminos de la Ec. 4.6 tienen el objetivo de suavizar el contornoque se obtiene. Los dos ultimos terminos de la Ec. 4.6 tienen el objetivo de obtener uncontorno que se ajuste a las regiones que se desean segmentar.

En efecto, si µ y ν son muy grandes con respecto a λ1 y λ2 el contorno que seobtiene sera suave pero no se ajustara bien a la region que se desea segmentar. En casocontrario, si µ y ν son muy pequenos con respecto a λ1 y λ2, el contorno que se obtienees irregular. En la Fig. 4.1(b) y Fig. 4.1(c) se puede ver como afectan estos parametrosen la segmentacion de Fig. 4.1(a). En la Fig. 4.1(b) se utilizo un µ grande y se obtuvoun contorno mas pequeno y regular pues se segmentaron todas las pelotitas como unaregion. En la Fig. 4.1(c) se utilizo un µ chico y se obtuvo un contorno mas grande eirregular pues se segmentaron las pelotitas por separado. El resultado esperado dependede la aplicacion en que se use el metodo. Es decir, hay aplicaciones del metodo en lascuales se puede desear que se agrupen a las pelotitas como una region y aplicaciones enlas que se desea que las pelotitas esten separadas. En resumen, el parametro µ funcionacomo parametro de escala.

En [CV01], se propone un algoritmo de dos pasos para minimizar la Ec. 4.6 quese repiten hasta obtener una solucion estacionaria, es decir φ(x,y, t)≈ φ(x,y, t +1) o loque es equivalente ∂φ

∂t = 0. En el primer paso se minimiza ECA(G1,G2,φ) con respectoa G1 y G2. En el segundo paso se minimiza ECA(G1,G2,φ) con respecto a φ.

Para minimizar la Ec. 4.6 con respecto a G1 se calcula G1 usando la siguienteformula:

G1(φ) =∫

D I0(~x)H(φ(~x))d~x∫D H(φ(~x))d~x

, (4.7)

en forma similar se puede minimizar Ec. 4.6 con respecto a G2:

G2(φ) =∫

D I0(~x)(1−H(φ(~x)))d~x∫D(1−H(φ(~x)))d~x

. (4.8)

Es decir, que se calcula el promedio de las intensidades de gris dentro y fuera delas regiones.


Para minimizar la Ec. 4.6 con respecto φ se calculan las ecuaciones de Euler-Lagrange asociadas :

∂ECA(G1,G2,φ)∂φ

= |∇φ|[

µdiv(

∇φ

|∇φ|

)−ν−λ1(I0−G1)2 +λ2(I0−G2)2

]= 0 en Ω× (0,∞)

φ(~x,0) = φ0(~x) en Ω

(4.9)

con las condiciones apropiadas sobre el borde de Ω y siendo que φ0 define el contornoinicial.

Es interesante contrastar los resultados que se obtienen utilizando el metodo debanda angosta con los que se obtienen resolviendo las PDEs. En la Fig. 4.2(a) se puedever una imagen a segmentar junto con un posible contorno inicial. En las Fig. 4.2(b)y Fig. 4.2(c) se pueden ver los resultados de la segmentacion resolviendo las PDEs yutilizando el metodo de banda angosta, respectivamente. Es interesante observar quela region en forma de anillo, utilizando el metodo de banda angosta, fue segmentadacomo un cırculo, mientras que resolviendo las PDEs se segmento correctamente. Loque sucede con el metodo de banda angosta es que no se logra segmentar el hueco delcırculo, pues no se encuentran nuevos bordes.

(a) Imagen a segmentarjunto con el contorno ini-cial marcado en rojo.

(b) Resultado de la segmenta-cion de contornos activos sinbordes resolviendo las PDEs.

(c) Resultado de la segmenta-cion de contornos activos sinbordes usando el metodo debanda angosta.

Fig. 4.2: Comparacion del resultado de la segmentacion de contornos activos sin bordes, usandoel metodo de banda angosta y resolviendo las PDEs.

5. EVOLUCION DE CURVAS BASADO EN REGIONES

Consideraremos una region Ω como un conjunto de pixels de una imagen. Y unvector de caracterısticas como un vector de valores que permiten distinguir dos re-giones. Los vectores de caracterısticas intentan distinguir regiones basandose en losniveles de gris, la textura o el color, entre otras elecciones posibles.

Una region es considerada homogenea si los valores del vector de caracterısticasv(x) para cada pixel x, son consistentes con un modelo estadıstico apropiado. La Fig.5.1 muestra diferentes regiones homogeneas con respecto a un vector de caracterısticas.

Fig. 5.1: Ejemplo de regiones homogeneas, el fondo fue creado con una distribucion gaussianade niveles de gris de media 128 y desviacion estandar 20. La cara de Mickey Mousefue creada con una distribucion gaussiana de niveles de gris de media 128 y desviacionestandar 80.

El objetivo en segmentacion de imagenes es partir una imagen en regiones ho-mogeneas, las cuales se espera que se correspondan con los objetos que se deseanidentificar. Mediante este planteo se obtiene una interpretacion estadıstica al problemade segmentacion de imagenes, en el cual se busca la particion mas probable dada unaimagen.

La evolucion de curvas puede utilizarse para segmentar imagenes, varios metodosbasados en una interpretacion estadıstica del problema de segmentacion de imageneshan sido propuestos [ZLY95, PD02] partiendo desde diferentes enfoques. En [ZLY95]se minimiza un funcional que se obtiene basandose en el criterio de Minimum Descrip-tion Length (MDL) [DHS00], mientras que en [PD02] se obtiene un funcional equiva-lente basandose en una aproximacion del maximum a posteriori (MAP) de la particionde la imagen, haciendo algunas suposiciones/simplificaciones.

En esta seccion, vemos el enfoque basado en MAP y MDL y luego vemos diferentes

5. EVOLUCION DE CURVAS BASADO EN REGIONES 42

modelos estadısticos para las regiones. Finalmente proponemos un nuevo metodo queevaluaremos experimentalmente en la Sec. 6.

5.1. Maximum a posteriori de la particion de la imagen

Siguiendo [Rou04], sea P(Ω) = Ω1, . . . ,ΩN a una particion en regiones de unaimagen I. Sea ∂P(Ω) = ∂Ω1, . . . ,∂ΩN los bordes de las regiones de la particion P(Ω).

Se desea maximizar P(P(Ω)|I), la cual representa la probabilidad a posteriori dela particion P(Ω) dada la imagen I. Dado que en general no se tiene una formula, laestimamos utilizando la regla de Bayes como:

P(P(Ω)|I) =P(I|P(Ω))P(P(Ω))

P(I)(5.1)

donde P(I) y P(P(Ω)) son la probabilidad de la imagen y de la particion, respectiva-mente. El termino P(I|P(Ω) representa la probabilidad de la imagen I, dada la particionP(Ω). Como P(I) no depende de P(Ω), entonces maximizar P(P(Ω)|I) es equivalentea maximizar P(I|P(Ω))P(P(Ω)).

5.1.1. Restricciones sobre la particion

La probabilidad P(P(Ω)) permite integrar conocimiento a priori sobre las parti-ciones de la imagen. Una opcion posible es la de favorecer particiones con contornospequenos, mediante:

P(P(Ω)) ∝ e−µ|C| (5.2)

donde |C| es el largo del contorno y µ es un parametro que controla la importancia quese desea otorgar a esta suposicion. Otras opciones se pueden encontrar en la literatura[PD02, Rou04].

5.1.2. Restricciones sobre las regiones

La probabilidad P(I|P(Ω)) se puede estimar basandose en los valores de la imagenque se desea particionar. Suponiendo que la imagen se compone de N regiones P(Ω) =Ω1, . . . ΩN independientes, entonces P(I|P(Ω)) se puede escribir como :

P(I|P(Ω)) = P(I|Ω1)P(I|Ω2) . . .P(I|ΩN) (5.3)

donde P(I|ΩX ) denota la probabilidad de tener la imagen I dado ΩX .Si ademas se supone que los pixels dentro de las regiones son variables aleatorias

independientes e identicamente distribuidas se puede expresar P(I|ΩX ) como:

P(I|ΩX )≈ P(v|ΩX ) = ∏x∈ΩX

P(v(x)|ΩX ) (5.4)

siendo v(x) el vector de caracterısticas de la region para cada pixel x (ver Sec. 5.2).Remplazando la Ec. 5.4 en la Ec. 5.3:

P(I|P(Ω)) = ∏x∈Ω1

P(v(x)|Ω1) ∏x∈Ω2

P(v(x)|Ω2) . . . ∏x∈ΩN

P(v(x)|ΩN) (5.5)


La aproximacion de la Ec. 5.5 depende del modelo estadıstico que se use paraP(v(x)|ΩX ) y de los vectores de caracterısticas elegidos para distinguir entre las regio-nes. En las siguientes secciones veremos algunas elecciones de la literatura y propon-dremos un nuevo modelo.

5.1.3. Formulacion de la energıa

Finalmente, la maximizacion de P(I|P(Ω))P(P(Ω)) es equivalente a la minimiza-cion del funcional E(P(Ω)) luego de aplicar menos el logaritmo:

E(P(Ω)) =− log(P(I|P(Ω))P(P(Ω)))=− log(P(I|P(Ω)))− log(P(P(Ω)))

=− log

(∏

x∈Ω1

P(v(x)|Ω1) ∏x∈Ω2

P(v(x)|Ω2) . . . ∏x∈ΩN

)− loge−µ|C|

=−∑i

∫Ωi

logP(v(x)|Ωi)dx+µ|C|

(5.6)

Los trabajos [ZLY95, PD02] se basan en el funcional de la Ec. 5.6 pues brinda unainterpretacion estadıstica al problema de segmentacion de imagenes. Los supuestos quese utilizaron fueron:

Pixels dentro de las regiones son variables aleatorias independientes e identica-mente distribuidas.

La imagen esta compuesta de N regiones independientes.

Se favorecen los contornos cortos.

5.1.4. Minimizacion de la energıa

En el caso de que solo se tengan dos regiones, el funcional de la Ec. 5.6 se puedeexpresar con el formalismo de conjuntos de nivel:

E(φ)=−∫

logP(v(x)|Ω0)H(φ)dx−∫

logP(v(x)|Ω1)(1−H(φ))dx+µ∫

δ(φ(x))|∇φ(x)| dx

(5.7)Para minimizar el funcional de la Ec. 5.7 se pueden calcular las ecuaciones de

Euler-Lagrange asociadas, con las cuales se obtienen las siguientes ecuaciones de mo-vimiento de conjuntos de nivel:

∂φ

∂t= |∇φ|

[logP(v(x)|Ω0)− logP(v(x)|Ω1)+µdiv

(∇φ

|∇φ|

)]= |∇φ|

[log(

P(v(x)|Ω0)P(v(x)|Ω1)

)+µdiv

(∇φ

|∇φ|

)] (5.8)

Debido a su interpretacion, los terminos fi = logP(v(x)|Ωi)∇φ

|∇φ| de la Ec. 5.8 se co-nocen como ”fuerzas estadısticas” [ZLY95]. El movimiento en un punto x de la curva


Fig. 5.2: Fuerzas estadısticas actuando sobre un punto entre dos regiones.

esta determinado por el test de verosimilitud : P(v(x)|Ω0)P(v(x)|Ω1) . Si P(v(x)|Ω0) > P(v(x)|Ω1),

entonces la curva se mueve expandiendo la region Ω0. O lo que es equivalente, si xsatisface mejor el criterio de homogeneidad de la region Ω0 que el de la region Ω1,entonces la curva expande la region Ω0. En la Fig. 5.2 se pueden ver las fuerzas es-tadısticas actuando sobre un punto entre dos regiones.

En el caso de que se tengan mas de dos regiones, se pueden evolucionar variasfunciones de conjuntos de nivel [Rou04].

5.2. Vectores de caracterısticas

Los vectores de caracterısticas son los que permiten discernir entre las diferentesregiones de las imagenes. La eleccion del vector de caracterısticas se encuentra estre-chamente ligada con el tipo de regiones que se desean segmentar. La eleccion adecuadade un vector de caracterısticas debe permitir discernir las regiones, en base a las distri-buciones de los valores de los vectores en cada region.

En el caso de que las regiones que se desean segmentar sean no texturadas, se pue-den utilizar vectores basados en los niveles de gris o en el color [ZLY95]. Sin embargocuando las regiones contienen texturas, los niveles de gris o el color no suelen ser bue-nas elecciones.

5.2.1. Caracterizacion de regiones con texturas

Textura es una de las areas menos comprendidas en vision por computadora. Aun-que no exista una definicion rigurosa de textura que agrupe todos los conceptos rela-cionados, se pueden nombrar algunos de los aspectos fundamentales. Las texturas sonpatrones compuestos de subpatrones que se repiten, los cuales generan la percepcion debrillo, uniformidad, densidad, robustez, frecuencia, direccionalidad, entre otros. Una delas principales causas de la falta de definicion de textura, se debe a que existen ejemplosde texturas que muestran propiedades contradictorias. Investigaciones han demostradoque la percepcion de las texturas en el sistema de vision humano es uno de los primerospasos que se efectuan. Los metodos mas populares se pueden agrupar en dos clases.


Los metodos espectrales se relacionan con estadısticas basadas en respuestas a fil-tros. La evidencia muestra que algunos bancos de filtros simulan los receptores neu-rologicos del sistema visual humano, la principal motivacion de estos metodos. Unbanco de filtros consiste de un conjunto de filtros disenado sensible a frecuencias,orientaciones o escalas. Algunos autores han cuestionado la efectividad de los bancosde filtros [VZ03].

Los metodos basados en estadısticas incluyen estadısticas de primer orden como:media, desviacion estandar y momentos de mayor orden. Tambien se utilizan estadısti-cas de segundo orden basadas en la matriz de co-ocurrencia. La matriz de co-ocurrenciaM(dx,dy)(i, j) captura la relacion espacial entre pares de pixels en una imagen. Cadaelemento de la matriz M(dx,dy)(i, j) representa la frecuencia de que ocurran dos pixelsseparados por el desplazamiento (dx,dy) y que uno tenga intensidad de gris i y el otrointensidad de gris j. Las caracterısticas propuestas por Haralick [HSD73] se encuen-tran entre las mas populares y se han mostrado que logran superar, en muchos casos, elresto de los metodos.

El tamano de la matriz de co-ocurrencia crece en forma cuadratica cuando aumentala cantidad de niveles de gris, lo cual hace difıcil de manejarla computacionalmente.La forma comun de solucionar este problema es la de agrupar diferentes niveles de grisen los elementos de la matriz. En el Alg. 17 se puede ver el algoritmo para calcular lamatriz de co-ocurrencia M(dx,dy) de una imagen I, con los niveles de gris agrupados enfilas/columnas de N niveles de grises.

Algoritmo 17 Calcular matriz de co-ocurrencia1: function CALCULARMATRIZDECOOCURRENCIA(I, (dx,dy), N)2: for px = 1 : Width do3: for py = 1 : Height do4: if el pixel (px +dx, py +dy) sigue dentro de la imagen then5: bin1 =

⌊I(px+dx,py+dy)

N

⌋6: bin2 =

⌊I(px,py)

N

⌋7: M(dx,dy)(bin1,bin2)←M(dx,dy)(bin1,bin2)+18: end if9: end for

10: end for11: M(dx,dy)←M(dx,dy)/Sum(M(dx,dy))12: end function

Por ejemplo, para la siguiente imagen:

0 1 2 31 0 2 12 1 0 11 2 3 0

(5.9)


la matriz de co-ocurrencia M(1,1) es:

19

3 0 0 00 1 1 10 2 1 00 0 0 0

(5.10)

y la matriz de co-ocurrencia M(1,1) agrupando los niveles de gris en 2 columnas es:

19

(4 22 1

)(5.11)

5.3. Modelos estadısticos

En esta seccion consideramos diferentes modelos estadısticos para las regiones.Revisamos el modelo de estadıstica parametrica propuesto en [ZLY95] y el modelo deestadıstica no parametrica propuesto en [Rou04]. Finalmente introducimos un nuevomodelo basado en test de hipotesis.

5.3.1. Modelos basados en estadıstica parametrica

En [ZLY95], se asume que la distribucion del vector de caracterısticas de cadaregion pertenece a una familia de distribuciones. Cada region se diferencia por losparametros de la distribucion. Luego la probabilidad P(v(x)|Ωi) es equivalente a P(v(x)|~θi),siendo ~θi los parametros de la distribucion.

Ademas se propone utilizar los parametros θi de las distribuciones como incognitasen la Ec. 5.6 obteniendose un nuevo funcional a minimizar:

E(Ω1, . . . ,ΩN,~θ1, . . . , ~θN) =−∑i

∫Ωi

logP(v(~x)|~θi)dx+µ|C|. (5.12)

En el funcional se pueden distinguir dos tipos de parametros: las regiones Ωi y losparametros estadısticos ~θi. Por lo tanto, en [ZLY95] se propone un algoritmo de dospasos para minimizar el funcional, los cuales se repiten hasta obtener un mınimo. Enel primer paso se minimiza el funcional con respecto de los parametros estadısticos yen el segundo paso se minimiza el funcional con respecto a las regiones.

La minimizacion del funcional con respecto a los parametros estadısticos, para cadaregion, se efectua mediante la formula:

θi = argmın~θ

(−∫

Ωi

logP(~θ|v(~x))dx)

. (5.13)

En muchos casos los parametros se pueden encontrar en forma analıtica, por ejem-plo, en el caso de que las distribuciones se asuman Gaussianas, los parametros son lamedia y la varianza de la poblacion. La minimizacion del funcional con respecto a lasregiones se efectua evolucionando las funciones de conjunto de nivel.

Ademas es interesante destacar que el metodo funciona de manera no supervisada,pues los parametros de las distribuciones son estimados a medida que se evolucionan


las curvas. En caso de que se tenga informacion de antemano sobre las distribuciones delas regiones, la misma se puede utilizar evolucionando unicamente la curva y obviandoel paso de minimizacion con respecto a los parametros estadısticos.

5.3.2. Modelos basados en estadıstica no parametrica

La eleccion de una familia parametrica para aproximar la distribucion del vector decaracterısticas puede ser visto como una limitacion de los modelos basados en estadısti-ca parametrica. En contraposicion, los modelos basados en estadıstica no parametricapueden aproximar cualquier funcion de densidad para un conjunto de datos lo sufi-cientemente grande. Uno de los metodos no parametricos mas difundidos es ParzenWindows [DHS00]. La estimacion de la funcion de densidad, mediante Parzen Win-dows, para una region ΩX se puede expresar como:

PX (~z) =1|ΩX |

∫ΩX

1h

K(

~z− v(~y)h

)d~y, (5.14)

donde K es una funcion kernel y h es un parametro de escala. Diferentes tipos denucleos se han propuesto. Los mas comunes son el esferico, el Gaussiano, o el Epa-nechnikov. Sin embargo, el parametro mas importante es h. En la Fig. 5.3 se puedever la aproximacion de una funcion de densidad bimodal, tomando dos mil muestrasy utilizando un nucleo Gaussiano con diferentes elecciones de h. A medida que au-menta el h la funcion de densidad estimada resultante tiene menos ruido pero tambienpierde fluctuaciones, que podrıan ser inherentes a la funcion de densidad que se quiereestimar.

Utilizando la Ec. 5.14 se puede reescribir la funcion de energıa de la Ec. 5.6:

E(P(Ω)) =−∑i

∫Ωi

log(

1|Ωi|

∫Ωi

1h

K(

v(~x)− v(~y)h

)d~y)

dx+µ|C| (5.15)

Las ecuaciones de Euler-Lagrange para la Ec. 5.15 en el caso de que solo se tengandos regiones, son [Rou04]:

∂φ

∂t= |∇φ|

[µdiv

(∇φ

|∇φ|

)+ log

P1(v(~x))P2(v(~x))

− 1|Ω1|

+1|Ω2|

+q1(v(~x))−q2(v(~x))]

(5.16)siendo qX (z):

qX (z) =1|ΩX |

∫ΩX

K(~z−v(~x)h )

hPX (v(~x))d~x (5.17)

En general se suele utilizar la siguiente version simplificada de la Ec. 5.16 [Rou04]:Pi(v(~x)) = 1|Ωi|

∫Ωi

1h K(

v(~x)−v(~y)h

)d~y

∂φ

∂t = |∇φ|[µdiv

(∇φ

|∇φ|

)+ log P1(v(~x))

P2(v(~x))

] (5.18)

La eleccion del kernel K y del parametro h son de gran importancia en este tipode metodos debido a que una mala eleccion puede hacer que el metodo no converja.


(a) h = 1 (b) h = 10

(c) h = 20 (d) h = 30

Fig. 5.3: Estimacion de la funcion de densidad utilizando un nucleo Gaussiano y variando el h.


Fig. 5.4: Funciones de densidad de dos distribuciones Normales. La distribucion de la izquierdatiene media menos uno y varianza uno, la de la derecha tiene media uno y misma va-rianza. La region en gris es la de posible clasificacion erronea, la cual tiene probabilidaddel 32 %.

Los parametros deben elegirse para que se represente en forma adecuada el histogra-ma. Valores grandes de h remueven el ruido, pero tambien pueden hacer desaparecerfluctuaciones en el histograma.

Si bien el metodo de [Rou04] plantea un nuevo funcional, basado en el funcional decompeticion de regiones, en el fondo lo unico que se hace es modificar el Likelihoodratio de la Ec. 5.8 para incorporar una aproximacion de la funcion de distribucion delas regiones mediante Parzen Windows.

5.3.3. Modelos basados en test de hipotesis

Una desventaja que tienen tanto los modelos basados en estadıstica parametrica co-mo en estadıstica no parametrica es que las fuerzas estadısticas en un punto x del bordeentre las regiones Ωi y Ω j dependen de P(v(x)|Ωi) y de P(v(x)|Ω j). Si bien esto pareceadecuado, en realidad se esta utilizando una sola muestra de la distribucion y puede serbastante probable que v(x) se encuentre en la cola de la distribucion. Este hecho puedehacer que el pixel x sea clasificado erroneamente. En la Fig. 5.4 se puede observar unejemplo de esta situacion para distribuciones Gaussianas, la region sombreada es la deposible clasificacion erronea.

Como se explica en [ZLY95], un caso extremo en el modelo estadıstico parametricoutilizando Gaussianas, se genera cuando las distribuciones de las regiones Ωi y Ω jtienen la misma media pero distinta varianza, como se puede ver en la Fig. 5.5.

En [ZLY95] se propone, para modelos parametricos basados en Gaussianas, solu-cionar estos problemas utilizando ventanas. Sea V (~x) = v(~y) :~y ∈W (~x), siendo Wuna ventana de tamano m centrada en~x y suponiendo que cada v(~y) sigue una distribu-cion N(µ,σ2), como se muestra con lıneas negras en la Fig. 5.6. Si se calcula la mediamuestral : V (~x) = 1

|V (~x)| ∑z∈V (~x) z se obtiene que sigue una distribucion N(µ, σ2

m ), la cualse muestra en lıneas punteadas en la Fig. 5.6. Dado que la varianza se dividio por m seredujo el error de clasificacion.


Fig. 5.5: Funciones de densidad de dos distribuciones Normales. Una distribucion tiene mediacero y varianza dos, la otra tiene la misma media pero varianza cuatro. La region en grises la de posible clasificacion erronea, la cual tiene probabilidad del 55 %.

Fig. 5.6: Comparacion entre regiones de clasificacion erronea para el par de distribucionesN(µ1,σ

21) y N(µ2,σ

22) (lıneas solidas) y para el par de distribuciones N(µ1,

σ21

m ) y

N(µ2,σ2

2m ) (lıneas punteadas) que se obtienen tomando ventanas de tamano m.


Si bien este enfoque resuelve los problemas en el caso de Gaussianas, el enfoque esdifıcil de generalizar pues depende de los parametros de la distribucion. En esta seccionproponemos un nuevo enfoque para solucionar el problema.

Nuestro enfoque utiliza el test estadıstico chi-cuadrado para comparar la distribu-cion de los valores que toman los vectores de caracterısticas en una ventana. El testestadıstico chi-cuadrado, es un procedimiento que permite determinar si un conjuntode observaciones sigue una distribucion conocida, o si dos conjuntos de observacionessiguen la misma distribucion, con cierto grado de significancia. El test chi-cuadrado sedefine como el resultado de evaluar:

χ2(H1,H2) =

N

∑i=1

(H1i −H2

i )2

H1i +H2

i(5.19)

donde H1 y H2 son dos histogramas normalizados con N bins. El valor del test chi-cuadrado es cero cuando los histogramas H1 y H2 son iguales y crece a medida que loshistogramas difieren. Si N es igual a 1, entonces solamente se tiene un solo bin y nose puede distinguir diferentes distribuciones. Mientras mas grande es el N, se puedendistinguir mas distribuciones.

El nuevo metodo introduce el test estadıstico chi-cuadrado en las ecuaciones demovimiento (5.8), a fin de comparar las distribuciones del vector de caracterısticasdentro de una ventana W (~x) centrada en el punto~x.

Dado que las imagenes que deseamos analizar contienen texturas, utilizamos unvector de caracterısticas que permite discernir entre las mismas. Una opcion natural esla matriz de co-ocurrencia pues, como se ha discutido anteriormente, permite represen-tar texturas y como es un histograma de segundo orden, el test estadıstico chi-cuadradose puede utilizar para comparar las matrices de co-ocurrencia.

Las ecuaciones de movimiento propuestas son:

∂φ

∂t= |∇φ|

[log

(χ2(M(dx,dy)(W (x)),M(dx,dy)(Ω0))χ2(M(dx,dy)(W (x)),M(dx,dy)(Ω1))

)+µdiv

(∇φ

|∇φ|

)](5.20)

donde M(dx,dy)(W (x)) es la matriz de co-ocurrencia de n× n de la ventana de m×mcentrada en el pixel x, M(dx,dy)(Ω0) y M(dx,dy)(Ω1) son las matrices de co-ocurrencia,que representan las texturas de las regiones Ω1 y Ω0. Las cuales son calculadas, pre-viamente, utilizando diferentes muestras de las regiones.

Si bien en la Sec. 6 se vera en detalle como usar el metodo descrito para CMEs, en laFig. 5.7 se puede ver las regiones utilizadas para estimar las matrices de co-ocurrenciade CMEs y del fondo.

La eleccion de los parametros m y n afectan el desempeno del nuevo metodo. Mien-tras mas grande sea el m se obtiene una menor precision para localizar la curva quesepara las regiones, pues las matrices de co-ocurrencia de las ventanas de los pixels enla curva no siguen la distribucion de ninguna de las regiones, sino una mezcla de lasmismas. Por otro lado si el m es pequeno entonces las fuerzas estadısticas se basan enuna menor cantidad de pixels y por ende el error de clasificacion es mayor. Ademasla eleccion del m y del n estan relacionadas, el m debe ser lo suficientemente grandecomo para que los bins sean representativos de la distribucion.


(a) Regiones utilizadas para estimar lasmatrices de co-ocurrencia del CME (rojo)y del fondo (azul).

(b) Matrices de co–ocurrencia estimadas pa-ra el CME (gris oscuro) y para el fondo (grisclaro). Cada columna corresponde a un bin de32 niveles de gris.

Fig. 5.7: Estimacion de matrices de co-ocurrencia.

Es interesante recalcar que el metodo propuesto es supervisado dado que es necesa-rio que se conozca la matriz de co-ocurrencia de las regiones de antemano, a diferenciadel metodo propuesto [ZLY95] donde los parametros de las distribuciones se estimanautomaticamente.

5.4. Resumen

En esta seccion vimos la evolucion de curvas basadas en regiones en la cual sebusca la particion P(Ω) = Ω1, . . . ,ΩN mas probable de una imagen, mediante laminimizacion del funcional:

E(P(Ω)) =−∑i

∫Ωi

logP(v(x)|Ωi)dx+µ|C|. (5.21)

Ademas vimos dos modelos estadısticos para las regiones. El primero, basado enestadıstica parametrica en cual se asume que la distribucion del vector de caracterısticasde cada region pertenece a una familia de distribuciones. Cada region se diferencia porlos parametros de la distribucion. Luego la probabilidad P(v(x)|Ωi) es equivalente aP(v(x)|~θi), siendo ~θi los parametros de la distribucion.

El segundo modelo, basado en estadıstica no parametrica, puede aproximar cual-quier funcion de densidad para un conjunto de datos lo suficientemente grande.

Vimos diferentes vectores de caracterısticas para texturas, haciendo especial enfasisen la matriz de co-ocurrencia.

Finalmente, introdujimos un nuevo modelo estadıstico, basado en el test estadısticochi-cuadrado, el cual compara la distribucion de los vectores de caracterısticas en unaventana.

6. APLICACION A LA DETECCION Y SEGUIMIENTO DE CMESEN SECUENCIA DE IMAGENES

Los objetos que deseamos detectar y seguir son las Eyecciones Coronales Masivaso CMEs por sus siglas en ingles, como vimos en la Sec. 1. Su firma en los coronografoses la de una nueva, discreta y brillante luz con direccion saliente. Los CMEs puedenser muy debiles para ser detectados en las imagenes obtenidas por los coronografos.Una tecnica usada comunmente, es la de realzar el contraste de los CMEs con respectoal fondo mediante running differences (diferencias consecutivas), donde cada imagende la secuencia se obtiene de la diferencia de dos imagenes consecutivas. Por ende,las senales pseudo-estacionarias que se encuentran en las imagenes se cancelan, ob-teniendose casi solamente los CMEs. En la Fig. 6.1(a) se puede observar una imagenproveniente del LASCO C2 sin procesar, en la Fig. 6.1(b) se puede observar la imagenrealzada mediante running differences.

(a) Imagen proveniente del LASCO C2sin procesar.

(b) Imagen proveniente del LASCO C2realzada usando running differences.

Fig. 6.1: Comparacion de imagenes utilizando la tecnica de running differences para realzar elcontraste de los CMEs.

La firma tıpica que se puede observar de los CMEs en las running differences esla de un leading edge (frente) brillante, seguido por una region oscura y una cola dematerial con multiples posibles configuraciones. En la Fig. 6.2 se pueden ver el leadingedge, la region oscura y la cola.

En esta seccion, proponemos un modelo de seguimiento y deteccion de CMEs,original, basado en la modificacion del modelo de competicion de regiones descritoen la seccion 5. El modelo presentado, se utiliza para segmentar el leading edge de

6. APLICACION A LA DETECCION Y SEGUIMIENTO DE CMES EN SECUENCIA DE IMAGENES 54

@@I

leading edge

cola

zona oscura

@@@

@@I

disco oclutor

Fig. 6.2: Imagen en la que se puede observar el leading edge brillante, la region oscura que lesigue, la cola del CMEs y el disco oclutor.

los CMEs en las secuencias de imagenes procesadas usando running differences delLASCO/C2. Se contrastan los resultados obtenidos usando el modelo 5.3.3 con losobtenidos usando el modelo de competicion de regiones y se analizan las dificultadesencontradas. Finalmente, presentamos algoritmos para el calculo de las propiedades delos CMEs.

6.1. Modelo de deteccion de CMEs

En este trabajo, proponemos detectar los CMEs segmentando el leading edge en lasimagenes running differences del LASCO/C2. Se pueden distinguir dos enfoques parasegmentar el leading edge.

El enfoque bottom–up, consiste en segmentar en regiones homogeneas toda la ima-gen y luego agrupar las regiones que se corresponden con el objeto de interes, el lea-ding edge en nuestro caso. En este caso, el objeto de interes puede estar segmentadoen multiples regiones, algunas de las cuales pueden mezclar el objeto de interes con elfondo. Ademas, puede suceder que las regiones segmentadas no contengan al objetode interes. Un ejemplo de modelo de segmentacion que utiliza este enfoque es el decompeticion de regiones.

Un enfoque complementario es el top–down, en el que se utiliza conocimiento deantemano sobre las propiedades del objeto a segmentar tales como la forma, la texturao el color, entre otros. Este enfoque es mucho mas sensible a la segmentacion inicialutilizada que el enfoque bottom–up. La segmentacion inicial debe contener el objetoa segmentar. Un ejemplo de modelo de segmentacion que utiliza este enfoque es el deContorno Activos Sin Bordes [CV01], conociendose de antemano los niveles de grisque componen las regiones.

En este trabajo usamos el enfoque top–down pues al utilizar conocimiento a prioridel objeto, nos permite asegurar que la region segmentada se corresponde solamentecon CMEs. Ademas, al no tener que segmentar toda la imagen en todas las regionesque la componen, es mas rapido que el bottom–up.


En el Alg. 18 se resume el esquema de deteccion de CMEs. El mismo establece uncontorno inicial en forma de anillo alrededor del disco oclutor pues los CMEs, en sufase inicial, se desarrollan cerca del disco oclutor. Luego se hace evolucionar el con-torno, utilizando el conocimiento a priori de las CMEs y del fondo. En caso de que nose este desarrollando ningun CME, el contorno se contraera hasta desvanecerse. Si seestuviesen desarrollando una o mas CMEs, el contorno se ajustara a cada CME. Dadoque todas las CMEs detectadas se agruparan en la misma region, es necesario un anali-sis a posteriori para detectar las CMEs por separado, el mismo se efectua calculando lascomponentes conexas de la region que agrupa las CMEs. Finalmente, verificamos queno haya CMEs desarrollandose, detectados en alguna imagen anterior, en las cercanıas.

Algoritmo 18 Deteccion de CMEs1: Establecer region inicial Ωini en forma de anillo alrededor del disco oclutor.2: Evolucionar la region Ωini3: for all region conexa CC dentro de la region resultante Ω f in do4: if No hay CME desarrollandose en las cercanıas then5: Agregar CC a la lista de CMEs detectados.6: end if7: end for

En la Fig. 6.3(b) se muestra la disposicion del contorno inicial, en forma de anillo,alrededor del disco oclutor para la deteccion de CMEs en la Fig. 6.3(a), la cual tiene dosCMEs desarrollandose. En las Fig. 6.3(c) - 6.3(e) se muestra la evolucion del contorno.En la Fig. 6.3(f) se muestra el contorno resultante, la cual detecta correctamente losdos CMEs que se inician.

En la Fig. 6.4(b), al igual que en Fig. 6.3(b), se muestra la disposicion del con-torno inicial alrededor del disco oclutor para la deteccion de CMEs en la Fig. 6.4(a),la cual no tiene ningun CME desarrollandose. En las Fig. 6.4(c) - 6.4(d) se muestra laevolucion del contorno. En la Fig. 6.4(e) se muestra que el contorno resultante se des-vanecio, indicando que no hay ninguna CME desarrollandose. Es importante recalcar,que tanto en Fig. 6.4 como en Fig. 6.3, el algoritmo propuesto se comporto en formasatisfactoria.

6.2. Modelo de seguimiento de CMEs

Para el seguimiento de las CMEs en una secuencia de imagenes, proponemos que,el resultado de la segmentacion del CME de una imagen se use como estimacion inicialpara la segmentacion en la siguiente imagen. Cuando la region resultante de la segmen-tacion es vacıa se elimina de la lista de CMEs a seguir y se calculan sus propiedades(ver Sec. 6.3). El Alg. 19 resume el esquema de seguimiento de CMEs.

En la Fig. 6.5 se puede ver el resultado de aplicar el Alg. 19 a una secuencia deimagenes utilizando la caracterizacion de CMEs basada en texturas y test estadısticos,explicado en la Sec. 5.

Es importante recalcar, que las CMEs pueden variar la intensidad de gris durantesu desarrollo y por ende no es conveniente re-estimar el modelo estadıstico. Por otro


(a) Imagen del LASCO/C2 en la cual se deseadetectar CMEs.

(b) Region inicial Ωini, en forma de anillo al-rededor del disco oclutor.

(c) Evolucion de la region Ωini luego de la ite-racion 5.

(d) Evolucion de la region Ωini luego de la ite-racion 8.

(e) Evolucion de la region Ωini luego de la ite-racion 15.

(f) Segmentacion resultante Ω f in.

Fig. 6.3: Disposicion y evolucion del contorno inicial para detectar CMEs en una imagen conCME.


(a) Imagen del LASCO/C2 en la cual se deseadetectar CMEs.

(b) Region inicial Ωini, en forma de anillo al-rededor del disco oclutor.

(c) Evolucion de la region Ωini luego de la ite-racion 2.

(d) Evolucion de la region Ωini luego de la ite-racion 4.

(e) Segmentacion resultante Ω f in.

Fig. 6.4: Disposicion y evolucion del contorno inicial para detectar CMEs en una imagen sinCME.


Algoritmo 19 Seguimiento de CMEs1: for k← 1 to n do2: Cargar la imagen Ik3: for all cme en la lista de CMEs detectados do4: Evolucionar la region del cme que se obtuvo de la imagen k−15: if La region resultante es vacıa then6: Calcular las propiedades del CME y remover de la lista CMEs detecta-

dos7: end if8: end for9: end for

lado, como se utiliza el resultado de la segmentacion de la imagen anterior como esti-macion inicial, puede suceder que si el CME es muy abrupto (es decir se propaga muyvelozmente), el metodo no logre seguir estos eventos.

6.3. Calculo de propiedades de los CME

En esta seccion presentamos algoritmos para calcular las propiedades de las CMEsque son de interes para los fısicos solares.

A cada punto ~p de una imagen de coronagrafıa se le puede asociar un vector ~vp,con origen en el centro de Sol ~o y extremo en el punto ~p. Los bordes laterales de unaCME son los puntos ~p y~q del contorno de la CME, tales que los vectores ~vp y ~vq tienenangulo maximo. El ancho angular de una CME se define como el angulo formado porlos vectores ~vp y ~vq. El central position angle (CPA) de una CME se define como elangulo del vector ~vp +~vq medido en direccion anti–horaria empezando en el polo nortedel Sol (eje vertical).

En la Fig. 6.6 se pueden observar las propiedades de una CME segmentada. Losvectores A y B son los bordes laterales izquierdo y derecho, respectivamente. El vectorC es el resultado de la suma de los vectores A y B, que permite calcular el CPA. Elpunto D es el punto mas distante del contorno de la CME desde el centro del Sol.

El Alg. 20 muestra como calcular el ancho angular y los bordes laterales. Se calculael par de puntos p1, p2 del contorno de una CME que tienen mayor angulo entre sı. Paracalcular los puntos p1, p2, el algoritmo propuesto, en cada paso busca en el contornode la CME un punto que se aumente el angulo entre los p1, p2. Para calcular el CPAbasta con calcular el angulo, con respecto al norte solar, del resultado de hacer la sumade los puntos p1 y p2.

Para decidir si un punto x = (x1,x2) se encuentra en sentido horario o anti–horariocon respecto a un pixel y = (y1,y2), usamos el producto cruz x× y = x1y2 − x2y1,como se define en [CLR90], que puede ser interpretado como el area con signo delparalelogramo con vertices x,y,o,x + y, siendo o el origen de coordenadas. Si x× y espositivo, entonces x se encuentra en sentido horario a y; si el producto cruz es negativoentonces x se encuentra en sentido anti–horario a y.


(a) Imagen de la secuencia del LASCO/C2. (b) Imagen del LASCO/C2.

(c) Imagen del LASCO/C2. (d) Imagen del LASCO/C2.

Fig. 6.5: Seguimiento de CMEs usando el Alg. 19 de varios CMEs.

Algoritmo 20 Ancho angular de una CME1: p1 punto del Contorno de la CME2: p2 punto del Contorno de la CME3: for all p en el Contorno de la CME do4: if p se encuentra en sentido anti–horario a p1 then5: p1← p6: end if7: if p se encuentra en sentido horario a p2 then8: p2← p9: end if

10: end for11: return angulo entre p1 y p2


Fig. 6.6: Propiedades de una CME segmentada. El punto D es el punto mas distante del contornode la CME desde el centro del Sol. Los vectores A y B son los bordes laterales izquierdoy derecho. El vector C es el resultado de la suma de los vectores A y B, que permitecalcular el CPA.

6.4. Deteccion y seguimiento basado en niveles de gris y metodosparametricos

En esta seccion analizamos una variante del modelo de competicion de regionespara la deteccion y el seguimiento de CMEs. La variante utiliza como vector carac-terıstico los niveles de gris y asume que los niveles de gris siguen una distribucionNormal. El modelo a analizar usa, como conocimiento a priori, los niveles de gris quese corresponden con las CMEs y los niveles de gris que se corresponden con el fondo.Es decir, el modelo sigue el enfoque top–down descrito anteriormente. La evolucion decontorno se implementa utilizando el Alg. 16, de la Sec. 3.

En la Fig. 6.7 se puede observar los resultados del seguimiento de una CME ob-servada por el LASCO/C2 el dıa 1 de Enero del ano 2000. En la Fig 6.7(a) se muestrala deteccion de la CME en la primera imagen de la secuencia. En la Fig. 6.7(b) y Fig.6.7(c) se muestra el seguimiento de la CME para diferentes imagenes de la secuen-cia analizada. El conocimiento a priori de la CME y del fondo, para este ejemplo, sebaso en la estimacion de los parametros de las distribuciones Normales promediandovarias CMEs segmentadas a mano y varias muestras de fondo.

En la Fig. 6.8 se puede observar otros resultados del seguimiento de otra CMEobservada por el LASCO/C2 el dıa 1 de Enero del ano 2000. En la Fig. 6.8(a) semuestra la deteccion de la CME en la primera imagen de la secuencia. En la Fig.6.8(b) y Fig. 6.8(c) se muestra el seguimiento de la CME para diferentes imagenesde la secuencia analizada. El conocimiento a priori de la CME y del fondo, para esteejemplo, se baso en la estimacion de los parametros de las Normales promediandovarias CMEs segmentadas a mano y varias muestras de fondo.

En las ultimas secuencias se puede ver que los resultados no son muy buenos. Enla Fig. 6.9 se pueden observar los histogramas de la CME y del fondo de las Fig.


(a) Imagen observada por el LAS-CO/C2 a las 6.48 con el contorno dela CME detectada.

(b) Imagen observada por el LAS-CO/C2 a las 10.06 con el contorno dela CME que se sigue.

(c) Imagen observada por el LAS-CO/C2 a las 12.00 con el contorno dela CME que se sigue.

Fig. 6.7: Deteccion y seguimiento exitoso de CME observado por LASCO/C2, usando modelobasado en competicion de regiones con niveles de gris y suponiendo distribucionesNormales.


(a) Imagen observada por el LASCO/C2 a las14.30 con el contorno de una CME debil detec-tada.

(b) Imagen observada por el LASCO/C2 a las16.30 el contorno que sigue la CME debil no abar-ca toda la CME.

(c) Imagen observada por el LASCO/C2 a las17.05 donde la CME debil que se estaba siguiendose perdio.

Fig. 6.8: Deteccion y seguimiento fallido de CME observado por LASCO/C2, usando modelobasado en competicion de regiones con niveles de gris y suponiendo distribucionesNormales.


(a) Histograma de la CME de la Fig. 6.8(a). (b) Histograma del fondo de la Fig. 6.8(a).

Fig. 6.9: Histogramas de la CME y del fondo de la Fig. 6.8(a).

6.8. Inspeccionando los histogramas se hacen evidentes dos problemas que causan losresultados inesperados. El primero es que la suposicion de que los niveles de gris de lasCMEs siguen una distribucion Normal no es valida, Fig. 6.9(a). El segundo problemaes el gran solapamiento entre los histogramas de las regiones, lo que genera que el errorde clasificacion sea grande.

Para resolver el primer problema, utilizaremos el modelo propuesto en la Sec. 5.3,el cual no requiere conocer las distribuciones de los objetos de interes. Para resol-ver el segundo problema, agregaremos informacion sobre la textura de las CMEs. Enla siguiente seccion analizamos los resultados obtenidos mediante las modificacionespropuestas.

6.5. Deteccion y seguimiento basado en texturas y metodos basadosen test de hipotesis

En esta seccion analizamos la variante del modelo de competicion de regiones parala deteccion y el seguimiento de CMEs descrita en la Sec. 5.3, la cual utiliza el testchi–cuadrado para comparar la matriz de co–ocurrencia dentro de las ecuaciones demovimiento de conjuntos de nivel. Al igual que en la seccion anterior el enfoque utili-zado es top–down, sin embargo el conocimiento a priori en este modelo viene descritopor las matrices de co–ocurrencias del fondo y las CMEs. La evolucion de contorno seimplementa utilizando el Alg. 16, de la Sec. 3. En los resultados que se presentan a con-tinuacion usamos una matriz de co–ocurrencia M(1,1), de tamano 8× 8 y una ventanade tamano 7×7.

En la Fig. 6.10 se pueden observar las matrices de co–ocurrencia, para el CMEy para el fondo, calculadas en base a las imagenes de la secuencia de la Fig. 6.8. Lasmatrices de co–ocurrencia se corresponden a histogramas de segundo orden que son vi-siblemente diferentes. El metodo propuesto utiliza esta diferencia entre los histogramaspara clasificar los pixels en la region adecuada. La forma en que el metodo propues-


Fig. 6.10: Matrices de co–ocurrencia para un CME (gris oscuro) y para el fondo (gris claro).Cada columna corresponde a un bin de 32 niveles de gris.

to utiliza la diferencia entre histogramas para clasificar los pixels es mediante el testchi–cuadrado.

En las Fig. 6.11 y Fig. 6.12 se pueden contrastar los resultados de seguimiento deCMEs de nuestro metodo con el metodo de la seccion anterior. En la Fig. 6.11 se puedeobservar los resultados del seguimiento del mismo CME que se siguio en la Fig. 6.8.Con el metodo propuesto se logra seguir en forma exitosa el CME, a diferencia delmetodo de la seccion anterior que no pudo.

Mientras que en la Fig. 6.12 se puede observar los resultados del seguimiento delmismo CME que se siguio en la Fig. 6.7. Con el metodo propuesto se logra seguir enforma exitosa el CME, al igual que con el metodo de la seccion anterior.

6.6. Resumen

En esta seccion propusimos utilizar la evolucion de curvas basadas en regiones parala deteccion y el seguimiento de CMEs. El metodo desarrollado es un aporte innova-dor en el area de deteccion y seguimiento de CMEs pues se basa en la segmentacionde las CMEs utilizando un modelo estadıstico, mientras que los metodos propuestosanteriormente [RB04] se basan en la deteccion de objetos con velocidad saliente en lasimagenes de los coronografos.

Los problemas que encontramos tiene la segmentacion de las CMEs utilizando elmodelo de competicion son:

La suposicion de que los niveles de gris de las CMEs siguen una distribucionNormal no es valida

El gran solapamiento entre los histogramas de las CMEs y el fondo, lo que generaque el error de clasificacion sea grande

Por ende. utilizamos el metodo de segmentacion propuesto en la Sec. 5.3.3, basadoen el test estadıstico chi-cuadrado y las matrices de co-ocurrencia.

Finalmente, presentamos algoritmos para el calculo de las propiedades de las CMEs.


(a) Imagen observada por el LASCO/C2 a las14.54 con el contorno de una CME debil detec-tada.

(b) Imagen observada por el LASCO/C2 a las15.30 con el contorno de una CME debil detec-tada.

(c) Imagen observada por el LASCO/C2 a las18.30 con el contorno de una CME debil detec-tada.

(d) Imagen observada por el LASCO/C2 a las19.54 con el contorno de una CME debil detec-tada.

Fig. 6.11: Deteccion y seguimiento de CME observado por LASCO/C2, usando el modelo pro-puesto. El mismo CME no pudo ser seguido utilizando el metodo de la seccion ante-rior.


(a) Imagen observada por el LASCO/C2 a las07.31 con el contorno de una CME detectada.

(b) Imagen observada por el LASCO/C2 a las09.54 con el contorno de una CME detectada.

(c) Imagen observada por el LASCO/C2 a las10.54 con el contorno de una CME detectada.

(d) Imagen observada por el LASCO/C2 a las13.54 con el contorno de una CME detectada.

Fig. 6.12: Deteccion y seguimiento de CME observado por LASCO/C2, usando el modelo pro-puesto. El mismo CME pudo ser seguido utilizando el metodo de la seccion anterior.

7. RESULTADOS

En esta seccion comparamos los resultados de deteccion y seguimiento de CMEs denuestro metodo con la lista elaborada por el grupo de expertos del LASCO, disponibleen http://cdaw.gsfc.nasa.gov/CME list/. Si bien el catalogo del LASCO tiene datos demas de 10 anos, nosotros elegimos comparar los CMEs detectados en las imagenes co-rrespondientes al perıodo entre el 1 de Enero del ano 2001 y el 14 de Enero del mismoano. La secuencia de imagenes analizada tiene mas de 800 imagenes individuales, lascuales fueron adquiridas, salvo excepciones, cada 24 minutos. Las imagenes tienen unaresolucion de 512 por 512 pixels. La secuencia completa fue analizada en una PentiumCore Duo en 3 horas.

Los resultados se pueden ver en la Tab. 7.1, la columna CPA es el Central PositionAngle medido en grados, la columna AW es el Angular Width medido en grados. Enla tabla se eliminaron los eventos detectados con ancho angular menor a 14 grados o loque fueron detectados en una sola imagen.

En el periodo entre el 1 de Enero del ano 2001 y el 14 de Enero del mismo ano seregistraron 56 eventos, de los cuales cuatro eventos no fueron detectados por nuestrometodo, pues eran muy debiles. Cuatro eventos fueron detectados por nuestro metodopero no se encuentran en el catalogo del LASCO, posiblemente hayan sido descartadosluego de haberse efectuado un analisis con otros instrumentos. Un evento fue perdidomientras se seguıa debido a que era muy abrupto. Dos eventos fueron descartados de-bido a que eran muy angostos. El AW de un evento fue corrupto debido a perdida defragmentos de imagenes de la secuencia. El AW de otro evento fue corrupto debido aque se confundio con otro evento.

Los resultados arrojan areas de posibles mejoras para el metodo:

Considerar fragmentos faltantes en las imagenes a la hora de evolucionar losCMEs

Mejorar el criterio de cercanıa de CMEs

Integrar informacion de otros instrumentos

Mejorar el esquema de seguimiento para que no sea necesario que los CMEsentre imagen e imagen tengan regiones en comun.

7. RESULTADOS 68

Tab. 7.1: Comparacion de CMEs detectados entre nuestro metodo y el catalogo del LASCO. Lacolumna CPA es el Central Position Angle medido en grados, la columna AW es elAngular Width medido en grados.

Catalogo del LASCO Nuestro metodoFecha y Hora CPA AW Fecha y Hora CPA AW2001/01/01 10:30:31 259 50 2001/01/01 09:30:00 AM 287 492001/01/02 05:54:05 222 49 2001/01/02 05:54:00 AM 220 252001/01/02 08:30:05 261 52 2001/01/02 09:30:00 AM 281 142001/01/02 12:30:05 226 128 2001/01/02 02:30:00 PM 210 412001/01/02 13:54:06 59 41 2001/01/02 01:54:00 PM 71 162001/01/02 17:54:28 152 60 DETECTADO EN UNA SOLA IMAGEN2001/01/02 21:30:10 71 114 2001/01/02 09:30:00 PM 55 522001/01/02 21:54:05 284 113 2001/01/02 10:06:00 PM 285 492001/01/03 04:30:05 192 53 2001/01/03 04:06:00 AM 200 282001/01/03 07:31:49 269 50 2001/01/03 07:31:00 AM 282 362001/01/03 10:54:06 270 40 NO DETECTADO2001/01/03 12:54:05 36 146 2001/01/03 12:30:00 PM 63 702001/01/03 14:30:05 273 35 2001/01/03 02:30:00 PM 275 202001/01/04 01:31:47 74 25 2001/01/04 01:31:00 AM 74 302001/01/04 07:54:08 112 46 2001/01/04 07:54:00 AM 122 212001/01/04 21:54:05 284 28 2001/01/04 09:54:00 PM 281 142001/01/04 23:06:05 69 38 2001/01/04 11:06:00 PM 75 252001/01/05 07:31:49 99 25 2001/01/05 07:31:00 AM 107 16NO PRESENTE EN EL CATALOGO 2001/01/05 11:06:00 AM 265 17NO PRESENTE EN EL CATALOGO 2001/01/05 11:30:00 AM 26 432001/01/05 11:54:05 111 44 2001/01/05 11:54:00 AM 126 212001/01/05 14:30:05 325 25 NO DETECTADO2001/01/05 17:06:05 Halo (BA) 360 2001/01/05 05:06:00 PM HALONO PRESENTE EN EL CATALOGO 2001/01/05 02:06:00 AM 282 32

7. RESULTADOS 69

2001/01/06 08:30:05 263 59 2001/01/06 09:06:00 AM 278 452001/01/06 12:30:06 257 68 2001/01/06 12:30:00 AM 272 612001/01/06 18:06:05 307 33 2001/01/06 06:06:00 PM 309 332001/01/07 04:06:05 298 76 2001/01/07 03:54:00 AM 317 892001/01/07 13:54:06 280 43 2001/01/07 01:54:00 PM 278 412001/01/07 14:54:05 75 47 LO PIERDE2001/01/07 21:30:10 161 60 CONSIDERADO CERCANO2001/01/07 22:30:32 258 37 CONSIDERADO CERCANO2001/01/08 04:30:05 54 134 2001/01/08 04:06:00 AM 80 1102001/01/08 08:54:05 150 27 MUY ANGOSTO2001/01/08 12:54:05 72 58 2001/01/08 12:54:00 AM 92 652001/01/08 17:54:32 34 54 DETECTADO JUNTO CON EL ANTERIOR2001/01/08 21:54:05 72 63 2001/01/08 09:54:00 PM 78 632001/01/09 03:30:05 273 35 2001/01/09 02:30:00 AM 274 372001/01/09 13:31:51 238 37 2001/01/09 01:31:00 PM 242 34NO PRESENTE EN EL CATALOGO 2001/01/09 10:30:00 PM 78 172001/01/09 23:06:05 234 44 2001/01/09 11:06:00 PM 247 612001/01/10 00:54:05 Halo (OA) 360 2001/01/10 12:54:00 PM HALO2001/01/10 08:54:32 239 45 2001/01/10 08:30:00 AM 251 492001/01/10 11:54:05 99 77 2001/01/10 10:54:00 AM 94 752001/01/10 20:30:05 9 14 2001/01/10 07:31:00 PM MUY ANGOSTO2001/01/10 21:30:10 303 66 2001/01/10 08:06:00 PM 304 Corrupto2001/01/11 18:54:05 128 79 2001/01/11 07:31:00 PM 130 Interferencia2001/01/11 22:30:05 57 244 2001/01/11 09:54:00 PM HALO2001/01/12 06:30:05 111 11 2001/01/12 06:30:00 AM 111 142001/01/12 12:54:05 72 92 2001/01/12 12:54:00 PM 92 602001/01/12 17:30:05 103 43 2001/01/12 05:30:00 PM 100 182001/01/13 03:54:08 102 119 2001/01/13 03:54:00 AM 116 1042001/01/13 08:30:05 79 76 2001/01/13 08:06:00 AM 83 1012001/01/14 05:30:07 254 66 NO DETECTADO2001/01/14 06:30:05 327 134 2001/01/14 06:30:00 AM 358 1642001/01/14 09:30:05 191 78 NO DETECTADO

8. CONCLUSIONES Y TRABAJO FUTURO

En este trabajo presentamos un metodo automatico para la deteccion y el segui-miento de CMEs. La deteccion de las mismas es importante debido a que pueden afec-tar los sistemas tecnologicos, de los cuales nos hemos convertido muy dependientes.El metodo propuesto puede detectar y seguir CMEs aun cuando las mismas tienen di-ferentes formas y el contraste con respecto al fondo varie enormemente de una imagena la siguiente.

El metodo de deteccion se basa en evolucionar una curva inicial, mediante la tecnicade conjuntos de nivel, alrededor del disco oclutor. El metodo de seguimiento utiliza elresultado de la segmentacion, de una imagen de la secuencia, como estimacion inicialpara la segmentacion en la siguiente imagen. En ambos casos la evolucion es guiadapor un modelo estadıstico apropiado.

El metodo desarrollado es un aporte innovador en el area de deteccion y segui-miento de CMEs pues se basa en la segmentacion de las CMEs utilizando un modeloestadıstico, mientras que los metodos propuestos anteriormente [RB04] se basan en ladeteccion de objetos con velocidad saliente en las imagenes de los coronografos.

Los resultados expuestos en la Sec. 7 confirman el potencial del metodo y arrojanareas de posibles mejoras:

Considerar fragmentos faltantes en las imagenes a la hora de evolucionar losCMEs

Mejorar el criterio de cercanıa de CMEs

Integrar informacion de otros instrumentos

Mejorar el esquema de seguimiento para que no sea necesario que los CMEsentre imagen e imagen tengan regiones en comun.

Ademas, los metodos propuestos deberıan poder extenderse para procesar imagenesprovenientes de otros instrumentos como el LASCO/C3 o los coronografos de la misionSTEREO. Integrando los datos provenientes de todos los instrumentos de las misionesSOHO y STEREO se deberıa poder crear un sistema confiable para la deteccion y elseguimiento de CMEs.

Otro aporte de la tesis, en el area de segmentacion de imagenes, es la modificacionde las ecuaciones de movimiento de competicion de regiones. En las cuales se propusointroducir el test estadıstico chi-cuadrado, a fin de comparar las distribuciones del vec-tor de caracterısticas dentro de una ventana, para segmentar regiones cuyos vectores

8. CONCLUSIONES Y TRABAJO FUTURO 71

de caracterısticas tengan distribuciones con solapamiento grande. Ademas, las ecua-ciones propuestas, utilizan matrices de co-ocurrencias para representar las texturas delas CMEs.

El enfoque basado en test de hipotesis de nuestro metodo de segmentacion, lo ha-ce atractivo para circunstancias donde se necesita segmentar imagenes y no se tieneinformacion sobre la distribuciones de las regiones, o cuando las distribuciones de lasregiones se encuentran muy solapadas.

El metodo de segmentacion es supervisado y requiere que se estimen los histogra-mas de antemano, esto puede verse como una limitacion de nuestro metodo pues nosiempre es posible. Se podrıa intentar mejorar el metodo para convertirlo en uno nosupervisado.

En los experimentos realizados pudimos comprobar que el metodo de segmenta-cion propuesto, basado en el test estadıstico chi-cuadrado, se comporto mejor que elmodelo parametrico basado en Gaussianas. Posibles lınea de investigacion son reali-zar experimentos con otro tipo de imagenes o comparar los resultados con metodos desegmentacion no parametricos.

Por ultimo, basados en [SK05], presentamos nuevos algoritmos que permiten repre-sentar una region y obtener su contorno de manera eficiente. Utilizando estos algorit-mos planteamos algoritmos de evolucion de curvas. El metodo propuesto fue utilizadoen forma exitosa para evolucionar las curvas en nuestros experimentos. Una posiblemejora futura es plantear algoritmos de evolucion de curvas mas elaborados, basadosen los algoritmos de representacion de regiones.

BIBLIOGRAFıA

[AS95] D. Adalsteinsson and J. A. Sethian, A fast level set method for propagatinginterfaces, Journal of Computational Physics. (1995).

[BHK+95] G. E. Brueckner, R. A. Howard, M. J. Koomen, C. M. Korendyke, D. J.Michels, J. D. Moses, D. G. Socker, K. P. Dere, P. L. Lamy, A. Llebaria,Schwenn Bout, M. V., Simnett R., D. K. G. M., Bedford, and C. J. Eyles,The large angle spectroscopic coronagraph (lasco), Solar Physics (1995),357–402.

[CKS95] Vincent Caselles, Ron Kimmel, and Guillermo Sapiro, Geodesic activecontours, ICCV, 1995, pp. 694–699.

[CLR90] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduc-tion to algorithms, MIT Press, 1990.

[CM02] D. Comaniciu and P. Meer, Mean shift: A robust approach toward featurespace analysis, Pattern Analysis and Machine Intelligence, IEEE Transac-tions on 24 (2002), 603–619.

[CV01] Tony F. Chan and Luminita A. Vese, Active contours without edges., IEEETransactions on Image Processing 10 (2001), no. 2, 266–277.

[DFP95] V. Domingo, B. Fleck, and A. I. Poland, Soho: The solar and heliosphericobservatory, Space Science Reviews 72 (1995), 81–84.

[DHS00] R.O. Duda, P.E. Hart, and D.G. Stork., Pattern classification, 2nd edition,Wiley Interscience, 2000.

[HSD73] R. M. Haralick, K. Shanmugam, and I. Dinstein, Textural features for ima-ge classification, IEEE Transactions On Systems, Man, and Cybernetics(1973).

[KWT88] M. Kass, A. Witkin, and D. Terzopoulos, Snakes: Active contour models,International Journal of Computer Vision 1 (1988), no. 4, 321–331.

[OF03] Stanley Osher and Ronald Fedkiw, Level set methods and dynamic implicitsurfaces, Springer, 2003.

[OS88] Stanley Osher and James A Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations,Journal of Computational Physics 79 (1988), 12–49.

Bibliografıa 73

[PD02] Nikos Paragios and Rachid Deriche, Geodesic active regions: a new para-digm to deal with frame partition problems in computer vision, Journal ofVisual Communication and Image Representation, Special Issue on PartialDifferential Equations in Image Processing, Computer Vision and Compu-ter Graphics (2002), 249–268.

[RB04] E. Robbrecht and D. Berghmans, Automated recognition of coronal massejections (CMEs) in near-real-time data, aap 425 (2004), 1097–1106.

[Rou04] Mikael Rousson, Cue integration and front evolution in image segmenta-tion, Ph.D. thesis, UNIVERSITE DE NICE - SOPHIA ANTIPOLIS, 2004.

[Sap01] Guillermo Sapiro, Geometric partial differential equations and imageanalysis, Cambridge University Press, 2001.

[Set99] J. A. Sethian, Level set methods and fast marching methods: Evolving in-terfaces in computational geometry, fluid mechanics, computer vision, andmaterials science, Cambridge University Press, 1999.

[SK05] Yonggang Shi and William Clement Karl, Real-time tracking using levelsets., CVPR (2), IEEE Computer Society, 2005, pp. 34–41.

[SM00] Jianbo Shi and Jitendra Malik, Normalized cuts and image segmenta-tion, IEEE Transactions on Pattern Analysis and Machine Intelligence 22(2000), no. 8, 888–905.

[Tsc02] David Tschumperle, Pde’s based regularization of multivalued images andapplications, Ph.D. thesis, UNIVERSITE DE NICE - SOPHIA ANTIPO-LIS, 2002.

[VZ03] M. Varma. and A. Zisserman, Texture classification: are filter banks neces-sary?, CVPR03, 2003, pp. 691–698.

[ZLY95] Song Chun Zhu, Tai Sing Lee, and Alan L. Yuille, Region competition:Unifying snakes, region growing, energy/bayes/MDL for multi-band imagesegmentation, ICCV, 1995, pp. 416–.

deteccion y seguimiento de´ eyecciones coronales masivas...

Documents