（计算机系统结构专业论文）多核并行计算在视频服务中的研究及应用.pdf

山东大学硕士学位论文 摘要 随着网络技术的发展，流媒体技术也在不断地发展， 流媒体技术广泛的应用于网络电视、视频会议系统、视频 监控系统等场合。现在，人们对流媒体的要求越来越高的情 况下，要提高视频系统的实时性，一方面是要提高网络带 宽，另一方面就是提高其压缩速率。 为了提高压缩效率，m p eg 标准被提了出来。m p eg 是运 动图像专家小组的简称，在国际标准化组织iso iec 的领 导下，经过近十年卓有成效的工作，为多媒体计算机系统、 运动图像压缩编码技术的标准化和实用化，做出了巨大的 贡献。19 98 年正式推出了m p e o 一4 标准。该标准主要应用于 视频电话、视频电子邮件和电子新闻等场合。m p e g 一4 利用 很窄的带宽，通过帧重建技术压缩和传输数据，使得能够 以最小的数据获得最佳的图像质量。 目前，国内外很多芯片生产厂家正在致力于多核技术 的发展。多核可以降低芯片的频率，这样在降低了系统功耗 的同时，提高芯片运算的速度。为了提高压缩速度，结合 正在迅速发展的多核技术对压缩过程加以改进。 首先，本文对m pe g 一4 标准中一些基本概念和算法进行 了概括和介绍，包括视频服务系统的整体架构，m ee g 视频 压缩算法以及运动补偿预测等概念。 然后，对m p e g 一4 标准中的压缩算法进行了深入细致的 研究，发现压缩算法中存在很多并行性。并行性主要体现 在帧内编码中的离散余弦变换以及帧间编码时的运动估计 上。本文专门针对帧内编码和帧间编码分别提出了帧内并 行编码算法( ipc a ) 和基于预测的方向菱形运动估计 ( p p ddm e ) 算法，并且在双核平台u p o m a p5 910 上对算法进 行了实现和模拟。实验结果证明，并行算法的使用确实在 压缩速度上得到较大的提高。 最后，为了进一步提高压缩的速度，我们提出了多核 的负载平衡的技术。在对传统的负载平衡技术做了简要的 山东大学硕士学位论文 介绍之后，提出一个新个负载平衡模型，该模型将多核进 行等级划分，分别为一级核、二级核、三级核。这三种等 级的内核分别负责不同的工作，并且在二级核之间采用了 分布式负载平衡的方式，在二级核与其所管辖的三级核之 间采用了集中式负载平衡方式，将该模型用到了p p dd m e 算 法上。实验数据表明，负载平衡技术与并行压缩算法的结 合在较大程度上提高了视频服务系统的效率。 关键字：m peg 一4 标准：多核处理器：并行计算：运动估计： 负载平衡 i i 山东大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n t0 fn e t w o r kt e c h n e l o g y ，s t r e a m i n g m e d i a t e c h n 0 1 0 9 y is c o n t i n u o u s l yd e v e l o p i n g ，s t r e a m i n g m e d i at e c h n 0 1 0 9 yw i d e l yu s e di nn e t w or kt e le v is i o n ，v i d e e c o n f e r e n c i n gs y s t e m s ，v i d e es u r v e i l l a n c es ys t e m s ，a n do t h e r p 1 a c e s n o wp e o p l ea r ei nh i g hd e m a n d so fs t r e a m i n gm e d i a t e c h n 0 1 0 9 y ，h o wc a nw ei r e p r o v et h er e a l - t i m ev i d e es ys t e m ， o nt h eo n eh a n di st oe n h a n c en e t w o r kb a n d w id t h ，o nt h e o t h e rh a n dist or a is ei t sc o m p r e ss i o nr a t e i no r d e rt o i m p r o v et h ee f f i c i e n c y o fc o m p r e s s i o n ， m p e gs t a n d a r d sa r ep u tf o r w a r d m p e gi sa na b br e v i a t i o n o fm o v i n gp i c t u r ee x p er tg r o u p ，a n d ert h e1 e a d e r s h i po ft h e i n t e r n a t i o n a l0r g a n i z a t i o nf o rs t a n d a r d i z a t i o n ( i s 0 i e c ) ， a f t ern e a r l y10y e a r s0 ff r u i t f u lw o r kf o r t h em u l t i m e d i a c o m p u t e r s y s t e m ，s p o r t si m a g ec o m p r e s s i o nt e c h n o l o g y s t a n d a r d i z a t i o na n dpr a c t ic a l u s e ，h a v em a d et r e m e n d o u s c o n t r i b u t i o ns i nl9 9 8t h ef or m a ll a u n c ho fm p e g 4s t a n d a r d ，w h ic hi sm a i n l yu s e di nv i d e et e l e p h o n y ( v i d e ep h o n e ) ， v i d e e e - m a i l ( v i d e ee - m a i l ) a n d t h ee 1 e c t r o n i c sn e w s ( e 1 e c t r o n i cn e w s ) m p e g - 4u s i n gav e r yn a r r o wb a n d w i d t h ， t h r o u g hr e c o n s t r u c t i o nf r a m ed a t ac o m pr es s i o na n dt r a n s - m iss i o nt e c h n o l o g yt oe n a b l et h ed a t at om i n i m i z et h eb e s t i m a g eq u a l i t y a t p r e s e n t ，m a n yc h i p m a n u f a c t u r e r sa th o m ea n d a b r o a da r ec o m m i t t e dt ot h e d e v e l o p m e n to fm u l t i - c or e t e c h n o l o g y m u l t i c o r ec h i p sc a nr e d u c et h ef r e q u e n c yo ft h i s s ys t e ma n dr e d u c et h ep o w e rc o n s u m p t i o na tt h es a m et i m e ， i n c r e a s et h es p e e do fc o m p u t i n gc h i ps i no r d e rt o i m p r o v e t h es p e e do fc o m p r e s s i o n ，i nc o n ja n c t i o nw i t ht h ec u r r e n t r a p i dd e v e l o p m e n to fm u l t i 。c o r et e c h n o l o g yf o rt h ec o m 山东大学硕士学位论文 p r e ss i o npr o c e s st ob ei m pr o v e d f ir s t ，t h is p a p e rp r e s e n t e ss o m eb a s i cc o n c e p t s a n d a l g o r i t h m s i nm p e g - 4s t a n d a r d ，i n c l u d i n gv i d e os e r v ic e s s ys t e m ，t h eo v e r a l ls y s t e ma r c h i t e c t u r e ，m p e gv i d e oc o m - p r e ss i o na l g or i t h m sa n dm o t i o npr o je c t i o n sa n ds oo n t h e n ，t hr o u g ht h es t u d yo nt h em p e g 一4s t a n d a r dc o r n pr e s s i o na l g or i t h m ，w ef i n d t h a tt h e r ea r ep a r a l l e li nm a n y c o m p r e s s i o na l g o r i t h m p a r a l l e li sm a i n l yr e f l e c t e di nt h e d e c o d i n go ft h ed is cr e t ec os i n et r a n s f o r mc o d i n g ，a sw e l la s i n t er f r a m em o t i o nes t i m a t i o n t h is p a p e rp r o p o s e d t w o p a r a l l e la l g o r i t h m s f o ri n tr a a n di n t er - f r a m ec o d i n g ，a n d r e a l i z i n ga l g o r i t h m a n ds i m u l a t i o no nt h ed u a l - c o r e u p - o m a p 5910p l a t f or m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t ， a f t e rt h eu s i n go fp a r a l l e la l g or i t h m ，c o m p r e ss i o ns p e e di s g r e a t l ye n h a n t e d f i n a l l y ，i no r d e rt o f u r t h e ri m p r o v et h ec o m p r e s s i o n r a t e ，w eh a v ei n t r o d u c e dam u i t i - c o r e1 0 a db a l a n c i n gt e c h - n o l o g y a f t e rab r ie fi n t r o d u c t i o na b o u tt h et r a d i t i o n a ll o a d b a l a n c i n gt e c h n 0 1 0 9 y ，w ep r o p o s ean e wm o d e lo fl o a db a l - a n t i n g i nt h ism o d e l ，t h ec o r e sa r ed i v i d e di n t ot h r e e1 e v e l ， t h ef ir s tl e v e lc or e ，t h es e c o n d1 e v e lc or ea n dt h et h ir d 1 e v e lc o r e a 1 1t h r e e1 e v e lsc or ed od i f f er e n tw o r k a m o n g a l lt h es e c o n d1e v e lc or e s ，w epr o p os e dd is t r i b u t e1 0 a d b a l a n t i n g a n db e t w e e nt h es e c o n dc o r ea n di t st h i r dc o r e s ， w epr o p os e dc e n t r a l i z e dl o a db a l a n c i n g t h em o d e li su s e d o nt h ep p d d m ea l g or i t h m e x p e r i m e n t a ld a t ai n d i c a t et h a t ， t h ec o m b i n a t i o no f1 0 a db a l a n c i n gt e c h n o l o g ya n dp a r a l l e l c o m p r es s i o na l g or i t h i ni m pr o v es t h ee f f ic i e n c yo ft h e s y s t e mv i d e os e r v i c e st oag r e a te x t e n t k e y w o r d ：m p e g - 4s t a n d a r d ；m i i l t i c o r ep r o c e s o r ；p a r a i l e l c o m p u t i n g ；l o a db a l a n c i n g ；m o t i o ne s t i m a t i o n i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：盥日期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 做作者躲盟黝弥绰日期：出，夕 山东大学硕士学位论文 第一章绪论 1 1 课题研究背景及意义 随着网络技术和网格技术的不断发展，作为多媒体和网络领域交 叉学科的流媒体技术越来越成为各界人士研究的热点问题。多媒体使 计算机能够综合处理声音，文字，图像和视频，它以丰富的声、文、 图信息和方便的交互性，极大改善了人机界面，改变了人们使用计算 机的方式，从而为计算机进入人类生活和生产的各个领域打开了方便 之门，给人们的生活，工作和娱乐带来了深刻的变化。随着网络宽带 化的发展趋势，人们不再满足于信息高速公路中仅有的文本，图像或 声音这一类简单的信息，而越来越希望更直观，更丰富的新一代信息 的表现形式，流媒体( m e d i as t r e a m i n g ，又称s t r e a m i n gm e d i a ) 技术 由此便应运而生。以前，多媒体文件需要从服务器上下载后才能播放。 由于多媒体文件一般内存较大，一个典型m p e g 一1 编码视频节目，1 分 钟的数据为11 3 m b ，利用5 6 k b p s 调制解调器至少需要2 7 分钟进行下 载，因而限制了人们在互联网上使用多媒体数据进行交流。流媒体不 同于传统的媒体，它的主要特征就是边下载边观看，以流的形式进行 数字媒体的传送，从而可以使人们在线欣赏到连续不断的多媒体节目。 在互联网迅速发展的时代，流媒体技术的产生和发展必然会给我们的 日常生活和工作带来深远的影响。 流媒体技术广泛的应用于网络电视，视频会议系统，视频监控系 统，工业现场控制系统等各种场合，对于这些实时性要求特别高的应 用来说，在网络带宽一定的情况下一个适用于低传输速率的方案显得 尤为必要，m p e g - 4 正是基于此而提出的一种国际标准。m p e g 一4 视频编 码技术采用了现代图像编码方法，利用人眼视觉特性，从轮廓一纹理 的思路出发，支持基于内容和对象的编码，支持基于内容的交互功能。 m p e g 一4 视频编码正在完成从基于像素的图像编码向基于对象和内容的 现代编码的转变，它代表了新一代智能图像编码，是当下主流图像通 信机制所广泛采用的编码标准。 多核处理器标志着计算技术的一次重大飞跃。多核处理器，较之 山东大学硕士学位论文 皇量甍菖罾量鲁目鼍曼曼鼍曼量皇舅舅曼鲁量曼量_ i 皇曼曼曼皇鲁摹量量| 量量量曼曼皇曼皇曼皇邑量簟| 罾量曼曼曼| 曼量 单核处理器，能带来更多的性能和生产力优势，因而将成为一种广泛 普及的计算模式。多核并行计算可以降低单个问题的求解时间，增加问 题求解的规模，提高问题求解精度。基于以上种种优点，将多核并行 计算应用于视频传输之中必然会大大提高传输速率，提高视频传输的 实时性，有重要的理论和现实意义。 在嵌入式多核平台上研究在视频服务中的多核计算是山东省重大 科技攻关项目一具有自主知识产权的嵌入式系统研究及开发 ( 2 0 0 5 g g l1 010 01 ) 的一个子课题，具有非常重要的意义。 1 2 国内外流媒体技术发展现状 i n te r n e t 使世界日益变成一个“地球村，在这样的背景下，多媒 体和网络的交叉课题一一流媒体的发展成为一个必然结果。分析表明， i n t e r n e t 服务器5 0 的存储内容是流媒体数据。流媒体的应用系统， 国际标准和基础研究正成为目前产业界和科研机构密切关注的焦点。 1 2 1 视频传输 目前，多媒体和网络领域的相应国际标准和协议充分考虑了流媒 体的应用。在网络领域，i n t e r n e t 专家任务组i e t f ( i n t e r n e te x p e r t t a s k f o r c e ) 制定了实时传输协议实时传输控制协议 r t p r t c p ( r e a l t i m et r a n s f e rp r o t o c 0 1 r e a l - t i m et r a n s f e rc o n t r o lp r o t o c 0 1 ) 协议族。该协议族是流媒体的应用层协议，早在1 9 9 6 年就成为i n t e r n e t 的国际标准。针对具体应用，i e t f 还制定了r t p 与特定媒体相结合的标准( r f c ) ，如h 2 6 3o v e rr t p ，i n t e r l e a v e d m e d i ao v e rr t p ，g e n e r a la u d i oo v e rr t p ，f e co v e rr t p 等。m p e go v e r r t p 的标准为r f c 2 25 0 ，该协议在r t p 对m p e g 的封装过程中，将m p e g 码流特征信息如时间戳、编码层次结构等拷贝到r t p 包头中，对m p e g 视频的解析和封装直达片层( s li c e ) ，从而使r t p 分组有很强的q o s 保 障，传输终端可通过r t p 包头分析传输中的差错( 丢失率、乱序、延迟 和抖动) ，再通过一定的缓冲和补偿算法，修复相当程度的网络差错。 随着r t p 协议族的成功应用，最新制定的多媒体标准也开始考虑同r t p 山东大学硕士学位论文 曼晕曼皇| 皇曼曼暑皇曼曼曼曼曼量曼曼曼舅量量量曼量一m _ l | 吕奠 协议的结合，m p e g 一4 标准中就涉及了r t p 封装和传输，同时i e t f 也 制定了针对m p e g 一4 的r t p 封装协议。除了r t p 协议以外，还有很多 其他支持多媒体的传输和控制协议，如r s v p ( 资源预留协议) 、r t s p ( 实 时流化协议) 等。 1 2 2 m p e g 标准 m p e g ( m o v i n gp i c t u r ee x p e r t sg r o u p ) 运动专家小组，在国际标 准化组织i s o i e c 的领导下，经过近十年卓有成效的工作，为多媒体 计算机系统、运动图像压缩编码技术的标准化和实用化，做出了巨大 的贡献。 目前，y p e g 一1 和m p e g - 2 都已作为正式的国际标准，并且备受广大 多媒体软件开发和硬件厂商的重视。支持m p e g 标准的软硬件产品纷纷 问世，市场竞争非常激烈。1 9 9 8 年又正式推出m p e g - 4 标准。此标准主 要应用于视频电话( v id e op h o n e ) 、视频电子邮件( y i d e oe - r e a l1 ) 和电 子新闻( e 1 e c t r o n i cn e w s ) 等。m p e g - 4 利用很窄的带宽，通过帧重建技 术压缩和传输数据，使得能够以最小的数据获得最佳的图像质量。 继m p e g - 4 之后，要解决的问题就是对日渐庞大的图像和声音信息 的管理和迅速搜索。1 9 9 8 年1 0 月基于这种设想的褂i p e g - 7 标准被提出， 它的正式名称是“多媒体内容描述接口，它将对各种不同类型的多媒 体信息进行标准化的描述，并将该描述与所叙述的内容相联系，以实 现快速有效地搜索。m p e g - 7 的应用范围很广泛，既可应用于存储( 在线 或离线) ，也可用于流式应用( 如广播、将模型加入i n t e r n e t 等) 。它 还可以在实时或非实时环境下应用，如数字图书馆( 图像目录、音乐字 典等) 、多媒体名录服务( 如黄页) 、广播媒体选择( 无线电信道、t v 信 道等) 等。在未来它将会在教育、新闻、导游信息、娱乐等各方面发挥 巨大的作用。 山东大学硕士学位论文 1 3 国内外多核并行计算发展现状 1 3 1 多核处理器的发展现状 从单核( si n g le - c o r e ) 到多核( y u l t 卜c o r e ) ，不仅仅是处理器核心 的数量的增多，对处理器体系架构，计算机整体架构，i o 到操作系统、 应用软件提出巨大的挑战。在双核处理器发展之前，商业化处理器一 直致力于单核处理器的发展，其性能已经发展到极致。但应用对c p u 资源的需求却远远超过c p u 的发展速度，单核也越来越难以满足要求， 其局限性也日渐明显。单核处理器的局限性主要表现在：1 、仅靠提高 频率的办法，难以实现性能的突破。当c p u 提高到4 g h z 时，几乎接近 目前c p u 的工艺极限。2 、并行化的要求提高，单一线程中已经不太可 能提高更多的并行性。主要有以下两个方面的原因：是不断增加的 芯片面积提高了生产成本；二是设计和验证所花费的时间变得更长。3 、 通过通用x 8 6 处理器构建大规模机群遭遇到前所未有的障碍。而目前 应用对集群的需要急剧增加，特别是对集群的处理能力的需要，通过 单核处理器构建10 万亿或更大规模的集群基本上没有可能。4 、功耗 性能比问题日渐突出。 在过去的几年里，微处理器的发展可谓是风起云涌，似乎在一夜 之间，处理器就进入了多核时代。首先是i n t e l 发布了d e m p s e y 双核 处理器，后来i n t e1 又发布了基于c o r e 微架构的w o o d c r e s t 处理器， 接着a m d 发布了第二代双核皓龙o p t e r o n 处理器，最后i n t e l 发布了 四核c 1 0 v e r t o w n 处理器。除此之外，一些嵌入式的多核处理器也发布 出来，意法半导体在2 0 0 4 年开发出集成一颗单独a r m 核的n o m a d i k 处 理器，并带有两个处理语音和视频子系统。预计在2 0 1 2 年可推出1 2 个子系统的产品。德州仪器相继推出d m 2 7 0 、d m 2 7 5 、d m 3 2 0 、以及 o m a p 2 4 2 0 、o m a p 5 91 0 等多媒体多核处理器，为便携式多媒体终端提供 了较好的解决方案。国内在多核处理器的研制上，处于比较落后的状 况，其中中科院计算所研发出了龙芯多核处理器。浪潮、华硕、联想 使用国外的核心，做出了自己的多核产品。 4 山东大学硕士学位论文 皇量曼量舅曼皇曼曼曼量曼舅邑| 曼量鲁曼曼曹鲁舅| 鼍i i | 曼皇曼毫曼量罾| 寡皇皇鼍量皇皇曼量量量曼量量| 皇曼曼一 1 3 2 多核计算机的操作系统 随着技术的不断发展，用户要求操作系统不但能进行并行处理，而 且还能适应不断变化的多种硬件环境和多种程序设计模型的需要，这 就产生了并行操作系统。比如，并行语言处理系统对并行操作系统就提 出了明确的要求。过去，语言处理系统生成很多关于程序的信息，这主 要是为了提高程序的执行效率。并行操作系统介入后，由于每个程序的 调度方法、数据配置各不相同，所以并行语言处理系统仅能看到由并行 操作系统提供的虚拟机的情况是很不够的。为提高执行效率，并行语言 处理系统需要了解程序占用了哪些硬件资源( 物理处理机、物理存储器 等) 。因而，并行操作系统必须向并行语言处理系统提供必要的硬件资 源分配的信息。 目前，实际运行的并行操作系统有y a c h 、c h o r u s 、t o p a z 、p s y c h e 、 t o p - 1o s 、s k y - 1 、o m i c r o n y 3 、m u s t a r d 等。比较有名的是m a c h ，c h o r u s 。 1 3 3 多核计算算法现状 并行算法是并行计算中非常重要的问题。并行算法研究应该确立 一个“理论一设计一实现一应用 的系统方法，形成一个完善的“架 构一算法一编程”方法论，这样才能保证并行算法不断发展并变得更 加实用。 1 并行算法简介 简单的说，算法就是求解问题的方法和步骤。并行算法，就是在 并行机上用很多个处理器联合求解问题的方法和步骤。实际上，在自 然界中并行是客观存在的普遍现象，关键问题在于能不能很好的利用。 由于人们的思维能力以及思考问题的方法对并行不太习惯，且并行算 法理论不成熟，所以总是出现了需求再来研究算法，不具有导向性， 同时实现并行算法的并行程序性能较差，往往满足不了人们的需求。 并行算法的研究历史可简单归纳为：上世纪7 0 到8 0 年代，并行算法 研究处于高潮；到上世纪9 0 年代跌入低谷；目前，又处于研究的热点 山东大学硕士学位论文 阶段。现在，人们已经可以自己搭建p ccl u s t e r ，利用学习到的理论 知识来解决实际问题，不再是纸上谈兵，这也为我们提供了新的机遇 和挑战。 2 并行算法的研究内容 并行计算模型并行算法作为一门学科，首先研究的是并行计算模 型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁， 是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行 机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模 型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。 并行算法是并行计算中非常重要的问题。并法研究应该确立一个 “理论一设计一实现一应用 的系统方法，形成一个完善的“架构一 算法一编程”方法论，这样才能保证并行算法不断发展并变得更加实 用。 并行计算模型的第一代是共享存储模型，如si m d - s m 和m i m d - s m 的一些计算模型，模型参数主要是c p u 的单位计算时间，这样科学家 可以忽略一些细节，集中精力设计算法。第二代是分布存储模型。在 这个阶段，人们逐渐意识到对并行计算机性能带来影响的不仅仅是 c p u ，还有通信。因此如何把不同的通信性能抽象成模型参数，是这个 阶段的研究重点。第三代是分布共享存储模型，也是我们目前研究所 处的阶段。随着网络技术的发展，通信延迟固然还有影响，但对并行 带来的影响不再像当年那样重要，注重计算系统的多层次存储特性的 影响。 设计技术并行算法研究的第二部分是并行算法的设计技术。虽然 并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的， 例如划分法、分治法、平衡树法、倍增法指针跳跃法、流水线法破对 称法等都是常用的设计并行算法的方法。另外人们还可以根据问题的 特性来选择适合的设计方法。 以上是并行算法的常规研究内容。随着时代的进步，我们需要不 断调整研究方向。目前并行算法研究的新走向是：并行算法研究内容 不断拓宽，并行计算被纳入研究范畴；与广大用户领域结合，注重应 用，强调走到用户中去，为用户解决问题；重视新的、非常规计算模 山东大学硕士学位论文 式，如神经计算、量子计算等，这些模式能够解决某类特定问题，有 其自身的优越性。 1 4 论文的组织安排 第一章对国内外多核技术的发展以及并行计算的发展现状进行了 简要的概括。第二章对传统的视频传输系统的总体架构进行了描述， 并就多核技术在视频传输系统中的应用进行了讨论。第三章对m p g e 4 的压缩编码进行了介绍，并对传统的压缩算法进行研究，分析了其中 的并行性。第四章对前面章节中得到的并行性进行实现。初步得到了 一个并行算法。第五章对多核中的并行计算提出了负载平衡的要求， 并对目前国内外的负载平衡算法进行研究，并尝试得到一个更高效的 动态负载平衡算法。第六章对于前面章节提出的并行算法以及负载平 衡算法进行了验证，证明该算法确实能够在某些方面提高整个视频传 输系统的效率，并且对以后的工作进行了展望。 山东大学硕士学位论文 第二章视频服务系统编码技术 本章介绍了m p e g 4 视频服务系统的整体架构及其编码技术，对帧 内压缩算法和帧间压缩算法进行了描述。详细描述m p e g 压缩算法中的 三种类型的图像：帧内图像、预测图像以及双向预测图像。最后，介绍 了与预测图像以及双向预测图像压缩密切相关的运动补偿预测机制。 2 1 视频服务系统整体架构 m p e g 视频算法基于运动补偿离散全余弦变换算法。这些算法在2 0 世纪8 0 、9 0 年代为专有的和标准的视频压缩技术而开发。采用基本块 结构，适用于不同信号。这些基本块是m p e g 视频算法取得高效压缩的 主要部分，但是其中还采用了许多特殊的技术增加效率和扩展性。m p e g 视频编码器的流程如图2 1 所示。 图2 一lm p e g 视频编码流程 图2 1 是传统的m p e g 编码的的流程，在这个过程中，运动估计部 分是整系统的瓶径，如果我们能够利用目前的多核技术，对其加以改 进，那么整个系统的效率将会得到很大的提升。图2 2 就是在传统m p e g 编码的基础上，加入了并行的因素，得出的一个整体的架构。 山东大学硕士学位论文 l 状取视频流 一视频流压缩卜_ 一 j 盘缩视频流传送全l 视频流服务器 多核并行压缩数据流 1 通过互连同络传递消息 2 通过苁享内存苁享幽像数掘 刨 圈圈圆 视 互连网络 频 源 i 未经压缩1 1 压缩中的ff 压缩完成i 视频流 剧 图像数据n 图像数据n 图像数据l 叫 服务器 帮 共享内存空间 图2 2 视屏传输系统总体架构 如图2 - 2 所示，我们所规划的视频传输系统分为三大部分：1 ) 视 频源获取部分2 ) 视频数据流压缩部分3 ) 视频流服务器。 本文将重点阐述第二部分视频数据流的压缩，我们将在对视频数 据流根据m p e g 4 标准进行压缩的同时，对其中用到的关键算法进行了 改造，使之成为适用于目前流行的多核硬件平台的多行并行算法。从 而提高整个系统的效率。 2 2m p e g 视频压缩算法 m p e g 视频压缩技术 6 , 7 , s 1 是针对运动图像的数据压缩技术。为了 提高压缩比，帧内图像数据压缩和帧图像数据压缩技术必须同时使用。 数据的压缩充分利用了时间和空间上的冗余信息。由表达式2 1 可以看 出，运动图像本身在时间上和空间上都含有许多冗余信息，图像自身 的构造也有冗余性。对电视图像的压缩，m p e g 主要采用了以下的一 些算法。 1 帧内压缩算法 采用与j p e g 压缩算法大致相同的算法 1 - 4 1 ，即基于d c t 的变换编 码技术，用以减少空间冗余信息。 2 帧间压缩算法 帧间压缩算法包括预测法、差补法和运动补偿算法，其中预测法 有因果预测器( 纯粹的预测编码) 和非因果预测( 即差补编码) 。预测误差 可以再通过d c t 变换编码处理，进一步压缩。帧间编码技术可以减少 9 山东大学硕士学位论文 时间轴方向的冗余信息。运动补偿压缩和编码删除了一些即使缺少了 它们也不会显著破坏大脑和眼睛对图像感知的帧。 表2 1 视频压缩利用的冗余信息 种类 内容目前用的主要方法 统计空间冗余像素间的相关性变换编码，预测编码 特性时间冗余时间方向上的相关性 帧间预测，移动补偿 图像构造冗余图像本身的构造轮廓编码，区域分割 知识冗余收发两端对人物基于知识的编码 的共有认识 视觉冗余人的视觉特性基于知识的编码 其他不确定性因素 2 3 宏块简介 i 鬻! 竺一 卜一图片组叫 口口口口口口口口口口口 图片 块 图片切片宏块 ji 一r 1 1 1 ，n 伤 r 卜+ 7 京 1 一 8 图2 - 3m p e g 数据流结构 对数字化采样后的图像序列，进行m p e 6 编码处理时，要经过如图 2 - 3 所示的数据结构的转换。 ( 1 ) 运动图像序列 运动序列包括一个表头、一组或多组图像序列结束标志码。 ( 2 ) 图像组 图片组由一系列的图像组成，可以从运动序列中随机存取。 山东大学硕士学位论文 ( 3 ) 帧 m p e g - 1 将视频表示为一系列的帧。每帧的3 个表示像素的矩形矩 阵。一个为亮度( y ，黑和白) ，另两个为色度( c r 和c b ，颜色的差异) ， 亮度和色度定义从c c i r - 6 01 标准中来，该标准是表示未压缩视频的国 际标准。 m p e g - 1 的色度矩阵由两个与亮度矩阵关联的垂直与水平的分量进 行采样。其采样关系如图2 - x 所示。 口口口口口口口亮度 y 色度 口口口口口口口 口口口口口口口 口口口口口口口 _ x 图2 - 4m p e g - 1 色度与亮度采样关系 ( 4 ) 图像切片 图像切片由一个或多个连续的宏块构成。 ( 5 ) 宏块 每个图片帧被分成都市16x1 6 的块，每个块由4 个8x 8 ( y ) 亮度块 和2 个8 8 ( c b 和c r ) 色度块组成。这一组6 个块称为宏块，是用于获 得高水平压缩的基本分层部件，如图2 5 所示。 yuv 12 34 团圈 8 x 88 x 8 图2 - 5 宏块的组成 ( 6 ) 块 一个块由一个8x 8 的亮度信息或色度信息组成。 山东大学硕士学位论文 2 4 运动补偿预测 1 运动补偿的概念 运动补偿( m o tio nc o m p e n s a t io n ) 实际上是在对活动图像进行压缩 时所使用的一种帧间编码技术。所谓“活动图像 实际上是一系列静 止图像的连续排列，当它们以不小于2 4 f p s s 的速率连续显示时，由 于人眼的视觉有暂留特性，会使人产生了连续活动的感觉，因此一般 情况下，相邻帧间的内容实际上没有太大的变化( 场景切换除外) ，有很 大一部分甚至是完全一样的，所以相邻帧间有较大的相关性，这种相 关性称为时域相关性。运动补偿的目的正是要将这种时域相关性尽可 能去除。 2 运动补偿的基本原理 运动补偿的基本原理简述如下，当编码器对图像序列中的第n 帧进 行处理时，利用运动补偿中的核心技术一运动估计m e ( m o ti o ne s t i m a t io n ) ，得到第n 帧的预测帧n 。在实际编码传输时，并不总是传输 第n 帧，而是第n 帧和其预测帧n 的差值a 。如果运动估计十分有效， 中的概率基本上分布在零的附近，从而导致比原始图像第n 帧的能 量小得多，从而传输所需的比特数也就少得多，这就是运动补偿技术 能够去除信源中时间冗余度的本质所在。 运动补偿预测技术通常由以下几方面组成： 首先把图像分割为静止和运动的两部分，这里假设运动物体仅 做平移。 估计物体的位移值。 用位移估值进行运动补偿预测。 预测信息编码。 图像分割是运动补偿预测的基础，但实际上要把图像分割成不同 运动的物体比较困难，通常采用两种较简单的方法，一种把图像分为 矩形子块，适当选择块的大小，把子块分为动和不动两种，估计出运 动子块的位移，进行预测，如在m p e g 中，就是基于1 6 1 6 子块的算法， 将每个子块做为一个二维的运动矢量进行处理；另一种方法是对每个 像素的位移都进行递归估计，因此，在对图像的分割作了必要的简化 山东大学硕士学位论文 后，对运动子块的估计或者说运动估值m e ，因此，在对图像的分割做 了必要的简化后，对运动子块的估计或者说运动估值m e ，就成为必须 解决的关键技术。得到了运动物体的位移估值后，即可送入m c 预测器 和一切预测编码一样，输出入到预测器的数据都要用图像恢复数据， 即原始输入为n ，预测值为n ，二者之差经过量化后为，图像恢 复数据为s o = n + ，与原始数据s o 相比含有量化误差q o = a 一。 把恢复数据送进运动参数估值器后就得到运动位移的估值，有了运动 位移参数和前帧复原数据，就可以作出当前像素的预测值。 2 5m e p g 帧图像类型 在m p e g 中将图像分为3 种类型，下面将进行详细介绍。 1 i 图像( i n t r a p i c t u r e s ，帧内图像) i 图像是利用图像自身的相关性压缩，提供压缩数据流中的随机存 取点，采用基于d c t 的编码技术，编码不需要其他帧的图像作参考， 这些帧图像为译码器提供随机存取点，是预测图像( p ) 帧和双向预测图 像( b ) 帧的参考图像，所以压缩率不高，压缩后每个像素为1 - 2b i t 。 2 p 图像( p r e d i c t e dp ic t u r e s ，预测图像) p 图像是参考过去的帧内图像或者过去得到的图像用运动补偿预 测技术进行编码，这些预测图像通常做为进一步预测的参考，预测图 像的编码效率较高。 3 b 图像( b i d i r e c ti o n a lp r e d i c ti o n ，差补图或双向预测图像) b 图像在预测时，既可使用前一个图像作参照，也可使用下一个图 像作参照或同时使用前后两个图像做为参照图像( 双向预测) ，它的压 缩率最高，但双向预测图像不做为预测的参考图像。 在图2 6 中用箭头表示了这3 种图像之间的关系。共采用了4 种技术。 帧内编码： 前向预测： 后向预测： 双向预测。 山东大学硕士学位论文 前向预测 2 6 小结 图2 - 6 帧间编码 本章概括性地介绍了m p e g 4 视频服务系统的整体架构及其编码 技术，对其中用到的帧内压缩算法和帧间压缩算法进行了介绍。介绍 了m p e g 压缩算法中的三种类型的图像：帧内图像、预测图像以及双向 预测图像。并详细地介绍了与预测图像以及双向预测图像压缩密切相 关的运动补偿预测机制。 1 4 山东大学硕士学位论文 第三章m p e g 4 编码及并行性分析 在前面章节中，已经详细描述了m p e g 标准中涉及的基础知识。在 这个基础上，本章对m p e g 中所涉及到的算法进行了细致深入的研究。 研究结果表明，在帧内图像和帧间图像中都存在着很多数据无关的内 容，而算法上也潜在着很多并行性，本章对这些并行性给出了详细的 描述。 3 1 帧内编码及并行性分析 3 1 1 帧内图像压缩算法 帧内图像( i 帧图像) 不参照任何过去的或者将来的其他图像帧，压 缩编码采用类似j p e g 压缩算法。如果电视图像是用r g b 空间表示的， 则首先把它转换成y u v 空间表示的图像。每个图像平面分割成8 8 的 图块，对每个图块进行离散余弦变换d c t ( d is c r e t ec o s i n et r a n s f o r m ) 【3 1 7 】。d c t 变换后经过量化的交流分量系数按照z i g z a g 的形状 排序，然后再使用无损压缩技术进行编码。d c t 变换后经过量化的直流 分量系数用差分脉冲编码d p c m ( d i f f e r e n t i a lp u ls ec o d em o d u l a t i o n ) ，交流分量系数用游程编码r l e ( r u n - l e n g t he n c o d i n g ) ，然后再 用霍夫曼( h u f f m a n ) 编码或者用算术编码。 帧内图像压缩编码的伪代码如下： 算法1 i 帧图像压缩的串行伪代码 1 将y 、u 、v 三个分量的数据分配到三个独立的缓冲区中， 并且将这些数据分割为8 * 8 的数据块：