H.264 Motion Estimation Algorithm
An engineering-focused explanation of H.264 motion estimation methods, including diamond search, hexagon search, UMH, and fractional-pel refinement.
Motion estimation (ME) in inter prediction searches for the reference block that minimizes a distortion-cost objective for the current macroblock. The selected displacement is encoded as the motion vector (MV). Motion compensation then reconstructs a predictor from the selected reference location and forms the residual signal.
From an implementation perspective, ME is commonly the dominant contributor to encoder runtime, often accounting for 60% to 80% of total complexity. Therefore, ME algorithm design is fundamentally a rate-distortion-complexity tradeoff problem rather than a purely geometric search problem.
In H.264/AVC, practical pipelines separate ME into two stages: integer-pel search for coarse localization, followed by fractional-pel refinement for predictor accuracy. This article focuses on widely used fast integer search families: DIA, HEX, and UMH.
Notation
- MV: Motion vector.
- MVP: Motion vector predictor.
- MVD: Motion vector difference, typically MV - MVP.
- SATD: Sum of absolute transformed differences, usually measured in the Hadamard domain.
- SSD / SSE: Sum of squared differences/errors.
- MAD / MAE: Mean absolute difference/error.
- MSD / MSE: Mean squared difference/error.
Integer-Pel Motion Estimation
Diamond Search (DIA)
Diamond search uses two templates: the Large Diamond Search Pattern (LDSP) for iterative descent and the Small Diamond Search Pattern (SDSP) for local convergence. The algorithm iteratively recenters on the minimum-cost candidate until the minimum is located at the template center.
- Initialize the search center and evaluate the LDSP candidates.
- Select the minimum-cost candidate under the chosen metric.
- If the minimum is off-center, recenter and repeat LDSP.
- Once center-minimum is reached, switch to SDSP for final local refinement.
Engineering note: neighboring diamond iterations share overlapping candidates. Caching or pruning duplicated points yields direct compute savings with no impact on search outcome.
Hexagon Search (HEX)
Hexagon search extends the step size with a radius-2 hexagonal template for faster traversal under larger displacements, then applies radius-1 local refinement with a small diamond or square. The control flow is similar to DIA but with improved efficiency for medium-motion fields.
Adjacent hexagon placements overlap by multiple points. Optimized implementations, for example x264, evaluate only the incremental non-overlapping candidates in each step, reducing arithmetic and memory traffic.
Uneven Multi-Hexagon Grid Search (UMH)
UMH is a hybrid strategy combining cross search, multi-hexagon grid expansion, iterative hexagon refinement, and terminal local search. Its objective is robustness under complex, non-local, or predictor-misaligned motion while retaining practical runtime bounds.
In production encoders, UMH behavior is often conditioned by predictor reliability, block partition type, local SAD landscape, and neighboring MVs. Adaptive pattern sizing and early termination are the primary levers for quality-speed tuning.
Fractional-Pel Motion Estimation
After integer-pel localization, H.264/AVC refines vectors at half-pel and quarter-pel precision. Intermediate luma samples are synthesized through normative interpolation filters, and candidate costs are re-evaluated in the sub-pixel domain.
Fractional refinement typically improves prediction fidelity and bitrate efficiency, but increases computational intensity. Practical designs bound this overhead via staged search depth, mode-aware pruning, and early stop criteria.