基于分塊DCT的圖像去重算法

江小平，胡雪晴，孫 婧，李成華

(中南民族大學 電子信息工程學院，智能無線通信湖北省重點實驗室，武漢 430074)

隨著人類信息數(shù)據(jù)規(guī)模的急劇膨脹，互聯(lián)網(wǎng)中企業(yè)與個人累積的數(shù)據(jù)內容也在無限增長，其中很大部分是多媒體數(shù)據(jù)，尤其是圖像數(shù)據(jù).云端圖像數(shù)據(jù)存在大量冗余的相似圖像，包括完全重復的相同圖像和同源圖像的修改副本，后者在編碼數(shù)據(jù)上完全不同，但是具有相似的視覺感知內容.相似圖像經(jīng)客戶端上傳到云端，浪費了大量的帶寬和存儲空間，如何高效準確地去重相似圖像成為云存儲領域中亟待解決的問題[1,2].

目前采用的圖像去重方法多為文件級別去重，把圖像作為二進制文件，通過傳統(tǒng)哈希如MD5等方法對圖片去重[3].如sis等系統(tǒng)中采用的文件級去重，利用文件哈希算法計算圖片文件的哈希值，以哈希值作為判重標準.Zeng等[4]采用塊級數(shù)據(jù)去重算法，先把圖像文件分成固定大小的塊，通過哈希算法計算每塊的哈希值，再進行分塊間的比較.文獻[5]提出了一種基于分布式數(shù)據(jù)庫/文件系統(tǒng)的圖像文件去重辦法，該算法截取圖像文件二進制流的開頭128位、末尾 128位和FML偏移開始128位，將這三段二進制流分別進行MD5碼簽名，并再次簽名獲得該文件最終的 MD5碼簽名，以該數(shù)據(jù)作為判斷圖像重復的標準.文獻[6]提出針對上述算法的去重模型.以上方法均將圖像作為二進制文件，采用傳統(tǒng)哈希以二進制文件的標準進行判定去重，僅具有數(shù)據(jù)壓縮性，不能消除多媒體感知內容上的冗余，計算復雜、開銷大.對于圖像來說，典型的修改如尺寸變換和壓縮只改變它們的二進制表示，人類視覺感知上不變，應作為重復圖像刪除.這些感知相似的圖像在遠程服務器上占據(jù)很大的存儲空間，大大影響了重復數(shù)據(jù)刪除系統(tǒng)的效率.針對相似圖像的去重，提出了感知哈希的概念[7,8]. Li等[9]采用圖像均值感知哈希AVG-hash算法，在像素域得到圖像的哈希值，并利用漢明距離判斷兩幅圖像感知哈希序列的距離，不僅可減少計開銷，在設定的閾值范圍內，還可識別感知相似的圖像，消除感知冗余，實現(xiàn)相似去重；但該算法并不能識別經(jīng)過JPEG壓縮對比度變化的圖像改變.文獻[10,11]提出一種基于離散余弦變換的感知哈希算法的DCT-hash，通過提取頻域中特定系數(shù)生成的圖像哈希作為去重判斷.文獻[12]在文獻[10]的基礎上提出了DAN-hash算法，對DCT-hash算法進行優(yōu)化，提高了該算法的準確率和去重率.

本文針對相似圖像去重，提出了一種基于分塊DCT變換的新型感知哈希算法BDCT-hash，經(jīng)實驗驗證該算法具有更高的去重率.并針對目前主流的JPEG圖像標準，進一步優(yōu)化圖像去重方案，采用直接從JPEG圖像格式壓縮碼流中提取需要的系數(shù)的策略，大大提高了圖像去重的效率.

1 感知哈希去重算法

本算法中通過把圖像進行分塊DCT變換，提取變換后的重要系數(shù)，并對系數(shù)進一步處理生成圖像的感知哈希序列BDCT-hash，用來代表每一幅圖像.并用任意兩幅圖像BDCT-hash序列的漢明距離判斷兩幅圖像間的距離.

1.1 生成感知哈希序列

生成感知哈希序列包括兩個步驟，一是進行圖像預處理，二是提取圖像特征向量.

第一步：圖像預處理.

1)彩色圖像灰度化，本文僅考慮灰度情況下的圖片，降低了亮度對圖像分析的影響，彩色圖像首先通過RGB轉化為灰度圖像.使用下列公式將圖像轉換為灰度形式：

Gray=R×0.299+G×0.587+B×0.114.

(1)

2)統(tǒng)一圖像大小，對圖像進行雙線性插值，使分辨率統(tǒng)一為64×64，以保證生成的感知哈希序列長度一致.

第二步：提取圖像特征向量.

1)將預處理后的圖像分成64個8×8的塊，通過分塊DCT變換，得到每個分塊的DCT系數(shù)矩陣.

