colorquant.c File Reference

#include <math.h>
#include <stdio.h>
#include "rle_config.h"
#include "colorquant.h"

Include dependency graph for colorquant.c:

Go to the source code of this file.

Data Structures
struct	Box

Macros
#define	MAXCOLORS   256
#define	FULLINTENSITY   255
#define	MAX(x, y)   ((x) > (y) ? (x) : (y))
#define	REDI   0
#define	GREENI   1
#define	BLUEI   2
#define	TRUE   1
#define	FALSE   0
#define	INIT_HIST   1
#define	USE_HIST   2
#define	PROCESS_HIST   3

Functions
static void	QuantHistogram ()
static void	BoxStats ()
static void	UpdateFrequencies ()
static void	ComputeRGBMap ()
static void	SetRGBmap ()
void	inv_cmap ()
static int	CutBoxes ()
static int	CutBox ()
static int	GreatestVariance ()
static int	FindCutpoint ()
int	colorquant (unsigned char *red, unsigned char *green, unsigned char *blue, unsigned long pixels, colormap, int colors, int bits, unsigned char *rgbmap, int flags, int accum_hist)
static void	QuantHistogram (unsigned char *r, unsigned char *g, unsigned char *b, Box *box, int quantize)
static int	CutBoxes (Box *boxes, int colors)
static int	GreatestVariance (Box *boxes, int n)
static void	BoxStats (Box *box)
static int	CutBox (Box *box, Box *newbox)
static int	FindCutpoint (Box *box, int color, Box *newbox1, Box *newbox2)
static void	UpdateFrequencies (Box *box1, Box *box2)
static void	ComputeRGBMap (Box *boxes, int colors, unsigned char *rgbmap, int bits, colormap, int fast)
static void	SetRGBmap (int boxnum, Box *box, unsigned char *rgbmap, int bits)

Variables
static char	rcsid [] = "$Header: /l/spencer/src/urt/lib/RCS/colorquant.c,v 3.0.1.4 1992/04/30 14:06:48 spencer Exp $"
static unsigned long *	Histogram
static unsigned long	NPixels
static unsigned long	SumPixels
static unsigned int	Bits
static unsigned int	ColormaxI
static Box *	Boxes

Macro Definition Documentation

#define BLUEI   2

Definition at line 164 of file colorquant.c.

#define FALSE   0

Definition at line 166 of file colorquant.c.

#define FULLINTENSITY   255

Definition at line 156 of file colorquant.c.

#define GREENI   1

Definition at line 163 of file colorquant.c.

#define INIT_HIST   1

Definition at line 238 of file colorquant.c.

#define MAX	(		x,
			y
	)		((x) > (y) ? (x) : (y))

Definition at line 157 of file colorquant.c.

#define MAXCOLORS   256

Definition at line 149 of file colorquant.c.

#define PROCESS_HIST   3

Definition at line 240 of file colorquant.c.

#define REDI   0

Definition at line 162 of file colorquant.c.

#define TRUE   1

Definition at line 165 of file colorquant.c.

#define USE_HIST   2

Definition at line 239 of file colorquant.c.

Function Documentation

static void BoxStats ( )

static

static void BoxStats ( Box *  box )

static

Definition at line 408 of file colorquant.c.

{
    register int i, color;
    unsigned long *freq;
    double mean, var;

    if(box->weight == 0) {
        box->weightedvar = 0;
        return;
    }

    box->weightedvar = 0.;
    for (color = 0; color < 3; color++) {
        var = mean = 0;
        i = box->low[color];
        freq = &box->freq[color][i];
        for (; i < box->high[color]; i++, freq++) {
            mean += i * *freq;
            var += i*i* *freq;
        }
        box->mean[color] = mean / (double)box->weight;
        box->weightedvar += var - box->mean[color]*box->mean[color]*
                    (double)box->weight;
    }
    box->weightedvar /= SumPixels;
}

int colorquant	(	unsigned char *	red,
		unsigned char *	green,
		unsigned char *	blue,
		unsigned long	pixels,
		colormap	,
		int	colors,
		int	bits,
		unsigned char *	rgbmap,
		int	flags,
		int	accum_hist
	)

Definition at line 242 of file colorquant.c.

