# SURF matching against a database of images

I'd like to compare an image taken with a webcam against a database of known images. I've been trying to use SURF for this, and it works OK when the number of images is small. Using BruteForceMatcher i get good, repeatable results although it is very slow, since I need to compare against a database of 3000 images, which would take several minutes.

A post in stackoverflow led me to a paper where they say using a FLANN index of the images is very, very fast (down to a few milliseconds for thousands of images). A poster in that thread says he uses a big FLANN index with the SURF features of all images, and uses this to compare to the current image. I've tried to do what he claims. I'm using EMGU to acces openCV from C#. What I get is a Matrix<float> of image features for each image, and i concatenate all the matrices to get a big matrix of all features. WIth this i I build a FLANN index and use this to compare the current observation against this big database with KnnMatch.

It returns in about 25ms with all rows with value zero.

Now, if i reverse this, and build the FLANN index with the points of the observed image and compare the big bad matrix of all features, for 100 images it takes about 300ms and it works.

Has anyone tried this approach with success? Is it even possible to do this with opencv?

Thanks

What I'm doing currently is the following:

Part 1: initialization

Read all the images in a directory, use

surfCPU.ComputeDescriptorsRaw


and

surfCPU.DetectKeyPointsRaw (btw: SURFDetector surfCPU = new SURFDetector(500, false);)


for each DetectKeypoints, load into a big matrix:

supermatrix = surfCPU.ComputeDescriptorsRaw(img, null, add.modelKeyPoints);


also keep a List<int> of KeypointIndices:

imageLastIndex.Add(supermatrix.Rows); (assuming each image has 100 points: 100, 200,300: image 0 is points 0 to 99, image 2 is points 100 to 199, etc)


once all the images have been analyzed, build the index:

Emgu.CV.Flann.Index fln = new Index(supermatrix,4);


Part 2:

query Matrix<int> indices = new Matrix<int>(supermatrix.Rows, k);
Matrix<float> dist = new Matrix<float>(supermatrix.Rows, k);
fln.KnnSearch(observedDescriptors,indices,dist,k,12);


the result here is that "dist" (the return value) Is a Matrix<float> filled with all rows and cols with value "0.0"

Now if I do the opposite (notice the FLANN is created with observedDescriptors which is N times smaller than supermatrix, with N=number of images):

Emgu.CV.Flann.Index fln = new Index(observedDescriptors,4);
Matrix<int> indices = new Matrix<int>(supermatrix.Rows, k);
Matrix<float> dist = new Matrix<float>(supermatrix.Rows, k);
fln.KnnSearch(supermatrix, indices,dist, k,12);


the result is correct, but the FLANN index is not really "exploited". also this is slower than linear search

edit retag close merge delete

I am trying to do the same. Did any of you succeed to set this up.

Is there any github source that I can take a look at it ?

( 2013-07-18 22:57:15 -0500 )edit

Sort by » oldest newest most voted

Hi again: If i change

//At this point, we should to build the index of the big  matrix
Index fln = new Index(supermatrix, 4);

//Retrieve The Rows supermatrix
Matrix<int> indices = new Matrix<int>(supermatrix.Rows, k);
Matrix<float> dist = new Matrix<float>(supermatrix.Rows, k);

fln.KnnSearch(observedDescriptors, indices, dist, k, 12);


to

//At this point, we should to build the index of the big  matrix
Index fln = new Index(observedDescriptors, 4);

//Retrieve The Rows supermatrix

Matrix<int> indices = new Matrix<int>(supermatrix.Rows, k);
Matrix<float> dist = new Matrix<float>(supermatrix.Rows, k);

fln.KnnSearch(supermatrix, indices, dist, k, 20);


I think that this line it's incorrect, i think that the index should be built with supermatrix

Index fln = new Index(observedDescriptors, 4); //What it's the correct line?
Index fln = new Index(supermatrix, 4);


Indices and dist have values but the following code has output many rare values:

 for (int i = 0; i < indices.Rows; i++){
if (dist.Data[i, 0] < 0.8 * dist.Data[i, 1]){
Debug.WriteLine("This Point Is Good");
Debug.WriteLine("The image most similar is" + i);
}
}

