Steve on Image Processing

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

My tentative plan is to do three posts on this algorithm topic:

1. Explain the basic idea (today)

2. Show some examples using Image Processing Toolbox functions

3. Explain an algorithm optimization we recently put in the toolbox.

Let's talk 3-by-3 binary neighborhoods. Here's one:

bw = [0 0 1; 1 1 0; 1 0 0]

bw =

     0     0     1
     1     1     0
     1     0     0

Here's another:

bw = [1 0 0; 1 0 0; 0 1 0]

bw =

     1     0     0
     1     0     0
     0     1     0

OK, that might get old real fast.

QUESTION: How many different 3-by-3 binary neighborhoods are there?

Each pixel in the neighborhood can take on only two values, and there are nine pixels in the neighborhood, so the answer is:

2^9

ans =

   512

That's not so many different possibilities, although it would certainly be tedious to write them all out by hand! Is there an easy way to generate them?

I'm sure there are lots of reasonable methods. One way, used by the Image Processing Toolbox function makelut, is to use the 9-bit binary representation of the integers from 0 to 511.

label = 5;
bin = dec2bin(label, 9)

bin =

000000101

bin is a 9-character string. A logical comparison and a reshape turns it into a binary neighborhood:

bw = reshape(bin == '1', 3, 3)

bw =

     0     0     1
     0     0     0
     0     0     1

Just repeat this for the other 511 integers in the range [0,511] and you'll have all possible 3-by-3 neighborhoods. Compute the output of your operation for each one and save the result in a table.

Then use this procedure to implement your operation:

For each input pixel:
  Extract the 3-by-3 neighborhood
  Compute the table index corresponding to the neighborhood
  Insert the table value at that index into the output image

Computing the table index corresponding to a given neighborhood can be done by using bin2dec. Note that bin2dec 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.

str = repmat('0', 1, 9);
str(bw(:)') = '1';
bin2dec(str)

ans =

     5

And that's the heart of the lookup table algorithm for binary image neighborhood processes.

In my next post on this topic, I'll introduce the Image Processing Toolbox functions makelut and applylut and show examples illustrating their use.

Get the MATLAB code

Published with MATLAB® 7.6