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

15 次查看（过去 30 天）
Quentin
Quentin 2014-3-18
回答： Marcraven 2017-1-23
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
  1 个评论
Star Strider
Star Strider 2014-3-18
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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（3 个）

Greg Heath
Greg Heath 2014-3-18
>> min([ 1 1 2 2 3 3])
ans =
1
Hope this helps.
Thank you for formally accepting my answer
Greg
Quentin
Quentin 2014-3-18
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.
Marcraven
Marcraven 2017-1-23
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

类别

在 Help Center 和 File Exchange 中查找有关 Discriminant Analysis 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by