采用自适应聚类的教学视频关键帧研究

1、采用自适应聚类的教学视频关键帧研究摘要：视频镜头分割和关键帧提取是当前数字视 频系统发展的关键步骤。在ap聚类算法之上做了两 点改进：一是在初始相关系数矩阵中增加权重，提高 聚类精度;二是自适应调整阻尼系数，提高收敛速度。 先利用颜色信息加权和相邻帧间差方法把视频分割成 镜头,再利用改进的ap聚类算法对镜头提取关键帧。 实验结果表明，所提出的方法有效地解决了关键帧提 取方法中耗时高和视觉信息低效的问题。关键词：数字视频；镜头分割；关键帧提取；ap 聚类中图分类号:tp391.41文献标志码：a文章编号: 1006-8228 (2016) 12-90-05abstract： video shot

2、 segmentation and key frame extraction is the critical step in the current digital video system development. in this paper,the ap (affinitypropagation) clustering algorithm is improved in the two points： first， the weight is in creased in the initial correlation coefficient matrix to improve the clu

3、stering accuracy； second， the damping coefficient is adjusted adaptively to improve the con verge nee rate. use the weighted color in formati on and adjace nt frame differenee method to divide the video into shots, and then use the improved ap clustering algorithm to extract the key frames from the

4、shots the experimental results show that the method proposed can effectively solve the problems of high time consuming and low efficiency of capturing visual information in the key frame extraction methodskey words： digital video； shot segmentation； key frame extraction； affinity propagation cluster

5、ing0引言随着视频采集、存储与分布技术上的进步，教学 视频在学生日常生活中的访问次数呈现指数级增长。 如何帮助学生有效地浏览及检索其感兴趣的视频，将 具有重要的理论意义和实用价值。作为基于内容的视 频检索1-2基础，如何把视频数据组织成为更加紧凑 的关键帧则是本文要探讨的问题。多年来，各种聚类算法被应用于关键帧提取。通 常来说，当聚类完成后，在每个类别中选择一幅图像 作为关键帧。这种聚类算法的性能在很大程度上依赖 于用户输入值的大小或设置阈值参数值高低（例如，簇的数目）。此外，用于测量帧之间的相似度的标准也 显著地影响了关键帧设置。并且，许多现有的视频检 索方法在预处理阶段使用均匀采样方法会

6、导致一些信 息帧的排斥。本文描述了一种新型的有效利用改进的ap聚类 提取视频关键帧的方法。该方法按照图像帧颜色信息 分布不均匀特征对ap聚类的输入矩阵（也称为相似 度矩阵）增加权重且自适应调整阻尼系数，避免了提 取关键帧的不可靠和用户手动设置阻尼系数的随机性 的影响，提咼了关键帧的准确性和有效性。1镜头分割视频根据其自身的结构特征，被划分为场景、镜头和视频帧三个层次，镜头边缘检测（也称为镜头分 割）是视频检索和视频摘要的第一步，主要是将视频 进行有效地分割。其基本流程如图1所示。先把视频转化为m个帧，然后将m个帧分为b (3x3)个区域，接着计算每一个区域的灰度直方图，最后通过对b个区域中进行

7、加权得到最后的相 似度。根据m个帧之间的相似度和高低阈值系数可以 对镜头进行突变检测和渐变检测。1.1相邻帧帧差值计算yuv颜色空间是一种颜色编码方法，该方法经常 被用于电视系统，其特点是可以隔离亮度信号y和色 度信号u、v4o它可以不通过解压缩而直接通过压 缩视频获取。其中信号丫表示明亮度，信号u和v表 示色度，即描述影像色彩及饱和度并指定像素的颜色 。yuv颜色空间可以通过rgb空间转换得到，具体 情况如公式。(1)在对帧进行直方图统计时，会丢失位于帧中像素 点的位置信息，导致反映视频的空间信息困难，所以 本文采用分块直方图作为解决方案。事实上，一个 帧中不同部位的颜色提供的信息量各不相同

8、，一般帧 的信息主要集中在帧的正中央，而边缘部分作为背景, 由此，本文对帧进行简单的分块处理，对帧中的每一 块赋予不同的权重。分块方法有等距离环形分块方 法、不均匀分块方法等。本文采用不均匀分块方法， 如图2所示。从图2可以看出，将m个帧不均匀分为mxn(文 中为3x3)大小的子块，a区域位于帧的中心，它包 含了一幅帧的主要信息，赋y较大的权重；相对于a 而言，b、c、d、e区域中所包含的帧信息量较少，则 赋予较小的权重；f、g、h、i区域含有的帧信息量最 小，赋予最小的权重。计算m个相邻帧之间对应子块的直方图差值为:(2) 公式中的变量y_valuek代表当前第k帧 的y分量直方图，而变量y

