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 -> newfor 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
2 2 10 20 20 30
10 -> 0 20 -> 170 30 -> 255 0 170 170 255
1 4 50 50 50 50
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))