How would you convert X,Y points to Rho,Theta for hough transform in C?

Question

So I am trying to code Hough Transform on C. I have a binary image and have extracted the binary values from the image. Now to do hough transform I have to convert the [X,Y] values from the image into [rho,theta] to do a parametric transform of the form

rho=xcos(theta)+ysin(theta)

I don't quite understand how it's actually transformed, looking at other online codes. Any help explaining the algorithm and how the accumulator for [rho,theta] values should be done based on [X,Y] would be appreciated.Thanks in advance. :)

Answer 1

Your question hints at the fact that you think that you need to map each (X,Y) point of interest in the image to ONE (rho, theta) vector in the Hough space.

The fact of the matter is that each point in the image is mapped to a curve, i.e. SEVERAL vectors in the Hough space. The number of vectors for each input point depends on some "arbitrary" resolution that you decide upon. For example, for 1 degree resolution, you'd get 360 vectors in Hough space.

There are two possible conventions, for the (rho, theta) vectors: either you use [0, 359] degrees range for theta, and in that case rho is always positive, or you use [0,179] degrees for theta and allow rho to be either positive or negative. The latter is typically used in many implementation.

Once you understand this, the Accumulator is little more than a two dimension array, which covers the range of the (rho, theta) space, and where each cell is initialized with 0. It is used to count the number of vectors that are common to various curves for different points in the input.

The algorithm therefore compute all 360 vectors (assuming 1 degree resolution for theta) for each point of interest in the input image. For each of the these vectors, after rounding rho to the nearest integral value (depends on precision in the rho dimension, e.g. 0.5 if we have 2 points per unit) it finds the corresponding cell in the accumulator, and increment the value in this cell.
when this has been done for all points of interest, the algorithm searches for all cells in the accumulator which have a value above a chosen threshold. The (rho, theta) "address" of these cells are the polar coordinates values for the lines (in the input image) that the Hough algorithm has identified.

Now, note that this gives you line equations, one is typically left with figure out the segment of these lines that effectively belong in the input image.

A very rough pseudo-code "implementation" of the above

Accumulator_rho_size = Sqrt(2) * max(width_of_image, height_of_image)
                          * precision_factor  // e.g. 2 if we want 0.5 precision
Accumulator_theta_size = 180  // going with rho positive or negative convention
Accumulator = newly allocated array of integers
    with dimension  [Accumulator_rho_size, Accumulator_theta_size]
Fill all cells of Accumulator with 0 value.

For each (x,y) point of interest in the input image
   For theta = 0 to 179
       rho = round(x * cos(theta) + y * sin(theta),
                   value_based_on_precision_factor)
       Accumulator[rho, theta]++

Search in Accumulator the cells with the biggest counter value
(or with a value above a given threshold) // picking threshold can be tricky

The corresponding (rho, theta) "address" of these cells with a high values are
the polar coordinates of the lines discovered in the the original image, defined
by their angle relative to the x axis, and their distance to the origin.

Simple math can be used to compute various points on this line, in particular
the axis intercepts to produce a  y = ax + b equation if so desired.

Overall this is a rather simple algorithm. The complexity lies mostly in being consistent with the units, for e.g. for the conversion between degrees and radians (most math libraries' trig functions are radian-based), and also regarding the coordinates system used for the input image.