[XviD-devel] Most frequent motion vector?

[trbarry at trbarry.com]

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.

Maybe the first pass on, say, X could also keep track of the max and min
Y values so a smaller number of bins could be used in the second pass.
This might help if the actual range of Y keys is fairly small. (YBin =
Y - Ymin)

And by the time of the second pass on Y the entries going into the bins
are already in order so it is already possible to count duplicates and
keep track of the current best during that pass.  That might save a
little time and would finish the job as long as you didn't need 2nd best
etc.

And even keeping a small table of 2nd, 3rd, 4th, best etc. could
probably still be done for a small number in that second pass fairly
effectively if you had to.

But I haven't really worked out all this so I might be missing
something.  For instance I'm assuming the number of things to be sorted
is much greater than the total number of possible values each for the X
and Y keys.

- Tom



| -----Original Message-----
| From: xvid-devel-bounces at xvid.org
| [mailto:xvid-devel-bounces at xvid.org]On
| Behalf Of Christoph Lampert
| Sent: Saturday, October 04, 2003 4:08 AM
| To: xvid-devel at xvid.org
| Subject: [XviD-devel] Most frequent motion vector?
|
|
|
| Hi guys,
|
| I should have studied computer science instead of maths:
|
| Is there a fast and not too wasteful method to determine
| which is the most
| frequent motion vector of a XxY field of motion vectors?
|
| When going through all of them, how do I store how often they appear?
| An array of [-512,512]x[-512,512] wouldn't be such a good
| idea, right?
| Choose a center and a "outlier" group and working adaptively from
| there, possibly having to restart a couple of times?
|
| Or could this be done more efficiently during ME itself?
|
| If that succeeds, I might later need "2nd best" up to "Nth".
|
| gruel
|
|
| _______________________________________________
| XviD-devel mailing list
| XviD-devel at xvid.org
| http://list.xvid.org/mailman/listinfo/xvid-devel