Sunday, December 7, 2014

Superpixel algorithm implemented in Java

This Superpixel code has been stored on my hard drive for a year. Too bad, I have only very little time for my recreational image processing programming.

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
  1. The algorithm does not ensure superpixel connectivity, thus the result may have orphan pixels from 'wrong' cluster inside of other cluster.
  2. This algorithm works in RGB color space, some other color space (Lab for example) could give you better end results.
  3. The distance calculation can be done also using "approximated" distance without square root calculations, for performance reasons.
Links
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 Sdouble 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 Sdouble 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 Sdouble 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 Sdouble 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
        } 
    } 
         
} 

Tuesday, June 17, 2014

Problem connecting to Netflix - my solution

Recently I encountered an error when trying to open Netflix app on my Lenovo Android tablet. Netflix used to work flawlessly, but suddenly it stopped working on just one of my devices.

When trying to login, an error message appeared. The message was "There is a problem connecting to Netflix. Please try again later. If the problem persists, check that your device has the correct date and time and restart the Netflix application."

Actually, as the device is in Finnish locale, the message was "Netflix-yhteyden luomisessa oli ongelma. Yritä myöhemmin uudelleen. Jos ongelma ei poistu, tarkista että laitteessasi on oikea päivämäärä ja aika ja käynnistä Netflix-sovellus uudelleen."

I tried to reset my router, set the time and date for my router and devices etc, nothing helped. I removed Netflix app and reinstalled it. Everything else was working perfectly (net, games, etc) but still I was not able to connect to Netflix. And my kids were getting angry.

Finally I tried to check the DNS settings on my tablet. They pointed to my router, where I have Google's servers configured. Well, I thought, why not set the same IPs to the tablet as well.

So, I set up the Google name server IPs as DNS servers... and Netflix started to work again.

Steps to set up the DNS in Android 4.x devices:
1. Select "Settings"
2. Select "Wi-Fi"
3. Long tap your wifi network item - a pop up chooser will appear
4. Select "Modify network config"
5. Select "Show advanced options" - new options will appear
6. Select "IP settings" - select "Static" from drop down menu
7. Set "DNS1" to "8.8.8.8" (write down the original IP, in case you need it later)
8. Set "DNS2" to "8.8.4.4" (write down the original IP, in case you need it later)
9. Select "Save"
10. Start watching Netflix ;)



Sunday, April 20, 2014

Watershed image segmentation algorithm with Java

I am very interested in image segmentation, that is why the watershed segmentation caught my attention this time. People are using the watershed algorithm at least in the medical imaging applications, and the F. Meyer's algorithm was mentioned to be "one of the most common" one [1]. It also looked like it is quite easy to implement.

My favorite method for studying and understanding algorithms is to actually implement the algorithm. During the implementation, you really have to understand what is happening in each step. Also the produced images (in image algorithms) during the development process are helpful. It is fun to analyze the errors and what causes the artifacts in the image. So, the result for my studies is here: the watershed image segmentation algorithm implemented with Java.

Watershed algorithm explained (italics are from Wikipedia):


1. "A set of markers, pixels where the flooding shall start, are chosen. Each is given a different label."
  • Find all the minimum points from the image. This means that you need to loop through pixels and find the darkest pixel which has not been already selected and which is not close to already selected minimum pixel. You can find as many minimums you like or only selected count of minimums. These minimums are the lowest points of the "basins" which will be flooded.
  • The label can be for example the index numbering or color values from a known premade palette.

2. "The neighboring pixels of each marked area are inserted into a priority queue with a priority level corresponding to the gray level of the pixel."
  • For each found minimum point, add the surrounding pixels to the priority queue. Set the initial labels to the label table (result image). Sort the priority queue from dark to light pixels. Now you can start the flooding.

3. "The pixel with the highest priority level is extracted from the priority queue. If the neighbors of the extracted pixel that have already been labeled all have the same label, then the pixel is labeled with their label. All non-marked neighbors that are not yet in the priority queue are put into the priority queue." 
  • Take out the first pixel (the darkest one) from the priority queue. Check the neighboring pixels for that pixel. If all the labeled pixels are having the same label, label the current pixel with the same label; the current pixel is "inside" of the basin. Remember, there has to be at least one labeled pixel; the one that was previously next to the current pixel. 
  • If there are at least two pixels with different label, it means that we have found a boundary between two different flood basins. We can mark this pixel then as an "edge" pixel. 
  • Finally, add all those neighboring pixels that do not have label to the priority queue.

4. "Redo step 3 until the priority queue is empty."
  • Loop until there are no pixels left in the priority queue. When the priority queue is empty, all the pixels from the image are processed.

 

