马小萍2016数学建模网络挑战杯2007-三等

1、第九届“认证杯”数学中国数学建模网络挑战赛承 诺 书我们仔细阅读了第九届“认证杯”数学中国数学建模网络挑战赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们接受相应处理结果。我们允许数学中国网站()公布论文，以供网友之间学习交流，数学中国网站

2、以非商业目的的论文交流不需要提前取得我们的同意。我们的参赛队号为：2007参赛队员 (签名) ：队员1：马小萍 队员2：符文杰队员3：邓连燕 参赛队教练员 (签名)： 参赛队伍组别（例如本科组）：本科组第九届“认证杯”数学中国数学建模网络挑战赛编 号 专 用 页参赛队伍的参赛队号：（请各个参赛队提前填写好）：2007竞赛统一编号（由竞赛组委会送至评委团前编号）： 竞赛评阅编号（由竞赛评委团评阅前进行编号）：2016年第九届“认证杯”数学中国数学建模网络挑战赛第一阶段论文 题 目：低分辨率下看世界 关 键 词：运动估计 块匹配 全搜索法 方向预测摘 要根据序列图像的相邻块运动矢量的高度相关性，结

3、合运动方向实现快速运动预测，提出一种基于运动方向预测的快速运动估计算法，对运动进行估计和补偿。本文对运动估计采用了快速运动估计算法，借助Matlab7.0实现算法上的定量分析；对于不同运动类型的序列图像相邻帧采用不同的搜索策略，对相对运动块进行运动方向预测并且根据运动方向选择相应的方向搜索模板进行搜索。本文采用全搜索法使得搜索方向易锁定并且降低了搜索点数，通过运用快速运动估计算法和全搜索法阐述了在低分辨率下基于块匹配的序列图像的运动方向并且通过分析全搜索的不同类型各自的特点，可以得知当运动估计算法越完善，估计出的运动矢量就会越准确，运动补偿的性能也就越好，从而方向预测的误差就会越小。参赛密码

4、（由组委会填写）参赛队号: 2007所选题目: B题英文摘要（选填）（此摘要非论文必须部分，选填可加分，加分不超过论文总分的5%）Abstract:According to the high correlation between the adjacent block motion vector of a sequence images, which combined with the direction of movement to achieve fast motion prediction, proposed a fast motion estimation algorithm base

5、d on moving direction prediction, the motion estimation and compensation.This paper of motion estimation using the fast motion estimation algorithm, with the help of matlab7.0 and quantitative analysis algorithm, for different types of moving image sequence of adjacent frames using different search

6、strategies and the relative motion prediction and block motion direction ,according to the direction of movement of the choice direction corresponding to the search template to search.In this paper, the full search method makes the search direction is easy to lock and reduces the number of search po

7、ints, through the use of fast motion estimation algorithm and the full search method described in the low resolution based on the direction of motion of the block matching of sequence image and through analysis of their respective characteristics of the different types of full search, we can learn w

8、hen the motion estimation algorithm is more perfect, the estimated motion vector will be more accurate, the better performance of motion compensation,and thus the direction of the prediction error will be smaller. Key words:Motion Estimation;Block Matching;Full Search;Direction Prediction目录一、问题重述61.

9、1问题背景61.2问题提出6二、问题分析6三、模型假设6四、符号说明6五、模型建立75.1模型的总体思路：75.1.1快速运动估计算法75.1.2完全搜索法11六、模型求解126.1新三步搜索算法126.1.1算法的基本思想126.1.2新三步搜索法算法126.1.3新三步模板及搜索过程图示136.2.1四步搜索法146.2.2四步搜索法算法146.2.3四步模板及搜索过程156.3.1菱形搜索法166.3.2菱形搜索法算法176.3.3菱形模板及搜索过程186.4.1六边形搜索法186.4.3六边形模板及搜索过程19七、模型优缺点207.1模型的优点207.2模型的缺点20八、模型推广20九

