Lossy Algorithms

Lossy compression and perceptual models

Lossless compression preserves the input data. In contrast, lossy compression permanently reduces the precision of selected data or removes it. Decompression therefore produces an approximation of the original. For audio, images, and video, the choice of information depends on signal properties and a perceptual model. A higher compression level therefore involves a controlled quality loss. The result also depends on encoder parameters, so the same format can produce different file sizes and different quality levels.

This model is used in applications such as video streaming, image storage, and real-time voice and video transmission. An encoder analyzes the signal, identifies relevant components, and assigns them different precision. The principal families are transform coding, used in formats such as JPEG, MPEG, and MP3, predictive coding, and fractal compression based on image self-similarity. The lossy stage should be distinguished from later entropy coding, which can reduce the stream without another loss of information.

Transform coding

Transform coding is one of the basic methods of lossy compression. It is used in many image, video, and audio standards, including JPEG, MPEG, and MP3. The transform itself is a lossless change of representation; information is lost later through quantization or another precision limit. The transform is selected so that signal energy can concentrate in a small number of coefficients and leave many values close to zero.

Changing the representation domain

Raw values such as pixel brightness or audio sample amplitude can contain strong dependencies. A transform represents them in another mathematical domain, such as the frequency domain, where components with different importance are easier to separate.

A transform converts a data set from one representation to another without losing information in the operation itself. The new representation can make subsequent quantization and lossless coding more effective. Transform coding mainly serves two goals. In images, spatial dependencies are represented as frequency components; in audio, a related representation separates bands with different perceptual importance:

• Decorrelation: Adjacent pixels in images are often strongly correlated. A transform reduces these dependencies so that the coefficients describing the signal are less dependent on one another.
• Energy compaction: A suitable transform concentrates much of the signal energy in a small number of coefficients. The remaining coefficients often have small values and can be stored with lower precision.

Discrete Cosine Transform (DCT)

A frequently used transform in lossy compression is the Discrete Cosine Transform (DCT). JPEG and selected MPEG standards apply it to pixel blocks, usually 8x8, rather than to the entire image at once. Block processing limits the working memory, although strong quantization can make block boundaries visible.

The two-dimensional DCT takes an 8x8 block of pixel values and converts it into an 8x8 block of frequency coefficients. Each coefficient represents a combination of horizontal and vertical frequencies, so JPEG scans the coefficients in a zig-zag order before entropy coding.

• The top-left coefficient, the DC coefficient, represents the average brightness or color of the entire 8x8 block. For typical images, it carries a substantial part of the block's energy.
• The other 63 coefficients are the AC coefficients. They describe details and textures, from lower frequencies near the DC coefficient to higher frequencies toward the bottom-right corner.

The interactive DCT block shows how retaining low-frequency coefficients affects detail and how the block changes when other coefficients are set to zero.

Example: the JPEG image-coding pipeline

JPEG provides a practical example of transform coding for still images.

1. Step 1: color-space conversion and chroma subsampling: The image is converted from RGB (red, green, blue) to YCbCr. Y represents luminance, while Cb and Cr represent chrominance. Human vision is less sensitive to fine color changes than to brightness changes, so Cb and Cr may be downsampled, for example by storing one color value for each 2x2 pixel block. This is the first lossy stage. The exact sampling ratio depends on the selected scheme, such as 4:4:4, 4:2:2, or 4:2:0.
2. Step 2: blocking and DCT: Each component (Y, Cb, Cr) is divided into 8x8 pixel blocks. The DCT transforms each block, 64 values, into 64 coefficients. The DC coefficient represents the constant component, while the AC coefficients represent changes within the block.
3. Step 3: quantization, the lossy stage: Each of the 64 DCT coefficients is divided by a corresponding value from a 64-element quantization table, and the result is rounded to an integer.
   $\text{Quantized coefficient} = \operatorname{round}\left(\frac{\text{DCT coefficient}}{\text{Quantization value}}\right)$
   The table usually contains smaller values for lower frequencies and larger values for higher frequencies. Quantization turns many small AC coefficients into zero and limits the precision of the rest, permanently discarding information. The table scale is implementation-dependent. An image editor may expose a quality setting from 1 to 100, but that range is not part of the JPEG standard. A lower quality setting usually means larger divisors, more data loss, and a smaller file. The decoder multiplies by the table values to obtain approximate coefficients, so two images with the same quality number do not have to have the same visual result.
