郭丁云+薛峰+郭旦萍

摘要：針對基于鏡頭關(guān)鍵幀層次進行近重復(fù)視頻檢測耗時的問題，該文提出了一種新的視頻鏡頭的時序一致性特征，使用該特征對已有研究的級聯(lián)式近重復(fù)視頻檢測算法進行改進。首先在進行關(guān)鍵幀特征提取之前，在鏡頭層次利用鏡頭的時序一致性特征初步濾除掉一些完全不相同的視頻，然后再使用全局分塊顏色特征和SURF特征，并使用k-d樹型索引結(jié)構(gòu)來實現(xiàn)快速最近鄰檢測，最終逐步檢測與查詢視頻重復(fù)或近重復(fù)的視頻。通過在CC_WEB_VIDEO標準數(shù)據(jù)集上進行實驗，并與現(xiàn)有常用的三種方法比較，結(jié)果顯示本文方法的檢測效果更好，尤其對于那些畫面變化較大以及運動場景復(fù)雜的視頻更明顯。

關(guān)鍵詞：近重復(fù)視頻檢測；時序一致性特征；分塊顏色特征；加速魯棒特征；k-d樹型索引結(jié)構(gòu)

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2016）31-0160-04

Abstract： Given the existing near-duplicate video detection algorithms are processed by matching features directly in the key frame level， which is very time-consuming， this paper introduces a new cascaded near-duplicate video detection approach using the temporal consistency feature in the shot level to preliminarily filter out some dissimilar videos before extracting features， and combining global blocking color features and SURF feature. Then we use the k-d tree indexing structure to achieve fast detection speed and thus obtain the ultimate videos that are duplicated with the query video step by step. We have verified the approach by experimenting on the CC_WEB_VIDEO dataset， and compared the performance with the existing three commonly used methods. The analysis results show the proposed method can achieve better detection effect， especially for the videos with great frame changes and complex motion scenes.

Key words： Near-duplicate Video Detection； Temporal Consistency Feature； Blocking Color Feature； Speeded Up Robust Feature （SURF）； K-d Tree Indexing Structure

隨著各種視頻共享網(wǎng)站的普及以及多媒體技術(shù)的發(fā)展，互聯(lián)網(wǎng)上的視頻數(shù)量和種類飛速增長。視頻被大量傳播和復(fù)制造成了很多問題[1]，比如視頻盜版、視頻冗余等。文獻[2]曾指出在來自于社交網(wǎng)站上主要的24類查詢中存在著平均27%的重復(fù)，最大甚至達到93%。在視頻監(jiān)控領(lǐng)域，需要從成千上萬個海量視頻中找到用戶關(guān)心目標的視頻，比如穿藍色上衣的人，對大規(guī)模監(jiān)控視頻進行檢索必然花費很多精力和時間。在這個大背景下，有關(guān)視頻檢索和視頻摘要的研究開始如火如荼地開展起來[3-4]，針對如何在大規(guī)模視頻集中更加準確又快速地檢測出相同或相近的視頻或目標，在多媒體搜索和內(nèi)容分析中變得越來越重要。

目前現(xiàn)存的研究比較深入的近重復(fù)檢測算法大致如文獻[5]中所述。最常用的特征有全局特征、局部特征以及聯(lián)合這兩種特征的分層方法。全局特征中一般利用能夠簡單描述整個圖像顏色分布的顏色直方圖，局部特征主要描述圖像的區(qū)域特征，具有計算簡單、對局部遮擋和視覺變換魯棒性強的特點。在文獻[6]中提出了視頻直方圖這一新的全局簽名特征，來描述視頻中特征向量的分布情況。文獻[7]中由Wu Xiao等人提出了一種分層的方法，結(jié)合視頻的全局特征和局部特征進行一步步檢測，先濾除簡單場景的完全不相同的視頻，再利用局部特征檢測復(fù)雜場景的視頻。文獻[2]中Wu Xiao等人提出了一種結(jié)合視頻內(nèi)容和上下文信息的檢測方法，將全局簽名特征和局部關(guān)鍵點的內(nèi)容特征與視頻的時長、評論、縮略圖、訪問次數(shù)等上下文信息結(jié)合起來，以減少大量關(guān)鍵幀比較的計算量。總的來說，這些方法一般都是直接在所有關(guān)鍵幀圖像上提取特征，對于大規(guī)模視頻進行檢測，不僅會花費大量時間，還丟失了視頻本身在時間上的一致性信息。

