2022年2022年菱形搜索算法 .pdf

《2022年2022年菱形搜索算法 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年菱形搜索算法 .pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、毕 业 论 文（设 计） 2013届通信工程专业 0913071 班级题目菱形搜索运动估计算法研究及实现姓名学号指导教师职称二零一三年五月二十四日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 27 页 - - - - - - - - - I 内 容 提 要运动估计是视频压缩编码中的核心技术之一。采用运动估计和运动补偿技术可以消除视频信号的时间冗余，从而提高编码效率； 运动估计搜索算法是帧间编码的基础， 常用的运动估计搜索算法采用在搜索区域内搜索最佳绝对误差和（SAD ，

2、Sum of Absolute Differences）匹配点来进行宏块匹配， 获得宏块的运动矢量。 不同的搜索方法在搜索最佳 SAD 点上采用不同的搜索策略。 常见的快速搜索算法有三步法、新三步法、四步法、块梯度下降法以及菱形搜索算法等，本文主要研究菱形搜索运动估计算法并实现， 首先阐述了课题的背景与意义和运动估计的研究现状， 其次详细介绍了运动估计的原理以及典型块运动估计算法，分析它们的技术特点，然后重点介绍了菱形搜索算法，并在Visual C+ 6.0环境下编写程序代码将之实现，最后进行仿真得出实验结果。关 键 词视频压缩 ; 运动估计 ; 块匹配 ; 菱形搜索名师资料总结 - - -精

3、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 27 页 - - - - - - - - - II The Realization Of Diamond Searching Motion Estimation Algorithm Author: Tutor: Abstract Motion estimation is the video compression coding technology of the core. Using motion estimation and motion com

4、pensation techniques can eliminate temporal redundancy of the video signal, thereby improving the encoding efficiency; motion estimation search algorithm based on inter-coded, the common motion estimation search algorithm of the search area to search the best absolute error and SAD (Sum of Absolute

5、Differences) matching points to the macro block matching motion vector of the macro block obtained. Different search method searches for the best SAD point different search strategies. Common fast search algorithm has three steps, the new three-step method, four-step, block gradient descent and diam

6、ond search algorithm, etc. This paper studies the diamond search motion estimation algorithm and implementation, first describes the background and significance of the subject and motion estimation research status, followed by details of the motion estimation principle and the typical block motion e

7、stimation algorithm to analyze their technical characteristics, and then focuses on the diamond search algorithm, and the Visual C + + 6.0 environment to prepare the program code of the implementation, and finally the simulation The experimental results obtained. Keywords Video Compression Motion Es

8、timation Block Matching Diamond Search名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 27 页 - - - - - - - - - III 目录内容提要 . 错误！未定义书签。Abstract . II目录 . III第一章 绪论 . 1 1.1 课题的背景与意义. 1 1.2 运动估计的研究现状. 2 1.3 本文的主要内容及工作安排. 3 第二章 运动估计 . 5 2.1 运动估计原理 . 5 2.2 典型块运动估计算法分析. 6

9、 2.2.1 全搜索算法（ FS ） . 6 2.2.2 快速搜索算法 . 7 第三章 菱形搜索算法的实现. 错误！未定义书签。3.1 菱形搜索算法 . 错误！未定义书签。3.1.1 算法分析 . 错误！未定义书签。3.1.2 算法的基本思想. 错误！未定义书签。3.1.3 算法描述 . 错误！未定义书签。3.2 菱形搜索的核心代码. 错误！未定义书签。第四章 仿真分析 . 错误！未定义书签。4.1 仿真实验结果 . 错误！未定义书签。4.2 实验结果分析 . 错误！未定义书签。第五章 结果与展望 . 错误！未定义书签。致谢 . 错误！未定义书签。参考资料 . 错误！未定义书签。名师资料总结

10、- - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 27 页 - - - - - - - - - 1 菱形搜索运动估计算法研究及实现第一章绪论1.1 课题的背景与意义随着信息技术的发展和社会的不断进步，人类对信息的需求越来越丰富，人们希望无论何时何地都能够方便、快捷、灵活的通过语音、数据、图像与视频等多种方式进行通信。视觉信息给人们直观生动的形象，图像/ 视频的传输更受到广泛的关注。数字信号处理技术、物理媒体与网络技术、 超大规模集成电路技术突飞猛进的发展，使得多媒体通信研究成为研究应用的

