% MagickCore Methods to Reduce the Number of Unique Colors in an Image %
% %
% Software Design %
-% John Cristy %
+% Cristy %
% July 1992 %
% %
% %
-% Copyright 1999-2013 ImageMagick Studio LLC, a non-profit organization %
+% Copyright 1999-2014 ImageMagick Studio LLC, a non-profit organization %
% dedicated to making software imaging solutions freely available. %
% %
% You may not use this file except in compliance with the License. You may %
%
% 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.
+% these cubes are defined by the coordinate of two opposite vertices (vertex
+% nearest the origin in RGB space and the vertex farthest from the origin).
%
% The tree's root node represents the entire domain, (0,0,0) through
% (Cmax,Cmax,Cmax). Each lower level in the tree is generated by
Nodes
*node_queue;
+ MemoryInfo
+ *memory_info;
+
ssize_t
*cache;
alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel);
}
-static inline void AssociateAlphaPixelInfo(const Image *image,
- const CubeInfo *cube_info,const PixelInfo *pixel,
- RealPixelInfo *alpha_pixel)
+static inline void AssociateAlphaPixelInfo(const CubeInfo *cube_info,
+ const PixelInfo *pixel,RealPixelInfo *alpha_pixel)
{
double
alpha;
q=image->colormap;
for (i=0; i < (ssize_t) image->colors; i++)
{
- intensity=(double) ((double) GetPixelInfoIntensity(q) <
- ((double) QuantumRange/2.0) ? 0 : QuantumRange);
+ intensity=(double) (GetPixelInfoLuma(q) < (QuantumRange/2.0) ? 0 :
+ QuantumRange);
q->red=intensity;
q->green=intensity;
q->blue=intensity;
associate_alpha=image->alpha_trait == BlendPixelTrait ? MagickTrue :
MagickFalse;
- if (cube_info->quantize_info->colorspace == TransparentColorspace)
- associate_alpha=MagickFalse;
if ((cube_info->quantize_info->number_colors == 2) &&
(cube_info->quantize_info->colorspace == GRAYColorspace))
associate_alpha=MagickFalse;
*/
node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
if (node_info->child[id] == (NodeInfo *) NULL)
- (void) ThrowMagickException(exception,GetMagickModule(),
- ResourceLimitError,"MemoryAllocationFailed","`%s'",
- image->filename);
+ {
+ (void) ThrowMagickException(exception,GetMagickModule(),
+ ResourceLimitError,"MemoryAllocationFailed","`%s'",
+ image->filename);
+ continue;
+ }
if (level == MaxTreeDepth)
cube_info->colors++;
}
error.blue=QuantumScale*(pixel.blue-mid.blue);
if (cube_info->associate_alpha != MagickFalse)
error.alpha=QuantumScale*(pixel.alpha-mid.alpha);
- node_info->quantize_error+=sqrt((double) (count*error.red*error.red+
- count*error.green*error.green+count*error.blue*error.blue+count*
+ node_info->quantize_error+=count*sqrt((double) (error.red*error.red+
+ error.green*error.green+error.blue*error.blue+
error.alpha*error.alpha));
cube_info->root->quantize_error+=node_info->quantize_error;
index--;
*/
node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
if (node_info->child[id] == (NodeInfo *) NULL)
- (void) ThrowMagickException(exception,GetMagickModule(),
- ResourceLimitError,"MemoryAllocationFailed","%s",
- image->filename);
+ {
+ (void) ThrowMagickException(exception,GetMagickModule(),
+ ResourceLimitError,"MemoryAllocationFailed","%s",
+ image->filename);
+ continue;
+ }
if (level == cube_info->depth)
cube_info->colors++;
}
error.blue=QuantumScale*(pixel.blue-mid.blue);
if (cube_info->associate_alpha != MagickFalse)
error.alpha=QuantumScale*(pixel.alpha-mid.alpha);
- node_info->quantize_error+=sqrt((double) (count*error.red*error.red+
- count*error.green*error.green+count*error.blue*error.blue+count*
+ node_info->quantize_error+=count*sqrt((double) (error.red*error.red+
+ error.green*error.green+error.blue*error.blue+
error.alpha*error.alpha));
cube_info->root->quantize_error+=node_info->quantize_error;
index--;
if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
(cube_info->quantize_info->colorspace != CMYKColorspace))
(void) TransformImageColorspace((Image *) image,sRGBColorspace,exception);
- return(MagickTrue);
+ return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue);
}
\f
/*
cube_info->node_queue);
cube_info->node_queue=nodes;
} while (cube_info->node_queue != (Nodes *) NULL);
- if (cube_info->cache != (ssize_t *) NULL)
- cube_info->cache=(ssize_t *) RelinquishMagickMemory(cube_info->cache);
+ if (cube_info->memory_info != (MemoryInfo *) NULL)
+ cube_info->memory_info=RelinquishVirtualMemory(cube_info->memory_info);
cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info);
cube_info=(CubeInfo *) RelinquishMagickMemory(cube_info);
}
/*
Store the error.
*/
- AssociateAlphaPixelInfo(image,&cube,image->colormap+index,&color);
+ AssociateAlphaPixelInfo(&cube,image->colormap+index,&color);
current[u].red=pixel.red-color.red;
current[u].green=pixel.green-color.green;
current[u].blue=pixel.blue-color.blue;
MagickBooleanType
proceed;
-#if defined(MAGICKCORE_OPENMP_SUPPORT)
- #pragma omp critical (MagickCore_FloydSteinbergDither)
-#endif
proceed=SetImageProgress(image,DitherImageTag,(MagickOffsetType) y,
image->rows);
if (proceed == MagickFalse)
break;
node_info=node_info->child[id];
}
- node_info=node_info->parent;
/*
Find closest color among siblings and their children.
*/
*/
(void) CopyMagickMemory(p->error,p->error+1,(ErrorQueueLength-1)*
sizeof(p->error[0]));
- AssociateAlphaPixelInfo(image,cube_info,image->colormap+index,&color);
+ AssociateAlphaPixelInfo(cube_info,image->colormap+index,&color);
p->error[ErrorQueueLength-1].red=pixel.red-color.red;
p->error[ErrorQueueLength-1].green=pixel.green-color.green;
p->error[ErrorQueueLength-1].blue=pixel.blue-color.blue;
Initialize dither resources.
*/
length=(size_t) (1UL << (4*(8-CacheShift)));
- cube_info->cache=(ssize_t *) AcquireQuantumMemory(length,
- sizeof(*cube_info->cache));
- if (cube_info->cache == (ssize_t *) NULL)
+ cube_info->memory_info=AcquireVirtualMemory(length,sizeof(*cube_info->cache));
+ if (cube_info->memory_info == (MemoryInfo *) NULL)
return((CubeInfo *) NULL);
+ cube_info->cache=(ssize_t *) GetVirtualMemoryBlob(cube_info->memory_info);
/*
Initialize color cache.
*/
%
*/
-static inline ssize_t MagickRound(double x)
+static inline double MagickRound(double x)
{
/*
Round the fraction to nearest integer.
*/
- if (x >= 0.0)
- return((ssize_t) (x+0.5));
- return((ssize_t) (x-0.5));
+ if ((x-floor(x)) < (ceil(x)-x))
+ return(floor(x));
+ return(ceil(x));
}
MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels,
depth--;
if ((image->alpha_trait == BlendPixelTrait) && (depth > 5))
depth--;
+ if (IsImageGray(image,exception) != MagickFalse)
+ depth=MaxTreeDepth;
}
/*
Initialize color cube.
% %
% %
% %
++ Q u a n t i z e E r r o r F l a t t e n %
+% %
+% %
+% %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+% QuantizeErrorFlatten() traverses the color cube and flattens the quantization
+% error into a sorted 1D array. This accelerates the color reduction process.
+%
+% Contributed by Yoya.
+%
+% The format of the QuantizeImages method is:
+%
+% size_t QuantizeErrorFlatten(const Image *image,const CubeInfo *cube_info,
+% const NodeInfo *node_info,const ssize_t offset,
+% MagickRealType *quantize_error)
+%
+% A description of each parameter follows.
+%
+% o image: the image.
+%
+% o cube_info: A pointer to the Cube structure.
+%
+% o node_info: pointer to node in color cube tree that is current pointer.
+%
+% o offset: quantize error offset.
+%
+% o quantize_error: the quantization error vector.
+%
+*/
+static size_t QuantizeErrorFlatten(const Image *image,const CubeInfo *cube_info,
+ const NodeInfo *node_info,const ssize_t offset,MagickRealType *quantize_error)
+{
+ register ssize_t
+ i;
+
+ size_t
+ n,
+ number_children;
+
+ if (offset >= (ssize_t) cube_info->nodes)
+ return(0);
+ quantize_error[offset]=node_info->quantize_error;
+ n=1;
+ number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
+ for (i=0; i < (ssize_t) number_children ; i++)
+ if (node_info->child[i] != (NodeInfo *) NULL)
+ n+=QuantizeErrorFlatten(image,cube_info,node_info->child[i],offset+n,
+ quantize_error);
+ return(n);
+}
+\f
+/*
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% %
+% %
+% %
+ R e d u c e %
% %
% %
% o cube_info: A pointer to the Cube structure.
%
*/
+
+static int MagickRealTypeCompare(const void *error_p,const void *error_q)
+{
+ MagickRealType
+ *p,
+ *q;
+
+ p=(MagickRealType *) error_p;
+ q=(MagickRealType *) error_q;
+ if (*p > *q)
+ return(1);
+ if (fabs((double) (*q-*p)) <= MagickEpsilon)
+ return(0);
+ return(-1);
+}
+
static void ReduceImageColors(const Image *image,CubeInfo *cube_info)
{
#define ReduceImageTag "Reduce/Image"
span;
cube_info->next_threshold=0.0;
+ if ((cube_info->colors > cube_info->maximum_colors) &&
+ (cube_info->nodes > 128))
+ {
+ MagickRealType
+ *quantize_error;
+
+ /*
+ Enable rapid reduction of the number of unique colors.
+ */
+ quantize_error=(MagickRealType *) AcquireQuantumMemory(cube_info->nodes,
+ sizeof(*quantize_error));
+ if (quantize_error != (MagickRealType *) NULL)
+ {
+ (void) QuantizeErrorFlatten(image,cube_info,cube_info->root,0,
+ quantize_error);
+ qsort(quantize_error,cube_info->nodes,sizeof(MagickRealType),
+ MagickRealTypeCompare);
+ cube_info->next_threshold=quantize_error[MagickMax(cube_info->nodes-
+ 110*(cube_info->maximum_colors+1)/100,0)];
+ quantize_error=(MagickRealType *) RelinquishMagickMemory(
+ quantize_error);
+ }
+ }
for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; )
{
cube_info->pruning_threshold=cube_info->next_threshold;
image->colormap[i].alpha=(double) i;
qsort((void *) image->colormap,image->colors,sizeof(PixelInfo),
IntensityCompare);
- colormap=(PixelInfo *) AcquireQuantumMemory(image->colors,
- sizeof(*colormap));
+ colormap=(PixelInfo *) AcquireQuantumMemory(image->colors,sizeof(*colormap));
if (colormap == (PixelInfo *) NULL)
ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
image->filename);
projects / imagemagick / blobdiff