2008-10-22 2 views
32

Tenemos una colección de imágenes fotográficas que se dimensiona unos cientos de conciertos. Una gran cantidad de fotos son visualmente duplicadas, pero con diferentes tamaños de archivos, resolución, compresión, etc.Eliminación de imágenes duplicadas

¿Es posible utilizar algún método de procesamiento de imágenes específico para buscar y eliminar estas imágenes duplicadas?

+0

Podría describir las posibles diferencias entre los duplicados? ¿Podrían haber sido escalados, iluminados, recortados, con los ojos rojos, etc.? – Liam

+0

de observación, en orden de ocurrencias: comprimido, a escala, cambio en brillo/saturación, recortado –

+0

Ooh, eso es desagradable. – Liam

Respuesta

20

Hace poco quise realizar esta tarea para una galería de imágenes PHP. Quería poder generar una huella dactilar "borrosa" para una imagen cargada, y buscar en una base de datos cualquier imagen que tuviera la misma huella digital, indicando que eran similares, y luego compararlas más de cerca para determinar qué tan similar.

Lo logré redimensionando la imagen cargada a 150 píxeles de ancho, reduciéndola a escala de grises, redondeando el valor de cada color al múltiplo de 16 más cercano (dando 17 posibles tonos de gris entre 0 y 255), normalizándolos y almacenarlos en una matriz, creando así un histograma de color "borroso", y luego creando un md5sum del histograma que luego podría buscar en mi base de datos. Esto fue extremadamente efectivo para reducir las imágenes que eran visualmente muy similares al archivo cargado.

Luego, para comparar el archivo cargado con cada imagen "similar" en la base de datos, tomé ambas imágenes, las redimensioné a 16x16, las analicé píxel a píxel y saqué el valor RGB de cada píxel del valor del el píxel correspondiente en la otra imagen, sumando todos los valores y dividiendo por el número de píxeles, obteniendo una desviación de color promedio. Se determinó que cualquier valor inferior al específico era un duplicado.

Todo está escrito en PHP usando el módulo GD, y una comparación con miles de imágenes toma solo unos pocos cientos de milisegundos por archivo cargado.

Mi código, y la metodología está aquí: http://www.catpa.ws/php-duplicate-image-finder/

+0

+1 buen enfoque para una solución –

+0

buen pensamiento, en realidad hemos implementado esto, pero comenzará a trabajar extremadamente lento en una base de datos de más de 10.000 imágenes. –

+0

¿No estás creando grandes huecos en tu histograma aquí '$ value = (round ($ greyscale/16) * 16) -1;'? Solo se llena cada décimosexto valor. El tamaño de su histograma no debe ser 256, debe ser '256/bucketSize = 16'. – mpen

1

Un truco rápido en esto es escribir un programa que calculará el valor del píxel promedio en cada imagen, en escala de grises, ordenar por este valor, y luego compararlos visualmente. Las imágenes muy similares deben aparecer una junto a la otra en el orden ordenado.

+0

No creo que clasificar imágenes por brillo sea muy efectivo. –

+0

No muy efectivo, lo admito, pero tiene potencial como parte de un conjunto de heurísticas – Liam

0

El programa gqview tiene una opción para encontrar duplicados, por lo que puede intentar buscar allí. Sin embargo, no es infalible, por lo que solo sería adecuado como heurística para presentar duplicados a un ser humano, para confirmación manual.

1

La similitud de la imagen es probablemente un subcampo del procesamiento de imágenes/AI.

Prepárese para implementar algoritmos/fórmulas de documentos si está buscando una solución excelente (es decir, eficiente y escalable).

Si quieres algo rápido n sucio, google búsqueda de Image Similarity

Here's un C Nº de imagen de similitud aplicación que podría hacer lo que quiera.

Básicamente, todos los algoritmos extraen y comparan características. La definición de "característica" depende del modelo matemático en el que se basan.

0

La parte más importante es hacer que los archivos sean comparables.

Una solución genérica podría ser escalar todas las imágenes a un determinado tamaño fijo y en escala de grises. A continuación, guarde las imágenes resultantes en un directorio separado con el mismo nombre para una referencia posterior. Entonces sería posible ordenar por tamaño de archivo y comparar visualmente las entradas vecinas.

