Matching an image with a database

I am looking to compare a new image to a database of images, and then output the higher "similarity". The images I want to compare are similar, but the problem is though because they're not pixel by pixel equal. I've tried to use BoW (Bag Of Words) model already, as per recommendation, I tried various implementations without success, the best correct rate I got was 30%, which is something really low.

Let me show you what I am talking about: (imgur gallery with 5 example images) http://imgur.com/a/ukf5E#0. I want to detect that the four initial images are equal, and the fifth one is different. I wouldn't mind only detecting that the ones with the same angle orientation are equal, though. (In my example 2, 3 and 4)

So, that being said, are there any better methods than BoW for that? Or perhaps BoW should be enough if I implemented in a different way?

Thanks in advance.

[Aravind Dhakshinamoorthy]

Try using the SIFT algorithm. It detects key points in both images and maps the similar ones. Greater number of similar points greater the similarity.

[Hamad ALshahrani]

Write a Matlab program to find an image in the database similar to a query image which it is: a. Not in the database but for the same person. b. Not in the database and for another person. For both cases above, repeat the process 10 times on different faces and compute the accuracy ratio.

Answer 1

[Anand]

BoF seems like a reasonable approach to this problem. Usually, you are working with a much larger set of images than just 5. Crucial to BoF are the feature points and descriptors you use to represent the images as well as the size of the visual vocabulary.

In the example below, I have used SURF features to detect feature points and extract sparse descriptors. I used SURF because they are scale and rotation-invariant. The Computer Vision System Toolbox has functions that enable you to do this:

http://www.mathworks.com/help/vision/feature-detection-extraction-and-matching.html

I then used the K-means algorithm to construct a visual vocabulary using 20 words. This function is part of the Statistics Toolbox. After creating a visual vocabulary, I created a bag-of-features representation for each image using this visual vocabulary. We now have a feature vector of length 20 for each of the 5 images. Applying K-means (again) on this to partition it into 2 sets gives the desired result. The fist four images are partitioned into 1 set and the last image to a different set.

%%Read images
im{1} = rgb2gray(imread('http://i.imgur.com/TMyflBl.png'));
im{2} = rgb2gray(imread('http://i.imgur.com/ozygW2g.png'));
im{3} = rgb2gray(imread('http://i.imgur.com/dGj8FNE.png'));
im{4} = rgb2gray(imread('http://i.imgur.com/VbTLPjG.png'));
im{5} = rgb2gray(imread('http://i.imgur.com/huj2El9.png'));

%%Detect and extract MSER features
detectFeatures = @(in) {detectSURFFeatures(in)}; 
regions = cellfun(detectFeatures,im);

extractAndTransposeFeatures = @(in,pts) extractFeatures(in,pts)';
features = cellfun(extractAndTransposeFeatures,im,regions,'UniformOutput',false);

figure;
for i = 1 : 5
    subplot(2,3,i);
    imshow(im{i});
    hold on;
    plot(regions{i});
end

%%Create a visual vocabulary with 20 words
nWords = 20;

%use kmeans for constructing the vocabulary.
[idx,centers] = kmeans([features{:}]',nWords);

%%BoF Feature Representation
histFtrs = cell(5,1);
for i = 1 : 5
    start = 1;
    histFtrs{i} = hist(idx(start:start+size(features{i},2)),nWords)';

      %normalize
      histFtrs{i} = histFtrs{i}./sum(hisFtrs{i});
  end

%display histograms
figure;
for i = 1 : 5;
    subplot(2,3,i);
    bar(histFtrs{i});
end

%%Partition images into 2 sets using kmeans
idx = kmeans([histFtrs{:}]',2)

% idx =
% 
%      2
%      2
%      2
%      2
%      1

Hope this helps. Bear in mind that you may need to do a lot more fiddling with some of the parameters and general approach for a more complicated problem.

[Anand]

You can always store intermediate results in a MAT file using the SAVE command.

[Emmanuel Oreoluwa]

Hi Anand, Thanks for your clear explanation. Just want to ask if the coordinates of the centers which is 20x64 is for a single image or for the five images?

[Mohammad Mortazavi]

hi! i think your code is little wrong. in below section:

for i = 1 : 5
  start = 1;
  histFtrs{i} = hist(idx(start:start+size(features{i},2)),nWords)';
    %normalize
    histFtrs{i} = histFtrs{i}./sum(hisFtrs{i});
end

always (start=1) in all rounds of loop!!! and it counts from begin for all images. i think you should change this code to:

 start = 1;
 for i = 1 : k

    histFtrs{i} = hist(idx(start:start+size(features{i},2)-1),nWords)';
    %normalize
    histFtrs{i} = histFtrs{i}./sum(histFtrs{i});
    start = start+size(features{i},2);
end

now we can count all parts for all images!

i run your code, but my result is different.

my idx=
1
2
2
1
1

Answer 2

[Anand]

save idx.mat idx;
save centers.mat centers;

Answer 3

[Mohammed Magdy]

hello please why did you use this number (2) here (features{i},2)

histFtrs{i} = hist(idx(start:start+size(features{i},2)),nWords)';

[Anand]

I used that to get the second dimension of features{i}

>> size(features{1})

ans =

    64    15

There are 15 features and that's the number I was looking to get.

[Mohammed Magdy]

Hello i used gist descriptor (the descriptor for each image is a row vector 1*512. I choose nWords=30 but i don't have a good result. Please do you have any idea about this descriptor (GIST).

[hamed abdulaziz]

I have medical images and I need to classify them to normal and abnomal using bag of words model where I divided each image to patches(blocks) and extracted local features from each patch,my question how can I use k-means algorithm to constrcut visual words vocabulary,could any one provide me matlab code for this job,and thanks in advance

[Anand]

The code above shows how to do this. http://www.mathworks.com/matlabcentral/answers/67478#answer_79060

[hamed abdulaziz]

Anand :Thank you,I saw the code above but I divided each image to patches(blocks) and extracted local features from each patch,where is the code doesn't do that,could you guide me with my thanks.

Answer 4

[Yuva]

I am doing my final year project on attedance system by face recognition using SIFT algorithm,if there is any code on this project please comment code or provide any link .