Digital Image Processing (AD-603 (B)) Unit 4 Notes

How unit 4 is examined

This unit covers image compression (encoding model, lossless, lossy, JPEG) and segmentation by discontinuity (points, lines, edges, linking, Hough transform); no question has been asked recently, so every topic is short.

Encoding: Mapping, Quantizer, Coder

Not asked since 2022

Definition. Image encoding compresses an image in three stages: a mapper removes interpixel redundancy, a quantizer reduces accuracy, and a symbol coder assigns short codes to frequent values.

Key points.

The mapper converts pixels into a form that is easier to compress, such as differences or transform coefficients, and it is reversible.
The quantizer rounds the mapped values to fewer levels, which removes psychovisual redundancy but is irreversible, so it is dropped in lossless coding.
The symbol coder gives short variable-length codes to frequent symbols, which removes coding redundancy.
The decoder applies the inverse coder and inverse mapper only.

Error free compression

Definition. Error-free (lossless) compression reduces the data so that the decoded image is identical to the original.

Key points.

Huffman coding builds a binary tree by repeatedly merging the two least probable symbols, giving the shortest average code length.
Run-length encoding (RLE) stores each run of equal pixels as a (value, count) pair, so it suits binary and cartoon images.
The average code length is $L_{avg}=\sum p_k l_k$, and it can never fall below the entropy $H=-\sum p_k\log_2 p_k$.
Compression ratio is $C_R = n_1/n_2$ (original bits over compressed bits).

Lossy Compression schemes

Definition. Lossy compression discards some information, so the decoded image only approximates the original, in return for a much higher compression ratio.

Key points.

Quantization is the step that loses information, and it is applied to prediction errors or transform coefficients.
Predictive coding (DPCM) sends only the difference between a pixel and its prediction, quantized coarsely.
Transform coding (DCT) moves the image to the frequency domain and drops the small high-frequency coefficients.
Fidelity is judged by the error $e_{rms}=\sqrt{\frac{1}{MN}\sum (\hat f-f)^2}$ or by visual quality.

JPEG Compression standard

Definition. JPEG is the lossy standard that applies the 8x8 block DCT, quantizes the coefficients, and entropy-codes the result.

Steps.

Step 1: Split the image into 8x8 blocks and level-shift by subtracting 128.
Step 2: Apply the 2-D DCT to each block.
Step 3: Divide by the quantization table and round (the lossy step).
Step 4: Zigzag scan the coefficients and code the DC term by DPCM.
Step 5: Run-length and Huffman code the AC terms.

Key points.

Most energy sits in the low-frequency corner, so high-frequency coefficients quantize to zero.
A larger quantization step gives higher compression and lower quality.

Detection of discontinuation by point detection, Line detection, edge detection

Definition. Segmentation by discontinuity partitions an image at sudden intensity changes, found by convolving with a mask and thresholding the response.

Key points.

Point detection uses the Laplacian-type mask with centre 8 and eight neighbours -1, and flags a point where $|R|\ge T$.
Line detection uses four masks (horizontal, +45, vertical, -45) with weights 2 on the line and -1 elsewhere, and the largest response gives the direction.
An edge is a set of pixels where intensity changes abruptly, detected by the first derivative (gradient) or the second derivative (zero crossing).
Gradient magnitude is $\nabla f\approx|G_x|+|G_y|$, using Sobel or Prewitt masks.

Edge linking and boundary detection, Local analysis

Definition. Edge linking joins detected edge pixels into continuous boundaries, and local analysis links a pixel to its neighbours in a small window by similarity.

Key points.

Edge pixels are rarely continuous because of noise and breaks, so linking is needed after detection.
For a pixel $(x,y)$ and neighbour $(x_0,y_0)$, they are linked if gradient magnitudes differ by at most a threshold $T$: $|\nabla f(x,y)-\nabla f(x_0,y_0)|\le T$.
They must also have similar gradient direction: $|\alpha(x,y)-\alpha(x_0,y_0)|\le A$.
Linked points form a boundary, and the process is repeated over all pixels.

Global processing via Hough transforms and graph theoretic techniques

Definition. The Hough transform finds lines globally by letting every edge point vote in a parameter space, and the peaks in that space give the lines.

Key points.

A point $(x_i,y_i)$ lies on lines $y_i=ax_i+b$, which is a straight line in the $(a,b)$ plane, and collinear points give intersecting lines.
The normal form $\rho=x\cos\theta+y\sin\theta$ avoids infinite slope, and each point traces a sinusoid in $(\rho,\theta)$.
An accumulator array counts votes, and cells with high counts are the lines.
Graph-theoretic methods treat pixels as nodes and edges as arcs with cost, and the minimum-cost path is the boundary.

Last-minute revision

Encoder = mapper, quantizer, symbol coder; only the quantizer is lossy.
Huffman merges the two smallest probabilities; $L_{avg}\ge H$.
$C_R=n_1/n_2$.
RLE stores (value, run length).
JPEG: 8x8 blocks, level shift 128, DCT, quantize, zigzag, Huffman.
Point mask centre is 8 with eight -1 neighbours.
Line masks have 2 on the line and -1 elsewhere.
Gradient magnitude $|G_x|+|G_y|$ (Sobel, Prewitt).
Edge linking needs similar magnitude and direction.
Hough normal form $\rho=x\cos\theta+y\sin\theta$.

Memory hooks

Mapper, Quantizer, Coder: MQC, and Q is the only loss.
Huffman: rare symbols get long codes.
JPEG: Divide, Zigzag, Zip (quantize, scan, entropy code).
Hough: every point votes, peaks win.

Coverage checklist

Encoding: Mapping, Quantizer, Coder: no past questions.
Error free compression: no past questions.
Lossy Compression schemes: no past questions.
JPEG Compression standard: no past questions.
Detection of discontinuation by point detection, Line detection, edge detection: no past questions.
Edge linking and boundary detection, Local analysis: no past questions.
Global processing via Hough transforms and graph theoretic techniques: no past questions.

Account

Digital Image Processing (AD-603 (B)) - Unit 4 Short Notes

How unit 4 is examined

Encoding: Mapping, Quantizer, Coder

Error free compression

Lossy Compression schemes

JPEG Compression standard

Detection of discontinuation by point detection, Line detection, edge detection

Edge linking and boundary detection, Local analysis

Global processing via Hough transforms and graph theoretic techniques

Last-minute revision

Memory hooks

Coverage checklist