王榮波，陳 浩，孫小雪，張江豐

(1.杭州電子科技大學(xué) 認(rèn)知與智能計(jì)算研究所，浙江 杭州 310018；2.國網(wǎng)浙江省電力公司電力科學(xué)研究院，浙江 杭州 310014)

?

時(shí)空上下文編碼的視頻拷貝檢測(cè)*

王榮波1，陳 浩1，孫小雪1，張江豐2

(1.杭州電子科技大學(xué) 認(rèn)知與智能計(jì)算研究所，浙江 杭州 310018；2.國網(wǎng)浙江省電力公司電力科學(xué)研究院，浙江 杭州 310014)

基于內(nèi)容的視頻拷貝檢測(cè),目前最流行的方法是基于詞袋模型的關(guān)鍵幀內(nèi)容匹配方法。由于在空間上丟失了視覺詞匯的上下文信息，而在時(shí)域中，同樣丟失了關(guān)鍵幀時(shí)域上下文信息，此類方法的精度受到限制。針對(duì)這一問題，通過使用一個(gè)上下文模型用于計(jì)算視頻關(guān)鍵幀的空間上下文信息和時(shí)域上下文信息，同時(shí)將時(shí)空上下文信息量化成二進(jìn)制編碼，并通過海明距離實(shí)現(xiàn)快速的時(shí)空上下文驗(yàn)證。在TREVID—2009視頻集上的實(shí)驗(yàn)驗(yàn)證了該算法具有較高的效率與準(zhǔn)確性。

視頻拷貝檢測(cè)； 詞袋模型； 上下文編碼

0 引 言

如今隨著網(wǎng)絡(luò)視頻共享的急速發(fā)展以及數(shù)字視頻的編輯、發(fā)送和拷貝變得越來越容易，數(shù)字版權(quán)保護(hù)遇到了新的挑戰(zhàn)?；趦?nèi)容的視頻拷貝檢測(cè)利用了“視頻本身就是水印”的事實(shí)，越來越受到研究者的關(guān)注，基于內(nèi)容的視頻拷貝檢測(cè)正在成為替代傳統(tǒng)的水印方法來應(yīng)付數(shù)字視頻盜版和非法傳播等問題的重要技術(shù)。

基于內(nèi)容的視頻拷貝檢測(cè)算法主要由兩個(gè)關(guān)鍵技術(shù)組成，即特征表示和視頻匹配。

在現(xiàn)有的工作中使用的特征可以分為兩類，即全局特征和局部特征。全局特征一般是根據(jù)整個(gè)幀或整個(gè)剪輯片段的統(tǒng)計(jì)信息，因此，它們具有緊湊性和低計(jì)算復(fù)雜度的優(yōu)點(diǎn)，如Kim C等人[1]提出的簽名特征是基于幀圖像的全局統(tǒng)計(jì)特征的。然而全局特征不能有效處理更復(fù)雜的變換，如視頻后期處理時(shí)通常丟棄或替換原始幀或原始片段中的某個(gè)區(qū)域。相反，局部特征本質(zhì)上對(duì)這些保留部分原始內(nèi)容的變換具有抵抗性。在視頻拷貝檢測(cè)中使用的局部特征大多數(shù)是基于興趣點(diǎn)的檢測(cè)和局部描述子的計(jì)算，如SIFT,SURF,PCA—SIFT等。除了空間特征，時(shí)間特征也是視頻拷貝檢測(cè)時(shí)的重要特征，Shivakumar N等人[2]提出了利用視頻拍攝時(shí)間作為時(shí)間特征參與檢測(cè)，而Cheung S S等人[3]則使用關(guān)鍵幀的位置信息作為相似度計(jì)算的一個(gè)重要因素。同樣，時(shí)間差特征[1]和時(shí)間序特征[4]被用于視頻拷貝檢測(cè)。

視頻匹配方法主要分為兩類，即順序匹配[4]和幀融合匹配[5，6]。順序匹配的基本思路是兩個(gè)視頻片段直接幀到幀匹配。由于一個(gè)查詢序列通常比參考序列短得多，因此使用滑動(dòng)窗口算法遍歷式進(jìn)行序列匹配。順序匹配的主要缺點(diǎn)是與查詢序列匹配的所有可能的參考子序列眾多而導(dǎo)致較高計(jì)算復(fù)雜度。此外，序列匹配不能有效檢測(cè)和定位涉及丟幀的拷貝變換。而幀融合匹配算法的主要思想是通過每一個(gè)查詢幀在參考序列庫中搜索相似的參考幀列表，最后將參考幀列表融合并確定查詢序列是否為融合后的參考序列的拷貝?；趲诤系钠ヅ洳]有適當(dāng)時(shí)間融合機(jī)制，因此拷貝片段很難被精確檢測(cè)和定位。

