基于差分的圖像感知哈希算法

劉 帆，王 穎，閆國玉，蔣遂平

(1.中國航天科工集團第二研究院 七〇六所，北京 100854；2.西安電子科技大學(xué) 網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071)

0 引 言

圖像感知哈希(perceptual hashing，pHash)[1]從一幅圖像導(dǎo)出并可表征圖像特征指紋。圖像pHash算法與密碼學(xué)哈希(cryptographic hashing，cHash)[2]算法不同。在cHash算法中，假設(shè)輸入為一幅圖像，則該圖像的微小變化會通過雪崩效應(yīng)引起輸出結(jié)果即cHash值的巨大變化；而圖像pHash算法則要求輸入圖像在視覺上相似時，輸出的圖像pHash值也相似。

近年來，隨著云存儲技術(shù)的發(fā)展，圖像pHash算法對于圖像文件的內(nèi)容識別、完整性驗證和水印技術(shù)起到重要作用。圖像pHash算法被廣泛用于可搜索加密方案中的相似性檢索，并因為其能同時保證查詢效率和結(jié)果精確度的優(yōu)點，使其成為圖像安全去重的重要技術(shù)之一[3,4]。

云存儲和去重應(yīng)用，要求pHash算法具有計算簡單、一定的不同圖像區(qū)分能力等特性。為此，本文提出并實現(xiàn)了循環(huán)貫序差分和拉普拉斯算子等兩種基于差分的圖像感知哈希算法。針對設(shè)計的算法，分別在小規(guī)模相似圖像集合和大規(guī)模不同圖像集上進行了測試。與現(xiàn)有復(fù)雜性類似的圖像感知哈希算法相比，所提出的算法體現(xiàn)了圖像像素點間的局部關(guān)聯(lián)性，增加了不同圖像哈希值間的差異，顯著提升了不同圖像的區(qū)分概率。

1 相關(guān)的工作

自從圖像pHash的概念提出以來，研究人員已經(jīng)提出了多種pHash算法。根據(jù)算法運行機制的不同，主要分為以下3類：

(1)基于圖像灰度的pHash算法：利用圖像灰度值與圖像灰度均值的差或者利用相鄰像素的灰度差等信息來計算pHash值。應(yīng)用比較廣泛的主要有均值pHash算法(average pHash，Avg pHash)[5]，主要利用亮度變化小的區(qū)域即圖像低頻成分來描述整幅圖像所含有的信息，計算復(fù)雜度低，但是進行圖像相似性檢測的準(zhǔn)確率較低；塊均值pHash算法[5]，采用重疊阻塞和旋轉(zhuǎn)操作來增強圖像對幾何失真的魯棒性，在穩(wěn)健性和可辨識性方面表現(xiàn)出比其它現(xiàn)有算法更高的性能并且實現(xiàn)簡單；差分pHash算法[5]基于漸變實現(xiàn)，考慮了圖像的局部特征。

(2)基于圖像正交變換的pHash算法：對圖像進行正交等方式的變換，利用變換后的系數(shù)與系數(shù)平均值的差計算pHash值。劉穎等[6]提出一種基于離散余弦變換(discrete cosine transform，DCT)和奇異值分解(singular va-lue decomposition，SVD)相結(jié)合的pHash算法，首先需要將圖像進行分塊DCT變換，然后將低頻系數(shù)的組合進行SVD變換，最后將二值水印嵌入到奇異值所對應(yīng)的矩陣上，這使得當(dāng)嵌入較高強度的水印時也能具有較好的視覺不可感知性。Sheth等[7]提出了一種基于DCT、離散小波變換(discrete wavelet transformation，DWT)和密碼技術(shù)組合的算法，對水印圖像和原始圖像提供強大的魯棒性和感知透明度，以抵抗諸如裁剪、噪聲和縮放之類的不同類型的攻擊。

