Índice de documentos DOCUMENTO I. MEMORIA Parte I. Memoria Parte II. Manual de usuario

pág. 9 a 108 pág. 115 a 119

98 páginas 5 páginas

DOCUMENTO II. PLIEGO DE CONDICIONES 1. Generales y económicas 2. Técnicas y particulares

pág. 3 a 4 5 a 5

2 páginas 1 página

DOCUMENTO III. PRESUPUESTO 1. Coste equipo necesario 2. Coste de mano de obra 3. Presupuesto total

3 a 3 3 a 4 4 a 4

1 página 2 páginas 1 página

Autorizada la entrega del proyecto del alumno:

María Saiz Muñoz

L OS D IRECTORES DEL P ROYECTO

Manuel Alvar Miró

Fdo.: . . . . . . . . . . . . . . . . . . . . . . . .

Fecha: . . . . . . / . . . . . . / . . . . . . . . .

Álvaro Arranz Domingo

Fdo.: . . . . . . . . . . . . . . . . . . . . . . . .

Fecha: . . . . . . / . . . . . . / . . . . . . . . .

Álvaro Sánchez Miralles

Fdo.: . . . . . . . . . . . . . . . . . . . . . . . . Fecha: . . . . . . / . . . . . . / . . . . . . . . . O O V B DEL C OORDINADOR DE P ROYECTOS

Álvaro Sánchez Miralles

Fdo.: . . . . . . . . . . . . . . . . . . . . . . . .

Fecha: . . . . . . / . . . . . . / . . . . . . . . .

UNIVERSIDAD PONTIFICIA COMILLAS ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA (ICAI) INGENIERO INDUSTRIAL

PROYECTO FIN DE CARRERA

RECONSTRUCCIÓN TRIDIMENSIONAL MEDIANTE VISIÓN ESTÉREO Y TÉCNICAS DE OPTIMIZACIÓN

AUTOR: María Saiz Muñoz DIRECTORES: Manuel Alvar Miró Álvaro Arranz Domingo Álvaro Sánchez Miralles MADRID, Junio de 2010

Resumen estudio de la reconstrucción tridimensional de objetos y escenas ha sido y sigue siendo hoy en día un tema ampliamente investigado. La necesidad de crear mecanismos autónomos capaces de evaluar las características de una escena y tomar decisiones a partir del conjunto de información que recogen es cada vez mayor. En este contexto nace el concepto de robot móvil autónomo que no sólo es capaz de detectar obstáculos y evitarlos sino que su habilidad de reconstruir tridimensionalmente la escena le permite interactuar con los distintos objetos que se encuentran en la misma y establecer puntos de referencia para ayudar así al desarrollo de sus funciones. Así mismo, se hace necesario en multitud de disciplinas tales como la medicina o la topología el conocimiento exhaustivo de ciertos elementos tridimensionales a los que no se tiene acceso por simple inspección visual. En el campo de la medicina el proceso de reconstrucción tridimensional es especialmente útil en predicción y el tratamiento de ciertas patologías. Otra aplicación que ha tenido un gran impulso en los últimos años es la renderización de frames intermedios en la captura de imágenes mediante una cámara, que permite reconstruir los frames intermedios que una cámara no es capaz de capturar.

E

L

Los objetivos que persigue esta memoria son fundamentalmente dos, en primer lugar se procederá a la clasificación, evaluación y comparación de métodos de reconstrucción estéreo basados en optimización y en segundo lugar se intentarán aportar nuevas ideas a los algoritmos desarrollados. En el presente proyecto, el estudio de la reconstrucción tridimensional se centrará en la obtención de las imágenes tridimensionales a través de un mecanismo análogo al que se produce en el ojo humano. A partir de dos imágenes en estéreo, se determinarán los dos puntos en cada una de esas imágenes que se corresponden con el mismo punto en la realidad, estos dos puntos se denominan puntos correspondientes. Mediante la diferencia de las coordenadas horizontales de los puntos correspondientes para toda la imagen, se determina el mapa de disparidades, que es inversamente proporcional a la profundidad a la que se encuentra el punto y por lo tanto ofrece une aproximación al mapeo tridimensional de la imagen.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

IV

R ESUMEN

El proceso que se sigue para la determinación del mapa de disparidades es complejo y se puede abordar desde distintos puntos de vista. Los métodos locales, que ya fueron abordados en una memoria anterior, trabajan con regiones dentro de la imagen más pequeñas y suelen establecer puntos de interés que ayudan a identificar el objeto sin necesidad de conocer todo el mapa completo de disparidades. Por otro lado, los métodos globales tratan a la imagen como un conjunto obteniendo el mapa de disparidades denso de la imagen a partir de la optimización de una función objetivo. Se han seleccionado los métodos globales de optimización como caso de estudio ya que ofrecen mapas de disparidad densos mucho más fiables. Además, gracias a los grandes avances en la técnica, se han conseguido desarrollar algoritmos de escaso coste computacional, por lo que el uso de los métodos locales ha sido relegado a un segundo plano. Existe una aplicación desarrollada por los miembros de la Universidad de Middlebury que permite a la comunidad investigadora probar sus algoritmos de manera que los más efectivos, tanto desde el punto de vista del ahorro computacional como del error de cálculo, se publiquen en su ranking de los mejores algoritmos, facilitando así su divulgación y promoviendo un estandar que permita ahorrar tiempo y recursos a todas aquellas personas interesadas en el campo de la visión estéreo. Se comprueba fácilmente gracias al ranking anterior que los primeros puestos apoyan la teoría de que los métodos globales presentan una mejor actuación. Dentro de la resolución de las correspondencias de una imagen por métodos de optimización se presentan distintas etapas. En primer lugar se puede hacer un preprocesado de la imagen que permita mejorar la calidad de la misma y facilite el trabajo al algoritmo de optimización, en general se pueden aplicar tanto filtros que se encarguen del suavizado de la imagen como técnicas especiales de segmentación que permiten dividir la imagen en segmentos u objetos de manera que en etapas posteriores se conozcan perfectamente las características de la imagen. En la implementación de nuestro algoritmo se ha usado como técnica de pre-procesado el método de segmentación Mean-shift con muy buenos resultados. Una vez realizado el pre-procesado, se procede a la elección del método de optimización idóneo en función de los términos de la función objetivo que hayan sido seleccionados. Por un lado, los métodos de optimización se dividen en deterministas y en probabilísticos,dado el alto coste computacional de los primeros, se han seleccionado los segundos como método de optimización. Los métodos probabilísticos se dividen a su vez en

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

V

R ESUMEN

métodos basados en programación dinámica y métodos basados en campos de Markov. Dados los buenos resultados y la fuerte estandarización que presentan los segundos, se ha optado por el uso de est tipo de optimización, en particular, se han implementado los métodos ICM, Belief propagation, TRWS y Graph Cuts. En cuanto a los términos de la función objetivo, en su forma más simple consta de dos términos. El primer término Edata mide la semejanza entre puntos correspondientes, basado principalmente en la diferencia en las intensidades de color de los mismos. El segundo término Esmooth es un término de suavidad que intenta asignar una disparidad similar a los puntos cercanos imponiendo una coherencia en todas las direcciones. Una vez determinado el mapa de disparidades se puede mejorar la calidad del mismo por medio de sistemas de detección de oclusiones, que son aquellos puntos visibles en una sola imagen y que por lo tanto no presentan correspondencia. Ya por último, se puede contar con una etapa de post-procesado mediante filtros o estimación de subpíxeles que permita mejorar la calidad del mapa de disparidades obtenido. Tras la implementación de todas las etapas anteriores, se obtiene un mapa de disparidades que refleja una idea tridimensional de la escena. Entre todos los algoritmos estudiados, el que presenta una mejor actuación tanto en tiempo de ejecución como en píxeles erróneos es el método RANSAC con determinación de oclusiones por OC y aplicación del algoritmo Mean shift. Por otro lado, se ha comprobado que el algoritmo más rápico es el que emplea el método de Birchfield y Tomasi como término data y el que presenta un menor error es el algoritmo RANSAC con detección de oclusiones por LRcheck. En la Figura 1, se observa el mapa de disparidades obtenido para uno de los algoritmos con mejor actuación. En el lado izquierdo se muestra el mapa de disparidades real de la imagen y en el lado derecho el mapa de disparidades obtenido.

Figura 1. Reconstrucción 3D de una escena Como se puede observar, la aplicación de los métodos globales en reconstrucción 3D ofrece unos buenos resultados.A pesar de ello, estos métodos aún no presentan una solución única y cerrada, por lo que parece lógico pensar que esta disciplina tendrá un importante desarrollo en los próximos años.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

VI

Abstract 3D reconstruction of a scene or object from a pair of stereo images has been a widely researched topic over the last decades. The need to create autonomous mechanisms capable of evaluating the scene’s characteristics and making decisions based on the information recovered is becoming more and more important. In this context, a new concept of autonomous mobile robots has raised. These robots are not only able to detect obstacles and avoid them but also they can obtain the 3D reconstruction of the scene. This will permit the robot to interact with all the different objects in the scene and to establish reference points in order to guide himself.

T

HE

Furthermore, an exhaustive knowledge of certain three-dimensional elements that are not accesible with a mere visual inspection is required in a wide range of disciplines such as medicine or topology. Three-dimensional reconstruction is clearly much more developed in Medicine than any other discipline because of the importance of these tools in the prediction and treatment of certain patologies. On the other hand, disciplines such as topology have experienced enormous advances thanks to 3D reconstruction, nowadays much more accurate 3D maps of the earth can be obtained via aerial photographs and a great deal of caves have been discovered due to the success of this technologies. Another discipline that has experienced a major boost in the last years is the intermediate rendering , that allows to obtain a reconstruction of the intermediate frames which cannot be captured by a camera by considering the three dimensional structure of the captured frames. The main objectives in this project are to clasify, evaluate and compare several 3D reconstruction methods based in stereo vision and optimization techniques. Furthermore, new contribution to these methods will be suggested. In this project, the 3D reconstruction study will focus on obtaining the threedimensional images through a mechanism similar to the human eye. From one stereo pair of images, the points in both images corresponding with a single point in reality will

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

VII

A BSTRACT

be determined. This process is called correspondence and offers as a result the disparity maps, i.e., the difference between the horizontal coordinates of the corresponding pixels. The process followed to determine the disparity maps is complex and can be approached in a number of ways. Local methods, that have been discussed in a previous paper, work with smaller regions within the image and usually try to determine certain points of interest that help to identify the object withouth solving the whole disparity map. On the contrary, global methods treat the image as a whole obtaining the disparity map within the image from the optimization of an objective function. Distinct global methods have been selected as a case of study as they offer high quality dense disparity maps much more reliable than the disperse disparity maps obtained by the local methods. In addition, due to the important advances in computer science, many algorithms involving global methods have been developed with low computational costs,as a result, local methods have been pushed into the background. Middlebury University has created a testbed that classifies all the algorithms introduced by the stereo vision community in terms of effectiveness both in computational cost and error percentage of the disparity maps. This tool helps the researchers to save time and ressources and gives a general idea of the situation in computer stereo vision. It can be checked in the testbed that global methods perform better than local ones. Among the correspondence methods, many steps should be taken. First of all, it becomes essencial for certain algorithms to process a high quality input image in order to simplify the task of the optimization methods. This can be done by the use of a pre-processing step, the pre-processing step may include an application of a filter all over the image or the use of a segmentation method, which will divide the image into objects or segments.In our resolution of the problem, we will use a segmentation method called Mean-Shift segmentation. Once the pre-processing has been applied, it is followed by the election of the ideal optimization method depending on the terms of the objective function that has been selected. On the one hand, optimization methods are divided into deterministic and probabilistic, taking into account the high computational cost of the first method, probabilistic approaches have been chosen as the optimization method. Probabilistic methods are divided as well into two, dynamic programming based methods and Markov Random Fields based methods. As it is generally held that MRF perform better and they have a high standarization, we will use these methods from now on. In particular, we will solve our optimization problem using ICM, Belief Propagation, TRWS and

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

VIII

A BSTRACT

Graph Cuts. On the other hand, the terms of the objective function are as well highly standarized and they are usually two. The first term Edata measures the simmilarity between corresponding pixels while the second term Esmooth tries to ascribe similar disparities to pixels in the same neighbourhood. Once the disparity map has been determined, its quality can be improved by taking into consideration certain methods for handling occlusion, with occlusions being the points that are visible only in one of the stereo images and, therefore, don’t present correspondences. Finally, post-processing steps could be implemented to improve the quality of the output through filters or the refinement of the image. The implementation of these methods gave us a general idea of the best performance algorithm. The method that gives the best results both in execution time and erroneous pixels is RANSAC algorithm combined with an OC method to detect occlusions and a Meanshift algorithm for the segmentation step. The algorithm with the best time results is the one that uses the Birchfield and Tomasi approach. Finally, the algorithm with the lower number of false matches is the RANSAC algorithm combined with a LRcheck method for detecting occlusions and a Meanshift algorithm. Among all this results, one of the best performance has been choosen to be Figure 1 below, where the true disparity map is provided on the right hand side of the document and the output of our algorithm is on the left hand side.

Figure 1. Reconstrucción 3D de una escena As demonstrated on the above image, the implementation of global methods based on stereo vision yields excellent results. Nevertheless, these methods do not converge into a unique solution so it seems quite logical that research will continue in this field.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

IX

Agradecimientos Me gustaría aprovechar la ocasión para agradecer a toda la gente que me ha apoyado a lo largo de la carrera y en especial a realizar mi proyecto por toda la ayuda prestada. Sin vosotros hoy no podría estar escribiendo esta memoria. En primer lugar quisiera dar las gracias a mis padres, que me han apoyado siempre en todas las decisiones y me han animado en los momentos difíciles. Les agradezco el esfuerzo que han realizado para que yo haya podido estudiar en esta universidad y también que nunca hayan dejado de tener confianza en mí. Doy las gracias también a mi hermano, que siempre ha sabido escucharme y me ha ayudado en todo lo que he necesitado. No querría olvidarme de la universidad, que me ha permitido aprender cosas valiosisímas no sólo en el terreno académico, y gracias a la cual he logrado hacer cosas que nunca creí que podría hacer. Por supuesto, doy las gracias a mis directores, por sus consejos y su paciencia. Sin su ayuda no habría sido posible obtener estos resultados. Me gustaría agredecer a mis compañeros toda la ayuda prestada en el proyecto y muy en especial a Andrea y a Cristina, siempre habeis estado ahí en estos cinco años de carrera, apoyandome y ayudandome siempre que lo he necesitado, sin condiciones. Sois sin duda lo más importante que me llevo de ICAI. Por último, agradecer a Alberto toda su paciencia y su cariño, gracias a ti he logrado superar todas las dificultades que me han ido surgiendo a lo largo de la carrera, muchas gracias por estar siempre dispuesto a escucharme y confiar en mí.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

X

TML

DOCUMENTO I

MEMORIA

Índice I.

Memoria

1. Introducción 1.1. Estado del arte . . . . . . . . . . . . . 1.1.1. Revisión de los métodos existentes 1.1.2. Conclusiones . . . . . . . . . . . 1.2. Motivación . . . . . . . . . . . . . . 1.3. Objetivos . . . . . . . . . . . . . . . 1.4. Metodología . . . . . . . . . . . . . . 1.5. Recursos . . . . . . . . . . . . . . . .

9 . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

2. Reconstrucción 3D 2.1. Modelos matemáticos de la cámara. Modelo pinhole . . . 2.2. Calibración . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Geometría epipolar . . . . . . . . . . . . . . . . . . . . 2.4. Correspondencia . . . . . . . . . . . . . . . . . . . . . . 2.4.1. Estado del arte de los métodos de correspondencia . 2.4.2. Métodos locales . . . . . . . . . . . . . . . . . . . . 2.4.2.1. Métodos basados en el área. Correlación de área. 2.4.2.2. Métodos basados en características . . . . . . . 2.4.3. Métodos globales . . . . . . . . . . . . . . . . . . . 2.5. Reconstrucción . . . . . . . . . . . . . . . . . . . . . . 3. Métodos globales de optimización 3.1. Métodos deterministas . . . . . . . . . . . . . . 3.1.1. Iterated conditional models . . . . . . . . . . 3.2. Métodos probabilísticos . . . . . . . . . . . . . . 3.2.1. Programación dinámica . . . . . . . . . . . . 3.2.2. Markov Random Fields . . . . . . . . . . . . 3.2.2.1. Belief propagation . . . . . . . . . . . . 3.2.3. Graph cuts o Corte de grafos . . . . . . . . . 3.2.3.1. Recocido simulado . . . . . . . . . . . . 3.2.3.2. Graduated non convexity algorithm(GNC)

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . . .

. . . . . . . . .

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

. . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . .

10 11 11 16 17 21 22 23

. . . . . . . . . .

24 25 27 27 28 29 31 31 32 32 33

. . . . . . . . .

35 36 36 37 38 40 44 47 50 51

2

D OCUMENTO I. M EMORIA § Í NDICE

3.2.3.3. Tree reweighted message passing (TRW) . . . . . . . . . . . 3.3. Métodos cooperativos . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Preprocesamiento de imágenes 4.1. Algoritmo Mean Shift o de desplazamiento de la media . . . 4.1.1. Teoría del desplazamiento de la media . . . . . . . . . . 4.1.2. Procedimiento para la determinación de la segmentación 4.1.3. Resultados . . . . . . . . . . . . . . . . . . . . . . . . .

51 52

. . . .

54 55 55 60 60

. . . . . . . .

62 63 63 63 66 69 70 70 70

. . . . . . . .

72 74 74 75 76 76 78 79 79

7. Post-procesado de imágenes 7.1. Técnicas de filtrado . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.0.1. Filtros de paso bajo . . . . . . . . . . . . . . . . . . . . . . . 7.2. Estimación de subpíxeles . . . . . . . . . . . . . . . . . . . . . . . .

81 82 82 86

. . . .

. . . .

. . . .

5. Elección de los términos de la función objetivo 5.1. Elección del término Edata . . . . . . . . . . . . . . . . . . . . . 5.1.1. Método de diferencia de intensidades . . . . . . . . . . . . . 5.1.2. Método de cálculo de la similitud pixel a pixel . . . . . . . . . 5.1.3. Método de diferencia de cuadrados de intensidades y gradiente 5.1.4. Normilized cross-correlation (NCC) . . . . . . . . . . . . . . 5.2. Término Esmooth . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1. Diferencia de disparidades . . . . . . . . . . . . . . . . . . . 5.2.2. Diferencia de disparidades saturada a un valor . . . . . . . . . 6. Manejo de oclusiones 6.1. Métodos que detectan oclusiones . . . . . . . . . 6.1.1. Left-Right checking . . . . . . . . . . . . . . 6.1.2. Restricción en el orden de los píxeles . . . . 6.2. Métodos que reducen sensibilidad . . . . . . . . 6.2.1. RANSAC . . . . . . . . . . . . . . . . . . . 6.2.2. Least Median Square(LMS) . . . . . . . . . 6.3. Métodos que modelan la geometría de la oclusión 6.3.1. Modelo de oclusión global . . . . . . . . . .

. . . . . . . .

. . . . . . . .

8. Resultados 8.1. Métodos de optimización . . . . . . . . . . . . . . . 8.2. Términos de la función energía . . . . . . . . . . . . 8.3. Algoritmos de resolución de correspondencias . . . . 8.4. Valoración del mejor algoritmo frente a otros métodos

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . .

. . . . . . . .

. . . . . . . .

. . . .

. . . .

87 88 92 98 102

9. Conclusiones

104

10. Futuros desarrollos

107

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

3

D OCUMENTO I. M EMORIA § Í NDICE

Bibliografía

II. Manual de usuario

109

114

0.1. Características de la interfaz . . . . . . . . . . . . . . . . . . . . . . 115 0.2. Utilización de la interfaz . . . . . . . . . . . . . . . . . . . . . . . . 118

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

4

Índice de figuras 1. 2. 3. 4.

5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24.

Geometría epipolar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Reconstrucción tridimensional por métodos pasivos de perspectiva . . . . . Reconstrucción tridimensional por proyección de luz estructurada . . . . . Reconstrucción tridimensional de datos provenientes de TAC, RM y SPECT como parte del análisis preoperatorio de dos cavernomas cerebrales productores de un cuadro convulsivo . . . . . . . . . . . . . . . . . . . . . Reconstrucción de una mina en Chile . . . . . . . . . . . . . . . . . . . . Reconstrucción del polo norte de Marte . . . . . . . . . . . . . . . . . . . Huracán Rita. NASA. Septiembre 2005 . . . . . . . . . . . . . . . . . . . Basílica romana de Riegel. Reconstrucción realizada por Dr. Christian Dreier Esquema de la metodología a seguir . . . . . . . . . . . . . . . . . . . . . Modelo geométrico de la formación de una imagen . . . . . . . . . . . . . Modelo de la cámara pinhole . . . . . . . . . . . . . . . . . . . . . . . . . Configuración general de una geometría epipolar . . . . . . . . . . . . . . Técnicas de correlación de área más comunes[44] . . . . . . . . . . . . . . Método del punto medio . . . . . . . . . . . . . . . . . . . . . . . . . . . a) Mapa de disparidades real b)Mapa de disparidades obtenido con ICM . . Correspondencia estéreo usando programación lineal. . . . . . . . . . . . Vecindarios de órdenes 1,2,4,5 y 8 . . . . . . . . . . . . . . . . . . . . . . Mapa de disparidades real a la izquierda y resultado obtenido aplicando BP de Max-producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mapa de disparidades real a la izquierda y resultado obtenido aplicando BP de suma-producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mapa de disparidades real a la izquierda y resultado obtenido con algoritmo de intercambio de etiquetas . . . . . . . . . . . . . . . . . . . . . . . . . . Mapa de disparidades real a la izquierda y resultado obtenido con algoritmo de expansión de etiquetas . . . . . . . . . . . . . . . . . . . . . . . . . . . Cálculo de las ramas en TRWS . . . . . . . . . . . . . . . . . . . . . . . . En el lado izquierdo de la imagen se observa el mapa de disparidades real de tsukuba, en el lado derecho el resultado obtenido de la aplicación de TRWS Ejemplo típico del análisis del espacio de características . . . . . . . . . .

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

14 15 16

18 19 20 20 21 22 25 25 28 32 34 37 39 42 46 47 49 50 52 52 56

5

D OCUMENTO I. M EMORIA § Í NDICE

25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57.

Algoritmo de desplazamiento de la media . . . . . . . . . . . . . . . . . . Segmentación meanshift sobre la imagen Tsukuba . . . . . . . . . . . . . . Segmentación meanshift sobre la imagen Aloe . . . . . . . . . . . . . . . . Mapa de disparidades de tsukuba empleando SD . . . . . . . . . . . . . . Mapa de disparidades de aloe empleando SD . . . . . . . . . . . . . . . . Valores de intensidad muestreados por el sensor . . . . . . . . . . . . . . . Cálculo de la disimilitud . . . . . . . . . . . . . . . . . . . . . . . . . . . Mapa de disparidades de tsukuba empleando el cálculo de similitud . . . . Mapa de disparidades de aloe empleando el cálculo de similitud . . . . . . Operador Roberts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Operador Sobel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Operador Prewitt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mapa de disparidades de tsukuba para w = 0,3 con operador Sobel . . . . . Mapa de disparidades de tsukuba para w = 0,6 con operador Sobel . . . . . Mapa de disparidades de tsukuba para w = 0,9 con operador Sobel . . . . . Mapa de disparidades de tsukuba para Edata en NCC . . . . . . . . . . . . Puntos ocluidos en una escena . . . . . . . . . . . . . . . . . . . . . . . . Escena con textura repetitiva . . . . . . . . . . . . . . . . . . . . . . . . . Oclusiones en la imagen tsukuba . . . . . . . . . . . . . . . . . . . . . . . Oclusiones en la imagen aloe . . . . . . . . . . . . . . . . . . . . . . . . . Ejemplo de la restricción en el orden de los píxeles . . . . . . . . . . . . . Oclusiones de la imagen tsukuba . . . . . . . . . . . . . . . . . . . . . . . Oclusiones de la imagen aloe . . . . . . . . . . . . . . . . . . . . . . . . . Ejemplo de la restricción en el orden de los píxeles . . . . . . . . . . . . . Tsukuba con refinamiento por RANSAC . . . . . . . . . . . . . . . . . . . Tsukuba con refinamiento por LMS . . . . . . . . . . . . . . . . . . . . . Tsukuba con aplicación del modelo de oclusión global . . . . . . . . . . . a)Mapa de disparidades sin filtro b)Mapa de disparidades con filtro de la media a)Mapa de disparidades sin filtro b)Mapa de disparidades con filtro de la media ponderada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Aplicación filtro de la mediana . . . . . . . . . . . . . . . . . . . . . . . . a)Mapa de disparidades sin filtro b)Mapa de disparidades con filtro de la mediana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a)Mapa de disparidades sin estimación b)Mapa de disparidades con con estimación de subpíxeles . . . . . . . . . . . . . . . . . . . . . . . . . . . Imagenes obtenidas de la aplicación de los métodos de optimización, de derecha a izquierda y de arriba a abajo: ICM, Swap, Expansion, MaxProdBP, BPS y TRWS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

