基于奇異值優(yōu)化的圖像復制粘貼篡改檢測算法

李文龍，高 尚

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江 212003）

在數(shù)字媒體技術(shù)和計算機技術(shù)迅速發(fā)展的今天，各種圖像處理軟件變得越來越普及，人們可以方便的對圖像進行加工和處理，而且處理后的圖像逼真肉眼難以察覺。倘若這些篡改后的圖像被不法分子加以利用，將造成不可估量的后果和影響。因此，針對檢測數(shù)字圖像真?zhèn)蔚募夹g(shù)研究變得迫在眉睫。

數(shù)字圖像的真?zhèn)舞b別方法可以分為兩類：主動式認證方法和被動式認證方法。在圖像內(nèi)容創(chuàng)建或生成時，通過事先嵌入相關(guān)驗證信息的認證技術(shù)叫做主動認證，主要包括數(shù)字水印技術(shù)[1]和數(shù)字簽名技術(shù)[2]等；通過分析圖像固有屬性或特征的鑒定技術(shù)稱為被動取證。主動認證方法的研究起步早，較成熟，但是存在嚴重的缺陷，如：需要預先嵌入驗證信息、破壞了原來圖像、對攻擊敏感等，從而導致其應用大大的受到限制。而被動取證技術(shù)，又稱盲取證技術(shù)[3]可以在不需要獲得圖像的預處理信息（水印或簽名）的前提下，僅僅利用圖像本身的相關(guān)特性就可以達到認證的目的。這是圖像取證領(lǐng)域的一種新技術(shù)，由于該種技術(shù)目前仍處在初級階段，因此，許多被提出的檢測方法都存在不足之處，需要進一步研究解決的問題還很多。

有很多種圖像篡改方式，如圖像重采樣、JPEG雙壓縮、模糊潤飾等，而本文只針對其中最常見的一種——復制-粘貼篡改。這種篡改方式將圖像中的一部分區(qū)域復制粘貼到同幅圖像的不重疊的另一個區(qū)域?qū)⒃瓉韰^(qū)域覆蓋，以此達到隱藏某目標或新增對象以欺騙他人的目的。最先研究復制-粘貼篡改檢測的是Fridrich等[4]人，他們提出的DCT量化系數(shù)檢測方法把像素點操作轉(zhuǎn)化為圖像塊操作，在很大程度上提高了算法檢測效率，但實際上計算量還是很大；Popescu和Farid等[5]人采用主成分（PCT）分析法僅提取圖像塊的主要特征，進一步的提高了算法檢測效率，但是算法的魯棒性不強；駱偉祺等[6]人提出一種魯棒的檢測算法，雖然有效對抗篡改后處理操作，但同樣檢測時間復雜度高；王俊文等[7]提出一種基于幾何不變矩特征的檢測算法，通過提取圖像塊幾何不變矩特征實現(xiàn)篡改檢測，具有較好的魯棒性，但檢測效率仍有待提高。

為了進一步減少計算量，提高檢測效率，本文提出了基于改進后的奇異值分解的圖像復制粘貼篡改檢測算法。該算法利用奇異值的自身特性對其進行優(yōu)化，在不影響檢測效果的前提下，降低特征向量的維數(shù)，達到提高檢測效率的目的。此外，本算法在確定篡改區(qū)域時加入特征向量相似度判別的操作，以使得檢測結(jié)果更準確。

1 算法思想和流程

1.1 算法思想

本文的算法以離散小波變換和奇異值分解為基礎(chǔ)，首先對待檢測圖像進行DWT離散小波變換，提取圖像低頻分量，縮小圖像尺寸。然后對圖像進行滑窗分塊操作，使用奇異值分解方法來提取圖像塊特征向量。

奇異值分解定理[8]：設(shè)A是m×n實矩陣（不失一般性，設(shè)m≥n），則存在m階正交矩陣U，n階正交矩陣V，使得

其中，Λ 為對角矩陣，Λ=diag（λ1，λ2，…，λr，0，…，0），滿足λ1≥λ2≥…≥λr＞0，r是矩陣 A 的秩，λi（i=1，…，r）為矩陣 A 的奇異值，式（1）叫做矩陣的奇異值分解。奇異值特征矢量中前幾個值比較大，它們包含了矩陣A的大部分信息。因此，在實際應用中可以舍棄后面一些不重要的奇異值，以降低計算量。

矩陣A的秩為r，則其存在r個不為零的奇異值。按從大到小的順序，我們將其分為前面k個和后面r－k個奇異值。由于后r－k個奇異值較小，只包含少量信息，而前面k個奇異值大，包含了大部分信息，因此前面k個奇異值起主要作用，故可以忽略后面r－k個奇異值。關(guān)于k值如何選取的問題，本文采用的是最高貢獻率原則，其表示如式（2）所示，0<η<1。

