一种零延迟的基于滑动窗口的FGS带宽分配方法

摘要

一种零延迟的基于滑动窗口的FGS带宽分配方法：(1)初始化算法中的各个变量；(2)由FGS编码器在编码时提取当前编码帧的R-D曲线，将编码完成的帧放入滑动窗口内，依据实际测量的可用带宽和发送端帧率更新当前窗口的可用带宽值；(3)依据历史可用带宽总量与实际使用带宽总量，对当前窗口的可用带宽值进行修正，并以修正后带宽为上限，对整个滑动窗口运行一种现有的FGS带宽分配算法；(4)发送窗口内当前发送帧序号对应的那一帧，更新历史可用带宽总量和实际使用带宽总量；(5)若窗口大小超过阈值，滑动窗口下沿，并更新当前窗口的可用带宽值；(6)更新当前发送帧序号；(7)若还有未发送帧，则转到步骤(2)。本发明在不降低太多带宽分配效能的前提下，达到了快速分配带宽的目的，其所带来的延迟为零。

权利要求

1.一种零延迟的基于滑动窗口的FGS带宽分配方法，其特征在于步骤如下：(1)初始化：历史可用带宽总量TotalBW＝0，实际使用带宽总量UsedBW＝0，当前窗口的可用带宽值Rbudget＝0，当前发送帧序号NextSendID＝1；

(2)由FGS编码器取得当前帧及其R-D曲线信息，将帧放入滑动窗口内，依据实际测量的可用带宽Rcur和发送端帧率fps更新当前窗口的可用带宽值Rbudget；

(3)依据历史可用带宽总量TotalBW与实际使用带宽总量UsedBW，对当前窗口的可用带宽值进行修正，并以修正值为上限，对整个滑动窗口运行一种现有的FGS带宽分配算法；

(4)发送窗口内第NextSendID帧，更新历史可用带宽总量TotalBW和实际使用的带宽总量UsedBW；

(5)若窗口大小超过阈值Window，滑动窗口下沿，更新当前窗口的可用带宽值Rbudget，具体实现步骤为：(5.1)若窗口大小超过阈值Window时，滑动窗口下沿，清除旧视频帧的数据；

(5.2)更新当前窗口的可用带宽值Rbudget为：Rbudget＝Rbudget-r，其中r为滑动窗口内最旧一帧发送时所占带宽，由于每一步都会检测窗口大小，故当其为Window+1时，立刻会被检测到，只要去除第一帧的数据即可回退到Window大小；

(6)若NextSendID小于阈值Window，则令NextSendID＝NextSendID+1；

(7)若还有未发送帧，则转到步骤(2)。

2.根据权利要求1的零延迟的基于滑动窗口的FGS带宽分配方法，其特征在于：所述的步骤(2)进一步包括：(a)由FGS编码器在编码时提取当前编码帧R-D曲线信息；

(b)将当前编码完成的视频帧放入滑动窗口；

(c)依据当前实际测量的可用带宽Rcur和发送端帧率fps以下式更新当前窗口的可用带宽值Rbudget：Rbudget＝Rbudget+Rcur/fps。

3.根据权利要求1的零延迟的基于滑动窗口的FGS带宽分配方法，其特征在于：所述的步骤(3)进一步包括：(a)根据历史可用带宽总量TotalBW和实际使用带宽总量UsedBW以下式对当前窗口的可用带宽值R进行修正：R＝Rbudget-(UsedBW-TotalBW)；

(b)以R为可用带宽上限，对整个滑动窗口运行一种现有的FGS带宽分配算法，所述现有的FGS带宽分配算法为牛顿搜索法，二分搜索法，或R-D曲线合成法。

4.根据权利要求1的零延迟的基于滑动窗口的FGS带宽分配方法，其特征在于：所述的步骤(4)进一步包括：(a)根据前一步的算法结果发送窗口内第NextSendID帧；

