/*

% Copyright (C) 2003-2020 GraphicsMagick Group

% Copyright (C) 2002 ImageMagick Studio

% Copyright 1991-1999 E. I. du Pont de Nemours and Company

%

% This program is covered by multiple licenses, which are described in

% Copyright.txt. You should have received a copy of Copyright.txt with this

% package; otherwise see http://www.graphicsmagick.org/www/Copyright.html.

%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                                                             %

%                                                                             %

%                                                                             %

%           QQQ   U   U   AAA   N   N  TTTTT  IIIII   ZZZZZ  EEEEE            %

%          Q   Q  U   U  A   A  NN  N    T      I        ZZ  E                %

%          Q   Q  U   U  AAAAA  N N N    T      I      ZZZ   EEEEE            %

%          Q  QQ  U   U  A   A  N  NN    T      I     ZZ     E                %

%           QQQQ   UUU   A   A  N   N    T    IIIII   ZZZZZ  EEEEE            %

%                                                                             %

%                                                                             %

%         Methods to Reduce the Number of Unique Colors in an Image           %

%                                                                             %

%                                                                             %

%                           Software Design                                   %

%                             John Cristy                                     %

%                              July 1992                                      %

%                                                                             %

%                                                                             %

%                                                                             %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

%  Realism in computer graphics typically requires using 24 bits/pixel to

%  generate an image.  Yet many graphic display devices do not contain the

%  amount of memory necessary to match the spatial and color resolution of

%  the human eye.  The Quantize methods takes a 24 bit image and reduces

%  the number of colors so it can be displayed on raster device with less

%  bits per pixel.  In most instances, the quantized image closely

%  resembles the original reference image.

%

%  A reduction of colors in an image is also desirable for image

%  transmission and real-time animation.

%

%  QuantizeImage() takes a standard RGB or monochrome images and quantizes

%  them down to some fixed number of colors.

%

%  For purposes of color allocation, an image is a set of n pixels, where

%  each pixel is a point in RGB space.  RGB space is a 3-dimensional

%  vector space, and each pixel, Pi,  is defined by an ordered triple of

%  red, green, and blue coordinates, (Ri, Gi, Bi).

%

%  Each primary color component (red, green, or blue) represents an

%  intensity which varies linearly from 0 to a maximum value, Cmax, which

%  corresponds to full saturation of that color.  Color allocation is

%  defined over a domain consisting of the cube in RGB space with opposite

%  vertices at (0,0,0) and (Cmax, Cmax, Cmax).  QUANTIZE requires Cmax =

%  255.

%

%  The algorithm maps this domain onto a tree in which each node

%  represents a cube within that domain.  In the following discussion

%  these cubes are defined by the coordinate of two opposite vertices:

%  The vertex nearest the origin in RGB space and the vertex farthest from

%  the origin.

%

%  The tree's root node represents the the entire domain, (0,0,0) through

%  (Cmax,Cmax,Cmax).  Each lower level in the tree is generated by

%  subdividing one node's cube into eight smaller cubes of equal size.

%  This corresponds to bisecting the parent cube with planes passing

%  through the midpoints of each edge.

%

%  The basic algorithm operates in three phases: Classification,

%  Reduction, and Assignment.  Classification builds a color description

%  tree for the image.  Reduction collapses the tree until the number it

%  represents, at most, the number of colors desired in the output image.

%  Assignment defines the output image's color map and sets each pixel's

%  color by restorage_class in the reduced tree.  Our goal is to minimize

%  the numerical discrepancies between the original colors and quantized

%  colors (quantization error).

%

%  Classification begins by initializing a color description tree of

%  sufficient depth to represent each possible input color in a leaf.

%  However, it is impractical to generate a fully-formed color description

%  tree in the storage_class phase for realistic values of Cmax.  If

%  colors components in the input image are quantized to k-bit precision,

%  so that Cmax= 2k-1, the tree would need k levels below the root node to

%  allow representing each possible input color in a leaf.  This becomes

%  prohibitive because the tree's total number of nodes is 1 +

%  sum(i=1, k, 8k).

%

%  A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.

%  Therefore, to avoid building a fully populated tree, QUANTIZE: (1)

%  Initializes data structures for nodes only as they are needed;  (2)

%  Chooses a maximum depth for the tree as a function of the desired

%  number of colors in the output image (currently log2(colormap size)).

%

%  For each pixel in the input image, storage_class scans downward from

%  the root of the color description tree.  At each level of the tree it

%  identifies the single node which represents a cube in RGB space

%  containing the pixel's color.  It updates the following data for each

%  such node:

%

%    n1: Number of pixels whose color is contained in the RGB cube which

%    this node represents;

%

%    n2: Number of pixels whose color is not represented in a node at

%    lower depth in the tree;  initially,  n2 = 0 for all nodes except

%    leaves of the tree.

%

%    Sr, Sg, Sb: Sums of the red, green, and blue component values for all

%    pixels not classified at a lower depth. The combination of these sums

%    and n2  will ultimately characterize the mean color of a set of

%    pixels represented by this node.

%

%    E: The distance squared in RGB space between each pixel contained

%    within a node and the nodes' center.  This represents the

%    quantization error for a node.

%

%  Reduction repeatedly prunes the tree until the number of nodes with n2

%  > 0 is less than or equal to the maximum number of colors allowed in

%  the output image.  On any given iteration over the tree, it selects

%  those nodes whose E count is minimal for pruning and merges their color

%  statistics upward. It uses a pruning threshold, Ep, to govern node

%  selection as follows:

%

%    Ep = 0

%    while number of nodes with (n2 > 0) > required maximum number of colors

%      prune all nodes such that E <= Ep

%      Set Ep to minimum E in remaining nodes

%

%  This has the effect of minimizing any quantization error when merging

%  two nodes together.

%

%  When a node to be pruned has offspring, the pruning procedure invokes

%  itself recursively in order to prune the tree from the leaves upward.

%  n2,  Sr, Sg,  and  Sb in a node being pruned are always added to the

%  corresponding data in that node's parent.  This retains the pruned

%  node's color characteristics for later averaging.

%

%  For each node, n2 pixels exist for which that node represents the

%  smallest volume in RGB space containing those pixel's colors.  When n2

%  > 0 the node will uniquely define a color in the output image. At the

%  beginning of reduction,  n2 = 0  for all nodes except a the leaves of

%  the tree which represent colors present in the input image.

%

%  The other pixel count, n1, indicates the total number of colors within

%  the cubic volume which the node represents.  This includes n1 - n2

%  pixels whose colors should be defined by nodes at a lower level in the

%  tree.

%

%  Assignment generates the output image from the pruned tree.  The output

%  image consists of two parts: (1)  A color map, which is an array of

%  color descriptions (RGB triples) for each color present in the output

%  image;  (2)  A pixel array, which represents each pixel as an index

%  into the color map array.

%

%  First, the assignment phase makes one pass over the pruned color

%  description tree to establish the image's color map.  For each node

%  with n2  > 0, it divides Sr, Sg, and Sb by n2 .  This produces the mean

%  color of all pixels that classify no lower than this node.  Each of

%  these colors becomes an entry in the color map.

%

%  Finally,  the assignment phase reclassifies each pixel in the pruned

%  tree to identify the deepest node containing the pixel's color.  The

%  pixel's value in the pixel array becomes the index of this node's mean

%  color in the color map.

%

%  This method is based on a similar algorithm written by Paul Raveling.

%

%

*/

