Image Comparison with Java (Part II)

As described in the first part a more competitive algorithm for image comparison is based on a description of the picture. Here is the ultimate goal describing an image:

• Dimensions of the image
• Hue of the image (Mean of the histogram)
• Tags for the picture (extracted from the context)
• List of shapes in the image

Where as a shape is:

• Form
• Hue of the shape

It is conceivable trivial to process an image to display these characteristics, but it is not trivial to find a description of the shapes that is easily comparable.
The following describes an algorithm to find the contours in a binary image. The basic idea for the algorithm is described in the article on Morphological Image Processing.
This first code fragments sets up the enverionment and iterates through the image:

width = image.getWidth(); // member variable
height = image.getHeight(); // member variable
// Create a Buffered Image.
BufferedImage outImage = new BufferedImage(width,height,BufferedImage.TYPE_BYTE_GRAY);
WritableRaster raster = outImage.getRaster(); 
pixels = new int[nbands*width*height];  // nbands is 1
image.getData().getPixels(0,0,width,height,pixels);
for (int i=0;i<5;i++){
	for (int x=1;x
The changed method does the magic: it decides whether a pixel should be swaped to white. If it is not swapped to white change it to black. The changed method uses two helper methods isWhite to check if the pixel has the value 0 and isDark the inverse of isWhite. The changed implements three of the four rules to decide on the swapping and delegates the forth:
private boolean changed(int c, int x, int y,WritableRaster raster) {
	// do nothing if the pixel is white
	if (isWhite(c)) return false;
	// do nothing if all close neighbors are dark
	int[] offsets = new int[4];
	offsets[0]=(y-1)*width*nbands+x*nbands;
	offsets[1]=y*width*nbands+(x-1)*nbands;
	offsets[2]=y*width*nbands+(x+1)*nbands;
	offsets[3]=(y+1)*width*nbands+x*nbands;
	if(areDark(offsets)) return false;
	// do nothing if only one neighbur is dark
	offsets = new int[8];
	offsets[0]=(y-1)*width*nbands+(x-1)*nbands;
	offsets[1]=(y-1)*width*nbands+x*nbands;
	offsets[2]=(y-1)*width*nbands+(x+1)*nbands;
	offsets[3]=y*width*nbands+(x-1)*nbands;
	offsets[4]=y*width*nbands+(x+1)*nbands;
	offsets[5]=(y+1)*width*nbands+(x-1)*nbands;
	offsets[6]=(y+1)*width*nbands+x*nbands;
	offsets[7]=(y+1)*width*nbands+(x+1)*nbands;
	int counter = 0;
	for (int offset : offsets){
		c = pixels[offset]; 
		if (isDark(c)) counter++;
	}
	if(counter==1) return false;
	// do nothing if the neighbors are unconnected
	counter = countunconnectedNeighbours(x, y);
	if (counter>1) return false;
	
	// turn this pixel white
	raster.setSample(x,y,0,0);
	return true;
}

private int countunconnectedNeighbours(int x, int y) {
	int counter=0;
	int[] offsets = new int[8];
	offsets[0]=(y-1)*width*nbands+(x-1)*nbands;
	offsets[1]=(y-1)*width*nbands+x*nbands;
	offsets[2]=(y-1)*width*nbands+(x+1)*nbands;
	offsets[3]=y*width*nbands+(x+1)*nbands;
	offsets[4]=(y+1)*width*nbands+(x+1)*nbands;
	offsets[5]=(y+1)*width*nbands+x*nbands;
	offsets[6]=(y+1)*width*nbands+(x-1)*nbands;
	offsets[7]=y*width*nbands+(x-1)*nbands;
	int offset1 = offsets[0]; // 1
	int offset2 = offsets[1]; // 2
	int c1 = pixels[offset1]; // 1
	int c2 = pixels[offset2]; // 2
	if (isDark(c1) && !isDark(c2)) counter++;
	int offset3=offsets[2]; // 3
	int c3=pixels[offset3]; // 3
	offset1 = offsets[3];	// 4
	c1 = pixels[offset1+0]; // 4
	if (isDark(c2) && !isDark(c3) && !isDark(c1)) counter++;
	if (isDark(c3) && !isDark(c1)) counter++;
	offset2 = offsets[4]; // 5
	c2 = pixels[offset2]; // 5
	offset3 = offsets[5]; // 6
	c3=pixels[offset3]; // 6
	if (isDark(c1) && !isDark(c2) && !isDark(c3)) counter++;
	if (isDark(c2) && !isDark(c3)) counter++;
	offset1=offsets[6]; // 7
	c1 = pixels[offset1]; // 7
	offset2=offsets[7]; // 8;
	c2 = pixels[offset2]; // 8
	if (isDark(c3) && !isDark(c1) && !isDark(c2)) counter++;
	if (isDark(c1) && !isDark(c2)) counter++;
	offset1=offsets[0]; // 1
	c1 = pixels[offset1]; // 1
	offset3 = offsets[1]; // 2
	c3=pixels[offset3]; // 2
	if (isDark(c2) && !isDark(c1) && !isDark(c3)) counter++;
	return counter;
}

This produces a BufferedImage describing the contours of the original. It would be more simple to use a metric that does not describe the outer bounds of a shape but reduces it to its essentials. This can be achieved with skeletons. More on that in the next part of the article-series.

It should be possible to expand this algorithm to color images by separating the color bands, filter a hue with appropriate high- and low-pass filters and binarize the result. For an RGB image with 256 color channels this would result in 64 steps per band if 4 color channels were to be taken together as one hue: 64*3=192 iterations of the above algorithm for one image.