基于向量点积与相似聚类的图像伪造检测算法

刘琴琴，邱建林

(1.南通理工学院 计算机与信息工程学院，江苏 南通 226000；2.南通大学 计算机学院，江苏 南通 226000)

0 引 言

被篡改的数字图像[1-3]会给人们带来不可估量的后果，例如：在新闻传播中，伪造的数字图像将会把虚假的信息传递给人们、在目标跟踪中，伪造的数字图像将会使得跟踪目标发生错误等[4,5]。因此，为了对伪造图像中的篡改内容进行检测，学者们提出了相应的图像伪造检测技术。

目前，数字图像伪造检测技术多种多样，例如Pooja[6]提出了基于SIFT的复制-粘贴数字图像伪造检测算法，实验结果验证了其算法的有效性。又如李晓飞等[7]提出了基于SIFT的伪造图像盲检测算法，利用SIFT方法提取图像特征，然后利用最近邻搜索方法完成图像匹配，最后利用欧氏距离对可疑块进行判定完成图像伪造检测。然而，由于SIFT方法提取的特征点中存在较多的冗余点以及错误特征点，导致算法对伪造图像的检测正确度不高，而且检测效率也不理想。对此，焦丽鑫等[8]提出了基于均值漂移的图像复制粘贴伪造盲检测，利用SURF对特征点进行提取，然后利用最近邻匹配方法消除冗余点进行特征匹配，最后利用均值漂移方法进一步细化伪造检测结果，但SURF算法中生成的特征描述子维度较高，导致算法效率不佳。又如杨仁青等[9]提出了基于分数傅里叶变换的数字图像复制-粘贴篡改检测算法，首先利用一级小波变换对图像进行降维，然后对图像进行分块，最后通过求取相邻块之间的特征矢量差完成图像的伪造检测，但是该方法对经过旋转等复杂篡改方法处理后的伪造图像进行检测时，检测效果不理想。

对此，本文提出了基于向量点积耦合相似聚类的图像伪造检测算法的研究。利用Forstner算子来快速提取图像特征。通过构建圆形区域与角度盘，求取梯度累计直方图，从而改进了SURF机制，获取特征描述符。利用特征描述符构成的向量点积，构造向量点积双阀值匹配模型，对特征点进行匹配。采用归一化互相关函数对匹配特征点进行相似性测量，完成特征点的聚类。最后，测试了所提技术的伪造检测精度。

1 本文图像伪造检测算法设计

本文设计的图像伪造检测算法过程如图1所示，主要由4部分组成：图像特征点检测、获取特征点对应的特征描述符、特征点匹配、特征点的聚类。

图1 本文图像伪造检测算法过程

1.1 图像特征点的检测

为了精确、快速获取图像的特征点，通过专家学者的研究涌现出了较多优秀的特征点检测方法，例如：SIFT算子、Harris算子、FAST算子以及Forstner算子等[10]。在众多的特征点检测算子中，Forstner算子具有特征点检测精度高以及检测耗时少的特点。因此，本文将引用Forstner算子对图像的特征点进行检测。Forstner算子在检测图像特征点时，首先将对各个像素点的Robert梯度值进行计算，其计算过程如下[11]

(1)

(2)

获取到Robert梯度值后，再从图像中获取尺寸为F×F的窗口，对该窗口的灰度协方差矩阵J进行计算[12]

(3)

令V表示J的逆矩阵，当V对应的行列式用trV表示，V对应的迹用DetV表示时，兴趣值Q和H的计算过程为

(4)

(5)

然后对备选特征点判定阀值Pdf和Pdg进行设定，不失一般性可将设定规则定义如下

(6)

最后利用兴趣值以及备选特征点判定阀值建立如下备选特征点判定规则

(7)

若某一像素点满足式(7)，则该像素点就被判定为备选特征点。接着建立一个适当大小的窗口，比较窗口内的所有备选特征点，最大值对应的备选特征点则被视为特征点[13,14]。

1.2 获取特征描述符

