海量圖片快速去重技術(shù)

韓逢慶 宋志堅(jiān) 余銳

摘要：針對(duì)海量圖片中的去除重復(fù)圖片效率低的問題，提出一種基于圖片特征的并行化海量圖片快速去重技術(shù)。首先，對(duì)圖片提取圖片顏色、紋理、形狀等特征，用來全面描述圖片；其次，使用度量標(biāo)準(zhǔn)對(duì)圖片之間的特征距離進(jìn)行度量計(jì)算；最后，利用如果兩個(gè)點(diǎn)到任意一點(diǎn)距離相等則這兩點(diǎn)有可能是同一個(gè)點(diǎn)的思想實(shí)現(xiàn)根據(jù)特征距離對(duì)重復(fù)圖片的快速定位，達(dá)到重復(fù)圖片檢測(cè)與去重的目的。結(jié)合實(shí)驗(yàn)數(shù)據(jù)分析驗(yàn)證該技術(shù)不僅能夠準(zhǔn)確地去重圖片，且采用i5四核處理器的單機(jī)計(jì)算方式僅10min左右即可處理500萬級(jí)圖片量，與一般的兩兩計(jì)算相比，提高了海量圖片去重的時(shí)效性，使得計(jì)算時(shí)間大幅度縮短。

關(guān)鍵詞：

海量圖片；快速去重；并行化；單機(jī)計(jì)算；圖片特征

中圖分類號(hào)： TP301.6 文獻(xiàn)標(biāo)志碼：A

0引言

隨著數(shù)據(jù)的指數(shù)級(jí)增長(zhǎng)，企業(yè)面臨的快速備份和恢復(fù)的時(shí)間點(diǎn)越來越多，管理保存數(shù)據(jù)的成本及數(shù)據(jù)中心空間和能耗也變得越來越嚴(yán)重。研究發(fā)現(xiàn)，應(yīng)用系統(tǒng)所保存的數(shù)據(jù)中高達(dá)60%是冗余的，縮減數(shù)據(jù)占用空間，降低成本，重復(fù)數(shù)據(jù)刪除技術(shù)此句不太通順，請(qǐng)作相應(yīng)調(diào)整。已成為一個(gè)熱門的研究課題。所以，重復(fù)數(shù)據(jù)刪除技術(shù)就成為了縮減數(shù)據(jù)占用空間及降低成本的重要手段之一。目前重復(fù)數(shù)據(jù)刪除技術(shù)主要包含相同數(shù)據(jù)檢測(cè)及相似數(shù)據(jù)檢測(cè)兩大類，其中相同數(shù)據(jù)檢測(cè)[1-3]的方法主要有完全文件檢測(cè)技術(shù)、固定分塊檢測(cè)等，這些檢測(cè)方法主要通過hash技術(shù)進(jìn)行數(shù)據(jù)挖掘；相似數(shù)據(jù)檢測(cè)利用數(shù)據(jù)自身的相似性特點(diǎn)，通過shingle技術(shù)[4]、bloom filter技術(shù)[5]及模式匹配技術(shù)[6-7]等挖掘出重復(fù)數(shù)據(jù)。這些技術(shù)使得共享數(shù)據(jù)塊的文件之間產(chǎn)生了依賴性，降低了系統(tǒng)的可靠性；同時(shí)因?yàn)閿?shù)據(jù)檢測(cè)對(duì)比等過程導(dǎo)致大量的計(jì)算開銷，對(duì)系統(tǒng)的性能影響也很大。因此，為了提高檢測(cè)速度，降低對(duì)系統(tǒng)的性能影響，很多學(xué)者提出了并行化處理方式[8-10]。

