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