Lossy vs Lossless

Not all compression applications demand perfect reconstruction of the original data. When the end consumer is a human perceptual system, some level of distortion is tolerable. Lossless compression guarantees exact reconstruction while lossy compression trades reconstruction accuracy for significantly higher compression ratios. Understanding the boundary between these two classes and the criteria for acceptable distortion is fundamental to modern multimedia coding and GATE examinations.

Core Concept Explanation

In lossless compression the decoded output is bit-for-bit identical to the original. This is achieved by removing only statistical redundancy, which is the predictable structure in data. Huffman coding, LZ77, and arithmetic coding are all lossless. The minimum possible code length is bounded below by the source entropy H(S) bits per symbol, which represents irreducible information content.

In lossy compression, irrelevant information is deliberately discarded. The definition of irrelevance is determined by subjective fidelity criteria, which are psychophysical models of human perception. For images, the human visual system is less sensitive to high-frequency detail and color information than to low-frequency luminance. For audio, the ear masks quiet sounds that occur near loud sounds in frequency. Lossy coders exploit these perceptual limitations.

The fundamental theory governing this tradeoff is the rate-distortion theory developed by Shannon. Given a distortion measure D and a source, the rate-distortion function R(D) gives the minimum bit rate required to reconstruct the source with average distortion at most D. As D increases (more distortion allowed), R(D) decreases (fewer bits needed). Lossless coding corresponds to R(0).

Mathematical Expression

The most common distortion measure is Mean Squared Error (MSE), defined between original signal x and reconstructed signal x-hat of length N as:

MSE = (1/N) * sum( (x_i - x_hat_i)^2 )

The Peak Signal to Noise Ratio (PSNR) is derived from MSE and expressed in dB, giving a practical quality metric for images:

PSNR = 10 * log10( MAX^2 / MSE ) dB

where MAX is the maximum pixel value (255 for 8-bit). A PSNR above 40 dB is generally considered visually lossless. JPEG at typical quality settings achieves PSNR of 35 to 42 dB with compression ratios of 10:1 to 20:1.

Practical Understanding

JPEG uses lossy compression based on the Discrete Cosine Transform (DCT). The image block is transformed to the frequency domain, and high-frequency DCT coefficients are quantized coarsely (more loss) or finely (less loss) depending on a quality parameter. The quantization step is where information is irreversibly discarded. Subsequent entropy coding (Huffman or arithmetic) is lossless.

MPEG video compression extends the JPEG idea by also exploiting temporal redundancy between frames. Intra-frames (I-frames) are JPEG-like DCT compressed still images. Inter-frames (P-frames and B-frames) store only motion vectors and prediction residuals, dramatically reducing the bit rate.

For lossless applications such as medical imaging (X-ray, MRI), legal documents, financial records, and computer executables, lossy compression is completely unacceptable because even a single bit error can change meaning. PNG and FLAC are standard lossless formats for images and audio respectively.

Given:
Original 8-bit image block pixel values: [100, 102, 98, 101]
Reconstructed block after JPEG decompression: [104, 100, 96, 103]
N = 4 pixels, MAX = 255

Why this formula applies:
MSE measures average squared deviation between original and reconstructed pixels.
PSNR converts MSE to decibels relative to peak value.

Formula:
MSE = (1/N) * sum((xi - xi_hat)^2)
PSNR = 10 * log10(MAX^2 / MSE)

Substitution:
MSE = (1/4) * [(100-104)^2 + (102-100)^2 + (98-96)^2 + (101-103)^2]
    = (1/4) * [16 + 4 + 4 + 4]
    = (1/4) * 28 = 7.0

PSNR = 10 * log10(255^2 / 7.0)
     = 10 * log10(65025 / 7.0)
     = 10 * log10(9289.3)
     = 10 * 3.968

Final Answer:
PSNR = 39.68 dB
This is above 35 dB threshold, so perceptual quality is acceptable for most applications.

Exam Tip: GATE often asks whether entropy coding (Huffman, arithmetic) is lossy or lossless. It is always lossless. Lossy behavior enters only through quantization steps such as in JPEG DCT coefficient rounding.

Fidelity Criteria and Perceptual Coding

• Subjective fidelity criteria are based on psychophysical models of human perception, not mathematical exactness.
• Human visual system is less sensitive to high spatial frequencies and chrominance than to luminance and low frequencies.
• Human auditory system exhibits simultaneous and temporal masking, exploited by MP3 and AAC coders.
• Objective measures: MSE, PSNR (image), PESQ (speech), SSIM (structural similarity).
• Lossless formats: PNG, TIFF, FLAC, ZIP, GIF (for indexed images).
• Lossy formats: JPEG, HEIF, MPEG, MP3, AAC, Opus, WebP.

Quick Revision

• Lossless: exact reconstruction, CR limited by source entropy, used for medical/financial data.
• Lossy: controlled distortion, CR limited by perceptual quality, used for images/audio/video.
• MSE = (1/N)*sum((xi - xi_hat)^2) and PSNR = 10*log10(MAX^2/MSE) dB.
• JPEG: lossy DCT quantization + lossless Huffman. PNG: lossless prediction + DEFLATE.
• Subjective fidelity criteria exploit perceptual limitations of human vision and hearing.
• GATE trap: entropy coding (Huffman, arithmetic) is ALWAYS lossless. Only quantization is lossy.
• Rate-distortion function R(D) gives minimum bit rate for distortion at most D; R(0) = lossless.