采用非線性塊稀疏字典選擇的視頻總結(jié)

馬明陽,梅少輝,萬帥

(西北工業(yè)大學電子信息學院,710129,西安)

隨著互聯(lián)網(wǎng)、多媒體和智能終端的快速發(fā)展,視頻的獲取和傳輸變得前所未有的便捷,視頻數(shù)據(jù)呈現(xiàn)爆炸式增長。海量視頻數(shù)據(jù)在給人們帶來豐富信息的同時,也對視頻管理帶來了巨大的挑戰(zhàn),比如檢索、瀏覽和存儲等。因此,快速有效地訪問視頻的主要內(nèi)容和重要信息已經(jīng)成為與日俱增的需求。視頻總結(jié)是目前解決此需求的一種有效途徑,它是通過對整個視頻結(jié)構(gòu)和內(nèi)容進行分析來完成,既涵蓋了視頻的最主要的信息,也極大地減少了數(shù)據(jù)量[1-2]。

早期的視頻總結(jié)研究主要有基于聚類的方法和基于鏡頭邊界檢測的方法?；诰垲惖姆椒ㄊ紫炔捎镁垲惣夹g(shù)將內(nèi)容相似的視頻幀聚為一類,然后將聚類中心或離聚類中心最近的幀選為關(guān)鍵幀[3-5]?；阽R頭邊界檢測的方法首先對視頻進行鏡頭邊界檢測,在把視頻分割為鏡頭之后,取鏡頭中的首幀或末幀作為視頻的關(guān)鍵幀。此類算法的最關(guān)鍵步驟是鏡頭邊界檢測技術(shù),基本思想是識別視覺內(nèi)容的不連續(xù)性[6-8]。但是這兩類方法將視頻總結(jié)描述為根據(jù)距離或者相似度進行數(shù)據(jù)分類的問題,使得視頻的場景語義信息提取僅僅依賴于有限的特征表示[9]。

近年來,稀疏表示理論在模式識別以及計算機視覺領(lǐng)域取得了顯著的成果,研究人員也逐漸將稀疏表示理論應(yīng)用于視頻總結(jié),例如:Kumar等提出了一種基于稀疏表示的方法來提取關(guān)鍵幀,使用隨機投影矩陣將視頻幀投影到一個低維的隨機特征空間,并且在隨機特征空間中利用稀疏表示來分析視頻數(shù)據(jù)并生成關(guān)鍵幀[10];Cong等將視頻總結(jié)表述為稀疏字典選擇問題,并采用寬松約束條件L2,1范數(shù)以確保稀疏性,使用Nesterov最優(yōu)梯度算法來提取關(guān)鍵幀[11];Mei等將視頻總結(jié)問題表述為一個最小化稀疏重建問題,使用L0范數(shù)對稀疏度約束,采用貪婪算法使關(guān)鍵幀直接被選擇為稀疏字典[12];Cong等針對網(wǎng)絡(luò)視頻總結(jié)提出了一種自適應(yīng)的稀疏字典選擇模型,該算法包含用于選擇關(guān)鍵幀的前向步驟和用于移除已經(jīng)選擇的較差的關(guān)鍵幀的后向步驟[13]。

然而,以上算法都是基于線性稀疏表示,即假設(shè)視頻幀之間是線性關(guān)系。這一假設(shè)并不總是準確,因為在對視頻幀進行特征表示時,特征通常存在內(nèi)在的非線性屬性。另外,由于視頻中的關(guān)鍵幀成塊出現(xiàn),這些算法都只考慮了關(guān)鍵幀的稀疏特性,未充分考慮塊稀疏特性。Ma等對視頻中的非線性進行了探究,提出了非線性的稀疏表示的視頻總結(jié)方法[14]。本文在文獻[14]的基礎(chǔ)上首先建立非線性稀疏字典選擇模型,然后利用塊稀疏特性進一步擴展建立非線性塊稀疏字典選擇模型。針對模型的優(yōu)化,設(shè)計了一種核化的聯(lián)合塊正交匹配追蹤(kernelized simultaneous block-orthogonal matching pursuit,KSBOMP)算法?；鶞室曨l數(shù)據(jù)集上的實驗結(jié)果驗證了KSBOMP算法能明顯提高視頻總結(jié)的客觀評價結(jié)果。

1 非線性塊稀疏字典選擇模型

