Cheat Sheet

One dense page for the night before the CBE412 exam: formulas and numbers, text compression, JPEG and PNG pipelines, audio and video facts, QoS, image forensic techniques, steganography, steganalysis and watermarking.

Formulas marked (std) are standard definitions that are not written on the slides. Use them for numerical questions; everything else is from the decks.

Formulas and numbers Search on YouTube

Quantity	Formula	Slide or exam number	Lecture
Compression ratio (std)	$CR = \dfrac{\text{original size}}{\text{compressed size}}$	JPEG example: 40 MB → 4 MB, so $CR = 10:1$	L02
Space saving (std)	$1 - \dfrac{\text{compressed}}{\text{original}}$	40 MB → 4 MB saves 90%	L02
Uncompressed text	characters × 8 bits (ASCII)	"Mississippi": $11 \times 8 = 88$ bits	L01
Fixed-length code	characters × $\lceil \log_2(\text{symbols}) \rceil$	4 symbols → 2 bits: $11 \times 2 = 22$ bits	L01
Huffman total bits	$\sum f_i \, \ell_i$	Mississippi: $1 \cdot 3 + 2 \cdot 3 + 4 \cdot 2 + 4 \cdot 1 = 21$ bits	L01
Average code length	total bits / characters	$21/11 = 1.909$ bits/char	L01
Entropy (std)	$H = -\sum p_i \log_2 p_i$	Mississippi: $H \approx 1.823$ bits/char (Huffman 1.909 ≥ H)	L01
Huffman on pixels	bits per pixel	64 pixels, 4 values: $(25 + 42 + 42 + 12)/64 = 1.89$ bpp vs 2 bpp fixed	L02
Nyquist rate	$f_s \ge 2 f_{max}$	500 Hz and 750 Hz tones → $f_s \ge 1500$ Hz	L03
Nyquist frequency	$f_s / 2$	44.1 kHz → 22.05 kHz; 48 kHz → 24 kHz; 96 kHz → 48 kHz	L03
Quantization levels	$2^{n}$ for $n$ bits	3 bits → 8; 8 bits → 256; 16 bits → 65,536; 24 bits → 16,777,216	L03
Audio bitrate (std)	$f_s \times \text{bit depth} \times \text{channels}$	CD: $44{,}100 \times 16 \times 2 = 1{,}411{,}200$ bit/s	L03
Audio file size (std)	bitrate × seconds / 8	1 min of CD audio: $1{,}411{,}200 \times 60 / 8 = 10{,}584{,}000$ B ≈ 10.6 MB	L03
Video bitrate (std)	samples per frame × bits × fps	PAL MPEG: $(352 \cdot 288 + 2 \cdot 176 \cdot 144) \times 8 \times 25 \approx 30.4$ Mbit/s	L05
Image size (std)	width × height × bytes per pixel	$512 \times 512$ gray LSB stego holds $262{,}144$ bits = 32 KB	L06
MSE (std)	$MSE = \frac{1}{MN}\sum_{i,j} (I_{ij} - K_{ij})^2$	LSB on half the pixels (each ±1): $MSE = 0.5$	L06
PSNR (std)	$PSNR = 10 \log_{10} \dfrac{255^2}{MSE}$ dB	$MSE = 0.5$ → 51.14 dB; $MSE = 1$ → 48.13 dB	L06
Deterministic QoS	$QoS : T \rightarrow R$	$T$ = duration, $R$ = positive reals	L05
Pair of values	$QoS_{min} \le QoS(t) \le QoS_{max}$	15 to 30 fps; unacceptable if $QoS(t) < QoS_{min}$	L05
Predictable class	$B^{p} = \frac{1}{L}\sum_{i=n-L}^{n} B_i$	$(8 + 11 + 9)/3 = 9.33 \approx 9$ Mbit/s with $L = 3$	L05
Motion vector	(dx, dy) of a macroblock	Block moves 5 right and 3 down → $(+5, +3)$	L03

The slide's 1 Hz example says "more than 2 samples per second, say 3 Hz". The theorem says "at least twice". If asked for the minimum, write $2 f_{max}$ and add that a rate slightly above it is used in practice (guard band).

Text compression (L01)Search on YouTube

Method	Output	Key rule
Huffman	Variable-length prefix codes	Merge the two lowest frequencies repeatedly; frequent symbols get short codes. Lossless.
LZ77	Triplets (offset, length, next symbol)	Window = search buffer + look-ahead buffer. Offset counted back from the dividing line. No match → `(0, 0, c)`.
LZSS	Literal or (offset, length) pair	No forced next symbol. Only back-references that pay off; otherwise a literal.
RLE	count + value	`WWWWWWWWBBBBBBBBZWK` style runs → `8W-12B-1Z-1W-1K` (slide); pixels `95 95 95 95` → `4 x 95`

LZ77 slide example: cabracadabrarrarrad, window 13, look-ahead 6, search 7 → (0,0,c)(0,0,a)(0,0,b)(0,0,r)(3,1,c)(2,1,d)(7,4,r)(3,5,d).
LZ77 exercise: repetitive_repeat, search 11, look-ahead 4 → (0,0,r)(0,0,e)(0,0,p)(2,1,t)(0,0,i)(2,2,v)(6,1,_)(11,4,a)(10,1,$) ($ marks end of input).
LZSS on the same string: r e p 2 1 t i 2 2 v 6 1 11 4 a 10 1.
LZSS efficiency (std): compressed bytes = literals × 1 + pointers × 2 (End Sem 2025 assumption); $CR$ = original bytes / compressed bytes.
PNG's LZSS (DEFLATE) uses a 32 KB sliding window and a 258-byte look-ahead.

JPEG pipeline (lossy) (L02)Search on YouTube

Colour space conversion: RGB → Y (luminance), Cb, Cr (chrominance). Reversible, no loss.
Chrominance downsampling: keep Y; average Cb and Cr over every 2 x 2 block, so each becomes one quarter. Ratio Y : Cb : Cr = 1 : 1/4 : 1/4. First real data loss.
DCT: split into 8 x 8 blocks, subtract 128 (range −128 to 127), transform to frequency coefficients. No data thrown away yet. Energy concentrates in low frequencies (top left).
Quantization: divide by the quantization table and round. Small divisors for low frequencies, large for high. Actual compression happens here; most high-frequency values become 0.
Run-length and Huffman coding: zigzag scan, RLE for zero runs, Huffman for the result.

C D D Q E: "Colour Down DCT Quantize Entropy-code". Loss happens at Downsampling and Quantization only.

Camera pipeline before JPEG: lens → aperture → shutter → CFA → sensor → processing unit → storage. Bayer CFA is R : G : B = 1 : 2 : 1 (25% R, 50% G, 25% B), because the eye is most sensitive to green; demosaicing fills missing colours. Rods ≈ 100 million (light), cones ≈ 6 million (colour). Faster shutter → less motion blur, less light. RAW keeps all sensor data; JPEG drops data for smaller files.

PNG pipeline (lossless) (L02)Search on YouTube

Encode: filtering → LZSS → Huffman → PNG file. Decode: Huffman decoding → reverse LZSS → reverse filtering.

Why each stage: Huffman alone ignores spatial redundancy; RLE fails when repeats are patterns, not runs; LZSS back-references handle repeated patterns but fail on smooth gradients; filtering turns gradients (0, 4, 8, ...) into repeats (0, 4, 4, 4, ...) that LZSS compresses.

Neighbours: $a$ = left, $b$ = above, $c$ = above-left. All results are mod 256.

Filter	Output for pixel $x$	Slide check
None	$x$	unchanged
Sub	$x - a$	127 128 139 134 → 127 1 11 251
Up	$x - b$	131 − 127 = 4; 129 − 139 = −10 → 246
Average	$x - \lfloor (a + b)/2 \rfloor$	slide rounds .5 up: 129 − 66 = 63
Paeth	$x - P$ , where $P$ is whichever of $a, b, c$ is closest to $p = a + b - c$ (ties: $a$ , then $b$ , then $c$ )	first pixel 139 − 133 = 6; next 128 − 139 → 245

The PNG standard uses floor in the Average filter. The slide's example rounds 0.5 up (129 − 65.5 → 63). In an exam, state which rule you use.

Audio and video (L03)Search on YouTube

Media formats on the slides Search on YouTube

Format or standard	Media	Type	Notes
RAW	Image	Unprocessed	All sensor RGB intensity per pixel; most detail, most storage
JPEG	Image	Lossy	DCT + quantization; 40 MB → 4 MB example
PNG	Image	Lossless	Filtering + LZSS + Huffman; good for graphics
BMP, PPM	Image	Uncompressed	Stego size does not change (lab)
PCM	Audio	Lossless encoding	Sampling → quantization → encoding into a bitstream
WAV, AU	Audio	Usually uncompressed PCM	Steghide supports them
MPEG-2	Video	Lossy	DVD and broadcast; GOP 12 to 18
MPEG-4 / H.264 (AVC)	Video	Lossy	Streaming GOP 30 to 60; editing GOP 12 to 15
H.265	Video	Lossy	Real-time GOP 10 to 15 (IPPP...); archival GOP 60 to 120

Video numbers Search on YouTube

Item	Value
Frame rates	30 fps TV; 60 fps games and smooth video; slow motion = capture 240, display 24
Fluid motion from	12 to 15 fps
Flicker-free refresh	at least 50 Hz
Resolutions	720p 1280x720 (HD); 1080p 1920x1080 (Full HD); 2K 2048x1080; 4K 3840x2160 (UHD)
Aspect ratios	4:3 (1.33) SD; 16:9 (1.78) HD; 21:9 (2.39) CinemaScope; 1.85 theatrical; 1:1 square; 9:16 vertical
Component coding	Y sampled at 13.5 MHz, chroma at 6.75 MHz, 8 bits (256 levels)
MPEG sampling	4:1:1 (Y:Cb:Cr); blocks 16x16 for Y, 8x8 for Cb and Cr
MPEG PAL / NTSC	Y 352x288, chroma 176x144 / Y 352x240, chroma 176x120

	NTSC	PAL
Resolution	720 x 480	720 x 576
Frame rate	29.97 (≈30) fps	25 fps
Scan lines	525	625
Lines per field	262.5	312.5
Fields per second	59.94	50
Mains grid	60 Hz (US, Canada, Japan)	50 Hz (Europe, Australia, parts of Asia and Africa)

MPEG flow: input frames and colour conversion → motion estimation and compensation (temporal) → spatial compression (8x8 DCT, quantization) → entropy coding (RLE, Huffman). JPEG uses spatial redundancy only; MPEG = spatial + temporal.

Frame	Coded from	Size
I (intra)	Itself only; anchor and random-access point	Largest
P (predicted)	Previous I or P (forward prediction)	Medium
B (bi-directional)	Previous and next I or P	Smallest

Long GOP (30+): better compression, worse seeking and error resilience. Short GOP (≤12): better random access and resilience. Motion search uses 16x16 macroblocks and SAD.

Audio numbers Search on YouTube

Range	Frequency
Infrasound	0 to 20 Hz (earthquakes, elephants, whales)
Audible	20 Hz to 20 kHz (most multimedia)
Ultrasound	20 kHz to 1 GHz (fetal imaging, bats, dolphins)
Hypersound	1 GHz to 10 THz (non-destructive testing, acoustic microscopy)

Sample rate	Nyquist frequency	Guard band above 20 kHz cut-off
44.1 kHz	22.05 kHz	2.05 kHz
48 kHz	24 kHz	4 kHz
96 kHz	48 kHz	28 kHz

Wave parameters: frequency (cycles per second, pitch), amplitude (loudness), phase (start position).
Sampling is lossless (mathematically, with band-limiting by a low-pass filter); quantization is lossy and adds quantization noise. More bits → smaller error.
A higher sampling rate is not the same as better quality. Sampling 4 kHz at 8 kHz puts every sample at 0.
Pulse modulation: width (PWM), position (PPM), amplitude (PAM), code (PCM: each sample as an 8-bit code).

QoS and resource management (L05)Search on YouTube

Topic	Key items
Stream handling	Scaling/adaptation (ABR, Netflix) vs resource reservation (VoIP)
Deadlines	Soft (some misses tolerated) vs hard (miss = system failure)
Real-time traits	Predictably fast response, high schedulability, stability under transient overload
Constraints	Data movement, segmentation and reassembly, error recovery
QoS layers	Perceptual, application, system, device, network
Service objects	Media sources, connections, virtual circuits
Parameterization	ISO, Tenet, METS, RSVP, OS, middleware
Spec approaches	Script, parameter, process, control logic, aspect, object
Service classes	Guaranteed (single, pair, triple values), predictable ( $B^p$ ), best effort
Resources	Active/passive, exclusive/shared, single/multiple
Phases	Establishment, runtime
Requirements	Throughput, delay (local, end-to-end), jitter, reliability
Network load / performance	Inter-arrival time, burstiness, packet size, service time / delay, loss, jitter (traffic envelope)
Media server	Sequential access, real time, high bandwidth, buffering; pull (client, YouTube) vs push (server, live TV)

Image forensic techniques (L04)Search on YouTube

Technique	Principle	Detects	Limits
Metadata (EXIF, IPTC, XMP)	Read camera, time, GPS, software, history (`exiftool`)	Conflicting time or GPS, editing software, altered fields	Stripped (WhatsApp), spoofed GPS, time zones
Error level analysis	Re-save at known quality, subtract, normalize	Spliced or added regions with different compression	Textures and edges; poor on faces
Key point matching (SIFT, SURF)	Stable keypoints + descriptors matched inside the image	Copy-move (cloning)	SURF faster, SIFT more accurate
PRNU	Sensor noise fingerprint correlated with camera reference	Source camera, computer-generated, splicing	Needs many images from the same camera
Statistical analysis	Histograms, mean/variance/correlation, noise, DCT blocks, colour channels, Fourier/wavelet	Any disturbance of natural statistics	Needs a baseline
Shadow analysis	Sun position (SunEarthTools) or light-source geometry	Wrong place or time, spliced objects	Needs visible shadows
Deepfake checks	Face, movement, audio, context, eye blinking	AI face swaps (shared encoder, two decoders)	Arms race

Forgery map: copy-move → SIFT/SURF; splicing → ELA, PRNU, shadows; inpainting → ELA, statistics, noise.

Steganography versus watermarking (L06)Search on YouTube

Aspect	Steganography	Watermarking
Goal	Hide that a message exists	Prove ownership or authenticity
Data	Unrelated to the cover	Related to the cover
Value	The message; the cover is secondary	The cover; the mark adds information
Main property	Statistical undetectability (Cachin: $P_S = P_C$ )	Robustness and fidelity
Payload	As large as possible while undetectable	Small (benchmark: 80 bits)
Success if found?	No	Yes, if it cannot be removed
Tools and methods	LSB, OutGuess (DCT LSB + histogram fix), Steghide, model-based	E_BLIND, side information, spread spectrum, redundant, mid-frequency DCT

Stego building blocks: cover work; embed/extract (symbol assignment, modification, selection rule); stego key.
Embedding principles: cover lookup, cover synthesis (SpamMimic), cover modification (sequential, pseudo-random, adaptive).
Practical methods: statistics-preserving, model-based ( $P(c_{emb} \mid c_{inv})$ ), masking as natural processing.
Watermark properties: effectiveness, fidelity, payload; blind vs informed detection, false positives, robustness; modifiability; costs; security.
Watermark models: basic (cover as noise, $c_w = c_o + w_a$ ), side information (stronger in dark areas), multiplexed (two messages).
Robust embedding: redundant, spread spectrum, perceptually significant (mid-frequency) coefficients, known-robust domains (Fourier magnitudes for shifts, DCT for linear filtering).
Applications: copy prevention, copyright protection, broadcast monitoring, transaction tracking, owner identification, proof of ownership, content authentication.

Attacks Search on YouTube

Target	Attack	Effect or counter
Stego (warden)	Passive warden: inspect, drop if suspicious	Blind or targeted detection
Stego (warden)	Active warden: modify every message	Destroys hidden data even if undetected
Stego (warden)	Malicious warden: detect and impersonate Alice or Bob	Needs the algorithm
Stego (steganalysis)	Targeted: SAD feature for LSB; chi-square on pairs $(2k, 2k+1)$	Beaten by statistics-preserving tools (OutGuess, Steghide)
Stego (steganalysis)	Blind: classifier on many algorithms or one-class on covers; universal features (noise, correlation, transforms)	Fails on unseen algorithms
Stego (lab)	Brightness change, crop, JPEG re-save	Destroyed Steghide and OutGuess payloads; rename did not
Watermark (hostile)	Unauthorized removal, embedding, detection	Keys, content binding, redundant spread-spectrum marks
Watermark (processing)	Compression, cropping, filtering, rotation, spatial shifts, D/A conversion, format change	Redundant embedding, spread spectrum, mid-frequency, Fourier/DCT domains
Images (forgery)	Copy-move, splicing, inpainting, AI generation, metadata stripping or GPS spoofing	See the forensic techniques table

Trade-offs to quote Search on YouTube

Payload up → false positives up. Robustness up → fidelity down. Lower detection threshold → more robust but more false positives. Higher embedding strength → more robust but more visible.
Long GOP → compression up, seeking down. Short GOP → the reverse.
More quantization bits → less noise, larger file. Higher sampling rate ≠ better audio.
Guaranteed QoS → reliable but reserves resources; best effort → high utilization, no guarantee.

Formulas and numbersSearch on YouTubeBookmarkSaved

Text compression (L01)Search on YouTubeBookmarkSaved

JPEG pipeline (lossy) (L02)Search on YouTubeBookmarkSaved

PNG pipeline (lossless) (L02)Search on YouTubeBookmarkSaved

Audio and video (L03)Search on YouTubeBookmarkSaved

Media formats on the slidesSearch on YouTubeBookmarkSaved

Video numbersSearch on YouTubeBookmarkSaved

Audio numbersSearch on YouTubeBookmarkSaved

QoS and resource management (L05)Search on YouTubeBookmarkSaved

Image forensic techniques (L04)Search on YouTubeBookmarkSaved

Steganography versus watermarking (L06)Search on YouTubeBookmarkSaved

AttacksSearch on YouTubeBookmarkSaved

Trade-offs to quoteSearch on YouTubeBookmarkSaved

On this page