Dpto. Tecnología Electrónica
Jason Oscar Merry
Dirigido por: Cristina Urdiales García
Departamento Tecnología Electrónica
ETSI Telecomunicación
Universidad de Málaga
Algoritmo de resolución automática de puzzles
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
INDICE
IntroducciónIntroducción
Descripción del programaDescripción del programa
ResultadosResultados
Conclusiones y trabajo futuroConclusiones y trabajo futuro
PreguntasPreguntas
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
INTRODUCCIÓNObjetivo del proyecto Aplicación de la visión artificial que interpreta imágenes digitales de forma inteligente y automática.
Simulación del comportamiento humano para la resolución automática de puzzles.
Usuario solo tiene que especificar la imagen que va a procesar, sus dimensiones y el número de piezas.
Lenguaje C: portabilidad del código.
Razón del estudio de puzzles Aplicación práctica de las investigaciones realizadas por el DTE en el campo de la visión artificial.
Permite probar la exactitud y prestaciones de los algoritmos.
Fácilmente adaptable a tareas de ensamblaje donde requieren el reconocimiento y selección de componentes.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Caracterización
Imagen original
Puzzle resuelto
Procesado
Resolución
DESCRIPCIÓN DEL PROGRAMA
Estructura facilita su adaptación a otras tareas.
Imágenes sometidas a tres etapas de proceso:
1. Procesado de la imagen1. Procesado de la imagen
2. Caracterización de las piezas2. Caracterización de las piezas
3. Resolución del puzzle3. Resolución del puzzle
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
Proceso perceptivo:interpretación de la imagen para diferenciar cada uno de los objetos.
1.1. Compresión
1.2. Segmentación
1.3. Detección de objetos
1.4. Obtención de los contornos
Proceso se repite si no logra diferenciar todos los objetos: auto-calibración.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.1. Compresión de la imagen
Reducción del volumen de datos.
Factor de compresión: 2, 4, 8..
Auto-calibración.
Cálculo de promedios de factor x factor píxeles.
Compresión en color frente al blanco y negro.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.1. Compresión de la imagen
Color o solo un componente R, G, B.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.2. Segmentación de la imagen
Diferenciación de regiones de tamaño variado y distribución aleatoria. Cada objeto en una región.
Características estáticas y dinámicas.
Filosofía de segmentación:
• Detección de bordes
• Detección de áreas homogéneas.
- Local o global.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.2. Segmentación de la imagen
Imagen única que contiene un número conocido de objetos sobre un fondo uniforme.
Algoritmo: segmentación estática: umbralización.
• Obtención del color de fondo.
• Comparación píxel a píxel: binarización.
• Punto clave: elección del umbral adecuado.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.3. Detección de objetos
Selección de objetos de interés y la determinación de sus ‘bounding-boxes’.
Dos técnicas empleados en serie:
• Descarte por dispersión:
- Se eliminan aquellos píxeles considerados objeto que estén aislados sobre el fondo.
• Descarte por área:
- Etiquetado para diferenciar los objetos restantes.
- Obtención del área.
- Eliminación si no supera área mínima.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.3. Detección de objetos
Descarte por dispersión
Presencia de ruido en el fondo:
- Píxeles aislados
- Manchas
Píxeles aislados eliminados
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.3. Detección de objetos
Descarte por área. Etiquetado de los objetos
4 falsos objetos debidos a un fondo no uniforme.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.3. Detección de objetos
Descarte por área. Definición de ‘bounding-boxes’.
Los X marcan la ubicación de los objetos eliminados
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.4. Obtención de los contornos
Conversión de coordenadas.
• Imagen comprimida -> imagen original.
Obtención de los contornos. Cuatro etapas en serie:
• Eliminación de píxeles aislados.
• Reducción de huecos.
• Diferenciación contorno – relleno.
• Limpieza del contorno.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.4. Obtención de los contornos
Reducción de huecos.
Eliminación de píxeles aislados.
Objeto tras la segmentación.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Segmentación
Imagen original
Imagen segmentada
Compresión
Detección
Contornos
1. Procesado de la imagen
1.4. Obtención de los contornos Diferenciación contorno – relleno.
Limpieza del contorno.
El contorno se queda con anchura de un píxel.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Interpretación
Contornos de las piezas
Lados diferenciados
Caracterización
2. Caracterización de las piezas
Objetivo: diferenciar los cuatro lados de las piezas y ofrecer información sobre su forma.
2.1. Caracterización Basada en curvatura. Evaluación de pendiente.
• Baja carga computacional.
• Facilidad para comparar similitud.
• Resistente a transformaciones.
2.2. Interpretación de las funciones de curvatura
Dividir la función de curvatura en los cuatro segmentos correspondientes a cada lado.
Localización y estudio de los puntos significativos.
• Lados separados por puntos de esquina principales.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Interpretación
Contornos de las piezas
Lados diferenciados
Caracterización
2. Caracterización de las piezas
2.1. Caracterización Pasos previos: punto de inicio y número total de puntos.
Algoritmo de cálculo de función de curvatura:
1. Estimación del código de cadena incremental
2. Suma de k códigos cadena incrementales.
3. Localización del ángulo asociado en tabla ‘look-up’.
4. Normalización -> independiente a la orientación.
5. Filtrado -> reducción de efectos del ruido.
-100
-80
-60
-40
-20
0
20
40
60
80
100
CU
RV
AT
UR
A
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Interpretación
Puntos significativos
Puntos de esquina
Obtención de lados
Contornos de las piezas
Lados diferenciados
Caracterización
2. Caracterización de las piezas
2.2. Interpretación de las funciones de curvatura
Obtención de los puntos significativos.
• Búsqueda de máximos y mínimos.
• Umbralización: valor elevado.
• Candidatos para la etapa posterior.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Interpretación
Puntos significativos
Puntos de esquina
Obtención de lados
Contornos de las piezas
Lados diferenciados
Caracterización
2. Caracterización de las piezas
2.2. Interpretación de las funciones de curvatura
Cálculo de los puntos de esquina principales.
Basado en las características comunes a todas las piezas, emplea dos procesos:
• Descarte por signo y geometría.
Esquina principal: dos tramos rectos unidos en un punto significativo negativo y que formaban un ángulo de entre 70 y 90°.
• Filtrado por posición.
4 esquinas principales, puntos extremos de los lados.
Bandas verticales y horizontales.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Interpretación
Puntos significativos
Puntos de esquina
Obtención de lados
Contornos de las piezas
Lados diferenciados
Caracterización
2. Caracterización de las piezas
2.2. Interpretación de las funciones de curvatura
Obtención de los lados.
• Cada lado esta delimitado por dos esquinas principales.
• División de la función de curvatura en 4 tramos correspondientes a cada lado.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzleUsando la información de curvatura de cada lado, clasifica las piezas, los empareja y monta el puzzle en pantalla.
3.1. Clasificación de los lados
3.2. Emparejamiento de las piezas
3.3. Presentación de resultados Emparejamiento
Presentación
Puzzle resuelto
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
3.1. Clasificación de los lados
Para cada lado estudia los puntos significativos de mayor magnitud que no sean una esquina principal. Si los dos mayores son:
• Negativos => existe un hueco (lado hembra)
• Positivos => existe un pincho (lado macho)
• No existen => lateral o plano
También guarda su valor y ubicación.
Ventajas:
Emparejamiento
Presentación
Puzzle resuelto
Rápido descarte de candidatos en el emparejamiento.
Fácil comparación de los lados.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
3.2. Emparejamiento de las piezas
Algoritmo:
1. Cuenta los lados que requieren pareja.
2. Emparejamiento de piezas de tipo lateral y esquina => resolución del borde.
3. Resolución del interior. Emparejamiento
Presentación
Puzzle resuelto
Proceso auto-corrector: si falla el emparejamiento calcula la pareja en función de las parejas vecinas.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzleResolución del borde
Emparejamiento
Presentación
Puzzle resuelto
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzleResolución del interior
Emparejamiento
Presentación
Puzzle resuelto
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
Búsqueda de pareja. Pruebas del candidato:
• Es de otra pieza y no tiene ningún lado emparejado con la pieza objeto.
• Lado no está emparejado y es de tipo contrario.
• Si es pieza de tipo lateral comprueba orientación del lado.
• Compara longitud, valor de máximos y su ubicación.
• Si hay más de un candidato, compara el color.
Orientación del lateral
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
Cálculo de parejas
• Cuando búsqueda de pareja fracasa.
• Estudio de las parejas de las piezas vecinas que sí han sido emparejadas.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
Pasos:
1. Calcula dimensiones del puzzle resuelto.
2. Coloca la primera esquina en la esquina superior izquierda.
3. Monta resto del borde en mismo orden que cuando se emparejaron.
4. Monta interior por filas o columnas según se monto primero la fila superior o lateral izquierdo del borde.
3.3. Presentación de resultados
Genera imagen del puzzle montado en función de la información de emparejamiento. Aplica rotación y traslación.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
3.3. Presentación de resultados
Rotación y traslación
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
3.3. Presentación de resultados
Rotación y traslación
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
3.3. Presentación de resultados
Rotación y traslación
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
3.3. Presentación de resultados
Rotación y traslación
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
3.3. Presentación de resultados
Rotación y traslación
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
3.3. Presentación de resultados
Rotación y traslación
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
3.3. Presentación de resultados
Rotación y traslación
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
3.3. Presentación de resultados
Rotación y traslación
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
Lados diferenciados
Clasificación
3. Resolución del puzzle
Emparejamiento
Presentación
Puzzle resuelto
3.3. Presentación de resultados
Rotación y traslación
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
RESULTADOS
Resolución de un puzzle real de 20 piezas
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
CONCLUSIONES Y TRABAJO FUTURO
Funcionamiento rápido y correcto pero requiere condiciones favorables de iluminación, y no admite determinadas formas de pieza.
Mejoras:
• Mayor inmunidad a los efectos de la iluminación.
• Mayor libertad en cuanto a la forma de los objetos.
Trabajo futuro:
• Programa ejecutado en un sistema dotado de un procesador, sistema de visión y brazo de robot.
• Ampliación de posibles aplicaciones para el reconocimiento de otros objetos.
Dpto. Tecnología Electrónica
Algoritmo de resolución automática de puzzles
PRUEBAS DEL SISTEMA
Ejecución del programa
Parámetros de entrada:
Nombre de la imagen (puzzpig.raw)
Dimensiones (ancho=1600, alto=1200)
Número de piezas (20)
Modo de prueba: (0)
• 0 Sin pruebas
• 1, 2 o 3 Pruebas para solo una etapa
• 4 Pruebas en todas las etapas
• 5 Modo demo (ejecución pausada)