X-Git-Url: https://git.tokkee.org/?a=blobdiff_plain;f=src%2Ftrace%2Fsiox.h;h=42fd304219237be2f1772d9a30efeb9eec6bc0ff;hb=80d34fe4a953d704430b44c6201a4fcbf455dfc6;hp=bb955f28adebbe8d0ed410f4facc52cb130c9dac;hpb=41629a744eebd14552631d1a23cfbe9e6a4cf358;p=inkscape.git diff --git a/src/trace/siox.h b/src/trace/siox.h index bb955f28a..42fd30421 100644 --- a/src/trace/siox.h +++ b/src/trace/siox.h @@ -1,396 +1,669 @@ -#ifndef __SIOX_SEGMENTATOR_H__ -#define __SIOX_SEGMENTATOR_H__ -/* - Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping - - Conversion to C++ for Inkscape by Bob Jamison - - Licensed under the Apache License, Version 2.0 (the "License"); - you may not use this file except in compliance with the License. - You may obtain a copy of the License at - - http://www.apache.org/licenses/LICENSE-2.0 - - Unless required by applicable law or agreed to in writing, software - distributed under the License is distributed on an "AS IS" BASIS, - WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - See the License for the specific language governing permissions and - limitations under the License. - */ - -#include -#include - -namespace org -{ -namespace siox -{ - -/** - * Image segmentator based on - *SIOX: Simple Interactive Object Extraction. - *

- * To segmentate an image one has to perform the following steps. - *

  1. Construct an instance of SioxSegmentator. - *
  2. Create a confidence matrix, where each entry marks its - * corresponding image pixel to belong to the foreground, to the - * background, or being of unknown type. - *
  3. Call segmentate on the image with the confidence - * matrix. This stores the result as new foreground confidence into - * the confidence matrix, with each entry being either - * zero (CERTAIN_BACKGROUND_CONFIDENCE) or one - * (CERTAIN_FOREGROUND_CONFIDENCE). - *
  4. Optionally call subpixelRefine to areas - * where pixels contain both foreground and background (e.g. - * object borders or highly detailed features like flowing hairs). - * The pixel are then assigned confidence values bwetween zero and - * one to give them a measure of "foregroundness". - * This step may be repeated as often as needed. - *
- *

- * For algorithm documentation refer to - * G. Friedland, K. Jantz, L. Knipping, R. Rojas: - * Image Segmentation by Uniform Color Clustering - * -- Approach and Benchmark Results, - * Technical Report B-05-07, - * Department of Computer Science, Freie Universitaet Berlin, June 2005.
- *

- * See http://www.siox.org for more information.
- *

