Watershed_Algorithm.java

Go to the documentation of this file.

package watershed;

import java.util.ArrayList;

/*
 * Watershed algorithm
 *
 * Copyright (c) 2003 by Christopher Mei (christopher.mei@sophia.inria.fr)
 *
 * This plugin is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 
 * as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this plugin; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

public class Watershed_Algorithm {

        final static int HMIN = 0;

        final static int HMAX = 256;

        int width, height;

        public void run(short[] pixels, int width, int height) {
                this.width = width;
                this.height = height;

                WatershedStructure watershedStructure = new WatershedStructure(pixels,
                                width, height);

                WatershedFIFO queue = new WatershedFIFO();
                int curlab = 0;

                int heightIndex1 = 0;
                int heightIndex2 = 0;

                for (int h = HMIN; h < HMAX; h++) /*
                                                                                         * Geodesic SKIZ of level h-1 inside
                                                                                         * level h
                                                                                         */{

                        for (int pixelIndex = heightIndex1; pixelIndex < watershedStructure
                                        .size(); pixelIndex++) /* mask all pixels at level h */{
                                WatershedPixel p = watershedStructure.get(pixelIndex);

                                if (p.getIntHeight() != h) {
                                        heightIndex1 = pixelIndex;
                                        break;
                                }

                                p.setLabelToMASK();

                                ArrayList neighbours = p.getNeighbours();
                                for (int i = 0; i < neighbours.size(); i++) {
                                        WatershedPixel q = (WatershedPixel) neighbours.get(i);

                                        if (q.getLabel() >= 0) {/*
                                                                                         * Initialise queue with neighbours
                                                                                         * at level h of current basins or
                                                                                         * watersheds
                                                                                         */
                                                p.setDistance(1);
                                                queue.fifo_add(p);
                                                break;
                                        } // end if
                                } // end for
                        } // end for

                        int curdist = 1;
                        queue.fifo_add_FICTITIOUS();

                        while (true) 
                        {
                                WatershedPixel p = queue.fifo_remove();

                                if (p.isFICTITIOUS())
                                        if (queue.fifo_empty()) {
                                                break;
                                        } else {
                                                queue.fifo_add_FICTITIOUS();
                                                curdist++;
                                                p = queue.fifo_remove();
                                        }

                                ArrayList neighbours = p.getNeighbours();
                                for (int i = 0; i < neighbours.size(); i++) /*
                                                                                                                         * Labelling p by
                                                                                                                         * inspecting
                                                                                                                         * neighbours
                                                                                                                         */{
                                        WatershedPixel q = (WatershedPixel) neighbours.get(i);

                                        if ((q.getDistance() <= curdist) && (q.getLabel() >= 0)) {
                                                /* q belongs to an existing basin or to a watershed */

                                                if (q.getLabel() > 0) {
                                                        if (p.isLabelMASK())
                                                                // Removed from original algorithm ||
                                                                // p.isLabelWSHED() )
                                                                p.setLabel(q.getLabel());
                                                        else if (p.getLabel() != q.getLabel())
                                                                p.setLabelToWSHED();
                                                } // end if lab>0
                                                else if (p.isLabelMASK())
                                                        p.setLabelToWSHED();
                                        } else if (q.isLabelMASK() && (q.getDistance() == 0)) {

                                                q.setDistance(curdist + 1);
                                                queue.fifo_add(q);
                                        }
                                } // end for, end processing neighbours

                        } // end while (loop)

                        /* Detect and process new minima at level h */
                        for (int pixelIndex = heightIndex2; pixelIndex < watershedStructure
                                        .size(); pixelIndex++) {
                                WatershedPixel p = watershedStructure.get(pixelIndex);

                                if (p.getIntHeight() != h) {
                                        heightIndex2 = pixelIndex;
                                        break;
                                }

                                p.setDistance(0); /* Reset distance to zero */

                                if (p.isLabelMASK()) { /* the pixel is inside a new minimum */
                                        curlab++;
                                        p.setLabel(curlab);
                                        queue.fifo_add(p);

                                        while (!queue.fifo_empty()) {
                                                WatershedPixel q = queue.fifo_remove();

                                                ArrayList neighbours = q.getNeighbours();

                                                for (int i = 0; i < neighbours.size(); i++) /*
                                                                                                                                         * inspect
                                                                                                                                         * neighbours
                                                                                                                                         * of p2
                                                                                                                                         */{
                                                        WatershedPixel r = (WatershedPixel) neighbours
                                                                        .get(i);

                                                        if (r.isLabelMASK()) {
                                                                r.setLabel(curlab);
                                                                queue.fifo_add(r);
                                                        }
                                                }
                                        } // end while
                                } // end if
                        } // end for
                }
                byte[] newPixels = new byte[pixels.length];

                for (int pixelIndex = 0; pixelIndex < watershedStructure.size(); pixelIndex++) {
                        WatershedPixel p = watershedStructure.get(pixelIndex);

                        if (p.isLabelWSHED() && !p.allNeighboursAreWSHED())
                                newPixels[p.getX() + p.getY() * width] = (byte) 255;
                }
                for (int i = 0; i < pixels.length; i++)
                        pixels[i] = newPixels[i];
        }

}