相似图片搜索

转自：http://xuhehuan.com/219.html

相似图片搜索的原理简析

2010年6月份，谷歌图片的搜索框旁边放置了一个小照相机的按钮，标志着以图搜图的全新图片检索功能开始启用，8月份，搜狗图片搜索也具备了以图搜图的功能，12月，百度正式上线图片搜索新功能——百度识图。这些图片搜索不同于以前的以关键字来搜索图片，而是使用图片本身替代了关键字来搜索类似图片，这种以图搜图方式的搜索引擎用术语来说就是“反向图片搜索引擎”(reverse image search engine)。

谷歌和搜狗在图片搜索框放置的都是小照相机，单击后会出现一个对话框，在里面输入网片的网址，或者直接上传图片，就会找出与其相似的图片。

百度识图更为直观，直接看到上传本地图片和输入图片URL地址两项。下面是著名的Lena图像：

上传谷歌后，可以得到的相似图片结果如下：

相比于传统的关键字搜索，以图搜图具有着革命性的意义，更多的相似图片搜索引擎可以看这里：以图搜图的相似图片搜索网站。

看到了技术，我们就想探究技术背后的原理，这种技术的原理是什么？计算机怎么知道两张图片相似呢？

根据Neal Krawetz博士的解释，原理非常简单易懂。我们可以用一个快速算法，就达到基本的效果。这里的关键技术叫做“感知哈希算法”（Perceptual hash algorithm），它的作用是对每张图片生成一个“指纹”（fingerprint）字符串，然后比较不同图片的指纹。结果越接近，就说明图片越相似。

下面是一个最简单的实现：

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

第二步，简化色彩。将缩小后的图片，转为64级灰度。也就是说，所有像素点总共只有64种颜色。

第三步，计算平均值。计算所有64个像素的灰度平均值。

第四步，比较像素的灰度。将每个像素的灰度，与平均值进行比较。大于或等于平均值，记为1；小于平均值，记为0。

第五步，计算哈希值。将上一步的比较结果，组合在一起，就构成了一个64位的整数，这就是这张图片的指纹。组合的次序并不重要，只要保证所有图片都采用同样次序就行了。

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

具体的代码实现，可以参见Wote用python语言写的imgHash.py。代码很短，只有53行。使用的时候，第一个参数是基准图片，第二个参数是用来比较的其他图片所在的目录，返回结果是两张图片之间不相同的数据位数量（汉明距离）。

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

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

这种方法对于寻找一模一样的图片是有效的，但并不能够去搜索“相似”的照片，也不能局部搜索，比如从一个人的单人照找到这个人与别人的合影。这些Google Images都能做到。早在2008年，Google公布了一篇图片搜索的论文（PDF版），和文本搜索的思路是一样的：对于每张图片，抽取其特征，这和文本搜索对于网页进行分词类似；对于两张图片，其相关性定义为其特征的相似度，这和文本搜索里的文本相关性也是差不多的；图片一样有image rank，文本搜索中的page rank依靠文本之间的超链接。图片之间并不存在这样的超链接，image rank主要依靠图片之间的相似性（两张图片相似，便认为它们之间存在超链接），具有更多相似图片的图片，其image rank更高一些。

Google的算法，其官方描述为：

When you upload an image to Search by Image,the algorithms analyze the content of the image and break it down into smaller pieces called “features”. These features try to capture specific,distinct characteristics of the image – like textures,colors,and shapes. Features and their geometric configuration represent the computer’s understanding of what the image looks like.

大意是说在Google眼里，图片并不是一个由像素点构成点阵，而是一些“features“，包括形状、质地和颜色块。图片之间的比较，是直接去比较图片里的线条等。