基于SIFT與K-means的圖像復(fù)制粘貼篡改檢測

葉雨晴，邱曉暉

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

近年來，隨著圖像處理軟件的日益普及，人們可以輕而易舉地對一幅數(shù)字圖像進(jìn)行隨意修改。一些不法分子通過偽造、篡改圖像實現(xiàn)非法目的，不但影響到版權(quán)保護(hù)，而且給新聞報道、商業(yè)宣傳、法庭取證的真實性和可靠性都帶來了前所未有的挑戰(zhàn)。在這種背景下，圖像篡改檢測技術(shù)應(yīng)運(yùn)而生。圖像篡改方式多種多樣，其中復(fù)制粘貼是一種較常見、較隱蔽的篡改方式。圖像復(fù)制粘貼即選擇圖像的一個或多個區(qū)域，在進(jìn)行旋轉(zhuǎn)、縮放、光照變換等操作后復(fù)制粘貼到同幅圖像[1]，以達(dá)到增加或掩蓋目標(biāo)的目的。

目前，針對復(fù)制-粘貼篡改的盲檢測主要分為兩種方法:

(1)基于塊匹配的圖像盲檢測方法。該方法是通過對圖像進(jìn)行分塊，計算每個塊的不變特征向量，并在此基礎(chǔ)上對特征向量通過字典排序等方法進(jìn)行相似塊匹配。Fridrich等[2]利用量化DCT系數(shù)作為圖像特征；Popescu等[3]采用PCA表征圖像塊，進(jìn)一步提高了算法檢測效率，但算法的魯棒性不強(qiáng)；Li等[4]通過小波變換提取圖像的低頻子帶分量。該類基于塊匹配的算法對平滑區(qū)域的篡改圖像檢測率較高，但對于經(jīng)過旋轉(zhuǎn)、縮放等操作的篡改圖像魯棒性較差。

(2)基于特征點匹配的圖像盲檢測方法。該方法是通過搜索圖像的局部角點或極值點并在去除錯誤特征點后進(jìn)行圖像匹配。該類方法包括Harris角點檢測[5]、基于SIFT[6]、SURF[7]算法、ORB算法[8]等，這類算法在處理圖像之間發(fā)生平移、旋轉(zhuǎn)、仿射變換情況下的匹配問題上具有良好的檢測效果[9]。其中SIFT算法提取的特征點比較穩(wěn)定,具有抗光照和抗幾何形變的能力，但是該算法仍存在一些不足，比如特征描述符的維數(shù)過大以及耗時過長。

針對圖像復(fù)制粘貼篡改操作，以圖像特征點匹配為切入點，對傳統(tǒng)SIFT算法特征向量維數(shù)過高的缺點，對SIFT算法進(jìn)行改進(jìn)。

1 SIFT算法簡介

尺度不變特征變換(scale-invariant feature transform，SIFT)是一種在尺度空間尋找極值點，并提取其位置、尺度、旋轉(zhuǎn)不變量的算法。SIFT特征提取需要以下幾個步驟:

(1)尺度空間的構(gòu)建。

通過構(gòu)建尺度空間，可以模擬數(shù)字圖像多尺度特性。一幅圖像尺度空間L(x,y,σ)的定義如下:

L(x,y,σ)=G(x,y,σ)*I(x,y)

(1)

其中，(x,y)表示圖像中每個像素的位置；σ表示尺度空間大小因子；G(x,y,σ)為高斯卷積核:

(2)

(2)尺度可變高斯函數(shù)的表示。

為了在尺度空間中有效地檢測穩(wěn)定的關(guān)鍵點，將相鄰兩尺度空間函數(shù)相減構(gòu)造高斯差分函數(shù)(DOG)金字塔模型。DOG算子如下：

D(x,y,σ)=L(x,y,Kσ)-L(x,y,σ)

(3)

其中，L(x,y,σ)表示尺度為σ的尺度空間；L(x,y,Kσ)表示尺度為Kσ的尺度空間。

(3)計算關(guān)鍵點。

