Tema 2: Registrado de Imágenes basado en Algoritmos ... · esquema de codificación binaria al enfrentarse con imágenes con transformaciones rígidas 3D y 2D, respectivamente z

Tema 2: Registrado de Imágenes basado en Algoritmos Evolutivos y Metaheurísticas

Master en Soft Computing y Sistemas InteligentesCurso: Soft Computing y Visión por Ordenador

Parte I: Registrado de Imágenes mediante Computación Evolutiva

Universidad de Granada

Oscar Cordón García

2/114Soft Computing y Visión por OrdenadorParte I: Registrado de Imágenes mediante Computación Evolutiva Oscar Cordón García

Tema 2: Registrado de Imágenes basadoen Algoritmos Evolutivos y Metaheurísticas

1. Introducción

2. Primeros Modelos e Inconvenientes

3. Modelos Avanzados en el Espacio de la Transformación

4. Modelos en el Espacio de correspondencias (matching)

5. Estudio Comparativo


La Computación Evolutiva (CE) se emplea para resolverproblemas reales que requieren técnicas robustas y flexibles

La visión por computador y la comprensión de imágenesrepresentan algunos de los más desafiantes por su grancomplejidad, centrados en diseñar sistemas concapacidades de comprensión similares a las humanas para:

permitirles percibir el entorno, comprender la informaciónadquirida, identificar patrones, emprender acciones apropiadasy aprender de la experiencia para mejorar futuras actuaciones

Para ello, deben resolverse otros problemas de nivel másbajo, tales como la extracción de características, elmodelado 3D y la clasificación de objetos

2.1. Introducción

1. Introducción



4. Modelos en el Espacio de Correspondencias


CONTENIDO


2.1. Introducción

La aplicabilidad general de los algoritmos evolutivos (AEs)les permite resolver muchas aplicaciones del procesamientode imágenes

Recientemente, hay un gran interés en aplicar AEs al RI:

1. Introducción





CONTENIDO


2.2. Primeros Modelos e Inconvenientes

Los AEs son las técnicas metaheurísticas de mayoraplicación en RI, como demuestra el volumen importante decontribuciones publicadas en las últimas décadas

Dentro de esta familia de métodos, podemos encontrartanto soluciones de alta calidad, como enfoques en los queel AE no se diseña de forma adecuada

Prácticamente todas estas contribuciones están basadas enel enfoque de RI de la búsqueda evolutiva de losparámetros de la transformación

1. Introducción





CONTENIDO



1. Introducción





CONTENIDO

Rotación = {5°, 25°, 0°} Traslación = {2, 0, 1}

f ’

f ´ ≅ f *

Cálculo del punto delmodelo más próximo acada punto de la escena

Evaluar f’

Búsqueda de los mejores parámetros de f(Método de optimización)



Los primeros intentos de resolver el RI mediante técnicasde CE se encuentran a principios de los ochenta

El volumen de la información manejada así como el númerode parámetros que se buscaban prevenían de realizar unabúsqueda exhaustiva de las soluciones

La primera aproximación basada en un AG binario sepropuso en 1984 para imágenes angiográficas 2D:

Fitzpatrick, J., Grefenstette, J., Gucht, D. (1984). Image registration bygenetic search. IEEE Southeast Conference, pp. 460–464, Louisville, EEUU

1. Introducción





CONTENIDO


Desde esta contribución inicial, diversos autores hanresuelto el problema mediante distintos enfoques pero aúnencontramos importantes limitaciones en sus propuestas:

Falta de precisión al abordar el problema: Uso decodificación binaria

Simplificaciones importantes:

• El esquema de AG usado es el original propuesto porHolland en la década de los setenta

• Uso de las transformaciones de registrado más simples:transformaciones rígidas


1. Introducción





CONTENIDO


FALTA DE PRECISIÓN:

El primer problema es el uso de la codificación binaria pararesolver un problema inherentemente de codificación real

Por ello, es necesario equilibrar la magnitud de la transformaciónconsiderada y la precisión de la solución para un determinadonúmero de bits en la codificación

Esto sólo puede permitirse en entornos donde la precisión no esun requisito crítico o donde se conozca a priori el rango de cambiode los parámetros de la transformación

Además, si se intenta obtener una solución más precisaaumentando el número de bits, el tiempo necesario para que elalgoritmo converja aumentará también


1. Introducción





CONTENIDO


Mandava, V. R., Fitzpatrick, J. M., Pickens, D. R. (1989). Adaptive searchspace scaling in digital image registration. IEEE Transactions on MedicalImaging, 8(3):251–262

