ImageMagick v6 Examples --
Color Quantization and Dithering

Index

ImageMagick Examples Preface and Index

Color Reduction Introduction (what is involved)

Extracting Image Colors (what colors is used by an image)

Color Quantization (reducing the number of colors in an image)

• The Color Quantization Operator
• Color Quantization and Colorspace
• Quantization does not Preserve Colors
• Color Quantization and Transparency

Error Correction Dithering (Or Psuedo-Randomized Dithering)

• How an E-Dither Works
• E-Dither Change Sensitive
• E-Dither Pixel Speckling
• Monochrome Dithered Bitmap Images
• Two Color Quantization
• Dither using Pre-Defined Color Maps
• Common or 'Best' Colormap
• Using Web-Safe Colors
• Uniform Color Maps
• Uniform 332 ColorMap
• Gamma Corrented Uniform ColorMaps
• Posterize, Recolor Using a Uniform Color Map

Threshold Dithering Methods

• Threshold Images
• Random Dither with Thresholding

Ordered Pattern Dithers (Using a tiled threshold map)

• Diffused Pixel Dithering
• Digital Halftone Dithers
• XML Threshold Maps
• Ordered Dither with Uniform Color Levels
• Better Ordered Dither Results

DIY Dither Patterns and Threshold Maps (dither images in your own way)

• Multi-Image Bitmap Dither Patterns
• DIY Ordered Dither Threshold Maps
• DIY Horizontal Dither
• Dithering with Symbol Patterns

Reducing the number of colors or replacing specific colors is a very complex and difficult step in ImageMagick, and that is the topic covered in this example pages. This includes reduction of the overall number of colors, dithering or patterning the reduced number of colors, generating bitmap images, and even handling boolean (on/off) transparency.

This is so important that color reduction or quantization often happens automatically, just so IM can save to formats that can't hold all the colors available in an image, for example GIF, XPixmap, and XBitmap formats. Knowing this you can do the color reduction yourself, so as to improve the overall resulting image stored in a particular file format.

---

Color Reduction Introduction

Color reduction is a very important aspect of ImageMagick. For example to convert a JPEG or PNG image containing millions of colors, into a GIF image containing a maximum of 256 color, you really have to be able to reduce colors in a efficient and effective way. Often during an image format conversion, this happens automatically behind the scenes, but there are other times when you want to do this manually.

Reducing the number of colors in image is a typically a three step process,

1. First you (may) need to survey the colors an image uses. Not only to see how many colors are actually used, but how often a particular color is used. It is no good preserving one specific color, if only a single pixel is using that color, though sometimes you still need to do that.
2. Next you need to somehow decide on the final color set you want to limit your image too. Sometimes you what the 'best' set of colors for a specific image. Other times you may want something more general and global that can be used on any image.
3. And finally you need to modify the image so as to only use the colors you have selected. Preferably you want it so the results will look good, or perhaps you want it so that it will compress, compare, or optimize well.

To further complicate matters, these steps are often interlinked, as one method of replacing colors, often can only be applied using specific sets of colors. And if you are using a specific set of colors, doing some sort of color survey is not needed, or perhaps you need to make exceptions for specific colors.

Basically while color reduction is often automatically handled behind the scenes, you need to be aware that it is happening, and what its effects will be.

Color Survey

This is probably the lest important, and while IM provides you with methods to perform a survey, it is rarely done by users for color reduction. I will leave further discussion to the relevant section, Extracting Image Colors.

Color Selection (Quantization)

For a good initial overview see Wikipedia, Color Quantization.

There are four basic methods for the selection colors.

The IM Color Quantization method ("Adaptive Spatial Subdivision" using octtrees) surveys the colors in an image. It then attempts to choose a specific set of colors to best match a specific image, within the limits given. See the Color Quantization Operator below.

With "-map" you can give IM your own set of predefined colors (See User Defined Color Maps).

You can threshold all or specific color channels of the image, essentially making each color channel purely boolean or on/off. That is each color channel can be given a value of zero or MaxRGB (IM 'Q' level dependant). This however only produces a minimal set of about about 8 colors. A very limited color set.

The final alternative is to mathematically divide up each color channel into a set of color levels or intensities producing a 'uniform color map'. That is a color map with each channel set to a constant set of values or intensities. Threshold itself could actually be regarded as the minimal uniform color map with only two values.

These four color control methods: Quantization, Predefined Color Map, Uniform Colors, and Threshold; all have their limitations, as you will see.

Here is an example of each of these four methods...

The number of colors in each of the final images is only a representative set, but approximately 32 colors in each case (except for threshold which only has 8). From this you can get an idea of what you can expect from each of them.

Only the first color quantization, method actually will pick the color to be used based on the the current image contents. As the test image is predominately white, a lot of lighter colors is selected.

All the other methods have a fix set of colors (according to the operators argument) regardless of the image that is being color reduced.

The color map "colortable.gif" used in the above, is a set of 32 colors specifically picked for use in an old X Window Icon Library and is designed with cartoon like icons in mind. (See AIcon Color Selection for details).

Applying a Color Set

Once you have a set of colors, the next problem is to apply the color to an image so that it only uses the selected set of colors. This is known as 'Dithering', and is named as such because of its, "should I pick this, or should I pick that?", nature.

Basically the idea of dithering is to place pixels of different colors near each other in such a way as to fool the eye into seeing more colors in the image than is actually used. That is the color in that area of the image more closely matches the original color of the image, because of the way the human eye 'merges' neighbouring colors together.

One of the best introductions to Dithering is on Wikipedia though you will need to skip over the 'Audio Dithering' section at the start. This presents an excellent set of examples of the benefits of using a dithered pattern of pixels, when you have a limited set of colors.

The basic styles of dithering include...

• Direct Color Mapping
• Random Dither
• Error Correction Dithers
• Ordered Diffused Pixel Dither
• Digital Halftone Dither

Direct mapping if the nearest color in a given set is what was shown above. Basically you get distinct areas of solid, unchanging colors. When this is applied to a image of slowing varying color, such real life photo of sky, you get bands of colors. Not very good.

The only time direct color mapping is usually thought of as acceptable is for logos, symbols, icons, and cartoon-like images. It is actually rarely an option. This is why, you generally have to turn it off if you do not want dithering in your images.

