基于圖像正則化的抗幾何變換的感知哈希算法

孫 銳， 閆曉星， 丁志中

（1. 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 合肥230009；2. 合肥工業(yè)大學(xué)光電技術(shù)研究院，安徽 合肥 230009）

基于圖像正則化的抗幾何變換的感知哈希算法

孫 銳1， 閆曉星2， 丁志中1

（1. 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 合肥230009；2. 合肥工業(yè)大學(xué)光電技術(shù)研究院，安徽 合肥 230009）

圖像哈希在內(nèi)容認(rèn)證、數(shù)據(jù)庫(kù)搜索和水印等領(lǐng)域有廣泛的應(yīng)用。該文提出的新的抗幾何變換的感知哈希方法包括三個(gè)主要階段：第一階段通過(guò)圖像正則化過(guò)程獲得一個(gè)對(duì)任意仿射變換具有不變性的正則圖像；第二階段對(duì)隨機(jī)選擇的多個(gè)子圖像進(jìn)行小波變換產(chǎn)生一個(gè)包括圖像主要特征的副圖像；第三階段采用奇異值分解捕獲圖像的局部感知成分并生成最終哈希。仿真實(shí)驗(yàn)表明算法有效抵抗了幾何變換、壓縮等感知保持操作，內(nèi)容篡改也被正確檢測(cè)。批量實(shí)驗(yàn)也證明算法有較好的穩(wěn)健性和抗誤分類(lèi)能力。

計(jì)算機(jī)應(yīng)用；感知哈希；圖像正則化；幾何變換；圖像認(rèn)證

圖像哈希是圖像內(nèi)容或特征的一種簡(jiǎn)潔表示，即使兩幅感知相近的圖像在數(shù)值上有不同的表示，感知哈希函數(shù)也使它們產(chǎn)生相同或相近的哈希序列，這是感知哈希技術(shù)與傳統(tǒng)密碼學(xué)中的哈希的顯著區(qū)別。傳統(tǒng)的哈希算法包括MD5和SHA-1等，它們對(duì)每比特的信息變化都非常敏感，這種敏感性比較適合文本或軟件數(shù)據(jù)的要求，而對(duì)于多媒體信息，它們可能在傳輸過(guò)程中經(jīng)歷有損壓縮、濾波、幾何失真、噪聲污染等變化，但依然和原始媒體感知一致，因此傳統(tǒng)的哈希算法不適合于多媒體信息[1-2]。

感知哈?？捎糜趫D像的完整性認(rèn)證，隨著大量多媒體應(yīng)用的發(fā)展，數(shù)字圖像增加了被非法操作和篡改的危險(xiǎn)。感知哈希技術(shù)通過(guò)提取表征圖像內(nèi)容的特征產(chǎn)生哈希，這一過(guò)程包含一個(gè)或若干依賴(lài)于密鑰的隨機(jī)化過(guò)程，在信息的發(fā)送端，哈?？梢酝ㄟ^(guò)伴隨或嵌入多媒體數(shù)據(jù)方式傳輸，也可單獨(dú)傳輸；在接收端，接收的信息的哈希通過(guò)同樣的方法提取，并同接收的哈希做比較來(lái)完成認(rèn)證過(guò)程。圖像哈希除了應(yīng)用于圖像認(rèn)證之外，還可用于基于內(nèi)容的數(shù)據(jù)庫(kù)提取，將數(shù)據(jù)庫(kù)中圖像的哈希排列成查找表的格式，當(dāng)需要查找某幅圖像時(shí)，計(jì)算待查圖像的哈希與查找表做比較，可快速實(shí)現(xiàn)感知相似的圖像匹配。例如，公安部門(mén)可利用哈希對(duì)罪犯指紋與指紋數(shù)據(jù)庫(kù)做快速比對(duì)，加快案件的偵破。圖像哈希還可作為邊信息用于非盲水印的提取和作為依賴(lài)圖像內(nèi)容的密鑰。

