Classic Three-Step Search Method in Motion Estimation

The Classic Three-Step Search (TSS) algorithm is a widely adopted block matching technique in motion estimation, primarily used for video compression and inter-frame prediction. Its core concept involves progressively narrowing the search range to rapidly locate the optimal matching block with reduced computational cost.

Algorithm Step-by-Step Analysis Initial Step Search Centered on the current block, the algorithm selects 8 uniformly distributed candidate points within the search window using the maximum step size (typically 7 pixels). Together with the center point, these 9 positions undergo matching cost calculation using metrics like Sum of Absolute Differences (SAD) or Mean Square Error (MSE). In code implementation, this typically involves nested loops comparing macroblock pixel values.

Dynamic Step Reduction The point with the minimum matching error from the previous step becomes the new center, while the step size is halved (e.g., 7→4→2). The 8-point search pattern repeats with exponentially shrinking search range. Programmers often implement this using recursive functions or while loops with step size as the termination condition.

Local Refinement The final step employs 1-pixel step size for precise motion vector determination within the minimal neighborhood. Through three iterations, computational complexity reduces from O(n²) for full search to O(log n). The algorithm typically returns coordinates of the best-matched block and corresponding motion vector.

Performance Key Metrics Speed Advantage: Compared to full search algorithms, TSS reduces computational load by over 85% Accuracy Trade-off: Achieves near-full-search accuracy for low-motion sequences but may miss global optimum in high-motion scenarios Application Scenarios: Real-time encoding systems, hardware-constrained environments

Although subsequently improved by algorithms like Diamond Search, TSS's hierarchical approach remains foundational in motion estimation. Practical deployment requires adjusting initial step size and termination thresholds based on video dynamic range, often implemented through configuration parameters in video codec libraries.