基于稀疏自動編碼器的近重復視頻檢索

隨著互聯網的迅速發展，網絡上產生了大量的近重復視頻，如何快速精確地檢測出這些近重復視頻成為研究的熱點。本文提出了一種基于稀疏自動編碼器的視頻特征提取模型，用于近重復視頻檢索。先用稀疏自動編碼器提取視頻關鍵幀的特征，然后根據視頻間匹配的關鍵幀數占視頻所有關鍵幀數的比例來度量視頻的相似性。實驗結果表明所提出的方法取得了較好的檢索精度。

【關鍵詞】深度學習 自編碼器 網絡視頻 近重復視頻檢索

1 引言

隨著視頻分享網站（如YouTube、優酷、土豆網等）的出現，互聯網上的視頻數量和種類爆炸性地增長。用戶可以通過手機、攝像機制作視頻或者從網上獲取視頻，在做過一些改動后重新發布到網上。根據YouTube 2009年5月的統計數據顯示，每分鐘大約有20小時的新視頻上傳到該網站，日均瀏覽量超過2億次。而到2012年，每天每秒就有長達一小時的視頻上傳到YouTube，并且日均瀏覽量達到40億次。但是在這些海量的網絡視頻中，存在著大量重復的或者近似重復的視頻。Wu等人通過24個關鍵詞對YouTube、Google Video和Yahoo！ Video三個常用視頻搜索引擎的搜索結果進行分析，發現在搜索結果中平均存在27%的重復或近似重復的視頻。對于某些特定的查詢，重復率甚至高達93%。這些大量重復的視頻不僅浪費了存儲空間，也給視頻的有效管理帶來不便。而且，用戶在網絡上搜索感興趣的視頻時返回過多的重復結果，大大降低了用戶體驗。因此為了提高網絡視頻的管理、搜索及瀏覽效率，高效的視頻重復檢測方法就顯得十分必要。

現有的近重復視頻檢索方法多分為如下3個步驟：首先，從每個視頻中提取一系列的關鍵幀，用這些關鍵幀代表一個視頻；然后，對每一個視頻關鍵幀采用特征提取算法生成一組特征向量；最后，通過關鍵幀的特征向量計算視頻之間的相似度。關鍵幀的特征表示又分為兩類：全局特征和局部特征，分別對應于不同的視頻內容表示算法和相似性度量的選取。

本文提出一種用稀疏自動編碼器提取關鍵幀特征的方法，并將該方法用于近重復視頻的檢測，取得了較好的檢測準確度。

2 相關概念

2.1 深度學習

深度學習的概念由Hinton等人于2006年提出，它是機器學習研究中的一個新的領域，其動機在于建立和模擬人腦進行分析學習的神經網絡，它模仿人腦的機制來解釋數據，例如圖像理解，語音識別和自然語言處理等。深度學習中的無監督學習方法，可以通過對深層非線性網絡結構的學習，實現對復雜函數的逼近，從而實現對輸入數據的分布式表示，具有從少數樣本中提取本質特征的強大能力。

自動編碼器（AE） 作為深度學習的基本模型之一，可以捕捉輸入數據中的重要特征，使訓練后的數據可以無限逼近輸入數據。為了學習更復雜的非線性函數，在自動編碼器的基礎上添加稀疏性約束，得到稀疏自動編碼器（SAE），它可以通過學習得到更好的特征表示。

2.2 稀疏自動編碼器

稀疏自動編碼器是一種無監督的學習方法，通過前向傳播構建網絡結構，采用梯度下降的方法調整權重，利用反向傳播算法實現目標值逼近輸入值，它是用于降維和特征提取的神經網絡，可以提取數據中最主要的隱藏特征（特征的個數通過隱藏節點數確定）。稀疏自動編碼器（SAE）是以人工神經網絡為基礎構建而成的網絡，因此稀疏自動編碼器可以認為是一種雙層神經網絡，第一層是由輸入層和中間隱層節點組成的編碼層，第二層是由中間隱層和輸出層節點組成的編碼層，其中編碼層輸入節點的個數與解碼層輸出節點的個數相等。

稀疏自動編碼器（SAE）的神經網絡結構包括有m個節點的輸入層x={x1，x2，…，xm}，n個節點的中間隱層z={z1，z2，…，zn}，和m個節點的輸出層y={y1，y2，…，ym}。y是通過隱層節點z對x進行的重構，其中隱層的維數比輸入層小，即n

