羅紅溫，楊艷芳，齊美彬，蔣建國（.合肥工業(yè)大學計算機與信息學院，安徽合肥　30009；.合肥工業(yè)大學電子科學與應用物理學院，安徽合肥　30009）

?

基于改進的多特征哈希的近重復視頻檢索

羅紅溫1，楊艷芳2，齊美彬1，蔣建國1
（1.合肥工業(yè)大學計算機與信息學院，安徽合肥230009；2.合肥工業(yè)大學電子科學與應用物理學院，安徽合肥230009）

摘要：隨著互聯(lián)網(wǎng)的迅速發(fā)展，產(chǎn)生了大量的近重復視頻。文章提出了一種改進的哈希算法提高近重復視頻的檢索準確性，根據(jù)語義哈希對圖像檢索的原理，對算法中的鄰接矩陣進行改進。鄰接矩陣表示KNN圖中樣本間的鄰接關系，文中不再使用0和1兩個值表示樣本間的鄰接關系，而是引入高斯核函數(shù)來表示，提高了模型的檢索精度。實驗結(jié)果表明所提出的方法具有更高的檢索精度。

關鍵詞：近重復視頻檢索；哈希算法；鄰接矩陣；高斯核函數(shù)；KNN圖

齊美彬（1969-），男，安徽東至人，博士，合肥工業(yè)大學教授，碩士生導師；

蔣建國（1955-），男，安徽寧國人，合肥工業(yè)大學教授，博士生導師.

近重復視頻檢索的實質(zhì)是比較2個視頻的內(nèi)在特征，根據(jù)結(jié)果判斷視頻是否相似。近重復視頻檢索一般分為如下3步：關鍵幀提取、特征提取和檢索，其中選擇合適的檢索方法是近重復視頻檢索的難點。

近重復視頻檢索方法一般有如下3類：

（1）直接進行特征匹配的檢索方法，需要對視頻的關鍵幀內(nèi)容兩兩進行相關性分析。如文獻［1］對提取的關鍵幀的特征進行相關性分析，通過對視頻中每2幀內(nèi)容的相關性進行分析并統(tǒng)計，最終得到能表示視頻相似性的參數(shù)。文獻［2-3］提出了一種分層的方法，首先通過顏色特征過濾一些很不相似的視頻，然后采用更精確的局部關鍵點方法對余下視頻進行匹配。這類方法最大的缺點是關鍵幀間的局部關鍵點兩兩比較計算量非常大，因此不適合應用在大規(guī)模近重復視頻檢索上。

（2）通過建立索引進行檢索的方法，可以提高檢索速度，其中最常用的是KD樹，如文獻［4-5］中介紹了一些常用的有效的索引方法。文獻［6］介紹了樹形索引結(jié)構(gòu)在高維空間的最近鄰查找。這類方法計算量雖然減少了，但是當特征維度比較大時，樹形索引往往效果較差，出現(xiàn)所謂的“維度災難”。

（3）語義哈希的檢索方法。其準則是在原始空間中相似的視頻有相似的哈希碼。其原理是利用圖的拉普拉斯矩陣［7］進行編碼，最終經(jīng)語義哈希映射成的二進制碼把訓練集高度壓縮，其結(jié)果能代表訓練集的內(nèi)容，同時該方法在漢明空間中求異或操作速度很快。因此語義哈希被廣泛應用在近重復視頻檢索上。

前期的基于語義哈希的檢索都是應用單特征，并且采用現(xiàn)有的哈希函數(shù)模型，如文獻［8］介紹了譜哈希應用在大規(guī)模數(shù)據(jù)集上。采用譜哈希的方法進行檢索大大提高了檢索的精度，但是要求訓練數(shù)據(jù)服從統(tǒng)一分布。文獻［9］介紹了自學哈希在快速相似性檢索上的應用，在譜哈希的基礎上提高了檢索精度，但是當有新視頻時，使用該方法需要重新進行訓練。但是這2種哈希方法都只是使用了單特征，并且可擴展性較差。文獻［10-11］提出了一種哈希算法，該算法有很強的可擴展性和可移植性，并且同時得到哈希碼和哈希函數(shù)。該模型簡單，對訓練數(shù)據(jù)的分布沒有任何限制，準確性、可擴展性和可移植性較強，但是檢索精度需要近一步提高。因此本文對該算法進行了改進。

本文在文獻［11］的基礎上提出了一種改進的多特征哈希的方法，對拉普拉斯矩陣中的鄰接矩陣進行改進，用高斯核函數(shù)的值來表示鄰接矩陣的元素，這樣可以更加精確地表示幀間的相似程度，從而提高了模型的檢索精度。

1　多特征哈希原理