This Point Is Good
The image most similar is11
This Point Is Good
The image most similar is12
This Point Is Good
The image most similar is25
This Point Is Good
The image most similar is27
This Point Is Good
The image most similar is30
This Point Is Good
The image most similar is31
................................
................................


All points in dist are similar?
I think that i have a big error in the code.

more

First of all: Do not delete your answers and don't post new ones, only edit them, now all comments which lead to a solution are gone! How should anybody follow this now? Maybe s.o. else has the same struggles? And has now no clue about the development of the solution. This is not a typical forum but a Q&A forum and you broke now already two rules of this forum - antother one would have already closed this thread twice! Again: DO NOT DELETE OR ADD ANSWERS - EDIT/UPDATE and mark the parts which you have edited / updated so that it is clear what you did.

( 2013-04-10 05:48:30 -0500 )edit

Back to your question: Of course you should take the supermatrix for building your flann index. This is already stated in the original first question and my answer of @hjf . So build your supermatrix correctly and from this the index. If you do it your way, i.e. building an index with the observedmatrix and searching then for nearest neighbor with the observedmatrix of course all will be the same O_o !

( 2013-04-10 05:48:59 -0500 )edit

hi, i've tried the code and i have an error like this in this list code :

Index fln = new Index(supermatrix, 4);

but then, it gives me an error like this :

Argument 2 : cannot convert from 'int' to 'Emgu.CV,Flann.IIndexparams

i'm sorry to not given an answer but i ask a question again..

( 2018-01-04 08:08:04 -0500 )edit
1

@Rezi -- we don't deal with emgu at allhere. please rather ask on http://www.emgu.com/forum/

( 2018-01-04 08:15:29 -0500 )edit

but i think this code us emgucv, but if i'm wrong i'm so sorry... thank you sir :D

( 2018-01-04 08:19:25 -0500 )edit

^^ you're not wrong, it's just, that noone can or will help you with it from here, now.

( 2018-01-04 08:28:23 -0500 )edit

okay sir :D thank you sir :D

( 2018-01-04 08:30:51 -0500 )edit

I modified the code but i have retrieve the same result. Indices and dist are always contains 0 values in The system never executed the line " Debug.WriteLine("This Point Is Good"); I will be very gratefull if anyone could to fix my code. I am very lost with knntree examples. The second version of the code with the Guanta fix is:

    SURFDetector surfCPU = new SURFDetector(50, false);
Matrix<float> matrix,supermatrix;
VectorOfKeyPoint observedKeyPoints, modelKeyPoints;
Image<Gray, byte> observedImage, modelImage;
int k = 2;

private void Pruebas(){
//Load Image To Compare With ALL Images in Database
observedImage = new Image<Gray, byte>(@"C:\Users\gabri_000\Pictures\uneuro.png");
observedKeyPoints = surfCPU.DetectKeyPointsRaw(observedImage, null);
Matrix<float> observedDescriptors = surfCPU.ComputeDescriptorsRaw(observedImage, null, observedKeyPoints);

//Path With ALL Images Database
//We will to build the big index for use with flann algorithm
string[] images = Directory.GetFiles(@"C:\Users\gabri_000\Pictures", "*.png");
foreach (string image in images)
{
DateTime start = DateTime.Now;
Debug.WriteLine("Current Image  " + image);
modelImage = new Image<Gray, byte>(image);

modelKeyPoints = surfCPU.DetectKeyPointsRaw(modelImage, null);
matrix = surfCPU.ComputeDescriptorsRaw(modelImage, null, modelKeyPoints);

if (supermatrix == null)
{
supermatrix = new Matrix<float>(matrix.Rows, matrix.Cols);
supermatrix = matrix;
}
else
{
supermatrix= supermatrix.ConcateVertical(matrix);
}

DateTime end = DateTime.Now;

Debug.WriteLine("Process Time " + (end - start));

}

//At this point, we should to build the index of the big  matrix
Index fln = new Index(supermatrix, 4);

//Retrieve The Rows supermatrix

Matrix<int> indices = new Matrix<int>(supermatrix.Rows, k);
Matrix<float> dist = new Matrix<float>(supermatrix.Rows, k);

fln.KnnSearch(observedDescriptors, indices, dist, k, 12);

Debug.WriteLine("-----------------------");

for (int i = 0; i < indices.Size.Height; i++)
{
if (dist.Data[i, 0] < 0.6 * dist.Data[i, 1])
{
Debug.WriteLine("This Point Is Good");
Debug.WriteLine("The image most similar is" + i);
}

}

}

