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.

where

is the slope

is the y-intercept.

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

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

……………..

where

is the x-intercept.

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

Derivation:

Consider a line   which intersects the y-axis at point and x-axis at point . A line segment  having one end point on the origin intersects the line   at right angles at point .

makes an angle  with the a-axis. The length of  is .From the figure,  and

Consider .

……………..

Now consider .

.

because .

Therefore

……………..

Substituting the values of  in  with  we get

……………..

### Straight Line Detection:

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

Given the values of  and , we can vary the value of  and find the corresponding value of . Plotting  will give us a straight line.

For example, for  degrees and units the graph would look like this.

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

For example, let  be. Let . After substituting these values in  the   we get . When we plot the lines formed by the   pairs, they will all pass through

Now consider three points . Let .

The corresponding values of   are as follows.

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 , then the corresponding gets a vote from that point. The line with that gets maximum number of votes passes through maximum number of points.

In the above example, got three votes, that means it passes through all three point. If gets number of votes then it passes through 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 and for the point the graph would look like this.

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

Similarly we can plot graph for the points , and . We observe that all the 3 curves intersect at a point. The point of intersection is .

<p >But for practical application we can consider a small subset of angles; let’s say . Here we are considering only 180 values for and we get 180 values for . 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 and . For practical implementation and are integral values. Select appropriate value for threshold .
Step 2: Initialize a 2-D array A of size x and fill it with zeros.
Step 3: For each white pixel find value of corresponding to each value of . Increment .
Step 5: Search for values of 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;

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++)
{
{

//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. 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!