Hough Transform Equation

Question

I was wondering why the Hough Transform uses rho=xcos(theta) + ysin(theta) for representation of a straight line (y=mx+b). I tried to work through this (and went to the wikipedia article about this), but can not find a way to derive one from the other.

Does anyone know how to derive one from the other?

Thank you in advance.

Answer 1

Polar coordinate system is 2-D coordinate system that has a reference point (like origin) called pole and a line from the pole called the polar axis. Each point in the Polar coordinate system is represented as (rho, theta) where 'rho' is the distance between the pole (origin) and the point and 'theta' is the angle between the polar axis and the line joining the pole and the point. See here.

The Polar coordinate (rho, theta) can be converted to Cartesian coordinate (x,y) using the following trigonometric equations.

x = rho cos theta       ----(1) 
y = rho sin theta       ----(2)

Refer here for more info.

How do we get the above equations?

The equations use concepts of a right angle (trignonometry)

See the picture here.

cos theta = adjacent-side/hypotenuse = x/rho,  thus we get (1)     
sin theta = opposite-side/hypotenuse = y/rho,  thus we get (2)
and Pythagorean theorem says,
hypotenuse^2 = adjacent side ^2 + opposite side^2, so
rho^2 = x^2 + y^2       ----(3)

Now let's derive the relationship between Cartesian coordinate (x,y) and Polar coordinate (rho,theta)

rho^2 = x^2 + y^2       ---- from (3)
rho^2 = x*x  +  y*y
rho^2 = x(rho cos theta) + y (rho sin theta)   ---- from (1) and (2)  
rho^2 = rho(x cos theta + y sin theta)
rho = x cos theta + y sin theta

Answer 2

Derivation:

The equation x/a + y/b = 1:

• defines a line
• has x-intercept = a
• has y-intercept = b

From trigonometry, recall how a ray rotated by angle t will project onto the x- and y- axes according to (angle=t, radius=1) -> (x=cos(t), y=sin(t))*

Draw the tangent line at the labelled point. Trigonometry (or even geometry with similar triangles) tells us that the tangent line intersects at x=1/cos(t), y=1/sin(t). Thus the line a distance 1 away will have a=1/cos(t) and b=1/sin(t), and thus described by x/(1/cos(t)) + y/(1/sin(t)) = 1...

... which is just cos(t) x + sin(t) y = rho where rho=1

You can see that rho corresponds to how far the line is from the origin (either by playing around with the equation, or by noting that multiplication here just scales all values by the same amount, effectively rescaling the grid).

---

*see http://en.wikipedia.org/wiki/File:Unit_circle.svg for credit

Answer 3

That's just a transform from a linear coordinate system to a rotational one. The reason for this is outlined in the Wikipedia article:

In the Hough transform, a main idea is to consider the characteristics of the straight line not as image points (x1, y1), (x2, y2), etc., but instead, in terms of its parameters, i.e., the slope parameter m and the intercept parameter b. Based on that fact, the straight line y = mx + b can be represented as a point (b, m) in the parameter space. However, one faces the problem that vertical lines give rise to unbounded values of the parameters m and b. For computational reasons, it is therefore better to use a different pair of parameters, denoted r and θ (theta), for the lines in the Hough transform.

And to transform between the two, use the equation y = -(cos(theta)/sin(theta))x + r/sin(theta). Thus m = -(cos(theta)/sin(theta)) and b = r/sin(theta). These obviously break down when sin(theta)=0 or theta=0, which is why the rotational coordinate system is preferred (there aren't any problems with lines with infinite slopes).