其中，相鄰兩層節點之間邊的權重用矩陣w（1）={w（1）11，w（1）12，…，w（1）nm}和w（2）={w（2）11，w（2）12，…，w（2）nm}表示，其中w（1）ji表示輸入層第i個節點與隱層第j個節點之間的權重。隱層和輸出層的偏置項用b（1）={b（1）1，b（1）2，…，b（1）n}和b（2）={b（2）1，b（2）2，…，b（2）m}表示，其中b（1）j是隱層第j個節點的偏置值。隱層第j個節點的輸入值定義為公式（1）：

（1）

其中，每個隱層節點的輸出值aj是通過sigmoid激活函數f（z）的線性表示，即f（z）=1/（1+e-z），aj=f（zj）。輸出層的值y，可表示為公式（2）：

（2）

3 基于自編碼的近重復視頻檢索

信息檢索的任務，是對用戶輸入的一個對象，按與輸入相關程度輸出排序后的一系列對象。對于近重復視頻檢索系統，其步驟如下：

3.1 關鍵幀抽取

給定視頻數據集V，對于數據集中的每一個視頻采用基于鏡頭的關鍵幀抽取方法抽取關鍵幀。假設從視頻數據集V中抽取了n個關鍵幀，接下來就是針對這n個關鍵幀提供的信息做進一步的處理。

3.2 特征提取

用上一步得到的一部分關鍵幀對自編碼器神經網絡進行訓練，得到訓練好的自編碼器網絡模型。然后，將每一個關鍵幀作為自編碼器的輸入，得到編碼后的結果，將此結果作為該關鍵幀的特征表示。

因此，兩個關鍵幀Si和Sj之間的相似性d（Si， Sj）可以使用對應的特征向量的歐式距離表示：

（3）

其中，Fi = （x1， x2，…，xd）和Fj=（y1， y2，…， yd）為兩個關鍵幀的特征向量。

3.3 視頻相似性度量

提取視頻每個關鍵幀的特征后，就可以比較兩個關鍵幀的相似性。而兩個視頻間匹配的關鍵幀越多，則這兩個視頻越相似。為了更好地定量分析，對視頻的相似性作如下定義：

假設Vq= {Sq1， Sq2，…，Sqm}表示查詢視頻，包含m個關鍵幀；Vd= {Sd1， Sd2， …，Sdn}表示數據庫中的一個視頻，包含n個關鍵幀。那么視頻Vq和Vd之間的相似性R（Vq，Vd）可以表示為：

（4）

當上式超過給定的閾值，則稱Vq和Vd是重復視頻。其中Sqk為視頻Vq中的任意關鍵幀，|Vq|是視頻Vq中關鍵幀的個數，函數δ（Sqk，Vd）是個邏輯函數，即視頻Vd中是否存在與關鍵幀Sqk相匹配的關鍵幀，若查詢視頻Vq中的關鍵幀Sqk在視頻Vd中存在相匹配的鏡頭，其函數值為1，否則為0，即：

（5）

其中，T為一個給定的經驗閾值，即當查詢視頻Vq中的關鍵幀Sqk與視頻Vd中最相似的關鍵幀Sdk距離不大于T時，則這兩個關鍵幀相匹配。

4 實驗與分析

為了評價本文方法的有效性，在本章中將給出本文方法及一些其他現有方法的實驗結果，包括視頻數據集和評價方法的介紹。實驗表明，本文方法在指定數據集上取得了較好的近重復視頻檢測效果。

4.1 視頻數據集

本文采用的是網絡視頻近似重復檢索所常用的一個公開數據集，即CC_WEB_VIDEO數據集。CC_WEB_VIDEO是由香港城市大學和卡內基梅隆大學提供的。它通過使用24個關鍵詞（“The lion sleeps tonight”，“Evolution of dance”，“Fold shirt”等）在YouTube、Google Video和Yahoo！ Video上搜索并下載得到，一共有12790個視頻。對于每組視頻，最流行的視頻被用做查詢視頻，然后人工對剩余視頻進行標注，即標注成相似的或不相似的。查詢關鍵詞和近似重復視頻的個數如表1所示。例如對于查詢“The lion sleeps tonight”，一共有792個視頻，其中有334個視頻與查詢視頻重復或近似重復。

4.2 評價方法

本文中針對上述實驗數據采用了查全率-查準率曲線和平均準確率（MAP）兩種評價標準。查全率（Recall）-查準率（Precision）曲線是比較常用的一種評價檢索結果的方法。查全率也稱召回率，指相關的文檔檢索出的越多越好，也就是返回的結果中相關的個數占全部相關結果的個數；查準率也稱準確率，是指檢索出的結果中，相關文檔的個數越多越好，也就是返回的結果中相關的個數占檢索到的所有結果的比例。查全率和查準率的公式分別為：

（6）

（7）

