基于决策树的多媒体视频关键帧实时提取方法研究

陈少伟，王志固

(漳州城市职业学院 文化艺术创意系，福建 漳州 363000)

0 引言

5G时代的到来快速推动了社会发展进程.多媒体短视频代替传统媒介成为一种新的传播方式[1]，其中的海量视觉信息颠覆人们固有思维.人们通过视觉方式获取信息量占比超过85%，最为生动形象的视频成为最高效的交流方式[2].在全球范围内采集及传输过程中，由于传统海量视觉信息未能获得高效处理，导致很多资源的浪费[3].为解决此类问题，多媒体技术在视频处理方面的技术获得推动式迅猛发展，视频关键帧作为该问题的核心环节，受到高度重视[4].多媒体网络技术，涉及各行各业，能够帮助用户快速精确搜索到感兴趣的内容[5]，这对多媒体视频中关键帧进行实时提取极为重要[6-7].为此，相关研究者进行了很多研究，并取得了一定成果.

仲梦洁等[8]提出一种基于视觉显著性的视频关键帧提取方法，该方法以多特征融合图像为参考，利用视觉显著性有效提取关键帧图像并压缩，并有效提取车辆关键帧信息，但该方法需测量多方面特征，时间成本极高，无法适用于普通视频的需求.张晓宇等[9]提出一种视频关键帧提取方法，该方法利用融合特征提取视频特征并分割关键帧，缺点是在关键帧分割时存在错误划分.为解决上述方法中存在的问题，本文提出基于决策树的多媒体视频关键帧实时提取方法.决策树作为预测模型，其实质上是一种监督模式机器学习方法，决策树依据选定特征属性对视频样本集进行层级分类，再判断特征分类.决策树具有效率高、易操作、可同步处理数据型以及常规型属性等多种优势，广泛应用于归类信息以及选取特征等应用场景中.将其应用到本文方法中，精准高效提取分割视频关键帧，促使用户更为快捷的浏览、检索感兴趣视频，同时能高效地掌握视频的核心内容，使检索效率进一步提升.

1 多媒体视频关键帧提取方法

1.1 基于信息增益比率的多媒体视频关键帧特征选择

多媒体视频关键帧实时提取之前，为了提升提取的精度，首先需要利用信息增益比率选择多媒体视频中的关键帧特征.

设S为多媒体视频帧样本集，用Ci,i=1,2,…,n描述多媒体视频帧样本类别标号，通过公式(1)描述：

(1)

其中：多媒体视频帧样本集S中样本总数量以及归属Ci类别样本数量分别用|S|、mum(Ci,S)表示；熵代表样本集的纯度(purity).

考量训练样本集纯度的参考指标为熵，信息增益作为衡量关键帧特征归类训练样本能力的准则，利用关键帧特征分割样本集，达到熵变小的目的[10]，拟定用S和A分别描述样本集与关键帧特征，通过公式(2)计算信息增益，表示为：

(2)

在信息增益应用熵过程中，仅衡量视频帧样本集S内各关键帧数值的熵，视频帧样本集S内关键帧特征A中每个值的熵为分裂数据，通过公式(3)得到分裂数据为：

(3)

其中：多媒体视频帧样本集S被c个数值的关键帧特征A切割，切割后获取到c个样本子集为S1-Sc.

信息增益比率利用信息熵及信息增益、分裂信息求解获取[11]，用公式(4)描述信息增益比率：

(4)

通过分支产生有效数据比率即为信息增益比率，信息增益比率数值越低，代表分支内拥有的有效数据占比越低，反之，则代表该分支内存在较多有效数据[12].

1.2 基于优化ID3决策树的视频关键帧提取

ID3决策树是一种利用信息增益比率确定关键帧特征选取准则，可将最高信息增益比率的关键帧点当作最新节点，并在此基础上进行子树繁衍.

1.2.1 ID3决策树算法

依据数据获取分类器且多方应用的逻辑方法即决策树.决策树隶属于监督学习，是一种机器学习方法.决策树的重要构成要素如图1所示，包含决策树的决策节点、分支节点和叶子节点.

图1 决策树重要构成要素

结合图1可以看出，决策树是一种树状构造.其中，各节点表示测试或选择各个属性的取值，测试或者选择结果则用分支描述；类别选用决策树的各个叶节点描述.根节点选择树的最高层节点作为决策树的起始点.

ID3决策树算法作为使用时间最久、范围最广的决策树算法，于上世纪末提出，已经取得较高成就.该算法实现流程如图2所示.