10、、参考文献20附录22一、问题重述1.1问题背景随着信息技术的不断发展和社会的不断进步，人类对信息的追求越来越丰富。其中数码摄像技术被广泛用于多种场合，同时如何在低分辨率下看世界也受到广泛的关注。图像是人们记录视觉信息的主要载体，将我们记录下的系列图像实时的传输到计算机以便人们可以获得较为直观，生动的视觉信息。有时由于客观条件的限制，拍摄设备只能在较低的分辨率下成像。为了简单起见，我们只考虑单色成像，假设成像的分辨率为32*64，成像方式是将整个矩形视野划分成32*64个相同大小的矩形格子，图像中每个像素的取值为对应格子的亮度平均值，每间隔一定时间拍摄一帧图像，运动的画面体现为图像的序列。1.

11、2问题提出 图像序列中，相邻帧之间存在很强时间的相关性，即存在很高的时间冗余。运动估计就是利用视频序列中相邻帧之间存在的时间相关性，建立它们表达上的相互关系，从而减少时间冗余，从而使用尽量少的时间判断出运动的方向。二、问题分析针对第一阶段问题：结合运动方向实现快速运动预测，由于拍摄的序列图像在时间上具有较强的相关性，对运动进行估计可以有效的减少时间相关性，运动估计是用来估计物体的位移，得到运动矢量，在实时拍摄图像的过程当中就可以判断出运动的方向，采用快速运动估计算法可以在很大程度上提高预测的有效性。运动补偿是根据得到的运动矢量，对前一帧中由于运动而产生的位移进行调整，从而得到尽可能接近本帧的预

12、测帧。运用全搜索算法对M*N搜索范围内所有可能的候选位置计算绝对值差值，从中找出最小绝对值差值，其对应偏移量即为所求运动矢量。此算法虽计算量大，但简单、可靠，找到的点即为全局最优点。三、模型假设1.同一块匹配的大小和形状选择合适并且同一块匹配内的像素运动类型是一致的；2.拍摄过程中移动的速度是匀速的；3.数码相机的材料精度足够高，拍摄角度足够好；4.拍摄的物体在帧间没有旋转，形状，大小的变化；四、符号说明符号说明运动矢量当前帧中该位置的像素参考帧中该位置的像素匹配块与当前块的相对位移归一化互相关函数绝对值差值函数最小均方差函数最大匹配像素数峰值信噪比最小块误差菱形搜索法六边形搜索法新三步法搜索

13、法大六边形模板搜索法小六边形模板搜索法水平方向位移矢量垂直方向位移矢量参考块的行的范围参考块的列的范围像素的比特数五、模型建立5.1模型的总体思路：对于拍摄到的序列图像，由于相邻帧间存在很大的时间相关性，即时间冗余。所以在实时拍摄的过程中要使时间尽量小，就需要减少时间冗余，这样可以大幅度提高图像的效率。解决这个问题的一种有效的方法就是基于块匹配的运动估计，其基本思想是将图像序列的每一帧分成M*N的宏块，然后对于当前帧中的每一块根据一定的匹配准则在前一帧或后一帧中在给定的搜索范围内找出与当前块最相似的块，即匹配块，根据匹配块与当前块的相对位置计算出运动位移，所得运动位移既为当前块的运动矢量，从而

14、判断出运动方向。5.1.1快速运动估计算法（1）搜索起点预测和运动方向预测确定搜索起点的主要方法有中值法、加权法和SAD比较法。SAD比较法预测精度高，但计算量大。一般的中值法和加权法虽然简单，但仅利用了运动矢量的空间相关性，而没有利用时间相关性。随着数据处理技术的发展，可以将参考帧中对应的运动矢量考虑进来。本算法将参考帧中对应位置块的运动矢量和其右方、下方的块的运动矢量也作为参考运动矢量，与当前块的左方、上方和右上方的块的运动矢量一起建立参考运动矢量集，来预测当前块的运动方向，作为搜索起点。图（5-1）非对称十字形多层次六边形格点运动具体搜索方法的步骤：Step1:起始搜索点搜索（中值预测）

15、Step2:不对称的十字交叉搜素；Step3:非均匀多层次六边形格点搜索； Step3-1:小矩形窗口全搜索；Step3-2:扩展的多层次六边形16格点；Step4:扩展的六边形搜索；Step4-1:六边形模式搜索；Step4-2:基于小六边形(菱形)模式搜索；（2）块匹配准则块运动估计的基本思想是将图像序列中的每一帧图像分成许多互不重叠的宏块，并假设每个宏块内的各个像素只做相等位移的运动，在当前帧中的每一个块到参考帧中某一给定范围内，根据一定的匹配准则找出最相似的块，即为匹配块，由匹配块与当前块的相对位置计算出运动位移,即为当前块的运动向量.如图1所示，为当前帧中要进行匹配的图像块，为参考帧