1 感知哈希的設(shè)計(jì)準(zhǔn)則

在設(shè)計(jì)圖像哈希算法時(shí)有兩個(gè)重要的設(shè)計(jì)標(biāo)準(zhǔn)：穩(wěn)健性和安全性。穩(wěn)健性意味在使用相同的密鑰的情況下，感知相近的圖像應(yīng)該產(chǎn)生相似或相同的哈希，這里哈希相似性一般用諸如歐幾里德和漢明距離來(lái)測(cè)度。在實(shí)際的應(yīng)用中作者會(huì)經(jīng)常遇到這樣的感知相近圖像，如圖像被多次A/D和D/A轉(zhuǎn)換，圖像被打印后掃描，圖像在傳輸中被濾波加噪，圖像中被加入水印等。安全性指在沒(méi)有密鑰的情況下，哈希值不容易被偽造或估計(jì)，它還必須滿(mǎn)足下列兩個(gè)性質(zhì)：?jiǎn)蜗蛐?，即假設(shè)已知哈希h和哈希函數(shù) H (·)，很難由h= H(I)得到原始圖像I；抗共謀性，即假設(shè)已知圖像I和哈希函數(shù) H (·)，很難生成第二副圖像I?滿(mǎn)足 H (I ?)= H(I)。密碼學(xué)認(rèn)證算法基本滿(mǎn)足這兩個(gè)性質(zhì)，但對(duì)于感知圖像哈希算法而言，以上穩(wěn)健性和安全性的要求實(shí)際上是相互矛盾和沖突的，如為了穩(wěn)健性可能要選取圖像處理后的不易改變的特征或關(guān)系，而對(duì)手可利用這些特征進(jìn)行共謀攻擊，所以圖像哈希技術(shù)實(shí)際是在兩者之間依據(jù)應(yīng)用的要求尋找一個(gè)最佳的折中。

綜上給出感知哈希的3個(gè)期望的性質(zhì)，設(shè)I為原始圖像， Iident為與原始圖像感知相近的圖像，Idiff為與原始圖像感知相異的圖像，H (I ,k)表示密鑰為k的哈希函數(shù)，q為哈希序列的長(zhǎng)度，θ1,θ2是滿(mǎn)足 0 ＜ θ1,θ2＜1的任意值[1]：

（1） 感知穩(wěn)健性

（2） 哈希的敏感性

（3） 哈希的不可預(yù)測(cè)性

第一條性質(zhì)對(duì)應(yīng)穩(wěn)健性的設(shè)計(jì)要求，而第二、三條性質(zhì)對(duì)應(yīng)安全性的設(shè)計(jì)要求。如何設(shè)計(jì)滿(mǎn)足這三條性質(zhì)的圖像哈希算法是一個(gè)開(kāi)放的問(wèn)題，有待分析和解決。

2 感知哈希發(fā)展簡(jiǎn)述

基于圖像內(nèi)容的感知哈希發(fā)展的歷程并不長(zhǎng)，從1996年Schneider在ICIP發(fā)表第一篇文章算起有 10年的時(shí)間，通過(guò)歸納可將圖像哈希分為兩個(gè)主要步驟，如圖1所示。

圖1 圖像哈希的主要過(guò)程

第一步特征提取將2D的圖像映射成1D的特征矢量（中間哈希），穩(wěn)健的特征提取必須捕獲圖像感知內(nèi)容，使感知相近的圖像產(chǎn)生相近的中間哈希。第二步壓縮主要功能有兩個(gè)：一是將中間哈希變?yōu)楦鼮榫o湊的形式，便于存儲(chǔ)或傳輸；二是通過(guò)量化、壓縮、信道解碼、聚類(lèi)[3]、分布式源編碼[4]等方式進(jìn)一步減少對(duì)內(nèi)容保持操作的敏感性，增強(qiáng)安全性。各種感知哈希算法的主要不同在于特征提取過(guò)程，它們主要分為基于圖像統(tǒng)計(jì)的方法、基于關(guān)系的方法、基于變換域表示的方法、基于圖像特征的方法。