11、热点。其中，最为关键的技术是数字视频的处理与传输技术， 它将电视技术、 计算机技术和通信技术结合在一起，在电视系统，计算机网络和通信产业中得到了广泛的应用，已经进入千家万户的生活中。数字视频硬件方面的进步和数字视频压缩国际标准的推出，使得数字视频技术领域趋于成熟。 在图像通信领域， 新的多媒体通信方式的不断出现，尤其是Internet和数字移动通信的迅速普及，利用IP网络以及宽带无线网络进行图像和视频信息的传输成为备受人们重视的新方式。 但是大量频繁的图像、 视频信息的交流与存贮活动也带来了许多新要求和新问题， 视频通信比其他类型的信息传输要占用更多的带宽资源。例如，帧速率为30 帧每秒、图像

12、大小为1920*1080、每个像素采用 24 为伪彩来存放亮度和色度分量的高清电视，则该数字视频要求带宽为：1920*1080*24*30=1423.83Mbps=1.3Gbps 数字视频信息的数据量是非常巨大的，若不经过压缩， 数字图像传输所需要的高传输速率与数字图像存储所需要的巨大容量将成为推广应用数字视频技术的最大障碍。虽然视频图像的数据量大， 但是名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 27 页 - - - - - - - - - 2 图像序列以及图像内部

13、数据具有高度相关性，存在大量信息冗余。 因此，虽然数字化的视频图像是非常大，仍然可以通过消除冗余实现图像/ 视频的压缩。这些冗余主要包括：信息熵冗余、时间冗余、结构冗余、知识冗余、 空间冗余等形式。视频图像压缩编码就是要用量少的比特数来表征图像 / 视频信息，同时又要保证图像的质量。运动估计是视频压缩系统中的一个重要组成部分，其效率主要体现在图像质量、 压缩码率和搜索速度 ( 复杂度 )三个方面。其基本原理是利用视频图像序列中相邻帧之间存在的时间相关性，建立序列相邻帧之间表达上的相互关系， 从而减少时间冗余， 提高视频压缩编码的效率。运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补

14、偿编码所需位数越少，比特率越小。运动估计速度越快，越有利于实时应用。因此，提高图像质量，加快估计速度，减小比特率是运动估计算法研究的目标。 当前来提高算法效率。 常用的方法主要是通过确定初始搜索点、选取合适的匹配准则及运动搜索策略。运动估计首先通过对物体位移的估计得到运动矢量，然后对前一帧进行运动补偿，这样就使得预测帧更接近本帧。因此，运动估计算法对运动补偿的性能具有重要影响。通过运动估计算法提高运动矢量的准确性，对减少预测误差、信息传输量，提高系统的码率压缩比具有重要作用。 运动估计的这些特点可有效减少时间相关性，针对视频序列图像在时间轴上具有较强的相关性特点，运动估计技术被广泛应用于各种视

15、频压缩编码方案中， 已经成为视频序列图像编码系统实现的重要技术。1.2 运动估计的研究现状运动估计算法通常分为两类：一类是像素递归算法PRA(Pixel recursive Algorithm);另一类是块匹配算法BMA （Block Matching Algorithm ）.PRA是基于递归思想，如果连续帧中像素数据的变化是因为物体的移位引起的， 算法就会沿着梯度方向对某个像素周围的若名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 27 页 - - - - - - -

16、- - 3 干像素做迭代运算， 使连续的运算最后收敛于一个固定的运动估计矢量， 从而预测该像素的位移； 而 BMA 则是基于当前帧中一定大小的块，在当前帧的前后帧的一定区域内搜索该像素块的最佳匹配快，作为它的预测快。尽管 PRA对比较复杂的运动形式来说， 其预测精度要高于BMA ，但是由于其计算量比BMA 大的多，同时 BMA 本身也拥有较好的性能，因此目前视频压缩编码国际标准普遍都采用BMA 。菱形搜索属于块匹配的运动估计算法， 因此，本文的研究都是针对块匹配的运动估计。运动估计和运动补偿是现阶段视频压缩编码的关键技术。运动估计目前面临的主要问题就是如何比较快速的得到比较准确的运动矢量，因为

