一種基于SimHash的海量視頻檢索方法

楚敏南++羅新高++白煜華

摘 要：針對(duì)海量視頻檢索，提出了一種基于SimHash的視頻相似性檢索方法。該方法的視頻特征提取部分首先采用視覺詞袋模型將視頻關(guān)鍵幀表示為詞袋模型向量，然后對(duì)高維詞袋模型向量建立魯棒的壓縮二值SimHash簽名；視頻相似幀查找部分首先置換SimHash簽名庫(kù)，并排序得到多張簽名表，然后在多張簽名表中按照數(shù)據(jù)量合理利用Bloom Filter算法精確匹配簽名表的置換部分，進(jìn)而根據(jù)精確匹配的結(jié)果高效查找漢明距離小于閾值的簽名，最后利用查找到的簽名對(duì)相關(guān)視頻進(jìn)行相似度計(jì)算，排序得到相似視頻的查詢結(jié)果。針對(duì)CC_WEB_VIDEO公開數(shù)據(jù)集的實(shí)驗(yàn)表明，該方法對(duì)大規(guī)模視頻的快速檢索是非常有效的。

關(guān)鍵詞：視頻檢索；視覺詞袋；SimHash；Bloom Filter

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.15913/j.cnki.kjycx.2015.18.009

目前，國(guó)內(nèi)外的視頻分享網(wǎng)站發(fā)展迅速，越來(lái)越多的人通過(guò)視頻分享網(wǎng)站、數(shù)字電視和微博等方式收看網(wǎng)絡(luò)視頻節(jié)目，并通過(guò)視頻網(wǎng)站上傳自制視頻與他人分享，網(wǎng)絡(luò)視頻點(diǎn)播量和觀看人數(shù)呈爆發(fā)式增長(zhǎng)態(tài)勢(shì)。因此，如何對(duì)海量視頻進(jìn)行快速、有效的相似性檢索逐漸成為研究熱點(diǎn)。

視頻相似性檢索的過(guò)程為：將視頻表示為視頻關(guān)鍵幀序列→提取關(guān)鍵幀序列的特征→通過(guò)特征匹配完成相似性檢索。在大規(guī)模視頻數(shù)據(jù)庫(kù)的條件下，需要高效、快速的特征匹配算法以滿足視頻檢索的實(shí)時(shí)性要求。目前，具體可采用以下6種方法：①引入min-hash算法對(duì)視覺詞匯建立min-hash簽名，并在檢索視頻片段時(shí)采用滑動(dòng)窗口依次匹配。②基于梯度方向重心的特征，使用kd-tree查詢候選幀，然后匹配特征序列。③基于層次的匹配算法匹配HSV的顏色直方圖。對(duì)于無(wú)法確定是否相似的視頻，可匹配局部特征。由于該方法需要確認(rèn)局部特征，所以，難以滿足實(shí)時(shí)性的要求。④基于LBP（Local Binary Pattern）與條件熵的時(shí)空特征方法。雖然該方法考慮了視頻數(shù)據(jù)處理規(guī)模過(guò)大的問(wèn)題，但使用倒排索引的方法召回視頻存在內(nèi)存占用過(guò)大和返回速率低的問(wèn)題。⑤基于LSH（Locality-sensitive hashing）算法，結(jié)合SURF（Speeded Up Robust Features）的特征，以投票的方式查找相似視頻片段。⑥利用LSH對(duì)高維向量進(jìn)行相似性檢索，并在P2P（peer-to-peer）環(huán)境下實(shí)現(xiàn)分布式檢索。該方法可應(yīng)用于需多次檢索的海量視頻數(shù)據(jù)庫(kù)。由于每次檢索都必須在節(jié)點(diǎn)間進(jìn)行多次查詢，所以時(shí)間復(fù)雜度過(guò)高。

