一種基于加速近端梯度法的視頻散列算法研究

軒璐

(河南省三門峽職業(yè)技術學院信息傳媒學院，河南三門峽472000)

一種基于加速近端梯度法的視頻散列算法研究

軒璐

(河南省三門峽職業(yè)技術學院信息傳媒學院，河南三門峽472000)

散列算法已經被廣泛應用于視頻數據的索引。然而，當前大多數視頻散列方法將視頻看成是多個獨立幀的簡單集合，通過綜合幀的索引來對每個視頻編制索引，在設計散列函數時往往忽略了視頻的結構信息。首先將視頻散列問題建模為結構正規(guī)化經驗損失的最小化問題。然后提出一種有監(jiān)管算法，通過利用結構學習方法來設計高效的散列函數。其中，結構正規(guī)化利用了出現于視頻幀(與相同的語義類別存在關聯)中的常見局部視覺模式，同時對來自同一視頻的后續(xù)幀保持時域一致性。證明了通過使用加速近端梯度(APG)法可有效求解最小化目標問題。最后，基于兩個大規(guī)模基準數據集展開全面實驗(150 000個視頻片斷，1 200萬幀)，實驗結果證明了該方法性能優(yōu)于當前其他算法。

視頻散列;幀;索引;結構學習;局部視覺模式;加速近端梯度法

當前大多數視頻搜索引擎主要依靠文本關鍵字匹配而不是視頻內容索引。這是由于視頻內容索引技術除了人們都知道的語義間隙問題外，另一瓶頸問題就是計算成本太高，因為當處理大量視頻片斷時，低層次視覺特征的詳細比較成本太大。但是新近出現的基于散列的近似最近鄰搜索(ANN)方法為大規(guī)模視頻檢索提供了一種高效方法［1］。人們對散列學習技術進行了廣泛研究，通過結合機器學習技術提出了多種散列算法［2-3］。雖然這些散列算法可以直接用于編制視頻數據的索引［4-5］，其性能優(yōu)異，但是它們都無法對視頻片斷中的具體結構信息進行有效編碼。鑒于此，本文研究的重點是利用結構信息來設計新的散列算法，從而提高視頻檢索應用的效率和效果。

1 相關工作

隨著互聯網上大規(guī)模視頻數據的激增，視頻索引和檢索相關技術的研究逐漸成為目前的熱點問題，相繼有眾多研究者提出了一系列有代表性的方案，如馮柏嵐等人［6］提出一種基于多模態(tài)概念關聯圖的視頻檢索方法。首先通過分析查詢與概念之間的組織關系得到網狀關系模型描述，并基于該模型構建概念關聯圖;然后采用正交的概念融合方法計算視頻索引值，用于視頻檢索。與多種典型的基于概念的視頻檢索方法相比，文中方法的平均檢索精度增幅達14.6% ～86.2%。李濤等人［7］提出了一種基于自然語言的方法來實現基于內容的視頻檢索，用戶可以用自然語言和系統進行交互，從而方便快捷地找到自己想要的視頻片段。該方法使系統能夠處理用戶提出的自然語言問題，根據問題構建簡潔明了的問題模板，用問題模板與系統中已建的描述視頻的模板進行匹配，從而降低了視頻檢索問題的復雜度，提高了系統的易用性。

另外，目前也有一些工作［8-10］研究如何確定具體的散列函數以便對視頻等結構化數據編制索引，Cao等人［9］提出子模散列算法對視頻編制索引。Song等人［10］提出基于多種特征的散列算法，實現了視頻的近重復檢測。然而，這些視頻散列算法往往利用局域性敏感散列和譜散列等傳統的散列方法生成二進制碼。而且這些算法均沒有考慮使用視頻共通性和視頻時域一致性等具體的結構信息來設計不同結構的散列函數，進而對視頻編制索引。