Dither however has its own problem. Once a image is dithered, a pattern of colors becomes part of the image. Once such a pattern is present, it is extremely difficult to remove. Also it is generally a bad idea to re-apply dithering to an image multiple times, as that just degrades the image.

Because of this the examples will generally show you how to create un-dithered versions for each technique, so if you don't want it, you don't need it. It is also done so you can see what color selections are being made before dithering attempts hides that information.

Random dithering is the simplest dithering method created. It is also regarded as the worst possible dithering method. However it has some special uses. Within IM only works with the colors threshold, so it is usually restricted to special case bitmap dithering. For more see Random Dither with Threshold below.

Error Correction Dithering is generally regarded as being the best method of dithering colors across images as it will produce the closest approximation to the original color of areas in the image. It is also the only method that can dither any set of colors, and as such can be used for all four color reduction techniques. See How E-Dithers work below for more detail.

However Error Correction Dithering has some serious problems, especially with regards to animations of images. Also currently only only one version of error correction dithering is provided by IM.

The last two dithering techniques Ordered Diffused Pixel and Digital Halftoning is also regarded as a good method, and one that works well for animations, but it can not just use any set of colors, only a fixed set of uniform colormap.

It also however provides a means of using a set of graded patterns in images allowing you to produce interesting effects otherwise not easy to produce.

All these aspects of color reduction are important techniques, and with understanding you can improve the results of your image operations, beyond the generalised defaults that IM provides. It is well worth the studying.

---

Extracting Image Colors

Information about images, such as the number of colors used and the overall spread can be very important to programs and scripts that are trying to make decisions about the best techniques to use. Here I look at some of the methods you can use to determine this type of information, and not just for color reduction.

You can of course use a verbose "identify" to extract either the color table the image is used (for index color image formats like GIF), or the histogram of the colors used.

The output from any of the above verbose identification will not return the color tables or histogram if there are more than 1024 colors! As such for large colorful images this is a hit or miss affair, and not recommended, though with an initial color reduction it can still be useful.

The better way however is to generate a "histogram:" of the image and extract the comment that is included in the result.

	convert tree.gif -format %c -depth 8 histogram:info:-

The "info:" output format was added to IM v6.2.4. For IM versions before this use.. convert tree.gif histogram:- | identify -depth 8 -format %c -

The problem with these methods is that you are given a plain text output of the colors, which you will need to parse for your own needs.

However as of IM v6.2.8-8, the "-unique-colors" operator will convert an image into a smaller one containing just one pixel per unique color found in the original image, all in a single row.

This means you can convert a image into a simpler color table image, listing each color present. The width of the image returns the number of colors, and if you need to actually list the colors you can output it to a "txt:" image format.

For example here is the color table for the tree image.

convert tree.gif -unique-colors -scale 1000% tree_colors.gif convert tree.gif -unique-colors -depth 16 txt:-

The order of the colors in the single row produced by the "-unique-colors" operator, is undefined.

This reduced color table is also very important as a way of storing a colormap of generated colors in a very small file. Such maps are particularly important for the "-map" color reduction operator. (See Pre-Defined Color Maps below)

The average color of an image can be found very quickly by using "-scale" to reduce an image to a single pixel. Here for example is the average color of the built-in "rose:" image. I output the color using the FX Escape Format whcih returns a color string that can be used directly IM without change.

You can also use "-crop" to cut out a single pixel that you may be interested in. You can then output this pixel as a image, or even use the "txt:" Enumerated Pixel Image Format.

As of IM v6.3.9 there are a number of new "-format" escapes that can be useful to extract more specific information about images without needing to parse a verbose "identify" or "info:" output.

For example you can get the average red channel colour by getting the '%[mean]' greyscale value from of the images, red channel image.

---

Color Quantization

Color Quantization Operator

The primary work horse of color quantization, and what is used internally for all automatic color reduction, is the "-colors" operator.

This implements a "Adaptive Spatial Subdivision" color reduction algorithm, and is an extremely good color reduction algorithm.

Here is a typical example, I have a image of a 'colorwheel' image containing a lot of colors, and we ask IM to reduce the number of colors down to only 64 colors.

I turned off the dithering on the second image produced above (using a "+dither" setting) so you can see exactly what colors were selected by the color quantization.

You can also see IM will by default use a 'dither' to shade the colors over the image. This prevents the sudden changes in color over smoothly changing gradients. If you turn of dithering (using the "+dither" setting) you can clearly see what colors were merged together to generate what IM regarded as the best set of colors for this specific image. You can also see the sudden color changes that gradients of color will produce is dithering was not done.

Of course this image uses a lot more colors than what most images use. As such while a 64 color limit is often acceptable for many images, it is completely unacceptable for this image. In other words color quantization trys to fine the best set of colors for a particular image.

Here are example of color quantization for part of IM logo, using an extremely small number of colors.

Compare that with using the same number with the built-in "rose:" photo image.

As you can see cartoon-like images require far less colors than a real photograph to produce a reasonable result.

Only one Color Quantization algorithm, "Adaptive Spatial Subdivision", is currently implemented in IM, and as it works very well, there has been little need to add others. However with feedback this algorithm is being steadily improved. ASIDE: As a reference the "Gifsicle" program lists a number of other color quantization methods (using it "--color-method" option). I have no idea as to how well these color quantization methods compare to IM. If you find a good reference to different methods of color quantization, please mail me.

Color Quantization Internals

The process of selecting the limited number of colors to use in an image is called Color Quantization, and is a very complex process involving a number of factors. A full technical description of it is given on the ImageMagick web site Color Reduction Algorithm. However I'll try to example some of the more important aspects of this here.

Probably the biggest factor is the actual colors used in an image. It is no good picking a particular color for an image if their are very few pixels that are 'close' to that color. As such the color choice depends not only on the colors used in an image, but the number of pixels 'close' to the color.

I can demonstrate this quite easily by trying to reduce two different two color images to a single common color.

As you can see the single final color depends not only on the colors present, but the amount of each color in the image.

FUTURE: Just what are the effects of the "-treedepth"  setting?
Mail me if you know

Color Quantization and ColorSpace

The other big influence on what colors are selected is defining exactly what we mean by colors that are 'close' or 'nearby'. This is defined by the colorspace used for the quantization (color selection), and is (as of IM v6.2.8-6) controlled by the "-quantize" colorspace setting.

The "-quantize" setting becomes particularly important when a very small number of colors are chosen. To demonstrate, lets reduce a standard 'colorwheel' image, using various different color spaces, defining different 'color distances'.