生成特征点的特征描述符由两部分组成，即特征点主方向的获取以及特征向量的获取。SURF机制生成的特征描述符具有尺度以及旋转不变特性。在此，将采用SURF机制获取特征点的主方向，然后构造同心圆区域以及角度盘，对SURF机制进行改进，以求取特征向量，从而获取特征点对应的特征描述符，以降低特征描述符的维度，使得算法的计算效率得以提高[15]。SURF机制生成特征描述符的过程如下。

选取尺度因子为φ的特征点作为圆心，对以半径为6φ的圆形邻域中的点，采用尺寸为4r的Haar小波求取其X以及Y方向上的Haar小波响应值[16]。用π/3大小的扇形窗口，以圆心为起点旋转扇形窗口，对窗口内所有的点进行Haar小波响应的向量求和运算，从而获得一个向量集合，向量集合中最长的向量则被判定为特征点对应的主方向[17]。

SURF机制中获取到特征点主方向后，将沿着主方向上构建一个尺度为20φ×20φ的矩形窗口，并将其均分为4×4个子域。对每个子域求取主方向上及与主方向垂直方向上的Haar小波响应，分别用dx和dy表示[17]。由此可得该子域的4个特征值： ∑dx、 ∑dy、 ∑|dx|、 ∑|dy|。 对应于4×4个子域就可形成4×4×4个向量。将这64个向量进行归一化处理后即可得到64维的特征向量。从而完成特征描述符的生成。

为了获取维度更低的特征向量，本文将对SURF机制进行改进，以提高算法的计算效率。具体过程如下。

首先，以任意一个特征点为中心构造一个如图2所示的同心圆区域。由图2可知，从内到外构建的同心圆的半径分别为3,2,2,1。这是因为离特征点越近的圆形区域对特征点的干扰越大，而离特征点越近的圆形区域旋转起来又会引起较大的旋转误差，为了平衡对特征点的干扰度以及图像旋转误差，故而将构造的同心圆半径设为3,2,2,1。

图2 同心圆区域

然后，以30度角为步长构建图3所示的角度盘。对每个同心圆计算角度盘所示的12个方向上的梯度累计直方图，并对所求取的梯度累计直方图进行高斯加权处理。

图3 角度盘

最后，将每个同心圆对应的所有梯度累加值进行降序排列，从而获得4×12个特征向量，对这些特征向量进行归一化处理即可得到48维的特征向量。

1.3 特征点匹配

对于m维的特征描述符I=(x1,x2,…,xm)T和J=(y1,y2,…,ym)T形成的角度λ(I,J)对应的余弦可表示为[18]

(8)

由式(8)可见，对于特征描述符I和J夹角的余弦可通过I和J的向量点积而得到。

对于任意一个待匹配特征点，可采用点积搜索法[19]在所有特征点中搜索出与其对应的具有最大点积MAXD的特征点，以及具有次大点积CMAXD的特征点。对于预定的双阀值KF1和KF2，可通过MAXD以及CMAXD构造如下向量点积双阀值匹配模型

(9)

若最大点积MAXD以及次大点积CMAXD满足式(9)，则判定最大点积MAXD对应的特征点与待匹配特征点为一对匹配特征点。通过实验得出KF1=0.3以及KF2=0.6时特征点的匹配效果较理想。

1.4 相似聚类

通过对特征点进行聚类可以对伪造图像中的篡改内容进一步精确定位，以提高图像伪造检测算法的检测精度以及正确度。本文将采用相似聚类的方法对特征点进行聚类，具体过程如下。

首先，设置Si=ki, ∀i∈H,H={i|i=1,2,…N}，Si表示聚类的集合，N表示样本的总数，在初始状态时，将每一个特征点都是为一个聚类样本。

然后，利用归一化互相关函数在集合Si中寻找与聚类样本kj,j∈i相似的聚类样本kp,p∈i且p≠j[20]

(10)

式中：kj(x,y)与kp(g,b)分别表示两个特征点，在所有的特征点中，当kj(x,y)与kp(g,b)形成的NCC值最大且大于阀值KFNCC时，即表示kp(g,b)是kj(x,y)的相似聚类，可将这两个聚类样本进行合并成一个聚类。

