余時強，張　錚，張為華

(1.復(fù)旦大學(xué) 軟件學(xué)院，上海 201203；2.復(fù)旦大學(xué) 上海市數(shù)據(jù)科學(xué)重點實驗室，上海 200433；3.解放軍信息工程大學(xué) 數(shù)學(xué)工程與先進計算國家重點實驗室,河南 鄭州 450001)

近似重復(fù)視頻檢索方法研究*

余時強1，2，張錚3，張為華1，2

(1.復(fù)旦大學(xué) 軟件學(xué)院，上海 201203；2.復(fù)旦大學(xué) 上海市數(shù)據(jù)科學(xué)重點實驗室，上海 200433；3.解放軍信息工程大學(xué) 數(shù)學(xué)工程與先進計算國家重點實驗室,河南 鄭州 450001)

隨著互聯(lián)網(wǎng)的飛速發(fā)展，越來越多的視頻被上傳和下載，然而這些海量的視頻中有很大的比例是近似重復(fù)的，這些近似重復(fù)的視頻會給版權(quán)控制、視頻檢索準確性等造成一定影響，同時也會增加運營商的存儲和處理成本。如何在大規(guī)模的視頻集中找出近似重復(fù)的視頻變得日益重要。本文對近幾年關(guān)于近似重復(fù)視頻檢索方面的相關(guān)工作和研究成果進行了深入調(diào)研，詳細論述了當前近似視頻檢索技術(shù)的現(xiàn)狀及關(guān)鍵技術(shù)，并對其發(fā)展進行了展望。

近似重復(fù)視頻；視頻特征；視頻檢索

0　引言

隨著社交媒體 Web 2.0飛速膨脹式的發(fā)展，大量的視頻被上傳到互聯(lián)網(wǎng)上，這些視頻被下載、觀看、編輯，重新被上傳到網(wǎng)上，因此互聯(lián)網(wǎng)上充斥著大量內(nèi)容相近的視頻。根據(jù)comScore的數(shù)據(jù)分析，2008年11月時，互聯(lián)網(wǎng)上的視頻總量已達126億個，而到2009年1月則達到了148億個，如此短短的3個月時間內(nèi)視頻總量就有17%的增幅。通過Wu[1]的分析，可以知道通過24次基于YouTube，Google Video和 Yahoo Video的視頻查詢，平均有27%的視頻，有最高可達93%的近似重復(fù)內(nèi)容。這些數(shù)據(jù)表明互聯(lián)網(wǎng)上存在海量的近似重復(fù)視頻。

大量存在的近似重復(fù)視頻會帶來諸多的問題，例如視頻版權(quán)保護和視頻檢索結(jié)果準確性等。由于無處不在的網(wǎng)絡(luò)，擁有版權(quán)控制的視頻可能會被重新編輯、修改然后重新發(fā)布，所以視頻版權(quán)商經(jīng)常會發(fā)現(xiàn)自己的視頻在沒有經(jīng)過允許的情形下就被修改并且發(fā)布到互聯(lián)網(wǎng)上，這會給他們的利益帶來巨大的損失。同樣，大量近似重復(fù)視頻的存在也會影響視頻檢索系統(tǒng)的準確性。很多時候在網(wǎng)上搜索某一個視頻，其實想要得到返回的結(jié)果是那些與之相關(guān)的原始視頻，但是往往搜索結(jié)果靠前的是某個視頻和它的近似重復(fù)視頻，而另外那些與關(guān)鍵詞相關(guān)的原始視頻排名卻靠后，極大地影響著檢索的效果。同時大量近似重復(fù)的視頻也會帶來大量的存儲開銷。

