图像指纹算法概述

在google上面搜索图像识别的时候，搜到一篇好文章，在这里翻译一下，所有版权来源于https://realpython.com/blog/python/fingerprinting-images-for-near-duplicate-detection/，作者源代码：https://github.com/realpython/image-fingerprinting/blob/master/code/output.csv虽然英语过了六级，但是仍然有很多专业术语不懂，翻译水平也只能是凑合而已。

注：本文写作的目的是这篇文章的作者发现建立网站的时候，很多用户用相同的头像，这导致识别度降低，为了防止用户上传相同的图片作为自己的头像以及上传不当的图像文件，作者研究了这个图像指纹的问题。（等我翻译完成竟然发现网上已经有人翻译好了http://python.jobbole.com/81277/，自愧不如）

不妨想一想，每一个人都有属于他自己的指纹一样，指纹能够识别人，那么图片的指纹也可以用来识别图片。

现在用三个阶段来实现算法：

　　1.将一组不合适的图像指纹计算出来，然后将这些图像指纹存入数据库中。

　　2.当用户上传一个新的客户资料中的头像时，我们将会将其与数据库中的图像指纹进行对比。如果发现数据库中任意一个头像指纹与该用户上传的图像符合，管理员将会阻止用户上传该图像作为自己的头像。 

　　3.依次类推，识别出色情图片，根据色情图片的指纹创建一个收集色情图片指纹的数据库，用来防止用户上传色情图片。

我们的程序并不是完美的，有效的。即使效率缓慢但是目的终究是达到了，虽然没有完全的解决问题，但是减少了用户上传的80%以上的不当文件。

那么接下来最大的问题是如何创建图像指纹？

请继续阅读并找出答案。。。

我们接下来需要做什么？

我们将利用图像指纹进行重复识别，一般称这种技术为“图像感知哈希法”或者“图像哈希法”。

什么是图像指纹或者说什么是图像哈希？

图像哈希的过程是通过检测图像的内容，然后构造一个值，该值在这些图像内容的基础上唯一的标志这个图像

如下图所示：

在给定的输入的图像中， 我们将使用一个散列函数，并基于图像视觉上的外观计算它的“图像散列”值，相似的头像，它的散列值应该也是相似的。使用图像哈希算法可以大大简化重复图像检测的程序。

在这里，我们将使用“difference hash”，或者仅仅使用dHash算法来计算我们的图像指纹。简单来说，dHash着力探究相邻像素之间的区别。哈希值是在这个基础上被创建出来的。

为什么我们不直接使用md5,sha-1等等算法？

不幸的是，我们不能在本例中使用加密散列算法。这是由于加密散列算法本身的性质——输入文件中非常微小的变化都会造成显著不同的哈希值。在本次图像指纹的案例中，是希望类似图片的输入能得到类似哈希值的输出。

图像指纹能应用在哪些领域？

就如同上面的例子，你可以用图像指纹来管理你的不合适的图像数据库，当用户尝试上传此类图像的时候你可以提醒他们。

你可以建立一个类似于TinEye的搜索引擎，用来跟踪图片，并且找出类似图片出现的网页。

你甚至可以通过使用图像指纹识别来管理你的个人相集。想象一下，你有一个存储你个人图片的硬盘，但是需要一种方法备份部分修剪的图片，并能够保持唯一的副本——图像指纹可以帮你做到。

简单来说，你可以在任何与图像重复副本检测的地方使用图像指纹或者图像散列方法。

我们需要哪些库？

为了制作我们的图像指纹识别方案，将会用的以下三个python库：

• PIL/Pillow用来读取或者加载图像
• ImageHash,其中包含dHash算法的实现
• 以及Numpy/Scipy，计算图像散列

你也可以通过如下命令搭建所有环境（python2.7）：

$ pip install pillow imagehash

第一步：创建图像指纹数据集

我们并不打算使用我日常在约会网站上遇到的色情图片，我已经找到了一个我们可以使用的数据集。

