[MÚSICA] Tal y como habíamos comentado en la presentación de la semana nos vamos a dedicar a proponer diferentes alternativas a los diferentes pasos previos a la extracción del vocabulario en el esquema de bag of words. Esto es nos vamos a centrar en el trabajo sobre las características locales de la imagen. La primera propuesta de extensión es el uso de un detector y descriptor alternativo a SIFT, llamado SURF, por el nombre en inglés de Speeded Up Robust Features, presentado en el 2006. Básicamente la idea que persigue este detector, descriptor es la de realizar las mismas tareas pero de forma más eficiente. Por ello igual que SIFT plantea 2 fases, la detección y la de descripción. En este primer vídeo vamos a centrarnos en la parte de detección y en el segundo vídeo explicaremos un poco más en detalle la parte de descripción de este modelo. En caso de tener dudas sobre el descriptor y sus detalles hay un montón de bibliografía accesible para quien quiera profundizar más en estos detalles. Bien las características de SURF son básicamente las que se presentan en esta transparencia. Una detección rápida de los puntos de interés, según los autores 3 veces mejor que SIFT. Cualquier descriptor y detector debe ser capaz de describir los puntos locales de forma distintiva, de manera que se pueda, que tenga capacidad de distinguir entre diferentes configuraciones locales de la imagen. Y como la mayoría de descriptores intentan ser robustos a diferentes características que pueden variar dentro de la imagen, por ejemplo la rotación, el posible desenfoque de la escena, el cambio de escala, que es fundamental, cambios de iluminación en la escena y pequeños cambios de punto de vista. Si el punto de vista y el cambio de punto de vista es significativo, todos los detectores y descriptores van a sufrir problemas en este apartado. Bien, para ello el detector de SURF debe localizar cuáles son los puntos de la imagen que localmente presentan alguna variación que los hace interesantes para poder hacer una descripción del contenido de la imagen. El mecanismo que utiliza SURF para esta detección es la llamada matriz Hessiana, esta matriz Hessiana está compuesta por 4 componentes y estos componentes no son nada más que la segunda derivada de una gaussiana de una determinada sigma. Vamos a entrar posteriormente en detalle del significado de esta segunda derivada. Pero la idea principal que utiliza SURF es usar el determinante de esta matriz Hessiana como indicador de los cambios locales que suceden alrededor de un determinado punto de interés. Y acabaremos seleccionando aquellos puntos de interés que tengan un determinante mayor, o sea que expresen un cambio local mayor respecto al resto de contenido de la imagen. Como hemos dicho se basa en utilizar la segunda derivada de la gaussiana. En vídeos anteriores hemos visto lo que implica un filtro gaussiano, cómo trabaja un filtro gaussiano. Aquí vemos su expresión matemática y lo que es más interesante su expresión gráfica, con lo cual la consecuencia de aplicar un filtro gaussiano, como se comentaba, es una suavización a medida que se aumenta esta gaussiana. Vamos a utilizar esta idea para incorporar el concepto de escala. La escala la podemos interpretar como cuando más lejos estamos de la imagen nuestro sistema visual más suaviza lo que percibimos, y es el efecto que quiere conseguir la gaussiana. Utilizando la gaussiana como base vamos a ver cómo podemos detectar estos cambios locales. En este ejemplo utilizamos una señal unidimensional para simplificar la extensión a 2 dimensiones cómo sería una imagen, sería directa. Esta de aquí sería el modelo gaussiano, una gaussiana determinada sigma, para el detalle no importa, su primera derivada y su segunda derivada. Si observamos una señal cualquiera donde lo que queremos es obtener dónde ha habido cambios locales, dónde están los cambios locales, deberíamos seleccionar estos dos puntos de aquí como puntos característicos. Sí que hay ciertos puntos característicos a lo largo de toda la señal, pero son tan pequeños que en principio no tienen demasiado interés. Necesitamos algún sistema que nos permita hacer este tipo de selección. Si filtramos esta imagen por la gaussiana directamente lo que obtenemos es esta señal de aquí, que lo que se observa es una suavización de la señal de entrada, Ha cambiado la escala debido a los factores de suavización y lo que observamos es que sí que ha habido algunos puntos máximos aquí, que aquí han desaparecido. Pero aún la señal no es del todo nítida, aquí hay un máximo que podría inducirnos a error, con lo cual buscar máximos y mínimos aquí en esta señal tiene un cierto peligro. La idea pues es utilizar la segunda derivada. Sabemos que si tenemos una función cualquiera para buscar máximos y mínimos de esta función, podemos cálcular su derivada y buscar los ceros de esta derivada. Estos ceros vendrán a ser máximos y mínimos de la señal. Al hacer la primera derivada sobre una gaussiana lo que estamos haciendo es introducir este suavizado que hemos conseguido en la primera fase y a la vez derivar la señal. Esta gráfica de aquí es el resultado de aplicar la primera derivada sobre la señal, utilizando una gaussiana. Podríamos utilizar esta señal para detectar cuáles son los puntos de máximos y mínimos en la señal original y cómo lo haríamos. Básicamente sería utilizando la propiedad de la derivada, que es buscando los cruzamientos por 0, cuando pase de positivo a negativo, cuando pase de negativo a positivo. Si observamos serían todos aquellos puntos que interseccionan con la señal a 0, y observamos que aquí tenemos un punto de cruce, aquí ya tenemos otro punto de cruce, tenemos otro punto de cruce, hay muchísimos puntos de cruce, pero de los cuáles los relevantes serían este de aquí y este de aquí. Esta señal es demasiado ruidosa aún, una manera de solucionarlo es buscar la respuesta en la segunda derivada, que sería la última gráfica de este esquema. Al filtrar la señal de entrada por esta segunda derivada, lo que obtenemos es esta nueva señal de aquí, en la que los máximos y mínimos han sido filtrados de forma muy significativa. Nos queda de forma resaltada cuáles son los puntos de interés en nuestra señal. Vamos a utilizar esta idea para conseguir realzar los puntos en los cuales hay un cambio local significativo, que puede ser indicativo de una estructura importante a representar en nuestra imagen. Para ello lo que utilizamos es los cartesianos, pero en 2 dimensiones. La apariencia de la señal gaussiana, de la segunda derivada de la señal gaussiana es la que se presenta en estas gráficas, en este caso es la segunda derivada respecto a x, esta x es la segunda derivada respecto a y, que es la misma pero girada 90 grados, y este caso de aquí es la segunda derivada respecto a x y respecto a y posteriormente. Los resultados que se obtienen aplicándolos sobre una imagen real, serían los que se observan en la fila de abajo y en los que podemos observar que el primer filtro, el de la segunda derivada en x es muy sensitivo a cambios en vertical, a cambios en esta dirección. La segunda derivada respecto a y será sensitivo a cambios en esta dirección de aquí, en esta dirección. Se observa en esta zona. Y la derivada segunda en xy será receptivo a cambios en diagonal, como sucede en este caso de aquí. El problema que tenemos es pues que lo que queremos es combinarlo lo otro, y para combinarlo la manera de hacerlo que proponen los autores es calculando el determinante de la matriz. En este caso lo que podemos observar, el resultado de aplicar el determinante directamente, en este caso ya hemos filtrado la imagen por las 4 señales y hemos calculado su determinante, multiplicando diagonales, multiplicando diagonal principal, restando La multiplicación de la diagonal a la secundaria y este es el resultado obtenido. Aquí observamos que lo que has resaltado han sido los puntos donde realmente hay cambios significativos en la estructura de la imagen, toda la parte interior del dragón y los perímetros de este. En esta segunda imagen lo que observamos es el efecto de utilizar una Gaussiana, de una sigma mayor, con lo cual es como si estuviéramos mirando la imagen desde más lejos y lo que resalta más serían aquellas estructuras mayores, la mano del dragón entera, los bordes, etcétera. Pues bien, el problema de utilizar este tipo de aproximación es que para calcular el filtro a la convolución con un filtro de este tipo necesitamos n por n, donde n es el tamaño del filtro, n por n multiplicaciones decimales por cada pixel de la imagen. Esto conlleva un costo computacional muy elevado y la alternativa en SURF es utilizar una aproximación a este filtro. Si dibujamos el filtro de la segunda derivada de la Gaussiana como una imagen lo que obtenemos es esta imagen de aquí. Esto sería la representación de este filtro en 3 dimensiones, pero sobre una imagen. En lugar de utilizar este filtro utilizaremos una aproximación de este filtro, y vamos a decir que toda esta zona de aquí es negra y toda esta zona de aquí es positiva y esta zona de aquí es positiva, donde negro es el negativo, y el blanco es el positivo y el gris correspondería a 0. Por tanto hacemos una binarización de este filtro y obtenemos esta aproximación de aquí. Vamos a tener errores, porque no es tan preciso, pero en promedio la señal será significativa respecto a lo cambios locales que aparecen. Este primer ejemplo es el caso de el filtro de segunda derivada con respecto a x, y este es la binarización y la aproximación del filtro de la segunda derivada respecto a x e y, que lo que nos hace es detectar los cambios en diagonal. Lo que conseguimos es que lo único que necesitamos es multiplicar por 2 o por 1 el contenido de los píxeles de las imágenes, que esto simplemente es hacer un desplazamiento. Con lo cual n por n multiplicaciones, conseguimos utilizar n por n sumas enteras por cada pixel de la imagen, con lo cual abarata el coste de cálculo. Podemos ir un poco más allá y conseguir un mejor rendimiento del proceso, en lugar de utilizar n por n sumas vamos a hacer que la operación por pixel nos cueste únicamente 4 operaciones. Para ello, partiendo de la binarización que hemos hecho como paso previo del filtro de la segunda derivada, vamos a utilizar el concepto de imágenes integrales. La imagen integral es una nueva imagen, que llamaremos O de x, en la que para cada punto de la imagen lo que guardamos en ese punto es la suma acumulada de todas las intensidades de la imagen desde el punto de origen hasta el punto de interés. Es decir la suma de todas las intensidades en este rectángulo, de manera que quisiéramos obtener las intensidades, la suma de las intensidades de este rectángulo de aquí, las únicas operaciones necesarias serían una vez calculado la imagen integral de todos los píxeles sería coger el valor acumulado en este punto O de x, restarle el valor acumulado en el punto z. Es decir le restaríamos toda esta parte de aquí, todas las intensidades de aquí, le restaríamos todas estas intensidades de aquí, todas estas intensidades y le sumaríamos estas intensidades de aquí, ya que estas se han restado 2 veces, con lo cual con 3 operaciones obtenemos la suma total de los píxeles que hay en t. Habría una cuarta operación que sería multiplicar los valores por el correspondiente factor que nos indica el filtro aproximado de la segunda derivada. Con ello conseguimos que una operación que en principio era n por n multiplicaciones en decimal coma flotante, pasen a ser 4 operaciones por cada 1 de los píxeles, con el consiguiente aumento de rendimiento y velocidad de respuesta del operador. Otras de las partes interesantes e importantes de cualquier detector es que sea capaz de describir a qué escala un cierto punto local es interesante respecto al contenido de la imagen. Podemos decir que una escala grande no se extraerá zonas de la imagen significativamente importantes en tamaño. Una escala grande nos podría detectar o como un punto de interés toda esta mano. En escalas pequeños lo que tendremos es puntos de interés en estas pequeñas manchas que ven aquí. La manera de conseguirlo en el esquema de SIFT que se vio es utilizar una pirámide de imágenes, con lo cual lo que obteníamos era un filtro constante y lo que variábamos es la imagen de entrada a la que le hacíamos un reescalado, y cada vez teníamos una imagen más pequeña representado puntos de vista más lejanos. Partiendo de la idea de utilizar filtros filtros de aproximados de la segunda derivada con las imágenes integrales vemos que no importa el tamaño del filtro, si el filtro es grande va a tardar lo mismo en calcularse si el filtro es pequeño. Con lo cual la propuesta de SURF es utilizar la imagen original en su tamaño inicial sin tocarlo y lo que modificamos es el tamaño del filtro. El tamaño del filtro será más grande a medida que aumentemos la escala en la cual intentamos detectar los puntos de interés. El coste va a ser el mismo sea cual sea el tamaño del filtro, con lo cual tiene una complejidad que aumenta de forma lineal y no exponencial. Pero el siguiente paso es la detección del punto de interés local dada una imagen, y en este caso se sigue el mismo esquema que se seguía en SIFT. Para cada punto de la imagen lo que hacemos es poner una rejilla centrada en este punto de 3x3, tanto en la capa que estamos mirando, en la escala que estamos mirando, como en la escala inferior y escala superior. Por tanto lo que tendremos es un esquema de este tipo para cada pixel de la imagen en el que analizaremos un vencindaje de 3x3x3, un cubo de 3x3x3, que incluirá la capa, la escala de análisis, la escala superior y la escala inferior. Y lo que nos interesa son aquellos puntos que son máximos en este entorno, si es un punto máximo, entonces sera un punto de interés. Y con esto somos capaces de detectar cuáles son los puntos que son realmente significativos porque tienen una cierta estructura local diferente a su entorno, y cuáles no. Y además podemos detectar cuán de importante son por la magnitud de este máximo que obtenemos aquí. Hasta aquí el detector de SURF y lo que observamos aquí es un ejemplo del comportamiento del lector de SURF respecto al detector SIFT. Lo que vemos es que SIFT es capaz de trabajar con detalles menores que SURF, en este caso no detecta. Por suerte la mayoría de puntos de interés significativos aparecen tanto en una imagen como en otra, y en ciertos casos el evitar estos puntos de pequeñas variaciones locales puede ser una ventaja respecto a SIFT. En este vídeo pues los conceptos claves que hemos visto respecto a detección de puntos de interés por parte de SIFT, es el concepto de Gessiano de una imagen y el uso de el Gessiano, como mecanismo para acelerar el proceso, gracias a los conceptos la aproximación discreta de la segunda derivada y el uso de imagen integral de forma extensiva. Y finalmente la aplicación de la escala sobre el filtro para aumentar aún más la velocidad de aplicación de este operador.