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