基于圖論的視覺顯著模型的圖像哈希算法

凌 曼，陳秀明，王先傳，齊保峰，劉爭艷

（1.安徽工商職業(yè)學院 信息工程學院，安徽 合肥 231131；2.阜陽師范大學 計算機與信息工程學院，安徽 阜陽 236037）

圖像哈希又被稱為圖像摘要或圖像指紋，可以用一段序列表示圖像信息，它通常被用來檢測網(wǎng)絡(luò)空間中有許多熱門事件的圖像副本，還被廣泛應(yīng)用于圖像索引、圖像質(zhì)量評價、圖像檢索、圖像取證等方面。圖像哈希算法可以將任意一幅圖像映射成一串短小的字符序列或者數(shù)字。通常，圖像哈希算法需要具備兩個基本性質(zhì)：魯棒性和唯一性。魯棒性是指哈希算法需要具備抵抗圖像壓縮、圖像增強、噪聲干擾等正常數(shù)字操作的能力。這是因為經(jīng)歷這些操作后的圖像，其視覺內(nèi)容與原圖像基本一致，圖像哈希應(yīng)該基本相同。唯一性是指，對于視覺內(nèi)容差異較大或者完全不同的圖像，用哈希算法計算得到的哈希值應(yīng)完全不同，良好的唯一性意味著將不同圖像判斷為相似圖像的錯誤率較低。一個高性能的算法應(yīng)該在魯棒性和唯一性之間達到很好的平衡。近年來，學者們提出并研究了許多哈希算法來提高圖像的魯棒性和唯一性。Tang[1]等提出了一種基于光譜殘差（SR）模型和低秩表示（LRR）相結(jié)合的圖像哈希算法，該算法對大角度旋轉(zhuǎn)具有較好的魯棒性，但是唯一性有待提高。He[2]等提出了一種無監(jiān)督雙向離散矩陣分解哈希算法（BDMFH），其具有良好的魯棒性和快速的計算速度。Zhou[3]等提出了一種基于深度森林的哈希學習方法，通過多粒度掃描和級聯(lián)森林生成一個深層森林集成分類器來逐層處理數(shù)據(jù)，以實現(xiàn)高效的圖像檢索。但是對于較長二進制碼的處理，其性能有待提高。Qin[4]等提出了一種基于紋理和結(jié)構(gòu)特征相結(jié)合的圖像哈希算法，該算法具有較好的穩(wěn)健性，但是在唯一性方面有待提高。凌曼[5]等提出了基于Itti視覺顯著模型和LLE的圖像哈希算法，該算法在魯棒性和唯一性之間可以達到良好的平衡。Tang[6]等利用隨機Gabor濾波器和DWT提取圖像特征的哈希算法，該算法的分類性能較好且運算速度也比常見DWT的哈希算法快。Shen和Zhao[7]提出了一種基于局部和全局特征的圖像哈希算法，其利用中心對稱局部二值模式（CS-LBP）提取圖像特征，具有較好的魯棒性。Yuan和Zhao[8]提出了一種結(jié)合三維全局特征和局部能量特征的哈希算法，其利用不同三維視角下圖像各層統(tǒng)計特征之間的關(guān)系生成全局特征哈希，該算法不僅提高了哈希算法的分類性能還加快了運算效率。張春艷[9]等設(shè)計了一種基于DWT和感知哈希的檢索方案。該方案利用Henon映射對圖像進行頻域加密運算，然后對醫(yī)學密文圖像進行DWT并生成逼近原圖的子圖，通過比較DCT系數(shù)與系數(shù)均值的關(guān)系得到圖像的感知哈希序列。該算法對于常規(guī)的幾何攻擊具有良好的魯棒性，但是其運行速度和唯一性有待提高。

從上面的綜述可以發(fā)現(xiàn)，大多數(shù)算法在魯棒性和唯一性之間沒有達到很好的平衡。針對這個問題，本文提出了一種基于圖論的視覺顯著（GBVS）模型的圖像哈希算法，該算法的主要貢獻如下。

