更新时间: 2018-01-21 18:24:04       分类: 算法


背景

检查两个图片的相似度,一个简单而快速的算法:感知哈希算法(Perceptual Hash),通过某种提取特征的方式为每个图片计算一个指纹(哈希),这样对比两个图片相似与否就变成了对比两个指纹异同的问题。

实现

Step1.缩小尺寸

将图片缩小到8*8的大小,这样做可以去除图片的细节,只保留结构和明暗等基本信息,同时摒弃不同尺寸和比例带来的图片差异。

Step2.灰度处理

把缩小后的图片转化为64级灰度图(每个像素只有64种颜色)。

Step3.计算平均值

计算所有64个像素的灰度平均值。

Step4.计算哈希

这里哈希的计算方法是:上面说的64个像素的灰度与平均值进行比较,大于或等于平均值记为1,小于记为0。

将每个像素的比较结果组合在一起成为一个64位的二进制整数,这个整数就是此图片的指纹。

Step5.对比哈希

不同图片对比的方法,就是对比它们的64位哈希中,有多少位不一样(汉明距离)。一般来说如果不同的位数不超过5,就说明两张图片很相似,如果大于10,就很可能是两张不同的图片。

代码(Python)

计算pHash:

def phash(img):
    img = img.resize((8, 8), Image.ANTIALIAS).convert('L')
    avg = reduce(lambda x, y: x + y, img.getdata()) / 64.
    return reduce(
        lambda x, (y, z): x | (z << y),
        enumerate(map(lambda i: 0 if i < avg else 1, img.getdata())),
        0
    )

计算汉明距离:

def hamming_distance(a, b):
    return bin(a^b).count('1')

计算两个图片是否相似:

def is_imgs_similar(img1,img2):
	return True if hamming_distance(phash(img1),phash(img2)) <= 5 else False

其中计算部分用到了lambda表达式和reduce,可参考此文:廖雪峰:map和reduce


评论

还没有评论