(3)基于圖像特征點的pHash算法：通過提取圖像特征點來表示圖像。歐陽君林等[8]提出了一種基于四元數(shù)Zernike矩(quaternion Zernike moments，QZMs)和尺度不變特征變換(scale invariant feature transform，SIFT)的魯棒圖像哈希方案用于圖像認(rèn)證。所提出的方法可以定位篡改區(qū)域并檢測修改的性質(zhì)，包括對象插入、移除、替換、復(fù)制、移動、剪切和粘貼等操作。然而此方案對于圖像噪聲以及圖像亮度變化較為敏感，使得其對該類型的圖像篡改識別準(zhǔn)確率較低。楊寧等[9]提出了一種基于SIFT特征和角度相對距離的圖像配準(zhǔn)算法，該算法充分利用了圖像正確匹配特征點對之間存在的角度關(guān)系，實現(xiàn)了特征點之間的精確匹配。

基于圖像灰度的pHash算法主要使用圖像低頻成分表征圖像信息，計算復(fù)雜度不高，但精度較低?；趫D像正交變換的pHash算法，對圖像進行正交等方式的變換來獲取圖片的低頻成分，只要圖像之間的相互空間關(guān)系不變，即能提供良好的相似圖像識別效果。但是該類算法的pHash值，大多僅能表示相較于該圖像頻率平均值比例的一個估計值，并不能提供圖像真實的低頻性質(zhì)。基于圖像特征點的pHash算法，生成的圖像哈希序列維數(shù)較高，算法復(fù)雜度高，計算開銷大，響應(yīng)速度低，故這類pHash算法在圖像快速相似性檢索中很少使用。

此外，上述pHash算法的研究和應(yīng)用中，重點考慮的是如何減小視覺上相似圖像的pHash值差異，無法體現(xiàn)pHash值對不同圖像的分辨程度。常用pHash算法在實際應(yīng)用中，會將大量視覺上的不同圖像判斷為相似圖像，所帶來的通信開銷很大。因此，需要解決感知哈希算法在應(yīng)用過程中所帶來的計算復(fù)雜度高、不同圖像區(qū)分概率太低和通信開銷大這一問題。

2 圖像pHash算法

2.1 圖像pHash值的計算流程

圖像pHash值的計算流程如下：

(1)將M行N列像素點的大圖像縮小為8×8、16×16、32×32即m×m等尺寸的小圖像。

(2)彩色小圖像轉(zhuǎn)換為灰度小圖像，此時圖像可以表示為m階圖像灰度像素矩陣。使用如下規(guī)則

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

(1)

式中：Gray代表圖像像素點的灰度值，R、G和B分別代表紅、綠和藍(lán)3種顏色通道的值，取值范圍[0,255]。

(3)灰度小圖像二值化，像素取值0或1，組成m階二值像素矩陣。

(4)二值小圖像像素按某種順序串接為64、256、1024等長度的比特序列，作為圖像的pHash值。

各種pHash算法的主要差異在于(3)，例如，均值pHash計算圖像的平均灰度如下

(2)

二值化方法如下

(3)

式中：h(i,j) 代表m階二值像素矩陣第i行j列的值。如果像素的灰度大于等于平均灰度，則二值化結(jié)果為1，否則為0。同樣地，在DCT pHash算法中，首先計算圖像DCT系數(shù)，如果像素矩陣中第i行j列上的系數(shù)大于等于所有系數(shù)的均值，則該位置像素二值化結(jié)果就為1，否則為0。

2.2 圖像二值化方法改進

針對圖像pHash值的計算流程，提出了循環(huán)貫序差分pHash(Seq pHash)算法和拉普拉斯算子pHash(Laplace pHash)算法，并主要基于步驟(3)即圖像二值化方法進行改進。

(1)Seq pHash：在Seq pHash算法中進行二值化時，圖像中的像素按從上到下、從左到右的順序依次排列。對每個像素而言，如果當(dāng)前像素的灰度值大于或者等于后一個像素的灰度值時，則對應(yīng)的二值像素為1，否則為0。當(dāng)前像素是小圖像中最后一個像素時，則當(dāng)前像素的后一個像素為小圖像中第一個像素。

