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