Introduction to customizing of ImageMagick #3, color reduction
- From japanese, translation of http://labs.gree.jp/blog/2012/10/5249/
acceleration process of color reduction
Hi there, I'm yoya, client infrastructure team, GREE inc.
Continuing the story of color reduction, I talk about the customizing of ImageMagick.
- previous article > http://translate.googleusercontent.com/translate_c?sl=ja&tl=en&u=http://labs.gree.jp/blog/2012/09/4824/
It took long time especially in "integrated processing of the cube, which is divided in RGB space" corresponding to the second of the three phases of ImageMagick color reduction, I sped it up by little customize.
Here is previous article's figure which corresponds to the process.
Processing of original ImageMagick
This is a finer description of the previous article: "integrated processing of the cube, which is divided in RGB space"
Details of the integration process
In the color reduction of original ImageMagick, the cube in RGB color space is deleted in order in which quantize_error is small, and one processing that they integrate into parents' cube is repeated.
- source code (magick/quantize.c)
- repetition until the desired number of colors (ReduceImageColors)
static void ReduceImageColors(const Image *image,CubeInfo *cube_info) { #define ReduceImageTag "Reduce/Image" MagickBooleanType proceed; MagickOffsetType offset; unsigned long 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); (omit...)
- smaller cube than prune_threshold is absorbed into parent cube by tree traversal. (Reduce)
static void Reduce(const Image *image,CubeInfo *cube_info, const NodeInfo *node_info) { register long i; unsigned long number_children; /* Traverse any children. */ number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; for (i=0; i < (long) 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; } }
commentary step by step
At First, it traverse the tree of RGB color space to look for the object must be erased, and it get a smallest quantize_error value. (The example of figure is depth of 1, but deeper tree is actually composed)
It remove the cube of quantize_error = 10 found previous time, at the same time, look for the smallest quantize_error in cube remaining. Of course, It's the full search for tree.
Previous time it found a cube of quantize_error = 20 so also remove it, and Look for a next small cube of quantize_error.
In this way, it is the original process that follow all the tree node every turn off the cube of one, it's repeated many times the processing.
commentary ImageMagick acceleration
The idea that, looking for limit threshold where the color remained first repeat, by sorting quantize_error in ascending order, and threshold was put.
detail of customize
At first, follow all the tree node in the RGB color space, and flatten quantize_error to one-dimensional array.
- source code (magick/quantize.c)
static unsigned int QuantizeErrorFlatten(const Image *image, CubeInfo *cube_info, const NodeInfo *node_info, MagickRealType *quantize_error_list, int quantize_error_offset, int quantize_error_offset_max) { long number_children; register long i, num ; if (quantize_error_offset >= quantize_error_offset_max) { fprintf(stderr, "quantize_error_offset >= quantize_error_offset_max\n"); return 0; } quantize_error_list[quantize_error_offset] = node_info->quantize_error; num = 1; number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL; for (i = 0; i < number_children ; i++) { if (node_info->child[i] != (NodeInfo *) NULL) { num += QuantizeErrorFlatten(image,cube_info,node_info->child[i], quantize_error_list, quantize_error_offset+num, quantize_error_offset_max); } } return num; }
Put it in ascending order by qsort function, so used as threshold of quantize_error that you want to keep number of colors.
After you've initially assigned a value of cube_info-> pruning_threshold the quantize_error thus found, integrated processing of color space will end just follow once the tree. In addition, we assign to pruning_threshold at the beginning of the while through the next_threshold in on the program code.
- source code
static int MagickRealTypeCmp(const void *a, const void *b) { MagickRealType *af = (MagickRealType *) a; MagickRealType *bf = (MagickRealType *) b; if (*af > *bf) return 1; return -1; } static void ReduceImageColors(const Image *image,CubeInfo *cube_info) { <omit...> cube_info->next_threshold=0.0; /* yoya speed up customize */ if (cube_info->colors > cube_info->maximum_colors) { MagickRealType *quantize_error_list; unsigned int quantize_error_result; quantize_error_list = malloc(sizeof(MagickRealType) * cube_info->nodes); quantize_error_result = QuantizeErrorFlatten(image, cube_info,cube_info->root, quantize_error_list, 0, cube_info->nodes); qsort(quantize_error_list, cube_info->nodes, sizeof(MagickRealType), MagickRealTypeCmp); cube_info->next_threshold = quantize_error_list[cube_info->nodes - cube_info->maximum_colors]; free(quantize_error_list); }
Verification of customizing results
- By converting to a GIF animation from PNG avatar image using the convert command of ImageMagick, and compares the time before and after customizing.
Performance measurement
I experiment with avatar images heavy layer processing.
- Original ImageMagick (v6.6.0)
% time /home/yoya/test/im660/bin/convert -layers optimize avatar[1-8].png avatar.gif real 0m5.436s user 0m5.416s sys 0m0.052s
- Customize version of ImageMagick
% time /home/yoya/test/im660y/bin/convert -layers optimize avatar[1-8].png avatar.gif real 0m0.581s user 0m0.548s sys 0m0.052s
It's about 10 times faster.
This is an expedient example, but if the avatar image large number of colors, usually is several times faster.
Measurement graph
With 1,000 sampling avatar image that was displayed actually in production services, we've graphed if processing time will be changed to.
By converting to a GIF animation convert command a still image of the avatar of each material, trimmed mean of processing time *1 is arranged in short order). Units on the vertical axis is the number of seconds.
Enough to take longer to process, improvement effect appears strong, good results a very convenient came out.
If it is this, you may need a few seconds even in a situation in which the user is like to wait 30 seconds in the avatar image generation until now.
Issues
Not only good story, (color banding in the image frequently used gradients in each red, blue and green, are used evenly*2 It is easier) is generated.
Here is an example that I found finally by checking about 300 pieces of the avatar image of the user.
Because it is hard to understand at first glance, let's take a look at the pixels to expand.
When you focus on the area of the left cheek, you see that has fallen one gradation of the gradient. The reason for this is still unknown.
In fact, it can be a problem in the process of QuantizeErrorFlatten, does not take into account if there is a color palette of more than one in a cube of one, but Ru stingy the division of color space when it reaches the 220,000 nodes, the above The original image is a 10,000 colors, it is not per to this problem.
Even if there were 220,000 colors or more temporarily, because it specifies the offset cube of the number of colors that you specify to leave, affect the image quality loop of going the color will remain omitted tolerated with only If you move a little should not come out.
Since the time it takes to display on influence not nearly to the eye the final shorter by far, is not the hand that you do not want to apply to service this, but as a topic for future research, because it's ideal image quality even if you can maintain .
Other improvement plan
- RGB color space axis and distance does not match the characteristics of human visual sensibility. Those who were treated with a different color space are likely to keep the image quality more. For example, Lab, the derived system and CIE XYZ, and so forth as a candidate.
- I take the square root sqrt when calculating the distance in the color space, but since there is only compared to the distance, it seems better to treatment remains of the square of the distance is low load of the CPU.
- ImageMagick will be handled internally by each 16bits RGB then the build by default. Because it is 8bits almost in the world of Web, configure --with-quantum-depth=8 but keep most of the image quality is specified, you can up in no small measure the performance. However, it did not change time of process about the color reduction.
Summary
To explain briefly the customizing of this
- Arranged in ascending order qsort to expand to one-dimensional array quantize_error on each node octal(or 16 binary tree) tree that represents the color space RGB(A) to be used for color reduction, the threshold of quantize_error at offset 256 color remains The acquisition and the initial value of the cube_info-> pruning_threshold.
Customizing itself is simple.
I've commited customize patch to Github, this case and mobile phone bug fixes patch including animated GIF, which was introduced in old article
I'd appreciate it if used to reference.
Because it was a little overdone, it is called the package name in gross in-house, YoyaMagick.
I think the original version of ImageMagick is 6.6.0.4 to match the package of Debian squeeze, but also the latest ImageMagick, and you can be applied in copy & paste, maybe.
Thank you!
