{"id":623,"date":"2009-11-22T10:37:22","date_gmt":"2009-11-22T09:37:22","guid":{"rendered":"http:\/\/sahits.ch\/blog\/?p=623"},"modified":"2009-11-22T12:28:12","modified_gmt":"2009-11-22T11:28:12","slug":"image-comparison-with-java-part-ii","status":"publish","type":"post","link":"http:\/\/sahits.ch\/blog\/blog\/2009\/11\/22\/image-comparison-with-java-part-ii\/","title":{"rendered":"Image Comparison with Java (Part II)"},"content":{"rendered":"<p>As described in the <a href=\"http:\/\/sahits.ch\/blog\/?p=587\">first part<\/a> a more competitive algorithm for image comparison is based on a description of the picture. Here is the ultimate goal describing an image:<\/p>\n<ul>\n<li>Dimensions of the image<\/li>\n<li>Hue of the image (Mean of the histogram)<\/li>\n<li>Tags for the picture (extracted from the context)<\/li>\n<li>List of shapes in the image<\/li>\n<\/ul>\n<p>Where as a shape is:<\/p>\n<ul>\n<li>Form<\/li>\n<li>Hue of the shape<\/li>\n<\/ul>\n<p>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.<br \/>\nThe following describes an algorithm to find the contours in a binary image. The basic idea for the algorithm is described in the <a href=\"http:\/\/www.dspguide.com\/ch25\/4.html\">article on Morphological Image Processing<\/a>.<!--more--><br \/>\nThis first code fragments sets up the enverionment and iterates through the image:<\/p>\n<pre>\r\nwidth = image.getWidth(); \/\/ member variable\r\nheight = image.getHeight(); \/\/ member variable\r\n\/\/ Create a Buffered Image.\r\nBufferedImage outImage = new BufferedImage(width,height,BufferedImage.TYPE_BYTE_GRAY);\r\nWritableRaster raster = outImage.getRaster(); \r\npixels = new int[nbands*width*height];  \/\/ nbands is 1\r\nimage.getData().getPixels(0,0,width,height,pixels);\r\nfor (int i=0;i&lt;5;i++){\r\n\tfor (int x=1;x<width -1;x++)\r\n\t\tfor (int y=1;y<height-1;y++){\r\n\t\t\tint offset = y*width*nbands+x*nbands; \r\n\t\t\tint c = pixels[offset]; \r\n\t\t\tif (!changed(c, x, y, raster)){\r\n\t\t\t\t\/\/ Change to black\r\n\t\t\t\traster.setSample(x, y, 0, 255);\r\n\t\t\t}\r\n\t\t}\r\n}\t\t\r\n<\/pre>\n<p>The <code>changed<\/code> 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 <code>isWhite<\/code> to check if the pixel has the value 0 and <code>isDark<\/code> the inverse of <code>isWhite<\/code>. The <code>changed<\/code> implements three of the four rules to decide on the swapping and delegates the forth:<\/p>\n<pre>\r\nprivate boolean changed(int c, int x, int y,WritableRaster raster) {\r\n\t\/\/ do nothing if the pixel is white\r\n\tif (isWhite(c)) return false;\r\n\t\/\/ do nothing if all close neighbors are dark\r\n\tint[] offsets = new int[4];\r\n\toffsets[0]=(y-1)*width*nbands+x*nbands;\r\n\toffsets[1]=y*width*nbands+(x-1)*nbands;\r\n\toffsets[2]=y*width*nbands+(x+1)*nbands;\r\n\toffsets[3]=(y+1)*width*nbands+x*nbands;\r\n\tif(areDark(offsets)) return false;\r\n\t\/\/ do nothing if only one neighbur is dark\r\n\toffsets = new int[8];\r\n\toffsets[0]=(y-1)*width*nbands+(x-1)*nbands;\r\n\toffsets[1]=(y-1)*width*nbands+x*nbands;\r\n\toffsets[2]=(y-1)*width*nbands+(x+1)*nbands;\r\n\toffsets[3]=y*width*nbands+(x-1)*nbands;\r\n\toffsets[4]=y*width*nbands+(x+1)*nbands;\r\n\toffsets[5]=(y+1)*width*nbands+(x-1)*nbands;\r\n\toffsets[6]=(y+1)*width*nbands+x*nbands;\r\n\toffsets[7]=(y+1)*width*nbands+(x+1)*nbands;\r\n\tint counter = 0;\r\n\tfor (int offset : offsets){\r\n\t\tc = pixels[offset]; \r\n\t\tif (isDark(c)) counter++;\r\n\t}\r\n\tif(counter==1) return false;\r\n\t\/\/ do nothing if the neighbors are unconnected\r\n\tcounter = countunconnectedNeighbours(x, y);\r\n\tif (counter>1) return false;\r\n\t\r\n\t\/\/ turn this pixel white\r\n\traster.setSample(x,y,0,0);\r\n\treturn true;\r\n}\r\n<\/pre>\n<pre>\r\nprivate int countunconnectedNeighbours(int x, int y) {\r\n\tint counter=0;\r\n\tint[] offsets = new int[8];\r\n\toffsets[0]=(y-1)*width*nbands+(x-1)*nbands;\r\n\toffsets[1]=(y-1)*width*nbands+x*nbands;\r\n\toffsets[2]=(y-1)*width*nbands+(x+1)*nbands;\r\n\toffsets[3]=y*width*nbands+(x+1)*nbands;\r\n\toffsets[4]=(y+1)*width*nbands+(x+1)*nbands;\r\n\toffsets[5]=(y+1)*width*nbands+x*nbands;\r\n\toffsets[6]=(y+1)*width*nbands+(x-1)*nbands;\r\n\toffsets[7]=y*width*nbands+(x-1)*nbands;\r\n\tint offset1 = offsets[0]; \/\/ 1\r\n\tint offset2 = offsets[1]; \/\/ 2\r\n\tint c1 = pixels[offset1]; \/\/ 1\r\n\tint c2 = pixels[offset2]; \/\/ 2\r\n\tif (isDark(c1) && !isDark(c2)) counter++;\r\n\tint offset3=offsets[2]; \/\/ 3\r\n\tint c3=pixels[offset3]; \/\/ 3\r\n\toffset1 = offsets[3];\t\/\/ 4\r\n\tc1 = pixels[offset1+0]; \/\/ 4\r\n\tif (isDark(c2) && !isDark(c3) && !isDark(c1)) counter++;\r\n\tif (isDark(c3) && !isDark(c1)) counter++;\r\n\toffset2 = offsets[4]; \/\/ 5\r\n\tc2 = pixels[offset2]; \/\/ 5\r\n\toffset3 = offsets[5]; \/\/ 6\r\n\tc3=pixels[offset3]; \/\/ 6\r\n\tif (isDark(c1) && !isDark(c2) && !isDark(c3)) counter++;\r\n\tif (isDark(c2) && !isDark(c3)) counter++;\r\n\toffset1=offsets[6]; \/\/ 7\r\n\tc1 = pixels[offset1]; \/\/ 7\r\n\toffset2=offsets[7]; \/\/ 8;\r\n\tc2 = pixels[offset2]; \/\/ 8\r\n\tif (isDark(c3) && !isDark(c1) && !isDark(c2)) counter++;\r\n\tif (isDark(c1) && !isDark(c2)) counter++;\r\n\toffset1=offsets[0]; \/\/ 1\r\n\tc1 = pixels[offset1]; \/\/ 1\r\n\toffset3 = offsets[1]; \/\/ 2\r\n\tc3=pixels[offset3]; \/\/ 2\r\n\tif (isDark(c2) && !isDark(c1) && !isDark(c3)) counter++;\r\n\treturn counter;\r\n}\r\n<\/pre>\n<p>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.<br \/>\nIt 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.<\/p>\n<p><\/width><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 &hellip; <a href=\"http:\/\/sahits.ch\/blog\/blog\/2009\/11\/22\/image-comparison-with-java-part-ii\/\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eImage Comparison with Java (Part II)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,6],"tags":[134,135,63,132,301,300,133],"class_list":["post-623","post","type-post","status-publish","format-standard","hentry","category-java","category-programmieren","tag-compare","tag-contour","tag-image","tag-jai","tag-java","tag-programmieren","tag-skeleton"],"_links":{"self":[{"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/posts\/623","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/comments?post=623"}],"version-history":[{"count":6,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/posts\/623\/revisions"}],"predecessor-version":[{"id":627,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/posts\/623\/revisions\/627"}],"wp:attachment":[{"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/media?parent=623"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/categories?post=623"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/tags?post=623"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}