Optimizing code - calculation of Euclidean distance Sift

Question

First of all I am well aware with the theory behind feature matching in Sift, my problem is rather a technical one

So I try to calculate Euclidean distance between a vector of the first image and all the vectors of the second and then if the ratio between the biggest two values is bigger than a certain threshold than there is a match

That's my code

distRatio = 0.5;   
for i = 1:size(des1,1)
    eucl = zeros(size(des2,1));
    for j=1:size(des2,1)
           eucl(j) = sqrt(sum((des1(i,:)-des2(j,:)).^2));
    end;

    [vals,indx] = sort(eucl);        
    if (vals(1) < distRatio * vals(2))
      match(i) = indx(1);
    else
      match(i) = 0;
    end
end;

The problem is that it is very slow, and I know the reason, it is slow because of the nested loop, is there any way to optimize that? Sorry I have poor experience with Matlab syntax.

Answer 1

One neat trick you can often use when calculating euclidean distance is to modify your algorithm to work with the squared euclidean distance instead - this eliminates a costly square root function that isn't necessary, for example, if you just want to find the largest or smallest distance in a set.

So the inner loop might become:

distSquared(j) = sum((des1(i, :) - des2(j, :)).^2);

In your case, the tricky thing to change is the line

if (vals(1) < distRatio * vals(2))

Which is equivalent to

if (vals(1)^2 < (distRatio * vals(2))^2)

Or

if (vals(1)^2 < (distRatio^2) * (vals(2)^2))

And if you are getting the values from distSquared instead of eucl, then you could use

if (valSquared(1) < (distRatio^2) * valSquared(2))

Finally, you could maybe take out the inner loop by rewriting the subtraction like this:

countRowsDes2 = size(des2, 1); % this line outside the loop

%... now inside the loop
    des1expand = repmat(des1(i, :), countRowsDes2, 1); % copy this row

    distSquared = sum((des1expand - des2).^2, 2);      % sum horizontally

Where I've used repmat to copy the row des1(i, :), and made sum work on the horizontal dimension using the second dimension argument.

Putting it all together

distRatio = 0.5;
distRatioSq = distRatio^2; % distance ratio squared
countRowsDes1 = size(des1, 1); % number of rows in des1
countRowsDes2 = size(des2, 1); % number of rows in des2

match = zeros(countRowsDes1, 1); % pre-initialize with zeros

for i = i:size(des1, 1)
    des1expand = repmat(des1(i, :), countRowsDes2, 1); % copy row i of des1
    distSquared = sum((des1expand - des2).^2, 2);      % sum horizontally

    [valsSquared, index] = sort(distSquared);

    if (valsSquared(1) < distRatioSq * valsSquared(2))
        match(i) = index(1);
    % else zero by initialization
end