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

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

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

關鍵詞：視頻檢索；視覺詞袋；SimHash；Bloom Filter

中圖分類號：TP391.41 文獻標識碼：A DOI：10.15913/j.cnki.kjycx.2015.18.009

目前，國內外的視頻分享網站發展迅速，越來越多的人通過視頻分享網站、數字電視和微博等方式收看網絡視頻節目，并通過視頻網站上傳自制視頻與他人分享，網絡視頻點播量和觀看人數呈爆發式增長態勢。因此，如何對海量視頻進行快速、有效的相似性檢索逐漸成為研究熱點。

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

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

1 總體設計方案

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

圖1 總體設計框圖

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

2.1 視頻關鍵幀的Bovw特征

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

2.2 構建SimHash簽名

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

通過以上方法，視頻幀可表示為e=（viedo_name，id，time_stamp，SimHash）。其中，viedo_name為視頻名；id為此關鍵幀在視頻中的序號；time_stamp為視頻幀時間戳；SimHash為該視頻幀Bovw向量的簽名。

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

Bloom Filter是一種快速、高效的匹配算法，其通過k個哈希函數將要存儲的變量a映射到m位的容器中。通過上述操作，可快速檢測某一條數據元素是否為集合中的成員之一。由此可見，Bloom Filter算法是通過犧牲出錯率來換取時間和空間的。在此算法中誤判的概率為：

. （1）

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

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

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

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

簽名表關聯兩個量，即整數bi與置換πi.初始化Bloom Filter結構中為m位的向量，存儲n個元素值，對于表T1中的所有簽名，將前bi比特的數據生成Bloom Filter結構BFi，因此，t張簽名表會對應t個Bloom Filter結構。

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

Input為查詢簽名sq、t張SimHash簽名表T1，T2，…，Tt和t張SimHash表對應的Bloom Filter結構BF1，BF2，…，BFt.

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

表1 明距離在K以內的SimHash簽名列表

1 for j=1～t

2 sq按πj進行置換得到π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以內的集合Result

表1中的3主要使用Bloom Filter算法過濾不在簽名表集合中的數據；4～6可實現二分查找；7～9可計算漢明距離在K以內加入的Result集合。

2.4 視頻的相似度計算

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

. （2）

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

3 實驗結果

本文的實驗環境如下：硬件采用Lenovo臺式機，處理器為Intel Core i3-2130，CPU主頻為3.40 GHz，內存為4 G。實驗數據集選擇CC_WEB_VIDEO，包含12 790個視頻，其中，查詢視頻有24個。視頻檢索常用的評估參數為查全率R、查準率P和F值，其計算方法如下：

. （3）

. （4）

. （5）

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

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

由圖2可知，當L=64，K=4時，F值為0.933，為最大值，因此，取L=64，K=4.由于r≥K+1，所以，64位的SimHash簽名至少分成5段，則b1=13，b2=13，b3=13，b4=13，b5=12，簽名表的個數t=5.簽名表對應的Bloom Filter結構具體分析如下。

對于b1，b2，b3，b4，對應段最多可能出現的情況為213=8 192，而b5=12，則最多出現212=4 096.如果存儲元素的個數n=8 192，分配位向量為m，哈希函數k個，則誤判率Perr的關系如表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設置為m=50 000（6.1 KB），誤判率Perr為0.054，k設置為4，多消耗內存30.5 KB。

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

表3 設置Bloom Filter檢索效果對比

視頻數 關鍵幀數 設置BF耗時/ms 不設置BF耗時/ms

5 8 510 5 7

10 17 020 7 11

100 170 200 49 86

500 851 000 202 377

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

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

圖3 平均查全率、查準率對比曲線

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

采用SURF-LSH的準確率略高于本文提出的方法，這是因為本文提出的方法采用的是SimHash算法，它在保證檢索效率的同時，比SURF-LSH降低了一定的準確率，但通過圖4中平均檢索時間與視頻數量的關系可發現，對于海量視頻檢索，本文提出的方法更有效。隨著視頻個數的增加，檢索時間也會隨之增加，LBP和SURF-LSH的增長速度明顯快于本文提出的的方法。

4 結束語

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

算BitMap的并集即可。本文在CC_WEB_VIDEO視頻數據集中對上述方法進行了檢驗，測試結果表明，該方法能將匹配效率提高1倍以上。今后，我們將構建更大規模的視頻數據庫，并結合分布式處理平臺Hadoop實驗。

圖4 平均檢索時間與視頻數量的關系

參考文獻

[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.

〔編輯：張思楠〕