/*

  Include declarations.

*/

#include "magick/studio.h"

#include "magick/analyze.h"

#include "magick/color.h"

#include "magick/colormap.h"

#include "magick/enhance.h"

#include "magick/monitor.h"

#include "magick/pixel_cache.h"

#include "magick/quantize.h"

#include "magick/utility.h"

/*

  Define declarations.

*/

#define CacheShift  (QuantumDepth-6)

#define ExceptionQueueLength  16

#define MaxNodes  266817

#define MaxTreeDepth  8

#define NodesInAList  1536

#define ColorToNodeId(red,green,blue,index) ((unsigned int) \

            (((ScaleQuantumToChar(red) >> index) & 0x01) << 2 | \

             ((ScaleQuantumToChar(green) >> index) & 0x01) << 1 | \

             ((ScaleQuantumToChar(blue) >> index) & 0x01)))

/*

  Typedef declarations.

*/

#if QuantumDepth > 16 && defined(HAVE_LONG_DOUBLE_WIDER)

  typedef long double ErrorSumType;

#else

  typedef double ErrorSumType;

#endif

typedef struct _NodeInfo

{

  struct _NodeInfo

    *parent,

    *child[MaxTreeDepth];

  double

    number_unique;

  double  /* was ErrorSumType */

    total_red,

    total_green,

    total_blue;

  ErrorSumType

    quantize_error;

  unsigned long

    color_number;

  unsigned char

    id,

    level;

} NodeInfo;

