1 引言

复制-粘贴篡改是一种常见的数字图像篡改手段,通过复制一幅图像中的某个区域,粘贴到同一幅图像的其他区域,以隐藏重要目标或造成某种假象。为了达到更好的视觉效果,篡改者往往还会在篡改过程中进行一些诸如旋转、平移、缩放和镜像等几何形变操作,从而增加篡改图像的真实性,增加了篡改检测的难度和复杂度。图像复制-粘贴篡改的盲取证技术大致分为两类:基于图像块的检测法和基于图像特征点的检测法。基于图像块的篡改检测方法研究中,Fridrich等^[1]首先提出一种基于离散余弦变换(DCT)的块匹配检测算法,对篡改后的图像加入噪声或进行多重压缩后,不能检测出复制-粘贴篡改区域。Cao等^[2]提出了改进的基于DCT系数的盲鉴别算法,利用DCT系数的平均值提高检测率,但对几何形变后处理操作的鲁棒性较差。Popescu等^[3]利用主成分分析(PCA)的方法对图像进行复制-粘贴篡改区域定位,该方法对加性噪声和有损压缩有较好的稳健性。然而上述算法均不能检测出经旋转和缩放等几何变换的复制-粘贴篡改区域。Ryu等^[4]提出基于泽尼克(Zernike)矩阵的复制-粘贴盲检测算法,该算法对噪声有较好的鲁棒性,解决了固定角度旋转不变性,但对其他几何变换的检测效果较弱。Davarzani等^[5]采用局部二值模式(LBP)进行复制-粘贴篡改检测,对几何变换和模糊噪声等后处理操作有较好的鲁棒性。Pun等^[6]利用小的超像素替换特征点作为特征块,将具有相似局部色彩特征的相邻块合并到特征块中以生成伪造区域,该算法对多区域复制-粘贴篡改检测有较强的鲁棒性。Lai等^[7]将计算得到的特征向量总和放在第一列以构造新的矩阵,按照第一行排序,执行搜索直到第一列中的差值大于阈值,对噪声和JPEG格式的图像压缩有很好的鲁棒性。

基于特征点的图像篡改检测研究中,Huang等^[8]提出了基于尺度不变特征变换(SIFT)特征点的篡改检测算法。Amerini等^[9]改进了SIFT特征提取的算法,先提取待测图像的SIFT特征并进行匹配,再对匹配的特征点对作分层聚类,该算法可解决多区域复制-粘贴篡改检测。Bay等^[10]提出基于加速稳健特征(SURF)点的篡改检测算法,能够检测特征点周围的纹理特征,检测性能比SIFT好。上述浮点型描述子本身不具备镜像不变性,不能用于镜像翻转的复制-粘贴篡改检测,Guo等^[11]提出了一种基于镜像不变特征变换(MIFT)-SIFT的特征提取算法,可检测出经镜像翻转的复制-粘贴篡改图像。Jaberi等^[12]改进了MIFT特征提取算法,能够有效地检测出经镜像变换的复制-粘贴区域,使算法更加完善。Warif等^[13]提出了基于对称性尺度不变特征变换(SIFT-Symmetry)的检测算法,其是将基于SIFT的特征提取算法与对称匹配方法相结合,对常见的几何变换都有较好的鲁棒性。Cozzolino等^[14]提出基于块匹配(PatchMatch)的复制-粘贴篡改检测算法,虽能够检测到经镜像翻转的复制-粘贴篡改图像,但对多区域和多区域镜像篡改有较高的虚警率。Yang等^[15]使用一种新的特征点分布策略,在整个图像中均匀分布SIFT特征点,最后使用匹配特征描述符进行图像取证。吕颖达等^[16]根据像素的灰度结构定位可疑块对,再进行基于对数极坐标变换的相位相关,从而定位复制-粘贴区域。朱叶等^[17]提出基于彩色LBP算法,利用改进的kd树和超平面划分标记分类,并应用形态学操作去除误匹配,可有效地检测隐蔽性复制-粘贴篡改区域。

