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

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

1 引言

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

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

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

2 相關(guān)概念

2.1 深度學(xué)習(xí)

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

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

2.2 稀疏自動(dòng)編碼器

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

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

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

（1）

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

（2）

3 基于自編碼的近重復(fù)視頻檢索

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

3.1 關(guān)鍵幀抽取

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

3.2 特征提取

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

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

（3）

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

3.3 視頻相似性度量

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

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

（4）

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

（5）

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

4 實(shí)驗(yàn)與分析

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

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

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

4.2 評(píng)價(jià)方法

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

（6）

（7）

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

（8）

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

（9）

4.3 實(shí)驗(yàn)結(jié)果

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

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

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

（3）基于深度學(xué)習(xí)稀疏自動(dòng)編碼器的方法：即本文使用的方法。

本文從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é)束語

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

參考文獻(xiàn)

[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]王雅思.深度學(xué)習(xí)中的自編碼器的表達(dá)能力研究[D].哈爾濱工業(yè)大學(xué)，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-），男，安徽省阜陽市人。碩士研究生學(xué)歷。研究方向?yàn)樯疃葘W(xué)習(xí)。

作者單位

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