為了解決上述問題，本文提出利用結構信息來設計新的視頻散列算法。尤其在學習過程中考慮兩種重要結構信息類型。第一種是空間結構信息，稱為區(qū)分性局部視覺共通性。很顯然，雖然每個視頻片斷包含重要的局部視頻模式，但是屬于同一語義類別的視頻只共享少量區(qū)分性局部特征。例如，圖1中“喂養(yǎng)動物”事件這一視頻的特征可由視頻模式部分稀疏集合描述(如圖1中的“眼睛”和“手”)。具體思路與稀疏編碼類似，只有少部分碼字或特征維度有非0權重。第二種是時域一致性。本文希望后續(xù)幀保持類似的視覺外觀。因此，散列方法應該確保后續(xù)幀的散列碼盡量類似(圖1)。為了兼顧這兩種類型的視頻結構特征，提出一種支持結構學習的有監(jiān)督算法，為視頻索引設計高效的線性散列函數。將目標定義為關于結構正規(guī)化經驗損失函數的最小化問題。最后，使用APG方法來高效求解最小化問題?；趦蓚€大規(guī)模視頻基準數據集的全面實驗驗證了本文視頻散列算法的優(yōu)異性能。

圖1 本文散列碼生成方法應用到“喂養(yǎng)動物”事件類別視頻時的相關結果

2 基于結構學習的視頻散列算法

本節(jié)將給出基于結構學習的視頻散列算法。首先給出相關標記法和定義，然后給出問題定義。

2.1 標記法和定義

已知一個視頻幀x，想要學習一個K比特二進制碼c∈ 0，{ }1K，因而需要設計K個二進制散列。在本文中，出于簡潔和效率考慮，選用線性散列函數。具體來說，第k個散列函數 (k=1，…，K)可被定義為

來自視頻Xi和Xj的兩個幀xia和xjb的散列碼的漢明(Hamming)距離定義為

以上述定義為基礎，視頻Xi和Xj間的Hamming距離定義為

這就是說，兩個視頻間的Hamming距離等于每對幀的平均Hamming距離。這一定義以如下基本假設為前提:一個視頻內的大部分幀應該有助于衡量兩個視頻間的距離。然而，由于sgn函數的離散特性，所以上述函數非常復雜。因此，本文的處理方法是將sgn替換為其符號數值以放松距離函數的定義，并將上述距離重寫為

式中:W=[w1，…，wk]∈Rd×K是由所有散列函數系數構成的矩陣。

2.2 問題描述

本文目標是學習一個系數矩陣W，該矩陣既可傳遞區(qū)分性信息又綜合了視頻的時域信息。定義如下目標函數，通過使結構正規(guī)化成本函數最小來學習散列函數

本文目標函數的思路如下:‖W‖2，1的最小化可以保證矩陣W只有少量的行非0。因為W的每一行都將乘以特征的一個具體維度，所以使之為0將會丟棄通過散列函數學習而獲得的特征維度的影響。于是，通過矩陣W的非0行可以選擇部分特征維度。被選擇的特征對應于與某種視頻類別相關的視頻幀的局部常見模式，這些模式傳達了區(qū)分性信息?！琖xi，t-Wxi，t+1‖∞的最小化可以保證兩個連續(xù)幀的散列向量盡可能相似，也就是說，鼓勵兩個散列向量的逐位差值的最大絕對值為0。于是，可在為視頻所有幀生成的散列碼中保留結構信息。請注意這里使用?∞范數而不是?1范數，因為?∞范數可進一步約束連續(xù)幀的兩個散列向量互相之間比較接近。通過上述兩個正規(guī)化因子，便可將視頻的結構信息全面編碼進生成的Hamming空間中。

基于?1損失(loss)，將式(5)中的損失函數定義為

有了這一損失項，將監(jiān)督信息納入散列函數學習過程中，進而獲得區(qū)分性二進制碼。不失一般性，簡單設置δ=1。請注意，也可使用鉸鏈損失函數或最小二乘損失函數作為損失函數。式(5)中的目標函數是非凸函數，因此可以實現局部最優(yōu)。在下一節(jié)將給出一種高效的優(yōu)化方法。

3 優(yōu)化方法

在式(5)中，由于?2，1范數和?∞范數正規(guī)化因子的非平滑性，所以無法計算W的梯度。首先，證明通過使用對偶范數和平滑近似可以計算出?2，1范數和?∞范數的梯度。然后，使用APG方法求解最優(yōu)化問題。

3.1 平滑近似

通過平滑近似來求解式(7)。首先將目標函數分解為如下兩項之和

