基于改進哈希算法的圖像相似度計算

胡新榮，歐陽祥,劉軍平

(1.武漢紡織大學 數(shù)學與計算機學院，湖北 武漢 430200；2.湖北省服裝信息化工程技術(shù)研究中心，湖北 武漢 430200)

隨著網(wǎng)絡(luò)時代的快速發(fā)展，多媒體技術(shù)廣泛地應用在多種場景，導致互聯(lián)網(wǎng)上的圖像呈爆炸式增長，數(shù)量達到了上千億級。圖像是人們生活中的信息載體，如何在龐大的圖像庫中快速地、精確地完成相似圖片的檢索成為了一個熱門的課題，而針對相似圖片的檢索重要的步驟就是圖像的相似度計算。

圖像相似度的快速計算可以采用哈希算法，就是把圖像信號壓縮到一個固定長度的哈希值，對于相同內(nèi)容的圖像，其哈希值應該也是相同，即圖像哈希具有較好的唯一性[1]。一般而言，圖像哈希序列的生成主要分為圖像預處理、特征提取與哈希序列的生成這三個過程，而特征提取尤其關(guān)鍵，其魯棒性的高低對整個哈希算法有很大的影響[2]。從Schneider[3]提出第一個灰度直方圖構(gòu)成哈希的圖像認證方法開始，哈希算法被應用于圖像處理的各個領(lǐng)域；在圖像檢索中，一種新興的哈希算法是基于深度網(wǎng)絡(luò)的哈希方法，例如文獻[4-7]提出了幾種基于深度網(wǎng)絡(luò)的哈希方法，通過深度神經(jīng)網(wǎng)絡(luò)學習圖像的哈希碼。但是基于深度網(wǎng)絡(luò)的哈希方法需要大量數(shù)據(jù)集去訓練模型，整個的檢索速度慢。在非監(jiān)督學習的哈希方法中，Kozat[8]提出一種基于圖像奇異值分解(singular value decomposition,SVD)的哈希算法，將隨機組成的特征圖像進行SVD分解后得到特征矢量來構(gòu)成哈希序列，實驗表明，這種算法雖然幾何變換具有一定的穩(wěn)健性，但是有較高的誤分類概率；Lin[9]提出了一種兼容JPEG壓縮的認證方法，其利用在分塊DCT變換后，任意塊的相同位置的系數(shù)在JPEG壓縮前后保持不變的大小關(guān)系來構(gòu)成哈希，實驗結(jié)果證實了方法對JPEG圖片的穩(wěn)健性，但在分塊離散余弦變換時存在方塊效應，導致算法魯棒性不高；Qin[10]等提出基于顯著結(jié)構(gòu)特征的圖像哈希算法，利用離散余弦變換（discrete cosine transform,DCT）機制對圖像進行分解，聯(lián)合主成分分析（principal components analysis,PCA）來生成對應哈希序列，但是該算法僅利用了邊緣特征，整體的魯棒性也不高。

針對圖像處理中的噪聲影響和DCT變換中存在的方塊效應，本文提出一種基于SVD-DWT的哈希算法來計算圖像的相似度。

1 理論基礎(chǔ)

1.1 奇異值分解

矩陣A為m×n階矩陣，則可以將矩陣A分解使得：

（1）式中 A 的奇異值為σ1，σ2,…,σr，設(shè)Δr=diag（σ1，σ2,…,σr），U 為m×m階的正交陣，VT為一個n×n階的正交陣，其中，

(1)式中，矩陣U的第i列為與A相對應的奇異值的左奇異向量ui，矩陣V的第i列為與A相對應奇異值的右奇異向量，Σ為奇異值對角矩陣。則對于任意的圖像A，我們可以將A分解為：

公式（3）表明一幅圖像A可以由r幅子圖像組成，每一幅子圖像對應一個奇異值，而圖像的大部分信息都集中在前面較大的奇異值中，較小的奇異值對于整幅圖像的貢獻較小[11]，因此可以取前面較大的奇異值對應的子圖像來代替整幅圖像。

假設(shè)純凈的圖像信號為Y[n]，噪聲信號為Z[n]，則包含噪聲的圖像信號可以表示為X[n]=Y[n]+Z[n](n=0，1，2，…，K-1)，K為輸入數(shù)據(jù)的長度。其中M≥N，且M+N=K+1。首先我們要建立Hankel矩陣 P∈RM×N。

