[<<][math][>>][..]
Sat Jul 12 13:49:32 CEST 2008

Toroidal Hough Transform

For grid estimation, we're not really interested in individual maxima
on the r-spectrum. Reducing this spectrum to a couple of values can be
done by adding bias toward a period R. Then, instead of using a voting
algorithm for bundles:

            (r,t) | r = x cos t + y cos t,  t \in [0,pi]

we vote for the phasor:

            (e^{i r/R} , t)

The advantage is that these votes can be accumulated immediately, so
memory access becomes simpler, and a histogram interval discretization
step is not necesesary.

The core computation is the evaluation of cos/sin, the rest seems
memory-bound.

Given R and t, the grid period, compute the complex phasor p: 

    p(R,t) = \sum_n e^{i r_n(t) / R}
    r_n(t) = (x,y) ? x cos t + y cos t : 0

The inner loop is the sum over the exponentials of r_n(t) for linearly
increasing x with y fixed, so this can be updated.

However, the image will be mostly sparse, so this will probably not
bring much speedup (points are not equidistant, so multiple rotation
update matrices are necessary).

( Tests indicate the 2 approachs: straight eval + update are about the
same speed. Maybe it's memory bound? )




[Reply][About]
[<<][math][>>][..]