基于多重壓縮感知和距離計(jì)算的視頻關(guān)鍵幀提取

潘 磊，束 鑫，張 靜，祁云嵩

(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)

基于多重壓縮感知和距離計(jì)算的視頻關(guān)鍵幀提取

潘 磊1，2，束 鑫1，張 靜1，祁云嵩1

(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ù)的關(guān)鍵問題．文中提出一種基于多重壓縮感知和距離計(jì)算的關(guān)鍵幀提取算法，首先將鏡頭內(nèi)的各幀圖像分割為若干不相交的塊，通過濾波器生成塊的高維特征;然后利用多個不同的、具有有限等距性質(zhì)的稀疏矩陣對塊高維特征進(jìn)行采樣，將采樣的均值作為塊的低維特征;采用多種距離計(jì)算相鄰幀對應(yīng)塊之間的差異，完成子鏡頭的分割操作，在每個子鏡頭內(nèi)部，選取與該子鏡頭平均內(nèi)容最接近的幀作為關(guān)鍵幀．實(shí)驗(yàn)表明，該算法提取出的關(guān)鍵幀能夠準(zhǔn)確描述鏡頭的主要內(nèi)容．

關(guān)鍵幀提取;壓縮感知;距離計(jì)算;子鏡頭

關(guān)鍵幀是指視頻鏡頭內(nèi)部能夠準(zhǔn)確描述該鏡頭內(nèi)容的幀圖像序列，廣泛應(yīng)用于視頻壓縮與存儲、快速檢索、場景分析等領(lǐng)域．由于關(guān)鍵幀的重要作用，相關(guān)的分析和提取向來被認(rèn)為是基于內(nèi)容的視頻分析與檢索技術(shù)的核心問題［1］，在工業(yè)界和學(xué)術(shù)界得到了廣泛重視與研究．

傳統(tǒng)的關(guān)鍵幀提取算法主要包括運(yùn)動分析法、內(nèi)容差異法、聚類分析法、壓縮域法、邊界法等．運(yùn)動分析法利用鏡頭內(nèi)部物體的運(yùn)動信息進(jìn)行估計(jì)，存在計(jì)算量大、復(fù)雜度高的缺點(diǎn);內(nèi)容差異法考慮相鄰幀間的像素值差異，在超過某個預(yù)定的閾值時提取關(guān)鍵幀，對運(yùn)動、噪聲和特效比較敏感;聚類分析法利用聚類算法將鏡頭內(nèi)容聚為若干類別，取各類別的中心作為關(guān)鍵幀，算法受到聚類效果的影響，且存在時間不連續(xù)的問題;壓縮域法通過視頻的壓縮信息進(jìn)行關(guān)鍵幀提取，無法應(yīng)用于非壓縮域的視頻，對壓縮算法的性能也較為敏感;邊界法通常提取鏡頭的首尾和中間幀作為關(guān)鍵幀，無法準(zhǔn)確描述鏡頭內(nèi)容．

近年來，許多學(xué)者提出了相應(yīng)的改進(jìn)或新型算法．例如，文獻(xiàn)［2］中采用稀疏基進(jìn)行降維，通過基于稀疏基矩陣的時空信息聚類進(jìn)行關(guān)鍵幀提取;文獻(xiàn)［3］中采用 Jensen－Shannon、Jensen－Rényi和Jensen－Tsallis 3種散度作為相鄰幀的差異度量方式進(jìn)行關(guān)鍵幀提取;文獻(xiàn)［4］中通過一種迭代的邊緣裁剪方法，利用動態(tài)德勞內(nèi)圖聚類進(jìn)行關(guān)鍵幀提取;文獻(xiàn)［5］中利用運(yùn)動、顏色和紋理特征構(gòu)造動態(tài)與靜態(tài)顯著映射，通過注意力模型進(jìn)行關(guān)鍵幀提取;文獻(xiàn)［6］中采用一種視覺特征聚合機(jī)制，將RGB空間顏色相關(guān)性、顏色直方圖和慣性矩相結(jié)合進(jìn)行關(guān)鍵幀提取;文獻(xiàn)［7］中利用共生矩陣提取幀圖像的高級語義上下文信息，通過監(jiān)控該信息的變化進(jìn)行關(guān)鍵幀提?。?/p>

由于采用了較為復(fù)雜的特征運(yùn)算和匹配方式，當(dāng)前的關(guān)鍵幀提取算法普遍需要較高的運(yùn)算和存儲開銷，提取的關(guān)鍵幀也不一定能夠準(zhǔn)確地描述鏡頭內(nèi)容．據(jù)此，文中提出一種基于多重壓縮感知和距離計(jì)算的關(guān)鍵幀提取算法，不僅可以降低運(yùn)算和存儲的需求，同時能夠得到較為準(zhǔn)確的關(guān)鍵幀集合．

