¿Qué algoritmo podría usarse para identificar si las imágenes son las "mismas" o similares, independientemente del tamaño?

Question

TinEye, el "motor de búsqueda de imágenes inversas", le permite cargar/vincular a una imagen y puede buscar entre las 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 comprobación ingenua ni nada relacionado con eso. A menudo puede encontrar ambas imágenes con una resolución más alta y una resolución más baja y un tamaño más grande y más pequeño que la imagen original que proporciona. 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 encontrado imágenes del mismo conjunto de imágenes, donde las personas de la imagen están en una posición diferente, pero el fondo permanece en gran medida 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 conjunto?

Answer 1

Estos algoritmos son generalmente a base de huella digital. 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, esta es una función de huella dactilar (no muy buena): cambie el tamaño de la imagen a 32x32 cuadrados, normalice y cuantifique los colores, reduciendo el número de colores a 256. Luego, tiene Huella digital de 1024 bytes para la imagen. Simplemente mantenga una tabla de huellas dactilares => [lista de URLs de imágenes]. Cuando necesite buscar imágenes similares a una imagen determinada, simplemente calcule su valor de huella digital y encuentre la lista de imágenes correspondiente. Fácil.

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 utilizan una gran cantidad de heurísticas (es decir,utilice el conocimiento sobre los contenidos fotográficos típicos, sobre el formato de imagen/datos adicionales en EXIF, etc.)

Otra variación es utilizar más de una función de huella digital, intente aplicar cada una de ellas y combine los resultados. En realidad, es similar a encontrar textos similares. Solo en lugar de "bolsa de palabras", la búsqueda de similitud de imágenes utiliza una "bolsa de huellas dactilares" y determina cuántos elementos de una bolsa son los mismos que los elementos de otra bolsa. Cómo hacer que esta búsqueda sea eficiente es otro tema.

Ahora, con respecto a los artículos/papeles. No pude encontrar un buen artículo que brindara una visión general de los diferentes métodos. La mayoría de los artículos públicos que conozco abordan la mejora específica de métodos específicos. Podría recomendar comprobar estos:

"Content Fingerprinting Using Wavelets". Este artículo es sobre huellas dactilares de audio usando wavelets, pero el mismo método se puede adaptar para huellas digitales de imágenes.

PERMUTATION GROUPING: INTELLIGENT HASH FUNCTION DESIGN FOR AUDIO & IMAGE RETRIEVAL. Información sobre hashes sensibles a la localidad.

Bundling Features for Large Scale Partial-Duplicate Web Image Search. Un muy buen artículo, habla sobre SIFT y características de agrupamiento para la eficiencia. También tiene una buena bibliografía al final

Answer 2

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, junto con un algoritmo de categorización regional para asegurar que las imágenes coloreadas y complejas no se equivoquen emparejado No sé si eso es lo que están usando, pero parece que eso sería el truco.

Answer 3

Probablemente se basa en las mejoras de los algoritmos de extracción de características, aprovechando las características que son invariables de escala.

Tome un vistazo a

• Feature extraction

• SIFT, other site

o, si usted está realmente interesado, puede pagar algo de 70 dólares (o al menos mira la vista previa de Google) para

• Feature Extraction & Image Processing

Answer 4

Consulte this blog post (no el mío) para obtener 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 en rojo: azul y verde: ratios azules, y verifica si los géneros fueron los mismos. 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 en ese blog, un enfoque principal parece ser wavelets.

Answer 5

The Hough Transform es un algoritmo de extracción de características muy antiguo, que te importa encontrar interesante. Dudo que sea lo que usa tinyeye, pero es un buen y sencillo lugar de inicio para aprender sobre la extracción de características.

También hay slides to a neat talk de algunas personas de la Universidad de Toronto sobre su trabajo en astrometry.net. Desarrollaron un algoritmo para unir imágenes telescópicas del cielo nocturno con ubicaciones en catálogos de estrellas para identificar las características de la imagen. Es un problema más específico que lo que tinyeye intenta resolver, pero espero que muchas de las ideas básicas de las que hablan sean aplicables al problema más general.

Answer 6

¿Qué hay de cambiar el tamaño de las imágenes a un tamaño pequeño estándar y la comprobación de los valores PSNR solo SSIM o luma? eso es lo que yo haría.

Answer 7

http://tineye.com/faq#how

base a esto, Igor Krivokon's answer parece estar en la marca.

Answer 8

El creador del sitio FotoForensics publicó esta publicación 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 las wavelets y la extracción de características.

http://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html

aHash (también llamado hash Hash medio o promedio).Este enfoque aplasta la imagen en una imagen en escala de grises 8x8 y establece los 64 bits en el hash según si el valor del píxel es mayor que el color promedio para la imagen.

pHash (también llamado "Perceptive Hash"). Este algoritmo es similar a aHash pero utiliza una transformada de coseno discreta (DCT) y compara las bases basadas en 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 una implementación , dHash es casi idéntico a aHash, pero realiza mucho mejor. Mientras aHash se enfoca en valores promedio y pHash evalúa los patrones de frecuencia , dHash rastrea los gradientes.