mpegvbr视频流建模与统计特性分析

mpegvbr视频流建模与统计特性分析

1视频流模型应采用的模型网络技术，尤其是宽带网b-isdt技术的发展，使多媒体应用，如视频传输、交互式电视、vod等逐渐成为可能。然而，要使这一可能性成为现实，首先，我们必须理解如何影响宽带网络的视频传输。根据近年来的研究，由于vbr视频流具有长期依赖于（lrd）和自我相似性行为，因此有必要建立有效的vbr视频流统计模型。网络流,特别是多媒体视频流,流内呈现较大的突发性.影响视频流突发性的两个关键因素是视频流的边际分布和流量到达时间间隔内的自相关函数,特别是短时自相关(SRD).流量过程对排队性能如队长、平均等待时间、缓冲丢失概率、缓冲溢出概率的影响往往是随时间而动态地变化,即使是对较轻的流量亦是如此.因此,要建立完整、有效的视频流模型,并能用其进行网络性能分析、网络设计和控制,将是一项十分困难的工作.然而,编码视频流因其固有的编码压缩算法(MPEGI,II),使得连续编码帧之间的速率相差极小,并且同一场景中的视频序列存在时间上的依赖关系,特别是正的短时自相关.因此,为模拟宽带网络的视频流,我们应该采用自相关模型.同时,视频流序列的突发性既可能因位流速率分布,也可能因流内自相关性引起,因此必须采用一种能同时拟合视频流序列的一阶和二阶统计特性的模型,这就是我们后面将要引入的TES模型.而大多数已有模型要么只能拟合视频流序列的分布函数,要么只能拟合其自相关函数,因而都不足以完整地对VBR视频流序列进行建模.2视频流序列建模方法我们的实验数据来源于Wuerzburg大学的Rose,可以通过其FTP站点下载.我们分析了实验数据的统计特性并在此基础上进行了建模仿真.实验分析的结果表明:(1)对流内突发性,可以采用Markov调制模型进行建模,这与已有的MMPP(MarkovModulatedPiossionProcess)以及Rose的研究结果是一致的;(2)Melamed的基于帧的TES模型对独立场景进行建模,因存在帧间的周期性自相关而难以对视频流序列的一阶和二阶统计特性进行有效的拟合;(3)Rose提出的基于GOP的三层建模方案,因Markov调制模型的状态空间过大,而以平方倍增加了计算的复杂性,这在实时应用中是不能满足需要的;(4)应用Markov调制模型模拟流内突发性,对场景变化进行建模,应用TES模型基于GOP速率对独立场景进行建模,则既能有效地描述流内突发性,又能捕获独立场景的分布和自相关属性;(5)视频流序列GOP间的分布可以用Gamma函数进行拟合,而自相关性则可以用双指数函数更好地拟合,而非仅仅是单指数拟合.下面简述我们的建模方案:(1)首先进行视频分段,视频序列被划分成多个独立的场景(scenes);(2)场景聚类,采用一定的聚类算法将场景划分到不同的类属中,每个场景被赋予特定的类标识(tag);(3)针对场景聚类建立有限状态马氏链;(4)基于GOP速率的每一个独立场景,根据其分布和自相关统计特性用TES过程建模;(5)最后,场景持续时间被建模成依赖于类的独立同分布(i.i.d)随机过程.以上步骤均是在GOP基础上进行.3连续gop/场景切换以下我们主要针对MPEG视频《侏罗纪公园》(JurassicPark)进行分析,我们对其它MPEGVBR视频流所做的分析也得到相应的结论.图1分别绘出了I,P,B的帧速率图,图中用3条虚线将它们分隔开,由上至下为I,P,B.由图1可见,I帧速率最高,P帧速率次之,B帧最低,这是由MPEG视频流编码特性所决定的.图2则绘出了基于GOP的图片组尺寸示意图.GOP共有3334个,为清晰起见,我们只绘出了前200个GOP.可以看出,若不考虑GOP间的突发性,连续GOP间的尺寸相差极小,即存在较大的短时自相关性.同时,从图中粗略的垂直虚线所划分开的每个场景来看,每个场景都可以看成是由一个独立的平稳随机过程构成.也就是说,该视频流序列可以看成是由许多个独立的场景(平稳随机过程)以及场景间的随机迁移组成,而场景边界则代表了连续GOP尺寸的突发性.视频分段有多种方法,本文采用简单的差分检测法.即当连续GOP间尺寸的差值的绝对值超过某一门限时,即认为发生场景切换.设GOP序列为{Xn},定义Jmin为差分门限,Jn为差分序列,则当且仅当|Xn-Xn-1|>Jmin⇒Jn=1,此时,我们认为视频发生了场景切换.然而,注意到并非所有超过了Jmin的GOP差分都预示着场景切换.因此为了准确地预测场景切换,定义最小场景切换长度为Lmin和场景标识序列{Sn},则当且仅当:Jn=1,Jn-1≠1,Jn-2≠1,…,Jn-Lmin≠1,⇒Sn=1.在实验中,我们设Jmin=105,Lmin=3,得到145个场景,对应于每个场景约8—10s左右,这与实际的视频序列基本吻合.4等价类聚类算法在对视频分段得到多个独立的场景后,我们需要将场景划分到尽可能少的类中,以便减少模型的复杂性.我们的目的是使聚类到同一类中的多个场景都能用一个通用的概率分布模型来进行描述.因此每一个等价类都可以用一个独立的随机过程来对其分布函数和自相关函数进行建模,而等价类之间则可以用Markov链进行建模.我们认为,多个场景可以由有限数个(<10)场景类进行聚类.因此,场景划分和聚类涉及到以下三个问题:(1)聚类准则;(2)聚类方法(最少类原则);(3)聚类过程.首先,需要确定是用场景的均值还是方差,或者二者同时作为聚类准则.事实上,用场景均值即可以获得一个较好的聚类准则(见图3).其次,采用何种方法进行聚类以获得最少的聚类数目.问题描述.给定d维空间中n个元素,需要找到一个关于n个元素的等价类划分K,使得这个等价类中元素间的距离小于到其它等价类间的距离,并且每个等价类中的元素的个数几乎相等.通常采用的距离度量是欧氏距离.d维空间中两元素u,v的欧氏距离η(u,v)定义为η(u,v)=√d∑i=1(ui-vi)2η(u,v)=∑i=1d(ui−vi)2−−−−−−−−−−ue001⎷ue000ue000,其中,u={u1,u2,…,ud},y={v1,v2,…,vd}.聚类算法采用逐步迭代、逐步修正的试探算法(TryandError).假设n个元素已经划分成K个聚类{C1,C2,…,CK},其中Ck={X(k)n1(k)n1,X(k)n2(k)n2,…,X(k)nk(k)nk},并且Κ∑k=1nk=n∑k=1Knk=n,则可以定义聚类中心为m(k)=1nknk∑j=1X(k)jm(k)=1nk∑j=1nkX(k)j;类中聚类方差为e2k=nk∑j=1η2(X(k)j,m(k))e2k=∑j=1nkη2(X(k)j,m(k)),因而总的聚类方差为E2Κ=Κ∑k=1e2kE2K=∑k=1Ke2k.聚类迭代搜索算法的目的就是寻找最佳聚类K,使得聚类方差E2Κ2K达到最小.其次,阐述聚类过程如下:(1)选择初始聚类;(2)将一个场景赋予具有最小聚类中心的聚类;(3)计算新的聚类中心和聚类方差;(4)重复(2),(3)直到聚类方差收敛;(5)通过分离或合并聚类,或移去较小的聚类,调整聚类个数.引入两辅助参数:ηmin表示类间中心最小距离;E2max2max表示类内最大方差.当两个聚类的中心小于ηmin时,该两聚类合并;当某聚类方差大于E2max时,该聚类被分离成两个聚类.通过调整这两个参数,可以控制允许的最大聚类数目(事实上,ηmin和E2max2max是相互制约的,因此必能得到最佳聚类).该方法的目的是尽可能地通过〈均值,方差〉对来对场景进行聚类.图3是采用该聚类方法对《侏罗纪公园》的场景进行聚类得到的均值-方差图.共有145个场景,经聚类得到4个场景类,其中,|Class#1|=34,|Class#2|=38,|Class#3|=38,|Class#4|=35.从图3中可以看出,聚类模式主要依赖于均值(mean),而受方差(variance)的影响较小.图3中用不同的符号表示不同的聚类,并用垂直虚线将聚类间大致分隔开.因此,在聚类算法中,我们可以仅考虑均值,而忽略方差的影响.5场景标记序列及转换概率采用第4节的聚类算法,我们可以得到对场景的分类,并且认为属于同一聚类的场景服从相同的平稳随机分布;而场景间的切换则可以用Markov调制链{Mn}加以表示.假设我们已经对视频流序列进行了场景划分,并且用标号C1,C2,C3,C4表示场景所属的类,则可以得到一场景标号序列{Cn},而{Mn}的转移矩阵P则可从标号序列{Cn}中求得.例.设某视频片段场景标号序列为{Cn}={1132,4213,4124,3122,2144,3133,2413,21},包含30个场景切换,|Cn|=30,则经计算可得其转移矩阵P的1步(OneStep)转移概率为Ρ=[1/30,1/15,2/15,1/30;1/10,1/15,0,1/10;1/15,1/10,1/30,1/30;1/15,1/30,1/15,1/30].P=[1/30,1/15,2/15,1/30;1/10,1/15,0,1/10;1/15,1/10,1/30,1/30;1/15,1/30,1/15,1/30].6gop而非帧fear场景建模在这节中,我们首先讨论TES建模方法;再讨论为什么要针对GOP而非帧(frame)对场景进行建模;最后讨论如何用TES模型对独立的场景及场景持续时间进行建模.6.1实验自相关数据模型TES模型的目的在于能够有效地同时拟合给定的时间序列的分布函数和自相关函数,即同时捕获已有随机序列的一阶和二阶统计特性.TES模型包括两部分:TES+和TES-.TES+包括如下形式的随机序列{U+n}∞n=0:U+n={U0,n=0;〈U+n-1+Vn〉,n>0(1)U+n={U0,⟨U+n−1+Vn⟩,n=0;n>0(1)其中,U0在[0,1)上均匀分布,{Vn}∞n=1是与U0相互独立的独立同分布(i.i.d)的随机变量,称为更新序列(innovationsequence),〈X〉=X-max{intn|n≤X}.注意到TES+能产生所有在[0,1)间的延迟为1的自相关系数.同样,TES-能产生所有在(-1,0]间的延迟为1的自相关系数.另定义关于{U+n}∞n=0的变换序列(transformsequence){X+n}∞n=0:X+n=D(U+n)D:[0,1)→R(2)X+n=D(U+n)D:[0,1)→R(2)给定一时间序列{Yn}Νn=0Nn=0,定义:DY,ξ(x)=ˆΗ-1Y(Sξ(x)),x∈[0,1)(3)DY,ξ(x)=Hˆ−1Y(Sξ(x)),x∈[0,1)(3)其中,Sξ(x)={x/ξ,0≤x≤ξ(1-x)/(1-ξ),ξ≤x≤1‚0≤ξ≤1(4)Sξ(x)={x/ξ,(1−x)/(1−ξ),0≤x≤ξξ≤x≤1‚0≤ξ≤1(4)而ˆΗHˆY为从序列数据计算得到的概率分布(直方图-Histogram).ˆΗ-1Y(x)=J∑j=1Ι[ˆCj-1,ˆCj)(x){lj+(x-ˆCj-1)ωjˆΡj}(5)其中,J为直方图单元数,[lj,rj)为直方图第j单元格,ωj=rj-lj(>0)为单元格宽度,ˆΡj为单元格j的概率,{ˆCj}Jj=1为{Pj}Jj=1的累积概率分布(CDF).即ˆCj=j∑i=1ˆΡi(ˆC0=0,ˆCJ=1).ΙA称为集合A的指示函数(indicatorfunction).注意到:(1)由式(1)可知,{U+n}∞n=0是平稳过程,且具有Markov特性,其分布函数在[0,1)上均匀分布,而与更新序列{Vn}∞n=1的选择无关.(2)由式(5),求逆方法使得我们可以将均匀分布的序列变换到具有任何分布的随机序列,如下所示:假设U在[0,1)上均匀分布,F为给定的分布,则X=F-1(U)的分布函数为F,特别是当F=ˆΗ-1Y.(3)变换Sξ|ξ∈[0,1)可以使得采样序列更为光滑和连续,因此,序列X+n=ˆΗ-1Y(Sξ(U+n))(6)可以保证其具有经验分布ˆΗY(直方图),而与更新序列{Vn}、更新序列密度函数fV无关.参数对(fV,ξ)的选择,仅决定序列{X+n}的序列间依赖性及自相关函数.因此,TES模型使得对分布函数和自相关函数的拟合能够分别进行.实际应用中,需要根据经验数据对{fV,ξ}进行启发式搜索,以使TES模型能更好地拟合经验数据的分布和自相关统计特性.软件支撑的TES环境TEStool能交互式地提供模型与实验数据的一阶、二阶统计特性的最佳拟合.6.2自相关函数的拟合以下分析基于GOP和基于帧(frame)的序列自相关性,并讨论为什么要对场景采用基于GOP的建模.图4和图5分别是基于帧和基于GOP的整个视频流序列的自相关曲线.由图4可以看出:基于帧的序列自相关呈现出有规律的周期性和突发性,这与视频流场景内序列相关性以及场景间切换时的流量突发性是相一致的,要对该自相关函数进行拟合是非常困难的;相反,从图5可以看出,基于GOP的序列自相关则随延迟步长的增加而几乎呈指数下降,当延迟超过60时,GOP序列间的自相关已经很小,因此更利于进行有效的拟合.这就是为什么我们在实验中采用基于GOP的场景建模的原因.Rose曾建议用单指数函数对GOP自相关性进行拟合.我们采用单指数函数拟合的结果见图5,可见,拟合曲线与自相关曲线差异很大.同时,我们考虑采用双指数函数进行拟合,形式如下:ρ(j)≈αρj1+(1-α)ρj2(7)其中,j为延迟,ρ(j)为自相关系数.实验中,我们取α=0.716,ρ1=0.854,ρ2=0.996,拟合结果见图5.可见,双指数函数能更好地拟合基于GOP的自相关函数.对其它MPEG视频流的分析也验证了该结论.6.3场景自相关函数给定视频序列,我们可以通过对其一阶、二阶统计特性的分析,来对该时间序列中已被划分出来的独立场景进行建模.图6绘出了给定视频序列被分段、聚类后,各子类的概率分布(直方图).正如文献的图12所示,Gamma分布比Gauss分布能更好地拟合各子类的概率分布,仅存在极小的拖尾效应.另外,除了如6.2节提到的全视频序列GOP自相关函数的双指数拟合外,为估计每一个场景类的自相关系数,我们采用以下估计方法:在每一场景类中选择一个代表性的场景,对子类中的代表场景采用三阶多项式进行了拟合,得到如图7所示的基于GOP的场景自相关函数曲线.可以看出,在延迟小于20GOPs时,该拟合也是可以接受的.当然,因为超过20GOPs(约8—10s视频流)时,通常场景都已经发生切换;并且属于同一场景类的两个连续场景往往并不相邻,因此基于GOP的场景自相关估计只能在同一场景中进行(对基于帧的估计亦然).实验结果与实际的视频流序列是相一致的.我们采用Gamma分布对各子类场景的GOP概率分布进行拟合;采用双指数函数或更简单的三阶多项式对场景的GOP自相关函数进行拟合.在此基础上,用TES模型对独立的场景进行建模,在较小的延迟(lag)下,将最大限度地减少计算的复杂性,增加实时应用的可能性.自相关系数的估计采用如下方法:给定视频流序列{Yn}Νn=0,则,ˆρ(τ)=1ˆσΗˆσΤ(Ν-τ)Ν-1-τ∑j=0(Yj-ˆmΗ)(ˆYj+τ-ˆmΤ)(8)其中,ˆmΗ=1Ν-τΝ-1-τ∑j=0Yj,ˆσ2Η=1Ν-τΝ-1-τ∑j=0(Yj-ˆmΗ)2,ˆmΤ=1Ν-τΝ-1∑j=τYj,ˆσ2Τ=1Ν-τΝ-1∑j=τ(Yj-ˆmΤ)2.也可以采用简单的估计方法(RoseO博士论文):ˆρ(k)=1ΝΝ-k∑t=1(Yt-ˆμ)(Yt+k