Hough Transform

Today I will be explaining a very popular algorithm in the domain of Computer Vision known as the Hough Transform.I will start by explaining how the algorithm works and then I would be showing a sample implementation using this algorithm for detection of straight lines in Sheet Music.
So lets get started
What  does Wikipedia tells you?
The Hough transform is a feature extraction technique used in image analysis, computer vision, and digital image processing. The purpose of the technique is to find imperfect instances of objects within a certain class of shapes by a voting procedure. This voting procedure is carried out in a parameter space, from which object candidates are obtained as local maxima in a so-called accumulator space that is explicitly constructed by the algorithm for computing the Hough transform.

What is meant by a parameter space?


Let me explain it by considering the case of a line.
In 2D the equation of a line can be written as
y=mx+c

Here the parameters of the line are m and c as a different 
 values of the parameters will give a different line in the XY plane




lets rewrite this equation as c=-mx+y
Now we can visualize the same as point in MC plane with x and y as the parameters.

This is known as the parametric space in Hough transform.
So what is the advantage of using such a space ?

Each point in an XY plane can be mapped to a line in the parametric domain and each point in the parametric space can be mapped into a line in the actual XY domain. So consider two points in the XY plane . Consider the corresponding lines in the parametric space.The point of intersection gives the M and C values for the equation of the line joining these two points.This is the main idea used behind all the Hough transform. But there is a problem in this case of vertical lines. Hence for obtaining a generalized solution we use another parametric representation of a line

i.e r=Xcos(theta) + Ysin(theta)

Now our task is to figure out if there is a line in a given image. Assume that the image is a binary images with either zeros or ones. For each point in the image we can draw a line in the parametric space. 

We can define the parametric space with a double dimensional array and increment the those cells through which a line passes. If the points do in fact lie in a line, then the cell corresponding to that parameter (r,theta)will have a huge value compared to other cells . Hence we can get the exact equation of the line.

The same technique can be extended for any curve which can be represented in a parametric way. Thus we can find if some points do in fact lie on a particular curve.

Lets analyze the complexity of this method. Consider that we have N points . For each point we have to update a set of points in the parameter space. But we can choose to to much we have to split the parametric space and this can be under our control. Finally we have to find the maximum in a two dimensional array to obtain the required parameters. Hence the overall complexity is of O(N) . The constants can be quite large though.

This is the result of applying hough line transform on a sheet music. Even though there are multiple lines for a particular stave line those can be avoided by using a clever usage. 

Thanks for reading , and have a great day