（计算机系统结构专业论文）基于多项式变换的运动估计算法及其应用研究.pdf

摘要+y5 7 8 9 9 _ 0数字视频具有数据量大、实时性要求强等特点，因此需要视频压缩技术以及有效的算法实现实时计算。运动估计与补偿和变换编码是实现视频高压缩比的关键，基于对象的视频压缩算法进一步提高了压缩比。此外，由于基于对象的压缩算法的人机交互性能的提高，凶而视频技术可以更好地应用于视频监控、交通管理、远程医疗、视频会议等领域。本文针对视频编码的计算效率问题，对运动估计的快速算法进行了研究，提h 了基于多项式变换的运动估计算法；为提高运动补偿帧差图像的变换编码效率，提出了一种运动补偿帧差图像的预测处理技术；此外还提出了块运动矢量加权的s n a k e s 模型，以实现视频对象分割。基于多项式变换的运动估计算法是本文新提出的一种块匹配运动估计算法，即保持了简单而易于硬件实现的特点，同时极大地提高了计算效率。在这部分研究中，对运动估计快速算法的研究现状、运动估计算法的匹配模型、匹配准则、快速算法的实现原理进行了分类总结；并从系统的角度出发，导出了块匹配的循环卷积算法，这种分析方法对研究新的运动估计快算法具有指导意义。利用多项式变换计算循环卷积，能较大地节省计算量，特别是乘法的计算量。基于多项式变换的运动估计算法中需要对当前块中的信号进行延拓，造成块内信号中很多采样点的值为零，利用信号的这一特点，设计了改进的快速多项式变换( m f p t ) 算法。文中除了对计算复杂度进行了理论分析外，还进行了详尽的实验比较。实验结果表明，与当前主要的运动估计算法相比，基于多项式变换的运动估计算法是高性能的运动估计算法之一。在般情况下，基于多项式变换的运动估计算法的执行时间为全搜索算法的9 1 8 ，这与最好的运动估计算法( s e a 、w i n n e r - u p d a t e 算法) 的性能相当，高j 二其它算法的性能。在h 2 6 4 标准中采用了s p i r a l 搜索算法，本文提出的算法的性能优于s p i r a l 搜索算法。实际的视频应用系统中，噪声的影响几乎是不可避免的，常见的噪声类型是高斯噪声和椒盐噪声。对测试图像序列施加这两种噪声后进行运动估计算法的比较，发现轻微的噪声使得w i n n e r - u p d a t e 、s p i r a l 等算法的性能急剧f 降，而基于多项式变换的运动估计算法则不受噪声影响。在噪声环境下，该算法比时间特性最好的w u s 算法以及s p i r a l 算法快2 1 0 倍。因此，基于多项式变换的运动估计算法的适+ 奉史研究t 作秩得同家高科技8 6 3 计划f 编号2 0 0 2 a a i1 9 0 1 0 ) 资助审乏p j “、譬都淄敷1勃童艾公布用性很高，是丈际的视频编码器的很好选择。运动补偿与变换编码是当前视频压缩的主流技术，高精度的运动补偿使得运动补偿帧差( m c f d ) 图像中像素灰度值趋于一致，并且数值较小，有利于提高变换编码的效率。但是，在运动图像序列中，往往存在背景被遮挡的区域，这些区域的运动补偿精度比其它区域低得多，造成在m c f d 图像中，遮挡区域存在狄度值的突变。在分析m c f d 图像特点的基础上，提出了一种m c f d 图像的后处理技术，进行了原理分析和实验验证。阱l s 预测算法作为m c f d 图像的预测处理技术，可以使处理后的图像灰度分伽变得平缓，减少像素点问的相关性，经d c t 变换后能量更加集中。与t m n 8 测试模型比较，编码帧的信噪比提商了o 2 0 5 d b 。图像分割是计算机视觉的基本问题，学者们划其进行了深入的研究，各种分割的理论和方法彳i 断被提出。自m p e g 一4 标准颁布后，图像分割作为实现m p e g 4 标准的基本技术环节，引发了更加广泛的关注。经典的s n a k e s 模型具有丌放的、统一的架构，在此基础上，为了分割复杂背景的序列图像，产生了各种改进的s n a k e s 模型，但都存在着不足：计算量大、需要先验知识、易受光流计算精度影响等。针对这些缺点，提出了块运动矢量加权的s n a k e s 模型，可以用于复杂背景序列图像的分割。这种模型以图像中的边缘信息为分割的最终依据，结合块运动估计的结果，增强了序列图像分割的鲁棒性。根掘运动场估计的结果在该模型中所超的作用，提出了边缘优先的块运动估计算法，大大减少了计算量。用块运动矢量加权的s n a k e s 模型分割复杂背景序列图像，取得了好的分割结果。关键词：运动估训；快速算法；图像分割：变换编码j ia b s t r a c t +d i g i t a lv i d e oi sg e n e r a l l yc o m p r e s s e di nt h ea c t u a la p p l i c a t i o n sb e c a u s eo fi t sg r e a td a t aq u a n t i t ya n dr e a l t i m ep r o p e r t i e s m o t i o ne s t i m a t i o na n dc o m p e n s a t i o na n dt r a n s f o r mc o d i n gp l a yi m p o r t a n tr o l e sf o rg e t t i n gh i g hc o m p r e s s i o nr a t i oo fd i g i t a lv i d e o ，a n do b j e c tb a s e dc o m p r e s s i o na l g o r i t h mp r o m o t e sc o m p r e s s i o nr a t i of u r t h e rm o r e i nt h em e a nt i m e ，d i g i t a lv i d e oc o m p r e s s e db yo b j e c tb a s e dc o m p r e s s i o na l g o r i t h mi sav e r yp r o p e rc a n d i d a t ef o rv i d e o c o n f e r e n c e ，t r a f f i cm a n a g e m e n t ，v i d e os u r v e i l l a n c e ，t e l e n m d i c i n e ，e t c ，b e c a u s et h ev i d e oi sc o n v e n i e n tt oh u m a n c o m p u t e ri n t e r a c t i o n a no v e r v i e wo ff a s ta l g o r i t h m sf o rm o t i o ne s t i m a t i o ni sp r e s e n t e d ，a n dap o l y n o m i a lt r a n s f o r mb a s e dm o t i o ne s t i m a t i o na l g o r i t h mi sp r o p o s e d ，ap r e t r e a t m e n tt e c h n i q u ei sp r e s e n t e df o rm o t i o nc o m p e n s a t i o nf l a m ed i f f e r e n c ei m a g e ，w h i c hc o n d u c e st op r o m o t et h ee f f i c i e n c yo ft r a n s f o r mc o d i n g ，i nt h ed i s s e r t a t i o n ，ab l o c km o t i o nv e c t o rw e i g h t e ds n a k e sm o d e li sp r e s e n t e dt or e a l i z ev i d e oo b j e c ts e g m e n t a t i o n p o l y n o m i a lt r a n s f o r mb a s e dm o t i o ne s t i m a t i o na l g o r i t h mi san e wb l o c km a t c h i n ga l g o r i t h m ，i tp r o m o t e sc o m p u t a t i o ne f f i c i e n c yb yc a l c u l a t el i n e a rc o r r e l a t i o no fb l o c k s t h ea d v a n t a g e so ft h ea l g o r i t h ma r es i m p l i c i t y , c o n g r u e n t ，a n di ti se a s yt or e a l i z eo nt h ep l a t f o r mo fh a r d w a r e f i r s t ，ar e v i e wo ft h ec u r r e n t l yk n o w nf a s tf u l ls e a r c hb l o c km o t i o ne s t i m a t i o na l g o r i t h m si sg i v e n ，t h ec u r r e n t l yk n o w nm a t c h i n gm o d e l s ，m a t c h i n gc r i t e r i o n s ，t h e o r i e so ff a s tm o t i o ne s t i m a t i o na r ed i v i d e ds o m ec a t e g o r i e sa n di n t r o d u c e db r i e f l y s e c o n d ，c o n v o l u t i o nb a s e db l o c km a t c h i n ga l g o r i t h mi sd e r i v e db yt h es y s t e mm e t h o d ，w h i c hi sh e l p m lt od e v e l o ps o m eo t h e rn e wf a s tm o t i o ne s t i m a t i o na l g o r i t h m ag r e a td e a lo fc o m p u t a t i o nl o a d ，e s p e c i a l l ym u l t i p l i c a t i o nc o m p u t a t i o nl o a d ，i ss a v e dw h e nc o n v o l u t i o ni sc o m p u t eb yp o l y n o m i a lt r a n s f o r m ，t h e r e f o r e ，p o l y n o m i a lt r a n s f o r mb a s e dm o t i o ne s t i m a t i o na l g o r i t h n ac a np r o c e s sb l o c km a t c h i n gv e r yf a s t i nt h i sa l g o r i t h m ，t h es i g n a li nt h ec u r r e n tb l o c kn e e dt ob ee x t e n d e dt ot h es i z eo fs e a r c hr a n g ea n dm a n yz e r os a m p l e sa r ea d d e d ，a c c o r d i n g l y ，am o d i f i e df a s tp o l y n o m i a lt r a n s f o r ma l g o r i t h mi sp r o p o s e di nd e t a i lt op r o m o t et h ec o m p u t a t i o ne f f i c i e n c yo fp o l y n o m i a lt r a n s f o r m t h ec o m p l e x i t i e so fa l la l g o r i t h m sa r eg i v e n ，a n de x p e r i m e n t a lr e s e a r c hi sd o n et o o 1 _ er e s e a r c hw a ss u p p o r t e di np a r tb yt h en a t i o n a lh i g ht e c h n o l o g yr e s e a r c ha n dd e v e l o p m e n tp r o g r a mo f c h i n a( 8 6 3p r o g r a m ，n o2 0 0 2 a a1 19 0 10 )e x p e r i m e n t a lr e s u l t si n d i c a t et h a tp o l y n o m i a lt r a n s f o r mb a s e dm o t i o ne s t i m a t i o na l g o r i t h mi se q u i v a l e n to re v e nb e t t e rt h a nw h a ti sa c h i e v e dw i t hc o n v e n t i o n a lm e t h o d s ，i t sc o m p u t a t i o nl o a di sa b o u t9 - 18 o ff u l ls e a r c ha l g o r i t h mi nt h ec o m m o nc a s ea n di t sp e r f o r m a n c ei sc o m p a r a b l et os e ao rw i n n e r - u p d a t ea l g o r i t h m t h ea f f e c t so fn o i s e ，i n c l u d i n gg a n s s i a nn o i s em a ds a l t & p e p p e rn o i s e a r ei n e v i t a b l ei na c t u a ls y s t e m s w h e nt e s ts e q u e n c e sa r ea d d e dn o i s e ，e v e nav e r yl i t t l en o i s e ，t h ep e r f o r m a n c e so fw i n n e r - u p d a t ea n ds p i r a la l g o r i t t u nd r o p sg r e a t l y , w h i l et h ep e r f o r m a n c eo fp o l y n o m i a lt r a n s f o r mb a s e dm o t i o ne s t i m a t i o na l g o r i t h mi sa ss a m ea st h ef o r m e rr e s u l t s i ts h o w st h a tt h en e wa l g o r i t h mh a se x c e l l e n ta n t i n o i s ep r o p e r t ya n da p p l i c a b i l i t y t h ep e r f o r m a n c eo fp r o p o s e da l g o r i t h mi sb e t t e rt h a no n e so fs p i r a la l g o r i t t m a ，w h i c ha d o p t e db yh 2 6 4s t a n d a r d e x p e r i m e n t a l l y , t h ep r o p o s e da l g o r i t h mr e q u i r e sa b o u t1 2 m l oc o m p u t a t i o no f b o t ha l g o r i t h m ap r e d i c t i o n - p r o c e s s i n ga l g o r i t h mu s i n gl e a s t - s q u a r e ( l s ) - b a s e dp r e d i c t i o ns c h e m e sf o rm o t i o n c o m p e n s a t e df r a m ed i f f e r e n c e ( m c f d ) i m a g e si sp r e s e n t e d m o t i o nc o m p e n s a t i o nf o l l o w e db yt r a n s f o r mc o d i n gt e c h n i q u e sp l a ya ni m p o r t a n tr o l ei na c h i e v i n gh i g hc o m p r e s s i o nb yr e d u c i n gt h et e m p o r a lr e d u n d a n c yi n h e r e n ti nv i d e os e q u e n c e s i ti sw e l lk n o w nt h a tt h eb e s to ft r a n s f o r mc o d i n gs h o u l dp r o d u c eu n c o r r e l a t e dc o e f f i c i e n t s ，a n dp a c kt h em a x i m u ma m o u n to fe n e r g yi n t ot h es m a l l e s tn u m b e ro fc o e f f i c i e n t s ，b u tt h et r a n s f o r me f f i c i e n c yi sd e c r e a s e df o rt h ep r e c i s i o no fm o t i o nc o m p e n s a t i o ni sm u c hl o w e ri nc o v e r e d u n c o v e r e dr e g i o n st h a nt h eo t h e rr e g i o n s g e n e r a l l y , t h e r ee x i s taf e wd r a m a t i c a l l yi n c r e a s e dg r a yl e v e l so fp i x e l si naf e wr e g i o n so fm c f di m a g e ，a n dt h e s ep i x e l ss h o wo b v r i o u sd i r e c t i o n a l i t y , w h i c ha d dp l e n t i f u lf r e q u e n c yc o m p o s i t i o n st of r e q u e n c yd o m a i no fm c f di m a g e s ，a n di n c r e a s et h eq u a n t i t yo fn o n - z e r oc o e f f i c i e n t si nt h ed i s s e r t a t i o n ，ap r e d i c t o rw a su s e df o ram c f di m a g et or e d u c et h ei n h e r e n ts p a t i a lc o r r e l a t i o ni nam c f di m a g e ，a n dt h ep r e d i c i o n p r o c e s s e dm c f di m a g ei ss m o o t h e rt h a no r i g i n a lo n e ，t h i sc a ni m p r o v et h ee f f i c i e n c yo ft r a n s f o r mc o d i n gl a r g e l y t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a td c tt r a n s f o r mi sm o r ee f f i c i e n tf o rp r e d i c t i o n - p r o c e s s e dm c f di m a g e st h a no r i g i n a lo n e s ，w ec a na c h i e v eag a i ni np s n ro f0 2 0 5d bt h a nt m n 8i nt h es a m eb i tr a t e h n a g es e g m e n t a t i o ni sa ni m p o r t a n tp r o b l e mo fc o m p u t e rv i s i o n ，ag r e a td e a lo fr e s e a r c h e sa b o u ti th a v eb e e nd o n ei nr e c e n ty e a r s m o r ea n dm o r ea t t e n t i o ni sf o c u s e do nt h ei m a g es e g m e n t a t i o nt e c h n i q u ea f t e rm p e g 一4s t a n d a r dh a sb e e ni s s u e d s n a k e sm o d e l ，w i t ha no p e na n du n i f o r mf r a m e w o r k ，i sa ne l e g a n tt o o lf o ri m a g es e g m e n t a t i o n t h ea c t i v ec o n t o u rc a nc o n v e r g ed y n a m i c a l l yt ot h eb o u n d a r yo ft h em o v i n go b j e c ti nas e q u e n t i a li m a g eb yc o n s t r u c t i n ga ne x t e r n a lf o r c ep r o p e r l y a tp r e s e n t ，m a n ym o d i f i e ds n a k e sm o d e li sp r e s e n t e df o rs e q u e n t i a li m a g es e g m e n t a t i o n ，b u tt h e yh a v ev a r yd e f i c i e n c ys u c ha sh i g hc o m p u t a t i o n a lc o m p l e x i t nr e q u i r i n gp r i o rk n o w l e d g e ，l i m i t i n gb yt h ep r e c i s i o no fo p t i c a lf l o wf i e l da n ds oo n t h es n a k e sm o d e lp r e s e n t e di nt h ep a p e ro v e r c o n l et h e s es h o r t c o m i n g ，c a l ls e g m e n ts e q u e n t i a li m a g ee f f e c t i v e l y t h ei n f o r m a t i o no fe d g ei sv i t a li m p o r t a n tf o ri m a g es e g m e n t a t i o n ，s oi ti st h ef o u n d a t i o no fc o n s t r u c t i n ge x t e r n a lf o r c e i nt h em e a nt i m e ，w ei n c o r p o r a t et h ek i n e t i ci n f o r m a t i o n ，g o t t e nb ym o t i o ne s t i m a t i o n ，i n t os e q u e n t i a li m a g es e g m e n t a t i o n ，t h e r e f o r e ，t h en o v e ls n a k e sm o d e li sa p p l i c a b l ef o rt h es e q u e n t i a li m a g ew i t hc o m p l e xb a c k g r o u n d f u r t h e r m o r e ，a ne d g e f i r s tb l o c kb a s e dm o t i o ne s t i m a t i o ni sp r o p o s e da c c o r d i n gt oi t sr o l ei nt h eb l o c k m o t i o nv e c t o rw e i g h t e ds n a k e sm o d e l ，w h i c hr e d u c e st h ec o m p u t a t i o n a ll o a de v i d e n t l yf i n a l l y , t h ep r o m i s i n ge x p e r i m e n t a lr e s u l t sa r ep r o v i d e dt oi l l u s t r a t et h ev a l i d i t yo ft h eb l o c k m o t i o nv e c t o rw e i g h t e ds n a k e sm o d ef o rs e q u e n t i a li m a g es e g m e n t a t i o n k e y w o r d s ：m o t i o ne s t i m a t i o n ：f a s ta l g o r i t h m ；i m a g es e g m e n t a t i o n ；t r a n s f o r me n c o d i n gv1 绪论随着仓业的国际环境变得日益复杂，竞争与协作成为企业生存与发展的两大主题，如何及时高效地获取信息成为至关重要的问题。多媒体和通信技术的迅猛发展，使得多媒体相关服务进入了生产和生活的诸多领域。会议电视、远程医疗、交通监控、视频点播、可视电话以及多媒体教育与娱乐等在很大程度上改变着社会面貌和个人生活。为了保持运动图像显示的连续性，每秒钟要播放足够多的帧数( 如电视每秒2 5 帧) ，这样运动图像未经压缩的数据量很大( 对每秒2 5 帧的电视图像序列，未压缩视频的码率为2 2 m b i t s ) ，存储和传输这种未压缩的视频数据是困难的。目前，通过i n t e r n e t 传输文字和静态图片等媒体信息的技术已经达到实用化的程度，为商业管理、工业生产、生活学习提供了便利。但是，由于视频等媒体信息具有数据量大的特点，如何在当前i n t e m e t所能提供的带宽范围内提供视频服务，仍然是一项挑战和迫切的任务。其技术难点归结为在低带宽、不可靠信道上传输视频流，并保证一定的重构质量。视频媒体的存储和传输，必需应用视频压缩技术来降低对存储空间和带宽的需求。运动估计与补偿技术是视频压缩技术的关键，因为它充分利用了视频序列间的相关性强的特点，获得高压缩比。获得广泛应用的视频压缩标准如m p e g 1 2 4 、h 2 6 x 等，无一例外地采用了运动补偿和变换编码技术来获得高压缩比。近几年来，p d a 、p o c k e tp c 等手持设备的技术和市场的发展势头迅猛，如何为这些新兴的上嘲装置提供视频服务，成为一个具有重大意义的研究热点。众所周知，手持式设备的体积小、能耗低，该特点制约了其计算能力的提高。因此，为手持设备提供视频服务，必须研究如何降低视频编码器的计算复杂度。因此，研究低比特率视频编码技术，包括压缩解压技术、运动估计与补偿技术、视频分割技术等，均是解决上述技术难点的关键。下面将对以上问题进行研究和分析。1 1 运动估计快速算法的研究背景、目的和意义11 1 数字视频压缩系统的组成数字视频的应用范围正变得越来越广泛，随着网络技术的发展，通过网络传输数字视频的需求不断增长，此外，移动电话的普及促使人们研究在无线信道上传输视频的技术。典型的视频传输系统如图1 1 所示。多媒体终端可以是移动电话、个人电脑等，视频信号经过信源编码和信道编码处理后，通过传输信道传送到目标终端。传输信道可以是无线电信道或者因特网等。通常的视频应用经常需要相互传递视频信号，这样，每个终端都成对地各有编解码器。用尸图1 1 腆型的视频传输系统视频传输过程中存在信道的低带宽和视频的大数掘量的矛盾，因此，视频压缩技术的应用成为必然，以减少目标比特流的码率，降低带宽需求。帧内压缩采用类似静态图像压缩的算法，通常视频信号的压缩比远高于静态图像的压缩比，这是因为视频帧之间有很强的相关性，通过运动估计孑补偿处理，极大地减少了帧间的数据冗余。典型的视频编解码器如图1 2 ( a ) f f r l 图1 2 伯) 所示。1 1 2 数字视频压缩的协议由于视频压缩技术的多样性，为了终端之间能够互相交换信息，必须遵循一定的协议。在视频压缩领域，主要存在两个系列的标准，分别出国际电信联盟( i t u ) 和冈际标准化组织o s o ) 制定。2 0 0 3 年3 月颁布的a v c ( a d v a n c e dv i d e oc o d i n g ) ；b j i 准，由i t u 和2i s o 共同制定，在i t u 协议系列中称为h 2 6 4 ，在i s o 协议系列中，则编入m p e g - 4 ( p a r tl o ) 中。国家标准的制定工作j 卜在进行中，工作组名称为“数字音视频编解码技术标准工作组( a u d i ov i d e oc o d i n gs t a n d a r dw o r k g r o u po fc h i n a ，a v s ) ”，其技术指标不低于h 2 6 4 ，计划在2 0 0 3 年底制定标准草案，有望在2 0 0 4 年成为国家标准。原始帧( a ) 编码器( b ) 解码器图1 2 视频编j 解码器的一般流程 t u 在1 9 9 0 年完成了h - 2 6 1 协议并验证通过，它允许在p x 6 4 k b i t s 的信道l 传输视频，它适用的传输网络是综合业务数字网( i s d n ) 1 2 | 。为了获得更低码率的比特流，i t u在1 9 9 6 年颁布了h 2 6 3 协议3 i ，并在1 9 9 8 年进一步修订了该协议，由于应用了半像素运动估计等新技术，视频压缩质量得到了提高。在h 2 6 1 协议中，宏块尺寸为1 6 x 1 6 ；在h 2 6 3 协议中，宏块尺寸可以为1 6 1 6 或8 x 8 两种。在最新的h 2 6 4 一引| 办议中，运7 日动估计允许7 种子块模式及多帧模式，其压缩质量超过m p e g 一4 。一与h 2 6 3 + + ，l 叮以用于无线信道的视频传输。i s o 的运动图像专家2 h ( m p e g ) 于1 9 9 0 年完成了m p e g - 1 协议的制定，该协议于1 9 9 2 年成为圈际标准。m p e g 1 的目标比特率是1 5 m b i t s s ，适合交互式视频应用以及光盘存贮。该标准同时也包括了伴旨编码部分。m p e g 一1 与h 2 6 1 的运动什计与补偿技术采用的块尺寸相同；与h 2 6 1 不同的是，m p e g 1 采用双向运动估计与补偿技术米提高运动补偿的精度。1 9 9 4 年颁布了m p e g 一1 的修订版本，称为m p e g 一2 ，压缩视频的质量得到提高，同时目标比特率也高于m p e g 一1 ，达到了2 3 0 m b i t s s ，适合数字电视和高速网络应用。最新的m p e g 4 标准于1 9 9 9 年通过验证，该标准提供了极低比特率f 8 3 2 k b i t s s ) 视频通讯的标准，适合视频的无线互联网应用。m p e g 4 标准也提供了应用于高带宽( 4 m b i t s s ) 场合的机制。a v s 工作组的任务是组织制定行业和国家信源编码技术标准，该标准面向的应用包括数字电视、激光视盘、网络流媒体、_ ： 云线流媒体等领域。a v s 是一套适应而i 分广阔的技术标准，优势表现在以下几个方面：( 1 ) a v s 是基于我国自主创新技术和国际公丌技术所构建的自主标准，妥善解决了知识产权问题；( 2 ) 编码效率高，比m p e g 一2 国际标准高2 3 倍( 高清晰度电视可达到3 倍或更多) ；( 3 ) 计算复杂度低，硬件实现成本较低。( 4 ) a v s 可节省一半以上的无线频谱和有线信道资源，显著降低传输、存储设备与系统的经济投入。为了达到以e 的目标，一个非常重要的方面就是制定运动估计弓补偿方面的新规范。数字视频耿得高压缩比的关键在于视频帧之间存在很多冗余，而运动估计与补偿技术是减少这种冗余最有效的手段。因此，研究运动估计与补偿技术是数字视频的重要研究内容，对数字视频压缩标准的制定具有重要意义。我们课题组作为a v s 研究组成员之一，进行了运动估计方面的研究，并提交了一些相关提案。此外，清华大学贺玉文、北京工业大学沈兰荪、中科院计算所高文、吴枫等也在进行相关研究。在上述协议中，运动估计与补偿算法是其核心之一，补偿后的帧差图像中，大部分的像素灰度值较小，有利于变换编码。运动估计与补偿对目标比特流的码率和视频质量的影响很大。在协议中涉及的运动估计与补偿规范涵盖了两部分内容：1 ) 提高运动估计的精度，降低压缩比特流的码率。在多媒体网络应用迅速发展的今灭，为了突破网络带宽瓶颈的限制，高精度的运动估计与补偿算法是一个有效的手段。2 ) 运动估计的快速算法，减少运动估计的时间。算法的高效性决定其实用性，特别地，因为视频应用的实时性要求，高效的运动估计算法显得很必要。11 3m p e g - 4 与视频序列图像分割m p e g 经过调查发现两个发展趋势，第一个是通用芯片的性能提高和价格降低使得基于软件平台的压缩方法成为可能，基于物体和对象的压缩方法多了起来；第一：个是应用需求的变化，人们对多媒体信息特别是视频信息的应用需求从单纯的播放转向基于内容的访问与操作。针对这种发展趋势，m p e g 制定了m p e g 4 标准，正式名称为“视听对象的编码”( c o d i n go f a u d i o v i s u a lo b j e c t s ) 。与m p e g 一1 和m p e g 一2 不同，m p e g 一4 不是针对一定比特率下的视频、音频编码，而是更注重多媒体系统的交互性和灵活性。m p e g 一4 的特点是更适用于交互a v 服务以及远程监控。m p e g 一4 是一个让用户由被动变为主动的动态图像标准，用户不再只是观看，允许用户的交互存在；它的另一个特点是其综合性，m p e g 4 希望将自然物体与人造物体在视觉效果上相互融合。m p e g 4 采用了基于内容的访问与操作，在压缩数据中加入描述视频内容的信息，从而使多媒体信息内容的访问可以直接针对压缩数据进行。m p e g - 4 是一种基于内容的压缩编码方法，它提供了对视频对象、音频对象、情景描述咀及发送系统的接口进行编码的标准方法。虽然基于内容的编码可以提高压缩比，降低带宽需求，实现交互式多媒体应用，但是要实现视听对象的编码，首先要从视频流中分割对象。基于内容的视频检索也提出了基于对象这一更深层次的要求。由此可见，视频对象的分割是m p e g 4 中的关键投术。由于视频分割的复杂性，目前视频分割还没有成熟的理论和方法。1 1 4 运动估计算法的复杂性基于分块的运动估计算法，具有简单且易于硬件实现的特点，被绝大多数视频编解码器所采用。即使如此，基于分块的运动估计直接算法仍然需要巨大的计算量。在基于分块的运动估计算法中，当前视频帧被划分成图像块，然后在参考帧中寻找与每个图像块最相似的分块，这样就必须建立一个匹配准则。一般地，运动估计需要事先给定块尺寸和搜索窗口的大小，然后采用一定的匹配准则来寻找最佳的块运动矢量，如图13所示。( a ) 半前帧) 参考帧幽1 3 运动估计从上述运动估计过程可知，运动估计和补偿算法复杂度包括：在给定搜索域内运动搜索的复杂度；每次块匹配运算的匹配汁算复杂度；每次块匹配运算需要从帧存读耿到运动估计处理器的数据量大小；实时硬件实现的适用性。其中，计算判决准则的次数通常作为衡量算法复杂性的尺度。不同的判决准则的计算量是不同的，最小均方误差( m s e l准则是理论分析时最常用的匹配准则，其表达式为m s e ( ) 。志弛( n l 川2 , k 。+ d ，, n 2 + d 2 , k + 1 ) 2( 1 1 )设块尺寸为n l n 2 ，则在每个搜索位嚣需要n 1 n 2 次减法和乘法，若搜索窗口s ，的尺寸为m 】m 2 ，则一共需要m ，x m 2 x n l n 2 次减法和乘法。增加分块尺寸和搜索窗f 的尺寸，需要的指令次数呈几何级数增长。可见，这样的运动估计算法的运算量很大，刈视频编解码器的实时性是个挑战。在h 2 6 4 标准中，增加了搜索帧的范围，最大范围是前后5 帧，增加了分块的种类，。运动估算精确到1 8 个象素点。这些特点在增加了运动估计精度的同时，极大地增加了计算复杂度，因此需要研究运动估计的快速算法。实际使用的视频编解码器的运动估计都应用了某些快速算法。1 1 5 运动估计快速算法的意义根据运动估计与补偿模块的执行时间在视频编码器运行时所占比例，可以知道高效的运动估计与补偿算法对提升视频编码器的性能所起的作用。表1 1 列出了h 2 6 3 基准测试模型中各模块执行时间的比例关系。6可以看到，总的运动估计与补偿功能模块的执行时间占整个视频编码器执行时问的比例很大，达到3 5 ，根据a m d a h l 定理。1 0 3 ，提升运动估计与补偿算法的性能，可有效地加快整个视频编码器的处理视频信，息的时间。表1 1h 2 6 3 基准测试模型中各模块执行时间的比例关系功能模块执行时间所占比例整数像素运动估训1 9 快速d c t1 2 快速i d c t9 半像素运动估计9 量化8 插值5 运动补偿2 在无线信道上传输视频是学术届和业界研究的热点问题，无线信道带宽低、差错率高，而视频本质上数据量大，如果利用冗余传输来进行纠错，数据量进步增大。斟此需要高精度的运动估计与补偿算法来降低视频流的比特率。在高精度的运动估计与补偿算法中，可以采用多帧运动估计，以及复杂的分块类型，这进一步增加了计算复杂性，只有在高端处理器上才能实现实时运动估计。在新一代的视频压缩标准中( 如h 2 6 4 ) ，已经采用了这种运动估计算法。因此，对无线视频服务的迫切需求，导致了运动估计快速算法研究的持续升温。因特网的迅速普及推动了网络服务的发展，“后p c ”时代即将来临。在“后p c ”时代，人们通过信息装置上网，从数据中心得到信息服务。这种信息装置的普及将使人们摆脱对p c 的依赖，p c 将不再是计算系统的中心。后p c 时代的重要标志是：移动便携式电子装置的大量使用，如个人数字助理( p d a ) 、移动电话、信息家加电成为同常的辅助工具；支持这些装置的基础设施的完善，如高速宽带网的建设、多功能服务器和数据库等“。在后p c 时代，便携设备将成为一种时尚，它将是后p c 时代的主流产品，成为计算机领域的主宰，其地位至少不会亚于台式机在当今的地位，在这一模式中，基本的个人电脑和通信设备将是便携的、以电池为能源的、支持语音识别和视频等多媒体功能。这样，体积小、能耗低，支持高端应用是个人移动电脑的基本特征。体积小、能耗低的芯片往往性能较低，因此，开发高性能的算法，提高软件的执行效率，才能满足高端应用的需求。以p a h n 公司研发的p d a 为例，其大部分型号采用的处理器都是摩托罗拉的6 8 k 系列的低端处理器“，来满足功耗低、体积小的要求，同时保证了价格优势。运动估计是视频应用中必不可少的组成部分，所以需要研究运动估计的快速算法。综上所述，运动估计算法复杂度高，是视频编解码器的重要组成部分，研究运动估计的快速算法，可有效地提升视频编解码器的性能。在手持设备上处理视频的迫切需求，使得近年米运动估计快速算法的研究成为热点。1 2 运动估计快速算法的相关研究综述运动估计算法研究的目标主要集中在两个方面，一个是降低运动估计中搜索算法的复杂度；另一个是提高运动估计的精度“。为了达