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

?

基于改進(jìn)的多特征哈希的近重復(fù)視頻檢索

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

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

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

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

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

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

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

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

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

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

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

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

1　多特征哈希原理

1.1相關(guān)術(shù)語(yǔ)和符號(hào)

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

其中，n為訓(xùn)練集中關(guān)鍵幀的總數(shù)；mv為第v個(gè)特征對(duì)應(yīng)2種特征的維度；Xv為所有關(guān)鍵幀的第v個(gè)特征，且v≤2。

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

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

Cv表示第v個(gè)特征的哈希碼。

1.2多特征哈希模型

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

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

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

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

2　改進(jìn)的多特征哈希

2.1改進(jìn)后的多特征哈希模型

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

本文采用高斯核函數(shù)的值來(lái)表示鄰接矩陣中的元素。采用高斯核函數(shù)是因?yàn)椋焊咚购撕瘮?shù)對(duì)沒(méi)有先驗(yàn)知識(shí)的數(shù)據(jù)效果最好，并且其值的范圍是（0，1）。本文中Av表示了2幀圖片特征值的相似程度，2幀圖片越接近時(shí)，Av值越大。對(duì)高斯核函數(shù)來(lái)說(shuō)，遠(yuǎn)離中心時(shí)核函數(shù)取值很小，每一幀圖片特征都可以看作一個(gè)中心。改進(jìn)后的Av定義如下：

其中，ξv表示訓(xùn)練集特征的方差。這樣不僅提高了精度，而且相對(duì)于全部用高斯核來(lái)說(shuō)，減少了無(wú)效的運(yùn)算。

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

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

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

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

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

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

2.2生成二進(jìn)制碼

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

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

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

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

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

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

其中，O的表達(dá)式為：

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

2.3算法步驟

訓(xùn)練步驟如下：

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

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

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

（1）對(duì)每個(gè)視頻中所有關(guān)鍵幀映射成的哈希值求平均。

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

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

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

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

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

圖1　種子視頻

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

圖2　相似視頻

圖3　巨大改變的視頻

圖4　不相似的視頻

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

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

表1　MAP值的比較

圖5　P-R曲線的比較

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

圖6　4種方法檢索實(shí)驗(yàn)結(jié)果

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

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

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

［參考文獻(xià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矩陣和非負(fù)矩陣的圖像分類［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，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.

（責(zé)任編輯張镅）

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

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

基金項(xiàng)目：安徽省科技攻關(guān)計(jì)劃資助項(xiàng)目（1301b）

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

Doi：10.3969/j.issn.1003-5060.2016.01.013

中圖分類號(hào)：TN919.81

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1003-5060（2016）01-0067-06