Tesis de Maestría - CENIDET · 2020. 7. 7. · Tesis de Maestría Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 1 TABLA DE CONTENIDO ÍNDICE DE FIGURAS

cenidet

Centro Nacional de Investigación y Desarrollo Tecnológico

Departamento de Ciencias Computacionales

TESIS DE MAESTRÍA EN CIENCIAS

Análisis de Algoritmos de Correspondencia para Visión Estéreo

presentada por

Ma. del Refugio Ofelia Luna Sandoval Lic. en Matemáticas por la Universidad Autónoma de Zacatecas

como requisito para la obtención del grado de:

Maestría en Ciencias en Ciencias de la Computación

Director de tesis: Dr. José Ruiz Ascencio

Co-Director de tesis:

M. C. Andrea Magadán Salazar

Jurado: Dr. Juan Manuel Rendón Mancha – Presidente

Dr. Andrés Blanco Ortega – Secretario M. C. Jorge Alberto Fuentes Pacheco – Vocal

Dr. José Ruiz Ascencio – Vocal Suplente

Cuernavaca, Morelos, México. 29 de noviembre de 2011

Dedicatoria

Esta tesis está dedicada, con todo cariño, a mi hijo:

I k i A l v a r a d o L u n a

Agradecimientos

Agradezco a:

Dios por permitir que esta experiencia figurara en mi destino.

Al Consejo Nacional y Tecnología (CONACyT) por el apoyo económico brindado durante estos

dos años de estudio.

Al Centro Nacional de Investigación y Desarrollo Tecnológico (CENIDET) y a su personal por

haberme permitido formar parte de esta institución.

A mis asesores: la M.C. Andrea Magadán Salazar y el Dr. José Ruiz Ascencio por su paciencia y su

sabia dirección durante todo el desarrollo de este proyecto.

A mis revisores: el Dr. Juan Manuel Rendón Mancha, el Dr. Andrés Blanco Ortega y el M.C. Jorge

Alberto Fuentes Pacheco por sus importantes observaciones y sugerencias.

Al Dr. René Santaolaya Salgado por su apoyo en la comprensión del paradigma orientado a objetos.

Al Dr. Gregory Dudek de la Universidad de McGill por facilitarme el repositorio de AQUA.

A la planta docente del CENIDET por su dedicación y empeño en la impartición de sus clases.

A mis compañeros Jorge Alberto Fuentes Pacheco y Alejandro Pech Can quienes durante toda mi

estancia de Maestría fueron un apoyo académico y moral.

A mis compañeros Sergio Alejandro González Segura y Cruz Lázaro Gómez Olán por su

instrucción en el uso de las librerías de Open CV.

Al Sistema Integral de Becas para la Educación Superior por el apoyo económico que me otorgó

para llevar a cabo mi proceso de titulación.

A todos mis amig@s del CENIDET porque fue un gusto coincidir con ustedes en esta vida.

A la Universidad Autónoma de Zacatecas (UAZ) y a quien la dirige, el Dr. Francisco Javier

Domínguez Garay, por otorgarme permiso para realizar mis estudios de posgrado.

Al H. Consejo de Unidad de la Facultad de Matemáticas de la UAZ por darme su autorización para

que me pudiera actualizar.

A la Directora de la Facultad de Matemáticas de la UAZ: M.C. Judith Alejandra Hernández

Sánchez por brindarme todo su apoyo de manera incondicional.

A mi inolvidable compañero M.C. Alberto García Aguilar (q.e.p.d.) por brindarme su aval para

continuar preparándome. Pero sobre todo, le agradezco, por haber sido siempre ser un excelente

ejemplo a seguir.

A mis compañeros: M.C. Elvira Borjón Robles, M.A.T.I. Mónica del Rocío Torres Ibarra y M.C.

Leopoldo Trueba Vázquez, por ser piezas clave para que este sueño se pudiera realizar.

A mi madre Ma. del Refugio Sandoval Rodríguez por enseñarme que para conseguir las cosas es

necesario esforzarse y ser disciplinado.

A mi hijo Iki quien día con día estuvo alentándome para que mi ánimo no decayera.

A Rolando Alvarado Flores y Gilberto Luna Sandoval porque durante mi ausencia se han hecho

cargo de las personas que yo tanto amo.

A todos ellos ¡MUCHAS GRACIAS!

Resumen

En esta tesis de maestría se evaluó el desempeño de doce algoritmos de correspondencia en

imágenes provenientes de entornos acuáticos y terrestres. Este análisis se llevó a cabo a través de la

comparación de la precisión y del tiempo que arrojaron estos algoritmos cuando se aplicaron a

imágenes muestra, las cuales se seleccionaron tanto de un conjunto de imágenes texturizadas como

de un conjunto de imágenes estructuradas. La clasificación del conjunto total de imágenes, en

texturizadas o estructuradas, se realizó a través de una forma que se propuso en este trabajo.

Los doce algoritmos de correspondencia fueron el resultado de la composición de algunos

algoritmos de detección de características destacadas, búsqueda y emparejamiento que se

identificaron en la literatura.

Como resultado de este trabajo de tesis se presentó un estudio exploratorio que facilita identificar la

predominancia del tipo de escena, texturizada o estructurada, inmersa en un entorno acuático o

terrestre. Asimismo este estudio posibilita establecer, por lo menos para la muestra analizada,

relaciones entre el tipo de escena y la respuesta del algoritmo de correspondencia aplicado.

Abstract

In this master’s thesis the performance of twelve correspondence algorithms has been evaluated on

images from aquatic and terrestrial environments. This analysis was conducted by comparing the

precision and the time it took these algorithms when applied to a sample of images that were

selected as a set of textured images and a set of structured images. The classification of the entire

set of images into textured or structured, is performed using a way proposed in this thesis.

Twelve correspondence algorithms were the result of the composition of salient feature detectors

with search and matching algorithms reported in the literature.

As a result of this thesis presented an exploratory study that enables us to identify the predominance

of the type of scene, textured or structured, immersed in a water or land. This study also enables us

to establish, at least for the sample, relationships between the type of scene and the response of the

matching algorithm applied.

Tesis de Maestría

Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 1

TABLA DE CONTENIDO

ÍNDICE DE FIGURAS 4

ÍNDICE DE TABLAS 7

ACRÓNIMOS 10

GLOSARIO 11

1. LINEAMIENTOS DEL TRABAJO DE TESIS 14

1.1. Introducción 14

1.2. Objetivo de la tesis 15

1.3. Metodología de solución 16

1.4. Organización del documento 18

2. ESTADO DEL ARTE 19

2.1. Propiedades de un detector de características 20

2.2. Detectores de características utilizados en esta tesis 21

2.3. Evaluación de algunos detectores de características 22

2.4. Artículos que hacen mención de algunas técnicas de correspondencia 26

2.5. Elementos a considerar en la elección de un algoritmo de correspondencia 28

2.6. Algoritmos de emparejamiento utilizados en la tesis 31

3. DESCRIPCIÓN DE LOS ALGORITMOS UTILIZADOS 34

3.1. Algoritmos de detección de características 34

3.1.1. Harris 34

3.1.2. Star 35

3.1.3. MSER 36

3.2. Algoritmo de búsqueda de puntos 37

3.2.1. Algoritmo de búsqueda Épsilon-bola 37

Tesis de Maestría


3.3. Algoritmos de emparejamiento de puntos 38

3.3.1. Suma de diferencias absolutas (SAD) 38

3.3.2. Correlación de varianza normalizada (VNC) 39

3.3.3. Algoritmo para descriptor de color 39

3.3.4. Algoritmos para descriptores de textura 40

3.4. Algoritmo de desambiguación 44

4. DISEÑO E IMPLEMENTACIÓN DEL SISTEMA 45

4.1. Introducción 45

4.2. Arquitectura del sistema 45

4.3. Especificaciones técnicas 47

5. DESCRIPCIÓN DE LOS REPOSITORIOS 48

5.1. Descripción del repositorio AQUA 51

5.2. Descripción del Repositorio Exteriores_Urbanos 52

5.3. Descripción del repositorio Exteriores_Naturales1 54

5.4. Descripción del Repositorio Exteriores_Naturales2 56

5.5. Descripción del repositorio Exteriores_Naturales3 57

5.6. Descripción del repositorio Interiores1 59

5.7. Descripción del repositorio Interiores2 60

6. EXPERIMENTOS Y RESULTADOS 66

6.1. Diseño de experimentos 66

6.2. Metodología de evaluación de los algoritmos 67

6.3. Inicialización de parámetros del sistema 67

6.4. Resultados de los experimentos 68

6.4.1. Resultados obtenidos en la muestra de entorno acuático 69

6.4.2. Resultados obtenidos en la muestra del entorno terrestre 76

6.4.3. Resumen de resultados 101

7. CONCLUSIONES Y TRABAJOS A FUTURO 109

Tesis de Maestría


7.1. Conclusiones 109

7.3. Aportaciones 110

7.4. Trabajos futuros 111

REFERENCIAS 112

ANEXOS 116

Anexo A. Atributos y métodos de la superclase Correspondencia 116

Anexo B. Salidas de SPSS Statistics 19 124

Anexo C. Tablas de resultados de los experimentos 133

Tesis de Maestría


Índice de figuras

Figura 1.1. Diagrama de bloques de la Metodología. ...................................................................... 16

Figura 2.1. Clasificación de los métodos estéreo en métodos densos y métodos dispersos (Cyganek,

2009). ............................................................................................................................ 25

Figura 2.2. Clasificación de los métodos estéreo en métodos locales y métodos globales (Cyganek,

2009). ............................................................................................................................ 26

Figura 3.1. Cuadrados superpuestos que simulan un círculo. .......................................................... 35

Figura 3.2. Identificación de puntos a través del algoritmo Épsilon-bola. ....................................... 37

Figura 3.3. Los 8 vecinos del píxel de referencia X de acuerdo al ángulo utilizado en el cálculo

de la matriz de coocurrencia para un desplazamiento d=1. .......................................... 41

Figura 4.1. Diagrama de clases. ....................................................................................................... 46

Figura 4.2. Diagrama de flujo para la ejecución del proceso de correspondencia. .......................... 47

Figura 5.1. Primera parte de la gráfica de pertenencia a conglomerados del repositorio AQUA. ... 51

Figura 5.2. Segunda parte de la gráfica de pertenencia a conglomerados del repositorio AQUA. .. 52

Figura 5.3. Primera parte de la gráfica de pertenencia a conglomerados del repositorio

Exteriores_Urbanos. ..................................................................................................... 53

Figura 5.4. Segunda parte de la gráfica de pertenencia a conglomerados del repositorio

Exteriores_Urbanos. ..................................................................................................... 53


Exteriores_Naturales1................................................................................................... 54



Figura 5.7. Tercera parte de la gráfica de pertenencia a conglomerados del repositorio












Figura 5.13. Gráfica de pertenencia a conglomerados del repositorio Interiores1. ........................... 60

Figura 5.14. Primera parte de gráfica de pertenencia a conglomerados del repositorio Interiores2. 61

Figura 5.15. Segunda parte de gráfica de pertenencia a conglomerados del repositorio Interiores2.

...................................................................................................................................... 61

Figura 5.16. Tercera parte de gráfica de pertenencia a conglomerados del repositorio Interiores2. 62

Figura 5.17. Cuarta parte de gráfica de pertenencia a conglomerados del repositorio Interiores2. . 62

Figura 6.1. Ejemplo de una correspondencia verdadera. ................................................................. 67

Figura 6.2. Número de características destacadas del repositorio AQUA. ...................................... 69

Tesis de Maestría


Figura 6.3. Número de correspondencias del repositorio AQUA. .................................................... 70

Figura 6.4. Precisión del repositorio AQUA. .................................................................................... 70

Figura 6.5. Tiempo, medido en segundos, del repositorio AQUA. ................................................... 71

Figura 6.6. Imagen 10 y 11 resultado del algoritmo StarTex (buen desempeño).............................. 72

Figura 6.7. Imagen 74 y 75 resultado del algoritmo StarTex (buen desempeño).............................. 72

Figura 6.8. Imagen 360 y 361 resultado del algoritmo MserCol (buen desempeño). ....................... 73

Figura 6.9. Imagen 620 y 621 resultado del algoritmo StarTex (buen desempeño). ........................ 73

Figura 6.10. Imagen 730 y 731 resultado del algoritmo StarSAD. ................................................... 74

Figura 6.11. Imagen 873 y 874 resultado del algoritmo StarSAD. ................................................... 74

Figura 6.12. Imagen 896 y 897 resultado del algoritmo HarrisSAD................................................. 75

Figura 6.13. Imagen 930 y 931 resultado del algoritmo HarrisSAD................................................. 75

Figura 6.14. Imagen 975 y 976 resultado del algoritmo MserSAD (buen desempeño). ................... 76

Figura 6.15. Número de características destacadas del repositorio Exteriores_Urbanos. ................. 77

Figura 6.16. Número de correspondencias del repositorio Exteriores_Urbanos. .............................. 77

Figura 6.17. Precisión del repositorio Exteriores_Urbanos............................................................... 78

Figura 6.18. Tiempo, medido en segundos, del repositorio Exteriores_Urbanos. ............................ 78

Figura 6.19. Imagen 20 y 21 resultado del algoritmo MserTex. ....................................................... 79

Figura 6.20. Imagen 240 y 241 resultado del buen desempeño del algoritmo MserSAD. ................ 79

Figura 6.21. Imagen 452 y 453 resultado del buen desempeño del algoritmo StarSAD. .................. 80

Figura 6.22. Imagen 499 y 500 resultado del buen desempeño del algoritmo MserTex. .................. 80

Figura 6.23. Imagen 570 y 571 resultado del buen desempeño del algoritmo HarrisSAD. .............. 81

Figura 6.24. Imagen 1029 y 1030 resultado del algoritmo MserTex. ............................................... 81

Figura 6.25. Número de características destacadas de los repositorios Exteriores_Naturales. ......... 82

Figura 6.26. Número de correspondencias de los repositorios Exteriores_Naturales. ...................... 83

Figura 6.27. Precisión de los repositorios Exteriores_Naturales. ...................................................... 83

Figura 6.28. Tiempo, medido en segundos, de los repositorios Exteriores_Naturales. ..................... 84

Figura 6.29. Imagen 120 y 121 resultado del algoritmo StarTex. ..................................................... 85


Figura 6.31. Imagen 406 y 407 resultado del algoritmo MserSAD. ................................................. 87


Figura 6.33. Imagen 138 y 139 resultado del buen desempeño del algoritmo HarrisSAD. .............. 89

Figura 6.34. Imagen 331 y 332 resultado del buen desempeño del algoritmo StarTex. ................... 89


Figura 6.36. Imagen 766 y 767 resultado del algoritmo MserCol. ................................................... 90


Figura 6.38. Imagen 323 y 324 resultado del algoritmo MserSAD. ................................................. 91



Figura 6.41. Número de características destacadas de los repositorios Interiores. ........................... 93

Figura 6.42. Número de correspondencias detectadas en la ejecución de los algoritmos. ................ 94

Figura 6.43. Precisión en la ejecución de los algoritmos. ................................................................. 94

Figura 6.44. Tiempo, medido en segundos, de los repositorios Interiores. ....................................... 95

Figura 6.45. Imagen 84 y 85 resultado del buen desempeño del algoritmo StarTex. ....................... 95

Figura 6.46. Imagen 259 y 260 resultado del buen desempeño del algoritmo MserTex. .................. 96

Tesis de Maestría









Figura 6.54. Imagen 1565 y 1566 resultado del buen desempeño del algoritmo MserTex. ............ 100

Figura 6.55. Imagen 1613 y 1614 resultado del buen desempeño del algoritmo MserTex. ............ 100

Figura 6.56. Imagen 1980 y 1981 resultado del buen desempeño del algoritmo MserSAD. .......... 101

Figura 6.57. Número de características para la muestra de imágenes texturizadas. ........................ 104

Figura 6.58. Número de características para la muestra de imágenes estructuradas. ...................... 105

Figura 6.59. Precisión de los algoritmos con Star aplicados en la muestra texturizada. ................. 105

Figura 6.60. Precisión de los algoritmos con Star aplicados en la muestra estructurada. ............... 106

Figura 6.61. Precisión de los algoritmos con MSER aplicados en la muestra texturizada. ............ 106

Figura 6.62. Precisión de los algoritmos con MSER aplicados en la muestra estructurada. ........... 107

Figura 6.63. Precisión de los algoritmos con Harris aplicados en la muestra texturizada. ............. 107

Figura 6.64. Precisión de los algoritmos con Harris aplicados en la muestra estructurada. ............ 108

Figura A.1. Diagrama de módulos. ................................................................................................ 121

Tesis de Maestría


Índice de tablas

Tabla 2.1. Información general de detectores de características (Tuytelaars, 2008). ........................ 23

Tabla 2.2. Técnicas para algoritmos de correspondencia de línea base corta. .................................. 32

Tabla 5.1. Características de los repositorios de imágenes. ............................................................. 49

Tabla 5.2. Características de los atributos numéricos. ..................................................................... 49

Tabla 5.3. Cantidad de conglomerados por repositorio. ................................................................... 50

Tabla 5.4. Características de conglomerados del repositorio AQUA. ............................................. 51

Tabla 5.5. Identificación de algunas escenas de AQUA. .................................................................. 52

Tabla 5.6. Características de conglomerados del repositorio Exteriores_Urbanos. ......................... 52

Tabla 5.7. Identificación de algunas escenas de Exteriores_Urbanos. .............................................. 53

Tabla 5.8. Características de conglomerados del repositorio Exteriores_Naturales1. ..................... 54

Tabla 5.9. Identificación de algunas escenas de Exteriores_Naturales1. .......................................... 55

Tabla 5.10. Características de conglomerados del repositorio Exteriores_Naturales2. ................... 56

Tabla 5.11. Identificación de algunas escenas de Exteriores_Naturales2. ........................................ 57

Tabla 5.12. Características de conglomerados del repositorio Exteriores_Naturales3. ................... 58

Tabla 5.13. Identificación de algunas escenas de Exteriores_Naturales3. ........................................ 59

Tabla 5.14. Características de conglomerados del repositorio Interiores1. ...................................... 59

Tabla 5.15. Identificación de algunas escenas del repositorio Interiores1. ....................................... 60

Tabla 5.16. Características de conglomerados del repositorio Interiores2. ...................................... 60

Tabla 5.17. Identificación de algunas escenas del repositorio Interiores2. ....................................... 62

Tabla 5.18. Características de los repositorios de imágenes texturizadas y estructuradas. ............... 63

Tabla 5.19. Características de conglomerados de los conglomerados. ............................................ 64

Tabla 5.20. Pertenencia de los conglomerados a los conglomerados. ............................................... 64

Tabla 5.21. Características de los conglomerados de repositorios. .................................................. 65

Tabla 5.22. Pertenencia de los repositorios a los conglomerados. .................................................... 65

Tabla 6.1. Tabla de composición de algoritmos de correspondencia. ............................................... 66

Tabla 6.2. Algoritmos que mejor se desempeñaron en el repositorio AQUA. ................................ 101

Tabla 6.3. Algoritmos que mejor se desempeñaron en el repositorio Exteriores_Urbanos. ........... 102

Tabla 6.4. Algoritmos que mejor se desempeñaron en el repositorio Exteriores_Naturales1. ........ 102



Tabla 6.7. Algoritmos que mejor se desempeñaron en el repositorio Interiores1. .......................... 103

Tabla 6.8. Algoritmos que mejor se desempeñaron en el repositorio Interiores2. .......................... 103

Tabla C.1. Número de características detectadas en las imágenes muestra del repositorio AQUA.

....................................................................................................................................... 133

Tabla C.2. Precisión de los algoritmos 1- 4 en las imágenes muestra del repositorio AQUA. ....... 133

Tabla C.3. Precisión de los algoritmos 5- 8 en las imágenes muestra del repositorio AQUA. ....... 133

Tabla C.4. Precisión de los algoritmos 9- 12 en las imágenes muestra del repositorio AQUA. ..... 134

Tabla C.5. Tiempo, en segundos, de los algoritmos 1-6 del repositorio AQUA. ............................ 134

Tabla C.6. Tiempo, en segundos, de los algoritmos 7-12 del repositorio AQUA. .......................... 135

Tabla C.7. Número de características detectadas en las imágenes muestra del repositorio

Exteriores_Urbanos. ...................................................................................................... 135

Tesis de Maestría


Tabla C.8. Precisión de los algoritmos 1- 4 en las imágenes muestra del repositorio





Exteriores_Urbanos. ................................................................................................... 136

Tabla C.11. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Exteriores_Urbanos. ..... 136

Tabla C.12. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Exteriores_Urbanos. ... 136


Exteriores_Naturales1................................................................................................. 137

Tabla C.14. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio






Tabla C.17. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Exteriores_Naturales1. . 138

Tabla C.18. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Exteriores_Naturales1. 138






















Interiores1. .................................................................................................................. 140

Tabla C.32. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio Interiores1. 141


Tabla C.34. Precisión de los algoritmos 9-12 en las imágenes muestra del repositorio Interiores1.

.................................................................................................................................... 141

Tesis de Maestría


Tabla C.35. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Interiores1. .................... 141

Tabla C.36. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Interiores1. .................. 141


Interiores2. .................................................................................................................. 142




.................................................................................................................................... 142

Tabla C.41. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Interiores2. .................... 143

Tabla C.42. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Interiores2. .................. 143

Tesis de Maestría


Acrónimos

Elemento Ortográfico

Descripción

CenSurE Center Surrounded Extrema

Extremos de Centro Rodeado

EBR

Edge Based Regions

Regiones Basadas en Bordes

GLCM

Grey Level Coocurrence Matrix

Matriz de Coocurrencia de Niveles de Grises

GLOH Gradient Location and Orientation Histograms

Histogramas de Orientación y Localización por Gradiente

IBR

Intensity Based Regions

Regiones Basadas en la Intensidad

MSER

Maximally Stable Extremal Regions

Regiones Extremas Máximamente Estables

NCC

Normalized Cross Correlation

Correlación Cruzada Normalizada

SAD

Sum of Absolute Differences

Suma de Diferencias Absolutas

SIFT Scale-Invariant Feature Transform

Transformación de Características Invariante a Escala

SSD Sum of Squared Differences

Suma de Diferencias Cuadradas

SURF Speeded Up Robust Features

Detector Acelerado de Características Robustas

SUSAN Smallest Univalue Segment Assimilating Nucleus

Segmento más Pequeño Univaluado de Asimilación de Núcleo

UAV Unmanned Aerial Vehicle

Vehículo Aéreo no Tripulado

VNC

Variance Normalized Correlation

Correlación de Varianza Normalizada

vSLAM

Visual Simultaneous Localization and Mapping

Localización y Mapeo Simultáneo basado en Visión

Tesis de Maestría


Glosario

Término

Definición

Ambiente (Del lat. Ambiens, -entis, que rodea o cerca). adj. Dicho de un fluido:

Que rodea un cuerpo (RAD, 2001).

Blob Se define como una región relativamente pequeña.

Características destacadas

de una imagen

Son bordes, regiones o puntos de interés que se presentan en la

imagen. Estas características se diferencian de las características

comunes en que representan patrones estables de la escena a lo largo

del tiempo, y en que pueden estar asociados tanto a características

geométricas de la misma como a características de los valores de

intensidad de los píxeles (Baumela, 2007).

Contorno Es un conjunto de píxeles que puede ser caracterizado mediante

medidas basadas en su intensidad y en su geometría, como pueden ser

su longitud, su orientación, su curvatura y el contraste medio a lo

largo de él (López, 2005).

Correspondencia

esteroscópica

Es el proceso mediante el cual dado un punto en la escena 3D se llega

a determinar cuál es su proyección en sendas imágenes del par

estereoscópico (Pajares, 2008).

Disparidad Es el valor absoluto de la diferencia de las primeras coordenadas de

un punto en la vista 1 y su correspondiente, en la vista 2, cuando la

línea epipolar que los contiene es paralela a la línea base del sistema

óptico. Esta distancia es inversamente proporcional a la distancia del

punto físico a las cámaras (González, 2011).

Entorno Se considera como sinónimo del concepto denominado ambiente.

Para los propósitos de este trabajo se clasificó en tres tipos: acuático,

aéreo y terrestre.

Entorno acuático Se considera un ambiente acuático si la cámara está rodeada de agua

y los objetos en la escena están sumergidos en ella.

Entorno aéreo

Se considera un ambiente aéreo si la cámara es portada por un

vehículo aéreo y la escena es capturada desde arriba.

Entorno terrestre

Se considera un ambiente terrestre si la cámara y todos los objetos

que se visualizan en la escena están unidos al suelo.

Escena (escenario) Se define como una porción del espacio tridimensional acotado por el

campo visual de la cámara, en un momento dado.

Escena estructurada Es aquella escena que genera imágenes estructuradas.

Escena texturizada Es aquella escena que genera imágenes texturizadas.

Tesis de Maestría


Espacio tridimensional no

controlado

Se entiende por aquel espacio en donde el espectador no tiene gran

intervención con respecto al tipo, número y disposición de los objetos

que aparecen en la escena.

Imagen estructurada

Imagen que contiene regiones homogéneas con bordes distintivos en

las fronteras y en consecuencia son más fáciles de segmentar

(Mikolajczyk, 2005).

Imagen texturizada

Imagen que está compuesta de patrones repetidos y que aparecen

como una superficie de textura única (Li, 2000) y (Mikolajczyk,

2005).

Línea base La expresión “línea base” se refiere a la distancia entre los dos

centros de la cámara de un sistema de cámaras estéreo (Pajares,

2008). En este sentido las palabras “línea base larga” se usan para

denotar una situación donde dos imágenes no son “obviamente

similares”, al menos para un sistema de visión (Tell, 2002).

Mapa de disparidad Es el conjunto de todas las disparidades entre dos imágenes de un par

estéreo (González, 2011).

Métodos de

correspondencia densos

Estos métodos generan mapas de disparidad, en donde todos o casi

todos los píxeles tienen determinados valores de disparidad

(Cyganek, 2009).

Métodos de

correspondencia dispersos

Estos métodos generan mapas de disparidad que tienen valores de

disparidad determinados sólo para un conjunto selecto de puntos

(generalmente este conjunto contiene esquinas o bordes), el resto de

los valores de disparidad se obtienen por interpolación (Cyganek,

2009).

Métodos de

correspondencia locales

Realizan la correspondencia entre puntos que provienen de distintas

imágenes tomadas de una misma escena a través de la comparación

entre vecindades de estos puntos (Cyganek, 2009).

Métodos de

correspondencia globales

Los métodos globales realizan la correspondencia entre puntos que

provienen de distintas imágenes tomadas de una misma escena a

través de la comparación entre líneas o todos los píxeles de las

respectivas imágenes (Cyganek, 2009).

Métodos de

correspondencia por

bloques o basados en la

correlación

Son aquellos que buscan el máximo puntaje de correspondencia o el

mínimo error sobre una pequeña región, típicamente usando variantes

de correlación cruzada o métricas de rango robustas (Brown, 2003).

En los métodos basados en la correlación, los elementos a comparar

son ventanas de la imagen de dimensión fija, y el criterio de

semejanza es una medida de la correspondencia entre las ventanas de

las dos imágenes, generalmente se aplican a la totalidad de los puntos

de la imagen (Graffigna, 2005).

Tesis de Maestría


Son aquellos que consideran los valores de intensidad de los píxeles

como una señal bidimensional, que en una de las dos imágenes ha

sufrido una traslación (López, 2005).

Métodos de

correspondencia basados

en características

Son aquellos que buscan puntos característicos de emparejamiento

más que intensidades (Brown, 2003).

Son aquellos que restringen la búsqueda a un conjunto disperso de

características. Estos métodos emplean propiedades simbólicas y

numéricas de las características, disponibles a partir de los

descriptores que se utilicen (Graffigna, 2005).

Son aquellas que limitan las regiones a analizar a características

fiables de las imágenes, como pueden ser los contornos, las curvas,

etc. (López, 2005).

Oclusión Se refiere al hecho de que algunos objetos en una escena sean

visibles en una cámara pero no en la otra, debido a la escena y a la

geometría de la cámara.

Par estereoscópico Es un par de características homólogas que son proyección del mismo

punto del espacio en tres dimensiones (Sánchez, 2003).

Región Se define como un conjunto de píxeles cuya descripción es

relativamente uniforme y diferenciada con respecto de las regiones

vecinas inmediatas.

Restricciones aplicables a

la correspondencia

Son aquellas proposiciones que tienen como objetivo establecer de

manera unívoca la correspondencia entre características (Pajares,

2008).

Segmentación Es el proceso de dividir una imagen en regiones (Baumela, 2007).

Texturas homogéneas Estas texturas se caracterizan porque sus rasgos de textura son

constantes (Lepistö, 2003).

Texturas no homogéneas Estas texturas se identifican porque sus rasgos de textura no son

constantes en cada parte de la muestra de textura (Lepistö, 2003).

Visión estéreo o

estereoscópica

Se define visión estéreo o estereoscópica como aquella en la que se

emplea más de una imagen para obtener una idea de

tridimensionalidad. Según el número de imágenes que se emplee, se

habla de visión bifocal -dos imágenes o vistas-, trifocal -tres

imágenes o vistas-, cuadrifocal –cuatro imágenes o vistas- o n-focal -

n imágenes o vistas (Ruiz, 2005).

La visión estéreo es un mecanismo para obtener información de

profundidad de imágenes digitales (Huang, 2008).

Es aquella en la que se emplea más de una imagen para obtener una

idea de tridimensionalidad (Morales, 2009).

Tesis de Maestría


Capítulo 1

1. Lineamientos del trabajo de tesis

1.1. Introducción

La estereovisión o visión estereoscópica es aquella en la que se emplea más de una imagen para

obtener una idea de tridimensionalidad (Morales, 2009). Su funcionamiento es básicamente el

siguiente: se obtienen dos imágenes de una misma escena, desde dos puntos de vista diferentes

(ligeramente diferentes). Estas imágenes pueden provenir respectivamente, de dos cámaras, en esta

