基于高清编码的自适应Slice划分算法

计　算　机　工　程ComputerEngineering

文章编号:1000—3428(2010)23—0226—03　　　文献标识码:A

2010年12月

December2010

中图分类号:TP311.52

基于高清编码的自适应Slice划分算法

冯飞龙,　陈耀武

(浙江大学数字技术及仪器研究所,杭州310027)

摘　要:对于多核高清视频实时编码系统,提出一种自适应Slice划分算法。该算法基于码率控制和熵编码复杂度模型,通过Intra预测得到当前编码图像的纹理复杂度分布,预测编码图像的计算复杂度分布,通过自适应Slice划分实现多核间计算复杂度均匀分配,从而提高多核并行编码效率。实验结果表明,与固定宏块数的Slice划分算法相比,该算法能更有效地提高并行加速比。关键词:多核;并行编码;Slice划分;H.2标准

AdaptiveSlicePartitionAlgorithmBasedonHighDefinitionEncoding

FENGFei-long,　CHENYao-wu

(InstituteofAdvancedDigitalTechnologyandInstrumentation,ZhejiangUniversity,Hangzhou310027,China)

【Abstract】Aimingathighdefinitionvideoreal-timeencodingbasedonmulti-coresystem,anadaptiveslicepartitionalgorithmisproposed.Basedonratecontrolandentropyencodingcomplexitymodel,thealgorithmperformsintra-predictionforcurrentframetogetthedistributionoftexturecomplexity,thenpredictsthedistributionofcomputationalcomplexity,andallocatesresourcesevenlyinmulti-coresystemthroughadaptiveslicepartition.Experimentalresultsprovethisalgorithmsignificantlyimprovestheparallelspeedupcomparedtofixedmacroblockslicepartition.【Keywords】multi-core;parallelencoding;Slicepartition;H.2standard

1　概述

随着视频应用的发展和处理器技术的进步,高复杂度高

压缩率的H.2算法取得了广泛应用。多核处理器技术的发展给并行算法提供了物理平台,多核并行算法成了实时编解码设计的关键。目前基于H.2的多核并行编码算法有多种,根据并行级别可以分为GOP级、帧级、Slice级和宏块级,其中Slice级并行算法因为实现简单,并行效果较好,应用最为广泛,但Slice级并行算法会因为图像内容差异引起每个核的计算复杂度分配不均匀,降低了并行效率[1]。

针对Slice级并行算法计算复杂度分配不均匀的问题,文献[2]提出一种提前判断宏块编码模式,从而判断宏块计算复杂度,进而进行Slice划分的算法,但该算法并不适用于高清视频实时编码系统,因为高清视频实时编码系统在权衡编码效率与图像质量后,常只进行大块编码(16×16、16×8、8×16),不做8×8块及其子块预测[3]。

本文在分析已有并行算法的基础上,针对多核高清视频实时编码系统,提出一种基于码率控制和熵编码复杂度模型的自适应Slice划分算法。实验结果表明,该算法能有效提高并行加速比。

到的宏块数为:

,i=0,1,…,S-1(1)

S-i

其中,N为一帧宏块总数;S为一帧内的Slice数;Numi为每个Slice的宏块数。采用固定宏块数的Slice划分算法后,每个Slice都能分到基本相同的宏块数,但由于每个宏块的图像内容不同,会造成宏块编码时间的差异,从而使多核间计算复杂度分配不均匀。2.2　基于快速模式选择的Slice划分算法

文献[2]提出的基于快速模式选择的自适应Slice划分算法,在JM9.6上取得了较好的效果。该算法首先将宏块分割尺寸分为大块模式(16×16或Skip)和小块模式(其他块尺寸),然后记录每个宏块的块尺寸、持续的帧数以及MV信息,从而预测当前块的块尺寸。因为JM模型的模式分析模块占最大的比重,RDO关闭时计算复杂度占到整个宏块编码的85%,所以它通过预测宏块编码模式即可确定计算复杂度分布,从而进行均匀的Slice划分。

