doc/tutorials/imgproc/imgtrans/hough_lines/hough_lines.markdown

   1 Hough Line Transform {#tutorial_hough_lines}
   2 ====================
   3
   4 Goal
   5 ----
   6
   7 In this tutorial you will learn how to:
   8
   9 -   Use the OpenCV functions @ref cv::HoughLines and @ref cv::HoughLinesP to detect lines in an
  10     image.
  11
  12 Theory
  13 ------
  14
  15 @note The explanation below belongs to the book **Learning OpenCV** by Bradski and Kaehler.
  16
  17 Hough Line Transform
  18 --------------------
  19
  20 -# The Hough Line Transform is a transform used to detect straight lines.
  21 -# To apply the Transform, first an edge detection pre-processing is desirable.
  22
  23 ### How does it work?
  24
  25 -#  As you know, a line in the image space can be expressed with two variables. For example:
  26
  27     -#  In the **Cartesian coordinate system:** Parameters: \f$(m,b)\f$.
  28     -#  In the **Polar coordinate system:** Parameters: \f$(r,\theta)\f$
  29
  30     ![](images/Hough_Lines_Tutorial_Theory_0.jpg)
  31
  32     For Hough Transforms, we will express lines in the *Polar system*. Hence, a line equation can be
  33     written as:
  34
  35     \f[y = \left ( -\dfrac{\cos \theta}{\sin \theta} \right ) x + \left ( \dfrac{r}{\sin \theta} \right )\f]
  36
  37 Arranging the terms: \f$r = x \cos \theta + y \sin \theta\f$
  38
  39 -#  In general for each point \f$(x_{0}, y_{0})\f$, we can define the family of lines that goes through
  40     that point as:
  41
  42     \f[r_{\theta} = x_{0} \cdot \cos \theta  + y_{0} \cdot \sin \theta\f]
  43
  44     Meaning that each pair \f$(r_{\theta},\theta)\f$ represents each line that passes by
  45     \f$(x_{0}, y_{0})\f$.
  46
  47 -#  If for a given \f$(x_{0}, y_{0})\f$ we plot the family of lines that goes through it, we get a
  48     sinusoid. For instance, for \f$x_{0} = 8\f$ and \f$y_{0} = 6\f$ we get the following plot (in a plane
  49     \f$\theta\f$ - \f$r\f$):
  50
  51     ![](images/Hough_Lines_Tutorial_Theory_1.jpg)
  52
  53     We consider only points such that \f$r > 0\f$ and \f$0< \theta < 2 \pi\f$.
  54
  55 -#  We can do the same operation above for all the points in an image. If the curves of two
  56     different points intersect in the plane \f$\theta\f$ - \f$r\f$, that means that both points belong to a
  57     same line. For instance, following with the example above and drawing the plot for two more
  58     points: \f$x_{1} = 4\f$, \f$y_{1} = 9\f$ and \f$x_{2} = 12\f$, \f$y_{2} = 3\f$, we get:
  59
  60     ![](images/Hough_Lines_Tutorial_Theory_2.jpg)
  61
  62     The three plots intersect in one single point \f$(0.925, 9.6)\f$, these coordinates are the
  63     parameters (\f$\theta, r\f$) or the line in which \f$(x_{0}, y_{0})\f$, \f$(x_{1}, y_{1})\f$ and
  64     \f$(x_{2}, y_{2})\f$ lay.
  65
  66 -#  What does all the stuff above mean? It means that in general, a line can be *detected* by
  67     finding the number of intersections between curves.The more curves intersecting means that the
  68     line represented by that intersection have more points. In general, we can define a *threshold*
  69     of the minimum number of intersections needed to *detect* a line.
  70 -#  This is what the Hough Line Transform does. It keeps track of the intersection between curves of
  71     every point in the image. If the number of intersections is above some *threshold*, then it
  72     declares it as a line with the parameters \f$(\theta, r_{\theta})\f$ of the intersection point.
  73
  74 ### Standard and Probabilistic Hough Line Transform
  75
  76 OpenCV implements two kind of Hough Line Transforms:
  77
  78 a.  **The Standard Hough Transform**
  79
  80 -   It consists in pretty much what we just explained in the previous section. It gives you as
  81     result a vector of couples \f$(\theta, r_{\theta})\f$
  82 -   In OpenCV it is implemented with the function @ref cv::HoughLines
  83
  84 b.  **The Probabilistic Hough Line Transform**
  85
  86 -   A more efficient implementation of the Hough Line Transform. It gives as output the extremes
  87     of the detected lines \f$(x_{0}, y_{0}, x_{1}, y_{1})\f$
  88 -   In OpenCV it is implemented with the function @ref cv::HoughLinesP
  89
  90 Code
  91 ----
  92
  93 -#  **What does this program do?**
  94     -   Loads an image
  95     -   Applies either a *Standard Hough Line Transform* or a *Probabilistic Line Transform*.
  96     -   Display the original image and the detected line in two windows.
  97
  98 -#  The sample code that we will explain can be downloaded from [here](https://github.com/opencv/opencv/tree/master/samples/cpp/houghlines.cpp). A slightly fancier version
  99     (which shows both Hough standard and probabilistic with trackbars for changing the threshold
 100     values) can be found [here](https://github.com/opencv/opencv/tree/master/samples/cpp/tutorial_code/ImgTrans/HoughLines_Demo.cpp).
 101     @include samples/cpp/houghlines.cpp
 102
 103 Explanation
 104 -----------
 105
 106 -#  Load an image
 107     @code{.cpp}
 108     Mat src = imread(filename, 0);
 109     if(src.empty())
 110     {
 111       help();
 112       cout << "can not open " << filename << endl;
 113       return -1;
 114     }
 115     @endcode
 116 -#  Detect the edges of the image by using a Canny detector
 117     @code{.cpp}
 118     Canny(src, dst, 50, 200, 3);
 119     @endcode
 120     Now we will apply the Hough Line Transform. We will explain how to use both OpenCV functions
 121     available for this purpose:
 122
 123 -#  **Standard Hough Line Transform**
 124     -#  First, you apply the Transform:
 125         @code{.cpp}
 126         vector<Vec2f> lines;
 127         HoughLines(dst, lines, 1, CV_PI/180, 100, 0, 0 );
 128         @endcode
 129         with the following arguments:
 130
 131         -   *dst*: Output of the edge detector. It should be a grayscale image (although in fact it
 132             is a binary one)
 133         -   *lines*: A vector that will store the parameters \f$(r,\theta)\f$ of the detected lines
 134         -   *rho* : The resolution of the parameter \f$r\f$ in pixels. We use **1** pixel.
 135         -   *theta*: The resolution of the parameter \f$\theta\f$ in radians. We use **1 degree**
 136             (CV_PI/180)
 137         -   *threshold*: The minimum number of intersections to "*detect*" a line
 138         -   *srn* and *stn*: Default parameters to zero. Check OpenCV reference for more info.
 139
 140     -#  And then you display the result by drawing the lines.
 141         @code{.cpp}
 142         for( size_t i = 0; i < lines.size(); i++ )
 143         {
 144           float rho = lines[i][0], theta = lines[i][1];
 145           Point pt1, pt2;
 146           double a = cos(theta), b = sin(theta);
 147           double x0 = a*rho, y0 = b*rho;
 148           pt1.x = cvRound(x0 + 1000*(-b));
 149           pt1.y = cvRound(y0 + 1000*(a));
 150           pt2.x = cvRound(x0 - 1000*(-b));
 151           pt2.y = cvRound(y0 - 1000*(a));
 152           line( cdst, pt1, pt2, Scalar(0,0,255), 3, LINE_AA);
 153         }
 154         @endcode
 155 -#  **Probabilistic Hough Line Transform**
 156     -#  First you apply the transform:
 157         @code{.cpp}
 158         vector<Vec4i> lines;
 159         HoughLinesP(dst, lines, 1, CV_PI/180, 50, 50, 10 );
 160         @endcode
 161         with the arguments:
 162
 163         -   *dst*: Output of the edge detector. It should be a grayscale image (although in fact it
 164             is a binary one)
 165         -   *lines*: A vector that will store the parameters
 166             \f$(x_{start}, y_{start}, x_{end}, y_{end})\f$ of the detected lines
 167         -   *rho* : The resolution of the parameter \f$r\f$ in pixels. We use **1** pixel.
 168         -   *theta*: The resolution of the parameter \f$\theta\f$ in radians. We use **1 degree**
 169             (CV_PI/180)
 170         -   *threshold*: The minimum number of intersections to "*detect*" a line
 171         -   *minLinLength*: The minimum number of points that can form a line. Lines with less than
 172             this number of points are disregarded.
 173         -   *maxLineGap*: The maximum gap between two points to be considered in the same line.
 174
 175     -#  And then you display the result by drawing the lines.
 176         @code{.cpp}
 177         for( size_t i = 0; i < lines.size(); i++ )
 178         {
 179           Vec4i l = lines[i];
 180           line( cdst, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(0,0,255), 3, LINE_AA);
 181         }
 182         @endcode
 183 -#  Display the original image and the detected lines:
 184     @code{.cpp}
 185     imshow("source", src);
 186     imshow("detected lines", cdst);
 187     @endcode
 188 -#  Wait until the user exits the program
 189     @code{.cpp}
 190     waitKey();
 191     @endcode
 192
 193 Result
 194 ------
 195
 196 @note
 197    The results below are obtained using the slightly fancier version we mentioned in the *Code*
 198     section. It still implements the same stuff as above, only adding the Trackbar for the
 199     Threshold.
 200
 201 Using an input image such as:
 202
 203 ![](images/Hough_Lines_Tutorial_Original_Image.jpg)
 204
 205 We get the following result by using the Probabilistic Hough Line Transform:
 206
 207 ![](images/Hough_Lines_Tutorial_Result.jpg)
 208
 209 You may observe that the number of lines detected vary while you change the *threshold*. The
 210 explanation is sort of evident: If you establish a higher threshold, fewer lines will be detected
 211 (since you will need more points to declare a line detected).