陳輝映，張大興，楊珊珊，郭家偉

(杭州電子科技大學(xué) 圖形圖像研究所，浙江 杭州 310018)

0 引 言

研究人員將復(fù)制粘貼篡改檢測技術(shù)分成兩類：基于分塊統(tǒng)計的算法和基于特征點匹配的算法。現(xiàn)有基于分塊統(tǒng)計的算法主要有基于矩的Zernike[1]算法，基于降維的PCA[2]算法、SVD[3]算法，基于灰度值的Circle[4]算法以及基于頻率的DCT[5]算法、DWT[6]算法?；诜謮K統(tǒng)計的算法對不經(jīng)過任何后處理操作的篡改圖片檢測具有一定效果，但普遍存在無法抵抗旋轉(zhuǎn)、縮放等幾何變換操作，且計算雜度高的問題。針對前述問題，有學(xué)者提出基于特征點匹配的檢測算法，如SIFT(scale-invariant feature transform)[7]算法、ORB(oriented brief)[8]算法和MIFT算法等?，F(xiàn)有基于特征點匹配的算法相對基于分塊統(tǒng)計的算法而言，提高了抗后處理操作的魯棒性，但大多只針對單處復(fù)制粘貼篡改，對于多處復(fù)制粘貼篡改圖像檢測效果較差，且檢測速度慢。針對這些問題，本文提出一種基于SURF的圖像復(fù)制粘貼篡改檢測方法，下文簡稱為SURF算法。該算法基于SURF描述符，利用了其不受旋轉(zhuǎn)、縮放等影響的特性，并提出k-g2NN方法對特征點進行匹配，最后根據(jù)幾何約束進行聚類以消除誤匹配，實驗結(jié)果表明了SURF算法的有效性。

1 SURF

SURF(speeded-up robust features)特征提取算法由Bay等提出，它能夠快速高效地提取圖像中的特征點并將其表達成描述符。算法使用方框濾波器代替二階高斯濾波器，用二階Hessian矩陣的近似值做特征點檢測，并在計算過程中引進積分圖像，提高了計算效率。

1.1 快速Hessian矩陣檢測

Hessian矩陣是SURF特征提取的基礎(chǔ)。假設(shè)X=(x,y)為圖像I的某個像素點，則尺度為σ的Hessian矩陣H(X,σ)的定義如下

(1)

det(Hessian)=DxxDyy-(wDxy)2

(2)

式中：w為權(quán)值系數(shù)，用于平衡二階高斯濾波與方框濾波器的能量之差。

圖1 SURF使用的方框濾波器

將輸入圖像與不同參數(shù)值的方框濾波模版進行卷積，可以得到不同的響應(yīng)結(jié)果，即尺度空間中的響應(yīng)圖。在尺度空間中，通過非極大值抑制方法可以找出圖像的興趣點。最后采用三維線性插值法對尺度空間進行插值，以得到特征點的位置值和尺度值。

1.2 特征點描述

SURF算法通過計算特征點鄰域內(nèi)的點在x、y方向上的Harr小波響應(yīng)生成描述子。

首先以檢測到的特征點為圓心劃一個半徑為4s(s為該特征點所在的尺度)的圓，計算圓內(nèi)的點在x、y方向的Haar小波響應(yīng)，并按照距離特征點的遠近對響應(yīng)賦上不同的高斯權(quán)值，距離越近的權(quán)重越大。然后取圓心角為60°的扇形以一定步長旋轉(zhuǎn)覆蓋整個圓形區(qū)域，疊加計算扇形內(nèi)的響應(yīng)得到矢量，并將最長矢量的方向作為特征點的主方向。

確定了特征點的主方向以后，以該點為中心建立直角坐標(biāo)系，y軸與主方向?qū)R以保證特征點不受旋轉(zhuǎn)的影響。在以該點為中心的20s范圍內(nèi)取一個正方形塊，并將其均勻分成4×4的子塊，如圖2所示。對每個子塊計算其對應(yīng)的Harr小波響應(yīng)，將水平方向的Harr小波響應(yīng)記為dx，垂直方向記為dy，為增加抗幾何形變和定位誤差的魯棒性，需要對dx和dy進行加權(quán)，然后對每個子塊的x、y方向的Harr小波響應(yīng)值及其絕對值進行求和，得到的四維向量表示如下

(3)

圖2 特征描述符

