OpenCV  3.2.0
Open Source Computer Vision
Hough Line Transform

.2.0+dfsg_doc_tutorials_imgproc_imgtrans_hough_lines_hough_lines

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)\)

    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\)):

    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:

    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

  • It consists in pretty much what we just explained in the previous section. It gives you as result a vector of couples \((\theta, r_{\theta})\)
  • In OpenCV it is implemented with the function cv::HoughLines

b. The Probabilistic Hough Line Transform

  • A more efficient implementation of the Hough Line Transform. It gives as output the extremes of the detected lines \((x_{0}, y_{0}, x_{1}, y_{1})\)
  • In OpenCV it is implemented with the function cv::HoughLinesP

Code

  1. What does this program do?
    • Loads an image
    • Applies either a Standard Hough Line Transform or a Probabilistic Line Transform.
    • Display the original image and the detected line in two windows.
  2. 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.
    #include <iostream>
    using namespace cv;
    using namespace std;
    static void help()
    {
    cout << "\nThis program demonstrates line finding with the Hough transform.\n"
    "Usage:\n"
    "./houghlines <image_name>, Default is ../data/pic1.png\n" << endl;
    }
    int main(int argc, char** argv)
    {
    cv::CommandLineParser parser(argc, argv,
    "{help h||}{@image|../data/pic1.png|}"
    );
    if (parser.has("help"))
    {
    help();
    return 0;
    }
    string filename = parser.get<string>("@image");
    if (filename.empty())
    {
    help();
    cout << "no image_name provided" << endl;
    return -1;
    }
    Mat src = imread(filename, 0);
    if(src.empty())
    {
    help();
    cout << "can not open " << filename << endl;
    return -1;
    }
    Mat dst, cdst;
    Canny(src, dst, 50, 200, 3);
    cvtColor(dst, cdst, COLOR_GRAY2BGR);
    #if 0
    vector<Vec2f> lines;
    HoughLines(dst, lines, 1, CV_PI/180, 100, 0, 0 );
    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, CV_AA);
    }
    #else
    vector<Vec4i> lines;
    HoughLinesP(dst, lines, 1, CV_PI/180, 50, 50, 10 );
    for( size_t i = 0; i < lines.size(); i++ )
    {
    Vec4i l = lines[i];
    line( cdst, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(0,0,255), 3, LINE_AA);
    }
    #endif
    imshow("source", src);
    imshow("detected lines", cdst);
    return 0;
    }

Explanation

  1. Load an image
    Mat src = imread(filename, 0);
    if(src.empty())
    {
    help();
    cout << "can not open " << filename << endl;
    return -1;
    }
  2. Detect the edges of the image by using a Canny detector
    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:
  3. Standard Hough Line Transform
    1. First, you apply the Transform:
      vector<Vec2f> lines;
      HoughLines(dst, lines, 1, CV_PI/180, 100, 0, 0 );
      with the following arguments:
      • dst: Output of the edge detector. It should be a grayscale image (although in fact it is a binary one)
      • lines: A vector that will store the parameters \((r,\theta)\) of the detected lines
      • rho : The resolution of the parameter \(r\) in pixels. We use 1 pixel.
      • theta: The resolution of the parameter \(\theta\) in radians. We use 1 degree (CV_PI/180)
      • threshold: The minimum number of intersections to "*detect*" a line
      • srn and stn: Default parameters to zero. Check OpenCV reference for more info.
    2. And then you display the result by drawing 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);
      }
  4. Probabilistic Hough Line Transform
    1. First you apply the transform:
      vector<Vec4i> lines;
      HoughLinesP(dst, lines, 1, CV_PI/180, 50, 50, 10 );
      with the arguments:
      • dst: Output of the edge detector. It should be a grayscale image (although in fact it is a binary one)
      • lines: A vector that will store the parameters \((x_{start}, y_{start}, x_{end}, y_{end})\) of the detected lines
      • rho : The resolution of the parameter \(r\) in pixels. We use 1 pixel.
      • theta: The resolution of the parameter \(\theta\) in radians. We use 1 degree (CV_PI/180)
      • threshold: The minimum number of intersections to "*detect*" a line
      • minLinLength: The minimum number of points that can form a line. Lines with less than this number of points are disregarded.
      • maxLineGap: The maximum gap between two points to be considered in the same line.
    2. And then you display the result by drawing the lines.
      for( size_t i = 0; i < lines.size(); i++ )
      {
      Vec4i l = lines[i];
      line( cdst, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(0,0,255), 3, LINE_AA);
      }
  5. Display the original image and the detected lines:
    imshow("source", src);
    imshow("detected lines", cdst);
  6. Wait until the user exits the program

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:

We get the following result by using the Probabilistic Hough Line Transform:

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

cv::Point_< int >
cv::HoughLines
void HoughLines(InputArray image, OutputArray lines, double rho, double theta, int threshold, double srn=0, double stn=0, double min_theta=0, double max_theta=CV_PI)
Finds lines in a binary image using the standard Hough transform.
imgproc.hpp
cv::Vec4i
Vec< int, 4 > Vec4i
Definition: matx.hpp:377
cv::cvtColor
void cvtColor(InputArray src, OutputArray dst, int code, int dstCn=0)
Converts an image from one color space to another.
cv::waitKey
int waitKey(int delay=0)
Waits for a pressed key.
CV_AA
#define CV_AA
Definition: imgproc_c.h:988
cv::Point_::y
_Tp y
Definition: types.hpp:176
cv::Point_::x
_Tp x
Definition: types.hpp:176
cv::Canny
void Canny(InputArray image, OutputArray edges, double threshold1, double threshold2, int apertureSize=3, bool L2gradient=false)
Finds edges in an image using the Canny algorithm .
highgui.hpp
cv::line
void line(InputOutputArray img, Point pt1, Point pt2, const Scalar &color, int thickness=1, int lineType=LINE_8, int shift=0)
Draws a line segment connecting two points.
cv::imread
Mat imread(const String &filename, int flags=IMREAD_COLOR)
Loads an image from a file.
cv::Mat::empty
bool empty() const
Returns true if the array has no elements.
cv::Vec
Template class for short numerical vectors, a partial case of Matx.
Definition: matx.hpp:306
imgcodecs.hpp
cvRound
int cvRound(double value)
Rounds floating-point number to the nearest integer.
Definition: fast_math.hpp:93
cv::LINE_AA
@ LINE_AA
antialiased line
Definition: core.hpp:218
cv::imshow
void imshow(const String &winname, InputArray mat)
Displays an image in the specified window.
cv::cudev::cos
__device__ __forceinline__ float1 cos(const uchar1 &a)
Definition: vec_math.hpp:294
cv::Scalar
Scalar_< double > Scalar
Definition: types.hpp:606
cv::Point
Point2i Point
Definition: types.hpp:183
cv::Mat
n-dimensional dense array class
Definition: mat.hpp:741
i
for i
Definition: modelConvert.m:63
cv::HoughLinesP
void HoughLinesP(InputArray image, OutputArray lines, double rho, double theta, int threshold, double minLineLength=0, double maxLineGap=0)
Finds line segments in a binary image using the probabilistic Hough transform.
cv::CommandLineParser
Designed for command line parsing.
Definition: utility.hpp:735
cv
Definition: affine.hpp:52
cv::cudev::sin
__device__ __forceinline__ float1 sin(const uchar1 &a)
Definition: vec_math.hpp:285
CV_PI
#define CV_PI
Definition: cvdef.h:302
cv::COLOR_GRAY2BGR
@ COLOR_GRAY2BGR
Definition: imgproc.hpp:540