基于超像素分割與三維空間的圖像哈希

劉 帥，趙 琰

(上海電力大學電子與信息工程學院，上海200120)

1 引言

科技的發(fā)展日新月異，人們使用計算機和手機等工具均可很方便地對圖像進行編輯處理，如圖像縮放，亮度調(diào)整，改變對比度等。但是這也帶來圖像分類，檢索等方面的問題。因此，研究者提出用圖像哈希解決這一類問題。圖像哈希指的是將圖像單向映射為一串短小的數(shù)字序列，該數(shù)字序列可以是二進制數(shù)或者是十進制數(shù)，通過比較圖像之間的哈希序列，可以有效地對圖像進行分類，檢索。圖像哈希具有魯棒性、區(qū)別性、安全性。魯棒性是指原始圖像經(jīng)過保持數(shù)字內(nèi)容的處理后生成的哈希序列應(yīng)與原圖像的哈希序列相同或者相似。區(qū)別性是指不同圖像之間的哈希序列應(yīng)有明顯的不同，就是說不同圖像的哈希序列的相似概率很小。安全性是指攻擊者在不知道密鑰的情況下無法生成正確的哈希序列。因此，圖像哈希可應(yīng)用于圖像檢索、圖像取證和圖像分類等方面。

近年來，不同的學者利用多種技術(shù)提出不同的哈希算法，其中按照數(shù)字圖像處理方式可劃分為基于圖像變換和基于數(shù)據(jù)降維的方法：

1)基于圖像變換的方法：文獻[1]中Tang等人提出利用多維尺度分析MDS(Multidimensional scaling)構(gòu)建圖像哈希。該算法可以抵抗旋轉(zhuǎn)攻擊，不過效率還有提高的空間。文獻[2]中Qin等人提出了一種基于顯著性結(jié)構(gòu)特征的圖像哈希方案，該方案具有較好的魯棒性，不過該算法容易遺漏一些局部信息，影響區(qū)別性。此外，還有利用小波變換DWT(discrete wavelet transform)計算哈希[3]，該算法效率較高。Tang等人提出了一種基于Random Gabor濾波和離散小波變換DWT的魯棒圖像哈希算法[4]，該算法對普通攻擊具有較好的魯棒性，不過對大角度旋轉(zhuǎn)的魯棒性比較差。

2)基于數(shù)據(jù)降維的方法：Tang等人在文獻[5]中使用DCT和局部線性嵌入LLE(local linear embedding)來構(gòu)建哈希序列。該算法對大角度的旋轉(zhuǎn)魯棒性較差。Tang等人提出基于張量分解TD(Tensor Decomposition)的圖像哈希算法[6]，該算法的魯棒性很好，效率也比較高，但是區(qū)別性還有提高的空間。文獻[7]中利用四元數(shù)奇異值分解QSVD (quaternion singular value decomposition)來構(gòu)建哈希序列，具有不錯的效果。文獻[8]Tang等人提出一種基于環(huán)分割和非負矩陣分解的圖像哈希方案。該方案對JPEG壓縮，旋轉(zhuǎn)等攻擊具有良好的魯棒性。

此外，還有基于統(tǒng)計特征[9-11]、中心局部對稱二值模式[12]、顯著區(qū)域[13]、Zernike矩[14-15]、結(jié)構(gòu)與梯度[16]、混合特征[17]等多種圖像哈希算法。

上述哈希算法的哈希序列相對較長，并且大多數(shù)基于二維平面進行特征提取，而三維空間特征也非常重要。本文算法將二維平面特征與三維空間特征結(jié)合，減小了哈希序列長度，并且增強了哈希算法的魯棒性和區(qū)別性。

