[MUSIC] Hola, bienvenidos de nuevo. En este vídeo veremos la base del esquema de pirámides espaciales, que es el Kernel de Comparación o Correspondecia de Pirámides. La idea será extender a nivel de vocabulario una técnica muy eficiente. Originalmente pensada para calcular correspondencias aproximadas, entre descriptores visuales de dos imágenes, en diferentes resoluciones. Veremos que significa la intersección de histogramas y como se aprovecha para contar el número de correspondencias de una misma palabra visual, en regiones diferentes de la imagen, que se encuentren a diferentes niveles de resolución. En particular, describiremos como este Kernel es un excelente estimador de la similitud entre dos histogramas de palabras visuales, que se han generado en diferentes niveles de resolución y en diferentes regiones de la imagen. Empecemos. El Kernel de Comparación de Pirámides que veremos en este vídeo. Se basa en una idea propuesta originalmente por Kristen Grauman y Trevor Darrell en el 2005 en el MIT. El objetivo era aproximar el cálculo de correspondencia ante descriptores visuales de dos imágenes en distinta resolución, para poder estimar su similitud de una forma muy eficiente. La idea principal es concatenar histogramas de varios niveles, donde el histograma tiene en cada nivel el doble de bins o dimensiones que el del nivel posterior. Esta idea de calcular similitudes entre histogramas de las características visuales a múltiples niveles, fue posteriormente adaptada por Svetlana Lazebnik, Cordelia Schmid y Jean Ponce en el 2006. Para aplicarlo en histogramas de palabras visuales. Veamos cómo se adaptó este kernel en el esquema de pirámides espaciales. Como vimos en el anterior vídeo, la idea básica de las pirámides espaciales es representar la imagen mediante histogramas de palabras visuales de diferentes niveles y a diferentes regiones de la imagen. Cada bin del histograma, corresponde a una palabra, al número de veces que aparece la palabra en toda la región para primer nivel. En cada una de las 4 regiones en el segundo nivel y en cada una de las 16 regiones en el tercer nivel. Este proceso se repite para todos los niveles generando 21 histogramas uno por región. Que se concatenan al final siendo la entrada a nuestro clasificador. En este caso el clasificador era un SVM con un kernel especial, un kernel de comparación de histogramas como vemos a continuación. you hemos visto en este curso en el uso de kernels para los calificadores de máquinas de vectores de soporte. La idea principal es proyectar un conjunto de datos a un espacio euclidiano donde se buscará las relaciones lineales entre sus muestras. Es decir en el SVM clásico, se utiliza como proyección el producto escalar para calcular la similitud de las muestras, conocer de esta manera sus posiciones relativas y determinar el hiperplano que los separa mejor. El uso de kernels, sucede cuando la distribución de los puntos son no lineales, no hay ninguna manera de encontrar una única línea recta que separe estos 2 grupos el rojo del verde. Por tanto la idea es proyectar los puntos a un espacio de alta dimensionalidad en este caso una gaussiana, un kernel RBF, Radio Basis Function. Y es en este espacio, donde se pueden encontrar las distancias que nos ayudará a determinar el hiperplano que mejor separe ambas clases. Así cuando la frontera de decisiones no lineal, se han propuesto distintas funciones que proyectan las muestras a otros espacios de representación donde el cálculo de la distancia entre muestras si se puede realizar buscando relaciones lineales. Entre estas funciones está el kernel de intersección de histogramas, que nos permite calcular la similitud existente entre histogramas de dos imágenes como veremos a continuación. No hay que olvidar, que como siempre, tanto el tipo de kernel como los parámetros asociados se calculan por validación cruzada. Es decir que hay que adaptar estas técnicas, para que den el mejor rendimiento, según el tipo de imágenes que tengamos que clasificar. Primero veremos el Kernel de Intersección de Histogramas, que nos permite estimar la similitud que hay entre dos histogramas. Es decir, básicamente, consiste en sumar los valores mínimos que hay por cada bin de dos histogramas que tengamos. Aquí vemos la ecuación y la has de correr para todas las dimensiones del histograma, recorreremos todos los bins y nos iremos quedando con el valor mínimo de cada pareja de bins. Si lo vemos gráficamente, aquí vemos superpuestos 2 bins La clase roja para una clase y el tipo azul para otra clase. Aquí se cuentan el número de puntos que hay en 2 conjuntos que tiene la misma cotización, es decir miramos la unión entre por cada bin del histograma. A continuación aplicaremos el kernel de intersección de histogramas según la idea propuesta por Grauman y Darrell. Para la correspondencia multiresolución de dos imágenes. La idea es que tenemos dos imágenes cualquiera que queremos saber si corresponden a la misma categoría. Extraemos los puntos característicos, de cada punto característico extraemos el descriptor, por ejemplo de forma. Este descriptor, N dimensional. Lo representamos en un espacio. Aquí vemos en un espacio de 2 dimensiones los diferentes descriptores SIFT que hemos extraído de esta imagen. Por tanto esto no corresponde con la posición espacial de la imagen, esto corresponde con el valor de las 2 dimensiones del descriptor SIFT. Es decir 2 valores SIFT en diferentes regiones que sean similares o idénticos caerán en la misma zona en el espacio de descriptores. La idea de Grauman y Darrell es calcular este proceso de correspondencia a diferentes resoluciones. Aquí la resolución sería menor. La idea entonces será, por cada nivel, contar el número de correspondencias que hay entre ambas pirámides. Es decir, queremos por cada bin, nos quedaremos con el menor número de apariciones de SIFT que haya entre las dos imágenes. Por ejemplo aquí tenemos dos valores, aquí tenemos ningún valor, por lo tanto el mínimo es cero. Esto lo haremos para cada uno de los niveles, teniendo en cuenta que si aquí hemos encontrado unas correspondencias de SIFT, aquí si las volvemos a encontrar no las tendremos en cuenta. La idea principal aparte de calcular el número de puntos SIFT que caen la misma región del espacio de descriptores, es ponderar el número de correspondencias encontradas por cada nivel. Es muy fácil encontrar correspondencias en niveles altos, es decir, cuando la resolución es muy baja y es muy difícil encontrar correspondencias cuando la resolución es muy alta. Por tanto aquí el peso acostumbrará a ser mayor. Por tanto al realizar esta suma ponderada por niveles, el Kernel lo que realiza es un proceso jerárquico para encontrar correspondencias en niveles bajos. Que no se han encontrado en niveles altos. Este proceso, es de un cálculo tan eficiente, que se puede decir que el kernel ofrece un estimador muy bueno para encontrar correspondencias. Que es bastante similar a los que nos daría como you hemos visto antes encontrar correspondencias directas en toda la imagen de un punto SIFT respecto a los otros. Es decir, este esquema de buscar por niveles las correspondencias que hay entre dos bins. Es lo mismo que si analíticamente buscáramos todas las posibles correspondencias, y nos quedará con las más cercanas que son más similares. Por tanto en este paso el proceso es muy eficiente. Para calcular el número de nuevas correspondencias que hay en cada nivel, no contarlas 2 veces si lo hemos encontrado en 2 niveles distintos. Es suficiente con calcular la diferencia entre las intersecciones de histogramas en 2 niveles consecutivos. Hay que recordar que estas intersecciones habrá que ponderarlas según el nivel. you que hay que dar a las correspondencias en regiones muy grandes menos influencia que a las encontradas en rejillas muy pequeñas. Al final, el kernel de correspondencia de pirámides consiste en esta ecuación. Que tiene dos componentes, las que hemos dicho anteriormente. Primero, por una parte, como doblamos la resolución en cada nivel de la malla donde vamos a buscar los descriptores SIFT. En nuestro caso buscaremos vocabularios, espacio de vocabularios. Lo que se hace es doblar la distancia en cada nivel. Por tanto, el peso es inversamente proporcional al doble del nivel en el que estemos. Esto se hace por el motivo de que se dobla la resolución de una malla cuando bajamos de nivel. Por eso el peso es 1/2 elevado al nivel en el que estemos. Este peso ponderativo, que será fijo, no hay que aprenderlo por radiación cruzada. Pondera el número de nuevas coincidencias, que es el número de descriptores SIFT encontrados en el nivel y que no se hayan encontrado you previamente en el nivel anterior. O sea, que solo contaremos con esta formula las nuevas ecuaciones que han emergido en ese nuevo nivel y que no se habían encontrado en el anterior. Aquí vemos cómo adaptar este kernel al uso de pirámides espaciales. Dada una imagen, se genera un histograma, como hemos visto antes, contando el número de veces que aparecen las palabras visuales en la imagen. Recordemos que este histograma está normalizado según Norma L1 L2, según vimos you a principio del curso. Así, para una palabra concreta, el valor de ese bin del histograma cuenta el número de veces que aparece. Por tanto, para este valor de bin contamos el número de veces en azul que ha aparecido esta palabra visual en la imagen. En este caso serían nueve. Para segundo nivel, el histograma, el primer elemento del bin. Cuenta el número de veces que esta palabra aparece en esta región. En este caso sería uno. Tres para la región dos. Dos para la región tres y tres para la región cuarta. Y, finalmente, vemos al final el número de palabras que aparecen en el último nivel. Vemos aquí que la magnitud del histograma en el primer nivel es de nueve, y la magnitud de cada bin del histograma como mucho será uno. Por tanto, you se ve que hay que ponderar más en los niveles bajos que decir de alta resolución. Así, en el esquema de pirámides espaciales, lo que hacemos es, extraer, por cada palabra, un bin en el primer nivel. 4 bins en el segundo nivel, que contaría el número de veces que aparece esa misma palabra y 16 bins para el nivel 0. Por tanto Lazebnik, Schmid y Ponce 2006 aplicando la técnica de correspondencia de histogramas de Grauman y Darrell sobre estos 3 histogramas que veis aquí. Para hacer la correspondencia, lo que se hace es tener en cuenta otra imagen y repetimos el mismo proceso. Si queremos buscar la correspondencia a partir de vocabularios visuales entre esta imagen y esta imagen de aquí, pues aplicamos el mismo proceso. Del vocabulario visual que hemos calculado para generar estos histogramas. Generamos el histograma para la nueva imagen. Contamos el número de veces que aparece esta palabra en particular en toda la imagen. Esta palabra en una región. Las 3 histogramas restantes para las 3 regiones de nivel 1. Y finalmente 16 histogramas, contando el primer bin, el número de veces que aparece en cada uno de estas regiones. Veamos en este ejemplo como funciona la correspondencia multiresolución de palabras visuales en imágenes mediante la intersección de histogramas. En el primer nivel de resolución, se cuenta por cada bin o partición que hemos encontrado del histograma, el número de veces que aparece esa palabra en nuestra imagen. En este caso, aquí veis en lo puntos azules y los puntos rojos se corresponden con, en qué bin aparece la palabra que corresponda, la primera palabra de nuestro vocabulario visual en ambas imágenes. Y aquí veis donde están en el espacio. El primer nivel de resolución, en el caso que estamos ahora se cuenta por cada bin o partición de la imagen el número de veces que aparece una palabra en concreto. Lo mismo hacemos para la segunda y luego una vez tenemos el histograma, en el que tenemos tantos bins como particiones de la imagen y tenemos tantos valores como veces aparecen las palabras en la imagen en esa región. Ahora según lo propuesto por Grauman y Darrell, el cálculo de correspondencias en este nivel, se calcula aplicando la intersección mínima de histograma, que en este caso será 2, hay 2 bins en el que como mínimo hay un elemento en cada uno de los 2 bins. Es decir hemos encontrado que la palabra, aparece 2 veces en el mismo bin en las 2 imágenes. Este valor se tiene que ponderar, recordemos la ecuación que es, las nuevas apariciones, correspondencias que hemos encontrado de vocabulario, en este caso de ahora, no tenemos nivel anterior, por tanto es 2, ponderado por el nivel en el que estamos. Y el nivel que estamos es el nivel 0, por tanto 2 elevado a -0 es 1, así el error o la similitud que existe a nivel 0 entre estas dos imágenes, es valor 2. 2 por las correspondencias, hemos encontrados 2 bins que tienen como mínimo 1 valor y luego ponderado por el nivel en el que estamos. Pasamos al siguiente nivel, estamos en el nivel 1, aquí tenemos 4 regiones, por tanto tenemos 4 bins. En estos 4 bins contamos el número de palabras que aparecen en estos bins de aquí y son estas de aquí. Por tanto se pueden construir los histogramas, tiene 4 bins, 1 elemento en el primer bin, 3 elementos en el segundo, 2 en el tercero y 3 en el cuarto bin y por la imagen segunda, 1 elemento en el primer bin, 2 en el segundo, 2 en el tercero. Aplicamos como antes, la técnica de la mínima intersección del histograma. Vemos que aquí hay uno parecido, aquí el mínimo seria 2 y aquí serian 2, por tanto son 5 el número de vocabularios visuales que aparecen en la misma región, 1 en la primera, 2 en la segunda, 2 en la tercera y ninguno en la cuarta. Recordando la ecuación original de intersección de pirámides. Miramos, 5 hemos encontrado en este nivel, 2 si acordáis los habíamos encontrado en el anterior nivel, por tanto son 3 las nuevas apariciones y ponderado por el nivel en el que estamos. El nivel es el primer nivel, 1 partido por 2, las nuevas correspondencias son 3, por tanto la medida de similitud de las 2 imágenes teniendo en cuenta 2 niveles, seria de 3,5. Finalmente para el último nivel. Sólo tenemos es el nivel más genérico de menos resolución, el nivel más alto, vemos que solo hay 1 bin. En este caso no tenemos particiones no hay regiones y tenemos 9 puntos en la primera imagen de una palabra visual y la misma palabra visual aparece 5 veces en la segunda imagen. Por tanto tenemos un único bin. Hacemos la intersección mínima del histograma. 5 es el número de vocablos que aparecen en las 2 imágenes como mínimo. Y teniendo en cuenta la ecuación, ponderamos estas 9, estas 5 apariciones de las palabras, restamos las que encontramos en el nivel anterior, que eran cinco. Por tanto, tenemos 0 nuevas apariciones. Estas 0, se ponderan por el nivel en el que estamos, que es un cuarto. Por tanto tenemos 5-5 es 0. No hay nuevas correspondencias en este nivel superior, por tanto se queda que la similitud entre las dos imágenes es de 3,5. Veamos aquí un resumen gráfico de la aplicación del kernel propuesto por Grauman y Darrell de comparación de pirámides de histogramas de multiresolución. Dentro de la esquema de pirámides espaciales que propuso Lazebnik, Smith y Ponce. En definitva, usarmos el kernel de intersección de histogramas para dar al SVM una técnica que permita encontrar similitudes entre dos imágenes a la hora de realizar la clasificación de aprender el mejor hiperplano, que separe una clase de otra. Este kernel, para comparar la similitud entre imágenes, se basa en histogramas generados en diferentes resoluciones. Es decir, para la primera resolución, lo que generamos es un histograma de tantos bins como regiones tengamos, en este caso es 1. Y cuenta para cada palabra del vocabulario, en este caso la primera, contaría el número de veces que aparece en la región. Aquí haríamos la intersección mínima de histograma entre 9, que tiene el bin y 5, saldría 5. Para el segundo nivel, contamos el número de palabras que aparecen en esta región. Tenemos tantos bins como regiones. 4 bins y 16 bins en estas regiones de aquí. Una vez tenemos los histogramas calculados, generamos el mínimo intersección. Que es, recordemos que teníamos dos bins. Eran dos los elementos que aparecían en las mismas regiones para los histogramas del nivel 0 de nuestra imagen. Por tanto la salida era el peso 1 por el número de palabras visuales que aparecen en la misma región. Para el nivel 1, tenemos 4 bins. Hemos encontrado 0 para el cuarto, 2 para el segundo y el tercero, y 1 para el primero. Por tanto tenemos 5 correspondencias menos los 2 anteriores. Pues tenemos la resta multiplicado por 1 entre 2, que es debido al nivel en que estamos y, finalmente, para el primer nivel. El nivel 2, el que sólo tiene una región, por tanto tiene 1 bin, hay 5 elementos en común entre las dos imágenes. Por tanto haríamos la resta. 5-5 es 0, y multiplicaríamos por un valor que representa al peso que se le quiere dar a esta región de mayor tamaño. Por tanto, el peso aquí será menor. que el que tenemos en el espacio en el nivel de más resolución. Además de incorporar el Kernel de comparación de pirámides, Lazebnik simplificó el cálculo de nuevas correspondencias entre niveles consecutivos. Es decir, a partir de la fórmula que hemos visto anteriormente lo que se hizo fue desarrollarla. Es decir, sustituir estos valores de cálculo de histograma de intersección por el valor del nivel y ver hacia donde lleva. Es decir que, si cogemos las intersecciones y desarrollamos estos productos, quitamos los paréntesis de esta ecuación de aquí. ¿Vale? No importa que estemos tratando con dos niveles, esto sería genérico para cualquier tipo de nivel que querámos. Pues si desarrollamos esta ecuación de aquí, la idea es que generamos, pues, cálculos de similitud entre dos imágenes, es igual a la intersección de histogramas a nivel 0 más 1/2 de la intersección de histogramas en el nivel 1. Menos 1/2 intersección de histogramas a nivel 0, más 1/4 en la intersección de histogramas del nivel 2, menos 1/4 intersección de histogramas del nivel 1. Es decir, desarrollando esta ecuación de aquí, quitando los valores multiplicativos, asociándolos a cada histograma de intersección. Lo que generamos es que el cálculo de similitud se basa en un peso que es fijo. 1/2 en el nivel de más resolución, 1/4 en el nivel 1 y 1/4 en el nivel de menos resolución, en el nivel más grande. Multiplicado por la intersección de histogramas. No hace falta calcular las restas. Sino simplemente, directamente al cálculo de intersección, sumamos estos valores. you tenemos una medida de similitud bastante buena. Visualmente, esto se refleja de la siguiente manera. Tenemos dos imágenes, para las que queremos encontrar una medida de similitud, para que el clasificador pueda encontrar un buen hiperplano. Obteniendo la localización relativa que hay entre estas dos imágenes de la misma clase. Como hemos dicho, generamos los histogramas para cada palabra. Esto seria un histograma de 1 bin para la palabra en cuestión. Cuatro bins, 16 bins, y ahora Lazebnik lo que hizo fue desarrollar la ecuación, por tanto no miramos la resta entre dos niveles consecutivos. La resta de correspondencias nuevas que hay entre dos niveles consecutivos. Sino calculamos directamente la intersección de histogramas por cada uno de los niveles y después ponderamos por un peso que es fijo. Aquí no hay aprendizaje de pesos, se calcula por nivel la intersección de histogramas. Realmente era un cálculo muy eficiente lo que presentó Lazebnik en el 2006. Para ir acabando, recordemos el significado de las tres ecuaciones más importantes que se han visto durante este vídeo. Por un lado tenemos el cálculo de similitud entre dos histogramas de D regiones o bins en un mismo nivel que se realiza por intersección mínima. Después se pondera el número de intersecciones mínimas que se han encontrado por cada nivel, según la resolución de la pirámide en la que se esté. Los valores son fijos y no vienen aprendidos por variación cruzada. Y finalmente, para una pirámide, esta ecuación de aquí. Se aplica sobre una palabra, por tanto se tiene que repetir el proceso visto anteriormente para todas las palabras visuales del vocabulario. O sea del histograma de todos los bins que corresponde la palabra visual sería mirar la localización que hay en la imagen. El Kernel de correspondencia a comparación de pirámides visto tiene unas propiedades que son muy interesantes. Por una parte permite incorporar información de localización de las palabras visuales en el cálculo de similitud de imágenes por histogramas multiresolución. Esto se hace a la hora de concatenar, en un orden muy específico, si es del primer nivel, del segundo nivel o del tercer nivel. Además, este Kernel satisface la condición de Mercer. Es decir que cumple con la garantía de que la solución que se encuentra con este Kernel puede ser la óptima. you que es un Kernel semi-definido positivo. Esto es debido a que la intersección de histogramas por nivel es una función definida positiva. Lo que significa a la práctica es que puntos o muestras similares pues tendrán distancias muy pequeñas. Además de un cálculo muy eficiente y rápido en la búsqueda de esta similitud. Este Kernel trabaja como estimador de distancias que es muy cercano a lo que se encontraría buscando correspodencias de todos con todos. Por todas estas razones el uso de pirámides espaciales fue muy popular. Siendo la base de las técnicas que ganaron sucesivamente en las competiciones de clasificación de imágenes. Organizadas por la red temática Pascal a principios del siglo 21. Por Mark Everingham y su grupo, y otros científicos de gran renombre en el área de la visión por computador. Finalizamos este vídeo repasando los conceptos más importantes que se han presentado. En este vídeo un poco más largo de lo habitual, hemos visto en detalle, una de las técnicas más importantes de los últimos años. Previos al advenimiento de las redes neuronales. Que es la combinación de las pirámides espaciales, con un kernel de comparación de histogramas multiresolución altamente eficiente. Lo que hizo Lazebnik y su equipo, fue adaptar el kernel propuesto por Grauman y Darrell, para incorporar la localización de las palabras visuales en la imagen. Penalizando, sobre todo, las correspondencias según el nivel de resolución piramidal en la que se ha encontrado. Es evidente que la configuración espacial determina la región a comparar y por ende, las correspondencias que se encuentran de palabras visuales en cada nivel. En el siguiente vídeo veremos un ejemplo práctico de aplicación de las pirámides espaciales para una base de datos concreta de diferentes escenas. Y analizaremos los resultados obtenidos. [MUSIC]
