唐林川 鄧思宇 吳彥學 溫柳英

摘 要：數(shù)據(jù)庫中大量重復圖片的存在不僅影響學習器性能，而且耗費大量存儲空間。針對海量圖片去重，提出一種基于pHash分塊局部探測的海量圖像查重算法。首先，生成所有圖片的pHash值;其次，將pHash值劃分成若干等長的部分，若兩張圖片的某一個pHash部分的值一致，則這兩張圖片可能是重復的;最后，探討了圖片重復的傳遞性問題，針對傳遞和非傳遞兩種情況分別進行了算法實現(xiàn)。實驗結(jié)果表明，所提算法在處理海量圖片時具有非常高的效率，在設(shè)定相似度閾值為13的條件下，傳遞性算法對近30萬張圖片的查重僅需2min，準確率達到了53%。

關(guān)鍵詞：重復圖片檢測;海量數(shù)據(jù);感知Hash;局部探測;傳遞性

中圖分類號：TP391

文獻標志碼：A

Deduplication for massive images based on pHash block detection

Duplicate detection algorithm for massive images based on pHash block detection

TANG Linchuan， DENG Siyu， WU Yanxue， WEN Liuying*

School of Computer Science， Southwest Petroleum University， Chengdu 610500， China

Abstract：

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; transitivity

0 引言

隨著計算機多媒體技術(shù)的快速發(fā)展，數(shù)字圖像已經(jīng)普遍出現(xiàn)在人們的日常生活中。同時，數(shù)字信息呈幾何級數(shù)增長，對現(xiàn)有存儲系統(tǒng)的容量、吞吐性能、可擴展性、可維護性和能耗管理等各個方面帶來全新的挑戰(zhàn)，且存儲效率低和存儲成本高等問題凸顯，僅增加存儲空間無法解決根本問題。在此情況下，消除冗余數(shù)據(jù)成為優(yōu)化存儲性能的重要手段，海量圖像去重也是熱門的研究分支之一，其目標是刪除海量圖像中重復的圖像。

圖像檢索技術(shù)是圖像去重的基本步驟，流行的圖像檢索技術(shù)是基于內(nèi)容的（Content Based Image Retrieval， CBIR）[1-2]。CBIR提取圖像的顏色、形狀、紋理等可視特征，對其特征進行量化表達，然后選擇合適的度量方式進行匹配。圖像的特征往往需要用高維向量來表達，因此大規(guī)模圖像檢索具有明顯的特征維度高的特性。在此情況下，基于Hash的檢索方法[3-4]被提出并得到快速發(fā)展，已經(jīng)被廣泛地應用在電子商務[5-7]、醫(yī)學研究[8]、刑偵勘察[9]、版權(quán)保護[10]等領(lǐng)域。

目前，常用的Hash算法有MD5[11]、SHA[12]和感知Hash（perception Hashing， pHash）[13]等?；贛D5的圖像去重算法存在嚴重的局限性，對于圖像數(shù)據(jù)，任何微小的改變都會導致MD5的劇變，比如添加水印等，因此，針對圖像去重問題，一般采用pHash檢索算法。

圖像Hash是將圖像映射成較短的編碼序列，叫作哈希指紋，用來表示其內(nèi)容特征。通過計算圖片間的哈希指紋的海明距離來判斷兩張圖片間的相似度。傳統(tǒng)感知Hash算法是一個pair-wised的算法，它對每一對圖片都進行匹配，存在復雜度高、效率低等問題，不適合運用在大規(guī)模數(shù)據(jù)量的情況下。本文提出一種基于pHash的分塊局部探測的海量圖片查重算法，能夠提高檢索速度，同時避免誤刪除。

算法1給出了圖像索引的構(gòu)建過程。

算法1 圖像索引構(gòu)建算法。

輸入：所有圖像的pHash值集合P;pHash值的長度p;圖像路徑集合M;pHash值分裂塊數(shù)s;

輸出：圖像的映射關(guān)系f。

有序號的程序——————————Shift+Alt+Y

程序前

1）

f ←[fi]si-1;l ← p/s

2）

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∪

9）

}//end if

10）

fi（b） ← fi（b） ∪{Mj}

