计算机研究与发展ISSN 100021239/CN 1121777/TPJournal of Computer Research and Development 42(10):1752～1757,2005　收稿日期:2005-06-14　基金项目:北京交通大学科技基金项目(2004sm013)基于自适应阈值的自动提取关键帧的聚类算法王方石　须　德　吴伟鑫(北京交通大学计算机与信息学院　北京　100044)(wfs @computer 1njtu 1edu 1cn )A Cluster Algorithm of Automatic K ey Frame ExtractionB ased on Adaptive ThresholdWang Fangshi ,Xu De ,and Wu Weixin(School of Com puter &Inf orm ation Technology ,Beijing Jiaotong U niversity ,Beijing 100044)Abstract It is a common method to extract key frames using the unsupervised cluster algorithm 1But the algorithm is sensitive to the initial number of the classes and the initial classification 1It is problematic to predefine the absolute number of key frames without knowing the video content 1An approach for two times clustering is presented 1In the first time ,the similarity distances of the consecutive frames in a shot are clustered into two classes so that the thresholds needed in the second time clustering process can be deter 2mined adaptively 1In the second time clustering ,all the frames in the shot are clustered using dynamic clus 2ter ISODA TA algorithm 1Then the frame nearest to the center of its class is automatically extracted as one key frame in the shot 1It is simple and effective with no need to predefine any threshold 1Experimental re 2sults of many videos with different traits demonstrate the good performance of the proposed algorithm 1K ey w ords key frame ;unsupervised cluster ;ISODA TA algorithm ;adaptive threshold摘　要　利用无监督聚类算法来提取关键帧是一种常用的方法,但该算法对类别数和初始类划分较敏感,在对视频内容一无所知的情况下,要求预先指定聚类数目是一个很困难的问题1提出一种二次聚类的方法;第1次以镜头内相邻两帧的相似度为数据样本进行聚类(分成两类),计算确定第2次聚类所需的阈值;第2次采用动态聚类的ISODA TA 算法,以视频序列的帧为数据样本进行聚类,得到最终聚类结果1最后在每类中自动提取距其类中心最近的帧为关键帧1该算法简单且行之有效,无需预定义任何阈值(如聚类数目)1对大量不同特点的视频进行了实验,该算法均取得了较好的实验结果1关键词　关键帧;无监督聚类;ISODA TA 算法;自适应阈值中图法分类号　TP3911　引 言为了有效地访问视频内容,首先需要将视频分解为一系列镜头,然后从每个镜头中提取最具代表性的、反映该镜头主要内容的若干帧,称之为关键帧1使用关键帧可简洁地表达镜头,为视频索引、浏览和检索提供合适的摘要,大大减少了视频操作的数据处理量1关键帧的提取主要涉及两个问题:①关键帧要具有代表性,能反映镜头内容;②关键帧的数量应根据镜头内容的变化程度而确定,内容变化大的镜头提取关键帧的数量要多1目前,已有多种关键帧提取技术1文献[1]计算当前帧与已存在的每个聚类中心之间的距离,同预先指定的阈值相比较,若当前帧与所有聚类中心间的距离均大于该阈值,则从该帧开始形成一个新类别,否则将其分配到离它最近的类中1取各类中离类中心距离最小的帧为关键帧1显然,关键帧数由类别数确定,而类别数又取决于指定的阈值1文献[2]提出结合关键帧和目标分割的算法,以Kullback Leibler(K L)距离作为度量,假设镜头中有N帧,先用文献[1]的聚类方法提取M(<N)个候选关键帧,用其为场景中的目标建立GMM模型,从所有候选关键帧中分割出目标,然后用SFFS(sequential forward floating selection)方法提取关键帧1由于该算法首先采用文献[1]的聚类方法提取候选关键帧,所以它也是依赖于阈值的1纵观上述算法,均需预先指定一些经验阈值,这些阈值对某些实验数据有效,对有些无效1尤其是在对视频内容一无所知的情况下,要求预先指定决定聚类数的经验阈值是一个很困难的问题1众所周知,无监督聚类算法对类别数和初始类划分较敏感,初值设置不当对实验结果影响很大1而视频中镜头长短不一,内容千差万别,不可能用统一的阈值对所有的实验数据均取得较好的效果1文献[3]提出自动确定类别数的方法,但却要指定两个阈值,最大关键帧数M和控制能否成为候选关键帧的参数r,该算法的最大难点就是选取r值1文献[4]采用聚类有效性分析,首先指定一个比实际类数大得多的类别最大数,取值为C=10+NΠ25,其中N为视频序列中帧的总数1然后将所有镜头的帧放在一起,进行C次标准的k均值聚类,每次聚类的类别数依次取[1,C]中的整数,计算其类分散度,使类分散度最小的类数即为最佳类别数1最后找离类中心最近的帧作为每类的关键帧1文中只给出了确定最佳类数的方法,并未说明如何划分初始类,而初始类的划分常常会影响最终结果1文献[5]在计算当前帧与其前一帧颜色直方图间相似度f col的同时,还要计算当前帧与其前K(文中取值20)帧颜色直方图均值之间的相似度f d,然后采用Otsu技术确定一个阈值T1若f col>T,则当前帧为关键帧,否则,若f d>T,则当前帧也为关键帧1另外还采用层次块匹配算法得到每帧的运动能量,取运动能量极小值处的帧为关键帧1只有两种方法都提出的帧才是真正的关键帧1其中K是人为给定的参数,且对实验结果有很大影响;层次块匹配算法本身也需设定一个参数———搜索范围,若像机进行快速变焦或摇移,而搜索范围过小,块匹配的结果就很不准确,若搜索范围过大,又会影响算法的时间效率12　提取关键帧的算法本文提出二次聚类的方法,可在已分割好的镜头中,根据其内容的变化程度,自适应地确定聚类所需的阈值,如关键帧的个数等,无需预定义任何阈值1然后采用动态的无监督聚类算法自动提取关键帧1该算法分4步:①读取镜头中的所有帧,提取各帧的特征向量并存入视频数据库;②进行第1次聚类,以相邻两帧间的相似度为样本,在一维数据空间中聚类,得到第2次聚类所需要的阈值;③第2次聚类采用ISODA TA算法,对镜头中的所有帧进行动态聚类;④在每类中提取离类中心最近的帧为关键帧1211　特征提取本算法采用HSV颜色累积直方图和MPEG27中推荐的边缘直方图描述符作为视觉特征1将H, S,V分别分为8,4,1个级别,得到一个32维的颜色特征向量,记为f c1再对每帧提取边缘直方图,得到一个80维的纹理特征向量,记为f t1为了消除各特征向量取值范围差异性的影响,对其进行高斯归一化1f c i,k表示第i帧的第k个颜色分量,f t i,k表示第i帧的第k个纹理分量,则计算两帧间相似度的公式为si m(F i,F j)=w1∑31k=0(f c i,k-f c j,k)2　+　w2∑79k=0(f t i,k-f t j,k)2　,(1)其中,w1和w2分别为颜色特征和纹理特征的权值,在本文中均取值0151为简化起见,下文中不分特征类型,用f i,k表示第i帧的第k个特征分量1 212　自适应确定聚类阈值并划分初始类所有基于帧差来判断两帧是否相似的方法都要指定一个阈值,本文提出一种自适应计算阈值的算法,即第1次聚类,其过程如下:(1)设一个镜头中有N帧{F1,F2,F3,…,F N},连续读入,利用式(1)求相邻两帧的相似度,得到数组Dif={D1,D2,…,D N-1};(2)以Dif中的元素作为一维数据空间的样3571王方石等:基于自适应阈值的自动提取关键帧的聚类算法本,进行聚类,分为两类1为提高算法效率,先对Dif 中的元素由大到小排序,假设排序后有:D1≥D2≥…≥D N-1,令T为T=arg minδ2W,(2)其中,δ2W=q Hδ2H+q Lδ2L,q H=T,q L=N-T-1,μH =1q H∑Ti=1D i,μL=1q L∑N-1i=T+1D i,δ2H =1q H∑Ti=1[D i-μH]2,δ2L=1q L∑N-1i=T+1[D i-μL]2,则D T就是所求阈值1(3)若相邻两帧帧差≥D T,则开始新的类;否则,若当前帧与当前类中心的距离≥D T,则开始新的类;(4)算法停止,得到初始类别数和初始类的划分1应用此算法对大量镜头进行了测试,限于篇幅,只给出视频序列Forest的曲线1如图1所示,曲线的横坐标是Dif中由大到小排序的元素D i所对应的第1帧的序号,纵坐标是以D i为分界点分成两类后计算所得的δ2W值1图中曲线最低点所对应的横坐标为60,这表示将Dif中已排序的元素在第60,其类内分散度最小,则D60即为所求阈值,比D60大的值有59个,因此初始划分的类数至少为60个1Fig11　Theδ2W curve of Forest sequence1图1　Forest序列的δ2W值曲线213　动态聚类并提取关键帧当镜头先对准A场景拍摄,接着对相机进行扫视(pan)、倾斜(tilt)、跟踪(track)或升降(boom)等操作,又对准B场景拍摄,然后转动镜头,再对A场景拍摄,假设A场景内容变化甚微,设为A′,则在提取关键帧时,文献[5]的方法会提出3个关键帧A,B,A′,而A和A′很相似,只用一个关键帧代表即可1文献[4]和本文所提算法采用动态聚类方法可解决此问题1在得到初始的类别数和初始类的划分后,本文采用ISODA TA算法[6]对镜头中的所有帧再进行动态聚类,即第2次聚类1该算法不仅能通过调整样本所属类别完成聚类分析,而且还能自动地进行类的合并和分裂,从而得到类数较为合理的各个聚类1ISODA TA算法需设置7个参数,以前的做法都是根据实验数据的先验知识,人为设定各参数值,显然不同数据对象的参数是不同的1本文采用自适应确定阈值的方法1K:期望得到的最大聚类数,取值为NΠ25,因为每秒视频包含25帧,1秒钟内最多提取一个关键帧,无需从太短的序列里提取关键帧;θN:一类中的最少样本数,取值为12(约015s);θS:标准偏差参数,取D T所对应那两帧(F i和F i+1)各特征分量之差的绝对值,即θS={|f i,0-f i+1,0|,|f i,1-f i+1,1|,…;　|f i,d-1-f i+1,d-1|};θC:合并参数,取第212节第2步求得的D T;L:每次迭代允许合并的最大聚类对数,取值1;I:允许迭代的次数,本文中取值为41参数K,θN,L和I的值与视频内容无关,对所有镜头可以指定相同的值,与视频内容有关的阈值θS和θC是通过计算得到的1设由第212节得到的初始聚类数为c,初始的聚类为{Γi},各类中心为m i,i=1,2,…,c1该算法的主要思想为若某类的类内离散度大于各类离散度的均值 δ,且该类的最大标准偏差分量σj,max>θS,max(其中max表示最大标准偏差分量的序号),则将该类分裂成两个类1若某两类类中心之间的距离小于θc,则将这两类合并成一类1假设需要将类中心为m j的类Γj分裂成两个类中心分别为m+j和m-j的聚类,应把原来的m j取消,且令c增11原算法中m+j和m-j的计算如下:人为给定一个p(0<p≤1)值,令γj=pσj或γj=p [0,…,σj max,…,0]T(σj是该类的标准偏差向量),则m+j=m j+γj,m-j=m j-γj1可见p的取值至关重要,对不同的数据也不统一1本文给出一种新的计算m+j和m-j的方法,避免了手工设定阈值的随意性1考虑到新的两类的类中心之间应尽可能相距得远些,才能将样本分开,因此,首先求类Γj中相距最远的两帧,记为F i和F k,然后采用下式计算两个类中心:m+j=(m j+F i)Π2,m-j=(m j+F k)Π21(3)4571计算机研究与发展　2005,42(10) 计算类Γj 中每帧与两个新类中心的距离,将其归入较近的类中去1实验证明了该方法行之有效1在得到最终聚类后,从每一类中提取离类中心最近的帧作为关键帧1214　算法效率分析设N 为视频序列中的帧数,d 是视频特征的维数,C 为类别数,T 为迭代次数1本文算法中第1次聚类的时间复杂度是O (N d );第2次聚类的时间复杂度为O (N dC T );从理论上分析,本文提出的计算m +j 和m -j 的算法在最坏情况下时间复杂度为O (N 2d ),但实际上执行分裂步骤的概率很小,而且需要分裂的类中所包含的帧数比整个镜头中所含帧数少得多,故总的时间复杂度为O (N dC T +N 2d )1我们对文献[4]和文献[5]中算法的时间复杂度进行分析1文献[4]中,一次K 均值聚类的时间复杂度为O (N dC T ),共执行了N Π25+10次,总的时间复杂度为O (N 2dC T )1N dC T +N 2d N 2dC T=1N+1C T•1C T(因为N µC T )1 可见,与文献[4]中算法相比较,视频时间越长,本算法在时间效率上的优势越明显1文献[5]中采用颜色特征提取关键帧算法的时间复杂度为O (N d ),采用运动信息提取关键帧的时间复杂度为O (W HN S ),其中W,H 分别为图像的宽和高,S 为对每个像素点进行层次块匹配时搜索的范围,故总的时间复杂度为O (N d +W HN S )1以视频序列Hall monitor 为例,每帧大小为352×240,若层次块匹配算法中每点匹配次数S 不超过20次,特征向量的维数d 约120,迭代次数T 和类数C 一般不会超过10,可见本文算法并不比文献[5]效率低1文献[5]对Hall monitor 提取了4个关键帧,如图2所示:Fig 12　The key frames extracted in reference[5]1图2　文献[5]提取的关键帧3　实验结果及分析在AMD Athlon 2500+,256MB 内存,Windows XP 环境下,用VC ++编程实现了本算法1对不同特点的视频序列做了大量的测试,限于篇幅,仅以3个各具特点的镜头为例进行分析1图3显示对Hall monitor 视频序列最终提取的关键帧,该序列背景静止,前景目标做中速运动,共303帧,整个提取过程耗时1秒钟1初始类别为61个,因数量过多,图3中就不显示了1其原因是画面中背景所占比例较大,前景目标中速运动,相邻两帧差别不大,使类分散度最小的阈值在Dif 中的排序位置趋于中间,故初始类数过多1由于大多数类别中的帧数少于12帧,动态聚类中合并了这样的类,最终得到6类,所提取的关键帧数比文献[5]多了两帧,其结果符合人的主观判断,效果比较理想1Fig 13　The key frames of Hall monitor after dynamic clus 2tering 1图3　Hall monitor 视频序列动态聚类后的关键帧 图4显示对镜头Ball 提取的关键帧,该序列有摄像机的运动,也有前景目标的快速运动,共201帧,整个提取过程耗时1s 1图4(a )是从初始类中提取的所有关键帧,4(b )是动态聚类后提取的关键帧1可见,动态聚类后,将以0019和0030为关键帧的两类合并为一类,选0002为新的关键帧;将以0139和0151为关键帧的两类合并为一类,选0150为新的关键帧;将以0165,0174和0176为关键帧的3类合并为一类,以0172为新的关键帧;还将以0096为关键帧的类分裂为两类,分别以0067和0110为新的关键帧1本算法以离类中心最近的帧作为关键帧,所以初始类中的关键帧与动态聚类后提取的关键帧不同1从画面看,这样的处理符合人的视觉认知1图5显示对镜头Forest 提取的关键帧,该序列没有前景,只有摄相机的扫视、倾斜、缩小镜头(zoom out )操作,共301帧,整个提取过程耗时2秒钟1图5(a )是初始类中的部分关键帧,从图1可知初始类别至少是60个,在此只显示前5个和中间5个关键帧1注意到前5帧彼此间隔不超过12帧,且画面相似,却都被当成关键帧了,这是因为相机在扫视的过程中,强烈的阳光时而被茂密的树叶遮档,使画面变暗,时而透过树叶的缝隙直射镜头,使画面变5571王方石等:基于自适应阈值的自动提取关键帧的聚类算法亮,因此即使画面极相似,也会因明暗不同使帧间特征差很大1从图5(b )可以看出,经过动态聚类后,使分类变得较合理,这是因为算法将样本数少于12的类拆散,其元素被分配到离其最近的类中去1Fig 14　The key frames of Ball sequence 1(a )The key frames after initial clustering and (b )The key frames after dynamic clustering 1图4　Ball 视频序列的关键帧1(a )初始聚类后的关键帧;(b )动态聚类后的关键帧Fig 15　The key frames of Forest sequence 1(a )The par 2tial key frames after initial clustering and (b )The key frames after dynamic clustering 1图5　Forest 视频序列的关键帧1(a )初始聚类后的部分关键帧;(b )动态聚类后的关键帧4　结束语本文提出了一种二次聚类的方法,第1次是以相邻两帧间的相似度为样本,在一维数据空间中进行聚类,目的是要自适应地确定第2次聚类所需的阈值,避免人为指定聚类数对实验结果的影响1第2次采用动态聚类的ISODA TA 算法,以视频序列的帧为样本,在112维的数据空间中进行聚类,然后在每类中自动提取离其类中心最近的帧为关键帧1该算法可根据镜头中视频内容的变化程度,自动确定关键帧的个数,无需预定义任何阈值1从大量的实验结果来看,该算法取得了较理想的效果1参考文献1Y 1Zhuang ,Y 1Rui ,T 1S 1Huang ,et al 1Adaptive key 2frame extraction using unsupervised clustering 1IEEE Int ’l Conf 1Image Processing ,Chicago ,IL ,19982Xiaomu Song ,Guoliang Fan 1Joint key 2frame extraction and ob 2ject 2based video segmentation 1IEEE Computer Society Workshop on Motion and Video Computing (WACV ΠMO TION 2005),Breckenridge ,Colorado ,USA ,20053X 1Sun ,M 1S 1K ankanhalli ,Y 1Zhu ,et al 1Content 2based rep 2resentative frame extraction for digital video 1IEEE Multimedia Computing and Systems ,Austin ,Texas ,19984A 1Hanjalic ,H 1J 1Zhang 1An integrated scheme for automated video abstraction based on unsupervised cluster 2validity analysis 1IEEE Trans 1Circuits System Video Technol 1,1999,9(8):1280～12895G ao Qi ,C 1C ko ,Liyanage C de silva 1A universal scheme for content 2based video representation and indexing 1IEEE Asia 2Pacif 2ic Conference on Circuits and Systems (APCCAS 2000),Tianjin ,20006Bian Zhaoqi ,Zhang Xuegong 1Pattern Recognition 1Beijing :Ts 2inghua University Press,20001237～239(边肇祺,张学工1模式识别(第二版)1北京:清华大学出版社,20001237～239)W ang F angshi ,born in 19691Associate pro 2fessor 1Her research interests are content 2based video retrieval and pattern recognition 1王方石,1969年生,副教授,主要研究方向为基于内容的视频检索、模式识别1X u De ,born in 19441Professor and Ph 1D 1supervisor 1His main research interests are multimedia and content 2based videore 2trieval 1须　德,1944年生,教授,博士生导师,主要研究方向为多媒体、基于内容的视频检索16571计算机研究与发展　2005,42(10)Wu Weixin ,born in 19821Master candi 2date 1His main research interests include multimedia database 1吴伟鑫,1982年生,硕士研究生,主要研究方向为多媒体数据库1R esearch B ackgroundK ey frames are most suitable for content 2based video browsing ,where they can be used to guide a user to locate s pecific video segments of interest 1Furthermore ,key frames are also effective in representing visual content of a video sequence for retrieval purpos 2es :video indexes may be constructed based on visual features of key frames ,and queries may be directed at key frames using image re 2trieval techniques 1S o it is a basic and important work to extract a suitable number of key frames of a video sequence 1The number of key frames should vary along with the complexity of different videos 1The unsupervised clustering is a common method to extract key frames 1But it is hard to predefine the initial number of the classes frames without knowin g the video content 1In this paper ,we pre 2sent a method of two times clustering for automatically producing an adaptive number of key frames of an arbitrary video sequence 1In the first time ,the similarity distances of the consecutive frames in a shot are clustered into two classes so that the thresholds needed in the second time clustering process can be determined adaptively 1In the second time clustering ,all the frames in the shot are clustered using dynamic cluster ISODA TA algorithm 1Then the frame nearest to the center of its class is automatically extracted as one key frame in the shot 1This method is designed to work without any human supervision 1It is simple and effective with no need to prede 2fine any threshold 1欢迎订阅《计算机研究与发展》《计算机研究与发展》创刊于1958年,是我国第一个计算机刊物1现已成为我国计算机领域最有影响的学术期刊之一1多年来,本刊一直被评为我国计算技术类核心期刊;国务院学位办指定的评估学位与研究生教育的“中文重要期刊”;并成为美国《工程索引》(EI )、日本《科学技术文献速报》、俄罗斯《文摘杂志》、中国科技论文统计源期刊数据库、中国科学引文数据库等国内外重要机构的检索源期刊1《计算机研究与发展》多次荣获国家及省部级科技期刊奖及“百种中国学术期刊”奖1影响因子已达到01843;总被引频次为11631目前,本刊以漂亮的封面设计、特色鲜明的高质量内涵、活泼多样的栏目吸引着广大作者和读者1欢迎投稿,欢迎订阅1邮发代号:22654订价:48100元Π期,全年576元Π12期.到编辑部购买可享受八折优惠,即38.40元Π期,全年460元Π12期(含邮费)1通信地址:北京2704信箱《计算机研究与发展》编辑部邮政编码:100080电 话:(010)62620696;(010)6256553328609;联系人:王玉荣开户名称:中国科学院计算技术研究所开户银行:工行北京市分行海淀镇支行帐 号:020000450908812312357571王方石等:基于自适应阈值的自动提取关键帧的聚类算法。