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 ******************************************************************************/ 009 010package imagingbook.common.regions; 011 012import ij.process.ByteProcessor; 013import imagingbook.common.geometry.basic.NeighborhoodType2D; 014 015import java.util.HashSet; 016 017import static imagingbook.common.geometry.basic.NeighborhoodType2D.N4; 018 019/** 020 * <p> 021 * Binary region segmentation based on a two-pass sequential labeling algorithm. See Sec. 8.1.2 (Alg. 8.3) of [1] for 022 * additional details. 023 * </p> 024 * <p> 025 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing – An Algorithmic Introduction</em>, 3rd ed, Springer 026 * (2022). 027 * </p> 028 * 029 * @author WB 030 * @version 2022/09/28 revised 031 */ 032public class SequentialSegmentation extends BinaryRegionSegmentation { 033 034 private HashSet<LabelCollision> collisions; 035 036 /** 037 * Constructor. Creates a new region segmentation from the specified image, which is not modified. The input image 038 * is considered binary, with 0 values for background pixels and values ≠ 0 for foreground pixels. The 039 * 4-neighborhood is used by default ({@link BinaryRegionSegmentation#DefaultNeighborhoodT}). 040 * 041 * @param ip the binary input image to be segmented 042 */ 043 public SequentialSegmentation(ByteProcessor ip) { 044 this(ip, DefaultNeighborhoodT); 045 } 046 047 /** 048 * Constructor. Creates a new region segmentation from the specified image and neighborhood type (4- or 049 * 8-neighborhood). The input image is considered binary, with 0 values for background pixels and values ≠ 0 for 050 * foreground pixels. 051 * 052 * @param ip the binary input image to be segmented 053 * @param nh the neighborhood type (4- or 8-neighborhood) 054 */ 055 public SequentialSegmentation(ByteProcessor ip, NeighborhoodType2D nh) { 056 super(ip, nh); 057 } 058 059 @Override 060 boolean applySegmentation(ByteProcessor ip) { 061 collisions = new HashSet<>(); 062 int[] nh = null; 063 064 // Step 1: assign initial labels: 065 for (int v = 0; v < height; v++) { 066 for (int u = 0; u < width; u++) { 067 if (getLabel(u, v) == Foreground) { 068 nh = getNeighborhood(nh, u, v); 069 int a = max(nh); 070 if (!isRegionLabel(a)) { // a = 0 or 1, i.e., (u,v) is isolated and not connected to any labeled pixel 071 setLabel(u, v, getNextLabel()); // new region with a new label 072 } 073 else { // at least one label in nh[] is an assigned label 074 setLabel(u, v, a); // connect to the existing region with the largest label among neighbors 075 for (int b : nh) { // register label collisions between a and all b 076 if (isRegionLabel(b) && a != b) { 077 registerCollision(a, b); // we know that a <= b 078 } 079 } 080 } 081 } 082 } 083 } 084 085 int[] replacementTable = resolveCollisions(); // Step 2: resolve label collisions 086 relabelImage(replacementTable); // Step 3: relabel the image 087 return true; 088 } 089 090 private int[] getNeighborhood(int[] nh, int u, int v) { 091 if (nh == null) { 092 nh = new int[(NT == N4) ? 4 : 8]; 093 } 094 //assemble the neighborhood nh (x is current position u,v): 095 // 4-neighborhood: 096 // [1] 097 // [0][x] 098 // 8-neighborhood: 099 // [1][2][3] 100 // [0][x] 101 if (NT == N4) { 102 nh[0] = getLabel(u - 1, v); 103 nh[1] = getLabel(u, v - 1); 104 } 105 else { // neighborhood == NeighborhoodType.N8 106 nh[0] = getLabel(u - 1, v); 107 nh[1] = getLabel(u - 1, v - 1); 108 nh[2] = getLabel(u, v - 1); 109 nh[3] = getLabel(u + 1, v - 1); 110 } 111 return nh; 112 } 113 114 private int max(int[] nh) { 115 int nMax = Integer.MIN_VALUE; 116 for (int n : nh) { 117 if (n > nMax) { 118 nMax = n; 119 } 120 } 121 return nMax; 122 } 123 124 private void registerCollision(int a, int b) { 125 if (a != b) { 126 LabelCollision c = (a < b) ? new LabelCollision(a, b) : new LabelCollision(b, a); 127 //if (!collisionMap.contains(c)) // not needed, add() does check for existing instance 128 collisions.add(c); 129 } 130 } 131 132 //--------------------------------------------------------------------------- 133 134 /** 135 * This is the core of the algorithm: The set of collisions (stored in map) is used to merge connected regions. 136 * Transitivity of collisions makes this a nontrivial task. The algorithm used here is a basic "Connected-Components 137 * Algorithm" as used for finding connected parts in undirected graphs (e.g. see Corman, Leiserson, Rivest: 138 * "Introduction to Algorithms", MIT Press, 1995, p. 441). Here, the regions represent the nodes of the graph and 139 * the collisions are equivalent to the edges of the graph. The implementation is not particularly efficient, since 140 * the merging of sets is done by relabeling the entire replacement table for each pair of nodes. Still fast enough 141 * even for large and complex images. 142 * 143 * @return replacement table 144 */ 145 private int[] resolveCollisions() { 146 final int N = getMaxLabel() + 1; 147 // R[k] is the index of the set in which element k is contained: 148 int[] R = new int[N]; 149 150 // Initially, each element i is in its own (one-element) set: 151 for (int i = 0; i < N; i++) { 152 R[i] = i; 153 } 154 155 // Inspect all collisions <a,b> one by one (note that a < b): 156 for (LabelCollision c : collisions) { 157 int A = R[c.a]; // set Ra contains label a 158 int B = R[c.b]; // set Rb contains label b 159 // Merge sets Ra and Rb (unless they are the same) by 160 // moving all elements of set Rb into set Ra: 161 if (A != B) { // a,b are in different sets 162 for (int i = 0; i < N; i++) { 163 if (R[i] == B) { 164 R[i] = A; 165 } 166 } 167 } 168 // otherwise a,b are already in the same set (i.e., known to be equivalent) 169 } 170 171 cleanup(R); 172 return R; 173 } 174 175 private void cleanup(int[] table) { 176 if (table.length <= getMinLabel()) { // case of empty image, nothing to clean 177 //return table; 178 return; 179 } 180 // Assume the replacement table looks the following: 181 // table = [0 1 4 4 4 6 6 8 3 3 ] 182 // i = 0 1 2 3 4 5 6 7 8 9 183 // meaning that label 2 should be replaced by 4 etc. 184 185 // First, we figure out which of the original labels 186 // are still used. For this we use an intermediate array "mark": 187 int[] mark = new int[table.length]; // initialized to 0 188 for (int i = 0; i < table.length; i++) { 189 int k = table[i]; 190 if (k < 0 || k >= table.length) { 191 throw new RuntimeException("illegal segmentation label: " + k); 192 } 193 mark[k] = 1; // mark label k as being used 194 } 195 // Result: 196 // mark = [1 1 0 1 1 0 1 0 1 0 ] 197 // i = 0 1 2 3 4 5 6 7 8 9 198 199 // Now we assign new, contiguous labels in mark array: 200 int newLabel = getMinLabel(); 201 for (int i = 0; i < getMinLabel(); i++) { 202 mark[i] = i; // keep labels 0,..., minLabel-1 203 } 204 for (int i = getMinLabel(); i < table.length; i++) { 205 if (mark[i] > 0) { // this one's marked 206 mark[i] = newLabel; 207 newLabel = newLabel + 1; 208 } 209 } 210 // Result: 211 // mark = [0 1 0 2 3 0 4 0 5 0 ] 212 // i = 0 1 2 3 4 5 6 7 8 9 213 214 // Update the actual replacement table to reflect the new labels: 215 for (int i = 0; i < table.length; i++) { 216 table[i] = mark[table[i]]; 217 } 218 // table = [0 1 4 4 4 6 6 8 3 3 ] 219 // | | 220 // V V 221 // table = [0 1 3 3 3 4 4 5 2 2 ] 222 // i = 0 1 2 3 4 5 6 7 8 9 223 224 //return table; 225 } 226 227 // Replace image labels in labelArray 228 private void relabelImage(int[] replacementTable){ 229 for (int v = 0; v < height; v++) { 230 for (int u = 0; u < width; u++) { 231 int oldLb = getLabel(u, v); 232 setLabel(u, v, replacementTable[oldLb]); 233 } 234 } 235 } 236 237 /** 238 * This class represents a collision between two pixel labels a, b 239 */ 240 private class LabelCollision { 241 private final int a, b; 242 243 LabelCollision(int a, int b) { 244 this.a = a; 245 this.b = b; 246 } 247 248 @Override 249 public int hashCode() { 250 return (17 + a) * 37 + b; 251 } 252 253 @Override 254 public boolean equals(Object other) { 255 if (other instanceof LabelCollision) { 256 LabelCollision coll = (LabelCollision) other; 257 return (this.a == coll.a && this.b == coll.b); 258 } 259 else { 260 return false; 261 } 262 } 263 } 264 265} 266 267