这篇文章写作于2016年12月，今天整理博客才发现它一直静静地躺在我的草稿箱里。第一次了解汉明距离好像是在数电课上，老师在讲编码的原理？记不太清了。后来做毕设时，老师希望我在我的设计中添加一个判断走势图是否相近似的小程序。

###汉明距离
用于编码，简单来说，判断两个序列是否相似，则判断是否有不同的位数。举例：

A = [0, 0, 1, 0]
B = [0, 1, 1, 0]

则AB有一位不同，汉明距离为1。
又比如：

A = [3,1,4,1,5,9]
B = [2,7,1,8,2,8]

很好，他们完全不一样，汉明距离为6。

算法大概过程

1. 缩小图片尺寸，假如设成8*8，那么最后得到64位字符串
2. 简化色彩，也就是把图像变灰
3. 计算平均值
4. 比较灰度，与平均值进行比较。大于等于平均值记为1；小于平均值记为0。
5. 比较哈希值（也就是汉明距离）

在实际实施算法时，有三种方法。

三种哈希算法

判断图像近似的哈希算法共有三种：A/D和P
A 指的是平均：average
D 指的是差异：diff
P 是指感知：perceptual
最推荐的是D也就是差异哈希，A仅计算平均值，误差很大。P虽然更精确但是计算速度过慢。D比较中庸。

计算灰度值的方法

R是red，G是green，B=blue，分别代表rgb图像中的三原色

1. 浮点算法：R0.3+G0.59+B*0.11
2. 整数方法：(R30+G59+B*11) /100
3. 移位：(R76+G151+B*28) >>8
4. 平均值方法:(R+G+B)/3
5. 仅取原谅方法：G

这里就贴代码好了。

平均哈希（A）

from skimage import transform
import cv2
#aHash方法计算图片的指纹数据

img=cv2.imread('/Users/myname/Desktop/test/d.jpg')#读入图片
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)

差异哈希（D）

基于渐变实现的差异算法，速度快。

1. 缩小图片至8行9列，98，为什么是98？因为在第三步要用
2. 转灰度图
3. 计算差异值：每行相邻像素之间计算差值，这样就变成（9-1）*8=64
4. 获取01值。

from skimage import transform,data
import matplotlib.pyplot as plt
from skimage import io
import cv2
img=cv2.imread('/Users/myname/Desktop/test/d.jpg')#读入图片
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)

感知哈希（P）

对图像生成一个字符串代表他的“指纹”。通过比对“指纹”来比较图像的相似性。

1. 缩小时建议32*32，方便DCT计算
2. 转灰度图
3. 计算DCT
4. 缩小DCT，保留左上角8*8的像素。
5. 计算平均值
6. 判断各点，大于等于平均值为1，小于为0
7. 得到64个信息位

import cv2
from skimage import transform
import numpy as np
#利用phash计算图像指纹
img=cv2.imread('/Users/lixuefei/Desktop/test/d.jpg')#读入图片

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)