1 #ifndef __SIOX_SEGMENTATOR_H__\r
2 #define __SIOX_SEGMENTATOR_H__\r
3 /*\r
4 Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping\r
5 \r
6 Conversion to C++ for Inkscape by Bob Jamison\r
7 \r
8 Licensed under the Apache License, Version 2.0 (the "License");\r
9 you may not use this file except in compliance with the License.\r
10 You may obtain a copy of the License at\r
11 \r
12 http://www.apache.org/licenses/LICENSE-2.0\r
13 \r
14 Unless required by applicable law or agreed to in writing, software\r
15 distributed under the License is distributed on an "AS IS" BASIS,\r
16 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
17 See the License for the specific language governing permissions and\r
18 limitations under the License.\r
19 */\r
20 \r
21 #include <map>\r
22 #include <vector>\r
23 \r
24 namespace org\r
25 {\r
26 namespace siox\r
27 {\r
28 \r
29 /**\r
30 * Image segmentator based on\r
31 *<em>SIOX: Simple Interactive Object Extraction</em>.\r
32 * <P>\r
33 * To segmentate an image one has to perform the following steps.\r
34 * <OL><LI>Construct an instance of <code>SioxSegmentator</code>.\r
35 * </LI><LI>Create a confidence matrix, where each entry marks its\r
36 * corresponding image pixel to belong to the foreground, to the\r
37 * background, or being of unknown type.\r
38 * </LI><LI>Call <code>segmentate</code> on the image with the confidence\r
39 * matrix. This stores the result as new foreground confidence into\r
40 * the confidence matrix, with each entry being either\r
41 * zero (<code>CERTAIN_BACKGROUND_CONFIDENCE</code>) or one\r
42 * (<code>CERTAIN_FOREGROUND_CONFIDENCE</code>).\r
43 * </LI><LI>Optionally call <code>subpixelRefine</code> to areas\r
44 * where pixels contain both foreground and background (e.g.\r
45 * object borders or highly detailed features like flowing hairs).\r
46 * The pixel are then assigned confidence values bwetween zero and\r
47 * one to give them a measure of "foregroundness".\r
48 * This step may be repeated as often as needed.\r
49 * </LI></OL>\r
50 * <P>\r
51 * For algorithm documentation refer to\r
52 * G. Friedland, K. Jantz, L. Knipping, R. Rojas:<i>\r
53 * Image Segmentation by Uniform Color Clustering\r
54 * -- Approach and Benchmark Results</i>,\r
55 * <A HREF="http://www.inf.fu-berlin.de/inst/pubs/tr-b-05-07.pdf">Technical Report B-05-07</A>,\r
56 * Department of Computer Science, Freie Universitaet Berlin, June 2005.<br>\r
57 * <P>\r
58 * See <A HREF="http://www.siox.org/" target="_new">http://www.siox.org</A> for more information.<br>\r
59 * <P>\r
60 * Algorithm idea by Gerald Friedland.\r
61 *\r
62 * @author Gerald Friedland, Kristian Jantz, Lars Knipping\r
63 * @version 1.12\r
64 */\r
65 \r
66 /**\r
67 * Helper class for storing the minimum distances to a cluster centroid\r
68 * in background and foreground and the index to the centroids in each\r
69 * signature for a given color.\r
70 */\r
71 class Tupel {\r
72 public:\r
73 \r
74 Tupel()\r
75 {\r
76 minBgDist = 0.0f;\r
77 indexMinBg = 0;\r
78 minFgDist = 0.0f;\r
79 indexMinFg = 0;\r
80 }\r
81 Tupel(float minBgDistArg, long indexMinBgArg,\r
82 float minFgDistArg, long indexMinFgArg)\r
83 {\r
84 minBgDist = minBgDistArg;\r
85 indexMinBg = indexMinBgArg;\r
86 minFgDist = minFgDistArg;\r
87 indexMinFg = indexMinFgArg;\r
88 }\r
89 Tupel(const Tupel &other)\r
90 {\r
91 minBgDist = other.minBgDist;\r
92 indexMinBg = other.indexMinBg;\r
93 minFgDist = other.minFgDist;\r
94 indexMinFg = other.indexMinFg;\r
95 }\r
96 Tupel &operator=(const Tupel &other)\r
97 {\r
98 minBgDist = other.minBgDist;\r
99 indexMinBg = other.indexMinBg;\r
100 minFgDist = other.minFgDist;\r
101 indexMinFg = other.indexMinFg;\r
102 return *this;\r
103 }\r
104 virtual ~Tupel()\r
105 {}\r
106 \r
107 float minBgDist;\r
108 long indexMinBg;\r
109 float minFgDist;\r
110 long indexMinFg;\r
111 \r
112 };\r
113 \r
114 \r
115 class CLAB\r
116 {\r
117 public:\r
118 CLAB()\r
119 {\r
120 C = L = A = B = 0.0f;\r
121 }\r
122 CLAB(float lArg, float aArg, float bArg)\r
123 {\r
124 C = 0.0f;\r
125 L = lArg;\r
126 A = aArg;\r
127 B = bArg;\r
128 }\r
129 CLAB(const CLAB &other)\r
130 {\r
131 C = other.C;\r
132 L = other.L;\r
133 A = other.A;\r
134 B = other.B;\r
135 }\r
136 CLAB &operator=(const CLAB &other)\r
137 {\r
138 C = other.C;\r
139 L = other.L;\r
140 A = other.A;\r
141 B = other.B;\r
142 return *this;\r
143 }\r
144 virtual ~CLAB()\r
145 {}\r
146 \r
147 float C;\r
148 float L;\r
149 float A;\r
150 float B;\r
151 };\r
152 \r
153 \r
154 class SioxSegmentator\r
155 {\r
156 public:\r
157 \r
158 /** Confidence corresponding to a certain foreground region (equals one). */\r
159 static const float CERTAIN_FOREGROUND_CONFIDENCE; //=1.0f;\r
160 \r
161 /** Confidence for a region likely being foreground.*/\r
162 static const float FOREGROUND_CONFIDENCE; //=0.8f;\r
163 \r
164 /** Confidence for foreground or background type being equally likely.*/\r
165 static const float UNKNOWN_REGION_CONFIDENCE; //=0.5f;\r
166 \r
167 /** Confidence for a region likely being background.*/\r
168 static const float BACKGROUND_CONFIDENCE; //=0.1f;\r
169 \r
170 /** Confidence corresponding to a certain background reagion (equals zero). */\r
171 static const float CERTAIN_BACKGROUND_CONFIDENCE; //=0.0f;\r
172 \r
173 \r
174 /**\r
175 * Constructs a SioxSegmentator Object to be used for image segmentation.\r
176 *\r
177 * @param w X resolution of the image to be segmentated.\r
178 * @param h Y resolution of the image to be segmentated.\r
179 * @param limits Size of the cluster on LAB axises.\r
180 * If <code>null</code>, the default value {0.64f,1.28f,2.56f}\r
181 * is used.\r
182 */\r
183 SioxSegmentator(int w, int h, float *limitsArg, int limitsSize);\r
184 \r
185 /**\r
186 * Destructor\r
187 */\r
188 virtual ~SioxSegmentator();\r
189 \r
190 \r
191 /**\r
192 * Segmentates the given image with information from the confidence\r
193 * matrix.\r
194 * <P>\r
195 * The confidence entries of <code>BACKGROUND_CONFIDENCE</code> or less\r
196 * are mark known background pixel for the segmentation, those\r
197 * of at least <code>FOREGROUND_CONFIDENCE</code> mark known\r
198 * foreground pixel for the segmentation. Any other entry is treated\r
199 * as region of unknown affiliation.\r
200 * <P>\r
201 * As result, each pixel is classified either as foregroound or\r
202 * background, stored back into its <code>cm</code> entry as confidence\r
203 * <code>CERTAIN_FOREGROUND_CONFIDENCE</code> or\r
204 * <code>CERTAIN_BACKGROUND_CONFIDENCE</code>.\r
205 *\r
206 * @param image Pixel data of the image to be segmentated.\r
207 * Every integer represents one ARGB-value.\r
208 * @param imageSize number of values in image\r
209 * @param cm Confidence matrix specifying the probability of an image\r
210 * belonging to the foreground before and after the segmentation.\r
211 * @param smoothness Number of smoothing steps in the post processing.\r
212 * @param sizeFactorToKeep Segmentation retains the largest connected\r
213 * foreground component plus any component with size at least\r
214 * <CODE>sizeOfLargestComponent/sizeFactorToKeep</CODE>.\r
215 * @return <CODE>true</CODE> if the segmentation algorithm succeeded,\r
216 * <CODE>false</CODE> if segmentation is impossible\r
217 */\r
218 bool segmentate(unsigned long *image, int imageSize,\r
219 float *cm, int cmSize,\r
220 int smoothness, double sizeFactorToKeep);\r
221 \r
222 /**\r
223 * Clears given confidence matrix except entries for the largest connected\r
224 * component and every component with\r
225 * <CODE>size*sizeFactorToKeep >= sizeOfLargestComponent</CODE>.\r
226 *\r
227 * @param cm Confidence matrix to be analysed\r
228 * @param threshold Pixel visibility threshold.\r
229 * Exactly those cm entries larger than threshold are considered\r
230 * to be a "visible" foreground pixel.\r
231 * @param sizeFactorToKeep This method keeps the largest connected\r
232 * component plus any component with size at least\r
233 * <CODE>sizeOfLargestComponent/sizeFactorToKeep</CODE>.\r
234 */\r
235 void keepOnlyLargeComponents(float *cm, int cmSize,\r
236 float threshold,\r
237 double sizeFactorToKeep);\r
238 \r
239 /**\r
240 * Depth first search pixels in a foreground component.\r
241 *\r
242 * @param cm confidence matrix to be searched.\r
243 * @param i starting position as index to confidence matrix.\r
244 * @param threshold defines the minimum value at which a pixel is\r
245 * considered foreground.\r
246 * @param curlabel label no of component.\r
247 * @return size in pixel of the component found.\r
248 */\r
249 int depthFirstSearch(float *cm, int i, float threshold, int curLabel);\r
250 \r
251 /**\r
252 * Refines the classification stored in the confidence matrix by modifying\r
253 * the confidences for regions which have characteristics to both\r
254 * foreground and background if they fall into the specified square.\r
255 * <P>\r
256 * The can be used in displaying the image by assigning the alpha values\r
257 * of the pixels according to the confidence entries.\r
258 * <P>\r
259 * In the algorithm descriptions and examples GUIs this step is referrered\r
260 * to as <EM>Detail Refinement (Brush)</EM>.\r
261 *\r
262 * @param x Horizontal coordinate of the squares center.\r
263 * @param y Vertical coordinate of the squares center.\r
264 * @param brushmode Mode of the refinement applied, <CODE>ADD_EDGE</CODE>\r
265 * or <CODE>SUB_EDGE</CODE>. Add mode only modifies pixels\r
266 * formerly classified as background, sub mode only those\r
267 * formerly classified as foreground.\r
268 * @param threshold Threshold for the add and sub refinement, deciding\r
269 * at the confidence level to stop at.\r
270 * @param cf The confidence matrix to modify, generated by\r
271 * <CODE>segmentate</CODE>, possibly already refined by privious\r
272 * calls to <CODE>subpixelRefine</CODE>.\r
273 * @param brushsize Halfed diameter of the square shaped brush.\r
274 *\r
275 * @see #segmentate\r
276 */\r
277 void subpixelRefine(int x, int y, int brushmode,\r
278 float threshold, float *cf, int brushsize);\r
279 \r
280 /**\r
281 * Refines the classification stored in the confidence matrix by modifying\r
282 * the confidences for regions which have characteristics to both\r
283 * foreground and background if they fall into the specified area.\r
284 * <P>\r
285 * The can be used in displaying the image by assigning the alpha values\r
286 * of the pixels according to the confidence entries.\r
287 * <P>\r
288 * In the algorithm descriptions and examples GUIs this step is referrered\r
289 * to as <EM>Detail Refinement (Brush)</EM>.\r
290 *\r
291 * @param area Area in which the reworking of the segmentation is\r
292 * applied to.\r
293 * @param brushmode Mode of the refinement applied, <CODE>ADD_EDGE</CODE>\r
294 * or <CODE>SUB_EDGE</CODE>. Add mode only modifies pixels\r
295 * formerly classified as background, sub mode only those\r
296 * formerly classified as foreground.\r
297 * @param threshold Threshold for the add and sub refinement, deciding\r
298 * at the confidence level to stop at.\r
299 * @param cf The confidence matrix to modify, generated by\r
300 * <CODE>segmentate</CODE>, possibly already refined by privious\r
301 * calls to <CODE>subpixelRefine</CODE>.\r
302 *\r
303 * @see #segmentate\r
304 */\r
305 bool subpixelRefine(int xa, int ya, int dx, int dy,\r
306 int brushmode,\r
307 float threshold, float *cf);\r
308 /**\r
309 * A region growing algorithms used to fill up the confidence matrix\r
310 * with <CODE>CERTAIN_FOREGROUND_CONFIDENCE</CODE> for corresponding\r
311 * areas of equal colors.\r
312 * <P>\r
313 * Basically, the method works like the <EM>Magic Wand<EM> with a\r
314 * tolerance threshold of zero.\r
315 *\r
316 * @param cm confidence matrix to be searched\r
317 * @param image image to be searched\r
318 */\r
319 void fillColorRegions(float *cm, int cmSize, unsigned long *image);\r
320 \r
321 private:\r
322 \r
323 /**\r
324 * Prevent this from being used\r
325 */\r
326 SioxSegmentator();\r
327 \r
328 /** error logging **/\r
329 void error(char *format, ...);\r
330 \r
331 /** trace logging **/\r
332 void trace(char *format, ...);\r
333 \r
334 typedef enum\r
335 {\r
336 ADD_EDGE, /** Add mode for the subpixel refinement. */\r
337 SUB_EDGE /** Subtract mode for the subpixel refinement. */\r
338 } BrushMode;\r
339 \r
340 // instance fields:\r
341 \r
342 /** Horizontal resolution of the image to be segmentated. */\r
343 int imgWidth;\r
344 \r
345 /** Vertical resolution of the image to be segmentated. */\r
346 int imgHeight;\r
347 \r
348 /** Stores component label (index) by pixel it belongs to. */\r
349 int *labelField;\r
350 \r
351 /**\r
352 * LAB color values of pixels that are definitly known background.\r
353 * Entries are of form {l,a,b}.\r
354 */\r
355 std::vector<CLAB> knownBg;\r
356 \r
357 /**\r
358 * LAB color values of pixels that are definitly known foreground.\r
359 * Entries are of form {l,a,b}.\r
360 */\r
361 std::vector<CLAB> knownFg;\r
362 \r
363 /** Holds background signature (a characteristic subset of the bg.) */\r
364 std::vector<CLAB> bgSignature;\r
365 \r
366 /** Holds foreground signature (a characteristic subset of the fg).*/\r
367 std::vector<CLAB> fgSignature;\r
368 \r
369 /** Size of cluster on lab axis. */\r
370 float *limits;\r
371 \r
372 /** Maximum distance of two lab values. */\r
373 float clusterSize;\r
374 \r
375 /**\r
376 * Stores Tupels for fast access to nearest background/foreground pixels.\r
377 */\r
378 std::map<unsigned long, Tupel> hs;\r
379 \r
380 /** Size of the biggest blob.*/\r
381 int regionCount;\r
382 \r
383 /** Copy of the original image, needed for detail refinement. */\r
384 long *origImage;\r
385 long origImageSize;\r
386 \r
387 /** A flag that stores if the segmentation algorithm has already ran.*/\r
388 bool segmentated;\r
389 \r
390 };\r
391 \r
392 } //namespace siox\r
393 } //namespace org\r
394 \r
395 #endif /* __SIOX_SEGMENTATOR_H__ */\r
396 \r