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