How to find all neighbours of an element in N-dimensional matrix

42 次查看（过去 30 天）
dave
dave 2013-9-11
评论： Image Analyst 2017-10-31
I just can't wrap my head around how to find all neighbours of an element in a N-dimensional matrix. After reading through the documentation on spatial searching I think it could be done using the Delaunay triangulation. However, these topics are still a bit too advanced for me, so any help would be appreciated.
  1 个评论
dave
dave 2013-9-12
编辑：dave 2013-9-12
Update: Thanks everybody for your suggestions. After all Shashank's hint with the knnsearch turned out to be the easiest solution in my case, since I have the statistics toolbox. If you don't have it, the solutions provided by Matt J and Image Analyst are also very useful.

请先登录，再进行评论。

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

采纳的回答

Matt J
Matt J 2013-9-11
编辑：Matt J 2013-9-11
What I often like to do is make an offset mask, as follows
s=size(yourmatrix);
N=length(s);
[c1{1:N}]=ndgrid(1:3);
c2(1:N)={2};
offsets=sub2ind(s,c1{:}) - sub2ind(s,c2{:})
Now, for any linear index in your matrix L, you can get all its neighbors by doing
neighbors = yourmatrix(L+offsets)
It won't work at the edges of the matrix, but you can take care of that by padding the edges first.
  14 个评论
显示 12更早的评论

请先登录，再进行评论。

更多回答（3 个）

Shashank Prasanna
Shashank Prasanna 2013-9-11
If you have the Statistics Toolbox installed, there are couple of nearest neighbor searching tools that you might find very useful. Although some of these concepts may be advanced for a casual user, the functionality itself is very quite easy to use, that's really the power of MATLAB:
One way to speed up higher dimensional neighbor searching is to use an optimized data structure such as k dimensional trees, and this is easy to do so as below:
kdtreeNS = KDTreeSearcher(x);
[n,d]=knnsearch(kdtreeNS,x);
Here is the page from the doc:
http://www.mathworks.com/help/stats/kdtreesearcher.knnsearch.html
  2 个评论
dave
dave 2013-9-11
Thanks for the suggestion...Yes, I do have the Statistics Toolbox, but after reading through the doc for a while I'm still not sure how to apply KDTreeSearcher() to my n-dimensional matrix, since it obviously only accepts 2-dimensional input (X). What am I doing wrong?
Shashank Prasanna
Shashank Prasanna 2013-9-11
Michael, I misunderstood your question. I made the assumption that you were referring to the columns as dimensions in |R^n space .
None of these function work on multidimensional matrices. If you have data in some n dimensional space each instance or observation can be represented as a vector with n entries. I am not sure how your data is represented but if you are able to represent it in a why described you can use all the functionality that I mentioned to do your neighbor search.

请先登录，再进行评论。

Image Analyst
Image Analyst 2013-9-11
You just take the index, the index plus one, and the index minus one, for every other dimension, but exclude the index of where you're at. For example if you have a 3D matrix, and you're at x=3, y=6, and z=9, you'd have all permutations of x in [2,3,4] with y in [5,6,7] with z in [8,9,10] but don't include the point itself with x=3,y=6, z=9. So that's 3*3*3-1 neighbors in 3D. For N dimensions you'd have 3 * 3 * 3 * ....(a total N times) * 3 -1 neighbors. So 2D gives 3*3-1 = 8 neighbors, 3D gives 26 neighbors, 4D gives 80 neighbors, etc.
  6 个评论
显示 4更早的评论
dave
dave 2013-9-11
编辑：dave 2013-9-11
@ImageAnalyst: I like your suggestion with the (sub-)hypervolume. Here's what I have so far:
indices = cell(1, length(size(hyperVolume)));
for i = 1:length(hyperVolume(:)),
[indices{:}] = ind2sub(size(hyperVolume), i);
%...
end
This way I iterate over every element of the hypervolume and store the indices of the current element. The only thing that's still unclear to me is how to get from the cell containing the indices to your line which extracts the subvolume:
endsubHyperVolume = hyperVolume(4:6, 18:20, 9:11, 7:9, 1:3);
Any idea?
Image Analyst
Image Analyst 2013-9-11
I'd use loops over each dimension, so for 5 dimensions like my example
for d1=1:d1max
for d2=1:d2max
for d3=1:d3max
for d4=1:d4max
for d5=1:d5max
subHyperVolume = hyperVolume(...
d1-1:d1+1,...
d2-1:d2+1,...
d3-1:d3+1,...
d4-1:d4+1,...
d5-1:d5+1,...
);
end
end
end
end
end

请先登录，再进行评论。

Sean de Wolski
Sean de Wolski 2014-6-24

类别

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

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by