Las imágenes resultantes se pueden cuantificar de cierta manera para detectar similitudes mediante programación (promediando bloques, líneas, etc.).

4

Esto sigue siendo un área de investigación, creo. Si tienes algo de tiempo en sus manos, algunas palabras clave relevantes son:

  • detección Copia de imagen
  • contenido de imágenes basado en la recuperación
  • indexación imagen
  • Imagen eliminación de duplicados

Básicamente, cada la imagen se procesa (indexa) para producir una "firma de imagen". Las imágenes similares tienen firmas similares. Si las imágenes se vuelven a escalar, es probable que su firma sea casi idéntica, por lo que se agrupan bien. Algunas firmas populares son los descriptores MPEG-7. Para agruparme, creo que K-Means o cualquiera de sus variantes puede ser suficiente. Sin embargo, es probable que tenga que tratar con millones de imágenes, esto puede ser un problema.

Aquí hay un enlace a la entrada principal de Wikipedia:
http://en.wikipedia.org/wiki/CBIR

Espero que esto ayude.

5

Pruebe PerceptualDiff para comparar 2 imágenes con las mismas dimensiones. Permite umbrales como considerar las imágenes con solo X número de píxeles diferentes para ser visualmente indistinguibles.

Si los duplicados visuales pueden tener diferentes dimensiones debido a la escala, o diferentes tipos de archivos, es posible que desee hacer un formato estándar para las comparaciones. Por ejemplo, podría usar ImageMagick para escalar todas las imágenes a 100x100 y guardarlas como archivos PNG.

+0

PerceptualDiff parece prometedor. –

1

Necesitará una herramienta de línea de comandos para manejar tantos datos.

La comparación de todos los pares de imágenes posibles no se escalará a un conjunto tan grande de imágenes. Debe ordenar todo el conjunto de imágenes de acuerdo con alguna métrica para que las comparaciones posteriores de solo sean necesarias en las imágenes vecinas.

Un ejemplo de una métrica simple es el valor promedio de todos los píxeles en una imagen, expresado como un valor de escala de grises único. Esto debería funcionar solo si los duplicados no han tenido alteraciones visuales. El uso de un formato de archivo con pérdida también puede ocasionar alteraciones visuales.

5

Un enfoque muy simple es la siguiente:

  • convertir la imagen a escala de grises en la memoria, por lo que cada píxel es sólo un número entre 0 (negro) y 255 (blanco).

  • Escala la imagen a un tamaño fijo. Encontrar el tamaño correcto es importante, debes jugar con diferentes tamaños. P.ej. puede escalar cada imagen a 64x64 píxeles, pero puede obtener mejores o peores resultados con imágenes más pequeñas o más grandes.

  • Una vez que haya hecho esto para todas las imágenes (sí, eso llevará un tiempo), siempre cargue dos imágenes en la memoria y restelas una de la otra. Eso es restar el valor de pixel (0,0) en la imagen A ob el valor de pixel (0,0) en la imagen B, ahora hacer lo mismo para (0,1) en ambos y así sucesivamente. El valor resultante puede ser positivo o negativo, siempre debe almacenar el valor absoluto (por lo que 5 resultados en 5, -8 sin embargo, resulta en 8).

  • Ahora tiene una tercera imagen que es la "imagen de diferencia" (imagen delta) de las imágenes A y B. Si fueran idénticas, la delta será negra (todos los valores se restarán a cero). Cuanto menos negro es, menos idénticas son las imágenes. Necesitas encontrar un buen umbral, ya que incluso si las imágenes son idénticas (a tus ojos), al escalar, alterar el brillo, etc., la imagen delta no será totalmente negra, pero solo tendrá greytones muy oscuros. Por lo tanto, necesita un umbral que diga "Si el error promedio (brillo de la imagen delta) está por debajo de un cierto valor, aún existe una buena posibilidad de que sean idénticos; sin embargo, si está por encima de ese valor, es probable que no. el umbral es tan difícil como encontrar el tamaño de escala correcto. Siempre tendrá falsos positivos (imágenes que se consideran idénticas, aunque no lo son en absoluto) y falsos negativos (imágenes que se consideran no idénticas, aunque lo son).

