Computer vision: Label regions and measure them

Labelling turns a mask into a table of objects with sizes and positions.

What to build

A program that labels 8-connected regions and reports each one's area, bounding box and centroid.

Requirements

  • Number the regions 1, 2, 3, … in the order their first pixel appears in reading order (row by row, left to right). There are at most 9.
  • Print the label map: each pixel's label digit, or . for background.
  • Then, for each region, print region K: area A, rows R1-R2, columns C1-C2, centroid (Y, X) with the centroid's mean row Y and mean column X to two decimal places.

Input

Line 1: H and W. Then H rows of # and ..

Output

H map rows, then one line per region.

Constraints

1 ≤ H, W ≤ 40.

Example

Input:

3 4
##..
#..#
...#

Output:

11..
1..2
...2
region 1: area 3, rows 0-1, columns 0-1, centroid (0.33, 0.33)
region 2: area 2, rows 1-2, columns 3-3, centroid (1.50, 3.00)

Why it works

The flood fill gathers each region's pixels, and the area, box and centroid are a count, minimums and maximums, and means over that list.

Examples

Example 1 · Input
3 4
##..
#..#
...#
Expected output
11..
1..2
...2
region 1: area 3, rows 0-1, columns 0-1, centroid (0.33, 0.33)
region 2: area 2, rows 1-2, columns 3-3, centroid (1.50, 3.00)
Example 2 · Input
2 3
#.#
.#.
Expected output
1.1
.1.
region 1: area 3, rows 0-1, columns 0-2, centroid (0.33, 1.00)

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

Hints

Hint 1

Scan in reading order; when you meet an unlabelled `#`, flood it with the next label and collect its pixels in a list.

Hint 2

The centroid is (sum of rows ÷ area, sum of columns ÷ area).

Solution

Show one correct solution (try it yourself first)
h, w = map(int, input().split())
grid = [input() for _ in range(h)]
labels = [[0] * w for _ in range(h)]
regions = []
for r in range(h):
    for c in range(w):
        if grid[r][c] == "#" and labels[r][c] == 0:
            regions.append([])
            k = len(regions)
            labels[r][c] = k
            stack = [(r, c)]
            while stack:
                y, x = stack.pop()
                regions[-1].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 labels[ny][nx] == 0:
                            labels[ny][nx] = k
                            stack.append((ny, nx))
for row in labels:
    print("".join(str(v) if v else "." for v in row))
for k, cells in enumerate(regions, 1):
    rows = [y for y, x in cells]
    cols = [x for y, x in cells]
    n = len(cells)
    print(f"region {k}: area {n}, rows {min(rows)}-{max(rows)}, columns {min(cols)}-{max(cols)}, centroid ({sum(rows) / n:.2f}, {sum(cols) / n:.2f})")

Lesson: Connected components and contours →