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