與上述算法相比，本文算法有幾點創(chuàng)新。第一，過去基于超像素分割的哈希算法是對整幅RGB或YCbCr圖像進行超像素分割，這會導致生成的哈希序列較長，占用較多存儲空間。本文哈希算法則是先提取圖像亮度分量Y進行分塊，再對每個小塊進行超像素分割提取特征，這樣可以減小哈希序列的長度，使哈希序列的存儲空間變小。第二，以往的哈希算法大多數(shù)沒有同時結(jié)合圖像二維平面特征與三維空間特征，并且忽略三維空間的局部特征。本文算法以超像素分割和凸包算法得到的輪廓特征做為二維平面特征，圖像分量所構(gòu)建的三維空間中的局部距離特征做為三維空間特征。結(jié)合二維平面特征與三維空間特征得到最終哈希序列，使提取的特征更加全面，增強算法的區(qū)別性。最后本文算法與最新的基于三維空間特征的算法[16]以及另外基于二維平面特征較好的算法進行比較，仿真結(jié)果顯示本文算法具有更好圖像分類性能，并且還具有較短的哈希序列，因此本文算法所產(chǎn)生的哈希序列占用的存儲空間較小。這說明本文所提出的結(jié)合二維平面特征與三維空間特征的哈希算法的性能要優(yōu)于單一基于二維平面特征或是單一基于三維空間特征的哈希算法。同時本算法具有良好的密鑰安全性，攻擊者很難在沒有正確密鑰的情況下生成正確的哈希碼。

2 提出的圖像哈希方案

基于超像素分割和三維空間的圖像哈希算法生成框圖如圖1所示。

2.1 圖像預(yù)處理

首先將輸入圖像通過雙線性內(nèi)插法將其原始大小調(diào)整為N×N，這樣可以讓不同尺寸的圖像具有相同的哈希長度，然后用高斯低通濾波處理，盡量減小噪聲對哈希序列的影響。

圖1 哈希算法流程圖

2.2 提取位置信息

本文使用SLIC算法[18]對每個小塊進行超像素分割提取位置信息，這樣可以減小哈希序列的長度。首先將圖像從RGB彩色空間轉(zhuǎn)換為YCbCr顏色空間，在YCbCr空間中提取圖像亮度圖像Y分成大小相等不重疊的M×M個小塊Y(i，j)，然后設(shè)定參數(shù)P將每一個小塊Y(i，j)超像素分割為若干個像素集，提取這幾個像素集中包含像素個數(shù)最多的像素集Yp(i，j)。其中i是小塊在所在的行數(shù)，j是小塊在所在的列數(shù)，1≤i≤M，1≤j≤M。

Yp(i，j)中包含所有像素的坐標集Yz(i，j)就是位置信息。每個小塊中有(N/M)×(N/M)個像素，每個像素的坐標(x，y)由該像素在小塊Y(i，j)中的行數(shù)x和列數(shù)y構(gòu)成，其中1≤x≤(N/M)，1≤y≤(N/M)。

2.3 提取輪廓特征

本文利用凸包算法[19]從位置信息中提取輪廓特征，這樣做的優(yōu)點是可以用面積的形式表示出像素集在二維平面的分布狀況。首先依次提取亮度圖像的每個小塊Y(i，j)中包含像素個數(shù)最多的像素集Yp(i，j)，用凸包算法計算出Yp(i，j)中所有像素形成的凸包面積Si，j，其中i為該小圖像塊的行數(shù)(1≤i≤M)，j為該小圖像塊的列數(shù)(1≤j≤M)。如圖2所示，對圖2中亮度分量Y(1，1)小塊進行超像素分割后提取最大部分區(qū)域3內(nèi)包含像素的坐標集Yz(1，1)，求出該坐標集合圍成的四舍五入取整后的凸包面積S1，1。最后得出矩陣Si，j

(1)

矩陣S是一個M行M列的矩陣，將其每一列依次連接再轉(zhuǎn)置到得到一個一行M×M列的向量S(n)，其中1≤n≤M2，用其構(gòu)建哈希序列H1

(2)

其中n=1，2，…，M2，e是S(n)的平均值。H1是由輪廓特征提取的哈希序列，長度為M2。

圖2 求圖像分量分成的小塊內(nèi)最大一部分3所包含的坐標圍成的凸包

2.4 提取三維空間距離特征

以像素的行為x軸坐標，像素列為y軸坐標，以像素值為z軸坐標，可將圖像構(gòu)建為三維矩陣。圖3(a)為亮度分量Y在三維空間中的形式。

本文將亮度分量Y分成大小相等不重疊的M×M個小塊。為了構(gòu)建三維坐標，分別以亮度分量Y所分成小塊的行數(shù)i為x軸坐標，以亮度分量Y所分成小塊的列數(shù)j為y軸坐標，由每個小塊包含像素的平均值L(i，j)為z軸坐標，由此建立三維坐標系。則亮度圖像Y位于M×M個小塊中第i行第j列的小塊Y(i，j)在三維空間中的坐標為(i，j，L(i，j))。圖3(b)顯示的是亮度圖像Y分成的小塊在三維空間中的坐標。

