¿Cómo puedo reconocer imágenes ligeramente modificadas?

Question

Tengo una base de datos muy grande de imágenes jpeg, alrededor de 2 millones. Me gustaría hacer una búsqueda difusa de duplicados entre esas imágenes. Las imágenes duplicadas son dos imágenes que tienen muchos (alrededor de la mitad) de sus píxeles con valores idénticos y el resto están desactivados por aproximadamente +/- 3 en sus valores R/G/B. Las imágenes son idénticas a simple vista. Es la clase de diferencia que obtendrías al volver a comprimir un jpeg.

Ya tengo una forma infalible de detectar si dos imágenes son idénticas: sumo el brillo delta sobre todos los píxeles y lo comparo con un umbral. Este método ha demostrado ser 100% exacto, pero hacer 1 foto contra 2 millones es increíblemente lento (horas por foto).

Me gustaría tomar las huellas dactilares de las imágenes de forma que solo pudiera comparar las huellas dactilares en una tabla hash. Incluso si puedo reducir de manera confiable la cantidad de imágenes que necesito comparar con solo 100, estaría en buena forma para comparar de 1 a 100. ¿Cuál sería un buen algoritmo para esto?

Answer 1

Tenga una mirada en O. Chum, J. Philbin, y A. Zisserman, Near duplicate image detection: min-hash and tf-idf weighting, en Actas de la Visión Artificial británica Conferencia, 2008. Resuelven el problema que tienes y demuestran los resultados de 146k imágenes. Sin embargo, no tengo experiencia de primera mano con su enfoque.

Answer 2

Idea ingeniosa: cree una pequeña miniatura (50x50 píxeles) para encontrar imágenes "probablemente idénticas", luego aumente el tamaño de la miniatura para descartar más imágenes.

Answer 3

No creo que este problema pueda resolverse mediante hash. Aquí está la dificultad: supongamos que tiene un píxel rojo, y quiere 3 y 5 para hacer un hash con el mismo valor. Bueno, entonces también quieres 5 y 7 para hash con el mismo valor, y 7 y 9, y así sucesivamente ... puedes construir una cadena que diga que quieres que todos los píxeles pasen al mismo valor.

Esto es lo que me gustaría probar en su lugar:

1. Construir un enorme árbol B, con 32 vías abanico de salida en cada nodo, que contiene todas las imágenes.
2. Todas las imágenes del árbol son del mismo tamaño o no están duplicadas.
3. Proporcione a cada píxel de color un número único que comience en cero. La parte superior izquierda puede estar numerada 0, 1, 2 para los componentes R, G, B, o puede que estés mejor con una permutación aleatoria, porque vas a comparar imágenes en orden de esa numeración.
4. Un nodo interno en la profundidad n discrimina 32 formas en el valor del píxel n dividido por 8 (esto capta parte del ruido en los píxeles cercanos.
5. Un nodo hoja contiene una pequeña cantidad de imágenes, digamos 10 a 100. O tal vez el número de imágenes es una función creciente de profundidad, por lo que si usted tiene 500 duplicados de una imagen, después de una cierta profundidad que dejar de tratar de distinguirlos.

una todos los nodos son dos millones insertado en el árbol, dos imágenes son duplicadas solo si están en el mismo nodo. ¿Correcto? Si el valor de píxel en dos imágenes es 127 y 128, uno entra en outedge 15 y el otro entra en outedge 16. Así que en realidad cuando discriminas en un píxel, es posible insertar esa imagen en uno o dos hijos:

• Para el brillo B, insertar al B/8, (B-3)/8 y (B+3)/8. A veces, los 3 serán iguales, y siempre 2 de 3 serán iguales. Pero con la probabilidad 3/8, se duplica el número de outedges en los que aparece la imagen. Dependiendo de cuán profundas sean las cosas, podrías tener muchos nodos adicionales.

Alguien más tendrá que hacer los cálculos y ver si tiene que dividirse por algo más de 8 para evitar que las imágenes se dupliquen demasiado.La buena noticia es que incluso si el verdadero fanout es solo alrededor de 4 en lugar de 32, solo necesita un árbol de profundidad 10. Cuatro duplicaciones en 10 le lleva a 32 millones de imágenes en las hojas. ¡Espero que tengas suficiente RAM a tu disposición! Si no, puedes poner el árbol en el sistema de archivos.

¡Avísame cómo te va!

Answer 4

también bien acerca de hash a partir de imágenes en miniatura: los duplicados son reconocidos a escala (con pequeñas modificaciones)

Answer 5

Basándose en la idea de minhash ...

Mi idea es hacer 100 tablas de búsqueda utilizando todas las imágenes actualmente en la base de datos. Las tablas de búsqueda están mapeando desde el brillo de un píxel en particular hasta una lista de imágenes que tienen el mismo brillo en ese mismo píxel. Para buscar una imagen solo ingrese en las tablas hash, obtenga 100 listas y obtenga un punto por cada imagen cuando aparezca en una lista. Cada imagen tendrá una puntuación de 0 a 100. La imagen con más puntos gana.

Existen muchas cuestiones sobre cómo hacerlo dentro de las limitaciones de memoria razonables y cómo hacerlo rápidamente. Se necesitan estructuras de datos adecuadas para el almacenamiento en el disco. También es posible ajustar el valor de hash, el número de tablas, etc. Si se necesita más información, puedo ampliar esto.

Mis resultados han sido muy buenos. Puedo indexar un millón de imágenes en aproximadamente 24 horas en una computadora y puedo buscar 20 imágenes por segundo. La precisión es asombrosa por lo que puedo decir.