Some calculations in MATLAB, including, for example, calculating local means or finite differences, or applying some other filter locally, operate on neighboring matrix elements. Doing so in an efficient manner is easy under the right conditions with MATLAB. Steve talked about neighbor indexing on his blog a few years ago.
Contents
Linear Indexing
I've talked about indexing a bunch of times previously if you want to read about the topic from different vantages. For now, let me remind you what linear indexing is.
MATLAB stores data column-wise. That is, each column of data is stacked below the previous one in a contiguous block of memory. If I have this matrix A
A = [ 1 3 5; 2 4 6]
A =
1 3 5
2 4 6
I can address the element in the 1st row, 2nd column via subscripts.
A(1,2)
ans =
3
I can also extract this element by indexing as if A was strictly a column vector. And then I could extract the same element with what we call _linear indexing.
A(3)
ans =
3
There are functions to convert between subscripts and linear indicies. Take a look at sub2ind and ind2sub.
I can also do the conversion from subscript to linear index easily myself. For a 2-D array, I simply need to know how many rows the matrix has.
nrows = size(A,1)
nrows =
2
Suppose now I have a larger matrix and I want to address some of the neighbors of a given element, located at (row,column), corresponding to linear index linidx. As long as the element is not too near an edge of the matrix, I can think about neighbors as offsets in different directions. So, the neighbor to the south of this element corresponds to (row+1,column), or linear indexing terms, linidx+1.
Table of Offsets
Here's a table of neighbor offsets for the 4 elements adject to element and not on the diagonals.
- S = ind+1
- N = ind-1
- E = ind+nrows
- W = ind-nrows
So you can easily see the correspondence, I am creating a matrix with values that are the numbers 1:30 arranged so they appear in ascending order when looked at as a 1-D vector.
nrows = 5; ncolumns = 6; B = reshape(1:30,nrows, ncolumns)
B =
1 6 11 16 21 26
2 7 12 17 22 27
3 8 13 18 23 28
4 9 14 19 24 29
5 10 15 20 25 30
If I want to find the neighbors for elements (2,4) and (3,2), I can do so in a vectorized way.
linPairs = sub2ind(size(B), [2 3], [4 2])
linPairs =
17 8
If I want the points east of these, I simply add nrows.
eastVals = B(linPairs+nrows)
eastVals =
22 13
Caution
The one cautionary comment is that you must be very sure you aren't going to go past an edge boundary from your elements of interest. If you do, you will either go outside the bounds of your array or pick up a value that wrapped around to the next row or column. If there's danger of that, you may want to pad your initial array before doing your neighbor operations, and then peel the padding back off when you are finished.
Do Your Calculations Require Addressing Neighbors?
What's your experience working with neighbors? Let me know here. Beware the edges
Get
the MATLAB code
Published with MATLAB® 7.11
Usually I’m interested in the Neighborhood. Lets say 5 x 5 Neighborhood.
Then I find im2col to be exactly what I want.
I wish you add something similar which keeps the Matrix form (Like in nlfilter).
Once this procedure supports multi core CPU’s (Like blockproc) I will be happy.
Hi Loren,
It’s worth noting that several of our Image Processing Toolbox functions allow users to specify connectivity parameters–including custom connectivities. For those functions, the “beware the edges” consideration is generally not a concern; the Toolbox functions will nicely handle the requisite padding and edge manipulations behind the scenes.
Here’s a link to a relevant section of our documentation:
http://www.mathworks.com/access/helpdesk/help/toolbox/images/f18-16264.html#f18-12600
Also: you’ve mentioned |BSXFUN| several times in your blog. I wanted to point out that, particularly in cases where connectivity is not a syntactic input, |BSXFUN| is quite useful in specifying neighbors. For instance, for a pixel with a linear index of IDX, in an image having M rows, one can readily calculate the linear indices of the “8-connected” neighbors (N,E,S,W,NE,NW,SE,SW) with:
In this case, of course, your edge caveat is quite relevant.
Hi Loren,
I’ve been having to deal with a similar problem, and also to beware of the edges. I’ve had to determine neighbourhood in D-dimensional lattices, with or without wrapping around the edges. Because I wouldn’t know the number of dimensions beforehand, I’ve actually had to re-implement ind2sub and sub2ind to take and return an NxD matrix of indices.
Your post has prompted me to upload the files onto the File Exchange :)
Cheers,
Laurens
Laurens-
Thanks for the contribution!
–loren
Hi again,
This is really nice. I have been dealing with this issues when working with cellular automata (CA). A “neighborhood” creation function is always handy, so you can automatically generate the filter to create von Neumann neighborhood, Margolus neighborhood, Moore neighborhood or any custom neighborhood.
Thanks for the post!
-Loren
Thanks for bringing up another interesting discussion. I think we could modify the table of neighbors to accomodate for the edge boundries:
fS = @(i) i + 1 – nrows*ismember(i,B(end,:));
fN = @(i) i – 1 + nrows*ismember(i,B(1,:));
fE = @(i) i + nrows – nrows*ncolumns*ismember(i,B(:,end));
fW = @(i) i – nrows + nrows*ncolumns*ismember(i,B(:,1));
linPairs = sub2ind(size(B), [1 3 5], [1 4 6])
Svals = B(fS(linPairs))
Nvals = B(fN(linPairs))
Evals = B(fE(linPairs))
Wvals = B(fW(linPairs))
linPairs =
1 18 30
Svals =
2 19 26
Nvals =
5 17 29
Evals =
6 23 5
Wvals =
26 13 25
As an additional remark about my last posting, the function handels fS,fE,fN,fN can be combined to realise diagonal movements:
SEvals = B(fS(fE(linPairs)));
NEvals = B(fN(fE(linPairs)));
SWvals = B(fS(fW(linPairs)));
NWvals = B(fN(fW(linPairs)));
-Mukhtar
Hello,
I am writing a function that will change the state of a cell depending on the state of its 8 neighbors and itself. I need to account for cells that have neighbors beyond the edge boundaries of an mxn matrix. How can I do this?
Thanks,
Sarah
Sarah-
You probably need to try one of the techniques for padding the initial array so when you get to the edge cases, you have manufactured neighbors for doing the calculation. How you choose to pad (how many rows/columns and with what values) depends entirely on your application.
–Loren
Overloading of Operators:
In one of your topics you show:
a = [ 1 3 0 ... ] a 1×8
b = [ 2 0 4 ... ] another 1×8
y = a&b yields a 1×8 of logical components , 0s and 1s
NOW
m = a(y) returns a vector with elements of a but only for those positions where there is a 1 in y.
So now here is a special definition of ( ). Where can I access the other overloaded operators to get even more out of Matlab.
Thanks.
Terry,
The a(y) is an example of logical indexing. I’ve written about it before and also there is good documentation in MATLAB for it.
-Loren
Hey,
This is useful information. Do you have any further information on how to implement approximate nearest neighbor (e-ANN) algorithms, or von Neumann/Moore neighborhoods for discrete cellular automation?
Thank you
Sorry-
I have no further information on approximate nearest neighbor algorithmic references or tricks. You might check out Steve’s blog on image processing in case there’s any info there.
–Loren