基于点匹配的区域拷贝篡改检测

收稿日期：2014-02-19

基金项目：国家自然科学基金资助项目（60973113）;院级一般科研项目(XYS10N05)

作者简介：朱珏钰(1980―），湖南长沙人，讲师，硕士，研究方向：智能信息处理、图像处理与模式识别。

文章编号：1003-6199(2014)02-0097-04

摘 要：图像区域拷贝是一种常见的数字图像篡改技术，目前的大部分数字图像区域拷贝取证技术未考虑旋转和缩放因素。提出一种新的基于点匹配的图像区域篡改检测算法。首先利用尺度不变旋转变换（SIFT）寻找图像中的关键点，使用主成分分析法(PCA)对关键点进行降维描述，然后利用关键点特征向量的相似度寻找关键相似点。实验表明，该算法不但能够较精确地定位出复制和粘贴的图像伪造区域，还能有效抵抗噪声污染、有损压缩以及旋转等攻击，并有效地减少运算量，提高了检测效率。

关键词：区域拷贝；点匹配；篡改检测；块匹配；关键点

中图分类号：TP309.2文献标识码：A

お

Detection of Image Region Forgery Based on Point Matching

お

ZHU Jueyuk

（Department of Information Science and Engineering, Hunan First Normal University,Changsha,Hunan 410205,China）

Abstract:Copymove is a common digital image manipulation technique. Attacks such as rotation and scaling are not considered in most copymove image forensic methods. This paper proposes a novel region forgery detection algorithm based on point matching. Firstly, we extract feature points with Scaleinvariant Feature Transform (SIFT), and describe the points by Principal Component Analysis (PCA). Owing to the similarity between the pasted region and the copied region, we find out all possible forgeries by seeking for similar point pairs by using their descriptors. The experimental results demonstrate that our proposed algorithm performs not only robustly in terms of additive noise, lossy JPEG compression but also effectively in rotation attack, comparing with the algorithm based on block matching. Furthermore, our algorithm has reduced the calculation amount and improved the detection efficiency.

Key words:region forgery; point matching; forgery detection;block matching;key point

1 引 言

随着图像处理软件功能的日渐强大，人们可以很容易地篡改数字图像，使图像的篡改用肉眼难以确定。如果官方媒体、科学发现、保险和法医等采用大量篡改和伪造的图像作为证据，这无疑将对社会产生重大的影响。因此，针对数字图像篡改的检测研究具有重要意义。

近年来，数字图像拷贝篡改检测已取得一些成就。美国伯明翰大学Jessica Fridrich等人提出了基于量化DCT系数的块匹配检测方法［1］。该方法计算出每个图像分块量化后的DCT系数后进行字典排序以检测出图像中被篡改的区域。骆伟祺等人则将图像分割成重叠块，再提取每个图像块的颜色特征向量，然后通过对比重叠块的相似度来确定拷贝篡改的区域［2］。这些算法都是采用图像块匹配的方法来进行篡改检测的，并能有效抵抗噪声、有损压缩等攻击。然而，一旦图像区域在篡改后经过了局部缩放、旋转等几何变换后，它们就失去了篡改检测的能力。因此，为了增强篡改区域在经受旋转和缩放后检测算法的鲁棒性，本文提出了一种基于点匹配的图像区域拷贝篡改检测算法。

2 区域拷贝篡改模型

区域拷贝也叫区域复制粘贴，是把图像中的某一区域复制后，粘贴到同一幅图像中的其他位置上， 以达到去除图像中某一重要目标或者证据的目的。图1给出了一般的区域拷贝篡改模型。

图1 图像区域拷贝篡改模型オ

其中，I(D)是篡改图像，D1是被复制的区域，D2是被粘贴的区域， D1、D2对应像素间的位移为dx=(Δx,Δy)。

从图中可知， 篡改后的图像中至少存在两个较大面积的相似区域。因此，若检测到一幅图像中存在较大面积的相似区域，则可判定该幅图像是经过了区域拷贝篡改的。

然而，伪造者在进行区域拷贝篡改后， 通常还会增加尺度旋转等操作，以掩盖篡改痕迹或使图像效果更好。此时D1 、D2 区域上对应的像素值就变得不完全相等了。因此，需要找到一个旋转不变的矩阵，使之针对旋转操作具有鲁棒性［3］。本文提出了一种采用PCASIFT的基于点匹配的区域拷贝篡改检测算法，能有效对抗旋转和局部缩放等┕セ鳌＊

3 基于点匹配的区域拷贝篡改检测算法

为了提高计算速度和加强匹配精度，本文提出了一种基于PCASIFT的区域拷贝篡改检测算法，该算法主要分为两个步骤：1）图像的PCASIFT特征提取；2）利用PCASIFT特征的匹配程度检测图像篡改。即：首先经过尺度空间极值点检测、关键点定位和关键点方向分配三个子步骤提取PCASIFT特征；然后确定关键点描述符，搜索匹配对来确定PCASIFT特征的匹配程度从而检测图像篡改［4］。

3.1 尺度空间内极值点检测

为了检测出尺度空间内的极值点，首先需要构造出图像的尺度空间。该空间用L(x,y,σ)表示，可以利用高斯函数G(x,y,σ)与图像I(x,y)的卷积得到：

L(x,y,σ)=G(x,y,σ)*I(x,y)(1)

其中*表示卷积操作，G(x,y,σ)定义如下：

G(x,y,σ)=12πσ2e－(x2+y2)/2σ2(2)

其中，(x,y)为像素坐标；σ为尺度空间因子，其大小决定图像的平滑程度［5］。

计算技术与自动化2014年6月

第33卷第2期朱珏钰：基于点匹配的区域拷贝篡改检测

在实际的计算过程中，为了能够得到更加稳定而有效的尺度空间特征点，通常会对两个相邻的高斯尺度空间进行差分处理，这样就得到了高斯差分的响应图D(x,y,σ)，在得到的响应图像上进行极值点的确定。

D(x,y,σ)=(G(x,y,kσ)－G(x,y,σ))*I(x,y)=

L(x,y,kσ)－L(x,y,σ)(3)

为了检测尺度空间内的极值点，要比较每个特征点与它的所有相邻点，如果该点在图像域以及尺度域都处于最小或者最大，则被认定为极值点。

3.2 关键点定位

为了准确定位出关键点的位置所在，同时需要去掉一些不稳定的特征点以及低对比度的点，以达到增强匹配精度的目的。由于位于边缘上的特征点存在定位方面的奇异性，同时也容易受到噪声的影响，因此很难定位到这类特征点。为了解决该问题，可引入2*2的Hessian矩阵来计算主曲率，该Hessian矩阵可表示为：

H(x,y)=Dxx(x,y)Dxy(x,y)Dxy(x,y)Dyy(x,y) (4)

其中D值可以利用采样点与相邻元素的差分近似求得［6］。用α表示Hessian矩阵的最大特征值，β表示最小的特征值，有：

Tr(H)=Dxx+Dyy=α+β(5)

Det(H)=DxxDyy-D2yy=αβ (6)

假定γ表示最大特征值α和最小特征值β之间的比值，即满足α=γ•β，那么：

Tr(H)2Det(H)=(α+β)2α•β=(γ•β+β)2γ•β2=(γ+1)2γ (7)

如果某个关键点能够满足下式条件，则保留该点,否则就丢弃。

Tr(H)2Det(H)＜(γ+1)2γ(8)

3.3 关键点方向分配

考虑到篡改检测算法需要对旋转之类的后处理操作具有良好的鲁棒性，则要求所得到的关键点的描述值具有旋转不变性。为了解决这个问题，在算法的实现过程中，需要依据检测所得到的特征点集所在的局部结构求取一个方向的基准。在具体的实现过程中，该稳定的方向基准可以利用梯度方法求解得到。具体的话利用有限差分，以所得到的关键点为中心，这里假定以3×1.5ω1,ω2,…,ωc为半径取关键点所在邻域计算幅值以及幅度角，如图2所示。假定m(x,y)表示图像在(x,y)处的梯度幅值值，

SymbolqA@

(x,y)表示(x,y)处的方向，那么：

m(x,y)=L21+L22(9)

θ(x,y)=arctan(L2/L1)(10)

其中：

L1=L(x+1,y,σ)-L(x-1,y,σ) (11)

L2=L(x,y+1,σ)-L(x,y-1,σ) （12）ゼ扑懔斯丶点所在邻域的高斯尺度图像的梯度之后，接着使用直方图方法统计出关键点所在邻域内全部像素的幅值以及梯度方向值。梯度直方图的横坐标表示梯度方向的角度，纵坐标则表示该方向角所对应的梯度幅度值的累加。考虑到梯度方向角的范围是0至360度，因此，一般将直方图划分成为36个Bin，每个Bin代表10度的跨度。最终，可以将直方图中梯度方向的峰值定位为这个关键点所在邻域范围内的主方向。除此之外，还可以定义一个关键点的辅助方向，即在梯度直方图中，如果存在另外一个值，该值的大小约为峰值的80%，则将该值对应的梯度方向定位为关键点辅助方向，这种处理方法能够有效的增强匹配过程中的鲁棒性。

a)梯度方向角和幅值表示b)特征点邻域选取