2.3　高清视频实时编码系统及现有算法分析

在高清视频实时编码系统中,以8Mb/s码率测试6个500帧的1080P30高清序列,得到编码模型中各个模块的计算复杂度比重如表1所示。其中,模式分析包含Inter预测和Intra预测;核心计算包含DCT/IDCT和Q/IQ子模块;CAVLC和CABAC指不同的熵编码模式。由于高清视频实

作者简介:冯飞龙(1984-),男,硕士研究生,主研方向:基于嵌入式平台的多媒体应用;陈耀武,教授、博士生导师

收稿日期:2010-02-25　　E-mail:feilongfeng@gmail.com

Numi=

N-∑Numk

k=0

i-1

2　现有Slice划分算法

基于Slice的并行编码算法就是将H.2每帧图像划分

为多个Slice,因为同一帧的各个Slice之间没有数据依赖,以此为基础可以实现并行编码[4]。目前的Slice划分算法主要有固定宏块数划分和自适应划分2种。2.1　固定宏块数Slice划分算法

JM使用的是固定宏块数Slice划分算法,每个Slice所分—226—

时编码系统通常只进行大块编码,因此模式分析模块的计算复杂度较为固定。另外,由于核心计算和去块滤波的计算复杂度也比较固定,因此宏块计算复杂度波动主要集中在熵编码模块。

表1　H.2高清视频实时编码系统计算复杂度分布(%)

模式分析

CAVLCCABAC

35.125.1

核心计算25.818.6

熵编码18.841.2

去块滤波20.314.7

当前编码图像的Intra预测,而编码的后续步骤将在Slice划

分后进行。因为Intra宏块解码时参考块由未滤波的相邻重建宏块得出,所以通用编码器在编码时也以重建数据做参考。而由于纹理复杂度模块只完成整帧Intra预测,没有生成重建数据,又因为重建数据跟原始像素接近,所以编码时参考数据可以使用原始像素,对图像质量基本没有影响。由于每个宏块的IP模块计算复杂度相同,可以给每个处理器分配相同的宏块数来完成该模块,即可产生代表纹理复杂度的IntraSAD值。

3.3　模式修正

