Huella digital de imagen para comparar la similitud de muchas imágenes

Necesito crear huellas dactilares de muchas imágenes (alrededor de 100.000 existentes, 1000 nuevas por día, RGB, JPEG, tamaño máximo 800x800) para comparar cada imagen con cualquier otra imagen muy rápido. No puedo usar métodos de comparación binaria porque también se deben reconocer las imágenes que son casi similares.

Lo mejor sería una biblioteca existente, pero también me ayudarían mucho algunas pistas sobre los algoritmos existentes.

Los algoritmos de cálculo hash o CRC normales no funcionan bien con datos de imagen. Debe tenerse en cuenta la naturaleza dimensional de la información.

Si necesita una toma de huellas dactilares extremadamente robusta, de modo que se tengan en cuenta las transformaciones afines (escalado, rotación, traslación, volteo), puede usar una transformación de Radon en la fuente de la imagen para producir un mapeo normativo de los datos de la imagen; almacene esto con cada imagen y luego compare solo las huellas dactilares. Este es un algoritmo complejo y no para los débiles de corazón.

son posibles algunas soluciones simples:

1. Cree un histograma de luminosidad para la imagen como huella digital
2. Cree versiones reducidas de cada imagen como huella digital
3. Combine la técnica (1) y (2) en un enfoque híbrido para mejorar la calidad de comparación

Un histograma de luminosidad (especialmente uno que está separado en componentes RGB) es una huella digital razonable para una imagen y puede implementarse de manera bastante eficiente. Restar un histograma de otro producirá un nuevo histórico que puede procesar para decidir qué tan similares son dos imágenes. Histogramas, porque los únicos que evalúan la distribución y ocurrencia de la información de luminosidad / color manejan las transformaciones afines bastante bien. Si cuantifica la información de luminosidad de cada componente de color hasta un valor de 8 bits, 768 bytes de almacenamiento son suficientes para la huella digital de una imagen de casi cualquier tamaño razonable. Los histogramas de luminosidad producen falsos negativos cuando se manipula la información de color de una imagen. Si aplica transformaciones como contraste / brillo, posterizar, cambio de color, cambios en la información de luminosidad.

El uso de imágenes escaladas es otra forma de reducir la densidad de información de la imagen a un nivel que sea más fácil de comparar. Las reducciones por debajo del 10% del tamaño de la imagen original generalmente pierden demasiada información para ser útil, por lo que una imagen de 800x800 píxeles se puede reducir a 80x80 y aún proporcionar suficiente información para realizar una toma de huellas dactilares decente. A diferencia de los datos de histograma, debe realizar un escalado anisotrópico de los datos de la imagen cuando las resoluciones de origen tienen proporciones variables. En otras palabras, reducir una imagen de 300x800 a una miniatura de 80x80 provoca la deformación de la imagen, de modo que cuando se compara con una imagen de 300x500 (que es muy similar) producirá falsos negativos. Las huellas digitales de las miniaturas también suelen producir falsos negativos cuando se trata de transformaciones afines. Si voltea o gira una imagen,

La combinación de ambas técnicas es una forma razonable de cubrir sus apuestas y reducir la aparición de falsos positivos y falsos negativos.

Existe un enfoque mucho menos ad-hoc que las variantes de imagen reducidas que se han propuesto aquí que conserva su sabor general, pero que proporciona una base matemática mucho más rigurosa para lo que está sucediendo.

Toma una onda de Haar de la imagen. Básicamente, la ondícula de Haar es la sucesión de diferencias de las imágenes de menor resolución a cada imagen de mayor resolución, pero ponderada por la profundidad a la que se encuentra en el "árbol" de mipmaps. El cálculo es sencillo. Luego, una vez que tenga la ondícula de Haar debidamente ponderada, deseche todos los coeficientes más grandes excepto los k (en términos de valor absoluto), normalice el vector y guárdelo.

Si toma el producto escalar de dos de esos vectores normalizados, obtendrá una medida de similitud, siendo 1 casi idéntico. Publiqué más información aquí .

Definitivamente deberías echarle un vistazo a phash .

Para comparar imágenes, existe este proyecto php : https://github.com/kennethrapp/phasher

Y mi pequeño clon de javascript : https://redaktor.me/phasher/demo_js/index.html

Desafortunadamente, esto se basa en "bitcount" pero reconocerá imágenes rotadas. Otro enfoque en javascript fue construir un histograma de luminosidad a partir de la imagen con la ayuda de canvas. Puede visualizar un histograma de polígono en el lienzo y comparar ese polígono en su base de datos (por ejemplo, mySQL espacial ...)

Hace mucho tiempo trabajé en un sistema que tenía algunas características similares, y esta es una aproximación del algoritmo que seguimos:

