葉雨晴，邱曉暉

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

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

1 SIFT算法簡介

尺度不變特征變換(scale-invariant feature transform，SIFT)是一種在尺度空間尋找極值點(diǎn)，并提取其位置、尺度、旋轉(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)鍵點(diǎ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)鍵點(diǎn)。

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

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

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

(4)

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

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

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

由于SIFT關(guān)鍵點(diǎn)特征向量具有很高的維度，導(dǎo)致其時間復(fù)雜度較高。PCA-SIFT[11]作為其改進(jìn)算法，使用更加精簡的方法構(gòu)建特征點(diǎn)描述向量，利用圖像特征主要成分來實現(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特征向量的降維。該類特征向量，最大保持了原有特征點(diǎn)的成分，并且相比于PCA-SIFT算法只能夠線性降維[13]。文中算法考慮了局部特征的非線性關(guān)系，不僅對平移操作檢測效果好，而且對于進(jìn)行縮放、旋轉(zhuǎn)操作的復(fù)制粘貼篡改圖像的檢測同樣具有很高的魯棒性。

2.1.1 K-means聚類算法

K-means算法能夠以較低維度表示高維度數(shù)據(jù)的局部信息[14]。其原理是將給定的n個數(shù)據(jù)點(diǎn)的數(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)鍵點(diǎn)個數(shù)為m，xi,xj為兩個m維SIFT特征矩陣列向量；dij為xi,xj的距離；N為列向量的總數(shù)。平均差異度越小，樣本與整體越相似。

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

(1)選取k個初始聚類中心c1,c2,…,ck。首先計算特征矩陣T列向量兩兩之間的距離dij，然后計算平均差異度di最小的列向量，作為第一個初始聚類中心c1；選取距離c1最遠(yuǎn)的點(diǎn)作為第二個中心點(diǎn)c2，選取距離c1和c2最遠(yuǎn)的點(diǎn)，作為c3，依次計算中心點(diǎn)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)鍵點(diǎn)，生成關(guān)鍵點(diǎn)的128維SIFT特征向量。

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

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

首先計算特征向量間的歐氏距離，其次在篡改圖像中遍歷每個關(guān)鍵點(diǎn)以找出與這個關(guān)鍵點(diǎn)歐氏距離最近和次近的兩個關(guān)鍵點(diǎn)。如果滿足式7,就認(rèn)為是一對復(fù)制粘貼匹配點(diǎn)，最終確定篡改區(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)行仿真，然后從匹配的正確率和匹配點(diǎn)數(shù)以及檢測時間上進(jìn)行比較。仿真結(jié)果如圖3所示。

圖3 仿真結(jié)果

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

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

(2)匹配精確度：由于PCA是一種線性降維方法，對于具有線性特征分布的特征點(diǎn)能夠起到很好的降維作用，如圖(c)，能夠保留足夠的特征點(diǎn)用于復(fù)制粘貼區(qū)域的匹配，但對于非線性分布的特征點(diǎn)，該算法無法保留足夠的特征點(diǎn)，如圖(g)、(k)，很多特征點(diǎn)被去除，匹配精度很低。而文中算法，在保證匹配點(diǎn)數(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)點(diǎn)，又比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.