image-processing - subir - google imagenes busqueda avanzada

¿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 (aproximadamente la mitad) de sus píxeles con valores idénticos y el resto están desactivados en aproximadamente +/- 3 en sus valores R / G / B. Las imágenes son idénticas a simple vista. Es el tipo de diferencia que obtendrías al volver a comprimir un jpeg.

Ya tengo una manera 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% preciso, 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 una manera que pudiera comparar las huellas dactilares en una tabla hash. Incluso si puedo reducir de manera confiable el número de imágenes que necesito comparar a solo 100, estaría en gran forma para comparar de 1 a 100. ¿Cuál sería un buen algoritmo para esto?

Answer 1

Eche un vistazo a O. Chum, J. Philbin y A. Zisserman, Detección de imágenes casi duplicadas: ponderación min-hash y tf-idf , en Actas de la Conferencia de Visión Británica de Máquinas, 2008. Resuelven el problema que tiene y demuestran Los resultados para 146k imagenes. Sin embargo, no tengo experiencia de primera mano con su enfoque.

Answer 2

Idea ingenua: cree una miniatura pequeña (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 solucionarse haciendo hash. Aquí está la dificultad: suponga que tiene un píxel rojo y desea que 3 y 5 tengan el mismo valor. Bueno, entonces también quieres que 5 y 7 tengan el mismo valor, y 7 y 9, y así sucesivamente ... puedes construir una cadena que diga que quieres que todos los píxeles tengan el mismo valor.

Esto es lo que intentaría en su lugar:

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

Uno de los dos millones de nodos se insertan en el árbol, dos imágenes se duplican solo si están en el mismo nodo. ¿Derecha? ¡Incorrecto! Si el valor de píxel en dos imágenes es 127 y 128, uno va hacia el margen 15 y el otro hacia el punto 16. Así que en realidad, cuando se discrimina en un píxel, puede insertar esa imagen en uno o dos hijos:

• Para el brillo B , inserte en 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, doblas el número de saldos en los que aparece la imagen. Dependiendo de la profundidad de las cosas, puedes tener muchos nodos adicionales.

Alguien más tendrá que hacer los cálculos y ver si tiene que dividir entre algo más grande que 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 necesitas un árbol de profundidad 10. Cuatro duplicaciones en 10 te llevan hasta 32 millones de imágenes en las hojas. Espero que tengas mucha memoria RAM a tu disposición! Si no, puedes poner el árbol en el sistema de archivos.

Déjame saber cómo va esto!

Answer 4

Sobre la base de la idea de minHash ...

Mi idea es hacer 100 tablas de búsqueda utilizando todas las imágenes que se encuentran actualmente en la base de datos. Las tablas de consulta se asignan desde el brillo de un píxel particular a una lista de imágenes que tienen ese mismo brillo en ese mismo píxel. Para buscar una imagen, simplemente ingrésela 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.

Hay muchos problemas con cómo hacer esto dentro de las limitaciones de memoria razonables y cómo hacerlo rápidamente. Se necesitan estructuras de datos adecuadas para el almacenamiento en 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.

Answer 5

También es bueno el hash desde miniaturas: se reconocen duplicados escalados (con poca modificación)