假設(shè)一個視頻有n幀,第i幀可以通過特征提取技術(shù)表示為在實數(shù)集R上的d維的特征向量fi,fi∈Rd,1≤i≤n,該視頻可以表示為F,F=[f1,f2,…,fn]∈Rd×n。視頻總結(jié)的目標是從原始視頻中提取一個包含k個關(guān)鍵幀的子集Fkey,Fkey=[fi1,fi2,…,fik]∈Rd×k,其中i1,i2,…,ik∈{1,2,…,n}為k個關(guān)鍵幀的幀序號,要求此關(guān)鍵幀集合包含視頻的主要內(nèi)容,同時關(guān)鍵幀的數(shù)量越少越好。

1.1 非線性稀疏字典選擇

基于稀疏表示的視頻總結(jié)方法首先建立一個假設(shè),即視頻中的每一幀都可以表示為關(guān)鍵幀集合的線性組合。由于關(guān)鍵幀是視頻的子集,所以此假設(shè)可以用公式表述為

fi=Fxi, i=1,2,…,n

(1)

式中:xi是稀疏表示系數(shù),xi∈Rn,xi最多有k個非零值,每個非零值對應(yīng)一個關(guān)鍵幀。

然而,在對視頻幀進行特征表示時,特征通常擁有內(nèi)在的非線性屬性,所以假設(shè)視頻幀之間是線性關(guān)系并不總是準確的,會降低視頻總結(jié)的性能。將原始特征通過核函數(shù)映射到高維特征空間,再進行稀疏表示,這樣在原始空間中不能線性可分的樣本在高維空間變得線性可分,而在原始空間中線性可分的樣本在高維空間中能夠更加準確地線性可分[15]。

假設(shè)存在一個映射ψ(·)可將原始樣本映射到高維空間,即fi∈Rd→ψ(fi)∈RD,其中D?d,可能是無窮大。那么,原始視頻通過映射后在高維特征空間下就可以表示為Φ=ψ(F)=[ψ(f1),…,ψ(fn)]=[φ1,…,φn]∈RD×n。在高維空間下,式(1)中的假設(shè)可以用公式表述為

(2)

通過式(2)中的假設(shè),視頻總結(jié)問題可以被表述為一個非線性稀疏字典選擇問題,其公式為

(3)

1.2 非線性塊稀疏字典選擇

目前,基于稀疏表示的方法基本只考慮關(guān)鍵幀的稀疏特性,而沒有考慮塊稀疏特性。塊稀疏是指視頻的關(guān)鍵幀或非關(guān)鍵幀是成塊出現(xiàn)的,這是由小鄰域內(nèi)視頻幀的內(nèi)容相似性所決定的,即如果某一幀可以被看作關(guān)鍵幀,那么其短時鄰域的任一幀都可以作為關(guān)鍵幀?；趬K稀疏特性,視頻可以被表示為幀塊的結(jié)構(gòu)形式,公式為

(4)

相應(yīng)地,式(2)中的假設(shè)以塊結(jié)構(gòu)的形式可以表示為

(5)

將式(5)寫成聯(lián)合表示的形式,可以得到

(6)

(7)

(8)

通常,在視頻總結(jié)時,關(guān)鍵幀重建的信息與原始視頻的信息允許有一定的誤差,而式(6)中的表示是理想情況,因此只需要最小化表示誤差,同時保持關(guān)鍵幀塊的數(shù)量在要求的最大數(shù)量之內(nèi)即可。所以,基于非線性塊稀疏字典選擇的視頻總結(jié)模型可以用公式表述為

(9)

10號礦體：該礦體是該區(qū)最大的礦體，呈扁豆體產(chǎn)出，在2線南—12線分布，總長為2 600 m，在4～8線出現(xiàn)，寒武系下面的巖層覆蓋了4線的南部大多數(shù)礦體，黃土覆蓋了8線的北部。該礦體厚度為5～302 m，平均為154.7 m，走向呈北北東方向，傾向南東，傾角為70°～80°。

2 優(yōu)化算法

2.1 核函數(shù)

Ψ(·)實現(xiàn)了原始樣本空間到高維空間的非線性映射,核空間中的兩點Ψ(x)和Ψ(y)之間的內(nèi)積定義為〈Ψ(x),Ψ(y)〉=kf(x,y),其中kf(x,y)稱為該核空間所對應(yīng)的核函數(shù)。雖然kf(x,y)定義為內(nèi)積的形式,但通常不直接在高維空間計算兩個映射樣本的內(nèi)積,高維空間中的兩個映射樣本的內(nèi)積可以通過低維空間樣本的核函數(shù)來計算,這就避免了將數(shù)據(jù)映射到高維特征時的計算花銷。

