1 /**
2 * Copyright (c) 2011, The University of Southampton and the individual contributors.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * * Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * * Neither the name of the University of Southampton nor the names of its
16 * contributors may be used to endorse or promote products derived from this
17 * software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
23 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
26 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30 package org.openimaj.image.analysis.algorithm;
31
32 import java.util.LinkedHashSet;
33
34 import org.openimaj.image.FImage;
35 import org.openimaj.image.Image;
36 import org.openimaj.image.MBFImage;
37 import org.openimaj.image.analyser.ImageAnalyser;
38 import org.openimaj.image.pixel.Pixel;
39 import org.openimaj.image.processor.SinglebandImageProcessor;
40
41 /**
42 * Flood-fill of @link{FImage}s or @link{MBFImage}s.
43 *
44 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
45 * @param <I>
46 * type of image
47 */
48 public class FloodFill<I extends Image<?, I> & SinglebandImageProcessor.Processable<Float, FImage, I>>
49 implements
50 ImageAnalyser<I>
51 {
52 FImage flooded;
53 Pixel startPixel;
54 float threshold;
55
56 /**
57 * Construct flood-fill processor with the given threshold and starting
58 * coordinate.
59 *
60 * @param x
61 * x-coordinate of start pixel
62 * @param y
63 * y-coordinate of start pixel
64 * @param threshold
65 * threshold for determing whether a pixel should be flooded
66 */
67 public FloodFill(int x, int y, float threshold) {
68 this.startPixel = new Pixel(x, y);
69 this.threshold = threshold;
70 }
71
72 /**
73 * Construct flood-fill processor with the given threshold and starting
74 * coordinate.
75 *
76 * @param startPixel
77 * coordinate of start pixel
78 * @param threshold
79 * threshold for determing whether a pixel should be flooded
80 */
81 public FloodFill(Pixel startPixel, float threshold) {
82 this.startPixel = startPixel;
83 this.threshold = threshold;
84 }
85
86 /*
87 * (non-Javadoc)
88 *
89 * @see
90 * org.openimaj.image.processor.ImageProcessor#processImage(org.openimaj
91 * .image.Image)
92 */
93 @Override
94 public void analyseImage(I image) {
95 flooded = floodFill((Image<?, ?>) image, startPixel, threshold);
96 }
97
98 /**
99 * Get the binary flooded image map
100 *
101 * @return flooded image
102 */
103 public FImage getFlooded() {
104 return flooded;
105 }
106
107 protected static <T> boolean accept(Image<T, ?> image, Pixel n, T initial, float threshold) {
108 if (image instanceof FImage) {
109 return Math.abs((Float) initial - (Float) image.getPixel(n.x, n.y)) < threshold;
110 } else if (image instanceof MBFImage) {
111 final Float[] finit = (Float[]) initial;
112 final Float[] fpix = (Float[]) image.getPixel(n.x, n.y);
113 float accum = 0;
114
115 for (int i = 0; i < finit.length; i++)
116 accum += (finit[i] - fpix[i]) * (finit[i] - fpix[i]);
117
118 return Math.sqrt(accum) < threshold;
119 } else {
120 throw new RuntimeException("unsupported image type");
121 }
122 }
123
124 /**
125 * Flood-fill an image from the given starting pixel position with the given
126 * threshold.
127 *
128 * @param <T>
129 * The pixel type of the image
130 * @param image
131 * the image
132 * @param startx
133 * the x-coordinate of the start pixel
134 * @param starty
135 * the y-coordinate of the start pixel
136 * @param threshold
137 * the threshold for determining with a pixel should be filled
138 * @return a binary @link{FImage} with filled pixels from the input set to 1
139 */
140 public static <T> FImage floodFill(Image<T, ?> image, int startx, int starty, float threshold) {
141 return floodFill(image, new Pixel(startx, starty), threshold);
142 }
143
144 /**
145 * Flood-fill an image from the given starting pixel position with the given
146 * threshold.
147 *
148 * @param <T>
149 * The pixel type of the image
150 * @param image
151 * the image
152 * @param start
153 * the start pixel
154 * @param threshold
155 * the threshold for determining with a pixel should be filled
156 * @return a binary @link{FImage} with filled pixels from the input set to 1
157 */
158 public static <T> FImage floodFill(Image<T, ?> image, Pixel start, float threshold) {
159 final FImage output = new FImage(image.getWidth(), image.getHeight());
160
161 // Flood-fill (node, target-color, replacement-color):
162 // 1. Set Q to the empty queue.
163 final LinkedHashSet<Pixel> queue = new LinkedHashSet<Pixel>();
164
165 // 2. If the color of node is not equal to target-color, return.
166 // if (image.pixels[start.y][start.x] == 0) return cc;
167 final T initial = image.getPixel(start.x, start.y);
168
169 // 3. Add node to Q.
170 queue.add(start);
171
172 // 4. For each element n of Q:
173 while (queue.size() > 0) {
174 // Pixel n = queue.poll();
175 final Pixel n = queue.iterator().next();
176 queue.remove(n);
177
178 // 5. If the color of n is equal to target-color:
179 if (accept(image, n, initial, threshold) && output.pixels[n.y][n.x] != 1) {
180 // 6. Set w and e equal to n.
181 int e = n.x, w = n.x;
182 // 7. Move w to the west until the color of the node to the west
183 // of w no longer matches target-color.
184 while (w > 0 && accept(image, new Pixel(w - 1, n.y), initial, threshold))
185 w--;
186
187 // 8. Move e to the east until the color of the node to the east
188 // of e no longer matches target-color.
189 while (e < image.getWidth() - 1 && accept(image, new Pixel(e + 1, n.y), initial, threshold))
190 e++;
191
192 // 9. Set the color of nodes between w and e to
193 // replacement-color.
194 for (int i = w; i <= e; i++) {
195 output.pixels[n.y][i] = 1;
196
197 // 10. For each node n between w and e:
198 final int north = n.y - 1;
199 final int south = n.y + 1;
200 // 11. If the color of the node to the north of n is
201 // target-color, add that node to Q.
202 if (north >= 0 && accept(image, new Pixel(i, north), initial, threshold)
203 && output.pixels[north][i] != 1)
204 queue.add(new Pixel(i, north));
205 // If the color of the node to the south of n is
206 // target-color, add that node to Q.
207 if (south < image.getHeight() && accept(image, new Pixel(i, south), initial, threshold)
208 && output.pixels[south][i] != 1)
209 queue.add(new Pixel(i, south));
210 }
211 // 12. Continue looping until Q is exhausted.
212 }
213 }
214 // 13. Return.
215 return output;
216 }
217 }