/* See jspgm_medcutx.h ** Last edited on 2013-10-21 00:32:14 by stolfilocal ** ** Copyright (C) 1989, 1991 by Jef Poskanzer. See note at end of file. */ #include #include #include #include /* Internal types */ typedef struct { pnm_sample_t lo; /* Lowest gray in box */ pnm_sample_t hi; /* Highest gray in box */ float center; /* The ideal box centroid */ pnm_sample_t rep; /* The box representative */ float spread; /* Total quantization error for entries in box */ } pgm_box; typedef pgm_box* pgm_box_vector; /* Internal prototypes */ typedef int (*qcomparefn)(const void *, const void *); extern void qsort (void *items, size_t nitems, size_t itemsize, qcomparefn cmp); static void pgm_set_box( pgm_box_vector b, long *gh, pnm_sample_t lo, pnm_sample_t hi, pnm_sample_t maxval ); static void pgm_box_center( long *gh, pnm_sample_t lo, pnm_sample_t hi, pnm_sample_t maxval, float *centerp, pnm_sample_t *repp ); static float pgm_box_spread( long *gh, pnm_sample_t lo, pnm_sample_t hi, pnm_sample_t rep, pnm_sample_t maxval ); static int pgm_spread_compare(const pgm_box *b1, const pgm_box *b2); static int pgm_gray_compare(const pnm_sample_t *g1, const pnm_sample_t *g2); static pgm_box_vector new_pgm_box_vector(int n); static pnm_sample_t* new_pgm_pixel_vector(int n); /* Implementation */ extern pgm_pixel_vector pgm_median_cut_x( long *gh, /* Pixel count indexed by gray level */ pnm_sample_t maxval, /* maxval of pixel values, also size of "gh" */ int *newgraysp /* In: desired number of grays, out: number chosen */ ) /* Here is the fun part, the median-cut graymap generator. This is based on Paul Heckbert's paper "Color Image Quantization for Frame Buffer Display", SIGGRAPH '82 Proceedings, page 297. */ { pgm_pixel_vector gm; /* The graymap */ pgm_box_vector bv; /* The box list */ register int bi; register pnm_sample_t g, lo, hi; float ctr; int boxes; bv = new_pgm_box_vector(*newgraysp); /* Set up the initial box. */ pgm_set_box(&(bv[0]), gh, 0, maxval, maxval); boxes = 1; /* Main loop: split boxes until we have enough. */ while (boxes < (*newgraysp)) { /* Box bv[0] should have the largest spread: */ if (bv[0].spread <= 0.0) break; /* exact graymap! */ lo = bv[0].lo; hi = bv[0].hi; if (lo >= hi) pnm_error("bad pgm_box spread"); ctr = bv[0].center; /* Split box at center: */ if (ctr < (float)lo) pnm_error("bad pgm_box center"); if (ctr >= (float)hi) pnm_error("bad pgm_box center"); g = (pnm_sample_t)ctr; pnm_sample_t g1 = (pnm_sample_t)(g+1); pgm_set_box(&(bv[0]), gh, lo, g, maxval); pgm_set_box(&(bv[boxes]), gh, g1, hi, maxval); ++boxes; /* Sort to bring the worst boxes to the top. */ qsort((void*) bv, boxes, sizeof(pgm_box), (qcomparefn) pgm_spread_compare); } /* Ok, we've got enough boxes. Collect their centroids: */ gm = new_pgm_pixel_vector(boxes); for (bi = 0; bi < boxes; ++bi) { gm[bi] = bv[bi].rep; } qsort((void*)gm, boxes, sizeof(pnm_sample_t), (qcomparefn) pgm_gray_compare); (*newgraysp) = boxes; free(bv); return (gm); } static void pgm_set_box( pgm_box_vector b, long *gh, pnm_sample_t lo, pnm_sample_t hi, pnm_sample_t maxval ) /* Sets lo and hi, and computes center, rep, spread */ { b->lo = lo; b->hi = hi; pgm_box_center(gh, lo, hi, maxval, &(b->center), &(b->rep)); b->spread = pgm_box_spread(gh, lo, hi, b->rep, maxval); } static void pgm_box_center( long *gh, pnm_sample_t lo, pnm_sample_t hi, pnm_sample_t maxval, float *centerp, pnm_sample_t *repp ) /* Compute a "central" gray level for this box, and rounds it to a "representative" level. */ { long w; float fg, fw; float sumg = 0.0, sumw = 0.0; pnm_sample_t maxg = 0; pnm_sample_t ming = maxval; pnm_sample_t g; #ifdef USE_LUM float offset = 0.05 * ((float)maxval); #endif /*USE_LUM*/ for (g = lo; g <= hi; ++g) { w = gh[g]; if (w > 0) { if (g < ming) ming = g; if (g > maxg) maxg = g; fg = (float)(g); fw = (float)(w); #ifdef USE_LUM fg = fg/(fg + offset); #endif /*USE_LUM*/ sumg += fw*fg; sumw += fw; } } if (sumw <= 0.0) pnm_error("empty pgm_box"); fg = sumg / sumw; #ifdef USE_LUM fg = (offset*fg)/(1.0 - fg); #endif /*USE_LUM*/ g = (pnm_sample_t)(fg); if (g > maxg) g = maxg; if (g < ming) g = ming; (*centerp) = fg; (*repp) = g; } static float pgm_box_spread( long *gh, pnm_sample_t lo, pnm_sample_t hi, pnm_sample_t rep, pnm_sample_t maxval ) /* Compute the box spread, relative to the appointed representative. */ { float fg, fw; float sumgg = 0.0; pnm_sample_t g; long w; float frep = (float)rep; #ifdef USE_LUM float offset = 0.05 * ((float)maxval); frep = frep/(frep + offset); #endif /*USE_LUM*/ for (g = lo; g <= hi; ++g) { w = gh[g]; if (w > 0) { fg = (float)(g); fw = (float)(w); #ifdef USE_LUM fg = fg/(fg + offset); #endif /*USE_LUM*/ fg = fg - frep; sumgg += fw*(fg*fg); } } return(sumgg); } static int pgm_spread_compare(const pgm_box *b1, const pgm_box *b2) { return ((int) (b1->spread > b2->spread ? -1 : (b1->spread < b2->spread ? 1 : 0)) ); } static int pgm_gray_compare(const pnm_sample_t *g1, const pnm_sample_t *g2) { return ((int) (*g1) - (*g2)); } static pgm_box_vector new_pgm_box_vector(int n) { pgm_box_vector bv = (pgm_box_vector)pnm_malloc(n*sizeof(pgm_box)); return(bv); } static pnm_sample_t* new_pgm_pixel_vector(int n) { pnm_sample_t *gv = (pnm_sample_t*)pnm_malloc(n*sizeof(pnm_sample_t)); return(gv); } /* 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. */