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

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

0 引 言

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

1 SURF

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

1.1 快速Hessian矩陣檢測(cè)

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

(1)

det(Hessian)=DxxDyy-(wDxy)2

(2)

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

圖1 SURF使用的方框?yàn)V波器

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

1.2 特征點(diǎn)描述

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

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

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

(3)

圖2 特征描述符

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

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

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

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

2.2 特征點(diǎn)匹配

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

(4)

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

(5)

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

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

2.3 剔除誤匹配

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

(1)基于方向的粗聚類

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

(6)

(2)基于距離的再聚類

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

2.4 后處理操作

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

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

3.1 測(cè)試圖庫(kù)集

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

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

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

(7)

(8)

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

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

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

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

圖3 一處復(fù)制多處粘貼篡改檢測(cè)實(shí)驗(yàn)

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

圖4 多處復(fù)制多處粘貼篡改檢測(cè)實(shí)驗(yàn)結(jié)果

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

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

圖5 抗旋轉(zhuǎn)和縮放檢測(cè)實(shí)驗(yàn)結(jié)果

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

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

3.5 抗JPEG壓縮

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

3.6 檢測(cè)時(shí)間

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

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

圖7 JPEG壓縮對(duì)SURF算法和SIFT算法的影響

算法名稱特征提取時(shí)間特征匹配時(shí)間總檢測(cè)時(shí)間SIFT算法58728947266SURF算法13377352553

4 結(jié)束語(yǔ)

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