17、在整个视频编码的过程中，即使采用快速算法，运动估计仍然是耗时最长、 资源占用最高的环节。 高效快速的运动估计算法一直是视频压缩编码领域的研究热点。常见的快速搜索算法有三步法、新三步法、四步法、 块梯形下降法以及菱形搜索算法，目前的各种搜索算法都存在搜索速度和精度相矛盾的问题，同时在特定的视频序列中，搜索精度和搜索速度都有提升的空间。1.3 本文的主要内容及工作安排第一章 绪论。通过查阅大量的相关文献介绍了课题的背景与研究的重要性。 简要介绍了现今运动估计的研究现状，并叙述了本文的主要内容和课题安排第二章 运动估计。介绍了运动估计的原理以及几种常见搜索算法运动估计。第三章 菱形搜索算法运动估计的

18、设计及实现。第四章系统仿真。介绍了本文提出的菱形搜索运动估计算法的系统仿真实验结果。 通过对实验结果中数据列表的分析实现预期的研究目标。第五章总结。总结全文的研究成果。并对运动估计算法研究进名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 27 页 - - - - - - - - - 4 行了展望，提出了进一步的研究工作。第二章运动估计名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

19、- - - - 第 8 页，共 27 页 - - - - - - - - - 5 由于视频序列图像在时间上具有较强的相关性，运动估计及运动补偿技术可以有效的减少时间相关性，因此该技术被广泛应用于各种视频压缩编码方案中。 运动估计用来估计物体的位移，得到运动矢量；运动补偿根据得到运动矢量，对前一帧中由于运动而产生的位移进行调整，从而得到尽可能接近本帧的预测帧，由此可见，运动估计算法越完善，估计出的矢量越准确，运动补偿的性能就越好，从而使预测误差越小， 编码后需要传输的信息量也将随之大大减少，整个系统的压缩效率就会的到很大的提高，因此运动估计和补偿技术已经成为视频序列图像编码系统中减少时间冗余、提

20、高压缩比的重要性。2.1 运动估计原理运动估计是视频编码和视频处理中广泛使用的一种技术。是视频编码系统的关键部分，同时也是整个视频编码器中计算量最大的部分。运动估计性能的优劣直接影响到整个视频编码器的运行效率和整个视频序列的重构质量。运动估计是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块。在帧间预测编码中，由于活动图像邻近帧中的景物存在着一定的相关性。因此，可将活动

21、图像分成若干块或宏块， 并设法搜索出每个块或宏块在邻近帧图像中的位置， 并得出两者之间的空间位置的相对偏移量，得到的相对偏移量就是通常所指的运动矢量，得到运动矢量的过程被称为运动估计。运动矢量和经过运动匹配后得到的预测误差共同发送到解码端，在解码端按照运动矢量指明的位置，从已经解码的邻近参考帧图像中找到相应的块或宏块， 和预测误差相加后就得到了块或宏块在当前帧中的位置。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 27 页 - - - - - - - - - 6 2.2

22、 典型块运动估计算法分析常见的块运动估计算法有全搜索法、三步法、新三步法、四步法块梯度下降法及菱形搜索法， 其算法的基本思想及描述分别如下文所述。2.2.1 全搜索算法（ FS）（1）全搜索算法分析全搜索算法（ Full Search Method,FS）是所有运动估计算法中最简单、最原始的块匹配算法， 它对整个搜索窗口的每一个点进行块匹配运算，所以单从块匹配的角度看，全搜索是最好的匹配方法。但它的计算量很大， 需要计算的点数多， 它在整个视频压缩编码过程中占有大部分的运算量， 限制了在需要实时压缩场合的应用，所以实时视频压缩编码实现很大程度上取决于运动估计算法的优化。（2）算法的基本思想 F

23、S算法是一种搜索策略最简单的搜索算法。它对M N 搜索范围内所有可能的候选位置计算SAD （i,j）值，从中找出最小SAD值，其对应偏移量即为所求运动矢量。（3）算法的描述第一步 : 从（0,0 ）点出发，按某种搜索路径由近及远，逐个像素点计算 SAD值，直到遍历搜索窗内所有的点；第二步 : 在所有的SAD 中找到最小块误差（Minimum Block Distortion,MBD）点，该点即为最佳匹配点。2.2.2 快速搜索算法 1 三步搜索法（1）算法分析名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

