c# - repetidas - fotos duplicadas en galeria android
Eliminando imágenes duplicadas (15)
Tenemos una colección de imágenes de fotos con unos cientos de conciertos. Una gran cantidad de fotos son visualmente duplicadas, pero con diferentes tamaños de archivos, 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?
De hecho, escribí una aplicación que hace esto mismo.
Comencé con una aplicación anterior que utilizaba un algoritmo básico de 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 el error cuadrático medio o el 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 formas 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 seleccionamos las imágenes (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 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 es todo caro 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 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.
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.
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 imágenes
Básicamente, cada 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 necesites 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 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 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 pueden cuantificarse de cierta manera para detectar similitudes programáticas (promediar bloques, líneas, etc.).
La similitud de la imagen es probablemente un subcampo del procesamiento de imágenes / AI.
Esté preparado para implementar algoritmos / fórmulas de documentos si está buscando una solución excelente (es decir, de rendimiento y escalable).
Si quieres algo rápido y sucio, busca en Google Imágenes Similitudes
Here''s una aplicación de similitud de imágenes C # que puede hacer lo que quieras.
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.
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 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.
La toma de huellas acústicas / este documento puede ser un buen comienzo en el concepto, ya que hay muchas implementaciones de esto. Here hay un documento sobre huellas digitales de imágenes.
Dicho esto, es posible que pueda salirse con la suya con algo más simple. Algo tan básico como cambiar el tamaño de la imagen a igual 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 con las demás. El tiempo requerido aumentará exponencialmente.
Necesitará una herramienta de línea de comando para manejar tantos datos.
Comparar cada par 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 solo se necesiten más comparaciones 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 único valor de escala de grises. 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 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 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 usar una herramienta como exiv2 para volcar estos datos en 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 conjuntos de 10,000 imágenes, una mejora significativa.
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 crear 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.
Recientemente 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é 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 de 16 más cercano (dando 17 posibles tonos de gris entre 0 y 255), normalizándolos y almacenándolos en una matriz, creando así un histograma de color "borroso", y luego creando un md5sum del histograma que luego pude 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 cambié de tamaño a 16x16 y las analicé píxel a píxel y quité el valor RGB de cada píxel del valor del píxel correspondiente en el 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 utilizando el módulo GD, y una comparación con miles de imágenes toma solo unos cientos de milisegundos por archivo cargado.
Mi código y metodología están aquí: http://www.catpa.ws/php-duplicate-image-finder/
Si puede encontrar una forma 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 todo a, b, c), entonces un BK-Tree sería una manera 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 tus coincidencias están restringidas a la misma imagen después de variar las cantidades de compresión / cambio de tamaño / etc., entonces la conversión 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 compatibles , podría escribir una prueba para Mechanical Turk de Amazon.
https://www.mturk.com/mturk/welcome
Esencialmente, estarías 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 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 utilizar los principios de Computación Humana que Luis Von Ahn ( http://www.cs.cmu.edu/~biglou/ ) usó con más frecuencia con ReCaptcha, que usa las respuestas de Captcha para determinar las palabras ilegibles. que se han ejecutado mediante Reconocimiento óptico de caracteres, lo que ayuda a digitalizar libros. Podría hacer un captcha que solicite a los usuarios ayudar a refinar las imágenes.
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 debas agrupar las imágenes por ubicación ya que se trata de imágenes turísticas.
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. Por ejemplo, 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), cargue siempre 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 la imagen A y B. Si fueran idénticas, la imagen delta es toda 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 escalado 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 requiere mucho tiempo. Entonces necesitas comparar cada imagen GS entre sí, una vez más, toneladas de tiempo. Además, 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 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 se debe hacer, pero no tengo idea de por qué funciona o cómo funciona en realidad, es simplemente mágico ;-)
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.