1 /*
2 % Copyright (C) 2003-2020 GraphicsMagick Group
3 % Copyright (C) 2002 ImageMagick Studio
4 % Copyright 1991-1999 E. I. du Pont de Nemours and Company
5 %
6 % This program is covered by multiple licenses, which are described in
7 % Copyright.txt. You should have received a copy of Copyright.txt with this
8 % package; otherwise see http://www.graphicsmagick.org/www/Copyright.html.
9 %
10 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
11 % %
12 % %
13 % %
14 % QQQ U U AAA N N TTTTT IIIII ZZZZZ EEEEE %
15 % Q Q U U A A NN N T I ZZ E %
16 % Q Q U U AAAAA N N N T I ZZZ EEEEE %
17 % Q QQ U U A A N NN T I ZZ E %
18 % QQQQ UUU A A N N T IIIII ZZZZZ EEEEE %
19 % %
20 % %
21 % Methods to Reduce the Number of Unique Colors in an Image %
22 % %
23 % %
24 % Software Design %
25 % John Cristy %
26 % July 1992 %
27 % %
28 % %
29 % %
30 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
31 %
32 % Realism in computer graphics typically requires using 24 bits/pixel to
33 % generate an image. Yet many graphic display devices do not contain the
34 % amount of memory necessary to match the spatial and color resolution of
35 % the human eye. The Quantize methods takes a 24 bit image and reduces
36 % the number of colors so it can be displayed on raster device with less
37 % bits per pixel. In most instances, the quantized image closely
38 % resembles the original reference image.
39 %
40 % A reduction of colors in an image is also desirable for image
41 % transmission and real-time animation.
42 %
43 % QuantizeImage() takes a standard RGB or monochrome images and quantizes
44 % them down to some fixed number of colors.
45 %
46 % For purposes of color allocation, an image is a set of n pixels, where
47 % each pixel is a point in RGB space. RGB space is a 3-dimensional
48 % vector space, and each pixel, Pi, is defined by an ordered triple of
49 % red, green, and blue coordinates, (Ri, Gi, Bi).
50 %
51 % Each primary color component (red, green, or blue) represents an
52 % intensity which varies linearly from 0 to a maximum value, Cmax, which
53 % corresponds to full saturation of that color. Color allocation is
54 % defined over a domain consisting of the cube in RGB space with opposite
55 % vertices at (0,0,0) and (Cmax, Cmax, Cmax). QUANTIZE requires Cmax =
56 % 255.
57 %
58 % The algorithm maps this domain onto a tree in which each node
59 % represents a cube within that domain. In the following discussion
60 % these cubes are defined by the coordinate of two opposite vertices:
61 % The vertex nearest the origin in RGB space and the vertex farthest from
62 % the origin.
63 %
64 % The tree's root node represents the the entire domain, (0,0,0) through
65 % (Cmax,Cmax,Cmax). Each lower level in the tree is generated by
66 % subdividing one node's cube into eight smaller cubes of equal size.
67 % This corresponds to bisecting the parent cube with planes passing
68 % through the midpoints of each edge.
69 %
70 % The basic algorithm operates in three phases: Classification,
71 % Reduction, and Assignment. Classification builds a color description
72 % tree for the image. Reduction collapses the tree until the number it
73 % represents, at most, the number of colors desired in the output image.
74 % Assignment defines the output image's color map and sets each pixel's
75 % color by restorage_class in the reduced tree. Our goal is to minimize
76 % the numerical discrepancies between the original colors and quantized
77 % colors (quantization error).
78 %
79 % Classification begins by initializing a color description tree of
80 % sufficient depth to represent each possible input color in a leaf.
81 % However, it is impractical to generate a fully-formed color description
82 % tree in the storage_class phase for realistic values of Cmax. If
83 % colors components in the input image are quantized to k-bit precision,
84 % so that Cmax= 2k-1, the tree would need k levels below the root node to
85 % allow representing each possible input color in a leaf. This becomes
86 % prohibitive because the tree's total number of nodes is 1 +
87 % sum(i=1, k, 8k).
88 %
89 % A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
90 % Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
91 % Initializes data structures for nodes only as they are needed; (2)
92 % Chooses a maximum depth for the tree as a function of the desired
93 % number of colors in the output image (currently log2(colormap size)).
94 %
95 % For each pixel in the input image, storage_class scans downward from
96 % the root of the color description tree. At each level of the tree it
97 % identifies the single node which represents a cube in RGB space
98 % containing the pixel's color. It updates the following data for each
99 % such node:
100 %
101 % n1: Number of pixels whose color is contained in the RGB cube which
102 % this node represents;
103 %
104 % n2: Number of pixels whose color is not represented in a node at
105 % lower depth in the tree; initially, n2 = 0 for all nodes except
106 % leaves of the tree.
107 %
108 % Sr, Sg, Sb: Sums of the red, green, and blue component values for all
109 % pixels not classified at a lower depth. The combination of these sums
110 % and n2 will ultimately characterize the mean color of a set of
111 % pixels represented by this node.
112 %
113 % E: The distance squared in RGB space between each pixel contained
114 % within a node and the nodes' center. This represents the
115 % quantization error for a node.
116 %
117 % Reduction repeatedly prunes the tree until the number of nodes with n2
118 % > 0 is less than or equal to the maximum number of colors allowed in
119 % the output image. On any given iteration over the tree, it selects
120 % those nodes whose E count is minimal for pruning and merges their color
121 % statistics upward. It uses a pruning threshold, Ep, to govern node
122 % selection as follows:
123 %
124 % Ep = 0
125 % while number of nodes with (n2 > 0) > required maximum number of colors
126 % prune all nodes such that E <= Ep
127 % Set Ep to minimum E in remaining nodes
128 %
129 % This has the effect of minimizing any quantization error when merging
130 % two nodes together.
131 %
132 % When a node to be pruned has offspring, the pruning procedure invokes
133 % itself recursively in order to prune the tree from the leaves upward.
134 % n2, Sr, Sg, and Sb in a node being pruned are always added to the
135 % corresponding data in that node's parent. This retains the pruned
136 % node's color characteristics for later averaging.
137 %
138 % For each node, n2 pixels exist for which that node represents the
139 % smallest volume in RGB space containing those pixel's colors. When n2
140 % > 0 the node will uniquely define a color in the output image. At the
141 % beginning of reduction, n2 = 0 for all nodes except a the leaves of
142 % the tree which represent colors present in the input image.
143 %
144 % The other pixel count, n1, indicates the total number of colors within
145 % the cubic volume which the node represents. This includes n1 - n2
146 % pixels whose colors should be defined by nodes at a lower level in the
147 % tree.
148 %
149 % Assignment generates the output image from the pruned tree. The output
150 % image consists of two parts: (1) A color map, which is an array of
151 % color descriptions (RGB triples) for each color present in the output
152 % image; (2) A pixel array, which represents each pixel as an index
153 % into the color map array.
154 %
155 % First, the assignment phase makes one pass over the pruned color
156 % description tree to establish the image's color map. For each node
157 % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean
158 % color of all pixels that classify no lower than this node. Each of
159 % these colors becomes an entry in the color map.
160 %
161 % Finally, the assignment phase reclassifies each pixel in the pruned
162 % tree to identify the deepest node containing the pixel's color. The
163 % pixel's value in the pixel array becomes the index of this node's mean
164 % color in the color map.
165 %
166 % This method is based on a similar algorithm written by Paul Raveling.
167 %
168 %
169 */
170
171 /*
172 Include declarations.
173 */
174 #include "magick/studio.h"
175 #include "magick/analyze.h"
176 #include "magick/color.h"
177 #include "magick/colormap.h"
178 #include "magick/enhance.h"
179 #include "magick/monitor.h"
180 #include "magick/pixel_cache.h"
181 #include "magick/quantize.h"
182 #include "magick/utility.h"
183
184 /*
185 Define declarations.
186 */
187 #define CacheShift (QuantumDepth-6)
188 #define ExceptionQueueLength 16
189 #define MaxNodes 266817
190 #define MaxTreeDepth 8
191 #define NodesInAList 1536
192
193 #define ColorToNodeId(red,green,blue,index) ((unsigned int) \
194 (((ScaleQuantumToChar(red) >> index) & 0x01) << 2 | \
195 ((ScaleQuantumToChar(green) >> index) & 0x01) << 1 | \
196 ((ScaleQuantumToChar(blue) >> index) & 0x01)))
197
198 /*
199 Typedef declarations.
200 */
201 #if QuantumDepth > 16 && defined(HAVE_LONG_DOUBLE_WIDER)
202 typedef long double ErrorSumType;
203 #else
204 typedef double ErrorSumType;
205 #endif
206
207 typedef struct _NodeInfo
208 {
209 struct _NodeInfo
210 *parent,
211 *child[MaxTreeDepth];
212
213 double
214 number_unique;
215
216 double /* was ErrorSumType */
217 total_red,
218 total_green,
219 total_blue;
220
221 ErrorSumType
222 quantize_error;
223
224 unsigned long
225 color_number;
226
227 unsigned char
228 id,
229 level;
230 } NodeInfo;
231
232 typedef struct _Nodes
233 {
234 NodeInfo
235 *nodes;
236
237 struct _Nodes
238 *next;
239 } Nodes;
240
241 typedef struct _CubeInfo
242 {
243 NodeInfo
244 *root;
245
246 unsigned long
247 colors;
248
249 DoublePixelPacket
250 color;
251
252 double /* was ErrorSumType */
253 distance;
254
255 ErrorSumType
256 pruning_threshold,
257 next_threshold;
258
259 unsigned long
260 nodes,
261 free_nodes,
262 color_number;
263
264 NodeInfo
265 *next_node;
266
267 Nodes
268 *node_queue;
269
270 long
271 *cache;
272
273 DoublePixelPacket
274 error[ExceptionQueueLength];
275
276 double
277 weights[ExceptionQueueLength];
278
279 const QuantizeInfo
280 *quantize_info;
281
282 long
283 x,
284 y;
285
286 unsigned long
287 depth;
288 } CubeInfo;
289
290 /*
291 Method prototypes.
292 */
293 static void
294 ClosestColor(Image *,CubeInfo *,const NodeInfo *);
295
296 static NodeInfo
297 *GetNodeInfo(CubeInfo *,const unsigned int,const unsigned int,NodeInfo *);
298
299 static unsigned int
300 DitherImage(CubeInfo *,Image *);
301
302 static void
303 DefineImageColormap(Image *,NodeInfo *),
304 HilbertCurve(CubeInfo *,Image *,const unsigned long,const unsigned int),
305 PruneLevel(CubeInfo *,const NodeInfo *),
306 PruneToCubeDepth(CubeInfo *,const NodeInfo *),
307 ReduceImageColors(const char *filename,CubeInfo *,const unsigned long,ExceptionInfo *);
308
309 /*
310 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
311 % %
312 % %
313 % %
314 + A s s i g n I m a g e C o l o r s %
315 % %
316 % %
317 % %
318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
319 %
320 % AssignImageColors() generates the output image from the pruned tree. The
321 % output image consists of two parts: (1) A color map, which is an array
322 % of color descriptions (RGB triples) for each color present in the
323 % output image; (2) A pixel array, which represents each pixel as an
324 % index into the color map array.
325 %
326 % First, the assignment phase makes one pass over the pruned color
327 % description tree to establish the image's color map. For each node
328 % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean
329 % color of all pixels that classify no lower than this node. Each of
330 % these colors becomes an entry in the color map.
331 %
332 % Finally, the assignment phase reclassifies each pixel in the pruned
333 % tree to identify the deepest node containing the pixel's color. The
334 % pixel's value in the pixel array becomes the index of this node's mean
335 % color in the color map.
336 %
337 % The format of the AssignImageColors() method is:
338 %
339 % unsigned int AssignImageColors(CubeInfo *cube_info,Image *image)
340 %
341 % A description of each parameter follows.
342 %
343 % o cube_info: A pointer to the Cube structure.
344 %
345 % o image: Specifies a pointer to an Image structure; returned from
346 % ReadImage.
347 %
348 %
349 */
AssignImageColors(CubeInfo * cube_info,Image * image)350 static MagickPassFail AssignImageColors(CubeInfo *cube_info,Image *image)
351 {
352 #define AssignImageText "[%s] Assign colors..."
353
354 unsigned int
355 dither;
356
357 unsigned int
358 is_grayscale,
359 is_monochrome;
360
361 MagickPassFail
362 status=MagickPass;
363
364 /*
365 Allocate image colormap.
366 */
367 if (!AllocateImageColormap(image,cube_info->colors))
368 ThrowBinaryException3(ResourceLimitError,MemoryAllocationFailed,
369 UnableToQuantizeImage);
370 image->colors=0;
371 is_grayscale=image->is_grayscale;
372 is_monochrome=image->is_monochrome;
373 DefineImageColormap(image,cube_info->root);
374 if (cube_info->quantize_info->colorspace == TransparentColorspace)
375 image->storage_class=DirectClass;
376 /*
377 Create a reduced color image.
378 */
379 dither=cube_info->quantize_info->dither;
380 if (dither)
381 dither=DitherImage(cube_info,image);
382 if (!dither)
383 {
384 long
385 y;
386
387 /*
388 FIXME: Use OpenMP?
389 */
390 for (y=0; y < (long) image->rows; y++)
391 {
392 IndexPacket
393 index;
394
395 long
396 count;
397
398 register IndexPacket
399 *indexes;
400
401 register long
402 i,
403 x;
404
405 register const NodeInfo
406 *node_info;
407
408 register PixelPacket
409 *q;
410
411 unsigned int
412 id;
413
414 q=GetImagePixels(image,0,y,image->columns,1);
415 if (q == (PixelPacket *) NULL)
416 {
417 status=MagickFail;
418 break;
419 }
420 indexes=AccessMutableIndexes(image);
421 for (x=0; x < (long) image->columns; x+=count)
422 {
423 /*
424 Identify the deepest node containing the pixel's color.
425 */
426 for (count=1; (x+count) < (long) image->columns; count++)
427 if (NotColorMatch(q,q+count))
428 break;
429 node_info=cube_info->root;
430 for (index=MaxTreeDepth-1; (long) index > 0; index--)
431 {
432 id=ColorToNodeId(q->red,q->green,q->blue,index);
433 if (node_info->child[id] == (NodeInfo *) NULL)
434 break;
435 node_info=node_info->child[id];
436 }
437 /*
438 Find closest color among siblings and their children.
439 */
440 cube_info->color.red=q->red;
441 cube_info->color.green=q->green;
442 cube_info->color.blue=q->blue;
443 cube_info->distance=3.0*(MaxRGBDouble+1.0)*(MaxRGBDouble+1.0);
444 ClosestColor(image,cube_info,node_info->parent);
445 index=(IndexPacket) cube_info->color_number;
446 for (i=0; i < count; i++)
447 {
448 if (image->storage_class == PseudoClass)
449 indexes[x+i]=index;
450 if (!cube_info->quantize_info->measure_error)
451 {
452 q->red=image->colormap[index].red;
453 q->green=image->colormap[index].green;
454 q->blue=image->colormap[index].blue;
455 }
456 q++;
457 }
458 }
459 if (!SyncImagePixels(image))
460 {
461 status=MagickFail;
462 break;
463 }
464 if (QuantumTick(y,image->rows))
465 if (!MagickMonitorFormatted(y,image->rows,&image->exception,
466 AssignImageText,image->filename))
467 {
468 status=MagickFail;
469 break;
470 }
471 }
472 }
473 if ((cube_info->quantize_info->number_colors == 2) &&
474 (IsGrayColorspace(cube_info->quantize_info->colorspace)))
475 {
476 PixelPacket
477 *q;
478
479 Quantum
480 intensity;
481
482 long
483 i;
484
485 /*
486 Monochrome image.
487 */
488 is_monochrome=True;
489 q=image->colormap;
490 for (i=(long) image->colors; i > 0; i--)
491 {
492 intensity=(Quantum) (PixelIntensityToQuantum(q) <
493 (MaxRGB/2) ? 0 : MaxRGB);
494 q->red=intensity;
495 q->green=intensity;
496 q->blue=intensity;
497 q++;
498 }
499 }
500 if (cube_info->quantize_info->measure_error)
501 (void) GetImageQuantizeError(image);
502 status &= SyncImage(image);
503 image->is_grayscale=is_grayscale;
504 image->is_monochrome=is_monochrome;
505 return(status);
506 }
507
508 /*
509 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
510 % %
511 % %
512 % %
513 + C l a s s i f y I m a g e C o l o r s %
514 % %
515 % %
516 % %
517 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
518 %
519 % ClassifyImageColors() begins by initializing a color description tree
520 % of sufficient depth to represent each possible input color in a leaf.
521 % However, it is impractical to generate a fully-formed color
522 % description tree in the storage_class phase for realistic values of
523 % Cmax. If colors components in the input image are quantized to k-bit
524 % precision, so that Cmax= 2k-1, the tree would need k levels below the
525 % root node to allow representing each possible input color in a leaf.
526 % This becomes prohibitive because the tree's total number of nodes is
527 % 1 + sum(i=1,k,8k).
528 %
529 % A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
530 % Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
531 % Initializes data structures for nodes only as they are needed; (2)
532 % Chooses a maximum depth for the tree as a function of the desired
533 % number of colors in the output image (currently log2(colormap size)).
534 %
535 % For each pixel in the input image, storage_class scans downward from
536 % the root of the color description tree. At each level of the tree it
537 % identifies the single node which represents a cube in RGB space
538 % containing It updates the following data for each such node:
539 %
540 % n1 : Number of pixels whose color is contained in the RGB cube
541 % which this node represents;
542 %
543 % n2 : Number of pixels whose color is not represented in a node at
544 % lower depth in the tree; initially, n2 = 0 for all nodes except
545 % leaves of the tree.
546 %
547 % Sr, Sg, Sb : Sums of the red, green, and blue component values for
548 % all pixels not classified at a lower depth. The combination of
549 % these sums and n2 will ultimately characterize the mean color of a
550 % set of pixels represented by this node.
551 %
552 % E: The distance squared in RGB space between each pixel contained
553 % within a node and the nodes' center. This represents the quantization
554 % error for a node.
555 %
556 % The format of the ClassifyImageColors() method is:
557 %
558 % unsigned int ClassifyImageColorsCubeInfo *cube_info,const Image *image,
559 % ExceptionInfo *exception)
560 %
561 % A description of each parameter follows.
562 %
563 % o cube_info: A pointer to the Cube structure.
564 %
565 % o image: Specifies a pointer to an Image structure; returned from
566 % ReadImage.
567 %
568 %
569 */
570
ClassifyImageColors(CubeInfo * cube_info,const Image * image,ExceptionInfo * exception)571 static MagickPassFail ClassifyImageColors(CubeInfo *cube_info,const Image *image,
572 ExceptionInfo *exception)
573 {
574 #define ClassifyImageText "[%s] Classify colors..."
575
576 double
577 bisect;
578
579 DoublePixelPacket
580 mid,
581 pixel;
582
583 long
584 count,
585 y;
586
587 NodeInfo
588 *node_info;
589
590 register long
591 x;
592
593 register const PixelPacket
594 *p;
595
596 unsigned long
597 index,
598 level;
599
600 unsigned int
601 id;
602
603 MagickPassFail
604 status=MagickPass;
605
606 /*
607 Classify the first 256 colors to a tree depth of 8.
608 */
609 for (y=0; (y < (long) image->rows) && (cube_info->colors < 256); y++)
610 {
611 p=AcquireImagePixels(image,0,y,image->columns,1,exception);
612 if (p == (const PixelPacket *) NULL)
613 {
614 status=MagickFail;
615 break;
616 }
617 if (cube_info->nodes > MaxNodes)
618 {
619 /*
620 Prune one level if the color tree is too large.
621 */
622 PruneLevel(cube_info,cube_info->root);
623 cube_info->depth--;
624 }
625 for (x=0; x < (long) image->columns; x+=count)
626 {
627 /*
628 Start at the root and descend the color cube tree.
629 */
630 for (count=1; (x+count) < (long) image->columns; count++)
631 if (NotColorMatch(p,p+count))
632 break;
633 index=MaxTreeDepth-1;
634 bisect=(MaxRGBDouble+1.0)/2.0;
635 mid.red=MaxRGBDouble/2.0;
636 mid.green=MaxRGBDouble/2.0;
637 mid.blue=MaxRGBDouble/2.0;
638 node_info=cube_info->root;
639 for (level=1; level <= 8; level++)
640 {
641 bisect/=2;
642 id=ColorToNodeId(p->red,p->green,p->blue,index);
643 mid.red+=id & 4 ? bisect : -bisect;
644 mid.green+=id & 2 ? bisect : -bisect;
645 mid.blue+=id & 1 ? bisect : -bisect;
646 if (node_info->child[id] == (NodeInfo *) NULL)
647 {
648 /*
649 Set colors of new node to contain pixel.
650 */
651 node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
652 if (node_info->child[id] == (NodeInfo *) NULL)
653 {
654 ThrowException3(exception,ResourceLimitError,
655 MemoryAllocationFailed,UnableToQuantizeImage);
656 status=MagickFail;
657 break;
658 }
659 if (level == MaxTreeDepth)
660 cube_info->colors++;
661 }
662 /*
663 Approximate the quantization error represented by this node.
664 */
665 node_info=node_info->child[id];
666 pixel.red=p->red-mid.red;
667 pixel.green=p->green-mid.green;
668 pixel.blue=p->blue-mid.blue;
669 node_info->quantize_error+=count*pixel.red*pixel.red+
670 count*pixel.green*pixel.green+count*pixel.blue*pixel.blue;
671 cube_info->root->quantize_error+=node_info->quantize_error;
672 index--;
673 }
674 if (status == MagickFail)
675 break;
676 /*
677 Sum RGB for this leaf for later derivation of the mean cube color.
678 */
679 node_info->number_unique+=count;
680 node_info->total_red+=(double) count*p->red;
681 node_info->total_green+=(double) count*p->green;
682 node_info->total_blue+=(double) count*p->blue;
683 p+=count;
684 }
685 if (QuantumTick(y,image->rows))
686 if (!MagickMonitorFormatted(y,image->rows,exception,
687 ClassifyImageText,image->filename))
688 {
689 status=MagickFail;
690 break;
691 }
692 }
693 if ((status == MagickFail) || (y == (long) image->rows))
694 return status;
695 /*
696 More than 256 colors; classify to the cube_info->depth tree depth.
697 */
698 PruneToCubeDepth(cube_info,cube_info->root);
699 for ( ; y < (long) image->rows; y++)
700 {
701 p=AcquireImagePixels(image,0,y,image->columns,1,exception);
702 if (p == (const PixelPacket *) NULL)
703 {
704 status=MagickFail;
705 break;
706 }
707 if (cube_info->nodes > MaxNodes)
708 {
709 /*
710 Prune one level if the color tree is too large.
711 */
712 PruneLevel(cube_info,cube_info->root);
713 cube_info->depth--;
714 }
715 for (x=0; x < (long) image->columns; x+=count)
716 {
717 /*
718 Start at the root and descend the color cube tree.
719 */
720 for (count=1; (x+count) < (long) image->columns; count++)
721 if (NotColorMatch(p,p+count))
722 break;
723 index=MaxTreeDepth-1;
724 bisect=(MaxRGBDouble+1.0)/2.0;
725 mid.red=MaxRGBDouble/2.0;
726 mid.green=MaxRGBDouble/2.0;
727 mid.blue=MaxRGBDouble/2.0;
728 node_info=cube_info->root;
729 for (level=1; level <= cube_info->depth; level++)
730 {
731 bisect/=2.0;
732 id=ColorToNodeId(p->red,p->green,p->blue,index);
733 mid.red+=id & 4 ? bisect : -bisect;
734 mid.green+=id & 2 ? bisect : -bisect;
735 mid.blue+=id & 1 ? bisect : -bisect;
736 if (node_info->child[id] == (NodeInfo *) NULL)
737 {
738 /*
739 Set colors of new node to contain pixel.
740 */
741 node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
742 if (node_info->child[id] == (NodeInfo *) NULL)
743 {
744 ThrowException3(exception,ResourceLimitError,
745 MemoryAllocationFailed,UnableToQuantizeImage);
746 status=MagickFail;
747 break;
748 }
749 if (level == cube_info->depth)
750 cube_info->colors++;
751 }
752 /*
753 Approximate the quantization error represented by this node.
754 */
755 node_info=node_info->child[id];
756 pixel.red=p->red-mid.red;
757 pixel.green=p->green-mid.green;
758 pixel.blue=p->blue-mid.blue;
759 node_info->quantize_error+=count*pixel.red*pixel.red+
760 count*pixel.green*pixel.green+count*pixel.blue*pixel.blue;
761 cube_info->root->quantize_error+=node_info->quantize_error;
762 index--;
763 }
764 if (status == MagickFail)
765 break;
766 /*
767 Sum RGB for this leaf for later derivation of the mean cube color.
768 */
769 node_info->number_unique+=count;
770 node_info->total_red+=(double) count*p->red;
771 node_info->total_green+=(double) count*p->green;
772 node_info->total_blue+=(double) count*p->blue;
773 p+=count;
774 }
775 if (QuantumTick(y,image->rows))
776 if (!MagickMonitorFormatted(y,image->rows,exception,
777 ClassifyImageText,image->filename))
778 {
779 status=MagickFail;
780 break;
781 }
782 }
783 return(status);
784 }
785
786 /*
787 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
788 % %
789 % %
790 % %
791 % C l o n e Q u a n t i z e I n f o %
792 % %
793 % %
794 % %
795 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
796 %
797 % CloneQuantizeInfo() makes a duplicate of the given quantize info structure,
798 % or if quantize info is NULL, a new one.
799 %
800 % The format of the CloneQuantizeInfo method is:
801 %
802 % QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
803 %
804 % A description of each parameter follows:
805 %
806 % o clone_info: Method CloneQuantizeInfo returns a duplicate of the given
807 % quantize info, or if image info is NULL a new one.
808 %
809 % o quantize_info: a structure of type info.
810 %
811 %
812 */
CloneQuantizeInfo(const QuantizeInfo * quantize_info)813 MagickExport QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
814 {
815 QuantizeInfo
816 *clone_info;
817
818 clone_info=MagickAllocateMemory(QuantizeInfo *,sizeof(QuantizeInfo));
819 if (clone_info == (QuantizeInfo *) NULL)
820 MagickFatalError3(ResourceLimitFatalError,MemoryAllocationFailed,
821 UnableToAllocateQuantizeInfo);
822 GetQuantizeInfo(clone_info);
823 if (quantize_info == (QuantizeInfo *) NULL)
824 return(clone_info);
825 clone_info->number_colors=quantize_info->number_colors;
826 clone_info->tree_depth=quantize_info->tree_depth;
827 clone_info->dither=quantize_info->dither;
828 clone_info->colorspace=quantize_info->colorspace;
829 clone_info->measure_error=quantize_info->measure_error;
830 return(clone_info);
831 }
832
833 /*
834 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
835 % %
836 % %
837 % %
838 + C l o s e s t C o l o r %
839 % %
840 % %
841 % %
842 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
843 %
844 % ClosestColor() traverses the color cube tree at a particular node and
845 % determines which colormap entry best represents the input color.
846 %
847 % This is a recursive function.
848 %
849 % The format of the ClosestColor method is:
850 %
851 % void ClosestColor(Image *image,CubeInfo *cube_info,
852 % const NodeInfo *node_info)
853 %
854 % A description of each parameter follows.
855 %
856 % o image: The image.
857 %
858 % o cube_info: A pointer to the Cube structure.
859 %
860 % o node_info: The address of a structure of type NodeInfo which points to a
861 % node in the color cube tree that is to be pruned.
862 %
863 %
864 */
ClosestColor(Image * image,CubeInfo * cube_info,const NodeInfo * node_info)865 static void ClosestColor(Image *image,CubeInfo *cube_info,
866 const NodeInfo *node_info)
867 {
868 register unsigned int
869 id;
870
871 /*
872 Traverse any children.
873 */
874 for (id=0; id < MaxTreeDepth; id++)
875 if (node_info->child[id] != (NodeInfo *) NULL)
876 ClosestColor(image,cube_info,node_info->child[id]);
877 if (node_info->number_unique != 0)
878 {
879 double
880 distance;
881
882 DoublePixelPacket
883 pixel;
884
885 register PixelPacket
886 *color;
887
888 /*
889 Determine if this color is "closest".
890 */
891 color=image->colormap+node_info->color_number;
892 pixel.red=color->red-cube_info->color.red;
893 distance=pixel.red*pixel.red;
894 if (distance < cube_info->distance)
895 {
896 pixel.green=color->green-cube_info->color.green;
897 distance+=pixel.green*pixel.green;
898 if (distance < cube_info->distance)
899 {
900 pixel.blue=color->blue-cube_info->color.blue;
901 distance+=pixel.blue*pixel.blue;
902 if (distance < cube_info->distance)
903 {
904 cube_info->distance=distance;
905 cube_info->color_number=node_info->color_number;
906 }
907 }
908 }
909 }
910 }
911
912 /*
913 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
914 % %
915 % %
916 % %
917 % C o m p r e s s I m a g e C o l o r m a p %
918 % %
919 % %
920 % %
921 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
922 %
923 % CompressImageColormap() compresses an image colormap by removing any
924 % duplicate or unused color entries.
925 %
926 % The format of the CompressImageColormap method is:
927 %
928 % void CompressImageColormap(Image *image)
929 %
930 % A description of each parameter follows:
931 %
932 % o image: The image.
933 %
934 %
935 */
CompressImageColormap(Image * image)936 MagickExport void CompressImageColormap(Image *image)
937 {
938 QuantizeInfo
939 quantize_info;
940
941 assert(image != (Image *) NULL);
942 assert(image->signature == MagickSignature);
943 if (!IsPaletteImage(image,&image->exception))
944 return;
945 GetQuantizeInfo(&quantize_info);
946 quantize_info.number_colors=image->colors;
947 quantize_info.tree_depth=MaxTreeDepth;
948 (void) QuantizeImage(&quantize_info,image);
949 }
950
951 /*
952 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
953 % %
954 % %
955 % %
956 + D e f i n e I m a g e C o l o r m a p %
957 % %
958 % %
959 % %
960 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
961 %
962 % DefineImageColormap() traverses the color cube tree and notes each colormap
963 % entry. A colormap entry is any node in the color cube tree where the
964 % of unique colors is not zero.
965 %
966 % The format of the DefineImageColormap method is:
967 %
968 % DefineImageColormap(Image *image,NodeInfo *node_info)
969 %
970 % A description of each parameter follows.
971 %
972 % o image: The image.
973 %
974 % o node_info: The address of a structure of type NodeInfo which points to a
975 % node in the color cube tree that is to be pruned.
976 %
977 %
978 */
DefineImageColormap(Image * image,NodeInfo * node_info)979 static void DefineImageColormap(Image *image,NodeInfo *node_info)
980 {
981 register unsigned int
982 id;
983
984 /*
985 Traverse any children.
986 */
987 for (id=0; id < MaxTreeDepth; id++)
988 if (node_info->child[id] != (NodeInfo *) NULL)
989 DefineImageColormap(image,node_info->child[id]);
990 if (node_info->number_unique != 0)
991 {
992 register double
993 number_unique;
994
995 /*
996 Colormap entry is defined by the mean color in this cube.
997 */
998 number_unique=node_info->number_unique;
999 image->colormap[image->colors].red=(Quantum)
1000 (node_info->total_red/number_unique+0.5);
1001 image->colormap[image->colors].green=(Quantum)
1002 (node_info->total_green/number_unique+0.5);
1003 image->colormap[image->colors].blue=(Quantum)
1004 (node_info->total_blue/number_unique+0.5);
1005 node_info->color_number=image->colors++;
1006 }
1007 }
1008
1009 /*
1010 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1011 % %
1012 % %
1013 % %
1014 + D e s t r o y C u b e I n f o %
1015 % %
1016 % %
1017 % %
1018 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1019 %
1020 % DestroyCubeInfo() deallocates memory associated with an image.
1021 %
1022 % The format of the DestroyCubeInfo method is:
1023 %
1024 % DestroyCubeInfo(CubeInfo *cube_info)
1025 %
1026 % A description of each parameter follows:
1027 %
1028 % o cube_info: The address of a structure of type CubeInfo.
1029 %
1030 %
1031 */
DestroyCubeInfo(CubeInfo * cube_info)1032 static void DestroyCubeInfo(CubeInfo *cube_info)
1033 {
1034 register Nodes
1035 *nodes;
1036
1037 /*
1038 Release color cube tree storage.
1039 */
1040 do
1041 {
1042 nodes=cube_info->node_queue->next;
1043 MagickFreeMemory(cube_info->node_queue->nodes);
1044 MagickFreeMemory(cube_info->node_queue);
1045 cube_info->node_queue=nodes;
1046 } while (cube_info->node_queue != (Nodes *) NULL);
1047 if (cube_info->quantize_info->dither)
1048 MagickFreeMemory(cube_info->cache);
1049 MagickFreeMemory(cube_info);
1050 }
1051
1052 /*
1053 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1054 % %
1055 % %
1056 % %
1057 % D e s t r o y Q u a n t i z e I n f o %
1058 % %
1059 % %
1060 % %
1061 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1062 %
1063 % DestroyQuantizeInfo() deallocates memory associated with an QuantizeInfo
1064 % structure.
1065 %
1066 % The format of the DestroyQuantizeInfo method is:
1067 %
1068 % DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1069 %
1070 % A description of each parameter follows:
1071 %
1072 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1073 %
1074 %
1075 */
DestroyQuantizeInfo(QuantizeInfo * quantize_info)1076 MagickExport void DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1077 {
1078 assert(quantize_info != (QuantizeInfo *) NULL);
1079 assert(quantize_info->signature == MagickSignature);
1080 MagickFreeMemory(quantize_info);
1081 }
1082
1083 /*
1084 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1085 % %
1086 % %
1087 % %
1088 + D i t h e r %
1089 % %
1090 % %
1091 % %
1092 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1093 %
1094 % Dither() distributes the difference between an original image and the
1095 % corresponding color reduced algorithm to neighboring pixels along a Hilbert
1096 % curve.
1097 %
1098 % The format of the Dither method is:
1099 %
1100 % unsigned int Dither(CubeInfo *cube_info,Image *image,
1101 % const unsigned int direction)
1102 %
1103 % A description of each parameter follows.
1104 %
1105 % o cube_info: A pointer to the Cube structure.
1106 %
1107 % o image: Specifies a pointer to an Image structure; returned from
1108 % ReadImage.
1109 %
1110 % o direction: This unsigned direction describes which direction
1111 % to move to next to follow the Hilbert curve.
1112 %
1113 */
Dither(CubeInfo * cube_info,Image * image,const unsigned int direction)1114 static MagickPassFail Dither(CubeInfo *cube_info,Image *image,
1115 const unsigned int direction)
1116 {
1117 DoublePixelPacket
1118 error;
1119
1120 IndexPacket
1121 index;
1122
1123 PixelPacket
1124 pixel;
1125
1126 register CubeInfo
1127 *p;
1128
1129 register IndexPacket
1130 *indexes;
1131
1132 register long
1133 i;
1134
1135 register PixelPacket
1136 *q;
1137
1138 p=cube_info;
1139 if ((p->x >= 0) && (p->x < (long) image->columns) &&
1140 (p->y >= 0) && (p->y < (long) image->rows))
1141 {
1142 /*
1143 Distribute error.
1144 */
1145 q=GetImagePixels(image,p->x,p->y,1,1);
1146 if (q == (PixelPacket *) NULL)
1147 return(MagickFail);
1148 indexes=AccessMutableIndexes(image);
1149 error.red=q->red;
1150 error.green=q->green;
1151 error.blue=q->blue;
1152 for (i=0; i < ExceptionQueueLength; i++)
1153 {
1154 error.red+=p->error[i].red*p->weights[i];
1155 error.green+=p->error[i].green*p->weights[i];
1156 error.blue+=p->error[i].blue*p->weights[i];
1157 }
1158
1159 pixel.red=RoundDoubleToQuantum(error.red);
1160 pixel.green=RoundDoubleToQuantum(error.green);
1161 pixel.blue=RoundDoubleToQuantum(error.blue);
1162
1163 i=(pixel.blue >> CacheShift) << 12 | (pixel.green >> CacheShift) << 6 |
1164 (pixel.red >> CacheShift);
1165 if (p->cache[i] < 0)
1166 {
1167 register NodeInfo
1168 *node_info;
1169
1170 register unsigned int
1171 id;
1172
1173 /*
1174 Identify the deepest node containing the pixel's color.
1175 */
1176 node_info=p->root;
1177 for (index=MaxTreeDepth-1; (long) index > 0; index--)
1178 {
1179 id=ColorToNodeId(pixel.red,pixel.green,pixel.blue,index);
1180 if (node_info->child[id] == (NodeInfo *) NULL)
1181 break;
1182 node_info=node_info->child[id];
1183 }
1184 /*
1185 Find closest color among siblings and their children.
1186 */
1187 p->color.red=pixel.red;
1188 p->color.green=pixel.green;
1189 p->color.blue=pixel.blue;
1190 p->distance=3.0*(MaxRGBDouble+1.0)*(MaxRGBDouble+1.0);
1191 ClosestColor(image,p,node_info->parent);
1192 p->cache[i]=(long) p->color_number;
1193 }
1194 /*
1195 Assign pixel to closest colormap entry.
1196 */
1197 index=(IndexPacket) p->cache[i];
1198 if (image->storage_class == PseudoClass)
1199 *indexes=index;
1200 if (!cube_info->quantize_info->measure_error)
1201 {
1202 q->red=image->colormap[index].red;
1203 q->green=image->colormap[index].green;
1204 q->blue=image->colormap[index].blue;
1205 }
1206 if (!SyncImagePixels(image))
1207 return(MagickFail);
1208 /*
1209 Propagate the error as the last entry of the error queue.
1210 */
1211 for (i=0; i < (ExceptionQueueLength-1); i++)
1212 p->error[i]=p->error[i+1];
1213 p->error[i].red=pixel.red-(double) image->colormap[index].red;
1214 p->error[i].green=pixel.green-(double) image->colormap[index].green;
1215 p->error[i].blue=pixel.blue-(double) image->colormap[index].blue;
1216 }
1217 switch (direction)
1218 {
1219 case WestGravity: p->x--; break;
1220 case EastGravity: p->x++; break;
1221 case NorthGravity: p->y--; break;
1222 case SouthGravity: p->y++; break;
1223 }
1224 return(MagickPass);
1225 }
1226
1227 /*
1228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1229 % %
1230 % %
1231 % %
1232 + D i t h e r I m a g e %
1233 % %
1234 % %
1235 % %
1236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1237 %
1238 % DitherImage() distributes the difference between an original image and the
1239 % corresponding color reduced algorithm to neighboring pixels along a Hilbert
1240 % curve. DitherImage returns True if the image is dithered otherwise False.
1241 %
1242 % This algorithm is strongly based on a similar algorithm by Thiadmer
1243 % Riemersma.
1244 %
1245 % The format of the DitherImage method is:
1246 %
1247 % unsigned int DitherImage(CubeInfo *cube_info,Image *image)
1248 %
1249 % A description of each parameter follows.
1250 %
1251 % o cube_info: A pointer to the Cube structure.
1252 %
1253 % o image: Specifies a pointer to an Image structure; returned from
1254 % ReadImage.
1255 %
1256 %
1257 */
DitherImage(CubeInfo * cube_info,Image * image)1258 static MagickPassFail DitherImage(CubeInfo *cube_info,Image *image)
1259 {
1260 register unsigned long
1261 i;
1262
1263 unsigned long
1264 depth;
1265
1266 /*
1267 Initialize error queue.
1268 */
1269 for (i=0; i < ExceptionQueueLength; i++)
1270 {
1271 cube_info->error[i].red=0.0;
1272 cube_info->error[i].green=0.0;
1273 cube_info->error[i].blue=0.0;
1274 }
1275 /*
1276 Distribute quantization error along a Hilbert curve.
1277 */
1278 cube_info->x=0;
1279 cube_info->y=0;
1280 i=image->columns > image->rows ? image->columns : image->rows;
1281 for (depth=1; i != 0; depth++)
1282 i>>=1;
1283 HilbertCurve(cube_info,image,depth-1,NorthGravity);
1284 (void) Dither(cube_info,image,ForgetGravity);
1285 return(MagickPass);
1286 }
1287
1288 /*
1289 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1290 % %
1291 % %
1292 % %
1293 + G e t C u b e I n f o %
1294 % %
1295 % %
1296 % %
1297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1298 %
1299 % GetCubeInfo() initialize the Cube data structure.
1300 %
1301 % The format of the GetCubeInfo method is:
1302 %
1303 % CubeInfo GetCubeInfo(const QuantizeInfo *quantize_info,
1304 % unsigned int depth)
1305 %
1306 % A description of each parameter follows.
1307 %
1308 % o cube_info: A pointer to the Cube structure.
1309 %
1310 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1311 %
1312 % o depth: Normally, this integer value is zero or one. A zero or
1313 % one tells Quantize to choose a optimal tree depth of Log4(number_colors).
1314 % A tree of this depth generally allows the best representation of the
1315 % reference image with the least amount of memory and the fastest
1316 % computational speed. In some cases, such as an image with low color
1317 % dispersion (a few number of colors), a value other than
1318 % Log4(number_colors) is required. To expand the color tree completely,
1319 % use a value of 8.
1320 %
1321 %
1322 */
GetCubeInfo(const QuantizeInfo * quantize_info,unsigned long depth)1323 static CubeInfo *GetCubeInfo(const QuantizeInfo *quantize_info,
1324 unsigned long depth)
1325 {
1326 CubeInfo
1327 *cube_info;
1328
1329 double
1330 sum,
1331 weight;
1332
1333 register long
1334 i;
1335
1336 /*
1337 Initialize tree to describe color cube_info.
1338 */
1339 cube_info=MagickAllocateMemory(CubeInfo *,sizeof(CubeInfo));
1340 if (cube_info == (CubeInfo *) NULL)
1341 return((CubeInfo *) NULL);
1342 (void) memset(cube_info,0,sizeof(CubeInfo));
1343 if (depth > MaxTreeDepth)
1344 depth=MaxTreeDepth;
1345 if (depth < 2)
1346 depth=2;
1347 cube_info->depth=depth;
1348 /*
1349 Initialize root node.
1350 */
1351 cube_info->root=GetNodeInfo(cube_info,0,0,(NodeInfo *) NULL);
1352 if (cube_info->root == (NodeInfo *) NULL)
1353 return((CubeInfo *) NULL);
1354 cube_info->root->parent=cube_info->root;
1355 cube_info->quantize_info=quantize_info;
1356 if (!cube_info->quantize_info->dither)
1357 return(cube_info);
1358 /*
1359 Initialize dither resources.
1360 */
1361 cube_info->cache=MagickAllocateMemory(long *,(1 << 18)*sizeof(long));
1362 if (cube_info->cache == (long *) NULL)
1363 return((CubeInfo *) NULL);
1364 /*
1365 Initialize color cache.
1366 */
1367 for (i=0; i < (1 << 18); i++)
1368 cube_info->cache[i]=(-1);
1369 /*
1370 Distribute weights along a curve of exponential decay.
1371 */
1372 weight=1.0;
1373 for (i=0; i < ExceptionQueueLength; i++)
1374 {
1375 cube_info->weights[ExceptionQueueLength-i-1]=1.0/weight;
1376 weight*=exp(log((MaxRGBDouble+1.0))/(ExceptionQueueLength-1.0));
1377 }
1378 /*
1379 Normalize the weighting factors.
1380 */
1381 weight=0.0;
1382 for (i=0; i < ExceptionQueueLength; i++)
1383 weight+=cube_info->weights[i];
1384 sum=0.0;
1385 for (i=0; i < ExceptionQueueLength; i++)
1386 {
1387 cube_info->weights[i]/=weight;
1388 sum+=cube_info->weights[i];
1389 }
1390 cube_info->weights[0]+=1.0-sum;
1391 return(cube_info);
1392 }
1393
1394 /*
1395 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1396 % %
1397 % %
1398 % %
1399 + G e t N o d e I n f o %
1400 % %
1401 % %
1402 % %
1403 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1404 %
1405 % GetNodeInfo() allocates memory for a new node in the color cube tree and
1406 % presets all fields to zero.
1407 %
1408 % The format of the GetNodeInfo method is:
1409 %
1410 % NodeInfo *GetNodeInfo(CubeInfo *cube_info,const unsigned int id,
1411 % const unsigned int level,NodeInfo *parent)
1412 %
1413 % A description of each parameter follows.
1414 %
1415 % o node: The GetNodeInfo method returns this integer address.
1416 %
1417 % o id: Specifies the child number of the node.
1418 %
1419 % o level: Specifies the level in the storage_class the node resides.
1420 %
1421 %
1422 */
GetNodeInfo(CubeInfo * cube_info,const unsigned int id,const unsigned int level,NodeInfo * parent)1423 static NodeInfo *GetNodeInfo(CubeInfo *cube_info,const unsigned int id,
1424 const unsigned int level,NodeInfo *parent)
1425 {
1426 NodeInfo
1427 *node_info;
1428
1429 if (cube_info->free_nodes == 0)
1430 {
1431 Nodes
1432 *nodes;
1433
1434 /*
1435 Allocate a new nodes of nodes.
1436 */
1437 nodes=MagickAllocateMemory(Nodes *,sizeof(Nodes));
1438 if (nodes == (Nodes *) NULL)
1439 return((NodeInfo *) NULL);
1440 nodes->nodes=MagickAllocateMemory(NodeInfo *,(NodesInAList*sizeof(NodeInfo)));
1441 if (nodes->nodes == (NodeInfo *) NULL)
1442 return((NodeInfo *) NULL);
1443 nodes->next=cube_info->node_queue;
1444 cube_info->node_queue=nodes;
1445 cube_info->next_node=nodes->nodes;
1446 cube_info->free_nodes=NodesInAList;
1447 }
1448 cube_info->nodes++;
1449 cube_info->free_nodes--;
1450 node_info=cube_info->next_node++;
1451 (void) memset(node_info,0,sizeof(NodeInfo));
1452 node_info->parent=parent;
1453 node_info->id=id;
1454 node_info->level=level;
1455 return(node_info);
1456 }
1457
1458 /*
1459 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1460 % %
1461 % %
1462 % %
1463 % G e t I m a g e Q u a n t i z e E r r o r %
1464 % %
1465 % %
1466 % %
1467 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1468 %
1469 % GetImageQuantizeError() measures the difference between the original
1470 % and quantized images. This difference is the total quantization error.
1471 % The error is computed by summing over all pixels in an image the distance
1472 % squared in RGB space between each reference pixel value and its quantized
1473 % value. These values are computed:
1474 %
1475 % o mean_error_per_pixel: This value is the mean error for any single
1476 % pixel in the image.
1477 %
1478 % o normalized_mean_square_error: This value is the normalized mean
1479 % quantization error for any single pixel in the image. This distance
1480 % measure is normalized to a range between 0 and 1. It is independent
1481 % of the range of red, green, and blue values in the image.
1482 %
1483 % o normalized_maximum_square_error: This value is the normalized
1484 % maximum quantization error for any single pixel in the image. This
1485 % distance measure is normalized to a range between 0 and 1. It is
1486 % independent of the range of red, green, and blue values in your image.
1487 %
1488 %
1489 % The format of the GetImageQuantizeError method is:
1490 %
1491 % unsigned int GetImageQuantizeError(Image *image)
1492 %
1493 % A description of each parameter follows.
1494 %
1495 % o image: Specifies a pointer to an Image structure; returned from
1496 % ReadImage.
1497 %
1498 %
1499 */
GetImageQuantizeError(Image * image)1500 MagickExport MagickPassFail GetImageQuantizeError(Image *image)
1501 {
1502 double
1503 distance,
1504 maximum_error_per_pixel,
1505 normalize;
1506
1507 DoublePixelPacket
1508 pixel;
1509
1510 IndexPacket
1511 index;
1512
1513 long
1514 y;
1515
1516 ErrorSumType
1517 total_error;
1518
1519 register const PixelPacket
1520 *p;
1521
1522 register const IndexPacket
1523 *indexes;
1524
1525 register long
1526 x;
1527
1528 MagickPassFail
1529 status=MagickPass;
1530
1531 /*
1532 Initialize measurement.
1533 */
1534 assert(image != (Image *) NULL);
1535 assert(image->signature == MagickSignature);
1536 image->total_colors=GetNumberColors(image,(FILE *) NULL,&image->exception);
1537 (void) memset(&image->error,0,sizeof(ErrorInfo));
1538 if (image->storage_class == DirectClass)
1539 return(MagickFail);
1540 /*
1541 For each pixel, collect error statistics.
1542 */
1543 maximum_error_per_pixel=0;
1544 total_error=0;
1545 for (y=0; y < (long) image->rows; y++)
1546 {
1547 p=AcquireImagePixels(image,0,y,image->columns,1,&image->exception);
1548 if (p == (const PixelPacket *) NULL)
1549 {
1550 status=MagickFail;
1551 break;
1552 }
1553 indexes=AccessImmutableIndexes(image);
1554 for (x=0; x < (long) image->columns; x++)
1555 {
1556 index=indexes[x];
1557 pixel.red=p->red-(double) image->colormap[index].red;
1558 pixel.green=p->green-(double) image->colormap[index].green;
1559 pixel.blue=p->blue-(double) image->colormap[index].blue;
1560 distance=pixel.red*pixel.red+pixel.green*pixel.green+
1561 pixel.blue*pixel.blue;
1562 total_error+=distance;
1563 if (distance > maximum_error_per_pixel)
1564 maximum_error_per_pixel=distance;
1565 p++;
1566 }
1567 }
1568 /*
1569 Compute final error statistics.
1570 */
1571 normalize=3.0*(MaxRGBDouble+1.0)*(MaxRGBDouble+1.0);
1572 image->error.mean_error_per_pixel=total_error/image->columns/image->rows;
1573 image->error.normalized_mean_error=
1574 image->error.mean_error_per_pixel/normalize;
1575 image->error.normalized_maximum_error=maximum_error_per_pixel/normalize;
1576 return(status);
1577 }
1578
1579 /*
1580 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1581 % %
1582 % %
1583 % %
1584 % G e t Q u a n t i z e I n f o %
1585 % %
1586 % %
1587 % %
1588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1589 %
1590 % GetQuantizeInfo() initializes the QuantizeInfo structure.
1591 %
1592 % The format of the GetQuantizeInfo method is:
1593 %
1594 % GetQuantizeInfo(QuantizeInfo *quantize_info)
1595 %
1596 % A description of each parameter follows:
1597 %
1598 % o quantize_info: Specifies a pointer to a QuantizeInfo structure.
1599 %
1600 %
1601 */
GetQuantizeInfo(QuantizeInfo * quantize_info)1602 MagickExport void GetQuantizeInfo(QuantizeInfo *quantize_info)
1603 {
1604 assert(quantize_info != (QuantizeInfo *) NULL);
1605 (void) memset(quantize_info,0,sizeof(QuantizeInfo));
1606 quantize_info->number_colors=256;
1607 quantize_info->dither=True;
1608 quantize_info->colorspace=RGBColorspace;
1609 quantize_info->signature=MagickSignature;
1610 }
1611
1612 /*
1613 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1614 % %
1615 % %
1616 % %
1617 % G r a y s c a l e P s e u d o C l a s s I m a g e %
1618 % %
1619 % %
1620 % %
1621 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1622 %
1623 % GrayscalePseudoClassImage converts an image to a PseudoClass
1624 % grayscale representation with an (optionally) compressed and sorted
1625 % colormap. Colormap is ordered by increasing intensity.
1626 %
1627 % The format of the GrayscalePseudoClassImage method is:
1628 %
1629 % void GrayscalePseudoClassImage(Image *image)
1630 %
1631 % A description of each parameter follows:
1632 %
1633 % o image: The image.
1634 %
1635 % o optimize_colormap: If true, produce an optimimal (compact) colormap.
1636 %
1637 */
1638
1639 #if defined(__cplusplus) || defined(c_plusplus)
1640 extern "C" {
1641 #endif
1642
IntensityCompare(const void * x,const void * y)1643 static int IntensityCompare(const void *x,const void *y)
1644 {
1645 long
1646 intensity;
1647
1648 PixelPacket
1649 *color_1,
1650 *color_2;
1651
1652 color_1=(PixelPacket *) x;
1653 color_2=(PixelPacket *) y;
1654 intensity=PixelIntensityToQuantum(color_1)-
1655 (long) PixelIntensityToQuantum(color_2);
1656 return(intensity);
1657 }
1658
1659 #if defined(__cplusplus) || defined(c_plusplus)
1660 }
1661 #endif
1662
GrayscalePseudoClassImage(Image * image,unsigned int optimize_colormap)1663 MagickExport void GrayscalePseudoClassImage(Image *image,
1664 unsigned int optimize_colormap)
1665 {
1666 long
1667 y;
1668
1669 register long
1670 x;
1671
1672 register IndexPacket
1673 *indexes;
1674
1675 register const PixelPacket
1676 *q;
1677
1678 register unsigned int
1679 i;
1680
1681 int
1682 *colormap_index=(int *) NULL;
1683
1684 assert(image != (Image *) NULL);
1685 assert(image->signature == MagickSignature);
1686
1687 if (!image->is_grayscale)
1688 (void) TransformColorspace(image,GRAYColorspace);
1689
1690 if (image->storage_class != PseudoClass)
1691 {
1692 /*
1693 Allocate maximum sized grayscale image colormap
1694 */
1695 if (!AllocateImageColormap(image,MaxColormapSize))
1696 {
1697 ThrowException3(&image->exception,ResourceLimitError,
1698 MemoryAllocationFailed,UnableToSortImageColormap);
1699 return;
1700 }
1701
1702 if (optimize_colormap)
1703 {
1704 /*
1705 Use minimal colormap method.
1706 */
1707
1708 /*
1709 Allocate memory for colormap index
1710 */
1711 colormap_index=MagickAllocateMemory(int *,MaxColormapSize*sizeof(int));
1712 if (colormap_index == (int *) NULL)
1713 {
1714 ThrowException3(&image->exception,ResourceLimitError,
1715 MemoryAllocationFailed,UnableToSortImageColormap);
1716 return;
1717 }
1718
1719 /*
1720 Initial colormap index value is -1 so we can tell if it
1721 is initialized.
1722 */
1723 for (i=0; i < MaxColormapSize; i++)
1724 colormap_index[i]=-1;
1725
1726 image->colors=0;
1727 for (y=0; y < (long) image->rows; y++)
1728 {
1729 q=GetImagePixels(image,0,y,image->columns,1);
1730 if (q == (PixelPacket *) NULL)
1731 break;
1732 indexes=AccessMutableIndexes(image);
1733 for (x=(long) image->columns; x > 0; x--)
1734 {
1735 register int
1736 intensity;
1737
1738 /*
1739 If index is new, create index to colormap
1740 */
1741 intensity=ScaleQuantumToMap(q->red);
1742 if (colormap_index[intensity] < 0)
1743 {
1744 colormap_index[intensity]=image->colors;
1745 image->colormap[image->colors]=*q;
1746 image->colors++;
1747 }
1748 *indexes++=colormap_index[intensity];
1749 q++;
1750 }
1751 if (!SyncImagePixels(image))
1752 {
1753 MagickFreeMemory(colormap_index);
1754 return;
1755 }
1756 }
1757 }
1758 else
1759 {
1760 /*
1761 Use fast-cut linear colormap method.
1762 */
1763 for (y=0; y < (long) image->rows; y++)
1764 {
1765 q=GetImagePixels(image,0,y,image->columns,1);
1766 if (q == (PixelPacket *) NULL)
1767 break;
1768 indexes=AccessMutableIndexes(image);
1769 for (x=(long) image->columns; x > 0; x--)
1770 {
1771 *indexes=ScaleQuantumToIndex(q->red);
1772 q++;
1773 indexes++;
1774 }
1775 if (!SyncImagePixels(image))
1776 break;
1777 }
1778 image->is_grayscale=True;
1779 return;
1780 }
1781 }
1782
1783 if (optimize_colormap)
1784 {
1785 /*
1786 Sort and compact the colormap
1787 */
1788
1789 /*
1790 Allocate memory for colormap index
1791 */
1792 if (colormap_index == (int *) NULL)
1793 {
1794 colormap_index=MagickAllocateArray(int *,MaxColormapSize,sizeof(int));
1795 if (colormap_index == (int *) NULL)
1796 {
1797 ThrowException3(&image->exception,ResourceLimitError,
1798 MemoryAllocationFailed,UnableToSortImageColormap);
1799 return;
1800 }
1801 }
1802
1803 /*
1804 Assign index values to colormap entries.
1805 */
1806 for (i=0; i < image->colors; i++)
1807 image->colormap[i].opacity=(unsigned short) i;
1808 /*
1809 Sort image colormap by increasing intensity.
1810 */
1811 qsort((void *) image->colormap,image->colors,sizeof(PixelPacket),
1812 IntensityCompare);
1813 /*
1814 Create mapping between original indexes and reduced/sorted
1815 colormap.
1816 */
1817 {
1818 PixelPacket
1819 *new_colormap;
1820
1821 int
1822 j;
1823
1824 new_colormap=MagickAllocateMemory(PixelPacket *,image->colors*sizeof(PixelPacket));
1825 if (new_colormap == (PixelPacket *) NULL)
1826 {
1827 MagickFreeMemory(colormap_index);
1828 ThrowException3(&image->exception,ResourceLimitError,
1829 MemoryAllocationFailed,UnableToSortImageColormap);
1830 return;
1831 }
1832
1833 j=0;
1834 new_colormap[j]=image->colormap[0];
1835 for (i=0; i < image->colors; i++)
1836 {
1837 if (NotColorMatch(&new_colormap[j],&image->colormap[i]))
1838 {
1839 j++;
1840 new_colormap[j]=image->colormap[i];
1841 }
1842
1843 colormap_index[image->colormap[i].opacity]=j;
1844 }
1845 image->colors=j+1;
1846 MagickFreeMemory(image->colormap);
1847 image->colormap=new_colormap;
1848 }
1849
1850 /*
1851 Reassign image colormap indexes
1852 */
1853 for (y=0; y < (long) image->rows; y++)
1854 {
1855 q=GetImagePixels(image,0,y,image->columns,1);
1856 if (q == (PixelPacket *) NULL)
1857 break;
1858 indexes=AccessMutableIndexes(image);
1859 for (x=(long) image->columns; x > 0; x--)
1860 {
1861 *indexes=colormap_index[*indexes];
1862 indexes++;
1863 }
1864 if (!SyncImagePixels(image))
1865 break;
1866 }
1867 MagickFreeMemory(colormap_index);
1868 }
1869 image->is_monochrome=IsMonochromeImage(image,&image->exception);
1870 image->is_grayscale=True;
1871 }
1872
1873 /*
1874 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1875 % %
1876 % %
1877 % %
1878 + H i l b e r t C u r v e %
1879 % %
1880 % %
1881 % %
1882 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1883 %
1884 % HilbertCurve() s a space filling curve that visits every point in a square
1885 % grid with any power of 2. Hilbert is useful in dithering due to the
1886 % coherence between neighboring pixels. Here, the quantization error is
1887 % distributed along the Hilbert curve.
1888 %
1889 % This is a recursive function.
1890 %
1891 % The format of the HilbertCurve method is:
1892 %
1893 % void HilbertCurve(CubeInfo *cube_info,Image *image,
1894 % const unsigned long level,const unsigned int direction)
1895 %
1896 % A description of each parameter follows.
1897 %
1898 % o cube_info: A pointer to the Cube structure.
1899 %
1900 % o image: Specifies a pointer to an Image structure; returned from
1901 % ReadImage.
1902 %
1903 % o direction: This unsigned direction describes which direction
1904 % to move to next to follow the Hilbert curve.
1905 %
1906 %
1907 */
HilbertCurve(CubeInfo * cube_info,Image * image,const unsigned long level,const unsigned int direction)1908 static void HilbertCurve(CubeInfo *cube_info,Image *image,
1909 const unsigned long level,const unsigned int direction)
1910 {
1911 if (level == 1)
1912 {
1913 switch (direction)
1914 {
1915 case WestGravity:
1916 {
1917 (void) Dither(cube_info,image,EastGravity);
1918 (void) Dither(cube_info,image,SouthGravity);
1919 (void) Dither(cube_info,image,WestGravity);
1920 break;
1921 }
1922 case EastGravity:
1923 {
1924 (void) Dither(cube_info,image,WestGravity);
1925 (void) Dither(cube_info,image,NorthGravity);
1926 (void) Dither(cube_info,image,EastGravity);
1927 break;
1928 }
1929 case NorthGravity:
1930 {
1931 (void) Dither(cube_info,image,SouthGravity);
1932 (void) Dither(cube_info,image,EastGravity);
1933 (void) Dither(cube_info,image,NorthGravity);
1934 break;
1935 }
1936 case SouthGravity:
1937 {
1938 (void) Dither(cube_info,image,NorthGravity);
1939 (void) Dither(cube_info,image,WestGravity);
1940 (void) Dither(cube_info,image,SouthGravity);
1941 break;
1942 }
1943 default:
1944 break;
1945 }
1946 return;
1947 }
1948 switch (direction)
1949 {
1950 case WestGravity:
1951 {
1952 HilbertCurve(cube_info,image,level-1,NorthGravity);
1953 (void) Dither(cube_info,image,EastGravity);
1954 HilbertCurve(cube_info,image,level-1,WestGravity);
1955 (void) Dither(cube_info,image,SouthGravity);
1956 HilbertCurve(cube_info,image,level-1,WestGravity);
1957 (void) Dither(cube_info,image,WestGravity);
1958 HilbertCurve(cube_info,image,level-1,SouthGravity);
1959 break;
1960 }
1961 case EastGravity:
1962 {
1963 HilbertCurve(cube_info,image,level-1,SouthGravity);
1964 (void) Dither(cube_info,image,WestGravity);
1965 HilbertCurve(cube_info,image,level-1,EastGravity);
1966 (void) Dither(cube_info,image,NorthGravity);
1967 HilbertCurve(cube_info,image,level-1,EastGravity);
1968 (void) Dither(cube_info,image,EastGravity);
1969 HilbertCurve(cube_info,image,level-1,NorthGravity);
1970 break;
1971 }
1972 case NorthGravity:
1973 {
1974 HilbertCurve(cube_info,image,level-1,WestGravity);
1975 (void) Dither(cube_info,image,SouthGravity);
1976 HilbertCurve(cube_info,image,level-1,NorthGravity);
1977 (void) Dither(cube_info,image,EastGravity);
1978 HilbertCurve(cube_info,image,level-1,NorthGravity);
1979 (void) Dither(cube_info,image,NorthGravity);
1980 HilbertCurve(cube_info,image,level-1,EastGravity);
1981 break;
1982 }
1983 case SouthGravity:
1984 {
1985 HilbertCurve(cube_info,image,level-1,EastGravity);
1986 (void) Dither(cube_info,image,NorthGravity);
1987 HilbertCurve(cube_info,image,level-1,SouthGravity);
1988 (void) Dither(cube_info,image,WestGravity);
1989 HilbertCurve(cube_info,image,level-1,SouthGravity);
1990 (void) Dither(cube_info,image,SouthGravity);
1991 HilbertCurve(cube_info,image,level-1,WestGravity);
1992 break;
1993 }
1994 default:
1995 break;
1996 }
1997 }
1998
1999 /*
2000 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2001 % %
2002 % %
2003 % %
2004 % M a p I m a g e %
2005 % %
2006 % %
2007 % %
2008 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2009 %
2010 % MapImage() replaces the colors of an image with the closest color from a
2011 % reference image.
2012 %
2013 % The format of the MapImage method is:
2014 %
2015 % unsigned int MapImage(Image *image,const Image *map_image,
2016 % const unsigned int dither)
2017 %
2018 % A description of each parameter follows:
2019 %
2020 % o image: Specifies a pointer to an Image structure.
2021 %
2022 % o map_image: Specifies a pointer to an Image structure. Reduce
2023 % image to a set of colors represented by this image.
2024 %
2025 % o dither: Set this integer value to something other than zero to
2026 % dither the quantized image.
2027 %
2028 %
2029 */
MapImage(Image * image,const Image * map_image,const unsigned int dither)2030 MagickExport MagickPassFail MapImage(Image *image,const Image *map_image,
2031 const unsigned int dither)
2032 {
2033 CubeInfo
2034 *cube_info;
2035
2036 QuantizeInfo
2037 quantize_info;
2038
2039 MagickPassFail
2040 status=MagickPass;
2041
2042 /*
2043 Initialize color cube.
2044 */
2045 assert(image != (Image *) NULL);
2046 assert(image->signature == MagickSignature);
2047 assert(map_image != (Image *) NULL);
2048 assert(map_image->signature == MagickSignature);
2049 GetQuantizeInfo(&quantize_info);
2050 quantize_info.dither=dither;
2051 quantize_info.colorspace=
2052 image->matte ? TransparentColorspace : RGBColorspace;
2053 cube_info=GetCubeInfo(&quantize_info,MaxTreeDepth);
2054 if (cube_info == (CubeInfo *) NULL)
2055 ThrowBinaryException3(ResourceLimitError,MemoryAllocationFailed,
2056 UnableToMapImage);
2057 status=ClassifyImageColors(cube_info,map_image,&image->exception);
2058 if (status != MagickFail)
2059 {
2060 /*
2061 Classify image colors from the reference image.
2062 */
2063 quantize_info.number_colors=cube_info->colors;
2064 status=AssignImageColors(cube_info,image);
2065 }
2066 DestroyCubeInfo(cube_info);
2067 return(status);
2068 }
2069
2070 /*
2071 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2072 % %
2073 % %
2074 % %
2075 % M a p I m a g e s %
2076 % %
2077 % %
2078 % %
2079 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2080 %
2081 % MapImages() replaces the colors of a sequence of images with the closest
2082 % color from a reference image. If the reference image does not contain a
2083 % colormap, then a colormap will be created based on existing colors in the
2084 % reference image. The order and number of colormap entries does not match
2085 % the reference image. If the order and number of colormap entries needs to
2086 % match the reference image, then the ReplaceImageColormap() function may be
2087 % used after invoking MapImages() in order to apply the reference colormap.
2088 %
2089 % The format of the MapImage method is:
2090 %
2091 % unsigned int MapImages(Image *images,Image *map_image,
2092 % const unsigned int dither)
2093 %
2094 % A description of each parameter follows:
2095 %
2096 % o image: Specifies a pointer to a set of Image structures.
2097 %
2098 % o map_image: Specifies a pointer to an Image structure. Reduce
2099 % image to a set of colors represented by this image.
2100 %
2101 % o dither: Set this integer value to something other than zero to
2102 % dither the quantized image.
2103 %
2104 %
2105 */
MapImages(Image * images,const Image * map_image,const unsigned int dither)2106 MagickExport MagickPassFail MapImages(Image *images,const Image *map_image,
2107 const unsigned int dither)
2108 {
2109 CubeInfo
2110 *cube_info;
2111
2112 Image
2113 *image;
2114
2115 QuantizeInfo
2116 quantize_info;
2117
2118 MagickPassFail
2119 status;
2120
2121 assert(images != (Image *) NULL);
2122 assert(images->signature == MagickSignature);
2123 GetQuantizeInfo(&quantize_info);
2124 quantize_info.dither=dither;
2125 image=images;
2126 if (map_image == (Image *) NULL)
2127 {
2128 /*
2129 Create a global colormap for an image sequence.
2130 */
2131 for ( ; image != (Image *) NULL; image=image->next)
2132 if (image->matte)
2133 quantize_info.colorspace=TransparentColorspace;
2134 status=QuantizeImages(&quantize_info,images);
2135 return(status);
2136 }
2137 /*
2138 Classify image colors from the reference image.
2139 */
2140 cube_info=GetCubeInfo(&quantize_info,8);
2141 if (cube_info == (CubeInfo *) NULL)
2142 ThrowBinaryException3(ResourceLimitError,MemoryAllocationFailed,
2143 UnableToMapImageSequence);
2144 status=ClassifyImageColors(cube_info,map_image,&image->exception);
2145 if (status != MagickFail)
2146 {
2147 /*
2148 Classify image colors from the reference image.
2149 */
2150 quantize_info.number_colors=cube_info->colors;
2151 for (image=images; image != (Image *) NULL; image=image->next)
2152 {
2153 quantize_info.colorspace=image->matte ? TransparentColorspace :
2154 RGBColorspace;
2155 status=AssignImageColors(cube_info,image);
2156 if (status == MagickFail)
2157 break;
2158 }
2159 }
2160 DestroyCubeInfo(cube_info);
2161 return(status);
2162 }
2163
2164 /*
2165 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2166 % %
2167 % %
2168 % %
2169 % O r d e r e d D i t h e r I m a g e %
2170 % %
2171 % %
2172 % %
2173 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2174 %
2175 % OrderedDitherImage() uses the ordered dithering technique of reducing color
2176 % images to monochrome using positional information to retain as much
2177 % information as possible.
2178 %
2179 % The format of the OrderedDitherImage method is:
2180 %
2181 % unsigned int OrderedDitherImage(Image *image)
2182 %
2183 % A description of each parameter follows.
2184 %
2185 % o image: Specifies a pointer to an Image structure; returned from
2186 % ReadImage.
2187 %
2188 %
2189 */
OrderedDitherImage(Image * image)2190 MagickExport MagickPassFail OrderedDitherImage(Image *image)
2191 {
2192 #define DitherImageText "[%s] Ordered dither..."
2193
2194 static const Quantum
2195 DitherMatrix[8][8] =
2196 {
2197 { 0, 192, 48, 240, 12, 204, 60, 252 },
2198 { 128, 64, 176, 112, 140, 76, 188, 124 },
2199 { 32, 224, 16, 208, 44, 236, 28, 220 },
2200 { 160, 96, 144, 80, 172, 108, 156, 92 },
2201 { 8, 200, 56, 248, 4, 196, 52, 244 },
2202 { 136, 72, 184, 120, 132, 68, 180, 116 },
2203 { 40, 232, 24, 216, 36, 228, 20, 212 },
2204 { 168, 104, 152, 88, 164, 100, 148, 84 }
2205 };
2206
2207 long
2208 y;
2209
2210 MagickPassFail
2211 status=MagickPass;
2212
2213 /*
2214 Initialize colormap.
2215 */
2216 (void) NormalizeImage(image);
2217 if (!AllocateImageColormap(image,2))
2218 ThrowBinaryException3(ResourceLimitError,MemoryAllocationFailed,
2219 UnableToDitherImage);
2220 /*
2221 Dither image with the ordered dithering technique.
2222 FIXME: Use OpenMP?
2223 */
2224 for (y=0; y < (long) image->rows; y++)
2225 {
2226 IndexPacket
2227 index;
2228
2229 register IndexPacket
2230 *indexes;
2231
2232 register long
2233 x;
2234
2235 register PixelPacket
2236 *q;
2237
2238 q=GetImagePixels(image,0,y,image->columns,1);
2239 if (q == (PixelPacket *) NULL)
2240 {
2241 status=MagickFail;
2242 break;
2243 }
2244 indexes=AccessMutableIndexes(image);
2245 for (x=0; x < (long) image->columns; x++)
2246 {
2247 index=(Quantum) (PixelIntensityToQuantum(q) >
2248 ScaleCharToQuantum(DitherMatrix[y & 0x07][x & 0x07]) ? 1 : 0);
2249 indexes[x]=index;
2250 q->red=image->colormap[index].red;
2251 q->green=image->colormap[index].green;
2252 q->blue=image->colormap[index].blue;
2253 q++;
2254 }
2255 if (!SyncImagePixels(image))
2256 {
2257 status=MagickFail;
2258 break;
2259 }
2260 if (QuantumTick(y,image->rows))
2261 if (!MagickMonitorFormatted(y,image->rows,&image->exception,
2262 DitherImageText,image->filename))
2263 {
2264 status=MagickFail;
2265 break;
2266 }
2267 }
2268 return(status);
2269 }
2270
2271 /*
2272 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2273 % %
2274 % %
2275 % %
2276 + P r u n e C h i l d %
2277 % %
2278 % %
2279 % %
2280 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2281 %
2282 % PruneChild() deletes the given node and merges its statistics into its
2283 % parent.
2284 %
2285 % This is a recursive function.
2286 %
2287 % The format of the PruneSubtree method is:
2288 %
2289 % PruneChild(CubeInfo *cube_info,const NodeInfo *node_info)
2290 %
2291 % A description of each parameter follows.
2292 %
2293 % o cube_info: A pointer to the Cube structure.
2294 %
2295 % o node_info: pointer to node in color cube tree that is to be pruned.
2296 %
2297 %
2298 */
PruneChild(CubeInfo * cube_info,const NodeInfo * node_info)2299 static void PruneChild(CubeInfo *cube_info,const NodeInfo *node_info)
2300 {
2301 NodeInfo
2302 *parent;
2303
2304 register unsigned int
2305 id;
2306
2307 /*
2308 Traverse any children.
2309 */
2310 for (id=0; id < MaxTreeDepth; id++)
2311 if (node_info->child[id] != (NodeInfo *) NULL)
2312 PruneChild(cube_info,node_info->child[id]);
2313 /*
2314 Merge color statistics into parent.
2315 */
2316 parent=node_info->parent;
2317 parent->number_unique+=node_info->number_unique;
2318 parent->total_red+=node_info->total_red;
2319 parent->total_green+=node_info->total_green;
2320 parent->total_blue+=node_info->total_blue;
2321 parent->child[node_info->id]=(NodeInfo *) NULL;
2322 cube_info->nodes--;
2323 }
2324
2325 /*
2326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2327 % %
2328 % %
2329 % %
2330 + P r u n e L e v e l %
2331 % %
2332 % %
2333 % %
2334 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2335 %
2336 % PruneLevel() deletes all nodes at the bottom level of the color tree merging
2337 % their color statistics into their parent node.
2338 %
2339 % This is a recursive function.
2340 %
2341 % The format of the PruneLevel method is:
2342 %
2343 % PruneLevel(CubeInfo *cube_info,const NodeInfo *node_info)
2344 %
2345 % A description of each parameter follows.
2346 %
2347 % o cube_info: A pointer to the Cube structure.
2348 %
2349 % o node_info: pointer to node in color cube tree that is to be pruned.
2350 %
2351 %
2352 */
PruneLevel(CubeInfo * cube_info,const NodeInfo * node_info)2353 static void PruneLevel(CubeInfo *cube_info,const NodeInfo *node_info)
2354 {
2355 register unsigned int
2356 id;
2357
2358 /*
2359 Traverse any children.
2360 */
2361 for (id=0; id < MaxTreeDepth; id++)
2362 if (node_info->child[id] != (NodeInfo *) NULL)
2363 PruneLevel(cube_info,node_info->child[id]);
2364 if (node_info->level == cube_info->depth)
2365 PruneChild(cube_info,node_info);
2366 }
2367
2368 /*
2369 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2370 % %
2371 % %
2372 % %
2373 + P r u n e T o C u b e D e p t h %
2374 % %
2375 % %
2376 % %
2377 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2378 %
2379 % PruneToCubeDepth() deletes any nodes ar a depth greater than
2380 % cube_info->depth while merging their color statistics into their parent
2381 % node.
2382 %
2383 % This is a recursive function.
2384 %
2385 % The format of the PruneToCubeDepth method is:
2386 %
2387 % PruneToCubeDepth(CubeInfo *cube_info,const NodeInfo *node_info)
2388 %
2389 % A description of each parameter follows.
2390 %
2391 % o cube_info: A pointer to the Cube structure.
2392 %
2393 % o node_info: pointer to node in color cube tree that is to be pruned.
2394 %
2395 %
2396 */
PruneToCubeDepth(CubeInfo * cube_info,const NodeInfo * node_info)2397 static void PruneToCubeDepth(CubeInfo *cube_info,const NodeInfo *node_info)
2398 {
2399 register unsigned int
2400 id;
2401
2402 /*
2403 Traverse any children.
2404 */
2405 for (id=0; id < MaxTreeDepth; id++)
2406 if (node_info->child[id] != (NodeInfo *) NULL)
2407 PruneToCubeDepth(cube_info,node_info->child[id]);
2408 if (node_info->level > cube_info->depth)
2409 PruneChild(cube_info,node_info);
2410 }
2411
2412 /*
2413 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2414 % %
2415 % %
2416 % %
2417 % Q u a n t i z e I m a g e %
2418 % %
2419 % %
2420 % %
2421 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2422 %
2423 % QuantizeImage() analyzes the colors within a reference image and chooses a
2424 % fixed number of colors to represent the image. The goal of the algorithm
2425 % is to minimize the color difference between the input and output image while
2426 % minimizing the processing time.
2427 %
2428 % The format of the QuantizeImage method is:
2429 %
2430 % unsigned int QuantizeImage(const QuantizeInfo *quantize_info,
2431 % Image *image)
2432 %
2433 % A description of each parameter follows:
2434 %
2435 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2436 %
2437 % o image: Specifies a pointer to an Image structure.
2438 %
2439 */
QuantizeImage(const QuantizeInfo * quantize_info,Image * image)2440 MagickExport MagickPassFail QuantizeImage(const QuantizeInfo *quantize_info,
2441 Image *image)
2442 {
2443 CubeInfo
2444 *cube_info;
2445
2446 MagickPassFail
2447 status;
2448
2449 unsigned long
2450 depth,
2451 number_colors;
2452
2453 assert(quantize_info != (const QuantizeInfo *) NULL);
2454 assert(quantize_info->signature == MagickSignature);
2455 assert(image != (Image *) NULL);
2456 assert(image->signature == MagickSignature);
2457 number_colors=quantize_info->number_colors;
2458 if (number_colors == 0)
2459 number_colors=MaxColormapSize;
2460 if (number_colors > MaxColormapSize)
2461 number_colors=MaxColormapSize;
2462 /*
2463 For grayscale images, use a fast translation to PseudoClass,
2464 which assures that the maximum number of colors is equal to, or
2465 less than MaxColormapSize.
2466 */
2467 if (IsGrayColorspace(quantize_info->colorspace))
2468 (void) TransformColorspace(image,quantize_info->colorspace);
2469 if (IsGrayImage(image,&image->exception))
2470 GrayscalePseudoClassImage(image,True);
2471 /*
2472 If the image colors do not require further reduction, then simply
2473 return.
2474 */
2475 if ((image->storage_class == PseudoClass) &&
2476 (image->colors <= number_colors))
2477 return(MagickPass);
2478 depth=quantize_info->tree_depth;
2479 if (depth == 0)
2480 {
2481 unsigned long
2482 colors;
2483
2484 /*
2485 Depth of color tree is: Log4(colormap size)+2.
2486 */
2487 colors=number_colors;
2488 for (depth=1; colors != 0; depth++)
2489 colors>>=2;
2490 if (quantize_info->dither)
2491 depth--;
2492 if (image->storage_class == PseudoClass)
2493 depth+=2;
2494 }
2495 /*
2496 Initialize color cube.
2497 */
2498 cube_info=GetCubeInfo(quantize_info,depth);
2499 if (cube_info == (CubeInfo *) NULL)
2500 ThrowBinaryException3(ResourceLimitError,
2501 MemoryAllocationFailed,UnableToQuantizeImage);
2502 if (quantize_info->colorspace != RGBColorspace)
2503 (void) TransformColorspace(image,quantize_info->colorspace);
2504 status=ClassifyImageColors(cube_info,image,&image->exception);
2505 if (status != MagickFail)
2506 {
2507 /*
2508 Reduce the number of colors in the image.
2509 */
2510 ReduceImageColors(image->filename,cube_info,number_colors,&image->exception);
2511 status=AssignImageColors(cube_info,image);
2512 if (quantize_info->colorspace != RGBColorspace)
2513 (void) TransformColorspace(image,quantize_info->colorspace);
2514 }
2515 DestroyCubeInfo(cube_info);
2516 return(status);
2517 }
2518
2519 /*
2520 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2521 % %
2522 % %
2523 % %
2524 % Q u a n t i z e I m a g e s %
2525 % %
2526 % %
2527 % %
2528 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2529 %
2530 % QuantizeImages() analyzes the colors within a set of reference images and
2531 % chooses a fixed number of colors to represent the set. The goal of the
2532 % algorithm is to minimize the color difference between the input and output
2533 % images while minimizing the processing time.
2534 %
2535 % The format of the QuantizeImages method is:
2536 %
2537 % unsigned int QuantizeImages(const QuantizeInfo *quantize_info,
2538 % Image *images)
2539 %
2540 % A description of each parameter follows:
2541 %
2542 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2543 %
2544 % o images: Specifies a pointer to a list of Image structures.
2545 %
2546 %
2547 */
QuantizeImages(const QuantizeInfo * quantize_info,Image * images)2548 MagickExport MagickPassFail QuantizeImages(const QuantizeInfo *quantize_info,
2549 Image *images)
2550 {
2551 CubeInfo
2552 *cube_info;
2553
2554 int
2555 depth;
2556
2557 MonitorHandler
2558 handler;
2559
2560 Image
2561 *image;
2562
2563 register long
2564 i;
2565
2566 unsigned int
2567 status;
2568
2569 unsigned long
2570 number_colors,
2571 number_images;
2572
2573 assert(quantize_info != (const QuantizeInfo *) NULL);
2574 assert(quantize_info->signature == MagickSignature);
2575 assert(images != (Image *) NULL);
2576 assert(images->signature == MagickSignature);
2577 if (images->next == (Image *) NULL)
2578 {
2579 /*
2580 Handle a single image with QuantizeImage.
2581 */
2582 status=QuantizeImage(quantize_info,images);
2583 return(status);
2584 }
2585 status=False;
2586 image=images;
2587 number_colors=quantize_info->number_colors;
2588 if (number_colors == 0)
2589 number_colors=MaxColormapSize;
2590 if (number_colors > MaxColormapSize)
2591 number_colors=MaxColormapSize;
2592 depth=quantize_info->tree_depth;
2593 if (depth == 0)
2594 {
2595 int
2596 pseudo_class;
2597
2598 unsigned long
2599 colors;
2600
2601 /*
2602 Depth of color tree is: Log4(colormap size)+2.
2603 */
2604 colors=number_colors;
2605 for (depth=1; colors != 0; depth++)
2606 colors>>=2;
2607 if (quantize_info->dither)
2608 depth--;
2609 pseudo_class=True;
2610 for (image=images; image != (Image *) NULL; image=image->next)
2611 pseudo_class|=(image->storage_class == PseudoClass);
2612 if (pseudo_class)
2613 depth+=2;
2614 }
2615 /*
2616 Initialize color cube.
2617 */
2618 cube_info=GetCubeInfo(quantize_info,depth);
2619 if (cube_info == (CubeInfo *) NULL)
2620 ThrowBinaryException3(ResourceLimitError,MemoryAllocationFailed,
2621 UnableToQuantizeImageSequence);
2622 image=images;
2623 for (i=0; image != (Image *) NULL; i++)
2624 {
2625 if (quantize_info->colorspace != RGBColorspace)
2626 (void) TransformColorspace(image,quantize_info->colorspace);
2627 image=image->next;
2628 }
2629 number_images=i;
2630 image=images;
2631 for (i=0; image != (Image *) NULL; i++)
2632 {
2633 handler=SetMonitorHandler((MonitorHandler) NULL);
2634 status=ClassifyImageColors(cube_info,image,&image->exception);
2635 if (status == MagickFail)
2636 break;
2637 image=image->next;
2638 (void) SetMonitorHandler(handler);
2639 if ((image != (Image *) NULL) &&
2640 (!MagickMonitorFormatted(i,number_images,&image->exception,
2641 ClassifyImageText,image->filename)))
2642 break;
2643 }
2644 if (status != MagickFail)
2645 {
2646 /*
2647 Reduce the number of colors in an image sequence.
2648 */
2649 ReduceImageColors(image->filename,cube_info,number_colors,&image->exception);
2650 image=images;
2651 for (i=0; image != (Image *) NULL; i++)
2652 {
2653 handler=SetMonitorHandler((MonitorHandler) NULL);
2654 status=AssignImageColors(cube_info,image);
2655 if (status == MagickFail)
2656 break;
2657 if (quantize_info->colorspace != RGBColorspace)
2658 (void) TransformColorspace(image,quantize_info->colorspace);
2659 image=image->next;
2660 (void) SetMonitorHandler(handler);
2661 if ((image != (Image *) NULL) &&
2662 (!MagickMonitorFormatted(i,number_images,&image->exception,
2663 AssignImageText,image->filename)))
2664 {
2665 status=MagickFail;
2666 break;
2667 }
2668 }
2669 }
2670 DestroyCubeInfo(cube_info);
2671 return(status);
2672 }
2673
2674 /*
2675 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2676 % %
2677 % %
2678 % %
2679 + R e d u c e %
2680 % %
2681 % %
2682 % %
2683 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2684 %
2685 % Reduce() traverses the color cube tree and prunes any node whose
2686 % quantization error falls below a particular threshold.
2687 %
2688 % This is a recursive function.
2689 %
2690 % The format of the Reduce method is:
2691 %
2692 % Reduce(CubeInfo *cube_info,const NodeInfo *node_info)
2693 %
2694 % A description of each parameter follows.
2695 %
2696 % o cube_info: A pointer to the Cube structure.
2697 %
2698 % o node_info: pointer to node in color cube tree that is to be pruned.
2699 %
2700 %
2701 */
Reduce(CubeInfo * cube_info,const NodeInfo * node_info)2702 static void Reduce(CubeInfo *cube_info,const NodeInfo *node_info)
2703 {
2704 register unsigned int
2705 id;
2706
2707 /*
2708 Traverse any children.
2709 */
2710 for (id=0; id < MaxTreeDepth; id++)
2711 if (node_info->child[id] != (NodeInfo *) NULL)
2712 Reduce(cube_info,node_info->child[id]);
2713 if (node_info->quantize_error <= cube_info->pruning_threshold)
2714 PruneChild(cube_info,node_info);
2715 else
2716 {
2717 /*
2718 Find minimum pruning threshold.
2719 */
2720 if (node_info->number_unique > 0)
2721 cube_info->colors++;
2722 if (node_info->quantize_error < cube_info->next_threshold)
2723 cube_info->next_threshold=node_info->quantize_error;
2724 }
2725 }
2726
2727 /*
2728 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2729 % %
2730 % %
2731 % %
2732 + R e d u c e I m a g e C o l o r s %
2733 % %
2734 % %
2735 % %
2736 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2737 %
2738 % ReduceImageColors() repeatedly prunes the tree until the number of nodes
2739 % with n2 > 0 is less than or equal to the maximum number of colors allowed
2740 % in the output image. On any given iteration over the tree, it selects
2741 % those nodes whose E value is minimal for pruning and merges their
2742 % color statistics upward. It uses a pruning threshold, Ep, to govern
2743 % node selection as follows:
2744 %
2745 % Ep = 0
2746 % while number of nodes with (n2 > 0) > required maximum number of colors
2747 % prune all nodes such that E <= Ep
2748 % Set Ep to minimum E in remaining nodes
2749 %
2750 % This has the effect of minimizing any quantization error when merging
2751 % two nodes together.
2752 %
2753 % When a node to be pruned has offspring, the pruning procedure invokes
2754 % itself recursively in order to prune the tree from the leaves upward.
2755 % n2, Sr, Sg, and Sb in a node being pruned are always added to the
2756 % corresponding data in that node's parent. This retains the pruned
2757 % node's color characteristics for later averaging.
2758 %
2759 % For each node, n2 pixels exist for which that node represents the
2760 % smallest volume in RGB space containing those pixel's colors. When n2
2761 % > 0 the node will uniquely define a color in the output image. At the
2762 % beginning of reduction, n2 = 0 for all nodes except a the leaves of
2763 % the tree which represent colors present in the input image.
2764 %
2765 % The other pixel count, n1, indicates the total number of colors
2766 % within the cubic volume which the node represents. This includes n1 -
2767 % n2 pixels whose colors should be defined by nodes at a lower level in
2768 % the tree.
2769 %
2770 % The format of the ReduceImageColors method is:
2771 %
2772 % ReduceImageColors(const char *filename, CubeInfo *cube_info,
2773 % const unsigned int number_colors, ExceptionInfo *exception)
2774 %
2775 % A description of each parameter follows.
2776 %
2777 % o filename: Filename for use in progress messages.
2778 %
2779 % o cube_info: A pointer to the Cube structure.
2780 %
2781 % o number_colors: This integer value indicates the maximum number of
2782 % colors in the quantized image or colormap. The actual number of
2783 % colors allocated to the colormap may be less than this value, but
2784 % never more.
2785 %
2786 % o exception: Return any errors or warnings in this structure.
2787 %
2788 */
ReduceImageColors(const char * filename,CubeInfo * cube_info,const unsigned long number_colors,ExceptionInfo * exception)2789 static void ReduceImageColors(const char *filename,CubeInfo *cube_info,
2790 const unsigned long number_colors,ExceptionInfo *exception)
2791 {
2792 #define ReduceImageText "[%s] Reduce colors: %lu..."
2793
2794 unsigned int
2795 status;
2796
2797 unsigned long
2798 span;
2799
2800 span=cube_info->colors;
2801 cube_info->next_threshold=0.0;
2802 while (cube_info->colors > number_colors)
2803 {
2804 cube_info->pruning_threshold=cube_info->next_threshold;
2805 cube_info->next_threshold=cube_info->root->quantize_error-1;
2806 cube_info->colors=0;
2807 Reduce(cube_info,cube_info->root);
2808 status=MagickMonitorFormatted(span-cube_info->colors,
2809 (size_t) span-number_colors+1,exception,
2810 ReduceImageText,
2811 filename,
2812 number_colors);
2813 if (status == False)
2814 break;
2815 }
2816 }
2817