How to remove false matches from FLANNBASED Matcher in OPENCV?

Question

[Request you to read question details before marking it duplicate or down-voting it. I have searched thoroughly and couldn't find a solution and hence posting the question here.]

I am trying to compare one image with multiple images and get a list of ALL matching images. I do NOT want to draw keypoints between images.

My solution is based on the following source code:

https://github.com/Itseez/opencv/blob/master/samples/cpp/matching_to_many_images.cpp

The above source code matches one image with multiple images and get best matching image.

I have modified the above sample and generated:

 vector<vector<DMatch>> matches;
 vector<vector<DMatch>> good_matches;

Now my question is how do I apply nearest neighbor search ratio to get good matches for multiple images?

Edit 1:

My implementation is as follows:

1. For each image in the data-set, compute SURF descriptors.

2. Combine all the descriptors into one big matrix.

3. Build a FLANN index from the concatenated matrix.

4. Compute descriptors for the query image.

5. Run KNN search over the FLANN index to find top 20 or less best matching image. K is set as 20.

6. Filter out all the inadequate matches computed in the previous step. (How??)

I have successfully done steps number 1 to 5. I am facing problem in step number 6 wherein I am not able to remove false matches.

Colonialism

So you already have found multiple matches for one image and now want to find the k best matches? – Uraeus

Yes. I am able to find the matches. I have set k as 20 because I want to find "all" similar images. – Colonialism

Ok, so you basically want find the false positives in your k best result? Didn't you ask this question already? – Uraeus

Initially, I was using BruteForce matcher when I asked that question. Using BruteForce matcher, I was able to remove false positives and get good results. Unfortunately, the speed of using BruteForce matcher is extremely slow. Now I am using FLANN matcher and again stuck at the same stage. – Colonialism

So you want to find images that are similar to your query image? Why not use BOV-descriptor, or other global image-descriptor? You best edit your answer saying what you want to accomplish overall, including sample images. – Flanna

@Unapiedra, Iam trying to find out duplicates in one folder. The folder consist of 5000 images. My solution is completely similar to the link I mentioned in the question. The only difference is that I want to find multiple matching images instead of the best one. – Colonialism

Thanks, please put that in the question (I can't upvote otherwise). – Flanna

Answer 1

There are two answers to your problem. The first is that you should be using a completely different technique, the second answer is how to actually do what you asked for.

Use a different method

You want to find duplicates of a given query image. Traditionally, you do this by comparing global image descriptors, not local feature descriptors.

The simplest way to do this would be by aggregating the local feature descriptors into a local descriptor. The standard method here is "bag of visual words". In OpenCV this is called Bag-Of-Words (like BOWTrainer, BOWImgDescriptorExtractor etc). Have a look at the documentation for using this.

There is some example code in samples/cpp/bagofwords_classification.cpp

The benefits will be that you get more robust results (depending on the implementation of what you are doing now), and that the matching is generally faster.

Use your method

I understand that you want to remove points from the input that lead to false positives in your matching.

You can't remove points from FLANN(1, 2, 3). FLANN builds a tree for fast search. Depending on the type of tree, removing a node becomes impossible. Guess what, FLANN uses a KD-tree which doesn't (easily) allow removal of points.

FlannBasedMatcher does not support masking permissible matches of descriptor sets because flann::Index does not support this.

I would suggest using a radius search instead of a plain search. Alternatively look at the L2-distance of the found matches and in your code write a function to see whether the distance falls below a threshold.

Edit

I should also note that you can rebuild your flann-tree. Obviously, there is a performance penalty when doing this. But if you have a large number of queries and some features coming up as false-positives way too often, it might make sense to do this once.

You need the functions DescriptorMatcher::clear() and then DescriptorMatcher::add(const vector<Mat>& descriptors) for this. Referenz.

Flanna

I tried the second method. It is not removing false positives. :-( – Colonialism

Answer 2

Firstly you need to define "inadequate matches", without this definition you can't do anything.

There are several loose definitions that spring to mind:

1: inadequate matches = match with distance > pre-defined distance

In this case a flann radius search may more appropriate as it will only give you those indexes within the predefined radius from the target:

http://docs.opencv.org/trunk/modules/flann/doc/flann_fast_approximate_nearest_neighbor_search.html#flann-index-t-radiussearch

2: inadequate matches = match with distance > dynamically defined distance based on the retrieved k-nn

This is more tricky and off the top of my head i can think of two possible solutions:

2a: Define some ratio test based on the distance the first 1-NN such as:

base distance = distance to 1NN

inadequate match_k = match distance_k >= a * base distance;

2b: Use a dynamic thresholding technique such as the Otsu threshold on the normalized distribution of distances for the k-nn, thus partitioning the the k-nn into two groups, the group that contains the 1-nn is the adequate group, the other is the inadequate group.

http://en.wikipedia.org/wiki/Otsu's_method,

http://docs.opencv.org/modules/imgproc/doc/miscellaneous_transformations.html#threshold.

Marty

I developed my application using BruteForce matcher as well as Flannn matcher. The results I got with BF matcher were perfect. I want the same kind of results with FLANN. The obvious reason for choosing Flann over BF matcher is speed. – Colonialism

@milanm FLANN is approximate, you can tune it's parameters to trade-off between speed/accuracy. – Marty

@milanm FLANN parameters doc. docs.opencv.org/modules/flann/doc/… , docs.opencv.org/modules/flann/doc/… – Marty