Estudio comparativo de medidas de distancia para histogramas en problemas de reidentificación

UNIVERSIDAD DE LAS PALMAS DE GRAN CANARIA M´aster Oficial en Sistemas Inteligentes y Aplicaciones Num´ericas en Ingenier´ıa Estudio comparativo de medidas de distancia para histogramas en problemas de reidentificaci´on Pedro Antonio Mar´ın Reyes Tutores: Jos´e Javier Lorenzo Navarro Modesto Fernando Castrill´on Santana Enero de 2015 No dejes para ma˜nana lo que puedas hacer hoy 1 2 Agradecimientos A mi familia que me ha tenido que aguantar con mis jaquecas y comentarios de conceptos que desconoc´ıan, pero que poco a poco han llegado a comprender ciertos puntos. Como tambi´en a mi pareja que me ha apoyado en todo momento con las decisiones que he tomado y el inter´es que ha mostrado cuando le he ense˜nado un sinf´ın de gr´aficas y tablas. A mis amigos a los cuales les he expuesto el presente trabajo y hemos intercambiado experiencias de nuestros proyectos. Como tambi´en me gustar´ıa agradecer a cualquier posible lector que se muestre congratulado con el presente trabajo que ha requerido su esfuerzo y dedicaci´on. Y por ´ultimo y no menos importante a mis tutores, por la ayuda ofrecida y la buena planificaci´on de las reuniones, que han resultado bastante ´utiles para llevar a cabo el trabajo, ya que nos reuniamos en conjunto para contrastar informaci´on, ver posibles erratas y compartir toda la informaci´on posible entre nosotros. Cabe decir que son muy buenos gestores y se respira un buen ambiente en el grupo de trabajo. 3 4 ´ Indice general 1. Objetivos 13 2. Introducci´on 15 2.1. Visi´on por computador . . . . . . . . . . . . . . . . . . . . . . 15 2.2. Reidentificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3. Espaciodecolor.......................... 18 2.4. Histograma ............................ 21 2.5. Distancia entre histogramas . . . . . . . . . . . . . . . . . . . 22 3. Metodolog´ıa 25 3.1. Basesdedatos........................... 25 3.2. Dise˜no del experimento . . . . . . . . . . . . . . . . . . . . . . 27 3.3. Divisi´on mediante franjas . . . . . . . . . . . . . . . . . . . . . 29 3.4. Implementaci´on.......................... 30 4. Resultados 33 4.1. Espaciodecolor.......................... 34 4.2. N´umerodebins.......................... 35 4.3. N´umero de franjas . . . . . . . . . . . . . . . . . . . . . . . . 37 4.4. Otras caracter´ısticas analizadas . . . . . . . . . . . . . . . . . 39 5. Conclusiones y l´ıneas futuras 43 Bibliograf´ıa 46 Glosario 47 A. Anexo 49 5 6´ INDICE GENERAL ´ Indice de figuras 2.1. Procesos en sistema de visi´on por computador. . . . . . . . . . 15 2.2. Im´agenes de individuos captadas por dos c´amaras diferentes. . 16 2.3. ´ Areas de conocimiento en reidentifiaci´on. Tomada de [Vezzani et al., 2013]. 17 2.4. Ejemplo de espacios de color. RGB y HSV. . . . . . . . . . . . 18 2.5. AConjunto de valores; H(A) Histograma correspondiente a A. 21 2.6. Comparaci´on de histogramas. (A) Corresponde con la comparaci´on de dos histogramas y (B) Corresponde a la comparaci´on de dos histogramas similares a (A) pero con un bin m´as que tienevalornulo........................... 23 3.1. Grupo de bases de datos. Tomada de [DENG et al., 2014]. . . 26 3.2. Curva CMC. Eje de abscisas representa posici´on de reidentificaci´on y el eje de ordenadas representa la probabilidad de aparecer el probe en la posici´on correspodiente. . . . . . . . . 28 3.3. Estructura del individuo. . . . . . . . . . . . . . . . . . . . . . 29 3.4. Etiquetado de imagen. (A) representa el identificador del probe y (B) hace referencia n´umero de imagen tomada para el probe. ............................... 30 4.1. ´ Area CMC para distancias y espacio color. . . . . . . . . . . . 35 4.2. ´ Area CMC para distancias y n´umero de bins. . . . . . . . . . 36 4.3. ´ Area CMC para distancias y n´umero de franjas. . . . . . . . . 38 4.4. Rendimiento en horas para n´umero de bins y n´umero de franjas. 39 4.5. ´ Area CMC para n´umero de franjas y n´umero de bins. . . . . . 40 4.6. ´ Area CMC para espacio de color y n´umero de bins. . . . . . . 41 4.7. ´ Area CMC para espacio de color y n´umero de franjas. . . . . . 42 7 14 Objetivos Cap´ıtulo 2 Introducci´on En este apartado lo que se pretende es dar a conocer ciertas nociones que se van a ir argumentando a lo largo del trabajo. Donde se explicar´an de forma detallada y concisa los conceptos que vamos a abarcar. 2.1. Visi´on por computador De acuerdo a [Jim´enez, 2000], visi´on por computador es un ”proceso de extracci´on de informaci´on del mundo f´ısico a partir de im´agenes, utilizando para ello un computador”, v´ease figura 2.1. Este ´area pretende construir sistemas que sean capaces de emular al sistema de visi´on humano. Los principales problemas a los que est´an afectados un proceso de visi´on por computador son la iluminaci´on de la escena, las caracter´ısticas del hardware de obtenci´on y la forma de los objetos. Figura 2.1: Procesos en sistema de visi´on por computador. 15 16 Introducci´on Este Trabajo de Fin de M´aster (TFM) se centra en concreto en la reidentifiaci´on. 2.2. Reidentificaci´on Actualmente gracias al abaratamiento de los sensores y de procesadores para c´amaras de v´ıdeo, en las ciudades o sitios p´ublicos como en centros comerciales se est´an extendiendo las redes de c´amaras de videovigilancia. Estas c´amaras pueden ser ´utiles a la hora de localizar personas desaparecidas, el seguimiento de ladrones, detecci´on de accidentes, seguimiento de medios de transporte, etc. Los escenarios pueden ser muy variados, se podr´ıan dividir en zonas de interior y zonas de exterior como un hospital o autopista respectivamente. Estos sistemas de vigilancia acumulan gran cantidad de informaci´on la cual se podr´ıa extraer. La reidentificaci´on manual puede ser inviable en ciertos escenarios, por eso surgen sistemas inteligentes para la reidentificaci´on [Wang, 2013]. Figura 2.2: Im´agenes de individuos captadas por dos c´amaras diferentes. De acuerdo a [Gong et al., 2014], el concepto de reidentificaci´on se define como la tarea fundamental para un sistema de c´amaras distribuidas o no, con las que se realiza una asociaci´on de las personas a trav´es de las im´agenes captadas por ´estas en cierta localizaci´on y tiempo. A continuaci´on se van a definir dos conceptos que posteriormente se van a emplear, en el ´ambito de la reidentificaci´on. Se denomina probe al individuo identificado que se pretende reidentificar. Por otro lado, gallery alude al conjunto de individuos donde se va a realizar la b´usqueda. Como se puede apreciar en la ecuaci´on (2.1), se define formalmente la tarea de reidentificaci´on, donde Tes el individuo 2.2. REIDENTIFICACI ´ ON 17 reidentificado del gallery τ={T1, ..., Tn}buscando probe Q.D() es una medida de similitud. T=argminTiD(Ti, Q), Ti∈τ(2.1) La figura 2.2 muestra ejemplos de pares de im´agenes del mismo individuo captadas en dos c´amaras diferentes en distintos instantes de tiempo. Esto provoca que las im´agenes est´en afectadas por ruido proveniente del entorno, ya sea brillo o sombras, por el ´angulo en el que se haya captado las im´agenes, por el desplazamiento del individuo o por el tama˜no en el que se captur´o las im´agenes. El factor tiempo afecta a los resultados, se obtienen mejores resultados cuando las im´agenes son temporalmente pr´oximas. Al no haber mucha diferencia de tiempo, la probabilidad de que la persona haya cambiado de apariencia es menor. Figura 2.3: ´ Areas de conocimiento en reidentifiaci´on. Tomada de [Vezzani et al., 2013]. Existen diferentes par´ametros que se deben considerar en un problema de reidentificaci´on, ver figura 2.3. Est´a ordenada por tipolog´ıa, representada por cada dimensi´on de la figura, dentro de esta se encuentra cada elemento ordenado de menor complejidad a mayor. A la hora de abordar el problema de reidentificaci´on hay que tener en cuenta ciertas caracter´ısticas del problema que se va a tratar. La primera constar´ıa de la configuraci´on de la c´amara, el formato en el que se recoge la informaci´on y la situaci´on de las c´amaras. Pudiendo usarse una sola c´amara, m´ultiples c´amaras que est´an solapadas, c´amaras calibradas y sin solapamiento o en el peor de los casos c´amaras sin calibrar y sin solapamiento. Otra caracter´ıstica a tener en cuenta es si se posee un amplio conjunto de probe, pudiendo ser este el caso m´as simple a la hora de realizar reidentificaci´on porque por ejemplo 18 Introducci´on se podr´ıa tomar valores promedio de las capturas del probe. Si se dispone de una sola imagen del probe y una imagen de cada persona en el gallery, se estar´ıa en un escenario single shot, mientras que si se dispone de conjuntos de im´agenes obtenidas de un video tanto en el probe como en el gallery, el escenario ser´ıa multiple shot. Otra caracter´ıstica fundamental es el escenario donde se aplica la reidentificaci´on, no es lo mismo obtener las descripciones de una imagen en un espacio cerrado donde las im´agenes capturadas son a corta distancia que en la calle donde el tama˜no de la persona en la imagen es menor y no nos permitir´ıa obtener de forma adecuada las descripciones del individuo. A la hora de describir los individuos hay que tener en cuenta los descriptores que se calculan de los individuos. As´ı, estos descriptores pueden basarse en color, forma, textura, posici´on o descripciones biom´etricas. Este trabajo se enmarca en la dimensi´on del conjunto de caracter´ısticas, m´as espec´ıficamente en descriptores basados en color [Satta, 2013], donde existen m´ultiples espacios de color con sus cualidades respecto a la luminancia ycrominancia. 2.3. Espacio de color Seg´un el libro [Acharya and Ray, 2005], hay una serie de espacios de color, los cuales poseen su propio sistema de coordenadas de color, cada punto en el sistema de coordenadas representa un color diferente. Existe una amplia variedad de modelos de color, poseen caracter´ısticas que los hacen ´utiles en determinados tipos de problemas. Figura 2.4: Ejemplo de espacios de color. RGB y HSV. Los espacios de color que se suelen emplear en el ´ambito de visi´on por computador son: 2.3. ESPACIO DE COLOR 19 RGB (Red Green Blue) : Es el t´ıpico espacio de color que se encuentra en cualquier dispositivo, lo conforman 3 canales (rojo, verde y azul) donde la luminancia y la crominancia no se encuentran por separado, lo ideal ser´ıa poder desacoplar el factor de iluminaci´on del color para analizar las im´agenes. Normalmente cada canal est´a formado por 8 bits. No es un espacio perceptualmente uniforme. Colores distantes no son percibidos como tal, y a la inversa. HSV (Hue Saturation Value) : Este espacio de color se compone por tres canales que caracterizan a la tonalidad (H), saturaci´on (S) y valor (V). Es una transformaci´on no lineal del espacio de color RGB. v´ease ecuaci´on (2.2). H=            no definido si MAX =MIN 60oG−B MAX−MIN + 0osi MAX =RyG≥B 60oG−B MAX−MIN + 360osi MAX =RyG < B 60oG−R MAX−MIN + 120osi MAX =G 60oR−G MAX−MIN + 240osi MAX =B S=0si MAX = 0 1−MIN MAX en otro caso V=MAX (2.2) donde: MAX: Valor m´aximo de RGB y MIN: Valor m´ınimo de RGB. CIELAB : Proviene de CIE (Commission Internationale de l’clairage), L (Lightness) y A y B para la dimensi´on de color oponente. Se pretende que CIELAB sea un espacio de color lineal. La transformacion de RGB a CIELAB aparece en la equaci´on (2.3). 20 Introducci´on   X= 0,412453R+ 0,357580G+ 0,180423B Y= 0,212671R+ 0,715160G+ 0,072169B Z= 0,019334R+ 0,119193G+ 0,950227B   L∗= 116f(Y/Yn)−16 a∗= 500(f(X/Xn)−f(Y/Yn)) b∗= 200(f(Y/Yn)−f(Z/Zn)) f(q) = q1 3si q > (6 29)3 1 3(29 6)2q+4 29 en otro caso (2.3) donde: Xn,YnyZnson los valores del punto blanco de referencia definido por el est´andar CIE de iluminaci´on. YCbCr: Este espacio de color se compone por una componente de luminosidad (Y) y dos componentes de color (Cb y Cr), que representan la crominancia en azul y en rojo. La transformaci´on de RGB a YCbCr aparece en la ecuaci´on (2.4).   Y Cb Cr  =  16 128 128  +  65,481 128,553 24,966 −37,797 −74,203 112 112 −93,786 −18,214    R G B  (2.4) Comunmente es necesario la discretizaci´on de los valores de color de las im´agenes, esto genera una p´erdida de la informaci´on pero se gana velocidad a la hora de realizar c´omputo. Una posible forma de recoger los valores discretizados es a partir de un histograma de color. A la hora de tratar las im´agenes podr´ıa ser a nivel de p´ıxel donde se posee localidad espacial de ´esta, o se podr´ıa obtener el histograma de la imagen, este m´etodo tiene como objetivo obtener las cualidades cuantitativas de la imagen. A pesar de perder informaci´on de la imagen, se emplea con frecuencia este m´etodo como descriptores cuando se basa la reidentificaci´on en apariencia. [Seon et al., 2011, Cha and Srihari, 2002, Naik et al., 2009, Ling and Okada, 2006]. 2.4. HISTOGRAMA 21 2.4. Histograma Un histograma representa el n´umero de ocurrencias de los valores de un conjunto de datos, haciendo referencia a la ecuaci´on (2.5). En el tratamiento de im´agenes se emplean histogramas para obtener informaci´on cuantitativa, la distribuci´on del color en la imagen. Hi(A) = n X j=1 cij donde cij =1si aj=xi 0en otro caso (2.5) Algunas caracter´ısticas de los histogramas son las siguientes: No contiene informaci´on espacial de la imagen Dos im´agenes diferentes pueden coincidir en histograma La imagen no se puede obtener a partir de un histograma La figura 2.5 representa un conjunto de datos y el histograma que se obtiene a partir del conjunto. Para el caso de visi´on por computador el conjunto representar´ıa la imagen con los valores de cada p´ıxel. En el histograma resultante se aprecia como se distribuyen los datos. A su vez, se puede simplificar de mayor manera obteniendo divisiones resultantes que aglutinen varias divisiones iniciales, el bin ser´ıa cada una de los intervalos en los que est´a dividido el rango de valores de la medida que representa el histograma. Figura 2.5: AConjunto de valores; H(A) Histograma correspondiente a A. A la hora de trabajar con histogramas, una buena pr´actica es realizar una normalizaci´on, se suele normalizar como funci´on de probabilidad, ver ecuaci´on (2.6). Esta tarea de preprocesado se lleva a cabo para llevar a un plano com´un cualquier distribuci´on sin importar el n´umero de elementos que tengan. 22 Introducci´on H0(A) = H(A) Pn i=1 Ai donde n X i=1 H(A) = 1 (2.6) Existe la necesidad de comparar histogramas para conocer como de similares son, como se identific´o en (2.1), por este motivo se hace uso de distintos tipos de medidas de distancias para histogramas. 2.5. Distancia entre histogramas Citando [rae, 2014], ”una distancia la definen por un espacio o intervalo de lugar o de tiempo que media entre dos cosas o sucesos”, pudiendo ser tambi´en ”la diferencia, desemejanza notable entre unas cosas y otras”. Una definici´on mas formal es la siguiente, como una funci´on de distancia d(x, y) definida en un espacio de dimensi´on Rn, es una funci´on d:Rn×Rn→ R, debe cumplir las siguientes propiedades: d(x, y)≥0 d(x, x) = 0 d(x, y) = d(y, x) Si adem´as cumple: d(x, y) = 0 iff x=y d(x, y)≤d(x, k) + d(k, y) Se dice que es una distancia m´etrica. A la hora de calcular la distancia entre dos histogramas hay que tener en cuenta qu´e distancia o conjunto de distancias son las que nos podr´ıan interesar, ya que cada distancia cumple con unas propiedades o serie de caracter´ısticas que las definen. Hay dos grupos de medidas, bin to bin y cross-bin. El primer grupo se centra en la comparaci´on del contenido del bin con el correspondiente del segundo histograma, no aprovechan la informaci´on de los bins adyacentes. El segundo grupo hace ´enfasis en los valores adyacentes al bin que corresponde a ser tratado. Dependiendo de la medidas que se empleen se pueden obtener valores distintos para histogramas que son aparentemente similares. V´ease figura 2.6, 2.5. DISTANCIA ENTRE HISTOGRAMAS 23 Figura 2.6: Comparaci´on de histogramas. (A) Corresponde con la comparaci´on de dos histogramas y (B) Corresponde a la comparaci´on de dos histogramas similares a (A) pero con un bin m´as que tiene valor nulo. dependiendo de la distancia que se emplee (A) tendr´a valor equivalente a (B) o no. Algunas medidas comunmente usadas en distancias entre histogramas: Bhattacharyya [Naik et al., 2009]: Es una medida del tipo bin to bin, la cual mide la similitud de dos distribuciones de probabilidad. Posee una complejidad computacional O(n). Bhattacharyya(x, y)=1−v u u t n X i=1 √xiyi pPn i=1 xiPn i=1 yi (2.7) Chi Cuadrado [Zhang and Canosa, 2014]: Es una medida del tipo bin to bin, la cual tiene origen estad´ıstico. Posee una complejidad computacional O(n). X2(x, y) = 1 2 n X i=1 (xi−yi)2 (xi+yi)(2.8) Correlaci´on [his, 2014]: Es una medida bin to bin, la cual refiere a una relaci´on estad´ıstica que implica dependencia[wik, 2014]. Posee una complejidad computacional O(n). correlation(x, y) = Pn i=1(xi−¯x)(yi−¯y) pPn i=1(xi−¯x)2Pn i=1(yi−¯y)2(2.9) Intersecci´on [Zhang and Canosa, 2014]: Es una medida del tipo bin to bin, la cual proviene de la intersecci´on de los dos histogramas. Esta medida tiene un alto rendimiento computacional. Posee una complejidad computacional O(n). intersec(x, y) = n X i=1 min(xi, yi) (2.10) 30 Metodolog´ıa de la cabeza, tronco y pies. Adem´as se podr´ıa ponderar con valores bajos las zonas con mayor variaci´on y altos las de menor. Por contra, hay que configurar detalladamente el n´umero de bins que tendr´an los histogramas porque no aparecer´an muchos colores en esa franja de la imagen. 3.4. Implementaci´on Lo primero que se va a realizar es la normalizaci´on de la estructura donde est´an alojadas las im´agenes para cada una de las bases de datos. Esto se va a realizar para estandarizar el proceso de carga y de verificaci´on de las im´agenes. Ya que va a ser una tarea que vamos a realizar m´ultiples veces. La estructura a seguir va a ser una carpeta donde alojar todas las im´agenes sin diferenciar los probes de los gallerys. Como se aprecia en la figura 3.4, el nombre del archivo sigue la siguiente estructura, los 4 primeros d´ıgitos son para el identificador del probe y los 3 restantes para el identificador del n´umero de imagen tomada del probe. Figura 3.4: Etiquetado de imagen. (A) representa el identificador del probe y (B) hace referencia n´umero de imagen tomada para el probe. A la hora de cargar las im´agenes vamos a obtener dos conjuntos de datos, el primer conjunto hace referencia a todos los probes de la base de datos y el segundo conjunto pertenece al gallery. Para obtener el conjunto de probes se van leyendo las im´agenes y el ´ındice de probe que no est´e en el conjunto se a˜nade, sino se omite. Por otro lado, el conjunto de gallery lo conforman las im´agenes omitidas por el conjunto anterior. La figura 3.3 alude a la estructura que siguen las im´agenes a la hora de obtener sus caracter´ısticas. A las im´agenes se les podr´a asignar un ancho y 3.4. IMPLEMENTACI ´ ON 31 un alto y se obtendr´an los valores del espacio de color que se desee emplear. A continuaci´on se dividir´a la imagen en franjas horizontales, para los cuales se obtendr´an los histogramas correspondientes para cada canal y secci´on con un determinado n´umero de bin. Para finalizar se normalizan los datos de los histogramas usando una normalizaci´on por funci´on de probabilidad (ecuaci´on 2.6) y se concatenan los canales. El siguiente paso a realizar es el matching el cual generar´a una lista ordenada para cada probe a trav´es de la comparaci´on de histogramas haciendo uso de las medidas de distancias referenciadas en la secci´on 3.2. El ranking estar´a ordenado de mayor similitud a menor. A continuaci´on se generar´a una lista con los valores correspondientes a cada posici´on de la CMC y se obtendr´a el ´area bajo la curva, vease la secci´on 3.2 donde se comenta como calcular la CMC. Con esta implementaci´on se va a extraer los datos necesarios para analizarlos y obtener los conclusiones. 32 Metodolog´ıa Cap´ıtulo 4 Resultados En este cap´ıtulo se comentar´an los resultados obtenidos para la fase de experimentaci´on que se ha realizado. Dividi´endose en 3 secciones, donde se analizar´an el comportamiento de las medidas de distancia para distintos espacio de color, n´umero de bins y n´umero de franjas. No incluimos una secci´on para confrontar las distancias con las distintas bases de datos porque no pretendemos comprobar como se comportan ante cada una, sino lo que pretendemos es obtener una visi´on general que pueda servir como punto de partida a la hora de seleccionar los valores de los diferentes par´ametros en estudio. Cabr´ıa resaltar que para el uso de las medidas de distancia para histogramas se han realizado peque˜nas modificaciones en las ecuaciones originales para evitar posibles indeterminaciones a la hora de procesar cada bin, que producir´ıa un error que se arrastrar´ıa a los bins restantes. Por otro lado, hay que contemplar qu´e entiende el algoritmo por mayor similitud, valores resultantes elevados o por el contrario pr´oximos a cero. Con el fin de eliminar posibles indeterminaciones a la hora de analizar los bins se han modificado las distancias Chi Cuadrado y KL. Para la primera distancia, se puede observar en la ecuaci´on (2.8) que si el denominador tiene valor cero el resultado ser´ıa infinito, esta situaci´on puede ocurrir cuando se est´en procesando dos bins con valores nulos. Nuestra aproximaci´on para eliminar esta indeterminaci´on ha sido desechar estos bins, no los incluimos en el c´alculo. Si observamos la ecuaci´on (2.11) correspondiente a la distancia de KullbackLiebler, no puede haber ning´un bin con valor cero porque podr´ıa ocurrir dos situaciones: Que el denominador sea igual a cero y obtendr´ıamos como valor infinito o que el numerador sea cero y como resultado obtendr´ıamos ln(0) 33 34 Resultados que eso es igual a infinito. Como soluci´on hemos desechado del an´alisis los pares de bins que a la hora de compararlos alguno de ellos tenga valor nulo. Se considerar´a como mayor similaridad o menor distancia entre histogramas, la distancia que obtenga menor valor num´erico. Por lo tanto se han modificado las ecuaciones (2.9, 2.10, 2.11) correspondientes a las distancias de Correlaci´on, Intersecci´on y KL respectivamente. Esto surge por la necesidad de hacer uso del mismo operador de comparaci´on y no ir alternando uno por otro dependiendo de la distancia que se haga uso en la fase de implementaci´on. Para solventar estos problemas se ha modificado las condiciones de las ecuaciones Correlaci´on e Intersecci´on como se observa en la ecuaci´on (4.1), adem´as para solventar la distancia KL se ha a˜nadido las siguientes condiciones, ecuaci´on (4.2). Si distancia = {Correlaci´on o Intersecci´on} distanciaf(x, y) = −distancia(x, y) (4.1) Si distancia = KL KLf(x, y) = KL(x, y)Si KL(x, y)≥0 KLf(x, y) = −KL(x, y)Si KL(x, y)<0(4.2) A continuaci´on se van a comentar de forma detallada los resultados que se han obtenido en la fase de experimentaci´on. Asimismo en el anexo A se muestran las tablas con los resultados obtenidos para cada configuraci´on de n´umero de bins y del n´umero de divisiones de la imagen, donde se enfrentan las medidas de distancia y el espacio de color. Adem´as destacar que existe un campo donde se visualiza el promedio de cada medida de distancia frente al espacio de color como conclusi´on de las tablas. Tambi´en se analizar´an otros datos que podr´ıan ser interesantes a la hora de concluir con los resultados. 4.1. Espacio de color Para conocer como afecta al resultado el uso de diferentes espacios de color, se ha obtenido el ´area CMC generado por el promedio del n´umero de bins, n´umero de franjas y de las bases de datos. De esta forma conseguimos visualizar los datos como aparecen en la figura 4.1, donde en el eje de abscisas agrupamos los resultado del ´area CMC para cada distancia con los espacios de color. 4.2. N ´ UMERO DE BINS 35 Figura 4.1: ´ Area CMC para distancias y espacio color. RGB HSV CIELAB Bhattacharyya 81.99 % 86.22 % 84.13 % Chi cuadrado 82.16 % 86.29 % 84.06 % Correlaci´on 78.16 % 79.87 % 74.08 % EMD 79.79 % 83.92 % 80.90 % Intersecci´on 82.27 % 86.05 % 83.55 % Mahalanobis 62.17 % 62.40 % 60.28 % KL 70.61 % 74.02 % 73.81 % Distancia promedio 76.74 % 79.83 % 77.26 % Cuadro 4.1: ´ Area CMC de las distancias frente espacios de color Las distancias que proporcionan mejores resultados son Bhattacharyya, Chi Cuadrado e Intersecci´on, las tres medidas son medidas de bin to bin, adem´as muestran una aparente relaci´on, id´entica, entre los espacios de color. El espacio de color que obtuvo mejores resultados fue el HSV, esto puede ser debido a la separaci´on en las componentes de la crominancia y la luminancia, ver tabla 4.1. 4.2. N´umero de bins Para conocer como afecta al resultado el uso de diferentes configuraciones para el n´umero de bins se ha obtenido el ´area CMC generado por el promedio del espacio color, n´umero de franjas y de las bases de datos. De esta forma 36 Resultados conseguimos visualizar los datos como aparecen en la figura 4.2, donde en el eje de abscisas agrupamos los resultado del ´area CMC para cada distancia con las distintas configuraciones de bins. Figura 4.2: ´ Area CMC para distancias y n´umero de bins. 16 bins 32 bins 64 bins 128 bins Bhattacharyya 85.49 % 85.64 % 85.58 % 85.60 % Chi cuadrado 85.49 % 85.59 % 85.48 % 85.49 % Correlaci´on 78.36 % 79.06 % 79.10 % 79.00 % EMD 84.24 % 83.63 % 82.86 % 82.18 % Intersecci´on 85.32 % 85.34 % 85.26 % 85.26 % Mahalanobis 62.93 % 64.37 % 66.12 % 67.73 % KL 78.70 % 76.30 % 73.25 % 69.93 % Distancia promedio 80.08 % 79.99 % 79.67 % 79.31 % Cuadro 4.2: ´ Area CMC de las distancias frente n´umero de bins Las distancias que proporcionan mejores resultados son Bhattacharyya, Chi Cuadrado e Intersecci´on, cabr´ıa resaltar que para la reducci´on del histograma empleando un tama˜no de bin mayor se obtienen resultados similares que con bins de menor tama˜no, por lo que ser´ıa interesante cuando se usen estas distancias, hacer uso de bins de mayor tama˜no porque los c´alculos ser´an computados a mayor velocidad, al tener el histograma un n´umero menor de bins. Cabr´ıa comentar el comportamiento que se percibe en las medidas KL, Maha- 4.3. N ´ UMERO DE FRANJAS 37 lanobis y EMD. En primer lugar la medida KL empeora los resultados cuanto mayor es el n´umero de bins, esto se debe a la aproximaci´on que hemos usado para solucionar las indeterminaciones que nos presenta KL. Al aumento del n´umero de bins van a haber valores de color que no se emplean y van a formar huecos en el histograma, estos huecos van a tener valor cero, lo que implica que no se van a procesar a la hora de realizar el c´alculo de la distancia con el otro histograma de color, a pesar de que el otro histograma tenga valores de color distintos de cero. Por lo que al disminuir el tama˜no de bin perdemos informaci´on a procesar, una posible soluci´on es usar la medida divergencia de Jeffrey [Rubner et al., 2000]. Por otro lado, destacar el comportamiento de las distancias de Mahalanobis y de EMD. La primera mejora cuanto mayor sea el n´umero de bins, esto se debe a que posee una matriz mayor para realizar la covarianza, por lo que obtiene mayor n´umero de caracter´ısticas para discriminar las im´agenes. Para la distancia EMD, cuanto mayor es el n´umero de bins peores resultados se obtienen, esto se debe a que busca el m´ınimo n´umero de movimientos para conseguir que un histograma se parezca a otro, al existir muchos ceros esas partes del histograma van a generar ruido para la obtenci´on del m´ınimo n´umero de movimientos. En la tabla 4.2 se refleja que el uso del menor n´umero de bins proporciona mejores resultados, pero no es una mejora significativa la que se obtiene, proponemos como configuraci´on inicial a un problema hacer uso de 16 ´o 32 bins para el histograma, para no perder demasiada informaci´on. 4.3. N´umero de franjas Para conocer como afecta al resultado el uso de diferentes configuraciones del n´umero de franjas en la imagen se ha obtenido el ´area CMC generado por el promedio del espacio color, n´umero de bins y de las bases de datos. De esta forma conseguimos visualizar los datos como aparecen en la figura 4.3, donde en el eje de abscisas agrupamos los resultado del ´area CMC para cada distancia con diferente n´umero de franjas. Las distancias que proporcionan mejores resultados son Bhattacharyya, Chi Cuadrado e Intersecci´on. La divisi´on de la imagen en franjas mejora significativamente los resultados, pero llega a un punto en el que el exceso de franjas hace que empeore los resultados. Esto se debe a que se le est´a a˜nadiendo ruido al histograma, al tener muchas franjas vamos a tener muchos histogramas 38 Resultados Figura 4.3: ´ Area CMC para distancias y n´umero de franjas. con valores de bins nulos. Por otro lado, hacer uso de un solo histograma para la imagen, no nos proporcionar´ıa detalle de la distribuci´on del color en ciertas zonas de la imagen que corresponden con diferenetes prendas de ropa. Como sucedi´o en la secci´on 4.2, la distancia KL se comporta de forma an´omala en comparaci´on con el resto de distancias. Esto es debido a lo descrito anteriormente, se ha desechado informaci´on importante a la hora de realizar el c´alculo de la distancia. Proponemos hacer uso como configuraci´on inicial, la divisi´on de la imagen en 10 franjas y 5 franjas que son las que han obtenido mejores resultados y Imagen completa 5 franjas 10 franjas 25 franjas Bhattacharyya 81.94 % 86.16 % 86.96 % 87.24 % Chi cuadrado 81.76 % 86.13 % 86.94 % 87.21 % Correlaci´on 70.09 % 79.76 % 82.11 % 83.57 % EMD 80.17 % 84.00 % 84.49 % 84.25 % Intersecci´on 81.32 % 85.92 % 86.82 % 87.12 % Mahalanobis 61.82 % 65.45 % 66.86 % 67.02 % KL 79.38 % 77.38 % 73.75 % 67.67 % Distancia promedio 76.64 % 80.69 % 81.13 % 80.58 % Cuadro 4.3: ´ Area CMC de las distancias frente n´umero de franjas 4.4. OTRAS CARACTER´ ISTICAS ANALIZADAS 39 entre ellas no difieren significativamente. V´ease la tabla 4.3. 4.4. Otras caracter´ısticas analizadas Hemos decidido que merece la pena comprobar el rendimiento en tiempo, ya que habr´ıa que tener un compromiso en relaci´on a tiempo y resultados obtenidos a la hora de reidentificar. En la figura 4.4 se observa el tiempo en horas en el que tardo en ejecutarse las pruebas, donde aludimos al n´umero de bins y al n´umero de franjas. Estos resultados aluden al tiempo total en ejecutar 4 bases de datos con 3 espacios de color, 7 medidas de distancia y 16 configuraciones para el n´umero de bins y n´umero de franjas. El coste computacional para ejecutar las pruebas de cada base de datos viene dada por la ecuaci´on (4.3). O48PG F5B+B(B−1) 2+B3log B+ 3 P2G+ 1 (4.3) Donde Prepresenta el n´umero de individuos probes, Ges el n´umero de individuos engallery, Fes el n´umero de franjas, Brepresenta el n´umero de bins. Figura 4.4: Rendimiento en horas para n´umero de bins y n´umero de franjas. Aumentar el n´umero de bins, como tambien el n´umero de franjas, aumenta el tiempo de ejecuci´on de las pruebas. Se puede observar que existe una relaci´on en el aumento de las franjas, donde aumentan para cada bin aproximadamente de forma lineal, ver tabla 4.4. En cambio para el n´umero de bins no se aprecia una relaci´on clara. [Gong et al., 2014] Gong, S., Cristani, M., Yan, S., and Change, C. (2014). Person Re-Identification. Springer. [Huang et al., 2010] Huang, J., Zhao, J., Gao, W., Long, C., Xiong, L., Yuan, Z., and Han, S. (2010). Local binary pattern based texture analysis for visual fire recognition. In Image and Signal Processing (CISP), 2010 3rd International Congress on, volume 4, pages 1887–1891. [Jim´enez, 2000] Jim´enez, J. G. (2000). Visi´on por Computador. Paraninfo. [Ling and Okada, 2006] Ling, H. and Okada, K. (2006). Diffusion distance for histogram comparison. In Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on, volume 1, pages 246–253. [Liu and Shum, 2003] Liu, C. and Shum, H.-Y. (2003). Kullback-leibler boosting. In Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, volume 1, pages I–587–I–594 vol.1. [Naik et al., 2009] Naik, N., Patil, S., and Joshi, M. (2009). A scale adaptive tracker using hybrid color histogram matching scheme. In Emerging Trends in Engineering and Technology (ICETET), 2009 2nd International Conference on, pages 279–284. [Rubner et al., 2000] Rubner, Y., Tomasi, C., and Guibas, L. J. (2000). The earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vision, 40(2):99–121. [Satta, 2013] Satta, R. (2013). Appearance descriptors for person reidentification: a comprehensive review. CoRR, abs/1307.5748. [Seon et al., 2011] Seon, D., Cristani, M., Stoppa, M., Bazzani, L., and Murino, V. (2011). Custom pictorial structures for re-identification. In Proceedings of the British Machine Vision Conference, pages 68.1–68.11. BMVA Press. http://dx.doi.org/10.5244/C.25.68. [Vezzani et al., 2013] Vezzani, R., Baltieri, D., and Cucchiara, R. (2013). People reidentification in surveillance and forensics: A survey. ACM Comput. Surv., 46(2):29:1–29:37. [Wang, 2013] Wang, X. (2013). Intelligent multi-camera video surveillance: A review. Pattern Recognition Letters, 34(1):3–19. [Zhang and Canosa, 2014] Zhang, Q. and Canosa, R. L. (2014). A comparison of histogram distance metrics for content-based image retrieval. Glosario bin to bin Tipo de distancia donde se comparan los elementos del mismo conjunto. La distancia total es la suma de la distancia de cada conjunto. 13, 22–24, 35 crominancia Componente de una se˜nal que contiene las informaciones del color. 18–20, 35, 44 cross-bin Tipo de distancia donde se comparan no solo los elementos del mismo conjunto sino tambi´en el resto. Se requiere una distancia bin to bin como base de distancia. 13, 22, 24 est´andar CIE Sistema que se emplea como referencia para definir los colores que percibe el ojo humano y otros espacios de color. 20 gallery T´ermino usado en reidentificaci´on para el conjunto de imagenes de individuos. 16–18, 28–30, 39 luminancia Densidad superficial de intensidad lum´ınica en una cierta direcci´on. 18, 19, 35, 44 matching Proceso en visi´on por computador que hace uso de descriptores o caracter´ısticas para identificar a un individuo en un conjunto. 31 probe T´ermino usado en reidentificaci´on para la imagen base que se pretende reidentificar entre una serie de imagenes. 16–18, 26–28, 30, 31, 39 47 48 Glosario Ap´endice A Anexo RGB HSV CIELAB Bhattacharyya 78.42 % 84.38 % 82.48 % Chi cuadrado 78.36 % 84.23 % 82.14 % Correlaci´on 71.40 % 70.66 % 65.78 % EMD 77.88 % 82.91 % 80.77 % Intersecci´on 78.12 % 83.75 % 81.63 % Mahalanobis 61.25 % 59.47 % 53.58 % KL 77.35 % 82.91 % 79.16 % Promedio 74.68 % 78.33 % 75.08 % Cuadro A.1: Porcentaje promedio del ´area bajo la curva CMC para 16 bins e imagen completa. Espacios de color frente a distancias RGB HSV CIELAB Bhattacharyya 78.54 % 84.40 % 83.05 % Chi cuadrado 78.38 % 84.24 % 82.80 % Correlaci´on 71.04 % 70.33 % 69.51 % EMD 77.77 % 82.48 % 80.75 % Intersecci´on 78.25 % 83.69 % 82.07 % Mahalanobis 62.42 % 62.55 % 56.93 % KL 77.33 % 82.58 % 80.00 % Promedio 74.82 % 78.61 % 76.45 % Cuadro A.2: Porcentaje promedio del ´area bajo la curva CMC para 32 bins e imagen completa. Espacios de color frente a distancias 49 50 Anexo RGB HSV CIELAB Bhattacharyya 78.55 % 84.39 % 83.04 % Chi cuadrado 78.42 % 84.21 % 82.85 % Correlaci´on 71.23 % 70.45 % 70.23 % EMD 77.60 % 82.02 % 80.54 % Intersecci´on 78.22 % 83.75 % 82.20 % Mahalanobis 64.50 % 64.19 % 60.85 % KL 76.64 % 82.04 % 79.17 % Promedio 75.02 % 78.72 % 76.98 % Cuadro A.3: Porcentaje promedio del ´area bajo la curva CMC para 64 bins e imagen completa. Espacios de color frente a distancias RGB HSV CIELAB Bhattacharyya 78.60 % 84.39 % 83.06 % Chi cuadrado 78.43 % 84.19 % 82.85 % Correlaci´on 71.14 % 69.70 % 69.56 % EMD 77.40 % 81.59 % 80.30 % Intersecci´on 78.32 % 83.75 % 82.12 % Mahalanobis 66.31 % 66.79 % 63.06 % KL 75.72 % 81.07 % 78.61 % Promedio 75.13 % 78.78 % 77.08 % Cuadro A.4: Porcentaje promedio del ´area bajo la curva CMC para 128 bins e imagen completa. Espacios de color frente a distancias RGB HSV CIELAB Bhattacharyya 83.06 % 88.45 % 86.77 % Chi cuadrado 83.18 % 88.48 % 86.70 % Correlaci´on 80.15 % 83.21 % 74.36 % EMD 81.96 % 87.15 % 85.54 % Intersecci´on 83.07 % 88.25 % 86.47 % Mahalanobis 65.35 % 66.19 % 59.68 % KL 77.95 % 83.46 % 81.19 % Promedio 79.24 % 83.60 % 80.10 % Cuadro A.5: Porcentaje promedio del ´area bajo la curva CMC para 16 bins e imagen dividida en 5 franjas. Espacios de color frente a distancias Anexo 51 BD Media RGB HSV CIELAB Bhattacharyya 83.09 % 88.38 % 87.17 % Chi cuadrado 83.11 % 88.37 % 87.15 % Correlaci´on 80.17 % 82.80 % 76.99 % EMD 81.43 % 86.48 % 85.17 % Intersecci´on 83.02 % 88.17 % 86.69 % Mahalanobis 65.68 % 66.66 % 63.84 % KL 75.99 % 81.09 % 80.22 % Promedio 78.93 % 83.14 % 81.03 % Cuadro A.6: Porcentaje promedio del ´area bajo la curva CMC para 32 bins e imagen dividida en 5 franjas. Espacios de color frente a distancias RGB HSV CIELAB Bhattacharyya 83.09 % 88.35 % 87.02 % Chi cuadrado 83.03 % 88.29 % 86.93 % Correlaci´on 80.27 % 82.94 % 76.67 % EMD 80.72 % 85.73 % 84.62 % Intersecci´on 82.99 % 88.10 % 86.57 % Mahalanobis 65.61 % 66.65 % 65.56 % KL 73.38 % 78.19 % 77.51 % Promedio 78.44 % 82.61 % 80.70 % Cuadro A.7: Porcentaje promedio del ´area bajo la curva CMC para 64 bins e imagen dividida en 5 franjas. Espacios de color frente a distancias RGB HSV CIELAB Bhattacharyya 83.17 % 88.36 % 87.07 % Chi cuadrado 83.07 % 88.27 % 86.99 % Correlaci´on 80.44 % 83.05 % 76.05 % EMD 80.16 % 85.06 % 84.01 % Intersecci´on 83.03 % 88.09 % 86.60 % Mahalanobis 66.18 % 66.63 % 67.35 % KL 70.25 % 74.21 % 75.15 % Promedio 78.04 % 81.95 % 80.46 % Cuadro A.8: Porcentaje promedio del ´area bajo la curva CMC para 128 bins e imagen dividida en 5 franjas. Espacios de color frente a distancias 52 Anexo RGB HSV CIELAB Bhattacharyya 84.05 % 89.11 % 87.51 % Chi cuadrado 84.19 % 89.23 % 87.50 % Correlaci´on 82.06 % 85.69 % 77.37 % EMD 82.91 % 87.85 % 86.34 % Intersecci´on 84.19 % 89.11 % 87.44 % Mahalanobis 65.84 % 65.55 % 62.96 % KL 75.81 % 81.14 % 80.72 % Promedio 79.86 % 83.95 % 81.41 % Cuadro A.9: Porcentaje promedio del ´area bajo la curva CMC para 16 bins e imagen dividida en 10 franjas. Espacios de color frente a distancias RGB HSV CIELAB Bhattacharyya 84.08 % 89.14 % 87.78 % Chi cuadrado 84.10 % 89.14 % 87.86 % Correlaci´on 82.14 % 85.55 % 79.16 % EMD 82.06 % 86.99 % 85.83 % Intersecci´on 84.03 % 89.02 % 87.62 % Mahalanobis 65.63 % 66.36 % 66.13 % KL 72.19 % 77.06 % 78.12 % Promedio 79.17 % 83.32 % 81.79 % Cuadro A.10: Porcentaje promedio del ´area bajo la curva CMC para 32 bins e imagen dividida en 10 franjas. Espacios de color frente a distancias RGB HSV CIELAB Bhattacharyya 84.07 % 89.10 % 87.62 % Chi cuadrado 84.01 % 89.03 % 87.58 % Correlaci´on 82.25 % 85.85 % 78.54 % EMD 81.15 % 86.02 % 84.98 % Intersecci´on 83.95 % 88.94 % 87.36 % Mahalanobis 67.93 % 69.11 % 66.41 % KL 69.14 % 72.62 % 74.46 % Promedio 78.93 % 82.95 % 80.99 % Cuadro A.11: Porcentaje promedio del ´area bajo la curva CMC para 64 bins e imagen dividida en 10 franjas. Espacios de color frente a distancias Anexo 53 RGB HSV CIELAB Bhattacharyya 84.20 % 89.10 % 87.71 % Chi cuadrado 84.05 % 89.00 % 87.64 % Correlaci´on 82.38 % 86.15 % 78.16 % EMD 80.43 % 85.13 % 84.15 % Intersecci´on 83.97 % 88.89 % 87.37 % Mahalanobis 69.86 % 68.62 % 67.94 % KL 65.34 % 67.19 % 71.24 % Promedio 78.60 % 82.01 % 80.60 % Cuadro A.12: Porcentaje promedio del ´area bajo la curva CMC para 128 bins e imagen dividida en 10 franjas. Espacios de color frente a distancias RGB HSV CIELAB Bhattacharyya 84.57 % 89.39 % 87.72 % Chi cuadrado 84.59 % 89.52 % 87.80 % Correlaci´on 82.99 % 87.34 % 79.31 % EMD 83.02 % 87.96 % 86.58 % Intersecci´on 84.50 % 89.50 % 87.87 % Mahalanobis 63.41 % 66.54 % 65.39 % KL 71.55 % 75.18 % 77.98 % Promedio 79.23 % 83.63 % 81.81 % Cuadro A.13: Porcentaje promedio del ´area bajo la curva CMC para 16 bins e imagen dividida en 25 franjas. Espacios de color frente a distancias RGB HSV CIELAB Bhattacharyya 84.64 % 89.43 % 87.93 % Chi cuadrado 84.52 % 89.40 % 87.98 % Correlaci´on 83.11 % 87.29 % 80.66 % EMD 81.86 % 86.90 % 85.80 % Intersecci´on 84.39 % 89.34 % 87.84 % Mahalanobis 64.66 % 64.87 % 66.70 % KL 67.55 % 69.45 % 74.02 % Promedio 78.68 % 82.38 % 81.56 % Cuadro A.14: Porcentaje promedio del ´area bajo la curva CMC para 32 bins e imagen dividida en 25 franjas. Espacios de color frente a distancias 54 Anexo RGB HSV CIELAB Bhattacharyya 84.65 % 89.38 % 87.70 % Chi cuadrado 84.47 % 89.28 % 87.66 % Correlaci´on 83.26 % 87.47 % 80.05 % EMD 80.74 % 85.51 % 84.73 % Intersecci´on 84.39 % 89.20 % 87.46 % Mahalanobis 68.33 % 67.44 % 66.89 % KL 62.89 % 63.70 % 69.25 % Promedio 78.39 % 81.71 % 80.54 % Cuadro A.15: Porcentaje promedio del ´area bajo la curva CMC para 64 bins e imagen dividida en 25 franjas. Espacios de color frente a distancias RGB HSV CIELAB Bhattacharyya 84.63 % 89.20 % 87.70 % Chi cuadrado 84.51 % 89.18 % 87.66 % Correlaci´on 83.43 % 87.84 % 80.09 % EMD 79.88 % 84.35 % 83.64 % Intersecci´on 84.41 % 89.14 % 87.43 % Mahalanobis 70.13 % 71.76 % 68.16 % KL 57.78 % 56.16 % 66.49 % Promedio 77.82 % 81.09 % 80.17 % Cuadro A.16: Porcentaje promedio del ´area bajo la curva CMC para 128 bins e imagen dividida en 25 franjas. Espacios de color frente a distancias