鑒于此，本文提出了一種基于SimHash算法的海量視頻快速檢索方法。該方法首先提取了視頻關(guān)鍵幀的SURF特征，并得到BOVW（bag of words，視覺詞袋模型）向量，然后通過(guò)SimHash算法建立視頻的魯棒二值簽名，并在漢明距離檢索中利用Bloom Filter算法進(jìn)行高效匹配，最終得到相似視頻。實(shí)驗(yàn)表明，該方法對(duì)大規(guī)模視頻數(shù)據(jù)庫(kù)的快速檢索非常有效。

1 總體設(shè)計(jì)方案

本文中提出的方法的總體設(shè)計(jì)方案如圖1所示。整個(gè)框架分為2個(gè)步驟：①構(gòu)建視頻索引，如圖1中的實(shí)線所示。通過(guò)對(duì)特征的提取，將目標(biāo)視頻表示成Bovw特征向量，然后利用SimHash建立特征向量的簽名，生成基于Bloom Filter的簽名表。②查詢相似視頻，如圖1中的虛線所示。經(jīng)過(guò)特征提取，將查詢視頻表示為Bovw特征向量，利用基于Bloom Filter的SimHash簽名表檢索與查詢視頻對(duì)應(yīng)幀相似的幀集合，根據(jù)返回的相似幀進(jìn)行視頻相似度計(jì)算，最后重新排序得到相似視頻的查詢結(jié)果。

圖1 總體設(shè)計(jì)框圖

2 基于SIMHASH的海量視頻檢索方法

2.1 視頻關(guān)鍵幀的Bovw特征

在視頻檢索中，要先對(duì)視頻庫(kù)建立索引，設(shè)目標(biāo)視頻庫(kù)中有M個(gè)視頻，對(duì)于視頻Vi，1≤i≤M，本文先按固定時(shí)間間隔（1 s）提取視頻關(guān)鍵幀，然后去掉相似度比較大的相鄰視頻幀，同時(shí)，保留每個(gè)視頻幀的時(shí)間序列信息。在此情況下，1個(gè)視頻幀可表示為e={序號(hào)，時(shí)間戳，視頻幀圖像名，視頻幀圖像}。特征表示部分采用BOVW模型為視頻關(guān)鍵幀，進(jìn)而建立“視覺詞庫(kù)”。由于圖像中的特征點(diǎn)和視覺詞袋中的視覺詞匯并不像文檔中現(xiàn)成的單詞是直接可見的，因此，需要對(duì)圖像進(jìn)行特征提取和通過(guò)聚類得到視覺詞匯，具體過(guò)程如下：①利用SURF算法提取視頻關(guān)鍵幀的SURF特征點(diǎn)；②將所有SURF特征點(diǎn)集合在一起，然后使用Kmeans聚類算法對(duì)SURF特征點(diǎn)聚類，將相似的點(diǎn)聚成“視覺字典”，生成由N個(gè)視覺詞匯組成的視覺特征字典；③將從所有關(guān)鍵幀中提取的所有SURF特征劃歸到最接近的圖像視覺字典對(duì)象中，從而將視頻關(guān)鍵幀映射成1個(gè)N維的視覺詞袋向量，而視頻Vi可表示為多個(gè)N維向量的集合。

2.2 構(gòu)建SimHash簽名

為了高效地檢索視頻片段，本文利用SimHash建立視頻關(guān)鍵幀的BOVW向量簽名。將N維的BOVW向量轉(zhuǎn)換為f維SimHash簽名S的計(jì)算過(guò)程為：①將1個(gè)f維的向量V初始化為0，f維的二進(jìn)制數(shù)S初始化為0.②將Surf特征聚類中心的N個(gè)向量作為特征，利用傳統(tǒng)的Hash算法，在每個(gè)聚類中心向量上產(chǎn)生1個(gè)f位的簽名bi，1≤i≤N.③對(duì)于j=1～f，如果b的第j位為1，則V的第j個(gè)元素加上該特征的權(quán)重。否則，V的第j個(gè)元素減去該特征的權(quán)重。④如果V的第j個(gè)元素>0，則S的第j位為1，否則為0，輸出S作為簽名。