1.1相關術(shù)語和符號

下面介紹模型中相關向量及含義。本文采用了HSV和LBP 2種特征，每個特征對應的訓練數(shù)據(jù)集為：

其中，n為訓練集中關鍵幀的總數(shù)；mv為第v個特征對應2種特征的維度；Xv為所有關鍵幀的第v個特征，且v≤2。

某一關鍵幀的特征向量可以表示為xl＝［（x1l）T，（x2l）T］∈R1×（m1＋m2），則所有關鍵幀的全部特征可以被向量X＝［x1，x2，…，xn］∈Rn×（m1＋m2）表示。線性哈希函數(shù)集為{ h1（·），h2（·），…，hp（·）}，其中哈希函數(shù)如（1）式所示，p為哈希碼的碼長。

并且定義常用向量I1∈Rn×1為元素值全為1的列向量；I∈Rn×n為矩陣；In∈Rn×n為對角陣，且主對角線上元素的值為1；Id∈R（m1＋m2）×（m1＋m2）為對角陣，且主對角線上元素的值為1。訓練集哈希碼為：

Cv表示第v個特征的哈希碼。

1.2多特征哈希模型

在該模型中，采用了拉普拉斯矩陣Lv。拉普拉斯矩陣的定義為：其中，Dv為度矩陣；Gv＝Av＋δBv，Av為鄰接矩陣，Av表示關鍵幀的單個特征的結(jié)構(gòu)信息；Bv表示關鍵幀是否屬于同一視頻；δ表示Av和Bv的權(quán)重。Av和Bv表示為：

最終生成的目標函數(shù)為：

其中，（6）式中第1項表示單個特征的個體的結(jié)構(gòu)信息，第2項表示所有特征的結(jié)構(gòu)信息，第3項保證了哈希函數(shù)的經(jīng)驗誤差最小。

對（6）式中的目標函數(shù)進行化簡求解［11］，通過化簡可以得到訓練集的哈希碼和一系列的哈希函數(shù)。為了進一步提高該模型的檢索精度，本文針對模型中的拉普拉斯矩陣進行了改進。

2　改進的多特征哈希

2.1改進后的多特征哈希模型

在多特征哈希模型（MFH）中，采用最簡單的0和1來表示鄰接矩陣的元素，這種表示雖然簡單，但是會導致k近鄰中所有數(shù)據(jù)的值都是一樣的，表達結(jié)果不精確，從而使檢索準確性降低。

本文采用高斯核函數(shù)的值來表示鄰接矩陣中的元素。采用高斯核函數(shù)是因為：高斯核函數(shù)對沒有先驗知識的數(shù)據(jù)效果最好，并且其值的范圍是（0，1）。本文中Av表示了2幀圖片特征值的相似程度，2幀圖片越接近時，Av值越大。對高斯核函數(shù)來說，遠離中心時核函數(shù)取值很小，每一幀圖片特征都可以看作一個中心。改進后的Av定義如下：

其中，ξv表示訓練集特征的方差。這樣不僅提高了精度，而且相對于全部用高斯核來說，減少了無效的運算。

為了得到目標函數(shù)，本文遵循語義哈希準則，即在原始空間中相似的視頻有相似的哈希碼。為了滿足上述準則，應使k近鄰的關鍵幀間的哈希碼盡可能相似，可用下面的最優(yōu)化公式來表示：

為了更好地表示視頻中關鍵幀的信息，也采用了矩陣Bv，并且有Gv＝Av＋δBv，此時目標函數(shù)表達式為：

（9）式中的目標函數(shù)只是考慮了單個特征個體的結(jié)構(gòu)信息，還需要全局地考慮所有特征的結(jié)構(gòu)信息。為了提高算法的準確性，應使每個特征盡可能地表示該幀圖像的內(nèi)容，即應保證該幀圖像單特征形成的哈希碼和多特征形成的哈希碼盡可能相似。因此，加入所有特征的結(jié)構(gòu)信息的目標函數(shù)被重新定義為：

其中，αv為表示特征間的權(quán)重；β為2個部分之間的權(quán)重。

在產(chǎn)生關鍵幀哈希碼的同時產(chǎn)生哈希函數(shù)，當有新的數(shù)據(jù)產(chǎn)生時可以直接處理，不需要重新訓練。為了保證在產(chǎn)生哈希碼的同時產(chǎn)生哈希函數(shù)，結(jié)合了機器學習中的經(jīng)驗風險最小化知識，目標函數(shù)近一步表示為：

