（电子科学与技术专业论文）一种h264运动估计器的系统级设计.pdf

声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取 得的成果，撰写成博士硕士学位论文= ! = 旌b ：丛连逊竖丝! ! ! 些、干 除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。本论文中不包含任何未加明确 注明的其他个人或集体已经公开发表或未公开发表的成果。 本声明的法律责任由本人承担。 学位论文作者签名： 绪 ，鲫歹年弓月f d 日 摘要 摘要 h 2 6 4 a v c 是由i t u - t 和m p e g 共同制定的晟新的视频编码标准。与现有标 准相比，h 2 6 4 获得了更高的编码效率、更好的图像质量和更强的网络适应性。 运动估计技术是包括h 2 6 4 在内的视频编码的一项关键性技术，它可以有效地 消除视频序列在时间上的相关性。运动估计v l s i 系统结构的设计已成为当前研 究的重点，其性能的好坏直接决定了h 2 6 4 视频压缩编码芯片的处理速度，功 耗及成本。 本文深入研究了运动估计技术的基本原理，提出了适用于h 2 6 4 视频编码 标准的模式决策算法和快速运动估计算法。并在此基础上，提出了经过软硬件 功能划分的最终可实现的系统结构框图。为了进一步实现的需要，本文还对系 统结构框图中的r i s c 运动估计协处理器和脉动阵列结构作了详尽深入的研究 和设计，并给出了它们的基本结构框图。 本文分别对算法和系统结构作了仿真。仿真结果表明，本文所提出的算法 不但能使运动估计器降低其硬件实现成本，而且能减少模式决策和运动估计的 时间。本文所提出的系统结构能够正确实现符合h 2 6 4 视频编码标准的实时运 动估计。 关键词：h 2 6 4 ；视频编码器；运动估计；软硬件协同设计；脉动阵列； 第4 页共8 2 页 a b s t r a c t a b s t r a c t h 2 6 4 ，a v ci st h el a t e s tv i d e oc o d i n gs t a n d a r do fn u 珂a n dm p e g ，w h i c h a c h i e v e se n c h a n c e dc o m p r e s s i o np e r f o r m a n c e ，b e t t e rv i d e oq n a l i t ya n dp r o v i d e sa ”n e t w o r k sf r i e n d l y ”v i d e or e p r e s e n t a t i o n m o t i o ne s t i m a t i o ni sak e yc o m p o n e n t o ft h e v i d e oc o d i n gs t a n d a r ds u c ha sh 2 6 4a n di tc a ne f e c t i v e l yr e m o v et h er e d u n d a n c eo f s u c c e s s i v ev i d e os i g n a l v l s ia r c h i t e c t u r eo fm o t i o ne s t i m a t o ri sv e r yi m p o r t a n tt o v i d e oc o d e cb e c a u s ei t sp e r f o r m a n c ed e t e r m i n e st h ee f f i c i e n c y ，p o w e ra n dc o s to f h 2 6 4v i d e o c o d i n gc h i p i nt h i s t h e s i s ，t h ep r i n c i p l e o fm o t i o ne s t i m a t i o ni ss t u d i e d d e e p l y a n dn e w a l g o r i t h m so fm o d e d e c i s i o na n dm o t i o ne s t i m a t i o nf o rh 2 6 4a r ep r o p o s e d 0 nt h e b a s i so ft h a t ，ak i n do fr e a l i z a b l es y s t e r ns t r u c t u r eo fh ，2 6 4m o t i o ne s t i m a t o ri s i n t r o d u c e d a f t e rt h eh a r d w a r e s o f t w a r e c o d e s i g n f o r t h e p u r p o s e o ff u r t h e r r e a l i z a t i o n ，t h er i s cm o t i o ne s t i m a t i o np r o c e s s o ra n ds y s t o l i ca r r a yi n t h es y s t e m s t r u c t u r ea r ea l s or e s e a r c h e da n dd e s i g n e d ，a n dt h e i rs t r u c t u r a ld i a g r a m sa r ep r o v i d e d s i m u l a t i o nr e s u l t ss h o wt h a tt h e s en e wa l g o r i t h m sc a nn o to n l yf e d u s et h e h a r d w a r ec o s to fm o t i o ne s t i m a t o r , b u ta l s oa c c e l e r a t em o d ed e c i s i o na n dm o t i o n e s t i m a t i o n t h es y s t e ms t r u c t u r e p r o p o s e di n t h i st h e s i sc a nr e a l i z et h er e a l t i m e m o t i o ne s t i m a t i o no fh 2 6 4s t a n d a r dc o r r e c t l y k e yw o r d s ：h 2 6 4 ，v i d e oe n c o d e r , m o t i o ne s t i m a t i o n ，h a r d w a r e s o f t w a r ec o + d e s i g n ， v l s ia r c h i t e c t u r e ， 第5 负共8 2 页 第一章概述 第一章概述 1 1 研究课题的背景与意义 数字视频技术的研究和应用是目前信息技术领域最热门的话题，其应用十分 广泛。数字视频通信有很多优点，如它可以中继传输和多次复制，不会造成噪 声和非线性失真的积累；便于加密；便于用v l s i 芯片实现等。数字视频压缩技 术在通信、媒体数据存储、数据分布等领域一直发挥着重要的作用，是信息处 理领域中最活跃的技术。 本课题研究的是数字视频编码器中的核，0 部件：运动估计器。运动估计器是 视频压缩编码芯片的重要组成部分，也是其中最消耗计算资源的模块，其性能 的好坏直接决定了视频图像的压缩质量，同时也决定了整个系统芯片的处理速 度，功耗以及成本。如何有效设计运动估计器的v l s i 并行实现算法与结构已成 为当前研究的重点。这对促进视频技术的发展具有重要的现实意义。 1 2 数字视频压缩标准的发展与现状 数字视频压缩编码技术成熟的标志就是一系列相应国际标准的制定，即国际 电信联盟i t u t 关于电视电话会议电视的视频编码标准h 2 6 1 、h 2 6 3 和国际 标准化组织i s o 国际电工委员会i e c 关于运动图像的编码标准m p e g 一1 、m p e g 一2 和m p e g 一4 等，以及i t u t 和i s o i e c 共同成立的联合视频小组( j v t ) 所制定的 新的视频编码标准h 2 6 4 ( m p e g 一4p a r t1 0a v c ) 。 这些国际标准融合了各种性能优良的视频压缩编码算法，代表了当前视频压 缩编码技术的发展水平。下面将对以上视频压缩编码标准作以简单介绍“3 ： h 2 6 1 是i t u t 针对可视电话和会议电视、窄带i s d n 等要求实时编解码和低 延时应用提出的一个编码标准。该标准包含的比特率为px6 4 k b s ，其中p 的 取值范围是1 到3 0 ，对应比特率为6 4 k b s 到1 9 2 m b s ，输入图像应满足c i f 或 q c i f 格式。采用的主要编码技术有d c t 。自适应量化，z i g z a g 扫描，运动补偿 预测，运动估计，h u f f m a n 编码以及容错编码等。 第6 负共8 2 负 第一章概述 h 2 6 3 是i t u t 于1 9 9 5 年针对低比特率视频应用制定的，被公认为以像素为 基础采用第一代编码技术的混合编码方案所能达到的最佳结果。特别适合p s t n 网络，无线网络与i n t e r n e t 等环境下的视频传输。目标比特率为8 k b s 到 1 5 m b s 。工作图像格式为q c i f ，s u b q c i f ，c i f ，4 c i f ，1 6 c i f 等。采用的编 码技术除了包含h 2 6 1 所有技术以外，还吸收了m p e g 等其它标准中合理有效的 部分，如双向运动补偿、半象素运动估计、高级运动估计、重叠运动补偿和算 术编码等。为进一步提高编码效率，提供了四种可选的编码模式。 m p e g 一1 是i s o i e c 的运动图像专家组m p e g ( m o v i n gp i c t u r ee x p e r t g r o u p ) 于1 9 9 3 年制定的针对1 5 m b s 速率的数字存储媒体运动图像及其伴音编码的国 际标准。这使得基于c d r o m 的数字视频和m p 3 的数字音频产品成为可能。在规 定带宽中1 i m b s 用于视频，1 2 8 k b s 用于音频，其余用于m p e g 系统本身。将 图像序列分为i 帧、p 帧、b 帧和d 帧，对应不同的编码模式。采用的编码技术 肖j p e g 所有技术，自适应量化，运动补偿预测，双向运动补偿以及半象素运动 估计等，其中核心技术为分块d c t 和帧问运动补偿预测编码。 m p e g 一2 于1 9 9 5 年推出，是在m p e g l 基础上的进一步扩展和改进，是主要针 对数字视频广播、高清晰度电视和数字视盘等制定的4 - 2 0 m b s 运动图像及其伴 膏的编码标准。m p e g - g 是数字电视机顶盒和d v d 等产品的基础。为了提高通用 姚，m p e g 一2 增大了重要的参数值，允许更大的画面格式、比特率和运动矢量长 菠并规定了分辨率从低到高的4 级5 类共1 1 种单独的技术规范。与m p e g i 比较，m p e g 2 加入了基于帧场的运动补偿、空间时间质量可扩展编码以及容 错编码等技术。 m p e g 一4 已不再是单纯的视音频编解码标准，以内容与交互性为核心，为多 媒体数据压缩提供了一个更为广阔的平台。m p e g 一4 第一次提出了基于对象的视 频编码概念和方法，从而获得比现有以像素为基础的标准更为优越的压缩性能， 同时也为应用提供了各种新的功能。m p e g 一4 在移动通信、专业视频、消费视频、 交互式视频等领域已显露出广阔应用前景。m p e g - 4 新采用的编码技术有小波 ( w a v e l e t ) 变换，高级运动估计，重叠运动补偿，视相关可扩展编码，位图形状 编码，对象编码，脸部动画以及动态网格编码等。 从1 9 9 8 年起，i t u t 的视频编码专家组( v i d e oc o d i n ge x p e r t sg r o u p ，v c e g ) 开始了h 2 6 l 标准的研制工作，旨在将编码效率比现有的视频编码标准提高 倍以上。2 0 0 1 年1 2 月，v c e g 与i s o i e c 的运动图像专家组( m o t i o np i c t u r e 第7 负共8 2 负 第一章概述 e x p e r t sg r o u p ，m p e g ) 合作，成立了联合视频小组j v t ( j o i n tv i d e ot e a m ) ， 开始致力于完成新的视频编码标准h 2 6 4 a v c 。i t u t 称之为h 2 6 4 ，i s o 称之 为a v c ( a d v a n c e dv i d e oc o d i n g ) ，作为m p e g 一4 标准的第1 0 部分。 这种新标准有以下五个特性： 1 更高的编码效率，与h 2 6 3 ( h 2 6 3 + ) 或m p e g 一4 相比，在相同的编码质量条 件下，h 2 6 4 最多可以节省5 0 9 6 的比特率。 2 更好的图像质量，1 t 2 6 4 在各种比特率条件下都可以提供满意的图像质量。 3 更强的时延适应性。h 2 6 4 可以在低时延模式下工作以适应实时通信应用 ( 如会议电视等) ，也可以在高时延模式下工作以取得最佳的压缩效果( 例如视频 图像的存储，基于服务器的视频流应用等) 。 4 更强的容错能力。h 2 6 4 提供了相应的工具来处理包交换网络中的丢包和 易于产生误码的无线信道中的误码问题。 5 更好的网络适应能力。在 j 2 6 4 中，视频编码层( v i d e oc o d i n gl a y e r ：v c l ) 和网络提取层( n e t w o r ka d a p t i n gl a y e r ，n a l ) 是彼此分离的，这样压缩后的 视频内容可以在不同类型的网络上传输，也使图像内容的打包和优先级控制更 加容易。 上述特点使得h 2 6 4 将成为通信、数字电视及互联网视频应用首选的标准， 可广泛应用于i n t e r n e t i n t r a n e t 上的多媒体流服务、视频点播、可视游戏、 低比特率的移动多媒体通信( 视频手机等) 、交互式多媒体应用、实时多媒体监 控、数字电视与演播电视、虚拟视频会议等等，并大有在上述领域一统天下的 趋势，有着非常广泛的开发和应用前景。 1 3h 2 6 4 视频压缩流程 h 2 6 4 的编码涵盖了视频编码层( v i d e oc o d i n gl a y e r ，v c l ) 和网络提取层 ( n e t w o r kk b s t r a s t i o nl a y e r ，v c l ) 。视频编码层的任务是高效地表达视频内 容，网络提取层的任务则是将v c l 提供的数据格式化并提供头信息，使其适用 于不同的传输层或存储介质。“” h 2 6 4 的总体结构如图1 1 所示： 第一章概述 翻1 11 2 6 4 的总体编码结构 本文主要讨论的是视频编码层。 h 2 6 4 视频编码层详细框图如图1 2 所示。 霹母出 数甓 鼍i 疆量爿夏曰一j 司一一确 i p 眨) 一母i 翻到蛩一 图1 2i t 2 6 4 视频编码层 图1 2 中，f n 表示当前输入帧。帧以宏块为单位进行处理( 对应原始图像的 1 6 x 1 6 个象素) 。每个宏块都按帧内或帧间模式进行编码。在任何一种情况下， 都由重建帧得到一个预测宏块p 。在帧内模式下，p 是由当前帧一第n 帧中己 进行编码、解码和重建的采样点构建的( 在图1 2 中用u f n 表示，使用未滤波 的采样点构建p ) 。在帧间模式下，预测宏块p 由一个或多个参考帧通过运动补 第9 砸共8 2 负 第一章概述 偿预测进行构建。在图中参考帧是作为己编码的帧f n l 出现的。每个宏块可 由一个或多个已经进行编码和重构的前帧或后帧( 以时间为顺序1 预测得到。将 预测宏块p 从当前宏块中减去，得到一个残差宏块d 。并对它进行变换、量化， 得到x 。对变换系数x 重新排序而后进行嫡编码。嫡编码后的系数与附加信息用 来从压缩的比特流中解出宏块( 比如宏块的预测模式、量化步长、运动矢量信息 等等) 。这些都被递交给网络提取层( n a l ) 进行传输或存储。 量化后的宏块系数x 被解码，用来重建一个帧，进而对下一个宏块进行编码。 系数x 经过再次伸缩和反变换，得到残差宏块d n 。它与原来的残差宏块d n 己 经不同，量化的过程带来了精度上的损失，所以d n 较d n 有失真。预测宏块p 与d n 相加得到一个重建宏块u f n ( 对原宏块的恢复，存在失真) 。用滤波器去 除块效应，重建的参考帧由一系列的宏块f n 构建。 1 4 片上运动估计器概述 从上文可以看出，h 2 6 4 数字视频编码器通过进行大量的运算消除了图像中 的冗余度，从而获鼐较低的传输码率。在整个的视频编码器中，由于运动估计 模块承担着巨大的运算量，因此一般都是作为独立的芯片设计单元，有些要求 较高的运动估计模块甚至需要几个芯片共同完成。目前比较成熟的运动估计模 块都是基于m p e g 一2 标准的，主要集中在i 蹦、c c u b e 、n t t 、三菱等大公司。与 此同时，基于更先进视频标准的运动估计芯片的研究一直没有间断过。 一个传统的运动估计芯片包括计算、控制、访存三部分，计算部分包括p e 运算阵列、后处理模块等；控制部分包括运算阵列控制器、读写控制器等；访 存部分主要指的是局部存储器及其读写接口。而基于h 2 6 4 标准的运动估计器 根据不同的算法需要一些额外的部件，如模式判别阵列、m e d i a n 运算部件等。 这些部件可以用软件实现，也可以用硬件实现。软件实现的优点在于节约成本， 易于实现较复杂的算法。而硬件实现的优点在于运算速度较快，并行性好。 本文所论述的运动估计器采用软硬件协同的方法设计，即一部分功能用软件 实现，另一部分功能用硬件实现。这样做的优点在于能对系统所实现的功能进 行折衷，便于产生一个最佳的软硬件分解方案来满足系统速度、面积、存储容 量、功耗、实时性等系列技术指标要求。同时在流片投产之前，便于对包含 软件、硬件的嵌入式系统所实现功能进行全面验证，以确保s o c 所实现的功能 第1 0 页共8 2 负 第一章概述 与最初的设计要求相一致。 这是一条具有挑战性的技术路线，软件的设计必须考虑芯片的硬件结构。而 芯片结构更需要硬件设计与软件设计的协同，使整个系统在协同设计中得到优 化。1 1 5 论文的主要研究内容 本文主要的研究内容是研究基于h 2 6 4 标准视频编码器中豹运动估计模块的 软硬件设计及其v l s i 实现，主要包括以下几个部分：第一、在探讨了用于运动 估计算法和其他几种快速搜索算法的基础上，对各种算法的优缺点进行了深入 研究并给出了选择运动估计算法胸原则，最后提出了改避韵快速运动估诗算法 和模式决策算法。第二、在确定了算法的基础上，对运动估计器进行软硬件功 能划分，确定整个系统的结构。第三、在完成了结构设计静基础上，分别对算 法做软件仿真和对硬件部分作v e r i l o g 语言描述，硬件帮玢包括r i , s c 运动估计 协处理器核和并彳i 驿列处理器。同时构建了验证平台，得出详细的仿真和验证 结果。 本文结构如下z 第一章为概述主要介绍各种视频压缩标准，h 2 6 4 视频压缩流程和片上运 动估计器概述。 第二章介绍了各种视频运动估计算法及它们的优缺点，筵提出了改进后的算 法。 第三章详细介绍了数字系统s o c 的设计流程，并提出了本系统的软硬件结构。 第四章主要介绍了r i s c 运动估计协处理器的指令格式和其硬件流水线结构 设计。 第五章主要介绍了并行s y s t o l i c 结构的概念，及其在本课题中的应用。 第六章给出了系统软硬件协同仿真验证的结果。 第七章简要总结了论文工作所取得的成果，并提出了不足之处和进一步工作 的展望。 第1 1 页共8 2 页 第二章视频运动估计算法的研究 第二章视频运动估计算法的研究 运动估计的作用是实现最佳帧间补偿预测，降低视频序列的时间冗余度以实 现高品质的数据压缩。运动估计算法的性畿对视频压缩系统的硬件实现以及解 码后的视频质量有着举足轻重的影响。对此，人们进行了多角度的深入研究， 提出了各种各样的运动估计模型。其中块匹配( b l o c km a t c h i n g ) 法由予其简单 的计算结构，较强的运动跟踪能力而成为目前最常用的一种运动估计算法，并 己广泛应用于h 2 6 x 和m p e g 等视频压缩编码的国际标准中。因此，本文主要研 究基于块匹配的运动估计算法。 在块匹配运动估计技珠中，全搜索( f s b m a ) 方法的搜索精度最高，但是它 的计算复杂度较高，为减小运动估计所需的计算量，很多快速运动估计算法被 提出，比如：二维对数搜索法( t d l ) 、三步搜索算法( t s s ) 、新三步搜索算 法( n t s s ) 、菱形搜索算法等。这些算法的基本思想就是将s n r 趋于极小的方向 定义为最小失真方向，并且假定其在偏离最小失真方向时是单调的。其实质均 是统一的梯度搜索算法，所不同的只是搜索路径和步长等。这些方法由于较快 的运动估计速度而得到广泛的应用，但它们的主要缺陷在于第一步搜索步长较 大使得搜索较小的运动矢量时效率不高，同时可能陷入局部最优，造成预测图 像质量的下降。因此，对一种快速运动估计算法来说，确定初始搜索点非常重 要。如果初始搜索点选择不好，便会偏离最佳匹配区，造成局部最优的情况。 对h 2 6 4 标准来说，多模式运动估计的新特点决定了基于这种标准的运动估 计器不但要进行多种模式的运动估计，而且还要在多种模式中决定一种最优的 模式。所以，对模式决策算法也需要作进一步的研究。 本文在研究了各种传统运动估计算法的优缺点和h 2 6 4 标准新特点的基础 上，提出了适用于新标准的快速运动估计算法和模式决策算法。 2 1 块匹配运动估计的原理1 1 块匹配的基本思想就是将当前图像帧分为若干个大小相同的块，对每一个块 ( 当前块) 分别在参考图像帧中的一定区域( 称为搜索窗) 内，按照定的匹 第1 2 页共8 2 负 第二章视频运动估计算法的研究 配准则搜索与之最接近的块( 称为预测块) ，预测块与当前块之间的位移称之为 运动矢量，它们的像素之间的差值称为残差块，预测块与当前块之间通过匹配 准则函数得到的值称为块失真度。这样当前帧中的每一块都可用一个残差块和 一对运动矢量来表示。图2 1 为块匹配运动估计的示意图。 材- h 哪i ，怯1 图2 1 块匹配运动估计 显然，残差值越小，越有利于压缩。因此运动估计的主要：目标就楚要使预测 块与当前块之间的块失真度最小化。 很明显，搜索窗尺寸大小选择对搜索结果有很大影响：搜索范圈越大，得到 更小残差块的可能性越大，但这会带来更大的运算量。通常选释的搜索范围是8 ， 1 6 ，3 2 ，4 8 等。 块匹配运动估计可从三个方向进行研究：块大小形状、块匹配准则和搜索策 略。目前，块大小形状和块匹配准则已经有了比较一致的选择，而搜索策略最 为复杂，它决定了一个算法的好坏，因此一直是快速运动估计研究的主要方向。 一般来说，块形状用正方形比较合适，这样比较利于图像的划分，也有利于 匹配准则函数的计算。不过也有其他算法采用别的形状( 如三角形、多边形等) 。 块的大小通常有多种选择，在m p e g l 和m p e 6 2 标准中，运动矢量以1 6x1 6 的宏块为单位。由于块尺寸较大，可能在一个宏块中包含不同运动的部分，造 成预测精度下降。在h 2 6 3 和m p e g 4 标准中，在宏块运动矢量基础上加入了8x 8 块的运动矢量，预测精度得到了一定程度的提高。在h 2 6 4 标准中，引入了七 种大小宏块的运动矢量，能达到较高的预测精度。 另外，有的运动估计算法，如分级式块匹配法采用的是块大小可变的方案。 第】3 页共8 2 负 第二章视频运动估计算法的研究 其基本思想是从最低分辨率开始，在每一层依次进行运动估计。低分辨率用于 确定相对较大块的位移初略估计，接着把低分辨率位移矢量的估计值传递到下 个高分辨率，较高分辨率用于精确调整位移矢量的估计。 块匹配准则是判断块相似程度的依据，因此匹配准则的好坏直接影响了运动 估计的精度；另一方面，匹配运算复杂度、数据读取复杂度在很大程度上取决 于所采用的块匹配准则。因此，提高运动估计算法的速度可以有两种途径，一 种是减少搜索匹配的点数，另一种是降低块匹配准则的计算复杂度。 常用的块匹配准则有以下几种： ( 1 ) 均方误差函数( m s e ) ： m s e ( m ，n ) 2 持y - 芝( i ：( m ，n ) 一i - ( i + m ，j + n ) ) 2 ( 式2 1 ) 该准则取m s e 最小对应的运动矢量作为搜索结果。 ( 2 ) 绝对平均差函数( m a d ) ： - i 一i m a d ( ) ：由l i ：( 。，n ) 一i ( i + m ，j + 。) 【( 武2 ，2 ) h t 0 ；0 该准则取m a d 最小对应的运动矢量作为搜索结果。 ( 3 ) 最大误差最小函数( m m e ) ： 埘e ( m ，n ) 。糕l i 。( m ，n ) 一i ，( i + r a ，j + n ) 1 ( 式2 3 ) 该准则取m ) i e 最小对应的运动矢量作为搜索结果。 实验表明，m s e 匹配函数运动估计的精度最高，但其众多的乘方运算用硬件 实现比较困难。m a d 匹配函数略差，但其相对简单的运算易于用硬件实现。删e 匹配函数则过于简单，没有利用匹配块所包含的特征信息，使运动估计的精度 大大降低。相对而言，m a d 准则函数比较实用，一度得到广泛使用。 s a d 准则出现以后，迅速取代m a d 被各种运动估计算法采用，因为它与m a d 的匹配效果等价，而计算量却大大减小： s a d ( m n ) =掣掣i i 。( m n ) 一i ( i + m ，j + n ) i( 式2 4 ) 0 ：弓嚣g 第1 4 页共8 2 硬 第二章视频运动估计算法的研究 这是因为如果采用相同形状大小的块，n 2 都是相同的，除以它没有任何必要。 另一方面，在计算s a d 的过程中，当发现块的部分s a d 已经大于当前最小s a d 时，可以中途退出，从而使计算量大大减少。 搜索策略是运动估计算法最关键也是最复杂的部分。搜索方向、搜索路线和 搜索路线的不同可以得到不同的搜索算法。本文以下部分就会讨论不同搜索策 略的运动估计算法。 评价一个算法的优劣，主要看其匹配的效梁帮羧索的时间复杂度。匹配效果 可通过人眼主观评价重构图像的质量，但这热毋缀大的主观牲和随意性，不能 进行定量的比较。因此，一般情况下，是通道甓豫韵平均峰值信噪比p s n r 来衡 量。p s n r 的计算公式如下： p s n r 21 0 l o g m ( 2 5 5 2 嘉毯，( * 一i ) 1 ) 2 2 传统的f s b m a 块匹配全搜索算法 ( 式2 5 ) 全搜索算法( f u l ls e a r c h ) 也称为穷羁搜索法，是块但配运础估计最早采 用的算法。它可以表述如下：若令x ( i ，k ) 袈示当前帧相对坐标i ，k 位置的橡素 值，对于参考块中的所有像素点的x ( i ，k ) ，都与搜索区域内的廊商搜索块对痤 的像素点去做s a d ( 如式2 4 所示) 计算，+ 精s a d 值在搜索区域的某个位置最小 时，则说明此位置就是当前参考块的最佳匹配块。 由于f s b m a 算法是穷尽搜索算法，也旋器说在绘定的搜索区域内的每一个可 能的位置都能计算并探测到。因此肯定可以我出当前给定搜索区域内的最佳匹 配宏块。但是正因为它是搜索区域全搜索的，因此在匹配的过程中会产生巨大 的计算量。其计算量可由式2 6 得出： ( 式2 6 ) 式2 6 中，p 和q 分别表示搜索窗垂直和水平方向的大小，g w 和g h 分别表 示一帧图像中在垂直和水平方向上的像素数，g 表示每秒的帧数。如果搜索窗大 小为1 6 ，一帧图像分辨率为7 2 0 x 4 8 0 ，每秒3 0 帧的话，每秒就要处理1 1 2 9x1 0 ” 个像素。对于更高分辨率的图像格式，f s b v j 算法的计算量是非常巨大的。 第】5 页共8 2 负 第二二章视频运动估计算法的研究 2 3 其他各类快速运动估计算法 由2 2 节可知，f s b m a 算法在作块匹配运动估计时会产生很大的运算量，尤 其是在作一些高清晰格式的图像( 如h d t v ) 时，这一点会尤为突出。为了降低 运动估计的运算量以更好的适应运动视频实时编码的需要，有人提出了很多快 速搜索算法，如二维对数搜索法( t d l ) 、三步搜索算法( t s s ) 、新三步搜索 算法( n t s s ) 、菱形搜索算法、多分辨率搜索算法等。以下对这些算法加以简单 介绍。 1 、二维对数搜索法( t d l ，t w o d i m e n s i o nl o g a r i t h m i cs e a r c h ) 二维对数搜索算法是第一个利用象限划分搜索区域的快速匹配算法。算法的 中心思想是，由每一步搜索的结果，确定下一步的搜索所在的象限范围，并动 态地变化搜索的步长，最终找到相应的最佳匹配位置。 算法对于不同大小的搜索窗口有不同的搜索步长，具体的搜索步骤如下： ( 1 ) 、如果搜索最大范围为d ，则第一步的搜索步长为2 ”“，这里 x 是不 小于x 的最小整数，假设计算得到的步长为s ，则对中心点以及在x ，y 轴上距中 心点s 的四个点做匹配计算。举个例子说明为，如果搜索的中心点为( 0 ，0 ) ，则 第一步搜索的匹配位置为：( 0 ，0 ) ，( 一s ，0 ) ，( 0 ，s ) ，( s ，0 ) ，( 0 ，s ) 五个点； ( 2 ) 、如果第一步得到的最佳匹配位置为中心位置( c ，c ，) ，则将搜索步长减 半，中心位置不变，按照第一步的方法继续进行搜索。如果第一步得到的最佳 匹配位置是其余四个位嚣中的一个( a ，b ) ，则搜索步长不变，中心位置变为 ( a ，b ) ，( c ，c ，) ：= ( a ，b ) ，按照第一步的搜索方法进行搜索，直到搜索步长变 为l ； ( 3 ) 、这时步长为1 ，进一步搜索当前最佳位置周围8 个点，即点( c 。，c ，) ， ( c 。，c 。) ，( c x , c y + 1 ) ，( c 。，c 。) ，( c 。，c ，) ，( c c ，一。) ，( c c 一。) ，( c 。一c ，) ，找 到最后的最佳匹配点，这个点的位置矢量就是当前块的运动矢量。 下面是一个采用t d l 算法进行匹配运算的图例， 第1 6 页菇8 2 ：! j ： 第二章视频运动估计算法的研究 l 、7 ；r 卜 ，、 ，； t + 曩蕊麓、，0 、 r 夺 一，：，、一 弋 罴米粼kk：7 ，：裂k 粼k 5y vy 十一 l“ 一l 丫 、 w - _ ，、叁，k v 、 、 r _ 幽2 , 2t d l 接索算法实例 图2 2 中，搜索最大范围为8 ，用点填充的圈所在的位置是搜索中每一步得 到最小值，位置分别为( 0 ，一4 ) ，( 4 ，一4 ) ，( 6 ，一4 ) ，最终得到的最佳匹配点 位镛! 是( 7 ，一4 ) 。 2 、三步搜索算法( t s s ，t h r e es t e ps e a r c h ) “1 三步算法和两维对数算法几乎同时提出的，它们在算法思想上有很大的相似 之处。三步算法的不同点在于它不只搜索中心位置周围的四个点，而是对周围 位置的8 个点作匹配运算。 算法的中心思想是，利用上一步搜索得到的最佳匹配位置作为当前搜索的中 心位置，每做一步，搜索的步长减1 。这种算法在( 一7 ，+ 7 ) 搜索窗口中刚好用 三步作完，所以这种算法被称为三步搜索算法。 算法的搜索步长依窗口大小而定，通常用于( 一7 ，+ 7 ) 的搜索范围，初始步 长为3 ，具体搜索步长如下： ( 1 ) 、如果搜索最大范围为d ，则第一步的搜索步长为2 “。“，这里 x 是 第1 7 页共8 2 页 第二章视频运动估计算法的研究 不小于x 的最小整数，假设计算得到的步长为s ，则对中心点以及在x ，y 轴上距 中心点s 的四个点作匹配运算。举个例子说明为，如果搜索的中心点为( 0 ，0 ) ， 则第一步搜索的匹配位置为( 0 ，0 ) ，( 一s ，0 ) ，( 一s ，s ) ，( s ，0 ) ，( - s ，s ) ，( s ， 0 ) ，( s ，一s ) ，( 0 ，一s ) ，( 一s ，一s ) 九个点； ( 2 ) 、将搜索步长减l ，假设第一步得到的最佳匹配位置是其余五个位置中 的一个( a ，b ) ，则中心位置变为( a ，b ) ，( c x ，c y ) ：= ( a ，b ) ，按照第一步的搜 索方法进行搜索。直到搜索步长变为1 ； ( 3 ) 、这时步长为1 ，进一步搜索当前最佳位置周围8 个点，即点( c x 一1 ，c y ) ， ( c x 一1 ，c y + 1 ) ，( c x ，c y + 1 ) ，( c x + l ，c y + 1 ) ，( c x + l ，c y + i ) ，( c x + l ，c y ) ， ( c x + l ，c y 一1 ) ，( c x ，c y 一1 ) ，( c x 一1 ，c y 一1 ) ，找到最后的最佳匹配点，这个点的 位置矢量就是当前块的运动矢量。 图2 3 是一个采用t s s 算法进行匹配运算的例子。 图中( 3 ，一3 ) ，( 3 ，一5 ) 分别是第一步和第二步得到的最佳匹配点，最终得 到的最佳匹配匹配点为( 2 ，一6 ) 。 三步搜索算法最多只需要作2 5 个位置的匹配计算，相对于全搜索来比，大 大减少匹配运算的复杂度，而且数据读取比较规则，易于硬件实现，所以被许 多标准推荐使用。 3 、新三步搜索算法( n t s s ，n e wt h r e es t e ps e a r c h ) 。” 新三步搜索算法是基于三步搜索算法，并在三步算法的基础上作一些改进。 三步算法由于它的简单高效和数据存取的规律性受到了普遍欢迎。然而，三步 算法对现实视频序列的中心偏置特性欠缺考虑。新三步算法在这方面作了改进， 从而达到了比三步算法更好的性能。 新三步算法的中心思想是，考虑到现实视频序列中，在相邻的两个帧之间大 部分块可以认为是静止的，或者作缓慢移动的，因此，在三步算法的第一步运 算是，对搜索窗口中心相邻的8 个点也同时作匹配运算，这样，对做慢速运动 的物体，可以找到与它最匹配的块。 算法的具体步骤如下： ( 1 ) 、对搜索窗口中心9 * 9 的矩形框和3 * 3 的矩形框的1 7 个点作匹配运算： 这1 7 个点的位置如图2 4 所示。 ( 2 ) 、根据第一步得到最小s a d 值的位置决定第二步的匹配位置： 第1 8 页共8 2 页 第二章视频运动估计算法的研究 如果在搜索窗口的中心位置的到最小的s a d 值，则停止搜索； 如果最小的s a d 值在3 * 3 的矩形框上得到，则搜索以此点为中心位置的3 * 3 的窗口，并跳到第三步； 如果最小的s 煳值在9 * 9 的矩形框上得到，则搜索的步骤与t s s 算法相讯 并跳到第三步： - 7靠，v43 u z l甜i23 ，b 一r 、 + 锶粼， ，-、， 冷降静y v ”孑 令 、； y，一， 2 - ,，、 yy y 一， 一、 2 - , vvv j 一 图2 3t s s 算法实例 ( 3 ) 、以第二步得到最佳匹配位置为中心，作最后的3 * 3 窗口中九个点的匹 配，得到最小s a d 值的位置，就是最佳匹配位置。 由于n t s s 算法采用了两级中止技术，在大多数情况下都是提前终止搜索过 程，所以获得了比t s s 低的运算复杂度。 若搜索范围为( 一7 ，+ 7 ) ，搜索窗口大小为1 5 1 5 ，n t s s 在最好的情况下只 需要作1 7 个点的匹配，在最坏的情况下需要作3 3 个点的匹配。由于宏块中心 偏置在现实视频序列中是普遍存在的，所以在低速率视频应用中，n t s s 算法的 优点可以得到较好的发挥。 第1 9 页共8 2 页 ，：，：o：2 3 4 _ 第二章视频运动估计算法的研究 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 0 0 0 0 0 0 0 o o o o o o o o o o o o o o o o o o 0 0 0 o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 0 0 0 0 0 0 0 0 0 0 0 0 0 o o o o o o o o o o o o o o o o o o o o o 0 0 0 0 0 0 o o o o 0 0 0 0 0 0 0 0 0 0 0 o o o o o o o o o o o o o o o 圈24n t s s 算法篇一步掩索位詈示意图 4 、菱形搜索算法。” 菱形搜索算法采用了不同的菱形搜索，并且没有对搜索的步数进行约束，以 确保搜索的精度。 该算法第一步的搜索位置呈菱形形状排列，在以后的步骤中，每一步的搜索 位只有上一步得出的结果确定。 算法的具体步骤为： 1 ) 、对搜索窗口中心，如图2 5 的菱形形状的九个位置作匹配运算，如果得 出的最佳匹配位置在菱形的中心( c ，c ) ，则跳至第三步；如果得出的最佳匹配 位置在菱形的边上( c 一1 ，c + 1 ) ，( c 一1 ，c 一1 ) ，( c + l ，c 一1 ) ，( c + l ，c + 1 ) ，或顶点上 ( c2 ，c ) ，( c + 2 ，c ) ，( c ，c2 ) ，( c ，c + 2 ) 则跳到第二步： 2 ) 、如果第一步得到的最佳匹配位置在边上，即点( c - 1 ，c + 1 ) ，( c - 1 ，c 1 ) ， ( c + l ，c 一1 ) ，( c + l ，c + 1 ) ，则作边搜索，边搜索是需要附加的搜索位置，在四个 边上的情况相同；如果第一步得到最佳匹配位置在顶点上，即点( c 一2 ，c ) ， ( c + 2 ，c ) ，( c ，c 2 ) ，( c ，c + 2 ) ，则作顶点搜索，顶点搜索是需要附加的搜索位 置。如果这一步得到的最佳匹配位置在中心位置，则跳至第三步，否则，跳回 第2 0 页共8 2 负 第二章视频运动估计算法的研究 第二步开始，继续作搜索； 3 ) 、以上一步得到的最佳匹配位置( c ，c ) 为中心，对( c l ，c ) ，( c 十l ，c ) ， ( c ，c 一1 ) ，( c ，c + 1 ) 四个位置作匹配运算，得到最终的最佳匹配位置。 图2 6 是应用菱形搜索算法进行搜索的范例： 图2 6 中，如果第一步得到最小s a d 的位置是坐标原点，则对a 、b 、c 、d 四个位置作最后的匹配运算。否则要对附加的搜索位置进行匹配。图中得到的 最佳匹配位置是( 6 ，一3 ) 。 对于相同的搜索范围，得到相同的运动矢量，菱形搜索算法进行的运算要明 显少于其他算法。这种搜索算法不限制搜索的部数，即对各个方向都进行搜索， 又着重考虑水平竖直方向，所以这种算法可以使搜索避免误找到局部最佳位置， 得到更好的性能。 一h 5 出 栅 卜 l 俐l 丫 圈2 5 第一步搜索的位置 4 、多分辨率搜索算法。” 多分辨率搜索算法也称分层搜索法。其主要思想是将先得到图象的不同分辨 率的分层表示，然后在逐层由粗到细搜索。 假设块f 的大小为n n ，且n = 2 “，那么可以得到该块的n + l 层描述，记为 f | l ，( 0 = i n = n ) 。f o 只有一个值，即块f 的平均值，r 是对f 中的每个2 2 取均值得到的，大小变为其i 4 。这样从f “到f 0 形成了一个自下而上的金字塔 结构。 金字塔层的生成方法可以描述如下： f ”1 ( i ，j ) = 1 4 ( f “( 2 i 一1 ，2 j 一1 ) + f “( 2 i ，2 j 1 ) + f “( 2 i 一1 ，2 j ) + f “( 2 i ，2 j ) ) 1 = m = n ，特别地，当2 p = n 时，阵列不需要延迟寄存器组，数据完全在p e 间流动。 第7 0 页共8 2 页 第五章脉动阵列结构的设计 5 4 无块间延迟的脉动阵列结构 消除块间延迟与消除行间延迟原理上是一样的。在当前宏块运动估计期间， 将下一个宏块运动估计所需要的数据提前输入阵列，当前宏块运动估计结束时 阵列中下一个宏块的数据也已经准备就绪了，这样阵列可以无延迟地开始新一 周期的运动估计，从而保证一帧图像相邻编码宏块进行计算的连续性。在无行 间延迟脉动阵列的基础上构建无块问延迟的脉动阵列，需要增加一组数据传递 通道，在宏