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

94

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.

Philip Dreyer
fuente
1
¿Idioma para el que debería ser la biblioteca?
Ben S

Respuestas:

57

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.

LBushkin
fuente
Respecto a la CRC, estuvo de acuerdo. Sin embargo, si uno quiere usarlo, es mejor usar hash MD5 que CRC32
mloskot
5
No querrá usar MD5 porque es un hash criptográfico unidireccional. Debe utilizar un método hash que produzca un resultado similar para una entrada similar, de modo que pueda comparar directamente las diferencias entre los hash.
AJ Quick
34

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í .

Edward KMETT
fuente
20

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 ...)

sebilasse
fuente
es esto en npm? Estoy buscando una manera de comparar la similitud entre dos imágenes usando javascript
Chovy
Hm, pensé que era "demasiado barato para npm". En realidad, fue solo una demostración escrita rápidamente desde cero. Sin embargo, siéntete libre de hacer lo que quieras con la fuente. Si puedo hacerlo, lo investigaré más tarde y lo enviaré a github github.com/redaktor ...
sebilasse
@SebastianLasse ¡Acabo de revisar tu puerto JS y es fantástico! Solo deseo que puedas pasar un URI de imagen a la Compare()función en lugar de tener que descargar la imagen primero. Además, según mis pruebas, el umbral para "una imagen muy similar" debería ser> 90%, no> 98%.
thdoan
12

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.

GalácticoVaquero
fuente
6

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.

allclaws
fuente
Esto se asigna a algún tipo de búsqueda de árbol, creo. Es interesante.
André Laszlo
3

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

ZZambia
fuente
¿Sabe cómo calcular la tasa de aceptación falsa si tiene una distribución gaussiana de puntuaciones para un sistema biométrico determinado?
GobiasKoffi
OP quiere "crear huellas dactilares de muchas imágenes". No comparar imágenes de huellas dactilares humanas.
Navin
3

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í .

Alex R
fuente
¿Es posible generar una imagen de huella digital a partir de datos binarios?
SwR
Claro, hay RNA para esta tarea, pero su respuesta no parece responder realmente a nada. La pregunta es: ¿Cómo se hace eso? La página vinculada no revela ninguna información y el término "Codificadores automáticos" tampoco ayuda.
Simon Steinberger
la pregunta original no dice "¿Cómo se hace eso?", pero sí dice "algunas pistas sobre los algoritmos existentes me ayudarían mucho", que es lo que proporcioné.
Alex R
No vinculó una "pista" a un algoritmo, de hecho, la página vinculada dice, "funciona, pero nadie sabe por qué. Por favor, no espere demasiado sobre el resultado" ...
odyth
Este deeplearning4j.org/deepautoencoder#use-cases proporciona más claridad sobre cómo se pueden usar los codificadores automáticos para crear una huella digital y luego cómo se puede usar esa huella digital para encontrar similitudes en otras imágenes según la similitud de los vértices.
odyth
2

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.

lc.
fuente
2

¿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.

Anónimo
fuente
tal vez una elección entre exhaustiva y limitada
johnny
0

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)?

Ian Hopkinson
fuente