59 60 61 63 63 64 65 65 66 67 68 68 69 69 69 70 73 73 74 75 75 75 76 77 78 79 80 83 84 85 85 86

89

6

D OCUMENTO I. M EMORIA § Í NDICE DE FIGURAS

58. Imagenes obtenidas de la aplicación de los métodos de optimización, de derecha a izquierda y de arriba a abajo: ICM, Swap, Expansion, MaxProdBP, BPS y TRWS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 59. Imagenes obtenidas de la aplicación de los métodos de optimización, de derecha a izquierda y de arriba a abajo: ICM, Swap, Expansion, MaxProdBP, BPS y TRWS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 60. Frente de Pareto de la imagen tsukuba para distintos métodos de optimización 91 61. Frente de Pareto de la imagen aloe para distintos métodos de optimización . 91 62. Frente de Pareto de la imagen cones para distintos métodos de optimización 92 63. Análisis de los términos de la función objetivo . . . . . . . . . . . . . . . . 93 64. Tsukuba para los distintos términos de la función objetivo . . . . . . . . . 94 65. Aloe para los distintos términos de la función objetivo . . . . . . . . . . . 94 66. Baby para los distintos términos de la función objetivo . . . . . . . . . . . 95 67. Cones para los distintos términos de la función objetivo . . . . . . . . . . . 95 68. Teddy para los distintos términos de la función objetivo . . . . . . . . . . . 96 69. Frente de pareto para tsukuba . . . . . . . . . . . . . . . . . . . . . . . . . 96 70. Frente de pareto para aloe . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 71. Frente de pareto para baby . . . . . . . . . . . . . . . . . . . . . . . . . . 97 72. Frente de pareto para cones . . . . . . . . . . . . . . . . . . . . . . . . . . 97 73. Frente de pareto para teddy . . . . . . . . . . . . . . . . . . . . . . . . . . 98 74. Análisis global de los algoritmos . . . . . . . . . . . . . . . . . . . . . . . 99 75. Imagenes tsukuba para los distintos algoritmos . . . . . . . . . . . . . . . 100 76. Frente de pareto para tsukuba . . . . . . . . . . . . . . . . . . . . . . . . . 100 77. Ranking de la universidad de Middlebury . . . . . . . . . . . . . . . . . . 103 78. Ejemplo de la reconstrucción tridimensional de la escena[53] . . . . . . . . 108 79. Interfaz de usuario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 80. Imagenes de prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

7

Acrónimos ICM BP GC TRWS MRF CAM

Iterated Conditional Models Belief Propagation Graph cuts o corte de grafos Tree Reweighted Message Passing Markov Random Fields Campos aleatorios de Markov

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

8

PARTE I

TML MEMORIA

Capítulo 1 Introducción reconstrucción tridimensional de una escena es una disciplina dentro del campo de la visión artificial y que de manera general se define como el proceso de captura de la forma y la apariencia de objetos reales dentro de una escena. Uno de los mayores retos a los que se ha enfrentado esta disciplina y sobre el que ha puesto un mayor énfasis es la reconstrucción automatica de la escena con escasa o nula intervención por parte del usuario. De esta manera, se consigue proveer del sentido de la vista a sistemas autónomos para que puedan interactuar de forma eficiente en ambientes complejos[36] .

L

A

Las técnicas de reconstrucción tridimensional son múltiples y en muchos casos específicas para cada actividad. Así, nos encontramos con mecanismos tan sencillos como los brazos articulados para la reconstrucción de objetos que son especialmente útiles en ambientes industriales o dispositivos tan complejos como las tomografías o la resonancia magnética en el campo de la medicina. Dentro del campo de la navegación de sistemas autónomos, de la topografía o de la realidad virtual adquieren especial relevancia los métodos de captura por reflexión, donde se encuentran entre otros los sonar, radar, láser o la visión estéreo. Debido a la simplicidad, versatilidad y al bajo coste que supone esta última técnica, la visión estéreo ha sido elegida como objeto de estudio en este proyecto. En un principio, el estudio de la visión estéreo se centró en los seres humanos y en su capacidad de percepción del entorno a través de los ojos que, dada su posición, reciben imágenes sensiblemente diferentes de una misma escena. Estas diferencias relativas en la posición reciben el nombre de disparidades y guardan una relación directa con la profundidad a la que se encuentran los objetos respecto al observador, de manera que una vez captadas las imágenes a través de los ojos, el cerebro se encarga de de la reconstrucción tridimensional de la escena.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

10

I. M EMORIA § 1. I NTRODUCCIÓN

A partir de la década de los 70, el estudio de la visión estéreo se extendió al campo de la visión artificial, donde ha sido un tema ampliamente estudiado ofreciendo considerables mejoras en ámbitos tan dispares como la navegación de robots, la medicina o la topología.

1.1.

Estado del arte

La reconstrucción tridimensional de una escena es un proceso complicado que requiere de varias etapas para conseguir unos resultados adecuados. En primer lugar será necesaria la transformación de las morfologías complejas que forman parte de la escena en datos para su posterior tratamiento informático. Una vez capturada la escena, se procede a la reconstrucción tridimensional propiamente dicha, que difiere mucho en función del método de captura elegido.

1.1.1.

Revisión de los métodos existentes

A continuación se hará una revisión de los métodos existentes para la obtención del mapa tridimensional de una escena. Los métodos de captura se puede dividir en tres grandes grupos: Captura por contacto Son los sistemas de captura más antiguos. Existen varios sistemas, entre ellos aquellos donde las coordenadas de los puntos se obtienen gracias al desplazamiento de una punta sobre la superficie a medir. Se ha avanzado mucho en la técnica, existiendo ya en el mercado cabezales de toma de medidas continuas con una velocidad considerablemente mayor a la de los cabezales convencionales. Los brazos articulados de operación manual son otro tipo de dispositivos de contacto con una elevada precisión pero escasa velocidad de adquisición de datos ya que el sistema es manual. Para emplear estos sistemas por contacto, se necesita que las piezas tengan la rigidez suficiente para que no se deformen por el contacto con la punta. Por otro lado, a pesar de que se trata de mecanismos de gran resolución, resulta complicado a veces obtener la reconstrucción de algunos puntos debido a su difícil acceso. Captura por transmisión Son aquellos sistemas que mediante la emisión de ondas o campos magnéticos consiguen obtener una reconstrucción del cuerpo que recibe las emisiones. Este método se divide en tres técnicas a sus vez:

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

11

I. M EMORIA § 1. I NTRODUCCIÓN

• Tomografía: Se denomina así a la técnica de procesado de imágenes por secciones. Este método es usado en medicina, arqueología, biología, geofísica, oceanografía, ciencia de los materiales y otras ciencias. En la mayoría de los casos se basa en un procedimiento matemático llamado reconstrucción tomográfica. Hay muchos tipos diferentes de tomografía en función de los fenómenos físicos que se utilicen para extraer la información, entre éstos se encuentran los rayos X, rayos gamma, aniquilación de electrones y positrones - reacción, etc. • Ultrasonidos: Son una onda acústica cuya frecuencia está por encima del espectro audible del oído humano (aproximadamente 20.000 Hz) y que se utilizan para la determinación tridimensional de un objeto o escena tanto en aplicaciones industriales como en la medición de distandias, caracterización interna de los materiales o ensayos destructivos así como en medicina, en el campo de la fisioterapia, ecografía o ultrasonoterapia. • Resonancia magnética: Es un fenómeno físico basado en las propiedades mecánico-cuánticas de los núcleos atómicos. La obtención de imágenes por este método es una técnica no invasiva que utiliza el fenómeno de la resonancia magnética para obtener información sobre la estructura y composición del cuerpo a analizar. Tiene múltiples aplicaciones, tanto en el campo de la medicina para el diagnóstico de cancer y otras patologías como en el sector industrial, donde se emplea para analizar la estructura de materiales orgánicos e inorgánicos. Captura por reflexión Se trata de técnicas que al igual que las anteriores realizan la reconstrucción tridimensional sin contacto, con una velocidad de adquisición muy superior a la de las técnicas por contacto. Las técnicas de captura por reflexión se dividen a su vez en dos grupos: • No óptica Dentro de esta categoría se tienen dos nuevos dispositivos, el sonar y el radar. El sonar es un dispositivo que usa la propagación del sonido para navegar, comunicarse o detectar otros cuerpos. Su aplicación fundamental es en medios acuáticos aunque la localización acústica se usó en aire antes que el radar, siendo aún de aplicación el SODAR (la exploración vertical aérea con sonar) para la investigación atmosférica. El radar es un sistema que usa ondas electromagnéticas para medir distancias, altitudes, direcciones y velocidades de objetos estáticos o móviles como aeronaves, barcos, vehículos motorizados, formaciones meteorológicas y el Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

12

I. M EMORIA § 1. I NTRODUCCIÓN

propio terreno. Su funcionamiento se basa en emitir un impulso de radio, que se refleja en el objetivo y se recibe típicamente en la misma posición del emisor. A partir de este eco se puede extraer gran cantidad de información. El uso de ondas electromagnéticas permite detectar objetos más allá del rango de otro tipo de emisiones (luz visible, sonido, etc.) Entre sus ámbitos de aplicación se incluyen la meteorología, el control del tráfico aéreo y terrestre y gran variedad de usos militares. • Óptica Los métodos de captura por reflexión óptica se dividen en métodos pasivos y métodos activos. Los métodos pasivos permiten obtener información de la profundidad de la escena mediante la fusión de dos o más escenas captadas mediante cámaras. Estas técnicas simulan la capacidad del ojo humano de captar tridimensionalmente una escena a partir de las dos imagenes tomadas por sus ojos. Este proceso es conocido como visión estereoscópica y se basa en utilizar dos puntos de vista de un mismo objeto para encontrar las coordenadas tridimensionales. Para determinar la posición de un punto a partir de dos imágenes es necesario tener un modelo del sistema óptico utilizado. Este principio general puede mejorarse con modelos de cámaras más elaborados o utilizando más de dos cámaras, lo que se conoce con el nombre de fotogrametría. Uno de los puntos fuertes de este método es la obtención de las coordenadas tridimensionales de una superficie independientemente de la iluminación específica. Existen cuatro técnicas de reconstrucción tridimensional por métodos pasivos, que se detallarán a continuación: ◦ Geometría epipolar: Conociendo los puntos correspondientes en cada una de las imágenes al mismo punto en la escena tridimensional, así como la posición y orientación de las cámaras, se puede establecer un modelo tridimensional de la escena gracias a ciertas técnicas de reconstrucción como la triangulación. Una vez determinados dos puntos correspondientes, éstos junto al punto de la escena al que representan forman un triángulo cuya intersección con los planos de proyección son las líneas epipolares. Para establecer la correspondencia entre dos puntos de cada una de las imágenes, se sabe que dado un punto P1 el punto correspondiente P2 se encuentra sobre la línea epipolar, como se puede observar en la figura 1

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

13

I. M EMORIA § 1. I NTRODUCCIÓN

Figura 1. Geometría epipolar ◦ Shape from Shading(SFS): La técnica de SFS[42] consiste en la recuperación de la forma de una escena a partir de la variación gradual en las sombras de una imagen. Para resolver este problema, se debe estudiar la manera en que se forman las imágenes. Un comportamiento muy simple es el lambertiano, en el que la escala de gris de un pixel en la imagen depende de la dirección de la fuente de luz y de la supericie normal en ese punto. De manera que la determinación de las profundidades parece relativamente simple, sin embargo, surge el problema de las imágenes que no siguen un patrón lambertiano y que son objeto de estudio actualmente. ◦ Dibujo en perspectiva: Sigue los principios básicos de la geometría cónica en el dibujo técnico. A partir de dos imágenes y de un dibujo en perspectiva de la escena usando los puntos de fuga, para cada punto de la imagen, se pueden determinar sus coordenadas en el espacio. En la Figura 2 se muestra un ejemplo de este tipo de reconstrucción.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

14

I. M EMORIA § 1. I NTRODUCCIÓN

Figura 2. Reconstrucción tridimensional por métodos pasivos de perspectiva Los métodos de reconstrucción activos hacen intervenir una fuente de luz específica para determinar las coordenadas tridimensionales de los puntos de medida. Estos sistemas constan siempre como mínimo de un emisor de luz y un receptor, sólo sirven para objetos que reflejen en todas direcciones, es decir, no se puede trabajar con cuerpos negros, especulares ni transparentes así como con medios participativos. El dispositivo envía un haz de luz a la escena y mide el tiempo que tarda en volver, una vez reflejado el haz de luz, se puede determinar la profundidad a la que se encuentra el objeto. Dentro de esta técnica también existen tres subdivisiones, por un lado se encuentran los métodos activos que son variantes de los pasivos, por otro lado aquellos basados en la distancia (sonar y láser) y por último los métodos activos basados en triangulación (proyección de luz estructurada y telemetría). ◦ Láser: La fuente de luz en estos sistemas es un láser de diodos. Dicho láser proyecta una línea de luz sobre la superficie bajo estudio, esta superficie reflejará la luz y será detectada por una o dos células fotosensibles que se encuentran situadas a ambos lados del láser. Estos detectores leen el haz de luz reflejado y transmiten la información obtenida sobre el perfil de la pieza a un software. ◦ Sonar: Como ya se ha indicado anteriormente, el sonar es una técnica que usa la propagación del sonido esencialmente en ambientes acuáticos aunque puede desenvolverse también en la superficie terrestre.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

15

I. M EMORIA § 1. I NTRODUCCIÓN

◦ Proyección de luz estructurada: En este sistema el emisor es un proyector de luz blanca y el receptor una cámara CCD. El proyector lanza sobre la escena una serie de franjas de luz verticales de claros y sombras alternadas que son registradas por la cámara. Una vez recogidas todas las muestras se procede a la reconstrucción tridimensional por triangulación, donde el proyector actua como un emisor de planos de luz mientras que la cámara CCD recibe líneas rectas. El cálculo de la profundidad se determinará a partir de las intersecciones plano-recta que definen emisor y receptor.

Figura 3. Reconstrucción tridimensional por proyección de luz estructurada ◦ Telemetría: La telemetría determina el mapa de profundidades de la escena a partir del tiempo que tarda en recorrer un rayo de luz, generalmente láser, la distancia de ida y vuelta entre el foco emisor y la superficie que se desea medir. Para la cálculo de dicha distancia se pueden utilizar dos métodos. Por un lado se puede realizar una medida del tiempo de vuelo o tiempo que tarda el haz de luz en retornar a la fuente emisora, y por otro lado se puede calcular por diferencia de fase, en este caso se envia un impulso luminoso a una frecuencia conocida y se mide el desfase que se ha producido entre el haz enviado y el recibido.

1.1.2.

Conclusiones

Como se puede comprobar, se cuenta con multitud de métodos para realizar la reconstrucción tridimensional de una escena u objeto, luego se deberá prestar especial

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

16

I. M EMORIA § 1. I NTRODUCCIÓN

atención al método seleccionado para realizar el mapa de profundidades. Existen métodos que se caracterizan por su sencillez y su precisión como los de captura por contacto, pero que se caracterizan también por ser lentos por lo tanto serán muy recomendables para ambientes industriales donde se pretenda analizar pequeños objetos pero no serán útiles cuando lo que se pretenda estudiar es la morfología completa de un gran objeto o el reconocimiento de una escena. Los métodos de captura por transmisión ofrecen resultados muy fiables y rápidos pero que requieren una tecnología muy complicada por lo que son equipos costosos. Las tomografías se emplean para disciplinas muy especificas como la medicina o la paleontología pero resultan inservibles en aquellos campos en los que se necesite una reconstrucción tridimensional densa del objeto o escena, los ultrasonidos presentan un uso más extendido empleandose en aplicaciones médicas, medición de distancias o caracterización interna de los materiales y por último las resonancias magnéticas también tienen un uso muy restringido ya que emplean radiaciones para la reconstrucción. Los métodos de captura por reflexión son los más adecuados para la creación de dispositivos autónomos que tengan capacidad de reconocimiento del entorno. Aunque todos estos métodos son rápidos y precisos, tanto el sonar como el radar, las técnicas de luz estructurada, la telemetría y el láser son sistemas caros que dependen en gran medida del ambiente en el que se encuentre situada la escena por lo que se han elegido las técnicas de captura por reflexión óptica pasiva para realizar la reconstrucción tridimensional en este proyecto. En particular, se realizará un estudio sobre la reconstrucción tridimensional a partir de las imágenes tomadas con una cámara estéreo y métodos globales de optimización, que ofrecen un mapa de disparidades denso de la imagen, de manera que se puede conocer la profundidad a la que se encuentran todos los puntos de la escena.

1.2.

Motivación

Las técnicas de reconstrucción 3D constituyen una herramienta esencial en todas aquellas disciplinas en las que es necesaria la recuperación de la estructura tridimensional de una escena. Por ello, se han ido desarrollando durante los últimos años numerosos métodos de reconstrucción, entre los que caben destacar la técnica de luz estructurada, la telemetría láser, el control de parámetros ópticos, la reconstrucción por cámara móvil o la técnica multivista, donde se encuentra la visión estereoscópica o reconstrucción tridimensional de una escena a partir de al menos dos vistas en 2D o

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

17

I. M EMORIA § 1. I NTRODUCCIÓN

estéreo de la misma. Éste método va a constituir la base de nuestro estudio puesto que presenta unos resultados razonablemente rápidos y fiables. Entre esos campos en los que la tercera dimensión juega un papel importante podemos destacar la medicina, la topografía, el estudio de la tierra y otros planetas, la telepresencia o la realidad virtual. El estudio de la representación tridimensional en medicina se ha expandido considerablemente en los últimos años. En el campo de la clínica la visualización en 3D puede ser de mucha utilidad en cirugía, ortopedia, traumas músculo-esqueléticos, estudios en hígado, análisis de tejidos reconstrucción de vasos sanguíneos, trombosis venosa, isquemias y visualización neuronal entre otros. Se usa para visualizar imágenes o modelos del interior del cuerpo humano, bien artificiales, bien generados a partir de imágenes reales obtenidas por medio de TAC (Tomografía Asistida por Computador) o RMN (Resonancia Magnética Nuclear). Técnicas como la radiografía estereoscópica permiten situar claramente cuerpos extraños o anomalías en el interior del paciente. A continuación, se muestra una ejemplo de aplicación de la reconstrucción tridimensional en medicina.

Figura 4. Reconstrucción tridimensional de datos provenientes de TAC, RM y SPECT como parte del análisis preoperatorio de dos cavernomas cerebrales productores de un cuadro convulsivo

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

18

I. M EMORIA § 1. I NTRODUCCIÓN

En el campo de la topografía, una de las aplicaciones prácticas más antigua es la visualización y medición del relieve terrestre mediante fotografías aéreas. Si un avión toma dos fotografías de una zona de terreno con una cierta distancia calculada entre ellas, se obtiene un par de imágenes en estéreo, de las que posteriormente se puede obtener el relieve. En la actualidad, se han desarrollado sistemas especiales capaces de representar incluso el relieve submarino.

Figura 5. Reconstrucción de una mina en Chile Por otro lado, la NASA lleva años tomando imágenes de la tierra y otros planetas por medio de satélites. Las imágenes en estéreo que ha obtenido la agencia del suelo de Marte le han ayudado no sólo a conocer la topografía del planeta sino también las distancias y tamaños de las rocas en su superficie facilitando en gran medida la navegación de la sonda Pathfinder. Así mismo, las imágenes que obtiene gracias a los satélites sirven de ayuda para calcular la trayectoria de ciertos fenómenos meteorológicos.Las Figuras 6 y 7muestran ejemplos de este tipo de aplicaciones

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

19

I. M EMORIA § 1. I NTRODUCCIÓN

Figura 6. Reconstrucción del polo norte de Marte

Figura 7. Huracán Rita. NASA. Septiembre 2005 La telepresencia es una técnica empleada para el control de sistemas o procesos que se encuentran en entornos hostiles o peligrosos y para los que se utilizan un par de cámaras en estéreo que recogen la situación de la escena permitiéndonos operar en el entorno. Por último, la realidad virtual es una técnica que emplea las imágenes estereoscópicas de una escena para introducir al usuario dentro de la misma gracias a un ordenador. Este campo de estudio es muy amplio y abarca disciplinas tan variadas como la arquitectura, la arqueología, la medicina o la industria aeroespacial con los simuladores de vuelo. Un ejemplo de aplicación se encuentra en la Figura 8

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

20

I. M EMORIA § 1. I NTRODUCCIÓN

Figura 8. Basílica romana de Riegel. Reconstrucción realizada por Dr. Christian Dreier

1.3.

Objetivos

Este proyecto constituye la continuación del proyecto anterior Reconstrucción 3D de modelos utilizando técnicas de visión artificial, que trataba los aspectos relativos a los modelos de reconstrucción tridimensional basados en métodos locales. Actualmente, el objetivo fundamental sigue siendo el estudio y aplicación de modelos de reconstrucción tridimensional pero en este caso a partir de los métodos globales y distintas técnicas de optimización. De forma general, se pueden dividir los objetivos en: Objetivo principal • Clasificación, evaluación y comparación de métodos de reconstrucción estéreo basados en optimización Objetivo secundario • Aporte de nuevas ideas a los algoritmos desarrollados

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

21

I. M EMORIA § 1. I NTRODUCCIÓN

1.4.

Metodología

El proceso que se plantea para la resolución tridimensional de una escena a partir de métodos globales sigue de manera habitual la secuencia que se muestra a continuación.

Figura 9. Esquema de la metodología a seguir Obtención del par estéreo. Para proceder al análisis de la escena, en primer lugar será preciso obtener dos vistas de la misma desde puntos ligeramente distintos. Pre-procesado de la imagen. En numerosas ocasiones se realizará un preprocesado de la imagen con el objetivo de identificar objetos dentro de la escena, eliminar posibles ruidos introducidos por la cámara, etc. De esta manera, se facilitará la obtención de unos mejores resultados. Elección del método de optimización. Como se ha señalado anteriormente, el proyecto se centra en el estudio de los métodos globales, que minimizan una función objetivo formada fundamentalmente por dos términos, un primero que llamaremos data y que se encarga de comprobar la validez de la correspondencia entre pixeles de cada una de las imágenes y un segundo término llamado smooth que se encarga de aproximar correctamente la disparidad de los puntos próximos a los bordes de los objetos. Los métodos de optimización que se considerarán para resolver la función objetivo se dividen en dos grupos fundamentales, los métodos deterministas y los heurísticos. Elección del término data. Existen numerosas funciones que se utilizan para determinar la calidad de la correspondencia, se estudiarán los métodos más elementales así como aquellos que han supuesto una mejora importante en el campo de la reconstrucción 3D. Elección del término smooth. Se elegirá cuidadosamente este término ya que se trata de la clave para el manejo de las discontinuidades. Se estudiará su influencia Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

