图片识别——三种哈希算法性能与准确度比较 - 高飞网
709 人阅读

图片识别——三种哈希算法性能与准确度比较

2017-07-28 02:09:46

    前面几篇文章对图片的三种哈希算法做了简单的介绍:均值哈希算法感知哈希算法差异哈希算法。本篇将对上面算法做一个总结。并对在性能方面做些对比。


性能和准确度

    目前有个超过150,000张图片的实验,有几张已知出现次数的待查找测试图片。比如一张图片(针)在150,000张图片(草堆)中出现一次,另外一张出现两次,第三张测试图片出现了32次。

    分别使用aHash、pHash、dHash三种算法在这一“草堆”查找一只“针”。为了作比较,没有预先缓存图片库中的任何哈希值。比较值(汉明距离)10以内的就认为是匹配。下面就是实现结果:

  1. 不计算哈希。这是一个比较的基线。程序把每张图片加载到内存中,之后一张张的卸载。这将告诉我们仅仅是文件访问和加载要花费多长时间(所有的图片在NFS模式的文件系统中加载--当然还有网络请求)。总时间是16分钟。没有任何图片比较,仅仅是加载完这些图片,要耗去16分钟。
  2. 不计算哈希,但缩小尺寸。上面讨论的所有算法都是从缩小图片尺寸开始的。小图缩放非常快,但是大图会花费10秒甚至更长时间。仅仅是加载和缩小这150,000张图,耗了3.75小时(真的有必要研究一种方法来优化图片缩放算法)。
  3. aHash算法。该算法花费了3.75小时来执行。换句话说,加载和缩放图片比算法本身要花费更多时间。但不幸的是,aHash算法出现了大量的误报。它去匹配所有期望的图片,但出现了几十位的误报。比如说,测试图片应该匹配32次,实现上却匹配了400张图片。更坏的是,这些图片中,有些差别位数竟然不到2位。总之,aHash算法是一种快速,但不准确的算法。
  4. pHash算法。该算法在准确性表现最好的。没有误报,没有漏报,每次匹配的距离值都在2以内。我确信更大的数据集(或修改测试图片)可能会产生误判断。但是漏报错误数量会大大小于aHash。
    毫无疑问,pHash的问题就是性能方面。它花费了7小时才完成。这是因为DCT比较有大量的操作,包括余弦变换。如果预先计算好DCT的数值,将会至少减少1-2小时的比较时间。总之,pHash算法准确,但不够快。
  5. dHash算法。绝对令人惊叹!非常小的误报。比如,已知有两个匹配的图片,最后得出结果是6个匹配(4个误报)。数值为10,0,8,10,0和10,两个0的是正确的匹配,所有误报匹配都是高的数值。而速度方面,dHash和aHash差不多。从技术层面来讲,它的速度快是因为不需要计算颜色均值。dHash算法有着aHash算法的速度,和非常小的误报率。


算法变种

    我已经试验了几种dHash算法的变种。比如,最初设想的是用一个8*8的图片并包含最后一个比较(比较p[0]与p[7]之间的不同),这确实比现在9*8的变体要差一些,不过差一点点。

    你可以使用结合dHash的性能加上pHahs的准确性。比如在用dHash比较得到匹配后,再用pHash去比较。

    最后,我意识到用dHash作为一种快速的过滤器是不错的选择。但可能不需要使用64位来比较。试想可以用6*4大小的图片来生成16位的dHash。这会产生20个不同值(每行6个像素产生5个不同值,共4行)。忽略四个角落产生16位hash。忽略的好处是像Instagram类似的光晕的影响。如果有1百万图片,那么每个16位的dHash会包含15个图片(因为有hash碰撞)。然后用pHash去比较15个图片依然非常快的。如果有十亿张图片,会有15,258张图片的碰撞,但依然还是非常小的数量级。

    我甚至可以让16位dHash变得稀疏,允许任何一位的变化都算匹配。任何可能的16位dHash计算将产生17个可能的dHash值匹配,百万图片将产生260个碰撞。10亿图片会生产260000碰撞,10亿的图片,同时存储16位dHash、64位dHash和64位pHash值是值得的。


应用比较

    从感知哈希算法中我们要考虑两个事情:速度和准确性。把dHash与pHash结合起来,我们将两者兼得。但是即使没有pHash,dHash相对于aHash依然是非常大的提升,并且没有任何性能损失。


还没有评论!
54.156.37.174