由于圖片文件的數(shù)據(jù)量大且不易修改的特性由于圖片文件的數(shù)據(jù)量大其不易修改的特性，若采用文件級(jí)去重則計(jì)算開銷大，效率較低，而塊級(jí)則容易導(dǎo)致圖片讀取不完整、刪除錯(cuò)誤、恢復(fù)圖片困難等問題，在海量圖片的情況下這些問題將更加突出。針對(duì)上述問題，文獻(xiàn)[11]提出一種針對(duì)海量圖片文件存儲(chǔ)去重技術(shù)的方法，利用MD5（MessageDigest Algorithm 5）特性在圖片文件上傳存儲(chǔ)過程中實(shí)現(xiàn)去重取得了較好的效果。本文則針對(duì)已存儲(chǔ)的海量圖片，提出一種并行化快速去重算法：主要提取圖片本身具有的數(shù)據(jù)特征，根據(jù)特征進(jìn)行重復(fù)檢測(cè)，實(shí)現(xiàn)海量圖片去重處理，其時(shí)間復(fù)雜度為Ο（n2）。進(jìn)一步，為了降低算法時(shí)間復(fù)雜度，本文針對(duì)該算法進(jìn)行改進(jìn)，將時(shí)間復(fù)雜度降低為Ο（n log n），實(shí)現(xiàn)了海量圖片的快速去重。

1.1顏色特征提取方法

顏色是圖像最直觀的特征，也是圖像視覺重要的感知特征之一。HSV（Hue， Saturation， Value）顏色模型由色度H、飽和度S、亮度V三個(gè)分量組成，和人的視覺特性比較接近，所以選擇在HSV空間提取顏色特征.為減少高維數(shù)特征對(duì)計(jì)算帶來的不便，進(jìn)行如下量化[12]：

再按式L=7H+3S+1V轉(zhuǎn)化成一維特征量。傳統(tǒng)顏色直方圖只是每種顏色的量的統(tǒng)計(jì)，忽略了圖像中每種顏色的分布方式。文獻(xiàn)[12]提出一種環(huán)形區(qū)域劃分的思想，將圖片空間劃分成M個(gè)同心圓環(huán)及外圍區(qū)域，以（C，D）為圖片幾何中心，中心圓半徑為R=[min（A，B）]/（2M），其中（A，B）為圖片邊長(zhǎng)，其他圓形半徑為MR，其中取M=2。本文同樣選擇M=2，將圖片區(qū)域被劃分為中心圓、圓環(huán)和外部3個(gè)區(qū)域。這樣既能夠不增加特征向量的維數(shù)和計(jì)算成本，同時(shí)與傳統(tǒng)顏色直方圖相比顏色空間分布信息得到充分利用。所以提取累加直方圖作為顏色特征，每個(gè)區(qū)域提取58個(gè)，共提取174個(gè)顏色特征。

1.2紋理特征及形狀特征提取方法

小波分析往往具有多尺度以及多方向性的特點(diǎn)，已經(jīng)被廣泛應(yīng)用到圖像紋理特征提取及形狀特征提取方面的應(yīng)用[13-14]。本文首先采用Mallat小波分解，得到分解層上的高頻子帶圖像能量和低頻子帶上灰度共生矩陣統(tǒng)計(jì)量作為紋理特征特征向量；同時(shí)得到分解層上的高頻子帶圖像均值、標(biāo)準(zhǔn)差和低頻子帶圖像Hu不變矩的10個(gè)相對(duì)矩作為形狀特征向量。Mallat在多分辨率分析中采用了離散框架小波變換。多次小波分解的分解系數(shù)是一組有關(guān)離散高通濾波U（n）和低通濾波G（n）的遞推關(guān)系式，其計(jì)算方式如式（4）和（5）所示：

特征提取過程如下：

1）根據(jù)Mallat分解方法，對(duì)圖片進(jìn)行4個(gè)子帶的分解。

2）繼續(xù)對(duì)低頻子圖像進(jìn)行小波變換，得到更多級(jí)別的分解子圖像。第i級(jí)別j子帶的能量表示為：

ENij=1n∑nk=1Cij（k）2（7）

其中：Cij（k）為該子帶上的小波系數(shù)；n是j子帶的小波的系數(shù)個(gè)數(shù)，將能量作為特征矩陣的元素構(gòu)造特征向量。

