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