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 * Flood-fill of @link{FImage}s or @link{MBFImage}s.
043 *
044 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
045 * @param <I>
046 *            type of image
047 */
048public class FloodFill<I extends Image<?, I> & SinglebandImageProcessor.Processable<Float, FImage, I>>
049                implements
050                ImageAnalyser<I>
051{
052        FImage flooded;
053        Pixel startPixel;
054        float threshold;
055
056        /**
057         * Construct flood-fill processor with the given threshold and starting
058         * coordinate.
059         *
060         * @param x
061         *            x-coordinate of start pixel
062         * @param y
063         *            y-coordinate of start pixel
064         * @param threshold
065         *            threshold for determing whether a pixel should be flooded
066         */
067        public FloodFill(int x, int y, float threshold) {
068                this.startPixel = new Pixel(x, y);
069                this.threshold = threshold;
070        }
071
072        /**
073         * Construct flood-fill processor with the given threshold and starting
074         * coordinate.
075         *
076         * @param startPixel
077         *            coordinate of start pixel
078         * @param threshold
079         *            threshold for determing whether a pixel should be flooded
080         */
081        public FloodFill(Pixel startPixel, float threshold) {
082                this.startPixel = startPixel;
083                this.threshold = threshold;
084        }
085
086        /*
087         * (non-Javadoc)
088         * 
089         * @see
090         * org.openimaj.image.processor.ImageProcessor#processImage(org.openimaj
091         * .image.Image)
092         */
093        @Override
094        public void analyseImage(I image) {
095                flooded = floodFill((Image<?, ?>) image, startPixel, threshold);
096        }
097
098        /**
099         * 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}