DOG尺度空間極值點即為SIFT算法特征點。圖1所示為DOG尺度空間3個相鄰尺度。每個檢測點與鄰域8個相鄰點以及上下相鄰尺度9×2個點共26個點同時進(jìn)行比較，以確保在尺度空間和二維圖像空間內(nèi)所檢測內(nèi)容為局部極值。

(4)關(guān)鍵點的精確定位。

由于DOG值對噪聲和邊緣敏感，因此要剔除低對比度點和邊緣點。通過對DOG函數(shù)的二階泰勒展開式求導(dǎo)精確定位極值點并求出極值D(X)，同時利用極值點處Hessian矩陣的性質(zhì)去除邊緣點，以增強(qiáng)匹配穩(wěn)定性、提高抗噪聲能力。

(4)

(5)特征主方向的提取與描述子的生成。

為使描述符具有旋轉(zhuǎn)不變性，根據(jù)局部特征為每個關(guān)鍵點分配一個基準(zhǔn)方向[10]。SIFT中使用梯度直方圖的方法求取局部結(jié)構(gòu)的穩(wěn)定方向。在特征描述上，Lowe建議描述子為關(guān)鍵點鄰域尺度空間內(nèi)4×4的窗口中計算每個窗口內(nèi)的8個方向的梯度信息，生成128(4×4×8)維向量表征。

2 基于改進(jìn)SIFT算法的圖像復(fù)制粘貼篡改檢測

由于SIFT關(guān)鍵點特征向量具有很高的維度，導(dǎo)致其時間復(fù)雜度較高。PCA-SIFT[11]作為其改進(jìn)算法，使用更加精簡的方法構(gòu)建特征點描述向量，利用圖像特征主要成分來實現(xiàn)降低維數(shù)的目的，但由于PCA采用線性降維的方法，未考慮描述子各局部特征的非線性關(guān)系，使得對部分局部關(guān)鍵信息表述不夠完整。而K-means聚類算法是一種既可以用于線性，也可以用于非線性的聚類方法[12]，基于此，文中算法采用K-means聚類的思想對SIFT算法進(jìn)行改進(jìn)。

2.1 利用K-means對SIFT特征向量降維

對比PCA-SIFT的優(yōu)劣情況，采用基于K-means聚類的方式對SIFT 算法進(jìn)行降維。通過對SIFT生成的特征向量矩陣的列向量進(jìn)行聚類，并提取與SIFT特征矩陣整體差異度最小的一類特征向量進(jìn)行匹配，進(jìn)而完成對SIFT特征向量的降維。該類特征向量，最大保持了原有特征點的成分，并且相比于PCA-SIFT算法只能夠線性降維[13]。文中算法考慮了局部特征的非線性關(guān)系，不僅對平移操作檢測效果好，而且對于進(jìn)行縮放、旋轉(zhuǎn)操作的復(fù)制粘貼篡改圖像的檢測同樣具有很高的魯棒性。

2.1.1 K-means聚類算法

K-means算法能夠以較低維度表示高維度數(shù)據(jù)的局部信息[14]。其原理是將給定的n個數(shù)據(jù)點的數(shù)據(jù)集X分為k類，在不斷地循環(huán)迭代中使其目標(biāo)函數(shù)達(dá)到最小，從而使同一類內(nèi)的數(shù)據(jù)差異性小，不同類之間的數(shù)據(jù)具有一定的分離性[15]。

2.1.2 基于K-means的改進(jìn)SIFT算法

K-means初始聚類中心的選取直接影響聚類的結(jié)果[16]。文中通過計算得到平均差異度最小的SIFT特征矩陣列向量，即與特征矩陣差異最小的列向量作為初始聚類中心c1。聚類完成后，劃分到c1所在類的特征矩陣與整體差異最小、最相似。提取該類的特征向量進(jìn)行匹配，不僅最大保持了原有特征向量的成分，而且大大降低了特征向量的維數(shù)。

平均差異度di的定義如下：

(5)

