gd_topal.c

下载来的一个看图软件的源代码

  /* The original version hand-rolled the array lookup a little, but
     with four dimensions, I don't even want to think about it. TBB */
  if (c2max > c2min)
    for (c2 = c2min; c2 <= c2max; c2++)
      for (c0 = c0min; c0 <= c0max; c0++)
	for (c1 = c1min; c1 <= c1max; c1++)
	  for (c3 = c3min; c3 <= c3max; c3++)
	    if (histogram[c0][c1][c2][c3] != 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++)
	for (c1 = c1min; c1 <= c1max; c1++)
	  for (c3 = c3min; c3 <= c3max; c3++)
	    if (histogram[c0][c1][c2][c3] != 0)
	      {
		boxp->c2max = c2max = c2;
		goto have_c2max;
	      }
have_c2max:
  if (c3max > c3min)
    for (c3 = c3min; c3 <= c3max; c3++)
      for (c0 = c0min; c0 <= c0max; c0++)
	for (c1 = c1min; c1 <= c1max; c1++)
	  for (c2 = c2min; c2 <= c2max; c2++)
	    if (histogram[c0][c1][c2][c3] != 0)
	      {
		boxp->c3min = c3min = c3;
		goto have_c3min;
	      }
have_c3min:
  if (c3max > c3min)
    for (c3 = c3max; c3 >= c3min; c3--)
      for (c0 = c0min; c0 <= c0max; c0++)
	for (c1 = c1min; c1 <= c1max; c1++)
	  for (c2 = c2min; c2 <= c2max; c2++)
	    if (histogram[c0][c1][c2][c3] != 0)
	      {
		boxp->c3max = c3max = c3;
		goto have_c3max;
	      }
have_c3max:
  /* 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 8-bit units to get consistent distances; 
   * after which, we scale according to the selected distance scale factors.
   * TBB: alpha shifts back to 7 bit units. That was accounted for in the
   * alpha scale factor. 
   */
  dist0 = ((c0max - c0min) << C0_SHIFT) * C0_SCALE;
  dist1 = ((c1max - c1min) << C1_SHIFT) * C1_SCALE;
  dist2 = ((c2max - c2min) << C2_SHIFT) * C2_SCALE;
  dist3 = ((c3max - c3min) << C3_SHIFT) * C3_SCALE;
  boxp->volume = dist0 * dist0 + dist1 * dist1 + dist2 * dist2 + dist3 * dist3;

  /* Now scan remaining volume of box and compute population */
  ccount = 0;
  for (c0 = c0min; c0 <= c0max; c0++)
    for (c1 = c1min; c1 <= c1max; c1++)
      for (c2 = c2min; c2 <= c2max; c2++)
	{
	  histp = &histogram[c0][c1][c2][c3min];
	  for (c3 = c3min; c3 <= c3max; c3++, histp++)
	    if (*histp != 0)
	      {
		ccount++;
	      }
	}
  boxp->colorcount = ccount;
}


static int
median_cut (gdImagePtr im, my_cquantize_ptr cquantize,
	    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, c3, 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->c3max = b1->c3max;
      b2->c0min = b1->c0min;
      b2->c1min = b1->c1min;
      b2->c2min = b1->c2min;
      b2->c3min = b1->c3min;
      /* 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;
      c3 = ((b1->c3max - b1->c3min) << C3_SHIFT) * C3_SCALE;
      /* We want to break any ties in favor of green, then red, then blue, 
         with alpha last. */
      cmax = c1;
      n = 1;
      if (c0 > cmax)
	{
	  cmax = c0;
	  n = 0;
	}
      if (c2 > cmax)
	{
	  cmax = c2;
	  n = 2;
	}
      if (c3 > cmax)
	{
	  n = 3;
	}
      /* 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;
	case 3:
	  lb = (b1->c3max + b1->c3min) / 2;
	  b1->c3max = lb;
	  b2->c3min = lb + 1;
	  break;
	}
      /* Update stats for boxes */
      update_box (im, cquantize, b1);
      update_box (im, cquantize, b2);
      numboxes++;
    }
  return numboxes;
}


static void
compute_color (gdImagePtr im, my_cquantize_ptr cquantize,
	       boxptr boxp, int icolor)
