基于提升小波变换的图像篡改检测算法

柴新新，邱晓晖

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

基于提升小波变换的图像篡改检测算法

柴新新，邱晓晖

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

图像在人类的感知中扮演着非常重要的角色，所传递的信息比其他任何形式更加丰富真切，而互联网中存在着大量的图像图片并且传播快速，这就使得辨别图像的真伪变得尤为重要。复制粘贴操作是最为常见的图像篡改手段之一，通过该手段可以达到修改或隐藏目标图像的目的。针对复制粘贴操作，文中提出了一种基于提升小波变换的图像复制粘贴篡改检测算法。首先，对图像进行提升小波变换，提取低频分量，并将其按像素重叠分块；其次，对每个小块图像进行奇异值分解得到奇异值特征向量矩阵，并进行字典排序，再进行欧氏距离修正；最后，根据偏移向量判断相似图块。实验结果表明，该算法能够有效地减少计算量，降低复杂度，使检测结果更准确。

复制粘贴；提升小波变换；奇异值分解；欧氏距离

0 引 言

随着各种简易操作的图像处理软件的盛行，无论是普通用户还是专业用户都可以轻而易举地修改图片，并可以做到真假难辨的程度。如果图像修改只是追求更好效果仅供个人欣赏，则无可厚非，若是被别有用心的人利用，后果将不堪设想。任何事物都具有两面性，在享受信息平台带来便利的同时，也隐藏着安全隐患。因此，开展针对图像篡改检测技术的研究，对于保证公众信任秩序、打击恶意修改和维护司法公正具有十分重要的意义。

图像篡改检测技术按照是否预先在数字图像中嵌入附加信息可以分为主动检测和被动盲检测两种[1]。被动盲检测技术是在无任何先验条件的情况下，进行图像的真伪鉴定[2]，相对于主动检测技术，不需要事先嵌入水印或签名等信息，可以直接对图像内容的真实性进行检测，实用性较强，所以文中采用被动盲检测方法。

图像拼接是图像篡改常用的处理方式[3]，复制粘贴就是最流行的方法之一，即从一幅图像中复制一个或多个区域粘贴到同幅图像中，以此到达隐藏目标信息的目的。针对复制粘贴操作的图像篡改被动盲检测方法主要有穷举搜索法、图像块自相关矩阵法和图像块匹配法[4-5]。穷举搜索法虽然理论简单，精确度高，但运算量很大；图像块自相关矩阵法运算量较穷举搜索法小，但只能检测出较大的复制粘贴图像块，使得其应用受限；图像块匹配法虽然也存在计算量偏大的问题，但是通过其他方法可减少计算量。

1 复制粘贴篡改的图像块匹配检测

图像篡改检测块匹配算法的基本思想是通过分析待测图像中不同区域内容或像素块间的相似程度，对其进行真伪判定[6]，通常有以下五个步骤：图像预处理、图像分块、特征提取、特征匹配、篡改定位。经典的复制粘贴篡改检测流程如图1所示[7-8]。

图1 经典复制粘贴检测流程

图像块匹配法为了更有效地检测到图像中的复制区域，通常在提取特征前对待检测图像进行离散余弦变换(DCT)、离散小波变换(DWT)、主成分分析(PCA)、傅里叶—梅林变换(FMT)、高斯金字塔分解等图像预处理操作，将图像空域特征转换到变换域中，对图像进行降维。整个方法的核心技术是特征提取，不同的算法在此阶段采取不同的方式提取特征。例如在空域提取图像块的均值、标准差、熵、零连通长度等统计特征，在频域提取Hu矩、Zernike矩等各种不变矩特征或SIFT、SURF、MIFT等关键点特征[9]以及采用其他方法如奇异值分解(SVD)[10]来提取特征等等。特征匹配阶段则根据相似度阈值、距离阈值、面积阈值等直接计算或通过聚类来完成。

不同的算法在计算量、计算复杂度以及检测结果上各有不同。文中算法采用提升小波变换和奇异值分解，在减少计算量、降低复杂度的同时可以达到更好的检测效果。

2 基于提升小波变换的图像复制粘贴篡改检测算法

小波变换具有良好的时频局部特性和多分辨分析特性，因此在图像处理方面得到了广泛应用。对图像进行小波变换可以将图像划分为四个分量，即一个低频分量和三个细节分量。低频分量基本上包含了原始图像的概貌特征，细节分量分别代表了图像水平方向、垂直方向和对角方向的细节信息。通过小波变换，基于小波变换的篡改检测算法将被检图像缩减为小波变换所得的低频分量区域，缩小了检测范围，同时也保留了图像信息，但由于传统小波变换的实现是通过卷积完成的，还存在计算复杂、运算速度慢、对内存需求量大的不足[11]。