在奇異值分解后，對得到的特征矩陣進行字典排序。以往算法直接默認經(jīng)字典排序后特征矩陣中相鄰的兩個向量是滿足相似度匹配條件的，但在實際情況中，由于有些圖像存在大量紋理相近或者光滑均勻的區(qū)域，比如天空、海洋、草地等，如果僅僅依靠字典排序的方式判別向量相似性會產(chǎn)生許多誤差。因此，本文算法在對特征矩陣遍歷時，同時比較相鄰兩特征向量的相似度和圖像塊對的位移距離，只有同時滿足向量相似度條件和位移閾值條件的圖像塊，才被認為是可疑的篡改塊。最后，對可疑篡改區(qū)域進行面積閾值判別并用數(shù)學形態(tài)學方法進行后處理，去除孤立點，得出最終篡改區(qū)域。

1.2 算法步驟

本文算法檢測流程如圖1所示。

算法步驟詳細描述如下：

1）對檢測圖像進行DWT離散小波變換：假設(shè)待檢測圖像I的大小為M×N，對圖像進行j級DWT變換，本文選取的是最簡單的haar小波進行實驗，然后提取變換后圖像的低頻分量 LL，其大小為（M/2j）×（N/2j）。

圖1 檢測算法流程圖Fig.1 Process of detection algorithm

2）對低頻分量LL進行滑窗分塊：用b×b大小的窗口模塊在尺寸為（M/2j）×（N/2j）的圖像低頻分量上滑動來提取圖像子塊。每次滑動一個像素，滑動順序是從左往右、從上往下的，提取出的圖像重疊子塊 Ai，i=1，2， …，（M/2j－b+1）×（N/2j－b+1），則所得圖像子塊總數(shù)為（M/2j－b+1）×（N/2j－b+1）。

3）使用改進后的奇異值分解方法對圖像子塊進行特征值提?。菏紫葘D像子塊進行奇異值分解，得到每個子塊的奇異值特征向量，所有奇異值特征向量組成特征矩陣Y，如式（3）所示。Y矩陣的每一行對應著一個圖像子塊的奇異值特征向量y→i=（λ1，λ2，…，λr，0，…，0），Y 的行數(shù)為圖像子塊的個數(shù) p，p=（M/2j－b+1）×（N/2j－b+1）。

接著用改進的奇異值分解方法對矩陣Y進行優(yōu)化，并通過設(shè)定最高貢獻率閾值θ，來確定k的取值，最后得到新的特征矩陣Sp×k，如式（4）所示。運用改進的奇異值分解方法對圖像塊進行處理之后，特征空間在原來基礎(chǔ)上進一步下降到k維，提高了檢測速度

4）特征矩陣字典排序：對特征矩陣Sp×k按行進行字典排序，得到排序后的特征矩陣為其中一行，為對應圖像塊的左上角坐標，用于表示圖像塊的位置。

5）遍歷Qp×k，對其中相鄰的兩行向量，判別其相似度。相似度SM計算公式如式（5）：

v，u表示Qp×k矩陣中相鄰的兩行向量，如果滿足SM≦ρ，則進一步判斷其位移距離是否滿足閾值條件。位移距離閾值一般要求滿足下式（6）：

當同時滿足SM≦ρ和L≧LT兩個條件時，標記對應的圖像塊。若存在這種圖像塊，則表明檢測圖像中存在潛在的復制粘貼篡改區(qū)域，進入下一步，否則算法結(jié)束。

6）根據(jù)篡改面積閾值ST確定最終的篡改區(qū)域，ST一般不小于檢測圖像面積的0.85%。最后，利用數(shù)學形態(tài)學中的膨脹，腐蝕操作對檢測結(jié)果進行后處理，去除噪聲引起的孤立點，得到最終檢測結(jié)果。

2 實驗結(jié)果及分析

為了驗證本文算法的有效性，分別對灰度圖像和彩色圖像進行了復制粘貼篡改區(qū)域的檢測。根據(jù)經(jīng)驗值和相關(guān)測試，本文選取的是最簡單的一級haar小波變換，滑窗塊大小為8×8，最大貢獻率閾值θ為0.95，向量相似度閾值ρ取0.06，位移距離閾值LT取16。對算法檢測結(jié)果進行了數(shù)學形態(tài)學方法處理，如腐蝕、膨脹操作，去除噪聲帶來的孤立點。

2.1 灰度圖像檢測結(jié)果

實驗用圖均來自互聯(lián)網(wǎng)并通過photoshop進行復制粘貼篡改操作。實驗結(jié)果如圖2所示：（a）是原灰度圖像，（b）是經(jīng)過復制粘貼篡改后的偽造圖，圖中將薯片又復制了一個在左邊，（c）是使用本文檢測算法的檢測結(jié)果圖。

