001/** 002 * Copyright (c) 2011, The University of Southampton and the individual contributors. 003 * All rights reserved. 004 * 005 * Redistribution and use in source and binary forms, with or without modification, 006 * are permitted provided that the following conditions are met: 007 * 008 * * Redistributions of source code must retain the above copyright notice, 009 * this list of conditions and the following disclaimer. 010 * 011 * * Redistributions in binary form must reproduce the above copyright notice, 012 * this list of conditions and the following disclaimer in the documentation 013 * and/or other materials provided with the distribution. 014 * 015 * * Neither the name of the University of Southampton nor the names of its 016 * contributors may be used to endorse or promote products derived from this 017 * software without specific prior written permission. 018 * 019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR 023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 029 */ 030package org.openimaj.image.contour; 031 032import java.util.ArrayList; 033import java.util.HashMap; 034import java.util.List; 035import java.util.Map; 036 037import org.openimaj.citation.annotation.Reference; 038import org.openimaj.citation.annotation.ReferenceType; 039import org.openimaj.image.FImage; 040import org.openimaj.image.analyser.ImageAnalyser; 041import org.openimaj.image.pixel.Pixel; 042import org.openimaj.math.geometry.shape.Rectangle; 043import org.openimaj.util.function.Operation; 044import org.openimaj.util.pair.IndependentPair; 045 046/** 047 * Given a binary image (1-connected and 0-connected regions) detect contours 048 * and provide both the contours and a hierarchy of contour membership. 049 * 050 * @author Sina Samangooei (ss@ecs.soton.ac.uk) 051 * 052 */ 053@Reference( 054 type = ReferenceType.Article, 055 author = { "Suzuki, S.", "Abe, K." }, 056 title = "Topological Structural Analysis of Digitized Binary Image by Border Following", 057 year = "1985", 058 journal = "Computer Vision, Graphics and Image Processing", 059 pages = { "32", "46" }, 060 month = "January", 061 number = "1", 062 volume = "30") 063public class SuzukiContourProcessor implements ImageAnalyser<FImage> { 064 /** 065 * the root border detected 066 */ 067 public Contour root; 068 private double minRelativeChildProp = -1; 069 070 @Override 071 public void analyseImage(final FImage image) { 072 this.root = findContours(image, this); 073 } 074 075 /** 076 * Find contours in the given image and return the border 077 * 078 * @param image 079 * the image 080 * @return the border 081 */ 082 public static Contour findContours(final FImage image) { 083 return findContours(image, new SuzukiContourProcessor()); 084 } 085 086 /** 087 * Detect borders hierarchically in this binary image. Note the image is 088 * changed while borders are found. 089 * 090 * @param image 091 * the image 092 * @param proc 093 * the contour detector 094 * @return the detected border 095 */ 096 public static Contour findContours(final FImage image, SuzukiContourProcessor proc) { 097 final float nbd[] = new float[] { 1 }; 098 final float lnbd[] = new float[] { 1 }; 099 // Prepare the special outer frame 100 final Contour root = new Contour(ContourType.HOLE); 101 final Rectangle bb = image.getBounds(); 102 root.points.addAll(bb.asPolygon().getVertices()); 103 root.finish(); 104 105 final Map<Float, Contour> borderMap = new HashMap<Float, Contour>(); 106 borderMap.put(lnbd[0], root); 107 final SuzukiNeighborStrategy borderFollow = new SuzukiNeighborStrategy(); 108 109 for (int i = 0; i < image.height; i++) { 110 lnbd[0] = 1; // Beggining of appendix 1, this is the beggining of a 111 // scan 112 for (int j = 0; j < image.width; j++) { 113 final float fji = image.getPixel(j, i); 114 final boolean isOuter = isOuterBorderStart(image, i, j); // check 115 // 1(a) 116 final boolean isHole = isHoleBorderStart(image, i, j); // check 117 // 1(b) 118 if (isOuter || isHole) { // check 1(c) 119 final Contour border = new Contour(j, i); 120 Contour borderPrime = null; 121 final Pixel from = new Pixel(j, i); 122 if (isOuter) { 123 nbd[0] += 1; // in 1(a) we increment NBD 124 from.x -= 1; 125 border.type = ContourType.OUTER; 126 borderPrime = borderMap.get(lnbd[0]); 127 // the check of table 1 128 switch (borderPrime.type) { 129 case OUTER: 130 border.setParent(borderPrime.parent); 131 break; 132 case HOLE: 133 border.setParent(borderPrime); 134 break; 135 } 136 } 137 else { 138 nbd[0] += 1; // in 1(b) we increment NBD 139 // according to 1(b) we set lnbd to the pixel value if 140 // it is greater than 1 141 if (fji > 1) 142 lnbd[0] = fji; 143 borderPrime = borderMap.get(lnbd[0]); 144 from.x += 1; 145 border.type = ContourType.HOLE; 146 // the check of table 1 147 switch (borderPrime.type) { 148 case OUTER: 149 border.setParent(borderPrime); 150 break; 151 case HOLE: 152 border.setParent(borderPrime.parent); 153 break; 154 } 155 } 156 157 final Pixel ij = new Pixel(j, i); 158 borderFollow.directedContour(image, ij, from, 159 new Operation<IndependentPair<Pixel, boolean[]>>() { 160 161 @Override 162 public void perform(IndependentPair<Pixel, boolean[]> object) { 163 final Pixel p = object.firstObject(); 164 final boolean[] d = object.secondObject(); 165 border.points.add(p); 166 if (crossesEastBorder(image, d, p)) { 167 image.setPixel(p.x, p.y, -nbd[0]); 168 } else if (image.getPixel(p) == 1f) { 169 // only set if the pixel has not been 170 // visited before 3.4(b)! 171 image.setPixel(p.x, p.y, nbd[0]); 172 } // otherwise leave it alone! 173 } 174 175 }); 176 // this is 3.1, if no borders were given, this means this is 177 // a pixel on its own, so we set it to -nbd 178 if (border.points.size() == 0) { 179 border.points.add(ij); 180 image.setPixel(j, i, -nbd[0]); 181 } 182 border.finish(); 183 // if(thisborder.rect.calculateArea()) 184 borderMap.put(nbd[0], border); 185 } 186 // This is step (4) 187 if (fji != 0 && fji != 1) 188 lnbd[0] = Math.abs(fji); 189 190 } 191 } 192 if (proc.minRelativeChildProp > 0) { 193 removeSmall(root, proc.minRelativeChildProp); 194 } 195 return root; 196 } 197 198 private static void removeSmall(Contour root, double minRelativeChildProp) { 199 final List<Contour> toSearch = new ArrayList<Contour>(); 200 toSearch.add(root); 201 while (toSearch.size() != 0) { 202 final Contour ret = toSearch.remove(0); 203 if (ret.parent != null && ret.rect.calculateArea() / ret.parent.rect.calculateArea() < minRelativeChildProp) { 204 ret.parent.children.remove(ret); 205 } else { 206 toSearch.addAll(ret.children); 207 } 208 } 209 } 210 211 private static boolean crossesEastBorder(final FImage image, boolean[] checked, final Pixel p) { 212 final boolean b = checked[Direction.fromTo(p, new Pixel(p.x + 1, p.y)).ordinal()]; 213 return image.getPixel(p) != 0 && (p.x == image.width - 1 || b);// this 214 // is 215 // 3.4(a) 216 // with 217 // an 218 // edge 219 // case 220 // check 221 } 222 223 private static boolean isOuterBorderStart(FImage image, int i, int j) { 224 return (image.pixels[i][j] == 1 && (j == 0 || image.pixels[i][j - 1] == 0)); 225 } 226 227 private static boolean isHoleBorderStart(FImage image, int i, int j) { 228 return (image.pixels[i][j] >= 1 && (j == image.width - 1 || image.pixels[i][j + 1] == 0)); 229 } 230 231 /** 232 * Set the threshold at which small children (measured relative to their 233 * parent area) are removed. 234 * 235 * @param d 236 * the threshold 237 */ 238 public void setMinRelativeChildProp(double d) { 239 this.minRelativeChildProp = d; 240 } 241 242}