Indexed color

From Wikipedia, the free encyclopedia

A 2-bit indexed color image. The color of each pixel is represented by a number; each number (the index) corresponds to a color in the color table (the palette).

In computing, indexed color is a technique to manage digital images' colors in a limited fashion, in order to save computer's memory and file storage, while speeding up display refresh and telecom transfers. When an image is encoded this way, the color information is not directly carried by the image pixel data, but it is stored into a separate piece of data called a palette: an array of color elements, in which every element, a color, is indexed by its position within the array. This way, each pixel does not contain the full information to represent its color, but only its index into the palette. This technique is sometimes referred as pseudocolor^[1] or indirect color,^[2] as colors are addressed indirectly.

[edit] The palette size

Main article: Palette (computing)

The palette in itself stores a very limited number of distinct colors, up to 4, 16 or 256 are the most common cases. These limits are often imposed by the target architecture's display adapter hardware to which the indexed color image is intended to, so it is not a surprise that those numbers are actually exact powers of two (the binary code): 2² = 4, 2⁴ = 16 and 2⁸ = 256. While 256 values can be fitted into a single 8-bit byte (and then a single indexed color pixel occupies a single byte), pixel indices ranging 16 values (4-bit, a nibble) and lesser number of colors can be packed together into a single byte (two nibbles per byte if 16 colors are employed and four 2-bit pixels per byte if using 4 colors). Sometimes, a mere 1-bit per pixel (bpp), 2-color values can be used and then up to eight pixels can be packed into a single byte, but when such colors are black and white, then the image is considered a binary image (sometimes referred as a bitmap or bilevel image) and not an indexed color image.

In order to save even more space, some indexed color image files can store only the effectively used colors in a given image and not the whole of the palette entries available for the pixel depth employed. Thus, it is not rare to find odd palette sizes of any number between 3 and 255 entries instead of always 256 (for 8 bpp) in such files.

If simple video overlay is intended through a transparent color, one palette entry is specifically reserved for this purpose, and it is discounted as an actual available color. Some machines, as the MSX series, had the transparent color reserved by hardware.^[3]

Indexed color images with palette sizes beyond 256 entries are rare. The practical limit is around 12-bit per pixel, 4,096 different indices. To use indexed 16 bpp or more does not provide the benefits of the indexed color images' nature, due to the color palette size in bytes may be then greater than the raw image data in itself. Also, useful direct RGB Highcolor modes can be set from 15 bpp and up.

If a given real life photograph or image has many subtle color shades, the limited repertoire of colors of the image palette can not be sufficient enough to represent the image accurately, due to gradients and other shadings can appear blocky or as strips (banding). In those cases, it is usual to employ dithering: patterned or trembling color pixel arrangements to reduce the banding effect and give a result closer to the original one.

Here is a typical indexed 256-color image and its own palette (shown as a rectangle of swatches):

[edit] Colors and palettes

See also List of palettes

How the colors are encoded within the color palette map of a given indexed color image depend also on the target platform.

[edit] Early color techniques

Many early personal and home computers had very limited proprietary color palettes made up of different color spaces implemented directly in its own hardware, so the color indices were imposed by the manufacturer, as those of the Apple II and the Commodore 64. This had the advantage that the mapping between the pixel indices and their correspondent colors was implicit, and then rarely (if ever) the color table was stored as a separate file or as part of an image file.

As display hardware evolved, available hardware palettes grew beyond the maximum single pixel depth (the number of different values a pixel can hold), so the indexed color images needed to select a limited repertoire of colors from a given wider hardware palette. Thus, the programs must load the image colors into the display's color hardware registers (or perform other special settings) before loading the actual image pixels into the video memory, and then the image palette in itself (or the values to set the actual screen colors) must be saved along with the raw image data.

[edit] RGB

Hardware palettes based on composite video colors such as YPbPr or the like tended to be replaced in the mid 1980's by the more flexible RGB color model, in which a given color can be obtained by mixing different amounts of three primary colors red, green and blue. Although the total number of different colors depends on the number of levels per primary, and on a given hardware implementation (while a 9-bit RGB provides 512 combinations, a 12-bit RGB provides 4,096, and so on), this model lets to implement Digital-to-Analog Converters (DAC) to generate the colors simplifying the hardware design, while abstracting of the number per levels used the software could manage the RGB colors in a device-independent fashion. With colors stored in RGB format within the palettes of indexed image files, by appropriate software any image could be displayed (through appropriate transformations) into any of such systems.