22

I. M EMORIA § 1. I NTRODUCCIÓN

sobre la calidad del mapa de disparidades final, teniendo en cuenta tanto la forma de esta función como el peso relativo de este término dentro de la función objetivo. Manejo de las oclusiones. Las oclusiones juegan un papel fundamental en la determinación de las correspondencias, por lo que será necesario estudiar los distintos métodos tanto para detectarlas como para conseguir algoritmos cada vez menos sensibles a estos puntos. Se define oclusión como aquel punto que se encuentra visible en una de las imágenes captadas por la cámara y que no lo está en la segunda imagen estéreo, de manera que no existe correspondencia posible entre puntos de ambas imágenes. Post-procesado. Una vez determinado el mapa de disparidades, se pueden aplicar distintos métodos para mejorar la calidad de los mismos, de manera que el error calculado mediante la comparación con los mapas de disparidad reales se haga muy pequeño.

1.5.

Recursos

Para llevar a cabo la reconstrucción tridimensional, es necesario minimizar la función objetivo que se plantee en cada caso, para ello se han utilizado dos herramientas diferentes. En primer lugar se ha utilizado GAMS (General Algebraic Modeling System), que es un sistema de modelización de alto nivel para problemas de programación matemática. Por otro lado, se ha utilizado el entorno de programación Visual Studio, donde se usará C++ como lenguaje de programación. En este caso, la resolución de la función objetivo se ha llevado a cabo a partir del código MRF benchmark[6, 17, 37, 38, 39, 40, 41].

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

23

Capítulo 2 Reconstrucción 3D este capítulo se introducirán las bases de la reconstrucción tridimensional mediante visión estéreo así como las dificultades que se plantean en la misma. Se trata de un análisis generalista, donde las etapas que se definen son válidas para cualquier técnica de reconstrucción multivista. La reconstrucción tridimensional de una escena plantea numerosos problemas que se deben abordar en etapas sucesivas para conseguir un mapa de disparidades denso de buena calidad. En primer lugar, se debe proceder a la calibración de la cámara, que consiste en determinar la geometría tanto interna como externa de la misma. Una vez desarrollada esta fase, se establece un algoritmo de correspondencia que permita obtener las disparidades en el par de imágenes, de manera que se puedan utilizar dichas disparidades para la determinación de las profundidades en la escena. Para facilitar la tarea a este algoritmo, existen restricciones generalmente basadas en propiedades físicas y geométricas de los objetos y superficies presentes en la escena. Entre éstas, cabe destacar que las correspondencias se establecen en una misma línea epipolar, luego será necesario conocer los principios de la geometría epipolar. Una vez conocido el mapa de disparidades, las profundidades para todos los puntos de la imagen se determinan a partir de un método de reconstrucción, entre los que cabe destacar la triangulación.

E

N

Este capítulo se divide en cuatro partes, en primer lugar se analizan los principios fundamentales de la geometría epipolar. A continuación se aborda el problema de la calibración de la cámara. En tercer lugar se detallan los distintos métodos de correspondencia, haciendo especial hincapié en aquellos métodos que se han considerado relevantes y serán objeto de un análisis posterior. Y por último, se introducen las distintas técnicas de reconstrucción tridimensional a partir del mapa de disparidades.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

24

I. M EMORIA § 2. R ECONSTRUCCIÓN 3D

2.1.

Modelos matemáticos de la cámara. Modelo pinhole

El modelo matemático nos da una idea del proceso de formación de la imagen. Una vez conocido el modelo matemático que rige el comportamiento de la cámara, se puede proceder a la obtención de las coordenadas bidimensionales de un punto de la imagen captada a partir de las coordenadas tridimensionales de un punto en la realidad. Este proceso se esquematiza en la figura inferior.

Figura 10. Modelo geométrico de la formación de una imagen De forma general, se pueden clasificar en cuatro tipos: Modelo monocular sencillo o pinhole: Suele ser habitual para modelar cámaras digitales. En este caso, la transformación que se sigue para llegar al modelo bidimensional de la imagen a partir de las coordenadas tridimensionales de los puntos en la escena se muestra en la figura 11.

Figura 11. Modelo de la cámara pinhole El punto m en la imagen captada por la cámara es el punto correspondiente a M en la escena tridimensional, que se obtiene a partir de la intersección de la Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

25

I. M EMORIA § 2. R ECONSTRUCCIÓN 3D

recta que une M con el centro óptico con el plano de la imagen. Si se definen M = (X, Y, Z)T y m = (x, y)T , ambas respecto a coordenadas de la cámara, la relación entre ambas se puede obtener mediante:   

x f

=

X Z

 

y f

=

Y Z

      X nx f 0 0 0       Y   ny  =  0 f 0 0  Z    n 0 0 1 0 1 Si además se tiene en cuenta que el punto M se encuentra en la escena y por lo tanto en coordenadas del mundo, se pueden definir X,Y y Z en función de las coordenadas X 0 , Y 0 y Z 0 mundo como:      X r11 r12 r13 tx X0      0  Y  r21 r22 r23 ty   Y   =    Z  r   0    31 r32 r33 tz   Z  1 0 0 0 1 1 Si además se tiene en cuenta la distorsión, las ecuaciones anteriores se pueden plantear como:        r11 r12 r13 tx X0   0 nxf Kx f 0 Cx 0        r21 r22 r23 ty   Y  Ky f Cy 0   nyf  =  0 r   0  31 r32 r33 tz   Z  n 0 0 1 0 0 0 0 1 1 Donde M = (X 0 , Y 0 , Z 0 )T y m = (xf , yf )T , la primera matriz a la derecha de la igualdad modela los parámetros extrínsecos de la cámara y la inmediatamente posterior los parámetros intrínsecos. Modelo monocular con lente fina: Es aquella que presenta un espesor despreciable en relación a su distancia focal. Esta característica permite simplificar los cálculos de las refracciones de los rayos de luz. Modelo monocular con lente gruesa: Es aquella cuyo espesor no es despreciable en comparación con su longitud focal. Sigue las mismas ecuaciones que el modelo monocular con lente fina salvo un cambio respecto de la interpretación de las distancias.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

26

I. M EMORIA § 2. R ECONSTRUCCIÓN 3D

Modelo binocular: se basa en el principio de la visión estereoscópica.

2.2.

Calibración

La calibración es un proceso esencial en la reconstrucción tridimensional a partir de técnicas multivista o visión estéreo. Sus objetivos fundamentales son por un lado la corrección de distorsiones y por otro el establecimiento de la geometría epipolar del sistema para poder rectificar las imágenes y simplificar la obtención del mapa de correspondencias. La calibración se define como el proceso mediante el cual se calculan los parámetros intrínsecos y extrínsecos de la cámara, a partir de un conjunto de puntos de control, conocidas las coordenadas tridimensionales de esos puntos y midiendo las correspondientes coordenadas de imagen, en la imagen obtenida con dicha cámara[43]. Dentro de los parámetros intrínsecos se encuentran los factores de escala, la distancia focal, el punto principal y la distorsión y en cuanto a los parámetros extrínsecos están el vector de traslación y la matriz de rotación. Las etapas que sigue el proceso de calibración para llegar a determinar dichos parámetros son: Obtención del modelo matemático Obtención de los datos de campo: En esta etapa se obtienen los puntos 2D de la imagen que provienen de los puntos tridimensionales de las escena. Determinación de los parámetros tanto intrínsecos como extrínsecos de la cámara: Una vez conocidos todos los puntos de la escena real y la imagen capturada por la cámara, se procede a resolver las ecuaciones que rigen el modelo que mejor se aproxima a la cámara.

2.3.

Geometría epipolar

Dentro de la geometría proyectiva, la geometría epipolar es aquella que representa la geometría estéreo. A continuación se muestra la configuración general de este tipo de geometrias.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

27

I. M EMORIA § 2. R ECONSTRUCCIÓN 3D

Figura 12. Configuración general de una geometría epipolar Como se observa en la figura, se define el plano epipolar para cada punto de la imagen como aquel que contiene los dos centros ópticos y el punto bajo estudio. Una vez establecido el plano epipolar, se puede determinar la recta epipolar, que se define para cada punto y cada cámara como la intersección del plano epipolar con el plano de la imagen captada. Las imágenes que van a ser objeto de prueba dentro de este proyecto son un caso particular de este tipo de geometría, donde los ejes de la cámara se encuentran alineados, de manera que el problema se simplifica enormemente ya que el plano epipolar cortará a las imágenes formando una recta epipolar horizontal luego a la hora de establecer las correspondencias entre los puntos, bastará con seleccionar un punto de una imagen y buscar sobre la línea horizontal que se encuentra sobre la misma posición vertical de la otra imagen el punto que mejor se corresponda.

2.4.

Correspondencia

El establecimiento de las correspondencias es, dentro del proceso de reconstrucción, la etapa mas importante. En ella se determinan los mapas de disparidad de la imagen, por lo tanto la calidad de reconstrucción que se obtenga finalmente dependerá fundamentalmente de la elección de un buen algoritmo. Se trata de un problema de difícil solución ya que geométricamente pueden existir infinitas soluciones o bien no tener solución, como ocurre en el caso de las oclusiones, lo que puede provocar mapas de disparidades llenos de falsas correspondencias. El objetivo de cualquier algoritmo de correpondencia aplicado a visión estéreo es hallar los puntos en cada una de las imágenes que se corresponden con el mismo punto en la escena. Este proceso se puede realizar de forma rápida y poco precisa a través de la obtención de mapas de disparidades dispersos o a partir de todos los puntos que conforman la escena con un mayor coste computacional a través de la reconstrucción

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

28

I. M EMORIA § 2. R ECONSTRUCCIÓN 3D

densa. En el primer caso, las técnicas de reconstrucción se basan fundamentalmente en la aplicación de métodos locales, que detectan puntos característicos de la escena de manera que se pueda obtener una idea general de los objetos que se encuentran en la escena. En el segundo caso, el problema se resuelve aplicando técnicas de optimización mediante los denominados métodos globales.

2.4.1.

Estado del arte de los métodos de correspondencia

La reconstrucción tridimensional de una escena a partir de un par de imágenes estéreo es un problema que ha sido ampliamente estudiado en el campo de la visión artificial. En sus comienzos, el estudio tridimensional de una escena, se centró en los fundamentos de la reconstrucción y los criterios para evaluar la eficacia de los algoritmos de la mano de Barnard and Fischler[1] en 1981. A lo largo de esta década, el enfoque que se dio al estudio de la visión estéreo continuó siendo global, incluyendo importantes avances tanto en la creación de nuevos algoritmos de correspondencia como en la jerarquización del procesado de las imágenes o el empleo de técnicas de determinación del error cometido en la reconstrucción. Al comienzo de la década de los 90, el estudio de la visión estéreo dio un giro radical sin abandonar la investigación más generalista del problema. La reconstrucción tridimensional había madurado suficientemente para lograr trasladar su estudio a problemas mucho más específicos como los de las oclusiones, las zonas carentes de textura o la implementación en tiempo real de sistemas de reconstrucción tridimensional. Se pueden considerar dos enfoques fundamentales, que son fuente de estudio en este periodo:

Reconstrucción dispersa: Se limita a la determinación de las coordenadas tridimensionales de ciertas partes de la escena a través de la identificación de los puntos de interés en las imágenes, que pueden tratarse de bordes, esquinas y demás elementos que caractericen un objeto. Esta técnica se utiliza fundamentalmente en aplicaciones para el reconocimiento del entorno de forma rápida y poco precisa. Reconstrucción densa: Se trabaja con la totalidad de los píxeles en ambas imágenes de manera que se obtiene un mapa de disparidades detallado, aunque el coste computacional en este caso es considerablemente más elevado. Esta técnica se utiliza fundamentalmente para la descomposición de una imagen en capas de igual profundidad para su posterior procesamiento y generación de nuevas vistas (Image Based Rendering), en la reconstrucción tridimensional de un objeto a partir de varias vistas o una secuencia vídeo, en navegación de robots, realidad virtual, seguimiento y vigilancia, etc. Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

29

I. M EMORIA § 2. R ECONSTRUCCIÓN 3D

Dentro de la reconstrucción dispersa surgieron grandes avances en esta época, fundamentalmente debido a la gran eficiencia de estos métodos. Dhond and Aggarwal[2] realizaron un extenso estudio sobre la literatura existente en este campo. Tiempo después, Venkateswar and Chellappa [3] propusieron un algoritmo basado en el reconocimiento de líneas, vértices, bordes y superficies dentro de la imagen, de manera que los objetos lograran ser claramente identificables y con profundidades conocidas. Se trataba de un método jerarquizado donde las correspondencias se determinan en primer lugar en el nivel más alto de la jerarquía, es decir, las superficies para luego ir descendiendo de nivel hasta las formas más sencillas, las líneas. Otra forma de aproximarse al problema es resolviendo la segmentación de la imagen[4] para luego calcular las correspondencias dentro del segmento[4, 5], esta técnica resultó ser muy efectiva en el manejo de las discontinuidades de profundidad. A lo largo de la década de los 80 y principio de los 90, las técnicas de reconstrucción por disparidad dispersa recibieron una gran atención debido a los razonables resultados que ofrecian y al escaso coste computacional, sin embargo, gracias a importantes mejoras en sus algoritmos de correspondencia, tanto a nivel de optimización como de restricciones de la función objetivo [6, 4, 7], la reconstrucción densa fue desplazando a las técnicas de reconstrucción dispersa en los rankings de los mejores algoritmos de reconstrucción[8, 58]. En el campo de la reconstrucción densa,se desarrollaron métodos de optimización para el cálculo de disparidades deterministas como el ICM[9],métodos cooperativos[10, 11] o métodos heurísticos basados en correspondencias línea a línea como Dynamic programming[12, 13, 14, 15, 16] así como aquellos basados en Markov Random Fields, con optimizaciones por graph cuts[6, 17], belief propagation[18], simulated annealing[19, 20, 21] o tree reweighted message passing[22, 23]. Un estudio más exhaustivo de cada uno de estos métodos y su comparación se encuentra en [24]. Por otro lado, el tratamiento de las imágenes de entrada utilizadas en la optimización de manera más eficiente por parte de Birchfield y Tomasi [25] permitió obtener resultados de una calidad sorprendente; aunque otros estudios también fueron dirigidos en esta misma dirección, como aquellos realizados por Matthies et al.[26] o Tian and Huhns [27], que pretendían ir un paso más allá de la simple diferencia de intensidad de los pixeles para hallar el mapa de disparidades. Uno de los grandes problemas a los que tuvo que hacer frente la visión artificial en este campo fue el manejo de discontinuidades, que se producen en aquellas zonas en las que hay un salto de intensidad debido a bordes o cambios de profundidad, y oclusiones, que son aquellos puntos en una imagen que no se encuentran visibles en la imagen estéreo

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

30

I. M EMORIA § 2. R ECONSTRUCCIÓN 3D

correspondiente. En cuanto a la mejora del cálculo de disparidades en las discontinuidades, existe gran cantidad de literatura, entre la que destaca las funciones del término smooth que preservan la discontinuidad como la función de Potts[28] o funciones truncadas[29]. El tratamiento de las oclusiones también fue abordado, tanto en esta época como en la posterior, con importantes contribuciones como la de Zitnick and Kanade[30],Ishikawa and Geiger[31] o Kolmogorov and Zabih[32]. Por último, cabe destacar la importancia que han adquirido las técnicas de post procesado del mapa de disparidades, que han permitido disminuir el error cometido en la reconstrucción de la escena realizando cada vez un mapeo más insensible a oclusiones y discontinuidades. El método meanshift[33, 34], permite segmentar la imagen de manera que los objetos dentro de la misma queden claramente definidos y permitan la interpolación de los puntos erróneos a partir de aquellos conocidos y considerados como válidos. Algoritmos como el desarrollado en [29] por han logrado resultados muy satisfactorios con el empleo de esta técnica. Se han aplicado también métodos de estimación de subpíxeles al mapa de disparidades deducido[35] así como filtros que mejoran considerablemente la calidad de la solución. En conclusión, el estudio de la reconstrucción tridimensional es un problema que continúa en vigencia y para el que se han estudiado multitud de métodos, donde se ha conseguido un avance muy importante en la técnica debido fundamentalmente al esfuerzo por parte de la comunidad investigadora de compartir resultados y crear un estándar que permita valorar la eficacia de los nuevos algoritmos propuestos frente a la literatura ya existente.

2.4.2.

Métodos locales

Son métodos que aplican restricciones a un pequeño número de píxeles alrededor del pixel de estudio. Suelen ser muy eficientes pero sensitivos a las ambigüedades locales de las regiones tales como oclusiones, regiones sin textura o textura repetitiva. Dentro de este grupo se encuentran los métodos basados en área y basados en características, así como los basados en la optimización del gradiente. 2.4.2.1.

Métodos basados en el área. Correlación de área.

Estos métodos consideran las dos imágenes captadas como una escena bidimensional trasladada. Para cada pixel de una imagen se define una ventana y se calcula la

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

31

I. M EMORIA § 2. R ECONSTRUCCIÓN 3D

correlación entre la distribución de disparidad en la misma frente a la que existe en una ventana en la otra imagen, que está centrada en el pixel bajo estudio. El método consiste en encontrar el pixel con una ventana que presente una distribución de disparidad análoga a la de la otra imagen. Este proceso se simplifica enormemente cuando se establece una geometría epipolar, de manera que la búsqueda del pixel correspondiente se limita a una sola línea.

Figura 13. Técnicas de correlación de área más comunes[44] En la Figura 13 se observan los métodos de reconstrucción 3D basados en área más comunes. 2.4.2.2.

Métodos basados en características

Consisten en la determinación de los puntos más característicos de la imagen, que van desde superficies, bordes o esquinas, etc. Los métodos basados en características recibieron especial atención en los años ochenta, debido a su eficacia. Sin embargo, dada la necesidad de obtener mapas densos de disparidad, estas técnicas se han ido abandonando en los últimos años.

2.4.3.

Métodos globales

Son métodos que aplican restricciones a la imagen completa. Suelen ser menos sensitivos a las peculiaridades locales ya que realizan el cálculo de las disparidades de manera global, sin embargo, suelen ser computacionalmente costosos. El objetivo de los métodos globales es encontrar la disparidad que minimice la función de energía global. E(d) = Edata (d) + λEsmooth (d)

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

32

I. M EMORIA § 2. R ECONSTRUCCIÓN 3D

La ecuación de optimización lleva asociadas ciertas restricciones que deben ser consideradas a la hora de resolver el problema. Las restricciones más básicas son: Restricción epipolar: Un punto y su correspondiente en la otra imagen se encuentran situados sobre la misma horizontal. Restricción del orden: Los puntos correspondientes entre dos imagen tienen que guardar siempre el mismo ordena relativo sobre la línea epipolar. Esto no se cumple en el caso de que existan objetos estrechos situados a distancias diferentes ya que no existe continuidad de superficie. Límite del gradiente de disparidad: Esta restriccoón impone límites en las tangentes de las superficies del objeto, que deben ser bastante pequeñas, es decir, impone una restricción sobre la forma de los objetos que pueden ser reconstruidos por visiçon estéreo. Restricción de unicidad: Para cada punto de la imagen existe un único punto correspondiente en la otra imagen. Siempre que no haya objetos semitransparentes en la imagen, esta condición se cumple. En los casos en que existen puntos ocluidos, éstos no tendrán correspondencia mientras que si no existen puntos ocluidos la correspondencia será bidireccional entre las dos imágenes. Restricción de continuidad: Los objetos se consideran como superficies continuas presentando disparidades únicamente en los bordes de separación con otros objetos. La continuidad en la superficie también implica continuidad en los mapas de disparidades. Dada la importancia que han adquirido estos métodos en los últimos años, principalmente debido a la necesidad de determinar mapas de disparidades densos, el proyecto se centrará en los métodos globales como medio de resolución del mapeo tridimensional de la escena [Véase capítulo 3 de la memoria].

2.5.

Reconstrucción

Una vez determinado el mapa de disparidades de la imagen se debe proceder al cálculo de profundidades real de la imagen. Para ello hay que realizar un proceso inverso al que ya se explicó con la calibración. El proceso de obtener un punto tridimensional a partir de sus proyecciones en las imágenes se denomina triangulación. Para poder llevarse a cabo es necesario conocer los puntos correspondientes en las dos imágenes y los parámetros de calibración de Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

33

I. M EMORIA § 2. R ECONSTRUCCIÓN 3D

la cámara, de esta manera, la intersección de la Figura 10 sería trivial. Sin embargo, existen errores asociados a la resolución de la cámara de manera que la intersección perfecta entre los puntos correspondientes y sus focos no siempre se da. A continuación se detallan dos métodos de triangulación que permiten eliminar este tipo de errores. Método del Punto Medio: Este método busca el punto medio geométrico entre ambos rayos.

Figura 14. Método del punto medio

Este método es útil en reconstrucciones euclídeas pero arroja unos resultados erróneos si la colocación de las cámaras no es simétrica ya que el punto medio no sería la mejor solución. Método lineal:Es un método basado en las matrices de los parámetros de las cámaras. Este método presenta varias desventajas, entre las que se encuentra que el modelo no tiene un significado geométrico para el problema y que se trata de un modelo poco robusto ya que trata los parámetros de la cámara con un determinado peso totalmente arbitrario, de manera que si se cambia este peso, cambiará la solución de la reconstrucción. Método polinomial: En este caso se emplea un método de optimización para obtener la intersección de las dos rectas que pasan por los puntos y sus focos. Partiendo de la idea de que los píxeles que se desean triangular no interceptarán en el espacio, se debe encontrar el píxel más cercano a p1 en la imagen izquierda y a p2 en la imagen derecha que cumpla con larestricción epipolar.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

34

Capítulo 3 Métodos globales de optimización métodos globales calculan el mapa denso de disparidades a partir de la imposición de restricciones a una función objetivo llamada función de energía global que debe ser minimizada. Esta ecuación viene dada por:

L

OS

E(d) = Edata (d) + Esmooth (d) donde el término Edata mide la semejanza entre los puntos que se hacen corresponder entre la imagen izquierda y la derecha de la escena. La correlación entre estos dos píxeles se suele realizar de forma general a partir de la diferencia de intensidades de color entre los mismos. El parámetro Esmooth modela la suavidad dentro del mapa de disparidades, intentando asignar una disparidad similar a los puntos que se encuentran situados dentro de un mismo vecindario, imponiendo una coherencia en todas las direcciones y no sólo en la de la línea epipolar. Este tipo de métodos han tenido un importante desarrollo en los últimos años, debido fundamentalmente a que ofrecen mejores resultados que todos las aplicaciones que emplean métodos locales, donde las correspondencias se establecen entre regiones específicas a través de ventanas que van recorriendo la imagen y no para todo el conjunto de la escena a la vez como hacen los métodos globales. El mayor inconveniente que presentan los métodos globales frente a los locales es su mayor coste computacional, es por ello que no fueron utilizados desde un principio en aplicaciones de visión artificial en tiempo real, aunque actualmente este inconveniente se ha visto mitigado gracias a la aparición de sistemas de cálculo mucho más rápidos que aquellos con los que se contaba hace tan solo unos años. Los métodos que se han ido desarrollando para realizar la optimización de la función objetivo se dividen en deterministas y heurísticos o probabilísticos. A continuación se

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

35

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

mostrarán ejemplos de cálculo para cada una de estas técnicas y ejemplos con distintas imágenes.

3.1.

Métodos deterministas

3.1.1.

Iterated conditional models

Los métodos deterministas fueron los primeros en implementarse. En ellos, el cálculo de las disparidades es muy sencillo. En primer lugar, se realiza una estimación de las etiquetas que presentan cada uno de los pixeles en la imagen. A continuación, para cada pixel, se elige la etiqueta que de como resultado la mayor disminución de la función objetivo y el proceso se repite hasta que el sistema converja. El modelo fue propuesto por Besag[9] en 1986 como alternativa a los modelos probabilísticos que se usaban en la época con gran dificultad. (k)