视频编码中由于时域相关性,前向帧的宏块信息可以用于当前帧参考,而在高清视频实时编码系统中块分割较大、宏块模式较少,因此可以通过直接映射前向帧宏块模式来实现快速模式预测。码率控制模块需要宏块SAD,可以结合宏块预测模式来预测宏块SAD。当预测模式为Skip时,宏块预测SAD为0;当预测模式为Intra时,宏块预测SAD使用(纹理复杂度模块结果(IntraSAD);当预测模式为Inter时,宏块预测SAD需使用前向Inter结果(PreInterSAD)和前向Intra结果(PreIntraSAD)对IntraSAD进行修正。

IntraSAD

SAD=IntraSAD

×PreInterSAD

PreIntraSAD0

ifmode=Intraifmode=Interifmode=Skip

(2)

　　固定宏块数的Slice划分算法可以用于高清视频实时编码系统,但是该算法只是按宏块数分配,没有考虑计算复杂

度,所以每个处理器的编码时间有较大差异。因为要编完一帧所有Slice后才能进行下一帧编码,所以固定宏块数的Slice划分算法会有核间等待消耗。文献[2]算法不适用于高清视频实时编码系统,因为在高清视频实时编码系统中,模式分析模块的计算复杂度基本不变,而该算法却是基于模式分析模块的复杂度预测,所以在高清视频实时编码系统中该算法无法实现。

在高清视频实时编码系统中,计算复杂度波动主要集中在熵编码模块,所以针对高清视频实时编码系统,必须通过预测熵编码模块计算复杂度分布才能进行均匀的Slice划分,提高并行加速比。

3　本文算法

基于上文分析,针对多核高清视频实时编码系统,本文提出了基于码率控制和熵编码复杂度模型的自适应Slice划分算法。

3.1　整体架构

由于熵编码复杂度模型需要使用到码率信息,由码率控制模型约束,另外码率控制模型需要用到SAD信息,因此可以建立一个如图1所示的自适应Slice划分算法模型,其中,纹理复杂度模块通过Intra预测获得当前帧的纹理复杂度分布,模式修正模块通过预测宏块模式来修正纹理复杂度信息,码率控制模块通过预测量化参数(QP)将纹理复杂度信息转换为比特数分布,熵编码复杂度模块基于熵编码复杂度模型通过比特数分布预测宏块计算复杂度分布,自适应Slice划分模块通过宏块计算复杂度分布均匀地划分Slice,最后以每个处理器编码一个Slice的方式进行多核编码。每个模块的具体工作将在下文中描述。

3.4　码率控制

单元级码率控制算法通过对每个宏块或宏块行进行比特分配,可以满足人们对感兴趣区域的高质量要求。对于高清视频实时编码系统,因为其整体复杂度很高,不能再采用复杂度较高的码率控制算法,权衡图像质量和编码效率后,可以采用宏块行级码率控制算法。

因为码率与纹理复杂度相关,针对本文提出的编码模型,可以使用基于纹理复杂度的宏块行级码率控制算法。首先按行统计一帧内的图像纹理分布,即对每行的IntraSAD求和,然后按每行SAD在整帧图像中所占比重分配比特数,再根据比特数结合率失真模型调整每行的QP。

率失真模型给出了码率(R)与QP的关系,可以通过宏块QP估计宏块比特数。常用的率失真模型有线性率失真模型和二次率失真模型两种,如式(3)和式(4)所示,其中线性率失真模型复杂度较低,但二次率失真模型具有较高精确度[5]:

2

R=c1×σ+c2

QP22

R=c3×σ+c4×σ2QPQP

(3)(4)

2

其中,σ为SAD;c1、c2、c3和c4为常数,由前向帧给出。宏块行级码率控制时需根据比特数调整宏块行QP,由于二次模

型通过R求QP复杂度较高,因此可以采用线性率失真模型。熵编码复杂度模型需要宏块比特数信息,可用二次率失真模型通过QP获得,但该模型公式中包含平方、除法等操作,复杂度较高,需要进行优化,可在帧开始对c3/QP+c4/QP2建

图1　自适应Slice划分算法模型

表,通过查表法每个宏块只需一次乘法操作。3.5　熵编码复杂度

熵编码模块复杂度随码率而变化,其复杂度模型为[6]:C=k1R+k2Rα

(5)

3.2　纹理复杂度

因为编码复杂度与纹理复杂度相关,针对高清视频实时编码系统的高效率要求,可以用代表纹理信息的Intra预测(IP)结果来预测宏块复杂度,所以纹理复杂度模块主要完成

其中,k1,k2和α为常数,由表2给出;R为码率,C为熵编码模块复杂度。由于熵编码与熵解码复杂度类似,该模型同样

—227—

适用于熵编码。

表2　熵编码复杂度模型参数

帧类型IP

熵编码模式CAVLCCABACCAVLCCABAC

k1-1.50　0.07　0.09　0.10

k23.4931.5186.1586.15

α0.720.310.220.15

动变大,所以整体并行编码效率会有所降低。

　　因为该模型是非线性的,所以实时编码过程中不能直接使用该公式。由于系数为常数,因此可以对熵编码复杂度和

R建表,通过划分码率区间进行查表即可在较低复杂度下完成该模型的功能。3.6　自适应Slice划分

在高清视频实时编码系统中,因为其他编码模块计算复杂度较为固定,只要加上熵编码模块复杂度即为宏块计算复杂度,然后以宏块为单位统计整帧复杂度分布,最后使用式(6)可以将计算复杂度均匀地分配到每个Slice。

I∑Ck-∑Cki

k=0

∑Ck≤k=0,i=0,1,…,S-1(6)k=Ii-1S-i

其中,Ck是宏块索引为k的宏块计算复杂度;N为一帧宏块

N

Ii-1

图2　CAVLC编码加速比

数;S为一帧的Slice数;Ii为宏块索引。满足条件的最大Ii值即为第i个Slice最后一个宏块的索引,当i为0时,第一个Slice分到的计算复杂度为总计算复杂度除以Slice数,后面的Slice分到的计算复杂度为剩余计算复杂度除以剩余Slice数,以此实现自适应Slice划分。

3.7　多核并行编码

由于本文提出的算法模型在初始阶段完成了整帧的Intra预测,因此在多核编码阶段只需做Inter模式预测,然后与Intra预测结果比较。因为多核编码划分了Slice,而Intra预测时还没有Slice边界,没有考虑预测方向的,所以多核编码时在Slice边界的Intra宏块预测方向不一定合法,需进行以下修正:如果选择Intra模式,则判断预测方向是否存在,如果不存在则重做Intra预测,然后再选择编码模式。最后结合编码模式选择,以一个处理器编码一个Slice的方式实现多核并行编码。

由于本文提出的自适应算法只是提前完成Intra预测,模式修正时也采用直接映射的方法,并且对二次率失真模型和熵编码复杂度模型进行了查表优化,因此使用该算法后整体计算复杂度增加很小。

图3　CABAC编码加速比

图4　四核CAVLC编码的并行加速比

4　实验结果与分析

本文以高清视频实时编码系统为基础,在PC仿真平台上测试了固定宏块数Slice划分算法和本文提出的自适应Slice划分算法。测试序列为500帧1080P30的rush-hour和ducks,使用IPPP模式,分别以CAVLC和CABAC测试了8Mb/s码率下并行加速比随并行核数的变化情况以及四核并行编码时不同码率下的并行加速比情况,分别如图2～图5所示。在图2和图3中,当并行核数为8时,自适应算法并行加速比约提高了0.5倍,提升效果明显。其中,CABAC提升效果比CAVLC略好,因为CABAC时熵编码模块复杂度较高,该模块计算复杂度波动对整体并行效率的影响也更大,经本文提出的自适应Slice划分算法调整后效果更为明显。在图4和图5中,码率增加后并行加速比会降低,主要是因为码率增加导致熵编码模块复杂度增加,使整体的计算复杂度波—228—

图5　四核CABAC编码的并行加速比

5　结束语

本文针对多核高清视频实时编码系统,提出一种新的自适应Slice划分算法,该算法均匀地分配计算复杂度并有效地提高了并行加速比。

参考文献

[1]　于俊清,李　江,魏海涛.基于同构多核处理器的H.2多粒

度并行编码器[J].计算机学报,2009,32(6):1100-1109.[2]　JungB,JeonB.AdaptiveSlice-levelParallelismforH.2/

AVCEncodingUsingPremacroblockModeSelection[J].JournalofVisualCommunicationandImageRepresentation,2008,19(8):558-572.

(下转第233页)

2.0,本文提出算法的加速比为2.34,较文献[5]的方法效率提高17%,说明基于功能模块的并行算法解码器效率得到提高。

　　图5中还比较了采用不同码率和熵编码方式的码流采用基于功能模块的并行解码器的加速比。由图可知,随着码率的增加,CAVLC和CABAC格式码流的加速比均下降,这是由于高码率带来更高的运算量。而CAVLC模式较CABAC模式算法复杂度低10%～15%,因此CAVLC模式码流的加速比一直高于同码率下CABAC格式码流的加速比。

能模块,设计了三核并行解码器结构,分析了模块间数据的依赖关系,简化了三核间数据交互。实验数据表明,本文提出的基于功能模块的并行解码算法并行程度更高,加速比优于基于可变模块划分等解码方法。

参考文献

[1]　RavasiM.AComputationalComplexityComparisonofMPEG4

andJVTCodecs[S].2002.

[2]　TolEB.MappingofH.2DecodingonaMultiprocessor

Architecture[C]//Proc.ofSPIE'03.SantaClara,[s.n.],2003.

[3]　SeinsterFH.AMacroblock-levelAnalysisontheDynamic

BehaviorofanH.2Decoder[C]//Proc.ofISCE'07.[S.l.]:IEEEPress,2007.

[4]　TullsenDM.LimitationsofCachePrefetchingonaBus-based

Multiprocessor[C]//Proc.ofthe20thAnnualInternationalSymposiumonComputerArchitecture.[S.l.]:IEEEPress,1993.

[5]　NishiharaK.ParallelizationofH.2VideoDecoderfor

EmbeddedMulticoreProcessor[C]//Proc.of2008IEEEInternationalConferenceonMultimediaandExpo.[S.l.]:IEEEPress,2008.

USA:

图5　不同码率码流加速比

5　结束语

本文提出一种基于功能模块的并行解码算法,分析了解码器内部模块的划分方法,将解码器较均衡的划分为3个功

编辑:陈　文

(上接第228页)

[3]　SpinsanteS,GambiE,ChiaralueeF,etal.ComplexityIssues

intheIntroductionofHighDefinitioninH.2/AVCBasedonVideoconferencing[C]//Proc.of2006InternationalConferenceonSoftware,

TelecommunicationsandComputerNetworks.

[S.l.]:IEEEPress,2006.

[4]　宁　华,梅　铮,李.基于Slice的H.2并行视频编码算

法[J].计算机工程,2005,31(4):181-182.

[5]　LiuYang,LiZhengguo,SohYeng-Chai.RegionofInterest-

basedResourceAllocationforConversationalVideo

CommunicationofH.2/AVC[J].IEEETransactionsonCircuitsandSystemsforVideoTechnology,2008,18(1):134-139.

[6]　MaZhan,ZhangZhongbo,WangYao.ComplexityModelingof

H.2Entropy2008.

Decoding[C]//Proc.of

International

ConferenceonImageProcessing.SanDiego,USA:[s.n.],

编辑:陈　文

(上接第230页)

运算量大,不利于实时处理,这是下一步的研究方向。

参考文献

[1]　EphraimY,MalahD.SpeechEnhancementUsingaMinium

MeansquarErrorShort-timeSpectralAmplitudeEstimator[J].IEEETrans.onAcoustSpeechSignalProcess,1984,32(6):1109-1121.

[2]　ErkelensJS,HendriksRC,HeusdensR,etal.Minimum

Mean-SquareErrorEstimationofDiscreteFourierCoefficientswithGeneralizedGammaPriors[J].IEEETrans.onAudio,Speech,andLanguageProcessing,2007,15(6):1741-1752.[3]　WuBingfei,

WangKun-Ching.RobustEndpointDetection

AlgorithmBasedontheAdaptiveBand-partitioningSpectralEntropyinAdverseEnvironments[J].IEEETrans.onSpeechandAudioProcessing,2005,13(5):762-774.

[4]　李燕诚,崔慧娟,唐　昆.基于似然比测试的语音激活检测算

法[J].计算机工程,2009,35(10):214-216.

[5]　CohenI.RelaxedStatisticalModelforSpeechEnhancementand

aPriorSNREstimation[J].IEEETrans.onSpeechandAudioProcessing,2005,13(5):870-881.

[6]　PlapousC,MarroC,ScalartP.ReliableAPosterioriSignal-to-noiseRatioFeaturesSelection[C]//Proc.of2005IEEEWorkshoponApplicationsofSignalProcessingtoAudioandAcoustics.NewPaltz,USA:[s.n.],2005.

编辑:金胡考

—233—