获取到点集的最小坐标距离的矩阵 [英] Get Matrix of minimum coordinate distance to point set
问题描述
我有一组点或坐标，例如{(3,3)，(3,4)，(4,5)，...}，并希望建立到该点集的最小距离的矩阵.让我使用一个可运行的示例进行说明:
I have a set of points or coordinates like {(3,3), (3,4), (4,5), ...} and want to build a matrix with the minimum distance to this point set. Let me illustrate using a runnable example:
width = 10;
height = 10;
% Get min distance to those points
pts = [3 3; 3 4; 3 5; 2 4];
sumSPts = length(pts);
% Helper to determine element coordinates
[cols, rows] = meshgrid(1:width, 1:height);
PtCoords = cat(3, rows, cols);
AllDistances = zeros(height, width,sumSPts);
% To get Roh_I of evry pt
for k = 1:sumSPts
% Get coordinates of current Scribble Point
currPt = pts(k,:);
% Get Row and Col diffs
RowDiff = PtCoords(:,:,1) - currPt(1);
ColDiff = PtCoords(:,:,2) - currPt(2);
AllDistances(:,:,k) = sqrt(RowDiff.^2 + ColDiff.^2);
end
MinDistances = min(AllDistances, [], 3);
这段代码运行得很好，但是我必须处理大约700亿个条目的矩阵大小(高度= 700，宽度= 500，sumSPts = 2k)，这减慢了计算速度.有没有更好的算法来加快速度?
This code runs perfectly fine but I have to deal with matrix sizes of about 700 milion entries (height = 700, width = 500, sumSPts = 2k) and this slows down the calculation. Is there a better algorithm to speed things up?
推荐答案
如评论中所述，您不必将所有内容都放入一个巨大的矩阵中并处理巨大的矩阵.您可以:
As stated in the comments, you don't necessary have to put everything into a huge matrix and deal with gigantic matrices. You can :
1.将pts矩阵切成较小的切片(长度为100)
2.在切片上循环并在这些点上计算Mindistances切片
2. Loop on the slices and calculate the Mindistances slice over these points
3.取得全球最低
tic
Mindistances=[];
width = 500;
height = 700;
Np=2000;
pts = [randi(width,Np,1) randi(height,Np,1)];
SliceSize=100;
[Xcoords,Ycoords]=meshgrid(1:width,1:height);
% Compute the minima for the slices from 1 to floor(Np/SliceSize)
for i=1:floor(Np/SliceSize)
% Calculate indexes of the next slice
SliceIndexes=((i-1)*SliceSize+1):i*SliceSize
% Get the corresponding points and reshape them to a vector along the 3rd dim.
Xpts=reshape(pts(SliceIndexes,1),1,1,[]);
Ypts=reshape(pts(SliceIndexes,2),1,1,[]);
% Do all the diffs between your coordinates and your points using bsxfun singleton expansion
Xdiffs=bsxfun(@minus,Xcoords,Xpts);
Ydiffs=bsxfun(@minus,Ycoords,Ypts);
% Calculate all the distances of the slice in one call
Alldistances=bsxfun(@hypot,Xdiffs,Ydiffs);
% Concatenate the mindistances
Mindistances=cat(3,Mindistances,min(Alldistances,[],3));
end
% Check if last slice needed
if mod(Np,SliceSize)~=0
% Get the corresponding points and reshape them to a vector along the 3rd dim.
Xpts=reshape(pts(floor(Np/SliceSize)*SliceSize+1:end,1),1,1,[]);
Ypts=reshape(pts(floor(Np/SliceSize)*SliceSize+1:end,2),1,1,[]);
% Do all the diffs between your coordinates and your points using bsxfun singleton expansion
Xdiffs=bsxfun(@minus,Xcoords,Xpts);
Ydiffs=bsxfun(@minus,Ycoords,Ypts);
% Calculate all the distances of the slice in one call
Alldistances=bsxfun(@hypot,Xdiffs,Ydiffs);
% Concatenate the mindistances
Mindistances=cat(3,Mindistances,min(Alldistances,[],3));
end
% Get global minimum
Mindistances=min(Mindistances,[],3);
toc
经过的时间是9.830051秒.
Elapsed time is 9.830051 seconds.
注意:
您最终不会做更少的计算.但这将减少您的内存使用量(700M的内存占用45Go的内存占用两倍)，从而加快了处理速度(还借助矢量化)
Note :
You'll not end up doing less calculations. But It will be a lot less intensive for your memory (700M doubles takes 45Go in memory), thus speeding up the process (With the help of vectorizing aswell)
bsxfun的一大优势在于，您不必将其值沿相同维度的矩阵供入.
One of the great strength of bsxfun is that you don't have to feed it matrices whose values are along the same dimensions.
例如:
说我有两个向量X和Y定义为:
Say I have two vectors X and Y defined as :
X=[1 2]; % row vector X
Y=[1;2]; % Column vector Y
我想要一个2x2矩阵Z作为1<=i<=2 and 1<=j<=2的Z(i,j)=X(i)+Y(j)构建.
And that I want a 2x2 matrix Z built as Z(i,j)=X(i)+Y(j) for 1<=i<=2 and 1<=j<=2.
假设您不知道meshgrid的存在(该示例有点太简单了)，那么您就必须这样做:
Suppose you don't know about the existence of meshgrid (The example is a bit too simple), then you'll have to do :
Xs=repmat(X,2,1);
Ys=repmat(Y,1,2);
Z=Xs+Ys;
使用bsxfun时，您可以执行以下操作:
While with bsxfun you can just do :
Z=bsxfun(@plus,X,Y);
例如，要计算Z(2,2)的值，bsxfun将自动获取X和Y的第二个值并进行计算.这样的优点是可以节省大量内存空间(在此示例中无需定义Xs和Ys)，并且在处理大型矩阵时速度更快.
To calculate the value of Z(2,2) for example, bsxfun will automatically fetch the second value of X and Y and compute. This has the advantage of saving a lot of memory space (No need to define Xs and Ys in this example) and being faster with big matrices.
如果您有兴趣比较bsxfun和repmat之间的计算时间，这里有两个 excellent (单词不够强大) Divakar的SO帖子:
If you're interested with comparing the computational time between bsxfun and repmat, here are two excellent (word is not even strong enough) SO posts by Divakar :
这篇关于获取到点集的最小坐标距离的矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