對視頻不同程度的編輯會給近似重復(fù)視頻的提取造成不同的影響，近似重復(fù)視頻的準確查詢?nèi)匀淮嬖谥薮蟮奶魬?zhàn)。雖然可以通過給視頻添加標簽、注釋分類等文字信息幫助提取過程，但是此類方法不夠準確，而且提取結(jié)果較大程度上取決于標記的準確性。另外一種則是基于視頻內(nèi)容的近似重復(fù)性鑒定。當前基于內(nèi)容的近似重復(fù)視頻提取方法整體可分成兩大類：全局特征提取方法和局部特征提取方法。全局的特征首先通過提取關(guān)鍵幀特征，然后通過空間、時間、顏色等模型整合這些幀的特征信息構(gòu)成多維向量，視頻之間的比較則為全局特征的匹配。局部特征方法則通過提取關(guān)鍵幀的局部特征（如 SIFT[2]、PCA-SIFT[3]特征向量）信息，來幫助查詢近似重復(fù)視頻。

全局特征方法提取的特征信息較局部特征方法更加精簡，因此在存儲和特征匹配的階段能夠節(jié)省大量資源，但是全局特征信息對于視頻的變換較為敏感，在變化較大的情形下不能準確地提取近似重復(fù)視頻。局部特征雖然在大量變形的情形下有較好的提取效果，但是計算復(fù)雜性和大量的存儲開銷使其在真實應(yīng)用中實用性不高。

本文從全局特征和局部特征的準確性和計算性能出發(fā)，分析了當前主流方法的優(yōu)缺點，并在此基礎(chǔ)上對近似重復(fù)視頻的發(fā)展方向進行了展望。

1　近似重復(fù)視頻概念

近似重復(fù)視頻是那些和原視頻幾乎一樣，但是在文件格式、編碼參數(shù)、光度變化(包括顏色以及光照變化)、編輯方式(包括插入水印、邊框等)、長度或者某些特定變化下（例如幀的增加和刪除等）有所不同。所以可以認定這些近似重復(fù)視頻和原視頻大體一樣。

重復(fù)視頻是近似重復(fù)視頻的一種，且重復(fù)視頻包含的信息和原視頻基本一樣，這并不意味著重復(fù)視頻在像素層面上和原視頻一模一樣，而是說包含的場景、任務(wù)一樣，沒有添加新的信息。而且判斷兩個視頻是否重復(fù)取決于比較的角度。例如有些版權(quán)控制的場景甚至需要判斷視頻中的某一幀是否和其他視頻一樣，而視頻搜索過程中視頻是否重復(fù)則是通過視頻播放的整體內(nèi)容而定的。本文所述的重復(fù)視頻是近似重復(fù)視頻的一種，在檢索方法中并不區(qū)別對待，因為無論是重復(fù)視頻還是近似重復(fù)視頻，都會被檢索出來而且排名較高。原始、重復(fù)、近似重復(fù)視頻概念圖例如圖1所示。

圖1　原始、重復(fù)、近似重復(fù)視頻概念圖例

2　近似重復(fù)視頻檢索方法

視頻作為多幀圖像在時間軸上的累加，圖像領(lǐng)域的識別和檢索方法也同樣可以運用在近似重復(fù)視頻檢索中。近似重復(fù)視頻的檢索整體分成3個部分：視頻特征的生成、視頻特征的管理、視頻特征的匹配。

給定一個查詢視頻，并且需要從視頻數(shù)據(jù)庫中檢測出相應(yīng)的近似重復(fù)視頻，首先需要對視頻庫中的所有視頻進行特征提取，根據(jù)檢索需要采用相應(yīng)的特征，然后再對這些視頻特征采用特定數(shù)據(jù)結(jié)果進行管理，例如樹形或者局部哈希的方法等。這個階段屬于檢索過程中的離線過程，在輸入查詢視頻之前就可以完成。接著提取輸入視頻的特征，與視頻庫中的視頻特征進行匹配，找出與之近似重復(fù)的視頻，該過程屬于數(shù)據(jù)檢索中的在線部分。

在視頻特征提取過程中，主要可以分成全局特征和局部特征兩種。全局特征主要是基于視頻關(guān)鍵幀的顏色、紋理、動作等信息，將其整合成一個多維向量，在計算和存儲方面較局部特征有較大優(yōu)勢，但是對于變化較大的視頻識別效果較差。雖然局部特征能在光線、噪聲、微視角變化較大的情形下有較高的辨識度，但是其帶來的巨大計算和存儲開銷使得在實際應(yīng)用中并不適用。所以當前較好的方法是采用兩者各自的優(yōu)勢，先用全局特征過濾那些差別較大的視頻，接著利用局部特征進一步匹配，使得檢索結(jié)果在性能和準確性方面都有較大的提升，接下來描述一些當前主流的視頻全局特征和局部特征方法。