9、_valuek+1则为第k+1帧子 块的y分量直方图。视频帧与分块权值相对应的加 权矩阵w由公式计算可以得出。(3)相邻两个视频帧之间对应的y分量的直方图差值 framdiffk, k+1可以通过帧之间差值和加权矩阵计算 得到，framdiffk, k+1 为：1.2高低阈值选取在一一个视频中，同一组镜头内各个帧表示的信息 相似，而镜头间的帧表示的信息差别较大。镜头的突 变是根据帧之间的y分量直方图帧差值较大形成的，而镜头的渐变则是根据帧的亮度不断变化来实现的。 计算当前检测镜头的帧差值总和framdiffaii为:其中i的初始值取视频中首帧编号，n表示镜头当 前位置帧到第一帧直接的帧数目7,

10、代表待测镜头内 的平均帧差值为：突变镜头检测的自适应高阈值为: 渐变镜头检测的自适应低阈值为: 其中公式和公式中的高阈值系数口值和低阈 值系数u值对镜头检测准确度影响很大，经过大量的 实验对比，这里取口的值为3.5, u的值为1.6。13镜头检测模块由公式和公式的高阈值和低阈值与相邻帧之 间的相似度矩阵d中的相似度做比较，进行镜头的切 变检测和渐变检测。如果相似度比低阈值小，表明两 个帧之间存在突变；反之则表明两个帧之间存在渐变。2关键帧提取2.1 ap算法ap (affinity propagation cluster!ng) 算法是由 frey等人于2007年提出的一种新型无监督聚类算法,

11、 该算法无需预先指定聚类数目，在迭代过程中不断搜 索合适的聚类中心，避免了聚类结果受初始类代表点 影响的缺点。同时该算法在处理多类数据时运算速度 较快，性能更优。算法以n个数据点两两之间的相似度组成的相似 度矩阵snxn作为算法的输入，数据点k成为聚类中 心的衡量准则依赖于相似度矩阵中的对角线上的数值 s (k, k)大小9。初始时将所有样本点当作是一个潜 在的聚类中心点，根据各结点间传递吸引力消息来确 定聚类中心，吸引力消息包括吸引度(responsibility) 和归属度(availability),吸引度r (i, k)表示数据点 k作为数据点i聚类中心的适合程度；归属度a (i, k

12、) 表示数据点i选择数据点k作为聚类中心的合适程度, 消息传递过程如图3所示10o公式中是计算相似度矩阵s (i, j)的大小，其 中p (i)称之为参考度p (preference),它影响着ap 聚类的数目。假设潜在的聚类中心都是由每个数据点 组成，那么参考度的取值相等；如若参考度的取值为 相似度矩阵s (i, j),则迭代后的聚类数目相等；如 若参考度取值最小，则迭代生成的聚类数目最少。公式(和(中入为收敛系数，可以通过调节收敛 系数的大小控制算法的收敛速度及稳定性。聚类中心 在迭代次数范围内不发生变化或者迭代次数超过预期 设置的最大阈值条件下，程序停止计算，并确定各类 的样本点以及聚类

13、中心，否则在其他条件下，程序继 续迭代11。2.2改进的ap算法2.2.1增加相似度矩阵权重传统的ap聚类算法对不同帧之间的相似度矩阵s 的值是通过计算两个不同帧之间的平方欧式距离，并 且对一个帧的相似度矩阵s (k, k)的值参考度p取 值为s的均值。采用该方法计算简便、时间复杂度低， 但是容易导致在最后聚类之后得到的关键帧类别不精 确(也就是说本应该在该类中的关键帧却在另外一类 中)，查准率不高；也忽略了帧与帧之间的相互关联关 系。为了减小不同帧之间的相似度矩阵的误差和精确 地找出关键帧并提高聚类的精度，本文在传统的ap 聚类算法上对相似度矩阵增加了权重。在各帧之间计 算视频帧的相似度的时

14、候，帧和帧之间会存在关联关 系，具体计算方式如公式(15)和(公式。(15) (16)公式(15)和(16)中，s (i, j)是输入数据和的相似度 2.2.2调整收敛系数矩阵,其中wk是表示计算单元的权重。传统的ap聚类算法收敛系数固定不变，文献8 通过实验发现，收敛系数越大则收敛过程越稳定，迭 代曲线较平稳，但收敛速度较慢，相反，收敛系数越 小迭代过程振荡程度越高收敛速度较快，因此，找到 一个合适的收敛系数对ap算法有较大的影响。本文 借鉴上述思想，提出一种收敛系数动态调整方案，在 ap算法更新迭代过程中动态调整收敛系数，使之在保 证收敛精度的同时具有较快的收敛速度。假设共有n个数据点，两两之间的相似度组成相 似度矩阵snxn,由于我们希望ap算法在开始时具有 较快的收敛速度，快速接近收敛状态，而在接近收敛 时减少振荡，逐渐趋于收敛状态，同时ap算法中数 据点k成为聚类中心的衡量准则常常是依赖于相似度 矩阵中的对角线上的数值s (k, k)大小，由此我们 根据聚类算的迭代过程中snxn对角线上数值的变化 速率来确定收敛系数的大小，具体方法如下：(17)公式(中入0为初始收敛系数，本文中设置入 0=0.75。，表示数据点k在第i次迭代后为聚类中心的 合适程度。