4. Step 4: entropy coding: The block of 64 quantized coefficients contains many zeros, so it can be compressed in a lossless stage. In baseline JPEG, Huffman codes describe the coefficient category and, for AC coefficients, the zero-run length. Additional bits carry the coefficient amplitude.

The decoder reads the losslessly coded data, dequantizes it by multiplying by the same table values, applies the inverse DCT, and reassembles the blocks. Precision lost during quantization cannot be recovered. Repeated JPEG saves can therefore accumulate quantization errors.

Predictive coding for audio signals

Predictive coding uses the relationship between consecutive samples. It is useful for signals such as audio, where adjacent samples often have similar values.

The difference between a sample and its prediction

Instead of encoding the full value of every audio sample, a predictive coder estimates the next value from preceding samples. It then calculates the prediction error, the difference between the estimate and the actual sample. For a strongly correlated signal, the error has a smaller range than the sample and can require fewer bits.

The process becomes lossy when the prediction error is quantized before transmission. A limited number of bits reduces its precision, and small errors may be rounded to zero. The decoder makes the same prediction, adds the received quantized error, and obtains an approximation of the original sample. A lossless variant can code the error exactly, while adaptive variants change the quantizer step as the signal range changes.

The interactive loop shows how the quantizer step and predictor change the error and the reconstructed DPCM signal.

This technique, known as Differential Pulse-Code Modulation (DPCM), is used in speech and audio codecs. For many signals, adjacent samples are similar, so the prediction error has a small amplitude and is easier to encode. ADPCM additionally adapts the quantizer step to use the available bits when the signal level changes.

Fractal image compression

Fractal compression is a less common method of lossy image compression. It uses self-similarity, the similarity of image regions at different scales.

Matching blocks and transformation parameters

A fractal compressor searches for regions that can be approximated by scaled or transformed versions of other regions in the same image. For example, a small cloud may resemble a larger cloud elsewhere in the sky, or a fern fragment may resemble the structure of the whole frond.

Encoding stores transformation parameters instead of every pixel value. For each small target region, it selects a larger source region and fits an affine transform with scaling, rotation, and brightness or contrast adjustment. The compressed representation is the collection of these parameters. A source region may come from another part of the image, and the fit usually minimizes a chosen error measure between source and target blocks.

Decoding is iterative. It starts with an initial image and repeatedly applies the stored transformations. For a contractive family, the Iterated Function System (IFS) theorem guarantees convergence to an attractor. The attractor approximates the encoded image and does not reproduce the original without error. The number of iterations affects decoding cost and the rate at which the image reaches a stable appearance.

Properties and limitations

Fractal compression has several characteristic properties:

• Large data reduction: Matching can produce a substantial compression level for selected natural and textured images.
• Output-resolution flexibility: Transformation parameters can be evaluated at different resolutions because the representation does not contain a grid of every pixel. Detail after enlargement depends on the quality of the fitted transformations.
• Expensive encoding: Searching for the best matching blocks requires many comparisons, so encoding is computationally costly. Decoding is usually simpler.

Encoding cost and historical patent issues limited the use of this method. It did not achieve the adoption of transform-based methods such as JPEG. Practical results also depend on the block-search strategy, transformation constraints, and selected similarity measure.

Combining transform and predictive coding

Transform, predictive, and fractal coding represent different approaches to lossy data reduction. Many video codecs combine transformation, inter-frame prediction, and entropy coding. In H.262, prediction with motion compensation uses similarity between successive frames, while the DCT codes image data and prediction errors. The selected transform, prediction method, quantization, and bitrate determine the trade-off between stream size and reconstructed quality. The same combination can use different quantization tables, block sizes, or prediction modes depending on the standard and profile. Entropy coding then removes statistical redundancy from the quantized representation. The decoder reverses that stage exactly, while quantization error remains in the reconstructed signal.