Comparación de imágenes: algoritmo rápido

Estoy buscando crear una tabla base de imágenes y luego comparar cualquier imagen nueva con eso para determinar si la nueva imagen es un duplicado exacto (o cercano) de la base.

Por ejemplo: si desea reducir el almacenamiento de la misma imagen cientos de veces, puede almacenar una copia y proporcionarle enlaces de referencia. Cuando se ingresa una nueva imagen, desea compararla con una imagen existente para asegurarse de que no sea un duplicado … ¿ideas?

Una idea mía fue reducir a una pequeña miniatura y luego elegir aleatoriamente ubicaciones de 100 píxeles y comparar.

A continuación hay tres enfoques para resolver este problema (y hay muchos otros).

  • El primero es un enfoque estándar en la visión por computadora, la coincidencia de puntos clave. Esto puede requerir algunos conocimientos básicos para implementar, y puede ser lento.

  • El segundo método utiliza solo procesamiento de imágenes elemental, y es potencialmente más rápido que el primer enfoque, y es sencillo de implementar. Sin embargo, lo que gana en comprensibilidad, carece de robustez: la coincidencia falla en imágenes escaladas, giradas o decoloradas.

  • El tercer método es rápido y robusto, pero es potencialmente el más difícil de implementar.

Coincidencia de puntos clave

Mejor que elegir 100 puntos aleatorios es elegir 100 puntos importantes . Ciertas partes de una imagen tienen más información que otras (particularmente en los bordes y esquinas), y estas son las que usted querrá usar para la coincidencia de imágenes inteligentes. Google ” extracción de punto clave ” y ” coincidencia de punto clave ” y encontrará bastantes artículos académicos sobre el tema. En la actualidad , los puntos clave SIFT son posiblemente los más populares, ya que pueden unir imágenes a diferentes escalas, rotaciones e iluminación. Algunas implementaciones de SIFT se pueden encontrar aquí .

Una desventaja de la coincidencia de puntos clave es el tiempo de ejecución de una implementación ingenua: O (n ^ 2m), donde n es el número de puntos clave en cada imagen, ym es el número de imágenes en la base de datos. Algunos algoritmos inteligentes pueden encontrar la coincidencia más cercana más rápido, como quadtrees o partición de espacio binario.


Solución alternativa: método de histogtwig

Otra solución menos robusta pero potencialmente más rápida es construir histogtwigs de características para cada imagen, y elegir la imagen con el histogtwig más cercano al histogtwig de la imagen de entrada. Implementé esto como estudiante universitario, y usamos 3 histogtwigs de color (rojo, verde y azul) y dos histogtwigs de textura, dirección y escala. Voy a dar los detalles a continuación, pero debería tener en cuenta que esto solo funcionó bien para emparejar imágenes MUY similares a las imágenes de la base de datos. Las imágenes reescaladas, giradas o descoloridas pueden fallar con este método, pero pequeños cambios como el recorte no romperán el algoritmo

La computación de los histogtwigs de color es sencilla: simplemente elija el rango para sus cubos de histogtwig, y ​​para cada rango, cuente el número de píxeles con un color en ese rango. Por ejemplo, considere el histogtwig “verde”, y suponga que elegimos 4 cubos para nuestro histogtwig: 0-63, 64-127, 128-191 y 192-255. Luego, para cada píxel, observamos el valor verde y agregamos un conteo al cubo apropiado. Cuando terminamos el recuento, dividimos el total de cada cubo por el número de píxeles en la imagen completa para obtener un histogtwig normalizado para el canal verde.

Para el histogtwig de dirección de texturas, comenzamos realizando la detección de bordes en la imagen. Cada punto de borde tiene un vector normal apuntando en la dirección perpendicular al borde. Cuantizamos el ángulo del vector normal en uno de los 6 segmentos entre 0 y PI (ya que los bordes tienen una simetría de 180 grados, convertimos los angularjs entre -PI y 0 para que estén entre 0 y PI). Después de contar el número de puntos de borde en cada dirección, tenemos un histogtwig no normalizado que representa la dirección de la textura, que normalizamos al dividir cada cubo por el número total de puntos de borde en la imagen.

