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