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; 014import imagingbook.common.geometry.basic.Pnt2d.PntInt; 015import imagingbook.common.util.tuples.Tuple2; 016 017import java.util.ArrayList; 018import java.util.Arrays; 019import java.util.List; 020 021import static imagingbook.common.geometry.basic.NeighborhoodType2D.N4; 022 023/** 024 * <p> 025 * Binary region segmentation based on a combined region labeling and contour tracing algorithm as described in [1]. 026 * Detected regions and contours are 4- or 8-connected. See Sec. 8.2.2 of [2] for additional details. 027 * </p> 028 * <p> 029 * [1] F. Chang, C. J. Chen, and C. J. Lu. A linear-time component labeling algorithm using contour tracing technique. 030 * Computer Vision, Graphics, and Image Processing: Image Understanding 93(2), 206-220 (2004). 031 * <br> 032 * [2] W. Burger, M.J. Burge, <em>Digital Image Processing – An Algorithmic Introduction</em>, 3rd ed, Springer 033 * (2022). 034 * </p> 035 * 036 * @author WB 037 * @version 2022/09/28 038 */ 039public class RegionContourSegmentation extends BinaryRegionSegmentation implements ContourTracer { 040 041 static private final int VISITED = -1; 042 043 private ByteProcessor ip; // only used temporarily 044 private List<Contour.Outer> outerContours; 045 private List<Contour.Inner> innerContours; 046 047 /** 048 * Constructor. Creates a combined region and contour segmentation from the specified image, which is not modified. 049 * The input image is considered binary, with 0 values for background pixels and values ≠ 0 for foreground 050 * pixels. The 4-neighborhood is used by default ({@link BinaryRegionSegmentation#DefaultNeighborhoodT}). 051 * 052 * @param ip the binary input image to be segmented 053 */ 054 public RegionContourSegmentation(ByteProcessor ip) { 055 this(ip, DefaultNeighborhoodT); 056 } 057 058 /** 059 * Constructor. Creates a combined region and contour segmentation from the specified image and neighborhood type 060 * (4- or 8-neighborhood). The input image is considered binary, with 0 values for background pixels and values ≠ 061 * 0 for foreground pixels. 062 * 063 * @param ip the binary input image to be segmented 064 * @param nh the neighborhood type (4- or 8-neighborhood) 065 */ 066 public RegionContourSegmentation(ByteProcessor ip, NeighborhoodType2D nh) { 067 super(ip, nh); 068 attachOuterContours(); // attach the outer contour to the corresponding region 069 attachInnerContours(); // attach all inner contours to the corresponding region 070 } 071 072 @Override 073 public List<Contour.Outer> getOuterContours() { 074 return getOuterContours(false); 075 } 076 077 @Override 078 public List<Contour.Outer> getOuterContours(boolean sort) { 079 Contour.Outer[] oca = outerContours.toArray(new Contour.Outer[0]); 080 if (sort) { 081 Arrays.sort(oca); 082 } 083 return Arrays.asList(oca); 084 } 085 086 @Override 087 public List<Contour.Inner> getInnerContours() { 088 return getInnerContours(false); 089 } 090 091 @Override 092 public List<Contour.Inner> getInnerContours(boolean sort) { 093 Contour.Inner[] ica = innerContours.toArray(new Contour.Inner[0]); 094 if (sort) { 095 Arrays.sort(ica); 096 } 097 return Arrays.asList(ica); 098 } 099 100 // non-public methods ------------------------------------------------------------------ 101 102 @Override 103 int[][] makeLabelArray(ByteProcessor ip) { 104 // Create a label array which is "padded" by 1 pixel, i.e., 105 // 2 rows and 2 columns larger than the image: 106 return new int[width + 2][height + 2]; // label array, initialized to zero 107 } 108 109 @Override 110 boolean applySegmentation(ByteProcessor ip) { 111 this.ip = ip; // temp. reference to ip 112 outerContours = new ArrayList<>(); 113 innerContours = new ArrayList<>(); 114 for (int v = 0; v < height; v++) { // scan top to bottom, left to right 115 int label = 0; // reset label, scan through horiz. row: 116 for (int u = 0; u < width; u++) { 117 if (ip.get(u, v) > 0) { // hit an unlabeled FOREGROUND pixel 118 if (label != 0) { // keep using the same label 119 setLabel(u, v, label); 120 } 121 else { // label == 0 122 label = getLabel(u, v); 123 if (label == 0) { // new (unlabeled) region is hit 124 label = getNextLabel(); // assign a new region label 125 PntInt xs = PntInt.from(u, v); 126 int ds = 0; 127 Contour.Outer c = traceContour(xs, ds, new Contour.Outer(label)); 128 outerContours.add(c); 129 setLabel(u, v, label); 130 } 131 } 132 } 133 else { // hit a BACKGROUND pixel 134 if (label != 0) { // exiting a region 135 if (getLabel(u, v) == Background) { // unlabeled - new inner contour 136 PntInt xs = PntInt.from(u - 1, v); 137 int ds = (NT == N4) ? 2 : 1; 138 Contour.Inner c = traceContour(xs, ds, new Contour.Inner(label)); 139 innerContours.add(c); 140 } 141 label = 0; 142 } 143 } 144 } 145 } 146 this.ip = null; 147 return true; 148 } 149 150 // Trace one contour starting at Xs in direction ds 151 private <T extends Contour> T traceContour(PntInt xs, final int ds, T C) { 152 final int label = C.getLabel(); // C: empty inner or outer contour 153 154 Tuple2<PntInt, Integer> next = findNextContourPoint(xs, ds); 155 PntInt x = next.get0(); 156 int d = next.get1(); 157 C.addPoint(x); 158 159 final PntInt xt = x; 160 boolean home = xs.equals(xt); 161 162 while (!home) { 163 setLabel(x, label); 164 PntInt xp = x; 165 int dn = (d + 6) % 8; 166 next = findNextContourPoint(x, dn); 167 x = next.get0(); 168 d = next.get1(); 169 // are we back at the starting position? 170 home = (xp.equals(xs) && x.equals(xt)); // back at start pos. 171 if (!home) { 172 C.addPoint(x); 173 } 174 } 175 return C; 176 } 177 178 private static final int[][] delta = { 179 { 1,0}, { 1, 1}, {0, 1}, {-1, 1}, 180 {-1,0}, {-1,-1}, {0,-1}, { 1,-1}}; 181 182 // -------------------------------------------------------------------- 183 184 // Starts at point X0 in direction d0, returns a tuple holding 185 // the next point and the direction in which it was found if successful. 186 // Returns null if no successor point is found. 187 private Tuple2<PntInt, Integer> findNextContourPoint(PntInt x0, int d0) { 188 final int step = (NT == N4) ? 2 : 1; 189 PntInt xn = null; 190 int d = d0; 191 int i = 0; 192 boolean done = false; 193 while (i < 7 && !done) { // N4: i = 0,2,4,6 N8: i = 0,1,2,3,4,5,6 194 xn = x0.plus(delta[d]); 195 if (!isInsideImage(xn) || ip.get(xn.x, xn.y) == Background) { 196 setLabel(xn, VISITED); // mark this background pixel not to be visited again 197 d = (d + step) % 8; 198 } 199 else { // found a non-background pixel (next pixel to follow) 200 done = true; 201 } 202 i = i + step; 203 } 204 return (done) ? 205 Tuple2.from(xn, d) : 206 Tuple2.from(x0, d0); // no successor found 207 } 208 209 // ------------------------------------------------------------------------------ 210 211 private void attachOuterContours() { 212 for (Contour.Outer c : outerContours) { 213 int label = c.getLabel(); 214 BinaryRegion reg = getRegion(label); 215 if (reg == null) { 216 throw new RuntimeException("could not attach outer contour to region with label " + label); 217 } 218 else { 219 reg.setOuterContour(c); 220 } 221 } 222 } 223 224 private void attachInnerContours() { 225 for (Contour.Inner c : innerContours) { 226 int label = c.getLabel(); 227 SegmentationBackedRegion reg = getRegion(label); 228 if (reg == null) { 229 throw new RuntimeException("could not attach inner contour to region with label " + label); 230 } 231 else { 232 reg.addInnerContour(c); 233 } 234 } 235 } 236 237 // access methods to the (padded) label array 238 @Override 239 public int getLabel(int u, int v) { // (u,v) are image coordinates 240 if (u >= -1 && u <= width && v >= -1 && v <= height) 241 return labelArray[u + 1][v + 1]; // label array is padded (offset = 1) 242 else 243 return Background; 244 } 245 246 @Override 247 void setLabel(int u, int v, int label) { // (u,v) are image coordinates 248 if (u >= -1 && u <= width && v >= -1 && v <= height) { 249 labelArray[u + 1][v + 1] = label; 250 } 251 } 252 253 private void setLabel(PntInt p, int label) { // (u,v) are image coordinates 254 setLabel(p.x, p.y, label); 255 } 256 257 private boolean isInsideImage(int u, int v) { 258 return (0 <= u && u < width && 0 <= v && v < height); 259 } 260 261 private boolean isInsideImage(PntInt p) { 262 return isInsideImage(p.x, p.y); 263 } 264 265}