Sample images

 

Image 1. This is the sample image I have been using for testing. I created it myself with GIMP.

Image 2. This is the result after executing the Watershed algorithm to the sample image. Red squares are the found minimums and the white borders are the basins edges.

Image 3. Here are the sample image and the result image combined in a same image. The boundaries have been colored to green.

Notes:

  • In this implementation, the minimums are found by "sweeping" the pixels from top-left to bottom-right. This way the found minimum is always the "first" one with the lowest value. That is why the minimum centers (the red squares) are not in the exact center of the darkest area. 
  • If you rotate the source image, the result will be different, that is because the minimum locations are changing (see the note above) and this discussion [2].
  • After segmentation, you probably need the remove the "background" pixels. What you need to do might change per application. See more examples for fine tuning the Watershed algorithm from http://cmm.ensmp.fr/~beucher/wtshed.html [3].

 

The Java source


Implementation notes:
  • To find more speed in the pixel sorting, I implemented a crude SortedVector, which uses insertion sort like algorithm to keep the inserted pixels (FloodPoints) in sorted order.
  • I am disabling the pixels from a rectangle shaped area around the minimum. A circle shape should work better in some cases.
  • The source contains commented code for saving the image in different steps of the process. Just uncomment the lines to get the images saved on your drive.
  • The source contains commented code for real time view of the process. Just uncomment the parts where the JFrame is accessed to see the final image being built. You should try that, it looks nice! :)
  • You can run the code in 4-connected pixels or 8-connected pixels mode. The results are slightly different. You should try them both.
Please let me know if you spot errors or have any other comments. Thanks!

Usage


java Watershed [source file] [result file] [number of segments, 1-256] [minimum window width, 8-256] [connected pixels, 4|8] 

For example: 
java Watershed sample_image.png result.png 22 60 8

SortedVector.java


import java.util.Vector
public class SortedVector { 
    Vector<Comparable<Object>> data; 
    public SortedVector() {  
        data = new Vector<Comparable<Object>>()
    } 
    public void add(Object o) { 
        if (instanceof Comparable) { 
            insert((Comparable<Object>)o)
        } else { 
            throw new IllegalArgumentException("Object " + 
                    "must implement Comparable interface.")
        } 
    } 
     
    private void insert(Comparable<Object> o) { 
        if (data.size()==0) { 
            data.add(o)
        } 
        int middle = 0; 
        int left  = 0; 
        int right = data.size()-1; 
        while (left < right) { 
            middle  = (left+right)/2; 
            if (data.elementAt(middle).compareTo(o)==-1) { 
                left = middle + 1; 
            } else if (data.elementAt(middle).compareTo(o)==1) { 
                right = middle - 1; 
            } else { 
                // position found, insert here 
                // break out while 
                left = data.size()+1; 
            } 
        } 
        data.add(middle, o)
    } 
    public int size() { 
        return data.size()
    } 
     
    public Object elementAt(int index) { 
        return data.elementAt(index)
    } 
    public Object remove(int position) { 
        return data.remove(position)
    } 
} 

Watershed.java


import java.awt.Color
import java.awt.Graphics
import java.awt.image.BufferedImage
import java.io.File
import java.util.Arrays
import java.util.Vector
import javax.imageio.ImageIO
import javax.swing.JFrame; 
/** 
 * @author tejopa / http://popscan.blogspot.com 
 * @date 2014-04-20 
 */ 
public class Watershed { 
    //JFrame frame; 
    int g_w; 
    int g_h; 
     
    public static void main(String[] args) { 
        if (args.length!=5) { 
            System.out.println("Usage: java popscan.Watershed
                            + " [source image filename]
                            + " [destination image filename]
                            + " [flood point count (1-256)]
                            + " [minimums window width (8-256)]
                            + " [connected pixels (4 or 8)]
                            )
            return
        } 
        String src = args[0]
        String dst = args[1]
        int floodPoints = Integer.parseInt(args[2])
        int windowWidth = Integer.parseInt(args[3])
        int connectedPixels = Integer.parseInt(args[4])
         
        Watershed watershed = new Watershed()
         
        long start = System.currentTimeMillis()
        BufferedImage dstImage = watershed.calculate(loadImage(src)
                floodPoints,windowWidth,connectedPixels)
        long end = System.currentTimeMillis()
         
        // save the resulting image 
        long totalms = (end-start)
        System.out.println("Took: "+totalms+" milliseconds")
        saveImage(dst, dstImage)
    } 
     
