Welcome to Doom9's Forum, THE in-place to be for everyone interested in DVD conversion.

Before you start posting please read the forum rules. By posting to this forum you agree to abide by the rules.

 

Go Back   Doom9's Forum > Video Encoding > MPEG-4 AVC / H.264

Reply
 
Thread Tools Search this Thread Display Modes
Old 1st August 2005, 00:50   #1  |  Link
IRMA1024
Registered User
 
Join Date: Jun 2005
Posts: 19
Motion Search Method

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
Code:
 
 /\
/\/\   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
IRMA1024 is offline   Reply With Quote
Old 1st August 2005, 09:46   #2  |  Link
sysKin
Registered User
 
sysKin's Avatar
 
Join Date: Jun 2002
Location: Adelaide, Australia
Posts: 1,167
Diamond is just four direct neighbours:
Code:
  |
—   —
  |
Hexagon, like the name suggests, has SIX directions, not eight:
Code:
 \  /
—    —
 /  \
Square, used in XviD (with motion precision 6) has eight:
Code:
\ | /
—   —
/ | \
Hopefully this helps.
__________________
Visit #xvid or #x264 at irc.freenode.net
sysKin is offline   Reply With Quote
Old 1st August 2005, 16:04   #3  |  Link
akupenguin
x264 developer
 
akupenguin's Avatar
 
Join Date: Sep 2004
Posts: 2,392
Diamond. The previous best known position is shown as "0", and the positions to try next as "1".
Code:
 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").
Code:
 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.
Code:
                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.
Code:
              ...
   111111111111111111111111
   111111111111111111111111
   111111111111111111111111
   111111111111111111111111
   111111111111111111111111
   111111111111111111111111
   111111111111111111111111
...111111111111011111111111...
   111111111111111111111111
   111111111111111111111111
   111111111111111111111111
   111111111111111111111111
   111111111111111111111111
   111111111111111111111111
   111111111111111111111111
              ...
akupenguin is offline   Reply With Quote
Old 1st August 2005, 16:23   #4  |  Link
Sirber
retired developer
 
Sirber's Avatar
 
Join Date: Oct 2002
Location: Canada
Posts: 8,978
Good post!
__________________
Detritus Software
Sirber is offline   Reply With Quote
Old 1st August 2005, 18:21   #5  |  Link
IRMA1024
Registered User
 
Join Date: Jun 2005
Posts: 19
wow thanks for the explanation...

by the way the exaustive search looking for every pixel in each loop... does it give significant result?
IRMA1024 is offline   Reply With Quote
Old 1st August 2005, 20:11   #6  |  Link
superdump
Guest
 
Posts: n/a
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.
  Reply With Quote
Old 1st August 2005, 21:51   #7  |  Link
IRMA1024
Registered User
 
Join Date: Jun 2005
Posts: 19
then finding upper bound is for what?
IRMA1024 is offline   Reply With Quote
Old 1st August 2005, 23:24   #8  |  Link
skal
Registered User
 
Join Date: Jun 2003
Posts: 121
IRMA1024: the upper bound is for knowing how much you've traded from speed to accuracy/quality.
-Skal

Last edited by skal; 2nd August 2005 at 06:14.
skal is offline   Reply With Quote
Old 2nd August 2005, 01:46   #9  |  Link
IRMA1024
Registered User
 
Join Date: Jun 2005
Posts: 19
it is 2^10 not 2^9... thanks
IRMA1024 is offline   Reply With Quote
Old 2nd August 2005, 06:30   #10  |  Link
skal
Registered User
 
Join Date: Jun 2003
Posts: 121
oops...my bad
-Skal (<="bendova, Junior")
skal is offline   Reply With Quote
Old 4th August 2005, 10:13   #11  |  Link
foxyshadis
ангел смерти
 
foxyshadis's Avatar
 
Join Date: Nov 2004
Location: Lost
Posts: 9,558
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.
foxyshadis is offline   Reply With Quote
Old 4th August 2005, 17:24   #12  |  Link
Isochroma
Registered User
 
Join Date: Mar 2005
Posts: 468
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!
Isochroma is offline   Reply With Quote
Old 4th August 2005, 17:49   #13  |  Link
Kostarum Rex Persia
Banned
 