Por ejemplo, en 1989, Mandava y otros usaron unaestructura de 64 bits para representar una solución con losocho parámetros de una transformación bilineal

Tsang, P. W. M. (1997). A genetic algorithm for aligning object shapes.Image and Vision Computing, 15:819–831

En 1997, Tsang usaba cromosomas de 48 bits para codificartres puntos de prueba como base de la estimación de unafunción de registrado afín 2D


1. Introducción





CONTENIDO


Yamany, S.M., Ahmed, M.N., Farag, A. A. (1999). A new genetic-basedtechnique for matching 3D curves and surfaces. Pattern Recognition,32:1817–1820Chalermwat, P., El-Ghazawi, T. A. (1999). Multi-Resolution ImageRegistration Using Genetics. Intl. Conf. on Image Processing, pp. 452–456

En propuestas más recientes (1999 y 2001) se sigue el mismoesquema de codificación binaria al enfrentarse con imágenes contransformaciones rígidas 3D y 2D, respectivamente

Yamany usa 6 bits por ángulo de rotación (rango de ±31º) y 8 porparámetro de desplazamiento (rango de ±127 unidades),definiendo un cromosoma de 42 bits

Chalermwat usaba 12 bits para el parámetro de rotación 2D(rango de búsqueda de ±20.48º) y 10 bits para los dosparámetros de traslación (±512 pixels), un total de 32 bits


1. Introducción





CONTENIDO


ESQUEMA DE AG CONSIDERADO:

El tipo de AG considerado usa un enfoque generacional, conel conocido método de selección por ruleta), así como eloperador clásico de cruce en un punto y la mutación simplepor intercambio

Es bien sabido que la estrategia de selección mencionadacausa una fuerte presión selectiva (alto riesgo deconvergencia prematura)

Además, es difícil que el cruce en un único puntoproporcione descendientes útiles al destruir los bloquesconstructores con mucha facilidad


1. Introducción





CONTENIDO


USO DE TRANSFORMACIONES RÍGIDAS:

Otro inconveniente importante de muchas contribuciones esque sólo manejan imágenes que han sufrido unatransformación rígidaSimunic, K., Loncaric, S. (1998). A genetic search-based partial imagematching. 2nd IEEE International Conference on Intelligent ProcessingSystems (ICIPS’98), pp. 119–122, Gold Coast, Australia

Chow, C. K. et al. (1998). Medical image registration and modelconstruction using genetic algorithms. Intl. Workshop on Medical Imagingand Augmented Reality (MIAR 2001), pp. 174–179, Hong Kong. IAPR

He, R., Narayana, P. A. (2002). Global optimization of mutual information:application to three-dimensional retrospective registration of magneticresonance images. Comp. Medical Imaging and Graphics, 26:277–292


1. Introducción





CONTENIDO


Estas trasformaciones pueden emplearse en un númerolimitado de aplicaciones prácticas pero éste no es el caso demuchas situaciones reales donde al menos es deseableañadir un escalado uniforme (transformación de similitud)

En el caso 2D, se han realizado diversas propuestas paraconsiderar trasformaciones bilineales o afines ([Mandava,89, Tsang, 97, Matsopoulos, 99]), pero no así en 3DMatsopoulos, G. K. et al. (1999). Automatic retinal image registrationscheme using global optimization techniques. IEEE Transactions onInformation Technology in Biomedicine, 3(1):47–60


1. Introducción





CONTENIDO


Yamany, S.M., Ahmed, M.N., Farag, A. A. (1999). A new genetic-basedtechnique for matching 3D curves and surfaces. Pattern Recognition,32:1817–1820

Es una de las propuestas evolutivas clásicas y másreferenciadas para el RI 3D

Sin embargo, el AG considerado es bastante básico(selección por ruleta, cruce multipunto y mutaciónaleatoria) y sólo maneja transformaciones rígidas

Está basado en codificación binaria: 6 bits por ángulo derotación (rango de ±31º) y 8 por parámetro de traslación(rango de ±127 unidades), cromosoma de 42 bits

2.2. Primeros Modelos e InconvenientesPropuesta de Yamany y Otros

1. Introducción





CONTENIDO


La función objetivo es una variante de maximización del ErrorCuadrático Medio:

Eso sí, en este trabajo se propone una de las estructuras decálculo de correspondencias de primitivas entre imágenes másempleadas en la literatura, el Grid Closest Point (GCP)

2.2. Primeros Modelos e InconvenientesPropuesta de Yamany y Otros

1. Introducción





CONTENIDO


