結(jié)合稀疏編碼和金字塔匹配的視頻檢索

甘 玲，汪子彧

GAN Ling,WANG Ziyu

重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065

School of Computer Scienceand Technology of Chongqing University of Postsand Telecommunications,Chongqing 400065,China

互聯(lián)網(wǎng)及相關(guān)技術(shù)的高速發(fā)展，使得多媒體信息呈海量增長(zhǎng)，傳統(tǒng)的文本檢索只依賴于標(biāo)簽和短文本信息對(duì)視頻的描述，因而有著很大的局限性。隨著用戶對(duì)檢索需求的提高，基于內(nèi)容的檢索成為了研究的熱點(diǎn)。研究基于內(nèi)容的視頻檢索（Content Based Video Retrieval，CBVR），重在檢索視頻本身的內(nèi)容，并使用視覺(jué)基礎(chǔ)特征作為相似度度量的依據(jù)，從而克服了傳統(tǒng)的基礎(chǔ)屬性和文本檢索的不足。

基于內(nèi)容的檢索的難點(diǎn)是“語(yǔ)義鴻溝”問(wèn)題，即基礎(chǔ)特征難以表示高層語(yǔ)義。目前對(duì)于使用基礎(chǔ)特征描述的視頻，圖像的區(qū)分通常采用金字塔匹配方法[1-5]。金字塔匹配方法的意義在于，通過(guò)多粒度劃分匹配子集合，就能利用基礎(chǔ)特征的組合重現(xiàn)一定的語(yǔ)義信息，從而提高檢索的準(zhǔn)確性?？臻g金字塔匹配方法[1]（Spatial Pyramid Matching，SPM）和時(shí)空金字塔匹配的方法[3]（Spatio-Temporal Pyramid Matching，STPM）均在此基礎(chǔ)上提出。此外，近年一些對(duì)重復(fù)近似識(shí)別（Near Duplicates Identification，NDI）的研究[4-5]均使用了金字塔匹配的思想，解決了諸如此類的相似性度量問(wèn)題。但大多數(shù)方法都著力于研究匹配策略，并不涉及研究在方法中結(jié)合改進(jìn)基礎(chǔ)特征的表示。以上大部分方法均采用矢量量化方法作對(duì)圖像基礎(chǔ)特征表示，但該方法在特征重建時(shí)，會(huì)不可避免地丟失一些重要信息，導(dǎo)致檢索效率的下降。目前一些研究已經(jīng)將源自生物視覺(jué)感知研究的稀疏編碼技術(shù)[6-8]融入上述方法中[9]，用于解決矢量量化特征描述不夠準(zhǔn)確的問(wèn)題，本文首次通過(guò)結(jié)合稀疏編碼的SPM和STPM方法進(jìn)行基于內(nèi)容的視頻檢索，取得了比原方法更好的檢索效果。

1 金字塔匹配

1.1 SPM和STPM

SPM和STPM均繼承了金字塔匹配的思想，前者在金字塔的每一級(jí)上將圖像按空間分布劃分成多粒度的子塊，然后在各級(jí)的子塊之間進(jìn)行匹配；后者將視頻的鏡頭看成一個(gè)時(shí)空延展的立方體，并按時(shí)空粒度劃分金字塔的匹配子集合用于匹配。因?yàn)橐曨l特征具有較強(qiáng)的時(shí)空相關(guān)性，所以STPM方法比SPM更適合度量視頻的相似度。

如圖1所示[3]，視頻在金字塔的L層上被分割為不同粒度大小的立方體，L=0層的金字塔其實(shí)就是BoF下的匹配。由圖1可以看出，在L=1層，將視頻分成2×2×2的子塊，在L=2層，視頻被分成4×4×4的子塊，以此類推。每一層上設(shè)置的時(shí)空立方體的長(zhǎng)、寬、高分別為第0層的立方體長(zhǎng)、寬、高的1/2L。匹配從各層的對(duì)應(yīng)子塊之間開(kāi)始，最后通過(guò)合并各層的匹配結(jié)果得到視頻的相似度。

圖1 STPM層級(jí)示意圖

1.2 金字塔匹配核

假設(shè)X和Y是D維特征空間中的2個(gè)向量集合。同時(shí)在0，1，…，L級(jí)分辨率上，構(gòu)造一系列的網(wǎng)格，l級(jí)上的每個(gè)網(wǎng)格在每一維度上有2l個(gè)單元，總共有 D=2dl個(gè)單元。令分別代表X和Y在l級(jí)分辨率下的直方圖，同時(shí)i)是X和Y第i個(gè)區(qū)間中的特征的數(shù)量。那么在l級(jí)下的匹配可以由式（1）的直方圖相交函數(shù)給出：

