第35卷第1O期 2012年1O月 计 算 机 学 报 Vo1.35 No.10 0ct.2O12 CHINESE JOURNAL OF COMPUTERS 视频解码计算复杂度的线性建模理论及在线预测方法 田 婷” 余胜生” 郭红星” 苏曙光 ”(华中科技大学计算机科学与技术学院 武汉(华中科技大学软件学院武汉430074) 430074) 摘要视频解码是一类最典型的多媒体应用,其计算量大、耗能高.现代多媒体计算平台可利用视频解码计算复 杂度固有的动态变化特征来自适应地调整所需计算资源,从而节省能耗,其前提是对视频解码计算复杂度进行准 确估计.作者基于解码计算复杂度与帧长之间的线性关系,提出了一种利用状态变量法对解码计算复杂度进行理 论建模和在线估计的方法.与传统的直接对帧长和计算复杂度之间的输入一输出依赖关系进行建模所不同,这里将 视频解码系统表征为由视频内容特征的状态变化所驱动的系统.首先从语义层面对解码器各模块的解码复杂度进 行分析,并导出各模块计算复杂度与语义参数间的依赖关系模型,总解码复杂度为各子模块的复杂度之和.经过化 简得到解码计算复杂度与帧长之间的线性模型,其中模型系数为上述语义参数的函数,表征了视频内容特征的状 态变化,被定义为状态变量.再结合压缩视频流中相邻帧语义参数之间的相关性,将系统状态方程定义为反映视频 内容变化程度的分段线性函数.根据I帧和P帧状态轨迹特性及其在压缩码流中位置属性的不同,分别进行计算 复杂度在线估计:对于I帧,采用统计分析方法获得其状态变量的均值并进行在线估计;而对P帧,则是在运行过 程中利用状态方程对状态变量进行实时更新和计算复杂度估计.在基于SimpleScalar的软件仿真平台和基于DSP 的嵌入式硬件平台上分别对H.264、MPEG一4压缩码流的解码计算复杂度进行在线估计,实验结果表明:对解码计 算复杂度的平均估计误差在7 以内,预测精度非常高,而且状态方程更新过程简单,在线运行复杂度低,特别适用 于嵌入式移动设备. 关键词 视频解码;计算复杂度;线性模型;在线预测;状态变量分析法 中图法分类号TP302 DO1号:10.3724/SP.J.1016.2012.02048 Linear Modeling and Online Predicting for Video Decoding Complexity TIAN Ting YU Sheng—Sheng ’ GUO Hong—Xing SU Shu—Guang (School of Computer Science and Technology.Huazhong University of Science and Technology,Wuhan 430074) (School of Software Engineering,Huazhong University of Science and Technology,Wuhan 430074) Abstract Multimedia applications,such as video decoding,always take heavy computational complexity and cause huge energy consumption.To save energy,existing hardware platforms tend to adj ust their resources according to the actual decoding computational demand.The e ffec— tiveness of such methods depends on the prediction accuracy of decoding complexity.Based on the linear relationship between frame length and the decoding complexity of each frame,this paper proposes a linear modeling and online predicting method which utilize State—Variable Analysis (SVA)for video decoding complexity prediction.The state equation of decoding system is estab— lished as follows.The semantic meanings of state variables which directly affect the linear rela— tionship between frame length and decoding complexity are exploited through analysis on decoding procedure.Then combined with the semantic correlation between neighboring frames in 收稿日期:2012—06—30;最终修改稿收到日期:2012—08—13.本课题得到国家自然科学基金“嵌入式多媒体流计算的质量驱动机制与共生调 优”(61173044)、国家自然科学基金“嵌人式多媒体流计算的自适应机制与跨层优化”(60873029)、中央高校基本科研业务费专项资金资 助.田 婷,女,1985年生,博士研究生,主要研究方向为嵌入式计算、流媒体技术.E—mail:tianting.hust@gmail.corn.余胜生,男,1944 年生,教授、博士生导师,主要研究领域为计算机存储系统、多媒体技术.郭红星(通信作者),男,1971年生,博士,副教授,主要研究方向 为嵌入式计算、多媒体网络.E mail:guohx@mail.hust.edu.el1.苏曙光,男,1975年生,博士,讲师,主要研究方向为视频编码与通信、嵌 入式系统与中间件. 10期 田 婷等:视频解码计算复杂度的线性建模理论及在线预测方法 comDressed streams,the state equation is established as a piecewise function which can reflect the variation of video content. Considering the different characteristics of state traj ectory between intra—frame and inter—frame,we provide online decoding complexity predicting methods for them respective1y.The mean values of state variables for intra—frame are obtained through offline sta— tistica1 analysis and then utilized directly during online process to predict decoding complexity. For inter—frame,the values of state variables are calculated using state equation in the online Drocess and then the decoding complexity can be predicted.The proposed method is implemented on both software—based simulation platform and DSP—based hardware platform,the decoding complexitv of compressed streams which use either H.2 6 4 or MPEG一4 coding standards is predic— ted.The experimental results show the proposed method can give fairly accurate prediction for decoding complexity.The average prediction errors are less than 7 .Moreover,since the state equation can update the state variable at a very 1OW cost,the runtime overhead of the method is very smal1.It is very useful for those resource-limited mobile devices. Keywords video decoding;computational complexity linear model;online prediction;state variable analysis 对多媒体流的计算复杂度进行精确估计是提高 引 言 视频编解码一类的多媒体应用不仅计算复杂度 DVFS效率的前提.最坏路径法(单位计算单元运行 最大开销)和平均值法(单位计算单元运行平均开 销)是对系统计算量进行估计的常用方法.由于多媒 高,而且计算过程需要进行密集数据存取,导致其功 耗需求较一般应用程序要大得多.因此,如何构建高 性能、低功耗的多媒体系统一直是设计者长期追求 的目标,特别是对于目前方兴未艾的无线移动多媒 体应用,由于其硬件平台资源严重受限,且采用电池 供电,能量有限,更迫切需要采用节能技术来提高续 航能力.这已经成为衡量众多移动设备性能的最重 要指标之一. 通过动态调节技术能使系统在运行阶段根据工 体系统计算复杂度受视频压缩标准、视频帧的编码 类型、采用的编码工具集合、视频内容、幅面、压缩码 率等因素的影响,变化幅度非常大,传统的计算复杂 度估计方法不适用于时变性非常强的多媒体任务, 迫切需要发展针对多媒体流计算任务的精确计算复 杂度估计方法. 视频解码是目前应用最为广泛的一类多媒体应 用.本文将以视频解码计算复杂度为研究对象,探讨 对其进行分析和建模的方法;同时通过该分析和建 作负载的动态变化来调整工作模式,从而降低能 耗l_1].现代计算机硬件的可伸缩性也为动态调节技 术提供了支持.按照调节方式的不同可将动态调节 技术分为两类:动态功耗管理(DPM)技术 和动态 电压频率调节(DVFS)技术[3].DPM根据系统工作 负载的变化情况有选择地将设备设置为低功耗模式 模过程归纳出对多媒体系统进行分析的共性方法并 指导后续工作. 2 相关研究 本节将在分析已有视频解码复杂度估计方法的 基础上,简要说明本文的工作及其意义. 2.1 视频解码复杂度估计研究进展 (或直接关闭),从而降低系统能耗.DVFS则通过动 态预测后续任务所需计算量,并根据预测结果调节 处理器运行电压和频率,以达到任务响应时间和系 统功耗之间的平衡.DPM技术适用于间歇性任务, 典型视频解码复杂度估计方法可分为两类:基 于统计分析的方法和基于预测的方法.基于统计分 析的方法首先将解码过程分成几个相对独立的模块 如硬盘读写操作;对于实时性要求高、任务时间间隔 短的多媒体流计算任务,频繁的设备状态切换不仅 增大了系统开销,而且还导致设备处于不稳定状态, 在这种情况下,DVFS技术更为适用. (如变长解码、运动补偿等),然后对每个模块进行统 计分析并确定各模块所需计算量与各种参数之间的 依赖关系,总解码计算量为各模块计算量之和.这类 计 算 机 学 报 方法的典型代表包括新加坡国立大学Wang等人 ] 提出的直接将每个模块的计算复杂度分别建模为残 差系数个数、不同编码类型宏块的数目等编码参数 的线性模型.纽约大学Wang等人 提出的对每个 模块的基本操作单元进行分析,并将模块复杂度建 模为基本操作单元的个数与操作单元平均计算复杂 度之积.加州大学洛杉矶分校Schaar等人 提出的 利用混合高斯模型建立视频特征参数以及解码执行 时间的联合概率密度分布函数,并通过离线学习与 在线更新相结合的方法对上述概率密度函数进行动 态更新,从而适应视频内容的变化.南加州大学Kuo 等人[=7 提出的将宏块运动补偿(帧内预测)的计算复 杂度建模为Cache未命中次数、横向插值次数、纵向 插值次数和宏块内运动矢量个数这4个参数的线性 表达,并通过对多个测试序列进行统计分析,获得每 个参数的权值因子.上述方法能够对解码计算复杂 度进行非常精确的分析,估计结果准确.但是,为了 获得解码复杂度模型中的各种参数,必须在解码端 插人大量的分析语句,或者在传输码流中插入指示 复杂度的信息.这样不仅增加了数据传输量,还需要 对解码系统进行修改,系统运行时的复杂度增加,也 不利于模块化系统设计. 基于预测的方法是根据视频帧之间的相关性, 利用已解码帧的计算复杂度来估计后续帧的计算复 杂度.这类方法的重点和难点是如何挖掘出相邻帧 计算复杂度之间的相关性.一旦建立起这种相关性 就可以通过简单的预测来获取每一帧的计算量,在 线运行时开销小,适用于处理能力较弱的多媒体计 算平台.典型算法包括伊利诺伊大学香槟分校 Nahrstedt等人[8 提出的利用相邻时间段内的视频 帧解码计算复杂度的概率密度函数具有连续性和相 似性的特点,以组为单位对解码计算复杂度概率密 度函数进行动态更新,并将前面组的概率密度函数 近似作为待解码视频组的概率密度函数.之后利用 解码系统的软实时性特点,在满足解码率ID(即在截 止期之前被解码的视频帧占总视频帧的比率)的条 件下,在概率密度函数中寻找合适的计算复杂度C, 使得P(c≤C) .0,将C作为对待解码视频组中每一 帧的计算复杂度的预测.该算法虽然利用了解码计 算复杂度概率密度函数的相关性,但对视频帧计算 复杂度的估计是以组为单位进行,粒度较大,没有充 分挖掘出相邻视频帧之间的相关性,因此估计结果 并不精确. 我们提出了一种融合离线统计分析和在线预测 的解码计算复杂度估计方法 ,利用解码计算复杂 度与视频帧长之间的线性关系对其进行建模.在离 线阶段通过统计方法对模型系数变化规律进行分析 并对相邻帧模型系数之间的关系式进行求解;在线运 行时利用这一关系式动态更新模型系数并进行解码 计算复杂度估计.这一方法融合了统计分析和在线预 测两种手段,实验结果表明该算法能以非常小的系统 开销对解码计算复杂度进行精确估计.这部分工作很 好地利用了相邻帧模型系数的相关性,但对于相关性 的内在机理分析不够,建模和分析方法不足以推广至 其它多媒体应用程序. 2.2本文的研究工作及其意义 本文在已有基础上主要开展了如下工作: (1)根据多媒体系统输出与视频内容特征之间 的强依赖性以及相邻视频帧之间潜在的相关性,首 次引入信号系统分析理论,将多媒体解码系统定义 为状态驱动的系统.将系统输出响应(解码计算复杂 度)的求解过程转化为描述系统状态变量变迁轨迹 (即状态方程)的过程. (2)采用状态变量分析法对解码系统计算复杂 度进行求解,并利用状态变量化简法优化系统状态 空间.解码计算复杂度最终表征为以帧长作为输入, 系数(K,B)为状态变量的输出响应.状态变量K用 以表征压缩视频编码信息的变化(视频编码信息主 要指预测模式、运动矢量精度及运动矢量范围);状 态变量B表征压缩视频幅面的变化,当视频幅面相 同时,B用以表征被编码残差的变化. (3)以(K,B)为状态变量利用压缩视频帧被编 码残差和视频编码信息之问固有的量变与质变关系 (即相邻帧之间的变化首先通过残差表现;当变化过 大时,相邻帧的编码信息将发生明显变化),给出了 一种建立系统状态方程的方法,并将其最终定义为 表征视频内容变化程度的分段线性函数. (4)提出了对解码计算复杂度在线估计的一整 套完整解决方案,实现了对不同编码方式、不同幅 面、不同帧类型的视频帧解码计算复杂度在线估计, 并通过软仿真和硬仿真两种方式分别对H.264和 MPEG一4压缩码流进行测试.实验结果表明本方法 能很好地适应各种类型的压缩码流. 除上述对解码计算复杂度进行理论分析、建模 和动态估计等工作外,本文所提出的方法从另外两 个方面展现了对其它多媒体系统建模的意义,包括: (1)本文所提出的方法从本质上来说是回归了 解码系统的物理属性,从解码机理出发探讨影响解 1O期 田 婷等:视频解码计算复杂度的线性建模理论及在线预测方法 2051 码系统计算复杂度的因素.多媒体系统不同于其它 视频帧的解码计算复杂度与帧长正相关.以基于 TI TMS360DM642 DSP芯片的嵌入式解码平台为 例,采用遵循MPEG一4编码标准的XVID编码器 将CIF格式的测试序列Akiyo、Hall、Coastguard、 计算系统的重要特点是其具有丰富的语义层信息, 虽然在计算机中多媒体是以信号的形式被表示、存 储和传输的,但语义层信息却广泛地被用来对多媒 体信号处理过程进行优化.遗憾的是,多媒体信号 经过越复杂的处理,其语义层信息被利用的程度 就越低,以至于最后通常选择复杂数学模型对视 Crew、Foreman、Mobile在各种码率下(200 kbps、 400 kbps、500kbps、600kbps、800kbps)进行压缩,将 生成的压缩码流输入到上述嵌入式解码器中进行解 码,并记录每帧压缩视频的帧长及所需计算复杂度. 频信号进行分析和处理,语义层信息熵被人为增 大.本文所提出的解码计算复杂度估计方法是一 种寻找编解码系统中语义层信息传递的方法,即 编码参数为XVID编码器的默认参数配置,将最大 I帧间隔设置为32.采用的解码器是遵循MPEG~4 原始视频帧时域和空域的相关性是如何转化为压缩 视频帧之间的相关性.首先利用基于输入一输出的统 计分析法获得可能体现压缩域视频帧相关性的参 数,然后利用状态变量法从理论层面进行推导,确定 待选参数作为状态变量的语义层含义.最终落脚点 是从语义层分析这些包含物理含义的状态变量随视 频帧连续变化而动态变迁的过程,并将其转化为数 学形式进行求解,而不是单纯的依靠数学工具.这种 方法能够挖掘不同形式视频信号中所潜在的语义层 信息,保持语义层信息熵的稳定性,同时也为提高多 媒体系统分析效率和减少分析复杂度提供了新 思路. (2)本文所获得的状态方程虽然最终服务于解 码计算复杂度估计,但是由于它能够很好地表征压 缩视频内容、残差以及视频幅面的变化,故可以作为 独立系统服务于其它需要对视频运动复杂度以及纹 理复杂度等视频特性进行分析的多媒体应用中. 本文第3节通过实验对解码计算复杂度和压缩 视频帧长呈正相关这一现象进行描述,并采用统计 的方法验证将帧长与解码计算复杂度之间的正相关 性建模为线性关系的合理性;第4节阐述利用状态 变量分析法获得解码系统状态变量(K,B)物理含义 的原理以及系统状态方程的建立过程,并给出了利 用状态方程分别对I帧和P帧解码计算复杂度进行 动态估计的方法;第5节是本文的实验部分,将分别 对H.264和MPEG一4压缩码流进行在线解码复杂 度动态预测,本节还将详细展现在线预测过程中表 征视频特征的状态变量的变迁过程;最后,第6节是 结论. 3计算复杂度与帧长的线性模型 通过对运行在典型嵌入式平台上的解码任务计 算量与视频流帧长之间的关系进行实验分析,发现 编码标准的DIVX解码器①,利用TI公司提供的线 性汇编语言对解码器进行优化,没有任何算法上的 修改,所得结果不失一般性. 图1给出了码率为500 kbps时,Foreman和 Mobile序列每一帧的帧长(以字节为单位)和解码 计算量(以解码一帧所需要的时钟周期数cycle作 为度量)对比图.其它码率下,各测试序列的表现形 式与此类似. 垛 垛 视频帧序号 (a)Foreman 黑 视频帧序号 (b)Mobile 图1 500kbps测试序列每帧帧长与解码计算复杂度对比图 ①http://en.pudn.com/downloads270/sourcecode/multime— dia/etaill232774——en.htm 计 算 机 学 报 从图1中可以看出,解码计算复杂度与帧长的 走势一致,当帧长发生剧烈变化时,计算复杂度也发4 融合统计分析和状态变量分析法的 生明显变化_因此,可将解码计算复杂度(记为c)-b 解码复杂度在线动态预测 帧长(记为L)之间的关系建模为 C一_,(L) (1) 其中关系函数厂应体现帧长与计算复杂度之间的 正相关性.考虑到算法实现时的低复杂度要求,尝试 将_厂定义为线性函数,即 C(L)一K×L+B (2) 式(2)成立的充要条件是随机变量C和L线性相 关,即两者相关系数p等于1.以CIF格式的测试序 列Akiyo、Hall、Coastguard、Crew、Foreman、Mobile 在各种码率下(200 kbps、400 kbps、500 kbps、600 kb— ps、800kbps)采用XVID编码器编码并解码后所得 到的计算复杂度和帧长为样本,计算样本相关系数, 结果如图2所示. 码翠/kbps 图2各序列在不同码率时解码计算复杂度与帧长相关系数 在大多数情况下解码计算复杂度与帧长之间的 相关系数大于0。8,表明两者确实存在很强的线性 相关性;视频运动复杂度低(如Akiyo、Hall等序 列),两者相关系数大于0.95,可以认为解码计算复 杂度与帧长是线性相关的.因此将厂定义为线性函 数是合理的. 式(2)中函数系数(K,B)可通过文献E93所给出 的线性拟合方法离线分析获得,在线运行过程中便 可利用该拟合系数对解码计算复杂度进行估计.但 是由于系数(K,B)是随输入视频内容的变化而动态 变化的(图(2)中计算复杂度和帧长相关系数不等于 1可以说明这一点),静态系数无法反映视频内容特 征的变化.因此有必要挖掘系数(K,B)随视频内容 特征动态变化的规律,从而指导我们对解码计算复 杂度进行在线动态估计. 为了挖掘系数变化规律,需要从多媒体系统内 部机理进行分析.在信号系统分析法中,状态变量分 析法正是从系统内部机理进行分析,构建系统各节 点的状态变量与系统输入输出之间联系的方法.采 用状态变量分析法需要首先确定系统状态变量,然 后建立两个基本方程,即 输出方程:l,( )一Cx( )+De(,z),建立输出向 量l,和状态向量x以及输入向量e之间的联系. 状态方程:X(n+1):Ax(n)+Be(n),建立状 态向量x在输入e的作用下的变化. 考虑到视频具有天然的语义层信息,视频编 解码器运行的过程就是挖掘和解释视频运动特 点、纹理特点的过程,因此系统的输出是由视频特 征所驱动的;而且由于视频帧具有时域上的连续 性,其特征也具有时域上的相关性.因此可借鉴状 态变量分析法的思想,将帧长与计算量线性模型 中的模型系数(K,B)重新定义为表征视频内容特 征的状态变量,并通过分析状态变量的具体物理含 义来建立系统状态方程. 4.1视频解码系统状态方程的建立 4.1.1解码系统状态变量物理含义分析 根据第3节的分析,系统输出方程可以定义为 C( )=K( )×L( )+B( ),7/"为视频帧序号.每一 帧的帧长在压缩后已经确定,可以认为L(n)为常 量,解码系统状态变量为(K,B).本小节将从视频解 码器工作流程切入,对解码器计算复杂度各组成部 分进行分析,并通过状态变量化简,推导出以(K,B) 为状态变量的系统输出. 图3给出了一个典型的视频解码器的工作流 程.压缩码流输入到解码器,熵解码模块(ED)对输 入的码字进行解析,得到压缩域残差系数.重排序模 块(Reorder)对这些残差系数进行反zig—zag扫描, 获得按行列顺序排列的压缩域残差系数.反量化模 块和反变换模块(IQ&IT)则将上述重排序后的压 缩域系数进行反量化和反变换操作获得像素域的残 差信息.最后MC/IP模块利用块预测模式和运动矢 量,取得当前块的预测块,并将其与像素域残差信息 相加,得到最终重构后的块.因此,视频解码计算复 杂度C可表征为熵解码(C 。)、重排序(C )、反量 化和反变换(C Q&1 )以及MC/IP模块(C c/ )的计 10期 田 婷等:视频解码计算复杂度的线性建模理论及在线预测方法 2053 算复杂度之和.即 C—CED+CR o+CIQ&lT+CMC/IP (3) 处指示): 一(( D,CR o,CIQ&IT,CMc/1P). 换言之,4个模块的计算量作为系统节点处的 输出,可被定义为解码系统状态变量(如图3中虚线 为了获得系统状态方程,对每个状态变量进行独立 分析,获得其各自表达式. 图3视频解码器工作流程图 熵解码模块按照码流输入顺序对码字逐个进行 为C似。 与宏块头长度正相关,从视频帧的角度来说 就是与帧头长度正相关.将残差与参考块相加所需 计算复杂度对单个块来说是一样的,总计算量取决 处理,其解码复杂度与视频帧帧长呈正比关系_5j.设 L为码流长度,Co为解码每个码元所需要的平均计 算量,熵解码计算复杂度可以定义为 CED—Co×L (4) 于视频幅面.设视频帧头部信息长度为L 且帧头中 每个码元预取数据所需平均计算复杂度为C。,视频 所包含的分块数为N,每个块相加所需平均计算复 Reorder模块对固定大小的块(4×4或8×8) 进行反zig—zag扫描,由于反zig—zag扫描的步骤不 杂度为 ,MC/IP计算复杂度可定义为 CMc/1P—Cfet h+C l 一C3×Lh+C4×N (7) 变,因此消耗在每个块的计算复杂度基本不变. Reorder模块的计算量由数据块个数决定.在视频 综合式(3)至式(7),解码计算复杂度可以表征为 编码中,对于采用统一编码标准的视频帧,其数据块 大小固定,块数目由视频帧的幅面决定.因此Reor- der模块的计算量与视频帧帧长基本无关,主要取 决于视频帧幅面.设视频所包含的分块数为N,每 个固定大小块所需要的计算复杂度为C ,则 CR 0一Cl×N (5) … ㈣ IQ&IT模块对每个固定大小的压缩域系数块 考察状态变量K的组成部分, 为熵解码模 进行相同的加法和乘法操作,与Reorder模块类似, 其计算量与视频帧帧长基本无关,主要由视频帧幅 面决定.但是目前所采用的优化IDCT算法会利用 许多DCT系数为零这个特点对计算过程进行简 块解码每个码元所需要的平均计算量,实验表明 该系数的变化幅度不大 ].K值的大小主要取决于 C。×(L /L)的大小,其中c。是MC/IP模块中每个 码元预取数据所需平均计算复杂度,当视频采用复 杂的预测模式、运动矢量为分数精度、运动矢量范围 很大时C。的值较大.L /L则表征的是帧头占帧长 化,在这种情况下反变换的计算量与非零系数的个 数和出现位置有关.设视频所包含分块数为N,处 理每个块所需平均计算复杂度为C ,则 CIQ&1T—C2×N (6) 的比例,该值由率失真优化模型决定,总是试图在头 信息和残差信息所占长度之间取得最好的平衡.因 MC/IP模块的计算复杂度包含两部分:获取参 此其大小与码率分配策略以及视频内容密切相关, 考块所需计算量(c )以及将参考块与残差相加所 需计算量(C 。 ).取参考块的计算复杂度取决于块 当码率分配均匀时,如果视频内容变化较小,相邻帧 的帧头在帧长所占比例应基本保持不变,否则此部 分的值将由于视频的预测模式、运动矢量等编码信 息的变化而发生较大幅度的变化.因此K值的大小 类型、块预测模式以及运动矢量的精度,当预测模式 复杂、采用分数精度运动矢量时计算复杂度会急剧 增加.由于块类型、块预测模式及运动矢量都是宏块 头的组成部分,复杂度高的预测模式以及分数精度 运动矢量将导致宏块头消耗较多码字,因此可以认 由视频编码信息所决定的. 考察状态变量B的组成部分,C 、C。、C4分别为 Reorder、IQ&IT以及MC/IP模块中对固定大小块 计 算 机 学 报 所做操作的平均计算量,原则上讲是不变的,因此B 值主要取决于N的大小,即视频幅面.但是当压缩 块残差系数全部为零时,解码器将不对该块进行相 (3)当视频序列幅面相同时,随着被编码残差 数量的增加B值将增大.如Mobile序列,其纹理非 常复杂,导致残差量较大;Foreman序列,其视频运 动复杂度较高,残差量较大;对于Crew序列,由于 应的操作;当为零的系数很多时,IQ/IT模块也将采 取一定的快速算法,单个块的计算复杂度也将发生 变化,因此在这种情况下,残差的变化决定了B值的 其运动复杂度很高,在编码时用以表示宏块编码模 北 8 9 1 7 式、运动矢量等编码信息的码字较多,最终被编码的 ∞∞鼯盯 变化.但是必须指出的是,在给定正常码率的条件下, 不可能出现所有块系数为零的情况,决定B值的主因 仍然是视频幅面. 为了验证上述对状态变量(K,B)物理含义的分 析,将CIF和4CIF格式标准测试序列在不同码率 下进行压缩并解码,I帧间隔设为250,对获得的帧 长和计算量进行拟合,得到不同码率时各测试序列 的状态变量拟合值,实验结果如表1和表2所示. 表1 不同码率下CIF格式测试序列状态变量拟合值 视频序列— 号芝 _F 表2不同码率下4CIF格式测试序列状态变量拟合值 视频序列 City Crew Harbor Ice 视频序列—百 至景 罢 主 !詈 观察上述两表,可以发现: (1)随着视频序列运动复杂度增加,K值在不 断增大,Crew序列的运动复杂度最大,其K值明显 大于其它序列. (2)4CIF格式视频序列B的拟合值大约为CIF 格式视频序列拟合值的4倍,与两种视频幅面的比 值相等. 残差数据较少.实验表明,Crew序列被编码残差量 3 8∞盯 3 2 明显小于其它序列,在500 kbps时,其残差所占长 船¨ 度仅为帧长的53 ,同等测试条件下Mobile序列 这一比例为76 . 5 7 1弘 2 (4)随着码率增加,被编码残差数量增加,B值 ∞ n踮 呈增大的趋势. 8 ∞ 6 5 3 上述实验结果表明K确实主要受视频预测模 式、运动矢量的范围和精度的影响,而B基本与上 4 3 ∞ 5 8 述视频编码信息无关.在幅面相同条件下,被编码残 差数对B的影响较大;当视频幅面不同时,B的变 化非常大,此时K的变化并不明显.因此,K和B的 物理含义可以定义为: 状态变量K可以表征被编码视频编码信息变 化,其中视频编码信息主要指预测模式、运动矢量精 度及运动矢量范围. 状态变量B可以表征被编码视频幅面的变化, 当视频幅面相同时,B可以表征被编码残差的变化. 4.1.2解码系统状态方程的建立 状态方程用来表征系统状态变量在输入激励下 所产生的变化,在视频解码系统中就是建立相邻帧 状态变量(K,B)之间的联系.通过对K和B物理含 义的分析,可以将相邻帧状态变量的变化映射为编 码信息以及被编码残差的变化. 根据视频压缩原理,从相邻帧变化角度来说,编 码信息和被编码残差之间是质与量的关系,即相邻 帧之间的变化首先通过被编码残差的数量发生改变 而体现;当视频内容发生剧烈变化时,被编码残差数 量发生很大幅度变化,此时编码器率失真优化模块 和码率控制模块将通过改变编码信息来提高压缩视 频的率失真性能.因此K和B之间的关系也可以认 为是质与量的关系,以相邻帧视频内容的变化程度 作为衡量质变与量变的准则,则有 (1)相邻帧视频内容变化小,视频内容的差别 主要由被编码残差的数量的变化来体现.相邻帧K 值保持不变,B值发生变化. (2)相邻帧视频内容变化大,视频内容的差别 主要由视频编码信息的变化来体现.相邻帧K值变 化,B值保持不变. 田 婷等:视频解码计算复杂度的线性建模理论及在线预测方法 2055 采用数学形式对上述过程进行描述,则可以给 出一种以视频内容变化程度为条件的分段函数,对 状态方程进行求解.设前一帧(第i一1帧)的状态变 量为(KH,B ),通过该状态变量值预测得到当前 帧(第i帧)的解码计算量C ;解码后得到当前帧的 真实计算量为c肌 ,第i帧的状态变量为(K ,B ), 则当前帧的解码复杂度估计误差为 ㈤一C ,且 fC ===KH×L +B I C )一K ×L +B 当视频内容变化较小时,相邻帧状态变量应基 本相同,则当前帧的解码复杂度估计误差较小;而当 视频内容变化大时,相邻帧状态变量差别较大,当前 帧的解码复杂度估计误差较大.因此可用当前帧的 解码复杂度估计误差来表征视频内容变化程度,进 而将其作为选择状态方程的约束条件. 利用计算复杂度估计误差、视频内容变化以及 状态变量变化三者之间的映射关系,解码系统状态 方程可由式(9)、(10)给出. 状态方程1:当前帧解码复杂度估计误差在一 墨 定范围内,即△ ㈤一C 三三三△ ,则 一 < 【(9) J I B 一CR㈤一C +B 一1 状态方程2:当前帧解码复杂度估计误差超过 一定范围,即c刚)一c 三三三△ l lc ( )一c 三三=△ ,则 1l KB 一 R( 1— +K 4.2解码复杂度在线动态预测 利用状态方程对解码计算复杂度进行在线估 计.由于状态方程描述系统前后帧状态变量的变化 关系,而在压缩序列中除全I帧序列外,I帧一般独 立出现,其后续帧多为P帧和B帧,前后帧属性不 同,相关性无法通过状态方程体现.因此本文针对I 帧和P帧状态变量轨迹特性和在编码过程中的位 置属性不同,分别提出了两种预测方法.针对I帧主 要是采用统计的方法获得I帧状态变量的统计特 性,并利用其对解码复杂度进行预测;对于P帧则 是融合统计分析和状态方程进行动态预测.B帧从 编码原理上来说同样是采用帧间预测编码,其估计 过程与P帧类似,在此不单独讨论. 为了分析不同编码方式对视频状态变量的统计 特性以及相邻帧状态变量的变化趋势的影响,还将 对MPEG一4和H.264编码标准进行对比讨论. 4.2.1基于统计分析的I帧计算复杂度预测 表3和表4分别给出了CIF格式全I帧MPEG一4 压缩码流和H.264压缩码流在不同码率时拟合得 到的(K,B)值.可以发现对于MPEG-4压缩码流, 当视频内容、压缩码率发生变化时,状态变量(K,B) 值基本保持不变.而对于H.264压缩码流,当视频 内容、压缩码率发生变化时,K值发生明显变化,B 值有一定区别,但变化幅度并不明显. 表3不同码率下CIF格式全I帧MPEG-4压缩码流 状态变量拟合值 视频序列— } 嘉 视频序列 篡 点 表4不同码率下CIF格式全I帧H.264压缩码流 状态变量拟合值 视频序列 视频序列— —至 ! 由于状态变量K表征被编码视频运动信息的 变化,I帧只采用帧内预测.在MPEG一4视频编码标 准中只有两种方向的帧内预测,且计算复杂度基本 相同,状态变量K值将保持基本不变.对于H.264 编码标准,由于其采用9种4×4预测模式和4种 16×16预测模式,且每种模式计算复杂度区别较 大,同时每种预测模式所需码长也不同,因此随着视 频纹理的变化K值将发生明显变化. 对于状态变量B,当视频幅面相同时,B的值与 墨计 算 机 学 报 被编码残差数量变化相关,MPEG一4压缩码流中各 过4 .上述规律可以应用至H.264压缩码流. 种帧内预测模式消耗的码字相同,在同样码率的条 件下被编码残差数量相近,B值保持不变.在不同码 利用规律1和规律2,对I帧解码计算复杂度估 计可以分为离线分析和在线预测两个部分.离线分 率条件下,随着码率的增加,B值会增加,但相对于 析得到针对某一幅面的压缩码流的状态变量统计 B值的大小来说增幅较小.而对于H.264压缩序 列,虽然各种预测模式消耗码字不等,但由于所占码 字较少,残差量变化并不明显,因此B值有一定变 化,但其主导因素还是视频幅面. 值,在线运行时根据接收视频与离线分析所使用 的视频的幅面的比值对状态变量统计值进行调 测.因此有算法1. 算法1. I帧计算复杂度预测. 整,调整后的值将用来对I帧解码复杂度进行预 通过以上分析可以发现,虽然MPEG一4压缩码 ∞流和H.264压缩码流的状态变量统计特性随编码 方式的不同而发生改变,但物理含义始终保持不变. 对于在码流中单独出现的I帧而言,由于它无法利 用连续帧之问的相关性进行状态变量的更新,这种 物理含义的一致性就显得尤为重要.通过分析状态 变量所表征的压缩码流特征,了解影响状态变量变 化的主要因素,为利用 帧状态变量的统计特征值 提供了理论支持.更确切的说,就是将状态变量 (K,B)的物理含义与表3、表4中状态变量的统计 特性相结合,可得到: 规律1. 当视频幅面一定时,随着视频内容、 压缩码率的变化,状态变量(K,B)值基本保持不变. 对于不同幅面的视频,表5给出了4CIF格式 全I帧MPEG一4压缩码流在不同码率时拟合得到 的(K,B)值,将它与表3对比,可以发现: 规律2. 当视频幅面变化时,状态变量K的值 基本不变,而状态变量B的值发生变化;且对不同 幅面的视频,其状态变量B的比值约等于幅面的 比值. 表5不同码率下4CIF格式全I帧MPEG-4压缩码流 状态变量拟合值 视频序列__ 视频序列_ 至 曩 ! 需要指出的是,虽然H.264压缩码流K值的 变化并不满足上述变化规律,但是由于I帧作为关 键帧,其在码流中出现的频率很低,预测误差对系统 整体性能的影响并不大.而且通过后续实验证明,在 确定了B值的基础上,I帧的平均预测误差也不超 输人:压缩视频流中的I帧及其帧长 输出:输入的I帧解码计算复杂度估计值 猢 1.离线分析得到某种幅面视频状态变量统计值: 1.1.选择与解码器所采用的压缩标准一致的编码器, 采用此编码器将某种幅面大小(记为s )的标准测试码流以 全I帧形式在不同码率下进行编码; 1.2.将压缩码流进行解码,并获取解码每一帧的计算 复杂度及压缩帧帧长,记为(C ,L ); 昭M1.3.以帧长为自变量,解码计算复杂度为因变量对上 述生成的(C ,L )利用最小二乘法进行线性拟合,获得I帧 状态变量统计值,记为(K。,B-). 2.在线预测I帧的计算复杂度: 2.1.初始化状态变量值,令(KI(0),Bl(。))一(Kl,B。); 2.2.计算接收视频幅面是否发生改变,如改变,则计算 接收视频的幅面Sz与步1中所使用的视频幅面S 之比,即 r=S /s ,根据r对状态变量值进行比例缩放,即(K ,B ): (KI(。),rXBI(。)).否则保持(KI,BI)不变; 2.3.读取当前帧帧长L,利用公式C--K。×L+B 估算 所需解码计算复杂度. 4.2.2融合统计分析和状态方程的P帧计算复杂 度动态预测 虽然MPEG一4与H.264标准在预测模式、运 动矢量精度、运动矢量范围等编码工具上有所区别, 但是它们都利用相邻帧之间的相关性进行状态方程 更新,因此两类码流中对于P帧的解码复杂度预测 方法类似.图4给出了对P帧解码计算复杂度进行 预测的框图. ……警笪 ……: 图4解码计算复杂度估计框图 们渤1o期 田 婷等:视频解码计算复杂度的线性建模理论及在线预测方法 2057 在解码视频帧之前,状态变量更新模块将更新 后的状态变量输入至解码计算复杂度在线预测模 块.预测模块结合待解码帧的帧长,对解码计算复杂 度进行预测.操作系统根据预测得到的计算复杂度 进行DVFS调节之后,解码器对当前帧进行解码并 记录其真实计算复杂度,将其输入至状态变量更新 模块.更新模块计算当前帧真实计算复杂度和预测 值之间的差值,并将其与迭代控制阈值进行比较,选 择4.1.2节中所给出的状态方程(9)或者(10)对状 态变量进行动态更新,更新后的状态变量将指导下 一帧的解码计算复杂度预测.P帧计算复杂度动态 预测算法如算法2所示. 算法2.P帧计算复杂度动态预测. 输入:压缩视频流中的P帧及其帧长 输出:输入的P帧解码计算复杂度估计值 1.离线分析得到系统状态变量迭代初值和迭代控制 阈值: 1.1.确定迭代控制阈值(△ ,△z),本算法是通过确定状 态变量B的范围(B…,B…)来确定(△ ,△z); 1.2.确定迭代初值(K ,B ). 2.在线动态预测输入P帧的计算复杂度: 2.1.初始化系统状态变量值及迭代控制阈值,令 (KP(。),BP(。))一(Kp,Bp),B…(。)一B…,B i (。)一B i ; 2.2.计算接收视频幅面是否发生改变,如改变,则计算 接收视频的幅面S。与步1中所使用的视频幅面S 之比,即 r—S /S .根据r对状态变量值进行比例缩放,即(K ,B )一 (KP(。),r×Bp(。)),(B咖一r×B…(。),Bm 一r×B (。)).否则 保持系统状态变量值及迭代控制阈值不变; 2.3.读取当前帧帧长L,直接利用公式c—K ×L+ BP估算其所需解码计算复杂度; 2.4.对当前帧进行解码,解码后得到真实计算量 以 及当前帧解码复杂度估计误差△一 —C; 2.5.计算当前帧的解码复杂度估计误差的阚值Ea , △ ],△ 一B~一B ,△ 一B…一B ,判断估计误差所处阈值 范围,如果△ △ △ ,则按式(9)更新BP为BP—B +△;否 则按式(10)更新K 为K =a/L+K ,将更新后的(K ,B ) 用于下一个P帧解码计算复杂度预测. 由于篇幅的限制,迭代控制阈值(△ ,△。)以及 迭代初值(K ,B )的计算方法没有详述,具体方法 可参看作者前期工作 ]. 5实验结果与分析 采用基于统计的解码计算复杂度预测算法 (Statistical Analysis based Prediction,SP)以及融 合统计分析和状态方程的解码复杂度预测算法 (Statistics merged State Variable Analysis,SS VA) 分别对I帧和P帧的解码复杂度进行估计.由于本 算法在实际运行阶段利用了相邻帧状态变量之间的 相关性进行解码计算复杂度预估,属于基于预测算 法,本节将给出与伊利诺伊大学香槟分校Nahrstedt 等人_8 提出的CDP(Cumulative Distribution based Prediction)算法的对比. 为了验证算法的有效性,实验分别选取了采用 MPEG一4和H.264两种视频编码标准的解码器,在 不同平台上进行测试.其中MPEG一4解码器运行 在基于TI TM¥32ODM642 DSP芯片的嵌入式开发 板上,采用DIVX解码器.H.264解码器运行在 SimpleScalar仿真器上 ,仿真器所仿真的硬件环 境为基于X86架构的通用PC,解码器源码选取开 源代码P264.如文献[8]所述,CDP算法包含3个控 制参数:视频帧解码率p,每组视频帧的数目叫和 计算复杂度分组问隔g,在本实验中,将其分别设置 为0.96,50帧和10000个时钟周期. 5.1 基于统计分析的I帧计算复杂度预测结果 5.1.1 MPEG一4压缩码流I帧预测结果 利用4.2.1节中所提出的算法1,对I帧解码 复杂度进行估计.首先选取Akiyo、Coastguard、 Foreman和Mobile等CIF格式的视频序列作为 测试序列,采用MPEG一4编码标准将其在不同码 率下(800 kbps、1000 kbps、1500 kbps、2000 kbps和 2500 kbps)以全I帧形式进行压缩并解码,记录每一 帧视频的帧长和解码计算复杂度,记为(C ,L ).以 帧长为自变量,解码计算复杂度为因变量,利用最小 二乘法对得到的(C ,L )进行线性拟合,得到状态 变量(K,B)值为(215.51,6.4108×10。). 利用拟合得到的状态变量值预测CIF格式 MPEG一4压缩码流的解码计算复杂度.将测试视频 (Akiyo、Hall、Coastguard、CFew、Foreman和Mo— bile)在不同码率下(800kbps、1000kbps、1500kbps、 2000kbps和2500kbps)按全I帧进行压缩,并将其 输入到解码器进行解码复杂度动态预测.图5给出 了预测误差的概率密度分布. 如图5所示,采用SP所得到的估计误差的概率 密度分布呈正态分布,且平均估计误差为0.47 ,近 89 9/6视频帧预测误差范围在1 9/5以内,最大预测误 差为2.94 ,SP方法精确度高于CDP方法.而且 采用SP方法的在线运行开销非常小,计算复杂度 可以通过一次乘法以及一次加法预测得到.在本实 验环境下,SP在线运行开销仅为54 cycles/帧. 计 算 机 学 报 测误差在1 以内,近99 的视频帧预测结果在 /sP 2 以内,最大预测误差为2.32 .这一结果表明规 律2是正确的,另一方面也暗示了本算法的鲁棒性, 虽然SP和SPSimple状态变量值稍有不同,但两者 都可以达到比较好的预测效果. 5.1.2 H.264压缩码流I帧预测结果 /CDP 选取CIF格式的视频序列(Akiyo、Coastguard、 Crew、Mobile)作为测试序列,采用H.264编码标准 将其在不同码率下(500kbps、800kbps、1000 kbps、 1500kbps、2000kbps)以全I帧形式压缩并解码,利 I r 图5 CIF格式视频序列预测结果 更进一步的,利用CIF格式视频序列所得到的 状态变量值动态预测4CIF格式视频序列解码计算 复杂度.将测试序列(Ice、Harbor、Crew和City)在 不同码率下(2000 kbps、4000 kbps、5000 kbps、6000 kbps和8000 kbps)按全I帧形式压缩,并将其输入 到解码器中进行解码复杂度动态预测.由于在线输 入视频幅面(4CIF)与离线分析视频所采用的幅面 (CIF)不同,按照4.2.1节中所提出的规律2,根据 视频幅面的比值将状态变量(K,B)值修正为 (215.51,2.5643×10 ).为了评价规律2的有效 性,本实验还给出了利用4CIF幅面视频进行离线 拟合分析所得到的状态变量值:(218.25,2.5421× 10 ). 图6给出了采用不同预测方法所得到的预测误 差的概率密度分布.其中将采用修正后的CIF格式 视频序列拟合得到的状态变量值进行预测的方法记 为SPSimple,采用4CIF幅面视频直接离线拟合得 到的状态变量值进行预测的方法记为SP. 图6 4CIF格式视频序列预测结果 实验结果表明,SP方法预测结果仍然很准确, 这再次验证了4.2.1节中所提到的规律1,即对同 一幅面视频序列,其状态空间基本不变这一规律是 正确的.虽然SPSimple的预测结果没有SP精确, 但是也有不错的预测结果.近69.79 视频帧的预 用最小二乘法进行线性拟合得到状态变量(K,B)值 为(222.6,1.4749×10 ). 利用拟合得到的状态变量值对CIF格式H.264 压缩码流的解码计算复杂度进行预测.将测试 视频(Akiyo、Hall、Coastguard、Crew、Foreman和 Mobile)在不同码率下(500kbps、800kbps、1000kbps、 1500kbps、2000kbps)按全I帧进行压缩,并将其输 入到解码器进行解码复杂度动态预测.表6给出了 不同序列在不同码率时的预测误差绝对值的均值. 表6采用H.264编码标准的全I帧测试序列在 不同码率时预测误差绝对值均值 实验结果表明,虽然H.264编码标准中的帧内 预测模式较MPEG一4编码标准复杂,状态变量空间 有小幅度变化,但在确定了状态变量(K,B)数量级 的基础上,仍能保持较高精度,所有测试序列估计误 差均值都保持在4 以内. 5.2融合统计分析和状态方程的P帧解码计算复 杂度预测结果 5.2.1 MPEG一4压缩码流P帧在线预测结果 利用4.2.2节所述的算法对P帧解码复杂度进 行估计.选取CIF格式测试序列Akiyo、Hall、 Coastguard、Foreman、Mobile、Crew作为测试序列, 并按照文献[9]中所述方法获取迭代控制阈值及迭 代初值:Al—I.7×10 一B( 一1),△2—2.4×10 一 B(r.1);(KP,BP)一(325.58,2.3171×10 ). 利用上述初值对MPEG一4压缩码流进行解码 计算复杂度在线估计.表7给出了SSVA和CDP的 平均绝对估计误差. 田 婷等:视频解码计算复杂度的线性建模理论及在线预测方法 2059 表7不同码率时P帧预测误差绝对值的均值 测非常平滑.对6个序列综合计算,估计误差在5 以内的比例为84.6 9/6,误差在1O 以内的比例为 96.6 ,SSVA精确度较高. 更进一步的,利用CIF格式视频序列所得到的 状态变量的值动态预测4CIF格式视频序列解码计 算复杂度.将测试序列(Ice、Harbor、Crew和City) 在不同码率下(800kbps、1000kbps、1500kbps、 2000kbps和2500kbps)压缩,并将其输入到解码器 中进行解码复杂度动态预测.由于在线输入视频幅 面(4CIF)与离线分析视频所采用的幅面(CIF)不 ∞ 加 同,根据视频幅面的比值将状态变量迭代初值修正 为(325.58,9.2684×10 ).为了评估该迭代初值的 实验结果表明ssVA适用于不同内容、不同码 率的压缩视频,特别是对于运动复杂度中等、纹理复 杂度中等的视频序列(如Hall、Coastguard和Mo— 有效性,本实验还给出了利用4CIF幅面视频进行 离线拟合分析所得到的迭代初值(344.24,8.6397× 10 )进行在线估计所得到的估计结果. 实验结果如表8所示,采用CIF序列初值得到 的估计初值记为EST,D1序列直接拟合得到初值 记为FIT.从表8中可以看出,两者效果类似,精确 bile序列),平均预测误差一般都在3 以内.对于运 动非常剧烈的视频(如Crew序列),由于相邻帧之 间的相关性较弱,导致相邻帧状态变量相似性减小, 预测结果较差,但其平均估计误差仍然小于6 . 度都比较高.这说明迭代初值对本文所提出的算法 影响并不大,只要确定状态变量(K,B)的数量量级, 在线预测算法会迅速地根据估计误差调整状态变量 K或者B,达到快速收敛的效果. 表8 MPEG-4用CIF序列估计D1序列拟合初值(EST)以及 用D1序列拟合选取初值(FIT)的预测绝对误差均值 图7给出了各序列预测误差概率密度分布,从 图中可以看出SSVA算法估计误差呈正态分布,且 估计误差均值和方差都接近0,证明SSVA算法预 估计误差 (b)HaU l 对算法在线运行复杂度进行分析,一旦通过离 线拟合确定了迭代控制阈值和状态变量迭代初值, 在线运行的过程中只需要通过一次加法和一次乘法 估计误差 (c)Coastguard 40 便可获得计算复杂度预测值,而状态变量的修正过 程也只需两次加法和一次乘法.在本实验所用的 DSP环境下,算法的在线运行开销为103 cycles/帧. 蓦30 羹2o 蟋 i 5.2.2 H.264压缩码流P帧在线预测结果 采用同MPEG-4压缩码流计算复杂度估计类 似的方法,选取CIF格式测试序列Akiyo、Hall、 Coastguard、Foreman、Mobile、Crew作为测试序列, 并按照文献E9]中所述方法获取迭代控制阈值及迭 代初值A1—9.5×10 一B( 一1),A2—1.26×10 一 嚣10 估计误差 (e)F0reman 估计误差 (f)Mobile 图7 预测误差概率密度分布 计 算 机 学 报 B(一1);(KP,BP)=(1109.99,1.O61×10 ).将CIF 格式测试序列(Ice、Harbor、Crew和City)在不同码 率下(200 kbps、400 kbps、500 kbps、600 kbps和 800 kbps)进行压缩,对用H.264编码标准进行编码 5.2.3解码系统状态变量轨迹分析 为了突出本文所提出的状态变量的物理含义, 本节将给出采用状态方程对状态变量进行求解后所 得到的每一帧视频对应的状态变量值.图8给出了 在码率为500 kbps时,采用MPEG一4编码标准进行 压缩的各测试序列的状态变量在状态空间的轨迹. 从图8可以看出,当视频运动简单,没有突变 时,表征视频预测模式、运动矢量复杂度的状态变量 的测试序列进行在线解码复杂度动态预测,实验结 果如表9所示. 表9采用H.264编码标准的不同视频测试序列在 不同码率下的预测误差绝对值均值 K值的变化幅度较小,如Akiyo、Hall、Mobile序 列,K值变化在30以内;当视频出现突变时,如 Coastguard序列在80帧附近发生一次镜头切换,K 值发生大幅度跳跃;Foreman序列从180帧到230 帧发生了数次镜头切换,K值也发生了几次跳变; 对于Crew序列,由于全序列的运动非常复杂,K值 从表9可以看出,本文提出的P帧解码复杂度 动态预测算法对H.264编码标准也非常有效,在线 估计误差不超过2 .虽然MPEG一4和H.264采用 的切换也是非常明显的. 当视频运动趋于稳定后,K值也基本稳定.之 后,解码器将在某一K值平面上通过更新B值(即 残差的变化)寻求最优位置,表现在图形中就是B 了不同的编码方式,但是本算法是从解码系统机理 出发,利用相邻帧之间的相关性来揭示系统状态变 量随视频内容变化的规律;是从物理层面引出的一 种解析方法,满足解码器运行规律,因此预测效果非 常好.对于采用其它编码方式进行编码的压缩码流 (如基于感兴趣区域编码的ROI_】妇),只要其采用基 值在某一个K值平面中震荡.这也进一步体现了编 码信息与被编码残差之间质与量的关系. 值得注意的是,在图8中Mobile、Akiyo序列的 K值平面在开始处发生过大幅度切换,这主要是因 为迭代初值所表征的视频内容的特征与当前序列的 特征不一致所导致,解码器必须通过更新K值平面 的方法迅速逼近最优位置.一旦逼近最优状态平面, 于MC—DCT混合编码框架,相邻帧之问状态空间就 具有极强的相关性,就可以利用本文所提出的状态 空间的变化规律进行求解,算法普适性强. 将通过小幅调整B的方法精细搜索最优位置. 3 删 。 删 羹s 3 咖 怕 300 300 图8 CIF格式测试序列状态空间变化图 1O期 田 婷等:视频解码计算复杂度的线性建模理论及在线预测方法 2O61 6 结 论 本文给出了一种基于状态变量法的视频流解码 计算复杂度估计方法.首先通过统计分析,对解码计 算复杂度与帧长之间的关系进行建模,得到解码计 算复杂度与帧长之间的线性关系,并分析得出模型 系数作为状态变量所包含的物理含义,从而将在线 模型系数求解问题转化为对系统状态变量进行更新 的问题. 通过统计分析,发现对于I帧,其状态变量值仅 与视频幅面相关,可通过离线分析方法获得状态变 量统计均值,在线运行过程中直接利用该值对解码 计算复杂度进行估计.对于P帧,则利用相邻视频 帧编码信息及残差的变化特点,结合状态变量所表 征的物理含义,将相邻视频帧的相关性转化为状态 变量随视频内容变化而变化的规律,并以预测误差 作为反馈动态调整相邻P帧状态变量值,最终快速 高效地预测解码计算复杂度. 本方法采用简单的线性模型对解码复杂度进行 估计,系统输入(帧长)可由压缩码流直接获得,解码 器设计流程简单、码流兼容性好;能对系统状态变量 进行动态更新,及时反映视频内容变化,估计结果精 确度高;进行在线更新时仅需利用上一次更新结果 做简单运算,系统运行时开销小,特别适合资源受限 的嵌入式系统. 最后,本文所提出的状态变量法利用视频的 语义层信息,通过挖掘状态的语义层含义直接构 建系统状态方程,摒弃了复杂的数学建模.所得到 的状态方程直接反映了多媒体解码系统固有的物 理特性,因此有非常好的效果.这一建模方法为对 其它多媒体系统进行理论分析和建模提供了新 思路. TIAN"ring,born in 1985,Ph.D. candidate.Her main research interests include cross-一layer design for embedded multimedia system,mulitmedia streaming. 参 考 文 献 [1] Benini I 。Micheli G De.System-level power optimization: Techniques and tools.ACM Transactions on Design Auto— mation of Electronic Systems,2000,5(2):115—192 E23 I i K,Kumpf R,Horton P,Anderson T.A quantitative analysis cf disk drive power management in portable(omput ers//Proceeding 0f USENIX Wir ter Technical Conference. San Francisco,USA,l994:279—291 [33 Ishihara T.Yasuura H.Voltage scheduhng Froblem for dy-一 namica1ly variable voltage pr0cessors//Procee djng of the 1998 Inte,national Symposium on L,cw Power E ̄lectronics and Design.Monterey,USA,1998:197 202 [43 Huang Y C,Tran A.V,Wang Y.A workload pr ̄dictino model for decoding mpeg video and its application to work一 】.oad--scalable transcoding//Pr0ceeding 0f the 15th Interna tional Conference on Multimedia.Augsburg,Germany, 2007:952-961 [53 /Via Z,Hu H,Wang Y.On complexity modeling cf H.264/ AVC video decoding and its application for energy efficient decoding.IEEE T'ransactions on M[ukimedia,2011,13(6): 124ff一1255 [6] Kontorinis N,Andreopoulos Y,van der Schaar M.Statisti.一 cal framework for video decoding complexity modeling and prediction.IEEE T"ransactions on C ̄ircuits and Systems for Video Technology,2009,19(7):1000—1013 [7] I ee S W,Kuo C-C J.Complexity modeling of.,patial and temporal compensations in H.264/AVC decoding.IEEE Transactions on Circuits and Systems for Video Technology, 2O1O。2O(5):706—720 [8] Yuan W,Nabrstedt K.Energy-efficient soft reab itme CPU Scheduhng for Mcbile Multimedia Systems//Proceedings of the 1 9th A CM Symposium on Operating Systems Principles. New Y0rk,USA,2003:149—163 [9] Wiarl T。Yu S S,Guo H X.Linear model-一based adaptive pie— diction for video decoding complexity//Proceeding of 201 1 IEEE International O;onference cn Muhimedia&Expo.Bar celona,Spain,2011:1—6 [1O] Austin T,I ,arson E,Ernst D.SimpleScalar:An infrastruc.一 ture for computer system modeling.IEEE Computer,2002, 35(2):59-67 [11] Lu S P,Zhang S H.Saliency-based fideltiy adaptation pre— processing for video coding.Journal of Computer Science and Technology,2011,26(1):195—202 YU Sheng.-Sheng,born in 1 944,professor,Ph.13. su— pervisor..His main research interests include computer stor— age systems,multimedia technologies. GUO Hong‘Xing,born in 1971,Ph.D.,associate pro— fessor,.His main research interests include embedded compu— ting,multimedia networking.. SU Shu-Guang,born in 1975,Ph.D.,lecture ̄.His m ain research interests include video coding and multimedia communications,embedded system and middleware. 2062 计 算 机 学 报 2O12往 Background This work is supported by the National Natural Science Foundation of China(Grant Nos.6l173044,60873029)and the Fundamental Research Funds for the Central Universi— ties.The main purpose is providing high—performance and energy-efficient multimedia technologies over a variety of hardware and software platforms. Energy-efficient optimization has been becoming an in— creasingly important aspect in the design of those highly conl— plicated multimedia systems,especially for battery—limited mobile devices.Scalability of hardware components provides us a new dimension to achieve this goa1.Since the computa— tional complexity and storage demand of the multimedia sys— tem vary with the video content,hardware platforms can ad— j ust their resources according to the demand of the multime— dia applications during runtime process.The effectiveness of such methods depends on the prediction accuracy of computa— tional complexity and storage demand. Video decoding is one of the most popular multimedia applications on mobile devices.Two kinds of methods for video decoding complexity prediction have been evolved dur— ing the past years.The first is analysis—based modeling, which works in a fine granularity manner and the prediction results are accurate.However,fine analysis causes redun~ dancy in either video decoding process or compressed bitstre— arns,which leads to low efficiency.The second is prediction— based method,which utilizes the correlation between the neighboring frames.Although the prediction overload can be low in terms of the coarse grained feed back control strategy, desirable prediction results are hard to achieve since it is dif— ficuh to exploit the correlation between decoding complexities of the neighboring frames. In this paper,we utilize the linear relationship between frame length and decoding complexity and consider the deco— ding system as a state—driven system,where the state means the characteristics of video content.Unlike those complicated mathematical modeling methods,our method utilizes the in trinsic semantic characteristic of video content and exploits the state variation patterns from the semantic layer.Then the state function is derived naturally with the state variation pat— tern and applied to update the state trajectory and perform online decoding complexity predicting for both MPEG一4 and H.264 compressed stream.The experimental results indicate our method can achieve good prediction results for bitstreams over a wide range of video contents and coding standards. It s very simple and effective. Our past work was published at IEEE ICME 2011 and nominated as the best paper candidate.We will continue our work on design of energy—efficient multimedia systems.