{
    int i,          /* Counter */
    OutColors,          /* # of entries computed */
    Colormax;           /* quantized full-intensity */ 
    float   Cfactor;    /* Conversion factor */

    if (accum_hist < 0 || accum_hist > PROCESS_HIST)
    fprintf(stderr, "colorquant: bad value for accum_hist\n");

    ColormaxI = 1 << bits;  /* 2 ^ Bits */
    Colormax = ColormaxI - 1;
    Bits = bits;
    NPixels = pixels;
    Cfactor = (float)FULLINTENSITY / Colormax;

    if (! accum_hist || accum_hist == INIT_HIST) {
    Histogram = (unsigned long *)calloc(ColormaxI*ColormaxI*ColormaxI, 
                        sizeof(long));
    Boxes = (Box *)malloc(colors * sizeof(Box));
    /*
     * Zero-out the projected frequency arrays of the largest box.
     */
    bzero(Boxes->freq[0], ColormaxI * sizeof(unsigned long));
    bzero(Boxes->freq[1], ColormaxI * sizeof(unsigned long));
    bzero(Boxes->freq[2], ColormaxI * sizeof(unsigned long));
    SumPixels = 0;
    }

    SumPixels += NPixels;

    if ( accum_hist != PROCESS_HIST ) 
    QuantHistogram(red, green, blue, &Boxes[0], flags&CQ_QUANTIZE);

    if ( !accum_hist || accum_hist == PROCESS_HIST) {
    OutColors = CutBoxes(Boxes, colors);

    /*
     * We now know the set of representative colors.  We now
     * must fill in the colormap and convert the representatives
     * from their 'prequantized' range to 0-FULLINTENSITY.
     */
    for (i = 0; i < OutColors; i++) {
        colormap[0][i] =
        (unsigned char)(Boxes[i].mean[REDI] * Cfactor + 0.5);
        colormap[1][i] =
        (unsigned char)(Boxes[i].mean[GREENI] * Cfactor + 0.5);
        colormap[2][i] =
        (unsigned char)(Boxes[i].mean[BLUEI] * Cfactor + 0.5);
    }

    if ( !(flags & CQ_NO_RGBMAP) )
        ComputeRGBMap(Boxes, OutColors, rgbmap, bits, colormap,
              flags&CQ_FAST);

    free((char *)Histogram);
    free((char *)Boxes);
    return OutColors;   /* Return # of colormap entries */
    }
    return 0;
}

static void ComputeRGBMap ( )

static

static void ComputeRGBMap ( Box *  boxes, int  colors, unsigned char *  rgbmap, int  bits, colormap  , int  fast  )

static

Definition at line 580 of file colorquant.c.

{
    register int i;

    if (fast) {
        /*
         * The centroid of each box serves as the representative
         * for each color in the box.
         */
        for (i = 0; i < colors; i++)
            SetRGBmap(i, &boxes[i], rgbmap, bits);
    } else
        /*
         * Find the 'nearest' representative for each
         * pixel.
         */
#ifdef slow_color_map
        find_colors(boxes, colors, rgbmap, bits, colormap, 1);
#else
        inv_cmap(colors, colormap, bits, Histogram, rgbmap);
#endif
}

static int CutBox ( )

static

static int CutBox ( Box *  box, Box *  newbox  )

static

Definition at line 440 of file colorquant.c.

{
    int i;
    double totalvar[3];
    Box newboxes[3][2];

    if (box->weightedvar == 0. || box->weight == 0)
        /*
         * Can't cut this box.
         */
        return FALSE;

    /*
     * Find 'optimal' cutpoint along each of the red, green and blue
     * axes.  Sum the variances of the two boxes which would result
     * by making each cut and store the resultant boxes for 
     * (possible) later use.
     */
    for (i = 0; i < 3; i++) {
        if (FindCutpoint(box, i, &newboxes[i][0], &newboxes[i][1]))
            totalvar[i] = newboxes[i][0].weightedvar +
                newboxes[i][1].weightedvar;
        else
            totalvar[i] = HUGE;
    }

    /*
     * Find which of the three cuts minimized the total variance
     * and make that the 'real' cut.
     */
    if (totalvar[REDI] <= totalvar[GREENI] &&
        totalvar[REDI] <= totalvar[BLUEI]) {
        *box = newboxes[REDI][0];
        *newbox = newboxes[REDI][1];
    } else if (totalvar[GREENI] <= totalvar[REDI] &&
         totalvar[GREENI] <= totalvar[BLUEI]) {
        *box = newboxes[GREENI][0];
        *newbox = newboxes[GREENI][1];
    } else {
        *box = newboxes[BLUEI][0];
        *newbox = newboxes[BLUEI][1];
    }

    return TRUE;
}

static int CutBoxes ( )

static

static int CutBoxes ( Box *  boxes, int  colors  )

static

Definition at line 360 of file colorquant.c.

{
    int curbox;

    boxes[0].low[REDI] = boxes[0].low[GREENI] = boxes[0].low[BLUEI] = 0;
    boxes[0].high[REDI] = boxes[0].high[GREENI] =
                  boxes[0].high[BLUEI] = ColormaxI;
    boxes[0].weight = SumPixels;

    BoxStats(&boxes[0]);

    for (curbox = 1; curbox < colors; curbox++) {
        if (CutBox(&boxes[GreatestVariance(boxes, curbox)],
               &boxes[curbox]) == FALSE)
                break;
    }

    return curbox;
}

static int FindCutpoint ( )

static

static int FindCutpoint ( Box *  box, int  color, Box *  newbox1, Box *  newbox2  )

static

Definition at line 493 of file colorquant.c.

