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-2016 Wilhelm Burger, Mark J. Burge. All rights reserved. 007 * Visit http://imagingbook.com for additional details. 008 *******************************************************************************/ 009 010package imagingbook.pub.regions; 011 012import ij.IJ; 013import ij.process.ByteProcessor; 014 015import java.util.HashMap; 016import java.util.Map; 017 018/** 019 * Binary region labeler based on a sequential labeling 020 * algorithm. 021 * 022 * @author WB 023 * @version 2016-11-08 024 */ 025public class SequentialLabeling extends RegionLabeling { 026 027 private Map<LabelCollision,LabelCollision> collisionMap = null; 028 029 /** 030 * Creates a new region labeling. 031 * 032 * @param ip the binary input image with 0 values for background pixels and values > 0 033 * for foreground pixels. 034 */ 035 public SequentialLabeling(ByteProcessor ip) { 036 super(ip); 037 } 038 039 @Override 040 void applyLabeling() { 041 if (IJ.debugMode) IJ.log("Sequential region labeling - Step 1"); 042 collisionMap = new HashMap<LabelCollision,LabelCollision>(1000); 043 044 // Step 1: assign initial labels: 045 resetLabel(); 046 for (int v = 0; v < height; v++) { 047 for (int u = 0; u < width; u++) { 048 if (getLabel(u, v) >= START_LABEL) { 049 setLabel(u, v, makeLabel(u, v)); 050 } 051 } 052 } 053 054 // Step 2: resolve label collisions 055 if (IJ.debugMode) IJ.log("Sequential region labeling - Step 2"); 056 int[] replacementTable = makeReplacementTable(getMaxLabel() + 1); 057 058 // Step 3: relabel the image 059 applyReplacementTable(replacementTable); 060 //showLabelArray(); 061 } 062 063 private int makeLabel(int u, int v) { 064 int newLabel = 0; 065 //assemble the neighborhood n: 066 // 067 // [1][2][3] 068 // [0][x] 069 // 070 int[] n = new int[4]; 071 n[0] = getLabel(u-1, v); 072 //gives 0 if no label is set or outside borders 073 n[1] = getLabel(u-1, v-1); 074 n[2] = getLabel(u, v-1); 075 n[3] = getLabel(u+1, v-1); 076 077 if ( n[0] == BACKGROUND 078 && n[1] == BACKGROUND 079 && n[2] == BACKGROUND 080 && n[3] == BACKGROUND) { 081 //all neighbors in n[] are empty, assign a new label: 082 newLabel = this.getNextLabel(); 083 } 084 else { //at least one label in n[] is not BACKGROUND 085 //find minimum region label among neighbors 086 int min = Integer.MAX_VALUE; 087 for (int i = 0; i < 4; i++) { 088 int ni = n[i]; 089 if (ni >= START_LABEL && ni < min) 090 min = ni; 091 } 092 newLabel = min; 093 094 //register label equivalence (collision) 095 for (int i = 0; i < 4; i++) { 096 int ni = n[i]; 097 if (ni >= START_LABEL && ni != newLabel) { 098 registerCollision(ni, newLabel); 099 } 100 } 101 } 102 return newLabel; 103 } 104 105 private void registerCollision(int a, int b) { 106 if (collisionMap == null){ 107 throw new Error("registerCollision(): no collission map!"); 108 } 109 if (a != b) { 110 LabelCollision c; 111 if (a < b) 112 c = new LabelCollision(a, b); 113 else 114 c = new LabelCollision(b, a); 115 if (!collisionMap.containsKey(c)) 116 collisionMap.put(c, c); 117 } 118 } 119 120// private void listCollisions() { 121// IJ.log("Listing collisions********* " + collisionMap.size()); 122// for (LabelCollision c: collisionMap.keySet()) { 123// IJ.log(" ---next----" + c.a + "/" + c.b + "=" + c); 124// } 125// } 126 127 //--------------------------------------------------------------------------- 128 129 private int[] makeReplacementTable(int size) { 130 int[] rTable = resolveCollisions(size); 131 return cleanupReplacementTable(rTable); 132 } 133 134 /** 135 * This is the core of the algorithm: The set of collisions (stored in map) 136 * is used to merge connected regions. Transitivity of collisions makes this 137 * a nontrivial task. The algorithm used here is a basic "Connected-Components 138 * Algorithm" as used for finding connected parts in undirected graphs 139 * (e.g. see Corman, Leiserson, Rivest: "Introduction to Algorithms", MIT Press, 140 * 1995, p. 441). Here, the regions represent the nodes of the graph and the 141 * collisions are equivalent to the edges of the graph. The implementation is 142 * not particularly efficient, since the merging of sets is done by relabeling 143 * the entire replacement table for each pair of nodes. Still fast enough even 144 * for large and complex images. 145 * 146 * @param size size of the label set 147 * @return replacement table 148 */ 149 private int[] resolveCollisions(int size) { 150 151 // The table setNumber[i] indicates to which set the element i belongs: 152 // k == setNumber[e] means that e is in set k 153 int[] setNumber = new int[size]; 154 155 //Initially, we assign a separate set to each element e: 156 for (int e = 0; e < size; e++) { 157 setNumber[e] = e; 158 } 159 160 // Inspect all collisions c=(a,b) one by one [note that a<b] 161 for (LabelCollision c: collisionMap.keySet()) { 162 int A = setNumber[c.a]; //element a is currently in set A 163 int B = setNumber[c.b]; //element b is currently in set B 164 //Merge sets A and B (unless they are the same) by 165 //moving all elements of set B into set A 166 if (A != B) { 167 for (int i = 0; i < size; i++) { 168 if (setNumber[i] == B) 169 setNumber[i] = A; 170 } 171 } 172 } 173 return setNumber; 174 } 175 176 private int[] cleanupReplacementTable(int[] table) { 177 if (table.length == 0) return table; // case of empty image 178 // Assume the replacement table looks the following: 179 // table = [0 1 4 4 4 6 6 8 3 3 ] 180 // i = 0 1 2 3 4 5 6 7 8 9 181 // meaning that label 2 should be replaced by 4 etc. 182 183 // First, figure out which of the original labels 184 // are still used. For this we use an intermediate array "mark": 185 int[] mark = new int[table.length]; 186 for (int i = 0; i < table.length; i++) { 187 int k = table[i]; 188 if (k >= 0 && k < table.length) 189 mark[k] = 1; 190 } 191 // Result: 192 // mark = [1 1 0 1 1 0 1 0 1 0 ] 193 // i = 0 1 2 3 4 5 6 7 8 9 194 195 // Now we assign new, contiguous labels in mark: 196 int newLabel = START_LABEL; 197 mark[BACKGROUND] = BACKGROUND; 198 mark[FOREGROUND] = FOREGROUND; 199 for (int i = START_LABEL; i < table.length; i++) { 200 if (mark[i]>0) { 201 mark[i] = newLabel; 202 newLabel = newLabel + 1; 203 } 204 } 205 // Result: 206 // mark = [0 1 0 2 3 0 4 0 5 0 ] 207 // i = 0 1 2 3 4 5 6 7 8 9 208 209 //Now modify the actual replacement table to reflect the new labels 210 for (int i = 0; i < table.length; i++) { 211 table[i] = mark[table[i]]; 212 } 213 // table = [0 1 4 4 4 6 6 8 3 3 ] 214 // | | 215 // V V 216 // table = [0 1 3 3 3 4 4 5 2 2 ] 217 // i = 0 1 2 3 4 5 6 7 8 9 218 219 return table; 220 } 221 222 private void applyReplacementTable(int[] replacementTable){ 223 if (replacementTable != null && replacementTable.length > 0){ 224 for (int v = 0; v < height; v++) { 225 for (int u = 0; u < width; u++) { 226 int oldLb = getLabel(u, v); 227 if (oldLb >= START_LABEL && oldLb < replacementTable.length){ 228 setLabel(u, v, replacementTable[oldLb]); 229 } 230 } 231 } 232 } 233 } 234 235 /** 236 * This class represents a collision between two pixel labels a, b 237 */ 238 private class LabelCollision { 239 private final int a, b; 240 241 LabelCollision(int label_a, int label_b) { 242 a = label_a; 243 b = label_b; 244 } 245 246 // This is important because hashCode determines how keys in the hashtable are 247 // compared. It makes sure that the key is directly related to the values of a,b. 248 // Otherwise the key would be derived from the address of the Collision object. 249 public int hashCode() { 250 return a * b; 251 } 252 253 public boolean equals(Object obj) { 254 if (obj instanceof LabelCollision) { 255 LabelCollision c = (LabelCollision) obj; 256 return (this.a == c.a && this.b == c.b); 257 } else 258 return false; 259 } 260 } 261 262} 263 264