基于pHash分块局部探测的海量图像查重算法.docx

    基于pHash分块局部探测的海量图像查重算法    唐林川 邓思宇 吴彦学 温柳英摘 要：数据库中大量重复图片的存在不仅影响学习器性能，而且耗费大量存储空间针对海量图片去重，提出一种基于pHash分块局部探测的海量图像查重算法首先，生成所有图片的pHash值;其次，将pHash值划分成若干等长的部分，若兩张图片的某一个pHash部分的值一致，则这两张图片可能是重复的;最后，探讨了图片重复的传递性问题，针对传递和非传递两种情况分别进行了算法实现实验结果表明，所提算法在处理海量图片时具有非常高的效率，在设定相似度阈值为13的条件下，传递性算法对近30万张图片的查重仅需2min，准确率达到了53%Key：重复图片检测;海量数据;感知Hash;局部探测;传递性：TP391文献标志码：ADeduplication for massive images based on pHash block detectionDuplicate detection algorithm for massive images based on pHash block detectionTANG Linchuan， DENG Siyu， WU Yanxue， WEN Liuying*School of Computer Science， Southwest Petroleum University， Chengdu 610500， ChinaAbstract：The large number of duplicate images in the database not only affects the performance of the learner， but also consumes a lot of storage space. For massive image deduplication， a duplicate detection algorithm for massive images was proposed based on pHash （perception Hashing）. Firstly， the pHash values of all images were generated. Secondly， the pHash values were divided into several parts with the same length. If the values of one of the pHash parts of the two images were equal to each other， the two images might be duplicate. Finally， the transitivity of image duplicate was discussed， and corresponding algorithms for transitivity case and non-transitivity case were proposed. Experimental results show that the proposed algorithms are effective in processing massive images. When the similarity threshold is 13， detecting the duplicate of nearly 300000 images by the proposed transitive algorithm only takes about two minutes with the accuracy around 53%.Key words：duplicate image detection; massive data; perception Hashing （pHash）; block detection; transitivity0 引言随着计算机多媒体技术的快速发展，数字图像已经普遍出现在人们的日常生活中。

同时，数字信息呈几何级数增长，对现有存储系统的容量、吞吐性能、可扩展性、可维护性和能耗管理等各个方面带来全新的挑战，且存储效率低和存储成本高等问题凸显，仅增加存储空间无法解决根本问题在此情况下，消除冗余数据成为优化存储性能的重要手段，海量图像去重也是热门的研究分支之一，其目标是删除海量图像中重复的图像图像检索技术是图像去重的基本步骤，流行的图像检索技术是基于内容的（Content Based Image Retrieval， CBIR）[1-2]CBIR提取图像的颜色、形状、纹理等可视特征，对其特征进行量化表达，然后选择合适的度量方式进行匹配图像的特征往往需要用高维向量来表达，因此大规模图像检索具有明显的特征维度高的特性在此情况下，基于Hash的检索方法[3-4]被提出并得到快速发展，已经被广泛地应用在电子商务[5-7]、医学研究[8]、刑侦勘察[9]、版权保护[10]等领域目前，常用的Hash算法有MD5[11]、SHA[12]和感知Hash（perception Hashing， pHash）[13]等基于MD5的图像去重算法存在严重的局限性，对于图像数据，任何微小的改变都会导致MD5的剧变，比如添加水印等，因此，针对图像去重问题，一般采用pHash检索算法。

