Hough transform

For some arbitrary point, there are an infinite number of lines that can pass through it, for different values of and . If we look at parameter space for a point, (the space with and as coordinate axes), we get a line describing all sets of where the line passes through it.

Now if we graph out vs for two different points in image space, we will see that the lines in parameter space intersect. Because only one will pass through two different points.

We discretize this concept with an accumulator matrix, with and as the coordinate axes. For a set of given points, we calculate the parameter space line, and increment all cells in the accumulator matrix where the line intersects. (Basically the accumulator matrix is our graph, and we treat its 2 dimensions as m and c.). This way, the cell with the highest value at the end has the most amount of parameter space lines passing through it. And we therefore have and to describe our line.

The hough transform is the parameter space.

Now since, , we instead use the representation , since . And instead of lines in parameter space, we get sine waves. And so we will increment that accumulator matrix along the sine wave.

Similarly like with lines, we can create a hough transform for a set of points using the coordinates of the center of the circle as parameters (we are assuming that we know the radius). We will have to increment the accumulator matrix in the shape of circles, and then look at maximal points to figure out the center of the circle.