最后，迭代该求取相似聚类的过程就可完成特征点的聚类。

2 仿真实验分析

仿真实验硬件环境为：IntelI5-7500，3.5 GHz CPU，4 GB内存，500 GB硬盘。软件环境为：Windows XP操作系统，MATLAB 7.0仿真软件。实验采用对比方法进行，将文献[21,22]中的图像伪造检测算法设立为对照组，首先对本文算法以及对照着方法的图像伪造检测效果进行测试，然后再对不同算法的性能进行量化测试。

2.1 图像伪造检测效果测试

图4到图6分别为本文算法以及文献[21,22]中方法的图像伪造检测效果图，其中图4为对简单的复制-粘贴篡改方法伪造图像检测的效果图，图5为对缩放和噪声叠加篡改方法伪造图像检测的效果图，图6为对旋转和噪声叠加篡改方法伪造图像检测的效果图。从图4到图6可见，本文算法以及对照组算法对不同篡改方法伪造图像的检测都具有一定的成效，但是通过对比可见，本文算法的检测效果较对照组方法检测的效果较为优秀。具体表现为，在图4中本文算法的检测效果(如图4(e)所示)，较对照组算法的检测效果(如图4(c)和图4(d)所示)具有更高的检测精度，正确特征匹配点的数量最多，而且错误检测点或漏检特征点最少，而文献[21,22]两种技术的错误检测点的数量均要高于所提技术。尤其是在图5至图6中，本文算法的优势更大，其检测效果(如图5(e)和图6(e)所示)，较文献[21]的检测效果(如图5(c)和图6(c)所示)，以及文献[22]的检测效果(如图5(d)和图6(d)所示)具有更少的漏检点以及错误检测点。

图4 复制-粘贴伪造图像检测效果

根据上述伪造检测结果可知，本文算法具有更高的健壮性，对复制-粘贴篡改、缩放和噪声叠加篡改，以及旋转和噪声叠加篡改都具有更高的检测精度。因为本文采用了Forstner算子对特征点进行检测，能精确提取图像中的特征点，提高对噪声的稳健性，同时，本文利用旋转角度盘与同心圆区域来设计向量点积双阀值匹配模型来实现特征点的鲁棒匹配，提高其对旋转、缩放伪造的识别精度，利用归一化互相关函数对特征点进行了相似聚类，有效的提高了特征点的匹配正确度，以及鲁棒性。文献[21]中利用计算Hessian矩阵的方法提取特征点，然后利用欧氏度量的方法完成特征点匹配。由于Hessian矩阵提取的特征点中存在较多的伪特征点，对旋转篡改的稳健性较差，而且利用欧氏度量完成特征点匹配会存在较多的错误匹配点，故而使得文献[21]中图像伪造检测算法的检测正确度较低。文献[22]中利用提升小波变换获取低频分量，然后按像素特征对图像进行分块，最后利用偏移向量完成图像的伪造检测。由于按像素特征对图像分块会导致块图像的内容有重叠或者遗漏现象，导致算法的检测正确度以及鲁棒性下降。

图5 缩放和噪声叠加伪造图像检测效果

图6 旋转和噪声叠加伪造图像检测效果

2.2 量化测试

在此将通过对本文算法以及对照组算法的检测效率，以及检测正确度进行量化测试来衡量算法的性能。测试对象如图7所示。

图7 量化测试对象

ROC曲线能良好的体现算法的检测正确度，不同算法的ROC曲线如图8所示。从图8可见，本文算法较对照组算法具有更好的ROC曲线特性，说明本文算法的检测正确度最理想。究其原因为本文采用了Forstner算子对特征点进行了精确地提取，而且还采用了向量点积双阀值匹配模型对特征点进行了准确的匹配，最后还对特征点进行了相似聚类，从而使得算法的检测正确度得以提升。

图8 ROC曲线测试结果