1996年Schneider提出了第一個(gè)由灰度直方圖構(gòu)成哈希的圖像認(rèn)證方法[5]，作者首先將圖像分塊，然后計(jì)算每一塊的灰度直方圖，并用密鑰加密后作為最終哈希。Venkatesan在2000年ICIP提出了一種基于小波分解后子帶的圖像統(tǒng)計(jì)的哈希算法[6]，他發(fā)現(xiàn)圖像小波分解后形成的子帶的均值和方差在經(jīng)歷一些感知保持操作后具有穩(wěn)健性，算法首先將小波分解后的圖像進(jìn)行隨機(jī)劃分，然后提取每一區(qū)域的統(tǒng)計(jì)量，然后量化并輸入Reed-Muller糾錯(cuò)碼的譯碼器中產(chǎn)生最終哈希，算法具有一定的穩(wěn)健性，但對(duì)于惡意的篡改不太敏感。Fridrich提出了一種DCT域的穩(wěn)健哈希算法[7]，算法利用DCT域中低頻系數(shù)與圖像感知緊密相連的關(guān)系，將 DCT塊映射到一個(gè)依賴(lài)于密鑰的隨機(jī)模板中，最終的結(jié)果與預(yù)設(shè)門(mén)限做比較產(chǎn)生哈希，算法可有效抵抗 JPEG、低通濾波等操作，但無(wú)抗幾何變換的能力。Kozat提出了一種基于圖像SVD分解的哈希算法[8]，將隨機(jī)組成特征圖像SVD后最強(qiáng)的特征矢量構(gòu)成哈希，這種算法對(duì)幾何變換具有一定的穩(wěn)健性，但是有較高的誤分類(lèi)概率。

提取表征圖像內(nèi)容的特征量作為哈希是感知哈希構(gòu)成的重要而有效的方法，Monga等提出了一種特征點(diǎn)的感知哈希方法[9]，他用Morlet小波捕獲圖像的特征點(diǎn)（線(xiàn)性結(jié)構(gòu)的拐點(diǎn)），這些特征點(diǎn)表征了重要的視覺(jué)感知成分，同時(shí)在感知保持操作下保持一定的穩(wěn)定性，Monga在壓縮階段也做了創(chuàng)新，他分別提出了用概率量化、聚類(lèi)方法形成的最終哈希，實(shí)驗(yàn)結(jié)果表明方法對(duì)各種非惡意操作（包括幾何變化）具有一定的穩(wěn)健性，算法的缺點(diǎn)是耗時(shí)較長(zhǎng)，同時(shí)對(duì)紋理簡(jiǎn)單的圖像性能欠佳。

一種好的感知哈希算法應(yīng)該對(duì)圖像的感知保持操作具有穩(wěn)健性，其中研究的難點(diǎn)在于對(duì)不改變圖像感知內(nèi)容的幾何變換（如旋轉(zhuǎn)、縮放、平移，簡(jiǎn)稱(chēng)RST）有較好的穩(wěn)健性，現(xiàn)有的方法一般利用RST不變域的特征構(gòu)成哈希，這樣的一些變換域包括 Radon變換[10]、Fourier-Mellin變換[11]等，總體來(lái)說(shuō)這類(lèi)算法在理論上具有可行性，在實(shí)際應(yīng)用的穩(wěn)健性方面還有待進(jìn)一步測(cè)試。為了實(shí)現(xiàn)抗幾何變換的穩(wěn)健特征提取，作者的思路是找到一種方法在圖像生成哈希之前將幾何變換對(duì)圖像的影響去除，這種方法就是圖像正則化。

3 圖像正則化