16、中与B位置相对应的块，为参考帧中搜索窗口区域内与相似度最高的块，即与相匹配的块.块相似度匹配准则可表示： 图（5-2）：块运动估计原理图的表达式为: (1)当（，）=（1,0）时表示SAE；当（，）=（1,1）时表示平均绝对误差；当（，）=（2,1）时表示均方误差.为避免复杂的平方运算，降低匹配运算的复杂度，本文采用函数作为匹配准则，令E达到最小的MV就是当前块的运动向量，即求 （2）的表达式为: （3）的表达式为: （4）的表达式: （5）的表达式为: （6）(i,j)的值最大的点为最优匹配点。的表达式为: （7）的表达式： （8）5.1.2完全搜索法全搜素法也称为穷尽搜索法，是对搜素范围内

17、所有可能的候选位置计算值，从中找出最小其对应得偏移量即为所求运动矢量。（1）全搜索法算法法描述Step 1：从原点出发，按顺时针方向由近及远，在逐个像素处计算的值，直到遍历搜素范围内所有的点；Step 2：在所有点中找到最小值，该点所在位置即对应最佳运动矢量；（2）二维对数法算法描述Step 1：从原点开始选取一定的步长，在以十字形分布的的五个点处进行块匹配计算并比较；Step 2：若最小块误差点在边缘四个点处，则以该点作为中心点保持步长不变，重新搜索十字形分布的五个点，若最小块误差点位于中心点则保持中心位置不变将步长减半构成十字形点群，在五个点处计算；Step 2：在中心及周围8个点处找出最

18、小块误差点若步长为1，该点所在位置即对应最佳运动矢量，算法结束，否则重复Step 2;图（5-3）图像块的运动方向区间六、模型求解6.1新三步搜索算法6.1.1算法的基本思想新三步搜索算法在第一步中通过搜索增加的中心8个点来修改搜索模板。同时使用半路中止技术来加速静止块的匹配，以此来减少搜索次数。新三步在第一步对搜索中心周围的八个点也同时作匹配运算，在很多情况下运算可以提前中止。与三步法的不同在于以下两点:（1） 改进了原有三步法第一步中搜索固定9个点的方法，采用了基于中心偏置的搜索模式。（2） 对静态子块或者准静态子块的搜索引入了中途停止的功能。6.1.2新三步搜索法算法新三步搜索法算法流程

19、如下:第一步:对搜索窗口中心的矩形框和的矩形框的17个点进行匹配运算。这17个点的位置如下图6-1图（6-1）NTSS算法第一步搜索点如果第一步搜索中最小像素点发生在搜索窗中心相邻的8个点，第二步的搜索模式有两种可能，其中白点是待搜索点，如图5-2图（6-2）NTSS算法第二步可能搜索点第二步:根据第一步得到的最小值的位置决定第二步匹配的位置：(1)如果在搜索窗口的中心位置得到最小的值，则停止搜索；(2)如果最小的值在3*3的矩形框上得到，则搜索以此点为中心位置的 3*3的窗口，并结束搜索；(3)如果最小的值在9*9的矩形框上得到，则搜索的步骤与早期三步法算法相同，搜索完成后跳到第三步。第三步

20、:以第二步得到的最佳匹配位置为中心，做最后的3*3窗口中九个点的匹配，得到最小值的位置，就是最佳的匹配位置。6.1.3新三步模板及搜索过程图示图（6-2）为算法的一个可能搜索过程的示意图。每个点上的数字表明了每个阶段搜索时计算的候选块的位置。图中点(1，-1)是第一个搜索阶段的点，也是第二个阶段的点，且位于搜索窗中心，故最终运动矢量为（1，-1）。图（6-3）NTSS算法搜索流程图6.2.1四步搜索法该算法类似于三步法，但它基于现实中序列图像的一个特征，即运动矢量都是中心分布的，从而在大5*5小的搜索窗口上构造了有9个检测点的搜索模板。算法首先采用5*5的搜索窗口，没有像算法使用9*9的搜索窗