1 基于時(shí)空上下文編碼的視頻拷貝檢測(cè)

針對(duì)已有工作的不足，本文提出了一種編碼時(shí)空上下文信息的方法，利用這個(gè)編碼彌補(bǔ)詞袋模型在量化時(shí)丟失的上下文空間信息，同時(shí)加強(qiáng)關(guān)鍵幀在時(shí)間域中的描述信息。在空間上，主要通過以關(guān)鍵幀的中心為起點(diǎn)均勻的將空間劃分為k塊區(qū)域，根據(jù)這些區(qū)域包含的局部特征構(gòu)建關(guān)鍵幀空間上下文描述信息，而在時(shí)域上，主要通過關(guān)鍵幀所在的時(shí)域范圍內(nèi)的普通幀構(gòu)建關(guān)鍵幀的時(shí)間上下文信息。

為了加速匹配，將時(shí)空上下文信息量化為二進(jìn)制碼，并使用海明距離作為相似度評(píng)測(cè)方法，本文算法相比傳統(tǒng)的拷貝檢測(cè)算法具有較高拷的精度和速度，在TREVID—2009視頻庫上的實(shí)驗(yàn)已證明該方法具有很好的效果?；跁r(shí)空上下文編碼的視頻拷貝檢測(cè)框架如圖1所示。本文主要對(duì)時(shí)空上下文編碼的生成過程和序列匹配方法進(jìn)行詳細(xì)講解。

圖1 基于時(shí)空上下文編碼的拷貝檢測(cè)框架Fig 1 Framework of video copy detection based on spatial-temporal contextual code

2 時(shí)空上下文信息

關(guān)鍵幀的上下文是關(guān)鍵幀在視頻中所處的周圍環(huán)境，它在視頻處理中的價(jià)值主要體現(xiàn)為在視頻處理應(yīng)用問題的解決過程中，上下文扮演者解決問題所需的信息和資源提供者的重要角色。當(dāng)前視頻拷貝檢測(cè)中，采用關(guān)鍵幀的內(nèi)容的集合表示一個(gè)視頻的方式，本來就丟失了關(guān)鍵幀的周圍環(huán)境信息，所以有必要把單個(gè)關(guān)鍵幀和它作用域中的普通幀同時(shí)加以考慮。

圖2 時(shí)空上下文編碼原理Fig 2 Principle of spatial-temporal contextual coding

通常上下文的選取是基于核心關(guān)鍵幀左右一定范圍進(jìn)行的，這個(gè)固定的范圍被稱為"窗口"。時(shí)空上下文編碼的生成過程如圖2所示。在空間上，通過關(guān)鍵幀內(nèi)容包含的局部特征生成一個(gè)體現(xiàn)關(guān)鍵幀內(nèi)容的上下文，在時(shí)域中，通過關(guān)鍵幀前后"窗口"內(nèi)的普通幀生成一個(gè)用于描述關(guān)鍵幀環(huán)境信息的時(shí)域上下文，接下來進(jìn)行詳細(xì)講解。

2.1 量化策略

接下來介紹如何將高維向量量化成二進(jìn)制碼，對(duì)于給定的高維向量R，首先通過公式(1)將其投影到低維空間Rp為

RP=P·R

(1)

式中 P為一個(gè)隨機(jī)生成且元素為1或-1的投影矩陣。然后，高維向量R的二進(jìn)制碼向量可以通過公式(2)得到

B=sgn(RP)

(2)

式中 sgn(·)為一個(gè)應(yīng)用于每一個(gè)維度的符號(hào)函數(shù)，即當(dāng)值為正時(shí)返回1，當(dāng)值為負(fù)時(shí)返回0。最后通過二進(jìn)制碼向量即可獲得高維向量R的二進(jìn)制碼。

2.2 上下文模型

對(duì)于給定的中心，通過其周圍的元素分布構(gòu)建用于描述該中心的上下文環(huán)境信息。其數(shù)學(xué)模型如下，定義周圍元素的集合為S、周圍元素特征向量集合為D={di|ei∈S}，則用于描述中心上下文環(huán)境的上下文向量可以定義為

(3)

式中 di和wi分別為周圍元素ei的特征向量和權(quán)重。

