[XviD-devel] SAD vs MSE for ME (warning! acronym overflow!)

Michael Niedermayer xvid-devel@xvid.org
Fri, 6 Sep 2002 13:05:32 +0200


Hi

On Friday 06 September 2002 09:24, Christoph Lampert wrote:
[...]
> After ME the problem is rather to find the best fractional positions
> "around" one integer position, because ME terminates with one vector
> (and most likely the information that this is a local minimum for SAD
> when considering only fullpel).
> However, one doesn't know which of the neighbours to chose for you
> method. Do you think there is a better way than calcalating
> fraction positions for both neighbours in 1D, and for all 4 neighbours
> in 2D? Because then we would have to decide which of the four is best,
> so we would have to really _calculate_ SSE and check values at the four
> positions :-(
>
> gruel
>
> But maybe you can come up with something better, because in many cases we
> can assume that the four neighbours have been visited
perhaps u want to take a look at motion_est.c in ffmpeg CVS it does halfpel 
search with only 4 instead of 8 checks

its based upon one assumtation:
that the score of the comparissions can be well approximated by axy + bx^2 + 
cy^2 + dx + ey + f(type)
type is the interpolation type (none, horizontal, vertical, both)

so for the horizontal (or vertical) interpolated positions, y (or x) is 0, the 
equation simplyfies to a quadratic poly: bx^2 + dx + f(type)
the known fullpel scores are:
score(-2,0)= 4b - 2d + f("f")
score( 0,0)=           f("f")
score( 2,0)= 4b + 2d + f("f")
4d = score( 2,0) - score(-2,0)

the scores of the horizontal interpolated points are:
score(-1,0)= b - d + f("h")
score( 1,0)= b + d + f("h")
so if score( 2,0) > score(-2,0) then score( 1,0) > score(-1,0)
so we only need to check one of them -> only 6 instead of 8 checks :)

for the both direction interpolated points:
score(-1,-1)= a + b + c - d - e + f("hv") = a - d - e + C
score( 1,-1)=-a + b + c + d - e + f("hv") =-a + d - e + C
score(-1, 1)=-a + b + c - d + e + f("hv") =-a - d + e + C
score( 1, 1)= a + b + c + d + e + f("hv") = a + d + e + C

so if d>0 && e>0 which is identical to score( 2,0) > score(-2,0)&& score( 0,2) 
> score(0,-2)
then either score(-1,-1) or if a is large then score( 1,-1) or score(-1,1) is 
best (depends upon d>e or d<e which are known)

the other cases are the same ...

the size at constant quantizers 2 and 10 is about 0.05% worse for the 4 checks 
vs. the 8
the psnr is practically identical (icant really see any significant difference 
in the psnr curve with gnuplot)

btw, as i "invented" that myself, it should be patent free hopefully ...

[...]

Michael