view release on metacpan or  search on metacpan

src/Source/FreeImage/NNQuantizer.cpp  view on Meta::CPAN

// NeuQuant Neural-Net Quantization Algorithm
// ------------------------------------------
//
// Copyright (c) 1994 Anthony Dekker
//
// NEUQUANT Neural-Net quantization algorithm by Anthony Dekker, 1994.
// See "Kohonen neural networks for optimal colour quantization"
// in "Network: Computation in Neural Systems" Vol. 5 (1994) pp 351-367.
// for a discussion of the algorithm.
//
// Any party obtaining a copy of these files from the author, directly or
// indirectly, is granted, free of charge, a full and unrestricted irrevocable,
// world-wide, paid up, royalty-free, nonexclusive right and license to deal
// in this software and documentation files (the "Software"), including without
// limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons who receive
// copies from any such party to do so, with the only requirement being
// that this copyright notice remain intact.

///////////////////////////////////////////////////////////////////////
// History
// -------
// January 2001: Adaptation of the Neural-Net Quantization Algorithm
//               for the FreeImage 2 library
//               Author: Hervé Drolon (drolon@infonie.fr)
// March 2004:   Adaptation for the FreeImage 3 library (port to big endian processors)
//               Author: Hervé Drolon (drolon@infonie.fr)
// April 2004:   Algorithm rewritten as a C++ class. 
//               Fixed a bug in the algorithm with handling of 4-byte boundary alignment.
//               Author: Hervé Drolon (drolon@infonie.fr)
///////////////////////////////////////////////////////////////////////

#include "Quantizers.h"
#include "FreeImage.h"
#include "Utilities.h"


// Four primes near 500 - assume no image has a length so large
// that it is divisible by all four primes
// ==========================================================

#define prime1		499
#define prime2		491
#define prime3		487
#define prime4		503

// ----------------------------------------------------------------

NNQuantizer::NNQuantizer(int PaletteSize)
{
	netsize = PaletteSize;
	maxnetpos = netsize - 1;
	initrad = netsize < 8 ? 1 : (netsize >> 3);
	initradius = (initrad * radiusbias);

	network = NULL;

	network = (pixel *)malloc(netsize * sizeof(pixel));
	bias = (int *)malloc(netsize * sizeof(int));
	freq = (int *)malloc(netsize * sizeof(int));
	radpower = (int *)malloc(initrad * sizeof(int));

	if( !network || !bias || !freq || !radpower ) {
		if(network) free(network);
		if(bias) free(bias);
		if(freq) free(freq);
		if(radpower) free(radpower);
		throw FI_MSG_ERROR_MEMORY;
	}
}

NNQuantizer::~NNQuantizer()
{
	if(network) free(network);
	if(bias) free(bias);
	if(freq) free(freq);
	if(radpower) free(radpower);
}

///////////////////////////////////////////////////////////////////////////
// Initialise network in range (0,0,0) to (255,255,255) and set parameters
// -----------------------------------------------------------------------

void NNQuantizer::initnet() {
	int i, *p;

	for (i = 0; i < netsize; i++) {
		p = network[i];
		p[FI_RGBA_BLUE] = p[FI_RGBA_GREEN] = p[FI_RGBA_RED] = (i << (netbiasshift+8))/netsize;
		freq[i] = intbias/netsize;	/* 1/netsize */
		bias[i] = 0;
	}
}

///////////////////////////////////////////////////////////////////////////////////////	
// Unbias network to give byte values 0..255 and record position i to prepare for sort
// ------------------------------------------------------------------------------------

src/Source/FreeImage/NNQuantizer.cpp  view on Meta::CPAN

// Move adjacent neurons by precomputed alpha*(1-((i-j)^2/[r]^2)) in radpower[|i-j|]
// ---------------------------------------------------------------------------------

void NNQuantizer::alterneigh(int rad, int i, int b, int g, int r) {
	int j, k, lo, hi, a;
	int *p, *q;

	lo = i - rad;   if (lo < -1) lo = -1;
	hi = i + rad;   if (hi > netsize) hi = netsize;

	j = i+1;
	k = i-1;
	q = radpower;
	while ((j < hi) || (k > lo)) {
		a = (*(++q));
		if (j < hi) {
			p = network[j];
			p[FI_RGBA_BLUE]  -= (a * (p[FI_RGBA_BLUE] - b)) / alpharadbias;
			p[FI_RGBA_GREEN] -= (a * (p[FI_RGBA_GREEN] - g)) / alpharadbias;
			p[FI_RGBA_RED]   -= (a * (p[FI_RGBA_RED] - r)) / alpharadbias;
			j++;
		}
		if (k > lo) {
			p = network[k];
			p[FI_RGBA_BLUE]  -= (a * (p[FI_RGBA_BLUE] - b)) / alpharadbias;
			p[FI_RGBA_GREEN] -= (a * (p[FI_RGBA_GREEN] - g)) / alpharadbias;
			p[FI_RGBA_RED]   -= (a * (p[FI_RGBA_RED] - r)) / alpharadbias;
			k--;
		}
	}
}

/////////////////////
// Main Learning Loop
// ------------------

/**
 Get a pixel sample at position pos. Handle 4-byte boundary alignment.
 @param pos pixel position in a WxHx3 pixel buffer
 @param b blue pixel component
 @param g green pixel component
 @param r red pixel component
*/
void NNQuantizer::getSample(long pos, int *b, int *g, int *r) {
	// get equivalent pixel coordinates 
	// - assume it's a 24-bit image -
	int x = pos % img_line;
	int y = pos / img_line;

	BYTE *bits = FreeImage_GetScanLine(dib_ptr, y) + x;

	*b = bits[FI_RGBA_BLUE] << netbiasshift;
	*g = bits[FI_RGBA_GREEN] << netbiasshift;
	*r = bits[FI_RGBA_RED] << netbiasshift;
}