圖像正則化技術(shù)[12]廣泛應(yīng)用于計(jì)算機(jī)視覺(jué)和模式識(shí)別中，正則化的圖像可以通過(guò)一個(gè)幾何變換過(guò)程得到[13]，這個(gè)過(guò)程對(duì)任意的仿射變換（Affine Transforms）具有不變性，為了進(jìn)一步描述這個(gè)過(guò)程，首先引入文中使用的若干概念：

設(shè) f (x ,y)為 M× N大小的數(shù)字圖像，它的矩和中心矩定義為 mpq和 μpq， p,q∈Z+

這里

前述的RST變換都是仿射變換的特殊形式，仿射變換的其他形式包括：① 在 x方向的剪切變換② 在 y方向的剪切變換③ 在 x和 y方向的尺度變換在 a ≠ 0,det(A) ≠0的情況下，

11任一仿射變換A都可分解為上述 3種變換的乘積A = As·Ay·Ax。

圖像正則化過(guò)程完成在仿射幾何偏移下的不變性，具體的過(guò)程如下：

（4） 在x和y方向的尺度變換 按照式（4）變換 f3(x,y)，式中為最終的正則化圖像，參數(shù)滿(mǎn)足預(yù)設(shè)的標(biāo)準(zhǔn)尺寸和

以上四步去除了幾何偏移成分，更具體地說(shuō)第一步消除了仿射攻擊中的平移，第二、三步消除了仿射攻擊中的x和y方向的剪切，第四步消除了仿射攻擊中的縮放，使圖像規(guī)整到一個(gè)標(biāo)準(zhǔn)尺寸。一幅圖像與它的仿射變換有相同的正則化圖像，參見(jiàn)圖2。

下面進(jìn)一步確定變換的主要參數(shù)：

（1） 剪切變換的參數(shù)β 參數(shù)β滿(mǎn)足以下等式

（2） 剪切變換的參數(shù)γ 參數(shù)γ滿(mǎn)足以下等式

（3） 尺度變換的參數(shù)α ,δ 通過(guò)預(yù)設(shè)的標(biāo)準(zhǔn)尺寸可以確定尺度變換的參數(shù)的幅值，它們的符號(hào)由確定。

4 感知哈希算法

以上描述的圖像正則化過(guò)程產(chǎn)生了一個(gè)對(duì)任意仿射變換具有不變性的正則化圖像，本節(jié)對(duì)這個(gè)圖像進(jìn)一步處理獲得最終哈希。

（1） 設(shè)正則化圖像為 Inor，從中偽隨機(jī)的選擇p個(gè)子圖像 Ai∈Rm×m，1 ≤ i≤ p。

（2） 對(duì)每個(gè)子圖像 Ai進(jìn)行L層離散小波分解，取其低頻子帶 Ai(DC)，并將其轉(zhuǎn)換成一維矢量

（3） 將p個(gè)矢量ηi順序組合成 p× r大小的矩陣T，又稱(chēng)副圖像。

（4） 對(duì)矩陣T做奇異值分解

這里U和V是正交的 p× p和 r× r的左右奇異值矩陣，S是非負(fù)元素組成的 p× r的對(duì)角陣。

哈希的整個(gè)生成過(guò)程可參見(jiàn)圖3，算法通過(guò)正則化（Normalization），小波變換（Wavelet），奇異值分解（SVD）3個(gè)階段產(chǎn)生最終哈希，所以可以簡(jiǎn)稱(chēng)為NWS算法。小波變換獲得原始圖像的粗略版本，其保留了圖像的主要特征，SVD增強(qiáng)了算法對(duì)感知保持操作的穩(wěn)健性，并進(jìn)一步降低了哈希的長(zhǎng)度。整個(gè)算法通過(guò)隨機(jī)選取可重疊的子圖像獲得安全性，同時(shí)可通過(guò)在步驟三引入置亂運(yùn)算進(jìn)一步增強(qiáng)安全性。

