什么算法可以用来确定图像是否是＆QUOT;相同＆QUOT;或相似，无论大小？ [英] 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 使用，将允许它的图像与其他人不同尺寸和COM pression比率的比较，但仍然准确地搞清楚，他们是相同的图像或设置？

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?

推荐答案

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

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.

只是为了给你举个例子，这是一个（不是特别好）指纹功能：图片大小调整为32×32平方，规范和和量化的颜色，减少了颜色，像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.

PERMUTATION分组： 智能散列功能设计用于音频和放大器;图像检索。信息的局部性敏感散列。

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

捆绑的大规模局部复制Web图像搜索特点。一篇非常好的文章，谈到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

这篇关于什么算法可以用来确定图像是否是＆QUOT;相同＆QUOT;或相似，无论大小？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！