平均準確率（MAP）反映的是系統在檢索全部的和主題相關的文檔的性能指標。一般情況下，如果系統檢索出的相關文檔排序越靠前，系統的平均準確率（MAP）就越高；如果沒有檢索到任何的相關的文檔，則MAP值為零。求解公式如下：

（8）

其中，q表示查詢集，N表示查詢集的個數，mi表示相關文檔的個數，Precision（Rij）表示返回的結果中第j個相關文檔在返回結果的位置與該文檔在返回結果中的位置，即

（9）

4.3 實驗結果

為了評價檢索效果，本節將對我們提出的方法與現有的典型方法進行比較，即基于HSV顏色直方圖全局特征的近重復視頻檢索方法以及全局特征和局部LBP特征結合的近重復視頻檢索方法。我們做了三個對比實驗，分別是：

（1）基于全局簽名的方法（Sig-CH）：該方法使用HSV顏色直方圖作為視頻關鍵幀的特征，將一個視頻所有關鍵幀特征的平均值作為該視頻的全局簽名。在這里簡稱這種方法為GF方法。

（2）基于局部特征的分層比較方法：該方法首先使用顏色直方圖檢測出很大概率與被檢視頻重復的視頻并過濾掉極度不相似的視頻，在使用基于LBP局部特征的關鍵幀比較方法檢測出其它近重復視頻。在這里簡稱這種方法為HF方法。

（3）基于深度學習稀疏自動編碼器的方法：即本文使用的方法。

本文從MAP值和P-R曲線分析算法。MAP值的比較見表2所列，P-R曲線的比較如圖2所示。

表2：MAP值的比較

方法 MAP

GF 0.892

LF 0.952

本文方法 0.955

從表2中可以看出，本文方法的MAP值結果最好。從圖2中可以看出GF在這些方法中效果最差，本文方法效果最好，LF方法效果次之。

5 結束語

本文利用深度學習中的稀疏自編碼器模型，自動地從視頻關鍵幀中學習圖像的特征，將學習到的特征應用于近重復視頻檢測任務上，并將該方法與基于視頻全局HSV顏色直方圖的方法以及全局特征與局部LBP特征相結合的方法進行了比較。實驗表明，本文提出的方法近重復視頻檢測的效果要優于其它兩種方法，具有較好的檢索準確性。

參考文獻

[1]Wikipedia.YouTube[EB/OL].http：//en.wikipedia.org/wiki/Youtube.

[2]Wu X，Ngo C W，Hauptmann A G，et al. Real-Time Near-Duplicate Elimination for Web Video Search With Content and Context[J].IEEE Transactions on Multimedia，2009，11（02）：196-207.

[3]WU Xiao，NGO C，HAUPTMANNA.CC_WEB_VIDEO：near-duplicate Web video dataset[EB/OL].http：//vireo.cs.cityu.edu.hk/webvideo/.

[4]Hinton G E，Osindero S，Teh Y W.A fast learning algorithm for deep belief nets.[J].Neural Computation， 2006，18（07）：1527-1554.

[5]王雅思.深度學習中的自編碼器的表達能力研究[D].哈爾濱工業大學，2014.

[6]Coates A，Ng A Y.The Importance of Encoding Versus Training with Sparse Coding and Vector Quantization[C]// International Conference on Machine Learning，ICML 2011，Bellevue， Washington，USA，June 28-July. 2011：921-928.

[7]Baccouche M， Mamalet F，Wolf C，et al.Spatio-Temporal Convolutional Sparse Auto-Encoder for Sequence Classification[J].Networks，2012， 18（05）.

[8]Coates A， Ng A Y， Lee H. An Analysis of Single-Layer Networks in Unsupervised Feature Learning[J]. Journal of Machine Learning Research， 2011（15）：215-223.

[9]Mukherjee S，Ashish K，Hui N B，et al. Modeling Depression Data：Feed Forward Neural Network vs.Radial Basis Function Neural Network[J].American Journal of Biomedical Sciences，2014.

[10]Needell D，Srebro N，Ward R. Stochastic gradient descent，weighted sampling，and the randomized Kaczmarz algorithm[J].Mathematical Programming，2016，155（01）：549-573.

[11]Yuan J，Duan L Y，Tian Q，et al. Fast and Robust Short Video Clip Search for Copy Detection[C]// ACM Sigmm International Workshop on Multimedia Information Retrieval， Mir 2004，October 15-16，2004，New York，Ny，Usa.2004：61-68.

[12]Wu X，Hauptmann A G，Ngo C W. Practical elimination of near-duplicates from web video search[C]// ACM International Conference on Multimedia.ACM，2007：218-227.

作者簡介

王飛飛（1991-），男，安徽省阜陽市人。碩士研究生學歷。研究方向為深度學習。

作者單位

合肥工業大學 安徽省合肥市 230009