基于深度學習的視頻近似拷貝檢索

馮兆華 朱允斌 李衛強

1(復旦大學計算機科學技術學院 上海 201203) 2(上海視頻技術與系統工程研究中心 上海 201203) 3(上海下一代廣播電視網應用實驗室有限公司 上海 200032)

0 引 言

隨著科技的發展，視頻數據總量飛速增長，人們希望能有類似以圖搜圖這種基于內容的搜索系統出現。

近年來，機器學習領域取得了許多令人矚目的成就，其中深度卷積神經網絡已經被廣泛應用在圖像分類、圖像識別和圖像檢索等領域[1]，將其應用在視頻檢索領域是很自然的想法。視頻近似拷貝檢測的第一步便是提取視頻采樣幀的特征，而深度卷積神經網絡恰好能做到這一點。之后需要為提取出的特征值建立索引以加快搜索速度，這一點可以利用k-d樹實現。

1 相關工作

從已有的圖像拷貝檢測以及視頻近似拷貝檢索的算法[2,8,11-12]來看，視頻近似拷貝檢測方法大都可分為三個主要步驟：提取采樣幀的特征值、為視頻庫內視頻的采樣幀建立索引，以及檢索和計算相似度。

在提取特征步驟，傳統方法的做法是手動提取特征。例如，文獻[2]以像素灰度的序數為依據，將畫面分塊匯總序數信息后作為特征值。這種特征值體積較小，且對亮度變化的處理能力強。但由于這種方法加入了圖像的空間信息，使其對于裁剪、遮擋、水印等變化十分敏感，對這類近似拷貝的檢測能力不足。

近年來，受到文獻[3]等圖像領域工作的啟發，一些學者嘗試利用深度學習進行視頻近似拷貝檢索，如文獻[11-12]等。雖然這些工作使用的網絡結構各不相同，但這類方法的總體思路都是將深度卷積神經網絡中所有卷積層的狀態匯總為一個向量，并使用主元分析等方法對其進行降維，以此作為視頻幀特征值，進一步將幀特征匯總為視頻特征。這類方法的缺點在于，需要匯總計算所有卷積層的狀態，并進行額外的降維操作才能得到幀特征值。此外，為了進行后續的索引操作，還需要進一步由幀特征得到視頻特征。

在建立索引步驟中，通過進行相似檢索來從視頻庫中選出與查詢視頻相似的視頻。現有算法包括大致可分為最近鄰搜索、二分圖匹配算法、使用樹結構以及哈希結構等[7]，目的都是為了提高搜索速度[6]。

2 系統實現

本系統可以劃分為使用深度卷積神經網絡提取采樣幀的特征值、為視頻庫內視頻的采樣幀建立索引，以及檢索并計算相似度三個部分。其中，提取特征和建立索引兩個步驟是離線進行的，檢索步驟為在線過程。

系統的設計目標是針對一個給定的輸入視頻，在離線視頻庫內找出與輸入視頻相似的視頻并輸出。系統應在保證高效的同時達到較高的精確度。

不同于現有基于深度學習的方法，本方法在特征提取與建立索引步驟加以創新。在特征提取階段，本方法在網絡中加入一個新的隱藏層，以隱藏層的狀態作為幀特征值。這種做法能夠在保證特征質量的前提下免于計算所有卷積層的狀態，同時不需要進行額外的降維操作，大大加快了特征提取的速度。在建立索引階段，本文使用了一種基于幀特征建立索引的方法，并提出了對應的置信度和視頻相似度計算方法，從而在保證索引效果的前提下避免了計算視頻特征值。

2.1 視頻近似拷貝檢索系統框架

本系統實現分為離線索引和在線檢索兩部分，在離線索引階段，算法使用深度卷積神經網絡提取出數據庫中視頻的采樣幀的特征值，之后并采用k-d樹為它們建立索引。在檢索階段，算法會采用同樣的方法提取出輸入查詢視頻的采樣幀特征值，并用近似最近鄰搜索的方法在索引庫中找出與其相似的候選視頻。在最后的相似度投票階段，算法會計算出候所有選視頻與查詢視頻的相似度，并按照相似度給出近似拷貝檢索的結果。

