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