基于提升小波變換的圖像篡改檢測(cè)算法

柴新新，邱曉暉

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

基于提升小波變換的圖像篡改檢測(cè)算法

柴新新，邱曉暉

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

圖像在人類的感知中扮演著非常重要的角色，所傳遞的信息比其他任何形式更加豐富真切，而互聯(lián)網(wǎng)中存在著大量的圖像圖片并且傳播快速，這就使得辨別圖像的真?zhèn)巫兊糜葹橹匾?fù)制粘貼操作是最為常見(jiàn)的圖像篡改手段之一，通過(guò)該手段可以達(dá)到修改或隱藏目標(biāo)圖像的目的。針對(duì)復(fù)制粘貼操作，文中提出了一種基于提升小波變換的圖像復(fù)制粘貼篡改檢測(cè)算法。首先，對(duì)圖像進(jìn)行提升小波變換，提取低頻分量，并將其按像素重疊分塊；其次，對(duì)每個(gè)小塊圖像進(jìn)行奇異值分解得到奇異值特征向量矩陣，并進(jìn)行字典排序，再進(jìn)行歐氏距離修正；最后，根據(jù)偏移向量判斷相似圖塊。實(shí)驗(yàn)結(jié)果表明，該算法能夠有效地減少計(jì)算量，降低復(fù)雜度，使檢測(cè)結(jié)果更準(zhǔn)確。

復(fù)制粘貼；提升小波變換；奇異值分解；歐氏距離

0 引 言

隨著各種簡(jiǎn)易操作的圖像處理軟件的盛行，無(wú)論是普通用戶還是專業(yè)用戶都可以輕而易舉地修改圖片，并可以做到真假難辨的程度。如果圖像修改只是追求更好效果僅供個(gè)人欣賞，則無(wú)可厚非，若是被別有用心的人利用，后果將不堪設(shè)想。任何事物都具有兩面性，在享受信息平臺(tái)帶來(lái)便利的同時(shí)，也隱藏著安全隱患。因此，開(kāi)展針對(duì)圖像篡改檢測(cè)技術(shù)的研究，對(duì)于保證公眾信任秩序、打擊惡意修改和維護(hù)司法公正具有十分重要的意義。

圖像篡改檢測(cè)技術(shù)按照是否預(yù)先在數(shù)字圖像中嵌入附加信息可以分為主動(dòng)檢測(cè)和被動(dòng)盲檢測(cè)兩種[1]。被動(dòng)盲檢測(cè)技術(shù)是在無(wú)任何先驗(yàn)條件的情況下，進(jìn)行圖像的真?zhèn)舞b定[2]，相對(duì)于主動(dòng)檢測(cè)技術(shù)，不需要事先嵌入水印或簽名等信息，可以直接對(duì)圖像內(nèi)容的真實(shí)性進(jìn)行檢測(cè)，實(shí)用性較強(qiáng)，所以文中采用被動(dòng)盲檢測(cè)方法。

圖像拼接是圖像篡改常用的處理方式[3]，復(fù)制粘貼就是最流行的方法之一，即從一幅圖像中復(fù)制一個(gè)或多個(gè)區(qū)域粘貼到同幅圖像中，以此到達(dá)隱藏目標(biāo)信息的目的。針對(duì)復(fù)制粘貼操作的圖像篡改被動(dòng)盲檢測(cè)方法主要有窮舉搜索法、圖像塊自相關(guān)矩陣法和圖像塊匹配法[4-5]。窮舉搜索法雖然理論簡(jiǎn)單，精確度高，但運(yùn)算量很大；圖像塊自相關(guān)矩陣法運(yùn)算量較窮舉搜索法小，但只能檢測(cè)出較大的復(fù)制粘貼圖像塊，使得其應(yīng)用受限；圖像塊匹配法雖然也存在計(jì)算量偏大的問(wèn)題，但是通過(guò)其他方法可減少計(jì)算量。

