低频快速切比雪夫矩的篡改图像检测算法①

郑佳雯,张威虎

(西安科技大学 通信与信息工程学院,西安 710054)

数字图像处理技术的快速发展在给人们带来生活便捷的同时,也存在着图像本身的真实性和完整性等问题,目前篡改后的数字图像出现在医学研究、新闻报道或法庭证据等重要场合,这会对社会造成极大的负面影响,因此,对于检测数字图像是否真实得到了人们的密切关注.当前图像篡改检测算法主要分为两大类:一是主动检测算法,另一种是被动检测算法[1].被动检测算法在没有任何先验信息的情况下,利用图像的本身特性对原图像进行真实性检测,此类检测算法已经得到了广泛应用[2].

复制粘贴篡改是生活中常见的图像篡改方式.复制粘贴篡改图像的检测方法可以分为两类:基于特征点的检测算法和基于图像块的检测算法,基于图像块的算法在准确定位到篡改区域上优于基于特征点的算法.Ryu SJ 等[3]提出了一种基于Zernike 矩定位复制图像区域的算法,设计了一种局部敏感散列的新型块匹配,并通过检查矩的相位来减少误匹配,但对于较大尺度变换的检测效果不是很好.Dixit R 等[4]利用傅里叶-梅林变换和对数极坐标映射以及使用K 均值聚类的基于颜色的分割技术,具有较好的平移和旋转不变性,但算法的实时性差.谷宗运等[5]提出了一种基于Tchebichef矩的篡改图像检测算法,比较提取的DWT 和Tchebichef矩相邻特征向量的相似性,实现篡改区域的定位,但对于多区域篡改区域定位效果较差.

针对上述算法的不足,本文提出一种低频快速切比雪夫矩算法的篡改图像检测算法,首先采用非抽样小波变换对图像二维分解,对低频部分进行重叠分块,再提取图像块的快速切比雪夫矩特征,采用PatchMatch算法对特征向量进行匹配,最后用稠密线性拟合算法消除误匹配以及形态学操作定位篡改区域.

1 构造特征向量

1.1 Tchebichef 矩

假设图像f(x,y)上一点(p,q),位于大小为N×N图像块(p,p+N-1)×(q,q+N-1),其n+m阶Tchebichef 矩为[6]:

其中,tn(x)和tm(y)为n阶和m阶正交切比雪夫多项式,定义如下:

其中,(·)l表示阶乘幂.tm(y)定义类似.

正交切比雪夫多项式在x 处的tn(x)和在x+a处的tn(x+a)有如下关系[7]:

当a=1 时,有:

其中,gr(n,l)定义为:

1.2 改进的低频快速Tchebichef 矩

对于图像篡改,如果非平移不变,在复制和粘贴两个相同的区域会被破坏,会出现漏检情况.下采样使得离散小波变换(DWT)不具有平移不变性,不仅会对DWT 系数产生巨大影响,还会对篡改区域产生不同的特征向量.另外,DWT 的伪吉布斯现象使得检测边缘和纹理等信号的效果不够理想.对于DWT 存在的不足,这里采用具有平移不变性的非抽样小波变换(UWT),由于UWT 不包括下采样和小波系数缩减,因此称为非抽样的[8].

对图像利用UWT 沿行和列进行二维分解,分别得到4 个子带,即水平高通子带LH,垂直高通子带HL、对角高通子带HH 以及低通子带LL,每个子带的尺寸不发生变化[9].

图像进行过UWT 后,由于图像的主要部分是低频部分,所以提取图像的低频部分.对提取的低频部分进行检测,可以大大降低块的个数,使得计算量仅为原来的1/4,同时低频对噪声不敏感,也可以加强特征的鲁棒性.再对图像进行分块,假设待测图像大小为M×N,用a×a像素的滑动窗口每次移动一个像素点对图像进行扫描,可以得到(M-a+1)×(N-a+1)个重叠块.

对于一个大小为N×N滑动块(p+1,p+N)×(q,q+N-1),其n+m阶水平方向的Tchebichef 矩为:

相同地,对于下一个大小为N×N滑动块(p,p+N-1)×(q+1,q+N),其n+m阶垂直方向的Tchebichef 矩为:

T分别表示输出行f(p+x,q),0 ≤x ≤N-1,m阶切比雪夫矩和输入行f(p+x,q+N),0 ≤x ≤N-1,m阶切比雪夫矩,定义如下:

基于上述理论,对于图像f(x,y),低频快速切比雪夫矩算法如下:

(1)对图像进行UWT 二维分解,提取其低频部分并进行重叠分块;