11）

}//end for

12）

}//end for

13）

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 if

21）

}//end if

22）

}//end for

23）

}//end for

24）

}//end for

25）

return D

程序后

在算法2中，

1）進行初始化操作;

2）定位到第i個索引集;

3）～23）對第i個索引集中每一個映射，判斷其中的圖片對的相似度是否小于或等于閾值，根據(jù)條件調(diào)整最終的重復圖片集合，

其中，17）～19）將兩個重復圖片集合融合到一起，這是由重復的傳遞性決定的。

針對pHash分塊探測算法，需要遵循的原則是圖片間重復性的傳遞思想;即圖片a和圖片b互為重復圖片，圖片a和圖片c互為重復圖片，那么圖片b和圖片c互為重復圖片。文中的相似度閾值由專家設(shè)定，具有一定的隨機性和差異性。

算法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 if

14）

}//end if

15）

}//end for

16）

}//end for

17）

if i∈g {

18）

g（i） ← g（i）∪{i}

19）

S ← S∪g（i）

20）

}//end if

21）

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 for

26）

}//end for

27）

}//end if

28）

}//end for

29）

for i∈g {

30）

D ← D∪{g（i）}

31）

}//end for

32）

return D

程序后

在算法3中，

1）～3）進行初始化操作，1）中定義了一個映射，鍵為圖片id，值為圖片id對應的重復圖片集;

4）～5）定位第i張圖片并判斷第i張圖片是否已經(jīng)被判斷為重復;

6）～16）將第i張圖片的pHash分塊并在不同的pHash索引集中探測重復圖片;17）～26）實現(xiàn)非傳遞性，已經(jīng)判斷為重復的圖片集合將從pHash索引中去除。

2.3 樣例分析

本節(jié)提供了一個樣例來說明pHash分塊局部探測算法如何進行pHash分塊，并將全局探測方法轉(zhuǎn)化為局部探測方法。

第一步，生成每張圖像的哈希值，并等分成四組，如表1所示。

第二步，根據(jù)哈希塊中的哈希值完成匹配，可建立映射關(guān)系，如表2所示。x3，x4的pHash1中的值都是caad，即x3，x4可能是重復圖像，則將x3，x4兩張圖像放在同一索引下。同理可計算pHash2、pHash3和pHash4塊。

第三步，計算得x3，x4完整哈希值的海明距離為9，則判斷x3，x4是不重復圖片。

2.4 算法優(yōu)勢

本文提出的算法相比于傳統(tǒng)pHash窮舉查重的算法而言，優(yōu)勢在于：在保證精度與傳統(tǒng)方法相當?shù)那闆r下，極大提高了算法的運行效率。傳統(tǒng)pHash算法通過窮舉來進行查重，窮舉的手段是進行兩兩比較。很顯然，任意兩張圖片都需要比較其pHash序列的漢明距離。假設(shè)pHash分塊數(shù)為s，那么存在以下3種情況：

1）相似度閾值t

2）相似度閾值t=s。此時存在這樣一種特殊情況無法被算法檢測到：圖片A和圖片B在每個pHash塊中均存在且只存在1個bit比特位不同，此時相似度為t。又假設(shè)圖片A和圖片B在相似度為t的條件下，不同的bit比特位之間相互獨立，且在不同的pHash塊中出現(xiàn)的概率是相等的。此時，無法被算法檢測到的情況發(fā)生的概率僅為s！/ss。這相當于將s個不同的小球等概率地放進s個不同的盒子，每個盒子均不為空的概率。特別地，若t=s=4，那么這個概率為3/32，當s越大，這個值越小。

3）相似度閾值t>s。此時采用與2）種情形相同的假設(shè)，那么無法被檢測到的情況則有t-s+1種，分別是當相似度為s、s+1、…、t時，每個pHash塊均有至少一個bit比特位相同的情況。當t比s大得多的時候，無法被檢測到的情況發(fā)生的概率較大。

所以，本文算法在第一種情況下，能夠達到與傳統(tǒng)算法一樣的精度。但后兩種情況則表明，本文提出的算法與傳統(tǒng)方法依然存在一定的精度差距。盡管如此，傳統(tǒng)算法也只是局限于理論精度，它在處理海量圖片時顯得非常乏力，甚至不可計算。

