低頻快速切比雪夫矩的篡改圖像檢測(cè)算法①

鄭佳雯,張威虎

(西安科技大學(xué) 通信與信息工程學(xué)院,西安 710054)

數(shù)字圖像處理技術(shù)的快速發(fā)展在給人們帶來(lái)生活便捷的同時(shí),也存在著圖像本身的真實(shí)性和完整性等問(wèn)題,目前篡改后的數(shù)字圖像出現(xiàn)在醫(yī)學(xué)研究、新聞報(bào)道或法庭證據(jù)等重要場(chǎng)合,這會(huì)對(duì)社會(huì)造成極大的負(fù)面影響,因此,對(duì)于檢測(cè)數(shù)字圖像是否真實(shí)得到了人們的密切關(guān)注.當(dāng)前圖像篡改檢測(cè)算法主要分為兩大類:一是主動(dòng)檢測(cè)算法,另一種是被動(dòng)檢測(cè)算法[1].被動(dòng)檢測(cè)算法在沒(méi)有任何先驗(yàn)信息的情況下,利用圖像的本身特性對(duì)原圖像進(jìn)行真實(shí)性檢測(cè),此類檢測(cè)算法已經(jīng)得到了廣泛應(yīng)用[2].

復(fù)制粘貼篡改是生活中常見的圖像篡改方式.復(fù)制粘貼篡改圖像的檢測(cè)方法可以分為兩類:基于特征點(diǎn)的檢測(cè)算法和基于圖像塊的檢測(cè)算法,基于圖像塊的算法在準(zhǔn)確定位到篡改區(qū)域上優(yōu)于基于特征點(diǎn)的算法.Ryu SJ 等[3]提出了一種基于Zernike 矩定位復(fù)制圖像區(qū)域的算法,設(shè)計(jì)了一種局部敏感散列的新型塊匹配,并通過(guò)檢查矩的相位來(lái)減少誤匹配,但對(duì)于較大尺度變換的檢測(cè)效果不是很好.Dixit R 等[4]利用傅里葉-梅林變換和對(duì)數(shù)極坐標(biāo)映射以及使用K 均值聚類的基于顏色的分割技術(shù),具有較好的平移和旋轉(zhuǎn)不變性,但算法的實(shí)時(shí)性差.谷宗運(yùn)等[5]提出了一種基于Tchebichef矩的篡改圖像檢測(cè)算法,比較提取的DWT 和Tchebichef矩相鄰特征向量的相似性,實(shí)現(xiàn)篡改區(qū)域的定位,但對(duì)于多區(qū)域篡改區(qū)域定位效果較差.

針對(duì)上述算法的不足,本文提出一種低頻快速切比雪夫矩算法的篡改圖像檢測(cè)算法,首先采用非抽樣小波變換對(duì)圖像二維分解,對(duì)低頻部分進(jìn)行重疊分塊,再提取圖像塊的快速切比雪夫矩特征,采用PatchMatch算法對(duì)特征向量進(jìn)行匹配,最后用稠密線性擬合算法消除誤匹配以及形態(tài)學(xué)操作定位篡改區(qū)域.

1 構(gòu)造特征向量

1.1 Tchebichef 矩

假設(shè)圖像f(x,y)上一點(diǎn)(p,q),位于大小為N×N圖像塊(p,p+N-1)×(q,q+N-1),其n+m階Tchebichef 矩為[6]:

其中,tn(x)和tm(y)為n階和m階正交切比雪夫多項(xiàng)式,定義如下:

其中,(·)l表示階乘冪.tm(y)定義類似.

正交切比雪夫多項(xiàng)式在x 處的tn(x)和在x+a處的tn(x+a)有如下關(guān)系[7]:

當(dāng)a=1 時(shí),有:

其中,gr(n,l)定義為:

1.2 改進(jìn)的低頻快速Tchebichef 矩

