Source code

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
015import java.util.Arrays;
016import java.util.Collections;
017import java.util.LinkedHashMap;
018import java.util.List;
019import java.util.Map;
020
021import static imagingbook.common.geometry.basic.NeighborhoodType2D.N4;
022
023/**
024 * <p>
025 * Performs region segmentation on a given binary image. See Ch. 8 of [1] for additional details. This class is
026 * abstract, since the implementation depends on the concrete region segmentation algorithm being used. Concrete
027 * implementations (subclasses of this class) are {@link BreadthFirstSegmentation}, {@link DepthFirstSegmentation},
028 * {@link RecursiveSegmentation}, {@link SequentialSegmentation}, {@link RegionContourSegmentation}. Most of the work is
029 * done by the constructor(s). If the segmentation has failed for some reason {@link #getRegions()} returns
030 * {@code null}.
031 * </p>
032 * <p>
033 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing &ndash; An Algorithmic Introduction</em>, 3rd ed, Springer
034 * (2022).
035 * </p>
036 *
037 * @author WB
038 * @version 2021/12/22
039 * @see BreadthFirstSegmentation
040 * @see DepthFirstSegmentation
041 * @see SequentialSegmentation
042 * @see RecursiveSegmentation
043 * @see RegionContourSegmentation
044 */
045public abstract class BinaryRegionSegmentation {
046        
047        /** The default neighborhood type. */
048        public static final NeighborhoodType2D DefaultNeighborhoodT = N4;
049        
050        static final int Background = 0;
051        static final int Foreground = 1;
052        
053//      final ImageProcessor ip;
054        final int width;
055        final int height;       
056        final NeighborhoodType2D NT;
057        
058        final int[][] labelArray;
059        // label values in labelArray can be:
060        //  0 ... unlabeled
061        // -1 ... previously visited background pixel
062        // >0 ... valid label
063        
064        private final Map<Integer, SegmentationBackedRegion> regions;
065        private final boolean isSegmented;
066        
067        private final int minLabel = 2;
068        private int currentLabel = -1;  // the maximum label assigned sofar
069        private int maxLabel = -1;              // the maximum label assigned total
070        
071        // -------------------------------------------------------------------------
072        
073        BinaryRegionSegmentation(ByteProcessor ip, NeighborhoodType2D nh) {
074//              this.ip = ip;
075                this.NT = nh;
076                this.width  = ip.getWidth();
077                this.height = ip.getHeight();
078                this.labelArray = makeLabelArray(ip);
079                this.isSegmented = applySegmentation(ip);
080                this.regions = (isSegmented) ? collectRegions() : Collections.emptyMap();
081        }
082        
083        int[][] makeLabelArray(ByteProcessor ip) {
084                int[][] lA = new int[width][height];    // label array
085                // set all pixels to either FOREGROUND or BACKGROUND (by thresholding)
086                for (int v = 0; v < height; v++) {
087                        for (int u = 0; u < width; u++) {
088                                lA[u][v] = (ip.get(u, v) != 0) ? Foreground : Background;
089                        }
090                }
091                return lA;
092        }
093        
094        // -------------------------------------------------------------------------
095        
096        /**
097         * This method must be implemented by all concrete sub-classes.
098         * @param ip the image to be segmented
099         * 
100         * @return true if segmentation was successful
101         */
102        abstract boolean applySegmentation(ByteProcessor ip);
103        
104        /**
105         * Returns the width of the segmented image. 
106         * @return the width of the segmented image
107         */
108        public int getWidth() {
109                return this.width;
110        }
111        
112        /**
113         * Returns the height of the segmented image. 
114         * @return the height of the segmented image
115         */
116        public int getHeight() {
117                return this.height;
118        }
119        
120        /**
121         * Returns the minimum label assigned by this segmentation.
122         * @return the minimum label
123         */
124        public int getMinLabel() {
125                return minLabel;
126        }
127        
128        /**
129         * Returns the maximum label assigned by this segmentation.
130         * @return the maximum label
131         */
132        public int getMaxLabel() {
133                return maxLabel;
134        }
135        
136        /**
137         * Returns true if the segmentation did complete successfully,
138         * false otherwise.
139         * 
140         * @return true if segmentation was successful
141         */
142        public boolean isSegmented() {
143                return isSegmented;
144        }
145
146        /**
147         * Returns an unsorted list of all regions associated with this region labeling. The returned list is empty if no
148         * regions were detected. See also {@link #getRegions(boolean)}.
149         *
150         * @return a (possibly empty) list of detected regions
151         */
152        public List<BinaryRegion> getRegions() {
153                return getRegions(false);       // unsorted
154        }
155
156        /**
157         * Returns a (optionally sorted) list of all regions associated with this region labeling. The returned list is
158         * empty if no regions were detected.
159         *
160         * @param sort set {@code true} to sort regions by size (largest regions first).
161         * @return the list of detected regions or {@code null} if the segmentation has failed.
162         */
163        public List<BinaryRegion> getRegions(boolean sort) {
164                if (regions == null) {
165                        throw new RuntimeException("regions is null, this should never happen");
166                }
167                BinaryRegion[] ra = regions.values().toArray(new BinaryRegion[0]);
168                if (sort) {
169                        Arrays.sort(ra);
170                }
171                return Arrays.asList(ra);
172        }
173        
174        // -------------------------------------------------------------------------
175
176        /**
177         * Creates a (map) container of {@link BinaryRegion} objects, collects the region pixels from the label image and
178         * calls {@link SegmentationBackedRegion#update()} to compute the statistics for each region. Region label numbers
179         * serve as map keys.
180         *
181         * @return a map of {@link BinaryRegion} instances.
182         */
183        Map<Integer, SegmentationBackedRegion> collectRegions() {
184                SegmentationBackedRegion[] regionArray = new SegmentationBackedRegion[maxLabel + 1];
185                for (int label = minLabel; label <= maxLabel; label++) {
186                        regionArray[label] = new SegmentationBackedRegion(label, this);
187                }
188                for (int v = 0; v < height; v++) {
189                        for (int u = 0; u < width; u++) {
190                                int label = getLabel(u, v);
191                                if (label >= minLabel && label <= maxLabel && regionArray[label] != null) {
192                                        regionArray[label].addPixel(u, v);
193                                }
194                        }
195                }
196                // create a list of regions to return, collect nonempty regions
197                Map<Integer, SegmentationBackedRegion> regionMap = new LinkedHashMap<>();
198                for (SegmentationBackedRegion r: regionArray) {
199                        if (r != null && r.getSize() > 0) {
200                                r.update();     // compute the statistics for this region
201                                regionMap.put(r.getLabel(), r); //add(r);
202                        }
203                }
204                return regionMap;
205        }
206
207        /**
208         * Returns the label number for the specified image coordinate. -1 is returned for out-of-image coordinates.
209         *
210         * @param u the horizontal coordinate.
211         * @param v the vertical coordinate.
212         * @return the label number for the given position or -1 if outside the image
213         */
214        public int getLabel(int u, int v) {
215                return (u >= 0 && u < width && v >= 0 && v < height) ? labelArray[u][v] : -1;
216        }
217        
218        void setLabel(int u, int v, int label) {
219                if (u >= 0 && u < width && v >= 0 && v < height)
220                        labelArray[u][v] = label;
221        }
222        
223        int getNextLabel() {
224                currentLabel = (currentLabel < 1) ? minLabel : currentLabel + 1;
225                maxLabel = currentLabel;
226                return currentLabel;
227        }
228        
229        boolean isRegionLabel(int i) {
230                return (i >= minLabel);
231        }
232
233        // --------------------------------------------------
234
235        /**
236         * Finds the region associated to the specified label or {@code null} if no region for that label exists.
237         *
238         * @param label the region's label number
239         * @return the region object associated with the given label or {@code null} if it does not exist
240         */
241        public SegmentationBackedRegion getRegion(int label) {
242                return (label < minLabel || label > maxLabel) ? null : regions.get(label);
243        }
244
245        /**
246         * Returns the {@link BinaryRegion} instance associated with the given image position or {@code null} if the
247         * segmentation contains no region covering the given position.
248         *
249         * @param u the horizontal position.
250         * @param v the vertical position.
251         * @return The associated {@link BinaryRegion} object or {@code null} if this {@link BinaryRegionSegmentation} has
252         * no region at the given position.
253         */
254        public SegmentationBackedRegion getRegion(int u, int v) {
255                return getRegion(getLabel(u, v));
256        }
257
258}