相似图片搜索的原理

作者: 阮一峰

日期: 2011年7月21日

上个月,Google把"相似图片搜索"正式放上了首页。

你可以用一张图片,搜索互联网上所有与它相似的图片。点击搜索框中照相机的图标。

一个对话框会出现。

你输入网片的网址,或者直接上传图片,Google就会找出与其相似的图片。下面这张图片是美国女演员Alyson Hannigan。

上传后,Google返回如下结果:

类似的"相似图片搜索引擎"还有不少,TinEye甚至可以找出照片的拍摄背景。

==========================================================

这种技术的原理是什么?计算机怎么知道两张图片相似呢?

根据Neal Krawetz博士的解释,原理非常简单易懂。我们可以用一个快速算法,就达到基本的效果。

这里的关键技术叫做"感知哈希算法"(Perceptual hash algorithm),它的作用是对每张图片生成一个"指纹"(fingerprint)字符串,然后比较不同图片的指纹。结果越接近,就说明图片越相似。

下面是一个最简单的实现:

第一步,缩小尺寸。

将图片缩小到8x8的尺寸,总共64个像素。这一步的作用是去除图片的细节,只保留结构、明暗等基本信息,摒弃不同尺寸、比例带来的图片差异。

第二步,简化色彩。

将缩小后的图片,转为64级灰度。也就是说,所有像素点总共只有64种颜色。

第三步,计算平均值。

计算所有64个像素的灰度平均值。

第四步,比较像素的灰度。

将每个像素的灰度,与平均值进行比较。大于或等于平均值,记为1;小于平均值,记为0。

第五步,计算哈希值。

将上一步的比较结果,组合在一起,就构成了一个64位的整数,这就是这张图片的指纹。组合的次序并不重要,只要保证所有图片都采用同样次序就行了。

= = 8f373714acfcf4d0

得到指纹以后,就可以对比不同的图片,看看64位中有多少位是不一样的。在理论上,这等同于计算"汉明距离"(Hamming distance)。如果不相同的数据位不超过5,就说明两张图片很相似;如果大于10,就说明这是两张不同的图片。

具体的代码实现,可以参见Wote用python语言写的imgHash.py。代码很短,只有53行。使用的时候,第一个参数是基准图片,第二个参数是用来比较的其他图片所在的目录,返回结果是两张图片之间不相同的数据位数量(汉明距离)。

这种算法的优点是简单快速,不受图片大小缩放的影响,缺点是图片的内容不能变更。如果在图片上加几个文字,它就认不出来了。所以,它的最佳用途是根据缩略图,找出原图。

实际应用中,往往采用更强大的pHash算法和SIFT算法,它们能够识别图片的变形。只要变形程度不超过25%,它们就能匹配原图。这些算法虽然更复杂,但是原理与上面的简便算法是一样的,就是先将图片转化成Hash字符串,然后再进行比较。

UPDATE(2013.03.31)

这篇文章还有续集,请看这里

(完)

留言(64条)

文中给出的代码 imgHash.py,建议使用网上流行的代码片段(snippet)分享服务,既可以高亮,又可以有一定的评论和修改功能,何乐而不为?这些服务中比较好的有:
- https://gist.github.com/
- http://snipt.org/
- http://pastebay.com/
- http://pastebin.com/

希望这些信息对你有用。

希望google继续开发出哼哼调子就可以搜索歌曲的服务,然后再交叉一下,哼哼调子会搜索图片,上传图片会搜索音乐,等这些交叉足够宽泛后,还需要一步,就是让第一次搜索的结果作为第二次搜索的条件,这想当于人在发呆时意识流的联想,再然后,google作为一个能对外界刺激(搜索框内的条件)产生反应(搜索结果)的生命体就诞生了

好像不是这么简单。Google Image Search可以用随意截取的小图(不是指微缩图)去搜大图,不是文章里算法能够做到的。

谷歌也推出了这个功能的chrome扩展.安装后对着网页上的图片右击就可以了.
https://chrome.google.com/webstore/detail/dajedkncpodkggklbegccjpmnglmnflm?hl=zh-CN#

长见识了。不过应该是把图片数字化可以让机器读懂的信息。毕竟机器不能像人一样理解图片。

首页的摄影作品很好看。

