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