矩陣R可以表示R=S+D，其中S為不受噪聲干擾的m×n階的Hankel矩證，D為噪聲信號構(gòu)成m×n階的Hankel矩陣。然后對矩陣R進行奇異值分解，確定奇異值對角陣Σ的有效秩，即前p個最大的奇異值，然后可以得到下式：

Rp按照下式構(gòu)造不受噪聲干擾的信號分量構(gòu)成的Hankel矩陣S?。

1.2 離散小波變換

設(shè)ψ（t） ∈L2（R），其傅里葉變換為（ω），若ψ（t）滿足允許條件：

則ψ（t）稱為小波基函數(shù)，將其按照伸縮因子a和平移因子b兩個參數(shù)進行平移、伸縮后得到小波序列

(9)式中m為頻率范圍指數(shù)，n為時間步長變化指數(shù)。

圖1為離散小波分解過程，圖像每經(jīng)過稀疏變換一次，經(jīng)過不同低通濾波器h和高通濾波器g的分解，通過降采樣濾波器Q得到四個分量LL、LH、HL、HH，其中LL表示近似系數(shù)的低頻分量，LH、HL、HH表示三個高頻分量，分別為水平、垂直、對角線方向的分量，而本文中只需要得到低頻分量LL。

圖1 小波分解示意圖

圖2 DCT變換示意圖

2 改進的哈希算法

本文中提出的SVD-DWT哈希算法是一種基于頻譜的無監(jiān)督學習的哈希方法，無需大量的帶標簽的數(shù)據(jù)集，通過生成一段緊湊的二進制碼，比較其漢明距離從而得到圖片的相似度。

2.1 方塊效應

如圖2所示，在DCT處理圖像時，為保證圖像處理的速度與質(zhì)量，通常將圖像分割成不重疊的8×8大小或者16×16大小方塊，然后對每一個獨立的小方塊進行單獨編碼，然后復原，這使得每個方塊之間信號的連續(xù)性被人為分割，從而導致方塊效應，而DWT是將整張圖像進行分解得到低頻部分的圖像，再對低頻圖像進行操作，融合了整張圖片的信息，包括一些重要的邊緣信息，從而消除方塊效應。

2.2 基于SVD-DWT的圖像哈希算法

圖3表示基于SVD-DWT的圖像哈希算法的流程圖，具體步驟如下：

步驟1：對輸入圖像進行判斷，如果為灰度圖像直接進行步驟2，如果為彩色圖像則進行灰度化處理；

步驟2：利用灰度圖片構(gòu)建Hankel矩陣，利用公式（1）對矩陣進行奇異值分解，利用（3）式得到r個子圖像Ai（其中i=1，2，3，…，r），仿真過程中發(fā)現(xiàn)奇異值個數(shù)取值太小，圖片還原的清晰度差，個數(shù)取值太大會導致去噪效果不好，取60-80個奇異值去噪還原的效果最佳[13]，因此文中選取r=60，分解后得到降噪后的圖像信號

步驟3：利用公式（9）對降噪后的圖片進行第一級離散小波變換分解成四個子圖像，本文中選擇的小波基函數(shù)ψ（t）為Biorthogonal小波函數(shù)，它是一個雙正交小波函數(shù)，具備正則性，分解后的圖像保留低頻分量LL；

步驟4：將得到的低頻子圖像LL縮小為16×16大小，計算縮小后圖像的像素平均值，遍歷所有像素點的像素值，大于平均值的記為1，其他的記為0，得到256位二進制哈希碼；

步驟5：計算兩幅圖像哈希碼之間的漢明距離，由漢明距離得到兩幅圖片的相似度。漢明距離是一個概念，它是描述之間的距離D(x，y)，如下式：

圖3 基于SVD-DWT圖像哈希算法流程圖

3 實驗

3.1 評價標準

3.1.1 PSNR

假設(shè)存在兩個m×n單色圖像I和K，則有：

峰值信噪比定義為：

其中MAXI為圖像像素值的最大值，如果圖像用8位表示，值就為255。通常來說，峰值信噪比越大，去噪后圖片失真越少，質(zhì)量就越好。

3.1.2 圖片的相似性

定義兩幅圖片的相似度可以用公式（13）：