He, R., Narayana, P. A. (2002). Global optimization of mutual information:application to three-dimensional retrospective registration of magneticresonance images. Comp. Medical Imaging and Graphics, 26:277–292

Ligera mejora de la aproximación de Yamany, proponiendo:• un esquema de codificación real,• haciendo uso de un operador de cruce aritmético y un

operador de mutación gausiano,• dentro de un modelo generacional elitista que considera

un mecanismo de reinicialización de la población

La propuesta se enfrenta a transformaciones rígidas 3D, locual no es suficiente para muchos problemas de RI

2.3. Modelos Avanzados en el Espacio de la TransformaciónPropuesta de He y Narayana

1. Introducción



3.1. Propuesta de He y Narayana

3.2. Propuesta de Rouet y Otros

3.3. Propuestas Equilibrio Exploración-Explotación

3.4. Propuesta CHC Cordón y Otros

3.5. Experimentación

3.6. Propuesta Scatter Search Cordón y Otros


…

CONTENIDO



Está basada en una técnica en dos etapas:

primero se realiza una estimación de parámetrospreliminar mediante el AG con codificación real y

después se refinan los resultados con un método dedivisión en rectángulos desarrollando una búsqueda local

En la primera etapa, el rango de los parámetros se fijó en±20 vóxeles a lo largo de las direcciones X e Y, y de ±40vóxeles en la dirección del eje Z

No obstante, el ajuste de los parámetros entre ambasetapas puede ser un punto débil en aplicaciones reales

1. Introducción










…

CONTENIDO



Al trabajar con imágenes de intensidades MRI, la funciónobjetivo es una medida de información mutua a maximizar:

donde A y B son las imágenes modelo y escena transformada,con intensidades ΩA y ΩB, y N es el número de vóxeles en laregión de solapamiento entre ambas imágenes

1. Introducción










…

CONTENIDO


2.3. Modelos Avanzados en el Espacio de la TransformaciónPropuesta de Rouet y Otros

Rouet, J. M., Jacq, J. J., Roux, C. (2000). Genetic algorithms for a robust 3-D MR-CT registration. IEEE Transactions on Information Technology inBiomedicine, 4(2):126–136

El problema de RI afrontado es multimodal, al trabajar conimágenes tridimensionales CT y MRI

Como los escáneres de MR suelen introducir pequeñasdistorsiones en las imágenes, trabajan con unatransformación de registrado elástica global en vez de rígida

Usan la transformación trilineal, al ser lo suficientementesimple para calcularla rápidamente y lo bastante elásticapara modelar las distorsiones de las MRI

1. Introducción










…

CONTENIDO



La transformación trilineal es una envolvente polinómicaconsistente en aplicar un recorte (shearing) en los tres ejes:

donde los ai,j,k, bi,j,k y ci,j,k son los parámetros de latransformación. Como i∈{0,1}, tenemos un total de 24

1. Introducción










…

CONTENIDO



La función objetivo incorpora una habitual medida dedistancia entre los características extraídas de las imágenes:

Las características consideradas son los puntos de lassuperficies aire-piel, S. Son comunes en ambas imágenes,CT y MR, y se extraen mediante un preprocesamiento:

Emplean un mapa de distancias y un cálculo estocásticorobusto para acelerar la obtención del punto más cercano

1. Introducción










…

CONTENIDO



El algoritmo de registrado 3D MRI-CT tiene tres etapas:

Se estiman los parámetros de una trasformación rígidamediante un AG con codificación real

Cruce uniforme, mutación por pequeña modificación local

1. Introducción










…

CONTENIDO



Luego otro AG entero busca las 8 correspondencias de puntosde las imágenes modelo y escena con las que derivar losparámetros de la transformación trilineal global

Cruce simple, mutación uniforme

Para restringir el tamaño del espacio de búsqueda, sólo sepermite asociar un punto de la imagen escena con otro delmodelo si pertenecen a la misma clase de curvatura

Finalmente, se refina la población de salida del paso previomediante un proceso de optimización local aplicado sobre elmejor cromosoma

Se añaden y eliminan progresivamente otrascorrespondencias existentes en los cromosomas de lapoblación para mejorar el valor de la función objetivo

1. Introducción










…

CONTENIDO



Así, esta propuesta brinda una de las aproximaciones máscompletas al problema de RI mediante AGs1. Introducción










…

CONTENIDO



No obstante, identificamos algunos puntos débiles:

Equilibrio diversidad-convergencia: Necesario para un buencomportamiento de cualquier AG. Usan una técnicadesconocida en CE denominada latin squares

