这是 Adrian Rosebrock 的客座帖子PyImageSearch.com ,一个关于计算机视觉、图像处理和构建图像搜索引擎的博客。
更新:
2014 年 12 月 22 日 - 删除了代码中对行号的引用。
2015 年 5 月 22 日 - 添加了依赖版本。
大约五年前,我正在为一个约会网站做开发工作。他们是一家早期初创公司,但已经开始看到一些初步的吸引力。与其他约会网站不同,这家公司以清白的声誉推销自己。这不是一个你会去勾搭的网站——这是你寻找诚实的人的地方关系 .
在数百万风险投资的推动下(这是在美国经济衰退之前),他们关于真爱和寻找灵魂伴侣的在线广告迅速转变。他们曾被《福布斯》杂志报道过。他们甚至还出现在国家电视台的短暂聚光灯下。这些早期的成功导致了初创公司令人垂涎的指数级增长——他们的用户群是每个月翻倍 。事情看起来对他们来说非常好。
但他们有一个严重的问题——色情问题。
该约会网站的一小部分用户上传色情图片并将其设置为个人资料图片。这种行为破坏了许多客户的体验,导致他们取消了会员资格。
现在,也许对于一些交友网站来说,零星的一些色情图片可能不成问题。或者它甚至可能被认为是“正常”或“预期”,只是在线约会的副产品,被简单地接受和忽视。
然而,这种行为既不能被接受,也不能被忽视。
请记住,这家初创公司将自己定位为优质的约会天堂,没有困扰其他约会网站的污秽和垃圾。简而言之,他们有一个非常真实的风险投资支持的声誉 他们需要坚持。
绝望地,约会网站争先恐后地阻止色情片的爆发。他们聘请了图像管理员团队实际上每天只是盯着管理页面 8 个小时以上 并删除上传到社交网络的任何新的色情图片。
他们实际上在这个问题上投入了数万美元(更不用说无数的工时),只是试图缓和和遏制疫情的爆发,而不是从源头上阻止它。
2009 年 7 月,疫情爆发达到临界水平。八个月来,用户数量首次未能翻倍(甚至开始下降)。更糟糕的是,投资者威胁称,如果该公司不解决问题,他们将撤回资金。
确实,污秽之潮正在冲击着象牙塔,威胁着将其推入大海。
当约会巨头的膝盖开始弯曲时,我提出了一个更稳健、更长期的解决方案:如果我们使用图像指纹来对抗疫情会怎样?
你看,每张图像都有指纹。就像指纹可以识别一个人一样,它也可以识别图像。
这导致了三阶段算法的实现:
对我们的一组不适当图像进行指纹识别,并将图像指纹存储在数据库中。
当用户上传新的个人资料图片时,我们将其与图像指纹数据库进行比较。如果上传的指纹与任何不适当图像的指纹匹配,我们会阻止用户将图像设置为其个人资料图片。
当图像版主标记新的色情图像时,它们也会被指纹识别并存储在我们的数据库中,从而创建一个不断发展的数据库,可用于防止无效上传。
我们的流程虽然并不完美,但确实有效。缓慢但肯定的是,疫情的爆发速度有所放缓。它从未完全停止 - 但通过使用这种算法,我们成功地减少了不当上传的数量超过80% .
我们还设法让投资者满意。他们继续为我们提供资金——直到经济衰退来袭。然后我们都失业了。
回想起来,我忍不住笑了。我的工作没有持续多久。这家公司并没有持续多久。甚至一些投资者也感到焦躁不安。
但有一件事did 存活。图像指纹算法。多年后,我想与大家分享这个算法的基础知识,希望大家能在自己的项目中使用它。
但最大的问题是,我们如何创建这个图像指纹?
请仔细阅读,找出答案。
我们会做什么?
我们将利用图像指纹来执行近似重复的图像检测。这种技术通常称为“感知图像哈希”或简称为“图像哈希”。
什么是图像指纹/哈希?
图像哈希是检查图像内容,然后根据这些内容构建唯一标识图像的值的过程。
例如,看看这篇文章顶部的图片。给定输入图像,我们将应用哈希函数并根据图像的视觉外观计算“图像哈希”。 “相似”的图像也应该具有“相似”的哈希值。使用图像哈希算法可以更轻松地执行近乎重复的图像检测。
特别是,我们将使用“差异哈希”或简单的 dHash 算法来计算我们的图像指纹。简单来说,dHash 算法着眼于相邻像素值之间的差异。然后,根据这些差异创建哈希值。
为什么不能使用md5、sha-1等?
不幸的是,我们无法在实现中使用加密哈希算法。由于加密哈希算法的性质,输入文件中非常微小的变化将导致显着不同的哈希值。在图像指纹识别的情况下,我们实际上想要我们的相似的输入 具有相似的输出哈希值 以及。
图像指纹可以用在哪里?
就像我上面的示例一样,您可以使用图像指纹来维护不适当图像的数据库,并在用户尝试上传此类图像时发出警报。
您可以构建一个反向图像搜索引擎,例如锡眼 跟踪图像及其出现的相关网页。
您甚至可以使用图像指纹来帮助管理您自己的个人照片集。想象一下,您的硬盘驱动器中充满了照片库的部分备份,但需要一种方法来修剪部分备份并仅保留图像的唯一副本 - 图像指纹识别也可以提供帮助。
简而言之,您可以在几乎任何需要检测图像的近似重复副本的设置中使用图像指纹/散列。
我们需要什么库?
为了构建我们的图像指纹识别解决方案,我们将使用三个主要的 Python 包:
太尔/枕头 以方便阅读和加载图像。
图像哈希值 ,其中包含我们的 dHash 实现。
和数值模拟 /科学Py ,这是 ImageHash 所需要的。
您可以通过执行以下命令来安装所有必需的先决条件:
$ pip install pillow == 2 .6.1 imagehash == 0 .3
第 1 步:对数据集进行指纹识别
第一步是对我们的图像数据集进行指纹识别。
在你问之前,不,我们不会像我在约会网站工作那样使用色情图片。相反,我创建了一个我们可以使用的人工数据集。
在计算机视觉研究人员中,CALTECH-101 数据集是传奇的。它包含来自 101 个不同类别的 7,500 多张图像,包括人物、摩托车和飞机。
从这大约 7,500 张图像中,我随机选择了其中的 17 张。
然后,我从这 17 张随机选择的图像中创建了N 通过随机调整图像大小+/-几个百分点来创建新图像。我们的目标是找到这些几乎重复的图像——有点像大海捞针。
想要创建一个类似的数据集来使用吗?下载CALTECH-101 数据集,抓取 17 个左右的图像,然后运行收集.py 脚本发现于回购协议 .
同样,除了宽度和高度之外,这些图像在各个方面都是相同的。由于它们没有相同的维度,我们不能依赖简单的 md5 校验和。更重要的是,图像类似内容 可能有显着不同 md5 哈希值。相反,我们可以诉诸图像哈希,其中具有相似内容的图像也将具有相似的哈希指纹。
因此,让我们开始编写代码来对数据集进行指纹识别。打开一个新文件,命名index.py
,让我们开始工作吧:
# import the necessary packages
from PIL import Image
import imagehash
import argparse
import shelve
import glob
# construct the argument parse and parse the arguments
ap = argparse . ArgumentParser ()
ap . add_argument ( "-d" , "--dataset" , required = True ,
help = "path to input dataset of images" )
ap . add_argument ( "-s" , "--shelve" , required = True ,
help = "output shelve database" )
args = vars ( ap . parse_args ())
# open the shelve database
db = shelve . open ( args [ "shelve" ], writeback = True )
我们要做的第一件事是导入我们需要的包。我们将使用Image
班级来自PIL
或者Pillow
从磁盘加载我们的图像。然后imagehash
库可用于构建感知哈希。
从那里,arg解析 用于解析命令行参数,shelve
用作驻留在磁盘上的简单键值数据库(Python 字典),并且glob
用于轻松收集图像的路径。
然后我们解析命令行参数。首先,--dataset
是我们图像输入目录的路径。第二,--shelve
是我们的输出路径shelve
数据库。
接下来我们打开我们的shelve
用于写入的数据库。这db
将存储我们的图像哈希值。接下来将详细介绍:
# loop over the image dataset
for imagePath in glob . glob ( args [ "dataset" ] + "/*.jpg" ):
# load the image and compute the difference hash
image = Image . open ( imagePath )
h = str ( imagehash . dhash ( image ))
# extract the filename from the path and update the database
# using the hash as the key and the filename append to the
# list of values
filename = imagePath [ imagePath . rfind ( "/" ) + 1 :]
db [ h ] = db . get ( h , []) + [ filename ]
# close the shelf database
db . close ()
这是大部分工作发生的地方。我们开始循环图像数据集,从磁盘加载它,然后创建图像指纹。
现在,我们到达整个教程中最重要的两行代码:
filename = imagePath [ imagePath . rfind ( "/" ) + 1 :]
db [ h ] = db . get ( h , []) + [ filename ]
就像我在这篇文章前面提到的,带有相同的指纹 被认为是完全相同的 .
因此,如果我们的目标是找到几乎相同的图像,我们需要维护具有相同指纹值的图像列表。
这正是这些线条的作用。
前者提取图像的文件名。然后后者维护具有相同图像哈希的文件名列表。
要从数据集中提取图像指纹并构建哈希数据库,请发出以下命令:
$ python index.py --dataset images --shelve db.shelve
该脚本将运行几秒钟,完成后,您将拥有一个名为db.shelve
包含图像指纹和文件名的键值对。
几年前我在约会初创公司工作时也使用过同样的基本算法。我们获取了不适当图像的数据集,为每个图像构建了图像指纹,然后将它们存储在我们的数据库中。当新图像到达时,我只需计算图像的哈希值并检查数据库以查看上传是否已被标记为无效内容。
在下一步中,我将向您展示如何执行实际搜索以确定数据库中是否已存在具有相同哈希值的图像。
第 2 步:搜索数据集
现在我们已经建立了图像指纹数据库,是时候了搜索 我们的数据集。
打开一个新文件,命名search.py
,我们将得到编码:
# import the necessary packages
from PIL import Image
import imagehash
import argparse
import shelve
# construct the argument parse and parse the arguments
ap = argparse . ArgumentParser ()
ap . add_argument ( "-d" , "--dataset" , required = True ,
help = "path to dataset of images" )
ap . add_argument ( "-s" , "--shelve" , required = True ,
help = "output shelve database" )
ap . add_argument ( "-q" , "--query" , required = True ,
help = "path to the query image" )
args = vars ( ap . parse_args ())
我们将再次导入相关包。然后我们解析命令行参数。我们需要三个开关,–dataset
,这是我们原始图像数据集的路径,–shelve
,我们的路径shelve
键值对数据库驻留,并且–query
,我们的查询/上传图像的路径。我们的目标是获取查询图像并确定它是否已存在于我们的数据库中。
现在,让我们编写代码来执行实际的搜索:
# open the shelve database
db = shelve . open ( args [ "shelve" ])
# load the query image, compute the difference image hash, and
# and grab the images from the database that have the same hash
# value
query = Image . open ( args [ "query" ])
h = str ( imagehash . dhash ( query ))
filenames = db [ h ]
print "Found %d images" % ( len ( filenames ))
# loop over the images
for filename in filenames :
image = Image . open ( args [ "dataset" ] + "/" + filename )
image . show ()
# close the shelve database
db . close ()
我们首先打开数据库,然后从磁盘加载图像,计算图像指纹,并找到具有相同指纹值的所有图像。
如果存在具有相同哈希值的图像,我们将循环这些图像并将它们显示到屏幕上。
使用此代码,我们将能够仅使用指纹值来确定数据库中是否已存在图像。
结果
正如我在本文前面提到的,我从 CALTECH-101 数据集中获取了约 7,500 张原始图像,随机选择了其中 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
结果如下:
我们再次将输入图像放在左边 。我们的图像指纹识别算法能够找到具有相同指纹的三张相同图像,如屏幕上所示正确的 .
最后一个例子:
$ python search.py --dataset images --shelve db.shelve --query images/5134e0c2-34d3-40b6-9473-98de8be16c67.jpg
这次我们的输入图像是一辆摩托车左边 。我们拍摄了这张摩托车图像,计算了它的图像指纹,然后在我们的指纹数据库中查找它。正如我们在正确的 ,我们能够确定数据库中还有其他三个图像具有相同的指纹。
改进我们的算法
有很多方法可以改进我们的算法,但最关键的方法是考虑哈希值相似的 , 但不是完全相同的 .
例如,本文中的图像仅调整了几个百分点(放大或缩小)。如果图像大小调整较大,或者纵横比发生变化,则哈希值将不相同。
然而,图像仍然是相似的 .
为了找到相似但不相同的图像,我们需要探索汉明距离 。汉明距离可用于计算哈希中的位数不同的 。因此,哈希值仅具有 1 位差异的两个图像比具有 10 位差异的图像更加相似。
然而,我们随后遇到了第二个问题——算法的可扩展性。
考虑一下:我们收到一个输入图像,并被指示在我们的数据库中查找所有相似的图像。然后我们必须计算输入图像和数据库中的每一个图像 .
随着数据库大小的增加,比较所有哈希值所需的时间也会增加。最终,我们的哈希数据库将达到这种线性比较不切实际的大小。
解决方案虽然超出了本文的范围,但可以利用K-d树 和副总裁树 将搜索问题的复杂度从线性降低到次线性。
概括
在这篇博文中,我们学习了如何构建和利用图像哈希来执行近似重复的图像检测。这些图像哈希是使用图像的视觉内容构建的。
就像指纹可以识别一个人一样,图像哈希也可以唯一地识别图像。
然后,利用我们对图像指纹识别的知识,我们构建了一个系统,只使用图像哈希来查找和识别具有相似内容的图像。
然后,我们演示了如何使用该图像哈希来快速查找具有几乎重复内容的图像。
哦,一定要从以下位置获取代码回购协议 .
在一个周末学习计算机视觉: 如果您喜欢这篇文章并且想了解有关计算机视觉、图像处理和构建图像搜索引擎的更多信息,请访问我的博客:PyImageSearch.com .
干杯!