文中为进一步降低篡改检测运算量、提高复制区域检测成功率，提出基于提升小波变换的图像复制粘贴篡改检测算法。该算法主要包括提升小波变换、奇异值分解、字典排序及修正等关键内容。

2.1 提升小波变换

作为第二代小波变换，提升小波变换既保持了传统小波的时频局部化等特性，又克服了它的局限性，其优越性表现为：

(1)可实现整数小波变换；

(2)不依赖于傅里叶变换实现小波构造；

(3)能在当前位置完成小波变换，节省内存；

(4)具有快速算法，计算更迅速。

提升小波变换的基本思想是通过一个基本小波，逐步构建出一个更具有良好性质的新小波[12]。提升小波变换分为分解和重构两个部分，重构是分解的逆过程，如图2所示[13]。提升算法可以分为三个步骤，即分解、预测、更新。

图2 提升小波变换的分解和重构示意图

(1)分解过程。将输入信号si分为2个较小的子集，一般是将信号分为偶数序列si-1和奇数序列di-1两个子集，如式(1)，其中F(si-1)为分解过程。

F(si-1)=(si-1,di-1)

(1)

(2)

(3)更新过程。经过分解步骤产生的子集的某些整体特征可能与原始数据并不一致，为了保持原始数据的这些整体特征需要一个更新过程，将更新过程用算子U来代替，定义为式(3)。

(3)

2.2 奇异值分解

奇异值分解具有三种特征，即稳定性、比例不变性和旋转不变性[14]。对图像块进行奇异值特征向量提取，可以降低维数，减少计算量，提高抗噪声能力。奇异值分解基本理论如下：设Am×n(m>n)为图像矩阵，则存在两个正交矩阵Um×m和Vn×n及对角矩阵Σm×n满足：

A=UΣVT

其中，Σ=diag(σ1,…,σr,0,…,0)(σ1≥σ2≥…≥σr≥0)，r是矩阵A的秩。

奇异值特征向量的第一个奇异值要比其他奇异值大很多，起着主要作用，所以可以忽略一些不重要的奇异值以降低计算量。假设Y为奇异值特征向量矩阵：

(4)

(5)

2.3 字典排序及修正

由于字典排序过分强调了最大奇异值的作用，有可能会将奇异值相近而不是相似块排在相邻位置，从而导致误差，所以再对排序后的矩阵进行欧氏距离修正。

(6)

2.4 算法步骤

基于提升小波变换的图像复制粘贴篡改检测算法的基本思想是先对图像进行提升小波变换提取低频分量，再将低频分量重叠分块；接着对子块进行奇异值分解，得到奇异值特征向量矩阵；然后对奇异值特征向量矩阵进行字典排序及修正；最后根据子块间的偏移向量来判断复制粘贴篡改区域。具体实现如下：

步骤1：对待检测图像进行提升小波变换。设待检测图像I为M×N矩阵，对图像进行j级提升小波变换，然后提取低频分量LL，低频分量的矩阵大小为(M/2j)×(N/2j)。

步骤2：对提取的低频分量LL进行重叠分块，分块大小为B×B，按像素移位，从上到下从左到右，假设分块大小B×B小于篡改区域，则得到的总块数t为(M/2j-B+1)×(N/2j-B+1)。

步骤4：对得到的新矩阵Y'按字典排序得到新的矩阵St×k。

步骤5：对矩阵St×k进行欧氏距离修正排序，得到欧氏距离修正排序矩阵Wt×k。

(△x,△y)=(xi-xi+1,yi-yi+1)

(7)

步骤7：对于△x>B或者△y>B的行向量进行标记，找出出现频率最多的偏移向量。

复制粘贴区域的相似块堆都具有统一的偏移向量，出现频率最多的偏移向量即可表明潜在的复制粘贴区域，对应于出现频率最多的偏移向量所在块进行标识，算法结束。

3 测试与分析

文中算法的测试环境是MATLAB(R2011a)，处理器运行频率2.2GHz、内存2.0G的笔记本电脑。对检测结果影响大的是子块大小的设置和贡献率的选取。B值太小，虚警率过高；B值太大，则会导致漏检。B的选取需根据情况来定，经过对多组阈值进行测试，其中以η大于0.90或0.95，M为500或者700效果更好。测试中的图像均为256×256，对于彩色图像，都是将其转换成灰色图像检测的。

