BSc CSIT (TU) Science Multimedia Computing (BSc CSIT, CSC467) Question Paper 2074 Nepal

JPEG Image Compression Standard

JPEG (Joint Photographic Experts Group) is a widely used lossy compression standard for continuous-tone still images. It exploits the limitations of the human visual system (which is less sensitive to high-frequency detail and to chrominance than luminance) to discard information that is not visually significant.

Block Diagram (pipeline)

Source Image
   |
[Color transform RGB -> YCbCr + chroma subsampling]
   |
[Divide into 8x8 blocks]
   |
[Forward DCT] --> [Quantization] --> [Zig-zag ordering] --> [Run-length + DPCM] --> [Entropy (Huffman) coding]
   |
Compressed bitstream (JFIF)

Main Steps

1. Color transform & subsampling. RGB is converted to $Y$ (luminance), $C_b, C_r$ (chrominance). Chrominance is subsampled (e.g. 4:2:0) since the eye is less sensitive to color detail.

2. Block splitting. Each component is divided into non-overlapping 8x8 pixel blocks.

3. Discrete Cosine Transform (DCT). Each 8x8 block of pixel values $f(x,y)$ is transformed into 64 frequency coefficients $F(u,v)$:

where $C(u),C(v)=1/\sqrt2$ for $u,v=0$, else $1$. The top-left coefficient $F(0,0)$ is the DC (average) term; the rest are AC terms representing increasing spatial frequencies. Energy is compacted into a few low-frequency coefficients.

4. Quantization. Each coefficient is divided by a value from an 8x8 quantization table $Q(u,v)$ and rounded:

Larger step sizes are used for high frequencies, so many of those coefficients become zero. This is the lossy step and controls the quality/size trade-off.

5. Zig-zag ordering. The 8x8 quantized block is read in a zig-zag order from low to high frequency. This groups the long runs of zeros at the end, which compress well.

6. Entropy (Huffman) coding. The DC coefficient is coded differentially (DPCM) against the previous block's DC. AC coefficients are coded as (run-length of zeros, value) pairs, then Huffman-coded to produce the final compressed bitstream. (Arithmetic coding is an optional alternative.)

Decoding

Decoding reverses the pipeline: entropy decode, dequantize, inverse DCT, recombine blocks, and convert YCbCr back to RGB.

MPEG Video Compression Standard

MPEG (Moving Picture Experts Group) standards (MPEG-1, MPEG-2, etc.) compress digital video by removing both spatial redundancy within a frame (using JPEG-like intra-frame DCT coding) and temporal redundancy between successive frames (using motion-compensated prediction).

Frame Types

• I-frames allow random access and act as recovery/refresh points but use the most bits.
• P-frames store only the motion-compensated difference from a past reference.
• B-frames interpolate between a past and a future reference, giving the best compression; they are not used as references themselves.

Motion Estimation and Compensation

Each frame is divided into macroblocks (typically 16x16 pixels).

• Motion estimation: For each macroblock, the encoder searches a region of the reference frame to find the best-matching block, producing a motion vector (dx, dy). Block-matching with a cost such as SAD (Sum of Absolute Differences) is used.
• Motion compensation: The predicted block is shifted by the motion vector. Only the residual (difference between actual and predicted block) plus the motion vector is encoded. The residual is DCT-transformed, quantized and entropy-coded.

This greatly reduces data because consecutive video frames are highly similar.

Group of Pictures (GOP)

A GOP is a repeating sequence of frames beginning with an I-frame, e.g.:

I B B P B B P B B P ...

• GOP size (distance between I-frames) trades off compression vs random-access/error-resilience.
• Because B-frames depend on a future P/I frame, the display order differs from the transmission/decoding order (the future reference is sent before the B-frames that use it).

Entropy and Source Coding for Multimedia

Entropy is the average information content of a source. For a source with symbols of probability $p_i$:

It is the theoretical lower bound on the average number of bits per symbol for lossless coding. Source (entropy) coding assigns shorter codes to frequent symbols to approach this bound.

Huffman Coding

