MATLAB: Matching an image with a database

Question

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.

Answer 1

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.