Optimizing Color Quantization for ASP.NET Images

Morgan Skinner
Microsoft Developer Services

May 2003

Summary: Describes how to quantize (recolor) dynamically generated images for ASP.NET pages in order to overcome a limitation of GDI+ in the .NET Framework versions 1.0 and 1.1. This article presents two methods of color depth reduction on images. (13 printed pages)

Applies To:
   Microsoft Framework versions 1.0 and 1.1
   Microsoft Visual C#
   Microsoft ASP.NET

Download the DotNET_Color_Quantization_Code.exe sample file.

Contents

Introduction
Overview of the Problem
Quantization Overview
Palette-based Quantization
Octree-based Quantization
Example Web Site
Conclusion
For More Information
About the Author

Introduction

Most Web sites include some form of graphics, such as the banner heading on the MSDN Web site, and the thumbnail images available for the list of recent headlines. All of these images are static—they are generated by a member of the Web team, recolored to suit the requirements of the Web site, and stored on disk to be used as appropriate.

With ASP.NET it is also possible to create dynamic images—images that are created during the processing of the current Web request. Some uses for this might be to personalize a site or to generate images that conform to a particular visual style, without requiring the services of a Web designer.

The generation of images is relatively simple: Create a surface to draw on, render the appropriate image, and save this to the ASP.NET response stream to be returned to the user.

The only problem with this scenario is the quality of the resulting image. By default, GDI+ will utilize a Web-safe palette when converting a bitmap to an image suitable for a Web page, such as GIF or JPEG. (See For More Information at the end of this article.) The resulting image will be of poor quality and may contain various stray colors from the color reduction algorithm used. This conversion to a Web-safe palette occurs before the image is converted to the output type (such as GIF or JPEG), so even though the output type may support many colors, the image will be generated to use colors from the Web-safe palette.

In addition to the quality of the resulting image, another reason to recolor an image is speed—it's generally faster to download an image from a Web site that uses 1 byte per pixel than 4 bytes per pixel, and not everyone has ADSL. Plus, certain browsers (such as WebTV) have a limited color space, so recoloring is necessary in order to provide a good image to your customers.

The process of recoloring an image to assign a color-reduced palette is termed quantization.

Overview of the Problem

To see the results of the default GDI+ image rendering, I'll present a simple example of image generation, then show the resulting output from a Web page that requests this image.

Let's say you work for an online bank, and as part of the credit card signup process a customer is able to personalize their card by choosing an image from a set of predefined images. You've probably captured the 'customer's name during the signup process, so it would be great to be able to render up a representation of the credit card with their name embossed on the image.

Figure 1. The background bitmap of the (fictitious) MSDN credit card

The image displayed to the user will be created by loading a background bitmap (the MSDN card), then rendering some text onto it to personalize the image. The code below shows how to load an image from the assembly manifest, emboss the name of the customer onto it, and then return this from an ASPX page.

// Obtain a stream over the background image resource
Assembly assem = Assembly.GetExecutingAssembly ( ) ;

using ( Stream   s = assem.GetManifestResourceStream 
                           ( "TestApp.MSDNCard.gif" ) )
{
   // And load the resource into a bitmap
   Bitmap   background = Bitmap.FromStream ( s ) as Bitmap ;

   Bitmap copy = new Bitmap ( background ) ;

   // Now construct a graphics object from the bitmap 
   // so that I can render onto it
   using ( Graphics g = Graphics.FromImage ( copy ) )
   {
      // Get a credit-card-like font
      Font textFont = new Font ( "Lucida Console" , 10 , FontStyle.Bold ) ;

      // Render the name of the card owner
      g.DrawString ( cardholder , textFont , Brushes.Silver , 12 , 130 ) ;
      g.DrawString ( cardholder , textFont , Brushes.White , 13 , 131 ) ;

      // And then the expiry date
      StringFormat   fmt = new StringFormat ( ) ;
      fmt.Alignment = StringAlignment.Far ;

      g.DrawString ( "June 04" , textFont , Brushes.Silver , 
        new RectangleF ( 186 , 130 , 100 , 20 ) , fmt ) ;
      g.DrawString ( "June 04" , textFont , Brushes.White , 
        new RectangleF ( 187 , 131 , 100 , 20 ) , fmt ) ;
   }

   // Return the image
   Response.ContentType = "image/gif" ;

copy.Save ( Response.OutputStream , ImageFormat.Gif ) ;
}

The image in this example is contained within the current assembly. To do this yourself, add an image (or other resource) into your project, and set the Build Action to Embedded Resource. You can access the Build Action property from the Property window for any file type in Visual Studio .NET.

