H264概念解析-运动搜索算法

运动搜索匹配准则：
块匹配就是判断块相似程度，匹配准则的好坏直接影响运动估计的精度。另一方面运算复杂度、数据读取复杂度和内存管理复杂度都很大程度上受到块匹配准则的影响。
例如：平均绝对误差函数(Mean of Absolute Error, MAE)
绝对差和SAD 只采用加法和绝对值计算，便于计算和硬件实现而且匹配精度和MAD相差不大。
主要的搜索算法有：
三步法(TSS),二维对数法(TDL),新三步法(NTSS), 四步法(FSS),基于菱形的搜索算法(DS), 基于六边形的搜索算法(HEXBS)等
一、Full Search
全搜索算法最简单暴力，对搜索范围内的所有可能的位置计算两个块的匹配误差，最小匹配误差对应的MV一定为全局最优的MV。

第一步：将搜索窗口的中心点作为搜索的起始点，从起始点开始依照顺时针方向逐点向外搜索，计算每一个搜索点的SAD(最小差值和)值。
第二步：比较第一步中左右点的SAD值，选取SAD最小的点作为最佳匹配点。
二、Fast Full Search
仅仅是全局搜索算法的一种优化实现。由于运动搜索时候有多种块类型(16x16,8x16,4x4),全局搜索时会因为位置重叠产生同一处的像素残差多次计算情况，可以选择一次将搜索范围内的所有像素点的像素残差计算出来，不同块类型只需要把残差进行组合即得到该类型的SAD

 三、三步搜索算法

第一步：从搜索窗口的一半或者一半多一点开始搜索，在每一步长的搜索中，比较搜索区域正方形的中心点和四周八个搜索点，计算九个点的SAD值，选择SAD值最小的点作为下一次搜索的中心点。
第二步：以第一步得到的点为中心，搜索步长减半，进行相似的搜索，再得到一个最佳匹配点。在第三次搜索的时就可以找到最佳匹配位置。
四、四步搜索算法

主要针对TSS(三步搜索搜索算法)第一步步长很大时，容易得到局部最优点。四步搜索算法主要针对该问题，基于运动矢量是中心分布的图像特征来实现的。
第一步：FSS四步搜索算法也是方形范围内的九个搜索点，但是搜索范围是5x5的搜索窗口上，小的步长避免错过最佳搜索点。九个点中SAD最小的点最优下一次搜索的中心。
第二步: 搜索窗口仍为5x5，以第一步结果为中心点，继续九点搜索，如果两次搜索的中心点重合，则减小步长，改为3x3进行第三步，如果不在中心点，则继续第二步搜索。
第三步：搜索窗口改为3x3，对中心点四周的8个点进行计算，选取SAD最小的点作为最优点。
五、菱形搜索算法
又称钻石搜索，存在大菱形和小菱形两种不同的匹配模板。大菱形是9点搜索，小菱形是5点搜索。先使用大菱形搜索模板粗搜索，然后使用小菱形模板细搜索。

第一步：以搜索窗中心点为中心，菱形模板，计算中心点和周围8个点共9个点的SAD，得到SAD最小的点。
第二步：如果第一步得到的最佳点刚好是中心点，则跳到第三步使用小菱形搜索模板，否则仍旧回到第一步搜索。
第三步：利用小菱形5点搜索，选取SAD值最小的点为最佳匹配点。
六、分级搜索算法
又称为金字塔式搜索，中心思想是现在下采样域搜索，逐级提高到上采样域搜索。以期在保证搜索准确性的同时，减少计算量。