本站原创摘 要：本文提出二次聚类的方法,第一次以镜头内相邻两帧的相似度为数据样本进行聚类（分成两类）,计算确定第二次聚类所需的阈值；第2次采用动态聚类的ISODA TA算法,以视频序列的帧为数据样本进行聚类,最终获得聚类结果.实验结果表明了此算法在镜头分割和关键帧提取方面的有效性.
关 键 词 ：关键帧；聚类；自适应阈值
中图分类号：TP242 文献标识码：A 文章编号：1674-7712 （2013） 24-0000-02
一、概述
本文主要研究在基于机器视觉的智能导盲系统中镜头捕获和关键帧的提取的部分.目前国内外有很多的关键帧提取技术.文献[1]计算当前帧与已存在的每个聚类中心之间的距离,同预先指定的阈值相比较,若当前帧有所有聚类中心间的距离均大于该阈值,则从该帧开始形成一个新类别,否则将其分配到离它最近的类中.显然,关键帧数有类别数确定,而类别数有取决于制定的阈值.比较文献[1]中的方法,本文在实现中采用基于自适应阈值自动提取关键帧的聚类算法来进行镜头分割和关键帧提取.
二、镜头分割与关键帧提取算法
本文采用HSV颜色累积直方图和MPEG-7中推荐的边缘直方图描述符作为视觉特征.将H、S、V分别分为8、4、1个级别,得到一个32维的颜色特征向量,记为fc.再对每帧提取边缘直方图,得到一个80维的纹理特征向量,记为ft.为了消除各特征向量取值范围差异性的影响,对其进行高斯归一化.Fic.k表示第i帧的第k个颜色分量,Fit.k k表示第i帧的第k个纹理分量,则计算两帧间相似度的公式为
Sim（Fi,Fj）等于w1 （1）.其中,w1和w2分别为颜色特征和纹理特征的权值,在此处取值0.5.
自适应计算阈值的算法,即第1次聚类：（1）设一个镜头中有N帧{F1,F2,F3,等,Fn},连续读入,利用式（1）求相邻两帧的相似度,得到数组Dif等于{D1,D2,等,DN-1}；（2）以Dif中的元素作为一维数据空间的样本,进行聚类,分为两类.为提高算法效率,先对Dif的元素由大到小排序,假设排序后有：D1≥D2≥等≥DN-1,令T等于argmin2w （2）.其中,argmin2w等于qH2H+qL2L,qH等于T,qL等于N-T-1,H等于i,H等于i,2H等于2,2L等于2,则DT就是所求阈值.
在得到初始的类别数和初始类的划分后,采用ISODATA算法对镜头中的所有帧再进行动态聚类,即第2次聚类,采用自适应确定阈值的方法设置7个参数.K：期望得到的最大聚类数,取值为（每秒视频包含25帧）；
：一类中的最少样本数,取值为12（约0.5s）；
：标准偏差参数,取DT所对应那两帧（和）各特征分量之差的绝对值,即等于{||,||,等.；||}；：合并参数,根据（2）求取预知的算法来求出DT；L：每次迭代允许合并的最大聚类对数,取值；I：允许迭代的次数,本文中取值为5（测试取值可任意）.
参数K,L和I的值与视频内容无关,对所有镜头可以指定相同的值,与频内容有关的阈值和是通过计算得到的.设初始聚类数为C,初始聚类为{Γi},各类中心为,i等于1,2,等,c.设类中心为的类Γj分裂成两个类中心分别为mj+和mj-的聚类,应把原来的取消,且令c增1.为了避免手工设定阈值的随意性,考虑到新的两类的类中心之间应尽可能相距得远些,首先求类Γj中相距最远的两帧,记为和,然后采用下式计算两个类中心：mj+等于（mj+Fi）/2,mj-等于（mj+Fk）/2,
计算类Γj中每帧与两个新类中心的距离,将其归入较近的类中.在得到最终聚类后,从每一类中提取离类中心最近的帧作为关键帧.实验证明了该方法行之有效.
三、算法效率及结果分析
设N为视频序列中的帧数,d是视频特征的维数,C为类别数,T为迭代次数.本算法中第1次聚类的时间复杂度是O（Nd）；第2次聚类的时间复杂度为O（NdCT）；从理论上分析,本文提出的计算mj+和mj-的算法在最坏情况下时间复杂度为O（N2d）,但实际上执行分裂步骤的概率很小,而且需要分裂的类中所包含的帧数比整个镜头中所含帧数少得多,故总的时间复杂度为O（NdCT+N2d）.对文献[2]和文献[3]中算法的时间复杂度进行分析.参考文献[1]中,一次K均值聚类的时间复杂度为O（NdCT）.共执行了+10次,总的时间复杂度为O（N2dCT）.
在Windows7环境下,用VC++编程实现本算法.对于不同特点的视频序列在这里做了大量的测试,现以2个镜头为例分析.
图1（带前景的目标运动）显示的是一组视频序列最终提取的关键帧,该帧背景静止,移动目标在做中速运动,整个过程耗时1分钟,共304帧.由于目标中速前进,因而相邻两帧之间的差别不大,使类分散度的最小阈值在Dif中的排序趋于中间,相应的初始聚类数也会较多.
图2是一组没有前景的动作的缓慢镜头,它的分割阈值为T等于0.81,可以过得看出图2的镜头相对较长,但却只表明了目标缓慢转动的这么一个动作,因此抽取图2中的两幅,即（a）帧图片与（d）帧图片作为该镜头的关键帧足以.所以,该算法提取出的关键帧能够有效的刻画镜头的主要内容.
四、结束语
用于机器视觉的智能导盲系统的镜头分割和关键帧提取则采用的是自适应阈值的聚类算法.第2次聚类所需要的阈值是在第一次聚类的基础上获得的,避免了人为指定聚类数对实验结果的影响.从大量的实验结果来看,该算法取得了较理想的效果.