于是，根據式(6)便可以計算出f(W)的子梯度。然而，由于r(W)的梯度不具有平滑性，因此無法直接計算。因此需要給出平滑近似，以便計算出它的梯度。本文使用如下的平滑函數［11］來近似r(W)

式中:μ是控制近似精度的平滑參數;〈·，·〉表示內積運算符;wi表示矩陣W的第i行;v和u分別是關于wi和(W·)i的輔助變量向量。本文設置μ為10-4。

3.2 基于AP進行優(yōu)化

對固定的μ，對下式最小化

式中:Fμ是F的精度性為μ的近似，同時，它是可微的，且梯度為

式中:

于是得出

現在可以使用APG來優(yōu)化Fμ(W)。優(yōu)化步驟如下:

利用APG求解式(13)

2)Initialize:根據式(18)計算 LFμ，隨機初始化，W(0)，Z(0)∈Rd×K和η(0)←0，t←0。

3)repeat。

5)根據式(14)計算?Fμ(α(t))。

9)until收斂。

10)Output W(t)。

4 仿真實驗

本節(jié)利用哥倫比亞消費類視頻(CCV)［13］和TRECVID多媒體事件檢測(MED)2012視頻數據集進行全面的實驗和比較。稍后給出兩個數據集的具體情況。為了證明使用視頻時間和空間結構性能的優(yōu)勢，對基于本文結構學習的散列算法多個版本進行測試，并在實驗中與下面6種典型的散列算法做比較:1)譜散列算法［14］;2)基于連續(xù)投影學習的散列算法(SPLH)［2］;3)非結構化視頻散列算法(UVH)，忽略視頻的結構算法，通過將式(5)中的λ和γ設為0，進而根據幀特征來學習散列函數;4)只支持區(qū)分性共通性的視頻散列算法(VHD)，將式(5)中的γ設為0即可;5)只支持時間一致性的視頻散列算法(VHD)，將式(5)中的λ設為0即可;6)支持區(qū)分性共通性和時間一致性的視頻散列算法(VHDT)。請注意，SH和SPLH算法均將每個視頻看成是獨立視頻幀的合成，通過融合幀的散列碼對視頻編制索引［9］。此外，SH和SPLH為散列碼公開可用的典型散列算法，因此選擇這兩個算法做比較。雖然最近出現了一些新的視頻散列算法［9-10］，但是它們基于LSH等標準的散列方法，且需要子模塊或多個特征表示等具體設置，因此在本實驗中沒有作為標準的比較算法。

4.1 評估和設置

采用文獻［2］的評估法則及以下評估指標:1)漢明排序:所有視頻片斷根據它們與查詢視頻的漢明距離進行排序;2)散列表:構建一個散列表，返回落入查詢樣本半徑為r(本文中r=2)的漢明球范圍內的所有樣本。因為每個查詢視頻表示為與視頻幀對應的一組二進制碼，于是采用如下查詢策略來返回最近鄰(NN)視頻片斷。對基于漢明排序的評估方法，通過式(3)全面計算并排序查詢樣本和數據集樣本間的視頻漢明距離，即可返回最近視頻片斷。對基于散列表的評估方法，首先對查詢視頻幀的各個散列碼向量，檢索漢明半徑為2的范圍內的最近鄰幀。然后，如果某個視頻的合成幀被任一查詢幀成功命中，則將該視頻看成最近鄰視頻候選。對這些候選最近鄰視頻進行排序的一種直觀方法就是計算每個視頻的命中頻率(基于該視頻的總幀數進行歸一化)。

漢明排序的質量評估性能更高，但是其復雜度為線性復雜度。散列查詢強調的是搜索速度，因為查詢復雜度往往是時間常數，但是使用非常長的散列碼時搜索質量不佳，于是在漢明半徑為r的范圍內返回為空，導致查詢失敗。

對SH和SPLH，使用文獻［2，14］中給出的最優(yōu)設置。對本文方法，使用交叉驗證來確定適當的參數，即權重λ和γ。此外，對所有有監(jiān)督和半監(jiān)督方法，隨機選擇部分被標記樣本作為CCV和TRECVID數據集的訓練數據。