表1为不同算法的检测效率，通过对比表1可见，本文算法的检测耗时为4.52 s，相对于对照组方法的检测耗时为最少。说明了本文算法具有较好的检测效率。因为本文采用了改进的SURF机制获取了较低维度的特征描述符，有效降低了特征描述符获取过程的计算复杂度，从而提高了算法的效率。文献[21]中采用SIFT机制获取的特征描述符维度较高，降低了算法的效率。文献[22]中对图像块进行奇异值分解获取特征向量矩阵，而且还需要进行字典排序。该过程计算复杂度较高，从而使得算法的效率下降。

表1 检测效率测试结果

3 结束语

为了实现对伪造图像中的篡改内容进行准确、快速的检测，本文提出了基于向量点积耦合相似聚类的图像伪造检测算法的研究。采用Forstner检测算子完成了对图像特征点的检测，由于Forstner算子对特征点的检测具有精度高等特点，使得算法的检测精度得以提升。利用构建的同心圆环以及角度盘求取梯度累计直方图，对SURF机制进行改进，获取低维度的特征描述符，使得算法的检测效率得到提高。利用特征描述符形成向量点积，接着构造向量点积双阀值匹配模型完成特征点的匹配。利用归一化互相关函数对匹配特征点进行相似性度量，完成特征点的相似聚类，对图像中的伪造内容进一步定位，提高了算法的检测精度。仿真结果表明，本文所设计的图像伪造检测算法不仅具有较高的检测正确度与效率，而且还具有较好的鲁棒性能。

参考文献：

[1]Mohammad Farukh Hashmi,Vijay Anand,Avinas G Keskar.Copy-move image forgery detection using an efficient and robust method combining un-decimated wavelet transform and scale invariant feature transform[J].AASRI Procedia,2014,3(9):84-91.

[2]Oussama Benrhouma,Houcemeddine Hermassi,Ahmed A Abd El-Latif.Chaotic watermark for blind forgery detection in images[J].Multimedia Tools and Applications,2016,75(14):8695-8718.

[3]Mahmoud Emam,Han Qi,Niu Xiamu.PCET based copy-move forgery detection in images under geometric transforms[J].Multimedia Tools and Applications,2016,75(18):11513-11527.

[4]ZHANG Ruifang,CHENG Xiaohui,SONG Zihang.Grey-Markov theory in blind detection of copy-move forgery in digital images by dyadic wavelet transforms[J].Journal of Guilin University of Technology,2014,34(4):775-781(in Chinese).[张瑞芳,程晓辉,宋子航.融合灰色马尔科夫理论的二进小波图像的复制-粘贴篡改检测算法[J].桂林理工大学学报,2014,34(4):775-781.]

[5]WANG Haoming,YANG Xiaoyuan.Detection method for JPEG image based on the difference of DCT coefficient histograms[J].Journal of Sichuan University(Engineering Science Edition),2014,46(1):41-46(in Chinese).[王浩明,杨晓元.一种基于DCT系数直方图差异的JPEG图像篡改检测[J].四川大学学报(工程科学版),2014,46(1):41-46.]

[6]Pooja Sharma.Detecting copy move forgery in digital image using sifts[J].International Journal of Latest Trends in Engineering and Technology,2016,3(7):1132-1138.

[7]LI Xiaofei,LI Pengfei.Blind detection algorithm for fake images based on SIFT[J].Journal of Changchun University,2014,24(10):1354-1357(in Chinese).[李晓飞,李鹏飞.基于SIFT的伪造图像盲检测算法[J].长春大学学报,2014,24(10):1354-1357.]

[8]JIAO Lixin,DU Zhenlong.Copy-paste image forgery blind detection based on mean shift[J].Journal of Computer Applications,2014,34(3):806-809(in Chinese).[焦丽鑫,杜振龙.基于均值漂移的图像复制粘贴伪造盲检测[J].计算机应用,2014,34(3):806-809.]

