N4, ND, N8, the three adjacencies (with m-adjacency explained), paths and components with a step-by-step path finder, and D4/D8/De, with every past question solved. Fall 2024 is left out.
Slide 4. Conventional indexing: the origin (0,0) is the top-left pixel; x runs down the rows, y runs across the columns. So p(x,y) means row x, column y. Around p:
| (x−1, y−1) | (x−1, y) | (x−1, y+1) |
| (x, y−1) | p (x, y) | (x, y+1) |
| (x+1, y−1) | (x+1, y) | (x+1, y+1) |
| set | pixels | distance from p |
|---|---|---|
| N4(p) (4-neighbours) | (x+1, y), (x−1, y), (x, y+1), (x, y−1): vertical and horizontal | 1 (unit distance) |
| ND(p) (diagonal) | (x+1, y+1), (x+1, y−1), (x−1, y+1), (x−1, y−1) | √2 = 1.414 (Euclidean) |
| N8(p) | N4(p) ∪ ND(p): all eight | 1 or 1.414 |
The relation is symmetric: q ∈ N4(p) implies p ∈ N4(q) (same for ND, N8).
Slide 10. Missing neighbours: when p lies on the image border some neighbours fall outside. Handle them by discarding them, zero padding or pixel replication.
For the 7×7 image (rows and columns numbered from 1, as on the slide) find N4(3,4), ND(3,4), N8(3,4), N4(1,1), N4(4,1), N8(7,7).
| 49 | 47 | 48 | 45 | 46 | 43 | 42 |
| 47 | 41 | 43 | 44 | 45 | 49 | 48 |
| 48 | 47 | 49 | 45 | 50 | 43 | 49 |
| 49 | 49 | 49 | 49 | 49 | 50 | 50 |
| 48 | 48 | 48 | 48 | 48 | 49 | 50 |
| 48 | 48 | 49 | 50 | 50 | 50 | 49 |
| 49 | 50 | 50 | 51 | 51 | 50 | 50 |
Slides 12–13. Adjacency depends on both the neighbourhood and the gray values. Two pixels are connected if they are neighbours and their gray levels satisfy a similarity criterion. In a binary image V = {1}; in a gray image V can be any subset of the 256 values.
| type | p and q (values in V) are adjacent if… |
|---|---|
| 4-adjacency | q ∈ N4(p) |
| 8-adjacency | q ∈ N8(p) |
| m-adjacency (mixed) | (i) q ∈ N4(p), or (ii) q ∈ ND(p) and N4(p) ∩ N4(q) has no pixel whose value is in V |
V = {0, 1, 2, 3, 5}. A = (0,0), B = (0,1), E = (1,1), C = (2,2), D = (3,3). Which pairs are 4-adjacent / 8-adjacent?
| 4 | 2 | 3 | 2 |
| 3 | 3 | 1 | 3 |
| 2 | 3 | 5 | 2 |
| 2 | 1 | 2 | 5 |
| pair | neighbours? | values in V? | 4-adjacent | 8-adjacent |
|---|---|---|---|---|
| A, B | yes (4-neighbours) | A = 4 ∉ V | no | no |
| A, C | no | A = 4 ∉ V | no | no |
| B, C | no: (0,1) and (2,2) are 2 rows apart | yes | no | no |
| C, D | diagonal | yes | no | yes |
| C, E | diagonal | yes | no | yes |
V = {0, 1, 2, 3, 5}. A = (0,0) = 4, B = (0,1) = 2, C = (2,2) = 5, D = (3,3) = 0. Which pairs are m-adjacent?
| 4 | 2 | 3 | 2 |
| 3 | 3 | 1 | 3 |
| 2 | 3 | 5 | 4 |
| 2 | 1 | 6 | 0 |
A, B / A, C: no, A = 4 ∉ V. B, C: not neighbours. C, D: D ∈ ND(C); N4(C) ∩ N4(D) = {(2,3) = 4, (3,2) = 6}, and neither 4 nor 6 is in V, so C and D are m-adjacent.
Slide 18. A digital path from p = (x0, y0) to q = (xn, yn) is a sequence of distinct pixels (x0, y0), (x1, y1), …, (xn, yn) where each pixel is adjacent to the next. n is the length of the path. If (x0, y0) = (xn, yn) the path is closed. 4-, 8- and m-paths use the matching adjacency.
Slide 19. p and q are connected in S if there is a path between them made only of pixels in S.
V = {1, 2}; p = (1,3), q = (3,3) in the slide's numbering (top-right and bottom-right).
| 0 | 1 | 1 |
| 0 | 2 | 0 |
| 0 | 0 | 1 |
8-path: two exist: (1,3) → (1,2) → (2,2) → (3,3) and (1,3) → (2,2) → (3,3). That ambiguity is what m-adjacency removes.
m-path: only (1,3) → (1,2) → (2,2) → (3,3). The diagonal step (1,3) → (2,2) is not allowed because they share the 4-neighbour (1,2) = 1 ∈ V. The step (2,2) → (3,3) is allowed: their shared 4-neighbours (2,3) and (3,2) are both 0.
4-path: absent: from (2,2) the only way down is through 0s.
Try it, step by step: slide 20: switch between 4-, 8- and m-paths and watch which steps are allowed.
V = {1, 2}. Find the m-connected path between p (bottom-left) and q (top-right). Is a 4-connected path possible?
| 4 | 2 | 3 | 2 |
| 3 | 3 | 1 | 3 |
| 2 | 3 | 2 | 2 |
| 2 | 1 | 2 | 3 |
4-path: none. m-path: (3,0)=2 → (3,1)=1 → (3,2)=2 → (2,2)=2 → (1,2)=1 → (0,3)=2, i.e. 2(p) → 1 → 2 → 2 → 1 → 2(q) as on the slide.
Try it, step by step: slide 23: the m-path, step by step. Try 4-path too: it fails.
Slide 24. Two subsets S1 and S2 are adjacent if some pixel of S1 is adjacent to some pixel of S2.
Slide 25. Connected component: for any pixel p in S, the set of pixels connected to it in S is a connected component of S. Example (V = {1}): 4-connectivity gives 3 components, m-connectivity 2: the lone 1 at the bottom right joins the top-right group through a diagonal whose shared 4-neighbours are 0.
| 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 |
Slides 26–28. If S has only one connected component, S is a connected set; a region is a connected set. Regions that are not adjacent are disjoint; two regions may be adjacent only under 8-adjacency (no 4-path between them, so their union is not 4-connected). The boundary (border, contour) of a region R is the set of its pixels that have at least one neighbour not in R; for a whole image, the first and last rows and columns.
Slide 29. For pixels p (x,y), q (s,t), z (v,w), a distance function D has three properties:
| 6 | 5 | 4 | 3 | 4 | 5 | 6 |
| 5 | 4 | 3 | 2 | 3 | 4 | 5 |
| 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| 3 | 2 | 1 | 0 | 1 | 2 | 3 |
| 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| 5 | 4 | 3 | 2 | 3 | 4 | 5 |
| 6 | 5 | 4 | 3 | 4 | 5 | 6 |
| 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 3 | 2 | 2 | 2 | 2 | 2 | 3 |
| 3 | 2 | 1 | 1 | 1 | 2 | 3 |
| 3 | 2 | 1 | 0 | 1 | 2 | 3 |
| 3 | 2 | 1 | 1 | 1 | 2 | 3 |
| 3 | 2 | 2 | 2 | 2 | 2 | 3 |
| 3 | 3 | 3 | 3 | 3 | 3 | 3 |
The pixels with D4 = 1 are exactly N4(p); the pixels with D8 = 1 are N8(p).
p = (3,4), q = (6,7). Find D4, D8, De.
What are the properties of the distance function for 3 pixels a, b and c? How are the city-block, chessboard and Euclidean distances between a and b calculated?
Properties: D(a,b) ≥ 0 with D(a,b) = 0 iff a = b; D(a,b) = D(b,a); D(a,c) ≤ D(a,b) + D(b,c).
For a = (x, y), b = (s, t): city block D4 = |x − s| + |y − t|; chessboard D8 = max(|x − s|, |y − t|); Euclidean De = √[(x − s)² + (y − t)²]. Example a = (0,0), b = (3,4):
Slide 33 · Problem 2.11 (glance): S1 and S2 are not 4-connected (q is not in N4(p)); they are 8-connected (q ∈ N8(p)); they are m-connected because q ∈ ND(p) and N4(p) ∩ N4(q) is empty of V-values.
Coordinates are (row, column) from 0 at the top-left unless the paper numbers from 1.
4×4 image, V = {0, 1, 2, 4}; p = (0,0) top-left, r = (0,3) top-right, q = (3,3) bottom-right. (i) Properties of the distance function for p, q, r. (ii) D4(p,q), D4(p,r), D8(p,q), De(p,q). (iii) N4(p), ND(p), N8(p). (iv) Is there a 4-path between p and q? (v) An m-path between p and q?
| 1 | 4 | 3 | 4 |
| 2 | 3 | 4 | 7 |
| 0 | 5 | 1 | 6 |
| 3 | 4 | 7 | 1 |
(i) D(p,q) ≥ 0 and = 0 only if p = q; D(p,q) = D(q,p); D(p,r) ≤ D(p,q) + D(q,r).
(ii) D4(p,q) = |0 − 3| + |0 − 3| = 6; D4(p,r) = |0 − 0| + |0 − 3| = 3; D8(p,q) = max(3, 3) = 3; De(p,q) = √(9 + 9) = 4.2426.
(iii) p is a corner, so the other neighbours fall outside: N4(p) = {(1,0) = 2, (0,1) = 4}; ND(p) = {(1,1) = 3}; N8(p) = {(1,0) = 2, (0,1) = 4, (1,1) = 3}.
(iv) 4-path: none. From p, the 4-neighbours in V are (0,1) = 4 and (1,0) = 2; from them every 4-step leads to 3, 5 or 7 (not in V), so q cannot be reached.
(v) m-path: (0,0)=1 → (0,1)=4 → (1,2)=4 → (2,2)=1 → (3,3)=1. Check the diagonal (0,1) → (1,2): shared 4-neighbours (0,2) = 3 and (1,1) = 3 are not in V, so the step is m-adjacent; likewise (2,2) → (3,3) with (2,3) = 6, (3,2) = 7.
Try it, step by step: SP22 Q3(b): the 4-path fails; the m-path goes round through the diagonals.
5×4 image [9, 34, 20, 0, 16, 21, 50, 5, 5, 6, 11, 15, 7, 8, 10, 2, 8, 7, 9, 0], V = {10, 20, 9, 7, 0, 5, 1, 3}. (i) Does an 8-path exist between the 9th and the 19th pixels? (ii) Their city-block, chessboard and Euclidean distances.
5×4 = 5 rows × 4 columns. Counting row by row from 1: the 9th pixel is (2,0) = 5 and the 19th is (4,2) = 9.
| 9 | 34 | 20 | 0 |
| 16 | 21 | 50 | 5 |
| 5 | 6 | 11 | 15 |
| 7 | 8 | 10 | 2 |
| 8 | 7 | 9 | 0 |
(i) Yes: (2,0)=5 → (3,0)=7 → (4,1)=7 → (4,2)=9. All values are in V and each step goes to an 8-neighbour (the step (3,0) → (4,1) is diagonal).
(ii)
Try it, step by step: SP23 Q2(e): the 8-path from the 9th to the 19th pixel.
S1 (columns 0–4) and S2 (columns 5–9) side by side; x = (3,2) in S1, y = (0,6) in S2. (i) Define a digital path. (ii) Is there a 4-path between x and y for V = {1, 2}? (iii) 4-path and m-path for V = {0, 1}. (iv) Are S1 and S2 4-adjacent for V = {1, 2}?
| 0 | 0 | 0 | 3 | 2 | 2 | 1 | 2 | 1 | 2 |
| 0 | 1 | 0 | 2 | 1 | 1 | 1 | 2 | 2 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 2 | 3 | 2 |
| 0 | 0 | 1 | 0 | 0 | 2 | 2 | 3 | 2 | 2 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
(i) A sequence of distinct pixels from x to y, each adjacent (4, 8 or m) to the next, all with values in V; the number of steps is its length.
(ii) V = {1, 2}: no 4-path. x's 4-neighbours are 0, 0, 1 and 0; the 1 below leads only to more 1s at the bottom that never reach the top-right through 1s and 2s.
(iii) V = {0, 1}: 4-path (3,2)=1 → (2,2)=0 → (2,3)=1 → (2,4)=1 → (1,4)=1 → (1,5)=1 → (1,6)=1 → (0,6)=1; m-path (3,2)=1 → (2,2)=0 → (2,3)=1 → (2,4)=1 → (1,4)=1 → (1,5)=1 → (1,6)=1 → (0,6)=1 (the same here: a 4-path is also an m-path).
(iv) Yes: column 4 of S1 and column 5 of S2 touch with values in {1, 2}: row 0: 2 | 2, row 1: 1 | 1, row 2: 1 | 1.
Try it, step by step: F21 B4(b): change nothing for V = {0, 1}: watch the 4-path being found.
State the difference between 4-neighbour, 8-neighbour and m-connectivity. For the 4×4 binary image [1010; 0101; 1010; 0101], find the number of connected components under each connectivity and discuss the effect of diagonal adjacency.
4-connectivity: only the up/down/left/right neighbours link pixels. 8-connectivity: the four diagonal neighbours link too. m-connectivity: 4-neighbours always link; a diagonal neighbour links only if the two pixels have no common 4-neighbour with a value in V (removes the double paths of 8-connectivity).
| 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
Every 1 has only 0s as 4-neighbours, so with 4-connectivity each 1 is alone: 8 components. Every 1 touches other 1s diagonally, so 8-connectivity joins all of them: 1 component. For each diagonal pair the two shared 4-neighbours are 0 (not in V), so every diagonal link is m-adjacent as well: 1 component.
Effect of diagonal adjacency: it merges pixels that touch only at corners, dropping the count from 8 to 1. m-connectivity keeps those joins here and only removes redundant (ambiguous) diagonal links where a 4-connection already exists.
| what | formula |
|---|---|
| N4(p) | (x±1, y), (x, y±1) |
| ND(p) | (x±1, y±1) |
| D4 | |x − s| + |y − t| |
| D8 | max(|x − s|, |y − t|) |
| De | √[(x − s)² + (y − t)²] |