176 #include "MagickCore/studio.h"
177 #include "MagickCore/artifact.h"
178 #include "MagickCore/attribute.h"
179 #include "MagickCore/cache-view.h"
180 #include "MagickCore/color.h"
181 #include "MagickCore/color-private.h"
182 #include "MagickCore/colormap.h"
183 #include "MagickCore/colorspace.h"
184 #include "MagickCore/colorspace-private.h"
185 #include "MagickCore/compare.h"
186 #include "MagickCore/enhance.h"
187 #include "MagickCore/exception.h"
188 #include "MagickCore/exception-private.h"
189 #include "MagickCore/histogram.h"
190 #include "MagickCore/image.h"
191 #include "MagickCore/image-private.h"
192 #include "MagickCore/list.h"
193 #include "MagickCore/memory_.h"
194 #include "MagickCore/memory-private.h"
195 #include "MagickCore/monitor.h"
196 #include "MagickCore/monitor-private.h"
197 #include "MagickCore/option.h"
198 #include "MagickCore/pixel-accessor.h"
199 #include "MagickCore/property.h"
200 #include "MagickCore/quantize.h"
201 #include "MagickCore/quantum.h"
202 #include "MagickCore/quantum-private.h"
203 #include "MagickCore/random_.h"
204 #include "MagickCore/resource_.h"
205 #include "MagickCore/string_.h"
206 #include "MagickCore/string-private.h"
207 #include "MagickCore/thread-private.h"
212 #if !defined(__APPLE__) && !defined(TARGET_OS_IPHONE)
217 #define ErrorQueueLength 16
218 #define ErrorRelativeWeight PerceptibleReciprocal(16)
219 #define MaxNodes 266817
220 #define MaxTreeDepth 8
221 #define NodesInAList 1920
306 error[ErrorQueueLength];
310 weights[ErrorQueueLength];
336 *GetCubeInfo(
const QuantizeInfo *,
const size_t,
const size_t);
341 static MagickBooleanType
383 quantize_info=(
QuantizeInfo *) AcquireCriticalMemory(
sizeof(*quantize_info));
384 GetQuantizeInfo(quantize_info);
390 quantize_info->dither_method=image_info->dither == MagickFalse ?
391 NoDitherMethod : RiemersmaDitherMethod;
392 option=GetImageOption(image_info,
"dither");
393 if (option != (
const char *) NULL)
394 quantize_info->dither_method=(DitherMethod) ParseCommandOption(
395 MagickDitherOptions,MagickFalse,option);
396 quantize_info->measure_error=image_info->verbose;
398 return(quantize_info);
441 static inline void AssociateAlphaPixel(
const Image *image,
447 if ((cube_info->associate_alpha == MagickFalse) ||
448 (GetPixelAlpha(image,pixel) == OpaqueAlpha))
450 alpha_pixel->red=(double) GetPixelRed(image,pixel);
451 alpha_pixel->green=(double) GetPixelGreen(image,pixel);
452 alpha_pixel->blue=(double) GetPixelBlue(image,pixel);
453 alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel);
456 alpha=(double) (QuantumScale*GetPixelAlpha(image,pixel));
457 alpha_pixel->red=alpha*GetPixelRed(image,pixel);
458 alpha_pixel->green=alpha*GetPixelGreen(image,pixel);
459 alpha_pixel->blue=alpha*GetPixelBlue(image,pixel);
460 alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel);
463 static inline void AssociateAlphaPixelInfo(
const CubeInfo *cube_info,
469 if ((cube_info->associate_alpha == MagickFalse) ||
470 (pixel->alpha == OpaqueAlpha))
472 alpha_pixel->red=(double) pixel->red;
473 alpha_pixel->green=(
double) pixel->green;
474 alpha_pixel->blue=(double) pixel->blue;
475 alpha_pixel->alpha=(
double) pixel->alpha;
478 alpha=(double) (QuantumScale*pixel->alpha);
479 alpha_pixel->red=alpha*pixel->red;
480 alpha_pixel->green=alpha*pixel->green;
481 alpha_pixel->blue=alpha*pixel->blue;
482 alpha_pixel->alpha=(double) pixel->alpha;
485 static inline size_t ColorToNodeId(
const CubeInfo *cube_info,
491 id=(size_t) (((ScaleQuantumToChar(ClampPixel(pixel->red)) >> index) & 0x01) |
492 ((ScaleQuantumToChar(ClampPixel(pixel->green)) >> index) & 0x01) << 1 |
493 ((ScaleQuantumToChar(ClampPixel(pixel->blue)) >> index) & 0x01) << 2);
494 if (cube_info->associate_alpha != MagickFalse)
495 id|=((ScaleQuantumToChar(ClampPixel(pixel->alpha)) >> index) & 0x1) << 3;
499 static MagickBooleanType AssignImageColors(
Image *image,
CubeInfo *cube_info,
502 #define AssignImageTag "Assign/Image"
513 colorspace=image->colorspace;
514 if (cube_info->quantize_info->colorspace != UndefinedColorspace)
515 (void) TransformImageColorspace(image,cube_info->quantize_info->colorspace,
517 cube_info->transparent_pixels=0;
518 cube_info->transparent_index=(-1);
519 if (SetImageColormap(image,cube_info,exception) == MagickFalse)
524 if (cube_info->quantize_info->dither_method != NoDitherMethod)
525 (void) DitherImage(image,cube_info,exception);
535 image_view=AcquireAuthenticCacheView(image,exception);
536 #if defined(MAGICKCORE_OPENMP_SUPPORT)
537 #pragma omp parallel for schedule(static) shared(status) \
538 magick_number_threads(image,image,image->rows,1)
540 for (y=0; y < (ssize_t) image->rows; y++)
552 if (status == MagickFalse)
554 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
556 if (q == (Quantum *) NULL)
562 for (x=0; x < (ssize_t) image->columns; x+=count)
580 for (count=1; (x+count) < (ssize_t) image->columns; count++)
585 GetPixelInfoPixel(image,q+count*GetPixelChannels(image),&packet);
586 if (IsPixelEquivalent(image,q,&packet) == MagickFalse)
589 AssociateAlphaPixel(image,&cube,q,&pixel);
591 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
593 id=ColorToNodeId(&cube,&pixel,index);
594 if (node_info->child[
id] == (
NodeInfo *) NULL)
596 node_info=node_info->child[id];
602 cube.distance=(double) (4.0*(QuantumRange+1.0)*(QuantumRange+1.0)+
604 ClosestColor(image,&cube,node_info->parent);
605 index=cube.color_number;
606 for (i=0; i < (ssize_t) count; i++)
608 if (image->storage_class == PseudoClass)
609 SetPixelIndex(image,(Quantum) index,q);
610 if (cube.quantize_info->measure_error == MagickFalse)
612 SetPixelRed(image,ClampToQuantum(
613 image->colormap[index].red),q);
614 SetPixelGreen(image,ClampToQuantum(
615 image->colormap[index].green),q);
616 SetPixelBlue(image,ClampToQuantum(
617 image->colormap[index].blue),q);
618 if (cube.associate_alpha != MagickFalse)
619 SetPixelAlpha(image,ClampToQuantum(
620 image->colormap[index].alpha),q);
622 q+=GetPixelChannels(image);
625 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
627 if (image->progress_monitor != (MagickProgressMonitor) NULL)
632 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y,
634 if (proceed == MagickFalse)
638 image_view=DestroyCacheView(image_view);
640 if (cube_info->quantize_info->measure_error != MagickFalse)
641 (void) GetImageQuantizeError(image,exception);
642 if ((cube_info->quantize_info->number_colors == 2) &&
643 (IsGrayColorspace(cube_info->quantize_info->colorspace)))
651 intensity=GetPixelInfoLuma(image->colormap+0) < QuantumRange/2.0 ? 0.0 :
653 if (image->colors > 1)
656 if (GetPixelInfoLuma(image->colormap+0) >
657 GetPixelInfoLuma(image->colormap+1))
658 intensity=(double) QuantumRange;
660 image->colormap[0].red=intensity;
661 image->colormap[0].green=intensity;
662 image->colormap[0].blue=intensity;
663 if (image->colors > 1)
665 image->colormap[1].red=(double) QuantumRange-intensity;
666 image->colormap[1].green=(double) QuantumRange-intensity;
667 image->colormap[1].blue=(double) QuantumRange-intensity;
670 (void) SyncImage(image,exception);
671 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
672 (IssRGBCompatibleColorspace(colorspace) == MagickFalse))
673 (void) TransformImageColorspace(image,colorspace,exception);
738 static inline void SetAssociatedAlpha(
const Image *image,
CubeInfo *cube_info)
743 associate_alpha=image->alpha_trait != UndefinedPixelTrait ? MagickTrue :
745 if ((cube_info->quantize_info->number_colors == 2) &&
746 ((cube_info->quantize_info->colorspace == LinearGRAYColorspace) ||
747 (cube_info->quantize_info->colorspace == GRAYColorspace)))
748 associate_alpha=MagickFalse;
749 cube_info->associate_alpha=associate_alpha;
752 static MagickBooleanType ClassifyImageColors(
CubeInfo *cube_info,
755 #define ClassifyImageTag "Classify/Image"
787 SetAssociatedAlpha(image,cube_info);
788 if (cube_info->quantize_info->colorspace != image->colorspace)
790 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
791 (cube_info->quantize_info->colorspace != CMYKColorspace))
792 (void) TransformImageColorspace((
Image *) image,
793 cube_info->quantize_info->colorspace,exception);
795 if (IssRGBCompatibleColorspace(image->colorspace) == MagickFalse)
796 (
void) TransformImageColorspace((
Image *) image,sRGBColorspace,
799 midpoint.red=(double) QuantumRange/2.0;
800 midpoint.green=(double) QuantumRange/2.0;
801 midpoint.blue=(double) QuantumRange/2.0;
802 midpoint.alpha=(double) QuantumRange/2.0;
804 image_view=AcquireVirtualCacheView(image,exception);
805 for (y=0; y < (ssize_t) image->rows; y++)
813 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
814 if (p == (
const Quantum *) NULL)
816 if (cube_info->nodes > MaxNodes)
821 PruneLevel(cube_info,cube_info->root);
824 for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
829 for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
834 GetPixelInfoPixel(image,p+count*GetPixelChannels(image),&packet);
835 if (IsPixelEquivalent(image,p,&packet) == MagickFalse)
838 AssociateAlphaPixel(image,cube_info,p,&pixel);
839 index=MaxTreeDepth-1;
840 bisect=((double) QuantumRange+1.0)/2.0;
842 node_info=cube_info->root;
843 for (level=1; level <= MaxTreeDepth; level++)
849 id=ColorToNodeId(cube_info,&pixel,index);
850 mid.red+=(
id & 1) != 0 ? bisect : -bisect;
851 mid.green+=(
id & 2) != 0 ? bisect : -bisect;
852 mid.blue+=(
id & 4) != 0 ? bisect : -bisect;
853 mid.alpha+=(
id & 8) != 0 ? bisect : -bisect;
854 if (node_info->child[
id] == (
NodeInfo *) NULL)
859 node_info->child[id]=GetNodeInfo(cube_info,
id,level,node_info);
860 if (node_info->child[
id] == (
NodeInfo *) NULL)
862 (void) ThrowMagickException(exception,GetMagickModule(),
863 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",
867 if (level == MaxTreeDepth)
873 node_info=node_info->child[id];
874 error.red=QuantumScale*(pixel.red-mid.red);
875 error.green=QuantumScale*(pixel.green-mid.green);
876 error.blue=QuantumScale*(pixel.blue-mid.blue);
877 if (cube_info->associate_alpha != MagickFalse)
878 error.alpha=QuantumScale*(pixel.alpha-mid.alpha);
879 distance=(double) (error.red*error.red+error.green*error.green+
880 error.blue*error.blue+error.alpha*error.alpha);
881 if (IsNaN(distance) != 0)
883 node_info->quantize_error+=count*sqrt(distance);
884 cube_info->root->quantize_error+=node_info->quantize_error;
890 node_info->number_unique+=count;
891 node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red);
892 node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green);
893 node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue);
894 if (cube_info->associate_alpha != MagickFalse)
895 node_info->total_color.alpha+=count*QuantumScale*
896 ClampPixel(pixel.alpha);
898 node_info->total_color.alpha+=count*QuantumScale*
899 ClampPixel((MagickRealType) OpaqueAlpha);
900 p+=count*GetPixelChannels(image);
902 if (cube_info->colors > cube_info->maximum_colors)
904 PruneToCubeDepth(cube_info,cube_info->root);
907 proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
909 if (proceed == MagickFalse)
912 for (y++; y < (ssize_t) image->rows; y++)
920 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
921 if (p == (
const Quantum *) NULL)
923 if (cube_info->nodes > MaxNodes)
928 PruneLevel(cube_info,cube_info->root);
931 for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
936 for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
941 GetPixelInfoPixel(image,p+count*GetPixelChannels(image),&packet);
942 if (IsPixelEquivalent(image,p,&packet) == MagickFalse)
945 AssociateAlphaPixel(image,cube_info,p,&pixel);
946 index=MaxTreeDepth-1;
947 bisect=((double) QuantumRange+1.0)/2.0;
949 node_info=cube_info->root;
950 for (level=1; level <= cube_info->depth; level++)
956 id=ColorToNodeId(cube_info,&pixel,index);
957 mid.red+=(
id & 1) != 0 ? bisect : -bisect;
958 mid.green+=(
id & 2) != 0 ? bisect : -bisect;
959 mid.blue+=(
id & 4) != 0 ? bisect : -bisect;
960 mid.alpha+=(
id & 8) != 0 ? bisect : -bisect;
961 if (node_info->child[
id] == (
NodeInfo *) NULL)
966 node_info->child[id]=GetNodeInfo(cube_info,
id,level,node_info);
967 if (node_info->child[
id] == (
NodeInfo *) NULL)
969 (void) ThrowMagickException(exception,GetMagickModule(),
970 ResourceLimitError,
"MemoryAllocationFailed",
"%s",
974 if (level == cube_info->depth)
980 node_info=node_info->child[id];
981 error.red=QuantumScale*(pixel.red-mid.red);
982 error.green=QuantumScale*(pixel.green-mid.green);
983 error.blue=QuantumScale*(pixel.blue-mid.blue);
984 if (cube_info->associate_alpha != MagickFalse)
985 error.alpha=QuantumScale*(pixel.alpha-mid.alpha);
986 distance=(double) (error.red*error.red+error.green*error.green+
987 error.blue*error.blue+error.alpha*error.alpha);
988 if (IsNaN(distance) != 0)
990 node_info->quantize_error+=count*sqrt(distance);
991 cube_info->root->quantize_error+=node_info->quantize_error;
997 node_info->number_unique+=count;
998 node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red);
999 node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green);
1000 node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue);
1001 if (cube_info->associate_alpha != MagickFalse)
1002 node_info->total_color.alpha+=count*QuantumScale*
1003 ClampPixel(pixel.alpha);
1005 node_info->total_color.alpha+=count*QuantumScale*
1006 ClampPixel((MagickRealType) OpaqueAlpha);
1007 p+=count*GetPixelChannels(image);
1009 proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
1011 if (proceed == MagickFalse)
1014 image_view=DestroyCacheView(image_view);
1015 if (cube_info->quantize_info->colorspace != image->colorspace)
1016 if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
1017 (cube_info->quantize_info->colorspace != CMYKColorspace))
1018 (void) TransformImageColorspace((
Image *) image,sRGBColorspace,exception);
1019 return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue);
1053 clone_info=(
QuantizeInfo *) AcquireCriticalMemory(
sizeof(*clone_info));
1054 GetQuantizeInfo(clone_info);
1057 clone_info->number_colors=quantize_info->number_colors;
1058 clone_info->tree_depth=quantize_info->tree_depth;
1059 clone_info->dither_method=quantize_info->dither_method;
1060 clone_info->colorspace=quantize_info->colorspace;
1061 clone_info->measure_error=quantize_info->measure_error;
1094 static void ClosestColor(
const Image *image,
CubeInfo *cube_info,
1106 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1107 for (i=0; i < (ssize_t) number_children; i++)
1108 if (node_info->child[i] != (
NodeInfo *) NULL)
1109 ClosestColor(image,cube_info,node_info->child[i]);
1110 if (node_info->number_unique != 0)
1127 p=image->colormap+node_info->color_number;
1128 q=(&cube_info->target);
1131 if (cube_info->associate_alpha != MagickFalse)
1133 alpha=(MagickRealType) (QuantumScale*p->alpha);
1134 beta=(MagickRealType) (QuantumScale*q->alpha);
1136 pixel=alpha*p->red-beta*q->red;
1137 distance=pixel*pixel;
1138 if (distance <= cube_info->distance)
1140 pixel=alpha*p->green-beta*q->green;
1141 distance+=pixel*pixel;
1142 if (distance <= cube_info->distance)
1144 pixel=alpha*p->blue-beta*q->blue;
1145 distance+=pixel*pixel;
1146 if (distance <= cube_info->distance)
1148 if (cube_info->associate_alpha != MagickFalse)
1150 pixel=p->alpha-q->alpha;
1151 distance+=pixel*pixel;
1153 if (distance <= cube_info->distance)
1155 cube_info->distance=distance;
1156 cube_info->color_number=node_info->color_number;
1190 MagickExport MagickBooleanType CompressImageColormap(
Image *image,
1196 assert(image != (
Image *) NULL);
1197 assert(image->signature == MagickCoreSignature);
1198 if (IsEventLogging() != MagickFalse)
1199 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
1200 if (IsPaletteImage(image) == MagickFalse)
1201 return(MagickFalse);
1202 GetQuantizeInfo(&quantize_info);
1203 quantize_info.number_colors=image->colors;
1204 quantize_info.tree_depth=MaxTreeDepth;
1205 return(QuantizeImage(&quantize_info,image,exception));
1238 static void DefineImageColormap(
Image *image,
CubeInfo *cube_info,
1250 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1251 for (i=0; i < (ssize_t) number_children; i++)
1252 if (node_info->child[i] != (
NodeInfo *) NULL)
1253 DefineImageColormap(image,cube_info,node_info->child[i]);
1254 if (node_info->number_unique != 0)
1265 q=image->colormap+image->colors;
1266 alpha=(double) ((MagickOffsetType) node_info->number_unique);
1267 alpha=PerceptibleReciprocal(alpha);
1268 if (cube_info->associate_alpha == MagickFalse)
1270 q->red=(double) ClampToQuantum(alpha*QuantumRange*
1271 node_info->total_color.red);
1272 q->green=(double) ClampToQuantum(alpha*QuantumRange*
1273 node_info->total_color.green);
1274 q->blue=(double) ClampToQuantum(alpha*QuantumRange*
1275 node_info->total_color.blue);
1276 q->alpha=(double) OpaqueAlpha;
1283 opacity=(double) (alpha*QuantumRange*node_info->total_color.alpha);
1284 q->alpha=(double) ClampToQuantum(opacity);
1285 if (q->alpha == OpaqueAlpha)
1287 q->red=(double) ClampToQuantum(alpha*QuantumRange*
1288 node_info->total_color.red);
1289 q->green=(double) ClampToQuantum(alpha*QuantumRange*
1290 node_info->total_color.green);
1291 q->blue=(double) ClampToQuantum(alpha*QuantumRange*
1292 node_info->total_color.blue);
1299 gamma=(double) (QuantumScale*q->alpha);
1300 gamma=PerceptibleReciprocal(gamma);
1301 q->red=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1302 node_info->total_color.red);
1303 q->green=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1304 node_info->total_color.green);
1305 q->blue=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1306 node_info->total_color.blue);
1307 if (node_info->number_unique > cube_info->transparent_pixels)
1309 cube_info->transparent_pixels=node_info->number_unique;
1310 cube_info->transparent_index=(ssize_t) image->colors;
1314 node_info->color_number=image->colors++;
1340 static void DestroyCubeInfo(
CubeInfo *cube_info)
1350 nodes=cube_info->node_queue->next;
1351 cube_info->node_queue->nodes=(
NodeInfo *) RelinquishMagickMemory(
1352 cube_info->node_queue->nodes);
1353 cube_info->node_queue=(
Nodes *) RelinquishMagickMemory(
1354 cube_info->node_queue);
1355 cube_info->node_queue=nodes;
1356 }
while (cube_info->node_queue != (
Nodes *) NULL);
1357 if (cube_info->memory_info != (
MemoryInfo *) NULL)
1358 cube_info->memory_info=RelinquishVirtualMemory(cube_info->memory_info);
1359 cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info);
1360 cube_info=(
CubeInfo *) RelinquishMagickMemory(cube_info);
1389 assert(quantize_info->signature == MagickCoreSignature);
1390 if (IsEventLogging() != MagickFalse)
1391 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
1392 quantize_info->signature=(~MagickCoreSignature);
1393 quantize_info=(
QuantizeInfo *) RelinquishMagickMemory(quantize_info);
1394 return(quantize_info);
1434 for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++)
1452 number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
1457 (void) memset(pixels,0,number_threads*
sizeof(*pixels));
1458 for (i=0; i < (ssize_t) number_threads; i++)
1463 return(DestroyPixelTLS(pixels));
1468 static inline ssize_t CacheOffset(
CubeInfo *cube_info,
1471 #define RedShift(pixel) (((pixel) >> CacheShift) << (0*(8-CacheShift)))
1472 #define GreenShift(pixel) (((pixel) >> CacheShift) << (1*(8-CacheShift)))
1473 #define BlueShift(pixel) (((pixel) >> CacheShift) << (2*(8-CacheShift)))
1474 #define AlphaShift(pixel) (((pixel) >> CacheShift) << (3*(8-CacheShift)))
1479 offset=(ssize_t) (RedShift(ScaleQuantumToChar(ClampPixel(pixel->red))) |
1480 GreenShift(ScaleQuantumToChar(ClampPixel(pixel->green))) |
1481 BlueShift(ScaleQuantumToChar(ClampPixel(pixel->blue))));
1482 if (cube_info->associate_alpha != MagickFalse)
1483 offset|=AlphaShift(ScaleQuantumToChar(ClampPixel(pixel->alpha)));
1487 static MagickBooleanType FloydSteinbergDither(
Image *image,
CubeInfo *cube_info,
1490 #define DitherImageTag "Dither/Image"
1507 pixels=AcquirePixelTLS(image->columns);
1509 return(MagickFalse);
1511 image_view=AcquireAuthenticCacheView(image,exception);
1512 for (y=0; y < (ssize_t) image->rows; y++)
1515 id = GetOpenMPThreadId();
1534 if (status == MagickFalse)
1536 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
1537 if (q == (Quantum *) NULL)
1543 current=pixels[id]+(y & 0x01)*image->columns;
1544 previous=pixels[
id]+((y+1) & 0x01)*image->columns;
1545 v=(ssize_t) ((y & 0x01) != 0 ? -1 : 1);
1546 for (x=0; x < (ssize_t) image->columns; x++)
1558 u=(y & 0x01) != 0 ? (ssize_t) image->columns-1-x : x;
1559 AssociateAlphaPixel(image,&cube,q+u*GetPixelChannels(image),&pixel);
1562 pixel.red+=7.0*cube_info->diffusion*current[u-v].red/16;
1563 pixel.green+=7.0*cube_info->diffusion*current[u-v].green/16;
1564 pixel.blue+=7.0*cube_info->diffusion*current[u-v].blue/16;
1565 if (cube.associate_alpha != MagickFalse)
1566 pixel.alpha+=7.0*cube_info->diffusion*current[u-v].alpha/16;
1570 if (x < (ssize_t) (image->columns-1))
1572 pixel.red+=cube_info->diffusion*previous[u+v].red/16;
1573 pixel.green+=cube_info->diffusion*previous[u+v].green/16;
1574 pixel.blue+=cube_info->diffusion*previous[u+v].blue/16;
1575 if (cube.associate_alpha != MagickFalse)
1576 pixel.alpha+=cube_info->diffusion*previous[u+v].alpha/16;
1578 pixel.red+=5.0*cube_info->diffusion*previous[u].red/16;
1579 pixel.green+=5.0*cube_info->diffusion*previous[u].green/16;
1580 pixel.blue+=5.0*cube_info->diffusion*previous[u].blue/16;
1581 if (cube.associate_alpha != MagickFalse)
1582 pixel.alpha+=5.0*cube_info->diffusion*previous[u].alpha/16;
1585 pixel.red+=3.0*cube_info->diffusion*previous[u-v].red/16;
1586 pixel.green+=3.0*cube_info->diffusion*previous[u-v].green/16;
1587 pixel.blue+=3.0*cube_info->diffusion*previous[u-v].blue/16;
1588 if (cube.associate_alpha != MagickFalse)
1589 pixel.alpha+=3.0*cube_info->diffusion*previous[u-v].alpha/16;
1592 pixel.red=(double) ClampPixel(pixel.red);
1593 pixel.green=(double) ClampPixel(pixel.green);
1594 pixel.blue=(double) ClampPixel(pixel.blue);
1595 if (cube.associate_alpha != MagickFalse)
1596 pixel.alpha=(double) ClampPixel(pixel.alpha);
1597 i=CacheOffset(&cube,&pixel);
1598 if (cube.cache[i] < 0)
1609 node_info=cube.root;
1610 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1612 node_id=ColorToNodeId(&cube,&pixel,index);
1613 if (node_info->child[node_id] == (
NodeInfo *) NULL)
1615 node_info=node_info->child[node_id];
1621 cube.distance=(double) (4.0*(QuantumRange+1.0)*(QuantumRange+1.0)+
1623 ClosestColor(image,&cube,node_info->parent);
1624 cube.cache[i]=(ssize_t) cube.color_number;
1629 index=(size_t) cube.cache[i];
1630 if (image->storage_class == PseudoClass)
1631 SetPixelIndex(image,(Quantum) index,q+u*GetPixelChannels(image));
1632 if (cube.quantize_info->measure_error == MagickFalse)
1634 SetPixelRed(image,ClampToQuantum(image->colormap[index].red),
1635 q+u*GetPixelChannels(image));
1636 SetPixelGreen(image,ClampToQuantum(image->colormap[index].green),
1637 q+u*GetPixelChannels(image));
1638 SetPixelBlue(image,ClampToQuantum(image->colormap[index].blue),
1639 q+u*GetPixelChannels(image));
1640 if (cube.associate_alpha != MagickFalse)
1641 SetPixelAlpha(image,ClampToQuantum(image->colormap[index].alpha),
1642 q+u*GetPixelChannels(image));
1644 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1649 AssociateAlphaPixelInfo(&cube,image->colormap+index,&color);
1650 current[u].red=pixel.red-color.red;
1651 current[u].green=pixel.green-color.green;
1652 current[u].blue=pixel.blue-color.blue;
1653 if (cube.associate_alpha != MagickFalse)
1654 current[u].alpha=pixel.alpha-color.alpha;
1655 if (image->progress_monitor != (MagickProgressMonitor) NULL)
1660 proceed=SetImageProgress(image,DitherImageTag,(MagickOffsetType) y,
1662 if (proceed == MagickFalse)
1667 image_view=DestroyCacheView(image_view);
1668 pixels=DestroyPixelTLS(pixels);
1672 static MagickBooleanType RiemersmaDither(
Image *image,
CacheView *image_view,
1675 #define DitherImageTag "Dither/Image"
1691 if ((p->x >= 0) && (p->x < (ssize_t) image->columns) &&
1692 (p->y >= 0) && (p->y < (ssize_t) image->rows))
1703 q=GetCacheViewAuthenticPixels(image_view,p->x,p->y,1,1,exception);
1704 if (q == (Quantum *) NULL)
1705 return(MagickFalse);
1706 AssociateAlphaPixel(image,cube_info,q,&pixel);
1707 for (i=0; i < ErrorQueueLength; i++)
1709 pixel.red+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1711 pixel.green+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1713 pixel.blue+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1715 if (cube_info->associate_alpha != MagickFalse)
1716 pixel.alpha+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1719 pixel.red=(double) ClampPixel(pixel.red);
1720 pixel.green=(double) ClampPixel(pixel.green);
1721 pixel.blue=(double) ClampPixel(pixel.blue);
1722 if (cube_info->associate_alpha != MagickFalse)
1723 pixel.alpha=(double) ClampPixel(pixel.alpha);
1724 i=CacheOffset(cube_info,&pixel);
1725 if (p->cache[i] < 0)
1737 for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1739 id=ColorToNodeId(cube_info,&pixel,index);
1740 if (node_info->child[
id] == (
NodeInfo *) NULL)
1742 node_info=node_info->child[id];
1748 p->distance=(double) (4.0*(QuantumRange+1.0)*((double)
1749 QuantumRange+1.0)+1.0);
1750 ClosestColor(image,p,node_info->parent);
1751 p->cache[i]=(ssize_t) p->color_number;
1756 index=(size_t) p->cache[i];
1757 if (image->storage_class == PseudoClass)
1758 SetPixelIndex(image,(Quantum) index,q);
1759 if (cube_info->quantize_info->measure_error == MagickFalse)
1761 SetPixelRed(image,ClampToQuantum(image->colormap[index].red),q);
1762 SetPixelGreen(image,ClampToQuantum(image->colormap[index].green),q);
1763 SetPixelBlue(image,ClampToQuantum(image->colormap[index].blue),q);
1764 if (cube_info->associate_alpha != MagickFalse)
1765 SetPixelAlpha(image,ClampToQuantum(image->colormap[index].alpha),q);
1767 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1768 return(MagickFalse);
1772 (void) memmove(p->error,p->error+1,(ErrorQueueLength-1)*
1773 sizeof(p->error[0]));
1774 AssociateAlphaPixelInfo(cube_info,image->colormap+index,&color);
1775 p->error[ErrorQueueLength-1].red=pixel.red-color.red;
1776 p->error[ErrorQueueLength-1].green=pixel.green-color.green;
1777 p->error[ErrorQueueLength-1].blue=pixel.blue-color.blue;
1778 if (cube_info->associate_alpha != MagickFalse)
1779 p->error[ErrorQueueLength-1].alpha=pixel.alpha-color.alpha;
1780 proceed=SetImageProgress(image,DitherImageTag,p->offset,p->span);
1781 if (proceed == MagickFalse)
1782 return(MagickFalse);
1787 case WestGravity: p->x--;
break;
1788 case EastGravity: p->x++;
break;
1789 case NorthGravity: p->y--;
break;
1790 case SouthGravity: p->y++;
break;
1795 static MagickBooleanType Riemersma(
Image *image,
CacheView *image_view,
1796 CubeInfo *cube_info,
const size_t level,
const unsigned int direction,
1808 status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1810 if (status != MagickFalse)
1811 status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1813 if (status != MagickFalse)
1814 status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1820 status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1822 if (status != MagickFalse)
1823 status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1825 if (status != MagickFalse)
1826 status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1832 status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1834 if (status != MagickFalse)
1835 status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1837 if (status != MagickFalse)
1838 status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1844 status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1846 if (status != MagickFalse)
1847 status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1849 if (status != MagickFalse)
1850 status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1862 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1864 if (status != MagickFalse)
1865 status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1867 if (status != MagickFalse)
1868 status=Riemersma(image,image_view,cube_info,level-1,WestGravity,
1870 if (status != MagickFalse)
1871 status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1873 if (status != MagickFalse)
1874 status=Riemersma(image,image_view,cube_info,level-1,WestGravity,
1876 if (status != MagickFalse)
1877 status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1879 if (status != MagickFalse)
1880 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1886 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1888 if (status != MagickFalse)
1889 status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1891 if (status != MagickFalse)
1892 status=Riemersma(image,image_view,cube_info,level-1,EastGravity,
1894 if (status != MagickFalse)
1895 status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1897 if (status != MagickFalse)
1898 status=Riemersma(image,image_view,cube_info,level-1,EastGravity,
1900 if (status != MagickFalse)
1901 status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1903 if (status != MagickFalse)
1904 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1910 status=Riemersma(image,image_view,cube_info,level-1,WestGravity,
1912 if (status != MagickFalse)
1913 status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1915 if (status != MagickFalse)
1916 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1918 if (status != MagickFalse)
1919 status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1921 if (status != MagickFalse)
1922 status=Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1924 if (status != MagickFalse)
1925 status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1927 if (status != MagickFalse)
1928 status=Riemersma(image,image_view,cube_info,level-1,EastGravity,
1934 status=Riemersma(image,image_view,cube_info,level-1,EastGravity,
1936 if (status != MagickFalse)
1937 status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1939 if (status != MagickFalse)
1940 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1942 if (status != MagickFalse)
1943 status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1945 if (status != MagickFalse)
1946 status=Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1948 if (status != MagickFalse)
1949 status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1951 if (status != MagickFalse)
1952 status=Riemersma(image,image_view,cube_info,level-1,WestGravity,
1962 static MagickBooleanType DitherImage(
Image *image,
CubeInfo *cube_info,
1978 artifact=GetImageArtifact(image,
"dither:diffusion-amount");
1979 if (artifact != (
const char *) NULL)
1980 cube_info->diffusion=StringToDoubleInterval(artifact,1.0);
1981 if (cube_info->quantize_info->dither_method != RiemersmaDitherMethod)
1982 return(FloydSteinbergDither(image,cube_info,exception));
1986 (void) memset(cube_info->error,0,ErrorQueueLength*
sizeof(*cube_info->error));
1989 extent=MagickMax(image->columns,image->rows);
1990 level=(size_t) log2((
double) extent);
1991 if (((
size_t) 1UL << level) < extent)
1993 cube_info->offset=0;
1994 cube_info->span=(MagickSizeType) image->columns*image->rows;
1995 image_view=AcquireAuthenticCacheView(image,exception);
1998 status=Riemersma(image,image_view,cube_info,level,NorthGravity,exception);
1999 if (status != MagickFalse)
2000 status=RiemersmaDither(image,image_view,cube_info,ForgetGravity,exception);
2001 image_view=DestroyCacheView(image_view);
2040 const size_t depth,
const size_t maximum_colors)
2057 cube_info=(
CubeInfo *) AcquireMagickMemory(
sizeof(*cube_info));
2058 if (cube_info == (
CubeInfo *) NULL)
2060 (void) memset(cube_info,0,
sizeof(*cube_info));
2061 cube_info->depth=depth;
2062 if (cube_info->depth > MaxTreeDepth)
2063 cube_info->depth=MaxTreeDepth;
2064 if (cube_info->depth < 2)
2066 cube_info->maximum_colors=maximum_colors;
2070 cube_info->root=GetNodeInfo(cube_info,0,0,(
NodeInfo *) NULL);
2071 if (cube_info->root == (
NodeInfo *) NULL)
2073 cube_info->root->parent=cube_info->root;
2074 cube_info->quantize_info=CloneQuantizeInfo(quantize_info);
2075 if (cube_info->quantize_info->dither_method == NoDitherMethod)
2080 length=(size_t) (1UL << (4*(8-CacheShift)));
2081 cube_info->memory_info=AcquireVirtualMemory(length,
sizeof(*cube_info->cache));
2082 if (cube_info->memory_info == (
MemoryInfo *) NULL)
2084 cube_info->cache=(ssize_t *) GetVirtualMemoryBlob(cube_info->memory_info);
2088 (void) memset(cube_info->cache,(-1),
sizeof(*cube_info->cache)*length);
2093 for (i=0; i < ErrorQueueLength; i++)
2095 cube_info->weights[i]=PerceptibleReciprocal(weight);
2096 weight*=exp(log(1.0/ErrorRelativeWeight)/(ErrorQueueLength-1.0));
2098 cube_info->diffusion=1.0;
2131 const size_t level,
NodeInfo *parent)
2136 if (cube_info->free_nodes == 0)
2144 nodes=(
Nodes *) AcquireMagickMemory(
sizeof(*nodes));
2145 if (nodes == (
Nodes *) NULL)
2147 nodes->nodes=(
NodeInfo *) AcquireQuantumMemory(NodesInAList,
2148 sizeof(*nodes->nodes));
2149 if (nodes->nodes == (
NodeInfo *) NULL)
2151 nodes->next=cube_info->node_queue;
2152 cube_info->node_queue=nodes;
2153 cube_info->next_node=nodes->nodes;
2154 cube_info->free_nodes=NodesInAList;
2157 cube_info->free_nodes--;
2158 node_info=cube_info->next_node++;
2159 (void) memset(node_info,0,
sizeof(*node_info));
2160 node_info->parent=parent;
2162 node_info->level=level;
2208 MagickExport MagickBooleanType GetImageQuantizeError(
Image *image,
2221 mean_error_per_pixel;
2227 assert(image != (
Image *) NULL);
2228 assert(image->signature == MagickCoreSignature);
2229 if (IsEventLogging() != MagickFalse)
2230 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
2231 image->total_colors=GetNumberColors(image,(FILE *) NULL,exception);
2232 (void) memset(&image->error,0,
sizeof(image->error));
2233 if (image->storage_class == DirectClass)
2237 area=3.0*image->columns*image->rows;
2239 mean_error_per_pixel=0.0;
2241 image_view=AcquireVirtualCacheView(image,exception);
2242 for (y=0; y < (ssize_t) image->rows; y++)
2250 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
2251 if (p == (
const Quantum *) NULL)
2253 for (x=0; x < (ssize_t) image->columns; x++)
2255 index=(ssize_t) GetPixelIndex(image,p);
2256 if (image->alpha_trait != UndefinedPixelTrait)
2258 alpha=(double) (QuantumScale*GetPixelAlpha(image,p));
2259 beta=(double) (QuantumScale*image->colormap[index].alpha);
2261 distance=fabs((
double) (alpha*GetPixelRed(image,p)-beta*
2262 image->colormap[index].red));
2263 mean_error_per_pixel+=distance;
2264 mean_error+=distance*distance;
2265 if (distance > maximum_error)
2266 maximum_error=distance;
2267 distance=fabs((
double) (alpha*GetPixelGreen(image,p)-beta*
2268 image->colormap[index].green));
2269 mean_error_per_pixel+=distance;
2270 mean_error+=distance*distance;
2271 if (distance > maximum_error)
2272 maximum_error=distance;
2273 distance=fabs((
double) (alpha*GetPixelBlue(image,p)-beta*
2274 image->colormap[index].blue));
2275 mean_error_per_pixel+=distance;
2276 mean_error+=distance*distance;
2277 if (distance > maximum_error)
2278 maximum_error=distance;
2279 p+=GetPixelChannels(image);
2282 image_view=DestroyCacheView(image_view);
2283 image->error.mean_error_per_pixel=(double) mean_error_per_pixel/area;
2284 image->error.normalized_mean_error=(double) QuantumScale*QuantumScale*
2286 image->error.normalized_maximum_error=(double) QuantumScale*maximum_error;
2312 MagickExport
void GetQuantizeInfo(
QuantizeInfo *quantize_info)
2315 if (IsEventLogging() != MagickFalse)
2316 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"...");
2317 (void) memset(quantize_info,0,
sizeof(*quantize_info));
2318 quantize_info->number_colors=256;
2319 quantize_info->dither_method=RiemersmaDitherMethod;
2320 quantize_info->colorspace=UndefinedColorspace;
2321 quantize_info->measure_error=MagickFalse;
2322 quantize_info->signature=MagickCoreSignature;
2377 for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++)
2379 kmeans_info[i]=(
KmeansInfo *) RelinquishMagickMemory(kmeans_info[i]);
2380 kmeans_info=(
KmeansInfo **) RelinquishMagickMemory(kmeans_info);
2381 return(kmeans_info);
2384 static int DominantColorCompare(
const void *x,
const void *y)
2392 return((
int) pixel_2->count-(int) pixel_1->count);
2395 static KmeansInfo **AcquireKmeansTLS(
const size_t number_colors)
2406 number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
2407 kmeans_info=(
KmeansInfo **) AcquireQuantumMemory(number_threads,
2408 sizeof(*kmeans_info));
2411 (void) memset(kmeans_info,0,number_threads*
sizeof(*kmeans_info));
2412 for (i=0; i < (ssize_t) number_threads; i++)
2414 kmeans_info[i]=(
KmeansInfo *) AcquireQuantumMemory(number_colors,
2415 sizeof(**kmeans_info));
2417 return(DestroyKmeansTLS(kmeans_info));
2419 return(kmeans_info);
2422 static inline double KmeansMetric(
const Image *magick_restrict image,
2423 const Quantum *magick_restrict p,
const PixelInfo *magick_restrict q)
2432 if ((image->alpha_trait != UndefinedPixelTrait) ||
2433 (q->alpha_trait != UndefinedPixelTrait))
2435 pixel=GetPixelAlpha(image,p)-(q->alpha_trait != UndefinedPixelTrait ?
2436 q->alpha : OpaqueAlpha);
2437 metric+=pixel*pixel;
2438 if (image->alpha_trait != UndefinedPixelTrait)
2439 gamma*=QuantumScale*GetPixelAlpha(image,p);
2440 if (q->alpha_trait != UndefinedPixelTrait)
2441 gamma*=QuantumScale*q->alpha;
2443 if (image->colorspace == CMYKColorspace)
2445 pixel=QuantumScale*(GetPixelBlack(image,p)-q->black);
2446 metric+=gamma*pixel*pixel;
2447 gamma*=QuantumScale*(QuantumRange-GetPixelBlack(image,p));
2448 gamma*=QuantumScale*(QuantumRange-q->black);
2451 pixel=QuantumScale*(GetPixelRed(image,p)-q->red);
2452 if (IsHueCompatibleColorspace(image->colorspace) != MagickFalse)
2454 if (fabs((
double) pixel) > 0.5)
2458 metric+=gamma*pixel*pixel;
2459 pixel=QuantumScale*(GetPixelGreen(image,p)-q->green);
2460 metric+=gamma*pixel*pixel;
2461 pixel=QuantumScale*(GetPixelBlue(image,p)-q->blue);
2462 metric+=gamma*pixel*pixel;
2466 MagickExport MagickBooleanType KmeansImage(
Image *image,
2467 const size_t number_colors,
const size_t max_iterations,
const double tolerance,
2470 #define KmeansImageTag "Kmeans/Image"
2471 #define RandomColorComponent(info) (QuantumRange*GetPseudoRandomValue(info))
2477 tuple[MagickPathExtent];
2501 assert(image != (
Image *) NULL);
2502 assert(image->signature == MagickCoreSignature);
2504 assert(exception->signature == MagickCoreSignature);
2505 if (IsEventLogging() != MagickFalse)
2506 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
2507 if (max_iterations == 0)
2508 return(MagickFalse);
2509 colors=GetImageArtifact(image,
"kmeans:seed-colors");
2510 if (colors == (
const char *) NULL)
2524 quantize_info=AcquireQuantizeInfo((
ImageInfo *) NULL);
2525 quantize_info->colorspace=image->colorspace;
2526 quantize_info->number_colors=number_colors;
2527 quantize_info->dither_method=NoDitherMethod;
2528 n=(ssize_t) number_colors;
2529 for (depth=1; n != 0; depth++)
2531 cube_info=GetCubeInfo(quantize_info,depth,number_colors);
2532 if (cube_info == (
CubeInfo *) NULL)
2534 quantize_info=DestroyQuantizeInfo(quantize_info);
2535 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
2538 status=ClassifyImageColors(cube_info,image,exception);
2539 if (status != MagickFalse)
2541 if (cube_info->colors > cube_info->maximum_colors)
2542 ReduceImageColors(image,cube_info);
2543 status=SetImageColormap(image,cube_info,exception);
2545 DestroyCubeInfo(cube_info);
2546 quantize_info=DestroyQuantizeInfo(quantize_info);
2547 if (status == MagickFalse)
2553 color[MagickPathExtent];
2561 status=AcquireImageColormap(image,number_colors,exception);
2562 if (status == MagickFalse)
2564 for (n=0, p=colors; n < (ssize_t) image->colors; n++)
2569 for (q=p; *q !=
'\0'; q++)
2572 (void) CopyMagickString(color,p,(
size_t) MagickMin(q-p+1,
2574 (void) QueryColorCompliance(color,AllCompliance,image->colormap+n,
2583 if (n < (ssize_t) image->colors)
2591 random_info=AcquireRandomInfo();
2592 for ( ; n < (ssize_t) image->colors; n++)
2594 (void) QueryColorCompliance(
"#000",AllCompliance,image->colormap+n,
2596 image->colormap[n].red=RandomColorComponent(random_info);
2597 image->colormap[n].green=RandomColorComponent(random_info);
2598 image->colormap[n].blue=RandomColorComponent(random_info);
2599 if (image->alpha_trait != UndefinedPixelTrait)
2600 image->colormap[n].alpha=RandomColorComponent(random_info);
2601 if (image->colorspace == CMYKColorspace)
2602 image->colormap[n].black=RandomColorComponent(random_info);
2604 random_info=DestroyRandomInfo(random_info);
2610 kmeans_pixels=AcquireKmeansTLS(number_colors);
2612 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
2614 previous_tolerance=0.0;
2615 verbose=IsStringTrue(GetImageArtifact(image,
"verbose"));
2616 number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
2617 image_view=AcquireAuthenticCacheView(image,exception);
2618 for (n=0; n < (ssize_t) max_iterations; n++)
2627 for (j=0; j < (ssize_t) number_threads; j++)
2628 (
void) memset(kmeans_pixels[j],0,image->colors*
sizeof(*kmeans_pixels[j]));
2629 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2630 #pragma omp parallel for schedule(dynamic) shared(status) \
2631 magick_number_threads(image,image,image->rows,1)
2633 for (y=0; y < (ssize_t) image->rows; y++)
2636 id = GetOpenMPThreadId();
2644 if (status == MagickFalse)
2646 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2647 if (q == (Quantum *) NULL)
2652 for (x=0; x < (ssize_t) image->columns; x++)
2665 min_distance=KmeansMetric(image,q,image->colormap+0);
2666 for (i=1; i < (ssize_t) image->colors; i++)
2671 if (min_distance <= MagickEpsilon)
2673 distance=KmeansMetric(image,q,image->colormap+i);
2674 if (distance < min_distance)
2676 min_distance=distance;
2680 kmeans_pixels[id][k].red+=QuantumScale*GetPixelRed(image,q);
2681 kmeans_pixels[id][k].green+=QuantumScale*GetPixelGreen(image,q);
2682 kmeans_pixels[id][k].blue+=QuantumScale*GetPixelBlue(image,q);
2683 if (image->alpha_trait != UndefinedPixelTrait)
2684 kmeans_pixels[id][k].alpha+=QuantumScale*GetPixelAlpha(image,q);
2685 if (image->colorspace == CMYKColorspace)
2686 kmeans_pixels[id][k].black+=QuantumScale*GetPixelBlack(image,q);
2687 kmeans_pixels[id][k].count++;
2688 kmeans_pixels[id][k].distortion+=min_distance;
2689 SetPixelIndex(image,(Quantum) k,q);
2690 q+=GetPixelChannels(image);
2692 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2695 if (status == MagickFalse)
2700 for (j=1; j < (ssize_t) number_threads; j++)
2705 for (k=0; k < (ssize_t) image->colors; k++)
2707 kmeans_pixels[0][k].red+=kmeans_pixels[j][k].red;
2708 kmeans_pixels[0][k].green+=kmeans_pixels[j][k].green;
2709 kmeans_pixels[0][k].blue+=kmeans_pixels[j][k].blue;
2710 if (image->alpha_trait != UndefinedPixelTrait)
2711 kmeans_pixels[0][k].alpha+=kmeans_pixels[j][k].alpha;
2712 if (image->colorspace == CMYKColorspace)
2713 kmeans_pixels[0][k].black+=kmeans_pixels[j][k].black;
2714 kmeans_pixels[0][k].count+=kmeans_pixels[j][k].count;
2715 kmeans_pixels[0][k].distortion+=kmeans_pixels[j][k].distortion;
2722 for (j=0; j < (ssize_t) image->colors; j++)
2727 gamma=PerceptibleReciprocal((
double) kmeans_pixels[0][j].count);
2728 image->colormap[j].red=gamma*QuantumRange*kmeans_pixels[0][j].red;
2729 image->colormap[j].green=gamma*QuantumRange*kmeans_pixels[0][j].green;
2730 image->colormap[j].blue=gamma*QuantumRange*kmeans_pixels[0][j].blue;
2731 if (image->alpha_trait != UndefinedPixelTrait)
2732 image->colormap[j].alpha=gamma*QuantumRange*kmeans_pixels[0][j].alpha;
2733 if (image->colorspace == CMYKColorspace)
2734 image->colormap[j].black=gamma*QuantumRange*kmeans_pixels[0][j].black;
2735 image->colormap[j].count=(MagickSizeType) kmeans_pixels[0][j].count;
2736 distortion+=kmeans_pixels[0][j].distortion;
2738 if (image->debug != MagickFalse)
2739 (void) LogMagickEvent(ImageEvent,GetMagickModule(),
2740 "distortion[%.20g]: %*g %*g\n",(double) n,GetMagickPrecision(),
2741 distortion,GetMagickPrecision(),fabs(distortion-previous_tolerance));
2742 if (fabs(distortion-previous_tolerance) <= tolerance)
2744 previous_tolerance=distortion;
2745 if (image->progress_monitor != (MagickProgressMonitor) NULL)
2750 proceed=SetImageProgress(image,KmeansImageTag,(MagickOffsetType) n,
2752 if (proceed == MagickFalse)
2756 image_view=DestroyCacheView(image_view);
2757 if (verbose != MagickFalse)
2758 for (n=0; n < (ssize_t) image->colors; n++)
2760 GetColorTuple(image->colormap+n,MagickTrue,tuple);
2761 (void) FormatLocaleFile(stderr,
"%s %.20g\n",tuple,(
double)
2762 image->colormap[n].count);
2764 dominant_image=CloneImage(image,0,0,MagickTrue,exception);
2765 if (dominant_image != (
Image *) NULL)
2770 qsort((
void *) dominant_image->colormap,dominant_image->colors,
2771 sizeof(*dominant_image->colormap),DominantColorCompare);
2772 GetColorTuple(dominant_image->colormap,MagickTrue,tuple);
2773 dominant_image=DestroyImage(dominant_image);
2774 (void) SetImageProperty(image,
"dominant-color",tuple,exception);
2776 kmeans_pixels=DestroyKmeansTLS(kmeans_pixels);
2777 if (image->progress_monitor != (MagickProgressMonitor) NULL)
2778 (void) SetImageProgress(image,KmeansImageTag,(MagickOffsetType)
2779 max_iterations-1,max_iterations);
2780 if (status == MagickFalse)
2782 return(SyncImage(image,exception));
2818 static inline double MagickRound(
double x)
2823 if ((x-floor(x)) < (ceil(x)-x))
2828 MagickExport MagickBooleanType PosterizeImage(
Image *image,
const size_t levels,
2831 #define PosterizeImageTag "Posterize/Image"
2832 #define PosterizePixel(pixel) ClampToQuantum((MagickRealType) QuantumRange*( \
2833 MagickRound(QuantumScale*pixel*(levels-1)))/MagickMax((ssize_t) levels-1,1))
2853 assert(image != (
Image *) NULL);
2854 assert(image->signature == MagickCoreSignature);
2856 assert(exception->signature == MagickCoreSignature);
2857 if (IsEventLogging() != MagickFalse)
2858 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
2859 if (image->storage_class == PseudoClass)
2860 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2861 #pragma omp parallel for schedule(static) shared(progress,status) \
2862 magick_number_threads(image,image,image->colors,1)
2864 for (i=0; i < (ssize_t) image->colors; i++)
2869 if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0)
2870 image->colormap[i].red=(double)
2871 PosterizePixel(image->colormap[i].red);
2872 if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0)
2873 image->colormap[i].green=(double)
2874 PosterizePixel(image->colormap[i].green);
2875 if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0)
2876 image->colormap[i].blue=(double)
2877 PosterizePixel(image->colormap[i].blue);
2878 if ((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0)
2879 image->colormap[i].alpha=(double)
2880 PosterizePixel(image->colormap[i].alpha);
2887 image_view=AcquireAuthenticCacheView(image,exception);
2888 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2889 #pragma omp parallel for schedule(static) shared(progress,status) \
2890 magick_number_threads(image,image,image->rows,1)
2892 for (y=0; y < (ssize_t) image->rows; y++)
2900 if (status == MagickFalse)
2902 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2903 if (q == (Quantum *) NULL)
2908 for (x=0; x < (ssize_t) image->columns; x++)
2910 if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0)
2911 SetPixelRed(image,PosterizePixel(GetPixelRed(image,q)),q);
2912 if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0)
2913 SetPixelGreen(image,PosterizePixel(GetPixelGreen(image,q)),q);
2914 if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0)
2915 SetPixelBlue(image,PosterizePixel(GetPixelBlue(image,q)),q);
2916 if (((GetPixelBlackTraits(image) & UpdatePixelTrait) != 0) &&
2917 (image->colorspace == CMYKColorspace))
2918 SetPixelBlack(image,PosterizePixel(GetPixelBlack(image,q)),q);
2919 if (((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0) &&
2920 (image->alpha_trait != UndefinedPixelTrait))
2921 SetPixelAlpha(image,PosterizePixel(GetPixelAlpha(image,q)),q);
2922 q+=GetPixelChannels(image);
2924 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2926 if (image->progress_monitor != (MagickProgressMonitor) NULL)
2931 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2935 proceed=SetImageProgress(image,PosterizeImageTag,progress,image->rows);
2936 if (proceed == MagickFalse)
2940 image_view=DestroyCacheView(image_view);
2941 quantize_info=AcquireQuantizeInfo((
ImageInfo *) NULL);
2942 quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels*
2943 levels,MaxColormapSize+1);
2944 quantize_info->dither_method=dither_method;
2945 quantize_info->tree_depth=MaxTreeDepth;
2946 status=QuantizeImage(quantize_info,image,exception);
2947 quantize_info=DestroyQuantizeInfo(quantize_info);
2990 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2991 for (i=0; i < (ssize_t) number_children; i++)
2992 if (node_info->child[i] != (
NodeInfo *) NULL)
2993 PruneChild(cube_info,node_info->child[i]);
2994 if (cube_info->nodes > cube_info->maximum_colors)
2999 parent=node_info->parent;
3000 parent->number_unique+=node_info->number_unique;
3001 parent->total_color.red+=node_info->total_color.red;
3002 parent->total_color.green+=node_info->total_color.green;
3003 parent->total_color.blue+=node_info->total_color.blue;
3004 parent->total_color.alpha+=node_info->total_color.alpha;
3005 parent->child[node_info->id]=(
NodeInfo *) NULL;
3046 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3047 for (i=0; i < (ssize_t) number_children; i++)
3048 if (node_info->child[i] != (
NodeInfo *) NULL)
3049 PruneLevel(cube_info,node_info->child[i]);
3050 if (node_info->level == cube_info->depth)
3051 PruneChild(cube_info,node_info);
3080 static void PruneToCubeDepth(
CubeInfo *cube_info,
const NodeInfo *node_info)
3091 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3092 for (i=0; i < (ssize_t) number_children; i++)
3093 if (node_info->child[i] != (
NodeInfo *) NULL)
3094 PruneToCubeDepth(cube_info,node_info->child[i]);
3095 if (node_info->level > cube_info->depth)
3096 PruneChild(cube_info,node_info);
3129 MagickExport MagickBooleanType QuantizeImage(
const QuantizeInfo *quantize_info,
3146 assert(quantize_info->signature == MagickCoreSignature);
3147 assert(image != (
Image *) NULL);
3148 assert(image->signature == MagickCoreSignature);
3150 assert(exception->signature == MagickCoreSignature);
3151 if (IsEventLogging() != MagickFalse)
3152 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
3153 maximum_colors=quantize_info->number_colors;
3154 if (maximum_colors == 0)
3155 maximum_colors=MaxColormapSize;
3156 if (maximum_colors > MaxColormapSize)
3157 maximum_colors=MaxColormapSize;
3158 type=IdentifyImageGray(image,exception);
3159 if (IsGrayImageType(type) != MagickFalse)
3160 (void) SetGrayscaleImage(image,exception);
3161 depth=quantize_info->tree_depth;
3170 colors=maximum_colors;
3171 for (depth=1; colors != 0; depth++)
3173 if ((quantize_info->dither_method != NoDitherMethod) && (depth > 2))
3175 if ((image->alpha_trait != UndefinedPixelTrait) && (depth > 5))
3177 if (IsGrayImageType(type) != MagickFalse)
3183 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
3184 if (cube_info == (
CubeInfo *) NULL)
3185 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3187 status=ClassifyImageColors(cube_info,image,exception);
3188 if (status != MagickFalse)
3193 if (cube_info->colors > cube_info->maximum_colors)
3194 ReduceImageColors(image,cube_info);
3195 status=AssignImageColors(image,cube_info,exception);
3197 DestroyCubeInfo(cube_info);
3231 MagickExport MagickBooleanType QuantizeImages(
const QuantizeInfo *quantize_info,
3244 MagickProgressMonitor
3256 assert(quantize_info->signature == MagickCoreSignature);
3257 assert(images != (
Image *) NULL);
3258 assert(images->signature == MagickCoreSignature);
3260 assert(exception->signature == MagickCoreSignature);
3261 if (IsEventLogging() != MagickFalse)
3262 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",images->filename);
3263 if (GetNextImageInList(images) == (
Image *) NULL)
3268 status=QuantizeImage(quantize_info,images,exception);
3272 maximum_colors=quantize_info->number_colors;
3273 if (maximum_colors == 0)
3274 maximum_colors=MaxColormapSize;
3275 if (maximum_colors > MaxColormapSize)
3276 maximum_colors=MaxColormapSize;
3277 depth=quantize_info->tree_depth;
3286 colors=maximum_colors;
3287 for (depth=1; colors != 0; depth++)
3289 if (quantize_info->dither_method != NoDitherMethod)
3295 cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
3296 if (cube_info == (
CubeInfo *) NULL)
3298 (void) ThrowMagickException(exception,GetMagickModule(),
3299 ResourceLimitError,
"MemoryAllocationFailed",
"`%s'",images->filename);
3300 return(MagickFalse);
3302 number_images=GetImageListLength(images);
3304 for (i=0; image != (
Image *) NULL; i++)
3306 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL,
3307 image->client_data);
3308 status=ClassifyImageColors(cube_info,image,exception);
3309 if (status == MagickFalse)
3311 (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
3312 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
3314 if (proceed == MagickFalse)
3316 image=GetNextImageInList(image);
3318 if (status != MagickFalse)
3323 ReduceImageColors(images,cube_info);
3325 for (i=0; image != (
Image *) NULL; i++)
3327 progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor)
3328 NULL,image->client_data);
3329 status=AssignImageColors(image,cube_info,exception);
3330 if (status == MagickFalse)
3332 (void) SetImageProgressMonitor(image,progress_monitor,
3333 image->client_data);
3334 proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
3336 if (proceed == MagickFalse)
3338 image=GetNextImageInList(image);
3341 DestroyCubeInfo(cube_info);
3378 static size_t QuantizeErrorFlatten(
const CubeInfo *cube_info,
3379 const NodeInfo *node_info,
const ssize_t offset,
double *quantize_error)
3388 if (offset >= (ssize_t) cube_info->nodes)
3390 quantize_error[offset]=node_info->quantize_error;
3392 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3393 for (i=0; i < (ssize_t) number_children ; i++)
3394 if (node_info->child[i] != (
NodeInfo *) NULL)
3395 n+=QuantizeErrorFlatten(cube_info,node_info->child[i],offset+n,
3436 number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3437 for (i=0; i < (ssize_t) number_children; i++)
3438 if (node_info->child[i] != (
NodeInfo *) NULL)
3439 Reduce(cube_info,node_info->child[i]);
3440 if (node_info->quantize_error <= cube_info->pruning_threshold)
3441 PruneChild(cube_info,node_info);
3447 if (node_info->number_unique > 0)
3448 cube_info->colors++;
3449 if (node_info->quantize_error < cube_info->next_threshold)
3450 cube_info->next_threshold=node_info->quantize_error;
3509 static int QuantizeErrorCompare(
const void *error_p,
const void *error_q)
3515 p=(
double *) error_p;
3516 q=(
double *) error_q;
3519 if (fabs(*q-*p) <= MagickEpsilon)
3524 static void ReduceImageColors(
const Image *image,
CubeInfo *cube_info)
3526 #define ReduceImageTag "Reduce/Image"
3537 cube_info->next_threshold=0.0;
3538 if (cube_info->colors > cube_info->maximum_colors)
3546 quantize_error=(
double *) AcquireQuantumMemory(cube_info->nodes,
3547 sizeof(*quantize_error));
3548 if (quantize_error != (
double *) NULL)
3550 (void) QuantizeErrorFlatten(cube_info,cube_info->root,0,
3552 qsort(quantize_error,cube_info->nodes,
sizeof(
double),
3553 QuantizeErrorCompare);
3554 if (cube_info->nodes > (110*(cube_info->maximum_colors+1)/100))
3555 cube_info->next_threshold=quantize_error[cube_info->nodes-110*
3556 (cube_info->maximum_colors+1)/100];
3557 quantize_error=(
double *) RelinquishMagickMemory(quantize_error);
3560 for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; )
3562 cube_info->pruning_threshold=cube_info->next_threshold;
3563 cube_info->next_threshold=cube_info->root->quantize_error-1;
3564 cube_info->colors=0;
3565 Reduce(cube_info,cube_info->root);
3566 offset=(MagickOffsetType) span-cube_info->colors;
3567 proceed=SetImageProgress(image,ReduceImageTag,offset,span-
3568 cube_info->maximum_colors+1);
3569 if (proceed == MagickFalse)
3604 MagickExport MagickBooleanType RemapImage(
const QuantizeInfo *quantize_info,
3616 assert(image != (
Image *) NULL);
3617 assert(image->signature == MagickCoreSignature);
3618 assert(remap_image != (
Image *) NULL);
3619 assert(remap_image->signature == MagickCoreSignature);
3621 assert(exception->signature == MagickCoreSignature);
3622 if (IsEventLogging() != MagickFalse)
3623 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
3624 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3625 quantize_info->number_colors);
3626 if (cube_info == (
CubeInfo *) NULL)
3627 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3629 status=ClassifyImageColors(cube_info,remap_image,exception);
3630 if (status != MagickFalse)
3635 cube_info->quantize_info->number_colors=cube_info->colors;
3636 status=AssignImageColors(image,cube_info,exception);
3638 DestroyCubeInfo(cube_info);
3672 MagickExport MagickBooleanType RemapImages(
const QuantizeInfo *quantize_info,
3684 assert(images != (
Image *) NULL);
3685 assert(images->signature == MagickCoreSignature);
3687 assert(exception->signature == MagickCoreSignature);
3688 if (IsEventLogging() != MagickFalse)
3689 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",images->filename);
3691 if (remap_image == (
Image *) NULL)
3696 status=QuantizeImages(quantize_info,images,exception);
3702 cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3703 quantize_info->number_colors);
3704 if (cube_info == (
CubeInfo *) NULL)
3705 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3707 status=ClassifyImageColors(cube_info,remap_image,exception);
3708 if (status != MagickFalse)
3713 cube_info->quantize_info->number_colors=cube_info->colors;
3715 for ( ; image != (
Image *) NULL; image=GetNextImageInList(image))
3717 status=AssignImageColors(image,cube_info,exception);
3718 if (status == MagickFalse)
3722 DestroyCubeInfo(cube_info);
3752 #if defined(__cplusplus) || defined(c_plusplus)
3756 static int IntensityCompare(
const void *x,
const void *y)
3767 intensity=GetPixelInfoIntensity((
const Image *) NULL,color_1)-
3768 GetPixelInfoIntensity((
const Image *) NULL,color_2);
3769 if (intensity < (
double) INT_MIN)
3770 intensity=(double) INT_MIN;
3771 if (intensity > (
double) INT_MAX)
3772 intensity=(
double) INT_MAX;
3773 return((
int) intensity);
3776 #if defined(__cplusplus) || defined(c_plusplus)
3780 static MagickBooleanType SetGrayscaleImage(
Image *image,
3801 assert(image != (
Image *) NULL);
3802 assert(image->signature == MagickCoreSignature);
3803 if (image->type != GrayscaleType)
3804 (void) TransformImageColorspace(image,GRAYColorspace,exception);
3805 extent=MagickMax(image->colors+1,MagickMax(MaxColormapSize,MaxMap+1));
3806 colormap_index=(ssize_t *) AcquireQuantumMemory(extent,
3807 sizeof(*colormap_index));
3808 if (colormap_index == (ssize_t *) NULL)
3809 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3811 if (image->storage_class != PseudoClass)
3813 (void) memset(colormap_index,(-1),extent*
sizeof(*colormap_index));
3814 if (AcquireImageColormap(image,MaxColormapSize,exception) == MagickFalse)
3816 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3817 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3822 image_view=AcquireAuthenticCacheView(image,exception);
3823 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3824 #pragma omp parallel for schedule(static) shared(status) \
3825 magick_number_threads(image,image,image->rows,1)
3827 for (y=0; y < (ssize_t) image->rows; y++)
3835 if (status == MagickFalse)
3837 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
3839 if (q == (Quantum *) NULL)
3844 for (x=0; x < (ssize_t) image->columns; x++)
3849 intensity=ScaleQuantumToMap(GetPixelRed(image,q));
3850 if (colormap_index[intensity] < 0)
3852 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3853 #pragma omp critical (MagickCore_SetGrayscaleImage)
3855 if (colormap_index[intensity] < 0)
3857 colormap_index[intensity]=(ssize_t) image->colors;
3858 image->colormap[image->colors].red=(
double)
3859 GetPixelRed(image,q);
3860 image->colormap[image->colors].green=(double)
3861 GetPixelGreen(image,q);
3862 image->colormap[image->colors].blue=(double)
3863 GetPixelBlue(image,q);
3867 SetPixelIndex(image,(Quantum) colormap_index[intensity],q);
3868 q+=GetPixelChannels(image);
3870 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3873 image_view=DestroyCacheView(image_view);
3875 (void) memset(colormap_index,0,extent*
sizeof(*colormap_index));
3876 for (i=0; i < (ssize_t) image->colors; i++)
3877 image->colormap[i].alpha=(double) i;
3878 qsort((
void *) image->colormap,image->colors,
sizeof(
PixelInfo),
3880 colormap=(
PixelInfo *) AcquireQuantumMemory(image->colors,
sizeof(*colormap));
3883 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3884 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3888 colormap[j]=image->colormap[0];
3889 for (i=0; i < (ssize_t) image->colors; i++)
3891 if (IsPixelInfoEquivalent(&colormap[j],&image->colormap[i]) == MagickFalse)
3894 colormap[j]=image->colormap[i];
3896 colormap_index[(ssize_t) image->colormap[i].alpha]=j;
3898 image->colors=(size_t) (j+1);
3899 image->colormap=(
PixelInfo *) RelinquishMagickMemory(image->colormap);
3900 image->colormap=colormap;
3902 image_view=AcquireAuthenticCacheView(image,exception);
3903 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3904 #pragma omp parallel for schedule(static) shared(status) \
3905 magick_number_threads(image,image,image->rows,1)
3907 for (y=0; y < (ssize_t) image->rows; y++)
3915 if (status == MagickFalse)
3917 q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
3918 if (q == (Quantum *) NULL)
3923 for (x=0; x < (ssize_t) image->columns; x++)
3925 SetPixelIndex(image,(Quantum) colormap_index[ScaleQuantumToMap(
3926 GetPixelIndex(image,q))],q);
3927 q+=GetPixelChannels(image);
3929 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3932 image_view=DestroyCacheView(image_view);
3933 colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3934 image->type=GrayscaleType;
3935 if (SetImageMonochrome(image,exception) != MagickFalse)
3936 image->type=BilevelType;
3970 MagickBooleanType SetImageColormap(
Image *image,
CubeInfo *cube_info,
3976 number_colors=MagickMax(cube_info->maximum_colors,cube_info->colors);
3977 if (AcquireImageColormap(image,number_colors,exception) == MagickFalse)
3978 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",
3981 DefineImageColormap(image,cube_info,cube_info->root);
3982 if (image->colors != number_colors)
3984 image->colormap=(
PixelInfo *) ResizeQuantumMemory(image->colormap,
3985 image->colors+1,
sizeof(*image->colormap));
3986 if (image->colormap == (
PixelInfo *) NULL)
3987 ThrowBinaryException(ResourceLimitError,
"MemoryAllocationFailed",