16
基于聚类的关键帧提取


聚类方法在人工智能、模式识别和语音识别等领域中 有着很广泛的应用，也可以使用聚类方法来提取镜头 关键帧。 实现步骤： 第一步：设某个镜头Si包含n个图像帧，可以表示为 Si={Fi1，……，Fin}，其中Fi1为首帧，Fin为尾帧。如 果相邻两帧之间的相似度定义是这相邻两帧颜色直方 图的相似度（也即是直方图特征差别），预定义一个 阈值δ控制聚类的密度。
4
关键帧提取的意义

减少视频帧间存在的大量冗余信息内容

更凝炼地表达一段视频中包含的信息，便 于对视频内容建立索引、管理
5
减少冗余信息

视频由成千上万的帧组成，视频数据流中t时刻的 图像帧和t+1时刻的图像帧在视觉特征和内容上差 别不大。 人们从由成千上万存在冗余的图像帧提取出“关 键图像帧”，而且使用这些关键图像帧表示视频 ，会更加简洁。这是在视频内容分析中提取视频 关键帧的原因之一。
25
基于PGF（peer group filtering)的关键帧提取

视频帧i和视频帧j的直方图差HDij的计算如下：
H颜色分量的归一化直方图
26
基于PGF（peer group filtering) 的关键帧提取


PGF主要思想：找出滤波窗口与中心象素特征 相近的邻域象素作为同组成员参加滤波。它是 先根据滤波窗口中邻域象素与原来象素特征的 相似性进行升序排列，再根据Fisher判别找出 该象素的同组成员，然后用滤波窗口中属于同 组成员象素的加权特征值代替原来中心象素的 特征值。 优点：很好的滤除混合噪声，且保护图像边缘 信息
和最后一幅图像作为镜头关键帧。 依据：既然在一组镜头中，相邻图像帧之 间的特征变化很少，所以整个镜头中图像 帧的特征变换也应该不大，因此选择镜头 第一帧和最后一帧可以将镜头内容完全表 达出来。

12
基于镜头边界法

缺点：以镜头首帧或尾帧或首帧加尾帧为 关键帧，这种方法虽简单，但它不考虑当 前视觉内容的复杂性，并且限制了镜头关 键帧的个数，使长短不同和内容不同的视 频镜头有相同个数关键帧，这样做并不合 理，事实上首帧或尾帧往往并非关键帧， 不能精确地代表镜头信息。
关键帧
δ=0.85
关键帧
δ=0.90
关键帧
1
2 3 11
0~302
303~388 389~439 1113~14 02
173
367 401 1219
173
367 401 1114
41
367 401 1117 1267 1348
22
基于聚类的关键帧提取

优点：1)该方法不仅计算效率高，它还能有 效地获取视频镜头的显著视觉内容。

8
2. 关键帧抽取算法
9
几种关键帧提取算法

基于抽样的方法 基于镜头边界法 基于颜色特征法 基于运动分析法 基于聚类的关键帧提取 （重点介 绍）



10
基于抽样的方法

思想 ： 基于抽样的方法是一种比较简单的方法 ，这种方法一般通过随机的抽取几帧、或者规 定间隔抽取关键帧、或者规定每个镜头提取的 帧数然后等间隔抽取。
32
28
基于PGF（peer group filtering)的关键帧提取
29
基于PGF（peer group filtering)的关键帧提取
30
基于PGF（peer group filtering)的关键帧提取
31
Feature space representation of a complex shot(center). For visualization purpose the feature space was reduced to 2d by PCA. A clustering of the frames leads to keyframes displayed on the left and right side.
27
基于PGF（peer group filtering)的关键帧提取



采用递归同类组滤波（PGF)的策略把镜头的视频帧根据 每一帧划分分两组：与第一帧属于同一组的视频帧和与第 一帧属于不同组的视频帧 PGF的主要功能是把一组数据集合通过最大化一个基于 Fisher区分分析的类间散度和两个类内散度的比率来划分 成两个类 ｛d1,…,dM}是时间序列上各个帧和第一帧的距离，这些 距离是按照从小到大的顺序排列。很显然，当距离很小时 ，这些帧和第一帧属于同一组。
13
基于颜色特征法

思想：将镜头当前帧与最后一个判断为关键帧 的图像进行比较，如有较多特征发生改变，则 当前帧为新的一个关键帧。 在实际中，可以将视频镜头第一帧作为关 键帧，然后比较后面视频帧图像与关键帧的图 像特征是否发生了较大变化，逐渐得到后续关 键帧。
14
基于颜色特征法

