Computer vision: Adaptive threshold for uneven light

A page photographed in uneven light defeats any single threshold. Compare each pixel with its own surroundings instead.

What to build

A program that finds dark ink with an adaptive mean threshold.

Requirements

  • For each pixel, take the k × k window centred on it, using only the pixels inside the image, and its mean.
  • The pixel is ink (#) when its value is less than (window mean − C); otherwise it is paper (.). Compare exactly, without rounding.
  • Print the mask, then ink pixels: N.

Input

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

Output

H mask lines and the count line.

Constraints

1 ≤ H, W ≤ 60; k is 3, 5 or 7; 0 ≤ C ≤ 50.

Example

Input:

1 5 3 5
100 100 50 100 100

Output:

..#..
ink pixels: 1

Why it works

Lighting changes slowly, so a pixel and its neighbours are lit alike; ink is darker than its local surroundings wherever it is on the page, while paper is about as bright as its neighbours.

Examples

Example 1 · Input
1 5 3 5
100 100 50 100 100
Expected output
..#..
ink pixels: 1
Example 2 · Input
2 6 3 10
100 120 140 160 180 200
100 60 140 160 120 200
Expected output
......
.#..#.
ink pixels: 2

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

Hints

Hint 1

For pixel (r, c) the window covers rows max(0, r − m) to min(H − 1, r + m), and likewise for columns, with m = k // 2.

Hint 2

Avoid fractions: v < mean − C is the same as v × count < sum − C × count.

Solution

Show one correct solution (try it yourself first)
h, w, k, C = map(int, input().split())
img = [list(map(int, input().split())) for _ in range(h)]
m = k // 2
count = 0
for r in range(h):
    line = ""
    for c in range(w):
        win = [img[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))]
        ink = img[r][c] * len(win) < sum(win) - C * len(win)
        line += "#" if ink else "."
        count += ink
    print(line)
print("ink pixels:", count)

Lesson: Thresholding and Otsu's method →