{"id":209,"date":"2008-05-07T08:49:55","date_gmt":"2008-05-07T12:49:55","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/05\/07\/lookup-tables-for-binary-image-processing\/"},"modified":"2019-10-28T09:30:43","modified_gmt":"2019-10-28T13:30:43","slug":"lookup-tables-for-binary-image-processing","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/05\/07\/lookup-tables-for-binary-image-processing\/","title":{"rendered":"Lookup tables for binary image processing"},"content":{"rendered":"
\r\n

Today I'm introducing a short series about using lookup tables<\/i> to implement neighborhood operations in binary images. This is a fast implementation technique that works for small neighborhoods,\r\n typically 2-by-2 or 3-by-3.\r\n <\/p>\r\n

My tentative plan is to do three posts on this algorithm topic:<\/p>\r\n

1. Explain the basic idea (today)<\/p>\r\n

2. Show some examples using Image Processing Toolbox functions<\/p>\r\n

3. Explain an algorithm optimization we recently put in the toolbox.<\/p>\r\n

Let's talk 3-by-3 binary neighborhoods. Here's one:<\/p>

bw = [0 0 1; 1 1 0; 1 0 0]<\/pre>
\r\nbw =\r\n\r\n     0     0     1\r\n     1     1     0\r\n     1     0     0\r\n\r\n<\/pre>
Here's another:<\/p>
bw = [1 0 0; 1 0 0; 0 1 0]<\/pre>
\r\nbw =\r\n\r\n     1     0     0\r\n     1     0     0\r\n     0     1     0\r\n\r\n<\/pre>
OK, that might get old real fast.<\/p>\r\n   
QUESTION:<\/b> How many different 3-by-3 binary neighborhoods are there?\r\n   <\/p>\r\n   
Each pixel in the neighborhood can take on only two values, and there are nine pixels in the neighborhood, so the answer is:<\/p>
2^9<\/pre>
\r\nans =\r\n\r\n   512\r\n\r\n<\/pre>
That's not so many different possibilities, although it would certainly be tedious to write them all out by hand!  Is there\r\n      an easy way to generate them?\r\n   <\/p>\r\n   
I'm sure there are lots of reasonable methods.  One way, used by the Image Processing Toolbox function makelut<\/tt>, is to use the 9-bit binary representation of the integers from 0 to 511.\r\n   <\/p>
label = 5;\r\nbin = dec2bin(label, 9)<\/pre>
\r\nbin =\r\n\r\n000000101\r\n\r\n<\/pre>
bin<\/tt> is a 9-character string.  A logical comparison and a reshape turns it into a binary neighborhood:\r\n   <\/p>
bw = reshape(bin == '1'<\/span>, 3, 3)<\/pre>
\r\nbw =\r\n\r\n     0     0     1\r\n     0     0     0\r\n     0     0     1\r\n\r\n<\/pre>
Just repeat this for the other 511 integers in the range [0,511] and you'll have all possible 3-by-3 neighborhoods.  Compute\r\n      the output of your operation for each one and save the result in a table.\r\n   <\/p>\r\n   
Then use this procedure to implement your operation:<\/p>
For each input pixel:\r\n  Extract the 3-by-3 neighborhood\r\n  Compute the table index corresponding to the neighborhood\r\n  Insert the table value at that index into the output image<\/pre>
Computing the table index corresponding to a given neighborhood can be done by using bin2dec<\/tt>.  Note that bin2dec<\/tt> takes a string, so we have to do a little work first to convert the binary neighborhood to a string of '0' and '1' characters.\r\n   <\/p>
str = repmat('0'<\/span>, 1, 9);\r\nstr(bw(:)') = '1'<\/span>;\r\nbin2dec(str)<\/pre>
\r\nans =\r\n\r\n     5\r\n\r\n<\/pre>
And that's the heart of the lookup table algorithm for binary image neighborhood processes.<\/p>\r\n   
In my next post on this topic, I'll introduce the Image Processing Toolbox functions makelut<\/tt> and applylut<\/tt> and show examples illustrating their use.\r\n   <\/p>