基于超像素分割和SURF特征点的图像复制粘贴篡改检测

华秀茹 魏为民 栗风永

(上海电力大学计算机科学与技术学院 上海 200090)

0 引 言

由于网络技术的飞速发展，图像编辑软件被人们广泛使用，这使得图像篡改越来越普遍。数字图像作为现代社会的重要信息载体，其真实性尤其重要，越来越多的人研究数字图像取证[1]。数字图像取证包括主动取证和被动取证。主动取证需要事先对图像嵌入相关信息，如水印、签名等；被动取证不需要事先对图像操作，而是直接检测图像的真实性，因此具有更实际的意义。复制粘贴是图像篡改时最常用的操作，通过复制图像中部分区域一处或多处粘贴到图像的另外区域中。在对图像进行复制粘贴篡改操作时，往往还会进行一些处理操作，例如旋转、缩放、模糊、压缩、添加噪声等使得篡改区域更加真实。复制粘贴篡改案例如图1所示 ，导弹发射升空图使用了复制粘贴篡改操作。

图1 导弹发射图

研究人员针对复制粘贴篡改盲取证方法主要分为块匹配方法和特征点匹配方法。基于块的伪造检测方法将输入图像划分为重叠和常规图像块，通过匹配图像像素块或变换系数获得篡改区域。现有的分块的方法主要有：基于频率的DCT算法[2]、DWT算法[3]、FMT算法[4]；基于矩的Hu不变矩[5]、blur不变矩[6]、Zernike矩[7]；基于降维的PCA算法[8]、PCA-EVD算法[9]。由于块匹配算法提取特征向量维数较多导致计算复杂度高的问题，提出效率高复杂度低的特征点匹配算法。对于特征点匹配算法，是指在整个图像上提取和匹配图像关键点以抵抗一些图像变换，同时识别重复区域，如SIFT算法[10]、SURF算法[11]、ORB算法[12]。虽然特征点匹配算法提取的特征向量维数少、效率高，但存在因图像本身存在的平滑或相似区域导致特征点提取不精确而产生的对篡改区域漏检情况。

针对以上问题本文提出基于超像素分割与SURF算法结合匹配篡改区域。算法对图像进行SLIC超像素分割成独立不重叠块，提取图像的SURF特征点与特征描述子用以匹配。匹配特征点时将k-d树和BBF算法结合提高算法运行效率。最后用RANSAC剔除误匹配，二值化图像显示篡改区域。

1 复制粘贴检测算法

复制粘贴检测算法如图2所示。算法由超像素分割图像、特征点提取与匹配、剔除误匹配后处理操作三个阶段完成：

(1) 分割图像。对待检测图像SLIC超像素分割，分割成不重叠的小块。

(2) 特征点提取与匹配。提取图像的SURF特征点以及特征描述子，通过构建k-d树与BBF算法提高特征点匹配速度。

(3) RANSAC剔除误匹配，形态学腐蚀膨胀操作显示篡改区域。

图2 复制粘贴篡改检测示意图

1.1 SLIC超像素分割

已有的块匹配算法将图像分割成重叠的图像块，增加提取特征点向量的维数，降低检测效率。采用超像素分割将检测图像分割成不重叠的独立小块。在比较几种著名的分割方法后[13-15]，选择采用复杂度相对较低的简单现行迭代聚类SLIC超像素分割算法[15]。

对于待检测图像，SLIC超像素分割算法可以生成近似均匀、紧凑的块。通过设置图像所需块的个数参数即可得到独立不重叠的小块。为了避免分割时复制区域与粘贴区域出现在同一块中，对于图像数据集中的图片，设置超像素个数不少于100块。SLIC超像素分割的实例如图3所示。

1.2 特征点提取

特征点提取时使用Bay提出的SURF算法，该算法在特征提取时因使用积分图和降维的特征描述子，因此特征点提取速度快，且有较好的旋转、尺度、光照不变性。使用SURF算法提取图像特征点的步骤主要有构建Hessian矩阵、确定特征点方向、提取特征描述子。

(1) 构建Hessian。SURF算法提取图像特征点首先要构建图像的Hessian矩阵。Hessian矩阵是由多元函数对应的二阶偏导数组成的方阵。图像I(x,y)由高斯滤波后的Hessian矩阵表达式为：

(1)

