王泓鑫 李碩

摘 要：檢測(cè)數(shù)字圖像復(fù)制—粘貼型篡改是目前研究熱點(diǎn)之一。多數(shù)復(fù)制—粘貼篡改檢測(cè)方案只對(duì)剛性平移篡改具有較好的檢測(cè)精度，無(wú)法有效應(yīng)對(duì)更復(fù)雜的幾何變換和常規(guī)信號(hào)攻擊。為優(yōu)化數(shù)字圖像復(fù)制—粘貼篡改檢測(cè)效率和精度，首次提出一種使用極坐標(biāo)復(fù)指數(shù)變換（PCET）與一致性敏感哈希（CSH）的高效檢測(cè)算法。首先，計(jì)算滑動(dòng)窗口PCET系數(shù)，將其作為不變的圖像局部特征;然后，根據(jù)這些特征，利用CSH算法快速、精確地匹配大量密集分塊;最后，使用基于密集線性濾波的后處理算法消除匹配結(jié)果中的錯(cuò)誤匹配并定位重復(fù)區(qū)域，得到最終檢測(cè)結(jié)果。根據(jù)實(shí)驗(yàn)結(jié)果可知，該算法不僅檢測(cè)精度平均提高12.06%，而且處理時(shí)間平均縮短315.64s。因此利用對(duì)幾何變換和常規(guī)信號(hào)攻擊魯棒的PCET系數(shù)刻畫(huà)圖像局部特征，并采用基于圖像一致性的快速高精度匹配算法CSH，可有效優(yōu)化復(fù)制—粘貼篡改檢測(cè)精度和效率。

關(guān)鍵詞：復(fù)制—粘貼型篡改;圖像矩;區(qū)域復(fù)制;旋轉(zhuǎn)不變

DOI：10. 11907/rjdk. 192614 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP317.4 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）008-0221-05

Abstract： Detecting copy-move forgery of digital images is one of the current research hotspots. However， most existing copy-move forgery detection schemes are generally only robust to translation， and they are not effective in dealing with more complex geometric transformations and conventional signal processing attacks. In addition， such algorithms are often time-consuming and cannot meet the needs of real-time detection. In order to optimize the efficiency and accuracy of digital image copy-move forgery detection， a fast and effective algorithm using polar complex exponential transform （PCET） and coherency sensitive hashing （CSH） was proposed in this paper. First， the algorithm calculates the PCET coefficients of the sliding windows as invariant local features. Then， based on these feature vectors， a large number of dense windows will be quickly and accurately matched by the CSH algorithm. Finally， the dense linear fitting （DLF） based post-processing algorithm is used to eliminate the mismatches and locate the duplicated regions. In this paper， five challenging tampered images are selected from GRIP and FAU databases， and the accuracy and speed are compared with classic algorithm. According to the experimental results， the proposed algorithm not only improves the average detection accuracy by 12.06%， but also reduces the average processing time by 315.64 seconds. PCET coefficients that are robust to geometric transformations and conventional signal processing attacks are used to characterize image local features. Moreover， image coherency based CSH is introduced for fast and high-precision feature matching. Therefore， the proposed algorithm is able to effectively optimize the accuracy and efficiency of detection.

Key Words： copy-move forgery;image moment; region duplication; rotation invariance

0 引言

圖像作為人類最重要的信息來(lái)源之一，在群體和個(gè)人意見(jiàn)形成過(guò)程中扮演關(guān)鍵角色。然而，現(xiàn)代圖像處理軟件（Photoshop、Gim）及個(gè)人電腦和終端的快速推廣，使人們可以極低的成本篡改數(shù)字圖像內(nèi)容。這對(duì)數(shù)字圖像可靠性產(chǎn)生了嚴(yán)重威脅，若篡改的圖像應(yīng)用于關(guān)鍵場(chǎng)景，可能導(dǎo)致嚴(yán)重的社會(huì)后果。

