基于多重壓縮感知和距離計算的視頻關鍵幀提取

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

(1．江蘇科技大學計算機科學與工程學院，江蘇鎮江 212003) (2．江蘇大學現代農業裝備與技術教育部重點實驗室，江蘇鎮江 212013)

基于多重壓縮感知和距離計算的視頻關鍵幀提取

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

(1．江蘇科技大學計算機科學與工程學院，江蘇鎮江 212003) (2．江蘇大學現代農業裝備與技術教育部重點實驗室，江蘇鎮江 212013)

關鍵幀提取是基于內容的視頻檢索技術的關鍵問題．文中提出一種基于多重壓縮感知和距離計算的關鍵幀提取算法，首先將鏡頭內的各幀圖像分割為若干不相交的塊，通過濾波器生成塊的高維特征;然后利用多個不同的、具有有限等距性質的稀疏矩陣對塊高維特征進行采樣，將采樣的均值作為塊的低維特征;采用多種距離計算相鄰幀對應塊之間的差異，完成子鏡頭的分割操作，在每個子鏡頭內部，選取與該子鏡頭平均內容最接近的幀作為關鍵幀．實驗表明，該算法提取出的關鍵幀能夠準確描述鏡頭的主要內容．

關鍵幀提取;壓縮感知;距離計算;子鏡頭

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

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

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

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

1 基于塊的幀圖像特征

1.1 圖像分塊

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

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

1.2 高維特征生成

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

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

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

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

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

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

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

在R為標準正態分布的條件下，λ的取值一般為1，3，N1/2或N/logN．

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

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

2 基于多距離計算的子鏡頭分割

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

2.1 距離度量公式

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

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

將以上距離進行綜合計算，能夠有效克服其中一種或幾種距離因對量綱、數值、角度等因素敏感而引起的差異度量錯誤問題，從而提升計算的準確性和魯棒性．

2.2 多距離計算下的子鏡頭分割

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

1)將鏡頭內部所有的幀進行分塊;

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

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

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

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

式中，μ是一個較小的正數．

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

可以看出，算法的基本思想是通過多種距離計算求出相鄰幀發生較大變化的對應塊數量，當這個數量超過一定值時，認為當前的相鄰幀屬于一個子鏡頭邊界，從而達到子鏡頭分割目標．

3 基于子鏡頭的關鍵幀提取

每個子鏡頭反映了一段內容相對穩定的幀圖像序列，因此，從每個子鏡頭中提取一幅幀圖像作為關鍵幀，按子鏡頭的先后順序將這些關鍵幀進行排列，就可以得到關鍵幀的集合，而這個集合，能夠準確描述整個鏡頭的內容．

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

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

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

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

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

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

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

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

4 實驗結果與分析

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

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

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

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

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

表2 實驗定量結果Table 2 Quantitative results of the experiments

圖2 實驗效果比較Fig．2 Comparison of the experimental results

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

圖3 部分視頻關鍵幀Fig．3 Partial video key frames

5 結論

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

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］．光電子激光，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)

(責任編輯:童天添)

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

國家自然科學基金資助項目(61103128，61471182，61170120，61305058，61503160);江蘇省自然科學基金資助項目(BK20130473，BK20130471，BK20140419);江蘇省科技創新與成果轉化(重大科技成果轉化)項目(BA2012129);江蘇大學現代農業裝備與技術教育部重點實驗室開放基金資助項目(NZ201303)

潘磊(1980—)，男，講師，研究方向為模式識別、計算機視覺．Email:just－panlei@just．edu．cn

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