其中，Ω（hq）為hq的歸一化函數(shù)；clq為對應關鍵幀xl的的第q位哈希碼；λ和μ為參數(shù)；約束條件是為了保證產(chǎn)生二進制碼和避免繁瑣解。同譜哈希算法一樣，在該約束條件下，它是一個NP-hard的問題，無法求解（11）式。因此，需放寬約束條件，只保留CTC＝I。同時結(jié)合（1）式、（11）式以及之前定義的向量，目標函數(shù)可以化為：

2.2生成二進制碼

語義哈希對圖像的編碼過程可以看成是圖分割問題，其借助于相似圖的拉普拉斯矩陣的特征值和特征向量的分析，得到圖分割問題的一個松弛解，然后對特征向量進行二值化，從而產(chǎn)生哈希碼。本文在多特征哈希模型的基礎上對拉普拉斯矩陣進行改進，該模型屬于語義哈希的一類，整個模型的編碼過程與語義哈希一致。本文采用多特征哈希中對目標函數(shù)化簡的方法，對（12）式的目標函數(shù)進行化簡。通過對（12）式的W和B分別求偏導，從而確定哈希函數(shù)。

分別對（12）式的W和B求偏導，令偏導數(shù)為0，可得：

其中，Rn＝In-I1I1T/n為一個中心矩陣。

把（13）式、（14）式分別帶入（12）式中，化簡目標函數(shù)可得：

其中，Lv為第v個特征的拉普拉斯矩陣；M＝Rn-RnX（XTRnX＋μId）-1XTRn。對（15）式中的Cv求偏導，并令導數(shù)為0，可得：

令Dv＝β（Lv＋βIn）-1，則Cv＝DvC，代入（16）式可得最終的目標函數(shù)為：

其中，O的表達式為：

本文通過求解矩陣O的特征值和特征向量，其中C為前p個最小的特征值對應的特征向量。對C進行二值化即可得到視頻的哈希碼。然后根據(jù)（13）式、（14）式分別求出W和B，同時產(chǎn)生了哈希碼和哈希函數(shù)。

2.3算法步驟

訓練步驟如下：

（1）根據(jù)（1）式求所有特征的拉普拉斯矩陣Lv。

（2）根據(jù)（17）式求出矩陣O，并求出矩陣O的前p個最小的特征值對應的特征向量C。

（3）根據(jù)（13）式、（14）式分別求出W和B。檢索過程步驟如下：

（1）對每個視頻中所有關鍵幀映射成的哈希值求平均。

（2）對該哈希值二值化，每個視頻產(chǎn)生一個p位的哈希碼。

（3）通過W和B求查詢視頻的哈希碼，和訓練集的哈希碼在漢明空間求異或，輸出檢索結(jié)果。

3　實驗結(jié)果及分析

為了驗證本算法的準確性，在公開的數(shù)據(jù)集CC-WEB-VIDEO上進行了實驗。實驗的環(huán)境為：VS2010和OpenCV2.4.3，64位Win7系統(tǒng)。

本文采用的數(shù)據(jù)庫中種子視頻的若干關鍵幀如圖1所示。

圖1　種子視頻

訓練集主要有完全相同的視頻、相似視頻、巨大改變的視頻、不相似的視頻4類，其中，完全相同的視頻不再貼圖，其余幾類的若干關鍵幀如圖2～圖4所示。

圖2　相似視頻

圖3　巨大改變的視頻

圖4　不相似的視頻

實驗中各參數(shù)設置為：μ＝1，λ＝103，δ＝103，β ＝1，α1＝1，α2＝1，k＝0.1×num，num為訓練集中關鍵幀的總數(shù)。編碼長度p＝320。HSV特征為162維，LBP特征為256維。

本文不僅和多特征哈希［11］法做了對比，還和一些主流方法做了對比，LF代表文獻［3］中的局部特征分層檢索方法，ST-lbp和ST-ce分別代表文獻［12］中的時空特征檢索方法，GF為只使用了HSV特征的哈希模型的檢索方法，IMmfh為本文算法。本文從MAP值和P-R曲線分析算法。MAP值的比較見表1所列，P-R曲線的比較如圖5所示。從表1中可以看出，本文方法的MAP值結(jié)果最好。從圖5中可以看出，GF在這些方法中效果最差，本文方法效果最好，其余幾種方法效果接近。

表1　MAP值的比較

圖5　P-R曲線的比較

另外，為了驗證本文方法的有效性，對24類數(shù)據(jù)集均做了實驗，并且和Content方法［2］、Layer方法［3］、多特征哈希（MFH）的方法做了對比，實驗結(jié)果分別如圖6所示。

圖6　4種方法檢索實驗結(jié)果

