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.analysis.algorithm; 031 032import java.util.LinkedHashSet; 033 034import org.openimaj.image.FImage; 035import org.openimaj.image.Image; 036import org.openimaj.image.MBFImage; 037import org.openimaj.image.analyser.ImageAnalyser; 038import org.openimaj.image.pixel.Pixel; 039import org.openimaj.image.processor.SinglebandImageProcessor; 040 041 042/** 043 * Flood-fill of @link{FImage}s or @link{MBFImage}s. 044 * 045 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 046 * @param <I> type of image 047 */ 048public class FloodFill< 049 I extends Image<?,I> & SinglebandImageProcessor.Processable<Float,FImage,I>> 050 implements 051 ImageAnalyser<I> 052{ 053 FImage flooded; 054 Pixel startPixel; 055 float threshold; 056 057 /** 058 * Construct flood-fill processor with the given 059 * threshold and starting coordinate. 060 * 061 * @param x x-coordinate of start pixel 062 * @param y y-coordinate of start pixel 063 * @param threshold threshold for determing whether a pixel should be flooded 064 */ 065 public FloodFill(int x, int y, float threshold) { 066 this.startPixel = new Pixel(x, y); 067 this.threshold = threshold; 068 } 069 070 /** 071 * Construct flood-fill processor with the given 072 * threshold and starting coordinate. 073 * 074 * @param startPixel coordinate of start pixel 075 * @param threshold threshold for determing whether a pixel should be flooded 076 */ 077 public FloodFill(Pixel startPixel, float threshold) { 078 this.startPixel = startPixel; 079 this.threshold = threshold; 080 } 081 082 /* (non-Javadoc) 083 * @see org.openimaj.image.processor.ImageProcessor#processImage(org.openimaj.image.Image) 084 */ 085 @Override 086 public void analyseImage(I image) { 087 flooded = floodFill((Image<?, ?>) image, startPixel, threshold); 088 } 089 090 /** 091 * Get the binary flooded image map 092 * @return flooded image 093 */ 094 public FImage getFlooded() { 095 return flooded; 096 } 097 098 protected static <T> boolean accept(Image<T,?> image, Pixel n, T initial, float threshold) { 099 if (image instanceof FImage) { 100 return Math.abs((Float)initial - (Float)image.getPixel(n.x, n.y)) < threshold; 101 } else if (image instanceof MBFImage) { 102 Float [] finit = (Float[]) initial; 103 Float [] fpix = (Float[]) image.getPixel(n.x, n.y); 104 float accum = 0; 105 106 for (int i=0; i<finit.length; i++) 107 accum += (finit[i] - fpix[i]) * (finit[i] - fpix[i]); 108 109 return Math.sqrt(accum) < threshold; 110 } else { 111 throw new RuntimeException("unsupported image type"); 112 } 113 } 114 115 /** 116 * Flood-fill an image from the given starting pixel position with the 117 * given threshold. 118 * @param <T> The pixel type of the image 119 * @param image the image 120 * @param startx the x-coordinate of the start pixel 121 * @param starty the y-coordinate of the start pixel 122 * @param threshold the threshold for determining with a pixel should be filled 123 * @return a binary @link{FImage} with filled pixels from the input set to 1 124 */ 125 public static <T> FImage floodFill(Image<T,?> image, int startx, int starty, float threshold) { 126 return floodFill(image, new Pixel(startx, starty), threshold); 127 } 128 129 /** 130 * Flood-fill an image from the given starting pixel position with the 131 * given threshold. 132 * @param <T> The pixel type of the image 133 * @param image the image 134 * @param start the start pixel 135 * @param threshold the threshold for determining with a pixel should be filled 136 * @return a binary @link{FImage} with filled pixels from the input set to 1 137 */ 138 public static <T> FImage floodFill(Image<T,?> image, Pixel start, float threshold) { 139 FImage output = new FImage(image.getWidth(), image.getHeight()); 140 141// Flood-fill (node, target-color, replacement-color): 142// 1. Set Q to the empty queue. 143 LinkedHashSet<Pixel> queue = new LinkedHashSet<Pixel>(); 144 145// 2. If the color of node is not equal to target-color, return. 146// if (image.pixels[start.y][start.x] == 0) return cc; 147 T initial = image.getPixel(start.x, start.y); 148 149// 3. Add node to Q. 150 queue.add(start); 151 152// 4. For each element n of Q: 153 while (queue.size() > 0) { 154 //Pixel n = queue.poll(); 155 Pixel n = queue.iterator().next(); 156 queue.remove(n); 157 158// 5. If the color of n is equal to target-color: 159 if (accept(image, n, initial, threshold)) { 160// 6. Set w and e equal to n. 161 int e = n.x, w=n.x; 162// 7. Move w to the west until the color of the node to the west of w no longer matches target-color. 163 while (w>0 && accept(image, new Pixel(w-1, n.y), initial, threshold)) w--; 164 165// 8. Move e to the east until the color of the node to the east of e no longer matches target-color. 166 while (e<image.getWidth()-1 && accept(image, new Pixel(e+1, n.y), initial, threshold)) e++; 167 168// 9. Set the color of nodes between w and e to replacement-color. 169 for (int i=w; i<=e; i++) { 170 output.pixels[n.y][i] = 1; 171 172// 10. For each node n between w and e: 173 int north = n.y - 1; 174 int south = n.y + 1; 175// 11. If the color of the node to the north of n is target-color, add that node to Q. 176 if (north >= 0 && accept(image, new Pixel(i, north), initial, threshold) && output.pixels[north][i] != 1) queue.add(new Pixel(i, north)); 177// If the color of the node to the south of n is target-color, add that node to Q. 178 if (south < image.getHeight() && accept(image, new Pixel(i, south), initial, threshold) && output.pixels[south][i] != 1) queue.add(new Pixel(i, south)); 179 } 180// 12. Continue looping until Q is exhausted. 181 } 182 } 183// 13. Return. 184 return output; 185 } 186}