Sean d los datos iniciales de las imágenes derecha e izquierda y fS−i las etiquetas para las distintas disparidades, el algoritmo se encarga de actualizar secuencialmente (k) (k+1) el valor de fi a fi de manera que se maximice la probabilidad condicional a posteriori P (fi |d, fS−i ) de que la etiqueta sea correcta. Se asumen dos hipótesis para el cálculo de P (fi |d, fS−i ). En primer lugar, se debe cumplir que las muestras d1 , ...., dm sean independientes y que cada di tenga la misma función de densidad de probabilidad p(di |fi ) en función de las etiquetas. Por lo tanto, p(d|f ) =

Y

p(di |fi )

La segunda hipótesis que debe cumplirse es que f depende sólo de las etiquetas que presenten los puntos del vecindario. A partir de estas dos hipótesis se puede plantear el teorema de Bayes como sigue: P (fi |d, fS−i ) ∝ p(di |fi )P (fi |fℵi ) (

Donde P (fi |di , fℵi k)) es mucho más fácil de maximizar que P (f |d). Por otro lado, maximizar la ecuación anterior corresponde a minimizar: (k+1)

fi

(k)

← argminfi V (fi |di , fℵi )

donde (k)

V (fi |di , fℵi ) =

X

(k)

V (fi |ffi0 ) + V (di |fi )

i0 ℵi

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

36

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

Para el cálculo de las etiquetas de manera discreta, V (fi |di , fℵi ) se evalua para cada fi y (k+1) la etiqueta con el menor valor de V (fi |di , fℵi ) es elegida para fi . Estas iteraciones continuarán hasta que la solución converja. La mayor desventaja de este método es que es muy sensible a las estimaciones iniciales, y requiere grandes recursos. A continuación se muestra en la figura 15 la actuación del algoritmo ICM para la imagen tsukuba con una función de energía muy sencilla que emplea la medida de similitud de Birchfield y Tomasi [25] para el cálculo de disparidades.

Figura 15. a) Mapa de disparidades real b)Mapa de disparidades obtenido con ICM Se observa que el método no produce un mapa de disparidades muy bueno, por lo que se prefiere el uso de los métodos heurísticos o probabilísticos para el cálculo del mapa de disparidades denso de una escena debido a su gran eficacia.

3.2.

Métodos probabilísticos

Los métodos probabilísticos intentan conocer con un cierto nivel de certeza la probabilidad de que un evento se produzca. En el caso de la determinación de las correspondencias, los métodos probabilísticos se encargan de determinar la probabilidad de que la correspondencia entre un píxel en la imagen izquierda y otro en la derecha sea correcta. Dentro del campo de la visión estéreo todos los métodos probabilísticos empleados están basados en probabilidad bayesiana y se pueden dividir en dos categorias, por un lado los métodos basados en programación dinámica y por otro aquellos basados en campos aleatorios de markov.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

37

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

3.2.1.

Programación dinámica

Existen determinados problemas cuyas soluciones pueden ser expresadas recursivamente en términos matemáticos, y que presentan como método de resolución más intuitivo la aplicación de un algoritmo recursivo. Sin embargo, el tiempo de ejecución de la solución recursiva crece generalmente de forma exponencial y por lo tanto la resolución mediante estos sistemas resulta impracticable. Para mejorar el tiempo de resolución de este tipo de problemas la programación dinámica se perfila como uno de los métodos más efectivos. Por otro lado, en aquellos problemas donde se usa un método recursivo de resolución, dividiendo el problema incial en subproblemas y calculando independientemente cada una de sus soluciones para luego combinarlas y obtener así la solución final por combinaciones de las soluciones parciales, podrían darse resultados erróneos si finalmente los subproblemas no fueran independientes entre sí. Ante esta situación, la única solución posible sería la aplicación de un algoritmo de programación dinámica, que resolvería todos los subproblemas de una sola vez. El uso más extendido de la programación dinámica se da en la resolución de los problemas de optimización ya que en este tipo de problemas se pueden presentar distintas soluciones, cada una con un valor, y lo que se desea es encontrar la solución de valor óptimo. La resolución en este tipo de casos se basa en el principio de óptimo, enunciado por Bellman en 1957: En una secuencia de decisiones óptima toda subsecuencia ha de ser también óptima. Este principio no es siempre cierto, por lo que se deberá verificar para cada problema la validez del mismo. Para que un problema pueda ser abordado por esta técnica se deben cumplir dos condiciones: La solución al problema ha de ser alcanzada a través de una secuencia de decisiones, una en cada etapa. Dicha secuencia de decisiones ha de cumplir el principio de óptimo. De forma general, los pasos que debe seguir un algoritmo de estas características son: 1. Planteamiento de la solución como una sucesión de decisiones y verificación de que ésta cumple el principio de óptimo.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

38

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

2. Definición recursiva de la solución. 3. Cálculo del valor de la solución óptima mediante una tabla en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos. 4. Construcción de la solución óptima haciendo uso de la información contenida en la tabla anterior. Para el caso concreto que nos ocupa de la reconstrucción tridimensional de una escena a partir del establecimiento del mapa de correspondencias, la función objetivo se plantea para cada una de las líneas epipolares que forman la imagen, también llamadas scanlines y se resuleven todas las funciones de energía a la vez por programación dinámica. La resolución de las disparidades se realiza en este caso buscando el camino de coste mínimo que se establece en una matriz que contiene todas las posibles correspondencias entre una scanline de la imagen izquierda y la scaline correspondiente a la imagen derecha, se puede observar un ejemplo en la Figura 16 sacado del trabajo de D. Scharstein y R. Szeliski [8].

Figura 16. Correspondencia estéreo usando programación lineal. Para cada par de scanlines correspondientes, se minimiza el camino por el que las correspondencias se establecen. Las minúsculas (a, k) simbolizan las intensidades dentro de cada scanline mientras que las mayúsculas representan el camino seleccionado dentro de la matriz. Las correspondencias se han señalado como M mientras que los puntos ocluidos se representan como L (si la oclusión presenta un punto visible sólo en la imagen izquierda) o R(si la oclusión presenta un punto visible sólo en la imagen derecha). Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

39

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

Los algoritmos de programación dinámica se basan en la asunción de preservación de orden en los bordes de un par estereoscópico de imágenes (que puede no cumplirse si dentro de la imagen se encuentran objetos muy estrechos) y en el teorema de unicidad, es decir, a un punto en la imagen izquierda sólo le puede corresponder otro punto en la imagen derecha.

3.2.2.

Markov Random Fields

Los campos aleatorios de markov proporcionan medidas de probabilidad sobre un dominio de definición que presente relaciones de tipo espacial o temporal. El conjunto de posiciones donde se define el campo va a denominarse malla o rejilla y se va a denotar por el conjunto S, en el caso de la resolución de las correspondencias mediante técnicas de optimización, el conjunto S representa una matriz con todos los píxeles de la imagen. Para cada posición sS se define un espacio de estados ∧s donde s representa cada uno de los píxeles en la imagen y el espacio de estados ∧s los niveles de disparidad asociados al pixel. Con xs ∧s se va a denotar un valor de la disparidad concreto para uno de los píxeles s de la imagen y Ω = (∧s )sS será el espacio de todas las posibles configuraciones. Por otro lado, con x = (xs )sS se denotará una configuración particular. Se va a suponer que todos los espacios y configuraciones son finitos. Además, si todos los píxeles tienen el mismo rango de disparidades, se dice que el espacio Ω es homogéneo. En los campos aleatorios de markov o CAM se define la medida de la probabilidad Q o distribución de probabilidad (x) ≥ 0 en el espacio de configuraciones Ω, para cada xΩ como: XY (x) = 1 xΩ

Y si se define suceso E ⊂ Ω como un conjunto de configuraciones entonces la probabilidad de ese conjunto vendrña dada por : Y XY (E) = (x) xE

Igualmente, se pueden definir subconjuntos A ⊂ S del espacio de defición S, que corresponden a subimágenes dentro de la imagen principal donde ΩA = (∧s )sA corresponde al espacio de configuraciones de la subimagen, xA = (xs )sA corresponde a una subimagen particular y la probabilidad de este subespacio es igual a la probabilidad marginal. Se denotan X, XA yXs como las variables aleatorias correspondientes a los

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

40

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

espacios Ω, ΩA yΩs respectivamente. Se dice que un campo definido en la malla S con espacio de configuraciones Ω Q ymedida de probabilidad asociada es un campo aleatorio o estocástico si para todo Q xΩ se cumple que (x) ≥ 0, es decir, si la distribución o medida de probabilidad cumple la condición de positividad. Esto quiere decir, en el caso que nos ocupa, que todos los valores de disparidades son posibles para un pixel. Una característica fundamental de los campos de markov es su definición de vecindario y las medidas locales que van asociados a ellos. Para un CAM se puede definir una probabilidad condicionada llamada característica local del campo, que viene definida para A ⊂ S como: Y (XA = xA /XS/A = xS/A ) Esta probabilidad, en el caso del problema de correspondencias, equivale a la probabilidad de que una determinada subimagen dentro de la imagen principal presente un cierto valor condicionada al valor que tome el resto de la imagen. Estas dependencias van a ser en general locales, esto quiere decir que el valor de disparidad de un pixel va a depender de los píxeles ceranos por lo que se definirá para cada posición sS un conjunto δ(s) ⊂ S, que corresponde a las posiciones de S de las que s depende. Los elementos de δ(s) se denominan vecinos de s. La colección de conjuntos δ = δ(s) : sS se denomina sistema de vecindario o vecindario de la malla S. Un sistema de vecindario debe cumplir dos propiedades: Que s no sea vecino de sí mismo s∈ / δ(s) Que si s es vecino de t, t también sea vecino de s sδ(t) ←→ tδ(s) En general, los sistemas de vecindario son homogéneos. Esto quiere decir que sabiendo los vecinos de una posición s se puede saber cuáles son los vecinos de otra posición t desplazando a t el sistema de vecinos de s. Se puede decir que son invariantes en el espacio. Los sistemas de vecinos que se comportan de la misma forma en todas las direcciones del espacio se denominan isótropos.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

41

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

En la imagen 17. se pueden observar algunos vecindarios de distinto orden. el punto negro representa el píxel s y los blancos son los píxeles vecinos t. Como la imagen tiene dimensiones finitas, los vecindarios en los bordes de las imágenes no pueden ser iguales que aquellos definidos para el interior de la imagen, sin embarg, se sigue manteniendo el concepto de homogeneidad suponiendo implícitamente el efecto de los bordes.

Figura 17. Vecindarios de órdenes 1,2,4,5 y 8 Se dice que un campo aleatorio es de Markov con respecto al vecindario δ si para todo xΩ Y Y (Xs = xs /Xr = xr , r 6= s) = (Xs = xs /Xr = xr , rδ(s)) con s, rS. Existen dos enfoques fundamentales para establecer la probabilidad de un campo aleatorio de Markov: En términos de probabilidades condicionales P =

Y (Xs = xs /Xr = xr , rδ(s))

con s, rS. En términos de la probabilidad conjunta de una subimagen P =

Y (XA = xA )

con AS. Una forma de estimar la probabilidad conjunta, es mediante una analogía entre los CAM y los Campos Aleatorios de Gíbbs (CAG). La distribución de Gibbs viene dada por: 1 −U (f ) P (f ) = e( ) z T donde Z es una constante de normalización igual a Z = Zf F e(

−U (f ) ) T

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

42

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

U(f) se conoce como la función de energía y se obtiene como la suma de los potenciales de todos los conjuntos A: X U (f ) = VA (f ) xA

Y T es una constante que se llama temperatura que generalmente se puede asumir igual a uno. La configuración más probable que estamos buscando corresponde a la de energía mínima. Para una vecindad de primer orden, se puede demostrar que en campo aleatorio de Markov y un campo aleatorio de Gibbs son equivalentes, por lo que se puede expresar la probabilidad conjunta en función de los potenciales de los vecindarios. Estos potenciales constituyen el conocimiento a priori del problema. Se puede usar el campo aleatorio de Markov para obtener el valor más probable de una configuración dada la información anterior a través del teorema de Bayes: PF/G (f ) = kPF (f )PF/G (f ) Donde el primer término representa la información a priori y el segundo término la información obtenida. La información conjunta obtenida vendrá dada entonces por el producto de las probabilidades de las vecindades: PF/G (f ) = k

Y

PA

A

Que se puede expresar como una suma (CAG) tomando logaritmos: PF/G (f ) =

1 (−Up (f )) e Z

Y en el caso de una vecindad de primer orden: Up (f ) =

X A

VA (f ) + λ

X

Vo (f )

o

Vc corresponde a la información del dominio dada por los vecinos y Vo corresponde a la información de las observaciones; λ es una constante que da el peso relativo entre ambas. Bajo este enfoque, la solución a un problema particular corresponde en encontrar la configuración del CAM de mayor probabilidad o de energía mínima. La función que se logre depende de la forma de las funciones para Vc y Vo .

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

43

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

3.2.2.1.

Belief propagation

El Belif propagation es un algoritmo que se utiliza para conocer la combinación de estados más probable en los nodos de una red de un campo aleatorio de Markov. Se trata de un método iterativo que minimiza la energía transmitiendo mensajes entre los nodos vecinos, en cada iteración, unos nodos se encargan de recibir y otros de emitir mensajes de manera que el proceso termina cuando la solución al problema no cambia independientemente de que se sigan enviando más mensajes. Existen dos tipos de nodos, los nodos observables y los ocultos. Los primeros son aquellos en los que su estado es conocido y los según aquellos que aún quedan por conocer. La función de distribución local φi (xi , yi ), donde xi son los nodos de estado desconocido e yi aquellos con estado conocido, permite expresar la función de distribución conjunta de los nodos ocultos como: p(x) =

Y 1Y ψij (xi , xj ) φi (xi ) Z ij i

(1)

Por otro lado, se definen los mensajes que envían el nodo oculto i al nodo oculto j como mij (xj ). Éstos contienen información del posible estado que debería tener j, de modo que el mensaje es proporcional a la probabilidad de que el nodo i piense que el nodo j estará en ese estado a partir de la información de la que dispone. En los algoritmos de Belief Propagation también existe una función de confianza llamada bi (xi ) proporcional al produco de la función local en ese nodo Q kφi (xi ) jℵ(i)mij (xi ) y a todos los mensajes que el nodo i recibe de sus vecinos: bi (xi ) = kφi (xi )

Y

mij (xi )

(2)

jℵ(i)

Donde k es una constante que permite la normalización de la ecuación y ℵ(i) consitutuye el vecindario de i. A partir de todas las definiciones anteriores, se puede proceder al método de transmisión de mensajes del algoritmo. El algoritmo que se va a desarrollar es una versión estándar del Belief propagation del que existen multitud de variantes. En este caso se trata del modelo más sencillo, denominado suma-producto, a partir del cual se consiguen encontrar las probabilidades marginales para todos los nodos.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

44

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

Los mensajes se actualizan a partir de la siguiente regla de actualización: mij (xi ) ←−

X

φi (xi )ψij

xi

Y

mki (xi )

(3)

kℵ(i)/j

Es decir, se toman todos los nodos entrantes excepto el que viene de j. Del cálculo de confianzas sobre un nodo se deduce que la función confianza proporciona probabilidades marginales exactas para todos los nodos de una red aleatoria de markov completamente conexa, es decir, no deben existir bucles sino un único camino entre dos nodos cualesquiera. Para un cálculo sobre una red, se procedería en primer lugar cono los nodos en el límite del gráfico y se calcularía el mensaje cuando se tienen disponibles todos los mensajes necesarios. De manera general los mensajes sólo deben ser calculados una vez para gráficos completamente conexos por lo que el tiempo de cálculo del algoritmo será directamente proporcional al número de nodos y no crecerá exponencialmente como hacen los métodos de cálculo de probabilidades marginales tradicionales. Se define la probabilidad marginal pij (xi , xj ) de los nodos i, j obtenida al marginalizar la función de distribución conjunta sobre cada nodo excepto la de los nodos i y j. X pij (xi , xj ) = p(z) (4) z:zij =(xi ,xj )

A partir de esta probabilidad marginal, se puede establecer la función de confianza de dos nodos de manera análoga a como se hizo para la ecuacion 2) en un solo nodo: bij (xi , xj ) = kψij (xi .xj )φi (xi )φj (xj )

Y

mki (xi )

kℵ(i)/j

Y

mij (xj )

(5)

iℵ(i)/i

Combinando las ecuaciones 2) y 4) se obtiene la regla de actualización de mensajes: bi (xi ) =

X

bij (xi , xj )

(6)

xj

Todas estas funciones no llevan explícito el uso de una determinada configuración de la red, sin embargo, la utilización de una red no conexa podría provocar que el mensaje circulara indefinidament epor el bucle de manera que el algoritmo no pudiese converger. Para encontrar los estados más probables de los nodos, se ejecuta el algoritmo y se obtiene las probabilidades marginales de cada nodos y entonces de forma sucesiva para cada distribución marginal se busca el valor x0i que maximiza la probabilidad individual.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

45

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

El problema que se plantea en este momento es el de encontrar los valores conjuntos que presentan una mayor probabilidad, que de forma general no coinciden con los valores máximos individuales de la distribución marginal. El correspondiente valor de la distribución conjunta vendrá dado por: p(xmax ) = maxx p(x) Para obtener los estados de los nodos que conjuntamente tienen mayor probabilidad, la actualización de mensajes se debe reemplazar por: mji (xj ) ←− m´ax φi (xi )ψij (xi , xj ) xj

Y

mki (xi )

kℵ(i)/j

Esta expresión corresponde al algoritmo max-producto, que se obtiene de la actualización de mensajes para el algoritmo suma-producto y remplazando los sumatorios por maximizaciones. Aunque el estandar que se acaba de definir es perfectamente aplicable, resulta computacionalmente muy costoso por lo que la aplicación directa del algoritmo se da muy pocas veces, en su lugar, se realizan simplificaciones que reducen considerablemente el tiempo de cálculo. En las figuras 18 y 19 se muestran algunos ejemplos obtenidos de la aplicación de métodos Belief Propagation simplificados con término Ed ata de cálculo de similitud píxel a píxel [25] para la imagen tsukuba.

Figura 18. Mapa de disparidades real a la izquierda y resultado obtenido aplicando BP de Max-producto

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

46

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

Figura 19. Mapa de disparidades real a la izquierda y resultado obtenido aplicando BP de suma-producto

3.2.3.

Graph cuts o Corte de grafos

Este tipo de algoritmos trata de encontrar el corte óptimo del grafo que constituye la red markoviana generada a partir de los datos de la imagen. Este método no es exclusivo de la visión estéreo sino que puede ser empleado para todos aquellos problemas en los que se requiera minimizar la función de energía, que debe ser igual a maximizar la estimación de la solución a posteriori. Los problemas binarios pueden ser resultos gracias a este método de manera exacta, si bien aquellos que no lo son, como es el caso de las correspondencias en estéreo, presentan una solución aproximada a través de este algoritmo que en muchas ocasiones es suficientemente buena. La teoría de los graph cuts fue implementada por primera vez en visión artificial por Greig, Porteous y Seheult[50], de la Universidad de Durham, aplicandolo sobre imagenes binarias sobre las que se pretendía suavizar el ruido de imágen de mala calidad. Al tratarse de imagenes binarias, la aplicación del algoritmo produjo una solución exacta. Además del inconveniente de que las imágenes deben ser binarias para presentar una respuesta exacta, los álgoritmos graph cuts sólo son aplicables en el campo de las correspondencias estéreo cuando las funciones de energía tienen un término Es mooth llamado métrico o semimétrico. Se entiende por término semimétrico el que cumple: V (α, β) = V (β, α) ≥ 0 V (α, β) = 0 ⇐⇒ α = β Además de la condición anterior, un término métrico cumple: V (α, β) ≥ V (α, γ) + V (γ, β)

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

47

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

Existen dos procedimientos para abordar el problema de correspondencia a través de graph cuts. Por un lado existen los algoritmos de expansión y por otro los de intercambio. A continuación se detallarán los pasos que siguen cada uno de ellos y se mostrarán algunos ejemplos obtenidos con las imágenes tsukuba. Algoritmo de intercambio α − β En este caso tenemos dos etiquetas o disparidades α y β asociadas a dos pixels distintos. El método consiste en intercambiar los pixeles etiquetados como α por los β y viceversa de manera que disminuya la función de energía. El algoritmo se resume en los siguientes pasos: 1. Comenzar con una etiqueta arbitraria f 2. Establecer éxito= 0 3. Para cada par de etiquetas α y β a) Encontrar f 00 = argminE(f 0 ) siendo f 0 el valor de la etiqueta al producir un único intercambio entre α y β b) Si E(f 00 ) ≤ E(f ) entonces establecer f = f 00 y éxito= 1 4. Si éxito= 1 volver al paso 2 5. Devolver el resultado final de la etiqueta f Para calcular el mínimo en el paso 3, se realiza un gráfico con tantos nodos como pixels unidos entre ellos si son vecinos y unidos a las dos posibles etiquetas α y β. Cada una de las ramas que se forman tienen un peso igual al término data y/o al término smooth de la función de energía, que va variando en cada iteración. Por lo tanto, para hallar el valor de la función de energía mínima, se debe realizar un corte del grafo mínimo. A continuación se muestra en la figura 20 los resultados obtenidos de la aplicación de este algoritmo a la imagen tsukuba.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

48

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

Figura 20. Mapa de disparidades real a la izquierda y resultado obtenido con algoritmo de intercambio de etiquetas Algoritmo de expansión α El método es análogo al anterior pero variando un poco la estructura del gráfico. En este caso no se trata de un intercambio de etiquetas o disparidades sino de un aumento del número de píxeles que presentan la etiqueta α, de manera que disminuya la función de energía. El algoritmo se resume en los siguientes pasos: 1. Comenzar con una etiqueta arbitraria f 2. Establecer éxito= 0 3. Para cada par de etiquetas α a) Encontrar f 00 = argminE(f 0 ) siendo f 0 el valor de la etiqueta al producir una única expansion de α b) Si E(f 00 ) ≤ E(f ) entonces establecer f = f 00 y éxito= 1 4. Si éxito= 1 volver al paso 2 5. Devolver el resultado final de la etiqueta f Para calcular el mínimo en el paso 3, se realiza un gráfico con tantos nodos como pixeles, unidos entre ellos si son vecinos y unidos a las dos posible etiquetas α y α. Además, en este caso también se añade un nodo ’a’ si las etiquetas entre dos pixels adyacentes son diferentes, uniendo dicho nodo a los otros dos y al que forma α. Cada una de las ramas que se forman tienen un peso igual al término data y/o al término smooth de la función de energía que va variando en cada iteración. Se deberá hallar, como en el caso anterior, el corte del grafo mínimo. Se puede observar en la Figura 21 un ejemplo del resultado que se obtiene de la utilización de este algoritmo. Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

49

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

Figura 21. Mapa de disparidades real a la izquierda y resultado obtenido con algoritmo de expansión de etiquetas

3.2.3.1.

Recocido simulado

