基于超像素分割的圖像復(fù)制粘貼篡改檢測(cè)

劉佳睿， 盧 偉， 劉 軻， 黃信朝， 藺 聰， 劉先進(jìn)

1.中山大學(xué)數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院，廣州510006

2.中科院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100093

隨著圖像編輯軟件和互聯(lián)網(wǎng)的發(fā)展，人們借助圖像處理軟件可以輕松地改變或者偽造一幅圖像的內(nèi)容而不容易被人眼識(shí)別，并在互聯(lián)網(wǎng)上傳播.因此，數(shù)字圖像篡改取證工作備受關(guān)注[1].圖像篡改包含諸多類型，其中區(qū)域復(fù)制粘貼篡改[2]較為常見(jiàn)，它是將圖像的一個(gè)或多個(gè)區(qū)域復(fù)制粘貼到該圖像中的其他區(qū)域以此達(dá)到改變真實(shí)圖像的目的.目前針對(duì)此類篡改研究出了許多檢測(cè)方法，大致可以分為兩類.第1 類是基于塊的區(qū)域重復(fù)檢測(cè)方法，該類方法通常將圖像劃分為若干個(gè)塊，然后對(duì)塊內(nèi)像素點(diǎn)或塊的變換系數(shù)進(jìn)行匹配檢測(cè).文獻(xiàn)[2]提出了離散余弦變換（discrete Cosine transform,DCT）和字典排序法檢測(cè)重復(fù)塊的方法.在此基礎(chǔ)上，文獻(xiàn)[3]對(duì)其進(jìn)行了改進(jìn)，不僅提高了運(yùn)算速度，而且對(duì)JPEG 壓縮、模糊和添加噪聲攻擊也具有了魯棒性.另外，基于離散小波變換（discrete wavelet transform,DWT）和主成分分析（principal component analysis,PCA）的檢測(cè)方法[4-5]對(duì)噪聲和JPEG 壓縮均具有魯棒性.文獻(xiàn)[6-7]提出了基于Zernike 矩陣的方法，該方法提取小圖像塊的Zernike 矩作為該塊的特征，采用基于局部敏感哈希（locality sensitive hashing,LSH）匹配的方式匹配這些小圖像塊，從而進(jìn)行復(fù)制粘貼篡改檢測(cè).文獻(xiàn)[8]提出隨機(jī)抽樣一致（random sample consensus,RANSAC）算法來(lái)減少錯(cuò)誤匹配對(duì)，該方法對(duì)旋轉(zhuǎn)、噪聲和JPEG 壓縮均具有較強(qiáng)的魯棒性.基于塊的檢測(cè)方法盡管在單純的平移復(fù)制粘貼檢測(cè)中表現(xiàn)良好，但是在大幅度的幾何變換情況下表現(xiàn)不佳且計(jì)算時(shí)間冗長(zhǎng).

為了克服塊方法的缺點(diǎn)，人們提出了第2 類方法--基于關(guān)鍵點(diǎn)的方法.這類方法通常是從整幅圖像中提取關(guān)鍵點(diǎn)，然后對(duì)其進(jìn)行匹配檢測(cè)，例如尺度不變特征變換（scale invariant feature transform,SIFT）[9]和SURF（speeded up robust features,SURF）[10]方法.文獻(xiàn)[11]在區(qū)域檢測(cè)中利用了SIFT 的方法，并在SIFT 算法的基礎(chǔ)上計(jì)算復(fù)制區(qū)域和粘貼區(qū)域的仿射變換矩陣，這種方法在檢測(cè)JPEG 壓縮和添加噪聲時(shí)具有魯棒性.文獻(xiàn)[12]在SIFT 特征點(diǎn)方法上增加了層次聚類，改善了聚類效果，從而提高了檢測(cè)復(fù)制區(qū)域的性能.文獻(xiàn)[13]在上述關(guān)鍵點(diǎn)方法的框架上使用J-Linkage 聚類方法，該方法主要包括了圖像分割和關(guān)鍵點(diǎn)匹配兩部分，其中關(guān)鍵點(diǎn)匹配又分為2 個(gè)步驟：第1 步是粗略推測(cè)變換矩陣；第2 步是移動(dòng)關(guān)鍵點(diǎn)的定位，根據(jù)基于EM 的算法進(jìn)一步推測(cè)變換矩陣.另外，文獻(xiàn)[14]提出了采用圖像分割策略進(jìn)行篡改檢測(cè)的方法.

