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

Estoy buscando crear una tabla base de imágenes y luego comparar cualquier imagen nueva con esa 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 proporcionar 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 era reducir a una miniatura pequeña 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 visión por computadora, coincidencia de puntos clave. Esto puede requerir algunos conocimientos básicos para implementar, y puede ser lento.

• El segundo método usa solo el procesamiento de imagen elemental, y es potencialmente más rápido que el primer enfoque, y es fácil de implementar. Sin embargo, lo que gana en comprensibilidad, carece de robustez: la coincidencia falla en imágenes a escala, rotadas o descoloridas.

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

Keypoint Matching

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 querrá usar para la coincidencia inteligente de imágenes. Google " extracción de puntos clave " y " coincidencia de puntos clave " y encontrará bastantes artículos académicos sobre el tema. En estos días, los puntos clave de SIFT son posiblemente los más populares, ya que pueden combinar imágenes bajo 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 los cuadrantes o la partición de espacio binario.

Solución alternativa: método de histograma

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

Calcular los histogramas de color es sencillo: simplemente elija el rango para los cubos de histograma y, para cada rango, calcule el número de píxeles con un color en ese rango. Por ejemplo, considere el histograma "verde" y suponga que elegimos 4 cubos para nuestro histograma: 0-63, 64-127, 128-191 y 192-255. Luego, para cada píxel, observamos el valor verde y agregamos una cuenta al cubo apropiado. Cuando terminamos de contar, dividimos el total de cada cubeta por el número de píxeles en toda la imagen para obtener un histograma normalizado para el canal verde.