部署本文方法的工作站的配置為:Intel XeonX5660，2.8 GHz CPU和8 Gbyte內存。圖2給出了本文實驗迭代優(yōu)化的收斂過程。可以看出，目標函數在60次迭代后便可收斂到局部最小，因此收斂速度很快。例如，在本文CCV數據集的實驗中，從算法中的第3步到第9步，迭代一次平均使用6.3 s左右的時間。圖3給出了SPLH和本文VHDT方法的訓練時間，可以發(fā)現，這兩個方法的計算時間相當。這表明，本文方法的計算復雜度與當前散列方法相當。此外，通過實驗證明，本文方法即使初始化不同，但是性能差異很小，說明本文方法對初始化的敏感度較低。

圖2 CCV數據集實驗的收斂曲線

圖3 SPLH和本文VHDT方法的訓練時間比較

4.2 CCV數據集

哥倫比亞消費類視頻(CCV)［13］包含9 317個You-Tube視頻，涉及20多種語義類別。在本文實驗中，從每種語義類別中隨機選擇5個視頻作為被標記數據用于訓練，選擇每種類別的另外25個視頻作為查詢視頻用于測試散列性能。于是，有100個訓練視頻和500個查詢視頻。剩余的8 717個視頻作為數據集樣本。每2 s對關鍵視頻幀均勻采樣，每個視頻至少有30個關鍵視頻。對每個關鍵視頻，提取關鍵點上的128維SIFT特征［15］，并通過BoW量化來獲得圖像表示［16］。使用兩種不同的關鍵點稀疏檢測器，即DoG檢測器和Hessian-Affine檢測器。最后，每個視頻關鍵幀表示為一個5 000維BoW特征。

在實驗中，基于不同長度的散列碼(12～64 bit)評估性能。圖4a給出了不同方法500次查詢時的平均精度(MAP)。從結果中可以得出如下結論:1)本文VHDT方法性能始終遠優(yōu)于其他基準算法，證明了視頻散列策略的有效性;2)包括VHDT，VHD和VHT在內的所有基于結構化學習的散列方法，其MAP值高于UVH。這是因為，前述方法利用了視頻數據的結構化信息(區(qū)分性局部模式或連續(xù)幀的時域一致性)，而UVH方法在生成散列碼時顯得缺乏針對性，沒有考慮任何結構信息; 3)本文方法的VHDT方法的性能顯然優(yōu)于SH和SPLH等傳統散列方法。原因是這些方法只學習了圖像等簡單樣本的散列函數，因此不適合視頻數據;4)本文VDHT方法的性能優(yōu)于VHD和VHT，因為后種方法只考慮了視頻結構信息的一個方面。但是本文VHDT方法充分利用了結構信息，在實驗中的性能最優(yōu)。

圖4 不同算法運行于CCV數據集且漢明半徑為2時的MAP/精度

在圖4b中給出了漢明半徑為2的范圍內的精度曲線，從圖中仍然可以看到本文方法的性能優(yōu)勢。然而，當使用的散列碼更長時，所有方法的精度開始下降。這是因為散列比特的數量上升時，落入桶內的樣本數量呈現指數規(guī)律下降，導致漢明半徑為2時范圍內返回為空。在先前文獻［2］中也觀察到類似的性能下降現象。同時，相比之下，VHDT方法的性能最優(yōu)。

4.3 TRECVID MED 2012數據集

TRECVID MED是評估視頻語義事件檢測的基準數據集。本文實驗使用TRECVID MED 2012數據集［17］。整個數據集有150 000左右個視頻屬于25種語義事件類別。大約有10 000個視頻片斷具有真實的語義標簽。對每種視頻，每2 s提取關鍵幀，獲得的最終集合包含1 200多萬個視頻關鍵幀。TRECVID MED 2012數據集是公共研究領域帶有人工注釋的最大規(guī)模視頻數據集之一。由于本文對150 000個視頻只有部分真實標簽，基于兩種不同協議評估性能。第一種協議就是基于真實標簽對10 000個視頻展開評估，第二種協議就是根據本文標記的最先返回視頻對整個150 000個視頻展開評估。對每種協議，均采用CCV實驗中相同的特征提取流程。在訓練階段，從每種類別中隨機選擇5個被標記視頻(共有125個視頻)。