1 復(fù)制粘貼篡改的圖像塊匹配檢測(cè)

圖像篡改檢測(cè)塊匹配算法的基本思想是通過(guò)分析待測(cè)圖像中不同區(qū)域內(nèi)容或像素塊間的相似程度，對(duì)其進(jìn)行真?zhèn)闻卸╗6]，通常有以下五個(gè)步驟：圖像預(yù)處理、圖像分塊、特征提取、特征匹配、篡改定位。經(jīng)典的復(fù)制粘貼篡改檢測(cè)流程如圖1所示[7-8]。

圖1 經(jīng)典復(fù)制粘貼檢測(cè)流程

圖像塊匹配法為了更有效地檢測(cè)到圖像中的復(fù)制區(qū)域，通常在提取特征前對(duì)待檢測(cè)圖像進(jìn)行離散余弦變換(DCT)、離散小波變換(DWT)、主成分分析(PCA)、傅里葉—梅林變換(FMT)、高斯金字塔分解等圖像預(yù)處理操作，將圖像空域特征轉(zhuǎn)換到變換域中，對(duì)圖像進(jìn)行降維。整個(gè)方法的核心技術(shù)是特征提取，不同的算法在此階段采取不同的方式提取特征。例如在空域提取圖像塊的均值、標(biāo)準(zhǔn)差、熵、零連通長(zhǎng)度等統(tǒng)計(jì)特征，在頻域提取Hu矩、Zernike矩等各種不變矩特征或SIFT、SURF、MIFT等關(guān)鍵點(diǎn)特征[9]以及采用其他方法如奇異值分解(SVD)[10]來(lái)提取特征等等。特征匹配階段則根據(jù)相似度閾值、距離閾值、面積閾值等直接計(jì)算或通過(guò)聚類來(lái)完成。

不同的算法在計(jì)算量、計(jì)算復(fù)雜度以及檢測(cè)結(jié)果上各有不同。文中算法采用提升小波變換和奇異值分解，在減少計(jì)算量、降低復(fù)雜度的同時(shí)可以達(dá)到更好的檢測(cè)效果。

2 基于提升小波變換的圖像復(fù)制粘貼篡改檢測(cè)算法

小波變換具有良好的時(shí)頻局部特性和多分辨分析特性，因此在圖像處理方面得到了廣泛應(yīng)用。對(duì)圖像進(jìn)行小波變換可以將圖像劃分為四個(gè)分量，即一個(gè)低頻分量和三個(gè)細(xì)節(jié)分量。低頻分量基本上包含了原始圖像的概貌特征，細(xì)節(jié)分量分別代表了圖像水平方向、垂直方向和對(duì)角方向的細(xì)節(jié)信息。通過(guò)小波變換，基于小波變換的篡改檢測(cè)算法將被檢圖像縮減為小波變換所得的低頻分量區(qū)域，縮小了檢測(cè)范圍，同時(shí)也保留了圖像信息，但由于傳統(tǒng)小波變換的實(shí)現(xiàn)是通過(guò)卷積完成的，還存在計(jì)算復(fù)雜、運(yùn)算速度慢、對(duì)內(nèi)存需求量大的不足[11]。

文中為進(jìn)一步降低篡改檢測(cè)運(yùn)算量、提高復(fù)制區(qū)域檢測(cè)成功率，提出基于提升小波變換的圖像復(fù)制粘貼篡改檢測(cè)算法。該算法主要包括提升小波變換、奇異值分解、字典排序及修正等關(guān)鍵內(nèi)容。

2.1 提升小波變換

作為第二代小波變換，提升小波變換既保持了傳統(tǒng)小波的時(shí)頻局部化等特性，又克服了它的局限性，其優(yōu)越性表現(xiàn)為：

(1)可實(shí)現(xiàn)整數(shù)小波變換；

(2)不依賴于傅里葉變換實(shí)現(xiàn)小波構(gòu)造；