优点：按照这个方法，对于不同的视频镜 头，可以提取出数目不同的关键帧，而且 每个帧之间的颜色差别较大。 缺点：对摄像机的运动（如摄像机镜头拉 伸造成焦距的变化及摄像机镜头平移的转 变）很不敏感，无法量化地表示运动信息 的变化，会造成关键帧提取不稳健。
2
11 17
21
67~134
641~752 1072~11 45
90
676 1101
68
655 679 733 1074， 1102
75
662 665 675 698 738 1079 1097 1107 1133 1144
基于聚类的关键帧提取
表2 生活视频片提取关键帧结果
镜 头 ID
镜头边界
δ=0.80
24
基于聚类的关键帧提取

注：在聚类过程中也可以加入些约束条件，如每个聚 类集中的图像帧数目不应该很少，也不应该很多；每 个聚类集的聚类质心不应该“相似”，也就是这些聚 类质心的距离要大；还可以采用模糊聚类方法实现关 键帧的提取。

缺点：聚类算法最大的限制是聚类参数 δ 是否恰当， 从上面对动作片与生活片视频关键帧提取可以知道， 对于不同的应用，聚类参数 δ 的设置就差别较大，因 此一个普遍的聚类参数δ获取是相当困难的。
18
基于聚类的关键帧提取

第三步：通过上面方法将镜头 Si所包含的 n 个图像帧，分别归类到不同聚类后，就可 以选择关键帧：从每个聚类中抽取离聚类 质心最近的帧作为这个聚类的代表帧，所 有聚类的代表帧就构成了镜头Si的关键帧。 假设镜头 Si 形成了 cluster 个聚类，那么就 可以从镜头Si中提取cluster个关键帧。

19
基于聚类的关键帧提取

特点：该聚类算法由阈值δ控制，δ越大，形成的 聚类数目越多，镜头Si划分越细，选择的关键帧也 越多；反之，δ越小，所形成的聚类个数越少，镜 头Si划分越粗。

示例：表8.1和表8.2显示了当δ取不同阈值时采 取聚类算法所提取的关键帧结果。
20
基于聚类的关键帧提取
表1 动作视频片提取关键帧结果 镜头ID 镜头边界 δ=0.80 关键帧 1 0~66 41 δ=0.85 关键帧 41 δ=0.90 关键帧 134

15
基于运动分析法

依据：在视频摄影中，摄像机运动所造成的 显著运动信息是产生图像变化的重要因素。 思想：将相机运动造成的图像变化分成两类： 一类是相机焦距变化造成的；一类是相机角 度变化造成的。对前一种，选择首、尾两帧 为关键帧；对后一种，如当前帧与上一关键 帧重叠小于30%，则选其为关键帧。

6
快速全面了解视频的内容


对于只想了解大致视频内容的用户而言，他们并 不愿意花很多时间观看每一帧。 提取关键帧可以极大地节约用户的欣赏时间。用 户通过关键帧，能了解整个视频数据流所蕴含的 内容。 在通过提取关键帧的底层信息来建立索引，方便 用户对视频内容的查询。
7
小结

关键帧提取可以减少视频数据流在内容上 的冗余度，其提取原则既要在数量上精简 ，又能够反映视频内容。 前面介绍了如何通过相邻视频帧间特征发 生变换，将连续视频流分割成长短不一的 视频镜头。要进行的下一步工作是从每个 切分出来的镜头中提取关键帧，在关键帧 的基础上进行进一步的结构化。
17
基于聚类的关键帧提取

第二步：计算当前帧Fii与现存某个聚类质心间 的相似度，如果该值小于δ，则该帧与该聚类 之间距离较大，因此，Fii不能加入该聚类中。 如Fii与所有现存聚类质心相似度均小于δ，则 Fii 形成一个新的聚类， Fii 为新聚类的质心； 否则将该帧加入到与之相似度最大的聚类中， 使该帧与这个聚类的质心之间的距离最小。


优点：这种方法的优点是简单快速。 缺点：这种方法具有明显的缺点即不能够有效的 表达视频的内容。当镜头很短时可能只能抽取到 一个关键帧，这可能导致一些重要信息丢失，而 对于一些比较长的视频镜头片断，可能会有很多 相似的关键帧被提取出来，这样关键帧提取的目 的没有达到。
11
基于镜头边界法

思想： 将切分得到镜头中的第一幅图像
对于低活动性镜头，大多数情况下它会提取少 量的关键帧或仅仅一个关键帧（表2）。但对于高活 动性镜头，它会根据镜头的视觉复杂性自动提取多 个关键帧（表1）。
23
基于聚类的关键帧提取


由于该方法仅依赖于当前帧与前面帧，因此 易于在线实现。 和其他关键帧提取算法一样，虽然这里使用 颜色直方图作为相似度度量，但是任何有用 的视觉或语义特征都能被集成到这个聚类算 法中。聚类算法基本上是一个非监督过程， 用户只要提供聚类参数δ，那么聚类与关键 帧提取等过程就可以自动完成，不需要人工 干预，因此效率较高。