cvrKMColorQuantization.h

Go to the documentation of this file.

/*
 * Copyright (C) 1998-2006
 * Lehrstuhl fuer Technische Informatik, RWTH-Aachen, Germany
 *
 *
 * This file is part of the Computer Vision and Robotics Library (CVR-Lib)
 *
 * The CVR-Lib is free software; you can redistribute it and/or
 * modify it under the terms of the BSD License.
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * 3. Neither the name of the authors nor the names of its contributors may be
 *    used to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */


/**
 * \file   cvrKMColorQuantization.h
 *         Contains a class for color quantization using the k-Means algorithm.
 * \author Pablo Alvarado
 * \date   30.04.1999 (CVR-Lib 1)
 * \date   12.01.2006 (CVR-Lib )
 *
 * $Id: cvrKMColorQuantization.h,v 1.2 2006/01/15 22:15:27 alvarado Exp $
 */


#ifndef _CVR_KM_COLOR_QUANTIZATION_H_
#define _CVR_KM_COLOR_QUANTIZATION_H_

#include "cvrFunctor.h"
#include "cvrImage.h"
#include "cvrTypes.h"
#include "cvrVector.h"
#include "cvrColorQuantization.h"
#include "cvrRGBPixel.h"
#include <map>

namespace cvr {
  /**
   * k-Means based color quantization.
   *
   * This functor calculates (using k-Means) an optimal color subpalette for
   * the input image.  The maximal number of colors to be used is given
   * through the parameters (inherited from colorQuantization::parameters).
   *
   * If the real number of colors used in the image is less than the desired
   * number of quantized colors, no quantization is done and the output palette
   * will contain all image colors, i.e. it will be smaller that the expected
   * size of parameters::numberOfColors.
   *
   * @ingroup gColorQuantization
   */
  class kMColorQuantization : public colorQuantization {
  public:

    /**
     * the parameters for the class kMColorQuantization
     */
    class parameters : public colorQuantization::parameters {
    public:
      /**
       * default constructor
       */
      parameters();

      /**
       * copy constructor
       * @param other the parameters object to be copied
       */
      parameters(const parameters& other);

      /**
       * destructor
       */
      ~parameters();


      /**
       * Returns the name of this type
       */
      virtual const std::string& name() const;

      /**
       * Returns a pointer to a clone of the parameters
       */
      virtual parameters* clone() const;

      /**
       * Returns a pointer to a new instance of the parameters
       */
      virtual parameters* newInstance() const;

      /**
       * Copy the other instance.here.
       */
      parameters& copy(const parameters& other);

      /**
       * Copy the contents of a parameters object.
       *
       * @param other the parameters object to be copied
       * @return a reference to this parameters object
       */
      parameters& operator=(const parameters& other);

      /**
       * write the parameters in the given ioHandler
       * @param handler the ioHandler to be used
       * @param complete if true (the default) the enclosing begin/end will
       *        be also written, otherwise only the data block will be written.
       * @return true if write was successful
       */
      virtual bool write(ioHandler& handler,const bool complete=true) const;

      /**
       * write the parameters in the given ioHandler
       * @param handler the ioHandler to be used
       * @param complete if true (the default) the enclosing begin/end will
       *        be also written, otherwise only the data block will be written.
       * @return true if write was successful
       */
      virtual bool read(ioHandler& handler,const bool complete=true);

      // ------------------------------------------------
      // the parameters
      // ------------------------------------------------

      /**
       * Maximal number of iterations taken for the k-Means algorithm to
       * converge.
       *
       * Default value: 50
       */
      int maximalNumberOfIterations;

      /**
       * Smallest change of palette.
       *
       * If the difference between the palette in the previous iteration
       * and the palette in the current iteration is smaller than this value
       * then it will be assumed that the algorithm has converged.
       *
       * The difference is computed as the sum of the distances between
       * corresponding entries of the palette, taken in the RGB color space,
       * with an L2 distance, i.e. sum(distanceSqr(palNew-palOld)).
       *
       * Note that the axes of the RGB space are dimensioned from 0 to 255.
       *
       * Default value: 0.2
       */
      float thresholdDeltaPalette;

    };

    /**
     * Default constructor
     */
    kMColorQuantization();

    /**
     * Constructor with parameters
     */
    kMColorQuantization(const parameters& par);

    /**
     * Copy constructor
     */
    kMColorQuantization(const kMColorQuantization& other);

    /**
     * Destructor
     */
    virtual ~kMColorQuantization();

    /**
     * Returns current parameters.
     */
    const parameters& getParameters() const;

    /**
     * Returns the name of this type.
     */
    virtual const std::string& name() const;

    /**
     * Copy data of "other" functor.
     *
     * @param other the functor to be copied
     * @return a reference to this functor object
     */
    kMColorQuantization& copy(const kMColorQuantization& other);

    /**
     * Returns a pointer to a clone of this functor.
     */
    virtual kMColorQuantization* clone() const;

    /**
     * Returns a pointer to a clone of this functor.
     */
    virtual kMColorQuantization* newInstance() const;