Este algoritmo es ultra lento. En realidad, solo crear las imágenes en escala de grises requiere mucho tiempo. Luego, debe comparar cada imagen GS entre sí, una vez más, muchísimo tiempo. También almacenar todas las imágenes GS requiere mucho espacio en disco. Así que este algoritmo es muy malo, pero los resultados no son tan malos, aunque es así de simple. Los resultados no son sorprendentes, son mejores de lo que inicialmente pensé.

La única forma de obtener mejores resultados es utilizar un procesamiento de imágenes avanzado y aquí comienza a ser realmente complicado. Implica una gran cantidad de matemáticas (una gran cantidad); hay buenas aplicaciones (buscadores de engaños) para muchos sistemas que tienen estos implementados, así que a menos que deba programarlo usted mismo, probablemente sea mejor que use una de estas soluciones. Leí muchos artículos sobre este tema, pero me temo que la mayor parte de esto va más allá de mi horizonte. Incluso los algoritmos que podría implementar de acuerdo con estos documentos están más allá; eso significa que entiendo lo que hay que hacer, pero no tengo idea de por qué funciona o cómo funciona realmente, es simplemente mágico ;-)

+0

¿Puede aconsejarme algunas formas de elegir el tamaño y el umbral correctos? –

+0

@DuyTran Lo siento, este fue un proyecto que abandoné hace mucho tiempo (¡la respuesta es de 2008!). Si bien el algoritmo fue mejor de lo que esperaba, mi código era demasiado lento, así que cambié a una aplicación comercial que era aproximadamente 3 veces más rápida y tenía muchos menos resultados falsos. Creo que obtendrás mejores resultados si comparas imágenes como se hace con la huella digital de música. Una imagen es solo datos en 2D, mientras que la música es datos 1D, pero ambos se pueden convertir a una representación de "frecuencia", que es más fácil de comparar, p. vea goo.gl/Yy46xk para ver cómo se compara la música. – Mecki

1

Pensando fuera de la caja, es posible que pueda utilizar los metadatos de la imagen para reducir su conjunto de datos. Por ejemplo, sus imágenes pueden tener campos que muestran la fecha y la hora en que se tomó la imagen, hasta el segundo más cercano. Es probable que los duplicados tengan valores idénticos. Se podría utilizar una herramienta como exiv2 para volcar estos datos a un formato de texto más conveniente y ordenable (con un poco de conocimiento de scripts de proceso por lotes/shell).

Incluso campos como el fabricante y el modelo de la cámara podrían usarse para reducir un conjunto de 1,000,000 de imágenes para decir 100 juegos de 10,000 imágenes, una mejora significativa.

0

