PDF de programación - Visión de alto nivel: Interpretación de dibujos de líneas mediante comparación de grafos

UNIVERSIDAD DE MURCIA

FACULTAD DE INFORMÁTICA

SISTEMAS Y
PROYECTOS

INFORMÁTICOS

Visión de alto nivel:

Interpretación de dibujos de líneas

mediante comparación de grafos

Autor:

Ginés García Mateos

Profesor tutor:

Alberto Ruiz García

Visión de alto nivel:

Interpretación de dibujos de líneas
mediante comparación de grafos.

INDICE

RESUMEN DEL PROYECTO IV

1. INTRODUCCIÓN. MOTIVACIÓN DEL PROYECTO. 1

1.1. LA VISIÓN ARTIFICIAL.
1.2. ETAPAS EN EL PROCESO DE VISIÓN.
1.3. LA VISIÓN DE ALTO NIVEL.
1.4. INTERPRETACIÓN DE DIBUJOS DE LÍNEAS.

1
2
3
3

2. OBJETIVOS DEL PROYECTO. 5

3. DESARROLLO DEL PROYECTO. 6

3.1. ESTRUCTURA GLOBAL DEL PROCESO.
3.2. LA ETAPA DE BAJO NIVEL: DETECCIÓN DE BORDES.

3.2.1. INTRODUCCIÓN. MOTIVACIÓN PARA EL USO DE IMÁGENES DE BORDES.
3.2.2. MÉTODOS BÁSICOS DE DETECCIÓN DE BORDES.
3.2.3. EL OPERADOR DE CANNY.

3.3. LA ETAPA DE MEDIO NIVEL: DETECCIÓN DE SEGMENTOS.

3.3.1. INTRODUCCIÓN.
3.3.2. ACERCAMIENTOS AL PROBLEMA DE DETECCIÓN DE SEGMENTOS.
3.3.3. EL ALGORITMO EMH PARA DETECCIÓN DE SEGMENTOS.

3.4. LA ETAPA DE ALTO NIVEL.

3.4.1. INTRODUCCIÓN. LA VISIÓN DE ALTO NIVEL EN EL DOMINIO 3D.
3.4.2. MÉTODOS DE INTERPRETACIÓN DE DIBUJOS DE LÍNEAS.

3.4.2.1. Técnicas de etiquetado de nodos.
3.4.2.2. Técnicas de comparación de grafos.

3.4.3. ESTRUCTURA DEL PROCESO DE ALTO NIVEL DESARROLLADO.
3.4.4. GRAFOS ASOCIADOS AL DIBUJO DE LÍNEAS.

3.4.4.1. Grafos de vértices.
3.4.4.2. Grafos de aristas.
3.4.4.3. Grafo de aristas dirigido y atribuido.

3.4.5. CREACIÓN DE GRAFOS.

3.4.5.1. Propiedad de coterminación.
3.4.5.2. Propiedad de colinearidad.
3.4.5.3. Propiedades de convergencia y terminación.
3.4.5.4. Heurísticas de acabado.

3.4.6. COMPARACIÓN DE GRAFOS.

3.4.6.1. El problema de la comparación de grafos.
3.4.6.2. Comparación por búsqueda en el espacio de estados.
3.4.6.3. Comparación mediante técnicas de optimización no lineal.
3.4.6.4. El algoritmo de asignación graduado.

6
8
8
9
11
12
12
13
14
16
16
17
18
20
22
22
23
24
25
27
29
30
31
32
33
33
34
35
35

ii

3.4.6.5. Coste de comparación de enlaces.
3.4.6.6. Tratamiento del subisomorfismo.
3.4.6.7. El coste de comparación total.
3.4.6.8. Interpretación mediante comparación.

3.4.7. ALINEAMIENTO Y VERIFICACIÓN DE HIPÓTESIS.

3.4.7.1. El problema de la comparación estructural.
3.4.7.2. Alineamiento mediante combinación de vistas.
3.4.7.3. Aplicación del alineamiento.
3.4.7.4. Verificación de la hipótesis.

4.1. INTEGRACIÓN DE ETAPAS DE PROCESAMIENTO.
4.2. EXTENSIONES Y APLICABILIDAD PRÁCTICA.

4.2.1. DETECCIÓN DE BORDES.
4.2.2. DETECCIÓN DE SEGMENTOS.
4.2.3. INTERPRETACIÓN DE LA ESCENA.

4.3. CONCLUSIONES FINALES.

39
41
42
43
44
44
45
46
47

49
50
50
50
51
51

4. CONCLUSIONES. 49

5. BIBLIOGRAFÍA. 53

ANEXO A. DISEÑO E IMPLEMENTACIÓN DEL SISTEMA. 54

A.1. INTRODUCCIÓN.
A.2. ESTRUCTURA DE MÓDULOS DEL SISTEMA.
A.3. DISEÑO DE CLASES.

Clase TPunto.
Clase TLinea.
Clase TEnlace.
Clase TGrafo.
Clase TEmparej.
Clase TModelo.

54
55
56
56
57
57
57
57
58

ANEXO B. PRUEBAS REALIZADAS. 59

B.1. INTRODUCCIÓN.
B.2. DETECCIÓN DE BORDES.

Tiempos de ejecución de los operadores.
Calidad de los operadores.

B.3. DETECCIÓN DE SEGMENTOS.

Tiempos de ejecución del algoritmo.
Calidad de los dibujos de líneas obtenidos.
B.4. INTERPRETACIÓN DE DIBUJOS DE LÍNEAS.