typedef struct _Nodes

{

  NodeInfo

    *nodes;

  struct _Nodes

    *next;

} Nodes;

typedef struct _CubeInfo

{

  NodeInfo

    *root;

  unsigned long

    colors;

  DoublePixelPacket

    color;

  double  /* was ErrorSumType */

    distance;

  ErrorSumType

    pruning_threshold,

    next_threshold;

  unsigned long

    nodes,

    free_nodes,

    color_number;

  NodeInfo

    *next_node;

  Nodes

    *node_queue;

  long

    *cache;

  DoublePixelPacket

    error[ExceptionQueueLength];

  double

    weights[ExceptionQueueLength];

  const QuantizeInfo

    *quantize_info;

  long

    x,

    y;

  unsigned long

    depth;

} CubeInfo;

/*

  Method prototypes.

*/

static void

  ClosestColor(Image *,CubeInfo *,const NodeInfo *);

static NodeInfo

  *GetNodeInfo(CubeInfo *,const unsigned int,const unsigned int,NodeInfo *);

static unsigned int

  DitherImage(CubeInfo *,Image *);

static void

  DefineImageColormap(Image *,NodeInfo *),

  HilbertCurve(CubeInfo *,Image *,const unsigned long,const unsigned int),

  PruneLevel(CubeInfo *,const NodeInfo *),

  PruneToCubeDepth(CubeInfo *,const NodeInfo *),

  ReduceImageColors(const char *filename,CubeInfo *,const unsigned long,ExceptionInfo *);

/*

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                                                             %

%                                                                             %

%                                                                             %

+   A s s i g n I m a g e C o l o r s                                         %

%                                                                             %

%                                                                             %

%                                                                             %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

%  AssignImageColors() generates the output image from the pruned tree.  The

%  output image consists of two parts: (1)  A color map, which is an array

%  of color descriptions (RGB triples) for each color present in the

%  output image;  (2)  A pixel array, which represents each pixel as an

%  index into the color map array.

%

%  First, the assignment phase makes one pass over the pruned color

%  description tree to establish the image's color map.  For each node

%  with n2  > 0, it divides Sr, Sg, and Sb by n2 .  This produces the mean

%  color of all pixels that classify no lower than this node.  Each of

%  these colors becomes an entry in the color map.

%

%  Finally,  the assignment phase reclassifies each pixel in the pruned

%  tree to identify the deepest node containing the pixel's color.  The

%  pixel's value in the pixel array becomes the index of this node's mean

%  color in the color map.

%

%  The format of the AssignImageColors() method is:

%

%      unsigned int AssignImageColors(CubeInfo *cube_info,Image *image)

%

%  A description of each parameter follows.

%

%    o cube_info: A pointer to the Cube structure.

%

%    o image: Specifies a pointer to an Image structure;  returned from

%      ReadImage.

%

%

*/

static MagickPassFail AssignImageColors(CubeInfo *cube_info,Image *image)

