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

2017-01-14王华秋殷志恒

计算机时代 2016年12期

王华秋+殷志恒

摘要：视频镜头分割和关键帧提取是当前数字视频系统发展的关键步骤。在AP聚类算法之上做了两点改进：一是在初始相关系数矩阵中增加权重，提高聚类精度；二是自适应调整阻尼系数，提高收敛速度。先利用颜色信息加权和相邻帧间差方法把视频分割成镜头，再利用改进的AP聚类算法对镜头提取关键帧。实验结果表明，所提出的方法有效地解决了关键帧提取方法中耗时高和视觉信息低效的问题。

关键词：数字视频；镜头分割；关键帧提取； AP聚类

中图分类号：TP391.41 文献标志码：A 文章编号：1006-8228（2016）12-90-05

Abstract： Video shot segmentation and key frame extraction is the critical step in the current digital video system development. In this paper， the AP （affinity propagation） clustering algorithm is improved in the two points： first， the weight is increased in the initial correlation coefficient matrix to improve the clustering accuracy； second， the damping coefficient is adjusted adaptively to improve the convergence rate. Use the weighted color information and adjacent frame difference method to divide the video into shots， and then use the improved AP clustering algorithm to extract the key frames from the 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 methods.

Key words： digital video； shot segmentation； key frame extraction； affinity propagation clustering

0 引言

随着视频采集、存储与分布技术上的进步，教学视频在学生日常生活中的访问次数呈现指数级增长。如何帮助学生有效地浏览及检索其感兴趣的视频，将具有重要的理论意义和实用价值。作为基于内容的视频检索[1-2]基础，如何把视频数据组织成为更加紧凑的关键帧则是本文要探讨的问题。

多年来，各种聚类算法被应用于关键帧提取。通常来说，当聚类完成后，在每个类别中选择一幅图像作为关键帧。这种聚类算法的性能在很大程度上依赖于用户输入值的大小或设置阈值参数值高低（例如，簇的数目）。此外，用于测量帧之间的相似度的标准也显著地影响了关键帧设置。并且，许多现有的视频检索方法在预处理阶段使用均匀采样方法会导致一些信息帧的排斥。

本文描述了一种新型的有效利用改进的AP聚类提取视频关键帧的方法。该方法按照图像帧颜色信息分布不均匀特征对AP聚类的输入矩阵（也称为相似度矩阵）增加权重且自适应调整阻尼系数，避免了提取关键帧的不可靠和用户手动设置阻尼系数的随机性的影响，提高了关键帧的准确性和有效性。

1 镜头分割

视频根据其自身的结构特征，被划分为场景、镜头和视频帧三个层次，镜头边缘检测（也称为镜头分割）是视频检索和视频摘要的第一步，主要是将视频进行有效地分割[3]。其基本流程如图1所示。

先把视频转化为m个帧，然后将m个帧分为

B（3×3）个区域，接着计算每一个区域的灰度直方图，最后通过对B个区域中进行加权得到最后的相似度。根据m个帧之间的相似度和高低阈值系数可以对镜头进行突变检测和渐变检测。

1.1 相邻帧帧差值计算

YUV颜色空间是一种颜色编码方法，该方法经常被用于电视系统，其特点是可以隔离亮度信号Y和色度信号U、V[4]。它可以不通过解压缩而直接通过压缩视频获取。其中信号Y表示明亮度，信号U和V表示色度，即描述影像色彩及饱和度并指定像素的颜色[5]。

YUV颜色空间可以通过RGB空间转换得到，具体情况如公式⑴。

⑴

在对帧进行直方图统计时，会丢失位于帧中像素点的位置信息，导致反映视频的空间信息困难，所以本文采用分块直方图作为解决方案[5]。事实上，一个帧中不同部位的颜色提供的信息量各不相同，一般帧的信息主要集中在帧的正中央，而边缘部分作为背景，由此，本文对帧进行简单的分块处理，对帧中的每一块赋予不同的权重[6]。分块方法有等距离环形分块方法、不均匀分块方法等。本文采用不均匀分块方法，如图2所示。

从图2可以看出，将m个帧不均匀分为M×N（文中为3×3）大小的子块，A区域位于帧的中心，它包含了一幅帧的主要信息，赋予较大的权重；相对于A而言，B、C、D、E区域中所包含的帧信息量较少，则赋予较小的权重；F、G、H、I区域含有的帧信息量最小，赋予最小的权重。

计算m个相邻帧之间对应子块的直方图差值为：

⑵

公式⑵中的变量Y_valuek代表当前第k帧的Y分量直方图，而变量Y_valuek+1则为第k+1帧子块的Y分量直方图[7]。视频帧与分块权值相对应的加权矩阵W由公式⑶计算可以得出。

