rsalz@uunet.uu.net (Rich Salz) (06/09/89)
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 <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 8 (of 8)."
# Contents: fbquant.c
# Wrapped by rsalz@fig.bbn.com on Fri Jun 9 08:38:31 1989
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'fbquant.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'fbquant.c'\"
else
echo shar: Extracting \"'fbquant.c'\" \(26110 characters\)
sed "s/^X//" >'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<numcolors> ] [ -<type> ] < 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 <stdio.h>
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<numcolors> ] [ -<type> ] < 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; c<colors; c++)
X { cmap[c].rd = mapimage.cm[c];
X cmap[c].gr = mapimage.cm[c+colors];
X cmap[c].bl = mapimage.cm[c+colors*2];
X cmap[c].indx = c;
X }
X
X fprintf (stderr, "Quantizing \"%s\" [%dx%d] with %d colors from %s\n",
X input.hdr.title, input.hdr.cols, input.hdr.rows, colors, mapfile);
X }
X else
X { fprintf (stderr, "Quantizing \"%s\" [%dx%d] with %d colors\n",
X input.hdr.title, input.hdr.cols, input.hdr.rows, colors);
X }
X
X if (input.hdr.planes != 3 || input.hdr.bits != 8)
X { fprintf (stderr, "fbquant can only handle 24bit RGB inputs\n");
X exit (1);
X }
X
X /* Now build header for output bit map */
X output.hdr = input.hdr;
X output.hdr.planes = 1;
X output.hdr.clrlen = 3 * colors;
X
X /* Allocate space for output */
X alloc_fbm (&output);
X
X /* Build colormap by sampling and mcut if not specified */
X if (mapfile == NULL)
X {
X cmap = (COLOR *) malloc ((unsigned) colors * sizeof (COLOR));
X sample_image (&input, hist);
X build_colormap (hist, cmap, colors);
X }
X
X /* Use Floyd-Steinberg error diffusion to quantize using the new cmap */
X clr_quantize (&input, &output, cmap, colors);
X
X /* Write out the result */
X if (write_bitmap (&output, stdout, outtype))
X { exit (0); }
X
X exit (1);
X}
X
X/****************************************************************
X * sample_image:
X ****************************************************************/
X
Xsample_image (image, hist)
XFBM *image;
Xint *hist;
X{ register int i, j;
X register unsigned char *rp, *gp, *bp;
X int width = image->hdr.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; i<CUBSIZ; i++) hist[i] = 0;
X
X /* Now count */
X for (j=0; j<height; j++)
X { rp = &(image->bm[j*rowlen]);
X gp = rp+plnlen;
X bp = gp+plnlen;
X
X for (i=0; i<width; i++)
X { if (++hist[ CLRINDEX8 (*rp++, *gp++, *bp++) ] == 1) used++; }
X }
X
X if (debug)
X { fprintf (stderr, "Done counting, used %d colors for %d pixels\n",
X used, width*height);
X }
X}
X
X/****************************************************************
X * build_colormap:
X ****************************************************************/
X
X# define SWAP(A,B) (t=A,A=B,B=t)
X
Xbuild_colormap (hist, cmap, colors)
Xint *hist;
XCOLOR *cmap;
Xint colors;
X{ register int i, k;
X PIXEL box[CUBSIZ];
X register PIXEL *b;
X int used=0, t;
X
X /* Build the first box, encompassing all pixels */
X for (b=box, i=0; i<CUBSIZ; i++)
X { b->color = 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<CUBSIZ; i++)
X { if (box[i].cnt > 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<used; i++)
X { cmap[i].rd = GETR8 (box[i].color);
X cmap[i].gr = GETG8 (box[i].color);
X cmap[i].bl = GETB8 (box[i].color);
X }
X
X /* Set the rest to WHITE */
X for (; i<colors; i++)
X { cmap[i].rd = 255;
X cmap[i].gr = 255;
X cmap[i].bl = 255;
X }
X }
X
X else /* Build sets all colors */
X { split_box (box, used, 0, colors, cmap); }
X
X /*----------------------------------------------------------------
X * Now arrange the colors in the desired order. Sun convention is that
X * color 0 is white and color n-1 is black, so we sort by increasing
X * intensity (why not?) and then swap the lightest and darkest colors
X */
X
X /* Now sort 0..n-1 according to increasing intensity */
X qsort (cmap, colors, sizeof (* cmap), cmp_int);
X
X /* Make first color lightest and last color darkest */
X SWAP (cmap[0].rd, cmap[colors-1].rd);
X SWAP (cmap[0].gr, cmap[colors-1].gr);
X SWAP (cmap[0].bl, cmap[colors-1].bl);
X
X /* Set the output indices */
X for (i=0; i<colors; i++) { cmap[i].indx = i; }
X}
X
X/****************************************************************
X * split_box: Basic recursive part of Heckberts adaptive partitioning
X * algorithm.
X ****************************************************************/
X
Xsplit_box (box, boxlen, clr, numclr, cmap)
XPIXEL *box;
Xint boxlen, clr, numclr;
XCOLOR *cmap;
X{ int maxv[3], minv[3], numv[3];
X int pcnt[3][CUBSID];
X int sbox, snum, split, half, maxdif, dif;
X register PIXEL *top, *bot;
X int topw, botw;
X int red, grn, blu;
X register int i, c;
X
X /* If numclr exceeds boxlen, we are in trouble */
X if (numclr > 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<CUBSID; i++) { pcnt[RD][i] = pcnt[GR][i] = pcnt[BL][i] = 0; }
X
X for (i=0; i<boxlen; i++)
X { c = box[i].color;
X red = GETR(c); grn = GETG(c); blu = GETB(c);
X
X if (red < minv[RD]) minv[RD] = red;
X if (red > 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<boxlen; i++)
X { split_box (box+i, 1, clr+i, 1, cmap); }
X return;
X }
X
X /* Pick a dimension to split */
X split = -1; maxdif = -1;
X
X if ((dif = (maxv[RD] - minv[RD])) > 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; i<c; i++) { top++; topw += top->cnt; }
X for (i=0; i<c; i++) { bot--; botw += bot->cnt; }
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<depth; i++) fprintf (stderr, " ");
X
X fprintf (stderr, "box [%d..%d|%d] r(%d,%d,%d) g(%d,%d,%d) b(%d,%d,%d) =>",
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; i<boxlen; i++)
X { sum += box[i].cnt; }
X
X return (sum);
X}
X
X/****************************************************************
X * box_avg_red: Determine the average red value [0..255] of a box
X ****************************************************************/
X
Xbox_avg_red (box, boxlen)
Xregister PIXEL *box;
Xregister int boxlen;
X{ register int sum = 0, n = 0, i;
X
X for (i=0; i<boxlen; i++)
X { sum += GETR8(box[i].color); n++; }
X
X return (sum / n);
X}
X
X/****************************************************************
X * box_avg_grn: Determine the average grn value [0..255] of a box
X ****************************************************************/
X
Xbox_avg_grn (box, boxlen)
Xregister PIXEL *box;
Xregister int boxlen;
X{ register int sum = 0, n = 0, i;
X
X for (i=0; i<boxlen; i++)
X { sum += GETG8(box[i].color); n++; }
X
X return (sum / n);
X}
X
X/****************************************************************
X * box_avg_blu: Determine the average blu value [0..255] of a box
X ****************************************************************/
X
Xbox_avg_blu (box, boxlen)
Xregister PIXEL *box;
Xregister int boxlen;
X{ register int sum = 0, n = 0, i;
X
X for (i=0; i<boxlen; i++)
X { sum += GETB8(box[i].color); n++; }
X
X return (sum / n);
X}
X
X
X/****************************************************************
X * sort by increasing red ( then green and blue )
X ****************************************************************/
X
Xcmp_red (a, b)
XPIXEL *a, *b;
X{ register 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 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; i<colors; i++)
X { output->cm[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; j<height; j++)
X { rp = &(input->bm[j*rowlen]);
X gp = rp+plnlen;
X bp = gp+plnlen;
X obm = &(output->bm[j*rowlen]);
X
X for (i=0; i<width; i++)
X { rd = *rp++; gr = *gp++; bl = *bp++;
X
X obm[i] = cmap[nearest (rd, gr, bl, cmap, colors)].indx;
X }
X }
X
X return;
X }
X
X /*------ Just use the nearest color around the left, right, and top ------*/
X
X /* Top border */
X rp = input->bm; gp = rp+plnlen; bp = gp+plnlen;
X obm = output->bm;
X for (i=0; i<width; i++)
X { obm[i] = cmap[nearest (rp[i], gp[i], bp[i], cmap, colors)].indx; }
X
X /* Left border */
X rp = input->bm; gp = rp+plnlen; bp = gp+plnlen;
X obm = output->bm;
X for (j=0; j<height; j++)
X { obm[j*rowlen] = cmap[nearest (rp[j*rowlen], gp[j*rowlen],
X bp[j*rowlen], cmap, colors)].indx; }
X
X /* Right border */
X rp = &(input->bm[width-1]); gp = rp + plnlen; bp = gp + plnlen;
X obm = &(output->bm[width-1]);
X for (j=0; j<height; j++)
X { obm[j*rowlen] = cmap[nearest (rp[j*rowlen], gp[j*rowlen],
X bp[j*rowlen], cmap, colors)].indx; }
X
X /*-------- Clear error vectors --------*/
X for (i=0; i<width; i++)
X { cerr[RD][i] = cerr[GR][i] = cerr[BL][i] = 0;
X lerr[RD][i] = lerr[GR][i] = lerr[BL][i] = 0;
X }
X
X /*-------- Major loop for Floyd-Steinberg --------*/
X for (j=1; j<height; j++)
X { rp = &(input->bm[j*rowlen+1]);
X gp = rp+plnlen;
X bp = gp+plnlen;
X obm = &(output->bm[j*rowlen+1]);
X
X for (i=1; i<width-1; i++)
X { rd = *rp++; gr = *gp++; bl = *bp++;
X
X /* Sum up errors using Floyd-Steinberg weights */
X rderr= cerr[RD][i-1] + 7*lerr[RD][i-1] + 5*lerr[RD][i] + 3*lerr[RD][i+1];
X grerr= cerr[GR][i-1] + 7*lerr[GR][i-1] + 5*lerr[GR][i] + 3*lerr[GR][i+1];
X blerr= cerr[BL][i-1] + 7*lerr[BL][i-1] + 5*lerr[BL][i] + 3*lerr[BL][i+1];
X
X rderr >>= 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<CUBSIZ; i++) { cache[i] = -1; }
X
X /* Sort the colormap by decreasing red, then green, then blue */
X qsort (cmap, colors, sizeof (COLOR), cmp_cmap);
X
X if (debug || showcolor)
X { fprintf (stderr, "\nFinal colormap:\n\n");
X for (i=0; i<colors; i++)
X { fprintf (stderr, "%3d: <%3d,%3d,%3d> [%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; a<b; )
X { c = a + (b-a)/2; /* Find midpoint */
X
X if (debug && verbose)
X { fprintf (stderr, "Searching for %d, a=%d (%d), b=%d (%d), c=%d (%d)\n",
X rd, a-cmap, a->rd, 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
--
Please send comp.sources.unix-related mail to rsalz@uunet.uu.net.