blob: 4c7842a82121dc020ada8b617bb6c9fe0394890c [file] [log] [blame]
cristy3ed852e2009-09-05 21:47:34 +00001/*
2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3% %
4% %
5% %
6% QQQ U U AAA N N TTTTT IIIII ZZZZZ EEEEE %
7% Q Q U U A A NN N T I ZZ E %
8% Q Q U U AAAAA N N N T I ZZZ EEEEE %
9% Q QQ U U A A N NN T I ZZ E %
10% QQQQ UUU A A N N T IIIII ZZZZZ EEEEE %
11% %
12% %
13% MagickCore Methods to Reduce the Number of Unique Colors in an Image %
14% %
15% Software Design %
16% John Cristy %
17% July 1992 %
18% %
19% %
cristy45ef08f2012-12-07 13:13:34 +000020% Copyright 1999-2013 ImageMagick Studio LLC, a non-profit organization %
cristy3ed852e2009-09-05 21:47:34 +000021% dedicated to making software imaging solutions freely available. %
22% %
23% You may not use this file except in compliance with the License. You may %
24% obtain a copy of the License at %
25% %
26% http://www.imagemagick.org/script/license.php %
27% %
28% Unless required by applicable law or agreed to in writing, software %
29% distributed under the License is distributed on an "AS IS" BASIS, %
30% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %
31% See the License for the specific language governing permissions and %
32% limitations under the License. %
33% %
34%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35%
36% Realism in computer graphics typically requires using 24 bits/pixel to
37% generate an image. Yet many graphic display devices do not contain the
38% amount of memory necessary to match the spatial and color resolution of
39% the human eye. The Quantize methods takes a 24 bit image and reduces
40% the number of colors so it can be displayed on raster device with less
41% bits per pixel. In most instances, the quantized image closely
42% resembles the original reference image.
43%
44% A reduction of colors in an image is also desirable for image
45% transmission and real-time animation.
46%
47% QuantizeImage() takes a standard RGB or monochrome images and quantizes
48% them down to some fixed number of colors.
49%
50% For purposes of color allocation, an image is a set of n pixels, where
51% each pixel is a point in RGB space. RGB space is a 3-dimensional
52% vector space, and each pixel, Pi, is defined by an ordered triple of
53% red, green, and blue coordinates, (Ri, Gi, Bi).
54%
55% Each primary color component (red, green, or blue) represents an
56% intensity which varies linearly from 0 to a maximum value, Cmax, which
57% corresponds to full saturation of that color. Color allocation is
58% defined over a domain consisting of the cube in RGB space with opposite
59% vertices at (0,0,0) and (Cmax, Cmax, Cmax). QUANTIZE requires Cmax =
60% 255.
61%
62% The algorithm maps this domain onto a tree in which each node
63% represents a cube within that domain. In the following discussion
64% these cubes are defined by the coordinate of two opposite vertices:
65% The vertex nearest the origin in RGB space and the vertex farthest from
66% the origin.
67%
68% The tree's root node represents the entire domain, (0,0,0) through
69% (Cmax,Cmax,Cmax). Each lower level in the tree is generated by
70% subdividing one node's cube into eight smaller cubes of equal size.
71% This corresponds to bisecting the parent cube with planes passing
72% through the midpoints of each edge.
73%
74% The basic algorithm operates in three phases: Classification,
75% Reduction, and Assignment. Classification builds a color description
76% tree for the image. Reduction collapses the tree until the number it
77% represents, at most, the number of colors desired in the output image.
78% Assignment defines the output image's color map and sets each pixel's
79% color by restorage_class in the reduced tree. Our goal is to minimize
80% the numerical discrepancies between the original colors and quantized
81% colors (quantization error).
82%
83% Classification begins by initializing a color description tree of
84% sufficient depth to represent each possible input color in a leaf.
85% However, it is impractical to generate a fully-formed color description
86% tree in the storage_class phase for realistic values of Cmax. If
87% colors components in the input image are quantized to k-bit precision,
88% so that Cmax= 2k-1, the tree would need k levels below the root node to
89% allow representing each possible input color in a leaf. This becomes
90% prohibitive because the tree's total number of nodes is 1 +
91% sum(i=1, k, 8k).
92%
93% A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
94% Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
95% Initializes data structures for nodes only as they are needed; (2)
96% Chooses a maximum depth for the tree as a function of the desired
97% number of colors in the output image (currently log2(colormap size)).
98%
99% For each pixel in the input image, storage_class scans downward from
100% the root of the color description tree. At each level of the tree it
101% identifies the single node which represents a cube in RGB space
102% containing the pixel's color. It updates the following data for each
103% such node:
104%
105% n1: Number of pixels whose color is contained in the RGB cube which
106% this node represents;
107%
108% n2: Number of pixels whose color is not represented in a node at
109% lower depth in the tree; initially, n2 = 0 for all nodes except
110% leaves of the tree.
111%
112% Sr, Sg, Sb: Sums of the red, green, and blue component values for all
113% pixels not classified at a lower depth. The combination of these sums
114% and n2 will ultimately characterize the mean color of a set of
115% pixels represented by this node.
116%
117% E: the distance squared in RGB space between each pixel contained
118% within a node and the nodes' center. This represents the
119% quantization error for a node.
120%
121% Reduction repeatedly prunes the tree until the number of nodes with n2
122% > 0 is less than or equal to the maximum number of colors allowed in
123% the output image. On any given iteration over the tree, it selects
124% those nodes whose E count is minimal for pruning and merges their color
125% statistics upward. It uses a pruning threshold, Ep, to govern node
126% selection as follows:
127%
128% Ep = 0
129% while number of nodes with (n2 > 0) > required maximum number of colors
130% prune all nodes such that E <= Ep
131% Set Ep to minimum E in remaining nodes
132%
133% This has the effect of minimizing any quantization error when merging
134% two nodes together.
135%
136% When a node to be pruned has offspring, the pruning procedure invokes
137% itself recursively in order to prune the tree from the leaves upward.
138% n2, Sr, Sg, and Sb in a node being pruned are always added to the
139% corresponding data in that node's parent. This retains the pruned
140% node's color characteristics for later averaging.
141%
142% For each node, n2 pixels exist for which that node represents the
143% smallest volume in RGB space containing those pixel's colors. When n2
144% > 0 the node will uniquely define a color in the output image. At the
145% beginning of reduction, n2 = 0 for all nodes except a the leaves of
146% the tree which represent colors present in the input image.
147%
148% The other pixel count, n1, indicates the total number of colors within
149% the cubic volume which the node represents. This includes n1 - n2
150% pixels whose colors should be defined by nodes at a lower level in the
151% tree.
152%
153% Assignment generates the output image from the pruned tree. The output
154% image consists of two parts: (1) A color map, which is an array of
155% color descriptions (RGB triples) for each color present in the output
156% image; (2) A pixel array, which represents each pixel as an index
157% into the color map array.
158%
159% First, the assignment phase makes one pass over the pruned color
160% description tree to establish the image's color map. For each node
161% with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean
162% color of all pixels that classify no lower than this node. Each of
163% these colors becomes an entry in the color map.
164%
165% Finally, the assignment phase reclassifies each pixel in the pruned
166% tree to identify the deepest node containing the pixel's color. The
167% pixel's value in the pixel array becomes the index of this node's mean
168% color in the color map.
169%
170% This method is based on a similar algorithm written by Paul Raveling.
171%
172*/
173
174/*
175 Include declarations.
176*/
cristy4c08aed2011-07-01 19:47:50 +0000177#include "MagickCore/studio.h"
178#include "MagickCore/attribute.h"
179#include "MagickCore/cache-view.h"
180#include "MagickCore/color.h"
181#include "MagickCore/color-private.h"
182#include "MagickCore/colormap.h"
183#include "MagickCore/colorspace.h"
cristy510d06a2011-07-06 23:43:54 +0000184#include "MagickCore/colorspace-private.h"
cristy4c08aed2011-07-01 19:47:50 +0000185#include "MagickCore/enhance.h"
186#include "MagickCore/exception.h"
187#include "MagickCore/exception-private.h"
188#include "MagickCore/histogram.h"
189#include "MagickCore/image.h"
190#include "MagickCore/image-private.h"
191#include "MagickCore/list.h"
192#include "MagickCore/memory_.h"
193#include "MagickCore/monitor.h"
194#include "MagickCore/monitor-private.h"
195#include "MagickCore/option.h"
196#include "MagickCore/pixel-accessor.h"
cristy1d1b10f2012-06-02 20:02:55 +0000197#include "MagickCore/pixel-private.h"
cristy4c08aed2011-07-01 19:47:50 +0000198#include "MagickCore/quantize.h"
199#include "MagickCore/quantum.h"
200#include "MagickCore/quantum-private.h"
cristyac245f82012-05-05 17:13:57 +0000201#include "MagickCore/resource_.h"
cristy4c08aed2011-07-01 19:47:50 +0000202#include "MagickCore/string_.h"
203#include "MagickCore/thread-private.h"
cristy3ed852e2009-09-05 21:47:34 +0000204
205/*
206 Define declarations.
207*/
cristye1287512010-06-19 17:38:25 +0000208#if !defined(__APPLE__) && !defined(TARGET_OS_IPHONE)
cristy3ed852e2009-09-05 21:47:34 +0000209#define CacheShift 2
cristye1287512010-06-19 17:38:25 +0000210#else
211#define CacheShift 3
212#endif
cristy3ed852e2009-09-05 21:47:34 +0000213#define ErrorQueueLength 16
214#define MaxNodes 266817
215#define MaxTreeDepth 8
216#define NodesInAList 1920
217
218/*
219 Typdef declarations.
220*/
cristy101ab702011-10-13 13:06:32 +0000221typedef struct _RealPixelInfo
cristy3ed852e2009-09-05 21:47:34 +0000222{
cristya19f1d72012-08-07 18:24:38 +0000223 double
cristy3ed852e2009-09-05 21:47:34 +0000224 red,
225 green,
226 blue,
cristy4c08aed2011-07-01 19:47:50 +0000227 alpha;
cristy101ab702011-10-13 13:06:32 +0000228} RealPixelInfo;
cristy3ed852e2009-09-05 21:47:34 +0000229
230typedef struct _NodeInfo
231{
232 struct _NodeInfo
233 *parent,
234 *child[16];
235
236 MagickSizeType
237 number_unique;
238
cristy101ab702011-10-13 13:06:32 +0000239 RealPixelInfo
cristy3ed852e2009-09-05 21:47:34 +0000240 total_color;
241
cristya19f1d72012-08-07 18:24:38 +0000242 double
cristy3ed852e2009-09-05 21:47:34 +0000243 quantize_error;
244
cristybb503372010-05-27 20:51:26 +0000245 size_t
cristy3ed852e2009-09-05 21:47:34 +0000246 color_number,
247 id,
248 level;
249} NodeInfo;
250
251typedef struct _Nodes
252{
253 NodeInfo
254 *nodes;
255
256 struct _Nodes
257 *next;
258} Nodes;
259
260typedef struct _CubeInfo
261{
262 NodeInfo
263 *root;
264
cristybb503372010-05-27 20:51:26 +0000265 size_t
cristy3ed852e2009-09-05 21:47:34 +0000266 colors,
267 maximum_colors;
268
cristybb503372010-05-27 20:51:26 +0000269 ssize_t
cristy3ed852e2009-09-05 21:47:34 +0000270 transparent_index;
271
272 MagickSizeType
273 transparent_pixels;
274
cristy101ab702011-10-13 13:06:32 +0000275 RealPixelInfo
cristy3ed852e2009-09-05 21:47:34 +0000276 target;
277
cristya19f1d72012-08-07 18:24:38 +0000278 double
cristy3ed852e2009-09-05 21:47:34 +0000279 distance,
280 pruning_threshold,
281 next_threshold;
282
cristybb503372010-05-27 20:51:26 +0000283 size_t
cristy3ed852e2009-09-05 21:47:34 +0000284 nodes,
285 free_nodes,
286 color_number;
287
288 NodeInfo
289 *next_node;
290
291 Nodes
292 *node_queue;
293
cristybb503372010-05-27 20:51:26 +0000294 ssize_t
cristy3ed852e2009-09-05 21:47:34 +0000295 *cache;
296
cristy101ab702011-10-13 13:06:32 +0000297 RealPixelInfo
cristy3ed852e2009-09-05 21:47:34 +0000298 error[ErrorQueueLength];
299
cristya19f1d72012-08-07 18:24:38 +0000300 double
cristy3ed852e2009-09-05 21:47:34 +0000301 weights[ErrorQueueLength];
302
303 QuantizeInfo
304 *quantize_info;
305
306 MagickBooleanType
307 associate_alpha;
308
cristybb503372010-05-27 20:51:26 +0000309 ssize_t
cristy3ed852e2009-09-05 21:47:34 +0000310 x,
311 y;
312
cristybb503372010-05-27 20:51:26 +0000313 size_t
cristy3ed852e2009-09-05 21:47:34 +0000314 depth;
315
316 MagickOffsetType
317 offset;
318
319 MagickSizeType
320 span;
321} CubeInfo;
322
323/*
324 Method prototypes.
325*/
326static CubeInfo
cristybb503372010-05-27 20:51:26 +0000327 *GetCubeInfo(const QuantizeInfo *,const size_t,const size_t);
cristy3ed852e2009-09-05 21:47:34 +0000328
329static NodeInfo
cristybb503372010-05-27 20:51:26 +0000330 *GetNodeInfo(CubeInfo *,const size_t,const size_t,NodeInfo *);
cristy3ed852e2009-09-05 21:47:34 +0000331
332static MagickBooleanType
cristy018f07f2011-09-04 21:15:19 +0000333 AssignImageColors(Image *,CubeInfo *,ExceptionInfo *),
cristy3ed852e2009-09-05 21:47:34 +0000334 ClassifyImageColors(CubeInfo *,const Image *,ExceptionInfo *),
cristy8a11cb12011-10-19 23:53:34 +0000335 DitherImage(Image *,CubeInfo *,ExceptionInfo *),
cristy018f07f2011-09-04 21:15:19 +0000336 SetGrayscaleImage(Image *,ExceptionInfo *);
cristy3ed852e2009-09-05 21:47:34 +0000337
cristybb503372010-05-27 20:51:26 +0000338static size_t
cristy3ed852e2009-09-05 21:47:34 +0000339 DefineImageColormap(Image *,CubeInfo *,NodeInfo *);
340
341static void
342 ClosestColor(const Image *,CubeInfo *,const NodeInfo *),
343 DestroyCubeInfo(CubeInfo *),
344 PruneLevel(const Image *,CubeInfo *,const NodeInfo *),
345 PruneToCubeDepth(const Image *,CubeInfo *,const NodeInfo *),
346 ReduceImageColors(const Image *,CubeInfo *);
347
348/*
349%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
350% %
351% %
352% %
353% A c q u i r e Q u a n t i z e I n f o %
354% %
355% %
356% %
357%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
358%
359% AcquireQuantizeInfo() allocates the QuantizeInfo structure.
360%
361% The format of the AcquireQuantizeInfo method is:
362%
363% QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info)
364%
365% A description of each parameter follows:
366%
367% o image_info: the image info.
368%
369*/
370MagickExport QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info)
371{
372 QuantizeInfo
373 *quantize_info;
374
cristy73bd4a52010-10-05 11:24:23 +0000375 quantize_info=(QuantizeInfo *) AcquireMagickMemory(sizeof(*quantize_info));
cristy3ed852e2009-09-05 21:47:34 +0000376 if (quantize_info == (QuantizeInfo *) NULL)
377 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
378 GetQuantizeInfo(quantize_info);
379 if (image_info != (ImageInfo *) NULL)
380 {
381 const char
382 *option;
383
cristycbda6112012-05-27 20:57:16 +0000384 quantize_info->dither_method=image_info->dither == MagickFalse ?
385 NoDitherMethod : RiemersmaDitherMethod;
cristy3ed852e2009-09-05 21:47:34 +0000386 option=GetImageOption(image_info,"dither");
387 if (option != (const char *) NULL)
cristy042ee782011-04-22 18:48:30 +0000388 quantize_info->dither_method=(DitherMethod) ParseCommandOption(
cristy3ed852e2009-09-05 21:47:34 +0000389 MagickDitherOptions,MagickFalse,option);
390 quantize_info->measure_error=image_info->verbose;
391 }
392 return(quantize_info);
393}
394
395/*
396%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
397% %
398% %
399% %
400+ A s s i g n I m a g e C o l o r s %
401% %
402% %
403% %
404%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
405%
406% AssignImageColors() generates the output image from the pruned tree. The
407% output image consists of two parts: (1) A color map, which is an array
408% of color descriptions (RGB triples) for each color present in the
409% output image; (2) A pixel array, which represents each pixel as an
410% index into the color map array.
411%
412% First, the assignment phase makes one pass over the pruned color
413% description tree to establish the image's color map. For each node
414% with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean
415% color of all pixels that classify no lower than this node. Each of
416% these colors becomes an entry in the color map.
417%
418% Finally, the assignment phase reclassifies each pixel in the pruned
419% tree to identify the deepest node containing the pixel's color. The
420% pixel's value in the pixel array becomes the index of this node's mean
421% color in the color map.
422%
423% The format of the AssignImageColors() method is:
424%
425% MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info)
426%
427% A description of each parameter follows.
428%
429% o image: the image.
430%
431% o cube_info: A pointer to the Cube structure.
432%
433*/
434
cristy4c08aed2011-07-01 19:47:50 +0000435static inline void AssociateAlphaPixel(const Image *image,
cristy101ab702011-10-13 13:06:32 +0000436 const CubeInfo *cube_info,const Quantum *pixel,RealPixelInfo *alpha_pixel)
cristy3ed852e2009-09-05 21:47:34 +0000437{
cristya19f1d72012-08-07 18:24:38 +0000438 double
cristy3ed852e2009-09-05 21:47:34 +0000439 alpha;
440
441 if ((cube_info->associate_alpha == MagickFalse) ||
cristy4c08aed2011-07-01 19:47:50 +0000442 (GetPixelAlpha(image,pixel)== OpaqueAlpha))
cristy3ed852e2009-09-05 21:47:34 +0000443 {
cristya19f1d72012-08-07 18:24:38 +0000444 alpha_pixel->red=(double) GetPixelRed(image,pixel);
445 alpha_pixel->green=(double) GetPixelGreen(image,pixel);
446 alpha_pixel->blue=(double) GetPixelBlue(image,pixel);
447 alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel);
cristy3ed852e2009-09-05 21:47:34 +0000448 return;
449 }
cristya19f1d72012-08-07 18:24:38 +0000450 alpha=(double) (QuantumScale*GetPixelAlpha(image,pixel));
cristy4c08aed2011-07-01 19:47:50 +0000451 alpha_pixel->red=alpha*GetPixelRed(image,pixel);
452 alpha_pixel->green=alpha*GetPixelGreen(image,pixel);
453 alpha_pixel->blue=alpha*GetPixelBlue(image,pixel);
cristya19f1d72012-08-07 18:24:38 +0000454 alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel);
cristy4c08aed2011-07-01 19:47:50 +0000455}
456
cristy101ab702011-10-13 13:06:32 +0000457static inline void AssociateAlphaPixelInfo(const Image *image,
458 const CubeInfo *cube_info,const PixelInfo *pixel,
459 RealPixelInfo *alpha_pixel)
cristy4c08aed2011-07-01 19:47:50 +0000460{
cristya19f1d72012-08-07 18:24:38 +0000461 double
cristy4c08aed2011-07-01 19:47:50 +0000462 alpha;
463
464 if ((cube_info->associate_alpha == MagickFalse) ||
465 (pixel->alpha == OpaqueAlpha))
466 {
cristya19f1d72012-08-07 18:24:38 +0000467 alpha_pixel->red=(double) pixel->red;
468 alpha_pixel->green=(double) pixel->green;
469 alpha_pixel->blue=(double) pixel->blue;
470 alpha_pixel->alpha=(double) pixel->alpha;
cristy4c08aed2011-07-01 19:47:50 +0000471 return;
472 }
cristya19f1d72012-08-07 18:24:38 +0000473 alpha=(double) (QuantumScale*pixel->alpha);
cristy4c08aed2011-07-01 19:47:50 +0000474 alpha_pixel->red=alpha*pixel->red;
475 alpha_pixel->green=alpha*pixel->green;
476 alpha_pixel->blue=alpha*pixel->blue;
cristya19f1d72012-08-07 18:24:38 +0000477 alpha_pixel->alpha=(double) pixel->alpha;
cristy3ed852e2009-09-05 21:47:34 +0000478}
479
cristy6f7e0422012-12-25 20:04:53 +0000480static inline Quantum ClampPixel(const MagickRealType value)
cristy3ed852e2009-09-05 21:47:34 +0000481{
cristy6f7e0422012-12-25 20:04:53 +0000482 if (value < 0.0f)
483 return(0.0f);
484 if (value >= (MagickRealType) QuantumRange)
485 return((Quantum) QuantumRange);
486#if !defined(MAGICKCORE_HDRI_SUPPORT)
487 return((Quantum) (value+0.5f));
488#else
489 return(value);
490#endif
cristy3ed852e2009-09-05 21:47:34 +0000491}
492
cristybb503372010-05-27 20:51:26 +0000493static inline size_t ColorToNodeId(const CubeInfo *cube_info,
cristy101ab702011-10-13 13:06:32 +0000494 const RealPixelInfo *pixel,size_t index)
cristy3ed852e2009-09-05 21:47:34 +0000495{
cristybb503372010-05-27 20:51:26 +0000496 size_t
cristy3ed852e2009-09-05 21:47:34 +0000497 id;
498
cristy6f7e0422012-12-25 20:04:53 +0000499 id=(size_t) (((ScaleQuantumToChar(ClampPixel(pixel->red)) >> index) & 0x01) |
500 ((ScaleQuantumToChar(ClampPixel(pixel->green)) >> index) & 0x01) << 1 |
501 ((ScaleQuantumToChar(ClampPixel(pixel->blue)) >> index) & 0x01) << 2);
cristy3ed852e2009-09-05 21:47:34 +0000502 if (cube_info->associate_alpha != MagickFalse)
cristy6f7e0422012-12-25 20:04:53 +0000503 id|=((ScaleQuantumToChar(ClampPixel(pixel->alpha)) >> index) & 0x1) << 3;
cristy3ed852e2009-09-05 21:47:34 +0000504 return(id);
505}
506
cristy018f07f2011-09-04 21:15:19 +0000507static MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info,
508 ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +0000509{
510#define AssignImageTag "Assign/Image"
511
cristyecc31b12011-02-13 00:32:29 +0000512 ssize_t
cristyecc31b12011-02-13 00:32:29 +0000513 y;
514
cristy3ed852e2009-09-05 21:47:34 +0000515 /*
516 Allocate image colormap.
517 */
518 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
519 (cube_info->quantize_info->colorspace != CMYKColorspace))
520 (void) TransformImageColorspace((Image *) image,
cristye941a752011-10-15 01:52:48 +0000521 cube_info->quantize_info->colorspace,exception);
cristy3ed852e2009-09-05 21:47:34 +0000522 else
cristy3d9f5ba2012-06-26 13:37:31 +0000523 if (IssRGBCompatibleColorspace(image->colorspace) == MagickFalse)
cristyc511e882012-04-16 21:11:14 +0000524 (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception);
cristy018f07f2011-09-04 21:15:19 +0000525 if (AcquireImageColormap(image,cube_info->colors,exception) == MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +0000526 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
527 image->filename);
528 image->colors=0;
529 cube_info->transparent_pixels=0;
530 cube_info->transparent_index=(-1);
531 (void) DefineImageColormap(image,cube_info,cube_info->root);
532 /*
533 Create a reduced color image.
534 */
cristycbda6112012-05-27 20:57:16 +0000535 if ((cube_info->quantize_info->dither_method != NoDitherMethod) &&
cristyd5acfd12010-06-15 00:11:38 +0000536 (cube_info->quantize_info->dither_method != NoDitherMethod))
cristy8a11cb12011-10-19 23:53:34 +0000537 (void) DitherImage(image,cube_info,exception);
cristy3ed852e2009-09-05 21:47:34 +0000538 else
539 {
cristy3ed852e2009-09-05 21:47:34 +0000540 CacheView
541 *image_view;
542
cristye9717ac2011-02-20 16:17:17 +0000543 MagickBooleanType
544 status;
545
546 status=MagickTrue;
cristy46ff2672012-12-14 15:32:26 +0000547 image_view=AcquireAuthenticCacheView(image,exception);
cristye9717ac2011-02-20 16:17:17 +0000548#if defined(MAGICKCORE_OPENMP_SUPPORT)
cristyac245f82012-05-05 17:13:57 +0000549 #pragma omp parallel for schedule(static,4) shared(status) \
cristy5e6b2592012-12-19 14:08:11 +0000550 magick_threads(image,image,image->rows,1)
cristye9717ac2011-02-20 16:17:17 +0000551#endif
cristybb503372010-05-27 20:51:26 +0000552 for (y=0; y < (ssize_t) image->rows; y++)
cristy3ed852e2009-09-05 21:47:34 +0000553 {
cristye9717ac2011-02-20 16:17:17 +0000554 CubeInfo
555 cube;
556
cristy4c08aed2011-07-01 19:47:50 +0000557 register Quantum
cristyc47d1f82009-11-26 01:44:43 +0000558 *restrict q;
cristy3ed852e2009-09-05 21:47:34 +0000559
cristye9717ac2011-02-20 16:17:17 +0000560 register ssize_t
561 x;
562
563 ssize_t
564 count;
565
566 if (status == MagickFalse)
567 continue;
cristy3ed852e2009-09-05 21:47:34 +0000568 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
569 exception);
cristyacd2ed22011-08-30 01:44:23 +0000570 if (q == (Quantum *) NULL)
cristye9717ac2011-02-20 16:17:17 +0000571 {
572 status=MagickFalse;
573 continue;
574 }
cristye9717ac2011-02-20 16:17:17 +0000575 cube=(*cube_info);
cristybb503372010-05-27 20:51:26 +0000576 for (x=0; x < (ssize_t) image->columns; x+=count)
cristy3ed852e2009-09-05 21:47:34 +0000577 {
cristy101ab702011-10-13 13:06:32 +0000578 RealPixelInfo
cristye9717ac2011-02-20 16:17:17 +0000579 pixel;
580
581 register const NodeInfo
582 *node_info;
583
584 register ssize_t
585 i;
586
587 size_t
588 id,
589 index;
590
cristy3ed852e2009-09-05 21:47:34 +0000591 /*
592 Identify the deepest node containing the pixel's color.
593 */
cristybb503372010-05-27 20:51:26 +0000594 for (count=1; (x+count) < (ssize_t) image->columns; count++)
cristy4c08aed2011-07-01 19:47:50 +0000595 {
cristy101ab702011-10-13 13:06:32 +0000596 PixelInfo
cristy4c08aed2011-07-01 19:47:50 +0000597 packet;
598
cristy101ab702011-10-13 13:06:32 +0000599 GetPixelInfoPixel(image,q+count*GetPixelChannels(image),&packet);
cristy4c08aed2011-07-01 19:47:50 +0000600 if (IsPixelEquivalent(image,q,&packet) == MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +0000601 break;
cristy4c08aed2011-07-01 19:47:50 +0000602 }
603 AssociateAlphaPixel(image,&cube,q,&pixel);
cristye9717ac2011-02-20 16:17:17 +0000604 node_info=cube.root;
cristybb503372010-05-27 20:51:26 +0000605 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
cristy3ed852e2009-09-05 21:47:34 +0000606 {
cristye9717ac2011-02-20 16:17:17 +0000607 id=ColorToNodeId(&cube,&pixel,index);
cristy3ed852e2009-09-05 21:47:34 +0000608 if (node_info->child[id] == (NodeInfo *) NULL)
609 break;
610 node_info=node_info->child[id];
611 }
612 /*
613 Find closest color among siblings and their children.
614 */
cristye9717ac2011-02-20 16:17:17 +0000615 cube.target=pixel;
cristya19f1d72012-08-07 18:24:38 +0000616 cube.distance=(double) (4.0*(QuantumRange+1.0)*
cristy3ed852e2009-09-05 21:47:34 +0000617 (QuantumRange+1.0)+1.0);
cristye9717ac2011-02-20 16:17:17 +0000618 ClosestColor(image,&cube,node_info->parent);
619 index=cube.color_number;
cristybb503372010-05-27 20:51:26 +0000620 for (i=0; i < (ssize_t) count; i++)
cristy3ed852e2009-09-05 21:47:34 +0000621 {
622 if (image->storage_class == PseudoClass)
cristy4c08aed2011-07-01 19:47:50 +0000623 SetPixelIndex(image,(Quantum) index,q);
cristye9717ac2011-02-20 16:17:17 +0000624 if (cube.quantize_info->measure_error == MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +0000625 {
cristye42f6582012-02-11 17:59:50 +0000626 SetPixelRed(image,ClampToQuantum(
627 image->colormap[index].red),q);
628 SetPixelGreen(image,ClampToQuantum(
629 image->colormap[index].green),q);
630 SetPixelBlue(image,ClampToQuantum(
631 image->colormap[index].blue),q);
cristye9717ac2011-02-20 16:17:17 +0000632 if (cube.associate_alpha != MagickFalse)
cristye42f6582012-02-11 17:59:50 +0000633 SetPixelAlpha(image,ClampToQuantum(
634 image->colormap[index].alpha),q);
cristy3ed852e2009-09-05 21:47:34 +0000635 }
cristyed231572011-07-14 02:18:59 +0000636 q+=GetPixelChannels(image);
cristy3ed852e2009-09-05 21:47:34 +0000637 }
638 }
639 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
cristye9717ac2011-02-20 16:17:17 +0000640 status=MagickFalse;
641 if (image->progress_monitor != (MagickProgressMonitor) NULL)
642 {
643 MagickBooleanType
644 proceed;
645
646#if defined(MAGICKCORE_OPENMP_SUPPORT)
647 #pragma omp critical (MagickCore_AssignImageColors)
648#endif
649 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y,
650 image->rows);
651 if (proceed == MagickFalse)
652 status=MagickFalse;
653 }
cristy3ed852e2009-09-05 21:47:34 +0000654 }
655 image_view=DestroyCacheView(image_view);
656 }
657 if (cube_info->quantize_info->measure_error != MagickFalse)
cristy8a11cb12011-10-19 23:53:34 +0000658 (void) GetImageQuantizeError(image,exception);
cristy3ed852e2009-09-05 21:47:34 +0000659 if ((cube_info->quantize_info->number_colors == 2) &&
660 (cube_info->quantize_info->colorspace == GRAYColorspace))
661 {
cristye42f6582012-02-11 17:59:50 +0000662 double
cristy3ed852e2009-09-05 21:47:34 +0000663 intensity;
664
cristy101ab702011-10-13 13:06:32 +0000665 register PixelInfo
cristyc47d1f82009-11-26 01:44:43 +0000666 *restrict q;
cristy3ed852e2009-09-05 21:47:34 +0000667
cristye9717ac2011-02-20 16:17:17 +0000668 register ssize_t
669 i;
670
cristy3ed852e2009-09-05 21:47:34 +0000671 /*
672 Monochrome image.
673 */
674 q=image->colormap;
cristybb503372010-05-27 20:51:26 +0000675 for (i=0; i < (ssize_t) image->colors; i++)
cristy3ed852e2009-09-05 21:47:34 +0000676 {
cristya19f1d72012-08-07 18:24:38 +0000677 intensity=(double) ((double) GetPixelInfoIntensity(q) <
678 ((double) QuantumRange/2.0) ? 0 : QuantumRange);
cristy4c08aed2011-07-01 19:47:50 +0000679 q->red=intensity;
680 q->green=intensity;
681 q->blue=intensity;
cristy3ed852e2009-09-05 21:47:34 +0000682 q++;
683 }
684 }
cristyea1a8aa2011-10-20 13:24:06 +0000685 (void) SyncImage(image,exception);
cristy3ed852e2009-09-05 21:47:34 +0000686 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
687 (cube_info->quantize_info->colorspace != CMYKColorspace))
cristyc511e882012-04-16 21:11:14 +0000688 (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception);
cristy3ed852e2009-09-05 21:47:34 +0000689 return(MagickTrue);
690}
691
692/*
693%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
694% %
695% %
696% %
697+ C l a s s i f y I m a g e C o l o r s %
698% %
699% %
700% %
701%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
702%
703% ClassifyImageColors() begins by initializing a color description tree
704% of sufficient depth to represent each possible input color in a leaf.
705% However, it is impractical to generate a fully-formed color
706% description tree in the storage_class phase for realistic values of
707% Cmax. If colors components in the input image are quantized to k-bit
708% precision, so that Cmax= 2k-1, the tree would need k levels below the
709% root node to allow representing each possible input color in a leaf.
710% This becomes prohibitive because the tree's total number of nodes is
711% 1 + sum(i=1,k,8k).
712%
713% A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
714% Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
715% Initializes data structures for nodes only as they are needed; (2)
716% Chooses a maximum depth for the tree as a function of the desired
717% number of colors in the output image (currently log2(colormap size)).
718%
719% For each pixel in the input image, storage_class scans downward from
720% the root of the color description tree. At each level of the tree it
721% identifies the single node which represents a cube in RGB space
722% containing It updates the following data for each such node:
723%
724% n1 : Number of pixels whose color is contained in the RGB cube
725% which this node represents;
726%
727% n2 : Number of pixels whose color is not represented in a node at
728% lower depth in the tree; initially, n2 = 0 for all nodes except
729% leaves of the tree.
730%
731% Sr, Sg, Sb : Sums of the red, green, and blue component values for
732% all pixels not classified at a lower depth. The combination of
733% these sums and n2 will ultimately characterize the mean color of a
734% set of pixels represented by this node.
735%
736% E: the distance squared in RGB space between each pixel contained
737% within a node and the nodes' center. This represents the quantization
738% error for a node.
739%
740% The format of the ClassifyImageColors() method is:
741%
742% MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
743% const Image *image,ExceptionInfo *exception)
744%
745% A description of each parameter follows.
746%
747% o cube_info: A pointer to the Cube structure.
748%
749% o image: the image.
750%
751*/
752
753static inline void SetAssociatedAlpha(const Image *image,CubeInfo *cube_info)
754{
755 MagickBooleanType
756 associate_alpha;
757
cristyb0a657e2012-08-29 00:45:37 +0000758 associate_alpha=image->alpha_trait == BlendPixelTrait ? MagickTrue :
759 MagickFalse;
cristy3ed852e2009-09-05 21:47:34 +0000760 if (cube_info->quantize_info->colorspace == TransparentColorspace)
761 associate_alpha=MagickFalse;
762 if ((cube_info->quantize_info->number_colors == 2) &&
763 (cube_info->quantize_info->colorspace == GRAYColorspace))
764 associate_alpha=MagickFalse;
765 cube_info->associate_alpha=associate_alpha;
766}
767
768static MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
769 const Image *image,ExceptionInfo *exception)
770{
771#define ClassifyImageTag "Classify/Image"
772
cristyc4c8d132010-01-07 01:58:38 +0000773 CacheView
774 *image_view;
775
cristy3ed852e2009-09-05 21:47:34 +0000776 MagickBooleanType
777 proceed;
778
cristya19f1d72012-08-07 18:24:38 +0000779 double
cristy3ed852e2009-09-05 21:47:34 +0000780 bisect;
781
782 NodeInfo
783 *node_info;
784
cristy101ab702011-10-13 13:06:32 +0000785 RealPixelInfo
cristy3ed852e2009-09-05 21:47:34 +0000786 error,
787 mid,
788 midpoint,
789 pixel;
790
791 size_t
cristyecc31b12011-02-13 00:32:29 +0000792 count,
cristy3ed852e2009-09-05 21:47:34 +0000793 id,
794 index,
795 level;
796
cristyecc31b12011-02-13 00:32:29 +0000797 ssize_t
798 y;
799
cristy3ed852e2009-09-05 21:47:34 +0000800 /*
801 Classify the first cube_info->maximum_colors colors to a tree depth of 8.
802 */
803 SetAssociatedAlpha(image,cube_info);
804 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
805 (cube_info->quantize_info->colorspace != CMYKColorspace))
806 (void) TransformImageColorspace((Image *) image,
cristye941a752011-10-15 01:52:48 +0000807 cube_info->quantize_info->colorspace,exception);
cristy3ed852e2009-09-05 21:47:34 +0000808 else
cristy3d9f5ba2012-06-26 13:37:31 +0000809 if (IssRGBCompatibleColorspace(image->colorspace) == MagickFalse)
cristyc511e882012-04-16 21:11:14 +0000810 (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception);
cristya19f1d72012-08-07 18:24:38 +0000811 midpoint.red=(double) QuantumRange/2.0;
812 midpoint.green=(double) QuantumRange/2.0;
813 midpoint.blue=(double) QuantumRange/2.0;
814 midpoint.alpha=(double) QuantumRange/2.0;
cristy4c08aed2011-07-01 19:47:50 +0000815 error.alpha=0.0;
cristy46ff2672012-12-14 15:32:26 +0000816 image_view=AcquireVirtualCacheView(image,exception);
cristybb503372010-05-27 20:51:26 +0000817 for (y=0; y < (ssize_t) image->rows; y++)
cristy3ed852e2009-09-05 21:47:34 +0000818 {
cristy4c08aed2011-07-01 19:47:50 +0000819 register const Quantum
cristyc47d1f82009-11-26 01:44:43 +0000820 *restrict p;
cristy3ed852e2009-09-05 21:47:34 +0000821
cristybb503372010-05-27 20:51:26 +0000822 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +0000823 x;
824
825 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
cristy4c08aed2011-07-01 19:47:50 +0000826 if (p == (const Quantum *) NULL)
cristy3ed852e2009-09-05 21:47:34 +0000827 break;
828 if (cube_info->nodes > MaxNodes)
829 {
830 /*
831 Prune one level if the color tree is too large.
832 */
833 PruneLevel(image,cube_info,cube_info->root);
834 cube_info->depth--;
835 }
cristybb503372010-05-27 20:51:26 +0000836 for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
cristy3ed852e2009-09-05 21:47:34 +0000837 {
838 /*
839 Start at the root and descend the color cube tree.
840 */
cristybb66d9c2010-10-09 01:40:31 +0000841 for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
cristy4c08aed2011-07-01 19:47:50 +0000842 {
cristy101ab702011-10-13 13:06:32 +0000843 PixelInfo
cristy4c08aed2011-07-01 19:47:50 +0000844 packet;
845
cristy101ab702011-10-13 13:06:32 +0000846 GetPixelInfoPixel(image,p+count*GetPixelChannels(image),&packet);
cristy4c08aed2011-07-01 19:47:50 +0000847 if (IsPixelEquivalent(image,p,&packet) == MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +0000848 break;
cristy4c08aed2011-07-01 19:47:50 +0000849 }
850 AssociateAlphaPixel(image,cube_info,p,&pixel);
cristy3ed852e2009-09-05 21:47:34 +0000851 index=MaxTreeDepth-1;
cristya19f1d72012-08-07 18:24:38 +0000852 bisect=((double) QuantumRange+1.0)/2.0;
cristy3ed852e2009-09-05 21:47:34 +0000853 mid=midpoint;
854 node_info=cube_info->root;
855 for (level=1; level <= MaxTreeDepth; level++)
856 {
857 bisect*=0.5;
858 id=ColorToNodeId(cube_info,&pixel,index);
859 mid.red+=(id & 1) != 0 ? bisect : -bisect;
860 mid.green+=(id & 2) != 0 ? bisect : -bisect;
861 mid.blue+=(id & 4) != 0 ? bisect : -bisect;
cristy4c08aed2011-07-01 19:47:50 +0000862 mid.alpha+=(id & 8) != 0 ? bisect : -bisect;
cristy3ed852e2009-09-05 21:47:34 +0000863 if (node_info->child[id] == (NodeInfo *) NULL)
864 {
865 /*
866 Set colors of new node to contain pixel.
867 */
868 node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
869 if (node_info->child[id] == (NodeInfo *) NULL)
870 (void) ThrowMagickException(exception,GetMagickModule(),
anthonye5b39652012-04-21 05:37:29 +0000871 ResourceLimitError,"MemoryAllocationFailed","'%s'",
cristy3ed852e2009-09-05 21:47:34 +0000872 image->filename);
873 if (level == MaxTreeDepth)
874 cube_info->colors++;
875 }
876 /*
877 Approximate the quantization error represented by this node.
878 */
879 node_info=node_info->child[id];
880 error.red=QuantumScale*(pixel.red-mid.red);
881 error.green=QuantumScale*(pixel.green-mid.green);
882 error.blue=QuantumScale*(pixel.blue-mid.blue);
883 if (cube_info->associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +0000884 error.alpha=QuantumScale*(pixel.alpha-mid.alpha);
cristy3ed852e2009-09-05 21:47:34 +0000885 node_info->quantize_error+=sqrt((double) (count*error.red*error.red+
886 count*error.green*error.green+count*error.blue*error.blue+
cristy4c08aed2011-07-01 19:47:50 +0000887 count*error.alpha*error.alpha));
cristy3ed852e2009-09-05 21:47:34 +0000888 cube_info->root->quantize_error+=node_info->quantize_error;
889 index--;
890 }
891 /*
892 Sum RGB for this leaf for later derivation of the mean cube color.
893 */
894 node_info->number_unique+=count;
895 node_info->total_color.red+=count*QuantumScale*pixel.red;
896 node_info->total_color.green+=count*QuantumScale*pixel.green;
897 node_info->total_color.blue+=count*QuantumScale*pixel.blue;
898 if (cube_info->associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +0000899 node_info->total_color.alpha+=count*QuantumScale*pixel.alpha;
cristyed231572011-07-14 02:18:59 +0000900 p+=count*GetPixelChannels(image);
cristy3ed852e2009-09-05 21:47:34 +0000901 }
902 if (cube_info->colors > cube_info->maximum_colors)
903 {
904 PruneToCubeDepth(image,cube_info,cube_info->root);
905 break;
906 }
cristycee97112010-05-28 00:44:52 +0000907 proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
908 image->rows);
cristy3ed852e2009-09-05 21:47:34 +0000909 if (proceed == MagickFalse)
910 break;
911 }
cristybb503372010-05-27 20:51:26 +0000912 for (y++; y < (ssize_t) image->rows; y++)
cristy3ed852e2009-09-05 21:47:34 +0000913 {
cristy4c08aed2011-07-01 19:47:50 +0000914 register const Quantum
cristyc47d1f82009-11-26 01:44:43 +0000915 *restrict p;
cristy3ed852e2009-09-05 21:47:34 +0000916
cristybb503372010-05-27 20:51:26 +0000917 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +0000918 x;
919
920 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
cristy4c08aed2011-07-01 19:47:50 +0000921 if (p == (const Quantum *) NULL)
cristy3ed852e2009-09-05 21:47:34 +0000922 break;
923 if (cube_info->nodes > MaxNodes)
924 {
925 /*
926 Prune one level if the color tree is too large.
927 */
928 PruneLevel(image,cube_info,cube_info->root);
929 cube_info->depth--;
930 }
cristybb503372010-05-27 20:51:26 +0000931 for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
cristy3ed852e2009-09-05 21:47:34 +0000932 {
933 /*
934 Start at the root and descend the color cube tree.
935 */
cristybb66d9c2010-10-09 01:40:31 +0000936 for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
cristy4c08aed2011-07-01 19:47:50 +0000937 {
cristy101ab702011-10-13 13:06:32 +0000938 PixelInfo
cristy4c08aed2011-07-01 19:47:50 +0000939 packet;
940
cristy101ab702011-10-13 13:06:32 +0000941 GetPixelInfoPixel(image,p+count*GetPixelChannels(image),&packet);
cristy4c08aed2011-07-01 19:47:50 +0000942 if (IsPixelEquivalent(image,p,&packet) == MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +0000943 break;
cristy4c08aed2011-07-01 19:47:50 +0000944 }
945 AssociateAlphaPixel(image,cube_info,p,&pixel);
cristy3ed852e2009-09-05 21:47:34 +0000946 index=MaxTreeDepth-1;
cristya19f1d72012-08-07 18:24:38 +0000947 bisect=((double) QuantumRange+1.0)/2.0;
cristy3ed852e2009-09-05 21:47:34 +0000948 mid=midpoint;
949 node_info=cube_info->root;
950 for (level=1; level <= cube_info->depth; level++)
951 {
952 bisect*=0.5;
953 id=ColorToNodeId(cube_info,&pixel,index);
954 mid.red+=(id & 1) != 0 ? bisect : -bisect;
955 mid.green+=(id & 2) != 0 ? bisect : -bisect;
956 mid.blue+=(id & 4) != 0 ? bisect : -bisect;
cristy4c08aed2011-07-01 19:47:50 +0000957 mid.alpha+=(id & 8) != 0 ? bisect : -bisect;
cristy3ed852e2009-09-05 21:47:34 +0000958 if (node_info->child[id] == (NodeInfo *) NULL)
959 {
960 /*
961 Set colors of new node to contain pixel.
962 */
963 node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
964 if (node_info->child[id] == (NodeInfo *) NULL)
965 (void) ThrowMagickException(exception,GetMagickModule(),
966 ResourceLimitError,"MemoryAllocationFailed","%s",
967 image->filename);
968 if (level == cube_info->depth)
969 cube_info->colors++;
970 }
971 /*
972 Approximate the quantization error represented by this node.
973 */
974 node_info=node_info->child[id];
975 error.red=QuantumScale*(pixel.red-mid.red);
976 error.green=QuantumScale*(pixel.green-mid.green);
977 error.blue=QuantumScale*(pixel.blue-mid.blue);
978 if (cube_info->associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +0000979 error.alpha=QuantumScale*(pixel.alpha-mid.alpha);
cristy3ed852e2009-09-05 21:47:34 +0000980 node_info->quantize_error+=sqrt((double) (count*error.red*error.red+
cristy83b6e792011-01-26 15:46:06 +0000981 count*error.green*error.green+count*error.blue*error.blue+
cristy4c08aed2011-07-01 19:47:50 +0000982 count*error.alpha*error.alpha));
cristy3ed852e2009-09-05 21:47:34 +0000983 cube_info->root->quantize_error+=node_info->quantize_error;
984 index--;
985 }
986 /*
987 Sum RGB for this leaf for later derivation of the mean cube color.
988 */
989 node_info->number_unique+=count;
990 node_info->total_color.red+=count*QuantumScale*pixel.red;
991 node_info->total_color.green+=count*QuantumScale*pixel.green;
992 node_info->total_color.blue+=count*QuantumScale*pixel.blue;
993 if (cube_info->associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +0000994 node_info->total_color.alpha+=count*QuantumScale*pixel.alpha;
cristyed231572011-07-14 02:18:59 +0000995 p+=count*GetPixelChannels(image);
cristy3ed852e2009-09-05 21:47:34 +0000996 }
cristycee97112010-05-28 00:44:52 +0000997 proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
998 image->rows);
cristy3ed852e2009-09-05 21:47:34 +0000999 if (proceed == MagickFalse)
1000 break;
1001 }
1002 image_view=DestroyCacheView(image_view);
1003 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
1004 (cube_info->quantize_info->colorspace != CMYKColorspace))
cristyc511e882012-04-16 21:11:14 +00001005 (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception);
cristy3ed852e2009-09-05 21:47:34 +00001006 return(MagickTrue);
1007}
1008
1009/*
1010%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1011% %
1012% %
1013% %
1014% C l o n e Q u a n t i z e I n f o %
1015% %
1016% %
1017% %
1018%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1019%
1020% CloneQuantizeInfo() makes a duplicate of the given quantize info structure,
1021% or if quantize info is NULL, a new one.
1022%
1023% The format of the CloneQuantizeInfo method is:
1024%
1025% QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
1026%
1027% A description of each parameter follows:
1028%
1029% o clone_info: Method CloneQuantizeInfo returns a duplicate of the given
1030% quantize info, or if image info is NULL a new one.
1031%
1032% o quantize_info: a structure of type info.
1033%
1034*/
1035MagickExport QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
1036{
1037 QuantizeInfo
1038 *clone_info;
1039
cristy73bd4a52010-10-05 11:24:23 +00001040 clone_info=(QuantizeInfo *) AcquireMagickMemory(sizeof(*clone_info));
cristy3ed852e2009-09-05 21:47:34 +00001041 if (clone_info == (QuantizeInfo *) NULL)
1042 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1043 GetQuantizeInfo(clone_info);
1044 if (quantize_info == (QuantizeInfo *) NULL)
1045 return(clone_info);
1046 clone_info->number_colors=quantize_info->number_colors;
1047 clone_info->tree_depth=quantize_info->tree_depth;
cristy3ed852e2009-09-05 21:47:34 +00001048 clone_info->dither_method=quantize_info->dither_method;
1049 clone_info->colorspace=quantize_info->colorspace;
1050 clone_info->measure_error=quantize_info->measure_error;
1051 return(clone_info);
1052}
1053
1054/*
1055%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1056% %
1057% %
1058% %
1059+ C l o s e s t C o l o r %
1060% %
1061% %
1062% %
1063%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1064%
1065% ClosestColor() traverses the color cube tree at a particular node and
1066% determines which colormap entry best represents the input color.
1067%
1068% The format of the ClosestColor method is:
1069%
1070% void ClosestColor(const Image *image,CubeInfo *cube_info,
1071% const NodeInfo *node_info)
1072%
1073% A description of each parameter follows.
1074%
1075% o image: the image.
1076%
1077% o cube_info: A pointer to the Cube structure.
1078%
1079% o node_info: the address of a structure of type NodeInfo which points to a
1080% node in the color cube tree that is to be pruned.
1081%
1082*/
1083static void ClosestColor(const Image *image,CubeInfo *cube_info,
1084 const NodeInfo *node_info)
1085{
cristybb503372010-05-27 20:51:26 +00001086 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00001087 i;
1088
cristybb503372010-05-27 20:51:26 +00001089 size_t
cristy3ed852e2009-09-05 21:47:34 +00001090 number_children;
1091
1092 /*
1093 Traverse any children.
1094 */
1095 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
cristybb503372010-05-27 20:51:26 +00001096 for (i=0; i < (ssize_t) number_children; i++)
cristy3ed852e2009-09-05 21:47:34 +00001097 if (node_info->child[i] != (NodeInfo *) NULL)
1098 ClosestColor(image,cube_info,node_info->child[i]);
1099 if (node_info->number_unique != 0)
1100 {
cristya19f1d72012-08-07 18:24:38 +00001101 double
cristy3ed852e2009-09-05 21:47:34 +00001102 pixel;
1103
cristya19f1d72012-08-07 18:24:38 +00001104 register double
cristy3ed852e2009-09-05 21:47:34 +00001105 alpha,
1106 beta,
1107 distance;
1108
cristy101ab702011-10-13 13:06:32 +00001109 register PixelInfo
cristyc47d1f82009-11-26 01:44:43 +00001110 *restrict p;
cristy3ed852e2009-09-05 21:47:34 +00001111
cristy101ab702011-10-13 13:06:32 +00001112 register RealPixelInfo
cristyc47d1f82009-11-26 01:44:43 +00001113 *restrict q;
cristy3ed852e2009-09-05 21:47:34 +00001114
1115 /*
1116 Determine if this color is "closest".
1117 */
1118 p=image->colormap+node_info->color_number;
1119 q=(&cube_info->target);
1120 alpha=1.0;
1121 beta=1.0;
cristy847620f2011-02-09 02:24:21 +00001122 if (cube_info->associate_alpha != MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +00001123 {
cristya19f1d72012-08-07 18:24:38 +00001124 alpha=(double) (QuantumScale*p->alpha);
1125 beta=(double) (QuantumScale*q->alpha);
cristy3ed852e2009-09-05 21:47:34 +00001126 }
cristy4c08aed2011-07-01 19:47:50 +00001127 pixel=alpha*p->red-beta*q->red;
cristy3ed852e2009-09-05 21:47:34 +00001128 distance=pixel*pixel;
cristy36fbc3b2011-02-09 02:30:04 +00001129 if (distance <= cube_info->distance)
cristy3ed852e2009-09-05 21:47:34 +00001130 {
cristy4c08aed2011-07-01 19:47:50 +00001131 pixel=alpha*p->green-beta*q->green;
cristy3ed852e2009-09-05 21:47:34 +00001132 distance+=pixel*pixel;
cristy36fbc3b2011-02-09 02:30:04 +00001133 if (distance <= cube_info->distance)
cristy3ed852e2009-09-05 21:47:34 +00001134 {
cristy4c08aed2011-07-01 19:47:50 +00001135 pixel=alpha*p->blue-beta*q->blue;
cristy3ed852e2009-09-05 21:47:34 +00001136 distance+=pixel*pixel;
cristy36fbc3b2011-02-09 02:30:04 +00001137 if (distance <= cube_info->distance)
cristy3ed852e2009-09-05 21:47:34 +00001138 {
1139 pixel=alpha-beta;
1140 distance+=pixel*pixel;
cristyc4080402011-02-09 02:55:58 +00001141 if (distance <= cube_info->distance)
cristy3ed852e2009-09-05 21:47:34 +00001142 {
1143 cube_info->distance=distance;
1144 cube_info->color_number=node_info->color_number;
1145 }
1146 }
1147 }
1148 }
1149 }
1150}
1151
1152/*
1153%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1154% %
1155% %
1156% %
1157% C o m p r e s s I m a g e C o l o r m a p %
1158% %
1159% %
1160% %
1161%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1162%
1163% CompressImageColormap() compresses an image colormap by removing any
1164% duplicate or unused color entries.
1165%
1166% The format of the CompressImageColormap method is:
1167%
cristy018f07f2011-09-04 21:15:19 +00001168% MagickBooleanType CompressImageColormap(Image *image,
1169% ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00001170%
1171% A description of each parameter follows:
1172%
1173% o image: the image.
1174%
cristy018f07f2011-09-04 21:15:19 +00001175% o exception: return any errors or warnings in this structure.
1176%
cristy3ed852e2009-09-05 21:47:34 +00001177*/
cristy018f07f2011-09-04 21:15:19 +00001178MagickExport MagickBooleanType CompressImageColormap(Image *image,
1179 ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00001180{
1181 QuantizeInfo
1182 quantize_info;
1183
1184 assert(image != (Image *) NULL);
1185 assert(image->signature == MagickSignature);
1186 if (image->debug != MagickFalse)
1187 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
cristy8a11cb12011-10-19 23:53:34 +00001188 if (IsPaletteImage(image,exception) == MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +00001189 return(MagickFalse);
1190 GetQuantizeInfo(&quantize_info);
1191 quantize_info.number_colors=image->colors;
1192 quantize_info.tree_depth=MaxTreeDepth;
cristy018f07f2011-09-04 21:15:19 +00001193 return(QuantizeImage(&quantize_info,image,exception));
cristy3ed852e2009-09-05 21:47:34 +00001194}
1195
1196/*
1197%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1198% %
1199% %
1200% %
1201+ D e f i n e I m a g e C o l o r m a p %
1202% %
1203% %
1204% %
1205%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1206%
1207% DefineImageColormap() traverses the color cube tree and notes each colormap
1208% entry. A colormap entry is any node in the color cube tree where the
1209% of unique colors is not zero. DefineImageColormap() returns the number of
1210% colors in the image colormap.
1211%
1212% The format of the DefineImageColormap method is:
1213%
cristybb503372010-05-27 20:51:26 +00001214% size_t DefineImageColormap(Image *image,CubeInfo *cube_info,
cristy3ed852e2009-09-05 21:47:34 +00001215% NodeInfo *node_info)
1216%
1217% A description of each parameter follows.
1218%
1219% o image: the image.
1220%
1221% o cube_info: A pointer to the Cube structure.
1222%
1223% o node_info: the address of a structure of type NodeInfo which points to a
1224% node in the color cube tree that is to be pruned.
1225%
1226*/
cristybb503372010-05-27 20:51:26 +00001227static size_t DefineImageColormap(Image *image,CubeInfo *cube_info,
cristy3ed852e2009-09-05 21:47:34 +00001228 NodeInfo *node_info)
1229{
cristybb503372010-05-27 20:51:26 +00001230 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00001231 i;
1232
cristybb503372010-05-27 20:51:26 +00001233 size_t
cristy3ed852e2009-09-05 21:47:34 +00001234 number_children;
1235
1236 /*
1237 Traverse any children.
1238 */
1239 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
cristybb503372010-05-27 20:51:26 +00001240 for (i=0; i < (ssize_t) number_children; i++)
cristy3ed852e2009-09-05 21:47:34 +00001241 if (node_info->child[i] != (NodeInfo *) NULL)
cristycee97112010-05-28 00:44:52 +00001242 (void) DefineImageColormap(image,cube_info,node_info->child[i]);
cristy3ed852e2009-09-05 21:47:34 +00001243 if (node_info->number_unique != 0)
1244 {
cristya19f1d72012-08-07 18:24:38 +00001245 register double
cristy3ed852e2009-09-05 21:47:34 +00001246 alpha;
1247
cristy101ab702011-10-13 13:06:32 +00001248 register PixelInfo
cristyc47d1f82009-11-26 01:44:43 +00001249 *restrict q;
cristy3ed852e2009-09-05 21:47:34 +00001250
1251 /*
1252 Colormap entry is defined by the mean color in this cube.
1253 */
1254 q=image->colormap+image->colors;
cristya19f1d72012-08-07 18:24:38 +00001255 alpha=(double) ((MagickOffsetType) node_info->number_unique);
cristy3e3ec3a2012-11-03 23:11:06 +00001256 alpha=PerceptibleReciprocal(alpha);
cristy3ed852e2009-09-05 21:47:34 +00001257 if (cube_info->associate_alpha == MagickFalse)
1258 {
cristy8cd03c32012-07-07 18:57:59 +00001259 q->red=(double) ClampToQuantum(alpha*QuantumRange*
1260 node_info->total_color.red);
1261 q->green=(double) ClampToQuantum(alpha*QuantumRange*
1262 node_info->total_color.green);
1263 q->blue=(double) ClampToQuantum(alpha*(double) QuantumRange*
1264 node_info->total_color.blue);
cristy4c08aed2011-07-01 19:47:50 +00001265 q->alpha=OpaqueAlpha;
cristy3ed852e2009-09-05 21:47:34 +00001266 }
1267 else
1268 {
cristya19f1d72012-08-07 18:24:38 +00001269 double
cristy3ed852e2009-09-05 21:47:34 +00001270 opacity;
1271
cristya19f1d72012-08-07 18:24:38 +00001272 opacity=(double) (alpha*QuantumRange*
cristy4c08aed2011-07-01 19:47:50 +00001273 node_info->total_color.alpha);
cristye42f6582012-02-11 17:59:50 +00001274 q->alpha=(double) ClampToQuantum(opacity);
cristy4c08aed2011-07-01 19:47:50 +00001275 if (q->alpha == OpaqueAlpha)
cristy3ed852e2009-09-05 21:47:34 +00001276 {
cristy8cd03c32012-07-07 18:57:59 +00001277 q->red=(double) ClampToQuantum(alpha*QuantumRange*
1278 node_info->total_color.red);
1279 q->green=(double) ClampToQuantum(alpha*QuantumRange*
1280 node_info->total_color.green);
1281 q->blue=(double) ClampToQuantum(alpha*QuantumRange*
1282 node_info->total_color.blue);
cristy3ed852e2009-09-05 21:47:34 +00001283 }
1284 else
1285 {
cristya19f1d72012-08-07 18:24:38 +00001286 double
cristy3ed852e2009-09-05 21:47:34 +00001287 gamma;
1288
cristya19f1d72012-08-07 18:24:38 +00001289 gamma=(double) (QuantumScale*q->alpha);
cristy3e3ec3a2012-11-03 23:11:06 +00001290 gamma=PerceptibleReciprocal(gamma);
cristy8cd03c32012-07-07 18:57:59 +00001291 q->red=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1292 node_info->total_color.red);
1293 q->green=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1294 node_info->total_color.green);
1295 q->blue=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1296 node_info->total_color.blue);
cristy3ed852e2009-09-05 21:47:34 +00001297 if (node_info->number_unique > cube_info->transparent_pixels)
1298 {
1299 cube_info->transparent_pixels=node_info->number_unique;
cristybb503372010-05-27 20:51:26 +00001300 cube_info->transparent_index=(ssize_t) image->colors;
cristy3ed852e2009-09-05 21:47:34 +00001301 }
1302 }
1303 }
1304 node_info->color_number=image->colors++;
1305 }
1306 return(image->colors);
1307}
1308
1309/*
1310%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1311% %
1312% %
1313% %
1314+ D e s t r o y C u b e I n f o %
1315% %
1316% %
1317% %
1318%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1319%
1320% DestroyCubeInfo() deallocates memory associated with an image.
1321%
1322% The format of the DestroyCubeInfo method is:
1323%
1324% DestroyCubeInfo(CubeInfo *cube_info)
1325%
1326% A description of each parameter follows:
1327%
1328% o cube_info: the address of a structure of type CubeInfo.
1329%
1330*/
1331static void DestroyCubeInfo(CubeInfo *cube_info)
1332{
1333 register Nodes
1334 *nodes;
1335
1336 /*
1337 Release color cube tree storage.
1338 */
1339 do
1340 {
1341 nodes=cube_info->node_queue->next;
1342 cube_info->node_queue->nodes=(NodeInfo *) RelinquishMagickMemory(
1343 cube_info->node_queue->nodes);
1344 cube_info->node_queue=(Nodes *) RelinquishMagickMemory(
1345 cube_info->node_queue);
1346 cube_info->node_queue=nodes;
1347 } while (cube_info->node_queue != (Nodes *) NULL);
cristybb503372010-05-27 20:51:26 +00001348 if (cube_info->cache != (ssize_t *) NULL)
1349 cube_info->cache=(ssize_t *) RelinquishMagickMemory(cube_info->cache);
cristy3ed852e2009-09-05 21:47:34 +00001350 cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info);
1351 cube_info=(CubeInfo *) RelinquishMagickMemory(cube_info);
1352}
1353
1354/*
1355%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1356% %
1357% %
1358% %
1359% D e s t r o y Q u a n t i z e I n f o %
1360% %
1361% %
1362% %
1363%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1364%
1365% DestroyQuantizeInfo() deallocates memory associated with an QuantizeInfo
1366% structure.
1367%
1368% The format of the DestroyQuantizeInfo method is:
1369%
1370% QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1371%
1372% A description of each parameter follows:
1373%
1374% o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1375%
1376*/
1377MagickExport QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1378{
1379 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1380 assert(quantize_info != (QuantizeInfo *) NULL);
1381 assert(quantize_info->signature == MagickSignature);
1382 quantize_info->signature=(~MagickSignature);
1383 quantize_info=(QuantizeInfo *) RelinquishMagickMemory(quantize_info);
1384 return(quantize_info);
1385}
1386
1387/*
1388%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1389% %
1390% %
1391% %
1392+ D i t h e r I m a g e %
1393% %
1394% %
1395% %
1396%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1397%
1398% DitherImage() distributes the difference between an original image and
1399% the corresponding color reduced algorithm to neighboring pixels using
1400% serpentine-scan Floyd-Steinberg error diffusion. DitherImage returns
1401% MagickTrue if the image is dithered otherwise MagickFalse.
1402%
1403% The format of the DitherImage method is:
1404%
cristy8a11cb12011-10-19 23:53:34 +00001405% MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info,
1406% ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00001407%
1408% A description of each parameter follows.
1409%
1410% o image: the image.
1411%
1412% o cube_info: A pointer to the Cube structure.
1413%
cristy8a11cb12011-10-19 23:53:34 +00001414% o exception: return any errors or warnings in this structure.
1415%
cristy3ed852e2009-09-05 21:47:34 +00001416*/
1417
cristy101ab702011-10-13 13:06:32 +00001418static RealPixelInfo **DestroyPixelThreadSet(RealPixelInfo **pixels)
cristye9717ac2011-02-20 16:17:17 +00001419{
1420 register ssize_t
1421 i;
1422
cristy101ab702011-10-13 13:06:32 +00001423 assert(pixels != (RealPixelInfo **) NULL);
cristyac245f82012-05-05 17:13:57 +00001424 for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++)
cristy101ab702011-10-13 13:06:32 +00001425 if (pixels[i] != (RealPixelInfo *) NULL)
1426 pixels[i]=(RealPixelInfo *) RelinquishMagickMemory(pixels[i]);
1427 pixels=(RealPixelInfo **) RelinquishMagickMemory(pixels);
cristye9717ac2011-02-20 16:17:17 +00001428 return(pixels);
1429}
1430
cristy101ab702011-10-13 13:06:32 +00001431static RealPixelInfo **AcquirePixelThreadSet(const size_t count)
cristye9717ac2011-02-20 16:17:17 +00001432{
cristy101ab702011-10-13 13:06:32 +00001433 RealPixelInfo
cristye9717ac2011-02-20 16:17:17 +00001434 **pixels;
1435
1436 register ssize_t
1437 i;
1438
1439 size_t
1440 number_threads;
1441
cristy9357bdd2012-07-30 12:28:34 +00001442 number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
cristy101ab702011-10-13 13:06:32 +00001443 pixels=(RealPixelInfo **) AcquireQuantumMemory(number_threads,
cristye9717ac2011-02-20 16:17:17 +00001444 sizeof(*pixels));
cristy101ab702011-10-13 13:06:32 +00001445 if (pixels == (RealPixelInfo **) NULL)
1446 return((RealPixelInfo **) NULL);
cristye9717ac2011-02-20 16:17:17 +00001447 (void) ResetMagickMemory(pixels,0,number_threads*sizeof(*pixels));
1448 for (i=0; i < (ssize_t) number_threads; i++)
1449 {
cristy101ab702011-10-13 13:06:32 +00001450 pixels[i]=(RealPixelInfo *) AcquireQuantumMemory(count,
cristye9717ac2011-02-20 16:17:17 +00001451 2*sizeof(**pixels));
cristy101ab702011-10-13 13:06:32 +00001452 if (pixels[i] == (RealPixelInfo *) NULL)
cristye9717ac2011-02-20 16:17:17 +00001453 return(DestroyPixelThreadSet(pixels));
1454 }
1455 return(pixels);
1456}
1457
cristyca972de2010-06-20 23:37:02 +00001458static inline ssize_t CacheOffset(CubeInfo *cube_info,
cristy101ab702011-10-13 13:06:32 +00001459 const RealPixelInfo *pixel)
cristyca972de2010-06-20 23:37:02 +00001460{
1461#define RedShift(pixel) (((pixel) >> CacheShift) << (0*(8-CacheShift)))
1462#define GreenShift(pixel) (((pixel) >> CacheShift) << (1*(8-CacheShift)))
1463#define BlueShift(pixel) (((pixel) >> CacheShift) << (2*(8-CacheShift)))
1464#define AlphaShift(pixel) (((pixel) >> CacheShift) << (3*(8-CacheShift)))
1465
1466 ssize_t
1467 offset;
1468
cristy6f7e0422012-12-25 20:04:53 +00001469 offset=(ssize_t) (RedShift(ScaleQuantumToChar(ClampPixel(pixel->red))) |
1470 GreenShift(ScaleQuantumToChar(ClampPixel(pixel->green))) |
1471 BlueShift(ScaleQuantumToChar(ClampPixel(pixel->blue))));
cristyca972de2010-06-20 23:37:02 +00001472 if (cube_info->associate_alpha != MagickFalse)
cristy6f7e0422012-12-25 20:04:53 +00001473 offset|=AlphaShift(ScaleQuantumToChar(ClampPixel(pixel->alpha)));
cristyca972de2010-06-20 23:37:02 +00001474 return(offset);
1475}
1476
cristy8a11cb12011-10-19 23:53:34 +00001477static MagickBooleanType FloydSteinbergDither(Image *image,CubeInfo *cube_info,
1478 ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00001479{
1480#define DitherImageTag "Dither/Image"
1481
cristyc4c8d132010-01-07 01:58:38 +00001482 CacheView
1483 *image_view;
1484
cristy3ed852e2009-09-05 21:47:34 +00001485 MagickBooleanType
cristye9717ac2011-02-20 16:17:17 +00001486 status;
cristy3ed852e2009-09-05 21:47:34 +00001487
cristy101ab702011-10-13 13:06:32 +00001488 RealPixelInfo
cristye9717ac2011-02-20 16:17:17 +00001489 **pixels;
cristy3ed852e2009-09-05 21:47:34 +00001490
cristy847620f2011-02-09 02:24:21 +00001491 ssize_t
cristy847620f2011-02-09 02:24:21 +00001492 y;
1493
cristy3ed852e2009-09-05 21:47:34 +00001494 /*
1495 Distribute quantization error using Floyd-Steinberg.
1496 */
cristye9717ac2011-02-20 16:17:17 +00001497 pixels=AcquirePixelThreadSet(image->columns);
cristy101ab702011-10-13 13:06:32 +00001498 if (pixels == (RealPixelInfo **) NULL)
cristy3ed852e2009-09-05 21:47:34 +00001499 return(MagickFalse);
cristye9717ac2011-02-20 16:17:17 +00001500 status=MagickTrue;
cristy46ff2672012-12-14 15:32:26 +00001501 image_view=AcquireAuthenticCacheView(image,exception);
cristybb503372010-05-27 20:51:26 +00001502 for (y=0; y < (ssize_t) image->rows; y++)
cristy3ed852e2009-09-05 21:47:34 +00001503 {
cristye9717ac2011-02-20 16:17:17 +00001504 const int
1505 id = GetOpenMPThreadId();
1506
1507 CubeInfo
1508 cube;
1509
cristy101ab702011-10-13 13:06:32 +00001510 RealPixelInfo
cristye9717ac2011-02-20 16:17:17 +00001511 *current,
1512 *previous;
1513
cristy4c08aed2011-07-01 19:47:50 +00001514 register Quantum
cristyecc31b12011-02-13 00:32:29 +00001515 *restrict q;
1516
cristybb503372010-05-27 20:51:26 +00001517 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00001518 x;
1519
cristye9717ac2011-02-20 16:17:17 +00001520 size_t
1521 index;
1522
1523 ssize_t
1524 v;
1525
1526 if (status == MagickFalse)
1527 continue;
cristy3ed852e2009-09-05 21:47:34 +00001528 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
cristyacd2ed22011-08-30 01:44:23 +00001529 if (q == (Quantum *) NULL)
cristye9717ac2011-02-20 16:17:17 +00001530 {
1531 status=MagickFalse;
cristy00cbdd62011-02-20 17:29:26 +00001532 continue;
cristye9717ac2011-02-20 16:17:17 +00001533 }
cristyed231572011-07-14 02:18:59 +00001534 q+=(y & 0x01)*image->columns*GetPixelChannels(image);
cristye9717ac2011-02-20 16:17:17 +00001535 cube=(*cube_info);
1536 current=pixels[id]+(y & 0x01)*image->columns;
1537 previous=pixels[id]+((y+1) & 0x01)*image->columns;
cristy4c08aed2011-07-01 19:47:50 +00001538 v=(ssize_t) ((y & 0x01) != 0 ? -1 : 1);
cristybb503372010-05-27 20:51:26 +00001539 for (x=0; x < (ssize_t) image->columns; x++)
cristy3ed852e2009-09-05 21:47:34 +00001540 {
cristy101ab702011-10-13 13:06:32 +00001541 RealPixelInfo
cristye9717ac2011-02-20 16:17:17 +00001542 color,
1543 pixel;
1544
1545 register ssize_t
1546 i;
1547
1548 ssize_t
1549 u;
1550
cristyed231572011-07-14 02:18:59 +00001551 q-=(y & 0x01)*GetPixelChannels(image);
cristy4c08aed2011-07-01 19:47:50 +00001552 u=(y & 0x01) != 0 ? (ssize_t) image->columns-1-x : x;
1553 AssociateAlphaPixel(image,&cube,q,&pixel);
cristy3ed852e2009-09-05 21:47:34 +00001554 if (x > 0)
1555 {
1556 pixel.red+=7*current[u-v].red/16;
1557 pixel.green+=7*current[u-v].green/16;
1558 pixel.blue+=7*current[u-v].blue/16;
cristye9717ac2011-02-20 16:17:17 +00001559 if (cube.associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +00001560 pixel.alpha+=7*current[u-v].alpha/16;
cristy3ed852e2009-09-05 21:47:34 +00001561 }
1562 if (y > 0)
1563 {
cristybb503372010-05-27 20:51:26 +00001564 if (x < (ssize_t) (image->columns-1))
cristy3ed852e2009-09-05 21:47:34 +00001565 {
1566 pixel.red+=previous[u+v].red/16;
1567 pixel.green+=previous[u+v].green/16;
1568 pixel.blue+=previous[u+v].blue/16;
cristye9717ac2011-02-20 16:17:17 +00001569 if (cube.associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +00001570 pixel.alpha+=previous[u+v].alpha/16;
cristy3ed852e2009-09-05 21:47:34 +00001571 }
1572 pixel.red+=5*previous[u].red/16;
1573 pixel.green+=5*previous[u].green/16;
1574 pixel.blue+=5*previous[u].blue/16;
cristye9717ac2011-02-20 16:17:17 +00001575 if (cube.associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +00001576 pixel.alpha+=5*previous[u].alpha/16;
cristy3ed852e2009-09-05 21:47:34 +00001577 if (x > 0)
1578 {
1579 pixel.red+=3*previous[u-v].red/16;
1580 pixel.green+=3*previous[u-v].green/16;
1581 pixel.blue+=3*previous[u-v].blue/16;
cristye9717ac2011-02-20 16:17:17 +00001582 if (cube.associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +00001583 pixel.alpha+=3*previous[u-v].alpha/16;
cristy3ed852e2009-09-05 21:47:34 +00001584 }
1585 }
cristy6f7e0422012-12-25 20:04:53 +00001586 pixel.red=(double) ClampPixel(pixel.red);
1587 pixel.green=(double) ClampPixel(pixel.green);
1588 pixel.blue=(double) ClampPixel(pixel.blue);
cristye9717ac2011-02-20 16:17:17 +00001589 if (cube.associate_alpha != MagickFalse)
cristy6f7e0422012-12-25 20:04:53 +00001590 pixel.alpha=(double) ClampPixel(pixel.alpha);
cristye9717ac2011-02-20 16:17:17 +00001591 i=CacheOffset(&cube,&pixel);
1592 if (cube.cache[i] < 0)
cristy3ed852e2009-09-05 21:47:34 +00001593 {
1594 register NodeInfo
1595 *node_info;
1596
cristybb503372010-05-27 20:51:26 +00001597 register size_t
cristy3ed852e2009-09-05 21:47:34 +00001598 id;
1599
1600 /*
1601 Identify the deepest node containing the pixel's color.
1602 */
cristye9717ac2011-02-20 16:17:17 +00001603 node_info=cube.root;
cristybb503372010-05-27 20:51:26 +00001604 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
cristy3ed852e2009-09-05 21:47:34 +00001605 {
cristye9717ac2011-02-20 16:17:17 +00001606 id=ColorToNodeId(&cube,&pixel,index);
cristy3ed852e2009-09-05 21:47:34 +00001607 if (node_info->child[id] == (NodeInfo *) NULL)
1608 break;
1609 node_info=node_info->child[id];
1610 }
1611 /*
1612 Find closest color among siblings and their children.
1613 */
cristye9717ac2011-02-20 16:17:17 +00001614 cube.target=pixel;
cristya19f1d72012-08-07 18:24:38 +00001615 cube.distance=(double) (4.0*(QuantumRange+1.0)*(QuantumRange+
cristy3ed852e2009-09-05 21:47:34 +00001616 1.0)+1.0);
cristye9717ac2011-02-20 16:17:17 +00001617 ClosestColor(image,&cube,node_info->parent);
1618 cube.cache[i]=(ssize_t) cube.color_number;
cristy3ed852e2009-09-05 21:47:34 +00001619 }
1620 /*
1621 Assign pixel to closest colormap entry.
1622 */
cristye9717ac2011-02-20 16:17:17 +00001623 index=(size_t) cube.cache[i];
cristy3ed852e2009-09-05 21:47:34 +00001624 if (image->storage_class == PseudoClass)
cristy4c08aed2011-07-01 19:47:50 +00001625 SetPixelIndex(image,(Quantum) index,q);
cristye9717ac2011-02-20 16:17:17 +00001626 if (cube.quantize_info->measure_error == MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +00001627 {
cristye42f6582012-02-11 17:59:50 +00001628 SetPixelRed(image,ClampToQuantum(image->colormap[index].red),q);
1629 SetPixelGreen(image,ClampToQuantum(image->colormap[index].green),q);
1630 SetPixelBlue(image,ClampToQuantum(image->colormap[index].blue),q);
cristye9717ac2011-02-20 16:17:17 +00001631 if (cube.associate_alpha != MagickFalse)
cristye42f6582012-02-11 17:59:50 +00001632 SetPixelAlpha(image,ClampToQuantum(image->colormap[index].alpha),q);
cristy3ed852e2009-09-05 21:47:34 +00001633 }
1634 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
cristye9717ac2011-02-20 16:17:17 +00001635 status=MagickFalse;
cristy3ed852e2009-09-05 21:47:34 +00001636 /*
1637 Store the error.
1638 */
cristy101ab702011-10-13 13:06:32 +00001639 AssociateAlphaPixelInfo(image,&cube,image->colormap+index,&color);
cristy3ed852e2009-09-05 21:47:34 +00001640 current[u].red=pixel.red-color.red;
1641 current[u].green=pixel.green-color.green;
1642 current[u].blue=pixel.blue-color.blue;
cristye9717ac2011-02-20 16:17:17 +00001643 if (cube.associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +00001644 current[u].alpha=pixel.alpha-color.alpha;
cristye9717ac2011-02-20 16:17:17 +00001645 if (image->progress_monitor != (MagickProgressMonitor) NULL)
1646 {
1647 MagickBooleanType
1648 proceed;
1649
1650#if defined(MAGICKCORE_OPENMP_SUPPORT)
1651 #pragma omp critical (MagickCore_FloydSteinbergDither)
1652#endif
1653 proceed=SetImageProgress(image,DitherImageTag,(MagickOffsetType) y,
1654 image->rows);
1655 if (proceed == MagickFalse)
1656 status=MagickFalse;
1657 }
cristyed231572011-07-14 02:18:59 +00001658 q+=((y+1) & 0x01)*GetPixelChannels(image);
cristy3ed852e2009-09-05 21:47:34 +00001659 }
1660 }
cristy3ed852e2009-09-05 21:47:34 +00001661 image_view=DestroyCacheView(image_view);
cristye9717ac2011-02-20 16:17:17 +00001662 pixels=DestroyPixelThreadSet(pixels);
cristy3ed852e2009-09-05 21:47:34 +00001663 return(MagickTrue);
1664}
1665
1666static MagickBooleanType
cristy8a11cb12011-10-19 23:53:34 +00001667 RiemersmaDither(Image *,CacheView *,CubeInfo *,const unsigned int,
1668 ExceptionInfo *exception);
cristy3ed852e2009-09-05 21:47:34 +00001669
1670static void Riemersma(Image *image,CacheView *image_view,CubeInfo *cube_info,
cristy8a11cb12011-10-19 23:53:34 +00001671 const size_t level,const unsigned int direction,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00001672{
1673 if (level == 1)
1674 switch (direction)
1675 {
1676 case WestGravity:
1677 {
cristy8a11cb12011-10-19 23:53:34 +00001678 (void) RiemersmaDither(image,image_view,cube_info,EastGravity,
1679 exception);
1680 (void) RiemersmaDither(image,image_view,cube_info,SouthGravity,
1681 exception);
1682 (void) RiemersmaDither(image,image_view,cube_info,WestGravity,
1683 exception);
cristy3ed852e2009-09-05 21:47:34 +00001684 break;
1685 }
1686 case EastGravity:
1687 {
cristy8a11cb12011-10-19 23:53:34 +00001688 (void) RiemersmaDither(image,image_view,cube_info,WestGravity,
1689 exception);
1690 (void) RiemersmaDither(image,image_view,cube_info,NorthGravity,
1691 exception);
1692 (void) RiemersmaDither(image,image_view,cube_info,EastGravity,
1693 exception);
cristy3ed852e2009-09-05 21:47:34 +00001694 break;
1695 }
1696 case NorthGravity:
1697 {
cristy8a11cb12011-10-19 23:53:34 +00001698 (void) RiemersmaDither(image,image_view,cube_info,SouthGravity,
1699 exception);
1700 (void) RiemersmaDither(image,image_view,cube_info,EastGravity,
1701 exception);
1702 (void) RiemersmaDither(image,image_view,cube_info,NorthGravity,
1703 exception);
cristy3ed852e2009-09-05 21:47:34 +00001704 break;
1705 }
1706 case SouthGravity:
1707 {
cristy8a11cb12011-10-19 23:53:34 +00001708 (void) RiemersmaDither(image,image_view,cube_info,NorthGravity,
1709 exception);
1710 (void) RiemersmaDither(image,image_view,cube_info,WestGravity,
1711 exception);
1712 (void) RiemersmaDither(image,image_view,cube_info,SouthGravity,
1713 exception);
cristy3ed852e2009-09-05 21:47:34 +00001714 break;
1715 }
1716 default:
1717 break;
1718 }
1719 else
1720 switch (direction)
1721 {
1722 case WestGravity:
1723 {
cristy8a11cb12011-10-19 23:53:34 +00001724 Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1725 exception);
1726 (void) RiemersmaDither(image,image_view,cube_info,EastGravity,
1727 exception);
1728 Riemersma(image,image_view,cube_info,level-1,WestGravity,
1729 exception);
1730 (void) RiemersmaDither(image,image_view,cube_info,SouthGravity,
1731 exception);
1732 Riemersma(image,image_view,cube_info,level-1,WestGravity,
1733 exception);
1734 (void) RiemersmaDither(image,image_view,cube_info,WestGravity,
1735 exception);
1736 Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1737 exception);
cristy3ed852e2009-09-05 21:47:34 +00001738 break;
1739 }
1740 case EastGravity:
1741 {
cristy8a11cb12011-10-19 23:53:34 +00001742 Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1743 exception);
1744 (void) RiemersmaDither(image,image_view,cube_info,WestGravity,
1745 exception);
1746 Riemersma(image,image_view,cube_info,level-1,EastGravity,
1747 exception);
1748 (void) RiemersmaDither(image,image_view,cube_info,NorthGravity,
1749 exception);
1750 Riemersma(image,image_view,cube_info,level-1,EastGravity,
1751 exception);
1752 (void) RiemersmaDither(image,image_view,cube_info,EastGravity,
1753 exception);
1754 Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1755 exception);
cristy3ed852e2009-09-05 21:47:34 +00001756 break;
1757 }
1758 case NorthGravity:
1759 {
cristy8a11cb12011-10-19 23:53:34 +00001760 Riemersma(image,image_view,cube_info,level-1,WestGravity,
1761 exception);
1762 (void) RiemersmaDither(image,image_view,cube_info,SouthGravity,
1763 exception);
1764 Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1765 exception);
1766 (void) RiemersmaDither(image,image_view,cube_info,EastGravity,
1767 exception);
1768 Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1769 exception);
1770 (void) RiemersmaDither(image,image_view,cube_info,NorthGravity,
1771 exception);
1772 Riemersma(image,image_view,cube_info,level-1,EastGravity,
1773 exception);
cristy3ed852e2009-09-05 21:47:34 +00001774 break;
1775 }
1776 case SouthGravity:
1777 {
cristy8a11cb12011-10-19 23:53:34 +00001778 Riemersma(image,image_view,cube_info,level-1,EastGravity,
1779 exception);
1780 (void) RiemersmaDither(image,image_view,cube_info,NorthGravity,
1781 exception);
1782 Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1783 exception);
1784 (void) RiemersmaDither(image,image_view,cube_info,WestGravity,
1785 exception);
1786 Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1787 exception);
1788 (void) RiemersmaDither(image,image_view,cube_info,SouthGravity,
1789 exception);
1790 Riemersma(image,image_view,cube_info,level-1,WestGravity,
1791 exception);
cristy3ed852e2009-09-05 21:47:34 +00001792 break;
1793 }
1794 default:
1795 break;
1796 }
1797}
1798
1799static MagickBooleanType RiemersmaDither(Image *image,CacheView *image_view,
cristy8a11cb12011-10-19 23:53:34 +00001800 CubeInfo *cube_info,const unsigned int direction,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00001801{
1802#define DitherImageTag "Dither/Image"
1803
1804 MagickBooleanType
1805 proceed;
1806
cristy101ab702011-10-13 13:06:32 +00001807 RealPixelInfo
cristy3ed852e2009-09-05 21:47:34 +00001808 color,
1809 pixel;
1810
1811 register CubeInfo
1812 *p;
1813
cristybb503372010-05-27 20:51:26 +00001814 size_t
cristy3ed852e2009-09-05 21:47:34 +00001815 index;
1816
1817 p=cube_info;
cristybb503372010-05-27 20:51:26 +00001818 if ((p->x >= 0) && (p->x < (ssize_t) image->columns) &&
1819 (p->y >= 0) && (p->y < (ssize_t) image->rows))
cristy3ed852e2009-09-05 21:47:34 +00001820 {
cristy4c08aed2011-07-01 19:47:50 +00001821 register Quantum
cristyc47d1f82009-11-26 01:44:43 +00001822 *restrict q;
cristy3ed852e2009-09-05 21:47:34 +00001823
cristyecc31b12011-02-13 00:32:29 +00001824 register ssize_t
1825 i;
1826
cristy3ed852e2009-09-05 21:47:34 +00001827 /*
1828 Distribute error.
1829 */
cristy3ed852e2009-09-05 21:47:34 +00001830 q=GetCacheViewAuthenticPixels(image_view,p->x,p->y,1,1,exception);
cristyacd2ed22011-08-30 01:44:23 +00001831 if (q == (Quantum *) NULL)
cristy3ed852e2009-09-05 21:47:34 +00001832 return(MagickFalse);
cristy4c08aed2011-07-01 19:47:50 +00001833 AssociateAlphaPixel(image,cube_info,q,&pixel);
cristy3ed852e2009-09-05 21:47:34 +00001834 for (i=0; i < ErrorQueueLength; i++)
1835 {
1836 pixel.red+=p->weights[i]*p->error[i].red;
1837 pixel.green+=p->weights[i]*p->error[i].green;
1838 pixel.blue+=p->weights[i]*p->error[i].blue;
1839 if (cube_info->associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +00001840 pixel.alpha+=p->weights[i]*p->error[i].alpha;
cristy3ed852e2009-09-05 21:47:34 +00001841 }
cristy6f7e0422012-12-25 20:04:53 +00001842 pixel.red=(double) ClampPixel(pixel.red);
1843 pixel.green=(double) ClampPixel(pixel.green);
1844 pixel.blue=(double) ClampPixel(pixel.blue);
cristy3ed852e2009-09-05 21:47:34 +00001845 if (cube_info->associate_alpha != MagickFalse)
cristy6f7e0422012-12-25 20:04:53 +00001846 pixel.alpha=(double) ClampPixel(pixel.alpha);
cristyca972de2010-06-20 23:37:02 +00001847 i=CacheOffset(cube_info,&pixel);
cristy3ed852e2009-09-05 21:47:34 +00001848 if (p->cache[i] < 0)
1849 {
1850 register NodeInfo
1851 *node_info;
1852
cristybb503372010-05-27 20:51:26 +00001853 register size_t
cristy3ed852e2009-09-05 21:47:34 +00001854 id;
1855
1856 /*
1857 Identify the deepest node containing the pixel's color.
1858 */
1859 node_info=p->root;
cristybb503372010-05-27 20:51:26 +00001860 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
cristy3ed852e2009-09-05 21:47:34 +00001861 {
1862 id=ColorToNodeId(cube_info,&pixel,index);
1863 if (node_info->child[id] == (NodeInfo *) NULL)
1864 break;
1865 node_info=node_info->child[id];
1866 }
cristyecc31b12011-02-13 00:32:29 +00001867 node_info=node_info->parent;
cristy3ed852e2009-09-05 21:47:34 +00001868 /*
1869 Find closest color among siblings and their children.
1870 */
1871 p->target=pixel;
cristya19f1d72012-08-07 18:24:38 +00001872 p->distance=(double) (4.0*(QuantumRange+1.0)*((double)
cristy3ed852e2009-09-05 21:47:34 +00001873 QuantumRange+1.0)+1.0);
1874 ClosestColor(image,p,node_info->parent);
cristybb503372010-05-27 20:51:26 +00001875 p->cache[i]=(ssize_t) p->color_number;
cristy3ed852e2009-09-05 21:47:34 +00001876 }
1877 /*
1878 Assign pixel to closest colormap entry.
1879 */
cristy4c08aed2011-07-01 19:47:50 +00001880 index=(size_t) p->cache[i];
cristy3ed852e2009-09-05 21:47:34 +00001881 if (image->storage_class == PseudoClass)
cristy4c08aed2011-07-01 19:47:50 +00001882 SetPixelIndex(image,(Quantum) index,q);
cristy3ed852e2009-09-05 21:47:34 +00001883 if (cube_info->quantize_info->measure_error == MagickFalse)
1884 {
cristye42f6582012-02-11 17:59:50 +00001885 SetPixelRed(image,ClampToQuantum(image->colormap[index].red),q);
1886 SetPixelGreen(image,ClampToQuantum(image->colormap[index].green),q);
1887 SetPixelBlue(image,ClampToQuantum(image->colormap[index].blue),q);
cristy3ed852e2009-09-05 21:47:34 +00001888 if (cube_info->associate_alpha != MagickFalse)
cristye42f6582012-02-11 17:59:50 +00001889 SetPixelAlpha(image,ClampToQuantum(image->colormap[index].alpha),q);
cristy3ed852e2009-09-05 21:47:34 +00001890 }
1891 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1892 return(MagickFalse);
1893 /*
1894 Propagate the error as the last entry of the error queue.
1895 */
1896 (void) CopyMagickMemory(p->error,p->error+1,(ErrorQueueLength-1)*
1897 sizeof(p->error[0]));
cristy101ab702011-10-13 13:06:32 +00001898 AssociateAlphaPixelInfo(image,cube_info,image->colormap+index,&color);
cristy3ed852e2009-09-05 21:47:34 +00001899 p->error[ErrorQueueLength-1].red=pixel.red-color.red;
1900 p->error[ErrorQueueLength-1].green=pixel.green-color.green;
1901 p->error[ErrorQueueLength-1].blue=pixel.blue-color.blue;
1902 if (cube_info->associate_alpha != MagickFalse)
cristy4c08aed2011-07-01 19:47:50 +00001903 p->error[ErrorQueueLength-1].alpha=pixel.alpha-color.alpha;
cristy3ed852e2009-09-05 21:47:34 +00001904 proceed=SetImageProgress(image,DitherImageTag,p->offset,p->span);
1905 if (proceed == MagickFalse)
1906 return(MagickFalse);
1907 p->offset++;
1908 }
1909 switch (direction)
1910 {
1911 case WestGravity: p->x--; break;
1912 case EastGravity: p->x++; break;
1913 case NorthGravity: p->y--; break;
1914 case SouthGravity: p->y++; break;
1915 }
1916 return(MagickTrue);
1917}
1918
cristybb503372010-05-27 20:51:26 +00001919static inline ssize_t MagickMax(const ssize_t x,const ssize_t y)
cristy3ed852e2009-09-05 21:47:34 +00001920{
1921 if (x > y)
1922 return(x);
1923 return(y);
1924}
1925
cristybb503372010-05-27 20:51:26 +00001926static inline ssize_t MagickMin(const ssize_t x,const ssize_t y)
cristy3ed852e2009-09-05 21:47:34 +00001927{
1928 if (x < y)
1929 return(x);
1930 return(y);
1931}
1932
cristy8a11cb12011-10-19 23:53:34 +00001933static MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info,
1934 ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00001935{
cristyc4c8d132010-01-07 01:58:38 +00001936 CacheView
1937 *image_view;
1938
cristy3ed852e2009-09-05 21:47:34 +00001939 MagickBooleanType
1940 status;
1941
cristybb503372010-05-27 20:51:26 +00001942 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00001943 i;
1944
cristybb503372010-05-27 20:51:26 +00001945 size_t
cristy3ed852e2009-09-05 21:47:34 +00001946 depth;
1947
cristyfb7e9cd2011-02-20 16:26:15 +00001948 if (cube_info->quantize_info->dither_method != RiemersmaDitherMethod)
cristy8a11cb12011-10-19 23:53:34 +00001949 return(FloydSteinbergDither(image,cube_info,exception));
cristy3ed852e2009-09-05 21:47:34 +00001950 /*
cristycee97112010-05-28 00:44:52 +00001951 Distribute quantization error along a Hilbert curve.
cristy3ed852e2009-09-05 21:47:34 +00001952 */
1953 (void) ResetMagickMemory(cube_info->error,0,ErrorQueueLength*
1954 sizeof(*cube_info->error));
1955 cube_info->x=0;
1956 cube_info->y=0;
cristybb503372010-05-27 20:51:26 +00001957 i=MagickMax((ssize_t) image->columns,(ssize_t) image->rows);
cristy3ed852e2009-09-05 21:47:34 +00001958 for (depth=1; i != 0; depth++)
1959 i>>=1;
cristybb503372010-05-27 20:51:26 +00001960 if ((ssize_t) (1L << depth) < MagickMax((ssize_t) image->columns,(ssize_t) image->rows))
cristy3ed852e2009-09-05 21:47:34 +00001961 depth++;
1962 cube_info->offset=0;
1963 cube_info->span=(MagickSizeType) image->columns*image->rows;
cristy46ff2672012-12-14 15:32:26 +00001964 image_view=AcquireAuthenticCacheView(image,exception);
cristy3ed852e2009-09-05 21:47:34 +00001965 if (depth > 1)
cristy8a11cb12011-10-19 23:53:34 +00001966 Riemersma(image,image_view,cube_info,depth-1,NorthGravity,exception);
1967 status=RiemersmaDither(image,image_view,cube_info,ForgetGravity,exception);
cristy3ed852e2009-09-05 21:47:34 +00001968 image_view=DestroyCacheView(image_view);
1969 return(status);
1970}
1971
1972/*
1973%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1974% %
1975% %
1976% %
1977+ G e t C u b e I n f o %
1978% %
1979% %
1980% %
1981%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1982%
1983% GetCubeInfo() initialize the Cube data structure.
1984%
1985% The format of the GetCubeInfo method is:
1986%
1987% CubeInfo GetCubeInfo(const QuantizeInfo *quantize_info,
cristybb503372010-05-27 20:51:26 +00001988% const size_t depth,const size_t maximum_colors)
cristy3ed852e2009-09-05 21:47:34 +00001989%
1990% A description of each parameter follows.
1991%
1992% o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1993%
1994% o depth: Normally, this integer value is zero or one. A zero or
1995% one tells Quantize to choose a optimal tree depth of Log4(number_colors).
1996% A tree of this depth generally allows the best representation of the
1997% reference image with the least amount of memory and the fastest
1998% computational speed. In some cases, such as an image with low color
1999% dispersion (a few number of colors), a value other than
2000% Log4(number_colors) is required. To expand the color tree completely,
2001% use a value of 8.
2002%
2003% o maximum_colors: maximum colors.
2004%
2005*/
2006static CubeInfo *GetCubeInfo(const QuantizeInfo *quantize_info,
cristybb503372010-05-27 20:51:26 +00002007 const size_t depth,const size_t maximum_colors)
cristy3ed852e2009-09-05 21:47:34 +00002008{
2009 CubeInfo
2010 *cube_info;
2011
cristya19f1d72012-08-07 18:24:38 +00002012 double
cristy3ed852e2009-09-05 21:47:34 +00002013 sum,
2014 weight;
2015
cristybb503372010-05-27 20:51:26 +00002016 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00002017 i;
2018
cristyecc31b12011-02-13 00:32:29 +00002019 size_t
2020 length;
2021
cristy3ed852e2009-09-05 21:47:34 +00002022 /*
2023 Initialize tree to describe color cube_info.
2024 */
cristy73bd4a52010-10-05 11:24:23 +00002025 cube_info=(CubeInfo *) AcquireMagickMemory(sizeof(*cube_info));
cristy3ed852e2009-09-05 21:47:34 +00002026 if (cube_info == (CubeInfo *) NULL)
2027 return((CubeInfo *) NULL);
2028 (void) ResetMagickMemory(cube_info,0,sizeof(*cube_info));
2029 cube_info->depth=depth;
2030 if (cube_info->depth > MaxTreeDepth)
2031 cube_info->depth=MaxTreeDepth;
2032 if (cube_info->depth < 2)
2033 cube_info->depth=2;
2034 cube_info->maximum_colors=maximum_colors;
2035 /*
2036 Initialize root node.
2037 */
2038 cube_info->root=GetNodeInfo(cube_info,0,0,(NodeInfo *) NULL);
2039 if (cube_info->root == (NodeInfo *) NULL)
2040 return((CubeInfo *) NULL);
2041 cube_info->root->parent=cube_info->root;
2042 cube_info->quantize_info=CloneQuantizeInfo(quantize_info);
cristycbda6112012-05-27 20:57:16 +00002043 if (cube_info->quantize_info->dither_method == NoDitherMethod)
cristy3ed852e2009-09-05 21:47:34 +00002044 return(cube_info);
2045 /*
2046 Initialize dither resources.
2047 */
2048 length=(size_t) (1UL << (4*(8-CacheShift)));
cristybb503372010-05-27 20:51:26 +00002049 cube_info->cache=(ssize_t *) AcquireQuantumMemory(length,
cristy3ed852e2009-09-05 21:47:34 +00002050 sizeof(*cube_info->cache));
cristybb503372010-05-27 20:51:26 +00002051 if (cube_info->cache == (ssize_t *) NULL)
cristy3ed852e2009-09-05 21:47:34 +00002052 return((CubeInfo *) NULL);
2053 /*
2054 Initialize color cache.
2055 */
cristybb503372010-05-27 20:51:26 +00002056 for (i=0; i < (ssize_t) length; i++)
cristy3ed852e2009-09-05 21:47:34 +00002057 cube_info->cache[i]=(-1);
2058 /*
cristycee97112010-05-28 00:44:52 +00002059 Distribute weights along a curve of exponential decay.
cristy3ed852e2009-09-05 21:47:34 +00002060 */
2061 weight=1.0;
2062 for (i=0; i < ErrorQueueLength; i++)
2063 {
cristy3e3ec3a2012-11-03 23:11:06 +00002064 cube_info->weights[ErrorQueueLength-i-1]=PerceptibleReciprocal(weight);
cristy3ed852e2009-09-05 21:47:34 +00002065 weight*=exp(log(((double) QuantumRange+1.0))/(ErrorQueueLength-1.0));
2066 }
2067 /*
2068 Normalize the weighting factors.
2069 */
2070 weight=0.0;
2071 for (i=0; i < ErrorQueueLength; i++)
2072 weight+=cube_info->weights[i];
2073 sum=0.0;
2074 for (i=0; i < ErrorQueueLength; i++)
2075 {
2076 cube_info->weights[i]/=weight;
2077 sum+=cube_info->weights[i];
2078 }
2079 cube_info->weights[0]+=1.0-sum;
2080 return(cube_info);
2081}
2082
2083/*
2084%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2085% %
2086% %
2087% %
2088+ G e t N o d e I n f o %
2089% %
2090% %
2091% %
2092%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2093%
2094% GetNodeInfo() allocates memory for a new node in the color cube tree and
2095% presets all fields to zero.
2096%
2097% The format of the GetNodeInfo method is:
2098%
cristybb503372010-05-27 20:51:26 +00002099% NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id,
2100% const size_t level,NodeInfo *parent)
cristy3ed852e2009-09-05 21:47:34 +00002101%
2102% A description of each parameter follows.
2103%
2104% o node: The GetNodeInfo method returns a pointer to a queue of nodes.
2105%
2106% o id: Specifies the child number of the node.
2107%
2108% o level: Specifies the level in the storage_class the node resides.
2109%
2110*/
cristybb503372010-05-27 20:51:26 +00002111static NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id,
2112 const size_t level,NodeInfo *parent)
cristy3ed852e2009-09-05 21:47:34 +00002113{
2114 NodeInfo
2115 *node_info;
2116
2117 if (cube_info->free_nodes == 0)
2118 {
2119 Nodes
2120 *nodes;
2121
2122 /*
2123 Allocate a new queue of nodes.
2124 */
cristy73bd4a52010-10-05 11:24:23 +00002125 nodes=(Nodes *) AcquireMagickMemory(sizeof(*nodes));
cristy3ed852e2009-09-05 21:47:34 +00002126 if (nodes == (Nodes *) NULL)
2127 return((NodeInfo *) NULL);
2128 nodes->nodes=(NodeInfo *) AcquireQuantumMemory(NodesInAList,
2129 sizeof(*nodes->nodes));
2130 if (nodes->nodes == (NodeInfo *) NULL)
2131 return((NodeInfo *) NULL);
2132 nodes->next=cube_info->node_queue;
2133 cube_info->node_queue=nodes;
2134 cube_info->next_node=nodes->nodes;
2135 cube_info->free_nodes=NodesInAList;
2136 }
2137 cube_info->nodes++;
2138 cube_info->free_nodes--;
2139 node_info=cube_info->next_node++;
2140 (void) ResetMagickMemory(node_info,0,sizeof(*node_info));
2141 node_info->parent=parent;
2142 node_info->id=id;
2143 node_info->level=level;
2144 return(node_info);
2145}
2146
2147/*
2148%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2149% %
2150% %
2151% %
2152% G e t I m a g e Q u a n t i z e E r r o r %
2153% %
2154% %
2155% %
2156%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2157%
2158% GetImageQuantizeError() measures the difference between the original
2159% and quantized images. This difference is the total quantization error.
2160% The error is computed by summing over all pixels in an image the distance
2161% squared in RGB space between each reference pixel value and its quantized
2162% value. These values are computed:
2163%
2164% o mean_error_per_pixel: This value is the mean error for any single
2165% pixel in the image.
2166%
2167% o normalized_mean_square_error: This value is the normalized mean
2168% quantization error for any single pixel in the image. This distance
2169% measure is normalized to a range between 0 and 1. It is independent
2170% of the range of red, green, and blue values in the image.
2171%
2172% o normalized_maximum_square_error: Thsi value is the normalized
2173% maximum quantization error for any single pixel in the image. This
2174% distance measure is normalized to a range between 0 and 1. It is
2175% independent of the range of red, green, and blue values in your image.
2176%
2177% The format of the GetImageQuantizeError method is:
2178%
cristy8a11cb12011-10-19 23:53:34 +00002179% MagickBooleanType GetImageQuantizeError(Image *image,
2180% ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00002181%
2182% A description of each parameter follows.
2183%
2184% o image: the image.
2185%
cristy8a11cb12011-10-19 23:53:34 +00002186% o exception: return any errors or warnings in this structure.
2187%
cristy3ed852e2009-09-05 21:47:34 +00002188*/
cristy8a11cb12011-10-19 23:53:34 +00002189MagickExport MagickBooleanType GetImageQuantizeError(Image *image,
2190 ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00002191{
cristyc4c8d132010-01-07 01:58:38 +00002192 CacheView
2193 *image_view;
2194
cristya19f1d72012-08-07 18:24:38 +00002195 double
cristy3ed852e2009-09-05 21:47:34 +00002196 alpha,
2197 area,
2198 beta,
2199 distance,
2200 maximum_error,
2201 mean_error,
2202 mean_error_per_pixel;
2203
cristybb503372010-05-27 20:51:26 +00002204 size_t
cristy3ed852e2009-09-05 21:47:34 +00002205 index;
2206
cristyecc31b12011-02-13 00:32:29 +00002207 ssize_t
2208 y;
2209
cristy3ed852e2009-09-05 21:47:34 +00002210 assert(image != (Image *) NULL);
2211 assert(image->signature == MagickSignature);
2212 if (image->debug != MagickFalse)
2213 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
cristy8a11cb12011-10-19 23:53:34 +00002214 image->total_colors=GetNumberColors(image,(FILE *) NULL,exception);
cristy3ed852e2009-09-05 21:47:34 +00002215 (void) ResetMagickMemory(&image->error,0,sizeof(image->error));
2216 if (image->storage_class == DirectClass)
2217 return(MagickTrue);
2218 alpha=1.0;
2219 beta=1.0;
2220 area=3.0*image->columns*image->rows;
2221 maximum_error=0.0;
2222 mean_error_per_pixel=0.0;
2223 mean_error=0.0;
cristy46ff2672012-12-14 15:32:26 +00002224 image_view=AcquireVirtualCacheView(image,exception);
cristybb503372010-05-27 20:51:26 +00002225 for (y=0; y < (ssize_t) image->rows; y++)
cristy3ed852e2009-09-05 21:47:34 +00002226 {
cristy4c08aed2011-07-01 19:47:50 +00002227 register const Quantum
cristyc47d1f82009-11-26 01:44:43 +00002228 *restrict p;
cristy3ed852e2009-09-05 21:47:34 +00002229
cristybb503372010-05-27 20:51:26 +00002230 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00002231 x;
2232
2233 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
cristy4c08aed2011-07-01 19:47:50 +00002234 if (p == (const Quantum *) NULL)
cristy3ed852e2009-09-05 21:47:34 +00002235 break;
cristybb503372010-05-27 20:51:26 +00002236 for (x=0; x < (ssize_t) image->columns; x++)
cristy3ed852e2009-09-05 21:47:34 +00002237 {
cristy4c08aed2011-07-01 19:47:50 +00002238 index=1UL*GetPixelIndex(image,p);
cristy8a46d822012-08-28 23:32:39 +00002239 if (image->alpha_trait == BlendPixelTrait)
cristy3ed852e2009-09-05 21:47:34 +00002240 {
cristya19f1d72012-08-07 18:24:38 +00002241 alpha=(double) (QuantumScale*GetPixelAlpha(image,p));
2242 beta=(double) (QuantumScale*image->colormap[index].alpha);
cristy3ed852e2009-09-05 21:47:34 +00002243 }
cristy4c08aed2011-07-01 19:47:50 +00002244 distance=fabs(alpha*GetPixelRed(image,p)-beta*
cristy01e4e7d2011-05-01 23:00:41 +00002245 image->colormap[index].red);
cristy3ed852e2009-09-05 21:47:34 +00002246 mean_error_per_pixel+=distance;
2247 mean_error+=distance*distance;
2248 if (distance > maximum_error)
2249 maximum_error=distance;
cristy4c08aed2011-07-01 19:47:50 +00002250 distance=fabs(alpha*GetPixelGreen(image,p)-beta*
cristy01e4e7d2011-05-01 23:00:41 +00002251 image->colormap[index].green);
cristy3ed852e2009-09-05 21:47:34 +00002252 mean_error_per_pixel+=distance;
2253 mean_error+=distance*distance;
2254 if (distance > maximum_error)
2255 maximum_error=distance;
cristy4c08aed2011-07-01 19:47:50 +00002256 distance=fabs(alpha*GetPixelBlue(image,p)-beta*
cristy01e4e7d2011-05-01 23:00:41 +00002257 image->colormap[index].blue);
cristy3ed852e2009-09-05 21:47:34 +00002258 mean_error_per_pixel+=distance;
2259 mean_error+=distance*distance;
2260 if (distance > maximum_error)
2261 maximum_error=distance;
cristyed231572011-07-14 02:18:59 +00002262 p+=GetPixelChannels(image);
cristy3ed852e2009-09-05 21:47:34 +00002263 }
2264 }
2265 image_view=DestroyCacheView(image_view);
2266 image->error.mean_error_per_pixel=(double) mean_error_per_pixel/area;
2267 image->error.normalized_mean_error=(double) QuantumScale*QuantumScale*
2268 mean_error/area;
2269 image->error.normalized_maximum_error=(double) QuantumScale*maximum_error;
2270 return(MagickTrue);
2271}
2272
2273/*
2274%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2275% %
2276% %
2277% %
2278% G e t Q u a n t i z e I n f o %
2279% %
2280% %
2281% %
2282%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2283%
2284% GetQuantizeInfo() initializes the QuantizeInfo structure.
2285%
2286% The format of the GetQuantizeInfo method is:
2287%
2288% GetQuantizeInfo(QuantizeInfo *quantize_info)
2289%
2290% A description of each parameter follows:
2291%
2292% o quantize_info: Specifies a pointer to a QuantizeInfo structure.
2293%
2294*/
2295MagickExport void GetQuantizeInfo(QuantizeInfo *quantize_info)
2296{
2297 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
2298 assert(quantize_info != (QuantizeInfo *) NULL);
2299 (void) ResetMagickMemory(quantize_info,0,sizeof(*quantize_info));
2300 quantize_info->number_colors=256;
cristy3ed852e2009-09-05 21:47:34 +00002301 quantize_info->dither_method=RiemersmaDitherMethod;
2302 quantize_info->colorspace=UndefinedColorspace;
2303 quantize_info->measure_error=MagickFalse;
2304 quantize_info->signature=MagickSignature;
2305}
2306
2307/*
2308%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2309% %
2310% %
2311% %
cristy018f07f2011-09-04 21:15:19 +00002312% P o s t e r i z e I m a g e %
cristy3ed852e2009-09-05 21:47:34 +00002313% %
2314% %
2315% %
2316%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2317%
2318% PosterizeImage() reduces the image to a limited number of colors for a
2319% "poster" effect.
2320%
2321% The format of the PosterizeImage method is:
2322%
cristybb503372010-05-27 20:51:26 +00002323% MagickBooleanType PosterizeImage(Image *image,const size_t levels,
cristycbda6112012-05-27 20:57:16 +00002324% const DitherMethod dither_method,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00002325%
2326% A description of each parameter follows:
2327%
2328% o image: Specifies a pointer to an Image structure.
2329%
2330% o levels: Number of color levels allowed in each channel. Very low values
2331% (2, 3, or 4) have the most visible effect.
2332%
cristycbda6112012-05-27 20:57:16 +00002333% o dither_method: choose from UndefinedDitherMethod, NoDitherMethod,
2334% RiemersmaDitherMethod, FloydSteinbergDitherMethod.
cristy3ed852e2009-09-05 21:47:34 +00002335%
cristy018f07f2011-09-04 21:15:19 +00002336% o exception: return any errors or warnings in this structure.
2337%
cristy3ed852e2009-09-05 21:47:34 +00002338*/
cristyd1a2c0f2011-02-09 14:14:50 +00002339
cristya19f1d72012-08-07 18:24:38 +00002340static inline ssize_t MagickRound(double x)
cristy4d727152011-02-10 19:57:21 +00002341{
2342 /*
cristyecc31b12011-02-13 00:32:29 +00002343 Round the fraction to nearest integer.
cristy4d727152011-02-10 19:57:21 +00002344 */
2345 if (x >= 0.0)
2346 return((ssize_t) (x+0.5));
2347 return((ssize_t) (x-0.5));
2348}
2349
cristyd1a2c0f2011-02-09 14:14:50 +00002350MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels,
cristycbda6112012-05-27 20:57:16 +00002351 const DitherMethod dither_method,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00002352{
cristyd1a2c0f2011-02-09 14:14:50 +00002353#define PosterizeImageTag "Posterize/Image"
cristy4d727152011-02-10 19:57:21 +00002354#define PosterizePixel(pixel) (Quantum) (QuantumRange*(MagickRound( \
cristy3e9cad02011-02-20 01:42:00 +00002355 QuantumScale*pixel*(levels-1)))/MagickMax((ssize_t) levels-1,1))
cristyd1a2c0f2011-02-09 14:14:50 +00002356
cristyc4c8d132010-01-07 01:58:38 +00002357 CacheView
cristyd1a2c0f2011-02-09 14:14:50 +00002358 *image_view;
cristyc4c8d132010-01-07 01:58:38 +00002359
cristy3ed852e2009-09-05 21:47:34 +00002360 MagickBooleanType
2361 status;
2362
cristyd1a2c0f2011-02-09 14:14:50 +00002363 MagickOffsetType
2364 progress;
2365
cristy3ed852e2009-09-05 21:47:34 +00002366 QuantizeInfo
2367 *quantize_info;
2368
cristy847620f2011-02-09 02:24:21 +00002369 register ssize_t
2370 i;
2371
cristy847620f2011-02-09 02:24:21 +00002372 ssize_t
cristyd1a2c0f2011-02-09 14:14:50 +00002373 y;
cristy847620f2011-02-09 02:24:21 +00002374
cristy3ed852e2009-09-05 21:47:34 +00002375 assert(image != (Image *) NULL);
2376 assert(image->signature == MagickSignature);
2377 if (image->debug != MagickFalse)
2378 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
cristyd1a2c0f2011-02-09 14:14:50 +00002379 if (image->storage_class == PseudoClass)
2380#if defined(MAGICKCORE_OPENMP_SUPPORT)
cristyac245f82012-05-05 17:13:57 +00002381 #pragma omp parallel for schedule(static,4) shared(progress,status) \
cristy5e6b2592012-12-19 14:08:11 +00002382 magick_threads(image,image,image->colors,1)
cristyd1a2c0f2011-02-09 14:14:50 +00002383#endif
2384 for (i=0; i < (ssize_t) image->colors; i++)
cristy3ed852e2009-09-05 21:47:34 +00002385 {
cristyd1a2c0f2011-02-09 14:14:50 +00002386 /*
2387 Posterize colormap.
2388 */
cristyed231572011-07-14 02:18:59 +00002389 if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0)
cristye42f6582012-02-11 17:59:50 +00002390 image->colormap[i].red=(double)
2391 PosterizePixel(image->colormap[i].red);
cristyed231572011-07-14 02:18:59 +00002392 if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0)
cristye42f6582012-02-11 17:59:50 +00002393 image->colormap[i].green=(double)
2394 PosterizePixel(image->colormap[i].green);
cristyed231572011-07-14 02:18:59 +00002395 if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0)
cristye42f6582012-02-11 17:59:50 +00002396 image->colormap[i].blue=(double)
2397 PosterizePixel(image->colormap[i].blue);
cristyed231572011-07-14 02:18:59 +00002398 if ((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0)
cristye42f6582012-02-11 17:59:50 +00002399 image->colormap[i].alpha=(double)
2400 PosterizePixel(image->colormap[i].alpha);
cristy3ed852e2009-09-05 21:47:34 +00002401 }
cristyd1a2c0f2011-02-09 14:14:50 +00002402 /*
2403 Posterize image.
2404 */
2405 status=MagickTrue;
2406 progress=0;
cristy46ff2672012-12-14 15:32:26 +00002407 image_view=AcquireAuthenticCacheView(image,exception);
cristyd1a2c0f2011-02-09 14:14:50 +00002408#if defined(MAGICKCORE_OPENMP_SUPPORT)
cristyac245f82012-05-05 17:13:57 +00002409 #pragma omp parallel for schedule(static,4) shared(progress,status) \
cristy5e6b2592012-12-19 14:08:11 +00002410 magick_threads(image,image,image->rows,1)
cristyd1a2c0f2011-02-09 14:14:50 +00002411#endif
2412 for (y=0; y < (ssize_t) image->rows; y++)
2413 {
cristy4c08aed2011-07-01 19:47:50 +00002414 register Quantum
cristyd1a2c0f2011-02-09 14:14:50 +00002415 *restrict q;
2416
2417 register ssize_t
2418 x;
2419
2420 if (status == MagickFalse)
2421 continue;
2422 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
cristyacd2ed22011-08-30 01:44:23 +00002423 if (q == (Quantum *) NULL)
cristy3ed852e2009-09-05 21:47:34 +00002424 {
cristyd1a2c0f2011-02-09 14:14:50 +00002425 status=MagickFalse;
2426 continue;
cristy3ed852e2009-09-05 21:47:34 +00002427 }
cristyd1a2c0f2011-02-09 14:14:50 +00002428 for (x=0; x < (ssize_t) image->columns; x++)
cristy3ed852e2009-09-05 21:47:34 +00002429 {
cristyed231572011-07-14 02:18:59 +00002430 if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0)
cristy4c08aed2011-07-01 19:47:50 +00002431 SetPixelRed(image,PosterizePixel(GetPixelRed(image,q)),q);
cristyed231572011-07-14 02:18:59 +00002432 if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0)
cristy4c08aed2011-07-01 19:47:50 +00002433 SetPixelGreen(image,PosterizePixel(GetPixelGreen(image,q)),q);
cristyed231572011-07-14 02:18:59 +00002434 if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0)
cristy4c08aed2011-07-01 19:47:50 +00002435 SetPixelBlue(image,PosterizePixel(GetPixelBlue(image,q)),q);
cristyed231572011-07-14 02:18:59 +00002436 if (((GetPixelBlackTraits(image) & UpdatePixelTrait) != 0) &&
cristy4c08aed2011-07-01 19:47:50 +00002437 (image->colorspace == CMYKColorspace))
2438 SetPixelBlack(image,PosterizePixel(GetPixelBlack(image,q)),q);
cristyed231572011-07-14 02:18:59 +00002439 if (((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0) &&
cristy8a46d822012-08-28 23:32:39 +00002440 (image->alpha_trait == BlendPixelTrait))
cristy4c08aed2011-07-01 19:47:50 +00002441 SetPixelAlpha(image,PosterizePixel(GetPixelAlpha(image,q)),q);
cristyed231572011-07-14 02:18:59 +00002442 q+=GetPixelChannels(image);
cristy3ed852e2009-09-05 21:47:34 +00002443 }
cristyd1a2c0f2011-02-09 14:14:50 +00002444 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2445 status=MagickFalse;
2446 if (image->progress_monitor != (MagickProgressMonitor) NULL)
2447 {
2448 MagickBooleanType
2449 proceed;
2450
2451#if defined(MAGICKCORE_OPENMP_SUPPORT)
cristy13020672011-07-08 02:33:26 +00002452 #pragma omp critical (MagickCore_PosterizeImage)
cristyd1a2c0f2011-02-09 14:14:50 +00002453#endif
2454 proceed=SetImageProgress(image,PosterizeImageTag,progress++,
2455 image->rows);
2456 if (proceed == MagickFalse)
2457 status=MagickFalse;
2458 }
2459 }
2460 image_view=DestroyCacheView(image_view);
cristy3ed852e2009-09-05 21:47:34 +00002461 quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL);
cristyd1a2c0f2011-02-09 14:14:50 +00002462 quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels*
2463 levels,MaxColormapSize+1);
cristycbda6112012-05-27 20:57:16 +00002464 quantize_info->dither_method=dither_method;
cristy3e9cad02011-02-20 01:42:00 +00002465 quantize_info->tree_depth=MaxTreeDepth;
cristy018f07f2011-09-04 21:15:19 +00002466 status=QuantizeImage(quantize_info,image,exception);
cristy3ed852e2009-09-05 21:47:34 +00002467 quantize_info=DestroyQuantizeInfo(quantize_info);
cristy3ed852e2009-09-05 21:47:34 +00002468 return(status);
2469}
2470
2471/*
2472%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2473% %
2474% %
2475% %
2476+ P r u n e C h i l d %
2477% %
2478% %
2479% %
2480%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2481%
2482% PruneChild() deletes the given node and merges its statistics into its
2483% parent.
2484%
2485% The format of the PruneSubtree method is:
2486%
2487% PruneChild(const Image *image,CubeInfo *cube_info,
2488% const NodeInfo *node_info)
2489%
2490% A description of each parameter follows.
2491%
2492% o image: the image.
2493%
2494% o cube_info: A pointer to the Cube structure.
2495%
2496% o node_info: pointer to node in color cube tree that is to be pruned.
2497%
2498*/
2499static void PruneChild(const Image *image,CubeInfo *cube_info,
2500 const NodeInfo *node_info)
2501{
2502 NodeInfo
2503 *parent;
2504
cristybb503372010-05-27 20:51:26 +00002505 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00002506 i;
2507
cristybb503372010-05-27 20:51:26 +00002508 size_t
cristy3ed852e2009-09-05 21:47:34 +00002509 number_children;
2510
2511 /*
2512 Traverse any children.
2513 */
2514 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
cristybb503372010-05-27 20:51:26 +00002515 for (i=0; i < (ssize_t) number_children; i++)
cristy3ed852e2009-09-05 21:47:34 +00002516 if (node_info->child[i] != (NodeInfo *) NULL)
2517 PruneChild(image,cube_info,node_info->child[i]);
2518 /*
2519 Merge color statistics into parent.
2520 */
2521 parent=node_info->parent;
2522 parent->number_unique+=node_info->number_unique;
2523 parent->total_color.red+=node_info->total_color.red;
2524 parent->total_color.green+=node_info->total_color.green;
2525 parent->total_color.blue+=node_info->total_color.blue;
cristy4c08aed2011-07-01 19:47:50 +00002526 parent->total_color.alpha+=node_info->total_color.alpha;
cristy3ed852e2009-09-05 21:47:34 +00002527 parent->child[node_info->id]=(NodeInfo *) NULL;
2528 cube_info->nodes--;
2529}
2530
2531/*
2532%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2533% %
2534% %
2535% %
2536+ P r u n e L e v e l %
2537% %
2538% %
2539% %
2540%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2541%
2542% PruneLevel() deletes all nodes at the bottom level of the color tree merging
2543% their color statistics into their parent node.
2544%
2545% The format of the PruneLevel method is:
2546%
2547% PruneLevel(const Image *image,CubeInfo *cube_info,
2548% const NodeInfo *node_info)
2549%
2550% A description of each parameter follows.
2551%
2552% o image: the image.
2553%
2554% o cube_info: A pointer to the Cube structure.
2555%
2556% o node_info: pointer to node in color cube tree that is to be pruned.
2557%
2558*/
2559static void PruneLevel(const Image *image,CubeInfo *cube_info,
2560 const NodeInfo *node_info)
2561{
cristybb503372010-05-27 20:51:26 +00002562 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00002563 i;
2564
cristybb503372010-05-27 20:51:26 +00002565 size_t
cristy3ed852e2009-09-05 21:47:34 +00002566 number_children;
2567
2568 /*
2569 Traverse any children.
2570 */
2571 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
cristybb503372010-05-27 20:51:26 +00002572 for (i=0; i < (ssize_t) number_children; i++)
cristy3ed852e2009-09-05 21:47:34 +00002573 if (node_info->child[i] != (NodeInfo *) NULL)
2574 PruneLevel(image,cube_info,node_info->child[i]);
2575 if (node_info->level == cube_info->depth)
2576 PruneChild(image,cube_info,node_info);
2577}
2578
2579/*
2580%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2581% %
2582% %
2583% %
2584+ P r u n e T o C u b e D e p t h %
2585% %
2586% %
2587% %
2588%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2589%
2590% PruneToCubeDepth() deletes any nodes at a depth greater than
2591% cube_info->depth while merging their color statistics into their parent
2592% node.
2593%
2594% The format of the PruneToCubeDepth method is:
2595%
2596% PruneToCubeDepth(const Image *image,CubeInfo *cube_info,
2597% const NodeInfo *node_info)
2598%
2599% A description of each parameter follows.
2600%
2601% o cube_info: A pointer to the Cube structure.
2602%
2603% o node_info: pointer to node in color cube tree that is to be pruned.
2604%
2605*/
2606static void PruneToCubeDepth(const Image *image,CubeInfo *cube_info,
2607 const NodeInfo *node_info)
2608{
cristybb503372010-05-27 20:51:26 +00002609 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00002610 i;
2611
cristybb503372010-05-27 20:51:26 +00002612 size_t
cristy3ed852e2009-09-05 21:47:34 +00002613 number_children;
2614
2615 /*
2616 Traverse any children.
2617 */
2618 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
cristybb503372010-05-27 20:51:26 +00002619 for (i=0; i < (ssize_t) number_children; i++)
cristy3ed852e2009-09-05 21:47:34 +00002620 if (node_info->child[i] != (NodeInfo *) NULL)
2621 PruneToCubeDepth(image,cube_info,node_info->child[i]);
2622 if (node_info->level > cube_info->depth)
2623 PruneChild(image,cube_info,node_info);
2624}
2625
2626/*
2627%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2628% %
2629% %
2630% %
2631% Q u a n t i z e I m a g e %
2632% %
2633% %
2634% %
2635%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2636%
2637% QuantizeImage() analyzes the colors within a reference image and chooses a
2638% fixed number of colors to represent the image. The goal of the algorithm
2639% is to minimize the color difference between the input and output image while
2640% minimizing the processing time.
2641%
2642% The format of the QuantizeImage method is:
2643%
2644% MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
cristy018f07f2011-09-04 21:15:19 +00002645% Image *image,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00002646%
2647% A description of each parameter follows:
2648%
2649% o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2650%
2651% o image: the image.
2652%
cristy018f07f2011-09-04 21:15:19 +00002653% o exception: return any errors or warnings in this structure.
2654%
cristy3ed852e2009-09-05 21:47:34 +00002655*/
cristy5f7dca62011-08-12 12:38:05 +00002656
2657static MagickBooleanType DirectToColormapImage(Image *image,
2658 ExceptionInfo *exception)
2659{
2660 CacheView
2661 *image_view;
2662
2663 MagickBooleanType
2664 status;
2665
2666 register ssize_t
2667 i;
2668
2669 size_t
2670 number_colors;
2671
2672 ssize_t
2673 y;
2674
2675 status=MagickTrue;
2676 number_colors=(size_t) (image->columns*image->rows);
cristy018f07f2011-09-04 21:15:19 +00002677 if (AcquireImageColormap(image,number_colors,exception) == MagickFalse)
cristy5f7dca62011-08-12 12:38:05 +00002678 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
2679 image->filename);
2680 if (image->colors != number_colors)
2681 return(MagickFalse);
2682 i=0;
cristy46ff2672012-12-14 15:32:26 +00002683 image_view=AcquireAuthenticCacheView(image,exception);
cristy5f7dca62011-08-12 12:38:05 +00002684 for (y=0; y < (ssize_t) image->rows; y++)
2685 {
2686 MagickBooleanType
2687 proceed;
2688
2689 register Quantum
2690 *restrict q;
2691
2692 register ssize_t
2693 x;
2694
2695 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2696 if (q == (Quantum *) NULL)
2697 break;
2698 for (x=0; x < (ssize_t) image->columns; x++)
2699 {
cristye42f6582012-02-11 17:59:50 +00002700 image->colormap[i].red=(double) GetPixelRed(image,q);
2701 image->colormap[i].green=(double) GetPixelGreen(image,q);
2702 image->colormap[i].blue=(double) GetPixelBlue(image,q);
2703 image->colormap[i].alpha=(double) GetPixelAlpha(image,q);
cristy5f7dca62011-08-12 12:38:05 +00002704 SetPixelIndex(image,(Quantum) i,q);
2705 i++;
2706 q+=GetPixelChannels(image);
2707 }
2708 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2709 break;
2710 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y,
2711 image->rows);
2712 if (proceed == MagickFalse)
2713 status=MagickFalse;
2714 }
2715 image_view=DestroyCacheView(image_view);
2716 return(status);
2717}
2718
cristy3ed852e2009-09-05 21:47:34 +00002719MagickExport MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
cristy018f07f2011-09-04 21:15:19 +00002720 Image *image,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00002721{
2722 CubeInfo
2723 *cube_info;
2724
2725 MagickBooleanType
2726 status;
2727
cristybb503372010-05-27 20:51:26 +00002728 size_t
cristy3ed852e2009-09-05 21:47:34 +00002729 depth,
2730 maximum_colors;
2731
2732 assert(quantize_info != (const QuantizeInfo *) NULL);
2733 assert(quantize_info->signature == MagickSignature);
2734 assert(image != (Image *) NULL);
2735 assert(image->signature == MagickSignature);
2736 if (image->debug != MagickFalse)
2737 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2738 maximum_colors=quantize_info->number_colors;
2739 if (maximum_colors == 0)
2740 maximum_colors=MaxColormapSize;
2741 if (maximum_colors > MaxColormapSize)
2742 maximum_colors=MaxColormapSize;
cristy8a46d822012-08-28 23:32:39 +00002743 if (image->alpha_trait != BlendPixelTrait)
cristy400e7012012-08-08 13:41:59 +00002744 {
2745 if ((image->columns*image->rows) <= maximum_colors)
2746 (void) DirectToColormapImage(image,exception);
cristyaeded782012-09-11 23:39:36 +00002747 if (IsImageGray(image,exception) != MagickFalse)
cristy400e7012012-08-08 13:41:59 +00002748 (void) SetGrayscaleImage(image,exception);
2749 }
cristy3ed852e2009-09-05 21:47:34 +00002750 if ((image->storage_class == PseudoClass) &&
2751 (image->colors <= maximum_colors))
2752 return(MagickTrue);
2753 depth=quantize_info->tree_depth;
2754 if (depth == 0)
2755 {
cristybb503372010-05-27 20:51:26 +00002756 size_t
cristy3ed852e2009-09-05 21:47:34 +00002757 colors;
2758
2759 /*
2760 Depth of color tree is: Log4(colormap size)+2.
2761 */
2762 colors=maximum_colors;
2763 for (depth=1; colors != 0; depth++)
2764 colors>>=2;
cristycbda6112012-05-27 20:57:16 +00002765 if ((quantize_info->dither_method != NoDitherMethod) && (depth > 2))
cristy3ed852e2009-09-05 21:47:34 +00002766 depth--;
cristy8a46d822012-08-28 23:32:39 +00002767 if ((image->alpha_trait == BlendPixelTrait) && (depth > 5))
cristy3ed852e2009-09-05 21:47:34 +00002768 depth--;
2769 }
2770 /*
2771 Initialize color cube.
2772 */
2773 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2774 if (cube_info == (CubeInfo *) NULL)
2775 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
2776 image->filename);
cristy8a11cb12011-10-19 23:53:34 +00002777 status=ClassifyImageColors(cube_info,image,exception);
cristy3ed852e2009-09-05 21:47:34 +00002778 if (status != MagickFalse)
2779 {
2780 /*
2781 Reduce the number of colors in the image.
2782 */
2783 ReduceImageColors(image,cube_info);
cristy018f07f2011-09-04 21:15:19 +00002784 status=AssignImageColors(image,cube_info,exception);
cristy3ed852e2009-09-05 21:47:34 +00002785 }
2786 DestroyCubeInfo(cube_info);
2787 return(status);
2788}
2789
2790/*
2791%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2792% %
2793% %
2794% %
2795% Q u a n t i z e I m a g e s %
2796% %
2797% %
2798% %
2799%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2800%
2801% QuantizeImages() analyzes the colors within a set of reference images and
2802% chooses a fixed number of colors to represent the set. The goal of the
2803% algorithm is to minimize the color difference between the input and output
2804% images while minimizing the processing time.
2805%
2806% The format of the QuantizeImages method is:
2807%
2808% MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
cristy018f07f2011-09-04 21:15:19 +00002809% Image *images,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00002810%
2811% A description of each parameter follows:
2812%
2813% o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2814%
2815% o images: Specifies a pointer to a list of Image structures.
2816%
cristy018f07f2011-09-04 21:15:19 +00002817% o exception: return any errors or warnings in this structure.
2818%
cristy3ed852e2009-09-05 21:47:34 +00002819*/
2820MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
cristy018f07f2011-09-04 21:15:19 +00002821 Image *images,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00002822{
2823 CubeInfo
2824 *cube_info;
2825
2826 Image
2827 *image;
2828
2829 MagickBooleanType
2830 proceed,
2831 status;
2832
2833 MagickProgressMonitor
2834 progress_monitor;
2835
cristybb503372010-05-27 20:51:26 +00002836 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00002837 i;
2838
cristybb503372010-05-27 20:51:26 +00002839 size_t
cristy3ed852e2009-09-05 21:47:34 +00002840 depth,
2841 maximum_colors,
2842 number_images;
2843
2844 assert(quantize_info != (const QuantizeInfo *) NULL);
2845 assert(quantize_info->signature == MagickSignature);
2846 assert(images != (Image *) NULL);
2847 assert(images->signature == MagickSignature);
2848 if (images->debug != MagickFalse)
2849 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
2850 if (GetNextImageInList(images) == (Image *) NULL)
2851 {
2852 /*
2853 Handle a single image with QuantizeImage.
2854 */
cristy018f07f2011-09-04 21:15:19 +00002855 status=QuantizeImage(quantize_info,images,exception);
cristy3ed852e2009-09-05 21:47:34 +00002856 return(status);
2857 }
2858 status=MagickFalse;
2859 maximum_colors=quantize_info->number_colors;
2860 if (maximum_colors == 0)
2861 maximum_colors=MaxColormapSize;
2862 if (maximum_colors > MaxColormapSize)
2863 maximum_colors=MaxColormapSize;
2864 depth=quantize_info->tree_depth;
2865 if (depth == 0)
2866 {
cristybb503372010-05-27 20:51:26 +00002867 size_t
cristy3ed852e2009-09-05 21:47:34 +00002868 colors;
2869
2870 /*
2871 Depth of color tree is: Log4(colormap size)+2.
2872 */
2873 colors=maximum_colors;
2874 for (depth=1; colors != 0; depth++)
2875 colors>>=2;
cristycbda6112012-05-27 20:57:16 +00002876 if (quantize_info->dither_method != NoDitherMethod)
cristy3ed852e2009-09-05 21:47:34 +00002877 depth--;
2878 }
2879 /*
2880 Initialize color cube.
2881 */
2882 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2883 if (cube_info == (CubeInfo *) NULL)
2884 {
cristy8a11cb12011-10-19 23:53:34 +00002885 (void) ThrowMagickException(exception,GetMagickModule(),
anthonye5b39652012-04-21 05:37:29 +00002886 ResourceLimitError,"MemoryAllocationFailed","'%s'",images->filename);
cristy3ed852e2009-09-05 21:47:34 +00002887 return(MagickFalse);
2888 }
2889 number_images=GetImageListLength(images);
2890 image=images;
2891 for (i=0; image != (Image *) NULL; i++)
2892 {
2893 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL,
2894 image->client_data);
cristy8a11cb12011-10-19 23:53:34 +00002895 status=ClassifyImageColors(cube_info,image,exception);
cristy3ed852e2009-09-05 21:47:34 +00002896 if (status == MagickFalse)
2897 break;
2898 (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
cristycee97112010-05-28 00:44:52 +00002899 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2900 number_images);
cristy3ed852e2009-09-05 21:47:34 +00002901 if (proceed == MagickFalse)
2902 break;
2903 image=GetNextImageInList(image);
2904 }
2905 if (status != MagickFalse)
2906 {
2907 /*
2908 Reduce the number of colors in an image sequence.
2909 */
2910 ReduceImageColors(images,cube_info);
2911 image=images;
2912 for (i=0; image != (Image *) NULL; i++)
2913 {
2914 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor)
2915 NULL,image->client_data);
cristy018f07f2011-09-04 21:15:19 +00002916 status=AssignImageColors(image,cube_info,exception);
cristy3ed852e2009-09-05 21:47:34 +00002917 if (status == MagickFalse)
2918 break;
2919 (void) SetImageProgressMonitor(image,progress_monitor,
2920 image->client_data);
cristycee97112010-05-28 00:44:52 +00002921 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2922 number_images);
cristy3ed852e2009-09-05 21:47:34 +00002923 if (proceed == MagickFalse)
2924 break;
2925 image=GetNextImageInList(image);
2926 }
2927 }
2928 DestroyCubeInfo(cube_info);
2929 return(status);
2930}
2931
2932/*
2933%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2934% %
2935% %
2936% %
2937+ R e d u c e %
2938% %
2939% %
2940% %
2941%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2942%
2943% Reduce() traverses the color cube tree and prunes any node whose
2944% quantization error falls below a particular threshold.
2945%
2946% The format of the Reduce method is:
2947%
2948% Reduce(const Image *image,CubeInfo *cube_info,const NodeInfo *node_info)
2949%
2950% A description of each parameter follows.
2951%
2952% o image: the image.
2953%
2954% o cube_info: A pointer to the Cube structure.
2955%
2956% o node_info: pointer to node in color cube tree that is to be pruned.
2957%
2958*/
2959static void Reduce(const Image *image,CubeInfo *cube_info,
2960 const NodeInfo *node_info)
2961{
cristybb503372010-05-27 20:51:26 +00002962 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00002963 i;
2964
cristybb503372010-05-27 20:51:26 +00002965 size_t
cristy3ed852e2009-09-05 21:47:34 +00002966 number_children;
2967
2968 /*
2969 Traverse any children.
2970 */
2971 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
cristybb503372010-05-27 20:51:26 +00002972 for (i=0; i < (ssize_t) number_children; i++)
cristy3ed852e2009-09-05 21:47:34 +00002973 if (node_info->child[i] != (NodeInfo *) NULL)
2974 Reduce(image,cube_info,node_info->child[i]);
2975 if (node_info->quantize_error <= cube_info->pruning_threshold)
2976 PruneChild(image,cube_info,node_info);
2977 else
2978 {
2979 /*
2980 Find minimum pruning threshold.
2981 */
2982 if (node_info->number_unique > 0)
2983 cube_info->colors++;
2984 if (node_info->quantize_error < cube_info->next_threshold)
2985 cube_info->next_threshold=node_info->quantize_error;
2986 }
2987}
2988
2989/*
2990%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2991% %
2992% %
2993% %
2994+ R e d u c e I m a g e C o l o r s %
2995% %
2996% %
2997% %
2998%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2999%
3000% ReduceImageColors() repeatedly prunes the tree until the number of nodes
3001% with n2 > 0 is less than or equal to the maximum number of colors allowed
3002% in the output image. On any given iteration over the tree, it selects
3003% those nodes whose E value is minimal for pruning and merges their
3004% color statistics upward. It uses a pruning threshold, Ep, to govern
3005% node selection as follows:
3006%
3007% Ep = 0
3008% while number of nodes with (n2 > 0) > required maximum number of colors
3009% prune all nodes such that E <= Ep
3010% Set Ep to minimum E in remaining nodes
3011%
3012% This has the effect of minimizing any quantization error when merging
3013% two nodes together.
3014%
3015% When a node to be pruned has offspring, the pruning procedure invokes
3016% itself recursively in order to prune the tree from the leaves upward.
3017% n2, Sr, Sg, and Sb in a node being pruned are always added to the
3018% corresponding data in that node's parent. This retains the pruned
3019% node's color characteristics for later averaging.
3020%
3021% For each node, n2 pixels exist for which that node represents the
3022% smallest volume in RGB space containing those pixel's colors. When n2
3023% > 0 the node will uniquely define a color in the output image. At the
3024% beginning of reduction, n2 = 0 for all nodes except a the leaves of
3025% the tree which represent colors present in the input image.
3026%
3027% The other pixel count, n1, indicates the total number of colors
3028% within the cubic volume which the node represents. This includes n1 -
3029% n2 pixels whose colors should be defined by nodes at a lower level in
3030% the tree.
3031%
3032% The format of the ReduceImageColors method is:
3033%
3034% ReduceImageColors(const Image *image,CubeInfo *cube_info)
3035%
3036% A description of each parameter follows.
3037%
3038% o image: the image.
3039%
3040% o cube_info: A pointer to the Cube structure.
3041%
3042*/
3043static void ReduceImageColors(const Image *image,CubeInfo *cube_info)
3044{
3045#define ReduceImageTag "Reduce/Image"
3046
3047 MagickBooleanType
3048 proceed;
3049
3050 MagickOffsetType
3051 offset;
3052
cristybb503372010-05-27 20:51:26 +00003053 size_t
cristy3ed852e2009-09-05 21:47:34 +00003054 span;
3055
3056 cube_info->next_threshold=0.0;
3057 for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; )
3058 {
3059 cube_info->pruning_threshold=cube_info->next_threshold;
3060 cube_info->next_threshold=cube_info->root->quantize_error-1;
3061 cube_info->colors=0;
3062 Reduce(image,cube_info,cube_info->root);
3063 offset=(MagickOffsetType) span-cube_info->colors;
3064 proceed=SetImageProgress(image,ReduceImageTag,offset,span-
3065 cube_info->maximum_colors+1);
3066 if (proceed == MagickFalse)
3067 break;
3068 }
3069}
3070
3071/*
3072%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3073% %
3074% %
3075% %
3076% R e m a p I m a g e %
3077% %
3078% %
3079% %
3080%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3081%
anthony31f1bf72012-01-30 12:37:22 +00003082% RemapImage() replaces the colors of an image with a dither of the colors
3083% provided.
cristy3ed852e2009-09-05 21:47:34 +00003084%
3085% The format of the RemapImage method is:
3086%
3087% MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
cristy018f07f2011-09-04 21:15:19 +00003088% Image *image,const Image *remap_image,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00003089%
3090% A description of each parameter follows:
3091%
3092% o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3093%
3094% o image: the image.
3095%
3096% o remap_image: the reference image.
3097%
cristy018f07f2011-09-04 21:15:19 +00003098% o exception: return any errors or warnings in this structure.
3099%
cristy3ed852e2009-09-05 21:47:34 +00003100*/
3101MagickExport MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
cristy018f07f2011-09-04 21:15:19 +00003102 Image *image,const Image *remap_image,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00003103{
3104 CubeInfo
3105 *cube_info;
3106
3107 MagickBooleanType
3108 status;
3109
3110 /*
3111 Initialize color cube.
3112 */
3113 assert(image != (Image *) NULL);
3114 assert(image->signature == MagickSignature);
3115 if (image->debug != MagickFalse)
3116 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
3117 assert(remap_image != (Image *) NULL);
3118 assert(remap_image->signature == MagickSignature);
3119 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3120 quantize_info->number_colors);
3121 if (cube_info == (CubeInfo *) NULL)
3122 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3123 image->filename);
cristy8a11cb12011-10-19 23:53:34 +00003124 status=ClassifyImageColors(cube_info,remap_image,exception);
cristy3ed852e2009-09-05 21:47:34 +00003125 if (status != MagickFalse)
3126 {
3127 /*
3128 Classify image colors from the reference image.
3129 */
3130 cube_info->quantize_info->number_colors=cube_info->colors;
cristy018f07f2011-09-04 21:15:19 +00003131 status=AssignImageColors(image,cube_info,exception);
cristy3ed852e2009-09-05 21:47:34 +00003132 }
3133 DestroyCubeInfo(cube_info);
3134 return(status);
3135}
3136
3137/*
3138%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3139% %
3140% %
3141% %
3142% R e m a p I m a g e s %
3143% %
3144% %
3145% %
3146%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3147%
3148% RemapImages() replaces the colors of a sequence of images with the
3149% closest color from a reference image.
3150%
3151% The format of the RemapImage method is:
3152%
3153% MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
cristy018f07f2011-09-04 21:15:19 +00003154% Image *images,Image *remap_image,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00003155%
3156% A description of each parameter follows:
3157%
3158% o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3159%
3160% o images: the image sequence.
3161%
3162% o remap_image: the reference image.
3163%
cristy018f07f2011-09-04 21:15:19 +00003164% o exception: return any errors or warnings in this structure.
3165%
cristy3ed852e2009-09-05 21:47:34 +00003166*/
3167MagickExport MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
cristy018f07f2011-09-04 21:15:19 +00003168 Image *images,const Image *remap_image,ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00003169{
3170 CubeInfo
3171 *cube_info;
3172
3173 Image
3174 *image;
3175
3176 MagickBooleanType
3177 status;
3178
3179 assert(images != (Image *) NULL);
3180 assert(images->signature == MagickSignature);
3181 if (images->debug != MagickFalse)
3182 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
3183 image=images;
3184 if (remap_image == (Image *) NULL)
3185 {
3186 /*
3187 Create a global colormap for an image sequence.
3188 */
cristy018f07f2011-09-04 21:15:19 +00003189 status=QuantizeImages(quantize_info,images,exception);
cristy3ed852e2009-09-05 21:47:34 +00003190 return(status);
3191 }
3192 /*
3193 Classify image colors from the reference image.
3194 */
3195 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3196 quantize_info->number_colors);
3197 if (cube_info == (CubeInfo *) NULL)
3198 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3199 image->filename);
cristy018f07f2011-09-04 21:15:19 +00003200 status=ClassifyImageColors(cube_info,remap_image,exception);
cristy3ed852e2009-09-05 21:47:34 +00003201 if (status != MagickFalse)
3202 {
3203 /*
3204 Classify image colors from the reference image.
3205 */
3206 cube_info->quantize_info->number_colors=cube_info->colors;
3207 image=images;
3208 for ( ; image != (Image *) NULL; image=GetNextImageInList(image))
3209 {
cristy018f07f2011-09-04 21:15:19 +00003210 status=AssignImageColors(image,cube_info,exception);
cristy3ed852e2009-09-05 21:47:34 +00003211 if (status == MagickFalse)
3212 break;
3213 }
3214 }
3215 DestroyCubeInfo(cube_info);
3216 return(status);
3217}
3218
3219/*
3220%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3221% %
3222% %
3223% %
3224% S e t G r a y s c a l e I m a g e %
3225% %
3226% %
3227% %
3228%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3229%
3230% SetGrayscaleImage() converts an image to a PseudoClass grayscale image.
3231%
3232% The format of the SetGrayscaleImage method is:
3233%
cristy018f07f2011-09-04 21:15:19 +00003234% MagickBooleanType SetGrayscaleImage(Image *image,ExceptionInfo *exeption)
cristy3ed852e2009-09-05 21:47:34 +00003235%
3236% A description of each parameter follows:
3237%
3238% o image: The image.
3239%
cristy018f07f2011-09-04 21:15:19 +00003240% o exception: return any errors or warnings in this structure.
3241%
cristy3ed852e2009-09-05 21:47:34 +00003242*/
3243
3244#if defined(__cplusplus) || defined(c_plusplus)
3245extern "C" {
3246#endif
3247
3248static int IntensityCompare(const void *x,const void *y)
3249{
cristy101ab702011-10-13 13:06:32 +00003250 PixelInfo
cristy3ed852e2009-09-05 21:47:34 +00003251 *color_1,
3252 *color_2;
3253
cristyecc31b12011-02-13 00:32:29 +00003254 ssize_t
3255 intensity;
3256
cristy101ab702011-10-13 13:06:32 +00003257 color_1=(PixelInfo *) x;
3258 color_2=(PixelInfo *) y;
cristyada285b2012-07-07 19:00:46 +00003259 intensity=(ssize_t) (GetPixelInfoIntensity(color_1)-(ssize_t)
3260 GetPixelInfoIntensity(color_2));
cristycee97112010-05-28 00:44:52 +00003261 return((int) intensity);
cristy3ed852e2009-09-05 21:47:34 +00003262}
3263
3264#if defined(__cplusplus) || defined(c_plusplus)
3265}
3266#endif
3267
cristy018f07f2011-09-04 21:15:19 +00003268static MagickBooleanType SetGrayscaleImage(Image *image,
3269 ExceptionInfo *exception)
cristy3ed852e2009-09-05 21:47:34 +00003270{
cristyc4c8d132010-01-07 01:58:38 +00003271 CacheView
3272 *image_view;
3273
cristyecc31b12011-02-13 00:32:29 +00003274 MagickBooleanType
3275 status;
cristy3ed852e2009-09-05 21:47:34 +00003276
cristy101ab702011-10-13 13:06:32 +00003277 PixelInfo
cristy3ed852e2009-09-05 21:47:34 +00003278 *colormap;
3279
cristybb503372010-05-27 20:51:26 +00003280 register ssize_t
cristy3ed852e2009-09-05 21:47:34 +00003281 i;
3282
cristyecc31b12011-02-13 00:32:29 +00003283 ssize_t
3284 *colormap_index,
3285 j,
3286 y;
cristy3ed852e2009-09-05 21:47:34 +00003287
cristy3ed852e2009-09-05 21:47:34 +00003288 assert(image != (Image *) NULL);
3289 assert(image->signature == MagickSignature);
3290 if (image->type != GrayscaleType)
cristye941a752011-10-15 01:52:48 +00003291 (void) TransformImageColorspace(image,GRAYColorspace,exception);
cristybb503372010-05-27 20:51:26 +00003292 colormap_index=(ssize_t *) AcquireQuantumMemory(MaxMap+1,
cristy3ed852e2009-09-05 21:47:34 +00003293 sizeof(*colormap_index));
cristybb503372010-05-27 20:51:26 +00003294 if (colormap_index == (ssize_t *) NULL)
cristy3ed852e2009-09-05 21:47:34 +00003295 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3296 image->filename);
3297 if (image->storage_class != PseudoClass)
3298 {
cristybb503372010-05-27 20:51:26 +00003299 for (i=0; i <= (ssize_t) MaxMap; i++)
cristy3ed852e2009-09-05 21:47:34 +00003300 colormap_index[i]=(-1);
cristy018f07f2011-09-04 21:15:19 +00003301 if (AcquireImageColormap(image,MaxMap+1,exception) == MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +00003302 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3303 image->filename);
3304 image->colors=0;
3305 status=MagickTrue;
cristy46ff2672012-12-14 15:32:26 +00003306 image_view=AcquireAuthenticCacheView(image,exception);
cristyb5d5f722009-11-04 03:03:49 +00003307#if defined(MAGICKCORE_OPENMP_SUPPORT)
cristyac245f82012-05-05 17:13:57 +00003308 #pragma omp parallel for schedule(static,4) shared(status) \
cristy5e6b2592012-12-19 14:08:11 +00003309 magick_threads(image,image,image->rows,1)
cristy3ed852e2009-09-05 21:47:34 +00003310#endif
cristybb503372010-05-27 20:51:26 +00003311 for (y=0; y < (ssize_t) image->rows; y++)
cristy3ed852e2009-09-05 21:47:34 +00003312 {
cristy4c08aed2011-07-01 19:47:50 +00003313 register Quantum
cristyc47d1f82009-11-26 01:44:43 +00003314 *restrict q;
cristy3ed852e2009-09-05 21:47:34 +00003315
cristyecc31b12011-02-13 00:32:29 +00003316 register ssize_t
3317 x;
3318
cristy3ed852e2009-09-05 21:47:34 +00003319 if (status == MagickFalse)
3320 continue;
3321 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
3322 exception);
cristyacd2ed22011-08-30 01:44:23 +00003323 if (q == (Quantum *) NULL)
cristy3ed852e2009-09-05 21:47:34 +00003324 {
3325 status=MagickFalse;
3326 continue;
3327 }
cristybb503372010-05-27 20:51:26 +00003328 for (x=0; x < (ssize_t) image->columns; x++)
cristy3ed852e2009-09-05 21:47:34 +00003329 {
cristybb503372010-05-27 20:51:26 +00003330 register size_t
cristy3ed852e2009-09-05 21:47:34 +00003331 intensity;
3332
cristy4c08aed2011-07-01 19:47:50 +00003333 intensity=ScaleQuantumToMap(GetPixelRed(image,q));
cristy3ed852e2009-09-05 21:47:34 +00003334 if (colormap_index[intensity] < 0)
3335 {
cristyb5d5f722009-11-04 03:03:49 +00003336#if defined(MAGICKCORE_OPENMP_SUPPORT)
cristyac245f82012-05-05 17:13:57 +00003337 #pragma omp critical (MagickCore_SetGrayscaleImage)
cristy3ed852e2009-09-05 21:47:34 +00003338#endif
3339 if (colormap_index[intensity] < 0)
3340 {
cristybb503372010-05-27 20:51:26 +00003341 colormap_index[intensity]=(ssize_t) image->colors;
cristye42f6582012-02-11 17:59:50 +00003342 image->colormap[image->colors].red=(double)
3343 GetPixelRed(image,q);
3344 image->colormap[image->colors].green=(double)
3345 GetPixelGreen(image,q);
3346 image->colormap[image->colors].blue=(double)
3347 GetPixelBlue(image,q);
cristy3ed852e2009-09-05 21:47:34 +00003348 image->colors++;
3349 }
3350 }
cristyaeded782012-09-11 23:39:36 +00003351 SetPixelIndex(image,(Quantum) colormap_index[intensity],q);
cristyed231572011-07-14 02:18:59 +00003352 q+=GetPixelChannels(image);
cristy3ed852e2009-09-05 21:47:34 +00003353 }
3354 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3355 status=MagickFalse;
3356 }
3357 image_view=DestroyCacheView(image_view);
3358 }
cristybb503372010-05-27 20:51:26 +00003359 for (i=0; i < (ssize_t) image->colors; i++)
cristye42f6582012-02-11 17:59:50 +00003360 image->colormap[i].alpha=(double) i;
cristy101ab702011-10-13 13:06:32 +00003361 qsort((void *) image->colormap,image->colors,sizeof(PixelInfo),
cristy3ed852e2009-09-05 21:47:34 +00003362 IntensityCompare);
cristy101ab702011-10-13 13:06:32 +00003363 colormap=(PixelInfo *) AcquireQuantumMemory(image->colors,
cristy3ed852e2009-09-05 21:47:34 +00003364 sizeof(*colormap));
cristy101ab702011-10-13 13:06:32 +00003365 if (colormap == (PixelInfo *) NULL)
cristy3ed852e2009-09-05 21:47:34 +00003366 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3367 image->filename);
3368 j=0;
3369 colormap[j]=image->colormap[0];
cristybb503372010-05-27 20:51:26 +00003370 for (i=0; i < (ssize_t) image->colors; i++)
cristy3ed852e2009-09-05 21:47:34 +00003371 {
cristy101ab702011-10-13 13:06:32 +00003372 if (IsPixelInfoEquivalent(&colormap[j],&image->colormap[i]) == MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +00003373 {
3374 j++;
3375 colormap[j]=image->colormap[i];
3376 }
cristy4c08aed2011-07-01 19:47:50 +00003377 colormap_index[(ssize_t) image->colormap[i].alpha]=j;
cristy3ed852e2009-09-05 21:47:34 +00003378 }
cristybb503372010-05-27 20:51:26 +00003379 image->colors=(size_t) (j+1);
cristy101ab702011-10-13 13:06:32 +00003380 image->colormap=(PixelInfo *) RelinquishMagickMemory(image->colormap);
cristy3ed852e2009-09-05 21:47:34 +00003381 image->colormap=colormap;
3382 status=MagickTrue;
cristy46ff2672012-12-14 15:32:26 +00003383 image_view=AcquireAuthenticCacheView(image,exception);
cristyb5d5f722009-11-04 03:03:49 +00003384#if defined(MAGICKCORE_OPENMP_SUPPORT)
cristyac245f82012-05-05 17:13:57 +00003385 #pragma omp parallel for schedule(static,4) shared(status) \
cristy5e6b2592012-12-19 14:08:11 +00003386 magick_threads(image,image,image->rows,1)
cristy3ed852e2009-09-05 21:47:34 +00003387#endif
cristybb503372010-05-27 20:51:26 +00003388 for (y=0; y < (ssize_t) image->rows; y++)
cristy3ed852e2009-09-05 21:47:34 +00003389 {
cristy4c08aed2011-07-01 19:47:50 +00003390 register Quantum
cristyc47d1f82009-11-26 01:44:43 +00003391 *restrict q;
cristy3ed852e2009-09-05 21:47:34 +00003392
cristyecc31b12011-02-13 00:32:29 +00003393 register ssize_t
3394 x;
3395
cristy3ed852e2009-09-05 21:47:34 +00003396 if (status == MagickFalse)
3397 continue;
3398 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
cristyacd2ed22011-08-30 01:44:23 +00003399 if (q == (Quantum *) NULL)
cristy3ed852e2009-09-05 21:47:34 +00003400 {
3401 status=MagickFalse;
3402 continue;
3403 }
cristybb503372010-05-27 20:51:26 +00003404 for (x=0; x < (ssize_t) image->columns; x++)
cristy4c08aed2011-07-01 19:47:50 +00003405 {
3406 SetPixelIndex(image,(Quantum) colormap_index[ScaleQuantumToMap(
3407 GetPixelIndex(image,q))],q);
cristyed231572011-07-14 02:18:59 +00003408 q+=GetPixelChannels(image);
cristy4c08aed2011-07-01 19:47:50 +00003409 }
cristy3ed852e2009-09-05 21:47:34 +00003410 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3411 status=MagickFalse;
3412 }
3413 image_view=DestroyCacheView(image_view);
cristybb503372010-05-27 20:51:26 +00003414 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
cristy3ed852e2009-09-05 21:47:34 +00003415 image->type=GrayscaleType;
cristy8a11cb12011-10-19 23:53:34 +00003416 if (IsImageMonochrome(image,exception) != MagickFalse)
cristy3ed852e2009-09-05 21:47:34 +00003417 image->type=BilevelType;
3418 return(status);
3419}