But here is my interpretation for Superpixel algorithm in Java programming language. The computational process itself is iterative, but I am using the Cluster objects to make the algorithm slightly easier to understand and follow. Without objects, it could be slightly faster, I have not tried to code that kind of version myself.
Interesting things to try:
- change the proximity modifier 'm' from small to large
- change the cell size 'S' from small to large
Notes
- The algorithm does not ensure superpixel connectivity, thus the result may have orphan pixels from 'wrong' cluster inside of other cluster.
- This algorithm works in RGB color space, some other color space (Lab for example) could give you better end results.
- The distance calculation can be done also using "approximated" distance without square root calculations, for performance reasons.
Image segmentation in Wikipedia: http://en.wikipedia.org/wiki/Image_segmentation
SLIC Superpixels - http://ivrg.epfl.ch/research/superpixels
jSLIC code in the GitHub - https://github.com/Borda/ij-CMP-BIA
Example images
Values used: left S=16, m=130, right S=24, m=130
Values used: left S=16, m=130, right S=24, m=130
Values used: left S=16, m=130, right S=24, m=130
Example usage
Using command line
java popscan.Superpixel "C:\java\flamingo.png" c:\java\sp_flamingo.png 16 130
Source
| package popscan; |
| import java.awt.Color; |
| import java.awt.image.BufferedImage; |
| import java.io.File; |
| import java.util.Arrays; |
| import java.util.Vector; |
| import javax.imageio.ImageIO; |
| /** |
| * @author tejopa, 2014 |
| * @version 1 |
| * http://popscan.blogspot.com |
| */ |
| public class Superpixel { |
| // arrays to store values during process |
| double[] distances; |
| int[] labels; |
| int[] reds; |
| int[] greens; |
| int[] blues; |
| Cluster[] clusters; |
| // in case of instable clusters, max number of loops |
| int maxClusteringLoops = 50; |
| /** |
| * @param args |
| */ |
| public static void main(String[] args) { |
| if (args.length!=4) { |
| System.out.println("Usage: java popscan.Superpixel" |
| + " [source image filename]" |
| + " [destination image filename]" |
| + " [cell width S (1-255)]" |
| + " [proximity modifier m (1-255)"); |
| return; |
| } |
| // parse arguments |
| String src = args[0]; |
| String dst = args[1]; |
| double S = Integer.parseInt(args[2]); |
| double m = Double.parseDouble(args[3]); |
| BufferedImage img = loadImage(src); |
| Superpixel sp = new Superpixel(); |
| BufferedImage dstImage = sp.calculate(img,S,m); |
| // save the resulting image |
| saveImage(dst, dstImage); |
| } |
| public Superpixel() { } |
| public BufferedImage calculate(BufferedImage image, |
| double S, double m) { |
| int w = image.getWidth(); |
| int h = image.getHeight(); |
| BufferedImage result = new BufferedImage(w, h, |
| BufferedImage.TYPE_INT_RGB); |
| long start = System.currentTimeMillis(); |
| // get the image pixels |
| int[] pixels = image.getRGB(0, 0, w, h, null, 0, w); |
| // create and fill lookup tables |
| distances = new double[w*h]; |
| Arrays.fill(distances, Integer.MAX_VALUE); |
| labels = new int[w*h]; |
| Arrays.fill(labels, -1); |
| // split rgb-values to own arrays |
| reds = new int[w*h]; |
| greens = new int[w*h]; |
| blues = new int[w*h]; |
| for (int y=0;y<h;y++) { |
| for (int x=0;x<w;x++) { |
| int pos = x+y*w; |
| int color = pixels[pos]; |
| reds[pos] = color>>16&0x000000FF; |
| greens[pos] = color>> 8&0x000000FF; |
| blues[pos] = color>> 0&0x000000FF; |
| } |
| } |
| // create clusters |
| createClusters(image, S, m); |
| // loop until all clusters are stable! |
| int loops = 0; |
| boolean pixelChangedCluster = true; |
| while (pixelChangedCluster&&loops<maxClusteringLoops) { |
| pixelChangedCluster = false; |
| loops++; |
| // for each cluster center C |
| for (int i=0;i<clusters.length;i++) { |
| Cluster c = clusters[i]; |
| // for each pixel i in 2S region around |
| // cluster center |
| int xs = Math.max((int)(c.avg_x-S),0); |
| int ys = Math.max((int)(c.avg_y-S),0); |
| int xe = Math.min((int)(c.avg_x+S),w); |
| int ye = Math.min((int)(c.avg_y+S),h); |
| for (int y=ys;y<ye;y++) { |
| for (int x=xs;x<xe;x++) { |
| int pos = x+w*y; |
| double D = c.distance(x, y, reds[pos], |
| greens[pos], |
| blues[pos], |
| S, m, w, h); |
| if ((D<distances[pos])&&(labels[pos]!=c.id)) { |
| distances[pos] = D; |
| labels[pos] = c.id; |
| pixelChangedCluster = true; |
| } |
| } // end for x |
| } // end for y |
| } // end for clusters |
| // reset clusters |
| for (int index=0;index<clusters.length;index++) { |
| clusters[index].reset(); |
| } |
| // add every pixel to cluster based on label |
| for (int y=0;y<h;y++) { |
| for (int x=0;x<w;x++) { |
| int pos = x+y*w; |
| clusters[labels[pos]].addPixel(x, y, |
| reds[pos], greens[pos], blues[pos]); |
| } |
| } |
| // calculate centers |
| for (int index=0;index<clusters.length;index++) { |
| clusters[index].calculateCenter(); |
| } |
| } |
| // Create output image with pixel edges |
| for (int y=1;y<h-1;y++) { |
| for (int x=1;x<w-1;x++) { |
| int id1 = labels[x+y*w]; |
| int id2 = labels[(x+1)+y*w]; |
| int id3 = labels[x+(y+1)*w]; |
| if (id1!=id2||id1!=id3) { |
| result.setRGB(x, y, 0x000000); |
| //result.setRGB(x-1, y, 0x000000); |
| //result.setRGB(x, y-1, 0x000000); |
| //result.setRGB(x-1, y-1, 0x000000); |
| } else { |
| result.setRGB(x, y, image.getRGB(x, y)); |
| } |
| } |
| } |
| // mark superpixel (cluster) centers with red pixel |
| for (int i=0;i<clusters.length;i++) { |
| Cluster c = clusters[i]; |
| //result.setRGB((int)c.avg_x, (int)c.avg_y, |
| //Color.red.getRGB()); |
| } |
| long end = System.currentTimeMillis(); |
| System.out.println("Clustered to "+clusters.length |
| + " superpixels in "+loops |
| +" loops in "+(end-start)+" ms."); |
| return result; |
| } |
| /* |
| * Create initial clusters. |
| */ |
| public void createClusters(BufferedImage image, |
| double S, double m) { |
| Vector<Cluster> temp = new Vector<Cluster>(); |
| int w = image.getWidth(); |
| int h = image.getHeight(); |
| boolean even = false; |
| double xstart = 0; |
| int id = 0; |
| for (double y=S/2;y<h;y+=S) { |
| // alternate clusters x-position |
| // to create nice hexagon grid |
| if (even) { |
| xstart = S/2.0; |
| even = false; |
| } else { |
| xstart = S; |
| even = true; |
| } |
| for (double x=xstart;x<w;x+=S) { |
| int pos = (int)(x+y*w); |
| Cluster c = new Cluster(id, |
| reds[pos], greens[pos], blues[pos], |
| (int)x, (int)y, S, m); |
| temp.add(c); |
| id++; |
| } |
| } |
| clusters = new Cluster[temp.size()]; |
| for (int i=0;i<temp.size();i++) { |
| clusters[i] = temp.elementAt(i); |
| } |
| } |
| /** |
| * @param filename |
| * @param image |
| */ |
| public static void saveImage(String filename, |
| BufferedImage image) { |
| File file = new File(filename); |
| try { |
| ImageIO.write(image, "png", file); |
| } catch (Exception e) { |
| System.out.println(e.toString()+" Image '"+filename |
| +"' saving failed."); |
| } |
| } |
| /** |
| * @param filename |
| * @return |
| */ |
| public static BufferedImage loadImage(String filename) { |
| BufferedImage result = null; |
| try { |
| result = ImageIO.read(new File(filename)); |
| } catch (Exception e) { |
| System.out.println(e.toString()+" Image '" |
| +filename+"' not found."); |
| } |
| return result; |
| } |
| class Cluster { |
| int id; |
| double inv = 0; // inv variable for optimization |
| double pixelCount; // pixels in this cluster |
| double avg_red; // average red value |
| double avg_green; // average green value |
| double avg_blue; // average blue value |
| double sum_red; // sum red values |
| double sum_green; // sum green values |
| double sum_blue; // sum blue values |
| double sum_x; // sum x |
| double sum_y; // sum y |
| double avg_x; // average x |
| double avg_y; // average y |
| public Cluster(int id, int in_red, int in_green, |
| int in_blue, int x, int y, |
| double S, double m) { |
| // inverse for distance calculation |
| this.inv = 1.0 / ((S / m) * (S / m)); |
| this.id = id; |
| addPixel(x, y, in_red, in_green, in_blue); |
| // calculate center with initial one pixel |
| calculateCenter(); |
| } |
| public void reset() { |
| avg_red = 0; |
| avg_green = 0; |
| avg_blue = 0; |
| sum_red = 0; |
| sum_green = 0; |
| sum_blue = 0; |
| pixelCount = 0; |
| avg_x = 0; |
| avg_y = 0; |
| sum_x = 0; |
| sum_y = 0; |
| } |
| /* |
| * Add pixel color values to sum of previously added |
| * color values. |
| */ |
| void addPixel(int x, int y, int in_red, |
| int in_green, int in_blue) { |
| sum_x+=x; |
| sum_y+=y; |
| sum_red += in_red; |
| sum_green+= in_green; |
| sum_blue += in_blue; |
| pixelCount++; |
| } |
| public void calculateCenter() { |
| // Optimization: using "inverse" |
| // to change divide to multiply |
| double inv = 1/pixelCount; |
| avg_red = sum_red*inv; |
| avg_green = sum_green*inv; |
| avg_blue = sum_blue*inv; |
| avg_x = sum_x*inv; |
| avg_y = sum_y*inv; |
| } |
| double distance(int x, int y, |
| int red, int green, int blue, |
| double S, double m, int w, int h) { |
| // power of color difference between |
| // given pixel and cluster center |
| double dx_color = (avg_red-red)*(avg_red-red) |
| + (avg_green-green)*(avg_green-green) |
| + (avg_blue-blue)*(avg_blue-blue); |
| // power of spatial difference between |
| // given pixel and cluster center |
| double dx_spatial = (avg_x-x)*(avg_x-x)+(avg_y-y)*(avg_y-y); |
| // Calculate approximate distance D |
| // double D = dx_color+dx_spatial*inv; |
| // Calculate squares to get more accurate results |
| double D = Math.sqrt(dx_color)+Math.sqrt(dx_spatial*inv); |
| return D; |
| } |
| } |
| } |