{
    float u, v, max;
    int i, maxindex, minindex, cutpoint;
    unsigned long optweight, curweight;

    if (box->low[color] + 1 == box->high[color])
        return FALSE;   /* Cannot be cut. */
    minindex = (int)((box->low[color] + box->mean[color]) * 0.5);
    maxindex = (int)((box->mean[color] + box->high[color]) * 0.5);

    cutpoint = minindex;
    optweight = box->weight;

    curweight = 0;
    for (i = box->low[color] ; i < minindex ; i++)
        curweight += box->freq[color][i];
    u = 0.;
    max = -1;
    for (i = minindex; i <= maxindex ; i++) {
        curweight += box->freq[color][i];
        if (curweight == box->weight)
            break;
        u += (float)(i * box->freq[color][i]) /
                    (float)box->weight;
        v = ((float)curweight / (float)(box->weight-curweight)) *
                (box->mean[color]-u)*(box->mean[color]-u);
        if (v > max) {
            max = v;
            cutpoint = i;
            optweight = curweight;
        }
    }
    cutpoint++;
    *newbox1 = *newbox2 = *box;
    newbox1->weight = optweight;
    newbox2->weight -= optweight;
    newbox1->high[color] = cutpoint;
    newbox2->low[color] = cutpoint;
    UpdateFrequencies(newbox1, newbox2);
    BoxStats(newbox1);
    BoxStats(newbox2);

    return TRUE;    /* Found cutpoint. */
}

static int GreatestVariance ( )

static

static int GreatestVariance ( Box *  boxes, int  n  )

static

Definition at line 387 of file colorquant.c.

{
    register int i, whichbox = 0;
    float max;

    max = -1;
    for (i = 0; i < n; i++) {
        if (boxes[i].weightedvar > max) {
            max = boxes[i].weightedvar;
            whichbox = i;
        }
    }
    return whichbox;
}

void inv_cmap

(

)

static void QuantHistogram ( )

static

static void QuantHistogram ( unsigned char *  r, unsigned char *  g, unsigned char *  b, Box *  box, int  quantize  )

static

Definition at line 315 of file colorquant.c.

{
    register unsigned long *rf, *gf, *bf;
    unsigned long i;

    rf = box->freq[0];
    gf = box->freq[1];
    bf = box->freq[2];

    /*
     * We compute both the histogram and the proj. frequencies of
     * the first box at the same time to save a pass through the
     * entire image. 
     */
    
    if ( !quantize )
        for (i = 0; i < NPixels; i++) {
        rf[*r]++;
        gf[*g]++;
        bf[*b]++;
        Histogram[((((*r++)<<Bits)|(*g++))<<Bits)|(*b++)]++;
        }
    else
    {
        unsigned char rr, gg, bb;
        for (i = 0; i < NPixels; i++) {
        rr = (*r++)>>(8-Bits);
        gg = (*g++)>>(8-Bits);
        bb = (*b++)>>(8-Bits);
        rf[rr]++;
        gf[gg]++;
        bf[bb]++;
        Histogram[(((rr<<Bits)|gg)<<Bits)|bb]++;
        }
    }
        
}

static void SetRGBmap ( )

static

static void SetRGBmap ( int  boxnum, Box *  box, unsigned char *  rgbmap, int  bits  )

static

Definition at line 612 of file colorquant.c.

{
    register int r, g, b;
    
    for (r = box->low[REDI]; r < box->high[REDI]; r++) {
        for (g = box->low[GREENI]; g < box->high[GREENI]; g++) {
            for (b = box->low[BLUEI]; b < box->high[BLUEI]; b++) {
                rgbmap[(((r<<bits)|g)<<bits)|b]=(char)boxnum;
            }
        }
    }
}

static void UpdateFrequencies ( )

static

static void UpdateFrequencies ( Box *  box1, Box *  box2  )

static

Definition at line 546 of file colorquant.c.

{
    register unsigned long myfreq, *h;
    register int b, g, r;
    int roff;

    bzero(box1->freq[0], ColormaxI * sizeof(unsigned long));
    bzero(box1->freq[1], ColormaxI * sizeof(unsigned long));
    bzero(box1->freq[2], ColormaxI * sizeof(unsigned long)); 

    for (r = box1->low[0]; r < box1->high[0]; r++) {
        roff = r << Bits;
        for (g = box1->low[1];g < box1->high[1]; g++) {
            b = box1->low[2];
            h = Histogram + (((roff | g) << Bits) | b);
            for (; b < box1->high[2]; b++) {
                if ((myfreq = *h++) == 0)
                    continue;
                box1->freq[0][r] += myfreq;
                box1->freq[1][g] += myfreq;
                box1->freq[2][b] += myfreq;
                box2->freq[0][r] -= myfreq;
                box2->freq[1][g] -= myfreq;
                box2->freq[2][b] -= myfreq;
            }
        }
    }
}

Variable Documentation

unsigned int Bits

static

Definition at line 179 of file colorquant.c.

Box* Boxes

static

Definition at line 181 of file colorquant.c.

unsigned int ColormaxI

static

Definition at line 179 of file colorquant.c.

unsigned long* Histogram

static

Definition at line 176 of file colorquant.c.

unsigned long NPixels

static

Definition at line 176 of file colorquant.c.

char rcsid[] = "$Header: /l/spencer/src/urt/lib/RCS/colorquant.c,v 3.0.1.4 1992/04/30 14:06:48 spencer Exp $"

static

Definition at line 86 of file colorquant.c.

unsigned long SumPixels

static

Definition at line 176 of file colorquant.c.