This is quantize.c in view mode; [Download] [Up]
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% 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 %
% %
% %
% Reduce the Number of Unique Colors in an Image %
% %
% %
% Software Design %
% John Cristy %
% July 1992 %
% %
% Copyright 1997 E. I. du Pont de Nemours and Company %
% %
% Permission to use, copy, modify, distribute, and sell this software and %
% its documentation for any purpose is hereby granted without fee, %
% provided that the above Copyright notice appear in all copies and that %
% both that Copyright notice and this permission notice appear in %
% supporting documentation, and that the name of E. I. du Pont de Nemours %
% and Company not be used in advertising or publicity pertaining to %
% distribution of the software without specific, written prior %
% permission. E. I. du Pont de Nemours and Company makes no representations %
% about the suitability of this software for any purpose. It is provided %
% "as is" without express or implied warranty. %
% %
% E. I. du Pont de Nemours and Company disclaims all warranties with regard %
% to this software, including all implied warranties of merchantability %
% and fitness, in no event shall E. I. du Pont de Nemours and Company be %
% liable for any special, indirect or consequential damages or any %
% damages whatsoever resulting from loss of use, data or profits, whether %
% in an action of contract, negligence or other tortious action, arising %
% out of or in connection with the use or performance of this software. %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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 program 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.
%
% Function Quantize 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 reclassification 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 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 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.
%
% For efficiency, QUANTIZE requires that the reference image be in a
% run-length encoded format.
%
% With the permission of USC Information Sciences Institute, 4676 Admiralty
% Way, Marina del Rey, California 90292, this code was adapted from module
% ALCOLS written by Paul Raveling.
%
% The names of ISI and USC are not used in advertising or publicity
% pertaining to distribution of the software without prior specific
% written permission from ISI.
%
%
*/
/*
Include declarations.
*/
#include "magick.h"
/*
Define declarations.
*/
#define MaxNodes 266817
#define MaxSpan ((1 << MaxTreeDepth)-1)
#define MaxTreeDepth 8
#define NodesInAList 2048
/*
Structures.
*/
typedef struct _Node
{
unsigned char
id,
level,
census,
mid_red,
mid_green,
mid_blue;
unsigned int
color_number,
number_unique;
double
quantization_error,
total_red,
total_green,
total_blue;
struct _Node
*parent,
*child[8];
} Node;
typedef struct _Nodes
{
Node
nodes[NodesInAList];
struct _Nodes
*next;
} Nodes;
typedef struct _Cube
{
Node
*root;
unsigned int
depth;
unsigned long
colors;
ColorPacket
color,
*colormap;
double
distance,
pruning_threshold,
next_pruning_threshold;
unsigned int
*squares,
nodes,
free_nodes,
color_number;
Node
*next_node;
Nodes
*node_queue;
} Cube;
/*
Global variables.
*/
static Cube
cube;
/*
Function prototypes.
*/
static Node
*InitializeNode(const unsigned int,const unsigned int,Node *,
const unsigned int,const unsigned int,const unsigned int);
static unsigned int
DitherImage(Image *);
static void
ClosestColor(const Node *),
DefineColormap(Node *),
PruneLevel(const Node *);
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% A s s i g n m e n t %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static void Assignment(QuantizeInfo *quantize_info,Image *image)
{
#define AssignImageText " Assigning image colors... "
register int
i;
const Node
*node;
register RunlengthPacket
*p;
register unsigned short
index;
unsigned int
id;
/*
Allocate image colormap.
*/
if (image->colormap == (ColorPacket *) NULL)
image->colormap=(ColorPacket *)
malloc(cube.colors*sizeof(ColorPacket));
else
image->colormap=(ColorPacket *)
realloc((char *) image->colormap,cube.colors*sizeof(ColorPacket));
if (image->colormap == (ColorPacket *) NULL)
{
Warning("Unable to quantize image","Memory allocation failed");
Exit(1);
}
if (image->signature != (char *) NULL)
free((char *) image->signature);
image->signature=(char *) NULL;
cube.colormap=image->colormap;
cube.colors=0;
DefineColormap(cube.root);
if ((quantize_info->number_colors == 2) &&
(quantize_info->colorspace == GRAYColorspace))
{
unsigned int
polarity;
/*
Monochrome image.
*/
polarity=Intensity(image->colormap[0]) > Intensity(image->colormap[1]);
image->colormap[polarity].red=0;
image->colormap[polarity].green=0;
image->colormap[polarity].blue=0;
image->colormap[!polarity].red=MaxRGB;
image->colormap[!polarity].green=MaxRGB;
image->colormap[!polarity].blue=MaxRGB;
}
if (quantize_info->colorspace != TransparentColorspace)
{
image->matte=False;
image->class=PseudoClass;
}
image->colors=(unsigned int) cube.colors;
/*
Create a reduced color image.
*/
if (quantize_info->dither)
quantize_info->dither=!DitherImage(image);
p=image->pixels;
if (!quantize_info->dither)
for (i=0; i < image->packets; i++)
{
/*
Identify the deepest node containing the pixel's color.
*/
node=cube.root;
for (index=MaxTreeDepth-1; (int) index > 0; index--)
{
id=(((Quantum) DownScale(p->red) >> index) & 0x01) << 2 |
(((Quantum) DownScale(p->green) >> index) & 0x01) << 1 |
(((Quantum) DownScale(p->blue) >> index) & 0x01);
if ((node->census & (1 << id)) == 0)
break;
node=node->child[id];
}
/*
Find closest color among siblings and their children.
*/
cube.color.red=p->red;
cube.color.green=p->green;
cube.color.blue=p->blue;
cube.distance=3.0*(MaxRGB+1)*(MaxRGB+1);
ClosestColor(node->parent);
index=cube.color_number;
if (image->class == PseudoClass)
p->index=index;
else
{
p->red=image->colormap[index].red;
p->green=image->colormap[index].green;
p->blue=image->colormap[index].blue;
}
p++;
if (QuantumTick(i,image))
ProgressMonitor(AssignImageText,i,image->packets);
}
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% C l a s s i f i c a t i o n %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static void Classification(Image *image)
{
#define ClassifyImageText " Classifying image colors... "
double
distance_squared;
int
distance;
register int
i;
Node
*node;
register RunlengthPacket
*p;
register unsigned int
index;
unsigned int
bisect,
count,
id,
level;
cube.root->quantization_error+=
3.0*(MaxRGB+1)*(MaxRGB+1)*image->columns*image->rows;
p=image->pixels;
for (i=0; i < image->packets; i++)
{
if (cube.nodes > MaxNodes)
{
/*
Prune one level if the color tree is too large.
*/
PruneLevel(cube.root);
cube.depth--;
}
/*
Start at the root and descend the color cube tree.
*/
count=p->length+1;
node=cube.root;
index=MaxTreeDepth-1;
for (level=1; level <= cube.depth; level++)
{
id=(((Quantum) DownScale(p->red) >> index) & 0x01) << 2 |
(((Quantum) DownScale(p->green) >> index) & 0x01) << 1 |
(((Quantum) DownScale(p->blue) >> index) & 0x01);
if (node->child[id] == (Node *) NULL)
{
/*
Set colors of new node to contain pixel.
*/
node->census|=1 << id;
bisect=(unsigned int) (1 << (MaxTreeDepth-level)) >> 1;
node->child[id]=InitializeNode(id,level,node,
node->mid_red+(id & 4 ? bisect : -bisect),
node->mid_green+(id & 2 ? bisect : -bisect),
node->mid_blue+(id & 1 ? bisect : -bisect));
if (node->child[id] == (Node *) NULL)
{
Warning("Unable to quantize image","Memory allocation failed");
Exit(1);
}
if (level == cube.depth)
cube.colors++;
}
node=node->child[id];
/*
Approximate the quantization error represented by this node.
*/
distance=(int) DownScale(p->red)-(int) node->mid_red;
distance_squared=cube.squares[distance];
distance=(int) DownScale(p->green)-(int) node->mid_green;
distance_squared+=cube.squares[distance];
distance=(int) DownScale(p->blue)-(int) node->mid_blue;
distance_squared+=cube.squares[distance];
node->quantization_error+=distance_squared*count;
index--;
}
/*
Increment unique color count and sum RGB values for this leaf for later
derivation of the mean cube color.
*/
node->number_unique+=count;
node->total_red+=p->red*count;
node->total_green+=p->green*count;
node->total_blue+=p->blue*count;
p++;
if (QuantumTick(i,image))
ProgressMonitor(ClassifyImageText,i,image->packets);
}
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% C l o s e s t C o l o r %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static void ClosestColor(const Node *node)
{
register unsigned int
id;
/*
Traverse any children.
*/
if (node->census != 0)
for (id=0; id < 8; id++)
if (node->census & (1 << id))
ClosestColor(node->child[id]);
if (node->number_unique != 0)
{
register float
distance_squared;
register int
distance;
register ColorPacket
*color;
/*
Determine if this color is "closest".
*/
color=cube.colormap+node->color_number;
distance=(int) color->red-(int) cube.color.red;
distance_squared=cube.squares[distance];
distance=(int) color->green-(int) cube.color.green;
distance_squared+=cube.squares[distance];
distance=(int) color->blue-(int) cube.color.blue;
distance_squared+=cube.squares[distance];
if (distance_squared < cube.distance)
{
cube.distance=distance_squared;
cube.color_number=(unsigned short) node->color_number;
}
}
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% D e f i n e C o l o r m a p %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static void DefineColormap(Node *node)
{
register double
number_unique;
register unsigned int
id;
/*
Traverse any children.
*/
if (node->census != 0)
for (id=0; id < 8; id++)
if (node->census & (1 << id))
DefineColormap(node->child[id]);
if (node->number_unique != 0)
{
/*
Colormap entry is defined by the mean color in this cube.
*/
number_unique=node->number_unique;
cube.colormap[cube.colors].red=(Quantum)
((node->total_red+number_unique/2)/number_unique);
cube.colormap[cube.colors].green=(Quantum)
((node->total_green+number_unique/2)/number_unique);
cube.colormap[cube.colors].blue=(Quantum)
((node->total_blue+number_unique/2)/number_unique);
node->color_number=(unsigned int) cube.colors++;
}
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% D i t h e r I m a g e %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static unsigned int DitherImage(Image *image)
{
#define CacheShift (QuantumDepth-6)
#define DitherImageText " Dithering image... "
typedef struct _ErrorPacket
{
int
red,
green,
blue;
} ErrorPacket;
ErrorPacket
*error;
int
blue_error,
green_error,
red_error,
step;
Node
*node;
Quantum
blue,
green,
red;
register ErrorPacket
*cs,
*ns;
register int
*cache,
*error_limit,
i;
register Quantum
*range_limit;
register RunlengthPacket
*q;
register unsigned short
index;
unsigned int
id,
quantum,
x,
y;
/*
Image must be uncompressed.
*/
if (!UncompressImage(image))
return(True);
/*
Allocate memory.
*/
cache=(int *) malloc((1 << 18)*sizeof(int));
error=(ErrorPacket *) malloc(((image->columns+2) << 1)*sizeof(ErrorPacket));
error_limit=(int *) malloc((MaxRGB*2+1)*sizeof(int));
range_limit=(Quantum *) malloc(3*(MaxRGB+1)*sizeof(Quantum));
if ((cache == (int *) NULL) || (error == (ErrorPacket *) NULL) ||
(error_limit == (int *) NULL) || (range_limit == (Quantum *) NULL))
{
Warning("Unable to dither image","Memory allocation failed");
return(True);
}
/*
Initialize color cache.
*/
for (i=0; i < (1 << 18); i++)
cache[i]=(-1);
/*
Initialize error tables.
*/
for (i=0; i < ((image->columns+2) << 1); i++)
{
error[i].red=0;
error[i].green=0;
error[i].blue=0;
}
/*
Initialize error limit (constrain error).
*/
quantum=(unsigned int) Max(image->colors >> 4,1);
if ((quantum > 1) && (QuantumDepth != 8))
quantum>>=1;
error_limit+=MaxRGB;
step=0;
for (i=0; i < ((MaxRGB+1)/quantum); i++)
{
error_limit[i]=step;
error_limit[-i]=(-step);
step++;
}
if (quantum > 3)
for ( ; i < (3*(MaxRGB+1)/quantum); i++)
{
error_limit[i]=step;
error_limit[-i]=(-step);
step+=(i & 0x01) ? 0 : 1;
}
for ( ; i <= MaxRGB; i++)
{
error_limit[i]=step;
error_limit[-i]=(-step);
}
/*
Initialize range tables.
*/
for (i=0; i <= MaxRGB; i++)
{
range_limit[i]=0;
range_limit[i+(MaxRGB+1)]=(Quantum) i;
range_limit[i+(MaxRGB+1)*2]=MaxRGB;
}
range_limit+=(MaxRGB+1);
/*
Dither image.
*/
for (y=0; y < image->rows; y++)
{
q=image->pixels+image->columns*y;
cs=error+1;
ns=cs+image->columns+2;
step=y & 0x01 ? -1 : 1;
if (step < 0)
{
/*
Distribute error right-to-left for odd scanlines.
*/
q+=(image->columns-1);
ns=error+image->columns;
cs=ns+image->columns+2;
}
for (x=0; x < image->columns; x++)
{
red_error=error_limit[(cs->red+8)/16];
green_error=error_limit[(cs->green+8)/16];
blue_error=error_limit[(cs->blue+8)/16];
red=range_limit[(int) q->red+red_error];
green=range_limit[(int) q->green+green_error];
blue=range_limit[(int) q->blue+blue_error];
i=(blue >> CacheShift) << 12 | (green >> CacheShift) << 6 |
(red >> CacheShift);
if (cache[i] < 0)
{
/*
Identify the deepest node containing the pixel's color.
*/
node=cube.root;
for (index=MaxTreeDepth-1; (int) index > 0; index--)
{
id=(((Quantum) DownScale(red) >> index) & 0x01) << 2 |
(((Quantum) DownScale(green) >> index) & 0x01) << 1 |
(((Quantum) DownScale(blue) >> index) & 0x01);
if ((node->census & (1 << id)) == 0)
break;
node=node->child[id];
}
/*
Find closest color among siblings and their children.
*/
cube.color.red=red;
cube.color.green=green;
cube.color.blue=blue;
cube.distance=3.0*(MaxRGB+1)*(MaxRGB+1);
ClosestColor(node->parent);
cache[i]=cube.color_number;
}
index=(unsigned short) cache[i];
if (image->class == PseudoClass)
q->index=index;
else
{
q->red=image->colormap[index].red;
q->green=image->colormap[index].green;
q->blue=image->colormap[index].blue;
}
q+=step;
/*
Propagate the error in these proportions:
Q 7/16
3/16 5/16 1/16
*/
red_error=(int) red-(int) image->colormap[index].red;
green_error=(int) green-(int) image->colormap[index].green;
blue_error=(int) blue-(int) image->colormap[index].blue;
cs->red=0;
cs->green=0;
cs->blue=0;
cs+=step;
cs->red+=7*red_error;
cs->green+=7*green_error;
cs->blue+=7*blue_error;
ns-=step;
ns->red+=3*red_error;
ns->green+=3*green_error;
ns->blue+=3*blue_error;
ns+=step;
ns->red+=5*red_error;
ns->green+=5*green_error;
ns->blue+=5*blue_error;
ns+=step;
ns->red+=red_error;
ns->green+=green_error;
ns->blue+=blue_error;
}
ProgressMonitor(DitherImageText,y,image->rows);
}
/*
Free up memory.
*/
range_limit-=(MaxRGB+1);
free((char *) range_limit);
error_limit-=MaxRGB;
free((char *) error_limit);
free((char *) error);
free((char *) cache);
return(False);
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% X G e t Q u a n t i z e I n f o %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
Export void GetQuantizeInfo(QuantizeInfo *quantize_info)
{
assert(quantize_info != (QuantizeInfo *) NULL);
quantize_info->number_colors=MaxRGB+1;
quantize_info->tree_depth=8;
quantize_info->dither=False;
quantize_info->colorspace=RGBColorspace;
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% I n i t i a l i z e C u b e %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static void InitializeCube(int depth)
{
register int
i;
/*
Initialize tree to describe color cube.
*/
cube.node_queue=(Nodes *) NULL;
cube.nodes=0;
cube.free_nodes=0;
if (depth > MaxTreeDepth)
depth=MaxTreeDepth;
if (depth < 2)
depth=2;
cube.depth=depth;
/*
Initialize root node.
*/
cube.root=InitializeNode(0,0,(Node *) NULL,(MaxSpan+1) >> 1,(MaxSpan+1) >> 1,
(MaxSpan+1) >> 1);
cube.squares=(unsigned int *) malloc((MaxRGB+MaxRGB+1)*sizeof(unsigned int));
if ((cube.root == (Node *) NULL) || (cube.squares == (unsigned int *) NULL))
{
Warning("Unable to quantize image","Memory allocation failed");
Exit(1);
}
cube.root->parent=cube.root;
cube.root->quantization_error=0.0;
cube.colors=0;
cube.squares+=MaxRGB;
for (i=(-MaxRGB); i <= MaxRGB; i++)
cube.squares[i]=i*i;
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% I n i t i a l i z e N o d e %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
*/
static Node *InitializeNode(const unsigned int id,const unsigned int level,
Node *parent,const unsigned int mid_red,const unsigned int mid_green,
const unsigned int mid_blue)
{
register int
i;
Node
*node;
if (cube.free_nodes == 0)
{
Nodes
*nodes;
/*
Allocate a new nodes of nodes.
*/
nodes=(Nodes *) malloc(sizeof(Nodes));
if (nodes == (Nodes *) NULL)
return((Node *) NULL);
nodes->next=cube.node_queue;
cube.node_queue=nodes;
cube.next_node=nodes->nodes;
cube.free_nodes=NodesInAList;
}
cube.nodes++;
cube.free_nodes--;
node=cube.next_node++;
node->parent=parent;
for (i=0; i < 8; i++)
node->child[i]=(Node *) NULL;
node->id=id;
node->level=level;
node->census=0;
node->mid_red=mid_red;
node->mid_green=mid_green;
node->mid_blue=mid_blue;
node->quantization_error=0.0;
node->number_unique=0;
node->total_red=0.0;
node->total_green=0.0;
node->total_blue=0.0;
return(node);
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% P r u n e C h i l d %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static void PruneChild(const Node *node)
{
Node
*parent;
/*
Merge color statistics into parent.
*/
parent=node->parent;
parent->census&=~(1 << node->id);
parent->number_unique+=node->number_unique;
parent->total_red+=node->total_red;
parent->total_green+=node->total_green;
parent->total_blue+=node->total_blue;
cube.nodes--;
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% P r u n e L e v e l %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static void PruneLevel(const Node *node)
{
register int
id;
/*
Traverse any children.
*/
if (node->census != 0)
for (id=0; id < 8; id++)
if (node->census & (1 << id))
PruneLevel(node->child[id]);
if (node->level == cube.depth)
PruneChild(node);
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% R e d u c e %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static void Reduce(const Node *node)
{
register unsigned int
id;
/*
Traverse any children.
*/
if (node->census != 0)
for (id=0; id < 8; id++)
if (node->census & (1 << id))
Reduce(node->child[id]);
if (node->quantization_error <= cube.pruning_threshold)
PruneChild(node);
else
{
/*
Find minimum pruning threshold.
*/
if (node->number_unique > 0)
cube.colors++;
if (node->quantization_error < cube.next_pruning_threshold)
cube.next_pruning_threshold=node->quantization_error;
}
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% R e d u c t i o n %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static void Reduction(const unsigned int number_colors)
{
#define ReduceImageText " Reducing image colors... "
unsigned int
span;
span=(unsigned int) cube.colors;
cube.next_pruning_threshold=1;
while (cube.colors > number_colors)
{
cube.pruning_threshold=cube.next_pruning_threshold;
cube.next_pruning_threshold=cube.root->quantization_error-1.0;
cube.colors=0;
Reduce(cube.root);
ProgressMonitor(ReduceImageText,(unsigned int) (span-cube.colors),
span-number_colors+1);
}
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% M a p I m a g e %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
void MapImage(Image *image,Image *map_image,const unsigned int dither)
{
Nodes
*nodes;
QuantizeInfo
quantize_info;
assert(image != (Image *) NULL);
if (map_image == (Image *) NULL)
return;
/*
Classify image colors from the reference image.
*/
InitializeCube(8);
Classification(map_image);
quantize_info.number_colors=cube.colors;
quantize_info.dither=dither;
quantize_info.colorspace=image->matte ? TransparentColorspace : RGBColorspace;
Assignment(&quantize_info,image);
/*
Release color cube tree storage.
*/
do
{
nodes=cube.node_queue->next;
free((char *) cube.node_queue);
cube.node_queue=nodes;
} while (cube.node_queue != (Nodes *) NULL);
cube.squares-=MaxRGB;
free((char *) cube.squares);
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% M a p I m a g e s %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
Export void MapImages(Image *images,Image *map_image,const unsigned int dither)
{
Image
*image;
Nodes
*nodes;
QuantizeInfo
quantize_info;
assert(images != (Image *) NULL);
if (images->next == (Image *) NULL)
{
/*
Handle a single image with MapImage.
*/
MapImage(images,map_image,dither);
return;
}
GetQuantizeInfo(&quantize_info);
quantize_info.dither=dither;
if (map_image == (Image *) NULL)
{
/*
Create a global colormap for an image sequence.
*/
if (images->class == PseudoClass)
quantize_info.number_colors=images->colors;
for (image=images; image != (Image *) NULL; image=image->next)
{
if (image->matte)
quantize_info.colorspace=TransparentColorspace;
if (image->class == PseudoClass)
if (image->colors > quantize_info.number_colors)
quantize_info.number_colors=image->colors;
}
QuantizeImages(&quantize_info,images);
return;
}
/*
Classify image colors from the reference image.
*/
InitializeCube(8);
Classification(map_image);
quantize_info.number_colors=cube.colors;
for (image=images; image != (Image *) NULL; image=image->next)
{
quantize_info.colorspace=
image->matte ? TransparentColorspace : RGBColorspace;
Assignment(&quantize_info,image);
}
/*
Release color cube tree storage.
*/
do
{
nodes=cube.node_queue->next;
free((char *) cube.node_queue);
cube.node_queue=nodes;
} while (cube.node_queue != (Nodes *) NULL);
cube.squares-=MaxRGB;
free((char *) cube.squares);
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% O r d e r e d D i t h e r I m a g e %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
static void OrderedDitherImage(Image *image)
{
static Quantum
DitherMatrix[8][8] =
{
{ UpScale( 0), UpScale(192), UpScale( 48), UpScale(240),
UpScale( 12), UpScale(204), UpScale( 60), UpScale(252) },
{ UpScale(128), UpScale( 64), UpScale(176), UpScale(112),
UpScale(140), UpScale( 76), UpScale(188), UpScale(124) },
{ UpScale( 32), UpScale(224), UpScale( 16), UpScale(208),
UpScale( 44), UpScale(236), UpScale( 28), UpScale(220) },
{ UpScale(160), UpScale( 96), UpScale(144), UpScale( 80),
UpScale(172), UpScale(108), UpScale(156), UpScale( 92) },
{ UpScale( 8), UpScale(200), UpScale( 56), UpScale(248),
UpScale( 4), UpScale(196), UpScale( 52), UpScale(244) },
{ UpScale(136), UpScale( 72), UpScale(184), UpScale(120),
UpScale(132), UpScale( 68), UpScale(180), UpScale(116) },
{ UpScale( 40), UpScale(232), UpScale( 24), UpScale(216),
UpScale( 36), UpScale(228), UpScale( 20), UpScale(212) },
{ UpScale(168), UpScale(104), UpScale(152), UpScale( 88),
UpScale(164), UpScale(100), UpScale(148), UpScale( 84) }
};
register int
x,
y;
register RunlengthPacket
*p;
/*
Transform image to uncompressed normalized grayscale.
*/
RGBTransformImage(image,GRAYColorspace);
NormalizeImage(image);
if (!UncompressImage(image))
return;
/*
Initialize colormap.
*/
image->class=PseudoClass;
if (image->colormap != (ColorPacket *) NULL)
free((char *) image->colormap);
image->colors=2;
image->colormap=(ColorPacket *) malloc(image->colors*sizeof(ColorPacket));
if (image->colormap == (ColorPacket *) NULL)
{
Warning("Unable to quantize image","Memory allocation failed");
Exit(1);
}
image->colormap[0].red=0;
image->colormap[0].green=0;
image->colormap[0].blue=0;
image->colormap[1].red=MaxRGB;
image->colormap[1].green=MaxRGB;
image->colormap[1].blue=MaxRGB;
/*
Dither image with the ordered dithering technique.
*/
p=image->pixels;
for (y=0; y < image->rows; y++)
{
for (x=0; x < image->columns; x++)
{
p->index=p->red > DitherMatrix[y & 0x07][x & 0x07] ? 1 : 0;
p++;
}
ProgressMonitor(DitherImageText,y,image->rows);
}
SyncImage(image);
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% Q u a n t i z a t i o n E r r o r %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
void QuantizationError(Image *image)
{
double
total_error;
float
distance_squared,
maximum_error_per_pixel;
int
distance;
register int
i;
register RunlengthPacket
*p;
/*
Initialize measurement.
*/
assert(image != (Image *) NULL);
image->mean_error_per_pixel=0;
image->normalized_mean_error=0.0;
image->normalized_maximum_error=0.0;
NumberColors(image,(FILE *) NULL);
if (image->class == DirectClass)
return;
cube.squares=(unsigned int *) malloc((MaxRGB+MaxRGB+1)*sizeof(unsigned int));
if (cube.squares == (unsigned int *) NULL)
{
Warning("Unable to measure error","Memory allocation failed");
return;
}
cube.squares+=MaxRGB;
for (i=(-MaxRGB); i <= MaxRGB; i++)
cube.squares[i]=i*i;
/*
For each pixel, collect error statistics.
*/
maximum_error_per_pixel=0;
total_error=0;
p=image->pixels;
for (i=0; i < image->packets; i++)
{
distance=(int) p->red-(int) image->colormap[p->index].red;
distance_squared=cube.squares[distance];
distance=(int) p->green-(int) image->colormap[p->index].green;
distance_squared+=cube.squares[distance];
distance=(int) p->blue-(int) image->colormap[p->index].blue;
distance_squared+=cube.squares[distance];
total_error+=(distance_squared*((double) p->length+1.0));
if (distance_squared > maximum_error_per_pixel)
maximum_error_per_pixel=distance_squared;
p++;
}
/*
Compute final error statistics.
*/
image->mean_error_per_pixel=(unsigned int)
total_error/(image->columns*image->rows);
image->normalized_mean_error=
(image->mean_error_per_pixel)/(3.0*(MaxRGB+1)*(MaxRGB+1));
image->normalized_maximum_error=
maximum_error_per_pixel/(3.0*(MaxRGB+1)*(MaxRGB+1));
cube.squares-=MaxRGB;
free((char *) cube.squares);
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% Q u a n t i z e I m a g e %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
*/
Export void QuantizeImage(QuantizeInfo *quantize_info,Image *image)
{
int
depth;
Nodes
*nodes;
assert(image != (Image *) NULL);
if ((quantize_info->number_colors == 2) &&
(quantize_info->colorspace == GRAYColorspace) && quantize_info->dither)
{
OrderedDitherImage(image);
return;
}
if (quantize_info->number_colors == 0)
quantize_info->number_colors=1;
if (quantize_info->number_colors > MaxColormapSize)
quantize_info->number_colors=MaxColormapSize;
if (image->packets == (image->columns*image->rows))
CompressImage(image);
depth=quantize_info->tree_depth;
if (depth == 0)
{
unsigned int
colors;
/*
Depth of color classification tree is: Log4(colormap size)+2.
*/
colors=quantize_info->number_colors;
for (depth=1; colors != 0; depth++)
colors>>=2;
if (quantize_info->dither)
depth--;
if (image->class == PseudoClass)
depth+=2;
}
/*
Reduce the number of colors in the continuous tone image.
*/
InitializeCube(depth);
if (quantize_info->colorspace != RGBColorspace)
RGBTransformImage(image,quantize_info->colorspace);
Classification(image);
if ((cube.colors >> 1) < quantize_info->number_colors)
quantize_info->dither=False;
if (quantize_info->number_colors < cube.colors)
Reduction(quantize_info->number_colors);
Assignment(quantize_info,image);
if (quantize_info->colorspace != RGBColorspace)
TransformRGBImage(image,quantize_info->colorspace);
/*
Release color cube tree storage.
*/
do
{
nodes=cube.node_queue->next;
free((char *) cube.node_queue);
cube.node_queue=nodes;
} while (cube.node_queue != (Nodes *) NULL);
cube.squares-=MaxRGB;
free((char *) cube.squares);
}
/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% %
% %
% Q u a n t i z e I m a g e s %
% %
% %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% 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.
%
%
*/
Export void QuantizeImages(QuantizeInfo *quantize_info,Image *images)
{
int
depth;
MonitorHandler
handler;
Image
*image;
Nodes
*nodes;
register int
i;
unsigned int
number_images;
assert(images != (Image *) NULL);
if (images->next == (Image *) NULL)
{
/*
Handle a single image with QuantizeImage.
*/
QuantizeImage(quantize_info,images);
return;
}
if (quantize_info->number_colors == 0)
quantize_info->number_colors=1;
if (quantize_info->number_colors > MaxColormapSize)
quantize_info->number_colors=MaxColormapSize;
depth=quantize_info->tree_depth;
if (depth == 0)
{
int
pseudo_class;
unsigned int
colors;
/*
Depth of color classification tree is: Log4(colormap size)+2.
*/
colors=quantize_info->number_colors;
for (depth=1; colors != 0; depth++)
colors>>=2;
if (quantize_info->dither)
depth--;
pseudo_class=True;
for (image=images; image != (Image *) NULL; image=image->next)
pseudo_class|=(image->class == PseudoClass);
if (pseudo_class)
depth+=2;
}
/*
Reduce the number of colors in the continuous tone image sequence.
*/
InitializeCube(depth);
image=images;
for (i=0; image != (Image *) NULL; i++)
{
if (image->packets == (image->columns*image->rows))
CompressImage(image);
if (quantize_info->colorspace != RGBColorspace)
RGBTransformImage(image,quantize_info->colorspace);
image=image->next;
}
number_images=i;
image=images;
for (i=0; image != (Image *) NULL; i++)
{
handler=SetMonitorHandler((MonitorHandler) NULL);
Classification(image);
image=image->next;
(void) SetMonitorHandler(handler);
ProgressMonitor(ClassifyImageText,i,number_images);
}
if ((cube.colors >> 1) < quantize_info->number_colors)
quantize_info->dither=False;
Reduction(quantize_info->number_colors);
image=images;
for (i=0; image != (Image *) NULL; i++)
{
handler=SetMonitorHandler((MonitorHandler) NULL);
Assignment(quantize_info,image);
if (quantize_info->colorspace != RGBColorspace)
TransformRGBImage(image,quantize_info->colorspace);
image=image->next;
(void) SetMonitorHandler(handler);
ProgressMonitor(AssignImageText,i,number_images);
}
/*
Release color cube tree storage.
*/
do
{
nodes=cube.node_queue->next;
free((char *) cube.node_queue);
cube.node_queue=nodes;
} while (cube.node_queue != (Nodes *) NULL);
cube.squares-=MaxRGB;
free((char *) cube.squares);
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.