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

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

【關(guān)鍵詞】深度學習 自編碼器 網(wǎng)絡(luò)視頻 近重復視頻檢索

1 引言

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

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

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

2 相關(guān)概念

2.1 深度學習

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

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

2.2 稀疏自動編碼器

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

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

其中，相鄰兩層節(jié)點之間邊的權(quá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個節(jié)點與隱層第j個節(jié)點之間的權(quán)重。隱層和輸出層的偏置項用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個節(jié)點的偏置值。隱層第j個節(jié)點的輸入值定義為公式（1）：

（1）

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

（2）

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

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

3.1 關(guān)鍵幀抽取

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

3.2 特征提取

用上一步得到的一部分關(guān)鍵幀對自編碼器神經(jīng)網(wǎng)絡(luò)進行訓練，得到訓練好的自編碼器網(wǎng)絡(luò)模型。然后，將每一個關(guān)鍵幀作為自編碼器的輸入，得到編碼后的結(jié)果，將此結(jié)果作為該關(guān)鍵幀的特征表示。

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

（3）

其中，F(xiàn)i = （x1， x2，…，xd）和Fj=（y1， y2，…， yd）為兩個關(guān)鍵幀的特征向量。

3.3 視頻相似性度量

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

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

（4）

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

（5）

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

4 實驗與分析

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

4.1 視頻數(shù)據(jù)集

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

4.2 評價方法

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

（6）

（7）

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

（8）

其中，q表示查詢集，N表示查詢集的個數(shù)，mi表示相關(guān)文檔的個數(shù)，Precision（Rij）表示返回的結(jié)果中第j個相關(guān)文檔在返回結(jié)果的位置與該文檔在返回結(jié)果中的位置，即

（9）

4.3 實驗結(jié)果

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

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

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

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

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

表2：MAP值的比較

方法 MAP

GF 0.892

LF 0.952

本文方法 0.955

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

5 結(jié)束語

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

參考文獻

[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].哈爾濱工業(yè)大學，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-），男，安徽省阜陽市人。碩士研究生學歷。研究方向為深度學習。

作者單位

合肥工業(yè)大學 安徽省合肥市 230009