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