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

   1 Hough Line Transform {#tutorial_hough_lines}
   2 ====================
   3
   4 @prev_tutorial{tutorial_canny_detector}
   5 @next_tutorial{tutorial_hough_circle}
   6
   7 Goal
   8 ----
   9
  10 In this tutorial you will learn how to:
  11
  12 -   Use the OpenCV functions **HoughLines()** and **HoughLinesP()** to detect lines in an
  13     image.
  14
  15 Theory
  16 ------
  17
  18 @note The explanation below belongs to the book **Learning OpenCV** by Bradski and Kaehler.
  19
  20 Hough Line Transform
  21 --------------------
  22
  23 -# The Hough Line Transform is a transform used to detect straight lines.
  24 -# To apply the Transform, first an edge detection pre-processing is desirable.
  25
  26 ### How does it work?
  27
  28 -#  As you know, a line in the image space can be expressed with two variables. For example:
  29
  30     -#  In the **Cartesian coordinate system:** Parameters: \f$(m,b)\f$.
  31     -#  In the **Polar coordinate system:** Parameters: \f$(r,\theta)\f$
  32
  33     ![](images/Hough_Lines_Tutorial_Theory_0.jpg)
  34
  35     For Hough Transforms, we will express lines in the *Polar system*. Hence, a line equation can be
  36     written as:
  37
  38     \f[y = \left ( -\dfrac{\cos \theta}{\sin \theta} \right ) x + \left ( \dfrac{r}{\sin \theta} \right )\f]
  39
  40 Arranging the terms: \f$r = x \cos \theta + y \sin \theta\f$
  41
  42 -#  In general for each point \f$(x_{0}, y_{0})\f$, we can define the family of lines that goes through
  43     that point as:
  44
  45     \f[r_{\theta} = x_{0} \cdot \cos \theta  + y_{0} \cdot \sin \theta\f]
  46
  47     Meaning that each pair \f$(r_{\theta},\theta)\f$ represents each line that passes by
  48     \f$(x_{0}, y_{0})\f$.
  49
  50 -#  If for a given \f$(x_{0}, y_{0})\f$ we plot the family of lines that goes through it, we get a
  51     sinusoid. For instance, for \f$x_{0} = 8\f$ and \f$y_{0} = 6\f$ we get the following plot (in a plane
  52     \f$\theta\f$ - \f$r\f$):
  53
  54     ![](images/Hough_Lines_Tutorial_Theory_1.jpg)
  55
  56     We consider only points such that \f$r > 0\f$ and \f$0< \theta < 2 \pi\f$.
  57
  58 -#  We can do the same operation above for all the points in an image. If the curves of two
  59     different points intersect in the plane \f$\theta\f$ - \f$r\f$, that means that both points belong to a
  60     same line. For instance, following with the example above and drawing the plot for two more
  61     points: \f$x_{1} = 4\f$, \f$y_{1} = 9\f$ and \f$x_{2} = 12\f$, \f$y_{2} = 3\f$, we get:
  62
  63     ![](images/Hough_Lines_Tutorial_Theory_2.jpg)
  64
  65     The three plots intersect in one single point \f$(0.925, 9.6)\f$, these coordinates are the
  66     parameters (\f$\theta, r\f$) or the line in which \f$(x_{0}, y_{0})\f$, \f$(x_{1}, y_{1})\f$ and
  67     \f$(x_{2}, y_{2})\f$ lay.
  68
  69 -#  What does all the stuff above mean? It means that in general, a line can be *detected* by
  70     finding the number of intersections between curves.The more curves intersecting means that the
  71     line represented by that intersection have more points. In general, we can define a *threshold*
  72     of the minimum number of intersections needed to *detect* a line.
  73 -#  This is what the Hough Line Transform does. It keeps track of the intersection between curves of
  74     every point in the image. If the number of intersections is above some *threshold*, then it
  75     declares it as a line with the parameters \f$(\theta, r_{\theta})\f$ of the intersection point.
  76
  77 ### Standard and Probabilistic Hough Line Transform
  78
  79 OpenCV implements two kind of Hough Line Transforms:
  80
  81 a.  **The Standard Hough Transform**
  82
  83 -   It consists in pretty much what we just explained in the previous section. It gives you as
  84     result a vector of couples \f$(\theta, r_{\theta})\f$
  85 -   In OpenCV it is implemented with the function **HoughLines()**
  86
  87 b.  **The Probabilistic Hough Line Transform**
  88
  89 -   A more efficient implementation of the Hough Line Transform. It gives as output the extremes
  90     of the detected lines \f$(x_{0}, y_{0}, x_{1}, y_{1})\f$
  91 -   In OpenCV it is implemented with the function **HoughLinesP()**
  92
  93 ###  What does this program do?
  94     -   Loads an image
  95     -   Applies a *Standard Hough Line Transform* and a *Probabilistic Line Transform*.
  96     -   Display the original image and the detected line in three windows.
  97
  98 Code
  99 ----
 100
 101 @add_toggle_cpp
 102 The sample code that we will explain can be downloaded from
 103 [here](https://raw.githubusercontent.com/opencv/opencv/master/samples/cpp/tutorial_code/ImgTrans/houghlines.cpp).
 104 A slightly fancier version (which shows both Hough standard and probabilistic
 105 with trackbars for changing the threshold values) can be found
 106 [here](https://raw.githubusercontent.com/opencv/opencv/master/samples/cpp/tutorial_code/ImgTrans/HoughLines_Demo.cpp).
 107 @include samples/cpp/tutorial_code/ImgTrans/houghlines.cpp
 108 @end_toggle
 109
 110 @add_toggle_java
 111 The sample code that we will explain can be downloaded from
 112 [here](https://raw.githubusercontent.com/opencv/opencv/master/samples/java/tutorial_code/ImgTrans/HoughLine/HoughLines.java).
 113 @include samples/java/tutorial_code/ImgTrans/HoughLine/HoughLines.java
 114 @end_toggle
 115
 116 @add_toggle_python
 117 The sample code that we will explain can be downloaded from
 118 [here](https://raw.githubusercontent.com/opencv/opencv/master/samples/python/tutorial_code/ImgTrans/HoughLine/hough_lines.py).
 119 @include samples/python/tutorial_code/ImgTrans/HoughLine/hough_lines.py
 120 @end_toggle
 121
 122 Explanation
 123 -----------
 124
 125 #### Load an image:
 126
 127 @add_toggle_cpp
 128 @snippet samples/cpp/tutorial_code/ImgTrans/houghlines.cpp load
 129 @end_toggle
 130
 131 @add_toggle_java
 132 @snippet samples/java/tutorial_code/ImgTrans/HoughLine/HoughLines.java load
 133 @end_toggle
 134
 135 @add_toggle_python
 136 @snippet samples/python/tutorial_code/ImgTrans/HoughLine/hough_lines.py load
 137 @end_toggle
 138
 139 #### Detect the edges of the image by using a Canny detector:
 140
 141 @add_toggle_cpp
 142 @snippet samples/cpp/tutorial_code/ImgTrans/houghlines.cpp edge_detection
 143 @end_toggle
 144
 145 @add_toggle_java
 146 @snippet samples/java/tutorial_code/ImgTrans/HoughLine/HoughLines.java edge_detection
 147 @end_toggle
 148
 149 @add_toggle_python
 150 @snippet samples/python/tutorial_code/ImgTrans/HoughLine/hough_lines.py edge_detection
 151 @end_toggle
 152
 153 Now we will apply the Hough Line Transform. We will explain how to use both OpenCV functions
 154 available for this purpose.
 155
 156 #### Standard Hough Line Transform:
 157 First, you apply the Transform:
 158
 159 @add_toggle_cpp
 160 @snippet samples/cpp/tutorial_code/ImgTrans/houghlines.cpp hough_lines
 161 @end_toggle
 162
 163 @add_toggle_java
 164 @snippet samples/java/tutorial_code/ImgTrans/HoughLine/HoughLines.java hough_lines
 165 @end_toggle
 166
 167 @add_toggle_python
 168 @snippet samples/python/tutorial_code/ImgTrans/HoughLine/hough_lines.py hough_lines
 169 @end_toggle
 170
 171 -       with the following arguments:
 172
 173         -   *dst*: Output of the edge detector. It should be a grayscale image (although in fact it
 174             is a binary one)
 175         -   *lines*: A vector that will store the parameters \f$(r,\theta)\f$ of the detected lines
 176         -   *rho* : The resolution of the parameter \f$r\f$ in pixels. We use **1** pixel.
 177         -   *theta*: The resolution of the parameter \f$\theta\f$ in radians. We use **1 degree**
 178             (CV_PI/180)
 179         -   *threshold*: The minimum number of intersections to "*detect*" a line
 180         -   *srn* and *stn*: Default parameters to zero. Check OpenCV reference for more info.
 181
 182 And then you display the result by drawing the lines.
 183 @add_toggle_cpp
 184 @snippet samples/cpp/tutorial_code/ImgTrans/houghlines.cpp draw_lines
 185 @end_toggle
 186
 187 @add_toggle_java
 188 @snippet samples/java/tutorial_code/ImgTrans/HoughLine/HoughLines.java draw_lines
 189 @end_toggle
 190
 191 @add_toggle_python
 192 @snippet samples/python/tutorial_code/ImgTrans/HoughLine/hough_lines.py draw_lines
 193 @end_toggle
 194
 195 #### Probabilistic Hough Line Transform
 196 First you apply the transform:
 197
 198 @add_toggle_cpp
 199 @snippet samples/cpp/tutorial_code/ImgTrans/houghlines.cpp hough_lines_p
 200 @end_toggle
 201
 202 @add_toggle_java
 203 @snippet samples/java/tutorial_code/ImgTrans/HoughLine/HoughLines.java hough_lines_p
 204 @end_toggle
 205
 206 @add_toggle_python
 207 @snippet samples/python/tutorial_code/ImgTrans/HoughLine/hough_lines.py hough_lines_p
 208 @end_toggle
 209
 210 -       with the arguments:
 211
 212         -   *dst*: Output of the edge detector. It should be a grayscale image (although in fact it
 213             is a binary one)
 214         -   *lines*: A vector that will store the parameters
 215             \f$(x_{start}, y_{start}, x_{end}, y_{end})\f$ of the detected lines
 216         -   *rho* : The resolution of the parameter \f$r\f$ in pixels. We use **1** pixel.
 217         -   *theta*: The resolution of the parameter \f$\theta\f$ in radians. We use **1 degree**
 218             (CV_PI/180)
 219         -   *threshold*: The minimum number of intersections to "*detect*" a line
 220         -   *minLinLength*: The minimum number of points that can form a line. Lines with less than
 221             this number of points are disregarded.
 222         -   *maxLineGap*: The maximum gap between two points to be considered in the same line.
 223
 224 And then you display the result by drawing the lines.
 225
 226 @add_toggle_cpp
 227 @snippet samples/cpp/tutorial_code/ImgTrans/houghlines.cpp draw_lines_p
 228 @end_toggle
 229
 230 @add_toggle_java
 231 @snippet samples/java/tutorial_code/ImgTrans/HoughLine/HoughLines.java draw_lines_p
 232 @end_toggle
 233
 234 @add_toggle_python
 235 @snippet samples/python/tutorial_code/ImgTrans/HoughLine/hough_lines.py draw_lines_p
 236 @end_toggle
 237
 238 #### Display the original image and the detected lines:
 239
 240 @add_toggle_cpp
 241 @snippet samples/cpp/tutorial_code/ImgTrans/houghlines.cpp imshow
 242 @end_toggle
 243
 244 @add_toggle_java
 245 @snippet samples/java/tutorial_code/ImgTrans/HoughLine/HoughLines.java imshow
 246 @end_toggle
 247
 248 @add_toggle_python
 249 @snippet samples/python/tutorial_code/ImgTrans/HoughLine/hough_lines.py imshow
 250 @end_toggle
 251
 252 #### Wait until the user exits the program
 253
 254 @add_toggle_cpp
 255 @snippet samples/cpp/tutorial_code/ImgTrans/houghlines.cpp exit
 256 @end_toggle
 257
 258 @add_toggle_java
 259 @snippet samples/java/tutorial_code/ImgTrans/HoughLine/HoughLines.java exit
 260 @end_toggle
 261
 262 @add_toggle_python
 263 @snippet samples/python/tutorial_code/ImgTrans/HoughLine/hough_lines.py exit
 264 @end_toggle
 265
 266 Result
 267 ------
 268
 269 @note
 270    The results below are obtained using the slightly fancier version we mentioned in the *Code*
 271     section. It still implements the same stuff as above, only adding the Trackbar for the
 272     Threshold.
 273
 274 Using an input image such as a [sudoku image](https://raw.githubusercontent.com/opencv/opencv/master/samples/data/sudoku.png).
 275 We get the following result by using the Standard Hough Line Transform:
 276 ![](images/hough_lines_result1.png)
 277 And by using the Probabilistic Hough Line Transform:
 278 ![](images/hough_lines_result2.png)
 279
 280 You may observe that the number of lines detected vary while you change the *threshold*. The
 281 explanation is sort of evident: If you establish a higher threshold, fewer lines will be detected
 282 (since you will need more points to declare a line detected).