24、- - - - - 第 10 页，共 27 页 - - - - - - - - - 7 三步搜索算法（ TSS,Three-Step Search ）是一种由粗到精的搜索算法，快速而且高效。它通过三步搜索，逐步减小搜索步长。每次搜索都是以上一步的搜索结果为中心，进行周围步长为33 像素搜索。由于简单，性能良好等特点， 为人们所重视。 最大搜索长度为7，搜索精度取一个像素，则步长为4、2、1，共需三步即可满足要求，因此而得名三步法。 TSS是较早的搜索速度和搜索精度两者取得比较适当折中的快速搜索算法，因其搜索步骤简单固定且易于硬件实现，已经在很多视频压缩系统中的到了应用。针对一个 1616 的像

25、素子块， TSS算法共搜索 25 个点，而 FS要进行 1515=225 个点的搜索，运算时间明显减少。它还是简单容易实现、每个块的搜索点数相同的优点。但它有个致命的缺点：第一步过于粗糙，在搜索范围较大是（如16 或者更大），初始步长相对于块的运动矢量估计来说就太大了，跳出了运动矢量存在可能性较大的区域，导致搜索方向的不确定性，因此很容易陷入局部最优。（2）算法的基本思想三步搜索算法采用一种有粗到细的搜索模式，从搜索窗口中心开始，按一定步长取周围8 个点作匹配运算， 文中采用的初始搜索步长为 4，得到 MBD 点后，每次利用上一步搜索得到的最佳匹配位置作为当前搜索的中心位置，没做一步，搜索步长

26、减半，直至搜索结束。（3）算法描述第一步：以窗口中心（ 0,0 ）为中心搜索点，步长为4，包括周围的 8 个像素点，计算 SAD值各点得到一个 MBD 点，共搜索 9 个点。第二步：以上一步的最佳匹配点中心，步长为2，继续搜索周围 8个像素点，计算各点SAD值得到 MBD 点，共搜索 8 个点。第三步：同上一步，只是步长减小1，最后得到的MBD点就是需要的运动估计的点，从而得到运动矢量。为了克服 TSS的上述缺点， 1994年出现了新三步搜索法 （NTSS ）,该算法利用视频运动矢量的中心偏置分布特点，加强搜索中心区域，名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

27、- - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 27 页 - - - - - - - - - 8 因此搜索精度有一定程度的提高。另外，NTSS引入“中途退出”的思想，虽然比较粗糙，但为以后的快速算法提出了一种新的策略。2 新三步搜索法（1）算法分析传统的快速搜索算法如三步法等属于多级搜索的第一步，搜索点是固定的，这些点在搜索窗内的位置， 由于假定全局极值点位置出现的概率在搜索窗内均匀分布， 所以也是均匀固定分布的， 这种搜索模式对于某些仅有细微运动的块来说，并非准确。因此如何在搜索第一步时优化设计搜索模式非常重要。 这种优化与全局极值点的概率

28、分布密切相关。因此，我们需要考虑视频序列的全局极值点的概率分布特征。Renxiang Li等在三步算法的基础上做一些改进得到了新三步搜索（New Three-Step Search,NTSS) 算法。三步算法由于其简单高效和数据存取的规律性受到普遍欢迎，但三步算法对现实视频序列的中心偏置特性欠缺考虑。NTSS算法在这方面做了改进，从而获得比三步算法更好的性能。 (2) 算法的基本思想在现实的视频序列中，运动矢量的分布是具有中心偏置特性的，为验证此特性， NTSS算法在第一步中通过搜索增加的中心8 个点来修改搜索模块，同时NTSS使用半路终止技术来增加静止块的匹配，从此来减少搜索次数。三步算法在

29、第一步对九个点做匹配运算，这九个点在搜索窗口中是等间距分配的， 没有考虑块的中心偏置， 新三步在第一步对搜索中心周围的八个点也同时做匹配运算，在很多运算情况下可以提前终止。 NTSS 算法与三步法的不同在于以下两点：改进了原有三步法第一步中搜索固定9 个点的方法，采用了中心名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 27 页 - - - - - - - - - 9 偏置的搜索模式。对静态子块或者准静态子块的搜索引入了中途停止的功能。（3）算法描述第一步：对搜索窗口中

