盧賀楠, 黃添強(qiáng), 林 晶

1(福建師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 福州 350007)2(福建省公共服務(wù)大數(shù)據(jù)挖掘與應(yīng)用工程技術(shù)研究中心, 福州 350007)3(福建師范大學(xué) 軟件學(xué)院, 福州 350007)4(大數(shù)據(jù)分析與應(yīng)用福建省高校工程研究中心, 福州 350007)

基于動(dòng)態(tài)閾值的幀復(fù)制粘貼篡改檢測(cè)①

盧賀楠1,2,4, 黃添強(qiáng)2,3,4, 林 晶1,2,4

1(福建師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 福州 350007)2(福建省公共服務(wù)大數(shù)據(jù)挖掘與應(yīng)用工程技術(shù)研究中心, 福州 350007)3(福建師范大學(xué) 軟件學(xué)院, 福州 350007)4(大數(shù)據(jù)分析與應(yīng)用福建省高校工程研究中心, 福州 350007)

幀復(fù)制粘貼是一種常見(jiàn)的時(shí)域篡改方式, 篡改者采用這種方式來(lái)移除視頻中某段內(nèi)容, 如犯罪現(xiàn)場(chǎng)、犯罪證據(jù)等. 針對(duì)這種篡改, 已經(jīng)有不少方案被提出, 但是它們有兩個(gè)缺點(diǎn): 一采用固定的閾值; 二時(shí)間復(fù)雜度很高. 大部分被篡改視頻會(huì)經(jīng)過(guò)再壓縮處理, 由于視頻壓縮基本是有損壓縮, 可能會(huì)導(dǎo)致固定閾值失去應(yīng)有作用.因此, 本文提出一種基于動(dòng)態(tài)閾值的被動(dòng)取證算法, 來(lái)增強(qiáng)算法的魯棒性, 并且通過(guò)引入字典排序算法來(lái)縮小幀匹配時(shí)的搜索范圍, 成功降低了時(shí)間復(fù)雜度. 文章采用精確度、召回率和平均每幀計(jì)算時(shí)間來(lái)對(duì)提出算法的性能進(jìn)行評(píng)估, 結(jié)果表明本算法在這三方面都優(yōu)于其他算法, 而且具有更好的魯棒性.

幀復(fù)制粘貼; 視頻取證; 時(shí)域篡改; 動(dòng)態(tài)閾值; 結(jié)構(gòu)相識(shí)性系數(shù)

視頻已經(jīng)廣泛應(yīng)用于新聞報(bào)道、安全監(jiān)控、法庭證據(jù)等各個(gè)領(lǐng)域, 與圖片相比, 視頻傳遞信息更直觀、生動(dòng). 然而, 近年來(lái)視頻編輯技術(shù)發(fā)展迅速, 編輯軟件種類(lèi)多樣并且容易使用, 非專(zhuān)業(yè)人員也能實(shí)現(xiàn)視頻篡改, 而且不遺留任何人眼可見(jiàn)的篡改痕跡. 數(shù)字媒體作為當(dāng)今信息傳播的主要媒介, 如果視頻傳遞的信息不真實(shí), 有可能導(dǎo)致人們做出錯(cuò)誤的決定, 甚至?xí)o社會(huì)帶來(lái)不好的影響. 例如虛假的產(chǎn)品商業(yè)宣傳就會(huì)給購(gòu)物者帶來(lái)經(jīng)濟(jì)損失. 更危險(xiǎn)的是當(dāng)一段篡改后的視頻被用于法庭證據(jù)時(shí), 會(huì)照成嚴(yán)重的后果. 因此,最近十年, 視頻內(nèi)容完整性取證逐漸成為學(xué)者們熱門(mén)領(lǐng)域之一, 旨在研究探索視頻的處理歷史[1].

隨著研究的深入, 許多視頻篡改取證方案被提出. Wang和Farid發(fā)現(xiàn)一種刪幀指紋[2], 并利用它對(duì)采用固定GOP(Group of picture)組的MPEG格式視頻進(jìn)行雙重壓縮檢測(cè); 文獻(xiàn)[3]改進(jìn)了Wang等人的特征, 構(gòu)建兩種刪除指紋, 分別用來(lái)對(duì)采用固定GOP組的視頻和動(dòng)態(tài)GOP組的視頻進(jìn)行刪幀和插幀篡改檢測(cè); Stamm M C等人發(fā)現(xiàn)如果視頻采用可變的GOP, 則可以利用P幀預(yù)測(cè)誤差序列和其自身平滑處理后做差結(jié)果來(lái)進(jìn)行檢測(cè)[4]; Su等人采用運(yùn)動(dòng)補(bǔ)償邊緣效應(yīng)(motion compensated edge artifact, MCEA)來(lái)檢測(cè)刪幀篡改[5]; 而Dong等人探索相鄰兩個(gè)P幀MCEA的差異, 檢測(cè)視頻幀序列經(jīng)過(guò)雙重壓縮后其傅里葉變換域中是否存在波峰, 進(jìn)而判斷視頻是否經(jīng)過(guò)篡改[6]. 林等人提出一種基于紋理譜的時(shí)域篡改檢測(cè)算法, 通過(guò)計(jì)算紋理譜序列之間的相關(guān)系數(shù), 根據(jù)給定閾值定位視頻篡改位置[7]. 為實(shí)現(xiàn)視頻局部區(qū)域復(fù)制粘貼篡改檢測(cè), Hsu Chih-Chung等人提出一種基于模式噪聲的取證方案[8].

