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 java.awt.Point; 013import java.util.ArrayList; 014import java.util.Collections; 015import java.util.List; 016 017import ij.IJ; 018import ij.process.ByteProcessor; 019 020/** 021 * Binary region labeler based on a combined region labeling 022 * and contour tracing algorithm: 023 * F. Chang, C. J. Chen, and C. J. Lu. A linear-time component labeling 024 * algorithm using contour tracing technique. Computer Vision, Graphics, 025 * and Image Processing: Image Understanding 93(2), 206-220 (2004). 026 * 027 * @author WB 028 * @version 2016-11-08 029 */ 030public class RegionContourLabeling extends RegionLabeling implements ContourTracer { 031 032 static private final int VISITED = -1; 033 034 private List<Contour> outerContours; 035 private List<Contour> innerContours; 036 037 /** 038 * Creates a new region labeling. 039 * 040 * @param ip the binary input image with 0 values for background pixels and values > 0 041 * for foreground pixels. 042 */ 043 public RegionContourLabeling (ByteProcessor ip) { 044 super(ip); // all work is done by the constructor of the superclass 045 } 046 047 // public methods required by interface ContourTracer (others are in inherited from super-class) 048 049 @Override 050 public List<Contour> getOuterContours() { 051 return copyContours(outerContours, false); 052 } 053 054 @Override 055 public List<Contour> getOuterContours(boolean sort) { 056 return copyContours(outerContours, sort); 057 } 058 059 @Override 060 public List<Contour> getInnerContours() { 061 return copyContours(innerContours, false); 062 } 063 064 @Override 065 public List<Contour> getInnerContours(boolean sort) { 066 return copyContours(innerContours, sort); 067 } 068 069 070 // non-public methods 071 072 @Override 073 protected int[][] initialize() { 074 // Create a label array which is "padded" by 1 pixel, i.e., 075 // 2 rows and 2 columns larger than the image: 076 int[][] lA = new int[width+2][height+2]; // label array, initialized to zero 077 outerContours = new ArrayList<Contour>(); 078 innerContours = new ArrayList<Contour>(); 079 return lA; 080 } 081 082 @Override 083 void applyLabeling() { 084 resetLabel(); 085 // scan top to bottom, left to right 086 for (int v = 0; v < height; v++) { 087 int label = 0; // reset label, scan through horiz. line: 088 for (int u = 0; u < width; u++) { 089 if (ip.getPixel(u, v) > 0) { // unlabeled FOREGROUND pixel 090 if (label != 0) { // keep using the same label 091 setLabel(u, v, label); 092 } 093 else { // label == zero 094 label = getLabel(u, v); 095 if (label == 0) { // new (unlabeled) region is hit 096 label = getNextLabel(); // assign a new region label 097 Contour oc = traceContour(u, v, 0, label); 098 outerContours.add(oc); 099 setLabel(u, v, label); 100 } 101 } 102 } 103 else { // BACKGROUND pixel 104 if (label != 0) { // exiting a region 105 if (getLabel(u, v) == BACKGROUND) { // unlabeled - new inner contour 106 Contour ic = traceContour(u - 1, v, 1, label); 107 innerContours.add(ic); 108 } 109 label = 0; 110 } 111 } 112 } 113 } 114 } 115 116 @Override 117 void collectRegions() { 118 super.collectRegions(); // collect region pixels and calculate statistics 119 attachOuterContours(); // attach each outer contours to the corresponding region 120 attachInnerContours(); // attach all inner contours to the corresponding regions 121 } 122 123 // Trace one contour starting at (xS,yS) 124 // in direction dS with label label 125 // trace one contour starting at (xS,yS) in direction dS 126 private Contour traceContour(int xS, int yS, int dS, int label) { 127 Contour contr = new Contour(label); 128 int xT, yT; // T = successor of starting point (xS,yS) 129 int xP, yP; // P = previous contour point 130 int xC, yC; // C = current contour point 131 Point pt = new Point(xS, yS); 132 int dNext = findNextPoint(pt, dS); 133 contr.addPoint(pt); 134 xP = xS; yP = yS; 135 xC = xT = pt.x; 136 yC = yT = pt.y; 137 138 boolean done = (xS == xT && yS == yT); // true if isolated pixel 139 while (!done) { 140 setLabel(xC, yC, label); 141 pt = new Point(xC, yC); 142 int dSearch = (dNext + 6) % 8; 143 dNext = findNextPoint(pt, dSearch); 144 xP = xC; yP = yC; 145 xC = pt.x; yC = pt.y; 146 // are we back at the starting position? 147 done = (xP==xS && yP==yS && xC==xT && yC==yT); 148 if (!done) { 149 contr.addPoint(pt); 150 } 151 } 152 return contr; 153 } 154 155 static final int[][] delta = { 156 { 1,0}, { 1, 1}, {0, 1}, {-1, 1}, 157 {-1,0}, {-1,-1}, {0,-1}, { 1,-1}}; 158 159 private int findNextPoint (Point pt, int dir) { 160 // Starts at Point pt in direction dir, 161 // returns the resulting tracing direction 162 // and modifies pt. 163 for (int i = 0; i < 7; i++) { 164 int x = pt.x + delta[dir][0]; 165 int y = pt.y + delta[dir][1]; 166 if (ip.getPixel(x, y) == BACKGROUND) { 167 setLabel(x, y, VISITED); // mark surrounding background pixels 168 dir = (dir + 1) % 8; 169 } 170 else { // found a non-background pixel (next pixel to follow) 171 pt.x = x; 172 pt.y = y; 173 break; 174 } 175 } 176 return dir; 177 } 178 179 private void attachOuterContours() { 180 for (Contour c : outerContours) { 181 int label = c.getLabel(); 182 BinaryRegion r = findRegion(label); 183 if (r == null) { 184 IJ.log("Error: Could not associate outer contour with label " + label); 185 } 186 else { 187 r.setOuterContour(c); 188 } 189 } 190 } 191 192 private void attachInnerContours() { 193 for (BinaryRegion r : regions) { 194 r.makeInnerContours(); // ensure that every region has a (empty) list of inner contours 195 } 196 for (Contour c : innerContours) { 197 int label = c.getLabel(); 198 BinaryRegion r = findRegion(label); 199 if (r == null) { 200 IJ.log("Error: Could not associate inner contour with label " + label); 201 } 202 else { 203 r.addInnerContour(c); 204 } 205 } 206 } 207 208 // access methods to the label array (which is padded!) 209 @Override 210 public int getLabel(int u, int v) { // (u,v) are image coordinates 211 if (u >= -1 && u <= width && v >= -1 && v <= height) 212 return labelArray[u + 1][v + 1]; // label array is padded (offset = 1) 213 else 214 return BACKGROUND; 215 //return labelArray[u + 1][v + 1]; // original version 216 } 217 218 @Override 219 protected void setLabel(int u, int v, int label) { // (u,v) are image coordinates 220 if (u >= -1 && u <= width && v >= -1 && v <= height) { 221 labelArray[u + 1][v + 1] = label; 222 } 223 } 224 225 private List<Contour> copyContours(List<Contour> cntrs, boolean sort) { 226 if (cntrs == null) 227 return Collections.emptyList(); 228 else { 229 List<Contour> cc = new ArrayList<Contour>(cntrs); 230 if (sort) { 231 Collections.sort(cc); 232 } 233 return cc; 234 } 235 } 236 237} 238