毕业论文设计_基于快匹配的人群运动估计(编辑修改稿)

毕业论文设计_基于快匹配的人群运动估计(编辑修改稿)内容摘要：

对程序各模块一一实现； 第 5 章：算法的验证和评价。 对算法进行测试，对结果进行分析； 第 6 章：结论。 本章对全文工作以及毕业收获进行总结，指出了还需改进的地方。 四川大学本科毕业论文 基于块匹配的人群运动估计 6 2 块匹配算法介绍及分析 本章主要介绍块匹配算法的各个模块，及各模块所用到的算法。 运动估计 运动估计已发展得较为成熟，最常用于人群监控与视频压缩编码。 基于块的运动估计和补偿是视频编码中最通用的算法。 它把图像域分割成互相不重叠的称为块的小区域，并且假定每一个块内的运动都可以用一个简单的参数模型特征化，如果快足够小，那么这种模型是相当合理 的。 目前这种方法被广泛用于视频标准变换运动补偿滤波和采用基于块的运动补偿进行的数字视频压缩 [11~12]。 在一幅幅复杂的人群图像中，如果依靠每个步行者的个体信息来估计人群总体的运动，必须要分离出每个个体的运动。 但要做到这点并不容易，因为在开放的空间中，一个步行者可能向各个方向移动，且步行者的身体各部分的移动方式也各不相同，进而，当人群密度较大，个体之间有相互遮挡时，这就变得更加困难，甚至是不可能的。 因此，本文提出基于块匹配的人群运动估计（ BMA）。 这种方法由于实现较简单且容易而受到广泛关注。 BMA 并不 借助人群中个体的信息，而是通过统计视频中各宏块的运动矢量估计出人群整体的运动 [13]。 块匹配基本思想 基于块匹配法的运动估计的基本思想就是将当前帧分成互不重叠的大小为 MN 的宏块 (一般情况下 M==N)，然后对当前帧中的每一个块都在参考帧中的一定区域，即搜索窗口内，按照一定的匹配准则搜索与之具有最小匹配误差的块 (Minimal DistortionBlock，MDB)，该块即为当前块的匹配块，由匹配块与当前块的相应位置计算出运动位移，所得运动位移即为当前块的运动矢量。 并且假定每一个块内的运动只做 相等的平移同时可以用一个简单的参数模型特征化。 如果块足够小，那么这种模型是相当合理的。 匹配块与当前块之间的坐标位移就是运动矢量，匹配块与当前块的对应象素点逐个做差就的到差值块。 基于这样的方法这样，当前帧中的每一个块都可以用一个差值块和一个运动矢量来表示，对当前帧的编码就转化为对每一块的差值块和运动矢量的编码。 块匹配的原理如图 21。 运动估计算法的整体效率主要体现在初始搜索点的选择、匹配准则和运动搜索策略三个方面。 本程序主要用基于块的运动方式开发出的运动估计算法——块匹配算法。 块匹配算法由于它具有较少的硬件 复杂度，容易在超大规模集成电路中实现，因此被认为是最通用的算法。 四川大学本科毕业论文 基于块匹配的人群运动估计 7 图 21 块匹配原理图 为了提高图像质量，加快估计速度是运动估计算法的研究目标 之一。 通常是通过研究初始搜索点的选择、匹配准则和运动搜索策略等来提高算法效率的 [13]。 初始搜索点的选择 (1)直接选择参考帧对应块的中心位置。 这种方法简单，但容易陷入局部最优点。 如果采用的算法初始步长太大，而原点 (以下均指待搜索块的中心点在参考帧中的相同位置的对应点，而不是坐标位置的 真正原点 )又不是最优点，有可能使快速搜索跳出原人群的运动估计点周围的区域 (这些区域可能包含最优点 )而去搜索远距离的点，导致搜索方向的不确定性，这就有可能陷入局部最优。 (2)选择预测的起点。 由于相邻块之间和相邻帧之间具有很强的相关性，因而许多算法都利用这种相关性先对初始搜索点进行预测，以预测点作为搜索起点。 大量实验证明预测点越靠近最优匹配点，越会使得搜索次数减少。 下面举例说明几种常见的预测方法。 方法 1:基于 SAD(the Sum of Absolute Differences)值的起点预测方法。 分别求出 当前块与其相邻块间的 SAD 值，然后选取 SAD 最小的块的运动矢量作为预测值。 这种方法预测精度高，但计算 SAD 值的时间开销大。 改进的方法是利用运动矢量的相关性来预测起点。 方法 2:利用相邻块和相邻帧对应块的运动矢量来预测当前块的搜索起点。 序列图像的运动矢量在空间、时间上具有很强的相关性。 由于保存前一帧运动矢量信息在解码端需要占用大量内存，使得系统复杂化，故大多算法仅考虑同帧块的空间相关性来预测运动。 比较典型的是 ―平均预测 ‖，在 中使用三个相邻块的运动矢量的中值作为当前块的运动矢量的预测值。 方法 3:基于 相邻运动矢量相等的起点预测方法。 如果当前块的各相邻块的运动矢量相等，则以其作为当前块运动矢量的预测值。 否则，使用方法 1 求出当前块与其相邻块间的SAD 值，然后选取 SAD 值最小的块作为预测起点。 这种方法在保证精度的基础上利用运动矢量相关性从而大大减少了计算量。 四川大学本科毕业论文 基于块匹配的人群运动估计 8 运动估计的复杂度主要取决于匹配计算量和所采用的搜索算法这两个方面 [14]。 在下一节中将介绍在运动估计常用的一些匹配准则。 块匹配准则 运动估计算法中常用的匹配准则有三种，即最小绝对值差 (MAD)、最小均方误差 (MSE)和归一化互相关函数 (NCCF)，它们分别定义如下 : (1) 最小绝对值差 : （ 1） 式中， B 代表 MN 宏块， (dx,dy)为运动矢量， fk 与 fk1 分别为当前帧和前一帧的灰度值，若在某一个点 (x， y)处 MAD(dx,dy)达到最小，则该点为要找的最优匹配点。 若在某一个点 (x,y)处 MAD(dx,dy)达到最小，则该点为要找的最优匹配点。 (2)最小均方误差 : （ 2） 能够使 MSE 值最小的点为最优匹配点。 (3)归一化互相关函数： （ 3） 式中 NCCF 的最大值点为最优匹配点。 在运动估计中，匹配准则对匹配的精度影响不是很大，由于 MAD 准则不需要作乘法运算，实现简单、方便，所以使用最 多，通常使用 ASD 代替 MAD。 SAD 即求和绝对误差，其定义如下 : （ 4） 搜索策略 搜索策论选择恰当与否对运动估计的准确性，运动估计的速度有很大的影响。 有关搜索策略的研究主要是解决运动估计中存在的计算复杂度和搜索精度这一矛盾。 如四川大学本科毕业论文 基于块匹配的人群运动估计 9 全搜索法，它对搜索范围内的每一个像素点进行块匹配运算以得到一个最优的运动矢量。 不过，较大的搜索窗通常会使得搜索点增多，从而加 大计算量，因此，搜索距离的设定需综合考虑具体视频的运动特性、运动估计的质量以及算法的计算量等因素，以获得最佳的估计性能 [15]。 另外三步法、二维对数法、交叉法等主要是通过限制搜索位置的数目来减少计算量。 这以后的许多搜多策略都是为了平衡搜索精度与计算速度而产生的。 典型的块匹配算法 在 MPEG24 视频编码算法中，运动估计 (ME)的计算量占整个编码计算量的 2/3 以上 [16]。 在视频编码系统中，运动估计处理消耗近 50%的功耗 [16]。 为了减小运动估计计算量 ，出现了各种块匹配算法，它们只是搜索策略各有不同 ，其中搜索精度最高的是全搜索法，但由于计算复杂度高，不宜于实时应用，为此人们提出了各种改进的快速算法。 下面介绍几种常用的经典算法。 (l)全搜索法 (FS， Full Seacrh method) ① 算法思想 :全搜索法也称为穷尽搜索法，或螺旋向外搜索法，是对搜索范围内所有可能的候选位置计算其 SAD(i， j)值，从中找出最小 SAD，其对应偏移量即为所求运动矢量。 此算法计算量虽大，但最简单，可靠，找到一定是全局的最优点。 ② 算法描述 : Setpl:从原点出发，按顺时针方向由近及远，在每个像素处计算 SAD 值，直到遍 历搜索范围内的所有点。 StPe2:在所有的 SAD 中找到最小块误差 (MBD)点 (即 SAD 最小值的点 )，该点所在位置即对应的最佳运动矢量。 ③ 模板及搜索过程图示 :如图 22 所示。 图 22 全搜索法搜索过程 四川大学本科毕业论文 基于块匹配的人群运动估计 10 ④ 算法分析 :FS 算法是最简单、最原始的块匹配算法，由于可靠，且能够得到全局最优的结果，通常是其它算法性能比较的标准，但它的计算量很大，这就限制了在需要实时性较强的场合的应用，所以有必要进一步研究其它快速算法。 (2)二维对数法 (TDL， TwoDimensional Logarithmic) 二维对数搜索法由 和 提出，它开创了快速算法的先例，分多个阶段搜索，逐次减小搜索范围直到不能再小时结束。 ① 基本思想 :二维对数搜索法是由原点开始，以 ―十 ‖字形分布的五个点构成每次搜索的点群，通过快速搜索跟踪加 MBD 点。 ② 算法描述 : Step 1:从原点开始，选取一定的步长，在以 ―十 ‖字形分布的五个点处进行块匹配计算并比较。 Step 2:若 MBD 点在边缘四个点处，则以该点做为中心点，保持步长不变，重新搜索 ―十 ‖字形分布的五个点。 若为 MBD 点位于中心点，则保持中心点位置不变，将步长减半，构成 ―十 ‖字形点群，在五个点处计算。 Step 3::若步长为 1，在中心及周围 8 个点处找出 MBD 点，该点所在位置即对应最佳运动矢量，算法结束。 否则，重复 Step 2。 ③ 搜索过程图示 :如图 23 所示。 ④ 算法分析 :TDL 算法搜索时，最大搜索点数为 2+7lbW，这里 W 表示最大偏移量max(dxmax,dymax)。 若发现新的 ―十 ‖字形点群的中心点位于搜索区域的边缘，则步长也减半。 后来有人提出应该在搜索的每个阶段都将步长减半。 所有这些改 动都是为了使算法搜索范围很快变小，提高收敛速度。 TDL 算法的前提是假设搜索区域内只有一个极小值点，如果搜索区域内存在多个极小值点时，该方法找到的可能是局部最小点。 不能保证找到全局最优点也正是大部分快速搜索算法的缺点。 图 23 二维对数法过程 (3)三步搜索法 (TSS，而 Three Step Search) 四川大学本科毕业论文 基于块匹配的人群运动估计 11 三步搜索法与 TDL 类似，由于其简单、健壮、性能良好的特点，已被人们所重视。 若最大搜索长度为 7，搜索精 度取 1 个像素，则步长为 1，共需要三步即可满足。 ① 基本思想 :TSS 算法的基本思想是采用一种由粗到细的搜索模式，从原点开始，按一定步长取周围 8 个点构成每次搜索的点群，然后进行匹配运算，跟踪最小块误差MBD 点。 . ② 算法描述 : Step 1:从原点开始，选取最大搜索长度的一半为步长，在中心点及周围 8 个点处进行块匹配计算并比较。 Step 2:将步长减半，中心移到上一步的 MBD 点，重新在中心点及周围的 8 个点处进行块匹配计算并比较。 Step 3:在中心点及周围 8 个点处找出加 MBD 点，若步长为 1，该点所在位 置即对应最佳运动矢量，算法结束。 否则，重复 Step 2。 ③ 搜索过程图示 :一个可能的搜索过程如图 24 所示。 图 24 中点 [+4， +4]、 [+6，+4]是第一、第二步的最小块误差点。 第三步得到最终运动矢量为 [+7， +5]，每个点上的数字表明了每个阶段搜索时计算的候选块的位置。 图 24 三步搜索法搜索过程 ④ 算法分析 :TSS 算法搜索时，整个过程采用了统一的搜索模板，使得第一步的步长过大，容易引起误导，因此对小运动模式的效率较低。 最大搜索点数为 1+8blW，当搜索范围大于 7 时，仅用三步是不够的，搜索步数的一般表达式为 lb(dmax+1). (4)交叉法 (CSA， Cross Search Algorithm) 1990 年， Chanbari 提出了交叉搜索算法，它也是在 TDL 和 TSS 基础上为进一步减小计算量而发展起来的快速搜索法。 本思想 :CSA 是从原点开始，以。