通過(guò)以上方法，視頻幀可表示為e=（viedo_name，id，time_stamp，SimHash）。其中，viedo_name為視頻名；id為此關(guān)鍵幀在視頻中的序號(hào)；time_stamp為視頻幀時(shí)間戳；SimHash為該視頻幀Bovw向量的簽名。

2.3 基于Bloom Filter的漢明距離檢索

Bloom Filter是一種快速、高效的匹配算法，其通過(guò)k個(gè)哈希函數(shù)將要存儲(chǔ)的變量a映射到m位的容器中。通過(guò)上述操作，可快速檢測(cè)某一條數(shù)據(jù)元素是否為集合中的成員之一。由此可見，Bloom Filter算法是通過(guò)犧牲出錯(cuò)率來(lái)?yè)Q取時(shí)間和空間的。在此算法中誤判的概率為：

. （1）

式（1）中：n為數(shù)據(jù)集中元素的個(gè)數(shù)；k為哈希函數(shù)個(gè)數(shù)；m為分配位向量的大小。

對(duì)于兩個(gè)視頻幀，生成L位的SimHash簽名后，如果漢明距離≤K，則認(rèn)為這兩個(gè)視頻幀相似。而查詢一個(gè)L比特的簽名在簽名庫(kù)中是否存在最多K比特不同的簽名，這被稱為漢明距離問(wèn)題。基于網(wǎng)頁(yè)爬蟲應(yīng)用提出了一種漢明距離的查詢方法，主要解決重復(fù)網(wǎng)頁(yè)檢測(cè)問(wèn)題。建立索引和利用漢明距離的具體步驟如下：

第一步，構(gòu)建索引。將L位的簽名分成r段，r≥K+1，在

簽名庫(kù)建立t張簽名表T1，T2，…，Tt，其中， ，每張

簽名表關(guān)聯(lián)兩個(gè)量，即整數(shù)bi與置換πi.初始化Bloom Filter結(jié)構(gòu)中為m位的向量，存儲(chǔ)n個(gè)元素值，對(duì)于表T1中的所有簽名，將前bi比特的數(shù)據(jù)生成Bloom Filter結(jié)構(gòu)BFi，因此，t張簽名表會(huì)對(duì)應(yīng)t個(gè)Bloom Filter結(jié)構(gòu)。

第二步，漢明距離檢索。對(duì)于查詢簽名sq，可在t張簽名表中檢索查詢SimHash簽名。

Input為查詢簽名sq、t張SimHash簽名表T1，T2，…，Tt和t張SimHash表對(duì)應(yīng)的Bloom Filter結(jié)構(gòu)BF1，BF2，…，BFt.

Output為漢明距離在K以內(nèi)的SimHash簽名列表。具體列表如表1所示。

表1 明距離在K以內(nèi)的SimHash簽名列表

1 for j=1～t

2 sq按πj進(jìn)行置換得到πj（sq），其前bj位為bj_bit，Q集合清空

3 if BF1.contains（bj_bit）=O then next j

4 for each element sx in Tj do

5 if High_bj_bit_equals（sx，πj（sq））then Q+=sx

6 end for

7 for each element sx in Q do

8 if Hamming_Distance（sq，sx） K then Result+=sx

9 end for

10 end for

11 return與sq簽名的漢明距離在K以內(nèi)的集合Result

表1中的3主要使用Bloom Filter算法過(guò)濾不在簽名表集合中的數(shù)據(jù)；4～6可實(shí)現(xiàn)二分查找；7～9可計(jì)算漢明距離在K以內(nèi)加入的Result集合。

2.4 視頻的相似度計(jì)算

