收稿日期：2020-07-13
基金项目：本项目受北京市大学生科学研究与创业行动计划资助
作者简介：张一凡（2000-），男，山西太原人，本科，主要研究方向为数字图像处理；李家辰（2000-），男，河南济源人，本科，主要研究方向为图形图像处
理。
张一凡，李家辰，旷远有，刘
盼，赵子元
（北方工业大学信息学院，北京
100144）
摘要：文章提出了一种基于k 均值聚类的视频关键帧提取算法。该算法在视频的镜头分割算法之上， 通过层次聚类对视频内容进行初步划分，
之后结合k 均值聚类算法对初步提取的关键帧进行直方图特征对比去掉冗余帧，最终确定视频的关键帧序列。经过大量的实验数据证明，该算法能够提取出冗余度较低、代表性较强的关键帧，一定程度上为视频关键帧提取提供了有效的方法。
关键词：视频镜头分割；关键帧提取；k 均值聚类中图分类号：TP391
文献标识码：A
Research on video Key Frame Extraction Based on K-means Clustering
ZHANG Yi-fan,LI Jia-chen,KUANG Yuan-you,LIU Pan,ZHAO Zi-yuan
(School of Information Science and Technology 袁North China University of Technology,Beijing 100144,China)
Abstract ：Based on the k-means clustering method,this paper proposes an algorithm for video key f
rame extraction.The algorithm,including video shots segmentation algorithm,partitions the video content through hierarchical clustering,then combined with k-means clustering algorithm for preliminary extract key frames histogram feature comparison to remove redundant frames,ultimately determine the key frames of video sequences.After a lot of testing,it is proved that the key frame redundancy extracted by this algorithm is relatively small,with high representativeness,and has certain validity of video key frame extraction.
Key words:video shots segmential;key frame extaction;k-means clustering
随着多媒体信息的日趋增多，视频作为信息的载体，其内容量渐渐宽广，成为信息交互的主流。目前网络上的视频种类多样，部分视频存在时间长、
信息冗余度大等问题，面对大量的视频，将视频多帧信息转为单帧关键帧图像能够使用户在短期内获得视频中的有效信息，视频摘要技术便应运而生。关键帧的获取则是视频摘要技术的重心。
关键帧是视频中最具代表性的帧，是视频一段相似内容的集中概括。视频关键帧提取的目的是从一段视频序列中提取出一个关键帧集合，该集合能够归结
整段视频的中心内容[1]。为了完成这一目的，必须要对源视频按照内容进行镜头划分，再在这些视频镜头内
选出若干视频帧，在其之上进行排列与特征比对，选出最能够代表这一镜头的一帧，同时保证提取出的关键帧尽可能少、关键帧之间的冗余度尽可能低。本算法中采用基于HSV 颜空间的方法来进行镜头分割，以此
确定同一视频中的不同镜头。对不同镜头中的采样帧进行层次聚类与k 均值聚类迭代，最终筛选出最能代
表该视频关键内容的帧画面。
该算法能够基本满足归结视频关键内容的需求，仅需少量的人工步骤即可实现该效果。
1视频镜头分割
通常情况下，每个分镜总是包含时、空相关的信
息，由一系列关系紧密的帧组合而成。视频镜头之间的切换大致分为两种：缓慢过渡与迅速切换。
视频镜头的迅速切换是指两个镜头在衔接处直接进行帧拼接，不发生任何过渡。缓慢过渡则是指两个镜头在衔接处，
通过电脑程序的处理，添加例如翻转、溶解等效果，将前一个镜头的最后若干帧与下一镜头的前若干帧进行结
合，使视频镜头间具有连贯过渡的效果。
在同一视频镜头变换后，视频中的内容会发生变
双金属螺杆
电脑与信息技术2021年2月
化，有的变化较大，例如视频背景、内容等均发生变化。有的则变化较小，视频所要表达信息为上一镜头的扩
展与补充。
对于镜头的分割，本文采用基于直方图特征的边
界检测方法。该方法由以下几个步骤组成：获取视频各帧颜直方图，计算得到帧间相似度，
从而确定渐变或突变镜头的界线。
1.1基于颜直方图的视频帧比较方法
监控摄像机主板
视频是由静止的一帧帧画面所构成，因此比较视频帧实际上是对图像文件的对比，因而需要提取图像的某些特征进行量化后对比。而其中最常用的是图像的颜特征。我们可以由现有数学方法与软件，
从常见的（RGB ）图像文件提取转化得到符合人视觉感知的（HSV)颜空间[2][3]。
针对得到的各帧HSV 颜空间，可以通过巴氏距离比较法获得各帧间的相似度。巴氏距离是衡量两种概率分布（无论连续或离散）之间相似性的数学量，采用巴氏系数来量化确定两个样本的相对接近是合理的。因此可以将巴氏距离用于本算法来计算得到各帧
间的相似程度。
如果有m 和n 两个离散概率散布在同一域Y 上，则有如下定义：
D B (m,n)=-ln(BC(m,n))其中
BC(m,n)=y ∈Y
∑m(y)n(y)
蚊帐 不锈钢 落地√巴氏系数对两个统计样本之间重叠情况的量化估
计能够用于确定两个样本的相似与否。
在本算法中，通过计算不同帧之间颜空间的巴氏系数来确定二者之
间的关系，公式如下：
巴氏系数Bhattacharyya:
i=1
∑(Σa i
·Σb i
)
√其中a 、b 代表不同的两帧图像，n 代表衡量图像
彩空间的维数，a i 表示第i 维特征的值。2.2基于直方图特征的镜头边界检测方法
2.2.1突变镜头检测当视频两个衔接镜头之间发生突变时，在两个镜
头的衔接处的几帧会进行直接变换，因此在镜头转换时衔接帧的相似度会比较小，
也就是说，交界处的帧相似度会远小于镜头内部的连续帧。
据此，我们总结得出一种突变镜头的检测手段：在获取视频中每一帧的特
征量度、计算其与前一帧的巴氏距离之上，
对比两帧的相似度，当其低于某一阈值T1时，就能够认定它们来自不同镜头，也就是说，视频内容在该处发生了突变。使用此方法能够确定较多的突变镜头边界。
2.2.2渐变镜头检测
当视频两个衔接镜头之间发生渐变时，在两个镜头的衔接处会发生缓慢的过渡，镜头间衔接帧会发生逐渐的融合变化过程。在该过程中会出现帧间相似性
波动的情况，初始阶段，帧之间的相似度十分接近，之后随着不同画面的过渡融合，
帧之间的相似度Y 也会相应减小，直至触及某一最低值M ，最后随着过渡趋于完成，帧间的相似值又会对应增大。
上述两种镜头变化趋势表现为如下图1、图2所示：
图1突变镜头（三次突变）
图2渐变镜头（一次渐变）
2视频关键帧提取
通过视频分镜边界的检测，就能够获取独立的视
频镜头，在这些镜头中的事件代表着独立的事件，
由于同一个镜头中包含许多相似度高的视频帧，为了能够使视频镜头中的信息通过较少的视频帧表现出来，通过设定阈值、均值聚类等数学方法提取来实现这一目的。2.1聚类算法
聚类是一种无监督学习方法。
对于一个样本集，将其按照某种要求划分，然后以满足要求为目的不断迭
代优化[4]。在关键帧提取技术中，
我们总是希望提取出的帧集是视频主体内容的概括，也就是其应满足在同
一镜头内视频帧间相似度高，同时镜头间视频帧相似度低。因此，该算法可以应用于关键帧提取技术中
。
·14·
第29卷第1期K 均值聚类算法是数据处理、图像或视频处理中运用最为广泛的聚类分析算法之一。
其主要过程如下：对于一个n 元元素的集合，给出一个初始划分方法构
建集合的k 个划分（也就是k 个簇），每个划分中随机选取一个元素作为其划分的中心（种子聚类中心）[5]。通过距离判断算法，将每个元素分配到与之最匹配的
类簇中，重新进行数据元素的划分。将上述步骤迭代进行，直至使得簇内各个样本之间的相似性最大。
对应描述该算法的数学表达如下：
对于输入的样本集D ，将其进行一个初始划分C ：D={x,x 2…x m }风光互补led路灯
C={C 1,C 2…C k }
对于当前的划分C ，不断迭代执行以下内容：min k
i =1∑∀
x ∈C i ∑‖x-u i ‖
2
其中：u i =1|C i |
∑x ∈Ci x
式中u i 是第i 个类簇C i 的聚类中心，‖ (2)
欧几里得距离。
在经过以上的初始操作后，K 均值聚类算法能够
选出K 个簇的最恰当的中心元素，即获得了n 元对象中k 个“最具代表性”
的元素。2.2基于K 均值聚类的关键帧提取方法
本文在基于聚类的方法的基础上改进视频中关键
帧选取方法，并结合实际关键帧提取效果调整参数。方法如下：
（1）聚类算法参数说明Fps ：视频每秒钟帧数FrameCount ：镜头内总帧数
SampleCount ：镜头内采样帧数SampleVector ：存放镜头内所有帧
SimilarityTable ：各帧相似度HsvVector ：存放镜头内各帧Hsv 组Iter ：聚类迭代次数K ：聚类的簇类总数
Gap ：SampleCount /K
（2）构造初始聚类
在视频镜头内部进行帧采样，每秒获取一帧，将所采样的视频帧序号存入SampleVector ，并计算每一采样帧的HSV 向量，将其存入HsvVector 。计算各个采样帧的相似度存入SimilarityTable 。假设镜头中采样帧的
第一帧为第一簇中心，之后每隔Gap 再将其设置为下一簇类中心
（3）分配各帧所属簇类
通过对比SimilarityTable 中每个采样帧与各个初
始采样簇类中心的相似度，将采样帧分配到与其最类
似的簇类之中。并且通过对视频帧前后相似度对比，设置阈值，当累计差距大于阈值时，
在其后重新增加一个类簇，实现自适应添加簇类。
（4）寻最匹配簇类中心
在经过上述操作后，需要评估是否到最佳簇类中心。本算法通过对比该簇类中心与簇类所有采样帧的相似度之和是否为簇内最高，否则重新分配簇类中心，直至该帧与簇内所有帧的相似度最高，
此时我们可以基本确定其满足关键帧特点，通常情况下，该算法迭代3-4次即可得到最佳簇类中心。
（5）算法流程图如图3所示：
图3算法流程图
4结果与分析
本文在Intel i5，2.4GHz CPU ，8GB 内存，Windows
10（64位）环境下VS 平台上基于Opencv 库实现该算
法，以检验该算法的有效性。本算法中所使用的单个测试视频帧长度分布在几百帧到几万帧，测试集总时长为114,440秒，测试集视频帧率保持在25-60帧，总帧
数为3,586,554帧。并且视频测试集种类较为全面，包含电影片段、广告、新闻、纪录片、
动画片段等类型，涵盖基本视频需求。
表1测试数据信息
表
视频类型时长（s ）总帧数镜头数电影片段20082636,599137广告10969326,876102新闻26365790,950114纪录片20116645,723169动画片段15027513,923253摄影混剪
21081
21081
217
张一凡等：基于K 均值聚类的视频关键帧提取技术研究
·15·
电脑与信息技术2021年2月
部分关键帧提取结果如图4、图5所示：图4纪录片片段关键帧提取结果
图5采访片段关键帧提取结果
本文引入查全率和准确率来检验视频关键帧的提
取效果。其中，查全率和查准率的定义如下所示：
查全率A=正确检测到的帧数TT/（正确检测到的帧数TT+漏检帧数TF ）
查准率P=正确检测到的帧数TT/（正确检测到的帧数TT+误检帧数FT ）
即为：A=TT
TT+TF
P=TT TT+FT
实验结果见表2。
表2实验结果表
5结束语
本文的视频关键帧提取算法，主要是根据视频画
面帧的HSV 特征信息提出相应的解决方法，
之后通过直方图特征来进行关键帧比对，最终确定视频的关键
帧。对大量数据应用本文算法，
从而分析得出：该方法对较多视频进行的关键帧提取效果较好，尽管有少量误检、漏检的情况存在。可以进一步加强视频特征信息
提取算法，降低漏检率和误检率。参考文献：
[1]李秋红.视频关键帧提取技术研究［D ］.杭州电子科技大学，
2010.
[2]
李健，姜楠，宝音巴特，等.空间颜聚类算法及其在图像特征提取中的应用[J].吉林大学学报(理学版),2020,58(03):627-
633.
[3]
Fu Q,Zhang Y,Xu L,et al.A method of shot -boundary
机顶盒支架detection based on hsv space [C].2013Ninth International Conference on Computational IntelligenceandSecurity.IEEE,2013:219-223.
[4]潘磊，吴小俊，尤媛媛.基于聚类的视频镜头分割和关键帧提取[J].红外与激光工程,2005,34（3）：341-344.[5]
黄韬，刘胜辉，谭艳娜.基于k -means 聚类算法的研究[J].计算机技术与发展,2011.21(7):
54-57.衡量标准值检测帧数
应得帧数查准率查全率数值
路径规划1340(-208)
1238
84%
91%
·16·
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议