30、心99 的矩形框和 33 的矩形框 17 个点进行匹配运算。 17个点的位置如图 2.1 所示图 2.1 NTSS 算法第一步搜索点如果第一步搜索中最小SAD 像素点发生在搜索窗中心相邻的8个点，第二步的搜索模式有两种可能，其中白点是待搜索点，如图2.2所示：图 2.2 NTSS 算法第二步搜索点第二步根据第一步得到最小SAD值得位置决定第二步匹配的位置：（1）如果在搜索窗口的中心位置得到最小的SAD值，则停止搜索；（2）如果最小的 SAD值在 33 的矩形框上得到，则搜索一此点为中心位置的 33 的窗口，并结束搜索；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

31、 - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 27 页 - - - - - - - - - 10 （3）如果最小的SAD值在 99 的矩形框上得到，则搜索的步骤与TSS算法相同，搜索完成后跳到第三步。第三步：以第二步得到的最佳匹配位置为中心，做最后的33 窗口中九个点的匹配，得到最小SAD值得位置，就是最佳匹配位置。由于运动矢量通常总是高度集中分布在搜索窗的中心位置附近，因此 NTSS采用基于中心偏置的搜索模式不仅提高了匹配速度，也减少了陷入局部最优的可能性； 而采用中止判别技术则大大降低了搜搜复杂度，提高搜索效率。NTSS针对 TSS搜索算

32、法中第一步搜索步长过大而容易陷入局部最优的缺陷进行了改进，新增 8 个搜索点用来保证缓慢运动的要求，第一步大的步长有可以满足快速运动的要求。我们一搜索范围为（ -7，7）搜索窗口大小为 1515 为例说明这种算法的性能。 NTSS 算法在最好的情况下只需做17 个点的匹配，最坏的情况下需要做33 个点的匹配，由于运动矢量的中心偏置特性在现实视频序列中是普遍存在的，在通常情况下，NTSS算法需要做 33点匹配的概率比较小，因此，在低速率视频应用中，如视频电话或视频会议中， NTSS 算法的优点可以得到较好的发挥。3 四步搜索法（1）算法分析新三步搜索算法考虑了块矢量中心偏移的特性，在初步搜索时对

33、中心周围的位置同时做了匹配运算。在物体做小范围运动时， 这种改进很有效，可以大大减少运算量，然而，在物体做大范围运动时，这种改进却带来了额外的运算量。现实的情况经常是物体既有小范围的偏移，也有大范围的运动。因此，在考虑块匹配算法时，既要照顾块的中心偏移特性，也要兼顾块的大范围运动。四步搜索（Four-Step Search,FSS）能够兼顾良好种情况，可以的到较好的性能。（2）算法的基本思想该算法类似于三步法，但它基于现实中序列图像的一个特征，即名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

34、 - 第 14 页，共 27 页 - - - - - - - - - 11 运动矢量都是中心分布的，从而在55 大小的搜索窗口上构造了有九个检测点的搜索模板，FSS算法首先采用55 的搜索窗口，没有像 TSS算法使用 99 的搜索窗，避免造成搜索方向的偏离，每一步的搜索范围由上一步的最佳匹配位置决定，并且将搜索窗的中心移向MBD 点处，前三部的搜索是定步长搜索，最后一次改变步长，得到最后的最佳匹配位置，且后两步搜索窗的大小依赖于MBD 点的位置。（3）算法描述 FSS 算法流程如下：第一步：对在中心位置周围等步长的55 矩形框上九个点做匹配运算，如果得到最小SAD值在窗口的中心位置，则将搜索窗

35、口改为33 ，转到第四步，否则执行第二步；图 2.3 第二步：搜索窗口的位置依照第一步的结果而定：（1）如果第一步得出的最小SAD值在四个顶点上，则额外的5 个位置需要做匹配运算，如图2.3（b）的情况；（2）如果第一步得出的最小SAD值在四个边上，则额外的3 个位置需要做匹配运算，如图2.3（c）的情况 ; （3）如果第一步得出的最小SAD 匹配位置在窗口的中心位置，则直名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 27 页 - - - - - - - - - 12

