Processing math: 100%
OpenCV  
Open Source Computer Vision
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
Hough Line Transform

Prev Tutorial: Canny Edge Detector

Next Tutorial: Hough Circle Transform

Original author Ana Huamán
Compatibility OpenCV >= 3.0

Goal

In this tutorial you will learn how to:

Theory

Note
The explanation below belongs to the book Learning OpenCV by Bradski and Kaehler.

Hough Line Transform

  1. The Hough Line Transform is a transform used to detect straight lines.
  2. To apply the Transform, first an edge detection pre-processing is desirable.

How does it work?

  1. As you know, a line in the image space can be expressed with two variables. For example:

    1. In the Cartesian coordinate system: Parameters: (m,b).
    2. In the Polar coordinate system: Parameters: (r,\theta)
    Hough_Lines_Tutorial_Theory_0.jpg

    For Hough Transforms, we will express lines in the Polar system. Hence, a line equation can be written as:

    y = \left ( -\dfrac{\cos \theta}{\sin \theta} \right ) x + \left ( \dfrac{r}{\sin \theta} \right )

Arranging the terms: r = x \cos \theta + y \sin \theta

  1. In general for each point (x_{0}, y_{0}), we can define the family of lines that goes through that point as:

    r_{\theta} = x_{0} \cdot \cos \theta + y_{0} \cdot \sin \theta

    Meaning that each pair (r_{\theta},\theta) represents each line that passes by (x_{0}, y_{0}).

  2. If for a given (x_{0}, y_{0}) we plot the family of lines that goes through it, we get a sinusoid. For instance, for x_{0} = 8 and y_{0} = 6 we get the following plot (in a plane \theta - r):

    Hough_Lines_Tutorial_Theory_1.jpg

    We consider only points such that r > 0 and 0< \theta < 2 \pi.

  3. We can do the same operation above for all the points in an image. If the curves of two different points intersect in the plane \theta - r, that means that both points belong to a same line. For instance, following with the example above and drawing the plot for two more points: x_{1} = 4, y_{1} = 9 and x_{2} = 12, y_{2} = 3, we get:

    Hough_Lines_Tutorial_Theory_2.jpg

    The three plots intersect in one single point (0.925, 9.6), these coordinates are the parameters ( \theta, r) or the line in which (x_{0}, y_{0}), (x_{1}, y_{1}) and (x_{2}, y_{2}) lay.

  4. What does all the stuff above mean? It means that in general, a line can be detected by finding the number of intersections between curves.The more curves intersecting means that the line represented by that intersection have more points. In general, we can define a threshold of the minimum number of intersections needed to detect a line.
  5. This is what the Hough Line Transform does. It keeps track of the intersection between curves of every point in the image. If the number of intersections is above some threshold, then it declares it as a line with the parameters (\theta, r_{\theta}) of the intersection point.

Standard and Probabilistic Hough Line Transform

OpenCV implements two kind of Hough Line Transforms:

a. The Standard Hough Transform

b. The Probabilistic Hough Line Transform

What does this program do?

Code

The sample code that we will explain can be downloaded from here. A slightly fancier version (which shows both Hough standard and probabilistic with trackbars for changing the threshold values) can be found here.