本文算法運行效率的提高是通過將傳統(tǒng)pHash窮舉查重轉(zhuǎn)化為局部查重來實現(xiàn)的。此時，圖片全集將被劃分成若干較小的不相交子集，在子集上進行兩兩比較遠高于在全集上進行兩兩比較的運行效率。例如，有100張圖片需要查重，本文算法將其劃分成了20個子集，每個子集有5張圖片，那么本文算法僅需做20×10=200次兩兩比較，而傳統(tǒng)算法將要做4950次比較，這極大地降低了比較次數(shù)。

3 實驗及分析

在本章中，首先說明數(shù)據(jù)集的來源和生成方式;其次，自定義一個查重精度的評價指標;最后，分別探討重復的傳遞性和非傳遞性對實驗結(jié)果的影響，并給出算法的運行時間。

3.1 數(shù)據(jù)集

本文采用的數(shù)據(jù)集為淘寶的商品圖片集合，圖片總量為81293張，因為無法確定該數(shù)據(jù)集是否重復，所以先需要對這些圖片去一次重復。設(shè)定海漢明距離閾值為3，在此情況下，有9546張圖片重復，將重復圖片刪除，最終得到的圖片總量為71747。

接著，利用一系列圖像處理方法生成重復的圖片數(shù)據(jù)，具體方法如下：

1）亮度調(diào)整。隨機地選擇一個亮度調(diào)整率α∈[-0.25，0.25]，負值表示圖片變暗;反之表示圖片變亮。

2）對比度調(diào)整。隨機地選擇一個對比度調(diào)整率β∈[0，3]。

3）飽和度調(diào)整。隨機地選擇一個飽和度調(diào)整率γ∈[0，3]。

4）剪裁。隨機剪裁圖片，剪裁后的圖片大小為原始圖片大小的0.8～1倍。

5）噪聲。隨機給圖像添加高斯白噪聲、泊松噪聲或是椒鹽噪聲。

6）高斯模糊。隨機設(shè)定正態(tài)分布的標準差σ∈（0，3]，模糊半徑r∈{1，2，3，4，5}。

通過以上方式，能夠知道哪些圖片是重復的，并可利用先驗信息對本文算法作出較為合理的評價。按照上述方法，針對數(shù)據(jù)集中的每一張圖片，重復生成三張圖片，最后得到的圖像總量為286988張。

2.4節(jié)從理論上分析了本文算法和傳統(tǒng)算法所得到的精度是相當?shù)?，所以，這里生成的數(shù)據(jù)集是為了驗證算法可用并且具有較高的執(zhí)行效率。在接下來的實驗中，我們將會看到這一點。

3.2 評價指標

由于本文研究圖片去重問題，但此處所說的重復并不是指圖片一定完全一致。從人的感知上講，圖片的重復應該具有局部不敏感的特點，即圖片中少量像素點的不同不影響人的感知。由于圖片查重相當于將重復圖片聚到相同的簇，這可被看成是一個聚類問題，因此，本文使用如下評價指標來衡量算法的查重效果：

acc（A）=（∑a∈Amax_dup（a））/N（4）

其中：A是圖片重復檢測的結(jié)果集合，其中的元素為檢測到的重復圖片。max_dup函數(shù)為a中最大的真實重復圖片個數(shù)。例如，假設(shè)a=[1，1，2，2，2，3，3]，那么max_dup（a）=3，即a中出現(xiàn)次數(shù)最多的元素個數(shù)，也就是2的個數(shù)。實際上，acc就是聚類純度。

3.3 實驗結(jié)果

本文從多個角度來衡量算法的有效性，分別是查重精度acc、檢測到的重復圖片數(shù)量分布和查重時間。實驗設(shè)置主要是針對相似度閾值的設(shè)置，這里相似度閾值范圍被設(shè)定為{0，1/64，…，17/64}（為了更好地顯示結(jié)果，在圖中省略了分母）。實驗在單臺MacOS Intel i5環(huán)境上進行，查重精度隨相似度閾值的變化曲線如圖2所示。

