《基于块匹配算法运动估计概要.doc》由会员分享，可在线阅读，更多相关《基于块匹配算法运动估计概要.doc（15页珍藏版）》请在金锄头文库上搜索。
1、鉴于块般配算法的运动预计纲要鉴于块般配算法的运动预计纲要：本文第一介绍了运动预计和块般配的观点和思想，而后详尽介绍了块般配的搜寻算法。最后依据块般配算法的运动预计给出了一个设计。要点字：运动预计，块般配，算法1 研究背景跟着现代信息社会对通讯业务要求的不停增添，图像通讯与通讯网容量的矛盾日趋突出，特别是拥有宏大数据量的视频图像通讯，更是很难传输和储存，极大的限制了图像通讯的发展。比如，按CCIR601建议，一般质量的电视信号数字视频的码率约为216Mbit/s，而高清楚度电视HDTV则在1.2Gb/s以上，假如没有高效率的压缩技术，则难以传输和储存。而运动检测与预计不单是军事领域中目标探测与追
2、踪的有效技术之一，同时也是视频图象编码与压缩的常用方法与核心技术。所以，该项研究关于复杂背景下的目标探测以及视频办理均拥有重要的应用价值。运动预计和运动赔偿是密切联系的，它是视频图像压缩编码中使用的一项核心技术，很好的解决了视频图像中时间冗余的问题，经验表示，适用化的压缩方法能够将运动图像数据压缩30倍而不失真。运动预计技术主要分为两大类:象素递归法和块般配法。考虑到计算复杂度和及时性要求，块般配法已成为目前最常用的方法。明显，要想获取好的运动赔偿，要点是要有正确的运动预计，所以运动预计算法的研究成为视频压缩算法的研究要点。运动预计研究的主要内容就是怎样迅速、有效的获取有足够精度的运动矢量。即
3、把前一帧的运动部分依据运动矢量补过来，同时用其余方法获取其节余的不一样部分的过程称为运动赔偿(MotionCompensation,MC)。就这样，采用运动预计和赔偿能够有效地去除视频信号在时间方向的重复信息，达到压缩的目的。此中，在这方面的一种有效方法就是块般配运动预计BMME(Block-MatchingMotionEstimation),它目前已被很多视频编码标准所采用。为了提升搜寻速度和效率，目前研究最多的是鉴于块般配(BlockMatching,BM)的迅速搜寻算法，比如三步法，四步法，二维对数法，菱形法等。跟着计算机网络的普及和发展，好多信息能够经过网络实现共享。形色兼具/1的视频
4、信息在网络传输的信息中所占有的比率也愈来愈高。但因为视频信息自己十分宏大，限制了其在网络中的流传速度。于是视频信息的压缩成为视频传输的一个重要环节。数字视频信息是由数字图像的时间序列构成的，每一幅数字图像称为一帧。视频编码的一个主(frame)要目的就是在保证必定重构质量的前提下，以尽量少的比特数来表征视频信息。视频编码是视频压缩的要点技术。视频编码与的原理是：因为表示图像和视频信息所需的大批的数据常常是高度有关的，这些有关性会惹起信息的冗余，所以能够经过去除这些冗余信息来实现对视频数据的压缩。静止图像的压缩是在保持重修图像质量能够接收的同时，尽量去除图像自己存在的空间冗余，而视频信号的压缩，
5、除了去除空间冗余以外，还能够经过去除时间冗余达到较高的压缩比。运动预计技术是视频图像压缩编码中使用的一项核心技术，很好的解决了视频图像中时间冗余的问题，运动预计技术主要分为两大类:象素递归法和块般配算法。考虑到计算复杂度和及时性要求，块般配法已成为目前最常用的方法。2 实验原理如图1所示,运动预计的基本思想是将图像序列的每一帧图像分红很多互不重叠的宏块,并假定块内各像素只作相等的平移,而后关于目前帧中的每一块到前一帧或后一帧某一给定搜寻范围内依据必定的般配准则找出与目前块最相像的块,即般配块,由般配块与目前块的相对地点计算出运动位移,所得运动位移即为目前块的运动矢量。宏块大小为MN,一般取16
6、16。搜寻范围一般由最大偏移矢量来决定,设可能的最大偏移矢量为(dxmax,dymax),则搜寻范围为(M+2dxmax)(N+2dymax)。图1运动预计基来源理22.1块般配介绍依据一般的想法，运动预计应当第一将图像中静止背景和运动物体区分开来，而后对运动物体的实质位移进行预计。但块般配方法却不是这样，它的思想是将图像区分为很多互不重叠的子块(比如1616)，并以为子块内全部像素的位移量都同样。这意味着每个子块被视为运动物体。假定在图像序列中，t时辰对应于第k帧图像，t-时辰对应于第k-1帧图像。关于k帧中的一个子块，在k-1帧中找寻与其最相像的子块，这个过程称为找寻般配块，并以为该般配块
7、在k-1帧中所处的地点就是k帧子块位移前的地点，这类地点的变化用运动矢量D来表示。将图像切割成MN的小块，并假定块内象素作同样的运动，且只作平移运动。固然实质上块内各点运动不必定同样，也不定只有平移运动，但当MN较小时，上述假定可近似建立。这样做的目的不过为了简化运算。块般配法对目前帧图像的每一块，在上一帧的必定范围内搜寻最优般配，并以为本块就是从上一帧最优般配块地点处平移过来的。设可能的最大偏移矢量为(r,r)，则搜寻范围为(p+2r)(q+2r)。图2示出了待般配块与搜寻区的几何地点关系。跟着图像压缩编码技术的发展和对压缩效率愈来愈高的要求，在好多场合均要求运动矢量精准到亚象素元级。图2待
8、般配块与搜寻区的几何地点关系块的大小遇到两个矛盾的拘束:块大时，块内各像素作平移运动的假定易被损坏，影响预计的精度；块小时，则易受噪声影响，预计不够靠谱，并且运算量增添，所需传输的附带信息也增添了。所以一定恰到利处地选择块的大小，以做3到二者兼备。目前的视频压缩标准，如H.26x和MPEG等，一般均以1616大小的块作为块般配单元，这是一个已为实践证明的较好的折衷结果。2.2失散余弦变换(DCT)失散余弦变换（DCT）是利用傅立叶变换的对称性,将图象描绘为不一样幅值和频次的正弦值之和的形式；是图象压缩JPEG压缩算法的基础和核心。是一个无信号损失的双向数学过程。经过DCT变换能去除视频信号的空
9、间冗余。一个NN矩阵的二维DCT定义以下：(1) 正变换N1N1f(x,y)cos(u(2x1)cos(v(2y1)Fc(u,v)c(u)c(v)（2.1）x0y02N2N(2)反变换N1N1Fc(,v)cos(x(2u1)cos(y(2v1)f(x,y)c(x)c(y)（2.2）u0v02N2N此中1/N(k0)c(k)2/N(1kN1)2.3块般配的准则运动预计算法中常用的般配准则有三种，即最小绝对差(拟D)、最小均方误差(MSE)和归一化互有关函数(NCCF)。分别定义以下：1、互有关函数(Cross-CorrelationFunction,简称CCF)s(n1,n2,k)s(n1d1,
10、n2d2,k1)n1,n2B（2.3）s(n1,n2,k)2s(n1d1,n2d2,k1)2n1,n2Bn1,n2B此中，pn1,n2p。(2.3)式是计算目前帧中(XY)矩阵域与前帧相对应的(X+2P,Y+2P)矩阵地区互有关函数。2、均方偏差函数(MSE)41s(n1,n2,k)s(n1d1,n2d2,k2MSE(d1,d2)1)（2.4）N1N2(n1,n2B)此中，pn1,n2p。(2.4)式是计算相邻帧相对应(XY)矩形地区的最小均方偏差。这是一种非线性丈量，能较好地追踪图像的协方差模型。3、绝对均匀偏差函数(MAD)1s(n1,n2,k)s(n1d1,n2d2,k1)（2.5）MA
11、D(d1,d2)N1N2(n1,n2B)(2.5)式是最简单的般配函数，用它计算相邻帧的绝对均匀偏差。在(2.3)，(2.4)和(2.5)式中都在找寻(x,y)，获取一个最小失真矢量。(2.3)式是计算一个最大的自有关函数CCF(x,y)，而(2.4)和(2.5)式是计算最小的均方偏差和绝对均匀偏差函数MSE(x,y)和MAD(x,y)。因为块般配算法计算简单，能够及时办理，近几年获取宽泛的应用。4、最大像素般配统计(MaximumPixelsCounting，MPC)还有一种般配准则叫做最大般配像素数(MPC：Matching-PixelCount)准则。第一依据下式将目前块中的像素分红般配
12、像素和不般配像素：T(n1,n2,d1,d2)1(s(n1,n2,k)s(n1d1,n2d2,k1)t)0(Otherwise)（2.6）MPC(d1,d2)T(n1,n2,d1,d2)（2.7）(n1,n2B)T(n1,n2,d1,d2)1，则地点(n1,n2,d1,d2)的像素为般配像素，不然为不般配像素。2.4块般配的搜寻算法前两节的剖析能够发现，在块般配方法中最重要的两个问题是怎样确立:(1) 鉴别两个子块般配的准则:(2) 计算量最小的搜寻方法。对这两个问题的不一样解决方案构成了不一样的搜寻算法。下边将对一些典型的块般配迅速搜寻算法进行逐次介绍。52.4.1完整搜寻法（1）算法思想全
13、搜寻法(FullSearchMethod,FS)也称为穷尽搜寻法，是对(p+2r)(q+2r)搜寻范围内全部可能的候选地点计算MAD(i,j)值，从中找出最小MAD，其对应偏移量即为所求运动矢量。此算法虽计算量大，但最简单、靠谱，找到的必为全局最优点。（2）FS算法描绘FS算法描绘以下:Step1:从原点出发，按顺时针方向由近及远，在逐一像素处计算MAD值，直到遍历搜寻范围内全部的点.Step2:在全部点MAD中找到最小值，该点所在地点即对应最正确运动矢量。（3）FS算法的剖析FS算法是最简单、最原始的块般配算法，因为靠谱，且能够获取全局最优的结果，往常是其余算法性能比较的标准，但它的计算量确实很大，这就限制了在需要及时压缩场合的应用，所以有必需进一步研究其余迅速算法。2.4.2二维对数法二维对数(Two-DimensionalLogarithmicTDL)搜索法由和提出，它创始了迅速算法的先例，分多个阶段搜寻，逐次减小搜寻范围直到不可以再小而结束。（1）TDL算法描绘TDL算法的基本思想是从原点开始，以“十”字形散
