quantize.c revision bd66cbe3ecb61270ac3a6f6298fca8e08d6ee4e9
1/* 2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3% % 4% % 5% % 6% QQQ U U AAA N N TTTTT IIIII ZZZZZ EEEEE % 7% Q Q U U A A NN N T I ZZ E % 8% Q Q U U AAAAA N N N T I ZZZ EEEEE % 9% Q QQ U U A A N NN T I ZZ E % 10% QQQQ UUU A A N N T IIIII ZZZZZ EEEEE % 11% % 12% % 13% MagickCore Methods to Reduce the Number of Unique Colors in an Image % 14% % 15% Software Design % 16% Cristy % 17% July 1992 % 18% % 19% % 20% Copyright 1999-2015 ImageMagick Studio LLC, a non-profit organization % 21% dedicated to making software imaging solutions freely available. % 22% % 23% You may not use this file except in compliance with the License. You may % 24% obtain a copy of the License at % 25% % 26% http://www.imagemagick.org/script/license.php % 27% % 28% Unless required by applicable law or agreed to in writing, software % 29% distributed under the License is distributed on an "AS IS" BASIS, % 30% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. % 31% See the License for the specific language governing permissions and % 32% limitations under the License. % 33% % 34%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 35% 36% Realism in computer graphics typically requires using 24 bits/pixel to 37% generate an image. Yet many graphic display devices do not contain the 38% amount of memory necessary to match the spatial and color resolution of 39% the human eye. The Quantize methods takes a 24 bit image and reduces 40% the number of colors so it can be displayed on raster device with less 41% bits per pixel. In most instances, the quantized image closely 42% resembles the original reference image. 43% 44% A reduction of colors in an image is also desirable for image 45% transmission and real-time animation. 46% 47% QuantizeImage() takes a standard RGB or monochrome images and quantizes 48% them down to some fixed number of colors. 49% 50% For purposes of color allocation, an image is a set of n pixels, where 51% each pixel is a point in RGB space. RGB space is a 3-dimensional 52% vector space, and each pixel, Pi, is defined by an ordered triple of 53% red, green, and blue coordinates, (Ri, Gi, Bi). 54% 55% Each primary color component (red, green, or blue) represents an 56% intensity which varies linearly from 0 to a maximum value, Cmax, which 57% corresponds to full saturation of that color. Color allocation is 58% defined over a domain consisting of the cube in RGB space with opposite 59% vertices at (0,0,0) and (Cmax, Cmax, Cmax). QUANTIZE requires Cmax = 60% 255. 61% 62% The algorithm maps this domain onto a tree in which each node 63% represents a cube within that domain. In the following discussion 64% these cubes are defined by the coordinate of two opposite vertices (vertex 65% nearest the origin in RGB space and the vertex farthest from the origin). 66% 67% The tree's root node represents the entire domain, (0,0,0) through 68% (Cmax,Cmax,Cmax). Each lower level in the tree is generated by 69% subdividing one node's cube into eight smaller cubes of equal size. 70% This corresponds to bisecting the parent cube with planes passing 71% through the midpoints of each edge. 72% 73% The basic algorithm operates in three phases: Classification, 74% Reduction, and Assignment. Classification builds a color description 75% tree for the image. Reduction collapses the tree until the number it 76% represents, at most, the number of colors desired in the output image. 77% Assignment defines the output image's color map and sets each pixel's 78% color by restorage_class in the reduced tree. Our goal is to minimize 79% the numerical discrepancies between the original colors and quantized 80% colors (quantization error). 81% 82% Classification begins by initializing a color description tree of 83% sufficient depth to represent each possible input color in a leaf. 84% However, it is impractical to generate a fully-formed color description 85% tree in the storage_class phase for realistic values of Cmax. If 86% colors components in the input image are quantized to k-bit precision, 87% so that Cmax= 2k-1, the tree would need k levels below the root node to 88% allow representing each possible input color in a leaf. This becomes 89% prohibitive because the tree's total number of nodes is 1 + 90% sum(i=1, k, 8k). 91% 92% A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255. 93% Therefore, to avoid building a fully populated tree, QUANTIZE: (1) 94% Initializes data structures for nodes only as they are needed; (2) 95% Chooses a maximum depth for the tree as a function of the desired 96% number of colors in the output image (currently log2(colormap size)). 97% 98% For each pixel in the input image, storage_class scans downward from 99% the root of the color description tree. At each level of the tree it 100% identifies the single node which represents a cube in RGB space 101% containing the pixel's color. It updates the following data for each 102% such node: 103% 104% n1: Number of pixels whose color is contained in the RGB cube which 105% this node represents; 106% 107% n2: Number of pixels whose color is not represented in a node at 108% lower depth in the tree; initially, n2 = 0 for all nodes except 109% leaves of the tree. 110% 111% Sr, Sg, Sb: Sums of the red, green, and blue component values for all 112% pixels not classified at a lower depth. The combination of these sums 113% and n2 will ultimately characterize the mean color of a set of 114% pixels represented by this node. 115% 116% E: the distance squared in RGB space between each pixel contained 117% within a node and the nodes' center. This represents the 118% quantization error for a node. 119% 120% Reduction repeatedly prunes the tree until the number of nodes with n2 121% > 0 is less than or equal to the maximum number of colors allowed in 122% the output image. On any given iteration over the tree, it selects 123% those nodes whose E count is minimal for pruning and merges their color 124% statistics upward. It uses a pruning threshold, Ep, to govern node 125% selection as follows: 126% 127% Ep = 0 128% while number of nodes with (n2 > 0) > required maximum number of colors 129% prune all nodes such that E <= Ep 130% Set Ep to minimum E in remaining nodes 131% 132% This has the effect of minimizing any quantization error when merging 133% two nodes together. 134% 135% When a node to be pruned has offspring, the pruning procedure invokes 136% itself recursively in order to prune the tree from the leaves upward. 137% n2, Sr, Sg, and Sb in a node being pruned are always added to the 138% corresponding data in that node's parent. This retains the pruned 139% node's color characteristics for later averaging. 140% 141% For each node, n2 pixels exist for which that node represents the 142% smallest volume in RGB space containing those pixel's colors. When n2 143% > 0 the node will uniquely define a color in the output image. At the 144% beginning of reduction, n2 = 0 for all nodes except a the leaves of 145% the tree which represent colors present in the input image. 146% 147% The other pixel count, n1, indicates the total number of colors within 148% the cubic volume which the node represents. This includes n1 - n2 149% pixels whose colors should be defined by nodes at a lower level in the 150% tree. 151% 152% Assignment generates the output image from the pruned tree. The output 153% image consists of two parts: (1) A color map, which is an array of 154% color descriptions (RGB triples) for each color present in the output 155% image; (2) A pixel array, which represents each pixel as an index 156% into the color map array. 157% 158% First, the assignment phase makes one pass over the pruned color 159% description tree to establish the image's color map. For each node 160% with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean 161% color of all pixels that classify no lower than this node. Each of 162% these colors becomes an entry in the color map. 163% 164% Finally, the assignment phase reclassifies each pixel in the pruned 165% tree to identify the deepest node containing the pixel's color. The 166% pixel's value in the pixel array becomes the index of this node's mean 167% color in the color map. 168% 169% This method is based on a similar algorithm written by Paul Raveling. 170% 171*/ 172 173/* 174 Include declarations. 175*/ 176#include "MagickCore/studio.h" 177#include "MagickCore/attribute.h" 178#include "MagickCore/cache-view.h" 179#include "MagickCore/color.h" 180#include "MagickCore/color-private.h" 181#include "MagickCore/colormap.h" 182#include "MagickCore/colorspace.h" 183#include "MagickCore/colorspace-private.h" 184#include "MagickCore/enhance.h" 185#include "MagickCore/exception.h" 186#include "MagickCore/exception-private.h" 187#include "MagickCore/histogram.h" 188#include "MagickCore/image.h" 189#include "MagickCore/image-private.h" 190#include "MagickCore/list.h" 191#include "MagickCore/memory_.h" 192#include "MagickCore/monitor.h" 193#include "MagickCore/monitor-private.h" 194#include "MagickCore/option.h" 195#include "MagickCore/pixel-accessor.h" 196#include "MagickCore/pixel-private.h" 197#include "MagickCore/quantize.h" 198#include "MagickCore/quantum.h" 199#include "MagickCore/quantum-private.h" 200#include "MagickCore/resource_.h" 201#include "MagickCore/string_.h" 202#include "MagickCore/thread-private.h" 203 204/* 205 Define declarations. 206*/ 207#if !defined(__APPLE__) && !defined(TARGET_OS_IPHONE) 208#define CacheShift 2 209#else 210#define CacheShift 3 211#endif 212#define ErrorQueueLength 16 213#define MaxNodes 266817 214#define MaxTreeDepth 8 215#define NodesInAList 1920 216 217/* 218 Typdef declarations. 219*/ 220typedef struct _RealPixelInfo 221{ 222 double 223 red, 224 green, 225 blue, 226 alpha; 227} RealPixelInfo; 228 229typedef struct _NodeInfo 230{ 231 struct _NodeInfo 232 *parent, 233 *child[16]; 234 235 MagickSizeType 236 number_unique; 237 238 RealPixelInfo 239 total_color; 240 241 double 242 quantize_error; 243 244 size_t 245 color_number, 246 id, 247 level; 248} NodeInfo; 249 250typedef struct _Nodes 251{ 252 NodeInfo 253 *nodes; 254 255 struct _Nodes 256 *next; 257} Nodes; 258 259typedef struct _CubeInfo 260{ 261 NodeInfo 262 *root; 263 264 size_t 265 colors, 266 maximum_colors; 267 268 ssize_t 269 transparent_index; 270 271 MagickSizeType 272 transparent_pixels; 273 274 RealPixelInfo 275 target; 276 277 double 278 distance, 279 pruning_threshold, 280 next_threshold; 281 282 size_t 283 nodes, 284 free_nodes, 285 color_number; 286 287 NodeInfo 288 *next_node; 289 290 Nodes 291 *node_queue; 292 293 MemoryInfo 294 *memory_info; 295 296 ssize_t 297 *cache; 298 299 RealPixelInfo 300 error[ErrorQueueLength]; 301 302 double 303 weights[ErrorQueueLength]; 304 305 QuantizeInfo 306 *quantize_info; 307 308 MagickBooleanType 309 associate_alpha; 310 311 ssize_t 312 x, 313 y; 314 315 size_t 316 depth; 317 318 MagickOffsetType 319 offset; 320 321 MagickSizeType 322 span; 323} CubeInfo; 324 325/* 326 Method prototypes. 327*/ 328static CubeInfo 329 *GetCubeInfo(const QuantizeInfo *,const size_t,const size_t); 330 331static NodeInfo 332 *GetNodeInfo(CubeInfo *,const size_t,const size_t,NodeInfo *); 333 334static MagickBooleanType 335 AssignImageColors(Image *,CubeInfo *,ExceptionInfo *), 336 ClassifyImageColors(CubeInfo *,const Image *,ExceptionInfo *), 337 DitherImage(Image *,CubeInfo *,ExceptionInfo *), 338 SetGrayscaleImage(Image *,ExceptionInfo *); 339 340static size_t 341 DefineImageColormap(Image *,CubeInfo *,NodeInfo *); 342 343static void 344 ClosestColor(const Image *,CubeInfo *,const NodeInfo *), 345 DestroyCubeInfo(CubeInfo *), 346 PruneLevel(const Image *,CubeInfo *,const NodeInfo *), 347 PruneToCubeDepth(const Image *,CubeInfo *,const NodeInfo *), 348 ReduceImageColors(const Image *,CubeInfo *); 349 350/* 351%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 352% % 353% % 354% % 355% A c q u i r e Q u a n t i z e I n f o % 356% % 357% % 358% % 359%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 360% 361% AcquireQuantizeInfo() allocates the QuantizeInfo structure. 362% 363% The format of the AcquireQuantizeInfo method is: 364% 365% QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info) 366% 367% A description of each parameter follows: 368% 369% o image_info: the image info. 370% 371*/ 372MagickExport QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info) 373{ 374 QuantizeInfo 375 *quantize_info; 376 377 quantize_info=(QuantizeInfo *) AcquireMagickMemory(sizeof(*quantize_info)); 378 if (quantize_info == (QuantizeInfo *) NULL) 379 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); 380 GetQuantizeInfo(quantize_info); 381 if (image_info != (ImageInfo *) NULL) 382 { 383 const char 384 *option; 385 386 quantize_info->dither_method=image_info->dither == MagickFalse ? 387 NoDitherMethod : RiemersmaDitherMethod; 388 option=GetImageOption(image_info,"dither"); 389 if (option != (const char *) NULL) 390 quantize_info->dither_method=(DitherMethod) ParseCommandOption( 391 MagickDitherOptions,MagickFalse,option); 392 quantize_info->measure_error=image_info->verbose; 393 } 394 return(quantize_info); 395} 396 397/* 398%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 399% % 400% % 401% % 402+ A s s i g n I m a g e C o l o r s % 403% % 404% % 405% % 406%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 407% 408% AssignImageColors() generates the output image from the pruned tree. The 409% output image consists of two parts: (1) A color map, which is an array 410% of color descriptions (RGB triples) for each color present in the 411% output image; (2) A pixel array, which represents each pixel as an 412% index into the color map array. 413% 414% First, the assignment phase makes one pass over the pruned color 415% description tree to establish the image's color map. For each node 416% with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean 417% color of all pixels that classify no lower than this node. Each of 418% these colors becomes an entry in the color map. 419% 420% Finally, the assignment phase reclassifies each pixel in the pruned 421% tree to identify the deepest node containing the pixel's color. The 422% pixel's value in the pixel array becomes the index of this node's mean 423% color in the color map. 424% 425% The format of the AssignImageColors() method is: 426% 427% MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info) 428% 429% A description of each parameter follows. 430% 431% o image: the image. 432% 433% o cube_info: A pointer to the Cube structure. 434% 435*/ 436 437static inline void AssociateAlphaPixel(const Image *image, 438 const CubeInfo *cube_info,const Quantum *pixel,RealPixelInfo *alpha_pixel) 439{ 440 double 441 alpha; 442 443 if ((cube_info->associate_alpha == MagickFalse) || 444 (GetPixelAlpha(image,pixel)== OpaqueAlpha)) 445 { 446 alpha_pixel->red=(double) GetPixelRed(image,pixel); 447 alpha_pixel->green=(double) GetPixelGreen(image,pixel); 448 alpha_pixel->blue=(double) GetPixelBlue(image,pixel); 449 alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel); 450 return; 451 } 452 alpha=(double) (QuantumScale*GetPixelAlpha(image,pixel)); 453 alpha_pixel->red=alpha*GetPixelRed(image,pixel); 454 alpha_pixel->green=alpha*GetPixelGreen(image,pixel); 455 alpha_pixel->blue=alpha*GetPixelBlue(image,pixel); 456 alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel); 457} 458 459static inline void AssociateAlphaPixelInfo(const CubeInfo *cube_info, 460 const PixelInfo *pixel,RealPixelInfo *alpha_pixel) 461{ 462 double 463 alpha; 464 465 if ((cube_info->associate_alpha == MagickFalse) || 466 (pixel->alpha == OpaqueAlpha)) 467 { 468 alpha_pixel->red=(double) pixel->red; 469 alpha_pixel->green=(double) pixel->green; 470 alpha_pixel->blue=(double) pixel->blue; 471 alpha_pixel->alpha=(double) pixel->alpha; 472 return; 473 } 474 alpha=(double) (QuantumScale*pixel->alpha); 475 alpha_pixel->red=alpha*pixel->red; 476 alpha_pixel->green=alpha*pixel->green; 477 alpha_pixel->blue=alpha*pixel->blue; 478 alpha_pixel->alpha=(double) pixel->alpha; 479} 480 481static inline 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 != UndefinedPixelTrait ? 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)*GetPixelChannels(image)*image->columns; 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 MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info, 1930 ExceptionInfo *exception) 1931{ 1932 CacheView 1933 *image_view; 1934 1935 MagickBooleanType 1936 status; 1937 1938 register ssize_t 1939 i; 1940 1941 size_t 1942 depth; 1943 1944 if (cube_info->quantize_info->dither_method != RiemersmaDitherMethod) 1945 return(FloydSteinbergDither(image,cube_info,exception)); 1946 /* 1947 Distribute quantization error along a Hilbert curve. 1948 */ 1949 (void) ResetMagickMemory(cube_info->error,0,ErrorQueueLength* 1950 sizeof(*cube_info->error)); 1951 cube_info->x=0; 1952 cube_info->y=0; 1953 i=MagickMax((ssize_t) image->columns,(ssize_t) image->rows); 1954 for (depth=1; i != 0; depth++) 1955 i>>=1; 1956 if ((ssize_t) (1L << depth) < MagickMax((ssize_t) image->columns,(ssize_t) image->rows)) 1957 depth++; 1958 cube_info->offset=0; 1959 cube_info->span=(MagickSizeType) image->columns*image->rows; 1960 image_view=AcquireAuthenticCacheView(image,exception); 1961 if (depth > 1) 1962 Riemersma(image,image_view,cube_info,depth-1,NorthGravity,exception); 1963 status=RiemersmaDither(image,image_view,cube_info,ForgetGravity,exception); 1964 image_view=DestroyCacheView(image_view); 1965 return(status); 1966} 1967 1968/* 1969%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1970% % 1971% % 1972% % 1973+ G e t C u b e I n f o % 1974% % 1975% % 1976% % 1977%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1978% 1979% GetCubeInfo() initialize the Cube data structure. 1980% 1981% The format of the GetCubeInfo method is: 1982% 1983% CubeInfo GetCubeInfo(const QuantizeInfo *quantize_info, 1984% const size_t depth,const size_t maximum_colors) 1985% 1986% A description of each parameter follows. 1987% 1988% o quantize_info: Specifies a pointer to an QuantizeInfo structure. 1989% 1990% o depth: Normally, this integer value is zero or one. A zero or 1991% one tells Quantize to choose a optimal tree depth of Log4(number_colors). 1992% A tree of this depth generally allows the best representation of the 1993% reference image with the least amount of memory and the fastest 1994% computational speed. In some cases, such as an image with low color 1995% dispersion (a few number of colors), a value other than 1996% Log4(number_colors) is required. To expand the color tree completely, 1997% use a value of 8. 1998% 1999% o maximum_colors: maximum colors. 2000% 2001*/ 2002static CubeInfo *GetCubeInfo(const QuantizeInfo *quantize_info, 2003 const size_t depth,const size_t maximum_colors) 2004{ 2005 CubeInfo 2006 *cube_info; 2007 2008 double 2009 sum, 2010 weight; 2011 2012 register ssize_t 2013 i; 2014 2015 size_t 2016 length; 2017 2018 /* 2019 Initialize tree to describe color cube_info. 2020 */ 2021 cube_info=(CubeInfo *) AcquireMagickMemory(sizeof(*cube_info)); 2022 if (cube_info == (CubeInfo *) NULL) 2023 return((CubeInfo *) NULL); 2024 (void) ResetMagickMemory(cube_info,0,sizeof(*cube_info)); 2025 cube_info->depth=depth; 2026 if (cube_info->depth > MaxTreeDepth) 2027 cube_info->depth=MaxTreeDepth; 2028 if (cube_info->depth < 2) 2029 cube_info->depth=2; 2030 cube_info->maximum_colors=maximum_colors; 2031 /* 2032 Initialize root node. 2033 */ 2034 cube_info->root=GetNodeInfo(cube_info,0,0,(NodeInfo *) NULL); 2035 if (cube_info->root == (NodeInfo *) NULL) 2036 return((CubeInfo *) NULL); 2037 cube_info->root->parent=cube_info->root; 2038 cube_info->quantize_info=CloneQuantizeInfo(quantize_info); 2039 if (cube_info->quantize_info->dither_method == NoDitherMethod) 2040 return(cube_info); 2041 /* 2042 Initialize dither resources. 2043 */ 2044 length=(size_t) (1UL << (4*(8-CacheShift))); 2045 cube_info->memory_info=AcquireVirtualMemory(length,sizeof(*cube_info->cache)); 2046 if (cube_info->memory_info == (MemoryInfo *) NULL) 2047 return((CubeInfo *) NULL); 2048 cube_info->cache=(ssize_t *) GetVirtualMemoryBlob(cube_info->memory_info); 2049 /* 2050 Initialize color cache. 2051 */ 2052 for (i=0; i < (ssize_t) length; i++) 2053 cube_info->cache[i]=(-1); 2054 /* 2055 Distribute weights along a curve of exponential decay. 2056 */ 2057 weight=1.0; 2058 for (i=0; i < ErrorQueueLength; i++) 2059 { 2060 cube_info->weights[ErrorQueueLength-i-1]=PerceptibleReciprocal(weight); 2061 weight*=exp(log(((double) QuantumRange+1.0))/(ErrorQueueLength-1.0)); 2062 } 2063 /* 2064 Normalize the weighting factors. 2065 */ 2066 weight=0.0; 2067 for (i=0; i < ErrorQueueLength; i++) 2068 weight+=cube_info->weights[i]; 2069 sum=0.0; 2070 for (i=0; i < ErrorQueueLength; i++) 2071 { 2072 cube_info->weights[i]/=weight; 2073 sum+=cube_info->weights[i]; 2074 } 2075 cube_info->weights[0]+=1.0-sum; 2076 return(cube_info); 2077} 2078 2079/* 2080%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2081% % 2082% % 2083% % 2084+ G e t N o d e I n f o % 2085% % 2086% % 2087% % 2088%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2089% 2090% GetNodeInfo() allocates memory for a new node in the color cube tree and 2091% presets all fields to zero. 2092% 2093% The format of the GetNodeInfo method is: 2094% 2095% NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id, 2096% const size_t level,NodeInfo *parent) 2097% 2098% A description of each parameter follows. 2099% 2100% o node: The GetNodeInfo method returns a pointer to a queue of nodes. 2101% 2102% o id: Specifies the child number of the node. 2103% 2104% o level: Specifies the level in the storage_class the node resides. 2105% 2106*/ 2107static NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id, 2108 const size_t level,NodeInfo *parent) 2109{ 2110 NodeInfo 2111 *node_info; 2112 2113 if (cube_info->free_nodes == 0) 2114 { 2115 Nodes 2116 *nodes; 2117 2118 /* 2119 Allocate a new queue of nodes. 2120 */ 2121 nodes=(Nodes *) AcquireMagickMemory(sizeof(*nodes)); 2122 if (nodes == (Nodes *) NULL) 2123 return((NodeInfo *) NULL); 2124 nodes->nodes=(NodeInfo *) AcquireQuantumMemory(NodesInAList, 2125 sizeof(*nodes->nodes)); 2126 if (nodes->nodes == (NodeInfo *) NULL) 2127 return((NodeInfo *) NULL); 2128 nodes->next=cube_info->node_queue; 2129 cube_info->node_queue=nodes; 2130 cube_info->next_node=nodes->nodes; 2131 cube_info->free_nodes=NodesInAList; 2132 } 2133 cube_info->nodes++; 2134 cube_info->free_nodes--; 2135 node_info=cube_info->next_node++; 2136 (void) ResetMagickMemory(node_info,0,sizeof(*node_info)); 2137 node_info->parent=parent; 2138 node_info->id=id; 2139 node_info->level=level; 2140 return(node_info); 2141} 2142 2143/* 2144%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2145% % 2146% % 2147% % 2148% G e t I m a g e Q u a n t i z e E r r o r % 2149% % 2150% % 2151% % 2152%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2153% 2154% GetImageQuantizeError() measures the difference between the original 2155% and quantized images. This difference is the total quantization error. 2156% The error is computed by summing over all pixels in an image the distance 2157% squared in RGB space between each reference pixel value and its quantized 2158% value. These values are computed: 2159% 2160% o mean_error_per_pixel: This value is the mean error for any single 2161% pixel in the image. 2162% 2163% o normalized_mean_square_error: This value is the normalized mean 2164% quantization error for any single pixel in the image. This distance 2165% measure is normalized to a range between 0 and 1. It is independent 2166% of the range of red, green, and blue values in the image. 2167% 2168% o normalized_maximum_square_error: Thsi value is the normalized 2169% maximum quantization error for any single pixel in the image. This 2170% distance measure is normalized to a range between 0 and 1. It is 2171% independent of the range of red, green, and blue values in your image. 2172% 2173% The format of the GetImageQuantizeError method is: 2174% 2175% MagickBooleanType GetImageQuantizeError(Image *image, 2176% ExceptionInfo *exception) 2177% 2178% A description of each parameter follows. 2179% 2180% o image: the image. 2181% 2182% o exception: return any errors or warnings in this structure. 2183% 2184*/ 2185MagickExport MagickBooleanType GetImageQuantizeError(Image *image, 2186 ExceptionInfo *exception) 2187{ 2188 CacheView 2189 *image_view; 2190 2191 double 2192 alpha, 2193 area, 2194 beta, 2195 distance, 2196 maximum_error, 2197 mean_error, 2198 mean_error_per_pixel; 2199 2200 size_t 2201 index; 2202 2203 ssize_t 2204 y; 2205 2206 assert(image != (Image *) NULL); 2207 assert(image->signature == MagickSignature); 2208 if (image->debug != MagickFalse) 2209 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 2210 image->total_colors=GetNumberColors(image,(FILE *) NULL,exception); 2211 (void) ResetMagickMemory(&image->error,0,sizeof(image->error)); 2212 if (image->storage_class == DirectClass) 2213 return(MagickTrue); 2214 alpha=1.0; 2215 beta=1.0; 2216 area=3.0*image->columns*image->rows; 2217 maximum_error=0.0; 2218 mean_error_per_pixel=0.0; 2219 mean_error=0.0; 2220 image_view=AcquireVirtualCacheView(image,exception); 2221 for (y=0; y < (ssize_t) image->rows; y++) 2222 { 2223 register const Quantum 2224 *restrict p; 2225 2226 register ssize_t 2227 x; 2228 2229 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception); 2230 if (p == (const Quantum *) NULL) 2231 break; 2232 for (x=0; x < (ssize_t) image->columns; x++) 2233 { 2234 index=1UL*GetPixelIndex(image,p); 2235 if (image->alpha_trait != UndefinedPixelTrait) 2236 { 2237 alpha=(double) (QuantumScale*GetPixelAlpha(image,p)); 2238 beta=(double) (QuantumScale*image->colormap[index].alpha); 2239 } 2240 distance=fabs((double) (alpha*GetPixelRed(image,p)-beta* 2241 image->colormap[index].red)); 2242 mean_error_per_pixel+=distance; 2243 mean_error+=distance*distance; 2244 if (distance > maximum_error) 2245 maximum_error=distance; 2246 distance=fabs((double) (alpha*GetPixelGreen(image,p)-beta* 2247 image->colormap[index].green)); 2248 mean_error_per_pixel+=distance; 2249 mean_error+=distance*distance; 2250 if (distance > maximum_error) 2251 maximum_error=distance; 2252 distance=fabs((double) (alpha*GetPixelBlue(image,p)-beta* 2253 image->colormap[index].blue)); 2254 mean_error_per_pixel+=distance; 2255 mean_error+=distance*distance; 2256 if (distance > maximum_error) 2257 maximum_error=distance; 2258 p+=GetPixelChannels(image); 2259 } 2260 } 2261 image_view=DestroyCacheView(image_view); 2262 image->error.mean_error_per_pixel=(double) mean_error_per_pixel/area; 2263 image->error.normalized_mean_error=(double) QuantumScale*QuantumScale* 2264 mean_error/area; 2265 image->error.normalized_maximum_error=(double) QuantumScale*maximum_error; 2266 return(MagickTrue); 2267} 2268 2269/* 2270%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2271% % 2272% % 2273% % 2274% G e t Q u a n t i z e I n f o % 2275% % 2276% % 2277% % 2278%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2279% 2280% GetQuantizeInfo() initializes the QuantizeInfo structure. 2281% 2282% The format of the GetQuantizeInfo method is: 2283% 2284% GetQuantizeInfo(QuantizeInfo *quantize_info) 2285% 2286% A description of each parameter follows: 2287% 2288% o quantize_info: Specifies a pointer to a QuantizeInfo structure. 2289% 2290*/ 2291MagickExport void GetQuantizeInfo(QuantizeInfo *quantize_info) 2292{ 2293 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); 2294 assert(quantize_info != (QuantizeInfo *) NULL); 2295 (void) ResetMagickMemory(quantize_info,0,sizeof(*quantize_info)); 2296 quantize_info->number_colors=256; 2297 quantize_info->dither_method=RiemersmaDitherMethod; 2298 quantize_info->colorspace=UndefinedColorspace; 2299 quantize_info->measure_error=MagickFalse; 2300 quantize_info->signature=MagickSignature; 2301} 2302 2303/* 2304%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2305% % 2306% % 2307% % 2308% P o s t e r i z e I m a g e % 2309% % 2310% % 2311% % 2312%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2313% 2314% PosterizeImage() reduces the image to a limited number of colors for a 2315% "poster" effect. 2316% 2317% The format of the PosterizeImage method is: 2318% 2319% MagickBooleanType PosterizeImage(Image *image,const size_t levels, 2320% const DitherMethod dither_method,ExceptionInfo *exception) 2321% 2322% A description of each parameter follows: 2323% 2324% o image: Specifies a pointer to an Image structure. 2325% 2326% o levels: Number of color levels allowed in each channel. Very low values 2327% (2, 3, or 4) have the most visible effect. 2328% 2329% o dither_method: choose from UndefinedDitherMethod, NoDitherMethod, 2330% RiemersmaDitherMethod, FloydSteinbergDitherMethod. 2331% 2332% o exception: return any errors or warnings in this structure. 2333% 2334*/ 2335 2336static inline double MagickRound(double x) 2337{ 2338 /* 2339 Round the fraction to nearest integer. 2340 */ 2341 if ((x-floor(x)) < (ceil(x)-x)) 2342 return(floor(x)); 2343 return(ceil(x)); 2344} 2345 2346MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels, 2347 const DitherMethod dither_method,ExceptionInfo *exception) 2348{ 2349#define PosterizeImageTag "Posterize/Image" 2350#define PosterizePixel(pixel) (Quantum) (QuantumRange*(MagickRound( \ 2351 QuantumScale*pixel*(levels-1)))/MagickMax((ssize_t) levels-1,1)) 2352 2353 CacheView 2354 *image_view; 2355 2356 MagickBooleanType 2357 status; 2358 2359 MagickOffsetType 2360 progress; 2361 2362 QuantizeInfo 2363 *quantize_info; 2364 2365 register ssize_t 2366 i; 2367 2368 ssize_t 2369 y; 2370 2371 assert(image != (Image *) NULL); 2372 assert(image->signature == MagickSignature); 2373 if (image->debug != MagickFalse) 2374 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 2375 if (image->storage_class == PseudoClass) 2376#if defined(MAGICKCORE_OPENMP_SUPPORT) 2377 #pragma omp parallel for schedule(static,4) shared(progress,status) \ 2378 magick_threads(image,image,1,1) 2379#endif 2380 for (i=0; i < (ssize_t) image->colors; i++) 2381 { 2382 /* 2383 Posterize colormap. 2384 */ 2385 if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0) 2386 image->colormap[i].red=(double) 2387 PosterizePixel(image->colormap[i].red); 2388 if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0) 2389 image->colormap[i].green=(double) 2390 PosterizePixel(image->colormap[i].green); 2391 if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0) 2392 image->colormap[i].blue=(double) 2393 PosterizePixel(image->colormap[i].blue); 2394 if ((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0) 2395 image->colormap[i].alpha=(double) 2396 PosterizePixel(image->colormap[i].alpha); 2397 } 2398 /* 2399 Posterize image. 2400 */ 2401 status=MagickTrue; 2402 progress=0; 2403 image_view=AcquireAuthenticCacheView(image,exception); 2404#if defined(MAGICKCORE_OPENMP_SUPPORT) 2405 #pragma omp parallel for schedule(static,4) shared(progress,status) \ 2406 magick_threads(image,image,image->rows,1) 2407#endif 2408 for (y=0; y < (ssize_t) image->rows; y++) 2409 { 2410 register Quantum 2411 *restrict q; 2412 2413 register ssize_t 2414 x; 2415 2416 if (status == MagickFalse) 2417 continue; 2418 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception); 2419 if (q == (Quantum *) NULL) 2420 { 2421 status=MagickFalse; 2422 continue; 2423 } 2424 for (x=0; x < (ssize_t) image->columns; x++) 2425 { 2426 if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0) 2427 SetPixelRed(image,PosterizePixel(GetPixelRed(image,q)),q); 2428 if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0) 2429 SetPixelGreen(image,PosterizePixel(GetPixelGreen(image,q)),q); 2430 if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0) 2431 SetPixelBlue(image,PosterizePixel(GetPixelBlue(image,q)),q); 2432 if (((GetPixelBlackTraits(image) & UpdatePixelTrait) != 0) && 2433 (image->colorspace == CMYKColorspace)) 2434 SetPixelBlack(image,PosterizePixel(GetPixelBlack(image,q)),q); 2435 if (((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0) && 2436 (image->alpha_trait != UndefinedPixelTrait)) 2437 SetPixelAlpha(image,PosterizePixel(GetPixelAlpha(image,q)),q); 2438 q+=GetPixelChannels(image); 2439 } 2440 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) 2441 status=MagickFalse; 2442 if (image->progress_monitor != (MagickProgressMonitor) NULL) 2443 { 2444 MagickBooleanType 2445 proceed; 2446 2447#if defined(MAGICKCORE_OPENMP_SUPPORT) 2448 #pragma omp critical (MagickCore_PosterizeImage) 2449#endif 2450 proceed=SetImageProgress(image,PosterizeImageTag,progress++, 2451 image->rows); 2452 if (proceed == MagickFalse) 2453 status=MagickFalse; 2454 } 2455 } 2456 image_view=DestroyCacheView(image_view); 2457 quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL); 2458 quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels* 2459 levels,MaxColormapSize+1); 2460 quantize_info->dither_method=dither_method; 2461 quantize_info->tree_depth=MaxTreeDepth; 2462 status=QuantizeImage(quantize_info,image,exception); 2463 quantize_info=DestroyQuantizeInfo(quantize_info); 2464 return(status); 2465} 2466 2467/* 2468%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2469% % 2470% % 2471% % 2472+ P r u n e C h i l d % 2473% % 2474% % 2475% % 2476%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2477% 2478% PruneChild() deletes the given node and merges its statistics into its 2479% parent. 2480% 2481% The format of the PruneSubtree method is: 2482% 2483% PruneChild(const Image *image,CubeInfo *cube_info, 2484% const NodeInfo *node_info) 2485% 2486% A description of each parameter follows. 2487% 2488% o image: the image. 2489% 2490% o cube_info: A pointer to the Cube structure. 2491% 2492% o node_info: pointer to node in color cube tree that is to be pruned. 2493% 2494*/ 2495static void PruneChild(const Image *image,CubeInfo *cube_info, 2496 const NodeInfo *node_info) 2497{ 2498 NodeInfo 2499 *parent; 2500 2501 register ssize_t 2502 i; 2503 2504 size_t 2505 number_children; 2506 2507 /* 2508 Traverse any children. 2509 */ 2510 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; 2511 for (i=0; i < (ssize_t) number_children; i++) 2512 if (node_info->child[i] != (NodeInfo *) NULL) 2513 PruneChild(image,cube_info,node_info->child[i]); 2514 /* 2515 Merge color statistics into parent. 2516 */ 2517 parent=node_info->parent; 2518 parent->number_unique+=node_info->number_unique; 2519 parent->total_color.red+=node_info->total_color.red; 2520 parent->total_color.green+=node_info->total_color.green; 2521 parent->total_color.blue+=node_info->total_color.blue; 2522 parent->total_color.alpha+=node_info->total_color.alpha; 2523 parent->child[node_info->id]=(NodeInfo *) NULL; 2524 cube_info->nodes--; 2525} 2526 2527/* 2528%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2529% % 2530% % 2531% % 2532+ P r u n e L e v e l % 2533% % 2534% % 2535% % 2536%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2537% 2538% PruneLevel() deletes all nodes at the bottom level of the color tree merging 2539% their color statistics into their parent node. 2540% 2541% The format of the PruneLevel method is: 2542% 2543% PruneLevel(const Image *image,CubeInfo *cube_info, 2544% const NodeInfo *node_info) 2545% 2546% A description of each parameter follows. 2547% 2548% o image: the image. 2549% 2550% o cube_info: A pointer to the Cube structure. 2551% 2552% o node_info: pointer to node in color cube tree that is to be pruned. 2553% 2554*/ 2555static void PruneLevel(const Image *image,CubeInfo *cube_info, 2556 const NodeInfo *node_info) 2557{ 2558 register ssize_t 2559 i; 2560 2561 size_t 2562 number_children; 2563 2564 /* 2565 Traverse any children. 2566 */ 2567 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; 2568 for (i=0; i < (ssize_t) number_children; i++) 2569 if (node_info->child[i] != (NodeInfo *) NULL) 2570 PruneLevel(image,cube_info,node_info->child[i]); 2571 if (node_info->level == cube_info->depth) 2572 PruneChild(image,cube_info,node_info); 2573} 2574 2575/* 2576%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2577% % 2578% % 2579% % 2580+ P r u n e T o C u b e D e p t h % 2581% % 2582% % 2583% % 2584%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2585% 2586% PruneToCubeDepth() deletes any nodes at a depth greater than 2587% cube_info->depth while merging their color statistics into their parent 2588% node. 2589% 2590% The format of the PruneToCubeDepth method is: 2591% 2592% PruneToCubeDepth(const Image *image,CubeInfo *cube_info, 2593% const NodeInfo *node_info) 2594% 2595% A description of each parameter follows. 2596% 2597% o cube_info: A pointer to the Cube structure. 2598% 2599% o node_info: pointer to node in color cube tree that is to be pruned. 2600% 2601*/ 2602static void PruneToCubeDepth(const Image *image,CubeInfo *cube_info, 2603 const NodeInfo *node_info) 2604{ 2605 register ssize_t 2606 i; 2607 2608 size_t 2609 number_children; 2610 2611 /* 2612 Traverse any children. 2613 */ 2614 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; 2615 for (i=0; i < (ssize_t) number_children; i++) 2616 if (node_info->child[i] != (NodeInfo *) NULL) 2617 PruneToCubeDepth(image,cube_info,node_info->child[i]); 2618 if (node_info->level > cube_info->depth) 2619 PruneChild(image,cube_info,node_info); 2620} 2621 2622/* 2623%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2624% % 2625% % 2626% % 2627% Q u a n t i z e I m a g e % 2628% % 2629% % 2630% % 2631%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2632% 2633% QuantizeImage() analyzes the colors within a reference image and chooses a 2634% fixed number of colors to represent the image. The goal of the algorithm 2635% is to minimize the color difference between the input and output image while 2636% minimizing the processing time. 2637% 2638% The format of the QuantizeImage method is: 2639% 2640% MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info, 2641% Image *image,ExceptionInfo *exception) 2642% 2643% A description of each parameter follows: 2644% 2645% o quantize_info: Specifies a pointer to an QuantizeInfo structure. 2646% 2647% o image: the image. 2648% 2649% o exception: return any errors or warnings in this structure. 2650% 2651*/ 2652 2653static MagickBooleanType DirectToColormapImage(Image *image, 2654 ExceptionInfo *exception) 2655{ 2656 CacheView 2657 *image_view; 2658 2659 MagickBooleanType 2660 status; 2661 2662 register ssize_t 2663 i; 2664 2665 size_t 2666 number_colors; 2667 2668 ssize_t 2669 y; 2670 2671 status=MagickTrue; 2672 number_colors=(size_t) (image->columns*image->rows); 2673 if (AcquireImageColormap(image,number_colors,exception) == MagickFalse) 2674 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 2675 image->filename); 2676 if (image->colors != number_colors) 2677 return(MagickFalse); 2678 i=0; 2679 image_view=AcquireAuthenticCacheView(image,exception); 2680 for (y=0; y < (ssize_t) image->rows; y++) 2681 { 2682 MagickBooleanType 2683 proceed; 2684 2685 register Quantum 2686 *restrict q; 2687 2688 register ssize_t 2689 x; 2690 2691 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception); 2692 if (q == (Quantum *) NULL) 2693 break; 2694 for (x=0; x < (ssize_t) image->columns; x++) 2695 { 2696 image->colormap[i].red=(double) GetPixelRed(image,q); 2697 image->colormap[i].green=(double) GetPixelGreen(image,q); 2698 image->colormap[i].blue=(double) GetPixelBlue(image,q); 2699 image->colormap[i].alpha=(double) GetPixelAlpha(image,q); 2700 SetPixelIndex(image,(Quantum) i,q); 2701 i++; 2702 q+=GetPixelChannels(image); 2703 } 2704 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) 2705 break; 2706 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y, 2707 image->rows); 2708 if (proceed == MagickFalse) 2709 status=MagickFalse; 2710 } 2711 image_view=DestroyCacheView(image_view); 2712 return(status); 2713} 2714 2715MagickExport MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info, 2716 Image *image,ExceptionInfo *exception) 2717{ 2718 CubeInfo 2719 *cube_info; 2720 2721 MagickBooleanType 2722 status; 2723 2724 size_t 2725 depth, 2726 maximum_colors; 2727 2728 assert(quantize_info != (const QuantizeInfo *) NULL); 2729 assert(quantize_info->signature == MagickSignature); 2730 assert(image != (Image *) NULL); 2731 assert(image->signature == MagickSignature); 2732 if (image->debug != MagickFalse) 2733 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 2734 maximum_colors=quantize_info->number_colors; 2735 if (maximum_colors == 0) 2736 maximum_colors=MaxColormapSize; 2737 if (maximum_colors > MaxColormapSize) 2738 maximum_colors=MaxColormapSize; 2739 if (image->alpha_trait == UndefinedPixelTrait) 2740 { 2741 if ((image->columns*image->rows) <= maximum_colors) 2742 (void) DirectToColormapImage(image,exception); 2743 if (IsImageGray(image,exception) != MagickFalse) 2744 (void) SetGrayscaleImage(image,exception); 2745 } 2746 if ((image->storage_class == PseudoClass) && 2747 (image->colors <= maximum_colors)) 2748 { 2749 if ((quantize_info->colorspace != UndefinedColorspace) && 2750 (quantize_info->colorspace != CMYKColorspace)) 2751 (void) TransformImageColorspace(image,quantize_info->colorspace, 2752 exception); 2753 return(MagickTrue); 2754 } 2755 depth=quantize_info->tree_depth; 2756 if (depth == 0) 2757 { 2758 size_t 2759 colors; 2760 2761 /* 2762 Depth of color tree is: Log4(colormap size)+2. 2763 */ 2764 colors=maximum_colors; 2765 for (depth=1; colors != 0; depth++) 2766 colors>>=2; 2767 if ((quantize_info->dither_method != NoDitherMethod) && (depth > 2)) 2768 depth--; 2769 if ((image->alpha_trait != UndefinedPixelTrait) && (depth > 5)) 2770 depth--; 2771 if (IsImageGray(image,exception) != MagickFalse) 2772 depth=MaxTreeDepth; 2773 } 2774 /* 2775 Initialize color cube. 2776 */ 2777 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors); 2778 if (cube_info == (CubeInfo *) NULL) 2779 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 2780 image->filename); 2781 status=ClassifyImageColors(cube_info,image,exception); 2782 if (status != MagickFalse) 2783 { 2784 /* 2785 Reduce the number of colors in the image. 2786 */ 2787 ReduceImageColors(image,cube_info); 2788 status=AssignImageColors(image,cube_info,exception); 2789 } 2790 DestroyCubeInfo(cube_info); 2791 return(status); 2792} 2793 2794/* 2795%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2796% % 2797% % 2798% % 2799% Q u a n t i z e I m a g e s % 2800% % 2801% % 2802% % 2803%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2804% 2805% QuantizeImages() analyzes the colors within a set of reference images and 2806% chooses a fixed number of colors to represent the set. The goal of the 2807% algorithm is to minimize the color difference between the input and output 2808% images while minimizing the processing time. 2809% 2810% The format of the QuantizeImages method is: 2811% 2812% MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info, 2813% Image *images,ExceptionInfo *exception) 2814% 2815% A description of each parameter follows: 2816% 2817% o quantize_info: Specifies a pointer to an QuantizeInfo structure. 2818% 2819% o images: Specifies a pointer to a list of Image structures. 2820% 2821% o exception: return any errors or warnings in this structure. 2822% 2823*/ 2824MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info, 2825 Image *images,ExceptionInfo *exception) 2826{ 2827 CubeInfo 2828 *cube_info; 2829 2830 Image 2831 *image; 2832 2833 MagickBooleanType 2834 proceed, 2835 status; 2836 2837 MagickProgressMonitor 2838 progress_monitor; 2839 2840 register ssize_t 2841 i; 2842 2843 size_t 2844 depth, 2845 maximum_colors, 2846 number_images; 2847 2848 assert(quantize_info != (const QuantizeInfo *) NULL); 2849 assert(quantize_info->signature == MagickSignature); 2850 assert(images != (Image *) NULL); 2851 assert(images->signature == MagickSignature); 2852 if (images->debug != MagickFalse) 2853 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename); 2854 if (GetNextImageInList(images) == (Image *) NULL) 2855 { 2856 /* 2857 Handle a single image with QuantizeImage. 2858 */ 2859 status=QuantizeImage(quantize_info,images,exception); 2860 return(status); 2861 } 2862 status=MagickFalse; 2863 maximum_colors=quantize_info->number_colors; 2864 if (maximum_colors == 0) 2865 maximum_colors=MaxColormapSize; 2866 if (maximum_colors > MaxColormapSize) 2867 maximum_colors=MaxColormapSize; 2868 depth=quantize_info->tree_depth; 2869 if (depth == 0) 2870 { 2871 size_t 2872 colors; 2873 2874 /* 2875 Depth of color tree is: Log4(colormap size)+2. 2876 */ 2877 colors=maximum_colors; 2878 for (depth=1; colors != 0; depth++) 2879 colors>>=2; 2880 if (quantize_info->dither_method != NoDitherMethod) 2881 depth--; 2882 } 2883 /* 2884 Initialize color cube. 2885 */ 2886 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors); 2887 if (cube_info == (CubeInfo *) NULL) 2888 { 2889 (void) ThrowMagickException(exception,GetMagickModule(), 2890 ResourceLimitError,"MemoryAllocationFailed","`%s'",images->filename); 2891 return(MagickFalse); 2892 } 2893 number_images=GetImageListLength(images); 2894 image=images; 2895 for (i=0; image != (Image *) NULL; i++) 2896 { 2897 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL, 2898 image->client_data); 2899 status=ClassifyImageColors(cube_info,image,exception); 2900 if (status == MagickFalse) 2901 break; 2902 (void) SetImageProgressMonitor(image,progress_monitor,image->client_data); 2903 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i, 2904 number_images); 2905 if (proceed == MagickFalse) 2906 break; 2907 image=GetNextImageInList(image); 2908 } 2909 if (status != MagickFalse) 2910 { 2911 /* 2912 Reduce the number of colors in an image sequence. 2913 */ 2914 ReduceImageColors(images,cube_info); 2915 image=images; 2916 for (i=0; image != (Image *) NULL; i++) 2917 { 2918 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) 2919 NULL,image->client_data); 2920 status=AssignImageColors(image,cube_info,exception); 2921 if (status == MagickFalse) 2922 break; 2923 (void) SetImageProgressMonitor(image,progress_monitor, 2924 image->client_data); 2925 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i, 2926 number_images); 2927 if (proceed == MagickFalse) 2928 break; 2929 image=GetNextImageInList(image); 2930 } 2931 } 2932 DestroyCubeInfo(cube_info); 2933 return(status); 2934} 2935 2936/* 2937%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2938% % 2939% % 2940% % 2941+ Q u a n t i z e E r r o r F l a t t e n % 2942% % 2943% % 2944% % 2945%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2946% 2947% QuantizeErrorFlatten() traverses the color cube and flattens the quantization 2948% error into a sorted 1D array. This accelerates the color reduction process. 2949% 2950% Contributed by Yoya. 2951% 2952% The format of the QuantizeImages method is: 2953% 2954% size_t QuantizeErrorFlatten(const Image *image,const CubeInfo *cube_info, 2955% const NodeInfo *node_info,const ssize_t offset, 2956% MagickRealType *quantize_error) 2957% 2958% A description of each parameter follows. 2959% 2960% o image: the image. 2961% 2962% o cube_info: A pointer to the Cube structure. 2963% 2964% o node_info: pointer to node in color cube tree that is current pointer. 2965% 2966% o offset: quantize error offset. 2967% 2968% o quantize_error: the quantization error vector. 2969% 2970*/ 2971static size_t QuantizeErrorFlatten(const Image *image,const CubeInfo *cube_info, 2972 const NodeInfo *node_info,const ssize_t offset,MagickRealType *quantize_error) 2973{ 2974 register ssize_t 2975 i; 2976 2977 size_t 2978 n, 2979 number_children; 2980 2981 if (offset >= (ssize_t) cube_info->nodes) 2982 return(0); 2983 quantize_error[offset]=node_info->quantize_error; 2984 n=1; 2985 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; 2986 for (i=0; i < (ssize_t) number_children ; i++) 2987 if (node_info->child[i] != (NodeInfo *) NULL) 2988 n+=QuantizeErrorFlatten(image,cube_info,node_info->child[i],offset+n, 2989 quantize_error); 2990 return(n); 2991} 2992 2993/* 2994%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2995% % 2996% % 2997% % 2998+ R e d u c e % 2999% % 3000% % 3001% % 3002%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3003% 3004% Reduce() traverses the color cube tree and prunes any node whose 3005% quantization error falls below a particular threshold. 3006% 3007% The format of the Reduce method is: 3008% 3009% Reduce(const Image *image,CubeInfo *cube_info,const NodeInfo *node_info) 3010% 3011% A description of each parameter follows. 3012% 3013% o image: the image. 3014% 3015% o cube_info: A pointer to the Cube structure. 3016% 3017% o node_info: pointer to node in color cube tree that is to be pruned. 3018% 3019*/ 3020static void Reduce(const Image *image,CubeInfo *cube_info, 3021 const NodeInfo *node_info) 3022{ 3023 register ssize_t 3024 i; 3025 3026 size_t 3027 number_children; 3028 3029 /* 3030 Traverse any children. 3031 */ 3032 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; 3033 for (i=0; i < (ssize_t) number_children; i++) 3034 if (node_info->child[i] != (NodeInfo *) NULL) 3035 Reduce(image,cube_info,node_info->child[i]); 3036 if (node_info->quantize_error <= cube_info->pruning_threshold) 3037 PruneChild(image,cube_info,node_info); 3038 else 3039 { 3040 /* 3041 Find minimum pruning threshold. 3042 */ 3043 if (node_info->number_unique > 0) 3044 cube_info->colors++; 3045 if (node_info->quantize_error < cube_info->next_threshold) 3046 cube_info->next_threshold=node_info->quantize_error; 3047 } 3048} 3049 3050/* 3051%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3052% % 3053% % 3054% % 3055+ R e d u c e I m a g e C o l o r s % 3056% % 3057% % 3058% % 3059%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3060% 3061% ReduceImageColors() repeatedly prunes the tree until the number of nodes 3062% with n2 > 0 is less than or equal to the maximum number of colors allowed 3063% in the output image. On any given iteration over the tree, it selects 3064% those nodes whose E value is minimal for pruning and merges their 3065% color statistics upward. It uses a pruning threshold, Ep, to govern 3066% node selection as follows: 3067% 3068% Ep = 0 3069% while number of nodes with (n2 > 0) > required maximum number of colors 3070% prune all nodes such that E <= Ep 3071% Set Ep to minimum E in remaining nodes 3072% 3073% This has the effect of minimizing any quantization error when merging 3074% two nodes together. 3075% 3076% When a node to be pruned has offspring, the pruning procedure invokes 3077% itself recursively in order to prune the tree from the leaves upward. 3078% n2, Sr, Sg, and Sb in a node being pruned are always added to the 3079% corresponding data in that node's parent. This retains the pruned 3080% node's color characteristics for later averaging. 3081% 3082% For each node, n2 pixels exist for which that node represents the 3083% smallest volume in RGB space containing those pixel's colors. When n2 3084% > 0 the node will uniquely define a color in the output image. At the 3085% beginning of reduction, n2 = 0 for all nodes except a the leaves of 3086% the tree which represent colors present in the input image. 3087% 3088% The other pixel count, n1, indicates the total number of colors 3089% within the cubic volume which the node represents. This includes n1 - 3090% n2 pixels whose colors should be defined by nodes at a lower level in 3091% the tree. 3092% 3093% The format of the ReduceImageColors method is: 3094% 3095% ReduceImageColors(const Image *image,CubeInfo *cube_info) 3096% 3097% A description of each parameter follows. 3098% 3099% o image: the image. 3100% 3101% o cube_info: A pointer to the Cube structure. 3102% 3103*/ 3104 3105static int MagickRealTypeCompare(const void *error_p,const void *error_q) 3106{ 3107 MagickRealType 3108 *p, 3109 *q; 3110 3111 p=(MagickRealType *) error_p; 3112 q=(MagickRealType *) error_q; 3113 if (*p > *q) 3114 return(1); 3115 if (fabs((double) (*q-*p)) <= MagickEpsilon) 3116 return(0); 3117 return(-1); 3118} 3119 3120static void ReduceImageColors(const Image *image,CubeInfo *cube_info) 3121{ 3122#define ReduceImageTag "Reduce/Image" 3123 3124 MagickBooleanType 3125 proceed; 3126 3127 MagickOffsetType 3128 offset; 3129 3130 size_t 3131 span; 3132 3133 cube_info->next_threshold=0.0; 3134 if ((cube_info->colors > cube_info->maximum_colors) && 3135 (cube_info->nodes > 128)) 3136 { 3137 MagickRealType 3138 *quantize_error; 3139 3140 /* 3141 Enable rapid reduction of the number of unique colors. 3142 */ 3143 quantize_error=(MagickRealType *) AcquireQuantumMemory(cube_info->nodes, 3144 sizeof(*quantize_error)); 3145 if (quantize_error != (MagickRealType *) NULL) 3146 { 3147 (void) QuantizeErrorFlatten(image,cube_info,cube_info->root,0, 3148 quantize_error); 3149 qsort(quantize_error,cube_info->nodes,sizeof(MagickRealType), 3150 MagickRealTypeCompare); 3151 cube_info->next_threshold=quantize_error[MagickMax((ssize_t) 3152 cube_info->nodes-110*(cube_info->maximum_colors+1)/100,0)]; 3153 quantize_error=(MagickRealType *) RelinquishMagickMemory( 3154 quantize_error); 3155 } 3156 } 3157 for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; ) 3158 { 3159 cube_info->pruning_threshold=cube_info->next_threshold; 3160 cube_info->next_threshold=cube_info->root->quantize_error-1; 3161 cube_info->colors=0; 3162 Reduce(image,cube_info,cube_info->root); 3163 offset=(MagickOffsetType) span-cube_info->colors; 3164 proceed=SetImageProgress(image,ReduceImageTag,offset,span- 3165 cube_info->maximum_colors+1); 3166 if (proceed == MagickFalse) 3167 break; 3168 } 3169} 3170 3171/* 3172%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3173% % 3174% % 3175% % 3176% R e m a p I m a g e % 3177% % 3178% % 3179% % 3180%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3181% 3182% RemapImage() replaces the colors of an image with a dither of the colors 3183% provided. 3184% 3185% The format of the RemapImage method is: 3186% 3187% MagickBooleanType RemapImage(const QuantizeInfo *quantize_info, 3188% Image *image,const Image *remap_image,ExceptionInfo *exception) 3189% 3190% A description of each parameter follows: 3191% 3192% o quantize_info: Specifies a pointer to an QuantizeInfo structure. 3193% 3194% o image: the image. 3195% 3196% o remap_image: the reference image. 3197% 3198% o exception: return any errors or warnings in this structure. 3199% 3200*/ 3201MagickExport MagickBooleanType RemapImage(const QuantizeInfo *quantize_info, 3202 Image *image,const Image *remap_image,ExceptionInfo *exception) 3203{ 3204 CubeInfo 3205 *cube_info; 3206 3207 MagickBooleanType 3208 status; 3209 3210 /* 3211 Initialize color cube. 3212 */ 3213 assert(image != (Image *) NULL); 3214 assert(image->signature == MagickSignature); 3215 if (image->debug != MagickFalse) 3216 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 3217 assert(remap_image != (Image *) NULL); 3218 assert(remap_image->signature == MagickSignature); 3219 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth, 3220 quantize_info->number_colors); 3221 if (cube_info == (CubeInfo *) NULL) 3222 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 3223 image->filename); 3224 status=ClassifyImageColors(cube_info,remap_image,exception); 3225 if (status != MagickFalse) 3226 { 3227 /* 3228 Classify image colors from the reference image. 3229 */ 3230 cube_info->quantize_info->number_colors=cube_info->colors; 3231 status=AssignImageColors(image,cube_info,exception); 3232 } 3233 DestroyCubeInfo(cube_info); 3234 return(status); 3235} 3236 3237/* 3238%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3239% % 3240% % 3241% % 3242% R e m a p I m a g e s % 3243% % 3244% % 3245% % 3246%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3247% 3248% RemapImages() replaces the colors of a sequence of images with the 3249% closest color from a reference image. 3250% 3251% The format of the RemapImage method is: 3252% 3253% MagickBooleanType RemapImages(const QuantizeInfo *quantize_info, 3254% Image *images,Image *remap_image,ExceptionInfo *exception) 3255% 3256% A description of each parameter follows: 3257% 3258% o quantize_info: Specifies a pointer to an QuantizeInfo structure. 3259% 3260% o images: the image sequence. 3261% 3262% o remap_image: the reference image. 3263% 3264% o exception: return any errors or warnings in this structure. 3265% 3266*/ 3267MagickExport MagickBooleanType RemapImages(const QuantizeInfo *quantize_info, 3268 Image *images,const Image *remap_image,ExceptionInfo *exception) 3269{ 3270 CubeInfo 3271 *cube_info; 3272 3273 Image 3274 *image; 3275 3276 MagickBooleanType 3277 status; 3278 3279 assert(images != (Image *) NULL); 3280 assert(images->signature == MagickSignature); 3281 if (images->debug != MagickFalse) 3282 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename); 3283 image=images; 3284 if (remap_image == (Image *) NULL) 3285 { 3286 /* 3287 Create a global colormap for an image sequence. 3288 */ 3289 status=QuantizeImages(quantize_info,images,exception); 3290 return(status); 3291 } 3292 /* 3293 Classify image colors from the reference image. 3294 */ 3295 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth, 3296 quantize_info->number_colors); 3297 if (cube_info == (CubeInfo *) NULL) 3298 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 3299 image->filename); 3300 status=ClassifyImageColors(cube_info,remap_image,exception); 3301 if (status != MagickFalse) 3302 { 3303 /* 3304 Classify image colors from the reference image. 3305 */ 3306 cube_info->quantize_info->number_colors=cube_info->colors; 3307 image=images; 3308 for ( ; image != (Image *) NULL; image=GetNextImageInList(image)) 3309 { 3310 status=AssignImageColors(image,cube_info,exception); 3311 if (status == MagickFalse) 3312 break; 3313 } 3314 } 3315 DestroyCubeInfo(cube_info); 3316 return(status); 3317} 3318 3319/* 3320%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3321% % 3322% % 3323% % 3324% S e t G r a y s c a l e I m a g e % 3325% % 3326% % 3327% % 3328%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3329% 3330% SetGrayscaleImage() converts an image to a PseudoClass grayscale image. 3331% 3332% The format of the SetGrayscaleImage method is: 3333% 3334% MagickBooleanType SetGrayscaleImage(Image *image,ExceptionInfo *exeption) 3335% 3336% A description of each parameter follows: 3337% 3338% o image: The image. 3339% 3340% o exception: return any errors or warnings in this structure. 3341% 3342*/ 3343 3344#if defined(__cplusplus) || defined(c_plusplus) 3345extern "C" { 3346#endif 3347 3348static int IntensityCompare(const void *x,const void *y) 3349{ 3350 PixelInfo 3351 *color_1, 3352 *color_2; 3353 3354 ssize_t 3355 intensity; 3356 3357 color_1=(PixelInfo *) x; 3358 color_2=(PixelInfo *) y; 3359 intensity=(ssize_t) (GetPixelInfoIntensity((const Image *) NULL,color_1)- 3360 (ssize_t) GetPixelInfoIntensity((const Image *) NULL,color_2)); 3361 return((int) intensity); 3362} 3363 3364#if defined(__cplusplus) || defined(c_plusplus) 3365} 3366#endif 3367 3368static MagickBooleanType SetGrayscaleImage(Image *image, 3369 ExceptionInfo *exception) 3370{ 3371 CacheView 3372 *image_view; 3373 3374 MagickBooleanType 3375 status; 3376 3377 PixelInfo 3378 *colormap; 3379 3380 register ssize_t 3381 i; 3382 3383 ssize_t 3384 *colormap_index, 3385 j, 3386 y; 3387 3388 assert(image != (Image *) NULL); 3389 assert(image->signature == MagickSignature); 3390 if (image->type != GrayscaleType) 3391 (void) TransformImageColorspace(image,GRAYColorspace,exception); 3392 colormap_index=(ssize_t *) AcquireQuantumMemory(MaxMap+1, 3393 sizeof(*colormap_index)); 3394 if (colormap_index == (ssize_t *) NULL) 3395 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 3396 image->filename); 3397 if (image->storage_class != PseudoClass) 3398 { 3399 for (i=0; i <= (ssize_t) MaxMap; i++) 3400 colormap_index[i]=(-1); 3401 if (AcquireImageColormap(image,MaxMap+1,exception) == MagickFalse) 3402 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 3403 image->filename); 3404 image->colors=0; 3405 status=MagickTrue; 3406 image_view=AcquireAuthenticCacheView(image,exception); 3407#if defined(MAGICKCORE_OPENMP_SUPPORT) 3408 #pragma omp parallel for schedule(static,4) shared(status) \ 3409 magick_threads(image,image,image->rows,1) 3410#endif 3411 for (y=0; y < (ssize_t) image->rows; y++) 3412 { 3413 register Quantum 3414 *restrict q; 3415 3416 register ssize_t 3417 x; 3418 3419 if (status == MagickFalse) 3420 continue; 3421 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1, 3422 exception); 3423 if (q == (Quantum *) NULL) 3424 { 3425 status=MagickFalse; 3426 continue; 3427 } 3428 for (x=0; x < (ssize_t) image->columns; x++) 3429 { 3430 register size_t 3431 intensity; 3432 3433 intensity=ScaleQuantumToMap(GetPixelRed(image,q)); 3434 if (colormap_index[intensity] < 0) 3435 { 3436#if defined(MAGICKCORE_OPENMP_SUPPORT) 3437 #pragma omp critical (MagickCore_SetGrayscaleImage) 3438#endif 3439 if (colormap_index[intensity] < 0) 3440 { 3441 colormap_index[intensity]=(ssize_t) image->colors; 3442 image->colormap[image->colors].red=(double) 3443 GetPixelRed(image,q); 3444 image->colormap[image->colors].green=(double) 3445 GetPixelGreen(image,q); 3446 image->colormap[image->colors].blue=(double) 3447 GetPixelBlue(image,q); 3448 image->colors++; 3449 } 3450 } 3451 SetPixelIndex(image,(Quantum) colormap_index[intensity],q); 3452 q+=GetPixelChannels(image); 3453 } 3454 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) 3455 status=MagickFalse; 3456 } 3457 image_view=DestroyCacheView(image_view); 3458 } 3459 for (i=0; i < (ssize_t) image->colors; i++) 3460 image->colormap[i].alpha=(double) i; 3461 qsort((void *) image->colormap,image->colors,sizeof(PixelInfo), 3462 IntensityCompare); 3463 colormap=(PixelInfo *) AcquireQuantumMemory(image->colors,sizeof(*colormap)); 3464 if (colormap == (PixelInfo *) NULL) 3465 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 3466 image->filename); 3467 j=0; 3468 colormap[j]=image->colormap[0]; 3469 for (i=0; i < (ssize_t) image->colors; i++) 3470 { 3471 if (IsPixelInfoEquivalent(&colormap[j],&image->colormap[i]) == MagickFalse) 3472 { 3473 j++; 3474 colormap[j]=image->colormap[i]; 3475 } 3476 colormap_index[(ssize_t) image->colormap[i].alpha]=j; 3477 } 3478 image->colors=(size_t) (j+1); 3479 image->colormap=(PixelInfo *) RelinquishMagickMemory(image->colormap); 3480 image->colormap=colormap; 3481 status=MagickTrue; 3482 image_view=AcquireAuthenticCacheView(image,exception); 3483#if defined(MAGICKCORE_OPENMP_SUPPORT) 3484 #pragma omp parallel for schedule(static,4) shared(status) \ 3485 magick_threads(image,image,image->rows,1) 3486#endif 3487 for (y=0; y < (ssize_t) image->rows; y++) 3488 { 3489 register Quantum 3490 *restrict q; 3491 3492 register ssize_t 3493 x; 3494 3495 if (status == MagickFalse) 3496 continue; 3497 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception); 3498 if (q == (Quantum *) NULL) 3499 { 3500 status=MagickFalse; 3501 continue; 3502 } 3503 for (x=0; x < (ssize_t) image->columns; x++) 3504 { 3505 SetPixelIndex(image,(Quantum) colormap_index[ScaleQuantumToMap( 3506 GetPixelIndex(image,q))],q); 3507 q+=GetPixelChannels(image); 3508 } 3509 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) 3510 status=MagickFalse; 3511 } 3512 image_view=DestroyCacheView(image_view); 3513 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index); 3514 image->type=GrayscaleType; 3515 if (IsImageMonochrome(image,exception) != MagickFalse) 3516 image->type=BilevelType; 3517 return(status); 3518} 3519