View
49
Download
0
Category
Preview:
Citation preview
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 2
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 3
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 4
Í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
Figura 5.5. Primera parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales1................................................................................................... 54
Figura 5.6. Segunda parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales1................................................................................................... 55
Figura 5.7. Tercera parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales1................................................................................................... 55
Figura 5.8. Primera parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales2................................................................................................... 56
Figura 5.9. Segunda parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales2................................................................................................... 56
Figura 5.10. Tercera parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales2................................................................................................... 57
Figura 5.11. Primera parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales3................................................................................................... 58
Figura 5.12. Segunda parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales3................................................................................................... 58
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 5
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.30. Imagen 344 y 345 resultado del buen desempeño del algoritmo StarSAD. .................. 86
Figura 6.31. Imagen 406 y 407 resultado del algoritmo MserSAD. ................................................. 87
Figura 6.32. Imagen 710 y 711 resultado del algoritmo StarTex. ..................................................... 88
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.35. Imagen 450 y 451 resultado del buen desempeño del algoritmo StarTex. ................... 90
Figura 6.36. Imagen 766 y 767 resultado del algoritmo MserCol. ................................................... 90
Figura 6.37. Imagen 120 y 121 resultado del buen desempeño del algoritmo StarSAD. .................. 91
Figura 6.38. Imagen 323 y 324 resultado del algoritmo MserSAD. ................................................. 91
Figura 6.39. Imagen 480 y 481 resultado del buen desempeño del algoritmo StarSAD. .................. 92
Figura 6.40. Imagen 720 y 721 resultado del algoritmo StarTex. ..................................................... 92
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 6
Figura 6.47. Imagen 550 y 551 resultado del buen desempeño del algoritmo MserSAD. ................ 96
Figura 6.48. Imagen 637 y 638 resultado del buen desempeño del algoritmo MserSAD. ................ 97
Figura 6.49. Imagen 197 y 198 resultado del buen desempeño del algoritmo MserSAD. ................ 97
Figura 6.50. Imagen 270 y 271 resultado del buen desempeño del algoritmo StarSAD. .................. 98
Figura 6.51. Imagen 330 y 331 resultado del buen desempeño del algoritmo MserSAD. ................ 98
Figura 6.52. Imagen 880 y 881 resultado del buen desempeño del algoritmo StarTex. ................... 99
Figura 6.53. Imagen 925 y 926 resultado del buen desempeño del algoritmo StarTex. ................... 99
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 7
Í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.5. Algoritmos que mejor se desempeñaron en el repositorio Exteriores_Naturales2. ........ 102
Tabla 6.6. Algoritmos que mejor se desempeñaron en el repositorio Exteriores_Naturales3. ........ 103
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 8
Tabla C.8. Precisión de los algoritmos 1- 4 en las imágenes muestra del repositorio
Exteriores_Urbanos. ...................................................................................................... 135
Tabla C.9. Precisión de los algoritmos 5- 8 en las imágenes muestra del repositorio
Exteriores_Urbanos. ...................................................................................................... 136
Tabla C.10. Precisión de los algoritmos 9- 12 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
Tabla C.13. Número de características detectadas en las imágenes muestra del repositorio
Exteriores_Naturales1................................................................................................. 137
Tabla C.14. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio
Exteriores_Naturales1................................................................................................. 137
Tabla C.15. Precisión de los algoritmos 5-8 en las imágenes muestra del repositorio
Exteriores_Naturales1................................................................................................. 137
Tabla C.16. Precisión de los algoritmos 9-12 en las imágenes muestra del repositorio
Exteriores_Naturales1................................................................................................. 137
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
Tabla C.19. Número de características detectadas en las imágenes muestra del repositorio
Exteriores_Naturales2................................................................................................. 138
Tabla C.20. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio
Exteriores_Naturales2................................................................................................. 138
Tabla C.21. Precisión de los algoritmos 5-8 en las imágenes muestra del repositorio
Exteriores_Naturales2................................................................................................. 138
Tabla C.22. Precisión de los algoritmos 9-12 en las imágenes muestra del repositorio
Exteriores_Naturales2................................................................................................. 139
Tabla C.23. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Exteriores_Naturales2. . 139
Tabla C.24. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Exteriores_Naturales2. 139
Tabla C.25. Número de características detectadas en las imágenes muestra del repositorio
Exteriores_Naturales3................................................................................................. 139
Tabla C.26. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio
Exteriores_Naturales3................................................................................................. 139
Tabla C.27. Precisión de los algoritmos 5-8 en las imágenes muestra del repositorio
Exteriores_Naturales3................................................................................................. 140
Tabla C.28. Precisión de los algoritmos 9-12 en las imágenes muestra del repositorio
Exteriores_Naturales3................................................................................................. 140
Tabla C.29. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Exteriores_Naturales3. . 140
Tabla C.30. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Exteriores_Naturales3. 140
Tabla C.31. Número de características detectadas en las imágenes muestra del repositorio
Interiores1. .................................................................................................................. 140
Tabla C.32. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio Interiores1. 141
Tabla C.33. Precisión de los algoritmos 5-8 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 9
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
Tabla C.37. Número de características detectadas en las imágenes muestra del repositorio
Interiores2. .................................................................................................................. 142
Tabla C.38. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio Interiores2. 142
Tabla C.39. Precisión de los algoritmos 5-8 en las imágenes muestra del repositorio Interiores2. 142
Tabla C.40. Precisión de los algoritmos 9-12 en las imágenes muestra del repositorio Interiores2.
.................................................................................................................................... 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 10
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 11
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 12
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 13
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 14
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 15
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 16
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 17
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.
Emparejamiento de puntos
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 18
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 19
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 20
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 21
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 22
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 23
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 24
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 25
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 26
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 27
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 28
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 29
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 30
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 31
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 32
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 33
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)
Emparejamiento de puntos
Técnicas de similitud de área a
través de métricas de descriptores
de textura o color
(García, 2001)
Emparejamiento de puntos
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 34
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 35
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 36
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 37
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 38
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 39
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 40
Para llevar a cabo el proceso de emparejamiento de la vista 1 a la vista 2 utilizando similitud de área
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.
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 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 41
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 42
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 43
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 44
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.
Para llevar a cabo el proceso de emparejamiento de la vista 1 a la vista 2 utilizando similitud de área
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.
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 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 45
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 46
#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
#img2 : <sin especificar> = 0
#img3 : <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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 47
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 48
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 49
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
4 Exteriores_Naturales2 Terrestre 1862 320×240 Imagen JPG
5 Exteriores_Naturales3 Terrestre 1118 320×240 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
imagen con el detector de características de
Star
3 NoStar Métrica Razón Número de blobs que se detectan en la
imagen con el detector de características de
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 50
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
4 Exteriores_Naturales2 Terrestre 2 PromSize
5 Exteriores_Naturales3 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 51
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.
Figura 5.1. Primera parte de la gráfica de pertenencia a conglomerados del repositorio
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 52
Figura 5.2. Segunda parte de la gráfica de pertenencia a conglomerados del repositorio
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
3 im469-im526 Predomina 3 Coral
4 im527-im579 Predomina 1 Coral
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.
Conglomerado Número de casos Centro final
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 53
La gráfica siguiente dividida en dos partes, figura 5.3 y figura 5.4, muestra la pertenencia de cada
imagen a su conglomerado correspondiente.
Figura 5.3. Primera parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Urbanos.
Figura 5.4. Segunda parte de la gráfica de pertenencia a conglomerados del repositorio
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
Imágenes Conglomerado 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 54
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
respectivamente y algunas de sus características se muestran en la tabla 5.8.
Tabla 5.8. Características de conglomerados del repositorio Exteriores_Naturales1.
Conglomerado Número de casos Centro final
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.
Figura 5.5. Primera parte de la gráfica de pertenencia a conglomerados del repositorio
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 55
Figura 5.6. Segunda parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales1.
Figura 5.7. Tercera parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales1.
En la tabla 5.9 se describen algunas secuencias de fotogramas del repositorio
Exteriores_Naturales1.
Tabla 5.9. Identificación de algunas escenas de Exteriores_Naturales1.
No.
Escena
Imágenes Conglomerado 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 56
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
respectivamente y algunas de sus características se muestran en la tabla 5.10.
Tabla 5.10. Características de conglomerados del repositorio Exteriores_Naturales2.
Conglomerado Número de casos Centro final
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.
Figura 5.8. Primera parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales2.
Figura 5.9. Segunda parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales2.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 57
Figura 5.10. Tercera parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales2.
En la tabla 5.11 se describen algunas secuencias de fotogramas del repositorio
Exteriores_Naturales2.
Tabla 5.11. Identificación de algunas escenas de Exteriores_Naturales2.
No.
Escena
Imágenes Conglomerado 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
8 im1547-im1677 De todos (1 y 2) Alternan escenas con pasto, follaje y
follaje con árbol
9 im1678-im1753 Claramente 2 Follaje y un árbol a lo lejos
10 im1754-im1861 De todos (1 y 2) Alternan escenas con pasto, follaje y
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
respectivamente y algunas de sus características se muestran en la tabla 5.12.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 58
Tabla 5.12. Características de conglomerados del repositorio Exteriores_Naturales3.
Conglomerado Número de casos Centro final
1 413 7.2495
2 704 5.6244
La gráfica siguiente dividida en dos partes, figura 5.11 y figura 5.12, muestra la pertenencia de cada
imagen a su conglomerado correspondiente.
Figura 5.11. Primera parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales3.
Figura 5.12. Segunda parte de la gráfica de pertenencia a conglomerados del repositorio
Exteriores_Naturales3.
En la tabla 5.13 se describen algunas secuencias de fotogramas del repositorio
Exteriores_Naturales3.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 59
Tabla 5.13. Identificación de algunas escenas de Exteriores_Naturales3.
No.
Escena
Imágenes Conglomerado 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
5 im402-im450 De ambos (1 y 2) Escenas variadas: arbustos y tronco de
árbol y arbustos solos
6 im451-im488 Claramente 1 Arbustos y trocos de árbol al fondo con
cambio de iluminación
7 im489-im625 De ambos (1 y 2) Escenas variadas: arbustos y tronco de
árbol y arbustos solos
8 im626-im737 Predomina 2
9 im738-im773 De ambos (1 y 2) Escenas variadas: arbustos y tronco de
árbol y arbustos solos
10 im774-im921 Predomina 2 Árboles con demasiada iluminación
11 im922-im967 De ambos (1 y 2) Escenas variadas: arbustos y tronco de
árbol y arbustos solos
12 im968-im1007 Claramente 2 Arbustos iluminados
13 im1008-im1040 Claramente 1 Troncos de árboles con arbustos
14 im1041-im1081 De ambos (1 y 2) Escenas variadas: arbustos y tronco de
árbol y arbustos solos
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.
Conglomerado Número de casos Centro final
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 60
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
Imágenes Conglomerado 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
respectivamente y algunas de sus características se muestran en la tabla 5.16.
Tabla 5.16. Características de conglomerados del repositorio Interiores2.
Conglomerado Número de casos Centro final
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 61
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 62
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
Imágenes Conglomerado 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 63
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
Texturizadas2 Texturizada 25 1024×1024 Imagen JPG
Texturizadas3 Texturizada 10 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 64
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 65
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
Exteriores_Naturales2 4 1
Exteriores_Naturales3 4 1
Texturizadas1 0 1
Texturizadas2 0 1
Texturizadas3 0 1
Textu 0 1
Estruct 0 1
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 66
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 67
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 68
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.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 69
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 70
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 71
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 72
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.
Figura 6.7. Imagen 74 y 75 resultado del algoritmo StarTex (buen desempeño).
La figura 6.8 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el noroeste.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 73
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.
Figura 6.9. Imagen 620 y 621 resultado del algoritmo StarTex (buen desempeño).
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 74
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 75
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 76
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 77
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 78
Figura 6.17. Precisión del repositorio Exteriores_Urbanos.
En la figura 6.18 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 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 79
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 80
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 81
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 82
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).
Del repositorio Exteriores_Naturales2: (im138,im139), (im331,im332), (im450,im451),
(im766,im767).
Del repositorio Exteriores_Naturales3: (im120,im121), (im323,im324), (im480,im481),
(im720,im721).
En la figura 6.25 se observa que, para esta muestra, la mayor cantidad de características las detecta
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 83
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 84
En la figura 6.28 se tiene 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 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
correspondencia no es buena.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 85
Figura 6.29. Imagen 120 y 121 resultado del algoritmo StarTex.
La figura 6.30 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el
noroeste.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 86
Figura 6.30. Imagen 344 y 345 resultado del buen desempeño del algoritmo StarSAD.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 87
Figura 6.31. Imagen 406 y 407 resultado del algoritmo MserSAD.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 88
Figura 6.32. Imagen 710 y 711 resultado del algoritmo StarTex.
o Repositorio Exteriores_Naturales2
En las figuras 6.33 – 6.36 se muestran las imágenes muestra del repositorio Exteriores_Naturales2,
con los algoritmos en donde se obtuvo la mejor precisión.
La figura 6.33 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el sur.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 89
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 90
Figura 6.35. Imagen 450 y 451 resultado del buen desempeño del algoritmo StarTex.
En la figura 6.36 las colas de las flechas voltean para todos lados, por lo tanto se deduce que la
correspondencia no es buena.
Figura 6.36. Imagen 766 y 767 resultado del algoritmo MserCol.
o Repositorio Exteriores_Naturales3
En las figuras 6.37 – 6.40 se muestran las imágenes muestra del repositorio Exteriores_Naturales3,
con los algoritmos en donde se obtuvo la mejor precisión.
La figura 6.37 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el norte.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 91
Figura 6.37. Imagen 120 y 121 resultado del buen desempeño del algoritmo StarSAD.
En la figura 6.38 las colas de las flechas voltean para todos lados, por lo tanto se deduce que la
correspondencia no es buena.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 92
Figura 6.39. Imagen 480 y 481 resultado del buen desempeño del algoritmo StarSAD.
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.
Figura 6.40. Imagen 720 y 721 resultado del algoritmo StarTex.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 93
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).
En la figura 6.41 se observa que, para esta muestra, la mayor cantidad de características las detecta
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 94
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.
En la figura 6.44 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 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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 95
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.
La figura 6.45 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el este.
Figura 6.45. Imagen 84 y 85 resultado del buen desempeño del algoritmo StarTex.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 96
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.
Figura 6.46. Imagen 259 y 260 resultado del buen desempeño del algoritmo MserTex.
La figura 6.47 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el sureste.
Figura 6.47. Imagen 550 y 551 resultado del buen desempeño del algoritmo MserSAD.
La figura 6.48 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el sureste.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 97
Figura 6.48. Imagen 637 y 638 resultado del buen desempeño del algoritmo MserSAD.
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.
Figura 6.49. Imagen 197 y 198 resultado del buen desempeño del algoritmo MserSAD.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 98
La figura 6.50 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el
noroeste.
Figura 6.50. Imagen 270 y 271 resultado del buen desempeño del algoritmo StarSAD.
La figura 6.51 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el noreste.
Figura 6.51. Imagen 330 y 331 resultado del buen desempeño del algoritmo MserSAD.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 99
La figura 6.52 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el noreste.
Figura 6.52. Imagen 880 y 881 resultado del buen desempeño del algoritmo StarTex.
La figura 6.53 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el este.
Figura 6.53. Imagen 925 y 926 resultado del buen desempeño del algoritmo StarTex.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 100
La figura 6.54 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el oeste.
Figura 6.54. Imagen 1565 y 1566 resultado del buen desempeño del algoritmo MserTex.
La figura 6.55 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el
suroeste.
Figura 6.55. Imagen 1613 y 1614 resultado del buen desempeño del algoritmo MserTex.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 101
La figura 6.56 se interpreta que la imagen experimentó un pequeño desplazamiento hacia el
suroeste.
Figura 6.56. Imagen 1980 y 1981 resultado del buen desempeño del algoritmo MserSAD.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 102
7 im896
im897
4 (Estructurada)
4
MSER y Star no detectaron CDs
Harris no funcionó
8 im930
im931
2 (Estructurada)
2
MSER y Star no detectaron CDs
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.
No. Par de Imágenes Conglomerado Algoritmos
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.
No. Par de Imágenes Conglomerado Algoritmos
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)
Tabla 6.5. Algoritmos que mejor se desempeñaron en el repositorio Exteriores_Naturales2.
No. Par de Imágenes Conglomerado Algoritmos
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 103
3 im450
im451
1 (Texturizada)
1
StarTex (0.7)
4 im766
im767
1 (Texturizada)
1
Ninguno
Tabla 6.6. Algoritmos que mejor se desempeñaron en el repositorio Exteriores_Naturales3.
No. Par de Imágenes Conglomerado Algoritmos
1 im120
im121
2 (Texturizada)
2
StarSAD (0.88), StarTex (0.75), MserSAD (0.6) y
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.
No. Par de Imágenes Conglomerado Algoritmos
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.
No. Par de Imágenes Conglomerado Algoritmos
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 104
4 im880
im881
4 (Estructurada)
4
StarSAD (0.75), StarTex (0.85), MserSAD (0.72) y
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 105
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 106
En la figura 6.60 aparece la precisión para los algoritmos que en su fase de detección utilizan el
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.
En la figura 6.61 aparece la precisión para los algoritmos que en su fase de detección utilizan el
algoritmo MSER aplicados en la muestra texturizada.
Figura 6.61. Precisión de los algoritmos con MSER aplicados en la muestra texturizada.
En la figura 6.62 aparece la precisión para los algoritmos que en su fase de detección utilizan el
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 107
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.
En la figura 6.63 aparece la precisión para los algoritmos que en su fase de detección utilizan el
algoritmo Harris aplicados en la muestra texturizada.
Figura 6.63. Precisión de los algoritmos con Harris aplicados en la muestra texturizada.
En la figura 6.64 aparece la precisión para los algoritmos que en su fase de detección utilizan el
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 108
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 109
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 110
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 111
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 112
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 113
(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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 114
(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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 115
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 116
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 117
//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
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 118
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 119
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 120
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 121
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 122
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:
Corresp(M2,m2,img5,img4,eps1,d,ud,d1)
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:
Corresp(M1,m1,img1,img2,eps1,d,ud,d1)
para obtener el arreglo de pares de puntos correspondientes de la vista 1 a la vista 2 y seguidamente se aplica la función:
Corresp(M2,m2,img2,img1,eps1,d,ud,d1)
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 124
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)
/METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE /PRINT INITIAL.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 125
Conglomerados de Exteriores_Urbanos
QUICK CLUSTER PromSize /MISSING=LISTWISE
/CRITERIA=CLUSTER(3) MXITER(10) CONVERGE(0)
/METHOD=KMEANS(NOUPDATE) /SAVE CLUSTER DISTANCE
/PRINT INITIAL.
Análisis de conglomerados de K medias
Notas
Resultados creados 31-jul-2011 17:24:06
Comentarios Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTE
RS\Urbanos\Urbanos.sav
Conjunto de datos activo Conjunto_de_datos4 Filtro <ninguno>
Peso <ninguno>
Segmentar archivo <ninguno> Núm. de filas del archivo de trabajo 1162
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(3) MXITER(10) CONVERGE(0)
/METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE /PRINT INITIAL.
Recursos Tiempo de procesador 00 00:00:00,047 Tiempo transcurrido 00 00:00:00,110
Espacio de trabajo necesario 320 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
PromSize 7,7949 9,7391 5,8625
Centros de los conglomerados finales
Conglomerado
1 2 3
PromSize 7,4295 8,3444 6,7931
Número de casos en cada conglomerado
Conglomerado 1 498,000
2 117,000
3 547,000
Válidos 1162,000
Perdidos ,000
Historial de iteracionesa
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
mínima entre los centros iniciales es de 1,932.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 126
Conglomerados de Exteriores_Naturales1
QUICK CLUSTER PromSize
/MISSING=LISTWISE
/CRITERIA=CLUSTER(2) MXITER(10) CONVERGE(0) /METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE
/PRINT INITIAL.
Análisis de conglomerados de K medias
Notas
Resultados creados 24-ago-2011 13:49:59
Comentarios Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTER
S\Naturales1\Naturales1.sav
Conjunto de datos activo Conjunto_de_datos1
Filtro <ninguno>
Peso <ninguno>
Segmentar archivo <ninguno> Núm. de filas del archivo de trabajo 1560
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(2) MXITER(10) CONVERGE(0)
/METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE /PRINT INITIAL.
Recursos Tiempo de procesador 00 00:00:00,281 Tiempo transcurrido 00 00:00:00,316
Espacio de trabajo necesario 240 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
PromSize 9,7273 5,4607
Centros de los conglomerados finales
Conglomerado
1 2
PromSize 7,3097 6,5202
Número de casos en cada conglomerado
Conglomerado 1 621,000
2 939,000
Válidos 1560,000
Perdidos ,000
Historial de iteracionesa
Iteración
Cambio en los centros de los conglomerados
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
mínima entre los centros iniciales es de 4,267.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 127
Conglomerados de Exteriores_Naturales2
QUICK CLUSTER PromSize
/MISSING=LISTWISE
/CRITERIA=CLUSTER(2) MXITER(10) CONVERGE(0) /METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE
/PRINT INITIAL.
Análisis de conglomerados de K medias
Notas
Resultados creados 31-jul-2011 19:37:01
Comentarios Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTER
S\Naturales2\Naturales2.sav
Conjunto de datos activo Conjunto_de_datos1
Filtro <ninguno>
Peso <ninguno>
Segmentar archivo <ninguno> Núm. de filas del archivo de trabajo 1861
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(2) MXITER(10) CONVERGE(0)
/METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE /PRINT INITIAL.
Recursos Tiempo de procesador 00 00:00:00,172 Tiempo transcurrido 00 00:00:00,242
Espacio de trabajo necesario 240 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
PromSize 10,8114 5,1429
Centros de los conglomerados finales
Conglomerado
1 2
PromSize 7,9142 6,5764
Número de casos en cada conglomerado
Conglomerado 1 631,000
2 1230,000
Válidos 1861,000
Perdidos ,000
Historial de iteracionesa
Iteración
Cambio en los centros de los conglomerados
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
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 ,010. La iteración actual es 10. La distancia
mínima entre los centros iniciales es de 5,669.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 128
Conglomerados de Exteriores_Naturales3
QUICK CLUSTER PromSize
/MISSING=LISTWISE
/CRITERIA=CLUSTER(2) MXITER(10) CONVERGE(0) /METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE
/PRINT INITIAL.
Análisis de conglomerados de K medias
Notas
Resultados creados 31-jul-2011 21:27:05
Comentarios Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTER
S\Naturales3\Naturales3.sav
Conjunto de datos activo Conjunto_de_datos1
Filtro <ninguno>
Peso <ninguno>
Segmentar archivo <ninguno> Núm. de filas del archivo de trabajo 1117
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(2) MXITER(10) CONVERGE(0)
/METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE /PRINT INITIAL.
Recursos Tiempo de procesador 00 00:00:00,078 Tiempo transcurrido 00 00:00:00,077
Espacio de trabajo necesario 240 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
PromSize 13,6000 4,0000
Centros de los conglomerados finales
Conglomerado
1 2
PromSize 7,2495 5,6244
Número de casos en cada conglomerado
Conglomerado 1 413,000
2 704,000
Válidos 1117,000
Perdidos ,000
Historial de iteracionesa
Iteración
Cambio en los centros de los conglomerados
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
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 ,030. La iteración actual es 10. La distancia
mínima entre los centros iniciales es de 9,600.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 129
Conglomerados de Interiores1
QUICK CLUSTER PromSize /MISSING=LISTWISE
/CRITERIA=CLUSTER(2) 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 18:11:19
Comentarios Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTER
S\Interiores1\Interiores1.sav
Conjunto de datos activo Conjunto_de_datos1 Filtro <ninguno>
Peso <ninguno>
Segmentar archivo <ninguno> Núm. de filas del archivo de trabajo 662
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(2) MXITER(10) CONVERGE(0)
/METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE /PRINT INITIAL.
Recursos Tiempo de procesador 00 00:00:00,047 Tiempo transcurrido 00 00:00:00,063
Espacio de trabajo necesario 240 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
PromSize 16,0000 ,0000
Centros de los conglomerados finales
Conglomerado
1 2
PromSize 10,1664 ,1829
Número de casos en cada conglomerado
Conglomerado 1 498,000
2 164,000 Válidos 662,000
Perdidos ,000
Historial de iteracionesa
Iteración
Cambio en los centros de los
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 130
Conglomerados de Interiores2
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 31-jul-2011 15:27:00
Comentarios Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTER
S\Interiores2\Interiores2.sav
Conjunto de datos activo Conjunto_de_datos1 Filtro <ninguno>
Peso <ninguno>
Segmentar archivo <ninguno> Núm. de filas del archivo de trabajo 2750
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)
/METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE /PRINT INITIAL.
Recursos Tiempo de procesador 00 00:00:00,156 Tiempo transcurrido 00 00:00:00,234
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
PromSize 16,0000 5,333
3
,0000 10,6667
Centros de los conglomerados finales
Conglomerado
1 2 3 4
PromSize 14,5689 6,2050 ,0000 10,1606
Número de casos en cada conglomerado
Conglomerado 1 462,000
2 672,000
3 325,000
4 1291,000
Válidos 2750,000
Perdidos ,000
Historial de iteracionesa
Iteració
n
Cambio en los centros de los conglomerados
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 131
Resultado de conglomerado de conglomerados
QUICK CLUSTER CvNoHarris CvPromRtotal
/MISSING=LISTWISE /CRITERIA=CLUSTER(2) MXITER(10) CONVERGE(0)
/METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE /PRINT INITIAL.
Análisis de conglomerados de K medias
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)
/METHOD=KMEANS(NOUPDATE) /SAVE CLUSTER DISTANCE
/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
Centros iniciales de los conglomerados
Conglomerado
1 2
CvNoHarris ,079131 ,793416
CvPromRtotal ,069708 ,686484
Centros de los conglomerados finales
Conglomerado
1 2
CvNoHarris ,200258 ,675605
CvPromRtotal ,213221 ,321606
Número de casos en cada conglomerado
Conglomerado 1 15,000
2 9,000
Válidos 24,000
Perdidos ,000
Historial de iteracionesa
Iteración
Cambio en los centros de los
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 132
Resultado de conglomerado de entornos
QUICK CLUSTER CvNoHarris CvPromSize CvNoMSER CvPromRtotal CvNoStar
/MISSING=LISTWISE
/CRITERIA=CLUSTER(2) MXITER(10) CONVERGE(0) /METHOD=KMEANS(NOUPDATE)
/SAVE CLUSTER DISTANCE
/PRINT INITIAL.
Análisis de conglomerados de K medias
Notas
Resultados creados 19-ago-2011 20:14:29 Comentarios
Entrada Datos C:\Users\Ofelia\Desktop\ENTORNOS\CLUSTERS\Entornos_Clusters1.sav
Conjunto de datos activo Conjunto_de_datos1
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)
/SAVE CLUSTER DISTANCE
/PRINT INITIAL.
Recursos Tiempo de procesador 00 00:00:00,031
Tiempo transcurrido 00 00:00:00,034 Espacio de trabajo necesario 800 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
CvNoHarris ,11619 1,56386
CvPromSize ,11185 ,63051 CvNoMSER ,14210 ,57288
CvPromRtotal ,20055 ,31052
CvNoStar ,33042 1,19979
Centros de los conglomerados finales
Conglomerado
1 2
CvNoHarris ,23493 1,11546 CvPromSize ,20608 ,56240
CvNoMSER ,25848 ,46638
CvPromRtotal ,24598 ,27444 CvNoStar ,72371 1,45001
Número de casos en cada conglomerado
Conglomerado 1 10,000
2 2,000
Válidos 12,000 Perdidos ,000
Historial de iteracionesa
Iteración
Cambio en los centros de los
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 133
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
NA NA NA NA NA NA NA NA
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
Tabla C.3. Precisión de los algoritmos 5- 8 en las imágenes muestra del repositorio AQUA.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 134
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
NA NA NA NA NA NA NA NA
8 im930
im931
0 0 0 0 0 0 0 0
9 im975 im976
5 1 5 1 5 1 6 1
Tabla C.4. Precisión de los algoritmos 9- 12 en las imágenes muestra del repositorio AQUA.
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 135
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.
No. Par de Imágenes Conglomerado MSER Star Harris
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
NoCorr StarSAD NoCorr StarVNC NoCorr StarTex NoCorr StarCol
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 136
Tabla C.9. Precisión de los algoritmos 5- 8 en las imágenes muestra del repositorio Exteriores_Urbanos.
No. Par de
Imágenes
NoCorr MserSAD NoCorr MserVNC NoCorr MserTex NoCorr MserCol
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
Tabla C.10. Precisión de los algoritmos 9- 12 en las imágenes muestra del repositorio Exteriores_Urbanos.
No. Par de
Imágenes
NoCorr HarrisSAD NoCorr HarrisVNC NoCorr HarrisTex NoCorr HarrisCol
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
StarSAD StarVNC StarTex StarCol MserSAD MserVNC
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 137
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.
No. Par de Imágenes Conglomerado MSER Star Harris
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
NoCorr StarSAD NoCorr StarVNC NoCorr StarTex NoCorr StarCol
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
Tabla C.15. Precisión de los algoritmos 5-8 en las imágenes muestra del repositorio Exteriores_Naturales1.
No. Par de
Imágenes
NoCorr MserSAD NoCorr MserVNC NoCorr MserTex NoCorr MserCol
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
Tabla C.16. Precisión de los algoritmos 9-12 en las imágenes muestra del repositorio Exteriores_Naturales1.
No. Par de
Imágenes
NoCorr HarrisSAD NoCorr HarrisVNC NoCorr HarrisTex NoCorr HarrisCol
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 138
Tabla C.17. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Exteriores_Naturales1.
No. Par de
Imágenes
StarSAD StarVNC StarTex StarCol MserSAD MserVNC
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
Tabla C.18. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Exteriores_Naturales1.
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
Repositorio Exteriores_Naturales2
Tabla C.19. Número de características detectadas en las imágenes muestra del repositorio Exteriores_Naturales2.
No. Par de Imágenes Conglomerado MSER Star Harris
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
Tabla C.20. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio Exteriores_Naturales2.
No. Par de
Imágenes
NoCorr StarSAD NoCorr StarVNC NoCorr StarTex NoCorr StarCol
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
Tabla C.21. Precisión de los algoritmos 5-8 en las imágenes muestra del repositorio Exteriores_Naturales2.
No. Par de
Imágenes
NoCorr MserSAD NoCorr MserVNC NoCorr MserTex NoCorr MserCol
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 139
Tabla C.22. Precisión de los algoritmos 9-12 en las imágenes muestra del repositorio Exteriores_Naturales2.
No. Par de
Imágenes
NoCorr HarrisSAD NoCorr HarrisVNC NoCorr HarrisTex NoCorr HarrisCol
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
Tabla C.23. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Exteriores_Naturales2.
No. Par de
Imágenes
StarSAD StarVNC StarTex StarCol MserSAD MserVNC
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
Tabla C.24. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Exteriores_Naturales2.
No. Par de
Imágenes
MserTex MserCol HarrisSAD HarrisVNC HarrisTex HarrisCol
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
Repositorio Exteriores_Naturales3
Tabla C.25. Número de características detectadas en las imágenes muestra del repositorio Exteriores_Naturales3.
No. Par de Imágenes Conglomerado MSER Star Harris
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
Tabla C.26. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio Exteriores_Naturales3.
No. Par de
Imágenes
NoCorr StarSAD NoCorr StarVNC NoCorr StarTex NoCorr StarCol
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 140
4 im720
im721
37 0.162 36 0.30 6 0.67 43 0.20
Tabla C.27. Precisión de los algoritmos 5-8 en las imágenes muestra del repositorio Exteriores_Naturales3.
No. Par de
Imágenes
NoCorr MserSAD NoCorr MserVNC NoCorr MserTex NoCorr MserCol
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
Tabla C.28. Precisión de los algoritmos 9-12 en las imágenes muestra del repositorio Exteriores_Naturales3.
No. Par de
Imágenes
NoCorr HarrisSAD NoCorr HarrisVNC NoCorr HarrisTex NoCorr HarrisCol
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
Tabla C.29. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Exteriores_Naturales3.
No. Par de
Imágenes
StarSAD StarVNC StarTex StarCol MserSAD MserVNC
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
Tabla C.30. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Exteriores_Naturales3.
No. Par de
Imágenes
MserTex MserCol HarrisSAD HarrisVNC HarrisTex HarrisCol
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.
No. Par de Imágenes Conglomerado MSER Star Harris
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 141
4 im637
im638
2
2
20
22
10
10
220
188
Tabla C.32. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio Interiores1.
No. Par de
Imágenes
NoCorr StarSAD NoCorr StarVNC NoCorr StarTex NoCorr StarCol
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
NA NA NA NA NA NA NA NA
4 im637 im638
6 1 6 0.33 3 0.33 7 0.71
Tabla C.33. Precisión de los algoritmos 5-8 en las imágenes muestra del repositorio Interiores1.
No. Par de
Imágenes
NoCorr MserSAD NoCorr MserVNC NoCorr MserTex NoCorr MserCol
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
Tabla C.34. Precisión de los algoritmos 9-12 en las imágenes muestra del repositorio Interiores1.
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
StarSAD StarVNC StarTex StarCol MserSAD MserVNC
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
Tabla C.36. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Interiores1.
No. Par de
Imágenes
MserTex MserCol HarrisSAD HarrisVNC HarrisTex HarrisCol
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
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 142
Repositorio Interiores2
Tabla C.37. Número de características detectadas en las imágenes muestra del repositorio Interiores2.
No. Par de Imágenes Conglomerado MSER Star Harris
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
Tabla C.38. Precisión de los algoritmos 1-4 en las imágenes muestra del repositorio Interiores2.
No. Par de
Imágenes
NoCorr StarSAD NoCorr StarVNC NoCorr StarTex NoCorr StarCol
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
Tabla C.39. Precisión de los algoritmos 5-8 en las imágenes muestra del repositorio Interiores2.
No. Par de
Imágenes
NoCorr MserSAD NoCorr MserVNC NoCorr MserTex NoCorr MserCol
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
Tabla C.40. Precisión de los algoritmos 9-12 en las imágenes muestra del repositorio Interiores2.
Tesis de Maestría
Análisis de Algoritmos de Correspondencia para Visión Estéreo Página 143
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
Tabla C.41. Tiempo, en segundos, de los algoritmos 1-6 del repositorio Interiores2.
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
Tabla C.42. Tiempo, en segundos, de los algoritmos 7-12 del repositorio Interiores2.
No. Par de
Imágenes
MserTex MserCol HarrisSAD HarrisVNC HarrisTex HarrisCol
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
Recommended