基于以上分析，受文獻[7]啟發(fā)，本文首先根據(jù)視頻本身固有的時間一致性特征，提出一種新的計算視頻時序一致性特征的方法，對現(xiàn)有的級聯(lián)式檢測算法進行改進，首先在對視頻的關(guān)鍵幀圖像進行特征提取之前，先利用鏡頭的時序一致性特征在鏡頭層次初步濾除掉一些完全不相同的視頻，然后再使用全局分塊顏色特征和SURF特征一步步進行更精確的檢測，最后使用k-d樹型索引結(jié)構(gòu)來實現(xiàn)快速最近鄰檢測，得到與要檢測視頻相同或相似的視頻的子鏡頭和對應(yīng)的關(guān)鍵幀，最終逐步檢測與查詢視頻重復(fù)或近重復(fù)的視頻，具體框架如圖1所示。

1 本文算法

1.1 基于邊緣輪廓差值法進行鏡頭邊界檢測

要進行近重復(fù)視頻檢測和檢索，第一步就是要對視頻進行分解，先要進行鏡頭邊界檢測，找出視頻中不同鏡頭發(fā)生變換的位置，然后再進一步分解視頻為鏡頭片段。本文中采用的是邊緣輪廓差值法進行鏡頭邊界檢測，具體實現(xiàn)步驟在文獻[8]中已有詳細說明，在此不再贅述。

1.2 基于幀差歐式距離法進行關(guān)鍵幀提取

對視頻進行匹配檢測可以看作是對靜態(tài)圖像進行匹配檢測，因此在進行鏡頭邊界檢測之后就可以提取各鏡頭中的關(guān)鍵幀圖像，然后進行圖像的特征提取和比較。本文采用的是基于幀差的歐式距離法來提取各個子鏡頭中的關(guān)鍵幀，在文獻[8]中已有詳細說明。

1.3 基于視頻鏡頭連續(xù)一致性的時序特征

考慮到視頻本身的特征，因為視頻是由很多連續(xù)時間上的靜態(tài)幀圖像組成的，因此相鄰的幀圖像之間必然在內(nèi)容上存在特別強烈的相關(guān)性，每個鏡頭中提取的關(guān)鍵幀應(yīng)該也存在這樣的相關(guān)性，而不同視頻的鏡頭和視頻中不會具有相同的時序一致性。本文中利用這一時序性質(zhì)，提出了一種新的計算時序一致性特征的方法來表示視頻鏡頭，在提取關(guān)鍵幀的顏色特征之前，直接在鏡頭層次上比較，提取出關(guān)鍵幀集中的時間切片特征，快速濾除無關(guān)視頻，時序一致性特征的生成如圖2所示。

具體實現(xiàn)步驟如下：

（1）首先提取出待檢測視頻與視頻庫中所有視頻的鏡頭中的關(guān)鍵幀并統(tǒng)計其數(shù)目，按照時間順序?qū)⒚總€關(guān)鍵幀圖像分為九塊，并計算中間塊的顏色特征；

（2）將每個鏡頭中的關(guān)鍵幀圖像中間塊的顏色特征構(gòu)成一個矩陣，可以計算得知該矩陣的行數(shù)為關(guān)鍵幀數(shù)目，而列數(shù)為36，這即可作為該鏡頭中的時序一致性特征；

（3）將待檢測視頻各鏡頭的時序一致性特征作為待檢測特征，分別與視頻集中所有鏡頭的時序特征進行比較，在這里采用余弦相似性作為比較指標；

（4）將比較所得的余弦相似度與事先設(shè)定的閾值進行比較，如果大于該閾值，即表明兩者相似，就取出來這一滿足條件的鏡頭，以進行接下來更細的比較，若小于該閾值，表明兩者不相似，進而說明該鏡頭所在的視頻與待檢測視頻不相似，即可濾除，這樣就可以直接在鏡頭層次進行一次初步濾除，避免進行特征提取和比較時花費大量時間和精力。

