Repositorio Institucional de Documentos

Proyecto Fin de Carrera Ingeniería Industrial Sistema de Realidad Aumentada en Entornos Reales Adversos Autor Miguel Ángel Montañés Laborda Director Mario F. Rodríguez Martínez Ponente José Elías Herrero Jaraba Escuela de Ingeniería y Arquitectura de Zaragoza 2014 Sistema de Realidad Aumentada en Entornos Reales Adversos RESUMEN En este trabajo proponemos una aplicación para plataformas móviles capaz de realizar la proyección de una imagen virtual sobre un entorno real de forma consistente a lo largo de un periodo de tiempo más o menos prolongado. Se realiza una detección del entorno para seleccionar la superficie de proyección de la imagen y, a lo largo de la duración de toda la observación, se mantiene la proyección de forma estable sobre ella. En el escenario seleccionado confluyen diferentes elementos adversos que dificultan las tareas de detección y seguimiento, como son cambios de iluminación, escala, giros y movimientos de la cámara y oclusiones por lo que hemos diseñado nuestro sistema para que sea capaz de gestionar todos estos distractores propios de ciertos escenarios adversos. Adicionalmente, se propone un sistema de reinicialización para aquellos casos en los que los distractores hagan imposible el seguimiento de la superficie y una proyección consistente. Los objetivos de este proyecto son el estudio de las técnicas existentes para realizar una aplicación de realidad aumentada como esta, la implementación de la propia aplicación integrando las técnicas que mejores resultados aportan al procesamiento del escenario y la aplicación de métodos de corrección que hagan posible que el sistema sea estable frente a los principales distractores que aparecen en los entornos reales. La aplicación final requiere el funcionamiento sobre un dispositivo móvil por lo que los requisitos de tiempo real han sido claves en la selección de los métodos utilizados. Adicionalmente, se han aplicado técnicas para mejorar la sensación visual permitiendo la detección de objetos en primeros planos y su correcta visualización por delante de la imagen virtual. La evaluación del sistema se ha realizado sobre diferentes videos englobando todos los distractores mencionados comparando los resultados con varios métodos y comprobando de forma cualitativa las mejoras obtenidas por el sistema propuesto. Los resultados finales concluyen que el sistema es capaz de obtener un procesado suficiente como para disfrutar de una sensación de tiempo real, mejorando al mismo tiempo la fiabilidad del sistema frente a oclusiones leves, siendo capaz, al mismo tiempo, de detectar las oclusiones más severas, permitiendo iniciar un proceso de reinicialización en estos casos. INDICE RESUMEN ................................................................................................................... 2 INDICE ......................................................................................................................... 3 Agradecimientos ........................................................................................................... 6 Capítulo 1: Introducción ............................................................................................... 1 Introducción ............................................................................................................ 1 Contexto .................................................................................................................. 5 Estado del arte ......................................................................................................... 6 Objetivos ............................................................................................................... 10 Capítulo 2: Estudio del sistema propuesto ................................................................. 12 2.1. Infraestructura ................................................................................................ 12 2.2. Funcionamiento del Sistema .......................................................................... 12 Tareas previas ................................................................................................... 14 Registro con primer fotograma ......................................................................... 16 Extraer superficie de proyección ...................................................................... 20 Tracking de la superficie .................................................................................. 22 Realimentación del tracking y corrección de errores ....................................... 24 Capítulo 3: Comparativa de métodos ......................................................................... 28 Etapa de Registro con el primer fotograma........................................................... 28 a. Características SIFT. ............................................................................... 28 b. Características SURF. ............................................................................. 29 c. Características FAST. ............................................................................. 30 Etapa de Extracción de la superficie de proyección. ............................................. 32 Etapa de Tracking. ................................................................................................ 35 Métodos de tracking ......................................................................................... 36 Métodos de emparejamiento de características ................................................ 41 Etapa de Corrección de errores. ............................................................................ 43 Capítulo 4: Conclusiones y resultados ....................................................................... 47 Capítulo 5: Trabajo futuro .......................................................................................... 51 Bibliografía ................................................................................................................ 53 Tabla de Figuras ......................................................................................................... 55 Tabla de Gráficas ....................................................................................................... 57 Anexos .......................................................................................................................... i Anexo 1: Tipos de Características ................................................................................. i 1. Características SIFT. .................................................................................. i 2. Características SURF. ............................................................................... v 3. Características FAST. .............................................................................. vi 4. Características oFAST. ........................................................................... vii 5. Características “Good Features to Track”. ............................................. viii Anexo 2: Descriptores y Emparejamiento o ‘matching’ de características. .................. i Descriptores ......................................................................................................... i Descriptores SIFT. .......................................................................................... i Descriptores SURF. ....................................................................................... ii Descriptores BRIEF. ..................................................................................... iv Descriptores rBRIEF. .................................................................................... v Matching ............................................................................................................ vi Anexo 3: Métodos de Tracking ..................................................................................... i Dificultades del seguimiento ............................................................................... i Métodos de tracking ........................................................................................... ii 1. Flujo óptico disperso y tracking KLT. ................................................. ii 2. Algoritmo de tracking de Kalman. ..................................................... vii 3. Algoritmo de tracking ORB. ............................................................. viii 4. Algoritmo de tracking FFME. ........................................................... viii 5. Algoritmos propios basados en emparejamiento. ............................... xi Anexo 4: Base de datos, Métodos y Resultados ............................................................ i Base de Datos: Características y tipos de distractores. ............................................ i Métodos evaluados. ................................................................................................ iii Tipos de resultados. ................................................................................................ iv Agradecimientos A mis directores y guías Mario, Elías y Carlos por su paciencia y empuje para concluir este trabajo a tiempo y con éxito. A todas aquellas personas que me han apoyado durante este largo tiempo, sobre todo a aquellos a quienes impulsaba la fe. Pero muy especialmente a quienes ya no están conmigo y que tanto me acompañaron, Nati, Casio, Carmen y Ángel. Y por último, a mi apoyo diario, Teresa. Capítulo 1: Introducción Estado del arte Para abordar un proyecto de cualquier índole, es necesario disponer de una visión de los avances realizados en el campo en que se enmarca dicho proyecto. Para este trabajo en concreto, se requiere el conocimiento de técnicas de Visión por Computador que permitan realizar las siguientes tareas: extracción de puntos característicos, emparejamiento de características, seguimiento o tracking de puntos, etc. • Extracción de características específicas de una imagen. Se busca un tipo de características que permita identificar puntos de la imagen de una forma precisa y lo más unívoca posible. El proceso de extracción de características consta de dos fases: o La primera de ellas consiste en una extracción de las coordenadas de los puntos que mejor cumplen con las características que impone el método utilizado. o En la segunda fase, por cada uno de los puntos obtenidos, se extrae un descriptor del mismo. Un descriptor es una representación del punto basada en las características de la imagen en el entorno de dicho punto característico y que sirve para modelarlo e identificarlo de la forma más única posible pues será a través de este descriptor que se realizarán las tareas de emparejamiento posteriores. Existen diversos tipos de características (o ‘features’) descritas en la bibliografía con distintas virtudes y defectos. a. Características SIFT (Scale-Invariant Feature Transform) [1] [2]. Son características muy robustas debido a que los descriptores en las coordenadas adecuadas son invariantes a escala y a rotación. Como contrapartida, su extracción de coordenadas es muy costosa computacionalmente. b. Características SURF (Speeded Up Robust Features) [3] [4]. También son invariantes a escala y rotación e inspiradas en las anteriores SIFT. La extracción de coordenadas características es más rápida que en SIFT, basadas en sumas de 2D Haar wavelet [5] [6] haciendo uso eficiente de las imágenes integrales. Son algo menos robustas que las SIFT frente a 6 Sistema de Realidad Aumentada en Entornos Reales Adversos escalado debido a que sacrifican algunas de las operaciones dedicadas a este aspecto en pro de ganar en velocidad de procesado. c. Características FAST (Features from Accelerated Segment Test) [7] [8] es un método de extracción de esquinas (ver Anexo 1) que puede ser usado para detección de coordenadas característicos y tracking de objetos. La ventaja más destacada es su eficiencia computacional. Se pueden utilizar varios tipos de descriptores como los obtenidos en SIFT o SURF. También se emplean descriptores diseñados para este tipo de características como el BRIEF (Binary Robust Independent Elementary Features) [9]. Se trata de un descriptor que, mediante lo que denomina ‘test binarios’, obtiene un vector {0,1}𝑁𝑁 (al que llama ‘bitstring’) como descriptor eficiente de puntos característicos. Son descriptores robustos a cambios de iluminación, distorsión de la perspectiva y desenfoque, pero muy sensibles a rotación. Como medida de similaridad puede utilizarse la distancia de Hamming cuyo cómputo es más eficiente que la norma L2 utilizada habitualmente. Su descripción detallada puede encontrarse en el Anexo 2. d. Características oFAST (Oriented-FAST) [10]. Se trata de un algoritmo para extraer coordenadas características de tipo FAST aprovechando así su eficiencia computacional y que, además, contengan información de la orientación. El descriptor diseñado para este tipo de características es el rBRIEF (Rotated BRIEF) [10]. Los descriptores rBRIEF son una modificación de los BRIEF que les permiten ser invariantes a las rotaciones en el plano. Son un tipo de descriptores que permiten utilizar la información de rotación que incorporan los puntos oFAST para construir ‘bitstring’ de palabras binarias invariante a rotación. Para facilitarles mayor fiabilidad frente a la perdida de varianza y reducir la correlación entre los ‘test binarios’, se incorpora un método de aprendizaje para la elección de un buen subconjunto de los ‘test binarios’. e. Características “Good Features to Track” [11]. En realidad se trata de un método de extracción de coordenadas mediante detección de esquinas robusto y medición de la similaridad entre fotogramas que permita un mejor seguimiento. El método utiliza dos modelos de 7 Capítulo 1: Introducción movimiento en la imagen. El primero de ellos propone seleccionar puntos con un alto contenido en ‘textura’ y por lo tanto inmunes al ruido y al problema de la apertura (ver la descripción de estas características en el Anexo 1 para más información). Estos puntos esencialmente son puntos ‘esquina’. El segundo de ellos propone un emparejamiento de características entre fotogramas mediante una medida de “similaridad” basada en transformaciones afines que contemplen deformaciones y no solamente desplazamientos. El artículo propone descriptores propios aunque se pueden utilizar otros como los ya descritos. • Emparejamiento robusto de características. Para realizar las correspondencias de características entre dos imágenes es necesario unos descriptores lo más unívocos posible. Determinados los descriptores, las características detectadas en una imagen pueden ser emparejadas con ellas mismas si aparecen en otra imagen distinta. Al proceso de reconocer una misma característica en dos imágenes diferentes es lo que se denomina como emparejamiento o ‘‘matching’’. Es importante entonces encontrar descriptores que cambien lo menos posible al variar la perspectiva, la escala, la iluminación, etc… para una misma característica, de tal forma que si el descriptor cumple estos requisitos sería fácil detectar esta característica en dos imágenes distintas cualesquiera. Existen distintos métodos para el emparejamiento de descriptores siendo los siguientes algunos de los más habituales: o Norma L2 o Distancia de Hamming. o Sum of Square Difference (SSD). o Otros. Para obtener un emparejamiento o ‘matching’ robusto se utilizan técnicas de refinado del emparejamiento. El más conocido y quizá el más confiable es el método RANSAC [12] [13]. Este método de ajuste de características a geometrías conocidas es especialmente útil en el filtrado de puntos para el cálculo de homografías entre planos [14]. Se puede consultar una explicación más exhaustiva en el Anexo 2. • Seguimiento (o “tracking”) de características. Una vez detectadas una serie de características en la imagen, puede realizarse un seguimiento de las mimas a 8 Sistema de Realidad Aumentada en Entornos Reales Adversos través de las imágenes consecutivas de un video o recibidas de dispositivos de streaming como cámaras o móviles. El proceso es conceptualmente distinto al de emparejamiento de características ya que en este proceso se dispone de información de unas características ya encontradas en un fotograma previo por lo que se puede asumir algunas restricciones. Al tratarse de imágenes consecutivas, es de esperar que las condiciones de iluminación y escala sean similares, así como que el desplazamiento de las características de una a otra imagen no sean excesivo y/o siga algún patrón. Muchos de los algoritmos de ‘matching’ en realidad se basan en emparejamiento de características aprovechando estas restricciones. o Algoritmo de tracking KLT de flujo óptico disperso [15] [16]: Algoritmo de seguimiento basado de Lucas-Kanade calculando el flujo óptico de forma piramidal. Es un método muy rápido y que obtiene muy buenos resultados en ausencia de oclusiones. o Algoritmo de tracking de Kalman [17] [18]. El filtro de Kalman es un algoritmo desarrollado por Rudolf E. Kalman en 1960 que sirve para identificar el estado oculto (no medible) de un sistema dinámico lineal, pero sirve además cuando el sistema está sometido a ruido blanco aditivo. La diferencia del filtro de Kalman sobre otros métodos radica en que Kalman es capaz de escoger la ganancia K de realimentación del error de forma óptima cuando se conocen las varianzas de los ruidos que afectan al sistema. En este proyecto se utiliza la implementación piramidal detallada en [18]. o Algoritmo de tracking FFME (Fast Feature-based Motion Estimation) [19]. Es un método de estimación del movimiento robusto al ruido y al problema de la apertura. Esto se logra imponiendo restricciones relacionadas con la magnitud del gradiente, el nivel de ruido adaptativo, la similitud o no con un punto esquina, y la diferenciación apreciable frente a puntos vecinos. Para la caracterización de cada punto singular se utiliza un descriptor complejo, que presenta una gran robustez a los cambios de iluminación y las pequeñas variaciones en el punto de vista de la cámara. La correspondencia entre los puntos singulares de imágenes consecutivas se realiza mediante la minimización de la distancia Euclídea como medida de similaridad con el descriptor del 9 Capítulo 1: Introducción punto en el fotograma anterior. El conjunto de correspondencias produce un campo vectorial disperso de movimiento que describe con precisión el movimiento de la imagen. Objetivos Los objetivos que se plantean en este proyecto son los siguientes: 1. Inicialización robusta. La secuencia de imágenes que se analizan, bien de un video o de un ‘stream’ de imágenes, no tiene por qué comenzar con la superficie de proyección bien encuadrada. Es necesario que el sistema disponga de una forma de detección de este hecho y sea capaz de permanecer a la espera, o incluso de guiar al usuario hasta que la superficie donde se quiere proyectar aparezca en el campo de visión. 2. Tracking consistente. Una vez localizada la superficie de proyección, se debe proyectar la imagen virtual de manera consistente durante todo el tiempo que dure la secuencia de imágenes, es decir, debe observarse estable, sin vibraciones visualmente molestas y en la posición ocupada por la superficie real. 3. Robustez a cambios de iluminación, rotaciones, cambios de escala. El sistema debe superar los distractores habituales que afectan a un sistema basado en visión por computador. Durante la secuencia de imágenes pueden producirse pequeños cambios de iluminación, cambios de escala debido a que el observador puede acercarse o alejarse de la superficie de proyección o rotaciones y desplazamientos propios de un sistema móvil producidos por el propio movimiento del usuario. 4. Gestión de oclusiones. Solventar las leves y reiniciar en las graves. El principal problema aún sin resolver de un sistema de visión como el propuesto, es el manejo de las oclusiones que afectan al objeto en estudio. En este proyecto se han analizado secuencias de oclusiones leves y severas y se ha preparado el sistema para que supere las primeras y detecte las segundas. En caso de una oclusión grave, el sistema queda a la espera de que desaparezca para retomar el seguimiento y la proyección del contenido. 5. Detección de profundidad: Para que la proyección del contenido tenga consistencia visual para el observador, debe realizarse una detección de los objetos que se encuentran en primer plano por delante de la superficie de 10 Sistema de Realidad Aumentada en Entornos Reales Adversos proyección. Esta detección nos permite superponer a la imagen proyectada los objetos de primer plano, dando una sensación visual más real y con sensación de profundidad. 6. Procesamiento en tiempo real. El sistema debe funcionar a una tasa de procesamiento que ofrezca al usuario una sensación de continuidad. Esta restricción obliga a ciertas elecciones que sacrifican cierto grado de fiabilidad en favor de la velocidad de procesado. 11 Capítulo 2: Estudio del sistema propuesto Como se ha descrito en la Introducción, el sistema objetivo de este trabajo realiza la proyección estable de una imagen sobre un entorno real fusionando ambos contenidos para dar la impresión al observador de que se trata de una imagen real. Los requisitos y objetivos se han descrito en el apartado de Objetivos y aquí se van a detallar la infraestructura utilizada tanto software como hardware y el funcionamiento general de todas las partes del sistema. 2.1. Infraestructura A pesar de que el objetivo final del sistema es su funcionamiento en plataformas móviles, para el desarrollo, pruebas y comparación de resultados de diversas alternativas se ha utilizado un ordenador tipo PC. Las características concretas de la plataforma de desarrollo son: 1. Ordenador Intel Core2 Duo E7400 de 2.8GHz y 4 GB de memoria RAM. 2. Sistema operativo Windows 7 de 64 bits. 3. IDE de desarrollo Eclipse IDE for C/C++ Developers Version: Juno Service Release 2. CDT para C/C++ 8.1.2. 4. Compilador MinGW32-g++ 4.8.1. 5. Biblioteca OpenCV de procesamiento de imagen versión 2.4.6 [20] [21]. 6. Videos grabados con varios dispositivos móviles de resoluciones de 1280x720, 640x480 y 1920x1080. 2.2. Funcionamiento del Sistema El funcionamiento del sistema desarrollado sigue un esquema de control en bucle cerrado que permite una realimentación de los resultados obtenidos. Este bucle de realimentación permite realizar correcciones sobre el funcionamiento y es el principal causante de la estabilidad del proceso frente a las oclusiones (ver Figura 6). 12 Sistema de Realidad Aumentada en Entornos Reales Adversos Figura 6: Esquema de control en bucle cerrado En este esquema se observa que a partir de la ‘Imagen a Proyectar’ (‘IP’), y la ‘Imagen de Referencia’ (‘IR’) etiquetada se consigue establecer una posición del observador en el entorno, lo que se traduce como una forma de relacionar ambas imágenes. Posteriormente, mediante un primer fotograma limpio (‘I0’) de la secuencia se consigue lo propio con la posición del nuevo observador. Con ambas imágenes, la de referencia (‘IR’) y la del fotograma (‘I0’), se extraen características y descriptores que se emparejan y se envían al módulo de tracking. Este proceso, tomando la secuencia de fotogramas del video y los descriptores, realiza un seguimiento de las posiciones de las características. Dado que en el video aparecen descriptores que alteran el funcionamiento normal del tracking, se hace necesario un bucle de realimentación para corregir las posibles desviaciones de las posiciones. El resultado es la imagen proyectada sobre la superficie seleccionada. Una visión más detallada del sistema se puede observar en la Figura 7. 13 Capítulo 2: Estudio del sistema propuesto Figura 7: Esquema detallado del sistema Tareas previas Este bloque del sistema consta de una serie de tareas que pueden y deben realizarse con anterioridad a la puesta en marcha del sistema. Son tareas principalmente manuales que permiten calibrar y agilizar el procesamiento posterior. Para realizar una proyección de una imagen sobre una superficie, es necesario obtener los siguientes datos previos: 1. Obtención de la ‘Imagen a Proyectar’ (‘IP’). Como imagen ejemplo de realidad aumentada se ha elegido el cuadro de la ‘Maja vestida’ de Goya pero puede ser cualquiera. Además de la propia imagen es necesario disponer de las posiciones de las 4 esquinas del cuadro. Es aconsejable que la imagen se encuentre bien encuadrada y sin giros ya que, de esta forma, las cuatro esquinas se corresponden con el propio tamaño de la imagen, ancho y alto. 14 Sistema de Realidad Aumentada en Entornos Reales Adversos Figura 11: Doble correspondencia homográfica, relación entre la Imagen a Proyectar, IP y el primer fotograma de la secuencia, I0 Como se observa en la Figura 11, esta proyección no muestra ningún espacio ni hueco sin rellenar tal como cabría esperar si se proyectase la ‘IP’ directamente sobre el fotograma, dado que la transformación en la perspectiva debería dejar puntos en la superficie para los que no hay una correspondencia directa. Para asegurar que no ocurre esto, el cálculo de la ‘IP’ sobre el fotograma se hace en el sentido inverso, es decir: • Se toman todos los puntos del fotograma ‘IT’, ‘puntos_t’. • Se les aplica la homografía inversa para situarlos en el sistema de referencia de la ‘IP’, ‘puntos_t_inv’. • Se toman todos los ‘puntos_t_inv’ que caen sobre la ‘IP’. • Se toma el valor del píxel (en sus tres canales) de la ‘IP’ y se aplica al ‘puntos_t’ correspondiente. • En caso de que uno de los ‘puntos_t_inv’ no tenga una correspondencia exacta con un píxel de la ‘IP’, se interpola linealmente entre sus píxeles vecinos (siendo 𝑤𝑤𝑖𝑖,𝑗𝑗 los pesos correspondientes a cada uno de los 4 puntos vecinos en función de la distancia al punto pinv). ∀𝑝𝑝(𝑥𝑥,𝑦𝑦)∈𝐼𝐼𝑇𝑇,→𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖(𝑥𝑥,𝑦𝑦)=𝐻𝐻𝑃𝑃_𝑇𝑇𝑖𝑖𝑖𝑖𝑖𝑖∗𝑝𝑝(𝑥𝑥,𝑦𝑦) 𝑆𝑆𝑆𝑆𝑆𝑆 𝑙𝑙𝑆𝑆 𝑖𝑖𝑖𝑖𝑖𝑖𝑆𝑆𝑖𝑖𝑝𝑝𝑖𝑖𝑙𝑙𝑆𝑆𝑖𝑖𝑖𝑖ó𝑖𝑖 𝑙𝑙𝑖𝑖𝑖𝑖𝑆𝑆𝑆𝑆𝑙𝑙,𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖 ∗(𝑥𝑥,𝑦𝑦)= � 𝑤𝑤𝑖𝑖,𝑗𝑗∗𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖�𝑥𝑥𝑖𝑖,𝑦𝑦𝑗𝑗� 𝑖𝑖=4,𝑗𝑗=4 𝑖𝑖=1,𝑗𝑗=1 𝑝𝑝(𝑥𝑥,𝑦𝑦)=�𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖 ∗(𝑥𝑥,𝑦𝑦) 𝑆𝑆𝑖𝑖 𝐼𝐼𝑃𝑃: 𝑆𝑆𝑖𝑖 𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖(𝑥𝑥,𝑦𝑦)∈𝐼𝐼𝑃𝑃 𝑝𝑝(𝑥𝑥,𝑦𝑦) 𝑆𝑆𝑖𝑖 𝐼𝐼𝑇𝑇: 𝑆𝑆𝑖𝑖 𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖(𝑥𝑥,𝑦𝑦)∉𝐼𝐼𝑃𝑃 𝐻𝐻𝑅𝑅_0 𝐻𝐻𝑃𝑃_0 𝐻𝐻𝑃𝑃_𝑅𝑅 21 Capítulo 2: Estudio del sistema propuesto Computacionalmente, este proceso de emparejamiento es el más costoso. Se han probado diversos métodos con distintos resultados y costes computacionales. La descripción completa de todos ellos se detalla en el Capítulo 3 y en el apartado Coste computacional de los diferentes métodos de tracking del Anexo 3. Tracking de la superficie Realizado el registro con el fotograma inicial de la secuencia, el sistema se centra en el seguimiento de los ‘puntos_ini’ y sus descriptores, ‘descriptores_ini’ obtenidos durante la etapa anterior de un fotograma en el instante t al siguiente en el instante t + 1. Si el sistema es capaz de realizar el seguimiento de estos puntos de un fotograma al siguiente de una forma consistente, el problema se resuelve. El emparejamiento utilizado en esta etapa es el KLT, Kanade-Lucas Tracker [15]. En concreto, el KL basado en flujo óptico de forma piramidal [16] explicado en el apartado Métodos de tracking del Anexo 3. Es un método que ofrece un muy buen compromiso entre velocidad de procesamiento y fiabilidad de resultados en ausencia de oclusiones. Este proceso permite extraer una relación homográfica, ‘HR_T’, entre la ‘IR’ y el fotograma actual ‘IT’ que, compuesta con la inicial ‘HP_R’, nos relaciona la ‘IP’ con la ‘IT’ como se muestra en la Figura 12: 𝐻𝐻𝑃𝑃_𝑇𝑇=𝐻𝐻𝑅𝑅_𝑇𝑇∗𝐻𝐻𝑃𝑃_𝑅𝑅 El cálculo de esta nueva relación homográfica, ‘HR_T’, también es sometido al proceso de filtrado mediante RANSAC lo cual permite filtrar puntos espurios que el tracking KLT no ha sido capaz de detectar. 22 Sistema de Realidad Aumentada en Entornos Reales Adversos Figura 12: Proyección de la imagen sobre cualquier fotograma de la secuencia por medio del tracking de puntos Este sistema hasta este momento en bucle abierto, cumple muy bien con muchos de los objetivos planteados en todos los casos chequeados si nos encontramos en una situación ausente de oclusiones: 1. Inicialización robusta. El registro inicial mediante emparejamiento de puntos SIFT permite una inicialización muy robusta (ver Figura 2). 2. Tracking consistente. El tracking KLT en esta implementación piramidal es resistente a cambios de escala y rotaciones no demasiado bruscas (ver Figura 3). 3. Robusto a cambios de iluminación, rotaciones, cambios de escala. Se ha comprobado que si las variaciones de iluminación, rotaciones o cambios de escala (al variar la distancia a la superficie de proyección) no son excesivos, este sistema funciona de una forma bastante correcta (se detectan ciertas vibraciones en algunos casos que dan una impresión visual molesta) (ver Figura 3 y Figura 13). 𝐻𝐻𝑅𝑅_𝑇𝑇 𝐻𝐻𝑃𝑃_𝑅𝑅 𝐻𝐻𝑃𝑃_𝑇𝑇 Imagen de Referencia Imagen a Proyectar Fotograma en instante t 23 Capítulo 2: Estudio del sistema propuesto Figura 13: Sistema de tracking KLT soporta giros no muy bruscos con cierta vibración 4. Gestión de oclusiones, solventar las leves y reiniciar en las graves. En las secuencias chequeadas en que la superficie de proyección es ocluida en parte o casi totalmente por algún objeto cercano a la cámara, el sistema en bucle abierto falla (ver Figura 14). Es para resolver este problema para el que es necesario plantear un lazo de realimentación que permita detectar y corregir las desviaciones observadas en el proceso de seguimiento. Figura 14: Sistema de tracking KLT falla en situaciones con oclusiones. Realimentación del tracking y corrección de errores Como se ha comentado en el apartado anterior, es necesario implementar un sistema de realimentación que permita al sistema de tracking detectar y corregir situaciones en las que, principalmente por alguna oclusión, los puntos característicos no están siendo emparejados correctamente entre dos fotogramas consecutivos: 24 Sistema de Realidad Aumentada en Entornos Reales Adversos Entradas: 1. Coordenadas de los ‘puntos_next’. Como ya se ha comentado, hemos llamado ‘puntos_ini’ a las posiciones de los puntos del fotograma en el instante t. Estos puntos se toman como la entrada del proceso del tracking KLT. A las posiciones correspondientes a los ‘puntos_ini’ en el instante t + 1 que el proceso de tracking devuelve como salida, las llamaremos ‘puntos_next’. 2. Coordenadas de los ‘puntos_ref’. Tal como se describe en el apartado de la descripción del proceso en la etapa de Registro con primer fotograma, los ‘puntos_ref’ son las coordenadas de los puntos SIFT extraídos y emparejados en la ‘IR’. 3. Homografía que relaciona la ‘IR’ con ‘IT’. Esta homografía sería la compuesta por: 𝐻𝐻𝑅𝑅_𝑇𝑇=𝐻𝐻𝑅𝑅_𝑇𝑇(𝑖𝑖) Salidas: 1. Coordenadas de ‘puntos_next’ válidos. Son los ‘puntos_next’ que el filtrado que se describe en el apartado siguiente de Proceso extrae como puntos correctamente emparejados. Llamaremos ‘puntos_next_ok’ a estos puntos. 2. Coordenadas de ‘puntos_next’ no válidos. Son aquellos ‘puntos_next’ que el filtrado que se describe en el apartado siguiente de Proceso extrae como puntos incorrectamente emparejados. Llamaremos ‘puntos_next_ko’ a estos puntos. 3. Homografía que relaciona la ‘IR’ con la ‘IT’ corregida. Tomando como emparejamientos los ‘puntos_next_ok’ anteriores y los ‘puntos_ref’ correspondientes a estos puntos, se recalcula la ‘HR_T’. 𝐻𝐻𝑅𝑅_𝑇𝑇𝑂𝑂𝑂𝑂=𝑓𝑓𝑖𝑖𝑖𝑖𝑓𝑓𝐻𝐻𝑖𝑖𝑓𝑓𝑖𝑖𝑓𝑓𝑖𝑖𝑆𝑆𝑝𝑝ℎ𝑦𝑦(𝑝𝑝𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖𝑝𝑝_𝑖𝑖𝑆𝑆𝑥𝑥𝑖𝑖_𝑖𝑖𝑜𝑜,𝑝𝑝𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖𝑝𝑝_𝑖𝑖𝑆𝑆𝑓𝑓) 4. Coordenadas de ‘puntos_next’ corregidas. El resultado final del proceso devuelve un conjunto de ‘puntos_next’ modificado: a. Los ‘puntos_next’ correspondientes a los ‘puntos_next_ok’ se mantienen sin ninguna variación puesto que son aquellos puntos no afectados por distractores y que el KLT ha seguido correctamente. b. Los ‘puntos_next’ correspondientes a los ‘puntos_next_ko’ son corregidos de la siguiente forma: • Se toman los ‘puntos_ref’ que corresponden a los ‘puntos_next_ko’. 25 Capítulo 2: Estudio del sistema propuesto • Se calculan las coordenadas de los ‘puntos_ref’ en el fotograma actual aplicándoles la homografía corregida con los ‘puntos_next_ok’: 𝑝𝑝𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖𝑝𝑝_𝑖𝑖𝑆𝑆𝑥𝑥𝑖𝑖_𝑜𝑜𝑖𝑖_𝑖𝑖𝑖𝑖_𝑖𝑖1=𝐻𝐻𝑅𝑅_𝑇𝑇𝑂𝑂𝑂𝑂 ∗ 𝑝𝑝𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖𝑝𝑝_𝑖𝑖𝑆𝑆𝑓𝑓 Es decir, el resultado del filtrado son los nuevos puntos en coordenadas del fotograma actual de los puntos que el KLT ha seguido correctamente y la proyección de los puntos en la ‘IR’ sobre el fotograma actual de aquellos puntos erróneos. Proceso: 1. Convertir las coordenadas de los ‘puntos_next’ a la ‘IR’. Dado que el tracking KLT devuelve un emparejamiento entre los ‘puntos_ini’ (puntos en el fotograma anterior) y los ‘puntos_next’ (en el fotograma actual), se puede calcular una homografía entre ‘IT’ y la ‘IR’: 𝐻𝐻𝑅𝑅_𝑇𝑇=𝑓𝑓𝑖𝑖𝑖𝑖𝑓𝑓𝐻𝐻𝑖𝑖𝑓𝑓𝑖𝑖𝑓𝑓𝑖𝑖𝑆𝑆𝑝𝑝ℎ𝑦𝑦(𝑝𝑝𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖𝑝𝑝_𝑖𝑖𝑆𝑆𝑥𝑥𝑖𝑖,𝑝𝑝𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖𝑝𝑝_𝑖𝑖𝑆𝑆𝑓𝑓) Utilizando la inversa de dicha transformación se pueden proyectar los ‘puntos_next’ sobre la ‘IR’. A estos puntos los llamaremos ‘puntos_next_inv’. 2. Calcular la media y varianza de los desplazamientos en X e Y entre los ‘puntos_next_inv’ y los ‘puntos_ref’. Dado que se dispone de los ‘puntos_ref’ y su emparejamiento con los ‘puntos_next’ (y por lo tanto con los ‘puntos_next_inv’) dado por el tracking KLT, se pueden calcular las distancias en coordenadas X e Y entre ellos. Con estos datos de calculan media y varianza de los desplazamientos. 3. Filtrado de los puntos cuya confianza sea menor al 95%. Con los datos de media y varianza (y desviación típica) obtenidas, se seleccionarán como puntos válidos aquellos cuyo desplazamiento en X e Y se encuentre dentro del margen de confianza del 95%, y como no válidos aquellos que se encuentren fuera de dicho margen. 4. Recalculo de la homografía 𝐻𝐻𝑅𝑅_𝑇𝑇𝑂𝑂𝑂𝑂. Dado que se han conseguido separar los ‘puntos_next_inv’ en dos grupos, válidos y no válidos, es posible refinar el cálculo de la ‘HR_T’ para obtener una mejor homografía 𝐻𝐻𝑅𝑅_𝑇𝑇𝑂𝑂𝑂𝑂: 𝐻𝐻𝑅𝑅_𝑇𝑇𝑂𝑂𝑂𝑂=𝑓𝑓𝑖𝑖𝑖𝑖𝑓𝑓𝐻𝐻𝑖𝑖𝑓𝑓𝑖𝑖𝑓𝑓𝑖𝑖𝑆𝑆𝑝𝑝ℎ𝑦𝑦(𝑝𝑝𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖𝑝𝑝_𝑖𝑖𝑆𝑆𝑥𝑥𝑖𝑖_𝑖𝑖𝑖𝑖𝑖𝑖_𝑖𝑖𝑆𝑆𝑙𝑙𝑖𝑖𝑓𝑓𝑖𝑖𝑝𝑝,𝑝𝑝𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖𝑝𝑝_𝑖𝑖𝑆𝑆𝑓𝑓) 26 Sistema de Realidad Aumentada en Entornos Reales Adversos 5. Proyección de los ‘puntos_ref’ correspondientes a los ‘puntos_next_ko’ al fotograma actual con la nueva 𝐻𝐻𝑅𝑅_𝑇𝑇𝑂𝑂𝑂𝑂: 𝑝𝑝𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖𝑝𝑝_𝑖𝑖𝑆𝑆𝑥𝑥𝑖𝑖_𝑜𝑜𝑖𝑖_𝑖𝑖𝑖𝑖_𝑖𝑖1=𝐻𝐻𝑅𝑅_𝑇𝑇𝑂𝑂𝑂𝑂 ∗ 𝑝𝑝𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖𝑝𝑝_𝑖𝑖𝑆𝑆𝑓𝑓 27 Capítulo 3: Comparativa de métodos En este capítulo se van a describir cada una de las alternativas posibles que se han probado en las diferentes etapas del sistema indicando en cada caso los pros y contras para finalmente argumentar la solución adoptada para cada proceso. Para obtener los datos indicados se utiliza uno cualquier de los videos de test. En este capítulo, no se pretende hacer notar tanto las cifras concretas como el argumentar la solución adoptada de forma cualitativa. • Etapa de Registro con el primer fotograma. Tal como se indica en el proceso de Registro con primer fotograma del apartado 2.2 del Capítulo 2, en esta etapa se extraen una serie de puntos característicos de la ‘IR’ y del primer fotograma de la secuencia y se emparejan. En el apartado de Estado del arte se describen diferentes tipos de características y descriptores que pueden ser utilizados en esta tarea. Para realizar el emparejamiento robusto de puntos, se ha utilizado el mismo método en todos los casos, es decir y de forma simplificada, un emparejamiento robusto mediante doble emparejamiento, test de simetría y filtrado por ratio y RANSAC. El procedimiento completo se detalla en el apartado de ‘matching’ del Anexo 2, obteniendo finalmente la matriz de homografía ‘HR_T’. Para realizar una comparación entre los distintos métodos de extracción de características, descriptores, sus emparejamientos y el tracking posterior, se selecciona uno cualquiera de los videos, sobre el cual se aplican todos los procesos que se detallan a continuación. Los resultados obtenidos con los diferentes tipos de características son los siguientes: a. Características SIFT. Estos puntos son los que tienen mejor comportamiento de entre los chequeados frente a cambios de iluminación y de escala. El tiempo consumido en la obtención de puntos SIFT es de unos 50-70 ms por cada 100 características. El emparejamiento obtenido utilizando estas características y sus descriptores es excelente. Con los umbrales por defecto este método extrae 1038 puntos en la ‘IR’ y 2432 en el primer 28 Sistema de Realidad Aumentada en Entornos Reales Adversos fotograma de la secuencia. El emparejamiento de estos puntos por fuerza bruta utilizando como medida de similaridad la norma L2, da como resultado 84 correspondencias bidireccionales, es decir, que, en estos casos, el emparejamiento de los puntos de la ‘IR’ y los del primer fotograma coincide con el emparejamiento de los puntos a la inversa (ver Figura 15). Figura 15: Puntos característicos de tipo SIFT b. Características SURF. Estos tipos de puntos no son tan robustos como los SIFT pero son más rápidos de extraer y procesar. El tiempo consumido en la obtención de estos puntos es de unos 40 ms por cada 100 características. El resultado del emparejamiento es bueno. El emparejamiento obtenido utilizando estas características y sus descriptores es excelente. Con los umbrales por defecto este método extrae 1005 puntos en la ‘IR’ y 1802 en el primer fotograma de la secuencia. El emparejamiento de estos puntos por fuerza bruta utilizando como medida de similaridad la norma L2, da como resultado 17 correspondencias bidireccionales, es decir, que, en estos casos, el mejor emparejamiento de los puntos de la ‘IR’ y los del primer fotograma coincide con el mejor emparejamiento de los puntos a la inversa (ver Figura 16). 29 Capítulo 3: Comparativa de métodos Figura 16: Puntos característicos de tipo SURF c. Características FAST. La extracción de estos puntos característicos es la más rápida de las tres. El tiempo que se emplea en la obtención de éstos es de unos 7 ms por cada 100 características. Este tipo de características produce un resultado muy malo cuando se intenta un emparejamiento por fuerza bruta en toda la imagen. Esto es debido a que no son robustos a cambios de escala e iluminación por lo que no son adecuados para la etapa de registro. Con los umbrales por defecto este método extrae 1184 puntos en la ‘IR’ y 3999 en el primer fotograma de la secuencia (en uno de los videos de test). Utilizando descriptor de tipo SURF, el emparejamiento de estos puntos por fuerza bruta utilizando como medida de similaridad la norma L2, da como resultado solo 3 correspondencias bidireccionales (ver Figura 17). Figura 17: Puntos característicos de tipo FAST El resultado de los emparejamientos obtenidos con los distintos tipos de puntos característicos anteriores se muestra en la Figura 18: 30 Sistema de Realidad Aumentada en Entornos Reales Adversos • En los fotogramas múltiplos de 10, se realiza el reemparejamiento. Para ello, se extraen características SIFT (en el ejemplo aunque también pueden ser FAST, SURF o de cualquier otro tipo) del fotograma actual y se realiza un emparejamiento robusto con los ‘puntos_ref’ obtenidos en la ‘IR’. • Se continúa el tracking con los nuevos puntos corregidos. El resultado se observa en la Figura 22. Figura 22: Algoritmo de Tracking KLT frente a oclusiones cuando se realiza un reemparejamiento cada 10 fotogramas mediante SIFT Esta alternativa da unos resultados excelentes frente a oclusiones de tipo leve, pero tiene la enorme desventaja de que el coste computacional del reemparejamiento en el fotograma correspondiente asciende a 1.2 segundos para imágenes de 640x480 y extracción de características de tipo SIFT. De hecho si se realiza un emparejamiento completo en todos los fotogramas el resultado es casi perfecto. El problema fundamental es el coste computacional tan elevado. Una mejora a esta última aproximación que permite reducir el tiempo de cómputo sustancialmente, consiste en restringir la búsqueda de las características SIFT a una zona en torno a la región de interés (donde se está realizando la proyección) en los fotogramas correspondientes al reemparejamiento. Para conseguir esto, se extrae una máscara de la región de proyección obtenida en el fotograma anterior y se amplía en todas las direcciones con un margen de seguridad que puede calcularse, por ejemplo, en función de alguna medida del desplazamiento de los puntos. En este 37 Capítulo 3: Comparativa de métodos ejemplo de la Figura 23 el tiempo de reemparejamiento desciende a unos 145 ms. Figura 23: Algoritmo de Tracking KLT frente a oclusiones cuando se realiza un reemparejamiento cada 10 fotogramas mediante SIFT y máscara de búsqueda en la ROI del fotograma anterior 2) Filtro de Kalman [17] [18]. Se ha valorado la utilización de un filtro de Kalman como método de tracking del sistema. Estudiando el proceso (ver el apartado Algoritmo de tracking de Kalman del Anexo 3), se puede observar que el filtro de Kalman necesita en cada uno de los instante, una serie de datos de medidas para poder alimentar el sistema y calcular su estado. Dado que no disponemos de medidas, se han intentado utilizar los resultados que proporciona un tracking KLT para simular dichas medidas. El resultado no solventa el problema de las oclusiones dado que las posiciones de los puntos característicos son arrastradas por los objetos que ocluyen la superficie de proyección de igual forma que ocurre al KLT por separado. El resultado es que, este arrastre modifica poco a poco la posición, lo cual se refleja en una modificación de la predicción de la dinámica lineal, y en definitiva, supone el arrastre de la posición estimada por el filtro de Kalman. Por lo tanto, la conclusión es que no es posible su utilización en este sistema. 38 Sistema de Realidad Aumentada en Entornos Reales Adversos 3) Tracking BRIEF [9]. Este algoritmo de tracking combina la extracción de características FAST con los descriptores BRIEF. Dado que los descriptores BRIEF son descriptores robustos a cambios de iluminación, distorsión de la perspectiva y desenfoque, pero muy sensibles a rotación el resultado no es demasiado bueno, como puede observarse en la Figura 24, por lo que se ha descartado su uso. Figura 24: Tracking mediante FAST y descriptores BRIEF. Resultado bastante inestable. 4) Tracking ORB [10]. Este algoritmo de tracking combina la extracción de características FAST con información de orientación (oFAST, descritas en el Anexo 1) con los descriptores rBRIEF descritos en el Anexo 2. El funcionamiento concreto se explica en el apartado Algoritmo de tracking ORB de los Métodos de tracking en el Anexo 3. Se han realizado pruebas con este método de seguimiento pero los resultados incluso sin oclusiones no mejoran los obtenidos por el KLT por lo que se ha desechado (ver Figura 25). 39 Capítulo 3: Comparativa de métodos Figura 25: Tracking ORB. Resultados inestables incluso sin oclusiones. 5) Tracking FFME [19]. Es un método de estimación del movimiento robusto al ruido y al problema de la apertura. El resultado de las correspondencias produce un campo vectorial disperso de movimiento que describe con precisión el movimiento de la imagen. No mejora los obtenidos por el KLT en los casos de oclusiones (ver Figura 26) y es significativamente más lento (en torno a 110 ms por fotograma) por lo que se ha desechado. 40 Sistema de Realidad Aumentada en Entornos Reales Adversos Figura 26: Tracking con método FFME. No supera oclusiones. Métodos de emparejamiento de características Se han probado diferentes métodos de tracking con la intención de combinar las ventajas de las diferentes características estudiadas. Los principales métodos probados son dos: a. Método de tracking p-SIFT. Los puntos SIFT y sus descriptores son las características que mejor resultado han dado en el emparejamiento en las escenas que se han evaluado. Sin embargo computacionalmente son demasiado pesados para su utilización en tiempo real. Se ha probado un sistema basado en el cálculo de unos puntos que llamamos p-SIFT pues están inspirados en ellos, pero eliminando parte de los cálculos más pesados. El cálculo exacto de estos puntos y sus descriptores se detalla en el Anexo 1. A estos p-SIFT se les aplica un método de predicción de medida y posterior búsqueda por ‘Hill climbing’ entre fotogramas de la secuencia. El sistema calcula los p-SIFT de la nueva imagen y predice la posición de los puntos en el nuevo fotograma en base al movimiento de 41 Capítulo 3: Comparativa de métodos los N fotogramas anteriores. En torno a los 3x3 vecinos del nuevo punto se busca del pixel de menor distancia al punto p-SIFT en el fotograma anterior. Si no coincide con el pixel predicho se vuelve a calcular la distancia de los 3x3 vecinos del nuevo pixel y así sucesivamente hasta encontrar el mínimo local o superar un máximo de iteraciones. El proceso es similar a ‘escalar una montaña’ (en este caso descender pues se busca el punto mínimo) de ahí su nombre. El resultado obtenido es bueno, soportando oclusiones leves (ver Figura 27). Se ha descartado frente al seleccionado debido a que es significativamente más lento, en torno a 170 ms por fotograma. Figura 27: Seguimiento mediante características p-SIFT. Soporta oclusiones leves. b. Método de tracking de puntos FAST y emparejamiento con medida de similaridad SSD. Este método pretende combinar la ligereza computacional del cálculo de puntos FAST con un sistema más robusto de emparejamiento de puntos que los descriptores basados en FAST. Para este caso se ha pensado utilizar un patch de 5x5 píxeles en torno al punto característico como descriptor. El emparejamiento se hace por fuerza bruta y la medida de dismilaridad utilizada es la SSD, mostrándose el cálculo completo del método en el Anexo 3. El resultado no ha sido demasiado bueno (ver Figura 28) y su implementación es bastante más lenta (1.3 segundos por fotograma) que la conseguida con el sistema propuesto en el Capítulo 2, por lo que se ha descartado. 42 Sistema de Realidad Aumentada en Entornos Reales Adversos Figura 28: Seguimiento mediante FAST y medida de similaridad SSD. Resultado no soporta oclusiones. • Etapa de Corrección de errores. Como se ha comentado en apartados anteriores, es necesario implementar un sistema de realimentación que permita al sistema de tracking detectar y corregir situaciones en las que existen oclusiones. Algunos de los métodos que se explican a continuación realizan un seguimiento entre fotogramas consecutivos al que denominaremos ‘Reproyección Indirecta’, a diferencia del método explicado en el apartado 2.2. Funcionamiento del Sistema del Capítulo 2 al que llamaremos ‘Reproyección Directa’. La ‘Reproyección Indirecta’ necesita de un paso intermedio para relacionar la ‘IR’ con el fotograma actual: Es necesario calcular una homografía que relaciona el fotograma en instantes anteriores con el fotograma actual. Esta homografía formalmente sería la compuesta por: 𝐻𝐻𝑅𝑅_𝑇𝑇+1=�𝐻𝐻𝑇𝑇_𝑇𝑇+1𝑖𝑖∗𝐻𝐻𝑅𝑅_0 𝑡𝑡+1 𝑖𝑖=0 43 Capítulo 3: Comparativa de métodos donde ∏𝐻𝐻𝑇𝑇_𝑇𝑇+1𝑖𝑖 𝑡𝑡+1 𝑖𝑖=0 son las homografías acumuladas desde el fotograma inicial hasta el actual. Se han probado varios métodos de corrección de errores, todos ellos basados en un filtrado de las posiciones en coordenadas de la ‘IR’ (ver Figura 29). El proceso sigue los mismos pasos que los explicados en el apartado Realimentación del tracking y corrección de errores del Capítulo 2. En resumen: a. Con las posiciones de los puntos en el instante t se calculan las posiciones en t + 1 mediante KLT. b. Con las posiciones obtenidas y las correspondientes en la ‘IR’ (método de ‘Reproyección Directa’) o en el fotograma anterior (método de ‘Reproyección Indirecta’), se obtiene la matriz de homografía ‘HR_T’ o ‘HR_T+1’ (según sea el método utilizado). c. Se proyectan las posiciones de los puntos en el instante actual sobre la ‘IR’ con dicha homografía. d. En este sistema de referencia, se compara la posición original de los puntos ‘puntos_ref’ con la obtenida de la proyección de los actuales ‘puntos_next_inv’. Se han probado tres métodos para el filtrado de los puntos: 1. Distancia máxima absoluta. Se establece un umbral máximo. Si la distancia entre un ‘puntos_ref’ y su correspondiente ‘puntos_next_inv’ es mayor que este umbral, se clasifica este punto como no válido. Este método tiene el problema de que necesita establecer un umbral “ad hoc”, y que a priori no puede ser intuido dado, entre otras cosas, a que depende de la velocidad de desplazamiento del observador o incluso de la velocidad de procesamiento, ya que si es necesario no procesar algún fotograma por mantener la sensación de tiempo real, el desplazamiento entre puntos es diferente. A este método de seguimiento de KLT con reproyección y filtrado por distancia máxima es al que llamamos ‘REPROY’. 2. Distancia máxima como función de la distancia media. Se establece un factor umbral máximo, ‘dist_th_factor’. Se calcula la distancia media de todos los ‘puntos_ref’ y sus correspondientes ‘puntos_next_inv’, ‘dist_mean’. Se clasifican como puntos no válidos a todos aquellos cuya distancia a su 44 Sistema de Realidad Aumentada en Entornos Reales Adversos correspondiente ‘puntos_ref’ este por encima de la ‘dist_mean’ * ‘dist_th_factor’: 𝑓𝑓𝑖𝑖𝑝𝑝𝑖𝑖𝑆𝑆𝑖𝑖𝑖𝑖𝑆𝑆(𝑥𝑥,𝑦𝑦;𝑖𝑖)= �> 𝑓𝑓𝑖𝑖𝑝𝑝𝑖𝑖_𝑖𝑖ℎ_𝑓𝑓𝑆𝑆𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖∗ 𝑓𝑓𝑖𝑖𝑝𝑝𝑖𝑖_𝑓𝑓𝑆𝑆𝑆𝑆𝑖𝑖; 𝑃𝑃𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖 𝑖𝑖𝑖𝑖 𝑖𝑖á𝑙𝑙𝑖𝑖𝑓𝑓𝑖𝑖 < 𝑓𝑓𝑖𝑖𝑝𝑝𝑖𝑖_𝑖𝑖ℎ_𝑓𝑓𝑆𝑆𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖∗ 𝑓𝑓𝑖𝑖𝑝𝑝𝑖𝑖_𝑓𝑓𝑆𝑆𝑆𝑆𝑖𝑖; 𝑃𝑃𝑝𝑝𝑖𝑖𝑖𝑖𝑖𝑖 𝑖𝑖á𝑙𝑙𝑖𝑖𝑓𝑓𝑖𝑖 Este método, igual que el anterior, requiere un umbral “ad hoc”, pero tiene la ventaja de que no es tan dependiente de factores externos como el anterior. Figura 29: Algoritmo de Tracking KLT frente a oclusiones cuando se realiza una validación por reproyección de las posiciones sobre la ‘Ir’ cada 10 fotogramas y un filtrado por distancia media. Con este método, el tracking KLT es capaz de superar oclusiones leves con un tiempo de procesado aceptable (~45 ms en los fotogramas en los que se ejecuta la corrección). El inconveniente principal es que, durante la proyección del contenido, en alguno de los pasos intermedios se producen vibraciones esporádicas visualmente incómodas (ver Figura 30). 45 Capítulo 3: Comparativa de métodos Figura 30: Vibraciones de la imagen. Tracking KLT frente a oclusiones con validación por reproyección de las posiciones sobre la ‘Ir’ y filtrado por distancia media. 3. Distancia máxima como función de la varianza de las distancias. Este es el filtro explicado en apartado Realimentación del tracking y corrección de errores del Capítulo 2: Sistema objetivo del estudio y el seleccionado como el mejor de ellos. Obtiene los mejores resultados visuales y es capaz de gestionar oclusiones leves con tiempos de ejecución razonables, ≈ 45 ms por fotograma ó ≈ 60ms en el fotograma concreto en que se ejecuta el filtrado. A este método de seguimiento de KLT con reproyección y filtrado basado en la confianza de la medida del desplazamiento es al que llamamos ‘REPROY+FILTRO’. Cualquiera de los tres métodos anteriores, permiten clasificar los puntos obtenidos en válidos y no válidos. Esta clasificación nos permite utilizar los puntos obtenido como válidos para refinar la homografía que nos ha facilitado el tracking, ‘H∗R_T+1’, y corregir la posición de los puntos no válidos. La posición de estos para el siguiente fotograma, será la obtenida por la proyección de sus correspondientes ‘puntos_ref’ con la nueva homografía refinada. Esto nos proporciona una posición para todos los puntos, la obtenida por el KLT en el caso de los puntos válidos (‘puntos_next’) y la obtenida por la proyección de los correspondientes ‘puntos_ref’ con la nueva homografía en los puntos no válidos. puntos_nextcorregidos= H∗R_T+1∗puntos_refpuntos_next_invno validos 46 Capítulo 4: Conclusiones y resultados 5. Se debe realizar una implementación sobre diferentes plataformas móviles y estudiar su comportamiento en ellas, tanto algorítmicamente (no sabemos si los mismos algoritmos que en un ordenador están funcionando correctamente también lo harán sobre Android o iOS) como en rendimiento (no es posible extrapolar el rendimiento de un Smartphone o una Tablet en relación a un ordenador), aunque el avance tecnológico tanto en hardware como en software que los diferentes dispositivos están experimentando, hace suponer que las posibles restricciones actuales serán solventadas en un futuro cercano. El proyecto TAMA continua por lo que este Proyecto Fin de Carrera será comprobado en el ámbito de un demostrador real. 52 Bibliografía [1] D. G. Lowe, «Object Recognition from Local Scale-Invariant Features,» de Proceedings of the International Conference on Computer Vision, ICCV '99 , Washington, DC, USA, 1999. [2] D. G. Lowe, «Distinctive Image Features from Scale-Invariant Keypoints,» Int. J. Comput. Vision, vol. 60, nº 2, pp. 91--110, 2004. [3] H. a. E. A. a. T. T. a. V. G. L. Bay, «Speeded-Up Robust Features (SURF),» Comput. Vis. Image Underst., vol. 110, nº 3, pp. 346--359, June, 2008. [4] H. Bay, T. Tuytelaars y L. V. Gool, «Surf: Speeded up robust features,» de In ECCV, 2006. [5] A. Haar, Zur Theorie der orthogonalen Funktionensysteme, Georg-AugustUniversitat, Gottingen., 1909. [6] P. Porwik y L. Agnieszka, «The New Graphic Description of the Haar Wavelet Transform.,» de International Conference on Computational Science, 2004. [7] E. Rosten y T. Drummond, «Fusing Points and Lines for High Performance Tracking,» de IN International Conference on Computer Vision, 2005. [8] E. Rosten, R. Porter y T. Drummond, «Faster and Better: A Machine Learning Approach to Corner Detection,» Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 32, nº 1, pp. 105-119, jan. 2010. [9] M. Calonder, V. Lepetit, C. Strecha y P. Fua, «BRIEF: binary robust independent elementary features,» de Proceedings of the 11th European conference on Computer vision: Part IV, Berlin, Heidelberg, 2010. [10] E. Rublee, V. Rabaud, K. Konolige y G. R. Bradski, «ORB: An efficient alternative to SIFT or SURF.,» de International Conference of Computer Vision , 2011. [11] J. Shi y C. Tomasi, «Good Features to Track,» de IEEE Conference on Computer Vision and Pattern Recognotion, Seattle, 1994. [12] K. D. Derpanis, «Overview of the RANSAC Algorithm,» York University, Toronto, Canada, 2010. [13] M. A. Fischler y R. C. Bolles, «Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography,» Commun. ACM, vol. 24, nº 6, pp. 381-395, 1981. [14] R. Zhang, «Automatic Computation of a Homography by RANSAC Algorithm,» ECE661 Computer Vision, 2008. [15] B. D. Lucas y T. Kanade, «An Iterative Image Registration Technique with an Application to Stereo Vision.,» de International Joint Conference on Artificial Intelligence, 1981. [16] J.-Y. Bouguet, Pyramidal Implementation of the Lucas Kanade Feature Tracker Description of the algorithm, Intel Corporation Microprocessor Research Labs, 2000. [17] R. E. Kalman, «A New Approach to Linear Filtering and Prediction Problems,» Journal of Basic Engineering, vol. 82, pp. 35-45, 1960. [18] G. Welch y G. Bishop, «An Introduction to the Kalman Filter,» University of 53 Bibliografıa North Carolina at Chapel Hill, Chapel Hill, NC, USA, 1995. [19] C. R. del Blanco, F. Jaureguizar, L. Salgado y N. García, «Motion estimation through efficient matching of a reduced number of reliable singular points,» de SPIE Real-Time Image Processing 2008, San Jose, CA, 2008. [20] G. Bradski, «The OpenCV Library,» Dr. Dobb's Journal of Software Tools, 2000. [21] G. Bradski y A. Kaehler, Learning OpenCV: Computer Vision with the OpenCV Library, 1st ed., O'Reilly Media, 2008. [22] S. Suzuki y K. Abe, «Topological structural analysis of digitized binary images by border following.,» Computer Vision, Graphics, and Image Processing, vol. 30, nº 1, pp. 32-46, 1985. [23] S. Bae, A. Agarwala y F. Durand, «Computational Rephotography,» ACM Trans. Graph., vol. 29, nº 3, pp. 24:1--24:15, #jul# 2010. [24] C. Harris y M. Stephens, «A Combined Corner and Edge Detector,» de Proceedings of the 4th Alvey Vision Conference, 1988. [25] P. Viola y M. Jones, «Rapid object detection using a boosted cascade of simple features,» 2001. [26] J. E. Bresenham, «Algorithm for Computer Control of a Digital Plotter.,» IBM Systems Journal, vol. 4, nº 1, pp. 25-30, 1965. [27] M. Muja y D. G. Lowe, «Fast approximate nearest neighbors with automatic algorithm configuration,» de In VISAPP International Conference on Computer Vision Theory and Applications, 2009. [28] «Sistema y Procedimiento de Observación Ampliada». 2007. [29] A. Gionis, P. Indyk y R. Motwani, «Similarity Search in High Dimensions via Hashing,» de Proceedings of the 25th International Conference on Very Large Data Bases, San Francisco, CA, USA, 1999. [30] Q. Lv, W. Josephson, Z. Wang, M. Charikar y K. Li, «Multi-probe LSH: Efficient Indexing for High-dimensional Similarity Search,» de Proceedings of the 33rd International Conference on Very Large Data Bases, 2007. [31] H. Voorhees y T. Poggio, «Detecting Textons and Texture Boundaries in Natural Images.,» 1987. [32] P. L. Rosin, «Edges: saliency measures and automatic thresholding.,» Mach. Vis. Appl., vol. 9, nº 4, pp. 139-159, 1997. [33] G. Klein y D. Murray, «Parallel Tracking and Mapping for Small {AR} Workspaces,» de Proc. Sixth {IEEE} and {ACM} In ternational Symposium on Mixed and Augmented Reality {(ISMAR'07)}, Nara, Japan, 2007. 54 Sistema de Realidad Aumentada en Entornos Reales Adversos Tabla de Figuras Figura 1: A la derecha se observa la imagen del Cubo de la Seo. A la izquierda se representa la proyección de imagen "virtual" sobre la superficie de proyección elegida ......................................................................................... 3 Figura 2: Inicialización del sistema en distintas condiciones .......................................... 3 Figura 3: Proyección coherente durante la secuencia ...................................................... 3 Figura 4: Gestión de oclusión leve .................................................................................. 4 Figura 5: Gestión de oclusión grave, mecanismo de detección ....................................... 4 Figura 6: Esquema de control en bucle cerrado ............................................................ 13 Figura 7: Esquema detallado del sistema ...................................................................... 14 Figura 8: Proceso de inicialización. Se buscan puntos SIFT para detectar la superficie de proyección. Si la zona de proyección no es visible completamente (parte izquierda de la figura) se sigue buscando el momento en que lo sea (parte derecha de la figura). A partir de ese instante el tracking KLT puede comenzar normalmente. ............................................................................... 17 Figura 9: Extracción de puntos SIFT y ‘matching’ inicial ............................................ 19 Figura 10: Tracking KLT en paralelo con el registro del primer fotograma para corregir desplazamientos durante el procesado. ........................................................ 20 Figura 11: Doble correspondencia homográfica, relación entre la Imagen a Proyectar, IP y el primer fotograma de la secuencia, I0 .................................................... 21 Figura 12: Proyección de la imagen sobre cualquier fotograma de la secuencia por medio del tracking de puntos ....................................................................... 23 Figura 13: Sistema de tracking KLT soporta giros no muy bruscos con cierta vibración ..................................................................................................................... 24 Figura 14: Sistema de tracking KLT falla en situaciones con oclusiones. .................... 24 Figura 15: Puntos característicos de tipo SIFT .............................................................. 29 Figura 16: Puntos característicos de tipo SURF ............................................................ 30 Figura 17: Puntos característicos de tipo FAST ............................................................ 30 Figura 18: Resultados del emparejamiento con los distintos tipos de características. .. 31 Figura 19: Mascara binaria y superficie de proyección del fotograma actual, respectivamente. .......................................................................................... 33 Figura 20: Contornos de los objetos en primer plano. ................................................... 34 55 Bibliografıa Figura 21: Proyección de la imagen sobre cualquier fotograma de la secuencia por medio del tracking de puntos ....................................................................... 36 Figura 22: Algoritmo de Tracking KLT frente a oclusiones cuando se realiza un reemparejamiento cada 10 fotogramas mediante SIFT ............................... 37 Figura 23: Algoritmo de Tracking KLT frente a oclusiones cuando se realiza un reemparejamiento cada 10 fotogramas mediante SIFT y máscara de búsqueda en la ROI del fotograma anterior ................................................. 38 Figura 24: Tracking mediante FAST y descriptores BRIEF. Resultado bastante inestable. ...................................................................................................... 39 Figura 25: Tracking ORB. Resultados inestables incluso sin oclusiones. .................... 40 Figura 26: Tracking con método FFME. No supera oclusiones. ................................... 41 Figura 27: Seguimiento mediante características p-SIFT. Soporta oclusiones leves. ... 42 Figura 28: Seguimiento mediante FAST y medida de similaridad SSD. Resultado no soporta oclusiones. ....................................................................................... 43 Figura 29: Algoritmo de Tracking KLT frente a oclusiones cuando se realiza una validación por reproyección de las posiciones sobre la ‘Ir’ cada 10 fotogramas y un filtrado por distancia media. ............................................. 45 Figura 30: Vibraciones de la imagen. Tracking KLT frente a oclusiones con validación por reproyección de las posiciones sobre la ‘Ir’ y filtrado por distancia media. .......................................................................................................... 46 Figura 31: Para cada octava del espacio de escalas, la imagen inicial es repetidamente convolucionada con Gaussianas para producir un conjunto de imágenes en el espacio de escalas como el mostrado a la izquierda. Imagenes convolucionadas adyacentes se sustraen para producir imágenes de diferencia de gaussianas como el mostrado a la derecha. Después, para cada octava, la imagen se muestrea reduciendo en un factor 2 y el proceso se repite. ............................................................................................................ iii Figura 32: Búsqueda de máximo y mínimo en las imágenes diferencia de gaussianas mediante la comparación del píxel marcado con un X y sus 26 vecinos de la región 3x3 de la imagen actual y las adyacentes en escala superior e inferior marcados con círculos. ................................................................................. iii Figura 33: Filtros gaussianos de segundo orden en la dirección Y, y en la dirección XY. Discretizaciones. ........................................................................................... vi Figura 34: Píxeles del círculo de Bresenham de radio 3. .............................................. vii 56 Sistema de Realidad Aumentada en Entornos Reales Adversos Figura 35: El descriptor de un keypoint se crea calculando la magnitud del vector gradiente y la orientación de cada punto de muestra en una región alrededor de la localización del keypoint, como se muestra a la izquierda. A la ventana se la aplica una gaussiana ponderada que está representada por el circulo sobreimpreso. Las muestras son acumuladas en histogramas de orientación resumiendo el contenido de subregiones 4x4, como se muestra en la derecha. La longitud de cada flecha se corresponde con la suma de las magnitudes del gradiente en cada dirección dentro de la región. Esta figura muestra un descriptor de 2x2 calculado en conjuntos de muestras de 8x8. ... i Figura 36: Máscaras Haar en las direcciones X e Y. ...................................................... iii Figura 37: Kernel de convolución para p-SIFT. ........................................................... xiii Figura 38: Posiciones de los 16 puntos (en rojo) en torno al punto de interés (en negro) de donde se extraen los valores de las 8 imágenes de ángulos. .................. xiii Figura 39: Construcción del descriptor SSD de un pixel. ............................................ xvi Figura 40: Emparejamiento de IR e I0 en situaciones con diferente iluminación y escala. Método FAST + ZM-SSD. ........................................................................ xvii Figura 41: Emparejamiento de IR e I0 en situaciones con similares condiciones de iluminación y escala. Método FAST + ZM-SSD. .................................... xviii Figura 42: Emparejamiento Inicial mediante SIFT. Tracking entre frames mediante extracción de puntos FAST + ZM-SSD. .................................................... xix Tabla de Gráficas Gráfica 1: Resultados globales obtenidos por métodos y distractores. 47 Gráfica 2: Resultados correctos obtenidos por métodos y tipo de distractor. 48 57 Anexos Anexo 1: Tipos de Características La aplicación desarrollada en este trabajo requiere conocer la situación relativa del observador respecto de un escenario mediante las imágenes captadas por un dispositivo móvil que este observador lleve consigo. Para realizar esta tarea, se necesita hacer corresponder ciertas superficies que aparecen en las imágenes captadas con las superficies de proyección que se han utilizado en el entrenamiento de este escenario. A este proceso de emparejamiento utilizando varias imágenes captadas desde diferentes puntos de vista y con diferentes condiciones, se le denomina Registro de Imágenes. Los métodos más estudiados en la bibliografía de registro de imágenes se basan en la extracción y emparejamiento de características muy concretas como por ejemplo esquinas o bordes de objetos o edificios, cambios bruscos de color que indiquen posibles objetos diferentes o características similares, cambios de texturas, etc... Se ha estudiado varias de las características más importantes de la bibliografía implementando pruebas para evaluar la aportación de cada una de ellas. En este anexo se hace una descripción de su extracción y su representación mediante descriptores, así como las ventajas e inconvenientes de cada una de ellas. 1. Características SIFT. ‘Scale-Invariant Feature Transform’ [1] [2]. Son características muy robustas, invariantes a escala y a rotación. En [2] se proporciona un método robusto de ‘matching’ que permite una sustancial solidez frente a distorsiones afines, cambios de punto de vista, ruido y cambios de iluminación. El coste de extracción de las características es minimizado mediante una aproximación en cascada donde los filtros y las operaciones más costosas sólo son aplicados a las localizaciones que superan el primer test. Las etapas de la extracción de características son las siguientes: • Detección de extremos en el espacio de escalas. Se busca identificar localizaciones y escalas que puedan ser reconocidas de forma repetible bajo diferentes puntos de vista del objeto. Para esta tarea, se utiliza un i Anexo 1: Tipos de Caracterısticas kernel gaussiano dependiente de la escala con el que se obtiene la función “espacio-escala” (‘escale space’) de una imagen, L(x,y,σ). Esta función resulta de la convolución de un kernel gaussian dependiente de la escala, G(x,y,σ) sobre la imagen de entrada, I(x,y): 𝐿𝐿(𝑥𝑥,𝑦𝑦,𝜎𝜎)=𝐺𝐺(𝑥𝑥,𝑦𝑦,𝜎𝜎)∗𝐼𝐼(𝑥𝑥,𝑦𝑦) donde * es la operación de convolución en x e y, y: 𝐺𝐺(𝑥𝑥,𝑦𝑦,𝜎𝜎)=1 2𝜋𝜋𝜎𝜎2𝑆𝑆−�𝑥𝑥2+𝑦𝑦2� 2𝜎𝜎2 Para la localización eficiente de ‘keypoints’ estables en posición y escala, se propone buscar los extremos en la función diferencia de las gaussianas (DoG, ‘Difference of Gaussians’) con las que se ha convolucionado la imagen, D(x,y,σ). Las funciones ‘DoG’ pueden ser calculadas mediante la diferencia de 2 escalas cercanas entre sí pero separadas por un factor multiplicativo y constante k: 𝐷𝐷(𝑥𝑥,𝑦𝑦,𝜎𝜎)=�𝐺𝐺(𝑥𝑥,𝑦𝑦,𝑜𝑜𝜎𝜎)−𝐺𝐺(𝑥𝑥,𝑦𝑦,𝜎𝜎)�∗𝐼𝐼(𝑥𝑥,𝑦𝑦) =𝐿𝐿(𝑥𝑥,𝑦𝑦,𝑜𝑜𝜎𝜎)−𝐿𝐿(𝑥𝑥,𝑦𝑦,𝜎𝜎) El uso de la función de diferencia de gaussianas con escala lleva implícita una normalización de escala con el factor σ2 que se requiere para la invariabilidad a escala. Una forma eficiente de construir la función D(x,y,σ), se muestra en Figura 30. La imagen inicial es incrementalmente convolucionada con gaussianas que producen imágenes separadas por un factor constante k en el espacio de escalas. Se elige dividir cada octava del espacio de escalas (correspondiente a doblar el valor de σ) en un número entero, s, de intervalos, lo que supone que 𝑜𝑜= 21𝑠𝑠. Por lo tanto se deben producir s+3 imágenes por cada octava para que al final la detección de los extremos cubra la octava al completo. Experimentalmente se ha comprobado que 𝑝𝑝= 3 da el mejor resultado. Las imágenes de la escala adyacentes se restan para producir la ‘DoG’ como se muestran en la parte derecha de la Figura 30. ii Sistema de Realidad Aumentada en Entornos Reales Adversos Figura 31: Para cada octava del espacio de escalas, la imagen inicial es repetidamente convolucionada con Gaussianas para producir un conjunto de imágenes en el espacio de escalas como el mostrado a la izquierda. Imagenes convolucionadas adyacentes se sustraen para producir imágenes de diferencia de gaussianas como el mostrado a la derecha. Después, para cada octava, la imagen se muestrea reduciendo en un factor 2 y el proceso se repite. Una vez que la octava se ha procesado completamente, se submuestrea la imagen de gaussianas para que tenga dos veces el valor inicial de σ, tomando todos los píxeles pares de cada fila y columna. • Localización de los ‘keypoints’. Para detectar los mínimos y máximos locales de D(x,y,σ), cada punto se compara con los 8 vecinos de la propia escala y con los 9 vecinos de las escalas superior e inferior (ver Figura 31). Figura 32: Búsqueda de máximo y mínimo en las imágenes diferencia de gaussianas mediante la comparación del píxel marcado con un X y sus 26 vecinos de la región 3x3 de la imagen actual y las adyacentes en escala superior e inferior marcados con círculos. iii Anexo 2: Descriptores y Emparejamiento o ‘matching’ de características. Una vez que se dispone de una serie de las coordenadas de las características en varias imágenes, es necesario identificar cuáles de ellas se corresponden entre sí, es decir, cuáles de esas características son la misma pero vista desde diferente perspectiva. A este proceso de hacer corresponder una característica en una imagen consigo misma vista desde otra perspectiva en otra imagen se le denomina emparejamiento de características o ‘matching’. Este proceso de ‘matching’ necesita de una forma de identificar lo más unívocamente posible a cada una de esas características con independencia de cualquier factor dependiente de la iluminación, la perspectiva, el enfoque, etc… Este identificador es lo que se conoce como descriptor de la característica. Descriptores Existen multitud de descriptores de características en la bibliografía de los cuales, en este proyecto, se han utilizado los siguientes: o Descriptores SIFT. Los pasos para la detección de los ‘keypoints’ SIFT (detallados en el apartado Características SIFT del Anexo 1), han asignado una localización, una escala y una orientación a cada uno de los ‘keypoints’. En la Figura 34 se ilustra el cálculo del descriptor del ‘keypoint’. Figura 35: El descriptor de un keypoint se crea calculando la magnitud del vector gradiente y la orientación de cada punto de muestra en una región alrededor de la localización del keypoint, como se muestra a la izquierda. A la ventana se la aplica una gaussiana ponderada que está representada por el circulo sobreimpreso. Las muestras son acumuladas en histogramas de orientación resumiendo el contenido de subregiones 4x4, como se muestra en la derecha. La longitud de cada flecha se corresponde con la suma de las magnitudes del gradiente en cada dirección dentro de la región. Esta figura muestra un descriptor de 2x2 calculado en conjuntos de muestras de 8x8. i Anexo 2: Descriptores y Emparejamiento o ‘matching’ de Características En primer lugar se muestrea la imagen de la magnitud del vector gradiente y las orientaciones alrededor del ‘keypoint’ utilizando la escala del propio ‘keypoint’ para seleccionar el nivel de la gaussiana que suavizará la imagen. Para conseguir invarianza a orientación las coordinadas del descriptor y las orientaciones de los gradientes se rotan en relación a la orientación del ‘keypoint’. Se utiliza una función gaussiana ponderada con σ igual a la mitad del ancho de la ventana del descriptor para asignar un peso a la magnitud de cada punto de muestra. El descriptor que se utiliza permite pequeños desplazamientos en las posiciones del gradiente mediante la creación de de histogramas de orientación sobre regiones de 4x4. La Figura 34 muestra 8 direcciones para cada histograma de orientación, en los cuales se indica la magnitud de cada entrada del histograma mediante la longitud de la flecha. Para evitar los efectos de borde, se aplica una interpolación trilineal para distribuir los valores de cada muestra del gradiente en varios histogramas adyacentes. El descriptor se forma partiendo del vector que contiene los valores de todas las entradas del histograma de orientaciones. Los mejores resultados se alcanzan con vectores de 4x4 histogramas de 8 orientaciones cada uno, por lo tanto el vector de un descriptor utiliza 4x4x8 = 128 elementos por cada ‘keypoint’. Finalmente el vector de la característica se modifica para reducir los efectos de los cambios de iluminación normalizándolo a la longitud unidad. o Descriptores SURF. La construcción del descriptor conlleva dos pasos: • En primer lugar se busca información reproducible de la orientación en una región circular en torno al punto de interés con el fin de que el descriptor sea invariante a rotación. Se calcula la respuesta a las máscaras de Haar, ‘Haar-wavelet’ en las direcciones x e y con las máscaras que se muestran en Figura 35, y en una vecindad ii Sistema de Realidad Aumentada en Entornos Reales Adversos compuesta por un circulo de radio 6s donde s es la escala del punto de interés detectado. Figura 36: Máscaras Haar en las direcciones X e Y. En este paso se hace uso de nuevo de las imágenes integrales apra acelerar el proceso. Una vez calculada la respuesta a la máscara y ponderada por una Gaussiana centrada en el punto de interés, se representa como un vector con el valor de la componente horizontal en abscisas y el valor de la componente vertical en ordenadas. La orientación dominante se estima calculando la suma de todas las respuestas dentro de una ventana deslizante de orientaciones que cubre un ángulo de 𝜋𝜋3. Las respuestas en las componentes horizontal y vertical se suman dando un nuevo vector. • El segundo paso es construir una región cuadrada alineada con la orientación seleccionada y extraer el descriptor SURF de ella. Para ello el primer paso es construir una región cuadrada centrada en el punto de interés y orientada a lo largo de la dirección de orientación seleccionada en el paso previo. La región se divide en 4 x 4 subregiones cuadradas más pequeñas. Para cada subregión se calculan unas pocas características (5x5) en unos puntos de muestra espaciados regularmente. Se llaman dx y dy a la respuesta de las máscaras Haar en direcciones horizontal y vertical respectivamente, entendiendo por “horizontal” y “vertical” a éstas direcciones referidas a la orientación seleccionada. Las respuestas dx y dy son sumadas sobre cada subregión formando un primer conjunto de entradas en el vector característico. Con el fin de obtener información sobre la ‘polaridad’ de la intensidad se extraen también estas sumas en valor absoluto |dx| y |dy|. De esta forma en cada iii Anexo 2: Descriptores y Emparejamiento o ‘matching’ de Características subregión se dispone de un vector del descriptor de 4 dimensiones, 𝑖𝑖=�∑𝑓𝑓𝑥𝑥,∑𝑓𝑓𝑦𝑦,∑|𝑓𝑓𝑥𝑥|,∑�𝑓𝑓𝑦𝑦��. Esto resulta en un descriptor para todas las subregiones de tamaño 4x4 con una longitud de 64. La respuesta a las máscaras hace al descriptor invariante a cambios de iluminación global. La invarianza al contraste y a escala se obtiene normalizando el vector a la unidad. o Descriptores BRIEF. Binary Robust Independent Elementary Features [9]. Se trata de un descriptor que propone el uso de palabras binarias como descriptor eficiente de puntos característicos. Son descriptores robustos a cambios de iluminación, distorsión de la perspectiva y desenfoque, pero muy sensibles a rotación. Como medida de similaridad puede utilizarse la distancia de Hamming cuyo cómputo es más eficiente que la norma L2 utilizada habitualmente. Para la obtención de los bits individuales del descriptor se comparan las intensidades de pares de puntos pero sin la necesidad de una fase de entrenamiento como ocurre en otros métodos. El proceso de construcción del vector de bits del descriptor es el siguiente: Algoritmo • Se calcula un suavizado o smooth del patch p de la imagen en torno al punto del que se quiere obtener el descriptor. • Se define como test τ en el patch p de tamaño S x S como: 𝜏𝜏(𝑝𝑝;𝑥𝑥,𝑦𝑦)∶=�1 𝑖𝑖𝑓𝑓 𝑝𝑝(𝑥𝑥)<𝑝𝑝(𝑦𝑦) 0 𝑖𝑖𝑖𝑖ℎ𝑆𝑆𝑖𝑖𝑤𝑤𝑖𝑖𝑝𝑝𝑆𝑆 donde p(x) es la intensidad del pixel en la versión suavizada de p en x = (u,v)T • Se elige un conjunto de nd(x,y) pares de localizaciones lo cual define un conjunto de test binarios. Este método toma el descriptor BRIEF como la cadena de bit nd-dimensional: 𝑓𝑓𝑖𝑖𝑑𝑑(𝑝𝑝)∶=�2𝑖𝑖−1 𝜏𝜏(𝑝𝑝;𝑥𝑥𝑖𝑖,𝑦𝑦𝑖𝑖) 1≤𝑖𝑖≤𝑖𝑖𝑑𝑑 iv Sistema de Realidad Aumentada en Entornos Reales Adversos • Las distintas pruebas realizadas en [9] indican que el tamaño del patch de 9x9 píxeles es necesario y suficiente. • Los mejores resultados en la elección de las nd localizaciones de los test binarios se consiguen con una distribución como la que sigue: Distribución Gaussiana isotrópica donde: 𝑝𝑝2=5 2𝜎𝜎⇔𝜎𝜎2=1 25 𝑆𝑆2 o Descriptores rBRIEF. Rotated BRIEF [10]. Los descriptores rBRIEF son una modificación de los BRIEF que les permiten ser invariantes a las rotaciones en el plano. Son un tipo de descriptores que permiten utilizar la información de rotación que incorporan los puntos oFAST para construir un descriptor de palabras binarias invariante a rotación. En [10] se introduce el descriptor steered-BRIEF para dotar al descriptor BRIEF de invariabilidad frente a rotaciones en el plano a través de la información de la orientación de los keypoints. Así, para todo el conjunto de características de n test binarios en las localizaciones (xi, yi), se define la matriz 2 x n: 𝑺𝑺= �𝒙𝒙𝟏𝟏, … , 𝒙𝒙𝒏𝒏 𝒚𝒚𝟏𝟏, … , 𝒚𝒚� utilizando la orientación del patch θ y la correspondiente matriz de rotación Rθ, se construye una versión “steered” Sθ de S: 𝑆𝑆𝜃𝜃=𝑅𝑅𝜃𝜃𝑆𝑆 por lo que el operador steered BRIEF queda así: 𝑓𝑓𝑖𝑖(𝑝𝑝,𝜃𝜃)∶=𝑓𝑓𝑖𝑖(𝑝𝑝)|(𝑥𝑥𝑖𝑖,𝑦𝑦𝑖𝑖)∈𝑆𝑆𝜃𝜃 discretizando el ángulo a incrementos de 2π/30 (12 grados) y construyendo una look-at-table se pueden tener pre-calculados los patrones BRIEF. Se demuestra en este artículo que es necesario reducir la correlación entre los test binarios y evitar la pérdida de la varianza que supone el método de steered-BRIEF por lo que se propone un método de aprendizaje para seleccionar un buen conjunto de test binarios. Algoritmo: v Anexo 2: Descriptores y Emparejamiento o ‘matching’ de Características • Se establece un conjunto de entrenamiento de N keypoints. • Se enumeran todos los posibles test binarios con patch de tamaño 31 x 31. Cada test es una pareja de 5x5 sub-ventanas del patch. • Se ejecuta cada uno de los test contra todos los patches de entrenamiento. • Se ordenan los test por distancia a una media de 0.5, formando el vector T. • Se realiza una búsqueda exhaustiva: o Se coloca el primer test en el vector R y se elimina de T. o Se toma el siguiente test de T y se compara con todos los test de R. Si la correlación absoluta es mayor que un umbral, se descarta, si no se añade a R. o Se repite el paso anterior hasta que se han añadido 256 test a R. Si no se consiguen al menos 256 test se aumenta el umbral y se repite el proceso. Al resultado obtenido, es a lo que se denomina rBRIEF. Matching El proceso de ‘matching’ es el encargado de hacer corresponder los descriptores de un grupo de características (al que se denomina ‘query’) con los descriptores de otro grupo de entrenamiento o previo (al que se denimona ‘train’) de la forma más consistente posible utilizando algún método de emparejamiento y mediante una medida concreta de similaridad. En la bibliografía se destacan dos métodos de emparejamiento principalmente: • Emparejamiento por fuerza bruta. Este método consiste en realizar una búsqueda barriendo todas las posibilidades existentes, es decir, en el caso de emparejamiento de características, todos los descriptores del grupo ‘query’ se comparan con todos los descriptores del grupo ‘train’ extrayendo la mejor correspondencia para cada uno de ellos. • Método FLANN de emparejamiento (Fast Library for Approximate Nearest Neighbors) [27]. Permite un emparejamiento más rápido que el de fuerza bruta para un número elevado de muestras gracias a un entrenamiento previo. vi Sistema de Realidad Aumentada en Entornos Reales Adversos Las medidas de similaridad más frecuentemente utilizadas son: • Norma L2. La norma L2 se define como la raíz cuadrada de la suma de las diferencias cuadráticas entre los dos descriptores, dquery, dtrain. 𝐿𝐿2=���𝑓𝑓𝑝𝑝𝑞𝑞𝑒𝑒𝑟𝑟𝑦𝑦𝑘𝑘−𝑓𝑓𝑡𝑡𝑟𝑟𝑡𝑡𝑖𝑖𝑖𝑖𝑘𝑘�2 𝑖𝑖 𝑘𝑘=1 • Distancia de Hamming. La distancia de Hamming se define como el número de bits que tienen que cambiarse para transformar una palabra válida en otra palabra válida. Si dos palabras de código difieren en una distancia d, se necesitan d cambios para convertir una en la otra. Si se utiliza en el ámbito de comparación de los descriptores, representa al número de bits de un descriptor ‘query’ que deben cambiar para convertirse en el descriptor ‘train’ con el que se está comparando. • Sum of Square Differences, ‘SSD’. Se trata de un método para medir la similaridad entre dos elementos compuestos como pueden ser descriptores o regiones de una imagen. Si ‘I1’ es un elemento compuesto por (u,v) elementos simples que se quiere comparar con un elemento compuesto ‘I2’ del mismo tamaño, la SSD se define como: 𝑆𝑆𝐷𝐷𝐷𝐷=��𝐼𝐼1(𝑝𝑝,𝑖𝑖)−𝐼𝐼2(𝑝𝑝,𝑖𝑖)�2 𝑞𝑞,𝑖𝑖 Con el objetivo de que el proceso de emparejamiento sea lo más robusto posible, se realizan varias operaciones: • Doble emparejamiento. o Emparejamiento de los descriptores de la ‘I0’, ‘query’, con los descriptores de la ‘IR’, ‘train’. En esta fase se utiliza la medida de similaridad Norma L2 explicada anteriormente. Se obtienen los ‘matches1’ correspondientes a los emparejamientos más similares. o Etapa inversa a la anterior. Emparejamiento de los descriptores de la ‘IR’, ‘train’ con los descriptores de la ‘I0’, ‘query’. Se obtienen los ‘matches2’. vii Anexo 2: Descriptores y Emparejamiento o ‘matching’ de Características o Test de simetría. De entre los emparejamientos ‘matches1’ y ‘matches2’, solo se seleccionan aquellos de los ‘matches1’ que han dado resultados correctos en ‘matches2’ y que simultáneamente los ‘matches2’ han dado en ‘matches1’ los mismos emparejamientos. Así se seleccionan los ‘matches’. • Filtrado por ‘ratio’. Dado que en cada uno de los emparejamientos se buscan los 2 mejores ‘train’ para cada ‘query’y viceversa, se puede hacer un filtrado por ratio. Este filtrado consiste en comparar entre si cada uno de los 2 descriptores ‘train’ encontrados para un mismo ‘query’ y descartar este emparejamiento si la distancia entre ellos es mínima. Recíprocamente se filtran para los descriptores ‘query’ encontrados para un mismo ‘train’. En definitiva, los dos descriptores encontrados cuando se busca el descriptor más parecido a uno dado, deben ser diferentes y diferenciables. • Filtrado por RANSAC. Se realiza un test de simetría, es decir, Se someten los ‘matches’ a un test de RANSAC para eliminar espurios tomando como modelo geométrico una transformación homográfica. Este método de filtrado se explica a continuación. En visión por computador existen técnicas que permiten mejorar y refinar el emparejamiento de características. El más conocido y quizá más fiable es el método RANSAC, RANdom Sample Consensus [12] [13]. Este método de ajuste de características a geometrías conocidas es especialmente útil en el filtrado de puntos para el cálculo de homografías entre planos [14]. Homografía Una homografía es una transformación lineal no singular de los puntos pertenecientes a un plano. Intuitivamente se puede ver como la transformación proyectiva (no perspectiva) de un plano. Geométricamente y matemáticamente una homografía será una matriz de transformación afín que nos pondrá en correspondencia los puntos pertenecientes a un plano entre diferentes vistas del mismo. Una vista es una proyección perspectiva del mundo real (en este caso, el mundo real será un plano). viii Sistema de Realidad Aumentada en Entornos Reales Adversos En el mundo real una homografía pondrá en correspondencia ideal todos los puntos de una vista tan sólo para aquellas vistas en las que únicamente exista movimiento rotacional de la cámara, es decir, sin cambio de perspectiva. Sin embargo, dado que una homografía permite hacer correspondencias entre los puntos de un mismo plano aún cuando entre las diferentes vistas exista traslación, giro o simetría, el uso de homografías es utilizado en multitud de aplicaciones: • Corrección de perspectiva. • Creación de panoramas. • Captura, restauración y corrección de documentos. • Calculo de velocidades, distancias y trayectorias, etc. El proceso de corrección de perspectiva es un problema recurrente en muchas aplicaciones de visión artificial y en concreto en tareas como ayuda al tracking, cálculo de velocidades y distancias reales, tracking multi-cámara, ampliación del campo de visión [28], etc… Se suele utilizar principalmente cuando se quiere una vista concreta de la escena u objeto de interés mediante una transformación perspectiva. El objetivo es el de llevar la proyección de un plano desde una vista origen a otra destino. Lo primero es recuperar la geometría del plano. La forma de hacer esto es con correspondencias puntuales. Tras ello necesitamos calcular una matriz de transformación que nos mapee los puntos desde la vista origen a la destino. Este tipo de transformación se le conoce como transformación proyectiva y se trata de una extensión de la transformación afín (la cual es un ix Anexo 3: Metodos de Tracking • Oclusiones. Puede ser que un objeto de interés no se observe bien cuando sea parcial o totalmente tapado por otros objetos en la escena. Las oclusiones son generalmente debidas a: o Un objeto de interés que se mueve detrás de un objeto estático, como por ejemplo una columna. o Otros objetos que se mueven en la escena de manera que entorpecen la visión de un objeto de interés. Métodos de tracking Los objetos se pueden representar mediante sus formas o apariencias, aunque una de las caracterizaciones más utilizadas generalmente se basan en la extracción de un conjunto de puntos de interés. Éste es el método principal utilizado durante este proyecto y todos los métodos utilizados para conseguir un tracking robusto se basan en el seguimiento de estos puntos de interés. 1. Flujo óptico disperso y tracking KLT. Algoritmo de seguimiento basado de Lucas-Kanade [15] que calcula del flujo óptico de forma piramidal. Es un método muy rápido y que obtiene muy buenos resultados en ausencia de oclusiones [16]. En visión por computador se conoce por flujo óptico al movimiento aparente de los píxeles de una imagen de un fotograma a otro dentro de una secuencia de video. Con puntos en tres dimensiones, el flujo óptico es definido como una medida de cómo se movieron dichos puntos en el espacio. El cálculo del flujo óptico no es un problema sencillo y computarlo para tomas realizadas en un ambiente real puede llegar a ser muy complicado. Por eso los algoritmos existentes se basan en determinadas hipótesis (intensidad constante, rigidez de los objetos, coherencia espacial, entre otras) que generalmente no se cumplen totalmene en escenarios reales. ii Sistema de Realidad Aumentada en Entornos Reales Adversos Tipos de flujo óptico Independientemente de la técnica que implementen, por los resultados que producen, los métodos pueden clasificarse en dos grandes grupos, algoritmos de flujo óptico disperso y algoritmos de flujo óptico denso. • Flujo óptico disperso Como su nombre lo sugiere el flujo óptico disperso no computa los vectores de velocidad para cada píxel de la imagen. El primer paso es seleccionar una serie de regiones de la imagen que sean buenas para rastrear (bordes, esquinas, manchas, etc). Luego para ese conjunto reducido de puntos se calcula el flujo óptico para toda la imagen. Uno de los primeros algoritmos que uso este enfoque fue el de Lukas-Kanade propuesto en 1981. • Flujo óptico denso El flujo óptico denso a diferencia del disperso se caracteriza por computar el vector de velocidad para cada píxel de la imagen. Generalmente este es un proceso computacionalmente costoso por lo que no es factible aun hacerlo en tiempo real, aunque con el desarrollo de las tarjetas de video y los algoritmos recientes se han logrado grandes avances en este sentido. Un exponente clásico de este grupo es el algoritmo de Horn y Shunk que data de 1981. La principal hipótesis detrás del cálculo del flujo óptico es la conservación de la intensidad o el color de un píxel en el tiempo a pesar del posible cambio de posición. Matemáticamente se expresa mediante la ecuación. 𝑓𝑓(𝑥𝑥+𝛥𝛥𝑥𝑥,𝑦𝑦+𝛥𝛥𝑦𝑦,𝑖𝑖+𝛥𝛥𝑖𝑖)≈𝑓𝑓(𝑥𝑥,𝑦𝑦,𝑖𝑖) La ecuación no brinda en todos los casos una solución única. Esto es conocido como el problema de apertura. El problema de computar la velocidad total de la imagen se transforma entonces en encontrar otra restricción que permita despejar la incógnita restante. Existen varias técnicas para intentar dar solución a esta ecuación, técnicas diferenciales, de análisis de frecuencia o energía y las basadas en correlación. Estas últimas se basan en la búsqueda de correspondencias iii Anexo 3: Metodos de Tracking utilizando ventanas o patrones alrededor de cada píxel. La ventaja que tienen con respecto a los anteriores, es que se utiliza información de los vecinos que en muchos casos hacen que la búsqueda de la correspondencia sea más efectiva. Lo que se busca con estos métodos es asociar píxeles a través de regiones similares en las imágenes que se obtienen por maximización de alguna medida de similaridad. Serán este tipo de técnicas las que utilizaremos en este proyecto. En concreto en [16] el método compara la intensidad de dos imágenes en escala de grises I y J en un entorno de los puntos de interés. El objetivo del tracking de características es encontrar la localización v = u + d = [ux + dx uy + dy]T en la segunda imagen J, de los puntos x = [x y]T en la primera imagen I. El vector d = [dx dy]T es considerado como la velocidad de la imagen en x, y u = [ux uy]T es el punto en la imagen I. Se define la velocidad de la imagen como el vector que minimiza la función residual definida por: 𝜖𝜖(𝑓𝑓)=𝜖𝜖�𝑓𝑓𝑥𝑥,𝑓𝑓𝑦𝑦�=� � �𝐼𝐼(𝑥𝑥,𝑦𝑦)−𝐽𝐽�𝑥𝑥+𝑓𝑓𝑥𝑥,𝑦𝑦+𝑓𝑓𝑦𝑦��2 𝑞𝑞𝑦𝑦+𝑤𝑤𝑦𝑦 𝑞𝑞𝑦𝑦−𝑤𝑤𝑦𝑦 𝑞𝑞𝑥𝑥+𝑤𝑤𝑥𝑥 𝑞𝑞𝑥𝑥−𝑤𝑤𝑥𝑥 Ecuación 3: Función residual para el cálculo del flujo óptico Con el doble objetivo de mejorar la fiabilidad frente a cambios de escala y al mismo tiempo poder manejar grandes desplazamientos de los píxeles, esta implementación al igual que otras implementaciones de métodos de extracción de características, construyen una representación piramidal de imágenes. Se define una representación piramidal de una imagen genérica I de tamaño nx x ny como una representación recursiva de I, IL(x,y) donde: 𝐼𝐼𝐿𝐿(𝑥𝑥,𝑦𝑦)=1 4𝐼𝐼𝐿𝐿−1(2𝑥𝑥, 2𝑦𝑦) + 1 8�𝐼𝐼𝐿𝐿−1(2𝑥𝑥−1,2𝑦𝑦)+𝐼𝐼𝐿𝐿−1(2𝑥𝑥+ 1,2𝑦𝑦)+𝐼𝐼𝐿𝐿−1(2𝑥𝑥, 2𝑦𝑦−1) +𝐼𝐼𝐿𝐿−1(2𝑥𝑥, 2𝑦𝑦+ 1)� +1 16 �𝐼𝐼𝐿𝐿−1(2𝑥𝑥−1,2𝑦𝑦−1)+𝐼𝐼𝐿𝐿−1(2𝑥𝑥+ 1,2𝑦𝑦+ 1) +𝐼𝐼𝐿𝐿−1(2𝑥𝑥−1,2𝑦𝑦+ 1)+𝐼𝐼𝐿𝐿−1(2𝑥𝑥+ 1,2𝑦𝑦+ 1)� iv Sistema de Realidad Aumentada en Entornos Reales Adversos Por lo tanto el nuevo tamaño de esta representación es: 𝑖𝑖𝑥𝑥𝐿𝐿≤𝑖𝑖𝑥𝑥𝐿𝐿−1+ 1 2 𝑖𝑖𝑦𝑦𝐿𝐿≤𝑖𝑖𝑦𝑦𝐿𝐿−1+ 1 2 Donde nx , ny son el ancho y alto de la nueva representación de la imagen respectivamente. Por lo tanto, calcular el flujo óptico de los puntos de interés en uno cualquiera de los niveles de la estructura piramidal, significa, aplicando una generalización de la Ecuación 3, resolver la función residual: 𝜖𝜖𝐿𝐿(𝑓𝑓𝐿𝐿)=𝜖𝜖𝐿𝐿�𝑓𝑓𝑥𝑥𝐿𝐿,𝑓𝑓𝑦𝑦𝐿𝐿�=� � �𝐼𝐼𝐿𝐿(𝑥𝑥,𝑦𝑦)−𝐽𝐽𝐿𝐿�𝑥𝑥+𝑓𝑓𝑥𝑥𝐿𝐿+𝑓𝑓𝑥𝑥𝐿𝐿,𝑦𝑦+𝑓𝑓𝑦𝑦𝐿𝐿+𝑓𝑓𝑦𝑦𝐿𝐿��2 𝑞𝑞𝑦𝑦 𝐿𝐿+𝑤𝑤𝑦𝑦 𝑞𝑞𝑦𝑦 𝐿𝐿−𝑤𝑤𝑦𝑦 𝑞𝑞𝑥𝑥𝐿𝐿+𝑤𝑤𝑥𝑥 𝑞𝑞𝑥𝑥𝐿𝐿−𝑤𝑤𝑥𝑥 Ecuación 4: Función residual para el cálculo del flujo óptico en el nivel L de la pirámide Donde gL = [gxL y gyL]T es la posición de inicialización del flujo óptico para el nivel L. A continuación el resultado de este cálculo se propaga a próximo nivel L-1 transmitiendo una nueva posición inicial gL-1, se resuelve de nuevo la Ecuación 4, y así sucesivamente. El método iterativo para el cálculo del flujo óptico por Lucas-Kanade tiene por objetivo encontrar el vector dL que minimiza la función ϵL definida en la Ecuación 4. Dado que el punto óptimo se alcanza cuando la primera derivada de ϵ con respecto al vector desplazamiento ʋ es cero, y haciendo aproximaciones por la Taylor de primer orden se llega a la expresión del cálculo óptimo para el vector de flujo óptico: Donde, v Anexo 3: Metodos de Tracking Aplicando un método iterativo al cálculo del vector de flujo óptico se alcanzará el desplazamiento con el margen de error necesario. El pseudo-código que describe el proceso es como sigue: Objetivo: Sea u un punto en la imagen I. Encontrar su localización correspondiente v en la imagen J. Se construye las representaciones piramidales de I y J: {IL}L=0,…,Lm y {JL}L=0,…,Lm. Inicialización de posiciones en la representación piramidal: gLm = [gxLm gyLm]T = [0 0]T for L=Lm to 0 con step de -1 Localización del punto u en la imagen IL: 𝑝𝑝𝐿𝐿= �𝑝𝑝𝑥𝑥 𝑝𝑝𝑦𝑦�𝑇𝑇=𝑞𝑞 2𝐿𝐿 Derivada de IL con respecto a x: 𝐼𝐼𝑥𝑥(𝑥𝑥,𝑦𝑦)=𝐼𝐼𝐿𝐿(𝑥𝑥+1,𝑦𝑦)−𝐼𝐼𝐿𝐿(𝑥𝑥−1,𝑦𝑦) 2 Derivada de IL con respecto a y: 𝐼𝐼𝑦𝑦(𝑥𝑥,𝑦𝑦)=𝐼𝐼𝐿𝐿(𝑥𝑥,𝑦𝑦+1)−𝐼𝐼𝐿𝐿(𝑥𝑥,𝑦𝑦−1) 2 Matriz de gradiente espacial: 𝐺𝐺= ∑ ∑ �𝐼𝐼𝑥𝑥2(𝑥𝑥,𝑦𝑦)𝐼𝐼𝑥𝑥(𝑥𝑥,𝑦𝑦)𝐼𝐼𝑦𝑦(𝑥𝑥,𝑦𝑦) 𝐼𝐼𝑥𝑥(𝑥𝑥,𝑦𝑦)𝐼𝐼𝑦𝑦(𝑥𝑥,𝑦𝑦)𝐼𝐼𝑦𝑦2(𝑥𝑥,𝑦𝑦)� 𝑝𝑝𝑦𝑦+𝑤𝑤𝑦𝑦 𝑝𝑝𝑦𝑦−𝑤𝑤𝑦𝑦 𝑝𝑝𝑥𝑥+𝑤𝑤𝑥𝑥 𝑝𝑝𝑥𝑥−𝑤𝑤𝑥𝑥 Inicialización de la iteración L-K: 𝑖𝑖0= [0 0]𝑇𝑇 for k=1 to K con step de 1 (o hasta ||µk||< umbral de seguridad) Diferencia de imágenes: 𝛿𝛿𝐼𝐼𝑘𝑘(𝑥𝑥,𝑦𝑦)=𝐼𝐼𝐿𝐿(𝑥𝑥,𝑦𝑦)−𝐽𝐽𝑙𝑙�𝑥𝑥+𝑓𝑓𝑥𝑥𝐿𝐿+𝑖𝑖𝑥𝑥𝑘𝑘−1,𝑦𝑦+𝑓𝑓𝑦𝑦𝐿𝐿+𝑖𝑖𝑦𝑦𝑘𝑘−1� Vector de diferencias de imágenes: 𝑏𝑏�𝑘𝑘= � � �𝛿𝛿𝐼𝐼𝑘𝑘(𝑥𝑥,𝑦𝑦)𝐼𝐼𝑥𝑥(𝑥𝑥,𝑦𝑦) 𝛿𝛿𝐼𝐼𝑘𝑘(𝑥𝑥,𝑦𝑦)𝐼𝐼𝑦𝑦(𝑥𝑥,𝑦𝑦)� 𝑝𝑝𝑦𝑦+𝑤𝑤𝑦𝑦 𝑝𝑝𝑦𝑦−𝑤𝑤𝑦𝑦 𝑝𝑝𝑥𝑥+𝑤𝑤𝑥𝑥 𝑝𝑝𝑥𝑥−𝑤𝑤𝑥𝑥 Flujo óptico L-K: 𝜇𝜇𝑘𝑘=𝐺𝐺−1𝑏𝑏�𝑘𝑘 Predicción para la próxima iteración: 𝑖𝑖𝑘𝑘= 𝑖𝑖𝑘𝑘−1+𝜇𝜇𝑘𝑘 end for en k Flujo óptico final en el nivel L: 𝑓𝑓𝐿𝐿= 𝑖𝑖𝑘𝑘 Predicción para el siguiente nivel L-1: 𝑓𝑓𝐿𝐿−1=�𝑓𝑓𝑥𝑥𝐿𝐿−1 𝑓𝑓𝑦𝑦𝐿𝐿−1�𝑇𝑇= 2(𝑓𝑓𝐿𝐿+𝑓𝑓𝐿𝐿) end for en L Vector de flujo óptico final: 𝑓𝑓=𝑓𝑓0+𝑓𝑓0 Localización del punto en J: 𝑖𝑖=𝑝𝑝+𝑓𝑓 Solución: El correspondiente punto está en la localización v de la imagen J. vi Sistema de Realidad Aumentada en Entornos Reales Adversos Este algoritmo declara como características “perdidas” aquellas que se encuentran en dos casos particulares: • El nuevo punto cae fuera de la imagen J. • El “patch” de la imagen alrededor del punto en seguimiento varia demasiado entre las imágenes I y J. 2. Algoritmo de tracking de Kalman. El filtro de Kalman [17] es un algoritmo desarrollado por Rudolf E. Kalman en 1960 que sirve para poder identificar el estado oculto (no medible) de un sistema dinámico lineal, pero sirve además cuando el sistema está sometido a ruido blanco aditivo. La diferencia del filtro de Kalman sobre otros métodos radica en que Kalman es capaz de escoger la ganancia K de realimentación del error de forma óptima cuando se conocen las varianzas de los ruidos que afectan al sistema. En este proyecto se utiliza la implementación detallada en [18]. El filtro de Kalman aborda el problema general de intentar estimar el estado x de un proceso controlado y discreto en el tiempo que está gobernado por la ecuación diferencial estocástica lineal: 𝑥𝑥𝑘𝑘=𝐴𝐴𝑥𝑥𝑘𝑘−1+𝐵𝐵𝑝𝑝𝑘𝑘−1+𝑤𝑤𝑘𝑘−1 con una medida dada por: 𝑧𝑧𝑘𝑘=𝐻𝐻𝑥𝑥𝑘𝑘+𝑖𝑖𝑘𝑘 Las variables aleatorias wk, y vk representan el ruido del proceso y ruido de la medida respectivamente. Se asumen que son independientes, blanco, y de distribución de probabilidad normal: 𝑝𝑝(𝑤𝑤)~𝑁𝑁(0, 𝑄𝑄) 𝑝𝑝(𝑖𝑖)~𝑁𝑁(0, 𝑅𝑅) La covarianza del ruido de proceso, Q y covarianza del ruido de medida, R, se asumen constantes. La matriz A n x n relaciona el estado en el instante anterior k – 1 con el instante actual k, en ausencia de ruido de proceso. La matriz B n x l relaciona las entradas de control opcionales u con el estado x. La matriz H m x n relaciona el estado con la medida zk. Todas se asumen constantes. vii Anexo 3: Metodos de Tracking Se define como estado estimado a priori en el instante k siendo conocido el proceso hasta el instante anterior al k, y el estado estimado a posteriori en el instante k conocida la medida zk respectivamente a: 𝑥𝑥�𝑘𝑘−∈𝑅𝑅𝑖𝑖,𝑥𝑥�𝑘𝑘∈𝑅𝑅𝑖𝑖 El objetivo del filtro de Kalman es encontrar una ecuación que calcule un estado estimado a posteriori como combinación lineal del estado a priori y la diferencia ponderada entre la medida y la predicción de la medida: 𝑥𝑥�𝑘𝑘=𝑥𝑥�𝑘𝑘−+𝐾𝐾(𝑧𝑧𝑘𝑘−𝐻𝐻𝑥𝑥�𝑘𝑘−) 3. Algoritmo de tracking ORB. Este método, descrito en [10], se basa en la combinación de la extracción de características FAST con información de orientación (oFAST) y los descriptores rBRIEF descritos en el Anexo 1. Está diseñado para combinar la ligereza computacional de las características FAST con un método que aporta robustez frente a giros y cambios de escala. Este método añade información de la orientación en los descriptores y utiliza fuerza bruta en el proceso de ‘matching’. Dado que rBRIEF es un patrón binario, se elige Locality Sensitive Hashing [29] como método de búsqueda del vecino más cercano. En LSH, los puntos son almacenados en varias tablas ‘hash’ en diferentes bloques. Dado un descriptor, se calcula el bloque al que pertenece y se empareja por fuerza bruta con los elementos del bloque. Para características binarias, la función ‘hash’ es simplemente un subconjunto de los bits de la firma: el bloque en la tabla ‘hash’ contiene descriptores con subconjuntos de datos comunes de la firma. La distancia utilizada en el emparejamiento es la distancia de Hamming. Se utiliza ‘multi-probe LSH’ [30] que mejora el tradicional LSH mediante búsqueda en los bloques vecinos cuando la búsqueda normal falla. 4. Algoritmo de tracking FFME. Fast Feature-based Motion Estimation [19] es un método de estimación del movimiento robusto al ruido y al problema de la apertura. La selección de los puntos singulares se lleva a cabo mediante la imposición de tres restricciones: • La primera restricción selecciona los puntos cuya magnitud del vector gradiente (‘gradient magnitude’) sea mayor que un cierto umbral de ruido viii Sistema de Realidad Aumentada en Entornos Reales Adversos adaptativo (‘Thgm’), obteniéndose así ‘SPgm’. La magnitud del vector gradiente,‖∇𝐼𝐼(𝑥𝑥,𝑦𝑦)‖=�𝐼𝐼𝑥𝑥2+𝐼𝐼𝑦𝑦2, se calcula utilizando una ‘look-up-table’ que se explicará más adelante. La imagen de la magnitud del vector gradiente se umbraliza por medio de ‘Thgm’, el cual es calculado como una función de la distribución del ruido en la imagen. Asumiendo que se trata de un ruido Gaussiano, la correspondiente imagen de la magnitud del vector gradiente tiene una distribución de Rayleigh [31]: 𝑅𝑅(‖∇𝐼𝐼(𝑥𝑥,𝑦𝑦)‖)=‖∇𝐼𝐼(𝑥𝑥,𝑦𝑦)‖ 𝜎𝜎2𝑆𝑆−‖∇𝐼𝐼(𝑥𝑥,𝑦𝑦)‖2 2𝜎𝜎2 Así, el ‘Thgm’ se calcula como un parámetro de la función de Rayleig, σ: 𝑇𝑇ℎ𝑒𝑒𝑚𝑚=𝜎𝜎�−2ln�𝑃𝑃𝑓𝑓� donde Pf es la proporción aceptable de confianza para los puntos singulares debida a los picos de ruido. La aproximación de Rosin [32] basada en el algoritmo ‘Least Median Squares’ (‘LMedS’) calcula una buena aproximación de σ: 𝜎𝜎�= 0.968 min 𝑗𝑗(𝑓𝑓𝑆𝑆𝑓𝑓𝑖𝑖𝑆𝑆𝑖𝑖∀𝑖𝑖(𝐻𝐻(𝑖𝑖)−𝑗𝑗)2) donde H(i) es el valor del histograma de la magnitud del vector gradiente i, y 0.968 es el factor de corrección relativo a la estimación LMedS de una distribución de Rayleigh no contaminada con σ. • La segunda restricción rechaza de entre los ‘SPgm’ aquellos puntos con baja similitud a puntos esquina, resultando los ‘SPcor’. Los puntos ‘SPgm’ localizados a lo largo de bordes rectos no son fiables para estimar el movimiento dado a que son muy sensibles a pequeños ruidos. Estos puntos se caracterizan por una baja similitud a puntos esquina lo que significa que tienen una curvatura principal a lo largo del borde pero otra muy pequeña en la dirección perpendicular. Las curvaturas principales de un punto son proporcionales a la matriz Hessiana, H, calculada en la posición del punto. Para reducir el coste computacional se adopta la aproximación de Harris y Stephen [24] que calcula el ratio de las curvaturas principales sin calcular los valores propios explícitamente. La traza (‘Tr’) y el determinante (‘Det’) de H se calculan como: 𝑇𝑇𝑟𝑟(𝐻𝐻)=𝐷𝐷𝑥𝑥𝑥𝑥+𝐷𝐷𝑦𝑦𝑦𝑦 ix Anexo 3: Metodos de Tracking 𝐷𝐷𝑆𝑆𝑖𝑖(𝐻𝐻)=𝐷𝐷𝑥𝑥𝑥𝑥𝐷𝐷𝑦𝑦𝑦𝑦+�𝐷𝐷𝑥𝑥𝑦𝑦�2 donde 𝐷𝐷𝑥𝑥𝑥𝑥, 𝐷𝐷𝑦𝑦𝑦𝑦 y 𝐷𝐷𝑥𝑥𝑦𝑦 son los elementos de H que se calculan utilizando un filtro de Sobel como operador derivada: 𝐻𝐻=�𝐷𝐷𝑥𝑥𝑥𝑥 𝐷𝐷𝑥𝑥𝑦𝑦 𝐷𝐷𝑥𝑥𝑦𝑦 𝐷𝐷𝑦𝑦𝑦𝑦� El ratio entre el valor propio más grande y el más pequeño, ‘Reig’, es referido a ‘Tr’ y a ‘Det’: 𝑇𝑇𝑟𝑟(𝐻𝐻)2 𝐷𝐷𝑆𝑆𝑖𝑖(𝐻𝐻)<�𝑅𝑅𝑒𝑒𝑖𝑖𝑒𝑒+ 1�2 𝑅𝑅𝑒𝑒𝑖𝑖𝑒𝑒 =𝑇𝑇ℎ𝑐𝑐𝑐𝑐𝑟𝑟 Como resultado de aplicar la restricción de similitud a puntos esquina, se obtienen los ‘SPcor’. • La selección final, ‘SPfin’, se obtiene aplicando un algoritmo de supresión de no-máximos en el espacio de los puntos esquina que elimina puntos que no son significativos en relación a sus vecinos. Para realizar el cálculo del descriptor se utiliza la aproximación de Lowe que consiste en permitir pequeños desplazamientos en la localización de los valores de los gradientes durante el cálculo de la medida de similaridad. Para realizar el cálculo del descriptor de Lowe se calculan la magnitud del vector gradiente (‘gradient magnitude’) y la dirección del vector gradiente (‘gradient phase’) en la vecindad de los puntos singulares definiendo una ventana cuadrada en su entorno llamada ventana de descripción. La magnitud del vector gradiente se suaviza con una función Gaussiana. La ventana de descripción se divide en Nh x Nh regiones cuadradas compuestas por Np x Np píxeles cada una. Después, se calcula un histograma de orientaciones en cada región. Un histograma de orientaciones es definido como un histograma de direcciones del vector gradiente compuesto por Nd bloques o ‘bins’ donde la contribución de cada ‘bin’ es el valor de la magnitud del vector gradiente. Para evitar que el descriptor varíe abruptamente se aplica una interpolación trilineal. El descriptor, ‘DVhist’, se forma concatenando el ‘bin’ de dirección (‘phase’) de todos los histogramas de orientaciones por filas. La longitud del descriptor es de 𝐿𝐿𝐷𝐷𝐷𝐷=𝑁𝑁ℎ×𝑁𝑁ℎ×𝑁𝑁𝑑𝑑. 𝐷𝐷𝐷𝐷ℎ𝑖𝑖𝑖𝑖𝑡𝑡=�𝐻𝐻𝑖𝑖𝑝𝑝𝑖𝑖(1,1)(1),𝐻𝐻𝑖𝑖𝑝𝑝𝑖𝑖(1,1)(2), … 𝐻𝐻𝑖𝑖𝑝𝑝𝑖𝑖(𝑟𝑟,𝑖𝑖)(𝑖𝑖),…,𝐻𝐻𝑖𝑖𝑝𝑝𝑖𝑖(𝑁𝑁ℎ,𝑁𝑁ℎ)(𝑁𝑁𝑑𝑑)�; 0 < 𝑖𝑖<𝑁𝑁𝑑𝑑, 0 < 𝑗𝑗<𝑁𝑁ℎ x Sistema de Realidad Aumentada en Entornos Reales Adversos donde 𝐻𝐻𝑖𝑖𝑝𝑝𝑖𝑖(𝑟𝑟,𝑖𝑖)(𝑖𝑖) es el i-ésimo ‘bin’ del histograma de orientaciones en las coordenadas (r,s). Puntos singulares en fotogramas consecutivos, 𝑆𝑆𝑃𝑃𝑓𝑓𝑖𝑖𝑖𝑖 𝑖𝑖 y 𝑆𝑆𝑃𝑃𝑓𝑓𝑖𝑖𝑖𝑖 𝑖𝑖+1, son emparejados mediante la distancia Euclidea calculada en el dominio de los descriptores. Considerando pequeños desplazamientos el emparejamiento puede ser restingido a puntos singulares cuya distancia entre ellos sea menor a un umbral, ‘Thdist’. 𝑀𝑀𝑆𝑆𝑖𝑖𝑖𝑖ℎ�𝑝𝑝𝚤𝚤 � � �  ∈𝑆𝑆𝑃𝑃𝑓𝑓𝑖𝑖𝑖𝑖 𝑖𝑖�=min 𝑝𝑝𝚥𝚥 � � � �  ∈𝑆𝑆𝑃𝑃𝑝𝑝𝑗𝑗 𝑖𝑖+1�𝐷𝐷𝐷𝐷𝑓𝑓𝑖𝑖𝑖𝑖(𝑝𝑝𝚤𝚤 � � �  )−𝐷𝐷𝐷𝐷𝑓𝑓𝑖𝑖𝑖𝑖�𝑝𝑝𝚥𝚥 � � �  �� donde || || es la distancia Euclidea y 𝑆𝑆𝑃𝑃𝑝𝑝𝑗𝑗 𝑖𝑖+1=�𝑝𝑝𝑗𝑗∈𝑆𝑆𝑃𝑃𝑓𝑓𝑖𝑖𝑖𝑖 𝑖𝑖+1|�𝑝𝑝𝚤𝚤 � � �  −𝑝𝑝𝚥𝚥 � � �  �<𝑇𝑇ℎ𝑑𝑑𝑖𝑖𝑖𝑖𝑡𝑡�. Se comparan las distancias en el dominio de los descriptores entre el primer y el segundo mejor emparejamientos de un punto para determinar la fiabilidad de cada correspondencia. Una correspondencia correcta debe satisfacer la condición de dFM > 0.51 dSM, donde dFM y dFM son la distancia Euclidea entre los correspondientes vectores descriptores del primer y el segundo mejor emparejamientos respectivamente. Las correspondencias que satisfacen las condiciones previas representan un campo vectorial disperso de movimiento, ‘SVMF’. La estrategia propone el uso de tres ‘look-up-tables’ diferentes para reducir el coste computacional. La primera de ellas se utiliza para calcular la magnitud del vector gradiente. Los índices de acceso son los valores horizontal y vertical del gradiente. La segunda ‘look-up-table’hace lo propio con la dirección del vector gradiente. La última de las ‘look-up-table’ se utiliza para el cálculo de la interpolación lineal. 5. Algoritmos propios basados en emparejamiento. Se han probado diferentes métodos de tracking basado en emparejamientos con la intención de combinar las ventajas de las diferentes características y descriptores estudiados. Los principales métodos combinados son dos: a. Método de tracking p-SIFT. Los puntos SIFT y sus descriptores son las características que mejor resultado han dado en el emparejamiento en las escenas que se han evaluado. Sin embargo computacionalmente son demasiado pesados para su utilización en tiempo real. Se ha probado un sistema basado en el cálculo de xi Anexo 3: Metodos de Tracking Figura 41: Emparejamiento de IR e I0 en situaciones con similares condiciones de iluminación y escala. Método FAST + ZM-SSD. En vista de los resultados pobres de un emparejamiento inicial basado en SSD, y con la misma idea de aprovechar el bajo coste computacional de las características FAST intentando mejorar la robustez de las mismas frente a cambios de iluminación o escala, se ha desarrollado esta metodología. La aplicación del método tiene varias fases: • Se realiza un primer emparejamiento de la ‘IR’ y el ‘I0’ de la secuencia mediante características SIFT y emparejamiento robusto de sus descriptores. • Con este primer registro de imágenes, ya se puede determinar, a través de la homografía correspondiente, una región de búsqueda en ‘I0’ (‘ROII0’). Esta región se corresponderá con la zona ocupada por la imagen que se quiere proyectar sobre la fachada (‘IP’) una vez aplicada la homografía ‘HR_0’ y proyectada sobre ‘I0’. • Sobre la ‘ROII0’ se buscan en la ‘I0’ los puntos característicos FAST (‘puntos_ini’) y sus descriptores basados en SSD y se emparejan con los FAST que se detectan sobre la ‘IR’ (‘puntos_ref’). xviii Sistema de Realidad Aumentada en Entornos Reales Adversos • Estos puntos emparejados correspondientes a la ‘IR’ son los puntos que inicialmente van a ser seguidos en cada uno de los fotogramas de la secuencia y posteriormente actualizados con los de los siguientes fotogramas. • Para el emparejamiento en cada fotograma, se extraen FAST y descriptores SSD (‘puntos_next’) y se utiliza fuerza bruta para emparejar los FAST detectados con los del fotograma anterior (inicialmente los ‘puntos_ref’ y posteriormente los ‘puntos_prev’). • Antes de cada nuevo fotograma los ‘puntos_next’ pasan a ser los ‘puntos_prev’ y la ‘ROII0’ se actualiza con la nueva homografía calculada. Los resultados obtenidos no se comportan demasiado bien frente a oclusiones, tal como se muestra en la Figura 41.Además, el resultado es más lento del que se hubiese esperado. Esto parece ser debido al emparejamiento completo de todos los descriptores. Se descarta su utilización por requisitos de tiempo de procesado. Figura 42: Emparejamiento Inicial mediante SIFT. Tracking entre frames mediante extracción de puntos FAST + ZM-SSD. xix Anexo 4: Base de datos, Métodos y Resultados Base de Datos: Características y tipos de distractores. Para este proyecto se ha dispuesto de una base de datos de 37 videos del entorno del Cubo de la Seo grabados en diferentes condiciones. En la lista siguiente se muestran dichas condiciones de grabación las cuales influyen en el funcionamiento del sistema: 1. Tres resoluciones diferentes: a. R1[ancho, alto] de 1280 x 720. De esta resolución se dispone de 7 videos. b. R2[ancho, alto] de 640 x 480. De esta resolución se dispone de 29 videos. c. R3[ancho, alto] de 720 x 480. De esta resolución se dispone de 1 video. 2. Ocho elementos distractores distintos: a. Inicialización Parcial (IP). Videos en los que la superficie de proyección no aparece inicialmente o aparece solo en parte. Se dispone de 8 ejemplos. b. Iluminación elevada o escasa (IE o IS). En estos videos la imagen se encuentra con mucha o muy poca iluminación. Se dispone de 11 ejemplos. c. Movimiento rápido (MR). Se producen movimientos rápidos o bruscos de la grabación. Se dispone de 8 ejemplos. d. Cambios de Iluminación (CI). Durante el video la iluminación cambia significativamente. Se dispone de 5 ejemplos. e. Cambio de escala (CE). En este caso se distinguen dos distractores diferentes. i. CE1. Durante la grabación del video el tamaño de la superficie de proyección cambia. Esto es debido a que el observador se acerca o se aleja. Se dispone de 1 ejemplos. ii. CE2. El tamaño de las imágenes del video es diferente al tamaño de la ‘Ir’. Se dispone de 27 ejemplos. i Anexo 4: Base de datos, Metodos y Resultados f. Cambio de dirección (CD). Durante la grabación el observador se mueve en una dirección y posteriormente en otra diferente. Se dispone de 3 ejemplos. g. Rotación de la Imagen (RI). Durante la grabación se produce un movimiento de la cámara en torno a la línea de visión, lo que se traduce en una rotación de la superficie de proyección. Se dispone de 6 ejemplos. h. Oclusiones (OC). Uno o varios elementos, objetos o personas pasan por delante de la línea de visión del observador ocluyendo la superficie de proyección en diferentes grados. Se dispone de 10 ejemplos. En la siguiente tabla (Tabla 1) se reflejan cuántos y cuáles de los videos contienen los distractores indicados y en qué grado. Se marca con una ‘X’ si el video contiene el distractor indicado y con ‘XX’ si este distractor es especialmente marcado. Nombre del video CE Resolución IP IE/IS MR CI CE1 CE2 CD RI OC 20131026_114604 1280x720 X X 20131026_114633 1280x720 20131026_114647 1280x720 X 20131026_114701 1280x720 X X 20131026_114708 1280x720 X 20131026_114721 1280x720 X X 20131026_114730 1280x720 20131026_114828 640x480 X 20131026_114841 640x480 X 20131026_114849 640x480 X X 20131026_114858 640x480 X X X 20131026_115006 640x480 X X 20131026_115020 640x480 X X 20131026_115053 640x480 20131026_115106 640x480 CAM00010 640x480 X X CAM00011 640x480 X X X CAM00012 640x480 X X CAM00013 640x480 X X CAM000105 640x480 X X X CAM000106 640x480 X X CAM000107 640x480 X X X CAM000108 640x480 X X X CAM000109 640x480 X X CAM000110 640x480 X X X X X CAM000111 640x480 X X X X X X ii Sistema de Realidad Aumentada en Entornos Reales Adversos CAM000112 640x480 X X CAM000113 640x480 X X X CAM000114 640x480 X X CAM000115 640x480 X XX CAM000116 640x480 X X X X X X XX CAM000117 640x480 X X CAM000118 640x480 X X CAM000119 640x480 X X CAM000120 640x480 X X CAM000121 640x480 X XX VID-20131027-WA0000 720x480 X Nombre del video Resolución IP IE/IS MR CI CE1 CE2 CD RI OC CE Lista 1: Base de datos de videos. Métodos evaluados. Los métodos elegidos para evaluar nuestro sistema son cuatro: 1. Método de tracking por flujo óptico de Lucas-Kanade, KLT. Este método en bucle abierto, utiliza únicamente como método de seguimiento el algoritmo de Lucas-Kanade. Al no disponer de una realimentación de las posiciones, el sistema es bastante inestable con resultados pobres en presencia de distractores. 2. Método de tracking KLT asistido esporádicamente con un reetiquetado completo, REETIQ. Se trata de nuevo de un sistema en bucle abierto, sin realimentación. Es una modificación del anterior en el que, cada cierto número de fotogramas (10 por defecto), el tracking KLT se sustituye por un reetiquetado completo de la imagen. Es decir, cada cierto número de fotogramas, se realiza una búsqueda de puntos SIFT en la imagen y se reemparejan con los puntos SIFT de la ‘Ir’ obtenidos en la secuencia de inicialización. Dado que el método de emparejamiento de SIFT es el que mejores resultados ha demostrado, este sistema es muy fiable y capaz de recuperarse de muchos distractores. Idealmente, reetiquetando en todos los fotogramas sería el método más estable de todos ellos. El coste computacional de este emparejamiento hace inviable su uso en sistemas de tiempo real. Es por este motivo por el que se realiza cada cierto número de fotogramas, aumentando considerablemente el tiempo de cómputo en estos instantes concretos. Los resultados son muy buenos, pero no iii Anexo 4: Base de datos, Metodos y Resultados es aplicable a tiempo real al menos sin algún método que permita reducir el tiempo de proceso en los fotogramas de reetiquetado. 3. Método de tracking KLT con corrección de errores mediante reproyección sobre la ‘Ir’, REPROY. Este método incorpora un lazo de realimentación de las coordenadas. Cada cierto número de fotogramas (10 por defecto) las posiciones de los puntos obtenidas por el tracking KLT se reproyectan sobre la ‘Ir’. En este sistema de coordenadas, se calcula la distancia euclídea media de todos los puntos reproyectados con sus homólogos extraídos inicialmente y se clasifican como no válidos aquellos que superan un umbral. 4. Método de tracking KLT con corrección de errores mediante reproyección sobre la ‘Ir’ y filtrado de puntos en base a la varianza de los desplazamientos, REPROY+FILTRO. Este método también incorpora un lazo de realimentación de las coordenadas. Cada cierto número de fotogramas (10 por defecto) las posiciones de los puntos obtenidas por el tracking KLT se reproyectan sobre la ‘Ir’. En este sistema de coordenadas, se calcula el desplazamiento medio de todos los puntos reproyectados con sus homólogos extraídos inicialmente en ambos ejes X e Y. Se calcula media y varianza de ambos datos, se toma un porcentaje de confianza del 95% y se clasifican como no válidos aquellos cuyo desplazamiento en alguno de los dos ejes no se encuentra en este margen de confianza. Es el método que se ha explicado en el Capítulo 2. Tipos de resultados. Para evaluar el sistema se han clasificado los resultados obtenidos en 3 categorías: 1. Resultado correcto (OK). Se califica como resultado OK, aquellos casos en los que el sistema ha sido capaz de realizar correctamente la proyección de la imagen durante toda la duración del video y sin vibraciones visualmente molestas. 2. Resultado sistema se recupera (SR). Se califica como resultado SR, aquellos casos en los que el sistema ha sufrido dificultades como pueden ser pérdida momentánea del seguimiento, o vibraciones molestas de la proyección, pero ha sido capaz de recuperar el seguimiento y la proyección. 3. Resultado sistema sufre una pérdida completa (KO). Se califica como resultado KO, aquellos casos en los que el sistema ha sufrido dificultades como pueden ser pérdida momentánea del seguimiento, o vibraciones molestas de la iv Sistema de Realidad Aumentada en Entornos Reales Adversos proyección, tan severas que ha sido incapaz de recuperar el seguimiento y la proyección produciéndose una pérdida completa. En la Tabla 2 se muestran el tipo de resultado obtenido en cada uno de los videos en función del método utilizado: Método Nombre del video KLT REETIQ REPROY REPROY+FILTRO 20131026_114604 SR OK OK OK 20131026_114633 OK OK OK OK 20131026_114647 KO OK KO OK 20131026_114701 KO OK KO OK 20131026_114708 SR OK SR OK 20131026_114721 OK OK OK OK 20131026_114730 OK OK OK OK 20131026_114828 OK OK OK OK 20131026_114841 OK OK OK OK 20131026_114849 SR OK OK OK 20131026_114858 SR OK SR OK 20131026_115006 KO OK SR OK 20131026_115020 OK OK OK OK 20131026_115053 OK OK OK OK 20131026_115106 OK OK OK OK CAM00010 KO KO KO KO CAM00011 KO OK KO OK CAM00012 OK OK OK OK CAM00013 OK OK OK OK CAM00105 SR SR SR OK CAM00106 SR OK OK OK CAM00107 OK OK SR OK CAM00108 KO KO KO OK CAM00109 KO KO KO OK CAM00110 KO KO KO KO CAM00111 KO KO KO KO CAM00112 KO KO KO KO CAM00113 KO KO SR OK CAM00114 KO SR KO OK CAM00115 KO KO KO KO CAM00116 KO KO KO KO CAM00117 KO SR KO OK CAM00118 KO KO KO KO CAM00119 KO OK SR OK CAM00120 OK OK KO OK CAM00121 KO KO KO OK VID-20131027-WA0000 KO KO KO OK Tabla 2: Tipo de resultado obtenido por cada video en función del método utilizado en el sistema. v