quantize - Reduce the Number of Unique Colors in an Image
Assignment(quantize_info,image)
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)
Procedure 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.
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.
Procedure 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
classification 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, 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.
Procedure ClosestColor traverses the color cube tree at a particular node
and determines which colormap entry best represents the input color.
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.
Procedure DefineColormap traverses the color cube tree and notes each
colormap entry. A colormap entry is any node in the color cube tree where
the number of unique colors is not zero.
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.
Procedure DitherImage uses the Floyd-Steinberg algorithm to dither the
image. Refer to ``An Adaptive Algorithm for Spatial GreySscale'', Robert W.
Floyd and Louis Steinberg, Proceedings of the S.I.D., Volume
17(2), 1976.
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.
Function XGetMontageInfo initializes the MontageInfo structure.
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.
Function InitializeCube initialize the Cube data structure.
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(number_colors). 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(number_colors) is required.
To expand the color tree completely, use a value of 8.
Function InitializeNode allocates memory for a new node in the color cube
tree and presets all fields to zero.
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.
Function PruneChild deletes the given node and merges its statistics into
its parent.
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.
Procedure PruneLevel deletes all nodes at the bottom level of the color
tree merging their color statistics into their parent node.
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.
Function Reduce traverses the color cube tree and prunes any node whose
quantization error falls below a particular threshold.
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.
Function 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 value 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.
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 replaces the colors of an image with the closest color from a
reference image.
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 replaces the colors of a sequence of images with the closest
color from a reference image.
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.
Procedure OrderedDitherImage uses the ordered dithering technique of
reducing color images to monochrome using positional information to retain
as much information as possible.
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.
Function QuantizationError measures the difference between the original and
quantized images. This difference is the total quantization error. The
error is computed by summing over all pixels in an image the distance
squared in RGB space between each reference pixel value and its quantized
value. These values are computed:
- 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.
The format of the QuantizationError routine is:
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.
Function QuantizeImage analyzes the colors within a reference image and
chooses a fixed number of colors to represent the image. The goal of the
algorithm is to minimize the difference between the input and output image
while minimizing the processing time.
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 analyzes the colors within a set of reference images and
chooses a fixed number of colors to represent the set. The goal of the
algorithm is to minimize the difference between the input and output images
while minimizing the processing time.
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.