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 */
030package org.openimaj.image.analysis.watershed;
031
032import java.util.HashMap;
033import java.util.Map;
034
035import org.apache.log4j.Logger;
036import org.openimaj.image.analysis.watershed.event.ComponentStackMergeListener;
037import org.openimaj.util.tree.TreeNode;
038import org.openimaj.util.tree.TreeNodeImpl;
039
040/**
041 * A listener that listens to the watershed algorithm progress and creates a
042 * region tree as the processing takes place.
043 *
044 * @author David Dupplaw (dpd@ecs.soton.ac.uk)
045 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
046 *
047 */
048public class MergeTreeBuilder implements ComponentStackMergeListener
049{
050        Logger logger = Logger.getLogger(MergeTreeBuilder.class);
051
052        /** This is the tree we build */
053        private TreeNode<Component> tree = null;
054
055        /**
056         * Because we're creating components to store the history, the components
057         * that are being processed by the algorithm are not the same as those in
058         * our tree, so we must provide a map so that we can join up the tree
059         * afterwards.
060         */
061        private Map<Component, TreeNode<Component>> map = null;
062
063        /**
064         * Default constructor
065         */
066        public MergeTreeBuilder()
067        {
068                map = new HashMap<Component, TreeNode<Component>>();
069        }
070
071        /**
072         * {@inheritDoc}
073         *
074         * @see org.openimaj.image.analysis.watershed.event.ComponentStackMergeListener#componentsMerged(org.openimaj.image.analysis.watershed.Component,
075         *      org.openimaj.image.analysis.watershed.Component)
076         */
077        @Override
078        public void componentsMerged(Component c1, Component c2)
079        {
080                // logger.debug( "Map: "+map );
081                logger.debug("Component c1: " + c1);
082                logger.debug("Component c2: " + c2);
083
084                // Create a tree node for the component if it doesn't
085                // exist already
086                TreeNode<Component> c1xtn = map.get(c1);
087                if (c1xtn == null)
088                {
089                        logger.debug("c1 not found");
090                        c1xtn = new TreeNodeImpl<Component>();
091                        final Component c1x = c1.clone();
092                        c1xtn.setValue(c1x);
093                        map.put(c1, c1xtn);
094                }
095
096                // Add all the pixels from c2 into our copy of c1
097                c1xtn.getValue().merge(c2);
098
099                // Create a tree node for the second component
100                // if it doesn't exist already
101                TreeNode<Component> c2xtn = map.get(c2);
102                if (c2xtn == null)
103                {
104                        logger.debug("c2 not found");
105                        c2xtn = new TreeNodeImpl<Component>();
106                        final Component c2x = c2.clone();
107                        c2xtn.setValue(c2x);
108                        map.put(c2, c2xtn);
109                }
110
111                // logger.debug("Linking " + c1xtn + " and " + c2xtn);
112
113                // Link the tree nodes
114                c1xtn.addChild(c2xtn);
115                this.tree = c1xtn;
116        }
117
118        /**
119         * {@inheritDoc}
120         *
121         * @see org.openimaj.image.analysis.watershed.event.ComponentStackMergeListener#componentPromoted(org.openimaj.image.analysis.watershed.Component)
122         */
123        @Override
124        public void componentPromoted(Component c1)
125        {
126                final TreeNode<Component> c1xtn_old = map.get(c1);
127
128                final Component c1x = c1.clone();
129
130                final TreeNode<Component> c1xtn = new TreeNodeImpl<Component>();
131                c1xtn.setValue(c1x);
132
133                map.put(c1, c1xtn);
134
135                if (c1xtn_old != null)
136                        c1xtn.addChild(c1xtn_old);
137        }
138
139        /**
140         * Return the tree that has been built.
141         *
142         * @return the tree
143         */
144        public TreeNode<Component> getTree()
145        {
146                return tree;
147        }
148}