如圖3(b)所示，亮度圖像Y位于M×M個小塊中第i行第j列的小塊Y(i，j)，在三維空間中的坐標為(i，j，L(i，j))，與其相鄰的三個小塊在三維空間中的坐標為(i，j+1，L(i，j+1))，(i+1，j，L(i+1，j))，(i+1，j+1，L(i+1，j+1))。

再求出(i，j+1，L(i，j+1))，(i+1，j，L(i+1，j))，(i+1，j+1，L(i+1，j+1))三個點在三維空間中圍成的三角形的重心坐標Oi，j，求出點(i，j，L(i，j))與Oi，j的距離D(i，j)構(gòu)建空間距離特征。Oi，j的坐標為(xi，j，yi，j，zi，j)，其中xi，j，yi，j，zi，j的值分別如式(3)～(5)所示

xi，j=(i+i+1+i+1)÷3

(3)

yi，j=(j+1+j+j+1)÷3

(4)

zi，j=(L(i，j+1)+L(i+1，j)+L(i+1，j+1))÷3

(5)

圖3 (a)亮度分量Y在三維空間中的形式 (b)亮度分量Y分成的小塊在三維空間中的坐標及距離特征的提取

最后求Y(i，j)在三維空間中的坐標為(i，j，L(i，j))與重心坐標Oi，j兩個點在三維空間中的距離D(i，j)，D(i，j)如式(6)所示：

(6)

D(i，j)組成的矩陣D

(7)

矩陣D是一個M-1行M-1列的矩陣，將其每一列依次連接再轉(zhuǎn)置到得到一個一行(M-1)×(M-1)列的向量D(n1)，其中1≤n1≤(M-1)2，用其構(gòu)建哈希序列H2

(8)

其中n1=1，2，…，(M-1)2，e1是D(n1)的平均值。則H2是由三維空間距離特征提取的哈希序列，長度為(M-1)2。

2.5 哈希生成

得到的兩個特征組合成Hm=[H1H2]為中間哈希序列。由2.3節(jié)和2.4節(jié)可知本文所提哈希算法的哈希為長度C=M2+(M-1)2=2M2-2M+1位的二進制數(shù)。最后使用密鑰對Hm進行置亂得到H，H為最終哈希序列。如(13)所示，當兩幅圖像漢明距離P大于閾值時判斷為不同圖像，反之判斷為相似圖像。

(9)

其中：h1和h2為兩幅圖像的哈希序列；⊕為異或符號。

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

本文算法的參數(shù)設(shè)置如下：歸一化尺寸N=256，標準差為1的3×3的高斯低通濾波。分成小塊的數(shù)量為M2=8×8=64，參數(shù)P=5，P是指對每個小塊使用超像素分割時預(yù)創(chuàng)建超像素數(shù)。因此哈希長度為C=M2+(M-1)2=2M2-2M+1=113bits。本文實驗均在一臺2.30GHz Core i5-8300H，8GB內(nèi)存，操作系統(tǒng)為windows 10的電腦上運行，編程平臺為Matlab 2018b。

3.1 魯棒性實驗

用20幅圖像作為樣本進行魯棒性實驗，其中10幅如圖4所示，樣本圖像依次按表1攻擊類型生成相似圖像。用本文算法得到這些相似圖像的哈希序列，并依次計算這些哈希序列與原始圖像的哈希序列之間的歸一化漢明距離。根據(jù)攻擊類別的不同，繪制原始圖像與相似圖像之間歸一化漢明距離圖，圖5給出了其中5幅圖像的魯棒性實驗結(jié)果，從圖5中可以看出除旋轉(zhuǎn)攻擊之外的曲線波動范圍較小，歸一化漢明距離均小于0.13。而圖像旋轉(zhuǎn)攻擊的實驗結(jié)果中，漢明距離隨角度的增加而增大。這是因為本算法對圖像進行分塊處理，因此對旋轉(zhuǎn)攻擊較敏感。表2為20幅圖像在不同攻擊下漢明距離的統(tǒng)計結(jié)果，可以看出在除旋轉(zhuǎn)攻擊外的實驗結(jié)果中，歸一化漢明距離最大值均小于0.13，平均值和標準差均小于0.06，而旋轉(zhuǎn)攻擊的最大值和均值均超過0.46。表示本文算法對除旋轉(zhuǎn)攻擊外的幾種攻擊，比圖像縮放，高斯濾波等攻擊具有很好的魯棒性。

