| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % QQQ U U AAA N N TTTTT IIIII ZZZZZ EEEEE % |
| % Q Q U U A A NN N T I ZZ E % |
| % Q Q U U AAAAA N N N T I ZZZ EEEEE % |
| % Q QQ U U A A N NN T I ZZ E % |
| % QQQQ UUU A A N N T IIIII ZZZZZ EEEEE % |
| % % |
| % % |
| % MagickCore Methods to Reduce the Number of Unique Colors in an Image % |
| % % |
| % Software Design % |
| % John Cristy % |
| % July 1992 % |
| % % |
| % % |
| % Copyright 1999-2013 ImageMagick Studio LLC, a non-profit organization % |
| % dedicated to making software imaging solutions freely available. % |
| % % |
| % You may not use this file except in compliance with the License. You may % |
| % obtain a copy of the License at % |
| % % |
| % http://www.imagemagick.org/script/license.php % |
| % % |
| % Unless required by applicable law or agreed to in writing, software % |
| % distributed under the License is distributed on an "AS IS" BASIS, % |
| % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. % |
| % See the License for the specific language governing permissions and % |
| % limitations under the License. % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % Realism in computer graphics typically requires using 24 bits/pixel to |
| % generate an image. Yet many graphic display devices do not contain the |
| % amount of memory necessary to match the spatial and color resolution of |
| % the human eye. The Quantize methods takes a 24 bit image and reduces |
| % the number of colors so it can be displayed on raster device with less |
| % bits per pixel. In most instances, the quantized image closely |
| % resembles the original reference image. |
| % |
| % A reduction of colors in an image is also desirable for image |
| % transmission and real-time animation. |
| % |
| % QuantizeImage() takes a standard RGB or monochrome images and quantizes |
| % them down to some fixed number of colors. |
| % |
| % For purposes of color allocation, an image is a set of n pixels, where |
| % each pixel is a point in RGB space. RGB space is a 3-dimensional |
| % vector space, and each pixel, Pi, is defined by an ordered triple of |
| % red, green, and blue coordinates, (Ri, Gi, Bi). |
| % |
| % Each primary color component (red, green, or blue) represents an |
| % intensity which varies linearly from 0 to a maximum value, Cmax, which |
| % corresponds to full saturation of that color. Color allocation is |
| % defined over a domain consisting of the cube in RGB space with opposite |
| % vertices at (0,0,0) and (Cmax, Cmax, Cmax). QUANTIZE requires Cmax = |
| % 255. |
| % |
| % The algorithm maps this domain onto a tree in which each node |
| % represents a cube within that domain. In the following discussion |
| % these cubes are defined by the coordinate of two opposite vertices: |
| % The vertex nearest the origin in RGB space and the vertex farthest from |
| % the origin. |
| % |
| % The tree's root node represents the entire domain, (0,0,0) through |
| % (Cmax,Cmax,Cmax). Each lower level in the tree is generated by |
| % subdividing one node's cube into eight smaller cubes of equal size. |
| % This corresponds to bisecting the parent cube with planes passing |
| % through the midpoints of each edge. |
| % |
| % The basic algorithm operates in three phases: Classification, |
| % Reduction, and Assignment. Classification builds a color description |
| % tree for the image. Reduction collapses the tree until the number it |
| % represents, at most, the number of colors desired in the output image. |
| % Assignment defines the output image's color map and sets each pixel's |
| % color by restorage_class in the reduced tree. Our goal is to minimize |
| % the numerical discrepancies between the original colors and quantized |
| % colors (quantization error). |
| % |
| % Classification begins by initializing a color description tree of |
| % sufficient depth to represent each possible input color in a leaf. |
| % However, it is impractical to generate a fully-formed color description |
| % tree in the storage_class phase for realistic values of Cmax. If |
| % colors components in the input image are quantized to k-bit precision, |
| % so that Cmax= 2k-1, the tree would need k levels below the root node to |
| % allow representing each possible input color in a leaf. This becomes |
| % prohibitive because the tree's total number of nodes is 1 + |
| % sum(i=1, k, 8k). |
| % |
| % A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255. |
| % Therefore, to avoid building a fully populated tree, QUANTIZE: (1) |
| % Initializes data structures for nodes only as they are needed; (2) |
| % Chooses a maximum depth for the tree as a function of the desired |
| % number of colors in the output image (currently log2(colormap size)). |
| % |
| % For each pixel in the input image, storage_class scans downward from |
| % the root of the color description tree. At each level of the tree it |
| % identifies the single node which represents a cube in RGB space |
| % containing the pixel's color. It updates the following data for each |
| % such node: |
| % |
| % n1: Number of pixels whose color is contained in the RGB cube which |
| % this node represents; |
| % |
| % n2: Number of pixels whose color is not represented in a node at |
| % lower depth in the tree; initially, n2 = 0 for all nodes except |
| % leaves of the tree. |
| % |
| % Sr, Sg, Sb: Sums of the red, green, and blue component values for all |
| % pixels not classified at a lower depth. The combination of these sums |
| % and n2 will ultimately characterize the mean color of a set of |
| % pixels represented by this node. |
| % |
| % E: the distance squared in RGB space between each pixel contained |
| % within a node and the nodes' center. This represents the |
| % quantization error for a node. |
| % |
| % Reduction repeatedly prunes the tree until the number of nodes with n2 |
| % > 0 is less than or equal to the maximum number of colors allowed in |
| % the output image. On any given iteration over the tree, it selects |
| % those nodes whose E count is minimal for pruning and merges their color |
| % statistics upward. It uses a pruning threshold, Ep, to govern node |
| % selection as follows: |
| % |
| % Ep = 0 |
| % while number of nodes with (n2 > 0) > required maximum number of colors |
| % prune all nodes such that E <= Ep |
| % Set Ep to minimum E in remaining nodes |
| % |
| % This has the effect of minimizing any quantization error when merging |
| % two nodes together. |
| % |
| % When a node to be pruned has offspring, the pruning procedure invokes |
| % itself recursively in order to prune the tree from the leaves upward. |
| % n2, Sr, Sg, and Sb in a node being pruned are always added to the |
| % corresponding data in that node's parent. This retains the pruned |
| % node's color characteristics for later averaging. |
| % |
| % For each node, n2 pixels exist for which that node represents the |
| % smallest volume in RGB space containing those pixel's colors. When n2 |
| % > 0 the node will uniquely define a color in the output image. At the |
| % beginning of reduction, n2 = 0 for all nodes except a the leaves of |
| % the tree which represent colors present in the input image. |
| % |
| % The other pixel count, n1, indicates the total number of colors within |
| % the cubic volume which the node represents. This includes n1 - n2 |
| % pixels whose colors should be defined by nodes at a lower level in the |
| % tree. |
| % |
| % Assignment generates the output image from the pruned tree. The output |
| % image consists of two parts: (1) A color map, which is an array of |
| % color descriptions (RGB triples) for each color present in the output |
| % image; (2) A pixel array, which represents each pixel as an index |
| % into the color map array. |
| % |
| % First, the assignment phase makes one pass over the pruned color |
| % description tree to establish the image's color map. For each node |
| % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean |
| % color of all pixels that classify no lower than this node. Each of |
| % these colors becomes an entry in the color map. |
| % |
| % Finally, the assignment phase reclassifies each pixel in the pruned |
| % tree to identify the deepest node containing the pixel's color. The |
| % pixel's value in the pixel array becomes the index of this node's mean |
| % color in the color map. |
| % |
| % This method is based on a similar algorithm written by Paul Raveling. |
| % |
| */ |
| |
| /* |
| Include declarations. |
| */ |
| #include "MagickCore/studio.h" |
| #include "MagickCore/attribute.h" |
| #include "MagickCore/cache-view.h" |
| #include "MagickCore/color.h" |
| #include "MagickCore/color-private.h" |
| #include "MagickCore/colormap.h" |
| #include "MagickCore/colorspace.h" |
| #include "MagickCore/colorspace-private.h" |
| #include "MagickCore/enhance.h" |
| #include "MagickCore/exception.h" |
| #include "MagickCore/exception-private.h" |
| #include "MagickCore/histogram.h" |
| #include "MagickCore/image.h" |
| #include "MagickCore/image-private.h" |
| #include "MagickCore/list.h" |
| #include "MagickCore/memory_.h" |
| #include "MagickCore/monitor.h" |
| #include "MagickCore/monitor-private.h" |
| #include "MagickCore/option.h" |
| #include "MagickCore/pixel-accessor.h" |
| #include "MagickCore/pixel-private.h" |
| #include "MagickCore/quantize.h" |
| #include "MagickCore/quantum.h" |
| #include "MagickCore/quantum-private.h" |
| #include "MagickCore/resource_.h" |
| #include "MagickCore/string_.h" |
| #include "MagickCore/thread-private.h" |
| |
| /* |
| Define declarations. |
| */ |
| #if !defined(__APPLE__) && !defined(TARGET_OS_IPHONE) |
| #define CacheShift 2 |
| #else |
| #define CacheShift 3 |
| #endif |
| #define ErrorQueueLength 16 |
| #define MaxNodes 266817 |
| #define MaxTreeDepth 8 |
| #define NodesInAList 1920 |
| |
| /* |
| Typdef declarations. |
| */ |
| typedef struct _RealPixelInfo |
| { |
| double |
| red, |
| green, |
| blue, |
| alpha; |
| } RealPixelInfo; |
| |
| typedef struct _NodeInfo |
| { |
| struct _NodeInfo |
| *parent, |
| *child[16]; |
| |
| MagickSizeType |
| number_unique; |
| |
| RealPixelInfo |
| total_color; |
| |
| double |
| quantize_error; |
| |
| size_t |
| color_number, |
| id, |
| level; |
| } NodeInfo; |
| |
| typedef struct _Nodes |
| { |
| NodeInfo |
| *nodes; |
| |
| struct _Nodes |
| *next; |
| } Nodes; |
| |
| typedef struct _CubeInfo |
| { |
| NodeInfo |
| *root; |
| |
| size_t |
| colors, |
| maximum_colors; |
| |
| ssize_t |
| transparent_index; |
| |
| MagickSizeType |
| transparent_pixels; |
| |
| RealPixelInfo |
| target; |
| |
| double |
| distance, |
| pruning_threshold, |
| next_threshold; |
| |
| size_t |
| nodes, |
| free_nodes, |
| color_number; |
| |
| NodeInfo |
| *next_node; |
| |
| Nodes |
| *node_queue; |
| |
| MemoryInfo |
| *memory_info; |
| |
| ssize_t |
| *cache; |
| |
| RealPixelInfo |
| error[ErrorQueueLength]; |
| |
| double |
| weights[ErrorQueueLength]; |
| |
| QuantizeInfo |
| *quantize_info; |
| |
| MagickBooleanType |
| associate_alpha; |
| |
| ssize_t |
| x, |
| y; |
| |
| size_t |
| depth; |
| |
| MagickOffsetType |
| offset; |
| |
| MagickSizeType |
| span; |
| } CubeInfo; |
| |
| /* |
| Method prototypes. |
| */ |
| static CubeInfo |
| *GetCubeInfo(const QuantizeInfo *,const size_t,const size_t); |
| |
| static NodeInfo |
| *GetNodeInfo(CubeInfo *,const size_t,const size_t,NodeInfo *); |
| |
| static MagickBooleanType |
| AssignImageColors(Image *,CubeInfo *,ExceptionInfo *), |
| ClassifyImageColors(CubeInfo *,const Image *,ExceptionInfo *), |
| DitherImage(Image *,CubeInfo *,ExceptionInfo *), |
| SetGrayscaleImage(Image *,ExceptionInfo *); |
| |
| static size_t |
| DefineImageColormap(Image *,CubeInfo *,NodeInfo *); |
| |
| static void |
| ClosestColor(const Image *,CubeInfo *,const NodeInfo *), |
| DestroyCubeInfo(CubeInfo *), |
| PruneLevel(const Image *,CubeInfo *,const NodeInfo *), |
| PruneToCubeDepth(const Image *,CubeInfo *,const NodeInfo *), |
| ReduceImageColors(const Image *,CubeInfo *); |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % A c q u i r e Q u a n t i z e I n f o % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % AcquireQuantizeInfo() allocates the QuantizeInfo structure. |
| % |
| % The format of the AcquireQuantizeInfo method is: |
| % |
| % QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info) |
| % |
| % A description of each parameter follows: |
| % |
| % o image_info: the image info. |
| % |
| */ |
| MagickExport QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info) |
| { |
| QuantizeInfo |
| *quantize_info; |
| |
| quantize_info=(QuantizeInfo *) AcquireMagickMemory(sizeof(*quantize_info)); |
| if (quantize_info == (QuantizeInfo *) NULL) |
| ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); |
| GetQuantizeInfo(quantize_info); |
| if (image_info != (ImageInfo *) NULL) |
| { |
| const char |
| *option; |
| |
| quantize_info->dither_method=image_info->dither == MagickFalse ? |
| NoDitherMethod : RiemersmaDitherMethod; |
| option=GetImageOption(image_info,"dither"); |
| if (option != (const char *) NULL) |
| quantize_info->dither_method=(DitherMethod) ParseCommandOption( |
| MagickDitherOptions,MagickFalse,option); |
| quantize_info->measure_error=image_info->verbose; |
| } |
| return(quantize_info); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + A s s i g n I m a g e C o l o r s % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % AssignImageColors() generates the output image from the pruned tree. The |
| % output image consists of two parts: (1) A color map, which is an array |
| % of color descriptions (RGB triples) for each color present in the |
| % output image; (2) A pixel array, which represents each pixel as an |
| % index into the color map array. |
| % |
| % First, the assignment phase makes one pass over the pruned color |
| % description tree to establish the image's color map. For each node |
| % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean |
| % color of all pixels that classify no lower than this node. Each of |
| % these colors becomes an entry in the color map. |
| % |
| % Finally, the assignment phase reclassifies each pixel in the pruned |
| % tree to identify the deepest node containing the pixel's color. The |
| % pixel's value in the pixel array becomes the index of this node's mean |
| % color in the color map. |
| % |
| % The format of the AssignImageColors() method is: |
| % |
| % MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info) |
| % |
| % A description of each parameter follows. |
| % |
| % o image: the image. |
| % |
| % o cube_info: A pointer to the Cube structure. |
| % |
| */ |
| |
| static inline void AssociateAlphaPixel(const Image *image, |
| const CubeInfo *cube_info,const Quantum *pixel,RealPixelInfo *alpha_pixel) |
| { |
| double |
| alpha; |
| |
| if ((cube_info->associate_alpha == MagickFalse) || |
| (GetPixelAlpha(image,pixel)== OpaqueAlpha)) |
| { |
| alpha_pixel->red=(double) GetPixelRed(image,pixel); |
| alpha_pixel->green=(double) GetPixelGreen(image,pixel); |
| alpha_pixel->blue=(double) GetPixelBlue(image,pixel); |
| alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel); |
| return; |
| } |
| alpha=(double) (QuantumScale*GetPixelAlpha(image,pixel)); |
| alpha_pixel->red=alpha*GetPixelRed(image,pixel); |
| alpha_pixel->green=alpha*GetPixelGreen(image,pixel); |
| alpha_pixel->blue=alpha*GetPixelBlue(image,pixel); |
| alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel); |
| } |
| |
| static inline void AssociateAlphaPixelInfo(const CubeInfo *cube_info, |
| const PixelInfo *pixel,RealPixelInfo *alpha_pixel) |
| { |
| double |
| alpha; |
| |
| if ((cube_info->associate_alpha == MagickFalse) || |
| (pixel->alpha == OpaqueAlpha)) |
| { |
| alpha_pixel->red=(double) pixel->red; |
| alpha_pixel->green=(double) pixel->green; |
| alpha_pixel->blue=(double) pixel->blue; |
| alpha_pixel->alpha=(double) pixel->alpha; |
| return; |
| } |
| alpha=(double) (QuantumScale*pixel->alpha); |
| alpha_pixel->red=alpha*pixel->red; |
| alpha_pixel->green=alpha*pixel->green; |
| alpha_pixel->blue=alpha*pixel->blue; |
| alpha_pixel->alpha=(double) pixel->alpha; |
| } |
| |
| static inline Quantum ClampPixel(const MagickRealType value) |
| { |
| if (value < 0.0f) |
| return(0); |
| if (value >= (MagickRealType) QuantumRange) |
| return((Quantum) QuantumRange); |
| #if !defined(MAGICKCORE_HDRI_SUPPORT) |
| return((Quantum) (value+0.5f)); |
| #else |
| return(value); |
| #endif |
| } |
| |
| static inline size_t ColorToNodeId(const CubeInfo *cube_info, |
| const RealPixelInfo *pixel,size_t index) |
| { |
| size_t |
| id; |
| |
| id=(size_t) (((ScaleQuantumToChar(ClampPixel(pixel->red)) >> index) & 0x01) | |
| ((ScaleQuantumToChar(ClampPixel(pixel->green)) >> index) & 0x01) << 1 | |
| ((ScaleQuantumToChar(ClampPixel(pixel->blue)) >> index) & 0x01) << 2); |
| if (cube_info->associate_alpha != MagickFalse) |
| id|=((ScaleQuantumToChar(ClampPixel(pixel->alpha)) >> index) & 0x1) << 3; |
| return(id); |
| } |
| |
| static MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info, |
| ExceptionInfo *exception) |
| { |
| #define AssignImageTag "Assign/Image" |
| |
| ssize_t |
| y; |
| |
| /* |
| Allocate image colormap. |
| */ |
| if ((cube_info->quantize_info->colorspace != UndefinedColorspace) && |
| (cube_info->quantize_info->colorspace != CMYKColorspace)) |
| (void) TransformImageColorspace((Image *) image, |
| cube_info->quantize_info->colorspace,exception); |
| else |
| if (IssRGBCompatibleColorspace(image->colorspace) == MagickFalse) |
| (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception); |
| if (AcquireImageColormap(image,cube_info->colors,exception) == MagickFalse) |
| ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", |
| image->filename); |
| image->colors=0; |
| cube_info->transparent_pixels=0; |
| cube_info->transparent_index=(-1); |
| (void) DefineImageColormap(image,cube_info,cube_info->root); |
| /* |
| Create a reduced color image. |
| */ |
| if ((cube_info->quantize_info->dither_method != NoDitherMethod) && |
| (cube_info->quantize_info->dither_method != NoDitherMethod)) |
| (void) DitherImage(image,cube_info,exception); |
| else |
| { |
| CacheView |
| *image_view; |
| |
| MagickBooleanType |
| status; |
| |
| status=MagickTrue; |
| image_view=AcquireAuthenticCacheView(image,exception); |
| #if defined(MAGICKCORE_OPENMP_SUPPORT) |
| #pragma omp parallel for schedule(static,4) shared(status) \ |
| magick_threads(image,image,image->rows,1) |
| #endif |
| for (y=0; y < (ssize_t) image->rows; y++) |
| { |
| CubeInfo |
| cube; |
| |
| register Quantum |
| *restrict q; |
| |
| register ssize_t |
| x; |
| |
| ssize_t |
| count; |
| |
| if (status == MagickFalse) |
| continue; |
| q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1, |
| exception); |
| if (q == (Quantum *) NULL) |
| { |
| status=MagickFalse; |
| continue; |
| } |
| cube=(*cube_info); |
| for (x=0; x < (ssize_t) image->columns; x+=count) |
| { |
| RealPixelInfo |
| pixel; |
| |
| register const NodeInfo |
| *node_info; |
| |
| register ssize_t |
| i; |
| |
| size_t |
| id, |
| index; |
| |
| /* |
| Identify the deepest node containing the pixel's color. |
| */ |
| for (count=1; (x+count) < (ssize_t) image->columns; count++) |
| { |
| PixelInfo |
| packet; |
| |
| GetPixelInfoPixel(image,q+count*GetPixelChannels(image),&packet); |
| if (IsPixelEquivalent(image,q,&packet) == MagickFalse) |
| break; |
| } |
| AssociateAlphaPixel(image,&cube,q,&pixel); |
| node_info=cube.root; |
| for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--) |
| { |
| id=ColorToNodeId(&cube,&pixel,index); |
| if (node_info->child[id] == (NodeInfo *) NULL) |
| break; |
| node_info=node_info->child[id]; |
| } |
| /* |
| Find closest color among siblings and their children. |
| */ |
| cube.target=pixel; |
| cube.distance=(double) (4.0*(QuantumRange+1.0)* |
| (QuantumRange+1.0)+1.0); |
| ClosestColor(image,&cube,node_info->parent); |
| index=cube.color_number; |
| for (i=0; i < (ssize_t) count; i++) |
| { |
| if (image->storage_class == PseudoClass) |
| SetPixelIndex(image,(Quantum) index,q); |
| if (cube.quantize_info->measure_error == MagickFalse) |
| { |
| SetPixelRed(image,ClampToQuantum( |
| image->colormap[index].red),q); |
| SetPixelGreen(image,ClampToQuantum( |
| image->colormap[index].green),q); |
| SetPixelBlue(image,ClampToQuantum( |
| image->colormap[index].blue),q); |
| if (cube.associate_alpha != MagickFalse) |
| SetPixelAlpha(image,ClampToQuantum( |
| image->colormap[index].alpha),q); |
| } |
| q+=GetPixelChannels(image); |
| } |
| } |
| if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) |
| status=MagickFalse; |
| if (image->progress_monitor != (MagickProgressMonitor) NULL) |
| { |
| MagickBooleanType |
| proceed; |
| |
| #if defined(MAGICKCORE_OPENMP_SUPPORT) |
| #pragma omp critical (MagickCore_AssignImageColors) |
| #endif |
| proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y, |
| image->rows); |
| if (proceed == MagickFalse) |
| status=MagickFalse; |
| } |
| } |
| image_view=DestroyCacheView(image_view); |
| } |
| if (cube_info->quantize_info->measure_error != MagickFalse) |
| (void) GetImageQuantizeError(image,exception); |
| if ((cube_info->quantize_info->number_colors == 2) && |
| (cube_info->quantize_info->colorspace == GRAYColorspace)) |
| { |
| double |
| intensity; |
| |
| register PixelInfo |
| *restrict q; |
| |
| register ssize_t |
| i; |
| |
| /* |
| Monochrome image. |
| */ |
| q=image->colormap; |
| for (i=0; i < (ssize_t) image->colors; i++) |
| { |
| intensity=(double) ((double) GetPixelInfoIntensity(q) < |
| ((double) QuantumRange/2.0) ? 0 : QuantumRange); |
| q->red=intensity; |
| q->green=intensity; |
| q->blue=intensity; |
| q++; |
| } |
| } |
| (void) SyncImage(image,exception); |
| if ((cube_info->quantize_info->colorspace != UndefinedColorspace) && |
| (cube_info->quantize_info->colorspace != CMYKColorspace)) |
| (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception); |
| return(MagickTrue); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + C l a s s i f y I m a g e C o l o r s % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % ClassifyImageColors() begins by initializing a color description tree |
| % of sufficient depth to represent each possible input color in a leaf. |
| % However, it is impractical to generate a fully-formed color |
| % description tree in the storage_class phase for realistic values of |
| % Cmax. If colors components in the input image are quantized to k-bit |
| % precision, so that Cmax= 2k-1, the tree would need k levels below the |
| % root node to allow representing each possible input color in a leaf. |
| % This becomes prohibitive because the tree's total number of nodes is |
| % 1 + sum(i=1,k,8k). |
| % |
| % A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255. |
| % Therefore, to avoid building a fully populated tree, QUANTIZE: (1) |
| % Initializes data structures for nodes only as they are needed; (2) |
| % Chooses a maximum depth for the tree as a function of the desired |
| % number of colors in the output image (currently log2(colormap size)). |
| % |
| % For each pixel in the input image, storage_class scans downward from |
| % the root of the color description tree. At each level of the tree it |
| % identifies the single node which represents a cube in RGB space |
| % containing It updates the following data for each such node: |
| % |
| % n1 : Number of pixels whose color is contained in the RGB cube |
| % which this node represents; |
| % |
| % n2 : Number of pixels whose color is not represented in a node at |
| % lower depth in the tree; initially, n2 = 0 for all nodes except |
| % leaves of the tree. |
| % |
| % Sr, Sg, Sb : Sums of the red, green, and blue component values for |
| % all pixels not classified at a lower depth. The combination of |
| % these sums and n2 will ultimately characterize the mean color of a |
| % set of pixels represented by this node. |
| % |
| % E: the distance squared in RGB space between each pixel contained |
| % within a node and the nodes' center. This represents the quantization |
| % error for a node. |
| % |
| % The format of the ClassifyImageColors() method is: |
| % |
| % MagickBooleanType ClassifyImageColors(CubeInfo *cube_info, |
| % const Image *image,ExceptionInfo *exception) |
| % |
| % A description of each parameter follows. |
| % |
| % o cube_info: A pointer to the Cube structure. |
| % |
| % o image: the image. |
| % |
| */ |
| |
| static inline void SetAssociatedAlpha(const Image *image,CubeInfo *cube_info) |
| { |
| MagickBooleanType |
| associate_alpha; |
| |
| associate_alpha=image->alpha_trait == BlendPixelTrait ? MagickTrue : |
| MagickFalse; |
| if (cube_info->quantize_info->colorspace == TransparentColorspace) |
| associate_alpha=MagickFalse; |
| if ((cube_info->quantize_info->number_colors == 2) && |
| (cube_info->quantize_info->colorspace == GRAYColorspace)) |
| associate_alpha=MagickFalse; |
| cube_info->associate_alpha=associate_alpha; |
| } |
| |
| static MagickBooleanType ClassifyImageColors(CubeInfo *cube_info, |
| const Image *image,ExceptionInfo *exception) |
| { |
| #define ClassifyImageTag "Classify/Image" |
| |
| CacheView |
| *image_view; |
| |
| MagickBooleanType |
| proceed; |
| |
| double |
| bisect; |
| |
| NodeInfo |
| *node_info; |
| |
| RealPixelInfo |
| error, |
| mid, |
| midpoint, |
| pixel; |
| |
| size_t |
| count, |
| id, |
| index, |
| level; |
| |
| ssize_t |
| y; |
| |
| /* |
| Classify the first cube_info->maximum_colors colors to a tree depth of 8. |
| */ |
| SetAssociatedAlpha(image,cube_info); |
| if ((cube_info->quantize_info->colorspace != UndefinedColorspace) && |
| (cube_info->quantize_info->colorspace != CMYKColorspace)) |
| (void) TransformImageColorspace((Image *) image, |
| cube_info->quantize_info->colorspace,exception); |
| else |
| if (IssRGBCompatibleColorspace(image->colorspace) == MagickFalse) |
| (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception); |
| midpoint.red=(double) QuantumRange/2.0; |
| midpoint.green=(double) QuantumRange/2.0; |
| midpoint.blue=(double) QuantumRange/2.0; |
| midpoint.alpha=(double) QuantumRange/2.0; |
| error.alpha=0.0; |
| image_view=AcquireVirtualCacheView(image,exception); |
| for (y=0; y < (ssize_t) image->rows; y++) |
| { |
| register const Quantum |
| *restrict p; |
| |
| register ssize_t |
| x; |
| |
| p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception); |
| if (p == (const Quantum *) NULL) |
| break; |
| if (cube_info->nodes > MaxNodes) |
| { |
| /* |
| Prune one level if the color tree is too large. |
| */ |
| PruneLevel(image,cube_info,cube_info->root); |
| cube_info->depth--; |
| } |
| for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count) |
| { |
| /* |
| Start at the root and descend the color cube tree. |
| */ |
| for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++) |
| { |
| PixelInfo |
| packet; |
| |
| GetPixelInfoPixel(image,p+count*GetPixelChannels(image),&packet); |
| if (IsPixelEquivalent(image,p,&packet) == MagickFalse) |
| break; |
| } |
| AssociateAlphaPixel(image,cube_info,p,&pixel); |
| index=MaxTreeDepth-1; |
| bisect=((double) QuantumRange+1.0)/2.0; |
| mid=midpoint; |
| node_info=cube_info->root; |
| for (level=1; level <= MaxTreeDepth; level++) |
| { |
| bisect*=0.5; |
| id=ColorToNodeId(cube_info,&pixel,index); |
| mid.red+=(id & 1) != 0 ? bisect : -bisect; |
| mid.green+=(id & 2) != 0 ? bisect : -bisect; |
| mid.blue+=(id & 4) != 0 ? bisect : -bisect; |
| mid.alpha+=(id & 8) != 0 ? bisect : -bisect; |
| if (node_info->child[id] == (NodeInfo *) NULL) |
| { |
| /* |
| Set colors of new node to contain pixel. |
| */ |
| node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info); |
| if (node_info->child[id] == (NodeInfo *) NULL) |
| (void) ThrowMagickException(exception,GetMagickModule(), |
| ResourceLimitError,"MemoryAllocationFailed","`%s'", |
| image->filename); |
| if (level == MaxTreeDepth) |
| cube_info->colors++; |
| } |
| /* |
| Approximate the quantization error represented by this node. |
| */ |
| node_info=node_info->child[id]; |
| error.red=QuantumScale*(pixel.red-mid.red); |
| error.green=QuantumScale*(pixel.green-mid.green); |
| error.blue=QuantumScale*(pixel.blue-mid.blue); |
| if (cube_info->associate_alpha != MagickFalse) |
| error.alpha=QuantumScale*(pixel.alpha-mid.alpha); |
| node_info->quantize_error+=count*sqrt((double) (error.red*error.red+ |
| error.green*error.green+error.blue*error.blue+ |
| error.alpha*error.alpha)); |
| cube_info->root->quantize_error+=node_info->quantize_error; |
| index--; |
| } |
| /* |
| Sum RGB for this leaf for later derivation of the mean cube color. |
| */ |
| node_info->number_unique+=count; |
| node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red); |
| node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green); |
| node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue); |
| if (cube_info->associate_alpha != MagickFalse) |
| node_info->total_color.alpha+=count*QuantumScale*ClampPixel( |
| pixel.alpha); |
| p+=count*GetPixelChannels(image); |
| } |
| if (cube_info->colors > cube_info->maximum_colors) |
| { |
| PruneToCubeDepth(image,cube_info,cube_info->root); |
| break; |
| } |
| proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y, |
| image->rows); |
| if (proceed == MagickFalse) |
| break; |
| } |
| for (y++; y < (ssize_t) image->rows; y++) |
| { |
| register const Quantum |
| *restrict p; |
| |
| register ssize_t |
| x; |
| |
| p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception); |
| if (p == (const Quantum *) NULL) |
| break; |
| if (cube_info->nodes > MaxNodes) |
| { |
| /* |
| Prune one level if the color tree is too large. |
| */ |
| PruneLevel(image,cube_info,cube_info->root); |
| cube_info->depth--; |
| } |
| for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count) |
| { |
| /* |
| Start at the root and descend the color cube tree. |
| */ |
| for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++) |
| { |
| PixelInfo |
| packet; |
| |
| GetPixelInfoPixel(image,p+count*GetPixelChannels(image),&packet); |
| if (IsPixelEquivalent(image,p,&packet) == MagickFalse) |
| break; |
| } |
| AssociateAlphaPixel(image,cube_info,p,&pixel); |
| index=MaxTreeDepth-1; |
| bisect=((double) QuantumRange+1.0)/2.0; |
| mid=midpoint; |
| node_info=cube_info->root; |
| for (level=1; level <= cube_info->depth; level++) |
| { |
| bisect*=0.5; |
| id=ColorToNodeId(cube_info,&pixel,index); |
| mid.red+=(id & 1) != 0 ? bisect : -bisect; |
| mid.green+=(id & 2) != 0 ? bisect : -bisect; |
| mid.blue+=(id & 4) != 0 ? bisect : -bisect; |
| mid.alpha+=(id & 8) != 0 ? bisect : -bisect; |
| if (node_info->child[id] == (NodeInfo *) NULL) |
| { |
| /* |
| Set colors of new node to contain pixel. |
| */ |
| node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info); |
| if (node_info->child[id] == (NodeInfo *) NULL) |
| (void) ThrowMagickException(exception,GetMagickModule(), |
| ResourceLimitError,"MemoryAllocationFailed","%s", |
| image->filename); |
| if (level == cube_info->depth) |
| cube_info->colors++; |
| } |
| /* |
| Approximate the quantization error represented by this node. |
| */ |
| node_info=node_info->child[id]; |
| error.red=QuantumScale*(pixel.red-mid.red); |
| error.green=QuantumScale*(pixel.green-mid.green); |
| error.blue=QuantumScale*(pixel.blue-mid.blue); |
| if (cube_info->associate_alpha != MagickFalse) |
| error.alpha=QuantumScale*(pixel.alpha-mid.alpha); |
| node_info->quantize_error+=count*sqrt((double) (error.red*error.red+ |
| error.green*error.green+error.blue*error.blue+ |
| error.alpha*error.alpha)); |
| cube_info->root->quantize_error+=node_info->quantize_error; |
| index--; |
| } |
| /* |
| Sum RGB for this leaf for later derivation of the mean cube color. |
| */ |
| node_info->number_unique+=count; |
| node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red); |
| node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green); |
| node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue); |
| if (cube_info->associate_alpha != MagickFalse) |
| node_info->total_color.alpha+=count*QuantumScale*ClampPixel( |
| pixel.alpha); |
| p+=count*GetPixelChannels(image); |
| } |
| proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y, |
| image->rows); |
| if (proceed == MagickFalse) |
| break; |
| } |
| image_view=DestroyCacheView(image_view); |
| if ((cube_info->quantize_info->colorspace != UndefinedColorspace) && |
| (cube_info->quantize_info->colorspace != CMYKColorspace)) |
| (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception); |
| return(MagickTrue); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % C l o n e Q u a n t i z e I n f o % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % CloneQuantizeInfo() makes a duplicate of the given quantize info structure, |
| % or if quantize info is NULL, a new one. |
| % |
| % The format of the CloneQuantizeInfo method is: |
| % |
| % QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info) |
| % |
| % A description of each parameter follows: |
| % |
| % o clone_info: Method CloneQuantizeInfo returns a duplicate of the given |
| % quantize info, or if image info is NULL a new one. |
| % |
| % o quantize_info: a structure of type info. |
| % |
| */ |
| MagickExport QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info) |
| { |
| QuantizeInfo |
| *clone_info; |
| |
| clone_info=(QuantizeInfo *) AcquireMagickMemory(sizeof(*clone_info)); |
| if (clone_info == (QuantizeInfo *) NULL) |
| ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); |
| GetQuantizeInfo(clone_info); |
| if (quantize_info == (QuantizeInfo *) NULL) |
| return(clone_info); |
| clone_info->number_colors=quantize_info->number_colors; |
| clone_info->tree_depth=quantize_info->tree_depth; |
| clone_info->dither_method=quantize_info->dither_method; |
| clone_info->colorspace=quantize_info->colorspace; |
| clone_info->measure_error=quantize_info->measure_error; |
| return(clone_info); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + C l o s e s t C o l o r % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % ClosestColor() traverses the color cube tree at a particular node and |
| % determines which colormap entry best represents the input color. |
| % |
| % The format of the ClosestColor method is: |
| % |
| % void ClosestColor(const Image *image,CubeInfo *cube_info, |
| % const NodeInfo *node_info) |
| % |
| % A description of each parameter follows. |
| % |
| % o image: the image. |
| % |
| % o cube_info: A pointer to the Cube structure. |
| % |
| % o node_info: the address of a structure of type NodeInfo which points to a |
| % node in the color cube tree that is to be pruned. |
| % |
| */ |
| static void ClosestColor(const Image *image,CubeInfo *cube_info, |
| const NodeInfo *node_info) |
| { |
| register ssize_t |
| i; |
| |
| size_t |
| number_children; |
| |
| /* |
| Traverse any children. |
| */ |
| number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; |
| for (i=0; i < (ssize_t) number_children; i++) |
| if (node_info->child[i] != (NodeInfo *) NULL) |
| ClosestColor(image,cube_info,node_info->child[i]); |
| if (node_info->number_unique != 0) |
| { |
| double |
| pixel; |
| |
| register double |
| alpha, |
| beta, |
| distance; |
| |
| register PixelInfo |
| *restrict p; |
| |
| register RealPixelInfo |
| *restrict q; |
| |
| /* |
| Determine if this color is "closest". |
| */ |
| p=image->colormap+node_info->color_number; |
| q=(&cube_info->target); |
| alpha=1.0; |
| beta=1.0; |
| if (cube_info->associate_alpha != MagickFalse) |
| { |
| alpha=(double) (QuantumScale*p->alpha); |
| beta=(double) (QuantumScale*q->alpha); |
| } |
| pixel=alpha*p->red-beta*q->red; |
| distance=pixel*pixel; |
| if (distance <= cube_info->distance) |
| { |
| pixel=alpha*p->green-beta*q->green; |
| distance+=pixel*pixel; |
| if (distance <= cube_info->distance) |
| { |
| pixel=alpha*p->blue-beta*q->blue; |
| distance+=pixel*pixel; |
| if (distance <= cube_info->distance) |
| { |
| pixel=alpha-beta; |
| distance+=pixel*pixel; |
| if (distance <= cube_info->distance) |
| { |
| cube_info->distance=distance; |
| cube_info->color_number=node_info->color_number; |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % C o m p r e s s I m a g e C o l o r m a p % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % CompressImageColormap() compresses an image colormap by removing any |
| % duplicate or unused color entries. |
| % |
| % The format of the CompressImageColormap method is: |
| % |
| % MagickBooleanType CompressImageColormap(Image *image, |
| % ExceptionInfo *exception) |
| % |
| % A description of each parameter follows: |
| % |
| % o image: the image. |
| % |
| % o exception: return any errors or warnings in this structure. |
| % |
| */ |
| MagickExport MagickBooleanType CompressImageColormap(Image *image, |
| ExceptionInfo *exception) |
| { |
| QuantizeInfo |
| quantize_info; |
| |
| assert(image != (Image *) NULL); |
| assert(image->signature == MagickSignature); |
| if (image->debug != MagickFalse) |
| (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); |
| if (IsPaletteImage(image,exception) == MagickFalse) |
| return(MagickFalse); |
| GetQuantizeInfo(&quantize_info); |
| quantize_info.number_colors=image->colors; |
| quantize_info.tree_depth=MaxTreeDepth; |
| return(QuantizeImage(&quantize_info,image,exception)); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + D e f i n e I m a g e C o l o r m a p % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % DefineImageColormap() traverses the color cube tree and notes each colormap |
| % entry. A colormap entry is any node in the color cube tree where the |
| % of unique colors is not zero. DefineImageColormap() returns the number of |
| % colors in the image colormap. |
| % |
| % The format of the DefineImageColormap method is: |
| % |
| % size_t DefineImageColormap(Image *image,CubeInfo *cube_info, |
| % NodeInfo *node_info) |
| % |
| % A description of each parameter follows. |
| % |
| % o image: the image. |
| % |
| % o cube_info: A pointer to the Cube structure. |
| % |
| % o node_info: the address of a structure of type NodeInfo which points to a |
| % node in the color cube tree that is to be pruned. |
| % |
| */ |
| static size_t DefineImageColormap(Image *image,CubeInfo *cube_info, |
| NodeInfo *node_info) |
| { |
| register ssize_t |
| i; |
| |
| size_t |
| number_children; |
| |
| /* |
| Traverse any children. |
| */ |
| number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; |
| for (i=0; i < (ssize_t) number_children; i++) |
| if (node_info->child[i] != (NodeInfo *) NULL) |
| (void) DefineImageColormap(image,cube_info,node_info->child[i]); |
| if (node_info->number_unique != 0) |
| { |
| register double |
| alpha; |
| |
| register PixelInfo |
| *restrict q; |
| |
| /* |
| Colormap entry is defined by the mean color in this cube. |
| */ |
| q=image->colormap+image->colors; |
| alpha=(double) ((MagickOffsetType) node_info->number_unique); |
| alpha=PerceptibleReciprocal(alpha); |
| if (cube_info->associate_alpha == MagickFalse) |
| { |
| q->red=(double) ClampToQuantum(alpha*QuantumRange* |
| node_info->total_color.red); |
| q->green=(double) ClampToQuantum(alpha*QuantumRange* |
| node_info->total_color.green); |
| q->blue=(double) ClampToQuantum(alpha*QuantumRange* |
| node_info->total_color.blue); |
| q->alpha=(double) OpaqueAlpha; |
| } |
| else |
| { |
| double |
| opacity; |
| |
| opacity=(double) (alpha*QuantumRange*node_info->total_color.alpha); |
| q->alpha=(double) ClampToQuantum((opacity)); |
| if (q->alpha == OpaqueAlpha) |
| { |
| q->red=(double) ClampToQuantum(alpha*QuantumRange* |
| node_info->total_color.red); |
| q->green=(double) ClampToQuantum(alpha*QuantumRange* |
| node_info->total_color.green); |
| q->blue=(double) ClampToQuantum(alpha*QuantumRange* |
| node_info->total_color.blue); |
| } |
| else |
| { |
| double |
| gamma; |
| |
| gamma=(double) (QuantumScale*q->alpha); |
| gamma=PerceptibleReciprocal(gamma); |
| q->red=(double) ClampToQuantum(alpha*gamma*QuantumRange* |
| node_info->total_color.red); |
| q->green=(double) ClampToQuantum(alpha*gamma*QuantumRange* |
| node_info->total_color.green); |
| q->blue=(double) ClampToQuantum(alpha*gamma*QuantumRange* |
| node_info->total_color.blue); |
| if (node_info->number_unique > cube_info->transparent_pixels) |
| { |
| cube_info->transparent_pixels=node_info->number_unique; |
| cube_info->transparent_index=(ssize_t) image->colors; |
| } |
| } |
| } |
| node_info->color_number=image->colors++; |
| } |
| return(image->colors); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + D e s t r o y C u b e I n f o % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % DestroyCubeInfo() deallocates memory associated with an image. |
| % |
| % The format of the DestroyCubeInfo method is: |
| % |
| % DestroyCubeInfo(CubeInfo *cube_info) |
| % |
| % A description of each parameter follows: |
| % |
| % o cube_info: the address of a structure of type CubeInfo. |
| % |
| */ |
| static void DestroyCubeInfo(CubeInfo *cube_info) |
| { |
| register Nodes |
| *nodes; |
| |
| /* |
| Release color cube tree storage. |
| */ |
| do |
| { |
| nodes=cube_info->node_queue->next; |
| cube_info->node_queue->nodes=(NodeInfo *) RelinquishMagickMemory( |
| cube_info->node_queue->nodes); |
| cube_info->node_queue=(Nodes *) RelinquishMagickMemory( |
| cube_info->node_queue); |
| cube_info->node_queue=nodes; |
| } while (cube_info->node_queue != (Nodes *) NULL); |
| if (cube_info->memory_info != (MemoryInfo *) NULL) |
| cube_info->memory_info=RelinquishVirtualMemory(cube_info->memory_info); |
| cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info); |
| cube_info=(CubeInfo *) RelinquishMagickMemory(cube_info); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % D e s t r o y Q u a n t i z e I n f o % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % DestroyQuantizeInfo() deallocates memory associated with an QuantizeInfo |
| % structure. |
| % |
| % The format of the DestroyQuantizeInfo method is: |
| % |
| % QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info) |
| % |
| % A description of each parameter follows: |
| % |
| % o quantize_info: Specifies a pointer to an QuantizeInfo structure. |
| % |
| */ |
| MagickExport QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info) |
| { |
| (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); |
| assert(quantize_info != (QuantizeInfo *) NULL); |
| assert(quantize_info->signature == MagickSignature); |
| quantize_info->signature=(~MagickSignature); |
| quantize_info=(QuantizeInfo *) RelinquishMagickMemory(quantize_info); |
| return(quantize_info); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + D i t h e r I m a g e % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % DitherImage() distributes the difference between an original image and |
| % the corresponding color reduced algorithm to neighboring pixels using |
| % serpentine-scan Floyd-Steinberg error diffusion. DitherImage returns |
| % MagickTrue if the image is dithered otherwise MagickFalse. |
| % |
| % The format of the DitherImage method is: |
| % |
| % MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info, |
| % ExceptionInfo *exception) |
| % |
| % A description of each parameter follows. |
| % |
| % o image: the image. |
| % |
| % o cube_info: A pointer to the Cube structure. |
| % |
| % o exception: return any errors or warnings in this structure. |
| % |
| */ |
| |
| static RealPixelInfo **DestroyPixelThreadSet(RealPixelInfo **pixels) |
| { |
| register ssize_t |
| i; |
| |
| assert(pixels != (RealPixelInfo **) NULL); |
| for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++) |
| if (pixels[i] != (RealPixelInfo *) NULL) |
| pixels[i]=(RealPixelInfo *) RelinquishMagickMemory(pixels[i]); |
| pixels=(RealPixelInfo **) RelinquishMagickMemory(pixels); |
| return(pixels); |
| } |
| |
| static RealPixelInfo **AcquirePixelThreadSet(const size_t count) |
| { |
| RealPixelInfo |
| **pixels; |
| |
| register ssize_t |
| i; |
| |
| size_t |
| number_threads; |
| |
| number_threads=(size_t) GetMagickResourceLimit(ThreadResource); |
| pixels=(RealPixelInfo **) AcquireQuantumMemory(number_threads, |
| sizeof(*pixels)); |
| if (pixels == (RealPixelInfo **) NULL) |
| return((RealPixelInfo **) NULL); |
| (void) ResetMagickMemory(pixels,0,number_threads*sizeof(*pixels)); |
| for (i=0; i < (ssize_t) number_threads; i++) |
| { |
| pixels[i]=(RealPixelInfo *) AcquireQuantumMemory(count,2*sizeof(**pixels)); |
| if (pixels[i] == (RealPixelInfo *) NULL) |
| return(DestroyPixelThreadSet(pixels)); |
| } |
| return(pixels); |
| } |
| |
| static inline ssize_t CacheOffset(CubeInfo *cube_info, |
| const RealPixelInfo *pixel) |
| { |
| #define RedShift(pixel) (((pixel) >> CacheShift) << (0*(8-CacheShift))) |
| #define GreenShift(pixel) (((pixel) >> CacheShift) << (1*(8-CacheShift))) |
| #define BlueShift(pixel) (((pixel) >> CacheShift) << (2*(8-CacheShift))) |
| #define AlphaShift(pixel) (((pixel) >> CacheShift) << (3*(8-CacheShift))) |
| |
| ssize_t |
| offset; |
| |
| offset=(ssize_t) (RedShift(ScaleQuantumToChar(ClampPixel(pixel->red))) | |
| GreenShift(ScaleQuantumToChar(ClampPixel(pixel->green))) | |
| BlueShift(ScaleQuantumToChar(ClampPixel(pixel->blue)))); |
| if (cube_info->associate_alpha != MagickFalse) |
| offset|=AlphaShift(ScaleQuantumToChar(ClampPixel(pixel->alpha))); |
| return(offset); |
| } |
| |
| static MagickBooleanType FloydSteinbergDither(Image *image,CubeInfo *cube_info, |
| ExceptionInfo *exception) |
| { |
| #define DitherImageTag "Dither/Image" |
| |
| CacheView |
| *image_view; |
| |
| MagickBooleanType |
| status; |
| |
| RealPixelInfo |
| **pixels; |
| |
| ssize_t |
| y; |
| |
| /* |
| Distribute quantization error using Floyd-Steinberg. |
| */ |
| pixels=AcquirePixelThreadSet(image->columns); |
| if (pixels == (RealPixelInfo **) NULL) |
| return(MagickFalse); |
| status=MagickTrue; |
| image_view=AcquireAuthenticCacheView(image,exception); |
| for (y=0; y < (ssize_t) image->rows; y++) |
| { |
| const int |
| id = GetOpenMPThreadId(); |
| |
| CubeInfo |
| cube; |
| |
| RealPixelInfo |
| *current, |
| *previous; |
| |
| register Quantum |
| *restrict q; |
| |
| register ssize_t |
| x; |
| |
| size_t |
| index; |
| |
| ssize_t |
| v; |
| |
| if (status == MagickFalse) |
| continue; |
| q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception); |
| if (q == (Quantum *) NULL) |
| { |
| status=MagickFalse; |
| continue; |
| } |
| q+=(y & 0x01)*image->columns*GetPixelChannels(image); |
| cube=(*cube_info); |
| current=pixels[id]+(y & 0x01)*image->columns; |
| previous=pixels[id]+((y+1) & 0x01)*image->columns; |
| v=(ssize_t) ((y & 0x01) != 0 ? -1 : 1); |
| for (x=0; x < (ssize_t) image->columns; x++) |
| { |
| RealPixelInfo |
| color, |
| pixel; |
| |
| register ssize_t |
| i; |
| |
| ssize_t |
| u; |
| |
| q-=(y & 0x01)*GetPixelChannels(image); |
| u=(y & 0x01) != 0 ? (ssize_t) image->columns-1-x : x; |
| AssociateAlphaPixel(image,&cube,q,&pixel); |
| if (x > 0) |
| { |
| pixel.red+=7*current[u-v].red/16; |
| pixel.green+=7*current[u-v].green/16; |
| pixel.blue+=7*current[u-v].blue/16; |
| if (cube.associate_alpha != MagickFalse) |
| pixel.alpha+=7*current[u-v].alpha/16; |
| } |
| if (y > 0) |
| { |
| if (x < (ssize_t) (image->columns-1)) |
| { |
| pixel.red+=previous[u+v].red/16; |
| pixel.green+=previous[u+v].green/16; |
| pixel.blue+=previous[u+v].blue/16; |
| if (cube.associate_alpha != MagickFalse) |
| pixel.alpha+=previous[u+v].alpha/16; |
| } |
| pixel.red+=5*previous[u].red/16; |
| pixel.green+=5*previous[u].green/16; |
| pixel.blue+=5*previous[u].blue/16; |
| if (cube.associate_alpha != MagickFalse) |
| pixel.alpha+=5*previous[u].alpha/16; |
| if (x > 0) |
| { |
| pixel.red+=3*previous[u-v].red/16; |
| pixel.green+=3*previous[u-v].green/16; |
| pixel.blue+=3*previous[u-v].blue/16; |
| if (cube.associate_alpha != MagickFalse) |
| pixel.alpha+=3*previous[u-v].alpha/16; |
| } |
| } |
| pixel.red=(double) ClampPixel(pixel.red); |
| pixel.green=(double) ClampPixel(pixel.green); |
| pixel.blue=(double) ClampPixel(pixel.blue); |
| if (cube.associate_alpha != MagickFalse) |
| pixel.alpha=(double) ClampPixel(pixel.alpha); |
| i=CacheOffset(&cube,&pixel); |
| if (cube.cache[i] < 0) |
| { |
| register NodeInfo |
| *node_info; |
| |
| register size_t |
| id; |
| |
| /* |
| Identify the deepest node containing the pixel's color. |
| */ |
| node_info=cube.root; |
| for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--) |
| { |
| id=ColorToNodeId(&cube,&pixel,index); |
| if (node_info->child[id] == (NodeInfo *) NULL) |
| break; |
| node_info=node_info->child[id]; |
| } |
| /* |
| Find closest color among siblings and their children. |
| */ |
| cube.target=pixel; |
| cube.distance=(double) (4.0*(QuantumRange+1.0)*(QuantumRange+1.0)+ |
| 1.0); |
| ClosestColor(image,&cube,node_info->parent); |
| cube.cache[i]=(ssize_t) cube.color_number; |
| } |
| /* |
| Assign pixel to closest colormap entry. |
| */ |
| index=(size_t) cube.cache[i]; |
| if (image->storage_class == PseudoClass) |
| SetPixelIndex(image,(Quantum) index,q); |
| if (cube.quantize_info->measure_error == MagickFalse) |
| { |
| SetPixelRed(image,ClampToQuantum(image->colormap[index].red),q); |
| SetPixelGreen(image,ClampToQuantum(image->colormap[index].green),q); |
| SetPixelBlue(image,ClampToQuantum(image->colormap[index].blue),q); |
| if (cube.associate_alpha != MagickFalse) |
| SetPixelAlpha(image,ClampToQuantum(image->colormap[index].alpha),q); |
| } |
| if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) |
| status=MagickFalse; |
| /* |
| Store the error. |
| */ |
| AssociateAlphaPixelInfo(&cube,image->colormap+index,&color); |
| current[u].red=pixel.red-color.red; |
| current[u].green=pixel.green-color.green; |
| current[u].blue=pixel.blue-color.blue; |
| if (cube.associate_alpha != MagickFalse) |
| current[u].alpha=pixel.alpha-color.alpha; |
| if (image->progress_monitor != (MagickProgressMonitor) NULL) |
| { |
| MagickBooleanType |
| proceed; |
| |
| #if defined(MAGICKCORE_OPENMP_SUPPORT) |
| #pragma omp critical (MagickCore_FloydSteinbergDither) |
| #endif |
| proceed=SetImageProgress(image,DitherImageTag,(MagickOffsetType) y, |
| image->rows); |
| if (proceed == MagickFalse) |
| status=MagickFalse; |
| } |
| q+=((y+1) & 0x01)*GetPixelChannels(image); |
| } |
| } |
| image_view=DestroyCacheView(image_view); |
| pixels=DestroyPixelThreadSet(pixels); |
| return(MagickTrue); |
| } |
| |
| static MagickBooleanType |
| RiemersmaDither(Image *,CacheView *,CubeInfo *,const unsigned int, |
| ExceptionInfo *exception); |
| |
| static void Riemersma(Image *image,CacheView *image_view,CubeInfo *cube_info, |
| const size_t level,const unsigned int direction,ExceptionInfo *exception) |
| { |
| if (level == 1) |
| switch (direction) |
| { |
| case WestGravity: |
| { |
| (void) RiemersmaDither(image,image_view,cube_info,EastGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,SouthGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,WestGravity, |
| exception); |
| break; |
| } |
| case EastGravity: |
| { |
| (void) RiemersmaDither(image,image_view,cube_info,WestGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,NorthGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,EastGravity, |
| exception); |
| break; |
| } |
| case NorthGravity: |
| { |
| (void) RiemersmaDither(image,image_view,cube_info,SouthGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,EastGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,NorthGravity, |
| exception); |
| break; |
| } |
| case SouthGravity: |
| { |
| (void) RiemersmaDither(image,image_view,cube_info,NorthGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,WestGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,SouthGravity, |
| exception); |
| break; |
| } |
| default: |
| break; |
| } |
| else |
| switch (direction) |
| { |
| case WestGravity: |
| { |
| Riemersma(image,image_view,cube_info,level-1,NorthGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,EastGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,WestGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,SouthGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,WestGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,WestGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,SouthGravity, |
| exception); |
| break; |
| } |
| case EastGravity: |
| { |
| Riemersma(image,image_view,cube_info,level-1,SouthGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,WestGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,EastGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,NorthGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,EastGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,EastGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,NorthGravity, |
| exception); |
| break; |
| } |
| case NorthGravity: |
| { |
| Riemersma(image,image_view,cube_info,level-1,WestGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,SouthGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,NorthGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,EastGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,NorthGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,NorthGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,EastGravity, |
| exception); |
| break; |
| } |
| case SouthGravity: |
| { |
| Riemersma(image,image_view,cube_info,level-1,EastGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,NorthGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,SouthGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,WestGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,SouthGravity, |
| exception); |
| (void) RiemersmaDither(image,image_view,cube_info,SouthGravity, |
| exception); |
| Riemersma(image,image_view,cube_info,level-1,WestGravity, |
| exception); |
| break; |
| } |
| default: |
| break; |
| } |
| } |
| |
| static MagickBooleanType RiemersmaDither(Image *image,CacheView *image_view, |
| CubeInfo *cube_info,const unsigned int direction,ExceptionInfo *exception) |
| { |
| #define DitherImageTag "Dither/Image" |
| |
| MagickBooleanType |
| proceed; |
| |
| RealPixelInfo |
| color, |
| pixel; |
| |
| register CubeInfo |
| *p; |
| |
| size_t |
| index; |
| |
| p=cube_info; |
| if ((p->x >= 0) && (p->x < (ssize_t) image->columns) && |
| (p->y >= 0) && (p->y < (ssize_t) image->rows)) |
| { |
| register Quantum |
| *restrict q; |
| |
| register ssize_t |
| i; |
| |
| /* |
| Distribute error. |
| */ |
| q=GetCacheViewAuthenticPixels(image_view,p->x,p->y,1,1,exception); |
| if (q == (Quantum *) NULL) |
| return(MagickFalse); |
| AssociateAlphaPixel(image,cube_info,q,&pixel); |
| for (i=0; i < ErrorQueueLength; i++) |
| { |
| pixel.red+=p->weights[i]*p->error[i].red; |
| pixel.green+=p->weights[i]*p->error[i].green; |
| pixel.blue+=p->weights[i]*p->error[i].blue; |
| if (cube_info->associate_alpha != MagickFalse) |
| pixel.alpha+=p->weights[i]*p->error[i].alpha; |
| } |
| pixel.red=(double) ClampPixel(pixel.red); |
| pixel.green=(double) ClampPixel(pixel.green); |
| pixel.blue=(double) ClampPixel(pixel.blue); |
| if (cube_info->associate_alpha != MagickFalse) |
| pixel.alpha=(double) ClampPixel(pixel.alpha); |
| i=CacheOffset(cube_info,&pixel); |
| if (p->cache[i] < 0) |
| { |
| register NodeInfo |
| *node_info; |
| |
| register size_t |
| id; |
| |
| /* |
| Identify the deepest node containing the pixel's color. |
| */ |
| node_info=p->root; |
| for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--) |
| { |
| id=ColorToNodeId(cube_info,&pixel,index); |
| if (node_info->child[id] == (NodeInfo *) NULL) |
| break; |
| node_info=node_info->child[id]; |
| } |
| /* |
| Find closest color among siblings and their children. |
| */ |
| p->target=pixel; |
| p->distance=(double) (4.0*(QuantumRange+1.0)*((double) |
| QuantumRange+1.0)+1.0); |
| ClosestColor(image,p,node_info->parent); |
| p->cache[i]=(ssize_t) p->color_number; |
| } |
| /* |
| Assign pixel to closest colormap entry. |
| */ |
| index=(size_t) p->cache[i]; |
| if (image->storage_class == PseudoClass) |
| SetPixelIndex(image,(Quantum) index,q); |
| if (cube_info->quantize_info->measure_error == MagickFalse) |
| { |
| SetPixelRed(image,ClampToQuantum(image->colormap[index].red),q); |
| SetPixelGreen(image,ClampToQuantum(image->colormap[index].green),q); |
| SetPixelBlue(image,ClampToQuantum(image->colormap[index].blue),q); |
| if (cube_info->associate_alpha != MagickFalse) |
| SetPixelAlpha(image,ClampToQuantum(image->colormap[index].alpha),q); |
| } |
| if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) |
| return(MagickFalse); |
| /* |
| Propagate the error as the last entry of the error queue. |
| */ |
| (void) CopyMagickMemory(p->error,p->error+1,(ErrorQueueLength-1)* |
| sizeof(p->error[0])); |
| AssociateAlphaPixelInfo(cube_info,image->colormap+index,&color); |
| p->error[ErrorQueueLength-1].red=pixel.red-color.red; |
| p->error[ErrorQueueLength-1].green=pixel.green-color.green; |
| p->error[ErrorQueueLength-1].blue=pixel.blue-color.blue; |
| if (cube_info->associate_alpha != MagickFalse) |
| p->error[ErrorQueueLength-1].alpha=pixel.alpha-color.alpha; |
| proceed=SetImageProgress(image,DitherImageTag,p->offset,p->span); |
| if (proceed == MagickFalse) |
| return(MagickFalse); |
| p->offset++; |
| } |
| switch (direction) |
| { |
| case WestGravity: p->x--; break; |
| case EastGravity: p->x++; break; |
| case NorthGravity: p->y--; break; |
| case SouthGravity: p->y++; break; |
| } |
| return(MagickTrue); |
| } |
| |
| static inline ssize_t MagickMax(const ssize_t x,const ssize_t y) |
| { |
| if (x > y) |
| return(x); |
| return(y); |
| } |
| |
| static inline ssize_t MagickMin(const ssize_t x,const ssize_t y) |
| { |
| if (x < y) |
| return(x); |
| return(y); |
| } |
| |
| static MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info, |
| ExceptionInfo *exception) |
| { |
| CacheView |
| *image_view; |
| |
| MagickBooleanType |
| status; |
| |
| register ssize_t |
| i; |
| |
| size_t |
| depth; |
| |
| if (cube_info->quantize_info->dither_method != RiemersmaDitherMethod) |
| return(FloydSteinbergDither(image,cube_info,exception)); |
| /* |
| Distribute quantization error along a Hilbert curve. |
| */ |
| (void) ResetMagickMemory(cube_info->error,0,ErrorQueueLength* |
| sizeof(*cube_info->error)); |
| cube_info->x=0; |
| cube_info->y=0; |
| i=MagickMax((ssize_t) image->columns,(ssize_t) image->rows); |
| for (depth=1; i != 0; depth++) |
| i>>=1; |
| if ((ssize_t) (1L << depth) < MagickMax((ssize_t) image->columns,(ssize_t) image->rows)) |
| depth++; |
| cube_info->offset=0; |
| cube_info->span=(MagickSizeType) image->columns*image->rows; |
| image_view=AcquireAuthenticCacheView(image,exception); |
| if (depth > 1) |
| Riemersma(image,image_view,cube_info,depth-1,NorthGravity,exception); |
| status=RiemersmaDither(image,image_view,cube_info,ForgetGravity,exception); |
| image_view=DestroyCacheView(image_view); |
| return(status); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + G e t C u b e I n f o % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % GetCubeInfo() initialize the Cube data structure. |
| % |
| % The format of the GetCubeInfo method is: |
| % |
| % CubeInfo GetCubeInfo(const QuantizeInfo *quantize_info, |
| % const size_t depth,const size_t maximum_colors) |
| % |
| % A description of each parameter follows. |
| % |
| % o quantize_info: Specifies a pointer to an QuantizeInfo structure. |
| % |
| % o depth: Normally, this integer value is zero or one. A zero or |
| % one tells Quantize to choose a optimal tree depth of Log4(number_colors). |
| % A tree of this depth generally allows the best representation of the |
| % reference image with the least amount of memory and the fastest |
| % computational speed. In some cases, such as an image with low color |
| % dispersion (a few number of colors), a value other than |
| % Log4(number_colors) is required. To expand the color tree completely, |
| % use a value of 8. |
| % |
| % o maximum_colors: maximum colors. |
| % |
| */ |
| static CubeInfo *GetCubeInfo(const QuantizeInfo *quantize_info, |
| const size_t depth,const size_t maximum_colors) |
| { |
| CubeInfo |
| *cube_info; |
| |
| double |
| sum, |
| weight; |
| |
| register ssize_t |
| i; |
| |
| size_t |
| length; |
| |
| /* |
| Initialize tree to describe color cube_info. |
| */ |
| cube_info=(CubeInfo *) AcquireMagickMemory(sizeof(*cube_info)); |
| if (cube_info == (CubeInfo *) NULL) |
| return((CubeInfo *) NULL); |
| (void) ResetMagickMemory(cube_info,0,sizeof(*cube_info)); |
| cube_info->depth=depth; |
| if (cube_info->depth > MaxTreeDepth) |
| cube_info->depth=MaxTreeDepth; |
| if (cube_info->depth < 2) |
| cube_info->depth=2; |
| cube_info->maximum_colors=maximum_colors; |
| /* |
| Initialize root node. |
| */ |
| cube_info->root=GetNodeInfo(cube_info,0,0,(NodeInfo *) NULL); |
| if (cube_info->root == (NodeInfo *) NULL) |
| return((CubeInfo *) NULL); |
| cube_info->root->parent=cube_info->root; |
| cube_info->quantize_info=CloneQuantizeInfo(quantize_info); |
| if (cube_info->quantize_info->dither_method == NoDitherMethod) |
| return(cube_info); |
| /* |
| Initialize dither resources. |
| */ |
| length=(size_t) (1UL << (4*(8-CacheShift))); |
| cube_info->memory_info=AcquireVirtualMemory(length,sizeof(*cube_info->cache)); |
| if (cube_info->memory_info == (MemoryInfo *) NULL) |
| return((CubeInfo *) NULL); |
| cube_info->cache=(ssize_t *) GetVirtualMemoryBlob(cube_info->memory_info); |
| /* |
| Initialize color cache. |
| */ |
| for (i=0; i < (ssize_t) length; i++) |
| cube_info->cache[i]=(-1); |
| /* |
| Distribute weights along a curve of exponential decay. |
| */ |
| weight=1.0; |
| for (i=0; i < ErrorQueueLength; i++) |
| { |
| cube_info->weights[ErrorQueueLength-i-1]=PerceptibleReciprocal(weight); |
| weight*=exp(log(((double) QuantumRange+1.0))/(ErrorQueueLength-1.0)); |
| } |
| /* |
| Normalize the weighting factors. |
| */ |
| weight=0.0; |
| for (i=0; i < ErrorQueueLength; i++) |
| weight+=cube_info->weights[i]; |
| sum=0.0; |
| for (i=0; i < ErrorQueueLength; i++) |
| { |
| cube_info->weights[i]/=weight; |
| sum+=cube_info->weights[i]; |
| } |
| cube_info->weights[0]+=1.0-sum; |
| return(cube_info); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + G e t N o d e I n f o % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % GetNodeInfo() allocates memory for a new node in the color cube tree and |
| % presets all fields to zero. |
| % |
| % The format of the GetNodeInfo method is: |
| % |
| % NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id, |
| % const size_t level,NodeInfo *parent) |
| % |
| % A description of each parameter follows. |
| % |
| % o node: The GetNodeInfo method returns a pointer to a queue of nodes. |
| % |
| % o id: Specifies the child number of the node. |
| % |
| % o level: Specifies the level in the storage_class the node resides. |
| % |
| */ |
| static NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id, |
| const size_t level,NodeInfo *parent) |
| { |
| NodeInfo |
| *node_info; |
| |
| if (cube_info->free_nodes == 0) |
| { |
| Nodes |
| *nodes; |
| |
| /* |
| Allocate a new queue of nodes. |
| */ |
| nodes=(Nodes *) AcquireMagickMemory(sizeof(*nodes)); |
| if (nodes == (Nodes *) NULL) |
| return((NodeInfo *) NULL); |
| nodes->nodes=(NodeInfo *) AcquireQuantumMemory(NodesInAList, |
| sizeof(*nodes->nodes)); |
| if (nodes->nodes == (NodeInfo *) NULL) |
| return((NodeInfo *) NULL); |
| nodes->next=cube_info->node_queue; |
| cube_info->node_queue=nodes; |
| cube_info->next_node=nodes->nodes; |
| cube_info->free_nodes=NodesInAList; |
| } |
| cube_info->nodes++; |
| cube_info->free_nodes--; |
| node_info=cube_info->next_node++; |
| (void) ResetMagickMemory(node_info,0,sizeof(*node_info)); |
| node_info->parent=parent; |
| node_info->id=id; |
| node_info->level=level; |
| return(node_info); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % G e t I m a g e Q u a n t i z e E r r o r % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % GetImageQuantizeError() measures the difference between the original |
| % and quantized images. This difference is the total quantization error. |
| % The error is computed by summing over all pixels in an image the distance |
| % squared in RGB space between each reference pixel value and its quantized |
| % value. These values are computed: |
| % |
| % o mean_error_per_pixel: This value is the mean error for any single |
| % pixel in the image. |
| % |
| % o normalized_mean_square_error: This value is the normalized mean |
| % quantization error for any single pixel in the image. This distance |
| % measure is normalized to a range between 0 and 1. It is independent |
| % of the range of red, green, and blue values in the image. |
| % |
| % o normalized_maximum_square_error: Thsi value is the normalized |
| % maximum quantization error for any single pixel in the image. This |
| % distance measure is normalized to a range between 0 and 1. It is |
| % independent of the range of red, green, and blue values in your image. |
| % |
| % The format of the GetImageQuantizeError method is: |
| % |
| % MagickBooleanType GetImageQuantizeError(Image *image, |
| % ExceptionInfo *exception) |
| % |
| % A description of each parameter follows. |
| % |
| % o image: the image. |
| % |
| % o exception: return any errors or warnings in this structure. |
| % |
| */ |
| MagickExport MagickBooleanType GetImageQuantizeError(Image *image, |
| ExceptionInfo *exception) |
| { |
| CacheView |
| *image_view; |
| |
| double |
| alpha, |
| area, |
| beta, |
| distance, |
| maximum_error, |
| mean_error, |
| mean_error_per_pixel; |
| |
| size_t |
| index; |
| |
| ssize_t |
| y; |
| |
| assert(image != (Image *) NULL); |
| assert(image->signature == MagickSignature); |
| if (image->debug != MagickFalse) |
| (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); |
| image->total_colors=GetNumberColors(image,(FILE *) NULL,exception); |
| (void) ResetMagickMemory(&image->error,0,sizeof(image->error)); |
| if (image->storage_class == DirectClass) |
| return(MagickTrue); |
| alpha=1.0; |
| beta=1.0; |
| area=3.0*image->columns*image->rows; |
| maximum_error=0.0; |
| mean_error_per_pixel=0.0; |
| mean_error=0.0; |
| image_view=AcquireVirtualCacheView(image,exception); |
| for (y=0; y < (ssize_t) image->rows; y++) |
| { |
| register const Quantum |
| *restrict p; |
| |
| register ssize_t |
| x; |
| |
| p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception); |
| if (p == (const Quantum *) NULL) |
| break; |
| for (x=0; x < (ssize_t) image->columns; x++) |
| { |
| index=1UL*GetPixelIndex(image,p); |
| if (image->alpha_trait == BlendPixelTrait) |
| { |
| alpha=(double) (QuantumScale*GetPixelAlpha(image,p)); |
| beta=(double) (QuantumScale*image->colormap[index].alpha); |
| } |
| distance=fabs(alpha*GetPixelRed(image,p)-beta* |
| image->colormap[index].red); |
| mean_error_per_pixel+=distance; |
| mean_error+=distance*distance; |
| if (distance > maximum_error) |
| maximum_error=distance; |
| distance=fabs(alpha*GetPixelGreen(image,p)-beta* |
| image->colormap[index].green); |
| mean_error_per_pixel+=distance; |
| mean_error+=distance*distance; |
| if (distance > maximum_error) |
| maximum_error=distance; |
| distance=fabs(alpha*GetPixelBlue(image,p)-beta* |
| image->colormap[index].blue); |
| mean_error_per_pixel+=distance; |
| mean_error+=distance*distance; |
| if (distance > maximum_error) |
| maximum_error=distance; |
| p+=GetPixelChannels(image); |
| } |
| } |
| image_view=DestroyCacheView(image_view); |
| image->error.mean_error_per_pixel=(double) mean_error_per_pixel/area; |
| image->error.normalized_mean_error=(double) QuantumScale*QuantumScale* |
| mean_error/area; |
| image->error.normalized_maximum_error=(double) QuantumScale*maximum_error; |
| return(MagickTrue); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % G e t Q u a n t i z e I n f o % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % GetQuantizeInfo() initializes the QuantizeInfo structure. |
| % |
| % The format of the GetQuantizeInfo method is: |
| % |
| % GetQuantizeInfo(QuantizeInfo *quantize_info) |
| % |
| % A description of each parameter follows: |
| % |
| % o quantize_info: Specifies a pointer to a QuantizeInfo structure. |
| % |
| */ |
| MagickExport void GetQuantizeInfo(QuantizeInfo *quantize_info) |
| { |
| (void) LogMagickEvent(TraceEvent,GetMagickModule(),"..."); |
| assert(quantize_info != (QuantizeInfo *) NULL); |
| (void) ResetMagickMemory(quantize_info,0,sizeof(*quantize_info)); |
| quantize_info->number_colors=256; |
| quantize_info->dither_method=RiemersmaDitherMethod; |
| quantize_info->colorspace=UndefinedColorspace; |
| quantize_info->measure_error=MagickFalse; |
| quantize_info->signature=MagickSignature; |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % P o s t e r i z e I m a g e % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % PosterizeImage() reduces the image to a limited number of colors for a |
| % "poster" effect. |
| % |
| % The format of the PosterizeImage method is: |
| % |
| % MagickBooleanType PosterizeImage(Image *image,const size_t levels, |
| % const DitherMethod dither_method,ExceptionInfo *exception) |
| % |
| % A description of each parameter follows: |
| % |
| % o image: Specifies a pointer to an Image structure. |
| % |
| % o levels: Number of color levels allowed in each channel. Very low values |
| % (2, 3, or 4) have the most visible effect. |
| % |
| % o dither_method: choose from UndefinedDitherMethod, NoDitherMethod, |
| % RiemersmaDitherMethod, FloydSteinbergDitherMethod. |
| % |
| % o exception: return any errors or warnings in this structure. |
| % |
| */ |
| |
| static inline double MagickRound(double x) |
| { |
| /* |
| Round the fraction to nearest integer. |
| */ |
| if ((x-floor(x)) < (ceil(x)-x)) |
| return(floor(x)); |
| return(ceil(x)); |
| } |
| |
| MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels, |
| const DitherMethod dither_method,ExceptionInfo *exception) |
| { |
| #define PosterizeImageTag "Posterize/Image" |
| #define PosterizePixel(pixel) (Quantum) (QuantumRange*(MagickRound( \ |
| QuantumScale*pixel*(levels-1)))/MagickMax((ssize_t) levels-1,1)) |
| |
| CacheView |
| *image_view; |
| |
| MagickBooleanType |
| status; |
| |
| MagickOffsetType |
| progress; |
| |
| QuantizeInfo |
| *quantize_info; |
| |
| register ssize_t |
| i; |
| |
| ssize_t |
| y; |
| |
| assert(image != (Image *) NULL); |
| assert(image->signature == MagickSignature); |
| if (image->debug != MagickFalse) |
| (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); |
| if (image->storage_class == PseudoClass) |
| #if defined(MAGICKCORE_OPENMP_SUPPORT) |
| #pragma omp parallel for schedule(static,4) shared(progress,status) \ |
| magick_threads(image,image,1,1) |
| #endif |
| for (i=0; i < (ssize_t) image->colors; i++) |
| { |
| /* |
| Posterize colormap. |
| */ |
| if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0) |
| image->colormap[i].red=(double) |
| PosterizePixel(image->colormap[i].red); |
| if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0) |
| image->colormap[i].green=(double) |
| PosterizePixel(image->colormap[i].green); |
| if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0) |
| image->colormap[i].blue=(double) |
| PosterizePixel(image->colormap[i].blue); |
| if ((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0) |
| image->colormap[i].alpha=(double) |
| PosterizePixel(image->colormap[i].alpha); |
| } |
| /* |
| Posterize image. |
| */ |
| status=MagickTrue; |
| progress=0; |
| image_view=AcquireAuthenticCacheView(image,exception); |
| #if defined(MAGICKCORE_OPENMP_SUPPORT) |
| #pragma omp parallel for schedule(static,4) shared(progress,status) \ |
| magick_threads(image,image,image->rows,1) |
| #endif |
| for (y=0; y < (ssize_t) image->rows; y++) |
| { |
| register Quantum |
| *restrict q; |
| |
| register ssize_t |
| x; |
| |
| if (status == MagickFalse) |
| continue; |
| q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception); |
| if (q == (Quantum *) NULL) |
| { |
| status=MagickFalse; |
| continue; |
| } |
| for (x=0; x < (ssize_t) image->columns; x++) |
| { |
| if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0) |
| SetPixelRed(image,PosterizePixel(GetPixelRed(image,q)),q); |
| if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0) |
| SetPixelGreen(image,PosterizePixel(GetPixelGreen(image,q)),q); |
| if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0) |
| SetPixelBlue(image,PosterizePixel(GetPixelBlue(image,q)),q); |
| if (((GetPixelBlackTraits(image) & UpdatePixelTrait) != 0) && |
| (image->colorspace == CMYKColorspace)) |
| SetPixelBlack(image,PosterizePixel(GetPixelBlack(image,q)),q); |
| if (((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0) && |
| (image->alpha_trait == BlendPixelTrait)) |
| SetPixelAlpha(image,PosterizePixel(GetPixelAlpha(image,q)),q); |
| q+=GetPixelChannels(image); |
| } |
| if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) |
| status=MagickFalse; |
| if (image->progress_monitor != (MagickProgressMonitor) NULL) |
| { |
| MagickBooleanType |
| proceed; |
| |
| #if defined(MAGICKCORE_OPENMP_SUPPORT) |
| #pragma omp critical (MagickCore_PosterizeImage) |
| #endif |
| proceed=SetImageProgress(image,PosterizeImageTag,progress++, |
| image->rows); |
| if (proceed == MagickFalse) |
| status=MagickFalse; |
| } |
| } |
| image_view=DestroyCacheView(image_view); |
| quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL); |
| quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels* |
| levels,MaxColormapSize+1); |
| quantize_info->dither_method=dither_method; |
| quantize_info->tree_depth=MaxTreeDepth; |
| status=QuantizeImage(quantize_info,image,exception); |
| quantize_info=DestroyQuantizeInfo(quantize_info); |
| return(status); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + P r u n e C h i l d % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % PruneChild() deletes the given node and merges its statistics into its |
| % parent. |
| % |
| % The format of the PruneSubtree method is: |
| % |
| % PruneChild(const Image *image,CubeInfo *cube_info, |
| % const NodeInfo *node_info) |
| % |
| % A description of each parameter follows. |
| % |
| % o image: the image. |
| % |
| % o cube_info: A pointer to the Cube structure. |
| % |
| % o node_info: pointer to node in color cube tree that is to be pruned. |
| % |
| */ |
| static void PruneChild(const Image *image,CubeInfo *cube_info, |
| const NodeInfo *node_info) |
| { |
| NodeInfo |
| *parent; |
| |
| register ssize_t |
| i; |
| |
| size_t |
| number_children; |
| |
| /* |
| Traverse any children. |
| */ |
| number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; |
| for (i=0; i < (ssize_t) number_children; i++) |
| if (node_info->child[i] != (NodeInfo *) NULL) |
| PruneChild(image,cube_info,node_info->child[i]); |
| /* |
| Merge color statistics into parent. |
| */ |
| parent=node_info->parent; |
| parent->number_unique+=node_info->number_unique; |
| parent->total_color.red+=node_info->total_color.red; |
| parent->total_color.green+=node_info->total_color.green; |
| parent->total_color.blue+=node_info->total_color.blue; |
| parent->total_color.alpha+=node_info->total_color.alpha; |
| parent->child[node_info->id]=(NodeInfo *) NULL; |
| cube_info->nodes--; |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + P r u n e L e v e l % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % PruneLevel() deletes all nodes at the bottom level of the color tree merging |
| % their color statistics into their parent node. |
| % |
| % The format of the PruneLevel method is: |
| % |
| % PruneLevel(const Image *image,CubeInfo *cube_info, |
| % const NodeInfo *node_info) |
| % |
| % A description of each parameter follows. |
| % |
| % o image: the image. |
| % |
| % o cube_info: A pointer to the Cube structure. |
| % |
| % o node_info: pointer to node in color cube tree that is to be pruned. |
| % |
| */ |
| static void PruneLevel(const Image *image,CubeInfo *cube_info, |
| const NodeInfo *node_info) |
| { |
| register ssize_t |
| i; |
| |
| size_t |
| number_children; |
| |
| /* |
| Traverse any children. |
| */ |
| number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; |
| for (i=0; i < (ssize_t) number_children; i++) |
| if (node_info->child[i] != (NodeInfo *) NULL) |
| PruneLevel(image,cube_info,node_info->child[i]); |
| if (node_info->level == cube_info->depth) |
| PruneChild(image,cube_info,node_info); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + P r u n e T o C u b e D e p t h % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % PruneToCubeDepth() deletes any nodes at a depth greater than |
| % cube_info->depth while merging their color statistics into their parent |
| % node. |
| % |
| % The format of the PruneToCubeDepth method is: |
| % |
| % PruneToCubeDepth(const Image *image,CubeInfo *cube_info, |
| % const NodeInfo *node_info) |
| % |
| % A description of each parameter follows. |
| % |
| % o cube_info: A pointer to the Cube structure. |
| % |
| % o node_info: pointer to node in color cube tree that is to be pruned. |
| % |
| */ |
| static void PruneToCubeDepth(const Image *image,CubeInfo *cube_info, |
| const NodeInfo *node_info) |
| { |
| register ssize_t |
| i; |
| |
| size_t |
| number_children; |
| |
| /* |
| Traverse any children. |
| */ |
| number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; |
| for (i=0; i < (ssize_t) number_children; i++) |
| if (node_info->child[i] != (NodeInfo *) NULL) |
| PruneToCubeDepth(image,cube_info,node_info->child[i]); |
| if (node_info->level > cube_info->depth) |
| PruneChild(image,cube_info,node_info); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % Q u a n t i z e I m a g e % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % QuantizeImage() analyzes the colors within a reference image and chooses a |
| % fixed number of colors to represent the image. The goal of the algorithm |
| % is to minimize the color difference between the input and output image while |
| % minimizing the processing time. |
| % |
| % The format of the QuantizeImage method is: |
| % |
| % MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info, |
| % Image *image,ExceptionInfo *exception) |
| % |
| % A description of each parameter follows: |
| % |
| % o quantize_info: Specifies a pointer to an QuantizeInfo structure. |
| % |
| % o image: the image. |
| % |
| % o exception: return any errors or warnings in this structure. |
| % |
| */ |
| |
| static MagickBooleanType DirectToColormapImage(Image *image, |
| ExceptionInfo *exception) |
| { |
| CacheView |
| *image_view; |
| |
| MagickBooleanType |
| status; |
| |
| register ssize_t |
| i; |
| |
| size_t |
| number_colors; |
| |
| ssize_t |
| y; |
| |
| status=MagickTrue; |
| number_colors=(size_t) (image->columns*image->rows); |
| if (AcquireImageColormap(image,number_colors,exception) == MagickFalse) |
| ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", |
| image->filename); |
| if (image->colors != number_colors) |
| return(MagickFalse); |
| i=0; |
| image_view=AcquireAuthenticCacheView(image,exception); |
| for (y=0; y < (ssize_t) image->rows; y++) |
| { |
| MagickBooleanType |
| proceed; |
| |
| register Quantum |
| *restrict q; |
| |
| register ssize_t |
| x; |
| |
| q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception); |
| if (q == (Quantum *) NULL) |
| break; |
| for (x=0; x < (ssize_t) image->columns; x++) |
| { |
| image->colormap[i].red=(double) GetPixelRed(image,q); |
| image->colormap[i].green=(double) GetPixelGreen(image,q); |
| image->colormap[i].blue=(double) GetPixelBlue(image,q); |
| image->colormap[i].alpha=(double) GetPixelAlpha(image,q); |
| SetPixelIndex(image,(Quantum) i,q); |
| i++; |
| q+=GetPixelChannels(image); |
| } |
| if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) |
| break; |
| proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y, |
| image->rows); |
| if (proceed == MagickFalse) |
| status=MagickFalse; |
| } |
| image_view=DestroyCacheView(image_view); |
| return(status); |
| } |
| |
| MagickExport MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info, |
| Image *image,ExceptionInfo *exception) |
| { |
| CubeInfo |
| *cube_info; |
| |
| MagickBooleanType |
| status; |
| |
| size_t |
| depth, |
| maximum_colors; |
| |
| assert(quantize_info != (const QuantizeInfo *) NULL); |
| assert(quantize_info->signature == MagickSignature); |
| assert(image != (Image *) NULL); |
| assert(image->signature == MagickSignature); |
| if (image->debug != MagickFalse) |
| (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); |
| maximum_colors=quantize_info->number_colors; |
| if (maximum_colors == 0) |
| maximum_colors=MaxColormapSize; |
| if (maximum_colors > MaxColormapSize) |
| maximum_colors=MaxColormapSize; |
| if (image->alpha_trait != BlendPixelTrait) |
| { |
| if ((image->columns*image->rows) <= maximum_colors) |
| (void) DirectToColormapImage(image,exception); |
| if (IsImageGray(image,exception) != MagickFalse) |
| (void) SetGrayscaleImage(image,exception); |
| } |
| if ((image->storage_class == PseudoClass) && |
| (image->colors <= maximum_colors)) |
| return(MagickTrue); |
| depth=quantize_info->tree_depth; |
| if (depth == 0) |
| { |
| size_t |
| colors; |
| |
| /* |
| Depth of color tree is: Log4(colormap size)+2. |
| */ |
| colors=maximum_colors; |
| for (depth=1; colors != 0; depth++) |
| colors>>=2; |
| if ((quantize_info->dither_method != NoDitherMethod) && (depth > 2)) |
| depth--; |
| if ((image->alpha_trait == BlendPixelTrait) && (depth > 5)) |
| depth--; |
| } |
| /* |
| Initialize color cube. |
| */ |
| cube_info=GetCubeInfo(quantize_info,depth,maximum_colors); |
| if (cube_info == (CubeInfo *) NULL) |
| ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", |
| image->filename); |
| status=ClassifyImageColors(cube_info,image,exception); |
| if (status != MagickFalse) |
| { |
| /* |
| Reduce the number of colors in the image. |
| */ |
| ReduceImageColors(image,cube_info); |
| status=AssignImageColors(image,cube_info,exception); |
| } |
| DestroyCubeInfo(cube_info); |
| return(status); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % Q u a n t i z e I m a g e s % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % QuantizeImages() analyzes the colors within a set of reference images and |
| % chooses a fixed number of colors to represent the set. The goal of the |
| % algorithm is to minimize the color difference between the input and output |
| % images while minimizing the processing time. |
| % |
| % The format of the QuantizeImages method is: |
| % |
| % MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info, |
| % Image *images,ExceptionInfo *exception) |
| % |
| % A description of each parameter follows: |
| % |
| % o quantize_info: Specifies a pointer to an QuantizeInfo structure. |
| % |
| % o images: Specifies a pointer to a list of Image structures. |
| % |
| % o exception: return any errors or warnings in this structure. |
| % |
| */ |
| MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info, |
| Image *images,ExceptionInfo *exception) |
| { |
| CubeInfo |
| *cube_info; |
| |
| Image |
| *image; |
| |
| MagickBooleanType |
| proceed, |
| status; |
| |
| MagickProgressMonitor |
| progress_monitor; |
| |
| register ssize_t |
| i; |
| |
| size_t |
| depth, |
| maximum_colors, |
| number_images; |
| |
| assert(quantize_info != (const QuantizeInfo *) NULL); |
| assert(quantize_info->signature == MagickSignature); |
| assert(images != (Image *) NULL); |
| assert(images->signature == MagickSignature); |
| if (images->debug != MagickFalse) |
| (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename); |
| if (GetNextImageInList(images) == (Image *) NULL) |
| { |
| /* |
| Handle a single image with QuantizeImage. |
| */ |
| status=QuantizeImage(quantize_info,images,exception); |
| return(status); |
| } |
| status=MagickFalse; |
| maximum_colors=quantize_info->number_colors; |
| if (maximum_colors == 0) |
| maximum_colors=MaxColormapSize; |
| if (maximum_colors > MaxColormapSize) |
| maximum_colors=MaxColormapSize; |
| depth=quantize_info->tree_depth; |
| if (depth == 0) |
| { |
| size_t |
| colors; |
| |
| /* |
| Depth of color tree is: Log4(colormap size)+2. |
| */ |
| colors=maximum_colors; |
| for (depth=1; colors != 0; depth++) |
| colors>>=2; |
| if (quantize_info->dither_method != NoDitherMethod) |
| depth--; |
| } |
| /* |
| Initialize color cube. |
| */ |
| cube_info=GetCubeInfo(quantize_info,depth,maximum_colors); |
| if (cube_info == (CubeInfo *) NULL) |
| { |
| (void) ThrowMagickException(exception,GetMagickModule(), |
| ResourceLimitError,"MemoryAllocationFailed","`%s'",images->filename); |
| return(MagickFalse); |
| } |
| number_images=GetImageListLength(images); |
| image=images; |
| for (i=0; image != (Image *) NULL; i++) |
| { |
| progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL, |
| image->client_data); |
| status=ClassifyImageColors(cube_info,image,exception); |
| if (status == MagickFalse) |
| break; |
| (void) SetImageProgressMonitor(image,progress_monitor,image->client_data); |
| proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i, |
| number_images); |
| if (proceed == MagickFalse) |
| break; |
| image=GetNextImageInList(image); |
| } |
| if (status != MagickFalse) |
| { |
| /* |
| Reduce the number of colors in an image sequence. |
| */ |
| ReduceImageColors(images,cube_info); |
| image=images; |
| for (i=0; image != (Image *) NULL; i++) |
| { |
| progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) |
| NULL,image->client_data); |
| status=AssignImageColors(image,cube_info,exception); |
| if (status == MagickFalse) |
| break; |
| (void) SetImageProgressMonitor(image,progress_monitor, |
| image->client_data); |
| proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i, |
| number_images); |
| if (proceed == MagickFalse) |
| break; |
| image=GetNextImageInList(image); |
| } |
| } |
| DestroyCubeInfo(cube_info); |
| return(status); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + R e d u c e % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % Reduce() traverses the color cube tree and prunes any node whose |
| % quantization error falls below a particular threshold. |
| % |
| % The format of the Reduce method is: |
| % |
| % Reduce(const Image *image,CubeInfo *cube_info,const NodeInfo *node_info) |
| % |
| % A description of each parameter follows. |
| % |
| % o image: the image. |
| % |
| % o cube_info: A pointer to the Cube structure. |
| % |
| % o node_info: pointer to node in color cube tree that is to be pruned. |
| % |
| */ |
| static void Reduce(const Image *image,CubeInfo *cube_info, |
| const NodeInfo *node_info) |
| { |
| register ssize_t |
| i; |
| |
| size_t |
| number_children; |
| |
| /* |
| Traverse any children. |
| */ |
| number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; |
| for (i=0; i < (ssize_t) number_children; i++) |
| if (node_info->child[i] != (NodeInfo *) NULL) |
| Reduce(image,cube_info,node_info->child[i]); |
| if (node_info->quantize_error <= cube_info->pruning_threshold) |
| PruneChild(image,cube_info,node_info); |
| else |
| { |
| /* |
| Find minimum pruning threshold. |
| */ |
| if (node_info->number_unique > 0) |
| cube_info->colors++; |
| if (node_info->quantize_error < cube_info->next_threshold) |
| cube_info->next_threshold=node_info->quantize_error; |
| } |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| + R e d u c e I m a g e C o l o r s % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % ReduceImageColors() repeatedly prunes the tree until the number of nodes |
| % with n2 > 0 is less than or equal to the maximum number of colors allowed |
| % in the output image. On any given iteration over the tree, it selects |
| % those nodes whose E value is minimal for pruning and merges their |
| % color statistics upward. It uses a pruning threshold, Ep, to govern |
| % node selection as follows: |
| % |
| % Ep = 0 |
| % while number of nodes with (n2 > 0) > required maximum number of colors |
| % prune all nodes such that E <= Ep |
| % Set Ep to minimum E in remaining nodes |
| % |
| % This has the effect of minimizing any quantization error when merging |
| % two nodes together. |
| % |
| % When a node to be pruned has offspring, the pruning procedure invokes |
| % itself recursively in order to prune the tree from the leaves upward. |
| % n2, Sr, Sg, and Sb in a node being pruned are always added to the |
| % corresponding data in that node's parent. This retains the pruned |
| % node's color characteristics for later averaging. |
| % |
| % For each node, n2 pixels exist for which that node represents the |
| % smallest volume in RGB space containing those pixel's colors. When n2 |
| % > 0 the node will uniquely define a color in the output image. At the |
| % beginning of reduction, n2 = 0 for all nodes except a the leaves of |
| % the tree which represent colors present in the input image. |
| % |
| % The other pixel count, n1, indicates the total number of colors |
| % within the cubic volume which the node represents. This includes n1 - |
| % n2 pixels whose colors should be defined by nodes at a lower level in |
| % the tree. |
| % |
| % The format of the ReduceImageColors method is: |
| % |
| % ReduceImageColors(const Image *image,CubeInfo *cube_info) |
| % |
| % A description of each parameter follows. |
| % |
| % o image: the image. |
| % |
| % o cube_info: A pointer to the Cube structure. |
| % |
| */ |
| static void ReduceImageColors(const Image *image,CubeInfo *cube_info) |
| { |
| #define ReduceImageTag "Reduce/Image" |
| |
| MagickBooleanType |
| proceed; |
| |
| MagickOffsetType |
| offset; |
| |
| size_t |
| span; |
| |
| cube_info->next_threshold=0.0; |
| for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; ) |
| { |
| cube_info->pruning_threshold=cube_info->next_threshold; |
| cube_info->next_threshold=cube_info->root->quantize_error-1; |
| cube_info->colors=0; |
| Reduce(image,cube_info,cube_info->root); |
| offset=(MagickOffsetType) span-cube_info->colors; |
| proceed=SetImageProgress(image,ReduceImageTag,offset,span- |
| cube_info->maximum_colors+1); |
| if (proceed == MagickFalse) |
| break; |
| } |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % R e m a p I m a g e % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % RemapImage() replaces the colors of an image with a dither of the colors |
| % provided. |
| % |
| % The format of the RemapImage method is: |
| % |
| % MagickBooleanType RemapImage(const QuantizeInfo *quantize_info, |
| % Image *image,const Image *remap_image,ExceptionInfo *exception) |
| % |
| % A description of each parameter follows: |
| % |
| % o quantize_info: Specifies a pointer to an QuantizeInfo structure. |
| % |
| % o image: the image. |
| % |
| % o remap_image: the reference image. |
| % |
| % o exception: return any errors or warnings in this structure. |
| % |
| */ |
| MagickExport MagickBooleanType RemapImage(const QuantizeInfo *quantize_info, |
| Image *image,const Image *remap_image,ExceptionInfo *exception) |
| { |
| CubeInfo |
| *cube_info; |
| |
| MagickBooleanType |
| status; |
| |
| /* |
| Initialize color cube. |
| */ |
| assert(image != (Image *) NULL); |
| assert(image->signature == MagickSignature); |
| if (image->debug != MagickFalse) |
| (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); |
| assert(remap_image != (Image *) NULL); |
| assert(remap_image->signature == MagickSignature); |
| cube_info=GetCubeInfo(quantize_info,MaxTreeDepth, |
| quantize_info->number_colors); |
| if (cube_info == (CubeInfo *) NULL) |
| ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", |
| image->filename); |
| status=ClassifyImageColors(cube_info,remap_image,exception); |
| if (status != MagickFalse) |
| { |
| /* |
| Classify image colors from the reference image. |
| */ |
| cube_info->quantize_info->number_colors=cube_info->colors; |
| status=AssignImageColors(image,cube_info,exception); |
| } |
| DestroyCubeInfo(cube_info); |
| return(status); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % R e m a p I m a g e s % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % RemapImages() replaces the colors of a sequence of images with the |
| % closest color from a reference image. |
| % |
| % The format of the RemapImage method is: |
| % |
| % MagickBooleanType RemapImages(const QuantizeInfo *quantize_info, |
| % Image *images,Image *remap_image,ExceptionInfo *exception) |
| % |
| % A description of each parameter follows: |
| % |
| % o quantize_info: Specifies a pointer to an QuantizeInfo structure. |
| % |
| % o images: the image sequence. |
| % |
| % o remap_image: the reference image. |
| % |
| % o exception: return any errors or warnings in this structure. |
| % |
| */ |
| MagickExport MagickBooleanType RemapImages(const QuantizeInfo *quantize_info, |
| Image *images,const Image *remap_image,ExceptionInfo *exception) |
| { |
| CubeInfo |
| *cube_info; |
| |
| Image |
| *image; |
| |
| MagickBooleanType |
| status; |
| |
| assert(images != (Image *) NULL); |
| assert(images->signature == MagickSignature); |
| if (images->debug != MagickFalse) |
| (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename); |
| image=images; |
| if (remap_image == (Image *) NULL) |
| { |
| /* |
| Create a global colormap for an image sequence. |
| */ |
| status=QuantizeImages(quantize_info,images,exception); |
| return(status); |
| } |
| /* |
| Classify image colors from the reference image. |
| */ |
| cube_info=GetCubeInfo(quantize_info,MaxTreeDepth, |
| quantize_info->number_colors); |
| if (cube_info == (CubeInfo *) NULL) |
| ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", |
| image->filename); |
| status=ClassifyImageColors(cube_info,remap_image,exception); |
| if (status != MagickFalse) |
| { |
| /* |
| Classify image colors from the reference image. |
| */ |
| cube_info->quantize_info->number_colors=cube_info->colors; |
| image=images; |
| for ( ; image != (Image *) NULL; image=GetNextImageInList(image)) |
| { |
| status=AssignImageColors(image,cube_info,exception); |
| if (status == MagickFalse) |
| break; |
| } |
| } |
| DestroyCubeInfo(cube_info); |
| return(status); |
| } |
| |
| /* |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % % |
| % % |
| % % |
| % S e t G r a y s c a l e I m a g e % |
| % % |
| % % |
| % % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % |
| % SetGrayscaleImage() converts an image to a PseudoClass grayscale image. |
| % |
| % The format of the SetGrayscaleImage method is: |
| % |
| % MagickBooleanType SetGrayscaleImage(Image *image,ExceptionInfo *exeption) |
| % |
| % A description of each parameter follows: |
| % |
| % o image: The image. |
| % |
| % o exception: return any errors or warnings in this structure. |
| % |
| */ |
| |
| #if defined(__cplusplus) || defined(c_plusplus) |
| extern "C" { |
| #endif |
| |
| static int IntensityCompare(const void *x,const void *y) |
| { |
| PixelInfo |
| *color_1, |
| *color_2; |
| |
| ssize_t |
| intensity; |
| |
| color_1=(PixelInfo *) x; |
| color_2=(PixelInfo *) y; |
| intensity=(ssize_t) (GetPixelInfoIntensity(color_1)-(ssize_t) |
| GetPixelInfoIntensity(color_2)); |
| return((int) intensity); |
| } |
| |
| #if defined(__cplusplus) || defined(c_plusplus) |
| } |
| #endif |
| |
| static MagickBooleanType SetGrayscaleImage(Image *image, |
| ExceptionInfo *exception) |
| { |
| CacheView |
| *image_view; |
| |
| MagickBooleanType |
| status; |
| |
| PixelInfo |
| *colormap; |
| |
| register ssize_t |
| i; |
| |
| ssize_t |
| *colormap_index, |
| j, |
| y; |
| |
| assert(image != (Image *) NULL); |
| assert(image->signature == MagickSignature); |
| if (image->type != GrayscaleType) |
| (void) TransformImageColorspace(image,GRAYColorspace,exception); |
| colormap_index=(ssize_t *) AcquireQuantumMemory(MaxMap+1, |
| sizeof(*colormap_index)); |
| if (colormap_index == (ssize_t *) NULL) |
| ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", |
| image->filename); |
| if (image->storage_class != PseudoClass) |
| { |
| for (i=0; i <= (ssize_t) MaxMap; i++) |
| colormap_index[i]=(-1); |
| if (AcquireImageColormap(image,MaxMap+1,exception) == MagickFalse) |
| ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", |
| image->filename); |
| image->colors=0; |
| status=MagickTrue; |
| image_view=AcquireAuthenticCacheView(image,exception); |
| #if defined(MAGICKCORE_OPENMP_SUPPORT) |
| #pragma omp parallel for schedule(static,4) shared(status) \ |
| magick_threads(image,image,image->rows,1) |
| #endif |
| for (y=0; y < (ssize_t) image->rows; y++) |
| { |
| register Quantum |
| *restrict q; |
| |
| register ssize_t |
| x; |
| |
| if (status == MagickFalse) |
| continue; |
| q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1, |
| exception); |
| if (q == (Quantum *) NULL) |
| { |
| status=MagickFalse; |
| continue; |
| } |
| for (x=0; x < (ssize_t) image->columns; x++) |
| { |
| register size_t |
| intensity; |
| |
| intensity=ScaleQuantumToMap(GetPixelRed(image,q)); |
| if (colormap_index[intensity] < 0) |
| { |
| #if defined(MAGICKCORE_OPENMP_SUPPORT) |
| #pragma omp critical (MagickCore_SetGrayscaleImage) |
| #endif |
| if (colormap_index[intensity] < 0) |
| { |
| colormap_index[intensity]=(ssize_t) image->colors; |
| image->colormap[image->colors].red=(double) |
| GetPixelRed(image,q); |
| image->colormap[image->colors].green=(double) |
| GetPixelGreen(image,q); |
| image->colormap[image->colors].blue=(double) |
| GetPixelBlue(image,q); |
| image->colors++; |
| } |
| } |
| SetPixelIndex(image,(Quantum) colormap_index[intensity],q); |
| q+=GetPixelChannels(image); |
| } |
| if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) |
| status=MagickFalse; |
| } |
| image_view=DestroyCacheView(image_view); |
| } |
| for (i=0; i < (ssize_t) image->colors; i++) |
| image->colormap[i].alpha=(double) i; |
| qsort((void *) image->colormap,image->colors,sizeof(PixelInfo), |
| IntensityCompare); |
| colormap=(PixelInfo *) AcquireQuantumMemory(image->colors,sizeof(*colormap)); |
| if (colormap == (PixelInfo *) NULL) |
| ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", |
| image->filename); |
| j=0; |
| colormap[j]=image->colormap[0]; |
| for (i=0; i < (ssize_t) image->colors; i++) |
| { |
| if (IsPixelInfoEquivalent(&colormap[j],&image->colormap[i]) == MagickFalse) |
| { |
| j++; |
| colormap[j]=image->colormap[i]; |
| } |
| colormap_index[(ssize_t) image->colormap[i].alpha]=j; |
| } |
| image->colors=(size_t) (j+1); |
| image->colormap=(PixelInfo *) RelinquishMagickMemory(image->colormap); |
| image->colormap=colormap; |
| status=MagickTrue; |
| image_view=AcquireAuthenticCacheView(image,exception); |
| #if defined(MAGICKCORE_OPENMP_SUPPORT) |
| #pragma omp parallel for schedule(static,4) shared(status) \ |
| magick_threads(image,image,image->rows,1) |
| #endif |
| for (y=0; y < (ssize_t) image->rows; y++) |
| { |
| register Quantum |
| *restrict q; |
| |
| register ssize_t |
| x; |
| |
| if (status == MagickFalse) |
| continue; |
| q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception); |
| if (q == (Quantum *) NULL) |
| { |
| status=MagickFalse; |
| continue; |
| } |
| for (x=0; x < (ssize_t) image->columns; x++) |
| { |
| SetPixelIndex(image,(Quantum) colormap_index[ScaleQuantumToMap( |
| GetPixelIndex(image,q))],q); |
| q+=GetPixelChannels(image); |
| } |
| if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) |
| status=MagickFalse; |
| } |
| image_view=DestroyCacheView(image_view); |
| colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index); |
| image->type=GrayscaleType; |
| if (IsImageMonochrome(image,exception) != MagickFalse) |
| image->type=BilevelType; |
| return(status); |
| } |