File size: 1,559 Bytes
9677843 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
function [ds,inds] = knnCPU(R,Q,k,maxMem)
% Find the k nearest neighbors for each element of the query set Q among
% the points in the reference set R
% Q is Nxd where N is the number of query points and d is the dimension
% R is Mxd where M is the number of reference points and d is the dimension
% k is the number of nearest neighbors desired
% maxMem is the number of GB of ram knnCPU can use
% ds is Nxk and contains the distances to the k nearest neighbors.
% inds is Nxk and contains the indices of the k nearest neighbors.
if (nargin<4)
maxMem = 2;
end
M = size(R,1);
N = size(Q,1);
maxArray = (maxMem*2500)^2;
blockSize = floor(maxArray/M);
blocks = floor(N/blockSize);
ds = zeros(N,k);
inds = zeros(N,k);
Nr = sum(R.^2,2);
Nq = sum(Q.^2,2);
for b = 1:blocks
dtemp = -2*R*Q((b-1)*blockSize + 1:b*blockSize,:)';
dtemp = bsxfun(@plus,dtemp,Nr);
dtemp = bsxfun(@plus,dtemp,Nq((b-1)*blockSize + 1:b*blockSize)');
[dst,indst] = sort(dtemp,1);
ds((b-1)*blockSize + 1:b*blockSize,:) = dst(1:k,:)';
inds((b-1)*blockSize + 1:b*blockSize,:) = indst(1:k,:)';
end
if (blocks*blockSize < N)
dtemp = -2*R*Q(blocks*blockSize + 1:N,:)';
dtemp = bsxfun(@plus,dtemp,Nr);
dtemp = bsxfun(@plus,dtemp,Nq(blocks*blockSize + 1:N)');
[dst,indst] = sort(dtemp,1);
ds(blocks*blockSize + 1:N,:) = dst(1:k,:)';
inds(blocks*blockSize + 1:N,:) = indst(1:k,:)';
end
ds = real(sqrt(ds));
end
|