1 基于塊的幀圖像特征

1.1 圖像分塊

隨著視頻編解碼和采集技術(shù)的發(fā)展，高清視頻的應(yīng)用越來越多．以720 P視頻為例，分辨率達(dá)到1 280×720，在如此大的范圍內(nèi)采用幀圖像的全局特征進(jìn)行匹配顯然是不合理的．由于視頻中的運(yùn)動和特效往往只在某些局部發(fā)生，因此，將幀圖像進(jìn)行分塊匹配，能夠較好地避免運(yùn)動與特效等消極因素帶來的干擾．文中將幀圖像分割為若干不相交的塊，采用對應(yīng)塊匹配的方式進(jìn)行特征比較，如圖1．

圖1 圖像分塊示例Fig．1 Illustration of image blocks

1.2 高維特征生成

使用濾波器對圖像進(jìn)行濾波是獲取圖像高維特征的常用做法．在視頻中，濾波模板內(nèi)的像素點(diǎn)有時需要賦予相同的權(quán)值，有時需要賦予不同的權(quán)值，因此采用均值和高斯兩種濾波器進(jìn)行濾波．濾波尺度從3開始，每次增加的步長為2，最大尺度限制在塊寬和高的25%．經(jīng)過濾波后生成的塊高維特征如式(1)．

式中:r為濾波最大尺度;Fc為濾波器;Bp，q為第p× q個塊;w和h分別為塊的寬和高．可以看出，高維特征的維度與塊的寬和高成正比，也即塊的寬與高越大，濾波生成的高維特征維度越高．

1.3 利用多重壓縮感知生成塊的低維特征

經(jīng)過濾波器濾波生成的塊高維特征能夠準(zhǔn)確描述塊的信息，然而，由于維度的影響，高維特征往往難以直接應(yīng)用于計(jì)算．例如，將分辨率為1 280× 720的幀圖像分割為8×8的塊集合，則每個塊的大小為160×90，對應(yīng)生成的高維特征維度約為105，在具有數(shù)十萬幅幀圖像的視頻中進(jìn)行如此高維的運(yùn)算顯然會造成巨大的開銷與損耗．因此，利用降維的操作將高維特征轉(zhuǎn)換為低維特征是實(shí)際運(yùn)算中的必然選擇．

壓縮感知是一種新型信號采樣與復(fù)原理論［8－15］，與傳統(tǒng)的香農(nóng)——奈奎斯特采樣相比，壓縮感知能夠以較低的頻率對信號進(jìn)行采樣，得到的低維信號較好地保留了原始信號的信息，并能夠以較高的概率復(fù)原原始信號．壓縮感知進(jìn)行信號采樣的過程如式(2):

式中:x為原始信號;y為采樣信號;R為M×N的采樣矩陣;為達(dá)到降維的目標(biāo)，一般有M?N．

根據(jù)壓縮感知理論，如果x是K稀疏的，則當(dāng)R滿足有限等距性質(zhì)(RIP)時，y能夠以較高概率復(fù)原x．常用的符合有限等距性質(zhì)且具有稀疏性的矩陣如式(3):

在R為標(biāo)準(zhǔn)正態(tài)分布的條件下，λ的取值一般為1，3，N1/2或N/logN．

由以上可以看出，直接使用壓縮感知思想能夠?qū)崿F(xiàn)高維特征的降維操作．但是，式(2)、(3)能夠準(zhǔn)確應(yīng)用于采樣和復(fù)原的前提是原始信號必須是K稀疏的，而高維圖像濾波信號并不能保證具備這一前提．換句話說，單次使用壓縮感知得到的低維幀圖像特征，有可能出現(xiàn)較多的信息丟失，導(dǎo)致低維特征不能準(zhǔn)確描述圖像信息．基于這個推理，文中提出采用多重壓縮感知采樣的思想，將多重采樣得到的均值作為幀圖像的低維特征，從而降低采樣過程中出現(xiàn)的誤差，盡可能多的保留原始幀圖像的信息．

式中，yi，j代表第i×j塊的低維特征，用于對該塊的信息進(jìn)行描述．

2 基于多距離計(jì)算的子鏡頭分割