幀復(fù)制粘貼篡改是一種時(shí)域篡改方式, 針對(duì)這種篡改取證的研究已經(jīng)有不少成果[9-12], Wang等人[9]把幀序列劃分成若干個(gè)重疊的子序列, 利用存在復(fù)制粘貼關(guān)系的子序列的空間域和時(shí)間域的相似性, 來(lái)進(jìn)行篡改取證, 但是由于幀的數(shù)量, 特征提取時(shí)計(jì)算量很大. Subramanyam等人[10]利用HOG(Histogram of Oriented Gradients)特征進(jìn)行匹配, 可是高維的HOG數(shù)據(jù)導(dǎo)致算法很復(fù)雜. Lin等人[11]先利用時(shí)域相似性來(lái)進(jìn)行粗檢測(cè), 找到可疑的幀; 然后利用空間的相似性從可疑幀查找存在復(fù)制粘貼關(guān)系的幀序列. 文獻(xiàn)[9-11]采用的特征比較復(fù)雜, 導(dǎo)致算法計(jì)算量很大, 而且精確度不夠理想. 因此, Li等人[12]提出一種基于結(jié)構(gòu)相似度算法, 以測(cè)量的幀間相似度系數(shù)為指標(biāo)來(lái)進(jìn)行篡改檢測(cè), 該方法提高了檢測(cè)精度, 同時(shí)降低了時(shí)間復(fù)雜度. 但Li采用的是固定閾值, 對(duì)再壓縮操作比較敏感.

本文提出的算法為每一幀設(shè)定一個(gè)動(dòng)態(tài)閾值, 該閾值隨著當(dāng)前幀和它前后兩個(gè)相鄰幀相似度的變化而變化, 因此算法對(duì)再壓縮有很好的魯棒性. 此外算法引入字典排序算法, 縮小幀匹配過(guò)程中搜索范圍, 有效的降低時(shí)間復(fù)雜度.

1 結(jié)構(gòu)相似度系數(shù)

在傳輸和解壓過(guò)程中, 數(shù)字圖像不可避免的發(fā)生不同程度的扭曲、失真現(xiàn)象, 不僅會(huì)影響視覺(jué)欣賞而且影響圖像傳遞信息的真實(shí)性. 為了得到較好質(zhì)量的圖片, 需要對(duì)接收的圖像進(jìn)行質(zhì)量評(píng)估, 來(lái)優(yōu)化傳輸系統(tǒng). 圖像的質(zhì)量評(píng)估工作過(guò)于繁重, 由觀察員來(lái)進(jìn)行主觀評(píng)價(jià)代價(jià)高而且浪費(fèi)時(shí)間. Wang Zhou等人[13]根據(jù)人眼視覺(jué)特征提出結(jié)構(gòu)相似度系數(shù)(structural similarity (SSIM) index)作為圖像質(zhì)量評(píng)估的指標(biāo). 該指標(biāo)性與主觀評(píng)價(jià)有很好的一致性, 而且計(jì)算簡(jiǎn)單,已經(jīng)廣泛應(yīng)用于圖像處理等領(lǐng)域.

SSIM系數(shù)是衡量?jī)煞鶊D像相似度的指標(biāo), 其值越大表示圖像越相似, 最大值為1. SSIM系數(shù)的計(jì)算分為三個(gè)部分: 亮度比較函數(shù)l(x,y)的計(jì)算, 如式(1), 對(duì)比度比較函數(shù)c(x,y)的計(jì)算, 如式(2), 以及結(jié)構(gòu)比較函數(shù)s(x,y)的計(jì)算, 如式(3). 三者合并得到兩幅圖像全局相似度SSIM系數(shù). 假設(shè)x、y分別代表原始圖像和接收的圖像, 兩者的SSIM系數(shù)計(jì)算如下:

其中,μx、σx分別是x圖像的均值和方差,μy、σy分別是y圖像的均值和方差,δxy表示兩幅圖像的協(xié)方差.C1、C2、C3是用來(lái)防止分母約等于0的情況下產(chǎn)生不可預(yù)知的事件的發(fā)生, 即使計(jì)算結(jié)果更穩(wěn)定.一般情況,是非常小的常數(shù),L為像素最大值.α、β、γ, 是用來(lái)調(diào)整三個(gè)分量相對(duì)重要性的參數(shù). 為使計(jì)算更簡(jiǎn)單, Wang Zhou等人設(shè)定α=β=γ=1, 得到一個(gè)特殊的SSIM系數(shù)計(jì)算式(5).

在實(shí)際應(yīng)用中, 圖片被分割成若干個(gè)11╳11像素大小的窗口, 用式(5)計(jì)算兩幅圖像中所有對(duì)應(yīng)窗口的SSIM系數(shù), 取平均得到平均的SSIM系數(shù), 定義如式(6), 其中N是局部窗口總數(shù),i是局部窗口序號(hào).