谁能说说阮兄在网站首页加Flickr照片展示的办法?
图片上显示Flickr的logo,但是图片另存下来就没有了?

阮老师请分享一下你经常浏览的国内和国外网站,谢谢!

我觉得更进一步的方法是这样(受矩阵稀疏表示的启发):可以将图片表示成一组线性无关向量的线性组合,如果这些基底都有实际的意义,比如一个基底表示图片结构,一个表示色彩风格之类的,那么匹配应该会更精准,也会有更神奇的效果

iphone上可以根据人哼唱的曲调来找歌的大概也是这类算法吧?

不久的将来,文字搜索可能会慢慢被音频、图像搜索取代。

很久之前就知道有这种服务,但现在才知道原理,真厉害,不是什么人都能想到的吖~

OT一下,看来博主是 How I Met Your Mother 的粉丝

怪不得有时候只能搜出色调相似的图片。Google也许有一些改进,因为用人的照片搜,基本上只能搜出人,即使只能搜出别人也一样。

@zhiqiang,我也觉得不止这么简单…

引用oldrev的发言:

OT一下,看来博主是 How I Met Your Mother 的粉丝

于是我就是为了这个来吐槽

用了一下,确实很棒,我找我头像的图片,来源都找到了

请教阮大哥:对于不同的图片格式原理是一样的吗?动态的GIF图片?

这个要顶。阮兄动作真快。

我怎么觉得是用 svm + image kernel (histogram) 来做的?

估计百度以后会用上的。

引用ivalyn的发言:

希望google继续开发出哼哼调子就可以搜索歌曲的服务

哼哼调子就可以搜歌曲的功能已经有些网站有了 我记得国内一个网站就有 很不成熟

hash算法的选择和优化很考水平的, 不是那么简单的事情.
甚至可能用到了遗传算法等东西来利用集群对算法进行优化.

我觉得这篇文章对我蛮有用的,我想通过微支付 给你付款,怎么显示说 交易已结束啊?

@nivek:

有人恶意交易,一下子把剩余份额都拍下,导致交易结束。

现在已经好了。

按照這個快速算法不能解釋 TinEye 的搜索,難道是分區識別?那樣指紋信息也就太大了~

我觉得这个功能有一个副作用,我们自己上传的图片会被google收集到,用的人多的话,google轻而易举就取得了好多我们原本不会不会公开的图片。

在这之上再对颜色,物体特征会更精准吧

@luluch 你上传后,Google帮你搜索到很多一样的图,不就说明其实这个图早都在网上有了么?

引用nixes的发言:

@luluch你上传后,Google帮你搜索到很多一样的图,不就说明其实这个图早都在网上有了么?

比如说,我想搜一下我熟悉的朋友在网上有没有其它的照片,于是我上传了一张我朋友的照片,结果却搜不出相似的,但是我这张照片还是传到google的服务器。

看到有人说把收到的交友照片放到这个搜索引擎中检索,鉴别是不是对方拿明星照来糊弄。
把朋友的照片放进去搜了一下,结果不是太有意义。

阮大哥,那个摄影作品展示,应该加个提示是能左右翻页的。。。我找了半天还以为只一个照片,刷新也不变,后来发现把鼠标放图片上是能翻页的。。。这个用户体验不好!!

阮前辈的博文必看

如果我想对图片式样的书籍或者扫描文件进行关键字识别呢?

还可以应用这样的算法?

这要多每个文字进行分割,对每个文字取得hash字符串?

呵呵,想和你讨论一下。

嗯,用来找饭否一周年的头像墙倒是很好用,谢谢!

谷歌正在组建最大的天网 哈哈

请问各位,实现局部图片搜索全图需要学习什么?

如果要是能够开发出一种图片搜索,根据图片中人物的头像来搜索出该人的信息就好了。

这种算法对于形状相似但不同的放置情况却无法识别啊,比如横躺的三角形和竖直的三角形就无法识别了。。。

引用辉子的发言:

这种算法对于形状相似但不同的放置情况却无法识别啊,比如横躺的三角形和竖直的三角形就无法识别了。。。

用余弦相似度可以识别吧

谢谢老师,今天第一次,看您的博文,很强大,很受教,以后锁定您写的东西!

老师,对于图片是这样,那有没有对文章的算法呢,比如传说的语意分析算法,或者文章匹配算法呢···

