{"id":254,"date":"2010-11-12T10:43:49","date_gmt":"2010-11-12T10:43:49","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/2010\/11\/12\/meet-the-neighbors\/"},"modified":"2010-11-09T18:56:32","modified_gmt":"2010-11-09T18:56:32","slug":"meet-the-neighbors","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2010\/11\/12\/meet-the-neighbors\/","title":{"rendered":"Meet the Neighbors"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <introduction>\r\n      <p>Some calculations in MATLAB, including, for example, calculating local means or finite differences, or applying some other\r\n         filter locally, operate on neighboring matrix elements.  Doing so in an efficient manner is easy under the right conditions\r\n         with MATLAB. Steve talked about <a href=\"https:\/\/blogs.mathworks.com\/steve\/2008\/02\/25\/neighbor-indexing-2\/\">neighbor indexing<\/a> on his blog a few years ago.\r\n      <\/p>\r\n   <\/introduction>\r\n   <h3>Contents<\/h3>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"#1\">Linear Indexing<\/a><\/li>\r\n         <li><a href=\"#8\">Table of Offsets<\/a><\/li>\r\n         <li><a href=\"#12\">Caution<\/a><\/li>\r\n         <li><a href=\"#13\">Do Your Calculations Require Addressing Neighbors?<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>Linear Indexing<a name=\"1\"><\/a><\/h3>\r\n   <p>I've talked about <a href=\"https:\/\/blogs.mathworks.com\/loren\/category\/indexing\/\">indexing<\/a> a bunch of times previously if you want to read about the topic from different vantages.  For now, let me remind you what\r\n      linear indexing is.\r\n   <\/p>\r\n   <p>MATLAB stores data column-wise.  That is, each column of data is stacked below the previous one in a contiguous block of memory.\r\n       If I have this matrix <tt>A<\/tt><\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">A = [ 1 3 5; 2 4 6]<\/pre><pre style=\"font-style:oblique\">A =\r\n     1     3     5\r\n     2     4     6\r\n<\/pre><p>I can address the element in the 1st row, 2nd column via subscripts.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">A(1,2)<\/pre><pre style=\"font-style:oblique\">ans =\r\n     3\r\n<\/pre><p>I can also extract this element by indexing as if <tt>A<\/tt> was strictly a column vector.  And then I could extract the same element with what we call _linear indexing.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">A(3)<\/pre><pre style=\"font-style:oblique\">ans =\r\n     3\r\n<\/pre><p>There are functions to convert between subscripts and linear indicies. Take a look at <a href=\"https:\/\/www.mathworks.com\/help\/releases\/R2010b\/techdoc\/ref\/sub2ind.html\"><tt>sub2ind<\/tt><\/a> and <a href=\"https:\/\/www.mathworks.com\/help\/releases\/R2010b\/techdoc\/ref\/ind2sub.html\"><tt>ind2sub<\/tt><\/a>.\r\n   <\/p>\r\n   <p>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\r\n      rows the matrix has.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">nrows = size(A,1)<\/pre><pre style=\"font-style:oblique\">nrows =\r\n     2\r\n<\/pre><p>Suppose now I have a larger matrix and I want to address some of the neighbors of a given element, located at <tt>(row,column)<\/tt>, corresponding to linear index <tt>linidx<\/tt>.  As long as the element is not too near an edge of the matrix, I can think about neighbors as offsets in different directions.\r\n       So, the neighbor to the south of this element corresponds to <tt>(row+1,column)<\/tt>, or linear indexing terms, <tt>linidx+1<\/tt>.\r\n   <\/p>\r\n   <h3>Table of Offsets<a name=\"8\"><\/a><\/h3>\r\n   <p>Here's a table of neighbor offsets for the 4 elements adject to <tt>element<\/tt> and not on the diagonals.\r\n   <\/p>\r\n   <div>\r\n      <ul>\r\n         <li>S = ind+1<\/li>\r\n         <li>N = ind-1<\/li>\r\n         <li>E = ind+nrows<\/li>\r\n         <li>W = ind-nrows<\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <p>So you can easily see the correspondence, I am creating a matrix with values that are the numbers <tt>1:30<\/tt> arranged so they appear in ascending order when looked at as a 1-D vector.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">nrows = 5;\r\nncolumns = 6;\r\nB = reshape(1:30,nrows, ncolumns)<\/pre><pre style=\"font-style:oblique\">B =\r\n     1     6    11    16    21    26\r\n     2     7    12    17    22    27\r\n     3     8    13    18    23    28\r\n     4     9    14    19    24    29\r\n     5    10    15    20    25    30\r\n<\/pre><p>If I want to find the neighbors for elements <tt>(2,4)<\/tt> and <tt>(3,2)<\/tt>, I can do so in a vectorized way.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">linPairs = sub2ind(size(B), [2 3], [4 2])<\/pre><pre style=\"font-style:oblique\">linPairs =\r\n    17     8\r\n<\/pre><p>If I want the points east of these, I simply add <tt>nrows<\/tt>.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">eastVals = B(linPairs+nrows)<\/pre><pre style=\"font-style:oblique\">eastVals =\r\n    22    13\r\n<\/pre><h3>Caution<a name=\"12\"><\/a><\/h3>\r\n   <p>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\r\n      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\r\n      row or column.  If there's danger of that, you may want to pad your initial array before doing your neighbor operations, and\r\n      then peel the padding back off when you are finished.\r\n   <\/p>\r\n   <h3>Do Your Calculations Require Addressing Neighbors?<a name=\"13\"><\/a><\/h3>\r\n   <p>What's your experience working with neighbors?  Let me know <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=254#respond\">here<\/a>. Beware the edges\r\n   <\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_e453ebf80d9f438997b11b6da837c367() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='e453ebf80d9f438997b11b6da837c367 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' e453ebf80d9f438997b11b6da837c367';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        author = 'Loren Shure';\r\n        copyright = 'Copyright 2010 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add author and copyright lines at the bottom if specified.\r\n        if ((author.length > 0) || (copyright.length > 0)) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (author.length > 0) {\r\n                d.writeln('% _' + author + '_');\r\n            }\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n      \r\n      d.title = title + ' (MATLAB code)';\r\n      d.close();\r\n      }   \r\n      \r\n-->\r\n<\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_e453ebf80d9f438997b11b6da837c367()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n            the MATLAB code \r\n            <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.11<br><\/p>\r\n<\/div>\r\n<!--\r\ne453ebf80d9f438997b11b6da837c367 ##### SOURCE BEGIN #####\r\n%% Meet the Neighbors\r\n% Some calculations in MATLAB, including, for example, calculating local\r\n% means or finite differences, or applying some other filter locally,\r\n% operate on neighboring matrix elements.  Doing so in an efficient manner\r\n% is easy under the right conditions with MATLAB. Steve talked about\r\n% <https:\/\/blogs.mathworks.com\/steve\/2008\/02\/25\/neighbor-indexing-2\/\r\n% neighbor indexing> on his blog a few years ago.\r\n%% Linear Indexing\r\n% I've talked about <https:\/\/blogs.mathworks.com\/loren\/category\/indexing\/\r\n% indexing> a bunch of times previously if you want to read about the topic\r\n% from different vantages.  For now, let me remind you what linear indexing\r\n% is.\r\n%% \r\n% MATLAB stores data column-wise.  That is, each column of data is stacked\r\n% below the previous one in a contiguous block of memory.  If I have this\r\n% matrix |A|\r\nA = [ 1 3 5; 2 4 6]\r\n%%\r\n% I can address the element in the 1st row, 2nd column via subscripts.\r\nA(1,2)\r\n%%\r\n% I can also extract this element by indexing as if |A| was strictly a\r\n% column vector.  And then I could extract the same element with what we\r\n% call _linear indexing.\r\nA(3)\r\n%%\r\n% There are functions to convert between subscripts and linear indicies.\r\n% Take a look at\r\n% <https:\/\/www.mathworks.com\/help\/releases\/R2010b\/techdoc\/ref\/sub2ind.html\r\n% |sub2ind|> and\r\n% <https:\/\/www.mathworks.com\/help\/releases\/R2010b\/techdoc\/ref\/ind2sub.html\r\n% |ind2sub|>.\r\n%%\r\n% I can also do the conversion from subscript to linear index easily\r\n% myself.  For a 2-D array, I simply need to know how many rows the matrix\r\n% has.\r\nnrows = size(A,1)\r\n%%\r\n% Suppose now I have a larger matrix and I want to address some of the\r\n% neighbors of a given element, located at |(row,column)|, corresponding to\r\n% linear index |linidx|.  As long as the element is not too near an edge of\r\n% the matrix, I can think about neighbors as offsets in different\r\n% directions.  So, the neighbor to the south of this element corresponds to\r\n% |(row+1,column)|, or linear indexing terms, |linidx+1|.\r\n%% Table of Offsets\r\n% Here's a table of neighbor offsets for the 4 elements adject to |element|\r\n% and not on the diagonals.\r\n%\r\n% * S = ind+1\r\n% * N = ind-1\r\n% * E = ind+nrows\r\n% * W = ind-nrows\r\n%%\r\n% So you can easily see the correspondence, I am creating a matrix with\r\n% values that are the numbers |1:30| arranged so they appear in ascending\r\n% order when looked at as a 1-D vector.\r\nnrows = 5; \r\nncolumns = 6;\r\nB = reshape(1:30,nrows, ncolumns)\r\n%%\r\n% If I want to find the neighbors for elements |(2,4)| and |(3,2)|, I can\r\n% do so in a vectorized way.\r\nlinPairs = sub2ind(size(B), [2 3], [4 2])\r\n%% \r\n% If I want the points east of these, I simply add |nrows|.\r\neastVals = B(linPairs+nrows)\r\n%% Caution\r\n% The one cautionary comment is that you must be very sure you aren't going\r\n% to go past an edge boundary from your elements of interest.  If you do,\r\n% you will either go outside the bounds of your array or pick up a value\r\n% that wrapped around to the next row or column.  If there's danger of\r\n% that, you may want to pad your initial array before doing your neighbor\r\n% operations, and then peel the padding back off when you are finished.\r\n%% Do Your Calculations Require Addressing Neighbors?\r\n% What's your experience working with neighbors?  Let me know\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=254#respond here>.\r\n% Beware the edges\r\n##### SOURCE END ##### e453ebf80d9f438997b11b6da837c367\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   \r\n      Some calculations in MATLAB, including, for example, calculating local means or finite differences, or applying some other\r\n         filter locally, operate on neighboring matrix... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2010\/11\/12\/meet-the-neighbors\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/254"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=254"}],"version-history":[{"count":0,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/254\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=254"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=254"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=254"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}