3）繼續(xù)對(duì)低頻子圖像進(jìn)行小波變換，對(duì)每層低頻子圖像計(jì)算Hu不變矩的10個(gè)相對(duì)矩[14]：

4）在低頻子帶上依次按照0°、45°、90°和135°方向構(gòu)造灰度共生矩陣[13]，然后分別計(jì)算熵Entropyj、二階矩ASMj、逆差矩DMj、對(duì)比度conj、相關(guān)系數(shù)corj作為特征參數(shù)，其中j=1，2，3，4，再結(jié)合之前計(jì)算出的各層子帶的能量ENj成為紋理特征向量如下：

Wi=[ENi.j.k，Entropyi.j.k，ASMi.j.k，DMi.j.k，coni.j.k，cori.j.k]

其中k表示分解層數(shù)。

1.3度量方法

1.3.1顏色特征的距離度量

本文顏色特征的距離度量采用歐氏距離法，公式如式（9）所示：

其中：xi，xj（i≠j）為圖片集中任意兩幅圖像；Eyk 、Ehk 、Ewk 分別為圖片區(qū)域的圓心、圓環(huán)和外部區(qū)域所提取的特征；k是特征分量；N為特征數(shù)目；ay，ah，aw為各區(qū)域的權(quán)重，對(duì)于一般圖片而言，圖片的中心區(qū)域信息量多，而圓環(huán)部分和外部區(qū)域的信息量較少，所以本文分別取0.5，0.3，0.2代表各區(qū)域的重要程度。

1.3.2紋理特征和形狀特征的距離度量

2并行化圖片去重算法

2.1并行化圖片去重算法

1）本文主要使用圖片固有特征實(shí)現(xiàn)達(dá)到圖片去重的目的，所以首先對(duì)圖片集{xi}提取上述特征值，設(shè)圖片集{xi}大小為n，將其分配給T個(gè)計(jì)算單元進(jìn)行處理，則時(shí)間縮短至n/T，本文中實(shí)驗(yàn)取T=4。

2）對(duì)任意圖片xi，xj（i≠j）計(jì)算距離D（xi，xj），由于重復(fù)圖片所在位置具有任意性，若要找出所有重復(fù)圖片則需要遍歷整個(gè)圖片集，計(jì)算量n2，采用并行計(jì)算則計(jì)算量為n2/T。

3）遍歷相似度距離D（xi，xj），查找其中距離為0。若為0，則說明其為相同圖片，標(biāo)記并且刪除后一張圖片，僅保留前一張。

2.2實(shí)驗(yàn)結(jié)果

由于如果圖片為重復(fù)圖片則提取特征值相等，則距離必然為0，故本文主要使用運(yùn)行時(shí)間作為衡量該算法的重要指標(biāo)，使用Matlab軟件編程實(shí)現(xiàn)對(duì)上述算法進(jìn)行評(píng)價(jià)（注：以下時(shí)間均不包含圖片特征的采集時(shí)間）。

本次實(shí)驗(yàn)選取1000及5000張圖片進(jìn)行處理，運(yùn)行時(shí)間如表1所示。

按照上述算法進(jìn)行5000張圖片去重時(shí)，處理時(shí)間就達(dá)到22min。如果按照上述算法對(duì)萬級(jí)、十萬級(jí)甚至百萬級(jí)圖片處理時(shí)程序運(yùn)行時(shí)間不可估量，本文對(duì)上述算法進(jìn)行改進(jìn)。

3改進(jìn)算法及實(shí)驗(yàn)結(jié)果

3.1算法改進(jìn)

