基于K-D樹的潤飾篡改圖像盲鑒別算法

陳 佳，姬鳳英

（1.武漢紡織大學 數(shù)學與計算機學院，湖北 武漢 430073；2.湖北省檔案局，湖北 武漢 430071）

基于K-D樹的潤飾篡改圖像盲鑒別算法

陳 佳1，姬鳳英2

（1.武漢紡織大學 數(shù)學與計算機學院，湖北 武漢 430073；2.湖北省檔案局，湖北 武漢 430071）

文章針對修復刷的潤飾原理提出了基于K-D樹的修復刷篡改圖像盲鑒別算法，當修復刷被應用于圖像時，采用K-D樹以及層次聚類算法精確識別圖像是否經(jīng)過篡改，并找出篡改位置。實驗表明，準確度高。

圖像鑒別；復制粘貼篡改；K-D樹

檔案資料的保存形式由紙介保存發(fā)展到電子化保存是科技發(fā)展的必然，“數(shù)字檔案館”的概念由此而生，其中，圖像檔案是數(shù)字化檔案很重要的一個組成部分，包括由數(shù)碼技術轉換的照片、圖形、圖片、攝像、圖表等。同時，隨著信息技術的高速發(fā)展，各種數(shù)字圖像編輯軟件使得圖像處理更為便捷，很多軟件采用了各種信息處理技術，比如修復刷等，通過這些技術對圖像進行潤飾或者改變。改變后的圖像往往從肉眼上很難看出痕跡，甚至專家也不能鑒別真?zhèn)?，但實際應用中卻需要原始圖像，因此需要對圖像的內(nèi)容進行真?zhèn)舞b別。目前很多軟件采用的潤飾方法不難被檢測到其修改的區(qū)域，比如康麗[1]直接復制從而組成圖像的某部分，陳海鵬等[2]利用光照不一致現(xiàn)象檢測復制部分，王波[3]利用的顏色不一致現(xiàn)象以及Cui等[4]和曹剛等[5]所針對的銳化操作。在各種技術中，修復刷能夠在圖像的邊界處平穩(wěn)過渡，保持了各像素點的特征，因而顏色和源區(qū)域具備穩(wěn)健性。

本文針對修復刷的潤飾原理提出了基于K-D樹的修復刷篡改圖像盲鑒別算法，當修復刷應用于圖像時，圖像的像素會發(fā)生改變，利用其存在的精確的衍生信息來識別圖像的潤飾修改，如果圖像的大區(qū)域被修改，該方法則以高壓縮率工作，基于這種思想，人們可以用K-D樹的修復刷篡改圖像盲鑒別算法進行鑒別。

1 國內(nèi)外研究現(xiàn)狀

保證檔案的原始性、真實性是檔案管理的核心部分，只有這樣才能保證其權威性從而被社會廣泛利用。目前，在信息化社會中，數(shù)字檔案同樣需要具備這樣的特性。因此，在數(shù)字化檔案開發(fā)和利用中，如何對數(shù)字檔案進行真?zhèn)巫R別，以及如何保護數(shù)字化檔案的版權和對其進行原始性鑒別，都是開發(fā)和使用中至關重要的步驟。而隨著信息化技術的高速發(fā)展，圖像處理技術的日益改進，很多圖像處理軟件，如Photoshop等，很容易對數(shù)字圖像進行修改和編輯。在帶來各種益處的同時，很多不法分子也利用這些技術對數(shù)字檔案、司法證據(jù)等大量制造偽造圖像。因此，國內(nèi)外研究學者對其進行大量研究。

著名的Dartmouth學院、Binghamton大學、Columbia大學和Polytechnic大學等都成立了專門的數(shù)字媒體取證研究小組。美國Dartmouth大學的Hany Farid教授領導的科研隊伍用對圖像進行多尺度小波分解和高階統(tǒng)計建模的方法進行分析，對數(shù)碼照片圖像、掃描圖像和計算機生成圖像進行盲檢測。這種小波分析方法利用不同來源的數(shù)字圖像上的各種不一致性進行圖像的真?zhèn)舞b別，開啟了這種不一致性鑒別技術的探索之路，也成了檔案圖像鑒別技術的主流和主要研究方向。然而，這種方法缺乏實際應用，主要還處在理論基礎階段，需要建立完備的技術路線。在檔案圖像的眾多篡改技術中，修復刷技術最具隱蔽性，其能夠在圖像邊緣處平穩(wěn)過渡，因此很難從圖像的結構信息以及顏色的跳躍來進行判斷，一般情況下很難辨別，但是由于被修護的圖層和本身的圖層色數(shù)有一定的差距，基于這種思想，本文提出了改進的檢測算法—基于K-D樹的潤飾篡改圖像盲鑒別算法。

2 基于K-D樹的潤飾篡改圖像盲鑒別算法

2.1 圖像的塊配對（找出用修復刷修復過的地方）

首先，對待檢測的圖像，要確定是否使用過修復刷，也就是找出修復刷使用過的位置。具體算法如下所示。

輸入：待檢測圖像P；

輸出：若干匹配塊。

第1步，將待檢測圖像P分成若干個小塊p1，p2，…，pn，其中每塊大小為N×N；

第2步，依次將p1，p2，…，pn的像素塊插入到K-D樹中；

第3步，采用廣度遍歷方法在K-D樹中查找具有近似值小塊。