现有的图像复制-粘贴篡改检测方法能够检测旋转、缩放、镜像和多区域(多重)等篡改问题,但极少有人提到如何检测多重复制-粘贴镜像篡改图像。因为复制-粘贴篡改区域经镜像翻转后,从该区域提取出来的特征描述符内部改变了原有向量的特征排序,不能和原有的特征描述符匹配,而且图像中篡改区域被复制后在多处粘贴,增加了检测的难度和复杂度,检测结果通常会遗漏某些复制-粘贴区域;另外,多区域镜像篡改会产生一个原始区域和多个镜像篡改区域,检测结果很容易会将多个重复的镜像篡改部分当作多区域篡改部分来进行检测,造成篡改图像不能被正确检测。针对上述问题,本文提出一种基于PatchMatch的图像篡改检测算法,先提取图像的BRISK(Binary Robust Invariant Scalable Keypoints)二值特征描述子,接着利用PatchMatch算法计算特征描述子间的偏移量,借助传导策略来随机搜索匹配块,最后通过计算拟合误差来精确定位篡改区域,移除误匹配点。相比现有的其他图像复制-粘贴检测算法,实验证明所提算法能够实现对经旋转、缩放、多区域、镜像和多区域镜像等复杂几何操作的篡改检测,在计算效率和检测准确率上有明显改善和提升。

2 基于PatchMatch的图像篡改检测算法

2.1 提取特征点及生成特征描述子

针对待检测图像,利用所提算法提取BRISK^[18]局部二值特征描述子,优点是同时具有尺度不变性、旋转不变性和镜像不变性。图像中篡改区域经复杂的几何形变后,被复制的源区域和目标区域的BRISK特征描述子仍存在较强的匹配能力。

BRSIK算法中对特征点的检测首先需要建立图像的尺度空间,为了对篡改区域尺度变化具有不变性,使用自适应通用加速分割检测(AGAST)算法^[19]在每个尺度空间内进行特征点检测,并对同层及上下两层进行非极大值抑制,最后对每个检测的极大值进行子像素和连续尺度优化,能够得到具有亚像素级精度的特征点。

利用高斯滤波器对以特征点为中心的圆形采样模型进行滤波,在采样模型中选择随机采样点对计算灰度差以得到二值特征向量。BRISK二值描述子在计算时需要先计算特征点的主方向,再将特征点的图像特征区域进行旋转,经旋转后得到新的采样区域并进行强度比较级联运算,最终形成512 bits旋转不变的特征描述子,使得篡改区域的旋转具有不变性。

2.2 特征匹配

在所提算法框架中,利用PatchMatch算法进行相似图像块搜索是复制-粘贴篡改检测的核心步骤。PatchMatch^[20]是一种基于随机初始化的近似最近邻(ANN)搜索算法,在图像中通过随机采样和邻域传播搜索快速查找和匹配最佳图像块,该算法现已应用于图像修复^[21-22]和立体匹配^[23]等图像处理和计算机视觉领域。针对复制-粘贴篡改图像问题,假设该图像区域的大小为M,每个匹配的小图像块中含有m个像素点,传统暴力搜索算法的复杂度为OmM2,PatchMatch算法虽能够提高搜索效率,但传播阶段每次只能搜索匹配到两个方向的偏移量,且提取到RGB颜色模型的值易受JPEG格式的压缩、噪声和常见几何形变的影响,对于经过旋转、缩放、镜像、多区域和多区域镜像等几何形变的篡改操作的检测效果不好。基于此,提出改进的PatchMatch技术计算特征描述子间的最近距离即偏移量,通过特征描述子间的匹配来定位相似图像块,同时借助传播和随机搜索策略可大幅降低处理时间,还能生成准确而规则的偏移域。在特征提取阶段提取特征不变性的描述子,是为了避免其受几何形变的影响,同时在特征匹配初始化阶段能够获得一个比较好的初始匹配结果,进一步提高算法的准确率。在复制-粘贴篡改区域会存在旋转和缩放等复杂的几何变换操作,匹配过程中,待匹配图像块计算其周围空间k个相邻图像块间的偏移量,描述不同的线性偏移域,对应旋转变化和尺度变化,所提算法取k=7,不会因匹配数过多而耗费太长时间,使得准确性和速度达到平衡。为了保证计算的准确率,在传播过程后加入随机搜索过程,在一个逐渐缩小的搜索框中,每次寻找一个最佳匹配值,再将整个计算过程中的最近距离及所对应的块作为待匹配块的ANN的最近邻域(NNF)。对ANN进行迭代更新操作,使算法的复杂度降低到O(mMlg kM),随之减少了计算时间,提升了匹配的准确性。该局部搜索算法的图像块是基于一个特征点,进而形成一个方形的搜索图像块,所提算法指定图像块的大小为32×32,一方面图像块中包含了特征描述子信息,另一方面较好地保留图像自身的结构信息和纹理信息,最终获得的篡改检测效果更好,图像更平滑。在待检测图像中,提取的特征点集合为B={B₁,B₂,…,B_n},对应的特征描述子集合为C={C₁,C₂,…,C_n},针对提取到的BRISK特征描述子,具体特征匹配过程如下。

