3.

1 Graphics/Image Data Types 69

6. Based on the Euclidean distance between a pixel RGB value and the box cen-
ters, assign every pixel to one of the representative colors. Replace the pixel by
the code in a lookup table that indexes representative colors (in the table, each
representative color is 24-bits—8 bits each for R, G, and B).
This way, we might have a table of 256 rows, each containing three 8-bit values.
The row indices are the codes for the lookup table, and these indices are what are
stored in pixel values of the new, color quantized or palettized image.

3.2 Popular File Formats

Some popular image file formats are described below. One of the simplest is the 8-bit
GIF format, and we study it because it is easily understood, and also because of its
historical connection to the WWW and HTML markup language as the first image
type recognized by net browsers. However, currently the most important common
file format is JPEG, which will be explored in-depth in Chap. 9.

3.2.1 GIF

Graphics Interchange Format (GIF) was devised by UNISYS Corporation and Com-
puserve, initially for transmitting graphical images over phone lines via modems. The
GIF standard uses the Lempel-Ziv-Welch algorithm (a form of compression—see
Chap. 7), modified slightly for image scanline packets to use the line grouping of
pixels effectively.
The GIF standard is limited to 8-bit (256) color images only. While this produces
acceptable color, it is best suited for images with few distinctive colors (e.g., graphics
or drawing).
The GIF image format has a few interesting features, notwithstanding the fact that
it has been largely supplanted. The standard supports interlacing—the successive
display of pixels in widely spaced rows by a four-pass display process.
In fact, GIF comes in two flavors. The original specification is GIF87a. The later
version, GIF89a, supports simple animation via a Graphics Control Extension block
in the data. This provides simple control over delay time, a transparency index, and
so on. Software such as Corel Draw allows access to and editing of GIF images.
It is worthwhile examining the file format for GIF87 in more detail, since many
such formats bear a resemblance to it but have grown a good deal more complex than
this “simple” standard. For the standard specification, the general file format is as in
Fig. 3.12. The Signature is six bytes: GIF87a; the Screen Descriptor is a seven-byte
set of flags. A GIF87 file can contain more than one image definition, usually to fit
on several different parts of the screen. Therefore each image can contain its own
color lookup table, a Local Color Map, for mapping 8 bits into 24-bit RGB values.
However, it need not, and a global color map can instead be defined to take the place
of a local table if the latter is not included.
70 3 Graphics and Image Data Representations

GIF signature

Screen descriptor

Global color map

...
Image descriptor
Repeated
Local color map 1 to n times

Raster area
...

GIF terminator

Fig. 3.12 GIF file format

Bits
7 6 5 4 3 2 1 0 Byte #
1
Screen width Raster width in pixels (LSB first)
2

3
Screen height Raster height in pixels (LSB first)
4

m cr 0 pixel 5

Background 6 Background = color index of screen

background (color is defined from
0 0 0 0 0 0 0 0 7 the global color map or if none
specified, from the default map)
m=1 Global color map follows descriptor
cr + 1 # bits of color resolution
pixel + 1 # bits/pixel in image

Fig. 3.13 GIF screen descriptor

The Screen Descriptor comprises a set of attributes that belong to every image in
the file. According to the GIF87 standard, it is defined as in Fig. 3.13. Screen Width
is given in the first two bytes. Since some machines invert the order MSB/LSB
(most significant byte/least significant byte—i.e., byte order), this order is specified.
Screen Height is the next two bytes. The ‘m’ in byte five is zero if no global color
map is given. Color resolution, “cr”, is 3 bits in 0 .. 7. Since this is an old standard
meant to operate on a variety of low-end hardware, “cr” is requesting this much color
resolution.
The next bit, shown as ‘0’, is extra and is not used in this standard. “Pixel” is
another 3 bits, indicating the number of bits per pixel in the image, as stored in the
3.2 Popular File Formats 71

Bits
7 6 5 4 3 2 1 0 Byte #
Red intensity 1 Red value for color index 0

Green intensity 2 Green value for color index 0

Blue intensity 3 Blue value for color index 0

Red intensity 4 Red value for color index 1

Green intensity 5 Green value for color index 1

Blue intensity 6 Blue value for color index 1

...

(continues for remaining colors)

Fig. 3.14 GIF color map

Bits
7 6 5 4 3 2 1 0 Byte #
0 0 1 0 1 1 0 0 1 Image separator character (comma)
2 Start of image in pixels from the
Image left
3 left side of the screen (LSB first)
4 Start of image in pixels from the
Image top
5 top of the screen (LSB first)
6
Image width Width of the image in pixels (LSB first)
7
8
Image height Height of the image in pixels (LSB first)
9
m i 0 0 0 pixel 10 m=0 Use global color map, ignore ‘pixel’
m=1 Local color map follows, use ‘pixel’
i=0 Image formatted in Sequential order
i=1 Image formatted in Interlaced order
pixel + 1 # bits per pixel for this image