對(duì)于待查詢的視頻，在提取視頻關(guān)鍵幀后，提取關(guān)鍵幀的Surf特征，建立詞袋模型向量，構(gòu)建SimHash簽名，根據(jù)漢明距離檢索得出與之相似的視頻關(guān)鍵幀，并將相似關(guān)鍵幀按照所屬視頻統(tǒng)計(jì)，計(jì)算最終的視頻相似度。視頻Vi與Vj的相似度采用如下公式計(jì)算：

. （2）

式（2）中：KFi和KFj為視頻Vi和Vj提取到的關(guān)鍵幀數(shù)目；KFi∩KFj為視頻Vi與Vj相似關(guān)鍵幀的數(shù)量，即通過(guò)漢明距離檢索得出相似視頻關(guān)鍵幀的數(shù)目；sim（Vi，Vj）為兩個(gè)視頻的相似度，∈[0，1]，通過(guò)計(jì)算相似視頻關(guān)鍵幀數(shù)量占總關(guān)鍵幀的比例計(jì)算，其值越高，表示兩個(gè)視頻越相似。

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

本文的實(shí)驗(yàn)環(huán)境如下：硬件采用Lenovo臺(tái)式機(jī)，處理器為Intel Core i3-2130，CPU主頻為3.40 GHz，內(nèi)存為4 G。實(shí)驗(yàn)數(shù)據(jù)集選擇CC_WEB_VIDEO，包含12 790個(gè)視頻，其中，查詢視頻有24個(gè)。視頻檢索常用的評(píng)估參數(shù)為查全率R、查準(zhǔn)率P和F值，其計(jì)算方法如下：

. （3）

. （4）

. （5）

首先分析SimHash中的L和K進(jìn)行，在L和K不同情況下的F值如圖2所示。

圖2 L和K不同情況下的F值

由圖2可知，當(dāng)L=64，K=4時(shí)，F(xiàn)值為0.933，為最大值，因此，取L=64，K=4.由于r≥K+1，所以，64位的SimHash簽名至少分成5段，則b1=13，b2=13，b3=13，b4=13，b5=12，簽名表的個(gè)數(shù)t=5.簽名表對(duì)應(yīng)的Bloom Filter結(jié)構(gòu)具體分析如下。

對(duì)于b1，b2，b3，b4，對(duì)應(yīng)段最多可能出現(xiàn)的情況為213=8 192，而b5=12，則最多出現(xiàn)212=4 096.如果存儲(chǔ)元素的個(gè)數(shù)n=8 192，分配位向量為m，哈希函數(shù)k個(gè)，則誤判率Perr的關(guān)系如表2所示。

表2 不同m，k情況下的誤判率Perr

m 單位/KB Perr k

10 000 1.220 703 0.559 1

20 000 2.441 406 0.319 2

30 000 3.662 109 0.175 3

40 000 4.882 813 0.097 3

50 000 6.103 516 0.054 4

由表2可知，Bloom Filter設(shè)置為m=50 000（6.1 KB），誤判率Perr為0.054，k設(shè)置為4，多消耗內(nèi)存30.5 KB。

對(duì)于上述算法，二分查找的時(shí)間復(fù)雜度為O（bi），即O（13）。因此，Bloom Filter的時(shí)間復(fù)雜度為O（4），當(dāng)查找的前bi比特能精確匹配時(shí)，時(shí)間復(fù)雜度為O（17），否則為O（4）。如果精確匹配的比例為P，則時(shí)間復(fù)雜度為O（17）×p+O（4）（1-p）=O（13）p+O（4）

表3 設(shè)置Bloom Filter檢索效果對(duì)比

視頻數(shù) 關(guān)鍵幀數(shù) 設(shè)置BF耗時(shí)/ms 不設(shè)置BF耗時(shí)/ms

5 8 510 5 7

10 17 020 7 11

100 170 200 49 86

500 851 000 202 377

