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