時空上下文編碼的視頻拷貝檢測*

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

(1.杭州電子科技大學 認知與智能計算研究所，浙江 杭州 310018；2.國網浙江省電力公司電力科學研究院，浙江 杭州 310014)

?

時空上下文編碼的視頻拷貝檢測*

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

(1.杭州電子科技大學 認知與智能計算研究所，浙江 杭州 310018；2.國網浙江省電力公司電力科學研究院，浙江 杭州 310014)

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

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

0 引 言

如今隨著網絡視頻共享的急速發展以及數字視頻的編輯、發送和拷貝變得越來越容易，數字版權保護遇到了新的挑戰。基于內容的視頻拷貝檢測利用了“視頻本身就是水印”的事實，越來越受到研究者的關注，基于內容的視頻拷貝檢測正在成為替代傳統的水印方法來應付數字視頻盜版和非法傳播等問題的重要技術。

基于內容的視頻拷貝檢測算法主要由兩個關鍵技術組成，即特征表示和視頻匹配。

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

視頻匹配方法主要分為兩類，即順序匹配[4]和幀融合匹配[5，6]。順序匹配的基本思路是兩個視頻片段直接幀到幀匹配。由于一個查詢序列通常比參考序列短得多，因此使用滑動窗口算法遍歷式進行序列匹配。順序匹配的主要缺點是與查詢序列匹配的所有可能的參考子序列眾多而導致較高計算復雜度。此外，序列匹配不能有效檢測和定位涉及丟幀的拷貝變換。而幀融合匹配算法的主要思想是通過每一個查詢幀在參考序列庫中搜索相似的參考幀列表，最后將參考幀列表融合并確定查詢序列是否為融合后的參考序列的拷貝。基于幀融合的匹配并沒有適當時間融合機制，因此拷貝片段很難被精確檢測和定位。

1 基于時空上下文編碼的視頻拷貝檢測

針對已有工作的不足，本文提出了一種編碼時空上下文信息的方法，利用這個編碼彌補詞袋模型在量化時丟失的上下文空間信息，同時加強關鍵幀在時間域中的描述信息。在空間上，主要通過以關鍵幀的中心為起點均勻的將空間劃分為k塊區域，根據這些區域包含的局部特征構建關鍵幀空間上下文描述信息，而在時域上，主要通過關鍵幀所在的時域范圍內的普通幀構建關鍵幀的時間上下文信息。

為了加速匹配，將時空上下文信息量化為二進制碼，并使用海明距離作為相似度評測方法，本文算法相比傳統的拷貝檢測算法具有較高拷的精度和速度，在TREVID—2009視頻庫上的實驗已證明該方法具有很好的效果。基于時空上下文編碼的視頻拷貝檢測框架如圖1所示。本文主要對時空上下文編碼的生成過程和序列匹配方法進行詳細講解。

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

2 時空上下文信息

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

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

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

2.1 量化策略

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

RP=P·R

(1)

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

B=sgn(RP)

(2)

式中 sgn(·)為一個應用于每一個維度的符號函數，即當值為正時返回1，當值為負時返回0。最后通過二進制碼向量即可獲得高維向量R的二進制碼。

2.2 上下文模型

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

(3)

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

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

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

wi=e-t‖Ic-Ii‖2

(4)

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

2.3 空間上下文

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

圖4 空間上下文Fig 4 Spatial context

1)計算局部特征中心：考慮到部分變換會改變原始幀的圖像中心，因此，計算局部特征所在的中心作為劃分k塊區域的中心。假設在特征提取完畢之后得到局部特征的位置坐標為f1(x1,y1)，f2(x2,y2)，…，fn(xn,yn)，則局部特征中心坐標fc(xc,yc)通過式(5)、式(6)計算獲得

(5)

(6)

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

2.4 時間上下文

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

圖5 時域上下文Fig 5 Temporal context

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

2.5 時空上下文編碼

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

3 關鍵幀索引

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

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

4 序列匹配

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

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

1)構建序列匹配矩陣

序列匹配矩陣用于描述參考視頻關鍵幀與查詢視頻關鍵幀的相似性匹配狀態。通過式(7)構建一個二維的序列匹配矩陣

(7)

(8)

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

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

dist(sn-1,sn)

(9)

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

5 實驗結果分析

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

5.1 參數選擇

本節將通過實驗結果分析，參數t、閾值T和閾值I在

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

不同取值下的實驗性能。為了簡化實驗，選取劃分的區塊數k=3，同時選取召回率與準確率作為評估標準。

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

圖8 參數t對性能的影響Fig 8 Impact of parameter t on characteristics

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

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

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

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

5.2 性能評估

為了驗證本算法具有較好的效果，將本文算法和其他算法的效果。文獻[8]中的算法是一種常見的視頻拷貝檢測算法。當t=0.25,T=20,I=3時，使用一些較難處理的拷貝變換下的查詢視頻，分別使用本算法和文獻[8]中的算法進行檢測，得到的評測效果對比直方圖如圖11所示。圖11表明，實驗結果中召回率與準確率明顯優于文獻[8]中的算法，說明本算法能夠對一些復雜的局部變換具有更好的魯棒性，這些局部變換改變了幀圖像的部分內容。

圖11 與文獻[8]的效果對比Fig 11 Effect comparison with references[8]

6 結 論

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

[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

國家自然科學基金青年基金資助項目(61202280，61202281)

TP 391

A

1000—9787(2016)11—0143—05

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