(2)计算切比雪夫多项式和系数矩阵;

(3)计算所有的行向量.对于图像f(x,y)每行的第一个行向量,计算其切比雪夫矩,每行的其余行向量计算其快速切比雪夫矩;

(4)计算所有的列向量的切比雪夫矩;

(5)计算图像f(x,y)第一个块的矩特征,基于步骤(4)的结果,采用快速切比雪夫矩计算第一行的所有块的矩特征;

(6)基于步骤(2)和步骤(4)的结果,采用快速切比雪夫矩计算其他块的矩特征.

2 PatchMatch 算法匹配

本文采用PatchMatch 算法进行特征匹配,它是一种图像块之间寻找最近邻匹配的快速随机算法,将正确的偏移量传播并且迭代更新至全部偏移量,相比较传统的kd-tree 算法而言,不仅可以大大减少处理时间,还可以提供准确的匹配率[11].算法步骤如下:

(1)初始化.对于每个像素s,随机初始化偏移量:

其中,U(s)是一个二维随机变量,并且均匀分布在整个图像.由于我们正在寻找与目标相对较远的匹配,这里我们不考虑 δ(s)=0,以及所有偏移量小于给定阈值的情况.虽然大多数初始随机偏移量很少用到,但也有可能是最优的或近似最优的.

(2)传播.在这个阶段,图像按照从上到下、从左到右的顺序光栅扫描,则每个像素s偏移量更新为:

其中,ΔP(s)={δ(s),δ(sr),δ(sc)},sr和sc分别表示光栅按行和列扫描的像素s之前的像素.每个像素判断相邻块的偏移量是否提供了更好的匹配,如果是,则采用相邻块的偏移量.若给定区域像素具有恒定偏移量,就可获得正确偏移量,并迅速传播,填充整个区域的下方和右侧.每次迭代更新时,按照反转的光栅顺序(从下到上、从右到左)扫描图像,以获得更准确的偏移量.

(3)随机搜索.由于传播过程依赖于随机初始的偏移量,所以不能达到最优匹配.为了尽量避免陷入局部最小值,采用随机搜素,在修正式(13)后,对当前偏移量进行随机采样,设候选偏移量δi(s),i=1,···,L为:

其中,Ri是一个二维随机变量,并且均匀分布在除去原点的半径为2i-1的方形区域中.事实上,大多数的候选偏移量非常接近δ(s),随机搜索后偏移量更新为:

其中,ΔR(s)={δ(s),δ1(s),···,δL(s)}.

3 后处理

除了平滑区域之外,通过特征匹配获得的偏移量应该是细节化的.但是由于噪声、压缩、几何变换、光照变化和相似区域等原因[12],PatchMatch 算法获得的偏移量很少遵循该情况,因此后处理阶段需要:(1)对偏移量进行正则化.(2)添加适当的约束.

由于隐式过滤得到的偏移量已经足够规则,所以需要添加适当的约束.这里采用稠密线性拟合的方法[13],这是因为它复杂性低并且可以快速地得到正确的偏移量.

通过仿射模型,在像素s的适当N像素邻域内拟合出真实偏移量:

转换参数A,设置为平方误差之和的最小值.

虽然偏移量是二维的,但是参数A 可以针对每一维进行独立地优化,因此,可以将 δ(x)视为一维偏移量,问题转化为:

其中,δ=[δ(s1),δ(s2),···,δ(sN)]T是匹配阶段的偏移量,a=[a0,a1,a2]T是识别仿射模型的参数向量,S是邻域内所有像素齐次坐标的N×3 矩阵.

因此真实偏移量为:

这是一个多元线性回归问题,解为:

因此,相应的平方误差之和为:

H=S(STS)-1ST

其中,是对称的,进一步简化H矩阵为:

其中,qj为N行列向量,所以,有:

下面给出具体的后处理步骤:

(1)对得到的偏移量进行中值滤波操作.

(3)去除误匹配对,包括较匹配区域对的距离像素更接近的匹配对,或小于匹配区域面积像素的匹配对.

(4)映射检测到的区域.

(5)使用圆形的结构元素进行形态学操作,实现篡改图像区域的定位完成检测.

为了证明稠密线性拟合方法的有效性,对篡改图像后处理阶段的进行检测,如图1 所示.由图1 可知,匹配阶段的偏移量已经足够规则,但还存在较多误检,后处理阶段采用稠密线性拟合方法可有效降低误检率.

图1 篡改图像后处理的检测结果

4 实验分析

