（计算机应用技术专业论文）降低快速搜索算法中局部最优误差的研究.pdf

摘要 运动估计是视频编码器的重要组成部分，占整个压缩编码5 0 以上的计算量。 而块匹配搜索又是运动估计的核心，全局搜索算法由于运算复杂度较大，没有实 用价值，为了降低搜索量，科研人员提出了各种快速搜索算法，如：，三步法、四 步法、钻石法等。 快速搜索算法虽然能够有效的降低搜索量，由于它是对搜索窗有选择的搜索， 容易陷入局部最优产生误差，称为局部最优误差，如何解决局部最优问题一直是 研究的热点。通过分析，降低局部最优误差的方法一般分为两类：一类是改进搜 索算法，另一类是改进搜索方案，本文就是基于这两类方法展开讨论。 在对经典快速搜索算法分析的基础上，本文提出了一种改进的快速搜索算法 两阶段搜索算法，主要通过提高第一步的搜索量来达到降低局部最优误差的 目的。 但如何评价一个快速搜索算法的好坏是提出新算法时要面临的问题。由于相 对快速搜索算法而言，全局搜索算法具有搜索量最大、搜索精度最高的特征，本 文提出把全局搜索算法作为一个参考点，所有待评价的快速搜索算法都与这个参 考点进行比较，得出一个量值，该量值就作为快速搜索算法质量值，通过比较质 量值来达到比较快速搜索算法的目的。 多分辨率运动估计是一种搜索方案的改进，它不再仅局限于对相邻帧原图进 行搜索，而是通过选择初始搜索点的方法来降低快速搜索算法的局部最优误差。 小波域多分辨率运动估计就是在这个基础上发展起来的，它利用小波变换良好的 多尺度特性，得到不同分辨率的子图，构造出多分辨率塔型结构。本文通过实验 分析得出：相对空间域搜索而言，基于小波域多分辨率运动估计的快速搜索算法 确实能够降低快速搜索算法局部最优误差，但增加了搜索层数，在一定程度上增 加了运动估计的复杂度。为解决这个问题本文提出了基于小波域的越级多分辨率 运动估计思想，并结合快速搜索算法，在降低局部最优误差的前提下，有效的降 低运算复杂度。 关键字：视频编码运动估计 快速搜索算法评价标准 两阶段搜索算法 小波域越级多分辨率运动估计 a b s t r a c t m o t i o ne s t i m a t i o np l a y sav e r yi m p o r t a n tp a r ti nv i d e oe n c o d e r , w h i c ha c c o u n t e d f o rm o r et h a n5 0 o ft h ea m o u n to fc o d i n g b e c a u s eo fc o m p u t a t i o n a lc o m p l e x i t yo f e x h a u s t i v e s e a r c h ，i th a sn op r a c t i c a l v a l u e i no r d e rt or e d u c et h ea m o u n to f c o m p u t a t i o n , t h er e s e a r c h e r sp u tf o r w a r dav a r i e t yo ff a s t s e a r c ha l g o r i t h m ss u c ha s t h r e es t e ps e a r c h , f o u rs t e ps e a r c h , d i a m o n ds e a r c h ，e t c a l t h o u g hf a s ts e a r c ha l g o r i t h m sc a l le f f e c t i v e l yr e d u c et h ea m o u n to fs e a r c h , b e c a u s eo ft h e i rc h o i c et os e a r c hi nt h es e a r c hw i n d o w , i tc a ne a s i l yf a l li n t ol o c a l o p t i m a la n dt h u sp r o d u c ee r r o r , w h i c hi sc a l l e da sl o c a lo p t i m a le r r o lh o w t os o l v e l o c a lo p t i m a lp r o b l e mh a sa l w a y sb e e nah o tt o p i c t h r o u g ha n a l y s i s ，t h ea p p r o a c ht o r e d u c et h el o c a lo p t i m a le r r o rc a ng e n e r a l l yb ed i v i d e di n t ot w ot y p e s ：o n ei st oi m p r o v e t h es e a r c ha l g o r i t h m ，t h eo t h e ri st oi m p r o v es e a r c hp l a n ，a n dt h i sp a p e ri st of u r t h e rt h e d i s e a s s i o no nt h eb a s eo f t h et w om e t h o d s o nt h eb a s i so ft h ea n a l y s i so ft h ec l a s s i c a lf a s ts e a r c ha l g o r i t h m s ，t h i sp a p e r p r o p o s e sam o d i f i e df a s ts e a r c ha l g o r i t h m t w o - p h a s es e a r c ha l g o r i t h m i tm a i n l ya d o p t s i m p r o v i n gt h ef i r s ts t e ps e a r c hv o l u m e t oa c h i e v et h ep u r p o s eo f r e d u c i n gl o c a lo p t i m a l e r r o r b u th o wt oa s s e s st h eq u a l i t yo faf a s ts e a r c ha l g o r i t h mi st h ep r o b l e mf a c e dw h e n p r o p o s e san e wa l g o r i t h m i nc o m p a r i s o nt o f a s ts e a r c ha l g o r i t h m s ，t h ee x h a u s t i v e s e a r c ha l g o r i t h mh a st h ef e a t u r e so ft h el a r g e s ta n dh i g h e s ta c c u r a c yo fs e a r c h , s ot h i s p a p e rp r o p o s e de x h a u s t i v e s e a r c ha l g o r i t h ma sar e f e r e n c ep o i n t a l lf a s ts e a r c h a l g o r i t h m sf o rt h ee v a l u a t i o nc o m p a r ew i t ht h er e f e r e n c ep o i n t ，a n dg e tav a l u e t h e v a l u ei sa st h eq u a l i t yv a l u eo f af a s ts e a r c ha l g o r i t h m m u l t i r e s o l u t i o nm o t i o ne s t i m a t i o ni sa l li m p r o v e m e n tt ot h es e a r c hp l a n ，a n di tn o l o n g e rl i m i t e dt ot h es e a r c ho ft w oa d j a c e n tf r a m e s ，b u tb yc h o o s i n gi n i t i a ls e a r c hp o i n t t or e d u c et h el o c a lo p t i m a le r r o ro ft h ef a s ts e a r c ha l g o r i t h m s t h ew a v e l e t b a s e d m u l t i r e s o l u t i o nm o t i o ne s t i m a t i o ni sd e v e l o p e do nt h i sb a s i s i tu s e sm u l t i s c a l ef e a t u r e o ft h ew a v e l e tt og e ts u b i m a g e sw h i c ho w nd i f f e r e n tr e s o l u t i o n ，a n dt h e nc o n s t r u c t st h e p y r a m i ds t r u c t u r eo fm u l t i r e s o l u t i o n i nc o m p a r i s o nt or e l a t i v ef a s ts e a r c ha l g o r i t h m s 2 b a s e do ns p a t i a ld o m a i n , f a s ts e a r c ha l g o r i t h m sb a s e do nw a v e l e t b a s e dm u l t i - r e s o l u t i o n c a ne f f e c t i v e l yr e d u c et h el o c a lo p t i m u me l t o r ，b u ti ta d d st h es e a r c hl a y e r s ，a n d i n c r e a s e st h ec o m p u t a t i o n a lc o m p l e x i t yi nac e r t a i ne x t e n t t os o l v et h i sp r o b l e m ，t h i s p a p e rp r o p o s e st h ew a v e l e t - b a s e dl e a p f r o g m u l t i - r e s o l u t i o nm o t i o ne s t i m a t i o na n d c o m b i n e sw i t l lt h ef a s ts e a r c ha l g o r i t h m s e f f e c t i v e l yr e d u c e st h ec o m p u t a t i o n a l c o m p l e x i t yu n d e r t h ea s s u r a n c eo f v i d e oq u a l i t y k e yw o r d s ：v i d e oc o d i n g m o t i o ne s t i m a t i o n e v a l u a t i o nc r i t e r i ao f f a s ts e a r c ha l g o r i t h m s t w o p h a s es e a r c ha l g o r i t h m w a v e l e t - b a s e dl e a p f r o gm u l t i - r e s o l u t i o nm o t i o ne s t i m a t i o n 独创性声明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含 为获得江西财经大学或其他教育机构的学位或证书所使用过的材料 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示了谢意 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后遵守此规定) 签名： 挞! 亟亟导师签名： 日期：1 柚 川 1 绪论 1 绪论 1 1视频压缩技术及其标准 视频图像能带来比文本数据更加丰富的信息，但是其传输和存储却是一项极 其耗时、困难的工程，这严重制约了视频图像的应用。比如一幅6 4 0 x 4 8 0 分辨率 的彩色图像( 2 4 比特，像素) ，其数据量约6 4 0 x 4 8 0 x 3 = 0 9 2 1 6 b ，如果以每秒3 0 帧的 速度播放，数据量将高达2 8 m b 。如果存放在4 7 g b 的光盘中，在不考虑音频信 号的情况下，每张光盘也只能播放1 7 0 秒的视频数据。因此对视频图像的庞大数 据量进行压缩是非常有必要的，视频压缩技术研究是解决数字化视频存储、传输 的关键。 多媒体技术的应用是越来越广，其压缩编码技术也越来越得到了学术界和工 业界的重视。制定视频编码标准的组织包括国际电信联盟( i t t 0 、美国a m s i 委员 会电信委员会、电信工业联合会( t i a ) 、欧洲电信标准机构( e t s i ) 、日本电信技术 委员会( n c ) 、美国电器电子工程师学会( i e e e ) 和国际标准化组织( i s o ) 等。 随着产业化活动的展开，国际标准化组织于1 9 9 8 年成立了运动图像压缩编 码组织m p e g 。m p e g 即活动图像专家组，它是隶属于国际标准化组织( i s o ) 和国 际电工委员会( i e c ) 的一个委员会。i e c 处理有关电学和电子学技术的国际标准， 除此之外的其它各种国际标准实际上均由i s o 处理。在信息技术的早期，i s o 和 i e c 建立了联合技术委员会( j t c l ) 从事于i t 方面的工作。j t c l 下面有一些工作组， 其中就包括联合图片专家组( j p e g ) 和w g l l ，而w g l l 就是m p e o 。 m p e g 专家组主要致力于运动图像压缩编码标准的制定。经过专家组不懈努 力，一系列主要针对视频数据的存储、广播电视和视频流的网络传输等应用场合 的视频压缩编码国际标准产生了，如：m p e g 1 、m p e g 2 、m p e g 4 、m p e g 7 。 而由另一个国际标准化组织i t u 制定的标准主要是针对实时视频通讯的应用，如 视频会议和可视电话等，它们以h 2 6 x 命名，主要有：h 2 6 1 、h 2 6 3 、h 2 6 4 1 - 5 】。 上述视频压缩标准的推出，不仅极大地推动了视频压缩技术的研究，而且已 经对多媒体相关产业产生深远的影响。 1 2 运动估计在视频编码中的作用 对于图像来说，像素之间存在很强的相关性，可以由预测编码或者变换编码 降低其空间冗余。 而视频图像，不仅每帧图像内像素之间存在很强的相关性，相邻帧之间也存 在很大的时间相关性，即时间冗余，也称帧间冗余。所以不仅要降低帧内的空间 降低快速搜索算法中局部最优误差的研究 冗余，还要通过减少时间冗余，来大幅度提高视频压缩编码的效率。一般用运动 估计( m o t i o ne s t i m a t i o n ，m e ) 与运动补偿预测( m o t i o nc o m p e n s a t e dp r e d i c t i o n m c p ) 嗍，或简称运动补偿( m c ) 来实现降低时间冗余，也称为帧间运动估计、运动 补偿。由于m e 、m c 算法简单、易于实现而得到广泛的应用。它几乎被所有的视 频编码标准所采纳，如：m p e g 1 、m p e g 2 、m p e g - 4 、h 2 6 1 、h 2 6 3 、h 2 6 4 等。 其基本思想是将视频图像的每一帧分成n x m 大小的宏块，然后对当前帧中的每一 宏块根据一定的匹配准则在前一帧或后一帧某一给定搜索范围内找出与当前块最 相似的块，即匹配块。由匹配块与当前块的相对位置计算出运动位移，所得运动 位移即为当前块的运动矢量( m o t i o n v e c t o r , m y ) 。然后利用搜索到的运动矢量在参 考帧上进行运动补偿，得到帧间位移误差( d i s p l a c e m e n tf r a m ed i f f e r e n c e d f d ) 【4 】 如图1 1 。这样，对视频图像的编码就可以变为仅对m v 和d f d 的编码。 从图1 1 可以看出，在基于m e 和m c 的帧间压缩编码方案中，整个过程得到 两个结果：m v 和d f d 。显然，m e 、m c 的结果m v 和d f d 不仅影响视频图像 压缩编码的质量，还影响编码压缩的效率。由于d f d 根据m v 得到，m v 又是由 m e 得到，因此，在整个运动估计过程中m e 才是视频压缩的关键环节。 图1 1 运动补偿预测+ d c t 变换视频编码器 另一方面，由于实际应用中m e 占整个系统的计算量最大，达到5 0 以上， 如何提高m e 的效率，使m e 算法搜索过程更健壮、更快捷、更有效仍是目前研 究的热点。 由于m e 需要在前后帧间逐像素比较，如果采用全局搜索算法，计算量非常 巨大。因此通常编码器都采用了快速算法，己提出的经典快速算法有：二维对数 搜索法嘲、三步搜索法【7 1 、新三步搜索法i s 、交叉搜索法【9 】、四步搜索法1 1 0 1 、钻石 搜索法d 1 , 1 2 等，这些快速搜索算法能很好的降低运算量，但是由于这些搜索算法是 对搜索窗有选择的进行搜索，很容易陷入局部最优而产生误差，称为局部误差。 1 绪论 在一定程度上影响m e 后得图像质量。然而即便采用快速算法，m e 仍是最费时的 环节。如在h 2 6 1 的编码过程中，在采用著名的三步搜索法的情况下，m e 仍要占 用整个编码过程6 3 的计算量；而在h 2 6 3 编码器中，m e 占了4 2 的计算量。 因此，m e 是视频压缩的瓶颈【4 】。 1 3多分辨率运动估计及基于小波变换的视频编码 上面所谈到的搜索算法都是相邻帧原始图像之间的搜索，称为空间域搜索算 法。由于空间域的快速搜索算法都容易出现局部最优问题，科研人员提出了各种 改进方案，一般分为两类：一类是基于空间域搜索，改进搜索算法。另一类是改 进搜索方案，它将不再局限于仅对空间域搜索，多分辨率运动估计就是作为一种 搜索方案的改进而被提出。 多分辨率运动估计( m u l t i - r e s o l u t i o nm o t i o ne s t i m a t i o n ，m r m e ) 又可以称为多 分层塔结构运动估计，其通过先粗搜索后细搜索求得m v ，可以比较好的解决快速 搜索算法的局部最优问题，达到提高编码后视频效果的目的。 小波变换是近十年发展起来的一种信号分析方法。随着小波图像编码技术研 究的不断深入，人们发现小波具有良好的时一频局部化分析特性和天然的多分辨 率结构，并能与人眼视觉特性相吻合。这使得基于小波的静态图像编码技术具有 良好的压缩性能和高度的可扩展能力，不仅能够避免传统视频编码算法中分块 d c t 变换带来的固有的“方块效应”，容错性能也尤为出色 5 , 1 3 - 1 7 1 。j p e g 2 0 0 0 图像 编码系统就采用了小波变换技术。 在视频编码方面，小波的应用虽然远没有静态图像编码那样普及，但也一直 是国内外研究热点 1 7 - 2 6 】。目前，基于小波变换的视频编码算法可分为两类：二维 小波视频编码和三维小波视频编码。其中二维小波视频编码包含2 种方法：基于 空域m e 的小波视频编码和基于变换域m e 的小波视频编码。三维小波视频编码 也可分为：含m e 和不含m e l ”j 。 基于空域m e 的小波视频编码算法在空间域进行m e 和m c ，对残差图像采用 小波变换进行编码，相当于把图1 1 中的d c t 换成d w t 。但由于运动补偿后的残 差图像不同于传统自然图像，若采用一般的小波变换并不能显著地提高压缩效率。 基于变换域m e 的小波视频编码算法就是一种基于多分辨率运动估计的思想。 首先对图像进行小波变换，在变换域中进行帧间m e 和m c ，再进行编码。由于小 波具有多分辨率的特性，结合m r m e 理论，能够很好的降低空间域搜索算法带来 的局部最优问题，对编码后视频图像的效果有一定的提高【2 7 1 。 三维小波视频编码可以看作是二维小波编码在三维空间的一种推广。 降低快速搜索算法中局部最优误差的研究 不含m e 三维小波视频编码过程：把连续1 6 帧视频图像作为一个图像组。一 个图像组中的各帧处于同一空间位置处的各个像素点构成了一个一位序列，然后 进行一维小波变换。再对分解后得到的高频子帧和低频子帧进行空域的二维小波 分解，这种帧间一维变换和帧内二维变换构成了三维小波变换。 含m e 三维小波视频编码方法将m e 技术和时间轴一维小波变换结合起来， 同时采用m e 和时域一维小波分解两种技术去除时间冗余信息。 三维小波变换具有无块效应，并且视频编码器在支持容错和可伸缩性码流输 出方面具有显著特性。然而它也明显存在着一些不足，由于在整个编码过程中需 要多帧的信息，就需要较多的帧存储器，并且由于以图像组为单位进行编码会带 来较大的延迟，一般人们采用较多的还是二维小波视频编码。 1 4 主要工作与论文安排 1 4 1 主要工作 由于空间域快速搜索算法经常受局部最优问题的困扰，如何降低快速搜索算 法的局部最优误差是本文主要讨论内容，一般改进方法有两类：类是基于搜索 算法的改进，另一类是基于搜索方案的改进。本文第一部分在经典搜索算法的基 础上，提出种改进的快速搜索算法两阶段搜索算法，并通过本文提出的快 速搜索算法评价标准，把该算法与经典快速搜索算法进行比较。第二部分是在小 波域多分辨率运动估计的基础上，提出一种能降低局部最优误差的改进搜索方案 基于小波域的越级多分辨率运动估计，并通过实验数据进行分析论证。 1 4 2 论文内容安排 本论文主要分以下章节： 第一章绪论。简单介绍了块匹配运动估计的概念、重要性及小波视频编码 的现状。 第二章详细介绍运动估计基本原理，对空间域e s 、t s s 、f s s 、d s 等经典 搜索算法进行理论分析，然后实验仿真、数据比较。在进行算法比较的过程中， 本文提出了种能同时考虑运动估计后视频效果和搜索量两个因素的空间域快速 搜索算法评价标准，该标准在比较快速搜索算法t s s ，f s s 、d s 优劣时起到重要 作用。 第三章在经典快速搜索算法分析基础上，提出一种改进快速搜索算法 两阶段搜索算法( t p s ) ，该算法的特点是通过提高第一步的搜索量来降低经典快速 搜索算法中容易出现的局部最优问题。然后提出基于该算法的第一阶段搜索模板， 1 ，绪论 并由此派生出四种搜索算法，最后通过实验数据来证明该算法的有效性。 第四章多分辨率运动估计作为一种改进型搜索方案而被提出，本章详细介 绍多分辨率运动估计原理、小波理论，并对现有的小波视频编码进行简单介绍。 第五章详细介绍小波域多分辨率运动估计过程，并进行实验仿真，分析结 果发现基于小波域多分辨率运动估计确实是一种降低快速搜索算法局部最优误差 的好方法，但相对空间域快速搜索算法而言，算法复杂度较高。所以本章提出了 一种能够降低搜索量的小波域多分辨率运动估计改进方法小波域越级多分辨 率运动估。 第六章总结与展望 1 4 3 创新点 ( 1 ) 提出基于空间域的快速搜索算法评价标准。 ( 2 ) 提出两阶段快速搜索算法，并提出第一阶段搜索模板，且相应派生出四 个算法。 ( 3 ) 提出基于小波域的越级多分辨率运动估计思想。 1 5实验条件 因为本文研究的主要目的是如何降低快速搜索算法中的局部最优误差，对于 快速搜索算法而言，局部最优误差一般容易出现在场景变换、场景复杂的、有一 定运动量的视频中，所以本论文采用的三个实验视频都是有一定运动量、场景变 换的视频。 “v e e t r a 视频片断，分辨率为3 5 2 x 2 8 8 ：是截取 v e e t r a 视频中连续6 0 帧作为 片断；场景内有一汽车从左向右运动。图1 2 为视频片断中第1 帧的图像。 图1 2 v e e t r a 视频片断第1 帧 “f o o t b a l l ”视频片断，分辨率为3 5 2 x 2 8 8 ；是截取“f o o t b a l l ”视频中连续6 0 帧作 5 降低快速搜索算法中局部最优误差的研究 为片断；场景内有多名运动员正在抢球。图1 3 为视频片断中第1 帧的图像。 图1 3 “f o o t b a l l ”视频片断第1 帧 w a l k 视频片断，分辨率为3 5 2 x 2 8 8 ；是截取 w a l k 视频中连续6 0 帧作为片 断；场景为一行人在前面走路，另行人手持摄像机在后面对其进行拍摄。图1 4 为视频片断中第l 帧的图像。 图1 4 w a l k 视频片断第1 帧 所有视频都是y u v 格式的视频文件。 下面简单贪绍y u v 格式的基本概念： y u v 是常用于多媒体技术中的一种格式，该文件适用于彩色电视的颜色表示。 其基本特征是：将亮度信号和色度信号分离表示，用y 代表亮度，而u 、v 表示 两个彩色分量，称为色度，一般是蓝、红色的相对值，用来表示色差。 y u v 的特点是：亮度信号y 和色度信号u 、v 相互独立，因此可以分别对y 、 u 、v 这三种信号分别进行编码。又由于人眼对亮度细节的分辨能力远比彩色细节 的分辨能力高，所以一般可以把色度信号的分辨率降低，由此来达到压缩彩色图 像存储量的目的1 3 j 。 本文为了降低实验的复杂性，实验中仅对视频的亮度信号y 进行运动估计。 6 2 运动估计 2 运动估计 如上章所述，视频图像在时间上具有很强的相关性，利用运动估计和运动补 偿技术可以有效地降低时间冗余，实现高码率压缩。对于现在广泛使用的视频压 缩国际标准如h 2 6 1 ，h 2 6 3 ，m p e g - l ，m p e g - 2 ，m p e g - 4 等，其编码系统的复 杂性一定程度上取决于运动估计技术。由此可见，运动估计技术是数字视频编码 的关键问题之一。 2 1基本原理 在第一章本文简单介绍了视频编码中运动估计理论，下面本节将对其进行详 细分析。 在视频中，相邻帧间主要的一些变化是由场景内各物体的运动引起的，检测 物体的运动参数，并通过这些运动参数由前一帧预测当前帧，这就是运动补偿预 测( m o t i o nc o m p e n s a t e dp r e d i c t i o n , m c p ) ，或简称运动补偿( m c ) 。其中最主要的是 检测物体的运动参数，称为运动估计( m o t i o ne s t i m a t i o n ，m e ) 1 5 。 物体的运动可能有多种情况，包括平移、旋转及扭曲等，完整地描述物体运 动模型是复杂的。但目前通用的图像压缩标准及大多数实用视频压缩算法中，均 使用了简化运动模型，即假设场景内物体的运动只由x 和y 方向的平移构成，这 样只用x 和y 方向( 水平与垂直方向) 的两个平移参数f ，_ ，构成一个运动矢量d 来表 征运动参数。 d = g 力 ( 2 1 ) 当前帧( ，) 坐标点的像素值由前一帧预测为 s ( 1 ，j r , | ) 一s ( 1 ，j ，忌) = s ( ，+ i , j + j ，k - 1 ) ( 2 2 ) 这里| j 表示当前帧，k - 1 表示前一帧，s ( 1 ，j ，| j ) 表示原始像素值，童( ，j ，后) 表 示预测到的像素值。 当前帧原始图像与预测图像之间可能会有误差，由于这个误差是由运动补偿 预测引起的，故称为帧间位移误差( d i s p l a c e m e n tf r a m ed i f f e r e n c e ，d f d ) ，表示如 下： d f d ( i ，j ，| | ) = s ( x ，j ，| ) 一s ( i ，j ，t ) = 3 ( i ，j ，d - s u + i ，j + _ ，k 一1 ) ( 2 3 ) 这样，对视频图像的编码就可以变为仅对d f d 场和d 场的编码。由于相邻帧 的相关性较高，运动补偿是有效的，d f d 场能量非常低，可以用很少的码字表示， d 场是稀疏的，同样用较少码字表示，这样就可以获得有效的码率压缩5 1 。图2 1 降低快速搜索算法中局部最优误差的研究 为编码矢量图例，图2 1 a 和图2 i b 分别为“v e c t r a 视频片断的第l 、2 帧亮度分量 原图，图2 1 c 和图2 1 e 分别为经过块匹配运动估计得到的d 场和d f d 场图，图 2 1 d 是仅由运动矢量d 场和第l 帧图像重建的第2 帧图像亮度分量图。 图2 1编码矢量图实例 在这里，平移运动假设有效性是有条件的：将每一帧分成等大的块，对于每 个块的平移与旋转可以用一个平移运动矢量来逼近，如果块分得足够小，对这些 块进行运动估计得到的d 场，就可以认为其逼近平移和旋转运动1 5 】。所以基于这 种块匹配运动估计是目前应用最广泛的，下面为其详细的过程。 假设对于当前第k 帧图像，将它平均地划分成大小相等的块，称为宏块，有时 简称为块。每个宏块的尺寸为n m ，即每个块包含行，每行m 个像素。每个 8 2 运动估计 块起始点在整帧图像中的列、行标号为( ，刀，整个块用b ( i ，j ，k ) 表示。假设相邻 帧间的x 和y 最大搜索长度为出一和方一。这样在第k 一1 帧上构成了一个搜索 窗口，这个窗的中心点坐标为( ，d ，窗大小为2 方一2 d x m ，在搜索窗中所有 要被搜索的块集合为 b ( i + f ，j + j , k 一1 ) ，一斑一f 出一，一c o , 一，砂一) 图2 2 为块匹配运动估计的搜索窗口图。 在所有这些搜索块中，与b ( i ，k ) 按某一匹配准则最接近的块，假设为 s ( i + i o , j + 矗，k - 1 ) ，那么它就称为b ( i ，j ，后) 的匹配块，则( 乇， ) 就是b ( z ，j ，j ) 的 运动矢量d 。在这个匹配过程中就必须要定义一个匹配准则，用于描述这两个块 的近似度，常用的匹配准则有最小均方差( m s e ) 、最小绝对差( m a d ) 、归一化相 关函数( n c c f ) n 最d , 求和绝对误差( 跚d ) f 4 ，5 1 3 1 。具体细节将在下一节进行详细讨 论。 参考i 啸( 七一1 和幻中n x m 搜需央 、 卜i 缸 逍一出。牟 _ f _ 吣廿 出- i 咖。 l i j j - 图2 2 块匹配运动估计搜索窗口图 参考帧 僻1 帧) 中的搜雷 亩 当前帻仕t d 中n x m 块 2 2运动估计的关键环节 视频编码算法的好坏主要体现在图像质量、压缩编码和运动估计三个方面。 运动估计越准确，d 场越有效，预测补偿的图像质量越高，d f d 场能量越小，所 需要的补偿编码越少，比特率越小，运动估计速度越快，越有利于实时应用。提 高图像质量、加快估计速度是运动估计算法主要的研究目标。 2 2 1 宏块的大小和形状 为了满足块匹配法，必须合理选择宏块的大小，以保证运动补偿预测的图像 更加逼近真实的图像，这在上一节已经提到。为此，块应取尽量小一些。但宏块 取得太小，搜索量将大大增加，比如在出一和砂。大小不变的情况下，若原来一 9 降低快速搜索算法中局部最优误差的研究 幅图分成l l x 9 个宏块，如果宏块长宽各减半，那么该图将要有2 2 x 1 8 个宏块要进 行匹配。宏块太小的话也很容易受噪声干扰，并且所需传输的附加信息也大大增 加，不利于高压缩。 因此，必须恰到好处地选择宏块大小，做到压缩率、运算速度、精确度兼顾。 目前视频压缩编码标准，如h 2 6 1 、m p e g - l 、m p e g 2 等，一般均以1 6 x 1 6 大小 像素块作为宏块，这是一个已被实践证明的较好折衷结果。虽然在h 2 6 3 的先进 预测模式中，每个8 x 8 的宏块都有一个运动矢量，但是它也是先进行1 6 x 1 6 的块 运动估计，然后在这个基础上再对每一个8 x 8 块进行小范围运动估计。而h 2 6 4 基于4 x 4 的宏块，并且使用了可交宏块大小的运动估计，提高了压缩后视频图像 的质量，但同时也带来了较大的运算量。 除了宏块的大小，块形状的选取也是视频压缩编码标准的一个考虑范围。比 如在以上的标准中就用到了1 6 x 1 6 、8 x 8 、4 x 4 的正方形宏块，还有1 6 x 8 、8 1 6 、 8 x 4 、4 8 等非正方形宏块。由于标准中用到的都是矩形块，使得最后的压缩视频 图像有一定的块效应，特别是在宏块比较大的时候。而矩形块也并不能真正反映 图像真实运动情况，所以在m p e g - 4 标准中提出了基于v o ( v i d e o o b j e c t ) 编码的思 想，宏块已经不再是简单的矩形块了，而是一个个对象，这十分符合人的视觉及 心理特性。 2 2 2 初始搜索点的选择 对于第k 帧图像，块b ( i ，d ，七) 在k 帧的起点位置为( ，) 。做运动估计时必须 找到该块起始点在k 一1 帧中所应该对应的点，即称为b ( i ，d ，的初始搜索点，并 以该点位置为中心建立2 d y 。2 d x 。, 大小的搜索窗。在一般情况下，在第k 一1 帧 上构成搜索窗1 ：3 的中心点坐标为( ，j ) ，即把k l 帧的( ，j ) 作为k 帧中b ( ，d ，k ) 的 初始搜索点。这种方法简单，但易陷入局部最优点。并且如果采用的算法初始步 长太大，而k 一1 帧的( ，) 又不是最优点时，有可能使快速搜索跳出可能性比较大 的区域而去搜索远距离的点，导致搜索方向的不确定性，陷入局部最优。正是由 于这些问题，提出了选择性的初始搜索点。根据一定的方法得到b ( i ，k ) 初始搜 索点，而不是直接把( ，) 作为其初始搜索点。 由于相邻块之间、同一图像的不同分辨率图像和相邻帧之间具有很强的相关 性，许多算法都利用这种相关性先对初始搜索点进行预测，以预测点作为初始搜 索点【4 】。多分辨率运动估计的思想就是一种选择性的初始搜索点方法，其通过把低 分辨率运动估计矢量作为高分辨率运动估计的初始搜索点，来提高视频编码后的 效果。 1 0 2 运动估计 2 2 3 匹配准则 如何找到与b ( i ，以j i ) 最接近的块，这就需要有个匹配准则，该准则能反映在 b ( x + f ，+ j ，| i 一1 ) ，一威一i 出一，一方一s j s d y 一) 中哪个块更加接近 b ( ，以k ) 。常用的准则有：最小均方差( 肋陋) 、最小绝对差( 心d ) 、归一化相关 函数( n c c f ) 和最小求和绝对误差( s a d ) 等。 ( 1 ) 最小均方差 m s e q , 护赤萎孕跗帆，帆炉跗+ f + n , j 坍础- l 】2 式中，( f ，力为位移矢量，s ( i + n , j + m ，k ) 和s ( 1 + i + n ，j + j + m ，k 一1 ) 分别为 当前帧和上一帧的灰度值，n x m 为宏块的大小，若在某一点( f o ， ) j f f m s e ( i o ， ) 达到最小，则b ( i + i o ，j + j o ，k - 1 ) 为b ( 1 ，k ) 的匹配块，对应点( f o ，矗) 为要找的最 优匹配点，即运动矢量。 ( 2 ) 最小绝对差 m a d ( i , j ) 3 志丢p ( ，帆，协七) 一s ( 帆j + j 慨k 1 ) i m a d 值最小点为最优匹配点。 ( 3 ) 归一化互相函数 s ( 1 + n ，j + m ，k ) s ( 1 + i + n ，j + j + m ，k 一1 ) n c c f ( i ，力2 证丽_ 止幽l 可正i _ _ 矿 l s 2 ( ，+ 疗，j + m ，i ) fj s 2 ( ，+ f + 聍，j + j + m ，k 1 ) i l n = om - o jl m = o j n c c f 的最大点为最优匹配点。 ( 4 ) 最小求和绝对误差 s a d ( i , j ) = i s ( 1 + n ，j + m ，_ i ) 一s ( 1 + i + n ，d + j + m ，k 一1 ) i s a d 值最小点为最优匹配点。 事实上，具体选择哪种准则对匹配结果影响不大，但是由于s a d 准则不需做 除法和平方，实现起来简单、方便，所以被广泛使用。本文所有搜索算法都是把s a d 作为搜索匹配准则。 2 2 4 搜索方法 搜索方法的好坏将极大地影响运动估计的可靠性与计算的复杂度。在块匹配 运动估计算法中，全搜索算法精度最高，但由于它要对搜索区内的每个搜索点进行 检测，因此计算复杂度高，比如若宏块大小为1 6 1 6 ，搜索窗半径 砂。= 出一= d 。= 1 6 ，要搜索的宏块数就有( 2 d 一+ 1 ) 2 = 1 0 8 9 ，对1 0 8 9 个宏 降低快速搜索算法中局部最优误差的研究 块进行s a d 运算，对非专用芯片实现实时编码系统来说计算量是庞大的。 所以研究人员提出了各种快速搜索算法，较经典的有：二维对数搜索法旧、三 步搜索法【7 1 、新三步搜索法嘲、交叉搜索 9 1 、四步搜索法【1 0 1 、钻石搜索法1 1 11 2 1 。还 有其他的一些改进算法，如：小菱形分层搜索法【2 踟、多模板搜索法1 2 9 、十字形搜 索法f 3 0 j 、双十字形搜索法【3 l 】、六边形搜索法【3 2 ，3 3 1 、双起点六变形与小菱形结合搜 索法【3 4 1 、十字、钻石、六边形搜索法【3 5 】、快速线性搜索法【3 6 1 、基于运动矢量分布 的搜索法 3 7 1 、基于运动相关特性和中心偏向特性的快速搜索法 3 8 1 、基于内容的强 意识搜索法嗍、改进全局搜索算法 4 0 , 4 ”、基于局部变量模型规则约束的密集搜索 法 4 2 1 ，基于匹配预测的不规则模板搜索法【4 3 1 、自适应双十字搜索法m 、矢量叠加 和自适应中止法1 4 5 1 、自适应预n , 法t 4 6 j 等，但在生活中使用最频繁的还是几种较经 典的快速搜索算法。下面就详细介绍几个常见的经典搜索算法并对它们进行理论 分析。 ( 1 ) 全局搜索法 算法思想 全局搜索法( e x h a u s t i v es e a r c h ，e s ) 也称为穷尽搜索法，是对搜索窗口内所有的 点计算s a d 值，从中找出最小s a d 点，则该点的位置即为最优运动矢量。此算法 虽计算量大，但最简单、可靠，找到的必为搜索窗的全局最优点。 算法描述 r 1 r 1 r 卜攫景路径 图2 3e s 搜索模板 1 2 2 运动估计 s t e p l ：从协。，一出一) 点出发，从上到下，从左到右搜索整个搜索窗口，在 逐个像素处计算s a d 值。 s t e p 2 ：在所有的s a d 中找到s a d 值最小的点，该点所在位置坐标即对应最优 运动矢量。 搜索模板及搜索过程图2 3 ( 2 ) 三步搜索法 三步搜索法【刀( n es t e ps e a r c h , t s s ) 法是t k o g a , k l i n u m a 等人提出的，由 于简单、健壮、性能良好的特点，为人们所重视。设出。= d y 一= k ，为 最大搜索长度。如果最大搜索长度为8 ，搜索精度取1 个像素，则步长为4 ，2 ，l ， 共需三步即可满足要求，因此而得名三步法。但是如果d 。为1 6 ，搜索精度为1 个像素，则搜索步长为8 ，4 ，2 ，l ，需要四步。 基本思想 t s s 算法是一种由粗到细的搜索模式，从原点开始，按一定步长取周围8 个 点构成每次搜索的点，然后进行匹配计算，找出黝d 最小的点。 人疋人 x y 一 。x 斛 y 八八厂 i ? 一努咕棚瞧第l 懒点。第三步搜囊点 搜棠路径 图2 4t s s 实例 算法描述 s t 印1 ：从原点开始，选取最大搜索长度的一半为步长即s f 印_ s i z e = 等，搜 索与原点距离为步长的8 个点，并进行匹配计算求出各点的s a d 值。 s t e p 2 ：中心点移到上一步的s a d 最小点，并将步长减半即 7 5 4 ，l 4 4 4 一 4 4 降低快速搜索算法中局部最优误差的研究 s t e p s i z e = s t e p _ s i z e ，搜索与该点距离为步长的8 个点，并进行匹配计算求