21、，避免造成搜索方向的偏离，每一步的搜索范围由上一步的最佳匹配位置决定，并且将搜索窗的中心移向点处，前三步的搜索是定步长搜索，最后一步改变步长，得到最后的最佳匹配位置，且后两步搜索窗的大小依赖于点的位置。6.2.2四步搜索法算法四步搜索法算法流程如下:第一步：对在中心位置周围等步长的矩形5*5框上的九个点做匹配运算，如果得到的最小值在窗口的中心位置，则将搜索窗口改为3*3，转到第四步，否则执行第二步；第二步：搜索窗口的位置依照第一步的结果而定:(1)如果第一步得出的最小值在四个顶点上，则额外的5个位置需要做匹配运算；(2)如果第一步得出的最小值在四个边上，则额外的3个位置需要做匹配运算；(3)如

22、果第一步得出的最小匹配位置在窗口的中心位置，则直接转到第四步，否则执行第三步；第三步：与第二步的搜索过程相同，只是做完搜索后直接转到第四步；第四步：对3*3搜索矩形框的九个点做匹配运算，得出的最佳匹配位置就是最终的匹配位置。 图（6-4）四步搜索法的搜索模式6.2.3四步模板及搜索过程图（6-4）给出算法一种可能的搜索过程。黑色点是每一步的点。图中(0,2)是第一步的点，按照图（5-4）的搜索模式得到第二步的点(2,4)再按照图（6-4）的搜索模式得到第三步的点(2,4)，最后按照图（6-4）的搜索模式得到第四步的点(3,5)，即(3,5)是运动矢量。图（6-5）FSS算法搜索过程6.3.1菱

23、形搜索法在块匹配算法中，搜索模板的形状和大小不但影响整个算法的运行速度，而且也影响算法的搜索质量。由于实际视频中的误差函数曲面通常不是单调的，所以搜索窗口太小，就容易陷入局部最优，例如BBGDS，其搜索窗口仅为3*3而搜索窗口太大，又容易产生错误的搜索路径，例如TSS的第一步。另外，根据运动矢量的中心偏置分布特性，在进行运动估计时，最佳运动矢量通常在零矢量周围，如图5-6所示。图（6-6）菱形法中运动矢量的中心偏置分布规律6.3.2菱形搜索法算法菱形搜索法算法流程如下:第一步：初始化大菱形以搜索窗口的原点(0,0)为中心，测试的九个检测点。如果计算得到的点位于中心位置，则转到第三步;否则，转到

24、第二步。第二步：以上一次找到的点作为中心建构新的并计算其8个搜索点的匹配误差，找到新模板的点。若它位于模板中心，则转到第三步;否则重复第二步。第三步：以上一次得到的点作为中心建构小模板，在其5个搜索点处进行匹配计算和比较，找出点，该点所在位置即对应最终得到的运动矢量。6.3.3菱形模板及搜索过程图6-6给出算法一种可能的搜索过程。图中(2,0),(-3,1),(-4,2),(-4,2)分别是第一、二、三、四次搜索的点，然后按模式搜索(-4,2)周围的四个点，即可得到最后一步的点，从而得到运动矢量。图中黑色的点代表已搜索点，白色的点代表待搜索点。图（6-7）菱形法搜索过程6.4.1六边形搜索法块

25、匹配误差实际上是在搜索范围内建立的误差表面函数，全局最小点即对应着最佳运动矢量，而六边形搜索法实际上只是一个旋转了45度的正方形模板，其周围的9个点到中心点距离是不同的，因此使用六边形搜索法进行粗定位时，沿不同方向移动的匹配速度也是不同的，特别是在对角方向上的梯度下降不够快，需要较多步数才能够搜索到最优点。6.4.2六边形搜索法流程如下:第一步：用六边形模板在搜索区域中心及中心周围的6个点处进行匹配计算，若得到的点位于中心点上，则执行第二步，否则执行第一步。第二步：以上一次得到的点作为中心点，用新的六边形模板进行匹配计算，若得到的点位于中心点上，则执行第三步，否则重复执行第二步。如图（a）第三

