基于图像正则化的抗几何变换的感知哈希算法

孙 锐， 闫晓星， 丁志中

（1. 合肥工业大学计算机与信息学院，安徽 合肥230009；2. 合肥工业大学光电技术研究院，安徽 合肥 230009）

基于图像正则化的抗几何变换的感知哈希算法

孙 锐1， 闫晓星2， 丁志中1

（1. 合肥工业大学计算机与信息学院，安徽 合肥230009；2. 合肥工业大学光电技术研究院，安徽 合肥 230009）

图像哈希在内容认证、数据库搜索和水印等领域有广泛的应用。该文提出的新的抗几何变换的感知哈希方法包括三个主要阶段：第一阶段通过图像正则化过程获得一个对任意仿射变换具有不变性的正则图像；第二阶段对随机选择的多个子图像进行小波变换产生一个包括图像主要特征的副图像；第三阶段采用奇异值分解捕获图像的局部感知成分并生成最终哈希。仿真实验表明算法有效抵抗了几何变换、压缩等感知保持操作，内容篡改也被正确检测。批量实验也证明算法有较好的稳健性和抗误分类能力。

计算机应用；感知哈希；图像正则化；几何变换；图像认证

图像哈希是图像内容或特征的一种简洁表示，即使两幅感知相近的图像在数值上有不同的表示，感知哈希函数也使它们产生相同或相近的哈希序列，这是感知哈希技术与传统密码学中的哈希的显著区别。传统的哈希算法包括MD5和SHA-1等，它们对每比特的信息变化都非常敏感，这种敏感性比较适合文本或软件数据的要求，而对于多媒体信息，它们可能在传输过程中经历有损压缩、滤波、几何失真、噪声污染等变化，但依然和原始媒体感知一致，因此传统的哈希算法不适合于多媒体信息[1-2]。

感知哈希可用于图像的完整性认证，随着大量多媒体应用的发展，数字图像增加了被非法操作和篡改的危险。感知哈希技术通过提取表征图像内容的特征产生哈希，这一过程包含一个或若干依赖于密钥的随机化过程，在信息的发送端，哈希可以通过伴随或嵌入多媒体数据方式传输，也可单独传输；在接收端，接收的信息的哈希通过同样的方法提取，并同接收的哈希做比较来完成认证过程。图像哈希除了应用于图像认证之外，还可用于基于内容的数据库提取，将数据库中图像的哈希排列成查找表的格式，当需要查找某幅图像时，计算待查图像的哈希与查找表做比较，可快速实现感知相似的图像匹配。例如，公安部门可利用哈希对罪犯指纹与指纹数据库做快速比对，加快案件的侦破。图像哈希还可作为边信息用于非盲水印的提取和作为依赖图像内容的密钥。

1 感知哈希的设计准则

在设计图像哈希算法时有两个重要的设计标准：稳健性和安全性。稳健性意味在使用相同的密钥的情况下，感知相近的图像应该产生相似或相同的哈希，这里哈希相似性一般用诸如欧几里德和汉明距离来测度。在实际的应用中作者会经常遇到这样的感知相近图像，如图像被多次A/D和D/A转换，图像被打印后扫描，图像在传输中被滤波加噪，图像中被加入水印等。安全性指在没有密钥的情况下，哈希值不容易被伪造或估计，它还必须满足下列两个性质：单向性，即假设已知哈希h和哈希函数 H (·)，很难由h= H(I)得到原始图像I；抗共谋性，即假设已知图像I和哈希函数 H (·)，很难生成第二副图像Iˆ满足 H (I ˆ)= H(I)。密码学认证算法基本满足这两个性质，但对于感知图像哈希算法而言，以上稳健性和安全性的要求实际上是相互矛盾和冲突的，如为了稳健性可能要选取图像处理后的不易改变的特征或关系，而对手可利用这些特征进行共谋攻击，所以图像哈希技术实际是在两者之间依据应用的要求寻找一个最佳的折中。