圖3 最終哈希的生成過(guò)程

5 實(shí)驗(yàn)結(jié)果

作者在實(shí)驗(yàn)中采用歐氏距離來(lái)測(cè)度兩個(gè)圖像哈希之間的差異，這里用 Iide表示與原始圖像I感知相似的圖像，用 Idif表示與原始圖像I感知不同的圖像，他們之間應(yīng)滿(mǎn)足

實(shí)驗(yàn)采用 256× 256的Lena、bridge、peppers作為測(cè)試圖像，見(jiàn)圖4所示。實(shí)驗(yàn)參數(shù)為 p =36，m =64， L =3， r =64， t =2， ε =0.02，δ =0.03，最終形成的哈希長(zhǎng)度h =200。圖

式中 ε,δ 為預(yù)設(shè)門(mén)限。5(a)～(d)為 4個(gè)感知相似的圖像，它們分別通過(guò)JPEG壓縮（QF=20），旋轉(zhuǎn)15°，隨機(jī)仿射變換，中值濾波（ 3× 3）處理。表1展示了三副測(cè)試圖像在各種感知保持操作后的歐氏距離（所有操作用 Stirmark測(cè)試軟件[14]得到），其中許多屬于仿射變換處理，可以看出算法對(duì)幾何變換具有很好的穩(wěn)健性，對(duì)其他感知保持操作也有很好的效果。表中最右一列為Kozat方法[8]對(duì)Lena測(cè)試的結(jié)果，對(duì)比發(fā)現(xiàn)NWS算法在幾何攻擊后有明顯改善。算法對(duì)內(nèi)容篡改具有敏感性，圖6為原始的 boats圖和內(nèi)容篡改后的圖像（桅桿等處被改），實(shí)驗(yàn)得到的歐氏距離為0.035，大于預(yù)設(shè)門(mén)限0.03。

圖4 原始圖像

圖5 4種攻擊后的圖像

表1 在各種感知保持操作后的歐氏距離

在內(nèi)容提取應(yīng)用中要求良好的抗誤分類(lèi)能力，為了進(jìn)一步測(cè)試算法的抗誤分類(lèi)能力，作者設(shè)計(jì)了如下實(shí)驗(yàn)，從圖像數(shù)據(jù)庫(kù)中隨機(jī)選取100幅不同的圖像，每幅圖像分別與圖5四種攻擊處理后的圖像和完全相異的圖像作歐氏距離的比較，實(shí)驗(yàn)結(jié)果如圖7所示，圖7(a)～(d)分別對(duì)應(yīng)四種攻擊，圖中實(shí)線(xiàn)代表與相異圖像的結(jié)果，虛線(xiàn)代表與相似圖像的結(jié)果。兩線(xiàn)并不重疊，表明算法具有較強(qiáng)的抗誤分類(lèi)能力。

圖6 內(nèi)容篡改前后的圖像

圖7 Lena圖像與100幅不同圖像的歐氏距離和在100個(gè)不同密鑰下與攻擊圖像的歐氏距離對(duì)比

6 總 結(jié)

本文提出了一種新的抗幾何變換的感知哈希方法NWS，NWS用3個(gè)階段來(lái)實(shí)現(xiàn)設(shè)計(jì)目標(biāo)，圖像正則化去除仿射變換的影響，小波變換抽取圖像中重要的特征成分，奇異值分解提取局部的感知成分并實(shí)現(xiàn)哈希長(zhǎng)度的壓縮。實(shí)驗(yàn)結(jié)果表明了算法對(duì)幾何變換具有良好的穩(wěn)健性，對(duì)其他感知保持操作和惡意篡改也具有較好性能。通過(guò)在圖像數(shù)據(jù)庫(kù)中的對(duì)比實(shí)驗(yàn)，也證實(shí)了算法有較好的抗誤分類(lèi)能力。