(1)确定最佳划分属性

ID3决策树内对信息熵进行初步界定，确定的最佳划分属性取决于信息熵结果.多媒体视频帧样本的纯度为信息熵含义，表示为：

(5)

其中：视频帧样本集信息熵指标用Ent(S)描述；该视频样本集内第k类样本占比用pk描述；视频帧样本总类型为y；当信息熵数值偏高则代表视频帧样本集纯度偏小，反之，则偏大.

图2 决策树算法的训练步骤

因此，最佳关键帧特征选取信息熵增益最高的帧特征需要满足以下条件，即：

(6)

其中：最佳划分关键帧特征用a*描述；视频帧样本集S依据关键帧特征a分割相应信息熵增益为Gain(S,a)；各属性取值数量用Va描述；视频帧样本子集信息熵为Ent(Sv)；视频帧样本集样本数目以及在视频帧样本集内关键帧特征a且取值v视频帧样本子集Sv分别用|Sv|和|S|描述.

(2)分支衍生

依据最佳划分属性，将选取的值进行分割操作，分支数为关键帧特征取值数值.

(3)循环判断

递归问题决策过程即决策树的演变过程.判断是否继续返回时要符合下述条件之一：①视频帧样本集为空集；②最佳关键帧特征为空集；③分割后获取视频帧样本子集为同类时则结束循环分割.

1.2.2 ID3决策树关键帧分类

以信息增益比率最高关键帧特征作为参考指标，选取决策树各个节点上属性即关键帧特征，并利用各个非叶节点完成测试，获取被测试记录有关最大类别数据.详细步骤为：①对全部关键帧特征进行检测并选取其中信息增益最高的关键帧特征当作决策树节点;②依据该关键帧特征的各个取值确定分支，之后调用该方法递归操作各个分支的多媒体视频子集，搭建决策树节点分支;③当全部多媒体视频帧子集内部只有同一个类型的信息时结束分支构建.确定关键帧数据类型及关键帧特征之间的关系，并以此获取决策树，归类最新视频帧样本[13].详细流程如下：

步骤1：对全部关键帧特征的信息增益进行求解，根节点选取其中信息增益数值最高的关键帧特征来表示.

(1)对已知的训练数据集归类信息期望I进行求解.

设含有s个信息的多媒体视频帧样本集合用S描述，其类别关键帧特征，分别选取m个值同时产生m个类别Ci,i=1,2,…,m，若Ci类内部样本数量用si描述，用公式(7)描述归类给定视频帧样本信息的信息量：

(7)

其中：随机选取一个信息数据Si归属于Ci的概率用pi描述.

(2)对关键帧特征各个取值的信息预期值E(A)进行求解.

拟定n为关键帧特征A内包含的各个取值{a1,a2,…,an}，多媒体视频帧样本集S分割是通过关键帧特征A实现，拆分为n类集合{S1,S2,…Sn}，其中，多媒体视频帧样本集关键帧特征A取值为aj，且该值存在Sj中.

假设用测试节点属性定义关键帧特征A，将其应用在分割样本集过程中，拟设多媒体视频帧样本子集Sj内归属为Ci类的样本数总和用sij描述，则信息熵的求解结果为：

(8)

用公式(9)描述多媒体视频帧样本子集Sj的信息量求解，即

(9)

其中：多媒体视频帧样本子集内随机挑选一个数据样本在Ci在类别内的概率为pij.

(3)求解关键帧特征A的信息增益InfoGain(A).

利用关键帧特征A对当前分支节点进行对应多媒体视频帧样本集划分，用公式(10)获取的信息增益为：

InfoGain(A)=
I(S1j,S2j,…,Smj)-E(A).

(10)

划分多媒体视频帧样本集InfoGain(A)获取信息熵降低数量是通过关键帧特征A取值结果实现的.当信息增益数值偏高，则表示关键帧特征A在归类过程中为其提供较多信息量，降低了取值的不确定性，保障数据的可靠性[14].求解每个关键帧特征的信息增益并将其进行比较；

步骤2：由根节点属性的各类取值继续构建决策树分支[15].

步骤3：通过递归方法选取信息增益最高的关键帧特征，作为子节点后直至全部子集内搜集完同类信息，实现多媒体视频关键帧提取.

1.2.3 多媒体视频关键帧提取流程设计