圖4 彩色圖像

圖5 魯棒性實驗

3.2 區(qū)別性實驗

表1 魯棒性實驗中的攻擊設(shè)置

表2 不同攻擊下的歸一化漢明距離

圖6表示這些圖像對之間的歸一化漢明距離分布及其概率分布，通過計算發(fā)現(xiàn)不同圖像之間歸一化漢明距離最小值為0.1770，相似圖像對之間最歸一化大漢明距離為0.2301，相似圖像對和不同圖像對歸一化漢明距離的交集出現(xiàn)在0.1770和0.2301之間。為了獲取最優(yōu)閾值來區(qū)分相似圖像對和不同圖像對，本文引入碰撞率和檢錯率來分析本文算法的區(qū)別性，計算公式可為

(10)

(11)

其中，NC表示不同圖像對被錯誤判斷為相似圖像對的總數(shù)，NE表示相似圖像對被檢測為不同圖像對的總數(shù)，ND表示不同圖像對的總數(shù)，NS表示相似圖像對的總數(shù)。PC和PE分別表示為碰撞率和檢錯率。

閾值選取的計算結(jié)果如表4所示，由其中數(shù)據(jù)可知，當閾值選取0.2124時，算法同時具有較低的碰撞率和檢錯率，區(qū)別性較好。

圖6 歸一化漢明距離與概率

表3 區(qū)別性實驗中的攻擊設(shè)置

表4 閾值選取

3.3 安全性實驗

哈希算法安全性是指由不同的密鑰會產(chǎn)生不同的哈希序列。圖7說明了本文哈希算法的密鑰安全性，x軸是1000個錯誤密鑰的索引，y軸是歸一化漢明距離。從圖中看出，所有錯誤密鑰的歸一化漢明距離最小值0.3363，平均值0.4750，均大于3.2選取的閾值0.2124，閾值如圖中紅線所示。說明如果得到的是錯誤密鑰，幾乎不可能計算出正確的哈希序列，因此本文算法具有不錯的密鑰安全性。

圖7 正確與錯誤密鑰的哈希值之間的歸一化漢明距離

3.4 不同分塊性能比較

為了分析對圖像進行分塊時，分塊的數(shù)目對算法性能的影響，本文引入接收者操作特性曲線(ROC)進行性能比較，性能主要包括魯棒性和區(qū)別性等。本節(jié)由不同的閾值計算出相應(yīng)的錯誤接受率(PFPR)和正確接受率 (PTPR)，圖8中的曲線顯示其計算結(jié)果。圖8中，橫坐標為錯誤接受率PFPR，縱坐標為正確接受率PTPR，計算公式可表示為

(12)

(13)

其中，n1代表的是圖像對被誤判為相似圖像對的數(shù)目，n2代表的是圖像對被正確判斷為相似圖像對的數(shù)目；N1代表所有不同圖像對的數(shù)量，N2代表所有相似圖像對的數(shù)量。顯然，橫坐標表示的是區(qū)別性的性能，縱坐標表示的是魯棒性的性能，ROC曲線越靠近左上角表示性能越好。

在實驗中，用1000幅圖像進行區(qū)別性測試。按表3中的攻擊設(shè)置，生成視覺上相似的圖像，每幅圖像可以生成12個相似圖像。因此，相似圖像對總數(shù)為78000個，不同圖像對為499500個。當把圖像分別分為4×4塊，8×8塊，16×16塊時，本文算法哈希碼長度分別25bit，113bit，481bit。當分為16×16塊時，哈希長度較長，而且如表5所示，生成哈希碼的平均時間較長，因此，實驗中只選擇比較圖像分為4×4塊和8×8塊的哈希算法的性能。由圖8可以看出，分為4×4塊的曲線比分為8×8塊的曲線更遠離左上角，因此性能更差。本文哈希算法選擇把圖像分為8×8塊是在魯棒性和區(qū)別性之間平衡的一個較好的選擇。

表5 不同分塊時間比較

圖8 不同分塊的ROC曲線

3.5 不同參數(shù)性能比較

