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

葉雨晴，邱曉暉

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

0 引 言

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

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

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

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

針對圖像復制粘貼篡改操作，以圖像特征點匹配為切入點，對傳統SIFT算法特征向量維數過高的缺點，對SIFT算法進行改進。

1 SIFT算法簡介

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

(1)尺度空間的構建。

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

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

(1)

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

(2)

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

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

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

(3)

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

(3)計算關鍵點。

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

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

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

(4)

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

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

2 基于改進SIFT算法的圖像復制粘貼篡改檢測

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

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

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

2.1.1 K-means聚類算法

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

2.1.2 基于K-means的改進SIFT算法

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

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

(5)

(6)

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

假設SIFT算法提取到的特征點個數為m，則得到的特征向量矩陣T的大小為m×128。基于K-means的改進SIFT算法具體步驟如下：

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

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

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

狀態監測系統提供豐富直觀的、可組態的多個監測畫面，從不同的角度、分層次展現機組的狀態信息。監測畫面中將各種監測狀態以圖表、圖形、數據等形式展示出來。

(4)重復步驟2和步驟3，直到聚類中心基本穩定或迭代次數達到上限結束。

2.2 基于改進SIFT算法的圖像復制粘貼篡改檢測步驟

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

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

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

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

(7)

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

算法流程如圖2所示。

圖2 基于K-means的改進SIFT算法流程

3 實驗結果分析

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

圖3 仿真結果

從表1～3可以得出以下結論：

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

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

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

表2 旋轉操作下的各類算法檢測結果對比

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

4 結束語

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

參考文獻:

[1] 柴新新,邱曉暉.基于提升小波變換的圖像篡改檢測算法[J].計算機技術與發展,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] 林 晶,黃添強,林玲鵬,等.采用局部強度順序模式的圖像復制—粘貼篡改檢測算法[J].通信學報,2016,37:132-139.

[10] 何林遠,畢篤彥,馬時平,等.基于SIFT和MSE的局部聚集特征描述新算法[J].電子學報,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算法在圖像匹配中的應用[J].電視技術,2015,39(7):21-24.

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

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

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

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