I then draw some text onto the image. Here, I've created a crude embossed look by drawing the text in silver first, then offsetting by a pixel in the X and Y axes and drawing the text again in white. This produces a pseudo embossed look, certainly good enough for this example.

When this image is returned to an ASP page (or saved to disk), the output is color reduced using a Web-safe palette. This results in the following image, regardless of the output type (GIF, JPEG, and so on).

Figure 2. A dithered image returned using a default palette

As you can see from the callout in this figure, the resulting image is very "grainy." This is caused by the dithering of the image that is required to reduce it to 256 colors, plus the fact that the resultant image utilizes the Web-safe palette rather than a custom palette of 256 colors.

What we need is a way to reduce the color depth of an image to 256 colors (or less!), and produce a GIF that contains palette information specific to the image. This process is generally termed quantization.

Quantization Overview

The process of quantizing an image is straightforward to describe. For each pixel in the source image, lookup or compute a value that will define the color of that pixel in the destination image. When reducing color depth to 256 colors, this usually means that the resulting "color" is an index into a palette.

For example, say we have an image that contains 5000 discrete colors, and we want to reduce this to a 256-color GIF. There will obviously be some loss of color in the resulting image, and a good quantization algorithm seeks to minimize these losses to produce an acceptable image.

As a first step, you could take the first 256 discrete colors in the source image, and use these as the palette for the entire image. Any subsequent colors would be mapped into these initial 256. This method doesn't take into account the frequency of colors in the image, so it will often produce poor results. If the 257th color in the image were used for 50 percent of the image, it would be best to ensure that this color was represented unchanged in the destination image.

At the other end of the scale, we could create an array with 32 KB slots, and produce a cumulative count of pixels in each slot. Then we would have to decide which of the pixels to promote to the output palette, and which to convert into palette colors. We might pick the most frequently used colors first, and then the next frequent, and so on until the palette was full.

In either case, there exist two main parts to the algorithm. The first is to iterate over the source, the second is to quantize the pixels and produce the resulting image and color palette. Armed with this knowledge, we can create the first part of the algorithm, which will traverse the image a pixel at a time, then plug in different quantizers as appropriate.

A Bit About Bitmaps

In order to produce our algorithm, we need to know a little about the internal (memory) representation of a bitmap. In this example I'll only consider images with either 8 BPP (bits per pixel) or 32 BPP. An 8 BPP image has a byte for each pixel, so an image of 16&times16; pixels would comprise 256 bytes. A 32 BPP image of the same size would consist of 1024 bytes, as each pixel consists of 4 bytes. Both of these ignore the overhead associated with a bitmap, such as the dimensions of the bitmap.

In the dark ages of computing (well, less colorful!), a display adapter might have only 256 possible colors (my second computer did in 1983), so a pixel color would be identified by an individual byte. Today, however, every man and his dog has an adapter capable of 32 KB colors or more, so a byte is now used to represent an index into a palette of colors. Writing an 8 BPP image is therefore also a two-stage process—calculate the palette index of each pixel in the source bitmap, plus set the palette entries.

Figure 3. A 32-BPP image vs. an 8-BPP image

A 32 BPP image consists of 8 bits for the red, green, and blue components of the color, plus an extra 8 bits of "alpha" channel information. This alpha component determines the transparency of the pixel, where a value of 255 is totally opaque, and a value of zero is totally transparent. We'll not deal with this component in the rest of this example, but you can (for instance) choose any color with an alpha component less than a predefined value to be transparent in the resulting GIF.

To loop through the bytes in the source image will require some unsafe code, as we'll be using pointers to speed up the process. There is a GetPixel function on the Bitmap class that we could use; however, this function isn't fast enough for iterating through all pixels in an image.

The following code will loop through all pixels in the source image, and is used in the example code as a first pass through the data.

BitmapData   sourceData = null ;

try
{
   // Lock the source data into memory
   sourceData = bmp.LockBits ( new Rectangle ( 0 , 0 , width , height ) , 
                               ImageLockMode.ReadOnly , 
                               PixelFormat.Format32bppArgb ) ;

   // Define the source data pointers. The source row is a byte to
   // keep addition of the stride value easier (as this is in bytes).
   byte*   pSourceRow = (byte*)sourceData.Scan0.ToPointer ( ) ;
   Int32*   pSourcePixel ;

   // Loop through each row
   for ( int row = 0 ; row < height ; row++ )
   {
      // Set the source pixel to the first pixel in this row
      pSourcePixel = (Int32*) pSourceRow ;

      // And loop through each column
      for ( int col = 0 ; col < width ; col++ , pSourcePixel++ )
      {
         // Do something with *pSourcePixel
      }

      // Add the stride to the source row
      pSourceRow += sourceData.Stride ;
   }
}
finally
{
   // Ensure that the data is unlocked
   bmp.UnlockBits ( sourceData ) ;
}