Today, display hardware and image file formats that deal with indexed color images manage almost exclusively the colors in the RGB format, being the de-facto standard encoding the so-called truecolor or 24-bit RGB, with 16,777,216 different possible colors. In every case, there is no constrain to 24-bit RGB color encoding of colors for indexed color images; the image palettes can hold any type of color encoding. For example, the PDF file format does support indexed color in other colorspaces, notably CMYK, and Adobe Distiller by default will convert images to indexed color whenever the total number of colors in an image is less or equal than 256. When using RGB, the TIFF file format stores the RGB triplets with a precision of 16-bit, 65,536 levels per component (48-bit RGB) for the color map; it also allows^[4] to store the palette's colors not in RGB, but this last feature is not in spread use. Every color entry in the color map table of the BMP file format indexed color mode is stored in BGR order rather than in RGB and has an additional unused byte for padding to align them into 32-bit words for better memory alignment during processing, but is still a 24-bit RGB color encoding.

[edit] Pixel bits arrangements

Except for very low resolution graphic modes, early home and personal computers rarely employed the "all-pixels-addressable" philosophy, that is, the ability to change a single pixel to any of the available colors independently. Their limitations came from employing separate color attribute or color RAM areas, leading to attribute clash effects. Also, the pixel bits and/or the scan lines of the video memory were commonly arranged in odd ways convenient for the video generator hardware, but sometimes difficult for the programs. Early image file fortmats, as PIC, stored little more than a bare memory dump of the video buffer of a given machine.

A pixel's bits in indexed-color, all-pixel-addressable images are not always contiguous (or chunky arranged) in video memory or image files. Some video hardware, as Enhanced Graphics Adapter (EGA) and Video Graphics Array (VGA) for IBM PC compatibles 16-color graphic modes^[5] or the Amiga video buffer^[6] are arranged as a series of bit planes (in a configuration called planar), in which the related bits of a single pixel are stacked along several and independent bitmaps. Thus, the pixel bits are conceptually aligned along the 3D Z-axis. This concept it is not the same as, although related to, that of pixel depth.

Also, some indexed-color image file formats as Graphics Interchange Format (GIF) allow to arrange the image's scan lines in interleaved fashion (not linear vertical order), which allowed the image to appear on screen little by little while it is still downloading with low-speed modems, and to catch an idea of its contents during the seconds before the whole image arrives. Here is an example of a typical interleaved download in four steps:

[edit] Advantages

Indexed color saves a lot of memory/storage space and/or transmission time: using truecolor, each pixel needs 24 bits, or 3 bytes. A typical 640×480 VGA resolution, truecolor uncompressed image needs 640×480×3 = 921,600 bytes (900 KiB). Limiting the image colors to 256, every pixel needs only 8 bits, or 1 byte each, so the example image now need only 640×480×1 = 307,200 bytes (300 KiB), plus 256×3 = 768 additional bytes to store the palette map in itself (assuming RGB), approx. one third of the original size. Smaller palettes (4-bit 16 colors, 2-bit 4 colors) can pack the pixels even more (to 1/6 or 1/12), obviously at cost of color accuracy.

Indexed color has been widely used in early personal computers and display adapters' hardware to reduce costs (mainly, fewer then-expensive RAM chips) but also for convenient image management with limited-power CPUs (of the order of 4 to 8 MHz) and file storage (cassette tapes and low density floppy disks). Notable computer graphics systems extensively (or even exclusively) using pseudocolor palettes in the early 1990's include EGA and VGA (for the IBM PC compatibles), the Atari ST and Amiga's OCS and AGA.

Image files exchanged over the Compuserve net in the early 1990's were encapsulated in the GIF format. Later, the Internet HTML web pages still used the GIF along with other indexed color-supporting file formats such as PNG, to exchange limited-color images quickly and store them in limited storage space.

Most image file formats that support indexed color images also commonly support some compression scheme, enhancing their ability to store the images in smaller files.

Interesting colorized and artistic effects can be easily achieved by playing with the color palette of the indexed color images, for example to produce colorized sepia tone images. Due to the separate nature of the associated palette element of the indexed color images, they are ideal to remap grayscale images into false color ones through the use of false color palettes.

