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

Digital Image Representation and Color Models

1. Digital Image Representation

A digital image is a 2-D array (matrix) of pixels (picture elements). Each pixel is sampled spatially and quantized in intensity. A pixel value is stored as a number of bits called the bit depth (e.g. 8 bits = 256 levels). A grayscale image needs one value per pixel; a colour image needs several channels (one per primary component).

• Spatial resolution: number of pixels (e.g. $1920 \times 1080$).
• Colour/pixel depth: bits per pixel. A 24-bit RGB image uses 8 bits each for R, G, B giving $2^{24} \approx 16.7$ million colours.
• Storage of an uncompressed image $= W \times H \times \text{(bits per pixel)} / 8$ bytes.

2. Color Models

(a) RGB (Red, Green, Blue): An additive model used by displays (monitors, cameras). Colours are produced by adding light. $(0,0,0)$ = black, $(255,255,255)$ = white. Device dependent.

(b) CMYK (Cyan, Magenta, Yellow, Black): A subtractive model used in printing. Inks absorb (subtract) light. Conversion (normalised): $C = 1-R,\; M = 1-G,\; Y = 1-B$, then $K = \min(C,M,Y)$ is extracted so black is printed with cheaper black ink rather than mixing all three.

(c) YUV / YCbCr (Luminance–Chrominance): Separates brightness (luma, Y) from colour (chroma). YUV is used in analog TV; YCbCr is its digital form used in JPEG/MPEG. Typical transform:

The eye is more sensitive to luminance than to colour, which this model exploits.

3. Colour Sampling and Chroma Subsampling

Because the human visual system has lower acuity for colour than for brightness, the chroma (Cb, Cr) channels can be sampled at lower resolution than luma (Y) with little perceptual loss. This is chroma subsampling, written as J:a:b (over a $4\times2$ block):

4:2:0 (used in JPEG, MPEG, H.264) reduces colour data to a quarter while keeping full luma, saving storage/bandwidth with minimal visible quality loss.

Conclusion

Images are pixel matrices; RGB suits displays, CMYK suits printing, and YCbCr enables compression by separating luma from chroma so chroma subsampling can discard redundant colour data.

JPEG Image Compression Standard

JPEG (Joint Photographic Experts Group) is a widely used lossy compression standard for continuous-tone still images. It exploits the eye's reduced sensitivity to high spatial frequencies and to colour detail.

Block Diagram (described)

Image --> Color transform (RGB->YCbCr) --> 8x8 Blocks --> [DCT] --> [Quantization]
      --> [Zig-zag + DPCM(DC)/RLE(AC)] --> [Entropy (Huffman) Coding] --> JPEG bitstream

Main Steps

1. Colour transform & subsampling: RGB is converted to YCbCr and chroma is subsampled (typically 4:2:0).

2. Block splitting: Each channel is divided into $8\times8$ pixel blocks. Values are level-shifted by subtracting 128.

3. Forward DCT: Each block is transformed by the 2-D Discrete Cosine Transform:

This converts pixels into frequency coefficients; energy concentrates in the top-left DC coefficient and low-frequency terms.

4. Quantization: Each coefficient is divided by a value from an $8\times8$ quantization table and rounded:

High-frequency coefficients (large $Q$) often become zero. This is the main lossy step and is controlled by the quality factor.

5. Zig-zag ordering: The 2-D block is read in a zig-zag path from low to high frequency, grouping the many trailing zeros together for efficient run-length coding.

6. Entropy (Huffman) coding:

• The DC coefficient is coded differentially (DPCM) from the previous block's DC.
• The AC coefficients are run-length encoded as (run-of-zeros, value) pairs.
• These are then Huffman coded (variable-length, shorter codes for frequent symbols) producing the final compressed bitstream.

Decoding

Decoding reverses the steps: Huffman decode → de-zig-zag → de-quantize (multiply by $Q$) → inverse DCT → upsample chroma → YCbCr→RGB.

Conclusion

JPEG achieves high compression (often 10:1 or more) by transforming to frequency domain (DCT), discarding visually unimportant high-frequency detail (quantization), and removing statistical redundancy (zig-zag + Huffman).

MPEG Video Compression Standard

MPEG (Moving Picture Experts Group) compresses video by removing both spatial redundancy (within a frame, like JPEG) and temporal redundancy (between consecutive frames). Consecutive frames are highly similar, so MPEG stores only the differences and the motion of objects.

