（通信与信息系统专业论文）图像编码中率失真优化算法的研究.pdf

摘要 图像编码中率失真优化算法的研究 摘要 自从1 9 4 8 年香农提出了率失真理论以来，率失真理论就是信源编码中重 要的基础理论。率失真优化技术能够有效地提高图像视频压缩编码系统的性能， 无论是从信息论的角度还是从设计实际编码系统的角度它在信源编码中都有着 广泛的应用，尤其在标准已定义的场合，率失真优化技术可以不受编码结构和技 术的限制进一步提高系统性能，因而一直以来都是热点的研究内容。最近国际上 新制定的h 2 6 4 a v c 视频编码标准在和以前的标准编码框架类似的条件下，压 缩效率至少提高了一倍以上，这一突破说明了对压缩编码中的关键技术进行研究 和率失真优化具有十分重要的理论和实际意义。在率失真优化技术中率失真曲线 斜率2 决定了优化的性能。在有损编码系统中量化是失真的主要来源，量化器的 性能直接影响了系统的编码效率。随着对高压缩比高质量的图像视频信号需求 的不断增加，如何最优地量化信号成为越来越重要的问题。因此本文围绕着率失 真优化，主要研究了下面几个方面的问题： 首先，我们对如何在给定码率约束条件下求解最优的率失真曲线斜率旯的问 题进行了研究。针对目前常用的二分法当率失真曲线上的可操作点稀疏时可能不 收敛的情况，提出了基于黄金分割搜索法求解最优率失真曲线斜率五幸的算法。 该算法克服了二分法在可操作点稀疏的情况下不收敛的缺点，而且复杂度较低、 易于实现，适于应用在实际的编码系统中。在j m l l 0 上的实验结果表明使用所 提算法求解的名进行模式选择可以有效提高系统的率失真性能。 然后，研究了如何优化块编码压缩系统中的量化器。针对图像视频编码系统 中量化器输入信号的分布特点，提出了率失真优化的量化阶调整算法。算法首先 调整输入信号的量化阶，实现系数级的优化；然后以块为单位优化编码块的量化 阶，实现块级的优化。实验结果表明本算法能够有效提高量化器性能，并且编码 增益随码率的增加而增加。同时所提算法还能够保留更多图像细节，解码后的图 像具有更好的主观质量。所提算法没有额外开销，与标准解码器兼容，而且适用 上海交通人学博士学位论文 于任何基于块编码的图像和视频压缩标准。 最后，本文研究了如何运用率失真优化提高格状编码量化器的性能。针对原 有量化算法中没有综合考虑失真和码率的缺点，提出了率失真优化的格状编码量 化算法。所提算法不仅优化了输入信号在子集中的量化阶，还对路径选择进行了 优化。实验结果表明所提算法可以有效提高格状编码量化器的性能。该算法没有 额外的开销，与标准的解码器兼容，同时可以广泛适用于基于格状编码量化器的 图像和视频编码系统。 关键词：率失真理论，拉格朗日优化，量化，格状编码量化器，死区，编码 i i a b s t ra c t s t u d i e so nr a t e d i s t o r t i o no p t i m i z a t i o ni n i m a g eco d i n g a b s t r a c t t h es t a r t i n gp o i n to fc l a s s i c a lr a t ed i s t o r t i o nt h e o r yc a nb ef o u n di ns h a n n o n s p a p e r “am a t h e m a t i c a lt h e o r yi nc o m m u n i c a t i o n i n19 4 8 r a t e - d i s t o r t i o nt h e o r y c o m e su n d e rt h eu m b r e l l ao fs o u r c ec o d i n go rc o m p r e s s i o n , w h i c hi sc o n c e r n e dw i t h t h et a s ko fm a x i m a l l ys t r i p p i n gr e d u n d a n c yf r o mas o u r c e ，s u b j e c tt of i d e l i t ye r i t e d o n r a t e - d i s t o r t i o no p t i m i z a t i o ng r e a t l yi m p r o v e sp e r f o r m a n c eo fc o d i n gs y s t e ms ot h a ti t p e r v a d e sa l lo fs o u r c ec o d i n g ，b o t hf r o ma ni n f o r m a t i o n t h e o r e t i cs t a n d p o i n ta sw l la s f o r t h ed e s i g no f p r a c t i c a lc o d i n gs y s t e m s f o rm a n yy e a r sr a t e d i s t o r t i o no p t i m i z a t i o n h a sa t t r a c t e dm o r ea n dm o r er e s e a r c h e r s i nm o s tl o s s yc o m p r e s s i o ns y s t e mq u a n t i z e r g r e a t l yi m p a c t st h ec o d i n gp e r f o r m a n c e w i t ha ni n c r e a s i n gd e m a n df o re f f i c i e n t l y c o m p r e s s e dr e p r e s e n t a t i o no fi m i a g e sa n dv i d e os i g n a l s ，t h et a s k o fo p t i m i a l q u a n t i z a t i o nh a sa s s u m e dr e n e w e di m p o r t a n c e t h er e s e a r c ho ft h i st h e s i sf o c u s e so n r a t e d i s t o r t i o n o p t i m i z a t i o nt e c h n o l o g y a n dh o wt o i m p r o v eq u a n t i z e rb y r a t e - d i s t o r t i o no p t i m i z a t i o ni ni m a g ea n dv i d e oc o m p r e s s i o n t h ec o n t e n to ft h i s t h e s i si si n t r o d u c e da sf o l l o w s ： f i r s t l y , w ei n v e s t i g a t eh o w t op i c kt h eo p t i m a ls l o p ev a l u ea o fc o n v e xh u l lo f t h er a t e d i s t o r t i o nc u r v ef o rag i v e nb u d g e tc r i t e r i o n 尼a i m i n ga tt h ed r a w b a c ko f b i s e c t i o na l g o r i t h m ，w ep r o p o s e dg o l d e n r a t i oa l g o r i t h mt of i n do u tt h eo p t i m a ls l o p e f o rb u d g e tc r i t e r i o nr c f i r s t l yt h eb i a s e dl a g r a n g i a nc o s t 喇) w h i c hi sac o n c a v e f u n c t i o no f2i si n t r o d u c e d t h e ni tt a nb ep r o v e nt h a tt h ev a l u em a x i m i z i n g 附) a r e t h eo p t i m a lc o n v e xf u l lf a c es l o p e2 f i n a l l yg o l d e n r a t i oa l g o r i t h mi sp r o p o s e dt o s e a r c ht h ev a l u et h a tm a x i m i z e s 附) ，t h a ti s ，t h eo p t i m a ls l o p ev a l u e 旯s t a r t i n g f r o mak n o w ni n i t i a li n t e r v a l e n g u l f i n gt h ed e , r e do p e r a t i n gs l o p e ，t h es e a r c h i n t e r v a l sa r em a d es u c c e s s i v e l ys m a l l e ru n t i lc o n v e r g e n c ei sa c h i e v e d i na d d i t i o n ，t h e i i i 上海交通大学博士学位论文 c o n v e r g e n t r u l eo fg o l d e n r a t i os e a r c h a l g o r t i h m i s i m p r o v e d t o g e t f a s t e r c o n v e r g e n c er a t e t h ea l g o r i t h m i s s a m p l ea n de a s yt ob er e a l i z e d m o r e o v e r , i t c o n v e r g e si na n ys i t u a t i o n t h ec l o s e rt h ei n i t i a ls e a r c hw i n d o wi st ot h ef i n a lv a l u e ， t h ef e w e ri t e r a t i o n sa r en e e d e d t h ee x p e r i m e n t a lr e s u l t ss h o wi t si t e r a t i v et i m e sc a n b ee v e nl e s st h a nb i s e c t i o n s i na d d i t i o n ，t h ep r o p o s e da l g o r i t h mc a ni m p r o v et h e c o d i n gp e r f o r m a n c e ag a i na b o u t0 6 0 7d bc a nb ea c h i e v e dw i t ht h es a m er a t ei n h 2 6 4 s e c o n d l y , h o wt oi m p r o v et h eq u a n t i z a t i o np e r f o r m a n c ei nb l o c k - b a s e di m a g e a n dv i d e oc o m p r e s s i o ni si n v e s t i g a t e d ar a t e - d i s t o r t i o nb a s e dq u a n t i z a t i o nl e v e l a d j u s t m e n t ( r d q l a ) a l g o r i t h m i s p r e s e n t e d c o n s i d e r i n g t h ed i s t r i b u t i o n c h a r a c t e r i s t i co ft h ei n p u ts i g n a lo ft h eq u a n t i z e r , t h ep r o p o s e da l g o r i t h mf o c u s e so n t h es m a l ls i g n a l s b a s e do nr a t e d i s t o r t i o nc r i t e r i o n ，t h eq u a n t i z a t i o nl e v e la d j u s t m e n t a l g o r i t h mo p t i m i z e sq u a n t i z a t i o nl e v e l so ft h es i g n a l sn e a rt h eb o u n d a r i e so fd e a d z o n e e x c e p tt h a tr d q l aa l g o r i t h ma l s om a k e si m p r o v e m e n to nb l o c kc o d i n gp r o c e s s t h e s p a r s en o n - z e r oc o e f f i c i e n t so c c u ri nab l o c ka f t e rt r a n s f o r m a t i o n ，w h i c hi sn o tw o r t h c o d i n g f r o mt h ev i e w p o i n to fr a t e d i s t o r t i o n 。i no r d e rt oa v o i dt h i s c a s e ，a r a t e d i s t o r t i o no p t i m i z e db l o c kc o d i n gm e t h o di su s e d t j a ep r o p o s e da l g o r i t h mh a sn o o v e r h e a da n di sf u l l yc o m p a t i b l ew i t ht h ee x i s t i n gc o m p r e s s i o ns t a n d a r d s i tc a nb e a p p l i e di na n yb l o c kb a s e di m a g ea n dv i d e oc o d i n gm e t h o d i np a r t i c u l a r , t h e a l g o r i t h mh a sb e e nv e r i f i e do nt h ep l a t f o r mo fh 2 6 4a n dh 2 6 3 e x p e r i m e n t a lr e s u l t s s h o wt h a tr d q l aa l g o r i t h mi m p r o v e sb o t ho b j e c t i v ea n ds u b j e c t i v ep e r f o r m a n c e s u b s t a n t i a l l y t h er d q l aa l g o r i t h ms u b s t a n t i a l l ys u r p a s s e st h eo r i g i n a la l g o r i t h m ， 、i t hb e n e f i t sb e c o m i n gs i g n i f i c a n ti nt h ec a s eo fh i g hb i tr a t e s f o rq c i fs e q u e n c e n e w s ”t h eg a i n si sa b o u t0 2 d ba tt h el o wr a t eo f4 0 k b i t sa n di sm o r et h a n2 d ba t r a t eo f1 3 m b i t s 。w h e nt h eq u a n t i z a t i o np a r a m e t e ri sv e r ys m a l l ，l i k e4 ，t h eg a i n s e v e ne x c e e d s5d b f i n a l l y , w ei n v e s t i g a t eh o wt oo p t i m i z et h et r e l l i s c o d e dq u a n t i z e r b a s e do nt h e a n a l y s i st o t h et r e l l i s c o d e dq u a n t i z e r , ar a t e - d i s t o r t i o no p t i m i z e dt r e l l i s - c o d e d q u a n t i z a t i o n ( r d o t c q ) a l g o r i t h mi sp r e s e n t e d t h ep r o p o s e da l g o r i t h mh a st w o s t e p sw h i c hr e s p e c t i v e l ya i ma tt h et w os t e p si nt r e l l i s c o d e dq u a n t i z a t i o n f i r s t l y , t h e i v a b s t r a c t s e l e c t i o no ft h er e p r o d u c t i o ns i g n a li ne a c hs u b s e ti s o p t i m i z e da c c o r d i n gt o r a t e - d i s t o r t i o nt h e o r ya n dt h e nt h et r e l l i sp a t hs e l e c t i o ni so p t i m i z e db yi n t r o d u c e st h e r a t e d i s t o r t i o nc o s ti n t ot h ec u m u l a t i v ep a t ht r a n s f e rc o s t b a s e do nr a t e - d i s t o r t i o n c r i t e r i o n ，t h ep r o p o s e da l g o r i t h me f f e c t i v e l yi m p r o v e sc o d i n ge f f i c i e n c y i na d d i t i o n , i th a sn oo v e r h e a da n di sf u l l yc o m p a t i b l ew i mt h es t a n d a r dd e c o d e r t h ep r o p o s e d a l g o r i t h mc a nb ea p p l i e di na n yt c q - b a s e ds y s t e m s i np a r t i c u l a r , t h ea l g o r i t h mh a s b e e nv e r i f i e do nt h ep l a t f o r mo ft h eq u a d t r e ec l a s s i f i e da n dt r e l l i sc o d e dq u a n t i z e d ( q t c q ) w a v e l e ti m a g ec o m p r e s s i o ns y s t e m e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e p r o p o s e da l g o r i t h mh a sab e t t e rr a t e d i s t o r t i o np e r f o r m a n c et h a nt h eq t c qa n do t h e r c o m p r e s s i o nm e t h o d s o nt h ea v e r a g e ，r d o t c qs u r p a s s e sq t c qa b o u t0 2d b a m a x i m u mg a i nu pt o1 0d bc a nb ea c h i e v e dc o m p a r e dw i t hs p i h t k e yw o r d s ：r a t e - d i s t o r t i o nt h e o r y , l a g r a n g i a no p t i m i z a t i o n ，s c a l a rq u a n t i z e r , t r e l l i s c o d e dq u a n t i z e r , d e a d z o n e ，q u a n t i z a t i o n v 上海交通大学博士学位论文 a c t c q c i f d p d c t e o b e c s q e c t c q h d i s o i t u j p e g l p l i s m p e g n u r q p d f p s n r q p q t c q 英文缩略语 a r i t h m e t i cc o d e du n i f o r m t h r e s h o l dt r e l l i s c o d e dq u a n t i z e r c o m m o ni n t e r m e d i a t ef o r m a t d y n a m i cp r o g r a m m i n g d i s c r e t ec o s i n et r a n s f o r m e n do f b l o c k 基于算术编码的均 匀门限格状编码量 化器 通用媒体格式 动态规划 离散余弦变换 块结束 e n t r o p y - c o n s t r a i n e ds c a l a rq u a n t i z e r熵受限标量量化器 e n t r o p y - c o n s t r a i n e dt r e l l i s c o d e d q u a n t i z e r h i g hd e f i n i t i o n 熵受限的格状编码 量化器 高清晰度 i n t e r n a t i o n a ls t a n d a r d i z a t i o no r g a n i z a t i o n 国际标准化组织 i n t e r n a t i o n a lt e l e c o m m u n i c a t i o n su n i o n 国际电信联盟 j o i n tt e c h n i c a lc o m m i t t e e l i s to fp i x e l s l i s to fi n s i g n i f i c a n ts e t s 联合图像专家组 系数表 不重要系数集表 m o v i n g p i c t u r ee x p e r tg r o u p运动图像专家组 n e a r l yu n i f o r mr e c o n s t r u c t i o nq u a n t i z e r p r o b a b i l i t yd e n s i t yf u n c t i o n p e a ks i g n a l t o - n o i s er a t i o 近似均匀重构量化 器 概率密度函数 峰值信噪比 量化参数 q u a d t r e ec l a s s i f i e da n dt r e l l i s四叉树划分的格状 v i 目录 q c 环 s n r s p m t t c q t c m v l c v q e g v q c o d e dq u a n t i z e r q u a r t e rc o m m o ni n t e r m e d i a t ef o r m a t s i g n a l - t o - n o i s er a t i o s e tp a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s t r e l l i s - c o d e dq u a n t i z e r 编码量化器 四分之一通用媒体 格式 信噪比 基于分层树集合分 割排序的编码 格状编码量化器 t r e l l i s c o d e dm o d u l a t i o n格状编码调制 v a r i a b l el e n g t hc o d i n g变长码编码 v i d e oq u a l i t ye x p e r t sg r o u p视频质量专家组 v e c t o rq u a n t i z e r v i i 矢量量化器 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位沦义作者签名：蒋牛 日期：力。男年争月7 曰 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密回。 ( 请在以上方框内打“4 ) 学位论文作者签名：蒋午 日期：力。方年4 月7 日 指黝师戳印孑 日期删年够月，j 曰 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位沦义作者签名：蒋牛 日期：力。男年争月7 曰 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密回。 ( 请在以上方框内打“4 ) 学位论文作者签名：蒋午 日期：力。方年4 月7 日 指黝师戳印孑 日期删年够月，j 曰 第章绪论 第一章绪论 近年来，随着多媒体技术的迅猛发展，与图像和视频相关的应用不断拓宽， 如网络交互式多媒体、数字电视广播、视频点播，远程教育与医疗、无线多媒体 通信等。由于原始图像和视频的数据量非常大，难以存储和传输，因此有效压缩 原始数据的要求变得越来越迫切，这也使得图像视频压缩成为国内外研究的热 点之一。自从1 9 4 8 年s h a n n o n 发表了标志着数字图像压缩编码技术开端的论文 “t h ep h i l o s o p h yo f p c m ”至今，国际上已经成功地制定了面向各种应用的静止 和运动图像编码标准，包括二值图像编码标准j b i g 1 2 4 1 、用于静止图像压缩的 j p e g 1 2 5 】、用于视频会议的h 2 6 1 6 酗、用于数字视频和音频传输及存储的 m p e g 1 【鲫、支持h d t v 等高品质数字视频和音频传输与存储的m p e g 2 【6 7 1 、适 合于低码率视频传输的h 2 6 3 6 引、基于对象的视频编码标准m p e g 一4 【6 9 】以及最新 制定的高编码效率的h 2 6 4 a v c 视频编码标准。随着新的国际编码标准的出台， 编码技术不断地提高和改进，图像视频编码性能也在不断地提高。尤其是 h 2 6 4 a v c 视频编码标准在和以前标准的编码框架基本相同的条件下，取得了压 缩效率至少提高一倍的优良性能，引起了业界广泛的关注i s 9 。表1 - 1 列出了h 2 6 4 和两个较新的编码标准压缩效率的比较1 19 1 。从表中可以看出即便是与m p e g 2 和h 2 6 3 这两个编码性能优良的标准相比，h 2 6 4 还能将压缩效率提高一倍左右。 下面就分析一下h 2 6 4 a v c 视频编码标准性能提高的根源所在。 目前的视频编码标准一般都是采用如图1 1 所示的技术框架，同是基于这个 框架，h 2 6 4 a v c 编码标准却比以往任何标准的编码效率都提高了一倍左右。分 析编码标准可以知道h 2 6 4 编码效率的提高来源于两个因素：其一是更精确的预 测技术，如多参考帧预测，1 4 像素精度运动补偿，可变块大小的运动补偿以及 更高效率的熵编码技术等；其二是率失真优化技术，如率失真优化的运动矢量搜 索和模式选择。率失真优化技术对编码性能的提高可以从图1 2 中看出。该图中 给出了j m l1 0 在三个q c i f 序列n e w s 、f o r e m a n 和c o n t a i n e r 上使用率失真优化 技术前后( 参数r d o p t i m i z a t i o n = 0 1 ) 编码性能的比较。可以看出在其它编码技术 相同的情况下，只增加率失真优化技术就能够有效提高编码性能，平均增益在 上海交通大学博士学位论文 表卜lh 2 6 4 相对m p e g - 2 和h 2 6 3 的编码增益，c i f 序列1 9 1 t a b l e1 - 1c o d i n gg a i no fh 2 6 4o v e rm p e g - 2a n dh 2 6 3f o rv a r i o u sc i fs e q u e n c e s 1 9 i r e n em o b i l ep a r i ss t u d e n t s c o d i n gg a i no v e rm p e g 一2 5 3 5 8 4 9 4 5 c o d i n gg a i no v e rh 2 6 3b a s e l i n e 5 3 5 8 4 2 4 5 图l 一1 典型的混合视频编码器框图 f i g 1 1t y p i c a lh y b r i dv i d e oc o d e r 0 6 d b 左右，最大增益甚至可以达到约l d b 。由此可见率失真优化技术是提高编 码效率的有效手段。它在提高编码效率的同时不受编码结构和技术的限制，这一 特性尤其适用于编码技术固定的场合，比如基于现有编码标准的应用。由于此时 无法通过修改己定义的技术提高编码性能，率失真优化技术就成为提高编码效率 的主要手段。无论从信息论的角度还是从系统设计的角度，率失真优化技术贯穿 了整个视频编码系统，从块内系数的量化阶的决策到宏块的模式选择到宏块间比 特分配等。因此率失真优化技术一直以来都是研究热点之一。 率失真优化技术中最常用的方法是拉格朗日优化方法。拉格朗日优化通过求 解不受限的最小值问题 2 第一章绪论 m i n j ( 2 ) = d ( x ) + 力尺( x ) )( 1 1 ) 来得到给定码率约束尼条件下可以达到的最优系统性能。其中五是率失真曲线 斜率，d 是平均失真，尺是对应的码率。它的物理意义是用一条斜率为a 的 直线不断逼近率失真曲线，最终和率失真曲线相切的切点就是最优解。可以看出 五是拉格朗同优化方法性能的决定因素，同时也直接影响了系统优化后的性能。 a 取值得当，就能得到给定码率下最优的编码性能；反之，可能得到率失真曲线 上的次优点，影响优化效果，甚至导致优化失败，造成系统性能下降。因此本文 首先研究了如何求解给定码率条件下最优的率失真曲线斜率名；然后由于量化 在有损编码系统中的重要作用，本文将率失真优化技术和量化相结合，分别研究 了基于d c t 变换的编码系统和基于小波变换编码系统中的量化器优化问题。虽 然以往这方面的研究有不少，但大都基于某个特定的编码标准，因而普适性较差。 本文在这方面的贡献是重点研究了具有普适性的率失真优化量化技术。 在本章接下来的内容中，先简要介绍率失真优化技术，然后简单介绍了标量 量化器及性能；最后概述了本文的主要内容和创新成果。 翌 叱 z 乱 - 图1 - 2 率失真优化前后编码性能的比较 f i g 1 - 2c o m p a r i s o no fr dp e r f o r m a n c e 、析t ha n dw i t h o u tr do p t i m i z a t i o n l 海交通人学博士学位论文 1 1 率失真优化技术 率失真理论是压缩编码的理论基础。率失真理论反映了源信号x 经过信道传 输或压缩失真后得到的接收信号】，间的互信息熵，率失真函数定义为 1 4 】 r ( d ) = m i n ，( x ；】，) ( 1 2 ) p ( y j l x j ) 其中心d 是信号x 和】，之间的信息熵，p ( y j x i ) 是传输而接收 的转移概率。码 率r 和失真d 的关系可以用如图1 3 中光滑的下凸单调曲线刻画，这条率失真 理论曲线定义了在不考虑任何约束条件下系统可能达到的最优性能。而在实际编 码系统中，为了保证可行性，通常对系统的编码复杂度、延时和内存等都有一定 的要求，因此实际系统的最优性能并不能达到率失真曲线定义的理论值，此时针 对输入信源分布设计的能够充分满足约束条件的最优编码方案所能达到的最好 性能就是实际编码系统的最优性能。而对于一个特定的图像或视频编码系统，编 码结构和技术已经确定，最优的编码方案就是在编码系统定义的所有参数值中搜 索能够使性能最优的参数配置。以图1 1 所示的视频编码系统为例，可以配置的 参数包括量化步长，宏块分割模式，预测模式以及编码模式等。为这些参数配置 不同的值就能得到不同的率失真性能。通过配置参数能够达到的最好的性能就是 该系统的最优性能。不同参数配置条件下码率和失真的关系可以通过下面的方式 获得。 1 用一组特定的编码参数配置( 比如量化步长、宏块模式选择等) 对输入信号编 码，并测量编码后的码率和重构信号失真，这样就获得了该参数配置条件下 得到的平均码率和失真，也就是一个可操作点( o p e r a t i n gp o i n t ) 。 2 使用不同的编码参数组合编码同一输入信号，以获得其它可操作点。 3 进一步组合编码参数，重复步骤l 和2 。 由上述过程得到的一组可操作点就构成了如图1 3 所示的可操作率失真曲线。该 曲线定义的是系统实际可以达到的性能。由于实际编码系统中参数的取值是有限 的，比如h 2 6 4 中量化参数只有5 2 个，h 2 6 3 中量化参数只有3 2 个，因此可操 作率失真曲线上的可操作点是离散的，可操作率失真曲线也不是一条光滑的曲 线。可操作率失真曲线的下边界也就是可操作率失真曲线的凸包络定义了系统最 优的率失真性能。在给定码率约束的条件下，最小失真就出现在凸包络上。可操 4 第一章绪论 作率失真曲线上的可操作点越靠近凸包络，它的率失真性能就越好。率失真优化 的目的就是找到一组编码参数配置使得对应的可操作点尽可能接近凸包络，也就 是在一组可能的操作点中确定能使系统性能最优的操作点，而且试验证明率失真 优化确实能够提高系统的性能【2 0 】。 代 图1 - 3 可操作率失真曲线示意图d 力 f i g 1 - 3t h eo p e r a t i o n a lr - dc h a r a c t 舐s t i c 【3 7 】 对于如图1 - 1 所示的典型的视频编码系统，需要配置的参数很多，包括预测 模式、运动估计、量化、编码模式等。每个参数都有若干可供选择的取值，如p s l i c e 的编码模式有帧内4 x 4 、帧内1 6 x 1 6 、帧间4 x 4 、帧间4 x 8 、帧间8 x 1 6 等， 量化模块有不同的量化阶等，那么如何在事先定义的参数中选择能使系统的编码 性能最优的参数配置? 解决这个问题的方法有拉格朗同优化方法和动态规划法 ( d y n a m i cp r o g r a m m i n g , d p ) 。动态规划法对每一种参数组合计算相应的率失真代 价值以求解最优的性能。该算法构造网格来代表所有可能的解，求解最优解就相 当于搜索一条最优路径，在到达同一个节点的所有路径中选择失真最小的最优路 径，其他在相同码率下失真较大的路径都被删除。该算法由于复杂度相当高，一 般不应用于实际系统中。而拉格朗日优化方法基于各编码块相互独立的假设，是 实际应用中最常用和最有力的优化编码系统的工具。拉格朗日优化由【2 1 1 提出， 在【2 2 】中首次被应用在信源编码中，接着被用于树裁剪和熵受限的资源分配问题 中【2 3 】【2 4 1 ，之后拉格朗日优化方法得到了广泛应用【2 5 】【2 q 【2 7 1 【2 8 】【2 9 】【3 0 】。拉格朗日优化 方法引入了非负的实数念o ，也就是拉格朗曰因子，得到拉格朗日代价值朋) = 5 上海交通大学博士学位论文 d + 肷。拉格朗日代价值彤) 被用来衡量编码性能的好坏，m ) 越小说明编 码性能越好。拉格朗日优化的核心思想是说，当编码块之间互不相关，也就是块 间的失真和码率不相关时，信源x 存在满足下式的最优解3 1 】 m i n j ( 2 ) = d ( x ) + 力r ( x ) )( 1 3 ) 其中d 是平均失真，r 是对应的码率，那么当最优解对应的码率等于r 。时， 该最优解也是下式的解。 m i n d ( x )s t r ( x ) 疋 ( 1 4 ) 由此可见拉格朗日优化给出了将受限的求极值问题转换为不受限的求极值 问题的方法。当( 1 3 ) 式求得的最优码率等于给定的码率约束时，( 1 3 ) 式的解也是 ( 1 4 ) 式的解。这样在优化编码系统时只要求解( 1 3 ) 式就可以了。在( 1 3 ) 式中，拉 格朗日因子a 用来衡量码率和失真的相对重要性。它的物理意义就是率失真曲线 的斜率。a 越小失真越重要，当a = 0 时，最小化朋) 就等价于在不考虑码率的情 况下使失真最小，也就是在可操作率失真曲线上选择最靠近y 轴的点；五越大码 率越重要，a = 0 0 时，最小化朋) 就等价于最小化码率，也就是搜索最靠近z 轴的 点。当i a 0 时，最小化朋) 就对应着中间的可操作点。图l - 4 给出了拉格朗 日优化方法的解释。在每一种a 的取值情况下，( 1 3 ) 式的解都是一条斜率为矗 的斜线和可操作率失真曲线的凸包络相切的点，因此拉格朗r 优化方法求出的解 严格位于可操作率失真曲线的凸包络上。 a 0 ) ) d 雕)斜率- 2 r 图1 - 4 拉格朗日优化 f i g 1 - 4l a g r a n g eo p t i m i z a t i o n 拉格朗日优化方法概念简单，能够有效的通过一种优化方式对多种编码参数 6 第一章绪论 的选择进行评估，是常用的系统优化的方法。拉格朗日优化中斜率a 决定了优化 后系统性能的好坏。从( 1 3 ) 式可以看出，a 已知时可以很容易地求出在给定a 的 条件下使系统性能最优的解。然而在实际应用中，通常不是在给定a 的条件下优 化系统，而是在给定码率约束条件下，对系统进行优化。这就需要首先求解出与 给定码率约束相对应的a 【2 2 】【3 0 】【3 2