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-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 java.awt.Color;
013import java.awt.Point;
014import java.awt.Rectangle;
015import java.awt.geom.Point2D;
016import java.util.ArrayList;
017import java.util.Collections;
018import java.util.Formatter;
019import java.util.HashMap;
020import java.util.Iterator;
021import java.util.LinkedList;
022import java.util.List;
023import java.util.Locale;
024import java.util.Map;
025import java.util.NoSuchElementException;
026
027import ij.process.ByteProcessor;
028import ij.process.ColorProcessor;
029import ij.process.ImageProcessor;
030import ij.process.ShortProcessor;
031
032/**
033 * This class does the complete region labeling for a given image.
034 * It is abstract, because the implementation of some parts depends
035 * on the region labeling algorithm being used.
036 * 
037 * @version 2016-11-08
038 */
039public abstract class RegionLabeling {
040        
041        static final int BACKGROUND = 0;
042        static final int FOREGROUND = 1;
043        static final int START_LABEL = 2;
044
045        protected final ImageProcessor ip;
046        protected final int width;
047        protected final int height;
048        
049        protected final int[][] labelArray;
050        // label values in labelArray can be:
051        //  0 ... unlabeled
052        // -1 ... previously visited background pixel
053        // >0 ... valid label
054        
055        protected int currentLabel;
056        protected int maxLabel; // the maximum label in the labels array
057        protected List<BinaryRegion> regions;
058        
059        protected RegionLabeling(ByteProcessor ip) {
060                this.ip = ip;
061                width  = ip.getWidth();
062                height = ip.getHeight();
063                labelArray = initialize();
064                applyLabeling();
065                collectRegions();
066        }
067        
068        protected int[][]  initialize() {
069                int[][] lA = new int[width][height];    // label array
070                // set all pixels to either FOREGROUND or BACKGROUND (by thresholding)
071                for (int v = 0; v < height; v++) {
072                        for (int u = 0; u < width; u++) {
073                                lA[u][v] = (ip.getPixel(u, v) > 0) ? FOREGROUND : BACKGROUND;
074                        }
075                }
076                return lA;
077        }
078        
079        /**
080         * Get an unsorted list of all regions associated with this region labeling.
081         * @return the list of regions.
082         */
083        public List<BinaryRegion> getRegions() {
084                return getRegions(false);       // unsorted
085        }
086        
087        /**
088         * Get a possibly sorted list of all regions associated with this region labeling.
089         * @param sort set {@code true} to sort regions by decreasing size.
090         * @return the list of regions.
091         */
092        public List<BinaryRegion> getRegions(boolean sort) {
093                if (regions == null) 
094                        return Collections.emptyList();
095                else {
096                        List<BinaryRegion> rns = new ArrayList<BinaryRegion>(regions);
097                        if (sort) {
098                                Collections.sort(rns);
099                        }
100                        return rns;
101                }
102        }
103        
104        // This method must be implemented by any real sub-class:
105        abstract void applyLabeling();
106        
107        // creates a container of BinaryRegion objects
108        // collects the region pixels from the label image
109        // and computes the statistics for each region
110        void collectRegions() {
111                BinaryRegion[] regionArray = new BinaryRegion[maxLabel + 1];
112                for (int i = START_LABEL; i <= maxLabel; i++) {
113                        regionArray[i] = new BinaryRegion(i);
114                }
115                for (int v = 0; v < height; v++) {
116                        for (int u = 0; u < width; u++) {
117                                int label = getLabel(u, v);
118                                if (label >= START_LABEL && label <= maxLabel && regionArray[label] != null) {
119                                        regionArray[label].addPixel(u, v);
120                                }
121                        }
122                }
123                // create a list of regions to return, collect nonempty regions
124                List<BinaryRegion> regionList = new LinkedList<BinaryRegion>();
125                for (BinaryRegion r: regionArray) {
126                        if (r != null && r.getSize() > 0) {
127                                r.update();     // compute the statistics for this region
128                                regionList.add(r);
129                        }
130                }
131                regions = regionList;
132        }
133        
134        /**
135         * Get the label number for the specified image coordinate.
136         * @param u the horizontal coordinate.
137         * @param v the vertical coordinate.
138         * @return the label number for the given position.
139         */
140        public int getLabel(int u, int v) {
141                if (u >= 0 && u < width && v >= 0 && v < height)
142                        return labelArray[u][v];
143                else
144                        return BACKGROUND;
145        }
146        
147        protected void setLabel(int u, int v, int label) {
148                if (u >= 0 && u < width && v >= 0 && v < height)
149                        labelArray[u][v] = label;
150        }
151        
152        protected void resetLabel() {
153                currentLabel = -1;
154                maxLabel = -1;
155        }
156        
157        int getNextLabel() {
158                if (currentLabel < 1)
159                        currentLabel = START_LABEL;
160                else
161                        currentLabel = currentLabel + 1;
162                maxLabel = currentLabel;
163                return currentLabel;
164        }
165        
166        int getMaxLabel() {
167                return maxLabel;
168        }
169        
170        // --------------------------------------------------
171        
172        /**
173         * Utility method that creates an image of the internal
174         * label array.
175         * 
176         * @param color set {@code false} to get a 16-bit grayscale image,
177         * {@code true} for an RGB (24-bit) color image.
178         * @return an image of the label array.
179         */
180        public ImageProcessor makeLabelImage(boolean color) {
181                return (color) ?  makeLabelImageColor() : makeLabelImageGray();
182        }
183
184        private ColorProcessor makeLabelImageColor() {
185                int[] colorLUT = new int[maxLabel+1];
186                for (int i = START_LABEL; i <= maxLabel; i++) {
187                        colorLUT[i] = makeRandomColor();
188                }
189                ColorProcessor cp = new ColorProcessor(width, height);
190                for (int v = 0; v < height; v++) {
191                        for (int u = 0; u < width; u++) {
192                                int lb = getLabel(u, v);
193                                if (lb >= 0 && lb < colorLUT.length) {
194                                        cp.putPixel(u, v, colorLUT[lb]);
195                                }
196                        }
197                }
198                return cp;
199        }
200        
201        private ShortProcessor makeLabelImageGray() {
202                ShortProcessor sp = new ShortProcessor(width, height);
203                for (int v = 0; v < height; v++) {
204                        for (int u = 0; u < width; u++) {
205                                int lb = getLabel(u, v);
206                                sp.set(u, v, (lb >= 0) ? lb : 0);
207                        }
208                }
209                sp.resetMinAndMax();
210                return sp;
211        }
212        
213
214        /**
215         * Find the region associated to the given label.
216         * @param label the label number.
217         * @return the associated region object or {@code null} if
218         * is does not exist.
219         * 
220         * @param label the label number.
221         * @return the region object associated with the given label
222         *              or {@code null} if it does not exist.
223         */
224        public BinaryRegion findRegion(int label) {
225                if (label <= 0 || regions == null) return null;
226                BinaryRegion regn = null;
227                for (BinaryRegion r : regions) {
228                        if (r.getLabel() == label) {
229                                regn = r;
230                                break;
231                        }
232                }
233                return regn;
234        }
235        
236        /**
237         * Finds the {@link BinaryRegion} instance associated with
238         * the given image position.
239         * @param u the horizontal position.
240         * @param v the vertical position.
241         * @return The associated {@link BinaryRegion} object or null if
242         * this {@link RegionLabeling} has no region at the given position.
243         */
244        public BinaryRegion getRegion(int u, int v) {
245                int label = getLabel(u, v);
246                return findRegion(label);
247        }
248        
249        protected int makeRandomColor() {
250                double saturation = 0.2;
251                double brightness = 0.2;
252                float h = (float) Math.random();
253                float s = (float) (saturation * Math.random() + 1 - saturation);
254                float b = (float) (brightness * Math.random() + 1 - brightness);
255                return Color.HSBtoRGB(h, s, b);
256        }
257        
258//      private void printSummary() {
259//              if (regions != null) {
260//                      IJ.log("Number of regions detected: " + regions.size());
261//                      for (BinaryRegion r : regions) {
262//                              IJ.log(r.toString());
263//                      }
264//              } else
265//                      IJ.log("No regions found.");
266//      }
267        
268        
269        // --------- Iteration over region pixels -----------------------------------
270        
271        /**
272         * @deprecated
273         * This method is not supported any longer.
274         * Instead use {@code Iterable<Point>} capability of {@link BinaryRegion}
275         * to iterate directly over region points.
276         * 
277         * @param r the binary region.
278         * @return an {@link Iterable} to iterate over all region points.
279         */
280        public Iterable<Point> getRegionPoints(final BinaryRegion r) {
281                return r.getRegionPoints();
282        }
283        
284        private class RegionPixelIterator implements Iterator<Point> {
285                final int label;                                        // the corresponding region's label
286                final int uMin, uMax, vMin, vMax;       // coordinates of region's bounding box
287                int uCur, vCur;                                         // current pixel position
288                Point pNext;                                            // coordinates of the next region pixel
289                boolean first;                                          // control flag
290
291                RegionPixelIterator(BinaryRegion R) {
292                        label = R.getLabel();
293                        first = true;
294                        Rectangle bb = R.getBoundingBox();
295                        uMin = bb.x;
296                        uMax = bb.x + bb.width;
297                        vMin = bb.y;
298                        vMax = bb.y + bb.height;
299                        uCur = uMin;
300                        vCur = vMin;
301                        pNext = null;
302                }
303
304                /** 
305                 * Search from position (uCur, vCur) for the next valid region pixel.
306                 * Return the next position as a Point or null if no such point can be found.
307                 * Don't assume that (uCur, vCur) is a valid region pixel!
308                 * 
309                 * @return the next point
310                 */
311                private Point findNext() {
312                        // start search for next region pixel at (u,v):
313                        int u = (first) ? uCur : uCur + 1;
314                        int v = vCur;
315                        first = false;
316                        while (v <= vMax) {
317                                while (u <= uMax) {
318                                        if (getLabel(u, v) == label) { // next pixel found (uses surrounding labeling)
319                                                uCur = u;
320                                                vCur = v;
321                                                return new Point(uCur, vCur);
322                                        }
323                                        u++;
324                                }
325                                v++;
326                                u = uMin;
327                        }
328                        uCur = uMax + 1;        // just to make sure we'll never enter the loop again
329                        vCur = vMax + 1;
330                        return null;            // no next pixel found
331                }
332
333                @Override
334                public boolean hasNext() {
335                        if (pNext != null) {    // next element has been queried before but not consumed
336                                return true;
337                        }
338                        else {
339                                pNext = findNext();     // keep next pixel coordinates in pNext
340                                return (pNext != null);
341                        }
342                }
343
344                // Returns: the next element in the iteration
345                // Throws: NoSuchElementException - if the iteration has no more elements.
346                @Override
347                public Point next() {
348                        if (pNext != null || hasNext()) {
349                                Point pn = pNext;
350                                pNext = null;           // "consume" pNext
351                                return pn;
352                        }
353                        else {
354                                throw new NoSuchElementException();
355                        }
356                }
357
358                @Override
359                public void remove() {
360                        throw new UnsupportedOperationException();
361                }
362
363        } // end of RegionPixelIterator
364        
365        
366        /**
367         * This inner class of {@link RegionLabeling} represents a connected 
368         * component or binary region. 
369         * It supports iteration over the contained points, e.g., by
370         * <pre>
371         * BinaryRegion R = ...;
372         * for (Point p : R) {
373         *    // process p ...
374         * }
375         * </pre>
376         */
377        public class BinaryRegion implements Comparable<BinaryRegion>, Iterable<Point> {
378                private final int label;                                // the label of THIS region
379                private int size = 0;
380                private double xc = Double.NaN;
381                private double yc = Double.NaN;
382                private int left = Integer.MAX_VALUE;
383                private int right = -1;
384                private int top = Integer.MAX_VALUE;
385                private int bottom = -1;
386                
387                private Contour outerContour;
388                private List<Contour> innerContours;
389                
390                // summation variables used for various statistics
391                private long x1Sum  = 0;
392                private long y1Sum  = 0;
393                private long x2Sum = 0;
394                private long y2Sum = 0;
395                
396                // ------- constructor --------------------------
397                
398                private BinaryRegion(int label) {
399                        this.label = label;
400                        this.outerContour = null;
401                        this.innerContours = null;
402                }
403                
404                /**
405                 * Get the x-value of the region's centroid.
406                 * @return the x-value of the region's centroid.
407                 */
408                public double getXc() {
409                        return xc;
410                }
411
412                /**
413                 * Get the y-value of the region's centroid.
414                 * @return the y-value of the region's centroid.
415                 */
416                public double getYc() {
417                        return yc;
418                }
419                
420                /**
421                 * Returns the sum of the x-values of the points
422                 * contained in this region.
423                 * 
424                 * @return the sum of x-values.
425                 */
426                public long getX1Sum() {
427                        return x1Sum;
428                }
429
430                /**
431                 * Returns the sum of the y-values of the points
432                 * contained in this region.
433                 * 
434                 * @return the sum of y-values.
435                 */
436                public long getY1Sum() {
437                        return y1Sum;
438                }
439
440                /**
441                 * Returns the sum of the squared x-values of the points
442                 * contained in this region.
443                 * 
444                 * @return the sum of squared x-values.
445                 */
446                public long getX2Sum() {
447                        return x2Sum;
448                }
449
450                /**
451                 * Returns the sum of the squared y-values of the points
452                 * contained in this region.
453                 * 
454                 * @return the sum of squared y-values.
455                 */
456                public long getY2Sum() {
457                        return y2Sum;
458                }
459
460                // ------- public methods --------------------------
461                
462                /**
463                 * Get the label associated with this region.
464                 * @return the region label.
465                 */
466                public int getLabel() {
467                        return this.label;
468                }
469                
470                /**
471                 * Get the size of this region.
472                 * @return the number of region points.
473                 */
474                public int getSize() {
475                        return this.size;
476                }
477                
478                /**
479                 * Get the x/y axes-parallel bounding box as a rectangle
480                 * (including the extremal coordinates).
481                 * @return the bounding box rectangle.
482                 */
483                public Rectangle getBoundingBox() {
484                        if (right < 0)
485                                return null;
486                        else
487                                return new Rectangle(left, top, right-left + 1, bottom - top + 1);
488                }
489                
490                /**
491                 * @deprecated
492                 * Returns the centroid of this region as a 2D point.
493                 * Use {@link getCenterPoint} or {@link getXc} and {@link getYc} instead.
494                 * @return the centroid of this region.
495                 */
496                public Point2D getCenter() {
497                        if (Double.isNaN(xc))
498                                return null;
499                        else
500                                return new Point2D.Double(xc, yc);
501                }
502                
503                
504                /**
505                 * Returns the centroid of this region as a 2D point.
506                 * See also {@link getXc}, {@link getYc}.
507                 * 
508                 * @return the centroid of this region.
509                 */
510                public Point2D getCenterPoint() {
511                        if (Double.isNaN(xc))
512                                return null;
513                        else
514                                return new Point2D.Double(xc, yc);
515                }
516                
517                // iteration --------------------------------------
518                
519                @Override
520                public Iterator<Point> iterator() {
521                        return new RegionPixelIterator(this);
522                }
523                
524                /**
525                 * @deprecated
526                 * Replaced by BinaryRegion implementing {@code Iterable<Point>}.
527                 * @return iterator to be used in a for-loop. 
528                 */
529                public Iterable<Point> getRegionPoints() {
530                        //return RegionLabeling.this.getRegionPoints(this);
531                        return new Iterable<Point>() {  // anonymous class!
532                                public Iterator<Point> iterator() {
533                                        return new RegionPixelIterator(BinaryRegion.this);
534                                }
535                        };
536                }
537                
538
539                /**
540                 * Use this method to add a single pixel to this region. Updates summation
541                 * and boundary variables used to calculate various region statistics.
542                 * 
543                 * @param u x-position
544                 * @param v y-position
545                 */
546                protected void addPixel(int u, int v) {
547                        size = size + 1;
548                        x1Sum = x1Sum + u;
549                        y1Sum = y1Sum + v;
550                        x2Sum = x2Sum + u * u;
551                        y2Sum = y2Sum + v * v;
552                        if (u < left)   left = u;
553                        if (v < top)    top = v;
554                        if (u > right)  right = u;
555                        if (v > bottom) bottom = v;
556                }
557                
558                /**
559                 * Call this method to update the region's statistics. For now only the
560                 * center coordinates (xc, yc) are updated. Add additional statements as
561                 * needed to update your own region statistics.
562                 */
563                protected void update() {
564                        if (size > 0) {
565                                xc = (double) x1Sum / size;
566                                yc = (double) y1Sum / size;
567                        }
568                }
569                
570                /**
571                 * Get the (single) outer contour of this region.
572                 * Points on an outer contour are arranged in clockwise
573                 * order.
574                 * @return the outer contour.
575                 */
576                public Contour getOuterContour() {
577                        return outerContour;
578                }
579                
580                protected void setOuterContour(Contour contr) {
581                        outerContour = contr;
582                }
583                
584                /**
585                 * Get all inner contours of this region.
586                 * Points on inner contours are arranged in counter-clockwise
587                 * order.
588                 * @return the list of inner contours.
589                 */
590                public List<Contour> getInnerContours() {
591                        return innerContours;
592                }
593                
594                protected void makeInnerContours() {
595                        if (innerContours == null) {
596                                innerContours = new LinkedList<Contour>();
597                        }
598                }
599                
600                protected void addInnerContour(Contour contr) {
601                        makeInnerContours();
602                        innerContours.add(contr);
603                }
604                
605                public String toString() {
606                        Formatter fm = new Formatter(new StringBuilder(), Locale.US);
607                        fm.format("Region %d", label);
608                        fm.format(", area = %d", size);
609                        fm.format(", bounding box = (%d, %d, %d, %d)", left, top, right, bottom );
610                        fm.format(", centroid = (%.2f, %.2f)", xc, yc);
611                        if (innerContours != null)
612                                fm.format(", holes = %d", innerContours.size());
613                        String s = fm.toString();
614                        fm.close();
615                        return s;
616                }
617                
618                // Compare method for sorting by region size (larger regions at front)
619                @Override
620                public int compareTo(BinaryRegion r2) {
621                        return r2.size - this.size;
622                }
623                
624                /* EXPERIMENTAL STUFF for attaching region properties dynamically:
625                 * Properties can be used to hash results of region calculations
626                 * to avoid multiple calculations.
627                 * Currently, only 'double' values are supported.
628                 * 
629                 * E.g. calculate major axis angle theta for region r, then do
630                 *    r.setProperty("angle", theta);
631                 * and subsequently
632                 *    double theta = r.getProperty("angle");
633                 */
634                
635                private Map<String, Double> properties = null;
636                
637                /**
638                 * Sets the specified property of this region to the given value.
639                 * @param name Chosen name of the property.
640                 * @param val Value associated with this property.
641                 */
642                public void setProperty(String name, double val) {
643                        if (properties == null) {
644                                properties = new HashMap<String, Double>();
645                        }
646                        properties.put(name, val);
647                }
648                
649                /**
650                 * Retrieves the specified region property. 
651                 * An {@link IllegalArgumentException} is thrown if the property 
652                 * is not defined for this region.
653                 * 
654                 * @param name The name of the property.
655                 * @return The value associated with the specified property.
656                 */
657                public double getProperty(String name) {
658                        Double value;
659                        if (properties == null || (value = properties.get(name)) == null) {
660                                throw new IllegalArgumentException("Region property " + name + " is undefined.");
661                        }
662                        return value.doubleValue();
663                }
664                
665                /**
666                 * Removes all properties attached to this region.
667                 */
668                public void clearProperties() {
669                        properties.clear();
670                }
671
672
673
674        }
675
676}