ID3决策树缺点表现在无法协调矛盾特征及模糊特征信息之间的关系，因此，本文选用优化ID3决策树分类方法.以提取的关键帧特征作为优化ID3决策树的属性值，对多媒体视频帧数据集中连续属性取值进行离散化处理，并求解每个条件属性重要性，此处采取k-means++算法完成.其中，分裂节点选取重要性最高的属性，以上为优化的ID3算法的主要思想.经过循环迭代，当全部条件属性成为分裂节点时，结束循环.剪枝处理，生成最终决策树.优化ID3算法详细流程为：

(1)初始化多媒体视频数据信息；

(2)对属性值离散与否进行判定.当属性值离散时，则进行下一步骤.当不能存在离散情况时，要确定离散化后取值数量，并对其使用k-means++算法进行离散化处理，用离散值代替原有连续值；

(3)对活跃条件属性重要程度进行求解；

(4)对多媒体视频样本集进行划分，分裂节点选取其中重要程度最高的条件属性；

(5)再次划分多媒体视频样本集，重复(3)和(4)，选取其余条件属性划分多媒体视频样本集，当全部条件属性都被当作分裂节点时，结束循环操作；

(6)剪枝，决策树完成优化.

将提取到的关键帧特征输入优化后的ID3决策树进行分类，实现多媒体视频关键帧提取.

2 实验及结果分析

2.1 实验环境

选用Matlab2021软件进行仿真实验，选取多媒体数据库中500段视频作为本次实验对象，分别从提取效果以及性能两方面进行分析验证.

2.2 实验结果分析

从数据库中选取一段篮球比赛视频片段进行投篮时的关键帧提取，部分图像关键帧提取效果如图3 所示.

分析图3可知，该方法可有效提取篮球比赛视频投篮的部分关键帧，依据该关键帧提取结果可分析该运行员投篮动作.

图3 关键帧提取效果

为全面评价本文方法提取效果，开展密集型实验，分别选出新闻、动画、综艺、电影和体育赛事5种不同特征类型的多媒体视频作为样本集，设定视频长度区间范围为5 000到6 000帧，利用本文方法提取各类型视频关键帧，验证其与人工检测实际关键帧效果，关键帧提取效果如图4 所示.

图4 关键帧提取结果

分析图4可知，本文方法检测出的各类型视频关键帧数量与人工检测的关键帧总数几乎一致，鉴于动画、体育及综艺3种视频皆属于复杂运动类型，提取关键帧总数与人工检测关键帧总数相比仅存在1项漏洞，总体效果良好.另外，视频关键帧提取受所选视频的分辨率因素影响，由于这些视频存在噪声干扰，因此，结果中存在微少的误判视为正常现象.

为验证本文方法的关键帧提取精度，将多媒体视频帧样本集等分为3部分，训练数据选取前两部分，其余一部分则作为测试集.验证ID3决策树优化前后在遭受各类攻击状态下的关键帧提取准确率，拟设ID3决策树优化前后的节点数量及叶子节点数可进行自适应调节，验证关键帧提取准确率是否受外界干扰影响，即验证本文方法的关键帧提取性能是否稳定.遭受各种攻击状态下ID3决策树优化前后的准确率对比结果如表1 所列.

分析表1可知，ID3决策树优化前在遭受各类攻击状态时其准确率维持在82.5%到88.6%区间范围内，整体偏低，性能略差；ID3决策树优化后的节点数及叶子节点数均为最少，同时准确率最高，全程保持在96.9%到98.8%，各种攻击状态下性能表现极佳，实验证明该方法能够准确提取海量多媒体视频关键帧.

选用DR、ACC作为衡量本文方法关键帧提取性能的两个指标，继续开展实验.DR代表多媒体视频关键帧提取率；ACC代表决策树能够准确识别出假阴性及真阳性的占比，结果如图5所示，横坐标为多媒体视频帧数量，图中曲线表示随着视频帧数量的变化，DR、ACC两者之间关系变化浮动大小.

分析图5可知，随着视频帧数量的增加，DR及ACC两项指标始终保持平稳状态，不会过多受视频帧数量干扰，证明本文方法的多媒体视频关键帧提取性能整体优秀.

表1 遭受各种攻击状态下2种方法的准确率

图5 视频帧数量对关键帧提取性能的影响

3 结语

当前，传统视频帧提取方法中由于视频内含有较多的冗余信息，难以提升关键帧的提取效果.本文提出基于决策树的多媒体视频关键帧实时提取方法.对视频样本集进行视频帧的关键帧特征提取，将获取的关键帧特征输入优化后的ID3决策树，完成视频关键帧提取.实验结果证明，该方法能够高效分类提取海量多媒体视频关键帧，在不同视频帧数量下提取性能较好.