Graphics Gems IV. Binary Image Thinning Using Neigborhood Maps

Question

What's mean this expression in algorithm?

p = ((p<<1)&0666) | ((q<<3)&0110) | (Image->scanLine(y+1)[x+1] != 0);

Algorithm "Binary Image Thinning Using Neigborhood Maps" in a book "Graphics Gems IV":

    static int  masks[] = {0200, 0002, 0040, 0010};

 uchar delete_[512] = 
 {
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,1,0,0,1,1,  0,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,1,1,1,0,1,1,  0,0,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  1,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,1,1,0,0,1,1, 
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  1,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,1,1,1,0,1,1,  1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,0,0,0,0,0,0,  1,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,1,1,1,0,1,1,  1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,1,1,1,0,1,1,  0,0,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,0,0,0,0,0,0,  1,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,1,1,1,0,1,1,  1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,0,0,0,0,0,0,  1,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,1,1,1,0,1,1,  1,1,1,1,1,1,1,1
 };

  int xsize, ysize; 
  int x, y; 
 int i;  
 int count = 1; 
 int p, q;  
 uchar *qb;
 int m;


 xsize = Image->width();
 ysize = Image->height();
 qb = (uchar*) malloc (xsize*sizeof(uchar));
 qb[xsize-1] = 0;

    while(count) 
 { 
  count = 0;
  for (i = 0; i < 4; ++i) 
  {
   m = masks[i];
   p = Image->scanLine(0)[0] != 0;

   for (x = 0; x < xsize-1; ++x)
    qb[x] = p = ((p<<1)&0006) | (Image->scanLine(0)[x+1] != 0);

   // Scan image for pixel deletion candidates.
   for (y = 0; y < ysize-1; ++y) 
   {
    q = qb[0];
    p = ((q<<3)&0110) | (Image->scanLine(y+1)[0] != 0);

    for (x = 0; x < xsize-1; ++x) 
    { 
     q = qb[x];
     p = ((p<<1)&0666) | ((q<<3)&0110) | (Image->scanLine(y+1)[x+1] != 0);
     qb[x] = p;
     if  ((p&m)==0 && delete_[p])
     {
      count++;
      Image->scanLine(y)[x] = 0; 
     } 
    }

Answer 1

It looks like a bitwise manipulation. Do you not understand the individual operations, or do you not understand why that manipulation is being done (if the later, a link to a description of the algorithm is essential, BTW)?

Operators in that line:

• << right shift operator (move the bits of p to more significant positions according to the RH argument)
• & in this context the bitwise and
• | the bitwise or

A helpful thing to recall here is that integer literals that start with '0' are expressed in octal which means that you can read the binary digits right out of the on-screen representation (well, with a little practice, anyway). The constants here are (666)_8 = (110110110)_2 and (0110)_8 = (001001000)_2.

Answer 2

(See commented source code)

The variables m, p, q, and elements of the qb array are 9-bit numbers that represent the 3x3-pixel "neighborhood" of a pixel.

Suppose your image looks like this (each letter represents a pixel, which is either 'on' or 'off' (1 or 0, black or white):

    ---x---
    0123456
| 0 abcdefg
| 1 hijklmn
y 2 opqrstu
| 3 vwxyz{|

The pixel at (x,y) location (2,1) is j. The neighborhood of that pixel is

bcd
ijk  // 3x3 grid centered on j
pqr

Since each pixel has a binary value, the neighborhood can be represented in 9 bits. The neighborhood above can be written out linearly, expressed in binary as bcd_ijk_pqr. The grouping of 3 pixels in a row makes octal a good choice, since each octal digit represents three bits.

Once you have a neighborhood expressed as a 9-bit value, you can do bit-manipulation on it. An operation such as ((p << 1) & 0666) takes a neighborhood, shifts all bits to the left one position, and clears the rightmost column of bits. For example, the shift changes bcd_ijk_pqr to cdi_jkp_qr@ (where @ represents a 'null' bit, by default 0). Then the mask changes it to cd@_jk@_qr@. Expressed in 3x3 grid form:

cd@
jk@
qr@

Essentially, the whole grid has been shifted to the left.

Similarly, an operation such as ((q << 3) & 0110) shifts all bits three positions (moves rows up) and clears the first two columns of bits. So bcd_ijk_pqr becomes ijk_pqr_@@@ and then after the masking, becomes @@k_@@r_@@@.

The gist of the algorithm is to evaluate the neighborhood of each pixel to determine whether to turn that pixel off (delete it). This line does the evaluation:

if  ((p&m)==0 && delete_[p])

Everything that precedes that line is done to set up the neighborhood in p. The code is written so that each pixel value is read exactly once per pass.

The qb array stores the neighborhood for each pixel in the previous scanline. Note that the elements of qb are only 8-bits wide. This means the upper-left pixel of the neighborhood is omitted. That is not a problem, since any time qb is used, it gets shifted up a row.

So to answer your question about what this line does:

p = ((p<<1)&0666) | ((q<<3)&0110) | (Image->scanLine(y+1)[x+1] != 0);

It creates the neighborhood of a pixel by merging the following:

• the neighborhood of the previous pixel on the same line, shifted to the left
• the right column of the neighborhood of the pixel one row higher, shifted up
• the (x+1,y+1) pixel of the image, put into the "southwest" corner

For example, the neighborhood about j is calculated as:

p = bc@_ij@_pq@ | @@d_@@k_@@@ | r

    bc@ | @@d | @@@   bcd
p = ij@ | @@k | @@@ = ijk
    pq@ | @@@ | @@r   pqr