图像搜索引擎搭建：利用VP-Tree实现以图搜图

用一张图像，从图像数据库中快速找到相似或者相同的图像，这就是以图搜图。

1. VP-Tree结构

1.1 概念

VP-Tree（Vantage Point Tree）在1991年被Uhlmann作者提出，它是一种基于距离的度量空间上的索引结构，是一颗度量二叉树。其基本思想是将 二分查找 用于只有距离信息的多维度量空间中。也就是采用特征空间的目标点集的点与 制高点（Vantage Point） 之间的距离信息对特征空间进行划分。

VP-Tree构造时间复杂度：O(nlogn)VP-Tree搜索在理想情况下的复杂度：O(logn)

1.2 数据结构

假设有一个数据集S={S₁，S₂，… ，S_n-1，S_n}，度量空间距离函数D(S_i，S_j)：

若|S|=0，构造空树，返回；若|S|不为0，从S中随机选取一个对象S_c，把这个S_c看作制高点（Vantage Point），设m是S中所有对象与S_c的距离中值，小于m的数据点分给左子树，大于m的数据点分给右子树： S_left={S_i|D(S_i, S_c) ≤ m, S_i∈S，S_i ≠ S_c } S_right={S_j|D(S_j, S_c) ≥ m, S_j∈S}递归构造VP-Tree（即递归地建立左子树和右子树）

1.3搜索算法

对于一个查询数据对象Q和距离范围r（近邻查询），A_c为当前制高点，距离中值m，搜索算法为：

当D(Q, A_c) ≤ r, 则返回A_c当D(Q, A_c) + r ≥ m，递归地搜索右子树 S_right（球外区域）当D(Q, A_c) - r ≤ m，递归地搜索左子树 S_left（球内区域）

2.图像哈希算法

在判断图片是不是同一张图片，最简单的方法是用加密哈希来进行判断是否相同，如：MD5, SHA-1等算法。但这存在很大的缺点，如果同一张图像被缩放或者颜色变了一点，产生MD5值是完全不同的，这就无法判断相似图片。比较好的解决方案是采用感知哈希算法，它包括：aHash、pHash、dHash。 他们的区别：

平均哈希aHash：速度比较快，但不精确感知哈希pHash：精确度比较高，但速度较差。差异哈希dHash：精确度较高，且速度也快

差异值哈希dHash算法步骤：

缩小图像：将图像调整为固定尺寸N + 1 xN。通常N = 8，即9X8大小，9作为行数，方便计算图像中相邻像素之间的差异（“差异哈希”）转化为灰度图：把缩放后的图片转化为256阶的灰度图。因为彩色的图片是由 RGB 三原色构成，每个像素点是一个由这三个颜色组成的一个 list 。而 RGB 三个颜色中每个颜色值都是用 8 个比特来表示，大小范围是 0 ～ 255(2⁸ - 1)，就一共有 256 * 256 * 256 种颜色。并且作为一个像素类似于这样的数值：[253 255 255] 是不利于简单比较的，肉眼看着类似的颜色，但是它的三个颜色分布可能相差很多。所以将它灰度化，用 256 个不同的灰色表示现有的图片。由于现在用一种灰色表示三种颜色，原来每个像素是一个 list 现在就降维成一个数值，这样数值的大小还是比较容易比较的。计算差异值：每行有9个像素，每列有8个像素。然后，我们可以计算相邻列像素之间的差异，得出8个差异。每行9个像素之间产生了8个不同的差异，得到64个值。生成哈希值：对差异值进行处理，若为正数或0，则记得为1；若为负数，记为0。将64个结果结合在一起就得到一个哈希值（每张图像的64个值组合顺序要一致），这就是图像的“指纹”。

3.汉明距离（Hamming Distance）

汉明距离表示两个（相同长度）字对应位不同的数量，我们以d（x,y）表示两个字x,y之间的汉明距离。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。 例如： A为 10101001 B为 10110001 可以看出A和B有两位的不同，那么汉明距离就是2

4.图像搜索引擎

假设有3,000,000张图像的图像库。这3,000,000张图像中的每张图像都计算了图像哈希值。假设每次汉明距离比较花费0.00001秒，总共有3,000,000张图像，它也将用30秒来完成搜索。这对于任何搜索引擎都是太慢了。图像引擎需要查询速度很快的，这就用到了上面提到的VP-Tree数据结构。

图像搜索引擎主要有两部分组成：索引和查询。

索引： 查询：

