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

Multimedia Synchronization

Multimedia synchronization is the process of maintaining the correct temporal (time), spatial (position), and content relationships between different media objects (text, audio, video, images, animation) during their capture, storage, transmission, and presentation. Its purpose is to ensure that media are played back at the right time and in the right order, so the presentation is meaningful to the user (e.g., audio matching the lip movements in a video).

Intra-media (Intra-stream) Synchronization

This maintains the temporal relationship within a single continuous media stream.

• It ensures a fixed, constant playout rate for the units (frames/samples) of one stream.
• Example: a video must display its frames at a constant rate (e.g., 25 frames/second); audio samples must be played at a constant sampling rate (e.g., 44,100 samples/second).
• Failure causes jitter, frames appearing too fast/slow, or jerky playback.

Inter-media (Inter-stream) Synchronization

This maintains the temporal relationship between two or more different media streams.

• The most common case is lip synchronization (audio aligned with video). The tolerable skew is roughly $\pm 80$ ms before users notice the mismatch.
• It also covers relationships such as a slide appearing together with its narration, or subtitles matching speech.
• Failure causes audio leading/lagging the video, or annotations appearing at the wrong moment.

Reference Model for Multimedia Synchronization

A layered four-layer reference model is used to describe synchronization at different levels of abstraction:

Each layer offers an interface (service) to the layer above and uses the services of the layer below. The Specification Layer is open (no fixed implementation) and includes models like the Object Composition Petri Net (OCPN), timeline-based, and reference-point models for expressing how media should be coordinated.

Digital Image Representation and Color Models

Digital Image Representation

A digital image is a 2-D array (matrix) of pixels (picture elements). Each pixel stores a numeric value representing brightness/color.

• Spatial resolution: number of pixels (width $\times$ height), e.g., $1920 \times 1080$.
• Color/bit depth: number of bits per pixel. A grayscale image uses 8 bits (0–255); a true-color image uses 24 bits (8 bits each for R, G, B).
• Storage (uncompressed) $= \text{width} \times \text{height} \times \text{bytes per pixel}$.

Color Models

RGB (Red, Green, Blue) — an additive model used by displays, cameras and scanners. Colors are produced by adding red, green and blue light; $(0,0,0)$ = black, $(255,255,255)$ = white. Device-dependent.

CMYK (Cyan, Magenta, Yellow, Black) — a subtractive model used in color printing. Inks absorb (subtract) light; combining C, M, Y gives a muddy dark, so a separate K (black) channel is added for true black and detail. Conversion (simplified): $C = 1-R'$, $M = 1-G'$, $Y = 1-B'$ on normalized values, then $K = \min(C,M,Y)$.

YUV / YCbCr — separates luminance (Y = brightness) from chrominance (color). $Y$ carries the gray-scale information; $U/Cb$ and $V/Cr$ carry color difference. Conversion from RGB (BT.601):

This model exploits the fact that the human eye is more sensitive to brightness than to color, which is the basis for compression.

Color Sampling and Chroma Subsampling

Because the eye perceives less detail in color than in luminance, the chrominance channels can be sampled at a lower resolution than luminance — this is chroma subsampling. It reduces data with little visible quality loss. It is denoted as $J{:}a{:}b$ (luma:chroma in a $4\times2$ region):

Example: 4:2:0 stores one Cb and one Cr value for every $2\times2$ block of luma pixels, roughly halving the total data versus 4:4:4.

JPEG Image Compression Standard

JPEG (Joint Photographic Experts Group) is a widely used lossy compression standard for continuous-tone still images. It achieves high compression by discarding high-frequency detail the human eye cannot easily perceive.

Block Diagram (encoder)

Input Image -> Color Transform (RGB->YCbCr) -> 8x8 Block split
   -> [Forward DCT] -> [Quantization] -> [Zig-zag scan]
   -> [DC: DPCM] [AC: Run-Length] -> [Entropy (Huffman) coding] -> Compressed bitstream

Main Steps

1. Color transform and downsampling. RGB is converted to YCbCr, and the chroma channels are subsampled (commonly 4:2:0).

2. Block splitting. The image is divided into $8\times8$ pixel blocks, processed independently. Pixel values are level-shifted (subtract 128).