3　視頻特征

3.1全局特征

視頻全局特征是通過將視頻作為一個整體提取出的特征，該特征具有占用存儲空間小、提取速度高的特點，被用在很多應(yīng)用中。顏色直方圖以及主成分分析是經(jīng)常被采用的兩種方法。

3.1.1顏色直方圖

顏色直方圖能夠較好地反映圖像中顏色的組成分布，即各種顏色區(qū)間在圖像中出現(xiàn)的概率，雖然該方法對光照敏感，但是仍然是一種好的特征方法。對于視頻而言，基于顏色直方圖的特征首先應(yīng)提取視頻中的關(guān)鍵幀，接著提取每一幀的直方圖，然后對這些關(guān)鍵幀的顏色直方圖取平均值，如式(1)所示[1]。

其中 VSi=(x1，x2…xm)，VSj=(y1，y2…ym)。如果兩視頻的距離接近，就認為它們是近似重復(fù)的。

3.1.2主成分分析

主成分分析是一種將多個變量通過線性變換以選出較少個數(shù)重要變量的一種多元統(tǒng)計分析方法，又稱為主分量分析。

通過視頻的主成分分析可以將最重要的信息作為視頻的特征，不重要的部分將被舍棄。該方法認為視頻中的一小段都有著自己獨特表達的主題，所以可以通過對視頻幀的變化趨勢用向量的方式表示出來，然后通過獲取突出分布從而獲取重要維度得到主要成分，形成視頻的特征[4]，在比較兩個視頻主成分的相似性的時候，為了提高精確性，主成分的旋轉(zhuǎn)變化也是需要考慮的部分。

3.2局部特征

視頻的局部特征主要來源于關(guān)鍵幀的局部特征。在圖像和模式識別領(lǐng)域，局部特征點的發(fā)明使得近似重復(fù)視頻的檢測也有了巨大的發(fā)展，而且由于基于關(guān)鍵幀的局部特征在視頻幾何變換程度很大的情況下仍然有較高的辨識度，檢索準確度較高，但是由于局部特征包含過多的信息，通常采用高維的向量表示，其在存儲和計算方面占用較大的資源。

一張圖片或關(guān)鍵幀包含成百上千個的局部特征點，而每個特征點由高維的向量構(gòu)成(如SIFT的128維向量，PCA-SIFT的36維向量)，雖然已有研究通過出現(xiàn)頻率的高低去過濾掉低頻的特征點來減少存儲和計算的開銷，但是基于局部特征向量的關(guān)鍵幀信息在匹配階段仍然是耗時的。

4　特征索引

無論是采用視頻的全局特征還是局部特征方法，在提取特征信息后，都需要將查詢視頻與視頻庫進行匹配，那么如何管理海量數(shù)據(jù)庫的特征信息將直接影響查詢性能和準確性。

4.1樹形結(jié)構(gòu)

樹形結(jié)構(gòu)已經(jīng)在圖像檢索領(lǐng)域有非常廣泛的應(yīng)用，如VOC-Tree[5]，可以利用該樹形結(jié)構(gòu)對視頻幀的局部特征進行聚類，使得在特征匹配過程中以樹的方式查詢，能夠快速提升檢索性能。在視頻檢索領(lǐng)域，視頻提取的特征是基于圖像特征的，都是用高維向量表示，所以基于樹形結(jié)構(gòu)的索引能有效提高索引速度，但是隨著維數(shù)的不斷增大，檢索的效率會有所減少。

4.2局部敏感哈希

無論是視頻采用全局特征或者是局部特征，特征信息都是以高維向量進行表示，局部敏感哈希是一種在高維情形下有效提高搜索效率的方法，通過哈希的方法可以在存儲的時候?qū)⑾嗨频奶卣餍畔⒋娣旁谝黄?，在搜索的時候便能快速定位到近似重復(fù)的特征，無論是從準確性還是速度方面都有很好的性能。

