寻找两组矩阵之间的最近点对

Question

寻找两组矩阵之间的最近点对

3

假设我有两组矩阵（A和B），每个矩阵中都包含一些点坐标，我想找出B中离A最近的点，并输出一个单元格数组C，根据最近的点对坐标列表，还要输出一个单元格数组D，记录未配对的点。如何处理？

更具体地说，这是我想要的：

两组矩阵包含点的xy坐标；

A=[ 1 2; 3 4]; B=[1 3; 5 6; 2 1];

我想获取 C{1,1}=[1 2; 1 3]; C{2,1}= [3 4; 5 6]; D{1,1}=[2 1]; 的内容。

感谢您的帮助。

- tytamu

A和/或B的元素可以被重复使用吗？您想要最小化哪种距离？ - aschepler

@aschepler，我猜我现在理解了你的第二个问题，我稍微修改了一下我的问题，希望这能澄清你所提出的第二点。 - tytamu

你有考虑使用 dsearchn 吗？ - Ansari

@ Ansari，我猜dsearchn在这里可能没有用，因为A和B中的元素不能被重复使用。 - tytamu

看看我对这个问题的回答：http://stackoverflow.com/questions/10639925/how-to-find-the-closest-vector-to-a-given-vector-in-matlab/10648151#10648151 虽然我是在寻找最接近的平均差异，但在找到它之前，它将计算你所要求的内容。 - Dan

显示剩余2条评论

2个回答

0

这是我的看法：

A=[1 2
   3 4]; 

B=[1 3
   5 6
   2 1];

dists = pdist2(A,B);

[dists, I] = sort(dists,2);

c = NaN(size(A,1),1);
for ii = 1:size(A,1)    
    newC = find(~any(bsxfun(@eq, I(ii,:), c), 1));
    c(ii) = I(ii,newC(1));
end

C = cellfun(@(x)reshape(x,2,2).',...
        mat2cell([A B(c,:)], ones(size(A,1),1), 4), 'uni', false);
D = {B(setdiff(1:size(B,1),c), :)}

这个解决方案假设：

所有的向量都是2D的
堆叠在A和B的行中
A始终是源（即，所有东西都与A进行比较）

如果这些假设不总是成立，您将需要采取更一般的方法，例如@GuntherStruyf建议的方法。

- Rody Oldenhuis

A=[0 0;1 1]和B=[1 1;0 0;2 2]怎么样？对于这个输入，结果是I=[2;2]！我不明白将dists的下三角部分设置为NaN如何解决不重复使用B元素的问题。除非一切都已经排序，否则你无法预先知道哪些点彼此最接近，这时这个问题就没有意义了... - Gunther Struyf

@GuntherStruyf 是的，我的解决方案是错误的；我被这个特定问题的正确结果所迷惑了。这次编辑应该可以纠正这个问题。 - Rody Oldenhuis

@GuntherStruyf 我仍然不喜欢那个for循环...我感觉有一个函数可以做到这一点，但我想不起来了... - Rody Oldenhuis

你必须一次处理A中的每个坐标，因为它会影响到A中其他坐标的解决方案。我认为这个问题没有直接/无循环/非迭代的解决方案。 - Gunther Struyf

@GuntherStruyf，那个踩票是你的吗？虽然你的解决方案更优雅（而且更快！），但是踩票...做个好人 :) - Rody Oldenhuis

因为一开始有错误，所以被downvote了，还没来得及验证你的更正，不过现在看起来还不错；）我立刻看到了第一个解决方案的问题，更正看起来要快速完成复杂一些:p - Gunther Struyf

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gunther Struyf · Accepted Answer

对于这个问题并没有唯一的解决方案，以（一维，但可以扩展到N-D）为例：

A= [1; 3];
B= [2];

那么要剩下的点可以是 A(1) 或者 A(2)。你的算法输出哪一个，将取决于它的工作方式，即你首先取哪个点来找到最近的点。

这种算法包括

Finding distances between each combination of A(i) and B(j). If you have the statistics toolbox, pdist2 does this for you:
```
A=[ 1 2; 3 4];
B=[1 3; 5 6; 2 1];
dist = pdist2(A,B);
```

Looping over the smallest of A or B (I'll take A, cause it is smallest in your example) and finding for each point in A the closest point in the remaining set of B:

N = size(A,1);
matchAtoB=NaN(N,1);
for ii=1:N
    dist(:,matchAtoB(1:ii-1))=Inf; % make sure that already picked points of B are not eligible to be new closest point
    [~,matchAtoB(ii)]=min(dist(ii,:));
end
matchBtoA = NaN(size(B,1),1);
matchBtoA(matchAtoB)=1:N;
remaining_indices = find(isnan(matchBtoA));

Combine result to your desired output matrices C and D:

C=arrayfun(@(ii) [A(ii,:) ; B(matchAtoB(ii),:)],1:N,'uni',false);
D=mat2cell(B(remaining_indices,:),ones(numel(remaining_indices),1),size(B,2));

请注意，这段代码也适用于一维点或更高维度（N-D），pdist2将所有内容压缩为标量距离。