As you can see the colors chosen depend heavily on how the colorspace is organized. The RGB (Red, Green, Blue) color cube will generally result in at least the colors close to the primary color being picked.

Chrisy notes that the CMYK colorspace acts like RGB colorspace because of the way a extra color channel is handled internally by ImageMagick. Both an images colormap and the CMYK black channel occupy the same data pointer. If we permit CMYK quantization it would overwrite the colormap indexes, and thus the black channel, which is not good when we later try to dither/replace the colors.

The CMY quantization colorspace should not have the four channel color problem of CMYK, but for some unknwon reason it is still producing an RGB quantization pattern, rather than a CMY pattern. Attempts to fix this have failed, as the cause of the problem is known at this time.

The RGB color space is particularly good at picking colors for cartoon like images and icons, but is actually a bad color space for general picture-like photos.

On the other hand YIQ, YUV are designed to produce more natural 'pastel' and 'mid-tone' shades of colors that are much better suited for photographs and images of the real world involving subtle shades of colors.

Christy, the ImageMagick Coordinator, notes that the most commonly used colorspace should be YIQ as it gives the best result when reducing a photograph of say a persons face to a limited color image such as GIF. I also agree with that recommendation.

The special color spaces involving a 'Hue' channel, such as HSL (Hue Saturation, Lightness), HSL (Hue, Saturation, Brightness), and HWB (Hue, White, Black), all have a cyclic color wheel representation of color as part of its color space. Actually it was using a HSL color space what was used to generate this color wheel. See Generating a Colorwheel.

At the time of writing, the distance algorithm IM uses does not take into account the cyclic nature of the 'Hue' or color of the colorspace, so a strong discontinuity occurs along the 'red' path. The result is that currently these color spaces do not generate many red colors in the color quantization process. This has been reported.

Finally there are a larger number of some very weird color spaces that are used for more specialized purposes. I have shown three of these above. If anyone has some info on what these (and other colorspaces) are used for, or can refer me to more info, please let me know.

In older versions of IM (specifically IM version 5) the color space that was used for quantization was set with the "-colorspace" option. However in IM version 6 this operator is used for modifying how images are stored in memory, and as such is not a setting for color quantization. As such in IM v6.2.8-6, the "-quantize" setting was provided to do this job. However it is only as setting for the "-colors", Color Quantization process. It will not do anything for the replacement and dithering of colors using operators such as "-map" and "-posterize", or the various dithering techniques.

For a complete list of the colorspaces available see the "-colorspace" operator.

You can see more effects of the colorspace on color selection by looking at the examples on Random Spots of Solid Color. There color quantization is used to reduce the number of colors in a randomized image using various colorspaces.

Quantization does NOT Preserve Colors

Note that in all the above images a pure-black color is never actually picked by Color Quantization. The only black that appears was added later as part of the labeling of the image. Even the 'GRAY' color space image did not produce a pure-black color. In fact none of the images contains any of the primary or secondary colors, such as: red, blue, green, cyan, magenta, or even white! I also doubt a specific 'named' color was picked either.

This situation however is not a bug!

First, a 'black' color was generally not selected in the above examples, usually because as their is very little black in the original image, so the Color Quantization generally did not worry too much about dark colors. In fact it generated more of the lighter colors as these are more common in the image. See the previous section for a specific example.

Secondly, as quantization is trying to pick colors that are close to the maximum number of existing color pixels in an image, this is best achieved by NOT matching a 'pure' primary or secondary color as these are the always at the extremes of the color space being used. An 'off' color will tend to match more colors than a 'primary' color, so these more often selected.

As such even though the original image used contained a lot of 'white' pixels, after color reduction a near-white color was chosen to better represent all the whitish colors. As such not even white was chosen as on of the colors in any of the above examples!

So let me be clear...

As of IM version 6.3 the Color Quantization function was modified to try to include colors that are common in the original image. As such if an image contains a area of a single color, that color will be included in the final color map. This improves the situation somewhat, especially for 'cartoon' like images or images on a solid color background.

Specific Color in Colormap Solutions

At the moment there is only a few ways of fixing this 'specific color' problem.

