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

凌 曼，陳秀明，王先傳，齊保峰，劉爭(zhēng)艷

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

得到向量序列{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向量，當(dāng)k足夠大時(shí)，只有λk1a1X1為非0，其余各項(xiàng)全部接近于0。因此，Uk可以近似視為λ1所對(duì)應(yīng)的特征向量。

2 具體采用的哈希算法

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

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

2.1 預(yù)處理

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

2.2 提取視覺顯著圖

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

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

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

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

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

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

2.4 哈希相似度計(jì)算

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

3.1 魯棒性

本文選擇柯達(dá)彩色圖像庫(kù)[18]中圖像作為測(cè)試圖像，其包含人像、建筑、花卉和風(fēng)景等24幅彩色圖像。利用MATLAB、Photoshop和Stir-Mark工具對(duì)測(cè)試圖像進(jìn)行常見的數(shù)據(jù)操作，以獲得視覺相似圖像用于魯棒性測(cè)試。MATLAB提供了3×3高斯低通濾波（標(biāo)準(zhǔn)偏差范圍為0.3～1.0，步長(zhǎng)為0.1）、伽馬校正（參 數(shù) 為0.75、0.9、1.1和1.25）、椒鹽噪聲和斑點(diǎn)噪聲處理（兩個(gè)參數(shù)范圍為0.001～0.01，步長(zhǎng)為0.001）。Photoshop提供亮度和對(duì)比度調(diào)整（參數(shù)為±10和±20）。Stir-Mark提供JPEG壓縮（質(zhì)量因子范圍為30～100，步長(zhǎng)為10）、水印嵌入（強(qiáng)度范圍為10～100，步長(zhǎng)為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ù)操作，使得每幅測(cè)試圖像可以得到74幅相似圖像，因此一共得到1 776（24×74=1 776）對(duì)視覺上相似的圖像。分別提取測(cè)試圖像與其視覺相似圖像的哈希值，并計(jì)算哈希相似度，不同魯棒性攻擊的測(cè)試結(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)圖像，本文算法可以較好地識(shí)別相似的圖像，正確檢測(cè)率高說明了本文算法具有良好的魯棒性。因此，如果選擇閾值T=0.98，本文哈希算法可以抵抗大多數(shù)魯棒性攻擊。

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

3.2 唯一性

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

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

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

3.3 密鑰依賴性

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

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

3.4 算法性能比較

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

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

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

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

4 結(jié)語

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