計(jì)算出鏡頭中所有幀圖像的塊低維特征后，下一步的工作就是采用距離度量判斷相鄰幀圖像各對應(yīng)塊之間的差異性，從而完成子鏡頭的分割操作．由于視頻存在多樣性的特點(diǎn)，單純使用某一種距離無法準(zhǔn)確判定兩個塊之間的差異程度．因此，文中采用多距離計(jì)算的方式綜合衡量塊與塊之間的差異．

2.1 距離度量公式

塊的低維特征可以看作是向量空間中的點(diǎn)，因此，塊與塊之間的差異可以通過點(diǎn)與點(diǎn)之間的距離進(jìn)行衡量．從向量的直線距離和夾角距離兩個方面考慮，文中采用閔可夫斯基距離族、標(biāo)準(zhǔn)歐幾里德距離、余弦距離族和馬哈拉諾比斯距離進(jìn)行差異度量，共8種距離計(jì)算方法，如式(8～13):

式(8)為閔可夫斯基距離族，采用該族中的歐幾里德距離、曼哈頓距離和切比雪夫距離．式(9)為標(biāo)準(zhǔn)歐幾里德距離．式(10)為余弦距離，式(11)、(12)分別為余弦距離族中的修正余弦距離和皮爾遜相關(guān)系數(shù)距離．式(13)為馬哈拉諾比斯距離．

將以上距離進(jìn)行綜合計(jì)算，能夠有效克服其中一種或幾種距離因?qū)α烤V、數(shù)值、角度等因素敏感而引起的差異度量錯誤問題，從而提升計(jì)算的準(zhǔn)確性和魯棒性．

2.2 多距離計(jì)算下的子鏡頭分割

根據(jù)前文描述的圖像分塊、高低維特征計(jì)算、距離度量等，設(shè)計(jì)子鏡頭分割算法如下:

1)將鏡頭內(nèi)部所有的幀進(jìn)行分塊;

2)計(jì)算出每幀的各塊高低維特征;

3)對于相鄰幀fk和fk+1，可以計(jì)算出8個距離矩陣，如式(14):

4)計(jì)算出所有相鄰幀的8個距離矩陣的均值矩陣和協(xié)方差矩陣，如式(15)、(16):

5)在相鄰幀fk和fk+1的每個距離矩陣中，找出所有滿足式(17)的元素:

式中，μ是一個較小的正數(shù)．

6)如果滿足式(17)的元素個數(shù)超過塊數(shù)的1/3，則標(biāo)記該距離矩陣為活躍距離矩陣．當(dāng)活躍距離矩陣數(shù)量超過距離矩陣總數(shù)的1/2時，認(rèn)為相鄰幀fk和fk+1是一個子鏡頭邊界．

可以看出，算法的基本思想是通過多種距離計(jì)算求出相鄰幀發(fā)生較大變化的對應(yīng)塊數(shù)量，當(dāng)這個數(shù)量超過一定值時，認(rèn)為當(dāng)前的相鄰幀屬于一個子鏡頭邊界，從而達(dá)到子鏡頭分割目標(biāo)．

3 基于子鏡頭的關(guān)鍵幀提取

每個子鏡頭反映了一段內(nèi)容相對穩(wěn)定的幀圖像序列，因此，從每個子鏡頭中提取一幅幀圖像作為關(guān)鍵幀，按子鏡頭的先后順序?qū)⑦@些關(guān)鍵幀進(jìn)行排列，就可以得到關(guān)鍵幀的集合，而這個集合，能夠準(zhǔn)確描述整個鏡頭的內(nèi)容．

按照分類的觀點(diǎn)，不同的子鏡頭可以看作是不同的類別，因此，選擇每個類別中最靠近類內(nèi)中心的幀圖像作為關(guān)鍵幀，顯然能夠準(zhǔn)確反映出該類的主要內(nèi)容．鑒于以上推理，首先計(jì)算各子鏡頭內(nèi)部的類內(nèi)中心，如式(18):

式中:C(k)為第k個子鏡頭的類內(nèi)中心;Yi(k)為該子鏡頭中第i個幀圖像的低維特征;L為該子鏡頭的長度．

其次，根據(jù)式(8～13)計(jì)算子鏡頭內(nèi)部各幀到類內(nèi)中心的距離，可以得到各幀與類內(nèi)中心之間的8個距離矩陣，如式(19):

式中，θ(k)為第k個子鏡頭類內(nèi)中心的標(biāo)記;i為該子鏡頭中第i幀的標(biāo)記;矩陣中的每個元素是按第c種距離方式計(jì)算出的對應(yīng)塊距離值．

