Repositorio Institucional de Documentos

UNIVERSIDAD DE ZARAGOZA Proyecto de Fin de Carrera de Ingeniería Informática Reconocimiento y registro 3D de objetos conocidos en una escena Curso Académico: 2009-2010 Fecha: Septiembre 2010 Departamento de Informática e Ingeniería de Sistemas Centro Politécnico Superior Autor: Félix Valdivielso Miranda Director: Luis Montesano Codirector: Javier Civera Reconocimiento y registro 3D de objetos conocidos en una escena RESUMEN El proyecto se inicia con la reconstrucción densa de una escena 3D a partir de imágenes en dos pasos. Con el primero de ellos se obtendrá la posición 3D de las cámaras usando la técnica conocida como Bundle Adjustment. En un segundo paso, a partir de estas localizaciones y mediante restricciones proyectivas se densificará la reconstrucción 3D de la escena. En esta primera fase del proyecto se desarrollará un visor 3D el cual nos permitirá manipular y visualizar el entorno 3D obtenido a partir de los programas mencionados previamente y que nos será de utilidad para la aplicación final. La segunda fase del proyecto se plantea el reconocimiento de objetos a partir de imágenes. El reconocimiento se realizará basado en características salientes en la imagen. En primer lugar se creará una pequeña base de datos con imágenes de un conjunto de objetos y su reconstrucción densa. En segundo lugar, se buscará en la escena los objetos de la base de datos mediante la comparación de descriptores asociados a las características salientes. Para ello será necesario el desarrollo de una aplicación que nos permita comparar las imágenes de los diferentes objetos de nuestra base de datos con las imágenes de la escena y ver así si los objetos de la base de datos aparecen o no en la escena. Una vez el objeto ha sido reconocido en la escena se pretende sustituir en el modelo 3D de dicha escena la reconstrucción 3D del objeto (por ejemplo, un libro) disponible en nuestra base de datos, permitiéndonos así visualizar en la escena 3D partes del libro que no se veían en las imágenes de la escena. Para ello será necesaria una tercera y última fase en el proyecto donde se deberá posicionar los modelos 3D de los objetos que disponemos en la base de datos y que aparecen en la escena. Agradecimientos: A mis padres por apoyarme en todo momento. A mi hermana por estar siempre animándome. A mis amigos por hacerme los días más amenos. A mi abuela por preocuparse por cómo me iba el proyecto. A mi director y codirector por su ayuda durante el proyecto. i TABLA DE CONTENIDOS 1. Introducción.............................................................................................................. 1 1.1 Objetivo y Resumen del proyecto........................................................................... 3 1.2 Aplicaciones del Proyecto ....................................................................................... 7 1.2.1 Realidad Aumentada ....................................................................................... 7 1.2.2 Robótica ........................................................................................................... 8 2. Obtención de Datasets ........................................................................................... 11 3. Reconstrucción 3D a partir de imágenes................................................................ 13 3.1. Reconstrucción 3D no densa............................................................................ 13 3.1.1. Explicación del proceso............................................................................. 16 3.2. Reconstrucción 3D densa................................................................................. 19 3.2.1. Explicación del proceso............................................................................. 23 3.3. Visor 3D ............................................................................................................ 25 3.4. Resultados ........................................................................................................ 27 4. Correspondencias entre puntos ................................................................................. 31 4.1 SIFT ........................................................................................................................ 31 4.1.1 Calculo de los descriptores ............................................................................ 33 4.2 SURF ...................................................................................................................... 39 4.2.1 Calculo de descriptores ................................................................................. 39 4.3 MSER ..................................................................................................................... 43 4.4 Comparativa .......................................................................................................... 45 4.4.1 SIFT vs SURF ................................................................................................... 45 4.4.2 MSER .............................................................................................................. 48 ii 4.4 Aplicación de emparejamiento ............................................................................. 49 4.4.1 Algoritmo desarrollado para el emparejamiento.......................................... 50 4.4.2 Explicación del algoritmo............................................................................... 51 4.5 Resultados ............................................................................................................. 53 4.5.1 Primeros Resultados ...................................................................................... 53 4.5.2 Resultados con el segundo dataset ............................................................... 57 5. Posicionamiento de los objetos en la escena ............................................................. 61 5.1 Calculo de la matriz fundamental ......................................................................... 62 5.2 Calculo de la matriz esencial y las matrices de calibración .................................. 63 5.3 Descomposición SVD y cálculo de las cuatro soluciones ...................................... 65 5.4 Calculo de la solución correcta mediante proyección .......................................... 67 5.5 Calculo de la escala entre escena y objeto ........................................................... 71 5.6 Calculo de la escala de la translación.................................................................... 72 5.7 Posicionamiento del Objeto.................................................................................. 73 5.8 Resultados ............................................................................................................. 75 6. Trabajo Futuro ............................................................................................................ 79 6.1 Optimización mediante kd-tree del algoritmo de emparejamiento .................... 79 6.2 Correspondencia con bolsa de palabras ............................................................... 79 6.3 Mejorar el posicionamiento.................................................................................. 80 6.4 Escenas con objetos duplicados............................................................................ 80 6.5 Escenas con objetos menos flexibles a puntos de interés.................................... 81 6.6 Eliminación de los puntos anteriores del objeto en la escena ............................. 82 7. Conclusiones ............................................................................................................... 83 7.1 Resumen y Conclusiones básicas .......................................................................... 83 7.2 Conclusiones Personales ....................................................................................... 85 iii 8. Bibliografía .................................................................................................................. 87 9. Anexos............................................................................ Error! Bookmark not defined. 9.1 Nociones básicas sobre Visión por Computador ..... Error! Bookmark not defined. 9.2 Instalación y ejecución de Bundler .......................... Error! Bookmark not defined. 9.3 Instalación y ejecución de PMVS ............................. Error! Bookmark not defined. 9.4 Instalación y ejecución de Qt en Visual Studio ........ Error! Bookmark not defined. 9.5 Instalación de OpenCV para Visual Studio ............... Error! Bookmark not defined. 9.6 Manual de usuario de la aplicación ......................... Error! Bookmark not defined. 9.6.1 Estructura básica de las carpetas de los modelos y objetos ..Error! Bookmark not defined. 9.6.2 Como desplazarse en el modelo cargado ......... Error! Bookmark not defined. 9.6.3 Ejemplo de ejecución de la aplicación.............. Error! Bookmark not defined. 9.7 Datasets.................................................................... Error! Bookmark not defined. 9.7.1 Dataset 1 ........................................................... Error! Bookmark not defined. 9.7.2 Dataset 2 ........................................................... Error! Bookmark not defined. 9.8 Estructura del proyecto ........................................... Error! Bookmark not defined. 9.8.1 main .................................................................. Error! Bookmark not defined. 9.8.2 mainWindow..................................................... Error! Bookmark not defined. 9.8.3 widgetGL ........................................................... Error! Bookmark not defined. 9.8.4 glBox.................................................................. Error! Bookmark not defined. 9.9 Bundler ..................................................................... Error! Bookmark not defined. 6 7 1.2 Aplicaciones del Proyecto A continuación se procede a poner algunos ejemplos en los que se podría aplicar algunas funcionalidades desarrolladas en este proyecto. 1.2.1 Realidad Aumentada La realidad virtual es un término referido a la visión directa o indirecta de un entorno físico real cuyos elementos se combinan con elementos virtuales para la creación de una realidad mixta a tiempo real. Un ejemplo de aplicación de este proyecto a la realidad aumentada seria el reconocimiento de objetos en tiempo real. Gracias a ello podríamos recorrer una galería o museo con un dispositivo que fuera visualizando las imágenes o cuadros para en tiempo real consultar una base de datos y mostrarnos en la pantalla del dispositivo información sobre lo que se está visualizando. Con esta tecnología sería posible y muy cómodo para una persona por ejemplo que viaja a otro país conocer detalles de los monumentos, locales y sitios de dicho lugar simplemente utilizando este dispositivo. Figura 3: Ejemplo de reconocimiento de imágenes en tiempo real. 8 Otra posible aplicación a realidad aumentada seria por como tutorial para ciertos dispositivos, tras reconocer por ejemplo un osciloscopio se podría señalar mediante la pantalla del dispositivo partes del osciloscopio y añadir instrucciones permitiendo así al usuario aprender sobre este dispositivo de una forma sencilla y rápida. Este ejemplo podría ser muy útil para facilitar la realización de ciertas prácticas en la universidad en las que se requiere de la utilización de elementos o maquinaria nueva para el estudiante, pudiendo así guiar la practica con el dispositivo de realidad virtual haciéndole más fácil adaptarse al entorno. Figura 4: Ejemplo de tutorial para un osciloscopio mediante realidad aumentada. 1.2.2 Robótica El mundo de la robótica en la industria está especialmente acotado por la precisión y la repetición haciendo que por ejemplo un brazo robótico realice siempre el mismo recorrido y los mismos movimientos. Sin embargo la tecnología está en constante evolución y es muy frecuente que cada cierto tiempo sea necesario modificar los movimientos que realiza un robot debido a modificaciones en el producto de fabricación que conllevan a un cambio en su entorno, llevando con ello un enorme coste en tiempo y dinero hasta que se consigue que el robot realice de nuevo su trabajo para ese nuevo entorno. Seria por tanto interesante que el robot pudiera 9 mediante varias cámaras reconocer objetos y saber su posición en el entorno de trabajo pudiendo así interactuar con ellos sin necesidad de programar previamente cada movimiento que ha de realizar. Figura 5: Ejemplo de un brazo robótico en una cadena de montaje. Un ejemplo claro de aplicación en el mundo de la industria seria el proceso de pintado en una cadena de montaje de coches, en donde para programar los movimientos que ha de realizar el brazo robótico para pintar un vehículo se utiliza a una persona que desplaza el brazo por las diferentes partes de la carrocería para así conocer las coordenadas exactas. Si se tuviera por ejemplo una reconstrucción 3D de la carrocería a pintar por el brazo robótico y se supiera su localización exacta en el entorno se podría pintar la carrocería sin necesidad de programar los movimientos del brazo previamente. 10 11 2. Obtención de Datasets Para la realización de este proyecto se ha decidido utilizar dos datasets: El primer dataset consta de una escena exterior en la que los objetos que aparecen poseen escasa textura haciéndolos más difíciles de identificar. Para ello se decidió utilizar como escena del primer dataset la cafetería del edificio Ada Byron del C.P.S. y como objetos las sillas y mesas de la cafetería. Como se puede observar en la figura 5 las sillas y las mesas que aparecen apenas tienen textura al ser prácticamente en su totalidad de un único color sin elementos identificables. Figura 6: Fotografía realizada a la escena del primer dataset. El segundo dataset consta de una escena interior con objetos con una textura más característica y por lo tanto más fácilmente identificable. En este caso se ha optado por utilizar como escena interior una mesa con varios objetos repartidos sobre ella, entre algunos de los objetos a utilizar en este dataset encontramos un peluche, un libro, un escarabajo, etc. 12 - Figura 7: Fotografía realizada a la escena del segundo dataset. A la hora de obtener las imágenes de los distintos datasets se ha optado por realizar las fotografías de la escena desde un único lado de esta para que al obtener posteriormente el modelo 3D existan partes de los objetos de la escena sin reconstruir debido a que no se tomaron fotos de esas partes. En el caso de los objetos por separado es distinto ya que lo que queremos es disponer del modelo 3D completo del objeto para posteriormente posicionarlo, por lo que tomaremos fotografías desde todos los ángulos. 13 3. Reconstrucción 3D a partir de imágenes Como se ha mencionado en la introducción para obtener los modelos 3D de un entorno a partir de un conjunto de imágenes de este se ha decidido realizar dos etapas: una en la que se obtienen algunos puntos del modelo y los parámetros de las cámaras para cada fotografía (reconstrucción 3D no densa) y una segunda para a partir de los datos obtenidos en la etapa previa obtener un modelo 3D con más puntos (reconstrucción 3D densa). Antes de proceder con el siguiente apartado se recomienda consultar el anexo 1 sobre conceptos básicos de visión por computador para facilitar la comprensión de las ecuaciones. Los métodos descritos a continuación sobre reconstrucción 3D no densa y densa son métodos básicos de visión por computador, pero hay que tener en consideración que no son la única forma de realizarlos. 3.1. Reconstrucción 3D no densa Esta primera fase de reconstrucción 3D se centra en la obtención de los parámetros de la cámara para cada fotografía como son su posición, distancia focal, coeficientes de distorsión, etc. Además, en esta fase se obtiene la posición 3D de algunos de los puntos de la escena fotografiada. Para ello inicialmente se calculan los puntos de interés de cada imagen de la escena que queremos obtener el modelo 3D, siendo 𝑥𝑖,𝑗= [𝑥 𝑦 1] el punto de interés j de la imagen i. Una vez se dispone de los puntos de interés para cada imagen se procede a calcular una matriz fundamental que cumple la siguiente propiedad 14 𝒙𝒊,𝒋′𝑻∗𝑭∗𝒙𝒎,𝒏=𝟎 Siendo F la matriz fundamental, 𝑥𝑖,𝑗 ′= [𝑥 𝑦 1] el punto de interés j de la imagen i y 𝑥𝑚,𝑛= [𝑥 𝑦 1]𝑇 el punto de interés n de la imagen m emparejado con el punto 𝑥′. Así pues según la ecuación descrita la matriz fundamental relaciona las correspondencias entre pixeles de dos imágenes. Si calculamos 𝐹 y conocemos los parámetros intrínsecos de las cámaras (distancia focal, coeficientes de distorsión, etc.) podemos obtener la rotación y translación de una cámara con respecto a otra ya que: 𝑲′𝑻∗𝑭∗𝑲=𝒕 × 𝑹 Siendo 𝐾 y 𝐾′ las matrices de parámetros intrínsecos de las cámaras, 𝐹 la matriz fundamental y 𝑡 y 𝑅 el vector de translación y la matriz de rotación de la cámara primera a la segunda. Es decir, siendo 𝑃 y 𝑃′ las matrices de proyección de cada camara, e 𝐼 una matriz de identidad 3x3 se cumple lo siguiente: 𝑷= 𝑰 𝟎] y 𝑷′= 𝑹 𝒕] Para calcular la matriz fundamental se necesita de un mínimo de 7 correspondencias: 𝒙′𝑻∗𝑭∗𝒙=𝟎 𝒙′𝒙𝒇𝟏𝟏+𝒙′𝒚𝒇𝟏𝟐+𝒚′𝒙𝒇𝟏𝟑+𝒚′𝒙𝒇𝟐𝟏+𝒚′𝒚𝒇𝟐𝟐+𝒚′𝒇𝟐𝟑+𝒙𝒇𝟑𝟏+𝒚𝒇𝟑𝟐+𝒇𝟑𝟑=𝟎 Separando términos conocidos de los términos no conocidos: 𝒙′𝒙,𝒙′𝒚,𝒙′,𝒚′𝒙,𝒚′𝒚,𝒚′,𝒙,𝒚,𝟏 ∗[𝒇𝟏𝟏,𝒇𝟏𝟐,𝒇𝟏𝟑,𝒇𝟐𝟏,𝒇𝟐𝟐,𝒇𝟐𝟑,𝒇𝟑𝟏,𝒇𝟑𝟐,𝒇𝟑𝟑]𝑻=𝟎 𝒙′𝟏𝒙𝟏𝒙′𝟏𝒚𝟏𝒙′𝟏𝒚′𝟏𝒙𝟏𝒚′𝟏𝒚𝟏𝒚′𝟏𝒙𝟏𝒚𝟏𝟏 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 𝒙′𝒏𝒙𝒏𝒙′𝒏𝒚𝒏𝒙′𝒏𝒚′𝒏𝒙𝒏𝒚′𝒏𝒚𝒏𝒚′𝒏𝒙𝒏𝒚𝒏𝟏 ∗𝒇=𝟎 15 El algoritmo básico seguido en este proyecto para la reconstrucción no densa consta de las siguientes fases: 1. Encontrar N vías (conjunto de puntos de interés que conectan múltiples imágenes) 𝑇 = {𝑇1,𝑇2,…,𝑇𝑁} a. Para cada par de imágenes 𝑄𝑖,𝑄𝑗 :  Detectar los puntos de interés en 𝑄𝑖 y 𝑄𝑗.  Emparejar los puntos de interés y posteriormente utilizar un filtrado RANSAC para eliminar emparejamientos erróneos. b. Emparejar los puntos de interés a través de múltiples imágenes, construyendo vías. 2. Estimar {𝑃1…𝑃𝑁} y la posición 3D de para cada vía {𝑋1…𝑋𝑁} a. Seleccionar un par de imágenes 𝑄1′,𝑄2′ (bien condicionadas, es decir que tengan un gran número de emparejamientos y no compartan un ángulo de visión muy similar) b. Siendo 𝑇1′2′ las vías que contienen puntos en común de ambas imágenes, estimar 𝐾1′y 𝐾2′, calcular {𝑃1′,𝑃2′} y la posición 3D de 𝑇1′2′ a partir de la matriz fundamental. Minimizar los errores de proyección de forma no lineal. c. Incrementalmente añadir una nueva cámara 𝑃𝐾 al sistema, estimar los parámetros de la cámara y optimizar el sistema de forma no lineal. d. Repetir el paso c hasta que todas las cámaras hayan sido estimadas. Para un mayor nivel de detalle del proceso seguido por este algoritmo consultar la sección 9 de anexos. 22 Figura 12: Ejemplo del primer proceso de filtrado de parches. U(p) denota un conjunto de parches que son inconsistentes visualmente con la información de P, por lo que se identifica a P como un outlier. [2] Para realizar el proceso de reconstrucción 3D densa se ha decidido utilizar un segundo programa llamado PMVS, un software desarrollado por Yasutaka Furukawa [2], el cual también es de código abierto (escrito en C) . Este programa toma inicialmente un conjunto de imágenes, además de los parámetros de las cámaras para reconstruir el modelo 3D del objeto o la escena que aparece en las imágenes mediante el método descrito previamente. PMVS solo reconstruye estructuras rígidas, es decir ignora los objetos no rígidos como podría ser el caso de peatones caminando enfrente de un edificio. Como salida del programa obtenemos un conjunto de puntos orientados (sus coordenadas, la normal a la superficie y el color) en lugar de modelos poligonales. Figura 13: Reconstrucción 3D del coliseo de Roma con PMVS. [13] 23 3.2.1. Explicación del proceso Al igual que con Bundler pese a que PMVS también dispone de un manual de instalación, fue necesario dedicarle cierto tiempo a la instalación de PMVS para hacerlo funcionar correctamente debido a su gran cantidad de dependencias. Tras instalar correctamente PMVS en el sistema se procedió a obtener el modelo en 3D del entorno que aparece en las fotografías utilizadas previamente en el Bundler, para ello fue necesario preparar los datos de entrada antes de la ejecución. PMVS requiere como datos de entrada una matriz de proyección para cada cámara, además de las imágenes correspondientes a cada cámara y un fichero de configuración del proceso de reconstrucción. Bundler dispone de un ejecutable, el cual nos permite convertir los parámetros que obtuvimos con este de cada cámara (rotación, translación, distancia focal etc.) a su correspondiente matriz de proyección. De esta forma, nos facilita de gran medida el proceso de introducción de los datos de las cámaras a la aplicación PMVS. Una vez ya disponíamos de los datos de entrada se procedió a ejecutar PMVS para obtener los modelos 3D. El tiempo de ejecución de esta aplicación es medianamente elevado llevando en nuestro caso entre 20 y 40 minutos en un ordenador convencional. Hay que tener en cuenta que dependiendo del número de fotografías empleadas para la reconstrucción, el tamaño de estas, los parámetros empleados en el fichero de configuración etc. el tiempo se incrementara o reducirá considerablemente además de mejorar o empeorar la calidad del modelo obtenido. 24 25 3.3. Visor 3D Para poder comprobar que los resultados obtenidos a partir de Bundler y de PMVS son correctos y que por lo tanto no se cometieron errores en la introducción de los parámetros correspondientes a su ejecución es necesaria la realización de un visor 3D. El objetivo de este visor 3D es ser capaz de leer los ficheros proporcionados por ambos programas para posteriormente mostrar estos datos en un entorno 3D. En el caso del Bundler, deberá mostrar en un entorno 3D las posiciones de las cámaras reconocidas además de los puntos de la escena u objeto. En el caso del PMVS, se deberá mostrar la reconstrucción 3D de la escena u objeto. Para mejorar la interacción del usuario con el visor 3D se ha decidido que este pueda moverse en torno al modelo 3D con ayuda exclusivamente del ratón, permitiéndole así movimientos de rotación, translación y zoom. Para el desarrollo de este visor se ha decidido utilizar Qt, una biblioteca multiplataforma para desarrollar interfaces graficas. Su uso actualmente está muy extendido, pudiendo encontrar aplicaciones como Google Earth, Adobe Photoshop Album, Skype... desarrolladas con esta biblioteca. Qt utiliza como lenguaje de programación C++ de forma nativa, además de permitir utilizar otros lenguajes de programación mediante bindings. Qt soporta otras librerías como son SQL, OpenGL, XML dándole así una gran versatilidad. En cuanto al entorno de programación se decidió utilizar Microsoft Visual Studio 2008 por su facilidad de manejo y por su compatibilidad para trabajar con la biblioteca Qt. 26 Figura 14: Imagen del Visor 3D. 27 3.4. Resultados En este apartado se muestran, utilizando el visor desarrollado, los resultados obtenidos con Bundler y PMVS tras proporcionar a estos las imágenes correspondientes al primer dataset. Para ver los resultados obtenidos con el resto de entornos y objetos fotografiados acudir a la sección Datasets en Anexos. Figura 15: Ejemplo de las fotos proporcionadas a Bundler y PMVS. Uno de los ficheros que Bundler devuelve como salida contiene un conjunto de puntos con su localización en un entorno 3D y su correspondiente color. En este conjunto de puntos se encuentran algunos puntos pertenecientes a la escena reconstruida, mientras que otros corresponden a la posición de las cámaras. En la Figura 16 se puede observar de color rojo, verde y amarillo algunas de las posiciones de las cámaras además de algunos de los puntos de la cafetería. 28 Figura 16: Imagen de la posición de las cámaras en la cafetería del C.P.S. En el caso de PMVS se reconstruye la escena con las imágenes de las cuales se conoce su localización gracias al proceso previo con Bundler. En la figura 17 se puede visualizar la reconstrucción de parte de la cafetería. La reconstrucción no es perfecta viéndose algunos espacios vacios, esto puede ser debido a ángulos muertos, a que las fotografías proporcionaban poca información de esas zonas, etc. Para mejorar el modelo obtenido se podría aplicar posteriormente a estos resultados filtros, métodos de expansión, etc. pero debido a que la finalidad de este proyecto es el reconocimiento y posicionamiento de objetos y una mejora de la calidad de los modelos obtenidos no influiría para nada en los objetivos se ha decidido trabajar directamente con los modelos proporcionados por PMVS. 29 Figura 17: Imagen de la cafetería tras la reconstrucción densa. 30 31 4. Correspondencias entre puntos Una vez se dispone de una base de datos de imágenes y modelos 3D con los que poder trabajar se requiere de un algoritmo para la obtención de descriptores locales en imágenes. Básicamente lo que hacen estos algoritmos es recopilar información invariante de pequeñas regiones de la imagen que considera de interés. Gracias a ello podemos comparar imágenes en las que aparecen los mismos objetos o escenas y saber así su grado de similitud. Existen multitud de algoritmos que nos permiten obtener esta información, cada uno con sus ventajas e inconveniente. A continuación procedemos a explicar y comparar algunos de los algoritmos que se tuvieron en cuenta para este proyecto. 4.1 SIFT SIFT (Scale-invariant feature transform) es un algoritmo de visión por computador para detectar y describir características locales de imágenes. El algoritmo fue publicado por David Lowe en 1999. SIFT puede de forma robusta identificar objetos desordenados o incluso parcialmente ocultos, esto es debido a que los descriptores proporcionados por SIFT son invariantes a escala, orientación, translación y parcialmente invariante a cambios de iluminación. Los descriptores calculados por SIFT guardan gran similitud con las neuronas del cortex inferior temporal, las cuales son usadas para reconocimiento de objetos en la visión humana permitiéndonos identificar rápidamente objetos que conocemos independientemente de su ángulo de visión, color, etc. 38 39 4.2 SURF SURF (Speeded Up Robust Features) es un robusto algoritmo para calculo de puntos de interés invariantes y descriptores en imágenes. Este algoritmo fue presentado por Herbert Bay en 2006. Dicho algoritmo fue inspirado inicialmente por los descriptores SIFT. Según su autor tiene como ventaja sobre SIFT su rapidez en el cálculo además de ser más robusto con las transformaciones de las imágenes. SURF en primer lugar detecta los posibles puntos de interés y su localización en la imagen. Una vez obtenidos los puntos se define un vector (normalmente de 64 elementos) para cada punto donde queda representada su vecindad. 4.2.1 Calculo de descriptores SURF utiliza imágenes integrales ya que el tiempo de cálculo de la aplicación de filtros de convolución es menor. La entrada de una imagen integral en una localización 𝑥= (𝑥,𝑦) está formada por la suma de los valores en la escala de grises de los pixeles de la imagen que se encuentran en un rectángulo formado por el origen y 𝑥. Una vez que una imagen integral ha sido calculada, son necesarias tres operaciones más y cuatro accesos de memoria para calcular la suma de intensidades de un rectángulo de cualquier tamaño. Figura 23: Cálculo de suma de intensidades para un rectángulo cualquiera. [3] 40 SURF basa su detector en matrices Hessianas debido a su gran precisión y bajo coste computacional. Pero a diferencia de otros detectores como el de Mikolajczyk y Schmid, SURF se basa en el determinante de la matriz para la localización de los puntos y la selección de la escala como hizo Lindeberg. Así pues, dado un punto 𝑥 = (𝑥,𝑦) en una imagen 𝐼, la matriz Hessiana ℋ 𝑥,𝜎 en x a escala 𝜎 se define: 𝓗 𝒙,𝝈 = 𝑳𝒙𝒙(𝒙,𝝈)𝑳𝒙𝒚(𝒙,𝝈) 𝑳𝒙𝒚(𝒙,𝝈)𝑳𝒚𝒚(𝒙,𝝈) Donde 𝜕2 𝜕𝑥2𝑔(𝜎) es la convolución de la derivada de segundo orden de la Gaussiana 𝐿𝑥𝑥(𝑥,𝜎) con la imagen I en el punto x. Para el cálculo del determinante se realizan aproximaciones a las derivadas de segundo orden de la Gaussiana, obteniendo con ello las aproximaciones: 𝐷𝑥𝑥, 𝐷𝑥𝑦, 𝐷𝑦𝑦. Para calcular el determinante de la matriz Hessiana que nos indicara la escala del punto será necesario aplicar la siguiente fórmula: 𝐝𝐞𝐭 𝓗𝒂𝒑𝒓𝒐𝒙 =𝑫𝒙𝒙𝑫𝒚𝒚− (𝟎.𝟗𝑫𝒙𝒚)𝟐 Como se ha mencionado previamente SURF guarda gran similitud con SIFT. En primer paso para obtener el descriptor de un punto de interés con SURF es calcular su orientación. Para obtener un punto invariante a la orientación se calcula el "Haarwavelet" en las direcciones 𝑥 e 𝑦 en una región circular de radio 6𝑠, donde 𝑠 es la escala del punto de interés. Una vez se ha calculado para todos los vecinos, se calcula la orientación dominante sumando todos los resultados dentro de una ventana deslizante que cubre un ángulo de de 𝜋/3. 41 Figura 24: Ejemplo del cálculo de la orientación en SURF. [3] Para construir el descriptor se utiliza una región cuadrada de tamaño 20𝑠 centrada en el punto de interés. Dicha región se divide en 4 subregiones, calculándose para cada una de ellas un conjunto de características simples. Posteriormente se calcula el "Haar-wavelet" para 𝑥 e 𝑦 y se suavizan los resultados mediante una Gaussiana, obteniéndose como resultado 𝑑𝑥 y 𝑑𝑦. A su vez, para cada subregión se suman los resultados 𝑑𝑥 y 𝑑𝑦 además de calcularse su valor absoluto |𝑑𝑥| y |𝑑𝑦|. De esta forma se dispone para cada subregión de un vector v compuesto por: 𝒗 = ( 𝒅𝒙, 𝒅𝒚, |𝒅𝒙|, |𝒅𝒚|) El vector SURF se forma uniendo los diferentes vectores de las subregiones. 42 Figura 25: Ejemplo de los valores adquiridos por dx y dy para diferentes imágenes. [3] 43 4.3 MSER MSER (Maximally Stable Extremal Regions) es una técnica para la detección de blobs en imágenes. Esta técnica fue propuesta por Matas [11] para encontrar correspondencias entre los elementos que aparecen en común en varias imágenes con distintos puntos de vista. Funciona mediante thresholds, toma regiones de pixeles que contienen un nivel similar de grises, de forma que la diferencia entre los pixeles que forman las regiones se encuentra por debajo de un determinado threshold. Posteriormente se sustituyen estas regiones por elipses. Con las elipses obtenidas se procederá a utilizar otros algoritmos como SURF o SIFT para calcular los descriptores de dichas elipses y así poder comparar ambas imágenes. Figura 26: Ejemplo del resultado de aplicar MSER a una imagen. [14] 44 La idea básica del algoritmo que sigue MSER es la siguiente: 1. Se ordenan los pixeles de la imagen en orden de intensidad. 2. Los pixeles se añaden a un árbol en orden creciente de intensidad. Dicho árbol tiene las siguientes propiedades:  Todos los descendientes de un determinado pixel son un subconjunto que forma una región.  Todas las regiones son descendientes de algunos pixeles. 3. Las regiones son extraídas del árbol calculado dependiendo de los valores (tamaño mínimo de la región, tamaño máximo, etc.) y thresholds establecidos. 4. Las regiones duplicadas u otras regiones malas son eliminadas. 5. Se calculan las elipses correspondientes a las regiones obtenidas. Debido a que con el algoritmo previamente expuesto se tiene una idea bastante general del funcionamiento de MSER se ha considerado que no era necesario profundizar en un mayor nivel de detalle. Figura 27: Ejemplo de emparejamiento entre dos imágenes con MSER. [14] 45 4.4 Comparativa 4.4.1 SIFT vs SURF Tanto SIFT como SURF obtienen puntos de interés de la imagen invariantes a escala y orientación, así como a cambios de iluminación. Ambos obtienen además un vector descriptor por cada punto de interés, aunque cada uno lo calcula de una forma distinta. Entre las diferencias encontramos que SIFT guarda la posición, escala y orientación debido a que en una misma posición (𝑥,𝑦) es posible encontrar varios puntos de interés con diferente escala s u orientación 𝜎 . En cambio en SURF para una posición (𝑥,𝑦) solo aparece un único punto de interés, por lo que no guarda la escala y orientación, aunque si la matriz de segundo momento y el signo de la laplaciana. A continuación se muestra una comparativa entre el algoritmo SURF y SIFT utilizando en ambos descriptores de 128. Tanto SIFT como SURF trabajan con imágenes en formato pgm (escala de grises) por lo que ambos parten de la misma base. Imagen Puntos SIFT Puntos SURF Tiempo SIFT (ms) Tiempo SURF (ms) 0000 1635 584 1879 494 0001 1943 659 2158 521 0002 2155 798 2483 572 0003 1967 673 2167 535 0004 1760 603 1932 501 0005 1548 529 1740 476 0006 1256 451 1656 466 Figura 28: Tabla comparativa entre SIFT y SURF. 46 En la tabla observamos como SURF es prácticamente 3 o 4 veces más rápido que SIFT. Mientras que en cuanto a puntos invariantes detectados SIFT obtiene más del doble de puntos que SURF. Sin embargo, tenemos que tener en cuenta que SIFT permite que existan varios puntos invariantes con distinta escala y orientación en una misma posición, mientras que en SURF solo sería posible uno. Es por ello que suponemos que el número de características detectada disminuiría si SIFT no permitiera varios puntos por posición. Así pues podemos deducir de la primera tabla que si nuestro objetivo es encontrar el mayor número de puntos de interés sin importarnos tanto el tiempo deberíamos optar por SIFT, mientras que si el tiempo es una prioridad para nosotros deberíamos elegir SURF. Sin embargo, no podemos calificar SIFT y SURF únicamente por el número de puntos y el tiempo de ejecución. Sería necesario comprobar también la calidad de los puntos invariantes proporcionado por cada algoritmo, por lo que se realizaran pruebas de emparejamiento entre distintas imágenes para posteriormente comparar los resultados obtenidos entre SIFT y SURF. Figura 29: Imágenes utilizadas para la comparativa ordenadas de izquierda a derecha y de arriba abajo, siendo la imagen superior izquierda la 0000 y la inferior derecha la 0005. 47 Par de imágenes Matches SIFT Matches SURF Matches SIFT tras RANSAC Matches SURF tras RANSAC 0000-0002 172 178 78 61 0001-0002 378 256 287 189 0003-0002 421 294 356 217 0004-0002 351 224 278 187 0005-0002 94 97 42 36 0006-0002 46 56 24 14 Figura 30: Tabla 2 comparativa entre SIFT y SURF. En la tabla 2 podemos visualizar como SIFT obtiene un numero de emparejamientos más elevado que SURF si las imágenes a emparejar están muy próximas, mientras que SURF encuentra más puntos si las imágenes comparadas se alejan de la inicial. Sin embargo, tras utilizar RANSAC en los emparejamientos obtenidos con SIFT y SURF observamos como el numero de emparejamientos correctos por parte de SURF es muy reducido comparado con el numero de emparejamientos correctos por parte de SIFT. En resumen, según la comparativa realizada SURF tiene como principal ventaja su reducido coste computacional, mientras que SIFT obtiene un número mayor de puntos de interés además de un número menor de falsos positivos en los emparejamientos. Para verificar que las conclusiones obtenidas no dependían únicamente de las imágenes escogidas para la comparativa se decidió consultar el paper de A.M Romero [7] sobre comparativa de descriptores en donde se deducían unas conclusiones similares entre SIFT y SURF. 54 En las imágenes aparece mediante puntos de colores los puntos de interés que no han sido emparejados, mientras que los puntos emparejados aparecen unidos mediante líneas. En cuanto a los resultados obtenidos, podemos observar como SURF apenas obtiene puntos de interés en la silla, mientras que en los elementos que hay alrededor de ella aparecen bastantes puntos de interés. De hecho, los pocos puntos de interés que aparecen sobre la silla pertenecen al logotipo. Ya que la silla es prácticamente de un único color y apenas tiene detalles de los que se puedan obtener puntos característicos se decidió probar nuevos métodos para ver hasta qué punto utilizar esta silla como objeto iba a ser un impedimento para el proyecto. La primera prueba consistía simplemente en utilizar SIFT en lugar de SURF, con este cambio se consiguió obtener más puntos de interés sobre la silla. Pero a la hora de realizar los emparejamientos con los descriptores obtenidos se producían muchos emparejamientos erróneos. La causa más probable de estos errores de emparejamientos vendrían por la gran similitud de los descriptores pertenecientes a la silla. Figura 34: Ejemplo de puntos de interés obtenidos al aplicar SIFT. 55 Como segunda prueba se creó una malla de puntos de interés para dos imágenes, las cuales ya se había conseguido emparejar anteriormente con éxito mediante SURF y SIFT. El objetivo al utilizar esta malla era poder obtener puntos de interés de cada parte de la imagen, cosa que en las imágenes de la silla no se daba ya que los puntos se concentraban sobretodo alrededor de la silla, en lugar de sobre esta. Figura 35: Ejemplo de emparejamiento con éxito mediante SURF. Una vez se disponía de la posición de los distintos puntos de interés de la malla para cada imagen se procedió a calcular los descriptores SURF en dichas posiciones con unos determinados parámetros de radio y laplaciana. Los resultados obtenidos no fueron precisamente buenos por lo que se desecho esta opción rápidamente. Figura 36: Segundo intento de emparejamiento mediante una malla de puntos de interés. 56 La tercera prueba consistía en hacer uso de los algoritmos por regiones o blobs como MSER para intentar obtener puntos de interés sobre la silla. Figura 37: Ejemplo de aplicar MSER a una imagen de la silla y otra de la mesa. Como se observa en la imagen MSER fue incapaz de obtener un gran número de regiones sobre la silla, mientras que alrededor de esta encontró numerosas regiones. En cuanto a la mesa, la situación es similar a la silla y MSER no encuentra suficientes regiones. Con estos resultados se decidió desechar también la idea de utilizar MSER. Tras comprobar que con los algoritmos de cálculo de descriptores actuales no era posible obtener resultados satisfactorios para el primer dataset se procedió a utilizar el segundo dataset. 57 4.5.2 Resultados con el segundo dataset Figura 38: Escena reconstruida del segundo dataset. 58 Figura 39: Objeto reconstruido del segundo dataset. 59 Figura 40: Ejemplo de emparejamiento con uno de los objetos del segundo dataset. Figura 41: Ejemplo de emparejamiento con otro de los objetos del segundo dataset. Tras realizar varias pruebas de emparejamiento tanto con SURF como con SIFT con los nuevos objetos de la escena comprobamos que se obtenían suficientes puntos de interés sobre los objetos a identificar además de obtener bastantes emparejamientos correctos. Por lo que se decidió continuar el proyecto con este nuevo dataset y dejar para más adelante o proyectos futuros el anterior dataset. En las imágenes se percibe como existe algún falso positivo en los emparejamientos, sin embargo este problema no es excesivamente importante ya que en los procedimientos posteriores estos emparejamientos serán filtrados con el método RANSAC consiguiendo así eliminar los falsos positivos. 60 61 5. Posicionamiento de los objetos en la escena Una vez disponemos ya de un dataset consistente con el que trabajar y de un algoritmo de emparejamiento con el que se obtienen resultados coherentes podemos ya proceder a programar los algoritmos necesarios para el posicionamiento de los objetos en la escena. Esta última fase del proyecto requiere de gran cantidad de cálculos, por lo que ha sido necesario dedicarle gran cantidad de tiempo tanto para programarla como para testearla y eliminar posibles errores. Algunas de las ecuaciones mostradas en esta sección del proyecto han sido ya vistas en la parte de reconstrucción 3D, esto es debido a que ambas fases guardan una gran similitud en sus cálculos. Para posicionar el objeto en la escena con éxito es necesario seguir los siguientes pasos: 1. Calcular los emparejamientos entre una imagen de la escena y otra del objeto 2. A partir de los emparejamientos calcular la matriz fundamental 3. Calcular las matrices de calibración para cada cámara 4. Calcular la matriz esencial a partir de la matriz fundamental y las matrices de calibración 5. Descomponer la matriz esencial mediante SVD para obtener las cuatro posibles soluciones al combinar las dos matrices de rotación obtenidas y los dos vectores de translación 6. Proyectar o triangularizar un punto a 3D para cada una de las cuatro soluciones obtenidas y quedarnos con aquella solución que nos dé una profundidad Z positiva para ambas cámaras. 7. Calcular la escala entre la escena y el objeto 8. Calcular la escala de la translación obtenida 9. Posicionar el objeto en la escena con la solución correcta 62 Como ayuda a la hora de programar todos los pasos anteriores se ha decidido hacer uso de la librería OpenCV. Entre las ventajas que obtenemos al utilizar esta librería encontramos que contiene un potente algoritmo para el cálculo de la matriz fundamental, además de permitirnos calcular la descomposición SVD de una matriz y definir y trabajar matrices de forma relativamente sencilla. A continuación se procede a explicar y describir con mayor detalle cómo se han desarrollado los diferentes puntos necesarios para el posicionamiento de objetos en la escena. 5.1 Calculo de la matriz fundamental La matriz fundamental redefine la restricción epipolar, es decir la relación entre las dos proyecciones como : 𝒙′𝑻∗𝑭∗𝒙=𝟎 Siendo F la matriz fundamental, 𝑥= [𝑥 𝑦 1]𝑇 el punto de la cámara izquierda y 𝑥′= [𝑥′ 𝑦′ 1] el punto de la cámara derecha emparejado con el punto 𝑥. Así pues para cada emparejamiento valido se deberá cumplir dicha propiedad. Para calcular la matriz fundamental hacemos uso de la función cvFindFundamentalMat de la librería OpenCV. Dicha función necesita como parámetros de entrada las coordenadas en pixeles de los puntos emparejados de las imágenes que se quiere obtener la matriz fundamental. Además de los puntos hay que especificar el método de cálculo a utilizar, en nuestro caso optamos por el método de los 8 puntos con un filtrado RANSAC para la detección de espurios. En cuanto a los parámetros a utilizar para el filtrado RANSAC, hemos optado por un valor de 1.0 como la distancia máxima en pixeles de un punto a la línea epipolar y un valor de 0.99 como el nivel de seguridad deseado de que la matriz fundamental calculada sea correcta. 63 cvFindFundamentalMat( pointsObjeto, pointsEscena, F, CV_RANSAC, 1.0, 0.9999, status ); 5.2 Calculo de la matriz esencial y las matrices de calibración La matriz esencial puede ser calculada a partir de la matriz fundamental y las matrices de calibración de cada cámara mediante la fórmula: 𝑬=𝑲′𝑻∗𝑭∗𝑲 Siendo F la matriz fundamental, K' la matriz de calibración de la cámara derecha y K la matriz de calibración de la cámara izquierda. Antes de proceder a calcular la matriz esencial es necesario obtener las matrices de calibración de cada cámara. La matriz de calibración permite junto a la matriz de proyección de perspectiva transformar las coordenadas de la escena en tres dimensiones a pixeles en la imagen. 𝒙𝒊 =𝑷∗ 𝑿 𝒊 𝒙𝒊 =𝑲∗𝑷𝒄𝒂𝒎∗𝑿 𝒊 Siendo 𝑥𝑖 las coordenadas del punto i en pixeles 𝑥 𝑦 1 , 𝐾 la matriz de calibración, 𝑃𝑐𝑎𝑚 la matriz de proyección en perspectiva y 𝑋𝑖 las coordenadas del punto i en 3D (𝑥 𝑦 𝑧 1). La matriz de proyección en perspectiva de la cámara izquierda la llamaremos 𝑷𝒄𝒂𝒎, mientras que la de la cámara derecha la llamaremos 𝑷′𝒄𝒂𝒎. Los valores de dichas matrices son los siguientes: 𝑷𝒄𝒂𝒎= [ 𝑰 | 𝟎 ] 70 Combinando ambas soluciones: 𝑷𝟑𝒄𝒂𝒎∗𝒙𝒊𝒄𝒂𝒎 −𝑷𝟏𝒄𝒂𝒎 𝑷𝟑𝒄𝒂𝒎∗𝒚𝒊𝒄𝒂𝒎 −𝑷𝟐𝒄𝒂𝒎 𝑷′𝟑𝒄𝒂𝒎∗𝒙′𝒊𝒄𝒂𝒎 −𝑷′𝟏𝒄𝒂𝒎 𝑷′𝟑𝒄𝒂𝒎∗𝒚′𝒊𝒄𝒂𝒎 −𝑷′𝟐𝒄𝒂𝒎 ∗𝑿 𝒊 = 𝟎 Esta solución tiene la forma 𝐴∗𝑥 = 0, donde 𝑨 = 𝑷𝟑𝒄𝒂𝒎∗𝒙𝒊𝒄𝒂𝒎 −𝑷𝟏𝒄𝒂𝒎 𝑷𝟑𝒄𝒂𝒎∗𝒚𝒊𝒄𝒂𝒎 −𝑷𝟐𝒄𝒂𝒎 𝑷′𝟑𝒄𝒂𝒎∗𝒙′𝒊𝒄𝒂𝒎 −𝑷′𝟏𝒄𝒂𝒎 𝑷′𝟑𝒄𝒂𝒎∗𝒚′𝒊𝒄𝒂𝒎 −𝑷′𝟐𝒄𝒂𝒎 Antes de proceder a solucionar el sistema anterior normalizamos 𝐴, 𝑨𝒏𝒐𝒓𝒎= 𝟏 𝑨𝟏 𝑨𝟏 𝟏 𝑨𝟐 𝑨𝟐 𝟏 𝑨𝟑 𝑨𝟑 𝟏 𝑨𝟒 𝑨𝟒 Una vez tenemos A normalizado podemos obtener fácilmente de forma rápida 𝑋 𝑖, ya que 𝑋 𝑖 es equivalente a la última columna de 𝑉 donde 𝑈∗𝑆∗𝑉𝑇= 𝐴𝑛𝑜𝑟𝑚 es la descomposición SVD de 𝐴𝑛𝑜𝑟𝑚. 71 Tras calcular el punto 3D 𝑋 𝑖, podemos comprobar cuál de las cuatro posibles matrices de proyección previas es la correcta. Para ello simplemente basta con observar el resultado de las siguientes ecuaciones para las cuatro soluciones: 𝑿 ′𝒊 = 𝑷 ∗𝑿 𝒊 𝑿 ′′𝒊=𝑷′ ∗𝑿 𝒊 Si la componente Z de 𝑋 ′𝑖 y 𝑋 ′′𝑖 es positiva significa que el punto 3D calculado está enfrente de las dos cámaras y por lo tanto es la solución correcta. 5.5 Calculo de la escala entre escena y objeto Para el cálculo de la escala entre la escena y el objeto vamos a utilizar algunos datos que nos proporciona el Bundler. En nuestro caso, los puntos de interés que utilizamos para trabajar con cada imagen los obtenemos de los que calculo previamente el Bundler para conocer la posición de las cámaras. Además de proporcionarnos los puntos de interés y las posiciones de las cámaras, Bundler guarda en un fichero la posición 3D de algunos de los puntos que ha sido capaz de reconstruir antes de la fase de PMVS. Esta información es muy valiosa ya que es la que nos va a permitir conocer la escala entre la escena y el objeto. Nuestro objetivo es utilizar el listado de emparejamientos que hemos calculado anteriormente para consultar si en la lista de puntos 3D del Bundler aparece la posición 3D de ese punto. Para conocer la escala de la escena o el objeto basta con saber la posición 3D de dos emparejamientos y calcular la distancia entre estos. Así pues los pasos a seguir serian los siguientes:  Recorrer la lista de emparejamientos obtenida entre una imagen de la escena y otra del objeto y consultar para cada imagen si en el fichero 72 que nos proporciona Bundler se conoce la posición 3D del par de puntos emparejados.  Buscar otro par de puntos distinto al anterior en la lista de emparejamientos de los que se conozca su posición 3D.  Siendo A y A' el par de puntos emparejados en el primer paso y B y B' el par de puntos emparejados en el segundo paso, donde A y B corresponden a puntos de interés de la imagen de la escena y A' y B' corresponden a puntos de interés de la imagen del objeto. Calcular la distancia de los puntos en 3D entre A y B para conocer la escala de la escena. Calcular la distancia entre los puntos en 3D entre A' y B' para conocer la escala del objeto. Una vez conocida la escala de la escena y del objeto podemos posicionar el objeto con el tamaño adecuado a la escena simplemente multiplicando los puntos 3D del objeto a posicionar por 𝑒𝑠𝑐𝑎𝑙𝑎𝑒𝑠𝑐/𝑒𝑠𝑐𝑎𝑙𝑎𝑜𝑏𝑗. 5.6 Calculo de la escala de la translación Para obtener la escala de la translación se debe calcular la proyección 3D de los puntos obtenidos para el cálculo de la escala de la escena y el objeto. Para proyectar los puntos a 3D vamos a realizar los mismos pasos que hemos realizado para calcular cual de las cuatro soluciones era la correcta, con la diferencia de que en lugar de utilizar 𝑃𝑐𝑎𝑚 , 𝑃′𝑐𝑎𝑚 , 𝑥 𝑖𝑐𝑎𝑚 , 𝑥 ′𝑖𝑐𝑎𝑚 vamos a utilizar 𝑃 , 𝑃′, 𝑥 𝑖 , 𝑥 ′𝑖. Es decir A será: 𝑨 = 𝑷𝟑∗𝒙𝒊 −𝑷𝟏 𝑷𝟑∗𝒚𝒊 −𝑷𝟐 𝑷′𝟑∗𝒙′𝒊 −𝑷′𝟏 𝑷′𝟑∗𝒚′𝒊 −𝑷′𝟐 Una vez tengamos A normalizada, haremos la descomposición SVD: 𝑈∗𝑆∗𝑉𝑇= 𝐴𝑛𝑜𝑟𝑚 73 De donde la última columna de V corresponderá al punto 3D proyectado. Cuando dispongamos ya de la posición 3D de ambos emparejamientos procederemos a calcular la distancia entre estos. Para saber la escala de la translación bastara con dividir la escala de la escena por la distancia que acabamos de obtener. Con la escala de la translación obtenida bastara con multiplicar la translación de una cámara con respecto a otra por dicha escala y así posicionar correctamente el objeto. 5.7 Posicionamiento del Objeto Una vez realizados todos los cálculos anteriores deberíamos ser capaces de posicionar un objeto en la escena sin problema. Para posicionar el objeto disponemos de los siguientes datos:  Modelo de la escena y del objeto (Los coordenadas de los puntos 3D de cada modelo están referenciados cada uno con respecto a una referencia mundo).  Posición de la cámara de la escena respecto a la referencia mundo del modelo (matriz de rotación 𝑅𝑤𝐸𝑠𝑐 𝑐𝑎𝑚𝐸𝑠𝑐 y vector de translación 𝑡𝑤𝐸𝑠𝑐 𝑐𝑎𝑚𝐸𝑠𝑐 proporcionado por Bundler en la reconstrucción 3D no densa).  Posición de la cámara del objeto respecto a la referencia mundo del modelo (matriz de rotación 𝑅𝑤𝑂𝑏𝑗 𝑐𝑎𝑚𝑂𝑏𝑗 y vector de translación 𝑡𝑤𝑂𝑏𝑗 𝑐𝑎𝑚𝑂𝑏𝑗 proporcionado por Bundler en la reconstrucción 3D no densa).  Posición de la cámara de la escena respecto a la del objeto (matriz de rotación 𝑅𝑐𝑎𝑚𝑂𝑏𝑗 𝑐𝑎𝑚𝐸𝑠𝑐 y vector de translación 𝑡𝑐𝑎𝑚𝑂𝑏𝑗 𝑐𝑎𝑚𝐸𝑠𝑐 calculados mediante SVD partiendo de la matriz fundamental obtenida a partir de los emparejamientos entre la imagen de la escena y la imagen del objeto).  Escala del modelo del objeto (𝑒𝑠𝑐𝑎𝑙𝑎𝑜𝑏𝑗) y del modelo de la escena 𝑒𝑠𝑐𝑎𝑙𝑎𝑒𝑠𝑐.  Escala del vector de translación de la cámara de la escena respecto a la del objeto (𝑒𝑠𝑐𝑎𝑙𝑎𝑡). 74 Figura 44: Ejemplo de transformaciones seguidas durante el posicionamiento. Para posicionar correctamente el objeto cogeremos cada punto 𝑋 𝑖= (𝑥,𝑦,𝑧) del modelo 3D del objeto y: 1. Lo multiplicamos por 𝑒𝑠𝑐𝑎𝑙𝑎𝑒𝑠𝑐/𝑒𝑠𝑐𝑎𝑙𝑎𝑜𝑏𝑗 para tener el objeto a la misma escala que aparece en la escena. 2. Después lo multiplicamos por 𝑅𝑤𝑂𝑏𝑗 𝑐𝑎𝑚𝑂𝑏𝑗 y le sumaremos la translación 𝑡𝑤𝑂𝑏𝑗 𝑐𝑎𝑚𝑂𝑏𝑗 . Con este paso hemos pasado de tener 𝑋 𝑖 referenciado con respecto al mundo del modelo del objeto a tenerlo referenciado con respecto a la cámara del objeto. 3. Multiplicamos 𝑋 𝑖𝑐𝑎𝑚𝑂𝑏𝑗 por 𝑅𝑐𝑎𝑚𝑂𝑏𝑗 𝑐𝑎𝑚𝐸𝑠𝑐 y le sumamos 𝑡𝑐𝑎𝑚𝑂𝑏𝑗 𝑐𝑎𝑚𝐸𝑠𝑐 ∗𝑒𝑠𝑐𝑎𝑙𝑎𝑡. Ahora tenemos las coordenadas del punto referenciadas con respecto a la cámara escena. 4. Solo queda pasar 𝑋 𝑖𝑐𝑎𝑚𝐸𝑠𝑐 a las coordenadas mundo del modelo de la escena. Para ello le restamos 𝑡𝑤𝐸𝑠𝑐 𝑐𝑎𝑚𝐸𝑠𝑐 a 𝑋 𝑖𝑐𝑎𝑚𝐸𝑠𝑐 y lo multiplicamos por𝑅𝑤𝐸𝑠𝑐 𝑐𝑎𝑚𝐸𝑠𝑐−1. Con este último paso ya tenemos el punto en las coordenadas de la escena y por lo tanto solo falta pintarlo por pantalla para comprobar los resultados. wObj (Ref Mundo Obj.) wEsc (ref Mundo Esc.) camObj camEsc 𝑅𝑤𝑂𝑏𝑗 𝑐𝑎𝑚𝑂𝑏𝑗 ,𝑡𝑤𝑂𝑏𝑗 𝑐𝑎𝑚𝑂𝑏𝑗 𝑅𝑐𝑎𝑚𝑂𝑏𝑗 𝑐𝑎𝑚𝐸𝑠𝑐,𝑡𝑐𝑎𝑚𝑂𝑏𝑗 𝑐𝑎𝑚𝐸𝑠𝑐 𝑅𝑐𝑎𝑚𝐸𝑠𝑐 𝑤𝐸𝑠𝑐 ,𝑡𝑐𝑎𝑚𝐸𝑠𝑐 𝑤𝐸𝑠𝑐 75 5.8 Resultados A continuación se muestra un ejemplo de los resultados obtenidos tras posicionar un objeto en la escena. En este ejemplo se utilizan la escena y los objetos del segundo dataset. El objeto a posicionar en la escena va a ser el tigre parcialmente incompleto y que se localiza en la parte derecha de la mesa (figura 45). Figura 45: Imagen de la escena a utilizar. En la figura 46 observamos el modelo del tigre a posicionar en la mesa. A diferencia del modelo del tigre que se visualiza en la mesa, de este modelo se tiene su completa reconstrucción a 360º, por lo que tras posicionar este modelo en la escena se podra visualizar partes del tigre que antes no se visualizaban. 76 Figura 46: Imagen del objeto a utilizar. Figura 47: Resultado de posicionar el modelo del objeto sobre la escena. 77 Figura 48: Resultado de posicionar el modelo del objeto sobre la escena. En la figura 48 se observa que el posicionamiento del objeto no es exacto, para ello basta que nos fijemos en la zona de la cola del tigre para visualizar más claramente el error. Este error es normal ya que la matriz fundamental calculada no es exacta y a partir de esta se han ido realizado numerosos cálculos que han podido incrementar o modificar dicho error. Sin embargo, se podría una vez realizada esta primera aproximación realizar algún calculo posterior para terminar de posicionar el objeto en su posición correcta. 78 79 6. Trabajo Futuro Como trabajo futuro para este proyecto se podrían realizar numerosas mejoras entre las que encontramos las siguientes: 6.1 Optimización mediante kd-tree del algoritmo de emparejamiento En este proyecto se ha programado un algoritmo de emparejamiento que devuelve resultados satisfactorios a costa de un tiempo medianamente elevado. Sin embargo este tiempo de cálculo podría ser reducido considerablemente si para el cálculo de los emparejamientos se utilizaran los arboles kd-tree. El motivo por el cual no se emplearon inicialmente en este proyecto fue debido a la falta de tiempo para su integración e implementación y a que al fin y al cabo el objetivo del proyecto no se veía afectado por la utilización o no de estos. La idea básica de la utilización de kd-tree es poder introducir los diferentes descriptores de la imagen de la escena y del objeto cada uno en su correspondiente árbol kd-tree. Una vez disponemos de un árbol con los descriptores de la escena y de otro con los descriptores del objeto podemos proceder a buscar los descriptores que más se asemejan a un descriptor en un tiempo mucho más reducido. 6.2 Correspondencia con bolsa de palabras En nuestro caso hemos trabajado con un pequeño dataset de objetos y por lo tanto no hemos tenido muchos inconvenientes para trabajar con él. Sin embargo en un futuro dicho dataset podría ser de un tamaño considerable y llegar a convertirse en un quebradero de cabeza, debido al tiempo que requiere comparar las diferentes imágenes de la escena con las de los objetos que tenemos registrados en nuestra base de datos para saber que objetos aparecen en dicha escena. 86 87 8. Bibliografía Papers [1] Noah Snavely, Steven M. Seitz, Richard Szeliski "Modeling the World from Internet Photo Collections". International Journal of Computer Vision, 2007 [2] Yasutaka Furukawa, Jean Ponce "Accurate, Dense and Robust Multi-View Stereopsis". IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009 [3] Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool, "SURF: Speeded Up Robust Features". Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, pp. 346--359, 2008 [4] Lowe, David G. "Object recognition from local scale-invariant features". Proceedings of the International Conference on Computer Vision, 1999 [5] Noah Snavely, Steven M. Seitz, Richard Szeliski. "Photo Tourism: Exploring image collections in 3D". ACM Transactions on Graphics (Proceedings of SIGGRAPH 2006), 2006. [6] Yasutaka Furukawa y Jean Ponce "Accurate, Dense and Robust Multi-View Stereopsis". IEEE Computer Society Conference on Computer Vision and Pattern Recognition, July 2007. [7] A.M Romero y M.Cazorla "Comparativa de detectores de características visuales y su aplicación al SLAM" X Workshop de agentes físicos, Septiembre 2009. [8] Yasutaka Furukawa, Brian Curless, Steven M. Seitz and Richard Szeliski "Reconstrucing Bulding Interiors from Images" ICCV 2009. [9] Marc Pollefeys "Visual modeling with a hand-held camera" International Journal of Computer Vision 2004. [10] Lowe, David G. "Distinctive Image Features from Scale Invariant Features". International Journal of Computer Vision, Vol. 60, No. 2, 2004 [11] J. Matas, O. Chum, M. Urban, T. Pajdla "RobustWide Baseline Stereo from Maximally Stable Extremal Regions". Proc. of British Machine Vision Conference, pages 384-396, 2002. 88 Páginas Web [12] http://phototour.cs.washington.edu/bundler/ [13] http://grail.cs.washington.edu/software/pmvs/ [14] http://www.vlfeat.org/ [15] http://www.wikipedia.org/