/* 
   Compute representative color for a box, put it in 
   palette index icolor */
{
  /* Current algorithm: mean weighted by pixels (not colors) */
  /* Note it is important to get the rounding correct! */
  hist4d histogram = cquantize->histogram;
  histptr histp;
  int c0, c1, c2, c3;
  int c0min, c0max, c1min, c1max, c2min, c2max, c3min, c3max;
  long count;
  long total = 0;
  long c0total = 0;
  long c1total = 0;
  long c2total = 0;
  long c3total = 0;

  c0min = boxp->c0min;
  c0max = boxp->c0max;
  c1min = boxp->c1min;
  c1max = boxp->c1max;
  c2min = boxp->c2min;
  c2max = boxp->c2max;
  c3min = boxp->c3min;
  c3max = boxp->c3max;

  for (c0 = c0min; c0 <= c0max; c0++)
    {
      for (c1 = c1min; c1 <= c1max; c1++)
	{
	  for (c2 = c2min; c2 <= c2max; c2++)
	    {
	      histp = &histogram[c0][c1][c2][c3min];
	      for (c3 = c3min; c3 <= c3max; c3++)
		{
		  if ((count = *histp++) != 0)
		    {
		      total += count;
		      c0total += ((c0 << C0_SHIFT) + ((1 << C0_SHIFT) >> 1)) * count;
		      c1total += ((c1 << C1_SHIFT) + ((1 << C1_SHIFT) >> 1)) * count;
		      c2total += ((c2 << C2_SHIFT) + ((1 << C2_SHIFT) >> 1)) * count;
		      c3total += ((c3 << C3_SHIFT) + ((1 << C3_SHIFT) >> 1)) * count;
		    }
		}
	    }
	}
    }
  im->red[icolor] = (int) ((c0total + (total >> 1)) / total);
  im->green[icolor] = (int) ((c1total + (total >> 1)) / total);
  im->blue[icolor] = (int) ((c2total + (total >> 1)) / total);
  im->alpha[icolor] = (int) ((c3total + (total >> 1)) / total);
  im->open[icolor] = 0;
  if (im->colorsTotal <= icolor)
    {
      im->colorsTotal = icolor + 1;
    }
}

static void
select_colors (gdImagePtr im, my_cquantize_ptr cquantize, int desired_colors)
/* Master routine for color selection */
{
  boxptr boxlist;
  int numboxes;
  int i;

  /* Allocate workspace for box list */
  boxlist = (boxptr) gdMalloc (desired_colors * sizeof (box));
  /* Initialize one box containing whole space */
  numboxes = 1;
  /* Note maxval for alpha is different */
  boxlist[0].c0min = 0;
  boxlist[0].c0max = 255 >> C0_SHIFT;
  boxlist[0].c1min = 0;
  boxlist[0].c1max = 255 >> C1_SHIFT;
  boxlist[0].c2min = 0;
  boxlist[0].c2max = 255 >> C2_SHIFT;
  boxlist[0].c3min = 0;
  boxlist[0].c3max = gdAlphaMax >> C3_SHIFT;
  /* Shrink it to actually-used volume and set its statistics */
  update_box (im, cquantize, &boxlist[0]);
  /* Perform median-cut to produce final box list */
  numboxes = median_cut (im, cquantize, boxlist, numboxes, desired_colors);
  /* Compute the representative color for each box, fill colormap */
  for (i = 0; i < numboxes; i++)
    compute_color (im, cquantize, &boxlist[i], i);
  /* TBB: if the image contains colors at both scaled ends
     of the alpha range, rescale slightly to make sure alpha 
     covers the full spectrum from 100% transparent to 100% 
     opaque. Even a faint distinct background color is 
     generally considered failure with regard to alpha. */

  im->colorsTotal = numboxes;
  gdFree (boxlist);
}


/*
 * These routines are concerned with the time-critical task of mapping input
 * colors to the nearest color in the selected colormap.
 *
 * We re-use the histogram space as an "inverse color map", essentially a
 * cache for the results of nearest-color searches.  All colors within a
 * histogram cell will be mapped to the same colormap entry, namely the one
 * closest to the cell's center.  This may not be quite the closest entry to
 * the actual input color, but it's almost as good.  A zero in the cache
 * indicates we haven't found the nearest color for that cell yet; the array
 * is cleared to zeroes before starting the mapping pass.  When we find the
 * nearest color for a cell, its colormap index plus one is recorded in the
 * cache for future use.  The pass2 scanning routines call fill_inverse_cmap
 * when they need to use an unfilled entry in the cache.
 *
 * Our method of efficiently finding nearest colors is based on the "locally
 * sorted search" idea described by Heckbert and on the incremental distance
 * calculation described by Spencer W. Thomas in chapter III.1 of Graphics
 * Gems II (James Arvo, ed.  Academic Press, 1991).  Thomas points out that
 * the distances from a given colormap entry to each cell of the histogram can
 * be computed quickly using an incremental method: the differences between
 * distances to adjacent cells themselves differ by a constant.  This allows a
 * fairly fast implementation of the "brute force" approach of computing the
 * distance from every colormap entry to every histogram cell.  Unfortunately,
 * it needs a work array to hold the best-distance-so-far for each histogram
 * cell (because the inner loop has to be over cells, not colormap entries).
 * The work array elements have to be INT32s, so the work array would need
 * 256Kb at our recommended precision.  This is not feasible in DOS machines.
 *
 * To get around these problems, we apply Thomas' method to compute the
 * nearest colors for only the cells within a small subbox of the histogram.
 * The work array need be only as big as the subbox, so the memory usage
 * problem is solved.  Furthermore, we need not fill subboxes that are never
 * referenced in pass2; many images use only part of the color gamut, so a
 * fair amount of work is saved.  An additional advantage of this
 * approach is that we can apply Heckbert's locality criterion to quickly
 * eliminate colormap entries that are far away from the subbox; typically
 * three-fourths of the colormap entries are rejected by Heckbert's criterion,
 * and we need not compute their distances to individual cells in the subbox.
 * The speed of this approach is heavily influenced by the subbox size: too
 * small means too much overhead, too big loses because Heckbert's criterion
 * can't eliminate as many colormap entries.  Empirically the best subbox
 * size seems to be about 1/512th of the histogram (1/8th in each direction).
 *
 * Thomas' article also describes a refined method which is asymptotically
 * faster than the brute-force method, but it is also far more complex and
 * cannot efficiently be applied to small subboxes.  It is therefore not
 * useful for programs intended to be portable to DOS machines.  On machines
 * with plenty of memory, filling the whole histogram in one shot with Thomas'
 * refined method might be faster than the present code --- but then again,
 * it might not be any faster, and it's certainly more complicated.
 */


