[MUSIC] En el vídeo anterior explicamos la parte de detección de puntos de interés en SIFT. Lo que vimos es que como resultado de la detección, obtenemos un conjunto de puntos de interés en toda la imagen, que se corresponden con zonas relevantes de la imagen. Recordemos primero que para la detección, se se utiliza una pirámide de imágenes con diferentes niveles de resolución y también con varias escalas de suavizado en cada nivel. Por lo tanto cada punto de interés va a tener asociado el nivel de la pirámide y la escala a la que ha sido detectado. y de esta manera hacemos posible que la detección sea invariante al tamaño del objeto en la imagen. Es decir, vamos a poder detectar los mismos puntos de interés independientemente del tamaño del objeto. Así mismo, el detector nos asegura una alta repetitividad en la detección. Lo que quiere decir que en imágenes diferentes donde aparecerá el mismo objeto con cambios en el punto de vista o en la iluminación, vamos a poder detectar mayoritariamente los mismos puntos de interés. Bien, ahora que you sabemos como localizar puntos de interés en una imagen, el siguiente paso va a ser obtener una descripción de cada uno de estos puntos. Normalmente esta descripción va a ser un vector numérico que nos va a dar una representación de la información local que tenemos en la imagen en una zona que se define alrededor del punto de interés. En los vídeos próximos veremos como esta representación local de cada punto de interés se puede agregar en una única representación global de toda la imagen. Que será la utilizaremos luego para la clasificación. Pero lo que veremos en este vídeo es como se calcula esta descripción local de cada punto de interés en SIFT. you vimos que SIFT tiene dos partes, la parte de detección y la parte de descripción. Por lo que respecta a la parte de descripción, que es la que explicaremos en este vídeo, podemos decir que en general cumple con las propiedades que nos interesa de cualquier descriptor. Por un lado que sea compacto, es decir que ocupe el mínimo espacio de memoria posible. Por otro lado, que sea robusto al ruido o a otras variaciones de la imagen. Como por ejemplo el punto de vista o la iluminación que obtengamos la misma descripción independientemente de estas variaciones. Y por último que sea suficientemente discriminativo. Es decir que objetos diferentes tengan representaciones que sean también lo más diferente posibles. Vista esta introducción, vamos a ver como empezamos a calcular el descriptor en SIFT. El primer paso va a ser determinar la zona de la imagen que utilizaremos para calcular esa descripción. Sabemos que cada punto de interés se ha detectado a un determinado nivel de la pirámide y dentro de ese nivel de la pirámide, a cierta escala de suavizado. Por lo tanto, lo primero que vamos a hacer es seleccionar la imagen que corresponde al nivel de la pirámide y a la escala de suavizado del punto de interés. Una vez determinada esta imagen, la zona para calcular el descriptor se define como una ventana que será siempre del mismo tamaño, de tamaño fijo, y centrada alrededor del punto de interés. De esta forma, en los niveles más bajos de la pirámide, vamos a describir regiones pequeñas en la imagen original pero, sin embargo a medida que vamos subiendo por la pirámide. Como el tamaño de la imagen va disminuyendo y la ventana de descripción se mantiene fija. Cada vez vamos a ser capaces de describir regiones más grandes en la imagen original. De esta forma, el área que utilizamos para calcular el descriptor se va adaptando a la escala en que se ha detectado cada punto de interés en una forma muy natural y permite que el descriptor sea invariante al tamaño el objeto. Comentar que en la configuración estándar del descriptor, el tamaño fijo de esta ventana se determina en 16x16 pixeles. Ahora que you sabemos cómo se define la región de la imagen que utilizamos alrededor de cada punto de interés para calcular el descriptor. Vamos a empezar a ver cómo se hace este cálculo. El descriptor se basa en el concepto de gradiente, que es un concepto muy utilizado en visión por computador. Vamos a empezar, pues, a explicar qué es y cómo se calcula el gradiente de una imagen. El gradiente se define en cada punto de la imagen como el cambio en la intensidad de la imagen en una determinada dirección. Aquella dirección es la que este cambio de intensidad alrededor del punto es máximo. Por lo tanto, el gradiente queda definido por dos valores. La dirección en la que el cambio local de intensidad es máximo y la magnitud de dicho cambio. Por ejemplo, en este primer punto de aquí de la imagen, la dirección donde se produce el mayor cambio de intensidad es en la dirección horizontal. En este segundo pixel, es la dirección vertical. Mientras que en este pixel central, se produce en la dirección diagonal. El gradiente se puede calcular muy fácilmente a partir de la diferencia de intensidad de los pixeles adyacentes en la dirección horizontal y en la dirección vertical. Si por ejemplo, tomamos como referencia este pixel central, la diferencia horizontal será el valor que tenemos a la derecha menos el valor que tenemos a la izquierda. En este caso, 255. La diferencia en vertical será el valor que tenemos arriba menos el valor que tenemos abajo, también 255. Para este segundo pixel, en este caso la diferencia en X será también 255, pero la diferencia en vertical será cero. Dado cualquiera de estos pixeles, las diferencias en X y en Y se pueden poner en un eje de coordenadas y estos dos valores en un eje coordenadas nos van a definir un vector. Este vector es lo que llamamos el vector gradiente. Y el ángulo de este vector con el eje horizontal nos va a dar la orientación del gradiente y la longitud del vector nos va a dar la magnitud del gradiente. Estos valores se pueden calcular fácilmente también utilizando estas expresiones de aquí. Así por ejemplo, en este pixel central que hemos utilizado antes, la orientación del gradiente aplicando esa fórmula nos va a dar 45 grados y en este segundo pixel que habíamos utilizado de ejemplo nos va a dar cero grados. En estas imágenes tenemos un ejemplo del cálculo del gradiente a partir de una imagen vemos en primer lugar el cálculo del gradiente en dirección horizontal. Las diferencias en el eje horizontal. Y vemos que en las diferencias en el horizontal tenemos una alta respuesta en todos aquellos tonos de la imagen donde tenemos un cambio de intensidad en dirección horizontal. Si analizamos el resultado del cálculo del gradiente de diferencias en dirección vertical. Vemos que tenemos una alta respuesta en aquellas zonas de la imagen donde tenemos cambios de intensidad en la dirección vertical. Finalmente en esta última imagen vemos el valor de la magnitud del gradiente, calculado con la fórmula anterior, combinando las diferencias tanto en el horizontal como en el vertical. Vemos que tenemos altas respuestas en cualquier zona de la imagen donde tenemos algún cambio de intensidad. Estos cambios de intensidad, en general, corresponden con los contornos de los objetos que tenemos en la imagen. Y el contorno de los objetos nos da información relevante para describir estas imágenes. Hasta aquí el gradiente nos da un valor de magnitud y orientación de cada uno de los pixeles de la región de interés. Lo que tenemos que conseguir ahora es agregar los valores de los gradientes de todos los píxeles en la región, en una única representación compacta de toda la región. La forma de conseguirlo será mediante un histograma de orientaciones del gradiente. El histograma es también una herramienta muy habitual en visión por computador. Y en este caso nos va a permitir obtener estadísticas de la orientación de los gradientes. Para calcular este histograma, lo primero que tenemos que hacer es dividir el rango de orientaciones de cero a 360 grados en un número fijo de intervalos. Por ejemplo, en este caso en ocho intervalos que nos da esta división que vemos aquí. Para cada píxel de la región ahora podemos coger su gradiente y asignarle el intervalo correspondiente en función de su orientación. Así por ejemplo, si tomamos este primer píxel de aquí, y suponemos que su orientación estuviese entre 270 y 315 grados, pues quedaría asignado al séptimo intervalo. Mientras que este segundo píxel de aquí, suponiendo que su orientación está entre cero y 45, quedaría asignado al primer intervalo. Con la asignación de todos los píxeles a su intervalo correspondiente, you podemos calcular el histograma. El histograma va a tener tantos valores como intervalos hayamos utilizado para dividir la orientación. Y cada valor del histograma va a ser la suma de las magnitudes de todos los gradientes que han quedado asignados a ese intervalo. Matemáticamente, lo expresamos con esta expresión que vemos aquí. Donde vemos que para un determinado valor k del histograma, acumulamos la suma de las magnitudes de todos los píxeles que han quedado asignados a ese intervalo. Y esto lo podemos ver repasando la fórmula de w donde vemos que toma valor uno, únicamente para los píxeles que corresponden al intervalo k del histograma. Y sin embargo tiene valor cero para todos los otros intervalos. A este cálculo del histograma, le vamos a añadir un paso adicional para poder dar más importancia a los píxeles que están situados cerca del centro de la región, y por lo tanto vamos a suponer que son más estables. Y dar menos importancia a los píxeles que están situados en los bordes, en la zona exterior de la región de interés, que suponemos que pueden ser más sensibles a ruido y a variaciones. La forma en que se introduce esta modificación, es ponderando el valor de la magnitud del gradiente en el histograma que habíamos visto antes, por el resultado de aplicar una función Gaussiana. Tal como la vimos en un vídeo anterior, que es calculada a partir de las coordenadas de cada píxel en la región de interés. you sabemos que la función Gaussiana, de esta manera, nos va dar un peso mayor a los píxeles cercanos al centro y nos va a dar un valor menor, por lo tanto un peso menor, a los píxeles que están situados en la zona más exterior de la región. El histograma de orientaciones nos da información acerca de la distribución de las orientaciones del gradiente en una determinada región. Por lo tanto, en primer lugar, lo podemos utilizar para determinar la orientación dominante en la región. Y esta orientación dominante se va a utilizar en el cálculo del descriptor para rotar la zona de interés, de manera que conseguiremos una descripción que sea invariante a rotación. Para determinar esta orientación dominante, se utiliza un histograma de orientaciones con 36 intervalos. Y se determina que la orientación dominante, corresponde al máximo global del histograma, este valor de aquí. Para evitar sensibilidad a variaciones y reducir el efecto de ruidos, se van a considerar otras orientaciones alternativas en aquellos otros puntos máximos del histograma que superen el 80% del máximo global. En este caso, este segundo máximo sería una orientación alternativa. Los otros máximos no lo serían, you que no superan el 80% del máximo global. El descriptor se va a calcular para todas las orientaciones dominantes que se han detectado. Una vez determinada la orientación dominante, la región de interés queda rotada, de forma que queda alineada con esa orientación dominante. En los ejemplos que mostraremos, you supondremos que las regiones han quedado orientadas en dirección vertical. Si tenemos orientaciones diferentes, solo tendremos que rotar las coordenadas de los píxeles por la orientación que corresponda. Bien, para calcular el descriptor, el primer paso va a ser dividir la región de interés en una cuadrícula de nxn celdas de igual tamaño. En la configuración estándar que es la que mostramos aquí, esta división es en 16 celdas. Cuatro en horizontal y cuatro en vertical. Para cada una de estas celdas, vamos a calcular un histograma de orientaciones exactamente igual como hemos explicado antes. En la configuración estándar se utilizan ocho intervalos en el histograma de orientación. Y para calcular cada uno de estos histogramas para cada una de las celdas, vemos que utilizamos únicamente los píxeles que pertenecen en esta primera configuración a la celda correspondiente. El descriptor final es la concatenación de los histogramas de cada una de las celdas. Lo que nos da un descriptor final en el que tenemos 16 histogramas. Cada uno de los histogramas tiene ocho orientaciones, y por lo tanto nos da un descriptor con 128 valores o dimensiones. Esta configuración básica del descriptor, se va a modificar ligeramente para reducir la sensibilidad al ruido y a pequeñas variaciones de los gradientes. Tanto en orientación como en la posición del gradiente dentro de la región de interés. Si nos fijamos, podemos observar que gradientes muy parecidos en orientación, o posicionados muy cerca dentro de la región de interés, pueden quedar asignados a intervalos diferentes dentro del histograma. O bien a celdas diferentes dentro del descriptor, como vemos en estos ejemplos, tanto en orientación como en la posición dentro de la celda. Esto podría provocar que en otra imagen de la misma clase, con ruido o con pequeñas variaciones, la descripción final fuese diferente you que gradientes equivalentes quedarían asignados a intervalos o a celdas diferentes. Para solucionarlo se propone cambiar la forma en que se asigna cada gradiente a un intervalo o a una celda. De forma que cada gradiente quedará asignado no únicamente a un sólo intervalo o celda. Sino que su aportación se va a interpolar entre varios intervalos y varias celdas vecinas. Como esta interpolación se va a realizar tanto en orientación como en la coordenada x, como en la coordenada y, este método se conoce como interpolación trilineal. Vamos a verlo primero en el caso de la orientación. Cada gradiente se va a repartir entre el intervalo al que le corresponde por asignación y el intervalo siguiente. En este caso entre el segundo y el tercer intervalo. Al intervalo teórico del gradiente, se le va a asignar un peso que va a ser esta distancia de aquí. La distancia entre la orientación y el final del intervalo, y esta distancia, este peso, es decreciente, va disminuyendo a medida que nos alejamos del origen del intervalo. Al intervalo siguiente se le va a asignar un peso complementario de forma que entre los dos sumen uno. Para el resto de intervalos del histograma el peso de ese gradiente va a ser cero. Igual que antes, cada valor del histograma va a ser la suma de las magnitudes de todos los gradientes asignados al intervalo correspondiente, ponderados por la función Gaussiana. Pero en este caso se le añade la ponderación por este peso relativo que nos da el peso relativo de la asignación del gradiente al intervalo. Para distribuir un gradiente entre celdas vecinas vamos a actuar de forma muy parecida. Vamos a ver sólo el caso de la coordenada x you que el caso de la coordenada y es equivalente. Igual que antes, cada píxel se va a repartir entre su celda teórica y la celda siguiente. Igual que antes, a la celda que correspondería por la asignación teórica se le va a asignar un peso, este peso de aquí que corresponde con la distancia. Esta delta x que corresponde con la distancia del píxel al final de la celda, de manera que va a ser un valor decreciente a medida que nos alejamos del origen de la celda. A la celda siguiente, se le asigna un peso que es complementario de forma de que entre los dos sumen uno, igual que con la orientación y cero para el resto de las celdas. Con esta nueva formulación, el valor de un histograma en una de las celdas deja de acumularse sólo para los pixeles de esa celda, sino que también tiene en cuenta los valores de las celdas vecinas. Por lo tanto el sumatorio es para todos los pixeles de la imagen. Igual que con la orientación, cada píxel tiene una determinada contribución a cada celda en función de su posición en x, y de su posición en y. Por lo tanto, la fórmula para calcular el valor del histograma tenemos la acumulación de la magnitud del gradiente, ponderado por la función gaussiana. Pero en este caso también lo tenemos ponderado por la contribución en la coordenada x, por la contribución en la coordenada y, y también por la contribución del gradiente al intervalo del histograma. Finalmente, una vez calculados los histogramas de todas las celdas y construido el vector final como concatenación de todos estos histogramas, el último paso en el cálculo del descriptor, va a consistir en normalizarlo, para reducir efectos de variaciones producidas por cambios de iluminación. El primer aspecto a tener en cuenta, es que el descriptor you es invariante a cambios en el brillo global de la imagen, you que estos cambios se traducen simplemente en sumar una constante a la intensidad de todos los pixeles. Por lo tanto no afectan ni a la dirección, ni a la magnitud del gradiente, you que se cancelan cuando calculamos las diferencias de intensidades. Cuando tenemos un cambio de constraste, el efecto es multiplicar la intensidad de todos los pixeles por una constante. En este caso la orientación no queda afectada, pero la magnitud del gradiente sí que queda multiplicada por esta constante. Este efecto se puede compensar normalizando todo el descriptor con su norma L2. Recordamos que la norma L2 es simplemente la raíz cuadrada de la suma de los componentes del vector al cuadrado. Dividendo por la norma obtenemos un nuevo vector con norma L2 igual a uno, en el que se cancela el efecto del cambio de contraste. Para cambios no lineales en la iluminación que pueden producir mayores variaciones en el gradiente, la solución que se adopta es recortar todos los valores del vector, que sean mayores que cero coma dos. Estos valores simplemente se dejan en cero coma dos, con lo que se minimiza el efecto de gradientes muy grandes que pudiesen estar provocados por estos cambios de iluminación. Finalmente, el vector recortado se re-normaliza otra vez con la norma L2. En estas imágenes podemos ver un ejemplo del cálculo del descriptor. En la imagen de la izquierda vemos una representación del descriptor que se obtiene a partir de un único punto de interés. Podemos ver el tamaño de la región que se ha definido para calcular el descriptor a partir de la escala en la que sería detectado este punto de interés. Podemos ver también como la región se ha rotado utilizando la orientación dominante. La flecha en cada una de las celdas corresponde con la orientación dominante del histograma para esa celda en concreto. En la imagen de la derecha podemos ver la misma representación para todos los puntos de interés. Aunque la imagen no sea del todo clara podemos observar la diferencia en el tamaño de la región de interés en función de la escala de detección. Por ejemplo, para este punto tenemos definida esta ventana de aquí, mientras que para este punto de interés a una escala menor la región de interés captura una zona menor de la imagen. Y mientras que esta zona captura un tamaño intermedio de la imagen. También vemos como cada región se orienta diferente en función de la orientación dominante en la región. Para resumir, en este vídeo hemos explicado como podemos obtener una descripción, para cada uno de los puntos de interés que se detectan con el método que vimos en el vídeo anterior. Nos hemos fijado en el concepto de gradiente como idea básica sobre la que se construye el descriptor. A partir del concepto de gradiente, hemos visto como se puede construir un histograma de las orientaciones del gradiente, para una zona de la imagen. Y hemos visto como el descriptor final, se obtiene combinando histogramas de orientaciones calculados en cada una de las celdas de una cuadrícula. Minimizando a la vez los efectos del ruido y de variaciones, utilizando lo que hemos explicado como interpolación trilineal, para asignar cada gradiente a diferentes intervalos y celdas. En los próximos vídeos de esta semana, lo que veremos es cómo podemos utilizar esta descripción de puntos de interés para comparar y clasificar la imágenes. Lo que explicaremos en esta primera semana, es un primer esquema de clasificación básico y muy simple, pero que en general va a tener un rendimiento bajo en la mayoría de los casos. Pero que nos va a servir como punto de partida para poder en el resto de las semanas del curso, ir introduciendo mejoras en cada uno de los pasos del esquema.