關(guān)鍵點(diǎn)方法在面對(duì)包含JPEG 壓縮和噪聲的篡改時(shí)具有良好的魯棒性，但是難以檢測(cè)到小區(qū)域或關(guān)鍵點(diǎn)數(shù)目較少的區(qū)域的復(fù)制粘貼操作.基于塊的方法能夠在單純的復(fù)制粘貼情形下具有良好的性能，然而目前階段通用算法速度慢，難以處理旋轉(zhuǎn)、縮放、添加噪聲等攻擊.有些方法可以檢測(cè)出比一般算法更多的復(fù)制塊，因而召回率較高；同時(shí)正因?yàn)樗鶛z測(cè)出的復(fù)制塊較多，會(huì)將某些背景也當(dāng)作復(fù)制區(qū)域，導(dǎo)致檢測(cè)精確率下降.所以召回率和精確率之間需要一個(gè)平衡.

為了解決上述問(wèn)題，本文提出了一種基于超像素分割[15]的方法，將圖像分為多個(gè)子區(qū)域（塊），并將每一個(gè)子區(qū)域編號(hào).在利用SIFT 特征得到匹配點(diǎn)對(duì)后，將匹配點(diǎn)置于圖像的子區(qū)域中，根據(jù)子區(qū)域內(nèi)特征點(diǎn)的數(shù)目進(jìn)行聚類.

1 SIFT 算法

尺度不變特征變換（SIFT）算法是一種提取數(shù)字圖像局部性特征的算法，它在尺度空間中尋找極值點(diǎn)，并提取出其位置、尺度、旋轉(zhuǎn)不變量.該算法對(duì)旋轉(zhuǎn)、縮放、亮度變化都保持良好的魯棒性，對(duì)仿射變換和噪聲也具有一定的魯棒性，且SIFT 特征相對(duì)容易獲取，識(shí)別率較高，近些年，很多研究人員將SIFT 算法用于數(shù)字圖像的復(fù)制粘貼檢測(cè)中，也收獲了不錯(cuò)的成果.SIFT 算法涉及以下4 個(gè)關(guān)鍵步驟.

1.1 尺度空間極值檢測(cè)

SIFT 算法的特征點(diǎn)是在高斯差分（difference of Gaussian,DoG）金字塔上通過(guò)檢測(cè)極值點(diǎn)的方法求得的.對(duì)于圖像D，高斯差分金字塔的計(jì)算公式為

式中，L(x,y,kσ)表示原圖I(x,y)與高斯核G(x,y,kσ)在kσ尺度上的卷積和.將高斯差分金字塔中的像素點(diǎn)與其同尺度的8 鄰域像素以及上下相鄰尺度的18 個(gè)像素進(jìn)行比較，即可獲得極值點(diǎn).

1.2 關(guān)鍵點(diǎn)定位

對(duì)求取的極值點(diǎn)進(jìn)行三維二次擬合，去除對(duì)比度低的不穩(wěn)定點(diǎn)，然后進(jìn)一步利用主曲率去除邊緣點(diǎn)，剩余的極值點(diǎn)便作為關(guān)鍵點(diǎn).

1.3 關(guān)鍵點(diǎn)方向確定

為了使特征描述子具有旋轉(zhuǎn)不變性，需要利用圖像的局部特征為關(guān)鍵點(diǎn)分配方向，利用特征點(diǎn)所在的鄰域像素梯度來(lái)確定該點(diǎn)的方向參數(shù).梯度值大小m(x,y)及其方向θ(x,y)的計(jì)算公式分別為

確定梯度后采用直方圖統(tǒng)計(jì)鄰域像素方向和梯度，直方圖的峰值方向即為關(guān)鍵點(diǎn)的主方向.

