43 #include "magick/studio.h"
44 #include "magick/cache-view.h"
45 #include "magick/color-private.h"
46 #include "magick/enhance.h"
47 #include "magick/exception.h"
48 #include "magick/exception-private.h"
49 #include "magick/hashmap.h"
50 #include "magick/histogram.h"
51 #include "magick/image.h"
52 #include "magick/list.h"
53 #include "magick/memory_.h"
54 #include "magick/monitor-private.h"
55 #include "magick/pixel-private.h"
56 #include "magick/prepress.h"
57 #include "magick/quantize.h"
58 #include "magick/registry.h"
59 #include "magick/semaphore.h"
60 #include "magick/splay-tree.h"
61 #include "magick/statistic.h"
62 #include "magick/string_.h"
67 #define MaxTreeDepth 8
68 #define NodesInAList 1536
129 *GetNodeInfo(
CubeInfo *,
const size_t);
162 static inline size_t ColorToNodeId(
const Image *image,
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 (image->matte != MagickFalse)
173 id|=((ScaleQuantumToChar(ClampToQuantum(pixel->opacity)) >> index) &
185 alpha=p->matte == MagickFalse ? OpaqueOpacity : p->opacity;
186 beta=q->matte == MagickFalse ? OpaqueOpacity : q->opacity;
187 if (AbsolutePixelValue(alpha-beta) >= MagickEpsilon)
189 if ((AbsolutePixelValue(alpha-TransparentOpacity) < MagickEpsilon) ||
190 (AbsolutePixelValue(beta-TransparentOpacity) < MagickEpsilon))
192 if (AbsolutePixelValue(p->red-q->red) >= MagickEpsilon)
194 if (AbsolutePixelValue(p->green-q->green) >= MagickEpsilon)
196 if (AbsolutePixelValue(p->blue-q->blue) >= MagickEpsilon)
198 if (p->colorspace == CMYKColorspace)
200 if (AbsolutePixelValue(p->index-q->index) >= MagickEpsilon)
210 #define EvaluateImageTag " Compute image colors... "
249 assert(image != (
const Image *) NULL);
250 assert(image->signature == MagickCoreSignature);
251 if (IsEventLogging() != MagickFalse)
252 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
253 cube_info=GetCubeInfo();
256 (void) ThrowMagickException(exception,GetMagickModule(),
257 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",image->filename);
260 GetMagickPixelPacket(image,&pixel);
261 GetMagickPixelPacket(image,&target);
262 image_view=AcquireVirtualCacheView(image,exception);
263 for (y=0; y < (ssize_t) image->rows; y++)
265 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
268 indexes=GetCacheViewVirtualIndexQueue(image_view);
269 for (x=0; x < (ssize_t) image->columns; x++)
274 node_info=cube_info->root;
275 index=MaxTreeDepth-1;
276 for (level=1; level < MaxTreeDepth; level++)
278 SetMagickPixelPacket(image,p,indexes+x,&pixel);
279 id=ColorToNodeId(image,&pixel,index);
280 if (node_info->child[
id] == (
NodeInfo *) NULL)
282 node_info->child[id]=GetNodeInfo(cube_info,level);
283 if (node_info->child[
id] == (
NodeInfo *) NULL)
285 (void) ThrowMagickException(exception,GetMagickModule(),
286 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",
291 node_info=node_info->child[id];
294 for (i=0; i < (ssize_t) node_info->number_unique; i++)
296 SetMagickPixelPacket(image,&node_info->list[i].pixel,
297 &node_info->list[i].index,&target);
298 if (IsMagickColorMatch(&pixel,&target) != MagickFalse)
301 if (i < (ssize_t) node_info->number_unique)
302 node_info->list[i].count++;
305 if (node_info->number_unique == 0)
308 node_info->list=(
ColorPacket *) AcquireQuantumMemory(
309 node_info->extent,
sizeof(*node_info->list));
312 if (i >= (ssize_t) node_info->extent)
314 node_info->extent<<=1;
315 node_info->list=(
ColorPacket *) ResizeQuantumMemory(
316 node_info->list,node_info->extent,
sizeof(*node_info->list));
320 (void) ThrowMagickException(exception,GetMagickModule(),
321 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",
325 node_info->list[i].pixel=(*p);
326 if ((image->colorspace == CMYKColorspace) ||
327 (image->storage_class == PseudoClass))
328 node_info->list[i].index=GetPixelIndex(indexes+x);
329 node_info->list[i].count=1;
330 node_info->number_unique++;
335 proceed=SetImageProgress(image,EvaluateImageTag,(MagickOffsetType) y,
337 if (proceed == MagickFalse)
340 image_view=DestroyCacheView(image_view);
374 static void DefineImageHistogram(
const Image *image,
NodeInfo *node_info,
386 number_children=image->matte == MagickFalse ? 8UL : 16UL;
387 for (i=0; i < (ssize_t) number_children; i++)
388 if (node_info->child[i] != (
NodeInfo *) NULL)
389 DefineImageHistogram(image,node_info->child[i],histogram);
390 if (node_info->level == (MaxTreeDepth-1))
396 for (i=0; i < (ssize_t) node_info->number_unique; i++)
398 (*histogram)->pixel=p->pixel;
399 (*histogram)->index=p->index;
400 (*histogram)->count=p->count;
439 DestroyColorCube(image,cube_info->root);
442 nodes=cube_info->node_queue->next;
443 cube_info->node_queue=(
Nodes *)
444 RelinquishMagickMemory(cube_info->node_queue);
445 cube_info->node_queue=nodes;
446 }
while (cube_info->node_queue != (
Nodes *) NULL);
447 return((
CubeInfo *) RelinquishMagickMemory(cube_info));
476 static void DestroyColorCube(
const Image *image,
NodeInfo *node_info)
487 number_children=image->matte == MagickFalse ? 8UL : 16UL;
488 for (i=0; i < (ssize_t) number_children; i++)
489 if (node_info->child[i] != (
NodeInfo *) NULL)
490 DestroyColorCube(image,node_info->child[i]);
492 node_info->list=(
ColorPacket *) RelinquishMagickMemory(node_info->list);
525 cube_info=(
CubeInfo *) AcquireMagickMemory(
sizeof(*cube_info));
528 (void) memset(cube_info,0,
sizeof(*cube_info));
532 cube_info->root=GetNodeInfo(cube_info,0);
533 if (cube_info->root == (
NodeInfo *) NULL)
576 cube_info=ClassifyImageColors(image,exception);
579 histogram=(
ColorPacket *) AcquireQuantumMemory((
size_t)
580 cube_info->colors+1,
sizeof(*histogram));
582 (
void) ThrowMagickException(exception,GetMagickModule(),
583 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",image->filename);
589 *number_colors=cube_info->colors;
591 DefineImageHistogram(image,cube_info->root,&root);
593 cube_info=DestroyCubeInfo(image,cube_info);
628 if (cube_info->free_nodes == 0)
636 nodes=(
Nodes *) AcquireMagickMemory(
sizeof(*nodes));
637 if (nodes == (
Nodes *) NULL)
639 nodes->next=cube_info->node_queue;
640 cube_info->node_queue=nodes;
641 cube_info->node_info=nodes->nodes;
642 cube_info->free_nodes=NodesInAList;
644 cube_info->free_nodes--;
645 node_info=cube_info->node_info++;
646 (void) memset(node_info,0,
sizeof(*node_info));
647 node_info->level=level;
678 static MagickBooleanType CheckImageColors(
const Image *image,
714 if (image->storage_class == PseudoClass)
715 return((image->colors <= max_colors) ? MagickTrue : MagickFalse);
719 cube_info=GetCubeInfo();
722 (void) ThrowMagickException(exception,GetMagickModule(),
723 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",image->filename);
726 GetMagickPixelPacket(image,&pixel);
727 GetMagickPixelPacket(image,&target);
728 image_view=AcquireVirtualCacheView(image,exception);
729 for (y=0; y < (ssize_t) image->rows; y++)
731 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
734 indexes=GetCacheViewVirtualIndexQueue(image_view);
735 if (indexes == (
const IndexPacket *) NULL)
737 for (x=0; x < (ssize_t) image->columns; x++)
742 node_info=cube_info->root;
743 index=MaxTreeDepth-1;
744 for (level=1; level < MaxTreeDepth; level++)
746 SetMagickPixelPacket(image,p,indexes+x,&pixel);
747 id=ColorToNodeId(image,&pixel,index);
748 if (node_info->child[
id] == (
NodeInfo *) NULL)
750 node_info->child[id]=GetNodeInfo(cube_info,level);
751 if (node_info->child[
id] == (
NodeInfo *) NULL)
753 (void) ThrowMagickException(exception,GetMagickModule(),
754 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",
759 node_info=node_info->child[id];
762 if (level < MaxTreeDepth)
764 for (i=0; i < (ssize_t) node_info->number_unique; i++)
766 SetMagickPixelPacket(image,&node_info->list[i].pixel,
767 &node_info->list[i].index,&target);
768 if (IsMagickColorMatch(&pixel,&target) != MagickFalse)
771 if (i < (ssize_t) node_info->number_unique)
772 node_info->list[i].count++;
779 node_info->list=(
ColorPacket *) AcquireQuantumMemory(1,
780 sizeof(*node_info->list));
782 node_info->list=(
ColorPacket *) ResizeQuantumMemory(node_info->list,
783 (
size_t) (i+1),
sizeof(*node_info->list));
786 (void) ThrowMagickException(exception,GetMagickModule(),
787 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",
791 node_info->list[i].pixel=(*p);
792 if ((image->colorspace == CMYKColorspace) ||
793 (image->storage_class == PseudoClass))
794 node_info->list[i].index=GetPixelIndex(indexes+x);
795 node_info->list[i].count=1;
796 node_info->number_unique++;
798 if (cube_info->colors > max_colors)
803 if (x < (ssize_t) image->columns)
806 image_view=DestroyCacheView(image_view);
807 cube_info=DestroyCubeInfo(image,cube_info);
808 return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue);
811 MagickExport MagickBooleanType IdentifyPaletteImage(
const Image *image,
814 assert(image != (
Image *) NULL);
815 assert(image->signature == MagickCoreSignature);
816 if (IsEventLogging() != MagickFalse)
817 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
818 return(CheckImageColors(image,exception,256));
847 MagickExport MagickBooleanType IsHistogramImage(
const Image *image,
850 #define MaximumUniqueColors 1024
885 assert(image != (
Image *) NULL);
886 assert(image->signature == MagickCoreSignature);
887 if (IsEventLogging() != MagickFalse)
888 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
889 if ((image->storage_class == PseudoClass) &&
890 (image->colors <= MaximumUniqueColors))
892 if (image->storage_class == PseudoClass)
897 cube_info=GetCubeInfo();
900 (void) ThrowMagickException(exception,GetMagickModule(),
901 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",image->filename);
904 GetMagickPixelPacket(image,&pixel);
905 GetMagickPixelPacket(image,&target);
906 image_view=AcquireVirtualCacheView(image,exception);
907 for (y=0; y < (ssize_t) image->rows; y++)
909 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
912 indexes=GetCacheViewVirtualIndexQueue(image_view);
913 for (x=0; x < (ssize_t) image->columns; x++)
918 node_info=cube_info->root;
919 index=MaxTreeDepth-1;
920 for (level=1; level < MaxTreeDepth; level++)
922 SetMagickPixelPacket(image,p,indexes+x,&pixel);
923 id=ColorToNodeId(image,&pixel,index);
924 if (node_info->child[
id] == (
NodeInfo *) NULL)
926 node_info->child[id]=GetNodeInfo(cube_info,level);
927 if (node_info->child[
id] == (
NodeInfo *) NULL)
929 (void) ThrowMagickException(exception,GetMagickModule(),
930 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",
935 node_info=node_info->child[id];
938 if (level < MaxTreeDepth)
940 for (i=0; i < (ssize_t) node_info->number_unique; i++)
942 SetMagickPixelPacket(image,&node_info->list[i].pixel,
943 &node_info->list[i].index,&target);
944 if (IsMagickColorMatch(&pixel,&target) != MagickFalse)
947 if (i < (ssize_t) node_info->number_unique)
948 node_info->list[i].count++;
954 if (node_info->number_unique == 0)
955 node_info->list=(
ColorPacket *) AcquireQuantumMemory(1,
956 sizeof(*node_info->list));
958 node_info->list=(
ColorPacket *) ResizeQuantumMemory(node_info->list,
959 (
size_t) (i+1),
sizeof(*node_info->list));
962 (void) ThrowMagickException(exception,GetMagickModule(),
963 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",
967 node_info->list[i].pixel=(*p);
968 if ((image->colorspace == CMYKColorspace) ||
969 (image->storage_class == PseudoClass))
970 node_info->list[i].index=GetPixelIndex(indexes+x);
971 node_info->list[i].count=1;
972 node_info->number_unique++;
974 if (cube_info->colors > MaximumUniqueColors)
979 if (x < (ssize_t) image->columns)
982 image_view=DestroyCacheView(image_view);
983 cube_info=DestroyCubeInfo(image,cube_info);
984 return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue);
1013 MagickExport MagickBooleanType IsPaletteImage(
const Image *image,
1016 assert(image != (
Image *) NULL);
1017 assert(image->signature == MagickCoreSignature);
1018 magick_unreferenced(exception);
1019 if (IsEventLogging() != MagickFalse)
1020 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
1021 if (image->storage_class != PseudoClass)
1022 return(MagickFalse);
1023 return((image->colors <= 256) ? MagickTrue : MagickFalse);
1075 MagickExport MagickBooleanType MinMaxStretchImage(
Image *image,
1076 const ChannelType channel,
const double black_value,
const double white_value)
1086 if ((channel & SyncChannels) != 0)
1091 (void) GetImageChannelRange(image,channel,&min,&max,&image->exception);
1094 if (fabs(min-max) >= MagickEpsilon)
1095 status&=LevelImageChannel(image,channel,min,max,1.0);
1096 return(status != 0 ? MagickTrue : MagickFalse);
1101 if ((channel & RedChannel) != 0)
1103 (void) GetImageChannelRange(image,RedChannel,&min,&max,&image->exception);
1106 if (fabs(min-max) >= MagickEpsilon)
1107 status&=LevelImageChannel(image,RedChannel,min,max,1.0);
1109 if ((channel & GreenChannel) != 0)
1111 (void) GetImageChannelRange(image,GreenChannel,&min,&max,
1115 if (fabs(min-max) >= MagickEpsilon)
1116 status&=LevelImageChannel(image,GreenChannel,min,max,1.0);
1118 if ((channel & BlueChannel) != 0)
1120 (void) GetImageChannelRange(image,BlueChannel,&min,&max,
1124 if (fabs(min-max) >= MagickEpsilon)
1125 status&=LevelImageChannel(image,BlueChannel,min,max,1.0);
1127 if (((channel & OpacityChannel) != 0) &&
1128 (image->matte != MagickFalse))
1130 (void) GetImageChannelRange(image,OpacityChannel,&min,&max,
1134 if (fabs(min-max) >= MagickEpsilon)
1135 status&=LevelImageChannel(image,OpacityChannel,min,max,1.0);
1137 if (((channel & IndexChannel) != 0) &&
1138 (image->colorspace == CMYKColorspace))
1140 (void) GetImageChannelRange(image,IndexChannel,&min,&max,
1144 if (fabs(min-max) >= MagickEpsilon)
1145 status&=LevelImageChannel(image,IndexChannel,min,max,1.0);
1147 return(status != 0 ? MagickTrue : MagickFalse);
1178 #if defined(__cplusplus) || defined(c_plusplus)
1182 static int HistogramCompare(
const void *x,
const void *y)
1190 if (color_2->pixel.red != color_1->pixel.red)
1191 return((
int) ((ssize_t) color_1->pixel.red-(ssize_t) color_2->pixel.red));
1192 if (color_2->pixel.green != color_1->pixel.green)
1193 return((
int) ((ssize_t) color_1->pixel.green-(ssize_t) color_2->pixel.green));
1194 if (color_2->pixel.blue != color_1->pixel.blue)
1195 return((
int) ((ssize_t) color_1->pixel.blue-(ssize_t) color_2->pixel.blue));
1196 return((
int) ((ssize_t) color_2->count-(ssize_t) color_1->count));
1199 #if defined(__cplusplus) || defined(c_plusplus)
1203 MagickExport
size_t GetNumberColors(
const Image *image,FILE *file,
1206 #define HistogramImageTag "Histogram/Image"
1209 color[MaxTextExtent],
1210 count[MaxTextExtent],
1212 tuple[MaxTextExtent];
1233 if (file == (FILE *) NULL)
1238 cube_info=ClassifyImageColors(image,exception);
1239 if (cube_info != (
CubeInfo *) NULL)
1241 number_colors=cube_info->colors;
1242 cube_info=DestroyCubeInfo(image,cube_info);
1244 return(number_colors);
1246 histogram=GetImageHistogram(image,&number_colors,exception);
1248 return(number_colors);
1249 qsort((
void *) histogram,(
size_t) number_colors,
sizeof(*histogram),
1251 GetMagickPixelPacket(image,&pixel);
1254 for (i=0; i < (ssize_t) number_colors; i++)
1256 SetMagickPixelPacket(image,&p->pixel,&p->index,&pixel);
1257 (void) CopyMagickString(tuple,
"(",MaxTextExtent);
1258 ConcatenateColorComponent(&pixel,RedChannel,NoCompliance,tuple);
1259 (void) ConcatenateMagickString(tuple,
",",MaxTextExtent);
1260 ConcatenateColorComponent(&pixel,GreenChannel,NoCompliance,tuple);
1261 (void) ConcatenateMagickString(tuple,
",",MaxTextExtent);
1262 ConcatenateColorComponent(&pixel,BlueChannel,NoCompliance,tuple);
1263 if (pixel.colorspace == CMYKColorspace)
1265 (void) ConcatenateMagickString(tuple,
",",MaxTextExtent);
1266 ConcatenateColorComponent(&pixel,IndexChannel,NoCompliance,tuple);
1268 if (pixel.matte != MagickFalse)
1270 (void) ConcatenateMagickString(tuple,
",",MaxTextExtent);
1271 ConcatenateColorComponent(&pixel,OpacityChannel,NoCompliance,tuple);
1273 (void) ConcatenateMagickString(tuple,
")",MaxTextExtent);
1274 (void) QueryMagickColorname(image,&pixel,SVGCompliance,color,exception);
1275 GetColorTuple(&pixel,MagickTrue,hex);
1276 (void) sprintf(count,
"%10.20g:",(
double) ((MagickOffsetType) p->count));
1277 (void) FormatLocaleFile(file,
" %s %s %s %s\n",count,tuple,hex,color);
1278 if (image->progress_monitor != (MagickProgressMonitor) NULL)
1283 proceed=SetImageProgress(image,HistogramImageTag,(MagickOffsetType) i,
1285 if (proceed == MagickFalse)
1290 (void) fflush(file);
1291 histogram=(
ColorPacket *) RelinquishMagickMemory(histogram);
1292 if (status == MagickFalse)
1294 return(number_colors);
1322 static void UniqueColorsToImage(
Image *unique_image,
CacheView *unique_view,
1325 #define UniqueColorsImageTag "UniqueColors/Image"
1339 number_children=unique_image->matte == MagickFalse ? 8UL : 16UL;
1340 for (i=0; i < (ssize_t) number_children; i++)
1341 if (node_info->child[i] != (
NodeInfo *) NULL)
1342 UniqueColorsToImage(unique_image,unique_view,cube_info,
1343 node_info->child[i],exception);
1344 if (node_info->level == (MaxTreeDepth-1))
1350 *magick_restrict indexes;
1357 for (i=0; i < (ssize_t) node_info->number_unique; i++)
1359 q=QueueCacheViewAuthenticPixels(unique_view,cube_info->x,0,1,1,
1363 indexes=GetCacheViewAuthenticIndexQueue(unique_view);
1365 if (unique_image->colorspace == CMYKColorspace)
1367 if (SyncCacheViewAuthenticPixels(unique_view,exception) == MagickFalse)
1372 if (unique_image->progress_monitor != (MagickProgressMonitor) NULL)
1377 proceed=SetImageProgress(unique_image,UniqueColorsImageTag,
1378 cube_info->progress,cube_info->colors);
1379 if (proceed == MagickFalse)
1382 cube_info->progress++;
1383 if (status == MagickFalse)
1388 MagickExport
Image *UniqueImageColors(
const Image *image,
1400 cube_info=ClassifyImageColors(image,exception);
1401 if (cube_info == (
CubeInfo *) NULL)
1402 return((
Image *) NULL);
1403 unique_image=CloneImage(image,cube_info->colors,1,MagickTrue,exception);
1404 if (unique_image == (
Image *) NULL)
1405 return(unique_image);
1406 if (SetImageStorageClass(unique_image,DirectClass) == MagickFalse)
1408 InheritException(exception,&unique_image->exception);
1409 unique_image=DestroyImage(unique_image);
1410 return((
Image *) NULL);
1412 unique_view=AcquireVirtualCacheView(unique_image,exception);
1413 UniqueColorsToImage(unique_image,unique_view,cube_info,cube_info->root,
1415 unique_view=DestroyCacheView(unique_view);
1416 cube_info=DestroyCubeInfo(image,cube_info);
1417 return(unique_image);