El recocido simulado o simulated annealing (SA) es una de las técnicas metaheurísticas más clásicas. Se basa en el estudio realizado por Metropolis en el campo de la termodinámica estadística, que intentaba modelar el proceso de recocido del acero, una técnica que consiste en calentar y luego enfriar controladamente un material para aumentar el tamaño de sus cristales y reducir sus defectos. El calor causa que los átomos se salgan de sus posiciones iniciales, que constituyen los puntos de energía mínima, y se muevan aleatoriamente. Si el enfriamiento es lento, les da mayores probabilidades de encontrar configuraciones con menor energía que la inicial. A principios de los 80, publicaciones independientes demostraron cómo el proceso puede ser aplicado en problemas de optimización, asociando los elementos del proceso del recocido a aquellos de optimización combinatoria. El algorimto que rige este proceso es relativamente sencillo. Para el caso de la resolución de correspondencias, la función objetivo a minimizar es considerada como la energía de los átomos. El algoritmo no podrá aceptar únicamente los cambios de configuración o etiquetas que reduzcan el valor de la función objetivo, ya que en ese caso, se está intentando enfriar demasiado rápido, de temperaturas muy altas a temperaturas prácticamente nulas. Para decrementar la temperatura lentamente, se intentará pasar el suficiente tiempo en cada una de las configuraciones para que el sistema alcance su estado constante. En cada paso, se le da a un átomo un pequeño desplazamiento aleatorio, pasando de E1 a E2 como sigue: δE = (E2 − E1 )

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

50

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

El cambio resultante en la energía será entonces calculado como: ( P (δE) =

1

) e( −δE kT

si δE ≤ 0 si δE > 0

Si P (δE) = 1, el desplazamiento es aceptado y utilizado como el punto de inicio del siguiente paso o bien si se genera un número aleatorio uniformemente distribuido en (0,1) y ese número es menor que P (δE) entonces se acepta la nueva configuración y se utiliza en el paso siguiente. Típicamente este paso se repite hasta que se alcanza un estado suficientemente bueno para la aplicación o hasta que se cumpla cierto tiempo computacional dado.Si el proceso se repite un número suficiente de veces, el sistema evoluciona a una distribución de Boltzmann. Una cualidad importante del método SA es que la probabilidad de transición P (δE) es siempre distinta de cero, aún cuando δE sea positivo, es decir, el sistema puede pasar a un estado de mayor energía(peor solución) que el estado actual. Esta cualidad impide que el sistema se quede atrapado en un óptimo local. Por otro lado, varios estudios teóricos demuestran que si la temperatura decrece lo suficientemente lenta, el proceso converge a la solución óptima. Sin embargo, una función de reducción de la temperatura que garantizase esa convergencia al óptimo global, requeriría unos tiempos de cálculo prohibitivos. Por lo tanto, este método no suele ser aplicado en los métodos de correspondencia estéreo sino que se utilizan métodos simplificados de éste que utilizan menores tiempos de cálculo, entre ellos cabe destacar el Mean field annealing, que es un simplificación de Simulated annealing que calcula el óptimo de la imagen por métodos deterministas. 3.2.3.2.

Graduated non convexity algorithm(GNC)

Es una técnica de optimización global que trata de resolver un problema de optimización complicado resolviendo inicialmente un problema simplificado a través del método de recocido simulado y que transforma poco a poco el problema hasta llegar a una configuración igual al problema inicial de mayor dificultad. Se usa para problemas continuos no convexos, es decir, sólo sirve para funciones de energía muy específicas. 3.2.3.3.

Tree reweighted message passing (TRW)

En los últimos años, un nuevo algoritmo ha sido introducido por Wainwright et al [51] para la minimización de la función de energía denominado max-product treereweighted message passing (TRW). Es un método similar al Belief propagation, en

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

51

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

este caso el grafo se divide en ramas como se muestran en la Figura 22 .

Figura 22. Cálculo de las ramas en TRWS Se aplica el algoritmo BP sobre cada figura, se determina el belief vector(suma del término data y los mensajes de los vecinos) del pixel que se está estudiando y se calcula la media del belief vector del pixel en cada una de las ramas. Este método ha dado muy buenos resultados en estudios comparativos realizados sobre Graph cuts, Belief propagation e ICM y tiene la ventaja de que aplicando un orden específico sobre las operaciones y las ramas del gráfico, se puede conseguir que el algortimo converja siempre. En tiempos inferiores a los empleados en un método Belief Propagation simple. En la Figura 23 se muestra el mapa de disparidades de la imagen tsukuba empleando el método de optimización TRWS.

Figura 23. En el lado izquierdo de la imagen se observa el mapa de disparidades real de tsukuba, en el lado derecho el resultado obtenido de la aplicación de TRWS

3.3.

Métodos cooperativos

Los algoritmos cooperativos se encuentran inspirados en los modelos de visión estéreo humanos. Estos algoritmos actúan de forma local sobre los píxeles de la imagen pero usan operaciones no lineales que producen un comportamiento similar al de los algorítmos globales de optimización.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

52

I. M EMORIA § 3. M ÉTODOS GLOBALES DE OPTIMIZACIÓN

Dado el poco desarrollo que han presentado este tipo de algoritmos en el campo de la visión artificial, se ha prescindido de su estudio centrándonos únicamente en métodos globales, que presentan una gran eficiencia en sus resultados.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

53

Capítulo 4 Preprocesamiento de imágenes tratamiento de las imágenes en una etapa anterior a la aplicación del método de optimización elegido es una técnica muy utilizada en el ámbito de la visión artificial. Este tipo de técnicas permiten aportar información adicional al proceso de reconstrucción; además permiten que el número de parámetros que deban ser seleccionados así como el número de datos que maneje el proceso sean lo más reducidos posibles.

E

L

Sus objetivos son múltiples, por un lado, se pretende que la imagen quede lo más libre posible de ruidos de manera que la etapa de correspondencias sea más eficaz y se consiga un buen mapa de disparidades. Por otro lado, gracias a las técnicas de preprocesado se consiguen imágenes con el brillo y la iluminación necesarias para su correcto manejo, así como detecciones del contorno de la escena que se precisan en etapas posteriores del algoritmo, generalmente en el refinamiento de imágenes a través de la determinación de los planos que definen a cada objeto dentro de la imagen. Este último uso se denomina de forma general análisis basado en el espacio de características. El espacio de características es un mapeo de la entrada de datos en pequeños subconjuntos que representan puntos con características similares tales como el color, las propiedades de cercanía o lejanía espacial, el tipo de textura, etc. Existen dos clases fundamentales de espacios de características, los espacios de características paramétricos y los no paramétricos. Los métodos paramétricos realizan suposiciones sobre el espacio tales como el número máximo de segmentos dentro de la imagen o la forma general de los mismos, que suele considerarse elíptica. Este tipo de métodos resultan en multitud de ocasiones poco prácticos ya que producen soluciones que pueden no guardar ningún parecido con la realidad.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

54

I. M EMORIA § 4. P REPROCESAMIENTO DE IMÁGENES

Los métodos no paramétricos no realizan las anteriores suposiciones y según el procedimiento que sigan se pueden dividir en dos clases: Agrupamiento jerárquico. Unen o dividen conjuntos de datos según una medida de proximidad. Requieren la determinación de un parámetro que indique el fin de las iteraciones y son en general computacionalmente costosos. Estimación de densidad. Consideran el espacio de características como una función de densidad de probabilidad(p.d.f.) del parámetro representado. Regiones densas en el espacio de características corresponden a máximos locales de la p.d.f., es decir, las modas de la densidad desconocida. Cuando la posición de la moda es encontrada, el grupo asociado a ella es delineado según la estructura local del espacio de características. Para realizar el preprocesado de la imagen, se ha seleccionado una técnica no parámetrica de estimación de la densidad denominada Mean Shift [33, 34] que ha demostrado ser especialmente eficaz tanto a la hora de segmentar las imágenes como de filtrarlas. Algunos de los algoritmos que presentan una mejor actuación dentro de la clasificación de la universidad de Middlebury[58] implementan este método de segmentación, entre ellos cabe citar [29, 48]. A continuación se detallarán las características del algoritmo y se mostrarán algunos de los resultados obtenidos.

4.1.

Algoritmo Mean Shift o de desplazamiento de la media

4.1.1.

Teoría del desplazamiento de la media

El algoritmo Mean Shift es una técnica de análisis no paramétrica del espacio de características que descompone la imagen de referencia en regiones de color homogéneo denominados segmentos o clusters. De forma general, se asume en la visión estéreo que los valores de disparidad varían poco en esas regiones de color homogéneo y que las discontinuidades debidas a distintas profundidades sólo aparecen en los límites de estas regiones por lo tanto si se consigue segmentar la imagen, el mapa de disparidades obtenido a partir de la optimización de la función de energía se podrá mejorar dentro de cada uno de los segmentos establecidos. Para diferenciar los distintos colores que aparecen en una imagen y así poder delimitar los diferentes objetos sobre la misma, se utiliza una representación espacial,

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

55

I. M EMORIA § 4. P REPROCESAMIENTO DE IMÁGENES

con todos los pixels que componen la imagen o una muestra significativa, en un sistema de color L*u*v* como muestra la Figura 24,[33, 34].

Figura 24. Ejemplo típico del análisis del espacio de características El espacio de color CIELUV o estrictamente CIE 1976(L*u*v) se define en colometría como una transformación simple del standard CIE XYZ, donde cada color viene dado por la adición de tres colores primarios X(rojo), Y(verde) y Z(azul) en mayor o menor medida. El objetivo fundamental de esta transformación es crear un espacio de color de percepción uniforme. Este sistema desplazó al tradicional RGB en la determinación de los segmentos ya que, a diferencia del anterior, la representación tridimensional de todos los puntos en la escena forma un espacio euclidiano, es decir, la distancia que separa en esa representación tridimensional a un punto de otro es directamente proporcional a la diferencia de color que existe entre ellos mientras que en un sistema RGB esta propiedad no se verifica, así, un punto muy cercano a otro puede presentar un color muy diferente o puntos muy alejados pueden ser simplemente tonos ligeramente distintos de un mismo color. Existen regiones en la representación espacial de los píxeles que son más densas que otras, cuanta mayor concentración de puntos tengan esas zonas, más próximo es el color entre ellas y por lo tanto corresponden al mismo objeto. Es decir, para delimitar los objetos es suficiente con conocer la función de densidad de probabilidad de la imagen y encontrar las regiones más densas, que se corresponden con los máximos locales de la fdp, esto es, con la moda. Matemáticamente, el procedimiento que sigue el desplazamiento de la media es el siguiente:

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

56

I. M EMORIA § 4. P REPROCESAMIENTO DE IMÁGENES

Sea un conjunto finito (los datos muestra) en el espacio n-dimensional. Sea K un kernel y w : S → (0, ∞) una función de pesos. La muestra promedio con kernel K en xX es definida como: P K(s − x)w(s)s m(x) = PsS sS K(s − x)w(s) La diferencia m(x)-x es conocida como mean shift. Por otro lado, el algoritmo mean shift se sirve de la definición anterior del desplazamiento de la media de la siguiente manera: Sea T ⊂ X un conjunto finito (centros de los grupos) en el espacio n-dimensional. La evolución de T en la forma de iteraciones T ← m(T )conm(T ) = m(t); tT , es conocida como el algoritmo mean shift. El algoritmo se detiene cuando alcanza un punto fijo(m(T)=T). Para cada tT hay una secuencia t,m(t),m(m(t)),..., que es llamada trayectoria de t. Para comenzar a implementar el algoritmo, será preciso determinar la función de densidad de probabilidad de la imagen, que vendrá dada por un estimador Parzen (ventana de Parzen) de la siguiente forma: n

1X fˆ(x) = KH (x − xi ) n i=1 KH (x) = |H|

−1 2

K(H

−1 2

x

Siempre que el espacio de características sea euclidiano, la matriz H se puede expresar como el producto entre un único parámetro de ancho de banda h al cuadrado por la matriz identidad. En ese caso, el estimador se puede expresar como: n 1 X x − xi ˆ f (x) = K( ), h > 0 d nh i=1 h n ck,d X x − xi 2 ˆ fh,K (x) = k(k k) d nh i=1 h

La calidad del estimador se determina a partir de un estudio AMISE [46]. Aunque estudios anteriores demuestran que el error de estimación es minimizado usando un kernel de Epanechnikov, la elección del kernel no es tan importante como la del ancho de banda [45]. Una vez definida la función de densidad de probabilidad, el siguiente paso consiste en calcular las modas de la misma. La moda se sitúa en los ceros del gradiente de la Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

57

I. M EMORIA § 4. P REPROCESAMIENTO DE IMÁGENES

función de densidad, luego se va a usar el algoritmo de desplazamiento de la media para determinar estos ceros sin necesidad de estimar la pdf. n 2ck,d X x − xi 2 ˆ ˆ 5fh,K (x) = 5fh,K (x) = k) (x − xi )k 0 (k d+2 nh h i=1

Haciendo el cambio de variable: g(x) = −k 0 (x)G(x) = cg,d g(kxk2 ) El gradiente de la función de densidad será:

ˆ h,k (x) = 2ck,d 5f nhd+2

n X

(x−xi)g(k

i=1

n X

n P

i 2 xig (k x−x k) h

x − xi 2 2ck,d x − xi 2 i=1 g(k k )= k )][ P [ n d+2 h nh h i=1

i=1

−x] i 2 g(k x−x k h

La ecuación anterior se puede descomponer en dos términos, por un lado se tiene: n cg,d X x − xi 2 ˆ g(k fh,G (x) = k) d nh i=1 h

Y el segundo término se corresponde con el vector desplazamiento de la media: n P

i 2 k) xig (k x−x h

mh,G (x) = i=1 n P

i=1

−x i 2 g(k x−x k h

Luego el gradiente de la función de densidad queda definido como: ˆ h,k (x) = fˆh,G (x) 2ck,d mh,G (x) 5f h2 cg,d

Y despejando el vector desplazamiento de la media: ˆ h,K (x) 1 5f mh,G (x) = h2 c 2 fˆh,G (x)

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

58

I. M EMORIA § 4. P REPROCESAMIENTO DE IMÁGENES

Así el vector de desplazamiento de la media, es decir la diferencia entre la media local y el centro de la ventana, es proporcional al gradiente de la densidad de probabilidad en ese punto del espacio x. Por otro lado, es inversamente proporcional a la densidad de probabilidad de G(x). Esto es beneficioso cuando se busca la región con mayor densidad de probabilidad, esta región se corresponde con un valor grande ˆ h,K (x) , es decir, se irá buscando el gradiente de fˆh,G (x) y un valor pequeño de 5f mínimo a pequeños desplazamientos de la media ya que nos encontramos en una región cercana al óptimo. Por otra parte, regiones con baja densidad de puntos se corresponden con largos desplazamientos de la media (amplificador por el pequeño valor del denominador). Los desplazamientos son siempre en la dirección y sentido del máximo de la densidad de probabilidad, es decir, la moda. En una región cercana a la moda, los desplazamientos de la media son casi nulos, en una lejana, los desplazamientos son importantes, por eso se denomina a este método de gradiente ascendente. En la figura 25 se observa la trayectoria que sigue el kernel hasta alcanzar el punto de mayor densidad de probabilidad.

Figura 25. Algoritmo de desplazamiento de la media Las localizaciones sucesivas del kernel se derivan de la ecuación del vector desplazamiento de la media obteniendose: n P

xi g(k

yj+1 = i=1 n P i=1

yj −xi 2 k) h

j = 1, 2... y −x g(k j h i k2 )

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

59

I. M EMORIA § 4. P REPROCESAMIENTO DE IMÁGENES

4.1.2.

Procedimiento para la determinación de la segmentación

Una vez desarrollada toda la teoría del desplazamiento de la media, se pueden describir los pasos a seguir en la segmentación de la imagen. 1. Realizar un filtrado incial de la imagen, preferiblemente el de desplazamiento de la media [33, 34]. Sea xi el input de dimensión d y zi los datos filtrados de dimensión d. a) Inicializar j = i, yi,1 = xi b) Calcular yi,j+1 como en la fórmula de la página anterior hasta que converja a y = ii,c c) Asignar a los datos filtrados la localización de entrada y el valor de color al que ha convergido r Zi = (Xis , Yi,c ) 2. Agrupar todos los Zi que estén más cercanos de hs en el dominio espacial y de hr en el dominio de los colores en Cp con p = 1....m 3. Para cada i o pixel asignar una etiqueta Li = p 4. De forma opcional, eliminar regiones en el espacio conteniendo menos de M pixels.

4.1.3.

Resultados

En las figuras 26 y 27 se presentan los resultados obtenidos a partir de la aplicación EDISON[47] para algunas de las imágenes que se emplearán en los capítulos sucesivos.

Figura 26. Segmentación meanshift sobre la imagen Tsukuba

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

60

I. M EMORIA § 4. P REPROCESAMIENTO DE IMÁGENES

Figura 27. Segmentación meanshift sobre la imagen Aloe

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

61

Capítulo 5 Elección de los términos de la función objetivo elección de los términos de la función objetivo determina en gran medida la calidad del mapa de disparidades que se obtendrá. En este capítulo se tratará la forma más simple de la ecuación de energía, que consta de dos términos como ya se señaló en capítulos anteriores:

L

A

E(d) = Edata (d) + λEsmooth (d) El primer término Edata mide la semejanza entre puntos correspondientes, basado principalmente en la diferencia en las intensidades de color de los mismos. El segundo término Esmooth es un término de suavidad que intenta asignar una disparidad similar a los puntos cercanos imponiendo una coherencia en todas las direcciones y no sólo en la de la línea epipolar. Entre los métodos existentes en la literatura se han escogido cuatro formas de cálculo del término Edata , el cálculo por diferencia de intensidades, la medida de disimilitud, el cálculo mediante diferencia del cuadrado de intensidades y gradiente y por último el método NCC (Normalized cross-correlation). Para el término smooth se ha elegido un único modelo que utiliza la diferencia de disparidades para suavizar la imagen. A continuación se detallan todos estos métodos.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

62

I. M EMORIA § 5. E LECCIÓN DE LOS TÉRMINOS DE LA FUNCIÓN OBJETIVO

5.1.

Elección del término Edata

5.1.1.

Método de diferencia de intensidades

El método de diferencia de intensidades (Square difference) es el más sencillo de todos. Se define como: Edata (x, y, c) =

XX c

kI1 (x, y, c) − I2 (x + d, y, c)k

x,y

Para establecer la similitud entre dos pixeles correspondientes, se mide la diferencia entre las intensidades del píxel (x, y) en la imagen izquierda (I1 ) y el píxel (x + d, y) en la imagen derecha (I2 ). Cuanto menor sea el valor absoluto de esta diferencia, más se parecerán los puntos en intensidad y por lo tanto, mejor será la correspondencia. A modo de ejemplo, se observa la actuación de este método sobre dos imágenes en las figuras 28y 29.

Figura 28. Mapa de disparidades de tsukuba empleando SD

Figura 29. Mapa de disparidades de aloe empleando SD

5.1.2.

Método de cálculo de la similitud pixel a pixel

Este método fue elaborado por Stan Birchfield y Carlo Tomasi[25] con el fin de obtener una medida de similitud insensible a la captura de la imagen. Cuando una escena es captada por un par de cámaras en estéreo, los valores de intensidad de los píxeles correspondientes no suelen ser generalmente los mismos. Esto se debe, entre otros factores, a que la luz reflejada en un punto no es la misma para

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

63

I. M EMORIA § 5. E LECCIÓN DE LOS TÉRMINOS DE LA FUNCIÓN OBJETIVO

todos los ángulos, a parámetros intrínsecos de la cámara así como a posibles ruidos que puedan aparecer. Para determinar el algoritmo que haga insensible el cálculo de la disparidad a estos factores, se ha supuesto que la imagen es epipolar. Sean iL e iR dos funciones de intensidad continuas de una única dimensión obtenidas a partir de la luz incidente sobre dos sensores, estas dos funciones son muestreadas resultando dos vectores con valores de intensidad IL e IR como se muestra en la figura 30.

Figura 30. Valores de intensidad muestreados por el sensor El objetivo del algoritmo será el de establecer la medida de similitud entre un pixel xL en la imagen izquierda y un pixel xR de la imagen derecha. Si se define IˆR como la función de interpolación lineal entre los puntos muestreados de la imagen derecha, se puede medir el parecido entre la intensidad de xL y la región interpolada alrededor de xR como: ¯ L , xR , IL , IR ) = d(x

m´ın

xR − 12 ≤x≤xR + 12

|IL (xL ) − IˆR (x)|

Definiendo IL de manera análoga, se obtiene el simétrico: ¯ R , xL , IR , IL ) = d(x

m´ın

xL − 12 ≤x≤xL + 12

|IˆL (xL ) − IR (x)|

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

64

I. M EMORIA § 5. E LECCIÓN DE LOS TÉRMINOS DE LA FUNCIÓN OBJETIVO

Figura 31. Cálculo de la disimilitud La similitud d entre los píxeles se define simétricamente como el mínimo de las dos catidades anteriores: ¯ L , xR , IL , IR ), d(x ¯ R , xL , IR , IL ) d(xL , xR ) = mind(x Como se ha establecido una interpolación lineal entre las muestras: 1 1 IR− ≡ IˆR (xR − ) = (IR (xR ) + IR (xR − 1)) 2 2 1 1 IR+ ≡ IˆR (xR + ) = (IR (xR ) + IR (xR + 1)) 2 2 Y si se definen Imin = m´ın IR− , IR+ , IR (xR ) y Imax = m´ax IR− , IR+ , IR (xR ), entonces ¯ L , xR , IL , IR ) = m´ax(0, IL (xL ) − Imax , Imin − IL (xL )) d(x Esta medida de similitud es la forma que toma el término Edata . Como se puede comprobar en las figuras 33 y 32, el algoritmo ofrece muy buenos resultados en un tiempo de ejecución considerablemente corto.

Figura 32. Mapa de disparidades de tsukuba empleando el cálculo de similitud

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

65

I. M EMORIA § 5. E LECCIÓN DE LOS TÉRMINOS DE LA FUNCIÓN OBJETIVO

Figura 33. Mapa de disparidades de aloe empleando el cálculo de similitud

5.1.3.

Método de diferencia de cuadrados de intensidades y gradiente

Este método fue empleado por Andreas Klaus, Mario Sormann y Konrad Karner en su algoritmo [48], que es hasta la fecha el que mejor resultado ha dado en el cálculo del mapa de disparidades según la clasificación de la universidad de Middlebury [58]. El método combina la diferencia de intensidades absoluta ya desarrollada en el punto 5.1.1. con una medida basada en el gradiente que se define como: X

CSAD (x, y, d) =

I1 (i, j) − I2 (i + d, j)

(i,j)N (x,y)

CGRAD (x, y, d) =

X

| 5x I1 (i, j) − 5x I2 (i + d, j)|

(i,j)Nx (x,y)

+

X

| 5y I1 (i, j) − 5y I2 (i + d, j)|

(i,j)Ny (x,y)

donde N (x, y) es una ventana de tamaño 3x3 que rodea al pixel en la posición (x, y).Nx (x, y) es una ventana que rodea al mismo pixel pero sin la última columna y Ny (x, y) es una ventana que rodea al pixel pero sin la última fila. 5x y 5y son respectivamente el gradiente de la intensidad en la dirección x y en la dirección y. El coste de la función Edata viene dado por: C(x, y, d) = (1 − w)CSAD (x, y, d) + wCGRAD (x, y, d) Para determinar de manera óptima el valor del peso de cada uno de los términos(w), se debe maximizar el número de correspondencias correctas obtenidas a partir de la comparación de los mapas de disparidades para la imagen izquierda y para la imagen derecha como imagen de referencia además de elegir el método con menor coste para la función Edata . Este procedimiento requeriría una serie de pruebas a priori para cada imagen de la que se quiera conocer el mapa de disparidades, lo que convertiría al método

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

66

I. M EMORIA § 5. E LECCIÓN DE LOS TÉRMINOS DE LA FUNCIÓN OBJETIVO

global de optimización en bastante ineficiente. Por esta razón y debido también a que la solución no presenta cambios importantes cuando se trabaja con w dentro de un rango de valores razonable, se ha preferido determinar empíricamente el valor que mejor aproxima el mapa de disparidades para todas las imágenes. La ventaja que presenta este método frente a otros más tradicionales es que tiene en cuenta la medida del gradiente, por lo que será capaz de detectar variaciones bruscas en las intensidades de los píxeles y por lo tanto de los bordes de los objetos en la escena. Para que la detección sea efectiva, se debe elegir un método adecuado para la determinación de los gradientes tanto horizontales como verticales. Existen numerosos métodos pero entre los más empleados se encuentran: Operador Roberts: Es el operador de gradiente más simple, utiliza las direcciones diagonales para calcular el gradiente mediante las máscaras que se presentan a continuación. " # 0 1 5x = −1 0 " # 1 0 5y = 0 −1 El filtro sobre la imagen tsukuba presenta la siguiente forma:

Figura 34. Operador Roberts Este operador obtiene una buena respuesta ante bordes diagonales y ofrece buenas prestaciones en cuanto a localización. El gran inconveniente de este operador es su extremada sensibilidad al ruido. Operador Sobel: Este operador calcula el gradiente de la imagen a partir de secciones de 3x3. Las máscaras que lo definen son: 

 −1 −2 −1   5x =  0 0 0 1 2 1 Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

67

I. M EMORIA § 5. E LECCIÓN DE LOS TÉRMINOS DE LA FUNCIÓN OBJETIVO

  −1 0 1   5y = −2 0 2 −1 0 1 El operador Sobel es menos sensible a los ruidos que el operador Roberts y además proporciona un suavizado de la imagen que no ofrece el operador anterior. En la figura 35 se observa la aplicación de este filtro sobre la imagen tsukuba, como se puede ver, la detección de los bordes es bastante buena.

Figura 35. Operador Sobel

Operador Prewitt: Este operador como el de Roberts tiende a amplificar el ruido. Su máscara es:   −1 −1 −1   5x =  0 0 0 1 1 1   −1 0 1   5y = −1 0 1 −1 0 1 La imagen tsukuba que se obtiene, una vez aplicando el filtro es:

Figura 36. Operador Prewitt

A raiz de las siguientes imágenes, se puede observar como este término Edata incluso para el operador Sobel, que a priori para el que ofrece una mejor calidad, no ha servido Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

68

I. M EMORIA § 5. E LECCIÓN DE LOS TÉRMINOS DE LA FUNCIÓN OBJETIVO

para obtener los resultados esperados. Se presentan tres figuras 37, 38, 39 para w = 0,3, 0,6 y 0,9, ninguno de los tres resultados presenta una respuesta aceptable.

Figura 37. Mapa de disparidades de tsukuba para w = 0,3 con operador Sobel

Figura 38. Mapa de disparidades de tsukuba para w = 0,6 con operador Sobel

Figura 39. Mapa de disparidades de tsukuba para w = 0,9 con operador Sobel

5.1.4.

Normilized cross-correlation (NCC)

Es una medida de similitud entre píxeles de distintas imágenes basada en la correlación entre los mismos. Se trata de un cálculo algo más complejo que el de diferencia de intensidades y que suele presentar mejores resultados que éste aunque debido al alto coste computacional que requiere, se deshecha en muchos casos como

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

69

I. M EMORIA § 5. E LECCIÓN DE LOS TÉRMINOS DE LA FUNCIÓN OBJETIVO

método de cálculo del término Edata . La fórmula empleada para esta medida de similitud es: X (i,j)W

I (i, j) · I2 (i + d, j) r P1 I12 (i, j) · I22 (i + d, j) 2 (i,j)W

Esta ecuación se utiliza para conjuntos de ventanas de tamaño W, cuanto mayor sea el tamaño de esta ventana mejor será la aproximación al mapa de disparidades real pero lamentablemente con el aumento de las dimensiones viene asociado un aumento del tiempo de cálculo. Se han elegido ventanas de tamaño pequeño (entre 4x4 y 16x16píxeles) ya que el método de optimización se volvía demasiado lento y los mapas de disparidades finales no presentaban mejoras muy importantes. A continuación se muestra en la figura 40 el mejor resultado que se ha obtenido para el algoritmo con término Edata en NCC:

Figura 40. Mapa de disparidades de tsukuba para Edata en NCC

5.2.

Término Esmooth

5.2.1.

Diferencia de disparidades

Para procurar que el valor de la disparidad de un pixel no difiera mucho de la del resto de su vecindad se utiliza la diferencia de disparidades de píxeles adyacentes en la función de energía de manera que al minimizar esta función, se tiendan a minimizar estas diferencias. La fórmula empleada en este caso es: Esmooth = d(i, j) − d(i − 1, j)

5.2.2.

Diferencia de disparidades saturada a un valor

En este caso, la diferencia de disparidades se determina de manera análoga al caso anterior, con la salvedad de que existe un límite superior para el valor de la función Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

70

I. M EMORIA § 5. E LECCIÓN DE LOS TÉRMINOS DE LA FUNCIÓN OBJETIVO

Esmooth , es decir, la función se encuentra truncada. De esta manera, se consigue un valor máximo de diferencia de disparidades por encima del cual toda correspondencia se considerará como errónea. El valor que se toma como límite superior se determinará empíricamente y variará de unas imágenes a otras.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

71

Capítulo 6 Manejo de oclusiones

U

NA vez establecido el mapa de disparidades, se observa cómo la calidad del mismo

no es en muchos casos la esperada. Existen pixeles para los que se han establecido incorrectamente sus correspondencias y se deben intentar mejorar sus valores. Los problemas de correspondencia pueden originarse por diversas causas, entre las principales se encuentran: Problemas debidos a variaciones fotométricas: Un punto de la escena captado en una de las imágenes puede no presentar la misma intensidad que su correspondiente en la otra imagen debido a variaciones de luminosidad o ruidos. Este problema afecta al cálculo de la disparidad ya que la función objetivo se basa en la correlación de intensidades para establecer las correspondencias por lo que se pueden llegar a obtener resultados erróneos. Para mejorar las correspondencias erróneas debidas a variaciones fotométricas existen métodos que las tienen en cuenta desde el planteamiento de la función objetivo, con un término Edata que se muestre poco sensible a las mismas. En el capítulo anterior se ha estudiado un ejemplo de este tipo de métodos con el cálculo de la similitud pixel a pixel de Birchfield y Tomasi [25]. Oclusiones: Se define un punto ocluido como aquel que no presenta correspondencia en la otra imagen. Los puntos ocluidos afectan de manera muy importante a los algoritmos de resolución tridimensional por lo que deberán ser abordados una vez establecido el mapa de disparidades inicial. Las oclusiones siempre implican una discontinuidad en la profundidad de la escena, ya que existen objetos en los planos más cercanos a la cámara que impiden ver la totalidad de los objetos situados más atrás para ciertos ángulos de la cámara. El fenómeno puede observarse en la Figura 41

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

72

I. M EMORIA § 6. M ANEJO DE OCLUSIONES

Figura 41. Puntos ocluidos en una escena

Figura 42. Escena con textura repetitiva

Para la determinación de los puntos ocluidos existen distintos métodos. Por un lado aparecen los métodos que detectan oclusiones, que se encargan de determinar los puntos definidos como ocluidos pero no realizan ningún tipo de tratamiento sobre los mismos. Relacionados con los métodos que detectan oclusiones se encuentran aquellos que reducen la sensibilidad a las mismas. En este caso se reconocen las oclusiones y se plantean algoritmos para estimar de la mejor manera posible la disparidad de los mismos.

Por último, también existen métodos que modelan la geometría de la oclusión, éstos añaden un nuevo término a la función objetivo de manera que las oclusiones se tengan en cuenta en el primer paso de optimización de algoritmo. Textura repetitiva: Todas aquellas escenas que presenten una misma geometría con cierta frecuencia pueden llevar a errores en el cálculo del mapa de disparidades, ya que a priori las correspondencias podrían ser posibles para todas aquellas regiones que se repiten. Un ejemplo de este tipo de estructuras se muestra en la Figura 42

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

73

I. M EMORIA § 6. M ANEJO DE OCLUSIONES

Falta de textura: Si ciertas regiones de la imagen presentan muchos puntos con las mismas características, la correspondencia no se podrá establecer de forma correcta ya que existen varias soluciones. En la práctica, el caso que mayores problemas está generando es la determinación y eliminación de los puntos ocluidos por lo que será en el punto en que nos centraremos para recuperar un buen mapa de disparidades. Los distintos métodos arriba mencionados se detallarán a continuación.

6.1.

Métodos que detectan oclusiones

6.1.1.

Left-Right checking

El procedimiento es sencillo, se calculan los mapas de disparidad tanto de la imagen izquierda como de la derecha y se comprueban las disparidades entre las dos imágenes, si la disparidad de un punto en la derecha difiere de la disparidad de su correspondiente en la derecha, entonces el pixel esta ocluido. Matemáticamente estas relaciones se pueden expresar como: DL (xL ) = DR (xL − DL (xL )) Entre las desventajas de este método están que no tiene en cuenta fallos debidos a la iluminación no uniforme o el ruido en la imagen. Además el tiempo de cálculo de las correspondencias es el doble que en cualquier otro de detección de oclusiones ya que el algoritmo de optimización debe ejecutarse dos veces, una vez para cada imagen. En las figuras 43 y 44 se muestran dos ejemplos de determinación de oclusiones para la imagen tsukuba y aloe a partir del método Left-Right checking:

Figura 43. Oclusiones en la imagen tsukuba

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

74

I. M EMORIA § 6. M ANEJO DE OCLUSIONES

Figura 44. Oclusiones en la imagen aloe

6.1.2.

Restricción en el orden de los píxeles

El orden relativo de los píxeles en el par estéreo se debe conservar de una imagen a la otra para una misma línea horizontal (scan-line) si se formula la hipótesis de que no hay objetos estrechos en la escena. Esta técnica verifica el orden de los píxeles y de sus correspondencias y así puede establecer si un punto está ocluido. En la figura 45 se muestra un ejemplo donde no se cumplen las restricciones del orden de los píxeles.

Figura 45. Ejemplo de la restricción en el orden de los píxeles En las figuras 47 y 46 se muestran las oclusiones detectadas sobre dos imágenes a partir de la restricción del orden:

Figura 46. Oclusiones de la imagen tsukuba

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

75

I. M EMORIA § 6. M ANEJO DE OCLUSIONES

Figura 47. Oclusiones de la imagen aloe

6.2.

Métodos que reducen sensibilidad

6.2.1.

RANSAC

Una vez determinados los pixeles ocluidos a partir de cualquiera de los métodos mencionados anteriormente, se procede a la interpolación de las disparidades erróneas a partir de aquellas de los puntos considerados como buenos. El método RANSAC[49] es una abreviatura para el consenso de la muestra escogida al azar. Consiste en la estimación de una serie de parámetros a partir de un conjunto de datos observados que contienen tanto inliers como outliers. El primer algoritmo de este tipo fue publicado por Fischler y Bolles en 1981. La particularidad del método RANSAC es que no tiene en cuenta los outliers para estimar los parámetros de la muestra, es por ello que resulta un método muy conveniente en el procesamiento de imágenes en estéreo para su posterior reconstrucción. Una vez determinados los segmentos que forman la imagen a partir del algoritmo meanshift y el mapa de disparidades de la imagen, se procede a la detección de los puntos ocluidos, que son tratados en cada uno de los segmentos a través del algoritmo RANSAC obteniendo un plano de disparidad bastante bueno que sirve para interpolar los valores de las disparidades de los píxeles que desconocemos por estar ocluidos. En la figura 48 se puede observar la mejora en el ajuste de los datos al utilizar el algoritmo RANSAC frente a una simple interpolación por mínimos cuadrados, que realiza el ajuste de la recta teniendo en cuenta los outliers.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

76

I. M EMORIA § 6. M ANEJO DE OCLUSIONES

Figura 48. Ejemplo de la restricción en el orden de los píxeles El algoritmo presenta como objetivo el ajuste robusto de un modelo, que será de la elección del usuario (como primera aproximación se suele escoger un ajuste por mínimos cuadrados) a un conjunto de datos S que contiene errores o outliers. Los pasos que sigue el mismo se presentan a continuación: 1. Seleccionar aleatoriamente una muestra s de puntos del conjunto total S y calcular el modelo con este subconjunto 2. Determinar el subconjunto de puntos Si que están dentro de un umbral de distancia al modelo. El subconjunto Si es el conjunto consenso y define los inliers de S. 3. Si el conjunto Si es mayor que un umbral T, volver a estimar el modelo utilizando todos los puntos de Si y terminar. 4. Si el tamaño de Si es menor que T, seleccionar un nuevo subconjunto y repetir el paso anterior. 5. Después de N intentos seleccionar el subconjunto Si con mayor consenso, volviendo a estimar el modelo utilizando todos los puntos del subconjunto Si Para escoger el valor del umbral de inliers existen dos posibilidades, se puede escoger empíricamente o bien, si el ruido de las medidas se puede ajustar a una gaussiana de media cero y desviación típica σ entonces T sigue una distribución chi cuadrado. Por otro lado, el umbral de consenso se determina a partir de: T = (1 − e)n donde e es la probabilidad de presencia de outliers y n el número total de datos. En la Figura 49 se muestran unas imágenes obtenidas por refinamiento del mapa de disparidades RANSAC con método de optimización Graph cuts.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

77

I. M EMORIA § 6. M ANEJO DE OCLUSIONES

Figura 49. Tsukuba con refinamiento por RANSAC

6.2.2.

Least Median Square(LMS)

Se trata de un procedimiento análogo al anterior en el que lo que se persigue es determinar el plano de disparidades de cada uno de los segmentos que forman la imagen. De esta manera, se calcularán sobre este plano los puntos que han sido definidos como erróneos. El algoritmo es sensiblemente más sencillo que el RANSAC, ya que no son precisos los umbrales de inliers. Los pasos que sigue el algoritmo se detallan a continuación: 1. Seleccionar aleatoriamente una muestra s de puntos del conjunto total S y calcular el modelo con este subconjunto 2. Determinar el subconjunto de puntos Si que están dentro de un umbral de distancia al modelo. El subconjunto Si es el conjunto consenso y define los inliers de S. 3. Si el conjunto Si es mayor que un umbral T, volver a estimar el modelo utilizando todos los puntos de Si y terminar. 4. Si el tamaño de Si es menor que T, seleccionar un nuevo subconjunto y repetir el paso anterior. 5. Después de N intentos seleccionar el subconjunto Si con mayor consenso, volviendo a estimar el modelo utilizando todos los puntos del subconjunto Si En la Figura 50 se muestran unas imágenes obtenidas por refinamiento del mapa de disparidades LMS con método de optimización Graph cuts.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

78

I. M EMORIA § 6. M ANEJO DE OCLUSIONES

Figura 50. Tsukuba con refinamiento por LMS

6.3.

Métodos que modelan la geometría de la oclusión

6.3.1.

Modelo de oclusión global

El modelo de oclusión global es una técnica muy efectiva en el cálculo de las correspondencias de imágenes en estéreo pero que no está en general muy explotada debido a que suele estar estandarizado el uso de una función objetivo con dos términos, que como ya se ha comentado anteriormente son el término Edata y el término Esmooth . En el caso de un modelo de oclusión global, se añade un nuevo término a la función objetivo para modelar las oclusiones de manera que estas no deban ser tratadas a posteriori. De esta forma, la nueva ecuación de optimización se plantea como: E(d) = Edata (d) + Esmooth (d) + Eoclusiones (d) Se ha optado por la utilización de un término para las oclusiones muy sencillo, de manera que pueda ser implementado sin dificultad en el código del que se parte para maximizar la función de energía. Este término se basa en la restricción del orden de los píxeles entre las dos imágenes para determinar si un píxel se encuentra o no ocluido. Para ello, se establece que si el valor de la coordenada en x del píxel inmediatamente anterior al que se quiere establecer la etiqueta mas su disparidad son mayores que la suma de la coordenada x y la posible etiqueta del píxel en estudio, entonces esa correspondencia equivaldría a un punto ocluido, por lo que se le asocia al término Eoclusiones un valor muy elevado, que evite que estas situaciones se produzcan. En el caso de no producirse, el término Eoclusiones

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

79

I. M EMORIA § 6. M ANEJO DE OCLUSIONES

se vería igualado a cero. De todo esto se deduce que la ecuación matemática que rige el término que modela las oclusiones viene dado por: ( Eioclusiones =

0 si xi−1 + dispi−1 < xi + dispi K si xi−1 + dispi−1 > xi + dispi

Donde K es el peso que se le da a este término como penalización por permitir una oclusión. Empíricamente se ha determinado que este valor es igual a 50. En la Figura 51 se muestran los resultados obtenidos de la aplicación de este método:

Figura 51. Tsukuba con aplicación del modelo de oclusión global

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

80

Capítulo 7 Post-procesado de imágenes etapa de post-procesado permite dar un último retoque al mapa de disparidades obtenido en las etapas anteriores mediante la aplicación de múltiples técnicas, entre las que cabe destacar el filtrado de la imagen o la estimación a nivel de subpíxeles de la disparidad de los puntos de la escena.

L

A

Este tipo de aplicaciones resultan fundamentales siempre que el método para la búsqueda de las correspondencias esté basado en técnicas de correlación de área, que se dan tanto en los métodos locales como en los globales en el caso de un término Edata bajo la forma de diferencia de intensidades o diferencia cuadrada de intensidades y gradiente, cuando no existe una técnica posterior de tratamiento de las correspondencias. Esto se debe a que estos métodos por sí solos introducen un gran número de falsas correspondencias que deben ser eliminadas. No se trata de una etapa fundamental, de hecho si el mapa de disparidades obtenido anteriormente presenta la calidad suficiente, implicaría un aumento del tiempo de tratamiento de la imagen que en muchas aplicaciones en tiempo real resultaría indeseable. Además, si el mapa de disparidades presenta demasiados errores, deberá analizarse con detenimiento si la aplicación de un método de post-procesado resultará útil ya que en numerosas ocasiones el método elegido arrastrará esos errores a otras zonas de la imagen que presentaban un buena aproximación al mapa de disparidades real de la escena. En este capítulo se estudiarán las técnicas de filtrado de imágenes de paso bajo. Además, se analizará la técnica de estimación de subpíxeles aplicada en el artículo [48].

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

81

I. M EMORIA § 7. P OST- PROCESADO DE IMÁGENES

7.1.

Técnicas de filtrado

Son métodos que se encargan de resaltar o suprimir, de forma selectiva, información contenida en una imagen o bien de ocultar valores anómalos dentro de la misma. El proceso de filtrado consiste en la aplicación a cada uno de los píxeles de la imagen de una matriz de filtrado o máscara compuesta por números enteros y que genera un nuevo valor para el píxel en función de su valor incial y los valores de los píxeles en su vecindario. El resultado de la aplicación de la máscara se suele dividir entre un escalar, que generalmente es la suma de todos los valores que forman la matriz. Además, se puede expresar la máscara del filtro en forma de ecuación, que para el caso más usual de una ventana de dimensiones 3x3 viene dado por:

0 N Di,j =

N Di−1,j−1 + N Di,j−1 + N Di+1,j−1 + N Di−1,j + 9

+N Di,j + N Di+1,j + N Di−1,j+1 + N Di,j+1 + N Di+1,j+1 9 donde i representa la fila y j la columna en la que se encuentra cada pixel, N Di,j 0 representa su valor inicial y N Di,j el valor obtenido tras el filtrado de la imagen. Se debe tener en cuenta que en el proceso de filtrado se pierde la información que pueden dar los bordes de la imagen ya que la ventana de filtrado se saldría fuera de la misma. Los filtros más utilizados son los de paso bajo, que presentan como particularidad que producen un suavizado de la imagen, los filtros paso alto que aumentan el contraste y que por tanto quedan fuera del estudio del post-procesado del mapa de disparidades, los filtros direccionales, que detectan en la imagen estructuras que siguen una determinada dirección y los filtros de detección de bordes, que permiten identificar los objetos a través de sus contornos. Ejemplos de este tipo de filtros fueron vistos en el capítulo 4 de esta memoria con el operador Sobel, Prewitt y Roberts. 7.1.0.1.

Filtros de paso bajo

Su objetivo es suavizar la imagen, son útiles cuando se supone que la imagen tiene gran cantidad de ruido y se quiere eliminar, así como para resaltar la información correspondiente a una determinada escala a través de la modificación del tamaño de la

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

82

I. M EMORIA § 7. P OST- PROCESADO DE IMÁGENES

matriz de filtrado. Existen varias posibilidades en cuanto a filtros paso bajo: Filtro de la media: Asigna al pixel central la media de todos los pixeles incluidos en la ventana. La matriz de filtrado estaría compuesta por unos y el divisor sería el número total de elementos en la matriz. A continuación se muestra la máscara que la determina para una ventana de 3x3, aunque el tamaño de la ventana puede variar en función de la calidad del filtrado obtenido.   1 1 1  1 1 1 1 9 1 1 1 De la aplicación de este filtro con una ventana de 8x8 sobre el mapa de disparidades de la imagen tsukuba, con método de optimización Belief Propagation dentro de los Markov Random Fiels se obtienen las imágenes de la figura 52:

Figura 52. a)Mapa de disparidades sin filtro b)Mapa de disparidades con filtro de la media

