Thu Jun 26 18:32:28 CEST 2008

Discretized integral transforms: domain / codomain loop order

Moving from the Hough transform -> Radon transform is an example of a
more general pattern of re-arranging control around data dependencies
in discretized integral transforms, basicly chainging the order of

The central idea is this: for finite versions of an integral
transform, there exists a related finite histogram based version with
inverted control.  Instead of computing the integral for each sampled
codomain point from all the domain points, one computes the
contribution of each domain point to all the codomain points. Basicly,
in the discrete version, the domain and codomain loops are transposed.

For example, a generic integral transform
             _  _
 (y0,y1) = _/ _/  F(x0,x1,y0,y1) dx0 dx1
           x0 x1

can be rewritten, after discretization as 4 nested loops over
y0,y1,x0,x1 (outer->inner): for each y0,y1 the result is computed
directly. However, it can also be computed as an update of an y0,y1
grid by re-ordering the loops x0,x1,y0,y1.

For the Hough transform there is only one integral, so there are 3
loops to reorder to get to a discretized Radon transform.

Is this useful? The only scenario i can think about is the case where
the histogram version is faster to compute than the direct version,
but you need some estimate before you use the direct version in an
iterative algorithm. Maybe this only makes sense for line integrals,
not for full 2D->2D maps.