尝试了一下,发现效果很不好,单纯做二值检索准确率肯定很低。

这个可以试着玩玩

写的简洁易懂~

请问本文用的"感知哈希算法"(Perceptual hash algorithm),不就是pHash么,为啥还说“实际应用中,往往采用更强大的pHash算法和SIFT算法”呢?

@万军:


文中的算法只是最简情况,而pHash是一个正式的产品,功能强大,两者不一样啊。

原文【得到指纹以后,就可以对比不同的图片,看看64位中有多少位是不一样的。在理论上,这等同于计算"汉明距离"(Hamming distance)】
使用汉明距离还是余弦相似性呢?比如有两张图片的灰度序列为
g1 = [0, 1, 0, 1, 1, 0],g2 = [1, 0, 1, 0, 0, 1](0,1位置完全相反)
汉明距离 hammingDistance(g1, g2) 为 6,最大值,也就是两张图片完全一样;
余弦相似性 cosineSimilarity(g1, g2) 为 0,两张图片完全不一样。
那种相似性算法正确呢?

@legend:

汉明距离的话应该是距离越小越相似吧?

将缩小后的图片,转为64级灰度。也就是说,所有像素点总共只有64种颜色。

这句话不大严密吧。应该说每个像素点的颜色只能用64种颜色之一来表示。

引用辉子的发言:

这种算法对于形状相似但不同的放置情况却无法识别啊,比如横躺的三角形和竖直的三角形就无法识别了。。。

应该是不具有旋转不变性吧

通俗易懂!赞一个。

引用万军的发言:

请问本文用的"感知哈希算法"(Perceptual hash algorithm),不就是pHash么,为啥还说“实际应用中,往往采用更强大的pHash算法和SIFT算法”呢?

因为混淆了均值哈希算法和感知哈希算法,最简单那个是均值哈希算法

我必须要说,这篇文章写得真是太好了


我目前使用的是安卓手机,安装了Chrome beat 版本,在打开google搜索,进入图片搜索,没有发现识图图标,扩展插件也安装不上,难道在安卓网页版google就没有识图功能吗?
如果有怎么来的安装使用?


2016年6月27日

引用legend的发言:

原文【得到指纹以后,就可以对比不同的图片,看看64位中有多少位是不一样的。在理论上,这等同于计算"汉明距离"(Hamming distance)】
使用汉明距离还是余弦相似性呢?比如有两张图片的灰度序列为
g1 = [0, 1, 0, 1, 1, 0],g2 = [1, 0, 1, 0, 0, 1](0,1位置完全相反)
汉明距离 hammingDistance(g1, g2) 为 6,最大值,也就是两张图片完全一样;
余弦相似性 cosineSimilarity(g1, g2) 为 0,两张图片完全不一样。
那种相似性算法正确呢?


你这个不太对吧。一般来说,汉明距离越大图片相似度越小的。
然后我的实验里使用汉明距离跟余弦相似度,比较之后发现汉明距离的效果要好于余弦相似度。


阮老师,请问这个图片是怎么得到的呢?这不是灰度图,像是二值化图,我用java来写这段均值算法,尝试多次都没有得到相同的指纹。

之前提问了个问题,不知道为啥没显示出来
------------------------------------------------

问题大概是利用示例中的算法规则,写的代码不能得出示例中的hash值。今天把python运行成功了,使用的是示例中的大图 http://image.beekka.com/blog/201107/bg2011072103.jpg
但得出的hash值于文中不相同 :

C:\Python27>python.exe imgHash.py C:\imagetest\c3\bg2011072103.jpg c:\imagetest\c3\abc\
avg=161
hash_=175f2f63435be3e7

撸了个Android版本,https://github.com/gavinliu/SimilarPhoto

"第四步,比较像素的灰度"
这个标题我觉得改为
“第四步,将灰度图转换为二值图”比较好
因为后面贴的图是纯黑白的,也就是二值图

阮老师你好,有没有专门讲图片水印技术的书籍或者博客可以推荐一下

您好,能不能写一篇视频相似度判断的原理入门教程?感谢。

这网页写的真糙,不过帖子是干货

请问一下,为什么要做这个处理:
return reduce(lambda x, (y, z): x | (z enumerate(map(lambda i: 0 if i 0)

不是直接用64位吗?

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接