A simple vista, no se puede observar si el filtro de la media introduce o no mejoras en la imagen inicial, por lo que se ha procedido a calcular el error en ambos casos. En la siguiente tabla se observan los resultados: Filtro

Error

Error porcentual

NO

1.0245

32.5021

SI

1.23643

32.8966

Como se señaló anteriormente, en este caso no es útil la utilización de un filtro de la media para reducir el nivel de error, pero no se puede concluir que para cualquier caso este filtro resulte ineficiente. En el capítulo de resultados se determinará la validez de esta técnica a raíz de los resultados obtenidos para distintas imágenes.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

83

I. M EMORIA § 7. P OST- PROCESADO DE IMÁGENES

Filtro de la media ponderada: Los elementos de la matriz de filtrado no son todos 1 sino que se da más peso a uno de ellos (generalmente el central) para obtener un resultado más parecido a la imagen original y evitar que aparezca borrosa. La máscara que utiliza es la siguiente:   1 1 1  1 1 2 1 9 1 1 1 El mismo análisis realizado con el filtro de la media sobre la imagen tsukuba se vuelve a hacer teniendo ahora en cuenta la ponderación. La figura 53 muestra los mapas obtenidos.

Figura 53. a)Mapa de disparidades sin filtro b)Mapa de disparidades con filtro de la media ponderada

El error que aparece en la imagen determinada con filtro y sin filtro es: Filtro

Error

Error porcentual

NO

1.0245

32.5021

SI

3.12335

60.3813

En este caso, el error aumenta mucho respecto al valor obtenido con el filtro de la media simple. Filtro de la mediana:Tiene la ventaja de que el valor final del pixel es un valor real presente en la imagen y no un promedio, de este modo se reduce el efecto borroso que tienen las imagenes que han sufrido un filtro de media. Además el filtro de la mediana es menos sensible a valores extremos. Tiene como inconveniente que resulta más complejo de calcular ya que hay que ordenar los diferentes valores que aparecen en los pixeles incluidos en la ventana

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

84

I. M EMORIA § 7. P OST- PROCESADO DE IMÁGENES

y determinar cual de ellos es el valor central. En la figura 54 se puede observar un ejemplo de cálculo para este filtro.

Figura 54. Aplicación filtro de la mediana

Para la imagen tsukuba, los mapas de disparidades con y sin el filtro de la mediana se muestran en la Figura 55.

Figura 55. a)Mapa de disparidades sin filtro b)Mapa de disparidades con filtro de la mediana

El error con y sin filtro se puede observar en la siguiente tabla: Filtro

Error

Error porcentual

NO

1.0245

32.5021

SI

1.32086

31.1668

Con el filtro de la mediana el error parece disminuir, pero de forma muy débil por lo que a priori no se podría señalar si se trata de un buen método de postprocesado.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

85

I. M EMORIA § 7. P OST- PROCESADO DE IMÁGENES

7.2.

Estimación de subpíxeles

