Computer vision: Otsu's threshold

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))

Lesson: Thresholding and Otsu's method →