具體實踐時，針對一個輸入視頻，我們采用1秒取1幀的固定間隔進行視頻采樣，得到一組連續的采樣幀。我們將這些采樣幀作為原始輸入視頻的代表，并在其基礎上進行特征提取、建立索引等操作。

2.2 深度卷積神經網絡模型

利用深度卷積神經網絡(CNN)提取視頻幀特征想法的產生是受到圖像檢索領域的啟發。最近的研究表明[3]，深度卷積神經網絡可以大幅提高多種視覺任務的效率，如物體檢測、圖像分類和分割等，這都是得益于深度卷積神經網絡對豐富的圖像中層表示強大的學習能力。為了降低CNN特征的維度，我們向典型的CNN模型中添加一個新的隱藏層，從中能夠提取出特征向量作為圖像中層特征[1,9]。在具體實現時，本算法使用文獻[13]提出的預訓練CNN模型，這種模型是基于大規模圖片數據庫ImageNet中的超過1 200 000張圖片訓練得到的，并將這些圖片歸為1 000個對象類。著名的CNN代碼庫Caffe中已經包含了這套模型，可以方便地使用。圖1為網絡框架圖。

圖1 深度卷積神經網絡框架

2.3 特征提取

為了使用CNN提取視頻幀特征，具體的做法是在CNN的F7和F8之間加入一個128節點的隱藏層H，其中的神經元狀態用Sigmoid函數近似至{0, 1}。

深度卷積神經網絡內的初始權值設定為從ImageNet數據庫訓練得來的權值，隱藏層H和最終層F8的權值被隨機初始化，之后在目標庫上進行微調訓練。隨著微調訓練的進行，這些隨機值逐漸變得更加適應監督深度學習[10]，從而能夠提取出視頻幀特征。

訓練完成后，將視頻采樣幀輸入網絡，隱藏層H的神經元狀態就是我們需要的128維特征值。

2.4 使用k-d樹為視頻幀建立索引

k-d樹是一種多維二叉查找樹，主要用于存儲關聯性搜索所需的信息[4]。以往的視頻近似拷貝檢索算法很多都使用了LSH等哈希方法來建立索引，目的是為了快速剔除大量不相關的視頻。但這類哈希方法只統計了視頻是否加入候選，沒有其他額外信息。與此相對地，利用k-d樹進行最近鄰搜索雖然速度稍慢，但可以在產生候選的同時附加一些額外的相似度信息，后續步驟可以以此為參考。

在建立索引時，只需將視頻庫內視頻的采樣幀特征值逐一加入k-d樹即可。在執行近似檢索時，利用所建立的k-d樹對查詢視頻的每一幀特征執行一次最近鄰(KNN)搜索，找出與其距離最近(換句話說，最為相似)的3個視頻庫中的視頻幀并記錄這三個視頻幀所屬的視頻編號，將其交給后續的相似度計算步驟。

假設視頻庫中共有編號為0～m-1的m個視頻，輸入視頻由n個采樣幀f1,f2,…,fn表示，k-d樹返回的f1,f2,…,fn的最近鄰所屬的視頻編號分別為V11,V12,V13,V21,V22,…,Vn3∈[0,m-1]。本算法用p0,p1,…,pm-1來統計視頻庫中的m個視頻作為最近鄰搜索結果的次數，換句話說，p0,p1,…,pm-1初始值為0，之后遍歷所有的Vij，其中的每一個都會使對應的pvij增加1。

最終，p0,p1,…,pm-1中存放了視頻庫中的m個視頻作為最近鄰搜索結果的次數，也即這些視頻中的幀與查詢視頻中的幀相似的個數。不難想象，這些數字體現了其對應視頻與輸入視頻的相似程度，數值越大，說明其對應視頻與輸入視頻之間相似幀的數量越多，兩個視頻之間的相似程度也就越大。然而，這終究只是根據特征值進行近似最近鄰搜索的結果，并不能完全準確地代表候選視頻與輸入視頻之間的相似度，可以將其理解為候選視頻與輸入視頻相似的可能性。為此，定義候選視頻的置信度如下：

