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 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);
 220
 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);
 237
 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);
 249
 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);
 278
 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);
 319
 320 private:
 321
 322     /**
 323      * Prevent this from being used
 324      */
 325     SioxSegmentator();
 326
 327     /** error logging **/
 328     void error(char *format, ...);
 329
 330     /** trace logging **/
 331     void trace(char *format, ...);
 332
 333     typedef enum
 334         {
 335         ADD_EDGE, /** Add mode for the subpixel refinement. */
 336         SUB_EDGE  /** Subtract mode for the subpixel refinement. */
 337         } BrushMode;
 338
 339     // instance fields:
 340
 341     /** Horizontal resolution of the image to be segmentated. */
 342     int imgWidth;
 343
 344     /** Vertical resolution of the image to be segmentated. */
 345     int imgHeight;
 346
 347     /** Number of pixels and/or confidence matrix values to process.
 348         equal to imgWidth * imgHeight
 349     */
 350     long pixelCount;
 351
 352     /** Stores component label (index) by pixel it belongs to. */
 353     int *labelField;
 354
 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;
 360
 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;
 366
 367     /** Holds background signature (a characteristic subset of the bg.) */
 368     std::vector<CLAB> bgSignature;
 369
 370     /** Holds foreground signature (a characteristic subset of the fg).*/
 371     std::vector<CLAB> fgSignature;
 372
 373     /** Size of cluster on lab axis. */
 374     float *limits;
 375
 376     /** Maximum distance of two lab values. */
 377     float clusterSize;
 378
 379     /**
 380      * Stores Tupels for fast access to nearest background/foreground pixels.
 381      */
 382     std::map<unsigned long, Tupel> hs;
 383
 384     /** Size of the biggest blob.*/
 385     int regionCount;
 386
 387     /** Copy of the original image, needed for detail refinement. */
 388     long *origImage;
 389     long origImageSize;
 390
 391     /** A flag that stores if the segmentation algorithm has already ran.*/
 392     bool segmentated;
 393
 394 };
 395
 396 } //namespace siox
 397 } //namespace org
 398
 399 #endif /* __SIOX_SEGMENTATOR_H__ */
 400