26、步：以上一次得到的点作为中心点使用小六边形模板进行匹配计算，找到五个检测点中的点，该点就是所求的最佳匹配点，从而可以得到其对应的最佳运动矢量。如图（b） 图（a） 图(b)6.4.3六边形模板及搜索过程图(6-8)显示了一个用算法搜索运动矢量(-2,4)的例子，每个点上的数字表明了各搜索阶段计算的候选块的位置，黑色点是每一步的点。搜索共用4步，每一步的点分别为(1,2),(-2,4),(-2,4),(-2,4)，使用了三次和一次，总共搜索了17个点。图（6-8）六边形算法搜索过程七、模型优缺点7.1模型的优点（1）本文模型做了较为详细的介绍及研究，算法灵活，易于理解；（2）对于运动方向进行了具

27、体的预测，模型具有可靠性；（3）通过本文模型可以判断出实时拍摄的图像运动的方向；7.2模型的缺点（1） 模型介绍不够详细，对模型优点的研究不够深入；（2） 只考虑了单色成像的下单个因素的图像序列，没有对多种成像情况下所占的权重比进行综合的考虑；（3） 由于研究时间的有限，文中对运动估计算法，搜索算法的理解不够深刻；八、模型推广由于研究时间的有限，文中对运动估计算法还有待更深刻的理解，对搜索算法的研究还需要做进一步的研究:（1）文中的搜索算法是在块匹配的基础上进行研究的，搜索的精度理论上最高能达到1个像素的精度。实际的宏块中有可能运动矢量不是整数个像素单位，需要研究针对亚像素精度的搜索法；（2）

28、目前常采用PSNR值作为验证搜索法的搜索精度，由于峰值信噪比(PSNR)计算的复杂性，在实际的仿真测试中，存在着峰值信噪比（PSNR）计算精度不高的问题；同时，由于PSNR最终反映的是视频序列的整个编码性能，当存在部分宏块的搜索精度高而部分又很低时，平均的PSNR将趋于一致，无法确切反映算法的搜索精度。对搜索算法的精度的验证条件还需要做深入的理论和实际的研究；（3）由于块匹配法固有的缺陷，对物体边缘、纹理等区域的估计性能较差，今后的工作中可以将特征识别方法与块匹配法相结合，增强块匹配法对特征区域的搜索性能。九、参考文献1唐泽鹏，秦雷，朱秀昌等.运动估计算法分析.数字电视与数字视频.2001.1

29、4(10) 16192 J.R.Jian, A.K.Jian. Displacement Measurement and Its Application in Interframe Image Coding. IEEE Trans Common. Dec.1981.Vo1.COM-29. No.12:1799-18083 M.Ghanbari. The Cross-search Algorithm for Motion Estimation.IEEE Trans Common. Jul. 1990. Vo1.38. No.7:950-9534 R.Li, B.Zeng, M.L.Liu.A N

30、ew Three-step Search Algorithm for Block Motion Estimation.IEEE Trans Circuits System Video TechnoL Aug.1994.Vo1.4:438-4425 L.M Po, W.C.Ma.A Novel Four-step Search Algorithm for Fast Block Motion Estimation.IEEE Trans Circuit System Video Technol.Jun.1996.Vo1.6.No.3:313-3176刘海峰，郭宝龙.基于块匹配运动估计的菱形搜索算法.

31、计算机学报.2002.25(7):7477527 C.Zhu, X.Lin, L.P.Chan.Hexagon-Based Search Pattern for Fast Block Motion Estimation.IEEE Trans Circuits System Video Technole.May2002.Vo1.12.No.5:349-3558 C.H.Cheng, L.M.Po.A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimatial- on.IEEE Trans Circuits Syste

32、m Video Technol.Dec.2002.Vo1.12.No.12:1168一11779周俐俐，蔡国权.块运动估计的决速搜索算法探讨.数字视频.1999年.第12卷第4期.222410张旭东，卢国栋，冯健著.图像编码基础和小波压缩技术(原理、算法和标准).北京.清华大学出版社.2004.10212111林耀荣，韦岗.基于三角形分块的快速运动补偿算法.华南理工大学学报.1998. Vo1.26.No.2712王辉波，张春田.极低码率视频编码中块白适应分割运动估值.中国图像图形学报.1998.Vo1.3.No.613C.Zhu,X.Lin,L.P.Chan.An Optimized Dia