Para calcular el histogtwig de escala de textura, para cada punto de borde, medimos la distancia hasta el punto de borde más cercano con la misma dirección. Por ejemplo, si el punto de borde A tiene una dirección de 45 grados, el algoritmo camina en esa dirección hasta que encuentra otro punto de borde con una dirección de 45 grados (o dentro de una desviación razonable). Después de calcular esta distancia para cada punto de borde, volcamos esos valores en un histogtwig y lo normalizamos dividiéndolo por el número total de puntos de borde.

Ahora tiene 5 histogtwigs para cada imagen. Para comparar dos imágenes, tome el valor absoluto de la diferencia entre cada categoría de histogtwig y luego sume estos valores. Por ejemplo, para comparar imágenes A y B, calcularíamos

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 

para cada cubo en el histogtwig verde, y repita para los otros histogtwigs, y luego resum todos los resultados. Cuanto menor sea el resultado, mejor será el partido. Repita para todas las imágenes en la base de datos, y la coincidencia con el resultado más pequeño gana. Probablemente quieras tener un umbral, arriba del cual el algoritmo concluye que no se encontró ninguna coincidencia.


Tercera elección: puntos clave + árboles de decisión

Un tercer enfoque que probablemente sea mucho más rápido que los otros dos es el uso de bosques de texto semánticos (PDF). Esto implica extraer puntos clave simples y utilizar árboles de decisión de una colección para clasificar la imagen. Esto es más rápido que la simple coincidencia de puntos clave SIFT, ya que evita el costoso proceso de coincidencia, y los puntos clave son mucho más simples que SIFT, por lo que la extracción del punto clave es mucho más rápida. Sin embargo, conserva la invarianza del método SIFT para la rotación, la escala y la iluminación, una característica importante de la que carecía el método del histogtwig.

Actualización :

Mi error: el trabajo de Semantic Texton Forests no trata específicamente de la coincidencia de imágenes, sino del etiquetado de regiones. El documento original que hace coincidir es este: Reconocimiento de puntos clave utilizando árboles aleatorizados . Además, los documentos a continuación continúan desarrollando las ideas y representan el estado del arte (c. 2010):

  • Reconocimiento rápido de Keypoint con helechos aleatorios : más rápido y escalable que Lepetit 06
  • BREVE: Binary Robust Independent Características elementales : menos robustas pero muy rápidas: creo que el objective aquí es la coincidencia en tiempo real en teléfonos inteligentes y otras computadoras de mano.

El mejor método que conozco es utilizar un Hash Perceptual. Parece que hay una buena implementación de código abierto de dicho hash disponible en:

http://phash.org/

La idea principal es que cada imagen se reduzca a un pequeño código hash o ‘huella digital’ mediante la identificación de características destacadas en el archivo de imagen original y una representación compacta de esas características (en lugar de mezclar los datos de imagen directamente). Esto significa que la tasa de falsos positivos es mucho más reducida que con un enfoque simplista, como reducir las imágenes a una imagen diminuta con tamaño de huella digital y comparar huellas digitales.

phash ofrece varios tipos de hash y se puede usar para imágenes, audio o video.

Esta publicación fue el punto de partida de mi solución, muchas buenas ideas aquí, así que pensé que compartiría mis resultados. La idea principal es que he encontrado una forma de evitar la lentitud de la coincidencia de imágenes basada en puntos clave mediante la explotación de la velocidad de Phash.

Para la solución general, es mejor emplear varias estrategias. Cada algoritmo es más adecuado para ciertos tipos de transformaciones de imagen y puede aprovecharlo.

En la parte superior, los algoritmos más rápidos; en la parte inferior, el más lento (aunque más preciso). Puede omitir los lentos si encuentra una buena coincidencia en el nivel más rápido.

  • archivo basado en hash (md5, sha1, etc.) para duplicados exactos
  • hashing perceptual (phash) para imágenes reescaladas
  • basado en características (SIFT) para imágenes modificadas