(1)

式中：1為輸入視頻的總長度。本算法將C0,C1,…,Cm按照降序進行排序，并選取其中數值最大的5個視頻作為候選視頻。

2.5 計算視頻相似度

給定一個查詢視頻，前面的索引步驟篩選出了一些候選視頻，成功地將近似視頻的范圍縮小至候選范圍內。雖然這些候選視頻與詢問視頻相似的概率很高，但并不是已經確定了它們和詢問視頻互為近似拷貝，因此需要進一步的檢測以確定最終的近似拷貝檢索結果。本算法采用的方法是逐對比較兩個視頻的特征值，用歐氏距離衡量兩個特征值之間的距離，得到所有特征值之間的距離信息后以此計算候選視頻與查詢視頻之間的相似度。

為了衡量候選視頻與輸入視頻的相似度，對于由采樣幀x1,x2,…,xm代表的視頻Sx(x1,x2,…,xm)和由采樣幀y1,y2,…,ym代表的視頻Sy(y1,y2,…,yn)，定義采樣幀xi與yj之間的距離f(i,j)為：

(2)

式中：D(i,j)為xi與yj之間的歐氏距離,H(xi,k)為xi的特征值的第k位：

(3)

從而，Sx與Sy的相似度定義為：

(4)

式中：d為查詢視頻與候選視頻的視頻長度差，k為參數。最終的WS值域在0到1之間。

最終，將所有候選的相似度由大到小排序，并選取其中與查詢視頻相似度大于特定閾值的候選作為最終的近似拷貝檢索結果輸出。在實際使用中，需要根據數據集情況、用戶需求等因素調整、選取合理的閾值。

3 實驗與評估

3.1 數據集

為驗證算法的效果，我們使用TRECVID[5]中的IACC.1.tv10.training視頻集作為數據集進行實驗，其中包括大約3 200部公開的網絡視頻。我們從中選取1 000部互不重復的長度在3.6分鐘左右的視頻，總長度為3 616分鐘，總大小約為14.3 GB。

3.2 實驗方法

本次實驗首先以選出的1 000部視頻作為離線視頻庫，按照第二節所述的方法為其提取特征并建立索引。之后，從中隨機選取100部視頻，對它們進行亮度改變、加入字幕、裁切、縮放、旋轉(90度和180度)、加入水印、抽幀(10幀)，以及打亂時序操作，加上原始的100部視頻，以此作為10組查詢視頻。

將10組查詢視頻輸入系統進行視頻近似拷貝檢索，在0～1.5之間選取16組不同的置信度閾值T進行實驗，得出候選后分別計算它們與查詢視頻的相似度，并選取相似度最高的視頻作為系統輸出。

本次實驗運行在Ubuntu系統服務器上，CPU為i7-5960X 3.00 GHz，GPU為(4x) NVIDIA GeForce GTX TITAN X，內存總大小為125 GB。

最終運行效率方面，為1 000部總長度3 616分鐘的視頻建立索引總計耗時129分鐘，耗時僅為視頻總長度的3.57%；執行全部100次查詢(總長度為361分鐘)總計耗時13分鐘，僅為查詢視頻長度的3.6%。索引文件大小為55.16 MB，僅為視頻總大小的0.38%。

3.3 實驗結果

實驗結果表明，由于選取了特定的特征提取和建立索引方法，本系統對字幕、裁切、縮放、水印、抽幀及打亂時序這六類近似拷貝有較好的識別能力，而對亮度變化和旋轉產生的近似拷貝不能很好地處理。實驗的平均準確率與召回率如圖2所示。

圖2 算法的平均Precision-Recall

