全搜索运动估计算法

资 源 简 介

全搜索运动估计算法

详 情 说 明

全搜索运动估计算法

全搜索（Full Search）是运动估计中最基础的算法，主要用于视频编码中的帧间预测。其核心思想是对参考帧中所有可能的候选块进行穷举搜索，找出与当前块最匹配的位置。

算法流程分为三个步骤：首先在当前帧划分固定大小的宏块（如16x16像素），然后在参考帧的搜索范围内（通常±15像素）逐像素位移，计算每个位置与当前块的匹配误差（常用SAD或MSE作为代价函数），最终选择误差最小的位移向量作为运动矢量。

该算法虽然能获得全局最优解，但计算复杂度极高。当搜索范围为±W像素时，每个宏块需要计算(2W+1)²次匹配运算，导致实时编码面临巨大挑战。

三步法快速搜索算法

三步搜索（Three-Step Search, TSS）是针对全搜索的优化方案，通过分层采样大幅降低计算量。其核心策略是通过三次逐步细化的搜索完成运动估计：

第一步在最大搜索范围内以4像素为步长选取9个检测点（3x3网格），确定最佳匹配区域。第二步将步长减半，在上一步最优点的邻域内进行5点搜索。第三步以1像素步长进行最终精细定位。相比全搜索，三步法将计算量从O(W²)降至O(logW)级别，在保持较高精度的同时提升约8-10倍速度。

两种算法各有优劣：全搜索适合对精度要求极高的离线处理场景，而三步搜索更适用于实时视频编码系统。实际工程中常采用菱形搜索、六边形搜索等改进算法来平衡效率与精度。