采用非线性块稀疏字典选择的视频总结

马明阳,梅少辉,万帅

(西北工业大学电子信息学院,710129,西安)

随着互联网、多媒体和智能终端的快速发展,视频的获取和传输变得前所未有的便捷,视频数据呈现爆炸式增长。海量视频数据在给人们带来丰富信息的同时,也对视频管理带来了巨大的挑战,比如检索、浏览和存储等。因此,快速有效地访问视频的主要内容和重要信息已经成为与日俱增的需求。视频总结是目前解决此需求的一种有效途径,它是通过对整个视频结构和内容进行分析来完成,既涵盖了视频的最主要的信息,也极大地减少了数据量[1-2]。

早期的视频总结研究主要有基于聚类的方法和基于镜头边界检测的方法。基于聚类的方法首先采用聚类技术将内容相似的视频帧聚为一类,然后将聚类中心或离聚类中心最近的帧选为关键帧[3-5]。基于镜头边界检测的方法首先对视频进行镜头边界检测,在把视频分割为镜头之后,取镜头中的首帧或末帧作为视频的关键帧。此类算法的最关键步骤是镜头边界检测技术,基本思想是识别视觉内容的不连续性[6-8]。但是这两类方法将视频总结描述为根据距离或者相似度进行数据分类的问题,使得视频的场景语义信息提取仅仅依赖于有限的特征表示[9]。

近年来,稀疏表示理论在模式识别以及计算机视觉领域取得了显著的成果,研究人员也逐渐将稀疏表示理论应用于视频总结,例如:Kumar等提出了一种基于稀疏表示的方法来提取关键帧,使用随机投影矩阵将视频帧投影到一个低维的随机特征空间,并且在随机特征空间中利用稀疏表示来分析视频数据并生成关键帧[10];Cong等将视频总结表述为稀疏字典选择问题,并采用宽松约束条件L2,1范数以确保稀疏性,使用Nesterov最优梯度算法来提取关键帧[11];Mei等将视频总结问题表述为一个最小化稀疏重建问题,使用L0范数对稀疏度约束,采用贪婪算法使关键帧直接被选择为稀疏字典[12];Cong等针对网络视频总结提出了一种自适应的稀疏字典选择模型,该算法包含用于选择关键帧的前向步骤和用于移除已经选择的较差的关键帧的后向步骤[13]。

然而,以上算法都是基于线性稀疏表示,即假设视频帧之间是线性关系。这一假设并不总是准确,因为在对视频帧进行特征表示时,特征通常存在内在的非线性属性。另外,由于视频中的关键帧成块出现,这些算法都只考虑了关键帧的稀疏特性,未充分考虑块稀疏特性。Ma等对视频中的非线性进行了探究,提出了非线性的稀疏表示的视频总结方法[14]。本文在文献[14]的基础上首先建立非线性稀疏字典选择模型,然后利用块稀疏特性进一步扩展建立非线性块稀疏字典选择模型。针对模型的优化,设计了一种核化的联合块正交匹配追踪(kernelized simultaneous block-orthogonal matching pursuit,KSBOMP)算法。基准视频数据集上的实验结果验证了KSBOMP算法能明显提高视频总结的客观评价结果。

1 非线性块稀疏字典选择模型

假设一个视频有n帧,第i帧可以通过特征提取技术表示为在实数集R上的d维的特征向量fi,fi∈Rd,1≤i≤n,该视频可以表示为F,F=[f1,f2,…,fn]∈Rd×n。视频总结的目标是从原始视频中提取一个包含k个关键帧的子集Fkey,Fkey=[fi1,fi2,…,fik]∈Rd×k,其中i1,i2,…,ik∈{1,2,…,n}为k个关键帧的帧序号,要求此关键帧集合包含视频的主要内容,同时关键帧的数量越少越好。

1.1 非线性稀疏字典选择

基于稀疏表示的视频总结方法首先建立一个假设,即视频中的每一帧都可以表示为关键帧集合的线性组合。由于关键帧是视频的子集,所以此假设可以用公式表述为

fi=Fxi, i=1,2,…,n

(1)

式中:xi是稀疏表示系数,xi∈Rn,xi最多有k个非零值,每个非零值对应一个关键帧。

