www.pudn.com > jseg.rar > xv24to8.c
/*
* The Conv24to8 procedure takes a pointer to a 24-bit image (loaded
* previously). The image will be a w * h * 3 byte array of
* bytes. The image will be arranged with 3 bytes per pixel (in order
* R, G, and B), pixel 0 at the top left corner. (As normal.)
* The procedure also takes a maximum number of colors to use (numcols)
* and pointers to three 256-long arrays of bytes (to hold the returned
* colormap)
*
* Note that Conv24to8() does NOT free the pic24 image under any circumstances
*
* The Conv24to8 procedure will set up the following: it will allocate, make
* & return 'pic8', a 'w' by 'h' (passed in values) 8-bit picture.
* it will load up the rmap, gmap and bmap colormap arrays. it will NOT
* calculate numcols, since the cmap sort procedure has to be called anyway
*
* Conv24to8 returns 'pic8' if successful, 'NULL' on failure (presumably on a
* malloc())
*
* The 'slow' code is based on Heckbert's Median Cut algorithm.
*
*/
#include "xv.h"
#define MAX_CMAP_SIZE 256
#define COLOR_DEPTH 8
#define MAX_COLOR 256
#define B_DEPTH 5 /* # bits/pixel to use */
#define B_LEN (1<next;
if (freeboxes) freeboxes->prev = NULL;
ptr->next = usedboxes;
usedboxes = ptr;
if (ptr->next) ptr->next->prev = ptr;
get_histogram(ptr);
/**** STEP 3: continually subdivide boxes until no more free boxes remain */
while (freeboxes) {
ptr = largest_box();
if (ptr) splitbox(ptr);
else break;
}
/**** STEP 4: assign colors to all boxes ****/
for (i=0, ptr=usedboxes; inext) {
assign_color(ptr, &rmap[i], &gmap[i], &bmap[i]);
}
/* We're done with the boxes now */
num_colors = i;
free(box_list);
box_list = freeboxes = usedboxes = NULL;
/**** STEP 5: scan histogram and map all values to closest color */
/* 5a: create cell list as described in Heckbert[2] */
ColorCells = (CCELL **) calloc(C_LEN*C_LEN*C_LEN, sizeof(CCELL *));
/* 5b: create mapping from truncated pixel space to color table entries */
map_colortable();
/**** STEP 6: scan image, match input values to table entries */
i = quant_fsdither();
/* free everything that can be freed */
for (j=0 ; j < C_LEN*C_LEN*C_LEN ; j++) {
if (ColorCells[j] != NULL) free (ColorCells[j]);
}
free(ColorCells);
if (i) { free(pic8); pic8 = NULL; } /* free 'pic' on failure */
return pic8;
}
/****************************/
static void get_histogram(box)
CBOX *box;
/****************************/
{
int i,j,r,g,b,*ptr;
byte *p;
box->rmin = box->gmin = box->bmin = 999;
box->rmax = box->gmax = box->bmax = -1;
box->total = WIDE * HIGH;
/* zero out histogram */
ptr = &histogram[0][0][0];
for (i=B_LEN*B_LEN*B_LEN; i>0; i-- ) *ptr++ = 0;
/* calculate histogram */
p = pic24;
for (i=0; i> (COLOR_DEPTH-B_DEPTH);
g = (*p++) >> (COLOR_DEPTH-B_DEPTH);
b = (*p++) >> (COLOR_DEPTH-B_DEPTH);
if (r < box->rmin) box->rmin = r;
if (r > box->rmax) box->rmax = r;
if (g < box->gmin) box->gmin = g;
if (g > box->gmax) box->gmax = g;
if (b < box->bmin) box->bmin = b;
if (b > box->bmax) box->bmax = b;
histogram[r][g][b]++;
}
}
/******************************/
static CBOX *largest_box()
/******************************/
{
CBOX *tmp, *ptr;
int size = -1;
tmp = usedboxes;
ptr = NULL;
while (tmp) {
if ( (tmp->rmax > tmp->rmin ||
tmp->gmax > tmp->gmin ||
tmp->bmax > tmp->bmin) && tmp->total > size ) {
ptr = tmp;
size = tmp->total;
}
tmp = tmp->next;
}
return(ptr);
}
/******************************/
static void splitbox(ptr)
CBOX *ptr;
/******************************/
{
int hist2[B_LEN], first, last, i, rdel, gdel, bdel;
CBOX *new;
int *iptr, *histp, ir, ig, ib;
int rmin,rmax,gmin,gmax,bmin,bmax;
enum {RED,GREEN,BLUE} which;
/*
* see which axis is the largest, do a histogram along that
* axis. Split at median point. Contract both new boxes to
* fit points and return
*/
first = last = 0; /* shut RT hcc compiler up */
rmin = ptr->rmin; rmax = ptr->rmax;
gmin = ptr->gmin; gmax = ptr->gmax;
bmin = ptr->bmin; bmax = ptr->bmax;
rdel = rmax - rmin;
gdel = gmax - gmin;
bdel = bmax - bmin;
if (rdel>=gdel && rdel>=bdel) which = RED;
else if (gdel>=bdel) which = GREEN;
else which = BLUE;
/* get histogram along longest axis */
switch (which) {
case RED:
histp = &hist2[rmin];
for (ir=rmin; ir<=rmax; ir++) {
*histp = 0;
for (ig=gmin; ig<=gmax; ig++) {
iptr = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++) {
*histp += *iptr;
++iptr;
}
}
++histp;
}
first = rmin; last = rmax;
break;
case GREEN:
histp = &hist2[gmin];
for (ig=gmin; ig<=gmax; ig++) {
*histp = 0;
for (ir=rmin; ir<=rmax; ir++) {
iptr = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++) {
*histp += *iptr;
++iptr;
}
}
++histp;
}
first = gmin; last = gmax;
break;
case BLUE:
histp = &hist2[bmin];
for (ib=bmin; ib<=bmax; ib++) {
*histp = 0;
for (ir=rmin; ir<=rmax; ir++) {
iptr = &histogram[ir][gmin][ib];
for (ig=gmin; ig<=gmax; ig++) {
*histp += *iptr;
iptr += B_LEN;
}
}
++histp;
}
first = bmin; last = bmax;
break;
}
/* find median point */
{
int sum, sum2;
histp = &hist2[first];
sum2 = ptr->total/2;
histp = &hist2[first];
sum = 0;
for (i=first; i<=last && (sum += *histp++)next;
if (freeboxes) freeboxes->prev = NULL;
if (usedboxes) usedboxes->prev = new;
new->next = usedboxes;
usedboxes = new;
{
int sum1,sum2,j;
histp = &hist2[first];
sum1 = 0;
for (j = first; j < i; ++j) sum1 += *histp++;
sum2 = 0;
for (j = i; j <= last; ++j) sum2 += *histp++;
new->total = sum1;
ptr->total = sum2;
}
new->rmin = rmin; new->rmax = rmax;
new->gmin = gmin; new->gmax = gmax;
new->bmin = bmin; new->bmax = bmax;
switch (which) {
case RED: new->rmax = i-1; ptr->rmin = i; break;
case GREEN: new->gmax = i-1; ptr->gmin = i; break;
case BLUE: new->bmax = i-1; ptr->bmin = i; break;
}
shrinkbox(new);
shrinkbox(ptr);
}
/****************************/
static void shrinkbox(box)
CBOX *box;
/****************************/
{
int *histp,ir,ig,ib;
int rmin,rmax,gmin,gmax,bmin,bmax;
rmin = box->rmin; rmax = box->rmax;
gmin = box->gmin; gmax = box->gmax;
bmin = box->bmin; bmax = box->bmax;
if (rmax>rmin) {
for (ir=rmin; ir<=rmax; ir++)
for (ig=gmin; ig<=gmax; ig++) {
histp = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++)
if (*histp++ != 0) {
box->rmin = rmin = ir;
goto have_rmin;
}
}
have_rmin:
if (rmax>rmin)
for (ir=rmax; ir>=rmin; --ir)
for (ig=gmin; ig<=gmax; ig++) {
histp = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++)
if (*histp++ != 0) {
box->rmax = rmax = ir;
goto have_rmax;
}
}
}
have_rmax:
if (gmax>gmin) {
for (ig=gmin; ig<=gmax; ig++)
for (ir=rmin; ir<=rmax; ir++) {
histp = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++)
if (*histp++ != 0) {
box->gmin = gmin = ig;
goto have_gmin;
}
}
have_gmin:
if (gmax>gmin)
for (ig=gmax; ig>=gmin; --ig)
for (ir=rmin; ir<=rmax; ir++) {
histp = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++)
if (*histp++ != 0) {
box->gmax = gmax = ig;
goto have_gmax;
}
}
}
have_gmax:
if (bmax>bmin) {
for (ib=bmin; ib<=bmax; ib++)
for (ir=rmin; ir<=rmax; ir++) {
histp = &histogram[ir][gmin][ib];
for (ig=gmin; ig<=gmax; ig++) {
if (*histp != 0) {
box->bmin = bmin = ib;
goto have_bmin;
}
histp += B_LEN;
}
}
have_bmin:
if (bmax>bmin)
for (ib=bmax; ib>=bmin; --ib)
for (ir=rmin; ir<=rmax; ir++) {
histp = &histogram[ir][gmin][ib];
for (ig=gmin; ig<=gmax; ig++) {
if (*histp != 0) {
bmax = ib;
goto have_bmax;
}
histp += B_LEN;
}
}
}
have_bmax: return;
}
/*******************************/
static void assign_color(ptr,rp,gp,bp)
CBOX *ptr;
byte *rp,*gp,*bp;
/*******************************/
{
int r,g,b;
r = ((ptr->rmin + ptr->rmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
g = ((ptr->gmin + ptr->gmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
b = ((ptr->bmin + ptr->bmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
*rp = (byte) r; *gp = (byte) g; *bp = (byte) b;
}
/*******************************/
static CCELL *create_colorcell(r1,g1,b1)
int r1,g1,b1;
/*******************************/
{
register int i;
register CCELL *ptr;
register byte *rp,*gp,*bp;
int ir,ig,ib;
long dist, mindist, tmp;
ir = r1 >> (COLOR_DEPTH-C_DEPTH);
ig = g1 >> (COLOR_DEPTH-C_DEPTH);
ib = b1 >> (COLOR_DEPTH-C_DEPTH);
r1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
g1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
b1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
ptr = (CCELL *) malloc(sizeof(CCELL));
*(ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
ptr->num_ents = 0;
/* step 1: find all colors inside this cell, while we're at
it, find distance of centermost point to furthest
corner */
mindist = 2000000000;
rp=rmap; gp=gmap; bp=bmap;
for (i=0; i>(COLOR_DEPTH-C_DEPTH) == ir &&
*gp>>(COLOR_DEPTH-C_DEPTH) == ig &&
*bp>>(COLOR_DEPTH-C_DEPTH) == ib) {
ptr->entries[ptr->num_ents][0] = i;
ptr->entries[ptr->num_ents][1] = 0;
++ptr->num_ents;
tmp = *rp - r1;
if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
dist = (tmp*tmp * R2FACT);
tmp = *gp - g1;
if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
dist += (tmp*tmp * G2FACT);
tmp = *bp - b1;
if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
dist += (tmp*tmp * B2FACT);
if (dist < mindist) mindist = dist;
}
/* step 3: find all points within that distance to box */
rp=rmap; gp=gmap; bp=bmap;
for (i=0; i> (COLOR_DEPTH-C_DEPTH) != ir ||
*gp >> (COLOR_DEPTH-C_DEPTH) != ig ||
*bp >> (COLOR_DEPTH-C_DEPTH) != ib) {
dist = 0;
if ((tmp = r1 - *rp)>0 || (tmp = *rp - (r1 + MAX_COLOR/C_LEN-1)) > 0 )
dist += (tmp*tmp * R2FACT);
if( (tmp = g1 - *gp)>0 || (tmp = *gp - (g1 + MAX_COLOR/C_LEN-1)) > 0 )
dist += (tmp*tmp * G2FACT);
if( (tmp = b1 - *bp)>0 || (tmp = *bp - (b1 + MAX_COLOR/C_LEN-1)) > 0 )
dist += (tmp*tmp * B2FACT);
if( dist < mindist ) {
ptr->entries[ptr->num_ents][0] = i;
ptr->entries[ptr->num_ents][1] = dist;
++ptr->num_ents;
}
}
/* sort color cells by distance, use cheap exchange sort */
{
int n, next_n;
n = ptr->num_ents - 1;
while (n>0) {
next_n = 0;
for (i=0; ientries[i][1] > ptr->entries[i+1][1]) {
tmp = ptr->entries[i][0];
ptr->entries[i][0] = ptr->entries[i+1][0];
ptr->entries[i+1][0] = tmp;
tmp = ptr->entries[i][1];
ptr->entries[i][1] = ptr->entries[i+1][1];
ptr->entries[i+1][1] = tmp;
next_n = i;
}
}
n = next_n;
}
}
return (ptr);
}
/***************************/
static void map_colortable()
/***************************/
{
int ir,ig,ib, *histp;
CCELL *cell;
histp = &histogram[0][0][0];
for (ir=0; ir>(B_DEPTH-C_DEPTH)) << C_DEPTH*2)
+ ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH)
+ (ib>>(B_DEPTH-C_DEPTH)) ) );
if (cell==NULL)
cell = create_colorcell(ir<<(COLOR_DEPTH-B_DEPTH),
ig<<(COLOR_DEPTH-B_DEPTH),
ib<<(COLOR_DEPTH-B_DEPTH));
dist = 2000000000;
for (i=0; inum_ents && dist>cell->entries[i][1]; i++) {
j = cell->entries[i][0];
d2 = rmap[j] - (ir << (COLOR_DEPTH-B_DEPTH));
d2 = (d2 * d2 * R2FACT);
tmp = gmap[j] - (ig << (COLOR_DEPTH-B_DEPTH));
d2 += (tmp*tmp * G2FACT);
tmp = bmap[j] - (ib << (COLOR_DEPTH-B_DEPTH));
d2 += (tmp*tmp * B2FACT);
if( d2 < dist ) { dist = d2; *histp = j; }
}
}
histp++;
}
}
/*****************************/
static int quant_fsdither()
/*****************************/
{
register int *thisptr, *nextptr;
int *thisline, *nextline, *tmpptr;
int r1, g1, b1, r2, g2, b2;
int i, j, imax, jmax, oval;
byte *inptr, *outptr;
int lastline, lastpixel;
imax = HIGH - 1;
jmax = WIDE - 1;
thisline = (int *) malloc(WIDE * 3 * sizeof(int));
nextline = (int *) malloc(WIDE * 3 * sizeof(int));
if (thisline == NULL || nextline == NULL) {
fprintf(stderr,"unable to allocate stuff for the 'dither' routine\n");
return 1;
}
inptr = (byte *) pic24;
outptr = (byte *) pic8;
/* get first line of picture */
for (j=WIDE * 3, tmpptr=nextline; j; j--)
*tmpptr++ = (int) *inptr++;
for (i=0; i>= (COLOR_DEPTH-B_DEPTH);
g2 >>= (COLOR_DEPTH-B_DEPTH);
b2 >>= (COLOR_DEPTH-B_DEPTH);
if ( (oval=histogram[r2][g2][b2]) == -1) {
int ci, cj;
long dist, d2, tmp;
CCELL *cell;
cell = *( ColorCells +
( ((r2>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2)
+ ((g2>>(B_DEPTH-C_DEPTH)) << C_DEPTH )
+ (b2>>(B_DEPTH-C_DEPTH)) ) );
if (cell==NULL) cell = create_colorcell(r1,g1,b1);
dist = 2000000000;
for (ci=0; cinum_ents && dist>cell->entries[ci][1]; ci++) {
cj = cell->entries[ci][0];
d2 = (rmap[cj] >> (COLOR_DEPTH-B_DEPTH)) - r2;
d2 = (d2*d2 * R2FACT);
tmp = (gmap[cj] >> (COLOR_DEPTH-B_DEPTH)) - g2;
d2 += (tmp*tmp * G2FACT);
tmp = (bmap[cj] >> (COLOR_DEPTH-B_DEPTH)) - b2;
d2 += (tmp*tmp * B2FACT);
if (d2>R_SHIFT) | ((g1&GMASK)>>G_SHIFT) |
((b1&BMASK)>>B_SHIFT));
*pp = val;
/* compute color errors */
r1 -= rmap[val];
g1 -= gmap[val];
b1 -= bmap[val];
/* Add fractions of errors to adjacent pixels */
r1 += 256; /* make positive for table indexing */
g1 += 256;
b1 += 256;
if (j!=jmax) { /* adjust RIGHT pixel */
thisptr[0] += tbl7[r1];
thisptr[1] += tbl7[g1];
thisptr[2] += tbl7[b1];
}
if (i!=imax) { /* do BOTTOM pixel */
nextptr[0] += tbl5[r1];
nextptr[1] += tbl5[g1];
nextptr[2] += tbl5[b1];
if (j>0) { /* do BOTTOM LEFT pixel */
nextptr[-3] += tbl3[r1];
nextptr[-2] += tbl3[g1];
nextptr[-1] += tbl3[b1];
}
if (j!=jmax) { /* do BOTTOM RIGHT pixel */
nextptr[3] += tbl1[r1];
nextptr[4] += tbl1[g1];
nextptr[5] += tbl1[b1];
}
nextptr += 3;
}
}
}
return 0;
}
/****************************/
static int QuickCheck(pic24,w,h,maxcol)
byte *pic24;
int w,h,maxcol;
{
/* scans picture until it finds more than 'maxcol' different colors. If it
finds more than 'maxcol' colors, it returns '0'. If it DOESN'T, it does
the 24-to-8 conversion by simply sticking the colors it found into
a colormap, and changing instances of a color in pic24 into colormap
indicies (in pic8) */
unsigned long colors[256],col;
int i, nc, low, high, mid;
byte *p, *pix;
if (maxcol>256) maxcol = 256;
/* put the first color in the table by hand */
nc = 0; mid = 0;
for (i=w*h,p=pic24; i; i--) {
col = (((u_long) *p++) << 16);
col += (((u_long) *p++) << 8);
col += *p++;
/* binary search the 'colors' array to see if it's in there */
low = 0; high = nc-1;
while (low <= high) {
mid = (low+high)/2;
if (col < colors[mid]) high = mid - 1;
else if (col > colors[mid]) low = mid + 1;
else break;
}
if (high < low) { /* didn't find color in list, add it. */
if (nc>=maxcol) return 0;
xvbcopy((char *) &colors[low], (char *) &colors[low+1],
(nc - low) * sizeof(u_long));
colors[low] = col;
nc++;
}
}
/* run through the data a second time, this time mapping pixel values in
pic24 into colormap offsets into 'colors' */
for (i=w*h,p=pic24, pix=pic8; i; i--,pix++) {
col = (((u_long) *p++) << 16);
col += (((u_long) *p++) << 8);
col += *p++;
/* binary search the 'colors' array. It *IS* in there */
low = 0; high = nc-1;
while (low <= high) {
mid = (low+high)/2;
if (col < colors[mid]) high = mid - 1;
else if (col > colors[mid]) low = mid + 1;
else break;
}
if (high < low) {
fprintf(stderr,"QuickCheck: impossible situation!\n");
exit(1);
}
*pix = mid;
}
/* and load up the 'desired colormap' */
for (i=0; i>16;
gmap[i] = (colors[i]>>8) & 0xff;
bmap[i] = colors[i] & 0xff;
}
return 1;
}
/***************************************************************/
/* The following code based on code from the 'pbmplus' package */
/* written by Jef Poskanzer */
/***************************************************************/
/* ppmquant.c - quantize the colors in a pixmap down to a specified number
**
** Copyright (C) 1989, 1991 by Jef Poskanzer.
**
** Permission to use, copy, modify, and distribute this software and its
** documentation for any purpose and without fee is hereby granted, provided
** that the above copyright notice appear in all copies and that both that
** copyright notice and this permission notice appear in supporting
** documentation. This software is provided "as is" without express or
** implied warranty.
*/
#undef max
#define max(a,b) ((a) > (b) ? (a) : (b))
#undef min
#define min(a,b) ((a) < (b) ? (a) : (b))
#undef abs
#define abs(a) ((a) >= 0 ? (a) : -(a))
#undef odd
#define odd(n) ((n) & 1)
typedef unsigned char pixval;
#define PPM_MAXMAXVAL 255
typedef struct { pixval r, g, b; } pixel;
#define PPM_GETR(p) ((p).r)
#define PPM_GETG(p) ((p).g)
#define PPM_GETB(p) ((p).b)
#define PPM_ASSIGN(p,red,grn,blu) \
{ (p).r = (red); (p).g = (grn); (p).b = (blu); }
#define PPM_EQUAL(p,q) ( (p).r == (q).r && (p).g == (q).g && (p).b == (q).b )
/* Color scaling macro -- to make writing ppmtowhatever easier. */
#define PPM_DEPTH(newp,p,oldmaxval,newmaxval) \
PPM_ASSIGN( (newp), \
(int) PPM_GETR(p) * (newmaxval) / (oldmaxval), \
(int) PPM_GETG(p) * (newmaxval) / (oldmaxval), \
(int) PPM_GETB(p) * (newmaxval) / (oldmaxval) )
/* Luminance macro. */
/*
* #define PPM_LUMIN(p) \
* ( 0.299 * PPM_GETR(p) + 0.587 * PPM_GETG(p) + 0.114 * PPM_GETB(p) )
*/
/* Luminance macro, using only integer ops. Returns an int (*256) JHB */
#define PPM_LUMIN(p) \
( 77 * PPM_GETR(p) + 150 * PPM_GETG(p) + 29 * PPM_GETB(p) )
/* Color histogram stuff. */
typedef struct colorhist_item* colorhist_vector;
struct colorhist_item { pixel color;
int value;
};
typedef struct colorhist_list_item* colorhist_list;
struct colorhist_list_item { struct colorhist_item ch;
colorhist_list next;
};
typedef colorhist_list* colorhash_table;
typedef struct box* box_vector;
struct box {
int index;
int colors;
int sum;
};
#define MAXCOLORS 32767
#define CLUSTER_MAXVAL 63
#define LARGE_LUM
#define REP_AVERAGE_PIXELS
#define FS_SCALE 1024
#define HASH_SIZE 6553
#define ppm_hashpixel(p) ((((int) PPM_GETR(p) * 33023 + \
(int) PPM_GETG(p) * 30013 + \
(int) PPM_GETB(p) * 27011) & 0x7fffffff) \
% HASH_SIZE)
/*** function defs ***/
#ifdef __STDC__
static colorhist_vector mediancut(colorhist_vector, int, int, int, int);
static int redcompare (colorhist_vector, colorhist_vector);
static int greencompare(colorhist_vector, colorhist_vector);
static int bluecompare (colorhist_vector, colorhist_vector);
static int sumcompare (box_vector, box_vector);
static colorhist_vector ppm_computecolorhist(pixel **, int,int,int,int *);
static colorhash_table ppm_computecolorhash(pixel **, int,int,int,int *);
static colorhist_vector ppm_colorhashtocolorhist(colorhash_table, int);
static colorhash_table ppm_alloccolorhash(void);
static void ppm_freecolorhist(colorhist_vector);
static void ppm_freecolorhash(colorhash_table);
#else
static colorhist_vector mediancut();
static int redcompare(), greencompare(), bluecompare();
static int sumcompare();
static colorhist_vector ppm_computecolorhist(), ppm_colorhashtocolorhist();
static colorhash_table ppm_computecolorhash(), ppm_alloccolorhash();
static void ppm_freecolorhist(), ppm_freecolorhash();
#endif
/****************************************************************************/
static int ppmquant(pic24, cols, rows, newcolors)
byte *pic24;
int cols, rows, newcolors;
{
pixel** pixels;
register pixel* pP;
int row;
register int col, limitcol;
pixval maxval, newmaxval;
int colors;
register int index;
colorhist_vector chv, colormap;
colorhash_table cht;
int i;
unsigned char *picptr;
static char *fn = "ppmquant()";
index = 0;
maxval = 255;
/*
* reformat 24-bit pic24 image (3 bytes per pixel) into 2-dimensional
* array of pixel structures
*/
if (DEBUG) fprintf(stderr,"%s: remapping to ppm-style internal fmt\n", fn);
pixels = (pixel **) malloc(rows * sizeof(pixel *));
if (!pixels) FatalError("couldn't allocate 'pixels' array");
for (row=0; rowr = *pic24++;
pP->g = *pic24++;
pP->b = *pic24++;
}
}
if (DEBUG) fprintf(stderr,"%s: done format remapping\n", fn);
/*
* attempt to make a histogram of the colors, unclustered.
* If at first we don't succeed, lower maxval to increase color
* coherence and try again. This will eventually terminate, with
* maxval at worst 15, since 32^3 is approximately MAXCOLORS.
*/
for ( ; ; ) {
if (DEBUG) fprintf(stderr, "%s: making histogram\n", fn);
chv = ppm_computecolorhist(pixels, cols, rows, MAXCOLORS, &colors);
if (chv != (colorhist_vector) 0) break;
if (DEBUG) fprintf(stderr, "%s: too many colors!\n", fn);
newmaxval = maxval / 2;
if (DEBUG) fprintf(stderr, "%s: rescaling colors (maxval=%d) %s\n",
fn, newmaxval, "to improve clustering");
for (row=0; rownext)
if (PPM_EQUAL(chl->ch.color, *pP)) {index = chl->ch.value; break;}
if (!chl /*index = -1*/) {/* No; search colormap for closest match. */
register int i, r1, g1, b1, r2, g2, b2;
register long dist, newdist;
r1 = PPM_GETR( *pP );
g1 = PPM_GETG( *pP );
b1 = PPM_GETB( *pP );
dist = 2000000000;
for (i=0; ich.color = *pP;
chl->ch.value = index;
chl->next = cht[hash];
cht[hash] = chl;
}
*picptr++ = index;
++col;
++pP;
}
while (col != limitcol);
}
/* rescale the colormap and load the XV colormap */
for (i=0; i maxr) maxr = v;
v = PPM_GETG( chv[indx + i].color );
if (v < ming) ming = v;
if (v > maxg) maxg = v;
v = PPM_GETB( chv[indx + i].color );
if (v < minb) minb = v;
if (v > maxb) maxb = v;
}
/*
** Find the largest dimension, and sort by that component. I have
** included two methods for determining the "largest" dimension;
** first by simply comparing the range in RGB space, and second
** by transforming into luminosities before the comparison. You
** can switch which method is used by switching the commenting on
** the LARGE_ defines at the beginning of this source file.
*/
{
/* LARGE_LUM version */
pixel p;
int rl, gl, bl;
PPM_ASSIGN(p, maxr - minr, 0, 0);
rl = PPM_LUMIN(p);
PPM_ASSIGN(p, 0, maxg - ming, 0);
gl = PPM_LUMIN(p);
PPM_ASSIGN(p, 0, 0, maxb - minb);
bl = PPM_LUMIN(p);
if (rl >= gl && rl >= bl)
qsort( (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
redcompare );
else if (gl >= bl)
qsort( (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
greencompare );
else qsort( (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
bluecompare );
}
/*
** Now find the median based on the counts, so that about half the
** pixels (not colors, pixels) are in each subdivision.
*/
lowersum = chv[indx].value;
halfsum = sm / 2;
for (i=1; i= halfsum) break;
lowersum += chv[indx + i].value;
}
/*
** Split the box, and sort to bring the biggest boxes to the top.
*/
bv[bi].colors = i;
bv[bi].sum = lowersum;
bv[boxes].index = indx + i;
bv[boxes].colors = clrs - i;
bv[boxes].sum = sm - lowersum;
++boxes;
qsort( (char*) bv, boxes, sizeof(struct box), sumcompare );
} /* while (boxes ... */
/*
** Ok, we've got enough boxes. Now choose a representative color for
** each box. There are a number of possible ways to make this choice.
** One would be to choose the center of the box; this ignores any structure
** within the boxes. Another method would be to average all the colors in
** the box - this is the method specified in Heckbert's paper. A third
** method is to average all the pixels in the box. You can switch which
** method is used by switching the commenting on the REP_ defines at
** the beginning of this source file.
*/
for (bi=0; bimaxval) r = maxval; /* avoid math errors */
g = g / sum; if (g>maxval) g = maxval;
b = b / sum; if (b>maxval) b = maxval;
PPM_ASSIGN( colormap[bi].color, r, g, b );
}
free(bv);
return colormap;
}
/**********************************/
static int redcompare(ch1, ch2)
colorhist_vector ch1, ch2;
{
return (int) PPM_GETR( ch1->color ) - (int) PPM_GETR( ch2->color );
}
/**********************************/
static int greencompare(ch1, ch2)
colorhist_vector ch1, ch2;
{
return (int) PPM_GETG( ch1->color ) - (int) PPM_GETG( ch2->color );
}
/**********************************/
static int bluecompare( ch1, ch2 )
colorhist_vector ch1, ch2;
{
return (int) PPM_GETB( ch1->color ) - (int) PPM_GETB( ch2->color );
}
/**********************************/
static int sumcompare( b1, b2 )
box_vector b1, b2;
{
return b2->sum - b1->sum;
}
/****************************************************************************/
static colorhist_vector
ppm_computecolorhist(pixels, cols, rows, maxcolors, colorsP)
pixel** pixels;
int cols, rows, maxcolors;
int* colorsP;
{
colorhash_table cht;
colorhist_vector chv;
cht = ppm_computecolorhash(pixels, cols, rows, maxcolors, colorsP);
if (!cht) return (colorhist_vector) 0;
chv = ppm_colorhashtocolorhist(cht, maxcolors);
ppm_freecolorhash(cht);
return chv;
}
/****************************************************************************/
static colorhash_table ppm_computecolorhash(pixels, cols, rows,
maxcolors, colorsP )
pixel** pixels;
int cols, rows, maxcolors;
int* colorsP;
{
colorhash_table cht;
register pixel* pP;
colorhist_list chl;
int col, row, hash;
cht = ppm_alloccolorhash( );
*colorsP = 0;
/* Go through the entire image, building a hash table of colors. */
for (row=0; rownext)
if (PPM_EQUAL(chl->ch.color, *pP)) break;
if (chl != (colorhist_list) 0) ++(chl->ch.value);
else {
if ((*colorsP)++ > maxcolors) {
ppm_freecolorhash(cht);
return (colorhash_table) 0;
}
chl = (colorhist_list) malloc(sizeof(struct colorhist_list_item));
if (!chl) FatalError("ran out of memory computing hash table");
chl->ch.color = *pP;
chl->ch.value = 1;
chl->next = cht[hash];
cht[hash] = chl;
}
}
return cht;
}
/****************************************************************************/
static colorhash_table ppm_alloccolorhash()
{
colorhash_table cht;
int i;
cht = (colorhash_table) malloc( HASH_SIZE * sizeof(colorhist_list) );
if (!cht) FatalError("ran out of memory allocating hash table");
for (i=0; inext) {
/* Add the new entry. */
chv[j] = chl->ch;
++j;
}
return chv;
}
/****************************************************************************/
static void ppm_freecolorhist( chv )
colorhist_vector chv;
{
free( (char*) chv );
}
/****************************************************************************/
static void ppm_freecolorhash( cht )
colorhash_table cht;
{
int i;
colorhist_list chl, chlnext;
for (i=0; inext;
free( (char*) chl );
}
free( (char*) cht );
}