Hough Line Transform

 

Hough Line transform is a technique used to detect straight lines in an image. This algorithm can detect all imperfect instances of a line in a given image ie, this algorithm can detect lines even if they are not perfectly straight. The detection of line is carried out by a voting process.  Before examining the algorithm in detail we need to demystify the mathematics behind it.

The Mathematics

There are several form of equations in which a line can be represented. The most common and familiar one should be the “slope-intercept” form.

y=mx+b

where

~m is the slope

~b is the y-intercept.

In this equation the slope ~m and the y-intercept ~b are known for a given line. ~x and ~y are variables. So by varying the value of ~x (or ~y) you can find the corresponding value of ~y(or ~x)

From the above equation we can derive another form of equation called the “Double Intercept” form.

x/a+y/b=1 ……………..equation 1

where

~a is the x-intercept.

~b is the y-intercept.

The double intercept form will be used to derive a new form of equation called the “Normal Form” which is used in the Hough Line Transform. The reason for using normal form is that the “slope-intercept” from fails in case of vertical lines and the Double intercept form fails because of the large range of ~a and ~b.

Derivation:

Consider a line ~L  which intersects the y-axis at point A (0,b) and x-axis at point B (a,0). A line segment ~OP having one end point on the origin intersects the line ~L  at right angles at point ~P.

OP makes an angle ~theta with the a-axis. The length of OP is ~r.From the figure, Length(OB) = a and Length(OA) = b

Consider Delta~POB.

Cos theta = OP/OB

Cos theta = r/a

a = r/{Cos theta} ……………..equation 2

Now consider Delta~POA.

Angle(POA) =90.

Angle(POA) =90- theta because Angle(BOA) =90.

Therefore Angle(PAO) =theta

Sin theta = OP/OA

Sin theta = r/b

b = r/{Sin theta} ……………..equation 3

 

Substituting the values of a and b in equation 1 with equation 2 and 3 we get

x/{r/Cos theta}+y/{r/Sin theta}=1

{x{ Cos theta}/r }+ {y{Sin theta}/r}=1

{x{ Cos theta} }+ {y{Sin theta}}=r ……………..equation 4

 Straight Line Detection:

Lets see how the above equation can be used to find straight lines.

Given the values of theta and r, we can vary the value of x and find the corresponding value of y. Plotting (x,y) will give us a straight line.

For example, for theta = 30 degrees and r=5units the graph would look like this.

If we keep the value x and y constant and vary the value of  theta we can find the corresponding values of  r. For each  (theta,r) pair we can plot a line in x-y coordinate and all these lines will pass through  (x,y).

For example, let (x,y) be(5,4). Let theta = {lbrace}15,30,45{rbrace}. After substituting these values in  the  equation we get r={lbrace}5.86,6.33,6.36{rbrace}. When we plot the lines formed by the  (theta,r) pairs, they will all pass through  (5,4)

 

Now consider three points (7,2),(1,8),(5,4). Let theta = {lbrace}15,30,45{rbrace}.

The corresponding values of  r are as follows.

(1,8) (5,4) (7,2)
theta r theta r theta r
15 3.03 15 5.86 15 7.27
30 4.86 30 6.33 30 7.06
45 6.36 45 6.36 45 6.36

 

If a line passes through a given point (x,y), then the corresponding (theta,r) gets a vote from that point. The line with (theta,r) that gets maximum number of votes passes through maximum number of points.

In the above example, (45,6.36) got three votes, that means it passes through all three point. If (theta,r) gets n number of votes then it passes through n number of points.

For simplicity we considered only 3 angles and 3 points. The number of lines that can pass through a point is infinite. If we plot all the possible values of theta and r for the point (5,4) the graph would look like this.

Pay Attention: We are not plotting the lines in this graph. We are directly plotting the values of theta and r. theta is on x-axis and is given in radian not degrees. r is on y-axis. This graph represents the (theta,r) values of lines that pass through the point (5,4)

Similarly we can plot graph for the points (7,2), (5,4) and (1,8). We observe that all the 3 curves intersect at a point. The point of intersection is (45,6.36).

<p >But for practical application we can consider a small subset of angles; let’s say theta = {lbrace}0,1,2,3 ..... 177,178,179{rbrace}. Here we are considering only 180 values for theta and we get 180 values for r. So effectively we are finding 180 lines that pass through a point.

Algorithm

Preprocessing: Canny edge detector is applied to extract the edges.
Step 1: Calculate the maximum and minimum value of theta and r. For practical implementation theta and r are integral values. Select appropriate value for threshold t.
Step 2: Initialize a 2-D array A of size max(theta)xmax(r) and fill it with zeros.
Step 3: For each white pixel find value of r corresponding to each value of theta. Increment A(theta,r).
Step 5: Search for values of A(theta,r) which is above the threshold;
Step 4: Draw the lines.

Code

I have used OpenCV library for this program. It was compiled using GCC 4.5 under Linux OS (Linux Mint 13)

#include <iostream>
#include "cv.h"
#include "highgui.h"
#include <math.h>
#define PI 3.14159265f
using namespace cv;