    private BufferedImage calculate(BufferedImage image,  
            int floodPoints, int windowWidth,  
            int connectedPixels) { 
        /* 
        // frame for real time view for the process 
        frame = new JFrame(); 
        frame.setSize(image.getWidth(),image.getHeight()); 
        frame.setVisible(true); 
        */ 
         
        g_w = image.getWidth()
        g_h = image.getHeight()
        // height map is the gray color image 
        int[] map = image.getRGB(0, 0, g_w, g_h, null, 0, g_w)
        // LUT is the lookup table for the processed pixels 
        int[] lut = new int[g_w*g_h]
        // fill LUT with ones 
        Arrays.fill(lut, 1)
        Vector<FloodPoint> minimums = new Vector<FloodPoint>()
        // loop all the pixels of the image until 
        // a) all the required minimums have been found 
        // OR 
        // b) there are no more unprocessed pixels left  
        int foundMinimums = 0; 
        while (foundMinimums<floodPoints) { 
            int minimumValue = 256; 
            int minimumPosition = -1; 
            for (int i=0;i<lut.length;i++) { 
                if ((lut[i]==1)&&(map[i]<minimumValue)) { 
                    minimumPosition = i; 
                    minimumValue = map[i]
                } 
            } 
            // check if minimum was found 
            if (minimumPosition!=-1) { 
                // add minimum to found minimum vector 
                int x = minimumPosition%g_w; 
                int y = minimumPosition/g_w;  
                int grey = map[x+g_w*y]&0xff; 
                int label = foundMinimums; 
                minimums.add(new FloodPoint(x,y, 
                        label,grey))
                // remove pixels around so that the next minimum 
                // must be at least windowWidth/2 distance from 
                // this minimum (using square, could be circle...) 
                int half = windowWidth/2; 
                fill(x-half,y-half,x+half,y+half,lut,0)
                lut[minimumPosition] = 0; 
                foundMinimums++; 
            } else { 
                // stop while loop 
                System.out.println("Out of pixels. Found " 
                                    + minimums.size() 
                                    + " minimums of requested " 
                                    + floodPoints+".")
                break
            } 
        } 
        /* 
        // create image with minimums only 
        for (int i=0;i<minimums.size();i++) { 
            FloodPoint p = minimums.elementAt(i); 
            Graphics g = image.getGraphics(); 
            g.setColor(Color.red); 
            g.drawRect(p.x, p.y, 2, 2); 
        } 
        saveImage("minimums.png", image); 
        */ 
         
        // start flooding from minimums 
        lut = flood(map,minimums,connectedPixels)
         
        // return flooded image 
        image.setRGB(0, 0, g_w, g_h, lut, 0, g_w)
        /*// create image with boundaries also 
        for (int i=0;i<minimums.size();i++) { 
            FloodPoint p = minimums.elementAt(i)
            Graphics g = image.getGraphics()
            g.setColor(Color.red)
            g.drawRect(p.x, p.y, 2, 2)
        } 
        saveImage("minimums_and_boundaries.png", image)
        */ 
        return image; 
    } 
    private int[] flood(int[] map, Vector<FloodPoint> minimums,  
            int connectedPixels) { 
        SortedVector queue = new SortedVector()
        //BufferedImage result = new BufferedImage(g_w, g_h, 
        //        BufferedImage.TYPE_INT_RGB); 
        int[] lut = new int[g_w*g_h]
        int[] inqueue = new int[g_w*g_h]
        // not processed = -1, processed >= 0 
        Arrays.fill(lut, -1)
        Arrays.fill(inqueue, 0)
        // Initialize queue with each found minimum 
        for (int i=0;i<minimums.size();i++) { 
            FloodPoint p = minimums.elementAt(i)
            int label = p.label; 
            // insert starting pixels around minimums 
            addPoint(queue, inqueue, map, p.x,   p.y-1, label)
            addPoint(queue, inqueue, map, p.x+1, p.y,   label)
            addPoint(queue, inqueue, map, p.x,   p.y+1, label)
            addPoint(queue, inqueue, map, p.x-1, p.y,   label)
            if (connectedPixels==8) { 
                addPoint(queue, inqueue, map, p.x-1, p.y-1, label)
                addPoint(queue, inqueue, map, p.x+1, p.y-1, label)
                addPoint(queue, inqueue, map, p.x+1, p.y+1, label)
                addPoint(queue, inqueue, map, p.x-1, p.y+1, label)
            } 
            int pos = p.x+p.y*g_w; 
            lut[pos] = label; 
            inqueue[pos] = 1; 
        } 
         
        // start flooding 
        while (queue.size()>0) { 
            // find minimum 
            FloodPoint extracted = null; 
            // remove the minimum from the queue 
            extracted = (FloodPoint)queue.remove(0)
            int x = extracted.x; 
            int y = extracted.y; 
            int label = extracted.label; 
            // check pixels around extracted pixel 
            int[] labels = new int[connectedPixels]
            labels[0] = getLabel(lut,x,y-1)
            labels[1] = getLabel(lut,x+1,y)
            labels[2] = getLabel(lut,x,y+1)
            labels[3] = getLabel(lut,x-1,y)
            if (connectedPixels==8) { 
                labels[4] = getLabel(lut,x-1,y-1)
                labels[5] = getLabel(lut,x+1,y-1)
                labels[6] = getLabel(lut,x+1,y+1)
                labels[7] = getLabel(lut,x-1,y+1)
            } 
            boolean onEdge = isEdge(labels,extracted)
            if (onEdge) { 
                // leave edges without label 
            } else { 
                // set pixel with label 
                lut[x+g_w*y] = extracted.label; 
            } 
            if (!inQueue(inqueue,x,y-1)) { 
                addPoint(queue, inqueue, map, x, y-1, label)
            } 
            if (!inQueue(inqueue,x+1,y)) { 
                addPoint(queue, inqueue, map, x+1, y, label)
            } 
            if (!inQueue(inqueue,x,y+1)) { 
                addPoint(queue, inqueue, map, x, y+1, label)
            } 
            if (!inQueue(inqueue,x-1,y)) { 
                addPoint(queue, inqueue, map, x-1, y, label)
            } 
            if (connectedPixels==8) { 
                if (!inQueue(inqueue,x-1,y-1)) { 
                    addPoint(queue, inqueue, map, x-1, y-1, label)
                } 
                if (!inQueue(inqueue,x+1,y-1)) { 
                    addPoint(queue, inqueue, map, x+1, y-1, label)
                } 
                if (!inQueue(inqueue,x+1,y+1)) { 
                    addPoint(queue, inqueue, map, x+1, y+1, label)
                } 
                if (!inQueue(inqueue,x-1,y+1)) { 
                    addPoint(queue, inqueue, map, x-1, y+1, label)
                } 
            } 
            // draw the current pixel set to frame, WARNING: slow... 
            //result.setRGB(0, 0, g_w, g_h, lut, 0, g_w); 
            //frame.getGraphics().drawImage(result,  
            //     0, 0, g_w, g_h, null); 
        } 
        return lut; 
    } 
     