{

#define AssignImageText "[%s] Assign colors..."

  unsigned int

    dither;

  unsigned int

    is_grayscale,

    is_monochrome;

  MagickPassFail

    status=MagickPass;

  /*

    Allocate image colormap.

  */

  if (!AllocateImageColormap(image,cube_info->colors))

    ThrowBinaryException3(ResourceLimitError,MemoryAllocationFailed,

                          UnableToQuantizeImage);

  image->colors=0;

  is_grayscale=image->is_grayscale;

  is_monochrome=image->is_monochrome;

  DefineImageColormap(image,cube_info->root);

  if (cube_info->quantize_info->colorspace == TransparentColorspace)

    image->storage_class=DirectClass;

  /*

    Create a reduced color image.

  */

  dither=cube_info->quantize_info->dither;

  if (dither)

    dither=DitherImage(cube_info,image);

  if (!dither)

    {

      long

        y;

      /*

        FIXME: Use OpenMP?

      */

      for (y=0; y < (long) image->rows; y++)

        {

          IndexPacket

            index;

          long

            count;

          register IndexPacket

            *indexes;

          register long

            i,

            x;

          register const NodeInfo

            *node_info;

          register PixelPacket

            *q;

          unsigned int

            id;

          q=GetImagePixels(image,0,y,image->columns,1);

          if (q == (PixelPacket *) NULL)

            {

              status=MagickFail;

              break;

            }

          indexes=AccessMutableIndexes(image);

          for (x=0; x < (long) image->columns; x+=count)

            {

              /*

                Identify the deepest node containing the pixel's color.

              */

              for (count=1; (x+count) < (long) image->columns; count++)

                if (NotColorMatch(q,q+count))

                  break;

              node_info=cube_info->root;

              for (index=MaxTreeDepth-1; (long) index > 0; index--)

                {

                  id=ColorToNodeId(q->red,q->green,q->blue,index);

                  if (node_info->child[id] == (NodeInfo *) NULL)

                    break;

                  node_info=node_info->child[id];

                }

              /*

                Find closest color among siblings and their children.

              */

              cube_info->color.red=q->red;

              cube_info->color.green=q->green;

              cube_info->color.blue=q->blue;

              cube_info->distance=3.0*(MaxRGBDouble+1.0)*(MaxRGBDouble+1.0);

              ClosestColor(image,cube_info,node_info->parent);

              index=(IndexPacket) cube_info->color_number;

              for (i=0; i < count; i++)

                {

                  if (image->storage_class == PseudoClass)

                    indexes[x+i]=index;

                  if (!cube_info->quantize_info->measure_error)

                    {

                      q->red=image->colormap[index].red;

                      q->green=image->colormap[index].green;

                      q->blue=image->colormap[index].blue;

                    }

                  q++;

                }

            }

          if (!SyncImagePixels(image))

            {

              status=MagickFail;

              break;

            }

          if (QuantumTick(y,image->rows))

            if (!MagickMonitorFormatted(y,image->rows,&image->exception,

                                        AssignImageText,image->filename))

              {

                status=MagickFail;

                break;

              }

        }

    }

  if ((cube_info->quantize_info->number_colors == 2) &&

      (IsGrayColorspace(cube_info->quantize_info->colorspace)))

    {

      PixelPacket

        *q;

      Quantum

        intensity;

      long

        i;

      /*

        Monochrome image.

      */

      is_monochrome=True;

      q=image->colormap;

      for (i=(long) image->colors; i > 0; i--)

        {

          intensity=(Quantum) (PixelIntensityToQuantum(q) <

                               (MaxRGB/2) ? 0 : MaxRGB);

          q->red=intensity;

          q->green=intensity;

          q->blue=intensity;

          q++;

        }

    }

  if (cube_info->quantize_info->measure_error)

    (void) GetImageQuantizeError(image);

  status &= SyncImage(image);

  image->is_grayscale=is_grayscale;

  image->is_monochrome=is_monochrome;

  return(status);

}

