基于结构相似的改进SIFT图像复制-粘贴篡改检测*

张 露,林开司,张志宏

(铜陵职业技术学院 电气工程系，安徽 铜陵 244000)

基于结构相似的改进SIFT图像复制-粘贴篡改检测*

张 露,林开司,张志宏

(铜陵职业技术学院 电气工程系，安徽 铜陵 244000)

基于SIFT算法的复制-粘贴篡改检测方法中用广义2NN测试获得的匹配点对存在错误匹配，产生误匹配点，针对这一问题，提出了一种利用匹配点对间的结构相似性对广义2NN测试得到的匹配点对进行提纯，剔除误匹配点对，提高匹配正确率；误匹配点对的剔除，减少了匹配点对，使后续的聚类和几何评估操作减少了时间，由此提高了整个算法的执行效率；实验表明改进算法性能有较大提升。

篡改；结构相似；复制-粘贴；误匹配；提纯

目前，针对数字图像篡改检测主要有主动检测和被动检测，主动检测指在被保护图像中事先嵌入数字水印等信息，而被动检测依据图像本身的几何、物理或者统计等信息进行图像真伪的鉴别[1]。在被动检测中图像的复制-粘贴篡改是最常见的篡改方法之一，复制-粘贴篡改又分为两种：一种是将图像中的某一区域复制然后粘贴到该图像的另一区域，对粘贴区域的目标进行遮挡达到篡改目的；另一种是复制某一图像中的区域粘贴到另一幅图像中某一区域的篡改[2-4]，这里讨论的是同幅图像的复制-粘贴篡改。

SIFT算法是一种进行图像局部特征点提取的算法，它在尺度空间寻找极值点并提取该点位置和尺度不变量[5]，该算法对旋转、尺度缩放、噪声以及仿射变换等具有较好的鲁棒性，很多国内外学者利用SIFT或SIFT改进算法提取图像的特征点并进行匹配[6-9]，以此来判断图像是否进行篡改，并确定篡改区域。但是有些情况下一幅图像上发生多次复制-粘贴篡改，上述算法并不适用，针对多次复制粘贴的情况，Amerini[10]提出了一种称之为广义2NN测试(g2NN)的新颖的匹配方法，该方法能解决图像的多次复制-粘贴篡改。上述检测方法都是利用特征点间的欧式距离来衡量关键点的差异性和相似性，以确定特征点间的匹配。但各特征点向量分量之间的相关性、欧式距离并没有考虑，因此在特征点匹配时会产生较多误匹配点对[11]。本文在文献[10]的基础上考虑特征点间的结构相似性[12]，对通过广义2NN测试获得的匹配点对进行提纯，减少误匹配点，提高匹配精度和复制-粘贴篡改检测效率。

1 SIFT复制-粘贴篡改检测

1.1 特征点提取

被检测图像首先与不同尺度空间因子的高斯核进行卷积构成高斯金字塔，再用相邻尺度空间函数相减得到高斯差分(DOG)金字塔。在DOG尺度空间，每一像素点与同尺度8个相邻像素和上下相邻尺度18个领域像素比较获得初步极值点。再对初步极值点做三维二次函数拟合，剔除低对比度的不稳定极值点，对边缘响应点利用主曲率进一步剔除。接着对每个特征点为中心的领域像素的梯度方向进行梯度直方图统计，获得相应特征点的主方向。为保证旋转不变性，再以特征点主方向为坐标轴，将特征点用128维向量描述，即为特征点描述子。

1.2 特征点匹配

对于给定测试图像，确定图像局部块的相似性可通过比较每个特征点描述子间的欧氏距离，若测试图像有n个特征点，对每一个特征点计算与其他n-1个特征点间的欧式距离并按升序排列，用D={d1,d2…,dn}表示。不断迭代计算相邻欧式距离的比值di/di+1，直到该比值大于阈值T，如果停止迭代时i=k，则{d1,d2,…,dk-1}(2≤k≤n)对应的两个特征点匹配。通过不断循环上述操作，最终可以获得所有匹配点对。

1.3 聚类和几何评估

为了识别可能的篡改区域，还要对上述获得的匹配点的坐标做凝聚层次聚类。先将每个关键点作为一类，再将符合某些相似性准则的最近的类合并，直到所有特征点合并完，变为一类，或者在类之间的差异性达到某种类合并的停止条件，则停止合并。最终由各种差异性阈值来决定聚类数目，且这个阈值和类之间的连接方法决定聚类的好坏。主要的连接方法有单链接 (single linkage)、word链接(word’s linkage)和中心链接(centroid linkage)。

为了判断篡改图像上原始块和粘贴块之间发生的几何变换，还要进行几何评估。用RANSAC算法计算原始块和粘贴块之间特征点坐标的仿射变换矩阵H，再用H将所有匹配的特征点分成局内点和局外点，再做奇异值分解获得两个块之间的几何变换参数。