实验是在Windows10 操作系统下,采用Matlab 软件测试的.为了验证本文方法的可行性和有效性,实验采用的数据集为benchmark data[14],该数据集包括48 幅原图像以及48 幅篡改图像,篡改区域包括单区域和多区域.同时将本文方法与文献[5]和文献[14]进行对比来证明本文方法的优越性.

性能分析主要包括图像层面和像素层面,本文从像素层面来衡量篡改检测算法的性能,采用precision、recall和F这3 个指标,定义如下:

其中,precision为检测准确率,即检测为篡改图像的数据集中有多少是真正的篡改图像,包括把篡改图像检测为篡改图像及把真实图像检测为篡改图像;recall为检测召回率,即数据集中的篡改图像有多少被正确检测了,包括把篡改图像检测为篡改图像及把篡改图像检测为真实图像;F为综合评价指标.TP为篡改图像中被正确检测到的篡改像素数量,FP为篡改图像中未篡改部分被检测为篡改像素的数量,FN为篡改图像中的篡改部分未被检测到的篡改像素数量.precision和recall这2 个评价指标相互制约,F综合考虑了这两个指标,F值越大,算法的检测性能越好.

本文对篡改区域为单一区域和多区域分别进行了实验,单区域篡改图像的检测结果见图2,单区域多次篡改图像的检测结果见图3,多区域篡改图像的检测结果见图4,表1 为3 种算法篡改检测性能的比较.

图2 单区域篡改图像的检测结果

图3 单区域多次篡改图像的检测结果

图4 多区域篡改图像的检测结果

表1 3 种算法检测性能的比较(%)

由图2～图4 可知,文献[5]和文献[14]都会出现漏检测的情况,尤其对于图4(c)出现两个不同的篡改区域,而只定位出一个篡改区域,虽然文献[14]的检测结果优于文献[5]的检测结果,但是检测到的篡改区域还是会遗漏一些篡改区域的细节信息,综合来说,本文算法的检测结果是最好的.为了更加准确地体现本文算法的优越性,由表1 可知,本文算法的综合评价标准F是最高的,其中precision分别提高了8.1%和1.8%,recall分别提高了3.3%和1.2%,F分别提高了3.5%和1.5%,与上图中的检测结果一致.这是因为文献[5]采用DWT 和Tchebichef 矩结合的特征向量,比较其相似性定位篡改区域,特征向量没有很好地表示篡改图像信息,会存在漏检测的情况;文献[14]对每个重叠分块提取快速切比雪夫矩特征,特征匹配使采用kdtree 算法,kd-tree 算法不能很好地实现篡改图像的匹配;本文算法采用低频快速切比雪夫矩作为特征向量,PatchMatch 算法进行特征匹配,最后用稠密线性拟合算法消除误匹配,这样可以较好地描述图像信息,防止漏检和误检的情况.

我们还比较了本文算法和文献[5]和文献[14]在数据集benchmark data 中每幅图片的平均运行时间,来证明本文算法的实时性,实验结果如表2 所示.由表2可知,除了图3(b)之外,其他图片都是本文算法的运行时间最短,最后一列是数据集中每幅图片的平均运行时间,可知本文算法的平均运行时间是最短的.这是由于本文算法采用UWT 实现图像分解,提取低频部分的快速切比雪夫矩特征,并且采用PatchMatch 算法进行匹配,可以缩短算法运行时间,提高本文算法的实时性.

表2 3 种算法运行时间的比较(单位:s)

最后我们比较了本文算法和文献[5]和文献[14] 在数据集benchmark data 中每幅图片的平均误匹配率(误匹配对/匹配对),实验结果如表3 所示.由表3 可知,本文算法的匹配对是最多的,误匹配对是最少的,误匹配率是最低的.这是因为相比较文献[5]的相似性匹配及文献[14]的kd-tree 匹配,本文算法采用PatchMatch算法进行匹配得到规则的偏移量,并且采用稠密线性拟合方法进行后处理降低误匹配,具有很好的匹配效果.

表3 3 种算法误匹配率的比较

5 结论与展望

本文提出了一种低频快速切比雪夫矩的篡改图像检测算法.利用非抽样小波变换分解图像并提取其低频部分,对于重叠块提取其快速切比雪夫矩特征,PatchMatch 算法匹配块特征,最后剔除误匹配并定位其篡改区域.相比之前算法,F达到了92.0%,分别提高了3.5%和1.5%,本文算法对于单区域、单区域多次以及多区域的篡改均有很好的定位结果,并且有效地降低了运行时间,提高了算法的实时性,最后也降低了误匹配率实现很好的匹配效果.后续工作将放在对篡改区域进行旋转、加噪、压缩以及模糊等处理的检测及精确定位上.