1.4 基于重疊圖像分塊方法進行全局特征提取

為了提高顏色特征提取的完整性，以保留足夠豐富的顏色位置信息，本文采用文獻[9]中提出的重疊圖像分塊方法，對圖像分為8個區(qū)域，在每一區(qū)域內(nèi)統(tǒng)計顏色直方圖來獲得顏色空間分布，這里不再贅述。

1.5 基于SURF算法進行局部關(guān)鍵點特征提取

鑒于SURF算法[10]中由于使用了積分圖像和箱式濾波器，運算速度是SIFT的3倍左右，且對于圖像的平移、旋轉(zhuǎn)、縮放以及噪聲的影響有很強的魯棒性，文中采用SURF算法提取局部特征。

1.6 基于k-d樹的特征索引與檢索

考慮到本文中視頻集中視頻數(shù)量較多，達成百上千個，本文采用的索引結(jié)構(gòu)是k-d樹，與一般方法相比，它本身具有的特點就是對于大規(guī)模的數(shù)據(jù)檢索有特別明顯高效的處理速度，因此使用k-d樹型索引結(jié)構(gòu)非常合適。實驗中首先從視頻庫中任意取出部分視頻作為訓(xùn)練集，初步建立一個k-d樹，對其他視頻進行比較，能夠在的時間復(fù)雜度里獲得最相近的視頻向量，其所對應(yīng)的視頻即為近重復(fù)視頻。

2 實驗結(jié)果與分析

2.1 實驗說明

本文實驗所用的電腦配置為Intel（R） Core（TM） i3 2.93GHz，2 GB RAM，實驗平臺為Microsoft Visual Studio 2005。實驗中使用的評價方法是大規(guī)模視頻集進行拷貝檢測和近重復(fù)檢測常用的查準率和查全率。

本文實驗中使用的視頻集是這類相關(guān)研究中普遍使用的公共視頻集CC_WEB_VIDEO，是在2006年11月由香港城市大學和卡耐基梅隆大學負責搜集完成的，視頻主要來自YouTube、Google Video和Yahoo！Video中人們最常瀏覽和感興趣的24類查詢的源視頻及其近重復(fù)視頻，如圖3所示。

2.2 實驗結(jié)果

首先要尋找一個查詢視頻，這里采用文獻[7]中的方法進行種子視頻的選擇，這里不再贅述。將實驗結(jié)果與基于顏色直方圖的全局簽名的方法[6]（M_GLOF）、聯(lián)合視頻內(nèi)容和上下文信息的方法[2]（M_CONTX）及結(jié)合全局特征和局部特征結(jié)合起來的分層方法[7]（M_HIER）進行比較，文中時序一致性特征方法用CAS_TF表示，得到各方法的查準率-查全率曲線（PR曲線圖）如圖4所示，在查全率相同時，查準率越高，則這種方法的性能越好。

2.3 結(jié)果分析

通過圖4中各圖進行分析，可得出以下結(jié)論：

（1）從圖4（a）可以看出，文獻[6]中的M_GLOF方法可以很快速又精確地檢測出那些具有簡單場景或變化很小或者完全相同的視頻，比如視頻集中的查詢9、16、24，但從圖4（d）可看出采用本文方法也能夠取得同樣好甚至更好的檢測效果。由于在簡單場景或變化很小的視頻中增加或刪除一些相似的幀圖像不會對其顏色直方圖產(chǎn)生太大影響，故可以直接通過全局顏色特征進行檢測，但是對于場景復(fù)雜或經(jīng)過了很大修改的視頻卻存在著不同視頻有同樣顏色分布的情況，因此不能簡單靠全局特征檢測出來。

（2）從圖4（b）中可以很明顯地看到，文獻[2]中M_CONTX方法效果是最差的，如查詢17、18、22，主要是因為在定義近重復(fù)視頻的時候，我們并沒有將視頻的標題、縮略圖以及長短版本等上下文信息作為視頻內(nèi)容特征，而這種方法恰恰是首先按照視頻的持續(xù)時間長短來檢測視頻的，因此就存在著很大的檢錯可能性。

