（计算机软件与理论专业论文）多类别的视频伸缩性编码的研究和实现.pdf

多类别的视频仲缩件编码的研究和实现 摘要 随着i n t e m e t 不断的发展和网络带宽的不断增长，网络上的多媒体的应用也 得到了迅速的发展。在i n t e r n e t 上传输音频、视频的相关技术也成为i n t e r n e t 研 究和开发的热点，而流媒体技术正是这些技术的核心。以前固定码率的视频编码 方式已经不能适合流媒体在i n t e m e t 这种异构的环境中传输，在这种背景下，伸 缩性的视频编码技术应运而生。伸缩性的视频编码指的是毯驱部分的码流就可以 重构出原始内容的视频，而根据截取码流的部分可以在视频的质量、空间和时间 上有伸缩性的表现。使用这种编码方式，可以在服务器上只保留一份内容的副本， 钊。对不同的用户，提供在质量上、画面大小上、每秒帧数上各不相同的视频内容。 本文主要研究了视频的伸缩性编码技术。随后分析了几个有代表性的视频伸缩性 编解码算法( f g s 、s p i h t ) 。在此基础上，本文提出了一种多盏盟的视频伸缩性 编解码算法i - s p i h t - 3 d 以及利用该算法的流媒体发布框架。接着介绍了该框架 和算法的参考实现。最后对编解码算法进行了细致的性能分析，通过对 i - s p i h t - 3 d 算法的分析、实验和比较，可以得到：i - s p i h t - 3 d 编解码算法是一 个适合流媒体发布的视频编解码算法，实现了从质量码率到空间、时间上的多类 别的可伸缩性；而1 - s p i h t - 3 d 系统则为该编解码算法的运行提供了体系结构和 平台上的支持。 关键字：视频编码，伸缩性编码， 中图分类号：t p 3 扒 嘴一 多类别的视频伸缩忭编码的研究和安现 a b s t r a c t a st h ed e v e l o p m e n to f t h ei n t e r a c ta n dt h ei n c r e m e n to f t h en e t w o r kb a n d w i d t h ， t h en e t w o r km u l t i m e d i aa p p l i c a t i o ng r o w sr a p i d l y t h et e c h n o l o g i e so ft r a n s m i s s i o n a u d i oa n dv i d e oo v e rt h ei n t e r n e th a v eb e c o m et h eh o t s p o to ft h ei n t e r n e ta n dt h e s t r e a m i n gm u l t i m e d i at e c h n o l o g yi st h ec o t eo ft h i s t h ec o n s t a n tb i tr a t ev i d e o c o d i n gp a t t e r nd o s en o ts u i t et h et r a n s m i s s i o no v e rt h ei n t e m e t , a si t i sa h e t e r o g e n e o u se n v i r o n m e n t u n d e rs u c hc i r c u m s t a n c e ，s c a l a b l ev i d e oc o d i n gh a sb e e n p u tf o r w a r d s c a l a b l ev i d e oc o d i n gi st or e c o n s t r u c tt h eo r i g i n a lv i d e ou s i n gt h ep a r t o ft h eb i ts t r e a m d e p e n d i n go nt h ec o d i n gp a r e m ，s e r v e rc a nu s eo n ev i d e oc o p yt o s e r v i c em a n yk i n d so fc l i e n tp l a y e r t h ec l i e n tp l a y e rc a ng e tt h ev i d e oc o n t e n tt h a t a d a p t st h e i rn e t w o r kb a n d w i d t ha n dd e v i c ep e r f o r m a n c e t h i sp a p e rm a k e sr e s e a r c h i n t ot h et e c h n o l o g i e so ft h es c a l a b l ev i d e oc o d i n ga n da n a l y s e ss e v e r a ls c a l a b l ev i d e o c o d i n ga r i t h m e t i c t h e nt h ea r i t h m e t i ca n dt h ef r a m e w o r ko fi - s p i h t - 3 dh a v eb e e n p r o p o s e d f i n a l l y , as y s t e mo f1 - s p i h t - 3 di sd e s i g n e da n di m p l e m e n t e dt os h o wt h e s y s t e mp e r f o r m a n c e a l la n a l y s i s ，e x p e r i m e n t sa n dc o m p a r i s o nd e m o n s t r a t et h a t i - s p i h t - 3 da l g o r i t h mi sas e a l a b l ev i d e oc o d i n ga l g o r i t h ma i m i n ga ti n c r e a s i n gu s e r s a t i s f a c t i o nw i t hi - s p i h t - 3 ds y s t e m p r o v i d i n gt h en e c e s s a r ya r c h i t e c t u r ea n d p l a t f o r ms u p p o r t k e yw o r d s ：v i d e oc o d i n g ，s e a l a b l ec o d i n g ，s t r e a m i n gm u l t i m e d i a 多类刷的视频伸缩忭编码的研究和寅现 1 。1 研究背景 第一章绪论 自上f l = 纪9 0 年代以来，i n t e m e t 已经成为世界上影响最广、增k 最快、市场 潜力最大的产业之一，并且正以超出人们想象的深度和广度不断发展。万维网 ( w o r l dw i d ew e b 或简称w e b ) 的出现更是以其简单的操作方式将图文并茂的 网上信息带给普通大众，使i n t e r n e t 从一种内容发送机制成为一种服务平台，大 量的服务和应用( 如新闻服务、网上银行，在线游戏、电子商务等) 都围绕着 w e b 进行，这极大的促进了刚络用户和流量的爆炸式增长。 掘统计f l l 1 2 】，i n t e m e t 上的连网主机数已经超过1 7 亿，w e b 站点数超过4 6 0 0 万，伞球i n t e m e t 用户人数接近7 亿，而这个数宁到2 0 0 5 年预计将突破l o 亿。 在经济发达国家，一半以卜的人口经常使用i n t e m e t ，信息技术最发达的美国则 拥有1 6 6 亿上网用户；即使在发展中国家，巴西也已经拥有1 4 0 0 万上网用户。 巾国且联网络信息中心( c n n i c ) 2 0 0 6 午1 月发布的第1 7 次统计报告【3 】显示， 到2 0 0 5 年年底，中国网民人数已经达剑了1 1 1 0 0 万，而且如图i 一1 所示，预 计这个数字还会飞速增氏。 1 1 l 吧一 9 4 啦 7 9 5 0 5 9 1 0 ：誓岁 2 0 0 01 22 0 0 l1 22 0 0 2 1 22 0 0 31 22 0 0 4i ： 2 0 0 51 2 坡搿鬏摊：t 引柚 鞭 一镪7 七铲t p 一孙 c n n i c ， 罔1 1 中田历次蒯食网民总数 捻蝴伽姗。 多类别的视频仲缩什编码的研究和，史现 随着i n t e m e t 不断的发展和网络带宽的不断增长，网络上的多媒体的应用也 得到了迅速的发展。在c n n i c 的报告巾( 图1 2 ) 显示了网民对在线音乐、影 视收听及下载等多媒体应用的服务需求越来越大。 l 象掣擎 艘敖粘件 辩聪硅试 站虹，粥lf 澎甓i 蒋 ，赭臻番舟瓣 # 犯# p 舟鹣 嗽 船魂。t ：n fh 镕$ 褙4 拽p 踺l 惜 麓】 # 摊嚣；* 目月 莪 m 碰， 辑h 技l 葶魁身尊堆。群税p 肫， 辩i 舻瘦 辫j 役盘采 h l 瞬街 x m 辨镯 辩 事 a 口l 料l 荆糟至硼l s 辨 砸r 齄喜幽i 十羲窑瓣鲢2 幽1 4 辩g ( 0 1 郇雠镍秘鑫)互圈l jh 蚪 垒醺 包赫辨缸辩 蝣瞬， # g 礴hh 孵l 粒 i t 锅蒋l 雷辩l 摊r 。辩i 辩霍：譬口蛳 热臻慧，耘锚瓣并三盈9 n 毽拼h i i p 也拉t op 酶n 蜀6 m 蜘t 控4 麟l4 i t ，拜l 叠静 圈5 1 等 艘l 琏拜，辅墒+ 黎务持咕雄， 墨4 幽 挺饕、宅盘柑“勰堆蠡 蠹j 籼 嚣乜图4 伊i mm mh m l 藏豫最耀：巾鞠q 鞋孵臻储辣巾尊渊i c 图1 2 中国刚民上网甘的分类 也正因为这些原囚，在i n t e m e t 上传输音频、视频的相关技术也成为i n t e m e t 研究和开发的热点1 4 】，而流媒体技术正是这些技术的核心。 所谓流媒体【5 j 是指用户通过网络或者特定数字信道边下载边播放多媒体数 据的一种工作方式。流媒体应用的一个最大的好处是用户不需要花费很长时间将 多媒体数据全部下载到本地后才能播放，而仅需将起始几秒的数据先下载到本地 的缓冲区中就可以开始播放，后面收到的数据会源源不断输入到该缓冲区，从而 维持播放的连续性，因此流媒体播放器通常只是在开始时有一些时延。 虽然流媒体技术有这些优势，但是流媒体应用系统要比下载播放系统复杂得 多，所以需要将多媒体的编解码和传输技术很好地结合在一起，才能确保用户在 复杂的网络环境下也能得到较稳定的播放质量。相比较本地播放的视频文件，在 州络上传输的流媒体码流需要史强的适应性和伸缩性。如图1 3 ，i n t e r n e t 嘲络 是一个异构的环境，它连接了大量的不同的网络环境。这种不同也许是网络连接 的速度不同，可能是几百兆带宽的局域网连接，也可能是只有2 8 8k b p s 的调制 多类别的视频仲缩忭编码的研究和史现 解调器连接；也许是移动所导致的无线环境的不同；也许是客户端设备不同的处 理能力和硬件条件，客户端可能是高性能的台式机，也可能是只有很小屏幕的移 动设备。就算在相同的网络条件和硬件设备条件下，网络带宽产生波动也会影响 流媒体应用系统的工作。 图1 3 i n t e m e t 异构的网络环境 在异构的网络环境下要实现最好质量的流媒体应用系统，一种方法就是针对 每个多媒体内容准备大量的适应各种环境的备份，比如同一个多媒体的内容，有 适合存同一个以太网内传输的大码率文件，也有适合低带宽的无线网络的小码率 文件，但是很明显这种方法效率非常低下。实现流媒体应用系统的另一个方法就 是让多媒体内容可以伸缩性的自适应异构的网络环境【4 】，也就是说对丁同一个内 容的请求，服务器可以只利用一个副本实时产生多个合适实际网络情况和客户端 情况的多媒体码率。在多媒体内容的可伸缩性处理中，视频的处理比音频的处理 更为重要，这是因为视频需要的带宽( 1 0 0k b p s 1 5 m b p s ) 一般比音频的( 8k b p s 1 2 8k b p s ) 大很多，所以如果传送的多媒体内容同时包含视频和音频信息，那 么对视频做可伸缩处理对整个多媒体内容的传输更有决定性的帮助。根据这方面 的考虑，本文的一1 作主要涉及视频的可伸缩性方向的处理。 多类剧的视频仲缩忭编码的研究和寅现 1 2 可伸缩视频编码技术简介 固定码率的视频编码是指在某个给定的码率下对视频进行最优的编码【6 】o 这 种通常的编码方式般应用在图1 4 的情况下。 播放 图1 4 固定码率的应用环境 在这种编码方式下，编码器对输入的原始视频内容进行编码，编码时候的性 能参数一般在编码前就已经确定。一般视频每一帧或者每一组帧都获得相同大小 的码流。还有一种编码的方式是变码率的视频编码，在这种方式中，保持不变的 是每一帧视频图像的画面质晕，也就是视频的质最系数保持不变，而码率会凼为 视频内容的变化产生前后大小不一致。 图1 5 网络视频应用 而在一些网络流媒体视频应用中( 图i 一5 ) ，编码器产生的文件要通过一个 信道传输到客户端，所以固定码率和可变码率的视频编码就都不合适了。因为在 编码时不知道实际的网络信道情况，无法使用一个固定的码率或者固定的质量系 数对视频进行最优的编码。而在这种情况下，视频编码的目的就变成在一段给定 的码率范围内，对视频进行最优的编码，产生的码流可以满足一定祀围内的任意 码率要求。这种视频的编码方式就被称为可伸缩的视频编码，截取部分的码流就 可以重构出比原始视频质量稍差的视频，所以说这种伸缩性也被称为码率伸缩性 或者质量伸缩性。 6 多类别的视频伸缩件编码的研究和爻现 好 斧 图1 6 视频质量和码率之问的关系图 图1 6 是视频质量和所需码率之间的关系图，纵轴表示用户接受到的视频 质量，横轴表示传送时的码率。理想曲线是指在某个给定码率下进行编码所能达 到最好的质量效果，而伸缩性码率编码的曲线一般会比理想曲线略低一点，三条 虚线代表了固定码牢编码的三种情况。可以看出，在某些区域，固定码率编码的 曲线会比伸缩性码率编码的曲线高，但是如果码率没有到达一个闽值，固定码率 编码就不能产生任何视频，而且随着码率的上升，视频质量也小再会上升了。所 以在网络带宽会发牛变动的环境下，伸缩性码率的编码将会有更好的应用。 除了码率伸缩性的编码，另外两种的伸缩住编码是空问伸缩性的编码和时间 伸缩性的编码。空问伸缩性的编码就是同一个码流可以产生几个国面尺寸大小不 同的视频；时间伸缩性的编码就足同一个码流可以产生几个每秒帧数不同的视 频。空间伸缩性和时问伸缩性的编码主要是解决在嘲络视频的应用中，客户端设 备的不同。 1 3 本文的研究内容和主要成果 本文的研究工作隶属于国家自然科学基金重点项目电子图书馆的相关关键 技术。作者希望通过本人的工作，为网络的伸缩性编码的视频流媒体传输提供框 架、编解码的算法和技术支撑，以提高流媒体服务的质晕。 本文主要研究了视频的伸缩性编码技术。随后分析了几个有代表性的视频伸 缩性编解码算法( f g s 、s p i h t ) 。在此基础卜，本文提m 了一种视频伸缩性编解 码算法( 简称i - s p i h t - 3 d ) 以及利用该算法的流媒体发布框架。接着介绍了该 框架和算法的参考实现，最后对编解码算法j 2 【行了细致的性能分析，做了大量的 多类州的视频仲缩竹编码的研究和史现 实验。通过和几个主流的算法的分析、实验和比较，我们的i - s p i h t - 3 d 的方案 具有以下特点和贡献。 1 ) 作为一个适合流媒体发布的视频编解码算法，1 - s p i h t - 3 d 实现了从质量 码率到空间、时间上的多类别的可伸缩性。 2 1i - s p i h t - 3 d 算法在编解码上使用了完全对称的算法，降低了编码时的复 杂性，使得实时编码成为可能。 3 ) 对于一个视频内容，j 保留一份文件，减少了对服务器磁盘的暂用量。 4 ) 充分考虑到流媒体传输时需要的实时陛，在r t p r t c p 上提出了无应答 选择重传的滑动窗口协议，保证了传输过程中高吞吐量。 5 ) i - s p i h t - 3 d 的实现上考虑了跨甲台问题，服务端程序和客户端程序都可 以运行在主流的操作系统平台上。 1 4 文章的组织结构 本文共分章，将讨论以f 几个方面的研究1 作： 1 ) 作为流媒体系统和伸缩性视频编码的产牛背景，第一章对i n t e m e t 的异 构网络环境和流媒体的应用的问题做了调查、研究和分析，随后对可伸 缩的视频编码技术进行了掏单的介绍。 2 ) 第二章研究了几个典型的视频编解码技术，包括m p e g 系列和小波系列 的视频编解码技术，并详细介绍了两个系列中可伸缩性编解码的代表： f g s 和s p i h t - 3 d 。 3 ) 第三章提出了i - s p i h t - 3 d 的视频编解码算法，先介绍了两维的算法， 然后扩展到三维的情况，提出了具体的算法。 4 ) 第四章提出了“多类别的可伸缩性的视频编解码系统i - s p i h t - 3 d ”，主 要介绍了这个系统对于异构的网络环境和不同的客户端情况如何完成 从质量到时间，空间上的伸缩性。 5 ) 第五章对i - s p l h t - 3 d 系统进行了设计和实现，并将i - s p i h t - 3 d 的视频 编解码算法与传统的视频编解码算法在性能和效率上进行了实验结果 的比较和分析。 6 ) 第六章是结束语，总结了本文的工作，并对将来的研究工作做了腱望。 一 多类j ；| j 的视频仲缩忭编码的研究和实现 第二章典型的视频编解码技术 信息论之父c e s h a n n o n 第一次用数学语言阐明了概率与信息冗余度的关 系。在1 9 4 8 年，s h a n n o n 提出1 7 1 任何信息都存在冗余，冗余大小与信息中每个 符号( 数字、字母或单词) 的出现概率或者说不确定性有关。s h a n n o n 借鉴了 热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”，并给出了 计算信息熵的数学表达式。这篇伟大的论文后来被誉为信息论的开山之作，信息 熵也奠定了所有数据压缩算法的理论基础。从本质上讲，数据压缩的目的就是要 消除信息中的，几余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗 余的程度。利用信息熵公式，人们可以计算出信息编码的极限，即在一定的概率 模型下，无损压缩的编码长度不可能小于信息熵公式给出的结果。视频编码的主 要目的就足希望可以通过算法对多媒体内容的数据进行压缩，用尽量小的文件储 存尽量多的内容。 在早期的视频编码技术中，运用的还是一些通用的数据压缩算法，比如 h u f f m a n 、l z 【8 1 【i9 1 ，【0 1 等。但是根据s h a n n o n 的信息论【7 】，对信息的先验知识越多， 我们就可以把信息压缩得越小。换句话说，如果压缩算法的设计目标不是任意的 数据源，而是基本属性已知的特种数据，压缩的效果就会进一步提高。 一般来说，主流的视频编码技术主要有三类：( 1 ) 基于离散余弦变换( d c t ) ： ( 2 ) 荩于小波变换；( 3 ) 一些专有的方式。 2 1 m p e g 系列视频编码技术 基于离散余弦变换的视频编码技术的代表是m p e g 【1 1 l ( 活动图像专家组 m o v i n gp i c t u r ee x p o r t sg r o u p ) 系列标准。m p e g 标准中用来对音频和视频内容 进行编码的标准包括m p e g - 1 ，m p e g 一2 ，m p e g - 4 ，这几个视频编码都是基于离 散余弦变换的。m p e g 标准一般首先使用傅立叶变换把视频信号变换成频率域上 的系数，然后使用分级的量化器对系数进行量化，最后使用行程编码。由于人对 高频信号不敏感，所以在码率的限制卜，视频的高频系数被截断。m p e g 编码依 靠两个荩本的方式：减少空间冗余信息的帧内d c t 编码；减少时间冗余佶息的 帧问d c t 编码。视频编码包括三种类犁的帧：i 、p 和b 。l 帧为帧内编码帧( i n t r a c o d e df r a m e ) ，编码时采用炎似j p e g 的帧内d c t 编码；p 帧为预测编码帧 9 多类别的税频伸缩件编码的研究和实现 ( p r e d i c t i v ec o d e df r a m e ) ，采用前向运动补偿预测和误差的d c t 编码，由其前 而的i 或p 帧进行预测。b 帧为双向预测编码帧( b i d i r e c t i o n a l l yp r e d i c t i v ec o d e d f r a m e ) ，采用双向运动补偿预测和误差的d c t 编码，由前面和后面的i 或p 帧 进行预测，所以b 帧的压缩效牢最高。 对于m p e g 的编码方式，存在几个可以进行伸缩性编码的方法。第一，通 过改变不同的量化级别以获得不同的编码码率”m ”】；第二，离散余弦变换系数 被分割成基本层和增强层，基本层携带了视频的重要信息，而增强层可以增强基 本层的视频质量，当网络带宽少的时候可以丢弃增强层以减少码率【1 4 】，【1 5 】“6 1 。 2 2 小波系列 在小波编码中，视频信号首先被分割成几个频带，然后使用小波函数获得变 换系数，变换后的系数最后通过量化和行程编码。可以看出，小波编码就是一个 渐进式的视频编码。通常的小波编码使用带运动补偿的曲维小波变换n 7 1 或者三维 的小波变换。 从伸缩性方面考虑，基于小波变换的编码技术优于基于离散余弦变换的编码 技术，因为小波变换是对一帧或者几帧图像进行处理，向离散余弦变换是对更小 的块进行处理的，所以小波变换的编码更容易扩展伸缩的特性。 2 3 专用方式 一些商用的应用程序比如r e a ln e t w o r k s 公司的r e a l v i d e o t ”1 和i n t e l 公司的 i n d e o t 2 0 1 使用了自己公司专用的视频编码技术。一般这些编码技术都混合使用了 基于离散余弦变换和小波变换的技术，它们的特点足对某种特定带宽码率的视频 压缩进行了优化，比如2 8 8 k b p s 和5 6 k b p s 。在伸缩性方面，r e a l v i d e o 的做法只 是把不同码率的视频简单的合并在一个文件中。 2 4 主要的可伸缩视频编码技术 2 4 1f g s 在上面已经提纠的，在早期的m p e g 标准的视频编码中，已经包含了伸缩 性的特点。在m p e g 2 和m p e g - 4 有数种层次化的伸缩性，如信噪比伸缩性编 o 多类别的视频仲缩忭编码的研究和实现 码( s n rs e a l a b i l i t y ) ，时间伸缩性( t e m p o r a ls c a l a b i l i t y ) 和空间伸缩性( s p a t i a l s c a l a b i l i t y ) 等等。在这种层次化的伸缩性巾，一个视频被编码成基础层和增强层。 而增强层和基础层相似，必须完整受到才能进行解码。所以说，层次化的伸缩性 码率质量曲线是条类似两节阶梯形状的曲线。相比较普通编码方式的一节阶 梯形状的曲线，层次化的伸缩性已经具有简单的伸缩特性，但足这个跟理想的曲 线还是有一定的距离。 针对层次化伸缩性的缺点，2 0 0 0 年m p e g 提出把精细粒度可缩放性( f i n e g r a n u l a r i t ys c a l a b i l i t y ) 囝编进m p e g 4 标准草案中。f g s 的基本想法也足将视频 编成基础层和增强层。首先，基础层使用不可伸缩的编码以达到编码效果的底限， 增强层则足利用了离散余弦变换系数的位平面编码( b i t p l a n ec o d i n g ) ，对原始画 面和基本层重建出来画面的差异值进行编码。 因为使用位平面编码方式，增强层可以在任意的位置截断，而解码所得视频 质量同增强层所解码的内容多少成正比。因此，f g s 除了分成基本层和增强层以 外，迩可将增强层进一步利用位平面编码将其分的更细，使得编码可以提供连续 的伸缩性曲线。 由于f g s 存在编码效率比较低的一些缺点，w u 等人又提出了渐进、精细的 可伸缩性技术2 2 1 ，( p r o g r e s s i v ef i n e g r a n u l a r s c a l a b l e ) ，简称p f g s 。如图2 一 l 所示，与m e p g - 4 中的f g s 相比，p f g s 编码框架试图在增强层的编码过程中 采用多个高质量的参考柬提高编码效率，这是因为高压量的参考可使运动预测更 准确。同时，p f g s 可以实现超过两个位流层，具有更好的预测和错误恢复能力。 b a s el a y e r l s te n h a n c e m e n t l a y e t 2 n de n h a n c e m e n t l a y e r 3 r de n h a n c e 鹏n t l a y e r 4 t he n h a n c e m e n t l a y e r 2 34 f r a m e s 图2 1f p g s 多类别的视频伸缩件编码的研究和寅现 2 4 2s p i h l - 3 d 小波变换的本质足多分辨率或多尺度地分析信号，它能够很好地消除图像数 据巾的统计冗余，同时又能够很好地保持原图像在各种分辨率下的精细结构，因 此对图片和视频的压缩率较大，而且视频重构输出质量非常高。正足由于这些原 因，小波编码在较高压缩比的图像视频编码领域和伸缩性编码领域被非常看好。 在基于小波变换的视频压缩技术巾口4 1 ，【2 5 】，【2 6 1 ，一- 种比较有效的方法是采用 s p i h t - 3 d 1 2 7 博法。s a i d 和p e a r l m a n 提出了基于s p i h t 2 8 1 的图像压缩算法，在编 码效率和编码时间上都获得了很好的结果。他们把s p i h t 扩展到三维，提出了 s p i h t - 3 d 算法，该算法对小波变换系数进行一个偏序的排列，从而实现了视频 的伸缩性编码。 多类别的税频仲缩什编码的研究和贸现 第三章可伸缩编解码算法 本文提出的i - s p i h t 是一个可伸缩的编解码算法，包括1 - s p i h t 图像编解码 算法和i - s p i h t - 3 d 视频编解码算法。由于i - s p i h t - 3 d 视频编解码算法是i - s p l h t 图像编解码算法的扩展，所以在本章里，会先介绍可伸缩编解码的基础，接下来 分别介绍i s p i h t 图像编解码算法和i - s p i h t - 3 d 视频编解码算法。 3 1 可伸缩编解码的基础 在可伸缩的编码领域，除了要对数据进行尽可能多的压缩，而且斋要编码产 生的码流有可伸缩的性能。这就要求产生的码流在任意的位置都可以重构原来的 图像或者视频内容。接下去介绍要产生伸缩性码流的先决条什。 因为图像和视频都可以看作是一些有序点的集合，那么假定需要处理的是一 幅图像。可以把原始图像定义为一系列的点n ，所组成的p ，f ，j ) 代表点的坐标。 编码可以认为是一个酉变换：c = q ( p ) 。酉变换后的c 和p 包含相同多的元素， 而q ，是变化后在( f ，) 的变化系数。整个伸缩性编码的模式如图3 一l 所示，发 送端只把部分的变化系数发送过去，接受端就只能利用e 进行原始图像的重构工 作。重构后产生的图像是户= q “i c ) 。 e 可以荤构山声，而我们还希望重构出来的户最接近p 。可以使用均方误差 ( m e a ns q u a r e de r r o rm s e ) 表示图像之间的接近程度( 公式1 ) 。 ：毕：专；跏咱，户 ， 因为在酉变换f 2 中，欧几里得标准保持不变，所以可以得出公式2 。 巩。【p 一声) = 瓯。仁一o ) = 面i 争_ 。c 广t ，) 2 2 从公式2 可以得到，如果只能f 送部分的系数，那么f 送绝对值尽量大的c ， 将使重掏的图像更接近原始图像。如果系数相同的位所包含信息量相同，可以把 多类别的视频伸缩件编码的研究和实现 公式2 扩展到系数的每个位中，即先传送所有系数的高位，然后再传送低位。位 平面方法就是利用了这个想法来进行渐进方式的传输。 所以说，如果想在编码中增加伸缩性的功能，那么编码输出的码流必须先输 出包含大信息量的系数。 3 2 i - s p i h t 图像编解码算法 在图像压缩技术领域，s h a p i r o 2 9 提出了嵌入式零树小波编码( e m b e d d e d z e r o t r e ew a v e l e t e z w ) 。这种技术不仅兼顾了效率和复杂度两个方面，而且可 以产生一个嵌入式的位流。这种嵌入式的位流可以在任意长度进行解码，得到画 面质量不同的图像。s a i d 和p e a r l m a n 在嵌入式零树小波编码的技术上提出了分 等级的集合分割图像编码算法( 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 p i h t ) 【2 8 】， 这种算法相比较e z w 算法在性能和效率上都有了更好的效果。e z w 和s p i h t 算法都满足上面提到条件，两个算法都是先输出包含大信息量的系数。 为了先输出包含大信息量的系数，需要对系数做一遍排序的处理。两个不同 系数相同的位包含了等量的信息，所以根据它们所包含的有用位的个数 ( 1 0 9 2 i c u l j ) 进行排序。 。；。警 ，i ； i s b0 s sssssss ss s sss s il0 0o0o000oo000 il00o0o0 0 0 0 0o lll l0o o o0o o 1l1ll1l 图3 2 排序扁的位平曲 图3 2 排序后的位平面是已排好序的系数队列，每一列代表了一个用二进 制表示的系数c 。，最上面一行代表了系数的符号，m s b 行代表了系数最高位， 也就是代表最莺要的信息的位，l s b 行代表了系数的最低位。输出箭头方向的码 流就是具有伸缩性的码流。对于系数，有以下一些概念上的定义。 定义i ： s 班悟其i c , 它j i 慨 - 2 如果s 。( f ) = 1 ，那么系数c 。对丁n 层足重要的系数，也可以说c 。对丁阈 值是电萤的系数；如果s 。o ) = 0 ，那么系数c 。对十”层是不重要的系数。 多类别的视频伸缩 牛编码的研究和寅现 定义2 ： 驰) = m 肚a x ，烧 如果瓯仃) = l ，那么集合r 对于厅层是重要的系数集合，也可以说集合r 对 于阈值是重要的系数集合；如果最仃) = 0 ，那么集合r 对于层是不重要的系数 集合。 这种方法可以输出具有伸缩性的码流，但是在码流前必须先输出系数的坐标 信息。如果只是简单的加上每个系数的坐标，那么添加的内容会很大，编码的效 率也就会非常低。因为不需要知道同一层的重要系数之间的大小，所以不一定需 要完全按照系数的大小进行排序。实际上，在”层位平面的时候j 需要提供哪些 系数是重要系数就够了，这是凼为任何算法的执行路径总是由些分支路径的判 断语句所决定，所以如果编码和解码使用相同的排序算法，而且解码器在解码的 时候能得到那些分支路径判断语句结果的话，解码器就町以复制出编码时候的执 行路径。也就是说，解码器根据得到的判断信息就可以获得系数坐标的信息，从 而重构出图像。 图3 3 小波分析 如图3 3 左边，图像经过小波变换，大部分能量都会集中在低频区域中， 而且在低频和高频区域之间会存在一些空间上的相似性。也就是说，如果在低频 的某些区域上的系数比较小，j i l ；么一般高频上的对应区域也会是一些比较小的系 数。跟据这个特点，可以把小波变换后的图像看成一个类似金字塔形状的结构( 图 3 3 右边) 。 区域a 为企宁塔的最上层，也称为仑宁塔的根，区域b 、c 、组成第二层， 多类别的视频伸缩性编码的研究和实现 而最外面区域b l 、c l 、d l 组成第三层，它们所包含的点被称为叶子。所有的点 都被分割成2 x 2 的组，图中最小的方格代表了一个点。除了根和叶子，每个点 都对应下一层一个2 x 2 的组，这个组就是它的孩子。根中每个2 x 2 的组，除了 左上角带星形的点以外，其余三个点都分别对应b 、c 、d 中的一个组。根据这 些结构，可以定义一些集合： o ( i ，) ：( f ，) 孩子的集合； d ( f ) ：( f ，) 所有子孙的集合； 日：根中所自的点； 工( f ，) = d ( f j ) 一o q , j ) 根据小波变换的特性，可以得出一个结论：如果在某个闽值r 下，系数c 。是 不重要的系数，那么它的孩子集合d ( f ) 很有可能也是不重要的系数集合。 利用这个结论和s p i h t 的工作，我 f j 提出了i - s p i h t 的算法。算法使用了 四个列表： l i p ：存放不重要的系数； l s p ：存放重要的系数； l t p ：存放临时的系数； l i s ：存放不重要的系数集合。 l i p 、l s p 和l 1 p 的元素是系数的坐标( f ) ；l i s 的元素是( f ，- ，) 和类型标志， 如果类型是a ，表示存放的是集合d ( i , j 1 ，如果类型是b ，表示存放的是 集合工( f j ) 。不管在算法的哪一步，四个列表中所有系数的总合一定就是图像的 所有系数。 编码包括排序、细化、插入三个步骤。在排序步骤里，首先根据现在的层次 n 计算新的阈值，然后把l i p 里对于新的阈值是重要的系数移到u p 中；把l 1 s 里对于新的阈值是重要的集合分割成几个点和几个集合，根据分割后系数的重要 性移到l i p 或者u 甲中，新的集合如果是不重要的集合，就添加在l i s 中，如 果还足重要的集合，就继续分割直到l i s 中存放的都足不重要的集合。通过排序 这个步骤，对于新的闳值变成苹要的系数都被添加到l s p 中。在细化步骤里， 把l s p 中所有系数对应该层的位流输出。在插入步骤里，因为要保证l s p 中的 系数是根据其坐标的顺序存放的，所以要把l t p 叶j 的系数捅入到l s p 合适的位 置。完成三个步骤以后，把n 减一，然后再进行排序、细化、插入这些步骤。 1 6 多类别的税频仲缩性编码的研究和实现 具体的i - s p i h t 的编码算法如下： 1 初始化： ”= l 。s ：( m a x 一趾 l s p = 空集合。 l i p = h ： l i s = l i p 中每一项的子孙点集合，类型为a ； 2 排序过程： f o rl i p 里面的每一项( i ，j ) 输出s n ( i ，j ) ； i f s n ( i ，j 户it h e n 添加( i ，j ) 到l t p 并且输出c i j 的符弓； e n d f o r f o rl i s 里面的每一项( i ，j ) s w i t c h ( i ，j ) 的类型： a ： 输出s n ( d ( i ，j ) ) ； i f s n ( d ( i ，j ) 产i f o r ( i ，j ) 的每个孩子( ki ) 输出s n ( k , 1 ) ； i f s n ( k ，1 ) = 1 添加( k ，1 ) 到l t p 并且输出c k ，l 的符号； e l s e 添j j h ( k ，i ) nl i p ； e n d i f e n d f o r i f l ( i ，j ) - 0 移动( i ，j ) 项到l i s 的最后，改变类型为b ； e l s e 从l i s 中移除( i ，j ) 项； e n d i f e n d i f b ： 输出s n ( l ( i ，j ) ) ； i f s n ( l ( i ，j ) ) = 1 添n ( i ，j ) 的四个孩子到l i s 中，类型为a ； 从l i s 中移除( i ，j ) 项； e n d i f e n d s w i t c h e n d f o r 3 细化过程： 对十l s p 中的每项( i ，j ) ，依次输出其绝对值的第n 位的值。 4 插入过程： 对丁l t p 中的系数，根据坐标移剑l s p 中合适的位置。 5 更新： n ，返回步骤2 。 多类别的视频伸缩忭编码的研究和，实现 以上是i - s p i h t 图像编码算法，因为要在编码和解码的时候得到相同的程序 执行路径，所以解码算法和编码算法有相同结构，区别只是在解码的时候根据输 入的位流来控制程序分支路径的走向。 3 3 i - s p i h t - 3 d 视频编解码算法 3 3 1i s p i h t - 3 d 视频编解码算法框架 i - s p i h t - 3 d 视频编解码算法是i - s p i h t 图像编解码算法的扩展。这种扩展有 两个方面：1 两维的图像扩展到三维的视频：2 只有p s n r 上的伸缩性扩展到 p s n r 、空间、时间多方面的伸缩性。图3 4 是系统视频编解码部分的总体框 架。 g o f l 客户端卜卜一鱼望+ 一服务器k i ! f 视频位流 叵! h 竺堕h 亟全卜黼g 1 v r 图3 4 视频编码部分的总体框架 固定数目的视频帧首先进行时问空间的小波分析，然后经过i - s p i h t - 3 d 的 编码，生成一个视频的位流和一个索引文件。服务器根据利用索引文件，根据当 时信道情况和客户端信息产生合适的码流。客户端接受到码流后通过i - s p i h t - 3 d 的解码和空间时间的综合，最后得到一组视频帧( g r o u po f f r a m e s ) 。 3 3 2 三维小波分析 类似i - s p i h t 算法，时间、空间分析的目的是要分解视频成多频带结构的， 然后利用低频和高频之间的空间相似性来编码视频文件。1 s p i h t - 3 d 使用了一 个三维小波分析。小波分析巾旨九对组视频帧( g o f ) 在刚间卜进行分析，然 后进行空问上的分析。图3 5 描述了一个g o f 首先被分解成四个时问上的频 骷。 多类别的视频仲缩忭编码的研究和实现 l h l l l l l h 罔3 5 g o f 小波分析 g o f 进过时间分析以后，将会对每帧进行类似图像的空间分析。很多以前 的工作2 7 1 认为不需要的时间高频带进行空间小波分析，囚为在高频带已经不包含 很大的能星了。但是，在i - s p i h t - 3 d 巾，我们发现对高频带做空间分析将有助 于提高编码性能。图3 6 a 是三次时间小波分析后的最低频带冉进行曲次牢问 小波分析；罔3 6 b 是三次时间小波分析后的最高频带；图3 6 c 是三次刚问 小波分析后的最高频带冉进行两次空间小波分析。 一 多类别的 ! | ! 频伸缩忭编码的研究和实现 圈3 6 空间、时间小波分析例子 从图b 可以看出，虽然进过空间小波分析以后，高频带已经没有什么能量了， 但是高频带还是会有一些的卒问冗余信息。而对高频带做窄间小波分析以后( 图 c ) ，能量进一步聚集在其巾的低频部分，而且在图c 巾也会存在少量的空间相似 性。 3 3 3 金字塔结构 i - s p i h t - 3 d 视频编解码算法主要从两维的i s p i h t 扩展向来。在扩展过程 中，关键足要保持i - s p i h t 算法的高效和伸缩性。i - s p i h t - 3 d 的编解码模式和两 维的基本相似，主要包括三个相似的特性：1 根据小波系数位数的大小对系数 进行排序；2 按照排序的结果进行传输位平面的位流；3 能充分利用三维时间 空间上的相似性。这三个特性保证了i - s p i h t - 3 d 输出的位流将是完全嵌入式的， 一个压缩以后的视频文件可以提供在时间上、空问上、质量上的伸缩性。 在上一节，我们讲述了i - s p i h t 算法，算法是维度无关的。特别是排序以后， 算法也不会利用维度的信息了，而只需要知道对于给定一个阈值哪些点或者集合 是重要集合。所以说，两个算法的一个不同点就是在构建金字塔结构的过程。 i - s p i h t - 3 d 要保证输出的位流具有时问上、空间上、质量上的伸缩性，而 i - s p i h t 只需要在空间上、质量上的伸缩性，这是两个算法另一个不同点。也正 凼为这样，i - s p l h t - 3 d 的索引文件将比1 - s p l h t 的复杂一点。 首先将讲述如何构建金宁塔结构的树。在i - s p i h t 中每个父亲有四个孩子或 者没有孩了，而i - s p i h t - 3 d 中，因为扩展到了三维，所以每个父亲有八个孩了 或者没有孩子。纠i s p i h t 类似，八个孩子组成2 x 2 x 2 的块。金字塔的最上层 是整棵树的根，八个点组成的一个块中，除了