src/trace/siox.h

   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 SioxSegmentator::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 SioxSegmentator::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