2 具有结构相似的改进算法

2.1 改进算法总体流程

被测图像经过SIFT算法进行特征点提取后，利用广义2NN测试进行特征点匹配，称为初匹配，匹配后产生的匹配点对有错误匹配，所以在进行后续聚类和几何评估操作前进行特征点提纯。提纯就是检测特征点对是否满足结构相似性准则，满足则保留，不满足则剔除。通过剔除误匹配点，减少匹配点数目，提高了正确匹配率，同时匹配点数目的减少也会提高几何评估中RANSAC算法的效率。改进算法的总体流程如图1所示。

图1 改进算法总体流程Fig.1 Improved algorithm general flow

2.2 特征点的结构相似性

图像特征点间的结构相似性是通过特征点的位置顺序和距离关系的信息来确定的。对于复制-粘贴篡改的图像，复制区域和粘贴区域的特征点的位置顺序存在对应关系，粘贴区域对象发生旋转操作也不会改变这种位置顺序；同时两个区域的尺寸存在对应关系，粘贴区域对象发生缩放操作也保持尺寸对应关系。

图2 结构相似示例Fig.2 Structural similarity sample

2.2.1 位序结构相似的具体判断

为使算法简单，这里只考虑了3个特征点构成三角形的情况，对于3个特征点共线的情况，三角形的面积为0，这时对应的特征点不剔除，因为满足共线的特征点多数情况下所占比例很少。

2.2.2 尺寸结构相似具体判决

步骤2 设s1、s2、s3分别为对应边长的比值，计算如下：

2.3 结构相似实现步骤

3 算法实验与分析

实验平台采用Windows10操作系统，CPU主频为2.20 GHz，4 G内存，编程环境为Matlab7.0和添加了Open CV库的Visual 2010。先在Visual 2010环境下用SIFT算法提取检测图像的特征点向量，再由Matlab7.0环境进行特征点匹配，并判断图像是否被篡改。

为验证改进算法对旋转、缩放、光照等变换的鲁棒性及对多次粘贴情况也有效，对5组测试图像分别用原算法和改进算法进行测试，测试中聚类连接采用word连接，方差阈值TH通过实验设置为0.01，各组图像大小都采用800600。用Noriginal和Nimprove分别表示原算法匹配点对数和改进算法匹配点对数；用Poriginal和Pimprove分别表示原算法和改进算法的匹配正确率；用Toriginal和Timprove分别表示从SIFT获取匹配点到几何评估结束所需要的时间。针对各种情况得到的实验结果如图3—图7。

图4 (组图2)粘贴目标放大比较Fig.4 Amplification comparison

图5 (组图3)粘贴目标放大旋转比较Fig.5 Amplification and rotating comparison

图6 (组图4)目标多次粘贴比较Fig.6 Multiple paste comparison

图7 (组图5)目标多次粘贴光照变化比较Fig.7 Multiple paste and illumination change comparison

为了便于比较，将表1中的正确匹配率和运行时间用折线图表示，如图8、图9所示。

图8 5组图像两种算法正确匹配率比较Fig.8 Five sets of image matching accuracy of the two algorithms

图9 5组图像两种算法所用时间比较Fig.9 Five sets of images of the two algorithms for the time comparison

表1 原算法和改进算法评价指标比较Table 1 Comparison of original algorithm and improved algorithm

通过上述5组实验分别比较了原算法和改进算法在旋转、放大、放大旋转、多次粘贴以及多次粘贴光照变换等情况的各项评价指标，从图3—图7直观上看，改进算法基本剔除了原算法中的错误匹配点对，从表1也能清楚地看到，改进后，匹配的特征点对大量减少，匹配的正确率大幅提高，甚至组图2(图4)和组图3(图5)匹配正确率达到100%，剔除了所有的错误匹配点。虽然匹配点对减少，但并不影响对图像复制-粘贴篡改的判断。由于匹配点对的减少，使得后续聚类和几何评估中RANSAC算法所用时间减少，使得最终的运行时间减少。由于不同计算机硬件设备在不同的工作状态下，对软件的运行速度会存在一定差异的影响，所以表1中的数据都是每组重复实验10次求平均值的结果。

4 结束语

在基于SIFT算法的图像复制-粘贴篡改检测中，采用广义2NN测试进行特征点匹配，由此产生了误匹配点对，所以提出了利用特征点对间的结构相似性对由广义2NN测试得到的匹配点对进行提纯，剔除错误匹配点对。由于误匹配点对的剔除，提高了匹配正确率，同时匹配点对数量的减少，使得算法后续聚类和几何评估中RANSAC算法的操作，运行时间减少，从而使整个算法的检测时间减少。最后针对旋转、放大、放大旋转、多次粘贴及光照变化等情况进行了实验，表明了改进算法在评价指标上的提高。