1.4 關(guān)鍵點(diǎn)描述

對(duì)已確定的關(guān)鍵點(diǎn)，在其尺度空間內(nèi)的4×4 的窗口中計(jì)算8 個(gè)方向的梯度信息，再將其轉(zhuǎn)換為128 維向量，生成SIFT 描述子.

2 本文方法

2.1 特征提取

本文用式（1）對(duì)待檢測(cè)的數(shù)字圖像求取高斯差分金字塔，將每個(gè)點(diǎn)與其鄰域空間進(jìn)行比較，求出特征點(diǎn)X={x1,x2,··· ,xn}；然后借助式（2）和（3）求出特征點(diǎn)梯度值及其方向，生成特征點(diǎn)的描述子集合F={f1,f2,··· ,fn}.

2.2 特征點(diǎn)匹配

對(duì)于得到的128 維特征描述子，本文采用歐氏距離來(lái)衡量不同向量之間的差別.由于SIFT 描述子是一個(gè)128 維的向量，歐氏距離可能取值波動(dòng)較大，單純用一個(gè)閾值來(lái)判斷兩描述子是否匹配會(huì)導(dǎo)致較大的誤差，因而本文采用2NN 匹配方法，求出某一描述子與其他描述子的歐氏距離后進(jìn)行排序，得到D={d1,d2,··· ,dn}，其中d1為最近距離.設(shè)閾值t，若d1/d2＜t，則認(rèn)為d1對(duì)應(yīng)的描述子與該描述子匹配，即這2 個(gè)特征點(diǎn)匹配.另外考慮到復(fù)制粘貼篡改可能出現(xiàn)多次粘貼的現(xiàn)象，需要一直比較到出現(xiàn)大于閾值的情況為止以確保證求出所有的匹配對(duì)，進(jìn)而檢測(cè)出可能存在的多個(gè)復(fù)制粘貼對(duì).對(duì)各個(gè)特征點(diǎn)描述子進(jìn)行上述2NN 匹配，即可得到所有匹配對(duì).

2.3 聚類及篡改檢測(cè)

圖像的復(fù)制粘貼篡改操作實(shí)際上都具有某種目的（如將墻上的1 幅畫(huà)復(fù)制成2 幅）.文獻(xiàn)[16]提出借助將圖像劃分為諸多有意義的子區(qū)域（如1 幅畫(huà)為1 個(gè)子區(qū)域）的辦法來(lái)提高聚類質(zhì)量.

本文提取的特征點(diǎn)是在空間尺度（高斯差分空間）中尋找極值點(diǎn)，它們通常為邊緣點(diǎn)、角點(diǎn)、明亮區(qū)域中的暗點(diǎn)以及黑暗區(qū)域中的明亮點(diǎn)，這些點(diǎn)反映了圖像的局部特征.為了提高特征點(diǎn)聚類的效率，需將圖像劃分為若干個(gè)有意義的子區(qū)域（局部）進(jìn)行聚類，本文采用了文獻(xiàn)[15]提出的超像素分割算法（TurboPixels）進(jìn)行聚類.該算法能夠根據(jù)圖像內(nèi)部的紋理、顏色、亮度等特征將圖像進(jìn)行區(qū)域劃分，并在子區(qū)域中對(duì)所提取的圖像局部特征點(diǎn)進(jìn)行聚類，充分發(fā)揮SIFT 算法和超像素分割算法的優(yōu)勢(shì).可以看出，該算法實(shí)際上是利用了特征點(diǎn)反映局部特征的特性，從而借助局部特性提高聚類效率.

TurboPixels 算法初始將N個(gè)種子置于圖像中，對(duì)所有種子點(diǎn)進(jìn)行標(biāo)記，隨后種子開(kāi)始擴(kuò)張.設(shè)Δt為每次擴(kuò)張的像素點(diǎn)數(shù)，ψ(x,y)為點(diǎn)(x,y)到最近的已標(biāo)記點(diǎn)的距離，即點(diǎn)到最近種子邊界的距離，則一個(gè)點(diǎn)的一次擴(kuò)張可以表示為