以参数B为12，η>0.90，M为500的一组阈值进行仿真测试，结果如图3所示。其中图(c)、(d)是图(a)的低频分量的重构图，图中涂黑部分为复制粘贴区域。由此可见，图(d)的检测结果更为准确。

4 结束语

文中分析了图像复制粘贴篡改检测的图像块匹配法，并提出一种基于提升小波变换的篡改检测方法。与文献[4]算法比较，文中算法采用了提升小波变换，对图像降维，降低计算复杂度；在疑似区域判定的方法上做了改进，减少计算量。实验结果表明，该算法计算复杂度低，检测结果更为准确。

图3 仿真结果图

[1]NgTT,ChangSF,SunQ.Blinddetectionofphotomontageusinghigherorderstatistics[C]//Proceedingsofthe2004internationalsymposiumoncircuitsandsystems.[s.l.]:IEEE,2004.

[2] 周琳娜.数字图像盲取证技术研究[D].北京:北京邮电大学,2007.

[3]NgTT,ChangSF.Amodelforimagesplicing[C]//Procofinternationalconferenceonimageprocessing.[s.l.]:[s.n.],2004:24-27.

[4] 康 丽.数字图像内容人为篡改检测[D].重庆:西南大学,2011.

[5] 单 薇.基于复制粘贴的数字图像篡改检测研究[D].苏州:苏州大学,2014.

[6] 仝艳菲.基于分块匹配的图像被动取证算法研究[D].成都:西南交通大学,2014.

[7]ChristleinV,RiessC,AngelopoulouE.Onrotationinvarianceincopy-moveforgerydetection[C]//ProcofIEEEinternationalworkshoponinformationforensicsandsecurity.[s.l.]:IEEE,2010:1-6.

[8]Al-QershiOM,BeK.Passivedetectionofcopy-moveforgeryindigitalimages:state-of-the-art[J].ForensicScienceInternational,2013,231(1):284-295.

[9]BirajdarGK,MankarVH.Digitalimageforgerydetectionusingpassivetechniques:asurvey[J].DigitalInvestigation,2013,10(3):226-245.

[10] 夏 鼐.基于离散小波变换的图像篡改的检测[D].北京:中国科学院大学,2013.

[11] 高世伟,郭 雷,杜亚琴,等.提升小波变换及其在图像处理中的应用[J].计算机工程与设计,2007,28(9):2066-2069.

[12] 林椹尠.提升格式下的小波变换在图像处理中的算法研究[D].西安:西安电子科技大学,2005.

[13] 胡昌华,李国华,周 涛.基于MATLAB7.x的系统分析与设计—小波分析[M].西安：西安电子科技大学出版社,2008.

[14]ZhangT,WangRD.Copy-MoveForgeryDetectionBasedonSVDindigitalimage[C]//Procof2ndinternationalcongressonimageandsignalprocessing.[s.l.]:IEEE,2009:1-5.

Image Forgery Detection Algorithm Based on Lifting Wavelet Transform

CHAI Xin-xin,QIU Xiao-hui

(College of Telecommunications & Information Engineering，Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Image in human perception plays a very important role,whose content is more plentiful.There are a large number of images in the Internet which spread quickly,so identifying image of authenticity is particularly important.The operation of copy-move is one of the frequently used techniques in image tampering,which can modify or hide the target image’s information.For this means,a new approach toward copy-move forgery detection is proposed based on lifting wavelet transform.Firstly,the input image is decomposed into approximation (LL) subbands using lifting wavelet transform,and the LL subbands are divided into overlapping blocks.Secondly,singular value decomposition is applied to each block to obtain singular value feature matrix which is lexicographically sorted,and after sorting the matrix is fixed by Euclidean distance.Finally,the similar blocks can be judged by offset vectors.The experimental results demonstrate that the proposed method can reduce calculation amount and complexity effectively,and have more accurate detection results.

copy-move;lifting wave transform;SVD;Euclidean distance

2015-07-10

2015-10-16

时间：2016-03-22

江苏省自然科学基金( BK2011789)；东南大学毫米波国家重点实验室开放课题(K201318)

柴新新(1988-)，女，硕士研究生，研究方向为智能信号处理、数字图像处理；邱晓晖，教授，研究方向为现代信号中的智能信号处理。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1520.062.html

TP301.6

A

1673-629X(2016)04-0078-04

10.3969/j.issn.1673-629X.2016.04.017