176 #include "magick/studio.h"
177 #include "magick/artifact.h"
178 #include "magick/attribute.h"
179 #include "magick/cache-view.h"
180 #include "magick/color.h"
181 #include "magick/color-private.h"
182 #include "magick/colormap.h"
183 #include "magick/colorspace.h"
184 #include "magick/colorspace-private.h"
185 #include "magick/enhance.h"
186 #include "magick/exception.h"
187 #include "magick/exception-private.h"
188 #include "magick/histogram.h"
189 #include "magick/image.h"
190 #include "magick/image-private.h"
191 #include "magick/list.h"
192 #include "magick/memory_.h"
193 #include "magick/monitor.h"
194 #include "magick/monitor-private.h"
195 #include "magick/option.h"
196 #include "magick/pixel-private.h"
197 #include "magick/quantize.h"
198 #include "magick/quantum.h"
199 #include "magick/resource_.h"
200 #include "magick/string_.h"
201 #include "magick/string-private.h"
202 #include "magick/thread-private.h"
207 #if !defined(__APPLE__) && !defined(TARGET_OS_IPHONE)
212 #define ErrorQueueLength 16
213 #define ErrorRelativeWeight PerceptibleReciprocal(16)
214 #define MaxNodes 266817
215 #define MaxTreeDepth 8
216 #define NodesInAList 1920
292 error[ErrorQueueLength];
296 weights[ErrorQueueLength];
322 *GetCubeInfo(
const QuantizeInfo *,
const size_t,
const size_t);
327 static MagickBooleanType
331 SetGrayscaleImage(
Image *);
368 quantize_info=(
QuantizeInfo *) AcquireMagickMemory(
sizeof(*quantize_info));
370 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
371 GetQuantizeInfo(quantize_info);
377 quantize_info->dither=image_info->dither;
378 option=GetImageOption(image_info,
"dither");
379 if (option != (
const char *) NULL)
380 quantize_info->dither_method=(DitherMethod) ParseCommandOption(
381 MagickDitherOptions,MagickFalse,option);
382 quantize_info->measure_error=image_info->verbose;
384 return(quantize_info);
427 static inline void AssociateAlphaPixel(
const CubeInfo *cube_info,
433 alpha_pixel->index=0;
434 if ((cube_info->associate_alpha == MagickFalse) ||
435 (pixel->opacity == OpaqueOpacity))
437 alpha_pixel->red=(MagickRealType) GetPixelRed(pixel);
438 alpha_pixel->green=(MagickRealType) GetPixelGreen(pixel);
439 alpha_pixel->blue=(MagickRealType) GetPixelBlue(pixel);
440 alpha_pixel->opacity=(MagickRealType) GetPixelOpacity(pixel);
443 alpha=(MagickRealType) (QuantumScale*(QuantumRange-GetPixelOpacity(pixel)));
444 alpha_pixel->red=alpha*GetPixelRed(pixel);
445 alpha_pixel->green=alpha*GetPixelGreen(pixel);
446 alpha_pixel->blue=alpha*GetPixelBlue(pixel);
447 alpha_pixel->opacity=(MagickRealType) GetPixelOpacity(pixel);
450 static inline size_t ColorToNodeId(
const CubeInfo *cube_info,
456 id=(size_t) (((ScaleQuantumToChar(ClampPixel(GetPixelRed(pixel))) >> index) &
457 0x01) | ((ScaleQuantumToChar(ClampPixel(GetPixelGreen(pixel))) >> index) &
458 0x01) << 1 | ((ScaleQuantumToChar(ClampPixel(GetPixelBlue(pixel))) >>
459 index) & 0x01) << 2);
460 if (cube_info->associate_alpha != MagickFalse)
461 id|=((ScaleQuantumToChar(ClampPixel(GetPixelOpacity(pixel))) >> index) &
466 static inline MagickBooleanType IsSameColor(
const Image *image,
469 if ((GetPixelRed(p) != GetPixelRed(q)) ||
470 (GetPixelGreen(p) != GetPixelGreen(q)) ||
471 (GetPixelBlue(p) != GetPixelBlue(q)))
473 if ((image->matte != MagickFalse) &&
474 (GetPixelOpacity(p) != GetPixelOpacity(q)))
479 static MagickBooleanType AssignImageColors(
Image *image,
CubeInfo *cube_info)
481 #define AssignImageTag "Assign/Image"
495 colorspace=image->colorspace;
496 if (cube_info->quantize_info->colorspace != UndefinedColorspace)
497 (void) TransformImageColorspace(image,cube_info->quantize_info->colorspace);
498 number_colors=MagickMax(cube_info->colors,cube_info->maximum_colors);
499 if (AcquireImageColormap(image,number_colors) == MagickFalse)
500 ThrowBinaryImageException(ResourceLimitError,
"MemoryAllocationFailed",
503 cube_info->transparent_pixels=0;
504 cube_info->transparent_index=(-1);
505 DefineImageColormap(image,cube_info,cube_info->root);
509 if ((cube_info->quantize_info->dither != MagickFalse) &&
510 (cube_info->quantize_info->dither_method != NoDitherMethod))
511 (void) DitherImage(image,cube_info);
524 exception=(&image->exception);
525 image_view=AcquireAuthenticCacheView(image,exception);
526 #if defined(MAGICKCORE_OPENMP_SUPPORT)
527 #pragma omp parallel for schedule(static) shared(status) \
528 magick_number_threads(image,image,image->rows,1)
530 for (y=0; y < (ssize_t) image->rows; y++)
536 *magick_restrict indexes;
547 if (status == MagickFalse)
549 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
556 indexes=GetCacheViewAuthenticIndexQueue(image_view);
558 for (x=0; x < (ssize_t) image->columns; x+=count)
576 for (count=1; (x+count) < (ssize_t) image->columns; count++)
577 if (IsSameColor(image,q,q+count) == MagickFalse)
579 AssociateAlphaPixel(&cube,q,&pixel);
581 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
583 id=ColorToNodeId(&cube,&pixel,index);
584 if (node_info->child[
id] == (
NodeInfo *) NULL)
586 node_info=node_info->child[id];
592 cube.distance=(MagickRealType) (4.0*(QuantumRange+1.0)*
593 (QuantumRange+1.0)+1.0);
594 ClosestColor(image,&cube,node_info->parent);
595 index=cube.color_number;
596 for (i=0; i < (ssize_t) count; i++)
598 if (image->storage_class == PseudoClass)
599 SetPixelIndex(indexes+x+i,index);
600 if (cube.quantize_info->measure_error == MagickFalse)
602 SetPixelRgb(q,image->colormap+index);
603 if (cube.associate_alpha != MagickFalse)
604 SetPixelOpacity(q,image->colormap[index].opacity);
609 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
611 if (image->progress_monitor != (MagickProgressMonitor) NULL)
616 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y,
618 if (proceed == MagickFalse)
622 image_view=DestroyCacheView(image_view);
624 if (cube_info->quantize_info->measure_error != MagickFalse)
625 (void) GetImageQuantizeError(image);
626 if ((cube_info->quantize_info->number_colors == 2) &&
627 (IsGrayColorspace(cube_info->quantize_info->colorspace)))
635 intensity=GetPixelLuma(image,image->colormap+0) < QuantumRange/2.0 ? 0.0 :
637 if ((image->colors > 1) &&
638 (GetPixelLuma(image,image->colormap+0) >
639 GetPixelLuma(image,image->colormap+1)))
640 intensity=(double) QuantumRange;
641 image->colormap[0].red=intensity;
642 image->colormap[0].green=intensity;
643 image->colormap[0].blue=intensity;
644 if (image->colors > 1)
646 image->colormap[1].red=(double) QuantumRange-intensity;
647 image->colormap[1].green=(double) QuantumRange-intensity;
648 image->colormap[1].blue=(double) QuantumRange-intensity;
651 (void) SyncImage(image);
652 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
653 (IssRGBCompatibleColorspace(colorspace) == MagickFalse))
654 (void) TransformImageColorspace(image,colorspace);
719 static inline void SetAssociatedAlpha(
const Image *image,
CubeInfo *cube_info)
724 associate_alpha=image->matte;
725 if ((cube_info->quantize_info->number_colors == 2) &&
726 ((cube_info->quantize_info->colorspace == LinearGRAYColorspace) ||
727 (cube_info->quantize_info->colorspace == GRAYColorspace)))
728 associate_alpha=MagickFalse;
729 cube_info->associate_alpha=associate_alpha;
732 static MagickBooleanType ClassifyImageColors(
CubeInfo *cube_info,
735 #define ClassifyImageTag "Classify/Image"
767 SetAssociatedAlpha(image,cube_info);
768 if (cube_info->quantize_info->colorspace != image->colorspace)
770 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
771 (cube_info->quantize_info->colorspace != CMYKColorspace))
772 (void) TransformImageColorspace((
Image *) image,
773 cube_info->quantize_info->colorspace);
775 if (IssRGBCompatibleColorspace(image->colorspace) == MagickFalse)
776 (
void) TransformImageColorspace((
Image *) image,sRGBColorspace);
778 midpoint.red=(MagickRealType) QuantumRange/2.0;
779 midpoint.green=(MagickRealType) QuantumRange/2.0;
780 midpoint.blue=(MagickRealType) QuantumRange/2.0;
781 midpoint.opacity=(MagickRealType) QuantumRange/2.0;
782 midpoint.index=(MagickRealType) QuantumRange/2.0;
784 image_view=AcquireVirtualCacheView(image,exception);
785 for (y=0; y < (ssize_t) image->rows; y++)
793 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
796 if (cube_info->nodes > MaxNodes)
801 PruneLevel(cube_info,cube_info->root);
804 for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
809 for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
810 if (IsSameColor(image,p,p+count) == MagickFalse)
812 AssociateAlphaPixel(cube_info,p,&pixel);
813 index=MaxTreeDepth-1;
814 bisect=((MagickRealType) QuantumRange+1.0)/2.0;
816 node_info=cube_info->root;
817 for (level=1; level <= MaxTreeDepth; level++)
823 id=ColorToNodeId(cube_info,&pixel,index);
824 mid.red+=(
id & 1) != 0 ? bisect : -bisect;
825 mid.green+=(
id & 2) != 0 ? bisect : -bisect;
826 mid.blue+=(
id & 4) != 0 ? bisect : -bisect;
827 mid.opacity+=(
id & 8) != 0 ? bisect : -bisect;
828 if (node_info->child[
id] == (
NodeInfo *) NULL)
833 node_info->child[id]=GetNodeInfo(cube_info,
id,level,node_info);
834 if (node_info->child[
id] == (
NodeInfo *) NULL)
836 (void) ThrowMagickException(exception,GetMagickModule(),
837 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",
841 if (level == MaxTreeDepth)
847 node_info=node_info->child[id];
848 error.red=QuantumScale*(pixel.red-mid.red);
849 error.green=QuantumScale*(pixel.green-mid.green);
850 error.blue=QuantumScale*(pixel.blue-mid.blue);
851 if (cube_info->associate_alpha != MagickFalse)
852 error.opacity=QuantumScale*(pixel.opacity-mid.opacity);
853 distance=(double) (error.red*error.red+error.green*error.green+
854 error.blue*error.blue+error.opacity*error.opacity);
855 if (IsNaN(distance) != 0)
857 node_info->quantize_error+=count*sqrt(distance);
858 cube_info->root->quantize_error+=node_info->quantize_error;
864 node_info->number_unique+=count;
865 node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red);
866 node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green);
867 node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue);
868 if (cube_info->associate_alpha != MagickFalse)
869 node_info->total_color.opacity+=count*QuantumScale*
870 ClampPixel(pixel.opacity);
872 node_info->total_color.opacity+=count*QuantumScale*
873 ClampPixel(OpaqueOpacity);
876 if (cube_info->colors > cube_info->maximum_colors)
878 PruneToCubeDepth(cube_info,cube_info->root);
881 proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
883 if (proceed == MagickFalse)
886 for (y++; y < (ssize_t) image->rows; y++)
894 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
897 if (cube_info->nodes > MaxNodes)
902 PruneLevel(cube_info,cube_info->root);
905 for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
910 for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
911 if (IsSameColor(image,p,p+count) == MagickFalse)
913 AssociateAlphaPixel(cube_info,p,&pixel);
914 index=MaxTreeDepth-1;
915 bisect=((MagickRealType) QuantumRange+1.0)/2.0;
917 node_info=cube_info->root;
918 for (level=1; level <= cube_info->depth; level++)
924 id=ColorToNodeId(cube_info,&pixel,index);
925 mid.red+=(
id & 1) != 0 ? bisect : -bisect;
926 mid.green+=(
id & 2) != 0 ? bisect : -bisect;
927 mid.blue+=(
id & 4) != 0 ? bisect : -bisect;
928 mid.opacity+=(
id & 8) != 0 ? bisect : -bisect;
929 if (node_info->child[
id] == (
NodeInfo *) NULL)
934 node_info->child[id]=GetNodeInfo(cube_info,
id,level,node_info);
935 if (node_info->child[
id] == (
NodeInfo *) NULL)
937 (void) ThrowMagickException(exception,GetMagickModule(),
938 ResourceLimitError,
"MemoryAllocationFailed",
"%s",
942 if (level == cube_info->depth)
948 node_info=node_info->child[id];
949 error.red=QuantumScale*(pixel.red-mid.red);
950 error.green=QuantumScale*(pixel.green-mid.green);
951 error.blue=QuantumScale*(pixel.blue-mid.blue);
952 if (cube_info->associate_alpha != MagickFalse)
953 error.opacity=QuantumScale*(pixel.opacity-mid.opacity);
954 distance=(double) (error.red*error.red+error.green*error.green+
955 error.blue*error.blue+error.opacity*error.opacity);
956 if (IsNaN(distance) != 0)
958 node_info->quantize_error+=count*sqrt(distance);
959 cube_info->root->quantize_error+=node_info->quantize_error;
965 node_info->number_unique+=count;
966 node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red);
967 node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green);
968 node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue);
969 if (cube_info->associate_alpha != MagickFalse)
970 node_info->total_color.opacity+=count*QuantumScale*ClampPixel(
973 node_info->total_color.opacity+=count*QuantumScale*
974 ClampPixel(OpaqueOpacity);
977 proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
979 if (proceed == MagickFalse)
982 image_view=DestroyCacheView(image_view);
983 if (cube_info->quantize_info->colorspace != image->colorspace)
984 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
985 (cube_info->quantize_info->colorspace != CMYKColorspace))
986 (void) TransformImageColorspace((
Image *) image,sRGBColorspace);
987 return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue);
1021 clone_info=(
QuantizeInfo *) AcquireMagickMemory(
sizeof(*clone_info));
1023 ThrowFatalException(ResourceLimitFatalError,
"MemoryAllocationFailed");
1024 GetQuantizeInfo(clone_info);
1027 clone_info->number_colors=quantize_info->number_colors;
1028 clone_info->tree_depth=quantize_info->tree_depth;
1029 clone_info->dither=quantize_info->dither;
1030 clone_info->dither_method=quantize_info->dither_method;
1031 clone_info->colorspace=quantize_info->colorspace;
1032 clone_info->measure_error=quantize_info->measure_error;
1065 static void ClosestColor(
const Image *image,
CubeInfo *cube_info,
1077 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1078 for (i=0; i < (ssize_t) number_children; i++)
1079 if (node_info->child[i] != (
NodeInfo *) NULL)
1080 ClosestColor(image,cube_info,node_info->child[i]);
1081 if (node_info->number_unique != 0)
1100 p=image->colormap+node_info->color_number;
1101 q=(&cube_info->target);
1104 if (cube_info->associate_alpha != MagickFalse)
1106 alpha=(MagickRealType) (QuantumScale*GetPixelAlpha(p));
1107 beta=(MagickRealType) (QuantumScale*GetPixelAlpha(q));
1109 pixel=alpha*GetPixelRed(p)-beta*GetPixelRed(q);
1110 distance=pixel*pixel;
1111 if (distance <= cube_info->distance)
1113 pixel=alpha*GetPixelGreen(p)-beta*GetPixelGreen(q);
1114 distance+=pixel*pixel;
1115 if (distance <= cube_info->distance)
1117 pixel=alpha*GetPixelBlue(p)-beta*GetPixelBlue(q);
1118 distance+=pixel*pixel;
1119 if (distance <= cube_info->distance)
1121 if (cube_info->associate_alpha != MagickFalse)
1123 pixel=GetPixelAlpha(p)-GetPixelAlpha(q);
1124 distance+=pixel*pixel;
1126 if (distance <= cube_info->distance)
1128 cube_info->distance=distance;
1129 cube_info->color_number=node_info->color_number;
1160 MagickExport MagickBooleanType CompressImageColormap(
Image *image)
1165 assert(image != (
Image *) NULL);
1166 assert(image->signature == MagickCoreSignature);
1167 if (IsEventLogging() != MagickFalse)
1168 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
1169 if (IsPaletteImage(image,&image->exception) == MagickFalse)
1170 return(MagickFalse);
1171 GetQuantizeInfo(&quantize_info);
1172 quantize_info.number_colors=image->colors;
1173 quantize_info.tree_depth=MaxTreeDepth;
1174 return(QuantizeImage(&quantize_info,image));
1207 static void DefineImageColormap(
Image *image,
CubeInfo *cube_info,
1219 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1220 for (i=0; i < (ssize_t) number_children; i++)
1221 if (node_info->child[i] != (
NodeInfo *) NULL)
1222 DefineImageColormap(image,cube_info,node_info->child[i]);
1223 if (node_info->number_unique != 0)
1234 q=image->colormap+image->colors;
1235 alpha=(MagickRealType) ((MagickOffsetType) node_info->number_unique);
1236 alpha=PerceptibleReciprocal(alpha);
1237 if (cube_info->associate_alpha == MagickFalse)
1239 SetPixelRed(q,ClampToQuantum((MagickRealType) (alpha*
1240 QuantumRange*node_info->total_color.red)));
1241 SetPixelGreen(q,ClampToQuantum((MagickRealType) (alpha*
1242 QuantumRange*node_info->total_color.green)));
1243 SetPixelBlue(q,ClampToQuantum((MagickRealType) (alpha*
1244 QuantumRange*node_info->total_color.blue)));
1245 SetPixelOpacity(q,OpaqueOpacity);
1252 opacity=(MagickRealType) (alpha*QuantumRange*
1253 node_info->total_color.opacity);
1254 SetPixelOpacity(q,ClampToQuantum(opacity));
1255 if (q->opacity == OpaqueOpacity)
1257 SetPixelRed(q,ClampToQuantum((MagickRealType) (alpha*
1258 QuantumRange*node_info->total_color.red)));
1259 SetPixelGreen(q,ClampToQuantum((MagickRealType) (alpha*
1260 QuantumRange*node_info->total_color.green)));
1261 SetPixelBlue(q,ClampToQuantum((MagickRealType) (alpha*
1262 QuantumRange*node_info->total_color.blue)));
1269 gamma=(double) (QuantumScale*(QuantumRange-(
double) q->opacity));
1270 gamma=PerceptibleReciprocal(gamma);
1271 SetPixelRed(q,ClampToQuantum((MagickRealType) (alpha*
1272 gamma*QuantumRange*node_info->total_color.red)));
1273 SetPixelGreen(q,ClampToQuantum((MagickRealType) (alpha*
1274 gamma*QuantumRange*node_info->total_color.green)));
1275 SetPixelBlue(q,ClampToQuantum((MagickRealType) (alpha*
1276 gamma*QuantumRange*node_info->total_color.blue)));
1277 if (node_info->number_unique > cube_info->transparent_pixels)
1279 cube_info->transparent_pixels=node_info->number_unique;
1280 cube_info->transparent_index=(ssize_t) image->colors;
1284 node_info->color_number=image->colors++;
1310 static void DestroyCubeInfo(
CubeInfo *cube_info)
1320 nodes=cube_info->node_queue->next;
1321 cube_info->node_queue->nodes=(
NodeInfo *) RelinquishMagickMemory(
1322 cube_info->node_queue->nodes);
1323 cube_info->node_queue=(
Nodes *) RelinquishMagickMemory(
1324 cube_info->node_queue);
1325 cube_info->node_queue=nodes;
1326 }
while (cube_info->node_queue != (
Nodes *) NULL);
1327 if (cube_info->memory_info != (
MemoryInfo *) NULL)
1328 cube_info->memory_info=RelinquishVirtualMemory(cube_info->memory_info);
1329 cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info);
1330 cube_info=(
CubeInfo *) RelinquishMagickMemory(cube_info);
1359 assert(quantize_info->signature == MagickCoreSignature);
1360 if (IsEventLogging() != MagickFalse)
1361 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1362 quantize_info->signature=(~MagickCoreSignature);
1363 quantize_info=(
QuantizeInfo *) RelinquishMagickMemory(quantize_info);
1364 return(quantize_info);
1401 for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++)
1419 number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
1424 (void) memset(pixels,0,number_threads*
sizeof(*pixels));
1425 for (i=0; i < (ssize_t) number_threads; i++)
1428 2*
sizeof(**pixels));
1430 return(DestroyPixelTLS(pixels));
1435 static inline ssize_t CacheOffset(
CubeInfo *cube_info,
1438 #define RedShift(pixel) (((pixel) >> CacheShift) << (0*(8-CacheShift)))
1439 #define GreenShift(pixel) (((pixel) >> CacheShift) << (1*(8-CacheShift)))
1440 #define BlueShift(pixel) (((pixel) >> CacheShift) << (2*(8-CacheShift)))
1441 #define AlphaShift(pixel) (((pixel) >> CacheShift) << (3*(8-CacheShift)))
1446 offset=(ssize_t) (RedShift(ScaleQuantumToChar(ClampPixel(pixel->red))) |
1447 GreenShift(ScaleQuantumToChar(ClampPixel(pixel->green))) |
1448 BlueShift(ScaleQuantumToChar(ClampPixel(pixel->blue))));
1449 if (cube_info->associate_alpha != MagickFalse)
1450 offset|=AlphaShift(ScaleQuantumToChar(ClampPixel(pixel->opacity)));
1454 static MagickBooleanType FloydSteinbergDither(
Image *image,
CubeInfo *cube_info)
1456 #define DitherImageTag "Dither/Image"
1476 pixels=AcquirePixelTLS(image->columns);
1478 return(MagickFalse);
1479 exception=(&image->exception);
1481 image_view=AcquireAuthenticCacheView(image,exception);
1482 for (y=0; y < (ssize_t) image->rows; y++)
1485 id = GetOpenMPThreadId();
1495 *magick_restrict indexes;
1507 if (status == MagickFalse)
1509 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
1515 indexes=GetCacheViewAuthenticIndexQueue(image_view);
1517 current=pixels[id]+(y & 0x01)*image->columns;
1518 previous=pixels[
id]+((y+1) & 0x01)*image->columns;
1519 v=(ssize_t) ((y & 0x01) ? -1 : 1);
1520 for (x=0; x < (ssize_t) image->columns; x++)
1532 u=(y & 0x01) ? (ssize_t) image->columns-1-x : x;
1533 AssociateAlphaPixel(&cube,q+u,&pixel);
1536 pixel.red+=7.0*cube_info->diffusion*current[u-v].red/16;
1537 pixel.green+=7.0*cube_info->diffusion*current[u-v].green/16;
1538 pixel.blue+=7.0*cube_info->diffusion*current[u-v].blue/16;
1539 if (cube.associate_alpha != MagickFalse)
1540 pixel.opacity+=7.0*cube_info->diffusion*current[u-v].opacity/16;
1544 if (x < (ssize_t) (image->columns-1))
1546 pixel.red+=cube_info->diffusion*previous[u+v].red/16;
1547 pixel.green+=cube_info->diffusion*previous[u+v].green/16;
1548 pixel.blue+=cube_info->diffusion*previous[u+v].blue/16;
1549 if (cube.associate_alpha != MagickFalse)
1550 pixel.opacity+=cube_info->diffusion*previous[u+v].opacity/16;
1552 pixel.red+=5.0*cube_info->diffusion*previous[u].red/16;
1553 pixel.green+=5.0*cube_info->diffusion*previous[u].green/16;
1554 pixel.blue+=5.0*cube_info->diffusion*previous[u].blue/16;
1555 if (cube.associate_alpha != MagickFalse)
1556 pixel.opacity+=5.0*cube_info->diffusion*previous[u].opacity/16;
1559 pixel.red+=3.0*cube_info->diffusion*previous[u-v].red/16;
1560 pixel.green+=3.0*cube_info->diffusion*previous[u-v].green/16;
1561 pixel.blue+=3.0*cube_info->diffusion*previous[u-v].blue/16;
1562 if (cube.associate_alpha != MagickFalse)
1563 pixel.opacity+=3.0*cube_info->diffusion*
1564 previous[u-v].opacity/16;
1567 pixel.red=(MagickRealType) ClampPixel(pixel.red);
1568 pixel.green=(MagickRealType) ClampPixel(pixel.green);
1569 pixel.blue=(MagickRealType) ClampPixel(pixel.blue);
1570 if (cube.associate_alpha != MagickFalse)
1571 pixel.opacity=(MagickRealType) ClampPixel(pixel.opacity);
1572 i=CacheOffset(&cube,&pixel);
1573 if (cube.cache[i] < 0)
1584 node_info=cube.root;
1585 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1587 id=ColorToNodeId(&cube,&pixel,index);
1588 if (node_info->child[
id] == (
NodeInfo *) NULL)
1590 node_info=node_info->child[id];
1596 cube.distance=(MagickRealType) (4.0*(QuantumRange+1.0)*(QuantumRange+
1598 ClosestColor(image,&cube,node_info->parent);
1599 cube.cache[i]=(ssize_t) cube.color_number;
1604 index=(size_t) cube.cache[i];
1605 if (image->storage_class == PseudoClass)
1606 SetPixelIndex(indexes+u,index);
1607 if (cube.quantize_info->measure_error == MagickFalse)
1609 SetPixelRgb(q+u,image->colormap+index);
1610 if (cube.associate_alpha != MagickFalse)
1611 SetPixelOpacity(q+u,image->colormap[index].opacity);
1613 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1618 AssociateAlphaPixel(&cube,image->colormap+index,&color);
1619 current[u].red=pixel.red-color.red;
1620 current[u].green=pixel.green-color.green;
1621 current[u].blue=pixel.blue-color.blue;
1622 if (cube.associate_alpha != MagickFalse)
1623 current[u].opacity=pixel.opacity-color.opacity;
1624 if (image->progress_monitor != (MagickProgressMonitor) NULL)
1629 proceed=SetImageProgress(image,DitherImageTag,(MagickOffsetType) y,
1631 if (proceed == MagickFalse)
1636 image_view=DestroyCacheView(image_view);
1637 pixels=DestroyPixelTLS(pixels);
1641 static MagickBooleanType
1644 static MagickBooleanType Riemersma(
Image *image,
CacheView *image_view,
1645 CubeInfo *cube_info,
const size_t level,
const unsigned int direction)
1656 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1657 if (status != MagickFalse)
1658 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1659 if (status != MagickFalse)
1660 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1665 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1666 if (status != MagickFalse)
1667 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1668 if (status != MagickFalse)
1669 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1674 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1675 if (status != MagickFalse)
1676 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1677 if (status != MagickFalse)
1678 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1683 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1684 if (status != MagickFalse)
1685 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1686 if (status != MagickFalse)
1687 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1698 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1699 if (status != MagickFalse)
1700 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1701 if (status != MagickFalse)
1702 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1703 if (status != MagickFalse)
1704 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1705 if (status != MagickFalse)
1706 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1707 if (status != MagickFalse)
1708 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1709 if (status != MagickFalse)
1710 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1715 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1716 if (status != MagickFalse)
1717 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1718 if (status != MagickFalse)
1719 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1720 if (status != MagickFalse)
1721 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1722 if (status != MagickFalse)
1723 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1724 if (status != MagickFalse)
1725 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1726 if (status != MagickFalse)
1727 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1732 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1733 if (status != MagickFalse)
1734 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1735 if (status != MagickFalse)
1736 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1737 if (status != MagickFalse)
1738 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1739 if (status != MagickFalse)
1740 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1741 if (status != MagickFalse)
1742 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1743 if (status != MagickFalse)
1744 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1749 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1750 if (status != MagickFalse)
1751 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1752 if (status != MagickFalse)
1753 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1754 if (status != MagickFalse)
1755 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1756 if (status != MagickFalse)
1757 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1758 if (status != MagickFalse)
1759 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1760 if (status != MagickFalse)
1761 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1767 return(status != 0 ? MagickTrue : MagickFalse);
1770 static MagickBooleanType RiemersmaDither(
Image *image,
CacheView *image_view,
1771 CubeInfo *cube_info,
const unsigned int direction)
1773 #define DitherImageTag "Dither/Image"
1789 if ((p->x >= 0) && (p->x < (ssize_t) image->columns) &&
1790 (p->y >= 0) && (p->y < (ssize_t) image->rows))
1796 *magick_restrict indexes;
1807 exception=(&image->exception);
1808 q=GetCacheViewAuthenticPixels(image_view,p->x,p->y,1,1,exception);
1810 return(MagickFalse);
1811 indexes=GetCacheViewAuthenticIndexQueue(image_view);
1812 AssociateAlphaPixel(cube_info,q,&pixel);
1813 for (i=0; i < ErrorQueueLength; i++)
1815 pixel.red+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1817 pixel.green+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1819 pixel.blue+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1821 if (cube_info->associate_alpha != MagickFalse)
1822 pixel.opacity+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1823 p->error[i].opacity;
1825 pixel.red=(MagickRealType) ClampPixel(pixel.red);
1826 pixel.green=(MagickRealType) ClampPixel(pixel.green);
1827 pixel.blue=(MagickRealType) ClampPixel(pixel.blue);
1828 if (cube_info->associate_alpha != MagickFalse)
1829 pixel.opacity=(MagickRealType) ClampPixel(pixel.opacity);
1830 i=CacheOffset(cube_info,&pixel);
1831 if (p->cache[i] < 0)
1843 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1845 id=ColorToNodeId(cube_info,&pixel,index);
1846 if (node_info->child[
id] == (
NodeInfo *) NULL)
1848 node_info=node_info->child[id];
1854 p->distance=(MagickRealType) (4.0*(QuantumRange+1.0)*((MagickRealType)
1855 QuantumRange+1.0)+1.0);
1856 ClosestColor(image,p,node_info->parent);
1857 p->cache[i]=(ssize_t) p->color_number;
1862 index=(size_t) (1*p->cache[i]);
1863 if (image->storage_class == PseudoClass)
1864 *indexes=(IndexPacket) index;
1865 if (cube_info->quantize_info->measure_error == MagickFalse)
1867 SetPixelRgb(q,image->colormap+index);
1868 if (cube_info->associate_alpha != MagickFalse)
1869 SetPixelOpacity(q,image->colormap[index].opacity);
1871 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1872 return(MagickFalse);
1876 (void) memmove(p->error,p->error+1,(ErrorQueueLength-1)*
1877 sizeof(p->error[0]));
1878 AssociateAlphaPixel(cube_info,image->colormap+index,&color);
1879 p->error[ErrorQueueLength-1].red=pixel.red-color.red;
1880 p->error[ErrorQueueLength-1].green=pixel.green-color.green;
1881 p->error[ErrorQueueLength-1].blue=pixel.blue-color.blue;
1882 if (cube_info->associate_alpha != MagickFalse)
1883 p->error[ErrorQueueLength-1].opacity=pixel.opacity-color.opacity;
1884 proceed=SetImageProgress(image,DitherImageTag,p->offset,p->span);
1885 if (proceed == MagickFalse)
1886 return(MagickFalse);
1891 case WestGravity: p->x--;
break;
1892 case EastGravity: p->x++;
break;
1893 case NorthGravity: p->y--;
break;
1894 case SouthGravity: p->y++;
break;
1899 static MagickBooleanType DitherImage(
Image *image,
CubeInfo *cube_info)
1914 artifact=GetImageArtifact(image,
"dither:diffusion-amount");
1915 if (artifact != (
const char *) NULL)
1916 cube_info->diffusion=StringToDoubleInterval(artifact,1.0);
1917 if (cube_info->quantize_info->dither_method != RiemersmaDitherMethod)
1918 return(FloydSteinbergDither(image,cube_info));
1922 (void) memset(cube_info->error,0,ErrorQueueLength*
sizeof(*cube_info->error));
1925 extent=MagickMax(image->columns,image->rows);
1926 level=(size_t) log2((
double) extent);
1927 if ((1UL << level) < extent)
1929 cube_info->offset=0;
1930 cube_info->span=(MagickSizeType) image->columns*image->rows;
1931 image_view=AcquireAuthenticCacheView(image,&image->exception);
1934 status=Riemersma(image,image_view,cube_info,level,NorthGravity);
1935 if (status != MagickFalse)
1936 status=RiemersmaDither(image,image_view,cube_info,ForgetGravity);
1937 image_view=DestroyCacheView(image_view);
1976 const size_t depth,
const size_t maximum_colors)
1993 cube_info=(
CubeInfo *) AcquireMagickMemory(
sizeof(*cube_info));
1994 if (cube_info == (
CubeInfo *) NULL)
1996 (void) memset(cube_info,0,
sizeof(*cube_info));
1997 cube_info->depth=depth;
1998 if (cube_info->depth > MaxTreeDepth)
1999 cube_info->depth=MaxTreeDepth;
2000 if (cube_info->depth < 2)
2002 cube_info->maximum_colors=maximum_colors;
2006 cube_info->root=GetNodeInfo(cube_info,0,0,(
NodeInfo *) NULL);
2007 if (cube_info->root == (
NodeInfo *) NULL)
2009 cube_info->root->parent=cube_info->root;
2010 cube_info->quantize_info=CloneQuantizeInfo(quantize_info);
2011 if (cube_info->quantize_info->dither == MagickFalse)
2016 length=(size_t) (1UL << (4*(8-CacheShift)));
2017 cube_info->memory_info=AcquireVirtualMemory(length,
sizeof(*cube_info->cache));
2018 if (cube_info->memory_info == (
MemoryInfo *) NULL)
2020 cube_info->cache=(ssize_t *) GetVirtualMemoryBlob(cube_info->memory_info);
2024 (void) memset(cube_info->cache,(-1),
sizeof(*cube_info->cache)*length);
2029 for (i=0; i < ErrorQueueLength; i++)
2031 cube_info->weights[i]=PerceptibleReciprocal(weight);
2032 weight*=exp(log(1.0/ErrorRelativeWeight)/(ErrorQueueLength-1.0));
2034 cube_info->diffusion=1.0;
2067 const size_t level,
NodeInfo *parent)
2072 if (cube_info->free_nodes == 0)
2080 nodes=(
Nodes *) AcquireMagickMemory(
sizeof(*nodes));
2081 if (nodes == (
Nodes *) NULL)
2083 nodes->nodes=(
NodeInfo *) AcquireQuantumMemory(NodesInAList,
2084 sizeof(*nodes->nodes));
2085 if (nodes->nodes == (
NodeInfo *) NULL)
2087 nodes->next=cube_info->node_queue;
2088 cube_info->node_queue=nodes;
2089 cube_info->next_node=nodes->nodes;
2090 cube_info->free_nodes=NodesInAList;
2093 cube_info->free_nodes--;
2094 node_info=cube_info->next_node++;
2095 (void) memset(node_info,0,
sizeof(*node_info));
2096 node_info->parent=parent;
2098 node_info->level=level;
2141 MagickExport MagickBooleanType GetImageQuantizeError(
Image *image)
2160 mean_error_per_pixel;
2166 assert(image != (
Image *) NULL);
2167 assert(image->signature == MagickCoreSignature);
2168 if (IsEventLogging() != MagickFalse)
2169 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
2170 image->total_colors=GetNumberColors(image,(FILE *) NULL,&image->exception);
2171 (void) memset(&image->error,0,
sizeof(image->error));
2172 if (image->storage_class == DirectClass)
2176 area=3.0*image->columns*image->rows;
2178 mean_error_per_pixel=0.0;
2180 exception=(&image->exception);
2181 image_view=AcquireVirtualCacheView(image,exception);
2182 for (y=0; y < (ssize_t) image->rows; y++)
2190 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
2193 indexes=GetCacheViewAuthenticIndexQueue(image_view);
2194 for (x=0; x < (ssize_t) image->columns; x++)
2196 index=(ssize_t) GetPixelIndex(indexes+x);
2197 if (image->matte != MagickFalse)
2199 alpha=(MagickRealType) (QuantumScale*(GetPixelAlpha(p)));
2200 beta=(MagickRealType) (QuantumScale*(QuantumRange-
2201 image->colormap[index].opacity));
2203 distance=fabs((
double) (alpha*GetPixelRed(p)-beta*
2204 image->colormap[index].red));
2205 mean_error_per_pixel+=distance;
2206 mean_error+=distance*distance;
2207 if (distance > maximum_error)
2208 maximum_error=distance;
2209 distance=fabs((
double) (alpha*GetPixelGreen(p)-beta*
2210 image->colormap[index].green));
2211 mean_error_per_pixel+=distance;
2212 mean_error+=distance*distance;
2213 if (distance > maximum_error)
2214 maximum_error=distance;
2215 distance=fabs((
double) (alpha*GetPixelBlue(p)-beta*
2216 image->colormap[index].blue));
2217 mean_error_per_pixel+=distance;
2218 mean_error+=distance*distance;
2219 if (distance > maximum_error)
2220 maximum_error=distance;
2224 image_view=DestroyCacheView(image_view);
2225 gamma=PerceptibleReciprocal(area);
2226 image->error.mean_error_per_pixel=gamma*mean_error_per_pixel;
2227 image->error.normalized_mean_error=gamma*QuantumScale*QuantumScale*mean_error;
2228 image->error.normalized_maximum_error=QuantumScale*maximum_error;
2254 MagickExport
void GetQuantizeInfo(
QuantizeInfo *quantize_info)
2257 if (IsEventLogging() != MagickFalse)
2258 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
2259 (void) memset(quantize_info,0,
sizeof(*quantize_info));
2260 quantize_info->number_colors=256;
2261 quantize_info->dither=MagickTrue;
2262 quantize_info->dither_method=RiemersmaDitherMethod;
2263 quantize_info->colorspace=UndefinedColorspace;
2264 quantize_info->measure_error=MagickFalse;
2265 quantize_info->signature=MagickCoreSignature;
2302 static inline double MagickRound(
double x)
2307 if ((x-floor(x)) < (ceil(x)-x))
2312 MagickExport MagickBooleanType PosterizeImage(
Image *image,
const size_t levels,
2313 const MagickBooleanType dither)
2318 status=PosterizeImageChannel(image,DefaultChannels,levels,dither);
2322 MagickExport MagickBooleanType PosterizeImageChannel(
Image *image,
2323 const ChannelType channel,
const size_t levels,
const MagickBooleanType dither)
2325 #define PosterizeImageTag "Posterize/Image"
2326 #define PosterizePixel(pixel) ClampToQuantum((MagickRealType) QuantumRange*( \
2327 MagickRound(QuantumScale*pixel*(levels-1)))/MagickMax((ssize_t) levels-1,1))
2348 assert(image != (
Image *) NULL);
2349 assert(image->signature == MagickCoreSignature);
2350 if (IsEventLogging() != MagickFalse)
2351 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
2352 if (image->storage_class == PseudoClass)
2353 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2354 #pragma omp parallel for schedule(static) shared(progress,status) \
2355 magick_number_threads(image,image,image->colors,1)
2357 for (i=0; i < (ssize_t) image->colors; i++)
2362 if ((channel & RedChannel) != 0)
2363 image->colormap[i].red=PosterizePixel(image->colormap[i].red);
2364 if ((channel & GreenChannel) != 0)
2365 image->colormap[i].green=PosterizePixel(image->colormap[i].green);
2366 if ((channel & BlueChannel) != 0)
2367 image->colormap[i].blue=PosterizePixel(image->colormap[i].blue);
2368 if ((channel & OpacityChannel) != 0)
2369 image->colormap[i].opacity=PosterizePixel(image->colormap[i].opacity);
2376 exception=(&image->exception);
2377 image_view=AcquireAuthenticCacheView(image,exception);
2378 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2379 #pragma omp parallel for schedule(static) shared(progress,status) \
2380 magick_number_threads(image,image,image->rows,1)
2382 for (y=0; y < (ssize_t) image->rows; y++)
2385 *magick_restrict indexes;
2393 if (status == MagickFalse)
2395 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2401 indexes=GetCacheViewAuthenticIndexQueue(image_view);
2402 for (x=0; x < (ssize_t) image->columns; x++)
2404 if ((channel & RedChannel) != 0)
2405 SetPixelRed(q,PosterizePixel(GetPixelRed(q)));
2406 if ((channel & GreenChannel) != 0)
2407 SetPixelGreen(q,PosterizePixel(GetPixelGreen(q)));
2408 if ((channel & BlueChannel) != 0)
2409 SetPixelBlue(q,PosterizePixel(GetPixelBlue(q)));
2410 if (((channel & OpacityChannel) != 0) &&
2411 (image->matte != MagickFalse))
2412 SetPixelOpacity(q,PosterizePixel(GetPixelOpacity(q)));
2413 if (((channel & IndexChannel) != 0) &&
2414 (image->colorspace == CMYKColorspace))
2415 SetPixelIndex(indexes+x,PosterizePixel(GetPixelIndex(indexes+x)));
2418 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2420 if (image->progress_monitor != (MagickProgressMonitor) NULL)
2425 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2429 proceed=SetImageProgress(image,PosterizeImageTag,progress,image->rows);
2430 if (proceed == MagickFalse)
2434 image_view=DestroyCacheView(image_view);
2435 quantize_info=AcquireQuantizeInfo((
ImageInfo *) NULL);
2436 quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels*
2437 levels,MaxColormapSize+1);
2438 quantize_info->dither=dither;
2439 quantize_info->tree_depth=MaxTreeDepth;
2440 status=QuantizeImage(quantize_info,image);
2441 quantize_info=DestroyQuantizeInfo(quantize_info);
2484 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2485 for (i=0; i < (ssize_t) number_children; i++)
2486 if (node_info->child[i] != (
NodeInfo *) NULL)
2487 PruneChild(cube_info,node_info->child[i]);
2488 if (cube_info->nodes > cube_info->maximum_colors)
2493 parent=node_info->parent;
2494 parent->number_unique+=node_info->number_unique;
2495 parent->total_color.red+=node_info->total_color.red;
2496 parent->total_color.green+=node_info->total_color.green;
2497 parent->total_color.blue+=node_info->total_color.blue;
2498 parent->total_color.opacity+=node_info->total_color.opacity;
2499 parent->child[node_info->id]=(
NodeInfo *) NULL;
2540 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2541 for (i=0; i < (ssize_t) number_children; i++)
2542 if (node_info->child[i] != (
NodeInfo *) NULL)
2543 PruneLevel(cube_info,node_info->child[i]);
2544 if (node_info->level == cube_info->depth)
2545 PruneChild(cube_info,node_info);
2574 static void PruneToCubeDepth(
CubeInfo *cube_info,
const NodeInfo *node_info)
2585 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2586 for (i=0; i < (ssize_t) number_children; i++)
2587 if (node_info->child[i] != (
NodeInfo *) NULL)
2588 PruneToCubeDepth(cube_info,node_info->child[i]);
2589 if (node_info->level > cube_info->depth)
2590 PruneChild(cube_info,node_info);
2621 MagickExport MagickBooleanType QuantizeImage(
const QuantizeInfo *quantize_info,
2635 assert(quantize_info->signature == MagickCoreSignature);
2636 assert(image != (
Image *) NULL);
2637 assert(image->signature == MagickCoreSignature);
2638 if (IsEventLogging() != MagickFalse)
2639 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
2640 maximum_colors=quantize_info->number_colors;
2641 if (maximum_colors == 0)
2642 maximum_colors=MaxColormapSize;
2643 if (maximum_colors > MaxColormapSize)
2644 maximum_colors=MaxColormapSize;
2645 if (image->matte == MagickFalse)
2647 if (SetImageGray(image,&image->exception) != MagickFalse)
2648 (
void) SetGrayscaleImage(image);
2650 depth=quantize_info->tree_depth;
2659 colors=maximum_colors;
2660 for (depth=1; colors != 0; depth++)
2662 if ((quantize_info->dither != MagickFalse) && (depth > 2))
2664 if ((image->matte != MagickFalse) && (depth > 5))
2666 if (SetImageGray(image,&image->exception) != MagickFalse)
2672 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2673 if (cube_info == (
CubeInfo *) NULL)
2674 ThrowBinaryImageException(ResourceLimitError,
"MemoryAllocationFailed",
2676 status=ClassifyImageColors(cube_info,image,&image->exception);
2677 if (status != MagickFalse)
2682 if (cube_info->colors > cube_info->maximum_colors)
2683 ReduceImageColors(image,cube_info);
2684 status=AssignImageColors(image,cube_info);
2686 DestroyCubeInfo(cube_info);
2718 MagickExport MagickBooleanType QuantizeImages(
const QuantizeInfo *quantize_info,
2731 MagickProgressMonitor
2743 assert(quantize_info->signature == MagickCoreSignature);
2744 assert(images != (
Image *) NULL);
2745 assert(images->signature == MagickCoreSignature);
2746 if (IsEventLogging() != MagickFalse)
2747 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",images->filename);
2748 if (GetNextImageInList(images) == (
Image *) NULL)
2753 status=QuantizeImage(quantize_info,images);
2757 maximum_colors=quantize_info->number_colors;
2758 if (maximum_colors == 0)
2759 maximum_colors=MaxColormapSize;
2760 if (maximum_colors > MaxColormapSize)
2761 maximum_colors=MaxColormapSize;
2762 depth=quantize_info->tree_depth;
2771 colors=maximum_colors;
2772 for (depth=1; colors != 0; depth++)
2774 if (quantize_info->dither != MagickFalse)
2780 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2781 if (cube_info == (
CubeInfo *) NULL)
2783 (void) ThrowMagickException(&images->exception,GetMagickModule(),
2784 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",images->filename);
2785 return(MagickFalse);
2787 number_images=GetImageListLength(images);
2789 for (i=0; image != (
Image *) NULL; i++)
2791 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL,
2792 image->client_data);
2793 status=ClassifyImageColors(cube_info,image,&image->exception);
2794 if (status == MagickFalse)
2796 (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
2797 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2799 if (proceed == MagickFalse)
2801 image=GetNextImageInList(image);
2803 if (status != MagickFalse)
2808 ReduceImageColors(images,cube_info);
2810 for (i=0; image != (
Image *) NULL; i++)
2812 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor)
2813 NULL,image->client_data);
2814 status=AssignImageColors(image,cube_info);
2815 if (status == MagickFalse)
2817 (void) SetImageProgressMonitor(image,progress_monitor,
2818 image->client_data);
2819 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2821 if (proceed == MagickFalse)
2823 image=GetNextImageInList(image);
2826 DestroyCubeInfo(cube_info);
2863 static size_t QuantizeErrorFlatten(
const CubeInfo *cube_info,
2864 const NodeInfo *node_info,
const ssize_t offset,
2865 MagickRealType *quantize_error)
2874 if (offset >= (ssize_t) cube_info->nodes)
2876 quantize_error[offset]=node_info->quantize_error;
2878 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2879 for (i=0; i < (ssize_t) number_children ; i++)
2880 if (node_info->child[i] != (
NodeInfo *) NULL)
2881 n+=QuantizeErrorFlatten(cube_info,node_info->child[i],offset+n,
2922 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2923 for (i=0; i < (ssize_t) number_children; i++)
2924 if (node_info->child[i] != (
NodeInfo *) NULL)
2925 Reduce(cube_info,node_info->child[i]);
2926 if (node_info->quantize_error <= cube_info->pruning_threshold)
2927 PruneChild(cube_info,node_info);
2933 if (node_info->number_unique > 0)
2934 cube_info->colors++;
2935 if (node_info->quantize_error < cube_info->next_threshold)
2936 cube_info->next_threshold=node_info->quantize_error;
2995 static int MagickRealTypeCompare(
const void *error_p,
const void *error_q)
3001 p=(MagickRealType *) error_p;
3002 q=(MagickRealType *) error_q;
3005 if (fabs((
double) (*q-*p)) <= MagickEpsilon)
3010 static void ReduceImageColors(
const Image *image,
CubeInfo *cube_info)
3012 #define ReduceImageTag "Reduce/Image"
3023 cube_info->next_threshold=0.0;
3024 if (cube_info->colors > cube_info->maximum_colors)
3032 quantize_error=(MagickRealType *) AcquireQuantumMemory(cube_info->nodes,
3033 sizeof(*quantize_error));
3034 if (quantize_error != (MagickRealType *) NULL)
3036 (void) QuantizeErrorFlatten(cube_info,cube_info->root,0,
3038 qsort(quantize_error,cube_info->nodes,
sizeof(MagickRealType),
3039 MagickRealTypeCompare);
3040 if (cube_info->nodes > (110*(cube_info->maximum_colors+1)/100))
3041 cube_info->next_threshold=quantize_error[cube_info->nodes-110*
3042 (cube_info->maximum_colors+1)/100];
3043 quantize_error=(MagickRealType *) RelinquishMagickMemory(
3047 for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; )
3049 cube_info->pruning_threshold=cube_info->next_threshold;
3050 cube_info->next_threshold=cube_info->root->quantize_error-1;
3051 cube_info->colors=0;
3052 Reduce(cube_info,cube_info->root);
3053 offset=(MagickOffsetType) span-cube_info->colors;
3054 proceed=SetImageProgress(image,ReduceImageTag,offset,span-
3055 cube_info->maximum_colors+1);
3056 if (proceed == MagickFalse)
3089 MagickExport MagickBooleanType RemapImage(
const QuantizeInfo *quantize_info,
3101 assert(image != (
Image *) NULL);
3102 assert(image->signature == MagickCoreSignature);
3103 if (IsEventLogging() != MagickFalse)
3104 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
3105 assert(remap_image != (
Image *) NULL);
3106 assert(remap_image->signature == MagickCoreSignature);
3107 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3108 quantize_info->number_colors);
3109 if (cube_info == (
CubeInfo *) NULL)
3110 ThrowBinaryImageException(ResourceLimitError,
"MemoryAllocationFailed",
3112 status=ClassifyImageColors(cube_info,remap_image,&image->exception);
3113 if (status != MagickFalse)
3118 cube_info->quantize_info->number_colors=cube_info->colors;
3119 status=AssignImageColors(image,cube_info);
3121 DestroyCubeInfo(cube_info);
3153 MagickExport MagickBooleanType RemapImages(
const QuantizeInfo *quantize_info,
3165 assert(images != (
Image *) NULL);
3166 assert(images->signature == MagickCoreSignature);
3167 if (IsEventLogging() != MagickFalse)
3168 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",images->filename);
3170 if (remap_image == (
Image *) NULL)
3175 status=QuantizeImages(quantize_info,images);
3181 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3182 quantize_info->number_colors);
3183 if (cube_info == (
CubeInfo *) NULL)
3184 ThrowBinaryImageException(ResourceLimitError,
"MemoryAllocationFailed",
3186 status=ClassifyImageColors(cube_info,remap_image,&image->exception);
3187 if (status != MagickFalse)
3192 cube_info->quantize_info->number_colors=cube_info->colors;
3194 for ( ; image != (
Image *) NULL; image=GetNextImageInList(image))
3196 status=AssignImageColors(image,cube_info);
3197 if (status == MagickFalse)
3201 DestroyCubeInfo(cube_info);
3228 #if defined(__cplusplus) || defined(c_plusplus)
3232 static int IntensityCompare(
const void *x,
const void *y)
3243 intensity=PixelPacketIntensity(color_1)-PixelPacketIntensity(color_2);
3244 if (intensity < (
double) INT_MIN)
3245 intensity=(double) INT_MIN;
3246 if (intensity > (
double) INT_MAX)
3247 intensity=(
double) INT_MAX;
3248 return((
int) intensity);
3251 #if defined(__cplusplus) || defined(c_plusplus)
3255 static MagickBooleanType SetGrayscaleImage(
Image *image)
3278 assert(image != (
Image *) NULL);
3279 assert(image->signature == MagickCoreSignature);
3280 exception=(&image->exception);
3281 if (image->type != GrayscaleType)
3282 (void) TransformImageColorspace(image,GRAYColorspace);
3283 extent=MagickMax(image->colors+1,MagickMax(MaxColormapSize,MaxMap+1));
3284 colormap_index=(ssize_t *) AcquireQuantumMemory(extent,
3285 sizeof(*colormap_index));
3286 if (colormap_index == (ssize_t *) NULL)
3287 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3289 if (image->storage_class != PseudoClass)
3291 (void) memset(colormap_index,(-1),extent*
sizeof(*colormap_index));
3292 if (AcquireImageColormap(image,MaxColormapSize) == MagickFalse)
3294 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3295 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3300 image_view=AcquireAuthenticCacheView(image,exception);
3301 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3302 #pragma omp parallel for schedule(static) shared(status) \
3303 magick_number_threads(image,image,image->rows,1)
3305 for (y=0; y < (ssize_t) image->rows; y++)
3308 *magick_restrict indexes;
3316 if (status == MagickFalse)
3318 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
3325 indexes=GetCacheViewAuthenticIndexQueue(image_view);
3326 for (x=0; x < (ssize_t) image->columns; x++)
3331 intensity=ScaleQuantumToMap(GetPixelRed(q));
3332 if (colormap_index[intensity] < 0)
3334 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3335 #pragma omp critical (MagickCore_SetGrayscaleImage)
3337 if (colormap_index[intensity] < 0)
3339 colormap_index[intensity]=(ssize_t) image->colors;
3340 image->colormap[image->colors].red=GetPixelRed(q);
3341 image->colormap[image->colors].green=GetPixelGreen(q);
3342 image->colormap[image->colors].blue=GetPixelBlue(q);
3346 SetPixelIndex(indexes+x,colormap_index[intensity]);
3349 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3352 image_view=DestroyCacheView(image_view);
3354 (void) memset(colormap_index,0,extent*
sizeof(*colormap_index));
3355 for (i=0; i < (ssize_t) image->colors; i++)
3356 image->colormap[i].opacity=(Quantum) i;
3357 qsort((
void *) image->colormap,image->colors,
sizeof(
PixelPacket),
3359 colormap=(
PixelPacket *) AcquireQuantumMemory(image->colors,
3363 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3364 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3368 colormap[j]=image->colormap[0];
3369 for (i=0; i < (ssize_t) image->colors; i++)
3371 if (IsSameColor(image,&colormap[j],&image->colormap[i]) == MagickFalse)
3374 colormap[j]=image->colormap[i];
3376 colormap_index[(ssize_t) image->colormap[i].opacity]=j;
3378 image->colors=(size_t) (j+1);
3379 image->colormap=(
PixelPacket *) RelinquishMagickMemory(image->colormap);
3380 image->colormap=colormap;
3382 image_view=AcquireAuthenticCacheView(image,exception);
3383 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3384 #pragma omp parallel for schedule(static) shared(status) \
3385 magick_number_threads(image,image,image->rows,1)
3387 for (y=0; y < (ssize_t) image->rows; y++)
3390 *magick_restrict indexes;
3398 if (status == MagickFalse)
3400 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
3406 indexes=GetCacheViewAuthenticIndexQueue(image_view);
3407 for (x=0; x < (ssize_t) image->columns; x++)
3408 SetPixelIndex(indexes+x,colormap_index[ScaleQuantumToMap(GetPixelIndex(
3410 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3413 image_view=DestroyCacheView(image_view);
3414 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3415 image->type=GrayscaleType;
3416 if (SetImageMonochrome(image,&image->exception) != MagickFalse)
3417 image->type=BilevelType;