（1）利用GBVS模型提取的顯著性圖來計算預處理圖像的視覺表示。由于顯著性圖可以表示人類的視覺注意，使用顯著性圖的視覺表示可以有效地描述圖像的顯著區(qū)域，在計算效率和檢測性能方面有較好的優(yōu)勢，所以具有可視化表示的哈希生成可以提高算法的魯棒性。

（2）通過對中間哈希進行數(shù)據(jù)加密，由混沌函數(shù)隨機生成序列，使得最終哈希具有安全性。

1 相關(guān)工作

1.1 基于圖論的視覺顯著（GBVS）模型

GBVS模型是Harel[10]等提出的一種新的自底向上的視覺顯著性模型，是在經(jīng)典的Itti模型[11]基礎(chǔ)之上，運用馬爾科夫隨機場的特點構(gòu)建二維圖像，并對二維圖像的馬爾科夫鏈求平衡分布后得到的顯著圖，GBVS模型具有較好的顯著性檢測效果。GBVS模型[12-14]的基本思想是：圖像的顯著性體現(xiàn)在特征圖中，若能有效地生成特征圖，則可以得到效果較好的顯著圖。GBVS模型生成顯著圖的方法與Itti模型相似，圖像提取三個底層特征的方法也相同，特征圖的融合也相同。不同的是GBVS特征圖是通過先構(gòu)造馬爾可夫矩陣，然后用冪法計算其最大譜對應(yīng)的特征向量，最后利用圖譜的方法來生成圖，并且僅采用了Itti的前四層高斯金字塔分解圖，即σ=[0,1,2,3]。本文只介紹GBVS模型與Itti模型不同之處，相同之處就不在此贅述。

1.2 構(gòu)造馬爾科夫矩陣

假設(shè)M用來表示原始圖像的灰度，圖像中兩個不同像素點的坐標位置分別用(i,j)和(p,q)來表示，M(i,j)代表(i,j)坐標位置的像素點灰度值，M(p,q)代表(p,q)坐標位置像素點的灰度值，則M(i,j)和M(p,q)之間的差異性定義為

把M的像素點看作圖GM的結(jié)點，利用公式（2）構(gòu)造權(quán)重矩陣來作為圖GM的鄰接矩陣，它可反映其它結(jié)點與GM中任意結(jié)點的聯(lián)系。

其中，σ為常數(shù)，一般取值是圖像寬度的1/10到1/5，在此區(qū)間取值對輸出結(jié)果影響較小。如式（2）所示，結(jié)點(i,j)與(p,q)連接成邊的權(quán)重與結(jié)點之間的差異對比性及相隔距離成正比。相反方向則擁有同樣的權(quán)重：

其中，GM是一個無向圖。將構(gòu)造出的權(quán)重矩陣按列進行歸一化后得到的矩陣稱之為馬爾可夫矩陣，該矩陣可以充分反映每個像素點與其周邊像素點間的差異對比性。

1.3 計算最大譜對應(yīng)的特征向量

GBVS是通過冪法來計算最大譜對應(yīng)的特征向量。假設(shè)M有X1,X2,X3,…,Xn個線性無關(guān)的特征向量，對應(yīng)的特征值為λ1,λ2,λ3,…,λn，且

設(shè)U0為任取一非0向量，并且與M進行迭代，

得到向量序列{Uk}，k=1,2,3…。

由于X1,X2,X3,…,Xn是線性無關(guān)的特征向量，則n維非0向量U0可線性表示為

則有

并且|λ2/λ1|≤1,|λ3/λ1|≤1,|λ4/λ1|≤1,…,|λn/λ1|≤1，且a1≠0，Uk≈λk1a1X1是非0向量，當k足夠大時，只有λk1a1X1為非0，其余各項全部接近于0。因此，Uk可以近似視為λ1所對應(yīng)的特征向量。

2 具體采用的哈希算法

基于圖論的視覺顯著模型的圖像哈希算法主要可分為三個步驟（圖1）：第一步，首先對輸入的圖像進行預處理，目的是建立規(guī)范化圖像；第二步，利用GBVS模型提取圖像的視覺顯示圖，并壓縮量化成中間哈希；最后，對中間哈希進行數(shù)據(jù)加密以得到最終的哈希值。