Estoy teniendo muy buenos resultados con Phash. La precisión es buena para imágenes redimensionadas. No es bueno para imágenes (perceptualmente) modificadas (recortadas, giradas, reflejadas, etc.). Para hacer frente a la velocidad de hash, debemos emplear una memoria caché / base de datos de disco para mantener los valores hash para el pajar.

Lo realmente bueno de Phash es que una vez que construyes tu base de datos hash (que para mí es de aproximadamente 1000 imágenes / seg), las búsquedas pueden ser muy, muy rápidas, en particular cuando puedes mantener toda la base de datos hash en la memoria. Esto es bastante práctico ya que un hash tiene solo 8 bytes.

Por ejemplo, si tiene 1 millón de imágenes, requerirá una matriz de 1 millón de valores hash de 64 bits (8 MB). ¡En algunas CPU esto cabe en el caché L2 / L3! En el uso práctico, he visto comparar un corei7 a más de 1 Giga-hamm / seg, solo es cuestión de ancho de banda de memoria para la CPU. Una base de datos de 1 mil millones es práctica en una CPU de 64 bits (se necesitan 8GB de RAM) y las búsquedas no excederán 1 segundo.

Para las imágenes modificadas / recortadas parecería que una característica invariante de transformación / detector de punto clave como SIFT es el camino a seguir. SIFT producirá buenos puntos clave que detectarán crop / rotate / mirror, etc. Sin embargo, la comparación del descriptor es muy lenta en comparación con la distancia de hamming utilizada por phash. Esta es una gran limitación. Hay muchas cosas que hacer, ya que hay descriptores IxJxK máximos que se pueden comparar para buscar una imagen (I = número de imágenes de pajar, J = puntos clave de destino por imagen de pajar, K = puntos clave de destino por imagen de aguja).

Para evitar el problema de la velocidad, traté de usar phash alrededor de cada punto clave encontrado, usando el tamaño / radio de la función para determinar el sub-rectángulo. El truco para hacer que esto funcione bien es boost / reducir el radio para generar diferentes niveles subsiguientes (en la imagen de la aguja). Normalmente, el primer nivel (sin escalar) coincidirá, sin embargo, a menudo requiere un poco más. No estoy 100% seguro de por qué funciona esto, pero me imagino que habilita características que son demasiado pequeñas para que Phash funcione (las imágenes de Phash escalan hasta 32×32).

Otro problema es que SIFT no distribuirá los puntos clave de manera óptima. Si hay una sección de la imagen con muchos bordes, los puntos clave se agruparán allí y no se obtendrá ninguno en otra área. Estoy usando GridAdaptedFeatureDetector en OpenCV para mejorar la distribución. No estoy seguro de cuál es el tamaño de cuadrícula mejor, estoy usando una cuadrícula pequeña (1×3 o 3×1 dependiendo de la orientación de la imagen).

Es probable que desee escalar todas las imágenes de pajar (y la aguja) a un tamaño menor antes de la detección de características (yo uso 210px a lo largo de la dimensión máxima). Esto reducirá el ruido en la imagen (siempre es un problema para los algoritmos de visión por computadora), también enfocará el detector en características más destacadas.

Para las imágenes de personas, puede probar la detección de rostros y usarla para determinar el tamaño de la imagen a escalar y el tamaño de la cuadrícula (por ejemplo, la cara más grande escalada a 100px). El detector de características cuenta para múltiples niveles de escala (usando pirámides) pero hay una limitación de cuántos niveles usará (esto es sintonizable, por supuesto).

Es probable que el detector de punto clave funcione mejor cuando devuelve menos que la cantidad de características que deseaba. Por ejemplo, si pide 400 y recupera 300, eso está bien. Si obtiene 400 de vuelta cada vez, probablemente algunas buenas características tuvieron que quedar fuera.

