Matlab最近邻/跟踪点

Question

我有一组 n 复数，它们从时间步长 1 到 nsampl 穿过复平面。我想绘制这些数字及其随时间的轨迹（y 轴显示虚部，x 轴显示实部）。这些数字存储在 n x nsampl 向量中。但是，在每个时间步中，n 点的顺序是随机的。因此，在每个时间步中，我在最后一个时间步中选择一个点，在当前时间步中找到它最近的邻居并将其放在与当前点相同的位置。然后我对所有其他 n-1 点重复该操作并继续下一个时间步。这样，上一步中的每个点都与新步骤中的一个点关联（1:1 关系）。下面给出了我当前的实现和示例。但是我的实现速度非常慢（10 x 4000 复数大约需要 10 秒）。因为我想同时增加设置大小 n 和时间范围 nsampl 这对我来说真的很重要。有没有更聪明的方法来实现它以获得一些性能？

n=3 且 nsampl=2 的示例：

%manually create a test vector X
X=zeros(3,2); % zeros(n,nsampl)
X(:,1)=[1+1i; 2+2i; 3+3i];
X(:,2)=[2.1+2i; 5+5i; 1.1+1.1i]; % <-- this is my vector with complex numbers

%vector sort algorithm
for k=2:nsampl
    Xlast=[real(X(:,k-1)) imag(X(:,k-1))];          % create vector with x/y-coords from last time step
    Xcur=[real(X(:,k)) imag(X(:,k))];               % create vector with x/y-coords from current time step
    for i=1:size(X,1) % loop over all n points
        idx = knnsearch(Xcur(i:end,:),Xlast(i,:));  %find nearest neighbor to Xlast(i,:), but only use the points not already associated, thus Xcur(i:end,:) points
        idx = idx + i - 1;
        Xcur([i idx],:) = Xcur([idx i],:);          %sort nearest neighbor to the same position in the vector as it was in the last time step
    end
    X(:,k) = Xcur(:,1)+1i*Xcur(:,2);                %revert x/y coordinates to a complex number
end

结果：

X(:,2)=[1.1+1.1i; 2.1+2i; 5+5i];

谁能帮我加快这段代码的速度？

Answer 1

您要解决的问题是组合优化，它可以通过 the hungarian algorithm (aka munkres). Luckily there is a implementation for matlab available for download. 下载文件并将其放在您的搜索路径或函数旁边。使用它的代码是：

for k=2:size(X,2)
   %build up a cost matrix, here cost is the distance between two points.
   pairwise_distances=abs(bsxfun(@minus,X(:,k-1),X(:,k).'));
   %let the algorithm find the optimal pairing
   permutation=munkres(pairwise_distances);
   %apply it
   X(:,k)=X(permutation,k);
end

Matlab最近邻/跟踪点

Matlab nearest neighbor / track points

performance

matlab

kdtree

nearest-neighbor