doc/tutorials/features2d/feature_flann_matcher/feature_flann_matcher.markdown

   1 Feature Matching with FLANN {#tutorial_feature_flann_matcher}
   2 ===========================
   3
   4 @prev_tutorial{tutorial_feature_description}
   5 @next_tutorial{tutorial_feature_homography}
   6
   7 Goal
   8 ----
   9
  10 In this tutorial you will learn how to:
  11
  12 -   Use the @ref cv::FlannBasedMatcher interface in order to perform a quick and efficient matching
  13     by using the @ref flann module
  14
  15 \warning You need the <a href="https://github.com/opencv/opencv_contrib">OpenCV contrib modules</a> to be able to use the SURF features
  16 (alternatives are ORB, KAZE, ... features).
  17
  18 Theory
  19 ------
  20
  21 Classical feature descriptors (SIFT, SURF, ...) are usually compared and matched using the Euclidean distance (or L2-norm).
  22 Since SIFT and SURF descriptors represent the histogram of oriented gradient (of the Haar wavelet response for SURF)
  23 in a neighborhood, alternatives of the Euclidean distance are histogram-based metrics (\f$ \chi^{2} \f$, Earth Mover’s Distance (EMD), ...).
  24
  25 Arandjelovic et al. proposed in @cite Arandjelovic:2012:TTE:2354409.2355123 to extend to the RootSIFT descriptor:
  26 > a square root (Hellinger) kernel instead of the standard Euclidean distance to measure the similarity between SIFT descriptors
  27 > leads to a dramatic performance boost in all stages of the pipeline.
  28
  29 Binary descriptors (ORB, BRISK, ...) are matched using the <a href="https://en.wikipedia.org/wiki/Hamming_distance">Hamming distance</a>.
  30 This distance is equivalent to count the number of different elements for binary strings (population count after applying a XOR operation):
  31 \f[ d_{hamming} \left ( a,b \right ) = \sum_{i=0}^{n-1} \left ( a_i \oplus b_i \right ) \f]
  32
  33 To filter the matches, Lowe proposed in @cite Lowe04 to use a distance ratio test to try to eliminate false matches.
  34 The distance ratio between the two nearest matches of a considered keypoint is computed and it is a good match when this value is below
  35 a threshold. Indeed, this ratio allows helping to discriminate between ambiguous matches (distance ratio between the two nearest neighbors
  36 is close to one) and well discriminated matches. The figure below from the SIFT paper illustrates the probability that a match is correct
  37 based on the nearest-neighbor distance ratio test.
  38
  39 ![](images/Feature_FlannMatcher_Lowe_ratio_test.png)
  40
  41 Alternative or additional filterering tests are:
  42 -   cross check test (good match \f$ \left( f_a, f_b \right) \f$ if feature \f$ f_b \f$ is the best match for \f$ f_a \f$ in \f$ I_b \f$
  43     and feature \f$ f_a \f$ is the best match for \f$ f_b \f$ in \f$ I_a \f$)
  44 -   geometric test (eliminate matches that do not fit to a geometric model, e.g. RANSAC or robust homography for planar objects)
  45
  46 Code
  47 ----
  48
  49 @add_toggle_cpp
  50 This tutorial code's is shown lines below. You can also download it from
  51 [here](https://github.com/opencv/opencv/tree/3.4/samples/cpp/tutorial_code/features2D/feature_flann_matcher/SURF_FLANN_matching_Demo.cpp)
  52 @include samples/cpp/tutorial_code/features2D/feature_flann_matcher/SURF_FLANN_matching_Demo.cpp
  53 @end_toggle
  54
  55 @add_toggle_java
  56 This tutorial code's is shown lines below. You can also download it from
  57 [here](https://github.com/opencv/opencv/tree/3.4/samples/java/tutorial_code/features2D/feature_flann_matcher/SURFFLANNMatchingDemo.java)
  58 @include samples/java/tutorial_code/features2D/feature_flann_matcher/SURFFLANNMatchingDemo.java
  59 @end_toggle
  60
  61 @add_toggle_python
  62 This tutorial code's is shown lines below. You can also download it from
  63 [here](https://github.com/opencv/opencv/tree/3.4/samples/python/tutorial_code/features2D/feature_flann_matcher/SURF_FLANN_matching_Demo.py)
  64 @include samples/python/tutorial_code/features2D/feature_flann_matcher/SURF_FLANN_matching_Demo.py
  65 @end_toggle
  66
  67 Explanation
  68 -----------
  69
  70 Result
  71 ------
  72
  73 -   Here is the result of the SURF feature matching using the distance ratio test:
  74
  75     ![](images/Feature_FlannMatcher_Result_ratio_test.jpg)