图2 梯度幅值和幅角

3.4 关键点描述符确定

通过前面的三步，可以获得关键点在图像中的具置，尺度和方向，接着需要为每一个关键点进行特征描述。PCASIFT与SIFT算法具有一样的关键点定位处理、尺度以及主方向，不同之处体现在对关键点描述符的计算。利用PCASIFT对关键点描述符的计算可以归纳为三个步骤：1)PCASIFT投影矩阵的生成或者导入；2)关键点的检测；3)利用投影矩阵求解关键点的紧凑特征┫蛄俊＊

投影矩阵的生成一般都是经过描述大量的图像得到的。在实际计算过程中，建立在投影矩阵的生成以及关键点的位置、尺度和方向的描述符的计算，其具体的步骤可归纳如下：

1) 对于特定的尺度空间，以关键点为中心，提取41×41的邻域，同时将它转至主方向；

2) 计算每个39×39邻域区间的水平和垂直方向的梯度值，形成3042大小的特征向量；

3) 将事先计算得的n×3042大小的投影矩阵与得到的特征向量进行相乘计算，生成n维的PCASIFT描述符(本文中n取36)。

3.5 匹配对搜索

获得图像中的关键点的描述符后，可以用36维特征向量表述每个关键点，接着需要寻找出相互匹配的关键点对，这就需要采用一定的搜索策略。本文采用的搜索策略为最近邻搜索法。

