DIP Past Questions

Image is 4×5, so N = 20 pixels; L = 8 gray levels (0 to 7).

Bit plane 2 is the MSB (weight 4), plane 1 has weight 2, plane 0 has weight 1 (3-bit image).

value = 4·b2 + 2·b1 + 1·b0

Task 1: 3×3 max filter at (3,2) (row 3, column 2, counted from 0 at the top-left)

sorted: 0, 0, 0, 0, 0, 1, 1, 5, 5 → max = 5

Max filter output at (3,2) = 5

Task 2: 3×3 negative Laplacian at (3,2)

Σ w·z = (-1)(0) + (-1)(1) + (4)(1) + (-1)(0) + (-1)(0) = 3

Laplacian response at (3,2) = 3

Task 3: mask that averages the 4 neighbours and leaves out the centre

g(x,y) = ¼ [ f(x−1,y) + f(x+1,y) + f(x,y−1) + f(x,y+1) ]

Approach 1 (without background): s = 255 if 120 ≤ r ≤ 200, else 0

Approach 2 (with background): s = 255 if 120 ≤ r ≤ 200, else s = r

i) Original = 512 × 512 × 8 bits = 2,097,152 bits = 262,144 bytes = 256 KB. Compressed = 64 KB.

C_R = 256 KB / 64 KB = 4 (4:1)

ii) RLE of AAAAABBBCCDAA

(A,5) (B,3) (C,2) (D,1) (A,2)

iii) ABAB… length 100: every run has length 1, so there are 100 runs → 100 (symbol, count) pairs.

Encoded length = 100 pairs × 2 bytes = 200 bytes, original = 100 bytes

C_R = 100/200 = 0.5: RLE expands the data (slide 109: small runs give expansion instead of compression).

iv) Huffman for A 0.4, B 0.3, C 0.2, D 0.1

Sort by probability (largest first). Repeatedly add the two smallest and re-sort (a sum that ties goes below the equal ones). Then walk back from the last column: the upper branch gets 0, the lower gets 1.

L_avg = Σ l(r_k)·p(r_k) = (0.4)(1) + (0.3)(2) + (0.2)(3) + (0.1)(3) = 1.9 bits/symbol

H = −Σ p·log₂p = −(0.4)log₂(0.4) + −(0.3)log₂(0.3) + −(0.2)log₂(0.2) + −(0.1)log₂(0.1) = 1.8464 bits/symbol

Efficiency η = H / L_avg = 1.8464 / 1.9 = 97.18%

L_avg = 1.9 is just above the entropy 1.8464, as it must be (you cannot go below H).

Dictionary locations 0–255 already hold the single gray levels 0–255; new entries start at 256. Read the pixels left to right, top to bottom.

Encoded output: 7 8 40 100 256 258 260 259 257 100

Original = 16 pixels × 8 bits = 128 bits; encoded = 10 codes × 9 bits = 90 bits

C_R = 128/90 = 1.4222

Same image and same +2 error as the RMSE question above: e_rms = 2.

H = −Σ P log₂P = 2.1972 bits/pixel

Best lossless compression for a 3-bit image = 3 / H = 3 / 2.1972 = 1.3654

A lossy coder can go beyond this ratio because it is allowed to change pixels; the price is the error measured by e_rms.

Final interval = [0.1544, 0.15536)

Any number in that interval encodes "bbadc". Shortest: 0.155

Walk the boundary anticlockwise, starting at top-left pixel (0,2). Directions (8-connected): 0 →, 1 ↗, 2 ↑, 3 ↖, 4 ←, 5 ↙, 6 ↓, 7 ↘.

Chain code from top-left pixel (0,2) (CC): 56770113353 (11 moves)

Shape number (smallest circular shift of CC) → start-point invariant only: 01133535677

Circular first difference (CFD), slide 22 rule: each digit = (next code − this code) mod 8. The last digit wraps round: (first − last), because the boundary is closed.

CFD = 11011020262 → rotation invariant

NCFD = smallest circular shift of the CFD (start reading at digit 3) = 01102026211

Start + rotation invariant chain code (shape number) = 01102026211

You choose the image. Use something small and clean: a 4×4 square inside a 6×6 image, and a 3×3 square SE with the origin at the centre.

Algorithm (slide 61, edge detection by dilation): 1. dilate A by B; 2. subtract A. Edges = (A ⊕ B) − A.

Inner boundary instead (slide 119): β(A) = A − (A ⊖ B).

Write the set definitions too: A ⊕ B = {z | (B̂)_z ∩ A ≠ ∅}, A ⊖ B = {z | (B)_z ⊆ A}.

Each SE is 3×3: 1 = must be object, 0 = must be background, × = don't care. A pixel is marked when the SE fits it exactly (both its 1s and its 0s). Pixels outside the image count as background.

10 corner pixels: (1,1), (1,5), (1,7), (1,11), (4,7), (4,11), (7,1), (7,5), (7,7), (7,11)

Step 3. Non-maximum suppression: compare each pixel with its two neighbours along its gradient direction (the arrow). Keep it only if it is not smaller than both; otherwise set it to 0.

Step 4. Double thresholding with T_H = 100, T_L = 45: strong if g_N ≥ 100; weak if 45 ≤ g_N < 100; else 0.

Step 5. Hysteresis (connectivity): keep a weak pixel only if it is 8-connected to a strong pixel.

ii) False positive / false negative: 74 at (2,2) is weak but survives because it touches the strong 101; if it is noise, it is a false positive. 50 at (2,0) is weak with no strong neighbour, so it is dropped; if it was a real edge, that is a false negative. The 40 and 41 are below T_L and are removed for the same reason.

iii) T_H = 245, T_L = 10: no pixel reaches 245, so there are no strong edges. Hysteresis keeps a weak pixel only when it touches a strong one, so every weak pixel is dropped: the output is empty (all real edges become false negatives). A very low T_L would otherwise let noise in (false positives); the rule of thumb is T_H : T_L = 2:1 or 3:1 (slide 52), and 245:10 breaks it.

Step 1. Equalize the input histogram → H_k

Step 2. Equalize the specified histogram → S_k = G(z)

Step 3. Map: for each r_k take its H_k, find the S value closest to it, and read that z. If two S values are equally close, take the higher one (slide 58).

Region size = 13 pixels

4-connectivity: 8 component(s)

8-connectivity: 1 component(s)

m-connectivity: 1 component(s)

4-neighbours of every 1 are 0s, so under 4-connectivity each 1 is its own component. Diagonal neighbours are 1, so 8-connectivity joins them all. m-adjacency allows a diagonal link only when the two pixels share no 4-neighbour in V; here the shared 4-neighbours are all 0, so every diagonal link is allowed and the answer equals the 8-connected one.

Effect of diagonal adjacency: it merges pixels that touch only at corners, so the count drops from 8 to 1. m-connectivity keeps those joins but removes double (ambiguous) paths.