[SciPy-user] hough transform again

Stefan van der Walt stefan at sun.ac.za
Tue Aug 22 12:08:46 CDT 2006

```On Tue, Aug 22, 2006 at 03:57:35PM +0100, stephen emslie wrote:
> It could be that Stefan's hough is fast because it uses only one for loop, and
> lots of array operations, which I believe are fast.
>
> Speed is definitely going to be an issue for me, as I'm going to need to be
> able to process a video feed in real-time. But I'd like to try and get things
> working with scipy and radon to start, and then look at speeding things up.
>
> btw, hope you dont mind if I send this to the list too. Perhaps someone will be
> able to give some more insight into hough, radon, inverse radon, speed, etc.
>
> Stephen
>
> On 8/22/06, Brent Pedersen <bpederse at gmail.com> wrote:
>
>     http://www.owlnet.rice.edu/~elec431/projects96/DSP/bpanalysis.html
>     i'm going to try to implement.
>     at least all the tools are in sci/num-py, just have to put them together...
>     i still wonder why the stefan's hough is so much faster than scipy's radon,
>     i guess the imrotate in radon must be pretty expensive.

Certainly.  Here is the code snippet from Lib/misc/pilutil.py:

if theta is None:
theta = mgrid[0:180]
s = zeros((arr.shape[1],len(theta)), float)
k = 0
for th in theta:
im = imrotate(arr,-th)
s[:,k] = sum(im,axis=0)
k += 1
return s

There are more accurate and faster ways of calculating the Radon
transform (but I must add that this snippet demonstrates the idea
behind the transform very well!).  It can, for example, simply be done
in the Fourier domain, as shown in

B.R. Ramesh, N. Srinivasa, K. Rajgopal, "An Algorithm for Computing
the Discrete Radon Transform With Some Applications", Proceedings of
the Fourth IEEE Region 10 International Conference, TENCON '89, 1989.

and, more recently, with the Fast Radon Transform as described in

Theory", IEEE Trans. on Image Processing, July 1993.

Both papers are on the internet and can be found using
scholar.google.com.  Beylkin's original article is harder to find:

Beylkin, G., "Discrete Radon Transform", IEEE Transactions on Acoustics,
Speech and Signal Processing, vol 35, no. 2, 1987, pp 162 - 172.

Or, if you *really* want to get to the root of things, read

J. Radon, "Uber die Bestimmung von Funktionen durch ihre Integralwerte
längs gewisser Manigfaltigkeiten",
Ber. Ver. Sächs. Akad. Wiss. Leipzig, Math-Phys. Kl., vol. 69, April
1917.

Sure, you'd have to learn German first, but that will probably come in
handy one day :)

Regards
Stéfan
```