doc/tutorials/features2d/feature_flann_matcher/feature_flann_matcher.markdown

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