復(fù)制—粘貼篡改是一類常見(jiàn)的圖像篡改手段，其中圖像一個(gè)或多個(gè)區(qū)域被復(fù)制并粘貼在同一圖像中的其它位置，其目的是隱藏或強(qiáng)調(diào)感興趣的對(duì)象[1]。盡管該篡改過(guò)程非常簡(jiǎn)單，但由于圖像存在同源性和差異性，檢測(cè)難度較大。在過(guò)去的10年中，多個(gè)復(fù)制—粘貼篡改檢測(cè)方案被提出[2- 3]。它們基本遵循一個(gè)通用框架：特征提取、特征匹配和后處理。根據(jù)是從每個(gè)像素中提取局部圖像特征，還是僅從某些選定特征點(diǎn)中提取特征，檢測(cè)方案可分為兩大類：基于塊的方法和基于特征點(diǎn)的方法。其中，基于特征點(diǎn)的方法因?yàn)樘卣鼽c(diǎn)稀疏性，檢測(cè)結(jié)果通常不如基于塊的方法精確。對(duì)基于塊的方法，現(xiàn)有文獻(xiàn)更多關(guān)注特征提取和匹配兩個(gè)階段。

在特征提取方面，不同的篡改檢測(cè)方法使用不同的變換描述圖像塊。常用變換方法包括離散余弦變換（Discrete Cosine Transform，DCT）[4]、離散小波變換（Discrete Wavelet Transform，DWT）[5]、傅立葉變換（Fourier Transform，F(xiàn)T）[6]、主成分分析（Principal Component Analysis，PCA）[7]和奇異值分解（Singular Value Decomposition，SVD）[8]。但是，這些特征在旋轉(zhuǎn)和縮放攻擊下非常脆弱。因此，出現(xiàn)新算法使用更復(fù)雜的幾何不變變換，如Hu矩（Hu Moments）[9]、澤尼克矩（Zernike Moments，ZM）[10]、傅里葉—梅林變換（Fourier-Mellin Transform，F(xiàn)MT）[11]和極坐標(biāo)余弦變換（Polar Cosine Transform，PCT）[12]。這些方法在抵抗幾何攻擊方面表現(xiàn)出更出色的檢測(cè)精度。

在特征匹配方面，大量圖像塊 （105～106） 需進(jìn)行匹配以揭示篡改。傳統(tǒng)匹配算法主要包括暴力搜索、字典排序、KD樹(shù)和局部敏感哈希算法（Locality Sensitivity Hashing，LSH）[13]，通常需高昂的時(shí)間成本。這主要是因?yàn)檫@些技術(shù)是通用的，并非專門用于篡改檢測(cè)任務(wù)，還忽略了該領(lǐng)域一項(xiàng)重要的先驗(yàn)知識(shí)：自然圖像平滑性和自相似性意味著領(lǐng)近像素最近鄰在空間上很大可能也彼此接近。受此啟發(fā)，一些更適用于復(fù)制-粘貼篡改檢測(cè)的匹配算法受到關(guān)注，包括PatchMatch [14]和一致性敏感哈希算法（Coherency Sensitive Hashing， CSH）[15]。由于充分利用了先驗(yàn)知識(shí)，這些對(duì)特征點(diǎn)位置敏感的新穎匹配策略在時(shí)間效率方面大幅度領(lǐng)先于其它方法。

為優(yōu)化數(shù)字圖像復(fù)制—粘貼篡改檢測(cè)效率和精度，本文首次提出一種使用極坐標(biāo)復(fù)指數(shù)變換（PCET）[16]與一致性敏感哈希（CSH）[17]的高效檢測(cè)算法。首先，計(jì)算滑動(dòng)窗口PCET系數(shù)，并將其作為不變的圖像局部特征;然后，根據(jù)這些特征，大量密集分塊由CSH算法快速、精確地匹配;最后，使用密集線性濾波（Dense Linear Fitting，DLF）[14]處理算法消除匹配結(jié)果中的錯(cuò)誤匹配，并定位重復(fù)區(qū)域，得到最終檢測(cè)結(jié)果。根據(jù)實(shí)驗(yàn)結(jié)果可知，該算法不僅可大幅提高檢測(cè)精度，還可極大壓縮基于塊的檢測(cè)算法時(shí)間成本。

1 復(fù)制—粘貼篡改檢測(cè)算法

1.1 極坐標(biāo)復(fù)指數(shù)變換

極諧變換 （Polar Harmonic Transforms，PHTs） 由Yap等[16]于2010年提出，是一種定義域?yàn)閱挝粓A的新型正交矩。PHTs包括極坐標(biāo)復(fù)指數(shù)變換 （PCET）、極坐標(biāo)余弦變換 （PCT）和極坐標(biāo)正弦變換 （Polar Sine Transform， PST）。本文聚焦于PCET。

由式（7）可知，將圖像旋轉(zhuǎn)一個(gè)角度后的PCET的模與原始圖像PCET的模相等。

