[XviD-devel] let's talk about the motion-estimation algorithm

[Christoph Lampert]

On Thu, 18 Sep 2003, yixian  wang wrote:

> Dear Sir/Madam:
> 
>   I read the source code of  motion-estimation algorithm( all in motion_est.c),it is very long and difficult to understand.
> 
>  In my summary, there are six search algorithms being used:
> 
> (1)Diamond Search: which include Diamond16_MainSearch,
> Diamond8_MainSearch,AdvDiamond16_MainSearch,
> AdvDiamond8_MainSearch
> 
> (2)Square Search: which include Square16_MainSearch,
> Square8_MainSearch
> 
> (3)Full Search :which include Full16_MainSearch,
> Full8_MainSearch
> 
> (4)PMVfastSearch:which include MVfastSearch16    ,PMVfastSearch8
> 
> (5)EPZSearch:which include 
> EPZSearch16,EPZSearch8
> 
> (6)Zero Search: which include ZeroSearch16
> 
> 
> Do you know about the advantage and disadvantage of every search algorithm. and the difference of the algorithms

All of them are very similar. The suffix 16 and 8 just describes
the blocksize: 16x16 or 8x8. (P)MVfast and EPZS are recently published
algorithms by A. Tourapis, although our implementation is a little
different. Basically they are just checking a few predictor for the best
starting point and then terminate early or do a usual gradient decent 
search.  Square and Diamond search just differ in the search pattern: a
diamond our the current position (4 point, (0,+1), (0,-1), (+1,0), (-1,0))
or a square (8 points: (+1,+1),(0,+1),(-1,+1),(+1,0),(-1,0),(+1,-1),
(0,-1),(-1,-1). Square is slower, but find somehow better vectors. 

gruel