对于计算机视觉研究人员来讲，CALTECH-101数据集是个**。它包含7500+张来自101个目录的图片，包括人、摩托车和飞机。

我从这7500张图片中随机抽取了17张。

然后从这17张随机抽选的图片中，我通过随机调整图片的尺寸创建了N个新的图像。我们的目标是找到这些近乎重复的图像，这就像是大海捞针。

并且，由于图片除了宽高尺寸外都是相同的，由于他们都没有相同的尺寸，我们不能简单的使用MD5校验，更重要的是内容类似的图片可能具有显著不同的哈希值，原因已解释，相反，我们可以使用图像散列，因为类似的图片拥有相似的哈希指纹。

那么现在开始编写关于数据集的代码，并将其命名为index.py：

 

# coding=utf-8
# 导入必要的包
import argparse
import shelve
   import imagehash
import glob
from PIL import Image

# 构建参数解析，并分析参数
ap = argparse.ArgumentParser()
ap.add_argument("-d", "--dataset", required=True,
                help="照片数据集的路径")
ap.add_argument("-s", "--shelve",required=True,
                help="shelve数据集的输出")
args = vars(ap.parse_args())

# 打开shelve数据集
db = shelve.open(args["shelve"], writeback=True)

 

首先，我们要做的就是导入我们需要的包。我们将使用PIL或者Pillow模块中的Image类从磁盘中加载图片。然后用图像指纹库来构建感性序列。

根据上面的代码可知，argparse用于解析命令行参数，shelve用来做python的子典型数据库，并将其存储在磁盘上，glob将用来更加轻易的收集图片的路径位置。

接着，分析命令行参数。第一，--dataset是我们输入图像的路径目录。第二，--shelve是通往shelve数据库的输出路径。

接下来，我们打开shelve数据库并对其进行写入。db将会存储我们的图像哈希值。代码如下：

 

# 在图像数据集中循环
for imagePath in glob.glob(args["dataset"] + "/*.jpg"):
    # 加载图片并计算哈希值的差异
    image = Image.open(imagePath)
    h = str(imagehash.dhash(image))

    # 提取路径中的文件名并更新数据库
    # 用散列作为字典的键，文件名添加到值列表
    filename = imagePath[imagePath.rfind("/") + 1:]
    db[h] = db.get(h, []) + [filename]

# 关闭shelf数据集
db.close()

这些就是我们大致需要的代码工作了，从磁盘中加载图像，并遍历图像数据集，然后创建图像指纹。

现在我们观察以下整个教程中最重要的两条代码：

filename = imagePath[imagePath.rfind("/") + 1:]
db[h] = db.get(h, []) + [filename]

就像我一开始在文章中提到的一样，具有相同指纹的图像被认为是同样的图像。

因此，如果我们的目标是找出相似图片，我们需要创建一个拥有相同指纹值的图像列表。

以上两行代码做的就是这个工作。

第一行提取图像的文件名，第二行给图像创建一个拥有相同哈希值的列表。

从数据库中提取图像指纹并创建我们的散列数据库，使用如下命令：

$ python index.py —dataset images —shelve db.shelve

该脚本将会运行几秒钟，一旦完成就好产生一个文件，里面包含了图像指纹—文件名对应的键值对。

这个算法和我几年前在创建约会网站时写的算法一样，我们将不适合的图片收集起来，并计算他们的散列值，存入数据库。当用户提交图像的时候，我只有计算图像的指纹，并将其与数据库中的指纹进行对比，用来判断是否上传被判无效的内容。

下一步我将会告诉你如何执行搜索，以确定图片是否在数据库中有类似的散列值的图像。

第二步：搜索数据库

既然我们已经创建了一个指纹图像数据库，是时候来搜索数据库了。

打开一个名字为search.py的新文件，开始编写代码：

 

# coding=utf-8
# 导入必要的包
from PIL import Image
import imagehash
import argparse
import shelve

# 构建参数解析，并分析参数
ap = argparse.ArgumentParser()
ap.add_argument("-d", "--dataset", required=True,
                help="照片数据集的路径")
