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