1)初始化:最近邻域的初始化是对每一个检测到的待匹配块进行随机独立均匀采样,目的是在后续迭代更新过程中可快速获得好的匹配效果。如图1(a)所示,分别为待匹配块a、b、c随机赋予一个偏移块a'、b'、c',相应的三条箭头描述最近邻块的映射关系,即各个图像块间的偏移量,将各个偏移量的值存入NNF中。

(2)迭代:对初始化后的NNF进行迭代更新,提升匹配的准确性。迭代更新由传播和随机搜索两部分组成。迭代过程是从左到右,从上到下检测篡改图像中的每个特征描述子的偏移值,每一步检测先执行传播,再紧随一步随机搜索。传播过程尝试利用待匹配块周围k个位置的图像块来改善当前图像块的偏移量,描述不同的线性偏移域,对应旋转变化和尺度变化,选取其中最好的偏移量来改善当前已知图像块的偏移量,如图1(b)所示。虚线块a和对应偏移块a'作一个相似度比较,然后a又与实线块b'、点划线块c'等周围k个最近邻块作相似度比较,假设a在c'处得到了一个好的映射结果,那么就尝试将c'处的偏移量传播给a,并使用这个好的映射结果的偏移量来修正和更新a的偏移量。同理,实线块b和点划线块c也采用相同操作。这种传播的好处在于,如果位于一个篡改区域的图像块得到了一个好的匹配值,则该篡改区域经几何形变后,其他所有图像块也都会得到好的匹配值。经传播后并不能保证得到的偏移量是最准确的,因此,在传播过程后加入随机搜索过程,随机搜索的过程是在已由传播得到的匹配块周围设定一个搜索窗口,在该窗口内进行随机搜索,窗口的大小以指数形式递减,设搜索窗口的大小为

ui=v0+wαiRi,(1)

式中:i∈{1,2,…,n};R_i为在[-1,1]之间的随机值;w为搜索框的初始大小;α为缩小系数;v₀为初始块的位置。如图1(c)所示,a'的搜索半径开始为图像块的大小,随着i增大,搜索框的大小将不断减小,直至小于1时停止搜索。迭代过程反复进行,直到每个特征点计算出最合适、最准确的偏移量,通过特征描述子间的匹配可定位出相似图像块。定义两个图像块间的距离函数为D,将得到的偏移量按照从小到大的顺序存入NNF中,得到D={D₁,D₂,…,D_i},如果新检测到的偏移量更小,那么NNF中距离最远的偏移量就会被舍弃。由于在边界检测到的特征描述子不具有尺度不变性和旋转不变性,且PatchMatch算法采用尺寸较大的像素块,在检测时易丢失边缘信息,因此,所提算法在匹配阶段去除边界中检测到的特征描述子,能够进一步提高计算效率。

图 1. 特征匹配步骤。(a)初始化;(b)传播;(c)随机搜索

Fig. 1. Feature matching steps. (a) Initialization; (b) propagation; (c) random search

下载图片 查看所有图片

计算与特征点B_i(i∈{1,2,…,i})相匹配的特征点时,为了避免计算得到B_i与另一个特征点B_j(j∈{1,2,…,j})相匹配后,又得到B_j与B_i相匹配的重复结果,所提算法构造了一个哈希表来快速识别候选特征点的偏移量是否已存在于NNF中,防止重复输入。

2.3 篡改区域精确定位

复制-粘贴篡改操作是将图像中的至少一部分进行复制,移动并粘贴到同一幅图像的另一部分上。理想情况下,在前一步骤中检测到的匹配对仅出现在篡改区域中。然而,诸如建筑物之类的自然图像存在多个成对的高度相似区域,特征匹配后所产生的偏移域具有不确定性,不能准确地检测出复制-粘贴篡改区域,所以要进行精确定位,移除误匹配,具体步骤如下。

1)以半径为ρ_m的圆形窗口对篡改图像进行中值滤波。其次,在半径为ρ_e的圆形邻域中,采用最小均方线性模型计算拟合误差ε(Z)。设Z为一组点的齐次坐标,M^3×n(R)为仿射变换矩阵,其中R为待检测图像的大小。即