/*

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                                                             %

%                                                                             %

%                                                                             %

+   C l a s s i f y I m a g e C o l o r s                                     %

%                                                                             %

%                                                                             %

%                                                                             %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

%  ClassifyImageColors() begins by initializing a color description tree

%  of sufficient depth to represent each possible input color in a leaf.

%  However, it is impractical to generate a fully-formed color

%  description tree in the storage_class phase for realistic values of

%  Cmax.  If colors components in the input image are quantized to k-bit

%  precision, so that Cmax= 2k-1, the tree would need k levels below the

%  root node to allow representing each possible input color in a leaf.

%  This becomes prohibitive because the tree's total number of nodes is

%  1 + sum(i=1,k,8k).

%

%  A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.

%  Therefore, to avoid building a fully populated tree, QUANTIZE: (1)

%  Initializes data structures for nodes only as they are needed;  (2)

%  Chooses a maximum depth for the tree as a function of the desired

%  number of colors in the output image (currently log2(colormap size)).

%

%  For each pixel in the input image, storage_class scans downward from

%  the root of the color description tree.  At each level of the tree it

%  identifies the single node which represents a cube in RGB space

%  containing It updates the following data for each such node:

%

%    n1 : Number of pixels whose color is contained in the RGB cube

%    which this node represents;

%

%    n2 : Number of pixels whose color is not represented in a node at

%    lower depth in the tree;  initially,  n2 = 0 for all nodes except

%    leaves of the tree.

%

%    Sr, Sg, Sb : Sums of the red, green, and blue component values for

%    all pixels not classified at a lower depth. The combination of

%    these sums and n2  will ultimately characterize the mean color of a

%    set of pixels represented by this node.

%

%    E: The distance squared in RGB space between each pixel contained

%    within a node and the nodes' center.  This represents the quantization

%    error for a node.

%

%  The format of the ClassifyImageColors() method is:

%

%      unsigned int ClassifyImageColorsCubeInfo *cube_info,const Image *image,

%        ExceptionInfo *exception)

%

%  A description of each parameter follows.

%

%    o cube_info: A pointer to the Cube structure.

%

%    o image: Specifies a pointer to an Image structure;  returned from

%      ReadImage.

%

%

*/

static MagickPassFail ClassifyImageColors(CubeInfo *cube_info,const Image *image,

  ExceptionInfo *exception)

