Much of the "World Wide Wait" is spent downloading poorly encoded images. Anything that helps make images smaller is a boon.
GIF (Graphics Interchange Format) files are very popular on the Internet for the transmission of raster graphic web images. GIF images are independent of the hardware used in their creation or display. Also, the GIF format specification has LZW compression built in, allowing for very compact images. These features make GIFs ideal for transmitting over the Internet.
Windows DIBs (Device Independent Bitmaps) are also a commonly used image format, not so much on the Internet, but definitely on Windows platforms. What makes DIB files unique is the ease with which they can be created and drawn on using the Win32 GDI (Graphics Device Interface) calls. Since Windows machines are being increasingly used to run web servers (and significantly, Microsoft's own web server) it seems prudent to examine methods to create GIF files from Windows palette-indexed DIB files. That is the subject of this article.
For those who are interested, I also present code that can be used from Microsoft's web server in the form of a scriptable COM object (see the sidebar.) This object can then be used directly from Microsoft's Active Server Pages, which are much like HTML with embedded Visual Basic scripting. You can also use the COM object from Windows Scripting Host, the new COM-based command shell language for the Windows platform.
GIF and DIB Formats
A GIF file consists of several parts, but the two most important are the color table and the image data. The color table, also known as a palette, is a sequence of bytes representing red-green-blue color triplets. The color table can have at most 256 entries, thus limiting the number of different colors that can be displayed in a GIF file. The image data for palette-based files consists of indexes into the color table, one index for each pixel in the image. In GIF files this image data is arranged as a sequence of sub-blocks, the maximum size of each sub-block being 255 bytes, or indexes. Pixel indexes within each sub-block are arranged in order from left to right, then top to bottom. (Each sub-block in a GIF can contain more than one row.) Each index must be within a range, starting at zero, that conforms to the size of the color table.
The sequence of indexes is encoded using the LZW compression algorithm. It is this combination of a color table and compressed image pixels that can make GIF files quite small. GIF files also provide support for interlacing, which allows for the progressive display of pictures over low bandwidths; and for transparency information. More information on the GIF specification can be found at http://members.aol.com/royalef/gif89a.txt.
DIB files can also be palette-indexed raster images, but without the image data compression. (Strictly speaking, DIB files can be run-length encoded, but that is beyond the scope of this article.) Like GIFs, DIB files also contain a color table and image data, but the layouts are of course different. Since the Windows DIB structure has been fairly well documented, I do not focus on the specifics here. Readers wishing to know more can consult [1].
A Windows DIB Class
I have created a class CImage (Figure 1), which is basically a wrapper class around a handle (an HBITMAP) to a Win32 DIB. CImage contains this handle as a private data member. I avoided using MFC because of the run-time overhead and memory footprint of the MFC DLLs. Besides, MFC has no DIB class. CImage offers several fairly straightforward methods to create, load, or save a DIB, and to get information regarding its width and height. The class includes a conversion operator to an HBITMAP so that it can be easily used in Win32 GDI calls. For example,
... HDC hdc; Cimage im; If (!im.Create(32,32,8)) Return; hdc = CreateCompatibleDC(NULL); HBITMAP hOldBmp = SelectObject(hdc, im); ...The really interesting methods in this class are the member functions that manipulate and alter the color table, such as SetColorTable (Figure 2.). These functions work with the help of two more utility classes, CImageColorTable and CImagePalette (not shown). Class CImageColorTable is a wrapper around an array of Win32 RGBQUAD structures, while CImagePalette is a wrapper around a handle to a Win32 palette (an HPALETTE).
CImage contains a method called OptimizeForSize, which will prepare the DIB to be converted to the smallest possible GIF file. The smallest possible GIF is achieved when the palette contains the fewest colors required to represent all the colors in the image. For instance, an image containing two colors can represent the color of each pixel with one bit, whereas an image with 117 colors would require seven bits per pixel. But suppose the image has 117 colors in its color table but uses only two of them. Not only is each pixel stored as an unnecessarily large number of bits; the overhead of all the unused colors in the color table becomes quite significant. Eliminating unused colors can save a lot of space. Quite often simple images produced by script commands can be optimized this way.
OptimizeForSize thus performs the following operations:
1) It iterates through all the DIB image pixels and constructs a set of the actual palette indexes used and the actual RGB colors of these palette indexes. The latter is necessary because an image's palette may contain the same color at two different locations. Iterating through an image's pixels is an expensive operation, especially if, for each pixel, the RGB colors must be looked up in the set of colors used. However, if the pictures are relatively simple, and pixels usually occur in runs of similar color, the process can be sped up by using a simple cache of the last RGB color found.
2) There are two conditions that require remapping of the image pixels to a new, smaller set of RGB colors:
- if the number of palette indexes used within the image data is less than the number of colors in the image's palette
- if the number of RGB colors used is less than the number of palette indexes used
This remapping process occurs in the method SetColorTable. (Note that remapping the pixels in this way should cause no loss in picture quality. SetColorTable can force a new palette into a picture, but it does not implement dithering, a process which inherently affects image quality.) SetColorTable then looks up each color in the new palette with the Win32 API GetNearestPaletteIndex.
Listing 1, test.cpp, shows how the CImage class may be used to write fairly simple programs to manipulate DIB files.
A Simple GIF File Class
I have also created a class CImageGif for GIF files. This class is not shown here, but it, as well as all the other source code, is available on the CUJ ftp site (see p. 3 for downloading instructions). CImageGif contains just enough methods to create and save GIF files. It is intended simply for use in converting images to GIF files. The implementation is based on the gd library by Thomas Boutell, which can be obtained at http://www.boutell.com/gd. This library is based on code drawn from part of the pbmplus package.
Future Improvements
Not all DIBs are palette based, especially those of a photographic nature. To work with these DIBs, the CImage class would need the ability to perform color reduction, also known as color quantization. Color quantization would be necessary to reduce the number of colors in the image to 256 or fewer, so the image could be saved as a GIF file. Such a feature would make the control much more useful.
Reference
[1] Win32 SDK. Search for DIBSECTION.
Lukas Knutsson has been using C++ since 1992 and now works for Spray Interactive Media Agency in Stockholm, Sweden, as the in-house C++ programmer on many different web sites that the company has created. Try www.electrolux.se for example and you'll see images that have all gone through the code of this article. When not hacking on Linux or Win32 Lukas enjoys going skydiving and has made over 4000 jumps. He can be contacted at lukas@spray.se.