然后，對于子鏡頭內(nèi)部各幀與類內(nèi)中心之間的距離矩陣，按照從小到大的順序計(jì)算其每個元素在各自維度上的排序，從而得到每幀的排序矩陣:

按第c種距離方式計(jì)算出對應(yīng)塊距離值在所有同位置塊距離值中的排序位置，將其作為矩陣中的每個元素．

經(jīng)8種距離方式綜合衡量后，選擇最接近于類內(nèi)中心的幀作為關(guān)鍵幀，如式(21):

式中，j(k)為第k個子鏡頭的關(guān)鍵幀位置．

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

實(shí)驗(yàn)在Intel G2020 CPU、4GB內(nèi)存的PC機(jī)上進(jìn)行，采用Matlab 2013b編程，測試數(shù)據(jù)集來源于10段1 280×720分辨率的高清視頻，這些視頻中的鏡頭和關(guān)鍵幀已通過手工進(jìn)行標(biāo)注．具體的測試視頻信息如表1．

表1 測試視頻信息Table 1 Information of the test videos

關(guān)鍵幀提取的主要用途在于為后續(xù)的視頻摘要、場景分析和情節(jié)重構(gòu)提供支撐，因此，關(guān)鍵幀的提取應(yīng)盡可能保證100%的查全率．出于以上考慮，文中采用基準(zhǔn)精確率對算法性能進(jìn)行評價，如式(22):

式中:k為正確檢測出的關(guān)鍵幀數(shù)量;f為錯誤檢測出的關(guān)鍵幀數(shù)量;k+f為滿足100%查全率條件的最小數(shù)量．

實(shí)驗(yàn)中，幀圖像被分為8×8塊，每塊的大小相同．采樣矩陣R的行數(shù)設(shè)為220，采樣次數(shù)設(shè)為10．為驗(yàn)證實(shí)驗(yàn)效果，將文中算法與文獻(xiàn)［2］和文獻(xiàn)［6］中的算法進(jìn)行了比較．表2和圖2列舉了實(shí)驗(yàn)的定量結(jié)果，表2中的A、B和C分別代表文中算法、文獻(xiàn)［2］中算法和文獻(xiàn)［6］中算法．圖3列舉了算法在部分視頻上進(jìn)行關(guān)鍵幀提取的定性結(jié)果．

表2 實(shí)驗(yàn)定量結(jié)果Table 2 Quantitative results of the experiments

圖2 實(shí)驗(yàn)效果比較Fig．2 Comparison of the experimental results

由表2和圖2可以看出，所提算法在10段測試視頻中取得了較好的實(shí)驗(yàn)效果，在每段視頻中的基準(zhǔn)精確率均高于其他兩種算法．從圖3可以看出，算法提取出的關(guān)鍵幀沒有連續(xù)和相似的問題，能夠準(zhǔn)確描述鏡頭的主要內(nèi)容．然而，在幀內(nèi)目標(biāo)劇烈運(yùn)動、拍攝特效和強(qiáng)烈光照等不利因素的干擾下，算法仍然會出現(xiàn)部分誤判的問題．這主要是因?yàn)樵谀繕?biāo)高低維特征生成過程中，單純從數(shù)值的角度建立幀圖像的特征描述，沒有考慮數(shù)值變化的速率問題，從而導(dǎo)致計(jì)算出的距離矩陣誤差較大，直接影響了子鏡頭分割的準(zhǔn)確性．這方面問題的解決，有待于高級語義信息與低級視覺特征相結(jié)合的研究．

圖3 部分視頻關(guān)鍵幀F(xiàn)ig．3 Partial video key frames

5 結(jié)論

圖像高維特征無法保證滿足K稀疏的要求，從而導(dǎo)致單次壓縮感知的采樣可能會產(chǎn)生較多的信息丟失，鑒于這個問題，文中提出采用多重壓縮感知進(jìn)行采樣并取均值的思想，能夠較好地抵消信息丟失帶來的負(fù)面影響．為進(jìn)一步提高計(jì)算的準(zhǔn)確性，文中引入圖像分塊的預(yù)處理操作，并通過多種距離度量，從直線和夾角兩個方面計(jì)算相鄰幀的特征差異．排序的運(yùn)算避免了因量綱和數(shù)值范圍不同而對距離計(jì)算產(chǎn)生干擾的問題．實(shí)驗(yàn)結(jié)果表明，所提算法在實(shí)驗(yàn)視頻中取得了較好的效果．為了更好地消除光照、運(yùn)動、噪聲和特效等因素的負(fù)面影響，今后的主要工作將集中于幀圖像高級語義信息的獲取，以及與低級視覺特征相結(jié)合生成魯棒鑒別特征的研究．