(3)能在當(dāng)前位置完成小波變換，節(jié)省內(nèi)存；

(4)具有快速算法，計(jì)算更迅速。

提升小波變換的基本思想是通過(guò)一個(gè)基本小波，逐步構(gòu)建出一個(gè)更具有良好性質(zhì)的新小波[12]。提升小波變換分為分解和重構(gòu)兩個(gè)部分，重構(gòu)是分解的逆過(guò)程，如圖2所示[13]。提升算法可以分為三個(gè)步驟，即分解、預(yù)測(cè)、更新。

圖2 提升小波變換的分解和重構(gòu)示意圖

(1)分解過(guò)程。將輸入信號(hào)si分為2個(gè)較小的子集，一般是將信號(hào)分為偶數(shù)序列si-1和奇數(shù)序列di-1兩個(gè)子集，如式(1)，其中F(si-1)為分解過(guò)程。

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

(1)

(2)

(3)更新過(guò)程。經(jīng)過(guò)分解步驟產(chǎn)生的子集的某些整體特征可能與原始數(shù)據(jù)并不一致，為了保持原始數(shù)據(jù)的這些整體特征需要一個(gè)更新過(guò)程，將更新過(guò)程用算子U來(lái)代替，定義為式(3)。

(3)

2.2 奇異值分解

奇異值分解具有三種特征，即穩(wěn)定性、比例不變性和旋轉(zhuǎn)不變性[14]。對(duì)圖像塊進(jìn)行奇異值特征向量提取，可以降低維數(shù)，減少計(jì)算量，提高抗噪聲能力。奇異值分解基本理論如下：設(shè)Am×n(m>n)為圖像矩陣，則存在兩個(gè)正交矩陣Um×m和Vn×n及對(duì)角矩陣Σm×n滿足：

A=UΣVT

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

奇異值特征向量的第一個(gè)奇異值要比其他奇異值大很多，起著主要作用，所以可以忽略一些不重要的奇異值以降低計(jì)算量。假設(shè)Y為奇異值特征向量矩陣：

(4)

(5)

2.3 字典排序及修正

由于字典排序過(guò)分強(qiáng)調(diào)了最大奇異值的作用，有可能會(huì)將奇異值相近而不是相似塊排在相鄰位置，從而導(dǎo)致誤差，所以再對(duì)排序后的矩陣進(jìn)行歐氏距離修正。

(6)

2.4 算法步驟

基于提升小波變換的圖像復(fù)制粘貼篡改檢測(cè)算法的基本思想是先對(duì)圖像進(jìn)行提升小波變換提取低頻分量，再將低頻分量重疊分塊；接著對(duì)子塊進(jìn)行奇異值分解，得到奇異值特征向量矩陣；然后對(duì)奇異值特征向量矩陣進(jìn)行字典排序及修正；最后根據(jù)子塊間的偏移向量來(lái)判斷復(fù)制粘貼篡改區(qū)域。具體實(shí)現(xiàn)如下：

步驟1：對(duì)待檢測(cè)圖像進(jìn)行提升小波變換。設(shè)待檢測(cè)圖像I為M×N矩陣，對(duì)圖像進(jìn)行j級(jí)提升小波變換，然后提取低頻分量LL，低頻分量的矩陣大小為(M/2j)×(N/2j)。

步驟2：對(duì)提取的低頻分量LL進(jìn)行重疊分塊，分塊大小為B×B，按像素移位，從上到下從左到右，假設(shè)分塊大小B×B小于篡改區(qū)域，則得到的總塊數(shù)t為(M/2j-B+1)×(N/2j-B+1)。

步驟4：對(duì)得到的新矩陣Y'按字典排序得到新的矩陣St×k。

步驟5：對(duì)矩陣St×k進(jìn)行歐氏距離修正排序，得到歐氏距離修正排序矩陣Wt×k。

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

(7)

步驟7：對(duì)于△x>B或者△y>B的行向量進(jìn)行標(biāo)記，找出出現(xiàn)頻率最多的偏移向量。

