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;xThe
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 methodsisWhite
to check if the pixel has the value 0 andisDark
the inverse ofisWhite
. Thechanged
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.
Ein Gedanke zu „Image Comparison with Java (Part II)“