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.morphology; 010 011import ij.process.ByteProcessor; 012import imagingbook.common.geometry.basic.Pnt2d.PntInt; 013 014import java.util.ArrayList; 015import java.util.List; 016 017/** 018 * <p> 019 * Implements a binary morphological thinning or "skeletonization" operation, based on the algorithm by Zhang and Suen 020 * [1]. See Sec. 7.4 (Alg. 7.2-7.3) of [2] for additional details. 021 * </p> 022 * <p> 023 * [1] T. Y. Zhang and C. Y. Suen. A fast parallel algorithm for thinning digital patterns. Communications of the ACM 024 * 27(3), 236–239 (1984). <br> [2] W. Burger, M.J. Burge, <em>Digital Image Processing – An Algorithmic 025 * Introduction</em>, 3rd ed, Springer (2022). 026 * </p> 027 * 028 * @author WB 029 * @version 2022/09/18 030 */ 031public class BinaryThinning implements BinaryMorphologyOperator { 032 033 private static final byte B0 = (byte) 0; 034 private static final byte B1 = (byte) 1; 035 private static final boolean T = true; 036 private static final boolean F = false; 037 038 private static final boolean[][] Q = { // = Q[c][pass] 039 {F, F}, // 0 040 {F, F}, // 1 041 {F, F}, // 2 042 {T, T}, // 3 043 {F, F}, // 4 044 {F, F}, // 5 045 {T, T}, // 6 046 {T, T}, // 7 047 {F, F}, // 8 048 {F, F}, // 9 049 {F, F}, // 10 050 {F, F}, // 11 051 {T, T}, // 12 052 {F, F}, // 13 053 {T, T}, // 14 054 {T, T}, // 15 055 {F, F}, // 16 056 {F, F}, // 17 057 {F, F}, // 18 058 {F, F}, // 19 059 {F, F}, // 20 060 {F, F}, // 21 061 {F, F}, // 22 062 {F, F}, // 23 063 {T, T}, // 24 064 {F, F}, // 25 065 {F, F}, // 26 066 {F, F}, // 27 067 {T, T}, // 28 068 {F, F}, // 29 069 {T, T}, // 30 070 {T, F}, // 31 071 {F, F}, // 32 072 {F, F}, // 33 073 {F, F}, // 34 074 {F, F}, // 35 075 {F, F}, // 36 076 {F, F}, // 37 077 {F, F}, // 38 078 {F, F}, // 39 079 {F, F}, // 40 080 {F, F}, // 41 081 {F, F}, // 42 082 {F, F}, // 43 083 {F, F}, // 44 084 {F, F}, // 45 085 {F, F}, // 46 086 {F, F}, // 47 087 {T, T}, // 48 088 {F, F}, // 49 089 {F, F}, // 50 090 {F, F}, // 51 091 {F, F}, // 52 092 {F, F}, // 53 093 {F, F}, // 54 094 {F, F}, // 55 095 {T, T}, // 56 096 {F, F}, // 57 097 {F, F}, // 58 098 {F, F}, // 59 099 {T, T}, // 60 100 {F, F}, // 61 101 {T, T}, // 62 102 {T, F}, // 63 103 {F, F}, // 64 104 {F, F}, // 65 105 {F, F}, // 66 106 {F, F}, // 67 107 {F, F}, // 68 108 {F, F}, // 69 109 {F, F}, // 70 110 {F, F}, // 71 111 {F, F}, // 72 112 {F, F}, // 73 113 {F, F}, // 74 114 {F, F}, // 75 115 {F, F}, // 76 116 {F, F}, // 77 117 {F, F}, // 78 118 {F, F}, // 79 119 {F, F}, // 80 120 {F, F}, // 81 121 {F, F}, // 82 122 {F, F}, // 83 123 {F, F}, // 84 124 {F, F}, // 85 125 {F, F}, // 86 126 {F, F}, // 87 127 {F, F}, // 88 128 {F, F}, // 89 129 {F, F}, // 90 130 {F, F}, // 91 131 {F, F}, // 92 132 {F, F}, // 93 133 {F, F}, // 94 134 {F, F}, // 95 135 {T, T}, // 96 136 {F, F}, // 97 137 {F, F}, // 98 138 {F, F}, // 99 139 {F, F}, // 100 140 {F, F}, // 101 141 {F, F}, // 102 142 {F, F}, // 103 143 {F, F}, // 104 144 {F, F}, // 105 145 {F, F}, // 106 146 {F, F}, // 107 147 {F, F}, // 108 148 {F, F}, // 109 149 {F, F}, // 110 150 {F, F}, // 111 151 {T, T}, // 112 152 {F, F}, // 113 153 {F, F}, // 114 154 {F, F}, // 115 155 {F, F}, // 116 156 {F, F}, // 117 157 {F, F}, // 118 158 {F, F}, // 119 159 {T, T}, // 120 160 {F, F}, // 121 161 {F, F}, // 122 162 {F, F}, // 123 163 {T, F}, // 124 164 {F, F}, // 125 165 {T, F}, // 126 166 {F, F}, // 127 167 {F, F}, // 128 168 {T, T}, // 129 169 {F, F}, // 130 170 {T, T}, // 131 171 {F, F}, // 132 172 {F, F}, // 133 173 {F, F}, // 134 174 {T, T}, // 135 175 {F, F}, // 136 176 {F, F}, // 137 177 {F, F}, // 138 178 {F, F}, // 139 179 {F, F}, // 140 180 {F, F}, // 141 181 {F, F}, // 142 182 {T, T}, // 143 183 {F, F}, // 144 184 {F, F}, // 145 185 {F, F}, // 146 186 {F, F}, // 147 187 {F, F}, // 148 188 {F, F}, // 149 189 {F, F}, // 150 190 {F, F}, // 151 191 {F, F}, // 152 192 {F, F}, // 153 193 {F, F}, // 154 194 {F, F}, // 155 195 {F, F}, // 156 196 {F, F}, // 157 197 {F, F}, // 158 198 {T, F}, // 159 199 {F, F}, // 160 200 {F, F}, // 161 201 {F, F}, // 162 202 {F, F}, // 163 203 {F, F}, // 164 204 {F, F}, // 165 205 {F, F}, // 166 206 {F, F}, // 167 207 {F, F}, // 168 208 {F, F}, // 169 209 {F, F}, // 170 210 {F, F}, // 171 211 {F, F}, // 172 212 {F, F}, // 173 213 {F, F}, // 174 214 {F, F}, // 175 215 {F, F}, // 176 216 {F, F}, // 177 217 {F, F}, // 178 218 {F, F}, // 179 219 {F, F}, // 180 220 {F, F}, // 181 221 {F, F}, // 182 222 {F, F}, // 183 223 {F, F}, // 184 224 {F, F}, // 185 225 {F, F}, // 186 226 {F, F}, // 187 227 {F, F}, // 188 228 {F, F}, // 189 229 {F, F}, // 190 230 {F, F}, // 191 231 {T, T}, // 192 232 {T, T}, // 193 233 {F, F}, // 194 234 {T, T}, // 195 235 {F, F}, // 196 236 {F, F}, // 197 237 {F, F}, // 198 238 {F, T}, // 199 239 {F, F}, // 200 240 {F, F}, // 201 241 {F, F}, // 202 242 {F, F}, // 203 243 {F, F}, // 204 244 {F, F}, // 205 245 {F, F}, // 206 246 {F, T}, // 207 247 {F, F}, // 208 248 {F, F}, // 209 249 {F, F}, // 210 250 {F, F}, // 211 251 {F, F}, // 212 252 {F, F}, // 213 253 {F, F}, // 214 254 {F, F}, // 215 255 {F, F}, // 216 256 {F, F}, // 217 257 {F, F}, // 218 258 {F, F}, // 219 259 {F, F}, // 220 260 {F, F}, // 221 261 {F, F}, // 222 262 {F, F}, // 223 263 {T, T}, // 224 264 {T, T}, // 225 265 {F, F}, // 226 266 {T, T}, // 227 267 {F, F}, // 228 268 {F, F}, // 229 269 {F, F}, // 230 270 {F, T}, // 231 271 {F, F}, // 232 272 {F, F}, // 233 273 {F, F}, // 234 274 {F, F}, // 235 275 {F, F}, // 236 276 {F, F}, // 237 277 {F, F}, // 238 278 {F, F}, // 239 279 {T, T}, // 240 280 {F, T}, // 241 281 {F, F}, // 242 282 {F, T}, // 243 283 {F, F}, // 244 284 {F, F}, // 245 285 {F, F}, // 246 286 {F, F}, // 247 287 {T, T}, // 248 288 {F, T}, // 249 289 {F, F}, // 250 290 {F, F}, // 251 291 {T, F}, // 252 292 {F, F}, // 253 293 {F, F}, // 254 294 {F, F} // 255 295 }; 296 297 private final int maxIterations; // set to <=0 to calculate dynamically 298 299 private boolean complete; // flag indicating if thinning actually completed 300 private int iterations; // number of iterations performed during last applyTo() or reset() 301 302 /** 303 * Constructor, creates a {@link BinaryThinning} operator 304 * with the maximum number of iterations to be calculated dynamically 305 * from the size of the processed image. 306 */ 307 public BinaryThinning() { 308 this(0); 309 } 310 311 /** 312 * Constructor, creates a {@link BinaryThinning} operator 313 * with the specified maximum number of iterations. 314 * 315 * @param maxIterations the maximum number of iterations 316 */ 317 public BinaryThinning(int maxIterations) { 318 this.maxIterations = maxIterations; 319 } 320 321 // ---------------------------------------------------------------------------- 322 323 /** 324 * Returns the number of iterations performed since the last invocation of 325 * {@link #applyTo(ByteProcessor)} or {@link #reset()}. 326 * @return the number of iterations 327 */ 328 public int getIterations() { 329 if (iterations < 0) { 330 throw new IllegalStateException("no iteration count available, call applyTo() first"); 331 } 332 return iterations; 333 } 334 335 /** 336 * Returns {@code true} if thinning has successfully completed, 337 * {@code false} otherwise. 338 * 339 * @return {@code true} if successfully completed 340 */ 341 public boolean isComplete() { 342 return this.complete; 343 } 344 345 /** 346 * Resets the internal iteration counter and completion flag. 347 * Provided for debugging or animation only. 348 */ 349 public void reset() { 350 iterations = 0; 351 complete = false; 352 } 353 354 // ---------------------------------------------------------------------------- 355 356 @Override 357 public void applyTo(ByteProcessor bp) { 358 int iMax = (maxIterations > 0) ? 359 maxIterations : bp.getWidth() + bp.getHeight(); 360 reset(); 361 do { 362 int deletions = thinOnce(bp); 363 this.complete = (deletions == 0); 364 this.iterations++; 365 } while (!complete && iterations < iMax); 366 } 367 368 // ---------------------------------------------------------------------------- 369 370 // Single thinning iteration. Returns the number of deletions performed (for debugging only). 371 /** 372 * Performs a single thinning iteration and returns the number of pixel deletions. 373 * Updates the internal iteration counter and completion flag. 374 * This method is iteratively called by {@link #applyTo(ByteProcessor)}. 375 * It is public only for debugging and animation. 376 * 377 * @param bp the image to be thinned 378 * @return the number of pixel deletions 379 */ 380 public int thinOnce(ByteProcessor bp) { 381 final int M = bp.getWidth(); 382 final int N = bp.getHeight(); 383 final List<PntInt> D = new ArrayList<>(); 384// final byte[] NH = new byte[8]; 385 int n = 0; 386 for (int pass = 0; pass < 2; pass++) { // make 2 passes 387 D.clear(); 388 for (int u = 0; u < M; u++) { 389 for (int v = 0; v < N; v++) { 390 if (bp.get(u, v) > 0) { 391// get8Neighborhood(ip, u, v, NH); 392// int c = get8NeighborhoodIndex(NH); 393 int c = get8NeighborhoodIndex(bp, u, v); 394 if (Q[c][pass]) { 395 D.add(PntInt.from(u, v)); 396 n = n + 1; 397 } 398 } 399 } 400 } 401 for (PntInt p : D) { 402 bp.putPixel(p.x, p.y, 0); 403 } 404 } 405 return n; 406 } 407 408 @SuppressWarnings("unused") 409 private void get8Neighborhood(ByteProcessor I, int u, int v, byte[] NH) { 410 NH[0] = binarize(I.getPixel(u+1, v)); 411 NH[1] = binarize(I.getPixel(u+1, v-1)); 412 NH[2] = binarize(I.getPixel(u, v-1)); 413 NH[3] = binarize(I.getPixel(u-1, v-1)); 414 NH[4] = binarize(I.getPixel(u-1, v)); 415 NH[5] = binarize(I.getPixel(u-1, v+1)); 416 NH[6] = binarize(I.getPixel(u, v+1)); 417 NH[7] = binarize(I.getPixel(u+1, v+1)); 418 } 419 420 @SuppressWarnings("unused") 421 private int get8NeighborhoodIndex(byte[] NH) { 422// int c = 0; 423// for (int i = 0; i < 8; i++) { 424// if (NH[i] != 0) { 425// c = c | (1 << i); 426// } 427// } 428// return c; // c = 0,...,255 429 return NH[0] + NH[1] * 2 + NH[2] * 4 + NH[3] * 8 + NH[4] * 16 430 + NH[5] * 32 + NH[6] * 64 + NH[7] * 128; 431 } 432 433 // get neighborhood index directly, without extracting neighborhood vector itself: 434 private int get8NeighborhoodIndex(ByteProcessor I, int u, int v) { 435 int c = 0; 436 if (I.getPixel(u+1, v) != 0) c+= 1; // NH[0] 437 if (I.getPixel(u+1, v-1) != 0) c+= 2; // NH[1] 438 if (I.getPixel(u, v-1) != 0) c+= 4; // NH[2] 439 if (I.getPixel(u-1, v-1) != 0) c+= 8; // NH[3] 440 if (I.getPixel(u-1, v) != 0) c+= 16; // NH[4] 441 if (I.getPixel(u-1, v+1) != 0) c+= 32; // NH[5] 442 if (I.getPixel(u, v+1) != 0) c+= 64; // NH[6] 443 if (I.getPixel(u+1, v+1) != 0) c+= 128; // NH[7] 444 return c; // c = 0,...,255 445 } 446 447 // -------------------------------------------------------------- 448 449 // only used once to calculate Q 450 @SuppressWarnings("unused") 451 private static boolean[][] makeDeletionCodeTable() { 452 boolean[][] Q = new boolean[256][2]; 453 for (int i = 0; i < 256; i++) { 454 byte[] N = new byte[8]; 455 for (int j = 0; j < 8; j++) { 456 N[j] = ((i & (1 << j)) != 0) ? B1 : B0; // test bit j of i 457 } 458// System.out.format("%d: %s\n", i, Arrays.toString(N)); 459 Q[i][0] = R1(N); 460 Q[i][1] = R2(N); 461 } 462 return Q; 463 } 464 465 // -------------------------------------------------------------- 466 467 private static byte binarize(int i) { 468 return (i == 0) ? B0 : B1; 469 } 470 471 private static boolean R1(byte[] NH) { 472 final int b = B(NH); 473 final int c = C(NH); 474 return 475 //NH[0] == 1 && 476 2 <= b && b <= 6 && 477 c == 1 && 478 NH[6] * NH[0] * NH[2] == 0 && 479 NH[4] * NH[6] * NH[0] == 0; 480 } 481 482 private static boolean R2(byte[] NH) { 483 final int b = B(NH); 484 final int c = C(NH); 485 return 486 //NH[0] == 1 && 487 2 <= b && b <= 6 && 488 c == 1 && 489 NH[0] * NH[2] * NH[4] == 0 && 490 NH[2] * NH[4] * NH[6] == 0; 491 } 492 493 private static int B(byte[] NH) { 494 return NH[0] + NH[1] + NH[2] + NH[3] + NH[4] + NH[5] + NH[6] + NH[7]; 495 } 496 497 private static int C(byte[] NH) { // NH = (N0, N1, N2, N3, N4, N5, N6, N7) 498 int c = 0; 499 for (int i = 0; i < 8; i++) { 500 c = c + NH[i] * (NH[i] - NH[(i+1) % 8]); 501 } 502 return c; 503 } 504 505 506 // ---------------------------------------------------------------------- 507 508// public static void main(String[] ards) { 509// boolean[][] Q = makeDeletionCodeTable(); 510// for (int i= 0; i < Q.length; i++) { 511// System.out.println(Arrays.toString(Q[i]) + " // " + i); 512// } 513// } 514}