針對(duì)上述算法主要影響運(yùn)行時(shí)間的是在去重過程要遍歷整個(gè)圖片集，計(jì)算量為n2，即便采用并行處理方式，對(duì)最終結(jié)果的影響終究有限。針對(duì)此問題，本文對(duì)第2章中的算法進(jìn)行改進(jìn)，從圖片集中任取一張圖片x0，如果存在圖片{xi，xj}（i≠j）使得D（x0，xi）=D（x0，xj），則{xi，xj}（i≠j）有可能為重復(fù)圖片，需要進(jìn)一步判斷D（xi，xj）是否為0；若不為0，則{xi，xj}（i≠j）不是重復(fù)圖片。利用這樣處理方式，在距離計(jì)算過程中計(jì)算量為n；同時(shí)在計(jì)算過程中采用并行處理，最終計(jì)算量減小為n/T，相比n2的計(jì)算量大大減小。

改進(jìn)算法具體步驟如下：

1）對(duì)圖片集提取特征值，設(shè)圖片集大小為n，將其分配給T個(gè)計(jì)算單元進(jìn)行處理，則時(shí)間縮短至n/T，本文中實(shí)驗(yàn)取T=4。

2）從圖片集中任取一張圖片x0，分別與其圖片集中其他圖片進(jìn)行距離計(jì)算，在計(jì)算過程中采用并行處理，計(jì)算量縮短為n/T。

3）對(duì)2）中計(jì)算得到的距離D（x0，xi）進(jìn)行由小到大排序，得到排序后的距離D*i（i=1，2，…，n）。本文采用快速排序法。

4）遍歷距離D*（x0，xi），查找其中相同的距離。由于在3）中已經(jīng)對(duì)距離進(jìn)行由小到大的排序，故每次只需要判斷D*i+1是否與D*i相同，若D*i+1與D*i相同則進(jìn)行第5）步，比較完畢后繼續(xù)遍歷剩下的距離，若遍歷完成且沒有相同距離則停止。

5）設(shè){xi，xj}（i≠j）使得D（x0，xi）=D（x0，xj），則計(jì)算D（xi，xj）之間的距離，若為0，則說明其為相同圖片，標(biāo)記并且刪除xj，保留xi；若大于0，則說明{xi，xj}對(duì)x0在特征上的相似程度一致，但并非相同圖片，兩張同時(shí)保留。

3.2查找重復(fù)圖片的改進(jìn)算法與第2章原算法運(yùn)行時(shí)間的對(duì)比

如果圖片量太大，第2章中對(duì)重復(fù)圖片查找算法的計(jì)算量會(huì)急劇上升，導(dǎo)致運(yùn)行時(shí)間過長(zhǎng)，故本次選用300，600及900張圖片分別用改進(jìn)方法和第2章中方法進(jìn)行重復(fù)圖片的查找，對(duì)查找時(shí)間進(jìn)行對(duì)比，如表2所示。

由表2中數(shù)據(jù)可知，采用遍歷圖片集查找重復(fù)圖片的方式運(yùn)算時(shí)間高于改進(jìn)運(yùn)算的10倍以上。同時(shí)改進(jìn)運(yùn)算在圖片數(shù)量增加時(shí)運(yùn)算時(shí)間增長(zhǎng)并不明顯，增長(zhǎng)幅度僅在百分位，說明改進(jìn)算法在海量圖片去重上是有效的。

3.3改進(jìn)算法在不同數(shù)量級(jí)與不同重復(fù)率時(shí)間對(duì)比

分別使用萬級(jí)（1萬）、十萬級(jí)（10萬）、百萬級(jí)（100萬和500萬）級(jí)圖片量進(jìn)行測(cè)試；同時(shí)每種量級(jí)的重復(fù)圖片分別占總數(shù)的30%、60%及90%，結(jié)果如表3所示。