然而,在对视频帧进行特征表示时,特征通常拥有内在的非线性属性,所以假设视频帧之间是线性关系并不总是准确的,会降低视频总结的性能。将原始特征通过核函数映射到高维特征空间,再进行稀疏表示,这样在原始空间中不能线性可分的样本在高维空间变得线性可分,而在原始空间中线性可分的样本在高维空间中能够更加准确地线性可分[15]。

假设存在一个映射ψ(·)可将原始样本映射到高维空间,即fi∈Rd→ψ(fi)∈RD,其中D≫d,可能是无穷大。那么,原始视频通过映射后在高维特征空间下就可以表示为Φ=ψ(F)=[ψ(f1),…,ψ(fn)]=[φ1,…,φn]∈RD×n。在高维空间下,式(1)中的假设可以用公式表述为

(2)

通过式(2)中的假设,视频总结问题可以被表述为一个非线性稀疏字典选择问题,其公式为

(3)

1.2 非线性块稀疏字典选择

目前,基于稀疏表示的方法基本只考虑关键帧的稀疏特性,而没有考虑块稀疏特性。块稀疏是指视频的关键帧或非关键帧是成块出现的,这是由小邻域内视频帧的内容相似性所决定的,即如果某一帧可以被看作关键帧,那么其短时邻域的任一帧都可以作为关键帧。基于块稀疏特性,视频可以被表示为帧块的结构形式,公式为

(4)

相应地,式(2)中的假设以块结构的形式可以表示为

(5)

将式(5)写成联合表示的形式,可以得到

(6)

(7)

(8)

通常,在视频总结时,关键帧重建的信息与原始视频的信息允许有一定的误差,而式(6)中的表示是理想情况,因此只需要最小化表示误差,同时保持关键帧块的数量在要求的最大数量之内即可。所以,基于非线性块稀疏字典选择的视频总结模型可以用公式表述为

(9)

10号矿体：该矿体是该区最大的矿体，呈扁豆体产出，在2线南—12线分布，总长为2 600 m，在4～8线出现，寒武系下面的岩层覆盖了4线的南部大多数矿体，黄土覆盖了8线的北部。该矿体厚度为5～302 m，平均为154.7 m，走向呈北北东方向，倾向南东，倾角为70°～80°。

2 优化算法

2.1 核函数

Ψ(·)实现了原始样本空间到高维空间的非线性映射,核空间中的两点Ψ(x)和Ψ(y)之间的内积定义为〈Ψ(x),Ψ(y)〉=kf(x,y),其中kf(x,y)称为该核空间所对应的核函数。虽然kf(x,y)定义为内积的形式,但通常不直接在高维空间计算两个映射样本的内积,高维空间中的两个映射样本的内积可以通过低维空间样本的核函数来计算,这就避免了将数据映射到高维特征时的计算花销。

常见的核函数包括线性核、多项式核以及高斯核,其中应用最为广泛的是高斯核函数,若用σ表示高斯核函数的的带宽参数,则其表达式为

(10)

本文实验选用高斯核函数,带宽参数σ需要人工设定,用于控制高维核空间中样本对内积的具体取值,σ设为0.24。通过核函数可以得到核矩阵K,K∈Rn×n,其中Ki,j=kf(fi,fj)。为了利用块特性,将K写成块形式,即

(11)

2.2 核化的联合块正交匹配追踪算法

在OMP算法的每次迭代中,字典中与重建误差相关性最大的原子被选中。类似地,在KSBOMP算法中,与所有帧的重建误差同时产生最大相关性的帧块被选择为关键帧块。另外,帧块的大小di可能不同,帧块越大,帧块和重建误差之间的相关性越大,所以采用平均相关性来消除帧块尺寸大小的影响,用公式表示为

(12)

(13)

为了获得最小误差,可用最小二乘法求解重建系数,求解公式为

(14)

式中:K[Λt,Λt]是以Λt为行和列索引的K的子矩阵块;K[Λt,:]是以Λt为行索引的K的子矩阵块。

在得到关键帧块和重建系数后,重建误差更新

(15)

(16)

通过上述迭代步骤,直到算法满足停止准则,就可以得到关键帧块。在获取关键帧块后,通过一定的策略f从每个块中选取一帧就可以得到关键帧集合。

综上所述,设计的KSBOMP算法步骤如下。

输入:视频F=[f1,f2,…,fn],关键帧的最大数目k,视频帧块的大小di(1≤i≤m)。

输出:关键帧索引集Γ。

步骤:

1.WHILE(t≤k)DO;

2.根据式(12)和(16),选择与当前重建误差最相关的帧块作为关键帧块,记录索引值λt;

3.更新关键帧块索引集,Λt=Λt-1∪λt;

5.增加迭代次数t=t+1;

6.ENDWHILE;

7.从关键帧块中选择关键帧,即Γ=f(Λ),选择策略f可以具体设计,本文实验简单地采用关键帧块的最中间帧作为关键帧。

3 实验与讨论

3.1 实验设置

3.1.1 实验数据集 采用VSUMM数据集[5],该数据集包含50个从OpenVideoProject收集的视频,视频的格式为MPEG-1,长度在1～4min之间,帧率为30帧/s,视频的内容包括纪录片、教育、演讲、历史、风景等多种类别。该数据集还为每个视频提供了5个用户手工提取的关键帧集,可以用于与视频总结的关键帧进行比较。在实验中,对原始视频帧进行5倍下采样。

3.1.2 视频帧特征表示 实验中对视频帧的表示采用一种360维的混合特征[11],包括252维的CENTRIST特征[16]和108维的颜色特征。CENTRIST特征提取视频帧的结构信息,对每帧图像采用空间金字塔提取2层共6块图像,每块图像分别提取CENTRIST特征,然后采用PCA降为42维,所以每帧图像的CENTRIST特征为42×6=252维。在提取颜色特征时,将图像分成3×4个不重叠的小块,并对每块图像的RGB三个颜色通道采用颜色矩(均值、方差和斜度)提取颜色特征,所以颜色特征为(3×3)×(3×4)=108维。

3.1.3 评价方式VSUMM数据的评价方式采用客观评价,每个视频都由1个自动总结(automaticsummaries,AS)算法结果与5个用户总结(usersummaries,US)结果进行比较,采用3个评价指标对比较结果进行评价,具体包括精度P、召回率R和F值Fscore,具体公式为

(17)

(18)

(19)

式中:Nm是自动总结与用户总结相匹配的关键帧个数;NAS和NUS分别是自动总结和用户总结的关键帧的数量。根据定义可知,精度反映了自动总结选中匹配关键帧的能力,召回率反映了匹配关键帧击中用户总结的能力,F值是对精度和召回率的平衡,是对视频总结效果进行评价的最重要的整体指标。

在实验中,每个视频的自动总结分别与5个用户总结单独地进行比较和评价,然后用5个用户总结的评价均值作为该视频的最终评价结果,最后用50个视频的评价结果的平均值作为此数据集的最终评价结果。

3.2 实验结果

3.2.1 实验参数分析 算法的参数对算法的性能存在影响,因此需要根据领域知识预先设置参数或探究参数的影响。本文所提的KSBOMP算法的主要参数包括视频帧块的大小di和关键帧的数量k。

图1 KSBOMP算法性能随关键帧数量的变化规律

(1)视频帧块的大小di。帧块大小统一设置为13帧。由于对原始视频进行了5倍的下采样,所以在原始视频中的帧块大小是65帧,对应的时长大约为2 s。通常,视频的内容在2 s内不会发生明显的变化,块内的帧具有相似性。

(2)关键帧的数量k。根据视频总结的目的,不难理解选择过少或者过多的关键帧都是不理想的。关键帧过少会导致遗漏部分重要的信息,相反,选择过多的关键帧不仅会提取到无关紧要的信息,还有可能会造成冗余。

随着关键帧数目的变化,KSBOMP算法性能随关键帧的变化规律如图1所示,分析得出:随着关键帧数量的增加,精度先缓慢上升后下降,召回率一直增加,但增加的速度呈下降趋势,F值先增加后下降;当关键帧数量较少时,随着关键帧的增加,更多的关键帧将会和用户总结中的关键帧相匹配,性能会逐渐提升;随着更多的关键帧被选择,会选择到不能与用户总结相匹配的关键帧,而且多个关键帧可能会匹配到同一个用户总结的关键帧,即出现关键帧冗余情况,性能下降。

3.2.2 性能比较 将KSBOMP算法分别与DT[3]、STIMO[4]、VSUMM[5]、MSR[12]、SMRS[17]、SOMP[18]、AGDS[13]、NSDS[14]算法进行比较。DT、STIMO、VSUMM算法是基于聚类的视频总结算法,它们的结果可以从VSUMM算法的官方网站下载,其他的5种算法都是基于稀疏表示的算法。表1是不同算法的实验结果数据对比,表中加粗数据代表最优数据。