El éxito de la segunda etapa del algoritmo depende de unadefinición precisa de la clase de curvatura en cada punto,información que es difícil de obtener en el caso desuperficies no estructuradas

El uso de operadores genéticos simples (como el cruceuniforme) en un AG con codificación real no es la mejoropción incluso si se pretende mejorar la eficiencia

1. Introducción










…

CONTENIDO


2.3. Modelos Avanzados en el Espacio de la TransformaciónPropuestas que Mejoran el Equilibrio Exploración-Explotación del AE

Como en cualquier metaheurística, el rendimiento de losAGs depende del equilibrio exploración - explotación

La acción de los operadores genéticos está enfrentada:

Selección: induce la explotación, define una presión selectiva(refuerzo de la selección de los mejores individuos).

Mutación: introduce diversidad aleatoria

Cruce: depende del caso considerado (el descendientepertenece o no a la misma región de los padres)

Diversidad útil: conseguir las ventajas derivadas de ambos

1. Introducción










…

CONTENIDO


AGs multimodales o con nichos: dividen la población en subpoblaciones que evolucionan en paralelo para explorar simultáneamente diferentes zonas del espacio

Métodos evolutivos de RI considerados:

AG básico con codificación binaria y mejoras a [Yamany,99]

AG con codificación real ([He, 02]) y operadores orientados al equilibrio diversificación-convergencia

AGs multimodales (con codificación binaria y real)


1. Introducción










…

CONTENIDO


Operadores genéticos:

Estrategia de selección: orden lineal y muestreo universalestocástico de Baker

Operador de cruce:Codificación binaria: cruce clásico en dos puntosCodificación real: BLX-α

Operador de mutación:Codificación binaria: mutación uniformeCodificación real: mutación aleatoria

Codificación binaria y real:

αxαy αz Δx ΔzΔy S


COMPONENTES COMUNES:1. Introducción










…

CONTENIDO

Rotación Traslación Escalado



Función Objetivo:1. Introducción










…

CONTENIDO

• E es la función “parte entera”• Ndentro_rejilla es el número de puntos escena dentro de la rejilla tras

aplicar T• Ne es el número de puntos de la imagen escena• T(yi) es el resultado de transformar el punto yi de la escena. GCP

devuelve el punto más cercano a T(yi) en la imagen modelo


CHC: AE clásico con un equilibrio muy adecuado entreexploración y explotación

Combinación de una estrategia de selección con altapresión selectiva y de varios elementos inductores dediversidad

Componentes del algoritmo:• Selección elitista• Operador de cruce altamente disgregador (HUX)• Mecanismo de prevención de incesto• Proceso de reinicialización

2.3. Modelos Avanzados en el Espacio de la TransformaciónPropuesta basada en CHC de Cordón y Otros

1. Introducción










…

CONTENIDO


Selección Elitista: Selecciona los N mejores cromosomasentre padres e hijos

Los N mejores elementos encontrados hasta elmomento permanecerán en la población actual.

Cruce Uniforme (HUX): Intercambia exactamente lamitad de los alelos que son distintos en los padres

Garantiza que los hijos tengan una distancia Hammingmáxima a sus dos padres


1. Introducción










…

CONTENIDO


Prevención de Incesto: Se forman N/2 parejas decromosomas y sólo se cruzan aquellas que difieren enun cierto número de bits (umbral de cruce d)

El umbral se inicializa a L/4 (L es la longitud delcromosoma). Si durante un ciclo la población nocambia, se le resta 1 a d

Reinicialización: Cuando d es menor que cero, lapoblación se reinicializa manteniendo el mejor

CHC no aplica el operador de mutación


1. Introducción










…

CONTENIDO


t = 0d = L / 4Inicializar (P(t)); Evaluar (P(t))REPETIR

t = t + 1C(t) = Emparejar (P(t-1))C’(t) = Recombinar (C(t))Evaluar (C’(t))P(t) = Seleccionar (C’(t), P(t-1))SI (P(t) = P(t-1)) ENTONCES

d = d – 1SI (d < 0) ENTONCES

Reinicializar (P(t))d = r · (1.0 – r) · L

FINHASTA (condición de parada = VERDAD)


1. Introducción










…

CONTENIDO



Cordón, O., Damas, S., y Santamaría, J. (2006). Feature-based imageregistration by means of the CHC evolutionary algorithm. Image and VisionComputing, 22:525–533

Extensión de CHC para codificación real: Se mantiene laestructura original, empleando los mismos componentes

La prevención de incesto y el cruce deben adaptarse:• La similitud entre los padres se mide usando la métrica de