36、 接转到第四步，否则执行第三步；第三步：与第二步的搜索过程相同， 只是做完搜索后直接转到第四步。第四步：对 33 搜索矩形框的九个点做匹配运算，得出的最佳匹配位置就是最终的匹配位置。4 基于块的梯度下降搜索法（BBGDS ）基 于 块 的 梯 度 下 降 法 （ Block-Based Gradient Descent Search,BBGDS ）利用运动矢量中心分布特性，第一步使用33 的正方形模板搜索窗对9 个点进行搜索。 在第二步中， 若 MBD 点在搜索窗中心，则算法结束；否则以上一步MBD 点为中心，重复第一步。视频帧内相邻像素间具有渐变性，每一步的MBD点分布具有一定的方向性，也即

37、梯度下降方向来决定下一步的搜索方向。在每一步搜索过程中，使用了中心匹配块而不是匹配点，降低了局部最优的可能性。 引入梯度下降的概念， 用梯度下降的方向来指导搜索方向，对该方向进行重点搜索， 从而减少和避免了不必要的搜索，大大降低了算法的复杂度。第三章菱形搜索算法的实现3.1 菱形搜索算法菱形搜索法（ DS ，Diamond Search) 采用两种搜索模板：大菱形名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 27 页 - - - - - - - - - 13 搜索模板

38、 LDSP （Large Diamond Search Patten）和小菱形搜索模板SDSP （Small Diamond Search Patten ） 。搜索模板的形状和大小是决定整个算法运行速度及性能的关键所在。统计数据表明， 视频图像中进行运动估计时，最优点通常是零矢量的周围，如图3.1所示，以搜索窗口中心为圆心，两像素为半径的圆内。图3.1 中的13个点便是圆内所有可能的检测点。图3.1 菱形法中运动矢量的中心偏置分布规律3.1.1 算法分析DS 算法是一种高效的运动估计方法，它分析了视频图像中运动矢量的基本规律，选用了大小两种形状的搜索模板LDSP 和SDSP 。先用LDSP 搜

39、索，搜索范围广，可以进行粗定位，搜索过程不会陷于局部最小；当粗定位结束后，可以认为最优点就在LDSP 周围8个点的菱形区此外，DS 搜索时各步骤之间有很强的相关性，模板移动时只需在几个新的检测点处进行匹配计算，所以也提高了搜索速度。3.1.2 算法的基本思想根据实验数据统计表明, 利用全搜索算法计算获得的运动向量分布概率和距离搜索中心点的距离之间的关系可以看出, 50% 至90%的运动向量集中在以搜索中心为圆心的半径为2的圆上 , 如图 3.1 所名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -

40、- - 第 17 页，共 27 页 - - - - - - - - - 14 示，根据实际视频序列物体运动的统计, 实际视频中块的运动可以在任何方向上进行运动, 但主要集中在水平和垂直两个方向上( 摄像机运动)。所以图 3.1 中在半径为 2的圆中的 13个搜索点是具有最优匹配概率最大的点。所以在该圆形区域内进行搜索, 搜索匹配的点数最小而能获得最佳的搜索效果。基于上述理论, 菱形搜索算法被提出。为了使得搜索范围为以搜索中心为原点的圆, 菱形搜索算法采用了两个搜索模式 , 如图3.2所示。一个模式称为大菱形搜索模式( LDSP) ，采用9 个搜索点 , 包括搜索中心 , 以及8个按照菱形分布的

41、围绕点。第二个模式成为小菱形搜索模式( SDSP), 采用搜索中心和与其相邻的水平垂直方向上的 4个点共5 个点组成小菱形。DS 搜索算法的搜索过程首先以搜索中心为中心, 进行大菱形搜索, 计算9个点, 如果最小 MAD 的点不在大菱形的中心的话, 将大菱形中心移到相应最小 MAD 的点上 , 重复大菱形搜索 , 直到最小 MAD 的点位于大菱形的中心为止。然后在该中心点上切换到小菱形搜索, 共搜索 5 个点得到最终的搜索结果作为运动估计的最优匹配点。图3.2 LDSP 模板与 SDSP 模板3.1.3 算法描述 Step1:用LDSP 在搜索区域中心及周围八个点出进行匹配计算，若MBD 位于