其中D(x，y)表示兩幅圖像的漢明距離，sim(x，y)∈[0，1]，表示m×n階圖片M1與圖片M2的相似度。

3.2 實驗方案

為了驗證文中提出的算法的性能，選取9張經(jīng)典的灰度圖像進行仿真實驗，圖片包括Baboon、carmeraman和lena等9幅圖片。本次實驗仿真平臺為Windows 10操作系統(tǒng)，CPU為Inter(R)Core(TM)i5-7300HQ處理器，8G內(nèi)存，仿真環(huán)境為Matlab2010a。以lena為例，圖4是經(jīng)過翻轉(zhuǎn)、模糊、旋轉(zhuǎn)、縮小尺寸等操作后的圖像。

圖4 圖像變換示例

表1 lena相似度計算結(jié)果

基于SVD哈希算法對圖像區(qū)分度太低，因此本文將與DCT哈希算法、PCA-DCT哈希算法和差值哈希三種方法進行比較，在圖片經(jīng)過旋轉(zhuǎn)、翻轉(zhuǎn)、改變亮度與對比度、模糊、改變尺寸和加入噪聲的攻擊下，通過漢明距離計算與原圖像的相似度。其中翻轉(zhuǎn)是左右翻轉(zhuǎn)，旋轉(zhuǎn)是將圖片向左旋轉(zhuǎn)10度，改變尺寸是將圖片縮小至原來圖片的四分之一，加入噪聲是在圖片中隨機加入百分之十的椒鹽噪聲和百分之十的高斯噪聲，模糊是對圖像進行高斯模糊，表1是lena圖像的實驗數(shù)據(jù)。

圖5 圖像降噪質(zhì)量

圖6 圖像相似度計算結(jié)果

3.3 實驗結(jié)果

3.3.1 降噪效果

如圖5所示，實驗圖片經(jīng)過不同方法降噪后得到的圖像的PSNR結(jié)果，經(jīng)過奇異值分解降噪后的圖片質(zhì)量比經(jīng)過均值濾波、高斯濾波、中值濾波和雙邊濾波降噪后的圖片質(zhì)量好，所以本文選擇SVD分解對圖片進行降噪處理。

3.3.2 圖像相似度計算

為了測試算法的魯棒性，本文與DCT哈希算法、PCA-DCT哈希算法和差值哈希算法進行比較，實驗結(jié)果如圖6所示，圖6（b）-圖6（f）分別對應圖像經(jīng)過翻轉(zhuǎn)、旋轉(zhuǎn)、改變對比度與亮度、加入噪聲、縮小尺寸和模糊六種攻擊，利用本文的方法計算圖片相似度相對于DCT哈希算法分別提高了9.82%，10.24%，19.77%，20.4%，5.72%和7.82%，相對于PCA-DCT哈希算法分別提高了3.9%，3.11%，11.47%，16.23%，8.46%和2.38%，差值哈希算法在圖片旋轉(zhuǎn)和翻轉(zhuǎn)的時計算圖片平均相似性度分別只有12.1%和12%，說明差值哈希算法在圖片旋轉(zhuǎn)和翻轉(zhuǎn)時魯棒性極差，本文算法在圖像改變亮度與對比度、加入噪聲、縮小尺寸和模糊的時，相對于差值哈希方法相似度分別提高了11.47%，16.23%，3.48%和7.57%。因此本文提出的算法在圖片改變亮度與對比度、圖片旋轉(zhuǎn)、圖片模糊、縮小尺寸、圖片翻轉(zhuǎn)和加入噪聲時魯棒性較高。

4 結(jié)束語

本文提出的基于SVD-DWT的哈希算法，利用SVD分解圖像，消除了噪聲對整體圖像相似度計算時的影響，通過DWT變換獲取圖像的低頻部分，低頻代表圖像的主體部分，將其用于后續(xù)的相似度計算，在圖像幾何變換和亮度改變時的實驗結(jié)果表明，文中算法魯棒性要優(yōu)于傳統(tǒng)算法。通過DWT替換DCT變換，解決了變換過程中存在的方塊效應，在圖像快速檢索方面有重要意義。但是由于文中采用的是灰度圖像，在彩色圖片轉(zhuǎn)變?yōu)榛叶葓D像的過程中不免造成信息丟失，因此，下一步的工作是改進算法，需要針對彩色圖像的變換進行研究，對算法進行改進。