孫 銳， 閆曉星， 丁志中

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

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

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

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

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

計算機應用；感知哈希；圖像正則化；幾何變換；圖像認證

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

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

1 感知哈希的設計準則

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

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

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

（2） 哈希的敏感性

（3） 哈希的不可預測性

第一條性質對應穩(wěn)健性的設計要求，而第二、三條性質對應安全性的設計要求。如何設計滿足這三條性質的圖像哈希算法是一個開放的問題，有待分析和解決。

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

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

圖1 圖像哈希的主要過程

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

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

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

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

3 圖像正則化

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

設 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。

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

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

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

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

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

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

（3） 尺度變換的參數(shù)α ,δ 通過預設的標準尺寸可以確定尺度變換的參數(shù)的幅值，它們的符號由確定。

4 感知哈希算法

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

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

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

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

（4） 對矩陣T做奇異值分解

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

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

圖3 最終哈希的生成過程

5 實驗結果

作者在實驗中采用歐氏距離來測度兩個圖像哈希之間的差異，這里用 Iide表示與原始圖像I感知相似的圖像，用 Idif表示與原始圖像I感知不同的圖像，他們之間應滿足

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

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

圖4 原始圖像

圖5 4種攻擊后的圖像

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

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

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

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

6 總 結

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

未來的工作作者將進一步探索算法在基于內(nèi)容的數(shù)據(jù)庫搜索和圖像認證中的應用，例如改良算法可以定位篡改的區(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-），男，浙江余姚人，副研究員，博士，主要研究方向為多媒體安全，圖像處理與理解。