Doom9's Forum - View Single Post

LigH · 14th December 2016, 12:03

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

14th December 2016, 12:03	#16 \| Link
LigH German doom9/Gleitz SuMo Join Date: Oct 2001 Location: Germany, rural Altmark Posts: 6,782	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.