[9]YANG Renqing,BAI Zhengyao,YIN Liguo.Detecting of copy-move forgery in digital images using fractional Fourier transform[J].Journal of Yunnan University(Natural Scie-nces Edition),2016,38(1):18-22(in Chinese).[杨仁青,柏正尧,尹立国.基于分数傅里叶变换的数字图像复制-粘贴篡改检测算法[J].云南大学学报(自然科学版),2016,38(1):18-22.]

[10]Ma Chi,Zhu Yongyong,Tian Ying.Ear recognition based on Forstner and SIFT[J].TELKOMNIKA:Indonesian Journal of Electrical Engineering,2013,12(11):367-373.

[11]SHEN Xingxing,BAO Wenxing.The remote sensing image matching algorithm based on the normalized cross-correlation and SIFT[J].Journal of the Indian Society of Remote Senk-sing,2014,24(2):417-422.

[12]GUO Bingxuan,LUO Guangguang,XIAO Xiongwu.Forstner feature point classification and precise location method[J].Science Technology and Engineering,2016,16(16):73-78(in Chinese).[郭丙轩,罗光光,肖雄武.Forstner特征点分类和精确定位方法探讨[J].科学技术与工程,2016,16(16):73-78.]

[13]HE Yinan,GENG Juan,QIN Jun.Forstner feature point classification and precise location method[J].Remote Sensing for Land & Resources,2015,27(1):48-54(in Chinese).[贺一楠,耿娟,秦军.结合Forstner与NCC约束的UAV图像配准研究[J].国土资源遥感,2015,27(1):48-54.]

[14]Ma Chi,Zhu Yongyong,Tian Ying.Ear recognition based on Forstner and SIFT[J].Telkomnika-Indonesian Journal of Electrical Engineering,2013,11(12):269-278.

[15]LI Yan,LIU Nian,ZHANG Bin.FI-SURF algorithm for image copy-flip-move forgery detection [J].Journal on Communications,2015,36(5):1-12(in Chinese).[李岩,刘念,张斌.图像镜像复制粘贴篡改检测中的FI-SURF算法[J].通信学报,2015,36(5):1-12.]

[16]ZHANG Yong,WANG Zhifeng,MA Wen.Research image mosaic algorithm based on improved SIFT feature matching[J].Microelectronics & Computer,2016,33(3):60-64(in Chinese).[张勇,王志锋,马文.基于改进SIFT特征点匹配的图像拼接算法研究[J].微电子学与计算机,2016,33(3):60-64.]

[17]Oliveira SAF,Rocha Neto AR,Bezerra FN.A novel genetic algorithms and SURF-based approach for image retargeting[J].Expert Systems with Applications,2016,44(8):332-343.

[18]YAN Zigeng,JIANG Jianguo,GUO Dan.Image matching based on SURF feature and Delaunay triangular meshes[J].Acta Automatica Sinica,2014,40(6):1216-1222(in Chinese).[闫自庚,蒋建国,郭丹.基于SURF特征和Delaunay三角网格的图像匹配[J].自动化学报,2014,40(6):1216-1222.]

[19]Rajeev Kaushika,Rakesh Kumar Bajajb,Jimson Mathewc.On image forgery detection using two dimensional discrete cosine transform and statistical moments[J].Procedia Compu-ter Science,2015,70(1):130-136.

[20]OU Hongyu,CHEN Xi,SONG Yanhui.Detection of image duplication forgery based on local binary pattern[J].Computer Applications and Software,2013,30(9):170-172(in Chinese).[欧红玉,陈曦,宋燕辉.基于LBP的图像复制篡改检测[J].计算机应用与软件,2013,30(9):170-172.]

[21]Swapnil H Kudke,Avinash D Gawande.Copy-move attack forgery detection by using SIFT[J].International Journal of Innovative Technology and Exploring Engineering,2013,5(1):221-224.

[22]CHAI Xinxin,QIU Xiaohui.Image forgery detection algorithm based on lifting wavelet transform[J].Computer Technology and Development,2016,26(4):78-81(in Chinese).[柴新新,邱晓晖.基于提升小波变换的图像篡改检测算法[J].计算机技术与发展,2016,26(4):78-81.]