No replies to this topic

[Biofag]

Hi, this is my first post so i'll get straightforward to the point.
i'm doing a function that takes as input two sift matrices of image A and B and returns the number of matching sifts.
the matrices have the following characteristics:

1)1 row describes 1 sift
2)the sifts are described only by integers:

x,y, coordinates, intensity, orientation + 128 integers in the range 0/255

3) the 128 integers are used to actually measure the distance between two SIFT
descriptors so in the sift matrix i'm using only them.
4)SIFT x from image A matches SIFT y from image B if y is the closest (to x)
SIFT in B, and the second closest SIFT z in b has distance such that
d(x,y)/
d(x,z)<alpha
this is made to avoid noise on the image
-Usually with alpha=0.8.

my algorithm:

int NumMatches

for each row in A
{ for each row in B
{ compute euclidian_distance(row(A),row(B));

select Minimum1 //the minimum distance
select Minimum2 //the second mimimum distance
}
}
if(Minimum1/Minimum2<alfa)
NumMatches++

return NumMatches


the algorithm must be applied to about 30K images, so i need that it would be as light as possible and my O(N^2) complexity is too much to handle.
Is it possilbe to do better?
Maybe changing the type of distance?
I need to know how i can make it faster!!
thanks!