Computer vision: Opening and closing

Opening and closing clean masks: one removes specks, the other fills holes.

What to build

A program that applies a sequence of morphological operations with a square or cross element.

Requirements

  • The element is square (the 3 × 3 block) or cross (the pixel and its four neighbours above, below, left and right).
  • Operations are erode, dilate, open (erode then dilate) and close (dilate then erode), applied left to right. Outside the image counts as background.
  • Print the final image, then set pixels: N.

Input

Line 1: H, W and the element. Then H rows of # and .. Last line: the operations, separated by spaces.

Output

H rows and the count line.

Constraints

1 ≤ H, W ≤ 40; at most 10 operations.

Example

Input:

5 6 square
......
.###..
.###..
.###.#
......
open

Output:

......
.###..
.###..
.###..
......
set pixels: 9

Why it works

Each operation is erosion (all neighbours set) or dilation (any neighbour set) with the chosen element; opening and closing are just these two in opposite orders.

Examples

Example 1 · Input
5 6 square
......
.###..
.###..
.###.#
......
open
Expected output
......
.###..
.###..
.###..
......
set pixels: 9
Example 2 · Input
5 5 square
.....
.###.
.#.#.
.###.
.....
close
Expected output
.....
.###.
.###.
.###.
.....
set pixels: 9

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

Hints

Hint 1

Write one function `morph(img, kind)` that erodes or dilates once, using a list of (row, column) offsets for the element.

Hint 2

`open` is erode then dilate; `close` is dilate then erode. Apply the operations in the order given.

Solution

Show one correct solution (try it yourself first)
h, w, shape = input().split()
h, w = int(h), int(w)
img = [[ch == "#" for ch in input()] for _ in range(h)]
ops = input().split()
if shape == "square":
    offs = [(i, j) for i in (-1, 0, 1) for j in (-1, 0, 1)]
else:
    offs = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)]


def morph(img, kind):
    out = []
    for r in range(h):
        row = []
        for c in range(w):
            near = [0 <= r + i < h and 0 <= c + j < w and img[r + i][c + j] for i, j in offs]
            row.append(all(near) if kind == "erode" else any(near))
        out.append(row)
    return out


PLAN = {"erode": ["erode"], "dilate": ["dilate"], "open": ["erode", "dilate"], "close": ["dilate", "erode"]}
for op in ops:
    for step in PLAN[op]:
        img = morph(img, step)
for row in img:
    print("".join("#" if v else "." for v in row))
print("set pixels:", sum(sum(row) for row in img))

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