运动估计中的经典三步搜索法

资 源 简 介

运动估计中的经典三步搜索法

详 情 说 明

经典三步搜索法（Three-Step Search，TSS）是运动估计中广泛使用的块匹配算法，主要用于视频压缩和帧间预测。其核心思想是通过逐步缩小搜索范围，以较低计算代价快速定位最佳匹配块。

算法逻辑分步解析 初始步长搜索 以当前块为中心，按最大步长（通常为7像素）在搜索窗内选取8个均匀分布的候选点，加上中心点共9个位置进行匹配度计算（如SAD或MSE）。

动态缩小步长 选择上一步中匹配误差最小的点作为新中心，将步长减半（如7→4→2），重复8点搜索模式。此时搜索范围呈指数级收缩。

局部精细定位 最后一步采用1像素步长，在最小邻域内精确确定最优运动矢量。通过三次迭代即可将计算复杂度从全搜索的O(n²)降至O(log n)。

实验效果关键指标 速度优势：相比全搜索算法，三步搜索可减少85%以上的计算量 精度权衡：对低速运动序列匹配效果接近全搜索，高速运动时可能错过全局最优 适用场景：实时编码系统、硬件资源受限环境

该算法虽被后续菱形搜索等改进，但其分层思想仍是运动估计领域的奠基性设计。实际部署时需根据视频动态范围调整初始步长和终止阈值。