doc/tutorials/features2d/trackingmotion/harris_detector/harris_detector.markdown

   1 Harris corner detector {#tutorial_harris_detector}
   2 ======================
   3
   4 @next_tutorial{tutorial_good_features_to_track}
   5
   6 Goal
   7 ----
   8
   9 In this tutorial you will learn:
  10
  11 -   What features are and why they are important
  12 -   Use the function @ref cv::cornerHarris to detect corners using the Harris-Stephens method.
  13
  14 Theory
  15 ------
  16
  17 ### What is a feature?
  18
  19 -   In computer vision, usually we need to find matching points between different frames of an
  20     environment. Why? If we know how two images relate to each other, we can use *both* images to
  21     extract information of them.
  22 -   When we say **matching points** we are referring, in a general sense, to *characteristics* in
  23     the scene that we can recognize easily. We call these characteristics **features**.
  24 -   **So, what characteristics should a feature have?**
  25     -   It must be *uniquely recognizable*
  26
  27 ### Types of Image Features
  28
  29 To mention a few:
  30
  31 -   Edges
  32 -   **Corners** (also known as interest points)
  33 -   Blobs (also known as regions of interest )
  34
  35 In this tutorial we will study the *corner* features, specifically.
  36
  37 ### Why is a corner so special?
  38
  39 -   Because, since it is the intersection of two edges, it represents a point in which the
  40     directions of these two edges *change*. Hence, the gradient of the image (in both directions)
  41     have a high variation, which can be used to detect it.
  42
  43 ### How does it work?
  44
  45 -   Let's look for corners. Since corners represents a variation in the gradient in the image, we
  46     will look for this "variation".
  47 -   Consider a grayscale image \f$I\f$. We are going to sweep a window \f$w(x,y)\f$ (with displacements \f$u\f$
  48     in the x direction and \f$v\f$ in the y direction) \f$I\f$ and will calculate the variation of
  49     intensity.
  50
  51     \f[E(u,v) = \sum _{x,y} w(x,y)[ I(x+u,y+v) - I(x,y)]^{2}\f]
  52
  53     where:
  54
  55     -   \f$w(x,y)\f$ is the window at position \f$(x,y)\f$
  56     -   \f$I(x,y)\f$ is the intensity at \f$(x,y)\f$
  57     -   \f$I(x+u,y+v)\f$ is the intensity at the moved window \f$(x+u,y+v)\f$
  58 -   Since we are looking for windows with corners, we are looking for windows with a large variation
  59     in intensity. Hence, we have to maximize the equation above, specifically the term:
  60
  61     \f[\sum _{x,y}[ I(x+u,y+v) - I(x,y)]^{2}\f]
  62
  63 -   Using *Taylor expansion*:
  64
  65     \f[E(u,v) \approx \sum _{x,y}[ I(x,y) + u I_{x} + vI_{y} - I(x,y)]^{2}\f]
  66
  67 -   Expanding the equation and cancelling properly:
  68
  69     \f[E(u,v) \approx \sum _{x,y} u^{2}I_{x}^{2} + 2uvI_{x}I_{y} + v^{2}I_{y}^{2}\f]
  70
  71 -   Which can be expressed in a matrix form as:
  72
  73     \f[E(u,v) \approx \begin{bmatrix}
  74                     u & v
  75                    \end{bmatrix}
  76                    \left (
  77            \displaystyle \sum_{x,y}
  78                    w(x,y)
  79                    \begin{bmatrix}
  80                     I_x^{2} & I_{x}I_{y} \\
  81                     I_xI_{y} & I_{y}^{2}
  82            \end{bmatrix}
  83            \right )
  84            \begin{bmatrix}
  85                     u \\
  86         v
  87                    \end{bmatrix}\f]
  88
  89 -   Let's denote:
  90
  91     \f[M = \displaystyle \sum_{x,y}
  92               w(x,y)
  93               \begin{bmatrix}
  94                         I_x^{2} & I_{x}I_{y} \\
  95                         I_xI_{y} & I_{y}^{2}
  96                    \end{bmatrix}\f]
  97
  98 -   So, our equation now is:
  99
 100     \f[E(u,v) \approx \begin{bmatrix}
 101                     u & v
 102                    \end{bmatrix}
 103            M
 104            \begin{bmatrix}
 105                     u \\
 106         v
 107                    \end{bmatrix}\f]
 108
 109 -   A score is calculated for each window, to determine if it can possibly contain a corner:
 110
 111     \f[R = det(M) - k(trace(M))^{2}\f]
 112
 113     where:
 114
 115     -   det(M) = \f$\lambda_{1}\lambda_{2}\f$
 116     -   trace(M) = \f$\lambda_{1}+\lambda_{2}\f$
 117
 118     a window with a score \f$R\f$ greater than a certain value is considered a "corner"
 119
 120 Code
 121 ----
 122
 123 @add_toggle_cpp
 124 This tutorial code's is shown lines below. You can also download it from
 125 [here](https://github.com/opencv/opencv/tree/3.4/samples/cpp/tutorial_code/TrackingMotion/cornerHarris_Demo.cpp)
 126 @include samples/cpp/tutorial_code/TrackingMotion/cornerHarris_Demo.cpp
 127 @end_toggle
 128
 129 @add_toggle_java
 130 This tutorial code's is shown lines below. You can also download it from
 131 [here](https://github.com/opencv/opencv/tree/3.4/samples/java/tutorial_code/TrackingMotion/harris_detector/CornerHarrisDemo.java)
 132 @include samples/java/tutorial_code/TrackingMotion/harris_detector/CornerHarrisDemo.java
 133 @end_toggle
 134
 135 @add_toggle_python
 136 This tutorial code's is shown lines below. You can also download it from
 137 [here](https://github.com/opencv/opencv/tree/3.4/samples/python/tutorial_code/TrackingMotion/harris_detector/cornerHarris_Demo.py)
 138 @include samples/python/tutorial_code/TrackingMotion/harris_detector/cornerHarris_Demo.py
 139 @end_toggle
 140
 141 Explanation
 142 -----------
 143
 144 Result
 145 ------
 146
 147 The original image:
 148
 149 ![](images/Harris_Detector_Original_Image.jpg)
 150
 151 The detected corners are surrounded by a small black circle
 152
 153 ![](images/Harris_Detector_Result.jpg)