對(duì)于圖像篡改,如果非平移不變,在復(fù)制和粘貼兩個(gè)相同的區(qū)域會(huì)被破壞,會(huì)出現(xiàn)漏檢情況.下采樣使得離散小波變換(DWT)不具有平移不變性,不僅會(huì)對(duì)DWT 系數(shù)產(chǎn)生巨大影響,還會(huì)對(duì)篡改區(qū)域產(chǎn)生不同的特征向量.另外,DWT 的偽吉布斯現(xiàn)象使得檢測(cè)邊緣和紋理等信號(hào)的效果不夠理想.對(duì)于DWT 存在的不足,這里采用具有平移不變性的非抽樣小波變換(UWT),由于UWT 不包括下采樣和小波系數(shù)縮減,因此稱為非抽樣的[8].

對(duì)圖像利用UWT 沿行和列進(jìn)行二維分解,分別得到4 個(gè)子帶,即水平高通子帶LH,垂直高通子帶HL、對(duì)角高通子帶HH 以及低通子帶LL,每個(gè)子帶的尺寸不發(fā)生變化[9].

圖像進(jìn)行過(guò)UWT 后,由于圖像的主要部分是低頻部分,所以提取圖像的低頻部分.對(duì)提取的低頻部分進(jìn)行檢測(cè),可以大大降低塊的個(gè)數(shù),使得計(jì)算量?jī)H為原來(lái)的1/4,同時(shí)低頻對(duì)噪聲不敏感,也可以加強(qiáng)特征的魯棒性.再對(duì)圖像進(jìn)行分塊,假設(shè)待測(cè)圖像大小為M×N,用a×a像素的滑動(dòng)窗口每次移動(dòng)一個(gè)像素點(diǎn)對(duì)圖像進(jìn)行掃描,可以得到(M-a+1)×(N-a+1)個(gè)重疊塊.

對(duì)于一個(gè)大小為N×N滑動(dòng)塊(p+1,p+N)×(q,q+N-1),其n+m階水平方向的Tchebichef 矩為:

相同地,對(duì)于下一個(gè)大小為N×N滑動(dòng)塊(p,p+N-1)×(q+1,q+N),其n+m階垂直方向的Tchebichef 矩為:

T分別表示輸出行f(p+x,q),0 ≤x ≤N-1,m階切比雪夫矩和輸入行f(p+x,q+N),0 ≤x ≤N-1,m階切比雪夫矩,定義如下:

基于上述理論,對(duì)于圖像f(x,y),低頻快速切比雪夫矩算法如下:

(1)對(duì)圖像進(jìn)行UWT 二維分解,提取其低頻部分并進(jìn)行重疊分塊;

(2)計(jì)算切比雪夫多項(xiàng)式和系數(shù)矩陣;

(3)計(jì)算所有的行向量.對(duì)于圖像f(x,y)每行的第一個(gè)行向量,計(jì)算其切比雪夫矩,每行的其余行向量計(jì)算其快速切比雪夫矩;

(4)計(jì)算所有的列向量的切比雪夫矩;

(5)計(jì)算圖像f(x,y)第一個(gè)塊的矩特征,基于步驟(4)的結(jié)果,采用快速切比雪夫矩計(jì)算第一行的所有塊的矩特征;

(6)基于步驟(2)和步驟(4)的結(jié)果,采用快速切比雪夫矩計(jì)算其他塊的矩特征.

2 PatchMatch 算法匹配

本文采用PatchMatch 算法進(jìn)行特征匹配,它是一種圖像塊之間尋找最近鄰匹配的快速隨機(jī)算法,將正確的偏移量傳播并且迭代更新至全部偏移量,相比較傳統(tǒng)的kd-tree 算法而言,不僅可以大大減少處理時(shí)間,還可以提供準(zhǔn)確的匹配率[11].算法步驟如下:

(1)初始化.對(duì)于每個(gè)像素s,隨機(jī)初始化偏移量:

其中,U(s)是一個(gè)二維隨機(jī)變量,并且均勻分布在整個(gè)圖像.由于我們正在尋找與目標(biāo)相對(duì)較遠(yuǎn)的匹配,這里我們不考慮 δ(s)=0,以及所有偏移量小于給定閾值的情況.雖然大多數(shù)初始隨機(jī)偏移量很少用到,但也有可能是最優(yōu)的或近似最優(yōu)的.

(2)傳播.在這個(gè)階段,圖像按照從上到下、從左到右的順序光柵掃描,則每個(gè)像素s偏移量更新為:

其中,ΔP(s)={δ(s),δ(sr),δ(sc)},sr和sc分別表示光柵按行和列掃描的像素s之前的像素.每個(gè)像素判斷相鄰塊的偏移量是否提供了更好的匹配,如果是,則采用相鄰塊的偏移量.若給定區(qū)域像素具有恒定偏移量,就可獲得正確偏移量,并迅速傳播,填充整個(gè)區(qū)域的下方和右側(cè).每次迭代更新時(shí),按照反轉(zhuǎn)的光柵順序(從下到上、從右到左)掃描圖像,以獲得更準(zhǔn)確的偏移量.

(3)隨機(jī)搜索.由于傳播過(guò)程依賴于隨機(jī)初始的偏移量,所以不能達(dá)到最優(yōu)匹配.為了盡量避免陷入局部最小值,采用隨機(jī)搜素,在修正式(13)后,對(duì)當(dāng)前偏移量進(jìn)行隨機(jī)采樣,設(shè)候選偏移量δi(s),i=1,···,L為:

其中,Ri是一個(gè)二維隨機(jī)變量,并且均勻分布在除去原點(diǎn)的半徑為2i-1的方形區(qū)域中.事實(shí)上,大多數(shù)的候選偏移量非常接近δ(s),隨機(jī)搜索后偏移量更新為:

其中,ΔR(s)={δ(s),δ1(s),···,δL(s)}.

3 后處理

除了平滑區(qū)域之外,通過(guò)特征匹配獲得的偏移量應(yīng)該是細(xì)節(jié)化的.但是由于噪聲、壓縮、幾何變換、光照變化和相似區(qū)域等原因[12],PatchMatch 算法獲得的偏移量很少遵循該情況,因此后處理階段需要:(1)對(duì)偏移量進(jìn)行正則化.(2)添加適當(dāng)?shù)募s束.

由于隱式過(guò)濾得到的偏移量已經(jīng)足夠規(guī)則,所以需要添加適當(dāng)?shù)募s束.這里采用稠密線性擬合的方法[13],這是因?yàn)樗鼜?fù)雜性低并且可以快速地得到正確的偏移量.

通過(guò)仿射模型,在像素s的適當(dāng)N像素鄰域內(nèi)擬合出真實(shí)偏移量:

轉(zhuǎn)換參數(shù)A,設(shè)置為平方誤差之和的最小值.

雖然偏移量是二維的,但是參數(shù)A 可以針對(duì)每一維進(jìn)行獨(dú)立地優(yōu)化,因此,可以將 δ(x)視為一維偏移量,問(wèn)題轉(zhuǎn)化為:

其中,δ=[δ(s1),δ(s2),···,δ(sN)]T是匹配階段的偏移量,a=[a0,a1,a2]T是識(shí)別仿射模型的參數(shù)向量,S是鄰域內(nèi)所有像素齊次坐標(biāo)的N×3 矩陣.

因此真實(shí)偏移量為:

這是一個(gè)多元線性回歸問(wèn)題,解為:

因此,相應(yīng)的平方誤差之和為:

H=S(STS)-1ST

其中,是對(duì)稱的,進(jìn)一步簡(jiǎn)化H矩陣為:

其中,qj為N行列向量,所以,有:

下面給出具體的后處理步驟:

(1)對(duì)得到的偏移量進(jìn)行中值濾波操作.

(3)去除誤匹配對(duì),包括較匹配區(qū)域?qū)Φ木嚯x像素更接近的匹配對(duì),或小于匹配區(qū)域面積像素的匹配對(duì).

(4)映射檢測(cè)到的區(qū)域.

