001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030/**
031 *
032 */
033package org.openimaj.image.feature.local.detector.mser;
034
035import java.util.ArrayList;
036import java.util.List;
037
038import org.openimaj.citation.annotation.Reference;
039import org.openimaj.citation.annotation.ReferenceType;
040import org.openimaj.image.FImage;
041import org.openimaj.image.analysis.watershed.Component;
042import org.openimaj.image.analysis.watershed.MergeTreeBuilder;
043import org.openimaj.image.analysis.watershed.WatershedProcessor;
044import org.openimaj.image.analysis.watershed.feature.ComponentFeature;
045import org.openimaj.util.tree.TreeNode;
046
047/**
048 * Detector for MSER features.
049 *
050 * @author David Dupplaw (dpd@ecs.soton.ac.uk)
051 */
052@Reference(
053                type = ReferenceType.Article,
054                author = { "J Matas", "O Chum", "M Urban", "T Pajdla" },
055                title = "Robust wide-baseline stereo from maximally stable extremal regions",
056                year = "2004",
057                journal = "Image and Vision Computing",
058                pages = { "761 ", " 767" },
059                url = "http://www.sciencedirect.com/science/article/pii/S0262885604000435",
060                number = "10",
061                volume = "22",
062                customData = {
063                                "issn", "0262-8856",
064                                "doi", "10.1016/j.imavis.2004.02.006",
065                                "keywords", "Robust metric"
066                })
067public class MSERFeatureGenerator {
068        /**
069         * A way of representing how the MSER should be processed.
070         *
071         * @author David Dupplaw (dpd@ecs.soton.ac.uk)
072         *
073         */
074        public enum MSERDirection {
075                /**
076                 * Upwards detection
077                 */
078                Up,
079                /**
080                 * Downwards detection
081                 */
082                Down,
083                /**
084                 * Upwards and Downwards detection
085                 */
086                UpAndDown
087        }
088
089        private int delta = 10;
090        private int maxArea = Integer.MAX_VALUE;
091        private int minArea = 1;
092        private float maxVariation = Float.MAX_VALUE;
093        private float minDiversity = 0;
094        private Class<? extends ComponentFeature>[] featureClasses;
095
096        /**
097         * Default constructor
098         *
099         * @param featureClasses
100         *            features to generate for each mser
101         */
102        @SafeVarargs
103        public MSERFeatureGenerator(Class<? extends ComponentFeature>... featureClasses) {
104                this.featureClasses = featureClasses;
105        }
106
107        /**
108         * Constructor that takes all the parameters for the MSER process.
109         *
110         * @param delta
111         * @param maxArea
112         * @param minArea
113         * @param maxVariation
114         * @param minDiversity
115         * @param featureClasses
116         *            features to generate for each mser
117         */
118        @SafeVarargs
119        public MSERFeatureGenerator(int delta, int maxArea, int minArea, float maxVariation, float minDiversity,
120                        Class<? extends ComponentFeature>... featureClasses)
121        {
122                this(featureClasses);
123
124                this.delta = delta;
125                this.maxArea = maxArea;
126                this.minArea = minArea;
127                this.maxVariation = maxVariation;
128                this.minDiversity = minDiversity;
129        }
130
131        /**
132         * Performs a watershed then an MSER detection on the given image and
133         * returns the MSERs.
134         *
135         * @param img
136         *            The image to analyse.
137         * @return A list of {@link Component}s
138         */
139        public List<Component> generateMSERs(FImage img) {
140                return generateMSERs(img, MSERDirection.UpAndDown);
141        }
142
143        /**
144         * Performs a watershed then an MSER detection on the given image and
145         * returns the MSERs.
146         *
147         * @param img
148         *            The image to analyse.#
149         * @param dir
150         *            The direction which to process the MSERS
151         * @return A list of {@link Component}s
152         */
153        public List<Component> generateMSERs(FImage img, MSERDirection dir) {
154                final List<MergeTreeBuilder> mtb = performWatershed(img);
155                final List<Component> regions = performMSERDetection(mtb, dir);
156                return regions;
157        }
158
159        /**
160         * Perform the watershed algorithm on the given image.
161         *
162         * @param img
163         *            The image to perform the watershed on
164         * @return A tuple of {@link MergeTreeBuilder}s (down first, up second)
165         */
166        public List<MergeTreeBuilder> performWatershed(FImage img) {
167                // Create the image analysis object
168                final WatershedProcessor watershedUp = new WatershedProcessor(featureClasses);
169                final WatershedProcessor watershedDown = new WatershedProcessor(featureClasses);
170                final MergeTreeBuilder treeBuilderUp = new MergeTreeBuilder();
171                watershedUp.addComponentStackMergeListener(treeBuilderUp);
172                final MergeTreeBuilder treeBuilderDown = new MergeTreeBuilder();
173                watershedDown.addComponentStackMergeListener(treeBuilderDown);
174
175                // -----------------------------------------------------------------
176                // Watershed the image to get the tree
177                // -----------------------------------------------------------------
178                // bottom-up watershed
179                watershedUp.processImage(img);
180
181                // Invert the image, as we must detect MSERs from both top-down
182                // and bottom-up.
183                img = img.inverse();
184                // top-down watershed
185                watershedDown.processImage(img);
186
187                // Return the image to its original state.
188                img = img.inverse();
189
190                final List<MergeTreeBuilder> mtb = new ArrayList<MergeTreeBuilder>();
191                mtb.add(treeBuilderDown);
192                mtb.add(treeBuilderUp);
193                return mtb;
194        }
195
196        /**
197         * Performs MSER detection on the trees provided. The input list must be a
198         * list containing {@link MergeTreeBuilder}s, the first being the downward
199         * watershed, the second being the upward watershed.
200         *
201         * @param mtbs
202         *            The list of {@link MergeTreeBuilder}s
203         * @param dir
204         *            The direction to detect MSERs from
205         * @return A list of {@link Component}s
206         */
207        public List<Component> performMSERDetection(List<MergeTreeBuilder> mtbs, MSERDirection dir) {
208                // Remove the MSER component flags in the trees (in case they're being
209                // reused)
210                clearTree(mtbs.get(0).getTree());
211                clearTree(mtbs.get(1).getTree());
212
213                // -----------------------------------------------------------------
214                // Now run the MSER detector on it
215                // -----------------------------------------------------------------
216                // bottom up detection
217                // System.out.println( mtbs.get(1).getTree() );
218                List<Component> regionsUp = null;
219                if (mtbs.get(1).getTree() != null && (dir == MSERDirection.Up || dir == MSERDirection.UpAndDown)) {
220                        final MSERDetector mser = new MSERDetector(mtbs.get(1).getTree());
221                        mser.setDelta(this.delta);
222                        mser.setMaxArea(this.maxArea);
223                        mser.setMinArea(this.minArea);
224                        mser.setMaxVariation(this.maxVariation);
225                        mser.setMinDiversity(this.minDiversity);
226                        regionsUp = mser.detect();
227                        // System.out.println( "Top-down detected: "+regionsUp );
228                }
229
230                // top-down detection
231                List<Component> regionsDown = null;
232                if (mtbs.get(0).getTree() != null && (dir == MSERDirection.Down || dir == MSERDirection.UpAndDown)) {
233                        final MSERDetector mser2 = new MSERDetector(mtbs.get(0).getTree());
234                        mser2.setDelta(this.delta);
235                        mser2.setMaxArea(this.maxArea);
236                        mser2.setMinArea(this.minArea);
237                        mser2.setMaxVariation(this.maxVariation);
238                        mser2.setMinDiversity(this.minDiversity);
239                        regionsDown = mser2.detect();
240                        // System.out.println( "Bottom-up detected: "+regionsDown );
241                }
242
243                final List<Component> regions = new ArrayList<Component>();
244                if (regionsUp != null)
245                        regions.addAll(regionsUp);
246                if (regionsDown != null)
247                        regions.addAll(regionsDown);
248
249                // System.out.println( "Detected "+regions.size()+" regions ");
250                // System.out.println( "Detected "+countMSERs( mtbs.get(0).getTree()
251                // )+" in down tree" );
252                // System.out.println( "Detected "+countMSERs( mtbs.get(1).getTree()
253                // )+" in up tree" );
254                return regions;
255        }
256
257        /**
258         * Removes all the MSER flags from the components in the tree
259         *
260         * @param tree
261         *            The tree to clear MSER flags
262         */
263        private void clearTree(TreeNode<Component> tree) {
264                if (tree == null)
265                        return;
266                final Component c = tree.getValue();
267                if (c != null)
268                        c.isMSER = false;
269                if (tree.getChildren() != null)
270                        for (final TreeNode<Component> child : tree.getChildren())
271                                clearTree(child);
272        }
273
274        /**
275         * Returns a count of the number of components in the tree that are marked
276         * as MSERs.
277         *
278         * @param tree
279         *            The tree to count MSERs in
280         * @return the count
281         */
282        public int countMSERs(TreeNode<Component> tree) {
283                if (tree == null)
284                        return 0;
285                int retVal = 0;
286                final Component c = tree.getValue();
287                if (c != null && c.isMSER)
288                        retVal++;
289                if (tree.getChildren() != null)
290                        for (final TreeNode<Component> child : tree.getChildren())
291                                retVal += countMSERs(child);
292                return retVal;
293
294        }
295
296        /**
297         * @return the delta
298         */
299        public int getDelta() {
300                return delta;
301        }
302
303        /**
304         * @param delta
305         *            the delta to set
306         */
307        public void setDelta(int delta) {
308                this.delta = delta;
309        }
310
311        /**
312         * @return the maxArea
313         */
314        public int getMaxArea() {
315                return maxArea;
316        }
317
318        /**
319         * @param maxArea
320         *            the maxArea to set
321         */
322        public void setMaxArea(int maxArea) {
323                this.maxArea = maxArea;
324        }
325
326        /**
327         * @return the minArea
328         */
329        public int getMinArea() {
330                return minArea;
331        }
332
333        /**
334         * @param minArea
335         *            the minArea to set
336         */
337        public void setMinArea(int minArea) {
338                this.minArea = minArea;
339        }
340
341        /**
342         * @return the maxVariation
343         */
344        public float getMaxVariation() {
345                return maxVariation;
346        }
347
348        /**
349         * @param maxVariation
350         *            the maxVariation to set
351         */
352        public void setMaxVariation(float maxVariation) {
353                this.maxVariation = maxVariation;
354        }
355
356        /**
357         * @return the minDiversity
358         */
359        public float getMinDiversity() {
360                return minDiversity;
361        }
362
363        /**
364         * @param minDiversity
365         *            the minDiversity to set
366         */
367        public void setMinDiversity(float minDiversity) {
368                this.minDiversity = minDiversity;
369        }
370
371}