5　實驗分析標準和數(shù)據(jù)集

在近似重復(fù)視頻檢測領(lǐng)域，需要有大量的視頻數(shù)據(jù)集來測試檢索效果，如今已經(jīng)有很多機構(gòu)專門在這方面提供了較為豐富的測試集，這些視頻都是從網(wǎng)絡(luò)上下載下來，有些還經(jīng)過了一些編輯處理以模擬近似重復(fù)關(guān)系。在測試性能方面，檢索準確率和效率是關(guān)注度較高的兩個方面。

5.1測試基準集

CC_WEB_VIDEO是香港城市大學(xué)和卡耐基梅隆大學(xué)提供的近似重復(fù)視頻數(shù)據(jù)集合。它總共包含通過24次查詢過程中從 Google Video，Yahoo Video和 YouTube上下載的13 129個視頻，這些視頻下載后沒有通過特定的軟件進行編輯，并且通過人工做標記來表明最真實的近似重復(fù)關(guān)系，來和實現(xiàn)結(jié)果做比較以判斷準確性。

VCDB[6]是上海智能信息實驗室和復(fù)旦大學(xué)收集的大規(guī)模的近似重復(fù)視頻集合，總共包括100 000個網(wǎng)絡(luò)視頻，這些視頻沒有經(jīng)過人為的變化處理，重復(fù)關(guān)系通過人為手動做標記。

TRECVID[7]是美國政府支持視頻檢索的數(shù)據(jù)集，每年都會基于上一年提供一些新的視頻集合，這些視頻經(jīng)過人工的編輯然后和原視頻混合在一起，真實的重復(fù)關(guān)系在變換之后也有記錄。

MUSCLE-VCD-2007是一個重復(fù)視頻的集合，該集合中總共包括100個小時的視頻，這些視頻形式多樣，有網(wǎng)絡(luò)視頻片段、電視視頻、電影片段等，這些視頻從分辨率和文件格式等方面均存在很大差異。

5.2性能標準

在近似重復(fù)視頻檢索中，檢索速度和準確性是評判結(jié)果的兩個非常重要的指標。

檢索速度一般是從檢索行為開始至結(jié)果返回中間這段過程中花費的時間來評定的。在實驗過程中，實驗準確性是將程序返回的近似重復(fù)結(jié)果和最開始人為標記的視頻近似重復(fù)關(guān)系做比較，人為標記的重復(fù)關(guān)系作為基準，在Wu[1]的CC_WEB_VIDEO集合中，就對集合中的所有視頻做了標記，以記錄近似重復(fù)關(guān)系。

6　結(jié)語

近似重復(fù)視頻的檢測在當前爆炸式增加的視頻的時代是十分重要的，隨著深度學(xué)習(xí)在視頻分類的領(lǐng)域中的快速發(fā)展[8]，并且也已經(jīng)取得顯著效果，該技術(shù)也定能夠在近視重復(fù)視頻檢測的領(lǐng)域發(fā)揮作用。同時隨著視頻量的增加，當前方法在更大量的視頻數(shù)據(jù)情況的可擴展性也是需要解決的問題之一。為了更好地提升檢索的精確性，不斷地根據(jù)反饋機制去調(diào)整檢索結(jié)果也是一個非常有前景的研究方向。

[1]WU X，HAUPTMANN A G，NGO C W.Practical elimination of near-duplicates from web video search[C].Proceedings of the 15th international conference on Multimedia.ACM，2007：218-227.

[2]LOWE D G.Distinctive image features from scale-invariant keypoints[J].International journal of computer vision，2004，60(2)：91-110.

[3]KE Y，SUKTHANKAR R.PCA-SIFT：A more distinctive representation for local image descriptors[C].Computer Vision and Pattern Recognition，2004.CVPR 2004.Proceedings of the 2004 IEEE Computer Society Conference on.IEEE，2004，2：II-506-II-513 Vol.2.

[4]SHEN H T，ZHOU X，HUANG Z，et al.UQLIPS：a realtime near-duplicate video clip detection system[C].Proceedings of the 33rd international conference on Very large data bases.VLDB Endowment，2007：1374-1377.