圖1 本文所提的哈希算法示意圖

2.1 預處理

預處理的主要操作就是通過雙線性插值[15]將輸入的圖像轉(zhuǎn)換為相同尺寸。通過該操作可以對圖像邊緣進行柔化處理，使圖像邊緣更加平滑，確保所提的哈希算法能夠抵抗較小的圖像縮放，并且可以使輸入的不同圖像的哈希長度相同。

2.2 提取視覺顯著圖

在預處理生成規(guī)格化圖像后，運用GBVS模型計算圖像的視覺顯著區(qū)域，并將提取出的視覺顯著圖記為J。具體步驟如下：首先，將輸入的歸一化圖像表示為無向完全圖，并將圖的節(jié)點視為像素。然后，計算任意兩個像素之間的差值與比率，且作為其對應(yīng)結(jié)點連接邊的權(quán)重；接著，通過隨機游走算法[16]將訪問頻率較低的結(jié)點找出，并給其對應(yīng)像素賦予較大的顯著值。由于在隨機游走過程中，圖像中顯著性較大的像素點與其他像素差異對比度較大，因此被訪頻率很低，這使得GBVS能夠從全局的角度來很好地定位顯著目標物對象。圖2是一幅彩色圖像及其視覺顯著圖。

圖2 彩色圖像及其視覺顯著圖。（a）原圖像；（b）GBVS視覺顯著圖

為了得到較短的中間哈希序列，對上文提取的視覺顯著圖J進行非重疊分塊，分塊大小為m×m，其中m可以被M整除，即n=M/m，于是得到n×n個圖像塊，同時，計算每個圖像塊的均值，并用該均值表示原圖像塊，因此可得到大小為n×n的均值圖像L。通過串聯(lián)圖像L上所有均值，于是得到一個包含n2個元素的序列V=[V(1),V(2),V(3),…,V(n2)]。

2.3 數(shù)據(jù)加密

從圖像的安全應(yīng)用考慮，圖像哈希算法需要由密鑰控制，使其具備安全性能。因此，在設(shè)計哈希算法時通常會引入密鑰，由密鑰去控制哈希序列的生成。換言之，對于給定的一幅圖像，使用不同的密鑰去提取哈希序列，所產(chǎn)生的哈希序列也應(yīng)該不同。對于有密鑰控制的圖像哈希函數(shù)，只有密鑰的所有者才能正確提取哈希值。為了生成安全的圖像特征，本文用Logistic混沌映射[17]對中間哈希序列V進行加密處理，并生成最終的圖像哈希H。Logistic混沌映射公式如下，

其中，u是Logistic參數(shù)，0≤xi≤1，0≤u≤4。研究表明，當xi∈[0,1]時，Logistic映射處于混沌狀態(tài)，實際中可將初值x0設(shè)為密鑰。本文通過Logistic混沌公式迭代生成n2個隨機數(shù)，將這些數(shù)依次進行排序，最后對照隨機數(shù)確定排序前后的位置關(guān)系，將中間哈希V的元素重新排列，得到最終的圖像哈希H，從而實現(xiàn)數(shù)據(jù)加密。

2.4 哈希相似度計算

設(shè)H1=[H1(1),H1(2),H1(3),…,H1(n2)]和H2=[H2(1),H2(2),H2(3),…,H2(n2)]分別是兩幅圖像的哈希序列，采用相關(guān)系數(shù)來測量它們的相似度。計算公式如下，

其中，a1和a2分別為H1和H2的均值，H1(l)和H2(l)分別為H1和H2的第l個元素，Δs是一個接近于0的正常數(shù)。相關(guān)系數(shù)的取值范圍為[-1,1]，通常相關(guān)系數(shù)越大，哈希序列越相似。如果ρ

3 實驗結(jié)果及分析

實驗圖像尺寸為512×512，非重疊圖像塊的大小為64×64，Logistic混沌映射生成的隨機數(shù)共64個，圖像哈希序列為64個整數(shù)。下面分別討論算法的魯棒性、唯一性、密鑰依賴性性及相關(guān)性能。

3.1 魯棒性