2 篡改檢測(cè)算法

一個(gè)視頻經(jīng)過(guò)幀復(fù)制粘貼篡改, 它的幀序列中至少包含一個(gè)復(fù)制粘貼幀序列片段, 而兩個(gè)幀序列片段之間如果存在復(fù)制粘貼關(guān)系, 那么它們的幀之間相似度會(huì)很高. 基于這個(gè)思想, 所提算法用式(6)計(jì)算兩幀之間的MSSIM系數(shù), 并以此結(jié)果作為判定兩幀之間存在復(fù)制粘貼關(guān)系的主要依據(jù). 算法的第一步是為每一幀設(shè)定一個(gè)閾值, 與幀匹配過(guò)程中計(jì)算的MSSIM系數(shù)作比較, 進(jìn)而確定兩幀是否存在復(fù)制粘貼關(guān)系.本文算法與其他算法相比, 主要優(yōu)勢(shì)在于設(shè)定的閾值是動(dòng)態(tài)的, 對(duì)視頻再壓縮有很強(qiáng)的魯棒性. 閾值設(shè)定后, 通過(guò)與計(jì)算得到的兩幀之間的MSSIM系數(shù), 把幀分為存在復(fù)制粘貼關(guān)系的和不存在復(fù)制粘貼關(guān)系的幀對(duì). 算法最后一步是剔除誤檢的幀對(duì), 同時(shí)找到漏檢的幀對(duì), 然后把它們按視頻中的順序排列, 并利用視頻內(nèi)容連續(xù)性的特點(diǎn), 給出原始序列和復(fù)制粘貼序列.由上述可知, 本文算法可以分成三部分, 其框圖如圖1所示.

圖1 算法框圖

2.1 閾值設(shè)定

根據(jù)視像編碼標(biāo)準(zhǔn)[14]可知, 視頻中每一幀在編碼過(guò)程中都會(huì)經(jīng)過(guò)DCT(Discrete Cosine Transform, DCT)變換和量化操作, 量化操作使得DCT系數(shù)由浮點(diǎn)數(shù)轉(zhuǎn)變?yōu)檎麛?shù), 兩者之間的差值被稱(chēng)為量化誤差[15,16],重構(gòu)幀圖像時(shí)又有反DCT變換和反量化操作, 反量化使得反DCT變換系數(shù)轉(zhuǎn)變?yōu)檎麛?shù), 同時(shí)把不在[0,255]范圍內(nèi)的系數(shù)強(qiáng)制轉(zhuǎn)為0或255[16]. 幀圖像編碼和重構(gòu)過(guò)程中都有數(shù)據(jù)丟失, 整個(gè)過(guò)程不可逆, 而且這種現(xiàn)象在全部視像編碼過(guò)程中都存在, 從而導(dǎo)致兩幀間的相似度隨著兩幀間隔距離的增加而降低. 為了展現(xiàn)這個(gè)結(jié)論, 我們來(lái)做一個(gè)實(shí)驗(yàn). 首先, 選取一個(gè)原始視頻, 視頻背景靜止并且沒(méi)有任何運(yùn)動(dòng)目標(biāo), 測(cè)量第90幀和視頻中所有幀之間的MSSIM系數(shù), 結(jié)果如圖2.然后對(duì)該視頻進(jìn)行幀復(fù)制粘貼篡改, 為方便對(duì)比, 我們把83～120的幀序列復(fù)制粘貼到196～233的位置, 篡改后的視頻幀序列中第90幀和第203幀之間存在復(fù)制粘貼關(guān)系, 同樣測(cè)量第90幀和篡改后視頻的所有幀之間的MSSIM系數(shù), 結(jié)果如圖3.

圖2 原始視頻幀序列第90幀和所有幀之間的MSSIM系數(shù)變換趨勢(shì)

圖3 篡改視頻幀序列第90幀和所有幀之間的MSSIM系數(shù)變換趨勢(shì)

圖2 展示的是MSSIM的值隨著兩幀之間距離的增加的變換趨勢(shì), 我們發(fā)現(xiàn)隨著間隔距離的增加, 兩幀間相似度整體表現(xiàn)為下降的趨勢(shì). 雖然有一些輕微的波動(dòng), 但總體是下降的趨勢(shì), 并且下降速度先快后慢. 由圖3可知存在復(fù)制粘貼關(guān)系的幀之間的相似度很高, 同時(shí)從中可以發(fā)現(xiàn)第90幀和第203幀之間的MSSIM系數(shù)并沒(méi)有達(dá)到1, 這是因?yàn)橐曨l篡改后進(jìn)行了二次壓縮, 使得兩幀之間的相似度降低了.

此外, 第90幀和第203幀之間的MSSIM系數(shù)高于第90幀和它的兩個(gè)相鄰幀(89幀和91幀)的MSSIM系數(shù). 為證明這一現(xiàn)象在視頻幀序列中普遍存在, 50段不同視頻的幀序列被用來(lái)做進(jìn)一步的實(shí)驗(yàn). 假設(shè)幀Pi和幀Pj存在復(fù)制粘貼關(guān)系, 幀Pi是原始幀V1是幀Pi和幀Pj之間的MSSIM系數(shù),V2是幀Pi和幀Pi+1之間的MSSIM系數(shù),V3是幀Pi和幀Pi-1之間的MSSIM系數(shù). 分別計(jì)算每個(gè)視頻相應(yīng)的V1、V2、V3,部分結(jié)果如表1. 用事件A表示:V1是最大的; 用事件B表示:V1介于V2和V3; 用事件C表示:V1是最小的.

