Infi-chu:
http://www.cnblogs.com/Infi-chu/
以图搜图的使用已经非常广泛了，我现在来介绍一下简单的以图搜图的相关算法及其实践。
一、感知hash算法
感知哈希算法：
感知哈希算法（Perceptual hash algorithm）是哈希算法的一类，主要用来做相似图片的搜索工作。
图片所包含的特征被用来生成一组指纹（不过它不是唯一的）, 而这些指纹是可以进行比较的。
步骤：
1.把图片转化为字符串，这个字符串就是图片的hash值，又称指纹。
2.求两个字符串之间的相似度（汉明距离），字符串越相似，即图片越相似。二、汉明距离
汉明距离：
汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
例如：
1011101 与 1001001 之间的汉明距离是 2。
2143896 与 2233796 之间的汉明距离是 3。
“toned” 与 “roses” 之间的汉明距离是 3。三、均值hash
下面的例子是使用了像素平均值，又叫均值哈希。
优点：均值哈希较为简单。
缺点：对图像灰度的平均值特别敏感，也不具备旋转不变性。import cv2
def p_hash(path):
# Step1. 把图像缩小为8 * 8,并转化为灰度图
src = cv2.imread(path, 0)
src = cv2.resize(src, (8, 8), cv2.INTER_LINEAR)
# Step2. 计算64个像素的灰度均值
avg = sum([sum(src[i]) for i in range(8)]) / 64
# Step3. 与平均值比较，生成01字符串
string = ''
for i in range(8):
string += ''.join(map(lambda i: '0' if i < avg else '1', src[i]))
# Step4. 计算hash值
result = ''
for i in range(0, 64, 4):
result += ''.join('%x' % int(string[i: i + 4], 2))
return result
def hamming(str1, str2):
if len(str1) != len(str2):
return
count = 0
for i in range(0, len(str1)):
if str1[i] != str2[i]:
count += 1
return count
# 读取四张图片，进行测试
h1 = p_hash('1.jpg')
h2 = p_hash('2.jpg')
h3 = p_hash('3.jpg')
h4 = p_hash('4.jpg')
# 四张图片的相互对比
print('1&2 --> ',hamming(h1,h2))
print('1&3 --> ',hamming(h1,h3))
print('1&4 --> ',hamming(h1,h4))
print('2&3 --> ',hamming(h2,h3))
print('2&4 --> ',hamming(h2,h4))
print('3&4 --> ',hamming(h3,h4))
结果：
1&2 --> 1
1&3 --> 0
1&4 --> 1
2&3 --> 1
2&4 --> 1
3&4 --> 1
四、余弦感知哈希
为了提升更好的识别效果，可以使用余弦感知哈希算法。
优点：能够处理旋转图形。
缺点：只能够识别变形程度在25%以内的图片。
步骤：
1.缩小尺寸：将图像缩小到32*32，并转为灰度图。
2.计算DCT：对图像进行二维离散余弦变换。
3.缩小DCT：只保留矩阵左上角8*8区域，对这个区域求哈希均值，并生成01字符串。
4.计算hash值。
5.求汉明距离import numpy as np
import cv2
def p_hash(path):
# Step1. 把图像缩小为32 * 32,并转化为灰度图
src = cv2.imread(path, 0)
src = cv2.resize(src, (32, 32), cv2.INTER_LINEAR)
# Step2. 对图像进行余弦变换
h, w = src.shape[:2]
arr = np.zeros((h, w), np.float32)
arr[:h, :w] = src
src = cv2.dct(cv2.dct(arr)) # 离散余弦变换
src.resize(8, 8)
# Step3. 计算64个像素的灰度均值
avg = sum([sum(src[i]) for i in range(8)]) / 64
# Step4. 与平均值比较，生成01字符串
string = ''
for i in range(8):
string += ''.join(map(lambda i: '0' if i < avg else '1', src[i]))
# Step5. 计算hash值
result = ''
for i in range(0, 64, 4):
result += ''.join('%x' % int(string[i: i + 4], 2))
return result
def hamming(str1, str2):
if len(str1) != len(str2):
return
count = 0
for i in range(0, len(str1)):
if str1[i] != str2[i]:
count += 1
return count
# 读取四张图片，进行测试
h1 = p_hash('1.jpg')
h2 = p_hash('2.jpg')
h3 = p_hash('3.jpg')
h4 = p_hash('4.jpg')
# 四张图片的相互对比
print('1&2 --> ',hamming(h1,h2))
print('1&3 --> ',hamming(h1,h3))
print('1&4 --> ',hamming(h1,h4))
print('2&3 --> ',hamming(h2,h3))
print('2&4 --> ',hamming(h2,h4))
print('3&4 --> ',hamming(h3,h4))
print('1&1 --> ',hamming(h1,h1))
结果：
1&2 --> 3
1&3 --> 1
1&4 --> 6
2&3 --> 3
2&4 --> 6
3&4 --> 5
1&1 --> 0
图例：
‘1.jpg’
‘2.jpg’
‘3.jpg’
‘4.jpg’
