Sat Jul 12 16:47:21 CEST 2008

Accellerating the inner accumulator loop

Bring the conditional out of the loop.

RLE will transform the sparse vector into an array of offsets that can
be used to perform the incremental accumulation without a conditional
in the inner loop. This representation needs to be computed only once,
and can be reused for every p(R,t) evaluation.

             e^{i (x cos t + y sin t) 2 pi / R}

( Moving one step further, instead of storing offsets that will have
  to be transformed to phase increments once per inner loop, what
  about storing the phase increments directly? This doesn't make sense
  for t=constant however, since each increment is used only once. It
  does make sense when multiple R are evaluated per t. )

The inner loop with y=cte looks like:

          \sum_X e^{i (a x + b)} = e^{i b} \sum_X e^{i a x}


      X = {x | image(x,y) = 1}  (range of sum)
      a = 2 pi cos t / R
      b = 2 pi y sin t / R

This makes the inner loop accumulation the accumulation of sin/cos of
scaled versions of the RLE x values.

Here a is the 'speed' at which the points in X rotate around. This
depends on t: the speed is a projection of the expected speed R under
angle t. Doesn't look there is a shortcut there, because of the
absence of structure in the set of points X.

( With RLE, the running time is proportional to the number of white
  points in the input image. Maybe some preprocessing step is desired
  to eliminate blurry gradients? )

If sincosf (math.h) can be used, this might go a bit faster.