表1 部分實(shí)驗(yàn)結(jié)果

從表中數(shù)據(jù)可知: 事件A經(jīng)常發(fā)生, 事件B偶爾發(fā)生, 事件C一次也沒(méi)發(fā)生. 因?yàn)槲覀冏鰧?shí)驗(yàn)所用視頻數(shù)目很少, 不能因此而得出事件C不可能發(fā)生這一結(jié)論, 但可以得出事件C發(fā)生的概率很小. 因此可以取V2、V3中較小的一個(gè)作為幀Pi的閾值來(lái)尋找與它有復(fù)制粘貼關(guān)系的幀.

在許多篡改取證算法中, 設(shè)定閾值是一個(gè)關(guān)鍵問(wèn)題, 也是一個(gè)難點(diǎn). Lin等人[11]和Li等人[12]采用固定參數(shù)作為判定閾值. 由上文分析知: 二次壓縮操作會(huì)降低復(fù)制粘貼幀之間的相似度, 繼而影響設(shè)定的固定閾值的效果, 使得算法的精確度降低. 圖4展示一個(gè)篡改視頻經(jīng)過(guò)不同比率的二次壓縮后, 所有相鄰幀的MSSIM系數(shù)平均值的變化趨勢(shì), 二次壓縮率為0%、10%、20%、……、90%, 在圖中的編號(hào)依次為1, 2, 3, ……, 10. 圖4表明相鄰幀相似度值會(huì)隨著壓縮率的增加而降低. 因此, 采用固定閾值的算法針對(duì)二次壓縮的魯棒性較弱.

圖4 幀間相似度隨著壓縮率增加的變化趨勢(shì)

針對(duì)這個(gè)問(wèn)題, 本文給出一種動(dòng)態(tài)閾值設(shè)定方法.根據(jù)上述實(shí)驗(yàn)可知: 可以取當(dāng)前幀與其前后兩個(gè)相鄰幀之間MSSIM系數(shù)中較小的一個(gè)為當(dāng)前幀的判定閾值, 即為每一幀設(shè)定一個(gè)閾值, 且閾值由該幀本身和它相鄰的幀決定. 詳細(xì)步驟如下.

T1. 第一步, 視頻轉(zhuǎn)換為幀序列:F1、F2、……、Fi、……、Fn,n是幀的總數(shù), 然后把每一幀轉(zhuǎn)換為灰度圖像, 得到灰度圖像序列:P1、P2、……、Pi、……、Pn.

T2. 第二步, 為每一幀設(shè)定一個(gè)判定閾值. 用Ti表示幀Pi的閾值. 分別計(jì)算Pi和Pi+1之間的MSSIM系數(shù),Pi和Pi-1之間的MSSIM系數(shù), 取兩者中較小的為Pi的判定閾值.

T3. 最后, 計(jì)算所有閾值的平均值E和方差D, 根據(jù)式(7)更新每一幀的閾值.

步驟T3中更新閾值操作很關(guān)鍵, 不能省略. 因?yàn)閷?duì)某一段視頻進(jìn)行檢測(cè)之前, 我們無(wú)法預(yù)測(cè)視頻經(jīng)過(guò)什么方式的處理, 也不清楚視頻內(nèi)容以及場(chǎng)景的變換規(guī)律, 但是我們要盡可能的把對(duì)算法有影響的因素都考慮到. 例如, 視頻中的場(chǎng)景快速變換; 一個(gè)快速移動(dòng)目標(biāo)進(jìn)入視頻; 有復(fù)制粘貼篡改操作等. 我們用圖5來(lái)解釋剛給出的三種狀況帶來(lái)的問(wèn)題. 假設(shè)第一種或第二種狀況發(fā)生在圖中的第三幀, 那么從第二幀圖片到第三幀圖片, 兩者的內(nèi)容發(fā)生了明顯的變化, 兩幀的相似度會(huì)急劇下降, 即兩幀的MSSIM系數(shù)很小. 如果3、4、5幀是從視頻中其他位置復(fù)制粘貼得到的, 那么第二幀和第三幀的MSSIM系數(shù)也很小, 因?yàn)檫@時(shí)兩者之間的內(nèi)容也存在明顯的差異. 考慮到這些狀況可能會(huì)發(fā)生, 為剔除步驟T2中可能存在的較小閾值,必須用式(7)對(duì)閾值進(jìn)行更新. 因?yàn)槟硯撝翟叫? 則找到的與該幀存在復(fù)制粘貼關(guān)系的可疑幀會(huì)越多(原因?qū)⒃谙乱还?jié)說(shuō)明), 從而增加算法計(jì)算量, 而且使得后處理更加困難, 降低了算法的效率.

圖5 部分視頻幀序列

2.2 幀匹配