La imagen de aguja puede tener menos puntos clave que las imágenes de pajar y aún así obtener buenos resultados. Agregar más no necesariamente te brinda grandes ganancias, por ejemplo, con J = 400 y K = 40, mi índice de acierto es de aproximadamente 92%. Con J = 400 y K = 400, la tasa de aciertos solo sube al 96%.

Podemos aprovechar la velocidad extrema de la función Hamming para resolver el escalamiento, la rotación, el reflection, etc. Se puede utilizar una técnica de pase múltiple. En cada iteración, transforma los sub-rectangularjs, vuelve a hash, y ejecuta la función de búsqueda nuevamente.

Tengo una idea, que puede funcionar y lo más probable es que sea muy rápida. Puede submuestrear una imagen para que diga una resolución de 80×60 o similar, y convertirla a escala de grises (después del submuestreo será más rápido). Procese ambas imágenes que quiera comparar. Luego ejecute la sum normalizada de las diferencias cuadradas entre dos imágenes (la imagen de la consulta y cada una desde el db), o incluso una correlación cruzada normalizada mejor, que da una respuesta más cercana a 1, si ambas imágenes son similares. Entonces, si las imágenes son similares, puede proceder a técnicas más sofisticadas para verificar que sean las mismas imágenes. Obviamente, este algoritmo es lineal en términos de cantidad de imágenes en su base de datos, por lo que a pesar de que va a ser muy rápido hasta 10000 imágenes por segundo en el hardware moderno. Si necesita invariancia a la rotación, entonces se puede calcular un gradiente dominante para esta imagen pequeña, y luego todo el sistema de coordenadas se puede girar a la orientación canónica, aunque esto será más lento. Y no, no hay invarianza a escala aquí.

Si desea algo más general o utilizar grandes bases de datos (millones de imágenes), entonces debe considerar la teoría de recuperación de imágenes (un montón de documentos aparecieron en los últimos 5 años). Hay algunos indicadores en otras respuestas. Pero podría ser excesivo, y el enfoque sugerido de histogtwig hará el trabajo. Aunque creo que la combinación de muchos enfoques diferentes será aún mejor.

Como señaló Cartman, puedes usar cualquier tipo de valor hash para encontrar duplicados exactos.

Un punto de partida para encontrar imágenes cercanas podría estar aquí . Esta es una herramienta utilizada por las empresas de CG para verificar si las imágenes renovadas aún muestran esencialmente la misma escena.

Creo que reducir el tamaño de la imagen a casi un tamaño de icono, digamos 48×48, luego convertir a escala de grises, y luego tomar la diferencia entre píxeles, o Delta, debería funcionar bien. Debido a que estamos comparando el cambio en el color del píxel, en lugar del color del píxel real, no importará si la imagen es un poco más clara o más oscura. Los grandes cambios importan ya que los píxeles que se vuelven demasiado claros / oscuros se perderán. Puede aplicar esto en una fila, o tantas como desee para boost la precisión. A lo sumo tendrías 47×47 = 2,209 restas para hacer para formar una clave comparable.

Escoger 100 puntos al azar podría significar que imágenes similares (o incluso ocasionalmente diferentes) se marcarían como iguales, lo que supongo que no es lo que quieres. Los hashes MD5 no funcionarían si las imágenes fueran de formatos diferentes (png, jpeg, etc.), tuvieran diferentes tamaños o tuvieran metadatos diferentes. Reducir todas las imágenes a un tamaño más pequeño es una buena opción, hacer una comparación píxel por píxel no debería tomar demasiado tiempo siempre que use una buena biblioteca de imágenes / lenguaje rápido, y el tamaño sea lo suficientemente pequeño.

Podrías tratar de hacerlos pequeños, luego si son lo mismo realizar otra comparación en un tamaño más grande, podría ser una buena combinación de velocidad y precisión …

Si tiene una gran cantidad de imágenes, busque en un filtro Bloom , que usa múltiples valores hash para obtener un resultado probabilístico pero eficiente. Si el número de imágenes no es enorme, entonces un hash criptográfico como md5 debería ser suficiente.