    /**
     * Quantize the colors of src and leave the labels for the quantized colors
     * in dest, and in the palette entries corresponding to the labels the
     * mean colors for each label.
     *
     * @param src Original image with the true-color data
     * @param dest channel8 where the indexes of the also calculated palette
     *             will be.
     * @param thePalette the color palette used by the channel. If it is not
     *             empty, it will be taken as a InitPalette for
     *             the computation of the new one.
     * @return true if apply successful or false otherwise.
     */
    virtual bool apply(const image& src,
                             matrix<ubyte>& dest,
                             palette& thePalette) const;


    /**
     * Quantize the colors of src and leave the labels for the quantized colors
     * in dest, and in the palette entries corresponding to the labels the
     * mean colors for each label.
     *
     * @param src Original image with the true-color data
     * @param dest matrix<int> where the indexes of the calculated palette
     *             will be.
     * @param thePalette The color palette used by the matrix. If it is not
     *             empty, it will be taken as a InitPalette for
     *             the computation of the new one.
     * @return true if apply successful or false otherwise.
     */
    virtual bool apply(const image& src,
                             matrix<int>& dest,
                             palette& thePalette) const;


    /**
     * Quantize the colors of the given image.
     *
     * @param srcdest image with the source data.  The result
     *                 will be left here too.
     * @return true if apply successful or false otherwise.
     */
    virtual bool apply(image& srcdest) const;

    /**
     * Quantize the colors of the given src image and leave the result in dest.
     *
     * @param src image with the source data.
     * @param dest image with only the number of colors specified in
     *             the parameters
     * @return true if apply successful or false otherwise.
     */
    virtual bool apply(const image& src,image& dest) const;

  private:
    /**
     * functor to calculate the kMeans
     */
    class kMeanColor {
    public:
      /**
       * constructor
       */
      kMeanColor(const int& maxNumOfClasses,
     const int& maxIterations,
     const float& thresdDeltaPal);

      /**
       * destructor
       */
      virtual ~kMeanColor();

      /**
       * calculate palette and colorMap using k-Means.
       * img is the input image, and it will be modified to use
       * the quantized colors!
       */
      bool operator()(const image& src,matrix<int>& dest,palette& thePalette);

    protected:
      /**
       * An entry of the hash table contains the number of pixels in
       * the image that have the color corresponding to this entry (counter)
       * and the index of this color in the cetroid-vector;
       */
      struct hashEntry {
        hashEntry(const int& idx=0,const int& cnt=0)
          : index(idx),counter(cnt) {};
        int index;
        int counter;
      };

      /**
       * Each entry of the hash has this type
       */
      typedef std::map<int,hashEntry> hashMapType;

      /**
       * Hash table type (see theHash for more details).
       */
      typedef hashMapType* hashType;

      /**
       * the centroids
       */
      vector< frgbPixel > centroids_;

      /**
       * centroid elements
       */
      vector<int> centerElems_;

      /**
       * The hash table.
       *
       * The hash table contains all relevant information of the image to be
       * quantized, necessary for the k-Mean algorithms.
       *
       * It is organized as an array of 4096 (12 bits) hashMapType elements.
       *
       * This array is then accessed with the lower 12 bits of the color
       * value.  The upper 12 bits of the color are used to index the
       * proper map, that returns a hashEntry structure, with the correponding
       * centroid index for this color and the number of pixels assigned
       * to the centroid until now.
       *
       * In real world images, there will be an average between 5 and 10
       * elements per map.
       *
       * To access theHash directly, you can use the method at(), or put()
       */
      hashType theHash_;

      /**
       * the maximal number of classes
       */
      const int maxNumberOfClasses_;

      /**
       * the number of classes really used in the image
       */
      int realNumberOfClasses_;

      /**
       * maximum number of iterations for the k-Means
       */
      const int maxNumberOfIterations_;

      /**
       * if "Palette-Changing" by iteration < thresholdDeltaPalette
       * than stop iterating
       * sum(distanceSqr(palNew-palOld))
       */
      const float thresholdDeltaPalette_;

      /**
       * returns a reference to the hash entry for the given pixel
       */
      inline hashEntry& at(const rgbaPixel& px);

      /**
       * put the given pixel in the hash table (increments the counter if
       * already exists).
       * @return true if the pixel is new added, false otherwise.
       */
      inline bool put(const rgbaPixel& px);

      /**
       * create and initialize the hash table with the image values
       */
      void initialize(const image& src);

      /**
       * get initial palette from hash
       */
      void getInitialPalette(const cvr::palette& thePalette);

      /**
       * iterate to find the clusters
       */
      void iterate();

      /**
       * get a random color from the color hash
       */
      rgbaPixel getAnImageColor();

      /**
       * size of the maps array
       */
      static const int firstKeySize_;

      /**
       * a counter to generate the random colors
       */
      int lastHashPosition_;

      /**
       * Random number generator from 0.0 to 1.0
       */
      double random() const;
    };

  };

}

#endif