    private boolean inQueue(int[] inqueue, int x, int y) { 
        if (x<0||x>=g_w||y<0||y>=g_h) { 
            return false; 
        } 
        if (inqueue[x+g_w*y] == 1) { 
            return true; 
        } 
        return false; 
    } 
    private boolean isEdge(int[] labels, FloodPoint extracted) { 
        for (int i=0;i<labels.length;i++) { 
            if (labels[i]!=extracted.label&&labels[i]!=-1) { 
                return true; 
            } 
        } 
        return false; 
    } 
    private int getLabel(int[] lut, int x, int y) { 
        if (x<0||x>=g_w||y<0||y>=g_h) { 
            return -2; 
        } 
        return lut[x+g_w*y]
    } 
     
    private void addPoint(SortedVector queue,  
            int[] inqueue, int[] map,  
            int x, int y, int label) { 
        if (x<0||x>=g_w||y<0||y>=g_h) { 
            return
        } 
        queue.add(new FloodPoint(x,y,label,map[x+g_w*y]&0xff))
        inqueue[x+g_w*y] = 1; 
    } 
     
    private void fill(int x1, int y1, int x2, int y2,  
            int[] array, int value) { 
        for (int y=y1;y<y2;y++) { 
            for (int x=x1;x<x2;x++) { 
                // clip to boundaries 
                if (y>=0&&x>=0&&y<g_h&&x<g_w) { 
                    array[x+g_w*y] = value; 
                } 
            } 
        } 
    } 
     
    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.")
        } 
    } 
    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 FloodPoint implements Comparable<Object{ 
        int x; 
        int y; 
        int label; 
        int grey; 
         
        public FloodPoint(int x, int y, int label, int grey) { 
            this.x = x; 
            this.y = y; 
            this.label = label; 
            this.grey = grey; 
        } 
        @Override 
        public int compareTo(Object o) { 
            FloodPoint other = (FloodPoint)o; 
            if (this.grey < other.grey ) { 
                return -1; 
            } else if (this.grey > other.grey ) { 
                return 1; 
            } 
            return 0; 
        } 
    } 
     
} 

Sources:
[1] http://en.wikipedia.org/wiki/Watershed_%28image_processing%29
[2] http://imagej.1557.x6.nabble.com/Watershed-Algorithm-source-bug-td3685192.html
[3] http://cmm.ensmp.fr/~beucher/wtshed.html