Part 2: Equalize

Digital processing can do an amazing job of enhancing a photograph. Consider, for example, the countryside image below at left. Particularly when you compare it to the enhanced version on the right, the picture on the left seems hazy. The enhanced version is the result of applying an algorithm called histogram equalization, which grayscales the image and spreads out the intensities to increase its effective contrast and make it easier to identify individual features.

Histogram equalization takes advantage of the fact that the human eye perceives some colors as brighter than others, similar to how it perceives tones of certain sound frequencies as louder than others. Green, for example, appears brighter than red or blue, which tend to make images appear darker. Your job is to implement the histogram equalization algorithm, which can be broken down into the following steps, each of which is well-suited to be decomposed into its own method:

1. Compute the luminosity histogram for the source image
2. Compute the cumulative luminosity histogram from the luminosity histogram
3. Use the cumulative luminosity histogram to modify each pixel to increase contrast 

Computing the Luminosity Histogram

To compute the luminosity histogram of the source image, we need to first define luminosity. Luminosity is a standardized calculation of the “brightness” of a pixel based on its RGB values. The luminosity is an integer between 0 and 255, just as the intensity values for red, green, and blue are. A luminosity of 0 indicates black, a luminosity of 255 indicates white, and any other color falls somewhere in between. There is a provided method called computeLuminosity that you can use in DarkRoomAlgorithms.java that takes RGB values for a pixel and returns its luminosity for those values. 

int luminosity = computeLuminosity(red, green, blue);

Now, we want to compute the luminosity histogram of the source image, which represents the distribution of brightness in the source image. Specifically, it’s an array of 256 integers – one for each possible luminosity value – where each entry in the array represents the number of pixels in the image with that luminosity. For example, the entry at index 0 of the array represents the number of pixels in the image with luminosity 0, the entry at index 1 represents the number of pixels in the image with luminosity 1, and so on. 

An image’s luminosity histogram says a lot about the distribution of brightness throughout the image. The example above shows the original low-contrast picture of the countryside at the top, along with its image histogram. The bottom row shows an image and histogram for a high-contrast picture. Images with low contrast tend to have histograms more tightly clustered around a small number of values, while images with higher contrast tend to have histograms that are more spread out throughout the full possible range of values. We will eventually use this histogram to modify images to spread their brightness distributions out to be more like the lower image.

Compute the Cumulative Luminosity Histogram

Now we need to take the luminosity histogram from the previous step and from it create the cumulative luminosity histogram, which is useful later in the algorithm. The cumulative luminosity histogram is the same size as the regular luminosity histogram; it’s also an array of 256 integers, one for each possible luminosity value. However, instead of each entry in the array representing the number of pixels in the image with that luminosity, each entry represents the number of pixels in the image with that luminosity or less. For example, the entry at index 2 of the array represents the number of pixels in the image with luminosity 0, 1 or 2, the entry at index 3 represents the number of pixels in the image with luminosity 0, 1, 2 or 3, and so on. As an example, if the first six entries in the image histogram were 

the corresponding cumulative histogram would be

As an example, the value at index 3 is 16 because 1+3+5+7 pixels have a luminosity of 3 or less.

An image’s cumulative luminosity histogram says a lot about the distribution of brightness throughout the image. Notice how the low-contrast image at the top has a sharp transition in its cumulative luminosity histogram, representing the smaller distribution of luminosity values. Meanwhile, the normal-contrast image on the bottom has a smoother increase over time. We will eventually use this histogram to modify images to spread their brightness distributions out to be more like the lower image.

Modify Each Pixel to Increase Contrast

Now that we have the cumulative luminosity histogram, we can use it to modify each pixel to increase the image’s overall brightness and contrast. The key is that we want to modify the image to spread its luminosity values across as much of the range of possible luminosity values as we can. We can do this via the following steps:

To understand how this works, suppose you had a low-contrast 10-pixel image with luminosities only between 125-130. The cumulative histogram for this example image could be as follows:

To make this image higher contrast, we want to spread these luminosities out so they occupy more of the range of luminosity values than just 125-130; this will result in more variation among pixel luminosities, and thus a better image.

For example, let’s take the pixel with luminosity 125. In our cumulative histogram above, there is only 1 total pixel (this one) with luminosity ≤ 125. Therefore, the percentage of pixels with that luminosity or less is 1/10 = 10%. Ideally, this pixel would be 10% bright, to use as much of the luminosity spectrum as possible. The value that achieves this is 10% of 255 (the maximum luminosity), or 25.5. Thus, we want this pixel to have a luminosity of 25 (round down). One property of luminosity is that, if the R, G and B values of a pixel are the same, the luminosity is just this value. Therefore, we can change the pixel at this location to be a grayscale pixel with an R, G, and B value of 25. Thus, for each pixel we calculate the percentage of pixels with that luminosity or less, and multiply this by 255 to get a new luminosity for that pixel, which we use for its R, G and B values. 

As another example, let’s take a pixel with luminosity 129. In our cumulative histogram above, there are 9 pixels with luminosity ≤ 129. Therefore, the percentage of pixels with that luminosity or less is 9/10 = 90%. Ideally, this pixel would be 90% bright, to use as much of the luminosity spectrum as possible. The value that achieves this is 90% of 255, or 229.5. Thus, we want this pixel to have a luminosity of 229 (round down). We therefore change the pixel at this location to be a grayscale pixel with an R, G, and B = 229. 

Notice how a luminosity of 125 is mapped to a new luminosity of 25, and a luminosity of 129 is mapped to a new luminosity of 229; this dramatically expands the range of luminosity values in the image, resulting in higher contrast and better detail.