综上给出感知哈希的3个期望的性质，设I为原始图像， Iident为与原始图像感知相近的图像，Idiff为与原始图像感知相异的图像，H (I ,k)表示密钥为k的哈希函数，q为哈希序列的长度，θ1,θ2是满足 0 ＜ θ1,θ2＜1的任意值[1]：

（1） 感知稳健性

（2） 哈希的敏感性

（3） 哈希的不可预测性

第一条性质对应稳健性的设计要求，而第二、三条性质对应安全性的设计要求。如何设计满足这三条性质的图像哈希算法是一个开放的问题，有待分析和解决。

2 感知哈希发展简述

基于图像内容的感知哈希发展的历程并不长，从1996年Schneider在ICIP发表第一篇文章算起有 10年的时间，通过归纳可将图像哈希分为两个主要步骤，如图1所示。

图1 图像哈希的主要过程

第一步特征提取将2D的图像映射成1D的特征矢量（中间哈希），稳健的特征提取必须捕获图像感知内容，使感知相近的图像产生相近的中间哈希。第二步压缩主要功能有两个：一是将中间哈希变为更为紧凑的形式，便于存储或传输；二是通过量化、压缩、信道解码、聚类[3]、分布式源编码[4]等方式进一步减少对内容保持操作的敏感性，增强安全性。各种感知哈希算法的主要不同在于特征提取过程，它们主要分为基于图像统计的方法、基于关系的方法、基于变换域表示的方法、基于图像特征的方法。

1996年Schneider提出了第一个由灰度直方图构成哈希的图像认证方法[5]，作者首先将图像分块，然后计算每一块的灰度直方图，并用密钥加密后作为最终哈希。Venkatesan在2000年ICIP提出了一种基于小波分解后子带的图像统计的哈希算法[6]，他发现图像小波分解后形成的子带的均值和方差在经历一些感知保持操作后具有稳健性，算法首先将小波分解后的图像进行随机划分，然后提取每一区域的统计量，然后量化并输入Reed-Muller纠错码的译码器中产生最终哈希，算法具有一定的稳健性，但对于恶意的篡改不太敏感。Fridrich提出了一种DCT域的稳健哈希算法[7]，算法利用DCT域中低频系数与图像感知紧密相连的关系，将 DCT块映射到一个依赖于密钥的随机模板中，最终的结果与预设门限做比较产生哈希，算法可有效抵抗 JPEG、低通滤波等操作，但无抗几何变换的能力。Kozat提出了一种基于图像SVD分解的哈希算法[8]，将随机组成特征图像SVD后最强的特征矢量构成哈希，这种算法对几何变换具有一定的稳健性，但是有较高的误分类概率。

提取表征图像内容的特征量作为哈希是感知哈希构成的重要而有效的方法，Monga等提出了一种特征点的感知哈希方法[9]，他用Morlet小波捕获图像的特征点（线性结构的拐点），这些特征点表征了重要的视觉感知成分，同时在感知保持操作下保持一定的稳定性，Monga在压缩阶段也做了创新，他分别提出了用概率量化、聚类方法形成的最终哈希，实验结果表明方法对各种非恶意操作（包括几何变化）具有一定的稳健性，算法的缺点是耗时较长，同时对纹理简单的图像性能欠佳。

一种好的感知哈希算法应该对图像的感知保持操作具有稳健性，其中研究的难点在于对不改变图像感知内容的几何变换（如旋转、缩放、平移，简称RST）有较好的稳健性，现有的方法一般利用RST不变域的特征构成哈希，这样的一些变换域包括 Radon变换[10]、Fourier-Mellin变换[11]等，总体来说这类算法在理论上具有可行性，在实际应用的稳健性方面还有待进一步测试。为了实现抗几何变换的稳健特征提取，作者的思路是找到一种方法在图像生成哈希之前将几何变换对图像的影响去除，这种方法就是图像正则化。