Z=x1…xny1…yn1…1,(2)

式中:x_n为图像的第n个横坐标;y_n为图像的第n个纵坐标。

最小均方线性模型的拟合误差为

ε(Z)=minM3×3R‖Δ-(EZ-Z)‖2,(3)

式中:Δ为齐次坐标中相同点的位移。从(3)式的意义来说,最好的仿射变换可用一个简单的最小二乘回归来估计,即

E=argminM3×3R‖Δ-(EZ-Z)‖2,(4)

(4)式的解可表示为

E=(Z+Δ)ZTZZT)-1。(5)

因此可在没有最小化步骤的情况下通过用

ε(Z)=‖Δ-(EZ-Z)‖2=‖Δ-[(Z+Δ)ZTZZT)-1Z-Z]‖2=‖Δ-ΔZTZZT)-1Z‖2=‖Δ(I-H)‖26

替换E来估计误差。式中:I为齐次坐标中相同点位移的集合;H为Z^TZZT)-1Z组成的矩阵。

对每一组计算后的拟合误差设置阈值τ,目的是将拟合误差ε(Z)计算得到的结果进行二值化处理,分割图像挑选检测到的复制-粘贴篡改区域。实验设置两个阈值:面积阈值T_m和距离阈值T_d。篡改区域一般是对某块较大区域进行复制-粘贴篡改,所以删除面积小于T_m的孤立区域对。同时,篡改操作往往是在位置较远处进行复制-粘贴,所以删除距离小于T_d的匹配区域对。

2)当一个篡改图像在多个区域进行复制-粘贴篡改时,可能会遗漏某些复制-粘贴区域,为了避免这个问题,对所提算法进行对称化检测。当检测到一个复制-粘贴区域时,将NNF中对应的偏移量也标记为复制-粘贴区域,这可以保证不会遗漏任何篡改区域。

3)对复制-粘贴区域进行几何形态学的膨胀操作。因为中值滤波和模型拟合都会腐蚀复制-粘贴区域,所以要通过膨胀操作来还原。通过上述步骤可实现图像中复制-粘贴篡改区域的精确定位。

3 实验分析

从CASIA V2.0图像数据库^[24]和哥伦比亚大学自然图像数据库^[10]中随机抽取100幅图像,利用图像编辑工具进行处理获得100幅复制-粘贴篡改图像,组成实验图像数据集,包括旋转、缩放、镜像、多区域Ⅰ、多区域Ⅱ和多区域镜像篡改图像。其中,多区域篡改分为两种情况:1)一块区域被复制后粘贴到多个地方,简记为多区域Ⅰ;2)多块区域分别被复制后粘贴到其他多个地方,简记为多区域Ⅱ。多区域镜像篡改分为两种情况:1)多区域篡改部分全部为镜像区域,简记为多区域镜像Ⅰ;2)多区域篡改部分一部分为镜像区域,一部分为普通复制-粘贴区域,简记为多区域镜像Ⅱ。实验运行环境为Window 10操作系统,计算机配置为Intel Core i5-3470 CPU 2.20 GHz,内存为8 GB,操作平台为MATLAB R2014a。实验使用的参数如表1所示。采用综合评价指标F值(F-measure)来评估算法性能,计算公式为

F=2TP2TP+FN+FP,(7)

式中:T_P为正确检测的篡改图像数目;F_P为真实图像被错误检测为篡改图像的数目;F_N为错误漏检的篡改图像数目。

图2~8所示为一组经过不同篡改操作的图像篡改检测结果。从检测结果可以看到,即使篡改区域经过旋转、缩放、镜像、多区域和多区域镜像操作,所提算法仍能有效识别和准确定位篡改区域。为了进一步评估算法的有效性,使用实验图像数据集设计两组实验,并与其他同类算法进行对比,以验证所提算法的性能。

1)评估文献[ 2]、文献[ 4]和文献[ 6]三种算法对于旋转、缩放和多区域篡改操作的有效性,同时对比各个算法的运算时间。因为文献[ 2]、文献[ 4]和文献[ 6]三种算法均检测不到镜像和多区域镜像复制-粘贴篡改区域,故仅比较旋转、缩放和多区域篡改操作方式,旋转角度设置为90°,缩放设置为缩小80%,篡改区域设置为3个,得到的F值如表2所示。从表2可以看到,所提算法对于同一幅图像的上述3种复制-粘贴篡改方式都有较高的F值,说明所提算法抵抗旋转、缩放和多区域复制-粘贴篡改等变换的性能优于上述三种算法。表3对比所提算法与文献[ 2]、文献[ 4]和文献[ 6]三种算法的计算效率,所提算法利用图像具有局部一致性的特点,通过初始化、传播和随机搜索三个步骤来计算相邻块的候选最佳匹配块,避免了大量不必要的块之间的距离计算,提高了处理速度,所以运行时间比上述三种算法更快。

