Computer Vision - Does implementation of Hough Transform for lines require a loop for angle parameter?

Question

I am trying to understand how Hough Transform is implemented in real world applications. Consider a line with equation:

$y = mx + b$

In parametric form, this line can be represented using (d, $\theta$):

$d = xcos(\theta) + ysin(\theta)$

This is the Hough Transform algorithm in simple form, using the parametric form (ref: link) :

Initialize parameter space H[d, theta]=0

for each edge point I[x,y] in the image, 

   for theta = [theta_min to theta_max ], 

      set H[d, theta] += 1

Find the value(s) of (d, theta) where H[d, theta] is maximum

1) In real world implementations, is the line: for theta = [theta_min to theta_max ] required? Since we apply Canny edge detector to an image, prior to Hough Transform, we can obtain angle of gradient($\theta$) for a point (x, y) from Sobel operators. This can be noted down against (x, y) and later used in Hough Transform algorithm, eliminating one for loop. Isn't this the better, real world approach? Or do we actually implement the extra for loop?

Answer 1

In real world implementations, is the line: for theta = [theta_min to theta_max ] required?

. . .

Since we apply Canny edge detector to an image, prior to Hough Transform, we can obtain angle of gradient(θ) for a point (x, y) from Sobel operators. This can be noted down against (x, y) and later used in Hough Transform algorithm, eliminating one for loop. Isn't this the better, real world approach?

The standard Hough Transform algorithm does not assume that direction information is available for the image that is transformed. It basically accepts a set of point values (pixel location, pixel value) ($(x,y,v)$) at its input and converts lines to points. This is because, colinear points 9lines) contribute to large "accumulations" (counts) along the directions of the line they form.

So, a pixel of value $v$ at some location $x,y$ contributes $+v$ to all the Hough domain arcs that pass through it.

Now, if we consider the line formed by two neighbouring pixels $(x_0,y_0,v_0), (x_1, y_1,v_1)$ that both happen to have values $v_0=v_1=v$ (for simplicity), then this line segment's contribution along the directions that are parallel to the line is $2 \cdot v$ but along the vertical direction is still $v$ for two arcs.

As the length ($l$) of the line segment that is formed by any two $(x_m,y_m), (x_n,y_n), m \neq n$ increases, even if the pixels are not neighbours now, then they contribute $l \cdot v$ to that one direction of convergence but still $v$ to $l$ arcs in the vertical direction. But also, as that length increases, it starts contributing between $v .. l \cdot v$ to a wider range of $\theta$s around the direction that is parallel to the line.

Therefore, the answer to the first question is "yes". The answer to the second question is "under certain conditions".

This is because, you can use some of the information of the Canny edge detector to inform the accumulation process of the Hough Transform, but you have to do it carefully.

The Canny edge detector implies a scale parameter because it uses a Gaussian filter. This scale parameter, along with the gradient information can be used to further subdivide the Canny edge detector's output into a set of composing elementary line segments at direction $\theta$ and length $l$. Then, the Hough Transform would be approximated by adding together the individual Hough Transforms of those elementary lines. But of course, notice here that you still have to "scan" the elementary line segments at a range of $\theta$s to obtain their contribution during this pre-computation stage.

Hope this helps.