Motion Search Method

[IRMA1024]

can someone explain me what's different on ME method on x264
-diamond search
-hexagonal search
-uneven multi-hexagon
-exhaustive search
??

is it true that

/\
/\/\ this is 4 elements of diamond search?
\/\/
\/

/-\
| | this is 1 element of hexagon??
\_/


so diamond search will have 4 edges each element, but hexagon wil have 8 elements (each edge represent direction of search) ?

is this on x264 only? how about xvid and another codec

[sysKin]

Diamond is just four direct neighbours:
|
— —
|
Hexagon, like the name suggests, has SIX directions, not eight:
\ /
— —
/ \

Square, used in XviD (with motion precision 6) has eight:
\ | /
— —
/ | \

Hopefully this helps.

[akupenguin]

Diamond. The previous best known position is shown as "0", and the positions to try next as "1".
1
101
1
Hexagon. The "1"s pattern is iterated; the "2"s pattern is run only once after the "1"s have terminated (i.e. once an iteration finds none of the "1"s to be any better than the "0").
1 1
222
12021
222
1 1
Uneven multihexagon has 3 different search patterns that it runs once each, and then switches to the same pattern as hexagon. I have superimposed the patterns below; they aren't necessarily centered on the same location.
3



3 3 3


3 3
3 3 3
1
3 3 3 3
1
3 3 3 3 3
3 3 1 3 3
3 3 22222 3 3
3 22122 3
31 131 131 13121012131 131 131 13
3 22122 3
3 3 22222 3 3
3 3 1 3 3
3 3 3 3 3
1
3 3 3 3
1
3 3 3
3 3


3 3 3



3
Exhaustive.
...
111111111111111111111111
111111111111111111111111
111111111111111111111111
111111111111111111111111
111111111111111111111111
111111111111111111111111
111111111111111111111111
...111111111111011111111111...
111111111111111111111111
111111111111111111111111
111111111111111111111111
111111111111111111111111
111111111111111111111111
111111111111111111111111
111111111111111111111111
...

[Sirber]

Good post!

[IRMA1024]

wow thanks for the explanation...

by the way the exaustive search looking for every pixel in each loop... does it give significant result?

[superdump]

Exhaustive searching is intended to find the upper bound as every position is checked. It is far too slow for any reasonable use other than this.

[IRMA1024]

then finding upper bound is for what?

[skal]

IRMA1024: the upper bound is for knowing how much you've traded from speed to accuracy/quality.
-Skal

[IRMA1024]

it is 2^10 not 2^9... thanks

[skal]

oops...my bad
-Skal (<="bendova, Junior")

[foxyshadis]

That uneven hexagon is pretty. =D

I still haven't done tests comparing uneven multi to standard hex; since it still goes fast enough, I just use it. One of these days I'd like to see an exhaustive matrix of qual vs. speed tradeoff of the many options, though x264 is probably still enough in flux that it would be outdated within a few months.

[Isochroma]

I use exhaustive motion search on all my encodes! Even if it yields only a few percent extra quality while decreasing encoding speed significantly, it doesn't matter...

The time is unimportant because it takes me 14 days to finish hand-editing 35,089 anime frame, so encoding is only a very small proportion (no more than 5%) of the time anyway.

So, thanks for providing ESA mode - and do keep it in future releases, as I know there are those who use it and will continue to do so.

And big thanks go out to the developers of x264, without whom I would not have this world-class video compression tool!

[Kostarum Rex Persia]

Isochroma,post some images of your video,and explain what settings you used for compression.

[Sirber]

hand edit?

[DeathTheSheep]

Isochroma, that's pretty cool...hand editing.
Yeah, I also use ME exhaustive range 64 when I'm at a fast computer and my source is less than 30 minutes in length. It's fun to watch it go soooo..... sloooooow... and then suddendly to go at 100fps in no-motion scenes! :p

[LigH]

