Repositorio Institucional de Documentos

Proyecto Final de Carrera Ingenier´ıa en Inform´atica Curso 2011/2012 Gu´ıa tur´ıstica de monumentos basada en reconocimiento visual con un m´ovil Javier Arroyo Espallargas Febrero 2012 Directora: Ana Cristina Murillo Arnal Codirector: Danilo Tardioli Departamento de Inform´atica e Ingenier´ıa de Sistemas Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza II RESUMEN La visi´on es una de las fuentes de informaci´on m´as potentes que tenemos las personas. Adem´as, cada vez nos encontramos con m´as c´amaras y grandes bases de datos de im´agenes a nuestra disposici´on. Dada esta situaci´on, el procesamiento autom´atico e inteligente de im´agenes esta adquiriendo gran relevancia en el desarrollo de nuevas tecnolog´ıas, que basan su desarrollo en t´ecnicas de visi´on por computador. En particular, en este proyecto el trabajo se ha centrado en las tecnolog´ıas aplicables a dispositivos m´oviles para aprovechar sus c´amaras integradas y su cada vez mayor capacidad de computo. En el presente proyecto se ha desarrollado una aplicaci´on que pueda servir como gu´ıa tur´ıstica aprovechando la c´amara de un tel´efono m´ovil, siendo capaz de reconocer diferentes edificios o monumentos mediante el procesamiento de im´agenes. En esta aplicaci´on, a diferencia de la gran mayor´ıa de aplicaciones similares, el objetivo es poder realizar todo el procesamiento de la imagen en el dispositivo, mientras que muchas otras aplicaciones hacen uso de la red para poder acceder a sistemas m´as potentes que realicen los c´alculos. Con este objetivo, se han estudiado y desarrollado diferentes t´ecnicas de visi´on por computador que permitan el reconocimiento de un edificio, haciendo especial hincapi´e, adem´as de un buen rendimiento en el reconocimiento, en que sean capaces de ejecutarse en tales dispositivos con un tiempo de respuesta aceptable. El proceso llevado a cabo tiene dos grandes bloques. Por un lado, se ha recopilado una base de datos de im´agenesdeedificiosdeinter´es. Esta informaci´on de referencia debe almacenarse de manera adecuada para su posterior uso, para lo cual se ha dise˜nado un proceso basado en t´ecnicas de extracci´on de puntos de inter´es en im´agenes. Por otro lado se han estudiado diferentes m´etodos para el reconocimiento de la imagen del usuario. Este bloque tiene tres pasos b´asicos: el usuario captura una imagen de un edificio; la aplicaci´on dise˜nada, comparar´a la informaci´on de esa imagen con las de referencia, haciendo uso de estructuras de b´usqueda de ´arbol y vocabularios de descriptores de im´agenes, muy utilizados en visi´on por computador. Una vez realizada la comparaci´on, la aplicaci´on devuelve la respuesta al usuario con informaci´on relativa al monumento. En este ´ultimo paso, por un lado se devuelve informaci´on textual a cerca del monumento, y por otro lado se ha estudiado e implementado una t´ecnicabasadaenlageometr´ıa entre varias im´agenes de una misma escena, que permite a˜nadir informaci´on virtual, es decir, aumentar la realidad. Todas las t´ecnicas estudiadas en cada paso han sido evaluadas en el entorno descrito y las configuraciones con mejor rendimiento han sido integradas con una interfaz implementada para la plataforma Android, tambi´en desarrollada en este proyecto. El prototipo final tiene unos resultados de reconocimiento buenos y un tiempo de respuesta adecuado para una aplicaci´on que necesita interactuar con un usuario. III IV ´ Indice general 1. Introducci´on 1 1.1. Motivaci´on ....................................... 1 1.2. ObjetivosyAlcancedelproyecto ........................... 2 1.3. HerramientasyEntornodeTrabajo ......................... 3 1.4. EstructuradelaMemoria ............................... 3 2. Evaluaci´on de similitud 5 2.1. Introducci´on....................................... 5 2.2. Representaci´on de Im´agenes.............................. 6 2.3. Algoritmos de similitud ................................ 7 2.3.1. Representaci´onCompleta ........................... 7 2.3.2. Bolsa de Palabras o Clusterizaci´on ...................... 10 2.4. Experimentos...................................... 13 2.4.1. Representaci´oncompleta............................ 14 2.4.2. Bolsa de Palabras o Clusterizaci´on ...................... 15 3. Realidad Aumentada 21 3.1. Introducci´on....................................... 21 3.2. Restricciones Geom´etricas............................... 22 3.3. Implementaci´on..................................... 22 3.4. Experimentos...................................... 23 4. Aplicaci´on Desarrollada 27 4.1. M´odulos de la Aplicaci´on ............................... 27 4.1.1. M´odulo de Interacci´onconelUsuario .................... 28 4.1.2. M´odulo de An´alisisdelaImagen ....................... 28 4.1.3. M´odulodeRealidadAumentada ....................... 29 4.2. Dise˜no de la Aplicaci´on ................................ 30 4.2.1. PantallaPrincipal ............................... 30 V ´ INDICE GENERAL ´ INDICE GENERAL 4.2.2. Pantalla An´alisisdeImagen.......................... 32 4.2.3. PantallaResultados .............................. 32 4.2.4. Pantalla informaci´ondelEdificio ....................... 33 4.2.5. PantallaRealidadAumentada......................... 33 5. Conclusiones 35 5.1. Conclusiones ...................................... 35 5.2. Trabajofuturo ..................................... 36 5.3. Valoraci´onpersonal................................... 36 A. Exp. Representaci´on Completa 37 A.1.Exp.1 .......................................... 37 A.2.Exp.2 .......................................... 40 A.3.Exp.3 .......................................... 41 A.4.Conclusiones ...................................... 42 B. Bolsa de Palabras 43 B.1.K-Means......................................... 43 B.2.AlgoritmoBOW .................................... 44 C. Experimentos BOW 49 C.1.SinGPS......................................... 49 C.1.1. Experimento1................................. 49 C.1.2.Experimento2 ................................. 51 C.1.3.Experimento3 ................................. 52 C.2.ConGPS ........................................ 54 C.2.1. Experimento1................................. 54 C.2.2.Experimento2 ................................. 55 C.2.3.ExperimentoFinal............................... 55 D. Android 61 D.1. Introducci´on....................................... 61 D.2.AndroidOS....................................... 61 D.3.KitdeDasarrolloSoftwaredeAndroid(SDK).................... 62 D.4.KitdeDasarrolloNativodeAndroid(NDK)..................... 63 E. Ejemplos Realidad Aumentada 65 VI ´ INDICE GENERAL ´ INDICE GENERAL F. DFD del sistema de reconocimiento 69 F.1.Nivel0.......................................... 69 F.2.Nivel1.......................................... 69 F.3.Nivel2.1......................................... 69 F.4.Nivel2.2......................................... 70 F.5.Nivel2.3......................................... 70 G. GPS 73 G.1. Utilidad de el GPS en este proyecto ......................... 73 G.2. C´alculodedistanciasentrecoordenadas ....................... 73 H. Gesti´on del Proyecto 75 Bibliograf´ıa 78 VII ´ INDICE GENERAL ´ INDICE GENERAL VIII Cap´ıtulo 1 Introducci´on Este cap´ıtulo describe la motivaci´on que ha llevado al desarrollo de este proyecto, as´ı como la descripci´on de los objetivos y el alcance del mismo. Tambi´en se detallar´anlasherramientasy el entorno en el que se ha realizado. 1.1. Motivaci´on En la actualidad, el reconocimiento de objetos dentro de bases de datos de im´agenes de gran tama˜no es un problema de visi´on por computador con numerosas aplicaciones, en particular en el ´ambito de los smartphones (v´ease el ejemplo de la Figura 1.1). Figura 1.1: Ejemplo de aplicaci´on de reconocimiento visual en smartphones: identificaci´on de monumentos. El t´ermino smartphone denota a un tel´efono m´ovil que ofrece m´as funciones que un tel´efono convencional, con una mayor capacidad de computo, un sistema operativo m´as potente que permite instalar aplicaciones y el uso de m´ultiples sensores integrados en el tel´efono. Existen multitud de modelos de diferentes fabricantes, con diferentes Sistemas Operativos (SO). Dependiendo 1 2.3. ALGORITMOS DE SIMILITUD CAP´ ITULO 2. EVALUACI ´ ON DE SIMILITUD Figura 2.3: Algoritmo de b´usqueda de im´agenes similares en una base de datos. Se divide en dos fases, la fase de entrenamiento y la fase de consulta. B´usqueda del vecino m´as cercano (NN): consiste en una b´usqueda exhaustiva. Dada una imagen de test y una imagen de referencia con la que queremos comparar, este algoritmo compara cada caracter´ıstica de la imagen de prueba con cada una de la imagen de referencia para buscar posibles correspondencias. El coste de este algoritmo de correspondencia entre im´agenes es cuadr´atico dependiendo del n´umero de caracter´ısticas a emparejar (n): O(n2). B´usqueda aproximada del vecino m´as cercano (ANN): realiza la misma tarea que la b´usqueda anterior pero con un coste computacional menor, gracias a mantener la informaci´on de referencia m´as ordenada. Para ello, construye una estructura de ´arbol, en particular k-d trees [4], para ordenar los datos. Esto permite obtener unos tiempos de ejecuci´on mucho m´as bajos, con resultados similares a los que se obtienen con b´usqueda exhaustiva. Un inconveniente de esta b´usqueda es que no siempre garantiza que se encuentre la soluci´on ´optima.Elcostedelab´usqueda es O(log(n)). Para m´as detalle, en el anexo C se pueden ver experimentos que muestran las mejoras del uso de k-d trees. 8 CAP´ ITULO 2. EVALUACI ´ ON DE SIMILITUD 2.3. ALGORITMOS DE SIMILITUD Figura 2.4: Evaluaci´on de similitud entre im´agenes basada en representaci´on completa. Este algoritmo selecciona aquella imagen de referencia con m´as correspondencias encontradas. La imagen Ref1 tiene una correspondencia, Ref2 dos y Ref3 ninguna. Por lo que la elegida ser´aRef2. B´usqueda aproximada del vecino m´as cercano con m´etodos robustos: dado que la b´usqueda mediante el algoritmo ANN o NN puede generar correspondencias incorrectas, se puede a˜nadir a estos m´etodos un paso de estimaci´on robusta, como es el m´etodo RANSAC [8]. Es com´un estimar una restricci´on geom´etrica entre varias im´agenes de una misma escena (homograf´ıa o matriz fundamental) mediante RANSAC a la vez que se eval´ua que correspondencias entre im´agenes son consistentes con ella [10]. Esto se consigue rechazar muchas correspondencias incorrectas que no son consistentes con el modelo geom´etrico que se estima de la escena. Pese a que la robustez de las correspondencias crece notablemente, este m´etodo no resulta del todo pr´actico para el fin que se persigue en este trabajo, ya que el tiempo de ejecuci´on de esta estimaci´on robusta es muy elevado, y lo que se intenta es encontrar un m´etodo eficiente y de r´apida ejecuci´on. 9 2.3. ALGORITMOS DE SIMILITUD CAP´ ITULO 2. EVALUACI ´ ON DE SIMILITUD 2.3.2. Bolsa de Palabras o Clusterizaci´on En este caso se intenta almacenar una representaci´on m´as comprimida de los descriptores de las im´agenes de referencia. Se agrupan las caracter´ısticasdetodaslasim´agenes de referencia en n conjuntos (o cl´usters) de descriptores parecidos, o lo que se suele denominar, un vocabulario de n palabras visuales [14] [16]. Este vocabulario almacena por un lado los centroides de cada palabra y por otro una tabla que indica en que im´agenes de referencia y con qu´e frecuencia aparece cada palabra (esta estructura se suele denominar “inverted file index”[6], y tiene su origen en trabajos de an´alisis de documentos de texto, de ah´ı la nomenclatura). Utilizando diversos m´etodos de comparaci´on, basados en analizar que palabras aparecen en una imagen de consulta y las de referencia, se puede calcular una similitud entre ellas (ver Figura 2.5). Estos m´etodos de evaluaci´on de similitud mediante bolsa de palabras se dividen en dos partes. La primera consiste en obtener el vocabulario a partir de las im´agenes de referencia, y los histogramas de votos a cada palabra que tiene cada imagen de referencia. La segunda consiste en asociar cada descriptor de la imagen de consulta a una palabra obteniendo su histograma de votos a palabras del vocabulario previamente calculado. A continuaci´on se detalla m´as detenidamente estos dos procesos. Creaci´on del Vocabulario Para la creaci´on del vocabulario se ha utilizado el algoritmo de k-means [1]. Este algoritmo busca los kgrupos m´as representativos entre los datos a analizar. Cada uno de los kgrupos o palabras se representa con el valor medio de los elementos que pertenecen a ´el, wk. M´as formalmente, dado un conjunto de observaciones (x1,x2,...,xn) donde cada observaci´on es un vector de dimensi´on d,k-means trata de agrupar esos ndatos en kgrupos que formar´an el vocabulario V, con k<=n,V={w1,w2,...,wk}donde cada wkrepresenta una palabra del vocabulario. El funcionamiento b´asico del algoritmo es el siguiente: 1. Se seleccionan kelementos del conjunto de observaciones, estos representar´an los centroides iniciales de las palabras del vocabulario. 2. Seleccionados los centros de esas kpalabras, se asocia cada observaci´on a la palabra m´as cercana. 3. El nuevo centroide de cada una de las kpalabras ser´a la media de todos los elementos que han sido asignados a esa palabra. 4. Se repiten los pasos 2 y 3 hasta que el algoritmo converge. La convergencia se produce cuando no hay cambio en los pasos 2 y 3, obteniendo as´ı un conjunto estable de palabras. 10 CAP´ ITULO 2. EVALUACI ´ ON DE SIMILITUD 2.3. ALGORITMOS DE SIMILITUD Figura 2.5: Evaluaci´on de similitud entre im´agenes basada en representaci´on de bolsa de palabras. Primero, a partir de los descriptores de las im´agenes de referencia obtenemos las kpalabras que formar´an el vocabulario a), en este caso {W1, ..., W4}. A partir de este vocabulario creamos el inverted file index b), almacenando la informaci´on de forma compacta. Con esta informaci´on, se asocia cada descriptor de la imagen de consulta a la palabra m´as representativa, obteniendo su histograma de votos a palabras c). Por lo que comparando dicho histograma con cada uno de los almacenados en el inverted file index podemos determinar la imagen m´as similar d). La forma en que se realiza la primera asignaci´on de los kcl´uster iniciales puede ser aleatoria, o basada en el uso de diversos algoritmos como puede ser el creado por Arthur and Vassilvitskii [7], utilizado en el desarrollo de este proyecto. El algoritmo k-means devuelve a qu´e palabra se asocia cada unos de los descriptores de las im´agenes de referencia, para disponer de esa informaci´on de forma m´as compacta se comprime, obteniendo la matriz del inverted file index. Esta matriz almacena un histograma de votos a cada palabra del vocabulario para cada una de las im´agenes de referencia (Figura 2.6). Evaluaci´on de similitud mediante Bolsa de palabras Una vez construido el vocabulario y la representaci´on de las im´agenes de referencia, se utilizan los siguientes pasos para evaluar una imagen nueva. 11 2.3. ALGORITMOS DE SIMILITUD CAP´ ITULO 2. EVALUACI ´ ON DE SIMILITUD Figura 2.6: Inverted File Index.Representa para cada imagen de referencia {Im1, Im2, Im3}el n´umero de votos a cada palabra que ha resultado en la asignaci´on de sus descriptores a las palabras del vocabulario {W1, W2, W3, W4}, es decir, su histograma. 1. Extracci´on de caracter´ısticas SURF de imagen test. 2. B´usqueda de la palabra que se asigna a cada caracter´ıstica. Obteniendo as´ı un vector de longitud igual al n´umero de caracter´ısticas, donde cada posici´on indica a que palabra ha sido asignada dicha caracter´ıstica. 3. Histograma de palabras. A partir del vector obtenido en el paso anterior se crea un vector de longitud k(n´umero de palabras del vocabulario) donde se almacena la frecuencia con que ha ocurrido cada palabra en esta imagen. Este vector es el histograma de palabras que aparecen en esta imagen, similar al que tenemos para cada imagen de referencia. 4. Haciendo uso de este histograma se calcula una medida de similitud. Hemos estudiado dos posibilidades, detalladas en el Anexo B. Sim1: Comparaci´on basada en los histogramas de palabras de cada imagen, es decir, se compara el histograma de la imagen consulta con cada uno de los histogramas de las im´agenes de referencia, y aquellos cuya distancia L1 (norma 1) es menor ser´an seleccionados como m´as similares. Dist1(Ii,I consulta)=|Hi−Hconsulta|(2.1) Donde Hirepresenta el histograma de palabras asociado a la imagen de referencia i (Ii), y Hconsulta el histograma de palabras asociado a la imagen consulta (Iconsulta). Sim2: Medida basada en la frecuencia con la que aparece cada palabra wen cada imagen de referencia Ii. Es decir, cada palabra que aparece en la imagen de consulta 12 CAP´ ITULO 2. EVALUACI ´ ON DE SIMILITUD 2.4. EXPERIMENTOS (Iconsulta) vota a aquellas de im´agenes de referencia donde aparec´ıa con una frecuencia m´as similar. Las im´agenes seleccionadas c´omo m´as similares ser´an aquellas con m´as votos. Votos(Ii,w j)=⎧ ⎨ ⎩ Hc(j)si[Hc(j)−Hi(j)] == min([Hc(j)−H1(j)]), ..., [Hc(j)−Hn(j)] 0 en cualquier otro caso (2.2) Votos i= n  j=1 Votos(Ii,w j) (2.3) Donde Hc(j)eseln´umero de votos a la palabra jexistente en la imagen consulta. Hi(j) es el n´umero de votos a la palabra jexistente en la imagen de referencia i. 2.4. Experimentos A continuaci´on se detallan los experimentos m´as representativos realizados para evaluar la similitud entre im´agenes utilizando los m´etodos descritos anteriormente. En esta memoria principal detallamos solamente los experimentos finales m´as significativos, dejando en los Anexos A y C los detalles de los dem´as experimentos realizados, que justifican las diferentes decisiones a lo largo del proceso y dise˜no. Los experimentos que se detallan a continuaci´on, as´ı como los detallados en los Anexos A y C, se han realizado en primer lugar sobre un computador (procesador Intel Core 2 Duo 2.1 GHz, memoria RAM 4 GB). Esto es debido a la necesidad de realizar pruebas a gran escala para evaluar aquellos m´etodos con mejores resultados y una r´apida ejecuci´on para su posterior migraci´on al dispositivo m´ovil. En todos los experimentos se utiliza una base de datos que contiene un n´umero determinado de im´agenes de referencia, de las cuales se extrae la informaci´on y se almacena de diferentes formas seg´un el m´etodo ejecutado. Como im´agenes de consulta se utiliza un conjunto variado de im´agenes distintas a las almacenadas en la base de datos, entre las que se incluyen im´agenes de edificios obtenidas de Internet. El objetivo en este caso, o criterio de similitud que queremos cumplir, es que las im´agenes contengan el mismo edificio. Es decir, que la b´usqueda de las im´agenes m´as similares nos indique que monumento aparece en la imagen de consulta. Es importante estudiar qu´em´etodos dan mejores resultados en la identificaci´on de los monumentos/edificios, pero tambi´en se debe prestar atenci´on a aquellos que son m´as eficientes (tanto en ocupaci´on de memoria y tiempo de ejecuci´on), ya que los m´etodos desarrollados finalmente se deben implementar en un tel´efono m´ovil. 13 2.4. EXPERIMENTOS CAP´ ITULO 2. EVALUACI ´ ON DE SIMILITUD La medida utilizada para evaluar la calidad del reconocimiento de cada m´etodo es el porcentaje de im´agenes cuyo contenido ha sido reconocido correctamente. Adem´as como la aplicaci´on final tiene interacci´on con el usuario, queremos que la aplicaci´on resulte realista y robusta. Por eso, en casos en que el reconocimiento no este claro y haya varios candidatos con similitud parecida, evaluaremos la opci´on de dar como soluci´on varias opciones ordenadas por similitud para que el usuario decida. Se ha realizado el estudio tanto de los m´etodos de representaci´on completa (subsecci´on 2.4.1) como mediante el uso de bolsa de palabras (subsecci´on 2.4.2), para evaluar la t´ecnica m´as adecuada para implementar en el dispositivo m´ovil. 2.4.1. Representaci´on completa En primer lugar se realizaron una serie de experimentos para evaluar los m´etodos de representaci´on completa. Detalles de los experimentos para su evaluaci´on y selecci´on de que medida de similitud es m´as adecuada est´an en el Anexo A. Como resumen vemos en la Figura 2.7 que los resultados obtenidos mediante la utilizaci´on de una b´usquedaexhaustiva(NN)frentealab´usqueda aproximada (ANN) (subsecci´on 2.3.1) son similares, pero con la diferencia de que el tiempo de ejecuci´on mediante la utilizaci´on de NN frente a ANN se incrementa considerablemente. En este caso el tiempo de simulaci´on total pasa de 910 a 1129 segundos. Figura 2.7: Acierto en el reconocimiento de edificios utilizando b´usqueda NN vs ANN. Los tres primeros grupos de barras representan los resultados o porcentaje de acierto para la medida de similitud Sim1 (ec. A.6) teniendo en cuenta si se elige la m´as votada a) o entre las 3 ´o5m´as votadas hay una correcta (b) y c) respectivamente). Idem para los otros tres grupos de barras pero con Sim2 (ec. A.7). 14 CAP´ ITULO 2. EVALUACI ´ ON DE SIMILITUD 2.4. EXPERIMENTOS Aunque los resultados de reconocimiento son aceptables, estos m´etodos presentan el inconveniente, para la implementaci´on en un dispositivo m´ovil, de un tiempo de ejecuci´on todav´ıa bastante elevado. Adem´as un elevado consumo de memoria, porque se deber´ıa almacenar en una matriz todos los descriptores de las im´agenes de referencia y realizar la comparaci´on con cada una de ellas. Suponiendo que de cada imagen se obtienen ncarater´ısticas SURF (unas 1000 de media), y que cada descriptor est´a compuesto por un vector de longitud d(64) de datos “float”, la representaci´on ocupar´a: d∗n∗4B= 375KB por imagen Suponiendo una base de datos de 100 im´agenes, el tama˜no que ocupa toda esa informaci´on aproximadamente es 375KB ∗100 = 37500KB =36,62MB. Viendo estos datos de ocupaci´on de memoria, se ve claramente que no ser´ıa nada recomendable su implantaci´on completa en un dispositivo m´ovil. Conforme aumente la base de datos, la memoria necesaria ser´ıa muy elevada para un un m´ovil y ser´ıa necesaria una conexi´on remota para acceder a estos datos de referencia. 2.4.2. Bolsa de Palabras o Clusterizaci´on En segundo lugar, se han estudiado t´ecnicas de comparaci´on de im´agenes basadas en en agrupaciones de descriptores, t´ecnica m´as frecuentemente referida como clusterizaci´on o bolsa de palabras, que utilizaremos en el resto del documento. Estos algoritmos son muy utilizados por sus ventajas de eficiencia y requerimientos de memoria m´as bajos. Se usan en muchos campos para procesar datos, entre los cuales se encuentra el reconocimiento de im´agenes. Al igual que en la subsecci´on anterior, aqu´ıs´olo se incluye el experimento m´as completo realizado con estos m´etodos. Experimentos anteriores est´an detallados en el Anexo C, donde se muestran pruebas iniciales, evaluaciones de las distintas medidas de similitud, y an´alisis de la utilizaci´on del GPS integrado en los m´oviles. El experimento principal descrito a continuaci´on confirm´o los dos pasos siguiente como claves para obtener buenos resultados: 1. Por un lado, la incorporaci´on del filtrado con GPS (en el Anexo G se describen m´as detalles acerca del GPS), que selecciona las im´agenes candidatas que adem´as de alta similitud, tengan una distancia m´etrica dentro de un rango. Este filtrado se podr´ıa incluir con cualquier m´etodo de similitud, pero se tom´o la decisi´ on de s´olo evaluarlo con los m´etodos que mejores resultados proporcionaban. 2. Por otro lado, a la hora de realizar la asignaci´on de palabras a cada caracter´ıstica de la imagen consulta, es importante el uso de k-d trees para realizar una b´usqueda de la palabra m´as cercana, que ahorra mucho tiempo respecto a hacer una b´usqueda exhaustiva. 15 2.4. EXPERIMENTOS CAP´ ITULO 2. EVALUACI ´ ON DE SIMILITUD Configuraci´on del experimento Modo b´usqueda: Bolsa de Palabras Nopalabras vocabulario: 600 Noim´agenes prueba: 141 En las Figuras 2.8 y 2.9 se observan los resultados de esta pruebas. La primera (2.8) muestra los resultados con la medida de similitud Sim1(ec. 2.1) mostrados en la Tabla 2.1, y Sim2(ec. 2.3) mostrados en la Tabla 2.2. Se utilizan estructuras k-d tree para la b´usquedadelapalabra asignada a cada punto SURF extra´ıdo de la imagen consulta. La Figura 2.9, sin embargo muestra los resultados de la prueba haciendo una b´usquedaexhaustivaalahoradeasignarunapalabra a cada caracter´ıstica. Asignaci´on de palabras con k-d tree Top 1 Top 3 Top 5 Sin GPS 65.24 % 76.59 % 80.85 % GPS 1 Km 78.01 % 88.65 % 91.48 % GPS 0.5 Km 84.39 % 91.48 % 93.61 % Tiempo de cada test 0.2 s Tabla 2.1: Reconocimiento correcto de edificios/monumentos utilizando k-d tree y Sim1 (ec.2.1): Porcentaje de im´agenes de consulta donde se encuentra un resultado correcto entre los “n” m´as similares (“top-n”). En cada una de las filas aparece los resultados teniendo en cuenta si se selecciona entre el top-1, top-3 o top-5 sin hacer uso del GPS, GPS con un radio de 1 Km o 0.5 Km. “Top-n” nos indica los resultados que obtenemos si se observan los “n” resultados m´as similares, es decir, si en esos “n” resultados hay alguna imagen asociada correctamente. Top 1 Top 3 Top 5 Sin GPS 39.00 % 60.28 % 66.66 % GPS 1 Km 63.82 % 78.01 % 83.68 % GPS 0.5 Km 74.46 % 86.52 % 92.19 % Tiempo de cada test 0.2 s Tabla 2.2: Reconocimiento correcto de edificios/monumentos utilizando k-d tree y Sim2 (ec.2.3). Tabla con el mismo formato que Tabla 2.1 De estas gr´aficas se puede observar que con la medida de similitud 1 se obtienen mejores resultados, adem´as del notable incremento en el porcentaje de acierto al incluir el GPS. Se pasa de un 65.24 % sin usar GPS a un 78.01 % usando un radio de 1 Km ´o 84.39 % con radio 0.5 Km. En el caso de la medida de similitud 2 se observa que los resultados son inferiores a los mostrados en otras pruebas. Esto es debido a que al asignar las palabras utilizando k-d trees la precisi´on disminuye, por lo que el m´etodo se ve perjudicado. 16 CAP´ ITULO 2. EVALUACI ´ ON DE SIMILITUD 2.4. EXPERIMENTOS Figura 2.8: Reconocimiento correcto de edificios/monumentos utilizando o no filtro GPS y k-d tree Top 1 Top 3 Top 5 Sin GPS 71.63 % 78.72 % 82.97 % GPS 1 Km 80.14 % 88.65 % 92.19 % GPS 0.5 Km 87.94 % 91.48 % 93.61 % Tiempo de cada test 15.42 s Tabla 2.3: Reconocimiento correcto de edificios/monumentos utilizando b´usqueda exhaustiva y Sim1 (ec.2.1). Tabla con el mismo formato que Tabla 2.1 Asignaci´on de palabras con b´usqueda exhaustiva En este caso se observa que los resultados son ligeramente mejores que los obtenidos haciendo uso de k-d trees. Por ejemplo, sin uso de GPS, con b´usqueda exhaustiva obtenemos un 71.63 % frente a un 65.24 % con k-d tree, para la medida Sim1 seleccionando s´olo la imagen m´as similar. Pero el principal inconveniente de la b´usqueda exhaustiva es el tiempo de ejecuci´on que lleva asociado. Como se observa en la gr´afica pasamos de un tiempo de ejecuci´on del test con k-d trees de 401 s a 3700 s algo que hay que tener en cuenta ya que en dispositivo m´ovil a´un se ver´am´as acentuado. El tiempo medio de asignaci´on de palabra con b´usqueda exhaustiva es 15.42 s frente a 0.2 s mediante la utilizaci´on de k-d trees, como se ve en la Figura 2.10. Top 1 Top 3 Top 5 Sin GPS 44.68 % 68.08 % 76.59 % GPS 1 Km 71.63 % 84.39 % 90.78 % GPS 0.5 Km 78.01 % 90.78 % 95.03 % Tiempo de cada test 15.42 s Tabla 2.4: Reconocimiento correcto de edificios/monumentos utilizando b´usqueda exhaustiva y Sim2 (ec.2.3). Tabla con el mismo formato que Tabla 2.1 17 3.4. EXPERIMENTOS CAP´ ITULO 3. REALIDAD AUMENTADA Figura 3.3: Esquema algoritmo realidad aumentada. se ve en la imagen derecha de la Figura 3.4, limitamos la regi´on d´onde se buscar´an correspondencias. En el Anexo E se pueden observar m´as ejemplos. Figura 3.4: Correspondencias de puntos SURF entre imagen de referencia y la de consulta del usuario. En la imagen izquierda aparecen representados todos las correspondencias, mientras que en la imagen derecha s´olo aparecen representados las correspondencias dentro de la regi´on que nos interesa para a˜nadir informaci´on aumentada. Como se observa en ambas im´agenes de la Figura 3.4, existen correspondencias err´oneas. Como las correspondencias son la base para estimar la matriz H y tienen “ruido” (errores), necesitamos estimar dicha matriz a partir de las correspondencias pero utilizando un m´etodo robusto que sea capaz de procesar datos con ruido, como es el algoritmo RANSAC mencionado anteriormente. Este algoritmo estimar´asimult´aneamente la homograf´ıa y el subconjunto de 24 CAP´ ITULO 3. REALIDAD AUMENTADA 3.4. EXPERIMENTOS correspondencias consistentes con la misma. Tras estimaci´on de H y filtrado de las correspondencias consistentes con ella, mantenemos s´olo el subconjunto de correspondencias entre imagen de referencia y consulta, que como se puede ver (Figura 3.5) son pr´acticamente 100 % correctas. Figura 3.5: Filtrado de correspondencias tras el c´alculo de H y exclusi´on de aquellas no consistentes mediante RANSAC. En esta ´ultima Figura 3.6, en la imagen izquierda se observa como las cuatro coordenadas que limitan la regi´on en la imagen de referencia se proyectan sobre la imagen de consulta utilizando la matriz H. Aplicando esta matriz a cada uno de los puntos de la imagen del interior del edificio, proyectamos esa imagen sobre la imagen del usuario, obteniendo como resultado final la imagen derecha. Figura 3.6: Proyecci´on de la regi´on e imagen interior sobre la imagen consulta. En la imagen izquierda aparecen proyectadas sobre la imagen consulta las cuatro coordenadas de la regi´on marcada en la imagen de referencia para proyectar la imagen interior del edificio. En la derecha aparece la imagen interior proyectada sobre la imagen consulta. Pero dado que este algoritmo se ha creado para que la adici´on de informaci´onextraala 25 3.4. EXPERIMENTOS CAP´ ITULO 3. REALIDAD AUMENTADA escena se haga autom´aticamente, no siempre funciona de forma perfecta. Hay ocasiones en las que la precisi´on con la que se calcula la matriz H no es del todo precisa y la proyecci´on no es tan perfecta como nos gustar´ıa (ver Figura 3.7). En el siguiente ejemplo se puede observar esto. Adem´as en el Anexo E se encuentra alg´un otro ejemplo. 1) 2) 3) 4) Figura 3.7: Ejemplo de proyecci´on ruidosa. En la imagen 1) se observan todas las correspondencias dentro de la regi´on donde se proyectar´a la imagen interior. En la imagen 2) tras calcular la matriz de homograf´ıa H y eliminar aquellas correspondencias no consistentes, s´olo quedan las correctas. En la imagen 3) proyectamos d´onde corresponden las coordenadas de la regi´on en la imagen consulta. Finalmente, la imagen 4) muestra el resultado que se muestra al usuario. 26 Cap´ıtulo 4 Aplicaci´on Desarrollada En este cap´ıtulo se explica los diferentes m´odulos que componen aplicaci´on dise˜nada, Secci´on 4.1, as´ı como la navegaci´on a trav´es de las diferentes pantallas de la aplicaci´on, Secci´on 4.2. Algunos otros detalles relacionados con la implementaci´on son: el Anexo D con m´as detalles a cerca del sistema Android, el Anexo F donde se encuentran los diagramas de flujo de datos de la aplicaci´on desarrollada y el Anexo H con la gesti´on del proyecto. 4.1. M´odulos de la Aplicaci´on A continuaci´on se va a explicar detalladamente los m´odulos b´asicos que forman nuestra aplicaci´on. Estos m´odulos, b´asicamente se pueden dividir en tres grandes grupos (Figura 4.1), el m´odulo de interacci´on con el usuario, el cual est´a desarrollado en lenguaje Java; y el m´odulo de an´alisis y evaluaci´on de similitud y el m´odulo de realidad aumentada, los cuales hacen uso de funciones de la librer´ıa OpenCV y est´an escritos en los lenguajes C y C++. Figura 4.1: M´odulos de la Aplicaci´on. 1) M´odulo de interacci´on con el usuario. Implementado en lenguaje Java. Contiene las clases Java para la gesti´on de los eventos de la aplicaci´on al interactuar con el usuario, as´ı como para invocar a la librer´ıa OpenCV o Google Maps. 2) M´odulo para el an´alisis de la imagen, se divide en 2 subm´odulos, uno para la generaci´on del vocabulario y otro para el evaluaci´on de similitud. 3) M´odulo para la implementaci´on de realidad aumentada. 27 4.1. M ´ ODULOSDELAAPLICACI ´ ON CAP´ ITULO 4. APLICACI ´ ON DESARROLLADA 4.1.1. M´odulo de Interacci´on con el Usuario Este m´odulo es el encargado de gestionar la interacci´on con el usuario, es decir, es la implementaci´on de la aplicaci´on que interact´ua con el usuario y cuyo uso est´a detallado en la Secci´on 4.2. Esta parte del proyecto se ha programado en lenguaje Java, ya que para la programaci´on de Android se utiliza normalmente este lenguaje. Las clases que componen este m´odulo son las siguientes: CityCam.java: clase principal de nuestro proyecto. Es la encargada de iniciar todos los componentes y en ella se carga la ventana principal de la aplicaci´on y de gestionar los eventos en esta. PantallaMuestraImagenes.java: es una de las clases que se encargan de gestionar los eventos ocurridos en la pantalla donde se muestran los resultados tras el an´alisis de la imagen del usuario. Hay tantas clases como pantallas tiene nuestra aplicaci´on. LibreriaOpenCV.java: en esta clase cargamos nuestro m´odulo de OpenCV donde se realiza el an´alisis de la imagen. Tambi´en aparecen definidas las funciones de c´odigo nativo a las cuales podemos llamar desde c´odigo Java. En nuestro caso aparecen definidas las funciones An´alisis yRealidadAumentada. InfoMapa.java: clase encargada de la carga de los mapas de Google Maps. 4.1.2. M´odulo de An´alisis de la Imagen En este m´odulo aparecen definidas todas las funciones que realizan el an´alisis de la imagen, para evaluar la similitud con respecto a las im´agenes de la base de datos. Todas ellas est´an escritas en C y C++. Estas funciones se pueden agrupar en dos grupos, las que se utilizan para generar el vocabulario y aquellas que se utilizan para evaluar la similitud de una imagen dada. En nuestro caso en la implantaci´on en el dispositivo m´ovil s´olo se han integrado las funciones de evaluaci´on de similitud, ya que se supone que la generaci´on de vocabulario es independiente y se ha generado previamente y el usuario nunca tendr´a acceso a ello. Generaci´on de Vocabulario Este subm´odulo es el encargado de generar la matriz de datos (Inverted File Index) que luego hace uso el m´odulo de evaluaci´on de similitud. El algoritmo lo que realiza es, en primer lugar extraer las caracter´ısticas SURF de cada imagen de la base de datos y almacenarlas en una matriz. Una vez se tienen todas caracter´ısticas almacenadas, se aplica el algoritmo de clusterizaci´on, KMeans, el cual se encarga de generar a partir de todas esas caracter´ısticas el vocabulario de npalabras. Como se indica en el Anexo B, este nos devuelve a la palabra a la 28 CAP´ ITULO 4. APLICACI ´ ON DESARROLLADA 4.1. M ´ ODULOS DE LA APLICACI ´ ON cual se asocia cada caracter´ıstica, por lo que a partir de esta informaci´on generamos el Inverted File Index que luego se almacena en el dispositivo m´ovil junto a la matriz de centros de cada una de las palabras del vocabulario, para que el algoritmo de evaluaci´on de similitud haga uso de esta informaci´on. Por tanto, de este m´oduloseimplantaeneldispositivom´ovil el fichero Inverted File Index y la matriz de centros de las palabras del vocabulario generado, ya que esta informaci´on es necesaria para la evaluaci´on de similitud entre im´agenes. Evaluaci´on de Similitud En este subm´odulo, existen funciones para realizar la evaluaci´on de similitud de una imagen tomada por el usuario con las de la im´agenes de la base de datos. Las funciones m´as importantes que lo componen son: LeerInvertedFileIndex: a partir de un fichero de texto, esta funci´on se encarga de cargar en la memoria del dispositivo la matriz conocida como Inverted File Index,lacualhasido generada anteriormente. LeerCentrosPalabras: funci´on similar a la anterior, se encarga de cargar en memoria la matriz de centros de cada una de las palabra que forman el vocabulario. LeerCoordenadasGPS: tambi´en se almacena en un fichero las coordenadas de los edificios de nuestra base de datos, por lo que esta funci´on carga en memoria esta informaci´on. Extracci´onSURF: funci´on encargada de obtener las caracter´ısticas SURF de la imagen del usuario. Invoca a la funci´on de la librer´ıa OpenCV, cvExtractSURF. EncontrarPalabra: esta funci´on busca cual es la palabra m´as cercana a la cual se asocia cada una las caracter´ısticas SURF. Requiere la matriz de centros para calcular la distancia a cada una de las palabras del vocabulario. Como resultado tendremos un vector que asocia a cada caracter´ıstica su palabra. FuncionComparaci´on: a partir de la matriz Inverted File Index y los votos a cada una de las palabras del vocabulario de las caracter´ısticas de la imagen del usuario, esta funci´on nos devuelve las im´agenes m´as similares de la base de datos. 4.1.3. M´odulo de Realidad Aumentada En este m´odulo aparecen las funciones encargadas de realizar el algoritmo que permite a˜nadir informaci´on adicional a la imagen tomada por el usuario. Las funciones que se pueden encontrar en este m´odulo son las encargadas de realizar el algoritmo explicado en la Figura 3.3. Estas sin 29 4.2. DISE ˜ NO DE LA APLICACI ´ ON CAP´ ITULO 4. APLICACI ´ ON DESARROLLADA mucho detalle son, una funci´on para la extracci´on SURF en una determinada regi´on, funci´on para el c´alculo de la matriz de homograf´ıa H, funci´on para el c´alculo de posicionamiento de la regi´on en la imagen del usuario y funci´on para el c´alculo de proyecci´on de la imagen interior del edificio. 4.2. Dise˜no de la Aplicaci´on A continuaci´on se va a explicar detalladamente las pantallas a trav´es de las cuales el usuario navegar´a cuando ejecute CityCam. En la Figura 4.2 podemos ver un diagrama de navegaci´on general. Figura 4.2: Diagrama de navegaci´on de la aplicaci´on CityCam. 4.2.1. Pantalla Principal Al iniciar la aplicaci´on el usuario desde su smartphone, la primera pantalla con la que se encontrar´a es la que se muestra en la Figura 4.3. En ella tendr´ab´asicamente cuatro opciones. 1) Bot´on C´amara La principal funci´on de esta aplicaci´on es la que se ejecuta si pulsa el bot´on superior izquierdo (Figura 4.2 transici´on 1)), cuando es pulsado se inicia la c´amara de nuestro smartphone permitiendo capturar una imagen. 30 CAP´ ITULO 4. APLICACI ´ ON DESARROLLADA 4.2. DISE ˜ NO DE LA APLICACI ´ ON Figura 4.3: Pantalla Inicio CityCam. En la imagen izquierda sin pulsar el bot´on Men´uy en la imagen derecha pulsado este, pudiendo acceder a im´agenes de galer´ıa o salir de la aplicaci´on 2) Bot´on Mapa La segunda opci´on es el bot´on superior derecho, al hacer click en ´este (Figura 4.2 transici´on 2)), se abrir´a Google Maps mostrando todos los edificios registrados en nuestra base de datos (Figura 4.4). Figura 4.4: Pantalla Mapa. En esta pantalla se muestra el mapa de Google Maps con los diferentes edificios de nuestra base de datos situados sobre el mapa. 3) Bot´on Configuraci´on Con la pulsaci´on del bot´on inferior derecho (Figura 4.2 transici´on 3)), accederemos a una pantalla donde se podr´a configurar que la aplicaci´on acceda a redes Wi-Fi y al GPS, para que la localizaci´on sea m´as precisa y por tanto los resultados mostrados al usuario mejores. 4) Bot´on Galer´ıa (Men´u) Pulsando el bot´on Men´ude nuestro dispositivo, accederemos a un submen´u, donde aparecen las opciones Galer´ıa ySalir. Presionado Galer´ıa, accedemos a nuestra galer´ıa de im´agenes 31 4.2. DISE ˜ NO DE LA APLICACI ´ ON CAP´ ITULO 4. APLICACI ´ ON DESARROLLADA (Figura 4.5), permitiendo la realizaci´on de pruebas de una forma m´as sencilla y r´apida. Figura 4.5: Galer´ıa de im´agenes. En esta pantalla aparecen todos los directorios con im´agenes de nuestro dispositivo para que se seleccione una para su an´alisis. 4.2.2. Pantalla An´alisis de Imagen Una vez tomada una imagen o seleccionada de galer´ıa(Figura 4.2 transici´on 6) ´o 7)), se pasa al an´alisis de la informaci´on de esta para mostrar al usuario aquellas m´as similares. Este proceso lleva asociado un tiempo (4-8 seg.) donde se visualizar´a la pantalla mostrada en la Figura 4.6. Figura 4.6: Pantalla de An´alisis de Imagen. Pantalla en la cual el usuario deber´a esperar a que se produzca el an´alisis de la imagen. 4.2.3. Pantalla Resultados Cuando el an´alisis haya acabado(Figura 4.2 transici´on 8)), ya se podr´a mostrar al usuario las im´agenes de la base de datos con mayor similitud, mostr´andolas como aparece en la Figura 4.7. 32 CAP´ ITULO 4. APLICACI ´ ON DESARROLLADA 4.2. DISE ˜ NO DE LA APLICACI ´ ON Figura 4.7: Pantalla de resultados tras el an´alisis. En esta pantalla se muestran las im´agenes de la base de datos que tras el an´alisis han resultados m´as similares. 4.2.4. Pantalla informaci´on del Edificio Una vez el usuario selecciona uno de los resultados mostrados (Figura 4.2 transici´on 9)), se muestra la imagen tomada por este con informaci´on adicional, as´ı como un link para que tenga m´as informaci´on de forma directa 4.8. Si este link es pulsado, se abrir´a nuestro navegador web por defecto, redirigi´endonos a una web con m´as informaci´on sobre el edificio. Figura 4.8: Pantalla con informaci´on del edificio. En la imagen izquierda aparece la imagen tomada por el usuario con informaci´on a cerca del edificio. Si es pulsado el link +info se abrir´a el navegador apareciendo m´as informaci´on del edificio, imagen derecha. 4.2.5. Pantalla Realidad Aumentada En algunos ejemplos, en la ´ultima pantalla (Figura 4.8) aparecer´a el bot´on Realidad Aumentada que permite al usuario mostrar la imagen con informaci´on virtual sobre su imagen, en este caso ser´a una imagen del interior del edificio. 33