1)使用真實標記時10 000個視頻的實驗結果:此時，從每種類別中選擇25個被標記視頻作為查詢視頻片斷進行散列性能測試。圖5a和圖5b給出了MAP和精度方面不同方法的性能曲線。可以看出，本文方法的性能最優(yōu)。當散列比特變化時，仍然可以穩(wěn)定實現性能提升。實驗結果再次證明了本文方法的有效性。請注意，對TRECVID MED任務，大多數最新系統［18］使用支持向量機分類器作為主要技術，因為人們重點追求預測性能而忽略了效率因素。相反，本文散列算法的重點放在大規(guī)模視頻數據的實時檢索上。例如，對10 000個視頻進行非線性支持向量機內核計算需要數小時，而使用基于散列的方法后，從整個數據集搜索類似的視頻片斷只需要10 s。因此，由于技術目的完全不同，因此不宜將本文方法與TRECVID MED 2012正式結果直接比較。

2)對150 000個視頻的運行結果:由于本文沒有150 000個視頻的所有標簽，所以無法計算漢明半徑為2時的MAP和精度。于是，只給出每種方法最先返回的100個視頻的精度。從25個類別中每種選出帶有真實數據的5個視頻，并將這125個視頻作為查詢。生成64位的二進制碼以從150 000視頻數據集中搜索視頻。對每次查詢，檢索漢明半徑為2的NN最近鄰視頻，然后選擇歸一化幀命中頻率排名前100的視頻。最后，對前100個視頻中沒有被貼標簽的視頻，手動注釋上類別標簽。計算了每次查詢前100個視頻的精度，并在表1中給出了125次查詢時的平均性能?？梢钥闯?，本文方法的性能最優(yōu)。圖6給出了部分查詢視頻的關鍵幀及返回的前6個關鍵幀，其中，從上到下查詢分別為“木工”、“攀巖”和“車輛”，給出了前6個檢查結果，錯誤結果用邊框表示。結果表明，本文基于結構學習的視頻散列算法生成的視頻檢索結果的性能更優(yōu)，可靠性更高。

圖5 不同算法運行于TRECVID MED 2012數據集且漢明半徑為2時的MAP/精度

表1 使用64位散列碼且運行于150 000個視頻時前100個檢索視頻精度

5 結論

本文提出一種針對大規(guī)模視頻散列計算的結構學習算法。本文算法運行于有監(jiān)督背景下，基于?1范數的經驗損失通過視頻結構項進行正規(guī)化。具體來說，使用?2，1范數選擇訓練視頻中的部分特征維度，以描述區(qū)分性局部視覺模式，并在后續(xù)幀的二進制碼中使用?∞范數以便保證經過學習的漢明空間的時域一致性。最終目標是表述為一個基于?2，1范數和?∞范數正規(guī)化的最小化問題，并且使用APG方法進行優(yōu)化?；趦煞N大規(guī)模視頻數據集的全面實驗證明了本文方法的有效性。在下一步工作中，筆者將結合核空間對本文方法展開分析。

圖6 使用64位散列碼且對150 000個視頻的定性評估結果

［1］WANG J，WANG J，YU N，etal.Order preserving hashing for approximate nearest neighbor search［C］ //Proc.21st ACM International Conference on Multimedia.Barcelona，Spain:ACM Press，2013: 133-142.

［2］HEO J，LEEY，HE J，etal.Spherical hashing［C］//Proc.2012 IEEE Conference on Computer Vision and Pattern Recognition(CVPR).RI，USA:IEEE Press，2012:2957-2964.

［3］WANG J，KUMAR S，CHANG S.Semi-supervised hashing for largescale search［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2012，34(12):2393-2406.

［4］THEPADE S，SUBHEDARPAGE K，MALIA，etal.Performance gain of contentbased video retrieval technique using intermediate block truncation coding on different color spaces［C］//Proc.2013 International Conference on Communications and Signal Processing(ICCSP).Ongole，India:IEEE Press，2013:1017-1020.

［5］MIRONICA I，IONESCU B，UIJLINGS J，et al.Fisher kernel based relevance feedback for multimodal video retrieval［C］//Proc.3rd ACM International Conference on Multimedia Retrieval.Dallas，TX，USA: ACM Press，2013:65-72.