將每個子區(qū)域的四維向量連接在一起，可以得到該特征點的64維描述符向量。

2 復(fù)制粘貼篡改檢測算法

2.1 圖像預(yù)處理及SURF特征點提取

RGB顏色空間十分常用，但其3個分量獨立性較低，同時容易受光照變化影響，若存在復(fù)制粘貼區(qū)域較小或明暗差異較大等因素，會導(dǎo)致在RGB顏色空間圖像的特征提取效果不理想。LAB顏色空間與RGB顏色空間不同，它將彩色圖像的色度和亮度分開，消除了RGB模型3個分量高度相關(guān)的缺陷?；谝陨峡紤]，算法將圖像轉(zhuǎn)換到LAB顏色空間后對3個分量值賦予不同權(quán)值并相加，再運用SURF算法提取圖像特征點和特征描述符。

2.2 特征點匹配

提取SURF特征點后，本文在I Amerini等[9]提出的g2NN方法的基礎(chǔ)上進行改進，提出k-g2NN方法對特征點進行匹配。g2NN方法采用搜索多近鄰的方法解決了多處復(fù)制粘貼篡改的問題。假設(shè)對圖像I提取SURF特征，得到特征點集S={s1,s2,…,sn}和對應(yīng)的特征描述符，對某個特征點si求它與余下的特征點對應(yīng)的描述符的歐式距離，對得到的歐式距離進行升序排列，得到距離向量D={d1,d2,…,dn}。圖像特征匹配過程中，若滿足

(4)

則表示特征點與距其最近的特征點匹配，即2NN準(zhǔn)則。τ表示取值為0到1之間的閾值，取值越小誤匹配就越少，但可能會出現(xiàn)漏匹配的現(xiàn)象。g2NN是廣義的2NN，循環(huán)2近鄰準(zhǔn)則進行搜索，依次計算

(5)

若存在z(1<=Z<=n-2)，滿足Tz≤τ且Tz+1>τ，則特征點si和距其{d1,d2,…,dz}的z個特征點均匹配，遍歷所有的特征點得到匹配對集合P={p1,p2,…,pm}，其中p1=(si,sj)即特征點與匹配點組成的二維向量。在匹配過程中，提取的特征點數(shù)量較多，g2NN方法在排序和閾值比較上需要花費大量的時間，效率較低。

本文提出的k-g2NN方法在g2NN方法的基礎(chǔ)上進行改進來提高匹配效率。改進主要分3點：第一，不對得到的歐式距離進行排序，而是直接選取與該特征點對應(yīng)描述符的歐式距離最近的k個特征點，k的取值與得到的特征點個數(shù)成比例且滿足k

2.3 剔除誤匹配

圖像中距離較近的點，往往因為紋理屬性或顏色亮度相似而使得兩點的特征描述符也很相似，進而導(dǎo)致了大量誤匹配的出現(xiàn)[10]。為解決匹配過程中常發(fā)生的誤匹配現(xiàn)象，算法采用對特征的匹配對進行聚類的方法剔除誤匹配。聚類基于幾何約束，先對得到的匹配對進行基于方向的聚類，然后對得到的結(jié)果進行基于距離的再聚類。

(1)基于方向的粗聚類

對匹配對集合P中的元素按照不同方向自然分組，構(gòu)成方向集合R={R1,R2,…,Rn}，其中Rn為這一子方向的匹配對集合。對于新的匹配對，依次計算它與現(xiàn)有方向子集合的主方向的夾角，若小于某個閾值，則將匹配對加入該子集合中。若當(dāng)前匹配對與現(xiàn)有方向子集合均匹配失敗，則創(chuàng)建一個新的方向子集Ri。選擇子集中所有元素方向的均值作為方向子集的主方向，并隨著元素的加入不斷更新

(6)

(2)基于距離的再聚類

按照方向?qū)ζヅ鋵M行粗聚類之后，集合中仍然可能存在匹配對的兩個特征點之間的距離太近或太遠的情況，而這些點并不是所求的篡改區(qū)域的點，因此需要對方向集合中的元素進行基于距離的再聚類。即對于每一個方向子集合Rj進行進一步細分生成距離集合H={H1,H2,…,Hm}。從方向子集合Rj中逐個取匹配對與距離子集合Hj的元素比較特征點間的距離，若距離小于某個閾值則把其添加到這個距離子集合當(dāng)中，否則與下一個距離子集的元素進行比較，若匹配對不屬于任何一個現(xiàn)有子集，則生成一個新的距離子集。

