一種新的時(shí)序一致性特征的近重復(fù)視頻檢測(cè)算法

郭丁云+薛峰+郭旦萍

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ù)量和種類飛速增長(zhǎng)。視頻被大量傳播和復(fù)制造成了很多問題[1]，比如視頻盜版、視頻冗余等。文獻(xiàn)[2]曾指出在來自于社交網(wǎng)站上主要的24類查詢中存在著平均27%的重復(fù)，最大甚至達(dá)到93%。在視頻監(jiān)控領(lǐng)域，需要從成千上萬個(gè)海量視頻中找到用戶關(guān)心目標(biāo)的視頻，比如穿藍(lán)色上衣的人，對(duì)大規(guī)模監(jiān)控視頻進(jìn)行檢索必然花費(fèi)很多精力和時(shí)間。在這個(gè)大背景下，有關(guān)視頻檢索和視頻摘要的研究開始如火如荼地開展起來[3-4]，針對(duì)如何在大規(guī)模視頻集中更加準(zhǔn)確又快速地檢測(cè)出相同或相近的視頻或目標(biāo)，在多媒體搜索和內(nèi)容分析中變得越來越重要。

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

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

1 本文算法

1.1 基于邊緣輪廓差值法進(jìn)行鏡頭邊界檢測(cè)

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

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

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

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

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

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

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

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

（3）將待檢測(cè)視頻各鏡頭的時(shí)序一致性特征作為待檢測(cè)特征，分別與視頻集中所有鏡頭的時(shí)序特征進(jìn)行比較，在這里采用余弦相似性作為比較指標(biāo)；

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

1.4 基于重疊圖像分塊方法進(jìn)行全局特征提取

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

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

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

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

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

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

2.1 實(shí)驗(yàn)說明

本文實(shí)驗(yàn)所用的電腦配置為Intel（R） Core（TM） i3 2.93GHz，2 GB RAM，實(shí)驗(yàn)平臺(tái)為Microsoft Visual Studio 2005。實(shí)驗(yàn)中使用的評(píng)價(jià)方法是大規(guī)模視頻集進(jìn)行拷貝檢測(cè)和近重復(fù)檢測(cè)常用的查準(zhǔn)率和查全率。

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

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

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

2.3 結(jié)果分析

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)：

[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)控視頻檢測(cè)算法[J].微型機(jī)與應(yīng)用， 2013（11）.

[9] 丁宏波. 基于顏色和紋理的圖像檢索系統(tǒng)的研究與實(shí)現(xiàn)[D]. [D]. 北京交通大學(xué)， 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.