Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

I'm familiar with the Radon transform from learning about CT scans, but not the Hough transform. Wikipedia says

The (r,θ) plane is sometimes referred to as Hough space for the set of straight lines in two dimensions. This representation makes the Hough transform conceptually very close to the two-dimensional Radon transform. (They can be seen as different ways of looking at the same transform.[5])

Their output looks the same to me:

side-by-side rho vs theta plots for Hough and Radon transform

So I don't understand what the difference is. Are they just the same thing seen in different ways? What are the benefits of each different view? Why aren't they combined into "the Hough-Radon transform"?

share|improve this question
    
Hey, sort of unrelated question, but could you share your Bezier heatmap colorscheme you used in this picture? It looks pretty good, and I was wondering if you had an $M\times 3$ array of RGB values describing it. –  DumpsterDoofus 21 hours ago
    
@DumpsterDoofus I guess I haven't published it because it's kludgy and I wanted to polish it first, but since I haven't yet: non-bezier version is here gist.github.com/endolith/2879736 and bezier attempt is here gist.github.com/endolith/ef948b924abf289287bd also used here flic.kr/p/dWSfUd –  endolith 18 hours ago
    
Thanks, I actually figured it out last night, it can be written compactly as $RGB(x)=\left( \begin{array}{c} (2-x) x \text{Boole}[0\leq x\leq 1] \\ x^2 \text{Boole}[-1\leq x\leq 1] \\ -x (x+2) \text{Boole}[-1\leq x\leq 0] \\ \end{array} \right).$ –  DumpsterDoofus 8 hours ago
    
@DumpsterDoofus Feel free to clean up my code :) –  endolith 8 hours ago

2 Answers 2

up vote 20 down vote accepted

The Hough transform and the Radon transform are indeed very similar to each other and their relation can be loosely defined as the former being a discretized form of the latter.

The Radon transform is a mathematical integral transform is defined for continuous functions on $\mathbb{R}^n$ on hyperplanes in $\mathbb{R}^n$. The Hough transform, on the other hand, is inherently a discrete algorithm that detects lines (extendable to other shapes) in an image by polling and binning (or voting).

I think a reasonable analogy for the difference between the two would be like the difference between

  1. calculating the characteristic function of a random variable as the Fourier transform of its probability density function (PDF) and
  2. generating a random sequence, calculating its empirical PDF by histogram binning and then transforming it appropriately.

However, the Hough transform is a quick algorithm that can be prone to certain artifacts. Radon, being more mathematically sound, is more accurate but slower. You can in fact see the artifacts in your Hough transform example as vertical striations. Here's another quick example in Mathematica:

img = Import["http://i.stack.imgur.com/mODZj.gif"];
radon = Radon[img, Method -> "Radon"];
hough = Radon[img, Method -> "Hough"];
GraphicsRow[{#1, #2, ColorNegate@ImageDifference[#1, #2]} & @@ {radon,hough}]

The last image is really faint, even though I negated it to show the striations in dark color, but it's there. Tilting the monitor will help. You can click all figures for a larger image.

Part of the reason why the similarity between the two is not very well known is because different fields of science & engineering have historically used only one of these two for their needs. For example, in tomography (medical, seismic, etc.), microscopy, etc., Radon transform is perhaps used exclusively. I think the reason for this is that keeping artifacts to a minimum is of utmost importance (an artifact could be a misdiagnosed tumor). On the other hand, in image processing, computer vision, etc., it's the Hough transform that's used because speed is primary.


You might find this article quite interesting and topical:

M. van Ginkel, C. K. Luengo Hendriks and L. J. van Vliet, A short introduction to the Radon and Hough transforms and how they relate to each other, Quantitative Imaging Group, Imaging Science & Technology Department, TU Delft

The authors argue that although the two are very closely related (in their original definitions) and equivalent if you write the Hough transform as a continuous transform, the Radon has the advantage of being more intuitive and having a solid mathematical basis.


There's also the generalized Radon transform similar to the generalized Hough transform, which works with parametrized curves instead of lines. Here's a references that deals with it:

Toft, P. A., "Using the generalized Radon transform for detection of curves in noisy images", IEEE ICASSP-96, Vol. 4, 2219-2222 (1996)

share|improve this answer
    
Oh, I thought those were added to the image intentionally. Didn't realize they're artifacts. So Radon is to Hough as DFT is to FFT? But there's also generalized Hough transform that can find circles and stuff, and maybe similar things for Radon transform? –  endolith Oct 27 '11 at 13:55
1  
Yeah, there's the generalized Radon transform that works for parametrized curves. I would assume it's harder to do so for completely arbitrary curves, but I do not know that much about it. I've added a reference to my answer. –  Lorem Ipsum Oct 27 '11 at 14:27
    
The Radon transform can be sped up with FFT methods, too. I'm guessing the Hough can't be? Is Hough still faster? I'm guessing it depends on image size? –  endolith Nov 24 '11 at 20:16
1  
@endolith It's my experience that Hough is faster. However, my use of these two is to detect the few odd lines in something I'm fiddling around with. Never used it in serious work, nor have I implemented my own. So I would suggest asking that as a new question, as I cannot answer with certainty. –  Lorem Ipsum Nov 25 '11 at 23:53

Additionally to Lorem Ipsum's answer explaining the Hough transform as a discretized form of Radon transform, I like this descriptive explanation - also according to Ginkel and others:

Both Radon and Hough are a mapping from the image space to a parameter space of $\rho$ and $\theta$, but they differ in their point of view. While the Radon transform derives a point in parameter space from image space (the reading paradigm), the Hough transform explicitly maps data points from image space to parameter space (the writing paradigm).

This becomes clear by comparing their (discrete) algorithms. For each $\theta$ in parameter space Radon projects the image points on a line described by (its angle) $\theta$ using buckets of size $\Delta\rho$. Hough on the other hand takes each image point $(x,y)$ and adds the appropriate intensity to all corresponding parameter space bins.

As a result Hough suffers artifacts whereas Radon allows for high resolution in parameter space (by adjusting $\Delta\theta$ and $\Delta\rho$ and dividing pixels into subpixels).

Hough is usually faster though the whole transformation needs to be performed (which is the intention in most cases anyway). Radon allows to compute only a short interval (in $\theta$) of the parameter space due to the reading paradigm. This can significantly reduce computation time if you have some a priori knowledge (like in which $\theta$ intervals your peaks probably are).

I guess Hough is dominant in many fields because of its simple algorithm, whereas Radon is used where accuracy is crucial or a priori knowledge available.

See also Matlab references (expand the Algorithm tab):

www.mathworks.com/help/images/ref/radon.html

www.mathworks.com/help/images/ref/hough.html

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.