A variable-length, prefix-free code built bottom-up: repeatedly merge the two least-probable symbols into a node whose probability is their sum, until one tree remains; assign 0/1 to branches. It produces the optimal integer-length prefix code.

Run-Length Encoding (RLE)

Replaces runs of identical symbols by a (value, count) pair, e.g. AAAAABBB -> 5A3B. Very effective for data with long repeats (e.g. zero runs after JPEG quantization, fax images).

Arithmetic Coding

Encodes an entire message as a single fractional number in $[0,1)$, recursively narrowing the interval according to each symbol's probability. It can use fractional bits per symbol and so approaches entropy more closely than Huffman, especially for skewed probabilities.

Worked Huffman Example

Let symbols and frequencies be: A=5, B=2, C=1, D=1 (total 9).

1. Combine smallest: C(1)+D(1) = CD(2).
2. Combine B(2)+CD(2) = BCD(4).
3. Combine A(5)+BCD(4) = root(9).

Assigning 0/left, 1/right:

Average length $=\frac{5\cdot1+2\cdot2+1\cdot3+1\cdot3}{9}=\frac{15}{9}\approx1.67$ bits/symbol, far better than 2 bits with fixed-length coding.

Huffman Coding

Huffman coding is a lossless, variable-length prefix code that assigns shorter codewords to more frequent symbols and longer codewords to rare ones, minimizing the average code length.

Algorithm

1. List symbols with their frequencies/probabilities.
2. Repeatedly take the two lowest-frequency nodes and merge them into a new node whose frequency is their sum.
3. Repeat until a single tree (root) remains.
4. Label each left/right branch 0/1; the path from root to a leaf is that symbol's code.

Example

Symbols: A=45, B=13, C=12, D=16, E=9, F=5.

Merging the two smallest at each step (F+E=14, C+B=25, ...), a valid resulting code is:

The codes are prefix-free (no code is a prefix of another), so the bitstream decodes unambiguously. Frequent symbol A uses 1 bit while rare F uses 4 bits, giving an average length well below the 3 bits needed for fixed-length coding of 6 symbols.

Run-Length Encoding (RLE)

Run-length encoding is a simple lossless compression technique that replaces consecutive repeated data values (a run) with a single value and a count, rather than storing each repetition.

Example

Input string:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

RLE output:

12W1B12W3B24W1B14W

Here 67 characters are reduced to 18, encoding each run as <count><symbol>.

Characteristics

• Best for data with long runs of identical values: simple graphics, icons, fax (CCITT) images, and the zero-runs produced after JPEG quantization.
• Worst case: data with no repetition can become larger than the original.
• It is fast and is often combined with other methods (e.g. RLE then Huffman in JPEG).

Role of DCT and Quantization in JPEG

Discrete Cosine Transform (DCT)

JPEG applies a forward DCT to each 8x8 block of pixels, converting spatial pixel values into 64 frequency coefficients:

• The coefficient $F(0,0)$ is the DC term (block average); the rest are AC terms for increasing frequencies.
• DCT performs energy compaction: most signal energy concentrates in a few low-frequency coefficients, while high-frequency coefficients (fine detail/noise) are small. The DCT itself is lossless and reversible.

Quantization

Each DCT coefficient is divided by a value from an 8x8 quantization table and rounded:

• Larger quantization steps are applied to high-frequency coefficients (the eye is less sensitive to them), so many become zero.
• This is the lossy step of JPEG; it is where actual compression and quality loss happen.
• The quality factor scales $Q$: higher quality = finer steps = larger files.

Together: DCT reorganizes information so it can be discarded selectively, and quantization discards the least visually important information, producing many zeros that subsequent zig-zag, run-length and Huffman coding compress efficiently.

I-frames vs P-frames vs B-frames (MPEG)

Summary

• I-frames are encoded independently using only spatial (intra-frame) redundancy, allowing random access but giving the least compression.
• P-frames use motion-compensated prediction from a previous reference frame and store only the residual + motion vectors.
• B-frames interpolate bidirectionally between a past and a future reference, achieving the best compression; because they need a future frame, the decoding order differs from the display order.

