Repositorio Institucional de Documentos

Santiago Escorihuela Miravet Página 1 RESUMEN: Descriptores globales binarios para reconocimiento de imágenes La visión por computador es la disciplina cuyo objetivo se suele plantear como "que un ordenador pueda ver". La definición de "ver" es bastante compleja, puesto que todos los mecanismos de la visión humana todavía no están bien entendidos. Pero sin duda alguna, uno de los aspectos que involucra la visión humana y que ha sido objeto de estudio por la visión por computador es el reconocimiento de escenas. En dicho problema, un computador recibe una imagen y debe clasificarla según la escena en la que ha sido tomada (parque, oficina, aeropuerto...). Uno de los aspectos más importantes en el reconocimiento de imágenes es la forma de describir el contenido de la imagen. Algebraicamente, un descriptor suele ser un vector de números reales más o menos complejo de extraer a partir de la imagen. Idealmente, dicho descriptor debería contener la información necesaria para clasificar la escena de la imagen. En el estado actual de la técnica, las tasas de reconocimiento visual de escenas son bastante bajas y el problema dista mucho de estar resuelto, por lo que es objeto de investigación. El problema de algunos descriptores es la cantidad de cómputo necesario para extraerlos y evaluarlos, así como la memoria requerida para almacenarlos. Este problema es muy relevante cuando las bases de datos de imágenes adquieren tamaños muy grandes, como Google Imágenes o las imágenes de Facebook. En estas bases de datos, que requieren técnicas avanzadas para la clasificación de las imágenes en función de su contenido, cualquier mejora en tiempo o almacenamiento conlleva un gran ahorro. El objetivo del proyecto es la propuesta de un descriptor binario y global para la clasificación de imágenes. La ventaja de este descriptor respecto a otros es el ahorro en tiempo de cómputo y almacenamiento: Las operaciones binarias pueden realizarse muy rápidamente en los procesadores actuales. Y un número binario ocupa 1 bit, mientras que un real ocupa como mínimo 32 bits. Además de la propuesta, se evalúa el comportamiento del descriptor en una base de datos estándar de visión por computador (SUN database). En dicha evaluación se han explorado diferentes configuraciones del descriptor para encontrar la configuración óptima y poder compararla con un descriptor del estado del arte. En concreto, se ha comparado con el descriptor Tiny images, ya que es el que tiene una configuración más similar. Descriptores globales binarios para reconocimiento de imágenes Página 2 TABLA DE CONTENIDOS 1. INTRODUCCIÓN.................................................................................................................................................... 3 1.1 VISION POR COMPUTADOR ....................................................................................... 3 1.2 RECONOCIMIENTO DE ESCENAS ................................................................................ 4 1.3 OBJETIVOS Y ALCANCE DEL PROYECTO....................................................................... 6 2. DESCRIPTORES ..................................................................................................................................................... 7 2.1 ¿QUÉ ES UN DESCRIPTOR? ......................................................................................... 7 2.2 DESCRIPTORES GLOBALES .......................................................................................... 7 2.3 DESCRIPTORES LOCALES ............................................................................................ 8 2.4 DESCRIPTORES BINARIOS ........................................................................................... 9 2.5 DESCRIPTORES EXISTENTES ........................................................................................ 9 2.5.1 Tiny images: ....................................................................................................... 9 2.5.2 BRIEF: Binary Robust Independent Elementary Features .................................. 10 2.6 G-BRIEF: Descriptor global y binario ......................................................................... 13 2.7 SUAVIZADO DE IMÁGENES: EL FILTRO GAUSSIANO .................................................. 15 3. DATA SET: SUN DATA BASE ....................................................................................................................... 19 4. ALGORITMO DE CLASIFICACIÓN ............................................................................................................. 21 5. MEDIDAS PARA LA EVALUACIÓN DEL RECONOCIMIENTO DE ESCENAS ......................... 23 6. RESULTADOS EXPERIMENTALES ........................................................................................................... 25 6.1 EXPERIMENTO 1: IMAGEN EN BLANCO Y NEGRO O ELECCIÓN DE UN CANAL. .......... 25 6.2 EXPERIMENTO 2: TAMAÑO ÓPTIMO DEL DESCRIPTOR ............................................. 27 6.3 EXPERIMENTO 3: FILTRADO DE IMAGEN .................................................................. 28 6.4 EXPERIMENTO 4: Nº ÓPTIMO DE VECINOS MÁS CERCANOS ..................................... 31 6.5 COMPARACIÓN CON EL ESTADO DEL ARTE (Tiny Images) ......................................... 34 6.6 ESCALABILIDAD DEL DESCRIPTOR G-BRIEF ............................................................... 36 7. CONCLUSIONES ................................................................................................................................................. 38 Santiago Escorihuela Miravet Página 3 1. INTRODUCCIÓN 1.1 VISION POR COMPUTADOR La visión por computador es la rama de la inteligencia artificial cuyo objetivo es hacer “que el ordenador pueda ver”. Pese a que pueda parecer simple, se trata de una tarea muy compleja, que todavía no está resuelta. La visión por computador es una disciplina muy fragmentada que abarca múltiples aplicaciones, a continuación se listan las más importantes:  La detección, segmentación, localización y reconocimiento de ciertos objetos en imágenes (por ejemplo: caras humanas, coches, personas, etc.). (Véase Figura 1)  La evaluación de los resultados (por ejemplo, segmentación y registro).  Registro de diferentes imágenes de una misma escena u objeto, es decir, hacer concordar un mismo objeto en diversas imágenes.  Seguimiento de un objeto en una secuencia de imágenes.  Mapeo de una escena para generar un modelo tridimensional de la escena; este modelo podría ser usado por un robot para navegar por la escena.  Estimación de las posturas tridimensionales de humanos.  Reconocimiento de escenas: Búsqueda de imágenes digitales por su contenido. Figura 1: Ejemplos de detección de objetos: Imagen sup. Izq: Reconocimiento de caras. Imagen sup. dcha: Reconocimiento estático de vehículos. Imagen inf. izq: Reconocimiento de personas. Imagen inf. dcha. Reconocimiento de vehículos en movimiento [1]. Descriptores globales binarios para reconocimiento de imágenes Página 4 1.2 RECONOCIMIENTO DE ESCENAS De todos los objetivos y aplicaciones de la visión por computador indicados en el anterior apartado, el presente proyecto se centra en el reconocimiento de escenas. El reconocimiento de escenas es el proceso de clasificación de imágenes en base a su contenido semántico. Es decir, asignar categorías a las imágenes en función de los objetos o escenas que se muestran en ellas. El ejemplo de aplicación más claro lo encontramos en Google imágenes, en este conocido buscador, al introducir en texto una breve descripción de la imagen (preferiblemente una o dos palabras), nos muestra imágenes cuyo contenido está relacionado con la búsqueda. En la Figura 2 se muestran, a modo de ejemplo, los resultados obtenidos al introducir “playa” en el buscador. Figura 2: Ejemplo de aplicación práctica del reconocimiento de escenas, al introducir la palabra “playa” en el buscador de Google, este nos devuelve imágenes que concuerdan perfectamente con la búsqueda. En el ejemplo de la Figura 2 hemos realizado una búsqueda muy sencilla, ya que la palabra “playa” delimita perfectamente la búsqueda. Sin embargo, cuando realizamos la búsqueda peor delimitada, como la que se muestra en la Figura 3, los resultados obtenidos no son tan precisos. En esta figura se muestran los resultados de introducir “casa de campo” en el buscador, dónde podemos observar la presencia de imágenes cuyo contenido no se corresponde exactamente con lo buscado. En concreto, la tercera imagen de la primera fila (recuadrada en rojo) muestra una panorámica de un lugar costero. Mientras que la tercera imagen de la segunda fila (recuadrada en rojo) muestra una piscina. Esta imperfección en los resultados es debida a que Google basa su clasificación en las palabras que acompañan a la imagen, fijándose mucho menos en el contenido semántico de las imágenes. Lo cual demuestra que el reconocimiento de escenas es una disciplina en desarrollo, en la que aún quedan muchos avances por realizar. Santiago Escorihuela Miravet Página 5 Figura 3: Ejemplo de imperfección en el reconocimiento de escenas. Al introducir la búsqueda “casa de campo” en el buscador de Google imágenes, obtenemos algunas imágenes cuyo contenido se corresponde con la búsqueda, y otras en las que no. Como son las imágenes recuadradas en rojo. Finalmente, en la Figura 4 se muestra un ejemplo ilustrativo de reconocimiento de escenas. En la parte izquierda de la tenemos las nuevas imágenes sin clasificar. El reconocimiento de escenas se encarga de organizarlas en función de su contenido semántico. Es decir, las imágenes 1 y 4 en las que se observan playas, son asignadas a la categoría “playa”, mientras que las imágenes 2 y 3 son asignadas a las categorías “pueblo” y “montaña” respectivamente. Figura 4: Ejemplo ilustrativo de reconocimiento de escenas. A la izquierda tenemos las imágenes de entrada, sin clasificar. El reconocimiento de escenas se encarga de clasificar las imágenes que muestran una playa (1 y 4) en la categoría “playa”, la que muestra una montaña (3) en la categoría “montaña” y la que muestra un pueblo (2) en la categoría “pueblo”. Imágenes sin clasificar playa montaña pueblo Reconocimiento de escenas 1 2 3 4 1 2 3 4 Descriptores globales binarios para reconocimiento de imágenes Página 6 1.3 OBJETIVOS Y ALCANCE DEL PROYECTO El presente proyecto propone un nuevo descriptor de imagen para el reconocimiento de escenas, al que hemos llamado G-BRIEF. Un descriptor de imagen es un conjunto de números ordenados, que contiene información acerca del contenido semántico de la imagen que describe. En la siguiente sección se profundiza en la definición de este concepto. El G-BRIEF ha sido concebido como un descriptor sencillo, cuyo principal objetivo es obtener un descriptor que reduzca al máximo el consumo de recursos en los procesos de reconocimiento de escenas (tanto el tiempo de ejecución, como el espacio necesario para el almacenamiento de los descriptores), manteniendo un nivel de acierto similar, o incluso superior, al estado del arte. Esta sencillez y eficiencia del G-BRIEF hacen que su principal aplicación sea el reconocimiento de escenas en grandes bases de datos, como Google imágenes. En estas bases de datos se realizan búsquedas entre millones de imágenes, por lo que se deben emplear descriptores muy sencillos y eficientes. Una vez propuesto el descriptor, en el presente proyecto, se ha implementado y evaluado el G-BRIEF hasta llegar a su configuración óptima, de modo que su aplicación en el reconocimiento de escenas nos proporcione el mejor ratio de acierto posible. Finalmente, con la intención de probar su valía, hemos comparado nuestro descriptor con el estado del arte. En la sección 2 se profundiza en el concepto de descriptor de imagen, para posteriormente realizar una descripción detallada de los tipos de descriptores que se han utilizado hasta la fecha, con el objetivo de contextualizar la propuesta del G-Brief. En la sección 3 se presenta la base de datos (o data set) que se ha utilizado para evaluar el descriptor, y compararlo con el estado del arte. En la sección 4 se presenta el algoritmo de clasificación empleado, que será el encargado de clasificar los descriptores de las imágenes de la base de datos. En la sección 5 se exponen las medidas de evaluación empleadas. En la sección 6 se exponen los experimentos realizados junto con los resultados más relevantes. Para finalizar, las principales conclusiones alcanzadas por el presente proyecto se exponen en la sección 7. Santiago Escorihuela Miravet Página 7 2. DESCRIPTORES 2.1 ¿QUÉ ES UN DESCRIPTOR? Un descriptor es un conjunto de números ordenados, que contiene información acerca de la imagen que describe. Suelen presentarse en forma de vector, o matriz. La imagen digital, en sí misma, puede considerarse un descriptor. Aunque con un grave problema, su tamaño: Una imagen de 1 Mega pixel (1.000.000 pixeles), teniendo en cuenta que cada pixel ocupa 3 bytes, tiene un tamaño de 3 Megabytes. Por ello se han desarrollado multitud de descriptores, que tratan de condensar la información relevante de la imagen, para su posterior procesamiento. A continuación se van a describir los diferentes tipos de descriptores existentes. 2.2 DESCRIPTORES GLOBALES Los descriptores globales dan información acerca del conjunto de la imagen. Debido a la gran cantidad de pixeles que debe representar el descriptor, la información es muy genérica y nos informa sobre las texturas y formas generales de la imagen. En la Figura 5 observamos un ejemplo ilustrativo de la formación de un descriptor global DG. A partir de una imagen digital (Izquierda) obtenemos el descriptor global (derecha). Figura 5: Ejemplo ilustrativo de la formación de un descriptor global DG (derecha) a partir de una imagen digital (izquierda). Descriptores globales binarios para reconocimiento de imágenes Página 14 Para la formación del descriptor G-BRIEF, en primer lugar, se seleccionan de forma aleatoria las parejas de pixeles ( , ) en la imagen completa I. Tal y como se ha explicado en la sección anterior, el número de parejas elegidas determinara el tamaño del descriptor obtenido: Donde:  : Es el número de parejas de pixeles seleccionadas para la formación del descriptor. A su vez, define el tamaño del descriptor, para el que se eligen potencias binarias como 128, 256, 512, etc.  : son los vectores que contienen el primer y el segundo integrante de las parejas de pixeles procedentes de la región R. Una vez tenemos seleccionadas las parejas de pixeles ), se compara la intensidad del primer pixel de la pareja, , con la del segundo ). Obteniéndose el descriptor de la aplicación de la siguiente regla: Para hasta Donde:  : Es el descriptor G-BRIEF de longitud q  : Es el índice que recorre todas las posiciones del vector descriptor  p( ): Es la intensidad del primer pixel de la pareja  p( ): Es la intensidad del segundo pixel de la pareja Una vez finalizado este bucle, se obtiene el descriptor G-BRIEF que representa la imagen I. Nótese la diferencia con la sección anterior, en la que la imagen I es representada por varios descriptores BRIEF. Santiago Escorihuela Miravet Página 15 Figura 11: Arriba izquierda: Fotografía del Taj Mahal con importante presencia de ruido. Arriba derecha: Ampliación del cielo donde se observan las grandes diferencias entre pixeles contiguos debido al ruido. Abajo izquierda: Fotografía del Taj Mahal sometida a un filtro Gaussiano (tamaño de la máscara 8x8 pixeles,  =0.5). Abajo derecha: Ampliación del cielo de la imagen filtrada, donde se observa una uniformidad absoluta en la intensidad de los pixeles. 2.7 SUAVIZADO DE IMÁGENES: EL FILTRO GAUSSIANO Uno de los principales inconvenientes de los descriptores binarios estriba en el modo en el que se seleccionan los pixeles tenidos en cuenta. Ya sean seleccionados de forma aleatoria, o siguiendo una distribución estadística, nos podemos encontrar con que hemos seleccionado un pixel con una intensidad muy diferente a la de sus vecinos. Ésto puede deberse al ruido presente en la imagen, o al excesivo nivel de detalle. Estos ruidos pueden ser eliminados mediante el filtrado (suavizado) de las imágenes. La aplicación del filtro hace que se suavicen los contrastes entre pixeles contiguos, difuminando la imagen y haciéndola más homogénea. De este modo, evitamos que el pixel seleccionado no sea representativo de la zona de la imagen en la que está situado. En la Figura 11 se observan los resultados obtenidos al aplicar un filtro Gaussiano (tamaño de la máscara 8x8 pixeles, =0.5), sobre una imagen del Taj Mahal con fuerte presencia de ruido. En la parte superior izquierda de la figura observamos la imagen sin filtrar, y a su derecha la ampliación de un trozo de cielo de esta imagen, en la que se observan grandes diferencias de color entre pixeles contiguos. En la parte inferior izquierda de la figura se encuentra la imagen filtrada, y a su derecha, de nuevo tenemos la ampliación de un trozo de cielo. En este caso, se observa una total uniformidad de color entre los pixeles del cielo. Descriptores globales binarios para reconocimiento de imágenes Página 16 Como ya sabemos, el descriptor G-BRIEF compara la intensidad de color entre distintos pixeles para obtener información semántica de la imagen. Nótese que las diferencias de color entre los pixeles del cielo de la imagen de arriba, no se corresponden con la información semántica, ya que todos ellos forman parte del cielo. Este ruido hace que obtengamos descriptores de peor calidad, y por lo tanto dificultan la tarea de reconocimiento de escenas. Obsérvese como en la imagen filtrada todos los pixeles del cielo tienen la misma intensidad de color, de modo que podremos obtener un descriptor que represente mucho mejor el contenido semántico de la imagen. Mediante un filtrado suficientemente agresivo, conseguimos obtener información acerca de las formas y texturas generales de la imagen, desechando los detalles y ruidos que dificultarían el proceso de reconocimiento. De los múltiples filtros existentes, el filtro Gaussiano es el que mejor se adecua a nuestros requerimientos. Matemáticamente el filtrado Gaussiano es la convolución de la imagen con una máscara función de Gauss. Lo que se consigue aplicando un filtrado Gaussiano es reducir los componentes de alta frecuencia de la imagen (filtro de paso bajo). La función Gaussiana que define el filtro bidimensional es la siguiente: Donde:  es la distancia al origen en el eje horizontal.  es la distancia al origen en el eje vertical.  : es la desviación estándar de la función Gaussiana. La aplicación de esta ecuación produce una superficie cuyos contornos son círculos concéntricos al origen con una distribución Gaussiana. Los valores extraídos de esta superficie se utilizan para construir una matriz de convolución que se aplica a la imagen original. Obteniéndose la imagen filtrada como resultado de la convolución. En teoría, se debe tener en cuenta la imagen completa para el cálculo de cada uno de los pixeles. En la práctica, cuando se calcula una aproximación discreta de la función de Gauss, se considera que los pixeles situados a una distancia de más de 3σ son despreciables. A continuación vamos a explicar el funcionamiento del filtrado Gaussiano mediante un ejemplo: Para comenzar, supondremos que tenemos una imagen de tamaño 5x5 pixeles, con los siguientes valores para cada pixel: Santiago Escorihuela Miravet Página 17 81 85 88 84 96 90 86 85 86 94 81 82 89 72 86 80 76 72 76 84 81 83 80 78 71 Tabla 1: Valores de los pixeles de una imagen 5x5 Para la aplicación del filtro Gaussiano debemos ajustar 3 parámetros:  La anchura y la altura de la máscara Gaussiana, que determinaran el número de pixeles contiguos a tener en cuenta para calcular en nuevo valor del pixel sometido al filtro (situado en el centro de la máscara).  , desviación estándar de la función Gaussiana, que determina el peso especifico que se le da al valor del pixel central, así como al resto de los pixeles tenidos en cuenta. En las tablas 2 y 3 se observa la distribución simétrica respecto al centro de valores en la matriz de convolución del filtro Gaussiano. C B C B A B C B C Tabla 2: Esquema filtro Gaussiano 3x3 El valor que tomaran las celdas A, B, C, D y F dependerá de la  elegida (por simplicidad el ejemplo será explicado con el filtro 3x3): Como podemos observar, cuanto mayor es el valor de la desviación estandar , menor es la influencia del propio pixel sometido al filtro y mayor es la de los pixeles contiguos, y por lo tanto más agresivo será el filtro. Del mismo modo que, cuanto mayor tamaño tenga la máscara utilizada, más pixeles influirán en el valor del pixel filtrado, haciendo el filtro más agresivo. A modo de ejemplo, el valor del pixel sombreado de la Tabla 1(valor inicial 89), sometido a un filtro Gaussiano 3x3, =0,5 se obtendría de la siguiente forma: F D C D F D C B C D C B A B C D C B C D F D C D F Tabla 3: Esquema filtro Gaussiano 5x5 Descriptores globales binarios para reconocimiento de imágenes Página 18 Para finalizar, en la Tabla 4 vamos a mostrar el resultado de aplicar un filtro Gaussiano 3x3, =0,5 a la imagen representada en la Tabla 1: 65,811 76,004 77,744 76,687 75,353 78,423 85,776 85,562 85,416 82,452 73,127 82,324 84,779 76,640 76,056 71,369 77,396 75,072 76,417 73,257 64,692 72,995 70,802 69,106 58,415 Tabla 4: Resultado obtenido de la aplicación de un filtro Gaussiano 3x3,  =0,5 sobre la imagen de la tabla1 Dado que el ejemplo ha sido resuelto para una supuesta imagen de dimensiones muy reducidas, en la Figura 12 se muestran los resultados de la aplicación del filtro Gaussiano sobre una imagen procedente del SUN Data Base [4], para distintos valores de tamaño de la máscara Gaussiana y desviación estándar (). Puede observarse como un mayor valor de desviación estándar, así como una máscara más grande generan una imagen filtrada más difuminada. Figura 12: Efectos del filtrado Gaussiano sobre una imagen procedente del SUN Data Base [4].Nótese que un mayor valor de sigma acompañado de una máscara más grande generan una imagen filtrada más difuminada. Santiago Escorihuela Miravet Página 19 3. DATA SET: SUN DATA BASE Una vez definido el descriptor G-BRIEF, es necesario evaluar su funcionamiento, así como comparar los resultados obtenidos con el estado del arte. Para ello necesitamos una base de datos de imágenes sobre la que probar tanto nuestro descriptor como otros descriptores del estado del arte. Y de este modo poder comparar nuestro descriptor con el estado del arte. Existe la posibilidad de crear una base de imágenes estándar (data set) propia, sin embargo, en este proyecto se ha elegido una de las existentes. Ya que este data set nos proporciona muchos resultados del estado del arte con los que compararnos. La base de imágenes estándar (o data set) elegida es la Sun data base, que posee dos secciones diferentes. Una para la detección de objetos y otra para el reconocimiento de escenas, en nuestro caso utilizaremos la segunda de ellas: SUN397 scene benchmark [4]. Esta base de datos contiene un total de 108.754 imágenes, organizadas en 397 categorías (Casa, oficina, playa, etc.). En la Figura 13 se observan algunas de las categorías presentes en la SUN397 scene benchmark [4]. Figura 13: Algunas de las categorías presentes en la base de datos SUN397 scene benchmark [4]. Descriptores globales binarios para reconocimiento de imágenes Página 20 Con la intención de que los experimentos sean lo más representativos e independientes posible, se nos propone utilizar una selección de imágenes organizadas por bloques, tal y como se explica a continuación. En total se proponen diez bloques, de modo que repetiremos cada experimento 10 veces (una por bloque). Cada bloque está formado por 39.700 imágenes, divididas en dos grupos:  19.850 (50 por categoría) Imágenes de entrenamiento (Training), correctamente clasificadas por categoría. Estas imágenes nos sirven para generar el clasificador.  19.850 (50 por categoría) Imágenes de prueba (Test). La categoría de estas imágenes es desconocida, el objetivo es clasificarlas basándonos en el clasificador creado con las imágenes de entrenamiento. No obstante, con el objetivo de poder evaluar los resultados, y saber cuando el clasificador nos proporciona resultados correctos o incorrectos, en éstos data sets también conocemos la categoría de las imágenes de Test. De los datos anteriores se extrae la gran cantidad de operaciones a realizar en cada ejecución, a modo ilustrativo, un solo experimento con el primer bloque de Test y Training conlleva 394.022.500 comparaciones de imágenes. Por lo que la eficiencia del método es crucial para que el tiempo y los recursos de computación sean asequibles. En la Figura 14 se observa un ejemplo ilustrativo del proceso de asignación de categoría a una imagen de Test, mediante la comparación con las imágenes de Training. Nueva Imagen (Test) Playa Montaña Pueblo Imágenes de Training Clasificador ¿A qué categoría pertenece? Playa Figura 14: Ejemplo ilustrativo del proceso de asignación de categoría. La nueva imagen de la izquierda es comparada con las imágenes de Training de la base de datos, dependiendo con que categoría tenga más similitud será asignada a una u otra. Santiago Escorihuela Miravet Página 21 4. ALGORITMO DE CLASIFICACIÓN Una vez definidos tanto los descriptores, como el data set, el siguiente paso es definir el algoritmo que va a servirnos para asignar categoría a las imágenes de Test. El algoritmo empleado en nuestros experimentos es el conocido como k-vecinos más cercanos (K-nearest neighbors). Este algoritmo utiliza los descriptores de las imágenes de entrenamiento (Training), para decidir a qué categoría pertenece la nueva imagen de Test. Sean los descriptores vectores de dimensiones: Donde,  : es el espacio de dimensiones, donde se sitúan los descriptores.  : Es el descriptor de longitud , de la primera imagen de Training.  : Es el descriptor de longitud , de la primera imagen de Test.  : Es la dimensión del vector descriptor, para poder realizar el emparejamiento de descriptores es necesario que los descriptores de imágenes de Test y Training tengan las mismas dimensiones. Para el cálculo de la distancia entre descriptores, el hecho de que los G-BRIEF sean binarios nos proporciona una importante ventaja. Ya que nos permite calcular ésta mediante la distancia de Hamming, evitando calcular la distancia euclídea (mucho más costosa). La distancia de Hamming es el número de bits que difieren entre un descriptor y otro: Donde,  : Es la distancia de Hamming entre un descriptor de Test genérico y uno de Training, ambos de igual longitud p. Descriptores globales binarios para reconocimiento de imágenes Página 22 La distancia de Hamming tiene las siguientes propiedades:   si y solo si  A modo de ejemplo, supongamos que queremos calcular la distancia de Hamming entre dos vectores(A y B) de 4 componentes: Sean: A=(0 1 0 1) y B=(1 1 1 1 ) Por lo que el número de bits que difieren entre A y B son dos. Una vez que conocemos las distancias entre el descriptor de la nueva imagen de Test, y todos los descriptores de las imágenes de Training, tenemos dos posibilidades:  Asignar a la nueva imagen de Test la categoría resultante de tener en cuenta los k vecinos más cercanos.  Asignar a la nueva imagen de Test, la categoría de la imagen de Training más cercana, es decir, mínima distancia de Hamming entre sus descriptores. Este es el caso particular cuando k es igual a 1. Con el objetivo de conseguir los mejores resultados posibles, se tienen en cuenta las distancias ponderadas entre los k vecinos más cercanos, dando mayor peso a los descriptores más cercanos. = Donde,  : es la categoría asignada a la nueva imagen de Test.  es una determinada categoría del conjunto total de categorías V  k: es el número de vecinos más cercanos tenidos en cuenta.  : Es la inversa de la distancia de Hamming entre la imagen de Test y la imagen de Training que ocupa la posición i en el vector de vecinos más próximos.  (Ci,Cj) es una función de selección, que es igual a 1 si las categorías Ci y Cj son la misma, y es cero en cualquier otro caso. Santiago Escorihuela Miravet Página 23  : es la categoría de la imagen de Training que ocupa la posición i , en el vector de vecinos más próximos. Esta ecuación recorre todas las categorías de . Para cada categoría, suma los pesos de los vecinos más próximos ponderados con la inversa de su distancia de Hamming si el vecino más próximo ha elegido dicha categoría (función de selección delta). La categoría cuya suma de pesos sea máxima es la categoría asignada a la imagen de test. 5. MEDIDAS PARA LA EVALUACIÓN DEL RECONOCIMIENTO DE ESCENAS Uno de los métodos más utilizados para valorar la calidad del funcionamiento de un método en el reconocimiento de escenas es la curva de Precision-Recall. Para explicar este método es necesario introducir los términos: Verdadero positivo, Falso positivo, Verdadero negativo y Falso negativo. Los términos positivo y negativo se refieren a la predicción del clasificador, mientras que los términos verdadero y falso se refieren a si esa predicción se corresponde con la realidad. (Véase Tabla 5) Categoría real Categoría predicha por el clasificador Verdadero positivo (tp) Predicción: Positivo Realidad: Positivo Falso positivo(fp) Predicción: Positivo Realidad: Negativo Falso negativo (fn) Predicción: Negativo Realidad: Positivo Verdadero negativo ( tn) Predicción: Negativo Realidad: Negativo Tabla 5: Definición de: tp, fp, tn, fn. En este contexto se define la Precision como el porcentaje de verdaderos positivos entre el total de los positivos predichos. Recall se define como el porcentaje de verdaderos positivos, entre el total de los positivos reales. Descriptores globales binarios para reconocimiento de imágenes Página 30 Figura 18: Resultados del experimento de filtrado óptimo. En el gráfico se representa el número de aciertos (promedio de los 10 bloques), para los diferentes niveles de filtrado Gaussiano. Los resultados del experimento demuestran lo que ya predecíamos en la sección 2.7. Como puede observarse en la Figura 18, cuando la imagen no es filtrada o se realiza un pequeño filtrado, los resultados no son óptimos, esto es debido a la presencia de ruido y excesivos detalles en la imagen. Sin embargo, cuando se realiza un filtro excesivamente agresivo (Máscara 150x150, σ=150) los resultados tampoco son buenos, debido a que el filtrado ha difuminado demasiado la imagen, perdiendo información importante. Por lo tanto, y a tenor de los resultados, el filtrado óptimo ha de tener un valor intermedio entre estos valores extremos. En este caso, como se puede apreciar en el gráfico de la Figura 18, el filtro Gaussiano que proporciona mejores resultados es el que tiene dimensiones de máscara 70x70 pixeles, y desviación estandar σ=50. En concreto, los resultados obtenidos para este filtrado son un 26,4% mejores que los obtenidos a partir de las imágenes sin filtrar. 230,7 239,4 255,5 268,5 265,6 273,7 286,8 291,7 284,7 282,8 269,2 266,5 0 50 100 150 200 250 300 350 FILTRO UTILIZADO GRÁFICO 3: FILTRADO ÓPTIMO Santiago Escorihuela Miravet Página 31 6.4 EXPERIMENTO 4: Nº ÓPTIMO DE VECINOS MÁS CERCANOS En la sección 4 se ha presentado el algoritmo de clasificación empleado, para el que debemos elegir el número de vecinos más cercanos que vamos a tener en cuenta. Con la intención de tomar esta decisión, se han realizado múltiples experimentos para diferentes valores de (k: nº de vecinos más cercanos tenidos en cuenta). Dado que el número de vecinos más cercanos elegido y el tamaño del descriptor se consideran parámetros independientes en el reconocimiento de escenas, este experimento se ha realizado únicamente con descriptores G-BRIEF de 128 bits. Sin embargo, las conclusiones obtenidas son válidas para cualquier tamaño de descriptor. En la Tabla 9 se presentan los resultados obtenidos para los diferentes valores de k (nº de vecinos más cercanos tenidos en cuenta). k=1 Test 1 Test 2 Test 3 Test 4 Test 5 Test 6 Test 7 Test 8 Test 9 Test 10 Promedio Nº aciertos 194 173 173 172 194 171 169 175 182 189 179,2 % de éxito 0,977% 0,872% 0,872% 0,866% 0,977% 0,861% 0,851% 0,882% 0,917% 0,952% 0,903% k=3 Nº aciertos 197 177 176 169 193 176 175 174 182 186 180,5 % de éxito 0,992% 0,892% 0,887% 0,851% 0,972% 0,887% 0,882% 0,877% 0,917% 0,937% 0,909% k=5 Nº aciertos 196 179 179 172 196 179 184 179 186 191 184,1 % de éxito 0,987% 0,902% 0,902% 0,866% 0,987% 0,902% 0,927% 0,902% 0,937% 0,962% 0,927% k=10 Nº aciertos 217 185 177 171 200 180 182 182 204 192 189 % de éxito 1,093% 0,932% 0,892% 0,861% 1,008% 0,907% 0,917% 0,917% 1,028% 0,967% 0,952% k=15 Nº aciertos 211 188 168 196 193 194 198 195 222 189 195,4 % de éxito 1,063% 0,947% 0,846% 0,987% 0,972% 0,977% 0,997% 0,982% 1,118% 0,952% 0,984% k=20 Nº aciertos 205 186 180 198 209 183 192 205 224 200 198,2 % de éxito 1,033% 0,937% 0,907% 0,997% 1,053% 0,922% 0,967% 1,033% 1,128% 1,008% 0,998% k=25 Nº aciertos 213 202 182 203 212 196 192 202 228 206 203,6 % de éxito 1,073% 1,018% 0,917% 1,023% 1,068% 0,987% 0,967% 1,018% 1,149% 1,038% 1,026% k=30 Nº aciertos 202 199 182 209 218 194 208 202 234 205 205,3 % de éxito 1,018% 1,003% 0,917% 1,053% 1,098% 0,977% 1,048% 1,018% 1,179% 1,033% 1,034% k=40 Nº aciertos 207 204 195 215 240 218 216 206 233 225 215,9 % de éxito 1,043% 1,028% 0,982% 1,083% 1,209% 1,098% 1,088% 1,038% 1,174% 1,134% 1,088% Descriptores globales binarios para reconocimiento de imágenes Página 32 k=50 Nº aciertos 222 209 196 201 244 219 239 227 239 230 222,6 % de éxito 1,118% 1,053% 0,987% 1,013% 1,229% 1,103% 1,204% 1,144% 1,204% 1,159% 1,121% k=60 Nº aciertos 204 208 191 200 241 218 223 226 234 224 216,9 % de éxito 1,028% 1,048% 0,962% 1,008% 1,214% 1,098% 1,123% 1,139% 1,179% 1,128% 1,093% k=70 Nº aciertos 217 208 206 210 247 224 224 235 236 230 223,7 % de éxito 1,093% 1,048% 1,038% 1,058% 1,244% 1,128% 1,128% 1,184% 1,189% 1,159% 1,127% k=80 Nº aciertos 225 218 206 229 242 231 207 239 226 247 227 % de éxito 1,134% 1,098% 1,038% 1,154% 1,219% 1,164% 1,043% 1,204% 1,139% 1,244% 1,144% k=90 Nº aciertos 225 220 207 215 228 225 216 234 221 229 222 % de éxito 1,134% 1,108% 1,043% 1,083% 1,149% 1,134% 1,088% 1,179% 1,113% 1,154% 1,118% k=100 Nº aciertos 239 232 211 221 233 223 221 248 229 233 229 % de éxito 1,204% 1,169% 1,063% 1,113% 1,174% 1,123% 1,113% 1,249% 1,154% 1,174% 1,154% k=125 Nº aciertos 228 235 220 220 247 218 228 231 218 256 230,1 % de éxito 1,149% 1,184% 1,108% 1,108% 1,244% 1,098% 1,149% 1,164% 1,098% 1,290% 1,159% k=150 Nº aciertos 240 237 203 212 243 238 227 221 211 244 227,6 % de éxito 1,209% 1,194% 1,023% 1,068% 1,224% 1,199% 1,144% 1,113% 1,063% 1,229% 1,147% Tabla 9: Resultados obtenidos para diferentes valores de K en el método K vecinos más cercanos Por motivos de claridad, en la Figura 19 se muestra una selección de los resultados presentes en la Tabla 9. En dicha figura se observa cómo a partir de k=50 la mejora en los resultados obtenidos no está clara. En la Tabla 10 se ha incluido un resumen de los resultados de este experimento, en dicha tabla se observa como los aciertos promedio de los 10 bloques tiene una clara tendencia ascendente conforme va aumentando k, hasta que llegamos a k=50, dónde se considera que la relación coste/ beneficio de aumentar el valor de k, no es rentable. Estos resultados pueden visualizarse de forma gráfica en la Figura 20. Todo lo anterior demuestra que el valor óptimo de k es =50. Este valor es dependiente del número de categorías en las que se clasifiquen las imágenes (en nuestro caso 397 categorías), por lo que para un diferente número de categorías, será diferente. Santiago Escorihuela Miravet Página 33 0 50 100 150 200 250 0 3 5 10 15 20 25 30 40 50 60 70 80 90 100 125 150 GRÁFICO 4.2: k-VECINOS MÁS CERCANOS Figura 19: Gráfico de barras que representa los resultados para diferentes valores de k( k-vecinos más cercanos) 0 50 100 150 200 250 300 1 2 3 4 5 6 7 8 9 10 GRÁFICO 4.1: K- VECINOS MÁS CERCANOS k=1 k=5 k=10 k=20 k=30 k=50 k=70 k=100 k=125 k=150 k Aciertos promedio (10 bloques) 1 179,2 3 180,5 5 184,1 10 189 15 195,4 20 198,2 25 203,6 30 205,3 40 215,9 50 222,6 60 216,9 70 223,7 80 227 90 222 100 229 125 230,1 150 227,6 Tabla 10: Tabla resumen de aciertos promedio frente a los diferentes valores de k. Figura 20: Tendencia de los resultados promedio para diferentes valores de k (kvecinos más cercanos) Descriptores globales binarios para reconocimiento de imágenes Página 34 6.5 COMPARACIÓN CON EL ESTADO DEL ARTE (Tiny Images) Una vez obtenidos los resultados para nuestro descriptor G-BRIEF, nos hemos comparado con el estado del arte. Para ello se ha elegido el Tiny images, ya que es un descriptor orientado a bases de datos de gran tamaño y por tanto necesidades computacionales y de almacenamiento muy bajas. Uno de los parámetros utilizados para comprar los diferentes descriptores es la curva de Precision-Recall, explicada en la sección 5. Los resultados de dicha curva para ambos descriptores se muestran en la Figura 21, en la que se observa un “empate técnico” entre ambos descriptores. Cabe destacar, que aunque la curva Precision-Recall sea prácticamente igual para ambos descriptores, en cuanto a coste y espacio de almacenamiento el G-BRIEF es más eficiente, y por lo tanto se considera mejor alternativa. Figura 21: Comparativa de la curva precision/recall del descriptor G-BRIEF y el Tiny images. La curva de Precision-Recall es un buen método para la comparación de descriptores, pero no el único. A continuación, en la Tabla 11 se muestra un resumen de los resultados obtenidos para las tres mejores configuraciones del G-BRIEF, así como los resultados obtenidos para el Tiny images. En dicha tabla se comparan los aciertos obtenidos con cada uno de estos descriptores, obsérvese que la configuración del descriptor G-BRIEF que mejores resultados proporciona es la que se deduce de los experimentos presentados anteriormente. Los datos de la Tabla 11 pueden visualizarse de forma gráfica en la Figura 22, en la que se observa claramente que los resultados obtenidos por el descriptor G-BRIEF son mejores que 0 0,005 0,01 0,015 0,02 0,025 0 0,2 0,4 0,6 0,8 1 1,2 PRECISION RECALL CURVA PRECISIONRECALL G-BRIEF 1024bits Tiny Images Santiago Escorihuela Miravet Página 35 los obtenidos mediante el descriptor Tiny images. En concreto el descriptor G-BRIEF obtenido a partir de la imagen filtrada proporciona resultados un 17,7% mejores que el Tiny images. Test 1 Test 2 Test 3 Test 4 Test 5 Test 6 Test 7 Test 8 Test 9 Test 10 PROMEDIO DE ACIERTOS G-BRIEF 1024 bits Nº aciertos 284 281 283 266 284 295 303 262 313 300 287,1 % de éxito 1,43% 1,42% 1,43% 1,34% 1,43% 1,49% 1,53% 1,32% 1,58% 1,51% 1,446% G-BRIEF 1024: FILTRO 70X70, s=50, k=1 Nº aciertos 355 306 340 312 355 353 347 355 347 385 345,5 % de éxito 1,788% 1,542% 1,713% 1,572% 1,788% 1,778% 1,748% 1,788% 1,748% 1,940% 1,741% G-BRIEF 1024: FILTRO 70X70, s=50, k=50 Nº aciertos 355 366 352 329 363 380 351 339 354 355 354,4 % de éxito 1,788% 1,844% 1,773% 1,657% 1,829% 1,914% 1,768% 1,708% 1,783% 1,788% 1,785% TINY IMAGES Nº aciertos 325 276 270 269 306 277 282 257 304 276 284,2 % de éxito 1,637% 1,390% 1,360% 1,355% 1,542% 1,395% 1,421% 1,295% 1,531% 1,390% 1,432% Tabla 11: Resumen de los resultados obtenidos para las tres mejores configuraciones del G-BRIEF y el Tiny images. Figura 22: Resumen de los resultados obtenidos para las tres mejores configuraciones del G- BRIEF y el Tiny images 0 50 100 150 200 250 300 350 400 PROMEDIO DE ACIERTOS ESTADO DEL ARTE G-BRIEF 1024 bits G-BRIEF 1024 bits: FILTRO 70X70, s=50, k=1 G-BRIEF 1024 bits: FILTRO 70X70, s=50, k=50 TINY IMAGES Descriptores globales binarios para reconocimiento de imágenes Página 36 6.6 ESCALABILIDAD DEL DESCRIPTOR G-BRIEF En este apartado se prueban los resultados de escalabilidad del descriptor G-BRIEF. Como se puede observar en la Tabla 12, el descriptor G-BRIEF mejora sus prestaciones cuanto mayor número de categorías de clasificación tenemos. En esta tabla se comparan los porcentajes de acierto obtenidos mediante el uso del descriptor G-BRIEF con los que se obtendrían de un modo aleatorio. descriptor G-BRIEF 1024 bits Filtro 70x70, =50 nº categorias 397 150 50 10 5 3 2 nº imag total 19850 7500 2500 500 250 150 100 aciertos % aciertos % aciertos % aciertos % aciertos % aciertos % aciertos % Test 1 355 1,79% 252 3,36% 187 7,5% 128 25,6% 107 42,8% 70 46,7% 61 61% Test 2 306 1,54% 233 3,11% 179 7,2% 118 23,6% 100 40,0% 76 50,7% 66 66% Test 3 340 1,71% 234 3,12% 173 6,9% 112 22,4% 105 42,0% 70 46,7% 59 59% Test 4 312 1,57% 242 3,23% 150 6,0% 120 24,0% 88 35,2% 66 44,0% 52 52% Test 5 355 1,79% 229 3,05% 171 6,8% 117 23,4% 100 40,0% 76 50,7% 59 59% Test 6 353 1,78% 254 3,39% 170 6,8% 123 24,6% 107 42,8% 79 52,7% 72 72% Test 7 347 1,75% 253 3,37% 185 7,4% 132 26,4% 112 44,8% 81 54,0% 66 66% Test 8 355 1,79% 223 2,97% 158 6,3% 104 20,8% 105 42,0% 75 50,0% 60 60% Test 9 347 1,75% 244 3,25% 155 6,2% 123 24,6% 107 42,8% 88 58,7% 69 69% Test 10 385 1,94% 229 3,05% 191 7,6% 116 23,2% 99 39,6% 66 44,0% 61 61% Promedio 345,5 1,74% 239,3 3,19% 171,9 6,9% 119,3 23,9% 103 41,2% 74,7 49,8% 62,5 63% Aleatorio 50 0,252% 50 0,667% 50 2,0% 50 10% 50 20% 50 33% 50 50% G-BRIEF/ Aleatorio 6,91 4,79 3,44 2,39 2,06 1,49 1,25 Tabla 12: Resultados de escalabilidad del descriptor G-BRIEF Los resultados presentados en la Tabla 12 son representados en la Figura 23. Si nos fijamos en los resultados obtenidos cuando se deben clasificar las imágenes en 397 categorías (1,74%) pueden parecer muy malos. Sin embargo, si lo comparamos con los resultados que se producirían de un modo aleatorio, los resultados del G-BRIEF son 7 veces mejores, con un consumo de recursos muy reducido. Como podemos intuir, el descriptor G-BRIEF va a proporcionarnos resultados muy satisfactorios cuando el número de categorías sea muy elevado. Algo que ningún descriptor del estado del arte puede igualar con un consumo de recursos tan escaso. Santiago Escorihuela Miravet Página 37 Figura 23: Resultados de escalabilidad del descriptor G-BRIEF 0,00 1,00 2,00 3,00 4,00 5,00 6,00 7,00 8,00 0 100 200 300 400 500 Nº DECATEGORIAS % G-BRIEF/ALEATORIO Descriptores globales binarios para reconocimiento de imágenes Página 38 7. CONCLUSIONES En este proyecto se ha propuesto un nuevo descriptor, el descriptor G-BRIEF, que combina lo mejor de los descriptores globales y los binarios. Este descriptor ha sido evaluado hasta hallar su configuración óptima. Esta configuración óptima es un descriptor de 1024 bits, con un filtrado Gaussiano previo de las imágenes. Se ha demostrado que el filtrado que proporciona mejores resultados es el que emplea una máscara Gaussiana de 70x70 pixeles y una desviación estándar =50. El algoritmo de emparejamiento que se ha empleado es el kvecinos más cercanos, para el que se ha demostrado que el valor óptimo de vecinos (k) tenidos en cuenta es de cincuenta. El descriptor G-BRIEF, proporciona un ratio de reconocimiento similar, incluso superior, al descriptor más similar del estado del arte: Tiny images. Con un consumo de recursos (almacenamiento y procesamiento) en el proceso de reconocimiento que puede llegar a ser 8 veces inferior [3]. Como trabajo futuro sería interesante probar el descriptor G-BRIEF en la base de datos Tiny images (de 80 millones de imágenes), y así, comprobar los resultados de escalabilidad de este proyecto. Santiago Escorihuela Miravet Página 39 REFERENCIAS: [1] High Detection-rate Cascades for Real-Time Object Detection. Hamed Masnadi-Shirazi and Nuno Vasconcelos Proceedings of IEEE International Conference on Computer Vision(ICCV), Rio de Janeiro, Brazil, 2007. [2] 80 million tiny images: a large dataset for non-parametric object and scene recognition. Antonio Torralba, Rob Fergus y William T. Freeman. Journal: IEEE Transactions on Pattern Analysis and Machine Intelligence Volume 30 Issue 11, November 2008. [3] BRIEF: Computing a Local Binary Descriptor Very Fast M. Calonder, V. Lepetit, M. Ozuysal, T. Trzcinski, C. Strecha, and P. Fua IEEE Transactions on Pattern Analysis and Machine Intelligence 2012 [4] SUN Database: Large-scale Scene Recognition from Abbey to Zoo Jianxiong Xiao , James Hays, Krista, A. Ehinger, Aude Oliva y Antonio Torralba IEEE Conference on Computer Vision and Pattern Recognition (CVPR2010)