3 图像正则化

图像正则化技术[12]广泛应用于计算机视觉和模式识别中，正则化的图像可以通过一个几何变换过程得到[13]，这个过程对任意的仿射变换（Affine Transforms）具有不变性，为了进一步描述这个过程，首先引入文中使用的若干概念：

设 f (x ,y)为 M× N大小的数字图像，它的矩和中心矩定义为 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)，式中为最终的正则化图像，参数满足预设的标准尺寸和

以上四步去除了几何偏移成分，更具体地说第一步消除了仿射攻击中的平移，第二、三步消除了仿射攻击中的x和y方向的剪切，第四步消除了仿射攻击中的缩放，使图像规整到一个标准尺寸。一幅图像与它的仿射变换有相同的正则化图像，参见图2。

下面进一步确定变换的主要参数：

（1） 剪切变换的参数β 参数β满足以下等式

（2） 剪切变换的参数γ 参数γ满足以下等式

（3） 尺度变换的参数α ,δ 通过预设的标准尺寸可以确定尺度变换的参数的幅值，它们的符号由确定。

4 感知哈希算法

以上描述的图像正则化过程产生了一个对任意仿射变换具有不变性的正则化图像，本节对这个图像进一步处理获得最终哈希。

（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个阶段产生最终哈希，所以可以简称为NWS算法。小波变换获得原始图像的粗略版本，其保留了图像的主要特征，SVD增强了算法对感知保持操作的稳健性，并进一步降低了哈希的长度。整个算法通过随机选取可重叠的子图像获得安全性，同时可通过在步骤三引入置乱运算进一步增强安全性。

图3 最终哈希的生成过程

5 实验结果

作者在实验中采用欧氏距离来测度两个图像哈希之间的差异，这里用 Iide表示与原始图像I感知相似的图像，用 Idif表示与原始图像I感知不同的图像，他们之间应满足

实验采用 256× 256的Lena、bridge、peppers作为测试图像，见图4所示。实验参数为 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]得到），其中许多属于仿射变换处理，可以看出算法对几何变换具有很好的稳健性，对其他感知保持操作也有很好的效果。表中最右一列为Kozat方法[8]对Lena测试的结果，对比发现NWS算法在几何攻击后有明显改善。算法对内容篡改具有敏感性，图6为原始的 boats图和内容篡改后的图像（桅杆等处被改），实验得到的欧氏距离为0.035，大于预设门限0.03。

图4 原始图像

图5 4种攻击后的图像

表1 在各种感知保持操作后的欧氏距离

在内容提取应用中要求良好的抗误分类能力，为了进一步测试算法的抗误分类能力，作者设计了如下实验，从图像数据库中随机选取100幅不同的图像，每幅图像分别与图5四种攻击处理后的图像和完全相异的图像作欧氏距离的比较，实验结果如图7所示，图7(a)～(d)分别对应四种攻击，图中实线代表与相异图像的结果，虚线代表与相似图像的结果。两线并不重叠，表明算法具有较强的抗误分类能力。

图6 内容篡改前后的图像

图7 Lena图像与100幅不同图像的欧氏距离和在100个不同密钥下与攻击图像的欧氏距离对比

6 总 结

本文提出了一种新的抗几何变换的感知哈希方法NWS，NWS用3个阶段来实现设计目标，图像正则化去除仿射变换的影响，小波变换抽取图像中重要的特征成分，奇异值分解提取局部的感知成分并实现哈希长度的压缩。实验结果表明了算法对几何变换具有良好的稳健性，对其他感知保持操作和恶意篡改也具有较好性能。通过在图像数据库中的对比实验，也证实了算法有较好的抗误分类能力。

未来的工作作者将进一步探索算法在基于内容的数据库搜索和图像认证中的应用，例如改良算法可以定位篡改的区域。

[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-），男，浙江余姚人，副研究员，博士，主要研究方向为多媒体安全，图像处理与理解。