在Lin等人和Li等人提出的方案中, 都先把整個(gè)視頻幀序列分割成若干個(gè)重疊的子序列, 再進(jìn)行幀間相似度測(cè)量. 子序列分割方式如圖6所示. 假設(shè)幀總數(shù)為n, 子序列的長(zhǎng)度為m, 則得到的子序列共有(n-m+1)個(gè). 每一個(gè)子序列都和其他子序列進(jìn)行相似度測(cè)量, 即使每?jī)蓚€(gè)子序列只進(jìn)行一次計(jì)算, 也需要進(jìn)行(n-m-1)(n-m)/2次, 隨著幀數(shù)目的增加, 計(jì)算量會(huì)快速增加.

圖6 子序列分割方式

為了降低計(jì)算量, 本算法引入字典排序算法. 字典排序能有效的把相似度較高圖片排序放在距離較近的地方, 而且簡(jiǎn)潔迅速. 字典排序?qū)μ崛〉奶卣鬏^為敏感, 本方案采用圖像DCT變換后系數(shù)作為特征, 為減少特征向量的維數(shù), 只取DCT系數(shù)Zig-Zag排序后的前十個(gè)系數(shù)作為每一幀的特征向量. 詳細(xì)步驟如下:

T1. 提取每一幀圖像的特征向量. 對(duì)灰度圖像序列:P1,P2, …,Pi, …,Pn中的每一幀進(jìn)行DCT變換,得到n個(gè)DCT系數(shù)矩陣, 每個(gè)矩陣中的系數(shù)經(jīng)過(guò)Zig-zag排序后取前十個(gè)系數(shù)作為對(duì)應(yīng)幀的特征向量.定義M=[V1,V2,…,Vi,…,Vn], 其中Vi表示幀Pi的特征向量,n是幀的總數(shù).

T2. 對(duì)矩陣M進(jìn)行字典排序得到矩陣Morder.

T3. 根據(jù)字典排序的結(jié)果, 來(lái)搜索可能存在復(fù)制粘貼關(guān)系的幀對(duì), 這個(gè)過(guò)程稱(chēng)為幀匹配. 假設(shè)幀Pi在矩陣Morder中的第j行, 那么尋找與幀Pi存在復(fù)制粘貼關(guān)系的幀時(shí), 只需要檢測(cè)在[j-10,j)∪(j,j+10]范圍內(nèi)的幀. 計(jì)算幀Pi和在[j-10,j)∪(j,j+10]范圍內(nèi)所有幀之間的MSSIM系數(shù), 并與Pi的閾值Ti進(jìn)行比較. 如果幀Pk在[j-10,j)∪(j,j+10]范圍內(nèi), 且Pi和Pk兩者之間的MSSIM系數(shù)Tik大于閾值Ti, 則把幀對(duì)(Pi,Pk)放入集合C中.

引入字典排序后, 縮小了幀匹配時(shí)搜尋的范圍,每一幀在匹配的過(guò)程中只需要進(jìn)行20次相似度測(cè)量,n幀需要計(jì)算 20n次, 與Lin和Li等人的方案相比, 所提算法有效的減少計(jì)算次數(shù), 提高了方案的效率.

2.3 后處理

在2.2節(jié), 匹配結(jié)果中可能會(huì)發(fā)現(xiàn)有一幀對(duì)應(yīng)多幀的情況, 這是問(wèn)題(一), 導(dǎo)致這種現(xiàn)象的原因有三個(gè), 一是這一幀確實(shí)多次復(fù)制粘貼, 二是上文中討論的事件B和事件C至少有一個(gè)出現(xiàn)了, 三是特殊情況,這兩幀相似度確實(shí)很高, 但它們之間不存在復(fù)制粘貼關(guān)系; 此外, 在2.2節(jié)中采用字典排序算法來(lái)縮小搜索范圍, 雖然提高了方案效率, 但是同時(shí)帶來(lái)一個(gè)問(wèn)題.因?yàn)樽值渑判虿荒鼙ＷC把所有相似的幀都排序放在相距很近的位置, 即有可能存在一幀與Pi有復(fù)制粘貼關(guān)系, 但是經(jīng)過(guò)字典排序后, 這一幀不在[j-10,j)∪(j,j+10], 導(dǎo)致漏檢, 這是問(wèn)題(二).

為了解決問(wèn)題(一), 我們?cè)O(shè)計(jì)了一個(gè)分類(lèi)器, 分類(lèi)器由兩部分組成, 第一部分是用來(lái)消除由事件B和事件C發(fā)生造成的誤檢測(cè), 第二部分是用來(lái)排除特殊情況造成的誤檢測(cè). 第二部分的設(shè)計(jì)原理是利用了人眼視覺(jué)特征, 因?yàn)楸仨氝B續(xù)復(fù)制粘貼15幀, 人眼才能感覺(jué)到視頻內(nèi)容的變化, 所以可以認(rèn)為復(fù)制粘貼的幀序列長(zhǎng)度至少為15, 如果檢測(cè)到的幀序列長(zhǎng)度小于15,則判定是特殊現(xiàn)象帶來(lái)的誤差. 問(wèn)題(二)是通過(guò)檢測(cè)到的幀, 按幀序號(hào)一幀一幀向外擴(kuò)展解決的, 具體步驟如下.

