Subject: v19i054: FBM, image manipulation library, Part08/08 Newsgroups: comp.sources.unix Sender: sources Approved: rsalz@uunet.UU.NET Submitted-by: Michael.Mauldin@NL.CS.CMU.EDU Posting-number: Volume 19, Issue 54 Archive-name: fbm/part08 #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh 'fbquant.c' <<'END_OF_FILE' X/**************************************************************** X * fbquant.c: FBM Library 0.93 (Beta test) 03-May-89 Michael Mauldin X * X * Copyright (C) 1989 by Michael Mauldin. Permission is granted to X * use this file in whole or in part provided that you do not sell it X * for profit and that this copyright notice is retained unchanged. X * X * fbquant: Convert an RGB color image to mapped color format (color X * quantization step). Floyd-Steinberg dithering is used X * to reduce color banding. The quantization used is a X * modification of Heckbert's median cut. X * X * USAGE X * % fbquant [ -c ] [ - ] < rgb > mapped X * X * EDITLOG X * LastEditDate = Wed May 3 21:55:36 1989 - Michael Mauldin X * LastFileName = /usr2/mlm/src/misc/fbm/fbquant.c X * X * HISTORY X * 03-May-89 Michael Mauldin (mlm) at Carnegie Mellon University X * Clear FBM pointers before allocate X * X * 07-Apr-89 Michael Mauldin (mlm) at Carnegie Mellon University X * Add provision for using colormap from another image. X * X * 07-Mar-89 Michael Mauldin (mlm) at Carnegie Mellon University X * Beta release (version 0.93) mlm@cs.cmu.edu X * X * 26-Feb-89 Michael Mauldin (mlm) at Carnegie Mellon University X * Changes for small color maps. Fixed bug with unsigned X * arithmetic that ruined dithering for images with small X * colormaps. Added error limiting in the Floyd-Steinberg X * code to prevent color "shadowing" that occurs with small X * numbers of colors. Also change to use colors 0..n-1 instead X * of reserving colors 0 and n-1 for Sun foreground/background X * colors. X * X * 11-Nov-88 Michael Mauldin (mlm) at Carnegie Mellon University X * Created. X * X * References: Uses a variant of Heckbert's adaptive partitioning X * algorithm. See Computer Graphics, v16n3 July 1982 X ****************************************************************/ X X# include X# include "fbm.h" X Xint cmp_red(), cmp_grn(), cmp_blu(), cmp_cmap(), cmp_int(); X X# define RD 0 X# define GR 1 X# define BL 2 X# define REDMASK 0076000 X# define REDSHFT 10 X# define GRNMASK 0001740 X# define GRNSHFT 5 X# define BLUMASK 0000037 X# define BLUSHFT 0 X# define CUBITS 5 X# define CUBIGN (8-CUBITS) X# define CUBSID 32 X# define CUBSIZ 32768 X# define MAXSHRT 32767 X# define MAXERR 32 X X# define GETR(X) (((X) & REDMASK) >> REDSHFT) X# define GETG(X) (((X) & GRNMASK) >> GRNSHFT) X# define GETB(X) ((X) & BLUMASK) X X# define CLRINDEX(R,G,B) \ X (((R) << REDSHFT) & REDMASK | \ X ((G) << GRNSHFT) & GRNMASK | \ X ((B) & BLUMASK)) X X# define CLRINDEX8(R,G,B) \ X (((R) << (REDSHFT-CUBIGN)) & REDMASK | \ X ((G) << (GRNSHFT-CUBIGN)) & GRNMASK | \ X ((B) >> (CUBIGN)) & BLUMASK) X X# define GETR8(X) (((X) & REDMASK) >> (REDSHFT-CUBIGN)) X# define GETG8(X) (((X) & GRNMASK) >> (GRNSHFT-CUBIGN)) X# define GETB8(X) (((X) & BLUMASK) << CUBIGN) X Xtypedef struct cstruct { X unsigned char rd, gr, bl, indx; X} COLOR; X XCOLOR *cmap = NULL; X Xtypedef struct pix_struct { X short cnt; X short color; X} PIXEL; X Xint debug=0, verbose=0, colors=256, showcolor=0, dither=1; X X/**************************************************************** X * main X ****************************************************************/ X X# define USAGE "Usage: fbquant [ -c ] [ - ] < rgb > mapped" X X#ifndef lint Xstatic char *fbmid = X "$FBM fbquant.c <0.93> 07-Mar-89 (C) 1989 by Michael Mauldin$"; X#endif X Xmain (argc, argv) Xchar *argv[]; X{ FBM input, output, mapimage; /* Images */ X int hist[CUBSIZ]; /* Color cube 32x32x32 for histogram */ X int outtype = DEF_8BIT; /* Output format desired */ X char *mapfile = NULL; /* Name of file to copy map from */ X register int c; X X /* Clear pointers */ X input.bm = input.cm = (unsigned char *) NULL; X output.bm = output.cm = (unsigned char *) NULL; X mapimage.bm = mapimage.cm = (unsigned char *) NULL; X X /* Get the options */ X while (--argc > 0 && (*++argv)[0] == '-') X { while (*++(*argv)) X { switch (**argv) X { case 'c': colors = atoi (*argv+1); SKIPARG; break; X case 'm': mapfile = *argv+1; SKIPARG; break; X case 'n': dither = 0; X case 'd': debug++; break; X case 'D': showcolor++; break; X case 'v': verbose++; break; X case 'A': outtype = FMT_ATK; break; X case 'B': outtype = FMT_FACE; break; X case 'F': outtype = FMT_FBM; break; X case 'G': outtype = FMT_GIF; break; X case 'I': outtype = FMT_IFF; break; X case 'L': outtype = FMT_LEAF; break; X case 'M': outtype = FMT_MCP; break; X case 'P': outtype = FMT_PBM; break; X case 'S': outtype = FMT_SUN; break; X case 'T': outtype = FMT_TIFF; break; X case 'X': outtype = FMT_X11; break; X case 'Z': outtype = FMT_PCX; break; X default: fprintf (stderr, "%s\n", USAGE); X exit (1); X } X } X } X X /* Check arguments */ X if (colors > 256 || colors < 8) X { fprintf (stderr, "fbquant can only handle 8..256 colors\n"); X exit (1); X } X X /* Open file if name given as argument */ X if (! read_bitmap (&input, (argc > 0) ? argv[0] : (char *) NULL)) X { exit (1); } X X /* Read colormap from map image (if specified) */ X if (mapfile != NULL) X { if (!read_bitmap (&mapimage, mapfile)) X { perror (mapfile); exit (1); } X X if (mapimage.hdr.clrlen == 0) X { fprintf (stderr, "fbquant: %s: no map\n", mapfile); exit (1); } X X /* Dont care about the map image, just its colormap */ X free (mapimage.bm); mapimage.bm = NULL; X X colors = mapimage.hdr.clrlen / 3; X cmap = (COLOR *) malloc ((unsigned) colors * sizeof (COLOR)); X X for (c=0; chdr.cols, height = image->hdr.rows; X int rowlen = image->hdr.rowlen, plnlen = image->hdr.plnlen; X int used=0; X X /* Clear the histogram */ X for (i=0; ibm[j*rowlen]); X gp = rp+plnlen; X bp = gp+plnlen; X X for (i=0; icolor = i; X k = hist[i]; X b->cnt = (k > MAXSHRT) ? MAXSHRT : k; X b++; X } X X /* Move all non-zero count pixels to the front of the list */ X for (i=0, used=0; i 0) box[used++] = box[i]; } X X /*-------- Special case if we didnt need all colors --------*/ X if (used <= colors) X { X /* Copy the colors actually found */ X for (i=0; i boxlen) X { fprintf (stderr, "boxlen %d is less numclr %d, panic!\n than", X boxlen, numclr); X fflush (stderr); X abort (); X } X X /* Base case: only one color, assign the average for this cell */ X if (numclr <= 1) X { red = box_avg_red (box, boxlen); X grn = box_avg_grn (box, boxlen); X blu = box_avg_blu (box, boxlen); X X /* Map x to x+4, because the histogram maps values to multiples of 8 */ X cmap[clr].rd = red + 4; X cmap[clr].gr = grn + 4; X cmap[clr].bl = blu + 4; X X if (debug) X { fprintf (stderr, "\t\tassigning color %d <%d,%d,%d> (%d)\n", X clr, cmap[clr].rd, cmap[clr].gr, cmap[clr].bl, X box_weight (box, boxlen)); X } X X return; X } X X /* Gather statistics about the boxes contents */ X minv[RD] = minv[GR] = minv[BL] = CUBSID; X maxv[RD] = maxv[GR] = maxv[BL] = 0; X numv[RD] = numv[GR] = numv[BL] = 0; X for (i=0; i maxv[RD]) maxv[RD] = red; X if (grn < minv[GR]) minv[GR] = grn; X if (grn > maxv[GR]) maxv[GR] = grn; X if (blu < minv[BL]) minv[BL] = blu; X if (blu > maxv[BL]) maxv[BL] = blu; X X if (++pcnt[RD][red] == 1) numv[RD]++; X if (++pcnt[GR][grn] == 1) numv[GR]++; X if (++pcnt[BL][blu] == 1) numv[BL]++; X } X X /* Special case, boxlen = numclr, just assign each box one color */ X if (boxlen == numclr) X { for (i=0; i maxdif) { maxdif = dif; split = RD; } X if ((dif = (maxv[GR] - minv[GR])) > maxdif) { maxdif = dif; split = GR; } X if ((dif = (maxv[BL] - minv[BL])) > maxdif) { maxdif = dif; split = BL; } X X /* Sort along the chosen dimension */ X switch (split) X { case RD: qsort (box, boxlen, sizeof (*box), cmp_red); break; X case GR: qsort (box, boxlen, sizeof (*box), cmp_grn); break; X case BL: qsort (box, boxlen, sizeof (*box), cmp_blu); break; X default: fprintf (stderr, "panic in split_box, split = -1\n"); X fflush (stderr); fflush (stdout); abort (); X } X X /* X * Split at the median, but make sure there are at least numclr/2 X * different colors on each side of the split, to avoid wasting X * colors. X * X * Note: need to keep in mind that when the box is large, dont split X * too close to one edge. X */ X X half = numclr / 2; X top = box; bot = box + (boxlen-1); X topw = top->cnt; botw = bot->cnt; X X /* Set top and bot to point to min/max feasible splits */ X while ((top-box)+1 < half) { top++; topw += top->cnt; } X while ((boxlen-(bot-box)) < half) { bot--; botw += bot->cnt; } X X /* Move top and bottom towards each other 1/8 of remaining distance */ X c = (bot-top) / 8; X for (i=0; icnt; } X for (i=0; icnt; } X X /* Now search for median */ X while (top < bot) X { if (topw < botw) { top++; topw += top->cnt; } X else { bot--; botw += bot->cnt; } X } X X /* Decide which half gets the midpoint */ X if (topw > botw) /* Median wants to go with top */ X { sbox = (top-box) + 1; X snum = numclr - half; X } X else /* Median wants to go with bottom */ X { sbox = (top - box); X snum = half; X } X X /* Handle boundary conditions with number of colors vs box size */ X if (sbox == 0) sbox++; X else if (sbox == boxlen) sbox--; X X while (snum > sbox) snum--; X while (numclr-snum > boxlen-sbox) snum++; X X# ifndef OPTIMIZE X /* Check for boundary condition errors */ X if (snum <= 0 || snum >= numclr) X { fprintf (stderr, "panic, using zero colors for box\n"); X fflush (stderr); X abort (); X } X X if (boxlen-sbox < numclr-snum) X { fprintf (stderr, "panic, about to used %d boxes for %d colors\n", X boxlen-sbox, numclr-snum); X fflush (stderr); X abort (); X } X X if (sbox < snum) X { fprintf (stderr, "panic, about to used %d boxes for %d colors\n", X sbox, snum); X fflush (stderr); X abort (); X } X# endif X X if (debug) X { int count = numclr, depth = 8; X while (count > 0) { depth--; count /= 2; } X for (i=0; i", X 0, boxlen-1, numclr, X minv[RD], maxv[RD], numv[RD], X minv[GR], maxv[GR], numv[GR], X minv[BL], maxv[BL], numv[BL]); X fprintf (stderr, " %c [%d..%d|%d] [%d..%d|%d]\n", X "RGB"[split], 0, sbox-1, snum, sbox, boxlen-1, numclr-snum); X } X X /* Now recurse and split each sub-box */ X split_box (box, sbox, clr, snum, cmap); X split_box (box+sbox, boxlen - sbox, clr+snum, numclr-snum, cmap); X} X X/**************************************************************** X * box_weight: Determine the total count of a box X ****************************************************************/ X Xbox_weight (box, boxlen) Xregister PIXEL *box; Xregister int boxlen; X{ register int sum = 0, i; X X for (i=0; icolor) - GETR(b->color)) X { return (r); } X X if (r = GETG(a->color) - GETG(b->color)) X { return (r); } X X if (r = GETB(a->color) - GETB(b->color)) X { return (r); } X X return (0); X} X X/**************************************************************** X * sort by increasing green ( then blue and red ) X ****************************************************************/ X Xcmp_grn (a, b) XPIXEL *a, *b; X{ register r; X X if (r = GETG(a->color) - GETG(b->color)) X { return (r); } X X if (r = GETB(a->color) - GETB(b->color)) X { return (r); } X X if (r = GETR(a->color) - GETR(b->color)) X { return (r); } X X return (0); X} X X/**************************************************************** X * sort by increasing blue ( then red and green ) X ****************************************************************/ X Xcmp_blu (a, b) XPIXEL *a, *b; X{ register r; X X if (r = GETB(a->color) - GETB(b->color)) X { return (r); } X X if (r = GETR(a->color) - GETR(b->color)) X { return (r); } X X if (r = GETG(a->color) - GETG(b->color)) X { return (r); } X X return (0); X} X X/**************************************************************** X * clr_quantize: Do Floyd Steinberg quantizing on the image X ****************************************************************/ X Xclr_quantize (input, output, cmap, colors) XFBM *input, *output; XCOLOR *cmap; Xint colors; X{ int **cerr, **lerr, **terr; X int width = input->hdr.cols, height = input->hdr.rows; X int rowlen = input->hdr.rowlen, plnlen = input->hdr.plnlen; X register int i, j; X register int rd, gr, bl; X int rderr, grerr, blerr, clr; X unsigned char *rp, *gp, *bp, *obm; X X /*-------- Copy colormap into output bitmap --------*/ X for (i=0; icm[i] = cmap[i].rd; X output->cm[i+colors] = cmap[i].gr; X output->cm[i+colors+colors] = cmap[i].bl; X } X X /* X * Precompute necessary nearest neighbor query info. Note that we wait X * until after copying the colormap, since init reorders it X */ X X init_nearest (cmap, colors); X X /*-------- Do halftoning --------*/ X cerr = (int **) malloc (3 * sizeof (int *)); X lerr = (int **) malloc (3 * sizeof (int *)); X cerr[RD] = (int *) malloc (width * sizeof (int)); X cerr[GR] = (int *) malloc (width * sizeof (int)); X cerr[BL] = (int *) malloc (width * sizeof (int)); X lerr[RD] = (int *) malloc (width * sizeof (int)); X lerr[GR] = (int *) malloc (width * sizeof (int)); X lerr[BL] = (int *) malloc (width * sizeof (int)); X X /*-------- Just use the nearest color everywhere --------*/ X if (!dither) X { X for (j=0; jbm[j*rowlen]); X gp = rp+plnlen; X bp = gp+plnlen; X obm = &(output->bm[j*rowlen]); X X for (i=0; ibm; gp = rp+plnlen; bp = gp+plnlen; X obm = output->bm; X for (i=0; ibm; gp = rp+plnlen; bp = gp+plnlen; X obm = output->bm; X for (j=0; jbm[width-1]); gp = rp + plnlen; bp = gp + plnlen; X obm = &(output->bm[width-1]); X for (j=0; jbm[j*rowlen+1]); X gp = rp+plnlen; X bp = gp+plnlen; X obm = &(output->bm[j*rowlen+1]); X X for (i=1; i>= 4; /* Divide by 16 */ X grerr >>= 4; /* Divide by 16 */ X blerr >>= 4; /* Divide by 16 */ X X /* Chose nearest color to adjusted RGB value */ X rd += rderr; gr += grerr; bl += blerr; X X clr = nearest (rd, gr, bl, cmap, colors); X *obm++ = cmap[clr].indx; X X /* Compute accumulated error for this pixel */ X rd -= (int) cmap[clr].rd; X gr -= (int) cmap[clr].gr; X bl -= (int) cmap[clr].bl; X X /* Limit error (avoids color shadows) */ X if (rd < -MAXERR || rd > MAXERR) rd = (rd * 3) >> 2; X if (gr < -MAXERR || gr > MAXERR) gr = (gr * 3) >> 2; X if (bl < -MAXERR || bl > MAXERR) bl = (bl * 3) >> 2; X X /* Store errors in error vectors */ X cerr[RD][i] = rd; X cerr[GR][i] = gr; X cerr[BL][i] = bl; X } X X /* Swap error vectors */ X terr = lerr; lerr = cerr; cerr = terr; X } X} X X/**************************************************************** X * nearest: Choose nearest color X ****************************************************************/ X Xshort cache[CUBSIZ]; X Xinit_nearest (cmap, colors) XCOLOR *cmap; Xint colors; X{ register int i; X X /* Initialize the cache */ X for (i=0; i [%d]\n", X i, cmap[i].rd, cmap[i].gr, cmap[i].bl, cmap[i].indx); X } X } X} X X/* Fast square macro, uses local variable to avoid mulitple eval of X */ X# define SQR(X) (sqrtmp = (X), sqrtmp*sqrtmp) X X/* Fast distance macro */ X# define CDIST(CPTR,CR,CG,CB) \ X(sumtmp = SQR (((int) ((CPTR)->rd)) - CR), \ X sumtmp += SQR (((int) ((CPTR)->gr)) - CG), \ X sumtmp += SQR (((int) ((CPTR)->bl)) - CB), \ X sumtmp) X X# define restrict(X) ((X) < 0 ? 0 : (X) > 255 ? 255 : (X)) X Xnearest (rd, gr, bl, cmap, colors) Xint rd, gr, bl; XCOLOR *cmap; Xint colors; X{ register int clr, sqrtmp, sumtmp; X register COLOR *a, *b, *c, *best, *ctail; X int cindx, bestd, dist; X X rd = restrict (rd); X gr = restrict (gr); X bl = restrict (bl); X X /* Find array index in cache */ X cindx = CLRINDEX8 (rd, gr, bl); X X /* Check cache for color value */ X if ((clr = cache[cindx]) >= 0) X { return (clr); } X X /* X * Search through colormap for nearest neighbor: X * 1) Find nearest red value by binary search X * 2) Search up and down, keeping best point X * 3) Terminate search when red difference is greater than best pt X */ X X /* Binary search for nearest red value */ X ctail = &cmap[colors]; X for (a=cmap, b= ctail-1; ard, b-cmap, b->rd, c-cmap, c->rd); X } X X if (c->rd == rd) X { break; } X else if (c->rd < rd) X { a = ++c; } X else X { b = c; } X } X X /* X * c now points to closest red value, search up and down for closer X * Euclidean distance, and stop search when the red distance alone X * exceeds the bext found. X */ X X /* Set best and bestd to best red value */ X best = c; X bestd = CDIST (c, rd, gr, bl); X X if (debug && verbose) X fprintf (stderr, "Found c=%d (%d) dist = %d\n", c-cmap, c->rd, bestd); X X /* a and b are search pointers up and down */ X a = c-1; X b = c+1; X X while (bestd > 0 && (a >= cmap || b < ctail)) X { X if (debug && verbose) X { fprintf (stderr, " search: bestd %d, best %d|%d, a %d, b %d\n", X bestd, best-cmap, best->indx, a-cmap, b-cmap); X } X X if (a >= cmap) X { if ((dist = CDIST (a, rd, gr, bl)) < bestd) X { best = a; bestd = dist; } X X if (SQR ((int) a->rd - rd) >= bestd) a = cmap-1; X else a--; X } X X if (b < ctail) X { if ((dist = CDIST (b, rd, gr, bl)) < bestd) X { best = b; bestd = dist; } X X if (SQR ((int) b->rd - rd) >= bestd) b = ctail; X else b++; X } X } X X if (best < cmap || best >= ctail) X { perror ("returning invalid color\n"); X abort (); X } X X clr = (best - cmap); X X if (debug) X { fprintf (stderr, "Nearest(%3d,%3d,%3d) => <%3d,%3d,%3d> [%d]\n", X rd, gr, bl, best->rd, best->gr, best->bl, best->indx); X } X X return ((cache[cindx] = clr)); X} X X/**************************************************************** X * sort colormap by decreasing red ( then green and blue ) X ****************************************************************/ X Xcmp_cmap (a, b) Xregister COLOR *a, *b; X{ register int r; X X if (r = (a->rd - b->rd)) { return (r); } X if (r = (a->gr - b->gr)) { return (r); } X if (r = (a->bl - b->bl)) { return (r); } X X return (0); X} X X/**************************************************************** X * sort colormap by increasing intensity (Use NTSC weights) X ****************************************************************/ X X# define RW 299 X# define GW 587 X# define BW 114 X Xcmp_int (a, b) Xregister COLOR *a, *b; X{ register int ai, bi; X X ai = RW * a->rd + GW * a->gr + BW * a->bl; X bi = RW * b->rd + GW * b->gr + BW * b->bl; X X return (ai - bi); X} END_OF_FILE if test 26110 -ne `wc -c <'fbquant.c'`; then echo shar: \"'fbquant.c'\" unpacked with wrong size! fi # end of 'fbquant.c' fi echo shar: End of archive 8 \(of 8\). cp /dev/null ark8isdone MISSING="" for I in 1 2 3 4 5 6 7 8 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked all 8 archives. rm -f ark[1-9]isdone else echo You still need to unpack the following archives: echo " " ${MISSING} fi ## End of shell archive. exit 0