encoding.info
You are hereSourcePredictionTransformEntropy codingFiltersFramesDecisionsRate controlPerceptionQualityBitstreamSettingsEncoder map
Page 5 of 7 in Decisions

Motion search patterns

Decisions · concept · added 2026-11-15

In Brief:
A full search compares every allowed position to find the lowest matching cost. A search pattern tests fewer positions and follows improvements from a starting guess. It can save many comparisons, and it may stop before it reaches the lowest cost in the window.

Motion estimation looks for the place in a reference frame that matches a block at the lowest cost. Testing every position in range finds the lowest cost among them and takes the most comparisons. A search pattern tests a few positions, moves toward the best, and repeats. It takes far fewer comparisons, and it can stop before it reaches the lowest cost.

Follow a pattern across the cost map

The two sliders set the vector from a 16×16 block of the current frame to its matching position in the reference. A vector of −3, 2 means the match lies three pixels left and two down in the reference; the cat's movement from the reference to the current frame is the opposite. The search starts from the zero vector. The cost of a position is the sum of absolute differences between the block and the reference there. The Cost map shows that cost for every vector within 8 pixels: lighter is lower, the middle cell is the zero vector. Dots are the positions the pattern tested, the line joins the positions it moved through, the ring is where it stopped, and the dashed coral square is the lowest cost in range. Diamond tests the four neighbors one pixel away and steps to the best, until none is better or it has taken 16 steps. Hexagon does the same with six positions two pixels away, for up to 8 steps, then checks the eight neighbors of where it stopped. Exhaustive computes the cost at every position in the window. Positions tested counts the distinct positions a search visited. It is not a timing: the page computes the whole map either way, to draw it.

-3
← look 6 pixels leftlook 6 pixels right →
2
← look 6 pixels uplook 6 pixels down →
Block
Reference
Cost map
teal: what the pattern tested and where it stopped dashed coral: the lowest cost in range
Positions tested
Vector found
Cost found
Lowest in range
Simplified demo: the cat is invented, the reference is the cat coded as an intra frame at quantization parameter 28, and the current frame is the source cat moved by whole pixels, opposite to the vector set. The diamond and hexagon have the geometry and the round limits (16 and 8) of x264's code for a range of 16; the positions counted are this script's, and x264's hexagon loop avoids repeated positions in its own way. Different from x264: the cost here is the sum of absolute differences alone, where x264 adds the cost of coding the vector; the search starts at zero, where x264 starts from predicted vectors; positions are limited to a window of 8 pixels each way, a separate limit from the rounds; and no sub-pixel refinement follows. Vectors are across, down, in pixels, and point from the current block to the reference.

For this block:

The patterns in x264

--mePatternPreset
diaDiamond, radius 1ultrafast, superfast
hexHexagon, radius 2veryfast to slow
umhUneven multi-hexagonslower, veryslow
esaExhaustivenone
tesaExhaustive, transformedplacebo

hex is the default, and the last column names the presets that use each pattern. The two exhaustive modes search the whole window but reject and screen positions on the way; the demo's Exhaustive computes a cost at every one.

The other patterns, the range and what follows

umh is a longer sequence of cross, square and hexagon stages before the same final refinement; it is not in the demo. For esa and tesa the window is set by --merange, 16 pixels by default and 24 in veryslow and placebo. esa uses a bound that rejects positions without computing their full sum of absolute differences. tesa screens further: it keeps a short list of the positions with the lowest sums and computes the transformed cost for those only. The cost the demo computes is a sum of absolute differences. Some pruning is safe because a bound proves a candidate cannot win; the rest is a judgment.

For dia and hex, --merange sets how many rounds they may take, and x264 caps it at 16 for them. Unless --subme is 0, the integer search is followed by sub-pixel refinement, which Sub-pixel interpolation covers.

Trade-offs

Sources

Read 2026-11-15, at the commit linked.