situación se estaría hablando de un sistema de visión estéreo binocular, o pueden provenir de una

sola cámara en movimiento, en cuyo caso se dice que se está hablando de un sistema de visión

estéreo monocular.

Una vez que se adquirieron ambas imágenes se establece la correspondencia entre los puntos de las

dos vistas que son la proyección de un mismo punto físico de la escena, a este proceso se le conoce

como correspondencia. Posteriormente, lo que se busca, normalmente, es la posición 3D del punto

físico (reconstrucción).

La investigación en estereovisión computacional ha madurado significativamente a través del

tiempo y son muchos los avances que se siguen produciendo. Sin embargo, López et al. (López,

2005) establecen que al contrario de la dificultad en la reconstrucción, la cuestión de la

correspondencia es un problema más difícil de resolver, ya que no es un problema con solución

cerrada, por la ambigüedad que existe al buscar posibles correspondencias entre los pixeles de las

dos imágenes.

El problema de la correspondencia se torna aún más difícil cuando las imágenes que se van a

analizar proceden de escenas reales con objetos no estáticos, a este tipo de escenas se les denomina

escenas no controladas.

Aunque se proponen continuamente algoritmos de correspondencia que tienen el propósito de

funcionar de manera eficaz y eficiente en cualquier entorno, hasta el momento, no se ha encontrado

un algoritmo que resuelva en su totalidad este problema.

Adicionalmente todas las funciones de los sistemas de visión robótica se ven afectadas y

condicionadas por la correspondencia. Estas funciones son: la reconstrucción1, la determinación de

cuadros significativos, la odometría visual2, la asociación de datos, localización y mapeo. Entonces

es muy importante tener una idea precisa de las limitaciones de cada método en cada escenario.

El grupo académico de Inteligencia Artificial del CENIDET, así como algunos investigadores de la

UAEM, de la Universidad Rey Juan Carlos de España y de la Universidad de McGill, Montreal,

Canadá, están interesados en buscar desempeños más parecidos a los de la visión humana para los

1 López et al. (López, 2005) definen reconstrucción como el proceso mediante el cual se busca la posición 3D

de un punto físico en una escena utilizando la proyección de éste en dos imágenes tomadas de esta misma

escena. 2 Williams et al. (Williams, 2010) definen la odometría visual es un proceso para determinar la trayectoria de

una cámara a través de la correspondencia de características destacadas que se establece entre una secuencia

de imágenes.

Tesis de Maestría


sistemas de visión automáticos de robots que aspiran a ser autónomos en entornos específicos. Estos

robots pueden estar estáticos o en movimiento, en este último se dice que se trata de un sistema

robótico móvil o de navegación computarizada.

En el CENIDET se pretende obtener cada vez más y mejores resultados en la navegación terrestre

de robots, como muestra de ello se tiene la tesis de Pérez (Pérez, 2002) en donde se desarrolló una

aplicación en lenguaje C++ (Builder), que calibra automáticamente un sistema de visión robótico

utilizando parámetros obtenidos mediante una interfaz. Asimismo en el trabajo de González

(González, 2011) se construyeron un robot móvil y su sistema de visión. Este sistema de visión le

permite al robot navegar en un ambiente controlado de suelo plano en el cual se colocan algunos

obstáculos con alta textura para simular un ambiente exterior.

También es del interés de este grupo académico el que se identifiquen y prueben algoritmos para

robots manipuladores que realizan labores que, eventualmente, por su naturaleza, resultan

peligrosas para un humano. Evidencia de esto es el trabajo de Gómez y Zamorano (Gómez, 2008)

en donde se usó la visión estereoscópica (monocular y binocular) para que un brazo robótico

PUMA pudiera localizar un punto en el espacio. Otra muestra de esto son los trabajos de Fuentes

(Fuentes, 2008), (Fuentes, 2009); en donde un robot manipulador CRS-T475, de siete grados de

libertad provisto con dos cámara fijas con configuración de par estéreo, fue capaz de seguir y

sujetar, en tiempo real, un objeto móvil que sigue una trayectoria oval.

Para que todos estos trabajos se pudieran llevar a cabo de manera exitosa fue necesario que estos

sistemas, ya sean móviles o estáticos, fueran capaces de identificar un conjunto suficiente de

correspondencias verdaderas entre imágenes, con el fin de calcular la distancia del sistema a

cualquier punto de la escena y consecuentemente poder recuperar información 3D.

A pesar de que es muy importante tener identificados los algoritmos de correspondencia que

funcionan mejor en cierto entorno, relativamente poco trabajo se ha hecho para caracterizar la

ejecución de los algoritmos en distintos ambientes. Esto hace que sea necesaria la realización de un

estudio exploratorio que permita clasificar un conjunto de algoritmos probando su eficiencia y

aplicabilidad en imágenes que provienen de distintos entornos.

1.2. Objetivo de la tesis

El objetivo de este trabajo de tesis consistió en investigar, analizar e implementar3 por lo menos

cuatro algoritmos de correspondencia, que permitan encontrar puntos correspondientes de dos

imágenes, extraídas de un video tomado por un sistema de visión estéreo monocular inmerso en un

entorno acuático o terrestre. Esto con el fin de realizar una evaluación comparativa del rendimiento

de dichos algoritmos, a través de la medición de la precisión y del tiempo de ejecución de éstos

cuando se aplican al mismo par estereoscópico.

Para realizar este objetivo se utilizaron pares de imágenes, en su mayoría, de repositorios generados

por los grupos académicos antes mencionados, se hizo uso de algoritmos implementados en Open

CV.2.1 para la fase de extracción de características y los algoritmos que se implementaron no usan

la restricción epipolar.

3 Implementación o codificación es la actividad de traducir los algoritmos de diseño de un programa escrito en

un lenguaje de programación (Joyanes, 2008).

Tesis de Maestría


1.3. Metodología de solución

La identificación de algunas de las fases de la metodología que se planteó para la realización de este

trabajo se basó en los trabajos de Sánchez (Sánchez, 2003) y Graffigna et al. (Graffigna, 2005). En

la figura 1.1 se muestra un diagrama de bloques de la metodología empleada.

Figura 1.1. Diagrama de bloques de la Metodología.

Adquisición

La evaluación de los algoritmos requiere de una base de datos de pares estereoscópicos para realizar

los ensayos. Por ello esta metodología comienza con la adquisición de dos imágenes consecutivas

extraídas de una secuencia de video generada por una cámara en movimiento.

Adquisición

Búsqueda de parejas

Desambiguación

Evaluación

Detección de Caracterísitcas

Destacadas (CD)

Star Mser Harris

Emparejamiento de puntos

Textura Color SAD VNC

Tesis de Maestría


Es importante hacer notar que no siempre se pueden obtener imágenes óptimas del escenario. Las

imágenes pueden estar borrosas por la vibración de la cámara, el desenfoque y el tiempo largo de

exposición. Puede haber falta de contraste por falta o sobra de luz, y en el caso binocular, falta de

sincronización entre imágenes que da lugar a problemas de reconstrucción.

Detección de características destacadas

En esta fase, a ambas imágenes se les aplica el mismo detector de características para obtener de

cada una de ellas un arreglo con las coordenadas en el espacio 2D de los indicadores de las

características destacadas que se detectan respectivamente en cada imagen. Concretamente, se debe

elegir uno de entre los algoritmos Star, Mser o Harris para construir dichos arreglos.

Búsqueda de parejas

Una vez obtenidos los arreglos con las coordenadas de los indicadores de las características

destacadas de ambas imágenes, a cada uno de ellos se les aplica una función denominada Ebola, la

cual implementa un proceso de búsqueda de tipo vecinos más cercanos, para generar otros dos

arreglos. Uno de estos nuevos arreglos contiene en cada fila las coordenadas del respectivo

indicador de la vista 1 junto con las coordenadas de los indicadores de la vista 2 cuya distancia al

indicador de la vista 1 no sobrepasa un cierto umbral, convirtiéndose automáticamente en las

parejas potenciales de dicho punto de la vista 1. De manera análoga el otro nuevo arreglo contiene

en cada una de sus filas las coordenadas del respectivo indicador de la vista 2 así como las

coordenadas de los indicadores de la vista 1 cuya distancia al indicador de la vista 2 no supera el

umbral prefijado.


A cada uno de los dos arreglos resultantes de la fase de búsqueda de parejas se les aplica el mismo

algoritmo de emparejamiento para construir dos arreglos con las coordenadas de los pares de puntos

correspondientes. En cada fila del primer arreglo obtenido en esta fase se almacenan las

coordenadas 2D del respectivo indicador de la vista 1 junto con las coordenadas 2D del indicador de

la vista 2 que eligió. De manera análoga en cada fila del segundo arreglo construido se almacenan

las coordenadas del respectivo indicador de la vista 2 junto con las coordenadas del punto de la

vista 1 que eligió. Para llevar a cabo el emparejamiento, se debe elegir uno de los siguientes

algoritmos SAD, VNC, Textura o Color.

Desambiguación

Dado que el indicador de una característica de la vista 2 puede ser elegido por más de un indicador

de una característica de la vista 1, y viceversa, se tiene que aplicar un algoritmo de desambiguación

con el fin de determinar, de manera definitiva, las parejas de puntos correspondientes.

Evaluación

Finalmente una vez determinado el arreglo final de parejas de puntos correspondientes se procede a

verificar cuáles de estas parejas son correctas o verdaderas, esto es, que corresponden al mismo

Tesis de Maestría


punto físico. Es importante hacer notar que a diferencia de las fases previas esta etapa es realizada

por un operador humano y no por el sistema computacional.

1.4. Organización del documento

El documento está organizado de la manera siguiente: en el Capítulo 1 se explicitan los elementos

que rigieron este trabajo de tesis, en el Capítulo 2 se da un resumen de la revisión del estado del

arte, en el Capítulo 3 se da una breve descripción de los algoritmos implementados en esta tesis, en

el Capítulo 4 se explica el diseño que se utilizó para la implementación del sistema, en el Capítulo 5

se describen los repositorios que se utilizaron, en el Capítulo 6 se presentan los resultados de las

pruebas del desempeño de los algoritmos y, finalmente, en el Capítulo 7 se muestran las

conclusiones de la tesis.

Tesis de Maestría


Capítulo 2

2. Estado del arte

Existe una dificultad intrínseca al momento de emparejar puntos, ya que con frecuencia hay una

multitud de píxeles con características muy parecidas y que no corresponden al mismo punto físico.

En contraparte también con frecuencia dos píxeles que corresponden al mismo punto físico no

presentan exactamente las mismas características, a causa de la diferencia en perspectiva de las

cámaras o en la iluminación. Debido a esto López et al. (López, 2005) mencionan que el problema

de la correspondencia estéreo es ambiguo y para su resolución es necesario averiguar qué

elementos, qué características, qué restricciones y qué consideraciones se pueden aplicar para

reducir la ambigüedad al máximo.

Para ello, de acuerdo con Baumela (Baumela, 2007), se tienen que responder las dos cuestiones

siguientes:

1. ¿Qué elementos o primitivas de la imagen se pondrán en correspondencia?

2. ¿Qué restricciones reducen la ambigüedad del proceso de correspondencia?

Para contestar la primera pregunta es necesario considerar que las primitivas a poner en

correspondencia deben de tener propiedades intrínsecas que les permitan tener una medida de

similitud fuertemente discriminante, algunas de estas propiedades son las siguientes:

1. Fácilmente extraíbles.

2. Informativas

3. Invariantes a cambios de iluminación y de punto de vista.

A las primitivas que cumplen con las propiedades anteriores se les llama características destacadas.

Estas características se diferencian de las características comunes en que representan patrones

distintivos y estables en la imagen de la escena a lo largo del tiempo, que pueden estar asociados

tanto a características geométricas de la misma como a características de los valores de intensidad

de los píxeles.

Las primitivas más comúnmente empleadas son:

a) Píxel

Es un único punto en una imagen y siempre se analiza éste junto con sus vecinos, ya que de esta

manera resulta más sencillo descartar correspondencias falsas producidas por la igualdad entre

píxeles individuales. Frecuentemente el píxel se utiliza para representar los puntos esquina y es

menos sensible al ruido que otras primitivas.

b) Conjuntos de píxeles: contornos o regiones

Según López et al. (López, 2005) con este tipo de primitiva es menos probable encontrar falsas

correspondencias sin embargo los contornos son sensibles al ruido.

Tesis de Maestría


En (López, 2005) se define contorno como un conjunto de píxeles que pueden ser caracterizados

mediante medidas basadas en su intensidad y en su geometría, como pueden ser su longitud, su

orientación, su curvatura y el contraste medio a lo largo de él.

También se puede pensar en agrupar los píxeles de contorno para formar curvas o trozos de curvas.

La curva más simple y que además es invariante mediante proyección perspectiva es la línea recta.

Se entiende por región a un conjunto de píxeles cuya descripción es relativamente uniforme y

diferenciada con respecto de las regiones vecinas inmediatas.

También se pueden utilizar regiones de las imágenes como primitivas para analizar su

correspondencia en el procesamiento estéreo. Existen muchas características que se pueden extraer

de dichas regiones para establecer las correspondencias: su nivel medio de brillo, su tamaño, su

perímetro, su forma, etc. El proceso de dividir una imagen en regiones se denomina segmentación.

Una región cuya área es relativamente pequeña se denomina blob.

Para realizar el emparejamiento entre indicadores de características destacadas de un par de

imágenes comúnmente se consideran sus propiedades de intensidad, color o textura.

2.1. Propiedades de un detector de características

Cuando se busca un detector de características adecuado para una cierta aplicación dada, Tuytelaars

et al. (Tuytelaars, 2008) sugieren considerar varios puntos:

Primero: Tipo de características destacadas que se van a extraer en la imagen esquinas, blobs o

regiones algunas de estas estructuras son más comunes en unas imágenes que en

otras.

Segundo: El nivel de invariancia, se refiere a que la detección de características no se vea afectada

por transformaciones geométricas considerables de la imagen.

Tercero: Las propiedades cualitativas de los detectores a considerar:

Distinción/informatividad: La intensidad de los patrones subyacentes de las

características detectadas deberían mostrar una cantidad de variación, de tal forma

que las características se puedan distinguir y por ende ser emparejadas.

Localidad: Las características deben ser locales, para reducir la probabilidad de

oclusión4 y permitir aproximaciones simples al modelo de las deformaciones

geométricas y fotométricas entre dos imágenes tomadas desde distintos puntos de

vista.

Cantidad: El número de características detectadas debe ser lo suficientemente

grande, de tal forma de que un número razonable de características sean detectadas

4 Se refiere al hecho de que algunos objetos en una escena sean visibles en una cámara pero no en la otra,

debido a la escena y a la geometría de la cámara.

Tesis de Maestría


incluso en objetos pequeños. Sin embargo, el número óptimo de características

necesarias depende de la aplicación.

Repetibilidad: Dadas dos imágenes del mismo objeto o escena, tomadas desde

puntos de vista distintos, debe suceder que un porcentaje alto de las características

detectadas en la imagen de la parte visible de la escena deberían de estar presentes en

las dos imágenes. Se puede decir que esta propiedad es la más importante de todas y

se puede lograr de dos formas distintas: por invarianza o por robustez.

o Invariancia: Cuando se esperan grandes transformaciones de la imagen, se

recomienda modelar estas transformaciones matemáticamente y entonces

desarrollar métodos para la detección de características que no se vean

afectados por estas transformaciones matemáticas.

o Robustez: En el caso de que las deformaciones sean pequeñas, a menudo

basta con hacer los métodos de detección de características menos sensibles

a tales deformaciones.

2.2. Detectores de características utilizados en esta tesis

En este trabajo de tesis se utilizaron tres algoritmos para la detección de características: Shi-Tomasi,

Star y MSER, los tres vienen implementados en OpenCV versión 2.1. y para que cada uno de ellos

se pueda aplicar se requiere que la imagen esté en escala de grises.

Shi y Tomasi (Shi, 1994) presentan un detector de puntos característicos basado

fuertemente en el detector de esquinas de Harris. Algunas veces este detector es referido

como detector de esquinas de Kanade-Tomasi, en este trabajo, en lo sucesivo, se le referirá

simplemente como “Harris”.

El algoritmo de Harris es uno de los algoritmos más citado en la literatura, mostrado por

primera vez (Harris, 1988). Se basa en la auto-correlación de la señal y detecta esquinas.

Según Sánchez (Sánchez, 2003) las esquinas son características presentes en muchos tipos

de escenas, ya que se encuentran con gran facilidad en entornos artificiales, pero también

pueden encontrarse sin problemas en entornos naturales.

El detector de blobs Star es derivado del algoritmo CenSurE (Extremos de Centro

Rodeado), y el descriptor que usa CenSurE está basado en el descriptor de SURF (Detector

Acelerado de Características Robustas).

MSER es un detector de regiones a través de la segmentación de la imagen. Matas et al.

(Matas, 2002) estaban interesados en definir descriptores que fueran robustos bajo

transformaciones surgidas por el cambio de perspectiva. Ellos estudiaron conjuntos de nivel

con respecto a la función de intensidad de escala de grises de una imagen y midieron la

estabilidad de éstos a lo largo de la dimensión de intensidad. Basándose en esta idea, ellos

definieron la noción de regiones extremas máximamente estables (MSER) y mostraron

como éstas pueden servir como características destacadas de la imagen para la

correspondencia estéreo.

Tesis de Maestría


Las MSER pueden verse como un subconjunto específico de blobs de niveles de grises para

el procesamiento.

2.3. Evaluación de algunos detectores de características

En (Mikolajczyk, 2002) se presenta el algoritmo denominado Harris-Affine con un enfoque nuevo

para detectar regiones de interés invariantes afines. Esto es, un algoritmo que hace frente a

transformaciones afines significativas que incluyen grandes cambios de escala. Tales

transformaciones introducen cambios significativos en la localización de los puntos así como en la

forma de la vecindad de un punto de interés.

Los autores proponen el detector de esquinas Harris-Affine como una mejora del detector de

esquinas Harris y hacen una comparativa entre Harris-Affine y otro algoritmo de detección de

puntos característicos denominado Harris-Laplace.

En (Mikolajczyk, 2006) se da un estado del arte de los detectores de regiones afines covariantes5

que habían hasta ese momento, y además se hizo una comparativa del desempeño de estos

detectores en un conjunto de prueba con 24 imágenes. Este conjunto incluyó imágenes de escenas

texturizadas y estructuradas, así como imágenes con tipos de transformaciones bien definidas, como

son: cambios en el punto de vista, cambios en la escala, cambios en la iluminación, desenfocado y

compresión de la imagen JPEG.

Las técnicas que se compararon fueron: Harris-Affine, Hessian-Affine, MSER, EBR (Regiones

Basadas en Bordes), IBR (Regiones Basadas en la Intensidad) y los resultados obtenidos fueron:

1. En varios casos el puntaje más alto se obtiene por el detector MSER, seguido por el

Hessian-Affine. MSER se ejecuta muy bien en imágenes que contienen regiones

homogéneas con límites distintivos. Esto mismo se aplica para IBR en el sentido de que

ambos algoritmos son designados para tipos de regiones similares.

2. MSER y EBR responden bien a las escenas estructuradas. El resto de los algoritmos

responden mejor a las escenas texturizadas.

3. El número de regiones correspondientes detectadas en las escenas estructuradas es mucho

menor que en las escenas texturizadas y sus variaciones, en distinta medida para cada uno

de los detectores.

4. Hessian-Affine y Harris-Affine proveen más regiones que los otros detectores. Además son

útiles para hacer correspondencia en escenas con oclusiones y confusiones.

5. EBR es apropiado para escenas que contienen intersecciones de bordes.

6. Las regiones destacadas obtuvieron bajos puntajes en esta evaluación pero se ejecutaron

bien en el contexto de reconocimiento de clases de objetos.

5 Se dicen regiones covariantes, en el sentido de que ellas cambian covariantemente con la transformación que

se les aplica. A menudo, en la literatura, se les llama regiones invariantes (Mikolajczyk, 2006).

Tesis de Maestría


En (Martínez, 2007) se analiza la idoneidad de los detectores de características Harris, Harris

Laplace, SUSAN (Segmento más Pequeño Univaluado de Asimiliación de Núcleo), SIFT

(Transformación de Características Invariante a Escala) y SURF cuando se usan como extractores

de marcas para la localización y mapeo simultáneo basado en visión (vSLAM). Para este propósito

se evaluaron estos detectores de acuerdo a su repetibilidad bajo cambios en el punto de vista y la

escala.

Para evaluar estos métodos se adquirieron 12 secuencias de imágenes con puntos de vista distintos,

cada secuencia estaba compuesta por 21 imágenes. Adicionalmente se capturaron 14 secuencias de

imágenes con cambios de escala, cada secuencia contenía 12 imágenes.

El detector de características Harris es el más estable, ya que es capaz de mantener casi el 30% de

los puntos iniciales de todas las imágenes de las secuencias con cambios de puntos de vista de 50

grados. Resultados similares se obtienen cuando se usa Harris en diferentes escalas. El detector de

características SIFT también obtiene buenos resultados con puntos de vista distintos, pero empeora

bajo cambios de la escala. En general se encuentra que el número de puntos detectados difiere

cuando se usan diferentes métodos.

Tuytelaars et al. (Tuytelaars, 2008) hacen una clasificación de los detectores de características:

Harris, Hessian, SUSAN, Harris-Laplace, Hessian-Laplace, DoG, SURF, Harris-Affine, Hessian-

Affine, Salient Regions, Edge-Based, MSER, Intensity- Based y Superpixels, en función del tipo de

característica destacada que extraen y su desempeño cuando se aplican a una secuencia de cuatro

imágenes de graffiti que sufrieron transformaciones ad hoc para probar sus propiedades cualitativas.

Esta información se resume en la tabla 2.1, en donde se observa que Harris aparece como uno de

los detectores con mayor tasa de repetibilidad y de los más informativos. MSER además se muestra

invariante a escala y transformaciones afines.

Tabla 2.1. Información general de detectores de características (Tuytelaars, 2008).

DC Esquina Blob Region Inv. a

Rotación

Inv. a

Escala

Inv.

Affine

Repetibilidad Precisión

de Loc.

Robustez Eficiencia

Harris +++ +++ +++ ++

Hessian ++ ++ ++ +

SUSAN ++ ++ ++ +++

Harris-

Laplace

+++ +++ ++ +

Hessian-

Laplace

+++ +++ +++ +

DoG ++ ++ ++ ++

SURF ++ ++ ++ +++

Harris-Affine +++ +++ ++ ++

Hessian-

Affine

+++ +++ +++ ++

Salient

Regions

+ + ++ +

Edge-Based +++ +++ + +

MSER +++ +++ ++ +++

Intensity-

Based

++ ++ ++ ++

Superpixels + + + +

Tesis de Maestría


En [2] se hace una comparativa de algunos detectores de características implementados en algunas

librerías de OpenCV, entre ellos se encuentran Star y MSER. Para realizar esta comparativa se

procesaron cuatro imágenes de prueba de tamaño 512512 en niveles de grises. Los resultados

mostraron que Star y MSER no se consideran entre los detectores que encuentran numerosas

características pero su tiempo de ejecución es aceptable y su porcentaje de seguimiento de

características es relativamente bueno.

Para contestar la segunda pregunta planteada por Baumela: ¿Qué restricciones reducen la

ambigüedad del proceso de correspondencia?, se tiene que Vincent et al. (Vincent, 2001)

recomiendan utilizar una serie de restricciones para tratar de reducir el espacio de búsqueda. Según

López et al. (López, 2005) las restricciones son de tres tipos básicos:

a) Restricciones geométricas impuestas por el sistema de captación de las imágenes.

Probablemente la restricción más importante sea la restricción epipolar, gracias a la cual se

puede transformar una búsqueda en dos dimensiones en otra de una dimensión.

b) Restricciones geométricas impuestas por los objetos que se están mirando. Se puede decir

que la continuidad de los objetos en las escenas, las distancias al origen de los puntos

cercanos de la escena varían lentamente en todas las direcciones excepto en las

discontinuidades producidas en los contornos.

c) Las restricciones físicas son aquellas que proceden de modelos por los que los objetos

interactúan con la iluminación: fuentes y reflexiones en los objetos. De todos ellos, el

modelo más simple y el más usado es el modelo Lambertiano, el cual asume que la

intensidad de la proyección de cualquier punto tridimensional no depende del punto de

vista, en otras palabras que los objetos reflejan la luz con la misma intensidad en todas

direcciones. Esto no se cumple en todo tipo de objetos, un ejemplo extremo de objetos que

no cumplen esta restricción son los espejos.

Las restricciones que se utilizaron en este trabajo las define Pajares (Pajares, 2008) de la manera

siguiente:

a) Semejanza: Las dos imágenes de la misma entidad 3D deben tener propiedades o atributos

similares.

b) Unicidad: Es una restricción basada en la geometría del sistema de visión y en la

naturaleza de los objetos de la escena. Para cada característica en una imagen debe haber

una única característica en la otra imagen, salvo que se produzca una oclusión y no haya

correspondencia de alguna característica. Esta restricción es el fundamento del proceso de

desambiguación que se realiza después de la fase de emparejamiento.

c) Relaciones estructuales: supone que los objetos están formados por aristas, vértices o

superficies con una cierta estructura y una disposición geométrica entre dichos elementos.

Una vez que se establecieron las restricciones que dirigieron esta investigación, así como los

detectores de características que se utilizaron para la primera fase de los algoritmos de

correspondencia, lo que siguió fue determinar qué técnicas de emparejamiento eran las más

adecuadas para lograr el objetivo.

Tesis de Maestría


A continuación se presentarán algunas clasificaciones de estas técnicas tomadas de (Cyganek,

2009), y posteriormente se citarán algunos artículos que hacen una revisión de ciertos algoritmos de

correspondencia.

Primera clasificación:

Los métodos estéreo, atendiendo al tipo de mapa de disparidad6 que generan, se clasifican en:

métodos densos y métodos dispersos, como se ilustra en la figura 2.1.

Figura 2.1. Clasificación de los métodos estéreo en métodos densos y métodos dispersos

(Cyganek, 2009).

Los métodos densos generan mapas de disparidad, en donde todos o casi todos los píxeles tienen

determinados valores de disparidad. Por otro lado, los métodos dispersos generan mapas de

disparidad que tienen valores de disparidad7 determinados solo para un conjunto selecto de puntos

(generalmente este conjunto contiene esquinas o bordes), el resto de los valores de disparidad se

obtienen por interpolación.

Segunda clasificación:

Los métodos de correspondencia estéreo pueden dividirse en dos grupos: métodos locales y

métodos globales.

Los métodos locales realizan la correspondencia entre puntos que provienen de distintas imágenes

tomadas de una misma escena a través de la comparación entre vecindades8 de estos puntos.

En contraparte, los métodos globales realizan la correspondencia entre puntos que provienen de

distintas imágenes tomadas de una misma escena a través de la comparación entre líneas o todos los

píxeles de las respectivas imágenes.

6 Es el conjunto de todas las disparidades entre dos imágenes de un par estéreo (González, 2011). 7 Es el valor absoluto de la diferencia de las primeras coordenadas de un punto en la vista 1 y su

correspondiente, en la vista 2, cuando la línea epipolar que los contiene es paralela a la línea base del

sistema óptico. Esta distancia es inversamente proporcional a la distancia del punto físico a las cámaras

(González, 2011). 8 Estas vecindades generalmente se determinan en función de una cierta distancia.

Métodos Estéreo

Métodos Densos

Métodos Dispersos

Tesis de Maestría


Existen varios métodos en ambos grupos, como se puede ver en la figura 2.2.

Figura 2.2. Clasificación de los métodos estéreo en métodos locales y métodos globales

(Cyganek, 2009).

En los artículos (Brown, 2003), (Graffigna, 2005) y (López, 2005) se pueden consultar las

definiciones de algunas de estas técnicas.

2.4. Artículos que hacen mención de algunas técnicas de correspondencia

Scharstein et al. (Scharstein, 2002) presentaron una clasificación de algunos algoritmos de

correspondencia densos para visión estéreo atendiendo a los diferentes costos computacionales,

métodos de agregación, y técnicas de optimización.

Brown et al. (Brown, 2003) realizaron una revisión del año 1993 al 2003 de los avances en la

computación estéreo, enfocándose en tres temas importantes: métodos de correspondencia, métodos

enfocados a problemas de oclusión e implementaciones en tiempo real. Todo esto con el fin de

proveer de tablas de referencia que den un panorama general de los tipos de algoritmos de

correspondencia que se están utilizando con sus ventajas y desventajas.

Como resultado de este trabajo se clasificaron algunos de los métodos de correspondencia estéreo

en métodos globales y métodos locales. Dentro de los métodos locales se consideraron los métodos

de correspondencia por bloques (métodos basados en área), optimización basada en el gradiente y

Métodos Estéreo

Métodos

Globales

Métodos

Locales

Pro

pag

ación

Belief

Pro

pag

ación

Din

ámica

Gráficas co

rte

Difu

sión n

o L

ineal

Méto

do

s Jerárqu

icos

(espacio

-escala)

Ten

sor v

otació

n

Co

rres

pon

den

cia

po

r C

arac

terí

stic

as

Co

rres

pon

den

cia

po

r Á

rea

Tesis de Maestría


emparejamiento por características. Entre los métodos globales se catalogaron los métodos de

programación dinámica, curvas intrínsecas, cortes de gráficas, difusión no lineal, propagación

creencia y acorrespondencia.

En particular Brown et al. definen los métodos de correspondencia por bloques como aquellos que

buscan el máximo puntaje de correspondencia o el mínimo error sobre una pequeña región,

típicamente usando variantes de correlación cruzada o métricas de rango robustas.

Los métodos de emparejamiento por características los definen como aquellos que buscan puntos

característicos de emparejamiento más que intensidades.

Además mencionan que los métodos locales son sensibles a regiones con textura uniforme en la

imagen y que en particular los métodos de correspondencia por bloques se caracterizan por ser

sensibles a discontinuidades profundas.

Kuhl (Kuhl, 2004) comparó tres algoritmos de correspondencia densos para visión estéreo que se