[1] 陈园园,于在河.数字图像被动取证技术综述[J].吉林大学学报(信息科学版),2014,32(6):689-698

CHEN Y Y,YU Z H.Survey on Passive Forensics Techniques for Digital Images[J].Journal of Jilin University ( Information Science Edition),2014,32(6):689-698

[2] KUO T Y,LO Y C,HUANG S N.Image Forgery Detection for Region Duplication Tampering[C]∥2013 IEEE International Conference on Multimedia and Expo (ICME),2013:1-6

[3] 张官亮,邹焕新,秦先祥,等.基于改进SIFT特征和图转换匹配的图像匹配算法[J].计算机应用研究,2013,30(9):2861-2864

ZHANG G L,ZOU H X,QIN X X,et al.Algorithm of Image Matching Based on Improved SIFT Feature and Graph Transformation Matching[J].Application Research of Computers,2013,30(9):2861-2864

[4] REDI J A,TAKTAK W,DUGELAY J L.Digital Image Forensics:a Booklet for Beginners[J].Multimedia Tools and Applications,2011,51(1):133-162

[5] 池静,张婷,杨振宇.基于SIFT和区域生长的图像复制粘贴盲检测算法[J].科技技术与工程,2013,13(4):917-925

CHI J,ZHANG T,YANG Z Y.An Image Copy-move Blind Detection Algorithm Based on SIFT Descriptors and Region Growing[J].Science Technology and Engineering,2013,13(4):917-925

[6] CHIHAOUI T,BOUROUIS S,HAMROUNI K.Copy-move Image Forgery Detection Based on SIFT Descriptors and SVD-matching[C]∥2014 lst International Conference on Advance Technologies for Signal and Image Processing (ATSIP),IEEE,2014:125-129

[7] LIU Bo,PUN C M.A SIFT and Local Features Based Integrated Method for Copy-move Attack Detection in Digital Image[C]∥2013 IEEE International Conference on Information and Automation (ICIA),2013:865-869

[8] 李昆仑,孙硕.基于改进SIFT算法的图像复制粘贴篡改检测[J].计算机科学,2016,43(6):179-183

LI K L,SUN S.Image Copy-Paste Tampering Detection Based on Improved SIFT Algorithm[J].Computer Science,2016,43(6):179-183

[9] LI K L,LI H X,YANG B,et al.Detection of Image Forgery Based on Improved PCA-SIFT[J].Compute Engineering and Networking,2014,277: 679-686

[10] AMERINI I,BALLAN L,CALDELLI R,et al.A SIFT-based Forensic Method for Copy-move Attack Detection and Trans-formation Recovery [J].IEEE Trans,Inf Forensics Security,2011,6(3):1099-1109

[11] 白廷柱,侯喜报.基于SIFT算子的图像匹配算法研究[J].北京理工大学学报,2013,33(6):622-627

BEI T Z,HOU X B.An Improved Image Matching Algorithm Based on SIFT[J].Transactions of Beijing Institute of Technology,2013,33(6):622-627

[12] 许可可,朱文球,郭富禄.基于结构相似的RANSAC改进算法[J].计算机工程与应用,2016,52(12):168-171

XU K K,ZHU W Q,GUO F L.Improved RANSAC Algorithm Based on Structural Similarity[J].Computer Engineering and Applications,2016,52(12):168-17

Improved SIFT Image Copy Paste Tampering DetectionBased on Structural Similarity

ZHANGLu,LINKai-si,ZHANGZhi-hong

(Department of Electrical Engineering,Tongling Vocation and Technical College,Anhui Tongling 244000,China)

SIFT is a commonly used matching algorithm,which is commonly used in image copy paste tampering detection.Based on the SIFT algorithm,the matching point pairs are obtained by the generalized 2NN test in the copy paste tampering detection method,there is an error match to produce the wrong match points.Therefore,this paper proposes a method to purify the matching points obtained from the generalized 2NN test by using the structural similarity between the matching points.The error matching points are eliminated and the matching accuracy is improved.Because the error matching point pairs are eliminated,the matching points are reduced.The time of clustering and geometrical assessment of subsequent operation is reduced,thereby the efficient execution of the algorithm is improved.The efficiency of the implementation of the entire algorithm is improved.Finally,the experiment shows that the improved algorithm has improved the performance.

temper; structural similarity; copy-paste; error matching; purification

TP391.9

：A

：1672-058X(2017)05-0031-06

责任编辑：罗姗姗

10.16055/j.issn.1672-058X.2017.0005.006

2017-04-12；

：2017-05-10.

安徽高等学校自然科学基金重点项目(KJ2016A712).

张露(1983-)，女，广西桂平人，讲师，硕士，从事数字图像处理研究.