(b)更新历史可用带宽总量TotalBW：TotalBW＝TotalBW+Rcur/fps，以及实际使用带宽总量UsedBW：UsedBW＝UsedBW+rsend，其中rsend为当前发送帧所占带宽。

说明书

技术领域

本发明涉及一种在异构网络环境下，大规模交互式实时多媒体系统中视频码流的带宽分配算法，尤其涉及一种零延迟的基于滑动窗口的FGS(Fine Granularity Scalability，精细可扩展编码)带宽分配方法。

背景技术

异构网络环境下的实时视频会议系统中需要解决的一个基本问题是视频流的网络带宽自适应。在MPEG-4标准中提出的FGS编码方式对DCT残差系数做位平面编码，其产生的码流可根据实际带宽的变化对增强层作任意长度截取而解码，而视频质量与解码长度成正比。
为了有效利用FGS码流的这种特点，需要使用一种带宽分配算法以保证接收端在可用带宽变动的情况下仍能得到较恒定的图像质量。目前为止，牛顿搜索法，二分搜索法，R-D曲线合成法等被提出并都取得了不错的效果。这些算法使用了一种滑动窗口以保证带宽分配结果的精度和有效性。所谓滑动窗口其实就是一个在发送端保存了M帧的缓冲区。算法每次发送出去的那一帧并不是编码器当前编码完成的，而是第N-M帧(我们假设当前编完码的是第N帧)。这样即使接收端收到后马上播放也会有M/Fs秒的延迟(设Fs为发送端帧率)。此外，M的一个典型取值往往是Fs的2到3倍，这也意味着造成的时延为2到3秒。在时延要求苛刻的交互式系统中M/Fs秒的延迟将变得让人难以接受，也会给交互效果带来很大的影响。

发明内容

本发明的技术解决问题：将现有的FGS带宽分配算法应用于时延要求苛刻的交互式应用中(如视频会议)，并对其进行改进，去除了原算法延迟大的缺点，提出了一种基于滑动窗口的FGS零延迟的带宽分配算法，它根据历史可用带宽总量与实际使用带宽的差值，对当前滑动窗口的可用带宽值进行补偿修正，并依据当前视频帧和历史视频帧的R-D曲线方程来运行算法，在不降低太多带宽分配效能的前提下，达到了快速分配带宽的目的，其所带来的延迟为零。
本发明的技术解决方案：一种零延迟的基于滑动窗口的FGS带宽分配算法，其特征在于如下步骤：
(1)初始化：历史可用带宽总量TotalBW＝0，实际使用带宽总量UsedBW＝0，当前窗口的可用带宽值Rbudget＝0，当前发送帧序号NextSendID＝1；
(2)由FGS编码器提取当前编码帧及其R-D曲线，将帧放入滑动窗口内，依据实际测量的当前可用带宽Rcur和发送端帧率fps更新滑动窗口的可用带宽值Rbudget；
(3)依据历史可用带宽总量TotalBW与实际使用的带宽总量UsedBW，对当前窗口的可用带宽值进行修正，并以修正后带宽为上限，对整个滑动窗口运行一种现有的FGS带宽分配算法；
(4)发送窗口内第NextSendID帧，更新历史可用带宽总量TotalBW和实际使用的带宽总量UsedBW；
(5)若窗口大小超过阈值Window，滑动窗口下沿，更新当前窗口的可用带宽值Rbudget；
(6)若NextSendID小于Window，则令NextSendID＝NextSendID+1；
(7)若还有未发送帧，则转到步骤(2)。
根据本发明的又一个方面，其中步骤(2)进一步包括步骤：
(a)由FGS编码器在编码时提取当前编码帧R-D曲线信息；
(b)将当前编码完成的视频帧放入滑动窗口；
(c)依据当前实际测量的可用带宽Rcur和发送端帧率fps以下式更新当前窗口的可用带宽值Rbudget：Rbudget＝Rbudget+Rcur/fps。
根据本发明的又一个方面，其中步骤(3)进一步包括：
(a)根据历史可用带宽总量TotalBW和实际使用带宽总量UsedBW以下式对当前窗口的可用带宽R进行修正：R＝Rbudget-(UsedBW-TotalBW)；
(b)以R为可用带宽上限，对整个滑动窗口运行一种现有的FGS带宽分配算法，所述现有的FGS带宽分配算法为牛顿搜索法，二分搜索法，或R-D曲线合成法。
根据本发明的又一个方面，其中步骤(4)进一步包括：
(a)根据前一步的算法结果发送窗口内第NextSendID帧；
(b)更新实际使用的带宽总量UsedBW：UsedBW＝UsedBW+rsend以及历史可用带宽总量TotalBW：TotalBW＝TotalBW+Rcur/fps，其中rsend为当前发送帧所占带宽；
根据本发明的又一个方面，其中步骤(5)进一步包括：
(a)若窗口大小超过阈值Window时，滑动窗口下沿，清除旧的视频帧数据；
(b)更新当前窗口的可用带宽值Rbudget：Rbudget＝Rbudget-r，其中r为滑动窗口内最旧一帧发送时所占带宽。由于每一步都会检测窗口大小，故当其为Window+1时，立刻会被检测到，只要去除第一帧的数据大小即可回退到Window。