Tiempo de ejecución del proceso de creación de grafos.
Tiempo de ejecución del proceso de comparación de grafos.
Resultados de la creación de grafos.
Bondad de la medida de comparación de grafos.

59
60
60
61
62
62
62
63
63
63
64
65

iii

Resumen del proyecto

En este proyecto se estudia y desarrolla de forma completa un sistema de visión, enfocado
hacia la interpretación de escenas tridimensionales, dentro de un entorno controlado. A partir de las
imágenes de entrada, serán extraídas las líneas correspondientes a los bordes de los objetos en la
escena, dando lugar a las descripciones conocidas como dibujos de líneas. La característica funda-
mental del acercamiento propuesto es la interpretación a través de una comparación de grafos, que
contendrán las relaciones más relevantes entre las líneas de borde de la escena.

Se ha considerado de manera especial la integración del proceso de interpretación, propia-
mente dicho, con todos los niveles previos de procesamiento, cuyo objetivo es la obtención del
dibujo de líneas asociado a la escena. En concreto, el sistema de visión está compuesto por tres
etapas (bajo, medio y alto nivel), actuando de forma coordinada a un nivel simbólico creciente.

El propósito de la etapa de bajo nivel es encontrar una descripción de la imagen original en
función de los bordes de intensidad. Estos bordes dividen la imagen en zonas cuyos lugares corres-
pondientes en la escena se espera que sean superficies con características de profundidad homogé-
neas (es decir, las caras de los objetos). La aplicación de esta etapa es relativamente sencilla y
automática, obteniéndose en la mayoría de los casos resultados bastante buenos. Con esto se consi-
gue que el proceso sea invariante a color, intensidad y a las características de iluminación de la
escena. Por contra, el proceso será muy sensible en caso de existir de texturas muy destacadas,
marcas, dibujos o pliegues suaves en los objetos.

El dibujo de bordes será recibido por el proceso de medio nivel, en el cual se realizará una
agrupación de los puntos de borde en segmentos de líneas rectas. Idealmente el dibujo de líneas de
la escena contiene la misma información que el dibujo de bordes pero a un mayor nivel descriptivo.
Los puntos individuales dejan de ser importantes, fijándonos en las agrupaciones de los mismos en
estructuras lineales. Puesto que los bordes delimitan las zonas con propiedades homogéneas, una
línea de borde describirá una arista de alguno de los objetos en la escena y una unión entre líneas
corresponderá a un vértice del objeto. El algoritmo de detección de segmentos utilizado, el algorit-
mo EMH, es capaz de obtener buenos resultados en un tiempo razonable. Además dispone de cierta
dinámica que le permite adaptarse rápidamente a pequeñas variaciones de la imagen de entrada. El
proceso de detección de segmentos impone una fuerte restricción sobre el dominio del problema:
sólo serán admitidos objetos poliédricos, es decir formados por caras planas.

Por último, en la etapa de alto nivel se lleva a cabo el proceso de interpretación propia-
mente dicho. Como un paso intermedio entre el medio y el alto nivel, se transformará la descrip-
ción de la escena una estructura de grafo, en la que se extraen las propiedades relevantes del dibujo
de líneas. Después se realizará el paso central de la interpretación: la comparación de grafos, entre
el grafo asociado al dibujo de líneas de la escena y los grafos que representan modelos. El resultado
será una hipótesis de interpretación, en la que se describirán los objetos reconocidos en la escena y
las posiciones en las que se encuentran. Esta hipótesis deberá ser verificada de una manera geomé-
tricamente más precisa, mediante una técnica de alineamiento, con la cual es posible obtener la
posición y orientación tridimensional de los objetos en la escena.

En la estructura de grafos utilizada, los nodos representan los segmentos del dibujo de lí-
neas y los arcos relacionan los segmentos unidos en el dibujo. De esta forma, el grafo es un reflejo
exacto de la disposición de las líneas en el dibujo. La creación de los grafos a partir de los dibujos
de líneas consistirá en un proceso de búsqueda de relaciones no accidentales entre los segmentos.
En este paso, algunos errores de los procesos anteriores podrán ser eliminados, quedándonos con la
información relevante y no redundante, más adecuada para la posterior comparación.

La comparación de grafos ha sido un problema ampliamente estudiado, debido a su utilidad
potencial, pero con una complejidad computacional de orden exponencial. Para resolverlo se utiliza
un algoritmo desarrollado recientemente, que enfoca la comparación a través del conocido proble-

iv

ma de asignación. Este algoritmo dispone de un bajo orden de complejidad, obteniendo en muchos
casos resultados óptimos o próximos al óptimo. Además dispone de un parámetro que permite
controlar la velocidad de ejecución.

El algoritmo trabaja con unos costes de comparación básicos, dependientes del problema
tratado. Para el caso de los grafos asociados a los dibujos de líneas, ha sido realizado en este pro-
yecto un estudio exhaustivo de cuales deberían ser estos costes. Se llega a la conclusión de que un
nodo está definido en función de sus relaciones con otros nodos, siendo el coste básico de la com-
paración de grafos el coste de comparación entre tipos de uniones de segmentos.

Finalmente, se ve la necesidad de comprobar la hipótesis de interpretación, obtenida en la
comparación de grafos, considerando las propiedades tridimensionales de los objetos de forma más
precisa. Esto se realiza con los conocidos métodos de alineamiento, cuya efecto es similar a la pro-
yección de un modelo 3D en un dibujo 2D. La comparación a bajo nivel de la imagen alineada con
la original permitirá decidir si la escena observada puede ser considerada