可以使用什么算法来识别图像是否“相同"?或类似的，无论大小? [英] 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.

置换分组:音频和智能散列函数设计图像检索.有关位置敏感哈希的信息.

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屋！