附图说明

图1为本发明的算法基本流程图；
图2为已有算法的发送端缓冲区状态图；
图3为本发明算法测试实验中Markov网络模型模拟的带宽变动图；
图4为各个测试序列在三种算法作用下的不同结果比较图，其中：图a为Mother_dauther Cif在本算法与二分搜索法作用下的不同结果；图b为Mother_dauther Cif在本算法与平均分配法作用下的不同结果；图c为Akiyo Cif在本算法与二分搜索法作用下的不同结果；图d为Akiyo Cif在本算法与平均分配法作用下的不同结果；图e为Coastguard Cif在本算法与二分搜索法作用下的不同结果；图f为Coastguard Cif在本算法与平均分配法作用下的不同结果；图g为Container Cif在本算法与二分搜索法作用下的不同结果；图h为Container Cif在本算法与平均分配法作用下的不同结果。

具体实施方式

下面参考附图，对本发明的实施例进行详细的说明。
具体而言，本发明所提出的改进算法基本流程如图1所示。
本发明主要包括的核心思想：根据历史可用带宽总量与实际使用带宽的差值，对当前可用带宽值进行修正，并以当前发送帧与历史数据帧的R-D曲线方程为对象来运行FGS带宽分配算法，从而降低了时延，但又不损失太多带宽分配效能。
在描述算法前先定义如下变量：
1.TotalBW为历史可用带宽总量，UsedBW表示实际使用的带宽总量；
2.Rbudget表示当前滑动窗口的可用带宽，Rcur为编码某一帧时实际测量的网络可用带宽；
3.Window表示预定义的滑动窗口大小；
4.NextSendID为下一个发送帧在当前窗口内的序号；
5.fps为发送端的帧率。
本发明的算法描述如下：
(1)初始化：历史可用带宽总量TotalBW＝0，实际使用的带宽总量UsedBW＝0，当前窗口的可用带宽值Rbudget＝0，当前发送帧序号NextSendID＝1；
(2)由FGS编码器提取当前编码帧及其R-D曲线，将帧放入滑动窗口内，更新窗口的可用带宽值Rbudget：Rbudget＝Rbudget+Rcur/fps，Rcur为当前实际测得的网络可用带宽。
(3)令R＝Rbudget-(UsedBW-TotalBW)，对现有窗口以R为可用带宽上限运行一种已有FGS带宽分配算法；
现有的算法是二分搜索法，运行算法的步骤如下：
a.计算只发送基本层窗口内所有帧的最小失真Dw
b.计算若R＜Rbudget-δ，则令Dmin＝Dw；若R＞Rbudget+δ，贝令Dmax＝Dw；
c.否则，结束算法。
算法中的Dmin和Dmax为预定义的最小和最大失真，δ则是平衡因子，保证算法在有限步骤内结束，Ri(D)则是各个视频帧的R-D曲线方程。
(4)发送窗口内第NextSendID帧，令TotalBW＝TotalBW+Rcur/fps，UsedBW＝UsedBW+rsend，其中rsend为发送帧所占带宽；
(5)若窗口大小超过阈值Window，则滑动窗口下沿，即清除最旧的视频帧，同时更新窗口的可用带宽值Rbudget：Rbudget＝Rbudget-r，其中r为滑动窗口内最旧一帧发送时所占带宽。由于每一步都会检测窗口大小，故当其为Window+1时，立刻会被检测到，只要去除第一帧的数据大小即可回退到Window；
(6)若NextSendID小于Window，则令NextSendID＝NextSendID+1；
(7)若还有未发送帧，则转到步骤(2)。
本发明的算法与原有算法最大的不同之处是：虽然本算法中也存在滑动窗口，但其仅含有一个未发送帧，其余都是历史帧；而现有算法的窗口内全是未发送的视频帧。这样，在本算法中，每一帧编码完成后经过处理就会马上被发送出去，不存在任何延迟。这一点对于像视频会议中现场实时录制的视频源来说尤为重要。
此外，较现有算法，本算法内存的使用量将会大大下降。这是因为，本算法的滑动窗口中只保存了现在将要发送那一帧的码流，并记录至多Window个视频帧的R-D曲线方程信息；比较而言，现有算法则是保存了Window个未发送的视频帧码流。
以下通过本发明算法和现有算法的对比实验，对本发明在保障带宽分配效能的前提下有效降低算法时延的改进予以说明。实验采用的测试序列分辨率为352×288，各200帧，帧率为20，即测试时间为10秒。实验以二分搜索算法作为本算法第3步中使用的算法，所对比的算法是平均分配法和二分搜索法。其中Window取为50，二分搜索法的窗口大小也取为50。实验中的网络环境使用了Markov网络模型来模拟实际的网络状态，其中发送速率为125kB/s，信道平均丢包率0.0997，每个包长625字节，平均突发丢包长度9.57，图3为模拟实验中的带宽变动图。实验统计了各个算法在接收端Y分量的PSNR。
图4为三种算法带宽分配结果的对比图。其中左边的图为本发明算法与二分搜索法的比较结果，右边的则是与平均分配算法的比较结果。可以看到，本算法与二分搜索法的结果都比较接近，且远好于平均分配算法。由于本算法启动时信息较少，带宽分配的结果较差，但随着时间的推移，就非常接近二分搜索法的效果。平均而言，平均分配算法在相邻帧的PSNR抖动上最显著，由图e、f可知在测试序列Coastguard Cif上超过了4分贝，而本算法仅有0.280分贝，这与二分搜索法的0.263分贝已经非常接近。另一方面，对于所有的测试序列，由图4可得，平均分配算法的PSNR抖动在4到6分贝之间，而本发明算法抖动在1.1分贝之内(不考虑前10帧的分配结果)。当然二分搜索法的效果最好，抖动被控制在0.7分贝左右。
应用本发明的多媒体实时交互系统已多次在教育部、科技部的视频会议中得到应用。在教育部，超过150个大学和各个省市的教育主管部门已经使用该系统作为教育部内部的协同和会议平台。证明了实际的应用效果。
对于本领域的普通技术人员来说可显而易见的得出其他优点和修改。因此，具有更广方面的本发明并不局限于这里所示出的并且所描述的具体说明及示例性实施例。因此，在不脱离由随后权利要求及其等价体所定义的一般发明构思的精神和范围的情况下，可对其做出各种修改。