由表3中數(shù)據(jù)可知：1）由萬級(jí)到10萬級(jí)運(yùn)行時(shí)間增長(zhǎng)在兩倍左右，而10萬級(jí)到100萬級(jí)甚至500萬級(jí)時(shí)按照本文圖片量呈現(xiàn)線性關(guān)系，運(yùn)行時(shí)間增長(zhǎng)分別在10倍及50倍左右，這是由于處理數(shù)據(jù)大量增長(zhǎng)，而實(shí)驗(yàn)用機(jī)在運(yùn)行速度和處理能力上有限，導(dǎo)致在100萬張及500萬張圖片的距離、比較等運(yùn)算時(shí)處理能力不足，所以運(yùn)行時(shí)間會(huì)呈現(xiàn)出與圖片量增長(zhǎng)倍數(shù)相同的情況，故適當(dāng)提高硬件處理能力可以減少運(yùn)行時(shí)間；2）由每種數(shù)量級(jí)不同重復(fù)率下的運(yùn)行時(shí)間來看，隨著重復(fù)率的升高運(yùn)行時(shí)間略有下降，此情況出現(xiàn)是由于排序算法導(dǎo)致，重復(fù)圖片越多，相同距離也就越多，故排序時(shí)間也就越短，所以在大數(shù)據(jù)量時(shí)選用合適的排序算法也是影響運(yùn)行時(shí)間的重要因素。

綜上所述，本文在改進(jìn)算法中，從圖片集中任取一張圖片x0，分別與其圖片集中其他圖片進(jìn)行距離的計(jì)算的方式相比遍歷圖片集計(jì)算距離的方式在運(yùn)行時(shí)間效率此處是否應(yīng)該是“運(yùn)行效率”，時(shí)間上應(yīng)該是減少，而不是提高吧？請(qǐng)明確。上提高10倍以上；同時(shí)針對(duì)不同重復(fù)率下不同數(shù)量級(jí)進(jìn)行了測(cè)試，發(fā)現(xiàn)查詢500萬數(shù)量級(jí)中重復(fù)圖片時(shí)運(yùn)算時(shí)間也僅需10min左右，去重效率大幅度提高。故本文提出的算法為大數(shù)據(jù)量的圖片快速去重工作提供了有效支撐。

4結(jié)語(yǔ)

面對(duì)目前數(shù)據(jù)的指數(shù)級(jí)增長(zhǎng)，海量數(shù)據(jù)重復(fù)刪除技術(shù)的研究在解決數(shù)據(jù)存儲(chǔ)空間消耗大、數(shù)據(jù)備份及恢復(fù)成本高等方面具有重要的意義。本文利用圖片固有屬性特征，提出了一種海量圖片快速并行化去重算法，使用該算法能夠快速準(zhǔn)確地對(duì)圖片進(jìn)行去重。實(shí)驗(yàn)結(jié)果表明，10min左右即可處理完500萬圖片集的去重工作，這為海量圖片的去重處理提供了新的思路。同時(shí)，實(shí)驗(yàn)發(fā)現(xiàn)在大數(shù)據(jù)量時(shí)，對(duì)距離進(jìn)行排序的時(shí)間對(duì)整個(gè)去重過程有一定的影響，排序時(shí)間越短，整個(gè)去重的時(shí)間也就越短，所以如何縮短排序時(shí)間作為本文將是該快速去重技術(shù)進(jìn)一步的研究方向。

參考文獻(xiàn)：

[1]

敖莉，舒繼武，李明強(qiáng).重復(fù)數(shù)據(jù)刪除技術(shù)[J].軟件學(xué)報(bào)，2010，21（5）：916-929.（AO L， SHU J W， LI M Q. Data deduplication techniques [J]. Journal of Software， 2010， 21（5）： 916-929.）

[2]

CLEMENTS A T， AHMAD I， VILAYANNUR M， et al. Decentralized deduplication in SAN cluster file systems [C]// Proceedings of the 2009 USENIX Annual Technical Conference. Berkeley， CA： USENIX Association， 2009： 101-114.

[3]

ESHGHI K， LILLIBRIDGE M， WILCOCK L， et al. Jumbo Store： providing efficient incremental upload and versioning for a utility rendering service [C]// Proceedings of the 5th USENIX Conference on File and Storage Technologies. Berkeley， CA： USENIX Association， 2007： 123-138.

[4]

HAN B， KELEHER P. Implementation and performance evaluation of fuzzy file block matching [C]// Proceedings of the 2007 USENIX Annual Technical Conference. Berkeley， CA： USENIX Association， 2007： 199-204.

