Download Registrado de imágenes.

Universidad de Granada
Tema 1: Introducción al Problema de
Registrado de Imágenes
Master en Soft Computing y Sistemas Inteligentes
Curso: Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
Tema 1: Introducción al Problema de
Registrado de Imágenes
1. Formulación y Aplicaciones
2. Taxonomía. Transformaciones de Registrado
3. Resolución del Registrado de Imágenes como un Problema
de Optimización
4. Enfoques de Matching y Parámetros de la Transformación
5. El Algoritmo ICP. Problemática y Variantes
2/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
z
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
z
Imagen 2D: función f(x,y), donde x e y son coordenadas
espaciales y la amplitud de f en cualquier par (x,y) se
conoce como intensidad o nivel de gris
Imagen digital: si x e y son discretas y finitas (compuesta
por un número finito de elementos: píxeles)
Procesamiento de imágenes digitales: tratamiento de
imágenes digitales mediante el ordenador
5. El Algoritmo ICP.
Problemática y
Variantes
3/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
1. Formulación y
Aplicaciones
Píxel: abreviatura de la expresión inglesa Picture Element
(Elemento de Imagen), es la unidad más pequeña o
primitiva elemental de las imágenes digitales 2D
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
4/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
1. Formulación y
Aplicaciones
Vóxel: extensión del concepto de píxel a las imágenes
digitales 3D
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
5/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
IMÁGENES 3D:
z Imágenes digitales 3D volumétricas: compuestas por un
conjunto de cortes o “rebanadas” (slices).
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
z
Imágenes de rango: imagen 2D + valor de intensidad
de cada píxel representa valor de profundidad
5. El Algoritmo ICP.
Problemática y
Variantes
6/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
ÁREAS DE LA VISIÓN POR ORDENADOR:
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
z
z
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
7/40
z
Nivel bajo o procesamiento: operaciones primitivas
(reducción de ruido, etc.). Entrada y salida son imágenes
Nivel medio o análisis: segmentación, clasificación, etc.
La entrada suele ser imagen, la salida, atributos de ésta
Nivel alto o visión por ordenador: implica “dar sentido” a
los objetos reconocidos y desarrollar funciones cognitivas
relacionadas con la visión
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
1. Formulación y
Aplicaciones
APLICACIONES DE LA VISIÓN POR ORDENADOR (I)
z Teledetección: tratamiento de la imagen vía satélite
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
z
Medicina: planificación cirugía, diagnóstico, tratamiento
z
Tráfico: control viario
5. El Algoritmo ICP.
Problemática y
Variantes
8/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
APLICACIONES DE LA VISIÓN POR ORDENADOR (II)
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
z
z
Robótica: sistemas de navegación
Sistemas de seguridad: reconocimiento de huellas, caras,
sistemas de vigilancia de edificios, detección explosivos
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
z
9/40
Control de calidad: inspección y verificación de motores,
cristales, circuitos impresos, madera, alimentos, etc.
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
1. Formulación y
Aplicaciones
z
Registrado de imágenes (RI): tarea encargada de hacer
coincidir/superponer dos imágenes similares en un mismo
sistema de coordenadas
2. Taxonomía.
Transformaciones de
Registrado
¿ PROBLEMA ?
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
10/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Imágenes en sistemas de
coordenadas diferentes
Relación de correspondencia
desconocida
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
1. Formulación y
Aplicaciones
APLICACIONES DEL RI (I)
z Planificación de intervenciones quirúrgicas
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
11/40
z
Integración de imágenes: multimodalidad, 2D/3D, etc.
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
1. Formulación y
Aplicaciones
APLICACIONES DEL RI (II)
z Teledetección: mosaicos para cartografía
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
z
Reconstrucción de piezas: en industria, arqueología,
antropología forense, etc.
5. El Algoritmo ICP.
Problemática y
Variantes
12/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
Producción científica en RI en los últimos años:
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
consulta: “image” AND (“registration” OR “alignment”)
13/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
z
Registrado de imágenes (RI): tarea encargada de hacer
coincidir/superponer dos imágenes similares en un mismo
sistema de coordenadas
Componentes de un sistema de RI:
3. Resolución del RI
como un Problema de
Optimización
Imágenes escena (Ie ⊂ R2/R3) y modelo (Im ⊂ R2/R3)
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
Transformación (f: R2/R3 Æ R2/R3)
5. El Algoritmo ICP.
Problemática y
Variantes
14/40
Métrica de similitud (F)
Optimizador (búsqueda de f óptima)
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.1. Formulación y Aplicaciones
CONTENIDO
z
Esquema genérico de un método de RI:
z
Formalización teórica:
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
15/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.2. Taxonomía. Transformaciones de Registrado
CONTENIDO
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones
de Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
16/40
z
Taxonomías centradas en la imagen
z
Basados en intensidades / Basados en características
z
Dimensionalidad 2D – 2D, 3D – 3D, 2D – 3D, etc.
z
Sistema adquisición: monomodalidad / multimodalidad
z
Información de referencia: extrínsicos / intrínsecos
z
RI médico: Intrasujeto / intersujeto
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.2. Taxonomía. Transformaciones de Registrado
CONTENIDO
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones
de Registrado
z
Existen distintos grupos de transformaciones geométricas f
z
El grupo lineal general: rotaciones, traslaciones, etc.
z
Otras transformaciones no lineales: elásticas, fluidos, etc
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
17/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.2. Taxonomía. Transformaciones de Registrado
CONTENIDO
1. Formulación y
Aplicaciones
Original
Traslación
Esc. No Unif.
Recorte
Rotación
Escalado Unif.
2. Taxonomía.
Transformaciones
de Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
18/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Proyección
Elástica
Oscar Cordón García
1.2. Taxonomía. Transformaciones de Registrado
CONTENIDO
z
Diversos grupos dentro de las transformaciones lineales:
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones
de Registrado
z
z
z
3. Resolución del RI
como un Problema de
Optimización
Transformaciones rígidas: rotación + traslación
Similitudes: rotación + traslación + escalado uniforme
Similitudes extendidas: rot. + traslación + Sx + Sy + Sz
SIMILITUDES
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
19/40
Rotación
f (R3ÆR3) =
Traslación
α Axisx Axisy Axisz
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Escalado
tx ty
tz s
Oscar Cordón García
1.3. Resolución del RI como Problema de Optimización
CONTENIDO
z
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
z
3. Resolución del RI
como un Problema
de Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
20/40
La formulación del problema es análoga a la de otros de
optimización en los que se precisa la selección de la
configuración más apropiada de un conjunto de opciones
Algoritmos de resolución:
• Exactos: encuentran la solución óptima. Imposible de aplicar
en todos los problemas (NP-duros)
• Aproximados: consiguen soluciones próximas a la óptima en
tiempo aceptable
Métodos de RI clásicos
atrapados en óptimos locales
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.3. Resolución del RI como Problema de Optimización
CONTENIDO
z
Limitaciones de los métodos de RI clásicos
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema
de Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
21/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.3. Resolución del RI como Problema de Optimización
CONTENIDO
z
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
z
Concepto de metaheurística: familia de algoritmos
aproximados basada en la extensión de métodos heurísticos
básicos mediante su inclusión en un proceso iterativo
Propiedades:
3. Resolución del RI
como un Problema
de Optimización
z
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
z
No exigen hacer uso de funciones derivables
z
Intentan evitar el estancamiento en óptimos locales
z
No son específicas de un problema concreto
5. El Algoritmo ICP.
Problemática y
Variantes
22/40
Son estrategias que guían el proceso de búsqueda con el
objetivo de explorar eficientemente el espacio de soluciones
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.3. Resolución del RI como Problema de Optimización
CONTENIDO
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
z
Algoritmos evolutivos: algoritmos metaheurísticos basados
en principios inspirados en la genética de las poblaciones
naturales para evolucionar sobre soluciones
3. Resolución del RI
como un Problema
de Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
23/40
Son los algoritmos metaheurísticos que han abordado
el problema de RI con mayor éxito
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.3. Resolución del RI como Problema de Optimización
CONTENIDO
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema
de Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
24/40
Algoritmos Genéticos (AGs)
EMPEZAR
t ← 0. Inicializar P(0). Evaluar P(0)
REPETIR MIENTRAS (NO condición de parada)
INICIO
Seleccionar P’(t) desde P(t)
Cruzar y mutar P’(t) con prob. Pc y Pm
Reemplazar P(t) con P’(t)
Evaluar P(t)
t ← t+1
FIN
Devolver el mejor individuo de P(t-1)
FIN
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.4. Enfoques del Matching y de la Transformación
CONTENIDO
z
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
z
Espacios de búsqueda:
z
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
z
5. El Algoritmo ICP.
Problemática y
Variantes
z
25/40
Enfoques de resolución: definir un optimizador con su
función objetivo y su esquema de codificación de soluciones
Correspondencia de primitivas de imagen: búsqueda
del mejor conjunto de emparejamientos para estimar
f * a partir de él
Transformación de registrado: búsqueda de
directamente en el espacio de los parámetros de f
f*
Métodos de RI clásicos: suelen realizar una búsqueda
monótona descendente
atrapados en óptimos locales
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.4. Enfoques del Matching y de la Transformación
CONTENIDO
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
Método numérico
3. Resolución del RI
como un Problema de
Optimización
f´≅f*
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
26/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
f’
Oscar Cordón García
1.4. Enfoques del Matching y de la Transformación
CONTENIDO
z
1. Formulación y
Aplicaciones
La incorporación de información específica (heurística) del
problema redunda en la mejora del rendimiento del proceso
de búsqueda:
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
z
Reducción drástica del espacio de búsqueda
z
Orientación inteligente de la búsqueda
Objetivo: extraer características de la forma relevantes
como información para el registrado:
z
z
27/40
z
2D: información derivada del esqueleto
3D: información derivada de la curvatura
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.4. Enfoques del Matching y de la Transformación
CONTENIDO
z
Concepto de esqueleto: analogía de Blum
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
z
28/40
Esqueleto objeto 2D: formado por curvas unidas que
acaban o en puntos intersección, o en puntos frontera
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.4. Enfoques del Matching y de la Transformación
CONTENIDO
z
Inducir una partición del objeto en regiones con significado
z
Definición de atributos basándonos en esta partición:
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
z
z
29/40
Tamaño relativo de una parte del esqueleto,
Variación del eje medio en una parte del esqueleto, …
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.4. Enfoques del Matching y de la Transformación
CONTENIDO
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
30/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.4. Enfoques del Matching y de la Transformación
CONTENIDO
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
z
Extracción de un conjunto de líneas de cresta en
imágenes 3D, formadas por puntos característicos 3D
con atributos curvatura mínima y máxima, k1 y k2,
respectivamente
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
31/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.4. Enfoques del Matching y de la Transformación
CONTENIDO
1. Formulación y
Aplicaciones
Búsqueda de los mejores parámetros de f
(Método de optimización)
2. Taxonomía.
Transformaciones de
Registrado
f´≅f*
3. Resolución del RI
como un Problema de
Optimización
Rotación = {5°, 25°, 0°}
Traslación = {2, 0, 1}
Evaluar f’
Cálculo del punto del
modelo más próximo a
cada punto de la escena
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
32/40
f’
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.4. Enfoques del Matching y de la Transformación
CONTENIDO
Búsqueda de los mejores parámetros de f
1. Formulación y
Aplicaciones
(Método de optimización)
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de z
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
Métodos clásicos de optimización: fuerte componente local
z
Con/sin estimación de gradiente: Gradiente-conjugado,
Quasi-Newton, Simplex, Powell, ...
Desalineaciones entre imágenes
atrapados en óptimos locales
33/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.5. El Algoritmo ICP. Problemática y Variantes
CONTENIDO
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
34/40
ƒ Besl, P. J. y McKay, N. D. (1992). A method for registration of 3D shapes.
IEEE Trans. on Pattern Analysis and Machine Intelligence, 14:239–256
z
Iterative Closest Point (ICP): iterar los tres pasos siguientes
hasta alcanzar un umbral de tolerancia:
z
z
z
Hallar las correspondencias entre puntos escena y
modelo mediante la regla de asignación del más próximo
Calcular los parámetros de la transformación
registrado mediante mínimos cuadrados
de
Aplicación de la transformación estimada a la escena y
cálculo del ECM
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.5. El Algoritmo ICP. Problemática y Variantes
CONTENIDO
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
z
ICP: algoritmo determinista. Considera como criterio de
correspondencia la «asignación del punto más próximo»
Eficiente y preciso, pero no garantiza la convergencia al
óptimo cuando las imágenes tienen cierto grado de desalineación
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
ICP
5. El Algoritmo ICP.
Problemática y
Variantes
35/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.5. El Algoritmo ICP. Problemática y Variantes
CONTENIDO
z
Limitaciones de ICP:
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
z
z
z
Los estados iniciales de la puesta en correspondencia
global juegan un papel crucial
Sensibilidad a la presencia de datos aberrantes
El coste de un ajuste local puede ser alto incluso si hay
un porcentaje bajo de oclusión
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
BuenaICP
Estimación
36/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.5. El Algoritmo ICP. Problemática y Variantes
CONTENIDO
1. Formulación y
Aplicaciones
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
ƒ Zhang, Z. (1994). Iterative point matching for registration of free form
curves and surfaces. Intl. Journal of Computer Vision, 13(2):119–152
z
Variante de ICP de Zhang: estudio de la distribución de las
distancias para enfrentarse a puntos aberrantes, oclusiones,
etc.
z
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
z
5. El Algoritmo ICP.
Problemática y
Variantes
z
37/40
Técnica robusta para descartar algunos emparejamientos
analizando las estadísticas de las distancias
La distancia entre cada pareja de puntos establecida
razonablemente debería ser similar
Para ello, en cada iteración se propone actualizar un
parámetro de distancia máxima DImax permitida
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.5. El Algoritmo ICP. Problemática y Variantes
CONTENIDO
1. Formulación y
Aplicaciones
Pi
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
Qj
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
38/40
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.5. El Algoritmo ICP. Problemática y Variantes
CONTENIDO
z
1. Formulación y
Aplicaciones
Además Zhang considera por primera vez el uso de una
estructura de datos (el KD-Árbol) que acelera el cálculo del
punto más próximo
2. Taxonomía.
Transformaciones de
Registrado
z
3. Resolución del RI
como un Problema de
Optimización
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
5. El Algoritmo ICP.
Problemática y
Variantes
39/40
En un KD-Árbol 3D, el
primer corte (rojo) divide
el conjunto de puntos
(blanco) en dos, cada
uno de los cuales se
divide entonces (verde)
en dos subconjuntos. Por
último, cada uno de los
cuatro subconjuntos se
divide (azul) en otros
dos
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García
1.5. El Algoritmo ICP. Problemática y Variantes
CONTENIDO
1. Formulación y
Aplicaciones
ƒ Liu, Y. (2004). Improving ICP with easy implementation for free form
surface matching. Pattern Recognition, 37(2):211–226
z
2. Taxonomía.
Transformaciones de
Registrado
3. Resolución del RI
como un Problema de
Optimización
I-ICP se centra en la propuesta de un método con reglas de
rechazo de falsas correspondencias en base a:
z Restricción
de colinealidad: para cada posible
correspondencia {xi,yi}, los puntos xi, yi y el centro
óptico O deben aproximarse a ser colineales
4. Enfoques del
Matching y de los
Parámetros de la
Transformación
Se prefiere
emparejar x
con yi’’ por
colinealidad
5. El Algoritmo ICP.
Problemática y
Variantes
z
40/40
Restricción de proximidad: la distancia entre los puntos
{xi,yi}, debe ser mínima,
Soft Computing y Visión por Ordenador
Parte I: Registrado de Imágenes mediante Computación Evolutiva
Oscar Cordón García