{

#define ClassifyImageText "[%s] Classify colors..."

  double

    bisect;

  DoublePixelPacket

    mid,

    pixel;

  long

    count,

    y;

  NodeInfo

    *node_info;

  register long

    x;

  register const PixelPacket

    *p;

  unsigned long

    index,

    level;

  unsigned int

    id;

  MagickPassFail

    status=MagickPass;

  /*

    Classify the first 256 colors to a tree depth of 8.

  */

  for (y=0; (y < (long) image->rows) && (cube_info->colors < 256); y++)

  {

    p=AcquireImagePixels(image,0,y,image->columns,1,exception);

    if (p == (const PixelPacket *) NULL)

      {

        status=MagickFail;

        break;

      }

    if (cube_info->nodes > MaxNodes)

      {

        /*

          Prune one level if the color tree is too large.

        */

        PruneLevel(cube_info,cube_info->root);

        cube_info->depth--;

      }

    for (x=0; x < (long) image->columns; x+=count)

    {

      /*

        Start at the root and descend the color cube tree.

      */

      for (count=1; (x+count) < (long) image->columns; count++)

        if (NotColorMatch(p,p+count))

          break;

      index=MaxTreeDepth-1;

      bisect=(MaxRGBDouble+1.0)/2.0;

      mid.red=MaxRGBDouble/2.0;

      mid.green=MaxRGBDouble/2.0;

      mid.blue=MaxRGBDouble/2.0;

      node_info=cube_info->root;

      for (level=1; level <= 8; level++)

      {

        bisect/=2;

        id=ColorToNodeId(p->red,p->green,p->blue,index);

        mid.red+=id & 4 ? bisect : -bisect;

        mid.green+=id & 2 ? bisect : -bisect;

        mid.blue+=id & 1 ? bisect : -bisect;

        if (node_info->child[id] == (NodeInfo *) NULL)

          {

            /*

              Set colors of new node to contain pixel.

            */

            node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);

            if (node_info->child[id] == (NodeInfo *) NULL)

              {

                ThrowException3(exception,ResourceLimitError,

                                MemoryAllocationFailed,UnableToQuantizeImage);

                status=MagickFail;

                break;

              }

            if (level == MaxTreeDepth)

              cube_info->colors++;

          }

        /*

          Approximate the quantization error represented by this node.

        */

        node_info=node_info->child[id];

        pixel.red=p->red-mid.red;

        pixel.green=p->green-mid.green;

        pixel.blue=p->blue-mid.blue;

        node_info->quantize_error+=count*pixel.red*pixel.red+

          count*pixel.green*pixel.green+count*pixel.blue*pixel.blue;

        cube_info->root->quantize_error+=node_info->quantize_error;

        index--;

      }

      if (status == MagickFail)

        break;

      /*

        Sum RGB for this leaf for later derivation of the mean cube color.

      */

      node_info->number_unique+=count;

      node_info->total_red+=(double) count*p->red;

      node_info->total_green+=(double) count*p->green;

      node_info->total_blue+=(double) count*p->blue;

      p+=count;

    }

    if (QuantumTick(y,image->rows))

      if (!MagickMonitorFormatted(y,image->rows,exception,

                                  ClassifyImageText,image->filename))

        {

          status=MagickFail;

          break;

        }

  }

  if ((status == MagickFail) || (y == (long) image->rows))

    return status;

  /*

    More than 256 colors;  classify to the cube_info->depth tree depth.

  */

  PruneToCubeDepth(cube_info,cube_info->root);

  for ( ; y < (long) image->rows; y++)

  {

    p=AcquireImagePixels(image,0,y,image->columns,1,exception);

    if (p == (const PixelPacket *) NULL)

      {

        status=MagickFail;

        break;

      }

    if (cube_info->nodes > MaxNodes)

      {

        /*

          Prune one level if the color tree is too large.

        */

        PruneLevel(cube_info,cube_info->root);

        cube_info->depth--;

      }

    for (x=0; x < (long) image->columns; x+=count)

    {

      /*

        Start at the root and descend the color cube tree.

      */

      for (count=1; (x+count) < (long) image->columns; count++)

        if (NotColorMatch(p,p+count))

          break;

      index=MaxTreeDepth-1;

      bisect=(MaxRGBDouble+1.0)/2.0;

      mid.red=MaxRGBDouble/2.0;

      mid.green=MaxRGBDouble/2.0;

      mid.blue=MaxRGBDouble/2.0;

      node_info=cube_info->root;

      for (level=1; level <= cube_info->depth; level++)

      {

        bisect/=2.0;

        id=ColorToNodeId(p->red,p->green,p->blue,index);

        mid.red+=id & 4 ? bisect : -bisect;

        mid.green+=id & 2 ? bisect : -bisect;

        mid.blue+=id & 1 ? bisect : -bisect;

        if (node_info->child[id] == (NodeInfo *) NULL)

          {

            /*

              Set colors of new node to contain pixel.

            */

            node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);

            if (node_info->child[id] == (NodeInfo *) NULL)

              {

                ThrowException3(exception,ResourceLimitError,

                                MemoryAllocationFailed,UnableToQuantizeImage);

                status=MagickFail;

                break;

              }

            if (level == cube_info->depth)

              cube_info->colors++;

          }

        /*

          Approximate the quantization error represented by this node.

        */

        node_info=node_info->child[id];

        pixel.red=p->red-mid.red;

        pixel.green=p->green-mid.green;

        pixel.blue=p->blue-mid.blue;

        node_info->quantize_error+=count*pixel.red*pixel.red+

          count*pixel.green*pixel.green+count*pixel.blue*pixel.blue;

        cube_info->root->quantize_error+=node_info->quantize_error;

        index--;

      }

      if (status == MagickFail)

        break;

      /*

        Sum RGB for this leaf for later derivation of the mean cube color.

      */

      node_info->number_unique+=count;

      node_info->total_red+=(double) count*p->red;

      node_info->total_green+=(double) count*p->green;

      node_info->total_blue+=(double) count*p->blue;

      p+=count;

    }

    if (QuantumTick(y,image->rows))

      if (!MagickMonitorFormatted(y,image->rows,exception,

                                  ClassifyImageText,image->filename))

        {

          status=MagickFail;

          break;

        }

  }

  return(status);

}