Looping through the image bits is fairly simple—a pointer is set to the start of the image in memory and is incremented onto the next pixel. After every row I add the value of the "stride"' to the row pointer, then iterate over the columns again.

The '"stride"' of a bitmap is the number of bytes each row takes up; this may or may not be the same as the number of pixels in the image. As an example, an 8 BPP image that is 13 bits wide may have a stride of 16, as this is a nice round number for a 32-bit machine.

Producing the Output Bitmap

The code to produce the output bitmap is very similar to that shown above for looping over the input bits in order to generate the color palette.

In this instance we now loop over each pixel in both the source and destination bitmaps, and assign the computed palette index of the source pixel to the destination pixel. When that is done we should have a fully quantized image, ready for display to the user. The code snippet below is a simplified version of the algorithm used in the sample that accompanies this article.

for ( int y = 0 ; y < height ; y++ )
   for ( int x = 0 ; x < width ; x++ )
      destinationPixel[x,y] = Quantize ( sourcePixel[x,y] ) ;

The actual algorithm used isn't quite as simple as the above, because there are faster ways to run through a bitmap than treating it as a two-dimensional array.

Now that all the pixels have been converted, there is one last thing to do. We need to associate the palette with the newly generated image, so that the output image appears correctly based on the quantization that has occurred.

Palette-based Quantization

The first example I'll describe is based on a known palette. Many Web sites have a set of custom colors that are used for branding purposes (such as the blues used on www.gotdotnet.com). What we want here is to produce an image and then recolor the image using a palette that has been generated in some manner. In this instance I've constructed a palette for the fictitious MSDN credit card using an image editor.

The palette-based algorithm works by choosing the nearest color in the output palette for each pixel in the source image.

This method has the benefit that it's easy to understand; however, it is not adaptive in that you are limited by the input palette. If your image has wildly differing colors from the palette, your image quality will suffer.

To convert a given pixel from the source color to the destination palette index, I have written a method that scans through the palette for a color whose RGB value is nearest the source color. The guts of the algorithm are shown below.

int   leastDistance = int.MaxValue ;
int red = pixel->Red ;
int green = pixel->Green;
int blue = pixel->Blue;

// Loop through the entire palette, looking for the closest color match
for ( int index = 0 ; index < _colors.Length ; index++ )
{
   // Lookup the color from the palette
   Color   paletteColor = _colors[index];
   
   // Compute the distance from our source color to the palette color
   int   redDistance = paletteColor.R - red ;
   int   greenDistance = paletteColor.G - green ;
   int   blueDistance = paletteColor.B - blue ;

   int      distance = ( redDistance * redDistance ) + 
                       ( greenDistance * greenDistance ) + 
                       ( blueDistance * blueDistance ) ;

   // If the color is closer than any other found so far, use it
   if ( distance < leastDistance )
   {
      colorIndex = (byte)index ;
      leastDistance = distance ;

      // And if it's an exact match, exit the loop
      if ( 0 == distance )
         break ;
   }
}

This uses a simple least-squares algorithm to find the nearest color match, and also uses a Hashtable to store the color once found, so that the palette needs to be traversed only for colors that have not already been quantized. This could be expensive (in terms of memory) for an image with a large number of colors, but without some form of cache the algorithm can be very slow.

Octree-based Quantization

The palette-based algorithm is fairly fast, but suffers from one drawback—it is not an adaptive algorithm. An Octree, on the other hand, can deal with any image, regardless of the number of different colors in the image. It can produce reasonable results with little degradation when converting from a high number of colors to something more reasonable. The downside is that it's a more computationally expensive algorithm, which means that it will typically take longer than the palette algorithm to quantize the same image.

The name Octree comes from the data structure that is used to represent the colors of the image. It is made up of a number of nodes, each of which has up to 8 children.