Me imagino que el método más escalable sería almacenar una huella digital con cada imagen. Luego, cuando se agrega una nueva imagen, es un caso simple de SELECT id FROM photos where id='uploaded_image_id' para buscar duplicados (o toma de huellas dactilares de todas las imágenes, luego hacer una consulta para duplicar

Obviamente, un simple hash de archivos no funcionaría ya que el contenido real difiere ..

Acoustic fingerprinting/this paper puede ser un buen comienzo en el concepto, ya que hay muchas implementaciones de esta. Here es un documento sobre la imagen de huellas dactilares.

dicho esto, usted puede ser capaz de salirse con la suya Más simple. Algo tan básico como redimensionar la imagen al mismo ancho o alto, restando image_a de image_b, y sumando la diferencia. Si la diferencia total está por debajo de un umbral, la imagen es un duplicado.

El problema con esto es que necesita comparar cada imagen con las demás. El tiempo requerido aumentará exponencialmente.

0

Si puede encontrar una forma de comparar imágenes que obedecen la desigualdad del triángulo (por ejemplo, si d (a, b) es la diferencia entre las imágenes a y b, entonces d (a, b) < d (a, c) + d (b, c) para todos a, b, c), entonces un BK-Tree sería una manera efectiva de indexar las imágenes de modo que pueda encontrar coincidencias en O (log n) tiempo en lugar de O (n) tiempo para cada imagen.

Si sus coincidencias están restringidas a la misma imagen después de variar las cantidades de compresión/cambio de tamaño/etc., convertir a tamaño canónico/balance de color/etc. y simplemente sumar los cuadrados de diferencias de cada píxel puede ser una buena métrica, y esto obedece a la desigualdad del triángulo, por lo que podría usar un árbol BK para un acceso eficiente.

-1

Suena como un problema de procedimiento en lugar de un problema de programación. ¿Quién carga las fotos? Usted o los clientes? Si está cargando la foto, estandarice las dimensiones en una escala fija y formato de archivo. De esa forma las comparaciones serán más fáciles. Sin embargo, tal como está, a menos que tenga días, o incluso semanas de tiempo libre, le sugiero que elimine manualmente las imágenes duplicadas, ya sea usted mismo o su equipo, comparando visualmente las imágenes.

Quizás deba agrupar las imágenes por ubicación ya que se trata de imágenes turísticas.

+0

las fotos son de un tercero y no contienen ningún dato de exif –

0

Si tiene un poco de dinero para gastar, y tal vez una vez que ejecute un primer pase para determinar qué imágenes son quizás coincidencias, podría escribir una prueba para Mechanical Turk de Amazon.

https://www.mturk.com/mturk/welcome

Esencialmente, usted estará creando un pequeño widget que AMT mostraría a los usuarios humanos reales que entonces, básicamente, sólo tienen que responder a la pregunta "¿Son estas dos imágenes del mismo?". O bien, podría mostrarles una cuadrícula de, digamos, imágenes de 5x5 y preguntarles "¿Cuáles de estas imágenes coinciden?". A continuación, recoger los datos.

Otro enfoque sería el uso de los principios de la computación humana que han sido más famoso propugnados por Luis Von Ahn (http://www.cs.cmu.edu/~biglou/) con reCaptcha, que utiliza las respuestas Captcha para determinar las palabras ilegibles que se han ejecutado a través de reconocimiento óptico de caracteres, por lo tanto ayudando a digitalizar libros. Podría hacer un captcha que solicite a los usuarios ayudar a refinar las imágenes.

5

De hecho, escribí un application que hace esto mismo.

Comencé con una aplicación anterior que utilizaba un algoritmo básico Levenshtein Distance para calcular la similitud de la imagen, pero ese método no es deseable por varias razones. Sin duda, el algoritmo más rápido que va a encontrar para determinar la similitud de la imagen es mean squared error o mean absolute error (ambos tienen un tiempo de ejecución de O (n), donde n es el número de píxeles de la imagen, y también ser trivial para enhebrar una implementación de cualquiera de los algoritmos de varias maneras diferentes). La publicación de Mecki es en realidad solo una implementación de Error Absoluto Medio, que mi aplicación puede realizar (el código también está disponible para su placer de navegación, si así lo desea). En cualquier caso, en nuestra aplicación, primero bajamos las imágenes de muestra (por ejemplo, todo se escala a, por ejemplo, 32 * 32 píxeles), luego convertimos a escala de grises y luego ejecutamos las imágenes resultantes a través de nuestros algoritmos de comparación. También estamos trabajando en algunos algoritmos de preprocesamiento más avanzados para normalizar aún más las imágenes, pero ... todavía no del todo.

Definitivamente hay algoritmos mejores que MSE/MAE (de hecho, los problemas con estos dos algoritmos aplicados a información visual han sido bien documentados), como SSIM, pero tiene un costo. Otras personas intentan comparar otras cualidades visuales en la imagen, como la luminancia, el contraste, los histogramas de color, etc., pero es todo caro en comparación con simplemente medir la señal de error.

Mi solicitud fuerza de trabajo, dependiendo de cuántos imágenes están en esas carpetas. Es multihilo (he visto cargar por completo ocho núcleos de procesador realizando comparaciones), pero nunca he probado en una base de datos de imágenes de más de unos cientos de imágenes. Algunos cientos de conciertos de imágenes suenan prohibitivamente grandes. (simplemente, leerlos desde el disco, reducir la resolución de resolución, convertirlos a escala de grises y almacenarlos en la memoria, suponiendo que tenga suficiente memoria para guardar todo, lo cual probablemente no ocurra), podría demorar un par de horas.

Cuestiones relacionadas