相似图片搜索的原理

相似图片的原理是什么？计算机怎么知道两张图片相似呢？

这其中的关键技术叫做"感知哈希算法", 它的作用是对每张图片生成一个指纹(fingerprint)字符串，然后比较不同图片的fingerprint。结果越接近，就说明度图片越相似。

¶实现

¶缩小尺寸

将图片缩小到8×8的尺寸，总共64个像素。这一步的作用是取出图片的细节，只保留结构、明暗等基本信息，摒弃不同尺寸、比例地带来的图片差异。

¶简化色彩

将缩小后的图片，转为64级灰度，也就是说，所有像素点总共只有64中颜色。

¶计算平均值

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

¶比较像素的灰度值

将每个像素的灰度，与平均值进行比较，大于或者等于平均值，记为1，小于平均值，记为0.

¶计算哈希值

将上一步的比较结果，组合在一起，构成一个64位的像素，这就是这张图片的fingerprint。组合的次序并不重要，只要保证所有的图片都采用相同次序就行了。

得到fingerprint之后，就可以对比不同的，看看64位中有多少位是不一样的。在理论上，这等同于计算汉明距离。如果不相同的数据不超过5，就说明两张图片很相似；如果大于10，就说明这是两张不同的图片。

这种算法的优点是简单快速，不收图片大小缩放的影响，缺点是图片的内容不能变更。如果在图片上加上几个字，它就认不出来了。所以，它的最佳用途是根据缩略图，找出原图。

实际应用中，往往采用更强大的pHash算法和SIFT算法，它们能够识别图片的变形。只要变形程度不超过25%，它们就能匹配原图。这些算法虽然更复杂，但是原理与上面的简便算法是一样的，就是先将图片转化成Hash字符串，然后再进行比较。

¶Python代码

#!/usr/bin/python

import glob
import os
import sys

from PIL import Image

EXTS = 'jpg', 'jpeg', 'JPG', 'JPEG', 'gif', 'GIF', 'png', 'PNG'

# 第一个参数是基准图片，第二个参数是用来比较的其他图片所在的目录，返回结果是两张图片之间不相同的数据位数量（汉明距离）

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

def hamming(h1, h2):
    h, d = 0, h1 ^ h2
    while d:
        h += 1
        d &= d - 1
    return h

if __name__ == '__main__':
    if len(sys.argv) <= 1 or len(sys.argv) > 3:
        print "Usage: %s image.jpg [dir]" % sys.argv[0]
    else:
        im, wd = sys.argv[1], '.' if len(sys.argv) < 3 else sys.argv[2]
        h = avhash(im)

        os.chdir(wd)
        images = []
        for ext in EXTS:
            images.extend(glob.glob('*.%s' % ext))

        seq = []
        prog = int(len(images) > 50 and sys.stdout.isatty())
        for f in images:
            seq.append((f, hamming(avhash(f), h)))
            if prog:
                perc = 100. * prog / len(images)
                x = int(2 * perc / 5)
                print '\rCalculating... [' + '#' * x + ' ' * (40 - x) + ']',
                print '%.2f%%' % perc, '(%d/%d)' % (prog, len(images)),
                sys.stdout.flush()
                prog += 1

        if prog: print
        for f, ham in sorted(seq, key=lambda i: i[1]):
            print "%d\t%s" % (ham, f)