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)
1099 p=image->colormap+node_info->color_number;
1100 q=(&cube_info->target);
1102 if (cube_info->associate_alpha != MagickFalse)
1103 alpha=(MagickRealType) (QuantumScale*GetPixelAlpha(p)*
1104 QuantumScale*GetPixelAlpha(q));
1105 pixel=GetPixelRed(p)-GetPixelRed(q);
1106 if (IsHueCompatibleColorspace(image->colorspace) != MagickFalse)
1112 if (fabs((
double) pixel) > (QuantumRange/2))
1113 pixel-=QuantumRange;
1116 distance=alpha*pixel*pixel;
1117 if (distance <= cube_info->distance)
1119 pixel=GetPixelGreen(p)-GetPixelGreen(q);
1120 distance+=alpha*pixel*pixel;
1121 if (distance <= cube_info->distance)
1123 pixel=GetPixelBlue(p)-GetPixelBlue(q);
1124 distance+=alpha*pixel*pixel;
1125 if (distance <= cube_info->distance)
1127 cube_info->distance=distance;
1128 cube_info->color_number=node_info->color_number;
1158 MagickExport MagickBooleanType CompressImageColormap(
Image *image)
1163 assert(image != (
Image *) NULL);
1164 assert(image->signature == MagickCoreSignature);
1165 if (IsEventLogging() != MagickFalse)
1166 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
1167 if (IsPaletteImage(image,&image->exception) == MagickFalse)
1168 return(MagickFalse);
1169 GetQuantizeInfo(&quantize_info);
1170 quantize_info.number_colors=image->colors;
1171 quantize_info.tree_depth=MaxTreeDepth;
1172 return(QuantizeImage(&quantize_info,image));
1205 static void DefineImageColormap(
Image *image,
CubeInfo *cube_info,
1217 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1218 for (i=0; i < (ssize_t) number_children; i++)
1219 if (node_info->child[i] != (
NodeInfo *) NULL)
1220 DefineImageColormap(image,cube_info,node_info->child[i]);
1221 if (node_info->number_unique != 0)
1232 q=image->colormap+image->colors;
1233 alpha=(MagickRealType) ((MagickOffsetType) node_info->number_unique);
1234 alpha=PerceptibleReciprocal(alpha);
1235 if (cube_info->associate_alpha == MagickFalse)
1237 SetPixelRed(q,ClampToQuantum((MagickRealType) (alpha*
1238 QuantumRange*node_info->total_color.red)));
1239 SetPixelGreen(q,ClampToQuantum((MagickRealType) (alpha*
1240 QuantumRange*node_info->total_color.green)));
1241 SetPixelBlue(q,ClampToQuantum((MagickRealType) (alpha*
1242 QuantumRange*node_info->total_color.blue)));
1243 SetPixelOpacity(q,OpaqueOpacity);
1250 opacity=(MagickRealType) (alpha*QuantumRange*
1251 node_info->total_color.opacity);
1252 SetPixelOpacity(q,ClampToQuantum(opacity));
1253 if (q->opacity == OpaqueOpacity)
1255 SetPixelRed(q,ClampToQuantum((MagickRealType) (alpha*
1256 QuantumRange*node_info->total_color.red)));
1257 SetPixelGreen(q,ClampToQuantum((MagickRealType) (alpha*
1258 QuantumRange*node_info->total_color.green)));
1259 SetPixelBlue(q,ClampToQuantum((MagickRealType) (alpha*
1260 QuantumRange*node_info->total_color.blue)));
1267 gamma=(double) (QuantumScale*(QuantumRange-(
double) q->opacity));
1268 gamma=PerceptibleReciprocal(gamma);
1269 SetPixelRed(q,ClampToQuantum((MagickRealType) (alpha*
1270 gamma*QuantumRange*node_info->total_color.red)));
1271 SetPixelGreen(q,ClampToQuantum((MagickRealType) (alpha*
1272 gamma*QuantumRange*node_info->total_color.green)));
1273 SetPixelBlue(q,ClampToQuantum((MagickRealType) (alpha*
1274 gamma*QuantumRange*node_info->total_color.blue)));
1275 if (node_info->number_unique > cube_info->transparent_pixels)
1277 cube_info->transparent_pixels=node_info->number_unique;
1278 cube_info->transparent_index=(ssize_t) image->colors;
1282 node_info->color_number=image->colors++;
1308 static void DestroyCubeInfo(
CubeInfo *cube_info)
1318 nodes=cube_info->node_queue->next;
1319 cube_info->node_queue->nodes=(
NodeInfo *) RelinquishMagickMemory(
1320 cube_info->node_queue->nodes);
1321 cube_info->node_queue=(
Nodes *) RelinquishMagickMemory(
1322 cube_info->node_queue);
1323 cube_info->node_queue=nodes;
1324 }
while (cube_info->node_queue != (
Nodes *) NULL);
1325 if (cube_info->memory_info != (
MemoryInfo *) NULL)
1326 cube_info->memory_info=RelinquishVirtualMemory(cube_info->memory_info);
1327 cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info);
1328 cube_info=(
CubeInfo *) RelinquishMagickMemory(cube_info);
1357 assert(quantize_info->signature == MagickCoreSignature);
1358 if (IsEventLogging() != MagickFalse)
1359 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1360 quantize_info->signature=(~MagickCoreSignature);
1361 quantize_info=(
QuantizeInfo *) RelinquishMagickMemory(quantize_info);
1362 return(quantize_info);
1399 for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++)
1417 number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
1422 (void) memset(pixels,0,number_threads*
sizeof(*pixels));
1423 for (i=0; i < (ssize_t) number_threads; i++)
1426 2*
sizeof(**pixels));
1428 return(DestroyPixelTLS(pixels));
1433 static inline ssize_t CacheOffset(
CubeInfo *cube_info,
1436 #define RedShift(pixel) (((pixel) >> CacheShift) << (0*(8-CacheShift)))
1437 #define GreenShift(pixel) (((pixel) >> CacheShift) << (1*(8-CacheShift)))
1438 #define BlueShift(pixel) (((pixel) >> CacheShift) << (2*(8-CacheShift)))
1439 #define AlphaShift(pixel) (((pixel) >> CacheShift) << (3*(8-CacheShift)))
1444 offset=(ssize_t) (RedShift(ScaleQuantumToChar(ClampPixel(pixel->red))) |
1445 GreenShift(ScaleQuantumToChar(ClampPixel(pixel->green))) |
1446 BlueShift(ScaleQuantumToChar(ClampPixel(pixel->blue))));
1447 if (cube_info->associate_alpha != MagickFalse)
1448 offset|=AlphaShift(ScaleQuantumToChar(ClampPixel(pixel->opacity)));
1452 static MagickBooleanType FloydSteinbergDither(
Image *image,
CubeInfo *cube_info)
1454 #define DitherImageTag "Dither/Image"
1474 pixels=AcquirePixelTLS(image->columns);
1476 return(MagickFalse);
1477 exception=(&image->exception);
1479 image_view=AcquireAuthenticCacheView(image,exception);
1480 for (y=0; y < (ssize_t) image->rows; y++)
1483 id = GetOpenMPThreadId();
1493 *magick_restrict indexes;
1505 if (status == MagickFalse)
1507 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
1513 indexes=GetCacheViewAuthenticIndexQueue(image_view);
1515 current=pixels[id]+(y & 0x01)*image->columns;
1516 previous=pixels[
id]+((y+1) & 0x01)*image->columns;
1517 v=(ssize_t) ((y & 0x01) ? -1 : 1);
1518 for (x=0; x < (ssize_t) image->columns; x++)
1530 u=(y & 0x01) ? (ssize_t) image->columns-1-x : x;
1531 AssociateAlphaPixel(&cube,q+u,&pixel);
1534 pixel.red+=7.0*cube_info->diffusion*current[u-v].red/16;
1535 pixel.green+=7.0*cube_info->diffusion*current[u-v].green/16;
1536 pixel.blue+=7.0*cube_info->diffusion*current[u-v].blue/16;
1537 if (cube.associate_alpha != MagickFalse)
1538 pixel.opacity+=7.0*cube_info->diffusion*current[u-v].opacity/16;
1542 if (x < (ssize_t) (image->columns-1))
1544 pixel.red+=cube_info->diffusion*previous[u+v].red/16;
1545 pixel.green+=cube_info->diffusion*previous[u+v].green/16;
1546 pixel.blue+=cube_info->diffusion*previous[u+v].blue/16;
1547 if (cube.associate_alpha != MagickFalse)
1548 pixel.opacity+=cube_info->diffusion*previous[u+v].opacity/16;
1550 pixel.red+=5.0*cube_info->diffusion*previous[u].red/16;
1551 pixel.green+=5.0*cube_info->diffusion*previous[u].green/16;
1552 pixel.blue+=5.0*cube_info->diffusion*previous[u].blue/16;
1553 if (cube.associate_alpha != MagickFalse)
1554 pixel.opacity+=5.0*cube_info->diffusion*previous[u].opacity/16;
1557 pixel.red+=3.0*cube_info->diffusion*previous[u-v].red/16;
1558 pixel.green+=3.0*cube_info->diffusion*previous[u-v].green/16;
1559 pixel.blue+=3.0*cube_info->diffusion*previous[u-v].blue/16;
1560 if (cube.associate_alpha != MagickFalse)
1561 pixel.opacity+=3.0*cube_info->diffusion*
1562 previous[u-v].opacity/16;
1565 pixel.red=(MagickRealType) ClampPixel(pixel.red);
1566 pixel.green=(MagickRealType) ClampPixel(pixel.green);
1567 pixel.blue=(MagickRealType) ClampPixel(pixel.blue);
1568 if (cube.associate_alpha != MagickFalse)
1569 pixel.opacity=(MagickRealType) ClampPixel(pixel.opacity);
1570 i=CacheOffset(&cube,&pixel);
1571 if (cube.cache[i] < 0)
1582 node_info=cube.root;
1583 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1585 id=ColorToNodeId(&cube,&pixel,index);
1586 if (node_info->child[
id] == (
NodeInfo *) NULL)
1588 node_info=node_info->child[id];
1594 cube.distance=(MagickRealType) (4.0*(QuantumRange+1.0)*(QuantumRange+
1596 ClosestColor(image,&cube,node_info->parent);
1597 cube.cache[i]=(ssize_t) cube.color_number;
1602 index=(size_t) cube.cache[i];
1603 if (image->storage_class == PseudoClass)
1604 SetPixelIndex(indexes+u,index);
1605 if (cube.quantize_info->measure_error == MagickFalse)
1607 SetPixelRgb(q+u,image->colormap+index);
1608 if (cube.associate_alpha != MagickFalse)
1609 SetPixelOpacity(q+u,image->colormap[index].opacity);
1611 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1616 AssociateAlphaPixel(&cube,image->colormap+index,&color);
1617 current[u].red=pixel.red-color.red;
1618 current[u].green=pixel.green-color.green;
1619 current[u].blue=pixel.blue-color.blue;
1620 if (cube.associate_alpha != MagickFalse)
1621 current[u].opacity=pixel.opacity-color.opacity;
1622 if (image->progress_monitor != (MagickProgressMonitor) NULL)
1627 proceed=SetImageProgress(image,DitherImageTag,(MagickOffsetType) y,
1629 if (proceed == MagickFalse)
1634 image_view=DestroyCacheView(image_view);
1635 pixels=DestroyPixelTLS(pixels);
1639 static MagickBooleanType
1642 static MagickBooleanType Riemersma(
Image *image,
CacheView *image_view,
1643 CubeInfo *cube_info,
const size_t level,
const unsigned int direction)
1654 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1655 if (status != MagickFalse)
1656 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1657 if (status != MagickFalse)
1658 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1663 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1664 if (status != MagickFalse)
1665 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1666 if (status != MagickFalse)
1667 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1672 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1673 if (status != MagickFalse)
1674 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1675 if (status != MagickFalse)
1676 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1681 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1682 if (status != MagickFalse)
1683 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1684 if (status != MagickFalse)
1685 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1696 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1697 if (status != MagickFalse)
1698 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1699 if (status != MagickFalse)
1700 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1701 if (status != MagickFalse)
1702 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1703 if (status != MagickFalse)
1704 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1705 if (status != MagickFalse)
1706 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1707 if (status != MagickFalse)
1708 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1713 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1714 if (status != MagickFalse)
1715 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1716 if (status != MagickFalse)
1717 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1718 if (status != MagickFalse)
1719 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1720 if (status != MagickFalse)
1721 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1722 if (status != MagickFalse)
1723 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1724 if (status != MagickFalse)
1725 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1730 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1731 if (status != MagickFalse)
1732 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1733 if (status != MagickFalse)
1734 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1735 if (status != MagickFalse)
1736 status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1737 if (status != MagickFalse)
1738 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1739 if (status != MagickFalse)
1740 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1741 if (status != MagickFalse)
1742 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1747 status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1748 if (status != MagickFalse)
1749 status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1750 if (status != MagickFalse)
1751 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1752 if (status != MagickFalse)
1753 status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1754 if (status != MagickFalse)
1755 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1756 if (status != MagickFalse)
1757 status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1758 if (status != MagickFalse)
1759 status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1765 return(status != 0 ? MagickTrue : MagickFalse);
1768 static MagickBooleanType RiemersmaDither(
Image *image,
CacheView *image_view,
1769 CubeInfo *cube_info,
const unsigned int direction)
1771 #define DitherImageTag "Dither/Image"
1787 if ((p->x >= 0) && (p->x < (ssize_t) image->columns) &&
1788 (p->y >= 0) && (p->y < (ssize_t) image->rows))
1794 *magick_restrict indexes;
1805 exception=(&image->exception);
1806 q=GetCacheViewAuthenticPixels(image_view,p->x,p->y,1,1,exception);
1808 return(MagickFalse);
1809 indexes=GetCacheViewAuthenticIndexQueue(image_view);
1810 AssociateAlphaPixel(cube_info,q,&pixel);
1811 for (i=0; i < ErrorQueueLength; i++)
1813 pixel.red+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1815 pixel.green+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1817 pixel.blue+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1819 if (cube_info->associate_alpha != MagickFalse)
1820 pixel.opacity+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1821 p->error[i].opacity;
1823 pixel.red=(MagickRealType) ClampPixel(pixel.red);
1824 pixel.green=(MagickRealType) ClampPixel(pixel.green);
1825 pixel.blue=(MagickRealType) ClampPixel(pixel.blue);
1826 if (cube_info->associate_alpha != MagickFalse)
1827 pixel.opacity=(MagickRealType) ClampPixel(pixel.opacity);
1828 i=CacheOffset(cube_info,&pixel);
1829 if (p->cache[i] < 0)
1841 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1843 id=ColorToNodeId(cube_info,&pixel,index);
1844 if (node_info->child[
id] == (
NodeInfo *) NULL)
1846 node_info=node_info->child[id];
1852 p->distance=(MagickRealType) (4.0*(QuantumRange+1.0)*((MagickRealType)
1853 QuantumRange+1.0)+1.0);
1854 ClosestColor(image,p,node_info->parent);
1855 p->cache[i]=(ssize_t) p->color_number;
1860 index=(size_t) (1*p->cache[i]);
1861 if (image->storage_class == PseudoClass)
1862 *indexes=(IndexPacket) index;
1863 if (cube_info->quantize_info->measure_error == MagickFalse)
1865 SetPixelRgb(q,image->colormap+index);
1866 if (cube_info->associate_alpha != MagickFalse)
1867 SetPixelOpacity(q,image->colormap[index].opacity);
1869 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1870 return(MagickFalse);
1874 (void) memmove(p->error,p->error+1,(ErrorQueueLength-1)*
1875 sizeof(p->error[0]));
1876 AssociateAlphaPixel(cube_info,image->colormap+index,&color);
1877 p->error[ErrorQueueLength-1].red=pixel.red-color.red;
1878 p->error[ErrorQueueLength-1].green=pixel.green-color.green;
1879 p->error[ErrorQueueLength-1].blue=pixel.blue-color.blue;
1880 if (cube_info->associate_alpha != MagickFalse)
1881 p->error[ErrorQueueLength-1].opacity=pixel.opacity-color.opacity;
1882 proceed=SetImageProgress(image,DitherImageTag,p->offset,p->span);
1883 if (proceed == MagickFalse)
1884 return(MagickFalse);
1889 case WestGravity: p->x--;
break;
1890 case EastGravity: p->x++;
break;
1891 case NorthGravity: p->y--;
break;
1892 case SouthGravity: p->y++;
break;
1897 static MagickBooleanType DitherImage(
Image *image,
CubeInfo *cube_info)
1912 artifact=GetImageArtifact(image,
"dither:diffusion-amount");
1913 if (artifact != (
const char *) NULL)
1914 cube_info->diffusion=StringToDoubleInterval(artifact,1.0);
1915 if (cube_info->quantize_info->dither_method != RiemersmaDitherMethod)
1916 return(FloydSteinbergDither(image,cube_info));
1920 (void) memset(cube_info->error,0,ErrorQueueLength*
sizeof(*cube_info->error));
1923 extent=MagickMax(image->columns,image->rows);
1924 level=(size_t) log2((
double) extent);
1925 if ((1UL << level) < extent)
1927 cube_info->offset=0;
1928 cube_info->span=(MagickSizeType) image->columns*image->rows;
1929 image_view=AcquireAuthenticCacheView(image,&image->exception);
1932 status=Riemersma(image,image_view,cube_info,level,NorthGravity);
1933 if (status != MagickFalse)
1934 status=RiemersmaDither(image,image_view,cube_info,ForgetGravity);
1935 image_view=DestroyCacheView(image_view);
1974 const size_t depth,
const size_t maximum_colors)
1991 cube_info=(
CubeInfo *) AcquireMagickMemory(
sizeof(*cube_info));
1992 if (cube_info == (
CubeInfo *) NULL)
1994 (void) memset(cube_info,0,
sizeof(*cube_info));
1995 cube_info->depth=depth;
1996 if (cube_info->depth > MaxTreeDepth)
1997 cube_info->depth=MaxTreeDepth;
1998 if (cube_info->depth < 2)
2000 cube_info->maximum_colors=maximum_colors;
2004 cube_info->root=GetNodeInfo(cube_info,0,0,(
NodeInfo *) NULL);
2005 if (cube_info->root == (
NodeInfo *) NULL)
2007 cube_info->root->parent=cube_info->root;
2008 cube_info->quantize_info=CloneQuantizeInfo(quantize_info);
2009 if (cube_info->quantize_info->dither == MagickFalse)
2014 length=(size_t) (1UL << (4*(8-CacheShift)));
2015 cube_info->memory_info=AcquireVirtualMemory(length,
sizeof(*cube_info->cache));
2016 if (cube_info->memory_info == (
MemoryInfo *) NULL)
2018 cube_info->cache=(ssize_t *) GetVirtualMemoryBlob(cube_info->memory_info);
2022 (void) memset(cube_info->cache,(-1),
sizeof(*cube_info->cache)*length);
2027 for (i=0; i < ErrorQueueLength; i++)
2029 cube_info->weights[i]=PerceptibleReciprocal(weight);
2030 weight*=exp(log(1.0/ErrorRelativeWeight)/(ErrorQueueLength-1.0));
2032 cube_info->diffusion=1.0;
2065 const size_t level,
NodeInfo *parent)
2070 if (cube_info->free_nodes == 0)
2078 nodes=(
Nodes *) AcquireMagickMemory(
sizeof(*nodes));
2079 if (nodes == (
Nodes *) NULL)
2081 nodes->nodes=(
NodeInfo *) AcquireQuantumMemory(NodesInAList,
2082 sizeof(*nodes->nodes));
2083 if (nodes->nodes == (
NodeInfo *) NULL)
2085 nodes->next=cube_info->node_queue;
2086 cube_info->node_queue=nodes;
2087 cube_info->next_node=nodes->nodes;
2088 cube_info->free_nodes=NodesInAList;
2091 cube_info->free_nodes--;
2092 node_info=cube_info->next_node++;
2093 (void) memset(node_info,0,
sizeof(*node_info));
2094 node_info->parent=parent;
2096 node_info->level=level;
2139 MagickExport MagickBooleanType GetImageQuantizeError(
Image *image)
2158 mean_error_per_pixel;
2164 assert(image != (
Image *) NULL);
2165 assert(image->signature == MagickCoreSignature);
2166 if (IsEventLogging() != MagickFalse)
2167 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
2168 image->total_colors=GetNumberColors(image,(FILE *) NULL,&image->exception);
2169 (void) memset(&image->error,0,
sizeof(image->error));
2170 if (image->storage_class == DirectClass)
2174 area=3.0*image->columns*image->rows;
2176 mean_error_per_pixel=0.0;
2178 exception=(&image->exception);
2179 image_view=AcquireVirtualCacheView(image,exception);
2180 for (y=0; y < (ssize_t) image->rows; y++)
2188 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
2191 indexes=GetCacheViewAuthenticIndexQueue(image_view);
2192 for (x=0; x < (ssize_t) image->columns; x++)
2194 index=(ssize_t) GetPixelIndex(indexes+x);
2195 if (image->matte != MagickFalse)
2197 alpha=(MagickRealType) (QuantumScale*(GetPixelAlpha(p)));
2198 beta=(MagickRealType) (QuantumScale*(QuantumRange-
2199 image->colormap[index].opacity));
2201 distance=fabs((
double) (alpha*GetPixelRed(p)-beta*
2202 image->colormap[index].red));
2203 mean_error_per_pixel+=distance;
2204 mean_error+=distance*distance;
2205 if (distance > maximum_error)
2206 maximum_error=distance;
2207 distance=fabs((
double) (alpha*GetPixelGreen(p)-beta*
2208 image->colormap[index].green));
2209 mean_error_per_pixel+=distance;
2210 mean_error+=distance*distance;
2211 if (distance > maximum_error)
2212 maximum_error=distance;
2213 distance=fabs((
double) (alpha*GetPixelBlue(p)-beta*
2214 image->colormap[index].blue));
2215 mean_error_per_pixel+=distance;
2216 mean_error+=distance*distance;
2217 if (distance > maximum_error)
2218 maximum_error=distance;
2222 image_view=DestroyCacheView(image_view);
2223 gamma=PerceptibleReciprocal(area);
2224 image->error.mean_error_per_pixel=gamma*mean_error_per_pixel;
2225 image->error.normalized_mean_error=gamma*QuantumScale*QuantumScale*mean_error;
2226 image->error.normalized_maximum_error=QuantumScale*maximum_error;
2252 MagickExport
void GetQuantizeInfo(
QuantizeInfo *quantize_info)
2255 if (IsEventLogging() != MagickFalse)
2256 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
2257 (void) memset(quantize_info,0,
sizeof(*quantize_info));
2258 quantize_info->number_colors=256;
2259 quantize_info->dither=MagickTrue;
2260 quantize_info->dither_method=RiemersmaDitherMethod;
2261 quantize_info->colorspace=UndefinedColorspace;
2262 quantize_info->measure_error=MagickFalse;
2263 quantize_info->signature=MagickCoreSignature;
2300 static inline double MagickRound(
double x)
2305 if ((x-floor(x)) < (ceil(x)-x))
2310 MagickExport MagickBooleanType PosterizeImage(
Image *image,
const size_t levels,
2311 const MagickBooleanType dither)
2316 status=PosterizeImageChannel(image,DefaultChannels,levels,dither);
2320 MagickExport MagickBooleanType PosterizeImageChannel(
Image *image,
2321 const ChannelType channel,
const size_t levels,
const MagickBooleanType dither)
2323 #define PosterizeImageTag "Posterize/Image"
2324 #define PosterizePixel(pixel) ClampToQuantum((MagickRealType) QuantumRange*( \
2325 MagickRound(QuantumScale*pixel*(levels-1)))/MagickMax((ssize_t) levels-1,1))
2346 assert(image != (
Image *) NULL);
2347 assert(image->signature == MagickCoreSignature);
2348 if (IsEventLogging() != MagickFalse)
2349 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
2350 if (image->storage_class == PseudoClass)
2351 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2352 #pragma omp parallel for schedule(static) shared(progress,status) \
2353 magick_number_threads(image,image,image->colors,1)
2355 for (i=0; i < (ssize_t) image->colors; i++)
2360 if ((channel & RedChannel) != 0)
2361 image->colormap[i].red=PosterizePixel(image->colormap[i].red);
2362 if ((channel & GreenChannel) != 0)
2363 image->colormap[i].green=PosterizePixel(image->colormap[i].green);
2364 if ((channel & BlueChannel) != 0)
2365 image->colormap[i].blue=PosterizePixel(image->colormap[i].blue);
2366 if ((channel & OpacityChannel) != 0)
2367 image->colormap[i].opacity=PosterizePixel(image->colormap[i].opacity);
2374 exception=(&image->exception);
2375 image_view=AcquireAuthenticCacheView(image,exception);
2376 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2377 #pragma omp parallel for schedule(static) shared(progress,status) \
2378 magick_number_threads(image,image,image->rows,1)
2380 for (y=0; y < (ssize_t) image->rows; y++)
2383 *magick_restrict indexes;
2391 if (status == MagickFalse)
2393 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2399 indexes=GetCacheViewAuthenticIndexQueue(image_view);
2400 for (x=0; x < (ssize_t) image->columns; x++)
2402 if ((channel & RedChannel) != 0)
2403 SetPixelRed(q,PosterizePixel(GetPixelRed(q)));
2404 if ((channel & GreenChannel) != 0)
2405 SetPixelGreen(q,PosterizePixel(GetPixelGreen(q)));
2406 if ((channel & BlueChannel) != 0)
2407 SetPixelBlue(q,PosterizePixel(GetPixelBlue(q)));
2408 if (((channel & OpacityChannel) != 0) &&
2409 (image->matte != MagickFalse))
2410 SetPixelOpacity(q,PosterizePixel(GetPixelOpacity(q)));
2411 if (((channel & IndexChannel) != 0) &&
2412 (image->colorspace == CMYKColorspace))
2413 SetPixelIndex(indexes+x,PosterizePixel(GetPixelIndex(indexes+x)));
2416 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2418 if (image->progress_monitor != (MagickProgressMonitor) NULL)
2423 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2427 proceed=SetImageProgress(image,PosterizeImageTag,progress,image->rows);
2428 if (proceed == MagickFalse)
2432 image_view=DestroyCacheView(image_view);
2433 quantize_info=AcquireQuantizeInfo((
ImageInfo *) NULL);
2434 quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels*
2435 levels,MaxColormapSize+1);
2436 quantize_info->dither=dither;
2437 quantize_info->tree_depth=MaxTreeDepth;
2438 status=QuantizeImage(quantize_info,image);
2439 quantize_info=DestroyQuantizeInfo(quantize_info);
2482 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2483 for (i=0; i < (ssize_t) number_children; i++)
2484 if (node_info->child[i] != (
NodeInfo *) NULL)
2485 PruneChild(cube_info,node_info->child[i]);
2486 if (cube_info->nodes > cube_info->maximum_colors)
2491 parent=node_info->parent;
2492 parent->number_unique+=node_info->number_unique;
2493 parent->total_color.red+=node_info->total_color.red;
2494 parent->total_color.green+=node_info->total_color.green;
2495 parent->total_color.blue+=node_info->total_color.blue;
2496 parent->total_color.opacity+=node_info->total_color.opacity;
2497 parent->child[node_info->id]=(
NodeInfo *) NULL;
2538 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2539 for (i=0; i < (ssize_t) number_children; i++)
2540 if (node_info->child[i] != (
NodeInfo *) NULL)
2541 PruneLevel(cube_info,node_info->child[i]);
2542 if (node_info->level == cube_info->depth)
2543 PruneChild(cube_info,node_info);
2572 static void PruneToCubeDepth(
CubeInfo *cube_info,
const NodeInfo *node_info)
2583 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2584 for (i=0; i < (ssize_t) number_children; i++)
2585 if (node_info->child[i] != (
NodeInfo *) NULL)
2586 PruneToCubeDepth(cube_info,node_info->child[i]);
2587 if (node_info->level > cube_info->depth)
2588 PruneChild(cube_info,node_info);
2619 MagickExport MagickBooleanType QuantizeImage(
const QuantizeInfo *quantize_info,
2633 assert(quantize_info->signature == MagickCoreSignature);
2634 assert(image != (
Image *) NULL);
2635 assert(image->signature == MagickCoreSignature);
2636 if (IsEventLogging() != MagickFalse)
2637 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
2638 maximum_colors=quantize_info->number_colors;
2639 if (maximum_colors == 0)
2640 maximum_colors=MaxColormapSize;
2641 if (maximum_colors > MaxColormapSize)
2642 maximum_colors=MaxColormapSize;
2643 if (image->matte == MagickFalse)
2645 if (SetImageGray(image,&image->exception) != MagickFalse)
2646 (
void) SetGrayscaleImage(image);
2648 depth=quantize_info->tree_depth;
2657 colors=maximum_colors;
2658 for (depth=1; colors != 0; depth++)
2660 if ((quantize_info->dither != MagickFalse) && (depth > 2))
2662 if ((image->matte != MagickFalse) && (depth > 5))
2664 if (SetImageGray(image,&image->exception) != MagickFalse)
2670 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2671 if (cube_info == (
CubeInfo *) NULL)
2672 ThrowBinaryImageException(ResourceLimitError,
"MemoryAllocationFailed",
2674 status=ClassifyImageColors(cube_info,image,&image->exception);
2675 if (status != MagickFalse)
2680 if (cube_info->colors > cube_info->maximum_colors)
2681 ReduceImageColors(image,cube_info);
2682 status=AssignImageColors(image,cube_info);
2684 DestroyCubeInfo(cube_info);
2716 MagickExport MagickBooleanType QuantizeImages(
const QuantizeInfo *quantize_info,
2729 MagickProgressMonitor
2741 assert(quantize_info->signature == MagickCoreSignature);
2742 assert(images != (
Image *) NULL);
2743 assert(images->signature == MagickCoreSignature);
2744 if (IsEventLogging() != MagickFalse)
2745 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",images->filename);
2746 if (GetNextImageInList(images) == (
Image *) NULL)
2751 status=QuantizeImage(quantize_info,images);
2755 maximum_colors=quantize_info->number_colors;
2756 if (maximum_colors == 0)
2757 maximum_colors=MaxColormapSize;
2758 if (maximum_colors > MaxColormapSize)
2759 maximum_colors=MaxColormapSize;
2760 depth=quantize_info->tree_depth;
2769 colors=maximum_colors;
2770 for (depth=1; colors != 0; depth++)
2772 if (quantize_info->dither != MagickFalse)
2778 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2779 if (cube_info == (
CubeInfo *) NULL)
2781 (void) ThrowMagickException(&images->exception,GetMagickModule(),
2782 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",images->filename);
2783 return(MagickFalse);
2785 number_images=GetImageListLength(images);
2787 for (i=0; image != (
Image *) NULL; i++)
2789 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL,
2790 image->client_data);
2791 status=ClassifyImageColors(cube_info,image,&image->exception);
2792 if (status == MagickFalse)
2794 (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
2795 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2797 if (proceed == MagickFalse)
2799 image=GetNextImageInList(image);
2801 if (status != MagickFalse)
2806 ReduceImageColors(images,cube_info);
2808 for (i=0; image != (
Image *) NULL; i++)
2810 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor)
2811 NULL,image->client_data);
2812 status=AssignImageColors(image,cube_info);
2813 if (status == MagickFalse)
2815 (void) SetImageProgressMonitor(image,progress_monitor,
2816 image->client_data);
2817 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2819 if (proceed == MagickFalse)
2821 image=GetNextImageInList(image);
2824 DestroyCubeInfo(cube_info);
2861 static size_t QuantizeErrorFlatten(
const CubeInfo *cube_info,
2862 const NodeInfo *node_info,
const ssize_t offset,
2863 MagickRealType *quantize_error)
2872 if (offset >= (ssize_t) cube_info->nodes)
2874 quantize_error[offset]=node_info->quantize_error;
2876 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2877 for (i=0; i < (ssize_t) number_children ; i++)
2878 if (node_info->child[i] != (
NodeInfo *) NULL)
2879 n+=QuantizeErrorFlatten(cube_info,node_info->child[i],offset+n,
2920 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2921 for (i=0; i < (ssize_t) number_children; i++)
2922 if (node_info->child[i] != (
NodeInfo *) NULL)
2923 Reduce(cube_info,node_info->child[i]);
2924 if (node_info->quantize_error <= cube_info->pruning_threshold)
2925 PruneChild(cube_info,node_info);
2931 if (node_info->number_unique > 0)
2932 cube_info->colors++;
2933 if (node_info->quantize_error < cube_info->next_threshold)
2934 cube_info->next_threshold=node_info->quantize_error;
2993 static int MagickRealTypeCompare(
const void *error_p,
const void *error_q)
2999 p=(MagickRealType *) error_p;
3000 q=(MagickRealType *) error_q;
3003 if (fabs((
double) (*q-*p)) <= MagickEpsilon)
3008 static void ReduceImageColors(
const Image *image,
CubeInfo *cube_info)
3010 #define ReduceImageTag "Reduce/Image"
3021 cube_info->next_threshold=0.0;
3022 if (cube_info->colors > cube_info->maximum_colors)
3030 quantize_error=(MagickRealType *) AcquireQuantumMemory(cube_info->nodes,
3031 sizeof(*quantize_error));
3032 if (quantize_error != (MagickRealType *) NULL)
3034 (void) QuantizeErrorFlatten(cube_info,cube_info->root,0,
3036 qsort(quantize_error,cube_info->nodes,
sizeof(MagickRealType),
3037 MagickRealTypeCompare);
3038 if (cube_info->nodes > (110*(cube_info->maximum_colors+1)/100))
3039 cube_info->next_threshold=quantize_error[cube_info->nodes-110*
3040 (cube_info->maximum_colors+1)/100];
3041 quantize_error=(MagickRealType *) RelinquishMagickMemory(
3045 for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; )
3047 cube_info->pruning_threshold=cube_info->next_threshold;
3048 cube_info->next_threshold=cube_info->root->quantize_error-1;
3049 cube_info->colors=0;
3050 Reduce(cube_info,cube_info->root);
3051 offset=(MagickOffsetType) span-cube_info->colors;
3052 proceed=SetImageProgress(image,ReduceImageTag,offset,span-
3053 cube_info->maximum_colors+1);
3054 if (proceed == MagickFalse)
3087 MagickExport MagickBooleanType RemapImage(
const QuantizeInfo *quantize_info,
3099 assert(image != (
Image *) NULL);
3100 assert(image->signature == MagickCoreSignature);
3101 if (IsEventLogging() != MagickFalse)
3102 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
3103 assert(remap_image != (
Image *) NULL);
3104 assert(remap_image->signature == MagickCoreSignature);
3105 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3106 quantize_info->number_colors);
3107 if (cube_info == (
CubeInfo *) NULL)
3108 ThrowBinaryImageException(ResourceLimitError,
"MemoryAllocationFailed",
3110 cube_info->quantize_info->colorspace=remap_image->colorspace;
3111 status=ClassifyImageColors(cube_info,remap_image,&image->exception);
3112 if (status != MagickFalse)
3117 cube_info->quantize_info->number_colors=cube_info->colors;
3118 status=AssignImageColors(image,cube_info);
3120 DestroyCubeInfo(cube_info);
3152 MagickExport MagickBooleanType RemapImages(
const QuantizeInfo *quantize_info,
3164 assert(images != (
Image *) NULL);
3165 assert(images->signature == MagickCoreSignature);
3166 if (IsEventLogging() != MagickFalse)
3167 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",images->filename);
3169 if (remap_image == (
Image *) NULL)
3174 status=QuantizeImages(quantize_info,images);
3180 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3181 quantize_info->number_colors);
3182 if (cube_info == (
CubeInfo *) NULL)
3183 ThrowBinaryImageException(ResourceLimitError,
"MemoryAllocationFailed",
3185 status=ClassifyImageColors(cube_info,remap_image,&image->exception);
3186 if (status != MagickFalse)
3191 cube_info->quantize_info->number_colors=cube_info->colors;
3193 for ( ; image != (
Image *) NULL; image=GetNextImageInList(image))
3195 status=AssignImageColors(image,cube_info);
3196 if (status == MagickFalse)
3200 DestroyCubeInfo(cube_info);
3227 #if defined(__cplusplus) || defined(c_plusplus)
3231 static int IntensityCompare(
const void *x,
const void *y)
3242 intensity=PixelPacketIntensity(color_1)-PixelPacketIntensity(color_2);
3243 if (intensity < (
double) INT_MIN)
3244 intensity=(double) INT_MIN;
3245 if (intensity > (
double) INT_MAX)
3246 intensity=(
double) INT_MAX;
3247 return((
int) intensity);
3250 #if defined(__cplusplus) || defined(c_plusplus)
3254 static MagickBooleanType SetGrayscaleImage(
Image *image)
3277 assert(image != (
Image *) NULL);
3278 assert(image->signature == MagickCoreSignature);
3279 exception=(&image->exception);
3280 if (image->type != GrayscaleType)
3281 (void) TransformImageColorspace(image,GRAYColorspace);
3282 extent=MagickMax(image->colors+1,MagickMax(MaxColormapSize,MaxMap+1));
3283 colormap_index=(ssize_t *) AcquireQuantumMemory(extent,
3284 sizeof(*colormap_index));
3285 if (colormap_index == (ssize_t *) NULL)
3286 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3288 if (image->storage_class != PseudoClass)
3290 (void) memset(colormap_index,(-1),extent*
sizeof(*colormap_index));
3291 if (AcquireImageColormap(image,MaxColormapSize) == MagickFalse)
3293 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3294 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3299 image_view=AcquireAuthenticCacheView(image,exception);
3300 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3301 #pragma omp parallel for schedule(static) shared(status) \
3302 magick_number_threads(image,image,image->rows,1)
3304 for (y=0; y < (ssize_t) image->rows; y++)
3307 *magick_restrict indexes;
3315 if (status == MagickFalse)
3317 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
3324 indexes=GetCacheViewAuthenticIndexQueue(image_view);
3325 for (x=0; x < (ssize_t) image->columns; x++)
3330 intensity=ScaleQuantumToMap(GetPixelRed(q));
3331 if (colormap_index[intensity] < 0)
3333 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3334 #pragma omp critical (MagickCore_SetGrayscaleImage)
3336 if (colormap_index[intensity] < 0)
3338 colormap_index[intensity]=(ssize_t) image->colors;
3339 image->colormap[image->colors].red=GetPixelRed(q);
3340 image->colormap[image->colors].green=GetPixelGreen(q);
3341 image->colormap[image->colors].blue=GetPixelBlue(q);
3345 SetPixelIndex(indexes+x,colormap_index[intensity]);
3348 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3351 image_view=DestroyCacheView(image_view);
3353 (void) memset(colormap_index,0,extent*
sizeof(*colormap_index));
3354 for (i=0; i < (ssize_t) image->colors; i++)
3355 image->colormap[i].opacity=(Quantum) i;
3356 qsort((
void *) image->colormap,image->colors,
sizeof(
PixelPacket),
3358 colormap=(
PixelPacket *) AcquireQuantumMemory(image->colors,
3362 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3363 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3367 colormap[j]=image->colormap[0];
3368 for (i=0; i < (ssize_t) image->colors; i++)
3370 if (IsSameColor(image,&colormap[j],&image->colormap[i]) == MagickFalse)
3373 colormap[j]=image->colormap[i];
3375 colormap_index[(ssize_t) image->colormap[i].opacity]=j;
3377 image->colors=(size_t) (j+1);
3378 image->colormap=(
PixelPacket *) RelinquishMagickMemory(image->colormap);
3379 image->colormap=colormap;
3381 image_view=AcquireAuthenticCacheView(image,exception);
3382 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3383 #pragma omp parallel for schedule(static) shared(status) \
3384 magick_number_threads(image,image,image->rows,1)
3386 for (y=0; y < (ssize_t) image->rows; y++)
3389 *magick_restrict indexes;
3397 if (status == MagickFalse)
3399 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
3405 indexes=GetCacheViewAuthenticIndexQueue(image_view);
3406 for (x=0; x < (ssize_t) image->columns; x++)
3407 SetPixelIndex(indexes+x,colormap_index[ScaleQuantumToMap(GetPixelIndex(
3409 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3412 image_view=DestroyCacheView(image_view);
3413 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3414 image->type=GrayscaleType;
3415 if (SetImageMonochrome(image,&image->exception) != MagickFalse)
3416 image->type=BilevelType;