圖2顯示，具有傳遞性的圖片重復檢測效果明顯優(yōu)于非傳遞性，且非傳遞性的結(jié)果并不是單調(diào)的，這是因為隨著相似度閾值的增加，有較多的不同圖片被錯誤地檢測為重復。但是具有傳遞性的結(jié)果恰恰相反，盡管有較多的不同圖片被錯誤地檢測為重復，但是由于傳遞的性質(zhì)，較多的相同圖片也會被放到同一個集合。

圖3（a）和（b）所示為相似度閾值為10，非傳遞性和傳遞性檢測算法分別得到的重復圖片集合size的分布直方圖。

可以看到，對非傳遞性檢測算法而言，大部分情況下，該算法檢測到的重復圖片為兩張。少部分情況下可以探測到更多的重復圖片。傳遞性檢測算法和非傳遞性檢測算法得到的結(jié)果類似，不同地是，該算法所檢測的圖片集合的size分布具有更廣的范圍，這是因為傳遞性本身就會使得集合的size增加。

圖4展示了兩種重復圖片檢測算法隨相似度閾值變化的時間花費曲線。可以看到，非傳遞的檢測算法運行時間隨著相似度閾值呈線性增長關(guān)系，且時間花費增長不明顯。相反地，傳遞性檢測算法在相似度閾值為14的時候，時間花費陡增，由于相似度閾值為16，17的時候，時間花費過大，圖中沒有給出。此時傳遞性算法幾乎沒有實用性。但這也符合預期，因為在相似度閾值達到一定值的時候，由于傳遞性的存在，許多小的重復圖片集合將會被融合到一起，此時針對該集合的檢測將花費大量時間。綜合圖2和圖4來看，在相似度閾值為13的時候，對近30萬張圖片的傳遞性重復檢測算法的時間花費僅需2min。此時傳遞性算法的精度達到了53%，非傳遞性算法的精度盡管達到了最高點，但仍不及傳遞性算法。如果進一步提升相似度閾值，傳遞性算法的運行時間將急劇上升。這是因為傳遞性本身會使得檢測到的重復圖片集合增大。如果在相似度設(shè)定也較大的情況，傳遞性算法檢測到的重復圖片集合會非常龐大，針對該重復圖片集合元素兩兩比較所花費的時間也會非常多。

4 結(jié)語

本文提出了一種新型的圖片查重算法，首先計算出所有圖片的pHash指紋，接著對pHash指紋進行分塊，目的是將全局查重轉(zhuǎn)變?yōu)榫植坎橹亍＿@極大地提高了重復圖片檢測的效率。設(shè)置相似度閾值為13的條件下，采用傳遞性查重算法處理近30萬張圖片僅需大約2min，精度達到了53%。未來將會采用更加優(yōu)質(zhì)的圖片指紋算法，以期獲得更好的結(jié)果。

參考文獻

