RANSAC

OK so here’s a graph of macro-block vectors, where red dots are those whose SAD is higher than the average and green is equal or lower than average.  The colour of each dot is more intense for the number of macro-blocks with that vector value..

All SADs

All SADs

Here’s a couple separating the greens (currently used) from the reds (currently discarded).

Red

Red

Green

Green

It’s pretty clear that both low and high SAD vectors have a common concentration around “the right value” i.e. SAD’s irrelevant for finding the most concentrated area of vectors.  If there’s a way to find that area in code, throw away all vectors outside that area’s boundary and then average out those that are left, the result should be much more accurate.

Adam Heinrich from the Czeck Republic has pointed me in the direction of the RANSAC (RANdom SAmple Consensus) algorithm; a simple, iterative way to identify the collection of macro-block vectors that are self-consistent.

I’ll leave it to Wikipedia to explain how it works.

The reason it’s so good in my context is that it can broken up into batches which can be processed when the code isn’t busy doing something else: i.e. when the FIFO is less than half full and we’re waiting for the next set of blocks from the video.

Once Christmas and New Year chaos are out of the way, I hope to dedicate more of my brain to how this works, and implementing it.

Thanks, Adam, for pointing me in the right direction.

Leave a Reply

Your email address will not be published. Required fields are marked *