Join Date: May 2005
Location: Serbia
Posts: 560
Isochroma,post some images of your video,and explain what settings you used for compression.
Kostarum Rex Persia is offline   Reply With Quote
Old 4th August 2005, 17:55   #14  |  Link
Sirber
retired developer
 
Sirber's Avatar
 
Join Date: Oct 2002
Location: Canada
Posts: 8,978
hand edit?
__________________
Detritus Software
Sirber is offline   Reply With Quote
Old 4th August 2005, 17:58   #15  |  Link
DeathTheSheep
<The VFW Sheep of Death>
 
DeathTheSheep's Avatar
 
Join Date: Dec 2004
Location: Deathly pasture of VFW
Posts: 1,149
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!
__________________
Recommended all-in-one stop for x264/GCC needs on Windows: Komisar x264 builds!
DeathTheSheep is offline   Reply With Quote
Old 14th December 2016, 12:03   #16  |  Link
LigH
German doom9/Gleitz SuMo
 
LigH's Avatar
 
Join Date: Oct 2001
Location: Germany, rural Altmark
Posts: 6,753
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: 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: 1 adjacent pixel in each orthogonal direction

Square search: small complete neighborhood, only suitable for littlest expected motion changes
  • one step: 1 adjacent pixel in each direction

Hexagonal search: 2-step search in a slightly larger range, assuming more probable vertical directions
  • step 1: ~2 pixel (approx. Euclidean) distance in 6 directions
  • step 2 – continuous motion, good hit: additional square refinement
  • step 2 – 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: 2 pixel "Manhattan" distance in 8 directions + 5 pixel distance in orthogonal directions
  • step 2 – continuous motion, good hit: additional "Small Diamond" refinement, 1 pixel orthogonal distance
  • step(s) 2 – changing motion, offset: additional recursive search with "Large Diamond" range, 2 pixel "Manhattan" distance
  • step(s) 3 – 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: 4 pixel square distance
  • step 2 – continuous motion, good hit: additional 2 pixel square distance refinement
  • step 3 – continuous motion, good hit: additional 1 pixel square distance refinement
  • step 2 – changing motion, offset: additional 2 pixel square distance refinement
  • step 3 – 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: ~4+8+12 pixel (approx. Euclidean) distance in 16 directions (vertically more dense)
  • step 2 – continuous motion, good hit: additional hexagonal 2 pixel refinement
  • step 3 – continuous motion, good hit: additional diamond refinement
  • step(s) 2 – changing motion, offset: additional recursive search with hexagonal 2 pixel distance
  • step(s) 3 – changing motion, offset: additional recursive "Small Diamond" refinement, 1 pixel orthogonal distance

CC-BY
__________________

New German Gleitz board
MediaFire: x264 | x265 | VPx | AOM | Xvid

Last edited by LigH; 14th December 2016 at 12:23.
LigH is offline   Reply With Quote
Old 14th December 2016, 12:19   #17  |  Link
Groucho2004
 
Join Date: Mar 2006
Location: Barcelona
Posts: 5,034
Last post was in 2005, Ligh, you're a necromancer.
__________________
Groucho's Avisynth Stuff
Groucho2004 is offline   Reply With Quote
Old 14th December 2016, 12:21   #18  |  Link
LigH
German doom9/Gleitz SuMo
 
LigH's Avatar
 
Join Date: Oct 2001
Location: Germany, rural Altmark
Posts: 6,753
I know. – Still, I believe it's the best place.
__________________

New German Gleitz board
MediaFire: x264 | x265 | VPx | AOM | Xvid
LigH is offline   Reply With Quote
Old 16th December 2016, 05:16   #19  |  Link
aymanalz
Registered User
 
Join Date: May 2015
Posts: 68
Quote:
Originally Posted by LigH View Post
I know. – 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?
aymanalz is offline   Reply With Quote
Old 16th December 2016, 08:43   #20  |  Link
LigH
German doom9/Gleitz SuMo
 
LigH's Avatar
 
Join Date: Oct 2001
Location: Germany, rural Altmark
Posts: 6,753
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).
__________________

New German Gleitz board
MediaFire: x264 | x265 | VPx | AOM | Xvid

Last edited by LigH; 16th December 2016 at 09:09.
LigH is offline   Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +1. The time now is 19:09.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.