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

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

　　0引言

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

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

　　1.1顏色特征提取方法

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

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

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

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

　　特征提取過(guò)程如下：

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

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

　　ENij=1n∑nk=1Cij(k)2(7)

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

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

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

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

　　其中k表示分解層數。

　　1.3度量方法

　　1.3.1顏色特征的距離度量

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

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

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

　　2并行化圖片去重算法

　　2.1并行化圖片去重算法

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

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

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

　　2.2實(shí)驗結果

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

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

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

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

　　3.1算法改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　4結語(yǔ)

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

【海量圖片快速去重技術(shù)論文】相關(guān)文章：

快與慢議論文11-28

快與慢議論文01-18

描寫(xiě)快與慢的議論文01-29

高中快與慢議論文10-28

高中快與慢的議論文11-07

議論文作文：快與慢01-27

快與慢優(yōu)秀議論文01-27

關(guān)于快與慢的議論文01-22

快與慢議論文（精選41篇）03-30

快與慢議論文(15篇)12-31