3. Forward DCT (Discrete Cosine Transform). Each $8\times8$ block is transformed from the spatial domain to the frequency domain:

The result is one DC coefficient (top-left, average value) and 63 AC coefficients. Energy is concentrated in the low-frequency (top-left) coefficients.

4. Quantization. Each DCT coefficient is divided by a value from a quantization table $Q$ and rounded:

High-frequency coefficients are divided by larger values, so many become zero. This is the lossy step and controls the quality/compression trade-off.

5. Zig-zag ordering. The $8\times8$ quantized block is read in a zig-zag pattern from low to high frequency. This groups the many trailing zeros together into a long run, making them easy to compress.

6. Entropy (Huffman) coding.

• The DC coefficient is coded differentially (DPCM) relative to the previous block's DC.
• The AC coefficients are run-length encoded as (run-of-zeros, value) pairs and then Huffman coded (variable-length codes giving short codes to frequent symbols). This is lossless.

At the decoder, the steps are reversed: entropy decoding -> de-zig-zag -> dequantization -> inverse DCT -> color transform back to RGB, reconstructing an approximation of the original image.

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 rarer symbols, minimizing the average code length. No code is a prefix of another, so the stream is uniquely decodable.

Algorithm

1. List all 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. Continue until one tree remains.
4. Label left edges 0 and right edges 1; the path from root to a leaf is that symbol's code.

Example

Symbols and frequencies: A=45, B=13, C=12, D=16, E=9, F=5 (total 100).

Building the tree (merge two smallest each step): F(5)+E(9)=14; C(12)+B(13)=25; 14+D(16)=30; 25+30=55; 55+A(45)=100.

Resulting codes:

Average length $= (45\cdot1 + 13\cdot3 + 12\cdot3 + 16\cdot3 + 9\cdot4 + 5\cdot4)/100 = 224/100 = 2.24$ bits/symbol, versus 3 bits with fixed-length coding — a clear saving. Decoding walks the tree bit-by-bit from the root until a leaf is reached.

Run-Length Encoding (RLE)

Run-length encoding is a simple lossless compression technique that replaces sequences of consecutive identical symbols (a run) with a single (symbol, count) pair. It is most effective on data with many long runs, such as simple graphics, fax images, and the long zero-runs in JPEG.

Working

Scan the data; whenever a value repeats consecutively, store it once together with the number of repetitions.

Example

Input string:

AAAAABBBCCDAA

RLE output (value, count):

5A 3B 2C 1D 2A   ->  encoded as: A5 B3 C2 D1 A2

The 13-character input is represented by 10 characters. For an image scan line like WWWWWWWWWWBBWWW (12 W, 2 B, ...), it becomes 12W2B3W, a large saving.

Note: RLE can expand data with few runs (e.g., ABCD becomes A1B1C1D1), so it works best on highly repetitive data.

Role of DCT and Quantization in JPEG

Discrete Cosine Transform (DCT)