implementaron en una PC para calcular mapas de profundidad. A partir de esto se escogió el mejor

para implementarlo en un robot. Las técnicas utilizadas fueron SAD (Suma de Diferencias

Absolutas), SSD (Suma de Diferencias Cuadradas), Census y Modificación de Census y se

obtuvieron los resultados siguientes:

1. La modificación del algoritmo Census fue mucho más rápida que el propio algoritmo pero el

mapa de profundidad se redujo en calidad.

1. La implementación del algoritmo SAD dio como resultado mapas de profundidad adecuados.

2. El tiempo de ejecución del algoritmo SSD fue casi el doble que el del algoritmo SAD.

3. El mapa de profundidad que resultó del algoritmo SSD fue completamente similar al del

algoritmo SAD.

Respecto al tiempo de ejecución se eligió el algoritmo SAD, posteriormente reduciendo el área de

análisis y utilizando la restricción de unicidad se logró mejorar este algoritmo. Al final esa mejora

fue la que se implementó en el robot.

Graffigna et al. (Graffigna, 2005) especifican que las técnicas de correspondencia locales se pueden

dividir en dos grupos: las basadas en características, y las basadas en la correlación. Ambos tipos de

técnicas aunque conceptualmente son muy similares, son en cambio muy diferentes desde el punto

de vista de la implementación a la que conducen.

Los métodos basados en características restringen la búsqueda a un conjunto disperso de éstas.

Estos métodos emplean propiedades simbólicas y numéricas de las características, disponibles a

partir de los descriptores que se utilicen.

En los métodos basados en la correlación, los elementos a comparar son ventanas de la imagen de

dimensión fija, y el criterio de semejanza es una medida de la correspondencia entre las ventanas de

las dos imágenes.

López et al. (López, 2005) hacen una descripción de los algoritmos de correspondencia siguientes:

técnicas basadas en la correlación, algoritmo de Nishihara, funciones basadas en rango y censo,

técnicas de relajación, algoritmo de Marr-Poggio, algoritmo de Pollard Mayhew, Frisby, Técnicas

Tesis de Maestría


de grueso a fino, métodos basados en el gradiente, correspondencia entre características,

programación dinámica, curvas íntimas, métodos de predicción y verificación, métodos basados en

diferencias de fase, métodos para reducir la sensibilidad a las oclusiones.

En particular definen la técnica de correspondencia denominada correlación de área como aquella

que considera los valores de intensidad de los píxeles como una señal bidimensional, que en una de

las dos imágenes ha sufrido una traslación.

López et al. (López, 2005) mencionan que las técnicas relacionadas con el área como la de

correlación son muy sensibles a errores provocados por las discontinuidades en la profundidad, así

como a las regiones uniformes. Para solventar estos problemas, se proponen las técnicas basadas en

características las cuales limitan las regiones a analizar a características fiables de las imágenes,

como pueden ser los contornos, las curvas, etc.

2.5. Elementos a considerar en la elección de un algoritmo de correspondencia

Elegir entre un algoritmo de correspondencia u otro para su ejecución, depende de múltiples

situaciones, de todas Tell (Tell, 2002) distingue dos: posición de la cámara y tipo de escena.

Posición de la cámara

Aquí se determinan qué movimientos, entre distintas adquisiciones de imágenes, serán permitidos

para la cámara. Movimientos de cámara pequeños generan que los puntos correspondientes estén

cerca cada uno de una imagen de su correspondiente en la otra imagen y los vecinos alrededor de

estos puntos son similares. A los algoritmos que funcionan para este tipo de situaciones se les suele

llamar de línea base corta. Por otro lado, si la cámara tiene un movimiento o una rotación

significativa, ninguna de estas propiedades se mantendrá y entonces se tienen que aplicar algoritmos

de línea base larga.

La expresión “línea base” se refiere a la distancia entre los dos centros de la cámara de un sistema

de cámaras estéreo (Pajares, 2008). En este sentido las palabras “línea base larga” se usan para

denotar una situación donde dos imágenes no son “obviamente similares”, al menos para un sistema

de visión (Tell, 2002).

En este trabajo se supone que la línea base del par estereoscópico en análisis es corta, por lo tanto se

asume que ambas imágenes son similares en el sentido computacional. Esto significa que si las

imágenes son superpuestas una encima de la otra los puntos correspondientes se encuentran cerca y

los píxeles vecinos de alrededor de estos puntos deben de presentar características parecidas, en

consecuencia una simple correlación-cruzada deberá funcionar para el emparejamiento.

En general se asumen los supuestos siguientes para algoritmos de línea base corta:

1. Si las imágenes son sobrepuestas una encima de la otra, los puntos correspondientes se

encuentran cerca.

2. Los vecinos de alrededor de estos puntos son similares.

3. No existe una rotación o traslación significativa de la cámara entre las imágenes.

Tesis de Maestría


4. La longitud focal u otras propiedades intrínsecas de la cámara no cambiaron entre las

imágenes.

En contraste, para algoritmos de línea base larga, se hacen los supuestos siguientes:

1. Para cualquier punto, su punto correspondiente puede estar en cualquier parte de la otra

imagen.

2. Los vecinos alrededor de los puntos correspondientes eventualmente pueden exhibir

semejanza, pero desde el momento en que ellos fueron transformados por el movimiento de

la cámara, no es adecuado comparar directamente las vecindades entre sí.

3. Objetos que eran visibles en una imagen pueden estar ocluidos en la otra imagen.

4. El problema de la línea base larga es muy difícil de resolver.

La elección entre un algoritmo de correspondencia de línea base larga o una corta en una aplicación

conlleva un compromiso entre la realización de la correspondencia y la confiabilidad numérica.

Dada una línea base corta, es fácil encontrar varios puntos correspondientes, pero la disparidad de

estos puntos es muy pequeña comparada con la distancia de los objetos en la escena, la

incertidumbre de la profundidad estimada de la escena y el movimiento de la cámara son grandes.

Con una línea base larga, la profundidad y el movimiento estimado son más confiables, pero es más

difícil encontrar los puntos correspondientes.

También hay un compromiso entre usar una cantidad pequeña o grande de imágenes, ya que si se

quiere realizar una reconstrucción 3D del objeto, se requiere de una secuencia de video del objeto

desde distintas perspectivas para obtener resultados confiables.

Tipo de Escena

Otro elemento importante a considerar es el tipo de información que contienen las imágenes, por

ejemplo si ellas tienen textura o no. Un algoritmo que se ejecuta muy bien en ciertas condiciones

puede fallar en otras. Existen muchas propiedades de la escena entre ellas la posición de los objetos,

la cual afecta la ejecución de un algoritmo particular.

La primera distinción entre los algoritmos de correspondencia se manifiesta en su desempeño

dependiente del tipo de escena donde se adquieren las imágenes. Parece razonable pensar que un

algoritmo aproveche la mayor cantidad de información contenida en una imagen. Sin embargo,

dependiendo de la escena, la “mejor” información de una imagen puede variar. Por ejemplo, si se

supone que la escena contiene en su mayoría objetos con textura baja. En este caso, los bordes de

los objetos son probablemente fáciles de detectar en las imágenes. Por otro lado, si la escena

contiene muchos objetos texturizados, los bordes de los objetos pueden ser difíciles de distinguir a

partir de la textura de los objetos. En este caso, el uso de la textura para realizar la correspondencia

es potencialmente una mejor elección que el uso de los bordes.

La textura es ciertamente una propiedad importante, pero hay otras. La siguiente es una lista de

algunas consideraciones relacionadas con el contenido de la imagen a tener en cuenta durante la

elección de un algoritmo de correspondencia.

Tesis de Maestría


1. ¿La escena está texturizada?

2. ¿La textura se repite o no? Por ejemplo, la superficie de un escritorio de madera es

texturizado, pero su textura es casi periódica, por lo tanto este descriptor no puede ser

usado para distinguir dos partes distintas del escritorio. Esta propiedad es buena para el

reconocimiento de objetos, donde el propósito es reconocer el escritorio, pero mala para

encontrar puntos correspondientes, donde el objetivo es reconocer partes específicas del

escritorio.

3. ¿Existen objetos en la escena que son planos o curvos por partes?

4. ¿Pueden ocurrir reflexiones especulares sobre los objetos?

5. ¿Se puede usar el color para distinguir los objetos?

6. ¿Oclusiones importantes ocurrirán si se mueve la cámara a una nueva posición?

7. ¿La escena contiene muchas discontinuidades profundas?

En función de la propiedad de textura en la escena se pueden distinguir dos tipos de escenas:

escenas texturizadas y escenas estructuradas.

Mikolajczyk et al. (Mikolajczyk, 2006) definen una escena estructurada como aquella que genera

imágenes que contienen regiones homogéneas limitadas por bordes distintivos. Definen a una

escena texturizada como aquella que genera imágenes que contienen texturas repetitivas de formas

diferentes.

Li et al. (Li, 2000) definen una escena texturizada como aquella que genera imágenes que están

compuestas por estructuras repetitivas y aparecen como una superficie de textura única.

Para fines prácticos en este trabajo se nombrarán como imágenes texturizadas a aquellas que se

obtuvieron de una escena texturizada y en contraparte se denominarán como imágenes estructuradas

aquellas que se obtuvieron de una escena estructurada.

Lepistö et al. (Lepistö, 2003) definen dos tipos de texturas: texturas homogéneas y texturas no

homogéneas. Las texturas homogéneas se caracterizan porque sus propiedades de textura son

constantes, por otro lado las texturas no homogéneas se identifican porque sus características de

textura no son constantes en cada parte de la muestra de textura.

Es importante hacer notar que la mayoría de las texturas naturales son estocásticas y no

homogéneas.

En [1] se menciona que las escenas texturizadas generan imágenes en donde hay una gran cantidad

de esquinas como componentes y, en contraparte, en las escenas estructuradas se generan imágenes

que son más fáciles de segmentar.

En los artículos siguientes se llevaron a cabo correspondencias entre imágenes que provenían de

entornos distintos al terrestre.

Tesis de Maestría


García et al. (García, 2001) presentaron un enfoque, basado en la textura, para mejorar la fiabilidad

de la correspondencia de puntos, relacionando dos imágenes consecutivas de una secuencia de

imágenes tomadas a una velocidad de 3 f.p.s. por una cámara enfocada hacia el fondo del mar,

mientras era llevada por un robot marino.

Bonfim et al. (Bonfim, 2010) evaluaron y compararon la efectividad de los algoritmos de

correspondencia, SIFT y SURF, sobre un conjunto de imágenes que provinieron de escenarios reales

tomadas desde un UAV (Vehículo Aéreo no Tripulado).

Kenton et al. (Kenton, 2010a) examinaron el desempeño de los detectores Harris y Hessian,

basados en esquinas y blobs, respectivamente; así como de los descriptores de características SIFT y

GLOH (Histogramas de Orientación y Localización por Gradiente), tanto de manera independiente

como de manera conjunta. Esto mediante la repetibilidad en la detección y la precisión del

emparejamiento de los puntos característicos, extraídos en imágenes tomadas bajo del agua.

Kenton et al. (Kenton, 2010b) presentaron un método nuevo para realizar la correspondencia de

características entre imágenes que se construyeron de manera sintética, a través de simular

diferentes condiciones de la escena dentro del agua.

2.6. Algoritmos de emparejamiento utilizados en la tesis

En esta investigación se tienen los supuestos teóricos de que los videos se tomaron con una cámara

cuyos parámetros, en general, permanecieron invariantes durante la adquisición de las secuencias.

Esto significa que la cámara no tuvo movimientos bruscos, lo que se reflejaría en traslaciones o

rotaciones leves entre un fotograma y su siguiente. Además se supone que la cámara no

experimentó reajustes, por ejemplo con un “zoom”, durante la adquisición de las secuencias.

Asimismo, la correspondencia de puntos se planteó para pares consecutivos de fotogramas.

Estas consideraciones fueron el motivo para elegir algoritmos de línea base corta para cada una de

las fases del algoritmo de correspondencia implementado.

En atención a la sugerencia que se hace en (López, 2005) para evitar errores provocados por las

discontinuidades en la profundidad y dado que no es un objetivo de esta tesis obtener el mapa de

disparidad, se consideraron únicamente las características destacadas de ambas imágenes para llevar

a cabo el emparejamiento. Aún así la cantidad de parejas potenciales, eventualmente, puede ser muy

grande, así que, apoyados en los supuestos teóricos de esta investigación se postuló que los puntos

correspondientes no se encontraban tan lejanos y que por consiguiente se podía utilizar un algoritmo

de proximidad para reducir el espacio de búsqueda de parejas.

Para ello se aplicó una estrategia de búsqueda de píxeles, denominada Épsilon-bola, inspirada en los

artículos: (Kenton, 2010a), (Kenton, 2010b) y (Yen, 2010), en los que se utiliza un algoritmo del

tipo vecinos más cercanos para una primera búsqueda de parejas potenciales.

Para la fase propiamente de emparejamiento, en donde se elige sólo una pareja para los puntos, se

optó por algoritmos de línea base corta que involucraran técnicas relacionadas con el área, usando

variantes de correlación como son SAD o VNC (Correlación de Varianza Normalizada), o en su

defecto usando métricas sobre descriptores de una pequeña región con alguno de los algoritmos

denominados Textura y Color respectivamente.

Tesis de Maestría


Las técnicas relacionadas con el área usan medidas de semejanza entre ventanas de la imagen de

dimensión fija, frecuentemente centradas en el indicador de la característica destacada en cuestión,

y el criterio de semejanza es una medida de la correspondencia entre las ventanas de las dos

imágenes. De acuerdo a (Graffigna, 2005), (Cyganek, 2009) y (Kuhl, 2004) se pueden utilizar estas

medidas de semejanza para realizar la comparación entre las ventanas que sirven como vecindad de

los indicadores de las características destacadas, ya que se ha mostrado, experimentalmente, que

este tipo de estrategias funcionan relativamente bien para algoritmos de línea base corta.

Se revisaron varias técnicas de similitud de área, pero porque aparecen con más frecuencia en los

artículos consultados, de entre ellas se eligieron para su implementación dos técnicas de

correlación: el algoritmo SAD y VNC, y dos técnicas que involucraban una métrica: distancia

Manhattan9 aplicada a vectores con descriptor de color y distancia Manhattan aplicada a vectores

con descriptores de textura.

La SAD según Graffigna et al. (Graffigna, 2005) es un índice fácil de implementar e insume menor

costo computacional que el resto de los índices de correlación, aspecto importante si se considera la

implementación en tiempo real. Aunque, según (Cyganek, 2009), tiene el inconveniente de ser muy

sensible a puntos atípicos.

De a cuerdo con Graffigna et al. (Graffigna, 2005) la correlación cruzada normalizada (NCC) es un

índice que permite al par estéreo independizarse de las diferencias de brillo y de contraste, gracias a

la normalización que se realiza respecto del valor medio y de la desviación estándar de las ventanas

de cálculo. El índice VNC es muy parecido a NCC y por ese motivo mantiene todas sus bondades,

además de que según Vincent et al. (Vincent, 2001), VNC tiene la ventaja de producir resultados

estables y confiables sobre un rango amplio de puntos de vista. Los valores obtenidos con este

índice varían entre -1 y 1 (inclusive), lo que facilita la elección de un umbral si es que así se desea.

Según López et al. (López, 2005) utilizar técnicas de correlación de área ofrece buenos resultados

sobre imágenes con textura importante, sin embargo, tiene los inconvenientes de: presentar

problemas con imágenes con elevadas discontinuidades de superficie, es muy sensible a variaciones

fotométricas debidas a sombras o reflejos y requiere un proceso posterior de eliminación de falsas

correspondencias.

García et al. (García, 2001) sugieren considerar descriptores de textura para el emparejamiento y

por ello se implementaron, en dos funciones por separado, descriptores de textura y color para el

emparejamiento de puntos.

En la tabla 2.2, se da un resumen de las técnicas que se identificaron para cada etapa del algoritmo

de correspondencia de línea base corta.

Tabla 2.2. Técnicas para algoritmos de correspondencia de línea base corta.

Técnicas Autores

Fase

Harris

MSER

(Harris, 1988)

(Konstantinos, 2000)

Extracción de Características

Destacadas

9 En (Lipschutz, 1965) se define como la función , donde

para: .

Tesis de Maestría


Star

(Matas, 2002)

(Mikolajczyk, 2005)

(Tuytelaars, 2008)

(Ebrahimi, 2009)

(Kenton, 2010a)

Vecinos más cercanos (Kenton, 2010a)

(Kenton, 2010b)

Primera búsqueda de pares de

puntos correspondientes

Técnicas de similitud de área a

través de correlación:

SAD , NCC o VNC

(Vincent, 2001)

(Brown, 2003)

(Graffigna, 2005)

(Kuhl, 2004)

(López, 2005)

(Cyganek, 2009)


Técnicas de similitud de área a

través de métricas de descriptores

de textura o color

(García, 2001)


Tesis de Maestría


Capítulo 3

3. Descripción de los algoritmos utilizados

A continuación se describen, brevemente, los algoritmos de detección de características, búsqueda

de puntos, emparejamiento de puntos y desambiguación, todos ellos componentes de los algoritmos

de correspondencia implementados en esta tesis:

3.1. Algoritmos de detección de características

En seguida se presentan los algoritmos que se utilizaron en la fase de detección de características de

la metodología propuesta.

3.1.1. Harris

Harris es un detector de esquinas que se aplica en imágenes en escala de grises y se basa en la auto-

correlación de la señal. Los artículos (Harris, 1988) y (Konstantinos, 2000) describen el algoritmo

básico de Harris en cinco pasos básicos:

Teniendo en cuenta una ventana W de dimensión de n×n, para cada píxel (i,j) de la imagen se hace

lo siguiente:

1. Calcular y utilizando diferencias de primer orden n×n para las derivadas parciales.

2. Calcular las tres cantidades ,

y .

3. Utilizando un núcleo Gaussiano con desviación estándar , ecuación (1):

obtener las medias promediadas ,

y utilizando la vecindad n×n y los valores

obtenidos en 3. Esta media es una media ponderada de los valores de la vecindad, que se

realiza a través de la convolución Gaussiana.

4. Evaluar los autovalores y de la matriz A, ecuación (2):

=

(2)

Si los autovalores de la matriz superan un determinado valor de umbral, el pixel, (i,j), asociado

se considera un punto de interés.

El algoritmo de detección de puntos característicos de Shi y Tomasi, (Shi, 1994) se define en

función del detector de esquinas de Harris. En este algoritmo se utiliza el min( , ) como el

indicador de intensidad de la esquina en lugar de y .

Tesis de Maestría


El indicador de característica que se usará para las características de Harris serán las coordenadas

de los puntos esquina.

Este algoritmo se implementó con una función denominada Harris que se describe en el anexo A y

para que esta función se ejecute es necesario que se le ingrese un número entero positivo que funge

como cota superior del número de esquinas. Una vez establecido este número permanecerá fijo

durante la doble aplicación de esta función: primero para obtener las características destacadas de la

vista 1 y después para obtener las características destacadas de la vista 2.

3.1.2. Star

En (Ebrahimi, 2009) Ebrahimi et al. dan una breve explicación del algoritmo CensurE

resumiéndolo en tres pasos básicos:

1. Calcular la respuesta a una laplaciana de una gaussiana bi-nivel simplificada y las

respuestas débiles son filtradas, dando como resultado la detección de bordes.

2. Detectar los extremos locales.

3. Detectar los extremos locales esquina con respuesta fuerte usando los criterios de Harris.

La diferencia entre CenSurE y Star es que mientras que CenSurE utiliza polígonos tales como

cuadrados, hexágonos y octágonos, Star utiliza círculos que se simulan con dos cuadrados

superpuestos uno vertical y otro rotado 45 grados formando una estrella, como se muestra en la

figura 3.1.

Figura 3.1. Cuadrados superpuestos que simulan un círculo.

Star detecta blobs como característica destacada y el indicador que se usa para estas características

son las coordenadas del centro del blob las cuales se pueden extraer de la estructura CvStarKeypoint

que se define en el anexo A.

Este algoritmo se implementó con una función denominada StarKeyPoint1 la cual se describe en el

anexo A y durante el proceso de correspondencia se ejecuta dos veces: primero para obtener las

características destacadas de la vista 1 y después para obtener las características destacadas de la

vista 2.

Tesis de Maestría


3.1.3. MSER

Matas et al. en el artículo (Matas, 2002) describen un algoritmo básico de regiones extremas

máximamente estables que se puede explicar de la siguiente manera:

Sea una imagen I como un mapeo , donde S es el rango de intensidades de la imagen

en niveles de grises. Generalmente S = {0,...,255}; sin embargo, el algoritmo de regiones extremas

se puede definir para S = R ya que solo se pide que S sea totalmente ordenado, i.e. que exista una

relación binaria ≤ en S que sea reflexiva, antisimétrica y transitiva.

Se puede hacer una binarización de una imagen estableciendo que todos aquellos píxeles de la

imagen cuyo nivel de gris sea menor que cierto umbral prefijado sean “negro” y, en contraparte,

aquellos píxeles cuyo nivel sea mayor o igual que dicho umbral sean “blanco”.

Si se consideran todos los umbrales posibles de niveles de gris en una imagen I, generalmente de 0

a 255, se podría hacer una sucesión de imágenes binarizadas , donde el fotograma t-ésimo

correspondería al umbral t. Así se tendría que la imagen correspondería a una imagen donde

todos sus píxeles son “blanco”, y conforme t va aumentado en las correspondientes imágenes irán

apareciendo más píxeles “negro” hasta que, finalmente, en donde todos los píxeles son

“negro”.

Se distinguen dos tipos de regiones dentro de las imágenes binarizadas de la siguiente manera:

Q={qDq es “blanco”}, también será una región de I.

es una relación de conexidad que se define de la siguiente manera:

Sean D, p A q si y solo sí .

Una región Q de D se dice que es conexa si y solo sí para cada p, q Q existe una sucesión

de elementos de Q tal que .

La frontera de una región Q se define como:

Se tiene que es una región extrema si y solo sí es una región conexa tal que se cumple que I(p) > I(q). (región de intensidad máxima) o I(p) < I(q) (región de

intensidad mínima).

Si se considera una sucesión de regiones extremas anidadas, , i.e.

. Una región extrema es maximalmente estable si y solo sí la razón de cambio de

la función de área

tiene un mínimo local en i*, aquí S es un parámetro del

método.

El indicador de característica que se usa para las características que detecta Mser son las

coordenadas del centro de un rectángulo que circunscribe a la región extrema máximamente estable

en análisis.

Este algoritmo se implementó con una función denominada Mser1 la cual se describe en el anexo A

y durante el proceso de correspondencia se ejecuta dos veces: primero para obtener las

Tesis de Maestría


características destacadas de la vista 1 y después para obtener las características destacadas de la

vista 2.

3.2. Algoritmo de búsqueda de puntos

A continuación se dará una pequeña descripción del algoritmo Épsilon-bola, el cual se utilizó en la

fase de búsqueda de parejas potenciales.

3.2.1. Algoritmo de búsqueda Épsilon-bola

Épsilon-bola es un algoritmo del tipo de vecinos más cercanos, en donde se establece un umbral y

todos aquellos indicadores de características destacadas de la vista 2 cuya distancia a un indicador

de la vista 1 sea menor que el umbral previamente establecido, se convierten automáticamente en

parejas potenciales del indicador de la vista 1, como se muestra en la figura 3.2. Si se repite este

proceso para cada uno de los indicadores de la vista 1 se obtiene un primer conjunto de

correspondencias en donde a cada indicador de la vista 1 se le puede asignar más de una pareja

potencial de la vista 2.

Este mismo proceso se realiza pero ahora para los indicadores de características destacadas de la

vista 2 y con ello se obtendrá otro arreglo en donde a cada indicador de la vista 2 se le puede

asignar más de una pareja potencial de la vista 1.

Figura 3.2. Identificación de puntos a través del algoritmo Épsilon-bola.

Este algoritmo se implementó con una función denominada Ebola la cual se describe en el anexo A.

Para que esta función se ejecute es necesario que se le ingresen el radio (umbral) de la bola y la

distancia que se desean utilizar. Una vez establecidos estos valores permanecerán fijos durante la

doble aplicación de esta función: primero para obtener la búsqueda de la vista 1 a la vista 2 y

después para obtener la búsqueda de la vista 2 a la vista 1.

Tesis de Maestría


Las distancias elegibles son la distancia Manhattan y la distancia euclidiana10

. Si se elige la

distancia euclidiana la forma de la bola será circular, mientras que si se elige la distancia Manhattan

la forma será romboidal. Además se sabe por experiencia que la distancia Manhattan consume

menos tiempo de ejecución que la distancia euclidiana.

3.3. Algoritmos de emparejamiento de puntos

Las técnicas de similitud que se utilizaron para la fase de emparejamiento del algoritmo de

correspondencia se describen a continuación.

3.3.1. Suma de diferencias absolutas (SAD)

Para obtener la similitud de correlación entre dos puntos correspondientes potenciales se aplican

ventanas cuadradas de tamaño 1111 denominadas y

, centradas en los puntos respectivos del par estereoscópico. Cada una de

estas ventanas contiene las intensidades de aquellos puntos cuya distancia de Chebyshev11

aplicada

a sus coordenadas y las coordenadas del centro de la ventana es menor o igual a 5.

La semejanza entre estas ventanas se obtiene a través de un índice denominado GS (Grado de

Semejanza). A continuación se definen, según Graffigna et al. (Graffigna, 2005), los grados de

semejanza correspondientes a SAD en la ecuación (3) y NCC en la ecuación (4).

Sean:

En el caso de SAD el índice GS se obtiene con la suma que se expresa en la ecuación (3):

(3)

El GS para la NCC centrada en la media se obtiene con el cociente que se expresa en la ecuación

(4):

(4)

10

En (Lipschutz, 1965) se define como la función , donde

para: .

11 En (Lipschutz, 1965) se define como la función , donde

para: .

Tesis de Maestría


3.3.2. Correlación de varianza normalizada (VNC)

VNC se considera una modificación de NCC y en (Vincent, 2001) Vincent et al. definen el GS para

VNC como el cociente que se expresa en la ecuación (5):

(5)

Para llevar a cabo el proceso de emparejamiento de la vista 1 a la vista 2 utilizando similitud de área

por correlación, independientemente de si el GS se calcula con SAD o con VNC, es el siguiente: se

fija un indicador de característica destacada de la vista 1 y luego se forma una lista con los índices

GS obtenidos de calcular la similitud de correlación de dicho punto con sus parejas potenciales de la

vista 2, las cuales resultaron de la fase de búsqueda previa. En seguida se elige como pareja del

punto de la vista 1 aquella pareja potencial de la vista 2 que arroje el GS mínimo, si existen más de

un indicador de la vista 2 que cumpla con esta condición de entre éstos se elige el primero que

aparece en la lista. Este proceso se repite para cada uno de los indicadores de características

destacadas de la vista 1 con lo que se logra que éstos tengan solamente una pareja.

El proceso de emparejamiento de la vista 2 a la vista 1 se realiza de manera análoga y también,

finalizado este proceso, lo que resulta es que a cada uno de los indicadores de la vista 2 le toque

sólo una pareja.

La función que se implementó para realizar los emparejamientos usando el índice SAD se llama

SAD y la que se implementó para realizar los emparejamientos usando el índice VNC se llama VNC,

ambas funciones se describen en el anexo A. Durante del proceso de emparejamiento la función de

correlación (SAD o VNC) se ejecuta dos veces: primero para obtener el emparejamiento de la vista 1

a la vista 2 y después para obtener el emparejamiento de la vista 2 a la vista 1.

3.3.3. Algoritmo para descriptor de color

Se implementó un descriptor de color consistente en un vector de tamaño 3 cuyas componentes

están normalizadas como se muestra en la expresión (6):

(6)

Donde: suma =

Esto significa que la primera componente de esta terna corresponde al cociente de la suma de color

rojo entre la suma de las sumas de color rojo, verde y azul; la segunda componente corresponde al

cociente de la suma de color verde entre la suma de las sumas de color rojo, verde y azul y,

finalmente, la tercera componente corresponde al cociente de la suma de color azul entre la suma de

las sumas de color rojo, verde y azul. Estos tres colores son extraídos de los píxeles de un disco

centrado en el indicador de la característica destacada. En adelante se hará referencia al vector (6)

como terna de color.

Tesis de Maestría



por métrica para descriptor de color se realiza lo siguiente: se fija un indicador de característica

destacada de la vista 1 y luego se forma una lista con las distancias aplicadas en la terna de color de

este punto y la terna de color de alguna de sus parejas potenciales de la vista 2, las cuales resultaron

de la fase de búsqueda previa. Se elige como pareja del punto de la vista 1 aquel punto de la vista 2

que arroje la distancia más pequeña, si existe más de un indicador de la vista 2 que cumpla con esta

condición de entre éstos se elige el primero que aparece en la lista. Este proceso se repite para cada

uno de los indicadores de características destacadas de la vista 1 con lo que se logra que éstos

tengan solamente una pareja.


finalizado este proceso, lo que resulta es que cada uno de los indicadores de la vista 2 tenga sólo

una pareja.

Este algoritmo se implementó con una función denominada Color la cual se describe en el anexo A

y para que ésta se ejecute es necesario que se ingresen los valores del radio del disco y la distancia

que se desean utilizar. Una vez establecidos estos valores permanecerán fijos durante la doble

ejecución de esta función: primero para obtener el emparejamiento de la vista 1 a la vista 2 y

después para obtener el emparejamiento de la vista 2 a la vista 1.

Las distancias elegibles son la distancia Manhattan y la distancia euclidiana. Si se elige la distancia

euclidiana la forma del disco será circular, mientras que si se elige la distancia Manhattan la forma

del disco será romboidal.

3.3.4. Algoritmos para descriptores de textura

De (Pajares, 2008) se definen descriptores estadísticos de primer y segundo orden los cuales se

apoyan principalmente en estadísticos de histograma de niveles de gris de una imagen. A

continuación se describen, brevemente, los que se implementaron en este trabajo.

Los estadísticos de primer orden son calculados a partir de los valores de gris originales de la

