潘 磊,束 鑫,程 科

(1. 江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江 212003；2. 江蘇大學 現(xiàn)代農(nóng)業(yè)裝備與技術省部共建教育部重點實驗室，江蘇 鎮(zhèn)江 212013)

基于壓縮傳感和EMD距離的視頻鏡頭關鍵幀提取

潘 磊1,2,束 鑫1,程 科1,2

(1. 江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江 212003；2. 江蘇大學 現(xiàn)代農(nóng)業(yè)裝備與技術省部共建教育部重點實驗室，江蘇 鎮(zhèn)江 212013)

關鍵幀提取是視頻內(nèi)容分析與檢索技術的核心問題。提出了一種基于壓縮傳感和EMD距離的關鍵幀提取方法，首先構造一個符合有限等距性質(zhì)的稀疏矩陣，將幀高維特征投影到低維空間，然后通過計算幀低維特征之間的調(diào)節(jié)余弦相似度完成子鏡頭分割。在各子鏡頭中，利用EMD距離計算幀與子鏡頭中心的差異，并選擇差異最小值所對應的幀作為該子鏡頭的關鍵幀。實驗結(jié)果表明，該方法提取的關鍵幀能夠?qū)σ曨l內(nèi)容進行準確的描述。

關鍵幀提取；視頻檢索；壓縮傳感；EMD距離

隨著互聯(lián)網(wǎng)技術的快速發(fā)展，海量視頻的出現(xiàn)給視頻檢索、瀏覽、查詢和管理帶來了巨大的困難，基于內(nèi)容的視頻檢索技術(Content-based Video Retrieval，CBVR)由此而生，并迅速成為多媒體信息處理領域的熱點研究方向[1-2]。通常，一個CBVR系統(tǒng)主要包括鏡頭邊界檢測、關鍵幀提取、視頻摘要生成、場景聚類與分析、視頻查找與檢索等眾多技術。其中，關鍵幀提取(Key Frame Extraction，KFE)是從每個鏡頭中提取若干幅幀圖像，并利用這些幀圖像描述鏡頭的主要內(nèi)容，是CBVR系統(tǒng)中最重要的環(huán)節(jié)之一[3-4]。通過關鍵幀集合，視頻的內(nèi)容描述能以非常簡要的方式進行，并為后續(xù)的視頻摘要和場景分析等高級操作奠定了基礎。由于關鍵幀提取對于視頻內(nèi)容描述的重要意義，相關研究工作得到了學術界和工業(yè)界的廣泛關注。

1 傳統(tǒng)關鍵幀提取方法

傳統(tǒng)的關鍵幀提取方法主要包括基于鏡頭邊界的提取方法、基于運動分析的提取方法、基于壓縮域的提取方法、基于聚類的提取方法、基于特征差異的提取方法等[5-6]?；阽R頭邊界的提取方法出于鏡頭內(nèi)部內(nèi)容應該相對一致這個假設，提取每個鏡頭的起始幀、中間幀和結(jié)束幀作為關鍵幀，提取的關鍵幀位置和數(shù)量固定，并不能作為準確的內(nèi)容描述；基于運動分析的提取方法一般通過光流計算，在運動的局部最小值處選取關鍵幀，這種方法計算量大，復雜度高，結(jié)果往往并不精確；基于壓縮域的提取方法利用視頻壓縮編碼信息，根據(jù)MPEG壓縮碼流中的I幀、P幀、B幀和宏塊的比較進行關鍵幀提取，能夠利用的特征較少，雖然處理速度較快，但是準確性受到壓縮信息的影響；基于聚類的提取方法利用聚類技術，將鏡頭內(nèi)部內(nèi)容相對接近的幀聚成一類，并選擇距離類內(nèi)中心最近的幀作為各類的關鍵幀，該方法受聚類算法性能的影響，且由于視頻具有時間性，聚類時往往受到時間因素的限制，并不能完全發(fā)揮聚類算法的效果；基于特征差異的提取方法以顏色、紋理、輪廓、形狀等特征作為幀的描述，當幀間差異超過一定范圍時提取一個關鍵幀，該方法受運動、噪聲等因素的影響較大，容易提取過多的關鍵幀。

近年來，一些學者提出了若干新型的關鍵幀提取方法，如基于熵的提取法、基于注意力模型的提取法、基于最大后驗概率MAP的提取法、基于稀疏表達的提取法等，具體可見文獻[7-10]。

2 基于壓縮傳感和EMD的關鍵幀提取

2.1 基于壓縮傳感的子鏡頭分割