more

Your approach should work fine. So, in your set-up sth must be wrong. And yes, this is definitely possible with OpenCV. If you'd like to get the maximum performance build your index with the original-flann from http://www.cs.ubc.ca/~mariusm/index.php/FLANN/ with OpenMP-support and use OpenCV's GPU::SURF module (http://docs.opencv.org/modules/nonfree/doc/feature_detection.html#gpu-surf-gpu).

However note that depending on the number of SURF descriptors (which depend of course on the SURF-settings and the size of the images and their content) you'll have to do many comparisons and a lot of memory to build your flann-index. So, I suggest to go a different way and compute a single descriptor for your images either by a global image descriptor (see e.g. http://answers.opencv.org/question/9271/global-image-feature-implementation/) or by the usage of a bag-of-words-descriptor (see http://answers.opencv.org/question/8677/image-comparison-with-a-database). The drawback of the bag-of-words-descriptor is that you need to build a vocabulary first which will also take quite a while for such a database. However the results should be definitely better with less false positives and the cool thing with a global image descriptor is that you can use it for classification tasks.

more

What I'm doing currently is the following:

Part 1: initialization

1. Read all the images in a directory, use

surfCPU.ComputeDescriptorsRaw and

surfCPU.DetectKeyPointsRaw (btw: SURFDetector surfCPU = new SURFDetector(500, false);)

1. for each DetectKeypoints, load into a big matrix:

1. also keep a List<int> of KeypointIndices:

imageLastIndex.Add(supermatrix.Rows); (assuming each image has 100 points: 100, 200,300: image 0 is points 0 to 99, image 2 is points 100 to 199, etc)

1. once all the images have been analyzed, build the index:

Emgu.CV.Flann.Index fln = new Index(supermatrix,4);

(followed in next comment)

( 2013-04-01 09:08:29 -0500 )edit

Part 2: query Matrix<int> indices = new Matrix<int>(supermatrix.Rows, k); Matrix<float> dist = new Matrix<float>(supermatrix.Rows, k); fln.KnnSearch(observedDescriptors,indices,dist,k,12);

the result here is that "dist" (the return value) Is a Matrix<float> filled with all rows and cols with value "0.0"

Now if I do the opposite (notice the FLANN is created with observedDescriptors which is N times smaller than supermatrix, with N=number of images):

Emgu.CV.Flann.Index fln = new Index(observedDescriptors,4); Matrix<int> indices = new Matrix<int>(supermatrix.Rows, k); Matrix<float> dist = new Matrix<float>(supermatrix.Rows, k); fln.KnnSearch(supermatrix, indices,dist, k,12);

the result is correct, but the FLANN index is not really "exploited". also this is slower than linear search

( 2013-04-01 09:13:54 -0500 )edit

Just where Part2 starts: I think it should be size (observedDescriptors.Rows, k) for the indices and dist-matrices . Btw: your comments are really hard to read, maybe your want to edit them for better readability.

( 2013-04-01 11:22:37 -0500 )edit

sorry i don't seem to be able to format comments. yes, if i do size (observedDescriptors.rows,k) it works but I only get 1 result (always the same and it's not the right one). i'm very confused :P

( 2013-04-01 11:32:46 -0500 )edit

1 result? You should get k results. Sorry that I can't help you more, I'm not familiar with C#, maybe you are creating your supermatrix in a wrong way?

( 2013-04-01 16:50:41 -0500 )edit

Official site

GitHub

Wiki

Documentation

## Stats

Seen: 18,354 times

Last updated: Jan 04 '18