How to implement the Hough Transform?

Question

How does one implement a Hough transform on a text image? I'm looking for pseudo-code (eventually this will be in java).

Here is some background information:

Given an image, determine the equation for a line y = mx + b. Typically the Hough Transform is represented in polar co-ordinates such that Rho = y*sin(theta) + x*cos(theta). (I'm not really sure what the X and Y values correspond to back to the image).

we are only interested in the Rho and theta values and plot them. The locations with many points in the accumulator (I know some of the implementation, not the execution) is considered a line.

The issue that I don't understand is how to find the rho and theta that you'd update the accumulator with.

Answer 1

The simplest case of Hough transform is the linear transform for detecting straight lines. In the image space, the straight line can be described as y = mx + b and can be graphically plotted for each pair of image points (x, y)

So this tells you what x and y correspond to back in the image.

In the Hough transform, a main idea is to consider the characteristics of the straight line not as image points (x1, y1), (x2, y2), ..., but instead, in terms of its parameters, such as 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 and (theta), for the lines in the Hough transform.

The parameter rho represents the distance between the line and the origin, while theta is the angle of the vector from the origin to this closest point.

This tells you what rho and theta correspond to: they are the representation in polar coordinates of slope and intercept of the line you are trying to describe in your image.

---

On SourceForge you can find a C++ implementation of hough transform.

A description from which you should be able to interpret the code which I pointed out in the previous link may be the following:

The Hough transform algorithm uses an array, called an accumulator, to detect the existence of a line y = mx + b.

For example, the linear Hough transform problem has two unknown parameters: m and b.

For each pixel and its neighborhood, the Hough transform algorithm determines if there is enough evidence of an edge at that pixel. If so, it will calculate the parameters of that line, and then look for the accumulator's bin that the parameters fall into, and increase the value of that bin.

By finding the bins with the highest values, typically by looking for local maxima in the accumulator space, the most likely lines can be extracted