src/trace/siox.h

   1 #ifndef __SIOX_SEGMENTATOR_H__
   2 #define __SIOX_SEGMENTATOR_H__
   3 /*
   4    Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping
   5
   6    Conversion to C++ for Inkscape by Bob Jamison
   7
   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
  11
  12    http://www.apache.org/licenses/LICENSE-2.0
  13
  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  */
  20
  21 #include <map>
  22 #include <vector>
  23
  24 namespace org
  25 {
  26 namespace siox
  27 {
  28
  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  */
  65
  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:
  73
  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         {}
 106
 107     float minBgDist;
 108     long  indexMinBg;
 109     float minFgDist;
 110     long  indexMinFg;
 111
 112  };
 113
 114
 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         {}
 146
 147     float C;
 148     float L;
 149     float A;
 150     float B;
 151 };
 152
 153
 154 class SioxSegmentator
 155 {
 156 public:
 157
 158     /** Confidence corresponding to a certain foreground region (equals one). */
 159     static const float CERTAIN_FOREGROUND_CONFIDENCE;  //=1.0f;
 160
 161     /** Confidence for a region likely being foreground.*/
 162     static const float FOREGROUND_CONFIDENCE;  //=0.8f;
 163
 164     /** Confidence for foreground or background type being equally likely.*/
 165     static const float UNKNOWN_REGION_CONFIDENCE;  //=0.5f;
 166
 167     /** Confidence for a region likely being background.*/
 168     static const float BACKGROUND_CONFIDENCE;  //=0.1f;
 169
 170     /** Confidence corresponding to a certain background reagion (equals zero). */
 171     static const float CERTAIN_BACKGROUND_CONFIDENCE;  //=0.0f;
 172
 173
 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);
 184
 185     /**
 186      * Destructor
 187      */
 188     virtual ~SioxSegmentator();
 189
 190
 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 imageSize number of values in image
 209      * @param cm Confidence matrix specifying the probability of an image
 210      *        belonging to the foreground before and after the segmentation.
 211      * @param smoothness Number of smoothing steps in the post processing.
 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, int imageSize,
 219                     float *cm, int cmSize,
 220                     int smoothness, double sizeFactorToKeep);
 221
 222     /**
 223      * Clears given confidence matrix except entries for the largest connected
 224      * component and every component with
 225      * <CODE>size*sizeFactorToKeep >= sizeOfLargestComponent</CODE>.
 226      *
 227      * @param cm  Confidence matrix to be analysed
 228      * @param threshold Pixel visibility threshold.
 229      *        Exactly those cm entries larger than threshold are considered
 230      *        to be a "visible" foreground pixel.
 231      * @param sizeFactorToKeep This method keeps the largest connected
 232      *        component plus any component with size at least
 233      *        <CODE>sizeOfLargestComponent/sizeFactorToKeep</CODE>.
 234      */
 235     void keepOnlyLargeComponents(float *cm, int cmSize,
 236                                  float threshold,
 237                                  double sizeFactorToKeep);
 238
 239     /**
 240      * Depth first search pixels in a foreground component.
 241      *
 242      * @param cm confidence matrix to be searched.
 243      * @param i starting position as index to confidence matrix.
 244      * @param threshold defines the minimum value at which a pixel is
 245      *        considered foreground.
 246      * @param curlabel label no of component.
 247      * @return size in pixel of the component found.
 248      */
 249     int depthFirstSearch(float *cm, int i, float threshold, int curLabel);
 250
 251     /**
 252      * Refines the classification stored in the confidence matrix by modifying
 253      * the confidences for regions which have characteristics to both
 254      * foreground and background if they fall into the specified square.
 255      * <P>
 256      * The can be used in displaying the image by assigning the alpha values
 257      * of the pixels according to the confidence entries.
 258      * <P>
 259      * In the algorithm descriptions and examples GUIs this step is referrered
 260      * to as <EM>Detail Refinement (Brush)</EM>.
 261      *
 262      * @param x Horizontal coordinate of the squares center.
 263      * @param y Vertical coordinate of the squares center.
 264      * @param brushmode Mode of the refinement applied, <CODE>ADD_EDGE</CODE>
 265      *        or <CODE>SUB_EDGE</CODE>. Add mode only modifies pixels
 266      *        formerly classified as background, sub mode only those
 267      *        formerly classified as foreground.
 268      * @param threshold Threshold for the add and sub refinement, deciding
 269      *        at the confidence level to stop at.
 270      * @param cf The confidence matrix to modify, generated by
 271      *        <CODE>segmentate</CODE>, possibly already refined by privious
 272      *        calls to <CODE>subpixelRefine</CODE>.
 273      * @param brushsize Halfed diameter of the square shaped brush.
 274      *
 275      * @see #segmentate
 276      */
 277     void subpixelRefine(int x, int y, int brushmode,
 278                              float threshold, float *cf, int brushsize);
 279
 280     /**
 281      * Refines the classification stored in the confidence matrix by modifying
 282      * the confidences for regions which have characteristics to both
 283      * foreground and background if they fall into the specified area.
 284      * <P>
 285      * The can be used in displaying the image by assigning the alpha values
 286      * of the pixels according to the confidence entries.
 287      * <P>
 288      * In the algorithm descriptions and examples GUIs this step is referrered
 289      * to as <EM>Detail Refinement (Brush)</EM>.
 290      *
 291      * @param area Area in which the reworking of the segmentation is
 292      *        applied to.
 293      * @param brushmode Mode of the refinement applied, <CODE>ADD_EDGE</CODE>
 294      *        or <CODE>SUB_EDGE</CODE>. Add mode only modifies pixels
 295      *        formerly classified as background, sub mode only those
 296      *        formerly classified as foreground.
 297      * @param threshold Threshold for the add and sub refinement, deciding
 298      *        at the confidence level to stop at.
 299      * @param cf The confidence matrix to modify, generated by
 300      *        <CODE>segmentate</CODE>, possibly already refined by privious
 301      *        calls to <CODE>subpixelRefine</CODE>.
 302      *
 303      * @see #segmentate
 304      */
 305     bool subpixelRefine(int xa, int ya, int dx, int dy,
 306                                      int brushmode,
 307                                      float threshold, float *cf);
 308     /**
 309      * A region growing algorithms used to fill up the confidence matrix
 310      * with <CODE>CERTAIN_FOREGROUND_CONFIDENCE</CODE> for corresponding
 311      * areas of equal colors.
 312      * <P>
 313      * Basically, the method works like the <EM>Magic Wand<EM> with a
 314      * tolerance threshold of zero.
 315      *
 316      * @param cm confidence matrix to be searched
 317      * @param image image to be searched
 318      */
 319     void fillColorRegions(float *cm, int cmSize, unsigned long *image);
 320
 321 private:
 322
 323     /**
 324      * Prevent this from being used
 325      */
 326     SioxSegmentator();
 327
 328     /** error logging **/
 329     void error(char *format, ...);
 330
 331     /** trace logging **/
 332     void trace(char *format, ...);
 333
 334     typedef enum
 335         {
 336         ADD_EDGE, /** Add mode for the subpixel refinement. */
 337         SUB_EDGE  /** Subtract mode for the subpixel refinement. */
 338         } BrushMode;
 339
 340     // instance fields:
 341
 342     /** Horizontal resolution of the image to be segmentated. */
 343     int imgWidth;
 344
 345     /** Vertical resolution of the image to be segmentated. */
 346     int imgHeight;
 347
 348     /** Stores component label (index) by pixel it belongs to. */
 349     int *labelField;
 350
 351     /**
 352      * LAB color values of pixels that are definitly known background.
 353      * Entries are of form {l,a,b}.
 354      */
 355     std::vector<CLAB> knownBg;
 356
 357     /**
 358      * LAB color values of pixels that are definitly known foreground.
 359      * Entries are of form {l,a,b}.
 360      */
 361     std::vector<CLAB> knownFg;
 362
 363     /** Holds background signature (a characteristic subset of the bg.) */
 364     std::vector<CLAB> bgSignature;
 365
 366     /** Holds foreground signature (a characteristic subset of the fg).*/
 367     std::vector<CLAB> fgSignature;
 368
 369     /** Size of cluster on lab axis. */
 370     float *limits;
 371
 372     /** Maximum distance of two lab values. */
 373     float clusterSize;
 374
 375     /**
 376      * Stores Tupels for fast access to nearest background/foreground pixels.
 377      */
 378     std::map<unsigned long, Tupel> hs;
 379
 380     /** Size of the biggest blob.*/
 381     int regionCount;
 382
 383     /** Copy of the original image, needed for detail refinement. */
 384     long *origImage;
 385     long origImageSize;
 386
 387     /** A flag that stores if the segmentation algorithm has already ran.*/
 388     bool segmentated;
 389
 390 };
 391
 392 } //namespace siox
 393 } //namespace org
 394
 395 #endif /* __SIOX_SEGMENTATOR_H__ */
 396