int main()
{
    int 	max_r;			//Maximum magnitude of r
    int		max_theta=179;	//Maximum value of theta.
    int 	threshold=60;	//Mimimum number of votes required by(theata,r) to form a straight line.
	int 	img_width;		//Width of the image
	int		img_height;		//Height of the image
	int		num_theta=180;	//Number of values of theta (0 - 179 degrees)
	int		num_r;			//Number of values of r.
	int 	*accumulator;	//accumulator to collect votes.
	long 	acc_size;		//size of the accumulator in bytes.
	float	Sin[num_theta];	//Array to store pre-calculated vales of sin(theta)
	float 	Cos[num_theta];	//Array to store pre-calculated vales of cos(theta)
	uchar 	*img_data;		//pointer to image data for efficient access.
	int 	i,j;
	Mat 	src;
	Mat		dst;

	/*Read and Display the image*/
	Mat image = imread("poly.png");
	namedWindow( "Polygon", 1 );
	imshow( "Polygon", image);
	//convert color to gray scale image
	cvtColor(image, src, CV_BGR2GRAY);
	/*Initializations*/
	img_width = src.cols;
	img_height = src.rows;

		//calculating maximum value of r. Round it off to nearest integer.
	max_r = round(sqrt( (img_width*img_width) + (img_height*img_height)));
		//calculating the number vales r can take. -max_r <= r<= max_r
	num_r = (max_r *2) +1;
		//pre-compute the values of sin(theta) and cos(theta).
	for(i=0;i<=max_theta;i++)
		{
			Sin[i] = sin(i * (PI/180));
			Cos[i] = cos(i * (PI/180));
		}
		//Initializing the accumulator. Conceptually it is a 2-D matrix with dimension r x theta
	accumulator = new int[num_theta * num_r];
		//calculating size of accumulator in bytes.
	acc_size = sizeof(int)*num_theta * num_r;
	//Initializing elements of accumulator to zero.
	memset(accumulator,0,acc_size);
	//extracting the edges.
	Canny(src,dst,50,200,3);

	//Getting the image data from Mat dst
	img_data = dst.data;
	//Loop through all the pixels. Each pixel is represented by 1 byte.
	for(i=0;i<img_height;i++)
	{
		for(j=0;j<img_width;j++)
		{
			//Getting the pixel value.
			int val =img_data[i*img_width+j];

			if(val>0)
			{
				//if pixel is not black do the following.
				//For that pixel find the the values of r for corresponding value of theta.
				//Value of r can be negative. (See the graph)
				//Minimum value of r is -max_r.
				//Conceptually the array looks like this
				//	   		0  1  2  3  4  5  6  .. 178  179	<---degrees
				// -max_r  |  |  |  |  |  |  |  |  |    |   |
				// -max_r+1|  |  |  |  |  |  |  |  |    |   |
				// -max_r+2|  |  |  |  |  |  |  |  |    |   |
				//   ...   |  |  |  |  |  |  |  |  |    |   |
				//	  0	   |  |  |  |  |  |  |  |  |    |   |
				//	  1    |  |  |  |  |  |  |  |  |    |   |
				//	  2    |  |  |  |  |  |  |  |  |    |   |
				//	 ...   |  |  |  |  |  |  |  |  |    |   |
				//	 max_r |  |  |  |  |  |  |  |  |    |   |
				//
				for(int t=0;t<=max_theta;t++)
				{
					//calculating the values of r for theta= t , x= j and y = i;
					int _r = round(j*Cos[t] + i*Sin[t]);
					//calculating the row index of _r in the accumulator.
					int r_index = (max_r+_r);
					//Registering the vote by incrementing the value of accumulator[r][theta]
					accumulator[r_index*num_theta + t]++;

				}

			}
		}
	}

	//Looping through each element in the accumulator
	for(int r_index=0;r_index<num_r;r_index++)
	{
		for(j=0;j<num_theta;j++)
		{
			//retrieve the votes.
			int votes = accumulator[r_index*num_theta+j];
			if(votes>threshold)
			{
				//if votes receive is greater than the threshold

				//getting the value of theta
				int _theta=j;
				//getting the value of r
				int _r = r_index-max_r;

				//Calculating points to draw the line.
				Point pt1, pt2;
				pt1.x =0;
				pt1.y =round((_r - pt1.x*Cos[_theta])/Sin[_theta]);
				pt2.x =img_width;
			    pt2.y =round((_r - pt2.x*Cos[_theta])/Sin[_theta]);
			    //Drawing the line.
				line( image, pt1, pt2, Scalar(0,255,0), 3, CV_AA);
			}

		}
	}
	namedWindow("Detected Lines", 1 );
	imshow( "Detected Lines",image);
	//Free the memory allocated to accumulator.
	delete[] accumulator;
	waitKey(0);

	return 0;
}

Output:

One thought on “Hough Line Transform

  1. Edward

    Hi! I could have sworn I’ve been to this blog before but after checking through some of the post I realized it’s new to me.
    Nonetheless, I’m definitely delighted I found it
    and I’ll be bookmarking and checking back frequently!

Leave a Reply

Your email address will not be published.


*

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>