Let the histogram choose the threshold.
What to build
A program that finds Otsu's threshold and prints the resulting mask.
Requirements
- Try every distinct level t except the largest. The dark class is the pixels ≤ t and the bright class the rest.
- Choose the t with the largest between-class variance n0 × n1 × (μ0 − μ1)² / N²; on a tie, the smallest t. If the image has only one level, the threshold is that level.
- Print
threshold T, then the mask with#for pixels greater than T and.for the rest.
Input
Line 1: H and W. Then H rows of W values.
Output
The threshold line and H mask lines.
Constraints
1 ≤ H, W ≤ 80.
Example
Input:
2 3
10 10 200
10 200 200
Output:
threshold 10
..#
.##
Why it works
Every candidate split is scored by how big and how far apart its two classes are; the best split falls in the valley of a two-humped histogram.
Examples
Example 1 · Input
2 3 10 10 200 10 200 200
Expected output
threshold 10 ..# .##
Example 2 · Input
1 6 0 10 20 100 110 120
Expected output
threshold 20 ...###
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Count each level, sort the levels, and walk through them keeping running totals of the dark class's pixel count and sum.
Hint 2
The variance for threshold t is n0 × n1 × (mean0 − mean1)² / N²; keep the first t with the largest value.
Solution
Show one correct solution (try it yourself first)
h, w = map(int, input().split())
img = [list(map(int, input().split())) for _ in range(h)]
counts = {}
for row in img:
for v in row:
counts[v] = counts.get(v, 0) + 1
levels = sorted(counts)
N = h * w
total = sum(v * n for v, n in counts.items())
best_t, best = levels[0], -1.0
n0 = s0 = 0
for t in levels[:-1]:
n0 += counts[t]
s0 += t * counts[t]
n1, s1 = N - n0, total - s0
var = n0 * n1 * (s0 / n0 - s1 / n1) ** 2 / N ** 2
if var > best:
best_t, best = t, var
print("threshold", best_t)
for row in img:
print("".join("#" if v > best_t else "." for v in row))