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. Thanks for the link. 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@gmail.com> wrote:
hi again, this page makes the inverse radon seem fairly do-able: http://www.owlnet.rice.edu/~elec431/projects96/DSP/bpanalysis.html<http://www.owlnet.rice.edu/%7Eelec431/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.
-b
On 8/22/06, stephen emslie <stephenemslie@gmail.com> wrote:
also, have you seen radon() in scipy.misc ?
if only there was an inverse_radon().
I'm taking a look at it now. The Radeon transform looks like it might be more effective than the Hough transform. Even so, I think it would be nice to have a Hough transform in scipy. Of course there's still that problem of the inverse transform as you say. It would definitely be handy to have!
Stephen
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.
Thanks for the link. 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@gmail.com> wrote:
hi again, this page makes the inverse radon seem fairly do-able: 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: def radon(arr,theta=None): 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 B. Kelley, V. K. Madisetti, "The Fast Discrete Radon Transform- I: 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
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.
You might find the open source Hough code in OpenCv instructive / useful. It's mature (Cv started in '99) and highly optimized, supporting standard and probabilistic methods for line and circle finding. On x86 platforms you will find its speed unbeatable for packaged code, especially w/ Intel's IPP. Wiki documentation for HoughLines2 w/ a C example at the API level: http://opencvlibrary.sourceforge.net/CvReference#cv_imgproc_special To see the underlying code you want the cvhough.cpp module in ../cv/src/ from the download tarball. There's also a Python example in ../samples/python/ of the CVS version, using OpenCv's Swig - Python port. I'm working on a ctypes Py port. Mark
participants (3)
-
Mark Heslep -
Stefan van der Walt -
stephen emslie