卢松松博客

Google图片搜索的原理

 人参与 | 时间:2012年05月17日 21:55

针对这个问题,请教了算法组的同事,他分享了基本的思路:

对于这种图像搜索的算法,一般是三个步骤:

1. 将目标图片进行特征提取,描述图像的算法很多,用的比较多的是:SIFT描述子,指纹算法函数,bundling features算法,hash  function(散列函数)等。也可以根据不同的图像,设计不同的算法,比如图像局部N阶矩的方法提取图像特征。

2. 将图像特征信息进行编码,并将海量图像编码做查找表。对于目标图像,可以对分辨率较大的图像进行降采样,减少运算量后在进行图像特征提取和编码处理。

3.  相似度匹配运算:利用目标图像的编码值,在图像搜索引擎中的图像数据库进行全局或是局部的相似度计算;根据所需要的鲁棒性,设定阈值,然后将相似度高的图片预保留下来;最后应该还有一步筛选最佳匹配图片,这个应该还是用到特征检测算法。

其中每个步骤都有很多算法研究,围绕数学,统计学,图像编码,信号处理等理论进行研究。

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

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

Google图片搜索的原理 好文分享 第1张

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

Google图片搜索的原理 好文分享 第2张

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

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

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

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

第一步,缩小尺寸。

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

Google图片搜索的原理 好文分享 第3张

第二步,简化色彩。

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

第三步,计算平均值。

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

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

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

第五步,计算哈希值。

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

Google图片搜索的原理 好文分享 第4张

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

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

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

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

文章来源:阮一峰的博客

相关阅读:

一款用于改进图片搜索效果的标注游戏

Google搜索引擎的工作原理

百度解构第一季 - 理解用户搜索行为

相似图片搜索的原理(二)

顶: 1踩: 0

来源:,欢迎分享,(QQ/微信:13340454)

必填

选填

选填

◎已有 41 人评论,微信:QQ13340454

1楼123  2015-06-24 20:55:37
大话西游比罗马复兴还老吗?
顶: 0踩: 0 回复
2楼囧闻囧事  2014-04-10 18:58:52
喜大普奔
顶: 0踩: 0 回复
3楼散户散闻  2014-02-14 11:22:33
用过56K的猫拨号上网,在榕树下混过……
至今还会在BBS胡扯
顶: 0踩: 0 回复
4楼美女高清  2014-01-17 23:17:23
都洗洗睡吧
顶: 0踩: 0 回复
5楼南京展览公司  2011-12-23 17:01:15
是啊,看来只有80后才玩过
顶: 0踩: 0 回复
6楼千寻  2011-12-06 23:59:14
离老网虫还差那么一点!!!
顶: 0踩: 0 回复
7楼枇杷酒  2014-10-22 16:33:42
它掌握着搜索引擎的核心技术。
顶: 0踩: 0 回复
8楼方芳芳  2014-09-28 17:08:47
没做过不知道,不过要做还是要对每一个像素进行分析,再转化灰阶度等再输出像素自己看看有什么规律。我觉得,如果能够识别出物体的轮廓,就已经进步了一大步。之后估计不成问题。
顶: 0踩: 0 回复
9楼囧闻囧事  2014-01-12 10:57:28
谷歌太牛了这个搜索的功能真是不错,google有些地方值得借鉴啊
顶: 0踩: 0 回复
10楼广州seo  2013-06-03 10:24:11
不是很多,不过你说的这些就已经非常受惠
顶: 0踩: 0 回复
11楼卢松松  2012-06-11 17:33:16
文章来源以及改了哈