常見的核函數(shù)包括線性核、多項式核以及高斯核,其中應(yīng)用最為廣泛的是高斯核函數(shù),若用σ表示高斯核函數(shù)的的帶寬參數(shù),則其表達式為

(10)

本文實驗選用高斯核函數(shù),帶寬參數(shù)σ需要人工設(shè)定,用于控制高維核空間中樣本對內(nèi)積的具體取值,σ設(shè)為0.24。通過核函數(shù)可以得到核矩陣K,K∈Rn×n,其中Ki,j=kf(fi,fj)。為了利用塊特性,將K寫成塊形式,即

(11)

2.2 核化的聯(lián)合塊正交匹配追蹤算法

在OMP算法的每次迭代中,字典中與重建誤差相關(guān)性最大的原子被選中。類似地,在KSBOMP算法中,與所有幀的重建誤差同時產(chǎn)生最大相關(guān)性的幀塊被選擇為關(guān)鍵幀塊。另外,幀塊的大小di可能不同,幀塊越大,幀塊和重建誤差之間的相關(guān)性越大,所以采用平均相關(guān)性來消除幀塊尺寸大小的影響,用公式表示為

(12)

(13)

為了獲得最小誤差,可用最小二乘法求解重建系數(shù),求解公式為

(14)

式中:K[Λt,Λt]是以Λt為行和列索引的K的子矩陣塊;K[Λt,:]是以Λt為行索引的K的子矩陣塊。

在得到關(guān)鍵幀塊和重建系數(shù)后,重建誤差更新

(15)

(16)

通過上述迭代步驟,直到算法滿足停止準則,就可以得到關(guān)鍵幀塊。在獲取關(guān)鍵幀塊后,通過一定的策略f從每個塊中選取一幀就可以得到關(guān)鍵幀集合。

綜上所述,設(shè)計的KSBOMP算法步驟如下。

輸入:視頻F=[f1,f2,…,fn],關(guān)鍵幀的最大數(shù)目k,視頻幀塊的大小di(1≤i≤m)。

輸出:關(guān)鍵幀索引集Γ。

步驟:

1.WHILE(t≤k)DO;

2.根據(jù)式(12)和(16),選擇與當前重建誤差最相關(guān)的幀塊作為關(guān)鍵幀塊,記錄索引值λt;

3.更新關(guān)鍵幀塊索引集,Λt=Λt-1∪λt;

5.增加迭代次數(shù)t=t+1;

6.ENDWHILE;

7.從關(guān)鍵幀塊中選擇關(guān)鍵幀,即Γ=f(Λ),選擇策略f可以具體設(shè)計,本文實驗簡單地采用關(guān)鍵幀塊的最中間幀作為關(guān)鍵幀。

3 實驗與討論

3.1 實驗設(shè)置

3.1.1 實驗數(shù)據(jù)集 采用VSUMM數(shù)據(jù)集[5],該數(shù)據(jù)集包含50個從OpenVideoProject收集的視頻,視頻的格式為MPEG-1,長度在1～4min之間,幀率為30幀/s,視頻的內(nèi)容包括紀錄片、教育、演講、歷史、風景等多種類別。該數(shù)據(jù)集還為每個視頻提供了5個用戶手工提取的關(guān)鍵幀集,可以用于與視頻總結(jié)的關(guān)鍵幀進行比較。在實驗中,對原始視頻幀進行5倍下采樣。

3.1.2 視頻幀特征表示 實驗中對視頻幀的表示采用一種360維的混合特征[11],包括252維的CENTRIST特征[16]和108維的顏色特征。CENTRIST特征提取視頻幀的結(jié)構(gòu)信息,對每幀圖像采用空間金字塔提取2層共6塊圖像,每塊圖像分別提取CENTRIST特征,然后采用PCA降為42維,所以每幀圖像的CENTRIST特征為42×6=252維。在提取顏色特征時,將圖像分成3×4個不重疊的小塊,并對每塊圖像的RGB三個顏色通道采用顏色矩(均值、方差和斜度)提取顏色特征,所以顏色特征為(3×3)×(3×4)=108維。

3.1.3 評價方式VSUMM數(shù)據(jù)的評價方式采用客觀評價,每個視頻都由1個自動總結(jié)(automaticsummaries,AS)算法結(jié)果與5個用戶總結(jié)(usersummaries,US)結(jié)果進行比較,采用3個評價指標對比較結(jié)果進行評價,具體包括精度P、召回率R和F值Fscore,具體公式為

(17)

(18)