為了橫向對比本算法的效果，本次實驗在相同的數據集上運行了文獻[11]中提出的方法，兩次實驗均選用最佳參數設置，實驗結果如圖3所示。

圖3 兩種算法的P-R對比

以上實驗結果表明，本算法能夠有效完成視頻近似拷貝檢索任務。這是由于本算法使用了合理的特征提取方法，通過在網絡中加入隱藏層，算法得以快速提取出包含足夠信息的特征值，避免了對網絡卷積層的大量計算。之后通過k-d樹為幀特征建立索引，算法得以快速找出與查詢視頻相似的視頻。

此外，為了對比本算法與傳統算法的效果，本次實驗在相同的數據集上運行了文獻[2]中提出的傳統方法，實驗結果如圖4所示。

圖4 五種情況的Precision對比(%)

從圖中可以看出，本算法的綜合表現優于文獻[2]中的方法，僅對亮度變化等的處理能力不如文獻[2]。如第一節所述，文獻[2]的局限性在于它使用的是一種基于像素序數和空間信息的特征，使其能夠較好地處理亮度變化，而對于水印、裁剪等局部空間變化的處理能力較差。

4 結 語

本文針對視頻近似拷貝檢測進行研究，使用深度學習方法提取特征，k-d樹建立索引，計算輸入視頻和候選視頻的相似度，得到按相似度排序的視頻序列。

本文在公用數據集上對系統進行了一些實驗與測試，并與已有方法進行了對比，驗證了系統是有效且快速的，在視頻近似拷貝檢測領域具有實踐和推廣價值。

[1] Lin K,Yang H F,Hsiao J H,et al.Deep learning of binary hash codes for fast image retrieval[C]//Proceeding of The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2015:27-35.

[2] Paisitkriangkrai S,Mei T,Zhang J,et al.Clip-based hierarchical representation of near-duplicate video detection[J].International Journal of Computer Mathematics,2011,88(18):3817-3833.

[3] Ciresan D,Meier U,Schmidhuber J.Multi-column deep neural networks for image classification[C]//Proceeding of The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2012:3642-3649.

[4] Friedman J H,Bentley J L,Finkel R A.An algorithm for finding best matches in logarithmic expected time[J].ACM Transactions on Mathematical Software,1977,3(3):209-226.

[5] Over P,Awad G,Michel M,et al.Trecvid—An overview of the goals, tasks, data, evaluation mechanisms and metrics[C]//Proceeding of TRECVid,2014:1-52.

[6] Benevenuto F,Duarte F,Rodrigues T,et al.Understanding video interactions in Youtube[C]//Proceeding of the 16th ACM international conference on Multimedia,2008:761-764.

[7] Beygelzimer A,Kakade S,Langford J.Cover trees for nearest neighbor[C]//Proceeding of the 23th international conference on Machine learning (ICML),2006:97-104.

[8] Wan J,Wang D,Hoi S C H,et al.Deep learning for content-based image retrieval:A comprehensive study[C]//Proceeding of the 22nd ACM international conference on Multimedia,2014:157-166.

[9] Oquab M,Bottou L,Laptev I,et al.Learning and transferring mid-level image representations using convolutional neural networks[C]//Proceeding of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2014:1717-1724.

[10] Babenko A,Slesarev A,Chigorin A,et al.Neural codes for image retrieval[C]//European Conference on Computer Vision(ECCV),2014:584-599.

[11] Wang L,Bao Y,Li H J,et al.Compact CNN Based Video Representation for Efficient Video Copy Detection[C]//Proceeding of International Conference on Multimedia Modeling,2017:576-587.

[12] Kordopatis-Zilos G,Papadopoulos S,Patras L,et al.Near-Duplicate Video Retrieval by Aggregating Intermediate CNN Layers[C]//Proceeding of International Conference on Multimedia Modeling,2017:251-263.

[13] Krizhevsky A,Sutskever I,Hinton G.ImageNet classification with deep convolutional neural networks[C]//Proceeding of Neural Information Processing System 25,2012:1106-1114.