下载文档原格式
快速块匹配运动估计算法的探索与分析——浙江大学第13期srtp研究报告指导教师：陆系群组员：金鑫、徐洋、徐超快速块匹配运动估计算法的探索与分析摘要：本文介绍了块匹配运动估计算法及对现已实现的三种算法（新三步法、四步法、钻石算法）进行分析及对比。
关键词：运动估计算法、块匹配、三步法、四步法、钻石算法Exploration and Analysis of Fast Block Matching Algorithms forMotion EstimationAbstract: This article introduces Fast Block Matching Algorithms for Motion Estimation, and analyzes three implemented algorithms (New three-step search algorithm, Four-step search algorithm, diamond search algorithm).Key Words:Motion Estimation Algorithms, Fast Block Matching, Three-step search algorithm, Four-step search algorithm, diamond search algorithm第一部分概述1.研究背景视频压缩(Video Compression)技术是计算机处理视频的前提。
视频信号数字化后数据带宽很高，通常在20MB/秒以上，因此计算机很难对之进行保存和处理。
采用压缩技术以后通常数据带宽能降到1-10MB/秒，这样就可以将视频信号保存在计算机中并作相应的处理。
视频图像数据有极强的相关性，也就是说有大量的冗余信息(Redundant information)。
冗余信息可分为空域冗余信息和时域冗余信息。
压缩技术就是将数据中的冗余信息去掉。
基于块匹配的运动估计的改进算法基于块匹配的运动估计是视频编码领域中应用最广泛的算法之一。
它通过将视频帧分为若干个互不重叠和重叠的小块，分别在参考帧和当前帧中找到最匹配的块，从而计算出运动矢量。
然而，基于块匹配的运动估计算法在预测运动估计值时存在预测误差较大的问题，尤其是在运动剧烈、纹理丰富的视频中表现不佳。
针对这个问题，本文提出了一种改进的运动估计算法。
首先，我们将参考帧和当前帧中的小块进行PCA主成分分析（Principal Component Analysis）降维处理，以减少特征维数，提高块匹配的精度和速度。
PCA可以将低维数据集映射到高维空间中，从而发现数据的内部结构和规律。
通过计算块的协方差矩阵和特征值分解，我们可以得到块的主成分，从而将块从原本的三维（x，y，t）降至二维或更低维，降低运算量和存储量。
其次，我们通过引入多尺度搜索（multi-scale search）来解决匹配误差较大的问题。
多尺度搜索可以将搜索尺度从大到小逐渐缩小，从而可以更好地匹配被遮挡的纹理细节和不同尺度的特征，提高匹配的准确度。
在搜索过程中，我们先通过抽取参考块和当前块的全局特征（如颜色、对比度、块的大小等）来确定最佳的搜索范围和步长。
然后，在最佳搜索范围内，我们通过计算相邻块之间的相关性来筛选出可能匹配的块，并进一步计算匹配程度和误差向量，最终得到运动矢量。
最后，我们采用了运动矢量的预测和补偿技术来进一步提高预测精度。
在传统的块匹配算法中，运动矢量往往会出现断点或跳变现象，造成运动预测误差较大。
为了解决这个问题，我们借助多帧画面的信息，通过分析运动方向和速度的变化趋势，预测下一帧的运动矢量，并将其用于运动补偿，从而使运动估计更加稳定和准确。
本文提出的改进算法在基于块匹配的运动估计算法的基础上，引入了PCA降维、多尺度搜索和运动矢量的预测和补偿等优化策略，有效提高了运动估计的精度和速度，对于应对复杂运动场景下的视频编码中具有重要的意义。
图像处理中的运动估计与运动补偿方法对比研究概述：在图像处理领域中，运动估计与运动补偿是常用的技术方法，用于处理视频序列中物体的运动。
运动估计是通过对连续帧之间的像素位移进行分析，来估计物体的运动轨迹。
而运动补偿则是根据运动估计的结果，对图像进行处理，以消除运动导致的图像模糊与变形。
本文将对常用的运动估计与运动补偿方法进行对比研究。
一、运动估计方法1. 基于块匹配的运动估计方法：基于块匹配的运动估计方法将图像划分为多个块，通过搜索邻域中与当前块相似的块，来确定运动向量。
常见的基于块匹配的运动估计算法有全局运动估计法（Global Motion Estimation）和局部运动估计法（Local Motion Estimation）。
全局运动估计法适用于场景变化较小的视频序列，通过对整个图像进行分析来估计全局的运动。
而局部运动估计法则适用于场景变化较大的视频序列，它将图像分为多个小块，对每个小块进行独立的运动估计。
2. 基于光流的运动估计方法：基于光流的运动估计方法利用了物体在连续帧之间的像素强度变化来估计物体的运动。
光流计算方法包括基于亮度的方法和基于特征点的方法。
基于亮度的方法通常使用亮度差分或亮度约束方程来计算光流，它假设相邻帧中像素的亮度保持不变。
基于特征点的方法则通过对图像中的特征点进行跟踪来计算光流，例如使用特征点的轨迹或特征描述子。
3. 基于模型的运动估计方法：基于模型的运动估计方法通过建立物体的数学模型，来估计物体的运动。
常见的基于模型的运动估计方法有基于刚体模型的运动估计和基于非刚体模型的运动估计。
基于刚体模型的运动估计方法假设被观测物体是刚体，运动是刚体的刚性变换。
这种方法可以通过对物体的旋转和平移进行分解来估计运动。
而基于非刚体模型的运动估计方法适用于非刚体物体，它考虑了物体的变形与形变。
二、运动补偿方法1. 基于插值的运动补偿方法：基于插值的运动补偿方法通过对图像进行插值，来消除由于运动导致的图像变形和模糊。
EBMA 算法实验报告一、实验内容以任一视频的两帧图像为输入，通过EBMA 算法，计算运动矢量、运动补偿误差等数据。
二、实验原理块匹配算法是一种重要的基于块的运动估计算法。
基于块的运动估计算法是在已估计的运动场上施加平滑约束，把图像分割为互不重叠的称为块的区域，并且假定每个块内的运动可以用一个简单的参数模型（如恒定、仿射、双线性）特征化。
块匹配算法的原理即是，以视频中的两帧图像为输入，假设为第K 帧（当前帧）与第K-1帧（上一帧）。
对当前帧图片以N*N 的图像块为单位，分成一个个块，且块间不重叠。
对于第x 个图像块A ，在第上一帧中，寻找与它最匹配的图像块A'，我们认为A 图像块是由A'图像块平移而得到的。
于是就把图像块A'到A 的运动矢量MV 记作图像块A 的运动矢量。
其原理图如下图所示：一般通过绝对平均误差函数来进行匹配：(i,j)|A(i,j)B(i,j)|p =-∑全搜索的块匹配算法是一种块匹配的搜索策略，是最简单、最原始的块匹配算法，可靠且能够得到全局最优的结果。
其基本思想是在一个预定的搜索区域内，将第m 个图像块与目标帧中所有候选块进行比较，并寻找具有最小误差的一个，这两个块之间的位移差即为所估计的运动矢量。
全搜索块匹配算法，假设图像的搜索范围为(-R,R)，为了减少计算量，设置搜索步长为1。
在范围内，对每一个可能的图像块都进行匹配计，寻找一个最优的匹配块。
对每个块，需要搜索22(2R 1)N +次，则对每帧图像需要搜索的次数为22(2R 1)M +。
三、实验内容输入视频中的两帧图像，以当前帧图像作为锚定帧，需要预测的下一帧图像作为目标帧，将其大小规定为256*256，并将其转化为灰度图像：对锚定帧图片，进行分块，取块大小为16*16。
设置图像的搜索范围为（-16,16），步长为1。
对目标帧在图像的搜索范围内搜索并计算MAD值，比较各块MAD值得大小，找到MAD值最小的当前块在锚定帧中的最优匹配快，并保存相应的运动矢量：通过得到的运动矢量图以及目标帧预测估计当前帧图像，并计算残差：其运动补偿误差为26.4406。
第22卷第3期2006年6月 河北北方学院学报(自然科学版)Journal of Hebei Nort h University (Nat ural Science Edition ) Vol 122No 13J une 2006 收稿日期:20060424 作者简介:乔月圆(19702),男,山西大同人,山西大同大学讲师.运动估计块匹配算法分析与研究乔月圆1,冯贵良2,兰安怡2(11山西大同大学,山西大同037003;21河北北方学院计算机科学系,河北张家口075000) 摘要:视频序列图像存在很强的相关性,采用运动估计和运动补偿技术可以消除时间冗余以提高编码效率,本文介绍了运动估计的原理以及一些常用的块匹配算法,并对这些算法的优劣性作了分析比较.关键词:运动估计;块匹配;算法中图分类号:TP 30116 文献标识码:A 文章编号:167321492(2006)0320067204The R esearch of B lock Matching Algorithms for Motion EstimationQ IAO Yue 2yuan 1,FEN G Gui 2liang ,L AN An 2yi 2(11Shanxi Datong University ,Datong ,Shanxi 037003,China ;21Department of Computer Science ,Hebei North University ,Zhangjiakou ,Hebei 075000,China ) Abstrcat :There is a st rong relativity between video f requency images.To improve t he coding efficien 2cy ,we can remove redundancy information by using motion estimation and compensation techniques.This paper introduces t he t heory of motion estimation and some block matching algorit hms being used f requent 2ly ,and compares t he virt ues and shortcomings between t his algorit hms.K ey w ord :motio n estimation ;block matching ;algorit hms 自然视频序编码的运动估计方法,就是计算当前帧(待编码的图像)的各像素块与其相邻帧(预测图像)的像素块的运动矢量,然后由其构成一个对当前帧的预测帧,求得其最佳预测误差,编码时只须传送预测误差值和运动矢量.由于预测误差的信息量通常会大大少于原图像的信息量,再对其施以适当的统计编码方法,则可以得到比较大的视频数据压缩.而在解码端,根据接收的运动矢量,采用运动补偿,将预测误差与己知的预测图像重合,生成解码.近年来,研究人员提出了很多运动估计块匹配算法,但是每种算法各有其优缺点和适用范围.1 运动估计的块匹配算法原理运动估计块匹配法的基本思想是将每一帧图像分割成一系列子块图像,宏块大小为M ×N (一般取16×16).计算当前帧中每一子块与相邻帧中的各子块的误差函数,把具有最小误差的相邻帧的对应子块图1 运动估计块基本原理作为当前块的预测块,并把两块的相对位移定义为位移矢量(运动矢量).其基本原理如图1所示.设当前帧的图像亮度信号为f k(m,n),前次传送的相邻帧的图像亮度信号为f k2N5(m,n),其中N s为帧差数目(通常N s可取1,3,5,…,15).假定当前帧f k(m,n)中当前块是从前帧f k2N5(m,n)平行移而来,并设该子块内M×N个像素都具有同一个位移值(i,j),假定运动物体在帧差Ns时间内水平和垂直方向的最大位移都为w,则我们可以在前帧f k2N5(m,n)对应的搜索区内进行搜索,寻找当前帧中的当前块在前帧对应的匹配块,搜索区面积为(M+2w)(N+2w).2 块匹配的准则运动估计算法中常用的准则有以下3种:1)归一化相关函数NCCF(Normalized Cro ss2Correctio n Function)N CC F(i,j)=∑M-1m=0∑N-1n=0f k(m,n)f k-N s(m+i,n+j)∑M-1m=0∑N-1n=0f2k(m,n)12∑M-1m=0∑N-1n=0f2k-N5k(m+i,n+j)12归一化相关函数NCCF的计算工作量很大,在实际应用中,一般用以下的均方误差函数和平均绝对误差函数来代替.2)平均均方误差函数MSD(Mean Square Difference)M S D(i,f)=1M N∑M-1m=0∑N-1n=0f k(m,n)-f k-N s(m+i,n+j)23)平均绝对差函数MAD(Mean Absolute Difference)M A D(i,f)=1M N∑M-1m=0∑N-1n=0|f k(m,n)-f k-N s(m+i,n+j)|通常使用求和绝对差SAD代替MAD,即SAD(i,j)=MN3MAD(i,j))在搜索区域内,如果某子块使得以上公式所计算的均方差值或绝对差值达到最小,该块就是所要找的匹配块,其位移量(i,j)就是当前帧中的当前块相对于其前帧的匹配块的运动矢量.匹配准则对匹配的精度影响不大,所以上面不含乘除法的求和绝对差SAD成为最常用的匹配准则FS(Full Search).全搜索匹配法对搜索区内的所有子块进行搜索,因此能够得到搜索区内与当前块最为匹配的块.其中前向水平、垂直搜索窗口高度和反向水平、垂直搜索窗口高度应当根据具体图像特征进行选择.如果图像变化不大,则为了提高搜索速度,可以用小的搜索窗口;反之,如果处理的序列有很多的激烈场面,帧与帧之间的变化很大,则必须用大的窗口进行搜索,以达到要求的编码质量.由于全搜索法需要对搜索窗口内每个宏块进行匹配,运算量非常大,有时甚至能占去整个编码器资源消耗的近80%.3 三步搜索法TSS(Three Step Search)如图2所示,TSS算法的基本思想是采用一种由粗到细的搜索模式.其搜索步骤一般为:第一步,从原点开始,以最大搜索长度的一半为步长检测中心点及周围8个相邻点的SAD值,找到SAD值最小点;第二步,以该SAD最小点为中心,搜索步长减半,并在缩小的方形的中心点及周围8个点找SAD最小点;第三步,重复第二步,直到步长为1,得到最后的运动向量.三步搜索法在搜索的第一步采用固定步长的搜索模式,这样可能导致该算法对细小的运动进行估计时效果不理想,并且极有可能陷入局部最小点.现实中很多图像序列的运动经常是平稳、光滑和变化缓慢的,这时全局最小值一般是基于中心分布的,而不是均匀分布的.新三步搜索法算法就是基于中心的测试模式,在原有的三步搜索法的第一步的测试点的基础上再增加了中心点的82邻域作为测试点,并且采用了半途终止的策略(Halfway2stop Technique),若最小的块位移量矩(BDM,Block Distortion Measure) 2006年6月 河北北方学院学报(自然科学版) 第3期出现在82邻域的中心点则停止搜索.具体算法为:第一步,在原有的三步搜索法的第一步的测试点的基础上再增加中心点82邻域作为测试点;第二步,如果最小BDM 在第一步出现在搜索窗口的中心则停止搜索,如果最小的BDM 出现在中心点的82邻域中,则以最小BDM 为中心计算其82邻域,找出最小BDM .半途终止策略用于有效地估计静止及半静止块的运动向量;重复上面的步骤,直到最小BDM 出现在中心,搜索停止.如果最小的BDM 出现在(±w/2,±w/2)上,则执行三步搜速算法的第二步和第三步.图2 三步搜索法图3 新三步搜速算法4 钻石搜索法DS (Diamond Search )钻石搜索法又叫菱形搜索法,以其搜索模式的形状而得名,其思想是减少进行块匹配的搜索点,具有简单、鲁棒和高效的特点.如图4所示,可以看到搜索点大都位于图像的水平和垂直方向上,这是考虑到现实中的物体在这两个方向运动的概率比较大,图像的频谱多呈菱形分布,也就是说,图像在水平和垂直方向的相关性大于斜线方向.钻石搜索法使用两个搜索模板,第一个为大钻石搜索模板(LDSP ,large diamond search pattern ),该模板包括围绕中心点的8个点,从而形成一个大钻石形(图a ).另一个为小钻石搜索模板(SDSP ,small diamond search pattern ),包含了5个点,形成一个较小规模的钻石形(图c ).搜索时首先可以进行粗定位,使搜索过程不会陷于局部最小;当粗定位结束后,可以认为最优点就在LDSP 周围8个点所围的菱形区域中;最后以上一次找到的MBD 点作为中心点,用小钻石型模式做匹配运算,MBD 点的位置即为最佳运动矢量(图b ).DS 算法的性能优于上述其它快速算法,是一种被M PEG 24校验模型所采纳的运动估计算法之一.5 运动向量场自适应搜索法MV FAS T (Motion Vector Field Adaptive Search Technique ) 运动向量场自适应搜索法首先设定一组预测器,一般为坐标(0,0)处的运动向量,或与(0,0)相邻的左边、顶上和右上处的运动向量.MV FAST 不仅仅是采用了一个大的菱形(图a ),而且还采用了一个可移动的小菱形(图c ).大菱形或者小菱形不断移动,直到发现最佳匹配点终止,此处即为菱形中央处,该点的SAD 值最小.图4 钻石搜索法图5 运动向量场自适应搜索法MV FAST 也有两种搜索模式:一种是小菱形模式,就是使用小菱形进行运动搜索,最佳点为其中心,找到该点后算法搜索终止;另一种是大菱形模式,在这种模式下,大菱形被使用,但最后一步的搜索还要使用小菱形(图b ).初始到底是选用大菱形还是小菱形进行搜索,这由运动类型的初始特性决定.如果相邻三个宏块运动2006年6月 乔月圆等:运动估计块匹配算法分析与研究 第3期2006年6月 河北北方学院学报(自然科学版) 第3期向量的最大值低于一个阈值Ll,我们称其为低速运动;如果它介于L1和另一个较大的阈值L2之间,为中速运动;如果它大于阈值L2,为高速运动.如果是低速运动,那么小菱形被使用,且(0,0)处的运动向量位于菱形的中央;若是中速运动,那么大菱形参与搜索,依然用(0,0)作为其中心;如果运动是剧烈的,使用小菱形进行搜索,此时检测(0,0)处的运动向量和其它几个预测器,最佳预测器作为小菱形的中心,同时还设定一个固定的阈值T,首先以它为限测试(0,0)处的运动向量,如果位移小于T,那么搜索终止,不再搜索其它位置.MV FAST运动估计算法无论是编码质量还是编码效率都比己有的菱形搜索算法提高了很多.6 结 论在各种基于块的运动估计算法中,以全搜索法的峰值信噪比最大,但是速度最慢.这表明全搜索法是以牺牲时间的因素来提高压缩质量的,原因是全搜索法是在整个搜索空间中进行的匹配查找,这样就可以保证完成匹配的象素是全局最优的,从而使得最终结果的信噪比最高.而其他快速搜索方法不可避免地找到的只是局部最优解,所以搜索时间虽然提高了,但编码后的质量却下降了.相比较三步搜索法(TSS),新三步搜索法(N TSS)在不损失信噪比的情况下,搜索速度明显提高了.这种搜索算法原理简单,可以比较容易地在硬件上实现.MV FAST的压缩速度明显高于其它算法,而且同时能获得相同的甚至更好的峰值信噪比,在搜索区域为16h,MV FAST的平均压缩速度提高了4到5倍,同时它的峰值信噪比分别比三步搜索法、新三步搜索法和菱形搜索法高有很大的提高.参考文献:[1] Zhu S,Ma KK.A new diamond search algorithm for fast block2matching motion estimation[J].IEEE Trans.ImageProcessing,2000,9(2):2872290[2] Wang YK,Kuroda H.Hilbert Scanning search algorithm for motion estimation[J].IEEE Trans.Circuits Systemsfor Video Technology,1999,6(5):6832691[3] 向友君,郭宝龙.运动估计快速块匹配算法[J].计算机工程,2003,256(13):62264[4] 王赜,梁川,王光兴.块匹配运动估计算法的速度优化[J].东北大学学报,2003,238(4):3152318[5] 周铁,丁钟琦.运动估值块匹配算法的一种改进[J].海南大学学报,2005,169(2):1402149[6] 全子一,门爱东,杨波.数字视频图像处理[M].北京:电子工业出版社,2005.75289[7] 容观澳.计算机图象处理[M].北京:清华大学出版社,2000.2602300[责任编辑:刘守义](上接第66页)疾病防疫再加上自己的努力就一定能够成功.参考文献[1] 王加志.养貉技术纵深谈[M].北京:农业出版社,1989.1162144[2] 华树芳,佟煜人,籍玉林.貉的饲养[M].吉林:吉林科学技术出版社,1988.28274[3] 覃能斌,孙海霞,刘春龙.实用养狐技术大全[M].北京:中国农业出版社,2004.1772180[4] 闰庆华.充分认识初乳对仔狐、貉生长的重要性[J].特种经济动植物,2005,8(5):2[5] 宋锦英,邓龙江.狐貉的过继技术[J].现代化农业,2005,27(6):20221[6] 樊兵菊.仔貉常见病的防治[J].河北畜牧兽医,2005,21(8):33[7] 边桂萍.防止母貉吃仔的措施[J].河北畜牧兽医,2005,21(9):33[8] 陈艳军,赵秀凤.保证仔貉全活全壮的重要措施[J].河北农业科技,2004,33(1):36[9] 华盛.维生素在毛皮兽上的应用[J].特种经济动植物,2004,7(10):223[10] 苑彪.貉妊娠期严把饲料关[J].黑龙江动物繁殖,2003,11(2):40241[11] 华丽.妊娠期和产仔泌乳期的饲养管理要点[J].农村养殖技术,2003,8(10):19[12] 华树芳.幼貉育成期的饲养管理要点[J].农村养殖技术,2003,8(11):21[责任编辑:刘守义]。
一种快速运动矢量场搜索的块匹配运动估计算法编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（一种快速运动矢量场搜索的块匹配运动估计算法）的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为一种快速运动矢量场搜索的块匹配运动估计算法的全部内容。
一种快速运动矢量场搜索的块匹配运动估计算法摘要: 运动估计作为实时视频编解码中最重要最耗时的部分，大量的研究都是通过减少搜索点数来降低计算量。
而块匹配算法以其简单、高效，便于硬件实现等优点被使用到运动估计中。
针对这一特点，提出一种基于块匹配的快速运动矢量场搜索算法(FMVS)。
FMVS算法通过将视频序列时间相关性与空间相关性相结合,提出的一种新算法.该算法包括以下五部分：预测搜索起点、动态阈值进行静止块判断、方向性类型判定、运动类型判定及混合模板运用.对视频标准测试序列的实验结果表明，该算法较MVFAST算法,搜索点数降低30%—50%，对于运动复杂的视频序列峰值信噪比提高0.21dB。
关键词: 运动估计；块匹配算法;运动矢量场；(矢量场自适应搜索）MVFAST；峰值信噪比中图分类号: TP393 文献标识码： A 文章编号：对于视频序列图像，由于相连帧之间存在很大的时间相关性，通过减少时间冗余，可以提高视频编码的效率。
而基于块匹配算法以其简单、高效，便于硬件实现等优点，已经被许多视频编码标准所采纳。
运动估计算法占整个编码器的60％~80%的运算量，很大程度决定编码器的效率。
在块匹配运动估计算法中,全搜索算法精度最高,但是运算量也最大大。
为了解决运算量大,产生了很多快速搜索算法。
一类是快速算法是按照某种搜索策略只对搜索窗口的相关参考点进行计算；如一些经典算法3步法[1］，菱形搜索算法[2］,六边形搜索算法[3]。
基于块匹配的视频图像运动估计技术研究_2.4经典的块匹配算法2.4.1全搜索法（Full Search Method, FS）全搜索法（Full Search Method, FS）也称为穷尽搜索法，是对（M＋2dx）×（N＋2dy）搜索范围内所有可能的候选位置计算MAD (i,j)值，从中找出最小MAD，其对应偏移量即为所求运动矢量。
此算法虽计算量大，但最简单、可靠，找到的必为全局最优点。
FS算法描述如下：从原点出发，按顺时针螺旋方向由近及远，在逐个像素处计算MAD值，直到遍历搜索范围内听有的点，然后在计算的所有点的MAD中找到最小值，该点所在位置即对应最佳运动矢量。
FS算法是最简单、最原始的块匹配算法，由于可靠，且能够得到全局最优的结果，通常是其它算法性能比较的标准，但它的计算量的确很大，这就限制了在需要实时压缩场合的应用，所以有必要进一步研究其它的快速算法。
2.4.2三步搜索算法（Three – Step Search，TSS）此搜索算法如图2-2所示，每一步搜索9个位置点，对每一个位置计算MSE （最小均方误差）来确定最小失真方向（DMD），在最小失真方向上搜索区域减少一半进行第二步的搜索匹配，然后继续沿最小失真方向将搜索区域又减少一半第一步第二步第三步图2-2 三步法（TSS）搜索步骤来进行第三步的搜索匹配，由于第二步和第三步的9个搜索点中均有一个点是在上一步中已经计算过MSE值，所以第二步与第三步均只要计算8个点而已，所以TSS算法的计算次数是9＋8＋8＝25次，同直接匹配需要169次比较，计算量大大减少。
2.4.3新三步搜索算法[26]（New Three – Step Search, NTSS）大部分近似的快速BMA算法（如TSS、2D-LOG等）假设BDM 随搜索窗口内当前检查点与最优BDM点之间的距离的增大而单调增加（当BDM为MSE或MAD时），然而这个假设并非总是正确，原因是：①孔径问题；②分块时引起的运动物体和背景的不连续分割；③周期性纹理形状的图像内容；④光线改变。
图像编码是一种将图像数据转换为可传输或存储的压缩格式的技术。
在图像压缩中，运动估计是一个关键的步骤，它通过分析图像中连续帧之间的运动来减少冗余。
本文将讨论图像编码中的运动估计方法。
一、传统方法在过去的几十年里，许多传统的运动估计方法被提出。
其中，块匹配算法是最常用的一种方法之一。
该方法将图像划分为一系列小块，然后在前一帧中搜索与当前块最相似的块。
通过计算块之间的差异来获得运动矢量。
然而，这种方法在处理高运动图像时存在一些问题，比如运动模糊和遮挡。
为了克服这些问题，一些改进的方法被提出，比如多尺度方法和分层方法。
多尺度方法通过在不同尺度上进行运动估计来更好地处理运动模糊。
分层方法通过将图像分解为不同的层级来处理遮挡问题。
二、基于区块的方法除了传统的方法外，基于区块的方法是另一种常用的运动估计方法。
该方法将图像划分为连续的区块，并使用特征点来表示每个区块。
然后，通过比较特征点之间的位置差异来估计运动。
该方法可以更准确地捕捉到图像中的细微变化。
三、基于光流的方法基于光流的方法是一种更先进的运动估计方法。
它基于图像中的亮度变化来计算运动矢量。
该方法可以在连续帧之间建立起像素之间的关联，并将其转化为表示相对运动的光流向量。
然而，由于光流的计算复杂性，基于光流的方法在实时图像编码中的应用相对较少。
尽管如此，很多研究人员仍在不断改进光流算法的性能，使其更加实用和有效。
四、深度学习方法随着深度学习的发展，越来越多的方法开始使用卷积神经网络（CNN）来进行图像编码中的运动估计。
这些方法通过训练神经网络来学习图像中的运动模式，然后使用网络来预测运动矢量。
与传统方法相比，深度学习方法具有更高的准确性和泛化能力。
然而，深度学习方法也存在一些挑战。
首先，需要大量的训练样本来训练网络。
其次，网络的计算复杂性限制了实时应用。
此外，深度学习模型的可解释性也是一个重要的问题。
五、结论总的来说，图像编码中的运动估计是一个复杂的任务，并且有许多不同的方法可以用于实现。
图像序列运动估计中经典块匹配算法研究陈宫;牛秦洲【期刊名称】《计算机应用与软件》【年(卷),期】2012(29)5【摘要】对图像序列运动估计中的穷尽搜索法、三步法、新三步法和菱形法等块匹配算法的基本思想、算法描述、搜索模板以及算法性能进行分析和研究,并在实验仿真中,采用平均每块搜索点数和平均峰值信噪比PSNR 为衡量指标,测试了在三种典型的视频序列运动估计中每种算法的搜索速度和效果,得出菱形法综合性能更为优越的结论.%The basic idea, algorithm description, search template and algorithm performance of BMA such as ES, TSS, NTSS and DS in motion estimation of image sequence are analysed and studied- In experimental simulation, average number of searching dots per block and PSNR are taken as the measurement indices, three typical motion estimations of vidpo sequence are tested with regard to search speed and effect for every algorithm, the conclusion drawn is that the comprehensive performance of the DS algorithm sounds superior.【总页数】5页(P147-151)【作者】陈宫;牛秦洲【作者单位】桂林理工大学信息科学与工程学院广西桂林 541004;桂林理工大学信息科学与工程学院广西桂林 541004【正文语种】中文【中图分类】TP30;TN919.8【相关文献】1.基于块匹配的运动估计算法研究和优化 [J], 王会鲜;陈伟;谢涛;郑洪江2.块匹配运动估计算法研究进展 [J], 张明;毕笃彦3.视频压缩中运动估计块匹配算法研究 [J], 邹庆揆;黄毅4.基于块匹配的视频帧间运动估计算法研究 [J], 郑运昌;张连连;张红岭;张克辉;黄晓英;张静静;王磊5.基于块匹配的视频帧间运动估计算法研究 [J], 郑运昌; 张连连; 张红岭; 张克辉; 黄晓英; 张静静; 王磊因版权原因，仅展示原文概要，查看原文内容请购买。
书山有路勤为径，学海无涯苦作舟LCD 中几种运动估计块匹配算法比较(1)响应时间和保持型的驱动方式是影响液晶显示器件运动由于没有直接可用的120 Hz 视频信号，我们需要根据现有的60 Hz 视频信号，通过插帧的方法得到120 Hz 视频信号，如运动估计的方法有很多，可以分为两大类：基于像素的直接估计法和基于块匹配的基本思想是将目标应用块匹配算法，首先要有搜索最佳匹配的标准，这里称之为价值函数：均方误差（MSE）、绝对误差和（SAD）、平均绝对误差（MAD）、方差和（SSE）、绝对变化误差和（SATD）都可以作为价值函数。
其中常用的是均方误差（MSE）和平均绝对误差（MAD），如方程（1）和（2）。
其中N 为块边长像素数（为方便搜索块通常划分为正方形），Cij 和Rij 分别为当前宏块和参考宏块相应像素的灰度。
具体步骤首先要将当前和参考帧基于1.1 节介绍的基本原理，块匹配方法根据搜索原理的不同又有不同的算法，主要有如下几种，如全搜索法(ES)：从原点出发，按顺时针方向由近及远，逐个宏块计算价值函数值，直到遍历搜索范围内所有的点。
比较所有点的价值函数，找到最小值。
这是最简单、最原始的块匹配算法，可靠，且能够得到全局最优的结果，通常是其它算法性能比较的标准。
但它的计算量的确很大，耗费大量的时间和资源，因此有必要进一步研究其它快速算法。
三步法(TSS)（第二步，将步长减半，中心点移到上一步的价值函数最小点，重新在周围距离步长的8 个点处进行块匹配计算并比较。
第三步，在中心及周围8 个点处找出价值函数最小点，若步长为1，该点价值函数最小，搜索结束，否则重复第二步。
这种算法采用由粗到细的搜索模式，是最早的快速算法之一，减少了算法的复杂度和运算量。
但是整个过程采用了统一的搜索模式，。
大作业运动估计算法比较一、实验内容简要介绍各种运动估计算法，并比较不同运动估计算法的性能，主要考虑各算法的运算速度和精度。
二、实验背景视频原始图像中存在着大量的信息冗余，如时间冗余、空间冗余、信息熵冗余、谱间冗余、几何结构冗余、视觉冗余和知识冗余等等。
运动估计是视频压缩编码中的核心技术之一，采用运动估计和运动补偿技术可以消除视频信号的时间冗余以提高编码效率。
如何提高运动估计的效率，使运动估计算法的搜索过程更健壮、更快速、更高效成为目前研究的热点。
运动估计的基本思想是尽可能准确地获得序列图像帧间的运动位移，即运动矢量。
因为运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补偿编码所需位数越少，需要传输的比特率就越小。
利用得到的运动矢量在帧间进行运动补偿。
补偿残差经过变换、量化、编码后与运动矢量一起经过熵编码，然后以比特流形式发送出去。
运动估计算法多种多样，大体上可以把它们分成四类：块匹配法、递归估计法、贝叶斯估计法和光流法。
其中块匹配运动估计算法因其具有算法简单、便于VLSI实现等优点得到广泛应用。
所以本文将重点介绍块匹配运动估计算法，并对各种块匹配算法在计算速度和估计精度上进行简单比较。
三、实验原理（一）、像素递归技术像素递归技术是基于递归思想。
在连续帧中像素数据的变化是因为物体的移位引起的，郑么如果沿着梯度方向在某个像素周圈的若干像素作迭代运算，运算会最后收敛于一个固定的运动估计矢量，从而预测该像素的位移。
（二）、块匹配运动估计块匹配运动估计是把图像帧划分为若干互不重叠的块，并以块为单位寻找目标帧中每块在参考帧（上一帧或者其它帧）中最优匹配的块的相对位置，假设图像中每块的大小为M×N，dxmax为参考块水平方向可搜索最大位移而dymax为参考块垂直方向可搜索最大位移那么基于块匹配的运动估计就是在参考帧（或者其它上一帧）的(M+2dxmax)×(N+2dymax)候选区搜索窗口中找到和目标帧的当前大小为M×N的块的最匹配的块则参考块的运动矢量可用如下的数学公式描述：R表示相关性评价函数，f(m,n)表示目标或当前帧图像的灰度值。
第22卷第3期2006年6月 河北北方学院学报(自然科学版)Journal of Hebei Nort h University (Nat ural Science Edition ) Vol 122No 13J une 2006 收稿日期:20060424 作者简介:乔月圆(19702),男,山西大同人,山西大同大学讲师.运动估计块匹配算法分析与研究乔月圆1,冯贵良2,兰安怡2(11山西大同大学,山西大同037003;21河北北方学院计算机科学系,河北张家口075000) 摘要:视频序列图像存在很强的相关性,采用运动估计和运动补偿技术可以消除时间冗余以提高编码效率,本文介绍了运动估计的原理以及一些常用的块匹配算法,并对这些算法的优劣性作了分析比较.关键词:运动估计;块匹配;算法中图分类号:TP 30116 文献标识码:A 文章编号:167321492(2006)0320067204The R esearch of B lock Matching Algorithms for Motion EstimationQ IAO Yue 2yuan 1,FEN G Gui 2liang ,L AN An 2yi 2(11Shanxi Datong University ,Datong ,Shanxi 037003,China ;21Department of Computer Science ,Hebei North University ,Zhangjiakou ,Hebei 075000,China ) Abstrcat :There is a st rong relativity between video f requency images.To improve t he coding efficien 2cy ,we can remove redundancy information by using motion estimation and compensation techniques.This paper introduces t he t heory of motion estimation and some block matching algorit hms being used f requent 2ly ,and compares t he virt ues and shortcomings between t his algorit hms.K ey w ord :motio n estimation ;block matching ;algorit hms 自然视频序编码的运动估计方法,就是计算当前帧(待编码的图像)的各像素块与其相邻帧(预测图像)的像素块的运动矢量,然后由其构成一个对当前帧的预测帧,求得其最佳预测误差,编码时只须传送预测误差值和运动矢量.由于预测误差的信息量通常会大大少于原图像的信息量,再对其施以适当的统计编码方法,则可以得到比较大的视频数据压缩.而在解码端,根据接收的运动矢量,采用运动补偿,将预测误差与己知的预测图像重合,生成解码.近年来,研究人员提出了很多运动估计块匹配算法,但是每种算法各有其优缺点和适用范围.1 运动估计的块匹配算法原理运动估计块匹配法的基本思想是将每一帧图像分割成一系列子块图像,宏块大小为M ×N (一般取16×16).计算当前帧中每一子块与相邻帧中的各子块的误差函数,把具有最小误差的相邻帧的对应子块图1 运动估计块基本原理作为当前块的预测块,并把两块的相对位移定义为位移矢量(运动矢量).其基本原理如图1所示.设当前帧的图像亮度信号为f k(m,n),前次传送的相邻帧的图像亮度信号为f k2N5(m,n),其中N s为帧差数目(通常N s可取1,3,5,…,15).假定当前帧f k(m,n)中当前块是从前帧f k2N5(m,n)平行移而来,并设该子块内M×N个像素都具有同一个位移值(i,j),假定运动物体在帧差Ns时间内水平和垂直方向的最大位移都为w,则我们可以在前帧f k2N5(m,n)对应的搜索区内进行搜索,寻找当前帧中的当前块在前帧对应的匹配块,搜索区面积为(M+2w)(N+2w).2 块匹配的准则运动估计算法中常用的准则有以下3种:1)归一化相关函数NCCF(Normalized Cro ss2Correctio n Function)N CC F(i,j)=∑M-1m=0∑N-1n=0f k(m,n)f k-N s(m+i,n+j)∑M-1m=0∑N-1n=0f2k(m,n)12∑M-1m=0∑N-1n=0f2k-N5k(m+i,n+j)12归一化相关函数NCCF的计算工作量很大,在实际应用中,一般用以下的均方误差函数和平均绝对误差函数来代替.2)平均均方误差函数MSD(Mean Square Difference)M S D(i,f)=1M N∑M-1m=0∑N-1n=0f k(m,n)-f k-N s(m+i,n+j)23)平均绝对差函数MAD(Mean Absolute Difference)M A D(i,f)=1M N∑M-1m=0∑N-1n=0|f k(m,n)-f k-N s(m+i,n+j)|通常使用求和绝对差SAD代替MAD,即SAD(i,j)=MN3MAD(i,j))在搜索区域内,如果某子块使得以上公式所计算的均方差值或绝对差值达到最小,该块就是所要找的匹配块,其位移量(i,j)就是当前帧中的当前块相对于其前帧的匹配块的运动矢量.匹配准则对匹配的精度影响不大,所以上面不含乘除法的求和绝对差SAD成为最常用的匹配准则FS(Full Search).全搜索匹配法对搜索区内的所有子块进行搜索,因此能够得到搜索区内与当前块最为匹配的块.其中前向水平、垂直搜索窗口高度和反向水平、垂直搜索窗口高度应当根据具体图像特征进行选择.如果图像变化不大,则为了提高搜索速度,可以用小的搜索窗口;反之,如果处理的序列有很多的激烈场面,帧与帧之间的变化很大,则必须用大的窗口进行搜索,以达到要求的编码质量.由于全搜索法需要对搜索窗口内每个宏块进行匹配,运算量非常大,有时甚至能占去整个编码器资源消耗的近80%.3 三步搜索法TSS(Three Step Search)如图2所示,TSS算法的基本思想是采用一种由粗到细的搜索模式.其搜索步骤一般为:第一步,从原点开始,以最大搜索长度的一半为步长检测中心点及周围8个相邻点的SAD值,找到SAD值最小点;第二步,以该SAD最小点为中心,搜索步长减半,并在缩小的方形的中心点及周围8个点找SAD最小点;第三步,重复第二步,直到步长为1,得到最后的运动向量.三步搜索法在搜索的第一步采用固定步长的搜索模式,这样可能导致该算法对细小的运动进行估计时效果不理想,并且极有可能陷入局部最小点.现实中很多图像序列的运动经常是平稳、光滑和变化缓慢的,这时全局最小值一般是基于中心分布的,而不是均匀分布的.新三步搜索法算法就是基于中心的测试模式,在原有的三步搜索法的第一步的测试点的基础上再增加了中心点的82邻域作为测试点,并且采用了半途终止的策略(Halfway2stop Technique),若最小的块位移量矩(BDM,Block Distortion Measure) 2006年6月 河北北方学院学报(自然科学版) 第3期出现在82邻域的中心点则停止搜索.具体算法为:第一步,在原有的三步搜索法的第一步的测试点的基础上再增加中心点82邻域作为测试点;第二步,如果最小BDM 在第一步出现在搜索窗口的中心则停止搜索,如果最小的BDM 出现在中心点的82邻域中,则以最小BDM 为中心计算其82邻域,找出最小BDM .半途终止策略用于有效地估计静止及半静止块的运动向量;重复上面的步骤,直到最小BDM 出现在中心,搜索停止.如果最小的BDM 出现在(±w/2,±w/2)上,则执行三步搜速算法的第二步和第三步.图2 三步搜索法图3 新三步搜速算法4 钻石搜索法DS (Diamond Search )钻石搜索法又叫菱形搜索法,以其搜索模式的形状而得名,其思想是减少进行块匹配的搜索点,具有简单、鲁棒和高效的特点.如图4所示,可以看到搜索点大都位于图像的水平和垂直方向上,这是考虑到现实中的物体在这两个方向运动的概率比较大,图像的频谱多呈菱形分布,也就是说,图像在水平和垂直方向的相关性大于斜线方向.钻石搜索法使用两个搜索模板,第一个为大钻石搜索模板(LDSP ,large diamond search pattern ),该模板包括围绕中心点的8个点,从而形成一个大钻石形(图a ).另一个为小钻石搜索模板(SDSP ,small diamond search pattern ),包含了5个点,形成一个较小规模的钻石形(图c ).搜索时首先可以进行粗定位,使搜索过程不会陷于局部最小;当粗定位结束后,可以认为最优点就在LDSP 周围8个点所围的菱形区域中;最后以上一次找到的MBD 点作为中心点,用小钻石型模式做匹配运算,MBD 点的位置即为最佳运动矢量(图b ).DS 算法的性能优于上述其它快速算法,是一种被M PEG 24校验模型所采纳的运动估计算法之一.5 运动向量场自适应搜索法MV FAS T (Motion Vector Field Adaptive Search Technique ) 运动向量场自适应搜索法首先设定一组预测器,一般为坐标(0,0)处的运动向量,或与(0,0)相邻的左边、顶上和右上处的运动向量.MV FAST 不仅仅是采用了一个大的菱形(图a ),而且还采用了一个可移动的小菱形(图c ).大菱形或者小菱形不断移动,直到发现最佳匹配点终止,此处即为菱形中央处,该点的SAD 值最小.图4 钻石搜索法图5 运动向量场自适应搜索法MV FAST 也有两种搜索模式:一种是小菱形模式,就是使用小菱形进行运动搜索,最佳点为其中心,找到该点后算法搜索终止;另一种是大菱形模式,在这种模式下,大菱形被使用,但最后一步的搜索还要使用小菱形(图b ).初始到底是选用大菱形还是小菱形进行搜索,这由运动类型的初始特性决定.如果相邻三个宏块运动2006年6月 乔月圆等:运动估计块匹配算法分析与研究 第3期2006年6月 河北北方学院学报(自然科学版) 第3期向量的最大值低于一个阈值Ll,我们称其为低速运动;如果它介于L1和另一个较大的阈值L2之间,为中速运动;如果它大于阈值L2,为高速运动.如果是低速运动,那么小菱形被使用,且(0,0)处的运动向量位于菱形的中央;若是中速运动,那么大菱形参与搜索,依然用(0,0)作为其中心;如果运动是剧烈的,使用小菱形进行搜索,此时检测(0,0)处的运动向量和其它几个预测器,最佳预测器作为小菱形的中心,同时还设定一个固定的阈值T,首先以它为限测试(0,0)处的运动向量,如果位移小于T,那么搜索终止,不再搜索其它位置.MV FAST运动估计算法无论是编码质量还是编码效率都比己有的菱形搜索算法提高了很多.6 结 论在各种基于块的运动估计算法中,以全搜索法的峰值信噪比最大,但是速度最慢.这表明全搜索法是以牺牲时间的因素来提高压缩质量的,原因是全搜索法是在整个搜索空间中进行的匹配查找,这样就可以保证完成匹配的象素是全局最优的,从而使得最终结果的信噪比最高.而其他快速搜索方法不可避免地找到的只是局部最优解,所以搜索时间虽然提高了,但编码后的质量却下降了.相比较三步搜索法(TSS),新三步搜索法(N TSS)在不损失信噪比的情况下,搜索速度明显提高了.这种搜索算法原理简单,可以比较容易地在硬件上实现.MV FAST的压缩速度明显高于其它算法,而且同时能获得相同的甚至更好的峰值信噪比,在搜索区域为16h,MV FAST的平均压缩速度提高了4到5倍,同时它的峰值信噪比分别比三步搜索法、新三步搜索法和菱形搜索法高有很大的提高.参考文献:[1] Zhu S,Ma KK.A new diamond search algorithm for fast block2matching motion estimation[J].IEEE Trans.ImageProcessing,2000,9(2):2872290[2] Wang YK,Kuroda H.Hilbert Scanning search algorithm for motion estimation[J].IEEE Trans.Circuits Systemsfor Video Technology,1999,6(5):6832691[3] 向友君,郭宝龙.运动估计快速块匹配算法[J].计算机工程,2003,256(13):62264[4] 王赜,梁川,王光兴.块匹配运动估计算法的速度优化[J].东北大学学报,2003,238(4):3152318[5] 周铁,丁钟琦.运动估值块匹配算法的一种改进[J].海南大学学报,2005,169(2):1402149[6] 全子一,门爱东,杨波.数字视频图像处理[M].北京:电子工业出版社,2005.75289[7] 容观澳.计算机图象处理[M].北京:清华大学出版社,2000.2602300[责任编辑:刘守义](上接第66页)疾病防疫再加上自己的努力就一定能够成功.参考文献[1] 王加志.养貉技术纵深谈[M].北京:农业出版社,1989.1162144[2] 华树芳,佟煜人,籍玉林.貉的饲养[M].吉林:吉林科学技术出版社,1988.28274[3] 覃能斌,孙海霞,刘春龙.实用养狐技术大全[M].北京:中国农业出版社,2004.1772180[4] 闰庆华.充分认识初乳对仔狐、貉生长的重要性[J].特种经济动植物,2005,8(5):2[5] 宋锦英,邓龙江.狐貉的过继技术[J].现代化农业,2005,27(6):20221[6] 樊兵菊.仔貉常见病的防治[J].河北畜牧兽医,2005,21(8):33[7] 边桂萍.防止母貉吃仔的措施[J].河北畜牧兽医,2005,21(9):33[8] 陈艳军,赵秀凤.保证仔貉全活全壮的重要措施[J].河北农业科技,2004,33(1):36[9] 华盛.维生素在毛皮兽上的应用[J].特种经济动植物,2004,7(10):223[10] 苑彪.貉妊娠期严把饲料关[J].黑龙江动物繁殖,2003,11(2):40241[11] 华丽.妊娠期和产仔泌乳期的饲养管理要点[J].农村养殖技术,2003,8(10):19[12] 华树芳.幼貉育成期的饲养管理要点[J].农村养殖技术,2003,8(11):21[责任编辑:刘守义]。
