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