Say you have a color value (#6475D6) that is to be quantized. The color is split into individual red, green, and blue components, and then successive bits are shifted out of the red, green, and blue values in order to produce a number between 0 and 7. This value determines which leaf will be traversed from the current node when building the tree, and also when searching for the nearest color value.

The result shown above is a combination of the bits for each of the constituent color values, and is computed for each bit in the RGB color as follows.

result = red | green<<1 | blue<<2 ;

The bits are traversed from most to least significant, so in my example I shift off the most significant bits (in bit 7), then the next significant (bit 6), and so on. For the above example, the nodes traversed in the tree are as follows.

Figure 4. Octree traversal for color #6475D6

As previously explained, when a color is inserted into an Octree, the nodes are traversed. When a leaf node is found, the count of pixels of this particular color is incremented in the node, and the red, green, and blue components are added to the R, G, and B values within the node. These numbers are used to produce an average color based on dividing each color value by the number of pixels of that color.

Without any pruning, you would end up with a tree that had as many leaf nodes as there were discrete colors in the input image. Instead of permitting the tree to grow ad infinitum, an Octree can have a predetermined number of leaves that form the color palette once the entire image has been quantized.

Discussions of Octrees have popped up on MSDN previously, so I've reused the code from Jeff Prosise's Wicked Code article from the October 1997 issue of Microsoft Systems Journal (MSJ). I've converted Jeff's code from Visual C++ to C# for this example, and along the way I've made a few modifications.

The main modification I made to Jeff's Octree algorithm was to improve performance of the quantization loop. In my version I cache the result of each quantize call, and this can speed up the process if there are a number of pixels all of the same color adjacent to one another. Each iteration around the loop I check the current pixel color, and if it matches the last pixel quantized I can short-circuit the code just to return the previous result.

Example Web Site

The accompanying code for this article includes both the palette- and Octree-based quantization algorithms. The results of the quantization are displayed alongside the original image and one that has been quantized in GDI+ (which appears very grainy). (Note that I have omitted the original image from the comparison in Figure 5 below, but you can see it in the code example.)

To produce the images, I have written a simple ASPX page for each image type, which includes code similar to the following.

  public void RenderImage ( )
{
   using ( Bitmap image = Generator.GenerateImage ( "Octree Quantized" ) )
   {
      OctreeQuantizer   quantizer = new OctreeQuantizer ( 255 , 8 ) ;

      using ( Bitmap quantized = quantizer.Quantize ( image ) )
      {
         Response.ContentType = "image/gif" ;

         quantized.Save ( Response.OutputStream , ImageFormat.Gif ) ;
      }
   }
}

This produces a quantized image of the credit card using the Octree quantizer, and sets the response type to image/gif. This is included in the example Web site page as an img tag: <img src="OctreeQuantization.aspx">. Each ASPX page simply includes a call to the RenderImage function above.

The results of the quantization process are shown below.

Quantization Type	Image	Image Size (in KB)
None (default GDI+)		21342
Palette-based		16748
Octree-based		16744

Figure 5. Comparison of quantization results

The palette and Octree results are 20 percent smaller than the default GDI+ rendering using a Web-safe palette, and the image quality is far superior. The palette- and Octree-based images are different because the images contained slightly differing text. Your results may vary based on the size of the image, but generating images that are smaller yet better has to be worthwhile.

Conclusion

With ASP.NET it is feasible to personalize a site for an individual user, or set of users, by generating images that are subsequently displayed on the Web site. There are a number of reasons why this would be advantageous. For example, you might need to generate button captions based on the language setting of the current user. Rather than generating a large number of images that are essentially the same, except for the text, it would be possible to create a generic button image, and render the text at runtime.

This article has presented two methods of quantization for .NET, but there are many other algorithms available, so feel free to experiment. The code has been written to be extended, so you can plug in your own quantizer by deriving from the Quantizer class and overriding the QuantizePixel and GetPalette methods, and optionally the InitialQuantizePixel method. The code provides documented examples of how to plug in your own algorithm.

For More Information

• Jeff Prosise, Wicked Code (Microsoft Systems Journal)
• What Is Color Quantization FAQ
• Robert Hess, The Safety Palette
• Radiosity: A Programmer's Perspective, Wiley Professional 1994 (ISBN 0-471-30444-1). This book has been out of print for a number of years, but copies can be found online and a CD version is also available.

About the Author

Morgan is an Application Development Consultant working for Microsoft in the UK, specializing in Visual C#, controls, WinForms, and ASP.NET. He's been working with .NET since the PDC release in 2000, and liked it so much he joined the company. His home page is http://www.morganskinner.com, where you'll find links to some of the other articles he has written. In his spare time (which there isn't much of) he fights weeds on his allotment and enjoys the odd Cornish pasty.

© Microsoft Corporation. All rights reserved.