隨著視頻編解碼技術的發(fā)展，當前視頻的主流分辨率已達到1 280×720以上，也就是說，一幅通常的幀圖像，就是一個1 280×720甚至更高維的信號，如果幀速為25 f/s(幀/秒)，則1 s內(nèi)包含的高維信號有25個。顯然，直接使用這些高維信號進行計算，所需要的計算開銷極大，使得算法完全不具有實時性的效果。本文引入壓縮傳感理論對這個問題加以解決。

2.1.1 壓縮傳感理論

壓縮傳感又稱壓縮感知，是近年來出現(xiàn)的一種新型信號采集、編解碼理論[11]。壓縮傳感可以用較低的頻率實現(xiàn)對高維信號的采樣，使得信號采樣和壓縮的過程能夠同時進行，并且，采樣后的低維信號基本保存了原始高維信號的信息，能夠以很大的概率復原原始信號。

一般地，信號采樣的過程可以通過矩陣與信號相乘的形式完成，如式(1)所示

y=Rx

(1)

式中：x是可K稀疏表示的n維原始信號；R是m×n的采樣矩陣；y是對應于x的m維采樣信號，n?m。根據(jù)壓縮傳感理論[12-16]，如果采樣矩陣R能夠滿足有限等距性質(zhì)(RIP)，則采樣y能夠以很高的概率復原信號x，換句話說，y基本保留了x的所有信息。有限等距性質(zhì)如式(2)所示

(2)

式中：ui和uj是任意2個具有相同稀疏基的原始信號；vi和vj是與之對應的采樣信號；ε是一個介于0和1之間的很小的正數(shù)。具有RIP性質(zhì)的矩陣包括高斯隨機矩陣、貝努利矩陣、哈達瑪矩陣和傅里葉矩陣等。根據(jù)文獻[15]的證明，以下矩陣也符合RIP性質(zhì)

(3)

式中：s的取值包括1，3，n1/2，n/lgn這4種情況。顯然，s越大，R中非零元出現(xiàn)的概率越小，相應的數(shù)目就越少，但是計算精度也會隨之降低。出于實時性的考慮，本文采用s=n/lgn的形式，當n的數(shù)量級為10d時，R中非零元出現(xiàn)的概率約為d/n， 也即共有md個非零元素。需要指出的是，由于R是一個非常稀疏的矩陣，在實際計算時，并不需要真正創(chuàng)建該矩陣，只需存儲相應的非零元位置和值即可。

2.1.2 基于壓縮傳感的幀低維特征計算

首先，通過濾波器與圖像卷積的形式構造幀高維特征，這里采用雙向同性的均值濾波器和高斯濾波器對幀進行濾波，濾波的尺度從3開始，尺度增加步長取為4，尺度最大值控制在幀寬和高的30%范圍內(nèi)，具體的濾波器描述如下

(4)

3≤i≤min(0.3w,0.3h)

(5)

S={s1,s2,…,sN}

(6)

其中，si代表第i幀的低維特征。根據(jù)壓縮傳感理論，每一個幀的低維特征都基本保留了該幀高維特征的所有信息?？梢哉J為，實際計算時采用幀的低維特征或高維特征具有基本等同的實際效果，而采用低維特征能顯著提高計算速度。

2.1.3 基于幀低維特征的子鏡頭分割

鏡頭內(nèi)部受到攝像機縮放、角度變換、特效介入和物體運動等因素的影響，呈現(xiàn)的內(nèi)容往往并不相似，因此，有必要通過子鏡頭分割的過程將鏡頭按照內(nèi)容進行劃分。根據(jù)上節(jié)得到的幀低維特征列向量組，設計子鏡頭分割策略如下：

1) 通過幀低維特征列向量組，按照時間順序計算幀間相似度，并得到幀間相似度列向量組DS

DS={d1,d2,…,dN-1}

(7)

式中：di表示第i幀和第i+1幀的低維特征相似度，這里采用調(diào)節(jié)余弦相似度(Adjusted Cosine Similarity)作為度量指標，定義如式(8)所示

(8)

與傳統(tǒng)余弦相似度相比，調(diào)節(jié)余弦相似度不僅同樣考慮了夾角的相似性，而且對向量中數(shù)值的差異情況也較為敏感，因此更為準確。

2) 對于鏡頭S內(nèi)部的第i幀，以該幀為中心，建立一個寬為2τ+1的窗口，如果di是這個窗口內(nèi)的局部最小值，則認為第i幀和第i+1幀是一個子鏡頭的邊界。

經(jīng)過以上兩步計算，鏡頭S按照低維特征和時間順序被劃分成了k個子鏡頭集合，如圖1所示。

圖1 子鏡頭序列

2.2 基于EMD距離的關鍵幀提取

2.2.1 EMD距離

