001/*******************************************************************************
002 * This software is provided as a supplement to the authors' textbooks on digital
003 *  image processing published by Springer-Verlag in various languages and editions.
004 * Permission to use and distribute this software is granted under the BSD 2-Clause 
005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause). 
006 * Copyright (c) 2006-2016 Wilhelm Burger, Mark J. Burge. All rights reserved. 
007 * Visit http://imagingbook.com for additional details.
008 *******************************************************************************/
009
010package imagingbook.pub.regions;
011
012import ij.process.ByteProcessor;
013
014import java.awt.Point;
015import java.util.Deque;
016import java.util.LinkedList;
017
018/**
019 * Binary region labeler based on a depth-first flood filling
020 * algorithm. 
021 * 
022 * @author WB
023 * @version 2016-11-08
024 */
025public class DepthFirstLabeling extends RegionLabeling {
026        
027        /**
028         * Creates a new region labeling.
029         * 
030         * @param ip the binary input image with 0 values for background pixels and values > 0
031         * for foreground pixels.
032         */
033        public DepthFirstLabeling(ByteProcessor ip) {
034                super(ip);
035        }
036        
037        @Override
038        void applyLabeling() {
039                resetLabel();
040                for (int v = 0; v < height; v++) {
041                        for (int u = 0; u < width; u++) {
042                                if (getLabel(u, v) == FOREGROUND) {
043                                        // start a new region
044                                        int label = getNextLabel();
045                                        floodFill(u, v, label);
046                                }
047                        }
048                }
049        }
050
051        private void floodFill(int u, int v, int label) {
052                Deque<Point> S = new LinkedList<Point>();       //stack contains pixel coordinates
053                S.push(new Point(u, v));
054                while (!S.isEmpty()){
055                        Point p = S.pop();
056                        int x = p.x;
057                        int y = p.y;
058                        if ((x >= 0) && (x < width) && (y >= 0) && (y < height)
059                                        && getLabel(x, y) == FOREGROUND) {
060                                setLabel(x, y, label);
061                                S.push(new Point(x + 1, y));
062                                S.push(new Point(x, y + 1));
063                                S.push(new Point(x, y - 1));
064                                S.push(new Point(x - 1, y));
065                        }
066                }
067        }
068
069}