⑶

相邻两个视频帧之间对应的Y分量的直方图差值FramDiffk，k+1可以通过帧之间差值和加权矩阵计算得到，FramDiffk，k+1为：

⑷

1.2 高低阈值选取

在一个视频中，同一组镜头内各个帧表示的信息相似，而镜头间的帧表示的信息差别较大。镜头的突变是根据帧之间的Y分量直方图帧差值较大形成的，而镜头的渐变则是根据帧的亮度不断变化来实现的。

计算当前检测镜头的帧差值总和FramDiffAll为：

⑸

其中i的初始值取视频中首帧编号，n表示镜头当前位置帧到第一帧直接的帧数目[7]，代表待测镜头内的平均帧差值为：

⑹

突变镜头检测的自适应高阈值为：

⑺

渐变镜头检测的自适应低阈值为：

⑻

其中公式⑺和公式⑻中的高阈值系数μ值和低阈值系数υ值对镜头检测准确度影响很大，经过大量的实验对比，这里取μ的值为3.5，υ的值为1.6。

1.3 镜头检测模块

由公式⑺和公式⑻的高阈值和低阈值与相邻帧之间的相似度矩阵D中的相似度做比较，进行镜头的切变检测和渐变检测。如果相似度比低阈值小，表明两个帧之间存在突变；反之则表明两个帧之间存在渐变。

2 关键帧提取

2.1 AP算法

AP（affinity propagation clustering）算法是由Frey等人于2007年提出的一种新型无监督聚类算法[8]，该算法无需预先指定聚类数目，在迭代过程中不断搜索合适的聚类中心，避免了聚类结果受初始类代表点影响的缺点。同时该算法在处理多类数据时运算速度较快，性能更优。

算法以n个数据点两两之间的相似度组成的相似度矩阵Sn×n作为算法的输入，数据点k成为聚类中心的衡量准则依赖于相似度矩阵中的对角线上的数值S（k，k）大小[9]。初始时将所有样本点当作是一个潜在的聚类中心点，根据各结点间传递吸引力消息来确定聚类中心，吸引力消息包括吸引度（responsibility）和归属度（availability），吸引度r（i，k）表示数据点k作为数据点i聚类中心的适合程度；归属度a（i，k）表示数据点i选择数据点k作为聚类中心的合适程度，消息传递过程如图3所示[10]。

公式⑼中是计算相似度矩阵S（i，j）的大小，其中p（i）称之为参考度p（preference），它影响着AP聚类的数目。假设潜在的聚类中心都是由每个数据点组成，那么参考度的取值相等；如若参考度的取值为相似度矩阵S（i，j），则迭代后的聚类数目相等；如若参考度取值最小，则迭代生成的聚类数目最少[9]。

公式⑿和⒀中λ为收敛系数，可以通过调节收敛系数的大小控制算法的收敛速度及稳定性。聚类中心在迭代次数范围内不发生变化或者迭代次数超过预期设置的最大阈值条件下，程序停止计算，并确定各类的样本点以及聚类中心，否则在其他条件下，程序继续迭代[11]。

2.2 改进的AP算法

2.2.1 增加相似度矩阵权重

传统的AP聚类算法对不同帧之间的相似度矩阵S的值是通过计算两个不同帧之间的平方欧式距离，并且对一个帧的相似度矩阵S（k，k）的值参考度p取值为S的均值。采用该方法计算简便、时间复杂度低，但是容易导致在最后聚类之后得到的关键帧类别不精确（也就是说本应该在该类中的关键帧却在另外一类中），查准率不高；也忽略了帧与帧之间的相互关联关系。

为了减小不同帧之间的相似度矩阵的误差和精确地找出关键帧并提高聚类的精度，本文在传统的AP聚类算法上对相似度矩阵增加了权重。在各帧之间计算视频帧的相似度的时候，帧和帧之间会存在关联关系，具体计算方式如公式⒂和⒃公式。

⒂

⒃

公式⒂和⒃中，S（i，j）是输入数据和的相似度矩阵，其中wk是表示计算单元的权重。

2.2.2 调整收敛系数

传统的AP聚类算法收敛系数固定不变，文献[8]通过实验发现，收敛系数越大则收敛过程越稳定，迭代曲线较平稳，但收敛速度较慢，相反，收敛系数越小迭代过程振荡程度越高收敛速度较快，因此，找到一个合适的收敛系数对AP算法有较大的影响。本文借鉴上述思想，提出一种收敛系数动态调整方案，在AP算法更新迭代过程中动态调整收敛系数，使之在保证收敛精度的同时具有较快的收敛速度。

