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.

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; /*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; }

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!