图像相似性比较实践

标签: Go | 发表时间:2018-09-07 11:37 | 作者:
出处:https://colobu.com/

2008年TinEye上线了图片搜索,开始是注册制,后来逐步放开。2011年, Google也上线了相似图片搜索,通过用户上传的图片,可以搜索相似的图片。
参考文档中提供了一些介绍图像搜索的一些文章, 尤其是阮一峰2011年和2013年两篇普及性的文章,可以帮助你了解图像相似搜索的原理。

图像相似性搜索应用广泛、除了使用搜索引擎搜索类似图片外,像淘宝可以让顾客直接拍照搜索类似的商品信息、应用在商品购物上。也可以应用物体识别比如拍图识花等领域。目前我在调研图片鉴权的方案,通过一张图片和图片库中的图片进行比对,来确定这张图片是否侵权,或者退一步讲,图片库中是否包含和这张图片类似。 这个需求和目前深度学习应用中的图像识别还不一样, 图像识别是需要将图像中的物体识别出来, 猫啊狗啊什么的,而我所要做的就是一个查找相似图片的东西。

Neal Krawetz博士看到了一些关于TinEye原理的询问, 虽然他并不知道TinEye是怎么实现的,但是根据搜索结果,他判断是基于感知哈希算法(Perceptual hash algorithm)的变种,他于2011年5月写了一篇文章,介绍相关的技术。

背景知识

感知哈希算法根据图像的特征生成一个确定的指纹,这些指纹可以用来比较。指纹越接近,说明图片越接近。在文章中他介绍了一个非常简单的感知哈希算法, Average Hash algorithm,以美女Alyson Hannigan照片为例,计算指纹(hash)的步骤如下:

1、减小图像的尺寸
生成一个 8 X 8的缩略图,一共64个像素。

2、编程灰度图像
这样就从64个像素(64 Red, 64 Green, 64 Blue)变为64中颜色。

3、计算颜色的平均值

4、计算64位中的每一位
简单和平均值比较,根据大小设置1和0

5、计算hash值
把这64bit赋值给一个64bit的整数,顺序是无关的,只要保持一致即可。

8f373714acfcf4d0

这样,这个图片的指纹就通过一个64位的整数表示出来了。图像放大缩小、旋转、对比度、饱和度的变换不会显著改变指纹。其实最大的好处就是

天下武功,无坚不摧,唯快不破

当你比较两张图片的时候,计算它们的hash值,然后再计算它们的汉明距离即可。

虽然平均散列是快速和容易的,但是photoshop的力量是无穷的,如果你对图片进行伽玛校正或者直方图的调整,对颜色进行非线性的改变,上述算法可能就不太准确了。

博士又介绍了 pHash算法, 它扩展了 Average Hash algorithm,使用DCT(离散余弦变换)减少图像的高频数据。

博士又动手写了一个工具,搜索了一批图片进行测试。研究发现, Average Hash非常快,在特定场景下是一个非常好的算法。

这篇文章非常值得你阅读,也引起了广泛的讨论,以及一些编程语言的实现。 博士在2013年又介绍了第三种算法:difference hash,准确性和aHash( Average Hash algorithm)查不多,但是更快。 aHash基于平均值,pHash基于图像频率,而dHash基于直方图。

阅读博士的文章的时候我在想,对于aHash, 分别计算RGB的指纹,用这三个指纹比较是不是会更好?

这里再介绍另外一种技术: SIFT,即尺度不变特征变换(Scale-invariant feature transform,SIFT),是用于图像处理领域的一种描述。这种描述具有尺度不变性,可在图像中检测出关键点,是一种局部特征描述子。 该方法于1999年由David Lowe首先发表于计算机视觉国际会议(International Conference on Computer Vision,ICCV),2004年再次经David Lowe整理完善后发表于International journal of computer vision(IJCV。截止2014年8月,该论文单篇被引次数达25000余次。SIFT在数字图像的特征描述方面当之无愧可称之为最红最火的一种,许多人对SIFT进行了改进,诞生了SIFT的一系列变种。SIFT已经申请了专利。

SIFT好是好,但是是有专利保护的,并且也慢。

这是雷经纬的整理的算法比较:

Go语言实践

以上是图片比对的背景知识,这一节我们介绍一个计算图像指纹,并且和对象进行比较的例子。

这次,我们使用的库是 goimagehash,它实现了aHash、dHash、pHash算法, wHash正准备实现。

例子中我们使用的三张图片分别是:

分别使用三种算法,计算第一张图片和第二张、第三张图片的汉明距离。

     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
     
package main
import (
"fmt"
"image/jpeg"
"os"
"github.com/corona10/goimagehash"
)
func main() {
queryFile, _ := os.Open("Alyson_Hannigan.jpg")
file1, _ := os.Open("Alyson_Hannigan2.jpg")
file2, _ := os.Open("Lena.jpg")
defer queryFile.Close()
defer file1.Close()
defer file2.Close()
imgQuery, _ := jpeg.Decode(queryFile)
img1, _ := jpeg.Decode(file1)
img2, _ := jpeg.Decode(file2)
queryHash, _ := goimagehash.AverageHash(imgQuery)
hash1, _ := goimagehash.AverageHash(img1)
hash2, _ := goimagehash.AverageHash(img2)
distance1, _ := queryHash.Distance(hash1)
distance2, _ := queryHash.Distance(hash2)
fmt.Printf("Distance between images: %d %d\n", distance1, distance2)
queryHash, _ = goimagehash.DifferenceHash(imgQuery)
hash1, _ = goimagehash.DifferenceHash(img1)
hash2, _ = goimagehash.DifferenceHash(img2)
distance1, _ = queryHash.Distance(hash1)
distance2, _ = queryHash.Distance(hash2)
fmt.Printf("Distance between images: %d %d\n", distance1, distance2)
queryHash, _ = goimagehash.PerceptionHash(imgQuery)
hash1, _ = goimagehash.PerceptionHash(img1)
hash2, _ = goimagehash.PerceptionHash(img2)
distance1, _ = queryHash.Distance(hash1)
distance2, _ = queryHash.Distance(hash2)
fmt.Printf("Distance between images: %d %d\n", distance1, distance2)
}

执行结果:

     
1
2
3
     
Distance between images: 2 46
Distance between images: 3 41
Distance between images: 6 36

可以看到,三种方法都能正确的识别出第一张和第二张图片是类似的(<= 6), 而和第三张图片的差别比较大。

对于这次测试,第二个图片我调整了一下饱和度,加了一个小小的水印。 而aHash表现最好。

对于简单的图像查重和相似图片的查找,使用这三种算法就可以了,要是你想根据一个人的正脸,去搜索这个人的侧脸图片,那可能就需要使用SIFT或者其他的算法了。

参考文档

  1. http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html
  2. http://www.ruanyifeng.com/blog/2011/07/principle_of_similar_image_search.html
  3. http://www.ruanyifeng.com/blog/2013/03/similar_image_search_part_ii.html
  4. https://cloud.tencent.com/developer/article/1006121
  5. https://fullstackml.com/wavelet-image-hash-in-python-3504fdd282b5
  6. http://www.infoq.com/cn/articles/image-similarity-algorithm-on-mobile-client
  7. https://github.com/nivance/image-similarity
  8. https://www.cnblogs.com/wangyaning/p/7854046.html
  9. https://github.com/facebookresearch/faiss
  10. https://en.wikipedia.org/wiki/Perceptual_hashing
  11. https://www.zhihu.com/question/19606748
  12. https://baike.baidu.com/item/SIFT/1396275

相关 [图像 相似 实践] 推荐:

图像相似性比较实践

- - 鸟窝
2008年TinEye上线了图片搜索,开始是注册制,后来逐步放开. 2011年, Google也上线了相似图片搜索,通过用户上传的图片,可以搜索相似的图片. 参考文档中提供了一些介绍图像搜索的一些文章, 尤其是阮一峰2011年和2013年两篇普及性的文章,可以帮助你了解图像相似搜索的原理. 图像相似性搜索应用广泛、除了使用搜索引擎搜索类似图片外,像淘宝可以让顾客直接拍照搜索类似的商品信息、应用在商品购物上.

[转][转] 文本相似性算法Simhash原理及实践

- - heiyeluren的blog(黑夜路人的开源世界)
simhash(局部敏感哈希)的原理. simhash广泛的用于搜索领域中,也许在面试时你会经常遇到这样的问题,如果对抓取的网页进行排重,如何对搜索结果进行排重等等. jaccard相似度也是一种相似 算法,它的计算方式比较直观,就是sim(x,y)= (x∩y) / (x∪y),例如:.      若  S={a, d}, T={a, c, d} .

LIRE(Lucene Image Retrieval)相似图像索引和搜索机制

- - CSDN博客云计算推荐文章
众说周知,lucene是一个开源的强大的索引工具,但是它仅限于文本索引. 基于内容的图像检索(CBIR)要求我们利用图像的一些基本特征(如颜色纹理形状以及sift,surf等等)搜索相似的图片,LIRE(Lucene Image Retrieval)是一款基于lucene的图像特征索引工具,它能帮助我们方便的对图像特征建立索引和搜索,作者也在不断加入新的特征供用户使用.

【实践】Spark 协同过滤ALS之Item2Item相似度计算优化 - CSDN博客

- -
CF召回优化,自之前第一版自己实现的基于item的协同过滤算法. http://blog.csdn.net/dengxing1234/article/details/76122465,考虑到用户隐型评分的. 稀疏性问题,所以尝试用Spark ml包(非mllib)中的ALS算法的中间产物item的隐性向量,进行进一步item到item的余弦相似度计算.

solr相似匹配

- - CSDN博客推荐文章
相似匹配   在我们使用网页搜索时,会注意到每一个结果都包含一个 “相似页面” 链接,单击该链接,就会发布另一个搜索请求,查找出与起初结果类似的文档. Solr 使用 MoreLikeThisComponent(MLT)和 MoreLikeThisHandler 实现了一样的功能. 如上所述,MLT 是与标准 SolrRequestHandler 集成在一起的;MoreLikeThisHandler 与 MLT 结合在一起,并添加了一些其他选项,但它要求发布一个单一的请求.

OpenStack实践

- - 开放博客
作者:Baihuogou DevOps Team. 我们在公司内部部署OpenStack主要是内部管理虚拟机的需要. 公司内部之前使用virt-manager来管理内部虚拟机,但是缺点有二:. 虽然提供图形界面,但是是桌面软件形式,需要安装软件. 所以现在需要一个新的管理软件来解决这些问题,满足两个特性:.

趣题:不用相似怎么办?

- flycondor - Matrix67: My Blog
    我老早就写过一个经典的小学几何题. 如果你还没看过这个问题,你一定要去看看. 一个小学奥数老师曾经告诉我,当年带领学生参加这次竞赛时,领队老师们都没有想到这个问题的“小学生解法”,以至于开始质疑这道题是否超纲了. 看到答案后,老师们大为折服——这个问题确实有一个无需任何几何知识的妙解.     今天,同样的事情发生了.

相似图片搜索的原理

- apuar - 阮一峰的网络日志
上个月,Google把"相似图片搜索"正式放上了首页. 你可以用一张图片,搜索互联网上所有与它相似的图片. 你输入网片的网址,或者直接上传图片,Google就会找出与其相似的图片. 下面这张图片是美国女演员Alyson Hannigan. 上传后,Google返回如下结果:. 类似的"相似图片搜索引擎"还有不少,TinEye甚至可以找出照片的拍摄背景.

用Mathematica寻找最相似的汉字

- hhx - Matrix67: My Blog
    Mathematica 提供了一个看上去毫无用途的无厘头函数 Rasterize ,它可以以图片的格式输出运算结果. 比如,下面这个句子可以打印出 (x+1)^n 的展开式的“倒影”:.     今天我突然想到,我们可以利用这个函数很方便地分析汉字在图象上的性质. 函数 Binarize 可以把图象转换为单色单通道, ImageData 则可以把图象转换成数组的形式,以便我们定量分析.

趣题:不用相似怎么办?

- 法法 - Matrix67: My Blog
    我老早就写过一个经典的小学几何题. 如果你还没看过这个问题,你一定要去看看. 一个小学奥数老师曾经告诉我,当年带领学生参加这次竞赛时,领队老师们都没有想到这个问题的“小学生解法”,以至于开始质疑这道题是否超纲了. 看到答案后,老师们大为折服——这个问题确实有一个无需任何几何知识的妙解.     今天,同样的事情发生了.