Motion search patterns
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.
For this block:
- At a vector of −3, 2 the diamond stopped at 0, 2 after 11 positions, with a cost of 6,292. The lowest cost in range is 838, at the vector that was set. From where the diamond stood, no neighbor one pixel away was better.
- The hexagon found it with 21 positions; Exhaustive computes all 289. Its longer step carried it across the stretch where the diamond stalled.
- Over all 169 vectors the sliders allow, the diamond missed the lowest cost 78 times and the hexagon 19. They tested 17.1 and 22.6 positions on average. These are 169 shifts of one invented picture, not a measure of how often x264 misses.
- Neither is safe from every start. Both follow the slope they can see. A better starting point can change the result; this experiment holds the start at zero. x264 tests predicted vectors before its main search.
The patterns in x264
--me | Pattern | Preset |
|---|---|---|
dia | Diamond, radius 1 | ultrafast, superfast |
hex | Hexagon, radius 2 | veryfast to slow |
umh | Uneven multi-hexagon | slower, veryslow |
esa | Exhaustive | none |
tesa | Exhaustive, transformed | placebo |
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
- A pattern can stop at a position that is only locally best. Flat areas and repeating texture are where that happens. A missed match is not fatal: the block is coded with a larger residual or another mode.
- The lowest difference is not always the best vector. A vector far from the one predicted for the block costs more bits to code, and x264 adds that cost during the search.
- Search cost multiplies. It is paid for every partition size and every reference frame an encoder tries, so a slower pattern costs most where many references and small partitions are also on.
Sources
Read 2026-11-15, at the commit linked.
- x264 at commit c24e06c (GitHub mirror): in
encoder/me.c, the diamond with its four positions, the hexagon with its six offsets and the square refinement, the uneven multi-hexagon, the two exhaustive searches with successive elimination and the four stages of the transformed search (its short list is half the range), the predicted vectors tested first, the vector cost taken relative to the predicted vector and the range; incommon/base.c, the default pattern, the default range, the presets ultrafast, superfast, slower, veryslow, placebo, the range of 24,--meand--merange; inencoder/encoder.c, the range capped at 16 for the diamond and the hexagon and the transformed search replaced by the plain one at--subme0 and 1 and in lossless coding; the five names; the options in the command-line list. - Not checked: the stages of the uneven multi-hexagon search, beyond their place in the code; how x264 gathers its candidate vectors, and the table of vector costs itself; whether the transformed search's short list ever leaves out the lowest transformed cost; sub-pixel refinement; motion search in x265, libaom and SVT-AV1; how often each pattern misses on real video.