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.watershed;
031
032import java.util.ArrayDeque;
033import java.util.ArrayList;
034import java.util.BitSet;
035import java.util.List;
036
037import org.openimaj.image.FImage;
038import org.openimaj.image.analysis.watershed.event.ComponentStackMergeListener;
039import org.openimaj.image.analysis.watershed.feature.ComponentFeature;
040import org.openimaj.image.pixel.IntValuePixel;
041
042/**
043 * Maximally Stable Extremal Region watershed algorithm, implemented as
044 * described in the Microsoft paper of Nister and Stewenius.
045 *
046 * @author David Dupplaw (dpd@ecs.soton.ac.uk)
047 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
048 *
049 */
050public class WatershedProcessorAlgorithm
051{
052        /**
053         * A sorted heap of pixels. When {@link #pop()} is called the lowest value
054         * pixel is returned first.
055         *
056         * @author David Dupplaw (dpd@ecs.soton.ac.uk)
057         * @author Jonathon Hare (dpd@ecs.soton.ac.uk)
058         *
059         */
060        private class BoundaryHeap
061        {
062                private BitSet availablePixels;
063                private ArrayDeque<IntValuePixel>[] stacks;
064
065                /**
066                 * Construct a boundary heap object with a given number of levels (i.e.
067                 * max value of a pixel).
068                 *
069                 * @param sz
070                 *            number of levels.
071                 */
072                @SuppressWarnings("unchecked")
073                public BoundaryHeap(int sz) {
074                        availablePixels = new BitSet(sz);
075                        stacks = new ArrayDeque[sz];
076
077                        for (int i = 0; i < sz; i++)
078                                stacks[i] = new ArrayDeque<IntValuePixel>();
079                }
080
081                /**
082                 * Pushes the pixel onto the heap.
083                 *
084                 * @param p
085                 *            The {@link IntValuePixel} to push onto the heap.
086                 */
087                public void push(IntValuePixel p)
088                {
089                        final ArrayDeque<IntValuePixel> l = stacks[p.value];
090                        l.push(p);
091                        availablePixels.set(p.value);
092                }
093
094                /**
095                 * Returns the lowest available pixel off the heap (removing it from the
096                 * heap). Pixels are returned in sorted order (lowest value first). The
097                 * method will return null if the heap is empty.
098                 *
099                 * @return The lowest value available pixel or NULL if no pixels are
100                 *         available.
101                 */
102                public IntValuePixel pop()
103                {
104                        final int l = availablePixels.nextSetBit(0);
105                        if (l == -1)
106                                return null; // Null means no available pixels (empty heap)
107
108                        final IntValuePixel xx = this.stacks[l].pop();
109                        if (this.stacks[l].size() == 0)
110                                availablePixels.set(l, false);
111                        return xx; // lowest and newest pixel
112                }
113        }
114
115        /** The pixel where the pour will start */
116        private IntValuePixel startPixel = null;
117
118        /** The mask that shows which pixels have been visited */
119        private BitSet accessibleMask = null;
120
121        /** The current pixel being investigated */
122        private IntValuePixel currentPixel = null;
123
124        /** The stack of components during processing */
125        private ArrayDeque<Component> componentStack = null;
126
127        /** The boundary heap during processing */
128        private BoundaryHeap boundaryHeap = null;
129
130        /** The image being processed */
131        private int[][] greyscaleImage = null;
132
133        /**
134         * The listeners for this watershed process. They will be called as regions
135         * are detected
136         */
137        private List<ComponentStackMergeListener> csmListeners = null;
138
139        private Class<? extends ComponentFeature>[] featureClasses;
140
141        /**
142         * Default constructor
143         *
144         * @param greyscaleImage
145         *            the image as a 2d array of integer values
146         * @param startPixel
147         *            The pixel to start the process at
148         * @param featureClasses
149         *            the features that should be created for each detected
150         *            component
151         */
152        @SafeVarargs
153        public WatershedProcessorAlgorithm(int[][] greyscaleImage, IntValuePixel startPixel,
154                        Class<? extends ComponentFeature>... featureClasses)
155        {
156                this.greyscaleImage = greyscaleImage;
157                this.startPixel = startPixel;
158                this.csmListeners = new ArrayList<ComponentStackMergeListener>();
159
160                this.featureClasses = featureClasses;
161        }
162
163        /**
164         * Default constructor
165         *
166         * @param bGreyscaleImage
167         *            the image to apply the watershed transform too
168         * @param startPixel
169         *            The pixel to start the process at
170         * @param featureClasses
171         *            the features that should be created for each detected
172         *            component
173         */
174        @SafeVarargs
175        public WatershedProcessorAlgorithm(FImage bGreyscaleImage, IntValuePixel startPixel,
176                        Class<? extends ComponentFeature>... featureClasses)
177        {
178                this(new int[bGreyscaleImage.getHeight()][bGreyscaleImage.getWidth()], startPixel, featureClasses);
179
180                for (int j = 0; j < bGreyscaleImage.getHeight(); j++) {
181                        for (int i = 0; i < bGreyscaleImage.getWidth(); i++) {
182                                greyscaleImage[j][i] = (int) (bGreyscaleImage.pixels[j][i] * 255);
183                        }
184                }
185        }
186
187        /**
188         * Start the detection process by pouring on water at the pour point. (part
189         * 1 and 2)
190         *
191         */
192        public void startPour()
193        {
194                // For each step on the downhill stream is created as
195                // a component.
196                this.currentPixel = startPixel;
197
198                // Store the grey level of the current pixel
199                this.currentPixel.value = greyscaleImage[this.startPixel.y][this.startPixel.x];
200
201                // Create the mask the shows where the water has access to
202                this.accessibleMask = new BitSet(this.greyscaleImage.length * this.greyscaleImage[0].length);
203
204                // Create the stack of components
205                this.componentStack = new ArrayDeque<Component>();
206
207                // Create the heap of boundary pixels
208                this.boundaryHeap = new BoundaryHeap(256);
209
210                // Create a dummy component with a greylevel higher than
211                // any allowed and push it onto the stack
212                final Component dummyComponent = new Component(new IntValuePixel(-1, -1, Integer.MAX_VALUE), featureClasses);
213                this.componentStack.push(dummyComponent);
214
215                // Continue the processing at the first pixel
216                this.processNeighbours();
217
218                // System.err.println("Component Stack: "+componentStack );
219        }
220
221        /**
222         * Process the current pixel's neighbours (part 4, 5, 6 and 7).
223         */
224        private void processNeighbours()
225        {
226                // Push an empty component with the current level
227                // onto the component stack
228                Component currentComponent = new Component(this.currentPixel, featureClasses);
229                componentStack.push(currentComponent);
230
231                // System.err.println( "Processing neighbours of "+currentPixel );
232
233                final boolean processNeighbours = true;
234                while (processNeighbours)
235                {
236                        boolean toContinue = false;
237
238                        // Get all the neighbours of the current pixel
239                        final IntValuePixel[] neighbours = getNeighbourPixels_4(this.currentPixel);
240                        // System.err.println("Neighbours: "+outputArray( neighbours ) );
241
242                        // For each of the neighbours, check if the the neighbour
243                        // is already accessible.
244                        for (final IntValuePixel neighbour : neighbours)
245                        {
246                                if (neighbour == null)
247                                        break; // neighbours array is packed, so nulls only occur at
248                                // the end
249
250                                final int idx = neighbour.x + neighbour.y * this.greyscaleImage[0].length;
251
252                                // If the neighbour is not accessible...
253                                if (!this.accessibleMask.get(idx))
254                                {
255                                        // Mark it as accessible...
256                                        this.accessibleMask.set(idx);
257                                        // System.err.println("Making "+neighbour+" accessible" );
258
259                                        // If its greylevel is not lower than the current one...
260                                        if (neighbour.value >= currentPixel.value)
261                                        {
262                                                // Push it onto the heap of boundary pixels
263                                                this.boundaryHeap.push(neighbour);
264                                                // System.err.println("1. Push "+neighbour+", = "+boundaryHeap
265                                                // );
266                                        }
267                                        // If, on the other hand, the greylevel is lower
268                                        // than the current one, enter the current pixel
269                                        // back into the queue of boundary pixels for later
270                                        // processing (with the next edge number), consider
271                                        // the new pixel and process it
272                                        // (this is the water pouring into the local minimum)
273                                        else
274                                        {
275                                                this.boundaryHeap.push(currentPixel);
276                                                // System.err.println("2. Push "+currentPixel+", = "+boundaryHeap
277                                                // );
278                                                this.currentPixel = neighbour;
279                                                currentComponent = new Component(this.currentPixel, featureClasses);
280                                                componentStack.push(currentComponent);
281                                                toContinue = true;
282                                                break;
283                                        }
284                                }
285                        }
286
287                        if (toContinue)
288                                continue;
289
290                        // Accumulate the current pixel to the component at the top of the
291                        // stack. (part 5)
292                        this.componentStack.peek().accumulate(this.currentPixel);
293                        // System.err.println("Added "+currentPixel+" to top component "+componentStack.peek()
294                        // );
295
296                        // Pop the heap of boundary pixels. (part 6)
297                        final IntValuePixel p = this.boundaryHeap.pop();
298                        // System.err.println("Popped "+p+", = "+boundaryHeap );
299
300                        // If the heap is empty, then we're done
301                        if (p == null)
302                                return;
303
304                        // If it's at the same grey-level we process its neighbours (part 6)
305                        if (p.value == currentPixel.value)
306                        {
307                                this.currentPixel = p;
308                        }
309                        // If it's at a higher grey-level we must process the components in
310                        // the stack (part 7)
311                        else
312                        {
313                                this.currentPixel = p;
314                                processComponentStack();
315                        }
316                }
317        }
318
319        private void processComponentStack()
320        {
321                while (this.currentPixel.value > this.componentStack.peek().pivot.value)
322                {
323                        // System.err.println( "Processing stack: "+componentStack );
324
325                        // If the second component on the stack has a greater
326                        // grey-level than the pixel, we set the component's grey-level
327                        // to that of the pixel and quit...
328                        final Component topOfStack = this.componentStack.pop();
329
330                        // System.err.println( "Top of stack gl: "+topOfStack.greyLevel );
331                        // System.err.println(
332                        // "Second stack gl: "+componentStack.peek().greyLevel );
333                        // System.err.println( "Pixel greylevel: "+currentPixel.value );
334
335                        if (this.currentPixel.value < this.componentStack.peek().pivot.value)
336                        {
337                                topOfStack.pivot = this.currentPixel;
338                                this.componentStack.push(topOfStack);
339
340                                fireComponentStackMergeListener(componentStack.peek());
341
342                                return;
343                        }
344
345                        fireComponentStackMergeListener(componentStack.peek(), topOfStack);
346
347                        // Otherwise...
348                        // Join the pixel lists
349                        this.componentStack.peek().merge(topOfStack);
350
351                        // TODO: histories of components
352                }
353        }
354
355        /**
356         * Returns the neighbouring pixels for a given pixel with 4-connectedness.
357         * If the pixel lies outside of the image the result will be null.
358         *
359         * @param pixel
360         *            The pixel to find the neighbours of
361         * @return An array of pixels some of which may be null if they lie outside
362         *         of the image boundary.
363         */
364        private IntValuePixel[] getNeighbourPixels_4(IntValuePixel pixel)
365        {
366                final IntValuePixel[] p = new IntValuePixel[4];
367                final int x = pixel.x;
368                final int y = pixel.y;
369
370                final int height = this.greyscaleImage.length;
371                final int width = this.greyscaleImage[0].length;
372
373                // Find the pixels
374                int c = 0;
375
376                if (x < width - 1)
377                        p[c++] = new IntValuePixel(x + 1, y, greyscaleImage[y][x + 1]);
378
379                if (x > 0)
380                        p[c++] = new IntValuePixel(x - 1, y, greyscaleImage[y][x - 1]);
381
382                if (y < height - 1)
383                        p[c++] = new IntValuePixel(x, y + 1, greyscaleImage[y + 1][x]);
384
385                if (y > 0)
386                        p[c++] = new IntValuePixel(x, y - 1, greyscaleImage[y - 1][x]);
387
388                return p;
389        }
390
391        /**
392         * Add a component stack merge listener
393         *
394         * @param csml
395         *            The {@link ComponentStackMergeListener} to add
396         */
397        public void addComponentStackMergeListener(ComponentStackMergeListener csml)
398        {
399                csmListeners.add(csml);
400        }
401
402        /**
403         * Removes the given {@link ComponentStackMergeListener} from the listeners
404         * list.
405         *
406         * @param csml
407         *            The {@link ComponentStackMergeListener} to remove
408         */
409        public void removeComponentStackMergeListener(ComponentStackMergeListener csml)
410        {
411                csmListeners.remove(csml);
412        }
413
414        /**
415         * Fire the component stack merge listener event for the merging of two
416         * components.
417         *
418         * @param c1
419         *            The first component
420         * @param c2
421         *            The second component
422         */
423        private void fireComponentStackMergeListener(Component c1, Component c2)
424        {
425                for (final ComponentStackMergeListener csm : csmListeners)
426                        csm.componentsMerged(c1, c2);
427        }
428
429        /**
430         * Fire the component stack merge listener event for the upward merge of a
431         * component.
432         *
433         * @param c1
434         *            The component that has been promoted to a higher intensity
435         *            level
436         */
437        private void fireComponentStackMergeListener(Component c1)
438        {
439                for (final ComponentStackMergeListener csm : csmListeners)
440                        csm.componentPromoted(c1);
441        }
442
443        /**
444         * Helper function for debugging arrays
445         *
446         * @param o
447         * @return
448         */
449        @SuppressWarnings("unused")
450        private String outputArray(Object[] o)
451        {
452                final StringBuilder sb = new StringBuilder();
453                sb.append("[");
454                boolean first = true;
455                for (final Object obj : o)
456                {
457                        if (!first)
458                                sb.append(",");
459                        if (obj == null)
460                                sb.append("null");
461                        else
462                                sb.append(obj.toString());
463                        first = false;
464                }
465                sb.append("]");
466                return sb.toString();
467        }
468}