表1 不同算法的实验结果数据对比

从表1可以看出,KSBOMP算法的F值在所有对比算法中最高,说明KSBOMP算法的总体性能最好。一般来说,选择的关键帧的数目越多,与用户总结相匹配的关键帧也就越多,召回率也就会越高,因此MSR、SMRS、SOMP、AGDS、NSDS、KSBOMP算法的召回率高于其他3种算法。VSUMM拥有最高的精度,但是选择的关键帧的数目较少,所以会遗漏部分关键帧,导致召回率和F值不高。具体来看,KSBOMP算法的精度仅低于VSUMM算法,召回率在所有算法中最高,说明用户总结中的大部分关键帧被KSBOMP算法选中,且选择的不与用户总结相匹配的关键帧也不是很多。综合来看,KSBOMP算法在精度、召回率和F值三个评测标准中都具有优秀的表现。

为了对算法的时间复杂度进行比较,将KSBOMP算法和基于稀疏表示的对比算法在相同的计算平台(CPU型号Core i7-6700,3.4 GHz,RAM容量12 GB)上实验,以50个视频的平均运行时间对算法的时间复杂度进行表示,实验结果如表2所示,可以看出,KSBOMP算法的运行时间仅多于MSR和NSDS算法,但是远远少于其他的算法。结合表1,说明KSBOMP算法以增加少量时间复杂度为代价,获得了性能的显著提升。

表2 不同算法的平均运行时间

3.2.3 核函数的影响 为探究不同类型的核函数对KSBOMP算法的影响,采用高斯核函数和线性核函数分别进行实验。两种核函数的性能比较如图2所示,可以看出:随着关键帧数量的增加,采用高斯核函数的性能明显优于采用线性核函数,即使采用线性核函数,KSBOMP算法的性能也优于表1中的对比算法。

图2 高斯核函数和线性核函数性能比较

3.2.4 非线性和块稀疏的有效性 将KSBOMP算法与只考虑非线性和只考虑块稀疏的两种算法进行对比,证明联合考虑两种属性的有效性。具体地,KSBOMP算法和以下两种算法进行比较:(1)只考虑帧间的非线性属性,未引入视频的块稀疏特性的非线性稀疏字典选择算法[14],简称为非线性算法;(2)只考虑视频的块稀疏特性,未引入帧间的非线性属性的算法,简称为块稀疏算法。KSBOMP算法同时考虑非线性和块稀疏特性,三种算法的性能比较结果如图3所示,分析得出:不论关键帧的数量是多少,同时考虑非线性和块稀疏特性的KSBOMP算法的性能总是优于非线性算法,此结果证明了考虑块稀疏特性的有效性;当关键帧数量较少时,同时考虑非线性和块稀疏特性的KSBOMP算法的性能和只考虑块稀疏算法的性能基本一致,但是随着关键帧数量的增加,前者的性能明显优于后者,此结果证明了考虑非线性的有效性。

图3 三种算法的性能比较

4 结 论

本文主要研究基于稀疏表示的视频总结方法,同时考虑视频帧之间的非线性关系和关键帧的块稀疏特性。通过核函数将视频帧映射到高维特征空间,使视频帧之间的关系由非线性转化线性,建立了非线性稀疏字典选择模型用于提取关键帧;在非线性模型的基础上,通过视频帧邻域内的内容相似性,将视频分为帧块,将关键帧的块稀疏特性纳入模型,建立了非线性块稀疏字典选择模型来提取关键帧块。为了优化所提出的模型,本文还设计了KSBOMP算法,并在基准视频数据集上与文献[3-5,12-14,17-18]的算法进行了对比实验,结果表明,KSBOMP算法在性能和效率上都有一定的优势。

目前,KSBOMP算法还有待改进之处。首先,每个帧块包含相同数量的帧,但实际中固定长度的帧块中的视频帧可能会存在不相似的内容,因此在下一步的工作中,可以考虑结合镜头边界检测技术,根据视频的内容变化来划分帧块。另外,首先确定关键帧块,然后将关键帧块的中间帧选为关键帧,此策略虽比较简单,但可能会造成选择的关键帧在此帧块中并不是最具有代表性的,所以后续考虑更高效的选择策略来进一步提高算法的性能。