(6)

其中，設(shè)SIFT關(guān)鍵點個數(shù)為m，xi,xj為兩個m維SIFT特征矩陣列向量；dij為xi,xj的距離；N為列向量的總數(shù)。平均差異度越小，樣本與整體越相似。

假設(shè)SIFT算法提取到的特征點個數(shù)為m，則得到的特征向量矩陣T的大小為m×128?；贙-means的改進(jìn)SIFT算法具體步驟如下：

(1)選取k個初始聚類中心c1,c2,…,ck。首先計算特征矩陣T列向量兩兩之間的距離dij，然后計算平均差異度di最小的列向量，作為第一個初始聚類中心c1；選取距離c1最遠(yuǎn)的點作為第二個中心點c2，選取距離c1和c2最遠(yuǎn)的點，作為c3，依次計算中心點c4,c5,…,ck。

(2)對特征向量矩陣T中的每個列向量xi，計算其與各個聚類中心ck的歐氏距離并將其歸為距離最小的類。

(3)根據(jù)式7求得各聚類中心數(shù)據(jù)的平均值進(jìn)而更新聚類中心ck。

狀態(tài)監(jiān)測系統(tǒng)提供豐富直觀的、可組態(tài)的多個監(jiān)測畫面，從不同的角度、分層次展現(xiàn)機(jī)組的狀態(tài)信息。監(jiān)測畫面中將各種監(jiān)測狀態(tài)以圖表、圖形、數(shù)據(jù)等形式展示出來。

(4)重復(fù)步驟2和步驟3，直到聚類中心基本穩(wěn)定或迭代次數(shù)達(dá)到上限結(jié)束。

2.2 基于改進(jìn)SIFT算法的圖像復(fù)制粘貼篡改檢測步驟

(1)讀取待檢測圖像I，利用SIFT算法提取圖像的關(guān)鍵點，生成關(guān)鍵點的128維SIFT特征向量。

(2)利用改進(jìn)的K-means算法對特征向量矩陣T的128維列向量進(jìn)行聚類，將列向量分為k類。

(3)對劃分到第一類的t維特征向量進(jìn)行特征匹配，定位復(fù)制粘貼區(qū)域并用線標(biāo)出。特征匹配的具體步驟如下：

首先計算特征向量間的歐氏距離，其次在篡改圖像中遍歷每個關(guān)鍵點以找出與這個關(guān)鍵點歐氏距離最近和次近的兩個關(guān)鍵點。如果滿足式7,就認(rèn)為是一對復(fù)制粘貼匹配點，最終確定篡改區(qū)域。

(7)

其中，Dnearest為最近歐氏距離；Dhpyo-nearest為次近歐氏距離。

算法流程如圖2所示。

圖2 基于K-means的改進(jìn)SIFT算法流程

3 實驗結(jié)果分析

實驗中PC配置為CPU 3.20 GHz，內(nèi)存4 G，仿真平臺為MATLAB R2016a。為了驗證該算法對篡改檢測性能的影響，設(shè)計了一系列實驗，對平移、旋轉(zhuǎn)、縮放等不同后處理下的圖像分別采用經(jīng)典的SIFT、PCA-SIFT算法以及提出的基于K-means的改進(jìn)SIFT算法進(jìn)行仿真，然后從匹配的正確率和匹配點數(shù)以及檢測時間上進(jìn)行比較。仿真結(jié)果如圖3所示。

圖3 仿真結(jié)果

從表1～3可以得出以下結(jié)論：

(1)正確率：無論是PCA-SIFT算法還是文中算法都繼承了SIFT算法對于尺度變換和旋轉(zhuǎn)的魯棒性。

(2)匹配精確度：由于PCA是一種線性降維方法，對于具有線性特征分布的特征點能夠起到很好的降維作用，如圖(c)，能夠保留足夠的特征點用于復(fù)制粘貼區(qū)域的匹配，但對于非線性分布的特征點，該算法無法保留足夠的特征點，如圖(g)、(k)，很多特征點被去除，匹配精度很低。而文中算法，在保證匹配點數(shù)的同時，提高了檢測效率。