2)分別取每個塊的DC分量以及按照zigbig掃描的AC1和AC5分量，將相同位置的分量按照從左至右從上至下的順序連接起來組成三個長度為64的一維向量Ai.

3)將三組向量分別進行二值化處理得到Fi.

(2)

4)依次連接Fi，生成長度為192的一維特征向量F.

特征向量F即為圖像經(jīng)過BDCT-hash得到的感知哈希序列值.

1.2 相似性度量

采用漢明距離作為比較兩個感知哈希序列值之間相似性的一種度量.

設x={x1,x2,…，xN},y={y1,y2,…，yN},表示兩個有限長字符串.x,y之間的漢明距離D(x,y)被定義為：

(3)

這里Q(xi,yi)是一個函數(shù)，當x和y不同時值為1，相同時等于0.為便于比較，漢明距離可以相對于字符串的長度n進行歸一化，歸一化漢明距離定義為：

(4)

特別地，二進制編碼的數(shù)字之間的漢明距離可使用XOR運算來計算.

(3)

兩個字符串之間的漢明距離可被用來確定其相似性.若漢明距離越大，字符串就越不一樣.為了識別類似的字符串，通常為漢明距離設置一個閾值T,D(x,y)≤T時，x,y被識別為相似的字符串，認為兩個感知哈希序列字符串代表的圖像為相似圖像；D(x,y)>T時，x,y被識別為不同的字符串，認為兩個感知哈希序列字符串代表的圖像為不同圖像.

2 基于JPEG壓縮的圖像去重

JPEG(聯(lián)合圖像專家小組)由ITU, ISO, IEC共同努力制訂，是第一個國際圖像壓縮標準.由于它具有良好的壓縮性能、重建質量、可調節(jié)的壓縮比等優(yōu)勢，在圖像、視頻等領域被廣泛應用，目前互聯(lián)網(wǎng)中絕大部分圖像采用了JPEG壓縮標準.因此在處理云端圖像去重這一問題上，如何對JPEG圖像進行準確高效的去重極為重要.本文針對JPEG圖像對感知哈希算法進行改進，其整體的框架見圖1.

圖1 基于JPEG壓縮的相似圖像去重框架Fig.1 Similar imagedeweighting frames based on JPEG compression

基于JPEG圖像的相似去重主要包括兩個部分.

(1)感知哈希的構造過程.在實際去重過程中采用直接從JPEG圖像格式壓縮碼流中提取需要的系數(shù)的方法，在BDCT-hash算法的基礎上，大大提高了圖像去重的效率.將標準化后的JPEG圖像碼流直接進行熵解碼，利用JPEGlib庫提取JPEG熵解碼碼流后Y分量的DC,AC1,AC5系數(shù)，再將系數(shù)二值化重組成為哈希序列值.

(2)相似圖像檢測過程.首先計算現(xiàn)有JPEG圖像的感知哈希序列存儲在哈希序列庫中.當有待檢測圖像傳來時，計算待檢測圖像的感知哈希序列.通過相似性度量，若計算所得的漢明距離大于設定的閾值，檢測結果顯示云端不存在相似圖像；反之則結果顯示已存在相似圖像.

3 實驗分析

用提出的算法BDCT-hash和文獻[9]中的像素域平均值感知哈希算法AVG-hash，文獻[10]中基于DCT變化的全局頻率感知哈希算法DCT-hash和文獻[12]中改進的頻率感知哈希算法DAN-hash進行對比.分別分析其在不同失真情況下的穩(wěn)健性以及大量數(shù)據(jù)環(huán)境下的去重率、錯判率.

采用與文獻[12]相同的圖像庫，包括TID2013, CSIQ, lena, peppers等7張圖像在內的圖像處理標準圖集合.TID2013建立在TID2008的基礎上，圖像庫包括25張參考原圖及3000幅失真圖像，共有24種常見的失真類型.CSIQ由美國俄克拉何馬州立大學建立，包含30幅參考圖像，866幅失真圖像，失真類型包括JPEG壓縮，JPEG2000壓縮，對比度變化，高斯粉紅噪聲添加，高斯白噪聲添加以及高斯相似.

3.1 BDCT-hash算法的穩(wěn)健性

TID2013圖像庫中包含25幅參考圖像，每種圖像有24種失真類型，5種不同程度的失真水平.我們選取其中10種典型的失真，分析4種算法在不同失真情況下的表現(xiàn).分別計算每種算法下25幅參考圖像與其對應10種失真類型，5種失真程度的感知哈希序列，每種算法均得到1275個感知哈希序列.然后計算每種算法下，失真圖像與相應參考圖像的漢明距離，共得到1250個距離，每種失真類型有125個漢明距離.表1中數(shù)據(jù)顯示的為4種算法在10種不同失真情況下，失真圖像與參考圖像漢明距離的平均值.