該算法首先要確定所劃分小塊的大小，如果劃得太大或太小，都不能準確計算使用過修復刷的區(qū)域值。經(jīng)過實驗，確定N值的取值范圍為[10,20]的像素之間。另外，該算法所涉及的一個重要參數(shù)即匹配的設定值FMAX，太大或太小都找不到正確的匹配對。同樣，這里采用實驗法。實驗發(fā)現(xiàn)，對于非壓縮圖像和壓縮圖像，該值取值不同，主要是由于修復刷所采用的過濾器對壓縮圖像的像素值產(chǎn)生了噪聲。因此，對于非壓縮圖像，F(xiàn)MAX可以為較低值或者較高值，而對于壓縮圖像，F(xiàn)MAX需為較大值。對于所采用的數(shù)字檔案圖像，其值設定為6—10。

2.2 篡改區(qū)域定位

通過相似值找到的匹配塊對中，由于有的區(qū)域被修復刷修飾過，造成源區(qū)域與鄰近區(qū)域其他塊誤匹配。因此在得到匹配對后，還需要進行誤匹配消除，再精確定位篡改區(qū)域。

本文采用分裂的層次聚類的方法對這些匹配塊進行聚類，通過得到的類的大小來判斷所包含的匹配塊是否為誤匹配塊。這里將所需匹配的匹配塊p1，p2，…，pn作為輸入向量[n1,n2,…,nn]，算法描述如下所示。

輸入：向量[n1,n2,…,nn]；

輸出：k個簇，將小簇消除。

Step1. 將輸入的向量[n1,n2,…,nn]看作一個初始簇；

Step2. For(i=1;i!=k;i++)

{計算所有簇的直徑并找出最大直徑簇；

計算每個點與其他簇的平均相異度；

將相異度最大的點分出作為新簇；}

Step3. END

對于此算法，首先要考慮參數(shù)k的大小，即分為幾個簇合適。實驗表明，k的大小隨輸入向量大小的變動而變動，但當簇中的向量數(shù)（即匹配塊數(shù)）小于某個值時，即可停止分裂，并認為該小簇中的匹配對是誤匹配對。通過實驗發(fā)現(xiàn)，當簇中的匹配塊個數(shù)為6—10時，即可認為該簇為小簇并確定該簇中的塊為誤匹配塊。

刪除誤匹配區(qū)域后，就需要確定篡改的區(qū)域。實際上，對于修復刷操作的篡改，雖然圖像邊界能夠平穩(wěn)過渡，但會使得相鄰區(qū)域之間的梯度長度具有強相關性，因此，將區(qū)域矩陣和其相鄰的矩陣做差值得到絕對值矩陣，該絕對值矩陣會有多個相鄰的零。換句話說，當存在多個差值的零分量連通集合時，這些塊即為篡改塊。通過實驗發(fā)現(xiàn)，當該集合大小大于3時，該塊為篡改塊。

3 實驗結果

本文采用的數(shù)據(jù)集為人的臉部皮膚，該數(shù)據(jù)集通過修復刷進行修飾，并采用K-D樹算法進行檢測。算法運行了一個大小為15的塊，用至少5個相同轉換的塊對尋找區(qū)域?qū)Α嶒灲Y果顯示，修復刷應用的大部分區(qū)域被檢測并且沒有誤報。在這兩種情況下，表面看著真實性的圖像有許多被潤色的區(qū)域。如圖1所示，這些初步的實驗表明了該方法對檢測修復刷的使用是有效的。圖1（a）為圖像未處理前，圖1（b）是圖像是處理后，圖1（c）是應用K-D樹查找的經(jīng)過修復后的內(nèi)容。

圖1 算法對一個人面部圖像的運行結果

4 結語

本文針對修復刷篡改問題，采用K-D樹及層次聚類法定位法，精確定位被篡改的區(qū)域，相對傳統(tǒng)算法提高了準確性。通過實驗證明，該方法對壓縮圖像和非壓縮圖像都能有效地找出即使邊界平穩(wěn)過渡的篡改區(qū)域，對我國的數(shù)字檔案的真?zhèn)巫R別有一定貢獻。

[1]康麗.數(shù)字圖像內(nèi)容人為篡改檢測[D].重慶：西南大學，2011.

[2]陳海鵬，申鉉京，呂穎達，等.基于Lambert光照模型的圖像真?zhèn)蚊よb別算法[J].計算機研究與發(fā)展，2011（7）：1237-1245.

[3]王波.利用成像引入特征的數(shù)字圖像被動盲取證研究[D].大連：大連理工大學，2010.

[4]GUI Z，LIU Y.An image sharpening algorithm based on fuzzy logic[J].Optik-International Journal for Light and Electron Optics，2011（8）：697-702.

[5]曹剛，趙耀，倪蓉蓉.一種基于振鈴效應分析的圖像銳化取證算法[J].計算機研究與發(fā)展，2009（S1）：217-220.

[6]杜加玉.數(shù)字圖像取證中的模糊與重采樣檢測研究[D].大連：大連理工大學，2010.

Blind identification for image authenticity based on K-D tree

Chen Jia1, Ji Fengying2
(1.Mathematics and Computer Science School, Wuhan Textile University, Wuhan 430073, China;2.Hubei Provincial Archives Bureau, Wuhan 430071, China)

In view of the retouch principle of repair brush, this paper proposes image blind identification algorithm of brush tamper based on K-D tree, which uses K-D tree and hierarchical clustering algorithm to accurately identify whether the image has been tampered with,and find out the tampering position. Experiments show that the accuracy is high.

identification for image authenticity; copy-move forgery; K-D tree

國家檔案局科技計劃項目；項目編號：2014-X-68。

陳佳（1982— ），女，湖北武漢人，副教授，博士；研究方向：圖像處理與模式識別。