Here are some additional images, based on my limited understanding of different sources (^#3, papers, slides...) of motion search algorithms, some e.g. used in x264 and x265 as well; no guarantee for a correct representation, correction remarks are welcome in case of a misunderstanding.

Exhaustive search: a waste of time {complexity should be O(n²) ?}, only for comparison with more efficient algorithms if they are possibly less precise

one step (http://www.ligh.de/pics/MotionSearch/MVPred_exh.png): Every pixel distance in a square neighborhood (here displayed with a maximum range of 8×8, will probably often be more)


Diamond search: small direct neighborhood, only suitable for littlest expected motion changes

one step (http://www.ligh.de/pics/MotionSearch/MVPred_dia.png): 1 adjacent pixel in each orthogonal direction


Square search: small complete neighborhood, only suitable for littlest expected motion changes

one step (http://www.ligh.de/pics/MotionSearch/MVPred_sqr.png): 1 adjacent pixel in each direction


Hexagonal search: 2-step search in a slightly larger range, assuming more probable vertical directions

step 1 (http://www.ligh.de/pics/MotionSearch/MVPred_hex1.png): ~2 pixel (approx. Euclidean) distance in 6 directions
step 2 (http://www.ligh.de/pics/MotionSearch/MVPred_hex2.png) – continuous motion, good hit: additional square refinement
step 2 (http://www.ligh.de/pics/MotionSearch/MVPred_hex2o.png) – changing motion, offset: additional square refinement


Star-shaped search: Large diamond shape with additional satellite samples in the first step, good for expected mainly orthogonal motion

step 1 (http://www.ligh.de/pics/MotionSearch/MVPred_star1.png): 2 pixel "Manhattan" distance in 8 directions + 5 pixel distance in orthogonal directions
step 2 (http://www.ligh.de/pics/MotionSearch/MVPred_star2.png) – continuous motion, good hit: additional "Small Diamond" refinement, 1 pixel orthogonal distance
step(s) 2 (http://www.ligh.de/pics/MotionSearch/MVPred_star2o.png) – changing motion, offset: additional recursive search with "Large Diamond" range, 2 pixel "Manhattan" distance
step(s) 3 (http://www.ligh.de/pics/MotionSearch/MVPred_star3o.png) – changing motion, offset: additional recursive "Small Diamond" refinement, 1 pixel orthogonal distance


Successive Elimination Algorithm (SEA): Logarithmic square search (effectively as good as exhaustive); here with only 3 steps in a reduced 7×7 range {complexity should be O(ld(n)) ?}:

step 1 (http://www.ligh.de/pics/MotionSearch/MVPred_sea1.png): 4 pixel square distance
step 2 (http://www.ligh.de/pics/MotionSearch/MVPred_sea2.png) – continuous motion, good hit: additional 2 pixel square distance refinement
step 3 (http://www.ligh.de/pics/MotionSearch/MVPred_sea3.png) – continuous motion, good hit: additional 1 pixel square distance refinement
step 2 (http://www.ligh.de/pics/MotionSearch/MVPred_sea2o.png) – changing motion, offset: additional 2 pixel square distance refinement
step 3 (http://www.ligh.de/pics/MotionSearch/MVPred_sea3o.png) – changing motion, offset: additional 1 pixel square distance refinement


Uneven Multi Hexagonal search (UMH): 3-step search in a larger range, purposefully suitable for expected wide and probably random motion, but generally elaborate

step 1 (http://www.ligh.de/pics/MotionSearch/MVPred_umh1.png): ~4+8+12 pixel (approx. Euclidean) distance in 16 directions (vertically more dense)
step 2 (http://www.ligh.de/pics/MotionSearch/MVPred_umh2.png) – continuous motion, good hit: additional hexagonal 2 pixel refinement
step 3 (http://www.ligh.de/pics/MotionSearch/MVPred_umh3.png) – continuous motion, good hit: additional diamond refinement
step(s) 2 (http://www.ligh.de/pics/MotionSearch/MVPred_umh2o.png) – changing motion, offset: additional recursive search with hexagonal 2 pixel distance
step(s) 3 (http://www.ligh.de/pics/MotionSearch/MVPred_umh3o.png) – changing motion, offset: additional recursive "Small Diamond" refinement, 1 pixel orthogonal distance


CC-BY

[Groucho2004]

Last post was in 2005, Ligh, you're a necromancer. :rolleyes:

[LigH]

I know. :o – Still, I believe it's the best place.

[aymanalz]

I know. :o – Still, I believe it's the best place.

Thanks for the explanatory post. So in your understanding, which method gives the highest quality among the last three? Star, SEA or UMH?

[LigH]

That's the wrong question, IMHO. All three are able to find the optimal motion vector – even if it is rather distant from a previous estimation (due to recursive search steps to continue into the direction of the best match so far). They will merely differ by the required time to find the optimum, but when it's found, the quality will be the same in all cases.

Assumed there are no misleading constellations which provoke the recursive search to fail when led into a wrong direction, in which case the remaining difference to be quantized would be of a bigger magnitude, or an intra coded block would be required, which would take more space and reduce the efficiency.

Star has a smaller scope right away, it will terminate faster for rather regular motion, which may differ a bit more in mostly vertical or horizontal direction. The scope of UMH is wider, there are already 49 samples always in a first step (16 directions * 3 radii + the origin of the estimation), which will make it probably one of the slowest of these three on the average, yet may be more suitable for the case of a rather shaky camera or otherwise randomly changing motion. And SEA is effectively exhaustive over the whole motion range square, its speed would be constantly high, equal to the dual logarithm of the range for 8..9 samples in each refinement step; to beat UMH on average speed, it has to calculate at most 6 steps which would cover a square of +/- 32 pixels around the estimation, if I'm not completely wrong...

For encoding a TV broadcast of a sports event, I would probably trust the star-shaped motion search because motion will most often be quite regular (well estimated), which will save some time in comparison to UMH (probably good for action body camera footage) and SEA (probably best for those who insist in "the best" regardless of costs).

[708145]

[QUOTE=LigH;1789870
Star has a smaller scope right away, it will terminate faster for rather regular motion, which may differ a bit more in mostly vertical or horizontal direction. The scope of UMH is wider, there are already 49 samples always in a first step (16 directions * 3 radii + the origin of the estimation), which will make it probably one of the slowest of these three on the average, yet may be more suitable for the case of a rather shaky camera or otherwise randomly changing motion. And SEA is effectively exhaustive over the whole motion range square, its speed would be constantly high, equal to the dual logarithm of the range for 8..9 samples in each refinement step; to beat UMH on average speed, it has to calculate at most 6 steps which would cover a square of +/- 32 pixels around the estimation, if I'm not completely wrong...
[/QUOTE]

I'm a bit out of touch with the latest progress in this matter.

Has anyone thought about a way to adaptively trade off effort and quality of the ME method in use?

Maybe evaluating several methods on a small subset of blocks and comparing the effort and residue?
It would be possible to adaptively select the appropriate ME method for a given context. A secondary trade-off is present between reaction time to changed context and overhead of ME re-evaluation.

[Ataril]

Wow, the same questions concern me at the moment.
Guys, do you know where to get the source code of these methods?

Really nice exhumation by the way :)

[LigH]

Sources of the whole x265 encoder are on bitbucket (https://bitbucket.org/multicoreware/x265/wiki/Home). It uses some of these methods.