圖3 中心周圍元素分布Fig 3 Distribution of elements surrounding center

為了抵抗在各種變換下周圍元素的丟失，為每一元素賦予不同的權(quán)重。如圖3所示，根據(jù)周圍元素距離中心元素的距離為其分配重要性，權(quán)重wi定義如下

wi=e-t‖Ic-Ii‖2

(4)

式中 |‖lc-li‖為周圍元素ei與中心C之間的距離，直觀的說，分配較小的權(quán)重給距離中心較遠(yuǎn)的元素，分配較大的權(quán)重給距離中心較近的元素。參數(shù)t用于控制參與描述上下文信息的周圍元素的數(shù)量，即在時(shí)域上,控制核心關(guān)鍵幀左右范圍“窗口”的大小，在空間上控制包含內(nèi)容的多少。

2.3 空間上下文

在關(guān)鍵幀的SIFT特征提取完畢之后可以獲得每一關(guān)鍵幀中所有局部特征的基本信息(如位置、尺度、主方向、描述子等)，通過局部特征的位置信息計(jì)算出關(guān)鍵幀的中心并將圖像空間均勻的劃分為k塊區(qū)域，如圖4所示，最后為每塊區(qū)域計(jì)算上下文向量從而構(gòu)建關(guān)鍵幀空間上下文向量。

圖4 空間上下文Fig 4 Spatial context

1)計(jì)算局部特征中心：考慮到部分變換會(huì)改變?cè)紟膱D像中心，因此，計(jì)算局部特征所在的中心作為劃分k塊區(qū)域的中心。假設(shè)在特征提取完畢之后得到局部特征的位置坐標(biāo)為f1(x1,y1)，f2(x2,y2)，…，fn(xn,yn)，則局部特征中心坐標(biāo)fc(xc,yc)通過式(5)、式(6)計(jì)算獲得

(5)

(6)

2)計(jì)算空間上下文向量：在k塊區(qū)域劃分后，定義Sk和Dk={di|ei∈Sk}表示第k塊區(qū)域中的局部特征和SIFT描述子的集合。將每塊區(qū)域中的局部特征看成以中心分布的元素，SIFT描述子為元素的特征向量，通過式(3)可以計(jì)算出每一塊區(qū)域的上下文向量，最后將所有的Ek連接起來得到關(guān)鍵幀空間上下文向量ES=[E1E2…Ek…]。

2.4 時(shí)間上下文

時(shí)間上下文信息用于描述關(guān)鍵幀所在視頻中的上下文環(huán)境信息，如包含關(guān)鍵幀之前后的環(huán)境信息，這類信息對(duì)于關(guān)鍵幀的匹配有著重要作用。如何圖5所示，每個(gè)關(guān)鍵幀在時(shí)間域中都圍繞著眾多的普通幀，通過使用這些普通幀來構(gòu)建關(guān)鍵幀的時(shí)間上下文信息。下面詳細(xì)介紹時(shí)間上下文的具體步驟。

圖5 時(shí)域上下文Fig 5 Temporal context

定義關(guān)鍵幀A的前后普通幀的集合分別為Sb和Sf。特征向量的集合分別是Db={bi|fi∈Sb}和Df={bi|fi∈Sf},其中bi為普通幀fi使用詞袋模型統(tǒng)計(jì)的詞頻向量。通過公式(3)可以計(jì)算出關(guān)鍵幀A的前后上下文向量Eb和Ef。最后關(guān)鍵幀的時(shí)域上下文向量為ET=[EbEf]。在實(shí)驗(yàn)中，為了降低計(jì)算復(fù)雜度，每5幀選取一幀加入集合為Sb和Sf。

2.5 時(shí)空上下文編碼

在經(jīng)過2.3節(jié)和2.4節(jié)的計(jì)算之后獲得了關(guān)鍵幀的空間上下文向量ES和時(shí)間上下文向量ET。為了使時(shí)空上下文信息容易存儲(chǔ)和易于相似度計(jì)算，需要將上述高維向量量化成二進(jìn)制碼。本文使用2.1節(jié)中的量化方法對(duì)關(guān)鍵幀的空間上下文向量ES和時(shí)間上下文向量ET進(jìn)行量化分別得到空間上下文編碼BS和時(shí)間上下文編碼BT，最后將它們組合起來得到關(guān)鍵幀的時(shí)空上下文編碼BST=[BSBT]。在試驗(yàn)中，選取的時(shí)空上下文編碼的長度為256位。