復(fù)制粘貼區(qū)域的相似塊堆都具有統(tǒng)一的偏移向量，出現(xiàn)頻率最多的偏移向量即可表明潛在的復(fù)制粘貼區(qū)域，對(duì)應(yīng)于出現(xiàn)頻率最多的偏移向量所在塊進(jìn)行標(biāo)識(shí)，算法結(jié)束。

3 測(cè)試與分析

文中算法的測(cè)試環(huán)境是MATLAB(R2011a)，處理器運(yùn)行頻率2.2GHz、內(nèi)存2.0G的筆記本電腦。對(duì)檢測(cè)結(jié)果影響大的是子塊大小的設(shè)置和貢獻(xiàn)率的選取。B值太小，虛警率過(guò)高；B值太大，則會(huì)導(dǎo)致漏檢。B的選取需根據(jù)情況來(lái)定，經(jīng)過(guò)對(duì)多組閾值進(jìn)行測(cè)試，其中以η大于0.90或0.95，M為500或者700效果更好。測(cè)試中的圖像均為256×256，對(duì)于彩色圖像，都是將其轉(zhuǎn)換成灰色圖像檢測(cè)的。

以參數(shù)B為12，η>0.90，M為500的一組閾值進(jìn)行仿真測(cè)試，結(jié)果如圖3所示。其中圖(c)、(d)是圖(a)的低頻分量的重構(gòu)圖，圖中涂黑部分為復(fù)制粘貼區(qū)域。由此可見(jiàn)，圖(d)的檢測(cè)結(jié)果更為準(zhǔn)確。

4 結(jié)束語(yǔ)

文中分析了圖像復(fù)制粘貼篡改檢測(cè)的圖像塊匹配法，并提出一種基于提升小波變換的篡改檢測(cè)方法。與文獻(xiàn)[4]算法比較，文中算法采用了提升小波變換，對(duì)圖像降維，降低計(jì)算復(fù)雜度；在疑似區(qū)域判定的方法上做了改進(jìn)，減少計(jì)算量。實(shí)驗(yàn)結(jié)果表明，該算法計(jì)算復(fù)雜度低，檢測(cè)結(jié)果更為準(zhǔn)確。

圖3 仿真結(jié)果圖

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

[2] 周琳娜.數(shù)字圖像盲取證技術(shù)研究[D].北京:北京郵電大學(xué),2007.

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

[4] 康 麗.數(shù)字圖像內(nèi)容人為篡改檢測(cè)[D].重慶:西南大學(xué),2011.

[5] 單 薇.基于復(fù)制粘貼的數(shù)字圖像篡改檢測(cè)研究[D].蘇州:蘇州大學(xué),2014.

[6] 仝艷菲.基于分塊匹配的圖像被動(dòng)取證算法研究[D].成都:西南交通大學(xué),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] 夏 鼐.基于離散小波變換的圖像篡改的檢測(cè)[D].北京:中國(guó)科學(xué)院大學(xué),2013.

[11] 高世偉,郭 雷,杜亞琴,等.提升小波變換及其在圖像處理中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(9):2066-2069.

[12] 林椹尠.提升格式下的小波變換在圖像處理中的算法研究[D].西安:西安電子科技大學(xué),2005.

[13] 胡昌華,李國(guó)華,周 濤.基于MATLAB7.x的系統(tǒng)分析與設(shè)計(jì)—小波分析[M].西安：西安電子科技大學(xué)出版社,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

時(shí)間：2016-03-22

江蘇省自然科學(xué)基金( BK2011789)；東南大學(xué)毫米波國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題(K201318)

柴新新(1988-)，女，碩士研究生，研究方向?yàn)橹悄苄盘?hào)處理、數(shù)字圖像處理；邱曉暉，教授，研究方向?yàn)楝F(xiàn)代信號(hào)中的智能信號(hào)處理。

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