[XviD-devel] RD stuff and more

[Michael Militzer]

Hi Radek,

Quoting Radek Czyz <syskin at ihug.com.au>:

[...]

> Right, I have a question for you. I'm rewriting fast qpel refinement 
> (very nice stuff) and I'm trying to understand how it works.
> I have problems seeing what happens after you check first three (or two) 
> qpel positions. The code says:
> 
> 	if(best_sad <= data->iMinSAD2) return;
> 
> best_sad is the best sad found in halfpel search. data->iMinSAD2 was 
> reset before the three qpel checks, so now contains either best_sad (or 
> less) if we've got a new best -  or the best sad of the three checks (if 
> none was good enough).
> 
> As I understand, it will "return" if we found one better match (equal), 
> will "return" if we haven't found anything good ( < ) and will only not 
> return if two of the three checks are better than best halfpel.
< 
> Okay I'm confused. Is this correct? Also, one of the three lines 
> actually says:
> 	if(best_sad < data->iMinSAD2) return;

I think it should always be '<=' - don't know why it's '<' for the second
check. In any case: '<' is saver and slower. Maybe I changed it to '<'
while testing, I don't remember. But from the global idea it should be
'<=', more below...

> That's very different, because now the function will not return if only 
> one better match is found. Which is correct?
> 
> I also have some problems understanding what happens next.... would you 
> be so kind and explain what's going on there? If I understand it, I 
> should be able to implement my version like it should be.

I'll try to quickly explain what's going on: Basically we're trying to
avoid checking the diagonal neighbours as checking these is really slow.
Also, we try to only check the neighbours 'in the direction' of the second
best SAD as we assume that the error landscape in subpel data is smooth so
that we won't get trapped in local minimas. Rather, the best qpel match
therefore has to be close around the best and second best halfpel matches.

In order to avoid checking the diagonal neighbours, we at first check the
three (or two) non-diagonal neighbours around the center that are closest
(or in the direction) to the second best match. If after these initial
checks, the center vector still is the best or second best match, we
assume that we won't find any better match and stop refinement using the
best match found so far as our qpel match.

If two of these non-diagonal checking points were better than the center,
then we check the diagonal neighbours at the corresponding angle. For
example:

  x
  o x

where o is our center and x are two non-diagonal neighbours that had a
smaller SAD than the center. In this case, we'll only check the top-right
position as our diagonal to the center. Then, subpel refinement finished.

If it looks like this:

 x
 o
 x

we'll check both diagonals: top and bottom in the direction towards the
second-best halfpel match. Well, that's it basically. If you need more
explanations, don't hesitate to ask...

Michael