1.2 一致性敏感哈希算法

一致性敏感哈希（CSH）算法 [17]擴(kuò)展于LSH算法和PatchMatch算法，可達(dá)到快速匹配圖像片段的效果。LSH基于圖像哈希算法，它會(huì)將相似的圖像塊投影到相同的桶 （Bin）中，因此算法可在桶中找到匹配圖像塊。LSH匹配精度雖然很高，但需高昂的計(jì)算成本。PatchMatch算法則基于圖像一致性，在自然圖像中迭代地進(jìn)行最優(yōu)偏移向量估計(jì)，并利用一致性獲得全局最優(yōu)的匹配偏移。由于使用了先驗(yàn)知識(shí)，算法計(jì)算復(fù)雜度很低，但有隨機(jī)性和匹配誤差大等缺點(diǎn)。CSH是LSH和PatchMatch的融合算法，首先CSH使用LSH查找初始匹配圖像塊 （而不是使用PatchMatch的隨機(jī)初始化） ，然后再利用PatchMatch在圖像中具有一致性的區(qū)域拓展正確匹配 （而不是僅使用CSH的圖像哈希） 。通常，CSH匹配時(shí)間遠(yuǎn)少于PatchMatch，且匹配精確也更高。顯然CSH對(duì)于自然圖像篡改檢測(cè)任務(wù)非常有效。

CSH算法流程可分為兩大部分：建立索引和搜索。算法輸入是特征矩陣[A]和[B] （[A]和[B]可以相同） ，[A]為源，[B]為目標(biāo)，輸出是近似的最近鄰域（Approximate Nearest Neighbor Fields，ANNF）。

1.2.1 索引建立

如此操作直至窮盡[PB]中的所有元素。

在上述搜索流程中，生成最近鄰候選集[PB]是關(guān)鍵操作。為簡(jiǎn)化討論，首先引入幾個(gè)標(biāo)記。定義哈希函數(shù)為[g]，由該函數(shù)生成的哈希表為[T]。此外，將哈希函數(shù)[g]分為[gA]和[gB]：當(dāng)對(duì)[A（B）]中的塊[a（b）]進(jìn)行哈希時(shí)，哈希函數(shù)[g]標(biāo)記為[gA（gB）]，生成的哈希表記為[TA（TB）]，并引入[gA]（[gB]）的逆運(yùn)算[g-1A]（[g-1B]）。塊[p]的上、下、左、右鄰接塊分別記[Top（p），Bottom（p），Left（p），Right（p）]。[A]中的塊[a]在[B]中目前已知的最近鄰塊記為[Cand（a）]。

CSH算法匹配候選技術(shù)基于以下4個(gè)定理，其中，[a，a1，a2]是[A]中的塊，[b，b1，b2]是[B]中的塊。

定理1：如果[gA（a）=gB（b）]，則[b]是[a]的一個(gè) （最佳） 候選。

定理2：如果[b]是[a1]的候選，并且[gA（a1）=gA（a2）]，則[b]也是[a2]的候選。

定理3：如果[b1]是[a]的候選，并且[gB（b1）=gB（b2）]，則[b2]也是[a]的候選。

定理4：如果[b]是[Left（a）]的候選，則[Right（b）]是[a]的候選 （該定理對(duì)于Right/Left Top/Bottom和Bottom/Top對(duì)同樣成立） 。

上述4項(xiàng)定理出自LSH和PatchMatch算法假設(shè)，其中定理1至定理3源自LSH，依賴于表示空間，定理4出自PatchMatch，依賴于一致性。以這4條定理為基礎(chǔ)，CSH算法定義了3種匹配候選方式，其公式定義和直觀表示分別見(jiàn)表1、圖3（彩圖掃描OSID碼可見(jiàn)），該定義對(duì)于類型2，Top/Bottom對(duì)同樣成立。

圖3中，紅色箭頭表示哈希函數(shù)[g]（請(qǐng)注意箭頭方向和表1公式定義之間的對(duì)應(yīng)關(guān)系） ，綠色箭頭表示目前已知最近鄰塊[Cand（ ）]，[A]中的淺藍(lán)色塊表示[a]，[B]中紫色塊并集是[a]的最近鄰候選集[PB]，在[A]和[B]中間的哈希表[T]實(shí)際上是由[TA]和[TB]合并得到的，[TA（TB）]的寬度指哈希表中每個(gè)桶最多可儲(chǔ)存的塊數(shù)，設(shè)置為[k]。則在理想情況下，類型1和類型3每個(gè)類型將貢獻(xiàn)[k]個(gè)候選塊，類型2中Left/Right對(duì)和Top/Bottom對(duì)每對(duì)將貢獻(xiàn)[k+1]個(gè)候選塊，因此[PB]的勢(shì)最大為[4k+2]。

