（通信与信息系统专业论文）基于运动补偿的去隔行系统的研究与fpga设计.pdf

摘要 随着高端电视的快速发展，数字电视技术的研究与应用，传统模拟电视的隔行扫 描方式引起的彩色爬行、画面闪烁和图像快速运动时产生的边缘模糊及锯齿等现象越 来越突出。然而由于经济发展的原因，模拟电视在一定时期内仍将在市场上占有一席 之地。因此模拟电视的隔行扫描到逐行扫描的转换即去隔行是当前视频后处理等电视 产品的重要组成部分。 由于电视信号处理的实时性要求，大多数去隔行技术采用了计算量小、易于硬件 实现的基于非运动补偿的算法。随着半导体技术的发展，大规模集成电路技术的提高， 尤其是a s i c 技术的应用，使得人们开始将基于运动补偿的去隔行算法应用于消费类 的电视产品中。 本文采用基于运动补偿的算法，对去隔行系统及其f p g a 设计作了深入的研究。 该系统包括三个关键模块：运动估计模块、运动补偿模块和缓存器模块。其中运动估 计模块是去隔行系统的设计重点，设计为双向运动估计，采用菱形快速搜索算法，与 目前普遍采用的全搜索算法相比极大的减少了计算量，但增加了控制的复杂度。该模 块主要分为计算和控制两大部分。计算部分为s a d 计算模块，采用累加树和流水线 技术：控制部分根据菱形搜索算法的第三步搜索的特点，对比较模块、s a d 暂存器 等模块做了具体的设计，以提高运动估计模块的计算效率。对于运动补偿模块采用双 向补偿的算法，补偿精度为半像素。根据半像素点的位置将运动补偿计算分为四个状 态，并通过对四个状态计算特点的分析设计了加法器的结构复用，节约了大量资源。 同时基于视频数据处理的需要，设计了四个具有双体存储结构的内部缓存器，由 f p g a 内部的嵌入式阵列块实现。根据运动估计模块和运动补偿模块的计算特点，分 别对缓存器的结构、读写时序和列序号控制进行设计，有效提高了数据的存取效率。 本文对于这三个去隔行系统的关键模块都给出了r t l 级设计和模块的功能仿真，并 在最后一章中给出了去隔行系统的f p g a 设计。 关键词：去隔行；运动补偿：运动估计；双体缓存器；f p g a ：菱形搜索算法 a b s t r a c t w i t ht h eh i g h s p e e dd e v e l o p m e n to fh i 曲一e n dt e l e v i s i o n ，t h er e s e a r c ha n da p p l i c a t i o n o fd i 百t a lt e l e v i s i o nt e c h n i q u e ，t h ef l a w sc a u s e db yi n t e r l a c e ds c a ni nt r a d i t i o n a la n a l o g t e l e v i s i o n ，s u c ha sc o l o r - c r a w l i n g , f l i c k e ra n df a s t - m o v e do b i e c t sb o u n d a r yb l u ra n d z i g z a g ，a r em o r ea n dm o r eo b v i o u s h o w e v e r , b e c a u s eo ft h ee c o n o m i cd e v e l o p m e n t ， a n a l o gt e l e v i s i o nw i l ls t i l lt a k ei t sp l a c ei nt h et v m a r k e td u r i n gal o n gp e r i o d t h e r e f o r e t h ec o n v e r s i o no fi n t e r l a c e ds c a nt o p r o g r e s s i n gs c a n ，w h i c h i s d e i n t e r l a c i n g ，i s a n i m p o r t a n tp a r to f c u r r e n tt e l e v i s i o np r o d u c t i o n ，s u c ha sd i g i t a lv i d e o p o s t p r o c e s s i n g a st h er e a l - t i m er e q u i r eo ft e l e v i s i o ns i g n a lp r o c e s s i n g ，m o s td e i n t e r l a c i n gs y s t e m a d o p tn o n m o t i o nc o m p e n s a t i o n - b a s ea l g o r i t h m s w h i c ha r es m a l ic a l c u l a t i o na c c o u n ta n d e a s yr e a l i z e d n o w a d a y sw i t h t h ed e v e l o p m e n to fs e m i c o n d u c t o r , t h ei m p r o v e m e n to f v l s ia n dt h e a p p l i c a t i o n o fa s i c t e c h n i q u e ，p e o p l e c a n a p p l y t h em o t i o n c o m p e n s a t i o n - b a s ea l g o r i t h m s t oc o n s u m i n gt e l e v i s i o np r o d u c t i o n s t h i sp a p e ra p p l i e st h em o t i o nc o m p e n s a t i o n - b a s e da l g o r i t h mt o d e i n t e r l a c i n gs y s t e m a n dd e e p l yr e s e a r c h e st h ef p g a d e s i g no ft h es y s t e m t h e r e r et h r e ek e ym o d u l e si nt h e s y s t e m ，w h i c ha r em o t i o ne s t i m a t i o nm o d u l e ，m o t i o nc o m p e n s a t i o nm o d u l ea n db u f f e r m o d u l e t h em o t i o ne s t i m a t i o nm o d u l ei st h em o s ti m p o r t a n tp a r to ft h ed e i n t e r l a c i n g s y s t e m ，w h i c hi sd e s i g n e da sb i - d i r e c t i o n a lm o t i o ne s t i m a t i o n i ta p p l i e sd i a m o n ds e a r c h a l g o r i t h m c o m p a r e dw i t hf u us e a r c ha l g o r i t h m i th a sl e s sc a l c u l a t i o na c c o u n ta n dm o r e c o m p l e x c o n t r 0 1 t h e r ea r et w op a r t si nt h em o d u l e ，w h i c ha r ec a l c u l a t i o na n dc o n t r o lp a r t t h ec a l c u l a t i o n p a r t i ss a dc a l c u l a t i o nm o d u l e i t a p p l i e s a d d e r - t r e ea n d p i p e l i n e t e c h n o l o g y a n db a s e do nt h ec h a r a c t e d s t i co ft h et h i r ds e a r c hs t e pi nd i a m o n ds e a r c h a l g o r i t h m ，t h ec o n t r o lp a r tm a k e ss p e c i a ld e s i g n sf o rc o m p a r i s o nm o d u l e ，s a db u f f e r , e t c t o i m p r o v e t h ec a l c u l a t i o n e f f i c i e n c y o fm o t i o ne s t i m a t i o nm o d u l e a st om o t i o n c o m p e n s a t i o n m o d u l e b i d i r e c t i o n a lc o m p e n s a t i o na l g o r i t h mi su s e d t h ep r e c i s i o ni sh a l f p i x e l b a s e do nt h ep o s i t i o no fh a l fp i x e l ，t h e r ea r ef o u rs t a t e s i nm o t i o nc o m p e n s a t i o n c a l c u l a t i o n a t i e ra n a l y z e dt h ec h a r a c t e r i s t i co ff o u rs t a t e sc a l c u l a t i o n ，t h ea d d e r sd i p l e x s t r u c t u r ei sd e s i g n e d ，w h i c hc a ns a v el a r g er e s o u r c e s a n df o rt h er e q u e s to fv i d e od a t a p r o c e s s i n g ，f o u ri n n e rb u f f e r sa r ed e s i g n e d ，w h i c ha r es t r u c t u r e db yd u a lb o d y t h e ya r e r e a l i z e d b ye m b e d d e da r r a yb l o c ki nf p g a a l s ot h e i rs t r u c t u r e s ，w r i t i n ga n dr e a d i n g t i m i n ga n dc o l u m n c o n t r 0 1a r ed e s i g n e db a s e do nt h ec a l c u l a t i o nc h a r a c t e r i s t i e so fm o t i o n e s t i m a t i o na n dm o t i o nc o m p e n s a t i o nm o d u l e ，w h i c hc a ne f f e c t i v e l yi m p r o v et h ed a t a s a c c e s se f f i c i e n c y t h et h r e ek e ym o d u l e sa r ea l lp r e s e n t e da sr t ll e v e ld e s i g na n dm o d u l e f u n c t i o n a ls i m u l a t i o n t h ed e i n t e r l a c i n gs y s t e m sf p o a d e s i g n i si nt h el a s tc h a p t e r k e y w o r d s ：d e i u t e r l a c i n g ；m o t i o nc o m p e n s a t i o n ；m o t i o ne s t i m a t i o n ；d u a l b o d yb u f f e r ； f p g a ；d i a m o n d s e a r c h a l g o r i t h m i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：么坐日期：趋埴：么堑 火连理工人学硕士学位论文 引言 电视机一直是消费类电子产品中最重要、发展最快和最引人注目的产品，从黑 白、彩色到图文电视，电视机经历了一代又一代革新。随着超大规模集成电路、计 算机和通信技术的迅速发展和结合，电视机的功能和视觉效果也在经历一场革命性 的飞跃，从模拟技术到数字处理，从单一的电视播放到多媒体家庭影院，从小尺寸、 大体积到超薄、超大的平面显示，从低分辨率到高清晰度画面等等方面都体现了技 术的进步和人们对高质量电视目益增长的要求【l 】【2 】。 我国的电视机普及率很高，共有3 亿多台电视，2 0 0 4 年在中国市场的销售量排 名居前位的进口彩电中，普通型彩电的销售量仅增长了3 ，而科技含量高的数字 高端电视却增长了5 0 。尽管数字梳状滤波器、亮度和色度动态增强电路等数字新 技术的出现，在一定程度上提高了电视机的图像质量和性能，但是图像的彩色爬行、 画面闪烁和图像快速运动时产生的边缘模糊及锯齿现象并未从根本上得到改善。这 些缺陷的罪魁祸首是模拟电视体制的隔行扫描方式。现行三大主要模拟彩色电视系 统p a l 、n t s c 和s e c a m 均采用这种扫描方式，这种缺陷经大尺寸屏幕放大后就 更加明显【j j 。为改变画面的视觉效果，去隔行技术( d e i n t e r l a c i n g ) 应运而生。 虽然高清晰度电视的性能正在不断提高，普及速度正在加快，但是模拟电视并 不会马上消失，未来若干年内将是由模拟电视向数字电视转换的过渡期。由于我国 各地区经济发展水平不一致，在经济相对落后的地区这个过渡期可能还会比较长。 在这个转型时期，由于需要覆盖所有标准，隔行逐行转换功能对电视产品来说是很 重要的功能，因此去隔行技术的研究有着广阔的前景。 为了解决去隔行的问题，人们已经研究了很多算法并将其应用于实际产品中。 其中最简单的是线性方法，直到上世纪7 0 年代末，这直是应用于电视产品的普 遍方法。从8 0 年代早期开始，有些学者提出了比线性方法性能更好的非线性方法。 接着，针对场景中运动物体的运动补偿的算法被提出来了，这种算法要做到实时性 需要占用大量高速硬件资源，因此当时被认为对于消费类电子来说过于昂贵。随着 超大规模集成电路的发展和数字系统设计手段的提高，在9 0 年代早期出现了基于 运动补偿的面向消费类电子的芯片【4 】【“，这是个重大的突破。 本文设计的去隔行系统采用基于运动补偿的算法，共包括三个关键模块：运动 估计模块、运动补偿模块和缓存器模块。 在运动补偿技术中最重要的部分是运动估计，目前的运动估计器都是采用全搜 基于运动补偿的去隔行系统的a s i c 前端设计 索块匹配算法，这种算法的特点是逻辑简单，可靠性高，但运算量大，占用资源多。 本文的运动估计模块设计为双向运动估计，采用菱形快速搜索算法，可以极大的减 少计算量，但由于快速搜索算法存在反馈判决，因此其控制逻辑相对比较复杂。运 动估计模块分为计算和控制两个部分，其中计算部分为s a d 计算模块，采用累加 树和流水线技术；控制部分包括比较模块、搜索算法模块等，主要根据菱形搜索算 法的第三步搜索特点，将搜索点分为重叠点和未重叠点，对未重叠点计算s a d 值， 对重叠点将其s a d 值暂存，在作s a d 值比较时直接读出，这样设计可以有效的提 高系统的计算效率。 对于运动补偿模块采用双向补偿的算法，补偿精度为半像素，其灰度值采用线 性差值法求解。根据半像素点的位置将运动补偿计算分为四个状态，并通过对四个 状态计算特点的分析设计了加法器的结构复用，节约了大量资源。在运动补偿计算 中由于数据到来的时序不一致，因此需对其作缓冲等齐，以保证运动补偿计算的时 序一致性。 同时基于视频数据处理的需要，设计了四个具有双体存储结构的内部缓存器， 由f p g a 内部的嵌入式阵列块实现。根据运动估计和运动补偿模块的计算特点，分 别对缓存器的结构、读写时序和列序号控制进行设计，有效提高了数据的存取效率。 本文主要研究这三个关键模块的r t l 级结构设计，并给出了各个模块的功能仿 真，最后完成了系统的f p g a 实现。 全文内容共分为五部分： 第一部分介绍了现行去隔行算法，主要包括基于非运动补偿的算法和基于运动 补偿的算法两大类，并对几种算法的作简单比较； 第二部分介绍了去隔行系统的运动估计和运动补偿两个模块的结构设计并给 出了相应的功能仿真，这两个模块是系统的计算模块； 第三部分介绍了两个计算模块对应的缓存器模块的结构设计和并给出了模块 的功能仿真； 第四部分在给出系统时序分配的基础上，根据实际时序分配和硬件条件给出了 去隔行系统的f p g a 实现，包括功能仿真、综合与后端仿真； 最后，对本文的工作及成果进行总结。 2 大连理工大学硕士学位论文 1 概述 1 1 隔行扫描的缺陷 电视图像的每一帧均是由电子束顺序地一行接着一行连续扫描而成，这种扫描 方式称为逐行扫描。要得到稳定的逐行扫描图像，每帧图像必须扫描整数行。举例 来说，一帧图像是连续扫描6 2 5 行组成的，每秒钟共扫描5 0 帧图像，即帧扫描频 率为5 0 帧秒，或写成5 0 h z ，行扫描频率为3 1 2 5 k h z 。 逐行扫描方法使信号的频谱及传送该信号的信道带宽均达到很高的要求。电视 专家把一幅6 2 5 行图像分成两场来扫，第一场称奇数场，只扫描6 2 5 行的奇数行( 依 次扫描1 、3 、5 、行) ，而第二场( 偶数场) 只扫描6 2 5 行的偶数行( 依次扫描2 、4 、 6 行) ，通过两场扫描完成原来一帧图像扫描的行数，这就是隔行扫描方式。对 于每帧图像为6 2 5 行的隔行扫描，每帧图像分两场扫，每一场只扫描了3 1 2 5 行， 而每秒钟只要扫描2 5 帧图像就可以了，故每秒钟共扫描5 0 场( 奇数场与偶数场各 2 5 场) ，即隔行扫描时帧频为2 5 h z 、场频为5 0 h z ，而行扫描频率为1 5 6 2 5 k h z 【7 】。 隔行扫描的原理如图1 1 。 图1 , 1 隔行扫描原理 f i g 1 1t h e o r yo f i n t e r l a c e ds c a n 隔行扫描的行扫描频率为逐行扫描时的一半，因而电视信号的频谱及传送该信 号的信道带宽亦为逐行扫描的一半。这样采用了隔行扫描后，在图像质量下降不多 的情况下，信道利用率提高了一倍。由于信道带宽的减小，使系统及设备的复杂性 与成本也相应减少，这就是为什么世界上早期的电视制式均采用隔行扫描的原因。 但隔行扫描也会带来许多缺点，如会产生行间闪烁效应、出现并行现象及垂直 边沿锯齿化现象等不良效应。传统的隔行扫描有以下缺点【8 i ： ( 1 ) 因为每场只有3 1 2 5 行，在2 9 英寸及以上的大屏幕彩电上，能很明显地看 到粗糙的行条纹光栅； 基于运动补偿的去隔行系统的a s i c 前端设计 ( 2 ) 因为行频比逐行扫描降低一倍，帧频仍为2 5 h z ，眼睛已能感觉到行问闪烁， 这会使眼睛疲劳； ( 3 ) 当移动物体沿水平方向的速度大于一场传送速度时，因隔行扫描使相邻行 在时间上相差一场，那么会降低垂直边缘清晰度； ( 4 ) p a l 信号解码时，色度信号中有逐行倒相的串色成分，在隔行扫描时，会 有缓慢的爬行现象。 隔行扫描的这些缺点在大屏幕显示器中显得尤为突出，而采用逐行扫描则可以 避免这些问题。 1 2 去隔行算法概述 去隔行处理的基本原理是根据图像序列在时间和空间的相关性，产生出空缺位置 处的像素点。通过这种处理，可以最大限度的恢复出逐行扫描图像，改善电视画面的 质量：同时也生成了点阵显示设备可以接受的逐行格式。 去隔行的任务就是将输入以隔行扫描的场为单位，包括奇场和偶场，转换成帧。 这些帧表示与输入相同的图像，但包括所有行的采样。一般的定义输出帧厶( x ，y ) 为 肭朋= 幺潞露2 钏删2 ( 1 1 ) 其中( x ，y ) 为二维空间的位置坐标，n 为场序号，工( x ，y ) 为输入场的像素点灰度值， 兀( z ，y ) 为插补场的像素点灰度值。 去隔行算法主要分为非运动补偿( n o n - m o t i o nc o m p e s a f i o n ) 和运动补偿州o r i o n c o m p e s a t i o n ) p 驮类p 】【1 0 1 。非运动补偿算法是早期比较简单，且硬件实现比较容易的算 法，主要包括线性和非线性两种算法。运动补偿类算法是目前最先进的去隔行算法， 与非运动补偿算法相比，运动补偿算法极大的提高了去隔行运算的准确度，但同时 由于加大了硬件实现的难度，这种算法一直停留在理论研究阶段，直到九十年代中 期随着v l s i 技术的发展和算法的改进，面向普通消费类市场的单芯片运动估计器 的出现，运动补偿类的格式转换算法才开始成为研究的热点。 本文采用运动补偿类算法去隔行。由于许多非运动补偿算法比较简单易于实 现，常将其与运动补偿算法结合起来使用。因此下面分别对非运动补偿算法和运动 补偿算法做简要介绍。 1 3 基于非运动补偿的去隔行算法 基于非运动补偿的去隔行算法分为两种：线性类算法和非线性类算法。这两种算 4 大连理工大学硕士学何论文 法中都包括空间( 场内) 、时间( 场间) 和时空算法。 1 3 1 线性类算法 这是最基本的一类格式变换算法，待插值点由其时一空邻域内的采样点加权求 得，其加权系数插值内核为一事先确定的常数，如式( 1 2 】所示。 - ，j ( x ，y ) = 芝：厶+ ，( x + 后，y + ，) ( 七，l ，坍) ，( t ，n - - ，一1 0 12 ， )( 1 2 ) 式中a ( ，l ，m ) 为插值内核。根据插值内核的形式不同可以得出空问滤波( s p a t i a l f i l t e rs f ) 、时间滤波( t e m p o r a l f i l t e r t f ) 和时空滤波( s p a t i a l t e m p o r a lf i l t e r v t f ) 三种不同的线性滤波算法。 ( 1 ) 空矧滤波s f r a j 滤波利用了待插值点在当前帧场中的空问相关性来获取内插值。其插值内 核为 附，f ，咖z ) 篙 ( 1 3 ) 最简单的空间滤波算法是邻近复制法，内插值将直接由原图像中最接近的点复 制而来。这种算法极易硬件实现，被广泛应用于早期的隔行转逐行电视产品中【1 1 1 。 ( 2 ) 时问滤波t f 时问滤波利用了待插值点在时间轴上的相关性来重构插值帧场，其插值内核为 撇，悱雀篡 4 ， 该类滤波器最早的实现形式为去隔行中的交织( w e a v e ) 技术，其实现原理是通过 奇偶两场内容的直接合并来形成一个逐行扫描帧。 ( 3 ) 时空滤波s t f 时空滤波结合了上述两种滤波算法的特性，利用时间空间三维邻域内的信号相 关性来重构待插信号1 2 心】。由于具有较好的处理品质，此类滤波算法在早期的去隔 行芯片中得到广泛运用，如文献 1 4 中采用了式( 1 5 ) 的插值内核。 ，1 1 1 8 ，8 1 8 ，8 1 8 ，1 1 8( k ，= 一3 ，- 1 ，1 ，3 ) = o ) 矗( ，m ) = 一5 1 8 ，1 0 1 8 ，一5 1 81 ；，= 一2 , 0 ，2 ) x ( 川= 0 )( 1 5 ) 1 0其它 。 线性类格式变换算法利用了视频信号在时问一空间频域内带限这基本假设， 基于运动补偿的去隔行系统的a s i c 前端设计 算法结构简洁，规则易于芯片实现，处理品质比较稳定。但线性滤波器也存在诸多 缺陷，如通带和止带的频率很难选择和所设计的低通滤波器不够理想等。 1 3 2 非线性类算法 线性空间滤波类算法会引入图像混迭，而线性时间滤波对于运动场景会引入运 动模糊。随着对多种算法的特性和由此引起的图像退化现象的深入理解，人们开始 考虑设计能够根据场景内容在不同算法和不同系数间进行自动调整的算法，以综合 不同算法的优势。这样在上世纪8 0 年代后期和9 0 年代早期出现了很多非线性类的自 适应变换算法。 ( 1 ) 运动自适应 运动自适应算法的基本原理是根据场景运动与否在空间( 场内) 算法和时间( 场 问) 算法间切换【i5 1 。其硬件结构为由运动检测器和自适应内插器组成，场景运动与 否通常由图像的帧差求取。待插值点公式为 厶( x ，y ) = c 巩。( x ，y ) + ( 1 一口) j 。( x ，y )( 1 6 ) 其中厶( x ，y ) 为静止图像部分；厶( x ，y ) 为运动图像部分：口为加权系数，由运动检 测模块输出的运动等级设定。 ( 2 ) 边界自适应 其中比较典型的算法为基于边界的行平均算 法( e d g e b a s e d l i n e a v e r a g e e l a ) 16 1 ，其待插值点为 i ( ，：( x 一1 ，y 一1 ) + 六( z + 1 ，y + 1 ) ) 2 i fm i n 似b ，一= 口 ：。( 石，y ) = ( l ，：( x 一1 ，y + 1 ) + 正( 工十1 ，y 1 ) ) 2i f m i n ( a , b ，= b( 1 7 1 ) 【( 五( t 一一1 ) + 五( 工，y + 1 ) ) 2 其它 其中a ，b ，c 分别定义为 口= i l ( x 一1 ，y - 1 ) - f , ( x + l ，y + 1 ) i b = 1 l ( x 一1 ，_ y + 1 ) 一l ( x + l ，y - 1 ) 1( 1 7 2 ) c = f a ( x ，y 一1 ) 一l ( x ，y + 1 ) l 与线性滤波类算法相比，边界自适应滤波器在保留边界信息的同时减少了运算 量( 二维滤波降为维滤波) ，是性价比很高的一类格式变换算法。但作为一种场 内算法，场率变换和隔行信源的混迭效应仍无法解决。 大连理工大学硕士学位论文 ( 3 ) 中值滤波 中值滤波是最常用的图像处理算法之一，隐含了对边界或运动的自适应。在去 隔行处理中常用的3 抽头v t ( v e r t i c a l t e m p o r a l ) 值滤波器是最典型的中值滤波类算 法。其待插值点为 ： 厶( x ，y ) = m e d ( 正( 工，y + 1 ) ，厶( x ，y 一1 ) ，六一。( x ，y ) ) ( 1 8 ) 即输出帧的内插行为当前场的上下点和前一场当前点的中值。 尽管中值滤波存在引起图像细节变形的缺陷，但是它能较好地保留物体边界信 息，且易于硬件实现。 1 4 基于运动补偿的去隔行算法 基于运动补偿的去隔行算法是目前最先进的格式转换算法，其基本原理是通过 运动估 ( m o t i o n e s t i m a t i o nm e ) 找出相邻场最匹配的块，计算出运动矢量，在运动 轨迹上进行插值，图1 2 为其实现方框图。 第n 场 第n + 1 场 第n 帧 图1 2 基于运动补偿的去隔行算法方框图 f i g 1 2d i a g r a mo fd e i n t e r l a c i n ga l g o r i t h mb a s e do nm c 采用运动补偿算法还原的图像能很好的保持原图像的垂直清晰度，但是它要求 运动矢量必须准确可靠，算法复杂度高，硬件资源消耗大，硬件实现复杂度高。 由于运动估计和运动补偿方法的不同，其算法也有多种形式。下面分别对运动 估计和运动补偿的各种算法作简要介绍。 1 4 1 运动估计算法 视频图像在时间轴上有较强的相关性，利用运动估计和运动补偿技术可以有效 地去除图像帧间冗余度。这种技术己广泛应用于视频砸缩的一些国际标准，如 h 2 6 1 、h 2 6 3 、m p e g 一1 和m p e g 2 等。运动估计技术在数字电视的研究中有着重 要意义，而运动估计的范围与准确性是衡量编码器优劣的关键指标。 块匹配法是常用的一种运动估计算法，由于此算法最为简单可靠，易于a s i c 实现，因而在数字图像压缩编码中得到广泛应用。 块匹配算法对图像中物体的运动作了一定的假设和限制，简化了运动分割。其 7 基于运动补偿的去隔行系统的a s i c 前端设计 基本原理是将图像划分成n n 固定大小的方块，然后对每块分别处理。将当前场 的一块在前一场的一个特定区域中搜索，依据某一匹配准则得到最佳匹配块，以这 一最佳匹配块作为当前场方块的预测块，同时将得到的位置矢量作为当前块的运动 矢量。由该算法的描述可以看出，块匹配算法是在块内运动场一致性的假设下实现 的，即假设方块内所有像素均具有相同的运动参数，并且这种运动被看作是刚体平 移。块匹配算法的优点是分割及编码简单，实现开销小；缺点是对比较复杂的场景 和快速运动的场景无法得到良好的预测效果【l ”。图1 3 为块匹配运动估计方框图， 其中箭头所代表的矢量即为该块所对应的运动矢量( m o t i o n v e c t o rm v ) 。 第k 1 场( 参考场) 第k 场( 当前场) 图1 3 块匹配运动估计方框图 f i g 1 3d i a g r a mo f b l o c k - m a t c h i n gm e 1 4 11 块匹配算法中的关键问题 在块匹配算法中有以下几个关键问题： ( 1 ) 匹配准则 在块匹配运动估计过程中，匹配准则的调用是非常频繁的。降低块匹配的匹配 准则的运算复杂度将会使整个估计器的运算速度大大降低。因此匹配准则必须是计 算简单且易于硬件实现的。 常见的有四个匹配准则：平均绝对差( m a d m e a n a b s o l u t e d i f f e r e n c e ) 、均方误 差f m s em e a ns q u a r ee r r o r ) 、绝对差值和( s a ds u mo f a b s o l u t ed i f f e r e n c e ) 以及绝对 方差和( s s es u mo f s q u a r ee r r o r ) 。其定义分别为式( 1 9 1 ) ( 1 9 4 ) t 1 8 l 。 删( d x , 矗) 2 志荟荟川”护 ( 川+ 以 ，+ d y ) i ( 1 - 9 1 ) m s e ( x , y ) ( d x , a y ) 2 志善萎嘛( 川舻肌m 屯y + ，+ d y ) 】2 ( 1 蚴 大连理工人学硕士学位论文 s a d ( d ，d y ) = k 1 + f ，y + ) 一f a x + i + d ，y + j + d y ) l i - o = 0 一】n - 1 s s e 忆，) ( ( ，d ，) = 厶一o + f ，y + ，) 一无( x + f 州，y + j + d ，) 】2 ( 1 9 3 ) f 1 9 4 ) 其中( d ；，d 。) 为所求的运动矢量，( x ，y ) 为当前块的左上角顶点坐标，块大小为 n x n ， 一。与 为第n 一1 和第 场像素点的灰度值。 上述四种匹配准则所给出的运动估值准确度相差不大，但由定义式可以看出它 们的计算量各有不同，其中m a e 和s s e 需要进行平方运算，而m a d 比s a d 多出 了一个求平均项，所以从硬件实现的角度考虑，一般采用运算量比较小的s a d 匹 配准则。 ( 2 ) 块大小n 在块匹配算法中，块的大小受到两个矛盾的约束。块大时，块内各像素作相同 平移运动的假设易被破坏，影响估计的精度；块小时，则易受噪声的影响，估计的 可靠性降低，且运算量增加，所需传输的附加信息也增加了。块大小的选定和实际 监控场景及监控目的有关，基本上块的大小应满足下列要求：每一个块几乎都只具 有单一运动或者没有运动；块不能过小，否则会出现匹配建立在包含相同灰度等级 模式的块上的情况【1 9 】。块大小还与运动速度有关，运动速度快时用大块计算较好， 反之小块较好。 因此，必须恰到好处的选择块的大小，以做到两者兼顾。目前的图像压缩编码 标准，如h 2 6 1 ，m p e g 等，一般以1 6 1 6 或8 8 大小块作为匹配单元，这是一 个已为实践所证明的较好的折衷结果。 f 3 ) 搜索窗大小w 搜索窗大小主要与运动目标的运动速度有关，运动速度大则搜索的范围就大， 反之搜索范围小。一般w 为7 ，即搜索窗为( 2 w + 1 ) ( 2 w + 1 ) = 1 5 1 5 。由于块匹配算 法假设同一块中所有点的运动矢量相同，所以搜索其中任意一点就可以代替搜索所 有的点。 ( 4 ) 门限值死的选取 门限值的设置是为了减少所需搜索的点数，加快运算速度，但同时误差值也会 有所增加。对快速运动序列而言，比较适合大一点的门限值，反之，对缓慢运动的 序列而言，比较适合小一点的门限值。 9 基于运动补偿的去隔行系统的a s l c 前端设计 1 4 1 2 几种块匹配算法 块匹配算法中最传统的算法是全搜索算法( f u l ls e a r c ha l g o r i t h mf s a ) ，其原理 是对整个搜索窗口的每一个点按照匹配准则进行计算并比较，最终得到最佳匹配点 即为该块的运动矢量。由于f s a 是逐点搜索的，因此其计算简单，可靠性高，但计 算量巨大，如果系统处理速度不够，用这种方法很难实现多媒体系统的实时化。近 年来人们致力于研究快速搜索算法，如三步搜索算法( t h r e e s t e ps e a r c ha l g o r i t h m t s s a ) 、菱形搜索算法( d i a m o n ds e a r c ha l g o r i t h md s a ) 和多候选值搜索算法 ( m u l t i c a n d i d a t es e a r c ha l g o r i t h mm c s a ) 等。与全搜索算法相比，快速搜索算法需 根据一定的搜索规则产生每一步的搜索点，并且存在反馈判决，即在每一个搜索后 都要根据一定判决准则决定是否要继续搜索。在以上四个关键问题确定的前提下， 可以得到快速搜索算法的流程图，如图1 4 所示。 产生当前步搜索点，即运动矢量的多个候选值 m v c ( m o t i o nv e c t o rc a n d i d a t e s ) 计算各个m v c 对应的s a d 值 比较各个s a d 值 得到当前步的最小s a d 值m i n m i n l d s p ( a ) c a s e l ：e d g ep o i n t l d s p l d s p 1f ii l上 tt li tt 1i il ii il ( b ) 类型2 ：拐角点l d s p l d s p ( b ) c a s e 2 ：c o m e rp o i n t l d s p - l d s p ii 11 il 上工 i 【 ir ti it ii li ( c ) 类型3 ：中心点l d s p - s d s p ( c ) c a s e 3 ：c e n t e rp o i n tl d s p - s d s p 图2 2d s a 搜索中心的三种类型 f i g 2 2t h r e e c a s e so f s e a r c hc e n t e rp o i n ti nd s a ( 2 ) d s a 性能分析 对于m v 在3 3 范围内的小运动块，d s a 最小搜索点数是1 3 点，即需要搜索 两步，而对该区域进行全搜索也只需搜索9 点，因此d s a 不适合对小运动块的搜 索。d s a 和f s a 对不同的m v 范围的搜索点数对比见表2 1 。 表2 1 d s a 和f s a 对不同的m v 范围搜索的对比 t a b 2 1c o m p a r i s o no f d s aa n df s ai nm v r a n g e 基于运动补偿的去隔行系统的a s i c 前端设计 在表2 1 中需注意以下三点： m v 范围取奇数是因为搜索窗关于零点对称的关系； d s a 算法的第三步搜索中心有边缘点和拐角点两种类型，对应的搜索点数分 别是3 个和5 个，表中计算的是最小搜索点数，因此只考虑搜索中心的类型为边缘 点的情况； d s a 的搜索点数出现两种情况是由于门限值的存在，如果最优点的s a d 值 小于门限值，则第三步搜索就是该块搜索过程的最后一步，反之则还需要进行最后 一步搜索，这样搜索点数就比之前多出4 个。 以m v 范围取5 5 为例，其搜索过程如图2 3 所示。 l l i 忧 王h - ， z4 1 34 。z12 143 2 11 1z z 1 2 ： - 8- 6- 4- 2024o8 图2 3 运动矢量范围5 5 的d s a 搜索过程 f i g 2 3 d s as e a r c h o f 5 5 m v 由于每一步得到的最佳匹配点都是一个，而不是多个，因此该算法可能会陷入 局部最小值。运动矢量范围越大，陷入局部最小值的可能性就越大。这一点从表2 1 中可以清楚的看出来，d s a 与f s a 的搜索点数比率越大，说明d s a 搜索的范围越 小，搜索的方向就越偏向某个方向，这样越会出现局部最小值问题。当搜索点数比 率小于o 2 0 时说明d s a 的搜索范围过于小，出现局部最小值问题的概率较大，这 时可以采用多候选值的搜索算法如m c s a 来进行搜索。 通过以上对d s a 算法的性能分析，可以得出d s a 比较适合运动矢量范围大于 3 3 而小于等于1 1 x 1 1 的情况，也就是运动矢量绝对值i m 矿l ( 1 ，5 。 2 1 2 运动估计模块总体设计 文中的运动估计设计为双向运动估计，采用的匹配块大小为8 8 ，搜索范围为 - 7 ，7 ，为计算方便设计搜索窗大小为1 6 x1 6 ，匹配准则采用绝对差值和s a d ( s u m o f a b s o l u t ed i f f e r e n e e ) ，其定义式为： 大连理工人学硕士学位论文 77 s a d ( 。) ( d r ，咖) = 阮+ 。( p + 幻+ ，) 一六一，( p + f + 出，g + ，+ 砂) l ( 2 1 ) i = 0 j = o 其中( p ，q ) 为当前块左上角顶点坐标：( d r ，方) 为当前块在搜索窗内的当前运动矢量 坐标； + 。和九一，分别表示第k + 1 场和第k 一1 场对应像素点的灰度值，用8 b i t 表示； f 和，分别表示8 8 块的行序号和列序号，取值范围是 0 ，7 】。 由运动估计算法的原理可以看出，在块匹配过程中，不管采用什么样的搜索方 式，运动估计的计算任务主要集中于像素块的s a d 的累加求和以及对所得的累加 和进行比较从而得到m v 两个方面。所以在运动估计器设计中，s a d 计算模块和比 较器是其主要组成部分，同时根据d s a 快速搜索算法的特点设计了s a d 暂存器及 其控制器模块，其总体框图如图2 4 所示。可以将其分为计算和控制两个部分，其 中计算部分为s a d 计算模块，其余模块都属于控制部分。 e l k s t a r t n e x tb l o c k m v ：l 鬻h 搜搿h 暂存器 m v c 一 h 产生器r _ _ 1模块r _ 。l j l 内部 s a d 暂存器 缓存器 及其控制器 及其 vj l1 r 控制器 一 。，。i i s a d l 。 爿7 r _ 计鼻礞块教榍 图2 4 运动估计器方框图 f i g 2 4d i a g r a m f o rm o t i o ne s t i m a t o r 2 1 3s a d 计算模块 计算一个搜索点的s a d 值需要读入的数据共有6 4 2 8 = 1 0 2 4 b i t ，为降低对 硬件i o 口数目的要求，将s a d 运算分为2 个部分，即将式( 2 1 ) 改为： 7 剐d 【。) ( d x ，a y ) = s a o f ( d r ，咖) 伊( 2 , 2 ) 翩。) ( d r ，咖) = 阮+ 。( p + f ，q + j ) - f k l ( p + f + 出，g + ，+ 咖) l f = o 这样每个时钟周期需输入两场对应行的像素点灰度值，所以s a d 计算模块的 输入数据为2 8x 8 b