式中，SI為當(dāng)前圖像的局部結(jié)構(gòu)，SB為當(dāng)前點(diǎn)與其他種子邊界的距離.SI由以下2 個(gè)因素決定：一是圖像在該點(diǎn)的梯度，梯度越大值越低；二是該點(diǎn)與圖像邊界的距離，距離越近值越小.此外，當(dāng)前點(diǎn)距離其他種子的邊界點(diǎn)越近，SB越小.SI和SB共同調(diào)節(jié)在當(dāng)前點(diǎn)的擴(kuò)張速度.

該算法關(guān)注的是每個(gè)種子邊界外4 個(gè)像素點(diǎn)寬的“窄帶”上點(diǎn)的ψ值.一旦標(biāo)記完所有的點(diǎn)算法即可停止，共得N個(gè)子區(qū)域，編號(hào)為1～N.

求出匹配對(duì)P1和P2后對(duì)其分別進(jìn)行“聚類”，若某一個(gè)子區(qū)域中點(diǎn)的數(shù)目達(dá)到閾值Th，則可以判定該子區(qū)域內(nèi)的點(diǎn)屬于一個(gè)整體，可聚成一類；反之，若一個(gè)子區(qū)域內(nèi)點(diǎn)的數(shù)目小于閾值，則認(rèn)為這些點(diǎn)是散點(diǎn)，將其剔除.

聚類完成后，若存在2 個(gè)或2 個(gè)以上的簇，即可認(rèn)為該圖像D是經(jīng)過(guò)復(fù)制粘貼篡改的.

2.4 估計(jì)仿射變換矩陣

這個(gè)矩陣需要至少3 個(gè)匹配點(diǎn)對(duì)才能求得.本文采用最大似然估計(jì)法來(lái)推測(cè)H，該方法是通過(guò)尋找最佳匹配對(duì)的方式來(lái)降低推測(cè)誤差的.誤差δ公式為

圖1 超像素分割在聚類中的應(yīng)用Figure1 Application of super pixel segmentation in clustering

3 實(shí) 驗(yàn)

3.1 測(cè)試數(shù)據(jù)集

本文測(cè)試實(shí)驗(yàn)采用Christlein[17]構(gòu)建的圖像處理數(shù)據(jù)集（image manipulation dataset,IMD）.該數(shù)據(jù)集包含不同尺寸的未篡改圖像（共計(jì)48 幅），以及平移、縮放、旋轉(zhuǎn)、添加噪聲和JPEG 壓縮共計(jì)5 種攻擊方式的復(fù)制粘貼篡改圖像，該數(shù)據(jù)集共有1 488 幅圖像.

平移：有48 幅原始圖像和48 幅經(jīng)過(guò)平移的圖像，共96 幅圖像.

縮放：粘貼區(qū)域?qū)?huì)進(jìn)行縮放，縮放比從0.91 到1.09，步長(zhǎng)為0.02，共480 幅圖像.

旋轉(zhuǎn)：粘貼區(qū)域?qū)?huì)進(jìn)行旋轉(zhuǎn)，旋轉(zhuǎn)角度從2°到10°，步長(zhǎng)為2°，共240 幅圖像.

添加噪聲：在粘貼區(qū)域添加高斯噪聲，標(biāo)準(zhǔn)差從0.02 到0.1，步長(zhǎng)為0.02，共240 幅圖像.

JPEG 壓縮：質(zhì)量因子取值從20 到100，步長(zhǎng)為10，共計(jì)432 幅圖像.

3.2 評(píng)價(jià)指標(biāo)

本文實(shí)驗(yàn)在像素級(jí)上采用召回率（recall）、精確率（precision）和F1分?jǐn)?shù)[17]來(lái)衡量檢測(cè)算法的性能，其中召回率為

精確率為

式中，tp表示算法判定為篡改區(qū)域且事實(shí)上也是篡改區(qū)域的像素?cái)?shù)，fp表示算法判定為篡改區(qū)域但實(shí)際上不是篡改區(qū)域的像素?cái)?shù)，fn表示算法判定為非篡改區(qū)域但實(shí)際上是篡改區(qū)域的像素?cái)?shù).