ap.add_argument("-s", "--shelve",required=True,
                help="shelve数据集的输出")
ap.add_argument("-q", "--query", required=True,
                help="搜索图像的路径")
args = vars(ap.parse_args())

 

像上次一样，导入我们需要的包，然后解析命令行参数。接下来需要三次转换，--dataset，它是原始图片数据集的路径，--shelve，存放键值对的数据库，以及--query，搜索或者上传图片的路径。我们的目标是根据上传的图片对数据库进行搜索类似哈希值的图片。

接下来，写关于执行搜索的代码：

# 打开shelf数据集
db = shelve.open(args["shelf"])

# 加载需要查询的图片，计算它的图像差分散列值，并从数据库中抓取类似散列值得图像
query = Image.open(args["query"])
h = str(imagehash.dhash(query))
filenames = db[h]
print("Found %d images" % (len(filenames)))

# 在图像内部循环
for filename in filenames:
    image = Image.open(args["dataset"] + "/" + filename)
    image.show()
    
# 关闭数据集
db.close()

我们先打开数据库，并从磁盘中加载图片，计算图像指纹，找出拥有相同指纹值得所有图片。

如果存在任何相同哈希值的图片，将会在图片中循环，依次展示这些图片。

使用这些代码，我们将会判断是否上传的图片已经存在于数据库中。

结果

正如我在文章前段部分提到的，我已经从CALTECH-101数据集中随机采集了17张图片，并通过一些小的尺寸上面的改动创建了N张新图片。

这些图片的尺寸造成只有小部分的像素不同，因此不能使用MD5哈希算法（这一点将会在算法改进中继续探讨）。想法我们需要利用图像散列找到类似的图像。

打开终端，并执行以下命令：

$ python search.py —dataset images —shelve db.shelve —query images/84eba74d-38ae-4bf6-b8bd-79ffa1dad23a.jpg

 

如果不报错的话将会出现以下结果：

上面图片的左边就是输入的图像，我们将用这张图片对数据集进行搜索，找出拥有相同指纹的所有图像。

值得肯定的是，在我们的数据集中有两张图片具有相同的指纹，如图像右边的两张图片所示。虽然从截图上面查看并不很明显，但是他们确实是具有相同内容的不同尺寸的图片。

让我们尝试输入另外一张图片：

$ python search.py —dataset images —shelve db.shelve —query images/9d355a22-3d59-465e-ad14-138a4e3880bc.jpg

结果如下：

perfect!

改进算法

有很多方法可以改进我们的算法，但是最重要的一种方法时考虑到散列是相似的并不是完全一样的。

比如说，我们这次提交的图片都是在尺寸上（向上或向下）调整了几个百分点的大小，如果图像调整比较大的话，导致纵横比改变，散列值将不会完全相同。

但是图片将是类似的。

为了找出相似并不相同的图片，我们需要进一步用到Hamming距离法。Hamming距离法可以计算出不同哈希值的像素位数。因此,两个具有一位像素相差的图像基本上比10位相差的的图新更相似。

但是我们遇到第二个问题，算法的扩展性。

试想一下，有一张被输入的图像，并需要找到数据库中所有类似的图像。那么我们可以计算输入图像和每一个数据库图像的Hamming距离。

随着数据集的增大，将会导致更多的时间比较所有的哈希值。最后，我们的散列数据库将会到达一定的规模以至于单纯的线性比较是不实际的。

有一个解决方案就是，使用Kd树分类法或者VP树分类，从线性搜索变成亚线性，减少搜索问题的复杂性。

总结

在这篇文章中，我们学会了如何构建和利用图像散列法执行近似图像的检测。图像散列应用在图像视觉内容研究中。

正如指纹可以识别人一样，一个图像的哈希值也可以唯一的标志图像。

使用我们的质问图像知识，再建立一个查找类似图像的系统无非是用的图像的哈希算法。

引用：https://www.cnblogs.com/wing1995/p/4471034.html

            https://realpython.com/blog/python/fingerprinting-images-for-near-duplicate-detection/