T1. 分類(lèi)器第一部分定義如式(8), 其中i、j表示幀序號(hào). 集合C中所以幀對(duì)都要經(jīng)分類(lèi)器處理, 如果φ(Pi,Pj)=0, 則把幀對(duì)(Pi,Pj)從集合C中移除.

T2. 集合C中的幀對(duì)經(jīng)過(guò)分類(lèi)器處理后, 從C中任取一幀對(duì)(Pp,Pq), 把它放入集合S中, 并從C中移除. 記錄下當(dāng)前這兩幀的序號(hào), 令a=p,b=q.

T3. 檢測(cè)幀對(duì)(Pp+1,Pq+1)是否存在與集合C中, 如果存在, 則把它從C中移除, 放入S中, 令p=p+1,q=q+1, 跳轉(zhuǎn)至T3; 如果不存在, 跳轉(zhuǎn)至T4.

T4. 計(jì)算幀Pp+1和幀Pq+1兩者之間的SSIM系數(shù),如果它們的SSIM系數(shù)大于閾值Tp+1(Pp+1的閾值)或者Tq+1(Pq+1的閾值)其中一個(gè), 則令p=p+1,q=q+1, 并跳轉(zhuǎn)至T3; 否則, 把幀對(duì)(Pp+1,Pq+1))從集合S中刪除, 令p=a,q=b, 然后跳轉(zhuǎn)至T5.

T5. 檢測(cè)幀對(duì)(Pp-1,Pq-1)是否存在于集合C中,如果存在, 則把它從C中移除, 放入S中, 令p=p-1,q=q-1, 跳轉(zhuǎn)至T5; 如果不存在, 跳轉(zhuǎn)至T6.

T6. 計(jì)算幀Pp-1和幀Pq-1之間的SSIM系數(shù), 如果它們的SSIM系數(shù)大于閾值Tp-1或者Tq-1, 則令p=p-1,q=q-1, 跳轉(zhuǎn)至T5; 否則, 跳轉(zhuǎn)至T7.

T7. 統(tǒng)計(jì)集合S中幀對(duì)的總數(shù), 記Num, 分類(lèi)器的第二部分定義如公式(9). 如果U(S)=1, 則認(rèn)為當(dāng)前集合S中可以組成兩段存在復(fù)制粘貼關(guān)系的幀序列.假設(shè)幀兩段幀序列分別為Pi,Pi+1, … ,Pi+m和Pj,Pj+1, …,Pj+m. 根據(jù)復(fù)制粘貼序列和其粘貼位置連續(xù)性較弱的特點(diǎn)來(lái)判定原始幀序列和復(fù)制粘貼幀序列, 計(jì)算公式如(10)～(13). 如果MSSIMi+MSSIMi+m＞MSSIMj+MSSIMj+m,則Pi,Pi+1, …,Pi+m是原始序列,Pj,Pj+1, …,Pj+m是復(fù)制粘貼幀序列; 否則,Pj,Pj+1, …,Pj+m是原始幀序列,Pi,Pi+1, …,Pi+m是復(fù)制粘貼序列. 如果U(S)=0, 則清空集合S, 轉(zhuǎn)至T8.

T8. 重復(fù)步驟T2～T7, 直到C為空.

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

為完成實(shí)驗(yàn), 我們選取15段視頻, 其中包括5段分辨率為640×480的視頻、5段分辨率為720×576的視頻以及5段分辨率為1920×1080的視頻. 篡改視頻時(shí), 復(fù)制的幀序列長(zhǎng)度從15～150不等, 使用Adobe Premiere Pro CS5來(lái)篡改視頻, 使用Free Video compression來(lái)對(duì)視頻進(jìn)行壓縮, 電腦配置了3.20GHz的CPU, 運(yùn)行軟件為Matlab2012a.

3.1 算法評(píng)估參數(shù)

為評(píng)估本方案的性能, 我們統(tǒng)計(jì)了算法的精確度(precision)、召回率(recall)和計(jì)算時(shí)間三種參數(shù). 精確度和召回率是比較傳統(tǒng)的評(píng)估參數(shù), 已經(jīng)廣泛應(yīng)用于圖片相關(guān)檢查、分類(lèi)研究等領(lǐng)域. 精確度越高表明算法的檢測(cè)越準(zhǔn)確; 召回率越高表明算法的誤檢率很低.精確度和召回率的定義分別如式(14)(15),Nc表示正確檢測(cè)結(jié)果的數(shù)目,Nf是錯(cuò)誤檢測(cè)結(jié)果的數(shù)目,Nm是漏檢幀的數(shù)目.

此外, 計(jì)算時(shí)間也被用來(lái)作為算法評(píng)估的一個(gè)重要參數(shù), 本文采用是平均每一幀所花費(fèi)的時(shí)間.

3.2 實(shí)驗(yàn)結(jié)果