(5)使用圓形的結(jié)構(gòu)元素進(jìn)行形態(tài)學(xué)操作,實(shí)現(xiàn)篡改圖像區(qū)域的定位完成檢測(cè).

為了證明稠密線性擬合方法的有效性,對(duì)篡改圖像后處理階段的進(jìn)行檢測(cè),如圖1 所示.由圖1 可知,匹配階段的偏移量已經(jīng)足夠規(guī)則,但還存在較多誤檢,后處理階段采用稠密線性擬合方法可有效降低誤檢率.

圖1 篡改圖像后處理的檢測(cè)結(jié)果

4 實(shí)驗(yàn)分析

實(shí)驗(yàn)是在Windows10 操作系統(tǒng)下,采用Matlab 軟件測(cè)試的.為了驗(yàn)證本文方法的可行性和有效性,實(shí)驗(yàn)采用的數(shù)據(jù)集為benchmark data[14],該數(shù)據(jù)集包括48 幅原圖像以及48 幅篡改圖像,篡改區(qū)域包括單區(qū)域和多區(qū)域.同時(shí)將本文方法與文獻(xiàn)[5]和文獻(xiàn)[14]進(jìn)行對(duì)比來(lái)證明本文方法的優(yōu)越性.

性能分析主要包括圖像層面和像素層面,本文從像素層面來(lái)衡量篡改檢測(cè)算法的性能,采用precision、recall和F這3 個(gè)指標(biāo),定義如下:

其中,precision為檢測(cè)準(zhǔn)確率,即檢測(cè)為篡改圖像的數(shù)據(jù)集中有多少是真正的篡改圖像,包括把篡改圖像檢測(cè)為篡改圖像及把真實(shí)圖像檢測(cè)為篡改圖像;recall為檢測(cè)召回率,即數(shù)據(jù)集中的篡改圖像有多少被正確檢測(cè)了,包括把篡改圖像檢測(cè)為篡改圖像及把篡改圖像檢測(cè)為真實(shí)圖像;F為綜合評(píng)價(jià)指標(biāo).TP為篡改圖像中被正確檢測(cè)到的篡改像素?cái)?shù)量,FP為篡改圖像中未篡改部分被檢測(cè)為篡改像素的數(shù)量,FN為篡改圖像中的篡改部分未被檢測(cè)到的篡改像素?cái)?shù)量.precision和recall這2 個(gè)評(píng)價(jià)指標(biāo)相互制約,F綜合考慮了這兩個(gè)指標(biāo),F值越大,算法的檢測(cè)性能越好.

本文對(duì)篡改區(qū)域?yàn)閱我粎^(qū)域和多區(qū)域分別進(jìn)行了實(shí)驗(yàn),單區(qū)域篡改圖像的檢測(cè)結(jié)果見圖2,單區(qū)域多次篡改圖像的檢測(cè)結(jié)果見圖3,多區(qū)域篡改圖像的檢測(cè)結(jié)果見圖4,表1 為3 種算法篡改檢測(cè)性能的比較.

圖2 單區(qū)域篡改圖像的檢測(cè)結(jié)果

圖3 單區(qū)域多次篡改圖像的檢測(cè)結(jié)果

圖4 多區(qū)域篡改圖像的檢測(cè)結(jié)果

表1 3 種算法檢測(cè)性能的比較(%)