/*

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                                                             %

%                                                                             %

%                                                                             %

%   C l o n e Q u a n t i z e I n f o                                         %

%                                                                             %

%                                                                             %

%                                                                             %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

%  CloneQuantizeInfo() makes a duplicate of the given quantize info structure,

%  or if quantize info is NULL, a new one.

%

%  The format of the CloneQuantizeInfo method is:

%

%      QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)

%

%  A description of each parameter follows:

%

%    o clone_info: Method CloneQuantizeInfo returns a duplicate of the given

%      quantize info, or if image info is NULL a new one.

%

%    o quantize_info: a structure of type info.

%

%

*/

MagickExport QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)

{

  QuantizeInfo

    *clone_info;

  clone_info=MagickAllocateMemory(QuantizeInfo *,sizeof(QuantizeInfo));

  if (clone_info == (QuantizeInfo *) NULL)

    MagickFatalError3(ResourceLimitFatalError,MemoryAllocationFailed,

      UnableToAllocateQuantizeInfo);

  GetQuantizeInfo(clone_info);

  if (quantize_info == (QuantizeInfo *) NULL)

    return(clone_info);

  clone_info->number_colors=quantize_info->number_colors;

  clone_info->tree_depth=quantize_info->tree_depth;

  clone_info->dither=quantize_info->dither;

  clone_info->colorspace=quantize_info->colorspace;

  clone_info->measure_error=quantize_info->measure_error;

  return(clone_info);

}

/*

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                                                             %

%                                                                             %

%                                                                             %

+   C l o s e s t C o l o r                                                   %

%                                                                             %

%                                                                             %

%                                                                             %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

%  ClosestColor() traverses the color cube tree at a particular node and

%  determines which colormap entry best represents the input color.

%

%  This is a recursive function.

%

%  The format of the ClosestColor method is:

%

%      void ClosestColor(Image *image,CubeInfo *cube_info,

%        const NodeInfo *node_info)

%

%  A description of each parameter follows.

%

%    o image: The image.

%

%    o cube_info: A pointer to the Cube structure.

%

%    o node_info: The address of a structure of type NodeInfo which points to a

%      node in the color cube tree that is to be pruned.

%

%

*/

static void ClosestColor(Image *image,CubeInfo *cube_info,

  const NodeInfo *node_info)

{

  register unsigned int

    id;

  /*

    Traverse any children.

  */

  for (id=0; id < MaxTreeDepth; id++)

    if (node_info->child[id] != (NodeInfo *) NULL)

      ClosestColor(image,cube_info,node_info->child[id]);

  if (node_info->number_unique != 0)

    {

      double

        distance;

      DoublePixelPacket

        pixel;

      register PixelPacket

        *color;

      /*

        Determine if this color is "closest".

      */

      color=image->colormap+node_info->color_number;

      pixel.red=color->red-cube_info->color.red;

      distance=pixel.red*pixel.red;

      if (distance < cube_info->distance)

        {

          pixel.green=color->green-cube_info->color.green;

          distance+=pixel.green*pixel.green;

          if (distance < cube_info->distance)

            {

              pixel.blue=color->blue-cube_info->color.blue;

              distance+=pixel.blue*pixel.blue;

              if (distance < cube_info->distance)

                {

                  cube_info->distance=distance;

                  cube_info->color_number=node_info->color_number;

                }

            }

        }

    }

}