[1]SMEULDERS A W M， WORRING M， SANTINI S， et al. Content-based image retrieval at the end of the early years [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（12）： 1349-1380.

[2]LIU Y， ZHANG D， LU G， et al. A survey of content-based image retrieval with high-level semantics [J]. Pattern Recognition， 2007， 40（1）： 262-282.

[3]KUO Y H， CHEN K T， CHIANG C H， et al. Query expansion for hash-based image object retrieval [C]// MM ‘09： Proceedings of the 17th ACM International Conference on Multimedia. New York： ACM， 2009： 65-74.

[4]ZHEN Y， YEUNG D Y. Active hashing and its application to image and text retrieval [J]. Data Mining and Knowledge Discovery， 2013， 26（2）： 255-274.

[5]LI Q-N， LI Y-Q， JIANG S-J. Application of a new Hash function in e-commerce [C]// ICEE ‘12： Proceedings of the 2012 3rd International Conference on E-Business and E-Government. Washington， DC： IEEE Computer Society， 2012， 4： 223-225.

[6]WRIGHT A. Controlling risks of e-commerce content [J]. Computers and Security， 2001， 20（2）： 147-154.

[7]張文麗，鐘曉燕，馮前進，等.基于Hash函數(shù)敏感性的醫(yī)學圖像精確認證[J].中國圖象圖形學報，2008，13（2）：204-208.（ZHANG W L， ZHONG X Y， FENG Q J， et al. Hard authentication for medical image based on sensitivity of Hash function [J]. Journal of Image and Graphics， 2008， 13（2）： 204-208.）

[8]趙峰.Hash簽名在電子商務中的應用[J].計算機與數(shù)字工程，2014，42（3）：531-534.（ZHAO F. Hash signature application in the electronic commerce [J]. Computer and Digital Engineering， 2014， 42（3）： 531-534.）

[9]ZHAN S， ZHAO J， TANG Y， et al. Face image retrieval： super-resolution based on sketch-photo transformation[J]. Soft Computing， 2018， 22（4）： 1351-1360.

[10]AL-MANSOORI S， KUNHU A. Hybrid DWT-DCT-Hash function based digital image watermarking for copyright protection and content authentication of DubaiSat-2 images [C]// Proceedings of the High-Performance Computing in Remote Sensing IV. International Society for Optics and PhotonicsBellingham， WA： SPIE， 2014， 9247： 924707.

[11]DEEPAKUMARA J， HEYS H M， VENKATESAN R. FPGA implementation of MD5 hash algorithm [C]// Proceedings of the 2001 Canadian Conference on Electrical and Computer Engineering. Piscataway， NJ： IEEE， 2001， 2： 919-924.

[12]GREMBOWSKI T， LIEN R， GAJ K， et al. Comparative analysis of the hardware implementations of hash functions SHA-1 and SHA-512 [C]// Proceedings of the 2002 International Conference on Information Security， LNCS 2433. Berlin： Springer， 2002： 75-89.

[13]SHIM H. PHash： a memory-efficient， high-performance key-value store for large-scale data-intensive applications [J]. Journal of Systems and Software， 2017， 123： 33-44.

[14]LIN K， YANG H-F， HSIAO J-H， et al. Deep learning of binary hash codes for fast image retrieval [C]// Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition Workshops. Piscataway， NJ： IEEE， 2015： 27-35.

[15]劉明生，王艷，趙新生.基于Hash函數(shù)的RFID安全認證協(xié)議的研究[J].傳感技術(shù)學報，2011，24（9）：1317-1321.（LIU M S， WANG Y， ZHAO X S. Research on RFID security authentication protocol based on Hash function [J]. Chinese Journal of Sensors and Actuators， 2011， 24（9）： 1317-1321.）

[16]周國強，田先桃，張衛(wèi)豐，等.基于圖像感知哈希技術(shù)的釣魚網(wǎng)頁檢測[J].南京郵電大學學報（自然科學版），2012， 32（4）：59-63.（ZHOU G Q， TIAN X T， ZHANG W F， et al. Detecting phishing Web pages based on image perceptual hashing technology [J]. Journal of Nanjing University of Posts and Telecommunications （Natural Science）， 2012， 32（4）： 59-63.）

[17]KURSA M B， JANKOWSKI A， RUDNICKI W R. Boruta—a system for feature selection [J]. Fundamenta Informaticae， 2010， 101（4）： 271-285.

[18]寧星，蔣年德.基于LBP人臉識別算法的預處理研究[J].電子質(zhì)量，2012（4）：76-77.（NING X， JIANG N D. Pretreatment research for face recognition based on LBP [J]. Electronic Quality， 2012（4）： 76-77.）

[19]DATAR M， IMMORLICAL N， INDYK P， et al. Locality-sensitive hashing scheme based on p-stable distributions [C]// Proceedings of the 20th Annual Symposium on Computational Geometry. New York： ACM， 2004： 253-262.

This work is partially supported by the Open Project of Key Laboratory of Data Mining and Application of Zhejiang Ocean University （OBDMA201601）.

TANG Linchuan， born in 1993， M. S. candidate. His research interests include active learning， recommender systems.

DENG Siyu， born in 1993， M. S. candidate. Her research interests include active learning.

WU Yanxue， born in 1995， M. S. candidate. His research interests include deep learning， feature learning.

WEN Liuying， born in 1983， Ph. D.， lecturer. Her research interests include rough set， attribute extraction， granular computing.