Introducción a SIFT( Scale Invariant Feature Transform)
TAMIZAR representa la Escala Invariante de la Función de Transformar y fue presentado por primera vez en 2004, por D. Lowe de la Universidad de British Columbia. TAMIZAR es invariancia a la escala y rotación de la imagen. Este algoritmo está patentado, por lo que este algoritmo está incluido en el módulo No libre de OpenCV.
Las principales ventajas de SIFT son
- Localidad: las características son locales, por lo que son robustas a la oclusión y al desorden (sin segmentación previa)
- Distintividad: las características individuales se pueden emparejar con una gran base de datos de objetos
- Cantidad: se pueden generar muchas características incluso para objetos pequeños
- Eficiencia: extensibilidad de rendimiento cercano al tiempo real
- : se puede extender fácilmente a una amplia gama de tipos de características diferentes, y cada uno agrega robustez
Esto es parte de una Detección y coincidencia de características de la serie 7. Otros artículos incluyen
- Introducción a la Detección y Coincidencia de Características
- Introducción al Detector de Esquinas Harris
- Introducción a SURF (Características Robustas Aceleradas)
- Introducción a FAST (Características de la Prueba de Segmento Acelerado)
- Introducción a BRIEF (Características Elementales Independientes Robustas Binarias)
- Introducción a ORB (Breve Orientado RÁPIDO y giratorio)
SIFT es un algoritmo bastante complicado. Hay principalmente cuatro pasos involucrados en el algoritmo de TAMIZADO. Los veremos uno por uno.
- Selección de picos de espacio de escala: Ubicación potencial para encontrar características.
- Localización de puntos de teclado: Localización precisa de los puntos de teclado de entidades.
- Asignación de orientación: Asignación de orientación a puntos de teclado.
- Descriptor de puntos de teclado: Describe los puntos de teclado como un vector de alta dimensión.
- Coincidencia de puntos de teclado
Selección de picos de espacio de escala
Los objetos del mundo real solo tienen sentido a una escala determinada. Es posible que veas un terrón de azúcar perfectamente en una mesa. Pero si miramos toda la vía láctea, entonces simplemente no existe. Esta naturaleza multiescala de los objetos es bastante común en la naturaleza. Y un espacio a escala intenta replicar este concepto en imágenes digitales.
La escala espacial de una imagen es una función L(x,y,σ) que se produce a partir de la convolución de un núcleo Gaussiano(Desenfoque) a diferentes escalas con la imagen de entrada. Escala: el espacio está separado en octavas y el número de octavas y escala depende del tamaño de la imagen original. Así que generamos varias octavas de la imagen original. El tamaño de imagen de cada octava es la mitad del anterior.
Desenfoque
Dentro de una octava, las imágenes se desdibujan progresivamente utilizando el operador de desenfoque gaussiano. Matemáticamente ,el «desenfoque» se conoce como la convolución del operador gaussiano y la imagen. El desenfoque gaussiano tiene una expresión u «operador» particular que se aplica a cada píxel. El resultado es la imagen borrosa.
G es el Desenfoque Gaussiano operador y yo es una imagen. Mientras que x, y son las coordenadas de ubicación y σ es el parámetro de «escala». Piensa en ello como la cantidad de desenfoque. Mayor es el valor, mayor es el desenfoque.
PERRO(Diferencia de núcleo Gaussiano)
Ahora vamos a utilizar esas imágenes borrosas para generar otro conjunto de imágenes, la Diferencia de Gaussianas (Perro). Estas imágenes de perros son ideales para descubrir puntos de teclado interesantes en la imagen. La diferencia de Gaussiano se obtiene como la diferencia de desenfoque gaussiano de una imagen con dos σ diferentes, sea σ y kσ. Este proceso se realiza para diferentes octavas de la imagen en la Pirámide gaussiana. Es representada en la siguiente imagen:
en busca de las claves
Hasta ahora, hemos generado una escala de espacio y la escala espacial para calcular la Diferencia de Gaussianas. Estos se utilizan para calcular Laplacianas de aproximaciones gaussianas que son invariantes de escala.
Un píxel en una imagen se compara con sus 8 vecinos, así como 9 píxeles en la siguiente escala y 9 de píxeles en las anteriores escalas. De esta manera, se realizan un total de 26 comprobaciones. Si es un extremo local, es un punto de teclado potencial. Básicamente significa que el punto de teclado está mejor representado en esa escala.
Localización de puntos de clave
Los puntos de clave 0 generados en el paso anterior producen muchos puntos de clave. Algunos de ellos se encuentran a lo largo de un borde, o no tienen suficiente contraste. En ambos casos, no son tan útiles como las características. Así que nos desharemos de ellos. El enfoque es similar al utilizado en el detector de esquinas Harris para eliminar las características de los bordes. Para las características de bajo contraste, simplemente comprobamos sus intensidades.
Usaron la expansión de espacio de escala de la serie Taylor para obtener una ubicación más precisa de los extremos, y si la intensidad en este extremo es menor que un valor de umbral (0.03 según el documento), se rechaza. El perro tiene una respuesta más alta para los bordes, por lo que los bordes también deben eliminarse. Utilizaron una matriz de Hessian 2×2 (H) para calcular la curvatura principal.
la Orientación de la Asignación de
Ahora tenemos legítimos de las claves. Han sido probados para ser estables. Ya sabemos la escala a la que se detectó el punto de teclado (es la misma que la escala de la imagen borrosa). Así que tenemos invariancia de escala. Lo siguiente es asignar una orientación a cada punto de teclado para que sea invariante de rotación.
Un barrio es tomado todo el keypoint ubicación dependiendo de la escala, y la magnitud del gradiente y la dirección se calcula en esa región. Se crea un histograma de orientación con 36 compartimentos que cubren 360 grados. Digamos que la dirección del gradiente en un punto determinado (en la «región de colección de orientación») es de 18,759 grados, luego irá a la bandeja de 10-19 grados. Y la «cantidad» que se agrega a la bandeja es proporcional a la magnitud del gradiente en ese punto. Una vez que haya hecho esto para todos los píxeles alrededor del punto de teclado, el histograma tendrá un pico en algún momento.
El pico más alto en el histograma se toma y cualquier pico por encima del 80% de esto también cuenta para el cálculo de la orientación. Crea puntos de teclado con la misma ubicación y escala, pero en direcciones diferentes. Contribuye a la estabilidad de la correspondencia.
punto clave descriptor
En este punto, cada punto clave tiene una ubicación, escala, orientación. Lo siguiente es calcular un descriptor para la región de imagen local sobre cada punto de teclado que es altamente distintivo e invariante como sea posible a variaciones tales como cambios en el punto de vista y la iluminación.
Para hacer esto, se toma una ventana de 16×16 alrededor del punto de teclado. Se divide en 16 sub-bloques de tamaño 4×4.
For each sub-block, 8 bin orientation histogram is created.
So 4 X 4 descriptors over 16 X 16 sample array were used in practice. 4 X 4 X 8 directions give 128 bin values. It is represented as a feature vector to form keypoint descriptor. Este vector de características presenta algunas complicaciones. Tenemos que deshacernos de ellos antes de finalizar la huella digital.
- Dependencia de rotación El vector de entidad utiliza orientaciones de gradiente. Claramente, si rotas la imagen, todo cambia. Todas las orientaciones de gradiente también cambian. Para lograr la independencia de rotación, la rotación del punto de teclado se resta de cada orientación. Por lo tanto, cada orientación de gradiente es relativa a la orientación del punto de teclado.
- Dependencia de la iluminación Si tenemos números de umbral que son grandes, podemos lograr la independencia de la iluminación. Por lo tanto, cualquier número (de los 128) mayor que 0.2 se cambia a 0.2. Este vector de entidad resultante se normaliza de nuevo. ¡Y ahora tienes un vector de características independiente de iluminación!
Coincidencia de puntos de teclado
Los puntos de teclado entre dos imágenes se comparan identificando a sus vecinos más cercanos. Pero en algunos casos, la segunda coincidencia más cercana puede estar muy cerca de la primera. Puede ocurrir debido al ruido o a otras razones. En ese caso, se toma la relación entre la distancia más cercana y la segunda distancia más cercana. Si es superior a 0,8, se rechazan. Elimina alrededor del 90% de coincidencias falsas, mientras que descarta solo el 5% de coincidencias correctas, según el papel.
Implementación
Pude implementar sift usando OpenCV (3.4). He aquí cómo lo hice:
Github enlace para el código: https://github.com/deepanshut041/feature-detection/tree/master/sift