/* log2(histogram cells in update box) for each axis; this can be adjusted */
#define BOX_C0_LOG  (HIST_C0_BITS-3)
#define BOX_C1_LOG  (HIST_C1_BITS-3)
#define BOX_C2_LOG  (HIST_C2_BITS-3)
#define BOX_C3_LOG  (HIST_C3_BITS-3)

#define BOX_C0_ELEMS  (1<<BOX_C0_LOG)	/* # of hist cells in update box */
#define BOX_C1_ELEMS  (1<<BOX_C1_LOG)
#define BOX_C2_ELEMS  (1<<BOX_C2_LOG)
#define BOX_C3_ELEMS  (1<<BOX_C3_LOG)

#define BOX_C0_SHIFT  (C0_SHIFT + BOX_C0_LOG)
#define BOX_C1_SHIFT  (C1_SHIFT + BOX_C1_LOG)
#define BOX_C2_SHIFT  (C2_SHIFT + BOX_C2_LOG)
#define BOX_C3_SHIFT  (C3_SHIFT + BOX_C3_LOG)


/*
 * The next three routines implement inverse colormap filling.  They could
 * all be folded into one big routine, but splitting them up this way saves
 * some stack space (the mindist[] and bestdist[] arrays need not coexist)
 * and may allow some compilers to produce better code by registerizing more
 * inner-loop variables.
 */

static int
find_nearby_colors (gdImagePtr im, my_cquantize_ptr cquantize,
		int minc0, int minc1, int minc2, int minc3, int colorlist[])
/* Locate the colormap entries close enough to an update box to be candidates
 * for the nearest entry to some cell(s) in the update box.  The update box
 * is specified by the center coordinates of its first cell.  The number of
 * candidate colormap entries is returned, and their colormap indexes are
 * placed in colorlist[].
 * This routine uses Heckbert's "locally sorted search" criterion to select
 * the colors that need further consideration.
 */
{
  int numcolors = im->colorsTotal;
  int maxc0, maxc1, maxc2, maxc3;
  int centerc0, centerc1, centerc2, centerc3;
  int i, x, ncolors;
  int minmaxdist, min_dist, max_dist, tdist;
  int mindist[MAXNUMCOLORS];	/* min distance to colormap entry i */

  /* Compute true coordinates of update box's upper corner and center.
   * Actually we compute the coordinates of the center of the upper-corner
   * histogram cell, which are the upper bounds of the volume we care about.
   * Note that since ">>" rounds down, the "center" values may be closer to
   * min than to max; hence comparisons to them must be "<=", not "<".
   */
  maxc0 = minc0 + ((1 << BOX_C0_SHIFT) - (1 << C0_SHIFT));
  centerc0 = (minc0 + maxc0) >> 1;
  maxc1 = minc1 + ((1 << BOX_C1_SHIFT) - (1 << C1_SHIFT));
  centerc1 = (minc1 + maxc1) >> 1;
  maxc2 = minc2 + ((1 << BOX_C2_SHIFT) - (1 << C2_SHIFT));
  centerc2 = (minc2 + maxc2) >> 1;
  maxc3 = minc3 + ((1 << BOX_C3_SHIFT) - (1 << C3_SHIFT));
  centerc3 = (minc3 + maxc3) >> 1;

  /* For each color in colormap, find:
   *  1. its minimum squared-distance to any point in the update box
   *     (zero if color is within update box);
   *  2. its maximum squared-distance to any point in the update box.
   * Both of these can be found by considering only the corners of the box.
   * We save the minimum distance for each color in mindist[];
   * only the smallest maximum distance is of interest.
   */
  minmaxdist = 0x7FFFFFFFL;

  for (i = 0; i < numcolors; i++)
    {
      /* We compute the squared-c0-distance term, then add in the other three. */
      x = im->red[i];
      if (x < minc0)
	{
	  tdist = (x - minc0) * C0_SCALE;
	  min_dist = tdist * tdist;
	  tdist = (x - maxc0) * C0_SCALE;
	  max_dist = tdist * tdist;
	}
      else if (x > maxc0)
	{
	  tdist = (x - maxc0) * C0_SCALE;
	  min_dist = tdist * tdist;
	  tdist = (x - minc0) * C0_SCALE;
	  max_dist = tdist * tdist;
	}
      else
	{
	  /* within cell range so no contribution to min_dist */
	  min_dist = 0;