可以使用什么算法来识别图像是否是“相同的”或类似，不管大小？ [英] What algorithm could be used to identify if images are the "same" or similar, regardless of size?

问题描述

TinEye 是反向图片搜索引擎，允许您上传/链接到图片，它是能够搜索通过它抓取的十亿张图片，并且它将返回其发现的图片的链接是相同的图片。

TinEye, the "reverse image search engine", allows you to upload/link to an image and it is able to search through the billion images it has crawled and it will return links to images it has found that are the same image.

但是，它不是一个朴素的校验或任何与此相关的。它通常能够找到比您提供的原始图像更高分辨率和更低分辨率的图像，以及更大和更小的尺寸。这是一个很好的服务，因为我经常找到一个图像，并希望它的最高分辨率版本的可能。

However, it isn't a naive checksum or anything related to that. It is often able to find both images of a higher resolution and lower resolution and larger and smaller size than the original image you supply. This is a good use for the service because I often find an image and want the highest resolution version of it possible.

不仅如此，我已经找到了相同图像集的图像，其中图像中的人处于不同的位置，但背景大部分保持在相同。

Not only that, but I've had it find images of the same image set, where the people in the image are in a different position but the background largely stays the same.

什么类型的算法可以 TinEye 使用允许它比较图像与各种尺寸和压缩比的其他人，但仍然准确地弄清楚，他们是相同的图像或集？

What type of algorithm could TinEye be using that would allow it to compare an image with others of various sizes and compression ratios and yet still accurately figure out that they are the "same" image or set?

推荐答案

这些算法通常是基于指纹的。指纹是一个相当小的数据结构，像一个长哈希码。然而，指纹函数的目标与哈希函数的目标相反。一个好的哈希函数应该为非常类似（但不等于）的对象产生非常不同的代码。相反，指纹函数应该为相似的图像生成相同的指纹。

These algorithms are usually fingerprint-based. Fingerprint is a reasonably small data structure, something like a long hash code. However, the goals of fingerprint function are opposite to the goals of hash function. A good hash function should generate very different codes for very similar (but not equal) objects. The fingerprint function should, on contrary, generate the same fingerprint for similar images.

只是给你一个例子，这是一个（不是特别好）指纹功能：将图片大小调整为32x32平方，规范化和量化颜色，的颜色到像256.然后，你有1024字节的指纹的图像。只需保留一个指纹表=> [图像URL列表]。当您需要查看与给定图像类似的图像时，只需计算其指纹值并找到相应的图像列表。容易。

Just to give you an example, this is a (not particularly good) fingerprint function: resize the picture to 32x32 square, normalize and and quantize the colors, reducing the number of colors to something like 256. Then, you have 1024-byte fingerprint for the image. Just keep a table of fingerprint => [list of image URLs]. When you need to look images similar to a given image, just calculate its fingerprint value and find the corresponding image list. Easy.

有什么不容易 - 在实践中，指纹功能需要对作物，仿射变换，对比度变化等的鲁棒性。功能是一个单独的研究课题。通常他们是手工调整的，并使用了很多启发式（即使用有关典型的照片内容，关于图像格式/ EXIF等附加数据的知识）。

What is not easy - to be useful in practice, the fingerprint function needs to be robust against crops, affine transforms, contrast changes, etc. Construction of good fingerprint functions is a separate research topic. Quite often they are hand-tuned and uses a lot of heuristics (i.e. use the knowledge about typical photo contents, about image format / additional data in EXIF, etc.)

另一种变化是使用多个指纹功能，尝试应用它们中的每一个并组合结果。实际上，它类似于找到相似的文本。只是代替文字包，图像相似性搜索使用指纹袋并且找到来自一个包的多少元素与来自另一个包的元素相同。如何使此搜索有效是另一个主题。

Another variation is to use more than one fingerprint function, try to apply each of them and combine the results. Actually, it's similar to finding similar texts. Just instead of "bag of words" the image similarity search uses a "bag of fingerprints" and finds how many elements from one bag are the same as elements from another bag. How to make this search efficient is another topic.

现在，关于文章/论文。我找不到一个好的文章，将概述不同的方法。我知道的大多数公共文章讨论具体方法的具体改进。我可以推荐您检查这些：

Now, regarding the articles/papers. I couldn't find a good article that would give an overview of different methods. Most of the public articles I know discuss specific improvement to specific methods. I could recommend to check these:

使用小波的内容指纹识别。这篇文章是关于使用小波的音频指纹识别，但是同样的方法可以适用于图像指纹识别。

"Content Fingerprinting Using Wavelets". This article is about audio fingerprinting using wavelets, but the same method can be adapted for image fingerprinting.

代码分组：
智能哈希函数设计为音频和IMAGE RETRIEVAL 。关于位置敏感哈希的信息。

PERMUTATION GROUPING: INTELLIGENT HASH FUNCTION DESIGN FOR AUDIO & IMAGE RETRIEVAL. Info on Locality-Sensitive Hashes.

大型部分重复网络图片搜索的捆绑功能。一个非常好的文章，谈谈SIFT和捆绑功能的效率。它还有一个很好的参考书目

Bundling Features for Large Scale Partial-Duplicate Web Image Search. A very good article, talks about SIFT and bundling features for efficiency. It also has a nice bibliography at the end

这篇关于可以使用什么算法来识别图像是否是“相同的”或类似，不管大小？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！