背景
图片相似度计算和相似图片搜索，是图片识别领域两个常见的应用场景。例如搜索相似商品，和相似的图片，在百度、淘宝中都有应用。在某些业务中，也存在对图片相似度的计算和判断。因此，在这里简单介绍一下相关算法。
一 Hash 算法
Hash 算法作为大多图片搜索引擎的核心算法，其准确率和效率均很高，本板块将介绍 Hash 的三种核心算法：aHash、pHash、dHash。
1.1 图像均值哈希算法-aHash
基于均值哈希的算法称为均值哈希算法（Average Hash Algorithm，AHA），此算法是基于比较灰度图每个像素与所有像素点的平均值来实现的，最适用于缩略图，放大图搜索。
步骤：
1.缩放图片：为了保留结构去掉细节，去除大小、横纵比的差异，把图片统一缩放到 8*8，共 64 个像素的图片。
2.转化为灰度图：把缩放后的图片转化为 256 阶的灰度图。
3.计算平均值： 计算进行灰度处理后图片的所有像素点的平均值。
4.比较像素灰度值：遍历灰度图片每一个像素，如果大于平均值记录为 1，否则为 0.
5.得到信息指纹：组合 64 个 bit 位，顺序随意保持一致性即可。
6.对比指纹：计算两幅图片的指纹，计算汉明距离（从一个指纹到另一个指纹需要变几次），汉明距离越大则说明图片越不一致，反之，汉明距离越小则说明图片越相似，当距离为 0 时，说明完全相同。（通常认为距离>10 就是两张完全不同的图片）
1.2 图像感知哈希算法-pHash
平均哈希算法过于严格，不够精确，更适合搜索缩略图，为了获得更精确的结果可以选择感知哈希算法，它采用的是 DCT（离散余弦变换）来降低频率的方法
感知哈希，全称是 Perceptual Hash，是基于像素点级别的一种散列映射方式，基于认知心理学的信息加工理论为基础，提取图像中的各种特征用于生成独特但不是唯一的指纹，即一串简短且可以表示图像可被人类感知的特征内容的感知数字序列，且这些指纹具有可比性。
步骤：
1.缩小图片：32 * 32 是一个较好的大小，这样方便 DCT 计算
2.转化为灰度图：把缩放后的图片转化为 256 阶的灰度图。（具体算法见平均哈希算法步骤）
3.计算 DCT:DCT 把图片分离成分率的集合
4.缩小 DCT：DCT 是 32*32，保留左上角的 8*8，这些代表的图片的最低频率
5.计算平均值：计算缩小 DCT 后的所有像素点的平均值。
6.进一步减小 DCT：大于平均值记录为 1，反之记录为 0.
7.得到信息指纹：组合 64 个信息位，顺序随意保持一致性即可。
8.对比指纹：计算两幅图片的指纹，计算汉明距离（从一个指纹到另一个指纹需要变几次），汉明距离越大则说明图片越不一致，反之，汉明距离越小则说明图片越相似，当距离为 0 时，说明完全相同。（通常认为距离>10 就是两张完全不同的图片）
1.3 图像差异哈希算法-dHash
图像差异哈希，全称是 Difference Hash，是基于像素点级别的一种散列映射方式。图像差异哈希是通过逐像素比对相邻像素像素值的差异，即逐像素得到当前像素与右邻像素的差值，得到一个图像差异矩阵，通过该矩阵映射生成哈希值。这个逐像素得到的图像差异矩阵的比原像素矩阵少了一列，即宽度比原像素矩阵少了 1，高度不变。
相比 pHash，dHash 的速度要快的多，相比 aHash，dHash 在效率几乎相同的情况下的效果要更好，它是基于渐变实现的。
步骤：
1.缩小图片：收缩到 9*8 的大小，一遍它有 72 的像素点
2.转化为灰度图：把缩放后的图片转化为 256 阶的灰度图。（具体算法见平均哈希算法步骤）
3.计算差异值，获得最后哈希值（与 aHash 主要区别处）。dHash 算法工作在相邻像素之间。比较每行左右两个像素，如果左边的像素比右边的更亮（左边像素值大于右边像素值），则记录为 1，否则为 0。因为每行有 9 个像素，左右两个依次比较可得出 8 个值，所以 8 行像素共可以得出 64 个值，因此此时哈希值为长度是 64 的 0-1 序列。
4.图片配对，计算汉明距离。
汉明距离
汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：
1011101 与 1001001 之间的汉明距离是 2。
2143896 与 2233796 之间的汉明距离是 3。
"toned" 与 "roses" 之间的汉明距离是 3。
二 算法比较
图像均值哈希本质上是对颜色的比较,图像感知哈希由于做了 DCT 操作，本质上是对频率的比较，图像差异哈希本质上是基于渐变的感知哈希算法。
下面是对比的素材：
下面是对比的结果：
三 环境搭建与算法实现
3.1 三种 hash 算法的实现与环境搭建
语言：python， 版本：python2.7 / python3
module 依赖：scikit-image ， opencv-python
依赖安装：
sudo pip3 install --upgrade setuptoolssudo pip3 install scikit-image -i http://pypi.douban.com/simple/ --trusted-host pypi.douban.com//后面为镜像源加速pip install --default-timeout=1000 opencv-python
//使用清华源安装pip3 install opencv-python -i https://pypi.tuna.tsinghua.edu.cn/simple
复制代码
3.2 aHash、dHash、pHash 的实现示例
3.2.1 aHash
# -*- coding: utf-8 -*-from skimage import transformimport cv2#aHash方法计算图片的指纹数据
img=cv2.imread('/Users/develop/imageanalysis/RPC框架.png')#读入图片length = 8height = 8sum = 0.0k = 0grey = []# 修改图像大小dst=transform.resize(img, (length, height))
for i in range(length): for j in range(height): (b,g,r) = dst[i,j] # 计算灰度值 grey.append(r*0.3+g*0.59+b*0.11)#浮点灰度值计算 sum+=grey[k] k=k+1average = sum/(length*height)#算出平均的灰度数据fingerprint = []
for i in range(length*height): if grey[i] > average: fingerprint.append(1)#如果灰度数据大于平均值，填入元素1，否则填入元素0 else: fingerprint.append(0)
print(fingerprint)
复制代码
3.2.2 dHash
# -*- coding: utf-8 -*-from skimage import transform,dataimport matplotlib.pyplot as pltfrom skimage import ioimport cv2img=cv2.imread('/Users/develop/imageanalysis/RPC框架.png')#读入图片length = 9height = 8sum = 0.0k = 0grey = []dst=transform.resize(img, (length, height))#灰度图转化for i in range(length): for j in range(height): (b,g,r) = dst[i,j] grey.append(r*0.3+g*0.59+b*0.11)#浮点灰度值计算 sum+=grey[k] k=k+1# 获取每行的差值，为64位differ = []for i in range(length-1):#i 8 for j in range(height):#j 8 differ.append(grey[j*8+i+1]-grey[j*8+i])#获取01值fingerprint = []for i in range((length-1)*height):#8*8 if differ[i] > 0: fingerprint.append(1) else: fingerprint.append(0)
print(fingerprint)
复制代码
3.2.3 pHash
# -*- coding: utf-8 -*-import cv2from skimage import transformimport numpy as np#利用phash计算图像指纹img=cv2.imread('/Users/develop/imageanalysis/RPC框架.png')#读入图片
length = 32s_length = 8
dst=transform.resize(img, (length, length))#print(type(dst))
#all 代表全图，建议32*32matrix_all_grey = [[0 for i in range(length)] for i in range(length)]#small 代表最低频率，8*8大小matrix_small_grey = [[0 for i in range(s_length)] for i in range(s_length)]
# 灰度图转化k = 0for i in range(length): for j in range(length): (b,g,r) = dst[i,j] matrix_all_grey[i][j] = ( b + g + r )/3# 缩小fft_matrix_grey = np.fft.fft(matrix_all_grey)for i in range(s_length): for j in range(s_length): matrix_small_grey[i][j] = fft_matrix_grey[i][j]# 计算平均sum_pixel = 0for i in range(s_length): for j in range(s_length): sum_pixel += matrix_small_grey[i][j]average = sum_pixel / (s_length*s_length)
bite = []
#赋予01值for i in range(s_length): for j in range(s_length): if matrix_small_grey[i][j] > average : bite.append(1) else: bite.append(0)print(bite)
复制代码
3.3 高效对比检索
通过上面的几种 hash 算法，我们可以得到一系列图片的 hash 值。接下来，如果需要对比去除重复图片，或者要检索，怎样才能加快查询速度呢?
暴力的遍历显然是不太靠谱的，少量图片还好，当达到百万、千万、甚至亿级十亿级的图片数量时，O(n)的复杂度显然无法保障查询速度。
可以考虑的是一种内存换速度的方式，64 位的的 hash 值，分为八组，每组八位。建立八个 dict，每个 dict 代表一组，以每组的值作为 key，value 是一个 list，存放 key 相同的 hash 值。查找的时候，把 hash 值分成八个，分别在八个 map 里边查找，如果有 key 相同的，取出 key 相同的所有 hash 值进行遍历。
示例代码：
split_count = 8 # 每个64位的phash值分为八段，每段8位
def split(key, split_count): pre_length = 64 / split_count return [key[i * pre_length: (i + 1) * pre_length] for i in range(split_count)]
class ImageManager(object): def __init__(self): self.phash = pHash() # pHash类 self.phash_cache = [defaultdict(list) for i in range(split_count)] # self.init_phash_map()
def init_phash_map(self): #把所有的phash存在sqlite里边，这边取出所有的Image for image in Image.select(): self.add_to_image_cache(image)
def add_to_image_cache(self, image): # 将hash值分割为8段 key_split = split(bin(int(image.phash))[2:].rjust(64, '0'), split_count) for index, k in enumerate(key_split): self.phash_cache[index][k].append(image)
def has_same(self, ori_image): phash = ori_image.phash key_split = split(bin(int(phash))[2:].rjust(64, '0'), split_count) result = set() for index, k in enumerate(key_split): if k in self.phash_cache[index]: for image in self.phash_cache[index][k]: distance = self.distance(int(phash), int(image.phash)) if distance < 5 and ori_image.key != image.key: result.add(image) if result: return True,list(result) return False,[]
复制代码
参考文章
相似图片搜索算法介绍
图像处理 图像相似算法aHash、dHash、pHash解析与对比
最近邻搜索
较大规模图片 使用phash去重
评论