潘 磊,束 鑫,程 科

(1. 江苏科技大学 计算机科学与工程学院，江苏 镇江 212003；2. 江苏大学 现代农业装备与技术省部共建教育部重点实验室，江苏 镇江 212013)

基于压缩传感和EMD距离的视频镜头关键帧提取

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

(1. 江苏科技大学 计算机科学与工程学院，江苏 镇江 212003；2. 江苏大学 现代农业装备与技术省部共建教育部重点实验室，江苏 镇江 212013)

关键帧提取是视频内容分析与检索技术的核心问题。提出了一种基于压缩传感和EMD距离的关键帧提取方法，首先构造一个符合有限等距性质的稀疏矩阵，将帧高维特征投影到低维空间，然后通过计算帧低维特征之间的调节余弦相似度完成子镜头分割。在各子镜头中，利用EMD距离计算帧与子镜头中心的差异，并选择差异最小值所对应的帧作为该子镜头的关键帧。实验结果表明，该方法提取的关键帧能够对视频内容进行准确的描述。

关键帧提取；视频检索；压缩传感；EMD距离

随着互联网技术的快速发展，海量视频的出现给视频检索、浏览、查询和管理带来了巨大的困难，基于内容的视频检索技术(Content-based Video Retrieval，CBVR)由此而生，并迅速成为多媒体信息处理领域的热点研究方向[1-2]。通常，一个CBVR系统主要包括镜头边界检测、关键帧提取、视频摘要生成、场景聚类与分析、视频查找与检索等众多技术。其中，关键帧提取(Key Frame Extraction，KFE)是从每个镜头中提取若干幅帧图像，并利用这些帧图像描述镜头的主要内容，是CBVR系统中最重要的环节之一[3-4]。通过关键帧集合，视频的内容描述能以非常简要的方式进行，并为后续的视频摘要和场景分析等高级操作奠定了基础。由于关键帧提取对于视频内容描述的重要意义，相关研究工作得到了学术界和工业界的广泛关注。

1 传统关键帧提取方法

传统的关键帧提取方法主要包括基于镜头边界的提取方法、基于运动分析的提取方法、基于压缩域的提取方法、基于聚类的提取方法、基于特征差异的提取方法等[5-6]。基于镜头边界的提取方法出于镜头内部内容应该相对一致这个假设，提取每个镜头的起始帧、中间帧和结束帧作为关键帧，提取的关键帧位置和数量固定，并不能作为准确的内容描述；基于运动分析的提取方法一般通过光流计算，在运动的局部最小值处选取关键帧，这种方法计算量大，复杂度高，结果往往并不精确；基于压缩域的提取方法利用视频压缩编码信息，根据MPEG压缩码流中的I帧、P帧、B帧和宏块的比较进行关键帧提取，能够利用的特征较少，虽然处理速度较快，但是准确性受到压缩信息的影响；基于聚类的提取方法利用聚类技术，将镜头内部内容相对接近的帧聚成一类，并选择距离类内中心最近的帧作为各类的关键帧，该方法受聚类算法性能的影响，且由于视频具有时间性，聚类时往往受到时间因素的限制，并不能完全发挥聚类算法的效果；基于特征差异的提取方法以颜色、纹理、轮廓、形状等特征作为帧的描述，当帧间差异超过一定范围时提取一个关键帧，该方法受运动、噪声等因素的影响较大，容易提取过多的关键帧。

近年来，一些学者提出了若干新型的关键帧提取方法，如基于熵的提取法、基于注意力模型的提取法、基于最大后验概率MAP的提取法、基于稀疏表达的提取法等，具体可见文献[7-10]。

2 基于压缩传感和EMD的关键帧提取

2.1 基于压缩传感的子镜头分割

随着视频编解码技术的发展，当前视频的主流分辨率已达到1 280×720以上，也就是说，一幅通常的帧图像，就是一个1 280×720甚至更高维的信号，如果帧速为25 f/s(帧/秒)，则1 s内包含的高维信号有25个。显然，直接使用这些高维信号进行计算，所需要的计算开销极大，使得算法完全不具有实时性的效果。本文引入压缩传感理论对这个问题加以解决。

2.1.1 压缩传感理论

压缩传感又称压缩感知，是近年来出现的一种新型信号采集、编解码理论[11]。压缩传感可以用较低的频率实现对高维信号的采样，使得信号采样和压缩的过程能够同时进行，并且，采样后的低维信号基本保存了原始高维信号的信息，能够以很大的概率复原原始信号。

一般地，信号采样的过程可以通过矩阵与信号相乘的形式完成，如式(1)所示

y=Rx

(1)

式中：x是可K稀疏表示的n维原始信号；R是m×n的采样矩阵；y是对应于x的m维采样信号，n≫m。根据压缩传感理论[12-16]，如果采样矩阵R能够满足有限等距性质(RIP)，则采样y能够以很高的概率复原信号x，换句话说，y基本保留了x的所有信息。有限等距性质如式(2)所示

(2)

式中：ui和uj是任意2个具有相同稀疏基的原始信号；vi和vj是与之对应的采样信号；ε是一个介于0和1之间的很小的正数。具有RIP性质的矩阵包括高斯随机矩阵、贝努利矩阵、哈达玛矩阵和傅里叶矩阵等。根据文献[15]的证明，以下矩阵也符合RIP性质

(3)

式中：s的取值包括1，3，n1/2，n/lgn这4种情况。显然，s越大，R中非零元出现的概率越小，相应的数目就越少，但是计算精度也会随之降低。出于实时性的考虑，本文采用s=n/lgn的形式，当n的数量级为10d时，R中非零元出现的概率约为d/n， 也即共有md个非零元素。需要指出的是，由于R是一个非常稀疏的矩阵，在实际计算时，并不需要真正创建该矩阵，只需存储相应的非零元位置和值即可。

