{"id":128,"date":"2007-03-28T09:56:36","date_gmt":"2007-03-28T13:56:36","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2007\/03\/28\/neighbor-indexing\/"},"modified":"2019-10-23T08:48:31","modified_gmt":"2019-10-23T12:48:31","slug":"neighbor-indexing","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2007\/03\/28\/neighbor-indexing\/","title":{"rendered":"Neighbor indexing"},"content":{"rendered":"
\r\n

In response to my last post about connected component labeling algorithms<\/a>, blog reader JanKees wanted to know<\/a> how to find neighboring pixel pairs programmatically. Prompted by this question, I thought I would describe a MATLAB indexing\r\n technique that is useful for various kinds of neighbor searching applications.\r\n <\/p>\r\n

To get started, let's first review linear indexing. If you use a single subscript to index into a matrix, you access elements\r\n in the matrix based on the way they are stored in memory, which is by columns. For example:\r\n <\/p>

a = magic(3)<\/pre>
\r\na =\r\n\r\n     8     1     6\r\n     3     5     7\r\n     4     9     2\r\n\r\n<\/pre>
a(3,1)<\/tt> is the third element in the columnwise ordering of the elements of a<\/tt>, so a(3)<\/tt> gives you that element:\r\n   <\/p>
a(3)<\/pre>
\r\nans =\r\n\r\n     4\r\n\r\n<\/pre>
a(2,3)<\/tt> is the eighth columnwise element, so a(8)<\/tt> gives you that element:\r\n   <\/p>
a(8)<\/pre>
\r\nans =\r\n\r\n     7\r\n\r\n<\/pre>
We call this single subscript a ''linear index''. You can use signed offsets to linear indices to get from a particular matrix\r\n      element to any of its neighbors.  For example, if you subtract 1 from an element's linear index, you get the location of the\r\n      element just above.  For a matrix with M<\/tt> rows, adding M<\/tt> to an element's linear index gives you the element just to the right.  (Caveat:<\/b> This technique only works for elements that aren't on the outermost rows or columns of the matrix.)\r\n   <\/p>\r\n   
Let's apply this technique to finding the 4-connected neighborhood pairs for a simple binary image matrix.<\/p>
bw = logical([ ...<\/span>\r\n    0 0 0 0 0 0 0\r\n    0 1 1 0 0 0 0\r\n    0 1 1 0 0 0 0\r\n    0 0 0 1 1 1 0\r\n    0 0 0 1 1 1 0\r\n    0 0 0 0 0 0 0 ])<\/pre>
\r\nbw =\r\n\r\n     0     0     0     0     0     0     0\r\n     0     1     1     0     0     0     0\r\n     0     1     1     0     0     0     0\r\n     0     0     0     1     1     1     0\r\n     0     0     0     1     1     1     0\r\n     0     0     0     0     0     0     0\r\n\r\n<\/pre>
Step 1: Given the size of the matrix, compute neighborhood index offsets.<\/p>
[M,N] = size(bw);\r\nnorth_offset = -1;\r\neast_offset = M;\r\nsouth_offset = 1;\r\nwest_offset = -M;<\/pre>
Step 2: Find the linear indices for all the nonzero matrix elements.<\/p>
idx = find(bw)<\/pre>
\r\nidx =\r\n\r\n     8\r\n     9\r\n    14\r\n    15\r\n    22\r\n    23\r\n    28\r\n    29\r\n    34\r\n    35\r\n\r\n<\/pre>
Step 3: Compute the values of all the north neighbors.<\/p>
north_idx = idx + north_offset;\r\nnorth_neighbors = bw(north_idx)<\/pre>
\r\nnorth_neighbors =\r\n\r\n     0\r\n     1\r\n     0\r\n     1\r\n     0\r\n     1\r\n     0\r\n     1\r\n     0\r\n     1\r\n\r\n<\/pre>
Step 4: Construct the matrix of northern neighbor pairs. Here I'll use north_neighbors<\/tt> as a logical index to pick out elements where north_neighbors<\/tt> is nonzero.\r\n   <\/p>
north_pairs = [idx(north_neighbors), north_idx(north_neighbors)]<\/pre>
\r\nnorth_pairs =\r\n\r\n     9     8\r\n    15    14\r\n    23    22\r\n    29    28\r\n    35    34\r\n\r\n<\/pre>
Step 5: Repeat steps 3 and 4 for the other directions.<\/p>
east_idx = idx + east_offset;\r\neast_neighbors = bw(east_idx);\r\neast_pairs = [idx(east_neighbors), east_idx(east_neighbors)];\r\n\r\nsouth_idx = idx + south_offset;\r\nsouth_neighbors = bw(south_idx);\r\nsouth_pairs = [idx(south_neighbors), south_idx(south_neighbors)];\r\n\r\nwest_idx = idx + west_offset;\r\nwest_neighbors = bw(west_idx);\r\nwest_pairs = [idx(west_neighbors), west_idx(west_neighbors)];\r\n\r\nall_pairs = [north_pairs; east_pairs; south_pairs; west_pairs]<\/pre>
\r\nall_pairs =\r\n\r\n     9     8\r\n    15    14\r\n    23    22\r\n    29    28\r\n    35    34\r\n     8    14\r\n     9    15\r\n    22    28\r\n    23    29\r\n    28    34\r\n    29    35\r\n     8     9\r\n    14    15\r\n    22    23\r\n    28    29\r\n    34    35\r\n    14     8\r\n    15     9\r\n    28    22\r\n    29    23\r\n    34    28\r\n    35    29\r\n\r\n<\/pre>
Note:<\/b> Generally, you need to prepad the matrix to make sure that no nonzero elements are on the boundaries. I didn't do that here\r\n      because my sample matrix didn't need it.  Just remember that prepadding changes the element locations and the neighbor offset\r\n      values, so you'll need to compensate for that in your own code. The details will vary depending on exactly what you are doing\r\n      with the neighbor values and locations.\r\n   <\/p>\r\n   
For more information about MATLAB indexing, including linear and logical indexing, here's a MATLAB Digest article<\/a> that Loren<\/a> and I wrote a few years ago.\r\n   <\/p>