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