實驗結(jié)果表明，本文算法能有效檢測針對灰度圖像的復制粘貼篡改。對于多處篡改的情況，本文算法也能有效檢測，在此不再舉例。

圖2 灰度圖像檢測結(jié)果Fig.2 Detection results of gray-level images

2.2 彩色圖像檢測結(jié)果

對于彩色圖像的檢測，本文選擇先將彩色圖像轉(zhuǎn)化為灰度圖像后再對其進行檢測。試驗結(jié)果如圖3所示：（a）是原始圖像，（b）是篡改圖像，把后面的小球被復制了兩個在草地上，前面的小球被草地覆蓋了，（c）是檢測結(jié)果圖。

結(jié)果表明，算法對彩色圖像的復制粘貼篡改也有效。

圖3 彩色圖像檢測結(jié)果Fig.3 Detection results of color images

2.3 試驗結(jié)果對比

以512×512大小的圖為例，相比于文獻[4]的64維特征向量和文獻[5]的32維特征向量，本文提出算法的特征向量只有8維，并且圖像子塊的個數(shù)也只有前二者的1/4，相當大程度上減少了計算量，提高了檢測效率。更直觀的對比結(jié)果見表1。

表1 本文算法與文獻[4，5]算法的比較結(jié)果Tab.1 Comparison results of referenced approaches of[4，5]with proposed approach

3 結(jié)束語

在數(shù)字圖像取證研究領(lǐng)域中，本文針對最常見的復制-粘貼篡改進行了研究，提出了一種基于離散小波變換（DWT）[9]和改進的奇異值分解的篡改檢測算法。該算法首先對檢測圖像進行離散小波變換，然后對圖像的低頻分量進行滑窗分塊，再對每個圖像塊進行奇異值分解，并對所得的奇異值特征向量進一步的優(yōu)化，以降低向量維度。接著對所得奇異值特征向量進行字典排序，遍歷特征矩陣通過向量相似度匹配和位移距離判別初步定位篡改區(qū)域，最后通過面積閾值比較和去孤立點確定最終篡改區(qū)域。實驗證明，本文算法檢測準確度良好，同時有效的減少了檢測消耗時間，提高了檢測效率。

[1]陳利利，王向陽.基于SIFT的橢圓區(qū)域魯棒數(shù)字水印方案[J]. 計算機工程與應用，2012，48（1）：98-101.CHEN Li-li，WANG Xiang-yang.Robust watermark scheme using SIFT in ellipse region[J].Computer Engineering and Applications，2012，48（1）:98-101.

[2]王雯娟，黃振杰，郝艷華.一個高效的基于證書數(shù)字簽名方案[J].計算機工程與應用，2011，47（6）:89-92.WANG Wen-juan，HUANG Zhen-jie，HAO Yan-hua.Efficient certificate-based signature scheme[J].Computer Engineering and Applications，2011，47（6）:89-92.

[3]吳瓊，李國輝，涂丹，等.面向真實性鑒別的數(shù)字圖像盲取證技術(shù)綜述[J].自動化學報，2008，34（12）：1458-1466.WU Qiong，LI Guo-hui，TU Dan，et al.A survey of blind digital image forensies technology for authentieity deteetion[J].Acta Automatica Sinica，2008，34（12）:1458-1466.

[4]Fridrich J，Soukal D，Luk J.Detection of copy move forgery indigital images[C]//Proc.Digital Forensic Research Workshop.August，2003:19-23.

[5]Popescu A C，F(xiàn)arid H.Exposing digital forgeries by detecting duplicated image regions[R].TR2004-515.Dartmouth College，2004.

[6]駱偉祺，黃繼武，丘國平.魯棒的區(qū)域復制圖像篡改檢測技術(shù)[J].計算機學報，2007，30（11）：1998-2007.LUO Wei-qi，HU Ji-wu，QIU Guo-ping.Robust detection of region-duplication forgery in digital image[J].Chinese Journal of Computers，2007，30（11）:1998-2007.

[7]王俊文，劉光杰，戴躍偉，等.一種檢測圖像Copy－Move篡改魯棒算法[J].模式識別與人工智能，2009，22（4）:630－634.WANG Jun-wen，LIU Guang-jie，DAIYue-wei，etal.A robust algorithm for detecting image copy-move forgery[J].Pattern Recognition and Artificial Intelligence，2009，22（4）:630-634.

[8]Ientilucci E J.Using the Singular Value Decomposition.Chester F.Carlson Center for Imaging Science，Rochester Institute of Technology，2003.

[9]陳楊，方寶磊，張小華.基于圖像置亂和ICA-DWT的數(shù)字圖像水印算法[J].電子科技，2012（10）:128-129，133.CHEN Yang，F(xiàn)ANG Bao-lei，ZHANG Xiao-hua.Digital image watermarking algorithm based on image scrambling and ICA-DWT[J].Electronic Science and Technology，2012（10）:128-129，133.