图 2. 算法对旋转变换操作的检测结果。(a)原始图像;(b)纂改图像(旋转90°);(c)匹配结果; (d)检测结果

Fig. 2. Detection results of the algorithm on rotation transform operation. (a) Original image; (b) tampering image (rotation 90°); (c) matching result; (d) detection result

下载图片 查看所有图片

图 3. 算法对缩放变换操作的检测结果。(a)原始图像;(b)纂改图像(缩小80%);(c)匹配结果;(d)检测结果

Fig. 3. Detection results of the algorithm on scaling transformation operation. (a) Original image; (b) tampering image (reduced by 80%); (c) matching result; (d) detection result

下载图片 查看所有图片

图 4. 算法对镜像变换操作的检测结果。(a)原始图像;(b)镜像图像(水平);(c)匹配结果;(d)检测结果

Fig. 4. Detection results of the algorithm on mirror transformation operation. (a) Original image; (b) mirror image (horizontal); (c) matching result; (d) detection result

下载图片 查看所有图片

图 5. 算法对多区域Ⅰ变换操作的检测结果。(a)原始图像;(b)纂改图像;(c)匹配结果;(d)检测结果

Fig. 5. Detection results of the algorithm for multi-region I transform operation. (a) Original image; (b) tampering image; (c) matching result; (d) detection result

下载图片 查看所有图片

图 6. 算法对多区域Ⅱ变换操作的检测结果。(a)原始图像;(b)纂改图像;(c)匹配结果;(d)检测结果

Fig. 6. Detection results of the algorithm for multi-region II transform operation. (a) Original image; (b) tampering image; (c) matching result; (d) detection result

下载图片 查看所有图片

图 7. 算法对多区域镜像Ⅰ变换操作的检测结果。(a)原始图像;(b)纂改图像;(c)匹配结果;(d)检测结果

Fig. 7. Detection results of the algorithm for multi-region mirroring I transform operation. (a) Original image; (b) tampering image; (c) matching result; (d) detection result

下载图片 查看所有图片

图 8. 算法对多区域镜像Ⅱ变换操作的检测结果。(a)原始图像;(b)多区域镜像Ⅱ纂改图像;(c)匹配结果;(d)检测结果

Fig. 8. Detection results of the algorithm for multi-region mirroring II transform operation. (a) Original image; (b) tampering image; (c) matching result; (d) detection result

下载图片 查看所有图片

2)比较所提算法和文献[ 11]、文献[ 12]和文献[ 13]三种算法对镜像和多区域镜像操作的鲁棒性。从表4可以看到,三种算法都能检测出经镜像变换后的复制-粘贴篡改图像,但文献[ 11]不能准确检测多个区域镜像的篡改图像,只能检测单个镜像篡改区域,所以不能作为正确检测多区域镜像的检测结果;文献[ 12]能够检测到复制-粘贴区域全部为镜像翻转的篡改图像,但随着篡改区域个数的增多,存在漏检情况,有较高的漏警率;文献[ 13]能够有效检测出经多个区域镜像的篡改图像,但检测效果不如所提算法好。在计算时间上,所提算法比上述三种算法有明显优势。

4 结论

提出一种基于PatchMatch的图像篡改检测算法,提取待测图像的BRISK特征描述子,根据PatchMatch算法寻找匹配的特征点对,最后通过最小均方线性模型计算拟合误差移除误匹配点,精确定位篡改区域。实验结果证明,所提算法能够有效检测出经旋转、缩放、镜像、多区域和多区域镜像等复杂几何形变的复制-粘贴篡改区域。在实验中发现,对图像进行多个复制-粘贴镜像翻转操作,再将篡改后的镜像区域进行旋转和大尺度缩放等几何攻击操作时,从该区域提取出来的特征描述子内部破坏了原有向量的排列顺序,不能和原特征描述子匹配,所以有可能遗漏某些区域或检测不够精确,从而产生误判,这也是下一步将要研究的主要问题。