Help selecting a search algorithm, dsearchn, knnsearch, etc.

Hello all,

I have a matrix A made up of several 2D points. I have a second matrix, B, which is the positions of these points slightly shifted in time. Basically they are from the next frame of a movie. I would like to find the points in B that are closest to each point in A. So far, I have been using dsearchn, but I found an issue that doesn't seem to make it work in my case. dsearchn will sometimes return the same point in B to multiple points in A. I would like something that returns a unique point in B for each point in A while minimizing the total distance. Is this something that already exists in matlab, or would I need to code it myself.

Thank you tremendously, Quentin

[Star Strider]

I’m not certain I understand. Is the ‘[k,d] = dsearchn(X,...)’ option not returning unique distances? Posting relevant parts of your code and a short but representative sample of your data would help.

Answer 1

[Greg Heath]

>> min([ 1 1 2 2 3 3])

ans =

     1

Hope this helps.

Thank you for formally accepting my answer

Greg

Answer 2

[Quentin]

I don't min will quite work because the same point in B might be assigned different points in A. The algorithm would need to exclude that possibility so that each point in B is assigned a unique point in A while minimizing the total distance that points were allowed to travel between frames. This is just to keep track of them and maximize the odds that they'll each maintain their own unique identity between frames.

Answer 3

[Marcraven]

I have a similar problem.

You can use the munkres algorithm for assignment, but it is slow.

What I do is assigning multiple points (with knnsearch) to a single one and then keeping only those with smallest distance, I don't know if that works for you.

 [spots,Distances]=knnsearch(A,B);
merged=[spots,Distances];
merged=sortrows(merged,2);
[a,b]=unique(merged(:,1),'rows');
Distances=merged(b,2);
spots=merged(b,1);
end