［6］馮柏嵐，包蕾，曹娟，等.基于多模態(tài)概念關聯圖的視頻檢索［J］.計算機輔助設計與圖形學學報，2010(5):827-832.

［7］李濤，王國營.在線學習視頻索引與檢索方法［J］.計算機工程與設計，2010(3):647-650.

［8］DOUZEM，JéGOU H，SCHMID C.An image-based approach to video copy detection with spatio-temporal post-filtering［J］.IEEE Trans. Multimedia，2010，12(4):257-266.

［9］CAO L，LIZ，MU Y，et al.Submodular video hashing:a unified framework towards video pooling and indexing［C］//Proc.20th ACM International Conference on Multimedia.Nara，Japan:ACM Press，2012: 299-308.

［10］SONG J，YANGY，HUANG Z，etal.Multiple feature hashing for realtime large scale near-duplicate video retrieval［C］//Proc.19th ACM International Conference on Multimedia.Scottsdale.AZ，USA:ACM Press，2011:423-432.

［11］NESTEROV Y.Smooth minimization of non-smooth functions［J］. Mathematical Programming，2005，103(1):127-152.

［12］DUCHI J，SHALEV-SHWARTZ S，SINGER Y，et al.Efficient projections onto the l1-ball for learning in high dimensions［C］//Proc. 25th ACM International Conference on Machine Learning.Helsinki，Finland:ACM Press，2008:272-279.

［13］JIANG Y，YE G，CHANG S，et al.Consumer video understanding:a benchmark database and an evaluation of human andmachine performance［C］//Proc.1st ACM International Conference on Multimedia Retrieval.Vancouver，Canada:ACM Press，2011:29-38.

［14］ ZHUANG Y，LIU Y，WU F，et al.Hypergraph spectral hashing for similarity search of social image［C］//Proc.19th ACM International Conference on Multimedia.Scottsdale，AZ，USA:ACM Press，2011: 1457-1460.

［15］TOEWSM，WELLSW.Efficient and robustmodel-to-image alignment using 3D scale-invariant features［J］.Medical Image Analysis，2013，17(3):271-282.

［16］MIKOLAJCZYK K，SCHMID C.Scale＆affine invariant interest point detectors［J］.International Journal of Computer Vision，2004，60(1): 63-86.

［17］TANG K，FEI L，KOLLER D.Learning latent temporal structure for complex event detection［C］//Proc.2012 IEEE Conference on Computer Vision and Pattern Recognition(CVPR).RI，USA:IEEE Press，2012:1250-1257.

［18］MERTENSR，LEIH，GOTTLIEB L，et al.Acoustic supermodels for large scale video event detection［C］//Proc.2011 Joint ACM Workshop on Modeling and Representing Events.Scottsdale，Arizona，USA: ACM Press，2011:19-24.

Research on Video Hashing Algorithm Based on Accelerated Proximal Gradient M ethod

XUAN Lu
(Sanmenxia Polytechnic，Henan Sanmenxia 472000，China)

Hashingmethodshave become popular for indexing video data.However，mostof the existing video hashingmethods treat videos as a simple aggregation of independent frames and index each video through combining the indexes of frames.The structure information of videos is often neglected in the design of hash functions.In this paper，firstly，the video hashing problem ismodeled into aminimization problem over a structure-regularized empirical loss.And a supervised method is proposed that explores the structure learning techniques to design efficient hash functions.In particular，the structure regularization exploits the common local visual patterns occurring in video frames thatare associated with the same semantic class，and simultaneously preserves the temporal consistency over successive frames from the same video.It is proved that theminimization objective problem can be efficiently solved by an Accelerated Proximal Gradient(APG)method.Extensive experiments on two large video benchmark datasets(up to around 150 000 video clipswith over 12 million frames)show that the proposed method significantly outperforms the state of the art hashingmethods.

video hashing;frames;indexing;structure learning;local visual patterns;accelerated proximal gradientmethod

TN911.73

A

軒 璐(1981—)，女，碩士，講師，主要研究方向為視頻檢索技術、圖像重構算法。

?? 雯

2014-04-15

【本文獻信息】軒璐.一種基于加速近端梯度法的視頻散列算法研究［J］.電視技術，2014，38(23).

國家自然科學基金項目(61373070/F020501)