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;
014
015/**
016 * <p>
017 * Binary region segmentation based on a recursive (depth-first) flood filling algorithm. See Sec. 8.1.1 (Alg. 8.2) of
018 * [1] for additional details. Note that this implementation may easily run out of stack space and should be used for
019 * demonstration purposes only.
020 * </p>
021 * <p>
022 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing &ndash; An Algorithmic Introduction</em>, 3rd ed, Springer
023 * (2022).
024 * </p>
025 *
026 * @author WB
027 * @version 2022/09/28 revised
028 */
029public class RecursiveSegmentation extends BinaryRegionSegmentation {
030
031        /**
032         * Constructor. Creates a new region segmentation from the specified image, which is not modified. The input image
033         * is considered binary, with 0 values for background pixels and values &ne; 0 for foreground pixels. The
034         * 4-neighborhood is used by default ({@link BinaryRegionSegmentation#DefaultNeighborhoodT}).
035         *
036         * @param ip the binary input image to be segmented
037         */
038        public RecursiveSegmentation(ByteProcessor ip) {
039                this(ip, DefaultNeighborhoodT);
040        }
041
042        /**
043         * Constructor. Creates a new region segmentation from the specified image and neighborhood type (4- or
044         * 8-neighborhood). The input image is considered binary, with 0 values for background pixels and values &ne; 0 for
045         * foreground pixels.
046         *
047         * @param ip the binary input image to be segmented
048         * @param nh the neighborhood type (4- or 8-neighborhood)
049         */
050        public RecursiveSegmentation(ByteProcessor ip, NeighborhoodType2D nh) {
051                super(ip, nh);
052        }
053        
054        @Override
055        boolean applySegmentation(ByteProcessor ip) {
056                try{
057                        for (int v = 0; v < height; v++) {
058                                for (int u = 0; u < width; u++) {
059                                        if (getLabel(u, v) == Foreground) {     // = unlabeled foreground
060                                                // start a new region
061                                                int label = getNextLabel();
062                                                floodFill(u, v, label);
063                                        }
064                                }
065                        }
066                } catch(StackOverflowError e) {
067                        return false;
068                }
069                return true;
070        }
071
072        private void floodFill(int x, int y, int label) {
073                if ((x >= 0) && (x < width) && (y >= 0) && (y < height) && getLabel(x, y) == Foreground) {
074                        setLabel(x, y, label);
075                        floodFill(x + 1, y, label);
076                        floodFill(x, y + 1, label);
077                        floodFill(x, y - 1, label);
078                        floodFill(x - 1, y, label);
079                        if (NT == NeighborhoodType2D.N8) {
080                                floodFill(x + 1, y + 1, label);
081                                floodFill(x - 1, y + 1, label);
082                                floodFill(x + 1, y - 1, label);
083                                floodFill(x - 1, y - 1, label);
084                        }
085                }
086        }
087
088}