/*

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                                                             %

%                                                                             %

%                                                                             %

%   C o m p r e s s I m a g e C o l o r m a p                                 %

%                                                                             %

%                                                                             %

%                                                                             %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

%  CompressImageColormap() compresses an image colormap by removing any

%  duplicate or unused color entries.

%

%  The format of the CompressImageColormap method is:

%

%      void CompressImageColormap(Image *image)

%

%  A description of each parameter follows:

%

%    o image: The image.

%

%

*/

MagickExport void CompressImageColormap(Image *image)

{

  QuantizeInfo

    quantize_info;

  assert(image != (Image *) NULL);

  assert(image->signature == MagickSignature);

  if (!IsPaletteImage(image,&image->exception))

    return;

  GetQuantizeInfo(&quantize_info);

  quantize_info.number_colors=image->colors;

  quantize_info.tree_depth=MaxTreeDepth;

  (void) QuantizeImage(&quantize_info,image);

}

/*

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                                                             %

%                                                                             %

%                                                                             %

+   D e f i n e I m a g e C o l o r m a p                                     %

%                                                                             %

%                                                                             %

%                                                                             %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

%  DefineImageColormap() traverses the color cube tree and notes each colormap

%  entry.  A colormap entry is any node in the color cube tree where the

%  of unique colors is not zero.

%

%  The format of the DefineImageColormap method is:

%

%      DefineImageColormap(Image *image,NodeInfo *node_info)

%

%  A description of each parameter follows.

%

%    o image: The image.

%

%    o node_info: The address of a structure of type NodeInfo which points to a

%      node in the color cube tree that is to be pruned.

%

%

*/

static void DefineImageColormap(Image *image,NodeInfo *node_info)

{

  register unsigned int

    id;

  /*

    Traverse any children.

  */

  for (id=0; id < MaxTreeDepth; id++)

    if (node_info->child[id] != (NodeInfo *) NULL)

      DefineImageColormap(image,node_info->child[id]);

  if (node_info->number_unique != 0)

    {

      register double

        number_unique;

      /*

        Colormap entry is defined by the mean color in this cube.

      */

      number_unique=node_info->number_unique;

      image->colormap[image->colors].red=(Quantum)

        (node_info->total_red/number_unique+0.5);

      image->colormap[image->colors].green=(Quantum)

        (node_info->total_green/number_unique+0.5);

      image->colormap[image->colors].blue=(Quantum)

        (node_info->total_blue/number_unique+0.5);

      node_info->color_number=image->colors++;

    }

}

/*

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                                                             %

%                                                                             %

%                                                                             %

+   D e s t r o y C u b e I n f o                                             %

%                                                                             %

%                                                                             %

%                                                                             %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

%  DestroyCubeInfo() deallocates memory associated with an image.

%

%  The format of the DestroyCubeInfo method is:

%

%      DestroyCubeInfo(CubeInfo *cube_info)

%

%  A description of each parameter follows:

%

%    o cube_info: The address of a structure of type CubeInfo.

%

%

*/

static void DestroyCubeInfo(CubeInfo *cube_info)

{

  register Nodes

    *nodes;

  /*

    Release color cube tree storage.

  */

  do

  {

    nodes=cube_info->node_queue->next;

    MagickFreeMemory(cube_info->node_queue->nodes);

    MagickFreeMemory(cube_info->node_queue);

    cube_info->node_queue=nodes;

  } while (cube_info->node_queue != (Nodes *) NULL);

  if (cube_info->quantize_info->dither)

    MagickFreeMemory(cube_info->cache);

  MagickFreeMemory(cube_info);

}

/*

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                                                             %

%                                                                             %

%                                                                             %

%   D e s t r o y Q u a n t i z e I n f o                                     %

%                                                                             %

%                                                                             %

%                                                                             %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

%  DestroyQuantizeInfo() deallocates memory associated with an QuantizeInfo