Eliminación de imágenes duplicadas [cerrado]

https://stackoverflow.com/questions/225210

03-07-2019
|

Pregunta

Tenemos una colección de imágenes fotográficas de unos cientos de gigas.Una gran cantidad de fotografías están visualmente duplicadas, pero con diferentes tamaños de archivo, resolución, compresión, etc.

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

Solución

Recientemente quería realizar esta tarea para una galería de imágenes PHP. Quería poder generar un & Quot; fuzzy & Quot; huella digital para una imagen cargada, y verifique una base de datos para cualquier imagen que tuviera la misma huella digital, lo que indica que eran similares, y luego compárelas más de cerca para determinar qué tan similares.

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

Luego, para comparar el archivo cargado con cada " similar " imagen en la base de datos, tomé ambas imágenes, las redimensioné a 16x16 y las analicé píxel por píxel y quité el valor RGB de cada píxel del valor del píxel correspondiente en la otra imagen, agregando todos los valores juntos y dividiéndolos por la cantidad de píxeles que me dan una desviación de color promedio. Se determinó que cualquier valor inferior al valor específico es 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 metodología están aquí: http://www.catpa.ws / php-duplicate-image-finder /

Otros consejos

Pruebe PerceptualDiff para comparar 2 imágenes con las mismas dimensiones. Permite umbrales tales como considerar 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.

Un enfoque muy simple es el siguiente:

Convierta la imagen a escala de grises en la memoria, por lo que cada píxel es solo 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 tomará un tiempo), cargue siempre dos imágenes en la memoria y reste una de la otra. Es decir, reste el valor de píxel (0,0) en la imagen A ob el valor de píxel (0,0) en la imagen B, ahora haga lo mismo para (0,1) en ambos y así sucesivamente. El valor resultante puede ser positivo o negativo, siempre debe almacenar el valor absoluto (de modo que 5 da como resultado 5, -8 sin embargo da como resultado 8).
Ahora tiene una tercera imagen que es " imagen de diferencia " (imagen delta) de la imagen A y B. Si fueran idénticas, la imagen delta es toda negra (todos los valores se restarán a cero). El & Quot; menos negro & Quot; es, cuanto menos idénticas son las imágenes. Debe encontrar un buen umbral, ya que incluso si las imágenes son idénticas (a sus ojos), al escalar, alterar el brillo, etc., la imagen delta no será totalmente negra, sin embargo, solo tendrá tonos grises muy oscuros. Por lo tanto, necesita un umbral que diga & Quot; Si el error promedio (brillo de la imagen delta) está por debajo de cierto valor, todavía hay una buena posibilidad de que puedan ser idénticos, sin embargo, si está por encima de ese valor, lo más probable es que no . Encontrar el umbral correcto 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 sean).

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

La única forma de obtener resultados aún mejores es usar un procesamiento de imagen avanzado y aquí comienza a complicarse mucho. Involucra muchas matemáticas (una gran cantidad de ellas); existen buenas aplicaciones (dupe finders) para muchos sistemas que tienen estos implementados, por lo que, a menos que deba programarlo usted mismo, probablemente sea mejor usar una de estas soluciones. Leí muchos documentos 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 según 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 ;-)

