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