using namespace cv;
using namespace std;
int main(int argc, char** argv)
{
// Declare the output variables
Mat dst, cdst, cdstP;
const char* default_file = "sudoku.png";
const char* filename = argc >=2 ? argv[1] : default_file;
// Loads an image
// Check if image is loaded fine
if(src.empty()){
printf(" Error opening image\n");
printf(" Program Arguments: [image_name -- default %s] \n", default_file);
return -1;
}
// Edge detection
Canny(src, dst, 50, 200, 3);
// Copy edges to the images that will display the results in BGR
cvtColor(dst, cdst, COLOR_GRAY2BGR);
cdstP = cdst.clone();
// Standard Hough Line Transform
vector<Vec2f> lines; // will hold the results of the detection
HoughLines(dst, lines, 1, CV_PI/180, 150, 0, 0 ); // runs the actual detection
// Draw the lines
for( size_t i = 0; i < lines.size(); i++ )
{
float rho = lines[i][0], theta = lines[i][1];
Point pt1, pt2;
double a = cos(theta), b = sin(theta);
double x0 = a*rho, y0 = b*rho;
pt1.x = cvRound(x0 + 1000*(-b));
pt1.y = cvRound(y0 + 1000*(a));
pt2.x = cvRound(x0 - 1000*(-b));
pt2.y = cvRound(y0 - 1000*(a));
line( cdst, pt1, pt2, Scalar(0,0,255), 3, LINE_AA);
}
// Probabilistic Line Transform
vector<Vec4i> linesP; // will hold the results of the detection
HoughLinesP(dst, linesP, 1, CV_PI/180, 50, 50, 10 ); // runs the actual detection
// Draw the lines
for( size_t i = 0; i < linesP.size(); i++ )
{
Vec4i l = linesP[i];
line( cdstP, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(0,0,255), 3, LINE_AA);
}
// Show results
imshow("Source", src);
imshow("Detected Lines (in red) - Standard Hough Line Transform", cdst);
imshow("Detected Lines (in red) - Probabilistic Line Transform", cdstP);
// Wait and Exit
return 0;
}

Explanation

Load an image:

const char* default_file = "sudoku.png";
const char* filename = argc >=2 ? argv[1] : default_file;
// Loads an image
Mat src = imread( samples::findFile( filename ), IMREAD_GRAYSCALE );
// Check if image is loaded fine
if(src.empty()){
printf(" Error opening image\n");
printf(" Program Arguments: [image_name -- default %s] \n", default_file);
return -1;
}

Detect the edges of the image by using a Canny detector:

// Edge detection
Canny(src, dst, 50, 200, 3);

Now we will apply the Hough Line Transform. We will explain how to use both OpenCV functions available for this purpose.

Standard Hough Line Transform:

First, you apply the Transform:

// Standard Hough Line Transform
vector<Vec2f> lines; // will hold the results of the detection
HoughLines(dst, lines, 1, CV_PI/180, 150, 0, 0 ); // runs the actual detection

And then you display the result by drawing the lines.

// Draw the lines
for( size_t i = 0; i < lines.size(); i++ )
{
float rho = lines[i][0], theta = lines[i][1];
Point pt1, pt2;
double a = cos(theta), b = sin(theta);
double x0 = a*rho, y0 = b*rho;
pt1.x = cvRound(x0 + 1000*(-b));
pt1.y = cvRound(y0 + 1000*(a));
pt2.x = cvRound(x0 - 1000*(-b));
pt2.y = cvRound(y0 - 1000*(a));
line( cdst, pt1, pt2, Scalar(0,0,255), 3, LINE_AA);
}

Probabilistic Hough Line Transform

First you apply the transform:

// Probabilistic Line Transform
vector<Vec4i> linesP; // will hold the results of the detection
HoughLinesP(dst, linesP, 1, CV_PI/180, 50, 50, 10 ); // runs the actual detection

And then you display the result by drawing the lines.

// Draw the lines
for( size_t i = 0; i < linesP.size(); i++ )
{
Vec4i l = linesP[i];
line( cdstP, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(0,0,255), 3, LINE_AA);
}

Display the original image and the detected lines:

// Show results
imshow("Source", src);
imshow("Detected Lines (in red) - Standard Hough Line Transform", cdst);
imshow("Detected Lines (in red) - Probabilistic Line Transform", cdstP);

Wait until the user exits the program

// Wait and Exit
return 0;

Result

Note
The results below are obtained using the slightly fancier version we mentioned in the Code section. It still implements the same stuff as above, only adding the Trackbar for the Threshold.

Using an input image such as a sudoku image. We get the following result by using the Standard Hough Line Transform:

hough_lines_result1.png

And by using the Probabilistic Hough Line Transform:

hough_lines_result2.png

You may observe that the number of lines detected vary while you change the threshold. The explanation is sort of evident: If you establish a higher threshold, fewer lines will be detected (since you will need more points to declare a line detected).