Simple video overlay can be achieved easily through the transparent color technique.

By manipulating the color hardware registers (Color look-up table or CLUT) of the display adapter in the indexed color graphic modes, interesting full-screen color-animation effects can be achieved without the need of entirely redrawing the image, that is, at low CPU time cost; a single change of the register values affects the whole screen at once. Color-map animation is extensively used in the demoscene.

[edit] Disadvantages

The main disadvantage of using indexed color is the limited set of simultaneous colors per image. Small 4- or 16-color palettes are still acceptable for little images (icons) or very simple graphics, but to reproduce real life images it becomes nearly unuseful. Some clever tricks, as color quantization, anti-aliasing and dithering combined together can approximate indexed 256-color images to the original one up to an acceptable level.

For comparison, here are the same image rendered with a 4-, 16-, and 256-color size with adaptive palettes (the best picked selected colors) without dithering, (full truecolor version at top):

Indexed color images are heavily dependent of their own color palettes. Except for a few and well known common fixed-color palettes (as that of the Color Graphics Adapter—CGA), raw image data and/or color map tables cannot be reliably exchanged between different image files without some kind of intermediate mapping. Also, if the original color palette for a given indexed image is lost, it can be near impossible to restore it. Here is an example of what happens when an indexed color image (the previous parrot) has associated an incorrect color palette:

Indexed color graphic modes for display adapters have the 16- or 256-color limit imposed by hardware. Indexed color images with rich but incompatible palettes can only be accurately displayed one at once, as in a slideshow. When it is necessary to show multiple images together, as in a mosaic of thumbnails, usually a common or master palette is used, which encompasses as many different hues as possible into a single set, thus limiting even more the overall accurate color availability.

Here is a mosaic of four different indexed color images rendered with a single shared master palette of 6-8-5 levels RGB plus 16 additional grays. Note the limited range of colors used for every image, and how many palette entries left unused.

Many indexed color display devices do not reach the 24-bit limit for the full RGB palette. The VGA for IBM PC compatibles, for example, only provides a 18-bit RGB with 262,144 different possible colors in both 16- and 256- indexed color graphic modes.

Some image editing software allow to apply a gamma correction over the colors of the palette for indexed color image files. In general for files, to apply a gamma correction directly to the color map is a bad practice, due to the original RGB color values are lost. Always it is better to apply the gamma correction through the display hardware (the most of modern display adapters support this feature), or as an active intermediate step of the rendering software through some kind of color management, which preserves the original color values. Only when the indexed color images are intended to systems that lacks any kind of color calibration abilities and they are not intended to be cross-platform interchanged, the gamma correction may be applied over the color table in itself.

[edit] Image file formats supporting indexed color

These are some of the most representative image file formats that support indexed color modes. Some of these support other modes (e.g. truecolor), but only the indexed color modes are listed here.

* Native support for proprietary compression schemes.

** RLE with optional proprietary Delta-leaps.

[edit] Notes

1. ^ Charles A. Poynton (2003). Digital Video and HDTV: Algorithms and Interfaces. Morgan Kaufmann. 
2. ^ http://www.cs.binghamton.edu/~reckert/class5b_01.PDF Computer Graphics, Prof. R. Eckert, Lect. #5, February 2001, Binghampton U., N.Y.
3. ^ http://emu-docs.org/VDP%20TMS9918/Datasheets/TMS9918.pdf Online datasheet for the Texas Instruments TMS9918 Video Chip used in the MSX.
4. ^ The TIFF image file format specification
5. ^ Richard Wilton, Programmer's Guide to PC & PS/2 VIDEO SYSTEMS, 1987, Microsoft Press. ISBN 1-55615-103-9
6. ^ Inc. Commodore-Amiga, Amiga Hardware Reference Manual, 1991, Addison-Wesley. ISBN 0201567768

[edit] References

• Julio Sanchez and Maria P. Canton (2003). The PC Graphics Handbook. CRC Press. ISBN 0849316782.

[edit] See also

• Palette (computing)
• Color depth
• Palette entry
• Color Look-Up Table
• List of palettes
• Image file formats
• Computer display
• List of home computers by video hardware

[edit] External links

• Introduction to indexed color images