铁路监控视频的运动估计技术研究(7)
3.2.1 全搜索法
(1）算法思想
全搜索法（Exhaustive Search, ES）也称为穷尽搜索法，是运动估计算法中最简单最基本的块匹配算法，它通过对当前帧中所有像素点的搜索来获得最佳匹配点的运动矢量的。对 搜索范围内所有可能的候选位置计算 值，从中找出最小MSE，对应位移量即是所求的运动矢量。该算法虽然计算量大，但最简单、可靠，找到的匹配点为最优点。
（2）算法描述
图3.1全搜索法
全搜索法是逐个像素都计算出MSE值，直到每个搜索范围内的像素点都被搜索。全搜索法比较常用的是光栅扫描顺序和螺旋扫描顺序。搜索的顺序可分为两种，第一种的搜索的起始位置在搜索窗的中心，然后逐步向外发散的顺序，由内到外逐点计算MSE。第二种的搜索的起始位置在搜索窗的左上角，然后按照顺序计算搜索窗内每一个点的MSE。
(3)算法分析
全搜索算法是最简单、最原始的块匹配算法，由于遍历搜索所有点，所以能够得到全局最优的结果，通常是其他算法性能比较的标准，但它的计算量很大，这就限制了在需要压缩场合的应用，所以其他快速算法的研究得以进一步发展。
3.2.2 三步搜索法
三步搜索法（TSS）[11]是最早的一种尝试块匹配，可追溯到20世纪80年代中期。目前，TSS应用比较广泛，它从搜索窗口的中心位置（0，0）开始搜索，并且以“0”来标记，最大的运动位移是 7个像素。
(1）基本思想
开始，它在与搜索位置中心设置的步长为S=4，一个普通的搜索参数值是p=7。然后，它在八个像素点搜索 是像素点周围像素（0,0）的。从这九个像素点搜查，使其搜索来源给予最少的成本。然后，它设置新的步骤大小 ，并重复了两个更多的迭代，直到 。在这一点上找到了用最少成本函数的位置，宏块在该位置最匹配块，计算得出的运动矢量。
(2)算法描述
图3.2TSS搜索法
Step 1: 以“0”为中心，步长为4,寻找 4的范围内的8个标记，标记是“1”和“0”的点，按测评准则函数，从这9个像素中找出具有最小MSE或者最小均方绝对差的点，这个点就是最佳匹配像素点。
Step 2: 以Step 1中的最佳匹配像素点，选择步长为2，寻找 的范围内的8个标记，标记为“2”的点，方法与Step 1相似，根据准则函数，找到了最佳匹配像素点。
Step 3: 选择步长为1，在Step 2的最佳匹配点，寻找范围在 的点，得到最佳匹配像素点，这个点就是TSS的结果。
(3)算法分析
三步搜索算法搜索时，整个过程采用了统一的搜索模板，由于第一步的步长过大容易引起误导，因此对小运动模式的效率较低，当搜索范围大于7时，仅用三步是不够的。总体说，三步法是一种较典型的快速搜索算法，后来又相继出现了许多改进的新三步法，改善了它在小运动模式下的估计性能。
3.2.3 新三步骤算法
由于三步骤搜索法第一步的搜索步长相对较大，可能会误导搜索方向，影响最终的搜索结果，从而陷入局部最优，所以为了改进三步搜索法在小运动估计方面的效果，提出了新三步骤搜索法。
(1）基本思想
新三步搜索法（NTSS）考虑到了运动矢量分布的一个基本特征：实际视频序列中物体的运动通常变化都是缓慢的。新三步骤搜索法在第一步中采用了具有中心偏置性的模版，而且对那些静止或准静止块应用了提前中止策略。
下一篇：单片机智能家电控制中心系统设计