Para el histograma de dirección de textura, comenzamos realizando la detección de bordes en la imagen. Cada punto de borde tiene un vector normal que apunta en la dirección perpendicular al borde. Cuantificamos el ángulo del vector normal en uno de los 6 cubos entre 0 y PI (dado que los bordes tienen una simetría de 180 grados, convertimos ángulos 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 histograma no normalizado que representa la dirección de la textura, que normalizamos dividiendo cada cubo por el número total de puntos de borde en la imagen.

Para calcular el histograma de la escala de textura, para cada punto de borde, medimos la distancia al siguiente 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 encontrar 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 histograma y lo normalizamos dividiendo por el número total de puntos de borde.

Ahora tiene 5 histogramas para cada imagen. Para comparar dos imágenes, toma el valor absoluto de la diferencia entre cada segmento de histograma y luego suma estos valores. Por ejemplo, para comparar las imágenes A y B, calcularíamos

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

para cada segmento en el histograma verde, y repita para los otros histogramas, y luego resuma todos los resultados. Cuanto más pequeño 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 desee tener un umbral, por encima del cual el algoritmo concluya que no se encontró coincidencia.

Tercera opció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 texto semántico en bosques (PDF). Esto implica extraer puntos clave simples y usar árboles de decisión de 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 de puntos clave es mucho más rápida. Sin embargo, conserva la invariancia del método SIFT con respecto a la rotación, la escala y la iluminación, una característica importante de la que carecía el método de histograma.

Actualizar :

Mi error: el papel de los bosques semánticos de Texton no se refiere específicamente a la coincidencia de imágenes, sino al etiquetado regional. El artículo original que coincide es este: Reconocimiento de puntos clave utilizando árboles aleatorios . Además, los siguientes documentos continúan desarrollando las ideas y representan el estado del arte (c. 2010):

• Reconocimiento rápido de puntos clave utilizando helechos aleatorios : más rápido y más escalable que Lepetit 06
• BREVE: Características elementales independientes binarias robustas - menos robustas pero muy rápidas - Creo que el objetivo aquí es la correspondencia en tiempo real en teléfonos inteligentes y otras computadoras de mano

El mejor método que conozco es usar 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' al identificar características sobresalientes en el archivo de imagen original y generar una representación compacta de esas características (en lugar de dividir directamente los datos de la imagen). Esto significa que la tasa de falsos positivos se reduce mucho en un enfoque simplista, como reducir las imágenes a una pequeña imagen del tamaño de una huella digital y comparar las huellas digitales.

Phash ofrece varios tipos de hash y puede usarse 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é en compartir mis resultados. La idea principal es que he encontrado una manera 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 el 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 la más lenta (aunque más precisa). Puede omitir los lentos si se encuentra una buena coincidencia en el nivel más rápido.

• basado en hash de archivo (md5, sha1, etc.) para duplicados exactos
• hashing perceptual (phash) para imágenes redimensionadas
• basado en funciones (SIFT) para imágenes modificadas

Estoy teniendo muy buenos resultados con phash. La precisión es buena para las imágenes reescaladas. No es bueno para imágenes modificadas (perceptualmente) (recortadas, rotadas, reflejadas, etc.). Para lidiar con la velocidad de hash debemos emplear un caché de disco / base de datos para mantener los hashes para el pajar.

Lo realmente bueno de phash es que una vez que construye su 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 puede 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ía 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 una comparación corei7 a más de 1 Giga-hamm / seg, solo es una cuestión de ancho de banda de memoria para la CPU. ¡Una base de datos de 1 mil millones de imágenes es práctica en una CPU de 64 bits (se necesitan 8 GB de RAM) y las búsquedas no excederán 1 segundo!

Para imágenes modificadas / recortadas, parecería 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 recorte / rotación / espejo, 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 limitación importante. Hay muchas comparaciones que hacer, ya que el descriptor IxJxK máximo se compara con la búsqueda de una imagen (I = num imágenes de pajar, J = puntos clave de destino por imagen de pajar, K = puntos clave de objetivo por imagen de aguja).

Para evitar el problema de la velocidad, intenté 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 hacer crecer / reducir el radio para generar diferentes niveles sub-rect (en la imagen de la aguja). Por lo general, el primer nivel (sin escala) coincidirá, sin embargo, a menudo se necesitan algunos más. No estoy 100% seguro de por qué esto funciona, pero me imagino que habilita características que son demasiado pequeñas para que phash funcione (phash reduce las imágenes a 32x32).

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 obtendrá ninguno en otra área. Estoy usando el GridAdaptedFeatureDetector en OpenCV para mejorar la distribución. No estoy seguro de qué tamaño de cuadrícula es mejor, estoy usando una cuadrícula pequeña (1x3 o 3x1 dependiendo de la orientación de la imagen).

Probablemente desee escalar todas las imágenes del pajar (y la aguja) a un tamaño más pequeño antes de la detección de características (uso 210 px 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 prominentes.

Para las imágenes de personas, puede intentar 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, el rostro más grande escalado a 100px). El detector de características tiene en cuenta los niveles de escala múltiple (usando pirámides) pero hay una limitación en la cantidad de niveles que usará (esto se puede ajustar, por supuesto).

El detector de puntos clave probablemente funciona mejor cuando devuelve menos que la cantidad de características que deseaba. Por ejemplo, si solicita 400 y obtiene 300 de vuelta, eso es bueno. Si recuperas 400 cada vez, probablemente algunas buenas características tuvieron que omitirse.

La imagen de la aguja puede tener menos puntos clave que las imágenes del 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 tasa de aciertos 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 escalado, la rotación, la duplicación, etc. Se puede utilizar una técnica de paso múltiple. En cada iteración, transforme los sub-rectángulos, vuelva a hacer hash y vuelva a ejecutar la función de búsqueda.

Como señaló Cartman, puede 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 compañías de CG para verificar si las imágenes renovadas todavía muestran esencialmente la misma escena.

Tengo una idea, que puede funcionar y es muy probable que sea muy rápida. Puede submuestrear una imagen para decir una resolución de 80x60 o comparable, y convertirla a escala de grises (después del submuestreo será más rápido). Procese las dos imágenes que desea comparar. Luego, ejecute la suma normalizada de las diferencias al cuadrado entre dos imágenes (la imagen de consulta y cada una de la base de datos), o incluso la Correlación cruzada normalizada, que da una respuesta más cercana a 1, si ambas imágenes son similares. Luego, 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, aunque será muy rápido, hasta 10000 imágenes por segundo en el hardware moderno. Si necesita invariancia para la rotación, entonces se puede calcular un gradiente dominante para esta pequeña imagen, y luego todo el sistema de coordenadas se puede girar a orientación canónica, sin embargo, esto será más lento. Y no, no hay invariancia a escala aquí.

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

Mi empresa tiene aproximadamente 24 millones de imágenes de fabricantes cada mes. Estaba buscando una solución rápida para asegurar que las imágenes que subimos a nuestro catálogo sean nuevas .

Quiero decir que he buscado en internet por todas partes para intentar encontrar una solución ideal. Incluso desarrollé mi propio algoritmo de detección de bordes.
He evaluado la velocidad y precisión de múltiples modelos. Mis imágenes, que tienen fondos blancos, funcionan extremadamente bien con phashing. Como dijo redcalx , recomiendo phash o ahash. NO HAGA use Hashing MD5 ni ningún otro hash criptográfico. A menos que solo desee coincidencias de imagen EXACTAS. Cualquier cambio de tamaño o manipulación que ocurra entre imágenes producirá un hash diferente.

Para phash / ahash, mira esto: imagehash

Quería extender la publicación de * redcalx * publicando mi código y mi precisión.

Lo que hago:

from PIL import Image
from PIL import ImageFilter
import imagehash

img1=Image.open(r"C:\yourlocation")
img2=Image.open(r"C:\yourlocation")
if img1.width<img2.width:
    img2=img2.resize((img1.width,img1.height))
else:
    img1=img1.resize((img2.width,img2.height))
img1=img1.filter(ImageFilter.BoxBlur(radius=3))
img2=img2.filter(ImageFilter.BoxBlur(radius=3))
phashvalue=imagehash.phash(img1)-imagehash.phash(img2)
ahashvalue=imagehash.average_hash(img1)-imagehash.average_hash(img2)
totalaccuracy=phashvalue+ahashvalue

Estos son algunos de mis resultados:

item1  item2  totalsimilarity
desk1  desk1       3
desk1  phone1     22
chair1 desk1      17
phone1 chair1     34

¡Espero que esto ayude!

Creo que bajar el tamaño de la imagen a casi un tamaño de icono, digamos 48x48, luego convertirlo a escala de grises, 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 real del píxel, no importará si la imagen es un poco más clara o más oscura. Importantes cambios serán importantes 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 aumentar la precisión. Como máximo, tendrías que hacer 47x47 = 2,209 restas para formar una clave comparable.

Elegir 100 puntos aleatorios podría significar que imágenes similares (u ocasionalmente incluso diferentes) se marcarían como lo mismo, lo que supongo que no es lo que desea. Los hash MD5 no funcionarían si las imágenes fueran de diferentes formatos (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 apuesta, hacer una comparación píxel por píxel no debería llevar mucho tiempo siempre que esté utilizando una buena biblioteca de imágenes / lenguaje rápido, y el tamaño es lo suficientemente pequeño.

Podría intentar hacerlos pequeños, luego, si son iguales, realice 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 un filtro Bloom , que utiliza múltiples hashes para obtener un resultado probabilístico pero eficiente. Si la cantidad de imágenes no es enorme, entonces un hash criptográfico como md5 debería ser suficiente.