1 /* 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3 % % 4 % % 5 % % 6 % H H IIIII SSSSS TTTTT OOO GGGG RRRR AAA M M % 7 % H H I SS T O O G R R A A MM MM % 8 % HHHHH I SSS T O O G GG RRRR AAAAA M M M % 9 % H H I SS T O O G G R R A A M M % 10 % H H IIIII SSSSS T OOO GGG R R A A M M % 11 % % 12 % % 13 % MagickCore Histogram Methods % 14 % % 15 % Software Design % 16 % Anthony Thyssen % 17 % Fred Weinhaus % 18 % August 2009 % 19 % % 20 % % 21 % Copyright 1999-2016 ImageMagick Studio LLC, a non-profit organization % 22 % dedicated to making software imaging solutions freely available. % 23 % % 24 % You may not use this file except in compliance with the License. You may % 25 % obtain a copy of the License at % 26 % % 27 % http://www.imagemagick.org/script/license.php % 28 % % 29 % Unless required by applicable law or agreed to in writing, software % 30 % distributed under the License is distributed on an "AS IS" BASIS, % 31 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. % 32 % See the License for the specific language governing permissions and % 33 % limitations under the License. % 34 % % 35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 36 % 37 % 38 */ 39 40 /* 42 Include declarations. 43 */ 44 #include "MagickCore/studio.h" 45 #include "MagickCore/cache-view.h" 46 #include "MagickCore/color-private.h" 47 #include "MagickCore/enhance.h" 48 #include "MagickCore/exception.h" 49 #include "MagickCore/exception-private.h" 50 #include "MagickCore/histogram.h" 51 #include "MagickCore/image.h" 52 #include "MagickCore/linked-list.h" 53 #include "MagickCore/list.h" 54 #include "MagickCore/memory_.h" 55 #include "MagickCore/monitor-private.h" 56 #include "MagickCore/pixel-accessor.h" 57 #include "MagickCore/prepress.h" 58 #include "MagickCore/quantize.h" 59 #include "MagickCore/registry.h" 60 #include "MagickCore/semaphore.h" 61 #include "MagickCore/splay-tree.h" 62 #include "MagickCore/statistic.h" 63 #include "MagickCore/string_.h" 64 65 /* 67 Define declarations. 68 */ 69 #define MaxTreeDepth 8 70 #define NodesInAList 1536 71 72 /* 74 Typedef declarations. 75 */ 76 typedef struct _NodeInfo 77 { 78 struct _NodeInfo 79 *child[16]; 80 81 PixelInfo 82 *list; 83 84 MagickSizeType 85 number_unique; 86 87 size_t 88 level; 89 } NodeInfo; 90 91 typedef struct _Nodes 92 { 93 NodeInfo 94 nodes[NodesInAList]; 95 96 struct _Nodes 97 *next; 98 } Nodes; 99 100 typedef struct _CubeInfo 101 { 102 NodeInfo 103 *root; 104 105 ssize_t 106 x; 107 108 MagickOffsetType 109 progress; 110 111 size_t 112 colors, 113 free_nodes; 114 115 NodeInfo 116 *node_info; 117 118 Nodes 119 *node_queue; 120 } CubeInfo; 121 122 /* 124 Forward declarations. 125 */ 126 static CubeInfo 127 *GetCubeInfo(void); 128 129 static NodeInfo 130 *GetNodeInfo(CubeInfo *,const size_t); 131 132 static void 133 DestroyColorCube(const Image *,NodeInfo *); 134 135 /* 137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 138 % % 139 % % 140 % % 141 + C l a s s i f y I m a g e C o l o r s % 142 % % 143 % % 144 % % 145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 146 % 147 % ClassifyImageColors() builds a populated CubeInfo tree for the specified 148 % image. The returned tree should be deallocated using DestroyCubeInfo() 149 % once it is no longer needed. 150 % 151 % The format of the ClassifyImageColors() method is: 152 % 153 % CubeInfo *ClassifyImageColors(const Image *image, 154 % ExceptionInfo *exception) 155 % 156 % A description of each parameter follows. 157 % 158 % o image: the image. 159 % 160 % o exception: return any errors or warnings in this structure. 161 % 162 */ 163 164 static inline size_t ColorToNodeId(const Image *image, 165 const PixelInfo *pixel,size_t index) 166 { 167 size_t 168 id; 169 170 id=(size_t) ( 171 ((ScaleQuantumToChar(ClampToQuantum(pixel->red)) >> index) & 0x01) | 172 ((ScaleQuantumToChar(ClampToQuantum(pixel->green)) >> index) & 0x01) << 1 | 173 ((ScaleQuantumToChar(ClampToQuantum(pixel->blue)) >> index) & 0x01) << 2); 174 if (image->alpha_trait != UndefinedPixelTrait) 175 id|=((ScaleQuantumToChar(ClampToQuantum(pixel->alpha)) >> index) & 176 0x01) << 3; 177 return(id); 178 } 179 180 static CubeInfo *ClassifyImageColors(const Image *image, 181 ExceptionInfo *exception) 182 { 183 #define EvaluateImageTag " Compute image colors... " 184 185 CacheView 186 *image_view; 187 188 CubeInfo 189 *cube_info; 190 191 MagickBooleanType 192 proceed; 193 194 PixelInfo 195 pixel, 196 target; 197 198 NodeInfo 199 *node_info; 200 201 register const Quantum 202 *p; 203 204 register size_t 205 id, 206 index, 207 level; 208 209 register ssize_t 210 i, 211 x; 212 213 ssize_t 214 y; 215 216 /* 217 Initialize color description tree. 218 */ 219 assert(image != (const Image *) NULL); 220 assert(image->signature == MagickCoreSignature); 221 if (image->debug != MagickFalse) 222 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 223 cube_info=GetCubeInfo(); 224 if (cube_info == (CubeInfo *) NULL) 225 { 226 (void) ThrowMagickException(exception,GetMagickModule(), 227 ResourceLimitError,"MemoryAllocationFailed","`%s'",image->filename); 228 return(cube_info); 229 } 230 GetPixelInfo(image,&pixel); 231 GetPixelInfo(image,&target); 232 image_view=AcquireVirtualCacheView(image,exception); 233 for (y=0; y < (ssize_t) image->rows; y++) 234 { 235 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception); 236 if (p == (const Quantum *) NULL) 237 break; 238 for (x=0; x < (ssize_t) image->columns; x++) 239 { 240 /* 241 Start at the root and proceed level by level. 242 */ 243 node_info=cube_info->root; 244 index=MaxTreeDepth-1; 245 for (level=1; level < MaxTreeDepth; level++) 246 { 247 GetPixelInfoPixel(image,p,&pixel); 248 id=ColorToNodeId(image,&pixel,index); 249 if (node_info->child[id] == (NodeInfo *) NULL) 250 { 251 node_info->child[id]=GetNodeInfo(cube_info,level); 252 if (node_info->child[id] == (NodeInfo *) NULL) 253 { 254 (void) ThrowMagickException(exception,GetMagickModule(), 255 ResourceLimitError,"MemoryAllocationFailed","`%s'", 256 image->filename); 257 return(0); 258 } 259 } 260 node_info=node_info->child[id]; 261 index--; 262 } 263 for (i=0; i < (ssize_t) node_info->number_unique; i++) 264 { 265 target=node_info->list[i]; 266 if (IsPixelInfoEquivalent(&pixel,&target) != MagickFalse) 267 break; 268 } 269 if (i < (ssize_t) node_info->number_unique) 270 node_info->list[i].count++; 271 else 272 { 273 if (node_info->number_unique == 0) 274 node_info->list=(PixelInfo *) AcquireMagickMemory( 275 sizeof(*node_info->list)); 276 else 277 node_info->list=(PixelInfo *) ResizeQuantumMemory(node_info->list, 278 (size_t) (i+1),sizeof(*node_info->list)); 279 if (node_info->list == (PixelInfo *) NULL) 280 { 281 (void) ThrowMagickException(exception,GetMagickModule(), 282 ResourceLimitError,"MemoryAllocationFailed","`%s'", 283 image->filename); 284 return(0); 285 } 286 node_info->list[i]=pixel; 287 node_info->list[i].red=(double) GetPixelRed(image,p); 288 node_info->list[i].green=(double) GetPixelGreen(image,p); 289 node_info->list[i].blue=(double) GetPixelBlue(image,p); 290 if (image->colorspace == CMYKColorspace) 291 node_info->list[i].black=(double) GetPixelBlack(image,p); 292 node_info->list[i].alpha=(double) GetPixelAlpha(image,p); 293 node_info->list[i].count=1; 294 node_info->number_unique++; 295 cube_info->colors++; 296 } 297 p+=GetPixelChannels(image); 298 } 299 proceed=SetImageProgress(image,EvaluateImageTag,(MagickOffsetType) y, 300 image->rows); 301 if (proceed == MagickFalse) 302 break; 303 } 304 image_view=DestroyCacheView(image_view); 305 return(cube_info); 306 } 307 308 /* 310 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 311 % % 312 % % 313 % % 314 + D e f i n e I m a g e H i s t o g r a m % 315 % % 316 % % 317 % % 318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 319 % 320 % DefineImageHistogram() traverses the color cube tree and notes each colormap 321 % entry. A colormap entry is any node in the color cube tree where the 322 % of unique colors is not zero. 323 % 324 % The format of the DefineImageHistogram method is: 325 % 326 % DefineImageHistogram(const Image *image,NodeInfo *node_info, 327 % PixelInfo **unique_colors) 328 % 329 % A description of each parameter follows. 330 % 331 % o image: the image. 332 % 333 % o node_info: the address of a structure of type NodeInfo which points to a 334 % node in the color cube tree that is to be pruned. 335 % 336 % o histogram: the image histogram. 337 % 338 */ 339 static void DefineImageHistogram(const Image *image,NodeInfo *node_info, 340 PixelInfo **histogram) 341 { 342 register ssize_t 343 i; 344 345 size_t 346 number_children; 347 348 /* 349 Traverse any children. 350 */ 351 number_children=image->alpha_trait == UndefinedPixelTrait ? 8UL : 16UL; 352 for (i=0; i < (ssize_t) number_children; i++) 353 if (node_info->child[i] != (NodeInfo *) NULL) 354 DefineImageHistogram(image,node_info->child[i],histogram); 355 if (node_info->level == (MaxTreeDepth-1)) 356 { 357 register PixelInfo 358 *p; 359 360 p=node_info->list; 361 for (i=0; i < (ssize_t) node_info->number_unique; i++) 362 { 363 **histogram=(*p); 364 (*histogram)++; 365 p++; 366 } 367 } 368 } 369 370 /* 372 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 373 % % 374 % % 375 % % 376 + D e s t r o y C u b e I n f o % 377 % % 378 % % 379 % % 380 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 381 % 382 % DestroyCubeInfo() deallocates memory associated with a CubeInfo structure. 383 % 384 % The format of the DestroyCubeInfo method is: 385 % 386 % DestroyCubeInfo(const Image *image,CubeInfo *cube_info) 387 % 388 % A description of each parameter follows: 389 % 390 % o image: the image. 391 % 392 % o cube_info: the address of a structure of type CubeInfo. 393 % 394 */ 395 static CubeInfo *DestroyCubeInfo(const Image *image,CubeInfo *cube_info) 396 { 397 register Nodes 398 *nodes; 399 400 /* 401 Release color cube tree storage. 402 */ 403 DestroyColorCube(image,cube_info->root); 404 do 405 { 406 nodes=cube_info->node_queue->next; 407 cube_info->node_queue=(Nodes *) 408 RelinquishMagickMemory(cube_info->node_queue); 409 cube_info->node_queue=nodes; 410 } while (cube_info->node_queue != (Nodes *) NULL); 411 return((CubeInfo *) RelinquishMagickMemory(cube_info)); 412 } 413 414 /* 416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 417 % % 418 % % 419 % % 420 + D e s t r o y C o l o r C u b e % 421 % % 422 % % 423 % % 424 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 425 % 426 % DestroyColorCube() traverses the color cube tree and frees the list of 427 % unique colors. 428 % 429 % The format of the DestroyColorCube method is: 430 % 431 % void DestroyColorCube(const Image *image,const NodeInfo *node_info) 432 % 433 % A description of each parameter follows. 434 % 435 % o image: the image. 436 % 437 % o node_info: the address of a structure of type NodeInfo which points to a 438 % node in the color cube tree that is to be pruned. 439 % 440 */ 441 static void DestroyColorCube(const Image *image,NodeInfo *node_info) 442 { 443 register ssize_t 444 i; 445 446 size_t 447 number_children; 448 449 /* 450 Traverse any children. 451 */ 452 number_children=image->alpha_trait == UndefinedPixelTrait ? 8UL : 16UL; 453 for (i=0; i < (ssize_t) number_children; i++) 454 if (node_info->child[i] != (NodeInfo *) NULL) 455 DestroyColorCube(image,node_info->child[i]); 456 if (node_info->list != (PixelInfo *) NULL) 457 node_info->list=(PixelInfo *) RelinquishMagickMemory(node_info->list); 458 } 459 460 /* 462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 463 % % 464 % % 465 % % 466 + G e t C u b e I n f o % 467 % % 468 % % 469 % % 470 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 471 % 472 % GetCubeInfo() initializes the CubeInfo data structure. 473 % 474 % The format of the GetCubeInfo method is: 475 % 476 % cube_info=GetCubeInfo() 477 % 478 % A description of each parameter follows. 479 % 480 % o cube_info: A pointer to the Cube structure. 481 % 482 */ 483 static CubeInfo *GetCubeInfo(void) 484 { 485 CubeInfo 486 *cube_info; 487 488 /* 489 Initialize tree to describe color cube. 490 */ 491 cube_info=(CubeInfo *) AcquireMagickMemory(sizeof(*cube_info)); 492 if (cube_info == (CubeInfo *) NULL) 493 return((CubeInfo *) NULL); 494 (void) ResetMagickMemory(cube_info,0,sizeof(*cube_info)); 495 /* 496 Initialize root node. 497 */ 498 cube_info->root=GetNodeInfo(cube_info,0); 499 if (cube_info->root == (NodeInfo *) NULL) 500 return((CubeInfo *) NULL); 501 return(cube_info); 502 } 503 504 /* 506 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 507 % % 508 % % 509 % % 510 % G e t I m a g e H i s t o g r a m % 511 % % 512 % % 513 % % 514 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 515 % 516 % GetImageHistogram() returns the unique colors in an image. 517 % 518 % The format of the GetImageHistogram method is: 519 % 520 % size_t GetImageHistogram(const Image *image, 521 % size_t *number_colors,ExceptionInfo *exception) 522 % 523 % A description of each parameter follows. 524 % 525 % o image: the image. 526 % 527 % o file: Write a histogram of the color distribution to this file handle. 528 % 529 % o exception: return any errors or warnings in this structure. 530 % 531 */ 532 MagickExport PixelInfo *GetImageHistogram(const Image *image, 533 size_t *number_colors,ExceptionInfo *exception) 534 { 535 PixelInfo 536 *histogram; 537 538 CubeInfo 539 *cube_info; 540 541 *number_colors=0; 542 histogram=(PixelInfo *) NULL; 543 cube_info=ClassifyImageColors(image,exception); 544 if (cube_info != (CubeInfo *) NULL) 545 { 546 histogram=(PixelInfo *) AcquireQuantumMemory((size_t) cube_info->colors, 547 sizeof(*histogram)); 548 if (histogram == (PixelInfo *) NULL) 549 (void) ThrowMagickException(exception,GetMagickModule(), 550 ResourceLimitError,"MemoryAllocationFailed","`%s'",image->filename); 551 else 552 { 553 PixelInfo 554 *root; 555 556 *number_colors=cube_info->colors; 557 root=histogram; 558 DefineImageHistogram(image,cube_info->root,&root); 559 } 560 } 561 cube_info=DestroyCubeInfo(image,cube_info); 562 return(histogram); 563 } 564 565 /* 567 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 568 % % 569 % % 570 % % 571 + G e t N o d e I n f o % 572 % % 573 % % 574 % % 575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 576 % 577 % GetNodeInfo() allocates memory for a new node in the color cube tree and 578 % presets all fields to zero. 579 % 580 % The format of the GetNodeInfo method is: 581 % 582 % NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t level) 583 % 584 % A description of each parameter follows. 585 % 586 % o cube_info: A pointer to the CubeInfo structure. 587 % 588 % o level: Specifies the level in the storage_class the node resides. 589 % 590 */ 591 static NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t level) 592 { 593 NodeInfo 594 *node_info; 595 596 if (cube_info->free_nodes == 0) 597 { 598 Nodes 599 *nodes; 600 601 /* 602 Allocate a new nodes of nodes. 603 */ 604 nodes=(Nodes *) AcquireMagickMemory(sizeof(*nodes)); 605 if (nodes == (Nodes *) NULL) 606 return((NodeInfo *) NULL); 607 nodes->next=cube_info->node_queue; 608 cube_info->node_queue=nodes; 609 cube_info->node_info=nodes->nodes; 610 cube_info->free_nodes=NodesInAList; 611 } 612 cube_info->free_nodes--; 613 node_info=cube_info->node_info++; 614 (void) ResetMagickMemory(node_info,0,sizeof(*node_info)); 615 node_info->level=level; 616 return(node_info); 617 } 618 619 /* 621 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 622 % % 623 % % 624 % % 625 % I d e n t i f y P a l e t t e I m a g e % 626 % % 627 % % 628 % % 629 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 630 % 631 % IdentifyPaletteImage() returns MagickTrue if the image has 256 unique colors 632 % or less. 633 % 634 % The format of the IdentifyPaletteImage method is: 635 % 636 % MagickBooleanType IdentifyPaletteImage(const Image *image, 637 % ExceptionInfo *exception) 638 % 639 % A description of each parameter follows. 640 % 641 % o image: the image. 642 % 643 % o exception: return any errors or warnings in this structure. 644 % 645 */ 646 647 static MagickBooleanType CheckImageColors(const Image *image, 648 ExceptionInfo *exception,size_t max_colors) 649 { 650 CacheView 651 *image_view; 652 653 CubeInfo 654 *cube_info; 655 656 PixelInfo 657 pixel, 658 target; 659 660 register const Quantum 661 *p; 662 663 register ssize_t 664 x; 665 666 register NodeInfo 667 *node_info; 668 669 register ssize_t 670 i; 671 672 size_t 673 id, 674 index, 675 level; 676 677 ssize_t 678 y; 679 680 if (image->storage_class == PseudoClass) 681 return((image->colors <= max_colors) ? MagickTrue : MagickFalse); 682 /* 683 Initialize color description tree. 684 */ 685 cube_info=GetCubeInfo(); 686 if (cube_info == (CubeInfo *) NULL) 687 { 688 (void) ThrowMagickException(exception,GetMagickModule(), 689 ResourceLimitError,"MemoryAllocationFailed","`%s'",image->filename); 690 return(MagickFalse); 691 } 692 GetPixelInfo(image,&pixel); 693 GetPixelInfo(image,&target); 694 image_view=AcquireVirtualCacheView(image,exception); 695 for (y=0; y < (ssize_t) image->rows; y++) 696 { 697 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception); 698 if (p == (const Quantum *) NULL) 699 break; 700 for (x=0; x < (ssize_t) image->columns; x++) 701 { 702 /* 703 Start at the root and proceed level by level. 704 */ 705 node_info=cube_info->root; 706 index=MaxTreeDepth-1; 707 for (level=1; level < MaxTreeDepth; level++) 708 { 709 GetPixelInfoPixel(image,p,&pixel); 710 id=ColorToNodeId(image,&pixel,index); 711 if (node_info->child[id] == (NodeInfo *) NULL) 712 { 713 node_info->child[id]=GetNodeInfo(cube_info,level); 714 if (node_info->child[id] == (NodeInfo *) NULL) 715 { 716 (void) ThrowMagickException(exception,GetMagickModule(), 717 ResourceLimitError,"MemoryAllocationFailed","`%s'", 718 image->filename); 719 break; 720 } 721 } 722 node_info=node_info->child[id]; 723 index--; 724 } 725 if (level < MaxTreeDepth) 726 break; 727 for (i=0; i < (ssize_t) node_info->number_unique; i++) 728 { 729 target=node_info->list[i]; 730 if (IsPixelInfoEquivalent(&pixel,&target) != MagickFalse) 731 break; 732 } 733 if (i < (ssize_t) node_info->number_unique) 734 node_info->list[i].count++; 735 else 736 { 737 /* 738 Add this unique color to the color list. 739 */ 740 if (node_info->number_unique == 0) 741 node_info->list=(PixelInfo *) AcquireMagickMemory( 742 sizeof(*node_info->list)); 743 else 744 node_info->list=(PixelInfo *) ResizeQuantumMemory(node_info->list, 745 (size_t) (i+1),sizeof(*node_info->list)); 746 if (node_info->list == (PixelInfo *) NULL) 747 { 748 (void) ThrowMagickException(exception,GetMagickModule(), 749 ResourceLimitError,"MemoryAllocationFailed","`%s'", 750 image->filename); 751 break; 752 } 753 GetPixelInfo(image,&node_info->list[i]); 754 node_info->list[i].red=(double) GetPixelRed(image,p); 755 node_info->list[i].green=(double) GetPixelGreen(image,p); 756 node_info->list[i].blue=(double) GetPixelBlue(image,p); 757 if (image->colorspace == CMYKColorspace) 758 node_info->list[i].black=(double) GetPixelBlack(image,p); 759 node_info->list[i].alpha=(double) GetPixelAlpha(image,p); 760 node_info->list[i].count=1; 761 node_info->number_unique++; 762 cube_info->colors++; 763 if (cube_info->colors > max_colors) 764 break; 765 } 766 p+=GetPixelChannels(image); 767 } 768 if (x < (ssize_t) image->columns) 769 break; 770 } 771 image_view=DestroyCacheView(image_view); 772 cube_info=DestroyCubeInfo(image,cube_info); 773 return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue); 774 } 775 776 MagickExport MagickBooleanType IdentifyPaletteImage(const Image *image, 777 ExceptionInfo *exception) 778 { 779 assert(image != (Image *) NULL); 780 assert(image->signature == MagickCoreSignature); 781 if (image->debug != MagickFalse) 782 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 783 return(CheckImageColors(image,exception,256)); 784 } 785 786 /* 788 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 789 % % 790 % % 791 % % 792 % I s H i s t o g r a m I m a g e % 793 % % 794 % % 795 % % 796 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 797 % 798 % IsHistogramImage() returns MagickTrue if the image has 1024 unique colors or 799 % less. 800 % 801 % The format of the IsHistogramImage method is: 802 % 803 % MagickBooleanType IsHistogramImage(const Image *image, 804 % ExceptionInfo *exception) 805 % 806 % A description of each parameter follows. 807 % 808 % o image: the image. 809 % 810 % o exception: return any errors or warnings in this structure. 811 % 812 */ 813 MagickExport MagickBooleanType IsHistogramImage(const Image *image, 814 ExceptionInfo *exception) 815 { 816 #define MaximumUniqueColors 1024 817 818 assert(image != (Image *) NULL); 819 assert(image->signature == MagickCoreSignature); 820 if (image->debug != MagickFalse) 821 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 822 return(CheckImageColors(image,exception,MaximumUniqueColors)); 823 } 824 825 /* 827 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 828 % % 829 % % 830 % % 831 % I s P a l e t t e I m a g e % 832 % % 833 % % 834 % % 835 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 836 % 837 % IsPaletteImage() returns MagickTrue if the image is PseudoClass and has 256 838 % unique colors or less. 839 % 840 % The format of the IsPaletteImage method is: 841 % 842 % MagickBooleanType IsPaletteImage(const Image *image) 843 % 844 % A description of each parameter follows. 845 % 846 % o image: the image. 847 % 848 */ 849 MagickExport MagickBooleanType IsPaletteImage(const Image *image) 850 { 851 assert(image != (Image *) NULL); 852 assert(image->signature == MagickCoreSignature); 853 if (image->debug != MagickFalse) 854 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 855 if (image->storage_class != PseudoClass) 856 return(MagickFalse); 857 return((image->colors <= 256) ? MagickTrue : MagickFalse); 858 } 859 860 /* 862 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 863 % % 864 % % 865 % % 866 % M i n M a x S t r e t c h I m a g e % 867 % % 868 % % 869 % % 870 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 871 % 872 % MinMaxStretchImage() uses the exact minimum and maximum values found in 873 % each of the channels given, as the BlackPoint and WhitePoint to linearly 874 % stretch the colors (and histogram) of the image. The stretch points are 875 % also moved further inward by the adjustment values given. 876 % 877 % If the adjustment values are both zero this function is equivalent to a 878 % perfect normalization (or autolevel) of the image. 879 % 880 % Each channel is stretched independantally of each other (producing color 881 % distortion) unless the special 'SyncChannels' flag is also provided in the 882 % channels setting. If this flag is present the minimum and maximum point 883 % will be extracted from all the given channels, and those channels will be 884 % stretched by exactly the same amount (preventing color distortion). 885 % 886 % In the special case that only ONE value is found in a channel of the image 887 % that value is not stretched, that value is left as is. 888 % 889 % The 'SyncChannels' is turned on in the 'DefaultChannels' setting by 890 % default. 891 % 892 % The format of the MinMaxStretchImage method is: 893 % 894 % MagickBooleanType MinMaxStretchImage(Image *image,const double black, 895 % const double white,const double gamma,ExceptionInfo *exception) 896 % 897 % A description of each parameter follows: 898 % 899 % o image: The image to auto-level 900 % 901 % o black, white: move the black / white point inward from the minimum and 902 % maximum points by this color value. 903 % 904 % o gamma: the gamma. 905 % 906 % o exception: return any errors or warnings in this structure. 907 % 908 */ 909 MagickExport MagickBooleanType MinMaxStretchImage(Image *image, 910 const double black,const double white,const double gamma, 911 ExceptionInfo *exception) 912 { 913 double 914 min, 915 max; 916 917 register ssize_t 918 i; 919 920 MagickStatusType 921 status; 922 923 status=MagickTrue; 924 if (image->channel_mask == DefaultChannels) 925 { 926 /* 927 Auto-level all channels equally. 928 */ 929 (void) GetImageRange(image,&min,&max,exception); 930 min+=black; 931 max-=white; 932 if (fabs(min-max) >= MagickEpsilon) 933 status&=LevelImage(image,min,max,gamma,exception); 934 return(status != 0 ? MagickTrue : MagickFalse); 935 } 936 /* 937 Auto-level each channel. 938 */ 939 for (i=0; i < (ssize_t) GetPixelChannels(image); i++) 940 { 941 ChannelType 942 channel_mask; 943 944 PixelChannel channel=GetPixelChannelChannel(image,i); 945 PixelTrait traits=GetPixelChannelTraits(image,channel); 946 if ((traits & UpdatePixelTrait) == 0) 947 continue; 948 channel_mask=SetImageChannelMask(image,(ChannelType) (1 << i)); 949 status&=GetImageRange(image,&min,&max,exception); 950 min+=black; 951 max-=white; 952 if (fabs(min-max) >= MagickEpsilon) 953 status&=LevelImage(image,min,max,gamma,exception); 954 (void) SetImageChannelMask(image,channel_mask); 955 } 956 return(status != 0 ? MagickTrue : MagickFalse); 957 } 958 959 /* 961 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 962 % % 963 % % 964 % % 965 % G e t N u m b e r C o l o r s % 966 % % 967 % % 968 % % 969 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 970 % 971 % GetNumberColors() returns the number of unique colors in an image. 972 % 973 % The format of the GetNumberColors method is: 974 % 975 % size_t GetNumberColors(const Image *image,FILE *file, 976 % ExceptionInfo *exception) 977 % 978 % A description of each parameter follows. 979 % 980 % o image: the image. 981 % 982 % o file: Write a histogram of the color distribution to this file handle. 983 % 984 % o exception: return any errors or warnings in this structure. 985 % 986 */ 987 988 #if defined(__cplusplus) || defined(c_plusplus) 989 extern "C" { 990 #endif 991 992 static int HistogramCompare(const void *x,const void *y) 993 { 994 const PixelInfo 995 *color_1, 996 *color_2; 997 998 color_1=(const PixelInfo *) x; 999 color_2=(const PixelInfo *) y; 1000 if (color_2->red != color_1->red) 1001 return((int) color_1->red-(int) color_2->red); 1002 if (color_2->green != color_1->green) 1003 return((int) color_1->green-(int) color_2->green); 1004 if (color_2->blue != color_1->blue) 1005 return((int) color_1->blue-(int) color_2->blue); 1006 return((int) color_2->count-(int) color_1->count); 1007 } 1008 1009 #if defined(__cplusplus) || defined(c_plusplus) 1010 } 1011 #endif 1012 1013 MagickExport size_t GetNumberColors(const Image *image,FILE *file, 1014 ExceptionInfo *exception) 1015 { 1016 #define HistogramImageTag "Histogram/Image" 1017 1018 char 1019 color[MagickPathExtent], 1020 hex[MagickPathExtent], 1021 tuple[MagickPathExtent]; 1022 1023 PixelInfo 1024 *histogram; 1025 1026 MagickBooleanType 1027 status; 1028 1029 PixelInfo 1030 pixel; 1031 1032 register PixelInfo 1033 *p; 1034 1035 register ssize_t 1036 i; 1037 1038 size_t 1039 number_colors; 1040 1041 number_colors=0; 1042 if (file == (FILE *) NULL) 1043 { 1044 CubeInfo 1045 *cube_info; 1046 1047 cube_info=ClassifyImageColors(image,exception); 1048 if (cube_info != (CubeInfo *) NULL) 1049 number_colors=cube_info->colors; 1050 cube_info=DestroyCubeInfo(image,cube_info); 1051 return(number_colors); 1052 } 1053 histogram=GetImageHistogram(image,&number_colors,exception); 1054 if (histogram == (PixelInfo *) NULL) 1055 return(number_colors); 1056 qsort((void *) histogram,(size_t) number_colors,sizeof(*histogram), 1057 HistogramCompare); 1058 GetPixelInfo(image,&pixel); 1059 p=histogram; 1060 status=MagickTrue; 1061 for (i=0; i < (ssize_t) number_colors; i++) 1062 { 1063 pixel=(*p); 1064 (void) CopyMagickString(tuple,"(",MagickPathExtent); 1065 ConcatenateColorComponent(&pixel,RedPixelChannel,X11Compliance,tuple); 1066 (void) ConcatenateMagickString(tuple,",",MagickPathExtent); 1067 ConcatenateColorComponent(&pixel,GreenPixelChannel,X11Compliance,tuple); 1068 (void) ConcatenateMagickString(tuple,",",MagickPathExtent); 1069 ConcatenateColorComponent(&pixel,BluePixelChannel,X11Compliance,tuple); 1070 if (pixel.colorspace == CMYKColorspace) 1071 { 1072 (void) ConcatenateMagickString(tuple,",",MagickPathExtent); 1073 ConcatenateColorComponent(&pixel,BlackPixelChannel,X11Compliance, 1074 tuple); 1075 } 1076 if (pixel.alpha_trait != UndefinedPixelTrait) 1077 { 1078 (void) ConcatenateMagickString(tuple,",",MagickPathExtent); 1079 ConcatenateColorComponent(&pixel,AlphaPixelChannel,X11Compliance, 1080 tuple); 1081 } 1082 (void) ConcatenateMagickString(tuple,")",MagickPathExtent); 1083 (void) QueryColorname(image,&pixel,SVGCompliance,color,exception); 1084 GetColorTuple(&pixel,MagickTrue,hex); 1085 (void) FormatLocaleFile(file,"%10.20g",(double) ((MagickOffsetType) 1086 p->count)); 1087 (void) FormatLocaleFile(file,": %s %s %s\n",tuple,hex,color); 1088 if (image->progress_monitor != (MagickProgressMonitor) NULL) 1089 { 1090 MagickBooleanType 1091 proceed; 1092 1093 proceed=SetImageProgress(image,HistogramImageTag,(MagickOffsetType) i, 1094 number_colors); 1095 if (proceed == MagickFalse) 1096 status=MagickFalse; 1097 } 1098 p++; 1099 } 1100 (void) fflush(file); 1101 histogram=(PixelInfo *) RelinquishMagickMemory(histogram); 1102 if (status == MagickFalse) 1103 return(0); 1104 return(number_colors); 1105 } 1106 1107 /* 1109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1110 % % 1111 % % 1112 % % 1113 % U n i q u e I m a g e C o l o r s % 1114 % % 1115 % % 1116 % % 1117 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1118 % 1119 % UniqueImageColors() returns the unique colors of an image. 1120 % 1121 % The format of the UniqueImageColors method is: 1122 % 1123 % Image *UniqueImageColors(const Image *image,ExceptionInfo *exception) 1124 % 1125 % A description of each parameter follows. 1126 % 1127 % o image: the image. 1128 % 1129 % o exception: return any errors or warnings in this structure. 1130 % 1131 */ 1132 1133 static void UniqueColorsToImage(Image *unique_image,CacheView *unique_view, 1134 CubeInfo *cube_info,const NodeInfo *node_info,ExceptionInfo *exception) 1135 { 1136 #define UniqueColorsImageTag "UniqueColors/Image" 1137 1138 MagickBooleanType 1139 status; 1140 1141 register ssize_t 1142 i; 1143 1144 size_t 1145 number_children; 1146 1147 /* 1148 Traverse any children. 1149 */ 1150 number_children=unique_image->alpha_trait == UndefinedPixelTrait ? 8UL : 16UL; 1151 for (i=0; i < (ssize_t) number_children; i++) 1152 if (node_info->child[i] != (NodeInfo *) NULL) 1153 UniqueColorsToImage(unique_image,unique_view,cube_info, 1154 node_info->child[i],exception); 1155 if (node_info->level == (MaxTreeDepth-1)) 1156 { 1157 register PixelInfo 1158 *p; 1159 1160 register Quantum 1161 *magick_restrict q; 1162 1163 status=MagickTrue; 1164 p=node_info->list; 1165 for (i=0; i < (ssize_t) node_info->number_unique; i++) 1166 { 1167 q=QueueCacheViewAuthenticPixels(unique_view,cube_info->x,0,1,1, 1168 exception); 1169 if (q == (Quantum *) NULL) 1170 continue; 1171 SetPixelRed(unique_image,ClampToQuantum(p->red),q); 1172 SetPixelGreen(unique_image,ClampToQuantum(p->green),q); 1173 SetPixelBlue(unique_image,ClampToQuantum(p->blue),q); 1174 SetPixelAlpha(unique_image,ClampToQuantum(p->alpha),q); 1175 if (unique_image->colorspace == CMYKColorspace) 1176 SetPixelBlack(unique_image,ClampToQuantum(p->black),q); 1177 if (SyncCacheViewAuthenticPixels(unique_view,exception) == MagickFalse) 1178 break; 1179 cube_info->x++; 1180 p++; 1181 } 1182 if (unique_image->progress_monitor != (MagickProgressMonitor) NULL) 1183 { 1184 MagickBooleanType 1185 proceed; 1186 1187 proceed=SetImageProgress(unique_image,UniqueColorsImageTag, 1188 cube_info->progress,cube_info->colors); 1189 if (proceed == MagickFalse) 1190 status=MagickFalse; 1191 } 1192 cube_info->progress++; 1193 if (status == MagickFalse) 1194 return; 1195 } 1196 } 1197 1198 MagickExport Image *UniqueImageColors(const Image *image, 1199 ExceptionInfo *exception) 1200 { 1201 CacheView 1202 *unique_view; 1203 1204 CubeInfo 1205 *cube_info; 1206 1207 Image 1208 *unique_image; 1209 1210 cube_info=ClassifyImageColors(image,exception); 1211 if (cube_info == (CubeInfo *) NULL) 1212 return((Image *) NULL); 1213 unique_image=CloneImage(image,cube_info->colors,1,MagickTrue,exception); 1214 if (unique_image == (Image *) NULL) 1215 return(unique_image); 1216 if (SetImageStorageClass(unique_image,DirectClass,exception) == MagickFalse) 1217 { 1218 unique_image=DestroyImage(unique_image); 1219 return((Image *) NULL); 1220 } 1221 unique_view=AcquireAuthenticCacheView(unique_image,exception); 1222 UniqueColorsToImage(unique_image,unique_view,cube_info,cube_info->root, 1223 exception); 1224 unique_view=DestroyCacheView(unique_view); 1225 cube_info=DestroyCubeInfo(image,cube_info); 1226 return(unique_image); 1227 } 1228