圖1給出了一個8×8小圖像的例子，將小圖像中的像素按照圖1中的序號順序可以排成一個序列，這是Seq pHash的順序性。如果序列中一個像素A的灰度大于等于后一個像素B的灰度，則這個像素A對應(yīng)的二值化結(jié)果為1，否則為0。如果一個像素A是序列中的最后一個像素，則像素A的后一個像素B是序列中第一個像素B，這是Seq pHash的循環(huán)性。例如在圖1中，64號像素的后一個像素是1號像素。

(2)Laplace pHash：在Laplace pHash算法中，對圖像灰度值進行二值化并使用了如下規(guī)則

(4)

圖1 Seq pHash中像素的排列方式

式中：n為鄰接像素的個數(shù)，D為m階像素矩陣中第i行j列元素鄰域像素點構(gòu)成的集合，Gray(i,j) 為m階像素矩陣中第i行j列元素鄰域上像素點的灰度值。設(shè)有一個灰度值為220的像素A。如果像素A為圖像中間像素，則其有8個鄰接像素，此時n=8，如圖2(a)所示。如果像素A在圖像的4個角上，則其有3個鄰接像素，此時n=3，如圖2(b)～圖2(e)所示。如果像素A在圖像4個邊緣，則有5個鄰接像素，此時n=5，如圖2(f)～圖2(i)所示。

圖2 Laplace pHash中鄰接像素

在Laplace pHash算法中，僅使用了Laplace的一階微分形式，并沒有采用先計算Laplace差分，再計算過零點獲得邊緣像素進行二值化的方法[10]。這是因為圖像二值化之前，較大的原始圖像已經(jīng)壓縮為小圖像，邊緣效果已經(jīng)不明顯，利用Laplace算子計算邊緣已經(jīng)沒有多大意義。

2.3 pHash值的相似性度量

漢明距離(Hamming distance)[11]是衡量兩個字之間距離的一種方法。它通過統(tǒng)計兩個相同長度的字所對應(yīng)位不同的數(shù)量來計算字之間的距離，進一步達(dá)到相似性度量的目的。若x={x1,x2,…,xn} 和y={y1,y2,…,yn} 分別表示兩個有限長度的字符串，以D(x,y) 表示兩個字符串x,y之間的漢明距離，則相似性度量過程可表示如下

(5)

式中：Q(xi,yi) 取值有如下規(guī)則

(6)

為加快字符比較效率，將漢明距離相對于字符串長度作相對距離歸一化。歸一化后的漢明距離可以定義為

(7)

特別的是，可以通過異或運算的方式來計算二進制字符串間的漢明距離Db，其中符號⊕代表異或運算符，如下

(8)

因此，可以使用所獲得的兩個字符串之間的漢明距離來確定其相似性。為了識別相似的字符串，通常設(shè)置漢明距離的閾值，表示為T。

如果D(x,y)=0，則x和y被認(rèn)為是相同的字符串。

如果D(x,y)≤T，則x和y被認(rèn)為是相似的字符串。

如果D(x,y)>T，則x和y被認(rèn)為是不相似的字符串。

兩幅圖像的pHash值差異采用漢明距離來進行度量。由于pHash值是比特序列，故漢明距離計算更加方便，只需要將兩個比特序列異或后，計算其中的比特1的數(shù)目即可。

3 實驗分析

使用圖像pHash算法進行圖像文件的相似性判斷，本質(zhì)上是將圖像按照視覺相似性進行分類，即將圖像分為與待上傳圖像相似的同類圖像和不相似的異類圖像。在模式分類中，要求同類事物的特征差距較小，不同類事物的特征差距較大[12]。因此，對于圖像pHash算法，應(yīng)該具有以下兩個性質(zhì)：

