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