（信号与信息处理专业论文）基于dct域的视频图像编码算法研究.pdf

摘要 由于视频图像在时间上和空间上都有很大的冗余量，所以必须对视频图像进行编码压 缩，以满足在存储和传输过程中的需要。所以说视频编码压缩的意义是：消除视频图像时 间上和空间上的冗余量。 当前网络和数字化时代的飞速发展，使得对视频图像的处理要求也越来越高。追求高 压缩比、实时传输、高传输效率是视频技术发展的方向。这几年来针对图像处理已经取得 了很大的发展，特别是在视频图像编码压缩算法领域，提出了快速变换算法、智能量化算 法、自适应编码扫描算法、快速m e 和快速m c 算法等等，这些算法都在一定程度上提高了 视频图像的计算复杂度、压缩效率、图像质量等性能标准。 本文分析在分析当前视频编码系统存在问题的基础上，结合相关知识，提出了一种在 d c t 域中进行运动估计的视频图像编码算法。该算法的特点是：在减少编码系统中回路中 模块数的基础上，能够在d c t 域中进行帧间运动估计有效地搜索到运动矢量。 通过理论分析，我们发现改进的算法能够改善编码系统中存在的问题，该算法能够减 少反馈回路中的模块数，同时能够在空间域中实现计算相对简单运动估计算法。通过实验 仿真，给出改进算法的结果，通过结果来分析改进算法的优缺点、适用的环境以及在未来 发展中的潜力。 关键词：运动估计，运动补偿，运动矢量，块匹配准则，伪相位，嵌入式零树小 波 a b s t r a c t f o rt h ev i d e op i c t u r e sh a v em o r er e d u n d a n c yo nt h et e m p o r a ld o m a i na n ds p e c i a ld o m a i n w e m u s tc o m p r e s st h ev i d e op i c t u r e st h r o u g ht h ev i d e oc o d i n gs y s t e m o nt h eo t h e rw o r dt h ep u r p o s e o f t h ev i d e oc o d i n gs y s t e mi st oe l i m i n a t et h et e m p o r a la n ds p e c i a lr e d u n d a n c y c u r r e n t l y , t h ed e m a n df o rp r o g r e s s i n gt h ev i d e op i c t u r e i so nt h eu p a n d u p a n dt h ea i mo f v i d e ot e c h n i q u ei st op u r s u eh i g hc o m p r e s s i o nr a t i o ，r e a l t i m et r a n s m i s s i o n ，h i 【g ht r a n s m i s s i o n e f f i c i e n c ya n ds oo n f o rs e v e r a ly e a r s ，w eh a v eo b t a i n e dl a r g ei m p r o v e m e n to nt h et e c h n i q u eo ft h e p r o g r e s s i n gt h ev i d e op i c t u r e s ，e s p e c i a l l yi n t h ev i d e oc o d i n gc o m p r e s s i o na l g o r i t h mf i e l d w e p r o p o s e dt h ef a s tt r a n s f o r m a t i o na l g o r i t h m ，a p t i t u d eq u a n t i t ya l g o r i t h m ，s e l f - a d a p tc o d i n ga l g o r i t h m ， f a s tm ea n dm ca l g o r i t h m a l lo ft h ea l g o r i t h mc a ni m p r o v et h ep e r f o r m a n c eo ft h ev i d e oc o d i n g s y s t e ma tac e r t a i ne x t e n t t h i sp a p e rp r o p o s e da ni m p r o v e dv i d e oc o d i n gs y s t e mo nt h eb a s i so fa n a l y z i n gt h et r a d i t i o n a l c o d i n gs y s t e m s c o m b i n i n g t h ec o r r e l a t i o nk n o w l e d g e ，w em o v et h em o t i o nv e c t o ro f t r a n s f o r m a t i o nc o e f f i c i e n t so nt h ed c td o m a i n t h ec h a r a c t e r i s t i c so ft h ep r o p o s e da l g o r i t h ma r et o r e d u c et h en u m b e ro ft h el o o po ft h ec o d i n gs y s t e ma n dg e tt h ee f f e c t i v em o t i o nv e c t o ro nd c t d o m a i n t h ei m p r o v e dc o d i n gs y s t e mc a nr e f o r mt h ep r o b l e mt h a tt h e r ea r et o om u c hm o d u l e si nt h e l o o po ft h et r a d i t i o n a lc o d i n gs y s t e m a n dt h ei m p r o v e dc o d i n gs y s t e mi n t r o d u c e san o v e lm e a l g o r i t h mb a s e d o nd c td o m a i n t h er e s u l to fs i m u l a t i o ni n d i c a t e st h a tt h en o v e lm ea l g o r i t h mc a n m o v et h em o t i o nv e c t o ro f t r a n s f o r mc o e f f i c i e n t s a n dt h ea l g o r i t h mh a ss i m p l e rc o m p l e x i t y k e y w o r d s ：m o t i o ne m i m a t i o n ，m o t i o nc o m p e n s a t e ，m o t i o nv e c t o r ，b l o c km a t c h i n gr u l e p s e u d o p h a s e ，e z w 南京邮电大学 硕士学位论文摘要 学辩、专韭：工学信号与绩怠处理 研究方向： 现代通信中智能信号处理 终 喾：塑竖缎研究生邹庆揆撵导教熙壑蕉蹇 题目：基于d c t 域的视频图像编码算法研究 英文题霹：m o t i o ne s t i m a t i o na l g o r i t h ms t u d yi nd c td o m a i ni n t h ev i d e oc o m p r e s s 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 m o t i o nc o m p e n s a t e m o t i o nv e c t o r b l o c km a t c h i n gn i l e p s e u d o p h a s e e z w 南京邮电大学学位论文独创性声鞠 本人声明所呈交学位论文是我个人在导蟋指导下进行的研究 王箨及取得酶磷究戏聚。尽我所翔，除了文；l ；祷舅l l 翔以标注稀致谢的 地方外，论文巾不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京都电大学或其它教育机构的学位或证书丽使用过的材 料。与我一岗工佟购嗣志对本研究所做灼惩露贡献均已在论文；扣 乍了 明确的说明并表示了瀣意。 研究生签名 盔纛攫n 期：坐一 南京邮电大学学位论文使用授权声瞬 南京都电大学、中国辑掌技术情息研究所、阑家图书馆有权保留 本人所送交学位论文的复印件翻电子文桄，可默采用影印、缀姆或其 他复制手段 采存论文。本人电子文档的肉容萃羁纸质论文韵内容楣一 致。除在保密期内的保密论文外，允许论文被杰阅和借阅，可以公布 包括聱j 瑟) 论文的全部或部分内容。论文的公布( 包括刊髓) 授税 南京邮电大学研究生郝办邂。 研究生签名：囊辇萎接露簿签名：垄囊壶爨期：苎! ! ! ：兰： 南球邮电人学碳七研究生举位论文 绪论 第一章绪论 1 1 视频编码压缩系统的发展状况 当前，网络和数字化时代的飞速发展，使得对视频图像多媒体的处理要求也越来越高。 追求离压缩比、实时传输、赢传输效率是视频技术发展的方恳。这几年来针对图像处理已经 取得了很大的发展，特别愁在视频闵像编码压缩算法领域，提出了快速变换簿法、镏能量化 冀法、叁适痰编码翔接算法、快速骓e 襄快速淞葵法等等，这建算法郄奁一定程度上提裹了援 频阁像的计算复杂度、压缩效率、图像质量等性能标准。 基蔻，掰舂豹援攘编磷疆鳕算法是在空润域实现瀵豫醚阗冗余鬃翡，越魏在这个嫠疆土 改进的算法都是采用相同的处理结构框架，只是在实现手段。t 有所麓异。所以说改进的总体 效鬃不大，一簸都怒在特殊癍强下豹某个方箍鼹改邋。密予这耱萋予窆漓域的视频编码压缩 技术出现较早，而熙技术相对成熟，所以得到广泛的应用。 随着辩数字褫频压缩耩来来税频通信领域的发糕，这种基于空阍域的视频编码撬缩系统 越来越不能满足需要，所以目前对视频编码压缩系统的改进算法已缀成为热门课题m p e g ， h 2 6 x 等专家组织也在做这方面的研究，提出了基予变换域的视频编码系统，希望改进整个编 码系统，以满足未来发展的嚣要。 1 2 运动储计在视频编码中的地位及研究状况 运动 鑫计模块在编强系统中起簧决定镶豹俸爰，一黢缡褥系绞串运动髅诗模浚掰占嚣簦 量大约为8 0 。如果能够襁编码系统中设计出计算嫩较少的运动估计算法，那么这个编码系 统载会有蘸好熬注麓；稠藏翔采德计算法魄较复杂、计算羹氇很大，那么慕瘸这释稳诗算法 的编码系统性能就不会很好。如何设计运动估计算法是改进编码系统最关键的问题，运动做 诗簿法的瞧能体现熬个编码系统的性能。 正是由于上述原因，对编码系统的改进綦本上就是对运动估计算法的改进。改进的运动 估计算法有很多，对这些算法的研究主要燕从初始搜索位鬣的选择、搜索窗的选择、匹配准 则、搜索燕嚎这几个方露寒考虑蛇。出现了三步搜索、薪三步搜索、四步搜索、钻石搜索等 算法，这些算法都商各自的性能特点。但遐由于这贱运动估计算法都是在空间域进行的，除 了少数足季孛改进豹舞法诗舅量比较少终，其它的嚣法诗箕鬟蠼差不大，因戴对整个编码系统 鱼史! ! ! ! ! 里查堂黧主塑塞兰鲎垡丝苎 堕垦 劳浚膏太大懿影噙。 所以说，设计性能优良的运动估计算法是目前编码系统研究的黧点问题。 i 。3 本文提出的基于交换域的视频编码压缩系统 在分析空间域视频编码压缩系统的基础上，提出了基予变换域的视频编码算法。这种基 于变换域的 ! ! i 频编粥系统李器思想怒：将传统编码系统的d c t 模块提出反馈阐路，在变换域中 设计算法进行有效的运动饿计。该算法实际上是改变编码系统中功e 模块熬毒届，缝合变换 域的频率特性和伪相位技术，设计算法实现在变换域中进行运动估计，准确提取运动矢量。 通过理论分枣厅发瑗；该雾法能够减少编秘系绞爱镶回踺审载模蛟数，降低诗雾复杂度、 提离编码效率的同时不会降低图像的质量。通过实验仿真发现：该算法能够通过运动估计有 效稳鬟取逸凌矢量，两盈晕瑟基于空鬻域弱算法一样缝够提取1 2 像素经置运动矢釜，甚至更为 精确的运动矢量的提取。 1 4 本文结构 本文主要分为蠢个部分，第一搴绻论，第二章传统视频编码系绫结构分毒斤、第三章基予 空间域的m e ，第四章本文算法结构分析和基于d c t 域豹m e 、第溉章利用伪相位技术提取 运动矢量实验仿真。 塑曼业生查堂堡塑兰兰垫丝苎 笪丝 并没有太大的影响。 所以说，设计性能优良的运动估计算法是目前编码系统研究的重点问题。 1 3 本文提出的基于变换域的视频编码压缩系统 在分析空间域视频编码压缩系统的基础上，提出了基于交换域的视频编码算法。这种基 于变换域的视频编码系统主要思想是：将传统编码系统的d c t 模块提出反馈回路，在变换域中 设计算法进行有效的运动估计。该算法实际上是改变编码系统中功能模块的布局，结合变换 域的频率特性和伪相位技术，设计算法实现在变换域中进行运动估计，准确提取运动矢量。 通过理论分析发现；该算法能够减少编码系统反馈回路中的模块数、降低计算复杂度， 提高编码效率的同时不会降低图像的质量。通过实验仿真发现：该算法能够通过运动估计有 效地提取运动矢量，而且和摹于空间域的算法样能够提取1 2 像素位置运动矢量，甚至更为 精确的运动矢量的提取。 l4 本文结构 本文主要分为五个部分，第一章绪论、第二章传统视频编码系统结构分析、第二章基于 空间域的m e 、第四章本文算法结构分析和基于d c t 域的m e ，第五章利用伪相位技术提取 运动矢量实验仿真。 运动矢量实验仿真。 堕皇! ! ! ! ! 里查望堡主婴塞竺兰丝堡兰 堡竺塑塑塑型墨竺竺丝坌堑 第二章传统视频编码系统结构分析 2 1 基本原理 如下图l 所示，i n p u t 输入可以是满足m p e g x 、h 2 6 x 标准的分辨率图像矩阵，也可以是i 、 u 、v 图像矩阵。在这里为了便于说明算法结构问题，以6 4 * 6 4 的灰度值图像矩阵作为i n p u t 输 入，接下来说明的算法结构的功能。 当i n p u t 输入为头帧( i 帧) ，i n p u t 矩阵经过d c t 模块变成d c t 系数矩阵，然后再经过q 模块量化，就将d c t 系数矩阵变成量化系数矩阵，接着就是编码模块e z w ，将量化后的变换系 数编码输出至l j b u f f e r ，最后由b u f f e r 输出的就是码流，这就完成了第一帧信号的编码，以上 操作就是消除图像帧内的冗余量的流程。由于相邻两帧图像的相关度很高，即为时间上的兀 余度很高，因此采用了运动估计的方法来消除时间上的冗余量的。当对下帧信号压缩时， 我们用第一帧信号作为参考帧，采用运动估计和补偿技术实现消除冗余量。具体操作是：在 第一帧信号量化输出到编码端时，对量化系数矩阵进行q 、i d c t 将它变为原来的输入帧作 为下一帧的参考帧，然后将参考帧与后一帧信号在m e 模块进行运动估计( 如何估计在文章的 后面将仔细阐述) ，两帧信号的估计得到运动矢量，估计出来的运动矢量经过算术编码模块 输出至l j b u f f e r ；然后将估计出的矢量与参考信号经过运动补偿模块，在参考帧的基础上根据 运动矢量来进行运动补偿，补偿出该帧信号，然后再与输入帧进行差值比较，得到差值帧( 由 于估计、补偿的不精确性，肯定会有误差产生) ；再将差值帧信号经过d c t 模块、q 模块、e z w 编码模块输出至l j b u f f e r ，在b u f f e r 中与运动矢量组成了这帧信号的码流，这一系列的处理过 程旨在消除相邻帧时间上的冗余量。同样和对第一帧处理的方法类似，对第二帧差值帧量化 后的信号经过q 、i d c t 模块，再与补偿出来的帧信号进行相加作为后一帧的参考帧，再次 经过m e ，m c 等模块处理，产生码流输出，从而达到连续帧编码的目的。 从图中可以看到：运动矢量部分的编码采用熵编码( e n t r o p yc o d i n g ) 方式，在我们这 里采用的是算术编码方式，头帧信号和差值帧信号采用的是e z w 编码方式，两部分码流的结合 是在b u f f e r 中，这就是传统的编码算法系统流程。 南京邮电学珂i 士研究生学位论文 传统视婀锺编码系统端构舒析 图1 2 。2 存在闯题 从图( 1 ) 中我们可以发现，传统的编码系统反馈回路中存在七个模块，这七个会导致下 列瓣惩； ( 1 ) 2 ) 反馈回路模块的增加导致时间延。 反缓强路模块静增掇导蘩系绫豹复杂，轻蠖箨豹要求都缓毫，露虽镬褥系绞 功耗增加。 3 )褚诗是在空阀域中遂行的，蕊配辩几乎好霹掰有像素都要计箨，困魏计篓薰 相对来说较大。 所以说在未来数字视频雁缩和视频通信领域中，对实对憔、高成嚣、离派缩眈、商效经、 微型性、移动性等要求很高的情况下，这种传统的编码算法就不能够很好的满足。 南京邮电丈学硕士研究生学位论文 基了= 宅间域的m e 第三巍基于空间域的m e 在阐述本文提出豹基于d c t 域的运动话计( m e ) 前，有必要对予糕子空间域的算法熟 基本思想和技术要素进行分析。撼于空间域的运动估计算法基本原理是：在给定的匹酉己准则 下，在特定的搜索窗内，通过一愆的搜索策略，在参考帧中搜索宏块可能出现的位置，得到 运动矢量。 本耄分麓疑运动售诗篓法豹裙始援索整爱貔选耩、搜索密载选择、嚣酝准翳、攘索繁戆 等方面来阐述。 3 1 空间域胍的基本思想 如图( 4 ) 所示，空间域m e 旗本思想就是：将图像帧分成巨不重叠的宏块，井假设宏块内的 艨有像素其鸯褪同豹整移董( 霹激镁竣宏涣内爨毒像素豹运动是一致貔) ，然瑟建当蘸赣熬 每一个宏浃巍参考顿中搜索珏粼块，即在给定豹搜索鬻内根据特定的匹醚准则搜索廷配( 如 图4 ( b ) 所示) ，找到与当前宏块最相似的块，作为暇配块，再由匹配块与当前块的相对位 置计算出来的位移即为当前块的避动矢量( m v ) 。通谶对当前帧的每个宏块都进行匹配搜索， 估计运动矢爨，扶两达到了对当裁帧的运动估计的目的。 在运麓 纛计中，宏块大小f m n 选箨一簸为1 6 l s ，或者隽8 8 。但是热杀宏块选秀8 8 的话，虽然最后恢复的图像质爨会有所改善，但怒运动估计算法总的计算璧会有所增加。 一般来说宏块大小的选择要根据盛际图像压缩编码的需要来确定，即：针附不同要求、不同 场合的图像，选择合适的宏块大小，以达到实际的要求。 匹配竣攘素范围魏确定是鬏攥嚣豫簇中蘩终豹愆动程度来设定戆。当宏缓大小走f m n 时，遥配块的搜索范围为( 村+ 2 威) ( + 2 痧) ，其中出为水平最大位移多乏黧、d y 为垂直最大 位移矢量。当得知图像帧中物体运动较剧烈时，要使得搜索的匹配块更加准确，就必须设定 较大的搜索窗；但是如果图像帧中物体运动比较平缓时，就可以将搜索窗缩小，没有必要设 定大的援索露，设定大豹搜索鬻瓣予疰配块来说除了会增加计算量，没露任簿意义。 可鞋辩遒：基于空间壤的运溯估计算法中麴宏块大小的选择和援豢密大小的选择，妻根 据实际图像的内容和实际需求采确定。这是运动估计中最基本的问题，也掇每一种估计算法 所必须考虑的问题。 塑壅蹩垒查鲎! 堕= 兰璧塞笺篓燕笙塞 燕王窒堡蹩堕翌曼 在匹醚块的搜索过程孛，还褥摄摄匹配准裂来确定簸佳隧配块。裳眉翡坟筵配缓赋有： s a d ( 绝对误差和) 、m s e ( 均方误差) 、c c f ( 瓦相关函数) 、s s a d ( - 7 ：采样绝对误越和) 等。 这塑强配猴则的目的就是使得待搜索的块与隧配块最相似，或者以特搜索块为最佳储计，遮 藏怒说待黩配块与匿配块之淘酌麓值激小。在视频编码艇缩算法研究中，我们发现估计算法 中疆配准则戆选择对惩诗效聚舂一定影穗，褥霹整个运渤绩诗模块豹诗筹慧彩璃不大。采溺 不同的匹酉已准则只对擐佳匹配块衡一定影响，但对系统复杂发没有太大影响。因此我们在碳 究比较不同算法系统复杂度、计算量方面的问题时，一般都采用s a d 准则进行搜索匹酗，这是 由予该准剃篱萃、萄壤辩，僵予编磷髯法毙较。 3 。2 挺蔚运溯估计效率静凡个技术阏题 运动然诗舅法懿散率芝要体蠛在圈豫矮爨、篷缭鹦搴帮羧琵速瘦这兰令方覆。获褥较离 视频图像缀璧是运动鼹终的目的。不错算法如何简单、如俺快速有效，萋达不到所期塑的图 像斌量效粜( 遽里指的是主观壤擞，人眼视觉效果) ，遮融算法没露价值。同对如果某种冀 法在实际搽作i 臻程中觅法实现，不膂它能达到多好的图像质擞，这种算法瞧怒不实际的。因 越我翻戆冀法磷究追求的警探楚在窝像屡璧缳证的簿携下使褥算法籍莘、准确、快速有效， 归纳如下： ( 1 ) 运动估计的简帮性：估计搏法越简单，实隧使用的可能越霄可能，对系统 要求越低。 ( 2 ) 运动嵇计的准确魅：运动 舂诗鹣越准确，补偿酌残差就越小，那么残差僖 号的编码所露的位数就越少，比特率越小，传输效率裁越糍。 ( 3 )运幼估计的快速性：主要是指搜索算法的选择，匹配块搜索的速度趟快， 视频压缩系统就越能满足实时谜的要求。 强簿徽割满足上述的三个方舔猩? 我们分掰鼠枥始援索点豹遥辑、毪淝准粼、运动估计 搜索策略三个方瑟寒耀述的。 3 。2 栩始搜索煮的选择 在进行匹配搜索肄雩，起步搜索般都是逸择参考帧的原始位置中心作为搜索点的起始能 置。这种搜索楣对而富这种方法比较简单，但是该算法狂搜索匹配时很容易陷入局部凝优点， 静攘索豹鼹琵块并不跫全嚣最撬杰。赞靖这静溥撬，我们采臻选择预涮耪始接索点的方法， m 京邮电大学硕士研究生学位论文 基f 窄】域的m e 利用相邻块在时间和空间上的相关性对初始搜索点进行预测，将预测点作为搜索起点。具体 地说有以下两种策略： ( 4 )基于s a d ( t h es u mo fa b s o l u t ed i f f e r e n c e s ) 值的搜索起点算法。分别计 算当前块与其相邻块运动矢量为运动矢量的s a d ，并取最小的s a d 的块的运动 矢量来预测确定搜索起点。 ( 5 ) 利用相邻块的运动矢量来预测当前快的搜索起点。这种方法有很多，基本思 想就是利用当前块相邻块的运动矢量的权值来预测当前块的运动矢量。例如 在h 2 6 3 中所采用的预测方法就是采用这一原理的，其中m v 为当前块运动矢 量，m v i 、m v 2 、m v 3 分别为当前块相邻块运动矢量，m y = m e d i a n ( m y i + m v 2 + m v 3 ) ， 我们把这种方法叫做中值法。 3 2 2 块匹配准则 在下列块匹配准则中m n 为宏块的大小，西( m ，n ) 为的第k 帧( m ，一) 处的像素值，( f ，j ) 为对应的相对位置运动矢量。 - i ni ( 1 ) s a d ：定义如下：s a d ( i ，_ ，) = z 2 1 b tm ，h ) 一b t 一，( 所+ f ，”+ ，) i m ；on ；o 当s a d ( i ，) 到达最小时，表示两个块达到最佳匹配。 ( 2 ) 慨：定义如下：m s e ( “) = 击m 荟- i 善n - i 陬m ) 地一，( 删，州) 2 当m s e ( i ，) 到达最小时，表示两个块达到最佳匹配。 m - i 一l 厩( 脚，n ) 既一- ( m + f ，n + j ) ( 3 )c c f ：定义如下： c 口( f ，) 2 正丙幽1 呵磊百f i 威( m ) il b 2 , - , m + i ，n + j ) l l m - on - ojl m = o ；t - - o j 当c c f ( i ，) 达到最大时说明两个块最相关，表示两个块到达最佳匹配。 ( 4 ) s s a d ：定义如下：s s a d ( i ，j ) = i 成( m ，”) 一b t t ( + f ，h + j ) l p ( m - i n - i ， ) 盯 m = o 月，o 塑璺型堡查鲎堕生堕塞点璺照堡兰 蒌主塞些攫塑竖曼 其蝴删。胪嚣黼 该穗触与s a d - - 样到达最小时，表示鼹个块达到最健匙酲。 由于采样的特性，予采样匹醚准则能俘有效降低计算的复杂废，从公式中得 到：子采榉题配猴则的诗舞羹仅为s a d 准则的秘分之一，这一点是缀多冀法毽 得考虑使用的重要因素。 注意裂擞然器准则量卡冀方式鸯黢不羼，诗算鬟蠢瑟有一是熬麓髯，但逐遥实验谖疆选择 不同准则避弦搜索匹配对运虢估计匹糕块灼搜索速度憋影嚷并不燕缓大，因数一般我髓采瘸 沈较蔫攀匏s 矗0 雩# 为我稻瓣块疆配难晷 j 。 3 2 。3 鼹懿块越搜索算滚 藏藤我 f j 已经谈到了块壁曼配啦剩豹选溪霹搜索避凌售诗瞧配块豹影髓菸不是缀大，采瘸 俺秘蠢效的搜索算法攘略才照关键。如何在绘定的搜索塞内按特定准则( 如s a d 准剿) 搜索烈 最佳匹配浃( 糖礁接索) ，鬻显搜索溪酲浃懿速炭较快是我们遥求的疆标。一般稻富疆索密 f 掰+ 2 a ) o v 2 矽) 麴大小怒峦蠲像瓣本身瘸容凌定豹。警胬像运动跑较捌烈对，为精确援 索鲢配块，我们就必须设定较大的搜索窗；威之，例如视频会议、远景物体的摄像等，图像 运动不利烈辩，可以设定较小的攘索留。当设定较大寓的辩，会增加计算爨，对搜索效果无 明显改善。所以宏块的大小、搜索窗大小的选择是根据具体的图像来确定的。但外在条件允 许的情况下，要尽可能扩大援索窑，可能使用小的宏块。缀蠲显对网视频麓像运动健计旺 配块搜索来说搜索窗越大，搜索的匹配块就越匹配、朦续处理的压缡效果衾越好；但是计算 爨也裁越大，搜索速度越蠛。搜用熬睡配宏敦越小，黼像分割疑越瀵糍，逐动售诗翡越难确， 恢复的图像腹壁就越小，但是计算蹙戟会很大，压赡蠲效率就会降低。 辍踅宏块丈小、搜索密大枣熬选择，辗攒其体静灏像浅容帮对视频雷像蒺耋瀚簧求采确 定的。在 重论蔷秘舞法的性黢分瓣时，巷是程摆翳蘩终下来处理的，捷褥不阉援豢弊法嚣对 澍祥的图像内容、阐样的蕊畿要求。所戳说按下采对各种控索算法的分析讨论，怒在同样宏 块大小、溺样谈索窗大小、接特定的浚疆酝准刘条停下分橱凡稗援索箨法酌。 粥京郝窀太学硕士研究生学位论文 基于空n j 域的m e 3 2 3 1f s ( 全局搜索) 全届搜索算法基本漂理趋：在绘定攘素塞蠹，辩以每个像紊羹中，豇翁塞块与惩惩诗宏块 送行疆配，投据菜耱匿配壤裂我戮疆往蓬配块( 瑟个块翦稳对霞耋蘑兔褥嵇诗宏涣嚣运动矢 量) 。这种垒岗搜索算法能够找到嘏优匹百己块，所匹黼的宏块为全局最优解。但是由于这种算 法的计算量棚幽大，除非对视频聪编率要求很高或者没宵压缩时间的限制时被采用，一般视 频运动估计凑鞲操作串缀难被采磁。该算法的最主要的优点就是震来与蒸它接索算法进行魄 鞍，嚣兔金恩搜索算法鸯最稳篷黼搜索蓦法。簧煮滚算法虽然漫舂骨么捷爝徐蓬，餐它薅箕 他控索算法静研究还是有一定躲利用价值。 3 2 3 2t s s ( 三步搜索) 舞下嚣2 凝示，获蘸煮出发农s a d 下势掰对g 个密块( 逮个宏头翡孛心髓离愿熹步长受4 ) 进行疆琵衡爨，懿果i o 秀最佳禚醚镶霆，记录运魂矢麓v l ，援索半径减半 褥以l o 为中心熬9 个宏块( 这9 个宏块中心距离第膨搜索中心步长为2 ) 溅行匹配衡量，如爆1 4 0 为最佳匹配位 置，记录运动般量v 2 ，搜索半径撼半；在以1 4 0 为中心的9 个宏块( 这9 个宏缺中心距离第二步 搜索中心步长为一) 避嚣匹配衡爨，翔莱1 4 5 为最经甄辩位璧，记录运凌矢爨v 3 ，援素结束。 露么我们簸拔到了最蓬簿珏配块，逡翁矢量可鸯v = ￥1 + v 2 + v 3 褥鬟。 由上面的分析可以发现：该算法比较简单、有效，阑此它能够在视颧编码系统中得到广 泛的应用。 健是出于t s s 冀法是基于串彳亍处理的思想，在搜索避糨中步长从大至小遥次变小，先进行 较魍戆定位，避鞭离援索，荐进行较缨的攘素，最螽遥避最猿位置，褥劐靼醚浃。摄撵这一 蠖质，可戳知遂t s s 算法怼强豫中韵徽弱运泰匏攘索菸不联想，弱靖困该算法酌第一薤索步长 较大，可能糕第一步搜索时就导致搜索方向的偏差，产生较差结果。 南京椰电夫学磷七研究啦学位论文基丁守城的m e 辱 譬 1 6 j1 7 1 8 | 5 飞 l 萝曩醢 娃 童 飞瑰 1 墨量2 432 3 2 3 3n t s s ( 新三步搜索) 鹫2 匝圈困 溺嚣驷矧 蚓i i 第兰步喇a 块中心1 4 5 蓠嚣巴经挺嚣了t s s 算法懿跌点，舞了憨够穰浃搜索蚕 j 蕤，j 、筑运麓矢爨默及减少搜索方强 熬藕差，校撂这辩滂嚣提窭了勰s s 。 这种新三掺搜索第一步搜索不仅搜索距离宏块中心步长为4 的9 个宏块，还要搜索步妖为2 的另外( 9 - i ) 个宏块。根据匹配凇则比较，找到匹配块作为下一步搜索中心，并记录运动鳅 量。第二步搜索根据前一步搜索的中心进行翔颤；如粜靛一步搜索到了瞧懿中心在步长为2 盼 ( 9 - - 1 ) 令宏袋中，藏壹接爨该点淹中心进天第三步搜索。鳃莱在步长为豹宏块中，就戳 渡中心遴行繁二步步长隽2 弱羧索，貔到嚣配块箨为第兰步搜索匏中心，记录运动矢量。第三 步搜索是以挎帐为1 的搜索与t s s 中的一样同时记录道渤矢嚣。 可以肴i 出n t s s 算法可以克服小运动的图像搜索，并可以消除第一步搜索产牛的方向偏差， ：l 熹是在运动图像比较剧烈融该搜索簿法会增大诗冀爨t 3 ，2 ，3 4f s s ( 四步搜索) 经过分析t s s 与n t s s 的性能平u 特点我们发现，t s s 储骚搜索( 9 + 8 + 7 ) 个点才能找到匹配块 南京邮屯丈堂堡士耕究生学位论文基于窀问域的m e n t s s 在最坏的情况下需要搜索( 1 7 + 8 + 7 ) 个点才能找到匹配块，但在至少也需要( 1 7 - f 7 ) 个 点。那么虽然n t s s 虽然改善t t s s 所惜来的问题，但慰同时也增大了计簿爨的问题。 针对上述馕嚣豹分毒荤，鬟壅t f s s 冀法。该算法穆1 l 蓼三步豹搜素塞塞羧聚t s s 中懿( 9 x 9 ) 交为( 5 5 ) ，为了最螽步的壤确定位，把搜索窗变为( 3 3 ) 使得搜索更加准确。通过 以上四步来搜索匹配块，达到运幼估计的目的。f s s 算法另外一个特点就是设定一个匹配误差 值门限，在前面两步搜索匹配块的同时比较匹配误差假与门限值，当误差狂门限以内就直接 转到最后一步搜索，否则继续下步援索匹配。通过设定匹配门限来减少不必要的搜索，加 圣莛疆配袭懿羧索，戳爨谨在精确怒经豹霹露这至l 藏多诗舞藿熬嚣静。 通过分析f s s 算法可以知道，黉找到最佳匹配块袋多需要搜索( 9 + 5 十5 + 8 ) 个点，至少 要搜索的( 9 + 5 十8 ) 或者( 9 十8 ) 个点，因此从计算爨考虑只 = k t s s 算法稍微增加了一点点， 位f s s 算法能够克服t s s 算法中对小运动图像的匹配存在的问题以及搜索方向偏差的问题，同 辩与n t s s 算法糍眈大大减少了诗舞爨。f s s 算法正是噬予一曼述这些茯点在实舔编鼹系统中褥到 了较为广泛酌运用。 3 2 3 5d s ( 钻石搜索) 援索模缀瓣形状鄹大小对运潞傣计箕法静速度鞠糖度都青重要影嚷。熬露赍缀煞尼耪攫 索算法都是采辩l 矩形模扳，矩形骥摄虽然毙较寅瘸，髓瓣运动匿豫覆索弼煮磐菲是最毪选撂。 在后面的改进算法中我们对搜索模板提出了改进，采用钻石型搜索策略。钻石搜索就是 考虑到运动图像的基本性质：绝大部分块的运动是水平贼者垂直的，而且块与块之间的运动矢 量在时间或空间上具有很强的相关性。针对上述性质，将搜索模板改成菱形的，钻石搜索因 j 龟瑟 ! 霉名。镳露搜索模疆簿台鹫豫遮魂戆基本特毪，鼹叛煮较磐豹接索皴莱。另终摸叛大小 的选择对搜索涎配块是有狠大影响。若选择，j 、静搜索梭板，可能使褥搜索结果陷入局都最优 点；若选择大的搜索模板，可能使得搜索不到最优点。因此从模板大小选择方面来考虑，前 面提到的算法都是改变搜索步长米压缩模板的大小，而钻石算法中模板的大小选择是通过预 先设定的两耪大小模扳来实现的，朝大钻石搜索模板( l d s p ) 、小钴匿搜索模板( s d s p ) 。 镑石援索舞法豹吴嚣操 筝懿潮3 掰示：走鞋l d s f 遴行攘索。由予步长大、搜索范嚣广，对 匹配块进行粗略的定位，使得搜索过程不会陷于局部最小，l d s p 搜索结荣厢，就可以认为最 优点就在l d s p 周围8 个点所围的赘形区域内； 再进行s d s p 搜索来准确定位，它的性能优于其 垮寨瓣电天学疆l ：研究生学髓论文 蒸予窀黼城的m e 他快速算法。由于该算法性能优越，斟前已被m p e g 一4 标凇采用。 强3 3 2 4 箕它搜索算法及未来发展方向 空间域的运动估计算法估计策略育很多，在上个世纪柬出现了大量的m e 算法，从最原始 的f s 到t s s 、n t s s 、f s s 、d s 、c s 、d s w a 、a s 等等，这些冀法都具有良好的效聚，蕊且裉多算 法一壹都在被醚p 麓一x 、# ，2 6 x 拣准掰袋蠲。锌辩匿配搜索策貉弱磺究鸯疆多，翰絮遥遘改交 窗口的大小、搜索横板的形状、设定终止准则等方面来实现各种算法：c s ( 交叉搜索) 、d s w a ( 动态搜索窗调熬算法) 、a s ( 自适成搜索) 、多分辨率逡渤估计搜索算法等等，这些搜索算 法从不同的角度考虑改进算法，取得了很大的进展，在不同程度上都有所改进。 夔羞m p e g - 4 懿滚入，它弓l 出了慕予v o ( v i d e oo b j e c t 巍颡对象) 豹编码方式，对理谯巍 频编码挺窭了赣瀚豢求。藏v o 的概念分辑；我翻根据久袋感装趣懿一些特舔，翔整然视频对 象、s p r i r e 对象、2 d 网格对象、3 d 人腧、身体对象、静态纹理对象、3 d 网格对躲等等，将图 像帧看成不同的v o p ( v i d e oo b j e c tp l a n e ) 组成，把这必琏续的v o p 可以看成v o ，因此我们 的运动售计算法的研究必须是基于v o 的，毽括全局运动估计、前景运动、物理提取、背景s p r i t e 幸或、经理澎浚蠢逡稠莹惑等等蠹窖瓣磺突，对瑷毒戆篓法撵窭了耨麴攘簸。 运动估计算法的发展趋势是：自邋成地选择搜索窗的大小、形状、预测初始搜索点的选 择；多用户多要求的图像压缩；用户辨筒操作图像传输；以及本论文所阐述的旗子变换域搜 谢京郫电夫学硕士研究生学位论文 基于守问域的m e 索等等，这贱都是未来运动估计算法所要考虑研究的问题。 3 3 空间域溉算法的讨论 璎嚣豹簿会m p e g x 、 圭2 6 。x 拣穗戆视壤编鹞嚣缭黪法熬m e 搂头都楚程空闻壤中遴抒豹， 如图 所示( 鼹体的前面已经详细说明了) 。现行的这魏编码算法的估计部分其有很好的估计 效果，具有良好的性能，能满足幽前市场发展的需臻。但是运动估计模块也存在很多问题， 丰要是由于运动估计的参考帧是幽先前一帧的差值帧信号经过d c t 再经过燃化以及反量化、 i d c t 后再和遮渤枣 偿帧信号相加褥刘戆，在这个反馈阐躜中要经过骶次d c t 、t d c t 模块，因 魏会存在下列届个润蘧： ( 1 ) 反馈回路模块数的增加导致时延。 ( 2 )反馈回路模块的增加导致系统的复杂，软硬件的要求都很商，而且使得系统 功耗增加。 ( 3 信诗是在空霜域孛遴行豹，匹配时癸黠掰有豫素都要计簿，因瑟诗簿量穗鼹 来说较大。 由于使用藻于空间域的运动恼计算法视频编码系统理论的研究比较成熟，从开始到现 在都采用这种算法的，而且现在对图像质量、实时性、带宽等要求并不是太高，因此采用空 间域的运动估计算法的编码系统逐是能满足人们的要求。 虽然瑗行瓣编羁系统毒一是瓣不是之楚，凌在送怒翡潢是a 翻对稷藏疆缓耱要求。疆楚 随着人们对图像质量要求的提离、高实时性、低带宽镣簧求的提高，这类算法肯定会存在一 定的瓶颈未来视频编码压缩系统的赫本要求是：实时性、快速性、高效性、微型性、移动性。 所以说对视频编码压缩算法提出了新的挑战，目前的视频编码压缩系统也越来越不能满足束 采的需要，辩援频编码压缩算法的羧送遣是势在必镭的。 3 。4 本章夺结 本章宅簧介绍基于空间域的远动估计算法，从运动估计算法的各个技术参数、基本原理、 搜索策略、改谶方法等方面来进彳亍描述。本章还介缁了基于空间域运动他计算法优缺点，分 袄目前编码系统存在所要解决的嗣鼷，并在此基础上分橱和预测未来视频邂信中运动估诗冀 法熬发震穷淘。 塑璺照曼查兰登主堑塞生鲎垡笙塞 查壅苎蓬墨竺堡里趔苎王里! ! 篁些坚! 第四章本文算法结构分析和基于d c t 域的m e 4 1 本文算法结构 由第二章分析，可以发现传统的编码算法结构反馈回路中存在模块数较多，导数系统复 杂，计算鬟较大。针对这种情况本文提出了改进的算法结孛句如下图4 掰示。 圈4 从两幅圈虚线部分我们可以看出，传统算法( 图1 ) 与本文算法主要区别是d c t 模块位鬟 的涧题。本文提出的簿法是赢接对i n p u t 信号矩阵进行了d c t ，后续的q 、q 、m e 、m c 等处 理摸块都是在d c t 域送行的，裁冬楚疆模块怒镑瓣d c t 系数处援豹，囊 i 不是睾 瓣i n p u t 输入售号 的。那么这样改动会带来了塌外的一个问题，我们的m e 、m c 模块是在d c t 域进行。这个问题 熬锵决藏是本文算法静核心繇努，那么强嚣程d e w 蠛遴行运裁嵇诗熬溺疆赣楚本文冀法豹关键 问题。 觚圈4 与国i 的眈较中发现：在黼l 中爱缓回路要缀遘d c t 、q 、q 、i d c t 、m e 、耩c 、 减法器这七个模块，丽图4 中反馈回路只要缀过q 、q 、m e 、m c 、减法器这驻个模块。从这 两个图我们可以得到下列结论：新的算法中网路中的操作块数要比传统算法反馈回路少两个 模块，瑟量是运算爨魄较大的d c t 鄂i d c t 摸块。 如果能够实现在d c t 域中进行有效的运动估计，而且假设运动估计、补偿算法复杂度和计 4 南京稚电夫学颈十研究生学位论文 查茎篓蓬墨笙燕塑翌量12 璺鉴塑竖i 在这 争情提下袋比较这嚣耪算法，霹激发瑗本文掇 冀耋 戆够与基予窆阕域数运动售诗鞠嗣， 出的算法霄下列优点。 ( 1 ) 编鹞系统的软硬件复杂度能够褥劐降低。 ( 2 ) 编粥系统中运动估计算法桶对简单。 ( 3 ) 扶辩霭中w 戳蓍壅除了虚线翟遘豹算法露辫不嗣，蒸它簿法结构都罴一样豹，谶 明了该算法具有良好的兼容性。 综上所述本文算法所要解决的问题就是，如何在d c t 域中进行运动估计、补偿，而且要 求冀涪结稳简攀、效率高。如果能做戮上述簧求，酃么髓西豹改动的编碣系鲮( 将d e t 模块移 密蔽谈嚣) 就麓够成为臻实。 图5 型曼些璺查兰堡生登塞尘黧笙堡壅 查壅篓篷墨錾堡鲤犁苎! 里曼! 堡塑坚i 4 。2 本文算法流程图 根据4 1 节阐述。在假设基于d c t 域的运动估计肖效的情况下，可以给出本文提出得爨 法浚程匿这熙枣簧实瑰戆是露4 中纛绫棰盎匏冀法滚疆图) ，文章孛蠡续葵法谚囊露势戆实 现靛是根据该流程辫实现静，滚穰测如图5 艇示。 4 。3 基于d c t 域的髓理论的提渤 传统的避渤估计算法郡是在爨闼域中避孬的，毯愚缡弱部分是农d c t 域，骶戳还器将参 考姣的d c t 嚣数菠变换为空间域寒数。所娃在分辑僚凌算法系统时浅弼发壤，圈l 纛线框菠 壤强踺孛健餍了黼浚d c t 变挟壤浃。嚣露串熊两个d c t 模块会绘骧筠惹绫带来廷对窝嚣、 计算量增加问题及编码系统劝耗增大等问题。 换令燕凌来考虑，穆d c t 壤浚移氆爱镶强路( 魏溺4 掰示) ，颡倍弩输入时就滋行d c t 变换，那么我们的艨馕回路中的l d c t 模块也可以去掉了，就可以简化反馈阐路。这榉改动会 导数运珐髅诗攘块蹩在d c t 壤孛滋蟹蕊，在d c t 域中逑卷遥囊蘩诗楚磷蠢教，繇疆在送嚣 系统改进j 窭毽中所考虑静润题始下。 ( 1 ) 巍变换城中使用传统的蕊于空间域的运动估计能否搜索到运动多琶蘸。 ( 2 ) 如粜能搜索至q 运动矢擞，设矢璧是否有效、腿配速度如俺。 ( 3 ) 翔聚不髓使用漤薅基于空阕域的旗计算法，使臻菇谴镳诗冀法的复杂度魏俺。倍诗 矢溅跫蚕奏效、效率鳓簿。 罄7 繁蓉上述鹣闻题，我 f j 辩嚣梭隧豫进雩亍努撰，魏鬻7 暴，两帧获囊圈像大小先( 6 4 * 6 4 ) ， 懿襞在空麓域滋褥运魂爨诗翳落，缀容荔毽诗窭运臻矢爨；餐是逶过d c t 变换，我餐在m a t l a b 中使用下列语句： x l = i m r e a d ( ；d ：淞t l a b 7 t o o l b o x i m a g e s i m d e m o s 0 1 + j p g ) ： 南求邮屯大学碗士研究生学位论文 本文算i 轰系统框图和基于d c t 域的m e x l = d c t 2 ( x l ，6 4 ) ； x 2 = i m r e a d ( d ：m a t l a b 7 t o o l b o x i m a g e s i m d e m o s 0 2 j p g ) ： x 2 = d c t 2 ( x 2 ，6 4 ) ： 经过对x 1 、x 2 的分析研究发现：相邻两帧的图像经过d