Introduction to image compression
Digital images are used in photographs, documents, and websites. Raw, uncompressed image data can require substantial storage. A single high-resolution photograph can take up tens of megabytes. Storing thousands of such photos would quickly fill a drive, and sending one over a slow internet connection could take minutes.
Image compression reduces file size by removing or representing repetitive and less important information more efficiently. allows more images to be stored and shared more quickly. In image data, can come from repeated patterns, large areas of one color, or details that perception tends to overlook. The techniques are divided into lossless and lossy compression.
The divide: lossless and lossy compression
The choice between lossless and lossy compression sets the trade-off between file size and fidelity to the original. Each approach serves different applications and image types.
Lossless compression: exact reconstruction
reduces file size without discarding information. Decompression restores exactly the data that was present before compression, bit for bit.
This is achieved by finding statistical redundancy in the data. For example, instead of storing "blue, blue, blue, blue, blue," a lossless algorithm might store "(blue, 5 times)". Another technique involves creating a dictionary of common patterns and replacing them with shorter codes. Consider this famous line of text:
To be, or not to be, that is the question
A lossless algorithm might notice that the phrase "to be" appears twice and replace the second instance with a short pointer such as "refer to the first 5 characters." This saves space without changing the data. The amount of compression depends on the input: repetitive data compresses well, while random data usually compresses poorly.
When to use it: Lossless compression is required when data must be restored without changes. Applications include text documents, computer programs, medical imaging such as MRI scans, and technical diagrams. PNG is a lossless image format, while GIF applies lossless LZW after storing an indexed palette.
PNG applies reversible scanline filtering before Deflate compression. Filtering changes how neighboring samples are represented, while the decoder can reconstruct the original bytes. The format supports indexed color, grayscale, truecolor, and an alpha channel. Each PNG chunk also carries a CRC check value that helps detect damaged data. The filter itself does not remove bytes; it prepares the data for more effective Deflate coding. PNG alpha can represent partial transparency, unlike the single transparent palette index available in GIF. PNG filtering is reversible and separate from palette quantization.
Lossy compression: an image approximation
permanently removes some data to produce a smaller file. The discarded information is selected using a data model and an estimate of perceptual sensitivity.
This method relies on that describe the sensitivities of human vision. Vision is usually more sensitive to changes in brightness than to small color changes, so an encoder can preserve luminance more precisely than chrominance. The result is an approximation of the original and may look lossless under particular viewing conditions. A "quality" setting selects a trade-off between file size and visual fidelity.
When to use it: Lossy compression is often used for photographs, video, and audio when bit-for-bit accuracy is not required. A small quality loss can justify the reduction in file size. JPEG is an example of a lossy image format.
GIF format: an indexed palette
GIF, which stands for Graphics Interchange Format, is a raster format with an indexed color palette. The GIF89a specification describes features including animation, transparency, and interlacing. If an image contains more than 256 colors, encoding requires palette reduction, after which the indices are compressed with lossless LZW.
Step 1: indexed color palette
A GIF file uses an indexed color palette. Instead of storing a full color value, usually 24 bits representing more than 16 million colors, it stores a color table and an index for each pixel. A GIF palette can contain at most 256 colors.
If the original image contains thousands or millions of colors, as a photograph may, the GIF encoder performs . It selects up to 256 colors and maps the remaining colors to the closest palette entries. Subtle gradients and shades are then lost. For an image that already has few colors, such as a logo or diagram, palette reduction can preserve all data.
Once the palette is established, each pixel in the image is no longer represented by its full color value, but by a simple 8-bit number () that serves as an index to its color in the palette.
Step 2: LZW compression
After conversion to a stream of color indices, the lossless Lempel-Ziv-Welch (LZW) algorithm is applied. LZW builds a dictionary of recurring sequences. When it finds a known sequence, it outputs a code pointing to its dictionary entry instead of the full sequence. This works well for images with large areas of flat color, where a long run of identical indices can be represented by a few codes.
GIF codes use a size derived from the dictionary and are preceded by the minimum code size. The data stream also contains clear and end-of-information codes. Decompression restores exactly the index stream that was stored after palette reduction.
Special features and use cases
- Animation: GIF can store multiple frames in one file with timing information, which allows simple looping animations.
- Transparency: GIF supports binary transparency. One palette color can be marked as transparent, but the format does not store partial alpha transparency.
- Interlacing: An interlaced GIF is displayed in several passes. An initial image appears before all data has arrived, and later passes fill in the remaining details.
JPEG format: compressing photographs
JPEG (named after the Joint Photographic Experts Group) is a format used for lossy compression of continuous-tone images such as photographs. It uses properties of visual perception, while the resulting size and quality depend on the encoding parameters.
ITU-T T.81 describes the baseline sequential DCT process, extended and progressive processes, and lossless processes. A particular JPEG file can therefore use a different profile and different tables from the baseline example.
The JPEG compression process has several stages:
- Color space transformation:
The image is typically converted from RGB (Red, Green, Blue) to a luminance and chrominance space called YCbCr. This separates brightness (Y, or luma) from color (Cb and Cr, or chrominance). Vision is usually more sensitive to fine brightness details than to fine color details.
- Chroma subsampling:
The chroma components can be stored at a lower resolution than luma. In the scheme, a pixel block shares Cb and Cr samples while each pixel retains its own Y sample. This reduces the number of color samples, while the result depends on the image and encoder settings.
Other schemes, such as and , preserve more chroma samples. Subsampling is not required for every JPEG encoding.
- Discrete cosine transform (DCT):
The image is divided into pixel blocks. Each block is processed by the . The transform represents a block with 64 frequency coefficients. The first, the DC coefficient, describes the constant component, while the other 63 AC coefficients describe image changes and detail.
The transform changes the coefficient representation. Information is discarded in the following quantization stage, not while calculating the DCT.
- Quantization:
This is the main lossy stage of JPEG. Each of the 64 DCT coefficients is divided by a corresponding value from a 64-element , and the result is rounded to an integer. Larger table values reduce coefficients more strongly, especially at high frequencies, so many become zero. An encoder's "quality" setting usually scales the quantization tables or selects a table variant, although the details depend on the implementation.
- Entropy coding:
In the final stage, quantized coefficients are read in zig-zag order, which groups zeros. Zero runs are represented with (RLE). In baseline JPEG, the resulting symbols are then coded losslessly with Huffman tables. T.81 also defines arithmetic-coding alternatives.
The quantization stage causes the intended loss, while the final entropy coding does not discard information from the already quantized coefficients. T.81 also describes lossless and predictive processes, so JPEG does not denote one mandatory processing path.
In typical baseline coding, the DC coefficient is coded differentially from the previous block, while AC coefficients describe a zero-run length and the value size. Huffman tables are part of the JPEG bitstream. Their selection affects the length of the final bitstream, while a quality setting primarily changes quantization.