Indexed color

In computing, indexed color is a technique to manage digital images' colors in a limited fashion, in order to save computer storage, while speeding up display refresh and file transfers. It is a form of vector quantization compression.
When an image is encoded in this way, color information is not directly carried by the image pixel data, but is stored in a separate piece of data called a color lookup table or palette: an array of color specifications. Every element in the array represents a color, indexed by its position within the array. For color information, each image pixel then specifies only its index into the palette.
This technique is sometimes referred as pseudocolor or indirect color, as colors are addressed indirectly.

History

Early graphics display systems that used 8-bit indexed color with frame buffers and CLUTs include Shoup's SuperPaint and the video frame buffer described in 1975 by Kajiya, Sutherland, and Cheadle. These supported a palette of 256 RGB colors. SuperPaint used a shift-register frame buffer, while the Kajiya et al. system used a random-access frame buffer.
A few earlier systems used 3-bit color, but typically treated the bits as independent red, green, and blue on/off bits rather than jointly as an index into a CLUT.

Palette size

The palette itself stores a limited number of distinct colors; 4, 16 or 256 are the most common cases. These limits are often imposed by the target architecture's display adapter
hardware, so it is not a coincidence that those numbers are exact powers of two: 2² = 4, 2⁴ = 16 and 2⁸ = 256. While 256 values can
fit into a single 8-bit byte, multiple pixel indices with 16 or fewer colors can be packed together into a single byte. Sometimes, 1-bit values can be used, and then up to eight pixels can be packed into a single byte; such images are considered binary images and not an indexed color image.
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 available color. Some machines, such as the MSX series, had the transparent color reserved by hardware.
Indexed color images with palette sizes beyond 256 entries are rare. The practical limit is around 12 bits per pixel, 4,096 different indices. Useful direct RGB high color modes can be used from 15 bpp and up.
If an image has many subtle color shades, it is necessary to select a limited repertoire of colors to approximate the image using color quantization. Such a palette is frequently insufficient to represent the image accurately; difficult-to-reproduce features such as gradients will appear blocky or as strips. In those cases, it is usual to employ dithering, which mixes different-colored pixels in patterns, exploiting the tendency of human vision to blur nearby pixels together, giving a result visually closer to the original one.
Here is a typical indexed 256-color image and its own palette :

Colors and palettes

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

Early color techniques

Many early personal and home computers had very limited hardware palettes that could produce a very small set of colors. In these cases, each pixel's value mapped directly onto one of these colors. Well-known examples include the Apple II, Commodore 64 and IBM PC CGA, all of which included hardware that could produce a fixed set of 16 colors. In these cases, an image can encode each pixel with 4-bits, directly selecting the color to use. In most cases, however, the display hardware supports additional modes where only a subset of those colors can be used in a single image, a useful technique to save memory. For instance, the CGA's 320×200 resolution mode could show only four of the 16 colors at one time. As the palettes were entirely proprietary, an image generated on one platform cannot be directly viewed properly on another.
Other machines of this era had the ability to generate a larger set of colors, but generally only allowed a subset of those to be used in any one image. Examples include the 256-color palette on Atari 8-bit machines or the 4,096 colors of the VT241 terminal in ReGIS graphics mode. In these cases it was common for the image to only allow a small subset of the total number of colors to be displayed at one time, up to 16 at once on the Atari and VT241. Generally, these systems worked identically to their less-colorful brethren, but a key difference was that there were too many colors in the palette to directly encode in the pixel data given the limited amount of video memory. Instead, they used a colour look-up table where each pixel's data pointed to an entry in the CLUT, and the CLUT was set up under program control. This meant that the image CLUT data had to be stored along with the raw image data in order to be able to re-produce the image correctly.

RGB

Hardware palettes based on component video colors such as YPbPr or the like were generally replaced in the mid 1980s by the more flexible RGB color model, in which a given color can be obtained by mixing different amounts of the 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, in this model digital-to-analog converters can generate the colors — simplifying the hardware design — while the software can treat the number per levels used abstractly and manage the RGB colors in a device-independent fashion. With colors stored in RGB format within the palettes of indexed image files, any image can be displayed on any such system, regardless of the color depth used in the hardware implementation.
Today, display hardware and image file formats that deal with indexed color images almost exclusively manage colors in RGB format, the de facto standard encoding being the so-called truecolor or 24-bit RGB, with 16,777,216 different possible colors. However, indexed color images are not genuinely constrained to a 24-bit RGB color encoding; 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 equal to or less than 256. When using RGB, the TIFF and PNG file formats can optionally store the RGB triplets with a precision of 16-bit yielding a total of 48 bits per pixel. A proposed extension to the TIFF Standard allows non-RGB color palettes, but this was never implemented in software due to technical reasons. The color map table of the BMP file format indexed color mode stores its entries in BGR order rather than RGB, and has an additional unused byte for padding to conform to 32-bit word alignment during processing, but it is essentially still a 24-bit RGB color encoding.

Pixel bits arrangements

Except for very low resolution graphic modes, early home and personal computers rarely implemented an "all-pixels-addressable" design - 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 creating difficulty for the people writing graphics programs. A pixel's bits in indexed-color, all-pixel-addressable images are not always contiguous in video memory or image files Some video hardware, such as the 16-color graphic modes of the Enhanced Graphics Adapter and Video Graphics Array for IBM PC compatibles
or the Amiga video buffer
are arranged as a series of bit planes, in which the related bits of a single pixel are split among several independent bitmaps. Thus, the pixel bits are conceptually aligned along the 3D Z-axis.
Early image file formats, such as PIC, stored little more than a bare memory dump of the video buffer of a given machine.
Some indexed-color image file formats such as Graphics Interchange Format allow the image's scan lines to be arranged in interleaved fashion, which allows a low resolution version of the image to appear on screen while it is still downloading, so that the computer user can gain an idea of its contents during the seconds before the whole image arrives. Here is an example of a typical vertically interleaved download in four steps:
As seen here, the image has been divided into four groups of lines: group A contains every fourth line, group B contains lines immediately following ones in group A, group C likewise contains the lines immediately following those in group B, and group D contains the remaining lines, which are between group C lines and group A lines. These are stored into the file in the order A, C, B, D, so that when the file is transmitted the second received group of lines lie centered between the lines of the first group, yielding the most spatially uniform and recognizable image possible, composed of only two of the groups of lines. The same technique can be applied with more groups, in which case at each step the next group to be sent contains lines lying at or near the centers of remaining bands that are not yet filled with image data. This method, with four or eight groups of lines, was commonly used on the early World Wide Web during the second half of the 1990s. Rather than leaving the background showing as in the illustration above, the partial image was often presented on screen by duplicating each line to fill the space below it down to the next received image line. The end result was a continuous image with decreased vertical resolution that would increase to full resolution over a few seconds as the later parts of the image data arrived.