The hit-or-miss transform in plain words, every corner and end-point past question solved in answer-script form, and a pixel-by-pixel simulator for each SE.
In plain wordsErosion only asks "are these pixels white?". The hit-or-miss transform asks a stricter question: "are these pixels white and those pixels black?". That lets it find an exact pattern, such as a corner or the end of a line.
Slides 4–5. The hit-or-miss transform (HMT) is a powerful tool used to detect exact shapes or patterns in binary images: a pattern-matching morphological operator and very simple object recognition. It is used to look for particular patterns of foreground and background pixels.
A hit-or-miss (composite) SE contains three kinds of cells: 1 means foreground, 0 means background, and × (NaN) means "I don't care" / any pixel.
Slide 6. If the foreground and background pixels of the SE exactly match the foreground and background pixels of the image, the pixel under the origin of the SE is set to the foreground colour; otherwise to background.
A ⊛ B: g(x,y) = 1 if every 1 of B lies on a 1 of A and every 0 of B lies on a 0 of A (× ignored); else 0
Slide 7. Watch out: we actually look for fits, but call them hits when talking about the hit-or-miss transform. Whenever there is a "hit", we mark where the centre of shape B was on image A.
Slides 8–9. So far the 0s of an SE were treated as don't cares (we focused on the 1s only). The extended / composite SE distinguishes 0s from don't cares: for a fit, the 0s of the SE must also match 0s of the underlying image.
×
1
×
1
1
1
×
1
×
ordinary SE: only 1s matter
1
1
1
×
0
×
×
0
×
composite SE: 1s, 0s and ×
Hit-or-miss procedure, step by step
Must studyslides 10–14Came in past papers
Slide 10. The SE has pixels with three values: 0, the corresponding pixel must be 0; 1, it must be 1; don't care. An input neighbourhood matches only if every 0 and every 1 agree; one wrong pixel (a 1 where the SE wants 0) makes it false.
Slides 11–14 · procedure with an extended SEworked
Slide the SE [1 1 1; × 0 ×; × 0 ×] over the image like an erosion and look for exact fits: three 1s in the row above, a 0 at the centre, a 0 below.
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
0
0
1
1
1
1
1
0
1
1
1
1
1
1
0
1
0
0
1
1
1
1
1
0
1
input image
1
1
1
×
0
×
×
0
×
SE (origin = centre)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
output: 2 fits at (2, 3), (4, 7)
At (2,3): the row above is 1 1 1, the centre is 0 and the pixel below is 0, so it is a fit. Same at (4,7). Every other position fails somewhere.
Slide 14. What we actually did: we searched for the pattern, i.e. we actually performed an erosion, but with both the foreground and the background part of the SE: A ⊛ B = (A ⊖ B1) ∩ (Ac ⊖ B2), where B1 is the set of 1s and B2 the set of 0s.
Try it, step by step: the slide 11–14 search, every position: each 1 and 0 of the SE is compared with the image.
Corner detection with hit-or-miss
Must studyslides 15–17Came in past papers
Slides 15–16. Use structuring elements representing the four corners. Apply each SE, then use the OR operation to combine the four results.
How to design a corner SE: the centre is 1 (the corner pixel itself). The two arms of the corner are 1 (e.g. the pixel above and the pixel to the right). The two opposite sides and the diagonal between them are 0 (background). The other cells are × (don't care). Rotating it by 90° gives the other three corners.
×
1
×
0
1
1
0
0
×
B1 (up + right: bottom-left corner)
×
1
×
1
1
0
×
0
0
B2 (up + left: bottom-right corner)
×
0
0
1
1
0
×
1
×
B3 (down + left: top-right corner)
0
0
×
0
1
1
×
1
×
B4 (down + right: top-left corner)
Slide 17. More applications: any shape detection ("T", "L", …); corner detection (rotated SEs); endpoint detection (line terminals); skeletonization and thinning; pattern recognition of predefined shapes.
F23 Q2(e)3 + 3 marks
Apply the hit-and-miss transform to detect the corners of the binary image A ("CS"). (i) Design four SEs for detecting the four different corners and explain them. (ii) Using your SEs, extract all corners of A; show the output for each SE and the combined final output.
(i) Each SE is 3×3 with the origin at the centre: 1 = must be object, 0 = must be background, × = don't care. The centre and the two arm pixels are 1; the two opposite neighbours and the cell between them are 0; the rest are ×. B1 finds bottom-left corners (arms going up and right), B2 bottom-right, B3 top-right, B4 top-left. Outside the image counts as background.
(ii)
×
1
×
0
1
1
0
0
×
B1 (up + right: bottom-left corner)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
A ⊛ B1: 3 found (4, 7), (7, 1), (7, 7)
×
1
×
1
1
0
×
0
0
B2 (up + left: bottom-right corner)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
A ⊛ B2: 2 found (7, 5), (7, 11)
×
0
0
1
1
0
×
1
×
B3 (down + left: top-right corner)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A ⊛ B3: 3 found (1, 5), (1, 11), (4, 11)
0
0
×
0
1
1
×
1
×
B4 (down + right: top-left corner)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A ⊛ B4: 2 found (1, 1), (1, 7)
Combine with OR: a pixel is a corner if any SE marked it.
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
1
1
1
1
1
0
0
1
0
0
0
1
0
1
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
1
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
1
0
0
0
1
0
0
1
1
1
1
1
0
1
1
1
1
1
0
input A
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
1
0
final: 10 corners
Try it, step by step: F23 CS image: each corner SE in turn, then the OR. Use “Next phase” to move to the next SE.
F21 B1(a)iii2 marks
Design four hit-or-miss SEs for locating the four corners of an object.
×
1
×
0
1
1
0
0
×
B1 (up + right: bottom-left corner)
×
1
×
1
1
0
×
0
0
B2 (up + left: bottom-right corner)
×
0
0
1
1
0
×
1
×
B3 (down + left: top-right corner)
0
0
×
0
1
1
×
1
×
B4 (down + right: top-left corner)
1 = object, 0 = background, × = don't care, origin at the centre. Apply each one with A ⊛ Bi and OR the four results.
End points with hit-or-miss
Must studyslides 18–19, 30–32Came in past papers
Slides 30–32. Find the 4-connected endpoints of a binary image: the pixels where a line ends. An endpoint has exactly one object neighbour among its 4 neighbours. So each SE has the centre 1, three of the 4-neighbours 0, and the fourth (the direction the line continues) × don't care; the diagonals are ×. Four rotations cover lines ending in the four directions.
×
×
×
0
1
0
×
0
×
E1 (open above)
×
0
×
0
1
0
×
×
×
E2 (open below)
×
0
×
×
1
0
×
0
×
E3 (open left)
×
0
×
0
1
×
×
0
×
E4 (open right)
An isolated single pixel fits all four SEs, so it is also counted as an endpoint.
Slides 30–32 · F22 A3(c) ii–iii2 + 2 marks
(ii) Design hit-or-miss SEs for locating the 4-connected endpoints of an image. (iii) Locate all 4-connected endpoints of the given binary image with them; draw each result and the combined one.
(ii) The four SEs above: centre 1, three 4-neighbours 0, one 4-neighbour × (the arm), diagonals ×.
(iii)
×
×
×
0
1
0
×
0
×
E1 (open above)
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A ⊛ E1: 2 found (0, 6), (3, 1)
×
0
×
0
1
0
×
×
×
E2 (open below)
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A ⊛ E2: 5 found (0, 3), (0, 6), (0, 9), (2, 5), (3, 1)
×
0
×
×
1
0
×
0
×
E3 (open left)
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A ⊛ E3: 5 found (0, 6), (1, 11), (3, 1), (4, 11), (5, 7)
×
0
×
0
1
×
×
0
×
E4 (open right)
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A ⊛ E4: 4 found (0, 6), (1, 7), (3, 1), (5, 1)
Combine with OR: a pixel is a 4-connected endpoint if any SE marked it.
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
1
1
1
1
1
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
input A
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
final: 10 4-connected endpoints
Try it, step by step: slide 30–32 / F22 image, each endpoint SE then the OR.
SP23 Q3(c)1 + 4 + 2 + 1 marks
Binary image "CSE-44". (i) Which morphological technique locates all end points? (ii) Design four SEs for four different end points. (iii) Extract all end points with your SEs and explain. (iv) How many end points are in the final output?
(i) The hit-or-miss transform A ⊛ B, with one SE per end direction, combined by OR.
(ii) The four endpoint SEs above (centre 1, three 4-neighbours 0, the arm ×).
(iii)
×
×
×
0
1
0
×
0
×
E1 (open above)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A ⊛ E1: 4 found (2, 3), (3, 15), (5, 19), (5, 23)
×
0
×
0
1
0
×
×
×
E2 (open below)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A ⊛ E2: 6 found (1, 17), (1, 19), (1, 21), (1, 23), (3, 15), (4, 3)
×
0
×
×
1
0
×
0
×
E3 (open left)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A ⊛ E3: 5 found (1, 8), (1, 13), (3, 12), (3, 15), (5, 13)
×
0
×
0
1
×
×
0
×
E4 (open right)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
A ⊛ E4: 2 found (3, 15), (5, 5)
Combine with OR: a pixel is a end point if any SE marked it.
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
input A
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
1
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
final: 14 end points
(iv)14 end points in the final output.
Try it, step by step: SP23 CSE-44, each SE then the OR.
Boundary, thinning and thickening
slides 18–29On study list
Slide 18. Some basic morphological algorithms: boundary extraction, region filling; also extraction of connected components, thinning/thickening, skeletons.
Slide 19. Boundary extraction: extracting the boundary (outline) of an object is often extremely useful: β(A) = A − (A ⊖ B) (worked and simulated on the deck 11 page).
Thinning (slides 20–26)
Used to remove selected foreground pixels from binary images. After edge detection, lines are often thicker than one pixel; thinning makes them one pixel wide.
A ⊗ B = A − (A ⊛ B) = A ∩ (A ⊛ B)c
Symmetric thinning uses a sequence of SEs {B} = {B1, B2, …, Bn}, where Bi is a rotated version of Bi−1: A ⊗ {B} = ((…((A ⊗ B1) ⊗ B2)…) ⊗ Bn). If the foreground and background fit the SE exactly, the pixel at the origin is set to 0. The SE value at the origin is 1 or don't care.
Figure 9.21: the set A is thinned with B1, then B2 … B8, and the whole sequence is repeated until no more changes occur (convergence); finally the result is converted to m-connectivity.
Thickening (slides 27–29)
Used to grow selected regions of foreground pixels, e.g. to approximate the convex hull. It is the morphological dual of thinning:
A ⊙ B = A ∪ (A ⊛ B), A ⊙ {{B}} = ((…((A ⊙ B1) ⊙ B2)…) ⊙ Bn)
If the foreground and background match the SE exactly, the pixel at the origin is set to 1. The SE value at the origin is 0 or don't care.
Slide 29. A separate thickening algorithm: thin the background instead (thin Ac), then complement the result; remove any disconnected points.
thinning ⊗
thickening ⊙
equation
A − (A ⊛ B)
A ∪ (A ⊛ B)
on a match, the origin pixel becomes
0 (removed)
1 (added)
SE value at origin
1 or ×
0 or ×
use
make lines 1 pixel wide, skeletons
grow regions, convex hull
Traps and one-minute sheet
slides all
Hit-or-miss needs both parts to match: 1s on object and 0s on background. × cells are ignored.
Draw each SE with its origin, label each cell 1 / 0 / ×, and show one output grid per SE plus the OR. That's where the marks are.
Pixels outside the image count as background, so an object touching the border can still give a corner or endpoint there.
An isolated single pixel is an endpoint for every endpoint SE.
Thinning subtracts the HMT result; thickening adds it.