An interesting problem

[muppet]

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  
neighborhood size.

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.