表1 平移操作下的各類算法檢測結(jié)果對比

表2 旋轉(zhuǎn)操作下的各類算法檢測結(jié)果對比

表3 縮放操作下的各類算法檢測結(jié)果對比

4 結(jié)束語

基于SIFT算法，將K-means算法用于SIFT特征向量的降維，節(jié)約了圖像復(fù)制粘貼篡改檢測過程中特征匹配的時間。實驗結(jié)果表明，利用該算法進(jìn)行圖像復(fù)制粘貼篡改檢測，既保持了傳統(tǒng)SIFT算法的穩(wěn)定性和精確性的優(yōu)點，又比SIFT算法以及PCA-SIFT算法具有更高的檢測效率。

參考文獻(xiàn):

[1] 柴新新,邱曉暉.基于提升小波變換的圖像篡改檢測算法[J].計算機(jī)技術(shù)與發(fā)展,2016,26(4):78-81.

[2] FRIDRICH J,SOUKAL D,LUKJ.Detection of copy-move forgery in digital images[C]//Proceedings of digital forensic research workshop.Cleveland:IEEE,2003:55-61.

[3] POPESCU A C,FARID H.Exposing digital forgeries by detecting traces of resampling[J].IEEE Transactions on Signal Processing,2005,53(2):758-767.

[4] LI Weihai,YUAN Yuan, YU Nenghai. Passive detection of doctored JPEG image via block artifact grid extraction[J].Signal Processing,2009,89(9):1821-1829.

[5] HARRIS C G,STEPHENS M J.A combined corner and edge detector[C]//Proceedings of alvey vision conference.[s.l.]:[s.n.],1988:147-151.

[6] LOWE D G.Distinctive image features from scale-invariant key-points[J]．International Journal of Computer Vision,2004,60(2):91-110.

[7] BAY H,TUYTELAARS T,GOOL L V.SURF:speeded up robust features[C]//Proceedings of the 9th European conference on computer vision.Graz,Austria:Springer-Verlag,2006:404-417.

[8] RUBLEE E,RABAUD V,KONOLIGE K,et al.ORB:an efficient alternative to SIFT or SURF[C]//Proceedings of the 2011 international conference on computer vision.[s.l.]:IEEE,2011:2564-2571.

[9] 林 晶,黃添強(qiáng),林玲鵬,等.采用局部強(qiáng)度順序模式的圖像復(fù)制—粘貼篡改檢測算法[J].通信學(xué)報,2016,37:132-139.

[10] 何林遠(yuǎn),畢篤彥,馬時平,等.基于SIFT和MSE的局部聚集特征描述新算法[J].電子學(xué)報,2014,42(8):1619-1623.

[11] LUO Juan,GWUN O.A comparison of SIFT,PCA-SIFT and SURF[J].International Journal of Image Processing,2009,3(4):143-152.

[12] 張寧麗,馬 燕,李順寶,等.FKPCA-SIFT算法在圖像匹配中的應(yīng)用[J].電視技術(shù),2015,39(7):21-24.

[13] 李 翠,馮冬青.基于改進(jìn)K-均值聚類的圖像分割算法研究[J]．鄭州大學(xué)學(xué)報:理學(xué)版,2011,43(1):109-113．

[14] 朱 葉,申鉉京,陳海鵬.基于混合灰度序模式的圖像復(fù)制-粘貼篡改盲鑒別算法[J].吉林大學(xué)學(xué)報:工學(xué)版,2017,47(4):1280-1285.

[15] 李昆侖,孫 碩.基于改進(jìn)SIFT算法的圖像復(fù)制粘貼篡改檢測[J].計算機(jī)科學(xué),2016,43(6A):179-183.

[16] 杜振龍,楊 凡,李曉麗,等.利用SIFT特征的非對稱匹配圖像拼接盲檢測[J].中國圖象圖形學(xué)報,2013,18(4):442-449.