Frame Types

I-frame (Intra-coded): Coded independently like a JPEG image using DCT + quantization. It is a reference/anchor frame, needs no other frame, provides random access, but gives the lowest compression.

P-frame (Predictive): Coded from the previous I- or P-frame using forward prediction. Only the motion vectors and the prediction error (residual) are stored. Better compression than I.

B-frame (Bidirectional): Predicted from both a previous and a future reference frame (forward + backward prediction). Gives the highest compression; not used as a reference itself.

Motion Estimation and Compensation

• Motion estimation: Each frame is divided into macroblocks (e.g. $16\times16$). For each macroblock, the encoder searches a region of the reference frame for the best-matching block (e.g. minimising SAD) and records a motion vector $(dx, dy)$.
• Motion compensation: The matched block is used as a prediction; only the residual (current − predicted) is DCT-coded, quantized and entropy-coded. This drastically reduces data for moving content.

Group of Pictures (GOP)

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

• GOP size = number of frames from one I-frame to the next.
• A shorter GOP gives better error recovery and random access; a longer GOP gives better compression.
• Because B-frames depend on future frames, the display order differs from the decoding/transmission order.

Conclusion

MPEG combines intra-frame (DCT-based) and inter-frame (motion-compensated prediction with I/P/B frames in a GOP) techniques to achieve high compression suitable for storage and streaming of video.

Huffman Coding

Huffman coding is a lossless, variable-length, prefix-free entropy coding technique that assigns shorter codes to more frequent symbols and longer codes to rare ones, minimising the average code length.

Construction (example)

Symbols with frequencies: A=5, B=2, C=1, D=1.

1. Treat each symbol as a leaf node with its frequency.
2. Repeatedly remove the two lowest-frequency nodes and combine them into a new node whose weight is their sum.
3. Repeat until one tree remains.

Step: combine C(1)+D(1)=2; combine B(2)+CD(2)=4; combine A(5)+BCD(4)=9 (root)
Assign 0 to left, 1 to right branches:
        (9)
       0/  \1
      A    (4)
          0/  \1
          B    (2)
              0/ \1
              C   D

Average length $= (5\cdot1 + 2\cdot2 + 1\cdot3 + 1\cdot3)/9 = 15/9 \approx 1.67$ bits/symbol, versus 2 bits with fixed-length coding.

Working

No code is a prefix of another (prefix property), so the bitstream decodes uniquely by walking the tree from the root until a leaf is reached. It is used in JPEG, MP3, ZIP and many other formats.

Run-Length Encoding (RLE)

