图片搜索之感知哈希算法

<wbr><wbr>TinEye是如何工作的呢？这里面也许有十分复杂的原理。不过从结果看来，它使用了一种叫做“感知哈希算法（以下简称PHA）”的东西。<br><wbr><wbr><wbr><wbr><wbr>PHA是一类比较哈希方法的统称。图片所包含的特征被用来生成一组指纹（不过它不是唯一的）,而这些指纹是可以进行比较的。<br><wbr><wbr><wbr><wbr><wbr>PHA与加密哈希方法（以下简称CHA)，如MD5、SHA1等，是不同的概念。CHA的哈希值是随机的。用来生成哈希的数据的行为就像随机种子，所以相同的数据产生相同的结果，反之亦然。读者可以如下做ruby测试：<br><wbr><wbr><wbr><wbr><wbr>require 'digest/sha2'<br><wbr><wbr><wbr><wbr><wbr>......<br><wbr><wbr><wbr><wbr><wbr>#生成加密后的散列值<br><wbr><wbr><wbr><wbr><wbr>def self.encrypt(string)<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr>return Digest::SHA256.hexdigest(string)<br><wbr><wbr><wbr><wbr><wbr>end<br><wbr><wbr><wbr><wbr><wbr>我对这方面未做深层研究，如有错误，不吝赐教。此文的重点不是CHA，恕草草带过。<br><wbr><wbr><wbr><wbr><br><wbr><wbr><wbr><wbr><wbr>如果想要深入理解下文内容的话，不妨读读我在ftp里的fourier相关文档，会有所收获。当然，不读也不会造成大的影响。（ftp具体在文末有提及）<br><br><wbr><wbr><wbr><wbr>对于图片来说，高频得到细节，低频得到轮廓。所以小图缺少细节，是低频的。我先叙述一个阮一峰先生提及的最简单PHA，在此表示感谢。大家可一睹为快。<br><br><wbr><wbr><wbr><a href="http://photo.blog.sina.com.cn/showpic.html#blogid=6b291d730100wiar&amp;url=http://s3.sinaimg.cn/orignal/6b291d73gaa9c04241bb2" target="_blank"> <img src="http://s3.sinaimg.cn/middle/6b291d73gaa9c04241bb2&amp;690" name="image_operate_19341313486995790" alt="感知哈希算法浅析" title="感知哈希算法浅析"></a><br><br><wbr><wbr><wbr><br><br><wbr><wbr><wbr>第一步，缩小尺寸。<br><br><wbr><wbr><wbr>最快速的去除高频和细节，只保留结构明暗的方法就是缩小尺寸。<br><br><wbr><wbr><wbr>将图片缩小到8x8的尺寸，总共64个像素。摒弃不同尺寸、比例带来的图片差异。<br><br><wbr><wbr><a href="http://photo.blog.sina.com.cn/showpic.html#blogid=6b291d730100wiar&amp;url=http://s16.sinaimg.cn/orignal/6b291d73gaa9c0763771f" target="_blank"> <img src="http://s16.sinaimg.cn/middle/6b291d73gaa9c0763771f&amp;690" alt="感知哈希算法浅析" title="感知哈希算法浅析" height="62" width="66"></a><wbr><br><br><wbr><wbr><wbr>第二步，简化色彩。<br><br><wbr><wbr><wbr>将缩小后的图片，转为64级灰度。也就是说，所有像素点总共只有64种颜色。<br><br><wbr><wbr><wbr>第三步，计算平均值。<br><br><wbr><wbr><wbr>计算所有64个像素的灰度平均值。<br><br><wbr><wbr><wbr>第四步，比较像素的灰度。<br><br><wbr><wbr><wbr>算法的精髓，简单、有趣，又充满深意。<br><br><wbr><wbr><wbr>将每个像素的灰度，与平均值进行比较。大于或等于平均值，记为1；小于平均值，记为0。<br><br><wbr><wbr><wbr>第五步，计算哈希值。<br><br><wbr><wbr><wbr>将上一步的比较结果，组合在一起，就构成了一个64位的整数，这就是这张图片的指纹。组合的次序并不重要，只要保证所有图片都采用同样次序就行了（例如，自左到右、自顶向下、big-endian）。<br><br><wbr><wbr><wbr><a href="http://photo.blog.sina.com.cn/showpic.html#blogid=6b291d730100wiar&amp;url=http://s6.sinaimg.cn/orignal/6b291d73g777601727925" target="_blank"> <img src="http://s6.sinaimg.cn/middle/6b291d73g777601727925&amp;690" name="image_operate_48221313487264779" alt="感知哈希算法浅析" title="感知哈希算法浅析" height="62" width="66"></a> = 8f373714acfcf4d0<br><br><wbr><wbr><wbr>得到指纹以后，就可以对比不同的图片，看看64位中有多少位是不一样的。在理论上，这等同于计算Hammingdistance）。如果不相同的数据位不超过5，就说明两张图片很相似；如果大于10，就说明这是两张不同的图片。<br><br><wbr><wbr><wbr><wbr>这个算法非常好，无论你改变图片的高宽、亮度甚至颜色，都不会改变哈希值。最关键的是速度极快！cool！<br><br><wbr><wbr><wbr><wbr>我在ftp里放了这个算法的python版本（使用了PIL库），如果读者会ruby的话，不妨使用RMagick库，同样强大（文档：http://www.imagemagick.org/RMagick/doc/项目：http://rubyforge.org/projects/rmagick/）<br><br><wbr><wbr><wbr><wbr>有没有更好的方法来判断相似度呢？有，pHash。这种方法稍复杂写，运用了DCT来降低频度，比起平均值方法更精确了。DCT参见http://en.wikipedia.org/wiki/Discrete_cosine_transform<br><wbr><wbr><wbr><wbr>下面来看它的过程。<br><wbr><wbr><wbr><wbr>第一步，缩小尺寸。<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>与平均值方法类似，不过要比8X8大些，32X32是个好尺寸，这样做是为了简化DCT的计算，而不是降频。<br><br><wbr><wbr><wbr><wbr>第二步，简化色彩。<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>改成灰度图，也是为了减少DCT计算量。<br><br><wbr><wbr><wbr><wbr>第三步，计算DCT。<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>DCT将图片分成了频度和纯量的集合。当JPEG使用8X8的DCT时，算法就使用32X32的DCT。<br><br><wbr><wbr><wbr><wbr>第四步，降低DCT。<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>当DCT是32X32时，只保留顶左的8X8，这部分代表了图片的最低频。这是神奇的一步。<br><wbr><wbr><wbr><wbr><br><wbr><wbr><wbr><wbr>第五步，计算平均值。<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>只用8X8的DCT低频值，因为DC系数和其他值相差很大，会破坏平均值。<br><wbr><br><wbr><wbr><wbr><wbr>第六步，进一步缩小DCT<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>将每个像素的灰度（64比特），与平均值进行比较。大于或等于平均值，记为1；小于平均值，记为0。图片结构不变，结果就不会变。这完成了关键的一步。<br></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>