Computer vision: Filter objects, trace boundaries

After thresholding, a mask still holds noise. Drop the small objects and describe the outlines of the rest.

What to build

A program that removes small 8-connected objects and reports each remaining object's area, boundary length and fill ratio.

Requirements

  • Find the 8-connected objects, ordered by their first pixel in reading order. Keep those with area at least A; the others become background.
  • Print the cleaned map: # for boundary pixels of kept objects (a side neighbour is background or outside the image), o for their interior pixels and . elsewhere.
  • Then print kept K of N objects and, for each kept object in order, object i: area A, boundary B, fill F, where F is area ÷ bounding-box area with two decimal places.

Input

Line 1: H, W and the minimum area A. Then H rows of # and ..

Output

H map rows, the kept line and one line per kept object.

Constraints

1 ≤ H, W ≤ 40; A ≥ 1.

Example

Input:

4 5 2
###..
###.#
###..
.....

Output:

###..
#o#..
###..
.....
kept 1 of 2 objects
object 1: area 9, boundary 8, fill 1.00

Why it works

Area filtering removes specks that are smaller than any real object, and a pixel with a background neighbour on a side lies on the object's outline, so counting those pixels measures the outline's length.

Examples

Example 1 · Input
4 5 2
###..
###.#
###..
.....
Expected output
###..
#o#..
###..
.....
kept 1 of 2 objects
object 1: area 9, boundary 8, fill 1.00
Example 2 · Input
3 3 1
#..
.#.
..#
Expected output
#..
.#.
..#
kept 1 of 1 objects
object 1: area 3, boundary 3, fill 0.33

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

Hints

Hint 1

First collect every 8-connected object as a list of pixels, in reading order of their first pixel, then keep the lists with at least the minimum area.

Hint 2

A pixel is interior when all four side neighbours are inside the image and `#`; otherwise it is a boundary pixel.

Solution

Show one correct solution (try it yourself first)
h, w, min_area = map(int, input().split())
grid = [input() for _ in range(h)]
seen = [[False] * w for _ in range(h)]
objects = []
for r in range(h):
    for c in range(w):
        if grid[r][c] == "#" and not seen[r][c]:
            seen[r][c] = True
            stack, cells = [(r, c)], []
            while stack:
                y, x = stack.pop()
                cells.append((y, x))
                for dy in (-1, 0, 1):
                    for dx in (-1, 0, 1):
                        ny, nx = y + dy, x + dx
                        if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] == "#" and not seen[ny][nx]:
                            seen[ny][nx] = True
                            stack.append((ny, nx))
            objects.append(cells)
kept = [cells for cells in objects if len(cells) >= min_area]


def on(y, x):
    return 0 <= y < h and 0 <= x < w and grid[y][x] == "#"


out = [["."] * w for _ in range(h)]
report = []
for i, cells in enumerate(kept, 1):
    edge = 0
    for y, x in cells:
        if on(y - 1, x) and on(y + 1, x) and on(y, x - 1) and on(y, x + 1):
            out[y][x] = "o"
        else:
            out[y][x] = "#"
            edge += 1
    rows = [y for y, x in cells]
    cols = [x for y, x in cells]
    box = (max(rows) - min(rows) + 1) * (max(cols) - min(cols) + 1)
    report.append(f"object {i}: area {len(cells)}, boundary {edge}, fill {len(cells) / box:.2f}")
for row in out:
    print("".join(row))
print(f"kept {len(kept)} of {len(objects)} objects")
for line in report:
    print(line)

Lesson: Connected components and contours →