(1)類內(nèi)聚合性：同一幅圖像及其微小變形圖像的pHash值差異應(yīng)該較小。

(2)類間分離性：視覺上不同的兩幅圖像的pHash值差異應(yīng)該較大，這樣可以降低pHash沖突率。pHash沖突率，即在使用pHash值差異衡量圖像相似性時，不同圖像被認(rèn)為是相同圖像的概率。

利用收集到的圖像數(shù)據(jù)集，從上述兩個性質(zhì)上，分析本文提出的pHash算法，并與常用的Avg pHash算法和DCT pHash算法進行對比。接下來，將進一步介紹具體實驗過程和評估結(jié)果。

3.1 類內(nèi)聚合性

類內(nèi)聚合性測試的圖像集合來自開源代碼pHash庫(https://www.phash.org/download/)。圖像集合中有23幅不同的圖像，每幅圖像有4個版本：基準(zhǔn)版本(misc)、模糊版本(blur)、壓縮版本(compr)、旋轉(zhuǎn)版本(rotd)，其中blur版本圖像經(jīng)過高斯噪聲和椒鹽噪聲等常見信號的處理；compr版圖像經(jīng)過聯(lián)合圖片專家組(joint photographic experts group，JPEG)制定的標(biāo)準(zhǔn)壓縮算法的處理；rotd版是以圖像對稱中心為定點并作輕微旋轉(zhuǎn)的圖像。其中1幅圖像的4個版本如圖3所示。

圖3 部分測試圖像

分別在不同算法和不同比特數(shù)目下，計算每幅基準(zhǔn)、模糊、壓縮和旋轉(zhuǎn)版本圖像的pHash值，進一步得到漢明距離的平均值和方差，列于表1。在表1欄目數(shù)據(jù)區(qū)域，每個單元格有兩行數(shù)值，第一行數(shù)值是平均值，第二行數(shù)值是方差。例如，在32×32圖像尺寸1024比特數(shù)目下，計算每幅基準(zhǔn)圖像和其模糊版圖像在Avg pHash算法下的pHash值。然后，求取兩個pHash值間的漢明距離，則23組圖像產(chǎn)生23個漢明距離。接下來，對該23個漢明距離值求取平均值和方差，分別為2.782 609和3.463 556。

從表1可以看出，在這個小規(guī)模圖像集合上，隨著圖像尺寸的縮小，這4種圖像pHash算法計算出的pHash值普遍存在著一種現(xiàn)象。每幅基準(zhǔn)圖像與其模糊、壓縮、旋轉(zhuǎn)版本圖像pHash值的差異在不斷縮小，這意味著類內(nèi)聚合性“越來越好”。然而這是一種假象，因為伴隨圖像壓縮率的提高，圖像損失的信息熵也會越來越多，再去比較相似性已經(jīng)沒有任何意義。因此，計算圖像的pHash值時，圖像比特數(shù)不應(yīng)太少，否則容易將不同的圖像判別為相同或相似的圖像。

此外，Avg pHash算法對于同一圖像的不同變化版本，計算出的pHash值差異較小，Seq pHash算法、Laplace pHash算法和DCT pHash算法計算出的pHash值差異較大。因此，可以得出如下結(jié)論：即Avg pHash算法在類內(nèi)聚合性上更有優(yōu)勢。但是，既然相似圖像的pHash值差異較小，不相同圖像的pHash值差異也可能較小，即不相同的圖像也可能被判斷為相同或相似的圖像，再次說明圖像分類中關(guān)于類間分離性的討論很有必要。

表1 基準(zhǔn)圖像與其它版本圖像的漢明距離均值和方差

3.2 類間分離性

為進一步分析pHash算法的類間分離性，采用CIFAR-100(http://www.cs.toronto.edu/～kriz/)的開源圖像集合進行實驗。CIFAR-100開源圖像集合由32×32圖像尺寸大小，共100個類的彩色圖像組成。其中每個類包含600幅圖像，500幅用于訓(xùn)練的圖像和100幅用于測試的圖像。以下是該圖像數(shù)據(jù)集合中的類，以及每個類中的一些隨機圖像，如圖4所示。

比較圖像在256比特數(shù)目下的pHash值差異。選取CIFAR-100開源圖像集合中的訓(xùn)練集，即100類不同景物的50 000幅不同彩色圖像，作為本次實驗的數(shù)據(jù)集。接下來，兩兩圖像形成一對，那么這50 000幅圖像可以組成 1 249 975 000 個圖像對。采用不同pHash算法，求取每個圖像對pHash值之間的漢明距離，并統(tǒng)計小于等于某個漢明距離的圖像對的累計分布情況。

圖5給出了不同pHash算法下圖像對數(shù)目隨漢明距離分布情況?？梢钥闯觯?dāng)漢明距離為50時，DCT pHash算法和Avg pHash算法便開始有數(shù)量比較可觀的不相同圖像對被判定為相似圖像對，而在此情景下，Seq pHash算法和Laplace pHash算法所對應(yīng)的漢明距離為90。相對而言，Seq pHash算法和Laplace pHash算法有較高的容錯率。

圖4 CIFAR-100數(shù)據(jù)集部分圖像

圖5 圖像對數(shù)目隨漢明距離分布情況

圖7 漢明距離小于50時的圖像對累計數(shù)目 隨距離分布趨勢

為進一步觀察不同pHash算法下漢明距離小于50時圖像對數(shù)目上存在的差距，圖6給出了不同pHash算法下漢明距離小于50時圖像對數(shù)目隨距離分布的對數(shù)坐標(biāo)變化趨勢，圖7給出了不同pHash算法下漢明距離小于50時圖像對累計數(shù)目隨距離分布情況?？梢钥闯觯琒eq pHash值和Laplace pHash值在漢明距離小于50的圖像對數(shù)目明顯少于Avg pHash值和DCT pHash值的圖像對數(shù)目。其中圖6和圖7，縱坐標(biāo)均采用了底數(shù)為10的對數(shù)刻度。

圖8給出了不同pHash算法下圖像對累計數(shù)目隨漢明距離分布情況，可以看出，大多數(shù)圖像對的Seq pHash值和Laplace pHash值的漢明距離大于90，大多數(shù)圖像對的Avg pHash值和DCT pHash值的漢明距離大于50。這表明，Seq pHash值和Laplace pHash值的pHash沖突概率[13]小于Avg pHash值和DCT pHash值的概率。

圖8 圖像對累計數(shù)目隨漢明距離分布情況

表2給出了部分漢明距離下圖像對數(shù)目的累計分布。例如，Avg pHash算法中有1693對圖像的漢明距離小于等于2?？梢钥闯觯瑸檫_(dá)到百萬分之一以下的哈希沖突率，即不同圖像被認(rèn)為是相同或相似圖像的概率小于百萬分之一，要求相同或相似圖像對的累計數(shù)目不能超過1250對。這時，Avg pHash算法對應(yīng)的漢明距離閾值為2，Seq pHash算法、Laplace pHash算法和DCT pHash算法對應(yīng)的漢明距離閾值分別為33、48和10。Seq pHash算法、Laplace pHash算法的漢明距離閾值較大，可以容許的圖像間差異較大，類間分離性優(yōu)于Avg pHash算法和DCT pHash算法。

由于不同pHash算法的類內(nèi)平均距離不同，用于判斷兩幅圖像是否為同一圖像的漢明距離閾值也應(yīng)不同。采用模糊、壓縮和旋轉(zhuǎn)3種情況的平均值T作為閾值，方法如下

表2 部分漢明距離下的圖像對累計數(shù)目

(9)

式中：D(mi,bi) 表示第i幅基準(zhǔn)版圖像和模糊版圖像pHash值間的漢明距離；D(mi,ci) 表示第i幅基準(zhǔn)版和壓縮版圖像pHash值間的漢明距離；D(mi,ri) 表示第i幅基準(zhǔn)版和旋轉(zhuǎn)版圖像pHash值間的漢明距離。k值代表圖像組數(shù)23，i取值范圍[1,23]。此時，Avg pHash算法、Seq pHash算法、Laplace pHash算法和DCT pHash算法對應(yīng)的漢明距離閾值分別為12、20、21和20，對應(yīng)的相同或相似圖像對數(shù)目的累計分別為31 983、167、124和39 138。其中，Seq pHash算法和Laplace pHash算法的相同或相似圖像對累計數(shù)目較小，哈希沖突概率小，類間分離性優(yōu)于Avg pHash算法和DCT pHash算法。

圖像旋轉(zhuǎn)造成的差異最大，超過平均差異，在工程中選擇圖像輕微旋轉(zhuǎn)情況下的均值與方差的和作為判斷圖像相似性的漢明距離閾值。這時，Avg pHash算法、Seq pHash算法、Laplace pHash算法和DCT pHash算法的閾值分別為21、33、33和35，對應(yīng)的相同或相似圖像對數(shù)目的累計分別為171 853、1240、321和587 125。該種情況下，Seq pHash算法和Laplace pHash算法的相同或相似圖像對累計數(shù)目明顯較小，再次說明，Seq pHash算法和Laplace pHash算法的哈希沖突概率小，類間分離性優(yōu)于Avg pHash算法和DCT pHash算法。

實驗結(jié)果表明，Avg pHash算法沒有考慮圖像像素點之間的關(guān)系，而DCT pHash算法中DCT系數(shù)主要描述圖像各種組成信號強弱的全局性質(zhì)。因此，Avg pHash算法和DCT pHash算法的類間分離性相對較差。Seq pHash算法和Laplace pHash算法均考慮了像素點之間的關(guān)系，即圖像的局部性質(zhì)。Seq pHash算法考慮了相鄰2個像素點之間的關(guān)系，Laplace pHash算法考慮了像素點與周圍像素點的關(guān)系，在圖像局部性上更有優(yōu)勢。因此，Laplace pHash算法的類間分離性好于Seq pHash算法。

由此可知，Seq pHash算法和Laplace pHash算法雖然增大了同一幅圖像與其微小變形圖像之間的pHash值差異，但也增大了不同圖像之間pHash值的差異。也就是說，通過選擇可以容許圖像微小變化的漢明距離閾值，這兩種算法將仍能按照視覺相似性進行圖像的分類。此外，所設(shè)計算法可以更清楚地量化哈希碰撞效果，提高了查詢結(jié)果的精確率和召回率。這樣將進一步減少圖像相似性判斷的錯誤率，從而降低了對結(jié)果處理的開銷。

4 結(jié)束語

本研究針對可搜索加密方案中相似性檢索關(guān)于如何增大不相似圖像差異這一問題，提出了Seq pHash和Laplace pHash兩種基于差分的圖像感知哈希算法，并對所提出的算法進行了性能測評。測評分別采用開源感知哈希庫的小規(guī)模圖像集和CIFAR-100大規(guī)模圖像集。測試結(jié)果表明，所提出的圖像感知哈希算法較好地體現(xiàn)了圖像像素點間的局部關(guān)聯(lián)性。在不同圖像被認(rèn)為是相同或相似圖像的概率小于百萬分之一情況下，Seq pHash算法和Laplace pHash算法對應(yīng)漢明距離閾值均高于Avg pHash算法和DCT pHash算法對應(yīng)漢明距離閾值。因此，所提出的pHash算法在類間分離性上優(yōu)于所對比的常用pHash算法，它們不僅能夠識別多種失真類型的相似圖像，還能有效地降低不相似圖像漢明距離接近的概率以實現(xiàn)不同圖像的區(qū)分，可以更好地應(yīng)用到可搜索加密方案中的相似性檢索中。