files/Source/Quantizers.h

// =============================================================
// Quantizer objects and functions
//
// Design and implementation by:
// - Hervé Drolon <drolon@infonie.fr>
// - Carsten Klein (cklein05@users.sourceforge.net)
//
// This file is part of FreeImage 3
//
// COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT WARRANTY
// OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT LIMITATION, WARRANTIES
// THAT THE COVERED CODE IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE
// OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED
// CODE IS WITH YOU. SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT
// THE INITIAL DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY
// SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL
// PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER
// THIS DISCLAIMER.
//
// Use at your own risk!
// =============================================================

// 
////////////////////////////////////////////////////////////////

#include "FreeImage.h"

////////////////////////////////////////////////////////////////

/**
  Xiaolin Wu color quantization algorithm
*/
class WuQuantizer
{
public:

typedef struct tagBox {
    int r0;			 // min value, exclusive
    int r1;			 // max value, inclusive
    int g0;  
    int g1;  
    int b0;  
    int b1;
    int vol;
} Box;

protected:
    float *gm2;
	LONG *wt, *mr, *mg, *mb;
	WORD *Qadd;

	// DIB data
	unsigned width, height;
	unsigned pitch;
	FIBITMAP *m_dib;

protected:
    void Hist3D(LONG *vwt, LONG *vmr, LONG *vmg, LONG *vmb, float *m2, int ReserveSize, RGBQUAD *ReservePalette);
	void M3D(LONG *vwt, LONG *vmr, LONG *vmg, LONG *vmb, float *m2);
	LONG Vol(Box *cube, LONG *mmt);
	LONG Bottom(Box *cube, BYTE dir, LONG *mmt);
	LONG Top(Box *cube, BYTE dir, int pos, LONG *mmt);
	float Var(Box *cube);
	float Maximize(Box *cube, BYTE dir, int first, int last , int *cut,
				   LONG whole_r, LONG whole_g, LONG whole_b, LONG whole_w);
	bool Cut(Box *set1, Box *set2);
	void Mark(Box *cube, int label, BYTE *tag);

public:
	// Constructor - Input parameter: DIB 24-bit to be quantized
    WuQuantizer(FIBITMAP *dib);
	// Destructor
	~WuQuantizer();
	// Quantizer - Return value: quantized 8-bit (color palette) DIB
	FIBITMAP* Quantize(int PaletteSize, int ReserveSize, RGBQUAD *ReservePalette);
};


/**
  NEUQUANT Neural-Net quantization algorithm by Anthony Dekker
*/

// ----------------------------------------------------------------
// Constant definitions
// ----------------------------------------------------------------

/** number of colours used: 
	for 256 colours, fixed arrays need 8kb, plus space for the image
*/
//static const int netsize = 256;

/**@name network definitions */
//@{
//static const int maxnetpos = (netsize - 1);
/// bias for colour values
static const int netbiasshift = 4;
/// no. of learning cycles
static const int ncycles = 100;
//@}

/**@name defs for freq and bias */
//@{
/// bias for fractions
static const int intbiasshift = 16;
static const int intbias = (((int)1) << intbiasshift);
/// gamma = 1024
static const int gammashift = 10;
// static const int gamma = (((int)1) << gammashift);
/// beta = 1 / 1024
static const int betashift = 10;
static const int beta = (intbias >> betashift);
static const int betagamma = (intbias << (gammashift-betashift));
//@}

/**@name defs for decreasing radius factor */
//@{
/// for 256 cols, radius starts
//static const int initrad = (netsize >> 3);
/// at 32.0 biased by 6 bits
static const int radiusbiasshift = 6;
static const int radiusbias = (((int)1) << radiusbiasshift);
/// and decreases by a 
//static const int initradius	= (initrad * radiusbias);
// factor of 1/30 each cycle
static const int radiusdec = 30;
//@}

/**@name defs for decreasing alpha factor */
//@{
/// alpha starts at 1.0
static const int alphabiasshift = 10;
static const int initalpha = (((int)1) << alphabiasshift);
//@}

/**@name radbias and alpharadbias used for radpower calculation */
//@{
static const int radbiasshift = 8;
static const int radbias = (((int)1) << radbiasshift);
static const int alpharadbshift = (alphabiasshift+radbiasshift);
static const int alpharadbias = (((int)1) << alpharadbshift);	
//@}

class NNQuantizer
{
protected:
	/**@name image parameters */
	//@{
	/// pointer to input dib
	FIBITMAP *dib_ptr;
	/// image width
	int img_width;
	/// image height
	int img_height;
	/// image line length
	int img_line;
	//@}

	/**@name network parameters */
	//@{

	int netsize, maxnetpos, initrad, initradius;

	/// BGRc
	typedef int pixel[4];
	/// the network itself
	pixel *network;

	/// for network lookup - really 256
	int netindex[256];

	/// bias array for learning
	int *bias;
	/// freq array for learning
	int *freq;
	/// radpower for precomputation
	int *radpower;
	//@}

protected:
	/// Initialise network in range (0,0,0) to (255,255,255) and set parameters
	void initnet();	

	/// Unbias network to give byte values 0..255 and record position i to prepare for sort
	void unbiasnet();

	/// Insertion sort of network and building of netindex[0..255] (to do after unbias)
	void inxbuild();

	/// Search for BGR values 0..255 (after net is unbiased) and return colour index
	int inxsearch(int b, int g, int r);

	/// Search for biased BGR values
	int contest(int b, int g, int r);
	