Hamming (conversión binaria)• El cruce se evita si la distancia entre padres es menor que “d”• La reinicialización se lleva a cabo cuando d≤0• Se usa el cruce BLX-α en lugar del HUX, permitiendo así que

este operador tenga un comportamiento tan “diversificador”como se desee

1. Introducción










…

CONTENIDO


Imag

en“P

inoc

ho”

Imag

en“D

ragó

n”

Imágenes 3D consideradas

2.3. Modelos Avanzados en el Espacio de la TransformaciónExperimentación y Análisis de Resultados

1. Introducción










…

CONTENIDO


Imagen “Queso” (Escena) Imagen “Cerebro” (Escena)


Transformaciones consideradas


1. Introducción










…

CONTENIDO


• Evaluación de RI:

f (xi) = [ - Ce · s · R · t · Ce ] · xi


1. Introducción










…

CONTENIDO



1. Introducción










…

CONTENIDO



1. Introducción










…

CONTENIDO



1. Introducción










…

CONTENIDO


• Análisis de resultados

ICP es superado por todas las propuestas evolutivas

El comportamiento de CHC es el mejor, con diferencia

Los resultados de CHC con codificación real siempre son mejores que los obtenidos con codificación binaria

Los resultados más pobres son los de los AGs básicos


1. Introducción










…

CONTENIDO


TR 1

REG(TR 1)


1. Introducción










…

CONTENIDO


REG(TR 2)

REG(TR 3)

REG(TR 4)


1. Introducción










…

CONTENIDO


ESCENA

MO

DE

LOREG(TR 1)


1. Introducción










…

CONTENIDO


RE

G(T

R 2

)

REG(TR 4)


1. Introducción










…

CONTENIDO

RE

G(T

R 3

)


ESCENA

MODELO

REG(TR 1)


1. Introducción










…

CONTENIDO


RE

G(T

R 2

)REG(TR 4)


1. Introducción










…

CONTENIDO

RE

G(T

R 3

)


Scatter Search: AE que potencia la combinación de un conjunto reducido (RefSet) de soluciones «elite» de gran calidad

2.3. Modelos Avanzados en el Espacio de la TransformaciónPropuesta basada en Scatter Search de Cordón y Otros

1. Introducción










…

CONTENIDO



Cordón, O., Damas, S., Santamaría, J. (2006b). A Fast and AccurateApproach for 3D Image Registration using the Scatter Search EvolutionaryAlgorithm. Pattern Recognition Letters, 27(11):1191–1200

• Representación: Vector de parámetros con codificación real

• Función objetivo:

Error geometría Control factor escalado

α Axisx Axisy Axisz tx ty tz s

Transformación f de similitud

1. Introducción










…

CONTENIDO


• GCP: Estructura de indexación espacial para acelerar elcálculo del punto más próximo en la función objetivo


1. Introducción










…

CONTENIDO


• Generador de Diversidad:uso de una aleatorización controlada según una memoria de frecuencias

• Mejora: búsqueda local estocástica y adaptativa de Solis&Wets


1. Introducción










…

CONTENIDO


• Generación de Subconjuntos:todas las parejas posibles de soluciones de RefSet

• Combinación: BLX-α

• Actualización de RefSet:reemplazo estático según calidad de la solución


1. Introducción










…

CONTENIDO



I1 I2 I3 I4

• Imágenes médicas 3D (repositorio Brainweb)

Imágenes MRIs 3D

Segmentación 3D

Extracción de características: Líneas de cresta 3D

583 puntos 393 puntos 348 puntos 248 puntos

Millones de datos

1. Introducción










…

CONTENIDO


*

= 16 instancias RI

4 escenarios de RI(según naturaleza de imagen)

Transformación desimilitud (f * = Ti)

(según desalineación)

• Instancias de RI abordadas (pares de imágenesdiferentes):


1. Introducción










…

CONTENIDO


• Métodos del estado del arte abordando el RI en elespacio de los parámetros de la transformación

• GAYamany [Yamany, 99]

• GAHe [He, 02]

• CHCbin y CHCreal [Cordón et. al, 06]

• SSp [Cordón et. al, 06b]

• Criterio de parada:

Máximo de tiempo: 20 segundos para todos ellos

• Número de ejecuciones: 15


1. Introducción










…

CONTENIDO


• Evaluación de RI:

f (xi) = [ - Ce · s · R · t · Ce ] · xi


1. Introducción










…

CONTENIDO


• Resultados experimentales (escenario I1 Vs. Ti(I2))


1. Introducción










…

CONTENIDO




1. Introducción