2.4 后處理操作

剔除誤匹配后對檢測結(jié)果進行后處理操作。先將剩下的匹配對所包含的特征點在篡改圖像上標(biāo)示出來，并對標(biāo)示的篡改圖進行二值化處理，其中白色區(qū)域表示篡改圖的復(fù)制和粘貼區(qū)域，然后利用腐蝕和膨脹操作進一步消除誤判，最終將定位的復(fù)制粘貼篡改檢測結(jié)果以二值圖像的形式輸出。

3 實驗結(jié)果與分析

3.1 測試圖庫集

實驗使用的圖庫集I由來自CASIA v2.0(Chinese aca-demy of sciences institute of automation)[11]圖庫的圖片組成。CASIA v2.0圖庫由中國科學(xué)院提供，在國內(nèi)外被廣泛使用，具有一定權(quán)威性，使用者可以根據(jù)自身算法在其中選擇不同類別的一組或多組篡改圖片進行測試。CASIA v2.0圖庫包括7491張原始圖以及5123張篡改圖，其中篡改圖包括JPEG、BMP以及TIFF這3種格式，分辨率從240×160到900×800之間。根據(jù)不同的篡改行為，該圖庫又對篡改圖進行了更細的分類，比如拼接篡改類、復(fù)制-粘貼篡改類、縮放篡改等等。圖庫集I由兩個子庫組成。子庫IA由未經(jīng)篡改的200張原圖組成。子庫IB包括復(fù)制-粘貼篡改類中的共300張圖片，包括兩種多處復(fù)制粘貼篡改圖像，部分圖像篡改區(qū)域經(jīng)過旋轉(zhuǎn)和縮放后處理操作。

3.2 準(zhǔn)確率與虛警率

實驗選擇Amerini等提出的一種基于SIFT的復(fù)制粘貼篡改檢測算法作為對比算法，該算法是目前基于特征點匹配的篡改檢測算法中性能最好的算法之一。并選擇準(zhǔn)確率TPR(true positive rate)和虛警率FPR(false positive rate)作為算法比對的測評標(biāo)準(zhǔn)，TPR表示篡改圖像被檢測成功的比率，F(xiàn)PR表示原始圖像被誤檢測為篡改圖的比率，定義如下

(7)

(8)

其中，Nforged表示篡改圖像的總數(shù)，Noriginal表示原始圖像的總數(shù)，Nfalse表示檢測錯誤的圖像的數(shù)量。對子庫IA中的原始圖像進行檢測得到算法的虛警率，對子庫IB中的篡改圖像進行檢測得到算法的準(zhǔn)確率。SURF算法和SIFT算法對兩個子庫進行檢測得到的虛警率和準(zhǔn)確率見表1，可以看到兩個算法的虛警率相差不大且都很低，但SURF算法檢測的準(zhǔn)確率要比SIFT高6個百分點。

表1 SURF算法和SIFT算法檢測準(zhǔn)確率和虛警率

3.3 多處平移復(fù)制粘貼篡改檢測

多處復(fù)制粘貼篡改技術(shù)可以分為兩種。第一種為一處復(fù)制多處粘貼篡改，如圖3所示，圖3(a)和圖3(d)是兩幅原始圖像，圖3(b)和圖3(e)是分別在兩幅圖像的基礎(chǔ)上將一處區(qū)域復(fù)制多次粘貼在圖像別的區(qū)域得到的圖像，篡改區(qū)域未經(jīng)過后處理操作，圖3(c)和圖3(f)是基于SURF算法對這兩幅篡改圖進行檢測得到的結(jié)果。檢測結(jié)果中的白色區(qū)域其中一處表示原圖被復(fù)制區(qū)域，剩下幾處表示被粘貼篡改的區(qū)域。

圖3 一處復(fù)制多處粘貼篡改檢測實驗

第二種為多處復(fù)制多處粘貼篡改，如圖4所示，圖4(a)和圖4(d)是兩幅原始圖像，圖4(b)和圖4(e)是分別在兩幅圖像的基礎(chǔ)上進行多處復(fù)制多處粘貼得到的篡改圖像，圖3(c)和圖3(f)是基于 SURF算法對這兩幅篡改圖進行檢測得到的結(jié)果。實驗表明本文SURF算法能有效檢測兩種多處復(fù)制粘貼篡改圖片。

