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

李文龍，高 尚

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮江 212003）

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

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

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

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

1 算法思想和流程

1.1 算法思想

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

奇異值分解定理[8]：設A是m×n實矩陣（不失一般性，設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個奇異值。關于k值如何選取的問題，本文采用的是最高貢獻率原則，其表示如式（2）所示，0<η<1。

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

1.2 算法步驟

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

算法步驟詳細描述如下：

1）對檢測圖像進行DWT離散小波變換：假設待檢測圖像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），則所得圖像子塊總數為（M/2j－b+1）×（N/2j－b+1）。

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

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

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

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

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

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

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

2 實驗結果及分析

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

2.1 灰度圖像檢測結果

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

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

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

2.2 彩色圖像檢測結果

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

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

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

2.3 試驗結果對比

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

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

3 結束語

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

[1]陳利利，王向陽.基于SIFT的橢圓區域魯棒數字水印方案[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]王雯娟，黃振杰，郝艷華.一個高效的基于證書數字簽名方案[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]吳瓊，李國輝，涂丹，等.面向真實性鑒別的數字圖像盲取證技術綜述[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，Farid H.Exposing digital forgeries by detecting duplicated image regions[R].TR2004-515.Dartmouth College，2004.

[6]駱偉祺，黃繼武，丘國平.魯棒的區域復制圖像篡改檢測技術[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的數字圖像水印算法[J].電子科技，2012（10）:128-129，133.CHEN Yang，FANG 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.