[XviD-devel] Most frequent motion vector?

[Christoph Lampert]

On Sat, 4 Oct 2003 trbarry at trbarry.com wrote:

> Hi -
> 
> I had to check back and make sure I remembered what a radix sort was.
> ( http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/radixsort.html )
> 
> But it looks like a radix sort is a small enough amount of code that it
> would be worthwhile writing a custom one that optimizes for the problem.
> If I understand the issue properly then the whole thing could maybe be
> done with only 2 passes through the data, once for key X and once for
> key Y.

Actually, I found a impressively fast sort-routine called "sedgesort.c"
at http://www.yendor.com/programming/sort/

The problem is, that my data depends very much on the image. It might be 
only 99 vectors, all of which are (0,0), or 5000 vectors spread out over
a range from -512 to 512. 
But I don't think the number of points would justify using a radixsort,
as far as I remember, the overhead is too large for such "small" sets. 

For a start, I chose to simply use a histogramm around the mean value
plus some outlier class. In the histogram, I don't store the frequency of
the vector but directly the bits needed. So the fullest bin directly
corresponds to the vector I am aiming at. If my tests are successfull
(which I doubt), I can check if other solutions are faster... 

Thanks anyway!

gruel