1. Divida la imagen en zonas. En nuestro caso, estábamos tratando con video de resolución 4: 3, por lo que usamos 12 zonas. Hacer esto elimina la resolución de las imágenes de origen de la imagen.
2. Para cada zona, calcule un color general: el promedio de todos los píxeles de la zona
3. Para la imagen completa, calcule un color general: el promedio de todas las zonas

Entonces, para cada imagen, está almacenando n + 1valores enteros, donde nestá el número de zonas que está rastreando.

Para realizar comparaciones, también debe observar cada canal de color de forma individual.

1. Para la imagen general, compare los canales de color de los colores generales para ver si están dentro de un cierto umbral, digamos, 10%
2. Si las imágenes están dentro del umbral, luego compare cada zona. Si todas las zonas también están dentro del umbral, las imágenes tienen una coincidencia lo suficientemente fuerte como para que al menos pueda marcarlas para una comparación adicional.

Esto le permite descartar rápidamente imágenes que no coincidan; también puede utilizar más zonas y / o aplicar el algoritmo de forma recursiva para conseguir una mayor confianza en las coincidencias.

Similar a la respuesta de Ic, puede intentar comparar las imágenes en múltiples resoluciones. Así que cada imagen se guarda como 1x1, 2x2, 4x4 .. 800x800. Si la resolución más baja no coincide (sujeta a un umbral), puede rechazarla inmediatamente. Si coincide, puede compararlos con la siguiente resolución más alta, y así sucesivamente.

Además, si las imágenes comparten una estructura similar, como imágenes médicas, es posible que pueda extraer esa estructura en una descripción que sea más fácil / rápida de comparar.

Por lo tanto, desea hacer una "coincidencia de huellas dactilares" que sea bastante diferente a la "coincidencia de imágenes". El análisis de huellas dactilares se ha estudiado en profundidad durante los últimos 20 años, y se han desarrollado varios algoritmos interesantes para garantizar la tasa de detección correcta (con respecto a las medidas FAR y FRR : tasa de aceptación falsa y tasa de rechazo falso ).

Le sugiero que busque mejor la clase de técnicas de detección LFA (Análisis de características locales) , en su mayoría basadas en la inspección de minucias. Las minucias son características específicas de cualquier huella dactilar y se han clasificado en varias clases. El mapeo de una imagen de trama a un mapa de minucias es lo que en realidad hacen la mayoría de las autoridades públicas para archivar a los criminales o terroristas.

Vea aquí para más referencias

Para comparar imágenes de iPhone y desarrollar similitudes de imágenes, consulte: http://sites.google.com/site/imagecomparison/

Para verlo en acción, visite eyeBuy Visual Search en iTunes AppStore.

A partir de 2015 (de regreso al futuro ... en esta pregunta de 2009 que ahora ocupa un lugar destacado en Google), la similitud de imágenes se puede calcular utilizando técnicas de aprendizaje profundo. La familia de algoritmos conocida como Auto Encoders puede crear una representación vectorial que se puede buscar por similitud. Hay una demostración aquí .

Una forma de hacer esto es cambiar el tamaño de la imagen y reducir la resolución significativamente (¿a 200x200 tal vez?), Almacenando una versión más pequeña (promedio de píxeles) para hacer la comparación. Luego defina un umbral de tolerancia y compare cada píxel. Si el RGB de todos los píxeles está dentro de la tolerancia, tiene una coincidencia.

Su ejecución inicial es O (n ^ 2) pero si cataloga todas las coincidencias, cada nueva imagen es solo un algoritmo O (n) para comparar (solo tiene que compararlo con cada imagen insertada previamente). Sin embargo, eventualmente se romperá a medida que la lista de imágenes para comparar se haga más grande, pero creo que está a salvo por un tiempo.

Después de 400 días de ejecución, tendrá 500.000 imágenes, lo que significa (descontando el tiempo para reducir el tamaño de la imagen) 200(H)*200(W)*500,000(images)*3(RGB)= 60.000.000.000 de comparaciones. Si cada imagen es una coincidencia exacta, se quedará atrás, pero probablemente ese no sea el caso, ¿verdad? Recuerde, puede descartar una imagen como coincidencia tan pronto como una sola comparación se salga de su umbral.

¿Quieres comparar literalmente cada imagen con las demás? Cual es la aplicacion? ¿Quizás solo necesita algún tipo de indexación y recuperación de imágenes basadas en ciertos descriptores? Entonces, por ejemplo, puede mirar el estándar MPEG-7 para la interfaz de descripción de contenido multimedia. Luego, podría comparar los diferentes descriptores de imágenes, que no serán tan precisos pero sí mucho más rápidos.

Parece que los algoritmos especializados de hash de imágenes son un área de investigación activa, pero quizás un cálculo hash normal de los bytes de la imagen funcionaría.

¿Está buscando imágenes de bytes idénticos en lugar de buscar imágenes que se derivan de la misma fuente pero que pueden tener un formato o resolución diferente (lo que me parece un problema bastante difícil)?