從圖6中可以看出圖6a的結(jié)果最差，其主要原因在于判斷視頻是否是近重復視頻時，該方法先通過視頻時間長短濾除部分視頻，然后再通過視頻的內(nèi)容信息判斷是否是近重復的。但是因為視頻的版本不同，時間上相差較大的視頻也可能是近重復視頻，因此造成了漏檢。本文方法更優(yōu)于MFH方法，雖然18類和22類效果不太理想，但是其效果仍然優(yōu)于MFH，該類數(shù)據(jù)集中的視頻變化比較復雜，通過引入時間信息和改進拉普拉斯矩陣更加精確地表示視頻結(jié)構(gòu)和內(nèi)容，從而提高了檢索精度。

4　結(jié)束語

本文提出了一種改進的多特征哈希的算法，主要改進了鄰接矩陣。實驗表明，和多特征哈希［11］的算法相比，本文算法不僅提高了檢索的精度，同時還保持了可擴展性和可移植性。進一步的研究工作是應用能表示視頻的時間信息和能表示視頻的動作特征對監(jiān)控視頻進行檢索。

［參考文獻］

［1］Liu J，Huang Z，Shen H T，et al.Correlation-based retrieval for heavily changed near-duplicate videos［J］.ACM Transactions on Information Systems，2011，29（4）：21.1-21.25.

［2］Wu X，Ngo C W，Hauptmann A G，et al.Real-time near-duplicate elimination for web video search with content and context ［J］.IEEE Transactions on Multimedia，2009，11（2）：196-207.

［3］Wu X，Hauptmann A G，Ngo C.Practical elimination of nearduplicates from web video search［J］.Proceedings of International Conference on Multimedia，2007：218-227.

［4］Glowacki P，Pinheiro M A，Turetken E，et al.Reconstructing evolving tree structures in time lapse sequences［C］//2014 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）.IEEE，2014：3035-3042.

［5］Ai L，Yu J，He Y，et al.High-dimensional indexing technologies for large scale content-based image retrieval：a review［J］.Journal of Zhejiang University：Science C，2013，14（7）：505-520.

［6］Tao Y，Yi K，Sheng C，et al.Efficient and accurate nearest neighbor and closest pair search in high-dimensional space［J］.ACM Transactions on Database Systems（TODS），2010，35 （3）：20.

［7］蔣云志，王年，汪斌，等.基于圖的Laplace矩陣和非負矩陣的圖像分類［J］.合肥工業(yè)大學學報：自然科學版，2011，34（9）：1330-1334.

［8］Weiss Y，Torralba A，F(xiàn)ergus R.Spectral hashing［C］//Advances in Neural Information Processing Systems，2009：1753-1760.

［9］Zhang D，Wang J，Cai D，et al.Self-taught hashing for fast similarity search［C］//Proceedings of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2010：18-25.

［10］Song J，Yang Y，Huang Z，et al.Multiple feature hashing for real-time large scale near-duplicate video retrieval［C］//Proceedings of the 19th ACM International Conference on Multimedia.ACM，2011：423-432.

［11］Song J，Yang Y，Huang Z，et al.Effective multiple feature hashing for large-scale near-duplicate video retrieval［J］.IEEE Transactions on Multimedia，2013，15（8）：1997-2008.

［12］Shang L，Yang L，Wang F，et al.Real-time large scale near-duplicate web video retrieval［C］//Proceedings of the International Conference on Multimedia.ACM，2010：531-540.

（責任編輯張镅）

A near-duplicate video retrieval method based on improved multiple feature hashing

LUO Hong-wen1，YANG Yan-fang2，QI Mei-bin1，JIANG Jian-guo1
（1.School of Computer and Information，Hefei University of Technology，Hefei 230009，China；2.School of Electronic Science and Applied Physics，Hefei University of Technology，Hefei 230009，China）

Abstract：With the development of Internet，a large number of near-duplicate videos are produced online each day.In this paper，an improved hashing algorithm is proposed to improve the accuracy of near-duplicate video retrieval.According to the theory of semantic hashing based image retrieval，the adjacency matrix is improved.Adjacency matrix is a representation of the sample’s adjacency of K-nearest neighbor（KNN）graph.The adjacency relationship is presented by Gaussian kernel function instead of 0 or 1，thus improving the accuracy of retrieval.The experimental results show that the proposed method has higher retrieval accuracy.

Key words：near-duplicate video retrieval；hashing algorithm；adjacency matrix；Gaussian kernel function；K-nearest neighbor（KNN）graph

作者簡介：羅紅溫（1987-），女，河北衡水人，合肥工業(yè)大學碩士生；

基金項目：安徽省科技攻關計劃資助項目（1301b）

收稿日期：2014-12-17；修回日期：2015-04-24

Doi：10.3969/j.issn.1003-5060.2016.01.013

中圖分類號：TN919.81

文獻標識碼：A

文章編號：1003-5060（2016）01-0067-06