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 ******************************************************************************/
009package imagingbook.common.mser;
010
011import ij.process.ByteProcessor;
012import imagingbook.common.mser.components.Component;
013import imagingbook.common.mser.components.ComponentTree;
014import imagingbook.common.mser.components.PixelMap.Pixel;
015
016import java.util.LinkedList;
017import java.util.List;
018
019/**
020 * <p>
021 * Performs "Maximally Stable Extremal Region" (MSER) detection [1] on gray-scale images. See Chapter 26 of [2] for more
022 * details. The constructor sets up the complete component tree for the specified image but does not perform feature
023 * detection itself, which is done by calling {@link #getMserFeatures()}.
024 * </p>
025 * <p>
026 * [1] J. Matas, O. Chum, M. Urban, and T. Pajdla. Robust widebaseline stereo from maximally stable extremal regions.
027 * Image and Vision Computing 22(10), 761–767 (2004). <br> [2] W. Burger, M.J. Burge, <em>Digital Image Processing
028 * &ndash; An Algorithmic Introduction</em>, 3rd ed, Springer (2022).
029 * </p>
030 *
031 * @author WB
032 * @version 2022/11/23
033 */
034public class MserDetector {
035
036        private final MserParameters params;
037        private final ComponentTree<MserData> compTree;
038        private final double minSizeAbs;
039        private final double maxSizeAbs;
040        private final double maxVar;
041        private final double minDiv;    
042        private final double elapsedTimeMs;
043        
044        private List<Component<MserData>> msers = null; // used to collect MSERs
045        
046        // --------------------------------------------------------------------
047        
048        /**
049         * Constructor using default parameters. 
050         * 
051         * @param ip the input image
052         * @see #MserDetector(ByteProcessor, MserParameters)
053         */
054        public MserDetector(ByteProcessor ip) {
055                this(ip, new MserParameters());
056        }
057
058        /**
059         * Constructor using explicit parameters. A set of parameters can be specified (see {@link MserParameters}). The
060         * constructor sets up the complete component tree but does not perform feature detection itself, which is done by
061         * calling {@link #getMserFeatures()}.
062         *
063         * @param ip the input image
064         * @param params a {@link MserParameters} instance
065         * @see MserParameters
066         */
067        public MserDetector(ByteProcessor ip, MserParameters params) {
068                this.params = params;
069                long startTime = System.nanoTime();
070                
071                // set up the component tree for ip
072                this.compTree = ComponentTree.from(ip, params.method);
073                
074                if (params.validateComponentTree) {
075                        if(!compTree.validate()) {
076                                throw new RuntimeException("component tree not valid");
077                        }
078                }
079
080                attachMserProperties(compTree);
081                calcVariations(compTree, params.delta);
082                markMaximallyStable(compTree);
083                updateStatistics(compTree.getRoot());   // calcPointStatistics(compTree);
084
085                int imgSize = ip.getWidth() * ip.getHeight();
086                
087                this.minSizeAbs = 
088                                Math.max((int) (imgSize * params.minRelCompSize), params.minAbsComponentArea);
089                this.maxSizeAbs = (int) (imgSize * params.maxRelCompSize);
090                this.maxVar = params.maxSizeVariation;
091                this.minDiv = params.minDiversity;
092                
093                this.elapsedTimeMs = (System.nanoTime() - startTime) / 1000000.0;
094        }
095
096        // -----------------------------------------------------------------------
097
098        /**
099         * Extracts and returns a list of MSER components. Features are extracted only once and cached for subsequent
100         * calls.
101         *
102         * @return a list of extracted MSER components
103         */
104        public List<Component<MserData>> getMserFeatures() {
105                if (this.msers == null) {
106                        this.msers = new LinkedList<>();
107                        collectMsers(compTree.getRoot(), Integer.MAX_VALUE);
108                }
109                return this.msers;
110        }
111        
112        // -----------------------------------------------------------------------
113
114        /**
115         * Attach Mser data to all region tree components.
116         * @param tree
117         */
118        private void attachMserProperties(ComponentTree<MserData> tree) {
119                for (Component<MserData> c : tree) {
120                        c.setProperties(new MserData(c));
121                }
122        }
123        
124        /**
125         * New version, works on components in any order.
126         * @param compTree
127         * @param delta
128         */
129        private void calcVariations(ComponentTree<MserData> compTree, int delta) {
130                for (Component<MserData> c : compTree) {                
131                        c.getProperties().variation = Float.POSITIVE_INFINITY;
132                        Component<?> p = c.getParent();
133                        if (p != null) {        // c is not root
134                                final int ld = c.getLevel() + delta;
135                                Component<?> cc = c;
136                                
137                                // find the next ancestor component (p) whose level val(p) >= vd :
138                                while (p != null && p.getLevel() < ld) {
139                                        // IJ.log("        hiC=" + hiC.ID + " hiC.parent.level=" + hiC.getParent().getLevel());
140                                        cc = p;                 // climb upward
141                                        p = cc.getParent();
142                                }
143                                if (p != null) {        // cc is not the root -->  pp.getLevel() >= vd
144                                        // calculate growth and assign to c
145                                        float ac  = c.getSize();                // size of the current component (c)
146                                        float acc = cc.getSize();               // size of the upper component (cc)
147                                        c.getProperties().variation = (acc - ac) / ac;
148                                }
149                        }
150                }
151        }
152        
153        /**
154         * We start from the root and walk down recursively.
155         * Every node is only visited once.
156         */
157        private void markMaximallyStable(ComponentTree<MserData> compTree) {
158                // initially assume all components are max. stable
159                for (Component<MserData> c : compTree) {
160                        Component<MserData> p = c.getParent();
161                        if (p == null) {                                        // the root is always unstable
162                                c.getProperties().isStable = false;
163                        }
164                        else if (c.getLevel() + 1 == p.getLevel()) {
165                                float vp = p.getProperties().variation;
166                                float vc = c.getProperties().variation;
167                                
168                                if (vc < vp) {
169                                        p.getProperties().isStable = false;
170                                }
171                                else if (vc > vp) {
172                                        c.getProperties().isStable = false;
173                                }
174                        }
175                }
176        }
177
178        /**
179         * Calculates point (coordinate) statistics for all tree components. We start at the forest root nodes and walk down
180         * recursively toward the leaf nodes. Each component carries a 5-element {@code long} vector of sums, where each
181         * element is the sum of the corresponding elements over all child components.
182         *
183         * @param c the current component
184         * @return a 5-element vector of coordinate sums
185         */
186        private long[] updateStatistics(Component<MserData> c) {
187                if (c.getProperties().stats != null) {
188                        throw new RuntimeException(this.getClass().getSimpleName() + ": sums array should not exist yet!");
189                }
190                long[] m = new long[5];
191                for (Pixel p : c.getLocalPixels()) {
192                        final long x = p.x;
193                        final long y = p.y;
194                        m[0] += x;
195                        m[1] += y;
196                        m[2] += x * x;
197                        m[3] += y * y;
198                        m[4] += x * y;
199                }
200
201                for (Component<MserData> child : c.getChildren()) {
202                        long[] sc = updateStatistics(child);
203                        for (int i = 0; i < sc.length; i++) {
204                                m[i] += sc[i];
205                        }
206                }
207                c.getProperties().stats = m;
208                //              IJ.log("updateStatistics: " + c.toString() + " " + Arrays.toString(c.sums));
209                return m;
210        }
211
212        // --------------------------------------------------------------------------------
213
214        /**
215         * Checks and collects component 'c' into {@link #msers}'. Started from a root component, recursively walks toward
216         * the leaf components. Diversity is the size ratio between collected components on the same path. I.e., to be
217         * eligible, the current component must be significantly smaller than the previously collected component. This
218         * starts with the largest component.
219         *
220         * @param c the current component
221         * @param ap the size of the closest ancestor component marked as MSER
222         */
223        private void collectMsers(Component<MserData> c, int ap) {
224                int ac = c.getSize();           // the current component's size
225
226                MserData props = c.getProperties();
227                if (props.isStable && 
228                                minSizeAbs <= ac && ac <= maxSizeAbs && 
229                                props.variation <= maxVar && 
230                                ((ap - ac) / (double) ap) >= minDiv) {
231
232                        props.init();
233                        double ellipseArea = props.getEllipse().getArea();
234                        double compactness = ac / ellipseArea;
235                        // ignore MSERs whose ellipse is too big (if turned on)
236                        // ignore MSERs whose size is much smaller than the associated ellipse (i.e., not compact at all)
237                        if ((!params.constrainEllipseSize || ellipseArea <= maxSizeAbs) && 
238                                        compactness > params.minCompactness) {
239                                this.msers.add(c);
240                                ap = ac;
241                                props.isMserP = true;   // mark component c as a selected MSER
242                        }
243                }
244                
245                if (ac > minSizeAbs) { // continue unless size is too small
246                        // recursively collect components from all children:
247                        for (Component<MserData> child : c.getChildren()) {
248                                collectMsers(child, ap);
249                        }
250                }
251        }
252
253        /**
254         * Returns the component tree for this MSER detector.
255         * 
256         * @return the component tree
257         */
258        public ComponentTree<MserData> getComponentTree() {
259                return compTree;
260        }
261
262        /**
263         * Returns the time required for the MSER detector to process the
264         * associated image (in milliseconds).
265         * 
266         * @return time required for MSER detection (ms)
267         */
268        public double getElapsedTime() {
269                return elapsedTimeMs;
270        }
271
272}