可以看出，CSH的3種匹配候選方式融合折中了LSH與PatchMatch的匹配方式，這使得CSH算法高效且精確。通過(guò)3種匹配候選方式，[A]中的任意塊[a]都得到了自己最近鄰候選集[PB]。

1.3 算法流程

本文提出的復(fù)制-粘貼篡改檢測(cè)算法充分利用了PCET與CSH的優(yōu)勢(shì)。首先，密集圖像分塊特征表示基于PCET系數(shù)，特征對(duì)于旋轉(zhuǎn)攻擊不變，而且在噪聲魯棒性方面表現(xiàn)良好。這是傳統(tǒng)空域特征和頻域特征所不具有的。隨后，CSH被用于圖像密集域局部不變特征的匹配，較于經(jīng)典的匹配策略，它在特征匹配速度和精度兩方面均有大幅改進(jìn)。整體上算法包括以下步驟：

步驟1：將給定的彩圖原始圖像變換為灰度圖像。

步驟2：計(jì)算密集分塊的PCET系數(shù) [16]，并取系數(shù)的模作為特征。

步驟3：使用CSH [17]對(duì)圖像塊特征進(jìn)行快速精確匹配，得到相應(yīng)匹配結(jié)果。

步驟4：對(duì)匹配結(jié)果使用DLF算法[14]進(jìn)行誤匹配篩除，并使用形態(tài)學(xué)方法優(yōu)化結(jié)果，最后標(biāo)記篡改區(qū)域。

2 實(shí)驗(yàn)結(jié)果

本文實(shí)驗(yàn)環(huán)境為：Matlab R2016a、3.60GHz 中央處理器和16GB 內(nèi)存。為使實(shí)驗(yàn)結(jié)果更有說(shuō)服力，來(lái)自GRIP [14]和FAU [18]數(shù)據(jù)庫(kù)的5幅測(cè)試圖像用于本次實(shí)驗(yàn)。

算法參數(shù)方面，圖像塊大小為[25×25]、特征的最大階數(shù)為5、匹配對(duì)最小距離為50像素、篡改區(qū)域最小尺寸為圖像尺寸的0.002%。

圖4給出了相關(guān)實(shí)驗(yàn)結(jié)果，其中第一列是原始圖像、第二列是篡改圖像、第三列是真實(shí)篡改區(qū)域、第四列是文獻(xiàn)[19]的檢測(cè)結(jié)果、第五列是本文算法的檢測(cè)結(jié)果?？梢钥吹?，本文算法檢測(cè)精度非常高，對(duì)各類篡改 （特別是多對(duì)象篡改） 有很強(qiáng)的檢測(cè)能力。

3 結(jié)語(yǔ)

本文提出了一種新穎的數(shù)字圖像復(fù)制—粘貼篡改檢測(cè)方法，可同時(shí)提高檢測(cè)精度和效率。該算法充分利用了PCET和CSH技術(shù)優(yōu)勢(shì)。首先，使用PCET抽取密集圖像分塊的高階特征，PCET系數(shù)對(duì)旋轉(zhuǎn)具有不變性，而且低階系數(shù)對(duì)噪聲類圖像攻擊具有魯棒性。相比于傳統(tǒng)空域特征和頻域特征，這有助于跨越語(yǔ)義鴻溝;隨后，基于圖像一致性這一關(guān)鍵先驗(yàn)知識(shí)，采用CSH匹配圖像密集域局部不變特征。較于計(jì)算機(jī)視覺(jué)領(lǐng)域中常規(guī)的匹配策略，CSH在特征匹配速度和精度兩方面均具有優(yōu)勢(shì)。從具體實(shí)驗(yàn)結(jié)果來(lái)看，本文算法不僅在檢測(cè)精度上平均高出經(jīng)典方案12.06%，而且在計(jì)算時(shí)間方面也比經(jīng)典方案減少了315.64秒。這證明本文算法具有較好的精度和效率，圖像矩方法與基于一致性的匹配算法在復(fù)制-粘貼篡改檢測(cè)領(lǐng)域具有獨(dú)特優(yōu)勢(shì)。