[5]

張星煜，張建，辛明軍.相似性—局部性方法相關(guān)參數(shù)分析[J].計(jì)算機(jī)技術(shù)與發(fā)展，2014，24（11）：47-50.（ZHANG X Y， ZHANG J， XIN M J. Analysis of related parameters based on similaritylocality approach [J]. Computer Technology and Development， 2014， 24（11）： 47-50.）

[6]

陳芬.改進(jìn)量子粒子群算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)庫(kù)重復(fù)記錄檢測(cè)[J].計(jì)算機(jī)應(yīng)用與軟件，2014，31（3）：22-23.（CHEN F. Database duplicate records detection using neural network optimised by IQPSO. [J]. Computer Applications and Software， 2014， 31（3）： 22-23.）

[7]

梁雪，任劍鋒，景麗.基于QPSOLSSVM的數(shù)據(jù)庫(kù)相似重復(fù)記錄檢測(cè)算法[J].計(jì)算機(jī)科學(xué)，2012，39（11）：157-159.（LIANG X， REN J F， JING L. Approximate duplicate record detection algorithm based on PSO and LSSVM [J]. Computer Science， 2012， 39（11）： 157-159.）

[8]

江程，朱銳，張芳，等.一種低開銷的并行重復(fù)數(shù)據(jù)刪除算法[J].軟件導(dǎo)刊，2015，14（8）：96-99.（JIANG C， ZHU R， ZHANG F， et al. A parallel deduplication method with low overhead [J]. Software Guide， 2015，14（8）： 96-99.）

[9]

劉厚貴，邢晶，霍志剛，等.一種支持海量數(shù)據(jù)備份的可擴(kuò)展分布式重復(fù)數(shù)據(jù)刪除系統(tǒng)[J].計(jì)算機(jī)研究與發(fā)展，2013，50（z2）：64-70.（LIU H G， XING J， HUO Z G， et al. A scalable distributed data deduplication system to backup massive storage [J]. Journal of Computer Research and Development， 2013， 50（z2）： 64-70.）

[10]

曹英忠.基于Hadoop的重復(fù)數(shù)據(jù)刪除技術(shù)的研究與應(yīng)用[D].桂林：桂林理工大學(xué)，2012：46-66.（CAO Y Z. Research on the technology of data deduplication by Hadoop [D]. Guilin： Guilin University of Technology， 2012： 46-66.）

[11]

孫有軍，張大興.海量圖片文件存儲(chǔ)去重技術(shù)研究[J].計(jì)算機(jī)應(yīng)用與軟件，2014，31（4）：56-58.（SUN Y J， ZHANG D X. Research on deduplication technology for massive image file storage [J]. Computer Applications and Software， 2014， 31（4）： 56-58.）

[12]

常哲，侯榆青，李明俐，等.綜合顏色和紋理特征的圖像檢索[J].小型微型計(jì)算機(jī)系統(tǒng)，2011，32（1）：161-164.（CHANG Z， HOU Y Q， LI M L， et al. Image retrieval based on combined color with texture feature [J]. Journal of Chinese Computer Systems， 2011， 32（1）： 161-164）

[13]

費(fèi)園園，孫勁光，陶志勇.基于小波分解和灰度共生矩陣的紋理圖像檢索[J].現(xiàn)代計(jì)算機(jī)，2007（10）： 58-59.（FEI Y Y， SUN J G， TAO Z Y. Texture image retrieval based on wavelet decomposition and gray level cooccurrence matrix [J]. Modern Computer， 2007（10）： 58-59.）

[14]

夏定元，劉書學(xué)，周曼麗，等.基于小波和相對(duì)矩的形狀特征提取與檢索方法[J].計(jì)算機(jī)工程，2004，30（10）：146-147.（XIA D Y， LIU S X， ZHOU M L， et al. Method for shape feature extraction and image retrieval based on wavelet and relative moments [J]. Computer Engineering， 2004， 30（10）： 146-147.）