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