0 引言

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

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

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

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

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

1 近似重復視頻概念

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

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

2 近似重復視頻檢索方法

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

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

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

3 視頻特征

3.1 全局特征

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

3.1.1 顏色直方圖

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

3.1.2 主成分分析

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

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

3.2 局部特征

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

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

4 特征索引

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

4.1 樹形結構

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

4.2 局部敏感哈希

    無論是視頻采用全局特征或者是局部特征，特征信息都是以高維向量進行表示，局部敏感哈希是一種在高維情形下有效提高搜索效率的方法，通過哈希的方法可以在存儲的時候將相似的特征信息存放在一起，在搜索的時候便能快速定位到近似重復的特征，無論是從準確性還是速度方面都有很好的性能。

5 實驗分析標準和數據集

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

5.1 測試基準集

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

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

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

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

5.2 性能標準

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

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

6 結語

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

參考文獻

[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，FISCUS 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.