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

軒璐

(河南省三門(mén)峽職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院，河南三門(mén)峽472000)

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

軒璐

(河南省三門(mén)峽職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院，河南三門(mén)峽472000)

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

視頻散列;幀;索引;結(jié)構(gòu)學(xué)習(xí);局部視覺(jué)模式;加速近端梯度法

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

1 相關(guān)工作

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

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

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

圖1 本文散列碼生成方法應(yīng)用到“喂養(yǎng)動(dòng)物”事件類(lèi)別視頻時(shí)的相關(guān)結(jié)果

2 基于結(jié)構(gòu)學(xué)習(xí)的視頻散列算法

本節(jié)將給出基于結(jié)構(gòu)學(xué)習(xí)的視頻散列算法。首先給出相關(guān)標(biāo)記法和定義，然后給出問(wèn)題定義。

2.1 標(biāo)記法和定義

已知一個(gè)視頻幀x，想要學(xué)習(xí)一個(gè)K比特二進(jìn)制碼c∈ 0，{ }1K，因而需要設(shè)計(jì)K個(gè)二進(jìn)制散列。在本文中，出于簡(jiǎn)潔和效率考慮，選用線(xiàn)性散列函數(shù)。具體來(lái)說(shuō)，第k個(gè)散列函數(shù) (k=1，…，K)可被定義為

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

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

這就是說(shuō)，兩個(gè)視頻間的Hamming距離等于每對(duì)幀的平均Hamming距離。這一定義以如下基本假設(shè)為前提:一個(gè)視頻內(nèi)的大部分幀應(yīng)該有助于衡量?jī)蓚€(gè)視頻間的距離。然而，由于sgn函數(shù)的離散特性，所以上述函數(shù)非常復(fù)雜。因此，本文的處理方法是將sgn替換為其符號(hào)數(shù)值以放松距離函數(shù)的定義，并將上述距離重寫(xiě)為

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

2.2 問(wèn)題描述

本文目標(biāo)是學(xué)習(xí)一個(gè)系數(shù)矩陣W，該矩陣既可傳遞區(qū)分性信息又綜合了視頻的時(shí)域信息。定義如下目標(biāo)函數(shù)，通過(guò)使結(jié)構(gòu)正規(guī)化成本函數(shù)最小來(lái)學(xué)習(xí)散列函數(shù)

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

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

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

3 優(yōu)化方法

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

3.1 平滑近似

通過(guò)平滑近似來(lái)求解式(7)。首先將目標(biāo)函數(shù)分解為如下兩項(xiàng)之和

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

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

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

對(duì)固定的μ，對(duì)下式最小化

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

式中:

于是得出

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

利用APG求解式(13)

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

3)repeat。

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

9)until收斂。

10)Output W(t)。

4 仿真實(shí)驗(yàn)

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

4.1 評(píng)估和設(shè)置

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

漢明排序的質(zhì)量評(píng)估性能更高，但是其復(fù)雜度為線(xiàn)性復(fù)雜度。散列查詢(xún)強(qiáng)調(diào)的是搜索速度，因?yàn)椴樵?xún)復(fù)雜度往往是時(shí)間常數(shù)，但是使用非常長(zhǎng)的散列碼時(shí)搜索質(zhì)量不佳，于是在漢明半徑為r的范圍內(nèi)返回為空，導(dǎo)致查詢(xún)失敗。

對(duì)SH和SPLH，使用文獻(xiàn)［2，14］中給出的最優(yōu)設(shè)置。對(duì)本文方法，使用交叉驗(yàn)證來(lái)確定適當(dāng)?shù)膮?shù)，即權(quán)重λ和γ。此外，對(duì)所有有監(jiān)督和半監(jiān)督方法，隨機(jī)選擇部分被標(biāo)記樣本作為CCV和TRECVID數(shù)據(jù)集的訓(xùn)練數(shù)據(jù)。

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

圖2 CCV數(shù)據(jù)集實(shí)驗(yàn)的收斂曲線(xiàn)

圖3 SPLH和本文VHDT方法的訓(xùn)練時(shí)間比較

4.2 CCV數(shù)據(jù)集

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

在實(shí)驗(yàn)中，基于不同長(zhǎng)度的散列碼(12～64 bit)評(píng)估性能。圖4a給出了不同方法500次查詢(xún)時(shí)的平均精度(MAP)。從結(jié)果中可以得出如下結(jié)論:1)本文VHDT方法性能始終遠(yuǎn)優(yōu)于其他基準(zhǔn)算法，證明了視頻散列策略的有效性;2)包括VHDT，VHD和VHT在內(nèi)的所有基于結(jié)構(gòu)化學(xué)習(xí)的散列方法，其MAP值高于UVH。這是因?yàn)椋笆龇椒ɡ昧艘曨l數(shù)據(jù)的結(jié)構(gòu)化信息(區(qū)分性局部模式或連續(xù)幀的時(shí)域一致性)，而UVH方法在生成散列碼時(shí)顯得缺乏針對(duì)性，沒(méi)有考慮任何結(jié)構(gòu)信息; 3)本文方法的VHDT方法的性能顯然優(yōu)于SH和SPLH等傳統(tǒng)散列方法。原因是這些方法只學(xué)習(xí)了圖像等簡(jiǎn)單樣本的散列函數(shù)，因此不適合視頻數(shù)據(jù);4)本文VDHT方法的性能優(yōu)于VHD和VHT，因?yàn)楹蠓N方法只考慮了視頻結(jié)構(gòu)信息的一個(gè)方面。但是本文VHDT方法充分利用了結(jié)構(gòu)信息，在實(shí)驗(yàn)中的性能最優(yōu)。

圖4 不同算法運(yùn)行于CCV數(shù)據(jù)集且漢明半徑為2時(shí)的MAP/精度

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

4.3 TRECVID MED 2012數(shù)據(jù)集

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

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

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

圖5 不同算法運(yùn)行于TRECVID MED 2012數(shù)據(jù)集且漢明半徑為2時(shí)的MAP/精度

表1 使用64位散列碼且運(yùn)行于150 000個(gè)視頻時(shí)前100個(gè)檢索視頻精度

5 結(jié)論

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

圖6 使用64位散列碼且對(duì)150 000個(gè)視頻的定性評(píng)估結(jié)果

［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)概念關(guān)聯(lián)圖的視頻檢索［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010(5):827-832.

［7］李濤，王國(guó)營(yíng).在線(xiàn)學(xué)習(xí)視頻索引與檢索方法［J］.計(jì)算機(jī)工程與設(shè)計(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，F(xiàn)inland: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，F(xiàn)EI 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—)，女，碩士，講師，主要研究方向?yàn)橐曨l檢索技術(shù)、圖像重構(gòu)算法。

?? 雯

2014-04-15

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

國(guó)家自然科學(xué)基金項(xiàng)目(61373070/F020501)