表2給出用于實(shí)驗(yàn)的15段視頻的詳細(xì)信息. 表3給出本文算法檢測(cè)的結(jié)果. 為了證明算法對(duì)二次壓縮有很強(qiáng)的魯棒性, 我們對(duì)篡改視頻進(jìn)行壓縮, 壓縮率分別為20%、50%以及90%, 然后用所提算法對(duì)壓縮后的視頻依次檢測(cè), 結(jié)果分別在表4、表5和表6中展示, 從實(shí)驗(yàn)結(jié)果可以知: 無(wú)論篡改視頻是否經(jīng)過(guò)壓縮,本文算法都能精確定位篡改幀序列.

表3結(jié)果顯示當(dāng)篡改者沒(méi)有對(duì)篡改視頻進(jìn)行二次壓縮時(shí), 算法檢測(cè)正確率達(dá)到100%, 無(wú)一幀漏檢. 原因是如果視頻篡改后不經(jīng)過(guò)壓縮, 那么存在復(fù)制粘貼關(guān)系的兩幀之間的相似度值是1, 而根據(jù)給出的閾值自適應(yīng)設(shè)定方法知, 閾值一定小于1, 這樣自然就不會(huì)出現(xiàn)漏檢現(xiàn)象.

表2 測(cè)試視頻

視頻11 321 1920×1080沒(méi)有篡改視頻12 300 1920×1080217-256 101-140視頻13 283 1920×108031-45 150-164視頻14 575 1920×1080123-201 363-441視頻15 293 1920×108083-120 196-233

表3 本文算法對(duì)沒(méi)有經(jīng)過(guò)二次壓縮視頻檢查結(jié)果

對(duì)比表3和表4發(fā)現(xiàn), 當(dāng)視頻二次壓縮率小于20%時(shí), 所提算法幾乎不受影響. 而由表5、表6可得,當(dāng)壓縮率達(dá)到50%時(shí), 結(jié)果偶爾出現(xiàn)漏檢現(xiàn)象, 如視頻9的幀對(duì)(164,342)、視頻14的幀對(duì)(123,363)未檢測(cè)到. 當(dāng)壓縮率達(dá)到90%時(shí), 漏檢現(xiàn)象就很普遍了, 如視頻3、5、7、9、10、13、14、15都出現(xiàn)漏檢情況, 但是我們發(fā)現(xiàn)漏檢的都是篡改幀序列的開(kāi)始1-2幀或者后面1-2幀, 這不影響算法對(duì)復(fù)制粘貼序列的定位. 此外, 本文算法對(duì)未篡改的視頻判定完全正確, 而且只有表6中視頻5的幀對(duì)(195,451)是誤檢測(cè)的, 說(shuō)明所提算法的誤檢率很低.

表4 算法對(duì)經(jīng)過(guò)二次壓縮率為20%的視頻檢測(cè)結(jié)果

視頻9 164-220 342-398 0.477視頻10 662-788 245-371 0.502視頻11 1920×1080沒(méi)有篡改 1.825視頻12 217-256 101-140 1.971視頻13 31-45 150-164 1.972視頻14 123-201 363-441 1.788視頻15 83-120196-233 1.984

表5 本文算法對(duì)經(jīng)過(guò)二次壓縮率為50%的視頻檢測(cè)結(jié)果

表6 本文算法對(duì)經(jīng)過(guò)二次壓縮率為90%的視頻檢測(cè)結(jié)果

3.3 算法對(duì)比

綜上所述, 本文提出的算法動(dòng)態(tài)設(shè)定閾值, 增強(qiáng)了算法的魯棒性, 同時(shí)采用字典排序算法, 有效的降低算法的計(jì)算量. 為說(shuō)明算法的有效性, 將從準(zhǔn)確度、召回率和計(jì)算時(shí)間三方面與文獻(xiàn)[12]所提算法進(jìn)行比較, 結(jié)果如表7.

表7 準(zhǔn)確度、召回率和計(jì)算時(shí)間比較

由表7可得, 文獻(xiàn)[12]給出的算法隨著二次壓縮率的增加, 算法準(zhǔn)確度和召回率都快速降低, 而無(wú)論視頻是否經(jīng)過(guò)二次壓縮, 本文所提算法的準(zhǔn)確度和召回率都沒(méi)有太大的波動(dòng), 并且都高于文獻(xiàn)[12]的算法. 結(jié)果證明本文算法對(duì)壓縮有很強(qiáng)的魯棒性.

表7最后一列給出每幀平均所花費(fèi)的時(shí)間, 平均時(shí)間計(jì)算方法: 首先, 分別計(jì)算分辨率為640×480, 720×576, 1920×1080的視頻每幀所用時(shí)間, 然后三者取平均. 相比文獻(xiàn)[12]的方法, 所提算法有效的降低了時(shí)間復(fù)雜度.

4 結(jié)語(yǔ)

本文提出一種新的幀復(fù)制粘貼篡改盲取證算法,該算法為每一幀設(shè)定一個(gè)閾值, 而且閾值是由當(dāng)前幀本身和它前后相鄰幀MSSIM系數(shù)決定, 隨著MSSIM系數(shù)的變化而動(dòng)態(tài)變化. 動(dòng)態(tài)閾值使得算法能很好的應(yīng)對(duì)不同強(qiáng)度的壓縮, 增強(qiáng)了算法的魯棒性. 而且所提算法引入了字典排序, 字典排序簡(jiǎn)單有效, 通過(guò)縮小幀匹配過(guò)程中的搜索范圍, 減少相似度計(jì)算的次數(shù),提高算法效率. 實(shí)驗(yàn)結(jié)果表明所提算法優(yōu)于文獻(xiàn)[12]中的算法.

