Computer vision: Greyscale opening and top-hat

Small bright marks on an uneven background are hard to threshold. The top-hat transform flattens the background first.

What to build

A program that computes the greyscale opening of an image and its top-hat.

Requirements

  • Erosion: each pixel becomes the minimum of the k × k window centred on it, using only the pixels inside the image. Dilation: the same with the maximum.
  • Opening = dilation of the erosion. Top-hat = original − opening.
  • Print opening and its H rows, then top-hat and its H rows.

Input

Line 1: H, W and k (odd). Then H rows of W values.

Output

Two labelled blocks of H rows.

Constraints

1 ≤ H, W ≤ 40; k is 1, 3, 5 or 7.

Example

Input:

1 5 3
10 20 90 40 50

Output:

opening
10 20 40 40 40
top-hat
0 0 50 0 10

Why it works

Opening removes bright details smaller than the window but follows the slowly changing background, so subtracting it leaves just the small bright details on a flat, dark background.

Examples

Example 1 · Input
1 5 3
10 20 90 40 50
Expected output
opening
10 20 40 40 40
top-hat
0 0 50 0 10
Example 2 · Input
3 3 3
5 5 5
5 99 5
5 5 5
Expected output
opening
5 5 5
5 5 5
5 5 5
top-hat
0 0 0
0 94 0
0 0 0

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Greyscale erosion is the minimum of the k × k window and dilation the maximum, using only pixels inside the image.

Hint 2

Opening is the dilation of the erosion; the top-hat is the original minus the opening, pixel by pixel.

Solution

Show one correct solution (try it yourself first)
h, w, k = map(int, input().split())
img = [list(map(int, input().split())) for _ in range(h)]
m = k // 2


def filt(a, pick):
    return [[pick(a[y][x] for y in range(max(0, r - m), min(h, r + m + 1)) for x in range(max(0, c - m), min(w, c + m + 1))) for c in range(w)] for r in range(h)]


opened = filt(filt(img, min), max)
print("opening")
for row in opened:
    print(" ".join(map(str, row)))
print("top-hat")
for r in range(h):
    print(" ".join(str(img[r][c] - opened[r][c]) for c in range(w)))

Lesson: Morphology: erosion, dilation, opening and closing →