因?yàn)樵趌級(jí)上的匹配數(shù)也包括了l+1級(jí)上的匹配數(shù)，所以在l級(jí)上新增的匹配數(shù)為 Γl-Γl+1，l=0，1，…，L-1。為了削弱在大粒度下發(fā)現(xiàn)的匹配，每一層的權(quán)值被設(shè)置為1/2L-l。綜上所述，金字塔匹配核的定義如式（2）、（3）所示：

上述直方圖相交和金字塔匹配核均為Mercer kernels[1]。

2 本文方法

2.1 算法思想

本文結(jié)合稀疏編碼方法用于以SPM、STPM等為匹配引擎的視頻檢索系統(tǒng)。首先對(duì)視頻基礎(chǔ)特征進(jìn)行采樣，然后用稀疏編碼方法訓(xùn)練得到的特征密碼本對(duì)每個(gè)視頻的特征進(jìn)行編碼，將編碼后特征的前c組顯著分量分別做c次STPM或SPM計(jì)算，并用稀疏編碼計(jì)算得到的權(quán)值合并這c組匹配，作為修正后的匹配結(jié)果。

2.2 視頻檢索的系統(tǒng)框架

本文的工作均基于時(shí)空金字塔匹配下的視頻檢索系統(tǒng)應(yīng)用[3]。系統(tǒng)結(jié)構(gòu)如圖2所示。

圖2 基于內(nèi)容的視頻檢索框架

首先構(gòu)建鏡頭數(shù)據(jù)庫(kù)：對(duì)輸入的視頻進(jìn)行鏡頭檢測(cè)，然后從各個(gè)鏡頭中提出基礎(chǔ)特征進(jìn)行訓(xùn)練、編碼。最后使用匹配引擎（如：SPM、STPM等）計(jì)算視頻的相似度，并將編碼結(jié)果和匹配結(jié)果存入數(shù)據(jù)庫(kù)。

當(dāng)用戶輸入一個(gè)查詢鏡頭時(shí)，系統(tǒng)通過(guò)匹配引擎進(jìn)行相似性度量，然后返回前k個(gè)最相似的結(jié)果。

2.3 矢量量化方法和稀疏編碼方法

矢量量化方法和稀疏編碼方法，都是為了從大量的基礎(chǔ)特征中提取出相對(duì)重要的信息用于數(shù)據(jù)類別表示。

2.3.1 矢量量化方法

假設(shè)X表示D維空間中的特征集合，例如：

那么矢量化方法，可以使用K-means算法解決式（4）的問(wèn)題：

其中，V=[v1，v2，…，vk]T是K-means算法的聚類中心，被稱為密碼本。這個(gè)優(yōu)化問(wèn)題，可以被重新寫(xiě)成式（5）中求解最優(yōu)矩陣因子的問(wèn)題：

其中，Card(um)=1是基數(shù)約束，意味著um中只有一個(gè)元素非零；‖‖.是L2范式；||um是L1范式，是um中所有元素絕對(duì)值的求和。由上式，可以看出um具有非負(fù)性。在訓(xùn)練階段，式（5）的求解同時(shí)依賴于U、V；在編碼階段，使用已經(jīng)訓(xùn)練好的V，求解U。

2.3.2 稀疏編碼方法

對(duì)于高維的特征來(lái)說(shuō)，Card(um)=1的基數(shù)約束，往往過(guò)于嚴(yán)格，常常使得重建的特征丟失了一些重要的信息。針對(duì)這一問(wèn)題，可以適當(dāng)放寬這一約束，讓um能夠有多個(gè)非零元素。這就是稀疏編碼的基本原理，如式（6）所示：

其中λ是一個(gè)正則化參數(shù)，密碼本V通常是一個(gè)超完備基向量集(K＞D)，式（6）中沒(méi)有寫(xiě)上非負(fù)約束，原因是um的符號(hào)來(lái)實(shí)現(xiàn)。其中 um+=min(0，um)，um-=max(0，um)。同矢量化方法一樣，稀疏編碼也需要先進(jìn)行訓(xùn)練，然后進(jìn)行編碼。

2.4 討論與應(yīng)用

本文結(jié)合稀疏編碼進(jìn)行視頻檢索的主要原因是：（1）圖像塊是稀疏信號(hào)；（2）稀疏編碼可以表示出圖像的顯著特征；（3）與矢量化方法相比，稀疏編碼能夠更精確地對(duì)特征編碼。

