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.LinkedList;
016import java.util.Queue;
017
018/**
019 * Binary region labeler based on a breadth-first flood filling
020 * algorithm. 
021 * 
022 * @author WB
023 * @version 2016-11-08
024 */
025public class BreadthFirstLabeling 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 BreadthFirstLabeling(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                Queue<Point> Q = new LinkedList<Point>();       //queue contains pixel coordinates
053                Q.add(new Point(u, v));
054                while (!Q.isEmpty()) {
055                        Point p = Q.remove();   // get the next point to process
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                                Q.add(new Point(x+1, y));
062                                Q.add(new Point(x, y+1));
063                                Q.add(new Point(x, y-1));
064                                Q.add(new Point(x-1, y));
065                        }
066                }
067        }
068
069}