References)

［1］Liu Xiao，Song Mingli，Zhang Luming，et al．Joint shot boundary detection and key frame extraction［C］∥In Proceedings of the 21st IEEE International Conference on Pattern Recognition．TsuKuba，JAPAN: IEEE，2012:2565－2568．

［2］Kumar M，Loui A C．Key frame extraction from consumer videos using sparse representation［C］∥InProceedings of the 18th IEEE International Conference on ImageProcessing．Brussels，Belgium: IEEE，2011:2437－2440．

［3］Xu Qing，Liu Yu，Li Xiu，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．

［4］Kuanar S K，Panda R，Chowdhury A S．Video key frame extraction through dynamic Delaunay clustering with a structural constraint［J］．Journal of Visual Communication and Image Representation，2013，24 (7):1212－1227．

［5］Lai Jieling，Yi Yang．Key frame extraction based on visual attention model［J］．Journal of Visual Communication and Image Representation，2012，23(1): 114－125．

［6］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．

［7］Yong S P，Deng J D，Purvis M K．Wildlife video keyframe extraction based on novelty detection in semantic context［J］．Multimedia Tools and Applications，2013，62(2):359－376．

［8］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．

［9］Li P，Hastie T J，Church K W．Very sparse random projections［C］∥In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining．Philadelphia，USA:［s．n．］，2006:287－296．

［10］Strohmer T．Measure what should be measured:progress and challenges in compressive sensing［J］．IEEE Signal Processing Letters，2012，19(12): 887－893．

［11］Yang Jianbo，Liao Xuejun，Yuan Xin，et al．Compressive sensing by learning a Gaussian mixture model from measurements［J］．IEEE Transactions on Image Processing，2015，24(1):106－119．

［12］Engelberg S．Compressive sensing［J］．IEEE Instrumentation＆Measurement Magazine，2012，15(1): 42－46．

［13］Donoho D L．Compressed sensing［J］．IEEE Transactions on Information Theory，2006，52(4):1289－1306．

［14］Friedland S，Li Q，Schonfeld D．Compressive sensing of sparse tensors［J］．IEEE Transactions on Image Processing，2014，23(10):4438－4447．

［15］ 潘磊，束鑫，程科，等．基于壓縮感知和熵計(jì)算的關(guān)鍵幀提取算法［J］．光電子激光，2014，25(10): 1977－1982．

Pan Lei，Shu Xin，Cheng Ke，et al．A key frame extraction algorithm based on compressive sensing and entropy computing［J］．Journal of Optoelectronics· Laser，2014，25(10):1977－1982．(in Chinese)

(責(zé)任編輯:童天添)

Video key frame extraction based on multiple compressive sensing and distances'computing

Pan Lei1，2，Shu Xin1，Zhang Jing1，Qi Yunsong1
(1．School of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang Jiangsu 212003，China) (2．Key Laboratory of Modern Agricultural Equipment and Technology，Ministry of Education，Jiangsu University，Zhenjiang Jiangsu 212013，China)

Key frame extraction is considered as the key issue of content-based video retrieval．An algorithm based on multiple compressive sensing and distances'computing is proposed．In the first step，each frame in one shot is segmented into several disjoint blocks，high dimensional features of which are generated by filtering．Then，multiple different sparse matrices that satisfy restricted isometry property are employed to sample the high dimensional feature of each block，and the mean value of sampling is calculated as the low dimensional feature of each block．Several different distances are used to compute differences between corresponding blocks of neighboring frames to conduct sub-shot segmentation．The frame nearest to the average content of each sub-shot is selected as the key frame．Experimental results demonstrate that key frames extracted by the proposed algorithm can describe the main content of shot accurately．

key frame extraction;compressive sensing;distance computing;sub-shot

TP391

:A

:1673－4807(2015)05－0437－06

10．3969/j．issn．1673－4807．2015．05．006

2015－05－25

國家自然科學(xué)基金資助項(xiàng)目(61103128，61471182，61170120，61305058，61503160);江蘇省自然科學(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)室開放基金資助項(xiàng)目(NZ201303)

潘磊(1980—)，男，講師，研究方向?yàn)槟Ｊ阶R別、計(jì)算機(jī)視覺．Email:just－panlei@just．edu．cn

潘磊，束鑫，張靜，等．基于多重壓縮感知和距離計(jì)算的視頻關(guān)鍵幀提取［J］江蘇科技大學(xué)學(xué)報(bào):自然科學(xué)版，2015，29(5):437－442．