實(shí)驗(yàn)中使用文獻(xiàn)[6]中的高效求解方法求解式（6）中的優(yōu)化問(wèn)題，同時(shí)為了將稀疏編碼融入基于金字塔匹配的檢索工作，本文所使用的投影函數(shù)F將um每一列中絕對(duì)值最大的前c個(gè)分量的序號(hào)作為該特征的直方圖統(tǒng)計(jì)表示，同時(shí)對(duì)這c個(gè)分量的絕對(duì)值進(jìn)行加權(quán)平均，作為合并匹配結(jié)果的權(quán)值。即在獲得稀疏編碼后的矩陣U以后，使用式（7）計(jì)算：

F是定義在um每一列上的操作，如式（8）所示：

zcj表示F從|uj|中取出的第c個(gè)顯著元素的行序號(hào)，wcj表示從|uj|中取出的第c個(gè)元素值，uij是U中第i行j列的元素，M是密碼本的行數(shù)，代表顯著局部特征的數(shù)量。在實(shí)驗(yàn)中，使用Zc做c次SPM、STPM運(yùn)算，然后使用式（9）中計(jì)算得到的權(quán)值合并匹配結(jié)果。

本文中的實(shí)驗(yàn)，從視頻的圖像塊中隨機(jī)抽取了51 200個(gè)sift[10]特征用于訓(xùn)練密碼本，然后用該密碼本對(duì)視頻特征進(jìn)行編碼、匹配。

3 實(shí)驗(yàn)

本文在UCF50視頻數(shù)據(jù)集上，分別對(duì)使用矢量量化方法和結(jié)合本文方法的關(guān)鍵幀匹配、SPM、STPM的視頻檢索做了對(duì)比實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)數(shù)據(jù)

UCF50是美國(guó)中佛羅里達(dá)大學(xué)收集自Youtube等視頻網(wǎng)站的視頻數(shù)據(jù)集。視頻按行為劃分有50類，如：游泳、跳水、蕩秋千等，其中每一類視頻均包含了大量特殊場(chǎng)景下的鏡頭，可以作為本文視頻檢索的實(shí)驗(yàn)數(shù)據(jù)。在實(shí)驗(yàn)中按鏡頭中的行為和場(chǎng)景選取了復(fù)雜場(chǎng)景下的20類視頻（每一類10個(gè)鏡頭，共200個(gè)鏡頭）作為本文的實(shí)驗(yàn)數(shù)據(jù)。

3.2 實(shí)驗(yàn)評(píng)價(jià)方法

本文的實(shí)驗(yàn)使用文獻(xiàn)[3]中的二分法判別評(píng)價(jià)每次檢索返回的結(jié)果，用NDCG@k評(píng)價(jià)整體檢索質(zhì)量。

3.2.1 二分法判別

文獻(xiàn)[3]中的二分法判別對(duì)每次檢索的結(jié)果評(píng)價(jià)，可以分為三種情況：（1）正確；（2）錯(cuò)誤；（3）不可分。

假設(shè)用戶輸入一個(gè)鏡頭Q，這個(gè)鏡頭屬于一個(gè)特定的類別，再假設(shè)有兩個(gè)鏡頭A、B：A和Q為同一類；B和Q不屬于同一類。那么檢索返回的結(jié)果中，A和Q的相似度應(yīng)該比B和Q的大，即STPM(Q，A)＞STPM(Q，B)。如果在限定返回的 k個(gè)結(jié)果中，全部滿足 STPM(Q，A)＞STPM(Q，B)，則判定為檢索成功；如果有 STPM(Q，A)＜STPM(Q，B)，則判定檢索錯(cuò)誤；除上述兩種情況的其他的情況判定為不可分。

查詢返回結(jié)果的例子如圖3所示。

圖3 查詢返回結(jié)果的例子

圖3 為一次查詢和返回前5個(gè)結(jié)果的例子，第一行為從輸入的查詢鏡頭中提取的3幀，下面的5列，每一列均取自檢索返回的結(jié)果的3幀。按照二分法判別，這是一次成功的查詢，因?yàn)檩斎氩樵兊氖撬夏ν型У溺R頭，而返回的5個(gè)結(jié)果中，所有水上摩托艇的鏡頭按照相似度排序，均在其他鏡頭（圖中其他鏡頭為：皮劃艇，游泳）之前。注意到圖2中，也將匹配數(shù)結(jié)果歸一化，作為查詢得分。

3.2.2 NDCG@k

NDCG@k（Normalized Discounted Cumulative Gain at top k Ranks）是一種信息檢索和測(cè)量結(jié)果準(zhǔn)確率的度量標(biāo)準(zhǔn)。NDCG@k公式如式（10）所示：