本文選擇柯達彩色圖像庫[18]中圖像作為測試圖像，其包含人像、建筑、花卉和風景等24幅彩色圖像。利用MATLAB、Photoshop和Stir-Mark工具對測試圖像進行常見的數(shù)據(jù)操作，以獲得視覺相似圖像用于魯棒性測試。MATLAB提供了3×3高斯低通濾波（標準偏差范圍為0.3～1.0，步長為0.1）、伽馬校正（參 數(shù) 為0.75、0.9、1.1和1.25）、椒鹽噪聲和斑點噪聲處理（兩個參數(shù)范圍為0.001～0.01，步長為0.001）。Photoshop提供亮度和對比度調(diào)整（參數(shù)為±10和±20）。Stir-Mark提供JPEG壓縮（質(zhì)量因子范圍為30～100，步長為10）、水印嵌入（強度范圍為10～100，步長為10）、圖像縮放（縮放比為0.5、0.75、0.9、1.1、1.5和2.0）和圖像旋轉(zhuǎn)（旋轉(zhuǎn)角度為±1、±2、±3、±4、±5）。值得注意的是，圖像旋轉(zhuǎn)將增加圖像大小，并將一些填充像素添加到旋轉(zhuǎn)圖像中。通過這些常見數(shù)據(jù)操作，使得每幅測試圖像可以得到74幅相似圖像，因此一共得到1 776（24×74=1 776）對視覺上相似的圖像。分別提取測試圖像與其視覺相似圖像的哈希值，并計算哈希相似度，不同魯棒性攻擊的測試結(jié)果如圖3所示。其中x軸是不同操作的參數(shù)，y軸是相關(guān)系數(shù)。圖3中曲線是24幅彩色圖像及其類似圖像的哈希相關(guān)系數(shù)的平均值?？梢钥闯?，除了旋轉(zhuǎn)、裁剪和縮放，大多數(shù)數(shù)據(jù)操作相關(guān)系數(shù)均大于0.98。通常相關(guān)系數(shù)越大，哈希序列越相似。如果沒有旋轉(zhuǎn)圖像，本文算法可以較好地識別相似的圖像，正確檢測率高說明了本文算法具有良好的魯棒性。因此，如果選擇閾值T=0.98，本文哈希算法可以抵抗大多數(shù)魯棒性攻擊。

圖3 不同魯棒性攻擊的測試結(jié)果

3.2 唯一性

選用UCID[19]來測試本文算法的唯一性，該數(shù)據(jù)集包含1 338幅真彩色圖像。將本文算法應(yīng)用于該數(shù)據(jù)集，提取1 338個圖像哈希序列，再計算兩兩圖像哈希序列間的相似度，可得到894 453（1 338×（1 338-1）/2=894 453）個距離，這些相關(guān)系數(shù)分布結(jié)果如圖4所示。從圖可知，最大相關(guān)系數(shù)為0.998 3，最小相關(guān)系數(shù)為-0.238 2，均值為0.822 3，標準差為0.132 6。同時，大多數(shù)相關(guān)系數(shù)都小于上述閾值T=0.98，唯一性表現(xiàn)良好，本文算法能夠較好地區(qū)分不同圖像。實際上，唯一性和魯棒性與閾值的選取密切相關(guān)，不同的閾值將導致不同的性能。

對比分析發(fā)現(xiàn)，如果選擇閾值T=0.98，此時有0.79%的不同圖像被誤判成相同圖像；若閾值選擇T=0.95，則有9.28%的不同圖像被誤判成相同圖像，降低了算法的唯一性和魯棒性。因此，可以選擇T=0.98作為閾值，可以使總錯誤率較小。將圖4中大于0.98的相關(guān)系數(shù)取出，并除以總的相關(guān)系數(shù)，再乘以100%，可得到不同圖像被誤判成相似圖像的比率。

圖4 不同圖像間哈希距離分布

3.3 密鑰依賴性