- * Algorithm idea by Gerald Friedland. - * - * @author Gerald Friedland, Kristian Jantz, Lars Knipping - * @version 1.12 - */ - -/** - * Helper class for storing the minimum distances to a cluster centroid - * in background and foreground and the index to the centroids in each - * signature for a given color. - */ -class Tupel { -public: - - Tupel() - { - minBgDist = 0.0f; - indexMinBg = 0; - minFgDist = 0.0f; - indexMinFg = 0; - } - Tupel(float minBgDistArg, long indexMinBgArg, - float minFgDistArg, long indexMinFgArg) - { - minBgDist = minBgDistArg; - indexMinBg = indexMinBgArg; - minFgDist = minFgDistArg; - indexMinFg = indexMinFgArg; - } - Tupel(const Tupel &other) - { - minBgDist = other.minBgDist; - indexMinBg = other.indexMinBg; - minFgDist = other.minFgDist; - indexMinFg = other.indexMinFg; - } - Tupel &operator=(const Tupel &other) - { - minBgDist = other.minBgDist; - indexMinBg = other.indexMinBg; - minFgDist = other.minFgDist; - indexMinFg = other.indexMinFg; - return *this; - } - virtual ~Tupel() - {} - - float minBgDist; - long indexMinBg; - float minFgDist; - long indexMinFg; - - }; - - -class CLAB -{ -public: - CLAB() - { - C = L = A = B = 0.0f; - } - CLAB(float lArg, float aArg, float bArg) - { - C = 0.0f; - L = lArg; - A = aArg; - B = bArg; - } - CLAB(const CLAB &other) - { - C = other.C; - L = other.L; - A = other.A; - B = other.B; - } - CLAB &operator=(const CLAB &other) - { - C = other.C; - L = other.L; - A = other.A; - B = other.B; - return *this; - } - virtual ~CLAB() - {} - - float C; - float L; - float A; - float B; -}; - - -class SioxSegmentator -{ -public: - - /** Confidence corresponding to a certain foreground region (equals one). */ - static const float CERTAIN_FOREGROUND_CONFIDENCE=1.0f; - - /** Confidence for a region likely being foreground.*/ - static const float FOREGROUND_CONFIDENCE=0.8f; - - /** Confidence for foreground or background type being equally likely.*/ - static const float UNKNOWN_REGION_CONFIDENCE=0.5f; - - /** Confidence for a region likely being background.*/ - static const float BACKGROUND_CONFIDENCE=0.1f; - - /** Confidence corresponding to a certain background reagion (equals zero). */ - static const float CERTAIN_BACKGROUND_CONFIDENCE=0.0f; - - - /** - * Constructs a SioxSegmentator Object to be used for image segmentation. - * - * @param w X resolution of the image to be segmentated. - * @param h Y resolution of the image to be segmentated. - * @param limits Size of the cluster on LAB axises. - * If null, the default value {0.64f,1.28f,2.56f} - * is used. - */ - SioxSegmentator(int w, int h, float *limitsArg, int limitsSize); - - /** - * Destructor - */ - virtual ~SioxSegmentator(); - - - /** - * Segmentates the given image with information from the confidence - * matrix. - *

- * The confidence entries of BACKGROUND_CONFIDENCE or less - * are mark known background pixel for the segmentation, those - * of at least FOREGROUND_CONFIDENCE mark known - * foreground pixel for the segmentation. Any other entry is treated - * as region of unknown affiliation. - *

- * As result, each pixel is classified either as foregroound or - * background, stored back into its cm entry as confidence - * CERTAIN_FOREGROUND_CONFIDENCE or - * CERTAIN_BACKGROUND_CONFIDENCE. - * - * @param image Pixel data of the image to be segmentated. - * Every integer represents one ARGB-value. - * @param imageSize number of values in image - * @param cm Confidence matrix specifying the probability of an image - * belonging to the foreground before and after the segmentation. - * @param smoothness Number of smoothing steps in the post processing. - * @param sizeFactorToKeep Segmentation retains the largest connected - * foreground component plus any component with size at least - * sizeOfLargestComponent/sizeFactorToKeep. - * @return true if the segmentation algorithm succeeded, - * false if segmentation is impossible - */ - bool segmentate(unsigned long *image, int imageSize, - float *cm, int cmSize, - int smoothness, double sizeFactorToKeep); - - /** - * Clears given confidence matrix except entries for the largest connected - * component and every component with - * size*sizeFactorToKeep >= sizeOfLargestComponent. - * - * @param cm Confidence matrix to be analysed - * @param threshold Pixel visibility threshold. - * Exactly those cm entries larger than threshold are considered - * to be a "visible" foreground pixel. - * @param sizeFactorToKeep This method keeps the largest connected - * component plus any component with size at least - * sizeOfLargestComponent/sizeFactorToKeep. - */ - void keepOnlyLargeComponents(float *cm, int cmSize, - float threshold, - double sizeFactorToKeep); - - /** - * Depth first search pixels in a foreground component. - * - * @param cm confidence matrix to be searched. - * @param i starting position as index to confidence matrix. - * @param threshold defines the minimum value at which a pixel is - * considered foreground. - * @param curlabel label no of component. - * @return size in pixel of the component found. - */ - int depthFirstSearch(float *cm, int i, float threshold, int curLabel); - - /** - * Refines the classification stored in the confidence matrix by modifying - * the confidences for regions which have characteristics to both - * foreground and background if they fall into the specified square. - *

- * The can be used in displaying the image by assigning the alpha values - * of the pixels according to the confidence entries. - *

- * In the algorithm descriptions and examples GUIs this step is referrered - * to as Detail Refinement (Brush). - * - * @param x Horizontal coordinate of the squares center. - * @param y Vertical coordinate of the squares center. - * @param brushmode Mode of the refinement applied, ADD_EDGE - * or SUB_EDGE. Add mode only modifies pixels - * formerly classified as background, sub mode only those - * formerly classified as foreground. - * @param threshold Threshold for the add and sub refinement, deciding - * at the confidence level to stop at. - * @param cf The confidence matrix to modify, generated by - * segmentate, possibly already refined by privious - * calls to subpixelRefine. - * @param brushsize Halfed diameter of the square shaped brush. - * - * @see #segmentate - */ - void SioxSegmentator::subpixelRefine(int x, int y, int brushmode, - float threshold, float *cf, int brushsize); - - /** - * Refines the classification stored in the confidence matrix by modifying - * the confidences for regions which have characteristics to both - * foreground and background if they fall into the specified area. - *

- * The can be used in displaying the image by assigning the alpha values - * of the pixels according to the confidence entries. - *

- * In the algorithm descriptions and examples GUIs this step is referrered - * to as Detail Refinement (Brush). - * - * @param area Area in which the reworking of the segmentation is - * applied to. - * @param brushmode Mode of the refinement applied, ADD_EDGE - * or SUB_EDGE. Add mode only modifies pixels - * formerly classified as background, sub mode only those - * formerly classified as foreground. - * @param threshold Threshold for the add and sub refinement, deciding - * at the confidence level to stop at. - * @param cf The confidence matrix to modify, generated by - * segmentate, possibly already refined by privious - * calls to subpixelRefine. - * - * @see #segmentate - */ - bool SioxSegmentator::subpixelRefine(int xa, int ya, int dx, int dy, - int brushmode, - float threshold, float *cf); - /** - * A region growing algorithms used to fill up the confidence matrix - * with CERTAIN_FOREGROUND_CONFIDENCE for corresponding - * areas of equal colors. - *

- * Basically, the method works like the Magic Wand with a - * tolerance threshold of zero. - * - * @param cm confidence matrix to be searched - * @param image image to be searched - */ - void fillColorRegions(float *cm, int cmSize, unsigned long *image); - -private: - - /** - * Prevent this from being used - */ - SioxSegmentator(); - - /** error logging **/ - void error(char *format, ...); - - /** trace logging **/ - void trace(char *format, ...); - - typedef enum - { - ADD_EDGE, /** Add mode for the subpixel refinement. */ - SUB_EDGE /** Subtract mode for the subpixel refinement. */ - } BrushMode; - - // instance fields: - - /** Horizontal resolution of the image to be segmentated. */ - int imgWidth; - - /** Vertical resolution of the image to be segmentated. */ - int imgHeight; - - /** Stores component label (index) by pixel it belongs to. */ - int *labelField; - - /** - * LAB color values of pixels that are definitly known background. - * Entries are of form {l,a,b}. - */ - std::vector knownBg; - - /** - * LAB color values of pixels that are definitly known foreground. - * Entries are of form {l,a,b}. - */ - std::vector knownFg; - - /** Holds background signature (a characteristic subset of the bg.) */ - std::vector bgSignature; - - /** Holds foreground signature (a characteristic subset of the fg).*/ - std::vector fgSignature; - - /** Size of cluster on lab axis. */ - float *limits; - - /** Maximum distance of two lab values. */ - float clusterSize; - - /** - * Stores Tupels for fast access to nearest background/foreground pixels. - */ - std::map hs; - - /** Size of the biggest blob.*/ - int regionCount; - - /** Copy of the original image, needed for detail refinement. */ - long *origImage; - long origImageSize; - - /** A flag that stores if the segmentation algorithm has already ran.*/ - bool segmentated; - -}; - -} //namespace siox -} //namespace org - -#endif /* __SIOX_SEGMENTATOR_H__ */ - +#ifndef __SIOX_H__ +#define __SIOX_H__ +/** + * Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping + * + * Conversion to C++ for Inkscape by Bob Jamison + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * Note by Bob Jamison: + * After translating the siox.org Java API to C++ and receiving an + * education into this wonderful code, I began again, + * and started this version using lessons learned. This version is + * an attempt to provide an dependency-free SIOX engine that anyone + * can use in their project with minimal effort. + * + * Many thanks to the fine people at siox.org. + */ + +#include +#include + +#define HAVE_GLIB + +#ifdef HAVE_GLIB +#include +#include +#endif + + +namespace org +{ + +namespace siox +{ + + +//######################################################################## +//# C L A B +//######################################################################## + +/** + * + */ +class CieLab +{ +public: + + /** + * + */ + CieLab() + { + init(); + C = 0; + L = A = B = 0.0f; + } + + + /** + * + */ + CieLab(unsigned long rgb); + + + /** + * + */ + CieLab(float lArg, float aArg, float bArg) + { + init(); + C = 0; + L = lArg; + A = aArg; + B = bArg; + } + + + /** + * + */ + CieLab(const CieLab &other) + { + init(); + C = other.C; + L = other.L; + A = other.A; + B = other.B; + } + + + /** + * + */ + CieLab &operator=(const CieLab &other) + { + init(); + C = other.C; + L = other.L; + A = other.A; + B = other.B; + return *this; + } + + /** + * + */ + virtual ~CieLab() + {} + + /** + * Retrieve a CieLab value via index. + */ + virtual float operator()(unsigned int index) + { + if (index==0) return L; + else if (index==1) return A; + else if (index==2) return B; + else return 0; + } + + + /** + * + */ + virtual void add(const CieLab &other) + { + C += other.C; + L += other.L; + A += other.A; + B += other.B; + } + + + /** + * + */ + virtual void mul(float scale) + { + L *= scale; + A *= scale; + B *= scale; + } + + + /** + * + */ + virtual unsigned long toRGB(); + + /** + * Approximate cube roots + */ + double cbrt(double x); + + /** + * + */ + double qnrt(double x); + + /** + * Raise to the 2.4 power + */ + double pow24(double x); + + /** + * Squared Euclidian distance between this and another color + */ + float diffSq(const CieLab &other); + + /** + * Computes squared euclidian distance in CieLab space for two colors + * given as RGB values. + */ + static float diffSq(unsigned int rgb1, unsigned int rgb2); + + /** + * Computes squared euclidian distance in CieLab space for two colors + * given as RGB values. + */ + static float diff(unsigned int rgb0, unsigned int rgb1); + + + unsigned int C; + float L; + float A; + float B; + +private: + + /** + * + */ + void init(); + + +}; + + +//######################################################################## +//# S I O X I M A G E +//######################################################################## + +/** + * This is a generic image type that provides a consistent interface + * to Siox, so that developers will not need to worry about data arrays. + */ +class SioxImage +{ +public: + + /** + * Create an image with the given width and height + */ + SioxImage(unsigned int width, unsigned int height); + + /** + * Copy constructor + */ + SioxImage(const SioxImage &other); + + /** + * Assignment + */ + SioxImage &operator=(const SioxImage &other); + + /** + * Clean up after use. + */ + virtual ~SioxImage(); + + /** + * Returns true if the previous operation on this image + * was successful, else false. + */ + virtual bool isValid(); + + /** + * Sets whether an operation was successful, and whether + * this image should be considered a valid one. + * was successful, else false. + */ + virtual void setValid(bool val); + + /** + * Set a pixel at the x,y coordinates to the given value. + * If the coordinates are out of range, do nothing. + */ + virtual void setPixel(unsigned int x, + unsigned int y, + unsigned int pixval); + + /** + * Set a pixel at the x,y coordinates to the given r, g, b values. + * If the coordinates are out of range, do nothing. + */ + virtual void setPixel(unsigned int x, unsigned int y, + unsigned int a, + unsigned int r, + unsigned int g, + unsigned int b); + + /** + * Get a pixel at the x,y coordinates given. If + * the coordinates are out of range, return 0 + */ + virtual unsigned int getPixel(unsigned int x, unsigned int y); + + + /** + * Return the image data buffer + */ + virtual unsigned int *getImageData(); + + /** + * Set a confidence value at the x,y coordinates to the given value. + * If the coordinates are out of range, do nothing. + */ + virtual void setConfidence(unsigned int x, + unsigned int y, + float conf); + + /** + * Get a confidence value at the x,y coordinates given. If + * the coordinates are out of range, return 0 + */ + virtual float getConfidence(unsigned int x, unsigned int y); + + /** + * Return the confidence data buffer + */ + virtual float *getConfidenceData(); + + /** + * Return the width of this image + */ + virtual int getWidth(); + + /** + * Return the height of this image + */ + virtual int getHeight(); + + /** + * Saves this image as a simple color PPM + */ + bool writePPM(const std::string fileName); + + + +#ifdef HAVE_GLIB + + /** + * Special constructor to create an image from a GdkPixbuf. + */ + SioxImage(GdkPixbuf *buf); + + /** + * Creates a GdkPixbuf from this image. The user must + * remember to destroy the image when no longer needed. + * with g_free(pixbuf) + */ + GdkPixbuf *getGdkPixbuf(); + +#endif + +private: + + SioxImage() + {} + + /** + * Assign values to that of another + */ + void assign(const SioxImage &other); + + /** + * Initialize values. Used by constructors + */ + void init(unsigned int width, unsigned int height); + + bool valid; + + unsigned int width; + + unsigned int height; + + unsigned long imageSize; + + /** + * Pixel data + */ + unsigned int *pixdata; + + /** + * Confidence matrix data + */ + float *cmdata; + +private: + + /** + * Error logging + */ + void error(char *fmt, ...) G_GNUC_PRINTF(2,3); + +}; + + + +//######################################################################## +//# S I O X O B S E R V E R +//######################################################################## +class Siox; + +/** + * This is a class for observing the progress of a Siox engine. Overload + * the methods in your subclass to get the desired behaviour. + */ +class SioxObserver +{ +public: + + /** + * Constructor. Context can point to anything, and is usually + * used to point to a C++ object or C state object, to delegate + * callback processing to something else. Use NULL to ignore. + */ + SioxObserver(void *contextArg) : context(NULL) + { context = contextArg; } + + /** + * Destructor + */ + virtual ~SioxObserver() + { } + + /** + * Informs the observer how much has been completed. + * Return false if the processing should be aborted. + */ + virtual bool progress(float /*percentCompleted*/) + { + return true; + } + + /** + * Send an error string to the Observer. Processing will + * be halted. + */ + virtual void error(const std::string &/*msg*/) + { + } + +protected: + + void *context; + +}; + + + +//######################################################################## +//# S I O X +//######################################################################## + +/** + * + */ +class Siox +{ +public: + + /** + * Confidence corresponding to a certain foreground region (equals one). + */ + static const float CERTAIN_FOREGROUND_CONFIDENCE; //=1.0f; + + /** + * Confidence for a region likely being foreground. + */ + static const float FOREGROUND_CONFIDENCE; //=0.8f; + + /** + * Confidence for foreground or background type being equally likely. + */ + static const float UNKNOWN_REGION_CONFIDENCE; //=0.5f; + + /** + * Confidence for a region likely being background. + */ + static const float BACKGROUND_CONFIDENCE; //=0.1f; + + /** + * Confidence corresponding to a certain background reagion (equals zero). + */ + static const float CERTAIN_BACKGROUND_CONFIDENCE; //=0.0f; + + /** + * Construct a Siox engine + */ + Siox(); + + /** + * Construct a Siox engine. Use null to ignore + */ + Siox(SioxObserver *observer); + + /** + * + */ + virtual ~Siox(); + + /** + * Extract the foreground of the original image, according + * to the values in the confidence matrix. If the operation fails, + * sioxImage.isValid() will be false. + * backgroundFillColor is any ARGB color, such as 0xffffff (white) + * or 0x000000 (black) + */ + virtual SioxImage extractForeground(const SioxImage &originalImage, + unsigned int backgroundFillColor); + +private: + + SioxObserver *sioxObserver; + + /** + * Progress reporting + */ + bool progressReport(float percentCompleted); + + /** + * Flag this as false during processing to abort + */ + bool keepGoing; + + /** + * Our signature limits + */ + float limits[3]; + + /** + * Image width + */ + unsigned int width; + + /** + * Image height + */ + unsigned int height; + + /** + * Image size in pixels + */ + unsigned long pixelCount; + + /** + * Image data + */ + unsigned int *image; + + /** + * Image confidence matrix + */ + float *cm; + + /** + * Markup for image editing + */ + int *labelField; + + + /** + * Maximum distance of two lab values. + */ + float clusterSize; + + /** + * Initialize the Siox engine to its 'pristine' state. + * Performed at the beginning of extractForeground(). + */ + void init(); + + /** + * Clean up any debris from processing. + */ + void cleanup(); + + /** + * Error logging + */ + void error(char *fmt, ...) G_GNUC_PRINTF(2,3); + + /** + * Trace logging + */ + void trace(char *fmt, ...) G_GNUC_PRINTF(2,3); + + /** + * Stage 1 of the color signature work. 'dims' will be either + * 2 for grays, or 3 for colors + */ + void colorSignatureStage1(CieLab *points, + unsigned int leftBase, + unsigned int rightBase, + unsigned int recursionDepth, + unsigned int *clusters, + const unsigned int dims); + + /** + * Stage 2 of the color signature work + */ + void colorSignatureStage2(CieLab *points, + unsigned int leftBase, + unsigned int rightBase, + unsigned int recursionDepth, + unsigned int *clusters, + const float threshold, + const unsigned int dims); + + /** + * Main color signature method + */ + bool colorSignature(const std::vector &inputVec, + std::vector &result, + const unsigned int dims); + + + /** + * + */ + void keepOnlyLargeComponents(float threshold, + double sizeFactorToKeep); + + /** + * + */ + int depthFirstSearch(int startPos, float threshold, int curLabel); + + + /** + * + */ + void fillColorRegions(); + + /** + * Applies the morphological dilate operator. + * + * Can be used to close small holes in the given confidence matrix. + */ + void dilate(float *cm, int xres, int yres); + + /** + * Applies the morphological erode operator. + */ + void erode(float *cm, int xres, int yres); + + /** + * Normalizes the matrix to values to [0..1]. + */ + void normalizeMatrix(float *cm, int cmSize); + + /** + * Multiplies matrix with the given scalar. + */ + void premultiplyMatrix(float alpha, float *cm, int cmSize); + + /** + * Blurs confidence matrix with a given symmetrically weighted kernel. + */ + void smooth(float *cm, int xres, int yres, + float f1, float f2, float f3); + + /** + * Squared Euclidian distance of p and q. + */ + float sqrEuclidianDist(float *p, int pSize, float *q); + + + + +}; + + + + +} // namespace siox +} // namespace org + +#endif /* __SIOX_H__ */ +//######################################################################## +//# E N D O F F I L E +//######################################################################## + + +