EMD距離全稱Earth Mover’s Distance，是一種基于運輸問題的分布差異度量準則[17-18]，通過求解線性規(guī)劃最優(yōu)解的方式計算2個分布之間的距離。令P和Q分別表示供貨站與收貨站的分布，如式(9)和式(10)所示

P={(p1,wp1),…,(pm,wpm)}

(9)

Q={(q1,wq1),…,(qn,wqn)}

(10)式中：pi和qi分別是P與Q的第i個站點，wpi是P的第i個站點需要運出的貨物量，wqi是Q的第i個站點能夠接受的貨物量，如果用D= (dij)表示P與Q站點之間的地面距離，用F=(fij)表示運輸方案，則將P中貨物運到Q所做的功可描述為

(11)

該方程受到以下條件的約束

fij≥0, 1≤i≤m,1≤j≤n

(12)

(13)

(14)

(15)

規(guī)范化的EMD距離可由式(16)和式(17)計算

(16)

(17)

式中：σi表示所有第i維數(shù)據(jù)的均方差。

2.2.2 幀間EMD距離計算與關鍵幀提取

在鏡頭S的第k個子鏡頭中，首先按照式(18)計算子鏡頭中心

(18)

子鏡頭代表了內(nèi)容相對穩(wěn)定的視頻序列，子鏡頭中心則反映了這個序列的均值情況。因此，子鏡頭內(nèi)部與中心相距最小的幀，最能代表子鏡頭的主要內(nèi)容。鑒于這個推理，設計子鏡頭關鍵幀提取規(guī)則如下

(19)

式中：Lk代表第k個子鏡頭中關鍵幀的位置。對每個子鏡頭進行關鍵幀提取后，即可獲得整個鏡頭的關鍵幀集合L，其中，L={L1，L2，…，Lu}。

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

實驗環(huán)境為Intel Core2 Duo 2.8 GHz CPU、4 Gbyte內(nèi)存、Win7 x64操作系統(tǒng)，采用MATLAB 2013b編程，經(jīng)濾波器濾波生成的高維特征維數(shù)約為108，采樣矩陣R的行數(shù)定為300。測試數(shù)據(jù)包括紀錄片、電影、電視劇等共十段手工標注的高清視頻，具體信息如表1所示。

表1 實驗視頻信息

序號視頻名稱分辨率幀數(shù)關鍵幀數(shù)1BBC-11280×72030241252BBC-21280×7201524453ABiteofChina1280×7202250564ThePalaceMuseum1280×7203374705Transformer31280×72034991906Underthesea1280×720137821724Hours1280×7202152498Godzilla1280×7201460189Thematrix1280×72022253710Themonkeyking1280×7203235113

算法性能評價標準采用基準精確率，也即基于100%查全率條件下的最高精確率，如式(20)所示

(20)

式中：Correct是指正確檢測出的關鍵幀數(shù)量；All是指在保證查全率為100%的前提下檢測出的最少關鍵幀數(shù)量。

表2和圖2給出了算法的定量測試結(jié)果，圖3給出了算法的部分定性測試結(jié)果。為驗證算法的有效性，實驗結(jié)果與文獻[4]和文獻[10]進行了比較。

表2 基準精確率實驗結(jié)果

序號視頻名稱本文算法文獻[4]算法文獻[10]算法1BBC-10810750782BBC-20880840793ABiteofChina0800740774ThePalaceMuseum0760690655Transformer30720680706Underthesea078068072724Hours0820770798Godzilla0780720729Thematrix06706206310Themonkeyking057053055平均結(jié)果076070071

圖2 基準精確率比較

圖3 部分提取的關鍵幀

4 小結(jié)

提出一種基于壓縮傳感和調(diào)節(jié)余弦相似度的子鏡頭分割方法，并通過EMD距離在每個子鏡頭中提取距離中心最小的幀作為關鍵幀。與常用方法相比，本算法提取的關鍵幀能夠更加準確的描述視頻內(nèi)容。今后的主要工作將側(cè)重于特征模型的構造，進一步增加算法的魯棒性和有效性。

[1] 蔣鵬， 秦小麟. 基于視覺注意模型的自適應視頻關鍵幀提取[J]. 中國圖象圖形學報，2009，14(8)：1650-1655.

[2] 潘磊，束鑫，程科，等.基于壓縮感知和熵計算的關鍵幀提取算法[J].光電子·激光，2014，25(10)：1977-1982.

[3] 吳開興，沈志佳.基于吞噬聚類的關鍵幀提取新算法[J].電視技術，2014，38(13)：212-214.

[4] EJAZ N， TARIQ T B， BAIK S W. Adaptive key frame extraction for video summarization using an aggregation mechanism[J]. Journal of Visual Communication and Image Representation，2012，23(7)：1031-1040.