One way is to quantize the image as normal, but then and output the generated color map (using "-unique-colors". Now you can adjust that color map so your white is really white. You can now Map the new color map to your image.

The colormap may no longer be the BEST colors for the image, and some other colors probably should also be adjusted, but it will be close to the colormap that you wanted.

Alternatively, append large patches of the specific colors wanted to the image, before using "-colors". Those colors will hopefully become included in the final color map (and all other colors adjusted to fit better).

If this works you can then just Crop the image to remove the extra color patches added. If it doesn't, then IM should have at least added a color close to the wanted 'specific color' so only very slight adjustments of just those color should be needed, before you again Map the colors to the original image yourself.

If you try this, with success or failure, please mail me

Ideally, what I would like to see added to IM is a way to specify a small number of specific colors, that must be part of the final color map, and then somehow ask IM to pick the best colors for rest of the colors in the color map, for a specific image.

Color Quantization and Transparency

ImageMagick by default not only generates fully opaque colors, but also attempts to generate semi-transparent colors. In this way images containing transparent shadows or other overlay effects will not loose those effects.

However as IM v6.2.6, color quantization that involves transparency was modified so as to treat all fully-transparent colors as being the same color. This is a linear modification so colors which are only half-transparent are also thought to be closer together than if they were fully opaque.

Because of this modification IM Color Quantization will still generate semi-transparent colors, but will concentrate more on the opaque colors and less on the fully transparent colors in the image.

For example here I generate a Rainbow Gradient of colors, with the image fully-opaque at the top, and fully-transparent at the top. I have displayed the images on a background pattern so that you can see just how transparent the image is.

As you can see, when we ask IM to reduce the number of colors needed by this image it created a lot more opaque colors, and used fewer highly transparent colors for the more translucent parts. The result is a very good spread of colors selected, especially when the number of colors is very small.

However just as I pointed out above, not only do primary colors not get picked, but the fully-transparent color will also not get picked for exactly the same reasons. In actual fact even fully-opaque colors will not get picked! In other words every color in the color quantized images in the previous example is semi-transparent.

Let me just make that clear.

Of course as of IM v6.3, and the 'common color' bug fix (see Quantization does NOT Preserve Colors above), that is less likely to happen if the image contains a lot of opaque and fully-transparent colors, which is commonly the case.

As some images can contain a lot of semi-transparent colors, such as images involving smoke or shadows effects, you may like to do a trial run, to make sure a fully-transparent color is selected for inclusion in the resulting image. You can then remap the most-transparent color to fully-transparent, and do the Color Mapping yourself.

FUTURE: Example of remapping the most transparent color to full
transparency. Prehaps a -contrast-stretch of the alpha channel?  --
your solutions are welcome.  

This is NOT a problem for GIF images which do not allow semi-transparent colors, JPG which does not allow transparency, or even PNG which do not need quantization to save properly. It only becomes a problem in specal cases where you may force an image to be quantize and lots of semi-transparency is involved.

Remember for the GIF format saving semi-transparent colors is a useless endeavor. As such if you plan to do color quantization yourself for such an image format, you need to tell IM to ignore image transparency when generating its reduced color set. you can do that by using the special "-quantize" color space setting of 'transparent'.

Notice how the color quantization completely ignored the transparency of the colors, and did not touch the images alpha channel at all. This means you can process the alpha channel in a more appropriate way for your image, completely separately to the other colors. In fact you can do so either before or after using "-colors" without problems. It will make no difference in the result.

This quantization color space is thus recommended when reducing the number of colors for an image you plan to save to a format with boolean or no transparency, such as GIF or XPM image formats.

If you count up the number of colors generated you will also see that it generated exactly the number of colors requested. As such if you you also need a fully transparent color (likely) then you need to reduce the argument of "-colors" by at least one, to leave space for it in the images final color table.

Thus to handle the GIF file format 256 color color table limit, you will need to reduce colors to 255, and not 256, leaving the extra space for the fully-transparent color index, as defined by the "-transparent-color" setting. Adjust this for a smaller color table sizes.

This quantization behaviour is automatic when IM saves to the GIF file format, but is important when you need to DIY the quantization yourself while generating global or shared color tables.

Of course you do still need to handle the semi-transparent pixels, so they are correct for what you want your image to look like.

FUTURE: This last part will probably move to a new section on 'Dithering
Alpha Channel' to be created in the near future. And a reference to this
section added here. 

Here are some examples of dithering just the alpha channel to just a boolean or on/off setting, without effecting the rest of the color channels in the image.

When extracting a copy of the Alpha Channel, so you can dither it using either "-monochrome", or "-map", be sure to remove any remaining alpha channel component from the copy, either by using "+matte", or using "-separate" to create a proper gray-scale image of the channel. If you don't you will probably end up with non-linear effects from the alpha channel still being present.

---

Error Correction Dithering

As discussed in the introduction an error correction dither is generally regarded the best choice for producing the truest representation of the original image with a reduced color set. It also limits itself to any pre-defined palette of colors, whether it was user supplied, or as determined by the IM color quantization routines.

Because of this it is the logical default choice for general color reduction as provided by the IM operators, "-colors", "-map", "-posterize" and "-monochrome".

How an E-Dither Works

The specific method used by IM for general dithering is a variation of the "Hilbert Curve Error Correction Dither". This is actually a very good dithering technique, very well defined and reasonably quick. For a full description (and a very simular variation) see... Riemersma Dither.

Basically each pixel in the image is looked at in a very complex path known as a 'Hilbert Curve'. The pixel is assigned the color closest to that pixels value, and any difference between the pixels original color and the selected color, is saved and added to the next pixels color values (which is always a neighbouring pixel) before a new color is again selected. In this way any color variations between selected colors and the images original color is distributed to the other pixels in the same area. The result is that while only specific colors will be assigned to the final image, the same basic overall color for that area will closely match the original image.

For example, here is a small grey image that I asked IM to dither using a set of colors that does not include the original color. The resulting image is magnified so you can see the individual colored pixel assigned.

As you can see the as the original images color was not in the specified color map, the original color is approximated using a pattern of the three nearest colors that were in the given color table.

If we were to average the color generated by the above dither pattern, we would get the color Which is very close to the images original average color of and that is the whole point of the dither pattern that was produced.

However as the 'path' used to assign colors is complex (though generally remains in the local area), the color assignments produce an essentially random pattern. It isn't technically random however as the same image will produce the same pattern, but it may as well be random, or pseudo-random.

The "Hilbert Curve E-Dither" method, is on a par with a more commonly used error correction dither, the "Floyd-Stienberg E-Dither", which instead of passing errors along a single path, distributes its color errors to a larger set of 'neighbouring pixels'.

The "F-S" dither is actually only one (the first one) of several 'Rasterized E-Dithers' that has been developed since its inception in the early 1970's. It is also probably the most widely implemented, even though it is not regarded as the best one. See the paper, Dithering Algorithms, for a more complete summery of such algorithms.

The "Floyd-Stienberg Dither" in particular I find produces a more 'hash' like pattern of pixels than the "Hilbert Curve Dither". A more regular pattern can make a low level manual clean up of minimal color icon images, a lot easier. This was something I did a lot of in my past for Anthony's Icon Library, but that type of thing is not often needed anymore, with the newer, truecolor displays, most computers use these days.

Unfortunately none of these other types of error correction dithers are currently available within IM. All of them however still share the same general problems of error correction dithers, whcih we will look at next.

E-Dither Problem - Change Sensitive

One of the biggest problems you face when you use an error correction dither is that you get an essentially random pattern of pixels, that is also highly sensitive to changes.

Here for example take the original grey image and replace one pixel with a different color before dithering it again. The result is a complete shift of the dithering pattern in every pixel that is further along the path followed by the Hilbert Curve Dither.

As you can see just adding a single pixel to the image resulted in the dither pattern changing dramatically! It only takes a single bit change for the resulting image to become different, even though overall look of an image (when not enlarged) is still basically the same (which is the purpose of a good dither algorithm after all).

The "compare" image also shows the extent of the change in the dither pattern. In this case approximately 80% of the pixels were assigned a completely different color. In a Hilbert Curve Dither, a single pixel change actually will result in every pixels that comes later being possibly different, which means any here from 0 to 100% percent of the dither pattern could be different. It just depends on where in the complex Hilbert curve the change occurred.

Just to give you some perspective, here is the same example but using a "Floyd-Stienberg Dither" provided by the NetPBM image processing package.

As you can see it has exactly the same problem. A single pixel change causing an almost complete change in the dither pattern for the part of the image that is processed after that pixel is seen by the algorithm.

It also shows how a rasterized error correction dither, such as the "Floyd-Stienberg Dither" tends to distribute errors only in one direction (usually downward) in the image. The result of its line by line (or raster) approach to dithering.

IM currently does not implement a rasterized error correction dither algorithm at this time.

The Floyd-Stienberg Dither, like the Hilbert Curve Dither, is a algorithm without random components (only pseudo-random effects), however the NetPBM "pnmremap" has some sort of random component in it. As such the same images dithered using the NetPBM FS Dither will always turn out differently due to randomized components. They should not be. Because of this the above example is actually not a good test, due to these random components. However the NetPBM developers have added an option that will remove there randomized component. When this new version becomes available then the above example should become valid. Do you know of an alternative E-Dither Algorithm I can test against?

For a single image the resulting pattern of the dithered colors is unimportant. The average color of the pattern should give the image the appropriate color for that area of the image. But when you have an animation in which one image is followed by other similar images, with large areas of constant color, the changing dither pattern becomes highly noticeable and irritating as a low level background 'noise'.

For example, here I generate a 3 image animation of the same dithered color but with a single pixel change in each frame. I also magnify a central region so you can see this changing pattern more clearly.

As you can see you get a sort of churning background to the image, caused by the pseudo-randomness generate by the E-Dither. In most cases the colors used are close enough together so as not to make this 'dither noise' visible. But when the dithering colors are visibly different (in this case forced by the use of a colormap) it definitely becomes an issue.

See Video Color Optimization for a more practical example of an animation showing this 'dither noise'.

The change in pattern also cause problems in optimizing the image. That is a different pattern means that simple frame optimization fails to reduce the size of frame overlays. For one solution see fuzzy color optimization.

Unlike other dithering methods the "-channel" setting does not effect color quantization, or error correction dithering. Basically has it has no place in these image operations.

Ordered dithers do not have any of these problems, but are generally limited to using a mathematically derived color set. (See Ordered Dither using a Uniform Color Map). I am working on an simple ordered dither (very simple) that can use a user provided color map.

E-Dither Pixel Speckling

Another problem with E-Dithers is that they can produce the occasional odd-colored pixels in areas which would otherwise be fairly uniform in color. For example the occasional green, pixel in a greyscale image. Or as in the examples below, a white pixel in a areas of otherwise plain flat blue color.

This is especially the case in large images which containing objects with large numbers of colors, and other areas of plain solid unchanging colors. This is especially typical of colored objects overlaid onto flat colored backgrounds, as you often get in diagrams and drawings.

You can see such a odd-colored pixel in the enlargement of the test examples above, where an extra ligt purple pixel was added quite a distance from the small single pixel change. The odd-colored pixels added to the above is not however readilly visible and the color map does cover the image rather well, so the odd pixels are reasonably close to the normal three colors used for dithering the image.

For a more extreme example, here I have a blurred gradient background, which I heavily color reduced to 64 colors to really stress the error correction dither.

convert -size 100x60 xc:SkyBlue \ -fill DodgerBlue -draw 'circle 50,70 15,35' \ -fill RoyalBlue -draw 'circle 50,70 30,45' \ -blur 0x5 -colors 64 speckle_gradient.gif

As you can see with this highly reduced color map, the error correction dither did a reasonbly good job of representing the original gradient.

But if we add a patch of pure white to the above...

convert -size 100x60 xc:SkyBlue \ -fill DodgerBlue -draw 'circle 50,70 15,35' \ -fill RoyalBlue -draw 'circle 50,70 30,45' -blur 0x5 \ -fill white -draw 'rectangle 40,40 60,55' \ -colors 64 speckle_problem.gif

You can see that the E-dither suddenly started to produce a sprinkling of white pixels in the upper area of the image where we didn't have any before.

Here is a enlargment a small section so you can see these pixel more clearly... convert speckle_problem.gif -crop 15x15+85+0 +repage \ -scale 90x90 speckle_prob_mag.gif

The odd colored pixel is caused by two factors.

First, the Color Quantization was forced to include a single pure white color (but no other white-blue anti-aliasing colors) into the final colormap for the image, thus the dithering process to use this extra color.

But as E-Dithers slowly accumulate errors, eventually the errors will add up to a large value. That is the 'error' escapes the normal blue gradient color map. However with the added white color in the color map, it suddenly thinks that adding an extra 'white' colored pixel, is a good way to 'correct' the slow accumlation of errors when it gets large enough. As such every so often a white pixel is output to 'correct the error' at a psuedo-random locations.

The result is a very light speckling of white pixels. The slower the accumulatation of error, the more spread out those white pixels are and the more, out-of-place, they appear.

The best solution is to switch to some other image format that does not have a limited color table. For example convert you GIF format image to PNG. This will avoid the need for color quantization (reduction) and hence the need to dither the reduced colors.

The next solution is to replace the use of E-dither with some other dithering method, such as Ordered Dithering. However that is currently not easy thing to apply in IM at this time. See Better Ordered Dither Results, for one such method until a more general one is found.

If switching to another image format, or using a different dithering method is not practical (and often isn't), then you are left with attempting to fix the situation for that specific image.

The best fix, to this is to somehow insure you have other colors just outside the large group of colors that is causing the E-Dither error accumulation. However normal Color Quantization does not do this. It tends to pick more average colors, inside the color group, that best represents a group of colors, than a set of pixels which are on the edges of a large set colors.

Here for example, I used a circle rather than a square, so that not only is a pure white color added, but a number of white-blue colors also. These were added automatically due to the anti-aliasing of the circle edges, to smooth its look.

convert -size 100x60 xc:SkyBlue \ -fill DodgerBlue -draw 'circle 50,70 15,35' \ -fill RoyalBlue -draw 'circle 50,70 30,45' -blur 0x5 \ -fill white -draw 'circle 50,45 40,40' \ -colors 64 speckle_fixed.gif

And a magnification of the same area as before. convert speckle_fixed.gif -crop 15x15+85+0 +repage \ -scale 90x90 speckle_fix_mag.gif

As you can see the additional colors provide the extra colors, just outside the blue-cyan gradient. Now while these extra colors will mean there are fewer colors available for the actual gradient, they do provide other colors in a blur-white gradient that will allow the E-dither to correct itself sooner, and more often, before the accumulated error can grow too large.

That is not to say we have not preventing E-dither speckling, just provided better colors for the dither algorithm to work with. If you study the magnified portion of the image you will still see a speckle pattern, but the colors are closer to the background color, and there are a lot more of them producing a more even, localized spread of speckles.

Another way is to generate our own color table, prehaps based on the one IM generated, and add the appropriate colors to prevent the error accumulation. This is however not an easy thing to do.

For this specific image, one way to prevent 'speckling' is to generate and dither the background, with slightly less colors that is needed, then overlay the white box.

convert -size 100x60 xc:SkyBlue \ -fill DodgerBlue -draw 'circle 50,70 15,35' \ -fill RoyalBlue -draw 'circle 50,70 30,45' -blur 0x5 \ -colors 63 \ -fill white -draw 'rectangle 40,40 60,55' speckle_perfect.gif

This will add a 'white' color to the image, but the background will not have any speckling effect, as white was not available when it was dithered using the error correction dither.

The result is an image with exactly 64 colors, and no speckling at all. However this is very dependant on the image and what you are trying to achieve, so is not a general solution to the specking problem.

A more general alturnative to adding extra colors is try to remove the speckles from the final dithered image. That is clean up the image in some way.

However this is itself a tricky problem, as you do not what to remove pixels which are part of the normal dithering pattern.

What we need is to find color pixels which are somehow very different to all the the colors surounding it, but which are also well isolated from all other simular colors, by some distance. Suggestions Wecome

Summery

To me speckling is a very annoying problem, especially for desktop icon images using a very limited color table. I myself often edit smaller 'icon' images to remove speckles or fix some of the other dithering effects, such a vertical banding.

If you know of another better solution, please let me know.

Monochrome Dithered Bitmap Images

The "-monochrome" operator is a specialized form of both the "-colors" operator to generate a bitmap image. It is as such an ideal operator to demonstrate not only 'Hilbert Curve Dithering', but also have a closer look at color selection.

Here is a typical example.

convert logo.png -monochrome monochrome.gif

The operator dithered the image solely based on their grey-scale brightness 'intensity' or 'level', however it doesn't dither the whole grey-scale range directly but thresholds the most extreme values to their maximum values.

We can see this by asking IM to dither a gradient image.

As you can see the gradient only has about the middle 50% of its colors dithered by the "-monochrome" operator. Special thanks goes to Ivanova <flamingivanova@punkass.com> for pointing out this interesting fact of the was IM works.

If you like to dither using the whole grey-scale range, you can use the "-map" operator using a pure black and white colormap (supplied by a built-in pattern image).

convert logo.png -map pattern:gray50 mono_map.gif convert -size 15x640 gradient: -rotate 90 \ -map pattern:gray50 mono_map_gradient.gif

By more careful selection of colors using "-map" you can effectively produce the same 'threshold' range as used by the "-monochrome" operator, or any other threshold range you like.

convert xc:gray20 xc:white +append ctrl_colors.gif convert logo.png -colorspace Gray \ -map ctrl_colors.gif -normalize mono_map_ctrl.gif convert -size 15x640 gradient: -rotate 90 \ -map ctrl_colors.gif -normalize mono_map_grad_ctrl.gif

What "-monochrome" actually does is to first convert the given image first into a grey scale image, after that it performs a two color 'Color Quantization', to decide the threshold colors to dither the image with. This is what the next section of examples will explore.

The "+dither" setting currently has no effect on the result of "-monochrome". This however may change in the future, so make sure it is not turned off in your scripts when using this operator.

Two Color Quantization

Rather than picking the two control colors yourself, you can use color quantization to pick the best two colors in the image by using the "-colors" operator. convert logo.png -colors 2 -colorspace gray -normalize \ colors_monochrome.gif

However the result will not be the same as using "-monochrome", as we didn't convert the image to grey-scale first.

Instead the image was dithered directly between the two non-grey color values chosen. That is the best two colors is selected to dither the image with, rather than two gray-scale brightness levels. Consequently it will produce a better result for say image that only uses colors of about the same gray-scale 'level'.

Here for example we use "-colors", as well as a "-monochrome" bitmap dithering operator, on a red-blue gradient. As you can so you can see that the results are not the same.

The "-monochrome" operator in the above failed to find any differences to bitmap dither as both blue and red are very nearly the same intensity. Using a "-colors" quantization method however had no problem in finding acceptable colors to dither between.

You can also see that only the middle portion of the colors were dithered. This is due to the color quantization picking colors in the middle of two color 'clusters' it selected. Colors on the 'outside' of the selected colors in is thus effectively threshold directly to that color without dithering.

This demonstrates that colors on the outside of the quantization color space does not get dithered, though this fact is difficult to make use of in a practical way.

By setting the "-colorspace" to gray-scale before quantization, you will reproduce the internal operation of the "-monochrome" operator. convert logo.png -colorspace gray -colors 2 -normalize \ monochrome_equivelent.gif

And finally, by turning off the dithering, you can produce a more automatic separation of the colors in the image than produced by using a fixed "-threshold" setting. convert logo.png -colorspace gray +dither -colors 2 -normalize \ threshold_two_grays.gif

Remember "-monochrome" currently ignores the "+dither" setting, so you can't just use that operator to do a 'smart threshold'.

If you remove the "-colorspace" for the color quantization stage of the image processing, you can threshold an image based on the best color separation (rather than greyscale color seperation) posible for that image. convert logo.png +dither -colors 2 -colorspace gray -normalize \ threshold_two_color.gif

Dither using Pre-Defined Color Maps

As shown above "-colors" attempts to choose an optimal limited set of colors with which to represent an image. With "-map" you provide IM with the final set of colors you want to use for the image, weather you plan to dither those colors, or just replace the ones with their nearest neighbours.

The argument is given as a image containing all the colors you would like to use. If you what to reduce a large image of colors to just its list of colors, you can use "-unique-colors", before saving, it for later use by "-map".

Note that while the "-map" operator will accept any image to use, do not use a JPEG image for this image or you will get a lot of extra colors due to its 'lossy compression' generating extra colors.

For example here I limit the colors used in the IM logo to a predefined map of named X window colors. Of course if you turn off dithering (using "+dither"), IM will just map each color pixel in the image directly to the nearest color in the provided color map.

As you can see IM attempted to do a reasonable job of representing the image using just the given colors, though the results is nowhere near as good as the image you get if you allowed IM to select the color set to use.

Mind you this "colortable.gif" image was never designed for dithering images, but as a color set for designing cartoon-like color icons for older more primitive X window color displays (See Anthony's X Window Icon Library and AIcons Color Selection for details).

Mind you IM's selection of 'LightSeaGreen' instead of say 'DodgerBlue' for the wizards jacket is rather surprising and is probably due to the use of RGB colorspace for color distancing. Unfortunately you do not have a choice about the color space for actual color internal map/dither operation.

Also note that the final image did not use all 32 colors provided by this map, though more of the colors in the map will be used when dithering was enabled (), than when it was turned off ().

This last example shows just how important selecting a good colormap is. Because of this I recommend you let IM optimize the color selection used in an image using the "-colors" operator, and modify that to suit your needs, unless you have more pressing reasons not to do so.

One final point, while you can specify a color space in which "-colors" will find the best set of colors, you currently can NOT define a color space for the color mapping or dithering phase. All my experiments seem to show that the color set is applied (both error correction dither and nearest color replacement) based on RGB space. The "-quantize" colorspace setting is only used for the selection of colors, not its mapping.

So if using a color map is such a bad idea, why would you want use it?

There are a number common reasons, usually because you need more control of the specific palette of colors used in an image. If you know of another reason to use the "-map" operator which I have not presented below - Mail me.

Common or 'Best' Colormap

The other technique, when handling multiple images, is to generate a common color table for all the images involved.

Basically you append all the images together into one large image, then use the "-colors" operator to figure out a good color map to use that is common to all the images. Once you have that color map image you can use it to re-color each of the original images using this juts generated Pre-Defined Color Map.

Alternativally, you can use the special "+map" operator, which does the same thing to a 255 color colormap. It counts up the colors, perform the color quantization to form a good, common colormap, then dithers the images to use that map, if needed.

Both "-map" and "+map" forms however has one very important feature for GIF animations. It converts all the images to a image "-type" of 'Palette' with all the images using the same palette of colors.

The reason is that when writing a GIF image, the first images color palette, will be used for the file formats 'global colormap'. Then as each image is written it notes that those images use the same set of colors, so it does NOT create a 'local colormap'. This can save up to 256 × 3, or 768 bytes of colormap space for each and every image the final GIF file.

Only the "-map" operators can do this. So when handling GIF's and in particular GIF animations, it can be an important point to remember.

For more details, and an example see Gif Animations, Global Color Table.

Web Safe Coloring

When the WWW was first created, computer displays had a limited range of colors available, and web browsers usually used a simpler set of colors for images. As such it was common to recolor images to this color set, to make them both smaller, and to ensure they will look okay on users browsers. For more detail see Web Style Guide, Dithering.

To help with this IM provided a built-in colormap image of this special table of 216 colors, called "netscape:". So lets look at how our test image would look on of a old web broswer display using these colors.

This color set was a mathematically determined pallet, designed by engineers of displays and computers, not graphic artists, and while it is is general enough that it works reasonably well for real images such as photos, it is very bad for images containing large flat areas of color, such as logos, backgrounds, computer generated images such as graphs, and cartoon-like images.

Basically this works in areas of highly variable colors, but for the larger flat areas of constant colors a dithering of three colors (in general) is applied, such as the off-blue shirt of the IM logo test images (above).

In other words, if you were designing an image or logo for use on the web, you work generally try to use the colors in this pallet for the large flat areas, and only have dithered colors in areas where your have varying shades of color.

The above commands lets you test your images to see how they would look on more primitive computer displays, and to edit image to use these colors, so they will work well. This is particularly important for symbols and navigation images.

Of course today, thanks to the demands by game and web users, you can be pretty well assured that most users have a modern computer display that does not have those old color limitations, however the use of this "web safe palette" is still around, as it does have other benefits, such a image compression.

For a discussion about the use of Web-safe colors in the modern world see Death of the Web-safe Color Palette?, and probably a more important view from a graphic designer that first identified this color map, Lynda Weinman.

Generating Color Maps

Determining a good color map for any image, or a a specific set of images, can be very important. This becomes especially important when you are dealing with a sequence of images that will be used for GIF animation. Basically you want to make it so they only need one color table, to use for all the frames of the animation, rather than a separate color table for each frame. In other words you want one single color map for all the image.

You have really only two choices in this case. You can attempt to create a colormap that will work well for any image, or you try to optimize a color map for the specific set of images you are applying it to.

Web-Safe Colormap

The first method is typically a mathematically generated color map, such as the IM built-in "netscape:" color map. This provides a set of 216 colors, which will nicely fit into the GIF formats 256 color limit, and still have space for handling image transparency, or even adding some extra colors for special purposes, like shadows, or text overlays.

This color map was generated by creating 6 levels of colors for each of the three color channels, producing 6×6×6 colors or 216 colors. The number of the beast.

As only 219 color are used it still has space (for GIF images) to add more colors to the color map for specific purposes. For example a transparent color, as well as more grey scale shades. An old Macintosh version of the web-safe map actually did exactly this to try to improve its overall result, but it was only used on Macintosh web clients.

This is probably the most common 'uniform' (or mathematically derived) colormap in general use, thanks to its simplicity, and its general use on the the World Wide Web.

Uniform 332 Colormap

Another uniform color mapping that is commonly used is the "332 RGB color map". The number refer to the number of bits used to represent each color within a 8 bit color index. That is 3 bits (or 8 levels) of red, 3 for green, and 2 bits (or 4 color levels) for blue, seeing as our eyes do not respond well to blue. This gives 3+3+2 bits or an 8 bit color index, or 256 colors. Perfect for the limited GIF color table. However it will not leave any space for a GIF transparency color, or other special use colors.

Here is one way to get IM to generate this color map...

convert -size 16x16 xc: -channel R -fx '(i%8)/7' \ -channel G -fx '(j%8)/7' \ -channel B -fx '((i>>3&1)|(j>>2&2))/3' \ -scale 600% colormap_332.png

The bit-rolling operators '>>' and '<<' was missing from the "-fx" operator until IM version 6.2.9-2.

The only drawback with this map is that it does not actually provide any 'gray' colors at all. However this drawback can be a plus when dithering is used as the difference produces a less distinct color boundary changes in a grey-scale gradient, making it just that little bit smother looking.

TrueColor 16bit Colormap

A similar uniform colormap to the '332 colormap' above, is used by X windows in a rarely used 16 bit visual class. In this case 16 bits are used for the color index, and is divided into 5 bits for red, 5 for green, and 6 for blue.

In other words this color map is more like a "556 colormap". It is however rarely seen outside this environment as images usually us an 8 bit color table, or 8 bit color levels (8 bits per RGB value, or 24 bits, 32 with transparency). As such I won't mention it further.

Gamma Corrected Uniform Colormaps

FUTURE: gamma-corrected uniform palette
        http://www.compuphase.com/unifpal.htm

Figure out gamma corrected colormaps,  6 level, 332,
as well as the full 256 colormap defined by this article.
Figure out how to incorporate these into the -ordered-dither expansion.

Posterize, Recolor using a Uniform Color Map

The operators original purpose (using an argument of '2') is to re-color images using just 8 basic colors, as if the image was generated using a simple and cheap poster printing method using just the basic colors. Thus the operator gets its name.

The "-posterize" operator is actual fact is a special color reduction operator that generates a color map based on the the number of color 'levels' given, for each color channels in the image, dithering the image using an error correction dither.

As you can see a "-posterize" argument on '2' means to only provide 2 colors per color channel, producing a map of just 8 colors for a 3 channel RGB image, such as the above. Basically it will recolor images using the threshold set of 8 colors.

An argument of '3' will remap images based on a colormap of 27 colors, including mid-tone colors. While an argument of '4' will generate a 64 color colortable, and '5' generates a 125 color colormap. Of course as mentioned above, an argument of '6' will reproduce the same set of 216 colors, as provided by the in the built-in "netscape:" image.

Please note that a "-posterize" argument of '0' or '1' is non-sensible, and with the latest IM releases just converts images to pure black (which though logical, is quite useless).

The result is that the image has been recolors using a mathematically derived or 'uniform' color map.

Lets repeat this using the shaded "colorwheel" image.

And here is the same thing with dithering enabled...

For example..

Of course many of the bitmap dithers we look at in the next section can also generate level 2 ordered dithers, using various sorts of dither styles. However few can use a larger number of grey levels.

Ordered Dither as of IM v6.2.9, is also a posterization method, due to its current limitation in dithering using a uniform colormaps. However the dither pattern is more uniform, with a larger selection of styles, than the pseudo-randomized dither produced by "-posterize". Compare these with the dithered "-posterize" versions above.

The 'threshold' dither map (instead of 'o8x8' map used in the last example) effectivally converts "-ordered-dither" into a un-dithered posterization method.

Finally the Ordered Dither does allow you to specify a different number of color levels, for each individual color channel unlike the "-posterize" operator.

---

Threshold Dithering Methods

Threshold Images

The simplest method of converting an image into black and white bitmap (to color) image is to use "-threshold". This is actually a simple mathematical operator that just provides a cutoff value. Anything equal to or below that value becomes black, while anything larger becomes white.

As you can see a value of '-1' will convert all colors white, while '100%' converts all colors to black. A '50%' is of course the most common value used.

A value of '0' is a special case which turns all non-pure black colors, white. Not that there are any pure black colors in this test image, unless it is normalized first. convert logo.png -normalize -threshold 0 threshold_black.gif

If you actually want to convert all non-pure white colors black, then I recommend that you threshold the negated image instead of trying to work out the right threshold value to use (one les than IM's current 'MaxRGB'), a valueo that is dependant on your specific IM's compile time in Quality, or 'Q' setting. convert logo.png -negate -threshold 0 -negate threshold_white.gif

The "-threshold" operator can be classed as a ultimate 'contrast' operator, maximizing the differences in colors by the threshold level. It is however a gray-scale operator, meaning that the "-channel" setting, can be used to adjust which color channel the operator will be applied to.

For example you can threshold each of the individual channels of the image to produce the same effect as a un-dithered level 2 "-posterize" operation.

convert logo.png -channel R -threshold 50% \ -channel G -threshold 50% \ -channel B -threshold 50% threshold_posterize.gif

Note that "-threshold" treats any transparency in an image as a matte channel, not an alpha channel (just as it is stored internally within IM). As such caution is needed if you plan to apply this operator to the alpha channel. See Matte Channel Examples for more details.

For a more automatic thresholding technques you can use a Two Color Quantization technique, we showed previously.

For example, this will threshold the image based on the best two colors found in the image. These colors may not necessarily be greyscale or even oppisites, just the two colors that best represent the whole image. The two colors are then mapped (using "-normalize") to pure black and white. convert logo.png +dither -colors 2 -colorspace gray -normalize \ threshold_two_color.gif

Random Dither and Threshold

The "-random-threshold" operator is a special form of bitmap image converter. In this case it uses a very simple "random dither" to determine if a particular pixel is to become a white pixel or a black pixel.

Unlike the "-threshold" or the "-monochrome" operators, or even the variations in the previous section, the selected channels (set with "-channels") are not merged together into single grey-scale channel and dithered as a single unit. Instead "-random-threshold" works on each selected channel completely independently of each other.

Of course using the operator directly will result in a 2 level posterization of the image using a random dither. convert logo.png -random-threshold 0x100% random_posterize.gif

Converting to gray-scale will equalize all the channels in the image, before they are dithered. But as each channel is dithered independent of each other and in a random way, the result is not a bitmap image as you would expect. Instead you will get a splatter of color pixels, especially for mid-tone colors. convert logo.png -colorspace Gray -random-threshold 0x100% \ random_greyscale.gif

Here is the correct way to generate a proper random dithered bitmap image. convert logo.png -colorspace Gray -channel B \ -random-threshold 0x100% -separate random_monochome.gif

Basically what it did was to only dither one channel of the grey-scaled image, and then use the "-separate" channel operator to extract that channel as the final bitmap image. Tricky but effective.

As a special feature for this operator, IM will ensure a bitmap image is generated in the special "-channels" option of 'All' is used. convert logo.png -channel All -random-threshold 0x100% random_all.gif

However please note that any alpha channel will be ignored and lost using this method, as such it is not normally recommended. I myself only discovered this ancient feature by accident from the source code.

Now that you know how to use the operator to correctly generate bitmaps from a color image lets look how the argument effects the range of the dithering. This also shows clearly the 'clumping' of pixels that this dither produces.

A "-random-threshold" setting of '0x100%' will produc