Fast algorithm for multiple line integrals over 2D discrete function

Question

Okay, I am looking for something akin to integral images (summed area tables) as used in the acceleration of integral calculations over a window.

I have an image I and its gradient image G. I want to calculate the straight line integral from two arbitrary points a and b in the image of the absolute value of G. Obviously I can step over the line (1-t)a + t*b, t in [0, 1] and sum up given the right t step size. I want, however, to do this several million times so I would like some acceleration structure that preferably doesn't require me to run a loop for every pair (a, b).

Does anyone know of an existing algorithm to accomplish this sort of thing?

Answer 1

I think the answer is no. If you were to integrate the gradient and not its absolute value, it would be trivial though.

I would have another concern though: How do you interpolate on G ? You'll have pixel values, and the sampling points you'll use to compute the integral won't generally fall exactly on pixels. Either "pick the closest pixel value" or "interpolate between the four neighbors" will do. The latter is more precise, the former is faster.

Since |G| is likely not to be smooth, you'll have no choice but (expensive) trapezoidal rule for integration.

EDIT: Look at Bresenham's algorithm. Since you won't be interpolating, it should provide useful optimization.

Answer 2

You seem to know your math, so I'll suggest the adaptive quadrature algorithm.

It is most commonly used for calculating simple 2D integrals efficiently, but you can probably put it to good use for what you are working on.