一种区域复制图像篡改检测的效率改进方法

【摘要】 提出一种在区域复制图像篡改检测中的块匹配检测的效率提高方法。将待匹配的图像分块进行简单分类，被划分为不同类的分块之间具有明显的区别，根据不同分类将所有的图像分块划分为多个分块队列。在分块相似度匹配的过程中，只有分类一致或接近的分块队列才进行匹配计算，避免了具有明显区别的图像分块匹配过程，从而大量降低分块匹配的次数，提高算法运行效率。实验结果表明，提出的改进方法与原算法的检测结果基本一致，而算法运行时间有较大幅度减少。

【关键词】 图像篡改 区域复制 篡改检测 效率改进

一、引言

随着当今网络技术的快速发展，以及摄像器件的小型化和便捷化，数字影像已经成为我们获取信息的主要方式之一。然而，伴随着数字图像处理算法和编辑软件的迅速发展和普及，数字图像或视频很容易通过图像处理软件被篡改。被篡改的图像有时候人眼不容易辨别出来，导致人们容易被篡改后的影像所误导[1-2]。

数字图像篡改检测技术作为被动图像认证的技术存在很多种检测方式，包括区域复制的检测、图像重采样检测技术、多次JPEG压缩图像的检测、基于噪声分布不一致性的检测、图像模糊润饰检测等，这些方法都有其优点和局限性[1-2]。

区域复制篡改是通过同一图像上的复制-粘贴操作，将图像中原有的某些信息遮盖隐藏的一种常用的篡改手段。针对该篡改方式，Fridrich等人首先提出了对图像进行分块，然后对图像分块DCT系数量化后进行字典排序，寻找相似块从而找出复制区域的算法[3]。Farid等人对图像分块进行PCA降低维度与量化，再使用字典排序方法寻找相似图像区域[4]。Li G H等人先对图像进行DWT变换再进行分块，提取分块的奇异值进行字典排序检测相似图像分块[5]。魏为民等人将图像进行两种不同的分块：不重叠分块和单像素滑动重叠分块，对两组分块进行haar小波变换，在两组小块之间使用小波变换的低频子带进行Pearson相关系数的计算进行相似分块的匹配检测[6]。刘潘梅等人提出在文献[6]的基础上对haar小波变换后的低频子带再次进行PCA降维，得到的1结果作为分块特征向量进行Pearson相关系数的计算[7]。

本文针对魏为民等人提出的算法进行改进，将该算法中两组分块队列中的重叠分块队列进行分类，形成多个子队列。不重叠分块队列中的分块不需要与所有的重叠分块进行比较，而是与部分子队列中的分块进行比较。从而可以较大的提高算法运行速度。

二、基于分类比较的算法描述

2.1 原始算法

首先对魏为民等人提出的算法进行简要描述：

（1）将图像按两种分块方式分别分块，形成2组分块队列。分块方式分别为不重叠分块和单像素滑动重叠分块，如图1所示：

假设待测图像大小为M×N，分块大小为b×b。那么不重叠分块数量为（M/b）×（N/b）（M，N不是b的整数倍则取整）单像素滑动重叠分块数量为（M-b+1）×（N-b+1）。如此就形成2组分块队列，不重叠分块队列中的分块用Bj表示，另一个队列的分块用Bi表示。

（2）对每一个分块Bj和Bi进行haar小波变换，使用低频子带cAj或cAi作为分块Bj或Bi的特征向量：

[cAi， cHi， cVi， cDi]=dwt2（Bi ，‘haar‘）；

（3）将2组队列分块的特征向量进行匹配检测，匹配算法使用Pearson相关系数检测方法：

上式中X和Y分别表示两组队列分块的特征向量cAj和cAi，计算结果为两个特征向量的相关系数，当相关系数超过门限值就认为两个分块相似，可能是复制篡改区域。匹配过程的复杂度可以从下图看出：

上图中，可以看到每个不重叠分块的特征向量都要与所有重叠分块的特征向量进行匹配运算。匹配的次数为（M/b）×（N/b）×（M-b+1）×（N-b+1）。分块尺寸会影响复杂度，分块越大匹配次数越低，但是分块太大容易超出篡改区域的尺寸，所以一般分块尺寸大小选择为16×16。

2.2 基于分类比较的改进算法

我们观察一副图像可以发现，图像的所有分块中，很多的分块具有很明显的区别，如下图所示，图中A、B、C三个分块具有很明显的区别：

那么对于前一小节所述的不重叠分块组中的分块是否需要与另一个队列的所有重叠小块进行匹配运算呢？答案是否定的。因此，可以根据某种分类依据，属于同一类的分块才进行Pearson相关系数计算进行匹配。即可以将重叠分块队列按分类标准分成几个子队列，而每个不重叠分块选择其中分类接近的部分子队列进行匹配计算，而不是与所有重叠分块进行匹配计算，从而大大减少了匹配的次数。如下图所示：

对于分类方式，本文使用分块的低频子带所有像素数值之和来进行分类。依据主要有三点：首先相似分块的像素和会比较接近；其次所有像素值之和对均值为零的噪声具有较好的抵抗能力；最后是该分类计算比较简单。不同的分类方式具有各自优缺点，当然有其他分类方式会具有更好性能，但可能计算比较复杂。

根据分块大小为16×16来进行分类设计：

（1）16×16分块的小波变换的低频子带为8×8像素，对每个像素值除2后，其值范围为[0，255]，其所有像素之和范围是[0，16320]。将该范围分为32个区间，每个区间的范围大小是510。即可以将重叠分块划为32个子队列。

（2）重叠分块组中的分块根据低频子带的像素值之和分别划分到32个子队列中。而每个不重叠分块也根据低频子带的像素值之和标识其对应子队列。这里要注意的是，不重叠分块子带的像素值之和可能落在区间边缘，所以不重叠分块不仅要与对应的子队列进行匹配，还要与其前后两个子队列即共三个子队列进行匹配计算。这样就能保证所有低频子带像素和的距离在510以内的分块都能进行匹配计算。如下图所示，对应子队列4的分块要与子队列3，4，5里的分块进行匹配计算：

上述分类将重叠分块划分为32个子队列，其中队列的数量对复杂度和性能有一定的影响。划分的队列越多，队列里的分块越少，因此算法速度就越快。但是队列多表示队列的数值范围减少，就容易导致漏判的情况出现。本文采用32个队列，每个队列范围510，经过测试发现，两个复制分块的低频子带像素和的差值很少超过510的值。

三、实验结果

采用以下两张纂改后的图像对本文提出的改进算法与文献[6]中的原算法进行比较：

在算法实现的过程中，考虑到2.1节中的式（1）里的以下部分只与分块一一对应：

所以可以在建立队列的时候就将所有分块计算好式（2）和式（3）并保存。在分块匹配的过程中就可以减少这部分的重复计算。可以一定程度上提高算法运行效率。原方法与本文提出的方法在仿真过程中都采用了该方式提高运行效率。

仿真测试的平台是intel CPU酷睿双核主频2.2GHz、内存2G、WindowsXP系统与Matlab 7.0。测试结果如下：

运行时间：

从检测结果来看，原算法和改进算法的结果基本一致，都可以检测出复制区域。但是也都存在误判的情况。而从运行时间来看改进后的算法耗时是原算法的1/3左右，运行效率有较大提升。

四、结束语

本文在文献[6]的算法基础上设计了一种利用分类比较的方法，将图像分块分为多个不同分类的子队列，通过只比较分类接近的分块子队列来大幅度的降低分块匹配次数。该方法可以适用于其他基于块相似度匹配的算法，可以在基本保持性能的前提下，提高算法效率。