（3）從圖4（c）中可以看出，文獻[2]中M_HIER方法對于大多數(shù)查詢都取得了很好的效果，首先利用全局顏色特征很容易就可以濾除掉一些很明顯不相同的視頻，剩下的視頻再用更精確的局部關(guān)鍵點特征進行檢測，不僅提高了檢測正確性，還可以大大降低檢測時間。

（4）從圖4（d）中可以看出，采用本文方法（CAS_TF）取得了不錯的檢測效果，尤其是對于那些畫面變化較大或運動場景復(fù)雜的視頻更加明顯，比如查詢13和15，在高的查全率情況下， 大部分查詢都取得了與其他三種相比較高的查準率。但也可以看到本方法對于查詢22效果非常不好，分析該視頻發(fā)現(xiàn)，在該視頻的開頭和結(jié)尾部分加入了很多不相關(guān)的幀，而本文方法在一開始提取鏡頭時序一致性特征，按照視頻鏡頭特征進行比較匹配，有可能將該視頻作為不相同的視頻濾除掉，從而導(dǎo)致查準率較低。

3 結(jié)論

通過以上分析可以看出，本文方法（CAS_TF）的性能比其他三種近重復(fù)檢測算法效果要好，尤其對于那些畫面變化較大以及運動場景復(fù)雜的視頻更明顯。不足之處在于本文沒有對各檢測算法所耗時間進行比較。未來的研究工作主要有兩點，一是對各種方法進行檢測所耗時間和存儲特征的復(fù)雜度進行分析，進一步完善該算法，更有力地驗證該方法的優(yōu)勢；二是要設(shè)計自適應(yīng)的閾值設(shè)置方案，而不用在每次檢測時都要人為地設(shè)置不同閾值，以進一步提高檢測的準確性。

參考文獻：

[1] Yan K， Sukthankar R， and Huston L. Efficient near-duplicate detection and sub-image retrieval[C]. Proceedings of ACM International Conference on Multimedia（MM）， 2004： 869-876.

[2] Wu X， Ngo C W， Alexander G H， et al.. Real-Time Near-Duplicate Elimination for Web Video Search With Content and Context[C]. IEEE Transactions on Multimedia， 2009， 11（2）： 196-207.

[3] Hong R C， Tang J H， Tan H K， et al.. Beyond search： event driven summarization for web videos[C]. Proceedings of ACM International Conference on Multimedia（MM）， 2011， 2（3）： 1-21.

[4] Ngo C W， Zhao W L， and Jiang Y G. Fast Tracking of Near-Duplicate Keyframes in Broadcast Domain with Transitivity Propagation[C]. Proceedings of ACM International Conference on Multimedia （MM）， 2006： 845-854.

[5] Shang L F， Yang L J， Wang F， et al.. Real-time large scale near-duplicate web video retrieval[C]. Proceedings of ACM International Conference on Multimedia（MM）， 2010： 531-540. Innovative Computing， Information and Control，2011， 7（4）： 1639-1649.

[6] Lu L， Wei L， Xian S H， et al.. Video Histogram： A Novel Signature for Efficient Web Video Duplicate Detection[J]. Lecture Notes in Computer Science， 2007： 94-103.

[7] Wu X ， A. G. Hauptmann， and Ngo C W. Practical elimination of near-duplicates from web video search[C]. Proceedings of ACM International Conference on Multimedia （MM）， 2007： 218-227.

[8] 郭丁云， 楊艷芳. 一種新的近重復(fù)監(jiān)控視頻檢測算法[J].微型機與應(yīng)用， 2013（11）.

[9] 丁宏波. 基于顏色和紋理的圖像檢索系統(tǒng)的研究與實現(xiàn)[D]. [D]. 北京交通大學， 2008.

[10] Bay H， Tuytelaars T， and Van G L. SURF： Speeded Up Robust Features[J]. Computer Vision and Image Understanding， 2008， 110（3）：346-359.