[5]NISTER D，STEWENIUS H.Scalable recognition with a vocabulary tree[C].Computer Vision and Pattern Recognition，2006 IEEE Computer Society Conference on.IEEE，2006，2：2161-2168.

[6]JIANG Y G，JIANG Y，WANG J.VCDB：A large-scale database for partial copy detection in videos[M].Computer Vision-ECCV 2014.Springer International Publishing，2014：357-371.

[7]OVER P，AWAD G M，F(xiàn)ISCUS J，et al.TRECVID 2010-An overview of the goals，tasks，data，evaluation mechanisms，and metrics[J].2011.

[8]KARPATHY A，TODERICI G，SHETTY S，et al.Large-scale video classification with convolutional neural networks[C]. Computer Vision and Pattern Recognition(CVPR)，2014 IEEE Conference on.IEEE，2014：1725-1732.

[9]WU X，Ngo C W，HAUPTMANN A G，et al.Real-time near-duplicate elimination for web video search with content and context[J].Multimedia，IEEE Transactions on，2009，11(2)：196-207.

[10]LIU J，HUANG Z，CAI H，et al.Near-duplicate video retrieval：Current research and future trends[J].ACM Computing Surveys(CSUR)，2013，45(4)：44.

[11]SHANG L，YANG L，WANG F，et al.Real-time large scale near-duplicate web video retrieval[C].Proceedings of the international conference on Multimedia.ACM，2010：531-540.

[12]SHEN H T，ZHOU X，HUANG Z，et al.Statistical summarization of content features for fast near-duplicate video detection[C].Proceedings of the 15th international conference on Multimedia.ACM，2007：164-165.

[13]ZHOU X，ZHOU X，CHEN L，et al.An efficient nearduplicate video shot detection method using shot-based interest points[J].Multimedia，IEEE Transactions on，2009，11(5)：879-891.

[14]SHEN H T，ZHOU X，HUANG Z，et al.UQLIPS：a realtime near-duplicate video clip detection system[C]. Proceedings of the 33rd international conference on Very large data bases.VLDB Endowment，2007：1374-1377.

Research of near-duplicate video retrieval

Yu Shiqiang1，2，Zhang Zheng3，Zhang Weihua1，2
(1.Software School，F(xiàn)udan University，Shanghai 201203，China；2.Shanghai Key Laboratory of Data Science，Shanghai 200433，China；3.State Key Laboratory of Mathematical Engineering and Advanced Computing，Zhengzhou 450001，China)

With the fast development of Internet,sheer amount of videos are upload and download in which high proportion are near-duplicate.And these near-duplicate videos arise problems in copy protection,video retrieval accuracy etc,also incurs extra unnecessary cost.It’s becoming more and more important to find out near-duplicate videos from large video sets.This paper systematically surveys current near-duplicate video retrieval technologies,compares trade-off between accuracy and throughput,and illustrates state-of-the-art works and explore the potential trending in this field.

near-duplicate；video signature；video retrieval

TP3

A

10.16157/j.issn.0258-7998.2016.05.007

國家高技術(shù)研究發(fā)展計劃(863)(2012AA010905)；國家自然科學(xué)基金(61370081)

2015-12-27)

余時強（1992-），男，碩士，主要研究方向：GPU、近似重復(fù)系統(tǒng)檢測、操作系統(tǒng)。

張錚（1977-），男，博士，副教授，主要研究方向：體系結(jié)構(gòu)、網(wǎng)絡(luò)安全與模式識別。

張為華（1974-），通信作者，男，博士，副教授，主要研究方向：體系結(jié)構(gòu)與編譯優(yōu)化，E-mail：zhangweihua@fudan.edu.cn。

中文引用格式：余時強，張錚，張為華.近似重復(fù)視頻檢索方法研究[J].電子技術(shù)應(yīng)用，2016，42(5)：24-26，35.

英文引用格式：Yu Shiqiang，Zhang Zheng，Zhang Weihua.Research of near-duplicate video retrieval[J].Application of Electronic Technique，2016，42(5)：24-26，35.