Histogram Equalization
Histogram Equalization
Histogram equalization improves image contrast by redistributing pixel intensities so they span the full [0, 255] range more uniformly. It is one of the most commonly used image enhancement techniques.
Given a 2D grayscale image with integer pixel values in [0, 255], apply histogram equalization and return the transformed image.
Algorithm
- Compute the histogram: count the frequency of each intensity value (0 through 255).
- Compute the cumulative distribution function (CDF): cdf[i] = sum of hist[0] through hist[i].
- Find cdf_min, the smallest non-zero value in the CDF (the CDF of the darkest pixel that actually appears).
- Map each pixel value v to a new value using:
If all pixels have the same value (total_pixels equals cdf_min), map every pixel to 0.
Examples
Input:
image = [[0, 1], [2, 3]]
Output:
[[0, 85], [170, 255]]
4 pixels, each unique. cdf = [1,2,3,4], cdf_min = 1. Mapping: 0 -> round(0/3255)=0, 1 -> round(1/3255)=85, 2 -> round(2/3255)=170, 3 -> round(3/3255)=255.
Input:
image = [[100, 100], [100, 100]]
Output:
[[0, 0], [0, 0]]
All pixels are identical. cdf_min equals total_pixels, so every pixel maps to 0.
Hint 1
Build the histogram first, then compute the running sum to get the CDF. The CDF at index i is the count of all pixels with value <= i.
Hint 2
Use Python's built-in round() function. Be careful: when total_pixels equals cdf_min, you must handle the division by zero separately.
Requirements
- Build a 256-bin histogram and its cumulative sum
- Use round() (not floor or ceil) when mapping to new values
- Handle the edge case where all pixels are the same value
Constraints
- Image has at least one pixel
- Pixel values are integers in [0, 255]
- Return a 2D list of integers with the same shape as input
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Histogram Equalization
Histogram Equalization
Histogram equalization improves image contrast by redistributing pixel intensities so they span the full [0, 255] range more uniformly. It is one of the most commonly used image enhancement techniques.
Given a 2D grayscale image with integer pixel values in [0, 255], apply histogram equalization and return the transformed image.
Algorithm
- Compute the histogram: count the frequency of each intensity value (0 through 255).
- Compute the cumulative distribution function (CDF): cdf[i] = sum of hist[0] through hist[i].
- Find cdf_min, the smallest non-zero value in the CDF (the CDF of the darkest pixel that actually appears).
- Map each pixel value v to a new value using:
If all pixels have the same value (total_pixels equals cdf_min), map every pixel to 0.
Examples
Input:
image = [[0, 1], [2, 3]]
Output:
[[0, 85], [170, 255]]
4 pixels, each unique. cdf = [1,2,3,4], cdf_min = 1. Mapping: 0 -> round(0/3255)=0, 1 -> round(1/3255)=85, 2 -> round(2/3255)=170, 3 -> round(3/3255)=255.
Input:
image = [[100, 100], [100, 100]]
Output:
[[0, 0], [0, 0]]
All pixels are identical. cdf_min equals total_pixels, so every pixel maps to 0.
Hint 1
Build the histogram first, then compute the running sum to get the CDF. The CDF at index i is the count of all pixels with value <= i.
Hint 2
Use Python's built-in round() function. Be careful: when total_pixels equals cdf_min, you must handle the division by zero separately.
Requirements
- Build a 256-bin histogram and its cumulative sum
- Use round() (not floor or ceil) when mapping to new values
- Handle the edge case where all pixels are the same value
Constraints
- Image has at least one pixel
- Pixel values are integers in [0, 255]
- Return a 2D list of integers with the same shape as input
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array