背景
图片相似度计算和相似图片搜索，是图片识别领域两个常见的应用场景。例如搜索相似商品，和相似的图片，在百度、淘宝中都有应用。在某些业务中，也存在对图片相似度的计算和判断。因此，在这里简单介绍一下相关算法。
一 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 transform import cv2 #aHash方法计算图片的指纹数据 img=cv2.imread('/Users/develop/imageanalysis/RPC框架.png')#读入图片 length = 8 height = 8 sum = 0.0 k = 0 grey = [] # 修改图像大小 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 average = 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,data import matplotlib.pyplot as plt from skimage import io import cv2 img=cv2.imread('/Users/develop/imageanalysis/RPC框架.png')#读入图片 length = 9 height = 8 sum = 0.0 k = 0 grey = [] 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 cv2 from skimage import transform import numpy as np #利用phash计算图像指纹 img=cv2.imread('/Users/develop/imageanalysis/RPC框架.png')#读入图片 length = 32 s_length = 8 dst=transform.resize(img, (length, length)) #print(type(dst)) #all 代表全图，建议32*32 matrix_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 = 0 for 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 = 0 for 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,[]