RGB vs CMYK Color Models

Explanation

• RGB is additive: colors are produced by emitting and combining red, green and blue light. Maximum of all three gives white; this matches how display devices generate color.
• CMYK is subtractive: printed inks absorb (subtract) wavelengths from white light reflected off paper. Cyan, magenta and yellow theoretically make black, but in practice a separate black (K) ink is added for deeper blacks, sharper text and to save colored ink.
• Designs created in RGB for screens must be converted to CMYK for printing, which may shift colors because CMYK has a smaller gamut.

Sampling and Quantization of Digital Audio

Converting a continuous (analog) sound wave into digital form requires two steps: sampling (discretizing time) and quantization (discretizing amplitude). Together they form Pulse Code Modulation (PCM).

Sampling

• The amplitude of the analog signal is measured at regular time intervals at a fixed sampling rate $f_s$ (samples per second, Hz).
• By the Nyquist theorem, $f_s$ must be at least twice the highest frequency in the signal to avoid aliasing:

• Example: human hearing reaches ~20 kHz, so audio CDs use $f_s = 44.1$ kHz.

Quantization

• Each sampled amplitude is rounded to the nearest level from a finite set of $2^n$ levels, where $n$ is the bit depth (e.g. 16 bits = 65,536 levels).
• The rounding error introduces quantization noise; more bits = finer levels = higher signal-to-noise ratio and better fidelity.

Data Rate

For CD-quality stereo: $44100 \times 16 \times 2 = 1.41$ Mbps. Higher rate/depth means better quality but larger files, motivating audio compression (e.g. MP3).

Lossy vs Lossless Compression

Explanation

• Lossless compression encodes data so it can be perfectly restored. It exploits statistical redundancy (e.g. Huffman, RLE, LZW). Used where exact data matters: text, executables, archives, medical/legal images.
• Lossy compression achieves much smaller sizes by discarding information the human eye/ear is unlikely to notice (high-frequency detail, inaudible sounds). The loss is irreversible but acceptable for photos, audio and video, so it is used in JPEG, MP3 and MPEG.

Trade-off: lossy gives far smaller files at the cost of fidelity; lossless preserves data exactly but compresses less.

Characteristics and Storage Requirements of Multimedia Data

Characteristics

1. Voluminous / large data size – images, audio and especially video produce huge amounts of data.
2. Heterogeneous (multiple media types) – text, graphics, images, audio, video and animation combined, each with different formats.
3. Time-dependent (continuous) media – audio and video must be presented at a fixed rate; they have temporal/real-time constraints.
4. High bandwidth and processing demands – capture, transmission and playback need high data rates.
5. Need for synchronization – different streams (e.g. audio with video) must stay aligned.
6. Highly compressible – contains much redundancy, so compression is essential.

Storage Requirements

Uncompressed multimedia is extremely large:

• Image: $\text{width}\times\text{height}\times\text{bits per pixel}$. A 1024x768 24-bit image $\approx 2.36$ MB.
• Audio: $f_s \times \text{bit depth} \times \text{channels}$. CD stereo = 1.41 Mbps $\approx$ 10 MB/minute.
• Video: $\text{frame size} \times \text{frames per second}$. Raw 720x480, 24-bit, 30 fps $\approx$ 248 Mbps, i.e. several GB per minute.

Because of these enormous sizes, multimedia systems rely on compression (JPEG, MP3, MPEG) and on high-capacity, high-throughput storage and networks.

Multimedia Synchronization

Multimedia synchronization is the coordination of the temporal and spatial relationships between different media objects so they are presented to the user in the correct, intended order and timing (e.g. keeping audio aligned with video, or showing a subtitle at the right moment).

Intra-media vs Inter-media Synchronization

Summary

• Intra-media synchronization preserves the timing within one medium (e.g. constant frame/sample rate).
• Inter-media synchronization preserves timing between media (the classic example being audio-video lip-sync). Proper synchronization is essential for a coherent multimedia presentation.