為了分析對圖像分成的每個小塊進行超像素分割時，設(shè)置的參數(shù)P對算法性能的影響，本節(jié)與3.4節(jié)相同，引入接收者操作特性曲線(ROC)進行性能比較，性能主要包括魯棒性和區(qū)別性等。本節(jié)由不同的閾值計算出相應(yīng)的錯誤接受率(PFPR)和正確接受率(PTPR)，圖9中的曲線顯示其計算結(jié)果。圖9中，橫坐標為錯誤接受率PFPR，縱坐標為正確接受率PTPR，計算公式與3.4節(jié)相同，可表示為式(16) (17)。

在實驗中，用1000幅圖像進行區(qū)別性測試。按表3中的攻擊設(shè)置，生成視覺上相似的圖像，每幅圖像可以生成12個相似圖像。因此，相似圖像對總數(shù)為78000個，不同圖像對為499500個。本節(jié)討論當對圖像分成的每個小塊進行超像素分割時，設(shè)置的不同參數(shù)對算法性能的影響，該參數(shù)P表示的是對每個小塊使用超像素分割時預(yù)創(chuàng)建超像素數(shù)。本節(jié)比較三個參數(shù)，分別為P=1，5，9時算法的性能。

由圖9可以看出，參數(shù)設(shè)置為5的哈希算法的ROC曲線比參數(shù)設(shè)置為1，9的哈希算法的ROC曲線更靠近左上角，所以性能更好。本文哈希算法選擇參數(shù)P=5，把超像素分割參數(shù)設(shè)置在5是在魯棒性和區(qū)別性之間平衡的一個較好的選擇。

圖9 不同參數(shù)的ROC曲線

3.6 不同算法性能比較

為了比較哈希算法的性能，本文算法與SG算法[16]，TD算法[6]，CVA-Canny算法[10]和Ring算法[9]進行了比較。比較的參數(shù)與各自發(fā)表的論文中設(shè)置的參數(shù)相同，所比較的算法哈希長度分別為156位二進制數(shù)，96位二進制數(shù)，40個十進制數(shù)(至少160位)和440位二進制數(shù)。本文提出的哈希算法的哈希碼長度是113位二進制數(shù)，僅稍長于TD算法。因此本文哈希算法與對比算法比較，在具有更優(yōu)的魯棒性和區(qū)別性的同時，具有更短的哈希碼，存儲本文算法產(chǎn)生的哈希碼的儲存空間較小。

在這個實驗中，與3.4節(jié)相同，用本文的算法計算相似圖像對與不同圖像對生成的哈希序列，并計算這些序列之間的距離。相似圖像的攻擊設(shè)置也和表3一樣。其中，相似圖像對總數(shù)78000個，不同圖像對總數(shù)499500個。與前文相同，由不同的閾值計算出相應(yīng)的錯誤接受率(PFPR)和正確接受率(PTPR)，圖10中的曲線顯示其計算結(jié)果?？梢钥闯?，本文算法的ROC曲線比別的算法更加靠近左上角，說明本文算法的分類效果較好。

表6 不同算法性能比較

SG算法[16]，TD算法[6]，CVA-Canny算法[10]，Ring算法[9]哈希碼計算的平均時間分別為0.014s，0.103s，0.284s，0.214s。本文算法提取了亮度分量Y并進行分塊，并對每個小塊進行超像素分割，因此哈希計算平均時間較長。

圖10 不同算法的ROC曲線

4 結(jié)語

圖像的三維空間特征容易在圖像哈希算法中被忽視，影響算法性能。為了充分利用圖像二維平面特征與三維空間距離特征，本文利用超像素分割與凸包算法提取二維平面特征，顯著地縮小哈希序列的長度，再結(jié)合圖像三維空間特征，提高算法性能。

仿真結(jié)果表明，本文算法對高斯濾波，圖像縮放等多種攻擊具有良好的魯棒性；ROC曲線表明本文算法與對比算法相比具有更好的圖像分類性能；本文算法在具有良好的安全性的同時哈希長度僅為113位二進制數(shù)，小于大多數(shù)哈希算法，說明本文算法產(chǎn)生的哈希序列需要的存儲空間較小。不過本文算法存在計算平均時間稍長的缺點，在下一步工作中，應(yīng)著重考慮在保留原有的良好性能的基礎(chǔ)上，優(yōu)化算法結(jié)構(gòu)，減少哈希計算的平均時間，使算法性能進一步提高。