The DCT converts each $8\times8$ block of pixels from the spatial domain to the frequency domain, producing one DC coefficient (the block's average) and 63 AC coefficients.

• It concentrates the image energy into a few low-frequency coefficients (top-left), while high-frequency coefficients are usually small.
• DCT itself is reversible/lossless (apart from rounding); it does not compress, it prepares the data so that the redundant high-frequency information can be removed efficiently.

Quantization

Quantization divides each DCT coefficient by a value from a quantization table and rounds the result:

• Larger divisors are used for high frequencies (which the eye is less sensitive to), so many small high-frequency coefficients become zero.
• This is the only lossy step in JPEG and the main source of compression; the quantization table (scaled by a quality factor) controls the quality vs. compression trade-off.
• The resulting blocks of zeros are then efficiently compressed by zig-zag scanning, run-length and Huffman coding.

Summary: DCT re-organizes the data by frequency so that quantization can discard perceptually unimportant high-frequency detail, enabling high compression with little visible loss.

I-frames, P-frames and B-frames in MPEG

MPEG video compresses a sequence using three frame (picture) types arranged in a Group of Pictures (GOP), exploiting both spatial and temporal redundancy.

I-frame: a self-contained reference frame; needed for random access (seeking) and to start/refresh a GOP.

P-frame: stores only the motion vectors and differences relative to a preceding reference frame, giving good compression.

B-frame: interpolated from frames before and after it, giving the highest compression; this requires the encoder/decoder to reorder frames (decode order differs from display order).

A typical GOP display order: I B B P B B P B B P ...

RGB vs CMYK Color Models

Key idea: RGB is device-of-light based — increasing all values moves toward white. CMYK is ink/pigment based — increasing values absorbs more light and moves toward black. A separate K (black) channel is added in CMYK because mixing C, M, Y inks yields a muddy brown rather than true black, and using black ink also saves the costlier colored inks. Images created in RGB on screen must be converted to CMYK for accurate printing, which may shift some out-of-gamut colors.

Sampling and Quantization of Digital Audio

Converting an analog (continuous) audio signal into digital form requires two steps performed by an Analog-to-Digital Converter (ADC): sampling (discretizing time) and quantization (discretizing amplitude).

Sampling

Sampling measures the amplitude of the continuous signal at regular time intervals. The number of samples per second is the sampling rate / frequency ($f_s$), measured in Hz.

• By the Nyquist–Shannon theorem, $f_s$ must be at least twice the highest frequency in the signal to avoid aliasing: $f_s \ge 2f_{max}$.
• Human hearing extends to ~20 kHz, so CD-quality audio uses $f_s = 44{,}100$ Hz (44.1 kHz).

Quantization

Each sampled amplitude is rounded to the nearest of a finite set of levels, represented by a fixed number of bits — the bit depth $n$. The number of levels $= 2^n$.

• 8-bit gives 256 levels; 16-bit (CD quality) gives $65{,}536$ levels.
• The rounding error is called quantization error/noise; more bits = smaller error and higher signal-to-noise ratio.

Storage / Bit Rate

Example (CD stereo): $44{,}100 \times 16 \times 2 = 1{,}411{,}200$ bits/s $\approx 1.41$ Mbps.

Together, sampling rate and bit depth determine the quality and size of the digital audio.

Lossy vs Lossless Compression

Lossless is essential where every bit matters (e.g., executables, text, medical imaging) — the decompressed file is bit-for-bit identical to the original.

Lossy sacrifices unimportant detail (exploiting limits of human vision/hearing) to achieve far higher compression, which is acceptable for everyday photos, music and video where small quality loss is unnoticeable.

Characteristics of Multimedia Data and Storage Requirements

Characteristics of Multimedia Data

1. Large volume / high data size — images, audio and especially video produce huge amounts of data, demanding large storage and high bandwidth.
2. Real-time / continuous nature — audio and video are continuous (time-dependent) media that must be captured and played back at a fixed rate; late data is useless.
3. Temporal requirements / QoS — needs guaranteed throughput, low delay and low jitter; requires intra- and inter-media synchronization.
4. Heterogeneity — combines different media types (text, graphics, image, audio, video, animation) with different formats and needs.
5. Voluminous and compressible — contains much redundancy, so it is usually stored/transmitted in compressed form (JPEG, MPEG, MP3).
6. Interactivity — often requires random access, fast-forward, rewind and user interaction.

Storage Requirements (with examples)

Uncompressed multimedia is very large. Storage size formulas:

• Image: $\text{size} = \text{width} \times \text{height} \times \text{bytes/pixel}$. Example: a $1024 \times 768$ 24-bit image $= 1024 \times 768 \times 3 \approx 2.36$ MB.
• Audio: $\text{rate} \times \text{bit depth} \times \text{channels}$. CD stereo $= 44{,}100 \times 16 \times 2 \approx 1.41$ Mbps, i.e. ~10 MB per minute.
• Video: frame size $\times$ frames/sec. Raw SD video can exceed 20 MB/second (over 1 GB/minute).

Because of these sizes, multimedia systems rely heavily on compression and on storage/transmission media with large capacity and high transfer rates (e.g., DVD, Blu-ray, SSDs, streaming servers with QoS).

Multimedia Synchronization: Intra-media vs Inter-media

Multimedia synchronization is the maintenance of the correct temporal, spatial and content relationships between media objects during capture, storage, transmission and, most importantly, playback, so the presentation is coherent (e.g., sound matching the picture).

Difference between Intra-media and Inter-media Synchronization

In short: intra-media synchronization ensures each individual stream plays smoothly at its own correct rate, whereas inter-media synchronization ensures separate streams stay coordinated with one another.