Computer vision: Histogram equalisation

Equalisation spreads crowded brightness levels apart, revealing detail in dull images.

What to build

A program that equalises a greyscale image and prints its look-up table and the result.

Requirements

  • cdf(v) is the number of pixels with value at most v, N is the number of pixels, and cdf_min is the cdf of the darkest value present.
  • Each value v present maps to (cdf(v) − cdf_min) × 255 / (N − cdf_min), rounded to the nearest whole number with halves rounded up. If the image has only one value, it maps to itself.
  • Print v -> new for each value present, in increasing order, then the new image rows.

Input

Line 1: H and W. Then H rows of W values from 0 to 255.

Output

One line per distinct value, then H rows.

Constraints

1 ≤ H, W ≤ 100.

Example

Input:

2 2
10 20
20 30

Output:

10 -> 0
20 -> 170
30 -> 255
0 170
170 255

Why it works

The cdf rises fastest at crowded levels, so mapping through it pushes those levels apart; subtracting cdf_min makes the darkest level 0 and dividing by N − cdf_min makes the brightest 255.

Examples

Example 1 · Input
2 2
10 20
20 30
Expected output
10 -> 0
20 -> 170
30 -> 255
0 170
170 255
Example 2 · Input
1 4
50 50 50 50
Expected output
50 -> 50
50 50 50 50

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

Hints

Hint 1

Count each level in a dictionary, then walk the levels in increasing order to build the running total cdf(v).

Hint 2

Round half up with whole numbers: for a = (cdf(v) − cdf_min) × 255 and b = N − cdf_min, the rounded value is (2a + b) // (2b).

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
n = h * w
lut, running, first = {}, 0, None
for v in sorted(counts):
    running += counts[v]
    if first is None:
        first = running
    if n == first:
        lut[v] = v
    else:
        a, b = (running - first) * 255, n - first
        lut[v] = (2 * a + b) // (2 * b)
for v in sorted(lut):
    print(f"{v} -> {lut[v]}")
for row in img:
    print(" ".join(str(lut[v]) for v in row))

Lesson: Histograms and contrast →