(19)

式中:Nm是自動總結(jié)與用戶總結(jié)相匹配的關(guān)鍵幀個數(shù);NAS和NUS分別是自動總結(jié)和用戶總結(jié)的關(guān)鍵幀的數(shù)量。根據(jù)定義可知,精度反映了自動總結(jié)選中匹配關(guān)鍵幀的能力,召回率反映了匹配關(guān)鍵幀擊中用戶總結(jié)的能力,F值是對精度和召回率的平衡,是對視頻總結(jié)效果進行評價的最重要的整體指標。

在實驗中,每個視頻的自動總結(jié)分別與5個用戶總結(jié)單獨地進行比較和評價,然后用5個用戶總結(jié)的評價均值作為該視頻的最終評價結(jié)果,最后用50個視頻的評價結(jié)果的平均值作為此數(shù)據(jù)集的最終評價結(jié)果。

3.2 實驗結(jié)果

3.2.1 實驗參數(shù)分析 算法的參數(shù)對算法的性能存在影響,因此需要根據(jù)領(lǐng)域知識預(yù)先設(shè)置參數(shù)或探究參數(shù)的影響。本文所提的KSBOMP算法的主要參數(shù)包括視頻幀塊的大小di和關(guān)鍵幀的數(shù)量k。

圖1 KSBOMP算法性能隨關(guān)鍵幀數(shù)量的變化規(guī)律

(1)視頻幀塊的大小di。幀塊大小統(tǒng)一設(shè)置為13幀。由于對原始視頻進行了5倍的下采樣,所以在原始視頻中的幀塊大小是65幀,對應(yīng)的時長大約為2 s。通常,視頻的內(nèi)容在2 s內(nèi)不會發(fā)生明顯的變化,塊內(nèi)的幀具有相似性。

(2)關(guān)鍵幀的數(shù)量k。根據(jù)視頻總結(jié)的目的,不難理解選擇過少或者過多的關(guān)鍵幀都是不理想的。關(guān)鍵幀過少會導(dǎo)致遺漏部分重要的信息,相反,選擇過多的關(guān)鍵幀不僅會提取到無關(guān)緊要的信息,還有可能會造成冗余。

隨著關(guān)鍵幀數(shù)目的變化,KSBOMP算法性能隨關(guān)鍵幀的變化規(guī)律如圖1所示,分析得出:隨著關(guān)鍵幀數(shù)量的增加,精度先緩慢上升后下降,召回率一直增加,但增加的速度呈下降趨勢,F值先增加后下降;當關(guān)鍵幀數(shù)量較少時,隨著關(guān)鍵幀的增加,更多的關(guān)鍵幀將會和用戶總結(jié)中的關(guān)鍵幀相匹配,性能會逐漸提升;隨著更多的關(guān)鍵幀被選擇,會選擇到不能與用戶總結(jié)相匹配的關(guān)鍵幀,而且多個關(guān)鍵幀可能會匹配到同一個用戶總結(jié)的關(guān)鍵幀,即出現(xiàn)關(guān)鍵幀冗余情況,性能下降。

3.2.2 性能比較 將KSBOMP算法分別與DT[3]、STIMO[4]、VSUMM[5]、MSR[12]、SMRS[17]、SOMP[18]、AGDS[13]、NSDS[14]算法進行比較。DT、STIMO、VSUMM算法是基于聚類的視頻總結(jié)算法,它們的結(jié)果可以從VSUMM算法的官方網(wǎng)站下載,其他的5種算法都是基于稀疏表示的算法。表1是不同算法的實驗結(jié)果數(shù)據(jù)對比,表中加粗數(shù)據(jù)代表最優(yōu)數(shù)據(jù)。

表1 不同算法的實驗結(jié)果數(shù)據(jù)對比

從表1可以看出,KSBOMP算法的F值在所有對比算法中最高,說明KSBOMP算法的總體性能最好。一般來說,選擇的關(guān)鍵幀的數(shù)目越多,與用戶總結(jié)相匹配的關(guān)鍵幀也就越多,召回率也就會越高,因此MSR、SMRS、SOMP、AGDS、NSDS、KSBOMP算法的召回率高于其他3種算法。VSUMM擁有最高的精度,但是選擇的關(guān)鍵幀的數(shù)目較少,所以會遺漏部分關(guān)鍵幀,導(dǎo)致召回率和F值不高。具體來看,KSBOMP算法的精度僅低于VSUMM算法,召回率在所有算法中最高,說明用戶總結(jié)中的大部分關(guān)鍵幀被KSBOMP算法選中,且選擇的不與用戶總結(jié)相匹配的關(guān)鍵幀也不是很多。綜合來看,KSBOMP算法在精度、召回率和F值三個評測標準中都具有優(yōu)秀的表現(xiàn)。

