/* * jquant2.c * * Copyright (C) 1991-1996, Thomas G. Lane. * This file is part of the Independent JPEG Group's software. * For conditions of distribution and use, see the accompanying README file. * * This file contains 2-pass color quantization (color mapping) routines. * These routines provide selection of a custom color map for an image, * followed by mapping of the image to that color map, with optional * Floyd-Steinberg dithering. * It is also possible to use just the second pass to map to an arbitrary * externally-given color map. * * Note: ordered dithering is not supported, since there isn't any fast * way to compute intercolor distances; it's unclear that ordered dither's * fundamental assumptions even hold with an irregularly spaced color map. */ #define JPEG_INTERNALS#include "jinclude.h"#include "jpeglib.h" #ifdef QUANT_2PASS_SUPPORTED  /* * This module implements the well-known Heckbert paradigm for color * quantization.  Most of the ideas used here can be traced back to * Heckbert's seminal paper *   Heckbert, Paul.  "Color Image Quantization for Frame Buffer Display", *   Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304. * * In the first pass over the image, we accumulate a histogram showing the * usage count of each possible color.  To keep the histogram to a reasonable * size, we reduce the precision of the input; typical practice is to retain * 5 or 6 bits per color, so that 8 or 4 different input values are counted * in the same histogram cell. * * Next, the color-selection step begins with a box representing the whole * color space, and repeatedly splits the "largest" remaining box until we * have as many boxes as desired colors.  Then the mean color in each * remaining box becomes one of the possible output colors. *  * The second pass over the image maps each input pixel to the closest output * color (optionally after applying a Floyd-Steinberg dithering correction). * This mapping is logically trivial, but making it go fast enough requires * considerable care. * * Heckbert-style quantizers vary a good deal in their policies for choosing * the "largest" box and deciding where to cut it.  The particular policies * used here have proved out well in experimental comparisons, but better ones * may yet be found. * * In earlier versions of the IJG code, this module quantized in YCbCr color * space, processing the raw upsampled data without a color conversion step. * This allowed the color conversion math to be done only once per colormap * entry, not once per pixel.  However, that optimization precluded other * useful optimizations (such as merging color conversion with upsampling) * and it also interfered with desired capabilities such as quantizing to an * externally-supplied colormap.  We have therefore abandoned that approach. * The present code works in the post-conversion color space, typically RGB. * * To improve the visual quality of the results, we actually work in scaled * RGB space, giving G distances more weight than R, and R in turn more than * B.  To do everything in integer math, we must use integer scale factors. * The 2/3/1 scale factors used here correspond loosely to the relative * weights of the colors in the NTSC grayscale equation. * If you want to use this code to quantize a non-RGB color space, you'll * probably need to change these scale factors. */ #define R_SCALE 2		/* scale R distances by this much */#define G_SCALE 3		/* scale G distances by this much */#define B_SCALE 1		/* and B by this much */ /* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined * in jmorecfg.h.  As the code stands, it will do the right thing for R,G,B * and B,G,R orders.  If you define some other weird order in jmorecfg.h, * you'll get compile errors until you extend this logic.  In that case * you'll probably want to tweak the histogram sizes too. */ #if RGB_RED == 0#define C0_SCALE R_SCALE#endif#if RGB_BLUE == 0#define C0_SCALE B_SCALE#endif#if RGB_GREEN == 1#define C1_SCALE G_SCALE#endif#if RGB_RED == 2#define C2_SCALE R_SCALE#endif#if RGB_BLUE == 2#define C2_SCALE B_SCALE#endif  /* * First we have the histogram data structure and routines for creating it. * * The number of bits of precision can be adjusted by changing these symbols. * We recommend keeping 6 bits for G and 5 each for R and B. * If you have plenty of memory and cycles, 6 bits all around gives marginally * better results; if you are short of memory, 5 bits all around will save * some space but degrade the results. * To maintain a fully accurate histogram, we'd need to allocate a "long" * (preferably unsigned long) for each cell.  In practice this is overkill; * we can get by with 16 bits per cell.  Few of the cell counts will overflow, * and clamping those that do overflow to the maximum value will give close- * enough results.  This reduces the recommended histogram size from 256Kb * to 128Kb, which is a useful savings on PC-class machines. * (In the second pass the histogram space is re-used for pixel mapping data; * in that capacity, each cell must be able to store zero to the number of * desired colors.  16 bits/cell is plenty for that too.) * Since the JPEG code is intended to run in small memory model on 80x86 * machines, we can't just allocate the histogram in one chunk.  Instead * of a true 3-D array, we use a row of pointers to 2-D arrays.  Each * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries.  Note that * on 80x86 machines, the pointer row is in near memory but the actual * arrays are in far memory (same arrangement as we use for image arrays). */ #define MAXNUMCOLORS  (MAXJSAMPLE+1) /* maximum size of colormap */ /* These will do the right thing for either R,G,B or B,G,R color order, * but you may not like the results for other color orders. */#define HIST_C0_BITS  5		/* bits of precision in R/B histogram */#define HIST_C1_BITS  6		/* bits of precision in G histogram */#define HIST_C2_BITS  5		/* bits of precision in B/R histogram */ /* Number of elements along histogram axes. */#define HIST_C0_ELEMS  (1<<HIST_C0_BITS)#define HIST_C1_ELEMS  (1<<HIST_C1_BITS)#define HIST_C2_ELEMS  (1<<HIST_C2_BITS) /* These are the amounts to shift an input value to get a histogram index. */#define C0_SHIFT  (BITS_IN_JSAMPLE-HIST_C0_BITS)#define C1_SHIFT  (BITS_IN_JSAMPLE-HIST_C1_BITS)#define C2_SHIFT  (BITS_IN_JSAMPLE-HIST_C2_BITS)  typedef UINT16 histcell;	/* histogram cell; prefer an unsigned type */ typedef histcell FAR * histptr;	/* for pointers to histogram cells */ typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */typedef hist1d FAR * hist2d;	/* type for the 2nd-level pointers */typedef hist2d * hist3d;	/* type for top-level pointer */  /* Declarations for Floyd-Steinberg dithering. * * Errors are accumulated into the array fserrors[], at a resolution of * 1/16th of a pixel count.  The error at a given pixel is propagated * to its not-yet-processed neighbors using the standard F-S fractions, *		...	(here)	7/16 *		3/16	5/16	1/16 * We work left-to-right on even rows, right-to-left on odd rows. * * We can get away with a single array (holding one row's worth of errors) * by using it to store the current row's errors at pixel columns not yet * processed, but the next row's errors at columns already processed.  We * need only a few extra variables to hold the errors immediately around the * current column.  (If we are lucky, those variables are in registers, but * even if not, they're probably cheaper to access than array elements are.) * * The fserrors[] array has (#columns + 2) entries; the extra entry at * each end saves us from special-casing the first and last pixels. * Each entry is three values long, one value for each color component. * * Note: on a wide image, we might not have enough room in a PC's near data * segment to hold the error array; so it is allocated with alloc_large. */ #if BITS_IN_JSAMPLE == 8typedef INT16 FSERROR;		/* 16 bits should be enough */typedef int LOCFSERROR;		/* use 'int' for calculation temps */#elsetypedef INT32 FSERROR;		/* may need more than 16 bits */typedef INT32 LOCFSERROR;	/* be sure calculation temps are big enough */#endif typedef FSERROR FAR *FSERRPTR;	/* pointer to error array (in FAR storage!) */  /* Private subobject */ typedef struct {  struct jpeg_color_quantizer pub; /* public fields */   /* Space for the eventually created colormap is stashed here */  JSAMPARRAY sv_colormap;	/* colormap allocated at init time */  int desired;			/* desired # of colors = size of colormap */   /* Variables for accumulating image statistics */  hist3d histogram;		/* pointer to the histogram */   boolean needs_zeroed;		/* TRUE if next pass must zero histogram */   /* Variables for Floyd-Steinberg dithering */  FSERRPTR fserrors;		/* accumulated errors */  boolean on_odd_row;		/* flag to remember which row we are on */  int * error_limiter;		/* table for clamping the applied error */} my_cquantizer; typedef my_cquantizer * my_cquantize_ptr;  /* * Prescan some rows of pixels. * In this module the prescan simply updates the histogram, which has been * initialized to zeroes by start_pass. * An output_buf parameter is required by the method signature, but no data * is actually output (in fact the buffer controller is probably passing a * NULL pointer). */ METHODDEF(void)prescan_quantize (j_decompress_ptr cinfo, JSAMPARRAY input_buf,		  JSAMPARRAY output_buf, int num_rows){  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;  register JSAMPROW ptr;  register histptr histp;  register hist3d histogram = cquantize->histogram;  int row;  JDIMENSION col;  JDIMENSION width = cinfo->output_width;   for (row = 0; row < num_rows; row++) {    ptr = input_buf[row];    for (col = width; col > 0; col--) {      /* get pixel value and index into the histogram */      histp = & histogram[GETJSAMPLE(ptr[0]) >> C0_SHIFT]			 [GETJSAMPLE(ptr[1]) >> C1_SHIFT]			 [GETJSAMPLE(ptr[2]) >> C2_SHIFT];      /* increment, check for overflow and undo increment if so. */      if (++(*histp) <= 0)	(*histp)--;      ptr += 3;    }  }}  /* * Next we have the really interesting routines: selection of a colormap * given the completed histogram. * These routines work with a list of "boxes", each representing a rectangular * subset of the input color space (to histogram precision). */ typedef struct {  /* The bounds of the box (inclusive); expressed as histogram indexes */  int c0min, c0max;  int c1min, c1max;  int c2min, c2max;  /* The volume (actually 2-norm) of the box */  INT32 volume;  /* The number of nonzero histogram cells within this box */  long colorcount;} box; typedef box * boxptr;  LOCAL(boxptr)find_biggest_color_pop (boxptr boxlist, int numboxes)/* Find the splittable box with the largest color population *//* Returns NULL if no splittable boxes remain */{  register boxptr boxp;  register int i;  register long maxc = 0;  boxptr which = NULL;    for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {    if (boxp->colorcount > maxc && boxp->volume > 0) {      which = boxp;      maxc = boxp->colorcount;    }  }  return which;}  LOCAL(boxptr)find_biggest_volume (boxptr boxlist, int numboxes)/* Find the splittable box with the largest (scaled) volume *//* Returns NULL if no splittable boxes remain */{  register boxptr boxp;  register int i;  register INT32 maxv = 0;  boxptr which = NULL;    for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {    if (boxp->volume > maxv) {      which = boxp;      maxv = boxp->volume;    }  }  return which;}  LOCAL(void)update_box (j_decompress_ptr cinfo, boxptr boxp)/* Shrink the min/max bounds of a box to enclose only nonzero elements, *//* and recompute its volume and population */{  my_cquantize_ptr cquantize = (my_cquantize_ptr) cinfo->cquantize;  hist3d histogram = cquantize->histogram;  histptr histp;  int c0,c1,c2;  int c0min,c0max,c1min,c1max,c2min,c2max;  INT32 dist0,dist1,dist2;  long ccount;    c0min = boxp->c0min;  c0max = boxp->c0max;  c1min = boxp->c1min;  c1max = boxp->c1max;  c2min = boxp->c2min;  c2max = boxp->c2max;    if (c0max > c0min)    for (c0 = c0min; c0 <= c0max; c0++)      for (c1 = c1min; c1 <= c1max; c1++) {	histp = & histogram[c0][c1][c2min];	for (c2 = c2min; c2 <= c2max; c2++)	  if (*histp++ != 0) {	    boxp->c0min = c0min = c0;	    goto have_c0min;	  }      } have_c0min:  if (c0max > c0min)    for (c0 = c0max; c0 >= c0min; c0--)      for (c1 = c1min; c1 <= c1max; c1++) {	histp = & histogram[c0][c1][c2min];	for (c2 = c2min; c2 <= c2max; c2++)	  if (*histp++ != 0) {	    boxp->c0max = c0max = c0;	    goto have_c0max;	  }      } have_c0max:  if (c1max > c1min)    for (c1 = c1min; c1 <= c1max; c1++)      for (c0 = c0min; c0 <= c0max; c0++) {	histp = & histogram[c0][c1][c2min];	for (c2 = c2min; c2 <= c2max; c2++)	  if (*histp++ != 0) {	    boxp->c1min = c1min = c1;	    goto have_c1min;	  }      } have_c1min:  if (c1max > c1min)    for (c1 = c1max; c1 >= c1min; c1--)      for (c0 = c0min; c0 <= c0max; c0++) {	histp = & histogram[c0][c1][c2min];	for (c2 = c2min; c2 <= c2max; c2++)	  if (*histp++ != 0) {	    boxp->c1max = c1max = c1;	    goto have_c1max;	  }      } have_c1max:  if (c2max > c2min)    for (c2 = c2min; c2 <= c2max; c2++)      for (c0 = c0min; c0 <= c0max; c0++) {	histp = & histogram[c0][c1min][c2];	for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)	  if (*histp != 0) {	    boxp->c2min = c2min = c2;	    goto have_c2min;	  }      } have_c2min:  if (c2max > c2min)    for (c2 = c2max; c2 >= c2min; c2--)      for (c0 = c0min; c0 <= c0max; c0++) {	histp = & histogram[c0][c1min][c2];	for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_C2_ELEMS)	  if (*histp != 0) {	    boxp->c2max = c2max = c2;	    goto have_c2max;	  }      } have_c2max:   /* Update box volume.   * We use 2-norm rather than real volume here; this biases the method   * against making long narrow boxes, and it has the side benefit that   * a box is splittable iff norm > 0.   * Since the differences are expressed in histogram-cell units,   * we have to shift back to JSAMPLE units to get consistent distances;   * after which, we scale according to the selected distance scale factors.   */  dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE;  dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE;  dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE;  boxp->volume = dist0*dist0 + dist1*dist1 + dist2*dist2;    /* Now scan remaining volume of box and compute population */  ccount = 0;  for (c0 = c0min; c0 <= c0max; c0++)    for (c1 = c1min; c1 <= c1max; c1++) {      histp = & histogram[c0][c1][c2min];      for (c2 = c2min; c2 <= c2max; c2++, histp++)	if (*histp != 0) {	  ccount++;	}    }  boxp->colorcount = ccount;}  LOCAL(int)median_cut (j_decompress_ptr cinfo, boxptr boxlist, int numboxes,	    int desired_colors)/* Repeatedly select and split the largest box until we have enough boxes */{  int n,lb;  int c0,c1,c2,cmax;  register boxptr b1,b2;   while (numboxes < desired_colors) {    /* Select box to split.     * Current algorithm: by population for first half, then by volume.     */    if (numboxes*2 <= desired_colors) {      b1 = find_biggest_color_pop(boxlist, numboxes);    } else {      b1 = find_biggest_volume(boxlist, numboxes);    }    if (b1 == NULL)		/* no splittable boxes left! */      break;    b2 = &boxlist[numboxes];	/* where new box will go */    /* Copy the color bounds to the new box. */    b2->c0max = b1->c0max; b2->c1max = b1->c1max; b2->c2max = b1->c2max;    b2->c0min = b1->c0min; b2->c1min = b1->c1min; b2->c2min = b1->c2min;    /* Choose which axis to split the box on.     * Current algorithm: longest scaled axis.     * See notes in update_box about scaling distances.     */    c0 = ((b1->c0max - b1->c0min) << C0_SHIFT) * C0_SCALE;    c1 = ((b1->c1max - b1->c1min) << C1_SHIFT) * C1_SCALE;    c2 = ((b1->c2max - b1->c2min) << C2_SHIFT) * C2_SCALE;    /* We want to break any ties in favor of green, then red, blue last.     * This code does the right thing for R,G,B or B,G,R color orders only.     */#if RGB_RED == 0    cmax = c1; n = 1;    if (c0 > cmax) { cmax = c0; n = 0; }    if (c2 > cmax) { n = 2; }#else    cmax = c1; n = 1;    if (c2 > cmax) { cmax = c2; n = 2; }    if (c0 > cmax) { n = 0; }#endif    /* Choose split point along selected axis, and update box bounds.     * Current algorithm: split at halfway point.     * (Since the box has been shrunk to minimum volume,     * any split will produce two nonempty subboxes.)     * Note that lb value is max for lower box, so must be < old max.     */    switch (n) {    case 0:      lb = (b1->c0max + b1->c0min) / 2;      b1->c0max = lb;      b2->c0min = lb+1;      break;    case 1:      lb = (b1->c1max + b1->c1min) / 2;      b1->c1max = lb;      b2->c1min = lb+1;      break;    case 2:      lb = (b1->c2max + b1->c2min) / 2;      b1->c2max = lb;      b2->c2min = lb+1;      break;    }    /* Update stats for boxes */    update_box(cinfo, b1);    update_box(cinfo, b2);    numboxes++;  }  return numboxes;}  LOCAL(void)compute_color (j_decompress_ptr cinfo, boxptr boxp, int icolor)/* Compute representative color for a box, put it in colormap[icolor] */

Lines 1–500 of 1310. Load more