登录 | 地图 欢迎访问【UZ导航】
当前位置:网站首页 > 推荐 > 正文

Google 按图搜索的原理

admin 2019-10-13 260 浏览 0 评论

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

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

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

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

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

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

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

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

1.jpg

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

2.jpg

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

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

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

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

第一步,缩小尺寸。

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

3.jpg

第二步,简化色彩。

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

第三步,计算平均值。

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

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

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

第五步,计算哈希值。

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

4.jpg

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

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

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

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


相关推荐

嘉兴女工8秒包1个粽子 月收入过万羡煞网友
嘉兴女工8秒包1个粽子 月收入过万羡煞网友

  又是一年#端午节#到来,最受大家关注的自然是粽子。近日,在浙江嘉兴,一位专门包粽子的高阿姨因手速快、收入高,引起了网友的关注。高阿姨是一名经验丰富的工人,已...

1周前 (06-25) admin

端午节粽子口味地图出炉 “甜咸之争”你是哪一派?
端午节粽子口味地图出炉 “甜咸之争”你是哪一派?

“吃货不分南北,口味必分甜咸”,作为端午节的特色美食,粽子几乎每年都会引发咸甜之争。粽子的甜咸之争其实与气候环境、文化习俗等因素关系密切,中国天气网根据用户调查...

1周前 (06-25) admin

萌娃商场认错妈妈抱着不撒手,亲妈出现后萌娃一脸懵
萌娃商场认错妈妈抱着不撒手,亲妈出现后萌娃一脸懵

近日,成都一网友上传了一段视频。在上班路上一小男孩突然跑过来叫她妈妈,接着她抱起了小男孩。随后小男孩抱着他不愿松手,不一会儿妈妈从远处走了过来。大家都告诉小孩妈...

2周前 (06-23) admin

亚马逊的直播带货,还差点什么
亚马逊的直播带货,还差点什么

5月22日,阿里巴巴发布了2020财年全年及第四季度业绩,阿里2020财年(2019年4月到2020年3月)的消费型商业业务交易额突破1万亿美元,成为全球首家交...

1个月前 (05-28) admin

为什么平时点外卖用的美团,离两个马爸爸越来越近了?
  • 为什么平时点外卖用的美团,离两个马爸爸越来越近了?
  • 为什么平时点外卖用的美团,离两个马爸爸越来越近了?
  • 为什么平时点外卖用的美团,离两个马爸爸越来越近了?
  • 为什么平时点外卖用的美团,离两个马爸爸越来越近了?
3月共有5亿海外用户涌入速卖通,App下载量已超过亚马逊
3月共有5亿海外用户涌入速卖通,App下载量已超过亚马逊

5月23日消息英国金融债券媒体LearnBonds近日发布报告称,受疫情影响,网购在海外迅速普及开来,全球手机购物用户激增。阿里巴巴旗下中国最大的跨境电商...

1个月前 (05-25) admin

拳王泰森放话:我欢迎任何人的挑战,愿意和任何人开战
  • 拳王泰森放话:我欢迎任何人的挑战,愿意和任何人开战
  • 拳王泰森放话:我欢迎任何人的挑战,愿意和任何人开战
  • 拳王泰森放话:我欢迎任何人的挑战,愿意和任何人开战
  • 拳王泰森放话:我欢迎任何人的挑战,愿意和任何人开战
受疫情影响 2020纽约车展正式宣布取消
受疫情影响 2020纽约车展正式宣布取消

当地时间5月22日,纽约车展组委会宣布受新冠肺炎疫情的影响,2020年纽约车展正式取消,下一届纽约车展将于2021年3月31日-4月11日期间举行,其中3月31...

1个月前 (05-23) admin

京东正式上线“自营房产”
京东正式上线“自营房产”

5月22日,京东房产与中骏集团在京签署战略协议,中骏集团成为首个在京东开设自营旗舰店的房产开发商,这也标志着京东正式上线“自营房产”业务。据京东方面介绍,通过此...

1个月前 (05-23) admin

重量级第一人泰森-富里:我很丑还秃顶,但没有人能战胜我
重量级第一人泰森-富里:我很丑还秃顶,但没有人能战胜我

近日,现WBC/《拳坛》杂志重量级拳王英国“吉普赛皇帝”泰森-富里(30-0-1,21KO)在接受媒体采访时表示,他现在是引领拳坛的超级巨星,而且是战无不胜的。...

1个月前 (05-22) admin

我国开通5G基站超20万个 运营商详解如何推进5G融合应用
我国开通5G基站超20万个 运营商详解如何推进5G融合应用

央广网北京5月17日消息(记者吕红桥)据中央广播电视总台经济之声《天下财经》报道,5月17日是世界电信日,工信部、几大运营商在世界电信日大会上重点聚焦5G,介绍...

2个月前 (05-18) admin

欢迎 发表评论: