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

Entropy and Source Coding for Multimedia

Entropy measures the average information content (uncertainty) of a source. For a source emitting symbols $s_i$ with probability $p_i$, Shannon's entropy is:

Entropy is the theoretical lower bound on the average number of bits per symbol for lossless coding. Source coding removes statistical redundancy so the average code length approaches $H$.

Huffman Coding

A prefix, variable-length code built by repeatedly merging the two least-probable symbols into a binary tree; shorter codes are assigned to frequent symbols. It is optimal among integer-length prefix codes, with average length satisfying $H \le \bar{L} < H+1$.

Run-Length Encoding (RLE)

Replaces runs of identical symbols by a (value, count) pair, e.g. AAAAB -> (A,4)(B,1). Very effective for data with long uniform runs (fax, simple graphics) but poor for noisy data.

Arithmetic Coding

Encodes an entire message as a single fractional number in $[0,1)$ by successively narrowing an interval according to symbol probabilities. It can use fractional bits per symbol and so approaches the entropy bound more closely than Huffman, especially for skewed or small alphabets.

Worked Huffman Example

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

1. Merge F(5)+E(9)=14
2. Merge C(12)+B(13)=25
3. Merge 14+D(16)=30
4. Merge 25+30=55
5. Merge A(45)+55=100

Resulting codes (one valid assignment):

Average length $\bar{L} = (45\cdot1+12\cdot3+13\cdot3+5\cdot4+9\cdot4+16\cdot3)/100 = 224/100 = 2.24$ bits/symbol, compared with 3 bits for fixed-length coding.

Digital Audio Representation

Sound is a continuous (analog) pressure wave. To process it digitally it must be sampled (discretized in time) and quantized (discretized in amplitude).

Sampling

The analog signal is measured at regular intervals at the sampling rate $f_s$. By the Nyquist theorem, $f_s \ge 2 f_{max}$ to avoid aliasing (e.g. CD audio uses 44.1 kHz to cover the 20 kHz audible range).

Quantization

Each sample's amplitude is rounded to one of $2^n$ levels for $n$-bit resolution (e.g. 16-bit = 65,536 levels). Quantization introduces quantization noise; signal-to-noise ratio improves about 6 dB per bit.

PCM (Pulse Code Modulation)

The standard uncompressed representation: a stream of quantized sample values. Bit rate $= f_s \times n \times \text{channels}$. CD stereo $= 44100 \times 16 \times 2 \approx 1.41$ Mbps.

Audio Compression and MPEG Audio (MP3)

• Lossless (FLAC, ALS) removes redundancy only.
• Lossy (MP3 = MPEG-1/2 Layer III) removes perceptually irrelevant data.

MP3 pipeline: the signal is split into frequency sub-bands using a filter bank and MDCT; a psychoacoustic model analyses each frame to decide what can be discarded; bits are allocated and quantized accordingly; finally Huffman coding packs the result. MP3 achieves roughly 10:1–12:1 compression with near-transparent quality at 128 kbps.

Role of Psychoacoustic Models

They exploit limits of human hearing:

• Absolute threshold of hearing — very quiet tones are inaudible.
• Frequency (simultaneous) masking — a loud tone hides nearby weaker tones.
• Temporal masking — sounds before/after a loud sound are masked.

Bits are allocated so that the quantization noise stays below the computed masking threshold, making the loss inaudible.

Multimedia System

A multimedia system is a computer-based system that can capture, store, process, transmit and present information in more than one medium — combining text, graphics, images, audio, video and animation in an integrated, often interactive, way.

Characteristics of Multimedia Data

• Large volume / high storage demand (especially audio and video).
• High bandwidth for transmission.
• Real-time and continuous nature — audio/video must be played within timing (latency, jitter) constraints.
• Time dependency / synchronization — media streams (e.g. lip-sync) must stay aligned.
• Heterogeneity — different media have different data and processing requirements.

Storage and Coding Requirements

Raw multimedia is huge: uncompressed CD audio is ~1.4 Mbps and SD video can exceed 100 Mbps. Therefore systems rely on compression/coding (JPEG, MPEG, MP3, H.264) to reduce storage and bandwidth, plus fast storage with high sustained throughput (SSD/RAID) and indexing for random access.

Components of a Multimedia Computing System

• Hardware: capture devices (camera, microphone, scanner), high-speed CPU/GPU, large RAM, fast storage, sound/graphics cards, display and audio output.
• Software: operating system with multimedia/real-time support, codecs, authoring tools (e.g. Adobe), media players and editors.
• Storage media: hard disks, SSDs, optical media, cloud storage.
• Networking/communication: high-bandwidth networks and streaming protocols (RTP/RTSP) for delivery.
• Compression standards that tie the components together.

Entropy in coding is the average information content of a source, $H = -\sum_i p_i \log_2 p_i$ bits per symbol, representing the minimum average number of bits needed to losslessly encode each symbol.

Relation to compression: Entropy is the theoretical lower bound for lossless compression. A good entropy coder (Huffman, arithmetic) produces an average code length approaching $H$. Low-entropy (highly predictable/redundant) data compresses well; high-entropy (random) data cannot be compressed below $H$.

Arithmetic coding represents an entire message as a single number (interval) in $[0,1)$. Starting from the full interval, it is recursively subdivided in proportion to each symbol's probability; the final interval (or any number inside it) encodes the whole message. It can assign fractional bits per symbol.

Differences from Huffman coding:

Arithmetic coding generally achieves better compression but is computationally heavier and historically encumbered by patents.

Motion estimation and motion compensation exploit temporal redundancy between successive video frames, since consecutive frames are usually very similar.

Motion estimation: Each frame is divided into blocks (e.g. 16x16 macroblocks). For each block in the current frame, the encoder searches a region of a reference frame for the best-matching block, producing a motion vector (the displacement) — typically using block-matching with a criterion such as minimum SAD/MSE.

Motion compensation: Using the motion vectors, the encoder predicts the current frame from the reference frame. Only the motion vectors and the small residual (prediction error) are encoded (the residual is then DCT-transformed and quantized).

This greatly reduces bit rate and is fundamental to P-frames and B-frames in MPEG/H.26x codecs.

MP3 Audio Compression

MP3 (MPEG-1/2 Audio Layer III) is a lossy audio compression format. The audio is divided into short frames, transformed into the frequency domain using a polyphase filter bank and MDCT, then quantized and Huffman coded. It typically gives 10:1–12:1 compression, with near-CD quality at about 128 kbps, by discarding perceptually irrelevant data rather than statistically redundant data.

Psychoacoustic Models

MP3's quality relies on a psychoacoustic model of human hearing:

• Absolute threshold of hearing: sounds quieter than the threshold are removed.
• Frequency masking: a strong tone makes nearby weaker tones inaudible.
• Temporal masking: sounds just before/after a loud sound are masked.

The model computes a masking threshold for each frame; the encoder allocates bits and sets quantization so that the resulting noise stays below this threshold, keeping the loss inaudible while saving bits.

Computer animation is the technique of creating the illusion of movement by rapidly displaying a sequence of images (frames) generated or manipulated by a computer, exploiting persistence of vision.

Frame-based vs Key-frame animation:

In key-frame animation the animator sets the start and end states (position, scale, colour) at key frames and the software computes the intermediate frames.

Hypermedia is an extension of hypertext in which the nodes and links connect not only text but also other media — images, audio, video, graphics and animation — allowing non-linear navigation through multimedia content (e.g. the modern World Wide Web).

Hypertext vs Hypermedia:

In short, hypermedia = hypertext + multimedia: every hypermedia system is hypertext-based, but hypertext deals only with linked text.

Multimedia Streaming

Streaming delivers audio/video so that playback begins while the rest of the content is still being downloaded, instead of waiting for a full download. A small buffer absorbs network variation; protocols such as RTP/RTSP or adaptive HTTP streaming (HLS, MPEG-DASH) are used. It may be on-demand (stored media) or live.

Issues Involved

• Bandwidth limitation: the network may not sustain the required data rate, causing rebuffering.
• Latency and delay: especially critical for live/interactive streams.
• Jitter: variable packet delay disrupts smooth playback; handled by buffering.
• Packet loss: UDP-based streaming may drop packets, degrading quality; needs error concealment/FEC.
• Synchronization: keeping audio and video (lip-sync) aligned.
• Heterogeneous clients: varying device/network capabilities require adaptive bit-rate streaming.
• QoS / continuous real-time delivery must be maintained.

Discrete Cosine Transform (DCT)

The DCT transforms a block of spatial-domain pixel values into the frequency domain, expressing the block as a sum of cosine basis functions. For an $N\times N$ block (JPEG uses $8\times8$), the 2-D forward DCT is:

where $C(k)=1/\sqrt{2}$ for $k=0$ and $1$ otherwise. $F(0,0)$ is the DC coefficient (average); the rest are AC coefficients of increasing frequency.

Importance in Image Compression

• It concentrates energy into a few low-frequency coefficients (energy compaction).
• Human eyes are less sensitive to high frequencies, so after the DCT those coefficients can be heavily quantized (set to zero), giving large compression.
• The DCT itself is lossless and reversible; loss happens only in the quantization step.
• It is the core transform of JPEG and MPEG image/video coding.

Common Multimedia File Formats

JPEG (.jpg): A lossy image format using DCT-based compression with adjustable quality. Excellent for photographs and natural images (24-bit colour) but introduces artifacts and is unsuitable for sharp-edged graphics/text. Does not support transparency.

GIF (.gif): A lossless image format limited to an 8-bit (256-colour) palette using LZW compression. Supports transparency and simple animation; best for logos, icons and small animations, poor for photographs.

PNG (.png): A lossless format supporting up to 24/32-bit colour with alpha transparency and better compression than GIF (DEFLATE). Ideal for web graphics and images needing transparency, but no native animation and larger than JPEG for photos.

MPEG (.mpg/.mp4): A family of lossy video/audio compression standards (MPEG-1/2/4, H.264) using DCT plus motion estimation/compensation to exploit temporal redundancy. Used for DVD, digital TV and streaming video.