顶: 0踩: 0 回复
12楼广州seo  2013-01-03 10:08:50
确实有这样的问题!很伤啊
顶: 0踩: 0 回复
13楼爱早起  2012-05-23 16:50:07
好像阮一峰很久以前写过一篇这样的文章呢,呵呵,怎么又成知乎的了?
顶: 0踩: 0 回复
14楼三适松  2012-05-22 09:15:34
分析的很棒。
顶: 0踩: 0 回复
15楼湘流域  2012-05-19 10:45:51
照这样说,按照哈希值可以随意组合一张图片?
顶: 0踩: 0 回复
16楼迷糊街网站  2012-05-18 23:03:58
学习了,分享一下
顶: 0踩: 0 回复
17楼一个臭卖袜子的  2012-05-18 22:09:26
我就拿它来偷看美女洗澡
顶: 0踩: 0 回复
18楼一个臭卖袜子的  2012-05-18 22:09:08
和透视望远镜的热传导原理差不多
顶: 0踩: 0 回复
19楼刘印博客  2012-05-18 19:53:58
呵呵,大概的了解了下~
顶: 0踩: 0 回复
20楼育儿知识大全  2012-05-18 19:31:50
很专业的说
顶: 0踩: 0 回复
21楼实木家具  2012-05-18 18:37:32
总觉得现在谷歌越来越靠不住,收录虽然很多,每日流量很小。百度虽然苛刻,但是流量来的还是要大于百度几倍
顶: 0踩: 0 回复
22楼苦荞茶网  2012-05-18 15:08:00
对于GG的图片搜索是不错的,我们自已的站能也发展这样一个功能,是相当好了
顶: 0踩: 0 回复
23楼推广者博客  2012-05-18 14:46:31
这个技术牛。
顶: 0踩: 0 回复
24楼拾穗者博客  2012-05-18 14:15:11
这个不懂啊
顶: 0踩: 0 回复
25楼女生长胡子  2012-05-18 13:53:59
谷歌太牛了
顶: 0踩: 0 回复
26楼消逝的硝烟博客  2012-05-18 13:39:03
这个好,大致了解了图片搜索的原理,以后可以写个简单的试下。
顶: 0踩: 0 回复
27楼快乐黑马  2012-05-18 13:20:08
海量图像编码做查找表。松松收集的技术文章,强大。图片搜索你看了百度的 stu.baidu.com吗
顶: 0踩: 0 回复
28楼编程入门  2012-05-18 13:17:23
谷歌技术在不断探索和进步
顶: 0踩: 0 回复
29楼Android开发  2012-05-18 13:16:18
这样的算法还只是初级阶段,估计以后会出现更高级的
顶: 0踩: 0 回复
30楼虚拟主机服务商  2012-05-18 12:31:10
百度的也有图片搜索 不过很不给力
顶: 0踩: 0 回复
31楼互联网战  2012-05-18 12:23:31
我以前做过一个简单的车牌识别系统,最后一步模式匹配和这里说的比较相似。
顶: 0踩: 0 回复
32楼零度记忆  2012-05-18 12:00:46
百度也有这个功能了吧,叫识图
顶: 0踩: 0 回复
33楼赖林林博客  2012-05-18 11:37:44
哇 技术文章 学习了 这个 搜图这个原理 一直困扰着赖林林 今天终于明白了。
顶: 0踩: 0 回复
34楼皮卡车改装  2012-05-18 11:03:19
google的技术真是高啊
顶: 0踩: 0 回复
35楼华子SEO博客  2012-05-18 10:51:02
有点专业啊 看了半天。。。
顶: 0踩: 0 回复
36楼SEO云南  2012-05-18 10:47:30
这段时间对于图片搜索比较关注
顶: 0踩: 0 回复
37楼中山尚人  2012-05-18 10:23:55
图片也有指纹了,方便找图。
顶: 0踩: 0 回复
38楼光的传人  2012-05-18 10:16:18
太专业了~了解下!
顶: 0踩: 0 回复
39楼雷东升  2012-05-18 10:02:38
还没用过谷歌的图片搜索,看来我真的是太落伍了
顶: 0踩: 0 回复
40楼雷森  2012-05-18 09:49:00
Google图片搜索帮我找到好几个朋友。
顶: 0踩: 0 回复
41楼电视购物  2012-05-18 09:42:12
百度能跟上脚步么
顶: 0踩: 0 回复
42楼蚂蚁在线  2012-05-18 08:55:35
知乎很不错哦
顶: 0踩: 0 回复
43楼小游戏  2012-05-18 08:43:20
这个搜索的功能真是不错,google有些地方值得借鉴啊
顶: 0踩: 0 回复
44楼没有如果  2012-05-18 08:19:43
从理论的角度解释。明白了
非常喜欢Google图片搜索。很好用
顶: 0踩: 0 回复
45楼淘宝开店培训  2012-05-18 08:01:51
谷歌技术就是比较好
顶: 0踩: 0 回复
46楼卢锋博客  2012-05-18 01:44:39
对技术方面表示egg hurt
顶: 0踩: 0 回复
47楼nol  2012-05-17 23:56:29
求种子
顶: 0踩: 0 回复
48楼挨踢小茶  2012-05-17 23:46:18
这个能广泛应用在交友网站,识别个人头像是真实的,还是网络上复制的。
顶: 0踩: 0 回复
49楼网型网秀  2012-05-17 23:08:56
原来是这样,Google图片搜索还挺不错的!
顶: 0踩: 0 回复