由表3可知，設(shè)置Bloom Filter能明顯提高視頻檢索效率。當(dāng)視頻數(shù)在5以下時(shí)，檢索效率提高不明顯；檢索視頻數(shù)為500時(shí)，檢索效率能提高86%.

下面將本文提出的方法（L=64，K=4）與基于LBP（Local Binary Pattern）的時(shí)空特征方法和基于LSH對(duì)SURF特征投票查找相似視頻片段（SURF-LSH）的方法相比較。采用LBP和SURF-LSH作為對(duì)比對(duì)象是因?yàn)檫@兩種方法比其他方法有更高的查全率和準(zhǔn)確率，對(duì)比結(jié)果如圖3所示。

圖3 平均查全率、查準(zhǔn)率對(duì)比曲線

由圖3可知，采用LBP時(shí)，當(dāng)查全率>0.7時(shí)，準(zhǔn)確率明顯下降。本文按時(shí)間間隔每秒提取視頻關(guān)鍵幀，并采用魯棒的SURF特征構(gòu)建詞袋模型向量，保證了較高的準(zhǔn)確率和召回率。

采用SURF-LSH的準(zhǔn)確率略高于本文提出的方法，這是因?yàn)楸疚奶岢龅姆椒ú捎玫氖荢imHash算法，它在保證檢索效率的同時(shí)，比SURF-LSH降低了一定的準(zhǔn)確率，但通過(guò)圖4中平均檢索時(shí)間與視頻數(shù)量的關(guān)系可發(fā)現(xiàn)，對(duì)于海量視頻檢索，本文提出的方法更有效。隨著視頻個(gè)數(shù)的增加，檢索時(shí)間也會(huì)隨之增加，LBP和SURF-LSH的增長(zhǎng)速度明顯快于本文提出的的方法。

4 結(jié)束語(yǔ)

隨著海量視頻的出現(xiàn)，快速、高效的視頻相似性檢索變得越來(lái)越重要。本文提出了一種基于Bloom Filter算法進(jìn)行漢明距離檢索的方法，該方法可查找SimHash簽名庫(kù)所有簽名中漢明距離在K以內(nèi)的簽名，并將所有Bloom Filter結(jié)構(gòu)匯總在一起，組成類似BitMap的結(jié)構(gòu)。因此，在最終查詢漢明距離時(shí)，只計(jì)

算BitMap的并集即可。本文在CC_WEB_VIDEO視頻數(shù)據(jù)集中對(duì)上述方法進(jìn)行了檢驗(yàn)，測(cè)試結(jié)果表明，該方法能將匹配效率提高1倍以上。今后，我們將構(gòu)建更大規(guī)模的視頻數(shù)據(jù)庫(kù)，并結(jié)合分布式處理平臺(tái)Hadoop實(shí)驗(yàn)。

圖4 平均檢索時(shí)間與視頻數(shù)量的關(guān)系

參考文獻(xiàn)

[1]Shen Heng tao，Liu Jia jun，Huang Zi.Near-duplicate video retrieval： current research and future trends[J]. IEEE Multimedia，2013，PP（99）：1-10.

[2]Chiu CY，Wang HM.Time-series linear search for video copies based on compact signature manipulation and containment relation modeling[J].IEEE Transactions on Circuits andSystems for Video Technology，2010，20（11）：1603-1613.

[3]Chiu CY，Wang HM，Chen CS.Fast min-hashing indexing and robust spatio-temporal matching for detecting video copies[J].ACM Transactions on Multimedia Computing，Communications，and Applications，2010，6（2）：1-23.

[4]Lee S，Yoo C D.Robust video fingerprinting for content-based video identification[J].IEEE Transactions on Circuits and Systems for Video Technology，2008，18（7）：983-988.

[5]Bloom B.Space/time tradeoffs in Hash coding with allow-able errors[J].Communication of the ACM，1970，13（7）：422-426.

〔編輯：張思楠〕