Hit-or-miss: Do It Yourself

After an introduction of the Hit-or-miss operator [Link], it is time to see how we can implement this kind of tool in ImageJ with JavaScript....

1- Do It Yourself

The synopsis of the implementation written in pseudo-code is as follows ...

output = create_new_image();
for each pixel of the input image
  values = get_pixel_values_of_8_neighbors(pixel)
  new_pix = hit_or_miss(values)
  output.setPixel(new_pix)
end for

1-1- Implementing the convolution

The first step is to get the neighboring pixel values for each pixel values (Fig. 1). 

Fig.1: Coordinates of the eight neighbors of central pixel (X,Y).

Second, we need to compare the pixel values to the pattern of the structuring element.

A naive implementation would consist of (i) putting the values in an array and (ii) comparing them to the kernel numbers in a huge 'if' something like ...

if (array[0]==kernel[0] && array[1]==kernel [1] && .... ) {
  // do erosion
}

1-1-1 Encoding neighbors and the structuring element

It is better to encode the eight values in a number of 8 bits (= 1 byte) and then to compare the two 8-bits numbers in a simple 'if'.

For this purpose, I choose  − because it will be convenient to calculate the rotated kernels  (see below) − to store the neighbors from the top left corner and successively in clockwise order as shown in Fig. 2.

1 2 3
8 * 4
7 6 5

Fig. 2: Numbering of neighbors.

(i) Encoding the structuring element

A structuring element (Fig. 3) is converted as the binary number 10100101 according to Fig. 2 and is transformed in decimal with the parseInt(..) JavaScript function yielding - here - 245.

Fig.3: Formatting and encoding of the structuring element in a decimal number.

(ii) Encoding 8 neighboring pixel values

There is an additional step because we need to convert the 0 and 255 (the only available pixel values in a  binary image) in a series of 0 and 1 before packing them in a 8-bit number.

This is done with a 'if' statement as follows...

  if (pixel == 255) {
    bit=1
  } 
  else {
    bit=0;
  } 

but there is a more concise way like ...

  bit = (pixel ==255) ? 1: 0;

... and you can go further by simplifying ...

  bit = (pixel == 255);

Note: In this case, the condition (pixel == 255) returns TRUE, however, TRUE is mapped as a 1 and can be used as a digit. FALSE is equal to 0.

Now, I can build a string with the collection of 0 and 1 and use the parseInt(...) function as described previously with the structuring element. But, here this is a good opportunity to play with the bitwise operators.

In all the programming languages, there are special operations occurring at bit level. They are the shift ( << or >>) and logical (& or | ) operators.

The shift operator allows to move to the left (<<) or to the right (>>), bit(s) into a byte as shown in Fig. 4.

Fig. 4: Bit shift operator. In this example 'bit << 4', we apply a left shift of 4 positions. The initial bit is shifted to the left yielding 10000₍₂₎ = 16₍₁₀₎. During the shift, the right bits are set to zero (0).

Then, to stack the 8 bits, we have to OR them with the '|' operator

byte = bit7 | bit6 | bit5 | bit4 | bit3 | bit2 | bit1 | bit0

Finally, all the various parts can be merged into a single expression and the code becomes ...

      var v = (ip.getPixel(x-1,y-1)== FOREGRND) << 7 |
              (ip.getPixel(x  ,y-1)== FOREGRND) << 6 |
              (ip.getPixel(x+1,y-1)== FOREGRND) << 5 |
              (ip.getPixel(x+1,y  )== FOREGRND) << 4 |
              (ip.getPixel(x+1,y+1)== FOREGRND) << 3 |
              (ip.getPixel(x  ,y+1)== FOREGRND) << 2 |
              (ip.getPixel(x-1,y+1)== FOREGRND) << 1 |
              (ip.getPixel(x-1,y  )== FOREGRND); 

Note: FOREGRND is a constant corresponding to the foreground pixel value (0 or 255).

1-2- What about the 'Don't Care' pixels ?

Actually, we need a mask for removing the unrequired pixels.

X 1 X
0 1 1
0 0 X

X1X1X000 If you use a mask setting a '0' to remove the 'Don't care' pixels and a '1' for the others. In this example, the mask is equal to 01010111

X1X1X000
01010111 <- mask

Ex:
11011000
01010111
01010000 

1-3- Calculating the rotated structuring elements

 A 45° rotation is simply a circular permutation as shown in Fig. 2 and a 90° rotation two successive permutations.

12345678 → 81234567

Fig. 2: Numbering of neighbors after a rotation of  45°. The rotation corresponds to a circular shift of 1 digit to the right.

2- Script

In the script, the kernel is defined by:

•  its type (S, R4, and R8) 
• its value stored as a string composed of 0, 1, and X characters.

The type indicates if this is a single kernel ('S') or if it is a collection of four  (0°, 90°, 180°, and 270°) or eight (0°, 45°, ..., 315°) rotated kernels.
They are pre-loaded and built in the function loadStructElements(...).
The main loop scans the whole image, get the local neighbors, convert the pixels in a byte for the comparison, and then update the output image if there is an exact match.

+++ JavaScript IJ snippet: hit-or-miss.js +++ +++ End of JavaScript IJ snippet +++

<< Previous: Hit-and-Miss in ImageJ

This is the end of this small series dedicated to Hit-or-Miss operator. Thank you for reading these lines, and feel free to check out the code and share your comments below.

Further reading

Mathematical morphology [Link]
Image Processing [Link]