MagickCore  7.1.1-43
Convert, Edit, Or Compose Bitmap Images
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 "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 */
74 typedef struct _HNodeInfo
75 {
76  struct _HNodeInfo
77  *child[16];
78 
79  PixelInfo
80  *list;
81 
82  size_t
83  extent;
84 
85  MagickSizeType
86  number_unique;
87 
88  size_t
89  level;
90 } HNodeInfo;
91 
92 typedef struct _HNodes
93 {
94  HNodeInfo
95  nodes[HNodesInAList];
96 
97  struct _HNodes
98  *next;
99 } HNodes;
100 
101 typedef 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 */
126 static HCubeInfo
127  *GetHCubeInfo(void);
128 
129 static HNodeInfo
130  *GetHNodeInfo(HCubeInfo *,const size_t);
131 
132 static 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 
163 static 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 
178 static 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 
206 static HCubeInfo *ClassifyImageColors(const Image *image,
207  ExceptionInfo *exception)
208 {
209 #define EvaluateImageTag " Compute image colors... "
210 
211  CacheView
212  *image_view;
213 
214  HCubeInfo
215  *cube_info;
216 
217  MagickBooleanType
218  proceed;
219 
220  PixelInfo
221  pixel;
222 
223  HNodeInfo
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+=(ptrdiff_t) 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 */
366 static 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  {
384  PixelInfo
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 */
421 static 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 */
466 static 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 */
507 static HCubeInfo *GetHCubeInfo(void)
508 {
509  HCubeInfo
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 */
555 MagickExport PixelInfo *GetImageHistogram(const Image *image,
556  size_t *number_colors,ExceptionInfo *exception)
557 {
558  PixelInfo
559  *histogram;
560 
561  HCubeInfo
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  {
576  PixelInfo
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 */
613 static HNodeInfo *GetHNodeInfo(HCubeInfo *cube_info,const size_t level)
614 {
615  HNodeInfo
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 
670 static MagickBooleanType CheckImageColors(const Image *image,
671  const size_t max_colors,ExceptionInfo *exception)
672 {
673  CacheView
674  *image_view;
675 
676  const Quantum
677  *p;
678 
679  HCubeInfo
680  *cube_info;
681 
682  HNodeInfo
683  *node_info;
684 
685  PixelInfo
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+=(ptrdiff_t) 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 
797 MagickExport 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 */
833 MagickExport 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 */
868 MagickExport 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 */
927 MagickExport 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)
1006 extern "C" {
1007 #endif
1008 
1009 static 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 
1030 MagickExport 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 
1152 static 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 
1217 MagickExport 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 }
_HNodeInfo
Definition: histogram.c:74
_CacheView
Definition: cache-view.c:65
_Image
Definition: image.h:131
_PixelInfo
Definition: pixel.h:181
_ExceptionInfo
Definition: exception.h:101
_HNodes
Definition: histogram.c:92
_HCubeInfo
Definition: histogram.c:101