1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 package org.openimaj.image.segmentation;
31
32 import gnu.trove.map.hash.TObjectFloatHashMap;
33
34 import java.util.ArrayList;
35 import java.util.Collections;
36 import java.util.List;
37 import java.util.Set;
38
39 import org.openimaj.citation.annotation.Reference;
40 import org.openimaj.citation.annotation.ReferenceType;
41 import org.openimaj.image.FImage;
42 import org.openimaj.image.Image;
43 import org.openimaj.image.MBFImage;
44 import org.openimaj.image.pixel.ConnectedComponent;
45 import org.openimaj.image.pixel.Pixel;
46 import org.openimaj.image.processing.convolution.FGaussianConvolve;
47 import org.openimaj.image.processor.SinglebandImageProcessor;
48 import org.openimaj.math.graph.SimpleWeightedEdge;
49 import org.openimaj.util.set.DisjointSetForest;
50
51
52
53
54
55
56
57
58
59
60 @Reference(
61 type = ReferenceType.Article,
62 author = {"Felzenszwalb, Pedro F.", "Huttenlocher, Daniel P."},
63 title = "Efficient Graph-Based Image Segmentation",
64 journal = "Int. J. Comput. Vision",
65 volume = "59",
66 number = "2",
67 month = "September",
68 year = "2004",
69 pages = {"167","181"},
70 url = "http://dx.doi.org/10.1023/B:VISI.0000022288.19776.77",
71 publisher = "Kluwer Academic Publishers"
72 )
73 public class FelzenszwalbHuttenlocherSegmenter<I extends Image<?,I> & SinglebandImageProcessor.Processable<Float, FImage, I>> implements Segmenter<I> {
74 protected float sigma = 0.5f;
75 protected float k = 500f / 255f;
76 protected int minSize = 50;
77
78
79
80
81 public FelzenszwalbHuttenlocherSegmenter() {}
82
83
84
85
86
87
88
89 public FelzenszwalbHuttenlocherSegmenter(float sigma, float k, int minSize) {
90 this.sigma = sigma;
91 this.k = k;
92 this.minSize = minSize;
93 }
94
95 @Override
96 public List<ConnectedComponent> segment(I image) {
97 if (((Object)image) instanceof MBFImage) {
98 return segmentImage((MBFImage)((Object)image));
99 } else {
100 return segmentImage(new MBFImage((FImage)((Object)image)));
101 }
102 }
103
104 private float diff(MBFImage image, Pixel p1, Pixel p2) {
105 float sum = 0;
106
107 for (FImage band : image.bands) {
108 float d = band.pixels[p1.y][p1.x] - band.pixels[p2.y][p2.x];
109 sum += d*d;
110 }
111
112 return (float) Math.sqrt(sum);
113 }
114
115 protected List<ConnectedComponent> segmentImage(MBFImage im) {
116 int width = im.getWidth();
117 int height = im.getHeight();
118
119 MBFImage smooth = im.process(new FGaussianConvolve(sigma));
120
121
122 List<SimpleWeightedEdge<Pixel>> edges = new ArrayList<SimpleWeightedEdge<Pixel>>();
123 for (int y = 0; y < height; y++) {
124 for (int x = 0; x < width; x++) {
125 if (x < width-1) {
126 SimpleWeightedEdge<Pixel> p = new SimpleWeightedEdge<Pixel>();
127 p.from = new Pixel(x, y);
128 p.to = new Pixel(x+1, y);
129 p.weight = diff(smooth, p.from, p.to);
130 edges.add(p);
131 }
132
133 if (y < height-1) {
134 SimpleWeightedEdge<Pixel> p = new SimpleWeightedEdge<Pixel>();
135 p.from = new Pixel(x, y);
136 p.to = new Pixel(x, y+1);
137 p.weight = diff(smooth, p.from, p.to);
138 edges.add(p);
139 }
140
141 if ((x < width-1) && (y < height-1)) {
142 SimpleWeightedEdge<Pixel> p = new SimpleWeightedEdge<Pixel>();
143 p.from = new Pixel(x, y);
144 p.to = new Pixel(x+1, y+1);
145 p.weight = diff(smooth, p.from, p.to);
146 edges.add(p);
147 }
148
149 if ((x < width-1) && (y > 0)) {
150 SimpleWeightedEdge<Pixel> p = new SimpleWeightedEdge<Pixel>();
151 p.from = new Pixel(x, y);
152 p.to = new Pixel(x+1, y-1);
153 p.weight = diff(smooth, p.from, p.to);
154 edges.add(p);
155 }
156 }
157 }
158
159
160 DisjointSetForest<Pixel> u = segmentGraph(width*height, edges);
161
162
163
164 for (int i = 0; i < edges.size(); i++) {
165 Pixel a = u.find(edges.get(i).from);
166 Pixel b = u.find(edges.get(i).to);
167
168 if ((a != b) && ((u.size(a) < minSize) || (u.size(b) < minSize)))
169 u.union(a, b);
170 }
171
172 Set<Set<Pixel>> subsets = u.getSubsets();
173 List<ConnectedComponent> ccs = new ArrayList<ConnectedComponent>();
174 for (Set<Pixel> sp : subsets) ccs.add(new ConnectedComponent(sp));
175
176 return ccs;
177 }
178
179 protected DisjointSetForest<Pixel> segmentGraph(int numVertices, List<SimpleWeightedEdge<Pixel>> edges) {
180
181 Collections.sort(edges, SimpleWeightedEdge.ASCENDING_COMPARATOR);
182
183
184 DisjointSetForest<Pixel> u = new DisjointSetForest<Pixel>(numVertices);
185
186 for (SimpleWeightedEdge<Pixel> edge : edges) {
187 u.add(edge.from);
188 u.add(edge.to);
189 }
190
191
192 TObjectFloatHashMap<Pixel> threshold = new TObjectFloatHashMap<Pixel>();
193 for (Pixel p : u) {
194 threshold.put(p, k);
195 }
196
197
198 for (int i = 0; i < edges.size(); i++) {
199 SimpleWeightedEdge<Pixel> pedge = edges.get(i);
200
201
202 Pixel a = u.find(pedge.from);
203 Pixel b = u.find(pedge.to);
204 if (a != b) {
205 if ((pedge.weight <= threshold.get(a)) && (pedge.weight <= threshold.get(b))) {
206 a = u.union(a, b);
207 threshold.put(a, pedge.weight + (k / u.size(a)));
208 }
209 }
210 }
211
212 return u;
213 }
214 }