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 */
73 typedef 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
88 typedef struct _Nodes
89 {
90 NodeInfo
91 nodes[NodesInAList];
92
93 struct _Nodes
94 *next;
95 } Nodes;
96
97 typedef 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 */
122 static CubeInfo
123 *GetCubeInfo(void);
124
125 static NodeInfo
126 *GetNodeInfo(CubeInfo *,const size_t);
127
128 static 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
ColorToNodeId(const Image * image,const PixelInfo * pixel,size_t index)159 static 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
ClassifyImageColors(const Image * image,ExceptionInfo * exception)175 static 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 */
DefineImageHistogram(const Image * image,NodeInfo * node_info,PixelInfo ** histogram)333 static 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 */
DestroyCubeInfo(const Image * image,CubeInfo * cube_info)388 static 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 */
DestroyColorCube(const Image * image,NodeInfo * node_info)433 static 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 */
GetCubeInfo(void)474 static 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 */
GetImageHistogram(const Image * image,size_t * number_colors,ExceptionInfo * exception)522 MagickExport 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 */
GetNodeInfo(CubeInfo * cube_info,const size_t level)580 static 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
CheckImageColors(const Image * image,ExceptionInfo * exception,size_t max_colors)635 static 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
IdentifyPaletteImage(const Image * image,ExceptionInfo * exception)764 MagickExport 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 */
IsHistogramImage(const Image * image,ExceptionInfo * exception)800 MagickExport 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 */
IsPaletteImage(const Image * image)835 MagickExport 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 */
MinMaxStretchImage(Image * image,const double black,const double white,const double gamma,ExceptionInfo * exception)894 MagickExport 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)
973 extern "C" {
974 #endif
975
HistogramCompare(const void * x,const void * y)976 static 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
GetNumberColors(const Image * image,FILE * file,ExceptionInfo * exception)997 MagickExport 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
UniqueColorsToImage(Image * unique_image,CacheView * unique_view,CubeInfo * cube_info,const NodeInfo * node_info,ExceptionInfo * exception)1116 static 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
UniqueImageColors(const Image * image,ExceptionInfo * exception)1181 MagickExport 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