式中：(x,y)为像素点位置；σ表示像素点对应尺度空间的尺度；Lxx(x,y,σ)、Lxy(x,y,σ)、Lyy(x,y,σ)分别表示图像上的点通过高斯函数与高斯二阶偏导数卷积的结果。通过计算图像中每个像素的Hessian行列式的值，以此来判断特征点。SURF算法使用方框滤波器代替高斯滤波器，以方框滤波器的近似模板加以计算。Hessian矩阵判别式为：

Det(H)=Lxx*Lyy-(ω*Lxy)2

(2)

式中：ω为加权系数，可以平衡使用方框滤波器近似模板时所带来的误差。方框滤波器及其近似模板如图4所示。

图4 滤波模板及其近似模板

图4中(a)、(b)、(c)表示高斯滤波模板在yy方向、xx方向、xy方向上二阶导数Lyy、Lxx和Lxy对应的值；(d)、(e)、(f)分别表示方框滤波器对(a)、(b)、(c)的近似。

为了改变方框滤波器的模板尺寸构造尺度空间，采用3维线性插值法找出极值点确定为特征点。

(2) 确定方向。以检测到的特征点为圆心，6s(s为尺度空间值)为半径画圆。计算落在60度扇形区域内点分别在水平方向和垂直方向的Harr小波响应值总和，并对点的响应赋权值，距离特征点越近，权值越大。以一定的步长滑动扇形区域，响应值最大的所属扇形区域即为该中心特征点的方向。扇形区域滑动示意图如图5所示。

图5 扇形区域滑动示意图

(3) 局部特征描述子。以特征点为中心，构建20s×20s的正方形区域，特征点的主方向为该正方形区域的主方向。将正方形区域划分成16个4s×4s的子区域，分别计算子区域25个像素点在水平方向和垂直方向上的Harr小波响应值，分别为水平方向值之和∑dx、绝对值之和∑|dx|，垂直方向值之和∑dy、绝对值之和∑|dy|，其中：dx表示像素点在水平方向(x方向)的Harr小波响应值；dy表示像素点在垂直方向(y方向)的Harr小波响应值。正方形共有16个子区域，故该特征点可以得到64个特征描述子。特征点描述子如图6所示。

图6 特征点的特征描述子

1.3 特征点匹配

特征点之间的距离通过计算特征描述子差异的L-2范数表示。提取的特征点构建k-d树，使用BBF算法搜索每个块中的每个特征点与其余块中特征点的最近邻居，若差值小于阈值(设置为0.04)则认为两特征点匹配。若一块中的部分特征点与另一块中的特征点匹配，则初步认为两块匹配，完成粗匹配。特征点提取与匹配示例如图7所示。

图7 特征点提取与匹配示例

块中特征点粗匹配时会由于图像中的平滑区域或相似区域之间像素的相似性而出现特征点误匹配现象，针对此现象要进行相对应的后处理操作。以图7为例，图片大小为800×600，检测到的特征点总数为1 727，匹配特征点数261，正确的匹配特征点数为256，占匹配特征点数98%，故可初步完成篡改检测的粗匹配。

1.4 剔除误匹配

剔除特征点匹配时出现的误匹配特征点对，采用RANSAC(Random Sample Consensus)算法剔除误匹配[16-17]。RANSAC是训练模型去除噪声影响的一种方法，其思想是使用尽可能少的点来训练模型，尽可能多地扩大模型参数的影响范围。

在匹配特征点集中随机选取4个匹配点对计算出矩阵模型，利用模型测试其余特征点匹配对，计算满足模型的特征点匹配对个数与变换误差，更新迭代矩阵模型与迭代次数，迭代出最优矩阵模型，消除误匹配点对，如式(3)所示。

(3)

式中:通常令h33=1来归一化矩阵;(x,y)表示特征点对位置;(x′,y′)为匹配的特征点对位置;s表示尺度参数。

1.5 后处理操作

二值化图像显示匹配块中的匹配特征点对。由于匹配特征点对的特征点间存在空隙，需要将独立的匹配特征点对之间变成可见的连通区域。形态学腐蚀膨胀操作可以填补空隙，连通特征点。形态学操作的完成需要使用结构元素，结构元素由0和1组成的矩阵构成，本文选用经典结构元素B，其表达式如下：

(4)

对于腐蚀和膨胀操作，本文选取先膨胀后腐蚀运算，即闭运算，具有填充特征点之间的空隙、连接临近特征点、平滑边界、消除误判的作用。针对二值图像A，进行闭运算的数学特征表达式[18-19]为：

