潘 磊,束 鑫,程 科

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

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

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

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

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

關(guān)鍵幀提取；視頻檢索；壓縮傳感；EMD距離

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

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

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

近年來(lái)，一些學(xué)者提出了若干新型的關(guān)鍵幀提取方法，如基于熵的提取法、基于注意力模型的提取法、基于最大后驗(yàn)概率MAP的提取法、基于稀疏表達(dá)的提取法等，具體可見(jiàn)文獻(xiàn)[7-10]。

2 基于壓縮傳感和EMD的關(guān)鍵幀提取

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

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

2.1.1 壓縮傳感理論

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

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

y=Rx

(1)

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

(2)

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

(3)

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

2.1.2 基于壓縮傳感的幀低維特征計(jì)算

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

(4)

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

(5)

S={s1,s2,…,sN}

(6)

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

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

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

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

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

(7)

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

(8)

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

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

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

圖1 子鏡頭序列

2.2 基于EMD距離的關(guān)鍵幀提取

2.2.1 EMD距離

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

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

(9)

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

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

(11)

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

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

(12)

(13)

(14)

(15)

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

(16)

(17)

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

2.2.2 幀間EMD距離計(jì)算與關(guān)鍵幀提取

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

(18)

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

(19)

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

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

實(shí)驗(yàn)環(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。測(cè)試數(shù)據(jù)包括紀(jì)錄片、電影、電視劇等共十段手工標(biāo)注的高清視頻，具體信息如表1所示。

表1 實(shí)驗(yàn)視頻信息

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

算法性能評(píng)價(jià)標(biāo)準(zhǔn)采用基準(zhǔn)精確率，也即基于100%查全率條件下的最高精確率，如式(20)所示

(20)

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

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

表2 基準(zhǔn)精確率實(shí)驗(yàn)結(jié)果

序號(hào)視頻名稱(chēng)本文算法文獻(xiàn)[4]算法文獻(xiàn)[10]算法1BBC-10810750782BBC-20880840793ABiteofChina0800740774ThePalaceMuseum0760690655Transformer30720680706Underthesea078068072724Hours0820770798Godzilla0780720729Thematrix06706206310Themonkeyking057053055平均結(jié)果076070071

圖2 基準(zhǔn)精確率比較

圖3 部分提取的關(guān)鍵幀

4 小結(jié)

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

[1] 蔣鵬， 秦小麟. 基于視覺(jué)注意模型的自適應(yīng)視頻關(guān)鍵幀提取[J]. 中國(guó)圖象圖形學(xué)報(bào)，2009，14(8)：1650-1655.

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

[3] 吳開(kāi)興，沈志佳.基于吞噬聚類(lèi)的關(guān)鍵幀提取新算法[J].電視技術(shù)，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)英， 張正軍. 基于互信息量的關(guān)鍵幀全局優(yōu)化提取方法[J]. 電視技術(shù)，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] 劉云鵬， 張三元， 王仁芳， 等. 視覺(jué)注意模型的道路監(jiān)控視頻關(guān)鍵幀提取[J]. 中國(guó)圖象圖形學(xué)報(bào)，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] 喻玲娟， 謝曉春. 壓縮感知理論簡(jiǎn)介[J]. 電視技術(shù)，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] 束鑫，吳小俊，潘磊. 一種新的基于形狀輪廓點(diǎn)分布的圖像檢索[J]. 光電子·激光，2009，20(10)： 1385-1389.

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

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

程 科(1972— )，博士，副教授，主要研究方向?yàn)閳D像處理。

責(zé)任編輯：閆雯雯

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

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

TP391.4

A

10.16280/j.videoe.2015.17.002

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