盡管本文算法對(duì)于常見(jiàn)的幾何攻擊（如旋轉(zhuǎn)、縮放、翻轉(zhuǎn)）具有較好的魯棒性，但由于使用了固定尺寸的圖像塊，導(dǎo)致縮放魯棒性僅在有限范圍內(nèi)可滿足。下一步將聯(lián)合尺度空間理論和圖像矩方法，尋找一種可行的優(yōu)化方法。

參考文獻(xiàn)：

[1] 呂穎達(dá)，申鉉京，陳海鵬. 具有幾何不變性的圖像復(fù)制—粘貼盲鑒別算法[J]. 電子學(xué)報(bào)，2016， 44（11）： 2592-2599.

[2] 畢秀麗，魏楊，肖斌，等. 基于級(jí)聯(lián)卷積神經(jīng)網(wǎng)絡(luò)的圖像篡改檢測(cè)算法[J]. 電子與信息學(xué)報(bào)， 2019， 41： 1-8.

[3] 許曼曼，楊繼翔. 數(shù)字圖像復(fù)制—粘貼篡改檢測(cè)與定位算法[J]. 軟件導(dǎo)刊，2016，15（11）： 199-201.

[4] FRIDRICH A J，SOUKAL B D， LUKá ?A J. Detection of copy-move forgery in digital images[C]. Proceedings of Digital Forensic Research Workshop，2003： 94-100 .

[5] MUHAMMAD G，HUSSAIN M，BEBIS G. Passive copy move image forgery detection using undecimated dyadic wavelet transform[J]. Digital Investigation， 2012， 9（1）： 49-57.

[6] BRAVO-SOLORIO S，NANDI A K. Exposing duplicated regions affected by reflection， rotation and scaling[C]. 2011 IEEE International Conference on Acoustics，Speech and Signal Processing，2011： 1880-1883.

[7] POPESCU A C， FARID H. Exposing digital forgeries by detecting duplicated image regions[R]. Dartmouth College： TR2004-515， 2004： 1-11.

[8] ZHAO J， GUO J. Passive forensics for copy-move image forgery using a method based on DCT and SVD[J]. Forensic Science International， 2013， 233（1-3）：158-166.

[9] 王俊文，劉光杰，張湛，等. 圖像區(qū)域復(fù)制篡改快速魯棒取證[J]. 自動(dòng)化學(xué)報(bào)， 2009， 35（12）： 1488-1495.

[10] RYU S J，LEE M J， LEE H K. Detection of copy-rotate-move forgery using Zernike moments[C]. International Workshop on Information Hiding， 2010： 51-65.

[11] BAYRAM S，SENCAR H T，MEMON N. An efficient and robust method for detecting copy-move forgery[C]. 2009 IEEE International Conference on Acoustics， Speech and Signal Processing， 2009： 1053-1056.

[12] LI Y. Image copy-move forgery detection based on polar cosine transform and approximate nearest neighbor searching[J]. Forensic Science International， 2013， 224（1-3）： 59-67.

[13] PUN C M， CHUNG J L. A two-stage localization for copy-move forgery detection[J]. Information Sciences， 2018， 463： 33-55.

[14] COZZOLINO D，POGGI G，VERDOLIVA L. Efficient dense-field copy–move forgery detection[J]. IEEE Transactions on Information Forensics and Security， 2015，10（11）： 2284-2297.

[15] BI X， PUN C M. Fast copy-move forgery detection using local bidirectional coherency error refinement[J]. Pattern Recognition， 2018， 81： 161-175.

[16] YAP P T，JIANG X，KOT A C. Two-dimensional polar harmonic transforms for invariant image representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，32（7）： 1259-1270.

[17] KORMAN S，AVIDAN S. Coherency sensitive hashing[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2015， 38（6）： 1099-1112.

[18] CHRISTLEIN V， RIESS C， JORDAN J， et al. An evaluation of popular copy-move forgery detection approaches[J]. IEEE Transactions on Information Forensics and Security， 2012， 7（6）： 1841-1854.

[19] ZANDI M， MAHMOUDI-AZNAVEH A， TALEBPOUR A. Iterative copy-move forgery detection based on a new interest point detector[J]. IEEE Transactions on Information Forensics and Security， 2016， 11（11）： 2499-2512.

（責(zé)任編輯：江 艷）