A·B=(A⊕B)ΘB

(5)

式中：⊕表示膨胀运算；Θ表示腐蚀运算。

以图3(b)篡改图像为例，经二值化和闭运算后的检测结果如图8所示。

图8 图3(b)篡改检测结果

2 实验及分析

用MATLAB 2017a验证本文算法的有效性。原始图像集A选取文献[20]中的48幅原图像与MICC_600[10]中的152幅原图共200幅，选用文献[20]中的240幅篡改图像作为篡改图像集B，数据集中图像的尺寸为389×259到1 632×1 224之间。篡改图像主要由表1中的攻击方式以及参数构成。

表1 攻击参数设置

2.1 复制粘贴篡改检测

实验验证检测数据集中篡改图像的有效性，分别检测无后处理操作的普通篡改和经后处理操作的篡改，结果如图9-图12所示。

(a) 原图像 (b) 篡改图像 (c) 检测结果图9 普通篡改检测结果图

(a) 原图像 (b) 篡改图像 (c) 检测结果图10 抗JPEG压缩检测结果图

(a) 原图像 (b) 篡改图像 (c) 检测结果图11 抗添加噪声检测结果图

(a) 原图像 (b) 篡改图像 (c) 检测结果

(d) 原图像 (e) 篡改图像 (f) 检测结果图12 抗旋转和缩放检测结果图

图10显示本文算法有效检测出图像在JPEG压缩质量因子为90的篡改区域。图11显示篡改图片在添加噪声偏差为20的情况下本文算法检测效果。图12显示本文算法抗旋转和缩放的效果，其中：(b)是在原图像的基础上对篡改区域旋转60°；(e)是在原图像的基础上对篡改区域缩放比为500的篡改图像。从以上检测结果可看出，本文算法可以有效地检测出无后处理操作的普通复制粘贴篡改和经后处理操作的篡改。

2.2 准确率与虚警率

实验选择与文献[10]、文献[21]相比较。并选择准确率和虚警率作为测评标准。准确率和虚警率定义如下：

(6)

(7)

式中：TPR表示篡改图像数据集中被正确检测出篡改图像的概率；Tforged_true表示篡改图像数据集中正确检测出篡改图像个数；Tforged表示篡改图像数据集图像总数；FPR表示原始图像数据集中图像被检测为篡改图像的概率；Foriginal_false表示原始图像被检测为篡改图像的个数；Foriginal表示原始图像数据集图像总数。

对于本文算法和比较算法，用数据集A测试FPR，数据集B测试TPR，实验结果如表2所示。

表2 准确率和虚警率测试结果 %

可以看出，文献[10]中SIFT算法在检测出复制粘贴篡改的同时，由于特征点提取量多、特征向量维数大，导致虚警率较高。文献[21]中检测算法在特征匹配后使用区域增长算法降低虚警率。本文算法在粗匹配时因先对图像分割，以分割块为目标进行匹配提高了准确率，在精匹配阶段用RANSAC算法降低误匹配率。

2.3 检测时间

分别用SURF算法和SIFT算法进行特征点提取与匹配，其性能检测结果如图13所示。

图13 算法性能比较

本文算法提取图像SURF特征点与特征描述子，匹配特征点时用k-d树和BBF算法结合降低计算复杂度，提高效率，故检测效率高于SIFT算法。从图13可以看出，用SURF算法进行特征点提取与匹配时，在添加JPEG压缩、噪声、旋转、缩放等后处理操作时检测时间明显低于SIFT算法。

3 结 语

现有的复制粘贴篡改检测算法对于基于块匹配的算法因提取的特征向量多，存在算法效率低、花费时间长的问题；基于特征点匹配的算法特征向量提取较少，效率高，但存在漏检问题。针对以上问题提出基于超像素分割和特征点匹配结合的算法。算法对待检测图像用SLIC超像素分割成不重叠的小块，以块为单位进行SURF特征点粗匹配，特征点匹配时将k-d树和BBF算法结合提高检测效率，精匹配阶段用RANSAC算法去除误匹配，运用二值化、形态学腐蚀膨胀操作显示篡改区域从而达到匹配复制粘贴篡改区域的效果。实验表明本文算法在检测篡改区域时提高准确率，降低误检测率，同时提高检测速度。