	/// Move neuron i towards biased (b,g,r) by factor alpha
	void altersingle(int alpha, int i, int b, int g, int r);

	/// Move adjacent neurons by precomputed alpha*(1-((i-j)^2/[r]^2)) in radpower[|i-j|]
	void alterneigh(int rad, int i, int b, int g, int r);

	/** Main Learning Loop
	@param sampling_factor sampling factor in [1..30]
	*/
	void learn(int sampling_factor);

	/// Get a pixel sample at position pos. Handle 4-byte boundary alignment.
	void getSample(long pos, int *b, int *g, int *r);


public:
	/// Constructor
	NNQuantizer(int PaletteSize);

	/// Destructor
	~NNQuantizer();

	/** Quantizer
	@param dib input 24-bit dib to be quantized
	@param sampling a sampling factor in range 1..30. 
	1 => slower (but better), 30 => faster. Default value is 1
	@return returns the quantized 8-bit (color palette) DIB
	*/
	FIBITMAP* Quantize(FIBITMAP *dib, int ReserveSize, RGBQUAD *ReservePalette, int sampling = 1);

};

/**
 * LFPQUANT - Lossless Fast Pseudo-Quantization Algorithm
 *
 * The Lossless Fast Pseudo-Quantization algorithm is no real quantization
 * algorithm, since it makes no attempt to create a palette, that is suitable
 * for all colors of the 24-bit source image. However, it provides very fast
 * conversions from 24-bit to 8-bit images, if the number of distinct colors
 * in the source image is not greater than the desired palette size. If the
 * number of colors in the source image is exceeded, the Quantize method of
 * this implementation stops the process and returns NULL.
 *
 * This implementation uses a very fast hash map implementation to collect
 * the source image's colors. It turned out that a customized implementation
 * of a hash table with open addressing (using linear probing) provides the
 * best performance. The hash table has 512 entries, which prevents the load
 * factor to exceed 0.5 as we have 256 entries at most. Each entry consumes
 * 64 bits, so the whole hash table takes 4KB of memory.
 *
 * For large images, the LFPQuantizer is typically up to three times faster
 * than the WuQuantizer.
 */
class LFPQuantizer {
public:
	/** Constructor */
	LFPQuantizer(unsigned PaletteSize);

	/** Destructor */
	~LFPQuantizer();

	/**
	 * Quantizer
	 * @param dib input 24-bit or 32-bit bitmap to be quantized
	 * @return returns the pseudo-quantized 8-bit bitmap
	 */
	FIBITMAP* Quantize(FIBITMAP *dib, int ReserveSize, RGBQUAD *ReservePalette);

protected:
	/** The maximum size of a palette. */
	static const unsigned MAX_SIZE = 256;

	/**
	 * The size of the hash table. Must be a power of 2. By sizing it
	 * MAX_SIZE * 2, we ensure the load factor not to exceed 0.5 at any
	 * time, since we will have MAX_SIZE entries at most.
	 */
	static const unsigned MAP_SIZE = MAX_SIZE * 2;

	/**
	 * With open addressing we need a special value for empty buckets.
	 * Both entry.color and entry.index are 0xFFFFFFFF for an empty
	 * entry.
	 */
	static const unsigned EMPTY_BUCKET = 0xFFFFFFFF;

	/**
	 * This structure defines a single entry in the hash table. We use
	 * color as the entry's key.
	 */
	typedef struct MapEntry {
		unsigned color;
		unsigned index;
	} MapEntry;

	/** The hash table. */
	MapEntry *m_map;

	/**
	 * The current size of the newly created palette. Since the provided
	 * reserve palette could contain duplicates, this is not necessarily
	 * the number of entries in the hash table. Initialized to zero.
	 */
	unsigned m_size;

	/**
	 * The desired maximum number of entries in the newly created palette.
	 * If m_size exceeds this value, the palette is full and the
	 * quantization process is stopped. Initialized to the desired
	 * palette size.
	 */
	unsigned m_limit;

	/**
	 *  The palette index used for the next color added. Initialized to
	 *  zero (the reserve palette is put to the end of the palette).
	 */
	unsigned m_index;

	/**
	 * Ensures that hash codes that differ only by constant multiples
	 * at each bit position have a bounded number of collisions.
	 * @param h the initial (aka raw) hash code
	 * @return the modified hash code
	 */
	static inline unsigned hash(unsigned h) {
		h ^= (h >> 20) ^ (h >> 12);
		return h ^ (h >> 7) ^ (h >> 4);
	}

	/**
	 * Returns the palette index of the specified color. Tries to put the
	 * color into the map, if it's not already present in the map. In that
	 * case, a new index is used for the color. Returns -1, if adding the
	 * color would exceed the desired maximum number of colors in the
	 * palette.
	 * @param color the color to get the index from
	 * @return the palette index of the specified color or -1, if there
	 * is no space left in the palette
	 */
	int GetIndexForColor(unsigned color);

	/**
	 * Adds the specified number of entries of the specified reserve
	 * palette to the newly created palette.
	 * @param *palette a pointer to the reserve palette to copy from
	 * @param size the number of entries to copy
	 */
	void AddReservePalette(const void *palette, unsigned size);

	/**
	 * Copies the newly created palette into the specified destination
	 * palettte. Although unused palette entries are not overwritten in
	 * the destination palette, it is assumed to have space for at
	 * least 256 entries.
	 * @param palette a pointer to the destination palette
	 */
	void WritePalette(void *palette);

};