2.1.2 基于压缩传感的帧低维特征计算

首先，通过滤波器与图像卷积的形式构造帧高维特征，这里采用双向同性的均值滤波器和高斯滤波器对帧进行滤波，滤波的尺度从3开始，尺度增加步长取为4，尺度最大值控制在帧宽和高的30%范围内，具体的滤波器描述如下

(4)

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

(5)

S={s1,s2,…,sN}

(6)

其中，si代表第i帧的低维特征。根据压缩传感理论，每一个帧的低维特征都基本保留了该帧高维特征的所有信息。可以认为，实际计算时采用帧的低维特征或高维特征具有基本等同的实际效果，而采用低维特征能显著提高计算速度。

2.1.3 基于帧低维特征的子镜头分割

镜头内部受到摄像机缩放、角度变换、特效介入和物体运动等因素的影响，呈现的内容往往并不相似，因此，有必要通过子镜头分割的过程将镜头按照内容进行划分。根据上节得到的帧低维特征列向量组，设计子镜头分割策略如下：

1) 通过帧低维特征列向量组，按照时间顺序计算帧间相似度，并得到帧间相似度列向量组DS

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

(7)

式中：di表示第i帧和第i+1帧的低维特征相似度，这里采用调节余弦相似度(Adjusted Cosine Similarity)作为度量指标，定义如式(8)所示

(8)

与传统余弦相似度相比，调节余弦相似度不仅同样考虑了夹角的相似性，而且对向量中数值的差异情况也较为敏感，因此更为准确。

2) 对于镜头S内部的第i帧，以该帧为中心，建立一个宽为2τ+1的窗口，如果di是这个窗口内的局部最小值，则认为第i帧和第i+1帧是一个子镜头的边界。

经过以上两步计算，镜头S按照低维特征和时间顺序被划分成了k个子镜头集合，如图1所示。

图1 子镜头序列

2.2 基于EMD距离的关键帧提取

2.2.1 EMD距离

EMD距离全称Earth Mover’s Distance，是一种基于运输问题的分布差异度量准则[17-18]，通过求解线性规划最优解的方式计算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)

规范化的EMD距离可由式(16)和式(17)计算

(16)

(17)

式中：σi表示所有第i维数据的均方差。

2.2.2 帧间EMD距离计算与关键帧提取

在镜头S的第k个子镜头中，首先按照式(18)计算子镜头中心

(18)

子镜头代表了内容相对稳定的视频序列，子镜头中心则反映了这个序列的均值情况。因此，子镜头内部与中心相距最小的帧，最能代表子镜头的主要内容。鉴于这个推理，设计子镜头关键帧提取规则如下

(19)

式中：Lk代表第k个子镜头中关键帧的位置。对每个子镜头进行关键帧提取后，即可获得整个镜头的关键帧集合L，其中，L={L1，L2，…，Lu}。

3 实验结果与分析

实验环境为Intel Core2 Duo 2.8 GHz CPU、4 Gbyte内存、Win7 x64操作系统，采用MATLAB 2013b编程，经滤波器滤波生成的高维特征维数约为108，采样矩阵R的行数定为300。测试数据包括纪录片、电影、电视剧等共十段手工标注的高清视频，具体信息如表1所示。

表1 实验视频信息

序号视频名称分辨率帧数关键帧数1BBC-11280×72030241252BBC-21280×7201524453ABiteofChina1280×7202250564ThePalaceMuseum1280×7203374705Transformer31280×72034991906Underthesea1280×720137821724Hours1280×7202152498Godzilla1280×7201460189Thematrix1280×72022253710Themonkeyking1280×7203235113

算法性能评价标准采用基准精确率，也即基于100%查全率条件下的最高精确率，如式(20)所示

(20)

式中：Correct是指正确检测出的关键帧数量；All是指在保证查全率为100%的前提下检测出的最少关键帧数量。

表2和图2给出了算法的定量测试结果，图3给出了算法的部分定性测试结果。为验证算法的有效性，实验结果与文献[4]和文献[10]进行了比较。

表2 基准精确率实验结果

序号视频名称本文算法文献[4]算法文献[10]算法1BBC-10810750782BBC-20880840793ABiteofChina0800740774ThePalaceMuseum0760690655Transformer30720680706Underthesea078068072724Hours0820770798Godzilla0780720729Thematrix06706206310Themonkeyking057053055平均结果076070071

图2 基准精确率比较

图3 部分提取的关键帧

4 小结

提出一种基于压缩传感和调节余弦相似度的子镜头分割方法，并通过EMD距离在每个子镜头中提取距离中心最小的帧作为关键帧。与常用方法相比，本算法提取的关键帧能够更加准确的描述视频内容。今后的主要工作将侧重于特征模型的构造，进一步增加算法的鲁棒性和有效性。

[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] 陈赞， 杨卫英， 张正军. 基于互信息量的关键帧全局优化提取方法[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] 刘云鹏， 张三元， 王仁芳， 等. 视觉注意模型的道路监控视频关键帧提取[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— )，硕士，讲师，主研基于内容的信息检索；

束 鑫(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); 江苏省科技创新与成果转化(重大科技成果转化)项目(BA2012129); 江苏大学现代农业装备与技术省部共建教育部重点实验室开放基金项目(NZ201303)

TP391.4

A

10.16280/j.videoe.2015.17.002

【本文献信息】潘磊,束鑫,程科.基于压缩传感和EMD距离的视频镜头关键帧提取[J].电视技术,2015，39(17).