為了對算法的時間復(fù)雜度進行比較,將KSBOMP算法和基于稀疏表示的對比算法在相同的計算平臺(CPU型號Core i7-6700,3.4 GHz,RAM容量12 GB)上實驗,以50個視頻的平均運行時間對算法的時間復(fù)雜度進行表示,實驗結(jié)果如表2所示,可以看出,KSBOMP算法的運行時間僅多于MSR和NSDS算法,但是遠遠少于其他的算法。結(jié)合表1,說明KSBOMP算法以增加少量時間復(fù)雜度為代價,獲得了性能的顯著提升。

表2 不同算法的平均運行時間

3.2.3 核函數(shù)的影響 為探究不同類型的核函數(shù)對KSBOMP算法的影響,采用高斯核函數(shù)和線性核函數(shù)分別進行實驗。兩種核函數(shù)的性能比較如圖2所示,可以看出:隨著關(guān)鍵幀數(shù)量的增加,采用高斯核函數(shù)的性能明顯優(yōu)于采用線性核函數(shù),即使采用線性核函數(shù),KSBOMP算法的性能也優(yōu)于表1中的對比算法。

圖2 高斯核函數(shù)和線性核函數(shù)性能比較

3.2.4 非線性和塊稀疏的有效性 將KSBOMP算法與只考慮非線性和只考慮塊稀疏的兩種算法進行對比,證明聯(lián)合考慮兩種屬性的有效性。具體地,KSBOMP算法和以下兩種算法進行比較:(1)只考慮幀間的非線性屬性,未引入視頻的塊稀疏特性的非線性稀疏字典選擇算法[14],簡稱為非線性算法;(2)只考慮視頻的塊稀疏特性,未引入幀間的非線性屬性的算法,簡稱為塊稀疏算法。KSBOMP算法同時考慮非線性和塊稀疏特性,三種算法的性能比較結(jié)果如圖3所示,分析得出:不論關(guān)鍵幀的數(shù)量是多少,同時考慮非線性和塊稀疏特性的KSBOMP算法的性能總是優(yōu)于非線性算法,此結(jié)果證明了考慮塊稀疏特性的有效性;當關(guān)鍵幀數(shù)量較少時,同時考慮非線性和塊稀疏特性的KSBOMP算法的性能和只考慮塊稀疏算法的性能基本一致,但是隨著關(guān)鍵幀數(shù)量的增加,前者的性能明顯優(yōu)于后者,此結(jié)果證明了考慮非線性的有效性。

圖3 三種算法的性能比較

4 結(jié) 論

本文主要研究基于稀疏表示的視頻總結(jié)方法,同時考慮視頻幀之間的非線性關(guān)系和關(guān)鍵幀的塊稀疏特性。通過核函數(shù)將視頻幀映射到高維特征空間,使視頻幀之間的關(guān)系由非線性轉(zhuǎn)化線性,建立了非線性稀疏字典選擇模型用于提取關(guān)鍵幀;在非線性模型的基礎(chǔ)上,通過視頻幀鄰域內(nèi)的內(nèi)容相似性,將視頻分為幀塊,將關(guān)鍵幀的塊稀疏特性納入模型,建立了非線性塊稀疏字典選擇模型來提取關(guān)鍵幀塊。為了優(yōu)化所提出的模型,本文還設(shè)計了KSBOMP算法,并在基準視頻數(shù)據(jù)集上與文獻[3-5,12-14,17-18]的算法進行了對比實驗,結(jié)果表明,KSBOMP算法在性能和效率上都有一定的優(yōu)勢。

目前,KSBOMP算法還有待改進之處。首先,每個幀塊包含相同數(shù)量的幀,但實際中固定長度的幀塊中的視頻幀可能會存在不相似的內(nèi)容,因此在下一步的工作中,可以考慮結(jié)合鏡頭邊界檢測技術(shù),根據(jù)視頻的內(nèi)容變化來劃分幀塊。另外,首先確定關(guān)鍵幀塊,然后將關(guān)鍵幀塊的中間幀選為關(guān)鍵幀,此策略雖比較簡單,但可能會造成選擇的關(guān)鍵幀在此幀塊中并不是最具有代表性的,所以后續(xù)考慮更高效的選擇策略來進一步提高算法的性能。