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