Para reducir las discontinuidades causadas por la cuantización del proceso de selección de las profundidades se puede utilizar un algoritmo de estimación de los sub-pixeles basado en un polinomio de interpolación cuadrático. Si la función que selecciona las profundidades fuera continua, la profundidad que llevaría al menor coste de la función de energía podría ser encontrada. Sin embargo, la función es discreta por lo que para mejorar el valor de las profundidades se puede proceder a interpolar cuadráticamente los puntos que ya se han obtenido, calcular los puntos intermedios entre los ya conocidos de manera que se obtengan tres medidas d− , d y d+ y seleccionar de entre ellos el valor mínimo de manera análoga a como se hizo en el cálculo de la similitud pixel a pixel por Birchfield y Tomasi[25]. Matemáticamente, la estimación de sub-pixeles se puede expresar como: f (x) = ax2 + bx + c −b 2a Sea f (xmin ) el mínimo de la función f (x), conocidos d, f (d), f (d− ) y f (d+ ) y sean a y b parámetros calculables, entonces se puede determinar la disparidad mínima como: xmin =

xmin = d −

f (d+ ) − f (d− ) 2(f (d+ ) + f (d− ) − 2f (d))

En la Figura 56 se muestran las imagenes obtenidas con y sin aplicación de la estimación de los subpíxeles al modelo tsukuba con método de obtimización Belief propagation:

Figura 56. a)Mapa de disparidades sin estimación b)Mapa de disparidades con con estimación de subpíxeles

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

86

Capítulo 8 Resultados este capítulo, se procederá a realizar pruebas con los distintos algoritmos planteados a lo largo de toda la memoria y los métodos de optimización basados en campos aleatorios de Markov de manera que se pueda llegar a determinar la validez de los mismos, su actuación en comparación con la del resto de algoritmos y el método que mejor responde ante un compromiso entre tiempo de ejecución y la calidad del mapa de disparidades.

E

N

En los capítulos anteriores se abordaron las distintas técnicas para obtener el mapa de disparidades y se evaluaron algunos de esos métodos pero no se llegaron a comparar entre sí. Se procederá en primer lugar a recorrer los distintos modelos de optimización de manera que se pueda seleccionar el método más eficiente. Se hará resolviendo el mismo algoritmo para distintas imágenes, de esta manera se evitará obtener resultados parciales que beneficien a las imágenes con unas determinadas características. En segundo lugar, se realizará una comparación entre todos los posibles términos que puede emplear la función de energía. Y a continuación se realizará un análisis general de todos los algoritmos empleados para la resolución del problema de correspondencia, teniendo en cuenta los aspectos del tiempo de ejecución y el error en el mapa de disparidades. Por último, se mostrarán los resultados obtenidos por nuestro mejor método en comparación con todos aquellos que se encuentran dentro de los mejores algoritmos en Middlebury Stereo Vision[58].

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

87

I. M EMORIA § 8. R ESULTADOS

Se debe tener en cuenta que los resultados que se presentan a continución no comprenden el conjunto de todas las pruebas realizadas sobre las imágenes, sino únicamente una muestra bastante significativa de las mismas.

8.1.

Métodos de optimización

El objetivo en este apartado es encontrar el método de optimización que presenta una mejor actuación en cuanto a tiempo de cálculo y píxeles erróneos en el mapa de disparidades. Se ha estudiado para uno de los algoritmos más sencillos y que presenta uno de los mejores resultados, la actuación de los distintos métodos de optimización para tres imágenes. El término Edata empleado ha sido el de la medida de la similitud píxel a píxel [25], el término Esmooth es igual al definido en el capítulo 5 de la memoria, con un peso relativo dentro de la función objetivo cinco veces mayor. Este resultado ha sido determinado empíricamente a partir de diversas pruebas sobre las imágenes obteniendo un porcentaje de error más bajo que en el resto de los pesos estudiados. En la tabla inferior se observan los resultados para las imágenes tsukuba, aloe y cones con sus errores correspondientes y sus tiempos de ejecución para el algoritmo implementado por Birchfield y Tomasi [58].

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

88

I. M EMORIA § 8. R ESULTADOS

Imagen

Optimizacion

Error

Error[ %]

Tiempo

Tsukuba Tsukuba Tsukuba Tsukuba Tsukuba Tsukuba Aloe Aloe Aloe Aloe Aloe Aloe Cones Cones Cones Cones Cones Cones

ICM Swap Expansion MaxProdBP BPS TRWS ICM Swap Expansion MaxProdBP BPS TRWS ICM Swap Expansion MaxProdBP BPS TRWS

10.798 1.73827 1.20382 0.977441 1.40292 1.3866 4.6913 4.1261 1.9426 2.2371 1.7003 2.4612 5.9487 6.8427 7.1634 3.4895 5.9472 3.4978

40.7476 17.6462 23.8734 32.4986 25.4573 26.2464 85.1627 62.4692 28.7461 31.7495 26.1349 28.6419 83.8239 93.7004 56.8751 68.9164 61.5408 58.6226

0.648 3.841 2.924 4.637 2.472 2.823 2.685 8.457 10.829 53.656 25.076 45.9825 2.666 7.452 13.821 70.092 32.242 55.038

Las imágenes obtenidas para cada una de las pruebas son las siguientes:

Figura 57. Imagenes obtenidas de la aplicación de los métodos de optimización, de derecha a izquierda y de arriba a abajo: ICM, Swap, Expansion, MaxProdBP, BPS y TRWS

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

89

I. M EMORIA § 8. R ESULTADOS

Figura 58. Imagenes obtenidas de la aplicación de los métodos de optimización, de derecha a izquierda y de arriba a abajo: ICM, Swap, Expansion, MaxProdBP, BPS y TRWS

Figura 59. Imagenes obtenidas de la aplicación de los métodos de optimización, de derecha a izquierda y de arriba a abajo: ICM, Swap, Expansion, MaxProdBP, BPS y TRWS A continuación se ha realizó un frente de Pareto para cada unas de las imagenes, que relaciona el tiempo de ejecución y el error cometido en los distintos métodos de optimización. Nótese que las tres imágenes aparecen representadas de forma independiente ya que las escalas de tiempo y error no coinciden en los tres casos, por lo tanto resulta más interesante realizar las observaciones sobre cada una de las imágenes.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

90

I. M EMORIA § 8. R ESULTADOS

El frente de Pareto nos permitirá establecer el óptimo paretiano, que es aquella situación en la cual se cumple que no es posible beneficiar a más elementos de un sistema sin perjudicar a otros. En el caso que nos ocupa, se trata del método que mejor compromiso presenta entre tiempos de ejecución bajos y error pequeño.

Figura 60. Frente de Pareto de la imagen tsukuba para distintos métodos de optimización

Figura 61. Frente de Pareto de la imagen aloe para distintos métodos de optimización

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

91

I. M EMORIA § 8. R ESULTADOS

Figura 62. Frente de Pareto de la imagen cones para distintos métodos de optimización Se observa como en los tres casos, el óptimo paretiano aparece entre el método basado en ’Belief propagation BPS’ y método de corte de grafos de tipo ’Expansion’. Éstos dos métodos presentan por lo tanto un buen compromiso entre tiempo de ejcución y error cometido en el mapa de disparidades. En el caso de mapas de disparidades sencillos, con un número reducido de disparidades, el algoritmo de corte de grafos tipo ’Swap’ presenta un buen comportamiento, pero resulta totalmente ineficiente cuando las imágenes se complican. De cualquier forma, se trata de un método muy rápido, luego cuando se precisen estimaciones en tiempo real sin necesidad de conocer un mapa de disparidades de gran calidad, éste puede resultar un método muy apropiado. El método Belief propagation de tipo max-producto (MaxProdBP) no será muy recomendable para realizar la reconstrucción, ya que presenta unos resultados comparables a los del algoritmo de Tree reweighted message(TRWS) pero con unos tiempos de cálculo considerablemente superiores. En cuanto al algoritmo Iterated conditional models(ICM), resulta inadecuado prácticamente en la totalidad de los casos ya que presenta unos resultados muy pobres. Cuando la escena se complica, éste método produce mapas de disparidades en los que no se logran ni siquiera percibir los objetos dentro de la imagen.

8.2.

Términos de la función energía

La elección de los términos que forman la función objetivo es fundamental para obtener un buen mapa de correspondencias. A continuación se van a comparar los cuatro métodos implementados en Edata para las cinco imágenes y se intentará determinar cuál Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

92

I. M EMORIA § 8. R ESULTADOS

de ellos presenta unos resultados más reales. Se empleará el algoritmo sin métodos de preprocesado ni postprocesado, de esta manera, se analizará únicamente el efecto que tienen los términos de la función de energía. El método de optimización empleado será el Expansion, basado en corte de grafos ya que como se ha determinado anteriormente, presenta los mejores resultados con un tiempo de cálculo bastante corto. A continuación se muestra una tabla resumen con los resultados obtenidos:

Figura 63. Análisis de los términos de la función objetivo Las imágenes obtenidas para cada una de las pruebas se muestra a continuación. En todos los casos, arriba a la derecha se encuentra la solución con el cálculo de similitud píxel a píxel, a su lado se encuentra el cálculo con Edata igual a diferencia de cuadrados. Abajo a la derecha se encuentra la imágen obtenido por diferencia de cuadrados absoluta y gradiente y a la izquierda la imagen obtenida con término Edata en NCC.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

93

I. M EMORIA § 8. R ESULTADOS

Figura 64. Tsukuba para los distintos términos de la función objetivo

Figura 65. Aloe para los distintos términos de la función objetivo

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

94

I. M EMORIA § 8. R ESULTADOS

Figura 66. Baby para los distintos términos de la función objetivo

Figura 67. Cones para los distintos términos de la función objetivo

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

95

I. M EMORIA § 8. R ESULTADOS

Figura 68. Teddy para los distintos términos de la función objetivo Y por último, se representan los frentes de pareto de manera que se pueda establecer el término que mejor comportamiento presenta. Como en el apartado anterior, los gráficos se han separado para cada una de las imágenes debido a la diferencia de escalas.

Figura 69. Frente de pareto para tsukuba

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

96

I. M EMORIA § 8. R ESULTADOS

Figura 70. Frente de pareto para aloe

Figura 71. Frente de pareto para baby

Figura 72. Frente de pareto para cones

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

97

I. M EMORIA § 8. R ESULTADOS

Figura 73. Frente de pareto para teddy Como se puede observar, el término Edata que presenta unos mejores resultados es el de diferencia de intensidades. El término que realiza el cálculo de la similitud píxel a píxel también suele dar buenos mapas de disparidades. A raiz de los resultados obtenidos para todas las imágenes y todos los algoritmos propuestos, se puede concluir que estos dos métodos presentan actuaciones similares, ya que las fluctuaciones en tiempo y error entre ambos hacen que unas veces se considere mejor la aplicación del método de cálculo de similitud y otras la simple utilización de un algoritmo de diferencia de intensidades. En cuanto el método NCC, la literatura afirma que se trata de un buen método para el cálculo de correspondencias, pero en este caso se ha implementado en su forma más básica, lo que implica un coste computacional elevado. Para disminuir este inconveniente, se ha optado por disminuir el tamaño de la ventana de cálculo, de esta manera se pierde mucha calidad pero se realizan las correspondencias en un tiempo razonable. En cuanto al método de resolución mediante diferencia de cuadrado de intensidades y gradiente, el método ha resultado ser muy ineficaz ya que la determinación del gradiente por parte de los operadores Sobel, Roberts y Prewitt no ha dado buenos resultados, de hecho, el mejor resultado que se obtiene para este método se da cuando el peso relativo del término debido al gradiente es nulo.

8.3.

Algoritmos de resolución de correspondencias

De manera global, se puede estudiar la actuación de los distintos algoritmos empleados y determinar cuál presenta unos mejores resultados. Se analizarán los resultados obtenidos para la imagen tsukuba con el modelo Expansion basado en corte de grafos. A pesar de que los resultados que se muestran se limitan sólo a este caso, se

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

98

I. M EMORIA § 8. R ESULTADOS

puede comprobar que el resto de las pruebas realizadas arrojan unos resultados similares. A continuación se muestra la tabla en la que figuran todos los métodos con los errores cometidos en los mapas de disparidades así como los tiempos de ejecución. Se muestran en color azul turquesa el método más rápido (primera fila) y el que presenta menor error (quinta fila), por otro lado, la fila resaltada en color amarillo representa el modelo que obtiene un mejor compromiso entre los dos parámetros anteriores. Hay que tener en cuenta que el método de optimización elegido era uno de los más rápidos por lo tanto las pruebas que se realicen con otros modelos presentarán unos tiempos de ejecución mucho mayores.

Figura 74. Análisis global de los algoritmos Las imágenes obtenidas para estas pruebas han sido:

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

99

I. M EMORIA § 8. R ESULTADOS

Figura 75. Imagenes tsukuba para los distintos algoritmos Y por último el frente de Pareto que se ha obtenido es el siguiente:

Figura 76. Frente de pareto para tsukuba Se puede observar en el gráfico de Pareto cómo los métodos que presentan un mejor compromiso entre rapidez y bajo error se encuentran en la parte central de la gráfica. El algoritmo más rápido corresponde a la aplicación de un término Edata de cálculo de similitud, sin manejo de oclusiones ni métodos de preprocesado o postprocesado. El algoritmo con menor error es aquel que presenta el mismo término Edata y determinación de los planos de disparidades de la escena por el algoritmo

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

100

I. M EMORIA § 8. R ESULTADOS

RANSAC gracias al cálculo de oclusiones por LR-checking. Por otro lado, el algoritmo que mejor se ajusta a un tiempo de ejecución bajo y un error pequeño es el que utiliza el mismo término Edata y una determinación de planos de disparidades de la escena por el algoritmo RANSAC gracias al cálculo de oclusiones teniendo en cuenta la restricción de orden. Éste algoritmo se encuentra entre el más rápido y el de menor error dentro del frente de Pareto. Resulta interesante la comparación de nuestros resultados con los obtenidos en el resto de literatura. Por un lado, cabe destacar que el método NCC, que siempre aparece como uno de los métodos con mejor aproximación del mapa de disparidades, obtiene en nuestro caso unos resultados muy pobres. Como ya se ha señalado anteriormente, ésto puede ser debido a la necesidad de tomar ventanas pequeñas para la realización de los cálculos de similitud entre píxeles ya que de otra manera el tiempo de cálculo aumentaría de manera muy considerable impidiendo que el algoritmo pudiera ser usado en tiempo real. Como ya se señaló en el capítulo 5, existen multitud de aproximaciones[56, 57] de este algoritmo mucho más rápidas y con las que probablemente se obtengan unos mejores resultados en tiempo y error. En los distintos artículos que tratan el método de cálculo de similitud píxel a píxel[8], este método presenta unos resultados bastante buenos dada la simplicidad del método y se ha comprobado a partir de las pruebas realizadas anteriormente que estos resultados siguen cumpliendose en nuestro caso. Los algoritmos que incluyen el gradiente de la imagen como parámetro de cálculo de la similitud no presentan muy buenos resultados,pero si se observan con mayor atención los resultados obtenidos de la aplicación de los distintos filtros de determinación del gradiente, podrá comprobarse que dichos filtros no ofrecen unos buenos resultados,por lo que no se puede concluir que este tipo de métodos presente unos resultados malos ya que sería preciso en primer lugar encontrar algún filtro que determinara correctamente el gradiente. Los algoritmos que se sirven de la estimación de lás disparidades de los píxeles ocluidos determinando planos de disparidad, es decir, los modelos RANSAC y LMS, presentan unos resultados muy buenos aunque se comprueba como en ambos casos el método de determinación de los píxeles ocluidos, que puede ser Left-Right check u ordering constraint, hace que varien considerablemente los tiempos de cálculo ya que en el primer caso se hace preciso implementar el algoritmo dos veces mientras que en el caso de OC esto es innecesario. Por lo tanto, los métodos de refinamiento por mapas de disparidad son muy adecuados siempre y cuando el tiempo de ejecución no sea crítico.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

101

I. M EMORIA § 8. R ESULTADOS

Por otro lado, a pesar de que en la literatura se recomienda a veces el uso de filtros que suavicen la imagen y mejoren el mapa de disparidades, en este caso se ha comprobado que su validez es muy dependiente del tipo de imagen de salida que se obtenga, por lo tanto parece que no tiene mucho sentido aplicar filtros en todos los casos, su aplicación deberá ser estudiada para cada caso particular. Esto explica porque un paso tan sencillo como éste no es utilizado como técnica de post procesado en todos los métodos de la literatura. Por último, en cuanto a los modelos globales, se tiene poca información en la literatura, sin embargo, en todos los artículos se ponen de manifiesto sus buenos resultados. A raiz de las imagenes obtenidas a partir de este método se puede comprobar que en nuestro caso la actuación de los métodos globales es muy adecuada.

8.4.

Valoración del mejor algoritmo frente a otros métodos

Una vez determinado el algoritmo que presenta el mejor mapa de disparidades, que como se ha señalado en la tabla de la Figura 74 se trata de el algoritmo que presenta como término Edata un cálculo de similitud píxel a píxel, método de optimización Expansion de corte de grafos y refinamiento de la imagen mediante algoritmo RANSAC y método de detección de oclusiones por ordering constraint, se puede comprobar la eficacia del mismo comparándolo con los algoritmos que en la literatura obtienen los mejores resultados. La página de la universidad de Middlebury[58] ofrece un ranking de dichos algoritmos, que permite incorporar a cualquier persona sus resultados de manera que pueda compararlos con los papers más relevantes. A continuación se muestran los resultados obtenidos, nuestro algoritmo se encuentra en el puesto 15 de la lista sólo teniendo en cuenta el resultado para la imagen tsukuba con un porcentaje de píxeles erróneos del 5.31 %. Se observa que este resultado es inferior al obtenido por nuestro algoritmo, esto se debe a que el umbral establecido para considerar los píxeles como erróneos es diferente en nuestro método de cálculo de error y el que aparece implementado en la página. También se ha utilizado la imagen cones para determinar el error y observar el puesto que ocupa. Los resultados obtenidos no han sido tan destacables como en el caso de la primera imagen. El algoritmo se encuentra alrededor del puesto 40. La principal

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

102

I. M EMORIA § 8. R ESULTADOS

dificultad que presenta esta imagen es que se trata de una escena más complicada y el número de disparidades requeridas para representarla es muy superior al caso de tsukuba.

Figura 77. Ranking de la universidad de Middlebury

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

103

Capítulo 9 Conclusiones utilización de técnicas de optimización para la determinación de los mapas de disparidades a partir de imágenes captadas en estéreo ha probado ser un método bastante eficiente, no sólo a nivel de la calidad final del mapa de disparidades obtenido sino también en cuanto a tiempos de cálculo. En la reconstrucción tridimensional a través de métodos globales de optimización es necesario tener en cuenta multitud de factores, la elección del método de optimización, la forma que presentará la función objetivo que se desea minimizar, el preprocesado que se realice sobre la imagen y todas las técnicas de post procesado que persigan la mejora del mapa de disparidades.

L

A

En cuanto a las técnicas de preprocesado, se trata en general de algoritmos que son imprescindibles en un gran número de ocasiones para poder proseguir con un tratamiento de la imagen posterior. Se ha estudiado la actuación de la técnica de segmentación por desplazamiento de la media, o en inglés Mean shift segmentation, ya que se trata de uno de los mejores métodos para el cálculo de los objetos dentro de la imagen. Los resultados que se obtienen son de gran calidad y el tiempo necesario para obtenerlos es muy pequeño. Se ha mostrado cómo la imagen segmentada resulta de gran utilidad cuando se quiere realizar un refinamiento de la imagen a través de los planos de disparidad que forman la imagen, de manera que el problema se divide en partes más pequeñas y se puede manejar con mayor facilidad. Por otro lado, la selección del método de optimización una vez que la imagen está preparada ha resultado ser fundamental. A raiz de los resultados obtenidos, se puede concluir que los métodos que mejor se adaptan a las especificaciones de tiempo y de bajo nivel de error son el método Expansion, que es un tipo de algoritmo basado en corte de grafos, y el método BPS, que es una variante simplificada de Belief propagation. De cualquier manera, todos estos métodos resultan muy sensibles al tipo de imagen, así practicamente la totalidad de los algoritmos presentan un buen comportamiento en las pruebas con la imagen tsukuba pero tanto los tiempos de cálculo como el error Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

104

I. M EMORIA § 9. C ONCLUSIONES

aumentan considerablemente cuando la estructura de la imagen presenta formas más complicadas. La elección de los términos de la función objetivo que debe ser minimizada gracias a los métodos anteriores hace variar considerablemente la calidad de la respuesta, si bien los tiempos no suelen verse demasiado influidos por la elección particular de alguno de ellos. Los mejores mapas de disparidades han sido atribuidos a los términos Edata de tipo diferencia de intensidades absolutas y cálculo de similitud píxel a píxel, que son a su vez los más sencillos dentro de todos aquellos que han sido estudiados. Para realizar una buena reconstrucción tridimensional hay que tener muy en cuenta las peculiaridades que diferencian a los mismos. En escenas sencillas y de luminosidad homogénea el método de diferencia de intensidades es bastante eficaz pero en aquellos casos en los que la iluminación de la escena varía mucho, resulta insuficiente y se hace obligado el uso de un término Edata de cálculo de similitud píxel a píxel. Otro parámetro a tener en cuenta son las oclusiones. En muchas imágenes, estos puntos pueden llevar a obtener una imagen con un gran número de errores. Para evitar esto se han implementado distintos métodos. Los métodos que detectan oclusiones por sí solos no presentan ninguna utilidad, ya que sólo informan de aquellos píxeles que se encuentran ocluidos. Los métodos que disminuyen la sensibilidad a las oclusiones han demostrado ser en cambio de gran utilidad, entre ellos se han estudiado los algoritmos RANSAC y LMS, obteniendose resultados similares pero con un error ligeramente superior en el segundo caso y tiempos de ejecución considerablemente superiores, por lo que se ha preferido el uso del algorimto RANSAC frente a LMS. También se han estudiado los métodos que modelan la geometría de la oclusión, es decir, que no tratan el problema de las oclusiones a posteriori sino que incluyen un nuevo término en la función objetivo que las modele. La actuación de este tipo de métodos ha resultado ser buena pero no tanto como la de RANSAC o LMS. Por último, se puede proceder a realizar técnicas de post procesado sobre las imágenes. Entre las que se han estudiado, se tienen por un lado los filtros, que se encargan de mejorar la calidad de la imagen mediante la aplicación de máscaras de convolución, y por otro lado la estimación de subpíxeles dentro de la imagen. En el primer caso, los filtros han resultado ser bastante ineficientes luego no se barajan como posible técnica de mejora de la calidad de la imagen a posteriori. En el caso de la estimación de los subpíxeles, la reconstrucción final de la escena no ha sido demasiado buena, este método tiende a emborronar la imagen y a arrastrar las malas estimaciones a otras regiones del mapa de disparidades.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

105

I. M EMORIA § 9. C ONCLUSIONES

En conclusión, existen una gran cantidad de métodos para abordar el problema, la literatura es extensa y cada vez se van descubriendo nuevos métodos debido a la necesidad de encontrar un algoritmo definitivo que resuelva la reconstrucción tridimensional de una escena. Las técnicas que se han implementado se encuentran todas ellas entre las más conocidas dentro de la visión estéreo y si bien no todas ofrecen unos resultados óptimos, en la mayoría de los casos el mapa de disparidades resulta muy aproximado a la escena real.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

106

Capítulo 10 Futuros desarrollos ya se ha señalado en el capítulo de introducción, los métodos de reconstrucción son muy variados. Dentro de la reconstrucción de los mapas de disparidades densos, que en un principio se perfilan como los más importantes dentro de la visión estéreo, los métodos globales son los más utilizados aunque podría ser interesante realizar un estudio exhaustivo sobre métodos cooperativos[52] para obtener una visión más global de la reconstrucción tridimensional por medio de imágenes en estéreo.

C

OMO