En realidad, escribí una aplicación 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 encontrará para determinar la similitud de la imagen es error cuadrático medio o error absoluto medio (ambos tienen un tiempo de ejecución de O (n), donde n es el número de píxeles en la imagen, y también sería trivial 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 reducimos la muestra de imágenes (por ejemplo, todo se escala a, por ejemplo, 32 * 32 píxeles), luego las 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 estamos allí.

Definitivamente hay mejores algoritmos que MSE / MAE (de hecho, los problemas con estos dos algoritmos aplicados a la 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 todo es costoso en comparación con simplemente medir la señal de error.

Mi aplicación podría funcionar, dependiendo de cuántas imágenes hay en esas carpetas. Es multiproceso (lo he visto cargar completamente ocho núcleos de procesador que realizan comparaciones), pero nunca lo he probado en una base de datos de imágenes de más de unos cientos de imágenes. Unos cientos de conciertos de imágenes suenan prohibitivamente grandes. (simplemente leerlos desde el disco, reducir el muestreo, convertirlos a escala de grises y almacenarlos en la memoria, suponiendo que tenga suficiente memoria para guardar todo, lo que probablemente no tenga, podría tomar un par de horas).

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

Detección de copia de imagen
Recuperación de imágenes basada en contenido
Indexación de imágenes
Eliminación de duplicados de imagen

Básicamente, cada imagen se procesa (indexa) para producir una " firma de imagen " ;. Imágenes similares tienen firmas similares. Si sus imágenes se vuelven a escalar, probablemente su firma sea casi idéntica, por lo que se agrupan bien. Algunas firmas populares son los descriptores MPEG-7. Para agrupar, creo que K-Means o cualquiera de sus variantes puede ser suficiente. Sin embargo, probablemente necesite lidiar 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.

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

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

Si quieres algo rápido y sucio, busca en Google Similitud de imagen

Aquí hay una aplicación de similitud de imagen C # que podría hacer lo que quieres

Básicamente, todos los algoritmos extraen y comparan características. Cómo definen & Quot; feature & Quot; depende del modelo matemático en el que se basan.

Un truco rápido para esto es escribir un programa que calcule el valor del píxel promedio en cada imagen, en escala de grises, ordenar por este valor y luego compararlos visualmente. Imágenes muy similares deberían aparecer cerca una de la otra en el orden ordenado.

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

Comparar cada par de imágenes posible no se escalará a un conjunto de imágenes tan grande. Debe ordenar todo el conjunto de imágenes de acuerdo con alguna métrica para que las comparaciones solo son necesarias en 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 solo valor en escala de grises. Esto debería funcionar solo si los duplicados no han tenido ninguna alteración visual. El uso de un formato de archivo con pérdida también puede provocar alteraciones visuales.

Pensando fuera de la caja, es posible que pueda usar metadatos de imagen para reducir su conjunto de datos. Por ejemplo, sus imágenes pueden tener campos que muestran la fecha y 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 descargar estos datos en un formato de texto más conveniente y ordenable (con un poco de conocimiento de scripting 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 decir 100 conjuntos de 10,000 imágenes, una mejora significativa.

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ístico presentar duplicados a un humano, para confirmación manual.

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 cierto tamaño fijo y escala de grises. Luego guarde las imágenes resultantes en un directorio separado con el mismo nombre para referencia posterior. Entonces sería posible ordenar por tamaño de archivo y comparar visualmente las entradas vecinas.

Las imágenes resultantes pueden cuantificarse de ciertas maneras para detectar similitudes mediante programación (promedio de bloques, líneas, etc.).

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 verificar si hay duplicados (o tomar huellas digitales de todas las imágenes y luego hacer una consulta para ver si hay duplicados)

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

Huellas dactilares acústicas/este papel puede ser un buen comienzo con el concepto, ya que hay muchas implementaciones de este. Aquí es un artículo sobre huellas dactilares de imágenes.

Dicho esto, es posible que puedas salirte con la tuya con algo más simple.Algo tan básico como cambiar el tamaño de la imagen para igualar 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 necesitas comparar cada imagen entre sí.El tiempo requerido aumentará exponencialmente.

Si puede encontrar una manera de comparar imágenes que obedecen a 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), luego a BK-Tree sería una forma efectiva de indexar las imágenes de modo que pueda encontrar coincidencias en el tiempo O (log n) en lugar del tiempo O (n) para cada imagen.

Si sus coincidencias están restringidas a la misma imagen después de diferentes cantidades de compresión / cambio de tamaño / etc., entonces convertir a un 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.

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 , podría escribir una prueba para Mechanical Turk de Amazon.

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

Esencialmente, estaría creando un pequeño widget que AMT mostraría a usuarios humanos reales que básicamente tendrían que responder la pregunta " ¿Son estas dos imágenes iguales? " ;. O puede mostrarles una cuadrícula de imágenes de 5x5 y preguntarles & Quot; ¿Cuál de estas imágenes coincide? & Quot ;. Luego recopilaría los datos.

Otro enfoque sería utilizar los principios de la Computación Humana que Luis Von Ahn adoptó con más fama ( http://www.cs.cmu.edu/~biglou/ ) con reCaptcha, que utiliza las respuestas de Captcha para determinar las palabras ilegibles que se han ejecutado a través del reconocimiento óptico de caracteres, lo que ayuda a digitalizar libros. Podría hacer un captcha que pidiera a los usuarios que ayudaran a refinar las imágenes.

Suena como un problema de procedimiento en lugar de un problema de programación. ¿Quién sube las fotos? ¿Tú o los clientes? Si está cargando la foto, estandarice las dimensiones a una escala fija y a un formato de archivo. De esa manera 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 o su equipo, comparando visualmente las imágenes.

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

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow