图像相似性比较实践

Question

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 的整数，顺序是无关的，只要保持一致即可。

这样，这个图片的指纹就通过一个 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 正准备实现。

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

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

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)
}

执行结果：

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