对于包含ω1,ω2,…,ωc共c种类别的数据，假定每类都有注明类别的Ni个样本，i=1,…,c，那么第i类ωi所采用的判别函数可以如下定义：

gi(X)=┆min k||X－Xki||，k=1,2,…,Ni(13)

其中，Xki表示ωi类中的第k个样本［7］。利用上述的判别函数可以进一步推出所使用的决策荚颍邯

若某个数据满足下式：

gj(X)=┆min igi(X)，i=1,2,…c(14)

那么判定：X∈ωj

最近邻算法只需要把未知样本和其他样本进行距离计算，然后将拥有最小距离值的样本定义成未知样本的决策类别即可。||•||表示距离计算，可以使用常见相似性计算公式，通常情况使用欧氏距离作为判断准则。

3.6 匹配对优化

由于上节利用最近邻算法所搜索到的匹配对并非一定准确，所以有必要对所得到匹配结果进行进一步的优化处理。上节中最近邻实际上是1-近邻算法，如果将该算法适当的拓展到k-近邻(k>1)对关键点数据进行分析效果将更佳。考虑k=2时，此时除了得到最近邻数据外，同时考虑次近邻数据。图3的概率分布图描述了4000多个关键点的最近邻和次近邻距离比值情况。

图3 最近邻与次近邻距离比值概率分布图

从图3可知，正确匹配下的距离比和错误情况下的距离比具有不同的分布情形。在最近邻和次近邻的距离比值小于0.8时，匹配对正确的概率极高；相反，则匹配对错误的可能性将较大。因此，如果引入次近邻的数据信息将有利于提高匹配的正确性，因此这里将利用下式对匹配对进行优化理［8］：

最近邻距离/次近邻距离≤距离阈值 (15)

如果集合中某关键点满足上述关系式，则保留该关键点，否则排除该点。公式15所采用的距离阈值取值范围为0-1。实验中，本文采用的该值为0.6。

4 实验仿真及结果

实验仿真平台：CPU 1.4GHz，内存 1.25G，操作系统 Windows XP，仿真软件 Visual Studio 2008+OpenCV2008。

为了验证算法的有效性，将本文算法与传统基于块匹配思想的算法进行比较验证，实验结果如图4所示。

