技术交流 Technoloqv Discussion 数据通信2015.3 基于聚类分析和SIFT的图像感知哈希算法 古明涛张定会刘晶 (上海理工大学光电信息与计算机工程学院上海200093) 摘要:本文提出一种基于尺度不变特征变换(sIFT)和聚类分析(K-means) ̄#8合的感知哈希算法。其 中,基于不变特征变换用于提取图像的局部稳定特征点,聚类分析用来对特征数据经行压缩并得到图像感知 哈希。图像的相似性通过感知哈希值之间的汉明距离来测评。实验数据分析表明,该算法在图像尺度变换、各 种几何攻击、仿射变换以及JPEG等攻击中具有较好的稳健率。 关键词:尺度不变特征变换;聚类分析;感知哈希;图像认证 1引言 合于文本或软件认证的要求。然而,对于在网络上传 在互联网时代,伴随多媒体技术的成熟,使得图 播的数字图片,其在传播过程中会经历各种攻击,诸 几何变换、噪声污染等攻击,这些都会 像、视频和音频等多媒体数字作品的创作、存储和传 如有损压缩、输变得极其便利。近年来,分布式计算技术——云技 使原图像的比特位发生多位改变,从而了利用 h函数来进行图像认证的运用。但改变后的 术逐渐兴起,以手机为代表的终端与网络服务器可 传统Has以实现实时的数据同步,而其中以图像为代表的海 图像感知内容依然与原图像感知内容一致,由此提 量图片信息大量存在于互联网上并广泛传播,这就 出了图像基于感知内容不变的哈希技术,通常称为 造成网络图片的隐私性,安全性问题。同时图像编辑 图像感知哈希,即内容认证。感知哈希技术与数字水 软件和各种成熟的图像处理技术可以对图像数据进 印技术相比较在认证方面有长足的优势,它不需要 行高质量伪造和篡改。种种这些都造成图像数据的 预先嵌入水印信息,也就不会修改文件的内容,注重 可信度逐渐降低,甚至失去其法律效应。也正是由于 内容检测的质量,因而比数字水印技术有着更为广 数字图像的极易编辑性【”,从而数字图像认证技术应 泛的应用场景。运而生。 图像认证技术根据内容的更改情况可分为完整 2感知哈希 一 性认证和内容认证。其中完整性认证不允许图像有 2.1感知哈希技术介绍 一比特位的改变,这种认证一般适用于非常严格和 一感知哈希技术是将数字图像中关键数据映射成 非常机密的情况下。这种认证要求可以借鉴传统密 个简短长度数字序列,是一种基于图像视觉内容 码学中的消息认证技术,它是利用Hash函数(又称散 压缩形式的操作,我们将得到的哈希序列称为哈希 列函数)对图像数据生成固定大小的摘要来进行图 值。根据人类视觉系统对不同内容图像的反应,感知 像消息认证。Hash函数中几种重要的算法包括MD5 哈希技术使得不同内容的图像具有不同的感知哈希 和SHA一1(美国的FIPS PUB 180—1标准)等,它们对每 值,内容相似的图像具有相似的哈希值 。感知哈希 一比特的信息改变都非常敏感,这种敏感性比较适 算法一般分为以下两个步骤: 36 2015.3数据通信 技术交流 Technoloav Discussion (1)提取一个关键依赖型的特征向量,即中间哈 加以完善。下面介绍sIFT算法的具体实现: 希,这个过程我们称之为特征提取; 终哈希值。 第一步是尺度空间的构建,将图像与多尺度的 y,kS)=c(x,y,kS) , k=l,2…S (2)将第一步提取的中间哈希压缩量化,产生最 高斯函数卷积获得图像的尺度空间表示: ,其中第一步产生可以代表图像感知内容的中问 哈希是最为关键的一步。 2.2感知哈希技术的分类 其中 ,y)代表图像腔间的坐标, 为尺度因子, 的大小决定图像的平滑程度。大的 值对应粗构尺 度(低分辨率),小的 值对应精细尺度(高分辨率)。 根据不同的分类标准,图像感知哈希算法的划 然后根据下式构造高斯差分尺度空间(DOG 分方法不一样,如我们可以从功能应用角度划分,可 scale-space): 分为面向识别功能的哈希算法和面向认证功能的哈 希算法;如果从空间域角度划分可以分为时域哈希 D , 6)=(G , = , 一G , 6)) ,),) 一 ,算法和频域哈希算法;如果基于两个大类去区分,我 y) 为了寻找尺度空间的极值点,每个采样点都要 们可以根据图像特征提取的方法分为两类:一种是 和它所有相邻点比较,如果一个点在DOG尺度空间 基于图像全局特征的方法,另一种是基于图像局部 本层8个相邻点以及上下相邻尺度对应的个点共26 特征的方法。其中,基于数字图像全局特征提取的方 点中都是最大或最小值时,就认为该点是图像在该 法包括利用图像的亮度均值、亮度方差、DCT(离散余 尺度下的一个特征点。弦变换)系数、DWT(离散小波变换)系数和各种直方 接着精确定位极值点。通过拟合三维二次函数 图统计信息等构造哈希值的方法 。这类方法对 以精确确定关键点的位置和尺度(达到亚像素精 JPEG压缩、加澡、滤波等非几何攻击具有较好的鲁棒 度),同时去除对比度的关键点和不稳定的边缘响应 性,且算法整体复杂度低。但是对尺度变换、旋转、剪 点,以增强匹配稳定性、提高抗噪声能力,这里我们 切等几何攻击的鲁棒性不足。 使用近视Harris Corner检测器。空间尺度函数泰勒展 基于数字图像局部特征的方法较第一类方法对 开式如下:各种几何攻击有较强的鲁棒性,但特征点之间的同 步关系容易发生改变,增加了算法中的量化、匹配模 讹 一 6)+ 肿丢 絮 (1) 块的设计难度[5-6]。所以该类算法较第一类算法复杂 度明显提高。而现实中,人类视觉系统对图像的各种 几何攻击具有很高的容忍性,所以图像的各种感知 算法应该能对各种几何攻击有很好的鲁棒性。本文 所采用的(Scale—invariant feature Transform)就是基 对(1)式求导,并令其为0,得到精确的位置: aD aD 一 将叠代人(1)式,只取前两项可得: D(露):D ,,,, +— 1 露 于图像局部特征点的第二类方法。它能应对各种几 何攻击,特别是它在尺度变换方面具有很好的鲁棒 性。以下对其详细介绍。 若 (露)I>0./03,则保留该特征点,否则丢弃。然 后检查主曲率的比值,根据阀值保留小于阀值的特 征点,本文采用默认值阀值。 最后为每个关键点制定方向参数。利用关键点 3 SIFT算法及聚类分析 尺度不变特征变换(sIFT)是用于图像处理领域 的一种组合尺度不变区域检测的图像局部描述子, 向参数,使算子具备旋转不变性: 这种描述具有尺度不变性,可在图像中检测出关键 m ,y)=X/ +l,y)— 一1, )+ ,),+1)一£ ,y-1)) 点,同时它也是一种梯度分布描述子。所以它具有图 O(x,y)=atan2((L ,y+1)一L@, 一1) +1 一 —1 像旋转和尺度变换的不可变性,同时对仿射变换、亮 式中为 ,),)处梯度的模值和方向公式, 所用的 度变换及噪声等也有较好的鲁棒性。它是由David Lowe首次发表于计算机视觉国际会议,并在2004年 尺度为每个关键点各自所在的尺度。至此可得到图 领域像素的梯度方向分布特性为每个关键点制定方 37 技术交流 Technoloav Discussion 数据通信2015.3 像的关键点,每个特征点包三个信息:位置、所在尺 为: 度以及方向。可最终确定一个/'t X 128维向量的SIFT 特征描述,n为特征点数目。 R= 1,R2,…R }R∈Z 其中,Ri表示图像中一个特征点向量, 表示所 有特征点向量的集合,z表示一个1 X 128维向量。 聚类分析指将物理或抽象对象的集合分组为由 类似的对象组成的多个类的分析过程。它是一种重 要的人类行为。聚类是将数据分类到不同的类或者 簇这样的一个过程,所以在同一个簇中的对象有很 大的相似性,而不同簇间的对象有很大的相异行。所 以我们可以采用聚类分析将提取的特征向量进行分 (3)将尺中各行相加如公式(2),得到一个1 X 128 维的中间哈希向量日。通过对特征矩阵各行元素求和 实现了对特征矩阵数据的压缩的目的。 日( )= R 1≤ ≤128 j=l (2) 类简化对比分析。它能对大量数据根据具体要求达 到分类聚合的目的,聚类分析已广泛应用与数据图 像处理的各领域,能很好适应图像数据的聚类分析。 (4) ̄lJ用聚类分析对日经行量化,这里采用基于 欧几里得度量来划分从而决定簇类,并根据聚类结 果的质心点 大小将其所在类c的数值映射为1或0 如公式(3)。最后得到最终的128位哈希值 。 4算法描述 本文感知哈希算法也是分为特征提取和压缩、 h(i)={0l 其中M1<M2 映射两个步骤,第一步利用SIFT提取局部特征点,将 (5)(可选)根据实际应用,可以产生由密钥控制 图像映射为特征矢量(中间哈希)。第二步利用聚类 的伪随机序列,再将最终哈希值映射到伪随机序列 分析将中间哈希进一步映射为最终哈希值。对于第 中,从而保证安全性。本文主要分析哈希值生成算 步特征提取就是要捕获图像的感知内容。而第二 法,安全.f生不做详细分析。 阶段是信息的压缩和分类,强调的是整体信息的压 一缩表示。本文算法流程图如图1所示: 5实验及性能分析 5.1匹配分析 本文采用汉明距离来测度图像之间的相似性。 具体识别匹配方法如下: 首先利用算法得到待测图像的最终128位图像 哈希h ,然后计算 r与原图像的128位图像哈希h。之 问的汉明距离Dis: Dis=hr--ho 图1算法流程图 本文提出的感知哈希方法具体描述如下: 其中,符号“一”规定为计算汉明距离运算符。根 据计算两幅图像的哈希值间汉明距离Dis进一步计算 两幅图像的相识度Sam为: (1)对原始图像进行预处理,其中包括将彩色图 s一 (3) 像灰度化、亮度处理,并采用双三值插值法将图像统 规格化为kxk,得到图像 ,本文中我们取k=256。 其中,Sam取值在0一l之间,当Sam大于预设判决 (2)对图像厶妯做SIFT特征提取,用Lowe的缺省参 门限 时,此处取 为0.9,待测图像与原图像被认定 数算法提取的局部特征点不是很稳定,同时数目较 为相识,否则认为两幅图像为差异图像,则图像被篡 多。由于SIFT特征是在多尺度空间下建立的,随着尺 改成功。 一度的增大,图像通过高斯卷积被平滑的程度也不断 5.2识别率测试 增大。因此在高尺度空间下能够提取的特征点具有 为了测试该算法的识别能力,我们选取人物、建 更强的稳定性,同时还可以通过调整峰值门限和边 筑、风景、新闻图片等共10类100幅彩色图像。我们使 缘门限来控制产生的特征点。最后得到的特征矢量 用StirMark Benchmark软件对图像库的所有图像进 38 2015.3数据通信 技术交流 Technolocw Discussion 表3受攻击图像识别率测试 攻击类型 TestPSNR 行各种攻击,各种攻击参数如表1所示。 表1 图像各种攻击方法参数 攻击类型 TestPSNR(信噪比) 识别率 92-35% 89.23% 攻击参数 0:1O:100 具体参数参见表2 T st A仿ne Test AddNoise TestAffine(仿射) _88.46% Test JPEG TestAddNoise( ̄ll澡) 96-37% 91.29% 87_36% 0:5:20 20:10:1oo TestMedianCut TestJPEG(压缩) _TestConvFiher _TestMedianCut(中值滤波) iflter size=3 5 7 9 ifherl=3 3 9,l 21,244,1 21 TestCropping 76.35% 90.68% Test Rescale TestRotation _TestConvFilter(卷及滤波) filter2=3 3 9,0-1 0,一1 5—1,0—1 0 95.34% 6643% 78.27% 86.59% TestCropping(剪切) ration(%)=50 60 75 ration(%)=50 75 90 l 10 150 200 Angles(℃)=-2-1—0.5 0.5 1 2 5 10 15 TestRotationCrop Test Rescale(尺度调整) TestRotationSeale _TestRemoveLines _TestRotation(旋转) 3045 90 要研究方向是哈希算法在组合攻击中的稳健性。 angles(oC)=一2-1-0.75-0.5-0.25 O 21 TestRotationCrop(旋转剪切) _0.5 0.75 l 2 6结论 基于SIFT提取的特征属于图像的局部特征,它 TestRotationSeale(旋转尺度) _angles(oc)=-2-I-0.75-0.5—0.25 O.2-' 0.5 0.751 2 对旋转、尺度变换、亮度变化具有不变性,在噪声攻 击及滤波方面也保持了一定的稳定性。本文提出了 基于聚类分析和SIFT的感知哈希方法,首先利用 SIFT算法提取图像的特征点,然后对提取的特征点 向量经行压缩,并利用聚类分析得到最终的哈希。实 Test_RemoveLines(删除行列) Frequency=l0:10:100 其中有关仿射变换的参数说明如下: 表2仿射变换参数说明 \参数 变 b d d \ 1 0 0 0.01 l l 1 1 O 0 验室分析表明该算法对于各种图像处理操作如旋 转、滤波、噪声、JPGE压缩等攻击有较好的稳健性。下 一Y—shearing l l 0 0.01 0 0 0 O.05 步的研究方向主要是提高感知哈希算法对各种组 0 0 O X—shearing 1 1 O05 .0 0 0 合攻击的稳健性。 参考文献 【1】YeungM,MintzerF.Invisible watermarking for image veriif— 00l 0.O5 0 0 0.01 0O5 .1 l XY-shearing 1 仿射变换公式为: l ’I=l。 6I lI+Id J Y’l『c dI lYI I e I cation[J].JoumalOf Electronic Imaging,1998,7(3):578—591 [2]张敏.基于图像内容认证的感知哈希算法的研究[D].湖南: 湖南大学.2010 所用变换方式及参数说明如表2所示。 然后根据本文提出的感知哈希算法计算出受攻 击后的所有数字图像的感知哈希值,并根据公式(3) 计算与原图像的相似度,攻击后的识别率如表3所 示。 【3]FRIDRICH.J.Robust bit extraction fom irmages【C].IEEE International Conference on Multimedia Computing and System,1999,2:536—540 『41孙悦,高隽.组合NMF和PCA的图像哈希方法lJJ.电子测量与 仪器学报,2009,23(5):52—57 [5]刘兆庆,李琼,刘景瑞,彭喜元.一种基于SI盯的图像哈希 从实验数据来看,本文算法在以上攻击识别中 维持了很好稳健性,特别在尺度调整及几何攻击中 表现很好的稳健性,同时算法在JPEG压缩中也变现 算法[J].仪器仪表学报,2001,32(9):2024—2027 【6】ROY S,ZHU X,YUAN J.On preserving robustness false alarm tradeof in media hashing[C】.Visual Communica— tions and Image Processing,2007,6508,part 1:65081C 出很好的稳健性。但发现算法对RotationCrop、 RotationScale两种类型的组合攻击识别率较低,说明 该算法对组合攻击稳健性不是太好,下一阶段的主 39 ■ g scu Journal of Computer Vision, key points[J].International features from scale—invariant 【10]武小红,周建江,李海林等.基于非欧式距离的可能性C均值 【7]Lowe G D.Distinctive image 聚类叨.南京航空航天大学学报,2006,38(6):701-705 2004,60(2):91-1 10 【8]邓荣峰,李熙莹.基于SI丌特征匹配的稳健图像拼接算法 『J].计算机应用,2009,29(6):219—221 [9】左浩,李雯.改进的PcM聚类算法在图像分割中的应用fJ]. 作者简介:古明涛:1990.03,男,上海理工大学光电信息与计 计算机与数学工程,2010(11):148—151 算机工程学院硕士研究生,研究方向为信息安全。■ (上接第25页) 0R rule 检测性能。 参考文献 姗 雾 畦 [1]Fe deral Communications Commission.Spectrum Policy Task Force.Rep.ET Docket no.02-135,Nov.2002 [2]Reisi N,Jamali V,Ahmadian M,Salari S.Cluster-based CO— operative spectrum sensing in cognitive radio networks under log—normal shadow—fading【C].Electrical Engineering(ICEE), 。 —I1 — — — — — — }—_2 SN刚B) Iranian Conference.201 1:1-5 [3]Danijela Cabric,Shridhar Mubaraq Mishra,and Robert W. Brodersen,Implementtiaon issues in spectrum sensing for cog— 图5 0R准则下全局检测概率和信噪比的关系曲线图 nitive radios『J],Proceedings of Asilomar Conference 2004, 100%,这也是信号能量增加所致。从图中还可以看 越多,全局检测的概率也越大。图5中在使用OR准则 是使用AND准则还是OR准则,均可以通过增大信噪 比或增多节点用户数来提高全局检测概率,从而达 到改善检测性能的目的。 2004:772—776 出,在相同的信噪比条件下,参与检测的节点用户数 l41郑轶,谢显中,杨黎丽.基于SNR ̄L较的认知无线电协作频 谱检N[JI.电讯技术,2009(8):13—17 机械与电子,2009(1 11:95—96 5]秦继新,方勇,张士兵.认知无线电中的频谱感知技术 情况下,其规律与使用AND准则时类似。因此,无论 [【6】温志刚.认知无线电频谱检测理论与实践【M】.北京:北京邮 电大学出版社,2011:63—64 【7]孙德奇,孙鑫淼.Gamma函数的几个性质【JJ.黑龙江科技信 息,2008(31):180 5结论 认知无线电在保证己授权用户不受影响的情况 [8]梁红玉,陈宏滨,赵峰.认知无线电协作频谱感知技术综述 lJ].广西通信技术,201 1(2):38—43 下可以提高频谱利用率,其中关键技术之一就是频 谱检测。本文就单节点的能量检测方法和基于AND 和OR准则的多节点协作频谱检测方法进行了研究, 研究结果表明:对于单节点频谱检测,可通过增大信 作者简介:王思璇,女,江苏大学计算机科学与通信工程学院 噪比或牺牲虚警概率的方法来改善检测性能;对于 硕士研究生,主要从事认知无线电研究;郭坤祺,男,江苏大学 硕士生导师,主要从事无 多节点协作频谱检测,无论是使用AND准则还是OR 计算机科学与通信工程学院副教授,准则,增大信噪比或增多节点用户数均能有效改善 线通信、移动计算、信号与信息处理等的研究。一 40 1