imagen y su frecuencia, como la media, varianza, desviación estándar. En estas medidas no se

considera la relación entre los píxeles. A continuación se definen los que se utilizaron en este

trabajo.

Sean:

L = el número de clases a considerar en el histograma de grises, generalmente 255.

= el representante de la clase i-ésima del histograma de grises (i {1,2, …,L}).

= frecuencia relativa de la clase i-ésima del histograma de grises.

Intensidad media [m]: Indica la intensidad media de la imagen e informa sobre el brillo general de

la imagen, esto es una imagen brillante tendrá una media alta mientras que por el contrario, una

imagen oscura poseerá una media baja. Se calcula usando la ecuación (7).

(7)

Tesis de Maestría


Varianza : Indica la medida de contraste de intensidad, una varianza alta corresponde a

una imagen con contraste alto, y viceversa. Se calcula usando la ecuación (8).

= (8)

Momento n-ésimo de z respecto de la media [ : La interpretación de este descriptor

depende del valor de n. Por ejemplo, el momento de tercer grado es una medida de oblicuidad del

histograma, mientras que el de cuarto orden es una medida de cuán plano es el histograma. A partir

del momento de quinto orden no es tan fácil relacionar los momentos con la forma del histograma,

pero sirven para obtener más información cuantitativa de discriminación de texturas. Se calcula

usando la ecuación (9).

(9)

Donde m es el valor medio de z y por tanto la intensidad media de la imagen.

Coeficiente R: Indica la suavidad relativa, es 0 para áreas con intensidad constante y es 1 para

valores grandes de . Se calcula usando la ecuación (10).

(10)

Por otro lado, los estadísticos de segundo orden son las medidas que consideran la relación de

coocurrencia entre grupos de los píxeles de la imagen original y a una distancia dada.

Una forma de introducir este tipo de información en el proceso de análisis de textura consiste en

considerar no solamente la distribución de intensidades, sino también las posiciones de píxeles que

tienen iguales, o casi iguales, valores de intensidad. Este método se conoce como matriz de

coocurrencia.

A partir de estadísticas de nivel de gris de segundo orden se obtienen las matrices de dependencia

espacial de nivel de gris. Sea P un operador de posición definido por el cual

indica una dirección específica (o bien para todas: 0º, 45º, 90º y 135º) entre los píxeles vecinos

dentro de una ventana móvil dentro en la imagen analizada, ver figura 3.3.

135º 90º 45º

6 7 8

5 X 1

4 3 2

225º 270º 315º

Figura 3.3. Los 8 vecinos del píxel de referencia X de acuerdo al ángulo utilizado en el

cálculo de la matriz de coocurrencia para un desplazamiento d=1.

0º 180

º

Tesis de Maestría


La simetría es necesaria para el cálculo de la matriz de coocurrencia, y esto se logra sumándole a

esta matriz su matriz transpuesta.

Una vez obtenida la matriz simétrica el paso siguiente es expresar esta matriz como probabilidad.

La definición más simple de la probabilidad es: “el número de veces que un evento ocurre, dividido

por el número de posibles eventos” y se calcula usando la ecuación (11).

(11)

Donde:

i es el número de filas y j es el número de columnas.

V es el valor de la celda (i,j) en la ventana.

es la probabilidad en la celda i, j.

N es el número de filas o columnas.

La ecuación (11) transforma la matriz de coocurrencia en una aproximación de la tabla de

probabilidad. Este proceso se denomina normalización de la matriz.

Hasta este punto se ha detallado como se crea una matriz normalizada, expresada como

probabilidad, para una determinada relación espacial entre dos píxeles vecinos, . Una vez

construida, de esta matriz pueden derivarse 9 variables estadísticas de segundo orden que sirven de

descriptores texturales, los cuales formarán el vector de características de coocurrencia y que harán

posible caracterizar con un conjunto de valores cuantificables cada imagen analizada.

Probabilidad Máxima: Es el valor máximo de las entradas de la matriz . Se calcula usando la

expresión (12).

(12)

Momento de distinción de elementos de orden k: Se calcula usando la expresión (13).

(13)

Homogeneidad también llamado momento inverso de distinción de elementos de orden 2: Es el

opuesto al contraste y se calcula mediante la expresión (14).

(14)

Entropía: Este descriptor mide la aleatoriedad de la imagen, alcanzando su máximo cuando todos

los elementos de la matriz de coocurrencia son iguales. Se calcula usando la expresión (15).

(15)

Se asume que (0)( ) = 0.

Tesis de Maestría


Uniformidad: Energía (o momento angular de segundo orden). Esta medida da valores altos

cuando en la matriz de coocurrencia tiene pocas entradas de gran magnitud, y es baja cuando todas

las entradas son similares. Si todos los píxeles son iguales la energía es mínima. Es una medida de

homogeneidad local. Se calcula mediante la expresión (16).

(16)

Correlación: Algunas propiedades de la correlación son: un objeto tiene más alta correlación

dentro de él que entre objetos adyacentes y píxeles cercanos están más correlacionados entre sí que

los píxeles más distantes. Este coeficiente se calcula usando la expresión (17).

(17)

donde:

Tonalidad: Lo primero que se debe calcular es la media de la matriz de coocurrencia, tanto para

filas como para columnas. La media de la matriz de coocurrencia no es simplemente el promedio de

los valores originales de los niveles de gris en la ventana. El valor del píxel no es ponderado por su

frecuencia por sí mismo, sino por la frecuencia de su coocurrencia en combinación de un

determinado valor del píxel vecino. Se calcula la tonalidad a través de la expresión (18).

(18)

donde:

Importancia: Medida similar a la tonalidad cuya expresión viene dada por (19).

(19)

donde:

Inercia (o contraste): Es una medida de la variación local en una imagen. Alcanza un valor alto

cuando la imagen tiene mucho contraste y tiene un valor bajo cuando los valores altos de la matriz

están cerca de la diagonal principal. Se calcula usando la expresión (20).

(20)

Tesis de Maestría


El vector de características de coocurrencia estará formado por 64 elementos, ya que a partir de

cada imagen se calculan sus ocho matrices de coocurrencia de niveles de grises (GLCM), una en

cada orientación principal: 0º, 45º, 90º, 135º, 180º, 225º, 270º y 315º, después de cada una de esas

matrices se obtienen las ocho características anteriores.

El vector final de descriptores utilizado para determinar texturas se construye uniendo las 6

características de histograma con las 64 características de coocurrencia, obteniendo un vector de 70

elementos para cada uno de los puntos analizados, al que se le denominó vector de textura.

Los estadísticos de un orden superior a dos no se consideraron ya que, aunque su cálculo es

teóricamente posible, se requiere mucho tiempo y su resultado es de difícil interpretación.


por métrica para descriptor de textura se realiza lo siguiente: se fija un indicador de característica

destacada de la vista 1 y luego se forma una lista con las distancias aplicadas en el vector de textura

de ese punto y el vector de textura de alguna de sus parejas potenciales de la vista 2. Se elige como

pareja del punto de la vista 1 aquel punto de la vista 2 que arroje la distancia Manhattan más

pequeña, si existen más de un indicador de la vista 2 que cumpla con esta condición de entre éstos

se elige el primero que aparece en la lista. Este proceso se repite para cada uno de los indicadores de

características destacadas de la vista 1 con lo que se logra que éstos tengan solamente una pareja.


finalizado este proceso, lo que resulta es que cada uno de los indicadores de la vista 2 tenga sólo

una pareja.

Este algoritmo se implementó con una función denominada Textura la cual se describe en el anexo

A. Para que esta función se ejecute es necesario que se ingrese el número de unidades de

desplazamiento que se requiere para el cálculo de la matriz de coocurrencia. Una vez establecido

este número permanecerá fijo para la doble aplicación de esta función: primero para obtener el

emparejamiento de la vista 1 a la vista 2 y después para obtener el emparejamiento de la vista 2 a la

vista 1.

3.4. Algoritmo de desambiguación

Después de que la fase de emparejamiento logró que tanto los indicadores de características de la

vista 1 como los de la vista 2 tuvieran solamente una pareja lo que sigue es procurar que ninguno de

estos indicadores sea elegido por más de un indicador de la otra vista. Para ello, simplemente, se

eligen como pares estereoscópicos aquellas parejas en donde ambos indicadores se hayan elegido

mutuamente.

Tesis de Maestría


Capítulo 4

4. Diseño e implementación del sistema

En este capítulo se muestra el diseño que se utilizó para llevar a cabo la implementación del sistema

denominado Correspondencia.

4.1. Introducción

El fin de esta tesis no era realizar un sistema computacional per se, sino que se visualizó como un

medio para generar algoritmos de correspondencia para posteriormente compararlos y generar

conocimiento. Para ello se pensó en un sistema que fuera lo más rápido, flexible y manejable

posible.

Por flexible se entiende que se pudieran hacer cambios al código para que el sistema pudiera

realizar distintos tipos de pruebas y manejable en el sentido de que el código complejo se pueda

dividir en varios programas más simples, y éstos a su vez en otros programas más simples, así hasta

obtener programas lo suficientemente simples como para poder ser analizados fácilmente.

Por este motivo se ideo un sistema de programación modular con interfaz de consola, en donde el

usuario ingresara los parámetros de manera manual.

4.2. Arquitectura del sistema

El algoritmo que se implementó se llama Correspondencia y de acuerdo al comportamiento que

tome será el algoritmo que se ejecutará. Por este motivo se eligió para su implementación el patrón

de diseño Template Method. Es un patrón que define una estructura algorítmica en la súper clase,

delegando la implementación a las subclases. Esto significa que define una serie de pasos que

determinarán el comportamiento del algoritmo a través de la redefinición en las subclases a través

de una estructura de herencia, en la cual la superclase sirve de plantilla de los métodos en las

subclases.

Este patrón es el adecuado para implementar el algoritmo genérico denominado Correspondencia,

ya que este algoritmo es común para muchas clases12

, pero con pequeñas variaciones entre una y

otras. Además de que este patrón evita la repetición de código y por tanto la aparición de errores.

En la figura 4.1 se muestra el diagrama de clases13

que describe la estructura del sistema

implementado.

12

Clase es una entidad que encapsula información y comportamiento de un objeto (Joyanes, 2008). 13

Es un diagrama que muestra un conjunto de clases, interfases y colaboraciones y sus relaciones; los

diagramas de clases cubren la vista de diseño estática de un sistema (Booch, 2005).

Tesis de Maestría


#CD()

#Buscar()

#Corresp()

+Correspondencia()

+~Correspondencia()

+SetCad()

+Calcular()

#NumAlg : int = 1

#secs : double = 0

#d1 : int = 0

#x1 : int = 200

#K1 : int = 3

#eps1 : int = 30

#d : uint = 1

#ud : int = 2

#es1 : int = 2

#es2 : int = 2

#m1 : int = 2

#m2 : int = 2

#m : int = 2

#esq1 : int = 0

#esq2 : int = 0

#M1 : int = 0

#M2 : int = 0

#M : int = 0

#ruta1 : unsigned char = 0

#ruta2 : char = 0

#ruta3 : char = 0

#ruta4 : char = 0

#img1 : <sin especificar> = 0



#im4 : <sin especificar> = 0

#im5 : <sin especificar> = 0

Correspondencia

+Harris()

+~Harris()

#CD()

Harris

+StarKeyPoint1()

+~StarKeyPoint1()

#CD()

StarKeyPoint1

+Mser1()

+~Mser1()

#CD()

Mser1

+Fact1()

+~Fact1()

#Buscar()

Fact1

+Fact2()

+~Fact2()

#Buscar()

Fact2

+Fact3()

+~Fact3()

#Buscar()

Fact3

+Uno()

+~Uno()

#Corresp()

Uno

+Dos()

+~Dos()

#Corresp()

Dos

+Doce()

+~Doce()

#Corresp()

Doce

+Once()

+~Once()

#Corresp()

Once

+Diez()

+~Diez()

#Corresp()

Diez

+Nueve()

+~Nueve()

#Corresp()

Nueve

+Ocho()

+~Ocho()

#Corresp()

Ocho

+Siete()

+~Siete()

#Corresp()

Siete

+Seis()

+~Seis()

#Corresp()

Seis

+Cinco()

+~Cinco()

#Corresp()

Cinco

+Cuatro()

+~Cuatro()

#Corresp()

Cuatro

+Tres()

+~Tres()

#Corresp()

Tres

Fin1 Fin2

Fin3

Fin4

Fin5Fin6Fin7

Fin8

Fin9

Fin10

Fin13

Fin

14 Fin11Fin12 Fin17Fin18

Fin21

Fin22

Fin19

Fin20

Fin15

Fin

16

Figura 4.1. Diagrama de clases.

En el anexo A se da una breve descripción de los atributos y métodos de la clase correspondencia.

Tesis de Maestría


En la figura 4.2 se visualiza el orden del llamado de los métodos de la clase Correspondencia para

llevar a cabo cada una de las fases del algoritmo Correspondencia.

Figura 4.2. Diagrama de flujo14

para la ejecución del proceso de correspondencia.

En el anexo A se indican las funciones que se ejecutan para realizar los procesos desde la detección

de características hasta la desambiguación del diagrama de la figura 4.2.

4.3. Especificaciones técnicas

Entre los requerimientos de hardware y software se considera a una computadora que tenga las

características siguientes:

Sistema Operativo: Windows 7 o versiones superiores.

Memoria RAM: Mínimo 4GB

Disco duro: 500GB libres

Procesador: AMD II Dual-Core P320 o superior.

El software que se necesita para la ejecución del sistema es la plataforma de desarrollo NetBeans

IDE 6.8 junto con el lenguaje de programación C++ y algunas librerías de OpenCV 2.1.

14

Es un diagrama que utiliza símbolos estándar para escribir los pasos de un algoritmo unidos por flechas,

denominadas líneas de flujo, que indican la secuencia en la que se debe ejecutar (Joyanes, 2008).

CDs Vista 2 Búsqueda

Vista 1 Búsqueda

Vista 2

Correspondencia

Vista 2

Correspondencia

Vista 1

CDs Vista 1

Repositorios

Inicio

Archivos

Imagen y Excel

Desplegado Desambiguación

Fin

Tesis de Maestría


Capítulo 5

5. Descripción de los repositorios

Los videos que se analizaron en este trabajo se tomaron en espacios tridimensionales no controlados

de entornos acuáticos y terrestres. Se entiende por espacios tridimensionales no controlados como

aquellos en donde el espectador no tiene gran intervención con respecto al tipo, número y

disposición de los objetos que aparecen en la escena.

Para el entorno acuático, se usó un repositorio de imágenes llamado AQUA, extraídas de un video

tomado por el robot marino AQUA15

de la Universidad de McGill, Montreal, Canadá.

Para el entorno terrestre se utilizaron imágenes extraídas de seis secuencias de video que se

distribuyeron de la siguiente manera:

1. Una secuencia con un entorno terrestre exterior de tipo urbano (Exteriores_Urbanos16

).

2. Tres secuencias las cuales representan un entorno terrestre exterior de tipo boscoso

(Exteriores_Naturales1, Exteriores_Naturales2 y Exteriores_Naturales3).

3. Finalmente, dos secuencias de interiores de edificio de oficinas (Interiores1 e Interiores2).

Las secuencias de Interiores se tomaron dentro de las instalaciones de la Universidad de McGill,

Montreal, Canadá y las secuencias de Exteriores_Naturales se tomaron en un parque cercano a la

Universidad de McGill, Montreal, Canadá. Todos estos videos se obtuvieron con una cámara que

tiene las características siguientes:

Marca: Canon

Modelo: PowerShot SD1200 IS

Lente Canon Zoom Lens 3x IS 6.2 a 18.6 mm, 1:2.8-4.9

Sensor de 10.0 MegaPixeles

Las tomas se hicieron con la mínima distancia focal (sin zoom), es decir 6.2 mm.

Los detalles de los repositorios de fotogramas se muestran en la tabla 5.1.

15

El robot AQUA fue desarrollado por un equipo de investigación combinada de McGill, York y las

universidades de Dalhousie. Este robot es muy pequeño, ágil y por medio de sus palas puede nadar bajo el

agua para la recopilación de datos complejos de arrecifes y barcos hundidos. 16

Obtenido de la página web con URL: http://www.vision.ee.ethz.ch/~bleibe/cvpr07/datasets.html, fecha de

acceso: 10/08/2011.

Tesis de Maestría


Tabla 5.1. Características de los repositorios de imágenes.

No Nombre del

Repositorio

Tipo de

entorno

No. de

Imágenes

Dimensiones

de las

Imágenes

Formato de la

Imagen

1 AQUA Acuático 1000 1024×638 Imagen BMP

2 Exteriores_Urbanos Terrestre 1163 360×288 Imagen PNG

3 Exteriores_Naturales1 Terrestre 1561 640×480 Imagen JPG



6 Interiores1 Terrestre 663 320×240 Imagen JPG

7 Interiores2 Terrestre 2751 640×480 Imagen JPG

Una vez que se obtuvieron los repositorios de las imágenes se procedió a identificar un conjunto de

atributos numéricos en las imágenes, que pudieran ser útiles para clasificarlas en texturizadas o

estructuradas. Como resultado de este proceso se establecieron cinco variables cuantitativas que

resultan interesantes para la descripción de una imagen, como se muestra en la tabla 5.2.

Tabla 5.2. Características de los atributos numéricos.

No. Nombre de

la variable

Tipo de

Variable

Escala de

Medida

Descripción de la variable

1 NoHarris Métrica Razón Número de puntos que se detectan en la

imagen con el detector de características de

Harris

2 NoMSER Métrica Razón Número de regiones que se detectan en la


Star

3 NoStar Métrica Razón Número de blobs que se detectan en la


MSER

4 PromSize Métrica Razón Promedio del tamaño de los blobs detectados

con el detector de características Star

5 PromRtotal Métrica Razón Promedio del tamaño de las regiones

detectadas con el detector de características

MSER

Tesis de Maestría


Para llevar a cabo la clasificación de las imágenes de cada uno de los repositorios se utilizó el

método kmeans de la herramienta IBM SPSS Statistics 19. Se probó con distintas combinaciones de

estas cinco variables conjuntamente con distintas cantidades posibles de conglomerados con el fin

de determinar, de manera empírica, cuáles parejas funcionaban mejor.

El criterio que se utilizó para determinar que una combinación concreta de variables y un número

concreto de conglomerados era una pareja conveniente para describir la propiedad de interés fue

que generara conglomerados diferentes los cuales constituyeran categorías importantes para la

investigación, es decir conglomerados que dentro de cada uno de ellos se pueda asumir un

comportamiento homogéneo de la propiedad en estudio, y que entre conglomerados se aprecie un

comportamiento heterogéneo. En esta clasificación la propiedad de interés es el tipo de escena que

contiene la imagen: texturizada o estructurada.

Para medir la heterogeneidad entre los conglomerados se recurrió a los centros de los

conglomerados, ya que centros relativamente cercanos indican que los conglomerados no son muy

heterogéneos y viceversa.

Otro criterio que su utilizó para la discriminación de parejas (combinación de variables y un número

de conglomerados) fue el número de elementos por conglomerado, desechando aquellas parejas que

generaran conglomerados con pocos elementos ya que se buscaba la generalidad y no los casos

atípicos.

Las parejas formadas por la combinación de variables y el número de conglomerados, que mejor

funcionaron, de entre las probadas, para cada uno de los repositorios, se muestran en la tabla 5.3.

Tabla 5.3. Cantidad de conglomerados por repositorio.

No Nombre del

Repositorio

Tipo de entorno No. de

Conglomerados

Variable que se

utilizó para clasificar

1 AQUA Acuático 4 PromSize

2 Exteriores_Urbanos Terrestre 3 PromSize

3 Exteriores_Naturales1 Terrestre 2 PromSize



6 Interiores1 Terrestre 2 PromSize

7 Interiores2 Terrestre 4 PromSize

En la tabla 5.3 se observa que la variable que resultó más significativa para este propósito, en cada

uno de los repositorios, fue PromSize, en consecuencia esta variable se utilizó como variable

criterio en el proceso de clasificación de las imágenes de cada uno de estos repositorios. Para cada

análisis de conglomerados, determinado por el repositorio en cuestión, se eligió el método de

clasificación Kmeans de la herramienta IBM SPSS Statistics 19. Las salidas de estos análisis se

muestran en el anexo B de esta tesis.

Tesis de Maestría


Otro resultado de estos análisis de conglomerados fue que a cada imagen de los repositorios se le

asignó una etiqueta, indicadora de a qué conglomerado pertenece pero por razones de espacio no se

consideró apropiado incluir esas tablas en este documento, sin embargo, esta información se

visualiza en las figuras 5.8.-5.17 incluidas en las descripciones por repositorio que se presentan a

continuación. En todas estas descripciones se incluyen algunos resultados que se extrajeron del

anexo B, así como la descripción de secuencias de fotogramas por repositorio ya que es importante

identificar, aunque sea a grandes rasgos, las distintas escenas que se presentaron en los repositorios.

5.1. Descripción del repositorio AQUA

Los conglomerados del repositorio AQUA se etiquetaron con los números 1, 2, 3 y 4

respectivamente y algunas de sus características se muestran en la tabla 5.4.

Tabla 5.4. Características de conglomerados del repositorio AQUA.

Conglomerado Número de casos Centro final

1 442 10.9631

2 149 14.0631

3 320 8.9615

4 87 0

La gráfica siguiente dividida en dos partes, figura 5.1 y figura 5.2, muestra la pertenencia de cada

imagen a su conglomerado correspondiente.


AQUA.

1

2

3

4

1

13

25

37

49

61

73

85

97

10

9

12

1

13

3

14

5

15

7

16

9

18

1

19

3

20

5

21

7

22

9

24

1

25

3

26

5

27

7

28

9

30

1

31

3

32

5

33

7

34

9

36

1

37

3

38

5

39

7

40

9

42

1

43

3

44

5

45

7

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Tesis de Maestría



AQUA.

En la tabla 5.5 se describen algunas secuencias de fotogramas del repositorio AQUA.

Tabla 5.5. Identificación de algunas escenas de AQUA.

No.

Escena

Imágenes Conglomerado Escena

1 im1-im191 Predomina 3 Coral

2 im192-im468 Predomina 1 Coral más iluminado



5 im580-im696 Predomina 2 Otro tipo de coral

6 im697-im850 Entre 1 y 3 Coral un poco borroso

7 im851-im924 Claramente 4 En su mayoría agua

8 im925-im968 Predomina 2 Buzo

9 im969-im995 De todos (1, 2, 3 y 4) Arrecife y buzo

Se observa que los conglomerados de este repositorio se determinan por los objetos que aparecen en

la escena.

5.2. Descripción del Repositorio Exteriores_Urbanos

Los conglomerados del repositorio Exteriores_Urbanos se etiquetaron con los números 1, 2 y 3

respectivamente y algunas de sus características se muestran en la tabla tabla 5.6.

Tabla 5.6. Características de conglomerados del repositorio Exteriores_Urbanos.


1 498 7.4295

2 117 8.3444

3 547 6.7931

1

2

3

4

46

9

48

3

49

7

51

1

52

5

53

9

55

3

56

7

58

1

59

5

60

9

62

3

63

7

65

1

66

5

67

9

69

3

70

7

72

1

73

5

74

9

76

3

77

7

79

1

80

5

81

9

83

3

84

7

86

1

87

5

88

9

90

3

91

7

93

1

94

5

95

9

97

3

98

7

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Tesis de Maestría





Exteriores_Urbanos.


Exteriores_Urbanos.

En la tabla 5.7 se describen algunas secuencias de fotogramas del repositorio Exteriores_Urbanos.

Tabla 5.7. Identificación de algunas escenas de Exteriores_Urbanos.

No.

Escena


1 im1-im576 De todos (1, 2 y 3) Cambios de iluminación continuos

2 im577-im758 Claramente 3 Generalmente iluminado

3 im759-im826 Claramente 1 Aprox. la mitad de la imagen iluminada

y la otra oscura.

1

2

3

1

16

31

46

61

76

91

10

6

12

1

13

6

15

1

16

6

18

1

19

6

21

1

22

6

24

1

25

6

27

1

28

6

30

1

31

6

33

1

34

6

36

1

37

6

39

1

40

6

42

1

43

6

45

1

46

6

48

1

49

6

51

1

52

6

54

1

55

6

57

1

1

2

3

57

7

59

2

60

7

62

2

63

7

65

2

66

7

68

2

69

7

71

2

72

7

74

2

75

7

77

2

78

7

80

2

81

7

83

2

84

7

86

2

87

7

89

2

90

7

92

2

93

7

95

2

96

7

98

2

99

7

10

12

10

27

10

42

10

57

10

72

10

87

11

02

11

17

11

32

11

47

11

62

Nú

mer

o d

e co

ngl

om

erad

o

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Número de imagen

Tesis de Maestría


4 im827-im970 Claramente 3 Muy iluminado

5 im971-im1156 De todos (1, 2 y 3) Cambios de iluminación continuos

En general se observa que los conglomerados se determinan por el nivel de iluminación en la escena

y que dada la relativa pequeña diferencia entre los centros: 7.4295, 8.3444 y 6.7931 hubiera sido

suficiente con un conglomerado, es decir, todo el repositorio.

5.3. Descripción del repositorio Exteriores_Naturales1

Los conglomerados del repositorio Exteriores_Naturales1 se etiquetaron con los números 1 y 2


Tabla 5.8. Características de conglomerados del repositorio Exteriores_Naturales1.


1 621 7.3097

2 939 6.5202

La gráfica siguiente dividida en tres partes, figura 5.5, figura 5.6 y figura 5.7, muestra la pertenencia

de cada imagen a su conglomerado correspondiente.


Exteriores_Naturales1.

1

2

1

14

27

40

53

66

79

92

10

5

11

8

13

1

14

4

15

7

17

0

18

3

19

6

20

9

22

2

23

5

24

8

26

1

27

4

28

7

30

0

31

3

32

6

33

9

35

2

36

5

37

8

39

1

40

4

41

7

43

0

44

3

45

6

46

9

48

2

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Tesis de Maestría






En la tabla 5.9 se describen algunas secuencias de fotogramas del repositorio


Tabla 5.9. Identificación de algunas escenas de Exteriores_Naturales1.

No.

Escena


1 im1-im178 Claramente 2 Follaje

2 im179-im484 De todos (1 y 2) Follaje árbol

3 im485-im534 Claramente 1 Follaje iluminado

4 im535-im631 De todos (1 y 2) Follaje medio iluminado

5 im632-im759 Claramente 1 Follaje árbol iluminado

6 im760-im1560 De todos (1 y 2) Follaje borroso algunas veces con árbol

o camino

1

2

48

5

49

8

51

1

52

4

53

7

55

0

56

3

57

6

58

9

60

2

61

5

62

8

64

1

65

4

66

7

68

0

69

3

70

6

71

9

73

2

74

5

75

8

77

1

78

4

79

7

81

0

82

3

83

6

84

9

86

2

87

5

88

8

90

1

91

4

92

7

94

0

95

3

96

6

97

9

99

2

1

2

10

01

10

16

10

31

10

46

10

61

10

76

10

91

11

06

11

21

11

36

11

51

11

66

11

81

11

96

12

11

12

26

12

41

12

56

12

71

12

86

13

01

13

16

13

31

13

46

13

61

13

76

13

91

14

06

14

21

14

36

14

51

14

66

14

81

14

96

15

11

15

26

15

41

15

56

Nú

mer

o d

e co

ngl

om

erad

o

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Número de imagen

Tesis de Maestría


Se observa que los conglomerados se determinan por el nivel de iluminación en la escena y que

dada la relativa pequeña diferencia entre los centros: 7.3097 y 6.5202 hubiera bastado un

conglomerado.

5.4. Descripción del Repositorio Exteriores_Naturales2

Los conglomerados del repositorio Exteriores_Naturales2 se etiquetaron con los números 1y 2




1 631 7.9142

2 1230 6.5764

La gráfica siguiente dividida en tres partes, figura 5.8, figura 5.9 y figura 5.10, muestra la

pertenencia de cada imagen a su conglomerado correspondiente.





1

2

1

21

41

61

81

10

1

12

1

14

1

16

1

18

1

20

1

22

1

24

1

26

1

28

1

30

1

32

1

34

1

36

1

38

1

40

1

42

1

44

1

46

1

48

1

50

1

52

1

54

1

56

1

58

1

60

1

62

1

64

1

66

1

68

1

70

1

72

1

74

1

76

1

78

1

1

2

79

4

80

9

82

4

83

9

85

4

86

9

88

4

89

9

91

4

92

9

94

4

95

9

97

4

98

9

10

04

1

01

9

10

34

1

04

9

10

64

1

07

9

10

94

1

10

9

11

24

1

13

9

11

54

1

16

9

11

84

1

19

9

12

14

1

22

9

12

44

1

25

9

12

74

1

28

9

13

04

1

31

9

13

34

1

34

9

13

64

1

37

9

13

94

Nú

mer

o d

e co

ngl

om

erad

o

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Número de imagen

Tesis de Maestría







No.

Escena


1 im1-im401 Claramente 2 Follaje y en ocasiones árbol

2 im402-im793 Predomina 1 Árboles con algo de sombra

3 im794-im950 De todos (1 y 2) Alternan escenas con pasto, follaje y

follaje con árbol

4 im951-im1097 Claramente 2 Follaje con árbol más iluminados que

los anteriores

5 im1098-im1403 De todos (1 y 2) Variadas escenas con puro follaje, pasto

o con árboles

6 im1404-im1496 Claramente 2 Follaje y árbol

7 im1497-im1546 Predomina 1 Árboles con mucha sombra


follaje con árbol

9 im1678-im1753 Claramente 2 Follaje y un árbol a lo lejos


follaje con árbol

Se observa que los conglomerados se determinan por el nivel de iluminación en la escena y los

objetos que aparecen en ella. La diferencia entre los centros: 7.9142 y 6.5764 es relativamente

pequeña indicativo de que para los fines hubiera sido suficiente un conglomerado.

5.5. Descripción del repositorio Exteriores_Naturales3

Los conglomerados del repositorio Exteriores_Naturales3 se etiquetaron con los números 1 y 2


1

2

14

04

14

16

14

28

14

40

14

52

14

64

14

76

14

88

15

00

15

12

15

24

15

36

15

48

15

60

15

72

15

84

15

96

16

08

16

20

16

32

16

44

16

56

16

68

16

80

16

92

17

04

17

16

17

28

17

40

17

52

17

64

17

76

17

88

18

00

18

12

18

24

18

36

18

48

18

60

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Tesis de Maestría




1 413 7.2495

2 704 5.6244









1

2

1

17

3

3

49

6

5

81

9

7

11

3

12

9

14

5

16

1

17

7

19

3

20

9

22

5

24

1

25

7

27

3

28

9

30

5

32

1

33

7

35

3

36

9

38

5

40

1

41

7

43

3

44

9

46

5

48

1

49

7

51

3

52

9

54

5

56

1

57

7

59

3

60

9

62

5

1

2

62

6

63

9

65

2

66

5

67

8

69

1

70

4

71

7

73

0

74

3

75

6

76

9

78

2

79

5

80

8

82

1

83

4

84

7

86

0

87

3

88

6

89

9

91

2

92

5

93

8

95

1

96

4

97

7

99

0

10

03

10

16

10

29

10

42

10

55

10

68

10

81

10

94

11

07

Nú

mer

o d

e co

ngl

om

erad

o

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Número de imagen

Tesis de Maestría



No.

Escena


1 im1-im101 Claramente 2 Pasto y tronco de árbol

2 im102-im170 De ambos (1 y 2) Escenas variadas: arbustos y tronco de

árbol y arbustos solos

3 im171-im256 Claramente 2 Arbustos

4 im257-im401 Predomina 1 Arbustos con leve cambio de

iluminación



6 im451-im488 Claramente 1 Arbustos y trocos de árbol al fondo con

cambio de iluminación



8 im626-im737 Predomina 2



10 im774-im921 Predomina 2 Árboles con demasiada iluminación



12 im968-im1007 Claramente 2 Arbustos iluminados

13 im1008-im1040 Claramente 1 Troncos de árboles con arbustos



15 im1082-im1117 Claramente 1 Árboles con arbustos

Se observa que los conglomerados se determinan por el nivel de iluminación en la escena y los

objetos que aparecen en ella. La diferencia entre los centros: 7.2495 y 5.6244 es relativamente

pequeña indicativo de que para los fines del trabajo hubiera sido suficiente un conglomerado.

5.6. Descripción del repositorio Interiores1

Los conglomerados del repositorio Interiores1 se etiquetaron con los números 1 y 2 respectivamente

y algunas de sus características se muestran en la tabla 5.14.

Tabla 5.14. Características de conglomerados del repositorio Interiores1.


1 498 10.1664

2 164 0.1829

La gráfica de la figura 5.13, muestra la pertenencia de cada imagen a su conglomerado

correspondiente.

Tesis de Maestría


Figura 5.13. Gráfica de pertenencia a conglomerados del repositorio Interiores1.

En la tabla 5.15 se describen algunas secuencias de fotogramas del repositorio Interiores1.

Tabla 5.15. Identificación de algunas escenas del repositorio Interiores1.

No.

Escena


1 im1-im462 Predomina 1 Continuos cambios de escena todas muy

iluminadas

2 im463-im519 De ambos (1 y 2) Cambios de escena continuos

3 im520-im602 Predomina 2 Predomina una escena oscura: puerta del

baño

4 im603-im662 De ambos (1 y 2) Predomina una escena muy iluminada

Aquí se observa que ambos conglomerados son relativamente diferentes por la diferencia que se

presenta entre sus centros: 10.1664 y 0.1829 pero se observa que los conglomerados obedecen al

tipo de objetos que aparecen en la escena.

5.7. Descripción del repositorio Interiores2

Los conglomerados del repositorio Interiores2 se etiquetaron con los números 1, 2, 3 y 4


Tabla 5.16. Características de conglomerados del repositorio Interiores2.


1 462 14.5689

2 672 6.2050

3 325 0

4 1291 10.1606

1

2 1

17

33

49

6

5

81

97

11

3

12

9

14

5

16

1

17

7

19

3

20

9

22

5

24

1

25

7

27

3

28

9

30

5

32

1

33

7

35

3

36

9

38

5

40

1

41

7

43

3

44

9

46

5

48

1

49

7

51

3

52

9

54

5

56

1

57

7

59

3

60

9

62

5

64

1

65

7

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Tesis de Maestría


La gráfica siguiente dividida en cuatro partes, figura 5.14, figura 5.15, figura 5.16 y figura 5.17,

muestra la pertenencia de cada imagen a su conglomerado correspondiente.

Figura 5.14. Primera parte de gráfica de pertenencia a conglomerados del repositorio

Interiores2.

Figura 5.15. Segunda parte de gráfica de pertenencia a conglomerados del repositorio

Interiores2.

1

2

3

4

1

19

37

55

73

91

10

9

12

7

14

5

16

3

18

1

19

9

21

7

23

5

25

3

27

1

28

9

30

7

32

5

34

3

36

1

37

9

39

7

41

5

43

3

45

1

46

9

48

7

50

5

52

3

54

1

55

9

57

7

59

5

61

3

63

1

64

9

66

7

68

5

1

2

3

4

70

1

71

9

73

7

75

5

77

3

79

1

80

9

82

7

84

5

86

3

88

1

89

9

91

7

93

5

95

3

97

1

98

9

10

07

1

02

5

10

43

1

06

1

10

79

1

09

7

11

15

1

13

3

11

51

1

16

9

11

87

1

20

5

12

23

1

24

1

12

59

1

27

7

12

95

1

31

3

13

31

1

34

9

13

67

1

38

5

Nú

mer

o d

e co

ngl

om

erad

o

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Número de imagen

Tesis de Maestría


Figura 5.16. Tercera parte de gráfica de pertenencia a conglomerados del repositorio

Interiores2.

Figura 5.17. Cuarta parte de gráfica de pertenencia a conglomerados del repositorio

Interiores2.

En la tabla 5.17 se describen algunas secuencias de fotogramas del repositorio Interiores2.

Tabla 5.17. Identificación de algunas escenas del repositorio Interiores2.

No.

Escena


1 im1-im82 Claramente 2 Aparece un tipo particular de escena

2 im83-im177 De todos (1, 2, 3 y 4) Escenas variadas

3 im178-im275 Claramente 2 Aparece una escena parecida a la que

aparece en la secuencia im1-im82

4 im276-im2750 De todos Escenas variadas

1

2

3

4

14

01

14

19

14

37

14

55

14

73

14

91

15

09

15

27

15

45

15

63

15

81

15

99

16

17

16

35

16

53

16

71

16

89

17

07

17

25

17

43

17

61

17

79

17

97

18

15

18

33

18

51

18

69

18

87

19

05

19

23

19

41

19

59

19

77

19

95

20

13

20

31

20

49

20

67

20

85

1

2

3

4

21

01

21

18

21

35

21

52

21

69

21

86

22

03

22

20

22

37

22

54

22

71

22

88

23

05

23

22

23

39

23

56

23

73

23

90

24

07

24

24

24

41

24

58

24

75

24

92

25

09

25

26

25

43

25

60

25

77

25

94

26

11

26

28

26

45

26

62

26

79

26

96

27

13

27

30

27

47

Nú

mer

o d

e co

ngl

om

erad

o

Nú

mer

o d

e co

ngl

om

erad

o

Número de imagen

Número de imagen

Tesis de Maestría


Aquí se observa que ambos conglomerados son relativamente diferentes por la diferencia que se

presentan entre sus centros: 14.5689, 6.2050, 0.000 y 10.1606 y también se observa que los

conglomerados obedecen al tipo de objetos que aparecen en la escena.

También se bajó un repositorio de imágenes texturizadas llamado Brodatz17

y con ese conjunto de

imágenes se formaron 3 conglomerados en función del tamaño de las imágenes. Estos

conglomerados se denominaron Textura 1, Textura 2 y Textura 3 respectivamente. Asimismo se

recopiló la base de imágenes con la que hicieron sus pruebas Mikolajczyk et al. (Mikolajczyk,

2005) y se formaron otros dos conglomerados: Textu y Estruct, Textu contiene las imágenes

texturizadas y Estruct contiene las imágenes estructuradas.

Los detalles de estos cinco repositorios se muestran en la tabla 5.18.

Tabla 5.18. Características de los repositorios de imágenes texturizadas y estructuradas.

Nombre del

Repositorio

Tipo No. de

Imágenes

Dimensiones de

las Imágenes

Formato de la

Imagen

Texturizadas1 Texturizada 26 512×512 Imagen JPG



Textu Texturizada 9 880×680 Imagen JPG

Estruct Estructurada 10 800×640 Imagen JPG

En total se obtuvieron 24 conglomerados para los cuales se calcularon los coeficientes de

variación18

: CvNoHarris, CvNoMSER, CvNoStar, CvPromSize, CvPromRtotal a partir de las

variables: NoHarris, NoMSER, NoStar, PromSize, PromRtotal definidas previamente en los

repositorios. Esto se hizo con el fin de clasificar estos 24 conglomerados en texturizados o

estructurados utilizando alguna combinación adecuada de las variables coeficiente de variación.

Después de algunas pruebas utilizando el método kmeans de la herramienta IBM SPSS Statistics 19

se verificó que las variables CvNoHarris y CvPromRtotal funcionaban bien para clasificar estos

conglomerados. Es decir que a los conglomerados como Texturizadas1, Texturizadas2,

Texturizadas3 y Textu que se sabe que son texturizados los clasificó como tal y que al

conglomerado Estruct que se sabe que es estructurado también lo clasificó correctamente.

La salida completa en SPSS de esta clasificación se encuentra en el anexo B de la tesis y de ahí se

extrajeron las tablas siguientes.

En la tabla 5.19 se muestran los centros de los conglomerados finales.

17

Obtenido de la página web con URL: http://www.ux.uis.no/~tranden/brodatz.html, fecha de acceso:

10/08/2011. 18

Es el cociente de la desviación típica entre la media de un conjunto de datos positivos. El coeficiente de

variación permite comparar las dispersiones de dos distribuciones distintas.

Tesis de Maestría


Tabla 5.19. Características de conglomerados de los conglomerados.

Conglomerado Número de casos Centros finales

CvNoHarris CvPromRtotal

1 15 0.200258 0.213221

2 9 0.675605 0.321606

En la tabla 5.20 se etiquetan cada uno de los veinticuatro repositorios en texturizado (1) o

estructurado (2). De acuerdo con esta tabla se puede asumir que todos los conglomerados que

pertenecen al conglomerado 2 contienen en su mayoría imágenes que provienen de escenas

estructuradas y que en contraste los conglomerados que pertenecen al conglomerado 1 contienen

una gran cantidad de imágenes que provienen de escenas texturizadas. Aunque parezca

contradictorio, ya que en la bibliografía frecuentemente se dice que las escenas de edificio son

estructuradas, es importante considerar el hecho de que los edificios que se filmaron en el video

Exteriores_Urbanos muestran bastantes estructuras repetitivas, como son las ventanas y los adornos.

Tabla 5.20. Pertenencia de los conglomerados a los conglomerados.

Repositorio Entorno Cluster_Entorno Cluster

AQUA 1 1 1

AQUA 1 3 1

Urbanos 3 1 1

Urbanos 3 2 1

Urbanos 3 3 1

Naturales1 4 1 1

Naturales1 4 2 1

Naturales2 4 1 1

Naturales2 4 2 1

Naturales3 4 1 1

Naturales3 4 2 1

Texturizadas1 0 1 1

Texturizadas2 0 1 1

Texturizadas3 0 1 1

Textu 0 1 1

AQUA 1 2 2

AQUA 1 4 2

Interiores1 2 1 2

Interiores1 2 2 2

Interiores2 2 1 2

Interiores2 2 2 2

Interiores2 2 3 2

Interiores2 2 4 2

Estruct 0 1 2

Tesis de Maestría


También utilizando el método kmeans de la herramienta IBM SPSS Statistics 19 se clasificaron los

repositorios completos, en texturizados o estructurados, y la combinación de variables que mejor

funcionó, considerando los supuestos que ya se tenían, fueron CvNoHarris, CvPromSize,

CvNoMSER, CvPromRtotal y CvNoStar. Un resumen del resultado de esta clasificación se

muestra en las tablas siguientes y la salida completa de SPSS se puede consultar en el anexo B de la

tesis.

En la tabla 5.21 se pueden consultar los centros finales de ambos conglomerados.

Tabla 5.21. Características de los conglomerados de repositorios.

Cong. Número

de casos

Centros finales

CvNoHarris CvPromSize CvNoMSER CvPromRtotal CvNoStar

1 10 0.23493 0.20608 0.25848 0.24598 0.72371

2 2 1.11546 0.56240 0.46638 0.27444 1.45001

En la tabla 5.22 se etiquetan los repositorios en texturizado (1) o estructurado (2), según sea el caso.

Se observa que el considerar todo el repositorio como un único conglomerado tiene sus

consecuencias ya que aunque la mayoría de los repositorios se mantienen en su estado de

texturizado o estructurado original, el repositorio de Estruct, que teóricamente contiene imágenes de

escenas estructuradas, se cambia al conglomerado de imágenes texturizadas. Esto da un indicio de

que no es conveniente trabajar con todo el repositorio de imágenes para tratar de ubicar el tipo de

escena y de que además esto se recomienda sólo en aquellos casos en donde todas las imágenes del

repositorio son muy homogéneas en función de la(s) variable(s) que se están midiendo o lo que es

lo mismo que se presente un tipo de escena muy parecido en todas las imágenes.

Tabla 5.22. Pertenencia de los repositorios a los conglomerados.

Repositorio Entorno Cluster

Interiores1 2 2

Interiores2 2 2

AQUA 1 1

Exteriores_Urbanos 3 1

Exteriores_Naturales1 4 1



Texturizadas1 0 1

Texturizadas2 0 1

Texturizadas3 0 1

Textu 0 1

Estruct 0 1

Tesis de Maestría


Capítulo 6

6. Experimentos y resultados

En este capítulo se presentan los criterios que se utilizaron para diseñar los experimentos y los

resultados de su ejecución.

6.1. Diseño de experimentos

Como esta investigación tiene un alcance exploratorio no se formularon hipótesis a priori, pero sí se

formularon conjeturas iniciales que versan sobre las posibles relaciones que se pueden establecer

entre el conglomerado y el tipo de algoritmo o mínimamente entre el tipo de escena, estructurada o

texturizada, y el tipo de algoritmo. Por este motivo se diseñó un plan de pruebas que contempla tres

pasos básicos:

Paso 1. Elección de una muestra.

En principio se seleccionó una muestra de cada uno de los repositorios buscando que, por lo menos,

un par de parejas de imágenes correspondieran al mismo conglomerado. En total se utilizaron 39

pares de imágenes de las cuales 16 son estructuradas y 23 texturizadas.

Paso 2. Aplicar los doce algoritmos a esas muestras.

Posteriormente a esas muestras se les aplicaron los doce algoritmos que se muestran en la tabla 6.1

para evaluar su desempeño. Estos algoritmos de correspondencia son el resultado de primero aplicar

un algoritmo de detección de características, posteriormente el algoritmo de búsqueda Épsilon-bola,

en seguida un algoritmo de emparejamiento de puntos y finalmente el algoritmo de

desambiguación, como lo indica la figura 1.1.

Tabla 6.1. Tabla de composición de algoritmos de correspondencia.

Número

Algoritmo

Nombre Composición

1. StarSAD Primero se aplica Star, luego Épsilon-bola y finalmente SAD

2. StarVNC Primero se aplica Star, luego Épsilon-bola y finalmente VNC

3. StarTex Primero se aplica Star, luego Épsilon-bola y finalmente Textura

4. StarCol Primero se aplica Star, luego Épsilon-bola y finalmente Color

5. MserSAD Primero se aplica MSER, luego Épsilon-bola y finalmente SAD

6. MserVNC Primero se aplica MSER, luego Épsilon-bola y finalmente VNC

7. MserTex Primero se aplica MSER, luego Épsilon-bola y finalmente Textura

8. MserCol Primero se aplica MSER, luego Épsilon-bola y finalmente Color

9. HarrisSAD Primero se aplica Harris, luego Épsilon-bola y finalmente SAD

10. HarrisVNC Primero se aplica Harris, luego Épsilon-bola y finalmente VNC

11. HarrisTex Primero se aplica Harris, luego Épsilon-bola y finalmente Textura

12. HarrisCol Primero se aplica Harris, luego Épsilon-bola y finalmente Color

Tesis de Maestría


Paso 3: Evaluar el desempeño de los algoritmos en las muestras.

Finalmente se evaluó el desempeño de los algoritmos de acuerdo a la metodología que se muestra

en la sección 6.2 y con esos resultados se formularon las conclusiones que se presentan en el

capítulo 7.

6.2. Metodología de evaluación de los algoritmos

Para evaluar el desempeño de los algoritmos se midió su tiempo de ejecución y además se calculó

un índice de precisión. Este índice de precisión se obtuvo del esquema de evaluación que utilizaron

Mikolajczyk (Mikolajczyk, 2005), Tuytelaars (Tuytelaars, 2008), Bonfim (Bonfim, 2010) y Kenton

(Kenton, 2010a) en el diseño de sus pruebas de correspondencia.

Este valor da un indicador de que tan bueno es el conjunto de correspondencias respecto a sí mismo,

y se define por el cociente que aparece en la ecuación (21).

(21)

Las correspondencias correctas son evaluadas visualmente por un operador y para facilitar este

proceso se trazan círculos de radio

, con colores azul y rojo respectivamente, que

están centrados en cada indicador de característica como se muestra en la figura 6.1. Una

correspondencia se supone correcta si a la vista del operador ambos círculos están centrados sobre

el mismo objeto en ambas imágenes.

Figura 6.1. Ejemplo de una correspondencia verdadera.

6.3. Inicialización de parámetros del sistema

La inicialización de parámetros del sistema se realiza ingresándolos de manera manual y los

parámetros que se establecieron ab initio, para la realización de estas pruebas fueron:

Tesis de Maestría


1. La función Harris utilizó como cota superior de esquinas 500.

2. La función cvGoodFeaturesToTrack recibió como parámetros los valores:

image = input

eigImage = output

tempImage = temp

corners = frame1_features

cornerCount = &x1 (donde x1 se fijó en 500)

double qualityLevel = 0.01

double minDistance = 0.01

intPtr mask = NULL

blockSize, useHarris y k se dejaron por default.

3. La función cvGetStarKeypoints, recibió como parámetros:

image = imag

La función cvStarDetectorParams recibió como parámetro el valor de 20 para maxSize ya

que, después de hacer varias pruebas, se verificó que es donde se obtiene la mayor cantidad

de características de la imagen. Para los otros parámetros se dejaron los que aparecen por

default.

4. La función cvExtractMSER, recibió como parámetros:

img = imag

mask = NULL

contours = &contours

storage = storage

params = params

la estructura params obtuvo sus valores con la ejecución de la función cvMSERParams( ),

la cual deja todos los valores por default para sus parámetros.

5. El algoritmo de proximidad Epsilón-bola utilizó un valor de radio de 30 y la distancia

Manhattan.

6. En el algoritmo Textura el número de unidades de desplazamiento fue de 2.

7. El algoritmo Color utilizó un disco de radio 5 y la distancia euclidiana.

6.4. Resultados de los experimentos

En seguida se muestran los resultados obtenidos de los experimentos en cada uno de los entornos:

acuático y terrestre.

http://msdn2.microsoft.com/en-us/library/643eft0t


http://msdn2.microsoft.com/en-us/library/5he14kz8

Tesis de Maestría


En estos resultados se mostrarán algunas imágenes con distintos tamaños debido a que ese es su

tamaño original y no se debe cambiar porque se modificaría también el tamaño de las flechas que

aparecen en ellas y sirven para indicar la orientación de las correspondencias. El símbolo en

estas imágenes se interpreta como la flecha pero con la punta en el origen de su cuerpo.

Asimismo, en algunas de las imágenes se ve claramente que la mayoría de las características se

ubican en zonas específicas de la imagen, esto es debido a que estas imágenes son la proyección de

escenas que contienen un objeto que tiene alta textura y por ende acapara la detección.

Para describir el movimiento de la imagen, de manera imaginativa, se ubicará una rosa de los

vientos en el centro de la imagen y a partir de ella se especificará la dirección del movimiento

aparente de la imagen.

6.4.1. Resultados obtenidos en la muestra de entorno acuático

o Repositorio AQUA

De la tabla C.1 a la tabla C.6 del anexo C se extrajeron los datos que se muestran en las gráficas de

las figuras 6.2 a 6.5. En estas figuras se ilustra el desempeño de los algoritmos en la muestra del

repositorio AQUA.

La muestra que se seleccionó del repositorio AQUA estuvo conformada por los pares de imágenes

siguientes: (im10,im11), (im74,im75), (im360,im361), (im620,im621), (im730,im731),

(im873,im874), (im896,im897), (im930,im931), (im975,im976).

En la figura 6.2 se observa que la mayor cantidad de características las detecta Harris, en los casos

donde no es así se debe a la cota superior de 500 que se estableció para el número de esquinas.

Además se observa que el comportamiento de MSER y Star en la búsqueda de características es

muy parecido, aunque MSER, en la mayoría de los casos de prueba detecta más características que

Star.

Figura 6.2. Número de características destacadas del repositorio AQUA.

0

100

200

300

400

500

600

700

800

900 im

10

im1

1

im7

4

im7

5

im3

60

im3

61

im6

20

im6

21

im7

30

im7

31

im8

73

im8

74

im8

96

im8

97

im9

30

im9

31

im9

75

im9

76

MSER

Star

Harris

Número de imagen

Nú

mer

o d

e c

arac

terí

stic

as d

esta

cad

as

Tesis de Maestría


En la figura 6.3 se observa que en general la mayor cantidad de correspondencias se encuentra en

los algoritmos que tienen como detector de características a Harris.

Figura 6.3. Número de correspondencias del repositorio AQUA.

En la figura 6.4. se observa que en general la mejor precisión la presenta el alogoritmo StarTex.

Figura 6.4. Precisión del repositorio AQUA.

0

20

40

60

80

100

120

140

160

180

200

im1

0-im

11

im7

4-im

75

im3

60

-im3

61

im6

20

-im6

21

im7

30

-im7

31

im9

30

-im9

31

im9

75

-im9

76

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserCol

HarrisSAD

HarrisVNC

HarrisTex

HarrisCol

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

im1

0-im

11

im7

4-im

75

im3

60

-im3

61

im6

20

-im6

21

im7

30

-im7

31

im9

30

-im9

31

im9

75

-im9

76

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserCol

HarrisSAD

HarrisVNC

HarrisTex

HarrisCol

Pareja de imágenes

Nú

mer

o d

e c

orr

esp

on

den

cias

Pareja de imágenes

Pre

cisi

ón

Tesis de Maestría


En la figura 6.5 se observa que el mayor tiempo de ejecución se consume cuando se aplican

algoritmos que tienen en su etapa de emparejamiento descriptores de textura. Además se ve que

existe una relación fuerte entre los algoritmos y las imágenes que analizan ya que la el rango de los

algoritmos que tienen en su etapa de emparejamiento descriptores de textura varía de 37.9 a 71.069

mientras que para el resto de los algoritmos el rango varía de 0.024 a 1.164.

Figura 6.5. Tiempo, medido en segundos, del repositorio AQUA.

A continuación de la figura 6.6. a la figura 6.14 se muestran las imágenes de la muestra del

repositorio AQUA resultado de los algoritmos en donde se obtuvo la mejor precisión:

La figura 6.6 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el suroeste.

0

10

20

30

40

50

60

70

80

im1

0-im

11

im7

4-im

75

im3

60

-im3

61

im6

20

-im6

21

im7

30

-im7

31

im9

75

-im9

76

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserCol

HarrisSAD

HarrisVNC

HarrisTex

HarrisCol

Pareja de imágenes

Tiem

po

(se

g)

Tesis de Maestría


Figura 6.6. Imagen 10 y 11 resultado del algoritmo StarTex (buen desempeño).

La figura 6.7 se interpreta que la imagen experimentó un desplazamiento hacia el suroeste.


La figura 6.8 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el noroeste.

Tesis de Maestría


Figura 6.8. Imagen 360 y 361 resultado del algoritmo MserCol (buen desempeño).

La figura 6.9 se interpreta que la imagen experimentó un desplazamiento hacia el noroeste.


En las figuras 6.10-6.13 las colas de las flechas voltean para todos lados, por lo tanto se infiere que

la correspondencia no es buena.

Tesis de Maestría


Figura 6.10. Imagen 730 y 731 resultado del algoritmo StarSAD.

Figura 6.11. Imagen 873 y 874 resultado del algoritmo StarSAD.

Tesis de Maestría


Figura 6.12. Imagen 896 y 897 resultado del algoritmo HarrisSAD.

Figura 6.13. Imagen 930 y 931 resultado del algoritmo HarrisSAD.

La figura 6.14 se interpreta que la cámara se está alejando de la escena.

Tesis de Maestría


Figura 6.14. Imagen 975 y 976 resultado del algoritmo MserSAD (buen desempeño).

6.4.2. Resultados obtenidos en la muestra del entorno terrestre

En el entorno terrestre se consideraron dos entornos: entorno terrestre de exteriores y entorno

terrestre de interiores.

Entorno terrestre de exteriores

El entorno terrestre de exteriores considera dos tipos de entornos: terrestre exterior de tipo urbano y

terrestre exterior de tipo boscoso. Para analizar el entorno terrestre de tipo urbano se trabajó con el

repositorio Exteriores_Urbanos.

o Repositorio Exteriores_Urbanos

De la tabla C.7 a la tabla C.12 del anexo C se extrajeron los datos que se muestran en las gráficas

de las figuras 6.15 a 6.18. En estas figuras se ilustra el desempeño de los algoritmos en la muestra

del repositorio Exteriores_Urbanos.

La muestra que se seleccionó del repositorio Exteriores_Urbanos estuvo conformada por los pares

de imágenes siguientes: (im20,im21), (im240,im241), (im452,im453), (im499,im500),

(im570,im571), (im1029,im1030).

En la figura 6.15 se observa que, para esta muestra, la mayor cantidad de características las detecta

Harris. Además el comportamiento de MSER y Star en la búsqueda de características es muy

parecido, en este caso, Star detecta, en su mayoría, más características que MSER.

Tesis de Maestría


Figura 6.15. Número de características destacadas del repositorio Exteriores_Urbanos.

En la figura 6.16 se observa que, para esta muestra, en general la mayor cantidad de

correspondencias se encuentra en los algoritmos que tienen como detector de características a

Harris.

Figura 6.16. Número de correspondencias del repositorio Exteriores_Urbanos.

En la figura 6.17 se puede observar que, para esta muestra, en general la mejor precisión la presenta

el MserTex.

0

100

200

300

400

500

600

im2

0

im2

1

im2

40

im2

41

im4

52

im4

53

im4

99

Im5

00

im5

70

im5

71

im1

02

9

im1

03

0

MSER

Star

Harris

0

20

40

60

80

100

120

140

160

180

200

im2

0-im

21

im2

40

-im2

41

im4

52

-im4

53

im4

99

-im5

00

im5

70

-im5

71

im1

02

9-im

10

30

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserCol

HarrisSAD

HarrisVNC

HarrisTex

HarrisCol

Nú

mer

o d

e c

arac

terí

stic

as d

esta

cad

as

Número de imagen

Pareja de imágenes

Nú

mer

o d

e c

orr

esp

on

den

cias

Tesis de Maestría


Figura 6.17. Precisión del repositorio Exteriores_Urbanos.



existe una relación fuerte entre los algoritmos y las imágenes que analizan ya que la el rango de los

algoritmos que tienen en su etapa de emparejamiento descriptores de textura varía de 11.49 a

137.42 mientras que para el resto de los algoritmos el rango varía de 0.0121 a 0.729.

Figura 6.18. Tiempo, medido en segundos, del repositorio Exteriores_Urbanos.

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

im2

0-im

21

im2

40

-im2

41

im4

52

-im4

53

im4

99

-im5

00

im5

70

-im5

71

im1

02

9-im

10

30

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserCol

HarrisSAD

HarrisVNC

HarrisTex

HarrisCol

0

20

40

60

80

100

120

140

160

180 im

20

-im2

1

im2

40

-im2

41

im4

52

-im4

53

im4

99

-im5

00

im5

70

-im5

71

im1

02

9-im

10

30

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserCol

HarrisSAD

HarrisVNC

HarrisTex

HarrisCol

Pareja de imágenes

Pre

cisi

ón

Pareja de imágenes

Tiem

po

(se

g)

Tesis de Maestría


A continuación de la figura 6.19 a la figura 6.24 se muestran las imágenes con los algoritmos en

donde se obtuvo la mejor precisión:

En la figura 6.19 las colas de las flechas voltean para todos lados, por lo tanto se deduce que la

correspondencia no es buena.

Figura 6.19. Imagen 20 y 21 resultado del algoritmo MserTex.

La figura 6.20 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el sureste.

Figura 6.20. Imagen 240 y 241 resultado del buen desempeño del algoritmo MserSAD.

Tesis de Maestría


La figura 6.21 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el

noroeste.

Figura 6.21. Imagen 452 y 453 resultado del buen desempeño del algoritmo StarSAD.

La figura 6.22 se interpreta que la imagen experimentó un desplazamiento hacia el oeste.

Figura 6.22. Imagen 499 y 500 resultado del buen desempeño del algoritmo MserTex.

La figura 6.23 se interpreta que la cámara se está acercando a la escena.

Tesis de Maestría


Figura 6.23. Imagen 570 y 571 resultado del buen desempeño del algoritmo HarrisSAD.

La figura 6.24 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el oeste.

Figura 6.24. Imagen 1029 y 1030 resultado del algoritmo MserTex.

Para analizar el entorno terrestre de de tipo boscoso se trabajó con los tres repositorios:

Exteriores_Naturales1, Exteriores_Naturales2 y Exteriores_Naturales3.

o Repositorios Exteriores_Naturales1, Exteriores_Naturales2 y Exteriores_Naturales3

De las tablas C.13 a la C.30 del anexo C se extrajeron los datos que se muestran en las gráficas de

las figuras 6.25 a 6.40. En estas figuras se ilustra el desempeño de los algoritmos en la muestra de

los repositorios Exteriores_Naturales.

Tesis de Maestría


La muestra que se seleccionó de los repositorios Exteriores_Naturales estuvo conformada por los

pares de imágenes siguientes:

Del repositorio Exteriores_Naturales1: (im120,im121), (im344,im345), (im406,im407),

(im710,im711).


(im766,im767).


(im720,im721).


Harris, ya que en los casos donde no es así es por la cota superior de 500 que se estableció para el

número de esquinas. Además se ve que el comportamiento de MSER y Star es muy parecido, en

este caso Star, en la mayoría de los casos detectó más características que MSER.

Figura 6.25. Número de características destacadas de los repositorios Exteriores_Naturales.

En la figura 6.26 se ve que, para esta muestra, la mayor cantidad de correspondencias se encuentra

en los algoritmos que tienen como detector de características a Star o Mser.

0

500

1000

1500

2000

2500

im1

20

im1

21

im3

44

im3

45

im4

06

im4

07

im7

10

im7

11

im1

38

im1

39

im3

31

im3

32

im4

50

im4

51

im7

66

im7

67

im1

20

im1

21

im3

23

im3

24

im4

80

im4

81

im7

20

im7

21

MSER

Star

Harris

Número de imagen

Nú

mer

o d

e c

arac

terí

stic

as d

esta

cad

as

Tesis de Maestría


Figura 6.26. Número de correspondencias de los repositorios Exteriores_Naturales.

En la figura 6.27 se observa que, para esta muestra, en general, la mejor precisión la presentan los

algoritmos StarTex y MserSAD.

Figura 6.27. Precisión de los repositorios Exteriores_Naturales.

0

100

200

300

400

500

600

700

800

900

im1

20

-im1

21

im3

44

-im3

45

im4

06

-im4

07

im7

10

-im7

11

im1

38

-im1

39

im3

31

-im3

32

im4

50

-im4

51

im7

66

-im7

67

im1

20

-im1

21

im3

23

-im3

24

im4

80

-im4

81

im7

20

-im7

21

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserCol

HarrisSAD

HarrisVNC

HarrisTex

HarrisCol

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

im1

20

-im1

21

im3

44

-im3

45

im4

06

-im4

07

im7

10

-im7

11

im1

38

-im1

39

im3

31

-im3

32

im4

50

-im4

51

im7

66

-im7

67

im1

20

-im1

21

im3

23

-im3

24

im4

80

-im4

81

im7

20

-im7

21

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserCol

HarrisSAD

HarrisVNC

HarrisTex

HarrisCol

Pareja de imágenes

Nú

mer

o d

e c

orr

esp

on

den

cias

Pareja de imágenes

Pre

cisi

ón

Tesis de Maestría


En la figura 6.28 se tiene que el mayor tiempo de ejecución se consume cuando se aplican


existe una relación fuerte entre los algoritmos y las imágenes que analizan ya que para los

repositorios Naturales2 y Naturales3 (contienen imágenes del mismo tamaño) el rango de los

algoritmos que tienen en su etapa de emparejamiento descriptores de textura varía de 5.79 a

193.458 y para el resto de los algoritmos, en los mismos repositorios, el rango varía de 0.011 a

0.084. Esto mismo sucede para el repositorio de Naturales1 ya que la el rango de los algoritmos que

tienen en su etapa de emparejamiento descriptores de textura varía de 33.25 a 495.58 y para el resto

de los algoritmos el rango varía de 0.0114 a 1.4.

Figura 6.28. Tiempo, medido en segundos, de los repositorios Exteriores_Naturales.

o Repositorio Exteriores_Naturales1

En las figuras 6.29 – 6.32 se muestran las imágenes muestra del repositorio Exteriores_Naturales1,

con los algoritmos en donde se obtuvo la mejor precisión.

En la figura 6.29 las colas de las flechas voltean para todos lados, por lo tanto se infiere que la


0

100

200

300

400

500

600

700

800

900

im1

20

-im1

21

im3

44

-im3

45

im4

06

-im4

07

im7

10

-im7

11

im1

38

-im1

39

im3

31

-im3

32

im4

50

-im4

51

im7

66

-im7

67

im1

20

-im1

21

im3

23

-im3

24

im4

80

-im4

81

im7

20

-im7

21

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserCol

HarrisSAD

HarrisVNC

HarrisTex

Pareja de imágenes

Tiem

po

(se

g)

Tesis de Maestría


Figura 6.29. Imagen 120 y 121 resultado del algoritmo StarTex.


noroeste.

Tesis de Maestría



En las figuras 6.31 y 6.32 las colas de las flechas voltean para todos lados, por lo tanto se deduce

que la correspondencia no es buena.

Tesis de Maestría


Figura 6.31. Imagen 406 y 407 resultado del algoritmo MserSAD.

Tesis de Maestría






La figura 6.33 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el sur.

Tesis de Maestría


Figura 6.33. Imagen 138 y 139 resultado del buen desempeño del algoritmo HarrisSAD.

La figura 6.34 se interpreta que aunque hubo un buen desempeño del algoritmo debido a la

proximidad de los puntos correspondientes no se logra identificar el desplazamiento de la imagen.

Figura 6.34. Imagen 331 y 332 resultado del buen desempeño del algoritmo StarTex.

La figura 6.35 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el noreste.

Tesis de Maestría





Figura 6.36. Imagen 766 y 767 resultado del algoritmo MserCol.




La figura 6.37 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el norte.

Tesis de Maestría





Figura 6.38. Imagen 323 y 324 resultado del algoritmo MserSAD.

La figura 6.39 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el este.

Tesis de Maestría



La figura 6.40 se interpreta que aunque el algoritmo StarTex no obtuvo el 70 % mínimo que se

pidió para que se le considerará con un buen desempeño, se puede ver que los puntos están bien

orientados y la imagen experimentó un pequeño desplazamiento hacia el suroeste.


Entorno terrestre de interiores

Para analizar el entorno terrestre de interiores de edificio de oficinas se usaron dos repositorios

denominados Interiores1 e Interiores2.

Tesis de Maestría


o Repositorio Interiores1 e Interiores2

De las tablas C.31 a la C.42 del anexo C se extrajeron los datos que se muestran en las gráficas de

la figura 6.41 a la figura 6.44. En estas figuras se ilustra el desempeño de los algoritmos en la

muestra de los repositorios de Interiores.

La muestra que se seleccionó de los repositorios de Interiores estuvo conformada por los pares de

imágenes siguientes:

Del repositorio Interiores1: (im84,im85), (im259,im260), (im550,im551), (im637,im638).

Del repositorio Interiores2: (im197,im198), (im270,im271), (im330,im331), (im880,im881),

(im925,im926), (im1565,im1566), (im1613,im1614), (im1980,im1981).


Harris. Otra vez el comportamiento de MSER y Star en la búsqueda de características es muy

similar.

Figura 6.41. Número de características destacadas de los repositorios Interiores.

En la figura 6.42 se ve que, para esta muestra, en general la mayor cantidad de correspondencias se

encuentra en los algoritmos que tienen como detector de características a Harris.

0

100

200

300

400

500

600

im8

4

im8

5

im2

59

im2

60

im5

50

im5

51

im6

37

im6

38

im1

97

im1

98

im2

70

im2

71

im3

30

im3

31

im8

80

im8

81

im9

25

im9

26

im1

56

5

im1

56

6

im1

61

3

im1

61

4

im1

98

0

im1

98

1

MSER

Star

Harris

Número de imagen

Nú

mer

o d

e c

arac

terí

stic

as d

esta

cad

as

Tesis de Maestría


Figura 6.42. Número de correspondencias detectadas en la ejecución de los algoritmos.

En la figura 6.43 se tiene que, para esta muestra, en general la mejor precisión se presenta en los

algoritmos StarTex y MserSAD.

Figura 6.43. Precisión en la ejecución de los algoritmos.



existe una relación fuerte entre los algoritmos y las imágenes que analizan ya para el repositorio

Interiores1 el rango de los algoritmos que tienen en su etapa de emparejamiento descriptores de

textura varía de 1.736 a 34.91 y para el resto de los algoritmos varía de 0.011 a 0.577. Esto mismo

0

20

40

60

80

100

120

140

160

180

200

im8

4-im

85

im2

59

-im2

60

im6

37

-im6

38

im1

97

-im1

98

im2

70

-im2

71

im3

30

-im3

31

im8

80

-im8

81

im9

25

-im9

26

im1

56

5-im

15

66

im1

61

3-im

16

14

im1

98

0-im

19

81

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserColor

HarrisSAD

HarrisVNC

HarrisTex

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

im8

4-im

85

im2

59

-im2

60

im6

37

-im6

38

im1

97

-im1

98

im2

70

-im2

71

im3

30

-im3

31

im8

80

-im8

81

im9

25

-im9

26

im1

61

3-im

16

14

im1

98

0-im

19

81

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserColor

HarrisSAD

HarrisVNC

HarrisTex

Pareja de imágenes

Nú

mer

o d

e c

orr

esp

on

den

cias

Pareja de imágenes

Pre

cisi

ón

Tesis de Maestría


sucede para el repositorio de Interiores2 porque el rango de los algoritmos que tienen en su etapa de

emparejamiento descriptores de textura varía de 1.909 a 35.704 y para el resto de los algoritmos el

rango varía de 0.03 a 0.867.

Figura 6.44. Tiempo, medido en segundos, de los repositorios Interiores.

o Repositorio Interiores1

En las figuras 6.45 – 6.48 se muestran las imágenes muestra del repositorio Interiores1, con los

algoritmos en donde se obtuvo la mejor precisión.



0

10

20

30

40

50

60

im8

4-im

85

im2

59

-im2

60

im6

37

-im6

38

im1

97

-im1

98

im2

70

-im2

71

im3

30

-im3

31

im8

80

-im8

81

im9

25

-im9

26

im1

61

3-im

16

14

im1

98

0-im

19

81

StarSAD

StarVNC

StarTex

StarCol

MserSAD

MserVNC

MserTex

MserColor

HarrisSAD

HarrisVNC

HarrisTex

Pareja de imágenes

Tiem

po

(se

g)

Tesis de Maestría


En la figura 6.46 aunque se tiene un buen desempeño del algoritmo MserTex, debido a la

proximidad de los puntos correspondientes, no se logra identificar el desplazamiento de la imagen.





Tesis de Maestría



o Repositorio Interiores2

En las figuras 6.49 – 6.56 se presentan las imágenes muestra del repositorio Interiores2, con los

algoritmos en donde se obtuvo la mejor precisión.

La figura 6.49 se interpreta que aunque hubo un buen desempeño del algoritmo MserSAD debido a

la proximidad de los puntos correspondientes no se logra identificar el desplazamiento de la

imagen.


Tesis de Maestría



noroeste.




Tesis de Maestría






Tesis de Maestría


La figura 6.54 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el oeste.



suroeste.


Tesis de Maestría



suroeste.


6.4.3. Resumen de resultados

Del anexo C se extrajeron las tablas 6.2 a la 6.8, una por cada repositorio analizado. Estas tablas

contienen en sus entradas el nombre del par de imágenes analizadas, el número de repositorio al que

pertenecen estas imágenes, Una etiqueta que indica si este par de imágenes es texturizado o

estructurado y el nombre de los algoritmos que mejor funcionaron para este par de imágenes.

Tabla 6.2. Algoritmos que mejor se desempeñaron en el repositorio AQUA.

No. Par de Imágenes Conglomerado Algoritmos

1 im10

im11

3 (Texturizada)

3

StarTex (0.857), MserTex (0.765)

2 im74

im75

3 (Texturizada)

3

StarTex (0.788), MserTex (0.667)

3 im360

im361

1 (Texturizada)

1

MserSAD (0.65), MserTex (0.614) y MserCol

(0.74)

4 im620

im621

2 (Estructurada)

2

StarTex (0.82), MserSAD (0.62), MserTex (0.62)

5 im730

im731

1 (Texturizada)

1

Ninguno

6 im873

im874

4 (Estructurada)

4

MSER y Star no detectaron CDs

Harris no funcionó

Tesis de Maestría


7 im896

im897

4 (Estructurada)

4


Harris no funcionó

8 im930

im931

2 (Estructurada)

2


Harris no funcionó

9 im975

im976

1 (Texturizada)

1

MserSAD (1), MserVNC (1) MserTex (1) y

MserCol (1)

Tabla 6.3. Algoritmos que mejor se desempeñaron en el repositorio Exteriores_Urbanos.


1 im20

im21

1 (Texturizada)

1

MserTex (0.6)

2 im240

im241

3 (Texturizada)

3

StarSAD (0.733), MserSAD (0.78), MserTex

(0.66) y MserCol (0.72)

3 im452

im453

3 (Texturizada)

3

StarSAD (0.803), StarTex (0.8), MserSAD

(0.786), MserCol (0.743) y HarrisSAD (0.78)

4 im499

im500

2 (Texturizada)

2

MserTex (0.68)

5 im570

im571

1 (Texturizada)

1

StarSAD (0.757), StarTex (0.727), MserSAD

(0.727), MserTex (0.619) y HarrisSAD (0.79)

6 im1029

im1030

2 (Texturizada)

2

MserTex (0.66)

Tabla 6.4. Algoritmos que mejor se desempeñaron en el repositorio Exteriores_Naturales1.


1 im120

im121

1 (Texturizada)

1

Ninguno

2 im344

im345

2 (Texturizada)

2

StarSAD (0.852), MserSAD (0.84) y HarrisSAD

(0.8)

3 im406

im407

2 (Texturizada)

2

MserSAD (0.6), HarrisSAD (0.6)

4 im710

im711

1 (Texturizada)

1

StarTex (0.615)



1 im138

im139

2 (Texturizada)

2

StarSAD (0.89), StarTex (0.62), MserSAD (0.9) y

HarrisSAD (0.93)

2 im331

im332

2 (Texturizada)

2

StarSAD (0.712), StarTex (0.8), MserSAD (0.75)

y HarrisSAD (0.63)

Tesis de Maestría


3 im450

im451

1 (Texturizada)

1

StarTex (0.7)

4 im766

im767

1 (Texturizada)

1

Ninguno



1 im120

im121

2 (Texturizada)

2


HarrisSAD (0.83)

2 im323

im324

1 (Texturizada)

1

Ninguno

3 im480

im481

1 (Texturizada)

1

StarSAD (0.88), StarTex (0.66) y HarrisSAD

(0.62)

4 im720

im721

2 (Texturizada)

2

StarTex (0.67)

Tabla 6.7. Algoritmos que mejor se desempeñaron en el repositorio Interiores1.


1 im84

im85

1 (Estructurada)

1

StarTex

2 im259

im260

1 (Estructurada)

1

MserSAD, MserTex y HarrisSAD

3 im550

im551

2 (Estructurada)

2

Star no detectó características

MserSAD, MserVNC, MserTex y MserCol

4 im637

im638

2 (Estructurada)

2

StarSAD, StarCol, MserSAD, MserTex y

MserCol

Tabla 6.8. Algoritmos que mejor se desempeñaron en el repositorio Interiores2.


1 im197

im198

2 (Estructurada)

2

StarSAD (0.89), StarTex (0.73), StarCol (0.72),

MserSAD (0.913), MserTex (0.88), MserCol (0.74)

y HarrisSAD (0.6)

2 im270

im271

2 (Estructurada)

2

StarSAD (0.93), StarVNC (0.69), StarTex (0.81),

StarCol (0.83), MserSAD (0.78) y MserTex (0.75)

3 im330

im331

4 (Estructurada)

4

StarSAD (0.66), StarTex (0.77), MserSAD (0.8),

MserTex (0.77) y MserCol (0.75)

Tesis de Maestría


4 im880

im881

4 (Estructurada)

4


MserCol (0.6)

5 im925

im926

1 (Estructurada)

1

StarVNC (0.81), StarTex (1), StarCol (0.84),

MserSAD (0.64) y MserVNC (0.6)

6 im1565

im1566

3 (Estructurada)

3

MserVNC (0.66) y MserTex (1)

7 im1613

im1614

1 (Estructurada)

1

StarSAD (0.64), StarVNC (0.63), StarTex (0.7),

StarCol (0.6), MserSAD (0.86), MserVNC (0.73),

MserTex (1) y MserCol (0.85)

8 im1980

im1981

3 (Estructurada)

3

StarSAD (1), StarVNC (1), StarTex (1), StarCol

(1), MserSAD (1), MserVNC (1), MserTex (1) y

MserCol (1)

Utilizando los datos del anexo C se graficó el número de características destacadas y la precisión de

los algoritmos de correspondencia pero ahora tomando como muestras las imágenes estructuradas

(muestra estructurada) y las imágenes texturizadas (muestra texturizada) que resultaron de

particionar la muestra original de 39 pares de imágenes en 13 y 23 pares de imágenes

respectivamente. En las figuras siguientes se muestran estos resultados.

En la figura 6.57 se presenta el número de características que encontraron los tres detectores de

características en cada una de las 46 imágenes de la muestra texturizada analizada.

Figura 6.57. Número de características para la muestra de imágenes texturizadas.

Por otro lado en la figura 6.58 se presenta el número de características que encontraron los tres

detectores en cada una de las 32 imágenes de la muestra estructurada analizada.

0

200

400

600

800

1000

1200

1400

1600

1800

2000

im1

0

im7

4

im3

60

im7

30

im9

75

im2

0

im2

40

im4

52

im4

99

im5

70

im1

02

9

im1

20

im3

44

im4

06

im7

10

im1

38

im3

31

im4

50

im7

66

im1

20

im3

23

im4

80

im7

20

Nú

me

ro d

e c

arác

terí

stic

as

MSER

Star

Harris

Tesis de Maestría


Figura 6.58. Número de características para la muestra de imágenes estructuradas.

Comparando la figura 6.57 con la figura 6.58 se puede observar que el número de características

destacadas detectadas es considerablemente mayor en las imágenes de la muestra texturizada que en

las imágenes de la muestra estructurada. Además también llama la atención que la detección de los

algoritmos Star y MSER en lo general se mantuvo muy baja y más aún para la muestra de imágenes

estructuradas.

Con el fin de evaluar el desempeño de los doce algoritmos implementados con respecto al índice de

precisión pero ahora aplicados en las muestras texturizada y estructurada se tomaron los datos

denominados precisión del anexo C y se graficaron. Éstas gráficas se agruparon de acuerdo al

detector de características que utilizan, dando origen a las figuras 6.59, 6.60, 6.61, 6.62, 6.63 y 6.64.

En la figura 6.59 aparece la precisión para los algoritmos que en su fase de detección utilizan el

algoritmo Star aplicados en la muestra texturizada.

Figura 6.59. Precisión de los algoritmos con Star aplicados en la muestra texturizada.

0

200

400

600

800

1000

1200

1400

1600

1800

2000

im6

20

im8

73

im8

96

im9

30

im8

4

im2

59

im5

50

im6

37

im1

97

im2

70

im3

30

im8

80

im9

25

im1

56

5

im1

61

3

im1

98

0

Nú

me

ro d

e c

arac

terí

stic

as

MSER

Star

Harris

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

im1

0-im

11

im7

4-im

75

im3

60

-im3

61

im7

30

-im7

31

im9

75

-im9

76

im2

0-im

21

im2

40

-im2

41

im4

52

-im4

53

im4

99

-im5

00

im5

70

-im5

71

im1

02

9-im

10

30

im1

20

-im1

21

im3

44

-im3

45

im4

06

-im4

07

im7

10

-im7

11

im1

38

-im1

39

im3

31

-im3

32

im4

50

-im4

51

im7

66

-im7

67

im1

20

-im1

21

im3

23

-im3

24

im4

80

-im4

81

im7

20

-im7

21

Pre

cisi

ón

StarSAD

StarVNC

StarTex

StarCol

Tesis de Maestría



algoritmo Star aplicados en la muestra estructurada.

Figura 6.60. Precisión de los algoritmos con Star aplicados en la muestra estructurada.

De comparar las figuras 6.59 y 6.60 se observa que la precisión de estos cuatro algoritmos aumenta

considerablemente cuando éstos se aplican a imágenes que son estructuradas.


algoritmo MSER aplicados en la muestra texturizada.

Figura 6.61. Precisión de los algoritmos con MSER aplicados en la muestra texturizada.


algoritmo MSER aplicados en la muestra estructurada.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1

im6

20

-im6

21

im9

30

-im9

31

im8

4-im

85

im2

59

-im2

60

im6

37

-im6

38

im1

97

-im1

98

im2

70

-im2

71

im3

30

-im3

31

im8

80

-im8

81

im9

25

-im9

26

im1

61

3-im

16

14

im1

98

0-im

19

81

Pre

cisi

ón

StarSAD

StarVNC

StarTex

StarCol

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

im1

0-im

11

im7

4-im

75

im3

60

-im3

61

im7

30

-im7

31

im9

75

-im9

76

im2

0-im

21

im2

40

-im2

41

im4

52

-im4

53

im4

99

-im5

00

im5

70

-im5

71

im1

02

9-im

10

30

im1

20

-im1

21

im3

44

-im3

45

im4

06

-im4

07

im7

10

-im7

11

im1

38

-im1

39

im3

31

-im3

32

im4

50

-im4

51

im7

66

-im7

67

im1

20

-im1

21

im3

23

-im3

24

im4

80

-im4

81

im7

20

-im7

21

Pre

cisi

ón

MserSAD

MserVNC

MserTex

MserCol

Tesis de Maestría


Figura 6.62. Precisión de los algoritmos con MSER aplicados en la muestra estructurada.

Comparando las figuras 6.61 y 6.62 se observa que la precisión de estos cuatro algoritmos aumenta

considerablemente cuando éstos se aplican a imágenes que son estructuradas.


algoritmo Harris aplicados en la muestra texturizada.

Figura 6.63. Precisión de los algoritmos con Harris aplicados en la muestra texturizada.


algoritmo Harris aplicados en la muestra estructurada.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1

im6

20

-im6

21

im9

30

-im9

31

im8

4-im

85

im2

59

-im2

60

im5

50

-im5

51

im6

37

-im6

38

im1

97

-im1

98

im2

70

-im2

71

im3

30

-im3

31

im8

80

-im8

81

im9

25

-im9

26

im1

56

5-im

15

66

im1

61

3-im

16

14

im1

98

0-im

19

81

Pre

cisi

ón

MserSAD

MserVNC

MserTex

MserCol

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

im1

0-im

11

im7

4-im

75

im3

60

-im3

61

im7

30

-im7

31

im9

75

-im9

76

im2

0-im

21

im2

40

-im2

41

im4

52

-im4

53

im4

99

-im5

00

im5

70

-im5

71

im1

02

9-im

10

30

im1

20

-im1

21

im3

44

-im3

45

im4

06

-im4

07

im7

10

-im7

11

im1

38

-im1

39

im3

31

-im3

32

im4

50

-im4

51

im7

66

-im7

67

im1

20

-im1

21

im3

23

-im3

24

im4

80

-im4

81

im7

20

-im7

21

Pre

cisi

ón

HarrisSAD

HarrisVNC

HarrisTex

HarrisCol

Tesis de Maestría


Figura 6.64. Precisión de los algoritmos con Harris aplicados en la muestra estructurada.

De ver las figuras 6.63 y 6.64 se puede decir que no existen elementos de peso para afirmar que los

algoritmos de correspondencia que tienen en su fase de detección a Harris se desempeñan mejor en

alguna de las dos muestras (texturizada o estructurada).

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1

im6

20

-im6

21

im9

30

-im9

31

im8

4-im

85

im2

59

-im2

60

im5

50

-im5

51

im6

37

-im6

38

im1

97

-im1

98

im2

70

-im2

71

im3

30

-im3

31

im8

80

-im8

81

im9

25

-im9

26

im1

56

5-im

15

66

im1

61

3-im

16

14

im1

98

0-im

19

81

Pre

cisi

ón

HarrisSAD

HarrisVNC

HarrisTex

HarrisCol

Tesis de Maestría


Capítulo 7

7. Conclusiones y trabajos a futuro

Los resultados de todo el trabajo realizado en esta tesis, así como las aportaciones y trabajos a

futuro se resumen en las secciones siguientes.

7.1. Conclusiones

De acuerdo al análisis realizado, en la muestra de 39 pares de imágenes provenientes de ambos

entornos: acuático y terrestre, se formulan las conclusiones siguientes:

1. De la pertenencia de los conglomerados (tabla 5.20) se concluye que aunque en todos los

entornos aparecen tanto escenas texturizadas como estructuradas, en el entorno terrestre

exterior de tipo boscoso claramente predominan las escenas texturizadas y en el entorno

terrestre de interiores de edificio de oficinas claramente predominan las escenas

estructuradas.

2. Considerando el número de características destacadas (figuras 6.2, 6.15, 6.25 y 6.41), se

tiene que Harris detectó más características que MSER y Star en las imágenes de las

muestras analizadas.

3. Según estas mismas figuras MSER y Star presentan un comportamiento similar con

respecto al número de características destacadas detectadas.

4. De acuerdo con las figuras 6.57 y 6.58, los tres detectores extrajeron mayor cantidad de

características en la muestra de imágenes texturizadas que en la de estructuradas, en

particular los algoritmos MSER y Star detectaron muy pocas características en las imágenes

clasificadas como estructuradas, como se encontró para MSER en (Mikolajczyk, 2006).

5. De las correspondencias por repositorio (figuras 6.3, 6.16, 6.26 y 6.42) se infiere que los

algoritmos que utilizan descriptores de textura, en la fase de emparejamiento: StarTex,

MserTex y StarTex encuentran, relativamente, menor cantidad de correspondencias que el

resto de los algoritmos.

6. De los tiempos de procesamiento por repositorio (figuras 6.5, 6.18, 6.28 y 6.44) se

desprende que los algoritmos de correspondencia StarTex, HarrisTex y MserTex consumen

considerablemente más tiempo en su ejecución que el resto de los algoritmos.

7. Estos mismos tiempos de procesamiento muestran que existe una relación fuerte entre los

algoritmos: StarTex, HarrisTex, MserTex y las imágenes en donde se aplican ya que para

estos algoritmos el rango del tiempo varía de 1.736 a 495.58 mientras que para el resto de

los algoritmos el rango varía de 0.011 a 1.4. Este comportamiento se manifiesta aún para

imágenes que provienen del mismo repositorio, resultado que es muy importante tener en

cuenta para las implementaciones en tiempo real.

8. De acuerdo con las figuras 6.59, 6.60, 6.61 y 6.62 se infiere que los algoritmos de

correspondencia que tienen en su fase de detección de características destacadas a MSER o

Tesis de Maestría


Star, con respecto a la precisión se desempeñan mejor en las imágenes estructuradas que en

las texturizadas, como se encontró para MSER en (Mikolajczyk, 2006).

9. Considerando la tabla 5.20 que indica que existen entornos en donde se pueden encontrar

tanto escenas texturizadas como estructuradas, tal es el caso para el entorno acuático, y

además el hecho de que el desempeño de los algoritmos sí depende del tipo de escena,

texturizada o estructurada que se le presenta, se deduce que el desempeño de los doce

algoritmos de correspondencia implementados obedece más al tipo de escena (estructurada

o texturizada) que al tipo de entorno.

Según los resultados de la precisión de los algoritmos (figuras 6.4, 6.17, 6.27 y 6.43) se infieren

las siguientes conclusiones:

10. La precisión no está en función de los conglomerados de los repositorios analizados.

11. Los algoritmos HarrisSAD, HarrisVNC, HarrisTex y HarrisCol fueron los que, en función

de la precisión, mostraron un desempeño menor que el resto de los algoritmos.

12. Los algoritmos MserSAD, MserVNC, MserTex y MserCol fueron los que en función de la

precisión mostraron un mejor desempeño que el resto de los algoritmos.

13. Los algoritmos de correspondencia que utilizaron a SAD en su fase de emparejamiento

fueron los que en función de la precisión mejor respondieron.

14. Los algoritmos de correspondencia que en segundo lugar mejor se desempeñaron en

función de la precisión son aquellos que en su fase de emparejamiento utilizan el algoritmo

de Textura.

15. Los algoritmos de correspondencia que utilizan el algoritmo VNC en el módulo de

emparejamiento no son muy precisos.

16. Por mayoría de votos, el algoritmo de correspondencia que mejor se desempeñó, tomando

en cuenta únicamente la precisión, fue StarTex (Star, Ebola, Textura) seguido del algoritmo

MserSAD (MSER, Ebola, SAD) y tomando en cuenta tanto la precisión como el tiempo fue

MserSAD.

7.3. Aportaciones

1. Se realizó un análisis descriptivo para cada uno de los repositorios.

2. Se propuso una forma para clasificar a una imagen en texturizada o estructurada.

3. Se estableció en qué tipo de escena es más probable que funcione un algoritmo de

correspondencia de los implementados.

4. Se aportó en la asimilación del estado del arte de los algoritmos de correspondencia y su

aplicación en escenas de entornos acuáticos o terrestres.

Tesis de Maestría


7.4. Trabajos futuros

1. Buscar un mecanismo de desambiguación más eficiente.

2. Aplicar el nuevo mecanismo de clasificación de imágenes en texturizadas o estructuradas

en otros repositorios para identificar el porcentaje de clasificación correcto.

3. Buscar combinaciones de las variables NoHarris, NoMSER, NoStar, PromSize, PromRtotal

para ver si alguna de ellas sirve para clasificar las imágenes texturizadas en homogéneas o

no homogéneas.

4. Realizar modificaciones al sistema para que los parámetros se ajusten de manera automática

al tipo de imagen.

Tesis de Maestría


Referencias

Referencias bibliográficas

(Baumela, 2007) L. Baumela, Visión por Computador, Departamento de Inteligencia

Artificial, Universidad Politécnica de Madrid, 2007.

(Bonfim, 2010) R. Bonfim, S. R. M. Pellegrino, An Experimental Evaluation of

Algorithms for Aerial Image Matching, IWSSIP 2010 – 17th International

Conference on Systems, Signals and Image Processing 416, 2010.

(Booch, 2005) G. Booch, J. Rumbaugh, I. Jacobson, El Lenguaje Unificado de Modelado

Guía del Usuario, segunda edición, Addison-Wesley, 2005.

(Brown, 2003) Z. Brown and B. Darius, Advances in Computational Stereo, IEEE

Transactions on Pattern Analysis and Machine Intelligence, Volume 25,

No. 8, August 2003.

(Cyganek, 2009) B. Cyganek, J. Siebert, An Introduction to 3D Computer Vision

Techniques and Algorithms, John Wiley & Sons, Ltd. ISBN: 978-0-470-

01704-3, 2009.

(Ebrahimi, 2009) M. Ebrahimi and W. Mayol-Cuevas, SUSurE: Speeded Up Surround

Extrema Feature Detector and Descriptor for Realtime Applications,

IEEE Computer Society Conference on Computer Vision and Pattern

Recognition 2009. ISBN: 978-1-4244-3994-2, 2009.

(Fuentes, 2008)

A. Fuentes, Seguimiento y Asimiento de un Objeto en Movimiento por

Medio de un Robot Manipulador y Visión Estéreo, CENIDET, tesis de

maestría, 2008.

(Fuentes, 2009) A. Fuentes, J. Ruiz, J. Rendón, J. M. Binocular visual tracking and

grasping of a moving object with a 3D trajectory predictor, Journal of

Applied Research and Technology, Vol. 7, Núm. 3, 2009, pp. 259-274.

Universidad Nacional Autónoma de México, México, 2009.

(García, 2001) R. García, X. Cufi and J. Batlle, Detection of Matchings in a Sequence of

Underwater Images through Texture Analysis, Image Processing, 2001

International Conference on. Volume, 2001.

(Graffigna, 2005) J. Graffigna, L. Romero y R. Romo, Evaluación de Métodos para la

Obtención del Mapa de Disparidad en Sistemas de Visión Estéreo, XV

CONGRESO ARGENTINO DE BIOINGENIERIA: 075PI, 2005.

(Gómez, 2008) A. Gómez y I. Zamorano, Visión estereoscópica y estimación de pose para

el posicionamiento de un brazo robótico, CENIDET, tesis de maestría,

2008.

Tesis de Maestría


(González, 2011) S. González, Visión Artificial Estéreo Binocular para Robot Móvil en

Ambientes Exteriores Simulados, CENIDET, tesis de maestría, 2011.

(Harris, 1988)

C. Harris y M. Stephens, A combined corner and edge detector,

Proceedings of the 4th Alvey Vision Conference: pages 147-151, 1988.

(Hsiu, 2008) S. Te-Hsiu, K-Cosine Corner Detection, Journal of Computers, Vol 3 No.

7, July 2008.

(Huang, 2008) D. Huang, D. Wunsch II and D. Levine, Advanced Intelligent Computing

Theories and Applications With Aspects of Contemporary Intelligent

Computing Techniques, 4th International Conference on Intelligent

Computing, ICIC 2008 Shanghai, China, September 15-18, 2008,

Proceedings.

(Joyanes, 2008) L. Joyanes, Fundamentos de Programación, Ed. Mc Graw Hill, Cuarta

edición, 2008.

(Kenton, 2010a)

O. Kenton, W. Hou, S. Wang. Image Feature Detection and Matching in

Underwater Conditions, Proceedings of SPIE Volume 7678 (Ocean

Sensing and Monitoring II), Orlando, FL, 2010.

(Kenton, 2010b) O. Kenton, W. Hou, S. Wang. Feature Matching in Underwater

Environments using Sparse Linear Combinations, IEEE Workshop on

Object Tracking and Classification Beyond and in the Visible Spectrum,

San Francisco, CA, 2010.

(Konstantinos, 2000) G. Konstantinos, The Harris Corner Detector, Computer Vision Related

Notes, 2000.

(Kuhl, 2004) A. Kuhl, Comparison of Stereo Matching Algorithms for Mobile Robots,

Master Thesis, Fakultat fur Informatik und Automatisierung, Technische

Universitat IImenau, 2004.

(Lepistö, 2003) Leena Lepistö, Iivari Kunttu, Jorma Autio, and Ari J. Visa, Data mining

on non-homogenous textures, Proc. SPIE 5098, 1 (2003);

doi:10.1117/12.486011.

(Li, 2000) Jia Li, James Ze Wang, and Gio Wiederhold, Classification of Textured

and non-textured images using region segmentation, in 7th International

Conference on Image Processing-ICIP, 2000.

(Lipschutz, 1965) S. Lipschutz, General Topology, Schawm Publishing Company, New

York, 1965.

(López, 2005) J. López, A. Fernández-Caballero y M. A. Fernandez, Conceptos y

Técnicas de Estereovisión por Computador, Revista Iberoamericana de

Inteligencia Artificial, Vol. 9, No. 27, 2005.

Tesis de Maestría


(Martínez, 2007) O. Martínez, A. Gil, M. Ballesta and O. Reinoso, Interest Point Detector

for Visual SLAM, in Proceedings of the Conference of the Spanish

Association for Artificial Intelligence (CAEPIA), (Salamanca, Spain),

pp. 217-226, November 2007.

(Matas, 2002) J. Matas, O. Chum, M. Urban, T. Pajdla, Robust wide baseline stereo from

maximally stable extremal regions, In British Machine Vision Conference,

Vol. 1 (2002), pp. 384-393. Key: citeulike:3578267.

(Mikolajczyk, 2002) K. Mikolajcczyk, C. Schmid, An affine invariant interest point detector,

“Proc. European Conf. Computer Vision”, Páginas 128-142, 2002.

(Mikolajczyk, 2006)

K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F.

Schaffalitzky, T. Kadir, L. Van Gool, A Comparison of Affine Region

Detectors, International Journal of Computer Vision, 65(1/2):43-72, 2006.

(Morales, 2009) L. Morales y L. Minaya, Reconstrucción del medio ambiente utilizando

visión estereoscópica, Facultad de Ingeniería Industrial y de Sistemas de

la Universidad Nacional de Ingeniería, tesis de licenciatura, 2009.

(Pajares, 2008) G. Pajares, Visión por Computador Imágenes Digitales y Aplicaciones,

Ed. Alfaomega Ra-Ma, 2008.

(Pérez, 2002) A. Pérez, Diseño de un Sistema de Calibración Automático para un

Sistema de Visión Robótica, CENIDET, tesis de maestría, 2002.

(RAD, 2001) Real Academia Española, Diccionario de la Lengua Española, Vigésima

Segunda Edición, 2001.

(Ruiz, 2005) C. Ruiz, VISIÓN COMPUTACIONAL. Retos Científicos de la

Computación. VISIÓN ESTEREOSCÓPICA. TÉCNICAS DE

CORRESPONDENCIA, 2005.

(Sánchez, 2003)

A. Sánchez, Auto-calibración de un sistema binocular de visión activa,

Depto. Ingeniería de Sistemas y Automática. Universidad Politécnica de

Valencia, Camino de Vera. Apdo. 22012 E-46071 Valencia, 2003.

(Scharstein, 2002)

D. Scharstein and R. Szeliski, A Taxonomy and Evaluation of Dense Two-

Frame Stereo Correspondence Algorithms, International Journal of

Computer Vision, Volume 47, Numbers 1-3, Pages 7-42, Springer

Netherlands, 2002.

(Shi, 1994) J. Shi and C. Tomasi, Good Features to Track, Proceedings of the IEEE

Conference on Computer Vision and Pattern Recognition, pages 593-600,

June 1994.

(Tell, 2002)

D. Tell, Wide Baseline Matching with Applications to Visual Servoing,

Doctoral Dissertation, Royal Institute of Technology, Stockholm, 2002.

(Tuytelaars, 2008) T. Tuytelaars and K. Mikolajczyk, Local Invariant Feature Detectors: A

Survey, Foundations and TrendsR_in Computer Graphics and Vision, Vol.

Tesis de Maestría


3, No. 3, Pages 177–280, 2008.

(Vincent, 2001) E. Vincent and R. Laganiére, Matching Feature Points in Stereo Pairs: A

comparative Study of Some Matching Strategies, School of Information

Technology and Engineering, University of Ottawa, Ottawa, ONT K1N

6N5, 2001.

(Williams, 2010) B. Williams and I. Reid, On Combining Visual SLAM and Visual

Odometry, Proceedings of the IEEE Conference on Robotics and

Automation, May 2010.

(Yen, 2010)

S. Yen, C. Shih, T. Li and H. Chang, Applying Multiple KD-Trees in High

Dimensional Nearest Neighbor Searching, International Journal of

Circuits Systems and Signal Processing, Volume 4, 2010.

Referencias electrónicas

[1] WIKIPEDIA. The Free Encyclopedia. URL:

http://en.wikipedia.org/wiki/Harris_affine_region_detector, fecha de último acceso: fecha de

acceso: 10/08/2011.

[2] Comparison of the OpenCV’s feature detection. URL: http://computer-vision-

talks.com/2011/01/comparison-of-the-opencvs-feature-detection-algorithms-2/, fecha de

acceso: 10/08/2011.

Tesis de Maestría


Anexos

Anexo A. Atributos y métodos de la superclase Correspondencia

Enseguida se presenta la sintaxis de la clase base Correspondencia, con algunos comentarios que describen concisamente

el atributo o método de esta superclase.

class Correspondencia {

public:

Correspondencia(); //Constructor de la clase Correspondencia virtual ~Correspondencia(); //Destructor de la clase Correspondencia

void SetCad(char* rut1,char* rut2,char* rut3,char* rut4,int NumAlg1); //Función que sirve para pasar las rutas de Estrategia

void Calcular(); //Aquí se determina que funciones se ejecutan

protected:

//VARIABLES DE CONTROL INTERNO

int NumAlg; //No. de algoritmo

double secs; //Variable que mide el tiempo

int d1; //Entero que controla la ejecución de los procesos del algoritmo

//VARIABLES DE CDs Y PAREJAS

int x1; //Cota superior para No. de esquinas en Harris

int K1; //No. de vecinos en K-vecinos

int eps1; //Radio de disco (Épsilon-bola y color)

int d; //Distancia (Épsilon-bola, K-vecinos y color)(0=Manhattan, 1=euclidiana)

int ud; //No. de desplazamientos

int es1; //No. de CDs de la vista 1

int es2; //No. de CDs de la vista 2

int m1; //No. de pares de puntos correspondientes vista 1

int m2; //No. de pares de puntos correspondientes vista 2 int m; //No. de pares de puntos correspondientes después de desambiguación

int **esq1; //matriz de CDs de la imagen1 int **esq2; //matriz de CDs de la imagen2

int **M1; //Matriz de puntos correspondientes vista 1 int **M2; //Matriz de puntos correspondientes vista 2

int **M; //Matriz de puntos correspondientes

//VARIABLES DE IMÁGENES

char* ruta1; //ruta donde se encuentra vista1

char* ruta2; //ruta donde se encuentra vista2

char* ruta3; //ruta donde se almacenarán las salidas char* ruta4; //ruta donde se almacenarán los libros

IplImage *img1; //imagen de vista1

IplImage *img2; //imagen de vista2

IplImage *img3; //imagen de salida IplImage *img4; //imagen de vista1 color

IplImage *img5; //imagen de vista2 color

Tesis de Maestría


//Funciones que requerirán de implementaciones particulares en la clase base

virtual void CD(int **&esqui,int &e,IplImage *imag,int &x,int &b1)=0;

virtual void Buscar(int **&N,int &n,int **esqui1,int e1,int **esqui2,int e2,int &K,int &eps,int &d,int &b1)=0; virtual void Corresp(int **&N1,int &e1,IplImage *imag1,IplImage *imag2,int &eps,int &d,int &ud1,int &b1)=0;

}; //Termina clase base

Las funciones que requerirán de implementaciones particulares en las subclases tendrán distintos comportamientos dependiendo de la

función que se llame, de acuerdo a la estrategia que se elija son:

virtual void CD(int **&esqui,int &e,IplImage *imag,int &x,int &b1)

virtual void Buscar(int **&N,int &n,int **esqui1,int e1,int **esqui2,int e2,int &K,int &eps,int &d,int &b1)

virtual void Corresp(int **&N1,int &e1,IplImage *imag1,IplImage *imag2,int &eps,int &d,int &ud1,int &b1)

A continuación se especifican los posibles comportamientos para cada una de estas funciones virtuales.

Función CD

La función CD implementa la etapa de características destacadas del algoritmo Correspondencia, tiene la sintaxis siguiente:

virtual void CD(int **&esqui,int &e,IplImage *imag,int &x,int &b1)

Parámetros

esqui = Arreglo de esquinas que se va a modificar e=No. de puntos característicos encontrados en la imagen imag

imag = Imagen de donde se van a obtener las esquinas

x=Cota superior de número de características destacadas b1= Entero que indica si el proceso de búsqueda de CDs se ejecutó de manera exitosa

Tiene los tres comportamientos siguientes:

void Harris(int **&esqui,int &e,IplImage *imag,int &x,int &b1) void StarKeyPoint1(int **&esqui,int &e,IplImage *imag,int &x,int &b1)

void Mser1(int **&esqui,int &e,IplImage *imag,int &x,int &b1)

Harris

La función Harris usó para su implementación cvGoodFeaturesToTrack, función de OpenCV 2.1 que determina esquinas fuertes en una

imagen usando el algoritmo de Shi-Tomasi. Tiene la sintaxis siguiente:

public static void cvGoodFeaturesToTrack(

const CvArr *image, const CvArr *eigImage,

const CvArr *tempImage,

CvPoint2D32f * corners, int *cornerCount,

double qualityLevel,

double minDistance, const CvArr *mask CV_DEFAULT(NULL),

int blockSize CV_DEFAULT(3),

int useHarris CV_DEFAULT(0), double k CV_DEFAULT(0.04)

)

Parámetros:

image (IntPtr)

Imagen de un solo canal, de origen de 8-bits o de punto flotante de 32-bits


http://msdn2.microsoft.com/en-us/library/td2s409d







Tesis de Maestría


eigImage (IntPtr)

Imagen temporal de punto flotante de 32 bits del mismo tamaño que la imagen

tempImage (IntPtr)

Otra imagen temporal del mismo tamaño y el mismo formato que eigImage

corners (IntPtr)

Parámetro de salida. Esquinas detectadas

cornerCount ( Int32 )

Parámetro de salida. Número de esquinas detectadas

qualityLevel (Double)

Multiplicador para el valor propio maxmin que especifica la calidad mínima aceptada de esquinas de la imagen.

minDistance (Double)

Límite, que especifica la distancia mínima posible entre las esquinas regresadas. Se utiliza la distancia euclidiana.

Mask (IntPtr)

Región de interés. La función selecciona los puntos entre la región especificada o la imagen completa si mask es NULL.

blockSize (Int32)

Tamaño del bloque promedio, pasó a cvCornerMinEigenVal o cvCornerHarris a través de la función.

useHarris (Int32)

Si el operador Harris (cvCornerHarris) es distinto de cero ser usa en lugar de cvCornerMinEigenVal.

K (Double)

Es un parámetro libre del detector de Harris, se usa solo si useHarris es distinto de cero.

la función Harris utiliza la variable x (int) que representa una cota superior para el número de esquinas.

StarKeyPoint1

La función StarKeyPoint1 usó para su implementación cvGetStarKeypoints, función de OpenCV 2.1 que recupera puntos clave usando el

algoritmo de detección de características Star. Tiene la sintaxis siguiente:

(

int maxSize CV_DEFAULT(45), int responseThreshold CV_DEFAULT(30),

int lineThresholdProjected CV_DEFAULT(10),

int lineThresholdBinarized CV_DEFAULT(8), int suppressNonmaxSize CV_DEFAULT(5))

Parámetros:

image ()

Imagen de un solo canal, de origen de 8-bits.

(

Memoria donde se guardarán los blobs.

(int maxSize CV_DEFAULT(45),

int responseThreshold CV_DEFAULT(30),

int lineThresholdProjected CV_DEFAULT(10), int lineThresholdBinarized CV_DEFAULT(8),

int suppressNonmaxSize CV_DEFAULT(5))( )

permanecen los valores por default

cvGetStarKeypoints es una secuencia de estructuras del tipo CvStarKeypoint que representan la característica calculada. Esta estructura tiene la lista de miembros siguiente:

CvStarKeypointCvStarKeypoint

Mser1











Tesis de Maestría


La función Mser1 usó para su implementación cvExtractMSER, función de OpenCV 2.1 que obtiene regiones extremas máximamente

estables clave usando el algoritmo de detección de características MSER. Tiene la sintaxis siguiente:

public static void cvExtractMSER(

const CvArr *img, const CvArr *mask,

const CvSeq **contours,

CvMemStorage *storage, CvMSERParams params

)

Parámetros:

img () Imagen de un solo canal, de origen de 8-bits.

(const CvArr* Es la máscara para la región de interés

contours (CvSeq **) Es una secuencia de secuencias de píxeles que representan las MSER. La cardinalidad de cada secuencia de píxeles se puede

calcular utilizando la propiedad de “total” de la secuencia y como consecuencia se puede conocer el tamaño de cada una las

regiones.

Storage (CvMemStorage *)

Es la memoria de almacenamiento.

Params(CvMSERParams)

Son los parámetros de las MSER que se almacenan en la estructura CvMSERParams mediante la ejecución de la función cvMSERParams que tiene los parámetros siguientes:

MSERParams(int delta CV_DEFAULT(5), int min_area CV_DEFAULT(60),

int max_area CV_DEFAULT(14400),

float max_variation CV_DEFAULT(.25f), float min_diversity CV_DEFAULT(.2f),

int max_evolution CV_DEFAULT(200),

double area_threshold CV_DEFAULT(1.01),

double min_margin CV_DEFAULT(.003),

int edge_blur_size CV_DEFAULT(5))CvMSERParams

En el código, ella compara (size_{i}-size_{i-delta})/size_{i-delta}

Poda el área que tiene el tamaño menor a min_area.

max_area (int) Poda el área que es mayor que max_area.

max_variation (float)

Poda el área que tiene el tamaño similar a sus hijos. min_diversity (float)

Aisla MSER con diversidad menor a min_diversity

max_evolution (int) La evolución de los pasos para el color de la imagen.

area_threshold (double)

El umbral para causar la reinicialización. min_margin (double)

Ignora excedentes demasiado pequeños

edge_blur_size (int) Determina el tamaño de la apertura para el borde de la mancha.

Typedef struct CvMSERParams {

cvMSERParams( );

} CvMSERParams

Esta estructura se llena mediante la ejecución de la función cvMSERParams().

Función Buscar

Tesis de Maestría


La función Buscar, la cual implementa la etapa de búsqueda del algoritmo Correspondencia, tiene la sintaxis siguiente:

virtual void Buscar(int **&N,int &n,int **esqui1,int e1,int **esqui2,int e2,int &K,int &eps,int &d,int &b1)

Parámetros:

N = Arreglo con las esquinas de la vista1, aquí se van a almacenar las parejas encontradas n = Número de puntos correspondientes

esqu1 = Arreglo con las esquinas de la vista1,

e1 = Número de esquinas de la vista 1 esqui2 = Arreglo con las esquinas de la vista2

e2 = Número de esquinas de la vista 2

K = El número de vecinos para el algoritmo K-vecinos eps = radio de la vecindad para Épsilon-bola

d = distancia que se utiliza para la búsqueda (1=Manhattan, 2=Euclidiana)

b1 = Entero que indica si el proceso Buscar se realizó de manera exitosa

El comportamiento que tiene es:

void Ebola(int **&N,int &n,int **esqui1,int e1,int **esqui2,int e2,int &K,int &eps,int &d,int &b1)

Esta función utiliza dos variables esps (int) y d (int) que representan el radio de la Épsilon-bola y la distancia respectivamente. Si se elige

1 para la distancia, se ejecutará la distancia Manhattan y si se elige 2, la distancia euclidiana.

Función Corresp

La función Corresp, la cual implementa la etapa de emparejamiento del algoritmo Correspondencia, tiene la sintaxis siguiente:

virtual void Corresp(int **&N1,int &e1,IplImage *imag1,IplImage *imag2,int &eps,int &d,int &ud1,int &b1)

Parámetros:

N1 = Primer arreglo de puntos correspondientes

e1 = Tamaño de N1

imag1 = Vista1 imag2 = Vista2

eps = radio para disco de proceso color

d = distancia para disco de proceso color (d=1 Manhattan, d=2 euclidiana) ud1 = unidades de desplazamiento de proceso textura

b1 = Entero que indica si el proceso Corresp se realizó de manera exitosa

Tiene los cuatro comportamientos siguientes:

void SAD(int **&N1,int &e1,IplImage *imag1,IplImage *imag2,int &eps,int &d,int &ud1,int &b1)

void NCC(int **&N1,int &e1,IplImage *imag1,IplImage *imag2,int &eps,int &d,int &ud1,int &b1)

void Textura(int **&N1,int &e1,IplImage *imag1,IplImage *imag2,int &eps,int &d,int &ud1,int &b1) void Color(int **&N1,int &e1,IplImage *imag1,IplImage *imag2,int &eps,int &d,int &ud1,int &b1)

La función Textura utiliza la variable ud1 (int) que corresponde al número de unidades de desplazamiento de la matriz de coocurrencia.

La función Color utiliza las variables eps (int) y d (int) que corresponden al radio del disco y la distancia respectivamente. Si se elige 1

para la distancia, se ejecutará la distancia Manhattan y si se elige 2, la distancia euclidiana.

Función Desam

La función Desam, implementa la etapa de desambiguación del algoritmo Correspondencia y tiene la sintaxis siguiente:

void Desam(int **&N,int &n,int **N1,int n1,int **N2,int n2,int &b1)

Parámetros:

Tesis de Maestría


N = Arreglo de parejas de puntos correspondientes final

n = Tamaño de N

N1 = Arreglo de parejas de puntos correspondientes de la vista1 n1 = Tamaño de N1

N2 = Arreglo de parejas de puntos correspondientes de la vista2

n2 = Tamaño de N2 b1 = Entero que indica si el proceso Desam se realizó de manera exitosa

Módulos del sistema

Los módulos del sistema19 se organizaron de la siguiente manera:

Se diseñaron dos módulos: Semejanza y Busqueda.

Semejanza contiene las clases: Uno, Dos, Tres, Cuatro, Cinco, Seis, Siete, Ocho, Nueve, Diez, Once y Doce. Las cuales están encargadas

del proceso emparejamiento.

Busqueda contiene las clases: Fact1, Fact2 y Fact3, las cuales están encargadas del proceso de búsqueda.

El resto de las clases se manejaron en módulos por separado por la cantidad de código que contenían. Como se muestra en el diagrama 4.4.

Figura A.1. Diagrama de módulos.

Procesamiento de los objetos20

En la función Calcular de la clase Correspondencia se llevan a cabo los procesos correspondientes a cada una de las fases del algoritmo de Correspondencia.

Para la obtención del objeto arreglo de pares correspondientes se realizó el siguiente procedimiento:

1. Inicialización de las variables necesarias para todo el proceso del algoritmo de correspondencia:

secs, d1, d, eps1, K1, ud, x1, es1, es2, m1, m2, m, esq1, esq2, M1, M2, M, ruta1, ruta2, ruta3, ruta4, img1, img2, img3, img4, img5

2. Cálculo de las características destacadas de la vista 1 mediante la aplicación de la función CD:

CD(esq1,es1,img1,x1,d1)

3. Cálculo de las características destacadas de la vista 2 con aplicación de la función CD pero ahora aplicada en la imagen 2.

CD(esq2,es2,img2,x1,d1)

19

Es un subprograma que ejecuta una única actividad o tarea y se analiza, codifica y pone a punto por separado (Joyanes, 2008). 20

Un objeto encapsula información y comportamiento. Es un término que representa una cosa concreta del mundo real (Joyanes, 2008)

llama llama

Mser1.hpp Harris.hpp StarKeyPoint1.hpp

Correspondencia.hpp

Main.cpp Estrategia.hpp Semejanza.hpp Busqueda.hpp

llama

llama llama llama

llama

Tesis de Maestría


4. Se obtiene el arreglo de puntos correspondientes para los indicadores de la vista 1 con la aplicación de la función Buscar en el arreglo

de CDs de la vista 1.

Buscar(M1,m1,esq1,es1,esq2,es2,K1,eps1,d,d1)

5. Se obtiene el arreglo de puntos correspondientes para los indicadores de la vista 2 con la aplicación de la función Buscar pero ahora en

el arreglo de CDs de la vista 2.

Buscar(M2,m2,esq2,es2,esq1,es1,K1,eps1,d,d1)

6. Si la fase de emparejamiento se va a llevar a cabo con el algoritmo de Color se aplica la función:

Corresp(M1,m1,img4,img5,eps1,d,ud,d1)

para obtener el conjunto de pares de puntos correspondientes de la vista 1 a la vista 2 y seguidamente se aplica la función:


para obtener el conjunto de pares de puntos correspondientes de la vista 2 a la vista 1.

En el caso de que la fase de emparejamiento se lleve a cabo con alguno de los algoritmos SAD, VNC o Textura, se aplica la función:


para obtener el arreglo de pares de puntos correspondientes de la vista 1 a la vista 2 y seguidamente se aplica la función:


para obtener el conjunto de pares de puntos correspondientes de la vista 2 a la vista 1.

7. Una vez que se tienen los arreglos M1 y M2 correspondientes a los conjuntos de pares de puntos correspondientes de la vista 1 y 2

respectivamente se aplica la función:

Desam(M,m,M1,m1,M2,m2,d1)

para obtener el arreglo M de pares estereoscópicos. En este paso se termina el proceso de correspondencia de puntos.

Tesis de Maestría


Anexo B. Salidas de SPSS Statistics 19

Conglomerados de AQUA

QUICK CLUSTER PromSize

/MISSING=LISTWISE /CRITERIA=CLUSTER(4) MXITER(10) CONVERGE(0)

/METHOD=KMEANS(NOUPDATE)

/SAVE CLUSTER DISTANCE /PRINT INITIAL.

Análisis de conglomerados de K medias

Notas

Resultados creados 30-jul-2011 16:50:20

Comentarios Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTE

RS\AQUA\AQUA.sav

Conjunto de datos activo Conjunto_de_datos1

Filtro <ninguno>

Peso <ninguno>

Segmentar archivo <ninguno> Núm. de filas del archivo de trabajo 998

Tratamiento de los datos perdidos Definición de perdidos Los valores definidos como perdidos por el

usuario son considerados como perdidos. Casos utilizados Los estadísticos se basan en los casos sin valores

perdidos para las variables de aglomeración

utilizadas. Sintaxis QUICK CLUSTER PromSize

/MISSING=LISTWISE

/CRITERIA=CLUSTER(4) MXITER(10) CONVERGE(0)



Recursos Tiempo de procesador 00 00:00:00,109 Tiempo transcurrido 00 00:00:00,125

Espacio de trabajo necesario 408 bytes

Variables creadas o modificadas QCL_1 Número inicial de casos

QCL_2 Distancia del caso desde su centro inicial de

clasificación

Centros iniciales de los conglomerados

Conglomerado

1 2 3 4

11,0000 16,0000 6,0000 ,0000

Centros de los conglomerados finales

Conglomerado

1 2 3 4

PromSize 10,9631 14,0631 8,9615 ,0000

Número de casos en cada conglomerado

Conglomerado 1 442,000

2 149,000

3 320,000

4 87,000 Válidos 998,000

Perdidos ,000

Historial de iteracionesa

Iteración

Cambio en los centros de los

conglomerados

1 2 3 4

1 ,448 1,347 1,768 ,000

2 ,068 ,505 ,564 ,000

3 ,077 ,138 ,238 ,000 4 ,075 ,042 ,156 ,000

5 ,067 ,031 ,087 ,000

6 ,050 ,021 ,063 ,000 7 ,027 ,021 ,029 ,000

8 ,019 ,011 ,023 ,000

9 ,010 ,010 ,010 ,000 10 ,009 ,000 ,013 ,000

a. Se han detenido las iteraciones debido a que se ha alcanzado el número máximo de iteraciones. Las

iteraciones no han logrado la convergencia. El cambio

máximo de coordenadas absolutas para cualquier centro es de ,013. La iteración actual es 10. La distancia

mínima entre los centros iniciales es de 5,000.

Tesis de Maestría


Conglomerados de Exteriores_Urbanos

QUICK CLUSTER PromSize /MISSING=LISTWISE


/METHOD=KMEANS(NOUPDATE) /SAVE CLUSTER DISTANCE

/PRINT INITIAL.


Notas


Comentarios Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTE

RS\Urbanos\Urbanos.sav

Conjunto de datos activo Conjunto_de_datos4 Filtro <ninguno>

Peso <ninguno>






/MISSING=LISTWISE







QCL_2 Distancia del caso desde su centro inicial de clasificación


Conglomerado

1 2 3

PromSize 7,7949 9,7391 5,8625


Conglomerado

1 2 3

PromSize 7,4295 8,3444 6,7931



2 117,000

3 547,000

Válidos 1162,000

Perdidos ,000


Iteración

Cambio en los centros de los conglomerados

1 2 3

1 ,416 ,643 ,744

2 ,039 ,479 ,122 3 ,018 ,145 ,044

4 ,003 ,075 ,018

5 ,001 ,021 ,003 6 ,003 ,012 ,000

7 ,002 ,008 ,000

8 ,003 ,012 ,000 9 ,001 ,000 ,001

10 ,000 ,000 ,000

a. Se ha logrado la convergencia debido a que los centros de los

conglomerados no presentan ningún cambio o éste es pequeño.

El cambio máximo de coordenadas absolutas para cualquier centro es de ,000. La iteración actual es 10. La distancia


Tesis de Maestría


Conglomerados de Exteriores_Naturales1


/MISSING=LISTWISE

/CRITERIA=CLUSTER(2) MXITER(10) CONVERGE(0) /METHOD=KMEANS(NOUPDATE)

/SAVE CLUSTER DISTANCE

/PRINT INITIAL.


Notas

Resultados creados 24-ago-2011 13:49:59

Comentarios Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTER

S\Naturales1\Naturales1.sav


Filtro <ninguno>

Peso <ninguno>






/MISSING=LISTWISE








clasificación


Conglomerado

1 2

PromSize 9,7273 5,4607


Conglomerado

1 2

PromSize 7,3097 6,5202



2 939,000

Válidos 1560,000

Perdidos ,000


Iteración


1 2

1 1,690 1,287

2 ,238 ,042 3 ,127 ,031

4 ,077 ,021

5 ,061 ,019 6 ,047 ,017

7 ,044 ,018

8 ,040 ,020 9 ,037 ,021

10 ,031 ,020

a. Se han detenido las iteraciones debido a que

se ha alcanzado el número máximo de

iteraciones. Las iteraciones no han logrado la convergencia. El cambio máximo de

coordenadas absolutas para cualquier centro es de ,031. La iteración actual es 10. La distancia


Tesis de Maestría




/MISSING=LISTWISE



/PRINT INITIAL.


Notas





Filtro <ninguno>

Peso <ninguno>






/MISSING=LISTWISE








clasificación


Conglomerado

1 2

PromSize 10,8114 5,1429


Conglomerado

1 2

PromSize 7,9142 6,5764



2 1230,000

Válidos 1861,000

Perdidos ,000


Iteración


1 2

1 2,298 1,675

2 ,253 ,086 3 ,142 ,058

4 ,089 ,041

5 ,046 ,022 6 ,021 ,010

7 ,012 ,006

8 ,010 ,005 9 ,012 ,006

10 ,010 ,005






Tesis de Maestría




/MISSING=LISTWISE



/PRINT INITIAL.


Notas





Filtro <ninguno>

Peso <ninguno>






/MISSING=LISTWISE








clasificación


Conglomerado

1 2

PromSize 13,6000 4,0000


Conglomerado

1 2

PromSize 7,2495 5,6244



2 704,000

Válidos 1117,000

Perdidos ,000


Iteración


1 2

1 4,241 2,174

2 ,906 ,098 3 ,591 ,161

4 ,247 ,109

5 ,133 ,059 6 ,074 ,037

7 ,046 ,023

8 ,033 ,017 9 ,030 ,016

10 ,030 ,017






Tesis de Maestría


Conglomerados de Interiores1




/PRINT INITIAL.


Notas



S\Interiores1\Interiores1.sav


Peso <ninguno>






/MISSING=LISTWISE








clasificación


Conglomerado

1 2

PromSize 16,0000 ,0000


Conglomerado

1 2

PromSize 10,1664 ,1829



2 164,000 Válidos 662,000

Perdidos ,000


Iteración


conglomerados

1 2

1 5,283 2,198 2 ,376 1,384

3 ,155 ,569

4 ,019 ,062 5 ,000 ,000

a. Se ha logrado la convergencia debido a que

los centros de los conglomerados no presentan

ningún cambio o éste es pequeño. El cambio

máximo de coordenadas absolutas para

cualquier centro es de ,000. La iteración actual

es 5. La distancia mínima entre los centros iniciales es de 16,000.

Tesis de Maestría


Conglomerados de Interiores2




/PRINT INITIAL.


Notas



S\Interiores2\Interiores2.sav


Peso <ninguno>






/MISSING=LISTWISE








clasificación


Conglomerado

1 2 3 4

PromSize 16,0000 5,333

3

,0000 10,6667


Conglomerado

1 2 3 4

PromSize 14,5689 6,2050 ,0000 10,1606



2 672,000

3 325,000

4 1291,000

Válidos 2750,000

Perdidos ,000


Iteració

n


1 2 3 4

1 ,761 ,825 ,000 ,288

2 ,325 ,096 ,000 ,068 3 ,175 ,003 ,000 ,061

4 ,088 ,009 ,000 ,037

5 ,034 ,009 ,000 ,017 6 ,005 ,015 ,000 ,009

7 ,038 ,006 ,000 ,017 8 ,005 ,009 ,000 ,006

9 ,000 ,006 ,000 ,003

10 ,000 ,000 ,000 ,000

a. Se ha logrado la convergencia debido a que los

centros de los conglomerados no presentan ningún cambio o éste es pequeño. El cambio máximo de

coordenadas absolutas para cualquier centro es de

,000. La iteración actual es 10. La distancia mínima entre los centros iniciales es de 5,333.

Tesis de Maestría


Resultado de conglomerado de conglomerados

QUICK CLUSTER CvNoHarris CvPromRtotal

/MISSING=LISTWISE /CRITERIA=CLUSTER(2) MXITER(10) CONVERGE(0)




Notas

Resultados creados 24-ago-2011 22:37:48 Comentarios

Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTE

RS\Cluster_Clusters1.sav Conjunto de datos activo Conjunto_de_datos1

Filtro <ninguno>

Peso <ninguno> Segmentar archivo <ninguno>

Núm. de filas del archivo de trabajo 24

Tratamiento de los datos perdidos Definición de perdidos Los valores definidos como perdidos por el usuario son considerados como perdidos.

Casos utilizados Los estadísticos se basan en los casos sin valores

perdidos para las variables de aglomeración utilizadas.

Sintaxis QUICK CLUSTER CvNoHarris CvPromRtotal

/MISSING=LISTWISE /CRITERIA=CLUSTER(2) MXITER(10)

CONVERGE(0)


/PRINT INITIAL.

Recursos Tiempo de procesador 00 00:00:00,016

Tiempo transcurrido 00 00:00:00,032

Espacio de trabajo necesario 376 bytes Variables creadas o modificadas QCL_1 Número inicial de casos

QCL_2 Distancia del caso desde su centro inicial de clasificación


Conglomerado

1 2

CvNoHarris ,079131 ,793416

CvPromRtotal ,069708 ,686484


Conglomerado

1 2

CvNoHarris ,200258 ,675605




2 9,000

Válidos 24,000

Perdidos ,000


Iteración


conglomerados

1 2

1 ,218 ,364

2 ,018 ,028

3 ,018 ,028 4 ,000 ,000

a. Se ha logrado la convergencia debido a que los centros de los conglomerados no presentan

ningún cambio o éste es pequeño. El cambio

máximo de coordenadas absolutas para

cualquier centro es de ,000. La iteración

actual es 4. La distancia mínima entre los

centros iniciales es de ,944.

Tesis de Maestría


Resultado de conglomerado de entornos

QUICK CLUSTER CvNoHarris CvPromSize CvNoMSER CvPromRtotal CvNoStar

/MISSING=LISTWISE



/PRINT INITIAL.


Notas

Resultados creados 19-ago-2011 20:14:29 Comentarios

Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTERS\Entornos_Clusters1.sav


Filtro <ninguno> Peso <ninguno>

Segmentar archivo <ninguno>

Núm. de filas del archivo de trabajo 12 Tratamiento de los datos perdidos Definición de perdidos Los valores definidos como perdidos por el usuario

son considerados como perdidos.

Casos utilizados Los estadísticos se basan en los casos sin valores perdidos para las variables de aglomeración utilizadas.

Sintaxis QUICK CLUSTER CvNoHarris CvPromSize

CvNoMSER CvPromRtotal CvNoStar /MISSING=LISTWISE

/CRITERIA=CLUSTER(2) MXITER(10)

CONVERGE(0) /METHOD=KMEANS(NOUPDATE)


/PRINT INITIAL.

Recursos Tiempo de procesador 00 00:00:00,031

Tiempo transcurrido 00 00:00:00,034 Espacio de trabajo necesario 800 bytes



clasificación


Conglomerado

1 2

CvNoHarris ,11619 1,56386

CvPromSize ,11185 ,63051 CvNoMSER ,14210 ,57288


CvNoStar ,33042 1,19979


Conglomerado

1 2

CvNoHarris ,23493 1,11546 CvPromSize ,20608 ,56240

CvNoMSER ,25848 ,46638

CvPromRtotal ,24598 ,27444 CvNoStar ,72371 1,45001



2 2,000

Válidos 12,000 Perdidos ,000


Iteración


conglomerados

1 2

1 ,440 ,530 2 ,000 ,000

a. Se ha logrado la convergencia debido a que los centros de los conglomerados no presentan ningún

cambio o éste es pequeño. El cambio máximo de

coordenadas absolutas para cualquier centro es de ,000. La iteración actual es 2. La distancia mínima

entre los centros iniciales es de 1,822.

Tesis de Maestría


Anexo C. Tablas de resultados de los experimentos

En las tablas C.1, C.7, C.13, C.19, C.25, C.31, C.37, respectivamente para cada uno de los repositorios, se muestra el

número de características destacadas detectadas para cada una de las imágenes de la muestra.

En las tablas C.2, C.3, C.4, C.8, C.9, C.10, C.14, C.15, C.16, C.20, C.21, C.22, C.26, C.27, C.28, C.32, C.33, C.34, C.38,

C.39 y C.40 se muestran el número de correspondencias obtenidas después de la desambiguación y la precisión que se

obtuvo para cada par de imágenes de la muestra. La precisión que es mayor o igual a 0.6 y menor que 0.7 aparece en color

morado y la precisión que es mayor o igual que 0.7 aparece en color rojo.

En las tablas C.5, C.6, C.11, C.12, C.17, C.18, C.23, C.24, C.29, C.30, C.35, C.36, C.41 y C.42 se muestra el tiempo de

ejecución para cada uno de los doce algoritmos en la muestra analizada.

Repositorio AQUA

Tabla C.1. Número de características detectadas en las imágenes muestra del repositorio AQUA.

No. Par de Imágenes Conglomerado MSER Star Harris

1 im10

im11

3

3

479

450

303

294

500

500

2 im74 im75

3 3

394 349

326 283

500 500

3 im360

im361

1

1

485

470

321

333

500

500

4 im620

im621

2

2

848

804

260

298

500

500

5 im730

im731

1

1

452

443

403

360

500

500

6 im873

im874

4

4

3

6

0

0

500

500

7 im896 im897

4 4

0 0

0 0

500 500

8 im930

im931

2

2

11

12

7

12

500

500

9 im975 im976

1 1

15 14

12 17

500 500

Tabla C.2. Precisión de los algoritmos 1- 4 en las imágenes muestra del repositorio AQUA.

No. Par de

Imágenes

NoCorr StarSAD NoCorr StarVNC NoCorr StarTex NoCorr StarCol

1 im10 im11

105 0.448 104 0.50 49 0.857 108 0.440

2 im74

im75

134 0.358 146 0.486 52 0.788 140 0.47

3 im360

im361

89 0.584 84 0.548 45 0.5333 88 0.5

4 im620

im621

100 0.55 85 0.51 51 0.82 101 0.55

5 im730

im731

153 0 131 0 25 0 149 0

6 im873

im874

NA NA NA NA NA NA NA NA

7 im896 im897


8 im930

im931

0 0 0 0 0 0 0 0

9 im975 im976

4 0.5 4 0.5 4 0.5 5 0.6


Tesis de Maestría


No. Par de

Imágenes

NoCorr MserSAD NoCorr MserVNC NoCorr MserTex NoCorr MserCol

1 im10 im11

115 0.582 123 0.512 85 0.765 128 0.547

2 im74

im75

125 0.536 139 0.489 99 0.667 135 0.467

3 im360

im361

97 0.65 101 0.535 70 0.614 99 0.74

4 im620 im621

127 0.62 122 0.46 81 0.62 128 0.53

5 im730

im731

122 0 106 0.0283 81 0 119 0

6 im873

im874

0 0 0 0 0 0 0 0

7 im896 im897


8 im930

im931

0 0 0 0 0 0 0 0

9 im975 im976

5 1 5 1 5 1 6 1


No. Par de

Imágenes

NoCorr HarrisSAD NoCorr HarrisVNC NoCorr HarrisTex NoCorr HarrisCol

1 im10

im11 177 0.197 150 0.03 84 0.059 189 0.158

2 im74 im75

169 0.23 156 0.33 86 0.31 175 0.24

3 im360

im361

154 0.38 104 0.34 69 0.39 160 0.36

4 im620

im621

166 0.34 100 0.32 65 0.5 182 0.37

5 im730 im731

144 0 125 0 73 0 157 0

6 im873

im874

82 0.08 35 0.14 18 0.05 99 0.22

7 im896

im897

15 0.26 15 0.13 13 0.23 14 0.23

8 im930

im931

50 0 51 0 36 0 48 0

9 im975

im976

69 0.043 60 0.38 34 0.41 79 0.27

Tabla C.5. Tiempo, en segundos, de los algoritmos 1-6 del repositorio AQUA.

No. Par de

Imágenes

StarSAD StarVNC StarTex StarCol MserSAD MserVNC

1 im10

im11

0.304 0.364 11.905 0.267 0.5994 0.6986

2 im74 im75

0.405 0.560 30.99 0.543 0.554 0.650

3 im360

im361

0.518 0.462 10.0591 0.325 0.764 0.874

4 im620

im621

0.323 0.367 8.09 0.238 0.692 0.840

5 im730

im731

0.916 0.933 41.00 0.766 0.399 0.797

6 im873

im874

NA NA NA NA 0 0

7 im896 im897

NA NA NA NA NA NA

8 im930

im931

NA NA NA NA NA NA

9 im975 0.368 0.527 0.539 0.235 0.494 0.503

Tesis de Maestría


im976

Tabla C.6. Tiempo, en segundos, de los algoritmos 7-12 del repositorio AQUA.

No. Par de Imágenes MserTex MserCol HarrisSAD HarrisVNC HarrisTex HarrisCol

1 im10 im11

19.758 0.584 0.280 0.555 46.716 0.413

2 im74

im75

18.928 0.580 0.277 0.605 61.536 0.461

3 im360 im361

11.803 1.164 0.284 0.715 34.59 0.60

4 im620

im621

22.11 0.73 0.275 0.725 71.7 0.58

5 im730 im731

37.9 0.479 0.261 0.631 59.71 0.474

6 im873

im874

0 0 0.283 0.708 25.249 0.58

7 im896

im897

NA NA 0.271 0.281 0.631 0.167

8 im930 im931

NA NA 0.26 0.617 13.91 0.487

9 im975

im976

0.710 0.532 0.26 0.438 8.36 0.317

Repositorio Exteriores_Urbanos

Tabla C.7. Número de características detectadas en las imágenes muestra del repositorio Exteriores_Urbanos.


1 im20

im21

1

1

154

159

166

170

500

500

2 im240

im241

3

3

114

110

137

130

500

500

3 im452

im453

3

3

126

116

171

183

500

500

4 im499

im500

2

2

111

117

72

67

448

500

5 im570

im571

1

1

123

144

191

202

500

500

6 im1029

im1030

2

2

134

141

156

150

500

500

Tabla C.8. Precisión de los algoritmos 1- 4 en las imágenes muestra del repositorio Exteriores_Urbanos.

No. Par de

Imágenes


1 im20

im21

58 0.29 40 0.025 5 0.2 59 0.20

2 im240

im241

60 0.733 38 0 10 0.4 63 0.46

3 im452

im453

66 0.803 36 0.0833 10 0.8 67 0.582

4 im499

im500

22 0.40 24 0.45 10 0.5 23 0.39

5 im570 im571

70 0.757 35 0.057 11 0.727 70 0.5

6 im1029

im1030

47 0.10 36 0.16 7 0.14 51 0.078

Tesis de Maestría



No. Par de

Imágenes


1 im20

im21

44 0.5 28 0.25 15 0.6 41 0.21

2 im240

im241

41 0.7804 35 0.2 21 0.667 40 0.725

3 im452 im453

42 0.786 29 0.24 19 0.526 39 0.743

4 im499

im500

29 0.44 27 0.44 19 0.68 31 0.45

5 im570

im571

33 0.727 24 0.29 21 0.619 39 0.61

6 im1029 im1030

26 0.26 30 0.4 18 0.66 32 0.18


No. Par de

Imágenes


1 im20 im21

131 0.23 54 0.05 11 0.18 146 0.26

2 im240

im241

162 0.55 67 0.11 31 0.38 154 0.38

3 im452

im453

184 0.78 54 0.01 21 0.19 148 0.35

4 im499 im500

61 0.03 50 0.18 26 0.19 69 0.15

5 im570

im571

158 0.79 58 0.051 19 0.26 128 0.45

6 im1029

im1030

60 0.03 44 0.15 19 0.26 59 0.05

Tabla C.11. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Exteriores_Urbanos.

No. Par de

Imágenes


1 im20

im21

0.043 0.168 23.07 0.209 0.156 0.166

2 im240 im241

0.049 0.171 22.467 0.149 0.107 0.149

3 im452

im453

0.049 0.140 14.52 0.117 0.111 0.155

4 im499 im500

0.038 0.053 3.22311 0.035 0.149 0.137

5 im570

im571

0.0501 0.175 16.37 0.148 0.121 0.170

6 im1029

im1030

0.040 0.144 11.923 0.109 0.10 0.140

Tabla C.12. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Exteriores_Urbanos.

No. Par de Imágenes MserTex MserCol HarrisSAD HarrisVNC HarrisTex HarrisCol

1 im20

im21

16.2 0.186 0.105 0.96 167.54 0.96

2 im240

im241

9.199 0.130 0.204 1.016 112.507 0.954

3 im452

im453

8.176 0.132 0.112 0.814 123.82 0.778

4 im499

im500

4.71 0.124 0.068 0.287 30.12 0.251

Tesis de Maestría


5 im570

im571

5.91 0.169 0.099 0.752 77.7 0.705

6 im1029

im1030

6.57 0.118 0.079 0.385 46.045 0.363

Repositorio Exteriores_Naturales1

Tabla C.13. Número de características detectadas en las imágenes muestra del repositorio Exteriores_Naturales1.


1 im120

im121

1

1

742

682

1192

1134

500

500

2 im344 im345

2 2

894 898

1572 1508

500 500

3 im406

im407

2

2

1311

1309

1975

1957

500

500

4 im710 im711

1 1

884 858

1374 1419

500 500

Tabla C.14. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio Exteriores_Naturales1.

No. Par de

Imágenes


1 im120

im121

377 0.11 230 0.16 22 0.4 455 0.10

2 im344

im345

782 0.852 366 0.0382 9 0.444 683 0.314

3 im406 im407

622 0.40 394 0.09 6 0.5 740 0.18

4 im710

im711

459 0.067 236 0.1483 13 0.615 556 0.125


No. Par de

Imágenes


1 im120

im121

175 0.24 169 0.24 78 0.37 197 0.23

2 im344 im345

320 0.84 221 0.063 107 0.486 311 0.472

3 im406

im407

321 0.6 290 0.11 108 0.41 361 0.37

4 im710

im711

203 0.275 207 0.29 86 0.453 253 0.363


No. Par de

Imágenes


1 im120

im121

135 0.24 125 0.21 63 0.26 151 0.24

2 im344 im345

184 0.80 144 0.07 77 0.27 185 0.45

3 im406

im407

140 0.6 126 0.26 80 0.25 150 0.37

4 im710 im711

154 0.29 139 0.27 62 0.29 196 0.19

Tesis de Maestría


Tabla C.17. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Exteriores_Naturales1.

No. Par de

Imágenes


1 im120

im121

0.258 1.50 274.01 1.34 0.401 0.79

2 im344

im345

0.428 2.726 769.59 2.74 0.656 1.484

3 im406 im407

0.459 2.49 618.54 2.340 0.606 1.221

4 im710

im711

0.388 2.249 525.83 2.213 0.735 1.318


No. Par de

Imágenes

MserTex MserCol HarrisSAD HarrisVNC HarrisTex HarrisCol

1 im120

im121

74.77 0.656 0.146 0.423 68.84 0.35

2 im344

im345

177.78 1.112 0.415 0.733 87.36 0.384

3 im406

im407

181.91 1.09 0.271 0.61 62.92 0.34

4 im710 im711

145.77 1.153 0.156 0.547 96.17 0.454




1 im138 im139

2 2

216 208

177 147

500 500

2 im331

im332

2

2

176

191

144

146

500

500

3 im450

im451

1

1

181

195

150

152

500

500

4 im766

im767

1

1

162

163

151

156

500

500


No. Par de

Imágenes


1 im138

im139

75 0.89 40 0.05 8 0.62 71 0.45

2 im331

im332

52 0.712 31 0.129 5 0.8 54 0.481

3 im450 im451

42 0.30 30 0.13 10 0.7 68 0.30

4 im766

im767

45 0.088 36 0.11 7 0.428 60 0.216


No. Par de

Imágenes


1 im138

im139

55 0.90 42 0.02 26 0.26 54 0.5

2 im331

im332

44 0.75 43 0.186 29 0.344 55 0.509

3 im450 im451

44 0.52 42 0.14 28 0.35 54 0.38

4 im766

im767

35 0.25 35 0.22 20 0.3 40 0.35

Tesis de Maestría



No. Par de

Imágenes


1 im138

im139

170 0.93 69 0 30 0.133 141 0.37

2 im331

im332

118 0.63 63 0.09 30 0.13 138 0.38

3 im450 im451

105 0.35 56 0.125 27 0.11 140 0.25

4 im766

im767

107 0.03 43 0.02 22 0 158 0.13


No. Par de

Imágenes


1 im138

im139

0.031 0.098 20.48 0.085 0.110 0.174

2 im331 im332

0.037 0.128 28.32 0.106 0.135 0.209

3 im450

im451

0.034 0.149 30.33 0.129 0.098 0.168

4 im766 im767

0.044 0.199 36.58 0.201 0.126 0.314


No. Par de

Imágenes


1 im138 im139

17.81 0.161 0.085 0.595 134.091 0.571

2 im331

im332

23.60 0.197 0.081 0.595 167.45 0.580

3 im450 im451

21.36 0.153 0.088 0.723 189.92 0.711

4 im766

im767

17.92 0.185 0.116 0.90 199.11 0.869




1 im120

im121

2

2

124

125

82

91

500

500

2 im323 im324

1 1

210 205

167 159

500 500

3 im480

im481

1

1

132

124

77

74

500

500

4 im720 im721

2 2

149 152

93 94

500 500


No. Par de

Imágenes


1 im120 im121

36 0.88 24 0.08 4 0.75 29 0.37

2 im323

im324

49 0.571 39 0.0256 6 0.33 65 0.45

3 im480

im481

25 0.88 25 0 3 0.66 27 0.29

Tesis de Maestría


4 im720

im721

37 0.162 36 0.30 6 0.67 43 0.20


No. Par de

Imágenes


1 im120

im121

35 0.6 32 0.062 16 0.18 33 0.42

2 im323 im324

49 0.591 43 0.162 19 0.36 57 0.526

3 im480

im481

22 0.59 24 0.2 18 0.33 31 0.38

4 im720 im721

38 0.23 45 0.2 26 0.34 40 0.12


No. Par de

Imágenes


1 im120

im121

114 0.83 50 0.08 19 0.157 119 0.27

2 im323

im324

61 0.56 40 0.2 21 0.28 72 0.4

3 im480

im481

85 0.62 58 0.17 28 0.17 104 0.41

4 im720 im721

120 0.1 88 0.18 28 0.07 157 0.14


No. Par de

Imágenes


1 im120 im121

0.049 0.110 18.83 0.104 0.085 0.129

2 im323

im324

0.039 0.175 42.86 0.154 0.130 0.227

3 im480

im481

0.046 0.077 11.61 0.057 0.085 0.121

4 im720

im721

0.038 0.101 21.34 0.083 0.115 0.174


No. Par de

Imágenes


1 im120 im121

12.40 0.112 0.124 1.207 289.788 1.291

2 im323

im324

32.21 0.219 0.081 0.564 150.19 0.571

3 im480 im481

8.73 0.101 0.123 0.473 96.33 0.451

4 im720

im721

20.80 0.155 0.150 0.761 206.62 0.704

Repositorio Interiores1

Tabla C.31. Número de características detectadas en las imágenes muestra del repositorio Interiores1.


1 im84

im85

1

1

39

36

23

20

251

231

2 im259

im260

1

1

40

37

19

18

230

230

3 im550

im551

2

2

1

1

0

0

500

500

Tesis de Maestría


4 im637

im638

2

2

20

22

10

10

220

188


No. Par de

Imágenes


1 im84

im85

13 0.38 10 0.3 6 0.833 12 0.58

2 im259 im260

12 0.83 11 0.27 7 0.85 13 0.69

3 im550

im551


4 im637 im638

6 1 6 0.33 3 0.33 7 0.71


No. Par de

Imágenes


1 im84 im85

13 0.38 9 0.55 7 0.57 18 0.5

2 im259

im260

14 0.78 11 0.09 7 0.85 13 0.69

3 im550 im551

1 1 1 1 1 1 1 1

4 im637

im638

13 1 8 0.37 7 0.71 12 1


No. Par de

Imágenes

NoCorr HarrisSAD NoCorr HarrisVN

C

NoCorr HarrisTex NoCorr HarrisCol

1 im84 im85

81 0.13 27 0.25 15 0.26 86 0.15

2 im259

im260

71 0.77 20 0.1 17 0.17 50 0.4

3 im550

im551

140 0.20 58 0.05 25 0.04 150 0.13

4 im637

im638

101 0.62 32 0.06 16 0.06 89 0.25

Tabla C.35. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Interiores1.

No. Par de

Imágenes


1 im84

im85

0.028 0.038 2.05 0.022 0.060 0.082

2 im259 im260

0.036 0.042 0.505 0.018 0.063 0.089

3 im550

im551

NA NA NA NA 0.050 0.049

4 im637 im638

0.022 0.025 0.314 0.011 0.056 0.065


No. Par de

Imágenes


1 im84

im85

2.15 0.062 0.060 0.492 48.0 0.44

2 im259 im260

0.929 0.059 0.119 0.216 13.09 0.187

3 im550

im551

0.070 0.033 0.120 0.793 38.25 0.763

4 im637

im638

0.790 0.049 0.063 0.367 35.94 0.331

Tesis de Maestría


Repositorio Interiores2

Tabla C.37. Número de características detectadas en las imágenes muestra del repositorio Interiores2.


1 im197

im198

2

2

46

46

37

35

455

398

2 im270 im271

2 2

45 54

28 39

500 500

3 im330

im331

4

4

35

26

31

18

500

500

4 im880 im881

4 4

189 163

81 74

500 500

5 im925

im926

1

1

56

55

20

22

500

500

6 im1565 im1566

3 3

15 14

4 6

500 500

7 im1613

im1614

1

1

50

47

56

61

361

412

8 im1980 im1981

3 3

20 22

11 10

500 500


No. Par de

Imágenes


1 im197 im198

19 0.89 19 0.42 15 0.73 18 0.72

2 im270

im271

15 0.93 13 0.69 11 0.81 12 0.83

3 im330

im331

12 0.66 11 0.54 9 0.77 11 0.54

4 im880 im881

28 0.75 24 0.5 14 0.85 28 0.53

5 im925

im926

12 0.58 11 0.81 9 1 13 0.84

6 im1565 im1566

0 NA 0 NA 0 NA 0 NA

7 im1613

im1614

28 0.64 22 0.63 17 0.7 23 0.6

8 im1980 im1981

2 1 2 1 2 1 2 1


No. Par de

Imágenes


1 im197

im198

23 0.913 20 0.6 18 0.88 19 0.74

2 im270 im271

14 0.78 8 0.25 8 0.75 16 0.37

3 im330

im331

10 0.8 10 0.5 9 0.77 12 0.75

4 im880 im881

43 0.72 39 0.56 27 0.59 33 0.6

5 im925

im926

17 0.64 15 0.6 15 0.8 19 0.68

6 im1565 im1566

2 0.5 3 0.66 2 1 2 0.5

7 im1613

im1614

15 0.86 15 0.73 13 1 14 0.85

8 im1980 im1981

4 1 4 1 4 1 4 1


Tesis de Maestría


No. Par de

Imágenes

NoCorr HarrisSA

D

NoCorr HarrisVN

C

NoCorr HarrisTex NoCorr HarrisCol

1 im197

im198

140 0.6 85 0.23 44 0.31 139 0.25

2 im270 im271

172 0.61 88 0.18 48 0.18 156 0.28

3 im330

im331

159 0.35 78 0.21 42 0.45 152 0.23

4 im880 im881

134 0.55 83 0.19 45 0.28 121 0.31

5 im925

im926

128 0.15 78 0.16 42 0.16 119 0.21

6 im1565 im1566

53 0.15 40 0.2 28 0.32 55 0.16

7 im1613

im1614

94 0.27 69 0.24 42 0.28 97 0.28

8 im1980 im1981

93 0.13 77 0.22 46 0.28 106 0.21


No. Par de Imágenes StarSAD StarVNC StarTex StarCol MserSAD MserVNC

1 im197 im198

0.252 0.158 0.952 0.099 0.237 0.447

2 im270

im271

0.185 0.140 0.346 0.074 0.530 0.257

3 im330 im331

0.205 0.151 0.582 0.076 0.345 0.231

4 im880

im881

0.123 0.145 2.048 0.092 0.250 0.277

5 im925

im926

0.129 0.129 0.484 0.071 0.332 0.302

6 im1565

im1566

NA NA NA NA 0.185 0.193

7 im1613

im1614

0.122 0.164 0.711 0.081 0.208 0.201

8 im1980

im1981

0.121 0.120 0.139 0.069 0.169 0.176


No. Par de

Imágenes


1 im197

im198

0.779 0.198 0.220 0.803 33.24 0.750

2 im270 im271

1.141 0.168 0.509 1.181 27.107 0.749

3 im330

im331

0.678 0.140 0.197 1.174 44.73 1.095

4 im880 im881

3.488 0.218 0.217 0.447 32.126 0.366

5 im925

im926

1.075 0.168 0.155 0.542 28.27 0.466

6 im1565 im1566

0.251 0.134 0.198 0.314 11.523 0.244

7 im1613

im1614

0.414 0.158 0.187 0.331 9.026 0.279

8 im1980 im1981

0.267 0.124 0.142 0.386 13.703 0.314

Documents

Tesis de Maestría - CENIDET · 2020. 7. 7. · Tesis de Maestría Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 1 TABLA DE CONTENIDO ÍNDICE DE FIGURAS