Run-length encoding is a simple lossless compression technique that replaces a run (sequence of identical consecutive values) with a single value and a count. It is effective when data contains long repeated runs (e.g. simple graphics, fax images, JPEG's quantized zeros).

Example

Input string: AAAAABBBCCDAA

Encode each run as (count, symbol):

5A 3B 2C 1D 2A → 5A3B2C1D2A

The original 13 characters are stored as 5 (count, symbol) pairs (10 characters), giving compression.

Note

RLE can expand data with few repetitions (e.g. ABCDEF becomes 1A1B1C1D1E1F). It is therefore best for data with long runs and is often combined with other methods (e.g. used for the AC coefficients in JPEG).

Role of DCT and Quantization in JPEG

DCT (Discrete Cosine Transform)

The 2-D DCT is applied to each $8\times8$ block of (level-shifted) pixels. It transforms the block from the spatial domain to the frequency domain, producing one DC coefficient (average/brightness, top-left) and 63 AC coefficients (increasing spatial frequency). For natural images, energy is concentrated in the low-frequency coefficients while high-frequency coefficients are small. The DCT itself is lossless and reversible (via inverse DCT) and merely reorganises information so it can be compressed efficiently.

Quantization

Each DCT coefficient is divided by a corresponding entry in an $8\times8$ quantization table and rounded:

• High-frequency coefficients use large $Q$ values (the eye is less sensitive to fine detail), so they often round to zero.
• This is the principal lossy step in JPEG and the source of compression; the quality factor scales the table to trade quality for size.
• The resulting many zeros enable efficient zig-zag + run-length + Huffman coding.

Summary

DCT concentrates image energy into few low-frequency coefficients (enabling compression but lossless itself); quantization discards perceptually unimportant high-frequency detail, providing the actual (lossy) data reduction in JPEG.

I-frames vs P-frames vs B-frames in MPEG

Summary:

• I-frame: self-contained reference; needed for seeking and error recovery; largest in size.
• P-frame: stores motion vectors + residual from a past frame; smaller than I.
• B-frame: uses both past and future frames, giving the best compression but requiring frame reordering (decode order ≠ display order) and extra latency.

RGB vs CMYK Color Models

Explanation:

• In RGB, colours are created by adding light: more light → brighter, all three full → white. It is the natural model for self-illuminating devices.
• In CMYK, white paper reflects all light and inks subtract wavelengths. Combining C, M, Y theoretically gives black, but in practice a separate K (black) ink is added for true blacks, sharper text and cheaper ink usage.
• Conversion (normalised, no GCR): $C=1-R,\;M=1-G,\;Y=1-B$, then extract $K=\min(C,M,Y)$.

Thus RGB is for screens (light) and CMYK is for print (ink), and images are converted from RGB to CMYK before printing.

Sampling and Quantization of Digital Audio

Converting a continuous (analog) sound wave into a digital signal requires two steps: sampling (discretising time) and quantization (discretising amplitude). This is performed by an Analog-to-Digital Converter (ADC).

1. Sampling

The continuous waveform is measured at regular time intervals; each measurement is a sample. The number of samples per second is the sampling rate / frequency ($f_s$, in Hz).

• Nyquist theorem: to reproduce a signal without aliasing, $f_s \ge 2 f_{max}$, where $f_{max}$ is the highest frequency present.
• Human hearing reaches ~20 kHz, so CD audio uses 44.1 kHz.

2. Quantization

Each sampled amplitude is rounded to the nearest of a finite set of levels. The number of bits per sample is the bit depth; $n$ bits give $2^n$ levels (e.g. 16-bit → 65 536 levels). Rounding introduces quantization error/noise; more bits → smaller error → higher dynamic range and quality.

Data Rate

Example (CD): $44100 \times 16 \times 2 = 1\,411\,200 \text{ bps} \approx 1.41 \text{ Mbps}$.

Summary

Sampling controls how often amplitude is captured (time axis, governed by Nyquist); quantization controls how precisely each value is stored (amplitude axis, governed by bit depth). Both determine audio quality and storage size.

Lossy vs Lossless Compression

Explanation

• Lossless compression removes only statistical/redundant information (e.g. repeated patterns) so the exact original can be reconstructed. Essential where every bit matters.
• Lossy compression also removes perceptually unimportant information (e.g. high-frequency detail the eye/ear cannot perceive). It achieves far higher ratios at the cost of irreversible quality loss, making it ideal for multimedia where small errors are acceptable.

Characteristics of Multimedia Data and Storage Requirements

Characteristics of Multimedia Data

1. Voluminous / large data size: Images, audio and especially video require huge amounts of data compared to text.
2. Diverse media types: Combines text, graphics, images, audio, video and animation, each with different formats.
3. Time-dependence (continuous media): Audio and video are time-based and must be played at a fixed rate; they require synchronization and have real-time constraints.
4. High bandwidth & processing demand: Capture, compression, transmission and playback need high data rates and computation.
5. Compressibility & redundancy: Contains spatial/temporal redundancy, so it is highly compressible (JPEG, MPEG).
6. Quality of Service (QoS) sensitivity: Tolerant of small errors but sensitive to delay and jitter.

Storage Requirements (examples)

Uncompressed size grows quickly:

• Image: $W \times H \times$ bytes/pixel. A $1024\times768$, 24-bit image $= 1024\times768\times3 \approx 2.36$ MB.
• Audio: $f_s \times$ bit depth $\times$ channels. CD audio $\approx 1.41$ Mbps $\approx 10.6$ MB/minute.
• Video: frame size $\times$ frame rate. A $640\times480$, 24-bit, 25 fps clip $\approx 640\times480\times3\times25 \approx 23$ MB per second uncompressed.

Because raw multimedia is so large, compression (lossy/lossless) and large, fast storage and bandwidth are essential.

Multimedia Synchronization

Multimedia synchronization is maintaining the correct temporal (and sometimes spatial) relationships among multiple media objects during presentation, so they are played in the intended order and timing (e.g. audio matching video). Without it, media drift apart (e.g. lip-sync errors).

Intra-media vs Inter-media Synchronization

Summary

Intra-media keeps a single stream's internal timing correct, while inter-media keeps different streams aligned with each other. Both are needed for a coherent multimedia presentation.