33、mond Search Algorithm for Block Motion Estimation.IEEE International Symposium on Circuits an Systems. 5.2002.Vo1.2.488-49114刘峰.视频图像编码技术及国际标准.北京邮电大学出版社.2005.789015刘海峰.运动估值快速块匹配算法的研究D西安:西安电子科技大学，2002.附录1. 主文件motionEstAnalysis.m % This script uses all the Motion Estimation algorithms written for the%

34、final project and save their results.close allclear all% imageName = 'caltrain.avi'VideoName = 'shaky_car.avi'video = VideoReader(VideoName); (VideoName);% movie(video);mbSize = 16;p = 7;for i = 1:6 imgINumber = i; imgPNumber = i; videoI = video(imgINumber); videoP = video(imgPNumber

35、); imgI = double(videoI.cdata); imgP = double(videoP.cdata); row col = size(imgI); % Exhaustive Search 基于块的全搜索算法 BlockCenter, motionVect, computations = motionEstES(imgP,imgI,mbSize,p); % P 帧当前重构图像 imgPComp = motionComp(imgI, motionVect, mbSize); % P 帧当前图像 和 P 帧当前重构图像的PSNR值 ESpsnr(i+1) = imgPSNR(img

36、P, imgPComp, 255); EScomputations(i+1) = computations; % P 帧当前重构误差图像 imagePDiff = imgP - imgPComp; if i = 4 figure; imageI = uint8(imgI); imageP = uint8(imgP); imagePComp = uint8(imgPComp); imagePDiff = uint8(imagePDiff); subplot(221);imshow(imageI); title('I 帧参考图像'); subplot(222);imshow(ima

37、geP); title('P 帧当前图像'); subplot(223);imshow(imagePComp); title('P 帧当前重构图像'); subplot(224);imshow(imagePDiff); title('P 帧当前重构误差图像'); % 画运动矢量图 figure; quiver( BlockCenter(2,:), BlockCenter(1,:), motionVect(2,:), motionVect(1,:), .2,'r'); axis(0 320 0 240); for i=mbSize:

38、mbSize:col-mbSize x = i,i; y = 0,row; line(x,y,'LineStyle','-','Marker','none'); end for j=mbSize:mbSize:row-mbSize x = 0,col; y = j,j; line(x,y,'LineStyle','-','Marker','none'); end xlabel('X'); ylabel('Y'); endend2. 文件

39、motionEstES.m% Computes motion vectors using exhaustive search method（全搜索法计算运动矢量）% Input% imgP : The image for which we want to find motion vectors（当前图像）% imgI : The reference image（参考图像）% mbSize : Size of the macroblock（宏块尺寸）% p : Search parameter (read literature to find what this means)（搜索参数）% Ou

40、put% motionVect : the motion vectors for each integral macroblock in imgP（当前图像中每一个积分宏块的运动矢量）% EScomputations: The average number of points searched for a macroblock（每个宏块搜索的平均点数）% Written by Aroh Barjatyafunction BlockCenter, motionVect, EScomputations = motionEstES(imgP, imgI, mbSize, p) % 定义函数文件mot

41、ionEstES.m，imgP、 imgI、 mbSize、 p为传入参数，BlockCenter、motionVect、 EScomputations为返回参数row col = size(imgI); % 将参考图像的行数赋值给row，列数赋值给colblockcenter = zeros(2,row*col/mbSize2);vectors = zeros(2,row*col/mbSize2); % 定义全0的矢量矩阵的大小costs = ones(2*p + 1, 2*p +1) * 65537; % 定义最小绝对差矩阵的大小computations = 0; % 搜索点数赋初值为0

42、% we start off from the top left of the image（从图像左上角开始）% we will walk in steps of mbSize（以宏块尺寸为步长）% for every marcoblock that we look at we will look for% a close match p pixels on the left, right, top and bottom of it （对于每一个宏块，在它的上下左右找到与搜索参数p最匹配的像素）mbCount = 1; %搜索的宏块数赋初值为1%1为循环起始值，mbSize为步长值，row-m

