Summary:Hough transform is a feature extraction algorithm widely used in digital image analysis. It identifies objects with specified shapes by letting all edge pixels in the image “vote” and extract candidates with the highest votes. The classical Hough transform is associated with the identification of straight lines, but with some modification, the algorithm can be used to detect objects of arbitrary shapes (usually circles, ellipses) in an image. Therefore, Hough transform has various applications in the field of computer vision. Samir and I implemented Hough transform to detect straight lines and circles in real world images and the results are below:

You can access the applications here for more details and try the algorithm on your own image!

Line Detection with Hough Transform

Circle Detection with Hough Transform

For people who want a bit more of the theory behind:

The voting procedure in Hough transform starts with an edge detector (we used the sobel edge detector in the applications). After locating all the edge pixels, the program will iterate through each of the pixels and record their “votes”. It is important to address that the voting procedure is completed in parameter space. For example, a straight line is usually in the form of y = a*x+b, the parameter space will be in terms of a and b. Hence y=2*x + 3 will be a point (2,3)  in the a-b space. However, notice that we cannot represent vertical lines with this system; it would take infinite memory to store a vertical line. Thus we use the polar coordinates system x*cos(θ) + y*sin(θ) - p = 0 instead, resulting in a θ -p space. Note that an image pixel (x₁,y₁) is represented by the intersection of all lines that satisfy x₁*cos(θ) + y₁*sin(θ) - p = 0, which in θ-p space is denoted as a sinusoidal curve. Hence the intersection of two different sinusoidal curves in θ-p space is essentially a unique, straight line that passes through two different image pixels. An intersection of 500 votes means that specific line passes through 500 edge pixels, implying that it is likely a solid contour line in the original image. In this way, by converting all edge pixels to sinusoidal curves in θ-p space, the algorithm is letting all pixels “vote”. In order to record the sinusoidal curves, we need an accumulator of θ * p dimensions. In the line detection application we used a matrix such that <= θ <= 180 and -sqrt(r² +c² ) <= p <= sqrt(r² +c² ), where r and c are the height (rows) and width (columns) of the image.

The voting procedure for circle detection is similar; the difference is in how we construct the accumulator to accommodate different parametrization for circles. Notice that a circle has three essential pieces of information, the x,y coordinates of centre and the radius. This suggests that our accumulator might have to be in three dimensions. In practice, circular Hough transform is usually performed with known or estimated radius, when the radius is not known, the most straightforward solution is indeed to test a range of possible radii with a 3-dimensional accumulator. However, this might be quite expensive, especially for images with high level of details.

Feel free to leave a comment if you have any question  :)  or if you can think of a good joke about Hough transform