Code Optimization - Euclidean Distance Calculation

Question

First of all, I know well the theory of correspondence of functions in Sift, my problem is rather technical.

So, I'm trying to calculate the Euclidean distance between the vector of the first image and all the vectors of the second, and then if the ratio between the largest two values ​​is greater than a certain threshold than a match

What is 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 due to a nested loop, is there any way to optimize this ? Sorry, I have poor experience with Matlab syntax.

Answer 1

One neat trick that you can often use when calculating the Euclidean distance is to change the algorithm to work with the quadratic Euclidean distance - this eliminates the expensive square root function that is not needed, for example, if you just want to find the largest or minimum distance in the set.

Thus, the inner cycle can become:

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

In your case, it's hard to change the line

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

Which is equivalent

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

or

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

And if you get the values ​​from distSquared instead of eucl , you can use

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

Finally, you could pull out the inner loop by rewriting the subtraction as follows:

 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 used repmat to copy the line des1(i, :) and made sum work with 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