[5] 陳贊， 楊衛(wèi)英， 張正軍. 基于互信息量的關鍵幀全局優(yōu)化提取方法[J]. 電視技術，2011，35(7)： 26-28.

[6] LIU T，ZHANG H J， QI F. A novel video key-frame-extraction algorithm based on perceived motion energy model[J]. IEEE Trans. Circuits and Systems for Video Technology，2003， 13(10)：1006-1013.

[7] XU Q， LIU Y，LI X， et al. Browsing and exploration of video sequences： a new scheme for key frame extraction and 3D visualization using entropy based Jensen divergence[J]. Information Sciences，2014(278)：736-756.

[8] 劉云鵬， 張三元， 王仁芳， 等. 視覺注意模型的道路監(jiān)控視頻關鍵幀提取[J]. 中國圖象圖形學報，2013，18(8)：933-943.

[9] LIU X， SONG M， ZHANG L， et al. Joint shot boundary detection and key frame extraction[C]//Proc. IEEE International Conference on Pattern Recognition. [S.l.]：IEEE Press，2012： 2565-2568.

[10] KUMAR M， LOUI A C. Key frame extraction from consumer videos using sparse representation[C]// Proc. IEEE International Conference on Image Processing. [S.l.]：IEEE Press，2011： 2437-2440.

[11] 喻玲娟， 謝曉春. 壓縮感知理論簡介[J]. 電視技術，2008， 32(12)：16-18.

[12] ENGELBERG S.Compressive sensing[J]. IEEE Instrumentation & Measurement Magazine，2012，15(1):42-46.

[13] DONOHO D L.Compressed sensing[J].IEEE Trans. Information Theory，2006，52(4)：1289-1306.

[14] FRIEDLAND S， LI Q， SCHONFELD D. Compressive sensing of sparse tensors[J]. IEEE Trans. Image Processing， 2014，23(10)：4438-4447.

[15] LI P， HASTIE T J， CHURCH K W. Very sparse random projections[C]//Proc. the 12th ACM SIGKDD International Conference on Knowledge Discovery And Data Mining. [S.l.]：IEEE Press，2006：287-296.

[16] QAISAR S， BILAL R M， IQBAL W， et al. Compressive sensing：from theory to applications，a survey[J]. Journal of Communications and Networks，2013，15(5)：443-456.

[17] RUBNER Y， TOMASI C， GUIBAS L J. The earth mover’s distance as a metric for image retrieval[J]. International Journal of Computer Vision，2000，40(2)：99-121.

[18] 束鑫，吳小俊，潘磊. 一種新的基于形狀輪廓點分布的圖像檢索[J]. 光電子·激光，2009，20(10)： 1385-1389.

潘 磊(1980— )，碩士，講師，主研基于內(nèi)容的信息檢索；

束 鑫(1979— )，博士，講師，主研圖像和形狀識別；

程 科(1972— )，博士，副教授，主要研究方向為圖像處理。

責任編輯：閆雯雯

Video Shot Key Frame Extraction Based on Compressive Sensing and EMD Distance

PAN Lei1,2, SHU Xin1, CHENG Ke1,2

(1.SchoolofComputerScienceandEngineering,JiangsuUniversityofScienceandTechnology,JiangsuZhenjiang212003,China； 2.KeyLaboratoryofModernAgriculturalEquipmentandTechnology,MinistryofEducationandJiangsuProvince,JiangsuUniversity,JiangsuZhenjiang212013,China)

Key frame extraction is the key issue of video content analysis and retrieval technology. A key frame extraction method based on compressive sensing and Earth Mover’s Distance is proposed. Firstly, high dimensional feature of each frame is projected to low dimensional space by a sparse matrix that satisfies Restricted Isometry Property (RIP), and then sub-shot segmentation is accomplished by computation of adjusted cosine similarity between low dimensional features. In each sub-shot, EMD distance is used to compute the difference between sub-shot center and each frame, the frame with minimum value is selected as the key frame. The experimental results show that key frames extracted by the proposed method can precisely describe video contents.

key frame extraction; video retrieval; compressive sensing; Earth Mover’s Distance

國家自然科學基金項目(61103128;61471182；61170120；61305058); 江蘇省自然科學基金項目(BK20130473；BK20130471；BK20140419); 江蘇省科技創(chuàng)新與成果轉(zhuǎn)化(重大科技成果轉(zhuǎn)化)項目(BA2012129); 江蘇大學現(xiàn)代農(nóng)業(yè)裝備與技術省部共建教育部重點實驗室開放基金項目(NZ201303)

TP391.4

A

10.16280/j.videoe.2015.17.002

【本文獻信息】潘磊,束鑫,程科.基于壓縮傳感和EMD距離的視頻鏡頭關鍵幀提取[J].電視技術,2015，39(17).