0 引言

    隨著社交媒體Web 2.0飛速膨脹式的發(fā)展，大量的視頻被上傳到互聯(lián)網(wǎng)上，這些視頻被下載、觀看、編輯，重新被上傳到網(wǎng)上，因此互聯(lián)網(wǎng)上充斥著大量?jī)?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%的增幅。通過(guò)Wu^[1]的分析，可以知道通過(guò)24次基于YouTube，Google Video和Yahoo Video的視頻查詢，平均有27%的視頻，有最高可達(dá)93%的近似重復(fù)內(nèi)容。這些數(shù)據(jù)表明互聯(lián)網(wǎng)上存在海量的近似重復(fù)視頻。

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

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

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

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

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

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

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

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

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

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

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

3 視頻特征

3.1 全局特征

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

3.1.1 顏色直方圖

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

3.1.2 主成分分析

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

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

3.2 局部特征

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

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

4 特征索引

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

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

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

4.2 局部敏感哈希

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

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

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

5.1 測(cè)試基準(zhǔn)集

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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

參考文獻(xiàn)

[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 real-time 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 near-duplicate 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 real-time near-duplicate video clip detection system[C].Proceedings of the 33rd international conference on Very large data bases.VLDB Endowment，2007：1374-1377.