An interesting problem
scott at asofyet.org
Wed Jan 3 21:25:02 GMT 2007
On Jan 3, 2007, at 3:51 PM, Andy Armstrong wrote:
> I'm still thinking optimisations on a brute force approach here -
> it'd be much nicer to think of a clever algorithm - but I'm coming
> up blank and I don't think the beer's helping as much as I'd hoped :)
I think that the previous mention of a 2D autocorrelation will be
good to explore, but you can use the "moving average" trick to avoid
lots of extra cycles while summing neighborhoods. I've implemented
this in C before and gotten speedups of 1x to 50x, depending on the
Essentially, for each neighborhood size, you sum an entire
neighborhood once, and then add and subtract only deltas from there.
To avoid resumming at the next row, you move in a serpentine fashion
through the image / matrix / table / whateveryoucallit. The output
of this exercise is, of course, another image whose size is original
size divided by neighborhood size.
Unfortunately, the code for this is not what you'd call simple and
light (edge effects, unrolled loops, etc), so make sure that this is
the algorithm you want before you go for optimizations. Brute force
has the advantage that it's easy to code correctly and therefore use
as a correctness tester.
More information about the london.pm