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

余時(shí)強(qiáng)，張　錚，張為華

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

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

余時(shí)強(qiáng)1，2，張錚3，張為華1，2

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

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

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

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

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

3　視頻特征

3.1全局特征

視頻全局特征是通過將視頻作為一個(gè)整體提取出的特征，該特征具有占用存儲空間小、提取速度高的特點(diǎn)，被用在很多應(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)。如果兩視頻的距離接近，就認(rèn)為它們是近似重復(fù)的。

3.1.2主成分分析

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

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

3.2局部特征

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

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

4　特征索引

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

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

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

4.2局部敏感哈希

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

5　實(shí)驗(yàn)分析標(biāo)準(zhǔn)和數(shù)據(jù)集

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

5.1測試基準(zhǔn)集

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

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

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

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

5.2性能標(biāo)準(zhǔn)

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

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

6　結(jié)語

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

[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ā)展計(jì)劃(863)(2012AA010905)；國家自然科學(xué)基金(61370081)

2015-12-27)

余時(shí)強(qiáng)（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。

中文引用格式：余時(shí)強(qiáng)，張錚，張為華.近似重復(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.