（通信与信息系统专业论文）视频帧间编码技术研究与实现.pdf

摘要 摘要 在视频压缩系统中，压缩比提高的大部分贡献来自帧间编码技术的采用。然 而帧间编码的运动估计和补偿涉及大量的数据的传输和运算，在现有的芯片运行 时钟和存储器带宽条件下，对视频压缩系统的实时实现构成了瓶颈。这必须通过 有效的v l s i 结构设计来解决。 在研究和分析了大量运动估计算法基础上，本文提出了一种改进的新的金字 塔运动估计算法及其v 】l s i 实现结构，相对于全搜索算法，它的性能降低非常小， 而资源占用率和运算时间却大大节省，而且充分利用搜索窗数据的相关性降低了 对数据传输带宽的要求。 针对许多快速运动估计算法不适合v l s i 实现的问题，本文给出了一种基于 m c u 架构的运动估计协处理器设计，结合了m c u 架构的灵活性，并在其中加入 运动估计专用处理结构和指令，这一设计既通过指令调度的方法满足了不同搜索 位置的灵活性又通过专用处理结构加速了固定搜索位置的匹配速度，在整体结构 上串行处理，局部高速并行处理满足了实时性的需求。 在h 2 6 4 的运动补偿中，半象素插值相对于以往的标准难度增加了很多，插 值的v l s i 结构设计是否高效直接影响编解码器是否能够实时运行。在本文中，我 们给出了一种并行高效的设计，通过合理划分数据存储r a m 提高处理并行度，多 级滤波器之间结构紧凑，数据利用率高，实验证明这一结构完全可以满足h 2 6 4 h d t v 实时性的需求。 关键字：视频编解码，运动估计，运动补偿，v l s i a b s t r a c c a b s t r a c t i n t e r 丘锄ec o d i n gi so n eo ft h em o s ti i n p o n 如tp a ni nv i d e 0c o d i n gs y s t 锄，a i l d c o n t r i b u t ct ot h ec o m p r e s s i o ne 伍c i 锄c yi nag r e a tm e a s u r e 王k t t h em o t i o ne s t i m a t i o n a i l dm o t i o n 咖p e n s a t i o ni i li 1 1 t e rm l i n ec o d i n gd e a lw i t hl a r g e 锄o i i n to fd a t a t r 黜m i s s i o na n dc o m p u t a t i o n i u m si 1 1 幻ab o t l l e n o c ki e x i s t i l l gc h i pl o c k 丘铷u e 玎c y 趾db 她d w i d t ho fm e m o r yc o m p o n e n t s t h ep r o b l c m 啪o n l yb es e m e dd o w nb y e 髓c i e mv l s ia r c h i t e c 札r e b 丛e do nt h er c s e 盯c ha n da n a l y s i so fl o t so fm o 吐o n 鹤t i | n a t i o na i 酬t h m s ，an e w p y r 锄i dm o t i o ne s t i i n a t i o na 1 9 0 r i t h n la i l di t sv l s ia 出瞅吡ea r ep r o p o s e d nf i l l l y u t i l i z e dt h er c l a 晰i t yo fn c i g h b o r i gs e a 蕾c hw i n d o wd a t at or e d u c eb a n d w i d t hr e q u e s t c 咖叩a r et 0 f i l ns e 甜c ha l g o r i t i l m ，t h ec o m p r e s s i o np e r f o 粕c er e d u c c se x t r e m e l y s l i g h n y ，b u tb a 珂聃眦r e s o u r c e 卸dc o m p u t a t i 叩t i m e a r c1 a i 琶e l ys a v e d hv i e wo ft h a tm a n yf a s ta l 鲥t h m sd o ts l l i tf o rh a 埘w 盯er e a l i z 8 ，am o t i o n e s t i i n a t i o n0 0 p c e s s o rb a s e do m c ua r c h i t e c t u r ei sd e s i g n e d 皿i sd e s i 印m a l 【e su s e o fm e n e x i b n i t yo fm c u 锄c l l i t c c t l h e ，a i l da d d ss o m es p e d a li n s t r u 舐o na n dp r o c c s s i n g s t m c t i l r et oe n h 缸c et h ep e 订0 m a i l c e i tm e e t st h er c a lt i m er e q u c s to fc o m p l e x a 1 9 0 r i t h mt h r o u g hs e r i a lp r o c e s s i n gi n o v e r a l ic o n s t m c t i o n 粕dp a n i a lh i g h s p e e d p a r a l l e lp m c e s s i n g t h ec o m p c n 朝6 0 ni nh 2 6 4i sm u 曲m o r ec o 1 p l i t et h 蛆c v e rb e f o r e 。w h e t h e r 也ei n t e r p o l a t i o nc 0 璐t n l c t i i se 伍c i e n td i r e c n yi m p a c t st h er c a lt j m ep e r f b 衄粕c eo f v i d e 0c o d e c i nt h i sp a p e r w ep r o d u c e dah i g hp e 哟册a n c e 粕dp a r a n e li n t e r l ，0 l a t i o n a r c h i t e c t u r c r e f e r e n c ed a t aa r er c a s o n a b l yd i v i d c dj n t on i n eb l o c ：kr 锄s ，s ot h a td a t a c a nb er e a do u ti p a r a u e l t h ee x p c 曲e n tr e s u l ts h o w st h a tt h i sa r c h i t e c c l l r e 啪m e e t t h ed 唧a l l do fh 2 6 4h d t vt i m er c u e s t k 叼w o r d ：v i d c oc o d e c ，m o t i 0 e s t i i n a l i o n ，m o 曲nc o m p e n s a 抽n ，v l s i 创新性声明 y8 5 89 7 6 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任何 贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：缉兰鳖日期：翌! 尘 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规息即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密的 论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名：日期：勋口多。，矿 第一章绪论 第一章绪论 1 1 引言 信息技术的发展日新月异，正在从各个方面改变着人类的生活方式。从通信 到医疗健康，从商业到教育，各个方面都体现出信息在当今社会中的重要性。随 着信息技术的进步，人们希望无论何时何地都能够方便、快捷、灵活地通过语音、 数据、图像与视频等多种方式进行通信。这其中，对视觉信息的需求占据了大约 7 0 以上，它能给人们以直观、生动的形象反映，也正因此，图像和视频的传输 更受到人们越来越广泛的关注。 经数字化后的视频数据有海量性的特点，给视频传输和存储造成了很大的困 难，在坤视频通信中这一问题尤为突出。因此，如何有效地压缩视频数据，以最 少的码字获取所需的信息，一直是研究者们契而不舍追求的目标。经过5 0 多年的 发展，在国际国内逐渐形成了多个标准化组织以及一系列视频编码标准，这些标 准融合了各种性能优良的图像编码方法，代表了视频编码的发展水平。 近年来，随着深亚微米集成电路设计制造技术的迅猛发展，在一个芯片上集 成一个超大规模的复杂系统逐渐成为可能，视频编码系统的s o c 实现也随之成为 更加活跃的研究领域。视频编码标准从1 9 9 0 年的h 2 6 1 到善前的h 2 6 4 复杂度在 不断提高，其硬件实现的难度也不断的加大。视频编解码帧间压缩技术包含对大 量视频数据的处理，是编解码器实现的瓶颈，如何在现有的硬件处理速度和存储 器传输带宽下，实时完成视频编解码，正是视频编解码帧间技术硬件实现所要解 决的问题。 1 2 国内外研究现状与技术背景 s h 蛆o n 的编码定理告诉我们：一个具有率失真函数r ( d ) 的信源，若有平均 失真d ，并具有两个任意小的正数# 与6 ，则必定存在一种信源编译码方法使其信 息比特率r ，r 佃) + s ，而平均失真ds d + 6 ，也就是说码率在某个界限内的压 缩编码是有可能的。这为视频压缩及信道编码奠定了理论基础。 研究视频图像数据可以发现其中存在大量的冗余，这些冗余主要表现在空间 冗余度、时间冗余度两个方面，其他还包括信息熵冗余、视觉冗余、结构冗余、 知识冗余、纹理统计冗余等等，减少这些冗余度可以极大地减少图像的数据量。 三一 塑堡塑塑塑堡堡查盟竺窒量塞垫 视频编码方法研究的主要内容也就集中在如何有效地减少这些冗余。 视频编码方法种类繁多，从信息保持的角度可以分为无损压缩和有损压缩两 大类。无损压缩利用数据的统计冗余( 数据之间的相关性、可预测性) 进行压缩， 以预测编码和熵编码为基础，可完全恢复原始数据而不引入任何失真，但其压缩 率受到数据统计冗余度的理论限制，一般为2 ：1 到5 ：1 。此类方法广泛用于文本数 据、程序和特殊应用场合的图像数据( 如指纹图像、医学图像等) 压缩。鉴于压 缩比的限制，仅使用无损压缩方法不可能解决图像和数字视频在存储和传输应用 中的问题。因此，视频有损压缩方法也得到了长足的进步和发展，它除了利用统 计冗余进行压缩编码外，还利用了视频数据的视觉冗余特性，即利用人类视觉系 统( h v s ) 对视频信息中某些频率成分不敏感的特性，允许压缩过程中损失一定 的信息，这虽然不能在解码端完全恢复原始数据，但所损失的部分信息对理解原 始图像的影响相对较小( 即视觉无明显失真) ，同时却换来了相当大的压缩率。 图1 - 1 视频图像压缩编码国际标准发展史 国际标准化协会( m m 砒i a ls i d a r d i 日t i 衄0 r 舯i z a 吐o n ，i s o ) 、国际电子学 委员会( h t e m a t i a 1 日e c c 砌n i 铬c 【啊m i t i c e m c ) 、国际电信协会( h l t e m a t i 锄a l t e l e c o m m u n i c a t i o nu i o n ，u ) 等组织于二十世纪九十年代领导制定了三个有关视 频图像压缩编码的系列化的国际标准tj p e g 标准、h 2 6 x 标准和m p 丑g x 标准， 图1 - 1 和表1 1 总结了视频编码标准的发展历史及各自的设计目标、应用场合， 除此之外还有一些过渡性的、没有形成很大影响的非主流的视频压缩算法，比如 兀u - t 的h 2 6 2 ，m i c r o 矗公司的w m 系列，o s 2 公司的v p 系列、r e a i n e t w o r k s 公司的r m 等，这里不再一一列举。 标准标题制订者 目标应用场合 v i d e oc o d e cf o ra u t i o h 2 6 lv i s u a ls e r v i c e sa ti t u t 综合业务数字网 p x 6 4 南、t s f s i s d n 中的视频会议 p r e g r e s s i v eb i l e v e l j b i gj p 阱传真、打印等 i m a g ec 伽p r e s s i o n d i t i g a lc o m p r e s s i o na n d 数字照相、图像视 j p e gc o d i n go fc o n t i n u o u s t o n ej p e g 频编辑等 s t i l li r i i a g e 第一章绪论 c o d i n go fm o v i n gp i c t u r e s a n da s s o ci a t e da u d i of o r 光盘存储、家用视频 m p e g 1m p e g d i g i t a ls t o r a g em e d i au p 摄像、视频监控等 t o1 5 m b i t s s g e n e r i cc o d i n go fm o v i n g 数字电视、d v d 、高 m p e g 一2p i c t u r e sa n da s s o c i a t e d蝴e g 清晰度电视、有线电 视及卫星电视、视频 a u d i o 点播等 h 2 6 3y i d e oc o d i n gf o rl o wb i t i t u t 桌面可视电话、移动 h 2 6 3 +r a t ec o 岫u n i c a t i o n视频通信等 i p 网络视频会议、交 c o d i n go fa u d i o 叫i s u a l 互式视频通信、便携 m p e g 一4 砌e g 0 b j e c t s 式视频通信终端、专 业视频等 v i d e oc o d i n gf o rl o wb i t桌面可视电话、移动 h 2 6 3 + + i t u _ t r a t ec o 加功u n i c a t i o n 视频通信等 j p e g 2 0 0 0i n l a g ec o d i n g 传真、电子商务、卫 j p e g 2 0 0 0 j p e g星通信、遥感图像编 s y s t e m 码、i p 网图像监控等 有线电视、无线视频 通信、包基网络的视 j o i n tv i d e os p e c i f i c a t i o n m p e g 频流传输、i p 视频会 h 2 6 4 a v c( i t u tr e c h 2 6 4 i t u t 议系统、光盘存储、 i s 0 i e c1 4 4 9 6 1 0a v c ) 高质量视频编解码 系统、多媒体邮件等 视频编解码一系列标准的制订，规范了视频编解码的技术参数，但在视频编 码器的实现中并非所有流程技术都固定不变，运动估计算法就是其中比较灵活的 一部分。在视频压缩过程中，可以根据实际应用对图像质量、码率和实时性的需 要，选择相应的运动估计算法。因此运动估计算法的v l s i 设计也一直是比较活跃 的研究领域。 运动估计涉及大量数据的运算，以【1 6 ，+ 1 6 1 的小范围全搜索为例，每处理一个 宏块的运动估计需要输入2 3 0 4 字节的搜索窝数据，做任意一个位置的匹配运算时 需要进行2 5 6 次减法和绝对值运算、2 5 5 次加法运算，以及一次比较运算，在全搜 索的情况下，做一个宏块的运动估计共需要2 6 2 1 4 4 次减法运算、2 6 2 1 4 4 次绝对值 运算和2 6 1 1 2 0 次加法运算，还有1 0 2 3 次比较运算。而一个c 诬视频帧中有3 9 6 个宏块，可见运算量是巨大的，如果每一次运算都占用一个时钟周期，所耗费的 时间也是可观的。 在采用全搜索运动估计算法时，相邻位置的搜索窗数据有很大的相关性，利 4 视频帧问编码技术的研究与实现 用这一点可以使多个位置的匹配运算流水线操作，从而节省大量的时间，但总的 运算量无法减少。在采用快速算法的设计中，运动估计不需要对搜索窗内的每个 位置进行匹配，节省了加减法和绝对值的运算次数，但同时带来了匹配位置数据 不规则的影响，使得时间上相邻的搜索位置在空间上不再具有相关性，无法并行 地对多个位置进行匹配。像三步法和钻石搜索法这样的运动估计算法，在对算法 步骤稍加修改的情况下仍可以挖掘相邻搜索位置数据的相关性，但像m 、，f a s t 和 p m 凇t 这样的高效快速算法，已经很难设计对应它的阵列运动估计处理器。 新的运动估计算法层出不穷，其相应的v l s i 结构设计也随应而出，但v l s i 结构设计远跟不上算法更新的步骤。而在实际的应用中，针对需求采用什么样的 运动估计算法，相应地如何设计满足时间和资源限制的算法v l s i 结构，始终是视 频编码硬件实时实现所首要关注的问题。 1 3 本文研究内容及主要贡献 本文详细介绍了视频编解码中的帧间压缩技术，介绍了多种块匹配运动估计 算法，给出了全搜索运动估计算法的v 】l s i 结构，并对这一结构进行了深入研究， 提出了加速运动估计运算的改进算法及硬件设计方案：似金字塔搜索法。本文还 对快速搜索法的可编程v l s i 设计进行了研究，给出了一种基于m c u 架构的运动 估计协处理器设计方案。针对h 2 6 4 a c 中的复杂l 4 象素精度运动补偿，作者 给出了一种快速插值硬件结构设计。 作者深入研究了业界提出的多种块匹配运动估计算法和硬件实现结构，成功 地完成了m p e g 4 a s p 编码器中的运动估计v 】l s i 设计。自行设计的似金字塔搜索 运动估计加速器和基于m c u 架构的运动估计协处理器均已运用于实际的视频编 解码系统。作者设计的h 2 6 4 运动补偿插值器成功地解决了h 2 6 4 瑚) r v 解码器 对运动补偿实时性的要求。此外，作者成功地完成了m p e 0 s p 编码器在n 公 司d m 6 4 2 芯片上的系统优化，优化性能基本达到实时要求。 本文的结构安排如下： 第一章绪论。简要介绍了视频压缩编码技术，回顾了视频编解码标准及其应 用，在此基础上给出了本文研究内容和主要贡献。 第二章帧问视频编解码技术及硬件实现结构。重点介绍了基于块匹配的运动 估计技术，给出了一种全搜索算法的v l s i 实现结构。 第三章似金字塔运动估计算法及其v l s i 结构。对全搜索算法及其v l s i 结 构进行了改进，介绍了提出的似金字塔搜索算法及其v l s i 结构。 第四章基于m c u 架构的运动估计协处理器研究。详细介绍了基于m c u 架 构的运动估计协处理器的总体v l s i 结构以及内部各模块的运行机制。 第一章绪论 第五章h 2 6 4 运动补偿插值v l s i 结构研究。对h 2 6 4 的补偿技术进行了研究 针对其插值部分的实时实现，给出了对应的v l s i 设计。 5 第二章帧问视频编解码技术及硬件实现结构 第二章帧间视频编解码技术及硬件实现结构 2 1 块匹配运动估计技术 目前的视频压缩编码国际标准中，最为有效而实用的技术是基于运动估计和 d c t 的混合编码方法。m p e g 4 标准引进了基于对象和内容的编码思想，有人称 其为第二代视频编码技术，而把运动估计和d c t 结合的混合编码方法称为第一代 视频编码技术。第二代视频编码技术引进了一些极具吸引力的概念，但是限于目 前的技术发展水平，其实用性在实时视频通信中还难以体现，目前占主导地位的 编码思想仍为运动估计和d c t 的混合编码方法，在现有视频压缩标准中性能最好 的h 2 6 4 标准也是基于这一思想的。 在这一混合编码方法中，运动估计是重要的帧间编码技术，它可以去除帧间 冗余度，提高压缩比。在连续的视频帧中，不失一般性，我们假设当前帧某像素f 或 像素块) 是上一帧的某个位置移动过来的，在做编码时以那个位置上的像素值作为 预测，这样可以有效地节省码字。我们把这个相对位置称为运动矢量，求运动矢 量的过程称为运动估计，利用运动估计进行预测编码的技术称为运动补偿。 块匹配法基本思想如下：将一帧图像分割成材的小块，假设块内各个象 素作相同的运动，且只作平移运动。虽然实际上块内各点运动不一定相同，也不 一定只有平移运动，但m 较小时，上述假设可近似成立。块匹配法对当前帧 图像的每一块，在上一帧的一定范围内搜索最优匹配，并且认为本块就是从上一 帧( 或其他已编码帧) 最优匹配块位置处平移过来的。设可能的最大偏移矢量为 出。，咖。，则搜索范围为似+ 2 出。) x ( + 2 由一) 。图2 1 示出了待匹 配块与搜索区的几何位置关系。 图2 1 块匹配运动估计示意图 视频帧间编码技术的研究与实现 运动矢量由最优匹配位置来判定，判定函数为： 肘矿- ( f 地， f 吩) ； ，y ) i r ( ( m ，甩) 。( m + 工，n + y ) ) ；肘n x ；小【o ，肘一1 】， ( 2 1 ) n 【o ，一1 】，工【一出m a x ，出m a x 一1 】，y 【一毋m a 】【，毋m a 】【一1 】) 其中，r 为相关性评价函数；l 表示参考帧与当前帧之间的距离，f 可正可负， 分别表示前向运动估计和后向运动估计； ( m ，n ) 表示当前帧图象的灰度值， 。+ 工，以+ y ) 表示参考帧图象的灰度值，x ，y 表示参考位置的偏移值。 在公式( 2 1 ) 中，评价函数r 有多种选择，在块匹配运动估计中，通常有三种 匹配准则：规一化相关函数c c f ，均方误差胍踞，平均绝对差j l ，他们的定 义如下： 1 ) 规一化相关函数( n 0 姗a l i z e dc 0 s tc 0 m l a t i o nn l n c t i ) 三 ( 小，n ) t 西+ x ，n + ) ，) c c f ) ，) 一堕唑可而 ( 2 2 ) tmn、7 2tm n、v i 荟荟加一ii 善薹儡( m + 五) | 在这种准则下r ，_ ) ，) 一c c f 0 ，y ) 。 2 ) 均方误差( m e 跹s q u a e 玎0 r ) 脚( ) 。亩聂善【 ( m ，一) 一“m 抖+ ) ，) 】2 仁3 在这种准则下r 0 ，) ，) - 1 朋硒o ，y ) 。 3 1 平均绝对差( m e a na b s o l u t ed i 船r e n c e ) 脚。亩荟荟i ，玎) 一 一) l 在这种准则下尺o ，) ，) - 1 ，批4 d y ) 。在绝大多数情况下，1 删是常数，因 此为了简便计算，我们通常将勉仞0 ，) ，) 演变为绝对差豇心y ) ( s 岫0 fa b s o l u t e d i 艉r e n c e l ； 哇d o ，) ，) - 朋4 脚o ，y ) 多受i 西，再) 一 。+ z ，以+ y ) l 忙_ 5 一兰三i 西，再) 一 - + z ，以+ y ) l ” 上述三个公式是运动估计运算中常用的匹配准则，在运动估计算法的硬件实 现中，出于运算复杂度的考虑，一般都会采用盛作为匹配标准a 2 2 块匹配运动估计算法 运动估计算法的目的在于快速而准确地找到最优匹配位置。在现有的算法中， 最简单、最准确的是全搜索运动估计算法，但它的计算量大很难满足实时性的要 第二章帧间视频编解码技术及硬件实现结构 求。在此基础上，人们又发展了多种快速算法，以下分类介绍。 2 2 1 全搜索算法 全搜索算法是最直接的块匹配算法，它对( m + 拙。) c + 2 咖一) 搜索范围 内所有可能的候选位置进行匹配运算，得到最优的匹配位置。单从运动估计的角 度来看，全搜索算法无疑是最好的算法。在运动估计算法的硬件实现中，这一算 法可以充分利用相邻搜索位置的相关性，提高数据利用率。但这一算法毕竟运算 量巨大，在很多实际应用中无法满足软硬件条件的限制。 2 2 2 启发式算法 在全搜索算法中，为了得到最优匹配位置，对搜索窗中每一个位置进行了遍 历。启发式算法通过分步匹配减少匹配位置数，每一步的匹配都可以以很大的概 率将最优位置锁定在更小的范围之内。这类算法都基于一种假设：搜索位置离匹 配位置越远，对应的鲥田值越大，试验表明这种假设在大多数情况下是成立的。 这类算法包括：二维对数搜索法，三步搜索法，四步搜索法，新三步搜索法，新 四步搜索法，钻石搜索法和六边形搜索法等。下面以典型的三步搜索法为例介绍。 三步搜索法的中心思想是：首先以搜索窗中心位置为搜索中心，搜索范围的 一半为步长，在横纵方向进行搜索，在以后的每一步搜索中利用上一步搜索得到 的最佳匹配位置作为当前搜索的中心位置，搜索的步长减1 。这种算法在( 7 ，+ 7 ) 搜索窗口中刚好用三步做完，所以被称为三步搜索算法。 三步搜索法搜索步骤如下： 如果搜索最大范围为d ，则第一步的搜索中心( q ，c y ) 一( 0 ，o ) ，步长为2 i 慨。j _ 1 ， 这里l 工i 是不小于x 的最小整数，假设计算得到的步长为s ，则对中心点以及在x ， v 轴上距中心点s 的四个点做匹配计算举个例子说明为，如果搜索的中心点为 ( 0 ，o ) ，则第一步搜索的匹配位置为：( 0 ，o ) ，( 一s ，0 ) ，( s ，0 ) ，( o ，一s ) ，( 0 ，s ) ，( 一s ，一s ) ， ( ，s ) ，p ，弗) ，拶，s ) 九个点。 将搜索步长减1 ，假设第一步得到的最佳匹配位置是其余五个位置中的一个 ( n ，6 ) ，则中心位置变为( 口，6 ) ，即( q ，回) 一( 口，6 ) ，跳回第一步进行搜索，直到搜 索步长变为1 。 这时步长为1 ，进一步搜索当前最佳位置周围8 个点，找到最后的最佳匹配点， 这个点的位置矢量就是当前块的运动矢量。 为了形象说明算法的步骤，我们用图2 2 做示范，图例中( 3 ，一3 ) ，( 3 ，一5 ) 分别 是第一步和第二步得到的最佳匹配点，最终得到的最佳匹配点为( 2 ，一6 ) 。 1 0 视频帧间编码技术的研究与实现 7 6 5 4 3 2 101 23456 7 v 5 _ ( 驴 ，j 、 卜 a 弋 旷 舂a 、 黧 i 泽 吲l 沪弋参 卜 险一 、 y 【 ! 广 l_ ( 驴 i i 图2 - 2 三步搜索法实例 三步搜索算法最多只需要做2 5 个位置的匹配计算，相对于全搜索来比，大大 减少了匹配运算的复杂度，而且取数比较规则，也易于硬件实现，所以被许多标 准推荐使用。 2 2 3 精简运算量的快速算法 与启发式搜索算法通过减少搜索位置数的方法不同，精简运算量的快速算法 通过减少每个匹配位置的运算量来加速搜索过程。以1 6 x 1 6 的块为例，全搜索算 法需要计算2 5 6 个象素点的匹配误差，并且每个象素的灰度值是用8 b i t 来表示的， 显然，为了减少运算量，可以通过减少匹配象素点的个数，也可以通过减少每个 象素灰度值的比特数来实现。这类算法包括简单亚抽样、梅花形亚抽样和象素均 值滤波等，结合提前中止技术，可以改变做匹配时匹配象素的顺序来减少最终参 加匹配的象素数，如基于希尔伯特扫描顺序的搜索法和基于维纳竞争策略的搜索 法等。这里我们以基于投影的快速匹配算法为例来介绍。 基于投影的快速块匹配算法在计算匹配误差时，只考虑每列象素在竖直方向 上的投影，减少了匹配运算的点数。具体介绍如下： 定义矿一一为第七帧图象中左上角坐标为o ，y ) 的图象块，大小为 fx ，磷? 一 为对应的( f ，f ) 位置的象素值，那么占b 一在竖直方向上的投影可以表示为： 上毋；缸了且。o f l f( 2 6 ) 钉” 那么在搜索窗口内，有下面的式子成立： b “”“；l e “”一丑o “1 ”+ e 批l “1 “ 伊7 l 第二童帧间视频编解码技术及硬件实现结构 f 加。“”，f ，fc m 1 ； 科1 ”1 2 馕“川”删= 肘一l ； l p ” ( 2 8 ) 从式( 2 7 ) 和式( 2 8 ) 可以看出，搜索窗口相邻参考位置的l 口计算有很大的冗余 度可以去除，从而减少了运算的复杂度。基于投影的可以表示为： 工鲥。似，匆) 4 荟p t b 一曲；“k 慨”毋1 ( 2 。) 即有： 似，毋) 。荟善b 蛐”一骂，“蚺“4 嘶l 2 誓 萋最，i ，j 一薯皿，i l j “b + 咖2 善f 磊最，妇。一荟皿，“h “”咖f 。陋b 一；“坫“”咖1 - 船仞陋，方) ( 2 1 0 ) 从上式可以看出，如果l 函，方) & m i n ，那么必有( 出，妙) m i n 。盛m i n 表示当前搜索到的最小的& 。也就是说通过比较l 翻d 就可 以排除大多数参考块，只要对剩余的少数参考块进行s a d 的比较就可以得到最佳 运动矢量。但在比较伽时，m i n 是得不到的，可以通过简单的线性估计来 得到l d i n i n ，记e 为鲥m i n 的估计值，鼢为 翻眈- a4 脚i n i n ( 2 1 1 ) 工函m i n 为当前最小的工值，若跗龇盛m i i l ，则不可能造成最优化 失真，否则可能造成最优化失真。口为比例扩展因子，口乏1 ，通过调节a 的大小 来改变运算的复杂度，口越大，排除的就越少，计算复杂度就越高。 归纳起来，基于投影的快速块匹配算法的步骤如下： 1 ) 计算所有参考位置的l ( 出，匆) ； 由& 佃l i n 确定鼢； 3 ) 排除所有工l d ( 觑，方卜鲥眈对应的参考位置； 4 ) 计算剩余位置的剐d ( 出，毋) ，得到最佳匹配位置。 有几点需要说明： 幻基于二维投影( 对应块所有象素的累加和) 的算法效果较差； 基于水平方向投影的算法性能不如基于竖直方向投影的算法； 0 基于两个方向投影平均的算法得不到比基于竖直方向投影的算法好的性 能。 视频帧问编码技术的研究与实现 2 2 4 多分辨率估计算法 多分辨率搜索法也称分层搜索法。其主要思想是先得到图象的不同分辨率的 分层表示，然后在逐层由粗到细搜索。我们咀金字塔型搜索为例来介绍。 假设块，的大小为，且一2 4 ，那么可以得到该块的m 层描述，记为 ，”，( o s m s ，1 ) 。，o 只有一个值，即块厂的平均值，厂4 是对，“中的每个2 2 取均值得到的，大小变为其1 “。这样从，“到，o 形成了一个自下而上的金字塔结 构，如图2 3 所示。 圈2 - 3 图像的金字塔表示 金字塔层的生成方法可以描述如下： ，”_ 1 ( 1 ，j ) - ( ，”( 2 j 一1 ，2 j 一1 ) + ，”( 2 i ，2 j 一1 ) + ，“( 2 f 一1 ，2 j ) + ，1 ( 2 f ，2 ，) ) 1 研皇一，”( f ，) - ，( f ，j ) f 2 2 ) 在m 层上的国记为& “，即： 脚5 - 善荟i 4 ( j ， ) 一时( ，_ 1 1 ) i 3 ) 分层搜索算法步骤如下： 1 1 生成当前块和搜索窗口的金字塔表示； 2 1 从第m 层开始搜索，找到该层的最佳匹配矢量； 3 1 以第m 层找到的矢量在第m l 层的位置为中心，搜索范围相对减少，找到 第m 一1 层的最佳矢量，重复至打一1 层： 4 1 在第打层以h l 层的结果为中心做小范围搜索，得到最终运动矢量。 分层搜索法中在每一层的搜索方式可以是全搜索，也可以是启发式搜索法等。 分层搜索法不仅降低了运算量，而且可以防止搜索陷入局部最优点。不难得到： 烈d “函加 ( 2 14 ) 那么如果有& t d “苫酣d m ，则有5 ：4 d 42 翻z ) m ；n ，利用这一性质，我们可以 第二章帧间视频犏解码技术及硬件实现结构 逐渐排除非最佳匹配点，这就是基于分层搜索的快速穷尽搜索法。 2 2 5 基于时空域相关的预测算法 实验中发现很多视频序列的运动矢量分布具有( 0 ，o ) 偏置特性，即很大一部分运 动矢量都为( 0 ，o ) 或在其附近，图2 4 ( a ) 为f o r e m 龃序列运动矢量的分布图。新三步 搜索法和新四步搜索法都利用了这种特性来加快搜索过程。这种特性对所有的视 频序列不总是成立的，对于大运动序列，( 0 ，0 ) 偏置特性不是很突出，图2 一为 f o o t b a l l 序列的运动矢量分布统计图。对于具有不同运动特性的视频序列，最好是 找到一种统一的运动矢量分布特性。 ( a ) 【b ) 图2 4 运动矢量分布统计( a ) f o r e m a n 序列( b ) 劬蚴l 序列 在一个视频帧中，如果几个块属于同一视频对象，那么它们应该具有同样的 运动矢量，所以运动矢量在空间上具有很强的相关性。例如当前宏块的运动矢量 与它的左、上、左上、右上宏块的运动矢量就有很大的相似性。另外，从图2 5 的统计结果可以看出，图2 5 在连续的视频帧中相邻帧同一位置的宏块的运动 矢量也有很强的相关性。在运动估计过程中，我们利用这些相关性来作矢量的预 测往往可以得到较好的搜索性能。这类算法的高效性能，也使其成为视频编码标 准中的推荐算法，我们以典型的p m _ a s l u r c d i c 咖e m o t i o n 、铣t o rf i c l d a d a p t i v e s e a ht e c b 且i q u e ) ，算法为例介绍。 1 4 视频帧间编码技术的研究与实现 ( a )( b ) 图2 - 5 序列运动矢量时空相关特性统计 【a ) f o 阳m a n 序列( b ) f o o t b a 序列 p m 粥t 算法中运用了停止搜索门限技术，咖”口和m r a 6 为停止搜索的门 限值，都为整数。p m 、慢 s t 的具体步骤如下： 1 ) 初始化。设置门限，方法如下：如果是第一行第一列的块，m r 口一5 1 2 ， 魄r 咖一1 0 2 4 ；否则珈w 等于左、上和右上块i d 的最小值，咖咖- 咖r 口+ 2 5 6 ， 并且： 如果咖r 部口 1 0 2 4 ，咖，咖一1 0 2 4 ； 如果腩r b 1 7 9 2 ，砌锄 1 7 9 2 ； 置f o h 脚一o ，以幻- o 。 根据中值规则计算预测矢量：取上一帧对应块，当前帧上和右上的块的运动 矢量m 圮、耐耽、 ，附计算中值得到。如果是边缘块则有以下规则： 如果是第一列，上一帧对应块运动矢量取( 0 ，o ) ； 如果是第一行，预测值取上一帧对应块运动矢量； 如果是最后一列，取右上方块运动矢量为( 0 ，o ) ； 如果舰z 肘n m 纷，置耐幻一1 。 2 ) 计算d 衄| l 把胁m o x | + 阳甜蛔谢叫；如果p r 以匈一1 并且预测运动矢 量等于上一帧对应块运动矢量，置凡w 耐一2 。 3 1 如果d 泖，o 或者m r 6 1 5 3 6 或者p r 耐勖一1 ，选择小钻石搜索方式， 否则选择大钻石搜索方式。 4 1 计算预测中值附近位置的盛值。如果所得运动矢量与前一帧运动矢量相 同并且榭h 蜘d 肌订，m 出，转到1 0 ) 如果胁h 跗d 2 5 6 ，转到1 0 ) 5 1 计算左、上、右上和上一帧对应块的运动矢量和( o 0 ) 矢量对应的跗d 值， 得到肘l n 。 6 1 如果埘h 函s 旃口，转到步骤1 0 ) ，如果所得运动矢量与前一帧运动矢 量相同并且脚n 跗d sp r p 册m ，转到1 0 ) 第二章帧问视频编解码技术及硬件实现结构 7 ) 钻石搜索法进行搜索，如果f 。“n d - 2 只执行一次钻石搜索并转到1 0 1 8 ) 如果是小钻模式，重复搜索直至最佳点为钻石中心并转到1 0 ) 9 ) 如果是大钻模式，重复搜索直至最佳点为钻石中心，转为小钻模式进一步 搜索并转到1 0 ) 1 0 1 砌& 对应位置即为最佳运动矢量。 类似的算法还有很多，p m 1 a s t 算法是一个很典型的例子，这类算法充分利 用了运动矢量的时空相关性和中心偏置特性，运用门限自适应调整技术提前中止 搜索。 2 2 6 基于率失真优化的算法 运动估计使用的m a d 准则从一定意义上来说有其不足之处： “m a d 准则反映了d c t 系数的方差，但是并不能精确反映编码所用的比特 数，因为参与编码的是量化后的d c t 系数； 、没有考虑编码运动矢量所用的比特数； 3 1 、没有考虑编码后的失真大小。 基于率失真优化的搜索法就是在选择运动矢量时，在编码长度和失真之间做 个权衡，这个权衡体现在匹配准则函数上，详述如下： 用豆( 哥) 表示用矢量矿编码当前块时的预测误差函数，例如可以定义为 豆) t ( 脱_ t d f ) ，d c ( f ) ) ，其中 玉( 矿) 为矢量矿对应的平均绝对误差，d c ) 为 平均误差。用b ) 表示编码矢量矿所用的比特数，那么匹配准则函数定义为 g 妒，q ) - 日但9 ) ，q ) + 曰f ) ( 2 1 5 ) 上式中，q 为量化步长。豆和日是这种算法的两个重要参数，豆为误差函数， h 是用来估计编码预测误差所用比特数的经验函数，它实际是速率和失真的联合 估计。考虑到计算复杂度，豆一般选用m a d ，实验表明选用m s e 得不到明显的 更好的结果。 日函数用来估计编码预测误差所用的比特数，理论上得不到严谨的公式，只 能根据实验结果来总结经验公式。把q 固定在不同的值上，改变矿，得到大量的 m a d 和编码d c r 系数所用的码字。为了方便，记m a d 为宇，那么根据实验结果， q 固定时，可以得到以下经验公式： h ( 亭) - c 】亭+ c 2 ( 2 1 6 ) ( 亭) zc l l o g ( 亭+ 1 ) + c 2 ( 2 17 ) 日( 亭) ；c l l o g ( 亭+ 1 ) + c 2 宇+ c 3 ( 2 1 8 ) 日函数和q 也是有关系的，q 值取决于码流控制，当然也可以模拟h ( 亭，q ) 曲 面，这样可能太复杂。q 的值是离散有限的，那么可以把q 看成q 的函数，q 只有 视频帧间编码技术的研究与实现 3 1 个可能的值，那么可以把对应c 存为查找表的形式。 同时考虑速率和失真的优化，我们可以把匹配准则函数写成下面的形式： g ，q ) 一日。嵋( 矿) ，q ) + a h 。怛妒) ，q ) + 口够) ( 2 19 ) 上式中，h 。为速率模型，日。为失真模型，假若二者采用式( 2 1 6 ) 一( 2 1 8 ) 中 同一函数，那么日- 日。+ 加。具有同式( 2 1 6 ) 一( 2 1 8 ) 同样的形式。 基于率失真优化的搜索法就是在式( 2 1 9 ) 准则下找到最优的矢量，a 的选取取 决于率失真曲线，为曲线上工作点斜率的负数。在这类算法中，如何确定日和曰函 数是关键，不同的方法对应了不同的算法。 2 3 全搜索算法的一种v l 剑结构 视频压缩编码在生活中应用面非常广，如视频会议、可视电话等，这类面向 大众的应用要求编解码器的成本非常低，因此随着微电子行业的发展，如何在现 有的v l s i 设计水平上实现实时视频压缩编码受到越来越多的关注。 视频编码的高复杂度为它的实时实现带来了很大的困难，在这些难点之中， 运动估计的实时实现尤为突出。从运动估计的原理可以看出，匹配搜索中有大量 的数据输入输出和算术运算，大量的数据输入输出对存储器的接口提出了较高的 要求，而大量的算术运算带来的额外功耗则必须通过合理的硬件算法来解决，而 这些困难都可以通过一种很好的v l s i 结构来缓解。 在设计运动估计v l s i 构架时，必须考虑以下要素： 1 1 实时性。图像分辨率越高，实时性编码难度越大，所以必须论证采用的方 法能对多高分辨率的图像实时编码。此外，实时性与编码帧率有关，帧率越高， 实时性难度越大； 编码效率。采用的运动估计算法和匹配的精度决定了编码的压缩效率； 3 1 成本。这是任何设计都必须考虑的问题，考虑芯片的成本时，首先要考虑 芯片本身的规模，其次还要考虑外围器件的成本； 钔功耗。功耗问题是芯片设计中的一个重要问题，它与很多因素有关，如工 作频