Fig. 3.15 GIF image descriptor

file. Although “cr” usually equals “pixel,” it need not. Byte six gives the color table
index byte for the background color, and byte seven is filled with zeros. For present
usage, the ability to use a small color resolution is a good feature, since we may be
interested in very low-end devices such as web-enabled wristwatches, say.
A color map is set up in a simple fashion, as in Fig. 3.14. However, the actual
length of the table equals 2pixel+1 as given in the screen descriptor.
72 3 Graphics and Image Data Representations

Image
row Pass 1 Pass 2 Pass 3 Pass 4 Result

0 *1a* *1a*
1 *4a* *4a*
2 *3a* *3a*
3 *4b* *4b*
4 *2a* *2a*
5 *4c* *4c*
6 *3b* *3b*
7 *4d* *4d*
8 *1b* *1b*
9 *4e* *4e*
10 *3c* *3c*
11 *4f* *4f*
12 *2b* *2b*
...

Fig. 3.16 GIF four-pass interlace display row order

Each image in the file has its own Image Descriptor, defined as in Fig. 3.15.
Interestingly, the developers of this standard allowed for future extensions by ignoring
any bytes between the end of one image and the beginning of the next, identified by a
comma character. In this way, future enhancements could have been simply inserted
in a backward-compatible fashion.
If the interlace bit is set in the local Image Descriptor, the rows of the image
are displayed in a four-pass sequence, as in Fig. 3.16. Here, the first pass displays
rows 0 and 8, the second pass displays rows 4 and 12, and so on. This allows for a
quick sketch to appear when a web browser displays the image, followed by more
detailed fill-ins. The JPEG standard (below) has a similar display mode, denoted
progressive mode.
The actual raster data itself is first compressed using the LZW compression
scheme (see Chap. 7) before being stored.
The GIF87 standard also set out, for future use, how Extension Blocks could be
defined. Even in GIF87, simple animations can be achieved, but no delay was defined
between images, and multiple images simply overwrite each other with no screen
clears.
GIF89 introduced a number of Extension Block definitions, especially those to
assist animation: transparency and delay between images. A quite useful feature
introduced in GIF89 is the idea of a sorted color table. The most important colors
appear first, so that if a decoder has fewer colors available, the most important ones
are chosen. That is, only a segment of the color lookup table is used, and nearby
colors are mapped as well as possible into the colors available.
3.2 Popular File Formats 73

We can investigate how the file header works in practice by having a look at a par-
ticular GIF image. Figure 3.7 is an 8-bit color GIF image. To see how the file header
looks, we can simply use everyone’s favorite command in the Unix/Linux/MacOS
operating system: od (octal dump). In Unix,1 then, we issue the command
od -c forestfire.gif | head -2
and we see the first 32 bytes interpreted as characters:
G I F 8 7 a \208 \2 \188 \1 \247 \0 \0 \6 \3 \5
J \132 \24 | ) \7 \198 \195 \ \128 U \27 \196 \166 & T

To decipher the remainder of the file header (after GIF87a), we use hexadecimal:
od -x forestfire.gif | head -2
with the result
4749 4638 3761 d002 bc01 f700 0006 0305
ae84 187c 2907 c6c3 5c80 551b c4a6 2654
The d002 bc01 following the Signature are Screen Width and Height; these are
given in least-significant-byte-first order, so for this file in decimal the Screen Width
is 0 + 13 × 16 + 2 × 162 = 720, and Screen Height is 11 × 16 + 12 + 1 × 162 = 444.
Then the f7 (which is 247 in decimal) is the fifth byte in the Screen Descriptor,
followed by the background color index, 00, and the 00 delimiter. The set of flags,
f7, in bits, reads 1, 111, 0, 111, or in other words: global color map is used,
8-bit color resolution, 0 separator, 8-bit pixel data.

3.2.2 JPEG

The most important current standard for image compression is JPEG [6]. This stan-
dard was created by a working group of the International Organization for Standard-
ization (ISO) that was informally called the Joint Photographic Experts Group and
is therefore so named. We shall study JPEG in greater detail in Chap. 9, but a few
salient features of this compression standard can be mentioned here.
The human vision system has some specific limitations, which JPEG takes advan-
tage of to achieve high rates of compression. The eye–brain system cannot see
extremely fine detail. If many changes occur within a few pixels, we refer to that
image segment as having high spatial frequency—that is, a great deal of change
in (x, y) space. This limitation is even more conspicuous for color vision than for
grayscale (black and white). Therefore, color information in JPEG is decimated (par-
tially dropped, or averaged) and then small blocks of an image are represented in the
spatial frequency domain (u, v), rather than in (x, y). That is, the speed of changes
in x and y is evaluated, from low to high, and a new “image” is formed by grouping
the coefficients or weights of these speeds.

1 CentOS version; older versions use slightly different syntax.