為了測試本文算法的安全性，仍然選擇柯達圖像數(shù)據(jù)庫中的圖像作為測試圖像，用不同的密鑰來生成同一幅測試圖像的哈希值，并計算其在不同密鑰下哈希序列的相關(guān)系數(shù)，結(jié)果發(fā)現(xiàn)所有相關(guān)系數(shù)取值都較小，則同一幅圖像由于密鑰的不同而被判斷成不同圖像，這說明哈希依賴于密鑰。下面列舉一個典型示例進行說明。首先，使用一組密鑰提取測試圖像的圖像哈希。其次，利用另外100組不同的密鑰生成同一圖像的哈希。在實驗中，僅更改密鑰，其他參數(shù)保持不變。圖5顯示了由不同密鑰控制的哈希間相關(guān)系數(shù)，可以看出，最大相關(guān)系數(shù)是0.4，遠小于閾值T=0.98，說明哈希依賴于密鑰，即本文的圖像哈希算法具有較好的密鑰依賴性。

圖5 不同密鑰的哈希序列間相關(guān)系數(shù)

3.4 算法性能比較

為了驗證哈希算法的優(yōu)越性，將本文算法與一些文獻的圖像哈希算法進行比較。選擇的對比算法有基于視覺模型的低秩圖像哈希算法[1]（Sr-Lrr）、基于視覺顯著模型和局部線性嵌入的圖像哈希算法[5]（Itti-Lle）和基于混合特征的哈希算法[4]（Hybrid feature）。數(shù)據(jù)集采用3.1和3.2節(jié)的測試圖像庫，圖像大小調(diào)整為512×512，其他參數(shù)設(shè)置不變。同時，對比算法的哈希相似測度仍然保持與原論文一致，即Sr-Lrr、Itti-Lle和Hybrid feature采用L2范數(shù)。為了直觀地比較算法性能，采用接收機操作特性[20]（ROC）曲線來分析本文算法和對比算法的分類性能，并計算正確率PTPR和誤判率PFPR。

其中，n1是相似圖像的正確判斷數(shù)，N1是相似圖像的總數(shù)；n2是不同圖像的誤判數(shù)，N2是不同圖像的總對數(shù)。PTPR和PFPR分別描述唯一性和魯棒性，PFPR越小，唯一性越好；PTPR越大，魯棒性越好。因此，在ROC曲線圖中，靠近左上角的ROC曲線優(yōu)于距離左上角較遠的曲線，其算法的整體分類性能越好。圖6對比了各種哈希算法的ROC曲線，其中，本文哈希算法的曲線最靠近左上角，其他對比算法的ROC曲線均在其下方，說明本文哈希算法優(yōu)于Sr-Lrr、Itti-Lle和Hybrid feature算法。

圖6 不同哈希算法的ROC曲線

實際上，本文算法之所以優(yōu)于其他三種算法，主要歸功于精心的設(shè)計步驟和合適的相似性度量。通過GBVS模型求解馬爾可夫鏈的平穩(wěn)分布且對圖像進行顯著性檢測，對具有復雜背景的圖像有很好的適應(yīng)性，提升了算法的魯棒性。同時，文獻[12]對多種顯著性算法的優(yōu)劣進行了評價，結(jié)果表明，GBVS模型在背景復雜、目標結(jié)構(gòu)清晰的圖像中比Sr模型和Itti模型更具優(yōu)勢。而Hybrid feature算法通過提取紋理和結(jié)構(gòu)這兩類特征后，再進行降維來生成圖像哈希，會失去某些局部信息，從而導致唯一性降低。

4 結(jié)語

本文提出了基于圖論視覺顯著模型的圖像哈希算法，使魯棒性和唯一性之間達到了較好的平衡。該算法的主要貢獻是利用GBVS模型提取的顯著性圖來突出顯著區(qū)域，提高了算法的魯棒性；再通過Logistic混沌映射生成位置映射數(shù)組，并對該數(shù)組進行數(shù)據(jù)加密以得到最終的哈希值，從而確保哈希算法具有安全性。通過驗證，本文算法具有較好的魯棒性與唯一性。同時，ROC曲線也表明，該哈希算法優(yōu)于Sr-Lrr、Itti-Lle和Hybrid feature算法。在接下來的工作中，可將深度學習算法引入到哈希算法中并擴大數(shù)據(jù)集驗證。