3 關(guān)鍵幀索引

為了得到更精確的初始匹配和改善檢索性能，需要為海量的視頻關(guān)鍵幀建立索引。在使用詞袋模型之后，每一個(gè)關(guān)鍵幀都可以用一個(gè)給定的視覺詞典統(tǒng)計(jì)的詞頻向量表示。因此，以該詞頻向量為依據(jù)，使用局部敏感哈希算法[7]將關(guān)鍵幀投影到不同的桶中，以此為視頻庫關(guān)鍵幀建立索引。由于只有相似的關(guān)鍵幀才能被投影到同一個(gè)桶中，因此在相似性關(guān)鍵幀查詢時(shí)可以明顯提高效率，如圖6所示，索引結(jié)構(gòu)中的每一項(xiàng)包含關(guān)鍵幀編號(hào)和時(shí)空上下文編碼。

圖6 局部敏感哈希投影Fig 6 Projection by local sensitive Hash

4 序列匹配

序列匹配的目的在于通過給定的查詢視頻在參考視頻中定位其拷貝片段。本文提出一種基于最長公共子序列的合算法對(duì)拷貝的片段進(jìn)行定位。圖7說明了一個(gè)簡單的例子。該過程主要由兩個(gè)步驟分別是構(gòu)建序列匹配矩陣和子序列融合，接下來詳細(xì)講解兩個(gè)步驟。

圖7 序列匹配例子Fig 7 Example of sequence matching

1)構(gòu)建序列匹配矩陣

序列匹配矩陣用于描述參考視頻關(guān)鍵幀與查詢視頻關(guān)鍵幀的相似性匹配狀態(tài)。通過式(7)構(gòu)建一個(gè)二維的序列匹配矩陣

(7)

(8)

2)最長公共子序列融合算法

在序列匹配矩陣構(gòu)建完畢后，使用最長公共子序列算法查找出一個(gè)最長的匹配序列S=(s1,s2,s3,…,sn)，其中，sn是一個(gè)連續(xù)的子序列。最后通過式(9)計(jì)算S中兩個(gè)連續(xù)的子序列之間的間隔大小來決定是否需要融合，從而獲得一個(gè)最長的連續(xù)序列。

dist(sn-1,sn)

(9)

式中 dist(sn-1,sn)為子序列sn-1和sn之間的間隔大小，I為一個(gè)給定的閾值，算法思想如表1所示。

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

為了驗(yàn)證本文提出的基于上下文編碼的視頻拷貝檢測(cè)方法的有效性，本文對(duì)400段參考視頻及其對(duì)應(yīng)的拷貝視頻進(jìn)行測(cè)試實(shí)驗(yàn)。本文使用的測(cè)試視頻均來自TRECVID—2009視頻庫。查詢視頻是隨機(jī)從400段參考視頻中截取的200個(gè)60 s的視頻片段，分別進(jìn)行模糊、縮放、亮度改變、高斯噪聲、圖中圖、平移，改變幀率以及嵌入字幕8種方式進(jìn)行攻擊，共產(chǎn)生1 200段拷貝視頻用于拷貝檢測(cè)。

5.1 參數(shù)選擇

本節(jié)將通過實(shí)驗(yàn)結(jié)果分析，參數(shù)t、閾值T和閾值I在

表1 最長公共子序列融合算法

不同取值下的實(shí)驗(yàn)性能。為了簡化實(shí)驗(yàn)，選取劃分的區(qū)塊數(shù)k=3，同時(shí)選取召回率與準(zhǔn)確率作為評(píng)估標(biāo)準(zhǔn)。

式(4)中參數(shù)t對(duì)性能的影響如圖8所示，當(dāng)t取值很小時(shí)，較少的空間上下文信息被記錄，然而當(dāng)t取值很大時(shí)，較多嘈雜的空間上下文信息被包括。正如圖8所示，在t=0.25時(shí)可以獲得最佳的性能。

圖8 參數(shù)t對(duì)性能的影響Fig 8 Impact of parameter t on characteristics

圖9顯示時(shí)空上下文編碼受不同閾值T取值的影響情況，可以觀察出當(dāng)T=20時(shí)具有較好的查詢效果，召回率與準(zhǔn)確率均在90 %以上，表明本文算法能夠滿足使用要求。

圖9 閾值T對(duì)性能的影響Fig 9 Impact of threshold T on characteristics