…

CONTENIDO




1. Introducción










…

CONTENIDO




1. Introducción










…

CONTENIDO


• Resultados experimentales (V)


1. Introducción










…

CONTENIDO


• Resultados experimentales (VI)


1. Introducción










…

CONTENIDO


• Análisis de resultados (I)

Los métodos con codificación real son los que ofrecenel mejor rendimiento

SSp es el método que consigue en 15 de las 16instancias el menor valor mínimo de ECM

SSp logra en 7 de las 16 instancias el menor valor medio de ECM y empata con CHCReal en las 9 restantes


1. Introducción










…

CONTENIDO


• Análisis de resultados (II)

Instancia

GAYamany


1. Introducción










…

CONTENIDO

SSp


2.4. Modelos en el Espacio de Correspondencias

1. Introducción




4.1. Propuesta ES de Luck y Otros

4.2. Propuesta ILS RI 2D y 3D de Cordón y Otros


4.4. Propuesta Scatter Search de Cordón y Otros



CONTENIDO

f ’

Método numérico

f ´ ≅ f *


Enfriamiento Simulado: Metaheurística que extiende a la búsquedalocal clásica, permitiéndole aceptar soluciones peores que la actualpara salir de óptimos locales

2.4. Modelos en el Espacio de CorrespondenciasPropuesta basada en ES de Luck y otros

1. Introducción










CONTENIDO


Luck, J. P., Little, C. Q., Hoff, W. (2000). Registration of Range DataUsing a Hybrid Simulated Annealing and Iterative Closest Point Algorithm.IEEE Intl. Conf. on Robotics and Automation (ICRA’00), pp. 3739–3744

Estrategia híbrida de RI con dos etapas:

1. Se aplica un algoritmo ICP con regla de rechazo de falsascorrespondencias (descarte de los emparejamientos quesuperan un cierto umbral de distancia calculado a priori)

2. Un algoritmo de enfriamiento simulado basado en elenfoque de la transformación trata de optimizar la soluciónobtenida, trabajando en un espacio de búsqueda reducido


1. Introducción










CONTENIDO


La función objetivo se basa en el Error Cuadrático Mediopero considera un criterio robusto para no considerar loserrores parciales de los emparejamientos incorrectos:

donde di es la distancia entre el punto del modelo y el de laescena transformada y wi es un peso de la correspondencia:

El umbral es la mediana de las distancias al cuadrado, conlo que hasta el 50% de los emparejamientos pueden serincorrectos sin afectar significativamente a la medida


1. Introducción










CONTENIDO


Los autores consideran un máximo de dos iteraciones delas dos etapas anteriores

El diseño del método trata de solucionar el problema conlos óptimos locales ayudando al proceso de búsqueda local(ICP) con la aplicación de una estrategia de búsquedaglobal (ES)


1. Introducción










CONTENIDO


Iterated Local Search: Metaheurística que extiende a la búsquedalocal clásica, envolviéndola en un proceso iterativo que genera nuevospuntos de arranque mediante perturbaciones progresivas de la mejorsolución generada

COMIENZOS0 = GenerarSoluciónInicials*= BúsquedaLocal(s0)REPETIR

s’ = Perturbación (s*,memoria)s*’ = BúsquedaLocal (s’)s* = CriterioDeAceptación(s*,s*’,memoria)

HASTA satisfacer condición de paradaFIN

1. Introducción










CONTENIDO

2.4. Modelos en el Espacio de CorrespondenciasPropuesta RI 2D y 3D basada en ILS de Cordón y Otros


Así, ILS busca mejorar los resultados de una búsqueda localbásica, escapando de óptimos locales mediante la iteración


1. Introducción










CONTENIDO


Cordón, O., Damas, S. (2006c). Image Registration with Iterated LocalSearch. Journal of Heuristics, 12:73–94

• Representación: permutación que representa la asignaciónde puntos 3D entre las imágenes escena y modelo

• El grado de desalineación entre las imágenes no influyeen el proceso de búsqueda

1. Introducción










CONTENIDO



• Algoritmo BúsquedaLocal:

• Permite obtener una solución completa al problema

• Correspondencia entre puntos ⇒ permutación

• Estimación del registrado por mínimos cuadrados

• Ventaja: distinto nº de puntos escena y modelo

• Operador de vecino: intercambio clásico

• Uso de información heurística para guiar la búsqueda:esqueleto en 2D y curvatura en 3D

1. Introducción










CONTENIDO



En 2D:Variante del mejor ⇒ Criterio de parada: el mejor vecino detodo el vecindario no es mejor que la solución actualFunción objetivo:

( )[ ]∑∑= =Θ

++⋅+⋅+Θ−−=Θ1 2

1

22

1

·1,,,

25.075.0·||)(||),,,(minN

i

ji

N

j

ijstM

TZInfLonEMedTPtoYsRtXMstME ωω

( )∑∑= =Θ

Δ+Δ+Θ−−=Θ1 2

1

2122

1

·1,,,

·||)(||),,,(minN

i

ji

N

j

ijstM

kkYsRtXMstME ωω

En 3D:Variante del 1er mejor ⇒ Criterio de parada: la búsqueda seestanca o se alcanza un número máximo de iteracionesFunción objetivo:

1. Introducción










CONTENIDO



GenerarSoluciónInicial: permutación aleatoria de tamaño n

Perturbación: intercambio aleatorio de las posiciones de losvalores de una sublista seleccionada de forma aleatoria detamaño: Parte_Entera(n/a)

CondiciónDeParada: el algoritmo termina cuando se alcanzaun número máximo de iteraciones

1. Introducción










CONTENIDO



ααααβχ

Imagen “Pico” (Escena)

Imagen “Pico” (Modelo)


2.4. Modelos en el Espacio de CorrespondenciasExperimentación y Análisis de Resultados (2D)

1. Introducción










CONTENIDO



1. Introducción










CONTENIDO


Imagen “Pico” 3ª Transformación

Transformación a estimar: Rotación=180º, Esc. 0.5


1. Introducción










CONTENIDO


Imagen “Queso” Imagen “Cerebro”


Transformaciones consideradas


Transformación 1 Transformación 2

1. Introducción










CONTENIDO


• Comparación con otros esquemas de búsqueda:

• MSLS (Búsqueda multiarranque)

• Métodos del estado del arte abordando el RI en elespacio de correspondencias:

• I-ICP [Liu, 04]

• ICP+SA [Luck y otros, 00]


1. Introducción










CONTENIDO


• Medidas de Calidad:

• Error Cuadrático Medio (ECM)

• Porcentaje de emparejamientos correctos (%)

• Criterio de parada: Máximo de iteraciones:

• ILS y MSLS: (20*2500,50*1000) (máximo númerode iteraciones del bucle externo y la búsqueda local)

• I-ICP (40) e ICP+SA (40+[30*50])

• Número de ejecuciones: 10 (salvo I-ICP)


1. Introducción










CONTENIDO


• Resultados experimentales (escenario Queso Vs. T1(Queso))


1. Introducción










CONTENIDO


• Resultados experimentales (escenario Queso Vs. T2(Queso))


1. Introducción










CONTENIDO


• Resultados experimentales (escenario Cerebro Vs. T1(Cerebro))


1. Introducción










CONTENIDO


• Resultados experimentales (escenario Cerebro Vs. T2(Cerebro))


1. Introducción










CONTENIDO


• Resultados experimentales (ILS Vs. I-ICP)


1. Introducción










CONTENIDO


• Resultados experimentales (ILS Vs. ICP+SA)


1. Introducción










CONTENIDO



• La información heurística (curvatura) es necesaria paraobtener resultados de calidad ((w1,w2)=(0.1,0.9))

• ILS mejora a MSLS en todos los casos, tanto en valoresmínimos como medios

• En el conjunto de ambos problemas, los mejoresresultados de ILS se obtienen con 20 × 2500 iteraciones

• Como es habitual, los resultados de ICP son muypobres. El método no estima correctamente las rotaciones

• ILS también supera a ICP+SA en todos los casos


1. Introducción










CONTENIDO



Tr. 1

Tr. 2


ICP ILS

1. Introducción










CONTENIDO


Imagen Escena y Modelo

(transformación Tr. 1) Estimación de registrado (ILS)


• Análisis de resultados (III)1. Introducción










CONTENIDO


• Análisis de resultados (IV)


ICP ILS

Tr. 1

Tr. 2

1. Introducción










CONTENIDO


Cordón, O., Damas, S., Martí, R., Santamaría, J. (2008). Scatter Search forthe 3D Point Matching Problem in Image Registration. INFORMS Journal ofComputing, 20(1):55-68

• Representación: permutación que representa la asignaciónde puntos 3D entre las imágenes escena y modelo

• El grado de desalineación entre las imágenes no influyeen el proceso de búsqueda

2.4. Modelos en el Espacio de CorrespondenciasPropuesta basada en Scatter Search de Cordón y Otros

1. Introducción










CONTENIDO


• Función objetivo:

Error geometría

Error información heurística


1. Introducción










CONTENIDO


• Generador de Diversidad:algoritmo voraz aleatorizadocon información heurística del problema

• Mejora: búsqueda local del primer mejor• Aplicación sistemática del operador de intercambio• Selección inteligente del siguiente movimiento

Diseño avanzado de RefSet:«Dos capas» [Laguna, 03]


1. Introducción










CONTENIDO


• Generación de Subconjuntos:todas las parejas posibles de soluciones de RefSet

• Combinación: PMX vs. Voto

PMX

• Actualización de RefSet:esquema de reemplazo estáticosegún calidad y diversidad Diseño avanzado de RefSet:

«Dos capas» [Laguna, 03]


1. Introducción










CONTENIDO


• Los mismos escenarios (imágenes de Brainweb ytransformaciones) considerados en el espacio de losparámetros

• Métodos del estado del arte abordando el RI en elespacio de búsqueda de correspondencias

• Basados en ICP: I-ICP [Liu, 04]

• Hibridaciones: ICP+SA [Luck, 00]

• Basados en metaheurísticas: ILS [Cordón y Damas, 06c]

• Basados en AEs: SSm [Cordón y Damas, 07]

2.4. Modelos en el Espacio de CorrespondenciasExperimentación y Análisis de Resultados

1. Introducción










CONTENIDO


• Criterio de parada:

Máximo de iteraciones: I-ICP (40) e ICP+SA (40+[20*50])

Máximo de tiempo: ILS y SSm, ambos con 20 segundos

• Número de ejecuciones:

15 para ICP+SA, ILS y SSm

1 para ICP (método determinístico)


1. Introducción










CONTENIDO




1. Introducción










CONTENIDO




1. Introducción










CONTENIDO




1. Introducción










CONTENIDO




1. Introducción










CONTENIDO




1. Introducción










CONTENIDO



SSm logra el menor valor medio de ECM en el total de instancias de RI consideradas

SSm consigue el menor valor mínimo en 15 de las 16 instancias

I-ICP es el método de RI que ofrece el rendimiento más bajo debido a la pronunciada desalineación considerada


1. Introducción










CONTENIDO


• Análisis de resultados (III)


1. Introducción










CONTENIDO

Instancia

SSm

I-ICP


2.5. Estudio comparativo entre Enfoques

EXPERIMENTACIÓN 1: MRI 3D

• Resultados experimentales (I)1. Introducción





5.1. Experimentación MRI

5.2. Experimentación CT

CONTENIDO



• Los métodos que operan en el espacio de búsqueda de latransformación ofrecen una mayor efectividad y precisión

• El aumento de la complejidad del problema afecta alrendimiento de los métodos del espacio de búsquedade las correspondencias

• Análisis de resultados (I)1. Introducción







CONTENIDO



• SSm es el método de RI más efectivo y preciso de entre los que trabajan en el espacio de búsqueda de las correspondencias

• Globalmente, SSp se muestra como el método más eficaz y preciso abordando las instancias de RI consideradas

• Análisis de resultados (II)1. Introducción







CONTENIDO



• Análisis de resultados (III)1. Introducción







CONTENIDO

SSm

SSp


2.5. Estudio comparativo entre EnfoquesEXPERIMENTACIÓN 2: RI TAC 3D

• Imágenes médicas CT-3D de pacientes reales (ambasdiferentes y con transformaciones locales)

512 puntos

412 puntos

1. Introducción







CONTENIDO



• Las mismas transformaciones consideradas hasta ahora

• Mejores métodos de entre los anteriores:

• Espacio de correspondencias: SSm, I-ICP e ICP+SA

• Espacio de la transformación: SSp, GAHe y CHCreal

• Criterio de parada, número de ejecuciones y evaluacióndel RI: los considerados anteriormente

1. Introducción







CONTENIDO



• Resultados experimentales

1. Introducción







CONTENIDO




• Globalmente, los métodos de RI del espacio de latransformación se muestran como los más robusto segúnel menor valor mínimo y medio de ECM

• SSp es el método más efectivo y preciso al lograr elmenor valor medio de ECM en 3 de las 4 instancias

• SSm ofrece el mejor rendimiento de los métodos queoperan en su espacio de búsqueda

1. Introducción







CONTENIDO




SSm ICP+SA I-ICP

SSp GAHe CHCReal

1. Introducción







CONTENIDO

T1

Documents

Tema 2: Registrado de Imágenes basado en Algoritmos ... · esquema de codificación binaria al enfrentarse con imágenes con transformaciones rígidas 3D y 2D, respectivamente z