假设共有n个数据点，两两之间的相似度组成相似度矩阵Sn×n，由于我们希望AP算法在开始时具有较快的收敛速度，快速接近收敛状态，而在接近收敛时减少振荡，逐渐趋于收敛状态，同时AP算法中数据点k成为聚类中心的衡量准则常常是依赖于相似度矩阵中的对角线上的数值S（k，k）大小，由此我们根据聚类算的迭代过程中Sn×n对角线上数值的变化速率来确定收敛系数的大小，具体方法如下：

⒄

公式⒄中λ0为初始收敛系数，本文中设置λ0=0.75。，表示数据点k在第i次迭代后为聚类中心的合适程度。α和β代表范围参数，分别用来调整算法收敛系数的波动区间和改变速率，参数α的数值越大，迭代过程中的波动情况对收敛系数的影响因素越大。β主要用于配合α，使得收敛系数的变化范围在合理范围内，本文中α=0.4，β=0.5。从式中可以看出，当两次迭代变化较大时，说明此时迭代仍处于初期，未进入稳定阶段，应使其保持快速收敛状态，快速收敛至较稳定状态。当两次迭代变化较小时，说明此时已进入稳定状态，通过上式可以增大收敛系数，使其不至于振荡，逐渐趋于稳定状态。

3 实验结果及分析

3.1 实验环境

实验在Windows7 64位操作系统下进行，软件测试环境为MATLABR2010b，实验的硬件环境为CPU：Intel（R） Core（TM）2 Duo，内存：4G。

3.2 聚类效果评价指标

本研究通过两个指标衡量聚类算法的性能：F-度量值[13]，收敛次数。F-度量值是用来反映关键帧提取中查准率和查全率的评价指标。用于度量聚类算法的准确性，而收敛次数指AP算法更新迭代至稳定状态所花费的迭代次数。

假设ni是代表类别i的视频帧的数量，nj是代表聚类j的视频帧数目，nij是聚类j中属于类别i的帧数目，则查准率P（i，j）和查全率R（i，j）的定义[14]如下：

⒅

对应的F-度量值F（i，j）的定义如下：

⒆

全局聚类的F-度量值的定义为：

⒇

其中n为帧总数和，F值越高，证明聚类效果越好。

3.3 改进的AP聚类算法在关键帧提取中的应用

为了衡量文中提出的在关键帧提取中所用改进AP算法与传统的AP算法之间的优劣性，从C语言程序设计、机器学习、Web智能与大数据和数据挖掘四个教学视频中抽取了部分视频进行测试，其中视频序列从1500多帧到8000帧之间，每一帧为640×360像素。四类视频提取的关键帧的结果如表1。

从影视中选取一部视频教程《数据挖掘》中的某一段视频，分别利用传统的方法与改进的方法来提取该教学视频中的关键帧，最后得出实验结果如图5和图6中所示。

从图5和图6中的对比实验结果图中可以看出，利用本文提出的方法提取出来的关键帧的数目要比传统算法的关键帧数目少，并且本文方法的聚类精度比传统的AP算法的高。

4 结束语

本文通过考虑视频帧之间的区域相关性和人工设置阻尼系数的偶然性，提出了一种新型且有效的利用区域相关和自适应阈值的AP聚类方法。该方法根据视频帧中的颜色信息分布不均匀特征对AP聚类的输入矩阵增加权重并且根据相似度值的变化速率自动阻尼系数来提取教学视频中的关键帧。经过实验验证，该方法有效地避免了提取关键帧的过程中产生随机性的阻尼系数的的影响，同时也通过增加相似度矩阵的权重提高了关键帧的准确性和有效性。根据教学视频本身的海量数据的特点，接下来的工作将在本文方法的基础上考虑并行处理技术，在保证聚类精度的同时，提高在海量的教学视频中聚类的效率。

参考文献（References）：

[1] Collomosse J P， McNeill G， Qian Y， Storyboard sketches

for Content Based Video Retrieval[C]//IEEE 12th International Conference on Computer Vision，2009：245-252

[2] Huang Zi， Li Yi-jun， ShaoJie， et al. Content-Based Video

search： Is there a Need， and Is it Possible[C]//International Workshop on Tnformation-Explosion and Next Generation Search，2008：12-19

[3] 蒋元友.一种基于聚类的关键帧提取算法[J].数字技术与应

用，2014.

[4] 周海燕.片上LCD控制器中多层显示的设计与实现[D].东南

大学，2010.

[5] 刘艳红.视频镜头分割算法综述[J].科技创新与应用，2014.

[6] 王华秋，王重阳，聂珍.空间密度聚类在数字图书馆图像检索

中的应用[J].现代情报，2016.36（2）：129-131