由圖2～圖4 可知,文獻(xiàn)[5]和文獻(xiàn)[14]都會(huì)出現(xiàn)漏檢測(cè)的情況,尤其對(duì)于圖4(c)出現(xiàn)兩個(gè)不同的篡改區(qū)域,而只定位出一個(gè)篡改區(qū)域,雖然文獻(xiàn)[14]的檢測(cè)結(jié)果優(yōu)于文獻(xiàn)[5]的檢測(cè)結(jié)果,但是檢測(cè)到的篡改區(qū)域還是會(huì)遺漏一些篡改區(qū)域的細(xì)節(jié)信息,綜合來(lái)說(shuō),本文算法的檢測(cè)結(jié)果是最好的.為了更加準(zhǔn)確地體現(xiàn)本文算法的優(yōu)越性,由表1 可知,本文算法的綜合評(píng)價(jià)標(biāo)準(zhǔn)F是最高的,其中precision分別提高了8.1%和1.8%,recall分別提高了3.3%和1.2%,F分別提高了3.5%和1.5%,與上圖中的檢測(cè)結(jié)果一致.這是因?yàn)槲墨I(xiàn)[5]采用DWT 和Tchebichef 矩結(jié)合的特征向量,比較其相似性定位篡改區(qū)域,特征向量沒(méi)有很好地表示篡改圖像信息,會(huì)存在漏檢測(cè)的情況;文獻(xiàn)[14]對(duì)每個(gè)重疊分塊提取快速切比雪夫矩特征,特征匹配使采用kdtree 算法,kd-tree 算法不能很好地實(shí)現(xiàn)篡改圖像的匹配;本文算法采用低頻快速切比雪夫矩作為特征向量,PatchMatch 算法進(jìn)行特征匹配,最后用稠密線性擬合算法消除誤匹配,這樣可以較好地描述圖像信息,防止漏檢和誤檢的情況.

我們還比較了本文算法和文獻(xiàn)[5]和文獻(xiàn)[14]在數(shù)據(jù)集benchmark data 中每幅圖片的平均運(yùn)行時(shí)間,來(lái)證明本文算法的實(shí)時(shí)性,實(shí)驗(yàn)結(jié)果如表2 所示.由表2可知,除了圖3(b)之外,其他圖片都是本文算法的運(yùn)行時(shí)間最短,最后一列是數(shù)據(jù)集中每幅圖片的平均運(yùn)行時(shí)間,可知本文算法的平均運(yùn)行時(shí)間是最短的.這是由于本文算法采用UWT 實(shí)現(xiàn)圖像分解,提取低頻部分的快速切比雪夫矩特征,并且采用PatchMatch 算法進(jìn)行匹配,可以縮短算法運(yùn)行時(shí)間,提高本文算法的實(shí)時(shí)性.

表2 3 種算法運(yùn)行時(shí)間的比較(單位:s)

最后我們比較了本文算法和文獻(xiàn)[5]和文獻(xiàn)[14] 在數(shù)據(jù)集benchmark data 中每幅圖片的平均誤匹配率(誤匹配對(duì)/匹配對(duì)),實(shí)驗(yàn)結(jié)果如表3 所示.由表3 可知,本文算法的匹配對(duì)是最多的,誤匹配對(duì)是最少的,誤匹配率是最低的.這是因?yàn)橄啾容^文獻(xiàn)[5]的相似性匹配及文獻(xiàn)[14]的kd-tree 匹配,本文算法采用PatchMatch算法進(jìn)行匹配得到規(guī)則的偏移量,并且采用稠密線性擬合方法進(jìn)行后處理降低誤匹配,具有很好的匹配效果.

表3 3 種算法誤匹配率的比較

5 結(jié)論與展望

本文提出了一種低頻快速切比雪夫矩的篡改圖像檢測(cè)算法.利用非抽樣小波變換分解圖像并提取其低頻部分,對(duì)于重疊塊提取其快速切比雪夫矩特征,PatchMatch 算法匹配塊特征,最后剔除誤匹配并定位其篡改區(qū)域.相比之前算法,F達(dá)到了92.0%,分別提高了3.5%和1.5%,本文算法對(duì)于單區(qū)域、單區(qū)域多次以及多區(qū)域的篡改均有很好的定位結(jié)果,并且有效地降低了運(yùn)行時(shí)間,提高了算法的實(shí)時(shí)性,最后也降低了誤匹配率實(shí)現(xiàn)很好的匹配效果.后續(xù)工作將放在對(duì)篡改區(qū)域進(jìn)行旋轉(zhuǎn)、加噪、壓縮以及模糊等處理的檢測(cè)及精確定位上.