Dentro de los métodos globales, también existen multitud de algoritmos que no han podido ser abordados en este proyecto, resultan especialmente interesantes: La creación de métodos de optimización mucho más flexibles[54] que permitan la utilización de otros términos dentro de la función objetivo de manera que los posibles problemas que puedan surgir en el mapa de correspondencias se traten a priori sin necesidad de etapas de post-procesado. La utilización del método Dynamic programming[55] para la obtención de los mapas de disparidad. Entre las ventajas que aparecen en la literatura para este tipo de optimización se encuentra el bajo coste computacional y los buenos resultados. La implantación de un método de post procesado basado en algoritmos de super resolución[53], que parecen haber adquirido una gran popularidad en los últimos años y permiten mejorar en gran medida el mapa de disparidades. La investigación de nuevos métodos para la detección de los puntos ocluidos en la imagen que presenten mayor complejidad que los abordados en este proyecto. Entre los trabajos ya desarrollados, cabe citar el artículo[54] de la universidad de Hong Kong, que ocupa el cuarto puesto en el ranking de Middlebury Stereo Vision.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

107

I. M EMORIA § 10. F UTUROS DESARROLLOS

Otra aportación más que podría ser interesante es la creación de un entorno gráfico que permitiera ir más allá de la simple representación de un mapa de disparidades plano mediante la ubicación de los distintos objetos o segmentos que forman la escena a distintos planos de profundidad, de manera que la sensación de tridimensionalidad no se perdiera en ningún momento como en el ejemplo de la Figura 78.

Figura 78. Ejemplo de la reconstrucción tridimensional de la escena[53]

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

108

Bibliografía [1] S. T. Barnard and M. A. Fischler, Computational Stereo. ACM Computing Surveys, vol.14, pp. 553-572, 1982. [2] U. R. Dhond and J. K. Aggarwal, Structure from Stereo - A Review. IEEE Trans.Systems, Man, and Cybernetics, vol. 19, pp. 1489-1510, 1989. [3] V. Venkateswar and R. Chellappa, Hierarchical Stereo and Motion Correspondence Using Feature Groupings. Int’l J. Computer Vision, vol. 15, pp. 245-269, 1995. [4] S. Birchfield and C. Tomasi, Multiway Cut for Stereo and Motion with Slanted Surfaces. Proc. Int’l Conf. Computer Vision, vol. 1, pp. 489-495, 1999. [5] S. Randriamasy and A. Gagalowicz, Region Based Stereo Matching Oriented Image Processing. Proc. Computer Vision and Pattern Recognition, pp. 736-737, 1991. [6] Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, November 2001. [7] R. Szeliski and D. Scharstein, Symmetric sub-pixel stereo matching. In Seventh European Conference on Computer Vision,ECCV 2002, volume II, Copenhagen, May 2002. Springer-Verlag. [8] D. Scharstein and R. Szeliski, A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms. Int’l J. Computer Vision, vol. 47, no. 1, pp. 7-42, 2002. [9] Besag, J., On the statistical analysis of dirty pictures (with discussion).. Journal of the Royal Statistical Society, Series B 48 (1986) 259-302 [10] D. Scharstein and R. Szeliski., Stereo matching with nonlinear diffusion.. IJCV, 28(2):155-174, 1998.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

109

I. M EMORIA § B IBLIOGRAFÍA

[11] C. L. Zitnick and T. Kanade., A cooperative algorithm for stereo matching and occlusion detection.. IEEE TPAMI, 22(7):675-684, 2000. [12] P. N. Belhumeur and D. Mumford, A Bayesian treatment of the stereo correspondence problem using half-occluded regions.. In CVPR, pages 506-512, 1992. [13] P. N. Belhumeur, A Bayesian approach to binocular stereopsis.. IJCV, 19(3):237260, 1996. [14] D. Geiger, B. Ladendorf, and A. Yuille., Occlusions and binocular stereo.. In ECCV, pages 425-433, 1992. [15] I. J. Cox, S. L. Hingorani, S. B. Rao, and B. M. Maggs., A maximum likelihood stereo algorithm.. CVIU, 63(3):542-567, 1996. [16] A. F. Bobick and S. S. Intille, Large occlusion stereo.. IJCV, 33(3):181-200, 1999. [17] Kolmogorov, V., Zabih, R., What energy functions can be minimized via graph cuts?. IEEE Trans Pattern Anal Mach Intell 26 (2004) 147-59 [18] J. Sun, H. Y. Shum and N. N. Zheng, Stereo Matching Using Belief Propagation. Proc. European Conf. Computer Vision, pp. 510-524, 2002. [19] S. T. Barnard, Stochastic stereo matching over scale.. IJCV, 3(1):17-32, 1989. [20] S. Geman and D. Geman, Stochastic relaxation, Gibbs distribution,and the Bayesian restoration of images.. IEEE TPAMI, 6(6):721-741, 1984. [21] J. Marroquin, S. Mitter, andT. Poggio., Probabilistic solution of ill-posed problems in computational vision.. Journal of the American Statistical Association, 82(397):76-89, 1987. [22] Kolmogorov, V., Convergent tree-reweighted message passing for energy minimization.. In: AISTATS. (2005) [23] Wainwright, M.J., Jaakkola, T.S., Willsky, A.S., AP estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches.. IEEE Trans Info Theory 51 (2005) [24] Richard Szeliski, Ramin Zabih, Daniel Scharstein,Olga Veksler, Vladimir Kolmogorov, Aseem Agarwala,Marshall Tappen, and Carsten Rother, A Comparative Study of Energy Minimization Methods for Markov Random Fields. ECCV 2006, Part II, LNCS 3952, pp. 16-29, 2006. Springer-Verlag Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

110

I. M EMORIA § B IBLIOGRAFÍA

[25] Stan Birchfield and Carlo Tomasi, A Pixel Dissimilarity Measure That Is Insensitive to Image Sampling. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 20, NO. 4, APRIL 1998 [26] L. H. Matthies, R. Szeliski, and T. Kanade, Kalman filter-based algorithms for estimating depth from image sequences.. International Journal of Computer Vision, 3:209-236, 1989. [27] Q. Tian and M. N. Huhns, Algorithms for subpixel registration.. Computer Vision, Graphics, and Image Processing, 35:220-233, 1986. [28] Vladimir Kolmogorov y Ramin Zabih, Computing Visual Correspondence with Occlusions via Graph Cuts.. International Conference on Computer Vision, pp. [29] Qingxiong Yang, Liang Wang, Ruigang Yang, Henrik Stewénius, David Nistér, Stereo Matching with Color-Weighted Correlation, Hierarchical Belief Propagation, and Occlusion Handling. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 31, NO. 3, MARCH 2009 [30] C. L. Zitnick and T. Kanade, A cooperative algorithm for stereo matching and occlusion detection.. IEEE TPAMI, 22(7):675-684, 2000. [31] H. Ishikawa and D. Geiger, Occlusions, discontinuities, and epipolar lines in stereo. In ECCV, pages 232-248, 1998. [32] V. Kolmogorov and R. Zabih, Computing visual correspondence with occlusions using graph cuts. In ICCV, volume II, pages 508-515, 2001. [33] D. Comaniciu and P. Meer, Mean shift: A robust approach toward feature space analysis. IEEE:PAMI, 24(5):603-619,May 2002. [34] D. Comaniciu and P. Meer, Mean Shift Analysis and Applications. IEEE Int’l Conf. Comp. Vis., Kerkyra, Greece, pp. 1197-1203, 1999. [35] Q. Yang, R. Yang, J. Davis, and D. Nistér, Spatial-depth super resolution for range images. CVPR 2007 [36] Hartley, R; Zisserman, A., Multiple View Geometry in Computer Vision.. Cambridge University Press. 2001 Primera edición. Londres. [37] Y. Boykov and Vladimir Kolmogorov., An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision.. In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 26, no. 9, pages 1124-1137, September 2004.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

111

I. M EMORIA § B IBLIOGRAFÍA

[38] R. Zabih, Y. Boykov, O. Veksler., System and method for fast approximate energy minimization via graph cuts. United Stated Patent 6,744,923, June 1, 2004. [39] M. F. Tappen and W. T. Freeman., Comparison of Graph Cuts with Belief Propagation for Stereo, using Identical MRF Parameters. . In Proceedings of the Ninth IEEE International Conference on Computer Vision (ICCV), pages 900-907, 2003 [40] M. J. Wainwright, T. S. Jaakkola and A. S. Willsky., MAP estimation via agreement on trees: Message-passing and linear-programming approaches. . In IEEE Transactions on Information Theory, vol. 51, no. 11, pages 3697-3717, November 2005. [41] V. Kolmogorov., Convergent Tree-reweighted Message Passing for Energy Minimization. . In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 28, no. 10, October 2006. [42] Ruo Zhang, Ping-Sing Tsai, James Edwin Cryer and Mubarak Shah, Shape from Shading: A Survey. School of Computer Science. University of Central Florida [43] Tsai, Roger Y., A Versatile Camera Calibration Technique for High- Accuracy 3D Machine Vision Metrology Using Off-the-Shelf TV Cameras and Lenses. IEEE Journal of Robotics and Automation, Vol. RA-3, No. 4, August 1987, pp. 323-344. [44] M. Z. Brown, D. Burschka and G. D. Hager, Advances in computational stereo. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 8, AUGUST 2003 [45] M.P. Wand and M. Jones, Kernel Smoothing. Chapman and Hall, 1995 [46] D. Comaniciu, V. Ramesh and P. Meer., The Variable Bandwidth Mean Shift and Data-Driven Scale Selection. Proceedings 8th International Conference on Computer Vision, Vancouver, Canada, volumen I, July 2001, pp.438-445. [47] Code for the Edge Detection and Image SegmentatiON system(EDISON) Aplicación para el cálculo de la segmentación y el filtrado por mean shift. Última visita: 28/05/2010 Rutgers University. [48] Andreas Klaus, Mario Sormann and Konrad Karner, Segment-Based Stereo Matching Using Belief Propagation and a Self-Adapting Dissimilarity Measure. 18th International Conference on Pattern Recognition (ICPR’06) Volume 3

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

112

I. M EMORIA § B IBLIOGRAFÍA

[49] M.A. Fischler and R.C. Bolles, Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Comm. ACM, vol. 24, pp. 381-395,1981. [50] D.M. Greig, B.T. Porteous and A.H. Seheult, Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society Series B, 51, 271-279. (1989) [51] M.J. Wainwright, T.S. Jaakkola, and A.S. Willsky, MAP estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches. IEEE Transactions on Information Theory, 51(11):3697 3717, November 2005. [52] Zeng-Fu Wang, Zhi-Gang Zheng, A Region Based Stereo Matching Algorithm Using Cooperative Optimization. University of Science and Technology of China [53] Q. Yang, R. Yang, J. Davis, and D. Nistér, Spatial-depth super resolution for range images. CVPR 2007 [54] L. Xu and J. Jia., Stereo matching: an outlier confidence approach.. ECCV 2008. [55] O. Veksler., Stereo correspondence by dynamic programming on a tree. CVPR 2005. [56] Peter Nillius and Jan-Olof Eklundh, Fast Block Matching with Normalized Cross-Correlation using Walsh Transforms. Computational Vision and Active Perception Laboratory (CVAP). [57] J. P. Lewis, Fast Normalized Cross-Correlation. Industrial Light & Magic [58] Middlebury Stereo Vision Page Página web de prueba de algoritmos. Última visita: 10/05/2010 Middlebury College

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

113

TML

PARTE II

MANUAL DE USUARIO

II. M ANUAL DE USUARIO § B IBLIOGRAFÍA

Con el fin de facilitar el manejo de los códigos al usuario, se ha creado una interfaz gráfica que permite realizar las pruebas sobre las distintas imágenes y para todos los algoritmos posibles de manera sencilla, sin necesidad de conocer C++ ni las particularidades del código empleado para realizar dichas pruebas.

0.1.

Características de la interfaz

La apariencia de la interfaz de usuario se muestra en la Figura 79.

Figura 79. Interfaz de usuario En primer lugar, se procederá a explicar las distintas opciones que se encuentran en la pantalla así como la forma de combinarlas.

1. Menú desplegable : En este menu se pueden seleccionar las distintas imágenes sobre las que realizar las pruebas. Como a lo largo de toda la memoria, las imágenes con las que se trabaja son:

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

115

II. M ANUAL DE USUARIO § B IBLIOGRAFÍA

Figura 80. Imagenes de prueba 2. Menú desplegable : En este menú se seleccionan los distintos métodos de optimización. Las seis opciones habilitadas son: ICM: Iterated conditional modes Cortes de grafos-Swap: Algoritmo de corte de grafos por intercambio de etiquetas α Cortes de grafos-Expansion: Algoritmo de corte de grafos por expansión de etiquetas α y β MaxProdBP: Algoritmo Belief Propagation de tipo max-producto BPS: Algoritmo Belief Propagation simplificado TRWS: Tree reweighted message passing 3. Menú desplegable : Permite seleccionar cualquiera de los métodos que se han implementado y desarrollado teóricamente a lo largo de la memoria. Las posibilidades que existen son: Birchfield Simple: Modela el término Edata de la función objetivo Diferencia de intensidades: Modela el término Edata de la función objetivo Diferencia cuadrado+gradiente: Modela el término Edata de la función objetivo NCC: Modela el término Edata de la función objetivo RANSAC+LRcheck+Meanshift: Algoritmo de tratamiento de oclusiones Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

116

II. M ANUAL DE USUARIO § B IBLIOGRAFÍA

RANSAC+OC+Meanshift: Algoritmo de tratamiento de oclusiones Modelo global: Algoritmo de tratamiento de oclusiones Estimacion subpixel: Método de post procesado una vez conocido el mapa de disparidades Filtro media: Método de post procesado una vez conocido el mapa de disparidades Filtro media ponderada: Método de post procesado una vez conocido el mapa de disparidades Filtro mediana: Método de post procesado una vez conocido el mapa de disparidades Filtro mediana NCC: Método de post procesado una vez conocido el mapa de disparidades LMS+Meanshift: Algoritmo de tratamiento de oclusiones LMS+Meanshift+Filtro mediana: Algoritmo de tratamiento de oclusiones Modelo global+Filtro mediana: Algoritmo de tratamiento de oclusiones 4. Botón de ejecutar: Una vez seleccionados todos los menús desplegables anteriores, se hará click sobre este botón para que se ejecute el fichero .exe que devolverá el mapa de disparidades 5. Ejes: Lugar donde aparece la imagen seleccionada 6. Botón para cargar la imagen seleccionada. Una vez se haga click sobre este botón, aparecerá la imagen en los ejes 7. Botón para cargar el mapa de disparidades obtenido de la imagen seleccionada. Una vez se haga click sobre este botón, aparecerá la imagen en los ejes 8 8. Ejes: Lugar donde aparece el mapa de disparidades 9. Botón para el cálculo del error: Una vez se haga click sobre este elemento, aparecerán reflejados en los cuadros de texto el error asociado a la desviación respecto al mapa de disparidades real y el error porcentual. Por otro lado, el usuario tiene la opción de manejar directamente los ejecutables que lanza la aplicación de matlab. En ese caso, existe un ejecutable para cada opción elegida dentro del interfaz, para acceder al mismo, sólo será preciso acceder a la carpeta que se desee (vienen definidas por Algoritmo+Método de optimización+Nombre de imagen) y ejecutar el fichero .exe que se encuentra dentro de la carpeta Release, sin necesidad de

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

117

II. M ANUAL DE USUARIO § B IBLIOGRAFÍA

modificar parámetros desde fuera. En el caso de que el usuario quiera lanzar el ejecutable con sus propias modificaciones, deberá acceder al código C++ que se encuentra en la carpeta, realizar las modificaciones oportunas y ejecutar de nuevo el programa. Se puede modificar la imagen seleccionada, el número de disparidades que se desean en el mapa de disparidad (nD), los valores de escala (outscale) y el tipo de optimización (ICM, MaxProd,etc.), el lugar en el que se deben realizar estos cambios se encuentra claramente indicado en el código.

0.2.

Utilización de la interfaz

Los pasos a seguir para trabajar correctamente con esta interfaz serán los siguientes: 1. Abrir el programa MATLAB 2. Escribir en la ventana de comandos: reconstruccion. Se abrirá entonces la interfaz de usuario y se podrá comenzar a trabajar sobre la misma. 3. Seleccionar en los distintos menús desplegables los métodos con los que se desean relizar las pruebas. Es importante tener en cuenta que si el método que se quiere seleccionar aparece como prefijado en el menú no significa que lo esté. Siempre se deberá seleccionar la opción elegida. 4. Presionar el botón Ejecutar 5. Presionar el botón: Cargar imagen. Aparecerá la escena que ha sido seleccionada en el menú desplegable en los ejes superiores. 6. Esperar un cierto tiempo hasta que en la ventana de comandos de matlab se refleje que el fichero .exe ha terminado de ejecutarse. Se reconocerá porque el programa devuelve un cero. 7. Presionar el botón: Mapa de disparidades. Se cargará sobre los ejes superiores la imagen obtenida del mapa de disparidades. 8. Una vez realizados todos los pasos anteriores se puede proceder a la determinación del error cometido presionando el botón:Calcular error. 9. Cuando el usuario haya terminado de realizar sus pruebas, se procederá a cerrar la ventana y el interfaz quedará cerrado. Como se puede observar, el manejo del programa es muy sencillo y evita que sea el propio usuario el que se encargue de modificar los códigos para obtener resultados con otros métodos de optimización o imágenes. Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

118

TML

DOCUMENTO II

PLIEGO DE CONDICIONES

Índice 1. Condiciones generales y económicas 1.1. Condiciones generales . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Condiciones económicas . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4

2. Condiciones técnicas y particulares 2.1. Equipo informático . . . . . . . 2.2. Normas de calidad . . . . . . . 2.3. Normas de Seguridad e Higiene 2.4. Vida útil del producto . . . . . .

5 5 5 5 5

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

2

Capítulo 1 Condiciones generales y económicas 1.1.

Condiciones generales

Las condiciones y cláusulas que se establecen en este documento son de obligado cumplimiento por las partes contratantes.

1. Tanto el administrador como el cliente se comprometen desde la fecha de la firma del contrato a llevar a cabo lo que se estipule. 2. Ante cualquier reclamación o discrepancia en lo concerniente al cumplimiento de lo pactado por cualquiera de las partes, una vez agotada toda vía de entendimiento, se tramitará el asunto por la vía de lo legal. El dictamen o sentencia que se dicte será de obligado cumplimiento para las dos partes. 3. Al firmarse el contrato, el suministrador se compromete a facilitar toda la información necesaria para la instalación y buen funcionamiento del sistema, siempre que sea requerido para ello. 4. Asimismo, el cliente entregará al suministrador todas las características distintivas del equipo comprado y aquellas otras que considere oportunas para el necesario conocimiento de la misma a efectos del diseño del presente equipo. 5. El plazo de entrega será de tres meses, a partir de la fecha de la firma del contrato, pudiendo ampliarse en un mes. Cualquier modificación de los plazos deberá contar con el acuerdo de las dos partes. 6. En caso de retrasos imputables al suministrador, se considerará una indemnización del 1 % del valor estipulado por semana de retraso. 7. Existirá un plazo de garantía de un año a partir de la entrega del sistema. Dicha garantía quedará sin efecto si se demostrase que el sistema ha estado sometido a manipulación o uso indebido. Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

3

D OCUMENTO II. P LIEGO DE CONDICIONES § 1. C ONDICIONES GENERALES Y ECONÓMICAS

8. Cumplido dicho plazo de garantía, el suministrador queda obligado a la reparación del sistema durante un plazo de cinco años, fuera del cual quedará a su propio criterio atender la petición del cliente. 9. En ningún momento tendrá el suministrador obligación alguna frente a desperfectos o averías por uso indebido por personas no autorizadas por el suministrador.

1.2.

Condiciones económicas

1. Los precios indicados en este proyecto son firmes y sin revisión por ningún concepto, siempre y cuando se acepten dentro del periodo de validez del presupuesto que se fija hasta Diciembre de 2001. 2. El pago se realizará como sigue: h 75 % a la firma del contrato. h 25 % en el momento de entrega. 3. La forma de pago será al contado mediante cheque nominativo o mediante transferencia bancaria. En ningún caso se aceptarán letras de cambio. 4. El suministrador se hará cargo de los gastos de embalaje y del transporte, dentro de la ciudad donde se encuentre la instalación. En caso de ser necesario transporte interurbano, el gasto correrá por cuenta del cliente. En todo caso, elresponsable de los posibles desperfectos ocasionados por el transporte será el suministrador. 5. Durante el plazo de garantía, la totalidad de los gastos originados por las reparaciones correrán por cuenta del suministrador. 6. Fuera de dicho plazo y durante los siguientes cinco años, los costes serán fijados mediante acuerdo por ambas partes. Pasados 5 años, éstos los fijará exclusivamente el suministrador.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

4

Capítulo 2 Condiciones técnicas y particulares 2.1.

Equipo informático

El equipo informático debe estar homologado conforme a la normativa Europea y Española a fecha de Junio de 2001. El equipo informático debe instalarse conforme a las indicaciones del fabricante, manteniendo las condiciones de humedad y temperatura entre los límites marcados. Los programas informáticos empleados han de contar con la licencia preceptiva y cumplir con las condiciones de la misma. En caso de usar programas de licencia GNU, se deberán respetar las condiciones de la misma.

2.2.

Normas de calidad

Los sistemas se diseñarán de forma que cumplan las normas UNE, CEI y EN aplicables a este tipo de productos, así como las normas ETSI (European Telecommunications Standards Institute) para sistemas de radiofrecuencia.

2.3.

Normas de Seguridad e Higiene

El proyecto cumplirá con la Ley 31/95 de Prevención de Riesgos Laborales.

2.4.

Vida útil del producto

Los sistemas se diseñarán para una vida útil no inferior a 10 años en funcionamiento continuo.

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

5

TML

DOCUMENTO III

PRESUPUESTO

Índice 1. Coste del sistema 1.1. Introducción . . . . . 1.2. Equipo necesario . . 1.3. Coste Mano de Obra 1.4. Presupuesto total . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

3 3 3 4 4

2

Capítulo 1 Coste del sistema 1.1.

Introducción

A pesar de que el análisis teórico y la aplicación práctica de los sistemas de reconstrucción a partir de imágenes en estéreo y técnicas de optimización ha dado unos buenos resultados, la viabilidad del proyecto fuera del ámbito académico se ve influenciada en fuerte medida por el coste asociado al desarrollo e implantación de este tipo de sistemas en las empresas. Por este motivo, se hace necesaria la realización de un presupuesto que permita a la empresa conocer de antemano los gastos en los que incurrirá al incorporar las técnicas desarrolladas en esta memoria en los dispositivos que fabrican, entre ellos, pueden encontrarse cualquier tipo de sistema autónomo, sistemas de control de la producción en naves industriales o aplicaciones de realidad virtual. En este capítulo, se llevará a cabo el cálculo de dicho presupuesto, dividiendo los costes en función del equipo necesario y de la mano de obra.

1.2.

Equipo necesario

El coste del servidor y del software necesario de los que debería disponer la empresa asciende a: Ordenador: 900e Entorno de programación Microsoft Visual Studio: 520e Programa MATLAB 7.7 R2008b: 6000e Coste total del servidor: 7420e

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

3

D OCUMENTO III. P RESUPUESTO § 1. C OSTE DEL SISTEMA

1.3.

Coste Mano de Obra

Teniendo en cuenta que el coste por hora de un ingeniero es de 60e/hora y que el número de horas total empleadas en la realización del proyecto es de 550 horas divididas en : 100 horas invertidas en el estudio y lectura de documentación previa. 300 horas invertidas en el desarrollo de los algoritmos. 150 horas en la realización de pruebas con imágenes El total de la mano de obra asciende a 33000e

1.4.

Presupuesto total

Descripción

Precio

Coste Equipo Coste Mano de Obra

7420e 33000e

TOTAL EQUIPO

40420e

Reconstrucción tridimensional mediante visión estéreo y técnicas de optimización María Saiz Muñoz

4