圖4 多處復(fù)制多處粘貼篡改檢測實驗結(jié)果

3.4 抗旋轉(zhuǎn)、縮放后處理操作

旋轉(zhuǎn)和縮放是圖像復(fù)制粘貼篡改技術(shù)對篡改區(qū)域常用后處理操作手段?？s放操作如圖5所示，在原圖5(a)的基礎(chǔ)上對粘貼副本進行放大20%和縮小20%操作后分別粘貼在原復(fù)制區(qū)域的左側(cè)和右側(cè)，可以得到篡改圖5(b)，圖5(c)是SURF算法對經(jīng)過縮放操作的篡改圖進行檢測得到的結(jié)果。在原圖5(d)的基礎(chǔ)上對粘貼副本順時針旋轉(zhuǎn)30°和50°操作后分別粘貼在原復(fù)制區(qū)域的上側(cè)和右側(cè)得到篡改圖5(e)，圖5(f)是SURF算法對經(jīng)過旋轉(zhuǎn)操作的篡改圖進行檢測得到的結(jié)果。

圖5 抗旋轉(zhuǎn)和縮放檢測實驗結(jié)果

對子庫IB中包含不同攻擊的篡改圖分別進行檢測，總體檢測結(jié)果如圖6所示，其中綜合表示同時對篡改區(qū)域進行旋轉(zhuǎn)和縮放操作。圖6中每組數(shù)據(jù)的左側(cè)柱形表示SURF算法的檢測結(jié)果，右側(cè)柱型是SIFT算法的檢測結(jié)果。從圖中可以看出，對包含不同幾何攻擊的篡改圖的檢測結(jié)果，SURF算法的檢測準(zhǔn)確率都要高于SIFT算法，且SURF算法在抗幾何變換攻擊方面有較強的魯棒性。

圖6 SURF算法和SIFT算法針對不同攻擊檢測結(jié)果

3.5 抗JPEG壓縮

對圖像進行JPEG壓縮會影響圖像的質(zhì)量，進而影響檢測結(jié)果，抗JPEG壓縮也是復(fù)制粘貼篡改檢測算法重要的性能之一。對圖庫I中的圖像JPEG壓縮后，使用SURF算法和SIFT算法對圖像進行驗測，二者在不同壓縮因子下TPR和FPR變化如圖7所示。隨著JPEG壓縮質(zhì)量的下降，兩者的FPR變化不大，而TPR會受一定影響，但SURF算法的TPR保持比較高的比率且始終高于SIFT算法，穩(wěn)定性較好。實驗結(jié)果表明，SURF算法在抗JPEG壓縮方面具有較強的魯棒性。

3.6 檢測時間

實驗分別使用SURF算法和SIFT進行檢測對子庫IB的所有圖片進行檢測，然后分別計算特征提取時間，特征匹配時間以及總檢測時間的平均值。兩個算法的檢測時間比較結(jié)果見表2。

在檢測速度上，無論是特征提取還是特征匹配過程，本文SURF算法都要優(yōu)于SIFT算法。單一圖像的平均檢測時間SURF算法需要2.6 s，而SIFT算法需要7.3 s，前者的檢測速度比后者提高了64%。實驗結(jié)果表明，SURF算法的檢測速度相比SIFT算法得到了較大的提高。

圖7 JPEG壓縮對SURF算法和SIFT算法的影響

算法名稱特征提取時間特征匹配時間總檢測時間SIFT算法58728947266SURF算法13377352553

4 結(jié)束語

復(fù)制-粘貼是常用的圖像內(nèi)容篡改手段之一?，F(xiàn)有檢測算法大多只在單處復(fù)制粘貼篡改檢測保持一定的檢測性能，但對多區(qū)域復(fù)制粘貼篡改圖像的檢測效果差，且檢測速度慢。本文提出一種高效的基于SURF的多區(qū)域復(fù)制粘貼篡改檢測算法。在保留SURF算法高效的優(yōu)點基礎(chǔ)上結(jié)合k-g2nn算法和聚類方法，能夠進一步提高檢測的精確性和穩(wěn)定性。實驗結(jié)果驗證，算法在保持良好魯棒性的情況下，不僅能夠精確定位出圖像的多處復(fù)制粘貼篡改區(qū)域，檢測速度也得到了較大的提高。