局部线性嵌入在视频镜头变换检测的应用

 

　　随着日益丰富的视频数据的出现，人们迫切期望能在大量视频数据中方便、快速地检索到自己感兴趣的视频段。而要实现视频检索，通常是先将视频分割成独立的视频镜头。镜头是指一个摄像机镜头连续拍摄的一组内在相关的连续帧，用来表现在时空上连续的一组运动，是视频检索的基本单元。镜头之间的变换通常分为切变（Cut）和渐变（Gradual）两大类，其中渐变镜头变换又可分为溶解（Dissolve）、扫换（Wipe）、淡入（Fade in）与淡出（Fade out）[1-3]等。检测出不同类型的镜头变换是对视频高层内容分析、分类、检索和其他应用的基础，因此，对镜头类型变换检测准确性的高低将直接影响到后续处理效果。

　　视频镜头边界检测是视频分段、组织、索引的首要步骤。本文在总结分析现有的镜头边界检测技术的基础上，深入研究了突变镜头的检测。总结了视频镜头边界检测中的方法和评价准则，并对各种方法进行比较。对直方图方法进行了深入的探讨，利用灰度直方图计算出帧间不连续值的方法来检测突变的方法，实验证明该方法可以准确快速地定位镜头边界。对渐变镜头检测也作了相应的分析，且介绍了边缘检测方法。镜头检测是视频分析的首要工作，综述了当前镜头边界检测的研究成果，并对其中具有代表性的方法进行了分析比较。

　　由于视频镜头变换的多样性以及视频帧高维性的特点，很难从高维中寻找到它们内在的特征，但通过选择恰当的算法在保持高维特征的情况下，把高维降到低维，然后通过分析低维中的数据，得出高维视频变换的特征数据。根据流形学习的特性和视频数据的特点，把视频表示成一幅幅图像随着时间变化而变化的一个高维空间，图像之间在时间轴上是局部相关的，图像之间呈现出特有的分布，把这种分布，看成是一个低维的流形嵌入到高维空间中进行处理。

　　1 基于局部线性嵌入（LLE）的视频镜头变换学习

　　局部线性嵌入LLE（Locally Liner Embedding）[6]是流形学习中的一种。流形学习是从观测到的现象中寻找事物的本质，找到产生数据的内在规律。本文用它来提取镜头之间的特征，以期得到对各种镜头分类的效果。

　　1.1 基于LLE特征提取

　　LLE算法操作简单，且算法中的优化不涉及到局部化。该算法能解决非线性映射，但是，当处理数据的维数过大，数量过多，涉及到的稀疏矩阵过大，不易于处理。在图1中的球形面中，当缺少北极面时，应用LLE算法则能很好的将其映射到二维空间中，如图1中的C所示。如果数据分布在整个封闭的球面上，LLE则不能将它映射到二维空间，且不能保持原有的数据流形。那么我们在处理数据中，首先假设数据不是分布在闭合的球面或者椭球面上。 LLE算法是近提出的针对非线性数据的一种新的降维方法，处理后的低维数据均能够保持原有的拓扑关系。它已经广泛应用于图像数据的分类与聚类、文字识别、多维数据的可视化、以及生物信息学等领域中。

　　LLE算法是从流形的局部入手，一个局部邻域上的流形可以近似看成是具有线性特征，在这个小的局部邻域上的一个点就可以用它的相邻点在二乘意义下的线性表示，通过连接的邻域就可以从局部逐步扩展到整体，处理过程如下。

　　给定视频Video,把视频看成是由帧序列{f1,f2,…，fn}构成的。

　　（1）将视频帧序列fi（i=1,…，n）转化为M×N（M、N为视频的行数、列数）的一维向量Fi,转换后视频帧变成n个f向量；

　　（2）用LLE算法提取镜头变换特征。

　　保存原流形中局部邻域间的相互关系，将高维数据映射到一维全局坐标系中，具体算法如下：

　　步骤1:邻域点搜索。计算出每个向量Fi的邻域点，通常取欧式距离的K个点为邻域或者固定半径ε的球状邻域。

　　步骤2:求重构误差。在Fi的邻域中，计算能重构每个Fi的权值Wij,使重构误差，即式（1）的值。

　　（3）特征提取

　　根据上面算法的步骤，把视频中得到的n个f向量数据作为数据源，用到LLE算法中，经过局部嵌入学习，求出一维向量Y,根据Y向量的值画出如图1所示的特征图。

　　因LLE对K值敏感，不同的K值，即使特征值不同也有可能得到相同的特征曲线，图1中算法的K值都取固定值15.对于2个镜头之间是切变变换，两镜头变换处的2帧之间形成一个突然上升或下降的级跃，如图1（a）所示；对于溶解型镜头变换，特征曲线表现为一个向下或向上的的光滑曲线，如图1（b）所示；对于扫换型镜头变换，特征曲线表现为一个不光滑的锯齿型曲线，如图1（c）所示；对于淡入淡出型镜头变换，特征曲线成一个"n"形或类似于"n"形曲线，如图1（d）所示。

　　为了便于特征的提取并能正确地反映镜头变化的过程，在提取特征时需选择合适的点数（即帧数），本文选择21个数据点作为镜头之间变换的过程进行实验。如果镜头变换过程中帧的数目多于21帧，则要对其进行抽样，采用等间距地抽取数据点，如淡入淡出镜头变换特征曲线，变换过程中共有71帧，如图2中的带星号线所示，经过抽样等距点后，变换成图2中左边的无星号的特征曲线，仍然保持原来渐变过程变换的特征。

　　1.2  K近邻视频镜头学习

　　有了一维流形Y向量的数据，得到了视频帧序列的一维线性曲线。根据线性曲线的特点，用K近邻法对视频序列进行学习，找出镜头变换的类型。算法的流程如图3所示。

　　（1）预处理镜头类型检测；

　　（2）将步骤（1）中处理的数据分为两部分，一部分作为学习集，另一部分作为测试集；

　　（3）提取镜头类型一维流形的特征，并根据预处理的镜头类型作相应类型标签；

　　（4）通过K近邻分类器测试测试集中镜头类型，并分出相应类别的识别率。

　　2 实验与分析

　　2.1 选择数据源

　　为了验证本文所述方法的有效性，在开放式视频库（www.open-video.org）中几段视频，各段视频帧数、镜头类型数和镜头数量如表1所示。

　　2.2 实验比较与分析

　　从表1中抽取每种镜头数各30个，共120个，然后从120个镜头变换中随机抽取每种各20个作为学习数据，剩下作为测试数据。用KNN分类器进行分类，验证上述方法的实验结果及其受K值的影响情况。取相应的 K值，实验结果数据如表2所示，不同K值实验结果如图4所示。

　　图4纵坐标数值表示镜头变换类型的识别率，横坐标表示K近邻分类器的不同K值。当K值为3时，除溶解的识别率为90%外，其他三种变换类型的识别率都达到了100%.从图4中可以看出，渐变识别率随着K值的增加而下降。这是因为在提取曲线特征，因帧数过多，间隔提取帧值时，造成渐变镜头特征曲线相互靠近，使渐变镜头类型特征曲线可能互串。从平均识别率看，在K值为3时，识别可达97.5%;在K值为9时，识别率为77.5%.

　　本文提出了一种基于流形学习和K近邻分类器相结合的镜头类型检测方法。通过流形学习获得了视频帧的原始特征，便于把高维变换到低维来分析、处理。

　　今后还要做的工作有：针对渐变或渐变中的一种采用流形实现镜头变换的检测；实现一个能自动处理视频镜头分割的系统，为关键帧提取、视频摘要做好坚实的基础。