1 /*
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 % Cristy %
17 % July 1992 %
18 % %
19 % %
20 % Copyright 1999-2021 ImageMagick Studio LLC, a non-profit organization %
21 % 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 % https://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 (vertex
65 % nearest the origin in RGB space and the vertex farthest from the origin).
66 %
67 % The tree's root node represents the entire domain, (0,0,0) through
68 % (Cmax,Cmax,Cmax). Each lower level in the tree is generated by
69 % subdividing one node's cube into eight smaller cubes of equal size.
70 % This corresponds to bisecting the parent cube with planes passing
71 % through the midpoints of each edge.
72 %
73 % The basic algorithm operates in three phases: Classification,
74 % Reduction, and Assignment. Classification builds a color description
75 % tree for the image. Reduction collapses the tree until the number it
76 % represents, at most, the number of colors desired in the output image.
77 % Assignment defines the output image's color map and sets each pixel's
78 % color by restorage_class in the reduced tree. Our goal is to minimize
79 % the numerical discrepancies between the original colors and quantized
80 % colors (quantization error).
81 %
82 % Classification begins by initializing a color description tree of
83 % sufficient depth to represent each possible input color in a leaf.
84 % However, it is impractical to generate a fully-formed color description
85 % tree in the storage_class phase for realistic values of Cmax. If
86 % colors components in the input image are quantized to k-bit precision,
87 % so that Cmax= 2k-1, the tree would need k levels below the root node to
88 % allow representing each possible input color in a leaf. This becomes
89 % prohibitive because the tree's total number of nodes is 1 +
90 % sum(i=1, k, 8k).
91 %
92 % A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
93 % Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
94 % Initializes data structures for nodes only as they are needed; (2)
95 % Chooses a maximum depth for the tree as a function of the desired
96 % number of colors in the output image (currently log2(colormap size)).
97 %
98 % For each pixel in the input image, storage_class scans downward from
99 % the root of the color description tree. At each level of the tree it
100 % identifies the single node which represents a cube in RGB space
101 % containing the pixel's color. It updates the following data for each
102 % such node:
103 %
104 % n1: Number of pixels whose color is contained in the RGB cube which
105 % this node represents;
106 %
107 % n2: Number of pixels whose color is not represented in a node at
108 % lower depth in the tree; initially, n2 = 0 for all nodes except
109 % leaves of the tree.
110 %
111 % Sr, Sg, Sb: Sums of the red, green, and blue component values for all
112 % pixels not classified at a lower depth. The combination of these sums
113 % and n2 will ultimately characterize the mean color of a set of pixels
114 % represented by this node.
115 %
116 % E: the distance squared in RGB space between each pixel contained
117 % within a node and the nodes' center. This represents the
118 % quantization error for a node.
119 %
120 % Reduction repeatedly prunes the tree until the number of nodes with n2
121 % > 0 is less than or equal to the maximum number of colors allowed in
122 % the output image. On any given iteration over the tree, it selects
123 % those nodes whose E count is minimal for pruning and merges their color
124 % statistics upward. It uses a pruning threshold, Ep, to govern node
125 % selection as follows:
126 %
127 % Ep = 0
128 % while number of nodes with (n2 > 0) > required maximum number of colors
129 % prune all nodes such that E <= Ep
130 % Set Ep to minimum E in remaining nodes
131 %
132 % This has the effect of minimizing any quantization error when merging
133 % two nodes together.
134 %
135 % When a node to be pruned has offspring, the pruning procedure invokes
136 % itself recursively in order to prune the tree from the leaves upward.
137 % n2, Sr, Sg, and Sb in a node being pruned are always added to the
138 % corresponding data in that node's parent. This retains the pruned
139 % node's color characteristics for later averaging.
140 %
141 % For each node, n2 pixels exist for which that node represents the
142 % smallest volume in RGB space containing those pixel's colors. When n2
143 % > 0 the node will uniquely define a color in the output image. At the
144 % beginning of reduction, n2 = 0 for all nodes except a the leaves of
145 % the tree which represent colors present in the input image.
146 %
147 % The other pixel count, n1, indicates the total number of colors within
148 % the cubic volume which the node represents. This includes n1 - n2
149 % pixels whose colors should be defined by nodes at a lower level in the
150 % tree.
151 %
152 % Assignment generates the output image from the pruned tree. The output
153 % image consists of two parts: (1) A color map, which is an array of
154 % color descriptions (RGB triples) for each color present in the output
155 % image; (2) A pixel array, which represents each pixel as an index
156 % into the color map array.
157 %
158 % First, the assignment phase makes one pass over the pruned color
159 % description tree to establish the image's color map. For each node
160 % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean
161 % color of all pixels that classify no lower than this node. Each of
162 % these colors becomes an entry in the color map.
163 %
164 % Finally, the assignment phase reclassifies each pixel in the pruned
165 % tree to identify the deepest node containing the pixel's color. The
166 % pixel's value in the pixel array becomes the index of this node's mean
167 % color in the color map.
168 %
169 % This method is based on a similar algorithm written by Paul Raveling.
170 %
171 */
172
173 /*
174 Include declarations.
175 */
176 #include "magick/studio.h"
177 #include "magick/artifact.h"
178 #include "magick/attribute.h"
179 #include "magick/cache-view.h"
180 #include "magick/color.h"
181 #include "magick/color-private.h"
182 #include "magick/colormap.h"
183 #include "magick/colorspace.h"
184 #include "magick/colorspace-private.h"
185 #include "magick/enhance.h"
186 #include "magick/exception.h"
187 #include "magick/exception-private.h"
188 #include "magick/histogram.h"
189 #include "magick/image.h"
190 #include "magick/image-private.h"
191 #include "magick/list.h"
192 #include "magick/memory_.h"
193 #include "magick/monitor.h"
194 #include "magick/monitor-private.h"
195 #include "magick/option.h"
196 #include "magick/pixel-private.h"
197 #include "magick/quantize.h"
198 #include "magick/quantum.h"
199 #include "magick/resource_.h"
200 #include "magick/string_.h"
201 #include "magick/string-private.h"
202 #include "magick/thread-private.h"
203
204 /*
205 Define declarations.
206 */
207 #if !defined(__APPLE__) && !defined(TARGET_OS_IPHONE)
208 #define CacheShift 2
209 #else
210 #define CacheShift 3
211 #endif
212 #define ErrorQueueLength 16
213 #define ErrorRelativeWeight PerceptibleReciprocal(16)
214 #define MaxNodes 266817
215 #define MaxTreeDepth 8
216 #define NodesInAList 1920
217
218 /*
219 Typdef declarations.
220 */
221 typedef struct _NodeInfo
222 {
223 struct _NodeInfo
224 *parent,
225 *child[16];
226
227 MagickSizeType
228 number_unique;
229
230 DoublePixelPacket
231 total_color;
232
233 MagickRealType
234 quantize_error;
235
236 size_t
237 color_number,
238 id,
239 level;
240 } NodeInfo;
241
242 typedef struct _Nodes
243 {
244 NodeInfo
245 *nodes;
246
247 struct _Nodes
248 *next;
249 } Nodes;
250
251 typedef struct _CubeInfo
252 {
253 NodeInfo
254 *root;
255
256 size_t
257 colors,
258 maximum_colors;
259
260 ssize_t
261 transparent_index;
262
263 MagickSizeType
264 transparent_pixels;
265
266 DoublePixelPacket
267 target;
268
269 MagickRealType
270 distance,
271 pruning_threshold,
272 next_threshold;
273
274 size_t
275 nodes,
276 free_nodes,
277 color_number;
278
279 NodeInfo
280 *next_node;
281
282 Nodes
283 *node_queue;
284
285 MemoryInfo
286 *memory_info;
287
288 ssize_t
289 *cache;
290
291 DoublePixelPacket
292 error[ErrorQueueLength];
293
294 MagickRealType
295 diffusion,
296 weights[ErrorQueueLength];
297
298 QuantizeInfo
299 *quantize_info;
300
301 MagickBooleanType
302 associate_alpha;
303
304 ssize_t
305 x,
306 y;
307
308 size_t
309 depth;
310
311 MagickOffsetType
312 offset;
313
314 MagickSizeType
315 span;
316 } CubeInfo;
317
318 /*
319 Method prototypes.
320 */
321 static CubeInfo
322 *GetCubeInfo(const QuantizeInfo *,const size_t,const size_t);
323
324 static NodeInfo
325 *GetNodeInfo(CubeInfo *,const size_t,const size_t,NodeInfo *);
326
327 static MagickBooleanType
328 AssignImageColors(Image *,CubeInfo *),
329 ClassifyImageColors(CubeInfo *,const Image *,ExceptionInfo *),
330 DitherImage(Image *,CubeInfo *),
331 SetGrayscaleImage(Image *);
332
333 static void
334 ClosestColor(const Image *,CubeInfo *,const NodeInfo *),
335 DefineImageColormap(Image *,CubeInfo *,NodeInfo *),
336 DestroyCubeInfo(CubeInfo *),
337 PruneLevel(CubeInfo *,const NodeInfo *),
338 PruneToCubeDepth(CubeInfo *,const NodeInfo *),
339 ReduceImageColors(const Image *,CubeInfo *);
340
341 /*
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
343 % %
344 % %
345 % %
346 % A c q u i r e Q u a n t i z e I n f o %
347 % %
348 % %
349 % %
350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
351 %
352 % AcquireQuantizeInfo() allocates the QuantizeInfo structure.
353 %
354 % The format of the AcquireQuantizeInfo method is:
355 %
356 % QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info)
357 %
358 % A description of each parameter follows:
359 %
360 % o image_info: the image info.
361 %
362 */
AcquireQuantizeInfo(const ImageInfo * image_info)363 MagickExport QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info)
364 {
365 QuantizeInfo
366 *quantize_info;
367
368 quantize_info=(QuantizeInfo *) AcquireMagickMemory(sizeof(*quantize_info));
369 if (quantize_info == (QuantizeInfo *) NULL)
370 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
371 GetQuantizeInfo(quantize_info);
372 if (image_info != (ImageInfo *) NULL)
373 {
374 const char
375 *option;
376
377 quantize_info->dither=image_info->dither;
378 option=GetImageOption(image_info,"dither");
379 if (option != (const char *) NULL)
380 quantize_info->dither_method=(DitherMethod) ParseCommandOption(
381 MagickDitherOptions,MagickFalse,option);
382 quantize_info->measure_error=image_info->verbose;
383 }
384 return(quantize_info);
385 }
386
387 /*
388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
389 % %
390 % %
391 % %
392 + A s s i g n I m a g e C o l o r s %
393 % %
394 % %
395 % %
396 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
397 %
398 % AssignImageColors() generates the output image from the pruned tree. The
399 % output image consists of two parts: (1) A color map, which is an array
400 % of color descriptions (RGB triples) for each color present in the
401 % output image; (2) A pixel array, which represents each pixel as an
402 % index into the color map array.
403 %
404 % First, the assignment phase makes one pass over the pruned color
405 % description tree to establish the image's color map. For each node
406 % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean
407 % color of all pixels that classify no lower than this node. Each of
408 % these colors becomes an entry in the color map.
409 %
410 % Finally, the assignment phase reclassifies each pixel in the pruned
411 % tree to identify the deepest node containing the pixel's color. The
412 % pixel's value in the pixel array becomes the index of this node's mean
413 % color in the color map.
414 %
415 % The format of the AssignImageColors() method is:
416 %
417 % MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info)
418 %
419 % A description of each parameter follows.
420 %
421 % o image: the image.
422 %
423 % o cube_info: A pointer to the Cube structure.
424 %
425 */
426
AssociateAlphaPixel(const CubeInfo * cube_info,const PixelPacket * pixel,DoublePixelPacket * alpha_pixel)427 static inline void AssociateAlphaPixel(const CubeInfo *cube_info,
428 const PixelPacket *pixel,DoublePixelPacket *alpha_pixel)
429 {
430 MagickRealType
431 alpha;
432
433 alpha_pixel->index=0;
434 if ((cube_info->associate_alpha == MagickFalse) ||
435 (pixel->opacity == OpaqueOpacity))
436 {
437 alpha_pixel->red=(MagickRealType) GetPixelRed(pixel);
438 alpha_pixel->green=(MagickRealType) GetPixelGreen(pixel);
439 alpha_pixel->blue=(MagickRealType) GetPixelBlue(pixel);
440 alpha_pixel->opacity=(MagickRealType) GetPixelOpacity(pixel);
441 return;
442 }
443 alpha=(MagickRealType) (QuantumScale*(QuantumRange-GetPixelOpacity(pixel)));
444 alpha_pixel->red=alpha*GetPixelRed(pixel);
445 alpha_pixel->green=alpha*GetPixelGreen(pixel);
446 alpha_pixel->blue=alpha*GetPixelBlue(pixel);
447 alpha_pixel->opacity=(MagickRealType) GetPixelOpacity(pixel);
448 }
449
ColorToNodeId(const CubeInfo * cube_info,const DoublePixelPacket * pixel,size_t index)450 static inline size_t ColorToNodeId(const CubeInfo *cube_info,
451 const DoublePixelPacket *pixel,size_t index)
452 {
453 size_t
454 id;
455
456 id=(size_t) (((ScaleQuantumToChar(ClampPixel(GetPixelRed(pixel))) >> index) &
457 0x01) | ((ScaleQuantumToChar(ClampPixel(GetPixelGreen(pixel))) >> index) &
458 0x01) << 1 | ((ScaleQuantumToChar(ClampPixel(GetPixelBlue(pixel))) >>
459 index) & 0x01) << 2);
460 if (cube_info->associate_alpha != MagickFalse)
461 id|=((ScaleQuantumToChar(ClampPixel(GetPixelOpacity(pixel))) >> index) &
462 0x1) << 3;
463 return(id);
464 }
465
IsSameColor(const Image * image,const PixelPacket * p,const PixelPacket * q)466 static inline MagickBooleanType IsSameColor(const Image *image,
467 const PixelPacket *p,const PixelPacket *q)
468 {
469 if ((GetPixelRed(p) != GetPixelRed(q)) ||
470 (GetPixelGreen(p) != GetPixelGreen(q)) ||
471 (GetPixelBlue(p) != GetPixelBlue(q)))
472 return(MagickFalse);
473 if ((image->matte != MagickFalse) &&
474 (GetPixelOpacity(p) != GetPixelOpacity(q)))
475 return(MagickFalse);
476 return(MagickTrue);
477 }
478
AssignImageColors(Image * image,CubeInfo * cube_info)479 static MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info)
480 {
481 #define AssignImageTag "Assign/Image"
482
483 ColorspaceType
484 colorspace;
485
486 ssize_t
487 y;
488
489 size_t
490 number_colors;
491
492 /*
493 Allocate image colormap.
494 */
495 colorspace=image->colorspace;
496 if (cube_info->quantize_info->colorspace != UndefinedColorspace)
497 (void) TransformImageColorspace(image,cube_info->quantize_info->colorspace);
498 number_colors=MagickMax(cube_info->colors,cube_info->maximum_colors);
499 if (AcquireImageColormap(image,number_colors) == MagickFalse)
500 ThrowBinaryImageException(ResourceLimitError,"MemoryAllocationFailed",
501 image->filename);
502 image->colors=0;
503 cube_info->transparent_pixels=0;
504 cube_info->transparent_index=(-1);
505 DefineImageColormap(image,cube_info,cube_info->root);
506 /*
507 Create a reduced color image.
508 */
509 if ((cube_info->quantize_info->dither != MagickFalse) &&
510 (cube_info->quantize_info->dither_method != NoDitherMethod))
511 (void) DitherImage(image,cube_info);
512 else
513 {
514 CacheView
515 *image_view;
516
517 ExceptionInfo
518 *exception;
519
520 MagickBooleanType
521 status;
522
523 status=MagickTrue;
524 exception=(&image->exception);
525 image_view=AcquireAuthenticCacheView(image,exception);
526 #if defined(MAGICKCORE_OPENMP_SUPPORT)
527 #pragma omp parallel for schedule(static) shared(status) \
528 magick_number_threads(image,image,image->rows,1)
529 #endif
530 for (y=0; y < (ssize_t) image->rows; y++)
531 {
532 CubeInfo
533 cube;
534
535 IndexPacket
536 *magick_restrict indexes;
537
538 PixelPacket
539 *magick_restrict q;
540
541 ssize_t
542 x;
543
544 ssize_t
545 count;
546
547 if (status == MagickFalse)
548 continue;
549 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
550 exception);
551 if (q == (PixelPacket *) NULL)
552 {
553 status=MagickFalse;
554 continue;
555 }
556 indexes=GetCacheViewAuthenticIndexQueue(image_view);
557 cube=(*cube_info);
558 for (x=0; x < (ssize_t) image->columns; x+=count)
559 {
560 DoublePixelPacket
561 pixel;
562
563 const NodeInfo
564 *node_info;
565
566 ssize_t
567 i;
568
569 size_t
570 id,
571 index;
572
573 /*
574 Identify the deepest node containing the pixel's color.
575 */
576 for (count=1; (x+count) < (ssize_t) image->columns; count++)
577 if (IsSameColor(image,q,q+count) == MagickFalse)
578 break;
579 AssociateAlphaPixel(&cube,q,&pixel);
580 node_info=cube.root;
581 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
582 {
583 id=ColorToNodeId(&cube,&pixel,index);
584 if (node_info->child[id] == (NodeInfo *) NULL)
585 break;
586 node_info=node_info->child[id];
587 }
588 /*
589 Find closest color among siblings and their children.
590 */
591 cube.target=pixel;
592 cube.distance=(MagickRealType) (4.0*(QuantumRange+1.0)*
593 (QuantumRange+1.0)+1.0);
594 ClosestColor(image,&cube,node_info->parent);
595 index=cube.color_number;
596 for (i=0; i < (ssize_t) count; i++)
597 {
598 if (image->storage_class == PseudoClass)
599 SetPixelIndex(indexes+x+i,index);
600 if (cube.quantize_info->measure_error == MagickFalse)
601 {
602 SetPixelRgb(q,image->colormap+index);
603 if (cube.associate_alpha != MagickFalse)
604 SetPixelOpacity(q,image->colormap[index].opacity);
605 }
606 q++;
607 }
608 }
609 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
610 status=MagickFalse;
611 if (image->progress_monitor != (MagickProgressMonitor) NULL)
612 {
613 MagickBooleanType
614 proceed;
615
616 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y,
617 image->rows);
618 if (proceed == MagickFalse)
619 status=MagickFalse;
620 }
621 }
622 image_view=DestroyCacheView(image_view);
623 }
624 if (cube_info->quantize_info->measure_error != MagickFalse)
625 (void) GetImageQuantizeError(image);
626 if ((cube_info->quantize_info->number_colors == 2) &&
627 (IsGrayColorspace(cube_info->quantize_info->colorspace)))
628 {
629 double
630 intensity;
631
632 /*
633 Monochrome image.
634 */
635 intensity=GetPixelLuma(image,image->colormap+0) < QuantumRange/2.0 ? 0.0 :
636 QuantumRange;
637 if ((image->colors > 1) &&
638 (GetPixelLuma(image,image->colormap+0) >
639 GetPixelLuma(image,image->colormap+1)))
640 intensity=(double) QuantumRange;
641 image->colormap[0].red=intensity;
642 image->colormap[0].green=intensity;
643 image->colormap[0].blue=intensity;
644 if (image->colors > 1)
645 {
646 image->colormap[1].red=(double) QuantumRange-intensity;
647 image->colormap[1].green=(double) QuantumRange-intensity;
648 image->colormap[1].blue=(double) QuantumRange-intensity;
649 }
650 }
651 (void) SyncImage(image);
652 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
653 (IssRGBCompatibleColorspace(colorspace) == MagickFalse))
654 (void) TransformImageColorspace(image,colorspace);
655 return(MagickTrue);
656 }
657
658 /*
659 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
660 % %
661 % %
662 % %
663 + C l a s s i f y I m a g e C o l o r s %
664 % %
665 % %
666 % %
667 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
668 %
669 % ClassifyImageColors() begins by initializing a color description tree
670 % of sufficient depth to represent each possible input color in a leaf.
671 % However, it is impractical to generate a fully-formed color
672 % description tree in the storage_class phase for realistic values of
673 % Cmax. If colors components in the input image are quantized to k-bit
674 % precision, so that Cmax= 2k-1, the tree would need k levels below the
675 % root node to allow representing each possible input color in a leaf.
676 % This becomes prohibitive because the tree's total number of nodes is
677 % 1 + sum(i=1,k,8k).
678 %
679 % A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
680 % Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
681 % Initializes data structures for nodes only as they are needed; (2)
682 % Chooses a maximum depth for the tree as a function of the desired
683 % number of colors in the output image (currently log2(colormap size)).
684 %
685 % For each pixel in the input image, storage_class scans downward from
686 % the root of the color description tree. At each level of the tree it
687 % identifies the single node which represents a cube in RGB space
688 % containing It updates the following data for each such node:
689 %
690 % n1 : Number of pixels whose color is contained in the RGB cube
691 % which this node represents;
692 %
693 % n2 : Number of pixels whose color is not represented in a node at
694 % lower depth in the tree; initially, n2 = 0 for all nodes except
695 % leaves of the tree.
696 %
697 % Sr, Sg, Sb : Sums of the red, green, and blue component values for
698 % all pixels not classified at a lower depth. The combination of
699 % these sums and n2 will ultimately characterize the mean color of a
700 % set of pixels represented by this node.
701 %
702 % E: the distance squared in RGB space between each pixel contained
703 % within a node and the nodes' center. This represents the quantization
704 % error for a node.
705 %
706 % The format of the ClassifyImageColors() method is:
707 %
708 % MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
709 % const Image *image,ExceptionInfo *exception)
710 %
711 % A description of each parameter follows.
712 %
713 % o cube_info: A pointer to the Cube structure.
714 %
715 % o image: the image.
716 %
717 */
718
SetAssociatedAlpha(const Image * image,CubeInfo * cube_info)719 static inline void SetAssociatedAlpha(const Image *image,CubeInfo *cube_info)
720 {
721 MagickBooleanType
722 associate_alpha;
723
724 associate_alpha=image->matte;
725 if ((cube_info->quantize_info->number_colors == 2) &&
726 ((cube_info->quantize_info->colorspace == LinearGRAYColorspace) ||
727 (cube_info->quantize_info->colorspace == GRAYColorspace)))
728 associate_alpha=MagickFalse;
729 cube_info->associate_alpha=associate_alpha;
730 }
731
ClassifyImageColors(CubeInfo * cube_info,const Image * image,ExceptionInfo * exception)732 static MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
733 const Image *image,ExceptionInfo *exception)
734 {
735 #define ClassifyImageTag "Classify/Image"
736
737 CacheView
738 *image_view;
739
740 DoublePixelPacket
741 error,
742 mid,
743 midpoint,
744 pixel;
745
746 MagickBooleanType
747 proceed;
748
749 MagickRealType
750 bisect;
751
752 NodeInfo
753 *node_info;
754
755 size_t
756 count,
757 id,
758 index,
759 level;
760
761 ssize_t
762 y;
763
764 /*
765 Classify the first cube_info->maximum_colors colors to a tree depth of 8.
766 */
767 SetAssociatedAlpha(image,cube_info);
768 if (cube_info->quantize_info->colorspace != image->colorspace)
769 {
770 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
771 (cube_info->quantize_info->colorspace != CMYKColorspace))
772 (void) TransformImageColorspace((Image *) image,
773 cube_info->quantize_info->colorspace);
774 else
775 if (IssRGBCompatibleColorspace(image->colorspace) == MagickFalse)
776 (void) TransformImageColorspace((Image *) image,sRGBColorspace);
777 }
778 midpoint.red=(MagickRealType) QuantumRange/2.0;
779 midpoint.green=(MagickRealType) QuantumRange/2.0;
780 midpoint.blue=(MagickRealType) QuantumRange/2.0;
781 midpoint.opacity=(MagickRealType) QuantumRange/2.0;
782 midpoint.index=(MagickRealType) QuantumRange/2.0;
783 error.opacity=0.0;
784 image_view=AcquireVirtualCacheView(image,exception);
785 for (y=0; y < (ssize_t) image->rows; y++)
786 {
787 const PixelPacket
788 *magick_restrict p;
789
790 ssize_t
791 x;
792
793 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
794 if (p == (const PixelPacket *) NULL)
795 break;
796 if (cube_info->nodes > MaxNodes)
797 {
798 /*
799 Prune one level if the color tree is too large.
800 */
801 PruneLevel(cube_info,cube_info->root);
802 cube_info->depth--;
803 }
804 for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
805 {
806 /*
807 Start at the root and descend the color cube tree.
808 */
809 for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
810 if (IsSameColor(image,p,p+count) == MagickFalse)
811 break;
812 AssociateAlphaPixel(cube_info,p,&pixel);
813 index=MaxTreeDepth-1;
814 bisect=((MagickRealType) QuantumRange+1.0)/2.0;
815 mid=midpoint;
816 node_info=cube_info->root;
817 for (level=1; level <= MaxTreeDepth; level++)
818 {
819 double
820 distance;
821
822 bisect*=0.5;
823 id=ColorToNodeId(cube_info,&pixel,index);
824 mid.red+=(id & 1) != 0 ? bisect : -bisect;
825 mid.green+=(id & 2) != 0 ? bisect : -bisect;
826 mid.blue+=(id & 4) != 0 ? bisect : -bisect;
827 mid.opacity+=(id & 8) != 0 ? bisect : -bisect;
828 if (node_info->child[id] == (NodeInfo *) NULL)
829 {
830 /*
831 Set colors of new node to contain pixel.
832 */
833 node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
834 if (node_info->child[id] == (NodeInfo *) NULL)
835 {
836 (void) ThrowMagickException(exception,GetMagickModule(),
837 ResourceLimitError,"MemoryAllocationFailed","`%s'",
838 image->filename);
839 continue;
840 }
841 if (level == MaxTreeDepth)
842 cube_info->colors++;
843 }
844 /*
845 Approximate the quantization error represented by this node.
846 */
847 node_info=node_info->child[id];
848 error.red=QuantumScale*(pixel.red-mid.red);
849 error.green=QuantumScale*(pixel.green-mid.green);
850 error.blue=QuantumScale*(pixel.blue-mid.blue);
851 if (cube_info->associate_alpha != MagickFalse)
852 error.opacity=QuantumScale*(pixel.opacity-mid.opacity);
853 distance=(double) (error.red*error.red+error.green*error.green+
854 error.blue*error.blue+error.opacity*error.opacity);
855 if (IsNaN(distance) != 0)
856 distance=0.0;
857 node_info->quantize_error+=count*sqrt(distance);
858 cube_info->root->quantize_error+=node_info->quantize_error;
859 index--;
860 }
861 /*
862 Sum RGB for this leaf for later derivation of the mean cube color.
863 */
864 node_info->number_unique+=count;
865 node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red);
866 node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green);
867 node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue);
868 if (cube_info->associate_alpha != MagickFalse)
869 node_info->total_color.opacity+=count*QuantumScale*
870 ClampPixel(pixel.opacity);
871 else
872 node_info->total_color.opacity+=count*QuantumScale*
873 ClampPixel(OpaqueOpacity);
874 p+=count;
875 }
876 if (cube_info->colors > cube_info->maximum_colors)
877 {
878 PruneToCubeDepth(cube_info,cube_info->root);
879 break;
880 }
881 proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
882 image->rows);
883 if (proceed == MagickFalse)
884 break;
885 }
886 for (y++; y < (ssize_t) image->rows; y++)
887 {
888 const PixelPacket
889 *magick_restrict p;
890
891 ssize_t
892 x;
893
894 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
895 if (p == (const PixelPacket *) NULL)
896 break;
897 if (cube_info->nodes > MaxNodes)
898 {
899 /*
900 Prune one level if the color tree is too large.
901 */
902 PruneLevel(cube_info,cube_info->root);
903 cube_info->depth--;
904 }
905 for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
906 {
907 /*
908 Start at the root and descend the color cube tree.
909 */
910 for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
911 if (IsSameColor(image,p,p+count) == MagickFalse)
912 break;
913 AssociateAlphaPixel(cube_info,p,&pixel);
914 index=MaxTreeDepth-1;
915 bisect=((MagickRealType) QuantumRange+1.0)/2.0;
916 mid=midpoint;
917 node_info=cube_info->root;
918 for (level=1; level <= cube_info->depth; level++)
919 {
920 double
921 distance;
922
923 bisect*=0.5;
924 id=ColorToNodeId(cube_info,&pixel,index);
925 mid.red+=(id & 1) != 0 ? bisect : -bisect;
926 mid.green+=(id & 2) != 0 ? bisect : -bisect;
927 mid.blue+=(id & 4) != 0 ? bisect : -bisect;
928 mid.opacity+=(id & 8) != 0 ? bisect : -bisect;
929 if (node_info->child[id] == (NodeInfo *) NULL)
930 {
931 /*
932 Set colors of new node to contain pixel.
933 */
934 node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
935 if (node_info->child[id] == (NodeInfo *) NULL)
936 {
937 (void) ThrowMagickException(exception,GetMagickModule(),
938 ResourceLimitError,"MemoryAllocationFailed","%s",
939 image->filename);
940 continue;
941 }
942 if (level == cube_info->depth)
943 cube_info->colors++;
944 }
945 /*
946 Approximate the quantization error represented by this node.
947 */
948 node_info=node_info->child[id];
949 error.red=QuantumScale*(pixel.red-mid.red);
950 error.green=QuantumScale*(pixel.green-mid.green);
951 error.blue=QuantumScale*(pixel.blue-mid.blue);
952 if (cube_info->associate_alpha != MagickFalse)
953 error.opacity=QuantumScale*(pixel.opacity-mid.opacity);
954 distance=(double) (error.red*error.red+error.green*error.green+
955 error.blue*error.blue+error.opacity*error.opacity);
956 if (IsNaN(distance) != 0)
957 distance=0.0;
958 node_info->quantize_error+=count*sqrt(distance);
959 cube_info->root->quantize_error+=node_info->quantize_error;
960 index--;
961 }
962 /*
963 Sum RGB for this leaf for later derivation of the mean cube color.
964 */
965 node_info->number_unique+=count;
966 node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red);
967 node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green);
968 node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue);
969 if (cube_info->associate_alpha != MagickFalse)
970 node_info->total_color.opacity+=count*QuantumScale*ClampPixel(
971 pixel.opacity);
972 else
973 node_info->total_color.opacity+=count*QuantumScale*
974 ClampPixel(OpaqueOpacity);
975 p+=count;
976 }
977 proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
978 image->rows);
979 if (proceed == MagickFalse)
980 break;
981 }
982 image_view=DestroyCacheView(image_view);
983 if (cube_info->quantize_info->colorspace != image->colorspace)
984 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
985 (cube_info->quantize_info->colorspace != CMYKColorspace))
986 (void) TransformImageColorspace((Image *) image,sRGBColorspace);
987 return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue);
988 }
989
990 /*
991 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
992 % %
993 % %
994 % %
995 % C l o n e Q u a n t i z e I n f o %
996 % %
997 % %
998 % %
999 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1000 %
1001 % CloneQuantizeInfo() makes a duplicate of the given quantize info structure,
1002 % or if quantize info is NULL, a new one.
1003 %
1004 % The format of the CloneQuantizeInfo method is:
1005 %
1006 % QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
1007 %
1008 % A description of each parameter follows:
1009 %
1010 % o clone_info: Method CloneQuantizeInfo returns a duplicate of the given
1011 % quantize info, or if image info is NULL a new one.
1012 %
1013 % o quantize_info: a structure of type info.
1014 %
1015 */
CloneQuantizeInfo(const QuantizeInfo * quantize_info)1016 MagickExport QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
1017 {
1018 QuantizeInfo
1019 *clone_info;
1020
1021 clone_info=(QuantizeInfo *) AcquireMagickMemory(sizeof(*clone_info));
1022 if (clone_info == (QuantizeInfo *) NULL)
1023 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1024 GetQuantizeInfo(clone_info);
1025 if (quantize_info == (QuantizeInfo *) NULL)
1026 return(clone_info);
1027 clone_info->number_colors=quantize_info->number_colors;
1028 clone_info->tree_depth=quantize_info->tree_depth;
1029 clone_info->dither=quantize_info->dither;
1030 clone_info->dither_method=quantize_info->dither_method;
1031 clone_info->colorspace=quantize_info->colorspace;
1032 clone_info->measure_error=quantize_info->measure_error;
1033 return(clone_info);
1034 }
1035
1036 /*
1037 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1038 % %
1039 % %
1040 % %
1041 + C l o s e s t C o l o r %
1042 % %
1043 % %
1044 % %
1045 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1046 %
1047 % ClosestColor() traverses the color cube tree at a particular node and
1048 % determines which colormap entry best represents the input color.
1049 %
1050 % The format of the ClosestColor method is:
1051 %
1052 % void ClosestColor(const Image *image,CubeInfo *cube_info,
1053 % const NodeInfo *node_info)
1054 %
1055 % A description of each parameter follows.
1056 %
1057 % o image: the image.
1058 %
1059 % o cube_info: A pointer to the Cube structure.
1060 %
1061 % o node_info: the address of a structure of type NodeInfo which points to a
1062 % node in the color cube tree that is to be pruned.
1063 %
1064 */
ClosestColor(const Image * image,CubeInfo * cube_info,const NodeInfo * node_info)1065 static void ClosestColor(const Image *image,CubeInfo *cube_info,
1066 const NodeInfo *node_info)
1067 {
1068 ssize_t
1069 i;
1070
1071 size_t
1072 number_children;
1073
1074 /*
1075 Traverse any children.
1076 */
1077 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1078 for (i=0; i < (ssize_t) number_children; i++)
1079 if (node_info->child[i] != (NodeInfo *) NULL)
1080 ClosestColor(image,cube_info,node_info->child[i]);
1081 if (node_info->number_unique != 0)
1082 {
1083 MagickRealType
1084 pixel;
1085
1086 DoublePixelPacket
1087 *magick_restrict q;
1088
1089 MagickRealType
1090 alpha,
1091 beta,
1092 distance;
1093
1094 PixelPacket
1095 *magick_restrict p;
1096
1097 /*
1098 Determine if this color is "closest".
1099 */
1100 p=image->colormap+node_info->color_number;
1101 q=(&cube_info->target);
1102 alpha=1.0;
1103 beta=1.0;
1104 if (cube_info->associate_alpha != MagickFalse)
1105 {
1106 alpha=(MagickRealType) (QuantumScale*GetPixelAlpha(p));
1107 beta=(MagickRealType) (QuantumScale*GetPixelAlpha(q));
1108 }
1109 pixel=alpha*GetPixelRed(p)-beta*GetPixelRed(q);
1110 distance=pixel*pixel;
1111 if (distance <= cube_info->distance)
1112 {
1113 pixel=alpha*GetPixelGreen(p)-beta*GetPixelGreen(q);
1114 distance+=pixel*pixel;
1115 if (distance <= cube_info->distance)
1116 {
1117 pixel=alpha*GetPixelBlue(p)-beta*GetPixelBlue(q);
1118 distance+=pixel*pixel;
1119 if (distance <= cube_info->distance)
1120 {
1121 if (cube_info->associate_alpha != MagickFalse)
1122 {
1123 pixel=GetPixelAlpha(p)-GetPixelAlpha(q);
1124 distance+=pixel*pixel;
1125 }
1126 if (distance <= cube_info->distance)
1127 {
1128 cube_info->distance=distance;
1129 cube_info->color_number=node_info->color_number;
1130 }
1131 }
1132 }
1133 }
1134 }
1135 }
1136
1137 /*
1138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1139 % %
1140 % %
1141 % %
1142 % C o m p r e s s I m a g e C o l o r m a p %
1143 % %
1144 % %
1145 % %
1146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1147 %
1148 % CompressImageColormap() compresses an image colormap by removing any
1149 % duplicate or unused color entries.
1150 %
1151 % The format of the CompressImageColormap method is:
1152 %
1153 % MagickBooleanType CompressImageColormap(Image *image)
1154 %
1155 % A description of each parameter follows:
1156 %
1157 % o image: the image.
1158 %
1159 */
CompressImageColormap(Image * image)1160 MagickExport MagickBooleanType CompressImageColormap(Image *image)
1161 {
1162 QuantizeInfo
1163 quantize_info;
1164
1165 assert(image != (Image *) NULL);
1166 assert(image->signature == MagickCoreSignature);
1167 if (image->debug != MagickFalse)
1168 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1169 if (IsPaletteImage(image,&image->exception) == MagickFalse)
1170 return(MagickFalse);
1171 GetQuantizeInfo(&quantize_info);
1172 quantize_info.number_colors=image->colors;
1173 quantize_info.tree_depth=MaxTreeDepth;
1174 return(QuantizeImage(&quantize_info,image));
1175 }
1176
1177 /*
1178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1179 % %
1180 % %
1181 % %
1182 + D e f i n e I m a g e C o l o r m a p %
1183 % %
1184 % %
1185 % %
1186 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1187 %
1188 % DefineImageColormap() traverses the color cube tree and notes each colormap
1189 % entry. A colormap entry is any node in the color cube tree where the
1190 % of unique colors is not zero.
1191 %
1192 % The format of the DefineImageColormap method is:
1193 %
1194 % void DefineImageColormap(Image *image,CubeInfo *cube_info,
1195 % NodeInfo *node_info)
1196 %
1197 % A description of each parameter follows.
1198 %
1199 % o image: the image.
1200 %
1201 % o cube_info: A pointer to the Cube structure.
1202 %
1203 % o node_info: the address of a structure of type NodeInfo which points to a
1204 % node in the color cube tree that is to be pruned.
1205 %
1206 */
DefineImageColormap(Image * image,CubeInfo * cube_info,NodeInfo * node_info)1207 static void DefineImageColormap(Image *image,CubeInfo *cube_info,
1208 NodeInfo *node_info)
1209 {
1210 size_t
1211 number_children;
1212
1213 ssize_t
1214 i;
1215
1216 /*
1217 Traverse any children.
1218 */
1219 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1220 for (i=0; i < (ssize_t) number_children; i++)
1221 if (node_info->child[i] != (NodeInfo *) NULL)
1222 DefineImageColormap(image,cube_info,node_info->child[i]);
1223 if (node_info->number_unique != 0)
1224 {
1225 MagickRealType
1226 alpha;
1227
1228 PixelPacket
1229 *magick_restrict q;
1230
1231 /*
1232 Colormap entry is defined by the mean color in this cube.
1233 */
1234 q=image->colormap+image->colors;
1235 alpha=(MagickRealType) ((MagickOffsetType) node_info->number_unique);
1236 alpha=PerceptibleReciprocal(alpha);
1237 if (cube_info->associate_alpha == MagickFalse)
1238 {
1239 SetPixelRed(q,ClampToQuantum((MagickRealType) (alpha*
1240 QuantumRange*node_info->total_color.red)));
1241 SetPixelGreen(q,ClampToQuantum((MagickRealType) (alpha*
1242 QuantumRange*node_info->total_color.green)));
1243 SetPixelBlue(q,ClampToQuantum((MagickRealType) (alpha*
1244 QuantumRange*node_info->total_color.blue)));
1245 SetPixelOpacity(q,OpaqueOpacity);
1246 }
1247 else
1248 {
1249 MagickRealType
1250 opacity;
1251
1252 opacity=(MagickRealType) (alpha*QuantumRange*
1253 node_info->total_color.opacity);
1254 SetPixelOpacity(q,ClampToQuantum(opacity));
1255 if (q->opacity == OpaqueOpacity)
1256 {
1257 SetPixelRed(q,ClampToQuantum((MagickRealType) (alpha*
1258 QuantumRange*node_info->total_color.red)));
1259 SetPixelGreen(q,ClampToQuantum((MagickRealType) (alpha*
1260 QuantumRange*node_info->total_color.green)));
1261 SetPixelBlue(q,ClampToQuantum((MagickRealType) (alpha*
1262 QuantumRange*node_info->total_color.blue)));
1263 }
1264 else
1265 {
1266 double
1267 gamma;
1268
1269 gamma=(double) (QuantumScale*(QuantumRange-(double) q->opacity));
1270 gamma=PerceptibleReciprocal(gamma);
1271 SetPixelRed(q,ClampToQuantum((MagickRealType) (alpha*
1272 gamma*QuantumRange*node_info->total_color.red)));
1273 SetPixelGreen(q,ClampToQuantum((MagickRealType) (alpha*
1274 gamma*QuantumRange*node_info->total_color.green)));
1275 SetPixelBlue(q,ClampToQuantum((MagickRealType) (alpha*
1276 gamma*QuantumRange*node_info->total_color.blue)));
1277 if (node_info->number_unique > cube_info->transparent_pixels)
1278 {
1279 cube_info->transparent_pixels=node_info->number_unique;
1280 cube_info->transparent_index=(ssize_t) image->colors;
1281 }
1282 }
1283 }
1284 node_info->color_number=image->colors++;
1285 }
1286 }
1287
1288 /*
1289 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1290 % %
1291 % %
1292 % %
1293 + D e s t r o y C u b e I n f o %
1294 % %
1295 % %
1296 % %
1297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1298 %
1299 % DestroyCubeInfo() deallocates memory associated with an image.
1300 %
1301 % The format of the DestroyCubeInfo method is:
1302 %
1303 % DestroyCubeInfo(CubeInfo *cube_info)
1304 %
1305 % A description of each parameter follows:
1306 %
1307 % o cube_info: the address of a structure of type CubeInfo.
1308 %
1309 */
DestroyCubeInfo(CubeInfo * cube_info)1310 static void DestroyCubeInfo(CubeInfo *cube_info)
1311 {
1312 Nodes
1313 *nodes;
1314
1315 /*
1316 Release color cube tree storage.
1317 */
1318 do
1319 {
1320 nodes=cube_info->node_queue->next;
1321 cube_info->node_queue->nodes=(NodeInfo *) RelinquishMagickMemory(
1322 cube_info->node_queue->nodes);
1323 cube_info->node_queue=(Nodes *) RelinquishMagickMemory(
1324 cube_info->node_queue);
1325 cube_info->node_queue=nodes;
1326 } while (cube_info->node_queue != (Nodes *) NULL);
1327 if (cube_info->memory_info != (MemoryInfo *) NULL)
1328 cube_info->memory_info=RelinquishVirtualMemory(cube_info->memory_info);
1329 cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info);
1330 cube_info=(CubeInfo *) RelinquishMagickMemory(cube_info);
1331 }
1332
1333 /*
1334 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1335 % %
1336 % %
1337 % %
1338 % D e s t r o y Q u a n t i z e I n f o %
1339 % %
1340 % %
1341 % %
1342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1343 %
1344 % DestroyQuantizeInfo() deallocates memory associated with an QuantizeInfo
1345 % structure.
1346 %
1347 % The format of the DestroyQuantizeInfo method is:
1348 %
1349 % QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1350 %
1351 % A description of each parameter follows:
1352 %
1353 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1354 %
1355 */
DestroyQuantizeInfo(QuantizeInfo * quantize_info)1356 MagickExport QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1357 {
1358 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1359 assert(quantize_info != (QuantizeInfo *) NULL);
1360 assert(quantize_info->signature == MagickCoreSignature);
1361 quantize_info->signature=(~MagickCoreSignature);
1362 quantize_info=(QuantizeInfo *) RelinquishMagickMemory(quantize_info);
1363 return(quantize_info);
1364 }
1365
1366 /*
1367 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1368 % %
1369 % %
1370 % %
1371 + D i t h e r I m a g e %
1372 % %
1373 % %
1374 % %
1375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1376 %
1377 % DitherImage() distributes the difference between an original image and
1378 % the corresponding color reduced algorithm to neighboring pixels using
1379 % serpentine-scan Floyd-Steinberg error diffusion. DitherImage returns
1380 % MagickTrue if the image is dithered otherwise MagickFalse.
1381 %
1382 % The format of the DitherImage method is:
1383 %
1384 % MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info)
1385 %
1386 % A description of each parameter follows.
1387 %
1388 % o image: the image.
1389 %
1390 % o cube_info: A pointer to the Cube structure.
1391 %
1392 */
1393
DestroyPixelThreadSet(DoublePixelPacket ** pixels)1394 static DoublePixelPacket **DestroyPixelThreadSet(DoublePixelPacket **pixels)
1395 {
1396 ssize_t
1397 i;
1398
1399 assert(pixels != (DoublePixelPacket **) NULL);
1400 for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++)
1401 if (pixels[i] != (DoublePixelPacket *) NULL)
1402 pixels[i]=(DoublePixelPacket *) RelinquishMagickMemory(pixels[i]);
1403 pixels=(DoublePixelPacket **) RelinquishMagickMemory(pixels);
1404 return(pixels);
1405 }
1406
AcquirePixelThreadSet(const size_t count)1407 static DoublePixelPacket **AcquirePixelThreadSet(const size_t count)
1408 {
1409 DoublePixelPacket
1410 **pixels;
1411
1412 size_t
1413 number_threads;
1414
1415 ssize_t
1416 i;
1417
1418 number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
1419 pixels=(DoublePixelPacket **) AcquireQuantumMemory(number_threads,
1420 sizeof(*pixels));
1421 if (pixels == (DoublePixelPacket **) NULL)
1422 return((DoublePixelPacket **) NULL);
1423 (void) memset(pixels,0,number_threads*sizeof(*pixels));
1424 for (i=0; i < (ssize_t) number_threads; i++)
1425 {
1426 pixels[i]=(DoublePixelPacket *) AcquireQuantumMemory(count,
1427 2*sizeof(**pixels));
1428 if (pixels[i] == (DoublePixelPacket *) NULL)
1429 return(DestroyPixelThreadSet(pixels));
1430 }
1431 return(pixels);
1432 }
1433
CacheOffset(CubeInfo * cube_info,const DoublePixelPacket * pixel)1434 static inline ssize_t CacheOffset(CubeInfo *cube_info,
1435 const DoublePixelPacket *pixel)
1436 {
1437 #define RedShift(pixel) (((pixel) >> CacheShift) << (0*(8-CacheShift)))
1438 #define GreenShift(pixel) (((pixel) >> CacheShift) << (1*(8-CacheShift)))
1439 #define BlueShift(pixel) (((pixel) >> CacheShift) << (2*(8-CacheShift)))
1440 #define AlphaShift(pixel) (((pixel) >> CacheShift) << (3*(8-CacheShift)))
1441
1442 ssize_t
1443 offset;
1444
1445 offset=(ssize_t) (RedShift(ScaleQuantumToChar(ClampPixel(pixel->red))) |
1446 GreenShift(ScaleQuantumToChar(ClampPixel(pixel->green))) |
1447 BlueShift(ScaleQuantumToChar(ClampPixel(pixel->blue))));
1448 if (cube_info->associate_alpha != MagickFalse)
1449 offset|=AlphaShift(ScaleQuantumToChar(ClampPixel(pixel->opacity)));
1450 return(offset);
1451 }
1452
FloydSteinbergDither(Image * image,CubeInfo * cube_info)1453 static MagickBooleanType FloydSteinbergDither(Image *image,CubeInfo *cube_info)
1454 {
1455 #define DitherImageTag "Dither/Image"
1456
1457 CacheView
1458 *image_view;
1459
1460 DoublePixelPacket
1461 **pixels;
1462
1463 ExceptionInfo
1464 *exception;
1465
1466 MagickBooleanType
1467 status;
1468
1469 ssize_t
1470 y;
1471
1472 /*
1473 Distribute quantization error using Floyd-Steinberg.
1474 */
1475 pixels=AcquirePixelThreadSet(image->columns);
1476 if (pixels == (DoublePixelPacket **) NULL)
1477 return(MagickFalse);
1478 exception=(&image->exception);
1479 status=MagickTrue;
1480 image_view=AcquireAuthenticCacheView(image,exception);
1481 for (y=0; y < (ssize_t) image->rows; y++)
1482 {
1483 const int
1484 id = GetOpenMPThreadId();
1485
1486 CubeInfo
1487 cube;
1488
1489 DoublePixelPacket
1490 *current,
1491 *previous;
1492
1493 IndexPacket
1494 *magick_restrict indexes;
1495
1496 PixelPacket
1497 *magick_restrict q;
1498
1499 size_t
1500 index;
1501
1502 ssize_t
1503 x,
1504 v;
1505
1506 if (status == MagickFalse)
1507 continue;
1508 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
1509 if (q == (PixelPacket *) NULL)
1510 {
1511 status=MagickFalse;
1512 continue;
1513 }
1514 indexes=GetCacheViewAuthenticIndexQueue(image_view);
1515 cube=(*cube_info);
1516 current=pixels[id]+(y & 0x01)*image->columns;
1517 previous=pixels[id]+((y+1) & 0x01)*image->columns;
1518 v=(ssize_t) ((y & 0x01) ? -1 : 1);
1519 for (x=0; x < (ssize_t) image->columns; x++)
1520 {
1521 DoublePixelPacket
1522 color,
1523 pixel;
1524
1525 ssize_t
1526 i;
1527
1528 ssize_t
1529 u;
1530
1531 u=(y & 0x01) ? (ssize_t) image->columns-1-x : x;
1532 AssociateAlphaPixel(&cube,q+u,&pixel);
1533 if (x > 0)
1534 {
1535 pixel.red+=7.0*cube_info->diffusion*current[u-v].red/16;
1536 pixel.green+=7.0*cube_info->diffusion*current[u-v].green/16;
1537 pixel.blue+=7.0*cube_info->diffusion*current[u-v].blue/16;
1538 if (cube.associate_alpha != MagickFalse)
1539 pixel.opacity+=7.0*cube_info->diffusion*current[u-v].opacity/16;
1540 }
1541 if (y > 0)
1542 {
1543 if (x < (ssize_t) (image->columns-1))
1544 {
1545 pixel.red+=cube_info->diffusion*previous[u+v].red/16;
1546 pixel.green+=cube_info->diffusion*previous[u+v].green/16;
1547 pixel.blue+=cube_info->diffusion*previous[u+v].blue/16;
1548 if (cube.associate_alpha != MagickFalse)
1549 pixel.opacity+=cube_info->diffusion*previous[u+v].opacity/16;
1550 }
1551 pixel.red+=5.0*cube_info->diffusion*previous[u].red/16;
1552 pixel.green+=5.0*cube_info->diffusion*previous[u].green/16;
1553 pixel.blue+=5.0*cube_info->diffusion*previous[u].blue/16;
1554 if (cube.associate_alpha != MagickFalse)
1555 pixel.opacity+=5.0*cube_info->diffusion*previous[u].opacity/16;
1556 if (x > 0)
1557 {
1558 pixel.red+=3.0*cube_info->diffusion*previous[u-v].red/16;
1559 pixel.green+=3.0*cube_info->diffusion*previous[u-v].green/16;
1560 pixel.blue+=3.0*cube_info->diffusion*previous[u-v].blue/16;
1561 if (cube.associate_alpha != MagickFalse)
1562 pixel.opacity+=3.0*cube_info->diffusion*
1563 previous[u-v].opacity/16;
1564 }
1565 }
1566 pixel.red=(MagickRealType) ClampPixel(pixel.red);
1567 pixel.green=(MagickRealType) ClampPixel(pixel.green);
1568 pixel.blue=(MagickRealType) ClampPixel(pixel.blue);
1569 if (cube.associate_alpha != MagickFalse)
1570 pixel.opacity=(MagickRealType) ClampPixel(pixel.opacity);
1571 i=CacheOffset(&cube,&pixel);
1572 if (cube.cache[i] < 0)
1573 {
1574 NodeInfo
1575 *node_info;
1576
1577 size_t
1578 id;
1579
1580 /*
1581 Identify the deepest node containing the pixel's color.
1582 */
1583 node_info=cube.root;
1584 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1585 {
1586 id=ColorToNodeId(&cube,&pixel,index);
1587 if (node_info->child[id] == (NodeInfo *) NULL)
1588 break;
1589 node_info=node_info->child[id];
1590 }
1591 /*
1592 Find closest color among siblings and their children.
1593 */
1594 cube.target=pixel;
1595 cube.distance=(MagickRealType) (4.0*(QuantumRange+1.0)*(QuantumRange+
1596 1.0)+1.0);
1597 ClosestColor(image,&cube,node_info->parent);
1598 cube.cache[i]=(ssize_t) cube.color_number;
1599 }
1600 /*
1601 Assign pixel to closest colormap entry.
1602 */
1603 index=(size_t) cube.cache[i];
1604 if (image->storage_class == PseudoClass)
1605 SetPixelIndex(indexes+u,index);
1606 if (cube.quantize_info->measure_error == MagickFalse)
1607 {
1608 SetPixelRgb(q+u,image->colormap+index);
1609 if (cube.associate_alpha != MagickFalse)
1610 SetPixelOpacity(q+u,image->colormap[index].opacity);
1611 }
1612 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1613 status=MagickFalse;
1614 /*
1615 Store the error.
1616 */
1617 AssociateAlphaPixel(&cube,image->colormap+index,&color);
1618 current[u].red=pixel.red-color.red;
1619 current[u].green=pixel.green-color.green;
1620 current[u].blue=pixel.blue-color.blue;
1621 if (cube.associate_alpha != MagickFalse)
1622 current[u].opacity=pixel.opacity-color.opacity;
1623 if (image->progress_monitor != (MagickProgressMonitor) NULL)
1624 {
1625 MagickBooleanType
1626 proceed;
1627
1628 proceed=SetImageProgress(image,DitherImageTag,(MagickOffsetType) y,
1629 image->rows);
1630 if (proceed == MagickFalse)
1631 status=MagickFalse;
1632 }
1633 }
1634 }
1635 image_view=DestroyCacheView(image_view);
1636 pixels=DestroyPixelThreadSet(pixels);
1637 return(MagickTrue);
1638 }
1639
1640 static MagickBooleanType
1641 RiemersmaDither(Image *,CacheView *,CubeInfo *,const unsigned int);
1642
Riemersma(Image * image,CacheView * image_view,CubeInfo * cube_info,const size_t level,const unsigned int direction)1643 static MagickBooleanType Riemersma(Image *image,CacheView *image_view,
1644 CubeInfo *cube_info,const size_t level,const unsigned int direction)
1645 {
1646 MagickStatusType
1647 status;
1648
1649 status=MagickTrue;
1650 if (level == 1)
1651 switch (direction)
1652 {
1653 case WestGravity:
1654 {
1655 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1656 if (status != MagickFalse)
1657 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1658 if (status != MagickFalse)
1659 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1660 break;
1661 }
1662 case EastGravity:
1663 {
1664 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1665 if (status != MagickFalse)
1666 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1667 if (status != MagickFalse)
1668 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1669 break;
1670 }
1671 case NorthGravity:
1672 {
1673 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1674 if (status != MagickFalse)
1675 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1676 if (status != MagickFalse)
1677 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1678 break;
1679 }
1680 case SouthGravity:
1681 {
1682 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1683 if (status != MagickFalse)
1684 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1685 if (status != MagickFalse)
1686 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1687 break;
1688 }
1689 default:
1690 break;
1691 }
1692 else
1693 switch (direction)
1694 {
1695 case WestGravity:
1696 {
1697 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1698 if (status != MagickFalse)
1699 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1700 if (status != MagickFalse)
1701 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1702 if (status != MagickFalse)
1703 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1704 if (status != MagickFalse)
1705 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1706 if (status != MagickFalse)
1707 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1708 if (status != MagickFalse)
1709 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1710 break;
1711 }
1712 case EastGravity:
1713 {
1714 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1715 if (status != MagickFalse)
1716 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1717 if (status != MagickFalse)
1718 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1719 if (status != MagickFalse)
1720 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1721 if (status != MagickFalse)
1722 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1723 if (status != MagickFalse)
1724 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1725 if (status != MagickFalse)
1726 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1727 break;
1728 }
1729 case NorthGravity:
1730 {
1731 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1732 if (status != MagickFalse)
1733 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1734 if (status != MagickFalse)
1735 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1736 if (status != MagickFalse)
1737 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1738 if (status != MagickFalse)
1739 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1740 if (status != MagickFalse)
1741 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1742 if (status != MagickFalse)
1743 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1744 break;
1745 }
1746 case SouthGravity:
1747 {
1748 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1749 if (status != MagickFalse)
1750 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1751 if (status != MagickFalse)
1752 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1753 if (status != MagickFalse)
1754 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1755 if (status != MagickFalse)
1756 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1757 if (status != MagickFalse)
1758 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1759 if (status != MagickFalse)
1760 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1761 break;
1762 }
1763 default:
1764 break;
1765 }
1766 return(status != 0 ? MagickTrue : MagickFalse);
1767 }
1768
RiemersmaDither(Image * image,CacheView * image_view,CubeInfo * cube_info,const unsigned int direction)1769 static MagickBooleanType RiemersmaDither(Image *image,CacheView *image_view,
1770 CubeInfo *cube_info,const unsigned int direction)
1771 {
1772 #define DitherImageTag "Dither/Image"
1773
1774 CubeInfo
1775 *p;
1776
1777 DoublePixelPacket
1778 color,
1779 pixel;
1780
1781 MagickBooleanType
1782 proceed;
1783
1784 size_t
1785 index;
1786
1787 p=cube_info;
1788 if ((p->x >= 0) && (p->x < (ssize_t) image->columns) &&
1789 (p->y >= 0) && (p->y < (ssize_t) image->rows))
1790 {
1791 ExceptionInfo
1792 *exception;
1793
1794 IndexPacket
1795 *magick_restrict indexes;
1796
1797 PixelPacket
1798 *magick_restrict q;
1799
1800 ssize_t
1801 i;
1802
1803 /*
1804 Distribute error.
1805 */
1806 exception=(&image->exception);
1807 q=GetCacheViewAuthenticPixels(image_view,p->x,p->y,1,1,exception);
1808 if (q == (PixelPacket *) NULL)
1809 return(MagickFalse);
1810 indexes=GetCacheViewAuthenticIndexQueue(image_view);
1811 AssociateAlphaPixel(cube_info,q,&pixel);
1812 for (i=0; i < ErrorQueueLength; i++)
1813 {
1814 pixel.red+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1815 p->error[i].red;
1816 pixel.green+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1817 p->error[i].green;
1818 pixel.blue+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1819 p->error[i].blue;
1820 if (cube_info->associate_alpha != MagickFalse)
1821 pixel.opacity+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1822 p->error[i].opacity;
1823 }
1824 pixel.red=(MagickRealType) ClampPixel(pixel.red);
1825 pixel.green=(MagickRealType) ClampPixel(pixel.green);
1826 pixel.blue=(MagickRealType) ClampPixel(pixel.blue);
1827 if (cube_info->associate_alpha != MagickFalse)
1828 pixel.opacity=(MagickRealType) ClampPixel(pixel.opacity);
1829 i=CacheOffset(cube_info,&pixel);
1830 if (p->cache[i] < 0)
1831 {
1832 NodeInfo
1833 *node_info;
1834
1835 size_t
1836 id;
1837
1838 /*
1839 Identify the deepest node containing the pixel's color.
1840 */
1841 node_info=p->root;
1842 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1843 {
1844 id=ColorToNodeId(cube_info,&pixel,index);
1845 if (node_info->child[id] == (NodeInfo *) NULL)
1846 break;
1847 node_info=node_info->child[id];
1848 }
1849 /*
1850 Find closest color among siblings and their children.
1851 */
1852 p->target=pixel;
1853 p->distance=(MagickRealType) (4.0*(QuantumRange+1.0)*((MagickRealType)
1854 QuantumRange+1.0)+1.0);
1855 ClosestColor(image,p,node_info->parent);
1856 p->cache[i]=(ssize_t) p->color_number;
1857 }
1858 /*
1859 Assign pixel to closest colormap entry.
1860 */
1861 index=(size_t) (1*p->cache[i]);
1862 if (image->storage_class == PseudoClass)
1863 *indexes=(IndexPacket) index;
1864 if (cube_info->quantize_info->measure_error == MagickFalse)
1865 {
1866 SetPixelRgb(q,image->colormap+index);
1867 if (cube_info->associate_alpha != MagickFalse)
1868 SetPixelOpacity(q,image->colormap[index].opacity);
1869 }
1870 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1871 return(MagickFalse);
1872 /*
1873 Propagate the error as the last entry of the error queue.
1874 */
1875 (void) memmove(p->error,p->error+1,(ErrorQueueLength-1)*
1876 sizeof(p->error[0]));
1877 AssociateAlphaPixel(cube_info,image->colormap+index,&color);
1878 p->error[ErrorQueueLength-1].red=pixel.red-color.red;
1879 p->error[ErrorQueueLength-1].green=pixel.green-color.green;
1880 p->error[ErrorQueueLength-1].blue=pixel.blue-color.blue;
1881 if (cube_info->associate_alpha != MagickFalse)
1882 p->error[ErrorQueueLength-1].opacity=pixel.opacity-color.opacity;
1883 proceed=SetImageProgress(image,DitherImageTag,p->offset,p->span);
1884 if (proceed == MagickFalse)
1885 return(MagickFalse);
1886 p->offset++;
1887 }
1888 switch (direction)
1889 {
1890 case WestGravity: p->x--; break;
1891 case EastGravity: p->x++; break;
1892 case NorthGravity: p->y--; break;
1893 case SouthGravity: p->y++; break;
1894 }
1895 return(MagickTrue);
1896 }
1897
DitherImage(Image * image,CubeInfo * cube_info)1898 static MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info)
1899 {
1900 CacheView
1901 *image_view;
1902
1903 const char
1904 *artifact;
1905
1906 MagickBooleanType
1907 status;
1908
1909 size_t
1910 extent,
1911 level;
1912
1913 artifact=GetImageArtifact(image,"dither:diffusion-amount");
1914 if (artifact != (const char *) NULL)
1915 cube_info->diffusion=StringToDoubleInterval(artifact,1.0);
1916 if (cube_info->quantize_info->dither_method != RiemersmaDitherMethod)
1917 return(FloydSteinbergDither(image,cube_info));
1918 /*
1919 Distribute quantization error along a Hilbert curve.
1920 */
1921 (void) memset(cube_info->error,0,ErrorQueueLength*sizeof(*cube_info->error));
1922 cube_info->x=0;
1923 cube_info->y=0;
1924 extent=MagickMax(image->columns,image->rows);
1925 level=(size_t) log2((double) extent);
1926 if ((1UL << level) < extent)
1927 level++;
1928 cube_info->offset=0;
1929 cube_info->span=(MagickSizeType) image->columns*image->rows;
1930 image_view=AcquireAuthenticCacheView(image,&image->exception);
1931 status=MagickTrue;
1932 if (level > 0)
1933 status=Riemersma(image,image_view,cube_info,level,NorthGravity);
1934 if (status != MagickFalse)
1935 status=RiemersmaDither(image,image_view,cube_info,ForgetGravity);
1936 image_view=DestroyCacheView(image_view);
1937 return(status);
1938 }
1939
1940 /*
1941 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1942 % %
1943 % %
1944 % %
1945 + G e t C u b e I n f o %
1946 % %
1947 % %
1948 % %
1949 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1950 %
1951 % GetCubeInfo() initialize the Cube data structure.
1952 %
1953 % The format of the GetCubeInfo method is:
1954 %
1955 % CubeInfo GetCubeInfo(const QuantizeInfo *quantize_info,
1956 % const size_t depth,const size_t maximum_colors)
1957 %
1958 % A description of each parameter follows.
1959 %
1960 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1961 %
1962 % o depth: Normally, this integer value is zero or one. A zero or
1963 % one tells Quantize to choose a optimal tree depth of Log4(number_colors).
1964 % A tree of this depth generally allows the best representation of the
1965 % reference image with the least amount of memory and the fastest
1966 % computational speed. In some cases, such as an image with low color
1967 % dispersion (a few number of colors), a value other than
1968 % Log4(number_colors) is required. To expand the color tree completely,
1969 % use a value of 8.
1970 %
1971 % o maximum_colors: maximum colors.
1972 %
1973 */
GetCubeInfo(const QuantizeInfo * quantize_info,const size_t depth,const size_t maximum_colors)1974 static CubeInfo *GetCubeInfo(const QuantizeInfo *quantize_info,
1975 const size_t depth,const size_t maximum_colors)
1976 {
1977 CubeInfo
1978 *cube_info;
1979
1980 MagickRealType
1981 weight;
1982
1983 size_t
1984 length;
1985
1986 ssize_t
1987 i;
1988
1989 /*
1990 Initialize tree to describe color cube_info.
1991 */
1992 cube_info=(CubeInfo *) AcquireMagickMemory(sizeof(*cube_info));
1993 if (cube_info == (CubeInfo *) NULL)
1994 return((CubeInfo *) NULL);
1995 (void) memset(cube_info,0,sizeof(*cube_info));
1996 cube_info->depth=depth;
1997 if (cube_info->depth > MaxTreeDepth)
1998 cube_info->depth=MaxTreeDepth;
1999 if (cube_info->depth < 2)
2000 cube_info->depth=2;
2001 cube_info->maximum_colors=maximum_colors;
2002 /*
2003 Initialize root node.
2004 */
2005 cube_info->root=GetNodeInfo(cube_info,0,0,(NodeInfo *) NULL);
2006 if (cube_info->root == (NodeInfo *) NULL)
2007 return((CubeInfo *) NULL);
2008 cube_info->root->parent=cube_info->root;
2009 cube_info->quantize_info=CloneQuantizeInfo(quantize_info);
2010 if (cube_info->quantize_info->dither == MagickFalse)
2011 return(cube_info);
2012 /*
2013 Initialize dither resources.
2014 */
2015 length=(size_t) (1UL << (4*(8-CacheShift)));
2016 cube_info->memory_info=AcquireVirtualMemory(length,sizeof(*cube_info->cache));
2017 if (cube_info->memory_info == (MemoryInfo *) NULL)
2018 return((CubeInfo *) NULL);
2019 cube_info->cache=(ssize_t *) GetVirtualMemoryBlob(cube_info->memory_info);
2020 /*
2021 Initialize color cache.
2022 */
2023 (void) memset(cube_info->cache,(-1),sizeof(*cube_info->cache)*length);
2024 /*
2025 Distribute weights along a curve of exponential decay.
2026 */
2027 weight=1.0;
2028 for (i=0; i < ErrorQueueLength; i++)
2029 {
2030 cube_info->weights[i]=PerceptibleReciprocal(weight);
2031 weight*=exp(log(1.0/ErrorRelativeWeight)/(ErrorQueueLength-1.0));
2032 }
2033 cube_info->diffusion=1.0;
2034 return(cube_info);
2035 }
2036
2037 /*
2038 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2039 % %
2040 % %
2041 % %
2042 + G e t N o d e I n f o %
2043 % %
2044 % %
2045 % %
2046 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2047 %
2048 % GetNodeInfo() allocates memory for a new node in the color cube tree and
2049 % presets all fields to zero.
2050 %
2051 % The format of the GetNodeInfo method is:
2052 %
2053 % NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id,
2054 % const size_t level,NodeInfo *parent)
2055 %
2056 % A description of each parameter follows.
2057 %
2058 % o node: The GetNodeInfo method returns a pointer to a queue of nodes.
2059 %
2060 % o id: Specifies the child number of the node.
2061 %
2062 % o level: Specifies the level in the storage_class the node resides.
2063 %
2064 */
GetNodeInfo(CubeInfo * cube_info,const size_t id,const size_t level,NodeInfo * parent)2065 static NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id,
2066 const size_t level,NodeInfo *parent)
2067 {
2068 NodeInfo
2069 *node_info;
2070
2071 if (cube_info->free_nodes == 0)
2072 {
2073 Nodes
2074 *nodes;
2075
2076 /*
2077 Allocate a new queue of nodes.
2078 */
2079 nodes=(Nodes *) AcquireMagickMemory(sizeof(*nodes));
2080 if (nodes == (Nodes *) NULL)
2081 return((NodeInfo *) NULL);
2082 nodes->nodes=(NodeInfo *) AcquireQuantumMemory(NodesInAList,
2083 sizeof(*nodes->nodes));
2084 if (nodes->nodes == (NodeInfo *) NULL)
2085 return((NodeInfo *) NULL);
2086 nodes->next=cube_info->node_queue;
2087 cube_info->node_queue=nodes;
2088 cube_info->next_node=nodes->nodes;
2089 cube_info->free_nodes=NodesInAList;
2090 }
2091 cube_info->nodes++;
2092 cube_info->free_nodes--;
2093 node_info=cube_info->next_node++;
2094 (void) memset(node_info,0,sizeof(*node_info));
2095 node_info->parent=parent;
2096 node_info->id=id;
2097 node_info->level=level;
2098 return(node_info);
2099 }
2100
2101 /*
2102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2103 % %
2104 % %
2105 % %
2106 % G e t I m a g e Q u a n t i z e E r r o r %
2107 % %
2108 % %
2109 % %
2110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2111 %
2112 % GetImageQuantizeError() measures the difference between the original
2113 % and quantized images. This difference is the total quantization error.
2114 % The error is computed by summing over all pixels in an image the distance
2115 % squared in RGB space between each reference pixel value and its quantized
2116 % value. These values are computed:
2117 %
2118 % o mean_error_per_pixel: This value is the mean error for any single
2119 % pixel in the image.
2120 %
2121 % o normalized_mean_square_error: This value is the normalized mean
2122 % quantization error for any single pixel in the image. This distance
2123 % measure is normalized to a range between 0 and 1. It is independent
2124 % of the range of red, green, and blue values in the image.
2125 %
2126 % o normalized_maximum_square_error: Thsi value is the normalized
2127 % maximum quantization error for any single pixel in the image. This
2128 % distance measure is normalized to a range between 0 and 1. It is
2129 % independent of the range of red, green, and blue values in your image.
2130 %
2131 % The format of the GetImageQuantizeError method is:
2132 %
2133 % MagickBooleanType GetImageQuantizeError(Image *image)
2134 %
2135 % A description of each parameter follows.
2136 %
2137 % o image: the image.
2138 %
2139 */
GetImageQuantizeError(Image * image)2140 MagickExport MagickBooleanType GetImageQuantizeError(Image *image)
2141 {
2142 CacheView
2143 *image_view;
2144
2145 ExceptionInfo
2146 *exception;
2147
2148 IndexPacket
2149 *indexes;
2150
2151 MagickRealType
2152 alpha,
2153 area,
2154 beta,
2155 distance,
2156 gamma,
2157 maximum_error,
2158 mean_error,
2159 mean_error_per_pixel;
2160
2161 ssize_t
2162 index,
2163 y;
2164
2165 assert(image != (Image *) NULL);
2166 assert(image->signature == MagickCoreSignature);
2167 if (image->debug != MagickFalse)
2168 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2169 image->total_colors=GetNumberColors(image,(FILE *) NULL,&image->exception);
2170 (void) memset(&image->error,0,sizeof(image->error));
2171 if (image->storage_class == DirectClass)
2172 return(MagickTrue);
2173 alpha=1.0;
2174 beta=1.0;
2175 area=3.0*image->columns*image->rows;
2176 maximum_error=0.0;
2177 mean_error_per_pixel=0.0;
2178 mean_error=0.0;
2179 exception=(&image->exception);
2180 image_view=AcquireVirtualCacheView(image,exception);
2181 for (y=0; y < (ssize_t) image->rows; y++)
2182 {
2183 const PixelPacket
2184 *magick_restrict p;
2185
2186 ssize_t
2187 x;
2188
2189 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
2190 if (p == (const PixelPacket *) NULL)
2191 break;
2192 indexes=GetCacheViewAuthenticIndexQueue(image_view);
2193 for (x=0; x < (ssize_t) image->columns; x++)
2194 {
2195 index=(ssize_t) GetPixelIndex(indexes+x);
2196 if (image->matte != MagickFalse)
2197 {
2198 alpha=(MagickRealType) (QuantumScale*(GetPixelAlpha(p)));
2199 beta=(MagickRealType) (QuantumScale*(QuantumRange-
2200 image->colormap[index].opacity));
2201 }
2202 distance=fabs((double) (alpha*GetPixelRed(p)-beta*
2203 image->colormap[index].red));
2204 mean_error_per_pixel+=distance;
2205 mean_error+=distance*distance;
2206 if (distance > maximum_error)
2207 maximum_error=distance;
2208 distance=fabs((double) (alpha*GetPixelGreen(p)-beta*
2209 image->colormap[index].green));
2210 mean_error_per_pixel+=distance;
2211 mean_error+=distance*distance;
2212 if (distance > maximum_error)
2213 maximum_error=distance;
2214 distance=fabs((double) (alpha*GetPixelBlue(p)-beta*
2215 image->colormap[index].blue));
2216 mean_error_per_pixel+=distance;
2217 mean_error+=distance*distance;
2218 if (distance > maximum_error)
2219 maximum_error=distance;
2220 p++;
2221 }
2222 }
2223 image_view=DestroyCacheView(image_view);
2224 gamma=PerceptibleReciprocal(area);
2225 image->error.mean_error_per_pixel=gamma*mean_error_per_pixel;
2226 image->error.normalized_mean_error=gamma*QuantumScale*QuantumScale*mean_error;
2227 image->error.normalized_maximum_error=QuantumScale*maximum_error;
2228 return(MagickTrue);
2229 }
2230
2231 /*
2232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2233 % %
2234 % %
2235 % %
2236 % G e t Q u a n t i z e I n f o %
2237 % %
2238 % %
2239 % %
2240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2241 %
2242 % GetQuantizeInfo() initializes the QuantizeInfo structure.
2243 %
2244 % The format of the GetQuantizeInfo method is:
2245 %
2246 % GetQuantizeInfo(QuantizeInfo *quantize_info)
2247 %
2248 % A description of each parameter follows:
2249 %
2250 % o quantize_info: Specifies a pointer to a QuantizeInfo structure.
2251 %
2252 */
GetQuantizeInfo(QuantizeInfo * quantize_info)2253 MagickExport void GetQuantizeInfo(QuantizeInfo *quantize_info)
2254 {
2255 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
2256 assert(quantize_info != (QuantizeInfo *) NULL);
2257 (void) memset(quantize_info,0,sizeof(*quantize_info));
2258 quantize_info->number_colors=256;
2259 quantize_info->dither=MagickTrue;
2260 quantize_info->dither_method=RiemersmaDitherMethod;
2261 quantize_info->colorspace=UndefinedColorspace;
2262 quantize_info->measure_error=MagickFalse;
2263 quantize_info->signature=MagickCoreSignature;
2264 }
2265
2266 /*
2267 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2268 % %
2269 % %
2270 % %
2271 % P o s t e r i z e I m a g e C h a n n e l %
2272 % %
2273 % %
2274 % %
2275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2276 %
2277 % PosterizeImage() reduces the image to a limited number of colors for a
2278 % "poster" effect.
2279 %
2280 % The format of the PosterizeImage method is:
2281 %
2282 % MagickBooleanType PosterizeImage(Image *image,const size_t levels,
2283 % const MagickBooleanType dither)
2284 % MagickBooleanType PosterizeImageChannel(Image *image,
2285 % const ChannelType channel,const size_t levels,
2286 % const MagickBooleanType dither)
2287 %
2288 % A description of each parameter follows:
2289 %
2290 % o image: Specifies a pointer to an Image structure.
2291 %
2292 % o levels: Number of color levels allowed in each channel. Very low values
2293 % (2, 3, or 4) have the most visible effect.
2294 %
2295 % o dither: Set this integer value to something other than zero to dither
2296 % the mapped image.
2297 %
2298 */
2299
MagickRound(double x)2300 static inline double MagickRound(double x)
2301 {
2302 /*
2303 Round the fraction to nearest integer.
2304 */
2305 if ((x-floor(x)) < (ceil(x)-x))
2306 return(floor(x));
2307 return(ceil(x));
2308 }
2309
PosterizeImage(Image * image,const size_t levels,const MagickBooleanType dither)2310 MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels,
2311 const MagickBooleanType dither)
2312 {
2313 MagickBooleanType
2314 status;
2315
2316 status=PosterizeImageChannel(image,DefaultChannels,levels,dither);
2317 return(status);
2318 }
2319
PosterizeImageChannel(Image * image,const ChannelType channel,const size_t levels,const MagickBooleanType dither)2320 MagickExport MagickBooleanType PosterizeImageChannel(Image *image,
2321 const ChannelType channel,const size_t levels,const MagickBooleanType dither)
2322 {
2323 #define PosterizeImageTag "Posterize/Image"
2324 #define PosterizePixel(pixel) ClampToQuantum((MagickRealType) QuantumRange*( \
2325 MagickRound(QuantumScale*pixel*(levels-1)))/MagickMax((ssize_t) levels-1,1))
2326
2327 CacheView
2328 *image_view;
2329
2330 ExceptionInfo
2331 *exception;
2332
2333 MagickBooleanType
2334 status;
2335
2336 MagickOffsetType
2337 progress;
2338
2339 QuantizeInfo
2340 *quantize_info;
2341
2342 ssize_t
2343 i,
2344 y;
2345
2346 assert(image != (Image *) NULL);
2347 assert(image->signature == MagickCoreSignature);
2348 if (image->debug != MagickFalse)
2349 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2350 if (image->storage_class == PseudoClass)
2351 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2352 #pragma omp parallel for schedule(static) shared(progress,status) \
2353 magick_number_threads(image,image,image->colors,1)
2354 #endif
2355 for (i=0; i < (ssize_t) image->colors; i++)
2356 {
2357 /*
2358 Posterize colormap.
2359 */
2360 if ((channel & RedChannel) != 0)
2361 image->colormap[i].red=PosterizePixel(image->colormap[i].red);
2362 if ((channel & GreenChannel) != 0)
2363 image->colormap[i].green=PosterizePixel(image->colormap[i].green);
2364 if ((channel & BlueChannel) != 0)
2365 image->colormap[i].blue=PosterizePixel(image->colormap[i].blue);
2366 if ((channel & OpacityChannel) != 0)
2367 image->colormap[i].opacity=PosterizePixel(image->colormap[i].opacity);
2368 }
2369 /*
2370 Posterize image.
2371 */
2372 status=MagickTrue;
2373 progress=0;
2374 exception=(&image->exception);
2375 image_view=AcquireAuthenticCacheView(image,exception);
2376 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2377 #pragma omp parallel for schedule(static) shared(progress,status) \
2378 magick_number_threads(image,image,image->rows,1)
2379 #endif
2380 for (y=0; y < (ssize_t) image->rows; y++)
2381 {
2382 IndexPacket
2383 *magick_restrict indexes;
2384
2385 PixelPacket
2386 *magick_restrict q;
2387
2388 ssize_t
2389 x;
2390
2391 if (status == MagickFalse)
2392 continue;
2393 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2394 if (q == (PixelPacket *) NULL)
2395 {
2396 status=MagickFalse;
2397 continue;
2398 }
2399 indexes=GetCacheViewAuthenticIndexQueue(image_view);
2400 for (x=0; x < (ssize_t) image->columns; x++)
2401 {
2402 if ((channel & RedChannel) != 0)
2403 SetPixelRed(q,PosterizePixel(GetPixelRed(q)));
2404 if ((channel & GreenChannel) != 0)
2405 SetPixelGreen(q,PosterizePixel(GetPixelGreen(q)));
2406 if ((channel & BlueChannel) != 0)
2407 SetPixelBlue(q,PosterizePixel(GetPixelBlue(q)));
2408 if (((channel & OpacityChannel) != 0) &&
2409 (image->matte != MagickFalse))
2410 SetPixelOpacity(q,PosterizePixel(GetPixelOpacity(q)));
2411 if (((channel & IndexChannel) != 0) &&
2412 (image->colorspace == CMYKColorspace))
2413 SetPixelIndex(indexes+x,PosterizePixel(GetPixelIndex(indexes+x)));
2414 q++;
2415 }
2416 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2417 status=MagickFalse;
2418 if (image->progress_monitor != (MagickProgressMonitor) NULL)
2419 {
2420 MagickBooleanType
2421 proceed;
2422
2423 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2424 #pragma omp atomic
2425 #endif
2426 progress++;
2427 proceed=SetImageProgress(image,PosterizeImageTag,progress,image->rows);
2428 if (proceed == MagickFalse)
2429 status=MagickFalse;
2430 }
2431 }
2432 image_view=DestroyCacheView(image_view);
2433 quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL);
2434 quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels*
2435 levels,MaxColormapSize+1);
2436 quantize_info->dither=dither;
2437 quantize_info->tree_depth=MaxTreeDepth;
2438 status=QuantizeImage(quantize_info,image);
2439 quantize_info=DestroyQuantizeInfo(quantize_info);
2440 return(status);
2441 }
2442
2443 /*
2444 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2445 % %
2446 % %
2447 % %
2448 + P r u n e C h i l d %
2449 % %
2450 % %
2451 % %
2452 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2453 %
2454 % PruneChild() deletes the given node and merges its statistics into its
2455 % parent.
2456 %
2457 % The format of the PruneSubtree method is:
2458 %
2459 % PruneChild(CubeInfo *cube_info,const NodeInfo *node_info)
2460 %
2461 % A description of each parameter follows.
2462 %
2463 % o cube_info: A pointer to the Cube structure.
2464 %
2465 % o node_info: pointer to node in color cube tree that is to be pruned.
2466 %
2467 */
PruneChild(CubeInfo * cube_info,const NodeInfo * node_info)2468 static void PruneChild(CubeInfo *cube_info,const NodeInfo *node_info)
2469 {
2470 NodeInfo
2471 *parent;
2472
2473 size_t
2474 number_children;
2475
2476 ssize_t
2477 i;
2478
2479 /*
2480 Traverse any children.
2481 */
2482 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2483 for (i=0; i < (ssize_t) number_children; i++)
2484 if (node_info->child[i] != (NodeInfo *) NULL)
2485 PruneChild(cube_info,node_info->child[i]);
2486 if (cube_info->nodes > cube_info->maximum_colors)
2487 {
2488 /*
2489 Merge color statistics into parent.
2490 */
2491 parent=node_info->parent;
2492 parent->number_unique+=node_info->number_unique;
2493 parent->total_color.red+=node_info->total_color.red;
2494 parent->total_color.green+=node_info->total_color.green;
2495 parent->total_color.blue+=node_info->total_color.blue;
2496 parent->total_color.opacity+=node_info->total_color.opacity;
2497 parent->child[node_info->id]=(NodeInfo *) NULL;
2498 cube_info->nodes--;
2499 }
2500 }
2501
2502 /*
2503 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2504 % %
2505 % %
2506 % %
2507 + P r u n e L e v e l %
2508 % %
2509 % %
2510 % %
2511 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2512 %
2513 % PruneLevel() deletes all nodes at the bottom level of the color tree merging
2514 % their color statistics into their parent node.
2515 %
2516 % The format of the PruneLevel method is:
2517 %
2518 % PruneLevel(CubeInfo *cube_info,const NodeInfo *node_info)
2519 %
2520 % A description of each parameter follows.
2521 %
2522 % o cube_info: A pointer to the Cube structure.
2523 %
2524 % o node_info: pointer to node in color cube tree that is to be pruned.
2525 %
2526 */
PruneLevel(CubeInfo * cube_info,const NodeInfo * node_info)2527 static void PruneLevel(CubeInfo *cube_info,const NodeInfo *node_info)
2528 {
2529 size_t
2530 number_children;
2531
2532 ssize_t
2533 i;
2534
2535 /*
2536 Traverse any children.
2537 */
2538 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2539 for (i=0; i < (ssize_t) number_children; i++)
2540 if (node_info->child[i] != (NodeInfo *) NULL)
2541 PruneLevel(cube_info,node_info->child[i]);
2542 if (node_info->level == cube_info->depth)
2543 PruneChild(cube_info,node_info);
2544 }
2545
2546 /*
2547 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2548 % %
2549 % %
2550 % %
2551 + P r u n e T o C u b e D e p t h %
2552 % %
2553 % %
2554 % %
2555 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2556 %
2557 % PruneToCubeDepth() deletes any nodes at a depth greater than
2558 % cube_info->depth while merging their color statistics into their parent
2559 % node.
2560 %
2561 % The format of the PruneToCubeDepth method is:
2562 %
2563 % PruneToCubeDepth(CubeInfo *cube_info,const NodeInfo *node_info)
2564 %
2565 % A description of each parameter follows.
2566 %
2567 % o cube_info: A pointer to the Cube structure.
2568 %
2569 % o node_info: pointer to node in color cube tree that is to be pruned.
2570 %
2571 */
PruneToCubeDepth(CubeInfo * cube_info,const NodeInfo * node_info)2572 static void PruneToCubeDepth(CubeInfo *cube_info,const NodeInfo *node_info)
2573 {
2574 size_t
2575 number_children;
2576
2577 ssize_t
2578 i;
2579
2580 /*
2581 Traverse any children.
2582 */
2583 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2584 for (i=0; i < (ssize_t) number_children; i++)
2585 if (node_info->child[i] != (NodeInfo *) NULL)
2586 PruneToCubeDepth(cube_info,node_info->child[i]);
2587 if (node_info->level > cube_info->depth)
2588 PruneChild(cube_info,node_info);
2589 }
2590
2591 /*
2592 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2593 % %
2594 % %
2595 % %
2596 % Q u a n t i z e I m a g e %
2597 % %
2598 % %
2599 % %
2600 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2601 %
2602 % QuantizeImage() analyzes the colors within a reference image and chooses a
2603 % fixed number of colors to represent the image. The goal of the algorithm
2604 % is to minimize the color difference between the input and output image while
2605 % minimizing the processing time.
2606 %
2607 % The format of the QuantizeImage method is:
2608 %
2609 % MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
2610 % Image *image)
2611 %
2612 % A description of each parameter follows:
2613 %
2614 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2615 %
2616 % o image: the image.
2617 %
2618 */
QuantizeImage(const QuantizeInfo * quantize_info,Image * image)2619 MagickExport MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
2620 Image *image)
2621 {
2622 CubeInfo
2623 *cube_info;
2624
2625 MagickBooleanType
2626 status;
2627
2628 size_t
2629 depth,
2630 maximum_colors;
2631
2632 assert(quantize_info != (const QuantizeInfo *) NULL);
2633 assert(quantize_info->signature == MagickCoreSignature);
2634 assert(image != (Image *) NULL);
2635 assert(image->signature == MagickCoreSignature);
2636 if (image->debug != MagickFalse)
2637 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2638 maximum_colors=quantize_info->number_colors;
2639 if (maximum_colors == 0)
2640 maximum_colors=MaxColormapSize;
2641 if (maximum_colors > MaxColormapSize)
2642 maximum_colors=MaxColormapSize;
2643 if (image->matte == MagickFalse)
2644 {
2645 if (SetImageGray(image,&image->exception) != MagickFalse)
2646 (void) SetGrayscaleImage(image);
2647 }
2648 depth=quantize_info->tree_depth;
2649 if (depth == 0)
2650 {
2651 size_t
2652 colors;
2653
2654 /*
2655 Depth of color tree is: Log4(colormap size)+2.
2656 */
2657 colors=maximum_colors;
2658 for (depth=1; colors != 0; depth++)
2659 colors>>=2;
2660 if ((quantize_info->dither != MagickFalse) && (depth > 2))
2661 depth--;
2662 if ((image->matte != MagickFalse) && (depth > 5))
2663 depth--;
2664 if (SetImageGray(image,&image->exception) != MagickFalse)
2665 depth=MaxTreeDepth;
2666 }
2667 /*
2668 Initialize color cube.
2669 */
2670 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2671 if (cube_info == (CubeInfo *) NULL)
2672 ThrowBinaryImageException(ResourceLimitError,"MemoryAllocationFailed",
2673 image->filename);
2674 status=ClassifyImageColors(cube_info,image,&image->exception);
2675 if (status != MagickFalse)
2676 {
2677 /*
2678 Reduce the number of colors in the image.
2679 */
2680 if (cube_info->colors > cube_info->maximum_colors)
2681 ReduceImageColors(image,cube_info);
2682 status=AssignImageColors(image,cube_info);
2683 }
2684 DestroyCubeInfo(cube_info);
2685 return(status);
2686 }
2687
2688 /*
2689 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2690 % %
2691 % %
2692 % %
2693 % Q u a n t i z e I m a g e s %
2694 % %
2695 % %
2696 % %
2697 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2698 %
2699 % QuantizeImages() analyzes the colors within a set of reference images and
2700 % chooses a fixed number of colors to represent the set. The goal of the
2701 % algorithm is to minimize the color difference between the input and output
2702 % images while minimizing the processing time.
2703 %
2704 % The format of the QuantizeImages method is:
2705 %
2706 % MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
2707 % Image *images)
2708 %
2709 % A description of each parameter follows:
2710 %
2711 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2712 %
2713 % o images: Specifies a pointer to a list of Image structures.
2714 %
2715 */
QuantizeImages(const QuantizeInfo * quantize_info,Image * images)2716 MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
2717 Image *images)
2718 {
2719 CubeInfo
2720 *cube_info;
2721
2722 Image
2723 *image;
2724
2725 MagickBooleanType
2726 proceed,
2727 status;
2728
2729 MagickProgressMonitor
2730 progress_monitor;
2731
2732 size_t
2733 depth,
2734 maximum_colors,
2735 number_images;
2736
2737 ssize_t
2738 i;
2739
2740 assert(quantize_info != (const QuantizeInfo *) NULL);
2741 assert(quantize_info->signature == MagickCoreSignature);
2742 assert(images != (Image *) NULL);
2743 assert(images->signature == MagickCoreSignature);
2744 if (images->debug != MagickFalse)
2745 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
2746 if (GetNextImageInList(images) == (Image *) NULL)
2747 {
2748 /*
2749 Handle a single image with QuantizeImage.
2750 */
2751 status=QuantizeImage(quantize_info,images);
2752 return(status);
2753 }
2754 status=MagickFalse;
2755 maximum_colors=quantize_info->number_colors;
2756 if (maximum_colors == 0)
2757 maximum_colors=MaxColormapSize;
2758 if (maximum_colors > MaxColormapSize)
2759 maximum_colors=MaxColormapSize;
2760 depth=quantize_info->tree_depth;
2761 if (depth == 0)
2762 {
2763 size_t
2764 colors;
2765
2766 /*
2767 Depth of color tree is: Log4(colormap size)+2.
2768 */
2769 colors=maximum_colors;
2770 for (depth=1; colors != 0; depth++)
2771 colors>>=2;
2772 if (quantize_info->dither != MagickFalse)
2773 depth--;
2774 }
2775 /*
2776 Initialize color cube.
2777 */
2778 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2779 if (cube_info == (CubeInfo *) NULL)
2780 {
2781 (void) ThrowMagickException(&images->exception,GetMagickModule(),
2782 ResourceLimitError,"MemoryAllocationFailed","`%s'",images->filename);
2783 return(MagickFalse);
2784 }
2785 number_images=GetImageListLength(images);
2786 image=images;
2787 for (i=0; image != (Image *) NULL; i++)
2788 {
2789 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL,
2790 image->client_data);
2791 status=ClassifyImageColors(cube_info,image,&image->exception);
2792 if (status == MagickFalse)
2793 break;
2794 (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
2795 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2796 number_images);
2797 if (proceed == MagickFalse)
2798 break;
2799 image=GetNextImageInList(image);
2800 }
2801 if (status != MagickFalse)
2802 {
2803 /*
2804 Reduce the number of colors in an image sequence.
2805 */
2806 ReduceImageColors(images,cube_info);
2807 image=images;
2808 for (i=0; image != (Image *) NULL; i++)
2809 {
2810 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor)
2811 NULL,image->client_data);
2812 status=AssignImageColors(image,cube_info);
2813 if (status == MagickFalse)
2814 break;
2815 (void) SetImageProgressMonitor(image,progress_monitor,
2816 image->client_data);
2817 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2818 number_images);
2819 if (proceed == MagickFalse)
2820 break;
2821 image=GetNextImageInList(image);
2822 }
2823 }
2824 DestroyCubeInfo(cube_info);
2825 return(status);
2826 }
2827
2828 /*
2829 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2830 % %
2831 % %
2832 % %
2833 + Q u a n t i z e E r r o r F l a t t e n %
2834 % %
2835 % %
2836 % %
2837 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2838 %
2839 % QuantizeErrorFlatten() traverses the color cube and flattens the quantization
2840 % error into a sorted 1D array. This accelerates the color reduction process.
2841 %
2842 % Contributed by Yoya.
2843 %
2844 % The format of the QuantizeErrorFlatten method is:
2845 %
2846 % size_t QuantizeErrorFlatten(const CubeInfo *cube_info,
2847 % const NodeInfo *node_info,const ssize_t offset,
2848 % MagickRealType *quantize_error)
2849 %
2850 % A description of each parameter follows.
2851 %
2852 % o cube_info: A pointer to the Cube structure.
2853 %
2854 % o node_info: pointer to node in color cube tree that is current pointer.
2855 %
2856 % o offset: quantize error offset.
2857 %
2858 % o quantize_error: the quantization error vector.
2859 %
2860 */
QuantizeErrorFlatten(const CubeInfo * cube_info,const NodeInfo * node_info,const ssize_t offset,MagickRealType * quantize_error)2861 static size_t QuantizeErrorFlatten(const CubeInfo *cube_info,
2862 const NodeInfo *node_info,const ssize_t offset,
2863 MagickRealType *quantize_error)
2864 {
2865 size_t
2866 n,
2867 number_children;
2868
2869 ssize_t
2870 i;
2871
2872 if (offset >= (ssize_t) cube_info->nodes)
2873 return(0);
2874 quantize_error[offset]=node_info->quantize_error;
2875 n=1;
2876 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2877 for (i=0; i < (ssize_t) number_children ; i++)
2878 if (node_info->child[i] != (NodeInfo *) NULL)
2879 n+=QuantizeErrorFlatten(cube_info,node_info->child[i],offset+n,
2880 quantize_error);
2881 return(n);
2882 }
2883
2884 /*
2885 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2886 % %
2887 % %
2888 % %
2889 + R e d u c e %
2890 % %
2891 % %
2892 % %
2893 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2894 %
2895 % Reduce() traverses the color cube tree and prunes any node whose
2896 % quantization error falls below a particular threshold.
2897 %
2898 % The format of the Reduce method is:
2899 %
2900 % Reduce(CubeInfo *cube_info,const NodeInfo *node_info)
2901 %
2902 % A description of each parameter follows.
2903 %
2904 % o cube_info: A pointer to the Cube structure.
2905 %
2906 % o node_info: pointer to node in color cube tree that is to be pruned.
2907 %
2908 */
Reduce(CubeInfo * cube_info,const NodeInfo * node_info)2909 static void Reduce(CubeInfo *cube_info,const NodeInfo *node_info)
2910 {
2911 size_t
2912 number_children;
2913
2914 ssize_t
2915 i;
2916
2917 /*
2918 Traverse any children.
2919 */
2920 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2921 for (i=0; i < (ssize_t) number_children; i++)
2922 if (node_info->child[i] != (NodeInfo *) NULL)
2923 Reduce(cube_info,node_info->child[i]);
2924 if (node_info->quantize_error <= cube_info->pruning_threshold)
2925 PruneChild(cube_info,node_info);
2926 else
2927 {
2928 /*
2929 Find minimum pruning threshold.
2930 */
2931 if (node_info->number_unique > 0)
2932 cube_info->colors++;
2933 if (node_info->quantize_error < cube_info->next_threshold)
2934 cube_info->next_threshold=node_info->quantize_error;
2935 }
2936 }
2937
2938 /*
2939 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2940 % %
2941 % %
2942 % %
2943 + R e d u c e I m a g e C o l o r s %
2944 % %
2945 % %
2946 % %
2947 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2948 %
2949 % ReduceImageColors() repeatedly prunes the tree until the number of nodes
2950 % with n2 > 0 is less than or equal to the maximum number of colors allowed
2951 % in the output image. On any given iteration over the tree, it selects
2952 % those nodes whose E value is minimal for pruning and merges their
2953 % color statistics upward. It uses a pruning threshold, Ep, to govern
2954 % node selection as follows:
2955 %
2956 % Ep = 0
2957 % while number of nodes with (n2 > 0) > required maximum number of colors
2958 % prune all nodes such that E <= Ep
2959 % Set Ep to minimum E in remaining nodes
2960 %
2961 % This has the effect of minimizing any quantization error when merging
2962 % two nodes together.
2963 %
2964 % When a node to be pruned has offspring, the pruning procedure invokes
2965 % itself recursively in order to prune the tree from the leaves upward.
2966 % n2, Sr, Sg, and Sb in a node being pruned are always added to the
2967 % corresponding data in that node's parent. This retains the pruned
2968 % node's color characteristics for later averaging.
2969 %
2970 % For each node, n2 pixels exist for which that node represents the
2971 % smallest volume in RGB space containing those pixel's colors. When n2
2972 % > 0 the node will uniquely define a color in the output image. At the
2973 % beginning of reduction, n2 = 0 for all nodes except a the leaves of
2974 % the tree which represent colors present in the input image.
2975 %
2976 % The other pixel count, n1, indicates the total number of colors
2977 % within the cubic volume which the node represents. This includes n1 -
2978 % n2 pixels whose colors should be defined by nodes at a lower level in
2979 % the tree.
2980 %
2981 % The format of the ReduceImageColors method is:
2982 %
2983 % ReduceImageColors(const Image *image,CubeInfo *cube_info)
2984 %
2985 % A description of each parameter follows.
2986 %
2987 % o image: the image.
2988 %
2989 % o cube_info: A pointer to the Cube structure.
2990 %
2991 */
2992
MagickRealTypeCompare(const void * error_p,const void * error_q)2993 static int MagickRealTypeCompare(const void *error_p,const void *error_q)
2994 {
2995 MagickRealType
2996 *p,
2997 *q;
2998
2999 p=(MagickRealType *) error_p;
3000 q=(MagickRealType *) error_q;
3001 if (*p > *q)
3002 return(1);
3003 if (fabs((double) (*q-*p)) <= MagickEpsilon)
3004 return(0);
3005 return(-1);
3006 }
3007
ReduceImageColors(const Image * image,CubeInfo * cube_info)3008 static void ReduceImageColors(const Image *image,CubeInfo *cube_info)
3009 {
3010 #define ReduceImageTag "Reduce/Image"
3011
3012 MagickBooleanType
3013 proceed;
3014
3015 MagickOffsetType
3016 offset;
3017
3018 size_t
3019 span;
3020
3021 cube_info->next_threshold=0.0;
3022 if (cube_info->colors > cube_info->maximum_colors)
3023 {
3024 MagickRealType
3025 *quantize_error;
3026
3027 /*
3028 Enable rapid reduction of the number of unique colors.
3029 */
3030 quantize_error=(MagickRealType *) AcquireQuantumMemory(cube_info->nodes,
3031 sizeof(*quantize_error));
3032 if (quantize_error != (MagickRealType *) NULL)
3033 {
3034 (void) QuantizeErrorFlatten(cube_info,cube_info->root,0,
3035 quantize_error);
3036 qsort(quantize_error,cube_info->nodes,sizeof(MagickRealType),
3037 MagickRealTypeCompare);
3038 if (cube_info->nodes > (110*(cube_info->maximum_colors+1)/100))
3039 cube_info->next_threshold=quantize_error[cube_info->nodes-110*
3040 (cube_info->maximum_colors+1)/100];
3041 quantize_error=(MagickRealType *) RelinquishMagickMemory(
3042 quantize_error);
3043 }
3044 }
3045 for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; )
3046 {
3047 cube_info->pruning_threshold=cube_info->next_threshold;
3048 cube_info->next_threshold=cube_info->root->quantize_error-1;
3049 cube_info->colors=0;
3050 Reduce(cube_info,cube_info->root);
3051 offset=(MagickOffsetType) span-cube_info->colors;
3052 proceed=SetImageProgress(image,ReduceImageTag,offset,span-
3053 cube_info->maximum_colors+1);
3054 if (proceed == MagickFalse)
3055 break;
3056 }
3057 }
3058
3059 /*
3060 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3061 % %
3062 % %
3063 % %
3064 % R e m a p I m a g e %
3065 % %
3066 % %
3067 % %
3068 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3069 %
3070 % RemapImage() replaces the colors of an image with the closest color from
3071 % a reference image.
3072 %
3073 % The format of the RemapImage method is:
3074 %
3075 % MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
3076 % Image *image,const Image *remap_image)
3077 %
3078 % A description of each parameter follows:
3079 %
3080 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3081 %
3082 % o image: the image.
3083 %
3084 % o remap_image: the reference image.
3085 %
3086 */
RemapImage(const QuantizeInfo * quantize_info,Image * image,const Image * remap_image)3087 MagickExport MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
3088 Image *image,const Image *remap_image)
3089 {
3090 CubeInfo
3091 *cube_info;
3092
3093 MagickBooleanType
3094 status;
3095
3096 /*
3097 Initialize color cube.
3098 */
3099 assert(image != (Image *) NULL);
3100 assert(image->signature == MagickCoreSignature);
3101 if (image->debug != MagickFalse)
3102 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
3103 assert(remap_image != (Image *) NULL);
3104 assert(remap_image->signature == MagickCoreSignature);
3105 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3106 quantize_info->number_colors);
3107 if (cube_info == (CubeInfo *) NULL)
3108 ThrowBinaryImageException(ResourceLimitError,"MemoryAllocationFailed",
3109 image->filename);
3110 status=ClassifyImageColors(cube_info,remap_image,&image->exception);
3111 if (status != MagickFalse)
3112 {
3113 /*
3114 Classify image colors from the reference image.
3115 */
3116 cube_info->quantize_info->number_colors=cube_info->colors;
3117 status=AssignImageColors(image,cube_info);
3118 }
3119 DestroyCubeInfo(cube_info);
3120 return(status);
3121 }
3122
3123 /*
3124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3125 % %
3126 % %
3127 % %
3128 % R e m a p I m a g e s %
3129 % %
3130 % %
3131 % %
3132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3133 %
3134 % RemapImages() replaces the colors of a sequence of images with the
3135 % closest color from a reference image.
3136 %
3137 % The format of the RemapImage method is:
3138 %
3139 % MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
3140 % Image *images,Image *remap_image)
3141 %
3142 % A description of each parameter follows:
3143 %
3144 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3145 %
3146 % o images: the image sequence.
3147 %
3148 % o remap_image: the reference image.
3149 %
3150 */
RemapImages(const QuantizeInfo * quantize_info,Image * images,const Image * remap_image)3151 MagickExport MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
3152 Image *images,const Image *remap_image)
3153 {
3154 CubeInfo
3155 *cube_info;
3156
3157 Image
3158 *image;
3159
3160 MagickBooleanType
3161 status;
3162
3163 assert(images != (Image *) NULL);
3164 assert(images->signature == MagickCoreSignature);
3165 if (images->debug != MagickFalse)
3166 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
3167 image=images;
3168 if (remap_image == (Image *) NULL)
3169 {
3170 /*
3171 Create a global colormap for an image sequence.
3172 */
3173 status=QuantizeImages(quantize_info,images);
3174 return(status);
3175 }
3176 /*
3177 Classify image colors from the reference image.
3178 */
3179 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3180 quantize_info->number_colors);
3181 if (cube_info == (CubeInfo *) NULL)
3182 ThrowBinaryImageException(ResourceLimitError,"MemoryAllocationFailed",
3183 image->filename);
3184 status=ClassifyImageColors(cube_info,remap_image,&image->exception);
3185 if (status != MagickFalse)
3186 {
3187 /*
3188 Classify image colors from the reference image.
3189 */
3190 cube_info->quantize_info->number_colors=cube_info->colors;
3191 image=images;
3192 for ( ; image != (Image *) NULL; image=GetNextImageInList(image))
3193 {
3194 status=AssignImageColors(image,cube_info);
3195 if (status == MagickFalse)
3196 break;
3197 }
3198 }
3199 DestroyCubeInfo(cube_info);
3200 return(status);
3201 }
3202
3203 /*
3204 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3205 % %
3206 % %
3207 % %
3208 % S e t G r a y s c a l e I m a g e %
3209 % %
3210 % %
3211 % %
3212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3213 %
3214 % SetGrayscaleImage() converts an image to a PseudoClass grayscale image.
3215 %
3216 % The format of the SetGrayscaleImage method is:
3217 %
3218 % MagickBooleanType SetGrayscaleImage(Image *image)
3219 %
3220 % A description of each parameter follows:
3221 %
3222 % o image: The image.
3223 %
3224 */
3225
3226 #if defined(__cplusplus) || defined(c_plusplus)
3227 extern "C" {
3228 #endif
3229
IntensityCompare(const void * x,const void * y)3230 static int IntensityCompare(const void *x,const void *y)
3231 {
3232 double
3233 intensity;
3234
3235 PixelPacket
3236 *color_1,
3237 *color_2;
3238
3239 color_1=(PixelPacket *) x;
3240 color_2=(PixelPacket *) y;
3241 intensity=PixelPacketIntensity(color_1)-PixelPacketIntensity(color_2);
3242 if (intensity < (double) INT_MIN)
3243 intensity=(double) INT_MIN;
3244 if (intensity > (double) INT_MAX)
3245 intensity=(double) INT_MAX;
3246 return((int) intensity);
3247 }
3248
3249 #if defined(__cplusplus) || defined(c_plusplus)
3250 }
3251 #endif
3252
SetGrayscaleImage(Image * image)3253 static MagickBooleanType SetGrayscaleImage(Image *image)
3254 {
3255 CacheView
3256 *image_view;
3257
3258 ExceptionInfo
3259 *exception;
3260
3261 MagickBooleanType
3262 status;
3263
3264 PixelPacket
3265 *colormap;
3266
3267 size_t
3268 extent;
3269
3270 ssize_t
3271 *colormap_index,
3272 i,
3273 j,
3274 y;
3275
3276 assert(image != (Image *) NULL);
3277 assert(image->signature == MagickCoreSignature);
3278 exception=(&image->exception);
3279 if (image->type != GrayscaleType)
3280 (void) TransformImageColorspace(image,GRAYColorspace);
3281 extent=MagickMax(image->colors+1,MagickMax(MaxColormapSize,MaxMap+1));
3282 colormap_index=(ssize_t *) AcquireQuantumMemory(extent,
3283 sizeof(*colormap_index));
3284 if (colormap_index == (ssize_t *) NULL)
3285 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3286 image->filename);
3287 if (image->storage_class != PseudoClass)
3288 {
3289 (void) memset(colormap_index,(-1),extent*sizeof(*colormap_index));
3290 if (AcquireImageColormap(image,MaxColormapSize) == MagickFalse)
3291 {
3292 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3293 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3294 image->filename);
3295 }
3296 image->colors=0;
3297 status=MagickTrue;
3298 image_view=AcquireAuthenticCacheView(image,exception);
3299 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3300 #pragma omp parallel for schedule(static) shared(status) \
3301 magick_number_threads(image,image,image->rows,1)
3302 #endif
3303 for (y=0; y < (ssize_t) image->rows; y++)
3304 {
3305 IndexPacket
3306 *magick_restrict indexes;
3307
3308 PixelPacket
3309 *magick_restrict q;
3310
3311 ssize_t
3312 x;
3313
3314 if (status == MagickFalse)
3315 continue;
3316 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
3317 exception);
3318 if (q == (PixelPacket *) NULL)
3319 {
3320 status=MagickFalse;
3321 continue;
3322 }
3323 indexes=GetCacheViewAuthenticIndexQueue(image_view);
3324 for (x=0; x < (ssize_t) image->columns; x++)
3325 {
3326 size_t
3327 intensity;
3328
3329 intensity=ScaleQuantumToMap(GetPixelRed(q));
3330 if (colormap_index[intensity] < 0)
3331 {
3332 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3333 #pragma omp critical (MagickCore_SetGrayscaleImage)
3334 #endif
3335 if (colormap_index[intensity] < 0)
3336 {
3337 colormap_index[intensity]=(ssize_t) image->colors;
3338 image->colormap[image->colors].red=GetPixelRed(q);
3339 image->colormap[image->colors].green=GetPixelGreen(q);
3340 image->colormap[image->colors].blue=GetPixelBlue(q);
3341 image->colors++;
3342 }
3343 }
3344 SetPixelIndex(indexes+x,colormap_index[intensity]);
3345 q++;
3346 }
3347 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3348 status=MagickFalse;
3349 }
3350 image_view=DestroyCacheView(image_view);
3351 }
3352 (void) memset(colormap_index,0,extent*sizeof(*colormap_index));
3353 for (i=0; i < (ssize_t) image->colors; i++)
3354 image->colormap[i].opacity=(Quantum) i;
3355 qsort((void *) image->colormap,image->colors,sizeof(PixelPacket),
3356 IntensityCompare);
3357 colormap=(PixelPacket *) AcquireQuantumMemory(image->colors,
3358 sizeof(*colormap));
3359 if (colormap == (PixelPacket *) NULL)
3360 {
3361 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3362 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3363 image->filename);
3364 }
3365 j=0;
3366 colormap[j]=image->colormap[0];
3367 for (i=0; i < (ssize_t) image->colors; i++)
3368 {
3369 if (IsSameColor(image,&colormap[j],&image->colormap[i]) == MagickFalse)
3370 {
3371 j++;
3372 colormap[j]=image->colormap[i];
3373 }
3374 colormap_index[(ssize_t) image->colormap[i].opacity]=j;
3375 }
3376 image->colors=(size_t) (j+1);
3377 image->colormap=(PixelPacket *) RelinquishMagickMemory(image->colormap);
3378 image->colormap=colormap;
3379 status=MagickTrue;
3380 image_view=AcquireAuthenticCacheView(image,exception);
3381 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3382 #pragma omp parallel for schedule(static) shared(status) \
3383 magick_number_threads(image,image,image->rows,1)
3384 #endif
3385 for (y=0; y < (ssize_t) image->rows; y++)
3386 {
3387 IndexPacket
3388 *magick_restrict indexes;
3389
3390 const PixelPacket
3391 *magick_restrict q;
3392
3393 ssize_t
3394 x;
3395
3396 if (status == MagickFalse)
3397 continue;
3398 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
3399 if (q == (PixelPacket *) NULL)
3400 {
3401 status=MagickFalse;
3402 continue;
3403 }
3404 indexes=GetCacheViewAuthenticIndexQueue(image_view);
3405 for (x=0; x < (ssize_t) image->columns; x++)
3406 SetPixelIndex(indexes+x,colormap_index[ScaleQuantumToMap(GetPixelIndex(
3407 indexes+x))]);
3408 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3409 status=MagickFalse;
3410 }
3411 image_view=DestroyCacheView(image_view);
3412 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3413 image->type=GrayscaleType;
3414 if (SetImageMonochrome(image,&image->exception) != MagickFalse)
3415 image->type=BilevelType;
3416 return(status);
3417 }
3418