42、中心点，则进行 Step3；否则进行 Step2。 Step2：以Step1找到MBD 点作为中心点，用新的LDSP 来计算，若名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 27 页 - - - - - - - - - 15 MBD 位于中心点，则进行 Step3；否则重复 Step2。 Step3：以Step1找到MBD 点作为中心点，将 LDSP 换为SDSP ，在五个点处计算，找出 MBD 点，该点所在位置及对应最佳运动矢量。 DS 算法的优势在于它把握了视频序

43、列中运动矢量的基本规律，所以它的性能优于其他算法。但DS 只是一种搜索策略上的折中处理，其性能的缺陷表现在： 不论是大运动图像序列， 还是保持静止的图像序列， DS 算法同等地对待搜索区域的各个部分，而且都要经历从大模板到小模板的搜索过程，至少要对13 个搜索点进行计算，这样造成了较大的搜索冗余，影响了算法的搜索速度。因此，DS 算法有待改进。3.2 菱形搜索的核心代码基于3.1 节对菱形搜索算法的描述，设计编写程序，其核心代码为： void search_DS(const int x,const int y,const int heigth,const int width) const in

44、t ox=x*BLOCK_HEIGTH,oy=y*BLOCK_WIDTH; const int LDS92=0,0,0,2,-1,1,-2,0,-1,-1,0,-2,1,-1,2,0,1,1; const int SDS52=0,0,0,1,-1,0,0,-1,1,0; uint32 sad=0 xffffff; MV mv=0,0;int mvx,mvy; PATTERN_SEARCH(LDS,9,1) PATTERN_SEARCH(SDS,5,0) frame_info.mvxy=mv; frame_info.sadxy=sad; frame_info.frame_sad+=sad; vo

45、id main() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 27 页 - - - - - - - - - 16 int num; if(fp_cur = fopen(news_cif.yuv,rb)=NULL) return; if(fp_ref = fopen(news_cif.yuv.enc,rb)=NULL) return; frame_info.sum_pot=frame_info.sum_sad=frame_info.sum_sse=0; frame_

46、info.mv=_mv_buffer0;frame_info.prev_mv=_mv_buffer1; printf(frametcosttpsnrn); for(num=0;num15;num+) int i,j; fseek(fp_cur,XX*YY*3/2*(num+1),SEEK_SET); if(fread(current_frame0,XX*YY,1,fp_cur)=0)break; fseek(fp_ref,XX*YY*3/2*(num+0),SEEK_SET); if(fread( ref_frame0,XX*YY,1,fp_ref)=0)break; frame_info.f

47、rame_pot=frame_info.frame_sad=frame_info.frame_sse=0; for( i=0;iX;i+) for( j=0;jY;j+) memset(_flag_search,0,SEARCH_RANGE*SEARCH_RANGE); search_DS(i,j,BLOCK_HEIGTH,BLOCK_WIDTH); rebuilt(i,j,BLOCK_HEIGTH,BLOCK_WIDTH); frame_info.sum_pot+=frame_info.frame_pot; frame_info.sum_sad+=frame_info.frame_sad;

48、frame_info.sum_sse+=frame_info.frame_sse; MV (*mv_tmp)Y=frame_info.mv;frame_info.mv=frame_info.prev_mv;frame_info.prev_mv=mv_tmp; memcpy(frame_info.prev_sad,frame_info.sad,X*Y*sizeof(uint32); printf(%dt%.2ft%.2fn,num,(float)frame_info.frame_pot/X/Y,10*log10(XX*YY*255*255.0/frame_info.frame_sse); pri

49、ntf(nAvg:t%.2ft%.2fn,(float)frame_info.sum_pot/X/Y/num,10*log10(XX*YY*255*255.0*num/frame_info.sum_sse); fclose(fp_cur);fclose(fp_ref) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 27 页 - - - - - - - - - 17 第四章仿真分析仿真实验在Visual C+6 0 的环境下进行，仿真视频序列为3个 CIF（ Commo

50、n intermediate format ）标 准 测 试序 列hall 、m other-daughter、news的前 15 帧。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 27 页 - - - - - - - - - 18 仿真实验时，在测试过程中，运动估计的宏块大小为1616，搜索范围为 1515，即7个像素点。测试序列中每帧图像的大小为352288。最佳搜索点采用最小SAD匹配准则。用 cost 表示平均每块的搜索点数，psnr 表示匹配之后的图像与原始