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 +++

	// Hit-or-Miss transform
	// Jean-Christophe Taveau
	// http://crazybiocomputing.blogspot.com
	var imp = IJ.getImage();
	var ip = imp.getProcessor();
	var w = imp.getWidth();
	var h = imp.getHeight();
	var FOREGRND=0;
	// Load structuring elements
	// 1 2 3
	// 8 X 4
	// 7 6 5
	//
	var corner = [{type: "R4",value: "X1X1X000"}];
	var ends = [{type: "R8",value: "00000001"}];
	var cross4 = [{type: "S",value: "10101010"},{type: "S",value: "01010101"} ];
	var cross3 = [{type: "R4",value: "10100100"},{type: "R4",value: "10101000"},{type: "R4",value: "11000100"} ];
	var elts = loadStructElements(ends);
	out = IJ.createImage("H-M_"+imp.getTitle(), "8-bit White", w, h, 1);
	outp = out.getProcessor();
	// Convolve
	for (var y = 0; y < h; y++) {
	for (var x = 0; x < w; x++) {
	if (ip.get(x,y)== FOREGRND) {
	var pix = ip.get(x,y);
	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);
	var stop = false;
	var i = 0;
	while (!stop) {
	if ( (v & elts[i].mask) == elts[i++].value) {
	outp.set(x,y,FOREGRND);
	stop = true;
	}
	if (i == elts.length)
	stop = true;
	}
	}
	}
	}
	out.show();
	print("End...");
	// F U N C T I O N S
	function loadStructElements(kern) {
	var newarr = new Array();
	for (var i in kern) {
	// Check 'no-care' pixels
	var m=kern[i].value.replace(/[01]/g,"1"); ;
	m=m.replace(/X/g,"0"); ;
	var mask = parseInt(m,2);
	kern[i].value=kern[i].value.replace(/X/g,"0");
	// Rotation
	if (kern[i].type == "R8") {
	var a = parseInt(kern[i].value,2);
	for (var j=0; j < 8; j++) {
	a = (((a&1) << 7 ) | (a>>1));
	mask = (((mask&1) << 7 ) | (mask>>1));
	newarr.push({"value": a, "mask": mask});
	}
	}
	else if (kern[i].type == "R4") {
	var a = parseInt(kern[i].value,2);
	for (var j=0; j < 4; j++) {
	a = (((a&1) << 7 ) | (a>>1));
	a = (((a&1) << 7 ) | (a>>1));
	mask = (((mask&1) << 7 ) | (mask>>1));
	mask = (((mask&1) << 7 ) | (mask>>1));
	newarr.push({"value": a, "mask": mask});
	}
	}
	else {
	newarr.push({"value": parseInt(kern[i].value,2), "mask": mask} );
	}
	}
	return newarr;
	}

view raw hit_or_miss.js hosted with ❤ by GitHub

+++ 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]