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.connectedcomponent;
31
32 import java.util.ArrayList;
33 import java.util.LinkedHashSet;
34 import java.util.List;
35
36 import org.openimaj.image.FImage;
37 import org.openimaj.image.analyser.ImageAnalyser;
38 import org.openimaj.image.pixel.ConnectedComponent;
39 import org.openimaj.image.pixel.Pixel;
40
41 /**
42 * A Connected Component Labeler for grey-level images. This class can be used
43 * to transform an image that represents a map of labeled objects into a list of
44 * {@link ConnectedComponent}s.
45 * <p>
46 * Internally we use a flood-fill approach to finding the
47 * {@link ConnectedComponent}s.
48 *
49 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
50 */
51 public class GreyscaleConnectedComponentLabeler implements ImageAnalyser<FImage> {
52 List<ConnectedComponent> components;
53
54 /**
55 * Syntactic sugar for calling {@link #analyseImage(FImage)} followed by
56 * {@link #getComponents()};
57 *
58 * @param image
59 * the image to extract components from
60 * @return the extracted components.
61 */
62 public List<ConnectedComponent> findComponents(FImage image) {
63 analyseImage(image);
64 return components;
65 }
66
67 protected ConnectedComponent floodFill(FImage image, Pixel start, int[][] output, int color) {
68 final ConnectedComponent cc = new ConnectedComponent();
69 // Flood-fill (node, target-color, replacement-color):
70 // 1. Set Q to the empty queue.
71 // Queue<Pixel> queue = new LinkedList<Pixel>();
72 final LinkedHashSet<Pixel> queue = new LinkedHashSet<Pixel>();
73
74 // 2. If the color of node is not equal to target-color, return.
75 final float targetColour = image.pixels[start.y][start.x];
76
77 // 3. Add node to Q.
78 queue.add(start);
79 // 4. For each element n of Q:
80 while (queue.size() > 0) {
81 // Pixel n = queue.poll();
82 final Pixel n = queue.iterator().next();
83 queue.remove(n);
84
85 // 5. If the color of n is equal to target-color:
86 if (image.pixels[n.y][n.x] == targetColour && output[n.y][n.x] != color) {
87 // 6. Set w and e equal to n.
88 int e = n.x, w = n.x;
89 // 7. Move w to the west until the color of the node to the west
90 // of w no longer matches target-color.
91 while (w > 0 && image.pixels[n.y][w - 1] == targetColour)
92 w--;
93
94 // 8. Move e to the east until the color of the node to the east
95 // of e no longer matches target-color.
96 while (e < image.width - 1 && image.pixels[n.y][e + 1] == targetColour)
97 e++;
98
99 // 9. Set the color of nodes between w and e to
100 // replacement-color.
101 for (int i = w; i <= e; i++) {
102 output[n.y][i] = color;
103 cc.addPixel(i, n.y);
104
105 // 10. For each node n between w and e:
106 final int north = n.y - 1;
107 final int south = n.y + 1;
108 // 11. If the color of the node to the north of n is
109 // target-color, add that node to Q.
110 if (north >= 0 && image.pixels[north][i] == targetColour && output[north][i] != color)
111 queue.add(new Pixel(i, north));
112 // If the color of the node to the south of n is
113 // target-color, add that node to Q.
114 if (south < image.height && image.pixels[south][i] == targetColour && output[south][i] != color)
115 queue.add(new Pixel(i, south));
116 }
117 // 12. Continue looping until Q is exhausted.
118 }
119 }
120 // 13. Return.
121 return cc;
122 }
123
124 @Override
125 public void analyseImage(FImage image) {
126 components = new ArrayList<ConnectedComponent>();
127
128 final int[][] labels = new int[image.height][image.width];
129 int nextColor = 1;
130
131 for (int y = 0; y < image.height; y++) {
132 for (int x = 0; x < image.width; x++) {
133 if (labels[y][x] == 0) {
134 components.add(floodFill(image, new Pixel(x, y), labels, nextColor));
135 nextColor++;
136 }
137 }
138 }
139 }
140
141 /**
142 * @return the list of components found in the last call to
143 * {@link #analyseImage(FImage)}.
144 */
145 public List<ConnectedComponent> getComponents() {
146 return components;
147 }
148 }