• NAME
• SYNOPSIS
• FUNCTION DESCRIPTIONS
  • Assignment
  • Classification
  • ClosestColor
  • DefineColormap
  • DitherImage
  • XGetQuantizeInfo
  • InitializeCube
  • InitializeNode
  • PruneChild
  • PruneLevel
  • Reduce
  • Reduction
  • MapImage
  • MapImages
  • OrderedDitherImage
  • QuantizationError
  • QuantizeImage
  • QuantizeImages

NAME

SYNOPSIS

Classification(image)

ClosestColor(node)

DefineColormap(node)

DitherImage(image)

InitializeCube(depth)

node=InitializeNode(node,id,level)

MapImage(image,map_image,dither)

MapImages(images,map_image,dither)

OrderedDitherImage(image)

PruneChild(node)

PruneLevel(node)

QuantizationError(image)

QuantizeImage(quantize_info,image)

QuantizeImages(quantize_info,number_images,images)

Reduce(node)

Reduction(number_colors)

FUNCTION DESCRIPTIONS

Assignment

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 Assignment routine is:

        Assignment(quantize_info,image)

A description of each parameter follows.

o quantize_info:

Specifies a pointer to an QuantizeInfo structure.

o image:

Specifies a pointer to an Image structure; returned from ReadImage.

Classification

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, classification 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 Classification routine is:

        Classification(image)

A description of each parameter follows.

o image:

Specifies a pointer to an Image structure; returned from ReadImage.

ClosestColor

The format of the ClosestColor routine is:

        ClosestColor(node)

A description of each parameter follows.

o node:

The address of a structure of type Node which points to a node in the color cube tree that is to be pruned.

DefineColormap

The format of the DefineColormap routine is:

        DefineColormap(node)

A description of each parameter follows.

o node:

The address of a structure of type Node which points to a node in the color cube tree that is to be pruned.

DitherImage

First find the closest representation to the reference pixel color in the colormap, the node pixel is assigned this color. Next, the colormap color is subtracted from the reference pixels color, this represents the quantization error. Various amounts of this error are added to the pixels ahead and below the node pixel to correct for this error. The error proportions are:

          P     7/16

    3/16  5/16  1/16

The error is distributed left-to-right for even scanlines and right-to-left for odd scanlines.

The format of the DitherImage routine is:

        DitherImage(image)

A description of each parameter follows.

o image:

Specifies a pointer to an Image structure; returned from ReadImage.

XGetQuantizeInfo

The format of the GetMontageInfo routine is:

    XGetMontageInfo(quantize_info)

A description of each parameter follows:

o quantize_info:

Specifies a pointer to a MontageInfo structure.

InitializeCube

The format of the InitializeCube routine is:

        InitializeCube(depth)

A description of each parameter follows.

o depth:

Normally, this integer value is zero or one. A zero or one tells Quantize to choose a optimal tree depth of Log4. A tree of this depth generally allows the best representation of the reference image with the least amount of memory and the fastest computational speed. In some cases, such as an image with low color dispersion (a few number of colors), a value other than Log4 is required. To expand the color tree completely, use a value of 8.

InitializeNode

The format of the InitializeNode routine is:

        node=InitializeNode(node,id,level)

A description of each parameter follows.

o node:

The InitializeNode routine returns this integer address.

o id:

Specifies the child number of the node.

o level:

Specifies the level in the classification the node resides.

o mid_red:

Specifies the mid point of the red axis for this node.

o mid_green:

Specifies the mid point of the green axis for this node.

o mid_blue:

Specifies the mid point of the blue axis for this node.

PruneChild

The format of the PruneSubtree routine is:

        PruneChild(node)

A description of each parameter follows.

o node:

pointer to node in color cube tree that is to be pruned.

PruneLevel

The format of the PruneLevel routine is:

        PruneLevel(node)

A description of each parameter follows.

o node:

pointer to node in color cube tree that is to be pruned.

Reduce

The format of the Reduce routine is:

        Reduce(node)

A description of each parameter follows.

o node:

pointer to node in color cube tree that is to be pruned.

Reduction

  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.

The format of the Reduction routine is:

        Reduction(number_colors)

A description of each parameter follows.

o number_colors:

This integer value indicates the maximum number of colors in the quantized image or colormap. The actual number of colors allocated to the colormap may be less than this value, but never more.

MapImage

The format of the MapImage routine is:

        MapImage(image,map_image,dither)

A description of each parameter follows:

o image:

Specifies a pointer to an Image structure.

o map_image:

Specifies a pointer to a Image structure. Reduce image to a set of colors represented by this image.

o dither:

Set this integer value to something other than zero to dither the quantized image.

MapImages

The format of the MapImage routine is:

        MapImages(images,map_image,dither)

A description of each parameter follows:

o image:

Specifies a pointer to a set of Image structures.

o map_image:

Specifies a pointer to a Image structure. Reduce image to a set of colors represented by this image.

o dither:

Set this integer value to something other than zero to dither the quantized image.

OrderedDitherImage

The format of the OrderedDitherImage routine is:

        OrderedDitherImage(image)

A description of each parameter follows.

o image:

Specifies a pointer to an Image structure; returned from ReadImage.

QuantizationError

o mean_error_per_pixel:

This value is the mean error for any single pixel in the image.

o normalized_mean_square_error:

This value is the normalized mean quantization error for any single pixel in the image. This distance measure is normalized to a range between 0 and 1. It is independent of the range of red, green, and blue values in the image.

o normalized_maximum_square_error:

Thsi value is the normalized maximum quantization error for any single pixel in the image. This distance measure is normalized to a range between 0 and 1. It is independent of the range of red, green, and blue values in your image.

        QuantizationError(image)

A description of each parameter follows.

o image:

The address of a byte (8 bits) array of run-length encoded pixel data of your reference image. The sum of the run-length counts in the reference image must be equal to or exceed the number of pixels.

QuantizeImage

The format of the QuantizeImage routine is:

        QuantizeImage(quantize_info,image)

A description of each parameter follows:

o quantize_info:

Specifies a pointer to an QuantizeInfo structure.

o image:

Specifies a pointer to a Image structure.

QuantizeImages

The format of the QuantizeImages routine is:

        QuantizeImages(quantize_info,number_images,images)

A description of each parameter follows:

o quantize_info:

Specifies a pointer to an QuantizeInfo structure.

o number_images:

Specifies an unsigned integer representing the number images in the image set.

o images:

Specifies a pointer to a list of Image structures.