陳 佳，姬鳳英

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

基于K-D樹的潤(rùn)飾篡改圖像盲鑒別算法

陳 佳1，姬鳳英2

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

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

圖像鑒別；復(fù)制粘貼篡改；K-D樹

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

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

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

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

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

2 基于K-D樹的潤(rùn)飾篡改圖像盲鑒別算法

2.1 圖像的塊配對(duì)（找出用修復(fù)刷修復(fù)過的地方）

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

輸入：待檢測(cè)圖像P；

輸出：若干匹配塊。

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

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

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

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

2.2 篡改區(qū)域定位

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

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

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

輸出：k個(gè)簇，將小簇消除。

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

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

{計(jì)算所有簇的直徑并找出最大直徑簇；

計(jì)算每個(gè)點(diǎn)與其他簇的平均相異度；

將相異度最大的點(diǎn)分出作為新簇；}

Step3. END

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

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

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

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

圖1 算法對(duì)一個(gè)人面部圖像的運(yùn)行結(jié)果

4 結(jié)語

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

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

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

[3]王波.利用成像引入特征的數(shù)字圖像被動(dòng)盲取證研究[D].大連：大連理工大學(xué)，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]曹剛，趙耀，倪蓉蓉.一種基于振鈴效應(yīng)分析的圖像銳化取證算法[J].計(jì)算機(jī)研究與發(fā)展，2009（S1）：217-220.

[6]杜加玉.數(shù)字圖像取證中的模糊與重采樣檢測(cè)研究[D].大連：大連理工大學(xué)，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

國(guó)家檔案局科技計(jì)劃項(xiàng)目；項(xiàng)目編號(hào)：2014-X-68。

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