未來(lái)的工作作者將進(jìn)一步探索算法在基于內(nèi)容的數(shù)據(jù)庫(kù)搜索和圖像認(rèn)證中的應(yīng)用，例如改良算法可以定位篡改的區(qū)域。

[1] Monga V. Perceptually based methods for robust image hashing [D]. University of Texas, Austin, 2005.

[2] Wang S Z, Zhang X P. Recent development of perceptual image hashing [J]. Journal of Shanghai University (English Edition), 2007, 11(4): 323-331.

[3] Monga V, Banerjee A, Evans B L. A clustering based approach to perceptual image hashing [J]. IEEE Trans. on Information Forensics and Security, 2006, 1(1): 68-79.

[4] Johnson M, Kannan R. Dither-based secure image hashing using distributed coding[C]//Proceedings of the 2003 International Conference on Image Processing. Barcelona, Catalonia, Spain, 2003: 14-17.

[5] Schneider M, Chang S F. A robust content based digital signature for image authentication[C]// Proceedings of 1996 IEEE ICIP. Laussane, Switzerland, 1996: 227-230.

[6] Venkatesan R, Koon S M, et al. Robust image hashing[C]//Proceedings of 2000 IEEE ICIP, 2000: 664-666.

[7] Fridrich J Goljan M. Robust hash functions for digital watermarking[C]//IEEE Proceedings International Conference on Information Technology: Coding and Computing. Las Vegas, Nevada, USA, 2000: 178-183.

[8] Kozat S S, Venkatesan R, Mihcak K M. Robust perceptual image hashing via matrix invariants[C]// Proceedings of 2005 ICIP. Genova, Italy, 2005: 3443-3446.

[9] Monga V, Evans B L. Perceptual image hashing via feature points: performance evaluation and tradeoffs [J]. IEEE Trans. on Image Processing, 2006, 15(11): 3453-3466.

[10] Seo S J, Haitsma J, et al. A robust image fingerprinting system using the radon transform [J]. Signal Processing: Image Communication, 2004, 19: 325-339.

[11] Swaminathan A, Mao Y, Wu M. Robust and secure image hashing [J]. IEEE Trans. on Information Forensics and Security, 2006, 1(2): 215-230.

[12] Wood J. Invariant pattern recognition: a review [J]. Pattern Recognition, 1996, 29(1): 1-17.

[13] Shen D, Ip S H. Generalized affine invariant image normalization [J]. IEEE Trans. on Pattern Anal. Mach. Intell. 1997, 19(5): 431-440.

[14] StirMark 4.0 2001[EB/OL]. Available: http://www.cl. cam.ac.uk/fapp2/watermarking/stirmark/.

Robust Perceptual Hashing Algorithm to Geometric Distortions Based on Image Normalization

SUN Rui1, YAN Xiao-xing2, DING Zhi-zhong1
( 1. School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China; 2. Academy of Optoelectronic Technology, Hefei University of Technology, Hefei Anhui 230009, China )

Image hashing functions have extensive applications in content authentication, database search and watermarking, etc. A novel perceptual hashing algorithm is developed which is robust to geometric distortions. The algorithm includes three stages: the first stage obtains the image that is invariant to any affine transforms through a normalization procedure; the second stage applies discrete wavelet transform to pseudo-randomly select sub-images to obtain secondary image including main features; the third stage uses singular value decomposing to capture local perceptual features and to get the final hash. The experiments show the method withstands perceptually preserved manipulations including geometric distortions, compression, and common signal processing operations. The content changes are also can be detected accurately. Thus the proposed method achieves perceptual robustness while avoiding misclassification.

computer application; perceptual Hashing; image normalization; geometric distortions; image authentication

TP 391.41

A

1003-0158(2010)02-0116-07

2008-10-31

孫 銳（1976-），男，浙江余姚人，副研究員，博士，主要研究方向?yàn)槎嗝襟w安全，圖像處理與理解。