OpenCV  4.5.1
Open Source Computer Vision
Feature Matching with FLANN

Table of Contents

Prev Tutorial: Feature Description
Next Tutorial: Features2D + Homography to find a known object

Original author Ana Huamán
Compatibility OpenCV >= 3.0

Goal

In this tutorial you will learn how to:

Warning
You need the OpenCV contrib modules to be able to use the SURF features (alternatives are ORB, KAZE, ... features).

Theory

Classical feature descriptors (SIFT, SURF, ...) are usually compared and matched using the Euclidean distance (or L2-norm). Since SIFT and SURF descriptors represent the histogram of oriented gradient (of the Haar wavelet response for SURF) in a neighborhood, alternatives of the Euclidean distance are histogram-based metrics ( \( \chi^{2} \), Earth Mover’s Distance (EMD), ...).

Arandjelovic et al. proposed in [Arandjelovic:2012:TTE:2354409.2355123] to extend to the RootSIFT descriptor:

a square root (Hellinger) kernel instead of the standard Euclidean distance to measure the similarity between SIFT descriptors leads to a dramatic performance boost in all stages of the pipeline.

Binary descriptors (ORB, BRISK, ...) are matched using the Hamming distance. This distance is equivalent to count the number of different elements for binary strings (population count after applying a XOR operation):

\[ d_{hamming} \left ( a,b \right ) = \sum_{i=0}^{n-1} \left ( a_i \oplus b_i \right ) \]

To filter the matches, Lowe proposed in [Lowe04] to use a distance ratio test to try to eliminate false matches. 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 a threshold. Indeed, this ratio allows helping to discriminate between ambiguous matches (distance ratio between the two nearest neighbors is close to one) and well discriminated matches. The figure below from the SIFT paper illustrates the probability that a match is correct based on the nearest-neighbor distance ratio test.

Alternative or additional filterering tests are:

  • cross check test (good match \( \left( f_a, f_b \right) \) if feature \( f_b \) is the best match for \( f_a \) in \( I_b \) and feature \( f_a \) is the best match for \( f_b \) in \( I_a \))
  • geometric test (eliminate matches that do not fit to a geometric model, e.g. RANSAC or robust homography for planar objects)

Code

Explanation

Result

  • Here is the result of the SURF feature matching using the distance ratio test:

cv::noArray
InputOutputArray noArray()
cv::String
std::string String
Definition: cvstd.hpp:150
cv::imread
CV_EXPORTS_W Mat imread(const String &filename, int flags=IMREAD_COLOR)
Loads an image from a file.
cv::Scalar_< double >::all
static Scalar_< double > all(double v0)
returns a scalar with all elements set to v0
cv::MatExpr::max
MatExpr max(const Mat &a, const Mat &b)
cv::samples::findFile
cv::String findFile(const cv::String &relative_path, bool required=true, bool silentMode=false)
Try to find requested data file.
cv::waitKey
int waitKey(int delay=0)
Waits for a pressed key.
highgui.hpp
core.hpp
cv::Mat::empty
bool empty() const
Returns true if the array has no elements.
cv::IMREAD_GRAYSCALE
@ IMREAD_GRAYSCALE
If set, always convert image to the single channel grayscale image (codec internal conversion).
Definition: imgcodecs.hpp:71
cv::dnn::print
static void print(const MatShape &shape, const String &name="")
Definition: shape_utils.hpp:198
cv::DescriptorMatcher::knnMatch
void knnMatch(InputArray queryDescriptors, InputArray trainDescriptors, std::vector< std::vector< DMatch > > &matches, int k, InputArray mask=noArray(), bool compactResult=false) const
Finds the k best matches for each descriptor from a query set.
cv::Ptr
std::shared_ptr< _Tp > Ptr
Definition: cvstd_wrapper.hpp:23
cv::imshow
void imshow(const String &winname, InputArray mat)
Displays an image in the specified window.
cv::drawMatches
void drawMatches(InputArray img1, const std::vector< KeyPoint > &keypoints1, InputArray img2, const std::vector< KeyPoint > &keypoints2, const std::vector< std::vector< DMatch > > &matches1to2, InputOutputArray outImg, const Scalar &matchColor=Scalar::all(-1), const Scalar &singlePointColor=Scalar::all(-1), const std::vector< std::vector< char > > &matchesMask=std::vector< std::vector< char > >(), DrawMatchesFlags flags=DrawMatchesFlags::DEFAULT)
features2d.hpp
cv::Scalar
Scalar_< double > Scalar
Definition: types.hpp:669
cv::drawMatches
void drawMatches(InputArray img1, const std::vector< KeyPoint > &keypoints1, InputArray img2, const std::vector< KeyPoint > &keypoints2, const std::vector< DMatch > &matches1to2, InputOutputArray outImg, const Scalar &matchColor=Scalar::all(-1), const Scalar &singlePointColor=Scalar::all(-1), const std::vector< char > &matchesMask=std::vector< char >(), DrawMatchesFlags flags=DrawMatchesFlags::DEFAULT)
Draws the found matches of keypoints from two images.
cv::Mat
n-dimensional dense array class
Definition: mat.hpp:798
cv::imshow
void imshow(const String &winname, const ogl::Texture2D &tex)
Displays OpenGL 2D texture in the specified window.
cv::CommandLineParser
Designed for command line parsing.
Definition: utility.hpp:789
cv
"black box" representation of the file storage associated with a file on disk.
Definition: affine.hpp:52
cv::DescriptorMatcher::FLANNBASED
@ FLANNBASED
Definition: features2d.hpp:956
cv::DescriptorMatcher::create
static Ptr< DescriptorMatcher > create(const String &descriptorMatcherType)
Creates a descriptor matcher of a given type with the default parameters (using default constructor).