根据实验结果可知，本文所提算法能够有效解决传统基于块匹配算法面对局部旋转和缩放的篡改区域检测无效的情形。此外，本文进一步比较了两类算法的运行效率。基于块匹配的算法处理一张300×400的图像一般需要50s左右，而本文算法在处理一张800×640的图像时只需要7s左右，前类算法低效的原因主要在于需要对图像的长特征向量进行字典排序，而本文算法利用索引结构有效的解决了这方面的问题。

图4 旋转、缩放篡改检测结果

(a)原始图；(b)篡改图；(c)传统基于块匹配算法对经旋转操作的篡改区域的检测结果图；(d)传统基于块匹配算法对经缩小操作的篡改区域的检测结果图；(e)本文算法对经旋转操作的篡改区域检测结果图；(f) 本文算法对经缩小操作的篡改区域检测结果图。

タ悸堑接PCASIFT具有相似性质的变换SIFT，本节将给出本文与基于SIFT的篡改检测算法二者间的对比结果，如表1所示。表中数值除最后一列表示算法的运行时间外，其余为算法的检测正确率。

表1 本文算法与基于SIFT的检测算法的对比结果

Algorithm

Rotation

Zoom

Fuzzy

Contrast

change

Computing

time

SIFT

0.80

0.75

0.6

0.79

26.3s

本文算法

0.77

0.63

1

0.87

7.7s

从上表可知，基于SIFT的算法在面对旋转和缩放后处理方面拥有更好的性能，但是本文算法中在模糊类和高对比度类篡改图像方面具有更高的检测性能，同时算法的运行时间更少。

图5 多种后处理组合的篡改检测结果

(a)高斯噪声；(b)椒盐噪声；(c) JPEG（70）压缩；(d) JPEG（50）压缩；(e) 局部旋转+缩小；(f) 局部旋转+缩小+JPEG压缩。オ

由于篡改者在进行伪造的过程中很有可能是多种篡改手法的结合，所以这里将给出对于几种常见后处理操作单独或组合修改篡改区域时的检测结果，如图5所示。

通过上面的实验结果可知，本文算法对于篡改后常用的后处理操作具有很好的鲁棒性，同时拥有较好的运行┬率。

5 结 论

针对常用的图像区域拷贝篡改，本来利用PCA-SIFT算法提出了一种基于点匹配的区域拷贝篡改检测算法，该算法首先利用尺度不变旋转变换得到图像中的关键点，然后利用PCA对关键点进行降维描述，最后采用最近邻搜索算法定位出篡改区域。实验结果表明该算法具有较好的性能，但是也存在着一定的缺陷，该算法只能检测同一幅图像内的区域拷贝篡改，而目前大部分的篡改图像都来源于不同的图像源，因此如何将这方面的工作进一步完善将是后面的研究重点。

参考文献

［1］ FRIDRICH J,SOUKALD,LUKASJ.Detection of copymove forgery in digital images, Proceedings of Digital Forensic Research Workshop［J］.Cleveland OH, USA, 2003.

［2］ 骆伟祺,黄继武,丘国平.鲁棒的区域复制图像篡改检测技术［J］.计算机学报,2007, 30(11):199-200.

［3］ 徐琼.基于二维EMD分解的数字图像压缩研究［D］.长沙:长沙理工大学，2009.

［4］ HUANG H,GUO W,ZHANG Y.Detection of copymove forgery in digital image using SIFT algorithm［J］.In IEEE PacificAsia Workshop on Computational Intelligence and Industrial Application ,2008.

［5］ 沈庭芝,王卫江,闫雪梅.数字图像处理及模式识别［M］.北京:北京理工大学出版社,2007.

［6］ JOHNSONM K,FARID H.Exposing Digital Forgeries by Detecting Inconsistencies in Lightint［C］//In:Proceeding of ACM Multimedia and Security Workshop,New York,NY,USA,2005:1-10.

［7］ NG T T,CHANG SF.A Modal for image splicing［C］//IEEE International Conference on Image Processing , Singapore, 2004:1169-1172.

［8］ SHIHFU CHANG,JOHN R SMITH. Single color extraction and image query［C］//In:International Conference on Image Processing, 1995:91-95.

［9］ 姜丽,吕皖丽,罗斌.基于相位和幅度谱的数字图像被动认证算法［J］.计算机工程与设计,2009,15(9):68-70.

［10］A刘蕊,陈红卫.一种改进的图像边缘检测算法［J］.科学技术与工程,2009,3(21):102-105.