void NNQuantizer::learn(int sampling_factor) {
	int i, j, b, g, r;
	int radius, rad, alpha, step, delta, samplepixels;
	int alphadec; // biased by 10 bits
	long pos, lengthcount;

	// image size as viewed by the scan algorithm
	lengthcount = img_width * img_height * 3;

	// number of samples used for the learning phase
	samplepixels = lengthcount / (3 * sampling_factor);

	// decrease learning rate after delta pixel presentations
	delta = samplepixels / ncycles;
	if(delta == 0) {
		// avoid a 'divide by zero' error with very small images
		delta = 1;
	}

	// initialize learning parameters
	alphadec = 30 + ((sampling_factor - 1) / 3);
	alpha = initalpha;
	radius = initradius;
	
	rad = radius >> radiusbiasshift;
	if (rad <= 1) rad = 0;
	for (i = 0; i < rad; i++) 
		radpower[i] = alpha*(((rad*rad - i*i)*radbias)/(rad*rad));
	
	// initialize pseudo-random scan
	if ((lengthcount % prime1) != 0)
		step = 3*prime1;
	else {
		if ((lengthcount % prime2) != 0)
			step = 3*prime2;
		else {
			if ((lengthcount % prime3) != 0) 
				step = 3*prime3;
			else
				step = 3*prime4;
		}
	}
	
	i = 0;		// iteration
	pos = 0;	// pixel position

	while (i < samplepixels) {
		// get next learning sample
		getSample(pos, &b, &g, &r);

		// find winning neuron
		j = contest(b, g, r);

		// alter winner
		altersingle(alpha, j, b, g, r);

		// alter neighbours 
		if (rad) alterneigh(rad, j, b, g, r);

		// next sample
		pos += step;
		while (pos >= lengthcount) pos -= lengthcount;
	
		i++;
		if (i % delta == 0) {	
			// decrease learning rate and also the neighborhood
			alpha -= alpha / alphadec;
			radius -= radius / radiusdec;
			rad = radius >> radiusbiasshift;
			if (rad <= 1) rad = 0;
			for (j = 0; j < rad; j++) 
				radpower[j] = alpha * (((rad*rad - j*j) * radbias) / (rad*rad));
		}
	}
	
}

//////////////
// Quantizer
// -----------

FIBITMAP* NNQuantizer::Quantize(FIBITMAP *dib, int ReserveSize, RGBQUAD *ReservePalette, int sampling) {

	if ((!dib) || (FreeImage_GetBPP(dib) != 24)) {
		return NULL;
	}

	// 1) Select a sampling factor in range 1..30 (input parameter 'sampling')
	//    1 => slower, 30 => faster. Default value is 1


	// 2) Get DIB parameters

	dib_ptr = dib;
	
	img_width  = FreeImage_GetWidth(dib);	// DIB width
	img_height = FreeImage_GetHeight(dib);	// DIB height
	img_line   = FreeImage_GetLine(dib);	// DIB line length in bytes (should be equal to 3 x W)

	// For small images, adjust the sampling factor to avoid a 'divide by zero' error later 
	// (see delta in learn() routine)
	int adjust = (img_width * img_height) / ncycles;
	if(sampling >= adjust)
		sampling = 1;


	// 3) Initialize the network and apply the learning algorithm

	if( netsize > ReserveSize ) {
		netsize -= ReserveSize;
		initnet();
		learn(sampling);
		unbiasnet();
		netsize += ReserveSize;
	}

	// 3.5) Overwrite the last few palette entries with the reserved ones
    for (int i = 0; i < ReserveSize; i++) {
		network[netsize - ReserveSize + i][FI_RGBA_BLUE] = ReservePalette[i].rgbBlue;
		network[netsize - ReserveSize + i][FI_RGBA_GREEN] = ReservePalette[i].rgbGreen;
		network[netsize - ReserveSize + i][FI_RGBA_RED] = ReservePalette[i].rgbRed;
		network[netsize - ReserveSize + i][3] = netsize - ReserveSize + i;
	}

	// 4) Allocate a new 8-bit DIB

	FIBITMAP *new_dib = FreeImage_Allocate(img_width, img_height, 8);

	if (new_dib == NULL)
		return NULL;

	// 5) Write the quantized palette

	RGBQUAD *new_pal = FreeImage_GetPalette(new_dib);

    for (int j = 0; j < netsize; j++) {
		new_pal[j].rgbBlue  = (BYTE)network[j][FI_RGBA_BLUE];
		new_pal[j].rgbGreen = (BYTE)network[j][FI_RGBA_GREEN];
		new_pal[j].rgbRed	= (BYTE)network[j][FI_RGBA_RED];
	}

	inxbuild();

	// 6) Write output image using inxsearch(b,g,r)

	for (WORD rows = 0; rows < img_height; rows++) {
		BYTE *new_bits = FreeImage_GetScanLine(new_dib, rows);			
		BYTE *bits = FreeImage_GetScanLine(dib_ptr, rows);

		for (WORD cols = 0; cols < img_width; cols++) {
			new_bits[cols] = (BYTE)inxsearch(bits[FI_RGBA_BLUE], bits[FI_RGBA_GREEN], bits[FI_RGBA_RED]);

			bits += 3;
		}
	}

	return (FIBITMAP*) new_dib;
}