NDCG@k將檢索得到的1到k個(gè)結(jié)果用一個(gè)評(píng)價(jià)函數(shù)s（p）進(jìn)行計(jì)算。s（p）代表第p個(gè)結(jié)果的檢索效果。在實(shí)驗(yàn)中，s（p）的設(shè)置和文獻(xiàn)[3]相同，根據(jù)返回鏡頭和查詢鏡頭是否在同一類別下，s（p）=1或者0。參數(shù)Z是一個(gè)用于歸一化的因子，它是理想化的DCG（Discounted Cumulative Gain）值。

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

從每個(gè)視頻鏡頭中，提取典型的8幀作為一個(gè)鏡頭的代表（因?yàn)樵趯?shí)際應(yīng)用中，該算法也往往是針對(duì)關(guān)鍵幀的集合進(jìn)行操作），然后對(duì)這8幀提取稠密SIFT特征來(lái)進(jìn)行稀疏編碼，密碼本V的維度設(shè)置為200×128（其中，200是一個(gè)常規(guī)的經(jīng)驗(yàn)取值，且該維度大于特征維度符合超完備基向量集的條件。128為sift特征描述符的維度）。

用二分法判別對(duì)200次查詢中每次返回5個(gè)結(jié)果的統(tǒng)計(jì)情況如表1所示。

表1 二分法判別的實(shí)驗(yàn)比較結(jié)果 （%）

由表1中可以看出分別對(duì)關(guān)鍵幀、SPM和STPM使用矢量量化方法和稀疏編碼方法進(jìn)行比較實(shí)驗(yàn)。從實(shí)驗(yàn)結(jié)果可以看出，使用了稀疏編碼后，基于關(guān)鍵幀的匹配雖然沒(méi)有提高檢索的正確率，但減少了不可分率。而SPM、STPM方法均增加了檢索的準(zhǔn)確率。尤其是基于STPM的視頻檢索，效果顯著增強(qiáng)。

圖4 每次查詢的NDCG@k值

圖4 中每一個(gè)數(shù)據(jù)點(diǎn)是200次查詢返回k個(gè)結(jié)果的NDCG@k均值，對(duì)使用了稀疏編碼方法和矢量量化方法的實(shí)驗(yàn)分別用實(shí)線和虛線表示?？梢钥闯鲈趉＜10的情況下，使用稀疏編碼的STPM、SPM的檢索效率均高于使用矢量量化方法時(shí)的效率。

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

金字塔匹配方法給出了一種快速高效的視頻、圖像檢索的解決方案。本文首次結(jié)合稀疏編碼和金字塔匹配用于基于內(nèi)容的相似視頻檢索，在線性時(shí)間復(fù)雜度增加的基礎(chǔ)上，取得了比用矢量量化方法的SPM、STPM更精確的檢索效果。在未來(lái)的工作中，將會(huì)使用更大的數(shù)據(jù)集（例如：在線數(shù)據(jù)集）來(lái)測(cè)試該方法的效率，同時(shí)嘗試使用合并的一些其他基礎(chǔ)特征，提高檢索的準(zhǔn)確性。

[1]Kristen G，Trevor D.The pyramid match kernel：discriminative classification with sets of image features[C]//ICCV，2005：1458-1465.

[2]Lazebnik S，Schmid C，Ponce J.Beyond bag of features：spatial pyramid matching for recognizing natural scene categories[C]//CVPR，2006：2169-2178.

[3]Choi J，Jeon W，Lee S C.Spatio-temporal pyramid matching for sports videos[C]//ACM Multimedia，2008.

[4]Xu Dong，Chang Shih-Fu.Visual event recognition in news video using kernel methods with multi-level temporal alignment[C]//CVPR，2007：1-8.

[5]Xu Dong，Cham T J.Near duplicate image identification with spatially aligned pyramid matching[C]//TCSVT，2010：1068-1079.

[6]Mairal J，Bach F.Online learning for matrix factorization and sparse coding[J].Machine Learning Research，2010，11.

[7]Mairal J，Bach F.Discriminative learned dictionaries for local image analysis[C]//CVPR，2008：1-8.

[8]Olshausen B A，F(xiàn)ield D J.Sparse coding with an overcomplete basis set：a strategy employed by V1[J].Vision Research，1997，37：3311-3325.

[9]Yang Jianchao，Yu Kai.Linear spatial pyramid matching using sparse coding for image classification[C]//CVPR，2009：1794-1801.

[10]Lowe D.Object recognition from local scale-invariant features[C]//ICCV，1999.