相比已經(jīng)存在的算法, 所提算法時(shí)間效率有了較大提升, 但是隨著視頻分辨率的增加, 平均每幀所用時(shí)間也大幅增加, 為應(yīng)對(duì)視頻分辨率的增長(zhǎng), 研究并發(fā)現(xiàn)一個(gè)更簡(jiǎn)單、更有效的新特征來(lái)進(jìn)行視頻篡改檢測(cè)是我們未來(lái)工作的主要目標(biāo).

1 Milani S, Fontani M, Bestagini P, et al. An overview on video forensics. APSIPA Trans. on Signal and Information Processing, 2012, 1: e2.

2 Wang W, Farid H. Exposing digital forgeries in video by detecting double quantization. Proc. of the 11th ACM Workshop on Multimedia and Security, ACM MM&SEC. New York. ACM. 2009. 39–48.

3 Stamm MC, Lin W, Liu KJ. Temporal forensics and anti-forensics for motion compensated video. IEEE Trans. on Information Forensics and Security, 2012, 7(4): 1315–1329.

4 Stamm MC, Wu M, Liu KJR. Information forensics: An overview of the first decade. Access, IEEE, 2013,1: 167–200.

5 Su Y, Zhang J, Liu J. Exposing digital video forgery by detecting motion-compensated edge artifact. International Conference on Computational Intelligence and Software Engineering. Wuhan, China. IEEE. 2009.

6 Dong Q, Yang G, Zhu N. A MCEA based passive forensics scheme for detecting frame-based video tampering. Digital Investigation, 2012, 9(2): 151–159.

7 林新棋,林云枚,林志新,等.基于紋理譜的視頻幀間篡改檢測(cè).計(jì)算工程,2015,41(11):314–321.

8 Chih C, Htzu YH, Lin C, et al. Video forgery detection using correlation of noise residue. Multimedia Signal Processing, 2008 IEEE 10th Workshop on. Cairns. IEEE. 2008. 170–174.

9 Wang W, Hany F. Exposing digital forgeries in video bydetecting duplication. Proc. of the 9th Workshop on Multimedia & Security. New York. ACM. 2007. 35–42.

10 Subramanyam AV, Emmanuel S. Video forgery detection using HOG features and compression properties. 14th International Workshop on Multimedia Signal Processing (MMSP). Banff. IEEE. 2012. 89–94.

11 Lin G, Chang J. Detection of frame duplication forgery in videos based on spatial and temporal analysis. International Journal of Pattern Recognition and Artificial Intelligence, 2012, 26(7): 1250017.

12 Li F, Huang T. Video copy-move forgery detection and localization based on structural similarity. Proc. of the 3rd International Conference on Multimedia Technology, ICMT 2013. Springer Berlin Heidelberg. 2014. 63–76.

13 Wang Z, Bovik AC, Sheikh HR, et al. Image quality assessment: From error visibility to structural similarity. IEEE Trans. on Image Processing, 2004, 13(4): 600–612.

14 林福宗.多媒體技術(shù)基礎(chǔ).第3版.北京:清華大學(xué)出版社,2011.

15 Huang F, Huang J, Shi Y. Detecting double JPEG compression with the same quantization matrix. IEEE Trans. on Information Forensics and Security, 2010, 5(4): 848–856.

16 Yang J, Jin X, Zhu G, et al. An effective method for detecting double JPEG compression with the same quantization matrix. IEEE Trans. on Information Forensics and Security, 2014, 9(11): 1933–1942.

Frame Copy and Paste Tampering Detection Based on Dynamic Threshold

LU He-Nan1,2,4, HUANG Tian-Qiang2,3,4, LIN Jing1,2,412
(School of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350007, China) (Fujian Engineering Research Center of Public Service Big Data Mining and Application, Fuzhou 350007, China)34(School of Software, Fujian Normal University, Fuzhou 350007, China) (Fujian Provincial University Engineering Research Center of Big Data Analysis and Application, Fuzhou 350007, China)

Frame duplication forgery is a very common operation for video tampering in the temporal domain. By removing some frames which contain a crime scene or crime evidence, the forger can change the video content. A lot of solutions have been proposed for detecting this type of tempering operation. However, there are two disadvantages. The first one is fixed threshold; the other is huge computation. In general, frame duplication forgery and re-compression would be performed on a video at the same time. Since re-compression will cause data lost, the fixed thresholds may lose their effects. Therefore, an algorithm based on dynamic threshold is proposed in this paper, which can improve the robustness. Additionally, the proposed method adopts dictionary order algorithm to reduce the search scope of frame matching and the time complexity. Three performance indices: precision, recall and average computation time per frame are employed to evaluate our algorithm. The results demonstrate that the proposed method outperforms the existing methods in terms of precision, recall and computation time.

frame duplication; digital video forensics; temporal forgery; dynamic threshold; structural similarity index

2016-03-14;收到修改稿時(shí)間:2016-05-12

10.15888/j.cnki.csa.005499