43、bSize+1为循环终止值for i = 1 : mbSize : row-mbSize+1 for j = 1 : mbSize : col-mbSize+1 % the exhaustive search starts here（全搜索开始） % we will evaluate cost for (2p + 1) blocks vertically % and (2p + 1) blocks horizontaly（我们将计算水平方向上(2p + 1)个块的最小绝对差和垂直方向上(2p + 1)个块的最小绝对差） % m is row(vertical) index（m为行指数） % n

44、 is col(horizontal) index（n为列指数） % this means we are scanning in raster order for m = -p : p %水平方向上位移矢量范围 for n = -p : p %垂直方向上位移矢量范围 % 补充下面程序 % row/Vert co-ordinate for ref block （参考块的行(垂直方向)的范围） refBlkVer = i+m; % col/Horizontal co-ordinate（参考块的列(水平方向)的范围） refBlkHor = j+n; %如果参考块的行列范围的任意一个在已经搜索过的宏

45、块之外，则继续下一步的搜索 if ( refBlkVer < 1 | refBlkVer+mbSize-1 > row . | refBlkHor < 1 | refBlkHor+mbSize-1 > col) continue; end costs(m+p+1,n+p+1) = costFuncMAD(imgP(i:i+mbSize-1,j:j+mbSize-1), . imgI(refBlkVer:refBlkVer+mbSize-1, refBlkHor:refBlkHor+mbSize-1), mbSize); % 搜索下一个点 computations = c

46、omputations + 1; end end % Now we find the vector where the cost is minimum % and store it . this is what will be passed back.（现在找到有最小绝对差的矢量并存储它，这就是将被返回的东西） % 补充下面程序 blockcenter(1,mbCount) = i+p; blockcenter(2,mbCount) = j+p; % finds which macroblock in imgI gave us min Cost（找到参考图像中最小绝对差的宏块） dx, dy,

47、 min = minCost(costs); % row co-ordinate for the vector（矢量的行集合） vectors(1,mbCount) = dx; % col co-ordinate for the vector（矢量的列集合） vectors(2,mbCount) = dy; %搜索下一个宏块 mbCount = mbCount + 1; costs = ones(2*p + 1, 2*p +1) * 65537; endendBlockCenter = blockcenter;motionVect = vectors; %返回当前图像中每一个积分宏块的运动矢量

48、EScomputations = computations/(mbCount - 1); %返回每个宏块搜索的平均点数 3. 文件costFuncMAD.m% Computes the Mean Absolute Difference (MAD) for the given two blocks（对给定的两个块计算最小绝对差）% Input% currentBlk : The block for which we are finding the MAD（当前块）% refBlk : the block w.r.t. which the MAD is being computed（参考块）% n

49、 : the side of the two square blocks% Output% cost : The MAD for the two blocks（两个块的最小绝对差）% Written by Aroh Barjatya% 定义函数文件costFuncMAD.m，currentBlk、refBlk、 n为传入参数，cost为返回参数function cost = costFuncMAD(currentBlk,refBlk, n) % 补充下面程序cost=sum(sum(abs(currentBlk-refBlk)/(n*n);4. 文件minCost.m% Finds the i

50、ndices of the cell that holds the minimum cost（找到拥有最小绝对差的点的指数）% Input% costs : The matrix that contains the estimation costs for a% macroblock（包含宏块的估计代价的矩阵）% Output% dx : the motion vector component in columns（列方向上运动矢量组成）% dy : the motion vector component in rows（行方向上运动矢量组成）% Written by Aroh Barjaty

51、afunction dx, dy, min = minCost(costs)row, col = size(costs);% we check whether the current value of costs is less then the already% present value in min.% If its inded smaller then we swap the min value with the current one and% note the indices.% （检测costs的当前值是否比已经出现的最小值小。如果小的话，我们将当前值与最小值对调，并注明指数）% 补充下面程序minnum=256;x=8;y=8;for i=1:row for j=1:col if(costs(i,j)<minnum) minnum=costs(i,j); x=i; y=j; end endenddx=x;dy=y;min=minnum;5. 文件motionComp.m% Computes