这里图像库有3万9千多张图。 构建VP-Tree代码：

from imutils import paths import pickle import vptree import numpy as np import cv2 # 差异哈希函数 def dhash(image, hashSize=8): # 转为灰度图 gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY) # 缩放 resizeImg = cv2.resize(gray, (hashSize + 1, hashSize)) # 计算差异值 diff_value = resizeImg[:, 1:] > resizeImg[:, :-1] return sum([2 ** i for (i, v) in enumerate(diff_value.flatten()) if v]) def convert_hash(hash_value): # 对差异值处理，返回64位浮点数值 return int(np.array(hash_value, dtype="float64")) def hamming(a_dist, b_dist): # 计算汉明距离 return bin(int(a_dist) ^ int(b_dist)).count("1") hashes = {} # 换成自己的图像库文件路径 path = "E:\\yu\\work\\python_work\\input\\image_data" imagePaths = list(paths.list_images(path)) for (i, imagePath) in enumerate(imagePaths): print("加载处理图像： {}/{}".format(i + 1, len(imagePaths))) image = cv2.imread(imagePath) # 计算 hash_value = dhash(image) hash_value = convert_hash(hash_value) # 添加进hashes字典 h = hashes.get(hash_value, []) h.append(imagePath) hashes[hash_value] = h # 建vp树 print("构建 VP-Tree...") points = list(hashes.keys()) tree = vptree.VPTree(points, hamming) # 保存 print("保存 VP-Tree...") f = open("E:\\yu\\work\\python_work\\output\\vptree.pickle", "wb") f.write(pickle.dumps(tree)) f.close() # 保存哈希值 print("保存 hashes...") f = open("E:\\yu\\work\\python_work\\output\\hashes.pickle", "wb") f.write(pickle.dumps(hashes)) f.close()

图有点多，需要等待两分钟 搜索代码：

import pickle import time import numpy as np import cv2 # 差异哈希函数 def dhash(image, hashSize=8): # 转为灰度图 gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY) # 缩放 resizeImg = cv2.resize(gray, (hashSize + 1, hashSize)) # 计算差异值 diff_value = resizeImg[:, 1:] > resizeImg[:, :-1] return sum([2 ** i for (i, v) in enumerate(diff_value.flatten()) if v]) def convert_hash(hash_value): # 对差异值处理，返回64位浮点数值 return int(np.array(hash_value, dtype="float64")) def hamming(a, b): # compute and return the Hamming distance between the integers return bin(int(a) ^ int(b)).count("1") # 加载VP和哈希文件 tree = pickle.loads(open("E:\\yu\\work\\python_work\\output\\vptree.pickle", "rb").read()) hashes = pickle.loads(open("E:\\yu\\work\\python_work\\output\\hashes.pickle", "rb").read()) print("加载 VP-Tree and hashes...") # 待搜索图片路径 image = cv2.imread("E:\\yu\\work\\python_work\\input\\image_data\\6.jpg") if(len(image)==None): print("加载图片失败 ...") cv2.namedWindow("test_search",cv2.WINDOW_NORMAL) cv2.resizeWindow("test_search",512,384) cv2.imshow("test_search", image) # 计算哈希值 search_Hash = dhash(image) search_Hash = convert_hash(search_Hash) # 获取结果 distance = 10 print("搜索中...") start = time.time() results = tree.get_all_in_range(search_Hash, distance) results = sorted(results) # print("results:",results) end = time.time() print("消耗时间 {} s".format(end - start)) # 结果处理 for (d, h) in results: # 用哈希值获取数据集中的所有相似图像 resultPaths = hashes.get(h, []) print("检索到 {} 张, 汉明距离: {}, 哈希值: {}".format( len(resultPaths), d, h)) # 显示结果 for resultPath in resultPaths: result = cv2.imread(resultPath) cv2.namedWindow("Result", cv2.WINDOW_NORMAL) cv2.resizeWindow("Result", 512, 384) cv2.imshow("Result", result) cv2.waitKey(0)

拿张图举个例子：

测试1：

拿原图比较，运行一下搜索代码： 搜索时间在0.12s，汉明距离为零表示是两张相同的图像。

测试2：

把图亮度，饱和度调整一下：

那修改后的图再次搜索一下，结果： 可以看到，距离变为了1。

测试3：

把图再修改一下： 运行结果： 完~

Reference: https://blog.csdn.net/mandycool/article/details/8492819 https://blog.csdn.net/Leo_whj/article/details/80923166