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-2023 Wilhelm Burger, Mark J. Burge. All rights reserved.
007 * Visit https://imagingbook.com for additional details.
008 ******************************************************************************/
009
010package imagingbook.common.regions;
011
012import ij.process.ByteProcessor;
013import imagingbook.common.geometry.basic.NeighborhoodType2D;
014import imagingbook.common.geometry.basic.Pnt2d.PntInt;
015
016import java.util.Deque;
017import java.util.LinkedList;
018
019/**
020 * <p>
021 * Binary region segmentation based on a breadth-first flood filling algorithm using a queue. See Sec. 8.1.1 (Alg. 8.2)
022 * of [1] for additional details.
023 * </p>
024 * <p>
025 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing &ndash; An Algorithmic Introduction</em>, 3rd ed, Springer
026 * (2022).
027 * </p>
028 *
029 * @author WB
030 * @version 2022/09/28 revised
031 */
032public class BreadthFirstSegmentation extends BinaryRegionSegmentation {
033
034        /**
035         * Constructor. Creates a new region segmentation from the specified image, which is not modified. The input image
036         * is considered binary, with 0 values for background pixels and values &ne; 0 for foreground pixels. The
037         * 4-neighborhood is used by default ({@link BinaryRegionSegmentation#DefaultNeighborhoodT}).
038         *
039         * @param ip the binary input image to be segmented
040         */
041        public BreadthFirstSegmentation(ByteProcessor ip) {
042                this(ip, DefaultNeighborhoodT);
043        }
044
045        /**
046         * Constructor. Creates a new region segmentation from the specified image and neighborhood type (4- or
047         * 8-neighborhood). The input image is considered binary, with 0 values for background pixels and values &ne; 0 for
048         * foreground pixels.
049         *
050         * @param ip the binary input image to be segmented
051         * @param nh the neighborhood type (4- or 8-neighborhood)
052         */
053        public BreadthFirstSegmentation(ByteProcessor ip, NeighborhoodType2D nh) {
054                super(ip, nh);
055        }
056        
057        @Override
058        boolean applySegmentation(ByteProcessor ip) {
059                for (int v = 0; v < height; v++) {
060                        for (int u = 0; u < width; u++) {
061                                if (getLabel(u, v) == Foreground) {
062                                        // start a new region
063                                        int label = getNextLabel();
064                                        //IJ.log(String.format("assigning label %d at (%d,%d), maxLabel=%d", label, u, v, maxLabel));
065                                        floodFill(u, v, label);
066                                }
067                        }
068                }
069                return true;
070        }
071
072        private void floodFill(int u, int v, int label) {
073                Deque<PntInt> Q = new LinkedList<>();   //queue contains pixel coordinates
074                Q.addLast(PntInt.from(u, v));
075                while (!Q.isEmpty()) {
076                        PntInt p = Q.removeFirst();     // get the next point to process
077                        int x = p.x;
078                        int y = p.y;
079                        if ((x >= 0) && (x < width) && (y >= 0) && (y < height) && getLabel(x, y) == Foreground) {
080                                setLabel(x, y, label);
081                                Q.addLast(PntInt.from(x + 1, y));
082                                Q.addLast(PntInt.from(x, y + 1));
083                                Q.addLast(PntInt.from(x, y - 1));
084                                Q.addLast(PntInt.from(x - 1, y));
085                                if (NT == NeighborhoodType2D.N8) {
086                                        Q.addLast(PntInt.from(x + 1, y + 1));
087                                        Q.addLast(PntInt.from(x - 1, y + 1));
088                                        Q.addLast(PntInt.from(x + 1, y - 1));
089                                        Q.addLast(PntInt.from(x - 1, y - 1));
090                                }
091                        }
092                }
093        }
094
095}