¿Qué algoritmo se podría usar para identificar si las imágenes son "iguales" o similares, independientemente del tamaño?
TinEye, el "motor de búsqueda de imágenes inversas", le permite cargar/enlazar a una imagen y es capaz de buscar a través de los mil millones de imágenes que ha rastreado y devolverá enlaces a imágenes que ha encontrado que son la misma imagen.
Sin embargo, no es una suma de verificación ingenua ni nada relacionado con eso. A menudo es capaz de encontrar imágenes de una resolución más alta y más baja resolución y tamaño más grande y más pequeño que la imagen original que suministra. Este es un buen uso para el servicio porque a menudo encuentro una imagen y quiero la versión de mayor resolución posible.
No solo eso, sino que he tenido que encontrar imágenes del mismo conjunto de imágenes, donde las personas en la imagen están en una posición diferente, pero el fondo en gran medida permanece igual.
Qué tipo de algoritmo podría usar TinEye que le permitiría comparar una imagen con otras de varios tamaños y relaciones de compresión y aún así descubrir con precisión que son la "misma" imagen o ¿listo?
8 answers
Estos algoritmos suelen estar basados en huellas dactilares. La huella dactilar es una estructura de datos razonablemente pequeña, algo así como un código hash largo. Sin embargo, los objetivos de la función de huella digital son opuestos a los objetivos de la función hash. Una buena función hash debería generar códigos muy diferentes para objetos muy similares (pero no iguales). La función de huella dactilar debería, por el contrario, generar la misma huella dactilar para imágenes similares.
Solo para darle un ejemplo, este es un (no particularmente bueno) función de huella digital: cambiar el tamaño de la imagen a 32x32 cuadrados, normalizar y y cuantizar los colores, reduciendo el número de colores a algo así como 256. Luego, tiene una huella digital de 1024 bytes para la imagen. Simplemente mantenga una tabla de fingerprint = >[lista de URLs de imágenes]. Cuando necesite buscar imágenes similares a una imagen dada, simplemente calcule su valor de huella digital y encuentre la lista de imágenes correspondiente. Sencillo.
Lo que no es fácil - para ser útil en la práctica, la función de huella digital debe ser robusta contra cultivos, transformaciones afines, cambios de contraste, etc. La construcción de buenas funciones de huellas dactilares es un tema de investigación separado. Muy a menudo se ajustan a mano y utiliza una gran cantidad de heurística(es decir, utilizar el conocimiento sobre el contenido típico de la foto, sobre el formato de imagen / datos adicionales en EXIF, etc.)
Otra variación es utilizar más de una función de huella digital, tratar de aplicar cada una de ellas y combinar los resultados. En realidad, es similar a encontrar textos similares. Solo en lugar de " bolsa de palabras "la búsqueda de similitud de imagen utiliza una" bolsa de huellas dactilares " y encuentra cuántos elementos de una bolsa son los mismos que los elementos de otra bolsa. Cómo hacer esta búsqueda eficiente es otro tema.
Ahora, con respecto a los artículos/documentos. No pude encontrar un buen artículo que diera una visión general de los diferentes métodos. La mayoría de los artículos públicos que conozco discuten mejoras específicas a métodos específicos. Yo podría recomendar para comprobar estos:
"Huella Digital de Contenido Usando Wavelets " . Este artículo trata sobre la huella digital de audio usando wavelets, pero el mismo método se puede adaptar para la huella digital de imágenes.
AGRUPACIÓN DE PERMUTACIÓN: DISEÑO INTELIGENTE DE LA FUNCIÓN HASH PARA LA RECUPERACIÓN DE AUDIO E IMAGEN . Información sobre Hashes Sensibles a la Localidad.
Funciones de Agrupación para la Búsqueda de Imágenes Web Duplicadas Parciales a Gran Escala . Un artículo muy bueno, habla de TAMIZAR y agrupar características para la eficiencia. También tiene una bonita bibliografía al final
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-06-18 08:20:01
Probablemente se basa en mejoras de algoritmos de extracción de características, aprovechando características que son invariantes de escala.
Echa un vistazo a
O, si está realmente interesado, puede desembolsar unos 70 dólares (o al menos mirar la vista previa de Google) para
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-06-17 04:40:20
El creador del sitio FotoForensics publicó esta entrada de blog sobre este tema, fue muy útil para mí, y mostró algoritmos que pueden ser lo suficientemente buenos para usted y que requieren mucho menos trabajo que wavelets y extracción de características.
Http://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html
AHash (también llamado Hash Promedio o Hash Medio). Este enfoque aplasta la imagen en una imagen en escala de grises de 8x8 y establece los 64 bits en el hash basado en si el valor del píxel es mayor que el color promedio de la imagen.
PHash (también llamado "Hash perceptivo"). Este algoritmo es similar a aHash, pero utiliza una transformada de coseno discreto (DCT) y compara en frecuencias en lugar de valores de color.
DHash Al igual que aHash y pHash, dHash es bastante simple de implementar y es mucho más preciso de lo que tiene derecho a ser. Como un implementación, dHash es casi idéntico a aHash pero funciona mucho mejor. Mientras que aHash se centra en los valores promedio y pHash evalúa patrones de frecuencia, dHash rastrea gradientes.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-02-06 08:11:01
La transformación de Hough es un algoritmo de extracción de características muy antiguo, que te importa encontrar interesante. Dudo que sea lo que tinyeye usa, pero es un buen lugar de inicio simple para aprender sobre la extracción de características.
También hay diapositivas de una charla ordenada de algunos amigos de la Universidad de Toronto sobre su trabajo en astrometry.net . Desarrollaron un algoritmo para emparejar imágenes telescópicas del cielo nocturno con ubicaciones en catálogos de estrellas con el fin de identificar características en la imagen. Es un problema más específico que lo que Tinyeye intenta resolver, pero esperaría que muchas de las ideas básicas de las que hablan sean aplicables al problema más general.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-06-17 06:17:10
Basado en esto, La respuesta de Igor Krivokon parece ser acertada.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 10:31:35
Bien pueden estar haciendo una transformada de Fourier para caracterizar la complejidad de la imagen, así como un histograma para caracterizar la distribución cromática, emparejado con un algoritmo de categorización de regiones para asegurar que las imágenes similarmente complejas y coloreadas no se emparejen erróneamente. No sé si eso es lo que están usando, pero parece que eso haría el truco.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-06-17 04:32:15
Echa un vistazo esta entrada de blog (no mía) para una descripción muy comprensible de un algoritmo muy comprensible que parece obtener buenos resultados por lo simple que es. Básicamente divide las imágenes respectivas en una cuadrícula muy gruesa, ordena la cuadrícula por proporciones rojo:azul y verde:azul, y comprueba si las clases son las mismas. Esto funciona naturalmente solo para imágenes en color.
Lo más probable es que los profesionales obtengan mejores resultados utilizando algoritmos mucho más avanzados. Como se mencionó en los comentarios de ese blog, un enfoque líder parece ser wavelets.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-06-17 05:10:41
¿Qué hay de cambiar el tamaño de las imágenes a un tamaño pequeño estándar y verificar los valores de SSIM o PSNR solo para luma? eso es lo que yo haría.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-06-20 01:09:24