3.3 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

3.3.1 平移復(fù)制粘貼檢測(cè)結(jié)果

圖2為部分實(shí)驗(yàn)結(jié)果示意圖，可以看出本文算法得到了較好的效果.表1展示了在試驗(yàn)數(shù)據(jù)集中平移復(fù)制粘貼檢測(cè)的結(jié)果，并將本文提出的算法實(shí)驗(yàn)結(jié)果與SIFT 和SURF 的算法結(jié)果進(jìn)行了比較.可以看出本文算法在平移復(fù)制粘貼篡改情況下表現(xiàn)出明顯優(yōu)于SIFT 和SURF 算法的特點(diǎn).

圖2 SIFT、SURF 以及本文算法結(jié)果比較Figure2 Results comparison of SIFT,SURF and the proposed method

表1 平移復(fù)制粘貼篡改檢測(cè)結(jié)果Table1 Detection results of plain copy-move forgery

3.3.2 其他形式復(fù)制粘貼檢測(cè)結(jié)果

在試驗(yàn)數(shù)據(jù)集中，其他形式復(fù)制粘貼攻擊檢測(cè)的結(jié)果如表2～5 所示.本文實(shí)驗(yàn)測(cè)試了4 種形式的復(fù)制粘貼篡改攻擊，分別為JPEG 壓縮、添加噪聲、旋轉(zhuǎn)、縮放，并將其測(cè)試結(jié)果與SIFT 和SURF 算法進(jìn)行了比較.結(jié)果顯示，本文方法在對(duì)抗平移變換、JPEG 壓縮變換、旋轉(zhuǎn)和縮放變換時(shí)仍具有良好的魯棒性，在召回率、精確率和F1分?jǐn)?shù)方面都明顯優(yōu)于SIFT[9]和SURF[10]算法.然而，本文算法在面對(duì)添加噪聲的復(fù)制粘貼篡改攻擊時(shí)表現(xiàn)不佳，原因是噪聲攻擊導(dǎo)致圖像匹配點(diǎn)對(duì)數(shù)量減少，使聚類時(shí)部分子區(qū)域內(nèi)點(diǎn)對(duì)數(shù)目未達(dá)到閾值，以致沒(méi)有成功聚類.

表2 JPEG 壓縮復(fù)制粘貼篡改檢測(cè)結(jié)果Table2 Detection results of JPEG compression copy-move forgery

表3 添加噪聲復(fù)制粘貼篡改檢測(cè)結(jié)果Table3 Detection results of adding noise copymove forgery

表4 旋轉(zhuǎn)復(fù)制粘貼篡改檢測(cè)結(jié)果Table4 Detection results of rotation copy-move forgery

表5 縮放復(fù)制粘貼篡改檢測(cè)結(jié)果Table5 Detection results of scale copy-move forgery

4 結(jié) 語(yǔ)

本文提出一種基于超像素分割的圖像復(fù)制粘貼篡改檢測(cè)算法.該方法利用超像素分割算法將圖像根據(jù)局部特征分為若干個(gè)子區(qū)域，求出特征匹配點(diǎn)對(duì)后將待聚類的匹配點(diǎn)置于分割后的圖像中.若一個(gè)子區(qū)域中包含3 個(gè)及以上的點(diǎn)，即可將該子區(qū)域中的點(diǎn)聚成一類；若少于3 個(gè)，則認(rèn)為區(qū)域中的點(diǎn)是錯(cuò)點(diǎn)，將其忽略.所提方法將聚類與圖像區(qū)域內(nèi)容結(jié)合，在聚類時(shí)從圖像子區(qū)域的內(nèi)容特征出發(fā)，先以圖像內(nèi)容進(jìn)行子區(qū)域劃分，再用圖像子區(qū)域內(nèi)容指導(dǎo)聚類，使得聚類結(jié)果更加貼合圖像本身，能夠更加清楚地反映實(shí)際的復(fù)制粘貼篡改區(qū)域情況.