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.connectedcomponent; 031 032import gnu.trove.map.hash.TIntIntHashMap; 033 034import java.util.ArrayList; 035import java.util.HashMap; 036import java.util.LinkedHashSet; 037import java.util.List; 038import java.util.Map; 039 040import org.openimaj.image.FImage; 041import org.openimaj.image.analyser.ImageAnalyser; 042import org.openimaj.image.pixel.ConnectedComponent; 043import org.openimaj.image.pixel.ConnectedComponent.ConnectMode; 044import org.openimaj.image.pixel.Pixel; 045 046/** 047 * A connected component labeler. 048 * 049 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 050 */ 051public class ConnectedComponentLabeler implements ImageAnalyser<FImage> { 052 /** 053 * Different algorithms for finding {@link ConnectedComponent}s. 054 * 055 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 056 */ 057 public enum Algorithm { 058 /** 059 * A single-pass algorithm 060 * 061 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 062 * 063 */ 064 SINGLE_PASS { 065 @Override 066 public List<ConnectedComponent> findComponents(FImage image, float bgThreshold, ConnectMode mode) { 067 final List<ConnectedComponent> components = new ArrayList<ConnectedComponent>(); 068 069 // Single pass method inspired by the wikipedia two-pass 070 // technique 071 // http://en.wikipedia.org/wiki/Connected_component_labeling 072 for (int y = 0; y < image.height; y++) { 073 for (int x = 0; x < image.width; x++) { 074 final float element = image.pixels[y][x]; 075 076 if (element > bgThreshold) { 077 final List<Pixel> neighbours = mode.getNeighbours(image, x, y, bgThreshold); 078 079 ConnectedComponent currentComponent = null; 080 for (final Pixel p : neighbours) { 081 final ConnectedComponent cc = searchPixel(p, components); 082 if (cc != null) { 083 if (currentComponent == null) { 084 currentComponent = cc; 085 } else if (currentComponent != cc) { 086 currentComponent.merge(cc); 087 components.remove(cc); 088 } 089 } 090 } 091 092 if (currentComponent == null) { 093 currentComponent = new ConnectedComponent(); 094 components.add(currentComponent); 095 } 096 097 currentComponent.addPixel(x, y); 098 } 099 } 100 } 101 102 return components; 103 } 104 105 private ConnectedComponent searchPixel(Pixel p, List<ConnectedComponent> components) { 106 for (final ConnectedComponent c : components) { 107 if (c.find(p)) 108 return c; 109 } 110 return null; 111 } 112 }, 113 /** 114 * The standard two-pass algorithm. 115 * 116 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 117 */ 118 TWO_PASS { 119 @Override 120 public List<ConnectedComponent> findComponents(FImage image, float bgThreshold, ConnectMode mode) { 121 final List<ConnectedComponent> components = new ArrayList<ConnectedComponent>(); 122 final TIntIntHashMap linked = new TIntIntHashMap(); 123 final int[][] labels = new int[image.height][image.width]; 124 int nextLabel = 1; 125 126 // first pass 127 for (int y = 0; y < image.height; y++) { 128 for (int x = 0; x < image.width; x++) { 129 final float element = image.pixels[y][x]; 130 131 if (element > bgThreshold) { 132 final List<Pixel> neighbours = mode.getNeighbours(image, x, y, bgThreshold); 133 final List<Integer> L = new ArrayList<Integer>(); 134 135 for (final Pixel p : neighbours) 136 if (labels[p.y][p.x] != 0) 137 L.add(labels[p.y][p.x]); 138 139 if (L.size() == 0) { 140 linked.put(nextLabel, nextLabel); 141 labels[y][x] = nextLabel; 142 nextLabel++; 143 } else { 144 int min = Integer.MAX_VALUE; 145 for (final int i : L) 146 if (i < min) 147 min = i; 148 labels[y][x] = min; 149 150 for (final int i : L) { 151 merge(linked, i, min); 152 } 153 } 154 } 155 } 156 } 157 158 // second pass 159 final Map<Integer, ConnectedComponent> comp = new HashMap<Integer, ConnectedComponent>(); 160 161 for (int i = 1; i <= linked.size(); i++) { 162 int min = linked.get(i); 163 164 while (true) { 165 final int m = linked.get(min); 166 167 if (m == min) 168 break; 169 else 170 min = m; 171 } 172 linked.put(i, min); 173 } 174 175 for (int y = 0; y < image.height; y++) { 176 for (int x = 0; x < image.width; x++) { 177 if (labels[y][x] != 0) { 178 final int min = linked.get(labels[y][x]); 179 // labels[r][c] = min; //not needed 180 181 if (comp.containsKey(min)) { 182 comp.get(min).addPixel(x, y); 183 } else { 184 final ConnectedComponent cc = new ConnectedComponent(); 185 cc.addPixel(x, y); 186 comp.put(min, cc); 187 } 188 } 189 } 190 } 191 components.addAll(comp.values()); 192 193 return components; 194 } 195 196 private void merge(TIntIntHashMap linked, int start, int target) { 197 if (start == target) 198 return; 199 200 final int old = linked.get(start); 201 202 if (old > target) { 203 linked.put(start, target); 204 merge(linked, old, target); 205 } else { 206 merge(linked, target, old); 207 } 208 } 209 }, 210 /** 211 * The flood-fill algorithm 212 * 213 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 214 */ 215 FLOOD_FILL { 216 @Override 217 public List<ConnectedComponent> findComponents(FImage image, float bgThreshold, ConnectMode mode) { 218 final List<ConnectedComponent> components = new ArrayList<ConnectedComponent>(); 219 final int[][] labels = new int[image.height][image.width]; 220 int nextColor = 1; 221 222 for (int y = 0; y < image.height; y++) { 223 for (int x = 0; x < image.width; x++) { 224 if (image.pixels[y][x] != 0 && labels[y][x] == 0) { 225 components.add(floodFill(image, new Pixel(x, y), labels, nextColor)); 226 nextColor++; 227 } 228 } 229 } 230 231 return components; 232 } 233 234 protected ConnectedComponent floodFill(FImage image, Pixel start, int[][] output, int color) { 235 final ConnectedComponent cc = new ConnectedComponent(); 236 // Flood-fill (node, target-color, replacement-color): 237 // 1. Set Q to the empty queue. 238 // Queue<Pixel> queue = new LinkedList<Pixel>(); 239 final LinkedHashSet<Pixel> queue = new LinkedHashSet<Pixel>(); 240 241 // 2. If the color of node is not equal to target-color, return. 242 if (image.pixels[start.y][start.x] == 0) 243 return cc; 244 245 // 3. Add node to Q. 246 queue.add(start); 247 248 // 4. For each element n of Q: 249 while (queue.size() > 0) { 250 // Pixel n = queue.poll(); 251 final Pixel n = queue.iterator().next(); 252 queue.remove(n); 253 254 // 5. If the color of n is equal to target-color: 255 if (image.pixels[n.y][n.x] != 0 && output[n.y][n.x] != color) { 256 // 6. Set w and e equal to n. 257 int e = n.x, w = n.x; 258 // 7. Move w to the west until the color of the node to 259 // the west of w no longer matches target-color. 260 while (w > 0 && image.pixels[n.y][w - 1] != 0) 261 w--; 262 263 // 8. Move e to the east until the color of the node to 264 // the east of e no longer matches target-color. 265 while (e < image.width - 1 && image.pixels[n.y][e + 1] != 0) 266 e++; 267 268 // 9. Set the color of nodes between w and e to 269 // replacement-color. 270 for (int i = w; i <= e; i++) { 271 output[n.y][i] = color; 272 cc.addPixel(i, n.y); 273 274 // 10. For each node n between w and e: 275 final int north = n.y - 1; 276 final int south = n.y + 1; 277 // 11. If the color of the node to the north of n is 278 // target-color, add that node to Q. 279 if (north >= 0 && image.pixels[north][i] != 0 && output[north][i] != color) 280 queue.add(new Pixel(i, north)); 281 // If the color of the node to the south of n is 282 // target-color, add that node to Q. 283 if (south < image.height && image.pixels[south][i] != 0 && output[south][i] != color) 284 queue.add(new Pixel(i, south)); 285 } 286 // 12. Continue looping until Q is exhausted. 287 } 288 } 289 // 13. Return. 290 return cc; 291 } 292 }; 293 294 /** 295 * Find the connected components in an image. 296 * 297 * @param image 298 * the image 299 * @param bgThreshold 300 * the threshold below which pixels should be considered to 301 * be background 302 * @param mode 303 * the {@link ConnectMode}. 304 * @return the connected components 305 */ 306 public abstract List<ConnectedComponent> findComponents(FImage image, float bgThreshold, ConnectMode mode); 307 } 308 309 protected float bgThreshold = 0; 310 protected Algorithm algorithm = Algorithm.TWO_PASS; 311 protected ConnectMode mode; 312 protected List<ConnectedComponent> components; 313 314 /** 315 * Construct using the default (two-pass) algorithm, background pixels 316 * having a value of 0 or less, and the given {@link ConnectMode}. 317 * 318 * @param mode 319 * the connection mode. 320 */ 321 public ConnectedComponentLabeler(ConnectMode mode) { 322 this.mode = mode; 323 } 324 325 /** 326 * Construct using the given algorithm, background pixels having a value of 327 * 0 or less, and the given {@link ConnectMode}. 328 * 329 * @param algorithm 330 * the algorithm to use 331 * @param mode 332 * the connection mode. 333 */ 334 public ConnectedComponentLabeler(Algorithm algorithm, ConnectMode mode) { 335 this.algorithm = algorithm; 336 this.mode = mode; 337 } 338 339 /** 340 * Construct using the given algorithm, background pixel threshold, and the 341 * given {@link ConnectMode}. 342 * 343 * @param algorithm 344 * the algorithm to use 345 * @param bgThreshold 346 * threshold at which pixels with lower values are considered to 347 * be the background 348 * @param mode 349 * the connection mode. 350 */ 351 public ConnectedComponentLabeler(Algorithm algorithm, float bgThreshold, ConnectMode mode) { 352 this.algorithm = algorithm; 353 this.bgThreshold = bgThreshold; 354 this.mode = mode; 355 } 356 357 /** 358 * Syntactic sugar for calling {@link #analyseImage(FImage)} followed by 359 * {@link #getComponents()}; 360 * 361 * @param image 362 * the image to extract components from 363 * @return the extracted components. 364 */ 365 public List<ConnectedComponent> findComponents(FImage image) { 366 analyseImage(image); 367 return components; 368 } 369 370 @Override 371 public void analyseImage(FImage image) { 372 components = algorithm.findComponents(image, bgThreshold, mode); 373 } 374 375 /** 376 * @return the list of components found in the last call to 377 * {@link #analyseImage(FImage)}. 378 */ 379 public List<ConnectedComponent> getComponents() { 380 return components; 381 } 382}