quantize.c revision 4c08aed51c5899665ade97263692328eea4af106
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/enhance.h" 185#include "MagickCore/exception.h" 186#include "MagickCore/exception-private.h" 187#include "MagickCore/histogram.h" 188#include "MagickCore/image.h" 189#include "MagickCore/image-private.h" 190#include "MagickCore/list.h" 191#include "MagickCore/memory_.h" 192#include "MagickCore/monitor.h" 193#include "MagickCore/monitor-private.h" 194#include "MagickCore/option.h" 195#include "MagickCore/pixel-accessor.h" 196#include "MagickCore/quantize.h" 197#include "MagickCore/quantum.h" 198#include "MagickCore/quantum-private.h" 199#include "MagickCore/string_.h" 200#include "MagickCore/thread-private.h" 201 202/* 203 Define declarations. 204*/ 205#if !defined(__APPLE__) && !defined(TARGET_OS_IPHONE) 206#define CacheShift 2 207#else 208#define CacheShift 3 209#endif 210#define ErrorQueueLength 16 211#define MaxNodes 266817 212#define MaxTreeDepth 8 213#define NodesInAList 1920 214 215/* 216 Typdef declarations. 217*/ 218typedef struct _RealPixelPacket 219{ 220 MagickRealType 221 red, 222 green, 223 blue, 224 alpha; 225} RealPixelPacket; 226 227typedef struct _NodeInfo 228{ 229 struct _NodeInfo 230 *parent, 231 *child[16]; 232 233 MagickSizeType 234 number_unique; 235 236 RealPixelPacket 237 total_color; 238 239 MagickRealType 240 quantize_error; 241 242 size_t 243 color_number, 244 id, 245 level; 246} NodeInfo; 247 248typedef struct _Nodes 249{ 250 NodeInfo 251 *nodes; 252 253 struct _Nodes 254 *next; 255} Nodes; 256 257typedef struct _CubeInfo 258{ 259 NodeInfo 260 *root; 261 262 size_t 263 colors, 264 maximum_colors; 265 266 ssize_t 267 transparent_index; 268 269 MagickSizeType 270 transparent_pixels; 271 272 RealPixelPacket 273 target; 274 275 MagickRealType 276 distance, 277 pruning_threshold, 278 next_threshold; 279 280 size_t 281 nodes, 282 free_nodes, 283 color_number; 284 285 NodeInfo 286 *next_node; 287 288 Nodes 289 *node_queue; 290 291 ssize_t 292 *cache; 293 294 RealPixelPacket 295 error[ErrorQueueLength]; 296 297 MagickRealType 298 weights[ErrorQueueLength]; 299 300 QuantizeInfo 301 *quantize_info; 302 303 MagickBooleanType 304 associate_alpha; 305 306 ssize_t 307 x, 308 y; 309 310 size_t 311 depth; 312 313 MagickOffsetType 314 offset; 315 316 MagickSizeType 317 span; 318} CubeInfo; 319 320/* 321 Method prototypes. 322*/ 323static CubeInfo 324 *GetCubeInfo(const QuantizeInfo *,const size_t,const size_t); 325 326static NodeInfo 327 *GetNodeInfo(CubeInfo *,const size_t,const size_t,NodeInfo *); 328 329static MagickBooleanType 330 AssignImageColors(Image *,CubeInfo *), 331 ClassifyImageColors(CubeInfo *,const Image *,ExceptionInfo *), 332 DitherImage(Image *,CubeInfo *), 333 SetGrayscaleImage(Image *); 334 335static size_t 336 DefineImageColormap(Image *,CubeInfo *,NodeInfo *); 337 338static void 339 ClosestColor(const Image *,CubeInfo *,const NodeInfo *), 340 DestroyCubeInfo(CubeInfo *), 341 PruneLevel(const Image *,CubeInfo *,const NodeInfo *), 342 PruneToCubeDepth(const Image *,CubeInfo *,const NodeInfo *), 343 ReduceImageColors(const Image *,CubeInfo *); 344 345/* 346%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 347% % 348% % 349% % 350% A c q u i r e Q u a n t i z e I n f o % 351% % 352% % 353% % 354%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 355% 356% AcquireQuantizeInfo() allocates the QuantizeInfo structure. 357% 358% The format of the AcquireQuantizeInfo method is: 359% 360% QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info) 361% 362% A description of each parameter follows: 363% 364% o image_info: the image info. 365% 366*/ 367MagickExport QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info) 368{ 369 QuantizeInfo 370 *quantize_info; 371 372 quantize_info=(QuantizeInfo *) AcquireMagickMemory(sizeof(*quantize_info)); 373 if (quantize_info == (QuantizeInfo *) NULL) 374 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); 375 GetQuantizeInfo(quantize_info); 376 if (image_info != (ImageInfo *) NULL) 377 { 378 const char 379 *option; 380 381 quantize_info->dither=image_info->dither; 382 option=GetImageOption(image_info,"dither"); 383 if (option != (const char *) NULL) 384 quantize_info->dither_method=(DitherMethod) ParseCommandOption( 385 MagickDitherOptions,MagickFalse,option); 386 quantize_info->measure_error=image_info->verbose; 387 } 388 return(quantize_info); 389} 390 391/* 392%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 393% % 394% % 395% % 396+ A s s i g n I m a g e C o l o r s % 397% % 398% % 399% % 400%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 401% 402% AssignImageColors() generates the output image from the pruned tree. The 403% output image consists of two parts: (1) A color map, which is an array 404% of color descriptions (RGB triples) for each color present in the 405% output image; (2) A pixel array, which represents each pixel as an 406% index into the color map array. 407% 408% First, the assignment phase makes one pass over the pruned color 409% description tree to establish the image's color map. For each node 410% with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean 411% color of all pixels that classify no lower than this node. Each of 412% these colors becomes an entry in the color map. 413% 414% Finally, the assignment phase reclassifies each pixel in the pruned 415% tree to identify the deepest node containing the pixel's color. The 416% pixel's value in the pixel array becomes the index of this node's mean 417% color in the color map. 418% 419% The format of the AssignImageColors() method is: 420% 421% MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info) 422% 423% A description of each parameter follows. 424% 425% o image: the image. 426% 427% o cube_info: A pointer to the Cube structure. 428% 429*/ 430 431static inline void AssociateAlphaPixel(const Image *image, 432 const CubeInfo *cube_info,const Quantum *pixel, 433 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 (image->colorspace != RGBColorspace) && 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 == (const 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 (image->colorspace != RGBColorspace)) 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 == (const 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 == (const 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% MagickBooleanType PosterizeImageChannel(Image *image, 2282% const ChannelType channel,const size_t levels, 2283% const MagickBooleanType dither) 2284% 2285% A description of each parameter follows: 2286% 2287% o image: Specifies a pointer to an Image structure. 2288% 2289% o levels: Number of color levels allowed in each channel. Very low values 2290% (2, 3, or 4) have the most visible effect. 2291% 2292% o dither: Set this integer value to something other than zero to dither 2293% the mapped image. 2294% 2295*/ 2296 2297static inline ssize_t MagickRound(MagickRealType x) 2298{ 2299 /* 2300 Round the fraction to nearest integer. 2301 */ 2302 if (x >= 0.0) 2303 return((ssize_t) (x+0.5)); 2304 return((ssize_t) (x-0.5)); 2305} 2306 2307MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels, 2308 const MagickBooleanType dither) 2309{ 2310 MagickBooleanType 2311 status; 2312 2313 status=PosterizeImageChannel(image,DefaultChannels,levels,dither); 2314 return(status); 2315} 2316 2317MagickExport MagickBooleanType PosterizeImageChannel(Image *image, 2318 const ChannelType channel,const size_t levels,const MagickBooleanType dither) 2319{ 2320#define PosterizeImageTag "Posterize/Image" 2321#define PosterizePixel(pixel) (Quantum) (QuantumRange*(MagickRound( \ 2322 QuantumScale*pixel*(levels-1)))/MagickMax((ssize_t) levels-1,1)) 2323 2324 CacheView 2325 *image_view; 2326 2327 ExceptionInfo 2328 *exception; 2329 2330 MagickBooleanType 2331 status; 2332 2333 MagickOffsetType 2334 progress; 2335 2336 QuantizeInfo 2337 *quantize_info; 2338 2339 register ssize_t 2340 i; 2341 2342 ssize_t 2343 y; 2344 2345 assert(image != (Image *) NULL); 2346 assert(image->signature == MagickSignature); 2347 if (image->debug != MagickFalse) 2348 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 2349 if (image->storage_class == PseudoClass) 2350#if defined(MAGICKCORE_OPENMP_SUPPORT) 2351 #pragma omp parallel for schedule(dynamic,4) shared(progress,status) 2352#endif 2353 for (i=0; i < (ssize_t) image->colors; i++) 2354 { 2355 /* 2356 Posterize colormap. 2357 */ 2358 if ((channel & RedChannel) != 0) 2359 image->colormap[i].red=PosterizePixel(image->colormap[i].red); 2360 if ((channel & GreenChannel) != 0) 2361 image->colormap[i].green=PosterizePixel(image->colormap[i].green); 2362 if ((channel & BlueChannel) != 0) 2363 image->colormap[i].blue=PosterizePixel(image->colormap[i].blue); 2364 if ((channel & OpacityChannel) != 0) 2365 image->colormap[i].alpha=PosterizePixel(image->colormap[i].alpha); 2366 } 2367 /* 2368 Posterize image. 2369 */ 2370 status=MagickTrue; 2371 progress=0; 2372 exception=(&image->exception); 2373 image_view=AcquireCacheView(image); 2374#if defined(MAGICKCORE_OPENMP_SUPPORT) 2375 #pragma omp parallel for schedule(dynamic,4) shared(progress,status) 2376#endif 2377 for (y=0; y < (ssize_t) image->rows; y++) 2378 { 2379 register Quantum 2380 *restrict q; 2381 2382 register ssize_t 2383 x; 2384 2385 if (status == MagickFalse) 2386 continue; 2387 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception); 2388 if (q == (const Quantum *) NULL) 2389 { 2390 status=MagickFalse; 2391 continue; 2392 } 2393 for (x=0; x < (ssize_t) image->columns; x++) 2394 { 2395 if ((channel & RedChannel) != 0) 2396 SetPixelRed(image,PosterizePixel(GetPixelRed(image,q)),q); 2397 if ((channel & GreenChannel) != 0) 2398 SetPixelGreen(image,PosterizePixel(GetPixelGreen(image,q)),q); 2399 if ((channel & BlueChannel) != 0) 2400 SetPixelBlue(image,PosterizePixel(GetPixelBlue(image,q)),q); 2401 if (((channel & BlackChannel) != 0) && 2402 (image->colorspace == CMYKColorspace)) 2403 SetPixelBlack(image,PosterizePixel(GetPixelBlack(image,q)),q); 2404 if (((channel & OpacityChannel) != 0) && 2405 (image->matte == MagickTrue)) 2406 SetPixelAlpha(image,PosterizePixel(GetPixelAlpha(image,q)),q); 2407 q+=GetPixelChannels(image); 2408 } 2409 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) 2410 status=MagickFalse; 2411 if (image->progress_monitor != (MagickProgressMonitor) NULL) 2412 { 2413 MagickBooleanType 2414 proceed; 2415 2416#if defined(MAGICKCORE_OPENMP_SUPPORT) 2417 #pragma omp critical (MagickCore_PosterizeImageChannel) 2418#endif 2419 proceed=SetImageProgress(image,PosterizeImageTag,progress++, 2420 image->rows); 2421 if (proceed == MagickFalse) 2422 status=MagickFalse; 2423 } 2424 } 2425 image_view=DestroyCacheView(image_view); 2426 quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL); 2427 quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels* 2428 levels,MaxColormapSize+1); 2429 quantize_info->dither=dither; 2430 quantize_info->tree_depth=MaxTreeDepth; 2431 status=QuantizeImage(quantize_info,image); 2432 quantize_info=DestroyQuantizeInfo(quantize_info); 2433 return(status); 2434} 2435 2436/* 2437%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2438% % 2439% % 2440% % 2441+ P r u n e C h i l d % 2442% % 2443% % 2444% % 2445%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2446% 2447% PruneChild() deletes the given node and merges its statistics into its 2448% parent. 2449% 2450% The format of the PruneSubtree method is: 2451% 2452% PruneChild(const Image *image,CubeInfo *cube_info, 2453% const NodeInfo *node_info) 2454% 2455% A description of each parameter follows. 2456% 2457% o image: the image. 2458% 2459% o cube_info: A pointer to the Cube structure. 2460% 2461% o node_info: pointer to node in color cube tree that is to be pruned. 2462% 2463*/ 2464static void PruneChild(const Image *image,CubeInfo *cube_info, 2465 const NodeInfo *node_info) 2466{ 2467 NodeInfo 2468 *parent; 2469 2470 register ssize_t 2471 i; 2472 2473 size_t 2474 number_children; 2475 2476 /* 2477 Traverse any children. 2478 */ 2479 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; 2480 for (i=0; i < (ssize_t) number_children; i++) 2481 if (node_info->child[i] != (NodeInfo *) NULL) 2482 PruneChild(image,cube_info,node_info->child[i]); 2483 /* 2484 Merge color statistics into parent. 2485 */ 2486 parent=node_info->parent; 2487 parent->number_unique+=node_info->number_unique; 2488 parent->total_color.red+=node_info->total_color.red; 2489 parent->total_color.green+=node_info->total_color.green; 2490 parent->total_color.blue+=node_info->total_color.blue; 2491 parent->total_color.alpha+=node_info->total_color.alpha; 2492 parent->child[node_info->id]=(NodeInfo *) NULL; 2493 cube_info->nodes--; 2494} 2495 2496/* 2497%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2498% % 2499% % 2500% % 2501+ P r u n e L e v e l % 2502% % 2503% % 2504% % 2505%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2506% 2507% PruneLevel() deletes all nodes at the bottom level of the color tree merging 2508% their color statistics into their parent node. 2509% 2510% The format of the PruneLevel method is: 2511% 2512% PruneLevel(const Image *image,CubeInfo *cube_info, 2513% const NodeInfo *node_info) 2514% 2515% A description of each parameter follows. 2516% 2517% o image: the image. 2518% 2519% o cube_info: A pointer to the Cube structure. 2520% 2521% o node_info: pointer to node in color cube tree that is to be pruned. 2522% 2523*/ 2524static void PruneLevel(const Image *image,CubeInfo *cube_info, 2525 const NodeInfo *node_info) 2526{ 2527 register ssize_t 2528 i; 2529 2530 size_t 2531 number_children; 2532 2533 /* 2534 Traverse any children. 2535 */ 2536 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; 2537 for (i=0; i < (ssize_t) number_children; i++) 2538 if (node_info->child[i] != (NodeInfo *) NULL) 2539 PruneLevel(image,cube_info,node_info->child[i]); 2540 if (node_info->level == cube_info->depth) 2541 PruneChild(image,cube_info,node_info); 2542} 2543 2544/* 2545%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2546% % 2547% % 2548% % 2549+ P r u n e T o C u b e D e p t h % 2550% % 2551% % 2552% % 2553%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2554% 2555% PruneToCubeDepth() deletes any nodes at a depth greater than 2556% cube_info->depth while merging their color statistics into their parent 2557% node. 2558% 2559% The format of the PruneToCubeDepth method is: 2560% 2561% PruneToCubeDepth(const Image *image,CubeInfo *cube_info, 2562% const NodeInfo *node_info) 2563% 2564% A description of each parameter follows. 2565% 2566% o cube_info: A pointer to the Cube structure. 2567% 2568% o node_info: pointer to node in color cube tree that is to be pruned. 2569% 2570*/ 2571static void PruneToCubeDepth(const Image *image,CubeInfo *cube_info, 2572 const NodeInfo *node_info) 2573{ 2574 register ssize_t 2575 i; 2576 2577 size_t 2578 number_children; 2579 2580 /* 2581 Traverse any children. 2582 */ 2583 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; 2584 for (i=0; i < (ssize_t) number_children; i++) 2585 if (node_info->child[i] != (NodeInfo *) NULL) 2586 PruneToCubeDepth(image,cube_info,node_info->child[i]); 2587 if (node_info->level > cube_info->depth) 2588 PruneChild(image,cube_info,node_info); 2589} 2590 2591/* 2592%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2593% % 2594% % 2595% % 2596% Q u a n t i z e I m a g e % 2597% % 2598% % 2599% % 2600%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2601% 2602% QuantizeImage() analyzes the colors within a reference image and chooses a 2603% fixed number of colors to represent the image. The goal of the algorithm 2604% is to minimize the color difference between the input and output image while 2605% minimizing the processing time. 2606% 2607% The format of the QuantizeImage method is: 2608% 2609% MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info, 2610% Image *image) 2611% 2612% A description of each parameter follows: 2613% 2614% o quantize_info: Specifies a pointer to an QuantizeInfo structure. 2615% 2616% o image: the image. 2617% 2618*/ 2619MagickExport MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info, 2620 Image *image) 2621{ 2622 CubeInfo 2623 *cube_info; 2624 2625 MagickBooleanType 2626 status; 2627 2628 size_t 2629 depth, 2630 maximum_colors; 2631 2632 assert(quantize_info != (const QuantizeInfo *) NULL); 2633 assert(quantize_info->signature == MagickSignature); 2634 assert(image != (Image *) NULL); 2635 assert(image->signature == MagickSignature); 2636 if (image->debug != MagickFalse) 2637 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 2638 maximum_colors=quantize_info->number_colors; 2639 if (maximum_colors == 0) 2640 maximum_colors=MaxColormapSize; 2641 if (maximum_colors > MaxColormapSize) 2642 maximum_colors=MaxColormapSize; 2643 if ((IsImageGray(image,&image->exception) != MagickFalse) && 2644 (image->matte == MagickFalse)) 2645 (void) SetGrayscaleImage(image); 2646 if ((image->storage_class == PseudoClass) && 2647 (image->colors <= maximum_colors)) 2648 return(MagickTrue); 2649 depth=quantize_info->tree_depth; 2650 if (depth == 0) 2651 { 2652 size_t 2653 colors; 2654 2655 /* 2656 Depth of color tree is: Log4(colormap size)+2. 2657 */ 2658 colors=maximum_colors; 2659 for (depth=1; colors != 0; depth++) 2660 colors>>=2; 2661 if ((quantize_info->dither != MagickFalse) && (depth > 2)) 2662 depth--; 2663 if ((image->matte != MagickFalse) && (depth > 5)) 2664 depth--; 2665 } 2666 /* 2667 Initialize color cube. 2668 */ 2669 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors); 2670 if (cube_info == (CubeInfo *) NULL) 2671 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 2672 image->filename); 2673 status=ClassifyImageColors(cube_info,image,&image->exception); 2674 if (status != MagickFalse) 2675 { 2676 /* 2677 Reduce the number of colors in the image. 2678 */ 2679 ReduceImageColors(image,cube_info); 2680 status=AssignImageColors(image,cube_info); 2681 } 2682 DestroyCubeInfo(cube_info); 2683 return(status); 2684} 2685 2686/* 2687%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2688% % 2689% % 2690% % 2691% Q u a n t i z e I m a g e s % 2692% % 2693% % 2694% % 2695%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2696% 2697% QuantizeImages() analyzes the colors within a set of reference images and 2698% chooses a fixed number of colors to represent the set. The goal of the 2699% algorithm is to minimize the color difference between the input and output 2700% images while minimizing the processing time. 2701% 2702% The format of the QuantizeImages method is: 2703% 2704% MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info, 2705% Image *images) 2706% 2707% A description of each parameter follows: 2708% 2709% o quantize_info: Specifies a pointer to an QuantizeInfo structure. 2710% 2711% o images: Specifies a pointer to a list of Image structures. 2712% 2713*/ 2714MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info, 2715 Image *images) 2716{ 2717 CubeInfo 2718 *cube_info; 2719 2720 Image 2721 *image; 2722 2723 MagickBooleanType 2724 proceed, 2725 status; 2726 2727 MagickProgressMonitor 2728 progress_monitor; 2729 2730 register ssize_t 2731 i; 2732 2733 size_t 2734 depth, 2735 maximum_colors, 2736 number_images; 2737 2738 assert(quantize_info != (const QuantizeInfo *) NULL); 2739 assert(quantize_info->signature == MagickSignature); 2740 assert(images != (Image *) NULL); 2741 assert(images->signature == MagickSignature); 2742 if (images->debug != MagickFalse) 2743 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename); 2744 if (GetNextImageInList(images) == (Image *) NULL) 2745 { 2746 /* 2747 Handle a single image with QuantizeImage. 2748 */ 2749 status=QuantizeImage(quantize_info,images); 2750 return(status); 2751 } 2752 status=MagickFalse; 2753 maximum_colors=quantize_info->number_colors; 2754 if (maximum_colors == 0) 2755 maximum_colors=MaxColormapSize; 2756 if (maximum_colors > MaxColormapSize) 2757 maximum_colors=MaxColormapSize; 2758 depth=quantize_info->tree_depth; 2759 if (depth == 0) 2760 { 2761 size_t 2762 colors; 2763 2764 /* 2765 Depth of color tree is: Log4(colormap size)+2. 2766 */ 2767 colors=maximum_colors; 2768 for (depth=1; colors != 0; depth++) 2769 colors>>=2; 2770 if (quantize_info->dither != MagickFalse) 2771 depth--; 2772 } 2773 /* 2774 Initialize color cube. 2775 */ 2776 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors); 2777 if (cube_info == (CubeInfo *) NULL) 2778 { 2779 (void) ThrowMagickException(&images->exception,GetMagickModule(), 2780 ResourceLimitError,"MemoryAllocationFailed","`%s'",images->filename); 2781 return(MagickFalse); 2782 } 2783 number_images=GetImageListLength(images); 2784 image=images; 2785 for (i=0; image != (Image *) NULL; i++) 2786 { 2787 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL, 2788 image->client_data); 2789 status=ClassifyImageColors(cube_info,image,&image->exception); 2790 if (status == MagickFalse) 2791 break; 2792 (void) SetImageProgressMonitor(image,progress_monitor,image->client_data); 2793 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i, 2794 number_images); 2795 if (proceed == MagickFalse) 2796 break; 2797 image=GetNextImageInList(image); 2798 } 2799 if (status != MagickFalse) 2800 { 2801 /* 2802 Reduce the number of colors in an image sequence. 2803 */ 2804 ReduceImageColors(images,cube_info); 2805 image=images; 2806 for (i=0; image != (Image *) NULL; i++) 2807 { 2808 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) 2809 NULL,image->client_data); 2810 status=AssignImageColors(image,cube_info); 2811 if (status == MagickFalse) 2812 break; 2813 (void) SetImageProgressMonitor(image,progress_monitor, 2814 image->client_data); 2815 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i, 2816 number_images); 2817 if (proceed == MagickFalse) 2818 break; 2819 image=GetNextImageInList(image); 2820 } 2821 } 2822 DestroyCubeInfo(cube_info); 2823 return(status); 2824} 2825 2826/* 2827%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2828% % 2829% % 2830% % 2831+ R e d u c e % 2832% % 2833% % 2834% % 2835%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2836% 2837% Reduce() traverses the color cube tree and prunes any node whose 2838% quantization error falls below a particular threshold. 2839% 2840% The format of the Reduce method is: 2841% 2842% Reduce(const Image *image,CubeInfo *cube_info,const NodeInfo *node_info) 2843% 2844% A description of each parameter follows. 2845% 2846% o image: the image. 2847% 2848% o cube_info: A pointer to the Cube structure. 2849% 2850% o node_info: pointer to node in color cube tree that is to be pruned. 2851% 2852*/ 2853static void Reduce(const Image *image,CubeInfo *cube_info, 2854 const NodeInfo *node_info) 2855{ 2856 register ssize_t 2857 i; 2858 2859 size_t 2860 number_children; 2861 2862 /* 2863 Traverse any children. 2864 */ 2865 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; 2866 for (i=0; i < (ssize_t) number_children; i++) 2867 if (node_info->child[i] != (NodeInfo *) NULL) 2868 Reduce(image,cube_info,node_info->child[i]); 2869 if (node_info->quantize_error <= cube_info->pruning_threshold) 2870 PruneChild(image,cube_info,node_info); 2871 else 2872 { 2873 /* 2874 Find minimum pruning threshold. 2875 */ 2876 if (node_info->number_unique > 0) 2877 cube_info->colors++; 2878 if (node_info->quantize_error < cube_info->next_threshold) 2879 cube_info->next_threshold=node_info->quantize_error; 2880 } 2881} 2882 2883/* 2884%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2885% % 2886% % 2887% % 2888+ R e d u c e I m a g e C o l o r s % 2889% % 2890% % 2891% % 2892%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2893% 2894% ReduceImageColors() repeatedly prunes the tree until the number of nodes 2895% with n2 > 0 is less than or equal to the maximum number of colors allowed 2896% in the output image. On any given iteration over the tree, it selects 2897% those nodes whose E value is minimal for pruning and merges their 2898% color statistics upward. It uses a pruning threshold, Ep, to govern 2899% node selection as follows: 2900% 2901% Ep = 0 2902% while number of nodes with (n2 > 0) > required maximum number of colors 2903% prune all nodes such that E <= Ep 2904% Set Ep to minimum E in remaining nodes 2905% 2906% This has the effect of minimizing any quantization error when merging 2907% two nodes together. 2908% 2909% When a node to be pruned has offspring, the pruning procedure invokes 2910% itself recursively in order to prune the tree from the leaves upward. 2911% n2, Sr, Sg, and Sb in a node being pruned are always added to the 2912% corresponding data in that node's parent. This retains the pruned 2913% node's color characteristics for later averaging. 2914% 2915% For each node, n2 pixels exist for which that node represents the 2916% smallest volume in RGB space containing those pixel's colors. When n2 2917% > 0 the node will uniquely define a color in the output image. At the 2918% beginning of reduction, n2 = 0 for all nodes except a the leaves of 2919% the tree which represent colors present in the input image. 2920% 2921% The other pixel count, n1, indicates the total number of colors 2922% within the cubic volume which the node represents. This includes n1 - 2923% n2 pixels whose colors should be defined by nodes at a lower level in 2924% the tree. 2925% 2926% The format of the ReduceImageColors method is: 2927% 2928% ReduceImageColors(const Image *image,CubeInfo *cube_info) 2929% 2930% A description of each parameter follows. 2931% 2932% o image: the image. 2933% 2934% o cube_info: A pointer to the Cube structure. 2935% 2936*/ 2937static void ReduceImageColors(const Image *image,CubeInfo *cube_info) 2938{ 2939#define ReduceImageTag "Reduce/Image" 2940 2941 MagickBooleanType 2942 proceed; 2943 2944 MagickOffsetType 2945 offset; 2946 2947 size_t 2948 span; 2949 2950 cube_info->next_threshold=0.0; 2951 for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; ) 2952 { 2953 cube_info->pruning_threshold=cube_info->next_threshold; 2954 cube_info->next_threshold=cube_info->root->quantize_error-1; 2955 cube_info->colors=0; 2956 Reduce(image,cube_info,cube_info->root); 2957 offset=(MagickOffsetType) span-cube_info->colors; 2958 proceed=SetImageProgress(image,ReduceImageTag,offset,span- 2959 cube_info->maximum_colors+1); 2960 if (proceed == MagickFalse) 2961 break; 2962 } 2963} 2964 2965/* 2966%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2967% % 2968% % 2969% % 2970% R e m a p I m a g e % 2971% % 2972% % 2973% % 2974%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2975% 2976% RemapImage() replaces the colors of an image with the closest color from 2977% a reference image. 2978% 2979% The format of the RemapImage method is: 2980% 2981% MagickBooleanType RemapImage(const QuantizeInfo *quantize_info, 2982% Image *image,const Image *remap_image) 2983% 2984% A description of each parameter follows: 2985% 2986% o quantize_info: Specifies a pointer to an QuantizeInfo structure. 2987% 2988% o image: the image. 2989% 2990% o remap_image: the reference image. 2991% 2992*/ 2993MagickExport MagickBooleanType RemapImage(const QuantizeInfo *quantize_info, 2994 Image *image,const Image *remap_image) 2995{ 2996 CubeInfo 2997 *cube_info; 2998 2999 MagickBooleanType 3000 status; 3001 3002 /* 3003 Initialize color cube. 3004 */ 3005 assert(image != (Image *) NULL); 3006 assert(image->signature == MagickSignature); 3007 if (image->debug != MagickFalse) 3008 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 3009 assert(remap_image != (Image *) NULL); 3010 assert(remap_image->signature == MagickSignature); 3011 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth, 3012 quantize_info->number_colors); 3013 if (cube_info == (CubeInfo *) NULL) 3014 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 3015 image->filename); 3016 status=ClassifyImageColors(cube_info,remap_image,&image->exception); 3017 if (status != MagickFalse) 3018 { 3019 /* 3020 Classify image colors from the reference image. 3021 */ 3022 cube_info->quantize_info->number_colors=cube_info->colors; 3023 status=AssignImageColors(image,cube_info); 3024 } 3025 DestroyCubeInfo(cube_info); 3026 return(status); 3027} 3028 3029/* 3030%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3031% % 3032% % 3033% % 3034% R e m a p I m a g e s % 3035% % 3036% % 3037% % 3038%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3039% 3040% RemapImages() replaces the colors of a sequence of images with the 3041% closest color from a reference image. 3042% 3043% The format of the RemapImage method is: 3044% 3045% MagickBooleanType RemapImages(const QuantizeInfo *quantize_info, 3046% Image *images,Image *remap_image) 3047% 3048% A description of each parameter follows: 3049% 3050% o quantize_info: Specifies a pointer to an QuantizeInfo structure. 3051% 3052% o images: the image sequence. 3053% 3054% o remap_image: the reference image. 3055% 3056*/ 3057MagickExport MagickBooleanType RemapImages(const QuantizeInfo *quantize_info, 3058 Image *images,const Image *remap_image) 3059{ 3060 CubeInfo 3061 *cube_info; 3062 3063 Image 3064 *image; 3065 3066 MagickBooleanType 3067 status; 3068 3069 assert(images != (Image *) NULL); 3070 assert(images->signature == MagickSignature); 3071 if (images->debug != MagickFalse) 3072 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename); 3073 image=images; 3074 if (remap_image == (Image *) NULL) 3075 { 3076 /* 3077 Create a global colormap for an image sequence. 3078 */ 3079 status=QuantizeImages(quantize_info,images); 3080 return(status); 3081 } 3082 /* 3083 Classify image colors from the reference image. 3084 */ 3085 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth, 3086 quantize_info->number_colors); 3087 if (cube_info == (CubeInfo *) NULL) 3088 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 3089 image->filename); 3090 status=ClassifyImageColors(cube_info,remap_image,&image->exception); 3091 if (status != MagickFalse) 3092 { 3093 /* 3094 Classify image colors from the reference image. 3095 */ 3096 cube_info->quantize_info->number_colors=cube_info->colors; 3097 image=images; 3098 for ( ; image != (Image *) NULL; image=GetNextImageInList(image)) 3099 { 3100 status=AssignImageColors(image,cube_info); 3101 if (status == MagickFalse) 3102 break; 3103 } 3104 } 3105 DestroyCubeInfo(cube_info); 3106 return(status); 3107} 3108 3109/* 3110%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3111% % 3112% % 3113% % 3114% S e t G r a y s c a l e I m a g e % 3115% % 3116% % 3117% % 3118%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3119% 3120% SetGrayscaleImage() converts an image to a PseudoClass grayscale image. 3121% 3122% The format of the SetGrayscaleImage method is: 3123% 3124% MagickBooleanType SetGrayscaleImage(Image *image) 3125% 3126% A description of each parameter follows: 3127% 3128% o image: The image. 3129% 3130*/ 3131 3132#if defined(__cplusplus) || defined(c_plusplus) 3133extern "C" { 3134#endif 3135 3136static int IntensityCompare(const void *x,const void *y) 3137{ 3138 PixelPacket 3139 *color_1, 3140 *color_2; 3141 3142 ssize_t 3143 intensity; 3144 3145 color_1=(PixelPacket *) x; 3146 color_2=(PixelPacket *) y; 3147 intensity=GetPixelPacketIntensity(color_1)-(ssize_t) 3148 GetPixelPacketIntensity(color_2); 3149 return((int) intensity); 3150} 3151 3152#if defined(__cplusplus) || defined(c_plusplus) 3153} 3154#endif 3155 3156static MagickBooleanType SetGrayscaleImage(Image *image) 3157{ 3158 CacheView 3159 *image_view; 3160 3161 ExceptionInfo 3162 *exception; 3163 3164 MagickBooleanType 3165 status; 3166 3167 PixelPacket 3168 *colormap; 3169 3170 register ssize_t 3171 i; 3172 3173 ssize_t 3174 *colormap_index, 3175 j, 3176 y; 3177 3178 assert(image != (Image *) NULL); 3179 assert(image->signature == MagickSignature); 3180 if (image->type != GrayscaleType) 3181 (void) TransformImageColorspace(image,GRAYColorspace); 3182 colormap_index=(ssize_t *) AcquireQuantumMemory(MaxMap+1, 3183 sizeof(*colormap_index)); 3184 if (colormap_index == (ssize_t *) NULL) 3185 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 3186 image->filename); 3187 if (image->storage_class != PseudoClass) 3188 { 3189 ExceptionInfo 3190 *exception; 3191 3192 for (i=0; i <= (ssize_t) MaxMap; i++) 3193 colormap_index[i]=(-1); 3194 if (AcquireImageColormap(image,MaxMap+1) == MagickFalse) 3195 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 3196 image->filename); 3197 image->colors=0; 3198 status=MagickTrue; 3199 exception=(&image->exception); 3200 image_view=AcquireCacheView(image); 3201#if defined(MAGICKCORE_OPENMP_SUPPORT) 3202 #pragma omp parallel for schedule(dynamic,4) shared(status) 3203#endif 3204 for (y=0; y < (ssize_t) image->rows; y++) 3205 { 3206 register Quantum 3207 *restrict q; 3208 3209 register ssize_t 3210 x; 3211 3212 if (status == MagickFalse) 3213 continue; 3214 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1, 3215 exception); 3216 if (q == (const Quantum *) NULL) 3217 { 3218 status=MagickFalse; 3219 continue; 3220 } 3221 for (x=0; x < (ssize_t) image->columns; x++) 3222 { 3223 register size_t 3224 intensity; 3225 3226 intensity=ScaleQuantumToMap(GetPixelRed(image,q)); 3227 if (colormap_index[intensity] < 0) 3228 { 3229#if defined(MAGICKCORE_OPENMP_SUPPORT) 3230 #pragma omp critical (MagickCore_SetGrayscaleImage) 3231#endif 3232 if (colormap_index[intensity] < 0) 3233 { 3234 colormap_index[intensity]=(ssize_t) image->colors; 3235 image->colormap[image->colors].red=GetPixelRed(image,q); 3236 image->colormap[image->colors].green=GetPixelGreen(image,q); 3237 image->colormap[image->colors].blue=GetPixelBlue(image,q); 3238 image->colors++; 3239 } 3240 } 3241 SetPixelIndex(image,(Quantum) 3242 colormap_index[intensity],q); 3243 q+=GetPixelChannels(image); 3244 } 3245 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) 3246 status=MagickFalse; 3247 } 3248 image_view=DestroyCacheView(image_view); 3249 } 3250 for (i=0; i < (ssize_t) image->colors; i++) 3251 image->colormap[i].alpha=(unsigned short) i; 3252 qsort((void *) image->colormap,image->colors,sizeof(PixelPacket), 3253 IntensityCompare); 3254 colormap=(PixelPacket *) AcquireQuantumMemory(image->colors, 3255 sizeof(*colormap)); 3256 if (colormap == (PixelPacket *) NULL) 3257 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 3258 image->filename); 3259 j=0; 3260 colormap[j]=image->colormap[0]; 3261 for (i=0; i < (ssize_t) image->colors; i++) 3262 { 3263 if (IsPixelPacketEquivalent(&colormap[j],&image->colormap[i]) == MagickFalse) 3264 { 3265 j++; 3266 colormap[j]=image->colormap[i]; 3267 } 3268 colormap_index[(ssize_t) image->colormap[i].alpha]=j; 3269 } 3270 image->colors=(size_t) (j+1); 3271 image->colormap=(PixelPacket *) RelinquishMagickMemory(image->colormap); 3272 image->colormap=colormap; 3273 status=MagickTrue; 3274 exception=(&image->exception); 3275 image_view=AcquireCacheView(image); 3276#if defined(MAGICKCORE_OPENMP_SUPPORT) 3277 #pragma omp parallel for schedule(dynamic,4) shared(status) 3278#endif 3279 for (y=0; y < (ssize_t) image->rows; y++) 3280 { 3281 register Quantum 3282 *restrict q; 3283 3284 register ssize_t 3285 x; 3286 3287 if (status == MagickFalse) 3288 continue; 3289 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception); 3290 if (q == (const Quantum *) NULL) 3291 { 3292 status=MagickFalse; 3293 continue; 3294 } 3295 for (x=0; x < (ssize_t) image->columns; x++) 3296 { 3297 SetPixelIndex(image,(Quantum) colormap_index[ScaleQuantumToMap( 3298 GetPixelIndex(image,q))],q); 3299 q+=GetPixelChannels(image); 3300 } 3301 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) 3302 status=MagickFalse; 3303 } 3304 image_view=DestroyCacheView(image_view); 3305 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index); 3306 image->type=GrayscaleType; 3307 if (IsImageMonochrome(image,&image->exception) != MagickFalse) 3308 image->type=BilevelType; 3309 return(status); 3310} 3311