写在前面:这篇文章摘自Adrian Rosebrock的一篇技术博客,这里只做简单的翻译总结。如果想直接看原文的话,可以点击以下链接查看:Image hashing with OpenCV and Python

Image hashing 或者 perceptual hashing 的过程包括:

  1. 检测一张图像的内容
  2. 根据输入图像的内容,为它创建一个特殊的hash值

或许最出名的Image hashing 工具/服务是TinEye,它是一个逆向的图像搜索引擎。

使用TinEye, 用户可以:

  1. 上传一张图片
  2. TinEye会告诉用户网上这张图片的出处

在这节的开头,你可以看到一个可视化的perceptual hashing/image hashing的例子。

对于一张给定的输入图像,我们的算法会根据图像的视觉表现来计算图片的hash值。同时外观相似的图像,也应该有尽可能相似的hash值。(这里相似是指hash值之间的Hamming距离)

通过使用image hashing 算法,我们可以在一定的时间内找到近似的图像。其中最差的情况是,我们需要遍历整个数据结构,时间复杂度是O(lg n)。

这里做个提醒,通过这篇文章我们会:

  1. 讨论image hashing/perceptual hashing(和为什么传统的hash不奏效)
  2. 实现image hashing, 特别是difference hashing(dHash)
  3. 使用image hashing来解决现实世界中的问题

Step #1: 将输入图像转化为灰度图

我们image hashing算法的第一步是将输入的图像转化为灰度图,同时舍弃所有的颜色信息。

舍弃颜色信息可以让我们:

  1. 对图像进行hash的过程变得更快,因为我们只需要检测一个通道
  2. 匹配那些相同但是颜色空间稍有出入的图像(因为颜色信息已经被我们去除了)

如果无论如何你都对颜色特别感兴趣,你可以将image hashing 算法分别运用在每个通道上,然后最后将结果结合起来。(尽管这会导致三倍大的hash)

Step #2: 修改原始图像的大小

由于我们的输入图像已经被转换成灰度图了,我们需要忽略横纵比,将它压缩到9×8的像素。对于大多数的图像和数据集来说,修改原始图片大小的步骤是这个算法最慢的一步。

然而,现在的你可能有两个问题:

  1. 我们在修改原始图像大小的时候为什么要忽略横纵比?
  2. 为什么是9×8的像素——这似乎是一个很奇怪的大小?

首先回答第一个问题:

我们将图像压缩到9×8的大小同时忽略横纵比,是为了确保image hash的结果可以匹配相似的图像而不管它们初始的空间维度。

第二个问题需要更多的解释,我们会在下一步进行解答。

Step #3: 计算图片之间的差异

我们最后的目标是计算一个64-bit的hash——因为8×8=64,十分接近我们目标。

因此,为什么要将图像的大小修改为9×8呢?

请牢记我们需要实现算法的名字:difference hash。Difference hash算法通过计算相邻像素的差异而生效。

如果我们使用一张每行有9个像素的图作为输入图像, 然后计算相邻列的像素,我们最后会得到8个不同结果。8行就会产生64个不同的结果,而这个结果也是我们希望编程的64位的hash.

事实上,我们并不一定要计算差异——我们可以使用更好的方法来测试。

如果你对这点仍有疑惑,不用担心, 一旦我们开始看一些代码之后,相信一切都会变得清晰起来。

Step #4: 建立hash

最后一步是分配bit值按后建立结果hash。为了实现这个目标,我们使用一个简单的二分类测试。

给定一张差异图像D,设其对应的像素为P,我们使用下面的测试:P[X] > P[X + 1] = 1 else 0

在这个例子中,我们测试左边的像素是不是比右边的像素更亮。如果左边像素更亮的话,我们就将输出值设为1。否则,如果左边的像素更暗的话,我们就将输出值设为0.

输出的图像如下图所示。

使用Difference hash的好处

使用difference hash 有很多好处,主要包含以下几点:

  1. 如果我们输入图像的横纵比改变的话,我们的image hash也不会改变
  2. 调整亮度或者对比度:1)不会改变我们的hash值 2)或者只是有轻微改变,以确保hash值彼此尽可能贴近
  3. Difference hash非常快

以下是代码部分:

1
2
3
4
5
6
7
# import the necessary packages
from imutils import paths
import argparse
import time
import sys
import cv2
import os
1
2
3
4
5
6
7
8
9
10
# define the difference hash function 
def dhash(image, hashSize=8):
# resize the input image, adding a single column (width) so we
# can compute the horizontal gradient
resized = cv2.resize(image, (hashSize + 1, hashSize))
# compute the (relative) horizontal gradient between adjacent
# column pixels
diff = resized[:, 1:] > resized[:, :-1]
# convert the difference image to a hash
return sum([2 ** i for (i, v) in enumerate(diff.flatten()) if v])
1
2
3
4
5
6
7
# construct the argument parse and parse the arguments
ap = argparse.ArgumentParser()
ap.add_argument("-a", "--haystack", required=True,
help="dataset of images to search through (i.e., the haytack)")
ap.add_argument("-n", "--needles", required=True,
help="set of images we are searching for (i.e., needles)")
args = vars(ap.parse_args())
1
2
3
4
5
6
7
8
9
# grab the paths to both the haystack and needle images 
print("[INFO] computing hashes for haystack...")
haystackPaths = list(paths.list_images(args["haystack"]))
needlePaths = list(paths.list_images(args["needles"]))
# remove the `\` character from any filenames containing a space
# (assuming you're executing the code on a Unix machine)
if sys.platform != "win32":
haystackPaths = [p.replace("\\", "") for p in haystackPaths]
needlePaths = [p.replace("\\", "") for p in needlePaths]
1
2
3
4
5
6
# grab the base subdirectories for the needle paths, initialize the
# dictionary that will map the image hash to corresponding image,
# hashes, then start the timer
BASE_PATHS = set([p.split(os.path.sep)[-2] for p in needlePaths])
haystack = {}
start = time.time()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# loop over the haystack paths
for p in haystackPaths:
# load the image from disk
image = cv2.imread(p)
# if the image is None then we could not load it from disk (so
# skip it)
if image is None:
continue
# convert the image to grayscale and compute the hash
image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
imageHash = dhash(image)
# update the haystack dictionary
l = haystack.get(imageHash, [])
l.append(p)
haystack[imageHash] = l
1
2
3
4
5
# show timing for hashing haystack images, then start computing the
# hashes for needle images
print("[INFO] processed {} images in {:.2f} seconds".format(
len(haystack), time.time() - start))
print("[INFO] computing hashes for needles...")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# loop over the needle paths
for p in needlePaths:
# load the image from disk
image = cv2.imread(p)
# if the image is None then we could not load it from disk (so
# skip it)
if image is None:
continue
# convert the image to grayscale and compute the hash
image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
imageHash = dhash(image)
# grab all image paths that match the hash
matchedPaths = haystack.get(imageHash, [])
# loop over all matched paths
for matchedPath in matchedPaths:
# extract the subdirectory from the image path
b = p.split(os.path.sep)[-2]
# if the subdirectory exists in the base path for the needle
# images, remove it
if b in BASE_PATHS:
BASE_PATHS.remove(b)
1
2
3
4
5
# display directories to check
print("[INFO] check the following directories...")
# loop over each subdirectory and display it
for b in BASE_PATHS:
print("[INFO] {}".format(b))