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.components; 010 011import imagingbook.common.geometry.basic.Pnt2d.PntInt; 012import imagingbook.common.mser.MserData; 013import imagingbook.common.mser.components.PixelMap.Pixel; 014 015import java.util.ArrayList; 016import java.util.Arrays; 017import java.util.Collection; 018import java.util.Iterator; 019import java.util.LinkedList; 020 021/** 022 * <p> 023 * This class is a re-implementation of the "quasi-linear-time" component tree algorithm which is based on efficient, 024 * tree-based union finding as described in [1]. See Section 26.2.2 of [2] for a detailed description (Algs. 26.1 - 025 * 26.2). This algorithm is also used in the original MSER paper by Matas et al. [3]. 026 * </p> 027 * <p> 028 * [1] L. Vincent and P. Soille, "Watersheds in digital spaces: An efficient algorithm based on immersion simulations", 029 * IEEE Transactions on Pattern Analysis and Machine Intelligence 13(6), 583–598 (1991). 030 * <br> 031 * [2] W. Burger, M.J. Burge, <em>Digital Image Processing – An Algorithmic Introduction</em>, 3rd ed, Springer 032 * (2022). 033 * <br> 034 * [3] J. Matas, O. Chum, M. Urban, and T. Pajdla. Robust widebaseline stereo from maximally stable extremal regions. 035 * Image and Vision Computing 22(10), 761–767 (2004). 036 * </p> 037 * 038 * @param <T> the type of properties to be attached to components 039 * @author WB 040 * @version 2022/11/19 041 */ 042public class ComponentTreeGlobalImmersion<T> extends ComponentTree<T> { 043 044 private final Collection<Component<T>> components; 045 private final Component<T> root; 046 047 /** 048 * Constructor, creates a new component tree from a {@link PixelMap} representing a gray-level image. 049 * 050 * @param pm a {@link PixelMap} 051 */ 052 public ComponentTreeGlobalImmersion(PixelMap pm) { 053 root = collectComponents(pm); 054 components = new ArrayList<>(); 055 buildTree(); 056 } 057 058 @Override 059 public Component<T> getRoot() { 060 return root; 061 } 062 063 @Override 064 public Collection<Component<T>> getComponents() { 065 return components; 066 } 067 068 // ------------------------------------------------------------ 069 070 /** 071 * Collects all image pixels (in sorted order) and creates a preliminary component tree whose root is returned. 072 * 073 * @param P a {@link PixelMap} (the input image) 074 * @return 075 */ 076 private Component<T> collectComponents(PixelMap P) { 077 final Pixel[] Q = P.getPixelVector(); 078 Arrays.sort(Q); // sorts pixels in P by increasing gray-level (value) 079 080 final ComponentMap<T> C = new ComponentMap<T>(P.width, P.height); 081 Component<T> r = null; // root of the component tree 082 083 for (Pixel p : Q) { 084 Component<T> cp = C.makeComponent(p); // creates a new sub-tree (with cp as root) 085 Pixel n = p.getNextNeighbor(); 086 while (n != null) { 087 Component<T> cn = C.getComponent(n); 088 if (cn != null) { 089 // the neighbor component is already part of a tree) 090 // find the associated roots 091 Component<T> rp = cp.findRoot(); // root of p 092 Component<T> rn = cn.findRoot(); // root of n 093 094 if(rp != rn) { // p and n have different roots 095 if (rp.getLevel() == rn.getLevel() && rp.getHeight() < rn.getHeight()) { 096 // n's root becomes the parent of p's root 097 join(rp, rn); 098 r = rn; 099 } else { 100 // rp.val > rn.val, p' root becomes the parent of n's root 101 join(rn, rp); 102 r = rp; 103 } 104 } 105 } 106 //else: the neighbor is in no forest, i.e. unprocessed so we don't care 107 n = p.getNextNeighbor(); 108 } 109 } 110 111 return r; 112 } 113 114 /** 115 * Joins the disjoint trees with root nodes r1 and r2. Makes the tree rooted at r1 a sub-tree under root r2, i.e., 116 * r1 becomes a child node of r2. Node r2 is the root of the joined tree. 117 * 118 * @param r1 the root of the first (child) sub-tree 119 * @param r2 the root of the second (master) sub-tree 120 */ 121 private void join(Component<T> r1, Component<T> r2) { 122 r1.setParent(r2); 123 r2.addChild(r1); 124 r2.addToSize(r1.getSize()); 125 r2.setHeight(Math.max(r2.getHeight(), r1.getHeight() + 1)); 126 } 127 128 // ---------------------------------------------------------------- 129 130 /** 131 * Builds the tree starting at the {@link #root} component. 132 */ 133 private void buildTree() { 134 // Find all extremal regions and connect them: 135 linkExtremalComponents(root, root); // fills components 136 //components.addAll(linkExtremalComponents2(root, root)); 137 138 // Reduce the remaining (non-extremal) components 139 // into the associated (ancestor) extremal components: 140 for (Component<T> c : components) { 141 reduceNonExtremalComponents(c); 142 } 143 } 144 145 // ----------------------------------------------------------------- 146 147 /** 148 * Recursively links extremal components by omitting intermediate non-extremal components. Initially applied to the 149 * root component. Collects extremal regions into {@link #components}. 150 * 151 * @param c the current component (to be inspected) 152 * @param e the closest extremal component on the ancestor path 153 */ 154 private void linkExtremalComponents(Component<T> c, Component<T> e) { 155 if (c.isExtremal()) { 156 components.add(c); 157 //System.out.println(" adding " + c.toString() + " extremalRegions.size()=" + extremalRegions.size()); 158 if (c != e) { 159 c.setParent(e); 160 e.addChild(c); // children is a HashSet, i.e., no duplicate entries! 161 } 162 e = c; 163 } 164 // do the same for all children 165 for (Component<T> child : new ArrayList<>(c.getChildren())) {// copy needed since recursive call may change the child list 166 linkExtremalComponents(child, e); 167 } 168 } 169 170 // Version 2: returns a set of extremal components (book version) 171 @SuppressWarnings("unused") 172 private Collection<Component<T>> linkExtremalComponents2(Component<T> c, Component<T> e) { 173 Collection<Component<T>> E = new LinkedList<>(); 174 if (c.isExtremal()) { 175 E.add(c); 176 //System.out.println(" adding " + c.toString() + " extremalRegions.size()=" + extremalRegions.size()); 177 if (c != e) { 178 c.setParent(e); 179 e.addChild(c); // children is a HashSet, i.e., no duplicate entries! 180 } 181 e = c; 182 } 183 // do the same for all children 184 for (Component<T> child : new ArrayList<>(c.getChildren())) {// copy needed since recursive call may change the child list 185 E.addAll(linkExtremalComponents2(child, e)); 186 } 187 return E; 188 } 189 190 /** 191 * Eliminates all non-extremal components attached to the given component. Initially invoked on an extremal 192 * component. All local pixels from a non-extremal child components are collected and merged to the parent 193 * component. 194 * 195 * @param c an extremal component 196 */ 197 private void reduceNonExtremalComponents(Component<T> c) { 198 if (!c.getChildren().isEmpty()) { 199 // visit each child and (if not extremal) collect all its points into c 200 Iterator<Component<T>> iter = c.getChildren().iterator(); 201 while (iter.hasNext()) { 202 Component<T> cc = iter.next(); 203 if (!cc.isExtremal()) { 204 reduceNonExtremalComponents(cc); // recursive call 205 c.getLocalPixels().addAll(cc.getLocalPixels()); 206 cc.getLocalPixels().clear(); 207 iter.remove(); // remove child from c's children 208 } 209 } 210 } 211 } 212 213 // ------------------------------------------------------------------------------------- 214 215 /** 216 * This nested class represents a 2D container for elements of type {@link Component}. The array is of the same size 217 * as the image, with one component for every image pixel. The array is initially empty, i.e. contains only 218 * {@code null} values. Components are created on demand (by {@link #makeComponent(Pixel)} during building of the 219 * component tree. The method {@link #getComponent(Pixel)} is used to check if the component for a specific image 220 * point exists. 221 * 222 * @param <T> the type of data that may be attached to components (e.g., {@link MserData}) 223 */ 224 private static class ComponentMap<T> implements Iterable<Component<T>> { 225 226 private final int width, height; 227 private final Object[] compArr; 228 229 public ComponentMap(int width, int height) { 230 this.width = width; 231 this.height = height; 232 this.compArr = new Object[this.width * this.height]; 233 } 234 235 /** 236 * Creates and returns a new component for the specified image point. An exception is thrown if a component 237 * already exists for this point. 238 * 239 * @param p the image point 240 * @return the new component 241 */ 242 public Component<T> makeComponent(Pixel p) { 243 int idx = width * p.y + p.x; // unique component index 244 if (compArr[idx] != null) { 245 throw new RuntimeException("component already exists for point " + ((PntInt)p).toString()); 246 } 247 Component<T> c = new Component<>(p.val, idx); 248 c.addPoint(p); 249 compArr[idx] = c; 250 return c; 251 } 252 253 /** 254 * Returns the component for the specified image point or {@code null} if it does not exist. 255 * 256 * @param p the image point 257 * @return the associated component or {@code null} 258 */ 259 @SuppressWarnings("unchecked") 260 public Component<T> getComponent(Pixel p) { 261 return (Component<T>) compArr[p.y * width + p.x]; 262 } 263 264 /** 265 * Iterator to loop over all {@link Component} elements of this {@link ComponentMap}. Note that this iterator 266 * may return null elements! 267 */ 268 @Override 269 public Iterator<Component<T>> iterator() { 270 return new Iterator<Component<T>>() { 271 private int pos = 0; 272 273 @Override 274 public boolean hasNext() { 275 return pos < compArr.length; 276 } 277 278 @Override 279 public Component<T> next() { 280 @SuppressWarnings("unchecked") 281 Component<T> c = (Component<T>) compArr[pos]; 282 pos++; 283 return c; 284 } 285 }; 286 } 287 288 } 289 290}