Hough transform

The Hough transform is a computer vision technique used to identify lines within an image. The only knowledge you need prior to understanding the algorithm is that lines can be represented either by two points or by two values. The first is the angle of the line (theta) and the second is the shortest distance from that line to the origin (rho). The algorithm basically works like this:

1. Create a large matrix where one axis of the matrix corresponds to theta and one to rho. This matrix is called the accumulator and is said to represent the "Hough space" of the image. Initialize this matrix by each entry being 0.
2. Create a grayscale image
3. Find the edges in that image (for example using the canny algorithm)
4. For each point in those edges:
5. Calculate many lines defined by theta and rho radiating out from that point. Each theta should have the same angle of difference to each other and each rho is calculated based on the coordinate of the point and the theta. For each of these lines, add a 1 to the corresponding entry in the accumulator matrix.
6. When you have a filled in accumulator, find a number of local maxima within that accumulator. Each local maxima corresponds to a line in the image, so if you want to find 10 lines you should pick out the 10 local maxima that have the largest values in the accumulator matrix.
7. Transform the local maxima in the accumulator back to lines using their corresponding theta and rho values.
8. To visualize the result, overlay these lines on your original image.

Some notes about the algorithm:

• If you increase the resolution of the accumulator, allowing more values for theta and rho, you will get a more precise result but the computational time will increase and you risk have many overlapping lines when you pick out the local maxima from the accumulator.
• The Hough transform is not very computationally efficient.
• The Hough transform can be generalised to find circles and ellipses, not just lines. In order to do this, simply repeat the algorithm above but use the parameters for circles and ellipses in the Hough space instead of just parameters for lines.
• When you increment the accumulator you can use a different value than 1. Instead you can calculate the gradient magnitude of the grayscale image and use that as an input to a continuously increasing function (such as the sigmoid function). This means that stronger edges get a higher impact in deciding where the final lines should be drawn and can give a better result.