jquant2.c

EVM板JPEG实现,Texas Instruments TMS320C54x EVM JPEG

/*
 * jquant2.c
 *
 * Copyright (C) 1991, 1992, 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 are invoked via the methods color_quant_prescan,
 * color_quant_doit, and color_quant_init/term.
 */

#include "jinclude.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.
 *
 * The most significant difference between this quantizer and others is that
 * this one is intended to operate in YCbCr colorspace, rather than RGB space
 * as is usually done.  Actually we work in scaled YCbCr colorspace, where
 * Y distances are inflated by a factor of 2 relative to Cb or Cr distances.
 * The empirical evidence is that distances in this space correspond to
 * perceptual color differences more closely than do distances in RGB space;
 * and working in this space is inexpensive within a JPEG decompressor, since
 * the input data is already in YCbCr form.  (We could transform to an even
 * more perceptually linear space such as Lab or Luv, but that is very slow
 * and doesn't yield much better results than scaled YCbCr.)
 */

#define Y_SCALE 2		/* scale Y distances up by this much */

#define MAXNUMCOLORS  (MAXJSAMPLE+1) /* maximum size of colormap */


/*
 * First we have the histogram data structure and routines for creating it.
 *
 * For work in YCbCr space, it is useful to keep more precision for Y than
 * for Cb or Cr.  We recommend keeping 6 bits for Y and 5 bits each for Cb/Cr.
 * 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 Y value (typically 2^6 = 64 pointers) and
 * each 2-D array has 2^5^2 = 1024 or 2^6^2 = 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).
 */

#ifndef HIST_Y_BITS		/* so you can override from Makefile */
#define HIST_Y_BITS  6		/* bits of precision in Y histogram */
#endif
#ifndef HIST_C_BITS		/* so you can override from Makefile */
#define HIST_C_BITS  5		/* bits of precision in Cb/Cr histogram */
#endif

#define HIST_Y_ELEMS  (1<<HIST_Y_BITS) /* # of elements along histogram axes */
#define HIST_C_ELEMS  (1<<HIST_C_BITS)

/* These are the amounts to shift an input value to get a histogram index.
 * For a combination 8/12 bit implementation, would need variables here...
 */

#define Y_SHIFT  (BITS_IN_JSAMPLE-HIST_Y_BITS)
#define C_SHIFT  (BITS_IN_JSAMPLE-HIST_C_BITS)


typedef UINT16 histcell;	/* histogram cell; MUST be an unsigned type */

typedef histcell FAR * histptr;	/* for pointers to histogram cells */

typedef histcell hist1d[HIST_C_ELEMS]; /* typedefs for the array */
typedef hist1d FAR * hist2d;	/* type for the Y-level pointers */
typedef hist2d * hist3d;	/* type for top-level pointer */

static hist3d histogram;	/* pointer to the histogram */


/*
 * Prescan some rows of pixels.
 * In this module the prescan simply updates the histogram, which has been
 * initialized to zeroes by color_quant_init.
 * Note: workspace is probably not useful for this routine, but it is passed
 * anyway to allow some code sharing within the pipeline controller.
 */

METHODDEF void
color_quant_prescan (decompress_info_ptr cinfo, int num_rows,
		     JSAMPIMAGE image_data, JSAMPARRAY workspace)
{
  register JSAMPROW ptr0, ptr1, ptr2;
  register histptr histp;
  register int c0, c1, c2;
  int row;
  long col;
  long width = cinfo->image_width;

  for (row = 0; row < num_rows; row++) {
    ptr0 = image_data[0][row];
    ptr1 = image_data[1][row];
    ptr2 = image_data[2][row];
    for (col = width; col > 0; col--) {
      /* get pixel value and index into the histogram */
      c0 = GETJSAMPLE(*ptr0++) >> Y_SHIFT;
      c1 = GETJSAMPLE(*ptr1++) >> C_SHIFT;
      c2 = GETJSAMPLE(*ptr2++) >> C_SHIFT;
      histp = & histogram[c0][c1][c2];
      /* increment, check for overflow and undo increment if so. */
      /* We assume unsigned representation here! */
      if (++(*histp) == 0)
	(*histp)--;
    }
  }
}


/*
 * Now 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 number of nonzero histogram cells within this box */
	long colorcount;
      } box;
typedef box * boxptr;

static boxptr boxlist;		/* array with room for desired # of boxes */
static int numboxes;		/* number of boxes currently in boxlist */

static JSAMPARRAY my_colormap;	/* the finished colormap (in YCbCr space) */


LOCAL boxptr
find_biggest_color_pop (void)
/* Find the splittable box with the largest color population */
/* Returns NULL if no splittable boxes remain */
{
  register boxptr boxp;
  register int i;
  register long max = 0;
  boxptr which = NULL;
  
  for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
    if (boxp->colorcount > max) {
      if (boxp->c0max > boxp->c0min || boxp->c1max > boxp->c1min ||
	  boxp->c2max > boxp->c2min) {
	which = boxp;
	max = boxp->colorcount;
      }
    }
  }
  return which;
}


LOCAL boxptr
find_biggest_volume (void)
/* Find the splittable box with the largest (scaled) volume */
/* Returns NULL if no splittable boxes remain */
{
  register boxptr boxp;
  register int i;
  register INT32 max = 0;
  register INT32 norm, c0,c1,c2;
  boxptr which = NULL;
  
  /* We use 2-norm rather than real volume here.
   * Some care is needed since the differences are expressed in
   * histogram-cell units; if HIST_Y_BITS != HIST_C_BITS, we have to
   * adjust the scaling to get the proper scaled-YCbCr-space distance.
   * This code won't work right if HIST_Y_BITS < HIST_C_BITS,
   * but that shouldn't ever be true.
   * Note norm > 0 iff box is splittable, so need not check separately.
   */
  
  for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
    c0 = (boxp->c0max - boxp->c0min) * Y_SCALE;
    c1 = (boxp->c1max - boxp->c1min) << (HIST_Y_BITS-HIST_C_BITS);
    c2 = (boxp->c2max - boxp->c2min) << (HIST_Y_BITS-HIST_C_BITS);
    norm = c0*c0 + c1*c1 + c2*c2;
    if (norm > max) {
      which = boxp;
      max = norm;
    }
  }
  return which;
}


LOCAL void
update_box (boxptr boxp)
/* Shrink the min/max bounds of a box to enclose only nonzero elements, */
/* and recompute its population */
{
  histptr histp;
  int c0,c1,c2;
  int c0min,c0max,c1min,c1max,c2min,c2max;
  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_C_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_C_ELEMS)
	  if (*histp != 0) {
	    boxp->c2max = c2max = c2;
	    goto have_c2max;
	  }
      }
 have_c2max:
  
  /* 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 void
median_cut (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();
    } else {
      b1 = find_biggest_volume();
    }
    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 find_biggest_volume about scaling...
     */
    c0 = (b1->c0max - b1->c0min) * Y_SCALE;
    c1 = (b1->c1max - b1->c1min) << (HIST_Y_BITS-HIST_C_BITS);
    c2 = (b1->c2max - b1->c2min) << (HIST_Y_BITS-HIST_C_BITS);
    cmax = c0; n = 0;
    if (c1 > cmax) { cmax = c1; n = 1; }
    if (c2 > cmax) { n = 2; }
    /* 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(b1);
    update_box(b2);
    numboxes++;
  }
}


LOCAL void
compute_color (boxptr boxp, int icolor)
/* Compute representative color for a box, put it in my_colormap[icolor] */
{
  /* Current algorithm: mean weighted by pixels (not colors) */