# 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.