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