表1 4種算法在10種失真下平均漢明距離值對比Tab.1 Comparison of average Hamming distance values of four algorithms under 10 kinds of distortion

由上文可知：感知哈希序列相似度由漢明距離來判定；漢明距離越小，兩個序列值越相近.因此，兩幅相似圖像的漢明距離越小越好，保證了在相同閾值情況下識別的準確率.在相同相似圖像情況下，漢明距離越小，表明該算法的穩(wěn)健性越強.從宏觀數(shù)據(jù)分析該算法的識別率和誤判率結果見圖2.由圖2可見：10種失真情況下，除圖像JPEG2000壓縮變換(4和6)中該算法的漢明距離平均值略大于其余3種算法；其他失真情況下，該算法的漢明距離平均值均明顯小于其他3種算法.因此，該算法具有很好的穩(wěn)健性.

1) Additive Guassian noise; 2) Noise in color comp.; 3) JEPG compression; 4) JPEG2000 compression; 5) JPEG transm. errors;6) JPEG2000 transm. errors; 7) Mean shift; 8) Contrast change; 9) Color saturation; 10) Chromatic aberrations圖2 4種算法在10種失真下平均漢明距離值對比Fig.2 Comparison of average Hamming distance values of four algorithms under 10 kinds of distortion

3.2 去重率分析

去重率是指在給定閾值T的情況下，算法可識別相似圖像的正確率.實驗分別統(tǒng)計了BDCT-hash，AVG-hash，識別率，實驗共3866幅圖像.每個算法產(chǎn)生3866個漢明距離，分別計算了4種算法所得漢明距離在閾值范圍內的漢明距離數(shù)量，以及該數(shù)量占該算法所有漢明距離的比例，得正確識別率.在閾值分別選擇T=1,T=5時相似圖像的正確識別率結果如表2.

表2 4種算法在TID2013,CSIQ圖像庫中去重率的對比Tab.2 Comparison of four algorithms in TID2013 and CSIQ image library

由表2可知：T=1時，本算法的正確識別率高達99.83%，而AVG-hash，DAN-hash，DCT-hash的識別率依次遞減；當T=5時，本算法的正確識別率高達95.36%，而AVG-hash，DAN-hash，DCT-hash三種算法的正確識別率均僅為約80%，.故所提出的BDCT-hash具有高度的穩(wěn)健性，可準確識別相似圖像，大大提高了相似圖像的識別率和相似圖像識別算法的準確性.

3.3 錯判率分析

感知哈希算法要求在正確識別相似圖像的同時，嚴格區(qū)分不同源圖像，即不同源圖像不可被識別為相似圖像.分析4種算法的錯判率，每種算法分別在TID2013中的3000張失真圖片與7張標準圖像的一一對應碰撞性實驗后得到21000組漢明距離，用TID2013中25張原圖與CSIQ中866張失真圖像一一對應實驗后得到21650組漢明距離.用其中漢明距離小于閾值的數(shù)量除以總數(shù)據(jù)量得到錯判的比例.在閾值分別選擇T=1,T=5時，4種算法的錯判率結果見表3.由表3可知：在有限大量數(shù)據(jù)量情況下，本算法的錯判率幾乎為0，相比于其他的算法，本算法具有明顯的優(yōu)勢，故該算法大大提高了相似圖像識別的準確率.

表3 4種算法在TID2013, CSIQ圖像庫中錯判率的對比

Tab.3 Comparison between four algorithms in TID2013 and CSIQ image database

給定閾值錯判率/%BDCT-hashDAN-hashDCT-hashAVG-hashT=1000.0360.04T=500.0060.8100.97

3.4 序列長度分析

算法生成的序列長度由提取的分量數(shù)和圖片的分塊數(shù)決定，統(tǒng)一圖像尺寸64×64，采用8×8的分塊，每塊提取量化后的DC和兩個AC系數(shù).故感知哈希序列長度為192.同時經(jīng)二值化的感知哈希序列每位可用一個二進制表示，最后生成的感知哈希序列長度為192 bit.

4 結語

圖像數(shù)據(jù)是當今互聯(lián)網(wǎng)數(shù)據(jù)中的重要組成部分，它在存儲和傳播中產(chǎn)生了大量冗余，本文在現(xiàn)有的感知哈希算法基礎上提出了基于分塊DCT的感知哈希算法BDCT-hash.同時，針對現(xiàn)流行的JPEG圖像壓縮標準，提出了針對JPEG壓縮的圖像去重方案.經(jīng)實驗驗證，該方案具有較高的穩(wěn)健性和準確率.該算法也可作為提取特殊幀特征值的方法，針對視頻數(shù)據(jù)存在的冗余，未來應用于視頻去重領域.