图像Hash是将图像映射成较短的编码序列，叫作哈希指纹，用来表示其内容特征通过计算图片间的哈希指纹的海明距离来判断两张图片间的相似度传统感知Hash算法是一个pair-wised的算法，它对每一对图片都进行匹配，存在复杂度高、效率低等问题，不适合运用在大规模数据量的情况下本文提出一种基于pHash的分块局部探测的海量图片查重算法，能够提高检索速度，同时避免误删除算法1给出了图像索引的构建过程算法1 图像索引构建算法输入：所有图像的pHash值集合P;pHash值的长度p;图像路径集合M;pHash值分裂块数s;输出：图像的映射关系f有序号的程序——————————Shift+Alt+Y程序前1）f ←[fi]si-1;l ← p/s2）for i ←1 to s {3）B ←4）for j ← 1 to |P| {5）b ← Pj [i*l，（i+1）*l]6）if bB {7）fi（b） ←8）B ← B∪{b}9）}//end if10）fi（b） ← fi（b） ∪{Mj}11）}//end for12）}//end for13）return f程序后2.2 pHash分块探测算法该阶段利用算法1获得的图像索引f，计算索引块fi中每一个局部特征值下的图像相互间的海明距离，进而判断图片是否重复。

通常情况下，海明距离越大说明图片间的相似程度越低算法2给出了传递性重复图像的检测过程算法2 传递性重复图像检测算法输入：所有图像的pHash值集合P;图像路径集合M;pHash图像索引f;相似度阈值t;输出：集合D，Di是一组重复图像集合有序号的程序——————————Shift+Alt+Y程序前1）D ←2）for i ←1 to |f| {3）for b∈fi{4）for （j1， j2）∈C[fi（b）] {5）if dist（Pj1， Pj2） ≤ t {6）if Dk1， Dk2∈D，Mj1Dk1∧M j2Dk2{7）D ← D∪{Mj1， Mj2}8）} else if（Dk1∈D，Mj1∈Dk1）∧（Dk2∈D， Mj2Dk2） {9）D ← D-{Dk1}10）Dk1 ← Dk1∪{ Mj2}11）D ← D∪{ Dk1}12）} else if （Dk2∈D，Mj2∈Dk2）∧（Dk1∈D， Mj1Dk1） {13）D ← D-{Dk2}14）Dk2 ← Dk2∪{Mj1}15）D ← D∪{Dk2}16）} else if（Dk1∈D，Mj1∈Dk1）∧（Dk2∈D， Mj2Dk2） {17）D ← D-{Dk1，Dk2}18）Dk1 ← Dk1∪ Dk2∪ { Mj1， Mj2}19）D ← D∪{Dk1}20）}//end if21）}//end if22）}//end for23）}//end for24）}//end for25）return D程序后在算法2中，1）進行初始化操作;2）定位到第i个索引集;3）～23）对第i个索引集中每一个映射，判断其中的图片对的相似度是否小于或等于阈值，根据条件调整最终的重复图片集合，其中，17）～19）将两个重复图片集合融合到一起，这是由重复的传递性决定的。

针对pHash分块探测算法，需要遵循的原则是图片间重复性的传递思想;即图片a和图片b互为重复图片，图片a和图片c互为重复图片，那么图片b和图片c互为重复图片文中的相似度阈值由专家设定，具有一定的随机性和差异性算法3给出了非传递性重复图像的检测过程算法3 非传递性重复图像检测算法输入：所有图像的pHash值集合P;图像路径集合M;pHash图像索引f;相似度阈值t;输出：集合D，Di是一组重复图像集合有序号的程序——————————Shift+Alt+Y程序前1）Define g：Z+ → 2Z+2）D，S ←，3）l ← |pl|/|f|4）for i ←1 to |M| {5）if iS{6）for j ←1 to |f| {7）b ← Pi[j*l，（j+l）*l]8）for k∈（fj（b）-{i}） {9）if dist（Pi， Pk） ≤ t {10）if ig {11）g（i） ←12）g（i） ← g（i）∪{k}13）}//end if14）}//end if15）}//end for16）}//end for17）if i∈g {18）g（i） ← g（i）∪{i}19）S ← S∪g（i）20）}//end if21）for j∈g（i） {22）for k ←1 to |f| {23）b ← Pj[k*l，（k+1）*l]24）fi（b） ← fi（b）-{j}25）}//end for26）}//end for27）}//end if28）}//end for29）for i∈g {30）D ← D∪{g（i）}31）}//end for32）return D程序后在算法3中，1）～3）进行初始化操作，1）中定义了一个映射，键为图片id，值为图片id對应的重复图片集;4）～5）定位第i张图片并判断第i张图片是否已经被判断为重复;6）～16）将第i张图片的pHash分块并在不同的pHash索引集中探测重复图片;17）～26）实现非传递性，已经判断为重复的图片集合将从pHash索引中去除。

2.3 样例分析本节提供了一个样例来说明pHash分块局部探测算法如何进行pHash分块，并将全局探测方法转化为局部探测方法第一步，生成每张图像的哈希值，并等分成四组，如表。