圖10顯示了基于最長公共子序列的融合方法受到不同閾值I的影響情況，當(dāng)I較小時(shí)，很多正確的子序列無法被合并，當(dāng)I叫大時(shí)，很多干擾子序列被合并，可以觀察出當(dāng)I=3時(shí)具有較好的性能。

圖10 閾值I對(duì)性能的影響Fig 10 Impact of threshold I on characteristics

5.2 性能評(píng)估

為了驗(yàn)證本算法具有較好的效果，將本文算法和其他算法的效果。文獻(xiàn)[8]中的算法是一種常見的視頻拷貝檢測(cè)算法。當(dāng)t=0.25,T=20,I=3時(shí)，使用一些較難處理的拷貝變換下的查詢視頻，分別使用本算法和文獻(xiàn)[8]中的算法進(jìn)行檢測(cè)，得到的評(píng)測(cè)效果對(duì)比直方圖如圖11所示。圖11表明，實(shí)驗(yàn)結(jié)果中召回率與準(zhǔn)確率明顯優(yōu)于文獻(xiàn)[8]中的算法，說明本算法能夠?qū)σ恍?fù)雜的局部變換具有更好的魯棒性，這些局部變換改變了幀圖像的部分內(nèi)容。

圖11 與文獻(xiàn)[8]的效果對(duì)比Fig 11 Effect comparison with references[8]

6 結(jié) 論

在本文中，提出了一種使用上下文編碼來表征關(guān)鍵幀時(shí)空上下文信息的算法，通過將其與詞袋模型配合使用，使其在查詢時(shí)具有更快的速度且存儲(chǔ)時(shí)需要更小的存儲(chǔ)空間，在標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了該算法的有效性。在今后的工作中，將尋找一種更精確的關(guān)鍵幀提取方法以減少關(guān)鍵幀數(shù)量，同時(shí)檢索性能得以保留。

[1] Kim C,Vasudev B.Spatiotemporal sequence matching for efficient video copy detection[J].IEEE Transactions on Circuits and Systems for Video Technology,2005,15(1):127-132.

[2] Shivakumar N.Detecting digital copyright violations on the internet[D].Stanford:Stanford University,1999.

[3] Cheung S S,Zakhor A.Efficient video similarity measurement with video signature[J].IEEE Transactions on Circuits and Systems for Video Technology,2003,13(1):59-74.

[4] Chen L,Stentiford F W M.Video sequence matching based on temporal ordinal measurement[J].Pattern Recognition Letters,2008,29(13):1824-1831.

[5] Kim H,Lee J,Liu H,et al.Video linkage:Group-based copied video detection[C]∥Proceedings of 2008 International Confe-rence on Content-based Image and Video Retrieval,ACM,2008:397-406.

[6] Wei S,Zhao Y,Zhu C,et al.Frame fusion for video copy detec-tion[J].IEEE Transactions on Circuits and Systems for Video Technology,2011,21(1):15-28.

[7] Datar M,Immorlica N,Indyk P,et al.Locality-sensitive hashing scheme based on p-stable distributions[C]∥Proceedings of the Twentieth Annual Symposium on Computational Geometry,ACM,2004:253-262.

[8] Zhao W L,Wu X,Ngo C W.On the annotation of web videos by efficient near-duplicate search[J].IEEE Transactions on Multimedia,2010,12(5):448-461.

陳 浩，通訊作者，E—mail：norvinq@163.com。

Video copy detection based on spatial-temporal contextual code*

WANG Rong-bo1,CHEN Hao1,SUN Xiao-xue1,ZHANG Jiang-feng2

(1.Institute of Cognitive and Intelligent Computing,Hangzhou Dianzi University,Hangzhou 310018,China;2.State Grid Research Institute of Electric Power,Hangzhou 310014,China)

The most popular approach for content-based video copy detection is based on bag-of-visual-words model with invariant local features.Due to the neglect of the spatial context information and the temporal context information,these methods are limited.An algorithm of representing the spatial and temporal context information of key frames quantified into binary codes,and spatial-temporal verification is quickly achieved by Hamming distance.Experiments on TREVID—2009 video set demonstrate the proposed algorithm has high efficiency and accuracy.

video copy detection;bag-of-visual-words;contextual code;

10.13873/J.1000—9787(2016)11—0143—05

2016—02—22

國家自然科學(xué)基金青年基金資助項(xiàng)目(61202280，61202281)

TP 391

A

1000—9787(2016)11—0143—05

王榮波(1978-)，男，浙江義烏人，博士，副教授，CCF會(huì)員，從事自然語言處理、篇章分析研究工作。