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